Lec8: Basic Blocks and Traces

Mismatch 1 双 label#

IR 的 CJUMP(e, t, f) 可以跳两个地方;真实机器的条件跳转只能指定 true label,假就 fall through 到下一条。

1
        IR Tree                    Machine
2
   CJUMP(e, t, f)            evaluate e
3
   ...                       JNZ t
4
   LABEL(t)                  if-false code
5
   if-true code              t: ...
6
   LABEL(f)
7
   if-false code

想让机器直接执行 CJUMP,必须保证 CJUMP 后面紧跟 false label——这是 Stage 3 要做的事。

Mismatch 2 让求值顺序变敏感#

1
      BINOP
2
     ╱  │  ╲
3
   op  e1  ESEQ
4
            ╱  ╲
5
           s    e2

s 有副作用,先算 e1 还是先算 s 结果不一样。例子:e1 = a + 5、s 是 a := 5——左右子树先后顺序决定结果。

但好的指令选择 / 调度器希望能自由调度子表达式。混杂在表达式里的语句剥夺了这种自由。

Mismatch 3 同样有副作用#

CALL 节点出现在表达式里和 ESEQ 同病相怜,而且 CALL 还有额外问题。

Mismatch 4<嵌套> CALL 抢 RV 寄存器#

1
CALL(f, [e1, CALL(g, [e2, ...])])

每个函数都把返回值放在同一个 TEMP(RV)——内层 g 的结果会覆盖外层 e1 已经放好的东西。

简单情形(显然成立)#

1
ESEQ(s1, ESEQ(s2, e))     =  ESEQ(SEQ(s1, s2), e)
2
BINOP(op, ESEQ(s, e1), e2) =  ESEQ(s, BINOP(op, e1, e2))
3
MEM(ESEQ(s, e1))           =  ESEQ(s, MEM(e1))
4
JUMP(ESEQ(s, e1))          =  SEQ(s, JUMP(e1))
5
CJUMP(op, ESEQ(s, e1), e2, l1, l2) = SEQ(s, CJUMP(op, e1, e2, l1, l2))

规律:ESEQ(s, e) 出现在某节点的第一个子表达式里 —— 直接把 s 抽出来放外层就行,因为 s 本来就该最先算。

难情形 出现在第二个子表达式#

1
BINOP(op, e1, ESEQ(s, e2))
2
CJUMP(op, e1, ESEQ(s, e2), l1, l2)

直接搬不行——s 可能改写 e1 依赖的内存。比如:

1
s  = MOVE(MEM(x), y)
2
e1 = MEM(x)

要是不管不顾把 s 提到 e1 前面,e1 读到的就是写过之后的值,语义错了。

1
BINOP(op, e1, ESEQ(s, e2))
2
↓
3
ESEQ(MOVE(TEMP t, e1),
4
     ESEQ(s,
5
          BINOP(op, TEMP t, e2)))

1
若 s 和 e1 commute:
2
BINOP(op, e1, ESEQ(s, e2)) = ESEQ(s, BINOP(op, e1, e2))

commute(s, e)<保守近似>#

什么时候 s 和 e 一定可换序?真实判断不可能(要做精确别名分析),所以用保守估计:

• 常量和任何 statement 都 commute
• 空 statement(EXP(CONST x))和任何 expression 都 commute
• 其他一律假设不commute

1
static bool isNop(T_stm x) {
2
  return x->kind == T_EXP && x->u.EXP->kind == T_CONST;
3
}
4
static bool commute(T_stm x, T_exp y) {
5
  return isNop(x) || y->kind == T_NAME || y->kind == T_CONST;
6
}

保守 = “宁可多塞 temp,也不破坏语义”。会多生成些 IR,但后续 dead code elimination 能扫掉。

Tiger 编译器的实现接口#

1
typedef struct expRefList_ *expRefList;
2
struct expRefList_ { T_exp *head; expRefList tail; };
3

4
struct stmExp { T_stm s; T_exp e; };
5

6
static T_stm    reorder(expRefList rlist);     // 关键
7
static T_stm    do_stm(T_stm stm);             // 处理 stmt
8
static struct stmExp do_exp(T_exp exp);        // 处理 expr,返回 (s, e)

• expRefList:指针的 list,每个元素指向一个 T_exp 槽位(便于原地 update)
• stmExp:do_exp 返回 (s, e'),使得 e ≡ ESEQ(s, e') 且 e’ 已无 ESEQ

reorder 的语义#

输入<一组子表达式> [e1, e2, ESEQ(s, e3)] 输出<把里面的> statement 抽出来,把子表达式槽位原地改成 ESEQ-clean 版本

1
[e1, e2, ESEQ(s, e3)]
2
   │
3
   ├── s commute with e1, e2:
