cpu0中LLVM编译控制流
7.7.1 控制流
会介绍与控制流有关的功能实现，比如 if、else、while 和 for 等，还会介绍如何将控制流的 IR 表示转换为机器指令；之后会引入几个后端优化，处理一些跳转需求引入的问题，说明如何编写后端优化的pass。在条件指令中，会介绍LLVM IR中的特殊指令select和 select_cc，以及如何处理这种指令，从而来支持更细节的控制流实现。
7.7.2 控制流语句
1. 简要说明
从机器层面上来看，所有的跳转只分为无条件跳转和有条件跳转，从跳转方式上来分，又分为直接跳转（绝对地址）和间接跳转（相对偏移），所以只需要将LLVM IR的跳转node，成功下降到机器跳转指令，并维护好跳转的范围、跳转的重定位信息即可。
Cpu032I 型机器支持 J 类型的跳转指令，比如无条件跳转JMP，有条件跳转JEQ、JNE、JLT、JGT、JLE、JGE，这部分指令是需要通过检查条件代码（SW 寄存器）来决定跳转条件的；Cpu032II 型机器除了支持 J 类型跳转指令之外，还支持 B 类型的跳转指令，比如 BEQ 和 BNE，这两个是通过直接比较操作数值关系来决定跳转条件的。相比较，后者的跳转依赖的资源少，指令效率更高。
SelectionDAG 中的 node，无条件跳转是ISD::br，有条件跳转是ISD::brcond，需要在 tablegen中通过指定指令选择 pattern 来对这些Node做映射。
另外，J 类型指令依赖的条件代码是通过比较指令（比如 CMP）的结果来设置的，在之前的内容已经完成了比较指令，LLVM IR 的SetCCnode 通常会被翻译为 addiu reg1, zero, const + cmp reg1, reg2 指令。
2. 文件修改
1）Cpu0ISelLowering.cpp
设置需要的几个Node为Custom的lowering类型，即会通过自定义的lowering操作来处理它们，这包括 BlockAddress，JumpTable 和 BRCOND。这分别对应 lowerBlockAddress()，lowerJumpTable() 和 lowerBRCOND() 函数，其中 getAddrLocal() 和 getAddrNonPIC() 是前边内容已经实现的自定义Node生成函数。BRCOND 是条件跳转节点（包括 condition 的 op与condition 为 true 时，跳转的 block 的地址），BlockAddress 字面可知是 BasicBlock 的起始地址类型的节点，JumpTable 是跳转表类型的节点。后两者是叶子节点类型。
另外，设置SetCC在 i1 类型时做 Promote。增加了几行代码来说明额外的一些 ISD 的Node需要做 Expand，就是采用 LLVM 内部提供的一些展开方式来展开这些不支持的操作。这些操作包括：BR_JT，BR_CC，CTPOP，CTTZ，CTTZ_ZERO_UNDEF，CTLZ_ZERO_UNDEF。其中 BR_JT 操作的其中一个 op 是 JumpTable 类型的节点（保存 JumpTable 中的一个 index）。BR_CC 操作和Select_cc操作类似，区别是它保存有两个op，通过比较相对大小来选择不同的分支。
2）Cpu0InstrInfo.td
增加两个和跳转有关的操作数类型：brtarget16 和 brtarget24，前者是 16 位偏移的编码，将用于 BEQ、BNE 一类的指令，这一类指令是属于 Cpu032II 型号中特有；后者是 24 位偏移的编码，将用于 JEQ、JNE 一类的指令。两个操作数均指定了编码函数和解码函数的名称。还定义了 jmptarget 操作数类型，用来作为无条件跳转JMP的操作数。
之后便是定义这几条跳转指令，包括它们的匹配 pattern 和编码。
无条件跳转JMP的匹配 pattern 直接指明到了 [(br bb::$addr)]，很好理解。
然后做一些优化来定义比较+跳转指令选择 Pattern，也就是将 brcond + seteq/setueq/setne/setune/setlt/setult/setgt/setugt/setle/setule/setge/setuge 系列模式转换为机器指令的比较+跳转指令组合。对于 J 系列的跳转指令，实际上会转换为 Jxx + CMP 模式，而对于 B 系列的跳转指令，则直接转换成指令本身。
比如：
def : Pat<(brcond (i32 (setne RC:$lhs, RC:$rhs)), bb:$dst), (JNEOp (CMPOp RC:$lhs, RC:$rhs), bb:$dst)>;
def : Pat<(brcond (i32 (setne RC:$lhs, RC:$rhs)), bb:$dst), (BNEOp RC:$lhs, RC:$rhs, bb:$dst)>;
无法从 C 语言生成 setueq 和 setune 指令，所以实际上并不会对其做选择（不过考虑到不要过分依赖前端，还是实现了）。
3）Cpu0MCInstLower.cpp
因为跳转的地址既可以是跳转表偏移，也可以是一个 label，所以需要在 MachineOperand 这里对相关的类型做 lowering。在 LowerSymbolOperand() 函数中增加对 MO_MachineBasicBlock、MO_BlockAddress 和 MO_JumpTableIndex 类型的 lowering。
4）Cpu0MCCodeEmitter.h/cpp
实现地址操作数的编码实现函数，包括 getBranch16TargetOpValue()，getBranch24TargetOpValue() 和 getJumpTargetOpValue() 函数，对JMP指令同时还是表达式类型的跳转位置的情况，选择正确的 fixups，fixups 类型在 Cpu0FixupKinds.h 文件中定义。
5）Cpu0AsmPrinter.h/cpp
定义一个名为 isLongBranchPseudo() 的函数，用来判断指令是否是长跳转的伪指令。
同时在 EmitInstruction() 函数中，增加当属于长跳转伪指令时，不发射该指令。
6）MCTargetDesc/Cpu0FixupKinds.h
添加重定位类型 fixup_Cpu0_PC16 和 fixup_Cpu0_PC24。
7）MCTargetDesc/Cpu0ELFObjectWriter.cpp
添加重定位类型的一些设置，在 getRelocType() 函数中增加内容。
8）MCTargetDesc/Cpu0AsmBackend.cpp
Cpu0 的架构和其他RISC机器一样，采用五级流水线结构，跳转指令会在 decode 阶段实现跳转动作（也就是将 PC 修改为跳转后的位置），但跳转指令在 fetch 阶段时，PC 会自动先移动到下一条指令位置，fetch 阶段在 decode 阶段之前，所以实际上，在 decode 阶段执行前，PC 已经自动+4（一个指令长度），所以实际上跳转指令中的偏移，并不是从跳转指令到目标位置的差，而应该是跳转指令的下一条指令到目标位置的差。
比如说：
jne $BB0_2
jmp $BB0_1 #jne指令 decode 之前，PC 指向这里
$BB0_1:
ld $4, 36($fp)
addiu $4, $4, 1
st $4, 36($fp)
jmp $BB0_2
$BB0_2:
ld $4, 32($fp) #jne指令 decode 之后，假设 PC 指向这里
jne 指令中的偏移，应该是JMP指令到 最后一条 ld 指令之间的距离，也就是 20 （而不是 24）。
为了实现这样的修正，在 adjustFixupValue() 函数中，针对重定位类型 fixup_Cpu0_PC16 和 fixup_Cpu0_PC24，指定其 Value 应该在自身的基础上减 4。
3. 检验成果
编译提供的测试用例 ch7_1_controlflow.c，使用 Cpu032I 生成的汇编如：
...
cmp $sw, $3, $2
jne $sw, $BB0_2
jmp $BB0_1
$BB0_1:
ld $4, 4($sp)
addiu $4, $4, 1
st $4, 4($sp)
jmp $BB0_2
$BB0_2:
ld $2, 4($sp)
...
可见 Cpu032I 处理器使用 sw 寄存器和 J 系列跳转指令，完成控制流操作。
使用 Cpu032II 生成的汇编如：
...
bne $2, $zero, $BB0_2
jmp $BB0_1
$BB0_1:
ld $4, 4($sp)
addiu $4, $4, 1
st $4, 4($sp)
jmp $BB0_2
$BB0_2:
ld $2, 4($sp)
Cpu032II 处理器使用 B 系列跳转指令，完成控制流操作，指令数更少。
通过 Cpu032I 直接生成二进制代码：
build/bin/llc -march=cpu0 -mcpu=cpu032I -relocation-model=pic -filetype=obj ch7_1_controlflow.ll -o ch7_1_controlflow.o
hexdump ch7_1_controlflow.o
通过 hexdump 可以将二进制代码输出到终端。从其中找到 31 00 00 14 36 00 00 00 这段编码，31 是jne指令，36 是JMP指令，14 是偏移的编码，可见这里偏移是 20，说明 Cpu0AsmBackend.cpp 中的设计生效了。
7.7.3 消除无用的JMP指令
LLVM的大多数优化操作都是在中端完成，也就是在LLVM IR下完成。除了中端优化以外，其实还有一些依赖于后端特性的优化在后端完成。比如说，Mips机器中的填充延迟槽优化，就是针对RISC下的pipeline优化。如果后端是一个带有延迟槽的pipeline RISC机器，那么也可以使用Mips的这一套优化。
实现一个简单的后端优化，叫做消除无用的JMP指令。这个算法简单且高效，可以作为一个优化的教程来学习，通过学习，也可以了解如何新增一个优化pass，以及如何在真实的工程中编写复杂的优化算法。
1. 简要说明
对于如下汇编指令：
JMP $BB_0
$BB_0:
... other instructions
在JMP指令的下一条指令，就是JMP指令需要跳转的 BasicBlock 块，因为JMP指令是无条件跳转，所以这里的控制流必然会做顺序执行，进而可以明确这里的JMP指令是多余的，即使删掉这条JMP指令，程序流也一样可以执行正确。
所以，目的就是识别这种模式，并删除对应的JMP指令。
2. 文件修改
1）CMakeLists.txt
添加新文件 Cpu0DelUselessJMP.cpp。
2）Cpu0.h
声明这个pass的工厂函数。
3）Cpu0TargetMachine.cpp
覆盖 addPreEmitPass() 函数，在其中添加pass。调用这个函数表示，pass会在代码发射之前被执行。
3. 文件新增
1）Cpu0DelUselessJMP.cpp
这是实现该优化pass的具体代码。有几个具体要留意的点：
代码：
#define DEBUG_TYPE "del-jmp"
...
LLVM_DEBUG(dbgs() << "debug info");
这里是为优化pass添加一个调试宏，这样可以通过在执行编译命令时，指定该调试宏来打印出想要的调试信息。注意需要以 debug 模式来编译，并且在执行编译命令时，指定参数：
llc -debug-only=del-jmp
或直接打开所有调试信息：
llc -debug
其次，看以下代码：
STATISTIC(NumDelJmp, "Number of uselessJMPdeleted");
表示定义了一个全局变量 NumDelJmp，可以允许在执行编译命令时，当执行完毕时，打印出这个变量的值。这个变量的作用是统计这个优化pass，一共消除了多少的无用JMP指令，变量的累加是在实现该pass的逻辑中，手动设计进去的。
在执行编译命令时，指定参数：
llc -stats
就可以打印出所有的统计变量的值。
其次，有以下代码：
static cl::opt<bool> EnableDelJmp(
...
...
);
2）新增代码解析
这部分代码是向 LLVM 注册了一个编译参数，参数名称是这里第一个元素，还指定了参数的默认值，描述信息等。使用参数名为：enable-cpu0-del-useless-jmp，默认是打开的。这就是说，如果指定了这个参数，并且令其值为 false，则会关闭这个优化pass。
具体的实现代码中，继承了 MachineFunctionPass 类，并在 runOnMachineFunction 中重写了逻辑，这个函数会在每次进入一个新的 Function 时被执行。在内部逻辑中调用了 runOnMachineBasicBlock 函数，同理，这个函数在每进入一个新的 BasicBlock 时被执行。
在每个函数中遍历每一个基本块，直接取其最后一条指令，判断是否为JMP指令，再判断这条指令指向的基本块是否是下一个基本块。如果都满足，则调用 MBB.erase(I) 删除 I 指向的指令（jmp 指令），并且累加 NumDelJmp 变量。
4. 检验成果
执行提供的测试用例：ch7_2_deluselessjmp.cpp
build/bin/llc -march=cpu0 -relocation-model=static -filetype=asm -stats ch7_2_deluselessjmp.ll -o -
查看输出汇编，会发现已经没有JMP指令，输出 statistics 信息中8 del-jmp告诉删除了8条无用的JMP指令。可以关闭这个优化再查看汇编（添加 -enable-cpu0-del-useless-jmp=false），两次结果做对比。
7.7.4 填充跳转延迟槽
这是个功能性的pass。很多RISC机器采用多级流水线设计，有些phase会产生延迟，为了保证软件运行正确，可能会需要软件（编译器）在需要延迟的指令做处理。Cpu0 就符合这种情况，对于所有的跳转指令，需要有一个 cycle 的延迟，编译器需要负责对这些跳转指令做延迟插入指令。为了让实现简单，目前的实现只是将一条nop指令填充到跳转指令之后。将其他有用的指令插入到跳转之后，可以参考Mips的实现（更加有意义，不单单是一条无用的等待），比如 MipsDelaySlotFiller.cpp 文件。
1. 简要说明
对于如下汇编指令：
jne $sw, $BB_0
nop // 这里是插入的指令
$BB_1:
... other instructions
对于jne指令，因为需要为其填充延迟指令，所以实际代码运行之后，会在汇编中，jne的下一条指令，输出一条nop指令，这样就可以保证在jne执行完毕之后，再进行后续的运行。
与上一节的设计类似，依然是设计一个pass，专门去识别这样一个模式，并创建一个nop指令并与跳转指令打到一个bundle中。bundle 是 LLVM 在 MI 层支持的一种指令扩展，它会在bundleemit 之前，将bundle看做一条指令，而bundle内部却可以包含多条指令。
2. 文件修改
1) CMakeLists.txt
添加新增的文件 Cpu0DelaySlotFiller.cpp。
2) Cpu0.h
添加创建新pass的工厂函数。
3) Cpu0TargetMachine.cpp
在 addPreEmitPass() 函数中增加pass。
4) Cpu0AsmPrinter.cpp
这里是汇编代码发射的地方，需要检查要发射的指令是否是 bundle，如果是，则将bundle展开，依次发射其中的每一条指令。这一个while代码在之前的内容已经添加。如果不做这个检查，则只有bundle中的第一条指令会被发射，这将会导致代码错误。
3. 文件新增
Cpu0DelaySlotFiller.cpp
新pass的实现代码。
定义了一个 hasUnoccupiedSlot() 函数，用来判断某条指令是否满足上文指定的模式，首先判断这条指令是否具有延迟槽，调用 hasDelaySlot() 函数，然后判断这条指令是否已经属于一个bundle，或者是最后一条指令，调用 isBundledWithSucc() 函数。这两个函数都是 LLVM 内置函数，在 MachineInstr.h 中实现。
当满足条件时，先使用BuildMI创建nop指令，并插入到跳转指令的后边；然后调用 MIBundleBuilder函数，将跳转指令和nop指令打到一个bundle。
4. 检验成果
没有额外提供测试用例，可以通过编译上一节的 ch7_2_deluselessjmp.cpp，查看输出的汇编内容，加 -stats 参数，输出共填充了 5 个这样模式的延迟槽。
7.7.5 条件MOV指令
1. 简要说明
条件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指令：
%ret =selecti1 %cond, i32 %a, i32 %b
所以需要做的就是在后端代码中，将这个 IR 转换为正确的指令表示。
2. 文件修改
1) Cpu0InstrInfo.td
新增和条件MOV相关的指令实例，以及用于窥孔优化的 Pattern 描述。
前者即定义movz和movn指令。注意到在class中使用 let Constraints = "$F = $ra" 的属性来指定两个操作符是同一个值，这种写法通常用于当其中一个def操作数，同时也需要作为use操作数的情况下，比如当前的select示例中。
后者是将 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, movn
2) Cpu0ISelLowering.h/.cpp
需要做一点配置。首先，LLVM的后端会默认把SetCC和select两个Node合并成一条 Select_cc指令，这是为能够支持Select_cc指令的后端而准备的，这种指令是通过条件代码来作为select指令的条件，比如在X86机器中。Cpu0不支持这种指令，所以需要在 Cpu0ISelLowering.cpp 中，将Select_cc设置为 Expand 类型，表示希望 LLVM 帮替代这个类型的节点。
另一件事是将 ISD::SELECT 这个Node的默认下降关掉，也就是设置其为Custom类型，在自定义的下降中，直接将这个Node返回。因为不希望selectNode在lowering阶段被选择为select，这样它会无法选到指令。条件MOV指令和这里的select指令有一些差异，所以只能通过在指令选择时的优化合并，来实现从selectNode 到后端指令的lowering。
3. 检验成果
这一小节提供了 3 个case，第一个case（ch7_4_select.c）是最简单的情况，直接使用 C 语言中的三目运算符，clang会在不开优化的情况下将其生成为IR Select。
第二个case(ch7_4_select2.c) 没有使用三目运算符，clang在不开优化的编译下，会生成两个BB块，通过跳转实现功能，只有在启用至少-O1优化下，才会生成为IR Select。
第三个case(ch7_4_select_global_pic.c) 引入了全局变量，测试在全局变量与select混合的情况下，是否能正常处理代码。
三个case的编译命令均与之前相同。
4. 小结
再补充几个知识点。静态单赋值形式的表示形式，在对待多分支的控制流时，会遇到多赋值的问题。LLVM IR处理这个问题的方式是引入Phi节点，Phi节点是一种特殊的操作，它允许操作中通过判断控制流的流向，来选择要赋值的值，从而避免了多赋值问题。
这种操作只有在 clang 启用优化的情况下才会生成，如果是 O0 不开优化时，LLVM 则会使用内存访问来解决问题，也就是将值写入同一个内存位置，再在需要赋值时从内存位置读出值，这样也能避免数据的多赋值。但也很显然，这种依赖于内存访问的方式会导致性能变差，所以只会在不开优化的情况下生成这种代码。
测试路径下也有这样的一个测试用例：ch7_5_phinode.c，可以通过 clang -O0 和 clang -O1 来编译生成 LLVM IR，查看代码并确认在 O1 优化下生成了Phi节点。
需要注意的是，因为目前还没有处理传参的问题，所以将LLVM IR编译成汇编代码的过程会出错：
Assertion failed: (InVals.size() == Ins.size() && "LowerFormalArguments didn't emit the correct number of values!"), function LowerArguments, file
会在下一节开始处理和函数调用有关的功能。