LLVM 目标无关代码生成器

警告

这是一个正在进行中的工作。

简介

LLVM 目标无关代码生成器是一个框架,它提供了一套可重用的组件,用于将 LLVM 内部表示转换为指定目标的机器代码——以汇编形式(适用于静态编译器)或二进制机器代码格式(适用于 JIT 编译器)。LLVM 目标无关代码生成器由六个主要组件组成

  1. 抽象目标描述接口,用于捕获机器各个方面的重要属性,而与其使用方式无关。这些接口在 include/llvm/Target/ 中定义。

  2. 用于表示为目标生成的代码的类。这些类旨在足够抽象,以表示任何目标机器的机器代码。这些类在 include/llvm/CodeGen/ 中定义。在这个级别,诸如“常量池条目”和“跳转表”之类的概念被显式公开。

  3. 用于表示对象文件级别代码的类和算法,MC 层。这些类表示汇编级别的构造,如标签、节和指令。在这个级别,诸如“常量池条目”和“跳转表”之类的概念不存在。

  4. 用于实现本机代码生成各个阶段的目标无关算法(寄存器分配、调度、栈帧表示等)。此代码位于 lib/CodeGen/ 中。

  5. 特定目标的抽象目标描述接口的实现。这些机器描述利用 LLVM 提供的组件,并且可以选择性地提供自定义的目标特定 Pass,以构建特定目标的完整代码生成器。目标描述位于 lib/Target/ 中。

  6. 目标无关的 JIT 组件。LLVM JIT 是完全目标无关的(它使用 TargetJITInfo 结构来处理目标特定的问题)。目标无关 JIT 的代码位于 lib/ExecutionEngine/JIT 中。

根据您感兴趣的代码生成器的部分,这些部分对您会有不同的用处。在任何情况下,您都应该熟悉目标描述机器代码表示类。如果您想为新目标添加后端,您将需要为您新目标实现目标描述类,并理解LLVM 代码表示。如果您有兴趣实现新的代码生成算法,它应该只依赖于目标描述和机器代码表示类,以确保其可移植性。

代码生成器中所需的组件

LLVM 代码生成器的两个部分是代码生成器的高级接口和可用于构建目标特定后端的重用组件集。两个最重要的接口 ( TargetMachine DataLayout ) 是后端融入 LLVM 系统唯一需要定义的接口,但如果要使用可重用代码生成器组件,则必须定义其他接口。

这种设计有两个重要的含义。第一个是 LLVM 可以支持完全非传统的代码生成目标。例如,C 后端不需要寄存器分配、指令选择或系统提供的任何其他标准组件。因此,它仅实现了这两个接口,并自行处理。请注意,C 后端已从 LLVM 3.1 版本后的主干中移除。这种代码生成器的另一个例子是将 LLVM 转换为 GCC RTL 形式并使用 GCC 为目标发出机器代码的(纯粹假设的)后端。

这种设计也意味着可以在 LLVM 系统中设计和实现完全不同的代码生成器,而无需使用任何内置组件。完全不建议这样做,但对于与 LLVM 机器描述模型不符的完全不同的目标(例如 FPGA)可能是必需的。

代码生成器的高级设计

LLVM 目标无关代码生成器旨在支持标准基于寄存器的微处理器的高效和高质量代码生成。此模型中的代码生成分为以下阶段

  1. 指令选择 — 此阶段确定在目标指令集中表达输入 LLVM 代码的有效方法。此阶段生成程序在目标指令集中的初始代码,然后利用 SSA 形式的虚拟寄存器和物理寄存器,这些物理寄存器表示由于目标约束或调用约定而需要的任何寄存器分配。此步骤将 LLVM 代码转换为目标指令的 DAG。

  2. 调度和形成 — 此阶段采用指令选择阶段生成的目标指令 DAG,确定指令的顺序,然后以该顺序发出指令作为 MachineInstrs 。请注意,我们在指令选择部分中描述了这一点,因为它在 SelectionDAG 上运行。

  3. 基于 SSA 的机器代码优化 — 此可选阶段由一系列机器代码优化组成,这些优化在指令选择器生成的 SSA 形式上运行。模调度或窥孔优化等优化在此处工作。

  4. 寄存器分配 — 目标代码从 SSA 形式的无限虚拟寄存器文件转换为目标使用的具体寄存器文件。此阶段引入溢出代码并消除程序中的所有虚拟寄存器引用。

  5. Prolog/Epilog 代码插入 — 一旦为函数生成了机器代码,并且已知所需的栈空间量(用于 LLVM alloca 和溢出槽),就可以插入函数的 prolog 和 epilog 代码,并消除“抽象栈位置引用”。此阶段负责实现诸如帧指针消除和栈打包之类的优化。

  6. 后期机器代码优化 — 在“最终”机器代码上运行的优化可以放在此处,例如溢出代码调度和窥孔优化。

  7. 代码发射 — 最终阶段实际上输出当前函数的代码,以目标汇编器格式或机器代码格式。

代码生成器基于以下假设:指令选择器将使用最佳模式匹配选择器来创建高质量的本机指令序列。基于模式扩展和激进迭代窥孔优化的替代代码生成器设计速度要慢得多。这种设计允许高效编译(对于 JIT 环境很重要)和激进优化(在离线生成代码时使用),方法是允许将不同复杂程度的组件用于编译的任何步骤。

除了这些阶段之外,目标实现还可以将任意目标特定的 Pass 插入到流程中。例如,X86 目标使用特殊的 Pass 来处理 80x87 浮点栈架构。具有不寻常要求的其他目标可以通过自定义 Pass 来支持,如需要。

使用 TableGen 进行目标描述

目标描述类需要目标架构的详细描述。这些目标描述通常具有大量公共信息(例如,add 指令几乎与 sub 指令相同)。为了允许最大程度地分解公共性,LLVM 代码生成器使用 TableGen 概述 工具来描述目标机器的大块内容,这允许使用特定于域和目标特定的抽象来减少重复量。

随着 LLVM 的持续开发和改进,我们计划将越来越多的目标描述移至 .td 形式。这样做为我们带来了许多优势。最重要的是,它使移植 LLVM 变得更容易,因为它减少了必须编写的 C++ 代码量,以及在有人可以开始工作之前需要理解的代码生成器的表面积。其次,它使更改事物变得更容易。特别是,如果表和其他所有内容都由 tblgen 发出,我们只需要在一个地方 (tblgen) 进行更改,即可将所有目标更新到新接口。

目标描述类

LLVM 目标描述类(位于 include/llvm/Target 目录中)提供了目标机器的抽象描述,独立于任何特定客户端。这些类旨在捕获目标的抽象属性(例如,它具有的指令和寄存器),并且不包含任何特定代码生成算法片段。

所有目标描述类(除了 DataLayout DataLayout TargetMachine 类)都设计为由具体目标实现子类化,并实现了虚方法。为了访问这些实现,

TargetMachine

类提供了应该由目标实现的访问器,即 get*Info 方法(getInstrInfo, getRegisterInfo, getFrameInfo 等)。此类设计为由具体目标实现(例如,X86TargetMachine)专门化,后者实现了各种虚方法。唯一必需的目标描述类是 DataLayout DataLayout

类,但如果要使用代码生成器组件,则也应实现其他接口。

DataLayout

DataLayout 类是唯一必需的目标描述类,也是唯一不可扩展的类(您不能从中派生新类)。DataLayout 指定有关目标如何为结构体布局内存、各种数据类型的对齐要求、目标中指针的大小以及目标是小端还是大端的信息。

TargetLowering

  • TargetLowering 类主要由基于 SelectionDAG 的指令选择器使用,以描述如何将 LLVM 代码降低为 SelectionDAG 操作。 除此之外,此类还指示

  • 用于各种 ValueType 的初始寄存器类,

  • 目标机器本机支持哪些操作,

  • setcc 操作的返回类型,

  • 用于移位量的类型,以及

各种高级特性,例如将常数除法转换为乘法序列是否有利可图。

TargetRegisterInfo

TargetRegisterInfo 类用于描述目标的寄存器文件以及寄存器之间的任何交互。

寄存器在代码生成器中由无符号整数表示。物理寄存器(目标描述中实际存在的寄存器)是唯一的小数字,虚拟寄存器通常很大。请注意,寄存器 #0 保留为标志值。

处理器描述中的每个寄存器都有一个关联的 TargetRegisterDesc 条目,该条目为寄存器提供文本名称(用于汇编输出和调试转储)和一组别名(用于指示一个寄存器是否与另一个寄存器重叠)。

除了每个寄存器的描述之外,TargetRegisterInfo 类还公开了一组处理器特定的寄存器类(TargetRegisterClass 类的实例)。每个寄存器类都包含具有相同属性的寄存器集(例如,它们都是 32 位整数寄存器)。指令选择器创建的每个 SSA 虚拟寄存器都有一个关联的寄存器类。当寄存器分配器运行时,它会将虚拟寄存器替换为集合中的物理寄存器。

这些类的目标特定实现是从寄存器文件的 TableGen 概述 描述自动生成的。

TargetInstrInfo

TargetInstrInfo 类用于描述目标支持的机器指令。描述定义了诸如操作码的助记符、操作数数量、隐式寄存器使用和定义列表、指令是否具有某些目标无关的属性(访问内存、是否可交换等),并保存任何目标特定的标志。

TargetFrameLowering

TargetFrameLowering 类用于提供有关目标堆栈帧布局的信息。它保存了堆栈增长的方向、每个函数入口处的已知堆栈对齐方式以及局部区域的偏移量。局部区域的偏移量是从函数入口处的堆栈指针到可以存储函数数据(局部变量、溢出位置)的第一个位置的偏移量。

TargetSubtarget

TargetSubtarget 类用于提供有关正在针对的特定芯片组的信息。子目标告知代码生成哪些指令受支持、指令延迟和指令执行行程;即,使用哪些处理单元,以什么顺序以及持续多长时间。

TargetJITInfo

TargetJITInfo 类公开了即时 (JIT) 代码生成器使用的抽象接口,以执行目标特定的活动,例如发出桩。如果 TargetMachine 支持 JIT 代码生成,则它应通过 getJITInfo 方法提供这些对象之一。

机器代码描述类 在高层,LLVM 代码被转换为由 , MachineFunction MachineBasicBlock MachineInstr

实例(在 include/llvm/CodeGen 中定义)构成的机器特定表示。此表示完全是目标无关的,以其最抽象的形式表示指令:操作码和一系列操作数。此表示旨在支持机器代码的 SSA 表示以及寄存器分配的非 SSA 形式。

MachineInstr

目标机器指令表示为 MachineInstr 类的实例。此类是以极其抽象的方式表示机器指令。特别是,它仅跟踪操作码编号和一组操作数。 操作码编号是一个简单的无符号整数,仅对特定后端有意义。目标的所有指令都应在目标的 *InstrInfo.td 文件中定义。操作码枚举值是从此描述自动生成的。MachineInstr 类没有任何关于如何解释指令的信息(即,指令的语义是什么);为此,您必须参考 TargetInstrInfo

