LLVM 项目博客

LLVM 项目新闻和来自战壕的细节

关于 PHI 转换的冗余加载消除高级主题

在我们的 关于 GVN 的上一篇文章 中，我们介绍了加载消除的一些基础知识。 这篇文章介绍了一些高级主题，并重点介绍了 PHI 转换：什么是 PHI 转换，为什么它很重要，展示它可以做的一些很棒的事情，并描述了在 LLVM 中的实现。

什么是 PHI 转换？

在对 SSA 形式执行冗余消除时， 当我们在 CFG 中行走并且正在分析的值在我们正在行走到的块中定义了操作数时，需要进行 PHI 转换。 在加载消除的情况下，正在分析的值的操作数是我们从中加载的指针。这意味着当我们加载的指针在块中定义时，就会发生 PHI 转换。例如，考虑这段 C 代码

if (...) {
    *A = 5;
    P = A;
  } else {
    *B = 9;
    P = B;
  }
  use(*P);

这段代码编译成如下所示的 LLVM IR

BB1:
  store i32 5, i32* %A
  br label %Merge

BB2:
  store i32 9, i32* %B
  br label %Merge

Merge:
  %P = phi i32* [%A, %BB1], [%B, %BB2]
  %Y = load i32 *%P
  ...
  ... use %Y ...

在这个例子中，GVN 开始查看 %Y 加载以查看是否可以消除它。 它向后扫描到块的顶部，寻找提供 %P 处内存地址值的其它内容。 与上一篇文章中的例子不同，这里我们实际上找到了 %P 的定义：我们该怎么办呢？

在 LLVM 2.6 及之前的版本中，内存依赖分析会直接放弃，并表现得好像内存已被覆盖，从而阻止进一步分析加载（在这种情况下最终会消除）。 在 LLVM 2.7 中的新增功能中，GVN 能够将 %P 转换为每个前驱。 在这种情况下，它会看到 %P 在 %BB1 中具有 %A 的值（然后会看到 %A 在那里可用），并且 %P 在 %BB2 中具有 %B 的值（在那里它也可用）。这允许 GVN 将此示例优化为

BB1:
  store i32 5, i32* %A
  br label %Merge

BB2:
  store i32 9, i32* %B
  br label %Merge

Merge:
  %Y = phi i32 [5, %BB1], [9, %BB2]
  %P = phi i32* [%A, %BB1], [%B, %BB2]
  ...
  ... use %Y ...

这消除了加载。这篇文章介绍了如何做到这一点，以及实现这一点的细微差别，以及这让我们能够优化什么。

为什么 PHI 转换对于正确性是必需的？

当我深入研究这个问题时，我并没有意识到，PHI 转换实际上对于正确性是必需的。 这就是为什么内存依赖分析在找到指针的定义时必须停止扫描的原因。 发生这种情况的案例比较微妙，通常涉及部分冗余消除。 例如，考虑以下循环

Loop:
  %P = phi i32* [%A, %Entry], [%B, %Loop]
  %X = load i32* %P
  ...
  store i32 5, i32* %B
  store i32 4, i32* %P
  br i1 %cond, label %Loop, label %Out

考虑如果 PHI 转换在 CFG 中向上扫描时继续扫描 %P 的前驱会发生什么：它会从 %X 加载向上扫描到循环块的顶部。如果没有正确进行 PHI 转换，它会继续扫描入口块中的 %P（在此示例中我们忽略它），然后扫描循环块中的 %P（它是它自己的前驱）。

在循环块中扫描 %P 会找到对 %P 的存储 4，因此我们将认为 4 是循环边缘上的一个活动输入值。但是，这是不正确的，会导致错误的编译：在该后边上的实际活动值为 5，这是由前面的存储提供的。

这个简单的例子旨在说明 PHI 转换不是一种优化：它是正确性所必需的，并且 PHI 转换的最简单形式是在你看到地址的定义时放弃。但是，LLVM 最近变得足够聪明，可以比这或者上面的简单指针情况做得更好。

更有趣的案例

考虑这个测试用例

struct S { int X, Y; };

int foo(struct S *P1, struct S *P2, int C) {
  struct S *P;
  if (C) {
    P1->X = 4;
    P1->Y = 2;
    P = P1;
  } else {
    P2->X = 24;
    P2->Y = 2;
    P = P2;
  }
  return P->X + P->Y;
}

