您的位置: 首页  >  文章  >  LLVM:The LLVM Target-Independent Code Generator

LLVM:The LLVM Target-Independent Code Generator

分类: 文章 • 2024-10-10 15:43:22

https://llvm.org/docs/CodeGenerator.html

 

 

目标无关代码生成器

  • Introduction
    • 六大部分
      • 抽象目标描述接口 include/llvm/target/
      • 机器码表示类 include/llvm/CodeGen/:处理常量/跳转表/全局遍历等
        • LLVM代码被翻译成由MachineFunction、MachineBasicBlock和MachineInstr实例
        • 格式：一个操作码和一系列操作数
      • MC Layer：处理标签/段/机器指令等
        • 输出.s 和elf格式的.o
        • 独立的汇编器和反汇编器
      • 目标无关算法 lib/CodeGen/:目标代码生成（寄存器分配，指令调度，栈帧表示...）
      • 实现特定目标描述接口 lib/Target/
      • 目标无关JIT部分 lib/ExecutionEngine/JIT
    • Required components in the code generator
      • 代码生成器的高级接口
      • 可用于构建特定目标后端的可重用组件集
      • 需要为后端定义两个最重要的接口(TargetMachine和DataLayout)
    • The high-level design of the code generator
      • 指令选择阶段：llvm code->DAG
      • 调度和形成阶段：决定指令顺序+输出指令为MachineInstrs
      • 基于ssa的机器码优化
      • 寄存器分配：SSA形式的虚拟寄存器->目标使用的实际物理寄存器
      • prolog/epilog 代码插入：每个函数开头和结尾都得进行对应操作
      • 后期机器码优化
      • 代码发射：输出汇编格式/目标指令格式/JIT-机器码
    • Using TableGen for target description
      • 架构描述语言ADL：*.td
  • Target description classes
    • The TargetMachine class
      • getInstrInfo/getSubtargetImpl/getSelectionDAGInfo/getDataLayout/getFrameLowering/getRegisterInfo/getTargetLowering/getInstrItineraryData
    • The DataLayout class
      • 惟一需要的目标描述类，也是惟一不可扩展的类(您不能从中派生新类)
      • 如何为结构布局内存、各种数据类型的对齐需求、目标中指针的大小以及目标是小端字节还是大端字节
    • The TargetLowering class
      • 描述如何从llvm code lowering到SelectionDAG：指令选择阶段的SelectionDAG调用
      • 用于各种valuetype的初始寄存器类
      • 目标机器本身支持哪些操作
      • setcc操作的返回类型
      • 用于移位数量的类型
      • 各种高级特性，比如将一个常数的除法转换成乘法序列是否有利
    • The TargetRegisterInfo class
      • 无符号整型表示，Reg0是个标识值，物理寄存器一般是唯一的较小数，而虚拟寄存器一般是较大的数值
      • TargetRegisterDesc ：文本名称（汇编输出/debug输出）+别名（检查是否重叠）
    • The TargetInstrInfo class
      • 操作码的助记符、操作数的数量、隐式寄存器使用的列表和defs、指令是否具有特定的与目标无关的属性(访问内存、可交换等)以及持有任何特定于目标的标志
    • The TargetFrameLowering class
      • 堆栈增长的方向、每个函数入口的已知堆栈对齐方式以及到局部区域的偏移量。到局部区域的偏移量是函数入口的堆栈指针到第一个可以存储函数数据(局部变量、溢出位置)的位置的偏移量
    • The TargetSubtarget class
      • 支持哪些指令、指令延迟和指令执行过程/槽，使用哪个处理单元，以什么顺序，使用多长时间。
    • The TargetJITInfo class
      •  getJITInfo
  • Machine code description classes

格式：一个操作码序号+一个MachineOperand指针+指令描述

操作数MachineOperand：一堆类型MO_寄存器/立即数...

指令描述MCInstrDesc：各种标志位表示是否访存/返回/延迟槽/分支指令/调用指令/伪指令...

TargetInstrInfo.td->自动生成对应的操作码序号

TargetInstrInfo.cpp->指令信息

操作数类型：寄存器/常量/机器基本块/...引用

操作数排序：目的操作数会被排在第一个，即使目标指令格式dst操作数在最后一个

BuildMI方法：在机器基本块的任意位置创建任意指令

LLVM:The LLVM Target-Independent Code Generator

 

固定/预先指定/专用的寄存器，比如只用于除法的寄存器，只用于函数返回值的寄存器等