类。

机器指令的操作数可以是几种不同的类型:寄存器引用、常量整数、基本块引用等。此外,机器操作数应标记为值的定义或使用(尽管只有寄存器才允许作为定义)。

按照约定,LLVM 代码生成器对指令操作数进行排序,以便所有寄存器定义都在寄存器使用之前,即使在通常以其他顺序打印的架构上也是如此。例如,SPARC add 指令:“add %i1, %i2, %i3” 将 “%i1” 和 “%i2” 寄存器相加,并将结果存储到 “%i3” 寄存器中。在 LLVM 代码生成器中,操作数应存储为 “%i3, %i1, %i2”:目标寄存器在前。

%r3 = add %i1, %i2

将目标(定义)操作数放在操作数列表的开头有几个优点。特别是,调试打印机将像这样打印指令

此外,如果第一个操作数是定义,则更容易创建指令,其唯一的定义是第一个操作数。

使用 MachineInstrBuilder.h 函数

// Create a 'DestReg = mov 42' (rendered in X86 assembly as 'mov DestReg, 42')
// instruction and insert it at the end of the given MachineBasicBlock.
const TargetInstrInfo &TII = ...
MachineBasicBlock &MBB = ...
DebugLoc DL;
MachineInstr *MI = BuildMI(MBB, DL, TII.get(X86::MOV32ri), DestReg).addImm(42);

// Create the same instr, but insert it before a specified iterator point.
MachineBasicBlock::iterator MBBI = ...
BuildMI(MBB, MBBI, DL, TII.get(X86::MOV32ri), DestReg).addImm(42);

// Create a 'cmp Reg, 0' instruction, no destination reg.
MI = BuildMI(MBB, DL, TII.get(X86::CMP32ri8)).addReg(Reg).addImm(42);

// Create an 'sahf' instruction which takes no operands and stores nothing.
MI = BuildMI(MBB, DL, TII.get(X86::SAHF));

// Create a self looping branch instruction.
BuildMI(MBB, DL, TII.get(X86::JNE)).addMBB(&MBB);

机器指令是使用 BuildMI 函数创建的,该函数位于 include/llvm/CodeGen/MachineInstrBuilder.h 文件中。BuildMI 函数使构建任意机器指令变得容易。BuildMI 函数的用法如下所示

MI.addReg(Reg, RegState::Define);

如果您需要添加定义操作数(可选目标寄存器除外),则必须显式将其标记为定义

固定(预分配)寄存器

代码生成器需要注意的一个重要问题是固定寄存器的存在。特别是,在指令流中,寄存器分配器必须安排将特定值放在特定寄存器中。这可能是由于指令集的限制(例如,X86 只能使用 EAX/EDX 寄存器执行 32 位除法),或诸如调用约定之类的外部因素。在任何情况下,指令选择器都应发出代码,以便在需要时将虚拟寄存器复制到物理寄存器或从物理寄存器复制出来。

define i32 @test(i32 %X, i32 %Y) {
  %Z = sdiv i32 %X, %Y
  ret i32 %Z
}

X86 指令选择器可能会为 divret 生成以下机器代码

;; Start of div
%EAX = mov %reg1024           ;; Copy X (in reg1024) into EAX
%reg1027 = sar %reg1024, 31
%EDX = mov %reg1027           ;; Sign extend X into EDX
idiv %reg1025                 ;; Divide by Y (in reg1025)
%reg1026 = mov %EAX           ;; Read the result (Z) out of EAX

;; Start of ret
%EAX = mov %reg1026           ;; 32-bit return value goes in EAX
ret

在代码生成结束时,寄存器分配器将合并寄存器并删除产生的恒等移动,从而生成以下代码

;; X is in EAX, Y is in ECX
mov %EAX, %EDX
sar %EDX, 31
idiv %ECX
ret

这种方法非常通用(如果它可以处理 X86 架构,那么它可以处理任何架构!)并且允许将关于指令流的所有目标特定知识隔离在指令选择器中。请注意,物理寄存器应该具有较短的生命周期,以实现良好的代码生成,并且假定所有物理寄存器在进入和退出基本块时都已失效(在寄存器分配之前)。因此,如果您需要一个值在基本块边界之间保持活动状态,则它必须存在于虚拟寄存器中。

调用-破坏寄存器

某些机器指令(如调用)会破坏大量物理寄存器。与其为所有这些寄存器添加 <def,dead> 操作数,不如使用 MO_RegisterMask 操作数。寄存器掩码操作数保存了被保留寄存器的位掩码,而其他所有寄存器都被视为被该指令破坏。

SSA 形式的机器代码

MachineInstr 最初以 SSA 形式选择,并在寄存器分配发生之前一直保持 SSA 形式。在大多数情况下,这非常简单,因为 LLVM 已经处于 SSA 形式;LLVM PHI 节点变为机器代码 PHI 节点,并且虚拟寄存器只允许有一个定义。

在寄存器分配之后,机器代码不再是 SSA 形式,因为代码中不再有虚拟寄存器。

MachineBasicBlock

MachineBasicBlock 类包含机器指令列表(实例)。它大致对应于指令选择器的 LLVM 代码输入,但可能存在一对多的映射(即,一个 LLVM 基本块可以映射到多个机器基本块)。 MachineBasicBlock 类有一个 “getBasicBlock” 方法,该方法返回它来自的 LLVM 基本块。

MachineFunction

MachineFunction 类包含机器基本块列表( MachineFunction 实例)。它与指令选择器的 LLVM 函数输入一一对应。除了基本块列表之外,MachineFunction 还包含 MachineConstantPoolMachineFrameInfoMachineFunctionInfoMachineRegisterInfo。 有关更多信息,请参阅 include/llvm/CodeGen/MachineFunction.h

MachineInstr Bundles

LLVM 代码生成器可以将指令序列建模为 MachineInstr bundles。 MI bundle 可以对 VLIW 组/包进行建模,其中包含任意数量的并行指令。它也可以用于对不能合法分离的顺序指令列表(可能具有数据依赖性)进行建模(例如,ARM Thumb2 IT 块)。

从概念上讲,MI bundle 是一个 MI,其中嵌套了许多其他 MI

--------------
|   Bundle   | ---------
--------------          \
       |           ----------------
       |           |      MI      |
       |           ----------------
       |                   |
       |           ----------------
       |           |      MI      |
       |           ----------------
       |                   |
       |           ----------------
       |           |      MI      |
       |           ----------------
       |
--------------
|   Bundle   | --------
--------------         \
       |           ----------------
       |           |      MI      |
       |           ----------------
       |                   |
       |           ----------------
       |           |      MI      |
       |           ----------------
       |                   |
       |                  ...
       |
--------------
|   Bundle   | --------
--------------         \
       |
      ...

MI bundle 支持不会更改 MachineBasicBlock 和 MachineInstr 的物理表示。所有 MI(包括顶层和嵌套的 MI)都存储为 MI 的顺序列表。“捆绑”的 MI 标记有 ‘InsideBundle’ 标志。具有特殊 BUNDLE 操作码的顶层 MI 用于表示 bundle 的开始。将 BUNDLE MI 与不是 bundle 内部或不表示 bundle 的单个 MI 混合使用是合法的。

MachineInstr passes 应该将 MI bundle 作为一个单元进行操作。成员方法已被教导正确处理 bundle 和 bundle 内部的 MI。 MachineBasicBlock 迭代器已被修改为跳过捆绑的 MI,以强制执行 bundle-as-a-single-unit 的概念。已向 MachineBasicBlock 添加了备用迭代器 instr_iterator,以允许 passes 迭代 MachineBasicBlock 中的所有 MI,包括嵌套在 bundle 中的 MI。顶层 BUNDLE 指令必须具有正确的寄存器 MachineOperand 集合,这些寄存器 MachineOperand 表示捆绑 MI 的累积输入和输出。

VLIW 架构的 MachineInstrs 的打包/捆绑通常应作为寄存器分配超级 pass 的一部分完成。更具体地说,确定应将哪些 MI 捆绑在一起的 pass 应在代码生成器退出 SSA 形式后完成(即,在 two-address pass、PHI 消除和复制合并之后)。此类 bundle 应在虚拟寄存器被重写为物理寄存器后最终确定(即,添加 BUNDLE MI 以及输入和输出寄存器 MachineOperands)。这消除了向 BUNDLE 指令添加虚拟寄存器操作数的需要,否则会有效地使虚拟寄存器 def 和 use 列表翻倍。Bundle 可以使用虚拟寄存器并在 SSA 形式中形成,但可能不适用于所有用例。

“MC” 层

MC 层用于表示和处理原始机器代码级别的代码,其中没有 “常量池”、“跳转表”、“全局变量” 或任何类似 “高级” 信息。在此级别,LLVM 处理诸如标签名称、机器指令和对象文件中的 sections 之类的事情。此层中的代码用于许多重要目的:代码生成器的尾端使用它来编写 .s 或 .o 文件,llvm-mc 工具也使用它来实现独立的机器代码汇编器和反汇编器。

本节介绍了一些重要的类。还有许多重要的子系统在此层进行交互,它们将在本手册的后面部分进行介绍。

MCStreamer API

MCStreamer 最好的理解方式是将其视为汇编器 API。它是一个抽象 API,以不同的方式实现(例如,输出 .s 文件、输出 ELF .o 文件等),但其 API 直接对应于您在 .s 文件中看到的内容。MCStreamer 每个指令都有一个方法,例如 EmitLabel、EmitSymbolAttribute、switchSection、emitValue(用于 .byte、.word)等,这些方法直接对应于汇编级别的指令。它还有一个 EmitInstruction 方法,用于将 MCInst 输出到 streamer。

此 API 对于两个客户端最重要:llvm-mc 独立汇编器实际上是一个解析器,它解析一行,然后在 MCStreamer 上调用一个方法。在代码生成器中,代码生成器的 代码发射 阶段将更高级别的 LLVM IR 和 Machine* 构造降低到 MC 层,并通过 MCStreamer 发射指令。

在 MCStreamer 的实现方面,有两个主要的实现:一个用于写出 .s 文件 (MCAsmStreamer),另一个用于写出 .o 文件 (MCObjectStreamer)。MCAsmStreamer 是一个直接的实现,它为每个方法打印一个指令(例如,EmitValue -> .byte),但 MCObjectStreamer 实现了完整的汇编器。

对于目标特定的指令,MCStreamer 有一个 MCTargetStreamer 实例。每个需要它的目标都定义一个从它继承的类,并且很像 MCStreamer 本身:它每个指令都有一个方法,并且有两个从它继承的类,一个目标对象 streamer 和一个目标 asm streamer。目标 asm streamer 只是打印它 (emitFnStart -> .fnstart),而对象 streamer 实现它的汇编器逻辑。

为了使 llvm 使用这些类,目标初始化必须调用 TargetRegistry::RegisterAsmStreamer 和 TargetRegistry::RegisterMCObjectStreamer,传递回调来分配相应的目标 streamer 并将其传递给 createAsmStreamer 或适当的对象 streamer 构造函数。