这段代码编译成如下所示的 IR（使用 "clang t.c -S -o - -emit-llvm | opt -mem2reg -S":

if.then:
  %tmp2 = getelementptr inbounds %struct.S* %P1, i32 0, i32 0
  store i32 4, i32* %tmp2
  %tmp4 = getelementptr inbounds %struct.S* %P1, i32 0, i32 1
  store i32 2, i32* %tmp4
  br label %if.end

if.else: 
  %tmp7 = getelementptr inbounds %struct.S* %P2, i32 0, i32 0
  store i32 24, i32* %tmp7
  %tmp9 = getelementptr inbounds %struct.S* %P2, i32 0, i32 1 
  store i32 2, i32* %tmp9
  br label %if.end

if.end: 
  %P = phi %struct.S* [ %P1, %if.then ], [ %P2, %if.else ] 
  %tmp12 = getelementptr inbounds %struct.S* %P, i32 0, i32 0 
  %tmp13 = load i32* %tmp12 
  %tmp15 = getelementptr inbounds %struct.S* %P, i32 0, i32 1 
  %tmp16 = load i32* %tmp15 
  %add = add nsw i32 %tmp13, %tmp16 
  ret i32 %add
}

在这种情况下，GVN 试图消除 %tmp13 和 %tmp14 加载。 考虑 %tmp13 加载：它向后扫描从加载到顶部，寻找 %tmp12 的可用值。 它立即找到了指针的定义（%tmp12），因此它需要 PHI 转换指针或放弃。 在尚未详细介绍如何做到这一点的情况下，以下是发生的直觉

在这种情况下，指针不是一个 PHI 节点，但它使用一个 PHI 节点作为操作数。 因此，GVN 需要将整个符号表达式 "gep P, 0, 0" 转换为前驱。 它会这样做，形成符号表达式 "gep P1, 0, 0"，并且会发现 PHI 转换的地址在 %if.then 块中作为 %tmp2 可用。 然后它将 "gep P, 0, 0" 表达式转换为 %if.else，形成 "gep P2, 0, 0" 符号表达式，并发现它在 %if.else 中作为 %tmp7 可用。 它会扫描这些块以查找指针，并发现这些值实际上是可用的。 由于它们都可用，它可以使用插入构造 SSA 形式来消除加载。

这使得它能够看到两个加载实际上都在前驱中可用。 以下是在 GVN 之后生成的代码（使用 "clang t.c -S -o - -emit-llvm | opt -mem2reg -S -gvn -die):

if.then:
  %tmp2 = getelementptr inbounds %struct.S* %P1, i32 0, i32 0
  store i32 4, i32* %tmp2
  %tmp4 = getelementptr inbounds %struct.S* %P1, i32 0, i32 1
  store i32 2, i32* %tmp4
  br label %if.end

if.else:
  %tmp7 = getelementptr inbounds %struct.S* %P2, i32 0, i32 0
  store i32 24, i32* %tmp7
  %tmp9 = getelementptr inbounds %struct.S* %P2, i32 0, i32 1
  store i32 2, i32* %tmp9
  br label %if.end

if.end:
  %tmp13 = phi i32 [ 1, %if.then ], [ 2, %if.else ]
  %tmp16 = phi i32 [ 3, %if.then ], [ 4, %if.else ]
  %add = add nsw i32 %tmp13, %tmp16
  ret i32 %add
}

在这里你可以看到，GVN 找到了可用值，插入了 PHI 节点，并消除了加载。

更复杂的地址表达式

虽然上面的例子可能很直观，但事实证明，PHI 转换像这样的表达式实际上比看起来要困难一些。它甚至被拆分成了一个单独的类，PHITransAddr（在 llvm/Analysis/PHITransAddr.h 中）。这样做实际上是由一些像这样的有趣的小例子驱动的

void test(int N, double* G) {
  for (long j = 1; j < 1000; j++)
    G[j] = G[j] + G[j-1];
}

这个例子 （它是从一个更大的例子中简化而来的） 有一个循环携带的冗余，其中每次迭代都会读取前一次迭代的值。实际上，这段代码可以重写成这样，循环中只包含一个加载

void test(int N, double* G) {
  double Prev = G[0];
  for (long j = 1; j < 1000; j++) {
    Prev = G[j] + Prev;
    G[j] = Prev;
  }
}

一些编译器具有专门的优化过程来识别并消除通过依赖分析进行的这些递归。虽然这是一件好事，但足够智能的部分冗余加载消除也应该能够消除这一点，而 LLVM 现在做到了。