物理寄存器的生命周期要尽量短，控制在一个机器基本块内，一旦某个寄存器需要跨过机器基本块间传输，必须使用虚拟寄存器

发生调用会破坏很多物理寄存器

不添加<def,dead>操作数，而是添加MO_RegisterMask操作数

MI一开始是SSA格式的，直到寄存器分配阶段过后就不是SSA格式了，因为虚拟寄存器不存在了

    • The MachineBasicBlock class
      • 包含一个以MI为元素的链表
      • 一个LLVM基本块（BB)可能对应多个机器基本块（MBB)
    • The MachineFunction class
      • 包含一个以MBB为元素的链表
      • 一个LLVM基本块和一个MF一一对应，
    • MachineInstr Bundles
      • 一个MI Bundles对应一个VLIW包
      • 组成：一个含有Bundles标志的MI+其他含有InsideBundle标志MIs

MI->isBundle()+多个MI->isInsideBundle()

LLVM:The LLVM Target-Independent Code Generator

 

      • 迭代器遍历

typedef  Instructions::iterator instr_iterator;  //遍历机器基本块内每一条指令，包含bundles和insidebundle标志的指令

typedef  bundle_iterator<MachineInstr,instr_iterator> iterator;以bundles标志的MI为单位遍历指令  

      • 打包和绑定包必须在寄存器分配阶段过后进行
  • The “MC” Layer
    • The MCStreamer API
      • 输出.s/.o的API：MCAsmStreamer+MCObjectStreamer
      • EmitInstruction ，EmitLabel，EmitSymbolAttribute，SwitchSection，EmitValue
      • MCTargetStreamer
    • The MCContext class
      • 不能被子类实例化，MC层唯一各种数据结构的拥有者
      • 创建/拥有MCSymbol
      • 创建/拥有MCSection
    • The MCSymbol class
      • 符号/标签
      • 汇编临时符号（通过加前缀作为标记，在发射汇编文件时丢弃）和普通符号
      • 指针对比相同则相同符号/地址，指针不同不能保证符号/地址不同
    • The MCSection class
      • 节/段
      • MCSectionMachO，MCSectionCOFF，MCSectionELF
      • SwitchToSection ：对应.s中的“.section”
    • The MCInst class
      • 比MI更简单的格式：一个操作码+一个MCOperand向量
      • MCOperand是一个union{寄存器，立即数，浮点立即数，重定位立即数，Sub-instruction操作数}
      • 汇编和反汇编阶段生成MCInst，指令编码器和指令打印器使用MCInst
  • Target-independent code generation algorithms

Directed-Acyclic-Graph：有向无环图

SDNode类的实例：include/llvm/CodeGen/ISDOpcodes.h

value/edge:

数据流：int float...

控制流：MVT(Machine Value Type)::Other / side effects:加载/存储/调用/返回

“Entry” and “Root” nodes：ISD::EntryToken+最后一个副作用节点

      • SelectionDAG Instruction Selection Process
          • 构建初始DAG：llvm code->简单的非法DAG
          • 优化SelectionDAG：进一步简化最初的DAG
          • 合法化SelectionDAG类型
          • 优化SelectionDAG：去除合法化类型阶段的冗余
          • 合法化SelectionDAG操作
          • 优化SelectionDAG：去除合法化操作阶段的低效
          • 从DAG选择指令/匹配DAG和目标指令/从目标无关的DAG转换为目标相关的DAG：模式匹配
          • SelectionDAG调度和形成（prepass调度技术）：对目标相关DAG指令排序+发送到Machine Function

-view-dag-combine1-dags 第一个优化前

-view-legalize-dags 合法化类型前

-view-dag-combine2-dags 第二个优化前

-view-isel-dags 选择指令前

-view-sched-dags 调度指令前

1 目标无关DAG：(fadd:f32 (fmul:f32 (fadd:f32 W, X), Y), Z)

%t1 = fadd float %W, %X

%t2 = fmul float %t1, %Y

%t3 = fadd float %t2, %Z

2 目标相关DAG:(FMADDS (FADDS W, X), Y, Z)

def FMADDS : AForm_1<59, 29, (ops F4RC:$FRT, F4RC:$FRA, F4RC:$FRC, F4RC:$FRB),

"fmadds $FRT, $FRA, $FRC, $FRB",

