跳转至

Week 12 - Translation 2

Recap: Translate expressions

上一节课我们介绍了如何翻译源代码到 LLVM IR，最主要的部分是如何计算一个对象的地址，即计算一个表达式的左值语义。

引用一个对象

当我们在 expression 中使用 Identifier 引用一个变量时，我们得到的实际上是该变量的地址。

  • 对于局部变量：它的地址是由 alloca 指令在栈上开辟的

  • 对于全局变量：它的地址是由 = global <ty> 指定的

  • 对于参数：默认情况下，它没有地址（参数的传递是值传递）。但是，我们可以人为地开辟一个局部变量，并将该参数的值 store 到这个局部变量中：

    int func0(int a) {
    return a + 1;
}

    define i32 @func0(i32 %a) {
entry:
%a.addr = alloca i32, align 4         ; store a's value to `&a`
store i32 %a, ptr %a.addr, align 4

%0 = load i32, ptr %a.addr, align 4   ; load `a` from `&a`

%add = add nsw i32 %0, 1
ret i32 %add                          ; add 1, and return.
}

得到一个对象的值

此处即为我们常说的 lvalue conversion，即 load 语义。当我们通过上述“引用一个对象”得到该对象的地址后，才能从这个地址读取出对象的值。

计算复杂的左值表达式

左值表达式，指的是其 Value Category 为 lvalue 的表达式

解引用

int *p;
*p = 123;
print(*p);

  • 第一行定义了 p 这个局部变量，即 p 这个 Identifier 指代的是 p 的地址（记作 &p）。

  • 第二行对 p 进行解引用，并对解出来的 lvalue 进行赋值，这里分为以下几步进行：

    1. 计算赋值号左侧的左值语义（即地址）：&p -> p，即一次 load

    2. 由于赋值操作符要求保留左侧操作数的左值语义，故此处不需要进行一次 lvalue conversion

    3. 计算赋值号右侧的右值语义（即值）：123 对应一个整数常量。

    4. 将值保存到地址里面：store ptr %p, 123，即一次 store

  • 第三行也对 p 进行了解引用，但是，在参数传递中，我们传递的是一个值，而非一个地址。所以此处会发生一次 lvalue conversion:

    1. 计算 *p 的左值语义（即地址）：&p -> p，即一次 load

    2. 计算 *p 的 右值语义（即值）：p -> *p，即第二次 load

取地址

"Except when it is the operand of ... the unary & operator, the ++ operator, the -- operator, or the left operand of the . operator or an assignment operator, an lvalue is converted to the value stored in the designated object (and is no longer an lvalue); this is called lvalue conversion."

对一个左值取地址时，返回的是一个右值。**但是，此时并不会发生一次 load 操作。**可以视为计算 &(expr) 的右值语义等于计算 (expr) 的左值语义。（(expr) 表示任意一个表达式，&(expr) 没有左值语义）。

结构体访问

"Except when it is the operand of the unary & operator, the ++ operator, the -- operator, or the left operand of the . operator or an assignment operator, an lvalue is converted to the value stored in the designated object (and is no longer an lvalue); this is called lvalue conversion."

计算 (expr).a 的左值语义时：

  1. 先计算 (expr) 的左值语义

  2. 然后，上述规则告诉我们，. operator 应该保留左侧操作数（即 (expr)）的左值属性

  3. 使用 gep %expr, 0, xx 来计算 (expr).a 的地址。

注意，上述步骤不存在一次对 expr 的 load！

结构体指针访问

(expr)->a 等价于 (*(expr)).a，即：

  1. 计算 *(expr) 的左值语义，然后 load 一次得到它的右值语义

  2. 对着 *expr 使用 gep %value_expr, 0, xx 来计算 (*(expr)).a 的地址。

指针加法

此处的指针加法包含了形如 (p - n) 的表达式，其语义等价于 (p + (-n))。

int arr[10];
int *p = &arr[0];
*(p + 1) = 123;
*(p++) = 456;
*(++p) = 456;

指针加法的语义是，该指针往前或往后第n个元素，所以它的计算方式如下：

  1. 计算 p 的值：先计算其左值语义 &p，然后 load 一次得到其值。

  2. 使用 gep %p, n 来向前或向后跳过 n 个元素。

注意这里是 gep %p, n 而不是 gep %p, 0, n！！

对指针的数组索引

我们在上节课提到的一个难点：

int *foo(struct ST *s) {
  return &s[1].Z.B[5][13];
}

ptr[1] 这样的表达式等价于：(ptr + 1)，即：先需要得到 ptr 的值，然后再往前或往后偏移n个对象（不是n个指针！）。

define ptr @foo(ptr %s) {
  %t1 = getelementptr %struct.ST, ptr %s, i32 1
  %t2 = getelementptr %struct.ST, ptr %t1, i32 0, i32 2
  %t3 = getelementptr %struct.RT, ptr %t2, i32 0, i32 1
  %t4 = getelementptr [10 x [20 x i32]], ptr %t3, i32 0, i32 5
  %t5 = getelementptr [20 x i32], ptr %t4, i32 0, i32 13
  ret ptr %t5
}

你可能会疑惑上述代码里面，得到 s 的值为什么没有一次 load：这是因为 ptr %s 是作为参数传入的，它本身就是一个值。

如果我们按照上述“本地拷贝一次”的方式处理参数，你会得到如下代码：

