2024-02-06 11:46:00
提示 ： 本文翻译了LLVM官方文档中的The LLVM Target-Independent Code Generator一文，主要为个人学习之用。根据个人的理解，删繁就简，所以有些地方跟原文有所出入，幸勿见怪。如果需要更准确的信息，请参照原文。
本节描述代码生成器的各个阶段，描述它们是如何工作的，以及如此设计的背后原理。
指令选择是将LLVM IR转换为特定机器指令的过程。学术界有多种指令选择算法，而LLVM使用了基于SelectionDAG的指令选择器。
目前，DAG指令选择器的一部分是由.td文件生成的，另一部分还是需要用C++代码实现。
GlobalISel是另一个指令选择框架，目前还是实验版本。
SelectionDAG提供了一种代码表示方式，对于用自动化的指令选择比较友好。另外，对于指令调度也比较友好。而且在这种表示上还可以做一些很低级的机器无关优化。
SelectionDAG是一种有向无环图，其结点是SDNode实例。SDNode主要包含了操作码和操作数。include/llvm/ISDOpcodes.h文件中描述各种操作节点类型。
实际中大多结点只是定义一个值，但每个结点都有可能定义多个值。比如，一个div/rem操作同时定义了商和余数。很多其他情形也需要多个值。每个结点还有若干操作数，表示为指向定义这些操作数的结点的边。因为结点可能定义多个值，这些边要表示为SDValue实例，即<SDNode, unsigned>序对，SDNode表示来自哪个结点，unsigned表示来自其哪个结果。SDNode产生的每个值都有关联的MVT (Machine Value Type)，表示该值的类型。
SelectionDAG包含两种类型的值：表示数据依赖的，表示控制依赖的。数据值就是整数或浮点数类型的边，控制依赖边就是MVT::Other类型的chain边。这些边为有副作用的结点(load/store/call/return)提供了顺序。根据约定，chain输入总是0号操作数，chain输出总是该操作产生的最后一个值。然而，经过指令选择，机器结点也会有在指令操作数后面的chain输入，而且后面可能跟着glue结点。
SelectionDAG指定有Entry和Root结点，Entry结点是一个标记结点，其操作数总是ISD::EntryToken。Root结点是产生最终结果的结点。
对于SelectionDAG，一个重要的概念是合法或非法。合法DAG只使用目标机支持的操作和类型。类型合法化和操作合法化负责将非法DAG转换为合法DAG。
包含以下步骤：
上述步骤完毕后，SelectionDAG被销毁，再运行的其他的代码生成pass。
为方便查看这些步骤发生的事情，可以利用LLC工具的一些选项。
SelectionDAGBuilder类负责从LLVM IR构建SelectionDAG，这个Pass大部分都是硬编码的（LLVM add -> SDNode add, getelementptr -> 显式的算术运算），过程中需要用到机器特定hooks来lower calls, returns, varargs等。
使DAG只使用目标机支持的类型。
将不支持的标量类型转化为支持的类型有两种方式：一种叫promoting，将小类型转为大类型，另一种叫expanding，将大整型分解为几个小整型。
将不支持的vector类型转换为支持的类型也有两种方式：一种是将vector分割，直到找到合法的类型，另一种是通过在末尾添加元素的方式扩展vector，叫expanding。如果一个vector一路到底分割为了单个元素，还没有找到支持的vector类型，那么这些元素就会被转化为标量，叫scalarizing。
目标机实现通过调用TargetLowering中的addRegisterClass方法来告知合法化器它支持哪些类型，对应的寄存器类是什么。
使DAG只使用目标机支持的操作。
目标机通常有古怪的约束，比如不支持某些操作。操作合法化通过用一系列操作来模拟某个不支持的操作（expansion）,或者通过将类型提升为更大类型来支持该操作（promotion）,或者通过目标特定的hook来实现合法化（custom）。
目标机实现通过调用TargetLowering中的setOperationAction方法来告知合法化器它不支持哪些操作，还有采用以上哪种方式来处理这种情况。
如果目标机有合法的vector类型，肯定希望用这些类型为shufflevector IR指令生成高效机器码，这就需要为shufflevector定制合法化操作。需要处理的形式包括以下几种：
vector select: 就两个输入vector中挑选元素组成新的vector，这也叫做blend或者bitwise select。
Insert subvector：vector要放入从index 0开始的一个更长的vector中。
Extract subvector: 从一个长的vector的index 0处拉出子向量。
Splat: vector的所有元素都是同样的标量元素。也叫broadcast或者duplicate。
合法化阶段的引入提供了一种SelectionDAG的标准化形式，并且可以在这种形式上做一些通用优化。
在代码生成中，SelectionDAG优化会多次运行，包括DAG刚刚构建好，以及每次合法化pass之后。该pass主要是做一些清理工作。一项重要的工作就是优化插入的符号扩展和零扩展指令。目前是使用ad-hoc技术，未来可能会转为使用更严格的技术。
这是指令选择过程的与机器有关的主要阶段。该阶段以合法的SelectionDAG为输入，通过模式匹配选择目标机上支持的指令，并输出新的DAG。考虑如下LLVM IR:
|
|
对应的SelectionDAG大致如下：
|
|
如果目标机支持浮点乘累加操作，那么乘和加就可以合并。在PowerPC上，指令选择器的输出大致如下：
|
|
PowerPC的后端会包含以下指令定义：
|
|
TableGen DAG指令选择器从.td文件中读取指令模式，并自动构建模式匹配代码。它具有以下优势：
在编译器自身的编译阶段，可以分析指令模式并告诉你该模式是否有意义。
在模式匹配时处理操作数约束。比如，很方便表达"匹配一个13 bit的符号扩展立即数"。
知悉关于模式一些重要性质。比如，知悉加法符合交换律。
具有功能齐全的类型推理系统。基本上不需要显式说明模式的每个部分是什么类型的。
目标机可以定义它们自己的模式片段。模式片段就是命名并可重用的模式。
除了指令，目标机还可以利用Pat类指定可以映射到单个或多个指令模式。比如，PowerPC不具有在一条指令中奖任意整型立即数搬到寄存器的方式，那么就可以在tblgen中做如下定义：
|
|
|
|
尽管有很多优点，该系统目前也有一些缺陷，主要是由于还有一些未完成的工作：
没有提供能定义多个值的SelectionDAG结点。这是仍然需要定制C++代码的主要原因。
尚未有支持复杂寻址模式的好的方式。未来将会扩展模式片段使之能够定义多个值。
无法自动推导类似isStore/isLoad的flag。
无法为合法化器自动生成所支持的寄存器和操作集合。
还没有绑定自定义合法化结点的方法。
尽管有这些限制，指令选择器生成器对于大多数的二元操作和逻辑操作指令仍然非常有用。
依据目标机器的各种约束，将机器指令的DAG指派一个顺序。顺序一旦建立，DAG就转换为MachineInstr列表，而后SelectionDAG就销毁了。
该阶段在逻辑上与指令选择是分开的，但是联系很紧密，因为该阶段的输入正是SelectionDAG。
TODO
活跃区间表示一个变量在哪个范围内是活跃的（live）。某些寄存器分配器会根据该信息确定需要相同物理寄存器的几个虚拟寄存器是否在某些程序点上同时活跃，即它们产生了冲突。如果产生了冲突，就要把某个虚拟寄存器溢出（spill）。
确定变量活跃区间的第一步就是计算指令执行后立即失效的寄存器集合（即指令计算了值，但后续不再使用），和本条指令中使用但后续不再使用的寄存器集合（即被杀死）。需要对每个虚拟寄存器和可分配的物理寄存器计算活跃变量信息，由于可以使用SSA对虚拟寄存器进行稀疏生命期分析，而且只需要跟踪一个基本块内的物理寄存器，这项任务可以很高效地完成。在寄存器分配之前，LLVM假设物理寄存器只在单个基本块活跃，这就使得通过局部分析就可以解析出物理寄存器的生命期。而如果一个物理寄存器不是可分配的（比如栈指针或条件码），就不需要跟踪它。
物理寄存器可能以活跃的状态流入或流出一个函数。流入的值常常是寄存器传递的参数，流出的值常常是寄存器传递的返回值。这些值在活跃区间分析中要打上特殊的标记。
PHI结点需要特殊处理，主要是因为在计算活跃变量信息时，对CFG的DFS遍历无法保证PHI结点使用的虚拟寄存器在使用前定义。当遇到PHI结点时，只处理定义，这是因为其使用会在其他基本块中处理。
对于当前基本块的每个PHI结点，要在当前基本块末尾模拟一个赋值语句并遍历后继基本块。如果后继基本块有PHI结点，且PHI结点的操作数来自于当前基本块，那么该变量就标记为在当前基本块中以及所有的前驱基本块中都是活跃的，直到碰到定义该变量的那个基本块。
现在有了足够的信息来做活跃区间分析。从给基本块和机器指令编号开始，接着处理流入的活跃值，这些值都是在物理寄存器中，所以在基本块末尾可以认为这些寄存器都死亡了。而对于虚拟寄存器，会计算出一个[i, j)形式的活跃区间，其中i, j都是指令编号。
寄存器分配问题就是将一个使用无限虚拟寄存器的程序，映射为只使用有限物理寄存器的程序。每个机器架构都有不同数量的物理寄存器，如果物理寄存器不够容纳所有的虚拟寄存器，一些虚拟寄存器就会被映射到内存，这叫spilled virtuals。
LLVM中物理寄存器用1~1023范围的整数来表示，可以阅读GenRegisterNames.inc文件来查看具体某个架构是怎么编号的，比如查阅lib/Target/X86/X86GenRegisterInfo.inc就可以直到EAX寄存器编号为43，MMX寄存器MM0编号为65。
一些架构含有物理位置相同的寄存器，如X86架构的EAX, AX, AL共享了前8bit。这些物理寄存器在LLVM中标记为别名。可以查阅RegisterInfo.td文件来检查某个架构的哪些寄存器是别名。而且，MCRegAliasIterator类可以枚举出跟某一个寄存器别名的所有物理寄存器。
物理寄存器在LLVM中被分组为寄存器类。同一个寄存器类中的寄存器是功能等价的，可以互换使用。每个虚拟寄存器只能被映射到某个寄存器类中的物理寄存器。例如，X86上，一些虚拟寄存器只能分配到8bit寄存器中。寄存器类用TargetRegisterClass对象描述，要想检查一个虚拟寄存器跟物理寄存器是否兼容，可以使用以下代码：
|
|
有时为了调试需求，需要改变目标机可用的物理寄存器数量。这项任务必须在TargetRegisterInfo.td中静态完成，RegisterClass的最后一个参数就是寄存器列表，如果需要避免使用某些寄存器，就从这里注释掉。
虚拟寄存器也是用整数表示的。与物理寄存器不同，不同的虚拟寄存器从来不会共享编号。物理寄存器是在TargetRegisterInfo.td中事先定义好的，不能由应用开发者创建，而虚拟寄存器不是这样。为了创建新的虚拟寄存器，可以使用MachineRegisterInfo::createVirtualRegister()方法，它会返回一个新的虚拟寄存器。用IndexedMap<Foo, VirtReg2IndexFunctor>来容纳每个虚拟寄存器的信息。如果需要枚举所有的虚拟寄存器，就使用TargetRegisterInfo::index2VirtReg()方法来找到虚拟寄存器编号：
|
|
在寄存器分配之前，虽然物理寄存器也有使用，不过指令操作数大部分都是虚拟寄存器。为了检查给定的操作数是否是寄存器，可以用MachineOperand::isRegister()方法。为了获得寄存器的整数编号，使用MachineOperand::getReg()。指令可能定义或使用寄存器。比如ADD reg:1026 := reg:1025 reg:1024使用了寄存器1024和1025，而定义了1026。给定寄存器操作数，方法MachineOperand::isUse()返回该寄存器是否被使用，而MachineOperand::isDef()返回该寄存器是否被定义。
我们将寄存器分配之前存在于LLVM IR中的物理寄存器叫做pre-colored寄存器。这类寄存器用于很多场景，比如，函数调用的参数传递，存储特殊指令的结果。有两类pre-colored寄存器：隐式定义的，显式定义的。后者就是正常的操作数，可以通过MachineInstr::getOperand(int)::getReg()来访问。而要想访问前者，就用TargetInstrInfo::get(opcode)::ImplicitDefs，其中opcode就是该指令的操作码。显式和隐式物理寄存器的重要区别就是后者是每条指令静态定义的，而前者会依赖具体被编译的程序而变化。例如，函数调用总是隐式定义或使用相同的物理寄存器集合。Pre-colored寄存器会给寄存器分配算法施加约束，寄存器分配器必须确保它们在活跃期间都不能被虚拟寄存器中的值所覆盖。
映射有两种方式：一是直接映射，使用TargetRegisterInfo和MachineOperand类中的方法；二是间接影射，依赖VirtRegMap类来插入load/store指令。
直接映射给寄存器分配器的开发者提供了更多灵活性，但是，也更容易出错，并且需要更多的实现工作。程序员需要指明在哪里插入laod和store指令。为了将某个物理寄存器指派给某个虚拟寄存器，用MachineOperand::setReg(p_reg)，插入store指令用TargetInstrInfo::storeRegToStackSlot(…)，插入load指令用TargetInstrInfo::loadRegFromStackSlot。
间接映射使开发者免于插入load/store指令的复杂性。用VirtRegMap::assignVirt2Phys(vreg, preg)将虚拟寄存器映射为物理寄存器，用VirtRegMap::assignVirt2StackSlot(vreg)将虚拟寄存器映射到内存，并返回映射的那个stack slot位置。如果需要将另一个虚拟寄存器映射到相同的stack slot，要用VirtRegMap::assignVirt2StackSlot(vreg, stack_location)。需要注意的一点是，当使用间接映射时，即便虚拟寄存器映射到了内存，仍然需要将它映射到物理寄存器，在对应值store之前，或reload之后，这个物理寄存器就是保存该值的位置。
如果使用间接映射，在虚拟寄存器映射到物理寄存器或栈槽之后，还需要使用spiller对象防止load/store指令。每个被映射到栈槽的虚拟寄存器在被定义之后都需要store到栈槽中，并在使用之前load回来。spiller的实现会尝试回收利用load/store指令，从而避免冗余。
LLVM机器码指令一般都是三地址指令，也就是说，最多定义一个寄存器，使用两个寄存器。但是有些架构使用二地址指令，被定义的寄存器同时也是被使用的寄存器中的一个，例如，X86中的ADD %EAX, %EBX表示%EAX = %EAX + %EBX.。
为了生成正确代码，LLVM必须将这类指令转化为二地址指令。LLVM提供了TwoAddressInstructionPass 来处理这种情况，且需要在寄存器分配前调用。调用之后生成的代码不再是SSA形式了，比如，%a = ADD %b %c会被转化为如下代码：
|
|
注意，在LLVM内部，第二条指令被表示为 ADD %a[def/use] %c。
在寄存器分配过程中发生的一个重要转换是SSA的销毁。SSA形式简化了CFG上执行的很多分析，但是传统指令集是不实现PHI指令的，因此，为了生成可执行代码，编译器必须将PHI指令替换为等价的其他指令。
消除PHI指令有多种方式，最传统的一种就是用copy指令替换PHI，这也是LLVM采取的策略。SSA销毁算法实现在lib/CodeGen/PHIElimination.cpp中。为了调用该Pass，需要打上PHIEliminationID标识符作为标记，因为寄存器分配器需要它。
指令折叠是在寄存器分配期间删除冗余copy指令的优化。比如，以下指令：
|
|
可以被安全替换为如下单条指令：
|
|
通过TargetRegisterInfo::foldMemoryOperand(...)方法可以将指令折叠。不过指令折叠时需要小心，折叠后的指令可能跟原始指令有相当大的差别。
LLVM基础设施提供了四种不同的寄存器分配器：
Fast — 是debug构建中默认使用的分配器。在基本块级别分配寄存器，尽量将值保存在寄存器中。
Basic — 一种增量的寄存器分配方法。通过启发式算法给寄存器指派活跃范围，每次一个。由于分配期间代码可能被改写，该框架允许分配器作为扩展实现。这并不是一个生产级别的分配器，但是在修复bug时很有用，而且可以作为性能基准。
Greedy — 默认的分配器。在Basic分配器基础上做了高度调优，引入了全局活跃范围分割。该分配器致力于使溢出代码的代价最小化。
PBQP — 基于PBQP的分配器。该分配器将寄存器分配问题建模为PBQP问题，然后使用PBQP求解器解决它，再把答案映射为寄存器的指派方案。
llc使用的寄存器分配器的类型可以在命令行用-regalloc=…选项指定：
|
|
TODO
TODO:
TODO
代码输出负责将代码生成器中的抽象表示（MachineFunction, MachineInstr等）lower到MC层使用的抽象表示（MCInst, MCStreamer等）。几个不同类合作完成这项任务：机器无关的AsmPrinter类，机器相关的AsmPrinter的子类，以及TargetLoweringObjectFile类。
MC层属于obj文件的抽象，不再有函数、全局变量等概念。相反，它会考虑标号，directive，指令等概念。此时使用的关键类是MCStreamer，它是可以用多种方式实现（输出.s或.o）的抽象API。MCStreamer针对每个directive有一个方法，比如EmitLabel, EmitSymbolAttribute, switchSection等，这都跟汇编级的directive是对应的。
如果对为某个机器实现代码生成器感兴趣，那么徐璈实现三件事情：
首先，需要继承AsmPrinter。该类将MachineFunction向下转换为MC标号。AsmPrinter基类提供了一系列有用的方法和例程，并允许覆盖其向下转换过程。如果想实现ELF，COFF，或者MachO格式的机器，可以复用很多已实现的代码，因为TargetLoweringObjectFile类已经实现了大部分公共逻辑。
其次，需要为你的目标机实现指令打印器。指令打印器以MCInst为输入，将其渲染成文本输出到raw_ostream。这里大部分都可以从.td文件中自动生成，但是仍然需要实现打印操作数的例程。
再次，需要实现从MachineInstr到MCInst的向下转换，常常实现在<target>MCInstLower.cpp文件中。这个向下转换过程经常是目标机相关的，负责将跳转表条目、常量池索引、全局变量地址转换为MCLabels。该转换层负责将代码生成器使用的微操作扩展为对应的实际机器指令，生成的MCInsts会交给指令打印器或者编码器。
最后，根据你的选择，你也可以为MCCodeEmitter实现一个子类，将MCInst向下转换为机器码字节和重定位。如果你想要支持.o文件输出，或者想实现一个汇编器，这一步就很重要。
当TargetLoweringObjectFile::StackSizesSection非空，且设置了TargetOptions::EmitStackSizeSection (-stack-size-section)时，包含函数栈大小元信息的section就会输出。该section包含一个数组，其元素是函数符号值和栈大小组成的有序对。当然栈大小仅包含在函数prologue中申请的栈空间，不包括动态栈申请。
在超长指令字架构上，编译器负责将指令映射到硬件功能单元上。为此，编译器会创建叫做packets或bundles的指令组。LLVM中的VLIW打包器就是完成机器指令打包的机器无关机制。
典型的VLIW机器指令会映射到多个功能单元。在打包过程中，编译器必须能够推理出一条指令是否能添加到指令包中。由于编译器需要检查所有可能的映射，这个决策过程可能会很复杂。因此，为了缓解这种复杂性，VLIW打包器会解析目标机的指令类，并在编译器构建期间生成表。可以通过机器无关的API查询这些表，来决定一条指令是否要容纳进一个指令包中。
打包器从目标机的itinerary描述中读取指令类，构建一个DFA来表示指令包的状态。一个DFA包含三个主要元素：输入、状态、转换。DFA的输入集合表示正在被添加到指令包中的指令，状态表示指令所消耗的可能的功能单元。在DFA中，从一个状态到另一个状态的转换发生在给已存在的指令包添加指令时。如果从功能单元到指令的合法映射存在，那么DFA就包含相应的转换。如果转换不存在，就意味着合法的映射不存在，指令不能添加到指令包中。
为了给VLIW机器生成表，需要在Makefile中将TargetGenDFAPacketizer.inc添加为目标。导出的API提供了三个函数：DFAPacketizer::clearResources(), DFAPacketizer::reserveResources(MachineInstr *MI), 和 DFAPacketizer::canReserveResources(MachineInstr *MI).。这些函数允许打包器将一条指令添加到已存在的指令包中，以及检查指令是否能被添加到指令包中。
LLVM支持实现完整的独立汇编器。其大部分代码都是从td文件中生成的。
指令解析一旦完成，就会进入MatchInstructionImpl函数。该函数做别名处理然后做实际的匹配。
别名处理是将相同指令的不同文本形式处理为一种标准形式。可能实现的别名有多种，下面按照它们被处理的顺序列出来了。通常情况下，你会想用第一种别名机制来满足实际需要，因为它允许更简洁的描述。
别名处理的第一步是简单的指令助记符重映射，它就是一种简单的从一种输入助记符到输出助记符的无条件重映射。这种别名不会去看操作数，所以这种重映射必须对给定的助记符的所有形式都适用。助记符别名的定义是很简单的，比如X86如下：
|
|
有了这类定义，助记符就可以简单直接地重映射。虽然助记符别名不会看指令内部信息，但是它们会通过Requires子句依赖于全局模式：
|
|
该例子中，根据当前指令集，助记符被映射到不同的指令。
别名处理的最一般步骤发生在匹配时：它提供了匹配器的新形式来匹配特定的指令生成。指令别名有两部分：要匹配的字符串和要生成的指令。例如：
|
|
这展示了一个强大的指令别名例子，根据汇编中存在哪些操作数，以多种不同的方式匹配相同的助记符。指令别名的结果可以包含以不同于目标指令的顺序排列的操作数,并且可以多次使用同一个输入，例如：
|
|
这个例子也展示了绑定的操作数只列出一次。在X86后端,XOR8rr有两个输入GR8和一个输出GR8(其中一个输入与输出绑定)。InstAliases 获取一个简化的不重复的操作数列表，指令别名的结果也可以使用立即数和固定的物理寄存器,它们在结果中会被添加为简单的立即数操作数，例如：
|
|
指令别名也可以使用Requires子句来使它们特定于具体的子目标机器。
如果后端支持，指令打印器还可以自动输出别名，而不是被别名的指令。通常这会导致代码更好更易读。如果确实需要被别名的指令，就在InstAlias定义时将0传入作为第三个参数。
TODO
2024-02-05 17:02:00
提示：本文翻译了LLVM官方文档中的The LLVM Target-Independent Code Generator一文，主要为个人学习之用。根据个人的理解，删繁就简，所以有些地方跟原文有所出入，幸勿见怪。如果需要更准确的信息，请参照原文。
LLVM的代码生成器是一个框架，提供了一系列可重用组件，将LLVM IR翻译为特定目标机器的汇编指令。包含以下六个组件：
抽象目标机描述接口：关于目标机器的重要属性（不包括这些属性是如何使用的）。位于include/llvm/Target。
用于表示目标机器代码的类：使之足够抽象以便能表达任意目标机的机器代码。位于include/llvm/CodeGen。例如，可以表达"常量池条目"和"跳转表"的概念。
用于在目标文件（MC层）表示代码的类和算法：可以表达汇编级的概念如：label, section, instruction. 而"常量池条目"和"跳转表"的概念不在这层表达。
目标无关算法。用于实现不同阶段的本地代码生成，如：寄存器分配、指令调度、栈帧表示。位于lib/CodeGen
对应于抽象机器描述接口的特定机器实现。这些机器描述利用LLVM提供的组件，以及为特定目标机定制的pass，为特定机器构件一个完整的目标生成器。位于lib/Target。
目标无关的JIT组件。该组件本身是目标无关的，但它会利用TargetJITInfo接口来处理目标相关的问题。位于lib/ExecutionEngine/JIT。
后端开发人员需要熟悉目标机描述以及机器代码表示相关的类。若要为新机器添加后端，需要为该机器实现抽象机器描述接口，并理解LLVM IR。若要实现新的代码生成算法，为了其可移植性，必须只依靠来目标机描述和机器代码表示来做。
要在LLVM框架中增加后端，需要实现的必不可少的接口只有两个：TargetMachine, DataLayout。
这意味着：一方面LLVM能够支持非传统的目标机，比如以C语言为后端，就不需要寄存器分配、指令选择等阶段；另一方面可以设计实现出完全不同的不需要用LLVM内置组件的代码生成器，比如针对FPGA。
设计代码生成器是为了支持寄存器微处理器的高效高质量代码生成。代码生成包含以下阶段：
指令选择：将LLVM IR转换为目标指令DAG。该DAG使用SSA形式的虚拟寄存器，以及与目标约束或调用约定相关的特定物理寄存器。
调度和生成序列化指令：以SelectionDAG为输入，决定指令顺序，并输出MachineInstr机器指令。
基于SSA的机器代码优化：比如modulo-scheduling和窥孔优化。
寄存器分配：将无限的虚拟寄存器映射到具体的物理寄存器，在必要时生成spill code。
插入prolog/epilog：一旦机器码生成完毕，栈空间需求量确定，就可以插入prolog/epilog。帧指针消除和stack packing也是在这阶段做的。
晚期机器码优化：比如spill code scheduling和窥孔优化。
代码输出：可以是汇编格式或二进制格式。
指令选择是基于最优化的模式匹配选择器做的。
具体后端的实现可以在这些阶段中任意插入自己特定的Pass。
机器描述类需要关于目标架构的详细描述。为了提取出关于机器描述的公共部分，LLVM使用TableGen语言来描述目标机器，来减少重复。
随着LLVM继续发展，会将越来越多机器描述移到td文件中。这样可以使移植后端更容易。
提供了目标机器的抽象描述。例如：指令、寄存器
所有的机器描述类（除了DataLayout）都是要被具体机器的实现继承的。TargetMachine类提供了需要被目标机实现的访问器。
提供了用于访问不同机器描述类的虚函数（getInstrInfo, getRegisterInfo, getFrameInfo）。具体机器（X86TargetMachine）实现这些虚函数。
该类是唯一必需的机器描述类，且不可被继承。该类用来说明目标机针对不同数据类型的内存布局、对齐要求、指针size、大小端等信息。
给指令选择使用，主要用于描述LLVM IR代码是如何lower到SelectionDAG。此外还用来指定：
该类描述目标机的寄存器集合以及这些寄存器之间的相互作用。
寄存器是用无符号整数表示的。需注意寄存器0保留为flag值。
处理器描述中的每个寄存器都有一个关联的TargetRegisterDesc条目，该条目提供了寄存器的文本名字以及一系列别名。
TargetRegisterInfo类还暴露了处理器特定的寄存器类，每个寄存器类都有相同属性。指令选择器创建的每个SSA虚拟寄存器都有一个关联的寄存器类。寄存器分配时，虚拟寄存器被相关联的寄存器类中的一个物理寄存器所替代。这些寄存器类都是通过TableGen自动生成的。
该类描述目标机支持的指令。定义了opcode对应的助记符、操作数数量、隐式使用和定义的寄存器、是否具有一些机器无关的属性（访问内存、满足交换律等）和机器相关的flag。
提供关于目标机器堆栈布局的信息。包含堆栈的增长方向，每个函数的堆栈对齐要求，局部变量区域的偏移位置。
提供目标机器的特定子芯片的信息。包括该子芯片支持的指令、指令延迟、指令指令itinerary（使用的的处理单元、顺序以及时长）。
定义了给JIT代码生成器的抽象接口，来处理机器相关的活动，如发射stub。
llvm使用MachineFunction, MachineBasicBlock, MachineInstr (include/llvm/CodeGen) 几个类来表示机器码，这几个类本身是机器无关的，将代码表示成抽象形式的指令：一个操作码加几个操作数。这种表示既支持SSA形式，也支持寄存器分配后的非SSA形式。
将机器指令表示为MachineInstr的实例。MachineInstr表达指令的方式相当抽象，只记录操作码和一系列操作数。
操作码就是一个简单的无符号整数。目标机的所有指令都应该定义在InstrInfo.td中。操作码的枚举值就是从这些定义中生成的。MachineInstr类并不包含对应指令的语义信息（这些信息在TargetInstrInfo类中）。
操作数可以有几种类型：寄存器引用、常量整数、基本块引用等。另外，还需要将操作数标记为def或use。根据约定，操作数中寄存器def必须出现在use之前（不管最终的汇编码是否如此）。
可以使用BuildMI (include/llvm/CodeGen/MachineInstrBuilder.h)来创建机器指令。用法如下：
|
|
若要增加额外的def操作数，必须要显式标记出来。
|
|
代码生成器需要知道哪些寄存器是有固定用途的。指令流里面常常需要把特殊值安排在特殊寄存器中，比如由于指令集的限制，X86需要用EAX/EDX来做32位除法，再比如调用约定产生的特殊约束。在这些情况下，指令选择器会生成代码将虚拟寄存器拷入或拷出到物理寄存器。比如以下LLVM代码：
|
|
会被转换为如下的机器码：
|
|
不过在最后，寄存器分配器会将冗余的寄存器拷贝操作删除，生成如下代码：
|
|
这种方法对任何目标机都适用。需要注意的是，为了高质量的代码生成，物理寄存器的生命周期要短，而且所有的物理寄存器在进入基本块和离开基本块时是dead的（在寄存器分配之前如此）。因此，如果需要一个值的活跃期跨越基本块，必须活跃于虚拟寄存器中。
一些机器指令会破坏大量的物理寄存器，，比如函数调用。这时就需要用MO_RegisterMask来将它们标记出来，MO_RegisterMask能够标记出哪些寄存器是在函数调用中被保护的，而除此之外的其他寄存器就默认是被破坏了。
MachineInstr在寄存器分配之前都保持着SSA形式。LLVM PHI结点变成了机器码PHI结点，而虚拟寄存器只允许有一个def。在寄存器分配之后，代码中就不存在虚拟寄存器了，机器码也不再是SSA形式了。
包含一个机器指令(MachineInstr)列表。大致跟LLVM IR中的基本块是对应的，不过也有可能一个LLVM IR基本块对应多个MachineBasicBlock。其中有一个getBasicBLock方法，可以返回对应的LLVM IR基本块。
包含一个MachineBasicBlock列表。跟LLVM IR中的函数是对应的。除了MachineBasicBlock列表之外，每个MachineFunction还包含一个MachineConstantPool, 一个MachineFrameInfo, 一个MachineFunctionInfo, 一个MachineRegisterInfo。
可以将一个指令序列视为MachineInstr指令包。这种指令包可以建模包含任意数量并行指令的VLIW指令，也可以建模无法分割的一个执行序列，如ARM Thumb2 IT block。
在概念上，一个MI指令包就是一个MI内部嵌套了几个其他MI。
|
|
内部的MI会打上InsideBundle标志。具有特殊BUNDLE操作码的顶层MI用来表示指令包的开头。
关于MachineInstr的Pass是将MI指令包作为基本单元来操作的。MachineBasicBlock的迭代器就是如此。正因如此，MachineBasicBlock还提供了另外一个迭代器instr_iterator，可以遍历基本块的所有MI指令。顶层BUNDLE指令必须具有正确的寄存器 MachineOperand 集合,这些寄存器表示捆绑指令(bundled MIs)的累积输入和输出。
对于VLIW架构，MachineInstr的打包是寄存器分配的一部分。具体说，决定哪些指令打包在一起的pass应该在代码从SSA形式退出之后做，需要在虚拟寄存器改写为物理寄存器之后完成。这就不再需要将虚拟寄存器操作数添加到BUNDLE指令中。
MC层用来表示和处理原始机器码级别的代码，已经不再存在诸如常量池、跳转表、全局变量等高层次的概念。在MC层，LLVM处理诸如label名称，机器指令，目标文件中section等。这层的代码有几个重要目的：代码生成器用它生成.s或.o文件，llvm-mc工具用它实现独立的机器码汇编器和反汇编器。
以下讲述几个重要的相关类：
最好将MCStreamer看做是汇编器API，它是抽象的，可以用不同方式实现，比如生成.s、生成.o就是不同的方式。MCStreamer对于每种directive都有一个方法，比如EmitLable, EmitSymbolAttribute, switchSection, emitValue等，这些都对应着汇编级别的概念。还有一个EmitInstruction方法，用来输出MCInst。
这套API有两个重要的客户：llvm-mc独立汇编器和代码生成器的代码发射阶段。
MCStreamer有两个主要的实现：一个用来输出.s文件，另一个用来输出.o文件。输出.o文件的MCObjectStreamer实现了一个完整的汇编器。
对于目标机器特定的directive，MCStreamer有一个MCTargetStreamer实例，一个目标机如果需要实现特定的directive，那么就需要从该类继承。这个自定义的子类需要对每个directive定义一个方法，同时还需要定义两个子类，分别生成asm和obj。
目标机的初始化代码还需要调用TargetRegistry::RegisterAsmStreamer和TargetRegistry::RegisterMCObjectStreamer将对应的streamer进行注册。
该类是MC层各种数据结构的所有者，包括symbols, sections等。若要创建symbol和section，就要与该类交互。该类不可被继承。
该类代表汇编文件中的一个symbol (aka label)。symbol有两种：汇编器临时symbol、正常symbol。汇编器临时symbol是被汇编器使用并处理的，并在生成obj文件时被丢弃。常见的做法是在label名前加前缀以示区别。
MCSymbol是被MCContext创建的，并保证唯一性。这意味着两个MCSymbol可以通过比较指针是否相等来判断同一性。但是指针不相等却不能保证它们最终映射到不同的地址。如下的输出在.s文件中是合法的：
|
|
这种情况下，foo和bar具有相同的地址。
该类代表一个obj文件的section。可以被继承以实现各种不同格式的obj文件，如ELF。它是被MCContext创建的并保证唯一性。MCStreamer中有当前section的概念，可以通过SwitchToSection来改变当前section（这个概念与.s文件中的.section directive相当）。
该类是一条指令的机器无关表示。这是一个很简单的类（相对于MachineInstr来说），只包含了特定机器的操作码和一系列MCOperands。而MCOperand只是一个包含了三种情况的union：1) 简单立即数 2）寄存器ID 3) 符号表达式MCExpr（如Lfoo-Lbar+42）
MC层的obj文件输出器支持多种obj格式。实际上每个目标机支持的格式仅仅是MC层提供的子集。大部分机器支持ELF格式，而其他机器可能还有它们自己定义的格式。
2024-02-01 16:06:00
LLVM IR中有两个特殊的关键字：undef和poison，它们分别代表两种特殊的常量，是常见的编程语言中没有的概念。
undef用来表示该常量有可能取任意值，这有利于编译器做优化，因为编译器可以用任意值来替代undef。
需要注意的是，undef的取值可以在其活跃范围内随时变化，这会带来一些违反直觉的结果。比如：
|
|
与之等价的是 %B = undef ，而不是直观上的 %B = 0 。
poison用来表示错误操作的结果。
典型的例子是，带有nsw/nuw flag的add指令，如果结果溢出，就会产生poison结果。
对于大多数指令（除了select），如果有一个操作数是poison，那么其结果也是poison。
与undef和poison密切相关的一条指令是freeze，它是用来停止undef/poison的传播的。
如果其操作数是undef/poison，那么其结果就变成了固定值（具体是多少是任意取的）；如果是其他操作数，则相当于一条nop。比如：
|
|
这段代码的执行结果会是： %C = 0 。
从语义角度看，poison是比undef更「强」的概念。
在能使用poison的地方，用undef来替代是安全的，反之则不然。
而从有利于优化的角度来看，应该尽可能使用poison，因为这相当于让编译器看到了更「具体」的信息，可以做更激进的优化。
2024-01-30 10:25:00
人是社会性动物，要在这个社会上生存，显然无法避开人际关系这个课题。而要创造良好的人际关系，就必须学会沟通。 不管是日常生活中的交朋友、谈恋爱，还是工作中的合作共赢，抑或是读书写作，只要需要与人打交道，就需要沟通。 可以说，沟通涉及到生活的方方面面，沟通能力的高低，直接或间接影响着我们的生活质量和幸福感，其重要性不言而喻。
《沟通的艺术》是一本专门讨论「沟通」的心理学书籍，它被多次再版（目前最新版是第15版），足见其受到的认可程度。 沟通能力，尽管受到许多先天因素的影响，但是其中仍然有不少技巧是可以通过学习而掌握的。如果你想提高沟通能力，不妨看看这本书。
该书第一章对「为什么要沟通」有更详尽的描述，从更科学的角度说明了沟通的重要性。
生理需求
沟通质量会直接影响我们的身体健康。
认同需求
我们在人际沟通中认识自己，知道「我是谁」。
社交需求
积极的关系是我们生活满足感和情绪幸福感的重要来源。
实际目标
沟通是我们完成具体任务（如工作）所需要的，良好的沟通能够使我们更有效率达到目标。
马斯洛把人的需求划分为五个层次：生理需求、安全需求、社交需求、自尊需求、自我实现需求。显然，沟通能力对于实现各个层次的需求都是必要的。
要想成为沟通高手，首先要看看沟通高手有哪些突出的特质，以便在我们自己练习时明确努力的方向。
以下列举了沟通高手具有的一些特质，以及对于每项特质的提高，我们需要在哪些方向上努力。我们可以反省一下自己在这些方面是否有不足，然后针对自己的不足，在实践中刻意练习。
拥有多样化的行为资料库
用心观察，归纳总结
挑选恰当行为的能力
考虑三个因素：当时的具体情境/自己的目的/对对方的认知
表现行为的技巧
刻意练习，孰能生巧
认知复杂度
知觉核验
描述对方的行为，列出关于此行为的至少两种可能的诠释，请求对方对行为诠释作澄清
枕头法
从多个角度看问题：我对你错，你对我错，双方都有对有错，这个议题不重要，前面几个立场都有道理
同理心
自我监控：以超然的眼光看待自己的所作所为
承诺：对沟通的重视意愿
以上是我的摘录，也是我认为该书的精华所在。如果你想了解更多，请直接读原书，很值得一读。
2024-01-26 10:18:29
PS: 这篇文章已经过时，最新解决方案请参考：链接
软件开发工作中，用ssh登录后在远程机器上操作，常常需要从远程机器上往本地复制文本。如果是小段的文本，一般在终端选中即可在本地粘贴；但是如果是大段的文本（超过一个屏幕），就没法一次性选中，复制操作变得很麻烦。这里提供一种方法，利用ssh reverse tunnel，可以很方便地将远程大段文本拷贝到本地。
基本思路是：在本地开启一个服务，其监听端口为5689，这个服务持续地将接收到的文本拷贝到剪贴板；利用ssh reverse tunnel将远程机器上的5689端口与本地的5689端口连接起来；在远程机器上，将需要复制的大段文本发送到其5689端口，这段文本就会出现在本地机器的剪贴板里。
命令行中执行以下代码：
|
|
启动netcat监听5689端口，将接收到的任何数据拷贝到剪贴板，然后继续监听。
现在，可以在本地测试一下效果：
|
|
ssh reverse tunnel 可以在远程机器和本地机器之间建立一个通道，在远程机器和本地机器各指定一个端口，并将它们连接在一起，这是通过-R参数实现的。
|
|
也可以将此配置写入.ssh/config，在对应的host条目里添加下面这行，以后登录ssh都会自动建立这个通道。
|
|
现在，可以在远程机器上执行以下命令测试一下效果：
|
|
经过以上步骤，只要在远程机器上将数据发往其5689端口，数据就会出现在本地剪贴板了。不过我最常用的场景是在vim中复制文本，把这部分操作进一步简化就很有必要了。为此，我在.vimrc中添加如下代码：
|
|
添加了一个自定义命令CL，执行这个命令时，被选中的文本就会发送到5689端口，进而传回到本机的剪贴板。
如此，当我在远程机器上的vim中想要复制文本时，我就先选中这段文本，然后执行命令:CL，接下来就可以从本地机器的剪贴板粘贴了。
在远程机器的.bashrc中设置以下命令：
|
|
在本地机器的.bashrc中设置以下命令：
|
|
这样，分别在远程和本地机器上执行以下命令（会利用base64工具的编码和解码功能）：
|
|
就可以将远程机器上的file文件复制到本地了。
2024-01-12 00:53:56
关于人生的意义，《活出生命的意义》一书中说：“人不应该问他的生命之意义是什么，而必须承认是生命向他提出了问题。简单地说，生命对每个人都提出了问题，他必须通过对自己生命的理解来回答生命的提问。”你会如何回答这个问题呢？
于我而言，人生中最重要的是体验，体验到一种成就感、意义感、幸福感。回顾我自己的人生经历，结合对历史上我所敬佩的那些人的观察，我发现我长久以来孜孜以求的，就是这几种感觉。当我通过运用自己的能力，做好一件事，或者完成一件作品，我会体验到一种成就感，这种成就感会给我长久的满足。当我知道我为什么做一件事，知道我做的事情会对他人产生正面影响，我会感到这件事是有意义的，这种意义感也会给我长久的满足。这些都是幸福感的重要来源。相反，如果做事时常常挫败，或者不知道自己做的事是为了什么，就很容易陷入沮丧和消沉。
那么怎么更多获得这样的正面体验呢？根据著名的马斯洛需求层次理论，越高层次需求的满足，特别是自我实现，越能给我们带来成就感、意义感和幸福感。而自我决定论指出，人的三种内在动机包括自主感、胜任感和归属感，当我们在做一件事的过程中，感到这件事不是被迫做的，感到自己有足够的能力做好这件事，感到做好这件事能给他人带来正面影响，我们就会由衷地感到满足。我们应该尽可能多做这样的事情。
《象与骑象人》指出，幸福的两大原则是：进展原则和适应原则。进展原则是说，达到目标后的幸福是短暂的，朝着目标不断前进比达到目标更幸福。适应原则是说，从长远来看，我们总会适应所遇到的“顺境”或“逆境”。因此不可能存在一个能永保幸福的标准，不可能说得到了某件事物，做成了某件事情，就保证幸福了。在我们的一生中，我们必须不停地做事情，制定目标，全力以赴去实现目标。但是须谨记，应该在这整个过程中去体验幸福感，而不是寄希望于达成目标的那一刹那。
如何看待世俗所追求的名和利呢？最好的态度是把名利视为做事的工具，而不是最终目的。名利显然不等于幸福，也未必带来幸福，利欲熏心者最终只能成为名利的奴隶。但也不必排斥名利，首先，作为凡夫俗子，多多少少会有名利心，这是很正常的；其次，如果出发点是善的，更多的财富，更好的名声，可以使我们更加便利地做事，给他人带来更多的帮助；再次，在做事的过程中，当我们为社会解决了更多的问题，名声和财富常常会随之自然而来，强行拒之门外反而是不自然的，佛家说莫执着，沉湎于名利是执着，而避之唯恐不及恐怕也是一种执着。
人终究走向死亡，正如佛陀所说，“如梦幻泡影，如露亦如电”。 在死亡面前，一切都如过眼云烟，微不足道。如果说人生是个梦，我依然希望是精彩的梦，梦中全心全意去体验。
我相信，到这个世界上我们是带着使命来的，我们每个人都有独一无二的天赋。我们需要相信天道，充分发挥天赋，不断超越自己，去做事，去解决问题，去创造属于自己的作品，给这个世界增添一些属于自己的色彩，就不枉来这世上走一遭了。
PS: 翻看自己的日志，发现自己多年前写过一篇小文明吾志，原来自己那时就已经在思考这些问题了。能够看出，今天的很多看法在当时已有萌芽，可以说是一脉相承的。只是，当时思考比较简单，不够深入，不成体系，在随后的这些年里也并未踏实践行，在遇到挫折时常常会怀疑自己，踌躇不定，这也导致这些年走了不少弯路。不过，随着人生经历的增加，读了一些书，行了一些路，识了一些人，自己对这些问题的认识和体会也更加深刻。虽然看似又回到了原点，但其实深度不可同日而语。马克思说事物的发展是螺旋上升的，我想我的思想认识也是如此。对自己是谁更加清晰，对自己要去哪儿更加坚定，我想这也是那些弯路的价值。人生没有白走的路，那些杀不死我的，必将使我更强大。
