初探 LLVM
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 所有概念几乎都可以直接对应到标准的学术界编译原理课程:
总体上 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):回边是导致无拓扑序的罪魁祸首,一般回边意味着循环。如果存在一条边 ,同时 支配 ,那么这是一条回边。
关键边(critical edge):如果存在A、B两个节点,存在边 ,其中 A 有多条出边,B 有多条入边,这条边就是关键边。因为关于该边的优化,会被多个路径限制。
不可规约图(irreducible graph):不可规约图意味着非自然循环,不可规约图循环优化更复杂,容易出错。
可以用迭代的方法判断不可规约图:
如果边 ,其中是的唯一前驱是的后继(理论角度可以不唯一),那么合并两个节点。
如果存在一条自边,那么删掉这个自边。
最后如果图可以规约成一个节点,则是可规约图,否则是不可规约图。
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,机器命令更接近汇编,所有的操作数与结果,全都统一成操作数了