这一章首先增加了更多的 Cpu0 算术运算指令和逻辑运算指令，这些在各个优化步骤中存在的 DAG 转换过程可以使用 Graphviz 来图形化显示，展示出更多的有效信息。不同于上一章，在这一章中，你应该专注于 C 代码的操作和 llvm IR 之间的映射以及如何在 td 文件中描述更复杂的 IR 与指令。这一章定义了另外一些寄存器类，你需要了解为什么需要它们，如果有些设计没有看懂，可能是对 Cpu0 的硬件不够熟悉，可以结合硬件来理解。
0 前言
看到这篇文章的朋友或许对编译器有基本的了解，也或许和我一样对LLVM比较迷茫。但不管如何，希望大家看完都有收获，我对LLVM的后端开发也在摸索的过程当中，欢迎共同讨论。
github项目地址：https://github.com/hhtdgit/LLVM17-Cpu0-Backend
相关资料：
- Cpu0架构：http://ccckmit.wikidot.com/ocs:cpu0
- 官方Tutorial：https://jonathan2251.github.io/lbd/about.html
- P2Tree的知乎专栏：https://zhuanlan.zhihu.com/p/351848328
1 算术运算
1.1 简要说明
（1）乘法和移位运算
C 语言中的加法（+）、减法（-）和乘法（*）运算符通过 add，addu，sub，subu 和 mul 指令来实现，左移（<<） 和右移（>>） 运算符通过 shl， shlv， sra， srav， shr， shrv 指令来实现。
对应到 llvm IR 中的指令分别是 add，sub，mul，shl，ashr，lshr 等，ashr 表示算术右移，或者说是符号扩展右移；lshr 表示逻辑右移，或者说是零扩展右移。不过，在 DAG node 中，使用 sra 表示 ashr 的 IR 指令，使用 srl 表示 lshr 的 IR 指令，看起来不是很直观，可能是历史设计的问题。
右移操作在不同的阶段的符号表示对应如：
| 描述 | 零扩展移位 | 符号扩展移位 |
| LLVM IR 中指令（.bc） | lshr | ashr |
| DAG node 中符号 | srl | sra |
| Mips 指令 | srl | sra |
| Cpu0 指令 | shr | sra |
如果我们认为右移 1 位等效于对右移数字除以 2，在逻辑右移中，对于一些有符号数，结果有可能是错的；在算术右移中，对于一些无符号数，结果也是错的。同理，对于左移操作，也不能单纯的用乘除法取代。比如，有符号数 0xfffffffe（-2）做逻辑右移，得到 0x7fffffff（2G-1），我们期望得到 -1，却得到一个大数；无符号数 0xfffffffe（4G-2）做算术右移，得到 0xffffffff（4G-1），我们期望得到 2G-1，却得到 4G-1；有符号的 0x40000000（1G）做逻辑左移，是 0x80000000（-2G），我们期望的应该是 2G 却得到了 -2G。所以我们不能用乘除法指令来替代移位指令，必须要设计专用的硬件移位指令。
（2）除法和求余运算
llvm IR 中的除法是 sdiv 和 udiv 指令，求余是 srem 和 urem 指令，这个指令接受一个整型值作为操作数（也可以是整形值元素的向量），它返回一个除法操作的余数。通常情况下数学上有多种对余数的定义，比如最接近 0 的那个余数，或者最接近负无穷大的那个余数，这里的余数定义是与被除数（第一个操作数）一致符号的余数（或能整除时为 0）。srem 是有符号数的求余，urem 是无符号数的求余指令。
除 0 后的余数是未定义行为，除法溢出也是未定义行为，和硬件实现相关。
LLVM 默认会把 带立即数的 除法和求余操作通过一个算法转换为利用有符号高位乘法 mulhs 来实现，但我们目前没有 mulhs，所以这个通路有问题。（LLVM 这么做的原因是，乘法操作在硬件上通常比除法操作更省资源，所以会尽量把除法转换成乘法来做）
为了支持 mulhs 这种操作，Mips 的做法是用 mult 指令（硬件指令）来将乘法运算结果的高 32 位放到 HI 寄存器，将低 32 位结果放到 LO 寄存器。然后使用 mfhi 和 mflo 硬件指令来将两部分结果移动到通用寄存器中。 我们的 Cpu0 也在这块采用这种实现方式。
// mulhs(a, b) 表示有符号整数的高位乘法结果，即：
mulhs(a, b) = (a * b) >> word_size这里介绍一下这种方法：对于 x / d 可以用 mulhs(x, m) 估算：其中 m 是一个预先计算好的乘法常数（magic number），通过乘法逼近除法。这个常数可以通过一个算法预计算得到。对于除以 10（带符号整数除法），有：
m = 0x1999999A（十六进制），也就是429496730（十进制）s = 3，表示右移位数
即 x / 10 可以转换为先乘m再右移s：
int x_div_10(int x) {
int64_t m = 0x1999999A; // 预计算出来的常数
int64_t mul = (int64_t)x * m;
int result = (int)(mul >> 32); // 获取高位部分，相当于 mulhs
return result >> s; // 右移 s 位得到最终结果
}llvm DAG node 中定义了 mulhs 和 mulhu，我们需要在 DAGToDAG 指令选择期间，将其转换为 mult + mfhi 的动作，这就是接下来实现 selectMULT() 函数的一部分功能。只有将 llvm IR 期间的 mulhs / mulhu 替换为 Cpu0 硬件支持的操作，才不会在后续报错（另外，如果我们的后端能够直接支持 mulh 指令是最好的，但 Cpu0 没有支持）。
然后，我们来讨论一下如果求余操作的操作数不是立即数的情况。这个 node 是 ISD::SDIVREM 和 ISD::UDIVREM，是除法和求余操作统一的 node。刚好我们的 Cpu0 支持一个 div 指令，这个指令的功能是将一个除法操作的商放到 LO 寄存器，将余数放到 HI 寄存器。我们只需要使用 mfhi 和 mflo 指令将这两部分按需求取出来就好。
求余操作在不同阶段的符号表示如：
| 阶段 | 符号 | 相关函数 |
|---|---|---|
| llvm IR 指令 | srem | |
| DAG 指令选择的合法化阶段 | sdivrem | setOperandAction(ISD::SREM, MVT::i32, Expand) |
| DAG 指令选择的优化合法化阶段 | Cpu0ISD::DivRem, CopyFromReg xx, Hi, Cpu0ISD::DivRem | setTargetDAGCombine(ISD::SDIVREM) |
| 指令模式匹配 | div, mfhi | Cpu0InstrInfo.td 中的 SDIV, MFLO |
在Cpu0ISelLowering.cpp 中，注册了 setOperationAction(ISD::SREM, MVT::i32, Expand) 等操作，将 ISD::SREM lowering 到 ISD::SDIVREM（有关于 Expand 的参考资料，可以查看 http://llvm.org/docs/WritingAnLLVMBackend.html#expand）。然后实现了 PerformDAGCombine() 函数，将 ISD::SDIVREM 根据它是除法还是求余（通过 SDNode->hasAnyUseOfValue(0) 来判断）操作，选择生成 div + mflo / mfhi 的 机器相关的 DAG，进而指令选择到机器汇编指令。
