第十一章 代码优化
11,1 什么是代码优化
11,2 局部优化
11,3 控制流程分析和循环
11,4 数据流分析举例何谓代码优化,
宗旨,获得较好性能的代码等价意图，结果，权衡阶段,
source front I.R code target
code end generator code
用户 中间代码优 化 目标代码优 化
int arr[10000];
void Binky() {
int i;
for (i=0; i < 10000; i++)
arr[i] = 1;
}
int arr[10000];
void Winky() {
register int *p;
for (p = arr; p < arr +
10000; p++)
*p = 1;
}
优化分类按阶段分,
与机器无关的优化 ---对中间代码进行依赖于机器的优化 --对目标代码进行根据优化所涉及的程序范围分成,
(1)局部优化,(基本块 )
(2)循环优化,对循环中的代码进行优化
(3)全局优化,大范围的优化
优化工作数据流分析 (control-flow analysis)
控制流分析 (data-flow analysis)
变换 (transformations)
优化技术简介 —常数合并
a = 10 * 5 + 6 - b;
_tmp0 = 10 ;
_tmp1 = 5 ;
_tmp2 = _tmp0 * _tmp1 ;
_tmp3 = 6 ;
_tmp4 = _tmp2 + _tmp3 ;
_tmp5 = _tmp4 – b;
a = _tmp5 ;
_tmp0 = 56 ;
_tmp1 = _tmp0
– b ;
a = _tmp1 ;
优化技术简介 —常数传播
_tmp4 = 0 ;
f0 = _tmp4 ;
_tmp5 = 1 ;
f1 = _tmp5 ;
_tmp6 = 2 ;
i = _tmp6 ;
f0 = 0 ;
f1 = 1 ;
i = 2 ;
优化技术简介 —代数简化
x+0 = x
0+x = x
x*1 = x
1*x = x
0/x = 0
x-0 = x
b && true = b
b && false = false
b || true = true
b || false = b
优化技术简介 —代数简化
b = 5 + a + 10 ;
_tmp0 = 5 ;
_tmp1 = _tmp0 + a ;
_tmp2 = _tmp1 + 10 ;
b = _tmp2 ;
_tmp0 = 15 ;
_tmp1 = a +
_tmp0 ;
b = _tmp1 ;
优化技术简介 —降低运算强度
a) i*2 = 2*i = i+i = i<<2
b) i/2 = (int)(i*0.5)
c) 0-1 = -1
d) f*2 = 2.0 * f = f + f
e) f/2.0 = f*0.5
优化技术简介 —复写传播
tmp2 = tmp1 ;
tmp3 = tmp2 * tmp1;
tmp4 = tmp3 ;
tmp5 = tmp3 * tmp2 ;
c = tmp5 + tmp4 ;
tmp3 = tmp1 * tmp1 ;
tmp5 = tmp3 * tmp1 ;
c = tmp5 + tmp3 ;
main()
{
int x,y,z;
x = (1+20)* -x;
y = x*x+(x/y);
y = z = (x/y)/(x*x);
}
tmp1 = 1 + 20 ;
tmp2 = -x ;
x = tmp1 * tmp2 ;
tmp3 = x * x ;
tmp4 = x / y ;
y = tmp3 + tmp4 ;
tmp5 = x / y ;
tmp6 = x * x ;
z = tmp5 / tmp6 ;
y = z ;
优化技术简介
1.删除多余运算
2.循环不变代码外提
3.强度削弱
4.变换循环控制条件
5.合并已知量与复写传播
6.删除无用赋值
P:=0
for I:=1 to 20 do
P:=P+A[I]*B[I]
(1)P:=0
(2)I:=1
(3)T1:=4*I
(4)T2:=addr(A)-4
(5)T3:=T2[T1]
(6)T4:=4*I
(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)
(1)P:=0
(2)I:=1
(3)T1:=4*I
(5)T3:=T2[T1]
(8)T6:=T5[T4]
(9)T7:=T3*T6
(10)P:=P+T7
(11)I:=I+1
(12)if I<=20 goto(3)
(4)T2:=addr(A)-4
(7)T5:=addr(B)-4
(6)T4:=T1
(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)
(1)P:=0
(2)I:=1
(4)T2:=addr(A)-4
(7)T5:=addr(B)-4
(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(5)
(3)T1:=4*I
(3‘)T1:=T1+4
(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)
(1)P:=0
(2)I:=1
(4)T2:=addr(A)-4
(7)T5:=addr(B)-4
(5)T3:=T2[T1]
(6)T4:=T1
(8)T6:=T5[ ]
(9)T7:=T3*T6
(10)P:=P+T7
(11)I:=I+1
(3’)T1:=T1+4
(12)if <=80 goto(5)
(3)T1:=4
T1
T1
(1)P:=0
(2)I:=1
(4)T2:=addr(A)-4
(7)T5:=addr(B)-4
(3)T1:=4
(5)T3:=T2[T1]
(6)T4:=T1
(8)T6:=T5[T1]
(9)T7:=T3*T6
(10)P:=P+T7
(11)I:=I+1
(3’)T1:=T1+4
(12)if T1<=80 goto(5)
(1)P:=0
(4)T2:=addr(A)-4
(7)T5:=addr(B)-4
(3)T1:=4
(5)T3:=T2[T1]
(8)T6:=T5[T1]
(9)T7:=T3*T6
(10)P:=P+T7
(3’)T1:=T1+4
(12)if T1<=80 goto(5)
1 1,2 局部优化：基本块内的优化基本块：是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。
入口语句：
1,程序的第一个语句；或者，
2,条件转移语句或无条件转移语句的转移目标语句；或者
3,紧跟在条件转移语句后面的语句。
划分基本块的算法：
1,求出四元式程序之中各个基本块的入口语句。
2,对每一入口语句，构造其所属的基本块。它是由该语句到下一入口语句 （不包括下一入口语句），或到一转移语句
（包括该转移语句），或到一停语句 （包括该停语句）之间的语句序列组成的。
3,凡未被纳入某一基本块的语句，都是程序中控制流程无法到达的语句，因而也是不会被执行到的语句，我们可以把它们删除。
(1) read (C)
(2) A:= 0
(3) B:= 1
(4) L1,A:=A + B
(5) if B>= C goto L2
(6) B:=B+1
(7) goto L1
(8) L2,write (A)
(9) halt
划分成四个基本块 B1,B2,B3,B4
B 1 ( 1 )
( 2 )
( 3 ) 基本块内实行的优化,合并已知量删除多余运算
B 2 ( 4 ) 删除无用赋值
( 5 )
B 3 ( 6 )
( 7 )
B 4 ( 8 )
( 9 )
基本块的 DAG表示及其应用
DAG Directed Acyclic Graph
无环路有向图基本块的 DAG是在结点上带有标记的 DAG
叶结点 独特的标识符 (名字,常数 )标记内部结点 运算符号标记各个结点 附加标识符标记用 DAG进行基本块的优化四元式 DAG 结点
0 型,A:=B(:=,B,—,A) n1 A
B
1 型,A:=op B(op,B,—,A) n2 A
op
n1
B
2 型,A:=B op C(op,B,C,A) n3 A
op
n1 n2
B C
n2n1
n3
n2
仅含 0,1,2 型四元式的基本块的 D A G 构造算法,
首先,D A G 为空。
对基本块的每一四元式，依次执行：
1,如果 N OD E （ B ）无定义，则构造一标记为 B 的叶结点并定义 N OD E （ B ）为这个结点；
如果当前四元式是 0 型，则记 N OD E ( B ) 的值为 n,转 4 。
如果当前四元式是 1 型，则转 2 ( 1 ）。
如果当前四元式是 2 型，则：
( I) 如果 N OD E ( 1 ) 无定义，则构造一标记为 C 的叶结点并定义 N OD E ( 1 ) 为这个结点；
( II) 转 2 ( 2 )
2,（ 1 ）如果 N O D E ( B ) 是标记为常数的叶结点,则转 2 ( 3 ),
否则转 3 （ 1 ）。
（ 2 ）如果 N O D E ( B) 和 N O D E ( C) 都是标记为常数的叶结点，则转 2 （ 4 ），否则转 3 （ 2 ）。
（ 3 ）执行 op B （即合并已知量），令得到的新常数为
P 。如果 N O D E ( B) 是处理当前四元式时新构造出来的结点，则删除它。如果 N O D E ( P) 无定义，则构造一用 P 做标记的叶结点 n 。置 N O D E ( P) = n,转 4 。
（ 4 ）执行 B op C （即合并已知量），令得到的新常数为
P 。如果 N O D E ( B) 或 N O D E ( C) 是处理当前四元式时新构造出来的结点，则删除它。如果 N O D E ( P) 无定义，则构造一用 P
做标记的叶结点 n 。置 N O D E ( P) = n,转 4 。
3,（ 1 ）检查 D A G 中是否已有一结点，其唯一后继为
N O D E ( B),且标记为 op （即找公共子表达式）。如果没有，
则构造该结点 n,否则就把已有的结点作为它的结点并设该结点为 n,转 4 。
（ 2 ）检查中 D A G 中是否已有一结点，其左后继为
N O D E ( B),其右后继为 N O D E ( C),且标记为 op （即找公共子表达式）。如果没有，则构造该结点 n,否则就把已有的结点作为它的结点并设该结点为 n,转 4 。
4,如果 N O D E ( A) 无定义，则把 A 附加在结点 n 上并令
N O D E ( A ) = n ；否则先把 A 从 N O D E ( A) 结点上附加标识符集中删除 （注意，如果 N O D E ( A) 是叶结点，则其标记 A 不删除），把 A 附加到新结点 n 上并令 N O D E ( A ) = n 。转处理下一四元式。
而后，我们可由 DAG 重新生成原基本块的一个优化的代码序列。
( 1 ) T
0
,= 3,1 4
( 2 ) T
1
,= 2 * T
0
( 3 ) T
2
,= R + r
( 4 ) A,= T
1
*T
2
( 5 ) B,= A
( 6 ) T
3
,= 2 * T
0
( 7 ) T
4
,= R + r
( 8 ) T
5
,= T
3
*T
4
( 9 ) T
6
,= R - r
( 1 0 ) B,= T
5
*T
6
T o
3,1 4
( a)
n1
T 0 T 1
3,1 4 6,2 8
( b )
n2n1
T 2
+
T 0 T 1
3,1 4 6,2 8 R r
( c)
n2
n5
n3n1 n4
A
*
T 2
+
T 0 T 1
3,1 4 6,2 8 R r
( d )
n2
n5
n3n1 n4
n6
A,B
*
T 2
+
T 0 T 1
3,1 4 6,2 8 R r
( e )
n2
n5
n3n1 n4
n6
A,B
*
T 2
+
T 0 T 1,T 3
3,1 4 6,2 8 R r
( f )
n2
n5
n3n1 n4
n6
A,B
*
T 2,T4
+
T 0 T 1,T 3
3,1 4 6,2 8 R r
( g )
n2
n5
n3n1 n4
n6
A,B,T5
*
T 2,T4
+
T 0 T 1,T 3
3,1 4 6,2 8 R r
( h )
n2
n5
n3n1 n4
n6
A,B,T 5
*
T 2,T4 T6
+ -
T 0 T 1,T 3
3,1 4 6,2 8 R r
n2
n5
n3
n7
n1
n4
n6
B
*
A,T 5
* T 2,T 4 T 6
+ -
T 0 T 1,T 3
3,1 4 6,2 8 R r
( j )
n2
n5
n3
n7
n1
n4
n6
n8
( 1 ) T
0
,= 3,1 4
( 2 ) T
1
,= 6,2 8
( 3 ) T
3
,= 6,2 8
( 4 ) T
2
,= R + r
( 5 ) T
4
,= T
2
( 6 ) A,= 6,2 8 * T
2
( 7 ) T
5
,= A
( 8 ) T
6
,= R - r
( 9 ) B,= A * T
6
11,3 控制流分析和循环控制流程图 （流图）：具有唯一首结点的有向图
G=（ N,E,n0） N：结点集 基本块集
E：有向边集
n0：首结点 包含程序第一个语句的基本块有向边
①基本块 j 在程序的位置紧跟在 i 后,且 i 的出口语句不是转移或停语句
② i 的出口是 g o t o ( S ) 或
i f g o t o ( S ),而 ( S )
是 j 的入口语句
i j
例：
* ( 1 ) r ea d x
( 2 0 re a d y
* ( 3 ) r,= x m o d y
( 4 ) i f r= 0 g o t o ( 8 )
* ( 5 ) x,= y
( 6 ) y,= r
( 7 ) g o t o ( 3 )
* ( 8 ) w r i t e y
( 9 ) h a l t
( 1 ) re a d x B1
( 2 ) re a d y
( 3 ) r,= x m o d y B 2
( 4 ) i f r = 0 g o t o ( 8 )
( 5 ) x,= y ( 8 ) w r i t e y B 4
( 6 ) y,= r B 3 ( 9 ) h a l t
( 7 ) g o t o ( 3 )
1
2
4 3
分析程序流图中结点间的关系
m DOM n 定义在程序流图中,对任意两个结点 m和 n,如果从流图的首结点出发,到达 n的任意通路都要经过 m,
则称 m是 n的必经结点,记为 m DOM n (?a,a
MOD a)
必经结点 集 定义结点 n的所有 必经结点 的集合,称为结点 n的必经结点集,记为 D(n).
例,
6
7
3
4
1
2
3
5
7
必经结点 必经结点集
D(1)={1}
D(2)={1,2}
D(3)={1,2,3}
D(4)={1,2,4}
D(5)={1,2,4,5}
D(6)={1,2,4,6}
D(7)={1,2,4,7}
循环的查找循环的查找算法回边：假设 a→ b是流图中的一条有向边，如果 b DOM a，则称 a → b是流图中的一条回边。
有向边 n→d 是回边，组成的循环是由结点 d，结点 n以及有通路到达 n而该通路不经过 d的所有结点组成，并且 d是该循环的唯一入口结点。
回边 6 6循环 {6}
7 4 {4,5,6,7}
4 2 {2,3,4,5,6,7}
循环 (结点序列的性质 )
1.强连通的 (任意两结点间,必有一条通路,且该通路上各结点都属于该结点序列 )
2.它们中间有且只有一个是入口结点,
例,
6
7
3
4
1
2
3
5
7
1
数据流分析
1.活跃变量数据流方程
2.到达 --定值数据流方程
3.讨论 数据流问题分类路径数据流方程解不唯一活跃变量的数据流分析所谓活跃变量就是它的当前值还将被引用
（ 在赋予一个新值之前 ） 。 在全局范围来分析的话,一个变量是活跃的,如果存在一条路径使得该变量被重新定值之前它的当前值还要被引用 。
通过全局活跃变量分析,识别出其当前值不再活跃 （ 即,它的值已经死了 ） 的那些变量 。 死变量的值在基本块的出口处不需要保存 。
令 B为一个基本块,
定义 LiveIn(B)为在基本块 B入口处为活跃的变量的集合 。
定义 LiveOut(B)为基本块 B的出口处的活跃变量的集合 。 LiveIn
和 LiveOut并不是相互独立的,令 S（ B） 为流图中基本块 B的后继的集合,则有 LiveOut(B)=∪ LiveIn(i) i∈ s(B)
如果基本块没有后继，则其 LiveOut为空令 LiveUse(B)为 B中被定值之前要引用变量的集合 。 这个集合由基本块 B中的语句唯一确定 。 容易看出,如果 v∈ LiveUse(B)，
则 v∈ LiveIn(B)； 即 LiveIn(B)? LiveUse(B)。
令 Def(B)为在 B中定值的变量集合 。 如果一个变量在基本块 B的出口处为活跃的且 v?Def(B),则它在 B的入口处也是活跃的,
即,LiveIn(B)? LiveOut(B)- Def(B)
因此有,LiveIn(B)= LiveUse(B)∪ (LiveOut(B)- Def(B))
即：一个变量在基本块入口处为活跃的,则一定有：或者它在基本块的 LiveUse集中,或者它在基本块的出口处为活跃的且在基本块中没有重新定值
a:=1;
if a=b then
b:=1
else c:=1
endif;
d:=a+b
a:=1
if a=b goto B2
b:=1 c:=1
d:=a+b
B1
B2 B3
B4
提取 Def和 LiveUse集合基本块
Def Live
Use
B1 {a} {b}
B2 {b}?
B3 {c}?
B4 {d} {a,b}
a:=1
if a=b goto B2
b:=1 c:=1
d:=a+b
B1
B2 B3
B4
从最后一个基本块开始由后往前计算，可以得到一定的解
LiveIn(B)= LiveUse(B)∪ (LiveOut(B)- Def(B))
LiveOut(B)=∪ LiveIn(i) i∈ s(B)
LiveOut(B4)=?,因此：
LiveIn(B4)= LiveUse(B4)= {a,b}-{d}
现在
LiveOut(B2)=LiveIn (B4)={a,b} -{d}
LiveOut(B3)=LiveIn (B4)= {a,b} -{d}
LiveIn(B2) = LiveOut(B2)- Def(B2)=
{a,b}- {b} -{d} = {a} -{d}
LiveIn(B3) = LiveOut(B3)- Def(B3)= {a,b}
– {c} -{d} = {a,b} – {c} -{d}
LiveOut(B1) = LiveIn (B2) ∪ LiveIn
(B3)= {a}∪ {a,b} -{d} = {a,b} -{d} –
{c}
最后
LiveIn(B1)=
LiveUse(B1)∪ (LiveOut(B1)-Def(B1)) =
{b}∪ ({a,b} – {c} -{d} – {a}) = {b} -
{d} – {c}
a:=1
if a=b goto B2
b:=1 c:=1
d:=a+b
B1
B2 B3
B4
分析程序中所有变量的定值和引用之间的关系到达 --定值数据流方程
OUT[B]=(IN[B]-KILL[B])?GEN[B]
IN[B]=? OUT[p]
p?P[B]
P[B]:B的所有前驱基本块
GEN[B]:B中定值并到达 B出口之后的所有定值点集,
KILL[B]:B之外的那些定值点集,其定值的变量在 B中又重新定值,
IN[B]:到 B入口之前 (紧 )的各变量的所有定值点集
OUT[B]:到达 B出口之后 (紧 )各变量的所有定值点集,
d
1
B
1
d
2
d
3
B
2
d
4
B
3
d
5
B
4
d
6
B
5
d
7
到达一定值
I,=2
J,=I + 1
I,=1
J,=J + 1
J,=J - 4
,=I
,=J
GEN 位向量 KILL
B1 {d1,d2} 1100000 0011100
B2 {d3} 0010000 1000000
B3 {d4} 0001000 0100100
B4 {d5} 0000100 0101000
B5 { } 0000000 0000000
IN[B] OUT[B]
B1 0111100 1100000
B2 1111100 0111100
B3 0111100 0011000
B4 0011000 0010100
B5 0011100 0011100
求解数据流方程 ( 含 n 个结点的流图 )
b e g i n
f o r i,= 1 t o n d o
b e g i n
IN [ B i ],=? ;
OU T [ B i ],= G E N [ B i ] ;
e n d ;
c h a n g e,= t r u e ;
w h i l e c h a n g e d o
b e g i n
c h a n g e,= f a l se ;
f o r i,= 1 t o n d o
b e g i n
n e w i n,=? OU T [ p ] ; / / p? P[ B i ]
i f n e w i n? IN [ B i ] t h e n
b e g i n
c h a n g e,= t u r e ;
IN [ B i ],= n e w i n ;
OU T [B i],= ( IN [B i] – KI L L [ B i ] )? G E N [ B i ]
e n d
e n d
e n d
e n d
应用
- - - - 查找循环不变式 ( 量 )
x,= y + z
条件 y 和 z 的所有可能的 定值点 在该循环外,
ud 链若 x,= y + z 是循环不变式,w 是循环外定值的,
则 v,= x + w 也是循环不变式
- - - - - - - - 全局优化入口结点
循环 L
前置结点入口结点
循环 L
B
1
B
2
B
3
B
4
B
5
( 1 ) i,= 1
( 2 ) i f x < y go t o B
3
(5)y,= y -1
(6)i f y < = 20 go t o B
5
(3)i,= 2
(4)x,= x+ 1
( 7 ) j,= i
1
2
3
4
5
B
1
B ’
2
B
2
B
3
B
4
B
5
i,= 2
i f x < y goto B
3
y,= y - 1
if y < = 20 go to B
5
x,= x + 1
j,= i
i,= 1
B 1
B 2
B 3 B4
B 5
(1)I:=1
I:=3;
(2)if x<y goto(3)
(3)I:=2
(4)x:=x+1
(5)y:=y-1
(6)if y<=20
goto B 2
(7)J:=I
B 1
B 2
B 3 B4
B 5
(1)I:=1
(2)if x<y goto(3)
(3)I:=2
(4)x:=x+1
(5)k:=I;y:=y-1
(6)if y<=20
goto B 2
(7)J:=I
当把循环中的不变运算 s:A:=B op C外提时注意：
（ 2） 要求循环中其它地方不再有 A的定值点。
（ 3） 要求循环中 A的所有引用点都是而且仅仅是这个定值所能达到的
（ 1）要求 s所在结点是循环的所有出口结点的必经结点
（ 4）要求 A在离开循环之后不再是活跃的数据流问题的讨论 合流问题向前流 （ forward-flow)(信息流的方向与控制流是一致的 )和向后流 （ backward – flow）
对每个基本块有一个 IN集合和一个 Out集合,在同一基本块中,In
和 Out集合的关系对于向前流问题,Out (B) = Used (B) ∪ (In(B) – Killed (B))
对于向后流问题,In (B) = Used (B) ∪ (Out (B) – Killed (B))
作为一个边界条件,向前流问题中的起始基本块的 In和向后流问题中最后一个基本块的 Out集合必须指明,通常,这些边界条件集或者为空,或者包含所有可能的值,因问题而定 。
如：到达 --定值数据流方程
OUT[B]=(IN[B]-KILL[B])?GEN[B]
活跃变量数据流方程
LiveIn(B)=LiveUse(B)∪ (LiveOut(B)-Def(B))
数据流问题的讨论路径 问题任意路径数据流分析讨论的数据流假定这么一个性质,即某条路径为真,
（ 如果存在某条路径上被引用这个变量就认为是活跃的；如果存在任何一条路径上被定值,则就认为这个变量是被定值的 ） 。 这种数据流问题被称为任意路径问题 。 任意路径问题的解不能保证所需的性质一定会满足,仅仅是可能满足 。
全路径数据流分析数据流问题也可以用全路径（ all- path）形式来解决，使所需的性质在所有可能的路径都满足。对于全路径问题的解，所需的性质可以保证总是满足。
数据流问题的解不一定唯一考察图 10.20的流图,其中有一个简单的循环 。 在这个流图中,没有对任何变量定值,a在 B4中被引用 。 应用向后流方法传播可以得到一个最明显的解,即四个基本块的 LiveIn集合均为 {a}。
但是,不太合理的解也是可能的 。。
若
Def(B1)=?
Def(B2)=?
Def(B3)=?
Def(B4)=?
Liveuse(B1)=?
Liveuse(B1)=?
Liveuse(B1)=?
Liveuse(B1)={a}
则最明显的解：
LiveIn(B1)=
LiveIn(B1)=
LiveIn(B1)=
LiveIn(B1)={a}
B1
B2 B3
B4
例如，下面解是满足数据流方程的：
基本块 LiveIn LiveOut
B1 {a,b} {a,b}
B2 {a,b} {a,b}
B3 {a,b} {a,b}
B4 {a}?
注意 b没有在任何基本块中被引用！问题所在是基本块 B2和 B3互为祖先；而且，因为 b从未定值
（所有 Def集为空）,一旦 b被包括在 LiveIn集合中，
它就永远消除不了
11,1 什么是代码优化
11,2 局部优化
11,3 控制流程分析和循环
11,4 数据流分析举例何谓代码优化,
宗旨,获得较好性能的代码等价意图，结果，权衡阶段,
source front I.R code target
code end generator code
用户 中间代码优 化 目标代码优 化
int arr[10000];
void Binky() {
int i;
for (i=0; i < 10000; i++)
arr[i] = 1;
}
int arr[10000];
void Winky() {
register int *p;
for (p = arr; p < arr +
10000; p++)
*p = 1;
}
优化分类按阶段分,
与机器无关的优化 ---对中间代码进行依赖于机器的优化 --对目标代码进行根据优化所涉及的程序范围分成,
(1)局部优化,(基本块 )
(2)循环优化,对循环中的代码进行优化
(3)全局优化,大范围的优化
优化工作数据流分析 (control-flow analysis)
控制流分析 (data-flow analysis)
变换 (transformations)
优化技术简介 —常数合并
a = 10 * 5 + 6 - b;
_tmp0 = 10 ;
_tmp1 = 5 ;
_tmp2 = _tmp0 * _tmp1 ;
_tmp3 = 6 ;
_tmp4 = _tmp2 + _tmp3 ;
_tmp5 = _tmp4 – b;
a = _tmp5 ;
_tmp0 = 56 ;
_tmp1 = _tmp0
– b ;
a = _tmp1 ;
优化技术简介 —常数传播
_tmp4 = 0 ;
f0 = _tmp4 ;
_tmp5 = 1 ;
f1 = _tmp5 ;
_tmp6 = 2 ;
i = _tmp6 ;
f0 = 0 ;
f1 = 1 ;
i = 2 ;
优化技术简介 —代数简化
x+0 = x
0+x = x
x*1 = x
1*x = x
0/x = 0
x-0 = x
b && true = b
b && false = false
b || true = true
b || false = b
优化技术简介 —代数简化
b = 5 + a + 10 ;
_tmp0 = 5 ;
_tmp1 = _tmp0 + a ;
_tmp2 = _tmp1 + 10 ;
b = _tmp2 ;
_tmp0 = 15 ;
_tmp1 = a +
_tmp0 ;
b = _tmp1 ;
优化技术简介 —降低运算强度
a) i*2 = 2*i = i+i = i<<2
b) i/2 = (int)(i*0.5)
c) 0-1 = -1
d) f*2 = 2.0 * f = f + f
e) f/2.0 = f*0.5
优化技术简介 —复写传播
tmp2 = tmp1 ;
tmp3 = tmp2 * tmp1;
tmp4 = tmp3 ;
tmp5 = tmp3 * tmp2 ;
c = tmp5 + tmp4 ;
tmp3 = tmp1 * tmp1 ;
tmp5 = tmp3 * tmp1 ;
c = tmp5 + tmp3 ;
main()
{
int x,y,z;
x = (1+20)* -x;
y = x*x+(x/y);
y = z = (x/y)/(x*x);
}
tmp1 = 1 + 20 ;
tmp2 = -x ;
x = tmp1 * tmp2 ;
tmp3 = x * x ;
tmp4 = x / y ;
y = tmp3 + tmp4 ;
tmp5 = x / y ;
tmp6 = x * x ;
z = tmp5 / tmp6 ;
y = z ;
优化技术简介
1.删除多余运算
2.循环不变代码外提
3.强度削弱
4.变换循环控制条件
5.合并已知量与复写传播
6.删除无用赋值
P:=0
for I:=1 to 20 do
P:=P+A[I]*B[I]
(1)P:=0
(2)I:=1
(3)T1:=4*I
(4)T2:=addr(A)-4
(5)T3:=T2[T1]
(6)T4:=4*I
(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)
(1)P:=0
(2)I:=1
(3)T1:=4*I
(5)T3:=T2[T1]
(8)T6:=T5[T4]
(9)T7:=T3*T6
(10)P:=P+T7
(11)I:=I+1
(12)if I<=20 goto(3)
(4)T2:=addr(A)-4
(7)T5:=addr(B)-4
(6)T4:=T1
(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)
(1)P:=0
(2)I:=1
(4)T2:=addr(A)-4
(7)T5:=addr(B)-4
(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(5)
(3)T1:=4*I
(3‘)T1:=T1+4
(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)
(1)P:=0
(2)I:=1
(4)T2:=addr(A)-4
(7)T5:=addr(B)-4
(5)T3:=T2[T1]
(6)T4:=T1
(8)T6:=T5[ ]
(9)T7:=T3*T6
(10)P:=P+T7
(11)I:=I+1
(3’)T1:=T1+4
(12)if <=80 goto(5)
(3)T1:=4
T1
T1
(1)P:=0
(2)I:=1
(4)T2:=addr(A)-4
(7)T5:=addr(B)-4
(3)T1:=4
(5)T3:=T2[T1]
(6)T4:=T1
(8)T6:=T5[T1]
(9)T7:=T3*T6
(10)P:=P+T7
(11)I:=I+1
(3’)T1:=T1+4
(12)if T1<=80 goto(5)
(1)P:=0
(4)T2:=addr(A)-4
(7)T5:=addr(B)-4
(3)T1:=4
(5)T3:=T2[T1]
(8)T6:=T5[T1]
(9)T7:=T3*T6
(10)P:=P+T7
(3’)T1:=T1+4
(12)if T1<=80 goto(5)
1 1,2 局部优化：基本块内的优化基本块：是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。
入口语句：
1,程序的第一个语句；或者，
2,条件转移语句或无条件转移语句的转移目标语句；或者
3,紧跟在条件转移语句后面的语句。
划分基本块的算法：
1,求出四元式程序之中各个基本块的入口语句。
2,对每一入口语句，构造其所属的基本块。它是由该语句到下一入口语句 （不包括下一入口语句），或到一转移语句
（包括该转移语句），或到一停语句 （包括该停语句）之间的语句序列组成的。
3,凡未被纳入某一基本块的语句，都是程序中控制流程无法到达的语句，因而也是不会被执行到的语句，我们可以把它们删除。
(1) read (C)
(2) A:= 0
(3) B:= 1
(4) L1,A:=A + B
(5) if B>= C goto L2
(6) B:=B+1
(7) goto L1
(8) L2,write (A)
(9) halt
划分成四个基本块 B1,B2,B3,B4
B 1 ( 1 )
( 2 )
( 3 ) 基本块内实行的优化,合并已知量删除多余运算
B 2 ( 4 ) 删除无用赋值
( 5 )
B 3 ( 6 )
( 7 )
B 4 ( 8 )
( 9 )
基本块的 DAG表示及其应用
DAG Directed Acyclic Graph
无环路有向图基本块的 DAG是在结点上带有标记的 DAG
叶结点 独特的标识符 (名字,常数 )标记内部结点 运算符号标记各个结点 附加标识符标记用 DAG进行基本块的优化四元式 DAG 结点
0 型,A:=B(:=,B,—,A) n1 A
B
1 型,A:=op B(op,B,—,A) n2 A
op
n1
B
2 型,A:=B op C(op,B,C,A) n3 A
op
n1 n2
B C
n2n1
n3
n2
仅含 0,1,2 型四元式的基本块的 D A G 构造算法,
首先,D A G 为空。
对基本块的每一四元式，依次执行：
1,如果 N OD E （ B ）无定义，则构造一标记为 B 的叶结点并定义 N OD E （ B ）为这个结点；
如果当前四元式是 0 型，则记 N OD E ( B ) 的值为 n,转 4 。
如果当前四元式是 1 型，则转 2 ( 1 ）。
如果当前四元式是 2 型，则：
( I) 如果 N OD E ( 1 ) 无定义，则构造一标记为 C 的叶结点并定义 N OD E ( 1 ) 为这个结点；
( II) 转 2 ( 2 )
2,（ 1 ）如果 N O D E ( B ) 是标记为常数的叶结点,则转 2 ( 3 ),
否则转 3 （ 1 ）。
（ 2 ）如果 N O D E ( B) 和 N O D E ( C) 都是标记为常数的叶结点，则转 2 （ 4 ），否则转 3 （ 2 ）。
（ 3 ）执行 op B （即合并已知量），令得到的新常数为
P 。如果 N O D E ( B) 是处理当前四元式时新构造出来的结点，则删除它。如果 N O D E ( P) 无定义，则构造一用 P 做标记的叶结点 n 。置 N O D E ( P) = n,转 4 。
（ 4 ）执行 B op C （即合并已知量），令得到的新常数为
P 。如果 N O D E ( B) 或 N O D E ( C) 是处理当前四元式时新构造出来的结点，则删除它。如果 N O D E ( P) 无定义，则构造一用 P
做标记的叶结点 n 。置 N O D E ( P) = n,转 4 。
3,（ 1 ）检查 D A G 中是否已有一结点，其唯一后继为
N O D E ( B),且标记为 op （即找公共子表达式）。如果没有，
则构造该结点 n,否则就把已有的结点作为它的结点并设该结点为 n,转 4 。
（ 2 ）检查中 D A G 中是否已有一结点，其左后继为
N O D E ( B),其右后继为 N O D E ( C),且标记为 op （即找公共子表达式）。如果没有，则构造该结点 n,否则就把已有的结点作为它的结点并设该结点为 n,转 4 。
4,如果 N O D E ( A) 无定义，则把 A 附加在结点 n 上并令
N O D E ( A ) = n ；否则先把 A 从 N O D E ( A) 结点上附加标识符集中删除 （注意，如果 N O D E ( A) 是叶结点，则其标记 A 不删除），把 A 附加到新结点 n 上并令 N O D E ( A ) = n 。转处理下一四元式。
而后，我们可由 DAG 重新生成原基本块的一个优化的代码序列。
( 1 ) T
0
,= 3,1 4
( 2 ) T
1
,= 2 * T
0
( 3 ) T
2
,= R + r
( 4 ) A,= T
1
*T
2
( 5 ) B,= A
( 6 ) T
3
,= 2 * T
0
( 7 ) T
4
,= R + r
( 8 ) T
5
,= T
3
*T
4
( 9 ) T
6
,= R - r
( 1 0 ) B,= T
5
*T
6
T o
3,1 4
( a)
n1
T 0 T 1
3,1 4 6,2 8
( b )
n2n1
T 2
+
T 0 T 1
3,1 4 6,2 8 R r
( c)
n2
n5
n3n1 n4
A
*
T 2
+
T 0 T 1
3,1 4 6,2 8 R r
( d )
n2
n5
n3n1 n4
n6
A,B
*
T 2
+
T 0 T 1
3,1 4 6,2 8 R r
( e )
n2
n5
n3n1 n4
n6
A,B
*
T 2
+
T 0 T 1,T 3
3,1 4 6,2 8 R r
( f )
n2
n5
n3n1 n4
n6
A,B
*
T 2,T4
+
T 0 T 1,T 3
3,1 4 6,2 8 R r
( g )
n2
n5
n3n1 n4
n6
A,B,T5
*
T 2,T4
+
T 0 T 1,T 3
3,1 4 6,2 8 R r
( h )
n2
n5
n3n1 n4
n6
A,B,T 5
*
T 2,T4 T6
+ -
T 0 T 1,T 3
3,1 4 6,2 8 R r
n2
n5
n3
n7
n1
n4
n6
B
*
A,T 5
* T 2,T 4 T 6
+ -
T 0 T 1,T 3
3,1 4 6,2 8 R r
( j )
n2
n5
n3
n7
n1
n4
n6
n8
( 1 ) T
0
,= 3,1 4
( 2 ) T
1
,= 6,2 8
( 3 ) T
3
,= 6,2 8
( 4 ) T
2
,= R + r
( 5 ) T
4
,= T
2
( 6 ) A,= 6,2 8 * T
2
( 7 ) T
5
,= A
( 8 ) T
6
,= R - r
( 9 ) B,= A * T
6
11,3 控制流分析和循环控制流程图 （流图）：具有唯一首结点的有向图
G=（ N,E,n0） N：结点集 基本块集
E：有向边集
n0：首结点 包含程序第一个语句的基本块有向边
①基本块 j 在程序的位置紧跟在 i 后,且 i 的出口语句不是转移或停语句
② i 的出口是 g o t o ( S ) 或
i f g o t o ( S ),而 ( S )
是 j 的入口语句
i j
例：
* ( 1 ) r ea d x
( 2 0 re a d y
* ( 3 ) r,= x m o d y
( 4 ) i f r= 0 g o t o ( 8 )
* ( 5 ) x,= y
( 6 ) y,= r
( 7 ) g o t o ( 3 )
* ( 8 ) w r i t e y
( 9 ) h a l t
( 1 ) re a d x B1
( 2 ) re a d y
( 3 ) r,= x m o d y B 2
( 4 ) i f r = 0 g o t o ( 8 )
( 5 ) x,= y ( 8 ) w r i t e y B 4
( 6 ) y,= r B 3 ( 9 ) h a l t
( 7 ) g o t o ( 3 )
1
2
4 3
分析程序流图中结点间的关系
m DOM n 定义在程序流图中,对任意两个结点 m和 n,如果从流图的首结点出发,到达 n的任意通路都要经过 m,
则称 m是 n的必经结点,记为 m DOM n (?a,a
MOD a)
必经结点 集 定义结点 n的所有 必经结点 的集合,称为结点 n的必经结点集,记为 D(n).
例,
6
7
3
4
1
2
3
5
7
必经结点 必经结点集
D(1)={1}
D(2)={1,2}
D(3)={1,2,3}
D(4)={1,2,4}
D(5)={1,2,4,5}
D(6)={1,2,4,6}
D(7)={1,2,4,7}
循环的查找循环的查找算法回边：假设 a→ b是流图中的一条有向边，如果 b DOM a，则称 a → b是流图中的一条回边。
有向边 n→d 是回边，组成的循环是由结点 d，结点 n以及有通路到达 n而该通路不经过 d的所有结点组成，并且 d是该循环的唯一入口结点。
回边 6 6循环 {6}
7 4 {4,5,6,7}
4 2 {2,3,4,5,6,7}
循环 (结点序列的性质 )
1.强连通的 (任意两结点间,必有一条通路,且该通路上各结点都属于该结点序列 )
2.它们中间有且只有一个是入口结点,
例,
6
7
3
4
1
2
3
5
7
1
数据流分析
1.活跃变量数据流方程
2.到达 --定值数据流方程
3.讨论 数据流问题分类路径数据流方程解不唯一活跃变量的数据流分析所谓活跃变量就是它的当前值还将被引用
（ 在赋予一个新值之前 ） 。 在全局范围来分析的话,一个变量是活跃的,如果存在一条路径使得该变量被重新定值之前它的当前值还要被引用 。
通过全局活跃变量分析,识别出其当前值不再活跃 （ 即,它的值已经死了 ） 的那些变量 。 死变量的值在基本块的出口处不需要保存 。
令 B为一个基本块,
定义 LiveIn(B)为在基本块 B入口处为活跃的变量的集合 。
定义 LiveOut(B)为基本块 B的出口处的活跃变量的集合 。 LiveIn
和 LiveOut并不是相互独立的,令 S（ B） 为流图中基本块 B的后继的集合,则有 LiveOut(B)=∪ LiveIn(i) i∈ s(B)
如果基本块没有后继，则其 LiveOut为空令 LiveUse(B)为 B中被定值之前要引用变量的集合 。 这个集合由基本块 B中的语句唯一确定 。 容易看出,如果 v∈ LiveUse(B)，
则 v∈ LiveIn(B)； 即 LiveIn(B)? LiveUse(B)。
令 Def(B)为在 B中定值的变量集合 。 如果一个变量在基本块 B的出口处为活跃的且 v?Def(B),则它在 B的入口处也是活跃的,
即,LiveIn(B)? LiveOut(B)- Def(B)
因此有,LiveIn(B)= LiveUse(B)∪ (LiveOut(B)- Def(B))
即：一个变量在基本块入口处为活跃的,则一定有：或者它在基本块的 LiveUse集中,或者它在基本块的出口处为活跃的且在基本块中没有重新定值
a:=1;
if a=b then
b:=1
else c:=1
endif;
d:=a+b
a:=1
if a=b goto B2
b:=1 c:=1
d:=a+b
B1
B2 B3
B4
提取 Def和 LiveUse集合基本块
Def Live
Use
B1 {a} {b}
B2 {b}?
B3 {c}?
B4 {d} {a,b}
a:=1
if a=b goto B2
b:=1 c:=1
d:=a+b
B1
B2 B3
B4
从最后一个基本块开始由后往前计算，可以得到一定的解
LiveIn(B)= LiveUse(B)∪ (LiveOut(B)- Def(B))
LiveOut(B)=∪ LiveIn(i) i∈ s(B)
LiveOut(B4)=?,因此：
LiveIn(B4)= LiveUse(B4)= {a,b}-{d}
现在
LiveOut(B2)=LiveIn (B4)={a,b} -{d}
LiveOut(B3)=LiveIn (B4)= {a,b} -{d}
LiveIn(B2) = LiveOut(B2)- Def(B2)=
{a,b}- {b} -{d} = {a} -{d}
LiveIn(B3) = LiveOut(B3)- Def(B3)= {a,b}
– {c} -{d} = {a,b} – {c} -{d}
LiveOut(B1) = LiveIn (B2) ∪ LiveIn
(B3)= {a}∪ {a,b} -{d} = {a,b} -{d} –
{c}
最后
LiveIn(B1)=
LiveUse(B1)∪ (LiveOut(B1)-Def(B1)) =
{b}∪ ({a,b} – {c} -{d} – {a}) = {b} -
{d} – {c}
a:=1
if a=b goto B2
b:=1 c:=1
d:=a+b
B1
B2 B3
B4
分析程序中所有变量的定值和引用之间的关系到达 --定值数据流方程
OUT[B]=(IN[B]-KILL[B])?GEN[B]
IN[B]=? OUT[p]
p?P[B]
P[B]:B的所有前驱基本块
GEN[B]:B中定值并到达 B出口之后的所有定值点集,
KILL[B]:B之外的那些定值点集,其定值的变量在 B中又重新定值,
IN[B]:到 B入口之前 (紧 )的各变量的所有定值点集
OUT[B]:到达 B出口之后 (紧 )各变量的所有定值点集,
d
1
B
1
d
2
d
3
B
2
d
4
B
3
d
5
B
4
d
6
B
5
d
7
到达一定值
I,=2
J,=I + 1
I,=1
J,=J + 1
J,=J - 4
,=I
,=J
GEN 位向量 KILL
B1 {d1,d2} 1100000 0011100
B2 {d3} 0010000 1000000
B3 {d4} 0001000 0100100
B4 {d5} 0000100 0101000
B5 { } 0000000 0000000
IN[B] OUT[B]
B1 0111100 1100000
B2 1111100 0111100
B3 0111100 0011000
B4 0011000 0010100
B5 0011100 0011100
求解数据流方程 ( 含 n 个结点的流图 )
b e g i n
f o r i,= 1 t o n d o
b e g i n
IN [ B i ],=? ;
OU T [ B i ],= G E N [ B i ] ;
e n d ;
c h a n g e,= t r u e ;
w h i l e c h a n g e d o
b e g i n
c h a n g e,= f a l se ;
f o r i,= 1 t o n d o
b e g i n
n e w i n,=? OU T [ p ] ; / / p? P[ B i ]
i f n e w i n? IN [ B i ] t h e n
b e g i n
c h a n g e,= t u r e ;
IN [ B i ],= n e w i n ;
OU T [B i],= ( IN [B i] – KI L L [ B i ] )? G E N [ B i ]
e n d
e n d
e n d
e n d
应用
- - - - 查找循环不变式 ( 量 )
x,= y + z
条件 y 和 z 的所有可能的 定值点 在该循环外,
ud 链若 x,= y + z 是循环不变式,w 是循环外定值的,
则 v,= x + w 也是循环不变式
- - - - - - - - 全局优化入口结点
循环 L
前置结点入口结点
循环 L
B
1
B
2
B
3
B
4
B
5
( 1 ) i,= 1
( 2 ) i f x < y go t o B
3
(5)y,= y -1
(6)i f y < = 20 go t o B
5
(3)i,= 2
(4)x,= x+ 1
( 7 ) j,= i
1
2
3
4
5
B
1
B ’
2
B
2
B
3
B
4
B
5
i,= 2
i f x < y goto B
3
y,= y - 1
if y < = 20 go to B
5
x,= x + 1
j,= i
i,= 1
B 1
B 2
B 3 B4
B 5
(1)I:=1
I:=3;
(2)if x<y goto(3)
(3)I:=2
(4)x:=x+1
(5)y:=y-1
(6)if y<=20
goto B 2
(7)J:=I
B 1
B 2
B 3 B4
B 5
(1)I:=1
(2)if x<y goto(3)
(3)I:=2
(4)x:=x+1
(5)k:=I;y:=y-1
(6)if y<=20
goto B 2
(7)J:=I
当把循环中的不变运算 s:A:=B op C外提时注意：
（ 2） 要求循环中其它地方不再有 A的定值点。
（ 3） 要求循环中 A的所有引用点都是而且仅仅是这个定值所能达到的
（ 1）要求 s所在结点是循环的所有出口结点的必经结点
（ 4）要求 A在离开循环之后不再是活跃的数据流问题的讨论 合流问题向前流 （ forward-flow)(信息流的方向与控制流是一致的 )和向后流 （ backward – flow）
对每个基本块有一个 IN集合和一个 Out集合,在同一基本块中,In
和 Out集合的关系对于向前流问题,Out (B) = Used (B) ∪ (In(B) – Killed (B))
对于向后流问题,In (B) = Used (B) ∪ (Out (B) – Killed (B))
作为一个边界条件,向前流问题中的起始基本块的 In和向后流问题中最后一个基本块的 Out集合必须指明,通常,这些边界条件集或者为空,或者包含所有可能的值,因问题而定 。
如：到达 --定值数据流方程
OUT[B]=(IN[B]-KILL[B])?GEN[B]
活跃变量数据流方程
LiveIn(B)=LiveUse(B)∪ (LiveOut(B)-Def(B))
数据流问题的讨论路径 问题任意路径数据流分析讨论的数据流假定这么一个性质,即某条路径为真,
（ 如果存在某条路径上被引用这个变量就认为是活跃的；如果存在任何一条路径上被定值,则就认为这个变量是被定值的 ） 。 这种数据流问题被称为任意路径问题 。 任意路径问题的解不能保证所需的性质一定会满足,仅仅是可能满足 。
全路径数据流分析数据流问题也可以用全路径（ all- path）形式来解决，使所需的性质在所有可能的路径都满足。对于全路径问题的解，所需的性质可以保证总是满足。
数据流问题的解不一定唯一考察图 10.20的流图,其中有一个简单的循环 。 在这个流图中,没有对任何变量定值,a在 B4中被引用 。 应用向后流方法传播可以得到一个最明显的解,即四个基本块的 LiveIn集合均为 {a}。
但是,不太合理的解也是可能的 。。
若
Def(B1)=?
Def(B2)=?
Def(B3)=?
Def(B4)=?
Liveuse(B1)=?
Liveuse(B1)=?
Liveuse(B1)=?
Liveuse(B1)={a}
则最明显的解：
LiveIn(B1)=
LiveIn(B1)=
LiveIn(B1)=
LiveIn(B1)={a}
B1
B2 B3
B4
例如，下面解是满足数据流方程的：
基本块 LiveIn LiveOut
B1 {a,b} {a,b}
B2 {a,b} {a,b}
B3 {a,b} {a,b}
B4 {a}?
注意 b没有在任何基本块中被引用！问题所在是基本块 B2和 B3互为祖先；而且，因为 b从未定值
（所有 Def集为空）,一旦 b被包括在 LiveIn集合中，
它就永远消除不了
