LLVM IR学习笔记 | 单小艺的博客

type

status

date

slug

summary

LLVM-IR简略学习笔记

🤓

这LR啊，是重庆LLVM的一大特色，不得不尝啊~

东学一点西学一点，后来发现顺序和内容和：编译高级教程｜学习笔记 - LeiWang1999 (leiblog.wang)这个帖子挺像的，~~咱也是高级上了。~~

IR、LLVM-IR

IR，全称intermediate representation，中间表示，是介于高级语言和低级语言的代码存在形式，IR的特点包括抽象性、可读性和可移植性，用于语法分析、代码优化和跨平台编译。

为什么使用LLVM-IR

~~因为它善~~LLVM-IR可以用于表示程序的控制流、数据流、内存访问等等，它是一种基于 SSA 形式（Static Single Assignment）的静态单赋值形式。人能看懂，比汇编简单一点，比高级语言底层一点，拿来做优化真好使吧。

怎么看懂LLVM-IR

LLVM-IR举例

SSA

SSA（static single assignment form，静态单赋值形式）于1980年在IBM开始进行研究。（~~石头门又干了~~）

SSA是IR的一种属性，要求每个变量仅被赋值一次并在被使用前定义。在初始的IR中已经存在的变量被划分为不同的版本，新的变量通常由原始名称和下标表示，因此每个定义实际上都有自己的不同版本。在SSA中，use-def链是显式的，并且每个链都包含一个单独的变量。

use-def链是一种特殊的数据结构：其中包含了一次定义和若干次使用，用于静态程序分析如数据流分析、可达性分析等中。use-def链是很多编译器优化的前置条件，包括常量传播和公共子表达式消除等。

一眼丁真，y1没用上，可以优化后删去，这就是SSA（bushi），

SSA的类型

（以下内容摘自wikipedia，结合了机翻和自己的部分理解）

Pruned SSA 剪枝SSA

Pruned SSA形式基于一个简单的观察：仅对于在 Φ 函数之后“live”的变量才需要 Φ 函数。（这里，“live”意味着沿着从相关 Φ 函数开始的某个路径使用该值。）如果变量不是“live”的，则不能使用 Φ 函数的结果，并且 Φ 函数的赋值是死代码。该形式的构造在 Φ 函数插入阶段使用实时变量信息来决定是否需要给定的 Φ 函数。如果原始变量名称在 Φ 函数插入点处不存在，则不会插入 Φ 函数。

Semi-pruned SSA 半剪枝SSA

Semi-pruned SSA是一种减少 Φ 函数数量的尝试，同时又不会产生相对较高的计算实时变量信息的成本。它基于以下观察：如果变量在进入基本块时从未处于活动状态，则它永远不需要 Φ 函数。在 SSA 构建过程中，任何“块本地”（块内完成def、use）变量的 Φ 函数都被忽略。与完整的实时变量分析相比，计算块局部变量集是一个更简单、更快速的过程，使得半剪枝 SSA 形式比剪枝 SSA 形式的计算效率更高。另一方面，半剪枝的SSA形式将包含更多的Φ函数。

Block arguments 块参数

Block arguments是 Φ 函数的替代方案，它在表示上是相同的，但实际上在优化期间可以更方便。块被命名并采用块参数列表，表示为函数参数。调用块时，块参数绑定到指定的值。 Swift SIL和 MLIR 使用块参数。

构建SSA

（这部分内容实际上是在后面的，但是二级标题分太碎了有点烦就挪到这里了）

构造SSA主要的步骤有两个：

在合适的位置放置φ函数

构造支配树

计算支配边界

插入φ函数

为变量重命名

为变量重命名实际上是将变量的定义与φ函数之间建立起联系

构造支配树、计算支配边界、插入φ函数都已经有了较为成熟的算法，值得注意的是，在DF(X)中插入φ函数，其本身也是一个对于变量的新定义（def），所以可能需要在DF(X)中插入新的φ函数。。

控制流图——CFG

CFG可以将程序执行的可能流向直观地展示出来，一系列顺序执行的语句构成一个个的block作为图的节点，跳转语句对应每一个出边，这样就将原本混成一坨的IR按照逻辑进行了处理变得更直观了。

随之而来的问题/SSA构建实操

我们已经知道了每次变更变量的时候，可以通过基于原变量加角标的形式将控制流图转化为SSA形式。那么考虑这样一个过程：

