LLVM代码生成

一、简介

编译器代码生成

  • 定义:编译器的最后一个步骤,将前端生成的中间表示(IR)转换为汇编代码或目标机器代码。
  • 输入:前端和代码优化阶段生成的LLVM IR。
  • 输出:汇编代码或目标程序(如.s.o文件)。

关键步骤

  1. 指令选择:将IR指令映射到目标机器的指令集。
  2. 指令调度:优化指令顺序以提高流水线效率。
  3. 寄存器分配:将虚拟寄存器映射到物理寄存器,必要时使用内存存储。

相关概念

  • 基本块:控制流只能从其第一个指令进入,从最后一个指令离开,除最后一个指令外不存在分支指令。
  • 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需要实现的内容,如目标机器的指令集、寄存器等。

后端任务

  1. 构造SelectionDAG:将llvm IR转换为目标机器的指令集,变为以目标指令表示的DAG。产生目标指令集程序所需的初始代码,使用虚拟寄存器和由于特殊约束而提前分配的物理寄存器。
  2. 指令调度:根据上一阶段产生的DAG,规划指令的顺序。经过此步骤后指令间关系由DAG变为线性。
  3. 基于SSA机器代码优化一系列基于SSA的代码优化。如模调度,窥视孔优化等。
  4. 寄存器分配:将虚拟寄存器映射到物理寄存器。将无法完全存入寄存器的变量移入主存。
  5. 添加函数头尾代码:如栈帧设置和清理。在这一步实现了帧指针消除,堆栈打包等优化。
  6. 目标特定优化:一些最终阶段的优化,运行目标特定的Pass。
  7. 代码生成:生成汇编或对象文件。

二、指令选择

MIR/MI

  • 定义:从这一阶段开始,大部分Pass不再在LLVM IR上运行,而是在MIR(Machine IR)上运行。
  • 特点:MIR是依赖于目标的指令表示,比LLVM IR更低层。它仍可以包含对虚拟寄存器的引用,因此还不是纯CPU指令。

DAG指令选择

  • 目标:将IR程序映射成可以在目标机器上运行的代码序列。
  • 过程:LLVM将IR转换为SelectionDAG,然后通过模式匹配将DAG节点转换为目标机器指令。

步骤

  1. 构建DAG:将IR转换为DAG结构。
  2. 优化DAG:通过合并和简化节点优化DAG。
  3. 类型合法化:确保所有类型在目标机器上有效。
  4. 操作合法化:确保所有操作在目标机器上有效。
  5. 指令选择:通过模式匹配将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提供三种不同的指令选择方法:

  1. 选择DAG:标准方法,适用于大多数情况。
  2. 快速指令选择(FastISel):适用于-O0优化级别,优先考虑速度而非代码质量。使用llc -fast-isel参数。
  3. 全局指令选择(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文件),默认生成汇编文件,也可以生成对象文件。