B1
x=1
B3
B2 (2)lb a (3)t1=x*5 (4)r=t1 (5)t2=x<10 (6) if(t2)_ B4
(10) ie _
(11) r=0
(7)t3=x+1 (8)x=t3 (9) gt a
※ 基本块内四元式的局部优化过程示例
优化后 【例8.2】 设 B=5; A=2*3.14/(R+r); 有语句片断： B=2*3.14/(R+r)*(R-r); (1) ( = 5 _ B ) (2) ( * 2 3.14 _ t1) (3) ( + R r t2 ) (4) ( / t1 t2 t3 ) (5) ( = t3 _ A ) (6) (* 2 3.14t1t4 ) t2 (7) ( + R r t5 ) (8) ( / t4 t5 t6 ) (9) ( - R r t7 ) (10)( * t6 t7 t8 ) (11)( = t8 _ B ) t1= 6.28 A=2*3.14/(R+r); B=A*(R-r); (1) (= 5 _ B )
基于DAG的局部优化练习答案
优化的DAG： + 9 L|M 根据优化的DAG重组的四元式：
L=A-B
8 24|T8 * 6 T4|T7 7 6|T5 - 4 L|T2 + 5 T3|T6 1 2|T1 2A 3 B T3=A+B T4=L*T3 L=24+T4
• 常值表达式节省 (例8.2中的 (2)(6))：
方法： ① 先进行常值计算； ② 将常值的变量以常值代替；
• 公共子表达式节省 (例8.2中的 (7)(8))： 方法： ① 找公共表达式，建立结果变量等价关系； ② 等价变量以老变量代替新变量； • 删除无用赋值 (例8.2中的(1))： 方法： ① 确认一个变量两个赋值点间无引用点； ② 前一赋值点为无用赋值；
n1 …
ni …B…
n A
ni …B… nj …C…
或
n A
ni …B… n2 …|…A…
③ 若 A 在 n2 已定义过，则删除之：
8.2.3 基于DAG的局部优化方法
2. 根据基本块内优化的 DAG，重组四元式：
【假设】(1) 临时变量的作用域是基本块内； (2) 非临时变量的作用域可以是基本块外。
若：a=5+3;…;a=x…; a=a+1; 则 a+1不是常值表达式！ 2. 公共子表达式节省(删除多余运算)
注
如：a=b*d+1;e=b*d-2; …… b*d是公共表达式! 则可优化为 t=b*d; a=t+1; e=t-2; 若：b=b*d+1; e=b*d-2; 则 b*d不是公共表达式！

