LLVM中指令的生命周期
LLVM是一个复杂的软件。为了了解它的工作原理，人们可以采取几种方法，但都不简单。
这里的目标是遵循“指令”在经过LLVM的多个编译阶段时的各种变化格式，从源语言中的语法构造开始，直到在输出对象文件中被编码为二进制机器代码。
本文本身不会教你LLVM是如何工作的。它假定对LLVM的设计和代码库已有一定的熟悉，并留下了许多“明显”的细节。注意，除非另有说明，这里的信息与LLVM 3.2相关。LLVM和Clang是快速发展的项目，未来的更改可能会导致本文的部分内容不正确。
输入代码
从一开始就开始这个探索过程-C源代码。下面是要使用的简单函数：
int foo(int aa, int bb, int cc) {
int sum = aa + bb;
return sum / cc;
}
本文的重点将放在division operation运算上。
Clang
Clang是LLVM的前端，负责将C、C++和ObjC源代码转换为LLVM IR。Clang的主要复杂性来自正确解析和语义分析C++的能力；简单C级操作的流程实际上非常简单。
Clang的解析器从输入中构建抽象语法树（AST）。AST是Clang各部分deal的主要“货币”。对于我们的division运算，在AST中创建了一个BinaryOperator节点，携带BO_div“operator kind”[1]。Clang的代码生成器接着从node节点发出sdiv LLVM IR指令，因为这是有符号整数类型的division划分。
LLVM IR
以下是为函数[2]创建的LLVM IR：
define i32 @foo(i32 %aa, i32 %bb, i32 %cc) nounwind {
entry:
%add = add nsw i32 %aa, %bb
%div = sdiv i32 %add, %cc
ret i32 %div
}
在LLVM IR中，sdiv是BinaryOperator，这是操作码为sdiv[3]的指令的子类。与任何其他指令一样，可以通过LLVM分析和转换过程进行处理。有关针对SDiv的特定示例，请查看SimplifySDivInst。由于在LLVM的“中间端”层中，指令始终保持其IR形式，所以不会花太多时间讨论。为了见证下一个变化，必须查看LLVM代码生成器。
代码生成器是LLVM最复杂的部分之一。任务是将相对高级、目标无关的LLVM IR“降低”为低级、目标相关的“机器指令”（MachineInstr）。在到达MachineInstr的过程中，LLVM IR指令通过“选择DAG节点”变化，这就是接下来要讨论的内容。
SelectionDAG node
SelectionDAG[4]节点由SelectionDAGBuilder类“在SelectionDAGISel的服务中”创建，SelectionDAGISel是指令选择的主要基类。SelectionDAGIsel遍历所有IR指令并调用SelectionDAGBuilder:：visit调度程序。处理SDiv指令的方法是SelectionDAGBuilder:：visitDiv。它使用操作码ISD:：SDIV从DAG申请一个新的SDNode，将成为DAG中的一个节点。
以这种方式构建的初始DAG仍然仅部分依赖于目标。在LLVM命名法中，称为“非法”——目标可能不直接支持所包含的类型；包含的操作也是如此。
有两种方法可以可视化DAG。一种是将-debug标志传递给llc，这将导致它在所有指令阶段创建DAG的文本转储。另一种方法是传递-view选项之一，使其转储并显示图形的实际图像（更多详细信息请参见代码生成器文档）。下面是DAG的相关部分，显示了DAG创建后的SDiv节点（SDiv节点位于底部）：
在SelectionDAG机器实际从DAG节点发出机器指令之前，这些节点会经历一些其他转换。最重要的是类型和操作合法化步骤，它使用特定于目标的钩子将所有操作和类型转换为目标实际支持的操作和类型。
在x86上将sdiv“合法化”为sdivrem
x86的division指令（有符号操作数的idv）计算运算的商和余数，并存储在两个独立的寄存器中。由于LLVM的指令选择区分了这类操作（称为ISD:：SDIVREM）和只计算商的division（ISD:：SDIV），因此当目标为x86时，我们的DAG节点将在DAG合法化阶段“合法化”。
代码生成器用于向通常独立于目标的算法传递特定于目标的信息的一个重要接口是TargetLowering。目标实现此接口以描述LLVM IR指令应如何降低到合法的SelectionDAG操作。此接口的x86实现是X86TargetPowering[5]。在其构造函数中，它标记哪些操作需要通过操作合法化来“扩展”，ISD:：SDIV就是其中之一。下面是代码中有趣的注释：
// Scalar integer divide and remainder are lowered to use operations that
// produce two results, to match the available instructions. This exposes
// the two-result form to trivial CSE, which is able to combine x/y and x%y
// into a single instruction.
当SelectionDAGLegalize:：LegizeOp在SDIV节点[6]上看到Expand标志时，它将其替换为ISD:：SDIVREM。这是一个有趣的示例，演示了在选择DAG形式下可以进行的转换操作。
Instruction selection - from SDNode to MachineSDNode
代码生成过程[7]的下一步是指令选择。LLVM提供了一种通用的基于表的指令选择机制，该机制在TableGen的帮助下自动生成。然而，许多目标后端选择在SelectionDAGISel:：Select实现中编写自定义代码来手动处理一些指令。然后通过调用SelectCode将其他指令发送到自动生成的选择器。
X86后端手动处理ISD:：SDIVREM，以处理一些特殊情况和优化。在此步骤中创建的DAG节点是MachineSDNode，这是SDNode的一个子类，保存了构建实际机器指令所需的信息，但仍然是DAG节点形式。此时，实际的X86指令操作码被选中-在例子中是X86:：IDIV32r。
Scheduling and emitting a MachineInstr
此时的代码仍然表示为DAG。但CPU不执行DAG，而是执行线性指令序列。调度步骤的目标是通过向DAG的操作（节点）分配顺序来线性化DAG。最简单的方法是只对DAG进行拓扑排序，但LLVM的代码生成器采用了巧妙的启发式方法（如寄存器压力降低）来尝试并生成一个可以产生更快代码的调度。
每个目标都有一些钩子，可以实现这些钩子来影响调度的方式。
最后，调度器使用InstrEmitter:：EmitMachineNode从SDNode转换，将指令列表发送到MachineBasicBlock。此处的说明采用MachineInstr形式（从现在起为“MI形式”），DAG可以被销毁。
可以通过调用带有-print machineinstrs标志的llc，并查看第一个显示“指令选择后”的输出，来检查此步骤中发出的机器指令：
# After Instruction Selection:
# Machine code for function foo: SSA
Function Live Ins: %EDI in %vreg0, %ESI in %vreg1, %EDX in %vreg2
Function Live Outs: %EAX
BB#0: derived from LLVM BB %entry
Live Ins: %EDI %ESI %EDX
%vreg2<def> = COPY %EDX; GR32:%vreg2
%vreg1<def> = COPY %ESI; GR32:%vreg1
%vreg0<def> = COPY %EDI; GR32:%vreg0
%vreg3<def,tied1> = ADD32rr %vreg0<tied0>, %vreg1, %EFLAGS<imp-def,dead>; GR32:%vreg3,%vreg0,%vreg1
%EAX<def> = COPY %vreg3; GR32:%vreg3
CDQ %EAX<imp-def>, %EDX<imp-def>, %EAX<imp-use>
IDIV32r %vreg2, %EAX<imp-def>, %EDX<imp-def,dead>, %EFLAGS<imp-def,dead>, %EAX<imp-use>, %EDX<imp-use>; GR32:%vreg2
%vreg4<def> = COPY %EAX; GR32:%vreg4
%EAX<def> = COPY %vreg4; GR32:%vreg4
RET
# End machine code for function foo.
注意，输出提到代码是SSA形式的，可以看到使用的一些寄存器是“虚拟”寄存器（例如%vreg1）。
Register allocation - from SSA to non-SSA machine instructions
除了一些定义明确的异常之外，指令选择器生成的代码是SSA形式的。特别是，假设有一组无限的“虚拟”寄存器可供操作。当然，这不是真的。因此，代码生成器的下一步是从目标寄存器库调用“寄存器分配器”，其任务是用物理寄存器替换虚拟寄存器。
上面提到的例外情况也很重要，也很有趣，所以让再多讨论一下。
某些架构中的某些指令需要固定寄存器。一个很好的例子是x86中的除法指令，要求输入位于EDX和EAX寄存器中。指令选择器知道这些限制，因此可以在上面的代码中看到，IDIV32r的输入是物理寄存器，而不是虚拟寄存器。此分配由X86DAGToDAGISel:：Select完成。
寄存器分配器负责所有非固定寄存器。SSA形式的机器指令上还有一些优化（和伪指令扩展）步骤，但将跳过这些步骤。同样，不会讨论寄存器分配后执行的步骤，因为这些步骤不会改变（此时的MachineInstr）中出现的基本形式操作。如果感兴趣，请查看TargetPassConfig:：addMachinePasses。
Emitting code
因此，现在将原始的C函数转换为MI形式——一个填充了指令对象（MachineInstr）的MachineFunction。这是代码生成器完成任务的时刻，可以发出代码。在当前的LLVM中，有两种方法可以做到这一点。一种是（遗留的）JIT，将可执行的、准备好运行的代码直接发送到内存中。另一个是MC，这是一个雄心勃勃的对象文件和汇编框架，已经成为LLVM的一部分几年了，取代了以前的汇编生成器。MC目前正在用于所有（或至少是重要的）LLVM目标的程序集和对象文件发射。MC还支持“MCJIT”，这是一个基于MC层的JIT框架。这就是为什么将LLVM的JIT模块称为遗留模块。
将首先对遗留的JIT说几句话，然后转向MC，这是更普遍的有趣之处。
传递到JIT发出代码的顺序由LLVMTargetMachine:：addPassesToEmitMachineCode定义。调用addPassesToGenerateCode，定义了完成本文大部分内容所需的所有过程——将IR转换为MI形式。接下来，调用addCodeEmitter，这是一个特定于目标的过程，用于将MI转换为实际的机器代码。由于MI已经非常低级，所以转换为可运行的机器代码是相当简单的[8]。位于lib/Target/x86/X86CodeEmitter.cpp中的x86代码。对于除法指令，这里没有特殊的处理，因为打包的MachineInstr已经包含了操作码和操作数。一般与emitInstruction中的其他指令一起处理。
MCInst
当LLVM用作静态编译器（例如，作为clang的一部分）时，MI被传递到处理对象文件发射的MC层（它也可以发射文本汇编文件）。关于MC可以说很多，但这需要一篇文章。LLVMTargetMachine:：addPassesToEmitFile负责定义发出对象文件所需的操作序列。实际MI到MCInst的转换在AsmPrinter接口的EmitInstruction中完成。对于x86，此方法由X86AsmPrinter:：EmitInstruction实现，将工作委托给X86MCInstLower类。与JIT路径类似，此时对除法指令没有特殊的处理，一般与其他指令一起处理。
通过将-show-mc-inst传递给llc，可以看到创建的mc级指令，以及实际的汇编代码：
foo: # @foo
# BB#0: # %entry
movl %edx, %ecx # <MCInst #1483 MOV32rr
# <MCOperand Reg:46>
# <MCOperand Reg:48>>
leal (%rdi,%rsi), %eax # <MCInst #1096 LEA64_32r
# <MCOperand Reg:43>
# <MCOperand Reg:110>
# <MCOperand Imm:1>
# <MCOperand Reg:114>
# <MCOperand Imm:0>
# <MCOperand Reg:0>>
cltd # <MCInst #352 CDQ>
idivl %ecx # <MCInst #841 IDIV32r
# <MCOperand Reg:46>>
ret # <MCInst #2227 RET>
.Ltmp0:
.size foo, .Ltmp0-foo
目标文件（或汇编代码）的发射是通过实现MCStreamer接口完成的。对象文件由MCObjectStreamer发出，根据实际的对象文件格式进行了进一步的子类化。例如，ELF发射在MCELFStreamer中实现。MCInst通过拖缆的大致路径是MCObjectStreamer:：EmitInstruction，后跟特定格式的EmitInstToData。当然，二进制形式的指令的最终发射是特定于目标的。由MCCodeEmitter接口（例如X86MCCodeEmitter）处理。虽然LLVM代码的其余部分通常很棘手，因为必须在独立于目标和特定于目标的功能之间进行区分，但MC更具挑战性，因为添加了另一个维度-不同的对象文件格式。因此，有些代码是完全通用的，有些代码依赖于格式，有些代码则依赖于目标。
Assemblers and disassemblers
MCInst故意是一个非常简单的表示。试图尽可能多地传递语义信息，只保留指令操作码和操作数列表（以及汇编程序诊断的源位置）。与LLVM IR一样，这是一种具有多种可能编码的内部表示。最明显的两个是程序集（如上所示）和二进制对象文件。
llvm-mc是一个使用mc框架实现汇编程序和反汇编程序的工具。在内部，MCInst是用于在二进制和文本形式之间转换的表示。此时，该工具不关心哪个编译器生成了程序集/对象文件。
[1]
To examine the AST created by Clang, compile a source file with the -cc1 -ast-dump options.
[2]
I ran this IR via opt -mem2reg | llvm-dis in order to clean-up the spills.
[3]
These things are a bit hard to grep for because of some C preprocessor hackery employed by LLVM to minimize code duplication. Take a look at the include/llvm/Instruction.def file and its usage in various places in LLVM's source for more insight.
[4]
A DAG here means Directed Acyclic Graph, which is a data structure LLVM code generator uses to represent the various operations with the values they produce and consume.
[5]
Which is arguably the single scariest piece of code in LLVM.
[6]
This is an example of how target-specific information is abstracted to guide the target-independent code generation algorithm.
[7]
The code generator performs DAG optimizations between its major steps, such as between legalization and selection. These optimizations are important and interesting to know about, but since they act on and return selection DAG nodes, they're out of the focus of this article.
[8]
When I'm saying "machine code" at this point, I mean actual bytes in a buffer, representing encoded instructions the CPU can run. The JIT directs the CPU to execute code from this buffer once emission is over.
参考文献链接
https://eli.thegreenplace.net/2012/11/24/life-of-an-instruction-in-llvm/
标签：DAG,代码,IR,生命周期,指令,寄存器,LLVM From： https://www.cnblogs.com/wujianming-110117/p/16954132.html