MCContext

MCContext 类是 MC 层中各种唯一数据结构的所有者,包括符号、sections 等。因此,这是您与之交互以创建符号和 sections 的类。此类不能被子类化。

MCSymbol

MCSymbol 类表示汇编文件中的符号(也称为标签)。有两种有趣的符号:汇编器临时符号和普通符号。汇编器临时符号由汇编器使用和处理,但在生成对象文件时会被丢弃。这种区别通常通过向标签添加前缀来表示,例如 “L” 标签是 MachO 中的汇编器临时标签。

MCSymbols 由 MCContext 创建并在其中唯一化。这意味着可以比较 MCSymbols 的指针等价性,以找出它们是否是相同的符号。请注意,指针不等价性并不保证标签最终会出现在不同的地址。输出如下内容到 .s 文件是完全合法的

foo:
bar:
  .byte 4

在这种情况下,foo 和 bar 符号都将具有相同的地址。

MCSection

MCSection 类表示特定于对象文件的 section。它由特定于对象文件的实现(例如,MCSectionMachOMCSectionCOFFMCSectionELF)子类化,这些实现由 MCContext 创建和唯一化。 MCStreamer 具有当前 section 的概念,可以使用 SwitchToSection 方法更改该 section(该方法对应于 .s 文件中的 “.section” 指令)。

MCInst

MCInst 类是指令的目标无关表示。它是一个简单的类(比 MachineInstr 简单得多),它保存一个特定于目标的操作码和一个 MCOperands 向量。MCOperand 反过来是一个简单的可区分联合,包含三种情况:1) 一个简单的立即数,2) 一个目标寄存器 ID,3) 一个符号表达式(例如 “Lfoo-Lbar+42”)作为 MCExpr。

MCInst 是用于在 MC 层表示机器指令的通用货币。它是指令编码器、指令打印机使用的类型,以及汇编解析器和反汇编器生成的类型。

对象文件格式

MC 层的对象写入器支持各种对象格式。由于对象格式的目标特定方面,每个目标仅支持 MC 层支持的格式的子集。大多数目标都支持发射 ELF 对象。其他特定于供应商的对象通常仅在供应商支持的目标上受支持(即,MachO 仅在 Darwin 支持的目标上受支持,而 XCOFF 仅在支持 AIX 的目标上受支持)。此外,某些目标有自己的对象格式(即,DirectX、SPIR-V 和 WebAssembly)。

下表捕获了 LLVM 中对象文件支持的快照

表 104 对象文件格式

格式

支持的目标

COFF

AArch64, ARM, X86

DXContainer

DirectX

ELF

AArch64, AMDGPU, ARM, AVR, BPF, CSKY, Hexagon, Lanai, LoongArch, M86k, MSP430, MIPS, PowerPC, RISCV, SPARC, SystemZ, VE, X86

GOFF

SystemZ

MachO

AArch64, ARM, X86

SPIR-V

SPIRV

WASM

WebAssembly

XCOFF

PowerPC

目标无关的代码生成算法

本节记录了 代码生成器的高级设计 中描述的阶段。它解释了它们的工作原理以及其设计背后的一些原理。

指令选择

指令选择是将呈现给代码生成器的 LLVM 代码转换为特定于目标的机器指令的过程。文献中有几种众所周知的方法可以做到这一点。LLVM 使用基于 SelectionDAG 的指令选择器。

DAG 指令选择器的某些部分是从目标描述 (*.td) 文件生成的。我们的目标是整个指令选择器都从这些 .td 文件生成,尽管目前仍有一些东西需要自定义 C++ 代码。

GlobalISel 是另一个指令选择框架。

SelectionDAGs 简介

SelectionDAG 提供了一种代码表示的抽象,这种抽象适用于使用自动技术(例如,基于动态规划的最优模式匹配选择器)进行指令选择。它也非常适合代码生成的其他阶段;特别是,指令调度(SelectionDAG 在选择后非常接近调度 DAG)。此外,SelectionDAG 提供了一个宿主表示,可以在其中执行各种非常低级(但与目标无关)的 优化;这些优化需要关于目标有效支持的指令的广泛信息。

SelectionDAG 是有向无环图,其节点是 SDNode 类的实例。 SDNode 的主要有效负载是其操作码 (Opcode),它指示节点执行的操作以及操作的操作数。各种操作节点类型在 include/llvm/CodeGen/ISDOpcodes.h 文件的顶部描述。

尽管大多数操作定义单个值,但图中的每个节点都可以定义多个值。例如,组合的 div/rem 操作将同时定义被除数和余数。许多其他情况也需要多个值。每个节点也有一些操作数,这些操作数是到定义所用值的节点的边。由于节点可以定义多个值,因此边由 SDValue 类的实例表示,SDValue 类是一个 <SDNode, unsigned> 对,分别指示正在使用的节点和结果值。 SDNode 生成的每个值都有一个关联的 MVT(机器值类型),指示值的类型。

SelectionDAGs 包含两种不同类型的值:表示数据流的值和表示控制流依赖项的值。数据值是具有整数或浮点值类型的简单边。控制边表示为 “链” 边,其类型为 MVT::Other。这些边在具有副作用的节点(例如加载、存储、调用、返回等)之间提供排序。所有具有副作用的节点都应将令牌链作为输入并生成一个新的令牌链作为输出。按照惯例,令牌链输入始终是操作数 #0,而链结果始终是操作生成的最后一个值。但是,在指令选择之后,机器节点在指令的操作数之后具有其链,并且可以后跟 glue 节点。

SelectionDAG 具有指定的 “Entry” 和 “Root” 节点。Entry 节点始终是操作码为 ISD::EntryToken 的标记节点。Root 节点是令牌链中的最后一个副作用节点。例如,在单个基本块函数中,它将是返回节点。

SelectionDAGs 的一个重要概念是 “合法” 与 “非法” DAG 的概念。目标的合法 DAG 是一个仅使用受支持的操作和受支持类型的 DAG。例如,在 32 位 PowerPC 上,具有 i1、i8、i16 或 i64 类型的值的 DAG 将是非法的,使用 SREM 或 UREM 操作的 DAG 也将是非法的。 合法化类型合法化操作 阶段负责将非法 DAG 转换为合法 DAG。

SelectionDAG 指令选择过程

基于 SelectionDAG 的指令选择包括以下步骤

  1. 构建初始 DAG — 此阶段执行从输入 LLVM 代码到非法 SelectionDAG 的简单转换。

  2. 优化 SelectionDAG — 此阶段对 SelectionDAG 执行简单的优化以简化它,并识别元指令(例如 rotates 和 div/rem 对),以用于支持这些元操作的目标。这使生成代码更有效,并使 从 DAG 中选择指令 阶段(如下)更简单。

  3. 合法化 SelectionDAG 类型 — 此阶段转换 SelectionDAG 节点以消除目标上任何不受支持的类型。

  4. 优化 SelectionDAG — 运行 SelectionDAG 优化器以清理类型合法化暴露的冗余。

  5. 合法化 SelectionDAG 操作 — 此阶段转换 SelectionDAG 节点以消除目标上任何不受支持的操作。

  6. 优化 SelectionDAG — 运行 SelectionDAG 优化器以消除操作合法化引入的低效率。

  7. 从 DAG 中选择指令 — 最后,目标指令选择器将 DAG 操作与目标指令匹配。此过程将目标无关的输入 DAG 转换为另一个目标指令 DAG。

  8. SelectionDAG 调度和形成 — 最后一个阶段为目标指令 DAG 中的指令分配线性顺序,并将它们发射到正在编译的 MachineFunction 中。此步骤使用传统的预先调度技术。

在完成所有这些步骤后,SelectionDAG 将被销毁,并且代码生成的其余 pass 将运行。

调试这些步骤的最常见方法之一是使用 -debug-only=isel,它会在每个步骤之后打印 DAG 以及其他信息(如调试信息)。或者,-debug-only=isel-dump 仅显示 DAG 转储,但可以使用 -filter-print-funcs=<function names> 按函数名称过滤结果。

可视化此处发生的事情的一个好方法是利用一些 LLC 命令行选项。以下选项会弹出一个窗口,在特定时间显示 SelectionDAG(如果您在使用此选项时只收到打印到控制台的错误,则您可能 需要配置您的系统 以添加对其的支持)。

  • -view-dag-combine1-dags 显示构建后、第一次优化 pass 之前的 DAG。

  • -view-legalize-dags 显示 Legalization 之前的 DAG。

  • -view-dag-combine2-dags 显示第二次优化 pass 之前的 DAG。

  • -view-isel-dags 显示 Select 阶段之前的 DAG。

  • -view-sched-dags 显示 Scheduling 之前的 DAG。

-view-sunit-dags 显示 Scheduler 的依赖关系图。此图基于最终的 SelectionDAG,其中必须一起调度的节点捆绑到单个调度单元节点中,并省略了立即操作数和其他与调度无关的节点。

选项 -filter-view-dags 允许选择您感兴趣可视化的基本块的名称,并过滤所有先前的 view-*-dags 选项。

初始 SelectionDAG 构建

初始 SelectionDAG 由 SelectionDAGBuilder 类从 LLVM 输入中天地进行窥孔扩展。此 pass 的目的是尽可能多地向 SelectionDAG 暴露低级、特定于目标的细节。此 pass 大多是硬编码的(例如,LLVM add 变为 SDNode add,而 getelementptr 扩展为明显的算术)。此 pass 需要特定于目标的 hooks 来降低调用、返回、varargs 等。对于这些功能, TargetLowering 接口被使用。

SelectionDAG LegalizeTypes 阶段

Legalize 阶段负责转换 DAG 以仅使用目标原生支持的类型。

将不受支持的标量类型的值转换为受支持类型的值,主要有两种方法:将小类型转换为较大类型(“提升”)以及将大整数类型分解为较小类型(“扩展”)。例如,目标可能要求将所有 f32 值提升为 f64,并将所有 i1/i8/i16 值提升为 i32。同一目标可能要求将所有 i64 值扩展为 i32 值对。这些更改可以根据需要插入符号和零扩展,以确保最终代码的行为与输入相同。

将不受支持的向量类型的值转换为受支持类型的值,主要有两种方法:拆分向量类型,必要时多次拆分,直到找到合法类型,以及通过在末尾添加元素来扩展向量类型,使其四舍五入为合法类型(“加宽”)。如果向量一直拆分到单元素部分,而没有找到受支持的向量类型,则元素将转换为标量(“标量化”)。

目标实现通过在其 TargetLowering 构造函数中调用 addRegisterClass 方法来告知 legalizer 哪些类型受支持(以及为它们使用哪个寄存器类)。

SelectionDAG Legalize 阶段

Legalize 阶段负责转换 DAG 以仅使用目标原生支持的操作。

