鱼和熊掌不可兼得——LLVM 条件常量传播优化的设计与妥协

前言

现代编译器可以通过推断程序代码中的变量值，消除代码中的部分计算指令和分支，从而减轻编译产物的执行时开销。借助上述优化，程序员通常可以在保持代码可读性的前提下得到较优的编译产物，而无须手动特化各个变量。

编译器可以通过分支条件或断言来推断一个变量的值或其范围。下面展示了一个简单的例子：

if (a > 10) {
  if (a > 5) return 1;
  return 0;
}
return 1;

显然，当程序的控制流进入第一个if语句的true分支时，a>10成立，从而a>5也必然成立。因此，嵌套的if语句可以被直接消除，该程序可以优化为直接返回1。

同样地，程序员也可以通过assume语句向编译器传递信息：

assume(a > 10);
if (a > 5) return 1;
return 0;

在这个例子中，编译器可以通过assume语句得知a>10，进而判断a>5成立。因此，该程序也同样可以被优化为直接返回1。

一个符合直觉的想法是，编译器拥有越多信息，就能够产生越高效的编译产物。然而，学术界却发现事实并非如此（Refined Input, Degraded Output: The Counterintuitive World of Compiler Behavior, PLDI 2024）。

Due to unexpected interactions between compiler components and phase ordering issues, sometimes more information leads to worse optimization. (由于编译器组件之间存在意外的相互作用以及优化阶段的顺序安排问题，有时掌握或提供更多的信息反而会导致优化效果变差。)

这篇博文将以LLVM中一个简单的Issue为引，探索LLVM中的IPSCCP (Interprocedural Sparse Conditional Constant Propagation，过程间稀疏条件常量传播)的实现，尝试理解现代编译器如何利用代码中的可被推断的常量信息，以及其在实际工程实践中的考量与妥协。

背景

前言中的两个例子以伪代码的形式介绍了编译器的条件常量传播优化。为了更深入探索LLVM的具体优化实现，我们需要将视角转向其编译的中间产物LLVM IR。下面展示了一个LLVM IR的例子：

; Code Snippet #1
@a1 = external global i32

define i32 @src(i32 %L) {
BB:
  store i32 %L, ptr @a1, align 4
  %cmp = icmp eq i32 %L, 10
  call void @llvm.assume(i1 %cmp)
  ret i32 %L
}

在上述例子中，函数src接收参数%L，并完成以下两个操作：

将%L写入指针@a1对应的内存
函数返回值%L 除此之外，编译器还被提供了额外的信息：%L首先与常数10进行相等比较（icmp eq操作），之后代码通过@llvm.assume函数告知编译器该比较的结果恒为真。显然，此时可以推断得到%L的值为常量10。因此，store语句和ret语句中的%L应该被替换为该常量。然而，编译器的输出并未符合我们的预期：

; clang-trunk -O3 generates:
define noundef i32 @src(i32 %L) local_unnamed_addr #0 {
BB:
  store i32 %L, ptr @a1, align 4 ; %L is not substituted here!
  %cmp = icmp eq i32 %L, 10
  tail call void @llvm.assume(i1 %cmp)
  ret i32 10 ; %L is substituted as expected.
}

编译器成功将ret语句的%L替换为常量10，然而store语句的%L并未被替换。为了进一步调查LLVM是否能够推断assume语句之前的%L的值，我们可以尝试改写上面的IR：

; Code Snippet #2
@a1 = external global i32
define i32 @src(i32 %L) {
BB:
  %H = add i32 %L, 1
  store i32 %H, ptr @a1, align 4
  %cmp = icmp eq i32 %L, 10
  call void @llvm.assume(i1 %cmp)
  ret i32 %L
}

在这个新的例子中，我们使用add命令将%L的值加1后再进行store操作。出乎意料的是，编译器在这段代码上展示了我们预期的正确优化行为：

define noundef i32 @src(i32 %L) local_unnamed_addr #0 {
BB:
  store i32 11, ptr @a1, align 4 ; %H is substituted by 11!
  %cmp = icmp eq i32 %L, 10
  tail call void @llvm.assume(i1 %cmp)
  ret i32 10 ; %L is substituted as expected.
}

上述代码store语句中的操作数%L被正确替换为常量11。因此，我们有理由相信最初代码片段是编译器出现了missed-optimization bug的结果。上述几个例子是LLVM repo中Issue #134540 和Issue #134992 的简化形式，对应的原始代码可以在libstdc++中找到（参见原始issue描述）。解决这个问题可能可以提升编译产物的执行效率，为各种基础系统软件引入新的优化机会。