[(set F4RC:$FRT, (fadd (fmul F4RC:$FRA, F4RC:$FRC),F4RC:$FRB))]>;//模式匹配

def FADDS : AForm_2<59, 21,(ops F4RC:$FRT, F4RC:$FRA, F4RC:$FRB),

"fadds $FRT, $FRA, $FRB",

[(set F4RC:$FRT, (fadd F4RC:$FRA, F4RC:$FRB))]>;

3 td文件里面定义模式匹配的好处

3.1 编译器编译时就能告诉你这些模式匹配有没有意义

3.2 模式匹配中的操作数可以添加任意限制，比如13bit的有符号扩展数据类型

3.3 模式匹配直到几个重要的规则而不需要人工添加，比如可交换规则，规定了fadd指令可交换，则(fadd X, (fmul Y, Z))会自动识别等效于(fadd (fmul X, Y), Z)

3.4 不需要人工特意指令寄存器类型，比如i8/i16/i32/f64/v4i32等，只要指令数据类型所属类即可，比如F4RC

3.5 可以自己定义模式匹配片段（pattern fragments），比如内置的(not x)用(xor x, -1)代替

3.6 Pat模式匹配

3.7 ComplexPattern模式匹配复杂的操作数，比如寻址类的操作数

4 不足

4.1 无法匹配定义了多个值的SelectionDAG，比如SMUL_LOHI, LOAD, CALL，这是我们要为指令选择器编写自定义的代码的最主要原因

4.2 没有很好的模式匹配复杂寻址模式

4.3  isStore/isLoad等标志无法自动推断

4.4 无法为合法化阶段自动生成合法的类型和操作

4.5无法绑定自定义的合法节点

变量的存活期：在寄存器分配阶段，需要相同物理寄存器的两个或多个虚拟寄存器是否位于程序的同一点，是则一个虚拟寄存器必须溢出/spilled

      • Live Variable Analysis
          • 计算在指令之后立即死亡的寄存器集
          • 跟踪计算虚拟寄存器（SSA形式）和物理寄存器（单个基本块），不是寄存器可分配的不追踪，比如栈指针，条件代码
          • 物理寄存器
            • live in属性：函数参数;标记一个“defining” instruction;在每个基本块结束前被杀死
            • live out属性：函数返回值
          • PHI节点特殊处理：当前基本块的下一个基本块的一个PHI节点的一个操作数来自当前基本块的这个PHI，则这个变量在当前基本块以及所有前置基本块设置为alive状态，直到遇到defining instruction
      • Live Intervals Analysis
    • Register Allocation

无限虚拟寄存器的程序转换为有限物理寄存器的程序，物理寄存器不够用则虚拟寄存器映射到内存/堆栈槽，称为虚拟溢出

aliased ；别名；TargegtRegisterInfo.td;class MCRegAliasIterator；MachineOperand::getReg()

          • 不存在不同名同编号虚拟寄存器

虚拟寄存器必须映射到可兼容/同类的物理寄存器：比如同位宽标量寄存器/同维度向量寄存器；用RegMapping_Fer::compatible_class函数检查是否兼容

          • 更改物理寄存器数量
            • 简单：TargetRegisterInfo.td注释掉某些寄存器
            • 更好：显示地在寄存器分配顺序中排序某些寄存器
          • pre-colored预着色寄存器：寄存器分配阶段前的物理寄存器
            • 显式explicitly物理寄存器：td文件为每个寄存器静态定义
            • 隐式implicitly 物理寄存器：编译时定义/确定使用
              • TargetInstrInfo::get(opcode)::ImplicitDefs
              • TargetInstrInfo::get(opcode)::ImplicitUses
          • 其他

for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i)

unsigned VirtReg = TargetRegisterInfo::index2VirtReg(i);

MachineOperand::isRegister()

MachineOperand::isUse()这个寄存器是否被这个指令使用

MachineOperand::isDef()这个寄存器是否正在被这条指令定义

      • Mapping virtual registers to physical registers
          • 直接映射：classes TargetRegisterInfo, MachineOperand;灵活易错
            • MachineOperand::setReg(p_reg)：§虚拟->物理
            • TargetInstrInfo::storeRegToStackSlot(...)：插入一条存储指令，虚拟->内存
            • TargetInstrInfo::loadRegFromStackSlot(.)：插入一条加载指令，内存->虚拟
          • 间接映射：VirtRegMap ；避免插入加载/存储指令
            • VirtRegMap::assignVirt2Phys(vreg, preg)：虚拟->物理
            • VirtRegMap::assignVirt2StackSlot(vreg)：虚拟->堆栈槽，依旧需要映射到一个物理寄存器，这个物理寄存器位置是这个虚拟寄存器存储之前，加载之后的位置
            • 使用了spiller对象，自动插入加载/存储指令；