目标通常具有奇怪的约束,例如并非在每个受支持的数据类型上都支持每个操作(例如,X86 不支持字节条件移动,而 PowerPC 不支持从 16 位内存位置进行符号扩展加载)。Legalize 通过开放编码另一个操作序列来模拟操作(“扩展”),通过将一种类型提升为支持该操作的更大类型(“提升”),或通过使用特定于目标的 hook 来实现合法化(“自定义”),从而处理此问题。

目标实现通过在其 TargetLowering 构造函数中调用 setOperationAction 方法来告知 legalizer 哪些操作不受支持(以及要采取的上述三种操作中的哪一种)。

如果目标具有合法的向量类型,则期望它为使用这些类型的 shufflevector IR 指令的常见形式生成高效的机器代码。这可能需要对从 shufflevector IR 创建的 SelectionDAG 向量操作进行自定义合法化。应处理的 shufflevector 形式包括

  • 向量选择 — 向量的每个元素都从 2 个输入向量的对应元素中选择。此操作在目标汇编中也可能被称为 “blend” 或 “bitwise select”。这种类型的 shuffle 直接映射到 shuffle_vector SelectionDAG 节点。

  • 插入子向量 — 向量放置到从索引 0 开始的较长向量类型中。这种类型的 shuffle 直接映射到 insert_subvector SelectionDAG 节点,其中 index 操作数设置为 0。

  • 提取子向量 — 向量从从索引 0 开始的较长向量类型中拉出。这种类型的 shuffle 直接映射到 extract_subvector SelectionDAG 节点,其中 index 操作数设置为 0。

  • Splat — 向量的所有元素都具有相同的标量元素。此操作在目标汇编中也可能被称为 “broadcast” 或 “duplicate”。 shufflevector IR 指令可能会更改向量长度,因此此操作可能会映射到多个 SelectionDAG 节点,包括 shuffle_vectorconcat_vectorsinsert_subvectorextract_subvector

在 Legalize pass 存在之前,我们要求每个目标 selector 都支持和处理每个运算符和类型,即使它们不是原生支持的。Legalize 阶段的引入允许跨目标共享所有规范化模式,并且使优化规范化代码非常容易,因为它仍然采用 DAG 的形式。

SelectionDAG 优化阶段:DAG Combiner

SelectionDAG 优化阶段在代码生成过程中会多次运行,分别在 DAG 构建完成后立即运行一次,以及在每次合法化之后运行一次。第一次运行此过程允许清理初始代码(例如,执行依赖于了解运算符具有受限类型输入的优化)。后续运行此过程会清理 Legalize 过程生成的混乱代码,这使得 Legalize 过程可以非常简单(它可以专注于使代码合法,而不是专注于生成良好且合法的代码)。

执行的一类重要优化是优化插入的符号扩展和零扩展指令。我们目前使用临时的技术,但未来可能会转向更严谨的技术。以下是一些关于此主题的优秀论文

加宽整数算术
Kevin Redwine 和 Norman Ramsey
国际编译器构造会议 (CC) 2004

有效的符号扩展消除
Motohiro Kawahito、Hideaki Komatsu 和 Toshio Nakatani
ACM SIGPLAN 2002 编程语言设计与实现会议论文集。

SelectionDAG 选择阶段

选择阶段是目标特定代码的大部分,用于指令选择。此阶段以合法的 SelectionDAG 作为输入,将目标支持的指令与此 DAG 进行模式匹配,并生成一个新的目标代码 DAG。例如,考虑以下 LLVM 代码片段

%t1 = fadd float %W, %X
%t2 = fmul float %t1, %Y
%t3 = fadd float %t2, %Z

这段 LLVM 代码对应于一个 SelectionDAG,它基本上看起来像这样

(fadd:f32 (fmul:f32 (fadd:f32 W, X), Y), Z)

如果目标支持浮点乘加 (FMA) 运算,则其中一个加法可以与乘法合并。例如,在 PowerPC 上,指令选择器的输出可能看起来像这样的 DAG

(FMADDS (FADDS W, X), Y, Z)

FMADDS 指令是一个三元指令,它将其前两个操作数相乘并加上第三个操作数(作为单精度浮点数)。FADDS 指令是一个简单的二元单精度加法指令。为了执行此模式匹配,PowerPC 后端包含以下指令定义

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))]>;

指令定义中突出显示的部分指示用于匹配指令的模式。DAG 运算符(如 fmul/fadd)在 include/llvm/Target/TargetSelectionDAG.td 文件中定义。“F4RC”是输入和结果值的寄存器类。

TableGen DAG 指令选择器生成器读取 .td 文件中的指令模式,并自动构建目标模式匹配代码的部分。它具有以下优点

  • 在编译器编译时,它会分析您的指令模式,并告诉您模式是否有意义。

  • 它可以处理模式匹配操作数的任意约束。特别是,可以很容易地说“匹配任何 13 位符号扩展值的立即数”。有关示例,请参阅 PowerPC 后端中的 immSExt16 和相关的 tblgen 类。

  • 它知道已定义模式的几个重要恒等式。例如,它知道加法是可交换的,因此它允许上面的 FMADDS 模式匹配 “(fadd X, (fmul Y, Z))” 以及 “(fadd (fmul X, Y), Z)”,而无需目标作者专门处理这种情况。

  • 它具有功能齐全的类型推断系统。特别是,您应该很少需要明确告诉系统模式中各个部分的类型。在上面的 FMADDS 示例中,我们不必告诉 tblgen 模式中的所有节点都是 ‘f32’ 类型。它能够从 F4RC 具有 ‘f32’ 类型这一事实中推断和传播此知识。

  • 目标可以定义自己的(并依赖内置的)“模式片段”。模式片段是可重用模式的块,在编译器编译时会内联到您的模式中。例如,整数 “(not x)” 运算实际上被定义为一个模式片段,它扩展为 “(xor x, -1)”,因为 SelectionDAG 没有原生的 ‘not’ 运算。目标可以根据需要定义自己的简写片段。有关示例,请参阅 ‘not’ 和 ‘ineg’ 的定义。

  • 除了指令之外,目标还可以使用 ‘Pat’ 类指定映射到一个或多个指令的任意模式。例如,PowerPC 没有办法在一个指令中将任意整数立即数加载到寄存器中。为了告诉 tblgen 如何做到这一点,它定义了

    // Arbitrary immediate support.  Implement in terms of LIS/ORI.
    def : Pat<(i32 imm:$imm),
              (ORI (LIS (HI16 imm:$imm)), (LO16 imm:$imm))>;
    

    如果没有用于将立即数加载到寄存器的单指令模式匹配,则将使用此模式。此规则表示“匹配任意 i32 立即数,将其转换为 ORI(‘或 16 位立即数’)和 LIS(‘加载 16 位立即数,其中立即数左移 16 位’)指令”。为了使此工作正常进行,LO16/HI16 节点转换用于操作输入立即数(在本例中,取立即数的高 16 位或低 16 位)。

  • 当使用 ‘Pat’ 类将模式映射到具有一个或多个复杂操作数(例如 X86 寻址模式)的指令时,该模式可以使用 ComplexPattern 将操作数作为一个整体指定,或者它可以分别指定复杂操作数的组件。后者例如通过 PowerPC 后端为预递增指令完成

    def STWU  : DForm_1<37, (outs ptr_rc:$ea_res), (ins GPRC:$rS, memri:$dst),
                    "stwu $rS, $dst", LdStStoreUpd, []>,
                    RegConstraint<"$dst.reg = $ea_res">, NoEncode<"$ea_res">;
    
    def : Pat<(pre_store GPRC:$rS, ptr_rc:$ptrreg, iaddroff:$ptroff),
              (STWU GPRC:$rS, iaddroff:$ptroff, ptr_rc:$ptrreg)>;
    

    在这里,ptroffptrreg 操作数对匹配到 STWU 指令中类 memri 的复杂操作数 dst 上。

  • 虽然系统自动化了很多工作,但如果有些事情难以表达,它仍然允许您编写自定义 C++ 代码来匹配特殊情况。

虽然它有很多优点,但该系统目前有一些局限性,主要是因为它仍在开发中且尚未完成

  • 总的来说,没有办法定义或匹配定义多个值的 SelectionDAG 节点(例如 SMUL_LOHILOADCALL 等)。这是您目前仍然必须为指令选择器编写自定义 C++ 代码的最大原因。

  • 目前还没有很好的方法来支持匹配复杂的寻址模式。未来,我们将扩展模式片段,以允许它们定义多个值(例如 X86 寻址模式的四个操作数,目前使用自定义 C++ 代码匹配)。此外,我们将扩展片段,以便一个片段可以匹配多个不同的模式。

  • 我们不会自动推断像 isStore/isLoad 这样的标志。

  • 我们不会自动为 Legalizer 生成支持的寄存器和操作集。

  • 我们还没有办法绑定自定义的合法化节点。

尽管存在这些限制,但指令选择器生成器对于典型指令集中的大多数二进制和逻辑运算仍然非常有用。如果您遇到任何问题或无法弄清楚如何做某事,请告诉 Chris!

SelectionDAG 调度和形成阶段

调度阶段从选择阶段获取目标指令的 DAG 并分配顺序。调度器可以根据机器的各种约束(即,最小寄存器压力的顺序或尝试覆盖指令延迟)选择顺序。一旦建立顺序,DAG 将转换为 列表 MachineInstrs 并且 SelectionDAG 被销毁。

请注意,此阶段在逻辑上与指令选择阶段分离,但在代码中与指令选择阶段紧密相连,因为它在 SelectionDAG 上运行。

SelectionDAG 的未来方向

  1. 可选的函数级选择。

  2. .td 文件自动生成整个选择器。

基于 SSA 的机器代码优化

待撰写

活跃区间

活跃区间是变量活跃的范围(区间)。一些 寄存器分配器 过程使用它们来确定两个或多个需要相同物理寄存器的虚拟寄存器是否在程序中的同一点活跃(即,它们冲突)。当这种情况发生时,必须溢出一个虚拟寄存器。

活跃变量分析

确定变量活跃区间的第一个步骤是计算指令后立即死亡的寄存器集合(即,指令计算值,但从未使用过)以及指令使用但指令后从未使用过的寄存器集合(即,它们被杀死)。为函数中的每个虚拟寄存器和可寄存器分配的物理寄存器计算活跃变量信息。这是以非常有效的方式完成的,因为它使用 SSA 来稀疏计算虚拟寄存器(采用 SSA 形式)的生命周期信息,并且只需要跟踪块内的物理寄存器。在寄存器分配之前,LLVM 可以假定物理寄存器仅在单个基本块内活跃。这允许它进行单个局部分析以解决每个基本块内的物理寄存器生命周期。如果物理寄存器不可寄存器分配(例如,堆栈指针或条件代码),则不跟踪它。

物理寄存器可能在函数内部或外部活跃。活跃的输入值通常是寄存器中的参数。活跃的输出值通常是寄存器中的返回值。活跃的输入值被标记为这样,并在活跃区间分析期间被赋予一个虚拟的“定义”指令。如果函数的最后一个基本块是 return,则它被标记为使用函数中的所有活跃输出值。