问题分析

我们在上一小节中展示了一个简单的LLVM优化不符合预期的例子。通过使用-debug参数运行llvm-opt工具，可以得到各个优化pass对IR的转换。可以注意到，与我们关注的%L相关的优化主要集中在IPSCCP (Interprocedural Sparse Conditional Constant Propagation，过程间稀疏条件常量传播)以及InstCombine 两个优化pass上。

IPSCCP Pass
根据LLVM官方文档的介绍，该pass是SCCP（Sparse Conditional Constant Propagation，稀疏条件常量传播）加入了过程间信息传递的变体。而SCCP主要实现以下两个优化：（1）证明一个变量存储的值是常数，并将其以对应的常数替代；(2) 证明一个条件分支是非条件（unconditional）的。这两个优化可以对IR实现变换，进而减少编译期计算和执行分支语句的开销。
InstCombine Pass
这个pass的其中一个作用是检查指令操作数推断的值域，并通过这些信息尝试简化相关指令。例如，对于add %x, 1指令，若能够推断出变量%x的最后一位数字为0，则该指令可以被简化为对处理器执行更友好的or %x, 1，因为其在加1时不会产生进位。同样地，若%x被推断为常数，则其将直接消除这个add指令，并用常数替代计算结果。

将上一节的代码片段#2作为优化器的输入，以默认的Source->IPSCCP->InstCombine的顺序执行优化，可以分步得到以下结果（一些中间优化步骤被隐去）：

Source->IPSCCP Pass

BB:
  %H = add i32 %L, 1
  store i32 %H, ptr @a1, align 4
  %cmp = icmp eq i32 %L, 10
  call void @llvm.assume(i1 %cmp)
  ret i32 10
}

Source->IPSCCP Pass->InstCombine Pass

BB:
  store i32 11, ptr @a1, align 4
  %cmp = icmp eq i32 %L, 10
  tail call void @llvm.assume(i1 %cmp)
  ret i32 10
}

可以看到，IPSCCP Pass替换了ret指令中的%L，但其没有对add指令的操作数%L进行替换。对add和store语句中%L和%H的替换由InstCombine Pass完成。进一步分析InstCombine Pass，发现其对于二元算术运算（如add, sub等）以及其余一些操作会利用当前已经得到的assumption对操作数进行简化，这也是代码片段#2可以正确被优化的原因。然而，对于代码片段#1中的store语句（以及不在上述例子中的zext等其它语句），其并不会尝试检查操作数是否为常量，因此导致了代码片段#1中store语句的操作数%L没有被替换。理论上，在InstCombine Pass的visitStoreInst函数中加入以下对操作数是否为常量的检查即可解决代码片段#1中的问题：

Instruction *InstCombinerImpl::visitStoreInst(StoreInst &SI) {
  // Existing code...
  if(!isa<Constant>(Val)) {
    KnownBits Known(Val->getType()->getScalarSizeInBits());
    computeKnownBits(Val, Known, 0, &SI);
    if (Known.isConstant()) {
      Constant *C = ConstantInt::get(Val->getType(), Known.getConstant());
      return replaceOperand(SI, 0, C);
    }
  }
  // Existing code...
}

然而，InstCombine Pass并不是IPSCCP Pass的“故障备份”，为所有指令的操作数进行常量检查并不符合其职责，同时由于其可以细粒度地追踪一个值的所有二进制位，利用这个机制来实现常量替换可能引入不可忽视的编译性能开销，对应修改也几乎不可能被上游接受。因此，我们需要将目光转向引起该问题的根源，即IPSCCP Pass。

IPSCCP的设计、实现和妥协

这篇博文不会详尽介绍IPSCCP的架构，而是会以上述提到的问题为切入点，聚焦于IPSCCP中处理分支条件和断言的部分，说明其如何利用程序员提供的assume信息来指导优化，以及上面几个小节中提到的问题是如何产生的。为了更好地理解后面IPSCCP引入的变量重命名和“重命名栈 (RenameStack)”的必要性，该小节将首先从谓词作用域的概念引入，并逐渐接近我们本文讨论的missed-optimization问题的根源。

谓词作用域

