Week 11 - Translation 1

Recap: LLVM IR

上一节课我们介绍了 LLVM IR，它是一种强类型的、基于 SSA 静态单赋值的 IR。

LLVM IR 中，指令打包在 Basic Blocks 中，每个 Basic Block 都具有一个入口标签（label），每个 Basic Block 的 Terminator Instruction 都指向了该块结束后去向哪里；因此， Basic Blocks 又构成一张控制流图（CFG）。

Basic Block

Basic Block (基本块) 是 一段连续执行、没有分支跳转（中途不转向）的指令序列 ，并且：

1. 只有一个入口：每个基本块只能从第一条指令进入。
2. 只有一个出口：每个基本块由 Terminator Instruction (终结指令) 结束。
3. 中间没有跳转：除了最后一条指令外，块内的所有指令都是顺序执行的。

LLVM 指令集包含以下几种指令：

1. Terminator Instructions: 结束一个 Basic Block 的指令
2. Binary Instructions: 二元操作指令，接收两个同类型的 operands，产生一个同类型的 Value.
3. Bitwise Binary Instructions: 一些特殊的二元操作指令，特指位运算。
4. Memory Instructions: 读、写、和分配内存的指令
5. Other Instructions: 其他指令

LLVM 的指令集更加贴近于汇编指令，例如 RISC-V 中的 rs1, rs2 和 rd.

LLVM IR 的 SSA 的意思是：IR 中，每一个变量仅可以被赋值一次。实际上，当我们在源代码中定义一个变量时，其语义是为它开辟一个内存空间，而这个内存空间的地址是不变的。在 LLVM IR 中，不变的即是这个地址，可变的是内存空间中的值。

int func() {
    int a;
    a = 2;
    return a + 4;
}

define i32 @func() {
  %a = alloca i32           ; int a;
  store i32 2, ptr %a       ; a = 2;
  %0 = load i32, ptr %a     ; return a + 4;
  %add = add nsw i32 %0, 4  ; ..
  ret i32 %add              ; ..
}

同理，当我们定义一个全局变量时，尽管我们声明它是 i32 类型，但是其 LLVM IR 变量的类型是一个 ptr。

int global_var;

int main() {
    global_var = 123;
}

@global_var = dso_local global i32 0, align 4

define dso_local i32 @main() #0 {
entry:
  store i32 123, ptr @global_var, align 4
  ret i32 0
}

计算表达式

Recap: 表达式的作用

(1) An expression is a sequence of operators and operands that specifies computation of a value, or that designates an object or a function, or that generates side effects, or that performs a combination thereof. The value computations of the operands of an operator are sequenced before the value computation of the result of the operator.

表达式 (expression) 是一个操作符 (operators) 和操作数 (operands) 的序列，它用于：

• 指定一个值的计算（例如 2 + 3），

• 或指定一个对象（例如 x，它指向一块内存）或函数（例如 main），

• 或产生副作用 (side effects)（例如 x++，它使 x 的值发生了变化），

• 或执行以上任意的组合（例如 x = y + 5）。

在翻译阶段，我们就需要将上述的 “操作符和操作数的序列” 拆成一个一个的 LLVM IR 指令。

地址计算（左值语义）

在 Project 4 中，我们注意到有一些 Operator 所返回的值的 Value Category 是 lvalue，例如数组 subscript (a[2])、结构体访问（a.b, a->c）、指针解引用（*ptr）等。

这些表达式的语义即是：指定一个对象。计算这样的表达式，其语义就是：计算该对象的内存地址

简单对象

对于一个在局部或全局定义的变量，我们应当生成一个 LLVM IR identifier 来指代它的地址，例如：

1. 对于局部变量，使用 alloca 在栈帧上开辟指定大小的内存空间

   <result> = alloca <type> [, <ty> <NumElements>]   ; yields ptr:result
   %ptr = alloca i32
   

2. 对于全局变量：

   @<GlobalVarName> = global <Type> [<InitializerConstant>]    ; yields ptr
   @global_var = global i32 0
   

这样的 identifier 就指代着它们的地址。若要进行读写，则使用 load/store 指令进行读写。

