第 9章 代码优化
9.1 代码优化概述
9.2 局部优化
9.3 控制流程分析和循环
9.4 数据流分析举例
9.1
何谓代码优化,
宗旨：
为获得较好性能的代码而进行的变换等价 变换权衡 ( 意图，结果 )
阶段,
(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;
}
优化技术简介 —常数合并
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
优化分类和 优化工作按阶段分,
与机器无关的优化 ---对中间代码进行依赖于机器的优化 --对目标代码进行根据优化所涉及的程序范围分成,
(1)局部优化,(基本块 )
(2)循环优化,对循环中的代码进行优化
(3)全局优化,大范围的优化优化工作数据流分析 (data-flow analysis)
控制流分析 (controldata-flow analysis)
变换 (transformations)
控制流分析
(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)
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 ;
数据流分析
x*x x/y
一些 优化技术
1.删除多余运算
2.循环不变代码外提
3.强度削弱
4.变换循环控制条件
5.合并已知量
6.删除无用赋值
7.代数化简
8.复写传播优化技术 —削弱运算强度
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 ;
从例子
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)
9.2局部优化：基本块内的优化基本块：是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。
入口语句：
程序的第一个语句；或者，
条件转移语句或无条件转移语句的转移目标语句；或者
紧跟在条件转移语句后面的语句。
划分基本块的算法：
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
B1 (1)
(2)
(3) 基本块内实行的优化,合并已知量删除多余运算
B2 (4) 删除无用赋值
(5) … …
B 3 (6)
(7)
B4 (8)
(9)
基本块的 DAG表示及其应用
DAG Directed Acyclic Graph
无环路有向图基本块的 DAG是在结点上带有标记的 DAG
叶结点 有独特的标识符 (名字,常数 )标记内部结点 有运算符号标记各个结点 可有附加标识符标记用 DAG进行基本块的优化四元式
DAG结点
0 型,A:=B(:=,B,—,A) A
B
1 型,A:=op B(op,B,—,A) A
op
B
2 型,A:=B op C(op,B,C,A) n3 A
op
n1 n2
B C
n1
n2n1
n3
n1
n2
仅含 0,1,2 型四元式的基本块的 DA G 构造算法,
首先,DAG 为空。
对基本块的每一四元式，依次执行,
1,如果 NO DE （ B ）无定义，则构造一标记为 B 的叶结点并定义 NO DE （ B ）为这个结点；
如果当前四元式是 0 型，则记 NO DE ( B ) 的值为 n,转 4 。
如果当前四元式是 1 型，则转 2 ( 1 ）。
如果当前四元式是 2 型，则,
(I) 如果 NO DE ( C ) 无定义，则构造一标记为 C 的叶结点并定义 NO DE ( C ) 为这个结点；
(II) 转 2 ( 2 )
2,（ 1 ）如果 N OD E ( B ) 是标记为常数的叶结点,则转 2 ( 3 ),
否则转 3 （ 1 ）。
（ 2 ）如果 N OD E ( B) 和 N OD E ( C) 都是标记为常数的叶结点，则转 2 （ 4 ），否则转 3 （ 2 ）。
（ 3 ）执行 op B （即合并已知量），令得到的新常数为
P 。如果 N OD E ( B) 是处理当前四元式时新构造出来的结点，则删除它。如果 N OD E ( P) 无定义，则构造一用 P 做标记的叶结点 n 。置 N OD E ( P) = n,转 4 。
（ 4 ）执行 B op C （即合并已知量），令得到的新常数为
P 。如果 N OD E ( B) 或 N OD E ( C) 是处理当前四元式时新构造出来的结点，则删除它。如果 N OD E ( P) 无定义，则构造一用 P
做标记的叶结点 n 。置 N OD E ( P) = n,转 4 。
3,（ 1 ）检查 D A G 中是否已有一结点，其唯一后继为
N OD E ( B),且标记为 op （即找公共子表达式）。如果没有，
则构造该结点 n,否则就把已有的结点作为它的结点并设该结点为 n,转 4 。
（ 2 ）检查中 D A G 中是否已有一结点，其左后继为
N OD E ( B),其右后继为 N OD 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,14
(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
(10 ) B:=T
5
*T
6
(1) T
0
:=3,14
(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
(10 ) B:=T
5
*T
6
To
3.1 4
( a )
n1
(1) T
0
:=3,14
(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
(10 ) B:=T
5
*T
6
T0 T1
3.1 4 6.2 8
( b)
n2 n1
(1) T
0
:=3,14
(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
(10 ) B:=T
5
*T
6
T2
+
T0 T1
3.1 4 6.2 8 R r
(c)
n2
n5
n3 n1 n4
(1) T
0
:=3,14
(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
(10 ) B:=T
5
*T
6
A
*
T2
+
T0 T1
3.1 4 6.2 8 R r
(d)
n2
n5
n3 n1 n4
n6
(1) T
0
:=3,14
(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
(10 ) B:=T
5
*T
6
A,B
*
T2
+
T0 T1
3.1 4 6.2 8 R r
(e)
n2
n5
n3 n1 n4
n6
(1) T
0
:=3,14
(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
(10 ) B:=T
5
*T
6
A,B
*
T2
+
T0 T1,T 3
3.1 4 6.2 8 R r
(f )
n2
n5
n3 n1
n4
n6
(1) T
0
:= 3.14
(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
(10) B:=T
5
*T
6
A,B
*
T2,T 4
+
T0 T 1,T3
3.14 6,28 R r
(g)
n2
n5
n3 n1
n4
n6
(1) T
0
:= 3.14
(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
(10) B:=T
5
*T
6
A,B,T5
*
T2,T 4
+
T0 T 1,T3
3.14 6,28 R r
(h)
n2
n5
n3 n1
n4
n6
(1) T
0
:= 3.14
(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
(10) B:=T
5
*T
6
A,B,T5
*
T2,T4 T 6
+ -
T0 T 1,T3
3.14 6,28 R r
n2
n5
n3
n7
n1
n4
n6
B
*
A,T 5
* T2,T4 T6
+ -
T0 T 1,T3
3.14 6,28 R r
(j)
n2
n5
n3
n7
n1
n4
n6
n8
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
T0:=3.14
T1:=6.28
T3:=6.28
T2:=R+r
T4:=T2
A:=6.28*T2
T5:=A
T6:=R-r
B:=A*T6
9.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 e a d x
( 2 0 r e 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
DOM 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
9.4数据流分析举例
1.活跃变量数据流方程
2.到达 --定值数据流方程
3.讨论 数据流问题分类路径数据流方程解不唯一活跃变量的数据流分析
对程序中的某变量Ａ和某点 p而言，如果存在一条从 p开始的通路，其中引用了Ａ在点 p
的值，则称 Ａ在点 p是活跃的。
无论是基本块优化或是循环优化，都可能引起某些变量的定值在该基本块或循环内不会被引用；只要这些变量在基本块或循环的出口之后也不是活跃的，那么，这些变量在该基本块或循环内的定值就是无用赋值，从而可以予以删除。因此，活跃变量的分析对于删除无用赋值是很有意义的。
活跃变量的数据流分析所谓活跃变量就是它的当前值还将被引用
（ 在赋予一个新值之前 ） 。 在全局范围来分析的话,一个变量是活跃的,如果存在一条路径使得该变量被重新定值之前它的当前值还要被引用 。
通过全局活跃变量分析,识别出其当前值不再活跃 （ 即,它的值已经死了 ） 的那些变量 。 死变量的值在基本块的出口处不需要保存 。
到达 --定值数据流分析
变量 A的定值是一个语句 (四元式 )，它赋值或可能赋值给 A，最普通的定值是对 A的赋值或读值到 A的语句，该语句的位置 称作 A
的定值点。
所谓变量 A的定值点ｄ到达某点ｐ，是指如果有路径从紧跟ｄ的点到达ｐ，并且在这条路径上ｄ没有被“注销”（所谓注销是指该变量重新被定值）。直观上说是指流图中从
ｄ有一条路径到达ｐ且该通路上没有Ａ的其它定值。
活跃变量的数据流方程令 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(在 B中定值的变量集合 )和 LiveUse (B中被定值之前要引用变量的集合 )集合基本块
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}
LiveOut(B3)=LiveIn (B4)= {a,b}
LiveIn(B2) = LiveOut(B2)- Def(B2)=
{a,b}- {b} = {a}
LiveIn(B3) = LiveOut(B3)- Def(B3)=
{a,b}– {c} = {a,b}
LiveOut(B1) = LiveIn (B2) ∪ LiveIn
(B3)= {a}∪ {a,b} = {a,b}
最后
LiveIn(B1)=
LiveUse(B1)∪ (LiveOut(B1)-Def(B1))
= {b}∪ ({a,b}–{a}) = {b}
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个结点的流图 )
begin
for i:= 1 to n do
begin
IN[ Bi],=?;
OUT[Bi ],= GEN[Bi ];
end;
change,= true;
while change do
begin
change,= false;
for i,= 1 to n do
begin
newin,=? OUT[p]; //p?P[Bi]
if newin? IN[Bi] then
begin
change,= ture;
IN[Bi],= newin;
OUT[Bi],= (IN[Bi] – KILL[Bi])? GEN[Bi]
end
end
end
end
到达 --定值信息的应用 （ｕｄ链） 把到达－定值信息存储作为引用－定值链,它是所有能够到达变量的某个引用的定值表假设在程序中某点 u引用了变量 A的值，则把能到达 u的 A的所有定值点的全体，称为 A在引用点 u的引用－定值链。也称之为ｕｄ链。
在进行循环优化时，为了求出循环中的所有不变运算，我们需要知道各变量引用点的ｕ
ｄ链信息。
到达 --定值信息的应用计算各个变量在任何引用点的ｕｄ链。其规则如下：
１,如果在基本块Ｂ中，变量Ａ的引用点ｕ之前有Ａ的定值点ｄ，并且Ａ在点ｄ的定值到达ｕ，那么Ａ在点ｕ的ｕｄ链就是｛ｄ｝。
２,如果在基本块中，变量Ａ的引用点ｕ之前没有Ａ的定值点，那么，ｉｎ
［Ｂ］中Ａ的所有定值点均到达ｕ，它们就是Ａ在点ｕ的ｕｄ链。
采用上述规则，我们可以求出图中变量ｉ和ｊ的ｕｄ链：
ｉ在引用点ｄ 2的ｕｄ链为｛ｄ１｝，
ｊ在ｄ４的ｕｄ链为｛ｄ２，ｄ４，ｄ５｝，
ｊ在ｄ５的ｕｄ链为｛ｄ４｝，
ｉ在ｄ６的ｕｄ链为｛ｄ３｝，
ｊ在ｄ７的ｕｄ链为｛ｄ４，ｄ５｝，
有了ｕｄ链信息，可进行各种优化，一系列循环优化。在整个程序范围内进行常数传播和合并已知量。
ud链 应用
----查找循环不变式 (量 )
x:=y+z
条件 y和 z的所有可能的 定值点 在该循环外,
--------全局优化若 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 go to 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
B
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
B
B
当把循环中的不变运算 s:A:=B op C外提时注意：
（ 2） 要求循环中其它地方不再有 A的定值点。
（ 3） 要求循环中 A的所有引用点都是而且仅仅是这个定值所能达到的
（ 1）要求 s所在结点是循环的所有出口结点的必经结点
（ 4）要求 A在离开循环之后不再是活跃的怎样建立和解数据流方程依据三个因素：
１,产生和注销的概念依赖于所需要的信息，即根据数据流方程所要解决的问题来决定。对某些问题，有可能不是沿着控制流前进和由 in[S]来定义 out[S]，而是反向前进和由 out[S]来定义 in[S]。
２,因为数据沿控制路径流动，所以数据流分析受程序控制结构影响。事实上，当我们写 out[S]时，隐含地认为控制流从语句的唯一出口点离开这个语句。通常方程是在基本块一级建立而不是在语句级建立。因为基本块有唯一的出口点。
３,在过程调用，通过指针赋值以及对数组变量的赋值语句中，常常会伴随一些问题，对于这些问题需进行相应的处理。
数据流问题的讨论 合流问题向前流 （ 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）形式来解决，使所需的性质在所有可能的路径都满足。对于全路径问题的解，所需的性质可以保证总是满足。
数据流问题的解不一定唯一
LiveIn(B)= LiveUse(B)∪ (LiveOut(B)- Def(B))
LiveOut(B)=∪ LiveIn(i) i∈ s(B)
若
Def(B1)=?
Def(B2)=?
Def(B3)=?
Def(B4)=?
Liveuse(B1)=?
Liveuse(B2)=?
Liveuse(B3)=?
Liveuse(B4)={a}
应用向后流方法传播可以得到一个最明显的解，即四个基本块的LiveIn集合均为 {a}
LiveIn(B1)=
LiveIn(B2)=
LiveIn(B3)=
LiveIn(B4)={a}
如下流图，没有对任何变量定值,a在 B4中被引用
:= 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集合中，
它就永远消除不了
9.1 代码优化概述
9.2 局部优化
9.3 控制流程分析和循环
9.4 数据流分析举例
9.1
何谓代码优化,
宗旨：
为获得较好性能的代码而进行的变换等价 变换权衡 ( 意图，结果 )
阶段,
(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;
}
优化技术简介 —常数合并
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
优化分类和 优化工作按阶段分,
与机器无关的优化 ---对中间代码进行依赖于机器的优化 --对目标代码进行根据优化所涉及的程序范围分成,
(1)局部优化,(基本块 )
(2)循环优化,对循环中的代码进行优化
(3)全局优化,大范围的优化优化工作数据流分析 (data-flow analysis)
控制流分析 (controldata-flow analysis)
变换 (transformations)
控制流分析
(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)
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 ;
数据流分析
x*x x/y
一些 优化技术
1.删除多余运算
2.循环不变代码外提
3.强度削弱
4.变换循环控制条件
5.合并已知量
6.删除无用赋值
7.代数化简
8.复写传播优化技术 —削弱运算强度
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 ;
从例子
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)
9.2局部优化：基本块内的优化基本块：是指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句。
入口语句：
程序的第一个语句；或者，
条件转移语句或无条件转移语句的转移目标语句；或者
紧跟在条件转移语句后面的语句。
划分基本块的算法：
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
B1 (1)
(2)
(3) 基本块内实行的优化,合并已知量删除多余运算
B2 (4) 删除无用赋值
(5) … …
B 3 (6)
(7)
B4 (8)
(9)
基本块的 DAG表示及其应用
DAG Directed Acyclic Graph
无环路有向图基本块的 DAG是在结点上带有标记的 DAG
叶结点 有独特的标识符 (名字,常数 )标记内部结点 有运算符号标记各个结点 可有附加标识符标记用 DAG进行基本块的优化四元式
DAG结点
0 型,A:=B(:=,B,—,A) A
B
1 型,A:=op B(op,B,—,A) A
op
B
2 型,A:=B op C(op,B,C,A) n3 A
op
n1 n2
B C
n1
n2n1
n3
n1
n2
仅含 0,1,2 型四元式的基本块的 DA G 构造算法,
首先,DAG 为空。
对基本块的每一四元式，依次执行,
1,如果 NO DE （ B ）无定义，则构造一标记为 B 的叶结点并定义 NO DE （ B ）为这个结点；
如果当前四元式是 0 型，则记 NO DE ( B ) 的值为 n,转 4 。
如果当前四元式是 1 型，则转 2 ( 1 ）。
如果当前四元式是 2 型，则,
(I) 如果 NO DE ( C ) 无定义，则构造一标记为 C 的叶结点并定义 NO DE ( C ) 为这个结点；
(II) 转 2 ( 2 )
2,（ 1 ）如果 N OD E ( B ) 是标记为常数的叶结点,则转 2 ( 3 ),
否则转 3 （ 1 ）。
（ 2 ）如果 N OD E ( B) 和 N OD E ( C) 都是标记为常数的叶结点，则转 2 （ 4 ），否则转 3 （ 2 ）。
（ 3 ）执行 op B （即合并已知量），令得到的新常数为
P 。如果 N OD E ( B) 是处理当前四元式时新构造出来的结点，则删除它。如果 N OD E ( P) 无定义，则构造一用 P 做标记的叶结点 n 。置 N OD E ( P) = n,转 4 。
（ 4 ）执行 B op C （即合并已知量），令得到的新常数为
P 。如果 N OD E ( B) 或 N OD E ( C) 是处理当前四元式时新构造出来的结点，则删除它。如果 N OD E ( P) 无定义，则构造一用 P
做标记的叶结点 n 。置 N OD E ( P) = n,转 4 。
3,（ 1 ）检查 D A G 中是否已有一结点，其唯一后继为
N OD E ( B),且标记为 op （即找公共子表达式）。如果没有，
则构造该结点 n,否则就把已有的结点作为它的结点并设该结点为 n,转 4 。
（ 2 ）检查中 D A G 中是否已有一结点，其左后继为
N OD E ( B),其右后继为 N OD 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,14
(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
(10 ) B:=T
5
*T
6
(1) T
0
:=3,14
(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
(10 ) B:=T
5
*T
6
To
3.1 4
( a )
n1
(1) T
0
:=3,14
(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
(10 ) B:=T
5
*T
6
T0 T1
3.1 4 6.2 8
( b)
n2 n1
(1) T
0
:=3,14
(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
(10 ) B:=T
5
*T
6
T2
+
T0 T1
3.1 4 6.2 8 R r
(c)
n2
n5
n3 n1 n4
(1) T
0
:=3,14
(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
(10 ) B:=T
5
*T
6
A
*
T2
+
T0 T1
3.1 4 6.2 8 R r
(d)
n2
n5
n3 n1 n4
n6
(1) T
0
:=3,14
(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
(10 ) B:=T
5
*T
6
A,B
*
T2
+
T0 T1
3.1 4 6.2 8 R r
(e)
n2
n5
n3 n1 n4
n6
(1) T
0
:=3,14
(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
(10 ) B:=T
5
*T
6
A,B
*
T2
+
T0 T1,T 3
3.1 4 6.2 8 R r
(f )
n2
n5
n3 n1
n4
n6
(1) T
0
:= 3.14
(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
(10) B:=T
5
*T
6
A,B
*
T2,T 4
+
T0 T 1,T3
3.14 6,28 R r
(g)
n2
n5
n3 n1
n4
n6
(1) T
0
:= 3.14
(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
(10) B:=T
5
*T
6
A,B,T5
*
T2,T 4
+
T0 T 1,T3
3.14 6,28 R r
(h)
n2
n5
n3 n1
n4
n6
(1) T
0
:= 3.14
(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
(10) B:=T
5
*T
6
A,B,T5
*
T2,T4 T 6
+ -
T0 T 1,T3
3.14 6,28 R r
n2
n5
n3
n7
n1
n4
n6
B
*
A,T 5
* T2,T4 T6
+ -
T0 T 1,T3
3.14 6,28 R r
(j)
n2
n5
n3
n7
n1
n4
n6
n8
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
T0:=3.14
T1:=6.28
T3:=6.28
T2:=R+r
T4:=T2
A:=6.28*T2
T5:=A
T6:=R-r
B:=A*T6
9.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 e a d x
( 2 0 r e 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
DOM 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
9.4数据流分析举例
1.活跃变量数据流方程
2.到达 --定值数据流方程
3.讨论 数据流问题分类路径数据流方程解不唯一活跃变量的数据流分析
对程序中的某变量Ａ和某点 p而言，如果存在一条从 p开始的通路，其中引用了Ａ在点 p
的值，则称 Ａ在点 p是活跃的。
无论是基本块优化或是循环优化，都可能引起某些变量的定值在该基本块或循环内不会被引用；只要这些变量在基本块或循环的出口之后也不是活跃的，那么，这些变量在该基本块或循环内的定值就是无用赋值，从而可以予以删除。因此，活跃变量的分析对于删除无用赋值是很有意义的。
活跃变量的数据流分析所谓活跃变量就是它的当前值还将被引用
（ 在赋予一个新值之前 ） 。 在全局范围来分析的话,一个变量是活跃的,如果存在一条路径使得该变量被重新定值之前它的当前值还要被引用 。
通过全局活跃变量分析,识别出其当前值不再活跃 （ 即,它的值已经死了 ） 的那些变量 。 死变量的值在基本块的出口处不需要保存 。
到达 --定值数据流分析
变量 A的定值是一个语句 (四元式 )，它赋值或可能赋值给 A，最普通的定值是对 A的赋值或读值到 A的语句，该语句的位置 称作 A
的定值点。
所谓变量 A的定值点ｄ到达某点ｐ，是指如果有路径从紧跟ｄ的点到达ｐ，并且在这条路径上ｄ没有被“注销”（所谓注销是指该变量重新被定值）。直观上说是指流图中从
ｄ有一条路径到达ｐ且该通路上没有Ａ的其它定值。
活跃变量的数据流方程令 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(在 B中定值的变量集合 )和 LiveUse (B中被定值之前要引用变量的集合 )集合基本块
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}
LiveOut(B3)=LiveIn (B4)= {a,b}
LiveIn(B2) = LiveOut(B2)- Def(B2)=
{a,b}- {b} = {a}
LiveIn(B3) = LiveOut(B3)- Def(B3)=
{a,b}– {c} = {a,b}
LiveOut(B1) = LiveIn (B2) ∪ LiveIn
(B3)= {a}∪ {a,b} = {a,b}
最后
LiveIn(B1)=
LiveUse(B1)∪ (LiveOut(B1)-Def(B1))
= {b}∪ ({a,b}–{a}) = {b}
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个结点的流图 )
begin
for i:= 1 to n do
begin
IN[ Bi],=?;
OUT[Bi ],= GEN[Bi ];
end;
change,= true;
while change do
begin
change,= false;
for i,= 1 to n do
begin
newin,=? OUT[p]; //p?P[Bi]
if newin? IN[Bi] then
begin
change,= ture;
IN[Bi],= newin;
OUT[Bi],= (IN[Bi] – KILL[Bi])? GEN[Bi]
end
end
end
end
到达 --定值信息的应用 （ｕｄ链） 把到达－定值信息存储作为引用－定值链,它是所有能够到达变量的某个引用的定值表假设在程序中某点 u引用了变量 A的值，则把能到达 u的 A的所有定值点的全体，称为 A在引用点 u的引用－定值链。也称之为ｕｄ链。
在进行循环优化时，为了求出循环中的所有不变运算，我们需要知道各变量引用点的ｕ
ｄ链信息。
到达 --定值信息的应用计算各个变量在任何引用点的ｕｄ链。其规则如下：
１,如果在基本块Ｂ中，变量Ａ的引用点ｕ之前有Ａ的定值点ｄ，并且Ａ在点ｄ的定值到达ｕ，那么Ａ在点ｕ的ｕｄ链就是｛ｄ｝。
２,如果在基本块中，变量Ａ的引用点ｕ之前没有Ａ的定值点，那么，ｉｎ
［Ｂ］中Ａ的所有定值点均到达ｕ，它们就是Ａ在点ｕ的ｕｄ链。
采用上述规则，我们可以求出图中变量ｉ和ｊ的ｕｄ链：
ｉ在引用点ｄ 2的ｕｄ链为｛ｄ１｝，
ｊ在ｄ４的ｕｄ链为｛ｄ２，ｄ４，ｄ５｝，
ｊ在ｄ５的ｕｄ链为｛ｄ４｝，
ｉ在ｄ６的ｕｄ链为｛ｄ３｝，
ｊ在ｄ７的ｕｄ链为｛ｄ４，ｄ５｝，
有了ｕｄ链信息，可进行各种优化，一系列循环优化。在整个程序范围内进行常数传播和合并已知量。
ud链 应用
----查找循环不变式 (量 )
x:=y+z
条件 y和 z的所有可能的 定值点 在该循环外,
--------全局优化若 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 go to 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
B
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
B
B
当把循环中的不变运算 s:A:=B op C外提时注意：
（ 2） 要求循环中其它地方不再有 A的定值点。
（ 3） 要求循环中 A的所有引用点都是而且仅仅是这个定值所能达到的
（ 1）要求 s所在结点是循环的所有出口结点的必经结点
（ 4）要求 A在离开循环之后不再是活跃的怎样建立和解数据流方程依据三个因素：
１,产生和注销的概念依赖于所需要的信息，即根据数据流方程所要解决的问题来决定。对某些问题，有可能不是沿着控制流前进和由 in[S]来定义 out[S]，而是反向前进和由 out[S]来定义 in[S]。
２,因为数据沿控制路径流动，所以数据流分析受程序控制结构影响。事实上，当我们写 out[S]时，隐含地认为控制流从语句的唯一出口点离开这个语句。通常方程是在基本块一级建立而不是在语句级建立。因为基本块有唯一的出口点。
３,在过程调用，通过指针赋值以及对数组变量的赋值语句中，常常会伴随一些问题，对于这些问题需进行相应的处理。
数据流问题的讨论 合流问题向前流 （ 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）形式来解决，使所需的性质在所有可能的路径都满足。对于全路径问题的解，所需的性质可以保证总是满足。
数据流问题的解不一定唯一
LiveIn(B)= LiveUse(B)∪ (LiveOut(B)- Def(B))
LiveOut(B)=∪ LiveIn(i) i∈ s(B)
若
Def(B1)=?
Def(B2)=?
Def(B3)=?
Def(B4)=?
Liveuse(B1)=?
Liveuse(B2)=?
Liveuse(B3)=?
Liveuse(B4)={a}
应用向后流方法传播可以得到一个最明显的解，即四个基本块的LiveIn集合均为 {a}
LiveIn(B1)=
LiveIn(B2)=
LiveIn(B3)=
LiveIn(B4)={a}
如下流图，没有对任何变量定值,a在 B4中被引用
:= 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集合中，
它就永远消除不了