4
   │     抽出 s,槽位变成 [e1, e2, e3]
5
   │
6
   ├── e2 不和 s commute:
7
   │     抽出 SEQ(MOVE(t1,e1), SEQ(MOVE(t2,e2), s)),槽位变成 [TEMP(t1), TEMP(t2), e3]
8
   │
9
   └── e2 和 s commute,但 e1 不:
10
         抽出 SEQ(MOVE(t1,e1), s),槽位变成 [TEMP(t1), e2, e3]

do_stm<每种> statement 怎么处理(节选)#

1
static T_stm do_stm(T_stm stm){
2
  switch (stm->kind) {
3
    case T_SEQ:                     // SEQ(s1, s2)
4
      return seq(do_stm(stm->u.SEQ.left),
5
                 do_stm(stm->u.SEQ.right));
6
    case T_JUMP:                    // JUMP(e)
7
      return seq(reorder(ExpRefList(&stm->u.JUMP.exp, NULL)), stm);
8
    case T_CJUMP:                   // CJUMP(o, e1, e2, t, f)
9
      return seq(reorder(ExpRefList(&stm->u.CJUMP.left,
10
                        ExpRefList(&stm->u.CJUMP.right, NULL))), stm);
11
    case T_MOVE: ...                // 见下面
12
    case T_EXP:
13
      if (stm->u.EXP->kind == T_CALL)
14
        return seq(reorder(get_call_rlist(stm->u.EXP)), stm);
15
      else
16
        return seq(reorder(ExpRefList(&stm->u.EXP, NULL)), stm);
17
  }
18
}

MOVE 要分四种情况:

1
case T_MOVE:
2
  if (dst==TEMP && src==CALL)            // MOVE(TEMP, CALL(...))  ← 已 canonical
3
    return seq(reorder(get_call_rlist(src)), stm);
4
  else if (dst==TEMP)                    // MOVE(TEMP, e)
5
    return seq(reorder([&src]), stm);
6
  else if (dst==MEM)                     // MOVE(MEM(e1), e2)
7
    return seq(reorder([&dst.MEM, &src]), stm);
8
  else if (dst==ESEQ) {                  // MOVE(ESEQ(s, e1), e2)
9
    // 拆成 SEQ(s, MOVE(e1, e2)) 再递归
10
    return do_stm(T_Seq(dst.ESEQ.stm,
11
                        T_Move(dst.ESEQ.exp, src)));
12
  }

do_exp<每种> expression 怎么处理#

1
static struct stmExp do_exp(T_exp exp){
2
  switch(exp->kind) {
3
    case T_BINOP:
4
      return StmExp(reorder([&L, &R]), exp);
5
    case T_MEM:
6
      return StmExp(reorder([&exp->u.MEM]), exp);
7
    case T_ESEQ: {
8
      struct stmExp x = do_exp(exp->u.ESEQ.exp);   // {x.s, x.e}
9
      return StmExp(seq(do_stm(exp->u.ESEQ.stm), x.s), x.e);
10
    }
11
    case T_CALL:
12
      return StmExp(reorder(get_call_rlist(exp)), exp);
13
    default:
14
      return StmExp(reorder(NULL), exp);    // CONST/NAME/TEMP 没子表达式
15
  }
16
}

T_ESEQ 那一支是关键<把内部> s 和 do_exp(e) 的 statement 部分串起来,作为新的 statement 抛出去;e 部分留作返回的 expression。

例子(三地址码)#

1
(1)  x := input
2
(2)  y := x - 1
3
(3)  z := x * y
4
(4)  if z < x goto (7)
5
(5)  p := x / y
6
(6)  q := p + y
7
(7)  a := q
8
(8)  b := x + a
9
(9)  c := a - b
10
(10) if p == q goto (12)
11
(11) goto (3)
12
(12) return

分块:

• 新块开始(LABEL 处 / 跳转目标):(1) (3) (5) (7) (11) (12)
• 新块开始(紧跟 JUMP/CJUMP)<在> (4) (10) (11) 后

得到 6 块:{1,2}、{3,4}、{5,6}、{7,8,9,10}、{11}、{12}。

Tree 语言版本(加 LABEL / JUMP)#

切完 (5)(6)(7)(8)(9)(10) 这两块后,要补:

1
LABEL(five)                LABEL(seven)
2
MOVE(p, x/y)               MOVE(a, q)
3
MOVE(q, p+y)               MOVE(b, x+a)
4
JUMP(NAME seven)  ← 补    MOVE(c, a-b)
5
                           CJUMP(EQ, p, q, twelve, eleven)

配图示例#

1
LABEL(b1)
2
...
3
JUMP(NAME b4)
4
        ↓
5
LABEL(b4)
6
...
7
JUMP(NAME b6)
8
        ↓