形式化地，一个谓词的作用域包含该谓词所在及其支配的基本块。一个更通俗易懂的说法是，当程序的“执行”了一个的assume语句或进入了条件判断的其中一个分支，我们才可以认为这个assume语句的条件或该判断的分支条件（或其否定）在后续的执行流中为真。下面通过一个直观的例子解释谓词作用域的概念：

; Code Snippet #3
define void @src(i32 %L) {
BB:
  %cond = icmp ult i32 %L, 5
  br i1 %cond, label %BB1, label %BB2
BB1:
  %cmp1 = icmp ult i32 %L, 10
  call void @use(i1 %cmp1)
  ret void
BB2:
  %cmp2 = icmp ult i32 %L, 10
  call void @use(i1 %cmp2)
  ret void
}

上面的是一个简单的嵌套分支代码片段。在基本块BB中，代码首先判断%L是否大于5，若成立，则跳转到基本块BB1，否则跳转到基本块BB2。基本块BB1和BB2的代码一致，均判断%L是否大于10，并使用判断结果作为参数调用外部函数@use。显然，若%L>5成立，则%L>10也一定成立。因此，BB1中的%cmp1可以直接被优化为true，而BB2中的%cmp2则需要被保留。在这个例子里，LLVM可以得到正确的优化结果：

define void @src(i32 %L) {
BB:
  %cond = icmp ult i32 %L, 5
  br i1 %cond, label %BB1, label %BB2
BB1: ; preds = %BB
  call void @use(i1 true) ; substituted by "true"!
  ret void
BB2: ; preds = %BB
  %cmp2 = icmp ult i32 %L, 10
  call void @use(i1 %cmp2)
  ret void
}

因此，同样是参数%L，其推断的范围在不同的基本块中可能并不一致（在上面的例子中，BB1的范围是0<%L<5，BB2的范围是5≤%L）。这为维护一个变量的值域和得到值域后“定向”替换那些可被推断的变量这两个操作带来了困难。为了更优雅地解决这个问题，IPSCCP引入了变量重命名机制。

变量重命名

IPSCCP为所有拥有相同值域的变量使用者生成该变量的拷贝，再使用拷贝后的变量替换这些使用者的原有操作数。我们以代码片段#3来说明：

; Code Snippet #3.1
define void @src(i32 %L) {
BB:
  %cond = icmp ult i32 %L, 5
  %L.0 = call i32 @llvm.ssa.copy.i32(i32 %L)
  %L.1 = call i32 @llvm.ssa.copy.i32(i32 %L)
  br i1 %cond, label %BB1, label %BB2
BB1:
  %cmp1 = icmp ult i32 %L.0, 10
  call void @use(i1 %cmp1)
  ret void
BB2:
  %cmp2 = icmp ult i32 %L.1, 10
  call void @use(i1 %cmp2)
  ret void
}

代码片段#3.1展示了对%L重命名后的代码。其使用 @llvm.ssa.copy intrinsic生成%L的两个拷贝%L.0和%L.1，并分别将其替换到基本块BB1和BB2中。因此，现在我们可以轻松地得到各个变量的值域（为了简单起见，我们假设各个变量为unsigned类型）：

变量名	值域
%L.0	(0, 5)
%L.1	[5, 1«32)

可见，变量重命名为变量值域的分析和基本块中变量的代换提供了便利。对于多层条件语句等嵌套代码而言，一个变量可能被多次重命名并可能生成若干拷贝。IPSCCP使用栈来维护变量值域。栈上的每个元素表示对该变量的一次重命名，而每次重命名都会为该变量带来新的约束（想象对一个变量嵌套的if条件判断语句）。因此，每次我们只需要将栈上的所有约束使用AND操作合并，即可得到当前变量的值域。而当我们离开某个约束的作用域时，只需要从栈中弹出该元素即可。

重命名栈和操作数替换实现

为了高效（在不扫描整份代码的前提下）实现变量重命名和对应使用者操作数的替换，IPSCCP主要将代码分析分为三个阶段（省略了部分迭代细节）：

Build Phase: 收集与变量关联的所有谓词信息（包括Branch语句、Switch语句和Assume语句）；
Rename Phase: 对于每个有优化机会的变量，遍历其uses，并同时完成变量重命名和对所有使用者操作数的替换；
Solve Phase: 合并所有变量的可能取值区间，并通过收集的信息简化操作数（如将其替换为常数）。其中，Build Phase和Solve Phase都相对标准化，且与本文开始时提到的issue关系不大。因此，我们将主要介绍Rename Phase的实现。为了更好地展示Rename Stack的工作方式，这里引入本文的最后一个代码片段。