未优化的代码在 LLVM IR 中看起来像这样

define void @test(i32 %N, double* %G) {
bb.nph:
  br label %for.body

for.body:
  %indvar = phi i64 [ 0, %bb.nph ], [ %tmp, %for.body ] ; indvar = [0 ... 999]
  %arrayidx6 = getelementptr double* %G, i64 %indvar
  %tmp = add i64 %indvar, 1
  %arrayidx = getelementptr double* %G, i64 %tmp
  %tmp3 = load double* %arrayidx                  ; load G[indvar+1]
  %tmp7 = load double* %arrayidx6                 ; load G[indvar]
  %add = fadd double %tmp3, %tmp7
  store double %add, double* %arrayidx            ; store G[indvar+1]
  %exitcond = icmp eq i64 %tmp, 999
  br i1 %exitcond, label %for.end, label %for.body

for.end:
  ret void
}

这里需要注意的一件有趣的事情是，-indvars 过程将归纳变量重写为从 0 到 999 计数，而不是从 1 到 1000 计数。 这仅仅是规范化，但这就是为什么我们看到对 indvar+1 的存储，而不是直接通过 indvar。

为了消除冗余的 "load G[indvar]"，GVN 首先寻找 %tmp7 加载的依赖项。 它向上扫描块，经过一些明显不会修改内存值的指令，直到它到达 %arrayidx6 指令，该指令定义了该值。 此时，它必须停止 PHI 转换（正确，但不是非常积极）或将其合并到扫描中并开始寻找 "gep %G, %indvar"。 它会这样做，直到下一个指令，该指令定义了 %indvar。 由于它找到了其中一个输入的定义，它必须停止 PHI 转换（同样正确，但不是非常积极）或尝试合并该值。

在这种情况下，PHITransAddr 试图将 "gep %G, %indvar" 符号表达式通过每个前驱的 PHI 转换。 在 %for.body 前驱中，它会查看是否存在一个指令可以生成 "gep %G, %tmp" 的值（因为 %tmp 是 %for.body 前驱中 PHI 的值），并且会发现该表达式作为 %arrayidx 存在。 由于 PHI 转换成功，它会从块的底部扫描以查看是否存在地址 %arrayidx 上的值的定义，并且会发现 %tmp3 加载产生了所需的值。

在另一个前驱 (%bb.nph) 中， PHITransAddr 将符号 "gep %G, %indvar" 表达式转换为 "gep %G, 0"（它使用 InstSimplify 将其简化为 "%G"），然后检查它是否作为地址可用。 "%G" 事实上是一个值地址，因此它会从 %bb.nph 块的底部扫描以查看地址 %G 上的值是否可用。 在这种情况下，它不可用，因此它记录该值在入口块中不可用，并且该块中的 PHI 转换地址为 %G。

此时，CFG 的递归遍历已经完成，并且 GVN 知道 %tmp7 加载实际上在其中一个前驱中作为 %tmp3 值可用，但在另一个前驱中不可用。 这是一个典型的部分冗余案例。 由于该值在一个边上是冗余的，但在另一个边上不是，GVN 通过在 %bb.nph 块中插入计算（对 %G 的加载）使该值完全冗余，构造 SSA 并消除原始加载。

我们得到的最终 LLVM IR 为

define void @test(i32 %N, double* %G) {
bb.nph:
  %tmp7.pre = load double* %G                     ; Inserted by PRE
  br label %for.body

for.body:
  %tmp7 = phi double [ %tmp7.pre, %bb.nph ],
                     [ %add, %for.body ]          ; SSA Construction
  %indvar = phi i64 [ 0, %bb.nph ], [ %tmp, %for.body ]
  %arrayidx6 = getelementptr double* %G, i64 %indvar
  %tmp = add i64 %indvar, 1
  %arrayidx = getelementptr double* %G, i64 %tmp
  %tmp3 = load double* %arrayidx
  %add = fadd double %tmp3, %tmp7      ; Now uses the PHI instead of a load
  store double %add, double* %arrayidx
  %exitcond = icmp eq i64 %tmp, 999
  br i1 %exitcond, label %for.end, label %for.body

for.end:
  ret void
}

通过此，GVN 和 PHI 转换共同努力消除了循环中的加载。 如果你更习惯于阅读 X86 机器代码，以下是循环的之前和之后代码

