鱼和熊掌不可兼得——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,并完成以下两个操作: ...