25
DAG在基本块优化中的作用


将一基本块的每一个四元式依次表示成对应 的一个DAG，再按原来构造DAG结点的顺 序重写四元式序列，便可得到“合并已知常 量”、“删除无用赋值”、“删除多余运算” 后的等价基本块。 对于出了基本块以后不再引用的名字，可以 不生成对其进行的赋值运算，而用临时变量 存放相应的运算结果。
局部优化
循环优化
全局优化
对一段顺 序语句序列 优化。
3
在整个程序 对中循环的 代码序列优化。 范围内进行的 优化。
§10.1 基本块与程序控制流图
4
一、基本块

基本块：是指程序中一顺序执行的语句序列， 其中只有一个入口语句(第一个语句)和一个 出口语句(最后一个语句)。 对于一个基本块来说，执行时只能从其 入口语句进入，从其出口语句退出。
37

必经结点：对任意两个结点d和n，若从首结 点出发，到达n的各条通路都必须经过的结 点d，称d为n的必经结点，记作 d DOM n。 必经结点集：n的全部必经结点的集合，记 作D(n)。

38
求必经结点集的算法
设结点n的父结点是 P1，P2，…，Pk，则： D(n)= {n} ∪ (∩ D(Pi)) 1≤i≤k
如果一个结点的基本块的入口语句是程 序的第一条语句，则称此结点为首结点。
10
一个控制流程图可表示成一个三元组： G=(N，E，n0) N：所有结点(基本块)集； E：所有有向边集； n0 ：首结点。
11
有向边
当下述条件有一个成立时，从结点i有 一有向边引向结点j：
i
j
① 基本块j在程序的位置紧跟在i后，且i的出 口语句不是无条件转移或停语句； ② i的出口是goto(S)或if goto(S)，而(S)是j的 入口语句。
48
2.代码外提 把结果独立于循环 执行次数的表达式 提到循环的前面。
(1)P:=0 (2)I:=1 (4)T2:=addr(A)-4 (7)T5:=addr(B)-4 (3)T1:=4*I (5)T3:=T2[T1] (6)T4:=T1 (8)T6:=T5[T4] (9)T7:=T3*T6 (10)P:=P+T7 (11)I:=I+1 (3‘)T1:=T1+4 (12)if I<=20 goto(5)
8
例子
(1) read a (2) read b (3) r:=a mod b (4) if r=0 goto (8) (5) a:= b (6) b:= r (7) goto (3) (8) write b (9) halt
9
B1
B2
B3
B4
二、程序控制流程图（流图）
定义：以基本块为结点，控制程序流向作 为有向边，画出的有向图称为流图。 特点： 具有唯一首结点的有向图； 从首结点开始到流图中任何结点都有通路。
18
四元式对应的DAG结点形式

按其四元式对应结点的后继个数分成四种类 型：0型、1型、2型、3型。
0型： 1型： 2型：
19
例子：构造以下基本块的DAG
(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) T0:=3.14 T1:=2*T0 T2:=R+r A:=T1*T2 B:=A T3:=2*T0 T4:=R+r T5:=T3*T4 T6:=R-r B:=T5*T6
5
查找循环算法




(1)找出回边nd； (2)则n、d必定属于nd回边组成的循环L中， L:={n,d} (3)若n≠ d且n的父节点n’不在L中，则将它添 加L中，L:=L∪ {n’} (4)对(3)求出的父节点n重复(3)，直至不再有 新节点加入为止。
44
四、循环优化