之前
LBB1_1:
 movsd 8(%rsi,%rax,8), %xmm0   # Load
 addsd (%rsi,%rax,8), %xmm0    # Load
 movsd %xmm0, 8(%rsi,%rax,8)   # Store
 incq %rax
 cmpq $999, %rax
 jne LBB1_1

之后
LBB1_1
addsd 8(%rsi,%rcx,8), %xmm0   # Load
 movsd %xmm0, 8(%rsi,%rcx,8)   # Store
 incq %rax
 incq %rcx
 cmpq $999, %rcx
 jne LBB1_1

如果你有兴趣了解 PHI 转换的其它示例，请查看 LLVM 发行版中的 test/Transforms/GVN/rle-phi-translate.ll 和 test/Transforms/GVN/rle.ll。

分工

要使这能够正常工作，需要多个不同的 LLVM 子系统共同协作。 以下是一些主要参与者

PHI 转换

该 PHITransAddr 类负责通过 PHI 节点构建和转换像 "gep %P, 1, (add %i, 1))" 这样的符号表达式。 当 "指令扫描" 发现当前 PHITransAddr 表达式的输入的定义时，它必须将其合并到（可能更大更复杂的）表达式中或放弃。 如果它放弃，则 PHI 转换失败，否则它可以继续扫描。

内存依赖分析

"MemDep" 是执行 CFG 和指令扫描的过程。 它构建了一个惰性和缓存的表示，在本质上类似于其它一些编译器使用的 "虚拟 SSA 形式"，但效率远高于我知道的虚拟 SSA 形式。

它公开了两个主要接口

1) "给我这个加载的所有本地依赖项"。 此查询会扫描加载所在的块以查找依赖指令。如果它没有找到依赖指令，它会返回 "非本地" 以指示加载的内存值可能对该块有效。

2) "给我对该块有效的加载的所有非本地依赖项"。此查询会执行递归的向上 CFG 扫描，该扫描会进行 PHI 转换以查找值的其它定义。

在 PHI 转换的有趣案例中，我们会最终执行非本地查询，并获得一组值可用的块以及一组值不可用的块。

别名分析

别名分析（在本例中，为 -basicaa 过程）是底层分析，它告诉我们两个指针是否可以指向同一个内存位置，或者一条指令是否可以修改或读取某个内存位置。 这需要 MemDep 能够扫描超出不会覆盖我们感兴趣的地址的存储和调用。

SSA 更新

该 SSAUpdater 类用于根据我们找到的可用加载集插入 PHI 节点。

GVN:

GVN 通道建立在所有这些子系统的基础之上。因为它基于其他设施，所以其逻辑相对简单：首先，进行一个非局部内存依赖性查询。如果它返回一组没有覆盖的定义，那么加载是完全冗余的，可以消除。否则，如果有一些定义处于活动状态，我们就会遇到一个部分冗余的情况。GVN 处理插入新的计算以使该值完全冗余。

限制

虽然这里有很多力量，但这个系统仍然有一些重要的限制。截至目前，以下是其中一些最显著的限制。

首先，符号表达式地址必须作为 SSA 值存在，才能使 PHI 翻译成功。在最后一个例子中，如果我们尝试将 "gep %G, %indvar" PHI 翻译成一个形成 "gep %G, %xxx" 符号表达式的祖先值，而该符号表达式实际上并不存在于代码中，那么 PHI 翻译就会失败。这是因为在 PHI 翻译完成之后，我们需要 MemDep 扫描块以查找依赖指令。由于 MemDep 查询基于以 LLVM 'Value*' 表示的指针值，因此我们需要有一个值才能进行查询。

其次，关键边目前阻止了加载的 PRE，因为我们不想在之前不存在的控制流路径上引入加载。原则上，我们可以通过延迟地拆分边来实现这一点，但这将需要更新 GVN 通道正在维护的其他正在进行中的数据结构，而我们目前还没有这样做。

最后，我们对加载的 PRE 肯定可以改进。目前，我们只在不会增加代码并且不会在之前不存在的路径上引入计算的情况下进行 PRE。由于我们正在删除加载，这意味着我们只希望最多插入一个加载。我们用来确定这种情况是否发生的启发式方法目前非常本地，可以改进。

无论如何，我希望这可以对 LLVM 中这个子系统如何工作以及它在 LLVM 2.7 中是如何变得更好的提供一个有用的概述。

-Chris