不难看出，要想符合SSA特性，不同的数据流向可能会导致后期的变量版本出现歧义（Func2中的y究竟是y1还是y2取决于数据来自于哪一个block），能否通过新的判断函数来维护整个程序的SSA性质？答案是肯定的。定义φ函数的功能为：根据之前的控制流，决定y3的定义以参与后续的程序执行，那么我们可以得到如下的优化CFG：

但是，要时刻记录数据变动并保留到后续的模块再通过φ函数判断当前变量的版本，对于程序实现原目的并没有实质性帮助，反而多增了很多不必要的内存占用与运行耗时，这是代码优化过程中难以接受的。因此，我们可以考虑一种等效的方式:

这里IF.then和IF.else最后的赋值指令就避免了后续的歧义问题。φ函数某种程度上代表了一种预处理方式。

φ函数的运用

提供代码片段max.c 如下

生成的IR如下

通过φ函数就可以处理这种版本不同步的问题。但是，我们真的需要在每一个带有多前驱的block开头都加上φ函数吗？有些“殊途同归”的变量是不是可以不使用φ也能正常运行？

alloca/load/store

LLVM IR借助“memory不是SSA value”的特点来开了个后门来妥协：前端在生成LLVM IR时，可以选择不生成真正的SSA形式，而是把局部变量生成为alloca/load/store形式：

用alloca来“声明”变量，得到一个指向该变量的指针

用store来把值存进变量里

用load来把值读出为SSA value

为什么不直接就把源程序完全处理成SSA形式呢，因为如果这样的话就会出现~~“前端只要把所有的优化做完就好了，而中端的pass需要考虑的就很多了”~~前端压力过大的情况，所以前端会通过暂存变量到memory的方式暂时规避这个问题，至于把含有这些关键词的ir真正变为具有SSA性质需要pass的参与（mem2reg pass），这个pass本质上就是识别“局部变量”的模式，并对它们构建SSA形式，具体而言，mem2reg pass采用的是iterated dominance frontier算法。

dominance frontiers方法

🤓

如果每一条从流图的入口结点到结点 n 的路径都经过结点 d, 我们就说 d 支配（dominate）n，记为 d dom n。请注意，在这个定义下每个结点都支配它自己。

-《编译原理》

描述支配逻辑的结构就是支配树（dominator tree）：

可以看出，初始节点支配该图的所有节点，而2，4，6又都由2支配，支配树节点的所有祖宗节点都对该节点具有支配关系，其中最近的支配节点称为直接支配点（immediate node），用IDom表示，例如上图IDom（6）=2。

当满足如果 d != n 且 d dom n，那么 d sdom n，（例如上图中1 sdom 5），sdom为严格支配。

说了这么多，什么是我们小标题里提到的支配边界（dominance frontier）呢？支配边界是指当前节点能支配的节点的边界（不包括边界本身），emm，感觉像是在说废话。一种阐述方式是这样的：“Y 是 X 的支配边界，当且仅当 X 支配 Y 的一个前驱节点，同时 X 并不严格支配 Y”

分析：节点5的支配边界节点4，它的一个前驱节点6被节点5支配，而节点4本身并不被节点5严格支配，这就是节点5支配范围“恰好达不到的地方”，也就是支配边界。

节点X的支配边界用DF(X)表示。

只有当节点A定义的某个变量沿着数据流到达其支配边界，才必须考虑将变量通过φ函数更新并统一成不同版本。其他情况可能还会引入φ函数，但是在支配边界的引入是不可优化的。

看到这里再去看前面的 SSA构建 可能就会更清晰一些了

Value、User、Use

Value·万物起源

请看下图(摊手):

LLVM的几乎所有类都是直接或间接继承自Value。Value是LLVM中表示所有可计算的值的基类，例如常量、指令、参数等。每个Value都有一个类型(Type)和一个名字(Name)。Value是LLVM IR中所有可计算实体的抽象。

User·使用者

User是LLVM IR中表示使用Value的类。User可以是指令(Instruction)、常量表达式(ConstantExpr)、全局变量(GlobalVariable)等。User持有对Value的引用，并且可以有多个Value作为其操作数(Operands)

User类包含一个OperandList来表示它使用的Value，每个操作数对应一个Use对象，List中通过存放Use，再经由Use中的指针间接访问到该User真正使用的Value。

Use·引用过程

Use表示的是Value和User之间的一个引用关系。每个Use包含一个指向被使用的Value的指针和一个指向对应User的指针。

Use允许LLVM跟踪每个Value的所有使用情况，并且当Value被修改或删除时，可以更新所有引用它的地方

将所有使用某Value的Use连接起来，就构成了关于这个Value的Uselist，表示使用该值的所有Use对象。

关系维护

创建 Use：