; Code Snippet #4
define void @basic(i32 %v) {
  %a1 = icmp ult i32 %v, 10
  call void @llvm.assume(i1 %a1)
  %a2 = icmp ugt i32 %v, 5
  call void @llvm.assume(i1 %a2)
  %c1 = icmp ult i32 %v, 10
  call void @use(i1 %c1)
  ret void
}

在这个片段中，我们通过两个assume将变量%v的范围限制在了(5, 10)，之后，变量%c1就可被推断为true。下面，本文将逐步介绍IPSCPP是怎么完成这段代码的优化的。

Build Phase

在这一阶段，IPSCCP遍历所有的assume语句，找到需要重命名的变量。对于每个变量，其找到所有的use点，并按基本块的DFS序进行排序。需要注意的是，assume语句也会被视为一个间接的use点（在ValueDFS数据结构中使用PredicateInfo字段存储）。对于代码片段#4，其产生的排序后的使用者序列如下所示：

OrderedUses:
[0] Use: %a1
[1] Predicate: %a1, OriginalOp: %v, RenamedOp: null
[2] Use: %a2
[3] Predicate: %a2, OriginalOp: %v, RenamedOp: null
[4] Use: %c1

RenameStack:
(empty)

RenamePhase

构建完成使用者序列后，IPSCCP进入RenamePhase，其按顺序遍历这个序列，并在遍历过程中维护当前变量的重命名栈RenameStack。

Step 1

OrderedUses:
* [0] Use: %a1
[1] Predicate: %a1, OriginalOp: %v, RenamedOp: null
[2] Use: %a2
[3] Predicate: %a2, OriginalOp: %v, RenamedOp: null
[4] Use: %c1

RenameStack:
(empty)

IPSCCP首先访问第一个use %a1，但因为RenameStack为空，其直接跳过。

Step 2

OrderedUses:
[0] Use: %a1
* [1] Predicate: %a1, OriginalOp: %v, RenamedOp: null
[2] Use: %a2
[3] Predicate: %a2, OriginalOp: %v, RenamedOp: null
[4] Use: %c1

RenameStack:
-> [0]: Predicate: %a1, OriginalOp: %v, RenamedOp: null

IPSCCP访问下一个项Predicate，并将其推至栈中。

Step 3

OrderedUses:
[0] Use: %a1
[1] Predicate: %a1, OriginalOp: %v, RenamedOp: %v
* [2] Use: %a2
[3] Predicate: %a2, OriginalOp: %v, RenamedOp: null
[4] Use: %c1

RenameStack:
[0]: Predicate: %a1, OriginalOp: %v, RenamedOp: %v

IPSCPP访问use %a2。此时重命名栈不为空。由于栈中的变量尚未被重命名（late-materialization，对于没有use的变量可以节省重命名开销），栈中对应新元素的RenamedOp被设置为原变量名%v。同时，use %a2中与OriginalOp %v相同的操作数被替换为改名后的变量%1。此时，对应的IR指令序列变换为：

; Code Snippet #4.1
define void @basic(i32 %v) {
  %a1 = icmp ult i32 %v, 10
  call void @llvm.assume(i1 %a1)
  -> %1 = call i32 @llvm.ssa.copy.i32(i32 %v)
  %a2 = icmp ugt i32 %1, 5
  call void @llvm.assume(i1 %a2)
  %c1 = icmp ult i32 %v, 10
  call void @use(i1 %c1)
  ret void
}

需要注意的是，这里仅替换了%a2指令的操作数。%a1指令的操作数%v没有被替换，这也和RenameStack中Predicate: %a1的RenamedOp为%v的行为保持一致。RenamedOp表示我们关心的变量在该Predicate中对应的操作数。在Solve Phase中，RenamedOp可以帮助我们在各个Predicate里轻松找到我们关心的变量（不管其是否被重命名）。

Step 4

OrderedUses:
[0] Use: %a1
[1] Predicate: %a1, OriginalOp: %v, RenamedOp: %v
[2] Use: %a2
* [3] Predicate: %a2, OriginalOp: %v, RenamedOp: null
[4] Use: %c1

RenameStack:
[0]: Predicate: %a1, OriginalOp: %v, RenamedOp: %v (Def: %1)
-> [1]: Predicate: %a2, OriginalOp: %v, RenamedOp: null

