Skip to content

Chapter 7

Three-Address Code

三地址码：一种中间表示形式

  • 先叶子再根，所以翻译成两条语句：alt text
  • one field for operation
  • 3 field for addresses

Intermediate Representation Tree

三个要求

  • 方便生成
  • 方便翻译成机器码
  • 简单清晰，易于优化

Kinds of Expression

  • Backpatching
  • true patch list 和 false patch list 存储对应条件下的目的地址

Array Variables

计算数组的地址

Subscripting and Field Selection

Chapter 8 Basic Blocks and Traces

IR tree 翻译成机器码时会有 mismatch

  • alt text
  • ESEQ nodes 不方便优化
  • CALL nodes 也有相同问题

优化思路

  • 原来的树变成一系列 Canonical Tree 的列表
    • Canonical Tree 没有 SEQ/ESEQ
  • 把这个列表分成多个 basic block(内部没有 jump 和 lable)
  • 把 basic block 排列成 trace 使得 CJUMP 后面直接跟 false lable

Canonical Trees

properties

Canonical Trees are defined as having these properties：

  1. 没有 SEQ 和 ESEQ - 每棵 Canonical Tree 至多有一个 statement node(根节点)，其他是 exp node
  2. CALL 的父母是 EXP 或 MOVE(temp t,) - 不能是 CALL

也就是说，CALL 的父母必须是根节点，一棵树最多只有一个 CALL

eliminate ESEQs

  • idea：把 ESEQ nodes 抬高使得可以变成 SEQ

  • Given ESEQ(s, e)，把 s 提出来，把父母变成有 s 的 ESEQ/SEQ alt text alt text

  • 对于下面这种情况，把 s 提到前面可能会改变 e1，使结果不正确（如果 s 和 e1 commute，不冲突，还是可以这样重写）alt text

  • 正确做法：用中间变量存储 e1alt text

判断 statement 和 expression 是否 commute

  • 常数一定 commute
  • 空 statement 一定 commute
  • 其他认为不 commute

总结来说

alt text

moveCALLs to top level

多个 call 指令会覆盖寄存器

  • idea：把返回值存入临时寄存器
  • CALL(f, args)-> ESEQ(MOVE(TEMP t, CALL(f, args)), TEMP t)

eliminate SEQs

  • 对于多个 SEQ SEQ(SEQ(SEQ(..., sx), sy), sz)
  • 重复规则 SEQ(SEQ(a, b), c) = SEQ(a, seq(b, c))
  • 这样就变成了一个 statement 的简单序列 s1, s2, ...

Basic block

划分规则

  • 从头到尾扫描
  • 有 jump，分块（这一行是结尾）
  • 有 lable，分块（这一行是开头）

alt text

Trace

把 basic block 排成 trace 使得 CJUMP 后面跟 false label，这样可以直接翻译成机器语言

  • 把 CJUMP 和 false label 放一起
  • 把 JUMP 和 target label 放一起，删去 JUMP

Trace Definition：在包含分支的程序中可以连续执行的 statement

  • 目的 trace 完全覆盖整个程序

    • 每个 block 只属于一个 trace
    • 每个 trace 里没有 loop
    • trace 越少越好（减少 jump）

  • idea

    • 先选取 trace 的起始位置 b1
    • b1 末尾 JUPM b4，把 b4 放在 b4 后面
    • b6 末尾 CJUMP(t:b7,f:b3)，false label 在 b3，b3 放在![alt text] b6 后面，b7 放在另一个 trace

alt text

Optimal Traces

经常执行的序列应该有自己的 trace，减少无条件跳转