LLVM(Low Level Virtual Machine)PL 界的邪恶飞龙,统治了半数软件。它使用 CMake 作为构建工具,这是一个“前现代”的构建系统(相比 makefile 与 xmake),这可以极大方便编译过程,并获得品尝屎味巧克力的机会。

LLVM 是一个编译器“后端”,但是LLVM项目内部会被进一步分成“中端”和“后端”。在传统的编译原理课程中,习惯性的将编译器分成“前端”和“后端”,LLVM整体对应这个后端。而在现代的编译器中,后端会被进一步拆分为:方便做优化、目标无关的中端;以及方便做代码生成,贴近目标的后端。

认识 LLVM

LLVM 存在大量的测试工具,大部分用于测试。LLVM 使用 gtest(google test) 作为测试框架,类似其他测试框架(比如 catch2),但是提供丰富的测试生态,以及沉重的库。

如何测试

// todo, If you're reading this, then you're reading this.

项目结构

llvm-project 有很多其他项目,比如 clang、lldb、llvm 之类的。llvm 是核心,llvm 项目下,还会有 include、lib、tools、unittests、utils等等,其中 lib 相当于 src 文件夹、unitests 单元测试、tools 有单独 target 的工具、include 很有说法:

  • llvm-project 的项目都采用 llvm/include/llvm/.../xxx.h 这样的组织方式,这里面 include 放的都是公开 API 的头文件,这里面重复两次项目是因为

    • 第一次是根目录区分项目文件夹,这样对应两个项目的源码,这无需解释

    • 第二次是为了头文件能有一个前缀做区分,他的target_include_directory会设置到对应项目的 include目录,从而每次导包的时候都是 #include "llvm/..."这样,毕竟 c++ 缺少模块化基础设施,至少在 LLVM 立项时没有,到现在也没人敢用。

  • llvm 的模块私有头直接放到了子模块的源码文件夹中了

  • llvm 的所有模块共享,但不暴露的给外部项目或者说不会 install 的头放到了include/llvm下,但是在安装的时候被排除了

LLVM IR 结构

如果学过编译原理,这个概念非常简单,LLVM 所有概念几乎都可以直接对应到标准的学术界编译原理课程:

--- config: layout: elk elk: mergeEdges: false nodePlacementStrategy: NETWORK_SIMPLEX flowchart: curve: linear nodeSpacing: 40 rankSpacing: 55 --- flowchart TB M["Module"] G["GlobalVariable"] F["Function"] A["Arguments"] R["Return Type"] B["BasicBlock"] I["Instruction"] T["Terminator"] P["PHINode"] OP["Opcode"] V["Result Value"] O["Operands"] M --> G M --> F F --> A F --> R F --> B B --> I B --> T I --> P I --> OP I --> V I --> O

总体上 LLVM 的 IR 结构大体上是

  • 模块:包括函数 和 全局变量

  • 函数:包括 返回值 参数 函数体(基本块)

  • 全局变量

  • 基本快:CFG 图结构的一个节点,内部是指令

  • 指令:包括 操作 结果变量 操作数

LLVM 的中端和后端还有两套 IR(Mid-End IR 和 Machine IR),不过他们都有完全一致的层次结构,只是对应的类不同。

模块 函数 全局变量(中端)

模块几乎对应着一个翻译单元(Translation Unit)或者 编译单元(Compilation Unit),并没有太多要说的,因为他可以看作是一个组织编译器编译单元内顶级对象的容器(比如一个 .c 文件有很多函数和全局变量)

函数是模块下的对象,对应着一个编程语言的函数(如果没有被内联掉的话)。和高级编程语言一样他有 参数、返回值、“函数体”。

全局变量:同 C 中的全局变量,不过他本质表达的是一个地址

API功能:

  • 构建模块(Module类)

    • 构造函数 Module(name, ctx)

    • 读取IR文件 parseIRFile(filename, dignostic, ctx)

    • 使用IR字符串 parseAssemblyString(irstr, dignostic, ctx)

  • 模块可获取迭代器,遍历所有的函数

  • Function 类继承了 GlobalValue,使用 empty() 判断是否有函数体(因为 LLVM 支持函数声明)

  • Function::getParent 可以获取的父模块

基本块(中端)

基本块 Basic Block,这是学术界 混合IR(CFG) 的经典概念,CFG 是一个图,用来表示代码块之间的转移关系,基本块基本的点就在于,不会有任何语句跳转会跳到基本块中间位置,也不会有任何语句会从基本块中间跳走(single-entry single-exit,SESE),内部顺序执行,这种结构可以方便编译器分析控制流。