RegAllocLinearScan::runOnMachineFunction in lib/CodeGen/RegAllocLinearScan.cpp

      • Handling two address instructions
          • 除特殊指令（调用等）外，llvm的机器指令都是三地址指令，其中最多一个def寄存器(out/dst),最多两个use寄存器（input/source)，例如add a b c/a=add b c
          • TwoAddressInstructionPass :转化为两地址指令
            • mov a b/a=b; add a c/a=add a c;
            • a既是use又是def寄存器
            • 寄存器分配阶段之前转换，转换后不再是SSA形式
      • The SSA deconstruction phase
          • SSA解构阶段：PHI节点解构算法，利用复制指令替换PHI指令
          • lib/CodeGen/PHIElimination.cpp
          • 标识符PHIEliminationID
      • Instruction folding
          • 折叠指令优化：移除不必要的复制指令，比如load a addr;mov c a;->load c addr;
          • TargetRegisterInfo::foldMemoryOperand(...)
      • Built in register allocators
          • 寄存器分配器种类
            • Fast ：调试默认分配器，基本块级别上分配寄存器，试图保留寄存器的值以便重用
            • Basic：增量方法，按序一次分配一个寄存器，独立模式，可扩展
            • Greedy：默认分配器，Basic分配器的一个高度调优版本，将溢出代码的成本降到最低
            • A Partitioned Boolean Quadratic Programming (PBQP)：PBQP问题，PBQP求解器
          • llc对应参数
            • -regalloc=linearscan
            • -regalloc=fast
            • regalloc=pbqp
    • Prolog/Epilog Code Insertion
        • Frame Description Entry (FDE)：一个函数需要20~30字节信息
        • unwind编码方法：compact unwind，一个函数需要4字节信息
    • Late Machine Code Optimizations
    • Code Emission

1 TargetAsmPrinter+TargetLoweringObjectFile:MF信息->MC 信息;elf,coff,MachO

2 TargetMCInstLower.cpp:MachineInstr->MCInst

3 汇编打印器-MCStreamer：MCInst->汇编字符串；支持.s文件生成

4 TargetMCCodeEmitter.cpp：MCInst->机器字节码/二进制；支持.o文件生成+汇编器+反汇编

      • Emitting function stack size information
          • TargetLoweringObjectFile::StackSizesSection非空
          • TargetOptions::EmitStackSizeSection 已设置
          • 发射一个段section:vector<pair<函数符号值（指针大小），栈大小>>,栈大小只包含在prolog阶段分配的大小，不含动态分配大小
    • VLIW Packetizer

packets or bundles;目标无关

MatchInstructionImpl(...)：别名处理和实际映射，简单->复杂顺序

require子句，以使它们具有特定于子目标的特性。

 

其他

1 JIT即时编译：高级语言java->机器码，不需经过中间代码（字节码）

2 后端的六大部分

Target description classes: abstract target description interfaces (代码地址：include/llvm/Target/)

Marchine code description classes: classes used to repesent the code being generated for a target (代码地址：include/llvm/CodeGen/)

The "MC" Layer: use to represent and process code at the raw machine code level(代码地址：lib/MC include/llvm/MC)

Target-independent code generation algorithms (代码地址：lib/CodeGen)

Implementations of the abstract description interfaces for particular targets (代码地址： lib/Target)

The target-independent JIT components (代码地址：lib/ExecutionEngine/JIT)

3 后端的七大环节

Instruction Selection

Scheduling and Formation

SSA-based Machine Code Optimizations

Register Allocation

Prolog/Epilog Code Insertion

Late Machine Code Optimizations

Code Emission

4 LLVM使用SelectionDAG来表示LLVM IR指令

5 Prolog/Epilog Code：初构/终解代码，/'ɛpə,lɔg/

Prolog&Epilog 其实就是两段固定的代码， 当编译器对程序进行编译的时候就会生成这两段代码， 然后编译器会在每一个函数的开头塞入Prolog代码，在每一个函数的结尾塞入 Epilog代码。 你可以把Prolog看成是一段程序的前言，把Epilog看成是一段程序的尾言。

 

相关推荐