在找出了程序流图中的循环之后，就可以针 对每个循环进行优化工作。 循环优化的三种重要技术： 1. 代码外提 2. 删除归纳变量 3. 强度削弱
26
例：试对基本块P (1)应用DAG进行优化， (2) 假定只有R、H在基本块出口是活跃的, 写出优化后的四元式序列。
27
ቤተ መጻሕፍቲ ባይዱ
S0:=2 S1:=3/S0 S2:=T - C S3:=T + C n6 / n7
H
*
R , H , S6
R:=S0/S3
H:=R S4:=3/S1 S5:=T + C S6:=S4/S5
45
用例子初步理解优化措施
P:=0 for I:=1 to 20 do P:=P+A[I]*B[I]
46
(1) P:=0 (2) I:=1
1.删除多余运算 (3) T1:=4*I (删除公共子表达式) (4) T2:=addr(A)-4 对于两个相同的表 (5) T3:=T2[T1] (6) T4:=4*I T4:=T1 达式计算，若它的 计算结果相同，则 (7) T5:=addr(B)-4 没必要重复的生成 (8) T6:=T5[T4] 两条运算指令。 (9) T7:=T3*T6 (10) P:=P+T7 (11) I:=I+1 (12) if I<=20 goto(3)
5
根据基本块的定义，它是一个按顺序执 行的代码序列，而且只能从它的唯一入口进 入，从其唯一的出口退出，期间不发生任何 分叉。 任何控制转移四元式 所转向的目标语句 出口语句 入口语句
6
入口语句
1. 程序的第一个语句；或者， 2. 条件转移语句或无条件转移语句的转 移目标语句；或者 3. 紧跟在条件转移语句后面的语句。
7
划分基本块的步骤
1、求四元式序列中各个基本块的入口语句。 2、对每一入口语句，构造所属的基本块，该基本块 由： （1）该入口语句到下一入口语句（不包括下一入口 语句）之间的语句序列组成；或， （2）该入口语句到一转移语句（包括该转移语句） 之间的语句序列组成；或， （3）该入口语句到一停语句（包括该停语句）之间 的语句序列组成。 3、凡是未包含在某一基本块中的语句，都是程序中 控制流程不可达的语句，可删除它们。
12
例子：构造以下程序的流图
(1) read a (2) read b (3) r:=a mod b (4) if r=0 goto (8) (5) a:= b (6) b:= r (7) goto (3) (8) write b (9) halt
13
B1
B1
B2
B2
B3
B3 B4
B4
§10.2 局部优化
1 2
3
图中的回边有： 66，74，42
6
4
5 7
41
查找循环算法

每一条回边构成一个循环： 设nd是回边，则该回边构成的循环 包括下列结点： n、d以及不经过d能到达n的所有结点。
42
1 2 4 6 7
43
回边42 循环={4 , 2 , 3 , 7 , 5 , 6} 3 回边74 循环={7，4，5，6} 回边66 循环={6}
S0:=2 S4:=2 S1:=1.5 S2:=T - C
S2:=T - C
S3:=T + C R:=2/S3
S3:=T + C
S5:=S3 R:=2/S3 S6:=R H:=R*S2
30
H:=R*S2
§10.3 循环优化
31



循环就是程序中那些可能反复执行的代码序 列。因为循环中的代码要反复执行，所以必 须着重考虑循环的代码优化。 首先要找出程序中的循环，这就需要对程序 的控制流程进行分析。 使用控制流程图对循环给出定义。
22
(3) 删除无用赋值 如果某变量被赋值之后，随后又被赋新 值，那么可删除对变量的前一个赋值。
23
由DAG生成优化后的代码序列
(1) T0:=3.14 n8 B * n6 A,T5 * T2,T4 n7 T6 n5 + T1,T3 n2 6.28 n3 R n4 r (2) T1:=6.28 (3) T3:=6.28 (4) T2:=R+r (5) T4:=T2
17
基本块的DAG表示

优化中用到的有向图是一种结点带有下述标 记或附加信息的DGA: (1) 图的叶结点以一标识符或常数做标记， 表示该结点代表该变量或常数的值。 (2) 图的内部结点以一运算符作为标记； (3) 图中各个结点上可能附加一个或多个标 识符，表示这些标识符具有该结点所代表 的值，简称附标。
14

局部优化是指基本块内的优化。 对于一个给定的程序，可以把它划分为一系 列的基本块。在各个基本块内分别进行优化。
15
一、局部优化种类
在一个基本块内，可以进行合并已知量、 删除公共子表达式和删除无用赋值三种优化 措施。 合并已知量是 删除公共子表 变量 A被定值 指在编译时就对 达式就是使基本 后不再被引用或 表达式中能计算 块内相同的子表 未经引用又发生 的部分先计算， 达式只计算一次， 了对 A的第二次 并用该值替换这 把重复计算的表 定值，则前一定 部分表达式，而 达式删去，从而 值为无用赋值， 不必生成相应的 避免多余的运算。 应删掉。 代码。
47
(1)P:=0 (2)I:=1 (4)T2:=addr(A)-4 (7)T5:=addr(B)-4 (3)T1:=4*I (5)T3:=T2[T1] (6)T4:=T1 (8)T6:=T5[T4] (9)T7:=T3*T6 (10)P:=P+T7 (11)I:=I+1 (12)if I<=20 goto(3)
S3,S5 n5 + n0 S0 ,S4 n1 2 1.5 S1 n2 T
n4 S2
n3 C
H:=S6*S2
28