当一个 User 使用一个 Value 时，会创建一个 Use 实例，并将其添加到该 Value 的 UseList 中，以及该 User 的 OperandList 中。

更新 Use：

当 User 修改其使用的 Value 时，会更新相应的 Use 实例，并更新旧值和新值的 UseList。

删除 Use：

当 User 不再使用某个 Value 时，会从相应的List中移除对应的 Use 实例。

这种借由Use实例构建的关系，使得LLVM可以有效地管理值的生命周期和依赖关系。例如，当一个Value被删除或修改时，所有引用它的Use都会收到通知，从而可以更新或删除相应的引用。同样，当一个User被删除时，它持有的所有Use也会被删除，从而解除了对Value的引用。

示例说明

🤓☝️哎，弄个例子给你

详细的说明参考这篇文章：LLVM 中的Value、User、Use设计-CSDN博客

It’s time for 优化

项目链接：

从学长手里蹭到的项目，学习一下pass的写法

mem2reg

上文已经提到了，前端在处理AST时会保留一些“棘手”的局部变量丢进memory里，来保证至少处理过的IR具有SSA性质（毕竟memory里不需要保证单一静态的赋值形式），而mem2reg就是把这部分再次薅出来处理掉~（代码已经由学长给出，我负责补充一些自己的理解就好了）

DCE（死代码清除）

结合上述知识，如果一个value没有任何的User，并且这个指令并不会对程序的执行产生其他的side effect，那么这个value就是多余的。

逻辑上来说，最好实现的肯定是Run(),只需要遍历function的每一个block，再遍历block里面的每一个instruction，判断好没有User和side effect就删除就完了。

对于HasSideEffect()，参考了

副作用和推测 - MLIR --- Side Effects & Speculation - MLIR (llvm.org)
Operations with memory effects. These operations read from and write to some mutable system resource, e.g. the heap, the stack, HW registers, the console. They may also interact with the heap in other ways, like by allocating and freeing memory. E.g. standard memory reads and writes, printf (which can be modeled as “writing” to the console and reading from the input buffers).
具有记忆效应的操作。这些操作读取和写入一些可变的系统资源，例如堆、堆栈、硬件寄存器、控制台。它们还可以通过其他方式与堆交互，例如分配和释放内存。例如，标准内存读取和写入、printf（可以建模为“写入”控制台并从输入缓冲区读取）。
Operations with undefined behavior. These operations are not defined on certain inputs or in some situations – we do not specify what happens when such illegal inputs are passed, and instead say that behavior is undefined and can assume it does not happen. In practice, in such cases these ops may do anything from producing garbage results to crashing the program or corrupting memory. E.g. integer division which has UB when dividing by zero, loading from a pointer that has been freed.
具有未定义行为的操作。这些操作没有在某些 inputs 上定义，或者在某些情况下没有定义 – 我们没有指定当传递此类非法 input 时会发生什么，而是说行为是未定义的，可以假设它不会发生。在实践中，在这种情况下，这些 operations 可能会做任何事情，从产生垃圾结果到使程序崩溃或损坏内存。例如，整数除法在除以零时具有 UB，从已释放的指针加载。
Operations that don’t terminate. E.g. an scf.while where the condition is always true.
不会终止的操作。例如，条件始终为 true 的 scf.while。
Operations with non-local control flow. These operations may pop their current frame of execution and return directly to an older frame. E.g. longjmp, operations that throw exceptions.
具有非本地控制流的操作。这些操作可能会弹出其当前执行帧并直接返回到较旧的帧。例如 longjmp，引发异常的操作。

于是对User类进行了查询

这五种操作是具有副作用的。实现的代码如下

然后是RemoveInst(),摁着Ctrl单击找到定义然后确定好使用的函数就没问题了

ConstantProp

有些操作数均为常数的User可以被常数运算的结果代替。以此来减少不必要的运算成本。

首先考虑Run()函数，怎么判断某个User是否可以用常量代替呢？只要它的所有的操作数都为常量就可以啦。可以套用上个pass使用的遍历方式。

而对于常量折叠函数，实际上就是把能算的表达式的值算出来，而对于单个数字没有折叠的必要：

（感谢copilot自动补全QAQ，手写真煎熬吧）

会不会在执行ConstantProp的过程中随着边遍历边替换，出现新的符合优化条件的情景呢，答案是肯定的，但是，由于程序运行逻辑和我们的遍历逻辑都是自先向后的，所以每当我们进行常量折叠与传播时，总能保证新出现的符合pass优化条件的情形出现在目前pass已经处理的IR之后。所以就可以跑一遍遍历出结果了~