PHI 节点需要特殊处理,因为从函数 CFG 的深度优先遍历计算活跃变量信息不能保证 PHI 节点使用的虚拟寄存器在其使用之前定义。当遇到 PHI 节点时,只处理定义,因为用途将在其他基本块中处理。

对于当前基本块的每个 PHI 节点,我们在当前基本块的末尾模拟赋值,并遍历后继基本块。如果后继基本块具有 PHI 节点,并且 PHI 节点的操作数之一来自当前基本块,则该变量在当前基本块及其所有前驱基本块中标记为活跃,直到遇到具有定义指令的基本块。

活跃区间分析

我们现在拥有可用于执行活跃区间分析并构建活跃区间本身的信息。我们首先对基本块和机器指令进行编号。然后我们处理“活跃输入”值。这些值位于物理寄存器中,因此假定物理寄存器在基本块结束时被杀死。虚拟寄存器的活跃区间是针对机器指令的某些排序 [1, N] 计算的。活跃区间是一个区间 [i, j),其中 1 >= i >= j > N,变量在该区间内活跃。

注意

更多内容即将推出…

寄存器分配

寄存器分配问题包括将程序 Pv(可以使用无限数量的虚拟寄存器)映射到程序 Pp,后者包含有限数量(可能很小)的物理寄存器。每个目标架构都有不同数量的物理寄存器。如果物理寄存器的数量不足以容纳所有虚拟寄存器,则其中一些必须映射到内存中。这些虚拟寄存器称为溢出虚拟寄存器

寄存器在 LLVM 中的表示方式

在 LLVM 中,物理寄存器用整数表示,通常范围从 1 到 1023。要查看如何为特定架构定义此编号,您可以阅读该架构的 GenRegisterNames.inc 文件。例如,通过检查 lib/Target/X86/X86GenRegisterInfo.inc,我们看到 32 位寄存器 EAX 用 43 表示,MMX 寄存器 MM0 映射到 65。

某些架构包含共享相同物理位置的寄存器。一个值得注意的例子是 X86 平台。例如,在 X86 架构中,寄存器 EAXAXAL 共享前八位。这些物理寄存器在 LLVM 中被标记为别名。给定一个特定的架构,您可以通过检查其 RegisterInfo.td 文件来检查哪些寄存器是别名。此外,类 MCRegAliasIterator 枚举了别名为寄存器的所有物理寄存器。

在 LLVM 中,物理寄存器被分组为寄存器类。同一寄存器类中的元素在功能上是等效的,并且可以互换使用。每个虚拟寄存器只能映射到特定类的物理寄存器。例如,在 X86 架构中,某些虚拟寄存器只能分配给 8 位寄存器。寄存器类由 TargetRegisterClass 对象描述。要发现虚拟寄存器是否与给定的物理寄存器兼容,可以使用此代码

bool RegMapping_Fer::compatible_class(MachineFunction &mf,
                                      unsigned v_reg,
                                      unsigned p_reg) {
  assert(TargetRegisterInfo::isPhysicalRegister(p_reg) &&
         "Target register must be physical");
  const TargetRegisterClass *trc = mf.getRegInfo().getRegClass(v_reg);
  return trc->contains(p_reg);
}

有时,主要用于调试目的,更改目标架构中可用的物理寄存器数量很有用。这必须在 TargetRegisterInfo.td 文件中静态完成。只需 grep RegisterClass,其最后一个参数是寄存器列表。只需注释掉一些是避免使用它们的一种简单方法。更礼貌的方法是从分配顺序中显式排除某些寄存器。有关此示例,请参见 lib/Target/X86/X86RegisterInfo.tdGR8 寄存器类的定义。

虚拟寄存器也用整数表示。与物理寄存器相反,不同的虚拟寄存器永远不会共享相同的编号。物理寄存器在 TargetRegisterInfo.td 文件中静态定义,并且不能由应用程序开发人员创建,但虚拟寄存器的情况并非如此。为了创建新的虚拟寄存器,请使用方法 MachineRegisterInfo::createVirtualRegister()。此方法将返回一个新的虚拟寄存器。使用 IndexedMap<Foo, VirtReg2IndexFunctor> 来保存每个虚拟寄存器的信息。如果您需要枚举所有虚拟寄存器,请使用函数 TargetRegisterInfo::index2VirtReg() 来查找虚拟寄存器号

for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
  unsigned VirtReg = TargetRegisterInfo::index2VirtReg(i);
  stuff(VirtReg);
}

在寄存器分配之前,指令的操作数主要是虚拟寄存器,尽管也可以使用物理寄存器。为了检查给定的机器操作数是否为寄存器,请使用布尔函数 MachineOperand::isRegister()。要获取寄存器的整数代码,请使用 MachineOperand::getReg()。指令可能定义或使用寄存器。例如,ADD reg:1026 := reg:1025 reg:1024 定义了寄存器 1024,并使用了寄存器 1025 和 1026。给定一个寄存器操作数,方法 MachineOperand::isUse() 通知该寄存器是否被指令使用。方法 MachineOperand::isDef() 通知该寄存器是否被定义。

我们将寄存器分配之前 LLVM 位代码中存在的物理寄存器称为预着色寄存器。预着色寄存器用于许多不同的情况,例如,传递函数调用的参数,以及存储特定指令的结果。预着色寄存器有两种类型:隐式定义的和显式定义的。显式定义的寄存器是正常操作数,可以使用 MachineInstr::getOperand(int)::getReg() 访问。为了检查哪些寄存器由指令隐式定义,请使用 TargetInstrInfo::get(opcode)::ImplicitDefs,其中 opcode 是目标指令的操作码。显式和隐式物理寄存器之间的一个重要区别是,后者是为每个指令静态定义的,而前者可能会根据正在编译的程序而变化。例如,表示函数调用的指令将始终隐式定义或使用同一组物理寄存器。要读取指令隐式使用的寄存器,请使用 TargetInstrInfo::get(opcode)::ImplicitUses。预着色寄存器对任何寄存器分配算法施加约束。寄存器分配器必须确保在虚拟寄存器的值仍然活跃时,不会被它们覆盖。

将虚拟寄存器映射到物理寄存器

有两种方法可以将虚拟寄存器映射到物理寄存器(或内存槽)。第一种方法,我们称之为直接映射,基于使用类 TargetRegisterInfoMachineOperand 的方法。第二种方法,我们称之为间接映射,依赖于 VirtRegMap 类,以便插入加载和存储指令,以发送和获取内存中的值。

直接映射为寄存器分配器的开发人员提供了更大的灵活性;但是,它更容易出错,并且需要更多实现工作。基本上,程序员必须指定应将加载和存储指令插入到正在编译的目标函数中的何处,以便在内存中获取和存储值。要将物理寄存器分配给给定操作数中存在的虚拟寄存器,请使用 MachineOperand::setReg(p_reg)。要插入存储指令,请使用 TargetInstrInfo::storeRegToStackSlot(...),要插入加载指令,请使用 TargetInstrInfo::loadRegFromStackSlot

间接映射使应用程序开发人员免受插入加载和存储指令的复杂性影响。为了将虚拟寄存器映射到物理寄存器,请使用 VirtRegMap::assignVirt2Phys(vreg, preg)。为了将某个虚拟寄存器映射到内存,请使用 VirtRegMap::assignVirt2StackSlot(vreg)。此方法将返回 vreg 的值将位于的堆栈槽。如果需要将另一个虚拟寄存器映射到同一堆栈槽,请使用 VirtRegMap::assignVirt2StackSlot(vreg, stack_location)。使用间接映射时需要考虑的一个重点是,即使虚拟寄存器映射到内存,它仍然需要映射到物理寄存器。此物理寄存器是虚拟寄存器在存储之前或重新加载之后应该找到的位置。

如果使用间接策略,在所有虚拟寄存器都已映射到物理寄存器或堆栈槽之后,有必要使用溢出器对象在代码中放置加载和存储指令。每个已映射到堆栈槽的虚拟寄存器将在定义后存储到内存中,并在使用前加载。溢出器的实现尝试回收加载/存储指令,避免不必要的指令。有关如何调用溢出器的示例,请参见 lib/CodeGen/RegAllocLinearScan.cpp 中的 RegAllocLinearScan::runOnMachineFunction

处理双地址指令

除了极少数例外(例如,函数调用),LLVM 机器代码指令是三地址指令。也就是说,每个指令最多定义一个寄存器,最多使用两个寄存器。但是,某些架构使用双地址指令。在这种情况下,定义的寄存器也是使用的寄存器之一。例如,X86 中的指令(如 ADD %EAX, %EBX)实际上等效于 %EAX = %EAX + %EBX

为了生成正确的代码,LLVM 必须将表示双地址指令的三地址指令转换为真正的双地址指令。LLVM 提供了 TwoAddressInstructionPass 过程,用于此特定目的。它必须在寄存器分配发生之前运行。执行后,生成的代码可能不再是 SSA 形式。例如,在诸如 %a = ADD %b %c 的指令转换为诸如以下两个指令的情况下,会发生这种情况

%a = MOVE %b
%a = ADD %a %c

请注意,在内部,第二个指令表示为 ADD %a[def/use] %c。即,寄存器操作数 %a 既被指令使用又被定义。

SSA 解构阶段

寄存器分配期间发生的一个重要转换称为SSA 解构阶段。SSA 形式简化了在程序控制流图上执行的许多分析。但是,传统的指令集不实现 PHI 指令。因此,为了生成可执行代码,编译器必须用其他指令替换 PHI 指令,以保留其语义。

有很多方法可以安全地从目标代码中删除 PHI 指令。最传统的 PHI 解构算法用复制指令替换 PHI 指令。这是 LLVM 采用的策略。SSA 解构算法在 lib/CodeGen/PHIElimination.cpp 中实现。为了调用此过程,标识符 PHIEliminationID 必须在寄存器分配器的代码中标记为必需。

指令折叠

指令折叠是在寄存器分配期间执行的优化,它删除不必要的复制指令。例如,诸如以下的指令序列

%EBX = LOAD %mem_address
%EAX = COPY %EBX

可以安全地替换为单个指令

%EAX = LOAD %mem_address

可以使用 TargetRegisterInfo::foldMemoryOperand(...) 方法折叠指令。折叠指令时必须小心;折叠后的指令可能与原始指令完全不同。有关其用法的示例,请参见 lib/CodeGen/LiveIntervalAnalysis.cpp 中的 LiveIntervals::addIntervalsForSpills

内置寄存器分配器

