The Often Misunderstood GEP Instruction

发布于 2019-10-03  3 次阅读


LLVM 原文
http://llvm.org/docs/GetElementPtr.html

翻译参考
https://blog.csdn.net/dongjideyu/article/details/88311222

介绍

本文旨在消除围绕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;
}
...
munger_struct Array[3];
...
munge(Array);

在这个“C”示例中,前端编译器(Clang)将通过赋值语句中的“P”为三个索引生成三个GEP指令。 函数参数P将是这些GEP指令中的每一个的第二个操作数。 第三个操作数通过该指针索引。 对于 f1 或 f2 字段,第四个操作数将是struct munger_struct类型的字段偏移量。 因此,在LLVM程序集中,munge函数如下所示:

void %munge(%struct.munger_struct* %P) {
entry:
  %tmp = getelementptr %struct.munger_struct, %struct.munger_struct* %P, i32 1, i32 0
  %tmp = load i32* %tmp
  %tmp6 = getelementptr %struct.munger_struct, %struct.munger_struct* %P, i32 2, i32 1
  %tmp7 = load i32* %tmp6
  %tmp8 = add i32 %tmp7, %tmp
  %tmp9 = getelementptr %struct.munger_struct, %struct.munger_struct* %P, i32 0, i32 0
  store i32 %tmp8, i32* %tmp9
  ret void
}

在每种情况下,第二个操作数是GEP指令开始的指针。 无论第二个操作数是参数,分配的内存还是全局变量,都是如此。 为了清楚说明,让我们考虑一个更为愚钝的例子:

%MyVar = uninitialized global i32
...
%idx1 = getelementptr i32, i32* %MyVar, i64 0
%idx2 = getelementptr i32, i32* %MyVar, i64 1
%idx3 = getelementptr i32, i32* %MyVar, i64 2

这些GEP指令只是从MyVar的基地址进行地址计算。它们计算如下(使用C语法):

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

由于已知类型i32是四个字节长,因此索引0, 1 和 2 分别转换为 0 , 4 和 8 的存储器偏移。 由于%MyVar的地址直接传递给GEP指令,因此没有访问内存来进行这些计算。此示例的迟钝的部分是%idx2和%idx3。 它们导致计算指向内存超过%MyVar全局结尾的地址,这只是一个i32长,而不是三个i32长。 虽然这在LLVM中是合法的,但是它是不可取的,因为具有由这些GEP指令产生的指针的任何加载或存储将产生未定义的结果。

为什么需要额外的0索引?

快速回答:没有多余的索引。 当GEP指令应用于始终为指针类型的全局变量时,最常出现此问题。例如,考虑一下:

%MyStruct = uninitialized global { float*, i32 }
...
%idx = getelementptr { float*, i32 }, { float*, i32 }* %MyStruct, i64 0, i32 1

上面的GEP通过索引结构 %MyStruct 的 i32 类型字段来产生 i32 *。 当人们第一次看到它时,他们想知道为什么需要 i64 0索引。 然而,仔细检查全局和GEP的工作方式可以发现是需要的。 了解以下事实将消除这种困惑:

  1. %MyStruct的类型不是 {float *,i32},而是 {float *,i32} *。 也就是说,%MyStruct 是一个指向结构的指针,该结构包含指向 float 和 i32 的指针。
  2. 通过注意GEP指令的第二个操作数的类型(%MyStruct)来证明点#1是 {float *,i32} * 。
  3. 第一个索引 i64 0 需要跨越全局变量 %MyStruct。 由于GEP指令的第二个参数必须始终是指针类型的值,因此第一个索引会逐步执行该指针。 值 0 表示从该指针偏移 0 个元素。
  4. 第二个索引 i32 1 选择结构的第二个字段(i32)。

GEP取消引用了什么?

快速回答:没什么。 GetElementPtr指令不引用任何内容。 也就是说,它不会以任何方式访问内存。 这就是加载和存储指令的用途。 GEP仅涉及地址的计算。 例如,考虑一下:

%MyVar = uninitialized global { [40 x i32 ]* }
...
%idx = getelementptr { [40 x i32]* }, { [40 x i32]* }* %MyVar, i64 0, i32 0, i64 0, i64 17

在这个例子中,我们有一个全局变量 %MyVar,它是一个指向结构的指针,该结构包含一个指向 40 个 int 的数组的指针。 GEP指令似乎正在访问结构的整数数组的第18个整数。 但是,这实际上是非法的GEP指令。 它不会编译。 原因是必须取消引用结构中的指针才能索引到40个整数的数组。 由于GEP指令永远不会访问内存,因此它是非法的。 要访问数组中的第18个整数,您需要执行以下操作:

%idx = getelementptr { [40 x i32]* }, { [40 x i32]* }* %, i64 0, i32 0
%arr = load [40 x i32]** %idx
%idx = getelementptr [40 x i32], [40 x i32]* %arr, i64 0, i64 17

在这种情况下,我们必须先使用加载指令在结构中加载指针,然后才能索引数组。如果示例更改为:

%MyVar = uninitialized global { [40 x i32 ] }
...
%idx = getelementptr { [40 x i32] }, { [40 x i32] }*, i64 0, i32 0, i64 17

一切正常。在这种情况下,结构不包含指针,GEP指令可以通过全局变量索引到结构的第一个字段并访问数组中的第18个i32。

为什么不用 GEP x, 0, 0, 1 和 GEP x, 1 个别名?

快速回答:他们计算不同的地址位置。 如果查看这些GEP指令中的第一个索引,您会发现它们不同( 0 和 1 ),因此地址计算与该索引不同。考虑这个例子:

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

在此示例中,idx1 计算 %MyVar 结构中数组中第二个整数的地址,即 MyVar + 4。 idx1 的类型是 i32 *。 但是,idx2 计算 %MyVar之后的下一个结构的地址。 idx2 的类型是 { [10 x i32] } *,它的值等于 MyVar + 40,因为它索引超过 MyVar中的10个4字节整数。 显然,在这种情况下,指针不会别名。

为什么 GEP x, 1, 0, 0 和 GEP x, 1个别名

快速回答:他们计算相同的地址位置。 这两个GEP指令将计算相同的地址,因为通过第0个元素的索引不会改变地址。但是,它确实改变了类型。考虑这个例子:

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

在此示例中,%idx1 的值为 %MyVar + 40,其类型为 i32 *%idx2 的值也是 MyVar + 40,但其类型为 { [10 x i32] } *

GEP可以将索引转换为向量元素吗?

虽然不建议这样做,但并不总是被强制禁止。
它导致优化器中的特殊情况的尴尬,并且IR中的基本不一致。在未来,它可能会被完全禁止。

GEP与ptrtoint,arithmetic和inttoptr有何不同?

它非常相似; 只有微妙的差异。
使用ptrtoint,您必须选择整数类型。 一种方法是选择 i64; 这对LLVM支持的一切都是安全的(LLVM内部假设指针在许多地方从不宽于64位),优化器实际上将 i64 算法缩小到不支持64位算术的目标上的实际指针大小。 大多数情况下。 但是,在某些情况下,它不会这样做。 使用GEP可以避免此问题。 此外,GEP还带有额外的指针别名规则。 从一个对象获取GEP,将地址转换为另一个单独分配的对象并取消引用它是无效的。 IR生产者(front-ends前端)必须遵循这一规则,消费者(优化者,特别是别名分析)可以从中依赖它。 有关详细信息,请参阅规则部分。 并且,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的结果值是未定义的。
       如果没有inbounds关键字,则对计算越界地址没有限制。 显然,执行加载或存储需要分配和充分对齐的存储器的地址。 但GEP本身只关心计算地址。

数组索引可以为负数吗?

是的。这基本上是数组索引超出范围的特殊情况。

我可以比较用GEP计算的两个值吗?

