LLVM Cpu0 新后端7 第二部分 窥孔优化
想好好熟悉一下llvm开发一个新后端都要干什么，于是参考了老师的系列文章：
LLVM 后端实践笔记
代码在这里（还没来得及准备，先用网盘暂存一下）：
链接: https://pan.baidu.com/s/1yLAtXs9XwtyEzYSlDCSlqw?pwd=vd6s 提取码: vd6s
这一章会介绍与控制流有关的功能实现，比如 if、else、while 和 for 等，还会介绍如何将控制流的 IR 表示转换为机器指令；之后会引入几个后端优化，处理一些跳转需求引入的问题，同时来说明如何编写后端优化的 pass。在条件指令小节中，会介绍 LLVM IR 中的特殊指令 select 和 select_cc，以及如何处理这种指令，从而来支持更细节的控制流支持实现。
目录
一、第三节
1.1 新增的文件
1.1.1 Cpu0DelaySlotFiller.cpp
1.2 修改的文件
1.2.1 Cpu0.h
1.2.2 Cpu0TargetMachine.cpp
1.2.3 Cpu0AsmPrinter.cpp
二、第四节
2.1 修改的文件
2.1.1 Cpu0InstrInfo.td
2.1.2 Cpu0ISelLowering.cpp/.h
2.2 窥孔优化
一、第三节
这是个功能性的 pass。很多 RISC 机器采用多级流水线设计，有些 phase 会产生延迟，为了保证软件运行正确，可能会需要软件（编译器）在需要延迟的指令做处理。Cpu0 就符合这种情况，对于所有的跳转指令，需要有一个 cycle 的延迟，编译器需要负责对这些跳转指令做延迟插入指令。为了让实现简单，我们目前的实现只是将一条 nop 指令填充到跳转指令之后。有关于将其他有用的指令插入到跳转之后，可以参考 Mips 的实现（更加有意义，不单单是一条无用的等待），比如 MipsDelaySlotFiller.cpp 文件。
jne $sw, $BB_0
nop // 这里是插入的指令
$BB_1:
... other instructions对于 jne 指令，因为需要为其填充延迟指令，所以实际我们代码运行之后，会在汇编中，jne 的下一条指令，输出一条 nop 指令，这样就可以保证在 jne 执行完毕之后，再进行后续的运行。
与上一节的设计类似，我们依然是设计一个 pass，专门去识别这样一个模式，并创建一个 nop 指令并与跳转指令打到一个 bundle 中。bundle 是 LLVM 在 MI 层支持的一种指令扩展，它会在 bundle emit 之前，将 bundle 看做一条指令，而 bundle 内部却可以包含多条指令。
1.1 新增的文件
1.1.1 Cpu0DelaySlotFiller.cpp
新 pass 的实现代码。和上一小节类似的实现就不赘述了。
定义了一个 hasUnoccupiedSlot() 函数，用来判断某条指令是否满足我们上文指定的模式，首先判断这条指令是否具有延迟槽，调用 hasDelaySlot() 函数，然后判断这条指令是否已经属于一个 bundle 或者是最后一条指令，调用 isBundledWithSucc() 函数。这两个函数都是 LLVM 内置函数，在 MachineInstr.h 中实现。
当满足条件时，先使用 BuildMI 创建 nop 指令，并插入到跳转指令的后边；然后调用 MIBundleBuilder 函数，将跳转指令和 nop 指令打到一个 bundle。
1.2 修改的文件
1.2.1 Cpu0.h
添加创建新 pass 的工厂函数。
1.2.2 Cpu0TargetMachine.cpp
在 addPreEmitPass() 函数中增加我们的 pass，和上一小节同理。
1.2.3 Cpu0AsmPrinter.cpp
void Cpu0AsmPrinter::emitInstruction(const MachineInstr *MI) {
......
do {
if (I->isPseudo())
llvm_unreachable("Pseudo opcode found in emitInstruction()");
MCInst TmpInst0;
MCInstLowering.Lower(&*I, TmpInst0);
OutStreamer->emitInstruction(TmpInst0, getSubtargetInfo());
} while ((++I != E) && I->isInsideBundle()); // Delay slot check
}这里是汇编代码发射的地方，需要检查要发射的指令是否是 bundle，如果是，则将 bundle 展开，依次发射其中的每一条指令。这一个 while 代码在之前的章节已经添加。如果不做这个检查，则只有 bundle 中的第一条指令会被发射，这将会导致代码错误。
二、第四节
在这一节我们会增加条件MOV指令。条件 MOV 指令也叫做 Select 指令，和 C 语言中的 select 操作语义一致，由一个条件值、两个指定值和一个定义值（输出）组成。在满足一个条件时，将指定值赋给定义值，否则把另一个指定值赋给定义值。我们在 Cpu0 中将实现两条 MOV 指令，分别是 movz 和 movn，表示当条件成立时（或条件不成立时），赋值第一个值，否则，赋值另一个值。
由于编码位有限，通常的条件 MOV 指令和 Select 指令均设计为其中一个指定值与定义值是同一个操作数（或者也有设计为条件值与定义值是同一个操作数）：
movz $1, $2, $3; @ $3 为条件值，当 $3 满足（为 true）时，将 $2 赋值给 $1,
@ 否则，保持 $1 值不变
movn $1, $2, $3; @ $3 为条件值，当 $3 不满足（为 false）时，将 $2 赋值给 $1,
@ 否则，保持 $1 值不变可以发现，movz 和 movn 是可以相互替代的，即：
movz $1, $2, $3; @ 等价于
movn $2, $1, $3; @ 当然，还需要保证上下文数据正确在 LLVM IR 中，只有一个指令来处理这个情况，叫做 select 指令，我们需要做的就是在后端代码中，将这个 IR 转换为正确的指令表示：
%ret = select i1 %cond, i32 %a, i32 %b2.1 修改的文件
2.1.1 Cpu0InstrInfo.td
新增和条件 MOV 相关的指令实例和用于窥孔优化的 Pattern 描述。
前者即定义 movz 和 movn 指令。注意到在 class 中使用 let Constraints = “$F = $ra” 的属性来指定两个操作符是同一个值，这种写法通常用于当其中一个 def 操作数同时也需要作为 use 操作数的情况下，比如当前的 select 示例中。
各种Pat模式中是将 IR 过来的 select + cmp 节点组合优化为一条 movz 或 movn 指令。select 指令的 condition 需要一条比较（或其他起相同作用的）指令来得出条件结果，在 Cpu032I 机器中是 cmp 指令，在 Cpu032II 机器中是 slt 指令。因为通常比较两个值是否相等，还可以采用 xor 指令，所以对于低效的 Cpu032I 比较 cmp 指令，可以使用 xor 做替换，但对于大于、小于等条件代码则只能继续使用 cmp 指令，体现在 .td 文件中就是不特别去优化 select 指令组合下的条件指令。
这个优化的路径是：
IR: icmp + (eq, ne, sgt, sge, slt, sle) + br
DAG: ((seteq, setne, setgt, setge, setlt, setle) + setcc) + select
Cpu0: movz, movn2.1.2 Cpu0ISelLowering.cpp/.h
需要做一点配置。首先，LLVM 的后端会默认把 SetCC 和 Select 两个 Node 合并成一条 Select_cc 指令，这是为能够支持 Select_cc 指令的后端而准备的，这种指令是通过 condition code 来作为 select 指令的条件，比如在 X86 机器中。我们的 Cpu0 不支持这种指令，所以需要在 Cpu0ISelLowering.cpp 中，将 Select_cc 设置为 Expand 类型，表示我们希望 LLVM 帮我们替代这个类型的节点。
另一件事是将 ISD::SELECT 这个 Node 的默认下降关掉，也就是设置其为 Custom 类型，在我们自定义的下降中，直接将这个 Node 返回。因为我们不希望 select Node 在 lowering 阶段被选择为 select，这样它会无法选到指令。我们的条件 MOV 指令和这里的 select 指令有一些差异，所以只能通过在指令选择时的优化合并来实现从 select Node 到后端指令的 lowering。
2.2 窥孔优化
上边提到了一个名词窥孔优化，这里简单介绍一下。
窥孔优化（Peephole Optimization）是一种编译器优化技术，通常在生成目标代码的最后阶段应用。窥孔优化通过在目标代码中寻找和替换特定的指令序列，以改进代码的效率和性能。这种优化技术通常针对短小的指令序列，称为“窥孔”（peephole），并尝试通过替换这些指令序列来提高代码的质量。
窥孔优化的目标是通过识别和替换无效、低效或冗余的指令序列，以减少指令的执行次数、减少内存访问或提高代码的局部性，从而提高程序的性能。这种优化技术通常是基于一组预定义的优化规则或模式，编译器会在目标代码中寻找这些模式，并根据规则进行相应的优化操作。
通过窥孔优化，编译器可以在不改变程序逻辑的情况下，对生成的目标代码进行微调和改进，以使程序在运行时更加高效。这种优化技术在编译器中扮演着重要的角色，有助于提高代码的执行速度、减少资源消耗，并改善程序的整体性能。
窥孔优化其实不单单指一种优化，泛指后端多种指令层面的优化，我们后端流水线里默认就带有这个pass：
void TargetPassConfig::addMachineSSAOptimization() {
......
addPass(&PeepholeOptimizerID);
// Clean-up the dead code that may have been generated by peephole
// rewriting.
addPass(&DeadMachineInstructionElimID);
}LLVM的窥孔优化是在PeepholeOptimizer.cpp这个文件里实现的。文件头的注释中例举出来了几个优化的典型场景。