LLVM 基础设施为应用程序开发人员提供了三种不同的寄存器分配器

  • Fast — 此寄存器分配器是调试构建的默认分配器。它在基本块级别分配寄存器,尝试将值保留在寄存器中并根据需要重用寄存器。

  • Basic — 这是寄存器分配的一种增量方法。活跃范围一次分配给一个寄存器,顺序由启发式方法驱动。由于代码可以在分配期间动态重写,因此此框架允许开发有趣的分配器作为扩展。它本身不是生产寄存器分配器,但作为性能基线,它是一种可能有用且独立的模式,用于分类错误。

  • Greedy默认分配器。这是Basic 分配器的高度调整实现,它结合了全局活跃范围拆分。此分配器努力将溢出代码的成本降至最低。

  • PBQP — 基于分区布尔二次规划 (PBQP) 的寄存器分配器。此分配器的工作原理是构建一个 PBQP 问题,表示正在考虑的寄存器分配问题,使用 PBQP 求解器解决此问题,并将解决方案映射回寄存器分配。

llc 中使用的寄存器分配器的类型可以使用命令行选项 -regalloc=... 选择

$ llc -regalloc=linearscan file.bc -o ln.s
$ llc -regalloc=fast file.bc -o fa.s
$ llc -regalloc=pbqp file.bc -o pbqp.s

序言/后记代码插入

注意

待撰写

紧凑展开

抛出异常需要从函数中展开。有关如何展开给定函数的信息传统上以 DWARF 展开(也称为帧)信息表示。但是该格式最初是为调试器回溯开发的,每个帧描述条目 (FDE) 每个函数需要约 20-30 字节。在运行时,将函数中的地址映射到相应的 FDE 也需要成本。另一种展开编码称为紧凑展开,每个函数仅需要 4 字节。

紧凑展开编码是一个 32 位值,它以架构特定的方式编码。它指定要恢复哪些寄存器以及从何处恢复,以及如何从函数中展开。当链接器创建最终链接映像时,它将创建一个 __TEXT,__unwind_info 区段。此区段是运行时访问任何给定函数的展开信息的一种小型快速方法。如果我们为函数发出紧凑展开信息,则该紧凑展开信息将编码在 __TEXT,__unwind_info 区段中。如果我们发出 DWARF 展开信息,则 __TEXT,__unwind_info 区段将包含最终链接映像中 __TEXT,__eh_frame 区段中 FDE 的偏移量。

对于 X86,紧凑展开编码有三种模式

带有帧指针的函数 (``EBP`` 或 ``RBP``)

基于 EBP/RBP 的帧,其中 EBP/RBP 在返回地址后立即推送到堆栈上,然后将 ESP/RSP 移动到 EBP/RBP。因此,要展开,使用当前的 EBP/RBP 值恢复 ESP/RSP,然后通过弹出堆栈来恢复 EBP/RBP,并通过再次将堆栈弹出到 PC 中来完成返回。所有需要恢复的非易失性寄存器都必须保存在堆栈上的一个小范围内,该范围从 EBP-4EBP-1020RBP-8RBP-1020)开始。偏移量(在 32 位模式下除以 4,在 64 位模式下除以 8)编码在位 16-23 中(掩码:0x00FF0000)。保存的寄存器编码在位 0-14 中(掩码:0x00007FFF),作为下表中的五个 3 位条目

紧凑编号

i386 寄存器

x86-64 寄存器

1

EBX

RBX

2

ECX

R12

3

EDX

R13

4

EDI

R14

5

ESI

R15

6

EBP

RBP

无帧且具有小常数堆栈大小(``EBP`` 或 ``RBP`` 未用作帧指针)

要返回,一个常量(以紧凑展开编码方式编码)会被加到 ESP/RSP。然后通过将栈弹出到 PC 来完成返回。所有需要恢复的非易失性寄存器必须在返回地址之后立即保存在栈上。栈大小(在 32 位模式下除以 4,在 64 位模式下除以 8)编码在位 16-23(掩码:0x00FF0000)中。在 32 位模式下,最大栈大小为 1024 字节,在 64 位模式下为 2048 字节。保存的寄存器数量编码在位 9-12(掩码:0x00001C00)中。位 0-9(掩码:0x000003FF)包含哪些寄存器被保存以及它们的顺序。(有关编码算法,请参阅 lib/Target/X86FrameLowering.cpp 中的 encodeCompactUnwindRegistersWithoutFrame() 函数。)

具有大常量栈大小的无帧 (``EBP`` 或 ``RBP`` 未用作帧指针)

这种情况类似于“具有小常量栈大小的无帧”情况,但栈大小太大,无法在紧凑展开编码中进行编码。相反,它要求函数在其序言中包含 “subl $nnnnnn, %esp”。紧凑编码在位 9-12(掩码:0x00001C00)中包含函数中 $nnnnnn 值的偏移量。

后期机器代码优化

注意

待撰写

代码生成

代码生成的代码生成步骤负责从代码生成器抽象(如 MachineFunctionMachineInstr 等)降低到 MC 层使用的抽象(MCInstMCStreamer 等)。这是通过几个不同类的组合完成的:目标无关的(命名不当的)AsmPrinter 类、AsmPrinter 的目标特定子类(如 SparcAsmPrinter)和 TargetLoweringObjectFile 类。

由于 MC 层在目标文件抽象级别上工作,因此它没有函数、全局变量等的概念。相反,它考虑的是标签、指令和指令。此时使用的关键类是 MCStreamer 类。这是一个抽象 API,以不同的方式实现(例如,输出 .s 文件,输出 ELF .o 文件等),它实际上是一个“汇编器 API”。MCStreamer 为每个指令都有一个方法,例如 EmitLabel、EmitSymbolAttribute、switchSection 等,这些方法直接对应于汇编级别的指令。

如果您有兴趣为目标实现代码生成器,则需要为您的目标实现三个重要事项

  1. 首先,您需要为您的目标创建一个 AsmPrinter 的子类。此类实现将 MachineFunction 转换为 MC 标签构造的通用降低过程。AsmPrinter 基类提供了许多有用的方法和例程,并且还允许您以一些重要方式覆盖降低过程。如果您正在实现 ELF、COFF 或 MachO 目标,您应该可以免费获得大部分降低,因为 TargetLoweringObjectFile 类实现了许多通用逻辑。

  2. 其次,您需要为您的目标实现一个指令打印器。指令打印器接受一个 MCInst 并将其呈现为 raw_ostream 作为文本。其中大部分是从 .td 文件自动生成的(当您在指令中指定类似 “add $dst, $src1, $src2” 的内容时),但您需要实现例程来打印操作数。

  3. 第三,您需要实现将 MachineInstr 降低为 MCInst 的代码,通常在 “<target>MCInstLower.cpp” 中实现。此降低过程通常是目标特定的,并负责将跳转表条目、常量池索引、全局变量地址等转换为适当的 MCLabel。此转换层还负责将代码生成器使用的伪操作扩展为它们对应的实际机器指令。由此生成的 MCInst 被馈送到指令打印器或编码器。

最后,您可以选择实现 MCCodeEmitter 的子类,该子类将 MCInst 降低为机器代码字节和重定位。如果您想支持直接 .o 文件生成,或者想为您的目标实现汇编器,这很重要。

生成函数栈大小信息

TargetLoweringObjectFile::StackSizesSection 不为空,并且 TargetOptions::EmitStackSizeSection 设置为 (-stack-size-section) 时,将生成包含函数栈大小元数据的节。该节将包含函数符号值(指针大小)和栈大小(无符号 LEB128)的数组对。栈大小值仅包括在函数序言中分配的空间。具有动态栈分配的函数不包括在内。

VLIW 数据包化器

在超长指令字 (VLIW) 架构中,编译器负责将指令映射到架构上可用的功能单元。为此,编译器创建称为数据包捆绑包的指令组。LLVM 中的 VLIW 数据包化器是一种目标无关的机制,用于启用机器指令的数据包化。

从指令到功能单元的映射

VLIW 目标中的指令通常可以映射到多个功能单元。在数据包化过程中,编译器必须能够推断指令是否可以添加到数据包中。此决定可能很复杂,因为编译器必须检查指令到功能单元的所有可能映射。因此,为了减轻编译时复杂性,VLIW 数据包化器解析目标的指令类,并在编译器构建时生成表。然后,提供的与机器无关的 API 可以查询这些表,以确定指令是否可以容纳在数据包中。

数据包化表如何生成和使用

数据包化器从目标的行程中读取指令类,并创建一个确定性有限自动机 (DFA) 来表示数据包的状态。DFA 由三个主要元素组成:输入、状态和转换。为生成的 DFA 设置的输入表示添加到数据包的指令。状态表示数据包中指令可能消耗的功能单元。在 DFA 中,从一个状态到另一个状态的转换发生在向现有数据包添加指令时。如果功能单元到指令的合法映射,则 DFA 包含相应的转换。缺少转换表明不存在合法映射,并且该指令无法添加到数据包中。

要为 VLIW 目标生成表,请将 TargetGenDFAPacketizer.inc 添加为目标目录中 Makefile 的目标。导出的 API 提供了三个函数:DFAPacketizer::clearResources()DFAPacketizer::reserveResources(MachineInstr *MI)DFAPacketizer::canReserveResources(MachineInstr *MI)。这些函数允许目标数据包化器向现有数据包添加指令,并检查指令是否可以添加到数据包中。有关更多信息,请参阅 llvm/CodeGen/DFAPacketizer.h

实现本机汇编器

虽然您阅读本文可能是因为您想编写或维护编译器后端,但 LLVM 也完全支持构建本机汇编器。我们努力自动化从 .td 文件(特别是指令语法和编码)生成汇编器的过程,这意味着可以分解大量手动和重复的数据输入并与编译器共享。

指令解析

注意

待撰写

指令别名处理

指令解析后,它会进入 MatchInstructionImpl 函数。MatchInstructionImpl 函数执行别名处理,然后执行实际匹配。

别名处理是将同一指令的不同词法形式规范化为一个表示形式的阶段。可以实现几种不同类型的别名,它们在下面按处理顺序(从最简单/最弱到最复杂/最强大)列出。通常,您希望使用满足您的指令需求的第一个别名机制,因为它将允许更简洁的描述。

助记符别名

别名处理的第一阶段是简单的指令助记符重映射,用于允许使用两个不同助记符的指令类。此阶段是从一个输入助记符到一个输出助记符的简单且无条件重映射。这种形式的别名不可能查看操作数,因此重映射必须应用于给定助记符的所有形式。助记符别名的定义很简单,例如 X86 有

def : MnemonicAlias<"cbw",     "cbtw">;
def : MnemonicAlias<"smovq",   "movsq">;
def : MnemonicAlias<"fldcww",  "fldcw">;
def : MnemonicAlias<"fucompi", "fucomip">;
def : MnemonicAlias<"ud2a",    "ud2">;

… 以及许多其他别名。使用 MnemonicAlias 定义,助记符被简单而直接地重映射。虽然 MnemonicAlias 无法查看指令的任何方面(例如操作数),但它们可以通过 Requires 子句依赖于全局模式(匹配器支持的相同模式)

def : MnemonicAlias<"pushf", "pushfq">, Requires<[In64BitMode]>;
def : MnemonicAlias<"pushf", "pushfl">, Requires<[In32BitMode]>;

在此示例中,助记符根据当前的指令集映射到不同的助记符。

指令别名

