(1) P:=0 (2) I:=1
B1
(1) P:=0
ห้องสมุดไป่ตู้
③删除无用代码 ④外提循环不变 式：(4)、(7)为循环
不变式，可外提至 B1中
(2) I:=1 B1 (4) T2:=addr(A) - 4 (7) T5:=addr(B) - 4
(3)T1:=4* I B2 (4) T2:=addr(A) - 4 (5) T3:=T2[T1] (6) T4:= T1 (7) T5:=addr(B) - 4 (8) T6:=T5[T1] (9) T7:=T3*T6 (10) P:=P+T7 (11) I:=I+1 (12) if I≤20 goto (3)
• 检查公共子表达式:若四元式为公共子表达式,
则把已有的结点作为它的结点(即加右标记); • 检查无用赋值: 若NODE[A]已是某结点的右标记, 则从该右标记集合中删除后再建立新结点。
算法框图：
初始化
取下一条四元式 (0)A:=B、（1）A:=opB、（2）A:=BopC N
NODE（B）定义？ Y
⑥变换循环控制条件 (1) P:=0 删除归纳变量
(12) if I≤20 goto (5) 分析I的作用: •计算 T1:=4*I •循环控制条件 I≤20 •递归赋值: I:=I+1 变换控制条件: •计数法: I≤20 •比较法: T1≤80 删除(11)
B1
(4) T2:=addr(A) - 4 (7) T5:=addr(B) - 4 (3) T1:=4
⑦合并已知量
(5) T3:=T2[T1] B2 (8) T6:=T5[T1] (9) T7:=T3*T6 (10) P:=P+T7 (3’) T1:=T1+4 (12) if T1≤80 goto (5)
图4. 运算强度削弱
B1中(2) I:=1 (3)T1:=4*I (3) 可改为: (3) T1:=4 图5. 变换循环控制条件与合并 删除(2) 已知量
结点集N为基本块集； 首结点n0为含有第一个语句的基本块；
有向边集E的构成规则:

i
j
基本块j紧跟在基本块 i 之后, 且基本块 i 的出口语句不是无条件转移语句或停语句； 基本块i 的出口语句是 goto (s) 或 if . . . goto (s) 且 (s) 是基本块j 的入口语句 ；
(4) if R=0 goto (8)
(5) X:= Y (6) Y:=R B3 (7) goto (3)
(8) write Y (9) halt
B4
程 序 流 图
4.基本块内的优化
[例]对以下求向量内积的PASCAL程序段的中间代码进行优化: P := 0; (设low=1,w=4) for I := 1 to 20 do (A[I]地址：I*w+(base-low*w) P:= P + A[I] * B[I] (1) P:=0
计算P=op B
计算P=Bop C
删除刚生成 的新结B和C
DAG中有以B、 C为后继且标记 为op的结点？
NODE（A）定义？ N 将A标记在结点n上
Y
将A 从原 结删除
有，设为n 构造新结点 n标为P，令 N NODE（P）定义？ Y B、C为其 生成新结n标为P 找到结点设n 左右后继
[例] 试构造以下基本块的DAG (1) T0:=3.14 (2) T1:=2*T0 (3) T2:=R+S (4) A:=T1*T2 构造DAG n6 (5) B:=A * (6) T3:=2*T0 (7) T4:=R+S n2 (8) T5:=T3*T4 2 T3 (9) T6:=R - S n1 T0 n2 T1 (10) B:=T5*T6 3.14 6.28
图3 删除无用代码和代码外提
图4 运算强度削弱
(1) P:=0
(2) I:=1 B1 (4) T2:=addr(A) - 4 (7) T5:=addr(B) - 4 (3) T1:=4*I (5) T3:=T2[T1] B2 (8) T6:=T5[T1] (9) T7:=T3*T6 (10) P:=P+T7 (11) I:=I+1 (3’) T1:=T1+4 (12) if I≤20 goto (5)
第十章
本章要点
阶段: 编译的第四阶段
代码优化
源程序 词法分析 表 语法分析 格 错
出
任务:对程序进行各种 等价变换，使得从变换后 的程序出发，能生成更有 效的目标代码。 重点: 局部优化 循环优化
中间代码生成
管 优 理 目标代码生成 目标程序 化 处 理
10.1 优化概述
1. 问题的提出 (1) 编译程序的作用 使计算机的使用方式从用机器语言编程发展到用 高级语言编程。是计算机发展史上的一次飞跃。 (2) 早期编译程序的不足 占用的空间大 目标程序质量差 运行的时间长 2. 解决的方法: 代码优化:即对程序进行各种等价变换，使得从变 换后的程序出发能生成更有效的目标代码。 优化原则:等价、有效、合算
[小结]
局部优化: ①删除公共子表达式
⑤合并已知量 ⑥复写传播 ⑦删除无用赋值 循环优化: ②外提循环不变式 ③运算强度削弱 ④变换循环控制条件 优化前后比较: 循环B2 四元式个数 乘法个数 优化前 10 3 优化后 6 1
以上优化方法均可用算法实现
基本块内还可进行以下几种变换 临时变量改名.
优化不是目的，只是手段
3. 优化方法 按优化所涉及的程序范围分： 局部优化: 在基本块上进行的优化 • 合并已知量
• 删除无用赋值（无用代码） • 删除多余运算（公共子表达式）
方法：DAG； 特点： 简单、成熟。 循环优化：在循环块上进行的优化 • 代码外提
• 运算强度削弱 • 删除归纳变量
交换语句的位置. 代数变换.
说明:
无用赋值的判定:
• 对A赋值后, A不被引用 (全局数据流分析)
• 对A赋值后, 引用前又重新赋值 ( 容易判定) • A仅在递归赋值(A:=A+C)中被引用(全局数据 流分析)
#
10.2.2. 基本块的DAG表示及其应用
1. 无环路有向图DAG (Directed Acyclic Graph) (1) 定义: 若有向图中所有通路均非环路, 则称其为DAG (2) 基本块的DAG(用于描述计算过程): a:=b*-c+b*-c的 := 是为结点附加了信息的DAG。 DAG（中间代 a + 码的图形表 叶结点: 示） •下标记: 常数或标识符 * •右标记: 标识符 @ 内结点: b •下标记: 运算符 c • 右标记: 标识符 (2) A:= op B (3) A:=B op C (3) 结点形式 n3 A n2 A (1) A:=B op op n1 A n1 n2 n1 B B C B 0型
方法：循环查找算法、数据流分析；复杂、高效。 全局优化：在整个程序上的优化 方法：全局控制流分析、全局数据流分析; 特点：代价大、高效。
10.2 局部优化
问题： 什么是基本块？ 怎样划分基本块？ 在基本块中可以进行哪些优化？ 怎样进行局部优化？ 10.2.1 基本块和流图 对一给定的程序，将其划分为若干个基本块， 在各个基本块中分别进行优化即称为局部优化。
(1) P:=0 (2) I:=1
B1
①删除公共子表达式
(3)、(6)为公共子式 可将(6)改为T4:=T1
(2) I:=1
B1
(3)T1:=4*I B2 (4) T2:=addr(A) - 4 (3) T1:=4*I ②进行复写传播 (5) T3:=T2[T1] (4) T2:=addr(A) - 4 T4:=T1 (5) T3:=T2[T1] B2 B2中(6)T6:=T5[T4] (6) T4:= T1 (8) (7) T5:=addr(B) - 4 (6) T4:=4*I T4：=T1 可改为(8)T6:=T5[T1] (8) T6:=T5[T1] (7) T5:=addr(B) - 4 (9) T7:=T3*T6 (8) T6:=T5[T4] T6:=T5[T1] (10) P:=P+T7 (9) T7:=T3*T6 (11) I:=I+1 (10) P:=P+T7 (12) if I≤20 goto (3) (11) I:=I+1 (12) if I≤20 goto (3) 图1 优化前的四元式 图2 删除公共子表达式和复写传播
(3)T1:=4*I (5) T3:=T2[T1] B2 (8) T6:=T5[T1] (9) T7:=T3*T6 (10) P:=P+T7 (11) I:=I+1 (12) if I≤20 goto (3)
图2 删除公共子表达式和 复写传播
图3删除无用代码和代码外 提
(1) P:=0
(2) I:=1 B1 (4) T2:=addr(A) - 4 ⑤运算强度削弱 (7) T5:=addr(B) - 4 由(3) T1:=4*I (11) I:=I+1 (3)T1:=4*I 可改为: 将(3)外提至B1 (5) T3:=T2[T1] B2 (11)后增加(3‘) (8) T6:=T5[T1] (3’) T1:=T1+4 (9) T7:=T3*T6 (10) P:=P+T7 (11) I:=I+1 (12) if I≤20 goto (3)
(1) P:=0
(2) I:=1 B1 (4) T2:=addr(A) - 4 (7) T5:=addr(B) - 4 (3) T1:=4*I
(5) T3:=T2[T1] B2 (8) T6:=T5[T1] (9) T7:=T3*T6 (10) P:=P+T7 (11) I:=I+1 (3‘) T1:=T1+4 (12) if I≤20 goto (5)