5. 消减运算强度（循环优化之二） 即把强度大的运算换算成强度小的运算。 如：i=1; while ( i<100 ){ t=4*i; b=a↑2;…; i++; }
则可优化为
t,i 线性 关系
i=1;t=0; while (i<100){t=t+4; b=a*a;…;i++;}
8.2.2 基本块及其划分
【开始】按结点编码顺序，依次读取每一结点 n1 信息： (1) 若 n1 为带有附加标记的叶结点： • 若 Ai 为非临时变量，则 生成： q1: Ai=B (i=1,2,…)
(2) 若 n1 为带有附加标记的非叶结点： ① 生成 q1: A=BC 或生成 q1: A=B ② 若Ai为非临时变量，则生成： q2: Ai=A (i=1,2,…) n1 B|A1,A2,… n1 A|A1,A2,… ni B|… nj C|… 以主标记 参加运算
※ 局部优化算法是以基本块为单位进行的，基本块 也是目标代码生成的基本单位。
【定义】基本块是程序中一段顺序执行的语 句序列，其中只有一个入口和一个出口。
基本块划分算法： 1．确定基本块的入口语句，它们是： (1) 程序的第一个语句或转向语句转移到的语句； (2) 紧跟在转向语句后面的语句。 2．确定基本块的出口语句，它们是： (1) 下一个入口语句的前导语句； (2) 转向语句(包括转向语句本身)； (3) 停语句(包括停语句本身)；
(3) (+ R r t2 ) (4) (/ 6.28 t2 t3 ) (5) (= t3 _ A )
t4≡t1 t5≡t2 t6≡t3 B 没有引用！ (9) (- R r t7 ) (10) (* t3 t7 t8 ) (11) (= t8 _ B )
※ 基本块内四元式的局部优化过程示例 优化的基本内容和方法：
删除 无用 赋值
常值 表达 式节 省
8.2.3 基于DAG的局部优化方法
(3) 若其它表达式 A = B C 或 A = B; ① 若在 n1 存在公共表达式: BC 或 B
n1 …
ni …B… nj …C…
则把A附加于n1上：
删除 公共 表达 式
n 1 … ,A
② 若不存在公共表达式， 则申请新结点n:
③ 循环优化 — 对循环语句实施的优化。
(2) 与机器有关的优化(目标代码级上的优化)：
包括：① 寄存器分配的优化； ② 消除无用代码。
8.2.1 常见的局部优化方法
1. 常值表达式节省(常数合并)
注
如：a=5+3;b=a+1; ……. 5+3,a+1 皆为常值表达式！ 则可优化为 a=8;b=9;
第 8 章 代码优化
优化处理是指产生更高效的目标代码所做的工作。 目标代码所占空间和执行速度
【内容提要】 8.1 优化的分类 8.2 局部优化
8.2.1 常见的局部优化方法 8.2.2 基本块及其划分 8.2.3 基于DAG的局部优化方法
8.1 优化的分类
根据代码优化是否涉及具体的计算机来划分： (1) 与机器无关的优化(在源代码或中间代码级上进行)； 又分三种： ① 全局优化 — 针对整个源程序。 ※ ② 局部优化 — 除全局优化外皆属此类。
3. 删除无用赋值 如：a=b+c;x=d-e;y=b;a=e-h/5; 则 a=b+c 为无用赋值！ 则可优化为 x=d-e;y=b;a=e-h/5; a 未有应用！！
8.2.1 常见的局部优化方法(续1)
4. 不变表达式外提（循环优化之一） 即把循环不变运算，提到循环外。 如：i=1; while(i<100){x=(k+a)/i;…;i++;} 则可优化为 循环不变表达式 i=1;t=k+a; while (i<100){x=t/i;…;i++;}
…
8.2.3 基于DAG的局部优化方法
DAG(Directed Acyclic Graph)是指无环有向图；这 里用来对基本块内的四元式序列进行优化。
Ⅰ. 四元式序列的DAG表示
1. DAG的结点内容及其表示： n1 n2 n4 n3 n5
前驱 ni M|A1,A2,A3,… 后继
DAG
: 运算符; ni: 结点的编码; M : 主标记（运算结果变量，叶结点时，是变量或常 数的初值）;
数组变量赋值运算 A=B[C]
[ ] n3 A
n1

n1
n2
A

n1
n3
A
n2
B
B
C
B[C]=D
n4
转向 ( [B] _ A ) 可选
n2
A
B
n2
C
n1
B
n2
C
n3
D
ni A
n1 B
Ⅱ. 基于DAG的局部优化算法
1. 构造基本块内优化的 DAG:
【假设】 (1) ni 为已有结点号；n为新结点号； (2) 访问各结点信息时，按结点号逆序进行； 【开始】 ① DAG 置空；依次读取一四元式 A=B C ； ② 分别定义 B , C 结点(若已定义过，则免)； (1) 若 赋值四元式 A=B n1…B… ,A ① 把 A 附加于 B 上： ② 若 A 在 n2 已定义过，则: n2 …|…A… (2) 若 常值表达式 A=C1C2 或 A=C1; n1 C|… ,A ① 计算常值 C = C1 C2 ; ② 若 C 在 n1 已定义过，则: n C| A 否则 申请新结点，且： n2 …|…A… ③ 若 A 在 n2 已定义过，则：
8.2.3 基于DAG的局部优化方法
【例8.3】 对下述语句片断进行基于DAG的优化： B=5; A=2*3.14*(R+r); B=2*3.14*(R+r)/(R-r); 1. 根据四元式序列构造优化的DAG: (1)B=5 (2)t1=2*3.14 (3)t2=R+r (4)t3=t1*t2 (5)A=t3 (6)t4=2*3.14 (7)t5=R+r (8)t6=t4*t5 (9)t7=R-r (10)t8=t6/t7 (11)B=t8 t3 |A * 6 A|t3,t6 为什 么要 位置 交换？
Ai :附加标记（运算结果变量，表示它具有该节点所代 表的值，可设置多个）i=1,2,3,…。
8.2.3 基于DAG的局部优化方法
2. 单个四元式的 DAG表示： 赋值 ( = B _ A ) 或 A = B ni B|A
双目运算 ( B C A ) 或 A = B C
单目运算 ( B _ A ) 或 A=B
8.2.2 基本块及其划分(续1)
【例8.1】设有源程序片段如下，划分出基本块；
对应的四 元式序列 x=1; a:r=x*5; r=0; if(x<10){x=x+1;goto a;} ※以基本块为结点的程 序流图，如下所示：