<result> = load <ty>, ptr <pointer>
store <ty> <value>, ptr <pointer>

复杂对象

对于 LLVM 中的 Aggregate Types，包含 Array Type 和 Structure Type，我们该如何定义这样的变量以及得到其中某个元素（如 a[i] 和 stru.b）的地址？

对于复杂对象的定义，参照上述简单对象的定义，identifier 即指向了这个对象的 基地址(base address)。

计算某个元素对于基地址的偏移量时，我们需要使用 GEP getelementptr 指令：

<result> = getelementptr <ty>, ptr <ptrval>{, <ty> <idx>}*
<result> = getelementptr inbounds <ty>, ptr <ptrval>{, <ty> <idx>}*
<result> = getelementptr nusw <ty>, ptr <ptrval>{, <ty> <idx>}*
<result> = getelementptr nuw <ty>, ptr <ptrval>{, <ty> <idx>}*

The ‘getelementptr’ instruction is used to get the address of a subelement of an aggregate data structure. It performs address calculation only and does not access memory.

GEP 指令仅用于计算一个复合类型的子元素的地址，它不进行内存访问。

第一个参数始终是用作计算基础的 类型（可以理解为：将后续指针解读为该类型的指针）。第二个参数始终是 指针 ，它是起始的 基地址 。其余的参数是 索引 ，用于指示聚合对象中的哪些元素被索引。

每个索引的解释取决于正在被索引的类型。

• 第一个索引总是针对作为第二个参数给出的 指针值 进行索引
• 第二个索引则是针对**被指向类型**的值进行索引（这不一定是基地址直接指向的那个值，因为第一个索引可能非零）
• 依此类推。第一个被索引的类型必须是指针值，后续的类型可以是数组、向量和结构体。

后续被索引的类型**绝不能**是指针，因为这需要先加载（Load）指针才能继续进行计算。

每个索引参数的类型取决于它所索引的目标类型。当索引到 结构体（包括可选的紧缩结构体 packed structure）时，只允许使用 i32 整数常量（当使用索引向量时，它们必须全部是相同的 i32 整数常量）。当索引到 数组、指针 时，允许使用任意位宽的整数，且不需要是常量。在相关上下文中，这些整数被视为 有符号值 。

考虑以下 C 代码与生成的 LLVM 代码：

struct RT {
  char A;
  int B[10][20];
  char C;
};
struct ST {
  int X;
  double Y;
  struct RT Z;
};

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

%struct.RT = type { i8, [10 x [20 x i32]], i8 }
%struct.ST = type { i32, double, %struct.RT }

define ptr @foo(ptr %s) {
entry:
  %arrayidx = getelementptr inbounds %struct.ST, ptr %s, i64 1, i32 2, i32 1, i64 5, i64 13
  ret ptr %arrayidx
}

在上述示例中，第一个索引针对 %struct.ST* 类型（这是一个指针）进行索引，得到 %struct.ST = { i32, double, %struct.RT } 类型，这是一个结构体。第二个索引索引进该结构体的第三个元素，得到 %struct.RT = { i8 , [10 x [20 x i32]], i8 } 类型，这是另一个结构体。第三个索引索引进这个结构体的第二个元素，得到 [10 x [20 x i32]] 类型，这是一个数组。随后对该数组的两个维度进行索引，最终得到一个 i32 类型。getelementptr 指令返回一个指向该（最终）元素的指针。

请注意，对结构体进行 部分索引（indexing partially）是完全合法的，这将返回一个指向内部中间元素的指针。因此，给定测试用例的 LLVM 代码等价于：

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
}

你可能注意到，从 %t2 到 %t5 这一串 GEP 中，其中第一个 index 始终为 0；GEP 为什么要这么设计？

https://llvm.org/docs/GetElementPtr.html#what-is-the-first-index-of-the-gep-instruction

考虑以下代码：

AType *Foo;
...
X = &Foo->F;

