Sherfiter's wiki for fun

第 7 章 · 中间表示与三地址码

前端读完了源程序,后端要写目标机器,中间需要一个「两种语言都不在乎」的通用形态:中间表示(Intermediate Representation, IR)。IR 是编译器的主战场(优化全在这里),设计得好坏直接决定后端的难度。本章讲最经典的教学 IR(三地址码)、它的两种数据结构表示(四元式 vs 静态单赋值 SSA 的预览)、以及 AST 到 IR 的完整生成。

7.1 为什么要 IR:一次生成,处处优化

回顾第 1 章的流水线:IR 在前端和后端之间,职责是「表达程序的语义,但不绑任何源语言或机器」。经典三地址码(Three-Address Code, TAC)的形状:每条指令最多三个地址(两个操作数 + 一个结果):

t1 = b * 2        ← 乘法:结果 t1,操作数 b、2
t2 = a[t1]        ← 数组寻址
a[t1] = t2? 不对,例子要一致:
x = y + z         二目运算
t1 = -x           一目运算
goto L1           无条件跳转
if x < 0 goto L2  条件跳转
param x, call f   函数调用(第 8 章)

「三地址」的名字来自 x = y op z 的三个地址位,复合表达式必须拆成多步(每步一个临时变量 t1、t2……),这个「拆平」正是优化的着力点:临时变量的生存期、公共子表达式都显形了。

7.2 从 AST 生成三地址码

第 5 章的后序遍历骨架,换个 emit 就成 IR 生成器:

int temp_id = 0;
char *new_temp(void) { static char buf[8]; sprintf(buf, "t%d", ++temp_id); return strdup(buf); }

char *gen_expr(const Node *n) {      // 返回「存放该表达式结果的地址」
    switch (n->kind) {
        case ND_NUM:  return emit_load(n->value);
        case ND_VAR:  return n->name;
        case ND_ADD: {
            char *l = gen_expr(n->lhs);       // 先左
            char *r = gen_expr(n->rhs);       // 再右
            char *t = new_temp();
            emit("%s = %s + %s", t, l, r);    // 最后自己
            return t;
        }
    }
}

对 a = b * 2 + c 走一遍,输出的 TAC:

t1 = b * 2
t2 = t1 + c
a = t2

「先孩子后自己」的后序遍历 = 运算的操作数先就位。控制流(if/while)生成时引入标签:

if (a < b) s1 else s2  →
  t1 = a < b
  if !t1 goto Lelse
  s1
  goto Lend
Lelse:
  s2
Lend:

while 是 if 的变体(条件在头,回边 goto 回条件)。生成的 IR 逐条与汇编仅一步之遥(第 10 章),这就是 IR 的「中间」含义。

7.3 IR 的两种数据形态:线性 vs SSA

TAC 有两种落地方式。线性四元式:指令数组(op, arg1, arg2, result),简单直接,经典教材与早期编译器用。静态单赋值形式(SSA):每个变量只被赋值一次,多次赋值时改名(x₁、x₂……),控制流汇合处用 φ(phi) 函数合并:

线性版:            SSA 版:
x = 1              x1 = 1
if ...             if ...  x2 = φ(x1, x3)
  x = 2              x = 2 → x3 = 2
x = x + 1          x4 = x2 + 1? 或 φ 的那个

SSA 的魔力:每个「名字」只有一处定义,使用-定义关系(du 链)变成树的形状,数据流分析(第 9 章)从「迭代求不动点」简化为「沿树传播」,大量优化(常量传播、死代码删除)变得局部而便宜。现代编译器全部以 SSA 为核心 IR(LLVM IR、V8 的 Sea of Nodes)。本课实现线性版(够教学),SSA 记住概念和「为什么单赋值这么值钱」即可,进阶读 LLVM 的 IR 文档。

7.4 好的 IR 设计考量

几个设计轴,每条都有权衡:

  • 层次:低级 IR(贴汇编,显式寄存器、内存地址)vs 高级 IR(有类型、有结构)。LLVM 用多层递降;
  • 显式控制流 vs 结构化:goto 风格(灵活,优化友好)vs if/while 结构化(可读);
  • 显式临时变量 vs 无限寄存器:IR 假设「无限寄存器」(机器无关),后端再分配真实寄存器(第 10 章),这层假设解放了前端。

设计 IR 的总原则:它要让中端的优化「写起来简单」。优化器是这个舞台的主角,IR 是为它定制的布景。

常见错误

  • 临时变量编号不唯一。静态计数器在多遍生成后没重置,t5 撞 t5。
  • 布尔表达式的短路语义丢了。a && b 直接生成 a+b 是错的(第 3 章 Java 的短路),要用「短路求值」的跳转模式生成。
  • 条件跳转的取反搞反。if-else 的 goto 条件是取反的(!t1 goto else),写反后 then/else 对调,程序「看起来能跑」结果全错。
  • IR 生成和语义检查混在一遍。类型错发现时 IR 已经吐了一半;分两遍,先查后生成。

练习

  1. 动手:给第 5、6 章的语言补上 if/while 的文法与 AST,完成 7.2 的控制流 IR 生成,对 while (i < n) { s = s + i; i = i + 1; } 输出完整 TAC。
  2. 手算:对 x = a + b * c - d 手写三地址码(注意优先级),再改成 SSA 版(每变量一次赋值),体会 t 变量的命名。
  3. 动手:实现「常量折叠」mini 优化:生成 IR 时检查两个操作数是否都是常量,是则直接算出结果(t1 = 2 * 3 变成 t1 = 6)。这就是中端优化的第一口。
  4. 思考:SSA 的 φ 函数在真实机器上不存在,后端要把它「删掉」(并行 copy)。查一下「φ elimination / SSA destruction」,思考为什么「插入 φ 容易、删除 φ 要小心」(提示:并行拷贝的次序,环)。
豫ICP备2026027944号