『LLVM IR』GEP Instruction & PointerType

时常感觉，“指针”是许多像我一样大一伊始时学计科学得浑浑噩噩的学生欠下的天债，既是债，那么总有要还的一天。令人庆幸的是，大二时接触到的面向对象理论很好地解决了我的相关问题，因此上手 LLVM，又见到这个熟悉的名词时，已不再像以前那样混沌而不知所谓。

这一块了解好后，处理数组、函数传参等等的 IR 就是非常自然的过程。

基本结构

1
2
3

<result> = getelementptr <ty>, ptr <ptrval>{, [inrange] <ty> <idx>}*
<result> = getelementptr inbounds <ty>, ptr <ptrval>{, [inrange] <ty> <idx>}*
<result> = getelementptr <ty>, <N x ptr> <ptrval>, [inrange] <vector index type> <idx>

上面的代码块展示了 GEP 指令的格式，看起来有点迷，不过没关系，往下看就是了。

GEP 指令的作用是获取聚合数据结构（Aggregate Data Structure，比如其实就可以直接理解成数组）子元素的地址。它只进行地址计算，不访问内存，很显然，它应该是一种指针，而事实证明它也确实是指针类型（如果你使用一些方法去打印 GEP 指令的值类型，会发现给出的是 PointerType），GEP 的本质就是一条指针计算语句。该指令也可以用来计算这些地址的向量。

指令参数

GEP 至少有两个参数。第一个参数是要计算的原始指针，往往是一个结构体指针，或者数组首地址指针（我们的实验中一般是后者）；第二个参数及以后的参数都称为 indices，表示要进行计算的参数，比如说结构体的第几个元素，数组的第几个元素，就是索引值。indices 数量不限的好处是显然的，这为我们指示高维数组提供了可能，使得我们能够完成 a->b->c 这类连续指向的运算。

但从前一节的格式示例看好像并没有那么简单？其实标准格式就是多了一些用于指示参数类型的关键字，我个人认为只要按上一段去理解就好了。

如果严格参照格式，一般来说，GEP 指令的第一个参数（即上面写的 <ty>）指示的是计算的基础类型，可以理解为指针的类型；第二个参数则是指针或者指针向量本身，并且一定从基址开始，其余的参数是指示该指针要指向聚合对象的哪个（或哪些）元素的索引值，索引值的数量和解释都取决于索引的具体类型（比如数组的维数等）。通常来说，第一个索引值总是用于索引第二个参数给出的那个指针值，第二个索引第三个，以此类推，而最后一个索引则用于索引所指向的类型的值。索引到的第一个类型必须是指针值，随后的类型可以是数组、向量和结构体，但，一定不能是指针——因为这将需要在继续计算之前加载指针。

参数类型

每个 indices 索引参数的类型取决于它索引到的类型。首先，结构体的计算地址必须是 i32：当索引指向任意一个结构体时（在这里要注意，结构体可以被声明为变量、指针或者数组），只允许它为 i32 整数常量（当使用索引向量时，它们必须都是相同的 i32 整数常量）；而当索引指向数组、指针或向量时，允许索引值为任何宽度的整数，甚至不需要是常量。下面给出一个 LLVM 官网的例子，解释得比较清楚：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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];
}

对于这一段代码，Clang 生成的 LLVM 中间代码是这样的：

1
2
3
4
5
6
7
8

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

define ptr @foo(ptr %s) nounwind uwtable readnone optsize ssp {
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]]’ 类型的数组。最后，GEP 指令返回一个指向该数组索引值为 13 的元素的指针。

顺带一提，数组下标在 GEP 中可以是负数，这是一种数组越界的特殊表示。

结构体成员总是使用 i32 索引这个规定其实是一个历史遗留问题。现在看来，具体的 i32 类型可能已经成为了一个历史文物，但它的宽度足以满足所有实际用途，所以 LLVM 的设计者认为现在没有必要再去更改它。它并不一定意味着 i32 类型的算术地址，它只是一个标识符，用来标识结构体中的一个字段。要求所有的结构体成员索引值类型相同可以减少两个 GEP 指令实际上相同但具有不同操作数类型的可能性，总而言之，就是一项方便的历史遗留的产物。

注意事项

关于 GetElementPtr 指令，有以下几条事例要记住，官网上给出的疑难解答都是从这五条出发的。

1. GEP 指令从不访问内存，它只提供指针计算。
2. GEP 指令的第二个操作数始终是一个指针，它必须被索引。
   1. 这里的“第二个”是按它给的标准格式定义的，其实意思就是要计算的原始指针必须给出
3. GEP 指令没有多余（superfluous）的索引。
   1. 我把“多余”理解成“可有可无” / “删掉也没关系” 的意思
   2. 可以理解为在指示一个形似向量或者结构体数组的结构时，不允许出现缺省值，如果你不需要用到某个元素，要设定其指针偏移值为 0
4. 指令末尾的 0 索引下标对于指针 aliasing是多余的，但对于指针的类型则不是。
   1. Aliasing 是指多于一个的左值指向同一块区域，意思是两个指针指向同一块区域或对象
   2. GEP x, 1, 0, 0 和 GEP x, 1 指向同一块区域，但指针类型不同，因为 0 偏移值不影响指向的地址，但对于指针类型的 GEP 指令本身来说，维度却被改变了，这一点可以结合第 3 条进行食用
      1. 编写 LLVM 需要时刻记住，LLVM 是强类型的，每一条语句，都有确定的类型，GetElementPtr 也正是这样，不同的参数一定会导致不同的返回类型。在正确理解 GetElementPtr 的工作方式时，必须时刻了解对应的类型，这样才不会偏差
      2. 不同的类型有这样的好处：假设一个三维数组 int a[10][10][10]，对它而言，可以用 GEP x, 1, 0, 0 指向 a[1][0][0] 这个数，用 GEP x, 1 则指向 a[1] 这个二维数组
5. 前导 0 索引下标对于指针 aliasing 和指针类型都不是多余的。

参考：

The Often Misunderstood GEP Instruction — LLVM 16.0.0git documentation

LLVM Language Reference Manual — LLVM 16.0.0git documentation