LLVM mem2reg 传递如何工作

Question

mem2reg 是 llvm 中重要的优化过程。我想了解这种优化是如何工作的，但没有找到好的文章、书籍、教程等。

我找到了这两个链接：

• 链接损坏或被劫持
• https://www.zzzconsulting.se/2018/07/16/llvm-exercise.html

两个链接都解释了可以使用 Cytron 的经典 SSA 算法来实现这一过程，但阅读原始论文时我没有看到 alloca 指令如何转换为寄存器。

由于alloca是特定于llvm IR的指令，我想知道将alloca指令转换为寄存器的算法是否是仅适用于llvm的ad-hoc算法。或者如果有一个我还不知道名字的通用理论框架来解释如何将内存变量提升为寄存器变量。

官方文档上说： mem2reg：该文件将内存引用提升为寄存器引用。它提倡仅将加载和存储用作用途的分配指令。通过使用支配边界放置 phi 节点来转换分配，然后以深度优先顺序遍历函数以根据需要重写加载和存储。这只是构建“修剪”SSA 形式的标准 SSA 构建算法。

通过这个描述，似乎只需要检查变量的所有用户是否都是加载和存储指令，如果是，则可以将其提升为寄存器。

因此，如果您能给我链接到文章、书籍、算法等，我将不胜感激。

Answer 1

高效计算静态单赋值形式和控制依赖图，作者：Cytron、Ferrante 等人。

alloca

指令以C中的

alloca()

函数命名，它是malloc()的很少使用的对应函数，它在堆栈而不是堆上分配内存，这样当函数返回时内存就会消失，而无需显式地分配释放了。

论文中，图2展示了“直线代码”的示例：

  V ← 4
    ← V + 5
  V ← 6
    ← V + 7

该文本不是有效的 LLVM IR，如果我们想在 pre-mem2reg LLVM IR 中重写相同的示例，它将如下所示：

  ; V ← 4
  store i32 4, i32* %V.addr
  ;   ← V + 5
  %tmp1 = load i32* %V.addr
  %tmp2 = add i32 %tmp1, 5
  store i32 %tmp2, i32* %V.addr
  ; V ← 6
  store i32 6, i32* %V.addr
  ;   ← V + 7
  %tmp3 = load i32* %V.addr
  %tmp4 = add i32 %tmp3, i32 7
  store i32 %tmp4, i32* %V.addr

在这个示例中很容易看出如何使用存储到加载转发将

%tmp1

替换为

i32 4

，但你不能总是删除最终存储。对

%V.addr

一无所知意味着我们必须假设它可以在其他地方使用。

如果你知道

%V.addr

是一个alloca，你可以简化很多事情。您可以看到 alloca 指令，这样您就知道您可以看到所有用途，您永远不必担心

%ptr

的存储可能会与

%V.addr

别名。您会看到分配情况，因此知道其对齐情况。您知道指针访问不会在函数中的任何地方出错，任何人都可以调用的分配没有

free()

等价物。如果您看到一个存储在函数结束之前未加载，则可以将该存储作为死存储消除，因为您知道分配器的生命周期在函数返回时结束。最后，如果您删除了分配器的所有用途，则可以删除分配器本身。

因此，如果您从一个唯一用户是加载和存储的分配器开始，那么该问题与大多数内存优化问题没有什么共同之处：不存在指针别名的可能性，也不担心内存访问错误。您需要做的是将 phi 函数（LLVM 中的

phi

指令）放置在给定控制流图的正确位置，这就是本文描述的操作方法。