9
LABEL(b6)
10
...
11
CJUMP(cond, b7, b3)    ← 取 false 后继 b3 拼到 trace 后面
12
        ↓                  这样 CJUMP 后面就是 LABEL(b3) ✓
13
LABEL(b7)  LABEL(b3)

顺着 b1 → b4 → b6 → b3 跑成一条 trace,b7 留到下一条 trace。

1. 为什么要 canonicalization?#

IR Tree 写起来漂亮,但有四个跟机器对不上的地方:

• CJUMP 双 label,机器只能单 label
• ESEQ 让求值顺序变敏感
• CALL 当作子表达式时同样有副作用
• 嵌套 CALL 共享 RV 寄存器,会互相覆盖

2. 三阶段流水线#

Stage 1(Canonical Trees)解决 ESEQ 和 CALL,Stage 2 + 3(Basic Blocks + Traces)联手解决 CJUMP。

3. ESEQ 上浮 + commute 估计#

原则<不停把> ESEQ 抬高,直到它能转成顶层 SEQ。语义不允许直接搬时,先把会被打乱的子表达式塞进 fresh temp。commute 用最保守的常量/空 stmt 规则估,宁滥勿缺。

4. CALL 立刻搬到 fresh temp#

CALL → ESEQ(MOVE(TEMP t, CALL), TEMP t),确保下游每个 CALL 的父节点都是 EXP 或 MOVE(TEMP, …)。

5. Basic Block = 控制流的最小颗粒#

“LABEL 开头 + JUMP/CJUMP 结尾,中间无跳转”——切块时缺 LABEL 就造一个,缺 JUMP 就补一条到下一块。

6. Trace 用 DFS 排序,让 CJUMP 接 false label#

Trace 内部沿可能的执行路径连成一串,CJUMP 后主动接它的 false 后继。剩下的少数 CJUMP 用”取反 / 加跳板”两招收尾。

7. 循环体单独成 trace#

test 排在循环体之后,使每轮迭代少一条 unconditional jump——循环执行次数越多收益越大。

Step 1<把>”为什么”想清楚(0.5h)#

• 复习 Lec7 的 IR Tree / ESEQ / CALL 三个节点的形状
• 理解四个 mismatch——特别是为什么 CJUMP 必须接 false label,为什么 ESEQ 让调度不自由
• 三阶段的对应关系 1 解 ESEQ + CALL,Stage 2 + 3 解 CJUMP

Step 2 Trees(2h)⭐ 重点#

• 把 9 条改写规则默写出来——尤其是”e1 不和 s commute 时要塞 temp”那条
• 弄懂 commute(s, e) 的保守近似<常量> + 空 stmt,其他全否
• 看懂 reorder 的工作<输入指针> list,抽出 statement,原地更新成 ESEQ-clean
• CALL → ESEQ(MOVE(TEMP t, CALL), TEMP t) 一定要记住——这是 RV 冲突的统一解法

Step 3 Blocks(0.5h)#

• 切块算法 4 步骤 开头、JUMP/CJUMP 结尾、缺 JUMP 补、缺 LABEL 造
• 手切一遍课件那个 12 行三地址码的例子

Step 4(1.5h)⭐ 重点#

• DFS 算法<沿着可能执行路径走>,撞到死路开新 trace
• “Finishing Up” 三种 CJUMP 的处理
• 循环 trace 的三种排法 (a)(b)(c) 的跳转计数,理解为啥 (c) 最优

Step 5 Module 三个接口(0.5h)#

• C_linearize / C_basicBlocks / C_traceSchedule 的输入输出
• 为什么 C_basicBlocks 返回 C_block(里面是 C_stmListList,即 list of basic blocks)

Step 6<做作业> 8.2 / 8.6 / 8.7(1h)#

• 8.2<手算> ESEQ 改写
• 8.6 block 划分
• 8.7 排序

常见陷阱#

• commute 错判<别想着证明两个表达式可换序>,就用保守的”常量/空 stmt”规则
• ESEQ 在第二个子表达式<不能直接搬>,必须用 temp(除非确定 commute)
• 嵌套 CALL<第一步就要拆>,别等到指令选择
• Trace 之间靠 JUMP 连<别忘了基本块结尾要有> JUMP/CJUMP——切块阶段就要补
• (c) 最优 ≠ 总用 (c) 算法是启发式 DFS,只是倾向长 trace,不保证最少 jump

和后续章节的衔接#

• Ch9<每条> canonical statement → 一条或多条机器指令(maximal munch / dynamic programming)
• Ch10/11<寄存器分配> / 调度——长 trace 提供了大块连续指令,给寄存器分配腾出更大的活动区间
• Ch8 是 IR 的”最后整形”<再往下>,IR 的形态就只剩”机器指令的列表”了