很自然地会认为这里只有一个索引，即对字段 F 的选择。然而，在这个例子中，Foo 是一个指针。在 LLVM 中，必须显式地对该指针进行索引。而在 C 语言中，则是透明地（隐式地）穿过指针进行了索引。为了得到与 C 代码相同的地址位置，你需要为 GEP 指令提供两个索引操作数。第一个操作数用于“穿过”该指针进行索引；第二个操作数用于索引结构体的字段 F，这就好比是你写成了：

X = &Foo[0].F;

值计算

lvalue conversion

最常见的例子就是：Lvalue Conversion：即给定一个左值，读取它的值，即 load 语义。

lvalue conversion

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

例如，在表达式中指定一个左值，我们先需要使用上述地址计算的方式得到它的地址，然后进行一次内存读取，才能访问到它的值。

%a = alloca i32

; ...

%0 = load i32, ptr %a
%add = add nsw i32 %0, 4
ret i32 %add

在 Project 5 中，什么时候需要跳过 lvalue conversion：the unary & operator, the ++ operator, the -- operator。

例如：对 &a 的值计算中，我们不需要对 a 的地址进行一次 load 操作，而是直接将 a 的地址作为值计算的结果。

加减乘除

对于其他在 Project 4 中定义的其他的值计算，例如加减乘除、逻辑比较等基本运算，我们几乎可以找到对应的 LLVM IR 指令或其组合。

我们会在下一节课中覆盖逻辑比较等部分。

指针例子

考虑以下例子：

struct s0 {
    int a;
    int b[10][20];
};

int func(int i) {
    struct s0 s;
    struct s0 *ptr[10];
    ptr[2] = &s;

    ptr[3]->b[1][i] = i;

    return 0;
}

%struct.s0 = type { i32, [10 x [20 x i32]] }

define i32 @func(i32 %i) #0 {
entry:
  ; Allocations:
  %i.addr = alloca i32, align 4
  %s = alloca %struct.s0, align 4
  %ptr = alloca [10 x ptr], align 16

  ; Store i's value into %i.addr
  store i32 %i, ptr %i.addr, align 4

  ; ptr[2] = &s;
  %arrayidx = getelementptr inbounds [10 x ptr], ptr %ptr, i64 0, i64 2
  store ptr %s, ptr %arrayidx, align 16

  ; calculate the address of `ptr[3]`
  %arrayidx1 = getelementptr inbounds [10 x ptr], ptr %ptr, i64 0, i64 3

  ; load it into %1, its a pointer to struct s0, it's a Dereference!!
  %1 = load ptr, ptr %arrayidx1, align 8

  ; calculate the address of `ptr[3]->b`
  %b = getelementptr inbounds nuw %struct.s0, ptr %1, i32 0, i32 1

  ; calculate the address of `ptr[3]->b[1]`
  %arrayidx2 = getelementptr inbounds [10 x [20 x i32]], ptr %b, i64 0, i64 1

  %2 = load i32, ptr %i.addr, align 4
  %idxprom = sext i32 %2 to i64
  ; calculate the address of `ptr[3]->b[1][i]`
  %arrayidx3 = getelementptr inbounds [20 x i32], ptr %arrayidx2, i64 0, i64 %idxprom

  ; load value from `i.addr`, store it into `ptr[3]->b[1][i]`
  %0 = load i32, ptr %i.addr, align 4
  store i32 %0, ptr %arrayidx3, align 4

  ret i32 0
}

GEP FAQ 的翻译

https://llvm.org/docs/GetElementPtr.html

以下内容由 Gemini 3 Pro 贡献

What is the first index of the GEP instruction?

快速回答：是对第二个操作数进行步进（step through）的索引。

关于第一个索引的困惑通常源于将 GetElementPtr 指令误认为仅仅是 C 语言的索引操作符。它们并不相同。例如，当我们在 C 语言中写下：

AType *Foo;
...
X = &Foo->F;

很自然地会认为这里只有一个索引，即对字段 F 的选择。然而，在这个例子中，Foo 是一个指针。在 LLVM 中，必须 显式地 对该指针进行索引。而在 C 语言中，则是 透明地（隐式地）穿过指针进行了索引。为了得到与 C 代码相同的地址位置，你需要为 GEP 指令提供 两个 索引操作数。第一个操作数用于“穿过”该指针进行索引；第二个操作数用于索引结构体的字段 F，这就好比是你写成了：