define dso_local ptr @foo(ptr noundef %s) #0 {
  %s.addr = alloca ptr, align 8
  store ptr %s, ptr %s.addr, align 8

  %s0 = load ptr, ptr %s.addr, align 8
  %4 = getelementptr inbounds %struct.ST, ptr %s0, i64 1
  %5 = getelementptr inbounds nuw %struct.ST, ptr %4, i32 0, i32 2
  %6 = getelementptr inbounds nuw %struct.RT, ptr %5, i32 0, i32 1
  %7 = getelementptr inbounds [10 x [20 x i32]], ptr %6, i64 0, i64 5
  %8 = getelementptr inbounds [20 x i32], ptr %7, i64 0, i64 13
  ret ptr %8
}

总结

  • 取地址 (p -> &p)：计算 p 的左值语义，直接将其视为右值语义
  • 解引用（p -> *p）：计算 p 的右值语义，直接将其视为左值语义
  • 结构体访问（expr.a）：计算 expr 的左值语义，使用 GEP 计算 expr.a 的左值语义
  • 结构体解引用（expr->a）：相当于对 expr 解引用一次，得到其右值语义，并将其视为左值语义，然后进行 GEP 计算地址
  • 指针加法与数组索引（p[n] 与 (p + n)）：计算 p 的右值语义，然后使用 GEP 偏移指针。

计算逻辑表达式

在 LLVM IR 中，逻辑值有它单独的类型：i1 和单独的两个常数：true 和 false。

<result> = icmp <cond> <ty> <op1>, <op2>   ; yields i1

icmp 指令用于比较两个 operands,它们的类型必须都是 <ty>（整型或指针），<cond> 表示比较模式：

  • eq, ne：相等与不相等
  • ugt, uge, ult, ule, sgt, sge, slt, sle：无符号（unsigned）/有符号（signed）大于/大于等于/小于/小于等于

计算 Expression 的逻辑值

在 C 语言中：非 0 即为 true，0 则为 false。

所以，我们可以用以下语句来将一个 expression 转换为逻辑值：%result = icmp ne i32 %operand, 0

使用条件分支

br i1 <cond>, label <iftrue>, label <iffalse>

br 条件跳转可以根据某个逻辑值（i1）来跳转控制流。

此处的 label 是一个 Basic Block 的名字。在 LLVM IR 中，每个 Basic Block 都显式或隐式的拥有一个 label。

int func0() {
    int cond1 = 1;
    if (cond1) {
        cond1++;
    } else {
        cond1--;
    }
    return 0;
}

define dso_local i32 @func0() #0 {
entry:
  %cond1 = alloca i32, align 4
  store i32 1, ptr %cond1, align 4

  %0 = load i32, ptr %cond1, align 4            ; load the value of `cond1`
  %tobool = icmp ne i32 %0, 0                   ; is that true?
  br i1 %tobool, label %if.then, label %if.end  ; true -> if.then, otherwise -> if.else

if.then:
  %1 = load i32, ptr %cond1, align 4
  %inc = add nsw i32 %1, 1
  store i32 %inc, ptr %cond1, align 4           ; cond++;
  br label %if.end                              ; goto if.end

if.else:
  %2 = load i32, ptr %cond1, align 4
  %dec = add nsw i32 %2, -1
  store i32 %dec, ptr %cond1, align 4           ; cond--;
  br label %if.end                              ; goto if.end

if.end:
  ret i32 0
}

注意：LLVM IR 中的 Basic Blocks 并不是线性排列的，而是从 Root Block 开始的一个任意顺序（Entry Block 不能有 Predecessors）。它不像汇编，跳转指令若不跳转则是执行下一条指令。

LLVM IR 总是要求 Terminator Instructions 明确指定下一个 Basic Block 的 label，而不是通过 Fall Through 的方式指定。

在上述例子中，你可以把 if.end 放到 if.then 之前，尽管这样不会改变程序的逻辑，但是会影响其生成汇编的顺序。

计算复杂逻辑表达式

对于 && 与 || 而言，我们不能将左右两侧同时算出来，然后再做 bitwise AND/OR。语言规范规定了：如果左侧操作数被计算为 true，则右侧才能/不能被计算。

如果将左右两侧同时算出来再做 bitwise AND/OR 会发生什么

表达式的计算可能产生副作用（side effects），或者导致程序错误，例如：

int cnt = 0;

int a = cond1 && (cnt++);

int *p = NULL;
int b = p && *p >= 3;

int func0() {
    int cond1 = 1;
    int todo = 0;

    if (cond1 && 1 >= 0) {
        todo ++;
    } else {
        todo--;        
    }
    return 0;
}

解决方法是用一个新的 Basic Block 来实现对右侧表达式的计算：

define dso_local i32 @func0() #0 {
entry:
  %cond1 = alloca i32, align 4
  %todo = alloca i32, align 4
  store i32 1, ptr %cond1, align 4
  store i32 0, ptr %todo, align 4       ; init

  %0 = load i32, ptr %cond1, align 4
  %tobool = icmp ne i32 %0, 0           ; lhs of &&

  br i1 %tobool, label %land.lhs.true, label %if.else
                                        ; if lhs true, check rhs -> land.lhs.true
                                        ; otherwise -> if.else
land.lhs.true:                          
  %1 = load i32, ptr %cond1, align 4
  %cmp = icmp sge i32 %1, 0
  br i1 %cmp, label %if.then, label %if.else    ; lhs true && rhs true -> if.then
                                                ; otherwise -> if.else

if.then:
  %2 = load i32, ptr %todo, align 4
  %inc = add nsw i32 %2, 1
  store i32 %inc, ptr %todo, align 4
  br label %if.end

if.else:
  %3 = load i32, ptr %todo, align 4
  %dec = add nsw i32 %3, -1
  store i32 %dec, ptr %todo, align 4
  br label %if.end

if.end:
  ret i32 0
}