常被误解的 GEP 指令¶

简介 ¶

本文档旨在消除围绕 LLVM 的GetElementPtr (GEP) 指令的神秘和困惑。一旦开发人员开始使用 LLVM 进行编码，关于狡猾的 GEP 指令的问题可能是最常见的问题。在这里，我们列出了困惑的来源，并表明 GEP 指令实际上非常简单。

地址计算 ¶

当人们第一次遇到 GEP 指令时，他们倾向于将其与其他编程范式中的已知概念联系起来，最著名的是 C 数组索引和字段选择。GEP 非常类似于 C 数组索引和字段选择，但是它有一些不同，这导致了以下问题。

GEP 指令的第一个索引是什么？¶

快速回答：遍历第二个操作数的索引。

第一个索引的困惑通常源于将 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 指令中的每一个的第二个操作数。第三个操作数遍历该指针。第四个操作数将是struct munger_struct类型的字段偏移量，用于f1或f2字段。因此，在 LLVM 汇编中，munge 函数如下所示

define void @munge(ptr %P) {
entry:
  %tmp = getelementptr %struct.munger_struct, ptr %P, i32 1, i32 0
  %tmp1 = load i32, ptr %tmp
  %tmp2 = getelementptr %struct.munger_struct, ptr %P, i32 2, i32 1
  %tmp3 = load i32, ptr %tmp2
  %tmp4 = add i32 %tmp3, %tmp1
  %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 指令产生的指针进行的任何加载或存储都会触发未定义行为 (UB)。

为什么需要额外的 0 索引？¶

快速回答：没有多余的索引。

当 GEP 指令应用于始终为指针类型的全局变量时，这个问题最常出现。例如，考虑以下情况

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

上面的 GEP 通过索引结构%MyStruct的i32类型字段来生成一个ptr。当人们第一次看到它时，他们想知道为什么需要i64 0索引。但是，仔细检查全局变量和 GEP 的工作原理就会揭示其必要性。了解以下事实将消除困惑

%MyStruct的类型不是{ ptr, i32 }，而是ptr。也就是说，%MyStruct是一个指针（指向一个结构），而不是结构本身。
第 1 点可以通过注意到 GEP 指令的第二个操作数（%MyStruct）的类型是ptr来证明。
第一个索引i64 0需要遍历全局变量%MyStruct。由于 GEP 指令的第二个参数必须始终是指针类型的值，因此第一个索引遍历该指针。值为 0 表示该指针偏移 0 个元素。
第二个索引i32 1选择结构的第二个字段（i32）。

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 将首先计算内部指针的地址，然后加载指针，然后计算第 18 个数组元素的地址。

这不能用单个 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 x,0,0,1 和 GEP x,1 不别名？¶

快速回答：它们计算不同的地址位置。

如果您查看这些 GEP 指令中的第一个索引，您会发现它们是不同的（0 和 1），因此地址计算在此索引处发生分歧。考虑以下示例

@MyVar = external global { [10 x i32] }
%idx1 = getelementptr { [10 x i32] }, ptr @MyVar, i64 0, i32 0, i64 1
%idx2 = getelementptr { [10 x i32] }, ptr @MyVar, i64 1

在此示例中，idx1计算@MyVar中结构内的数组中的第二个整数的地址，即MyVar+4。但是，idx2计算@MyVar之后下一个结构的地址，即MyVar+40，因为它索引超过了MyVar中的十个 4 字节整数。显然，在这种情况下，指针不会别名。

为什么 GEP x,1,0,0 和 GEP x,1 别名？¶

快速回答：它们计算相同的地址位置。

这两个 GEP 指令将计算相同的地址，因为遍历第 0 个元素不会更改地址。考虑以下示例

@MyVar = global { [10 x i32] }
%idx1 = getelementptr { [10 x i32] }, ptr @MyVar, i64 1, i32 0, i64 0
%idx2 = getelementptr { [10 x i32] }, ptr @MyVar, i64 1

在这个例子中，%idx1 的值为 MyVar+40，%idx2 的值也为 MyVar+40。

GEP 能否索引向量元素？¶

虽然这并没有一直被强制禁止，但并不推荐这样做。它会导致优化器出现尴尬的特殊情况，以及 IR 的根本不一致性。将来，它可能会被完全禁止。

地址空间对 GEP 有什么影响？¶

没有，除了第二个操作数指针类型的地址空间限定符始终与结果类型的地址空间限定符匹配。

GEP 与 `ptrtoint`、算术运算和 `inttoptr` 有什么区别？¶

它们非常相似；只有细微的差别。

使用 ptrtoint 时，您必须选择一个整数类型。一种方法是选择 i64；这在 LLVM 支持的所有内容上都是安全的（LLVM 在许多地方内部假设指针从不比 64 位宽），并且优化器实际上会将 i64 算术运算缩小到不支持 64 位算术的目标上的实际指针大小在大多数情况下。但是，在某些情况下它不会这样做。使用 GEP，您可以避免此问题。

此外，GEP 带有额外的指针别名规则。从一个对象获取 GEP，寻址到另一个单独分配的对象，并取消引用它是非法的。IR 生成器（前端）必须遵循此规则，并且使用者（优化器，特别是别名分析）可以从中受益，因为它们可以依赖它。有关更多信息，请参见规则部分。

并且，GEP 在常见情况下更简洁。

但是，对于所隐含的底层整数计算，没有区别。

我正在为一个需要 GEP 自定义降低的目标编写后端。我该如何操作？¶

您不需要这样做。GEP 隐含的整数计算与目标无关。通常，您需要做的是使您的后端模式匹配涉及 ADD、MUL 等的表达式树，这些表达式树是 GEP 降低到的内容。这样做的好处是让您的代码在更多情况下都能正常工作。

GEP 确实使用与数据类型的大小和布局相关的目标相关参数，目标可以自定义这些参数。

如果您需要支持非 8 位的寻址单元，则需要修复后端中的大量代码，其中 GEP 降低只是整体情况的一小部分。

VLA 寻址如何与 GEP 协同工作？¶

GEP 本身不支持 VLA。LLVM 的类型系统完全是静态的，并且 GEP 地址计算由 LLVM 类型指导。

VLA 索引可以实现为线性化索引。例如，类似于 X[a][b][c] 的表达式必须有效地降低为类似于 X[a*m+b*n+c] 的形式，以便它对 GEP 而言成为一个一维数组引用。

这意味着如果您想编写一个理解数组索引并希望支持 VLA 的分析，您的代码必须准备好反向工程线性化。解决此问题的一种方法是使用 ScalarEvolution 库，该库始终以相同的方式呈现 VLA 和非 VLA 索引。

规则 ¶

如果数组索引超出范围会发生什么？¶

数组索引超出范围有两种含义。

首先，有来自 GEP 的第一个操作数的（静态）类型的数组类型。大于对应静态数组类型中元素数量的索引是有效的。从这个意义上说，索引超出范围没有问题。索引到数组中仅取决于数组元素的大小，而不取决于元素的数量。

这如何使用的一个常见示例是大小未知的数组。通常使用长度为零的数组类型来表示这些。静态类型说有零个元素的事实无关紧要；计算任意元素索引是完全有效的，因为计算仅取决于数组元素的大小，而不取决于元素的数量。请注意，零大小的数组在这里不是一个特例。

这种意义与 inbounds 关键字无关。inbounds 关键字旨在描述低级指针算术溢出条件，而不是高级数组索引规则。

希望了解数组索引的分析传递不应假设静态数组类型边界得到遵守。

超出范围的第二种含义是计算超出实际底层分配对象的地址。

使用 inbounds 关键字，如果地址在实际底层分配对象之外且不是最后一个元素之后的地址，则 GEP 的结果值为 poison。

如果没有 inbounds 关键字，则对计算超出范围的地址没有限制。显然，执行加载或存储需要分配且对齐良好的内存地址。但是 GEP 本身只关心计算地址。

我可以比较使用 GEP 计算的两个值吗？¶

可以。如果两个地址都在同一个分配的对象内或最后一个元素之后，您将获得预期的比较结果。如果任何一个在它之外，则可能会发生整数算术环绕，因此比较可能没有意义。

我可以使用与底层对象类型不同的指针类型执行 GEP 吗？¶

可以。对将指针值位转换为任意指针类型没有限制。GEP 中的类型仅用于定义底层整数计算的参数。它们不需要与底层对象的实际类型相对应。

此外，加载和存储不需要使用与底层对象类型相同的类型。在这种情况下，类型仅用于指定内存大小和对齐方式。除此之外，它们仅仅是对优化器的提示，指示该值可能如何使用。

我可以将对象的地址转换为整数并将其添加到空指针吗？¶

您可以通过这种方式计算地址，但是如果您使用 GEP 进行加法，则无法使用该指针实际访问该对象，除非该对象在 LLVM 外部管理。

底层整数计算已充分定义；空指针具有定义的值——零——您可以向其添加任何您想要的值。

但是，使用此类指针访问（从其加载或存储到）LLVM 感知的对象是非法的。这包括 GlobalVariables、Allocas 和由 noalias 指针指向的对象。

如果您确实需要此功能，可以使用显式整数指令进行算术运算，并使用 inttoptr 将结果转换为地址。GEP 的大多数特殊别名规则不适用于从 ptrtoint、算术运算和 inttoptr 序列计算的指针。

我可以计算两个对象之间的距离，并将该值添加到一个地址以计算另一个地址吗？¶

与对空指针进行算术运算一样，您可以使用 GEP 以这种方式计算地址，但是如果您这样做，则无法使用该指针实际访问该对象，除非该对象在 LLVM 外部管理。

同样如上所述，ptrtoint 和 inttoptr 提供了一种替代方法来执行此操作，并且没有此限制。

我可以在 LLVM IR 上执行基于类型的别名分析吗？¶

您不能使用 LLVM 的内置类型系统执行基于类型的别名分析，因为 LLVM 对在寻址、加载或存储中混合类型没有限制。

LLVM 的基于类型的别名分析传递使用元数据来描述不同的类型系统（例如 C 类型系统），并在其之上执行基于类型的别名分析。更多详细信息请参见语言参考。

如果 GEP 计算溢出会发生什么？¶

如果 GEP 缺少 inbounds 关键字，则该值是评估隐含的二进制补码整数计算的结果。但是，由于无法保证对象将在地址空间中的哪个位置分配，因此此类值含义有限。

如果 GEP 具有 inbounds 关键字，则如果 GEP 溢出（即环绕地址空间的末尾），则结果值为 poison。

因此，这对 inbounds GEP 有一些影响：数组/向量/指针索引隐含的比例始终已知为“nsw”，因为它们是有符号值，并按元素大小缩放。这些值也允许为负数（例如“gep i32, ptr %P, i32 -1”），但指针本身在逻辑上被视为无符号值。这意味着 GEP 在指针基数（被视为无符号）与其应用于它的偏移量（被视为有符号）之间具有不对称的关系。偏移量计算内的加法结果不能出现有符号溢出，但当应用于基数指针时，可能会出现有符号溢出。

我如何判断我的前端是否遵循规则？¶

目前没有用于 getelementptr 规则的检查器。目前，执行此操作的唯一方法是手动检查前端中创建 GetElementPtr 运算符的每个位置。

不可能编写一个能够静态查找所有规则违规的检查器。可以编写一个通过用动态检查对代码进行检测来工作的检查器。或者，可以编写一个静态检查器来捕获一部分可能的问题。但是，目前还没有这样的检查器。

基本原理 ¶

为什么 GEP 的设计是这样的？¶

GEP 的设计具有以下目标，大致按照非正式的优先级顺序排列

支持 C、类 C 语言以及可以概念上降低到 C 的语言（这涵盖了很多）。
支持 C 编译器中常见的优化。特别是，GEP 是 LLVM 的指针别名模型的基石。
提供一种一致的计算地址的方法，以便地址计算不需要成为 IR 中加载和存储指令的一部分。
支持非类 C 语言，在不影响其他目标的情况下。
最大程度地减少 IR 中的目标特定信息。

为什么结构体成员索引总是使用 `i32`？¶

具体的类型 i32 可能只是一个历史遗留问题，但是它对于所有实际目的来说都足够宽，因此没有必要更改它。它并不一定意味着 i32 地址运算；它只是一个标识符，用于识别结构体中的一个字段。要求所有结构体索引都相同，可以减少两种 GEP 实际上相同但具有不同操作数类型的情况下的可能性。

什么是 uglygep？¶

一些 LLVM 优化器通过将 GEP 内部降低为更原始的整数表达式来对其进行操作，这使得它们可以与其他整数表达式组合和/或拆分为多个独立的整数表达式。如果它们进行了非平凡的更改，则转换回 LLVM IR 可能需要对寻址的结构进行逆向工程，以使其适合原始第一个操作数的静态类型。并非总是可以完全重建这种结构；有时底层寻址根本不对应于静态类型。在这种情况下，优化器将发出一个 GEP，其基指针转换为一个简单的地址单元指针，并使用名称“uglygep”。这并不美观，但它同样有效，并且足以保持 GEP 提供的指针别名保证。

总结 ¶

总之，以下是一些关于 GetElementPtr 指令始终需要记住的事情

GEP 指令永远不会访问内存，它只提供指针计算。
GEP 指令的第二个操作数始终是指针，并且必须对其进行索引。
GEP 指令没有多余的索引。
尾随零索引对于指针别名是多余的，但对于指针的类型不是多余的。
前导零索引对于指针别名和指针的类型都不是多余的。

文档

参与进来

其他链接

此页面