X = &Foo[0].F;

有时这个问题会被重新表述为：

为什么可以穿过第一个指针进行索引，但（类型遍历中遇到的）后续指针却不会被解引用？

答案很简单：因为执行该计算不需要访问内存。 GEP 指令的第二个操作数（即基地址）必须是一个指针类型的值。该指针的值是作为操作数 直接提供 给 GEP 指令的，不需要通过访问内存来获取。因此，必须对它进行索引，也就需要一个对应的索引操作数。

请考虑以下示例：

struct munger_struct {
  int f1;
  int f2;
};
void munge(struct munger_struct *P) {
  P[0].f1 = P[1].f1 + P[2].f2;
}
...
struct munger_struct Array[3];
...
munge(Array);

在这个“C”示例中，前端编译器（Clang）会为赋值语句中通过 P 进行的三次索引生成三条 GEP 指令。函数参数 P 将作为这三条 GEP 指令中每一条的 第二个操作数。

• 第三个操作数（即 GEP 的第一个索引）用于穿过该指针进行索引（对应 P[0], P[1], P[2]）。
• 第四个操作数（即 GEP 的第二个索引）将是进入 struct munger_struct 类型的字段偏移量，用于选择 f1 或 f2 字段。

因此，在 LLVM 汇编中，munge 函数看起来像这样：

define void @munge(ptr %P) {
entry:
  ; 计算 &P[1].f1 (索引 1, 字段 0)
  %tmp = getelementptr %struct.munger_struct, ptr %P, i32 1, i32 0
  %tmp1 = load i32, ptr %tmp
  ; 计算 &P[2].f2 (索引 2, 字段 1)
  %tmp2 = getelementptr %struct.munger_struct, ptr %P, i32 2, i32 1
  %tmp3 = load i32, ptr %tmp2
  %tmp4 = add i32 %tmp3, %tmp1
  ; 计算 &P[0].f1 (索引 0, 字段 0)
  %tmp5 = getelementptr %struct.munger_struct, ptr %P, i32 0, i32 0
  store i32 %tmp4, ptr %tmp5
  ret void
}

在每种情况下，第二个操作数都是 GEP 指令开始的指针。无论第二个操作数是参数、分配的内存还是全局变量，情况都是一样的。

为了让这一点更清楚，让我们看一个更晦涩的例子：

@MyVar = external global i32
...
%idx1 = getelementptr i32, ptr @MyVar, i64 0
%idx2 = getelementptr i32, ptr @MyVar, i64 1
%idx3 = getelementptr i32, ptr @MyVar, i64 2

这些 GEP 指令仅仅是在基于 MyVar 的基地址进行地址计算。它们的计算如下（使用 C 语法）：

idx1 = (char*) &MyVar + 0
idx2 = (char*) &MyVar + 4
idx3 = (char*) &MyVar + 8

由于已知 i32 类型长 4 个字节，索引 0、1 和 2 分别转换为 0、4 和 8 的内存偏移量。进行这些计算 不访问任何内存，因为 @MyVar 的地址是直接传递给 GEP 指令的。

这个例子中晦涩的部分在于 %idx2 和 %idx3 的情况。它们计算出的地址指向了 @MyVar 全局变量末尾之后的内存，因为该变量只有一个 i32 长，而不是三个 i32 长。虽然这在 LLVM 中是 合法的，但这并不建议，因为使用这些 GEP 指令产生的指针进行任何 load 或 store 操作都会触发 未定义行为 (UB)。

Why is the extra 0 index required?

快速回答：并不存在所谓的“多余”索引。

这个问题最常出现在将 GEP 指令应用于 全局变量 时，而全局变量始终是指针类型。例如，考虑以下代码：

%MyStruct = external global { ptr, i32 }
...
%idx = getelementptr { ptr, i32 }, ptr %MyStruct, i64 0, i32 1

