从抽象语法树降低表示

复习

• 为什么需要中间表示：IR 作为通用桥梁
• 抽象语法树：程序结构的树形表示
• 树：用父子关系表示层次

TL;DR

• “降低”指把高级结构改写成更接近执行的简单操作
• 它一步步把 AST 转化为更底层的 IR
• 每一步都必须保持语义不变
• 降低让后续的优化和代码生成更容易

正文

　　上一章说，源码要先变成 IR。可 AST 还是“高级”的：里面有函数、循环、复合表达式。IR 却要“低级”得多，接近执行。从高级到低级，需要一个逐步改写的过程，这个过程叫降低（lowering）。

把高级结构拆开

　　降低的思路，是把复杂的高级结构，改写成更简单、更接近执行的操作。

　　举个直观的例子，一个 for 循环：

for (i = 0; i < n; i = i + 1) { 循环体 }

　　它可以被“降低”成等价的、只有条件和跳转的形式：

i = 0
loop:
  if i >= n goto end
  循环体
  i = i + 1
  goto loop
end:

　　注意，改写前后做的事完全一样——for 的“甜”，只是给人和编译器看的语法糖，执行时本质就是“判断 + 跳转 + 自增”。

一步步来

　　降低通常不是一步到位的，而是分好几步逐步进行：

• 先把高级控制结构（for、while、switch）拆成条件与跳转
• 再把复杂的复合表达式，拆成一个个简单运算
• 每一步都产出比上一步更简单的形式

　　这种做法很好理解：一次只改一点，每次都改对，比一步跨到底更可靠。 而且每一步都能单独验证“语义没变”。

唯一的硬要求：语义不变

　　降低可以对形式做各种改写，但有一条铁律：降级前后，程序的行为必须完全一致。

　　如果拆着拆着把一个循环拆成了死循环，或者把边界条件搞错了，那再“低级”、再规整也没用。所以，降低的每一步，都要小心地保持语义等价。

　　这其实和前面“优化必须保留行为”是同一个精神：形式可以变，意义不能变。 先记住这条，因为接下来的中间表示、优化，全都建立在这个前提上。

思考题 1

　　“降低”到底把什么变成了什么？

思考题 2

　　降低过程中，最重要的原则是什么？

小结

知识点

• 降低把高级结构改写成更接近执行的简单操作
• 通常分多步逐步进行
• 每一步都必须保持语义等价
• 降低为后续的 IR、优化与代码生成做准备

参考资料

1. Wikipedia(zh)：中间表示：从高级结构到低级表示的转换
2. Wikipedia(zh)：控制流：循环与分支的低层表示

思考题答案（仅供参考）

思考题 1

　　它把高级、结构复杂的写法（如 for 循环、复合表达式），改写成更简单、更接近执行的操作（如条件、跳转、简单运算），也就是从“接近人”逐步走向“接近机器”。

思考题 2

　　最重要是保持语义不变：无论形式怎么改写，程序的执行行为都要与原来完全一致，否则后续的优化和代码生成都会建立在错误的基础上。

协议

　　本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

封面图

设计师 | 南国微雪