指令选择
复习
- 目标代码生成：后端的总任务
- 中间表示：三地址码
- 树：用树表示表达式结构
TL;DR
- 指令选择把 IR 操作映射为具体的机器指令
- 同一操作可能有多种指令组合，要选更优的
- 常用“模式匹配”：把 IR 看成树，用指令模板覆盖
- 选择时还要考虑指令的代价与特点
正文
后端第一件事，是决定“每个 IR 操作到底用哪些机器指令来实现”。这就是指令选择（instruction selection）。
一个操作，可能有好几种写法
最直接的映射，比如 a = b + c，在大多数机器上就是一条加法指令搞定。
但复杂表达式就没这么简单了。比如 a = b + c * d，机器可能：
- 先算
c * d，再和b相加 - 也可能某台机器有“乘加”一条指令，一次搞定
再比如取数组元素、访问结构体，往往有专门的寻址模式，能一条指令完成“基址 + 偏移”的加载。同一件事，可以有很多种指令组合，选哪种直接影响最终代码的效率和长度。
用“模式匹配”来做
怎么系统地做选择？常见办法是把 IR 表达式看成一棵树，而每一条机器指令，对应一个能覆盖这棵树的“小图案”（模板）。指令选择就变成了：
用这些图案，把整棵树覆盖起来。
一种覆盖方式，就是一种指令序列。覆盖方式往往不止一种，于是再根据每条指令的代价（执行快慢、长度）来挑总代价最小的那种。这又是一个在树/图上做选择的优化问题——前面的图论工具，在这里又派上了用场。
机器细节在这里登场
指令选择是最能体现“面向具体机器”的环节之一：
- 这台机器有哪些指令？
- 有哪些寻址方式？
- 哪条指令更便宜？
这些都得一一考虑。所以，为不同 CPU 编译，生成的指令可能很不一样——同一份源代码，同一套优化，最后落成的机器码却可能各不相同。 这正是后端存在的意义。
思考题 1
指令选择在做什么？
思考题 2
为什么同一个 IR 操作，可能有多种指令实现，需要“选择”？
小结
知识点
- 指令选择把 IR 操作映射为机器指令
- 同一操作常有多种指令组合
- 常用模式匹配，把 IR 树用指令模板覆盖
- 依据指令代价选择更优的方案
参考资料
- Wikipedia(zh)：指令选择：把中间表示映射为机器指令
- Wikipedia(zh)：树覆盖：用指令模板覆盖表达式树
思考题答案（仅供参考）
思考题 1
它在把 IR 的每个操作翻译成具体机器上的指令。对于复杂表达式，需要决定用哪几条指令、以什么顺序组合来实现它，并尽量选效率高、代价小的方案。
思考题 2
因为同一件事在机器上常有多种实现方式，例如是否有“乘加”指令、是否能利用寻址模式，都会影响指令组合。不同组合在速度、长度上各有差异，所以要“选择”出更优的那种。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