上面的 GEP 指令通过索引结构体 %MyStruct 的 i32 类型字段，产生（返回）了一个 ptr。当人们第一次看到它时，往往会疑惑为什么需要那个 i64 0 索引。然而，仔细审视全局变量和 GEP 的工作原理，就会发现这是必须的。了解以下事实将消除这种困惑：

1. %MyStruct 的类型 不是 { ptr, i32 }，而是 ptr。也就是说，%MyStruct 是一个指针（指向该结构体），而不是结构体本身。
2. 注意观察 GEP 指令第二个操作数（即 %MyStruct）的类型是 ptr，这证实了第 1 点。
3. 第一个索引 i64 0 是必须的，用于 穿过（step over） 全局变量 %MyStruct。由于 GEP 指令的第二个参数必须始终是指针类型的值，因此第一个索引用于在该指针上进行步进。值为 0 意味着相对于该指针的偏移量为 0 个元素（即取指针指向的第一个对象）。
4. 第二个索引 i32 1 选择结构体的第二个字段（即那个 i32）。

---

解析与助记：

为了方便理解，你可以将 LLVM 的 GEP 指令映射回 C 语言的语义：

• 场景：全局变量 MyStruct 是一个指针（例如 StructType *MyStruct）。
• 目标：访问 MyStruct->field2。
• C 语言写法：&MyStruct->field2 等价于 &(*MyStruct).field2 或 &MyStruct[0].field2。
• LLVM 对应：
  • 第一个索引 0 对应 MyStruct[0]（解引用指针这一层，虽然 GEP 不读内存，但在算术上定位到了对象基址）。
  • 第二个索引 1 对应 .field2（在对象内部偏移）。

如果你省略了第一个 0，写成 GEP %MyStruct, 1，那么你计算的是 MyStruct[1] 的地址（即紧挨着当前结构体的下一个结构体的地址），而不是结构体内部的成员。

What is dereferenced by GEP?

快速回答：什么都没有。

GetElementPtr 指令 不解引用任何东西。也就是说，它绝 不会 以任何方式访问内存。那是 Load（加载）和 Store（存储）指令做的事情。GEP 仅仅参与 地址的计算。

例如，请看下面的代码：

@MyVar = external global { i32, ptr }
...
%idx = getelementptr { i32, ptr }, ptr @MyVar, i64 0, i32 1
%arr = load ptr, ptr %idx
%idx = getelementptr [40 x i32], ptr %arr, i64 0, i64 17

在这个例子中，我们有一个全局变量 @MyVar，它是一个指向“包含一个指针的结构体”的指针。让我们假设这个内部指针指向一个类型为 [40 x i32] 的数组。上面的 IR 将首先计算该内部指针的 地址，然后 加载（load）该指针，最后再 计算 第 18 个数组元素的地址。

这个过程 无法 用单个 GEP 指令来表示，因为它要求在计算过程中间进行一次内存解引用（即读取那个指针的值）。

然而，下面的例子就可以正常工作（用单条 GEP）：

@MyVar = external global { i32, [40 x i32 ] }
...
%idx = getelementptr { i32, [40 x i32] }, ptr @MyVar, i64 0, i32 1, i64 17

在这种情况下，结构体 不包含指针（包含的是直接嵌入的数组）。因此，GEP 指令可以穿过全局变量进行索引，进入结构体的第二个字段，并直接定位到那里数组中的第 18 个 i32 元素。

---

核心技术点解析：

这段话揭示了 GEP 最重要的局限性：GEP 不能穿透内存中的指针。

1. 场景 A（指针的指针）：
   • 内存布局：Struct -> Pointer -> Array
   • GEP 只能算到 Pointer 的地址为止。你必须显式插入一条 Load 指令把 Pointer 的值取出来，然后用新的 GEP 基于这个值继续算。
2. 场景 B（结构体内的数组）：
   • 内存布局：Struct -> Array (数组是结构体的一部分，内存连续)
   • GEP 可以一路算到底，因为所有偏移量在编译时（或基于基地址）都是可以通过简单的加法计算出来的，不需要读取内存内容。