是的。如果两个地址都在同一个分配的对象中,或者一个接一个地,那么您将获得预期的比较结果。如果其中任何一个在其外部,则可能发生整数算术包装,因此比较可能没有意义。

我可以使用与基础对象类型不同的指针类型来执行GEP吗?

是的。 将指针值连接到任意指针类型没有限制。 GEP中的类型仅用于定义基础整数计算的参数。 它们不需要与底层对象的实际类型相对应。

此外,加载和存储不必使用与基础对象的类型相同的类型。 此上下文中的类型仅用于指定内存大小和对齐方式。 除此之外,优化器只有一个提示,指示如何使用该值。

我可以将对象的地址转换为整数并将其添加到null吗?

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

底层整数计算已充分定义; null 有一个定义的值 - 零 - 你可以添加你想要的任何值。

但是,使用这样的指针访问(load from 或store to)具有LLVM感知的对象是无效的。这包括GlobalVariables,Allocas和noalias指针指向的对象。

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

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

与null上的算术一样,您可以使用GEP以这种方式计算地址,但是如果您这样做,则不能使用该指针实际访问该对象,除非该对象在LLVM之外进行管理。

同样如上所述,ptrtoint和inttoptr提供了另一种没有此限制的方法。

我可以在LLVM IR上进行基于类型的别名分析吗?

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

LLVM基于类型的别名分析过程使用元数据来描述不同类型的系统(例如C类型系统),并在此基础上执行基于类型的别名。进一步的细节在语言参考

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

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

如果GEP具有 inbounds 关键字,则如果 GEP 溢出(即在包裹地址空间的末尾),则结果值是未定义的(“陷阱值”)。

因此,对于入口GEP存在一些这样的分支:由数组 / 向量 / 指针索引 隐含的比例总是已知为“nsw”,因为它们是由元素大小缩放的有符号值。 这些值也允许为负(例如“gep i32 *%P,i32 -1”),但指针本身在逻辑上被视为无符号值。 这意味着GEP在指针基(被视为无符号)和应用于它的偏移(被视为有符号)之间具有不对称关系。 偏移计算中的加法结果不能有符号溢出,但是当应用于基指针时,可能存在有符号溢出。

如何判断我的前端是否遵守规则?

目前没有getelementptr规则的检查器。 目前,唯一的方法是手动检查前端中创建GetElementPtr运算符的每个位置。 编写一个可以静态查找所有规则违规的检查程序是不可能的。 通过动态检查来编写代码,可以编写一个检查器。 或者,可以编写一个静态检查器来捕获可能出现问题的子集。 但是,今天不存在这样的检查器。

解释

为什么GEP以这种方式设计?

GEP的设计具有以下目标,粗略的非正式优先顺序:

  • 支持C,C类语言和可以在概念上降低到C语言的语言(这涵盖了很多)。
  • 支持优化,例如C编译器中常见的优化。特别是,GEP是LLVM指针别名模型的基石。
  • 提供一致的计算地址的方法,以便地址计算不需要成为IR中加载和存储指令的一部分。
  • 支持非C语言,只要它不干扰其他目标。
  • 最大限度地减少IR中的特定目标信息。

为什么struct成员索引总是使用i32?

特定类型 i32 可能只是一个历史文物,但是它足够宽,可用于所有实际目的,因此无需更改它。 它不一定意味着i32地址算术; 它只是一个标识结构中字段的标识符。 要求所有结构索引相同会减少两个GEP实际上相同但具有不同操作数类型的情况的可能性范围。

什么是丑陋的?

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

总结:

总之,这里有一些关于GetElementPtr指令的常识:

  1. GEP指令从不访问内存,它只提供指针计算。
  2. GEP指令的第二个操作数始终是指针,必须将其编入索引。
  3. GEP指令没有多余的索引。
  4. 尾随零索引对于指针别名是多余的,但对于指针的类型则不是。
  5. 对于指针别名和指针的类型,前导零索引不是多余的。