LLVM IR alloca指令

Question

我想为我的玩具编译器设计一个IR(如LLVM IR),我不知道该alloca指令在进一步分析中的目的是什么.在哪些优化alloca信息中使用？

Answer 1

长话短说

\n

该指令的目的是更容易地为具有可变变量的alloca命令式语言生成代码。如果没有它，您将需要以SSA 形式构建所有作业。对于可变变量，这可能会变得相当复杂。

\n\n

例子

\n

让我们看一下这个简单的 C 程序（取自LLVM 文档）并重点关注变量 X 及其赋值。正如您所注意到的，它的最终值（我们返回的值）取决于程序中采用的 if 分支。

\n

int G, H;\nint test(_Bool Condition) {\n  int X;\n  if (Condition)\n    X = G;\n  else\n    X = H;\n  return X;\n}\n

\n

将示例程序转换为 LLVM IR，无需alloca

\n

现在，如果我们将此程序转换为 LLVM IR，我们会得到如下内容：

\n

@G = weak global i32 0   ; type of @G is i32*\n@H = weak global i32 0   ; type of @H is i32*\n\ndefine i32 @test(i1 %Condition) {\nentry:\n  br i1 %Condition, label %cond_true, label %cond_false\n\ncond_true:\n  %X.0 = load i32* @G\n  br label %cond_next\n\ncond_false:\n  %X.1 = load i32* @H\n  br label %cond_next\n\ncond_next:\n  %X.2 = phi i32 [ %X.1, %cond_false ], [ %X.0, %cond_true ]\n  ret i32 %X.2\n}\n

\n

因为在返回指令之前 X 有两个不同的可能值，所以我们必须插入一个Phi 节点来合并这两个值。这是为什么？嗯，因为 LLVM 要求所有赋值都采用 SSA 形式，并且 Phi 节点是合并两个值的唯一方法。然而，这种使用 Phi 节点的 SSA 构建需要非常重要的算法，并且为每个编译器重新实现不方便且浪费。

\n

那么，您可能想知道我们如何解决这个问题？正如您可能已经猜到的那样，答案是alloca！

\n

将示例程序转换为 LLVM IRalloca

\n

这里的 \xe2\x80\x98trick\xe2\x80\x99 是，虽然 LLVM 确实要求所有寄存器值都采用 SSA 形式，但它不要求（或允许）内存对象采用 SSA 形式。考虑到这一点，高级思想是我们希望为函数中的每个可变对象创建一个堆栈变量（位于内存中）。使用它，我们的代码现在变成：

\n

@G = weak global i32 0   ; type of @G is i32*\n@H = weak global i32 0   ; type of @H is i32*\n\ndefine i32 @test(i1 %Condition) {\nentry:\n  %X = alloca i32           ; type of %X is i32*.\n  br i1 %Condition, label %cond_true, label %cond_false\n\ncond_true:\n  %X.0 = load i32* @G\n  store i32 %X.0, i32* %X   ; Update X\n  br label %cond_next\n\ncond_false:\n  %X.1 = load i32* @H\n  store i32 %X.1, i32* %X   ; Update X\n  br label %cond_next\n\ncond_next:\n  %X.2 = load i32* %X       ; Read X\n  ret i32 %X.2\n}\n

\n

由此，我们发现了一种处理任意可变变量的方法，而根本不需要创建 Phi 节点！

\n\n

进一步（对于好奇的人）：

\n

虽然这个解决方案解决了我们眼前的问题，但它引入了另一个问题：我们现在显然为非常简单和常见的操作引入了大量堆栈流量，这是一个主要的性能问题。对我们来说幸运的是，LLVM 优化器有一个名为 \xe2\x80\x9cmem2reg\xe2\x80\x9d 的高度调整的优化过程，可以处理这种情况，将这样的分配提升到 SSA 寄存器中，并根据需要插入 Phi 节点。

\n

Answer 2

“ alloca”指令在当前执行函数的堆栈帧上分配内存，当该函数返回其调用者时将自动释放该内存。始终在地址空间中为数据布局中指示的分配资源分配对象。

“ alloca”指令通常用于表示必须具有可用地址的自动变量。

您可以在这里找到更多

llvm IR书中的一些注释：

整个LLVM文件的内容（汇编或位代码）都可以用来定义LLVM模块。该模块是LLVM IR顶层数据结构。每个模块包含一系列功能，其中包含一系列基本模块，这些基本模块包含一系列指令。该模块还包含支持该模型的外围实体，例如全局变量，目标数据布局和外部函数原型以及数据结构声明。

所以alloca指令（在我的基础上）只是为了支持IR。

例如下面的代码：

int sum(int a, int b) {
  return a+b;
}

在IR中将如下所示：

; Function Attrs: noinline nounwind uwtable
define i32 @sum(int, int)(i32, i32) #0 !dbg !6 {
  %3 = alloca i32, align 4
  %4 = alloca i32, align 4
  store i32 %0, i32* %3, align 4
  call void @llvm.dbg.declare(metadata i32* %3, metadata !10, metadata !11), !dbg !12
  store i32 %1, i32* %4, align 4
  call void @llvm.dbg.declare(metadata i32* %4, metadata !13, metadata !11), !dbg !14
  %5 = load i32, i32* %3, align 4, !dbg !15
  %6 = load i32, i32* %4, align 4, !dbg !16
  %7 = add nsw i32 %5, %6, !dbg !17
  ret i32 %7, !dbg !18
}

alloca指令在当前函数的堆栈帧上保留空间。空间量取决于元素类型的大小，并且遵循指定的对齐方式。第一条指令％a.addr = alloca i32，对齐4，分配一个4字节的堆栈元素，该元素遵守4字节的对齐方式。指向堆栈元素的指针存储在本地标识符％a.addr中。alloca指令通常用于表示局部（自动）变量。