和Step 2 相同，IPSCCP访问Predicate并将其推至栈中。

Step 5

OrderedUses:
[0] Use: %a1
[1] Predicate: %a1, OriginalOp: %v, RenamedOp: %v
[2] Use: %a2
[3] Predicate: %a2, OriginalOp: %v, RenamedOp: null
* [4] Use: %c1

RenameStack:
[0]: Predicate: %a1, OriginalOp: %v, RenamedOp: %v (Def: %1)
[1]: Predicate: %a2, OriginalOp: %v, RenamedOp: %1 (Def: %2)

IPSCPP访问use %c1。此时重命名栈不为空。其从最早一个没有被materialize的变量开始，对所有RenameStack中的项进行materialize，并在对应语句后插入ssa_copy语句。

; Code Snippet #4.2
define void @basic(i32 %v) {
  %a1 = icmp ult i32 %v, 10
  call void @llvm.assume(i1 %a1)
  %1 = call i32 @llvm.ssa.copy.i32(i32 %v)
  %a2 = icmp ugt i32 %1, 5
  call void @llvm.assume(i1 %a2)
  -> %2 = call i32 @llvm.ssa.copy.i32(i32 %1)
  %c1 = icmp ult i32 %v, %2
  call void @use(i1 %c1)
  ret void
}

这里同样仅替换了%c1指令的操作数。除此之外，RenameStack中Predicate %a2的RenamedOp被指向%1，这也与在该icmp指令上实际发生的操作数替换相符。

总结

IPSCPP的RenamePhase通过使用重命名栈，巧妙地维护了每个Predicate的icmp（或其它比较指令）中具体是哪一个操作数与我们关心的变量相关的信息。重命名信息沿着栈向栈顶传递，当一个Predicate的操作数因为栈前面的Predicate而发生重命名时，它能根据栈上的信息找到其具体被重命名为了哪一个值。

Solve Phase

收集了所有变量的Predicate信息后，IPSCCP迭代找到每个变量在各个基本块中的取值范围，并尝试进行常量替换。该步骤和本文前面提到的missed-optimization bug无关，故不在本文的讨论范围之内。

妥协

让我们回到第一个代码片段：

; Code Snippet #1
@a1 = external global i32

define i32 @src(i32 %L) {
BB:
  store i32 %L, ptr @a1, align 4
  %cmp = icmp eq i32 %L, 10
  call void @llvm.assume(i1 %cmp)
  ret i32 %L
}

通过分析IPSCPP的具体实现，我们终于明白了这段代码的bug是怎么出现的：由于RenamePhase顺序访问基本块中的语句，故在访问store时，RenameStack还为空，故其没有正确完成重命名。事实上，这个bug更接近一个工程实现上的妥协：如果需要让assume可以作用到当前基本块中该assume语句之前的指令，则RenameStack以及重命名信息的传递方式需要被重新设计。其原因是，如果我们需要把变量重命名和对应的ssa_copy指令提升到assume以及其对应的icmp等条件判断语句之前，则这些条件判断语句的操作数就会受到变量重命名的影响。此时，我们难以使用RenamedOp来简单跟踪条件判断语句里我们感兴趣的变量对应的操作数。

当然，我们也许可以引入新的机制，例如使一个原始变量在一个基本块内不会被多次重命名，或以集合形式维护RenamedOp来绕过这个问题，但这必将为该算法的设计带来更多的复杂性，最终会不会被社区所接受也就不得而知了。

小结

现代操作系统和编译器等基础系统软件正在以惊人的速度走向复杂化。在我们谈论的这个例子中，LLVM原有的实现优雅、简单，能够正确实现绝大部分优化。然而，在某些示例中，我们会发现设计者的假设（基本块中位于前面的指令不应该使用到assume的结果）往往阻碍了优化的进展，而解决这个问题又会破坏原有算法符合直觉的特性，并可能无意地为编译器或后续维护人员埋下雷点。

当更好的性能表现意味着更复杂、更难以维护的设计，我们应该如何取舍？

前言#

背景#

问题分析#

IPSCCP的设计、实现和妥协#

谓词作用域#

变量重命名#

重命名栈和操作数替换实现#

Build Phase#

RenamePhase#

Step 1#

Step 2#

Step 3#

Step 4#

Step 5#

总结#

Solve Phase#

妥协#

小结#

前言

背景