最通用的别名处理阶段发生在匹配发生时:它为匹配器提供新的匹配形式,以及要生成的特定指令。指令别名有两个部分:要匹配的字符串和要生成的指令。例如

def : InstAlias<"movsx $src, $dst", (MOVSX16rr8W GR16:$dst, GR8  :$src)>;
def : InstAlias<"movsx $src, $dst", (MOVSX16rm8W GR16:$dst, i8mem:$src)>;
def : InstAlias<"movsx $src, $dst", (MOVSX32rr8  GR32:$dst, GR8  :$src)>;
def : InstAlias<"movsx $src, $dst", (MOVSX32rr16 GR32:$dst, GR16 :$src)>;
def : InstAlias<"movsx $src, $dst", (MOVSX64rr8  GR64:$dst, GR8  :$src)>;
def : InstAlias<"movsx $src, $dst", (MOVSX64rr16 GR64:$dst, GR16 :$src)>;
def : InstAlias<"movsx $src, $dst", (MOVSX64rr32 GR64:$dst, GR32 :$src)>;

这展示了指令别名的强大示例,根据汇编中存在的操作数,以多种不同的方式匹配相同的助记符。指令别名的结果可以包括操作数,其顺序与目标指令不同,并且可以多次使用输入,例如

def : InstAlias<"clrb $reg", (XOR8rr  GR8 :$reg, GR8 :$reg)>;
def : InstAlias<"clrw $reg", (XOR16rr GR16:$reg, GR16:$reg)>;
def : InstAlias<"clrl $reg", (XOR32rr GR32:$reg, GR32:$reg)>;
def : InstAlias<"clrq $reg", (XOR64rr GR64:$reg, GR64:$reg)>;

此示例还显示,绑定的操作数仅列出一次。在 X86 后端,XOR8rr 有两个输入 GR8 和一个输出 GR8(其中一个输入绑定到输出)。InstAliases 采用展平的操作数列表,对于绑定的操作数没有重复项。指令别名的结果也可以使用立即数和固定物理寄存器,这些立即数和固定物理寄存器作为简单的立即操作数添加到结果中,例如

// Fixed Immediate operand.
def : InstAlias<"aad", (AAD8i8 10)>;

// Fixed register operand.
def : InstAlias<"fcomi", (COM_FIr ST1)>;

// Simple alias.
def : InstAlias<"fcomi $reg", (COM_FIr RST:$reg)>;

指令别名也可以具有 Requires 子句,使其成为子目标特定的。

如果后端支持,指令打印器可以自动发出别名,而不是正在别名的内容。它通常可以生成更好、更易读的代码。如果最好打印出正在别名的内容,则将 '0' 作为第三个参数传递给 InstAlias 定义。

指令匹配

注意

待撰写

目标特定的实现说明

文档的这一部分解释了特定于特定目标的代码生成器的功能或设计决策。

尾调用优化

尾调用优化,被调用者重用调用者的堆栈,目前在 x86/x86-64、PowerPC、AArch64 和 WebAssembly 上受支持。如果满足以下条件,则在 x86/x86-64、PowerPC 和 AArch64 上执行:

  • 调用者和被调用者具有调用约定 fastcccc 10 (GHC 调用约定)、cc 11 (HiPE 调用约定)、tailccswifttailcc

  • 调用是尾调用 - 处于尾部位置(ret 紧跟在 call 之后,并且 ret 使用 call 的值或为 void)。

  • 选项 -tailcallopt 已启用,或者调用约定为 tailcc

  • 满足平台特定的约束。

x86/x86-64 约束

  • 不使用可变参数列表。

  • 在 x86-64 上生成 GOT/PIC 代码时,仅支持模块本地调用(可见性 = hidden 或 protected)。

PowerPC 约束

  • 不使用可变参数列表。

  • 不使用 byval 参数。

  • 在 ppc32/64 GOT/PIC 上,仅支持模块本地调用(可见性 = hidden 或 protected)。

WebAssembly 约束

  • 不使用可变参数列表

  • 启用 'tail-call' 目标属性。

  • 调用者和被调用者的返回类型必须匹配。除非被调用者也是 void,否则调用者不能为 void。

AArch64 约束

  • 不使用可变参数列表。

示例

调用方式为 llc -tailcallopt test.ll

declare fastcc i32 @tailcallee(i32 inreg %a1, i32 inreg %a2, i32 %a3, i32 %a4)

define fastcc i32 @tailcaller(i32 %in1, i32 %in2) {
  %l1 = add i32 %in1, %in2
  %tmp = tail call fastcc i32 @tailcallee(i32 inreg %in1, i32 inreg %in2, i32 %in1, i32 %l1)
  ret i32 %tmp
}

-tailcallopt 的含义

为了支持被调用者参数多于调用者的情况下的尾调用优化,使用了“被调用者弹出参数”的约定。这目前导致每个未进行尾调用优化的 fastcc 调用(因为不满足上述一个或多个约束)之后都跟随堆栈的重新调整。因此,在这些情况下,性能可能会更差。

兄弟调用优化

兄弟调用优化是尾调用优化的受限形式。与上一节中描述的尾调用优化不同,当未指定 -tailcallopt 选项时,它可以自动在任何尾调用上执行。

当满足以下约束时,当前在 x86/x86-64 上执行兄弟调用优化

  • 调用者和被调用者具有相同的调用约定。它可以是 cfastcc

  • 调用是尾调用 - 处于尾部位置(ret 紧跟在 call 之后,并且 ret 使用 call 的值或为 void)。

  • 调用者和被调用者具有匹配的返回类型,或者不使用被调用者的结果。

  • 如果任何被调用者参数在堆栈中传递,它们必须在调用者自己的传入参数堆栈中可用,并且帧偏移量必须相同。

示例

declare i32 @bar(i32, i32)

define i32 @foo(i32 %a, i32 %b, i32 %c) {
entry:
  %0 = tail call i32 @bar(i32 %a, i32 %b)
  ret i32 %0
}

X86 后端

X86 代码生成器位于 lib/Target/X86 目录中。此代码生成器能够以各种 x86-32 和 x86-64 处理器为目标,并包括对 ISA 扩展(如 MMX 和 SSE)的支持。

支持的 X86 目标三元组

以下是 X86 后端支持的已知目标三元组。这不是一个详尽的列表,添加人们测试过的三元组将很有用。

  • i686-pc-linux-gnu — Linux

  • i386-unknown-freebsd5.3 — FreeBSD 5.3

  • i686-pc-cygwin — Win32 上的 Cygwin

  • i686-pc-mingw32 — Win32 上的 MingW

  • i386-pc-mingw32msvc — Linux 上的 MingW 交叉编译器

  • i686-apple-darwin* — X86 上的 Apple Darwin

  • x86_64-unknown-linux-gnu — Linux

支持的 X86 调用约定

后端已知以下目标特定的调用约定

  • x86_StdCall — 在 Microsoft Windows 平台上看到的 stdcall 调用约定 (CC ID = 64)。

  • x86_FastCall — 在 Microsoft Windows 平台上看到的 fastcall 调用约定 (CC ID = 65)。

  • x86_ThisCall — 类似于 X86_StdCall。在 ECX 中传递第一个参数,其他参数通过堆栈传递。被调用者负责堆栈清理。此约定由 MSVC 默认用于其 ABI 中的方法 (CC ID = 70)。

在 MachineInstrs 中表示 X86 寻址模式

x86 具有非常灵活的内存访问方式。它能够直接在整数指令中形成以下表达式的内存地址(使用 ModR/M 寻址)

SegmentReg: Base + [1,2,4,8] * IndexReg + Disp32

为了表示这一点,LLVM 为这种形式的每个内存操作数跟踪不少于 5 个操作数。这意味着 ‘mov’ 的“加载”形式具有以下顺序的 MachineOperand

Index:        0     |    1        2       3           4          5
Meaning:   DestReg, | BaseReg,  Scale, IndexReg, Displacement Segment
OperandTy: VirtReg, | VirtReg, UnsImm, VirtReg,   SignExtImm  PhysReg

存储和所有其他指令以相同的方式和相同的顺序处理四个内存操作数。如果未指定段寄存器 (regno = 0),则不生成段覆盖。“Lea” 操作未指定段寄存器,因此它们的内存引用只有 4 个操作数。

支持的 X86 地址空间

x86 具有一个功能,该功能提供通过 x86 段寄存器对不同地址空间执行加载和存储的能力。指令上的段覆盖前缀字节导致指令的内存访问进入指定的段。LLVM 地址空间 0 是默认地址空间,包括堆栈和程序中的任何非限定内存访问。地址空间 1-255 当前为用户定义的代码保留。GS 段由地址空间 256 表示,FS 段由地址空间 257 表示,SS 段由地址空间 258 表示。其他 x86 段尚未分配地址空间编号。

虽然这些地址空间可能看起来类似于通过 thread_local 关键字的 TLS,并且通常使用相同的底层硬件,但它们之间存在一些根本差异。

thread_local 关键字应用于全局变量,并指定它们要分配在线程本地内存中。不涉及类型限定符,并且可以使用普通指针指向这些变量,并使用普通加载和存储进行访问。thread_local 关键字在 LLVM IR 级别是目标无关的(尽管 LLVM 尚未针对某些配置实现它)

相比之下,特殊地址空间适用于静态类型。每个加载和存储在其地址操作数类型中都有一个特定的地址空间,这决定了访问哪个地址空间。LLVM 忽略全局变量上的这些特殊地址空间限定符,并且不提供直接在其中分配存储空间的方法。在 LLVM IR 级别,这些特殊地址空间的行为部分取决于底层操作系统或运行时环境,并且它们特定于 x86(并且 LLVM 尚未在某些情况下正确处理它们)。

某些操作系统和运行时环境使用(或将来可能使用)FS/GS 段寄存器用于各种底层目的,因此在考虑它们时应谨慎。

指令命名

指令名称由基本名称、默认操作数大小和每个操作数一个字符(带有可选的特殊大小)组成。例如

ADD8rr      -> add, 8-bit register, 8-bit register
IMUL16rmi   -> imul, 16-bit register, 16-bit memory, 16-bit immediate
IMUL16rmi8  -> imul, 16-bit register, 16-bit memory, 8-bit immediate
MOVSX32rm16 -> movsx, 32-bit register, 16-bit memory

PowerPC 后端

PowerPC 代码生成器位于 lib/Target/PowerPC 目录中。代码生成可重定向到 PowerPC ISA 的几个变体或子目标;包括 ppc32、ppc64 和 altivec。

LLVM PowerPC ABI

LLVM 遵循 AIX PowerPC ABI,但有两个偏差。LLVM 使用 PC 相对 (PIC) 或静态寻址来访问全局值,因此不使用 TOC (r2)。其次,r31 用作帧指针,以允许堆栈帧的动态增长。LLVM 利用没有 TOC 的优势,在调用者帧的 PowerPC 链接区域中提供空间来保存帧指针。有关 PowerPC ABI 的其他详细信息,请访问 PowerPC ABI。注意:此链接描述了 32 位 ABI。64 位 ABI 类似,只是 GPR 的空间为 8 字节宽(而不是 4 字节),并且 r13 保留供系统使用。

