LLVM代码生成
一、简介
编译器代码生成
- 定义:编译器的最后一个步骤,将前端生成的中间表示(IR)转换为汇编代码或目标机器代码。
- 输入:前端和代码优化阶段生成的LLVM IR。
- 输出:汇编代码或目标程序(如
.s
或.o
文件)。
关键步骤
- 指令选择:将IR指令映射到目标机器的指令集。
- 指令调度:优化指令顺序以提高流水线效率。
- 寄存器分配:将虚拟寄存器映射到物理寄存器,必要时使用内存存储。
相关概念
- 基本块:控制流只能从其第一个指令进入,从最后一个指令离开,除最后一个指令外不存在分支指令。
- CFG(控制流图):Function的图形化表示,结点是基本块,边显示了控制流如何在基本块之间流动。
- DAG(有向无环图):基本块的图形化表示,结点是指令(不一定一一对应,指令类型可变),每个DAG都能够表示单个基本块的计算。
LLVM相关概念
- LLVM IR:中间表示,是前端和后端之间的桥梁。
- SelectionDAG:指令选择的有向无环图,用于将IR转换为目标机器指令。
- SDNode:SelectionDAG的节点,表示指令或数据。
LLVM后端
- 输入:LLVM IR。
- 输出:汇编或者对象文件。
- 作用:The LLVM IR is the middle point between the frontend and backend.
后端代码架构
llvm/lib/CodeGen
:通用算法的头文件和实现。llvm/lib/MC
:(反)汇编、对象文件相关。llvm/lib/TableGen
:TableGen工具实现,用于生成目标机器描述。llvm/lib/Target
:target-specific需要实现的内容,如目标机器的指令集、寄存器等。
后端任务
- 构造SelectionDAG:将llvm IR转换为目标机器的指令集,变为以目标指令表示的DAG。产生目标指令集程序所需的初始代码,使用虚拟寄存器和由于特殊约束而提前分配的物理寄存器。
- 指令调度:根据上一阶段产生的DAG,规划指令的顺序。经过此步骤后指令间关系由DAG变为线性。
- 基于SSA机器代码优化一系列基于SSA的代码优化。如模调度,窥视孔优化等。
- 寄存器分配:将虚拟寄存器映射到物理寄存器。将无法完全存入寄存器的变量移入主存。
- 添加函数头尾代码:如栈帧设置和清理。在这一步实现了帧指针消除,堆栈打包等优化。
- 目标特定优化:一些最终阶段的优化,运行目标特定的Pass。
- 代码生成:生成汇编或对象文件。
二、指令选择
MIR/MI
- 定义:从这一阶段开始,大部分Pass不再在LLVM IR上运行,而是在MIR(Machine IR)上运行。
- 特点:MIR是依赖于目标的指令表示,比LLVM IR更低层。它仍可以包含对虚拟寄存器的引用,因此还不是纯CPU指令。
DAG指令选择
- 目标:将IR程序映射成可以在目标机器上运行的代码序列。
- 过程:LLVM将IR转换为SelectionDAG,然后通过模式匹配将DAG节点转换为目标机器指令。
步骤
- 构建DAG:将IR转换为DAG结构。
- 优化DAG:通过合并和简化节点优化DAG。
- 类型合法化:确保所有类型在目标机器上有效。
- 操作合法化:确保所有操作在目标机器上有效。
- 指令选择:通过模式匹配将DAG节点转换为目标指令。
目标描述
- 定义:描述目标机器的指令集、寄存器、数据类型等信息。
- 来源:
.td
文件(TableGen文件)。 - 位置:
llvm/lib/Target
对应目录中。 - 作用:DAG指令选择使用目标描述中提供的模式匹配,并使用自定义代码,将IR指令转换为机器指令。
其他目标描述
- 数据类型支持:目标机器支持的数据类型。
- 操作支持:目标机器支持的操作。
- 实现方式:通过
TargetLowering
接口实现。
IR到SelectionDAG nodes (SDNode)
- 目的:将IR指令转换为更易处理的DAG节点。
基本块的DAG表示
- 结点类型:
- 值类型:表示整数、浮点数、向量或指针的具体值类型。
- Other类型:用于表示链值的抽象标记。
- Glue:表示glues,其连接的两个结点必须被粘在一起。
- 边类型:
- 黑色箭头:表示数据流(use-def关系)。
- 蓝色虚线箭头:标记控制流的链。
- 红色箭头:将节点粘在一起,防止它们重新排序。
构建完成后
- 结果:从IR得到了对应于IR的DAG。
- 目标:要得到特定于目标的SelectionDAG节点。
Lowering
- 定义:将高层节点转换为更接近目标机器的节点。
- 实现:
TargetLowering
类是一个抽象接口,每个target必须实现。
DAG combine and legalization
- DAG combine:在每次legalization之后运行,优化DAG以减少冗余。
- Legalization:确保所有类型和操作在目标机器上有效。
- 优化示例:
add (Register X), (constant 0)
可以被替换为Register X
。
Legalization
- 类型合法化:确保所有类型在目标机器上有效。
- 向量合法化:处理不被支持的向量操作。
- DAG合法化:处理其他无法直接转换的节点。
DAG-to-DAG instruction selection
- 模式匹配:通过模式匹配将独立于目标的节点转换为特定于目标的节点。
- 实现:每个后端通过实现
SelectDAGISel
的子类<Target_Name>DAGToDAGISel
中的Select
方法来处理指令选择。
LLVM的指令选择方法
LLVM提供三种不同的指令选择方法:
- 选择DAG:标准方法,适用于大多数情况。
- 快速指令选择(FastISel):适用于
-O0
优化级别,优先考虑速度而非代码质量。使用llc -fast-isel
参数。 - 全局指令选择(GlobalISel):旨在取代FastISel和选择DAG,平衡速度和代码质量。使用
llc -global-isel
参数。
三、指令调度与寄存器分配
指令调度的原因
- 流水线优化:通过对指令的调度,使程序尽可能地流水线化以提高性能。
- 限制因素:
- 控制依赖约束:指令执行顺序受控制流影响。
- 数据依赖约束:
- 依赖:写->读。
- 反依赖:读->写。
- 输出依赖:写->写。
- 资源约束:目标机器的硬件资源限制。
SUnit
- 定义:调度单元,表示特定于目标的SelectionDAG节点或MachineInstrs。
- 输出:生成的MachineInstr序列。
- 实现:通过
ScheduleDAGSDNodes
的子类实现。
pre-RA-sched
- 参数:
--pre-RA-sched=<value>
,指定在寄存器分配前的调度器。 - 可用调度器:
vliw-td
:VLIW调度器。list-ilp
:平衡ILP和寄存器压力的列表调度。list-hybrid
:平衡延迟和寄存器压力的列表调度。source
:尽可能按源代码顺序调度。list-burr
:减少寄存器使用的列表调度。linearize
:线性化DAG,不进行调度。fast
:快速但次优的列表调度。default
:目标的最佳调度器。
Machine instruction scheduler to use
- 参数:
--misched=<value>
,指定机器指令调度器。 - 可用调度器:
default
:使用目标的默认调度器。converge
:标准收敛调度器。ilpmax
:最大化ILP的自底向上调度。ilpmin
:最小化ILP的自底向上调度。shuffle
:交替方向的指令洗牌。
Instruction itineraries指令行程
- 定义:指令调度需要后端提供的信息,包括指令延迟和硬件管道信息。
- 存储位置:TableGen文件中
<Target>Schedule.td
。
ProcessorItineraries
- 定义:通过TableGen类
ProcessorItineraries
定义芯片或处理器系列的处理器行程。
Hazard detection
- 定义:检测指令调度中的潜在冲突。
- 实现:通过
ScheduleHazardRecognizer
接口。
寄存器分配
- 定义:将无限数量的虚拟寄存器转换为有限的物理寄存器。
- 任务:解构IR的SSA形式,并将虚拟寄存器映射到物理寄存器。
寄存器分配选项
- 图着色算法:基于图着色的寄存器分配算法(龙书)。
- PBQP:Partitioned Boolean Quadratic Programming,使用PBQP求解器将结果映射回寄存器。
- Greedy:高效的全局寄存器分配算法,支持实时范围拆分,减少溢出。
- Basic:最简单的寄存器分配算法。
- Fast:通过保留值在寄存器中并重用它们来提速。
寄存器分配依赖的其他Pass
- 存活变量分析:获取变量的def-use信息,判断寄存器之间的干扰。
Register coalesce
- 定义:如果有从寄存器到寄存器的拷贝,尝试使其使用同一个寄存器,删除冗余复制指令。
- 实现:通过
lib/CodeGen/RegisterCoalescer.cpp
实现。 - 目标钩子:在合并期间,虚拟寄存器需要来自兼容的寄存器类才能成功合并。
Virtual register rewrite
- 定义:将虚拟寄存器引用替换为物理寄存器引用。
- 实现:通过
VirtRegMap
保存寄存器分配结果。 - 处理:生成溢出代码,处理低级错误。
寄存器分配与指令调度的冲突关系
- 寄存器分配:希望把对同一个寄存器的使用放在一起,减少虚拟寄存器间的冲突。
- 指令调度:希望把不存在依赖关系的指令放在一起,实现高效的流水线。
四、其他
Prologue and epilogue
- 定义:函数需要prologue和epilogue才能完成。
- Prologue:在函数开始时设置栈帧和被调用方保存的寄存器。
- Epilogue:在函数返回之前清理堆栈帧。
- 实现:目标特定,定义在
<Target>FrameLowering::emitPrologue()
和<Target>FrameLowering::emitEpilogue()
方法中。
Code Emission
- 定义:将MachineInstr转换为MCInstr,生成最终的汇编或对象文件。
- MC指令:
- 定义在
include/llvm/MC/MCInst.h
中。 - 是指令的轻量级表示形式,用于汇编器和反汇编器。
- 携带的程序相关信息较少,保证其可以被反汇编器创建。
- 定义在
LLVM后端工具使用
- 工具:
llc
,输入是LLVM中间代码(.ll
或.bc
文件),默认生成汇编文件,也可以生成对象文件。