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文件），默认生成汇编文件，也可以生成对象文件。