帧布局

PowerPC 帧的大小通常在函数调用期间是固定的。由于帧大小固定,因此可以通过来自堆栈指针的固定偏移量访问帧中的所有引用。此规则的例外情况是当存在动态 alloca 或可变大小数组时,此时基指针 (r31) 用作堆栈指针的代理,并且堆栈指针可以自由增长或缩小。如果 llvm-gcc 未传递 -fomit-frame-pointer 标志,也会使用基指针。堆栈指针始终对齐到 16 字节,以便为 altivec 向量分配的空间将正确对齐。

调用帧的布局如下(低内存位于顶部)

链接

参数区域

动态区域

局部变量区域

保存的寄存器区域


上一个帧

链接区域供被调用者在分配自己的帧之前保存特殊寄存器使用。只有三个条目与 LLVM 相关。第一个条目是上一个堆栈指针 (sp),也称为链接。这允许 gdb 或异常处理程序等探测工具快速扫描堆栈中的帧。函数 epilog 也可以使用链接从堆栈中弹出帧。链接区域中的第三个条目用于保存来自 lr 寄存器的返回地址。最后,如上所述,最后一个条目用于保存上一个帧指针 (r31)。链接区域中的条目的大小与 GPR 的大小相同,因此在 32 位模式下链接区域为 24 字节长,在 64 位模式下为 48 字节长。

32 位链接区域

0 保存的 SP (r1)
4 保存的 CR
8 保存的 LR
12 保留
16 保留
20 保存的 FP (r31)

64 位链接区域

0 保存的 SP (r1)
8 保存的 CR
16 保存的 LR
24 保留
32 保留
40 保存的 FP (r31)

参数区域用于存储传递给被调用函数的参数。按照 PowerPC ABI,前几个参数实际上在寄存器中传递,参数区域中的空间未使用。但是,如果寄存器不足或被调用者是 thunk 或 vararg 函数,则这些寄存器参数可以溢出到参数区域中。因此,参数区域必须足够大,以存储调用者发出的最大调用序列的所有参数。大小还必须最小足够大,以溢出寄存器 r3-r10。这允许不了解调用签名的被调用者(例如 thunk 和 vararg 函数)有足够的空间来缓存参数寄存器。因此,参数区域最小为 32 字节(在 64 位模式下为 64 字节)。另请注意,由于参数区域与帧顶部有固定的偏移量,因此被调用者可以使用来自堆栈指针(或基指针)的固定偏移量访问其拆分参数。

结合有关链接、参数区域和对齐的信息。堆栈帧在 32 位模式下最小为 64 字节,在 64 位模式下最小为 128 字节。

动态区域最初大小为零。如果函数使用动态 alloca,则会将空间添加到堆栈,链接和参数区域会移至堆栈顶部,并且新空间立即在链接和参数区域下方可用。移动链接和参数区域的成本很小,因为只需要复制链接值。可以通过将原始帧大小添加到基指针来轻松获取链接值。请注意,动态空间中的分配需要遵守 16 字节对齐。

局部变量区域是 llvm 编译器为局部变量保留空间的地方。

保存的寄存器区域是 llvm 编译器在进入被调用者时溢出被调用者保存的寄存器的地方。

序言/尾声

llvm 序言和尾声与 PowerPC ABI 中描述的相同,但以下例外情况除外。被调用者保存的寄存器在创建帧后溢出。这允许 llvm 尾声/序言支持与其他目标通用。基指针被调用者保存的寄存器 r31 保存在链接区域的 TOC 插槽中。这简化了基指针空间的分配,并使其在编程和调试期间易于定位。

动态分配

注意

TODO - 更多内容即将推出。

NVPTX 后端

lib/Target/NVPTX 下的 NVPTX 代码生成器是 NVIDIA NVPTX 代码生成器的 LLVM 开源版本。它由 NVIDIA 贡献,是 CUDA 编译器 (nvcc) 中使用的代码生成器的移植版本。它的目标是 PTX 3.0/3.1 ISA,并且可以以任何计算能力大于或等于 2.0 (Fermi) 的目标为目标。

此目标是生产质量的,并且应与官方 NVIDIA 工具链完全兼容。

代码生成器选项

选项 描述
sm_20 将着色器模型/计算能力设置为 2.0
sm_21 将着色器模型/计算能力设置为 2.1
sm_30 将着色器模型/计算能力设置为 3.0
sm_35 将着色器模型/计算能力设置为 3.5
ptx30 目标 PTX 3.0
ptx31 目标 PTX 3.1

扩展 Berkeley Packet Filter (eBPF) 后端

扩展 BPF (或 eBPF) 类似于用于过滤网络数据包的原始(“经典”)BPF (cBPF)。bpf() 系统调用 执行与 eBPF 相关的一系列操作。对于 cBPF 和 eBPF 程序,Linux 内核在加载程序之前对其进行静态分析,以确保它们不会损害正在运行的系统。eBPF 是一种 64 位 RISC 指令集,旨在与 64 位 CPU 进行一对一映射。操作码是 8 位编码的,并定义了 87 条指令。有 10 个寄存器,按功能分组如下。

R0        return value from in-kernel functions; exit value for eBPF program
R1 - R5   function call arguments to in-kernel functions
R6 - R9   callee-saved registers preserved by in-kernel functions
R10       stack frame pointer (read only)

指令编码(算术和跳转)

eBPF 重用了经典 BPF 的大部分操作码编码,以简化经典 BPF 到 eBPF 的转换。对于算术和跳转指令,8 位“代码”字段分为三部分

+----------------+--------+--------------------+
|   4 bits       |  1 bit |   3 bits           |
| operation code | source | instruction class  |
+----------------+--------+--------------------+
(MSB)                                      (LSB)

三个 LSB 位存储指令类,指令类之一是

BPF_LD     0x0
BPF_LDX    0x1
BPF_ST     0x2
BPF_STX    0x3
BPF_ALU    0x4
BPF_JMP    0x5
(unused)   0x6
BPF_ALU64  0x7

当 BPF_CLASS(code) == BPF_ALU 或 BPF_ALU64 或 BPF_JMP 时,第 4 位编码源操作数

BPF_X     0x1  use src_reg register as source operand
BPF_K     0x0  use 32 bit immediate as source operand

四个 MSB 位存储操作码

BPF_ADD   0x0  add
BPF_SUB   0x1  subtract
BPF_MUL   0x2  multiply
BPF_DIV   0x3  divide
BPF_OR    0x4  bitwise logical OR
BPF_AND   0x5  bitwise logical AND
BPF_LSH   0x6  left shift
BPF_RSH   0x7  right shift (zero extended)
BPF_NEG   0x8  arithmetic negation
BPF_MOD   0x9  modulo
BPF_XOR   0xa  bitwise logical XOR
BPF_MOV   0xb  move register to register
BPF_ARSH  0xc  right shift (sign extended)
BPF_END   0xd  endianness conversion

如果 BPF_CLASS(code) == BPF_JMP,则 BPF_OP(code) 之一是

BPF_JA    0x0  unconditional jump
BPF_JEQ   0x1  jump ==
BPF_JGT   0x2  jump >
BPF_JGE   0x3  jump >=
BPF_JSET  0x4  jump if (DST & SRC)
BPF_JNE   0x5  jump !=
BPF_JSGT  0x6  jump signed >
BPF_JSGE  0x7  jump signed >=
BPF_CALL  0x8  function call
BPF_EXIT  0x9  function return

指令编码(加载、存储)

对于加载和存储指令,8 位“代码”字段的划分方式为

+--------+--------+-------------------+
| 3 bits | 2 bits |   3 bits          |
|  mode  |  size  | instruction class |
+--------+--------+-------------------+
(MSB)                             (LSB)

大小修饰符之一是

BPF_W       0x0  word
BPF_H       0x1  half word
BPF_B       0x2  byte
BPF_DW      0x3  double word

模式修饰符之一是

BPF_IMM     0x0  immediate
BPF_ABS     0x1  used to access packet data
BPF_IND     0x2  used to access packet data
BPF_MEM     0x3  memory
(reserved)  0x4
(reserved)  0x5
BPF_XADD    0x6  exclusive add

数据包数据访问 (BPF_ABS, BPF_IND)

两个非通用指令:(BPF_ABS | <size> | BPF_LD)和(BPF_IND | <size> | BPF_LD),用于访问数据包数据。寄存器 R6 是一个隐式输入,必须包含指向 sk_buff 的指针。寄存器 R0 是一个隐式输出,其中包含从数据包中获取的数据。寄存器 R1-R5 是暂存寄存器,不得用于跨 BPF_ABS | BPF_LD 或 BPF_IND | BPF_LD 指令存储数据。这些指令也具有隐式程序退出条件。当 eBPF 程序尝试访问超出数据包边界的数据时,解释器将中止程序的执行。

BPF_IND | BPF_W | BPF_LD 等效于

R0 = ntohl(*(u32 *) (((struct sk_buff *) R6)->data + src_reg + imm32))

eBPF 映射

eBPF 映射用于在内核和用户空间之间共享数据。当前实现的类型是哈希和数组,并有可能扩展以支持布隆过滤器、基数树等。映射由其类型、最大元素数、键大小和值大小(以字节为单位)定义。eBPF 系统调用支持对映射执行创建、更新、查找和删除功能。

函数调用

函数调用参数最多使用五个寄存器(R1 - R5)传递。返回值在专用寄存器(R0)中传递。四个额外的寄存器(R6 - R9)是被调用者保存的,并且这些寄存器中的值在内核函数中被保留。R0 - R5 是内核函数中的暂存寄存器,因此,如果需要在函数调用之间使用这些寄存器中的值,则 eBPF 程序必须存储/恢复这些寄存器中的值。可以使用只读帧指针 R10 访问堆栈。eBPF 寄存器与 x86_64 和其他 64 位架构上的硬件寄存器 1:1 映射。例如,x86_64 内核 JIT 将它们映射为

R0 - rax
R1 - rdi
R2 - rsi
R3 - rdx
R4 - rcx
R5 - r8
R6 - rbx
R7 - r13
R8 - r14
R9 - r15
R10 - rbp

由于 x86-64 ABI 规定 rdi、rsi、rdx、rcx、r8、r9 用于参数传递,而 rbx、r12 - r15 由被调用者保存。

程序启动

一个 eBPF 程序接收单个参数,并包含一个 eBPF 主例程;该程序不包含 eBPF 函数。函数调用仅限于预定义的内核函数集合。程序的大小限制为 4K 指令:这确保了快速终止和有限数量的内核函数调用。在运行 eBPF 程序之前,验证器会执行静态分析,以防止代码中的循环,并确保有效的寄存器使用和操作数类型。

AMDGPU 后端

AMDGPU 代码生成器位于 lib/Target/AMDGPU 目录中。此代码生成器能够以各种 AMD GPU 处理器为目标。有关更多信息,请参阅 AMDGPU 后端用户指南