基本块规则:

  • 第一条指令是基本快的入口

  • 被跳到的指令是基本块的入口

  • 跳转指令的下一条指令是基本块的入口

  • 基本块是入口指令(包含)到下一个入口指令(不包含)

同时还有一些基础概念:

  • Entry Point:第一个执行的 CFG 节点,从图论角度上来说,理论的入度不一定为 0(不过 LLVM 规定 Entry 必须无前驱),Entry Point 一定只有一个

  • Exit Point:所有可能的结束点,从图论角度上来说,出度不一定为 0,Exit Point 可能有多个

  • RPO:逆后序,也就是一个从 Entry Point 开始的翻转后的后序遍历循序。这个顺序是 Kosaraju 算法的一部分,因此它能线性表达拓扑顺序(尽管有环图无拓扑序),可以验证证明,假设对所有的强连通分量进行 SC 标号,SC 标号的大小顺序是一定满足拓扑序的。

  • 回边(backedge):回边是导致无拓扑序的罪魁祸首,一般回边意味着循环。如果存在一条边 u→vu \rightarrow v,同时 vv支配 uu,那么这是一条回边。

  • 关键边(critical edge):如果存在A、B两个节点,存在边 A→BA \rightarrow B,其中 A 有多条出边,B 有多条入边,这条边就是关键边。因为关于该边的优化,会被多个路径限制。

  • 不可规约图(irreducible graph):不可规约图意味着非自然循环,不可规约图循环优化更复杂,容易出错。

--- config: layout: elk look: classic elk: nodePlacementStrategy: NETWORK_SIMPLEX nodePlacementAlignment: BALANCED flowchart: curve: step nodeSpacing: 80 rankSpacing: 80 --- flowchart LR E["Entry"] A["A"] B["B"] X["Exit"] E -->|"!start"| A E -->|"start"| B A <--> B A --> X B --> X classDef normal fill:#f8fafc,stroke:#475569,color:#0f172a,stroke-width:1.5px classDef loop fill:#ffedd5,stroke:#c2410c,color:#7c2d12,stroke-width:2px class E,X normal class A,B loop

可以用迭代的方法判断不可规约图:

  1. 如果边 A→BA \rightarrow B,其中AA是BB的唯一前驱BB是AA的后继(理论角度可以不唯一),那么合并两个节点。

  2. 如果存在一条自边,那么删掉这个自边。

最后如果图可以规约成一个节点,则是可规约图,否则是不可规约图。

LLVM 基本块基本使用了学术上定义的 BB(Baisc Block),对此 LLVM 采用如下实现:

  • 第一条指令是特殊指令(如果存在),比如 phi (SSA内容)

  • 最后一条指令必须是终结指令,比如跳转

  • 没有隐式顺延(fall-through),必须显式添加跳转指令

  • 由于上面的原因,导致基本块一定不为空

API功能

  • BasicBlock::getFirstNonPHI() 第一个非PHI指令

  • BasicBlock::getTerminator() 获取结束指令

  • BasicBlock::getIterator() 可以直接获取当前BB的迭代器

  • 可以获取BB的迭代器,遍历所有的指令

指令(中端)

LLVM指令对应着三地址码,比较接近四元式,因此一个指令同时表示声明变量和定义操作。包含:

  • 定义:接收变量

  • 操作数:也就是指令需要使用的其他变量

  • 操作码:指令对应的行为

API

  • Instruction 对象自己就是变量声明(SSA 值的定义)

  • Instruction::getOperand(unsigned) 获取操作数

  • Instruction::getOpcode() 获取操作码

  • Instruction::getParent() 对应的基本块

  • 还有一大堆moveBefore/After、insertBefore...,实际上Instruction之间使用链表连接

机器 IR

机器 IR 几乎一一对应中端 IR:MachineModuleInfo、MachineFunction、MachineBasicBlock、MachineInstr:

  • MachineModuleInfo,没有模块概念,提供基础的 Function 到 MachineFunction map映射,主要是表示函数的集合,因为Machine IR 更底层,开始淡化模块,关注函数层次。

  • MachineFunction,没有返回值、没有参数,但是提供了 NoVRegs 标记,是否使用虚拟寄存器,以及指向Function的指针

  • MachineBasicBlock,提供了显式的前驱后继,不要求必须以跳转语句结尾

  • MachineInstr,机器命令更接近汇编,所有的操作数与结果,全都统一成操作数了