LLVM优化黑科技，让你的代码飞速运行

创作时间:

2025-01-22 18:20:15

作者:

@小白创作中心

LLVM优化黑科技，让你的代码飞速运行

LLVM（Low Level Virtual Machine）作为一款强大的编译器基础设施，提供了丰富的优化技术，如Dead Code Elimination（死代码消除）和Loop Unrolling（循环展开）等，可以帮助开发者显著提升代码性能。通过掌握这些优化技巧，你可以在编译过程中消除冗余代码，优化循环结构，从而让程序运行速度大幅提升。无论是从事编译器开发，还是希望优化现有代码性能，LLVM都是不可或缺的利器。快来一起探索LLVM的优化黑科技吧！

LLVM的核心优化技术

1. 激进的死代码消除

死代码消除是一种编译器优化技术，旨在删除程序中不会被执行的代码，从而提高程序的执行效率和资源利用率。死代码是指在程序的当前执行路径下不会被访问或执行的代码片段。

不可达操作通常有两类：

不可达基本块中的操作。当一个操作位于不可达基本块中，根据不可达基本块的定义，该操作将不可能被执行到，所以该操作为不可达操作。
由条件分支优化导致的舍弃基本块中的操作。当某个基本块 B 进行条件转移时，如果其条件在编译阶段可以直接被计算出来，那么编译阶段就很清楚条件转移会前往那个分支。相比于执行的分支，另一个分支将不会被编译器执行，这个分支所对应的所有操作都是不可达操作。

无用操作是指其结果没有外部可见效应，比如冗余的变量赋值操作，该变量在定义后没有在后续的操作中使用到，不会对后续操作产生任何影响，所以可以直接删除该变量赋值操作。

激进的死代码删除定义上有所不同，是递归定义：

初始，我们定义所有调用函数，函数返回，对存储器的操作为有效代码。
之后，我们标记以下语句是有效的：
- 对其他有效语句的 use 进行赋值的语句
- 其他有效语句控制依赖于的语句
之后，我们迭代得到所有语句，并把剩下的都删除。

我们希望回答的问题是，控制流图上的两个节点 x,y 中，x 能否直接控制节点 y 的执行？什么是控制执行呢？节点 x 有一个后继 u 能直接到达程序的 exitBlock 而不经过 y。而它同时也有一个后继 v 使得 v 到 exitBlock 的每一条路径都经过 y。

我们很容易就能得到控制依赖的等价定义：我们考虑 CFG 对应的反向图，在这张图上，x∈domFrontier(y)。因为 x 的前驱 v 被 y 直接支配，而它又能由 u 到达，因而 x 在 y 的支配边界上。

反向支配树（Reverse Dominator Tree, RDom）计算在死代码消除优化中是一个重要的工具，帮助优化器更好地理解程序的控制流结构，尤其是在处理指令和基本块之间的依赖关系时。

如果一个块的 terminal 被标记为不活跃的，它应当跳到它的后继中第一个活跃的块上。我们要在反支配树上寻找。我们断言，如果一个节点 x 是不活跃的，那么说 x 到 Rdom(x) 的这些节点一定都不是活跃的。如果其中有一个节点是活跃的，那么根据定义，一定能通过若干次 dominanceFrontier 的迭代，推出 x 是活跃的。那么我们只需要不停地迭代 target=target.Rdom 就行了。

标记关键指令

// 遍历基本块中的每条指令
for  ( auto  instr = (*bb)-> begin (); instr != (*bb)-> end (); instr = instr-> getNext ())
    {
        instDCEMarked[instr] =  false ;
// 如果指令是关键指令，标记为已处理并加入工作列表
if  (instr-> isCritical ())
        {
            instDCEMarked[instr] =  true ;
            bbDCEMarked[instr-> getParent ()] =  true ;
            worklist. push_back (instr);
        }
}

遍历工作列表进行活跃性分析：

处理了指令的使用链 , 定义链, 反向数据流，以及 PHI指令。
处理使用链：遍历当前指令的所有使用，并通过分析其定义来判断指令是否活跃。如果某个指令的使用依赖于一个未被标记的定义，该定义就会被加入工作列表。
处理定义链：遍历指令的定义，并检查其后续的使用。如果某个使用指令未被标记且其类型是无条件或条件使用，将其标记为活跃并加入工作列表。
处理反向数据流：遍历基本块的反向数据流RDF，处理所有跳转指令。如果某个跳转指令的目标是无效的，则它会被标记为死代码。
处理 PHI 指令：如果某些路径永远不会执行，对应的 PHI 指令就成了死代码。检查PHI 指令的输入源，如果源指令是死代码，则 PHI 指令也被视为死代码。

2. 循环展开

循环展开是LLVM优化层的重要技术之一，通过展开循环结构，减少循环控制开销，提高代码执行效率。在编译器的优化过程中，指令选择（Instruction Selection）是非常关键的一环。指令选择的主要任务是将中间表示（例如 LLVM IR）转换为目标特定的 SelectionDAG 节点，生成目标机器代码的指令序列，实现从高级语言表示到底层机器指令的转换。

具体来说，指令选择的过程包括以下几个关键步骤：

将内存中的 LLVM IR 变换为目标特定的 SelectionDAG 节点。
每个 SelectionDAG 节点能够表示单一基本块的计算过程。
在 DAG 图中，节点表示具体执行的指令，而边则编码了指令之间的数据流依赖关系。
目标是让 LLVM 代码生成程序库能够利用基于树的模式匹配指令选择算法，以实现高效的指令选择过程。

以上是一个 SelectionDAG 节点的例子。

红色线：红色连接线主要用于强制相邻的节点在执行时紧挨着，表示这些节点之间必须没有其他指令。
蓝色虚线：蓝色虚线连接代表非数据流链，用以强制两条指令的顺序，否则它们就是不相关的。

LLVM优化的实际效果

在实际应用中，LLVM的优化技术已经展现出了显著的效果。以Antmicro公司为例，他们在处理大规模Chisel设计时，通过优化LLVM的编译流程，将编译时间从10小时缩短到37分钟，实现了20倍的性能提升。

这个案例中，Chisel设计通过CIRCT转译为Verilog，再由Verilator生成C++模拟运行时代码，最后由LLVM编译为可执行二进制文件。由于生成的代码规模庞大且结构复杂，传统的编译优化方法难以应对。通过针对性的优化，LLVM成功解决了Scalar Replacement of Aggregates（SROA）阶段的性能瓶颈，大幅提升了编译效率。