编译原理讲义
(第八章 代码优化 )
南京大学计算机系赵建华优化的概念
编译时刻为改进目标程序的质量而进行的各项工作。
– 空间效率
– 时间效率
空间效率和时间效率有时是一对矛盾，有时不能兼顾。
优化的要求：
– 必须是等价变换
– 为优化的努力必须是值得的。
– 有时优化后的代码的效率反而会下降。
优化的分类
机器相关性：
– 机器相关优化：寄存器优化，多处理器优化，特殊指令优化，无用指令消除等。
– 无关的优化：
优化范围：
– 局部优化：当个基本块范围内的优化，合并常量优化，消除公共子表达式，削减计算强度和删除无用代码。
– 全局优化：主要是基于循环的优化：循环不变式优化，归纳变量删除，计算强度削减。
– 优化语言级：
优化语言级：针对中间代码，针对机器语言。
代码优化程序的结构
控制流分析的主要目的是分析出程序的循环结构。循环结构中的代码的效率是整个程序的效率的关键。
数据流分析进行数据流信息的收集，主要是变量的值的获得和使用情况的数据流信息。
– 到达 -定值分析；活跃变量；可用表达式；
代码变换：根据上面的分析，对内部中间代码进行等价变换。
控制流分析 数据流分析 代码变换基本块和流图
基本块中，控制流是由第一个四元式进入，到达最后一个四元式离开。
流图：把一个程序的中间表示中所有的基本块作为节点集合。有边从节点 n到节点 n’当且仅当控制流可能从 n的最后的一个四元式到达 n’的第一个四元式。
首节点：对应的基本块的第一个四元式是程序的第一个四元式。
流图的构造
以所有的基本块为节点集合。
有 B1到 B2的边（ B2是 B1的后继）当且仅当：
– B1的最后一个四元式有条件或无条件地转移到 B2的第一个四元式。
– B2是紧紧跟随在 B1后面的四元式，且 B1的最后四元式不是无条件转向语句。
流图的例子
在转移语句中，目标标号转变称为基本块的编号，
可以避免因为四元式的变动而引起的麻烦。
= 1 _ i
= 1 _ f
= 0 _ a
>= i 10 B4
= f _ b
+ f a t1
= t1 _ f
= b _ a
+ i 1 t2
= t2 _ i
GO B2
= f fib
B1
B2
B3
B4
基本块的优化
合并常量计算
消除公共子表达式
削减计算强度
删除无用代码合并常量计算
例子,l = 2*3.14*r
– * 2 3.14 t1
– * t1 r t2
– = t2 l
2*3.1415926的值在编译时刻就可以确定。
– * 6.28 r t2
– = t2 l
消除公共子表达式
+ b c a - a d b
+ b c c - a d d
显然，第 2和 4个四元式计算的是同一个值，所以第四个四元式可以修改称为 = b _ d。
对于第 1和 3个四元式，虽然都是计算 b+c，但是他们的值其实是不同的，所以不能完成处理。
公共表达式：如果某个表达式先前已经计算，且从上次计算到现在,E中的变量的值没有改变。那么 E的这次出现称为公共子表达式。
利用先前的计算结果，可以避免对公共子表达式的重复计算。
例子
x+y*t-a*(x+y*t)/(y*t)
* y t t1 + x t1 t2
* y t t3 + x t3 t4
* a t4 t5 * y t t6
/ t5 t1 t7 - t2 t7 t8
消除公共子表达式之后：
* y t t1 + x t1 t2
* a t2 t5 / t5 t1 t7
- t2 t7 t8
削减计算强度
实现同样的运算可以有多种方式。用计算较快的运算代替较慢的运算。
X2 变成 x*x。
2*x或 2.0*x 变成 x+x
x/2 变成 x*0.5
anxn+an-1xn-1+…+a 1x+a0变成
– ((…(a nx+an-1)x+ an-2)…)x+a 1)x+a0
删除无用代码
如果四元式 op x y z之后,z的值再也没有被使用到，那么这个四元式是无用的。
无用的四元式往往意味着程序的错误，一般不会出现再正确的程序里面。
多数无用四元式是由优化引起的。
= t1 t3，如果我们尽量用 t1替代 t3，
可能使 t3不被使用，从而这个四元式称为无用的四元式。
等价变换的分类
保结构等价变换
– 删除公共子表达式和删除无用代码，重新命名临时变量和交换独立四元式的顺序等。
– + x y t变成 + x y u
– + a b t1 + x y t2变成
– + x y t2 + a b t1
代数等价变换利用了代数恒等性质，
– 削减计算强度。 2x=x+x,B and true = B.
– 需要考虑双目运算符的可交换特性。
基本块优化的实现
基本块内部优化的实现主要工具为 DAG图。
用 DAG图表示各个值的计算 /依赖关系。
图中的标记：
– 叶子节点的标记为标识符（变量名）或常数作为唯一的标记。叶子节点是标识符时，用下标 0表示它时初值。
– 内部节点用运算符号作为标记，表示计算的值。每个节点的值都可以用关于变量初始值的表达式表示。
– 各节点可能附加有一个或者多个标识符。同一个节点的标识符表示相同的值。
DAG图的例子
+ b c a
- a d b
+ b c c
- a d d
+
-
+
b0 c0
d0
b,d
a
四元式的分类
0型,= x _ y
1型,op x _ y(单目运算）
2型,op x y z
relop x y z(z是序号 )
基本块 DAG图构造算法
输入：一个基本块 输出：相应 DAG图
算法说明：
– 通过逐个扫描四元式来逐渐建立 DAG图。
– 函数 node(x)表示和标识符 x相应的最近建立的节点。他代表扫描到当前的四元式的时候，标识符 x的值对应的节点。
步骤 1：初始化：无任何节点,node对任何标识符无定义。
步骤 2：依次对基本块中的每个四元式 op x y z执行下面的步骤。
– 如果 node(x)没有定义，建立叶子节点，标记为 x，让 node(x)
等于这个节点。如果 node(y)没有定义，为 y建立节点。
– 如果四元式为 0型,n=node(x);
– 如果四元式为 1型，寻找标记为 op且子节点为 node(x)的节点，如果找不到，建立这样的节点。
基本块 DAG图构造算法（续）
– 对于 2型四元式，查看是否存在标记为 op的节点，且其左右子节点分别为 node(x)和 node(y)。如果找不到，建立这样的节点。
步骤 3：如果 z为标识符，从 node(z)中删除标识符 z，并把 z加入到步骤 4所找到或者建立的节点 n的标识符表中，并设置 node(z)
为 n。
说明：
– 处理 2型四元式的时候，如果 op是可交换的运算符，
可以其左右节点可以互换。
生成 DAG图的例子
* 4 i t1 =[] a t1 t2
* 4 i t3 =[] b t3 t4
* t2 t4 t5 + prod t5 t6
= t6 prod + i 1 t7
= t7 i <= i 20 (3)
a 4 i
*
=[] =[]
b
*
+
prod0
1
+ 20
<=
DAG图的应用
公共子表达式：构造中，寻找是否有标记为 op
且子节点为 node(x),node(y)的节点时，自然完成了公共子表达式的寻找。
在基本块中，其值被引用的标识符：构造了叶子节点的标识符。
结果能够在基本块外被引用的四元式 op x y z。
设它对应的节点为 n，如果 DAG图构造结束的时候,n的标志符表不为空。
[]=和 &=运算符的处理
对数组的赋值需要特别的处理，这是因为数组的下标是变量。
对于数组元素的赋值可能改变数组中任何一个元素的值。
=[] A i t1 []= A j t2
&= y t2 t2 =[] A i t3
A[i]并不是公共子表达式。
在处理对数组 A的元素的赋值四元式的时候，应该注销所有以
=[]为标记,A为左节点的节点。从而不可能在此节点的标识符表中再附上其他的标识符。
处理对指针所指空间的赋值的时候，同样要注销相应的节点。
如果不能确定指针指向的范围，那么，需要注销所有的节点。
A i
=[]
j
[]=t1 t2
y
&= =[]
从 DAG图到四元式序列
在 DAG图中，有些运算已经进行了合并。
如果不考虑 []=和 &=算符，可以依照 DAG图中的拓扑排序得到的次序进行。但是，有了 []=和 &=算符之后，计算的次序必须修正。
实际上，我们可以按照各个节点生成的顺序来从 DAG
图生成四元式序列。
从 DAG重建四元式序列算法
按照 DAG图中的各个节点生成的次序，对于每个节点作如下处理：
– 若是叶子节点，且附加标识符表为空，不生成四元式。
– 若是叶子节点，标记为 x，附加标识符为 z，生成 = x z。
– 若是内部节点，附加标识符为 z，根据其标记 op和子节点数目，生成下列 4种形式的四元式。
Op不是 =[]或者 []=，也不是 relop，有两个子节点，生成 op x y z
如果是 =[]或者 []=，生成 op x y z。
如果是 relop，生成 relop x y z,z是基本块序号。
只有一个子节点，生成 op x _ z。
从 DAG重建四元式序列算法 (续 )
– 若是内部节点，且无附加标识符，则添加一个局部于本基本块的临时性附加标识符，按照上一情况生成。
– 如果节点的标识符重包含多个附加标识符 z1,z2,…,zk 时：
若是叶子节点，标记为 z，生成一系列四元式
– = z z1
– = z z2
–… … …
– = z zn
不是叶子节点，生成四元式序列：
– = z z2
–… … …
– = z zn
使用 DAG图进行优化的例子
(四元式序列 )
四元式序列片断,
* 4 i t10 =[] A t10 t11
= t11 x * 4 i t12
[]= A t12 t13 * 4 j t14
=[] A t14 t15 &= t15 t13 t13
* 4 j t16 []= A t16 t17
&= x t17 t17 < i j B2
使用 DAG图进行优化的例子
(DAG图 )
在第 10个节点生成后,
node(t11)变成无定义,
1,4 2,i
3,* t10
4,A
t12
5:=[] t11 6:[]= t13
8:*
7,j
t14
9,=[] t15
10:&=
t16
11:[]= t17
12,&=
13,<
B2
x
从 DAG图到四元式序列
– *4 i t10 (3)
– =[] A t10 t11 (5)
–,= t11 x (5)
– []= A t10 t13 (6)
– * 4 j t14 (8)
– =[] A t14 t15 (9)
– &= t15 t13 t13 (10)
– []= A t14 t17 (11)
– &= x t17 t17 (12)
– < i j B2 (13)
DAG的其他应用
合并常量计算,
– * 2 pi t1
– * t1 r t2
– = t2 l
无用代码的删除,
– 对于 = t10 t12，如果 t12不需要使用，那么，这个四元式不需要生成。
*
*
2 pi r0
与循环有关的优化
循环不变表达式外提。
归纳变量删除。
计算强度削减循环不变式外提
有些表达式位于循环之内，但是该表达式的值不随着循环的重复执行而改变，
该表达式被称为循环的不变表达式。
如果按照前面讲的代码生成方案，每一次循环都讲计算一次。
如果把这个表达式提取到循环外面，该计算就只被执行一次。从而可以获得更加好的效率。
循环不变式的例子
计算半径为 r的从 10度到 360度的扇形的面积：
– for(n=1; n<36; n++)
– {S:=10/360*pi*r*r*n; printf(“Area is %f”,S); }
显然，表达式 10/360*pi*r*r中的各个量在循环过程中不改变。
可以修改程序如下：
– C= 10/360*pi*r*r*n;
– for(n=1; n<36; n++)
– {S:=C*n; printf(“Area is %f”,S); }
修改后的程序中,C的值只需要被计算一次，而原来的程序需要计算 36次。
四元式的循环不变式
= 1 n > n 36 (21)
GO (4) / 10 360 tl
* tl pi t2 * t2 r t3
* t3 r t4 * t4 n t5
= t5 S … … … …
+ n 1 t9 = t9 n
GO (4)
其中，四元式 4,5,6,7是循环不变四元式。
循环不变四元式的相对性
对于多重嵌套的循环，循环不变四元式是相对于某个循环而言的。可能对于更加外层的循环，它就不是循环不变式。
例子：
for(i = 1; i<10; i++)
for(n=1; n<360/(5*i); n++)
{S:=(5*i)/360*pi*r*r*n;...}
5*i和 (5*i)/360*pi*r*r对于 n的循环（内层循环）是不变表达式，但是对于外层循环，它们不是循环不变表达式。
循环不变表达式优化需要解决的问题
如何识别循环中的不变表达式？
把循环表达式外提到什么地方？
什么条件下，不变表达式可以外提？
归纳变量的删除（例子）
例子：
Prod=0; i = 1;
for(i = 1; i<= 20; i++)
prod += prod+A[i]*B[i];
i作为计数器。每次重复,i的值增加 1，而 A[i],
B[i]对应的地址 t1,t3增加 4。
我们可以删除 i，而使用 t1或者 t3进行循环结束条件的测试。
归纳变量的删除
在循环中，如果变量 i的值随着循环的每次重复都固定地增加或者减少某个常量，则称 i为循环的归纳变量。
如果在一个循环中有多个归纳变量，归纳变量的个数往往可以减少，甚至减少到 1个。减少归纳变量的优化称为归纳变量的删除。
归纳变量的删除（四元式例子）
= 0 prod
= l i
* 4 i t1
=[] a t1 t2
* 4 i t3
=[] b t3 t4
* t2 t4 t5
+ prod t5 t6
= t2 prod
+ i 1 t7
= t7 i
<= i 20 B2
= 0 prod
= 0 t1
* 4 i t1
=[] a t1 t2
=[] b t3 t4
* t2 t4 t5
+ prod t5 t6
= t6 prod
<= t1 80 B2
归纳变量的删除
归纳变量的删除一方面可以删除变量，
减少四元式，另外，删除归纳变量同时也削减了计算强度。
为了进行归纳变量删除优化，必要的是找出归纳变量。
计算强度削减
在删除归纳变量的过程中,已经将一些乘法运算转换称为加法运算。
还有一类经常可以被应用的是对于下标变量地址的计算。
计算强度削减（下标变量）
对于数组 T a[n1][n2]…[nm],其下标变量
a[i1][i2][i3]…[im] 的地址计算如下：
– base+d；其中 base为 a[0][0]…[0] 的地址。
– d=((…((i1*n2+i2)*n3+i3)…)*nm+im)*sizeof(T);
当满足某些情况的时候，地址的计算可以使用加法来代替乘法。
下标变量计算强度的削减（例子）
for(v1=v10; v1<v1f; v1++)
for(v2=v20; v2<v2f; v2++)
{… A[i1][i2][i3]…}
i1,i2,i3都可以表示成为：
Ck0+Ck1*V1+Ck2*V2(k=1,2,3);
A[i1][i2][i3]的地址为 base+d; d=(i1*n2*n3+i2*n3+i3);
将 i1,i2,i3的表达式代入 d的表达式，可以得到
d=C0’+C1’*V1+C2’*V2.
下标变量计算强度的削减（例子）
显然，在上面的例子中，每次内循环 d的值增加 C2’；
每次外循环,d的值增加 C1’（但是 V2被重置）。
显然我们可以这样计算 A[i1][i2][i3]的地址：
– 在循环开始的时候，设置初值 d1=(base+C0’)+C1’*V10;
– 在进入外层循环后，进入内存循环前，设置 d2=d1+C2’*V20
– 在内存循环，使用 d2作为地址获取 A[i1][i2][i3]的值。
– 内存循环体每次运行结束之前，将 d2的值增加 C2’。
– 每次外层循环体运行结束之前，将 d1的值增加 C1’。
显然，对于 A[i1][i2][i3]的地址计算变成了加法运算。
下标变量计算强度的削减结果
D1 = base+C0+C1’*V10;
for(v1=v10; v1<v1f; v1++)
{
D2 = D1+C2’*V20;
for(v2=v20; v2<v2f; v2++)
{ … *D2…;
D2+=C2’;}
D1+= C1’;
}
下标地址优化计算的条件
相应的数组是常界数组：数组的上下界都是常量。
下标变量中的下标表达式是循环控制变量的线性表达式。
满足上述条件的成为可优化下标变量。
在 C语言中，要求循环控制变量每次循环的变动是常数。
循环优化的实现
循环结构的识别
数据流分析
代码转换循环结构的识别
对于源程序来说，识别循环是比较方便的。但是代码的优化是针对四元式序列的，所以识别循环必须针对流图进行。
定义 8.3 如果流图中，从某个初始节点出发，每一条到达节点 n的路径都必须经过 m，那么称 m是节点 n的必经节点。记为 m dom n。
– 任何节点都是自己的必经节点。
– m为 n的前驱,n为 m的后继。
直接必经节点：从初始节点到达 n的所有路径上，节点
n的最后一个必经节点称为直接必经节点。
循环满足的条件
循环必须有唯一的入口节点，称为首节点。
对于循环中任何一个节点，必定至少有一个路径回到首节点。
回边和自然循环
定义 8.4 假定流图中存在两个节点 M和 N
满足 M dom N。如果存在从节点 N到 M的有向边 N->M，那么这条边称为回边。
定义 8.5 在流图中，给定一个回边 N->M，
对应与这个回边的自然循环为,M，以及所有可以不经过 M而到达 N的节点。 M
为该循环的首节点。
用节点的集合表示自然循环。
自然循环的例子
3 dom 4
回边 4->3
4 dom 7
回边 7->4
10->7的自然循环 {7，
8,10}
7-4的自然循环
{4,5,6,7,8,10}
4-3,8->3的自然循环
{3,4,5,6,7,8,10}
1
2
3
4
5 6
7
8
9 10
回边寻找算法
首先列出所有从首节点开始，不带圈的路径。
节点 N的必经节点的集合为满足一下条件的节点 M：
– 所有包含 N的路径 P,M都在 N的前面出现。
回边集合如下：
– {N-->M | N是一个节点,M在 N的必经节点集合中 }
寻找自然循环的算法
输入,回边 {N->M}; 输出,回边对应的自然循环,
算法,
设置 loop={N,M};
push(stack,N);
while non-empty(stack) do
{m = top(stack); pop(stack);
for m的每个前驱节点 p
{if p is_not_in loop then
{loop += p; push(stack,p);
}
}
算法的说明
节点 M在初始时刻已经在 loop中所以,M
的前驱不可能被加入到 loop中。
如果 N->M不是回边，那么，首节点会被加入到 loop中。此时算法不能得到自然循环。
相关概念
通常，循环互不相交，或者一个在另外一个里面。
内循环：不包含其他循环的循环称为内循环。
如果两个循环具有相同的首节点，那么很难说一个包含另外一个。此时把两个循环合并。
B0
B1
B2 B3
可归约流图
可归约流图：删除了其中回边之后，
可以构成无环有向图的流图。
– 不存在循环外向循环内部的转移，
进入循环必须通过其首节点。
实际的程序对应的流图一般都是可归约的流图。
没有 goto语句的结构化程序的流图总是可归约的。一般使用 goto语句的程序也是可归约的。
B1
B2 B3
数据流分析相关概念
变量获得值的方式：
– 通过赋值语句；
– 通过输入语句；
– 通过过程形式参数；
点：流图基本块中的位置，包括：第一个四元式之前，
两个相邻四元式之间，和最后的四元式之间。
定值：是变量 x获得值的四元式称为对 x的定值，一般用四元式的位置表示。
引用点：引用某个变量 x的四元式的位置称为 x的引用点。
数据流分析的种类
到达 -定值数据流方程
活跃变量数据流方程
可用表达式数据流方程到达 -定值数据流方程
到达 -定值：假定 x有定值 d，如果存在一个路径，从紧随 d的点到达某点 p，并且此路径上面没有被注销，则称 x的定值 d到达 p。这表明，在 p点使用变量 x的时候，
x的值可能是由 d点赋予的。
到达 -定值链：设变量 x有一个引用点 u，变量 x的所有能过到达 u的一切定值称为 x在 u点处的引用 -定值链，
简称 ud链。
显然，通过变量 x在引用点 u的 ud链，可以判断 x是否循环不变的。
到达定值数据流方程（记号）
IN[B],表示基本块 B的入口点处各个变量的定点集合。
– 如果 B中点 p之前有 x的定值点 d，且这个定值能够到达 p，则点 p处 x的 ud链是 {d}。
– 否则，点 p处 x的 ud链就是 IB[B]中关于 x的定值点的集合。
P[B],B的所有前驱基本块的集合。
GEN[B]：各个变量在 B内定值，并能够到达 B的出口点的所有定值的集合。
OUT[B]：各个变量的能够到达基本块 B的出口点的所有定值的集合。
KILL[B]：是各个变量在基本块 B中重新定值，因此才块内部被注销的定值点的集合。
到达定值数据流方程
IN[B] = U OUT[p] where p isin P[B]
OUT[B] = GEN[B] U (IN[B]-KILL[B])
其中：
– GEN[B]可以从基本块中求出：使用 DAG图就可以得到。
– KILL[B]中，对于整个流图中的所有 x的定值点，如果 B中有对 x的定值，那么该定值点在 KILL[B]中。
方程求解算法
使用迭代方法。
初始值设置为,IN[Bi]=空； OUT[B]=GEN[Bi];
change = TRUE;
while(change)
{
change = FALSE;
for each B do
{IN[B] = U OUT[p] where p isin P[B];
OUT[B] = GEN[B] U (IN[B]-KILL[B]);
oldout = OUT[B];
if(OUT[B] != oldout) change = TRUE;}
}
算法例子
GEN[B1]={d1,d2,d3}
KILL[B1]={d4,d5,d6,d7}
GEN[B2]={d4,d5}
KILL[B2]={d1,d2,d7}
GEN[B3]={d6}
KILL[B3]={d3}
GEN[B4]={d7}
KILL[B4]={d1,d4}
d1,- m 1 j
d2,= n j
d3,= u2 a
d4,+ i 1 i
d5,- j 1 j
d6,= u2 a
d7,= u3 i
B1
B2
B3
B4
计算过程
初始化：
– IN[B1] = IN[B2] = IN[B3] = IN[B4] =空
– OUT[B1]={d1,d2,d3},OUT[B2]={d4,d5}
– OUT[B3]={d6},OUT[B4]={d7}.
第一次循环：
– IN[B1]=空 ; IN[B2] ={d1,d2,d3,d7}; IN[B3]={d4,d5};
– IN[B4]={d4,d5,d6}; OUT[B1]={d1,d2,d3};
– OUT[B2]={d3,d4,d5}…
结果：
– IN[B1]=空； OUT[B1]={d1,d2,d3};
– IN[B2]={d1,d2,d3,d5,d6,d7}; OUT[B2]={d3,d4,d5,d6};
– IN[B3]={d3,d4,d5,d6}; OUT[B3]={d4,d5,d6};
– IN[B4]={d3,d4,d5,d6}; OUT[B4]={d3,d5,d6,d7};
活跃变量数据流方程
判断在基本块出口之后，变量的值是否还被引用的这种判断工作称为活跃变量分析。
消除复写四元式的依据就是对活跃变量的分析。如果某个变量的值在以后不被引用，那么该复写四元式可以被消除。
对于变量 x和流图上的某个点 p，存在一条从 p开始的路径，在此路径上在对 x定值之前引用变量 x的值，则称变量 x在点 p是活跃变量，否则称 x在点 x不活跃。
无用赋值：对于 x在点 p的定值，在所有基本块内不被引用，且在基本块出口之后又是不活跃的，那么 x在点 p的定值是无用的。
记号
L_IN[B],基本块 B的入口点的活跃变量集合。
L_OUT[B],是在基本块 B的出口点的活跃变量集合。
L_DEF[B],是在基本块 b内的定值，但是在定值前在 B中没有被引用的变量的集合。
L_USE[B],表示在基本块中引用，但是引用前在 B中没有被定值的变量集合。
其中,L_DEF[B]和 L_USE[B]是可以从基本块 B
中直接求得的量，因此在方程中作为已知量。
活跃变量数据流方程
L_IN[B] = L_USE[B] U(L_OUT[B]-L_DEF[B])
L_OUT[B] = U L_IN[s]，其中 s遍历 B的所有后继。
变量在某点活跃，表示变量在该点的值在以后会被使用。
第一个方程表示：
– 如果某个变量在 B中没有定值就使用了，显然，变量在在入口处的值会被使用。
– 如果这个变量在 B的出口处活跃，并且 B中没有对他进行定值，那么变量在入口处也是活跃的。
第二个方程表示：
– 在 B的某个后记中会使用该后继的入口处的值，那么他其实也可能使用 B的出口处的值。
活跃变量数据流方程求解
设置初值,L_IN[Bi]=空 ;
重复执行一下步骤知道 L_IN[Bi]不再改变：
for(i=1; i<n; i++)
{
L_OUT[Bi]=U L_IN[s]; s是 Bi的后继；
L_IN[Bi]=L_USE[Bi] U (L_OUT[Bi]-L_DEF[Bi]);
}
活跃变量数据流方程例子
L_DEF[B1]={i,j,a}
L_USE[B1]={m,n,
u1}
L_DEF[B2]=空
L_USE[B2]={i,j}
L_DEF[B3]={a}
L_USE[B3]={u2}
L_DEF[B4]={i}
L_USE[B4]={u3}
d1,- m 1 j
d2,= n j
d3,= u2 a
d4,+ i 1 i
d5,- j 1 j
d6,= u2 a
d7,= u3 i
迭代过程
第一次循环：
– L_OUT[B1]=空 L_IN[B1]={m,n,u1}
– L_OUT[B2]=空 L_IN[B2]={i,j}
– L_OUT[B3]={i,j} L_IN[B3]={i,j,u2}
– L_OUT[B4]={i,j,u2} L_IN[B4]={j,u2,u3}
第二次循环：
– L_OUT[B1]={i,j,u2,u3} L_IN[B1]={m,n,u1,u2,u3}
– L_OUT[B2]={i,j,u2,u3} L_IN[B2]={i,j,u2,u3}
– L_OUT[B3]={i,j,u2,u3} L_IN[B3]={i,j,u2,u3}
– L_OUT[B4]={i,j,u2,u3} L_IN[B4]={j,u2,u3}
第三次循环各个值不再改变，完成求解。
可用表达式数据流方程
如果一个流图的首节点到达点 p的每个路径上面都有对
x op y的计算，并且在最后一个这样的计算到点 p之间某有对 x,y进行定值，那么表达式 x op y在点 p是可用的。
表达式可用的直观意义：在点 p上,x op y已经在之前被计算过，不需要重新计算。
注意：如果对于有间接赋值四元式的情况，需要保证最后的计算 x op y的点之间不会间接改变 x,或者 y的值：
比如指针不会指向 x或者 y的存储区域，特别是当 x为某个数组的时候。
书上的讲解是针对没有间接赋值四元式的情况处理的。
概念
对表达式的注销：如果某个基本块 B对 x或者 y
定值，且以后没有重新计算 x op y，那么称 B注销表达式 x op y。
表达式的产生：如果某个基本块 B对 x op y进行计算，而以后并没有在对 x或者 y重新定值，那么称 B产生表达式 x op y。
表达式的全集：在计算某个流图中的可用表达式的时候，表达式的讨论范围被限定在该出现在流图中的四元式对应的表达式。
记号
E_OUT[B]：在基本块出口处的可用表达式集合。
E_IN[B]：在基本块入口处的可用表达式集合。
E_GEN[B]：基本块 B所产生的可用表达式的集合。
E_KILL[B]：基本块 B所注销掉的可用表达式的集合。
E_GEN[B]和 E_KILL[B]的值可以直接从流图计算出来。因此在数据流方程中，可以将 E_GEN[B]和
E_KILL[B]当作已知量看待。
E_GEN[B]的计算
对于一个基本块 B,E_GEN[B]的计算过程如下：
初始设置,E_GEN[B]=空；
顺序扫描每个四元式：
– 对于四元式 op x y z，把 x op y加入 E_GEN[B]，
– 从 E_GEN[B]中删除和 z相关的表达式。
最后的 E_GEN[B]就是相应的集合。
E_KILL[B]的计算
设流图的表达式全集为 E;
初始设置,EK = 空；
顺序扫描基本块的每个四元式：
– 对于四元式 op x y z，把表达式 x op y从 EK中消除；
– 把 E中所有和 z相关的四元式加入到 EK中。
扫描完所有的四元式之后,EK就是所求的
E_KILL[B]。
数据流方程
1,E_OUT[B] = (E_IN[B]-E_KILL[B]) U
E_GEN[B]
2,E_IN[B]= ∩E_OUT[p] B!=B1,p是 B的前驱。
3,E_IN[B1]=空集
说明：
– 在程序开始的时候，无可用表达式。 (3)
– 一个表达式在某个基本块的入口点可用，
必须要求它在所有前驱的出口点也可用。
（ 2）
– 一个表达式在某个基本块的出口点可用，
或者该表达式是由它的产生的；或者该表达式在入口点可用，且没有被注销掉。
（ 1）
B
p2p1 p3
IN
OUT
GEN -KILL
方程求解算法
迭代算法
初始化,E_IN[B1]=空 ;
E_OUT[B1]=E_GEN[B1];E_OUT[BI]=U-
E_KILL[Bi](i>=2)
重复执行下列算法直到 E_OUT稳定,
FOR（ i=2; i<=n ;i++)
{
E_IN[Bi]= ∩E_OUT[p],p是 Bi的前驱；
E_OUT[Bi]=E_GEN[Bi] ∪ (E_IN[Bi]-E_KILL[Bi]);
}
算法说明
初始化值和前面的两个算法不同。
E_OUT[Bi]的初值大于实际的值。
在迭代的过程种,E_OUT[Bi]的值逐渐缩小直到稳定。
U表示四元式的全集，就是四元式序列中所有表达式 x op y的集合。
寻找循环不变表达式算法
输入：循环 L，已经建立的 UD链
输出：不变四元式
步骤 1：如果四元式的运算分量或者是常数，或者其所有定值点在循环外部。
步骤 2：重复执行下面的步骤：
– 如果一个四元式没有被加过标记，且孙算分量要么是常数，要么其 UD链中的定值点在循环外，或者该定值点已经被加过标记。
说明：一个四元式的是不变的，当且仅当其分量在循环中是不变的。主要有三种情况：常量，定值点在循环外部，或者定值点的四元式也是不变的。
不变四元式外提方法
对于不变四元式，可以在进入循环之前首先计算该四元式的值，
然后在循环内部使用该值。
可以将四元式的值外体到紧靠循环之前。
首节点首节点前置节点代码外提不合法的情况（ 1）
= 1 i
< u v B3
= 2 i
+ u 1 u
- v 1 v
<= v 20 B5
= i j
= 1 i
< u v B3
+ u 1 u
- v 1 v
<= v 20 B5
= i j
= 2 i
代码外提不合法的情况（ 2）
= 1 i
= 3 i
< u v B3
= 2 i
+ u 1 u
- v 1 v
<= v 20 B5
= i j
= 1 i
= 3 i
< u v B3
= 2 i
+ u 1 u
- v 1 v
<= v 20 B5
= i j
代码外提不合法的情况（ 3）
= 1 i
= 0 k
< u v B3
= i k
+ u 1 u
= 2 i
- v 1 v
<= v 20 B5
= i j
= 1 i
= 0 k
= 2 i
< u v B3
= i k
+ u 1 u
- v 1 v
<= v 20 B5
= i j
不变四元式外提的条件
不变四元式 op x y z可以外提的条件：
– Q坐在的基本块节点是循环所有出口节点的必经节点。出口节点是指有后继节点在循环外的节点。（反例：情况 1）
– 循环中 z没有其他的定值点。（反例：情况 2）
– 循环中 z的引用点仅由 Q到达。（反例：情况 3）
外提算法
步骤 1：寻找一切不变四元式。
步骤 2：对于找到的每个循环，检查是否满足上面说的三个条件。
步骤 3：按照不变四元式找出的次序，把所找到的满足上述条件的四元式外提到前置节点中。
– 如果四元式有分量在循环中定值，只有将定值点外提后，该四元式才可以外提。
循环不变式外提的例子
= 1 i
= 0 k
1) + i 1 k
2) * 2 k t
< u v B3
+ u 1 u
- v 1 v
<= v 20 B5
= i j
= 1 i
= 0 k
< u v B3
+ u 1 u
- v 1 v
<= v 20 B5
= i j
1)+ i 1 k
2)* 2 k t
关于归纳变量的优化
基本归纳变量：如果循环中，对于 i的定值只有形状如 i = i + c的定值，那么 I称为循环的基本归纳变量。
归纳变量族：如果循环中对变量 j的定值都是形状如 j=C1*i+C2，且 i为基本归纳变量，那么称 j
为归纳变量，且属于 i族。 i属于 i族。
对于定值为 C1*i+C2的 I族归纳变量 j，我们用
(i,C1,C2)来表示。
对于 i族的归纳变量 (i,C1,C2)，要求循环内部对此变量进行定值的时候，一定是赋给 C1*i+C2。
例子（源程序）
for(i = 0; i<100; i++)
{
j = 4*i;
printf(“%i”,j);
}
i是基本归纳变量。 j是 i族归纳变量，可以表示为 (i,
4,0)。
寻找循环的归纳变量算法
步骤 1：扫描循环的四元式，找出所有基本归纳变量。对应于每个基本归纳变量的三元组如 (i,1,0)。
步骤 2：寻找循环中只有一个赋值的变量 k，且对它的定值为如下形式,k=j*b,k=b*j,k=j/b,k=j+(-)b,k=b+(-)j。其中 j
为基本归纳变量，或者已经找到的归纳变量。
– 如果 j为基本归纳变量，那么 k属于 j族。 k对应的三元式可以确定。
– 如果 j不是基本归纳变量，且属于 i族，那么我们还要求：
循环中对 j的赋值以及和对 k的赋值之间没有对 i的赋值，且
没有 j在循环外的定值可以到达 k的这个定值点。
j的三元式可以相应确定。
算法说明
关于 j不是基本归纳变量的时候，算法中的两个要求实际上是保证：对 k进行赋值的时候,j变量当时的值一定等于 C1*（ i
当时的值） +C2。
归纳变量的计算强度削减算法
对于每个基本归纳变量 i，对其族中的每个归纳变量 j(i,c,d)执行下列步骤：
– 建立新的临时变量 t。
– 用 = t j四元式代替对 j的赋值。
– 对于每个定值 i=i+n之后，添加 t=t+c*n。
– 在前值节点的末尾，添加四元式 * c i t和 +
t d t。使得在循环开始的时候,t=c*i+t。
当两个归纳变量具有同样的三元式的时候，
可以只建立一个临时变量。
算法的说明
在优化过程中，为 j(i,c,d)引入的变量 t保证了在任何时刻 (不包括在对 i新定值后并且在 t重新定值前，但是由于两者的四元式时紧连的）都满足 t=c*i+d。
如果在某些情况下，程序运行时对 j的定值的次数远远少于对 i的定值，经过优化的程序需要对 t多次赋值，实际的效率可能降低。
归纳变量的删除
有些归纳变量的作用就是控制循环的次数。如果循环出口处的判断可以使用其它的变量代替，那么可以删除这些归纳变量。
归纳变量的删除算法
步骤 1：对于每个基本归纳变量，取 i族的某个归纳变量 j（尽量使得 c,d简单）。把每个对 i的测试修改称为用 j代替。
– relop i x B修改为 relop i c*x+d B。
– relop i1 i2 B，如果能够找到三元组 (i1,c,d)和 (i2,c,d)，那么可以将其修改为 relop j1 j2 B(假设 c>0)。
– 如果归纳变量不再被引用，那么可以删除和它相关的四元式。
– 如果基本归纳变量在循环出口处活跃，上面的算法不可以直接使用。
步骤 2：考虑对 j的赋值 = t j。如果每次对 j引用和这个赋值四元式之间没有任何对 t的赋值（此时，每次使用 j的时候都有 t=j)，
可以在引用 j的地方用 t代替，同时删除四元式 = t j（如果 j在循环的出口处活跃，需要增加 = t j）。
全局公共子表达式消除
对于循环中某个四元式 op x y z，如果在所有到达这个四元式的路径上，已经计算了 x op y，且计算之后 x,y的值再没有修改过，那么显然我们可以使用以前计算得到的值。
可用表达式表达的就是这个概念。
如果有四元式 op x y z，且在四元式前，表达式 x op
y可用，那么我们可以用下面的方法优化：在前面不同的地方计算 x op y时，把值记录到同一个临时变量 u里面。把这个四元式改变为 = u z。
全局公共子表达式消除
对于四元式 Q(op x y z)，如果 x op y再 Q之前可用，那么执行如下步骤：
– 从 Q开始逆向寻找，找到所有离 Q最近的计算了 x op y四元式。
– 建立新的临时变量 u。
– 把步骤 1中找到的四元式 op x y t用下列四元式代替,op x y u和 = u t。
– 用 = u t替代 Q。
全局公共子表达式消除 (图示 )
… …
* x y t
… …
… …
* x y k
… …
… …
* x y l
… …
… …
* x y u
= u k
… …
… …
= u l
… …
… …
* x y u
= u t
… …
复写四元式的消除
中间代码的生成可能产生四元式。
消除公共子表达式和删除归纳变量的时候，也会产生复写四元式。
通过复写四元式传播的变量大多数是临时变量。而对临时变量可以使用复写传播来消除复写四元式。
原理,= x y的效果是 x和 y的值相等。如果某个引用 y的四元式运行的时候,x和 y的值一定相等。那么我们可以使用对 y的引用来替代对 x的引用。这样做有时可以消除复写四元式 = x y。
消除复写四元式的条件
对于复写四元式 d,= x y，如果对 y对应于 d点的一切引用点 u满足下列条件，
那么我们可以删除 d，并且在这些引用点上用对 x的引用代替对 y的引用。
– 此定值点是 d到达 u的唯一的 y的定值。
– 从 d到达 u的路径（可以包含圈和多个 u，但是不包含多个 d）上，没有对 x的定值。
这两个条件实际上是说，当程序运行到达 u点的时候,x和 y的值总是相等。
记号
C_GEN[B]：在基本块 B中的所有复写四元式 = x y，
并且从该四元式开始到 B的出口,x和 y都没有在定值。
C_KILL[B]：包含了所有在流图中出现并且满足下列条件的复写四元式 = x y,B中存在对 x或者 y的定值，并且之后在没有复写四元式 = x y出现。
C_IN[B]：表示在 B的入口点，有效的复写四元式 = x
y的集合，也就是到达入口的路径上都要经过 = x
y并且之后没有对 x或者 y定值。
C_OUT[B]：表示在 B的出口点有效的复写四元式的集合。
数据流方程
C_OUT[B] = C_GEN[B] ∪ (C_IN[B]-
C_KILL[B])
C_IN[B] = ∩E_OUT[p]；其中 B不等于 B1,p
是 B的前驱。
C_IN[B1] = 空集。
其中 C_GEN[B]和 C_IN[B]可以直接从流图得到，所以在方程中作为已知量处理。
求解方法和可用表达式的求解相同。
复写传播算法
对于每个复写四元式 d,= x y执行下列步骤。
– 找出该 y定值所能够到达的那些对 y的引用。
– 对于每个这样的 y，确定 d是否在 C_IN[B]中，
B使包含这个引用的基本块，而且 B中该引用的前面没有 x或者 y的定值。
– 如果 d满足条件 (2)，删除 d，且把步骤 1中找到的的对 y的引用用 x代替。
复写传播算法的例子
= x y
* y 2 t
= x y
* y 3 t2
+ x 1 y
循环优化的例子 (原始流图）
B2
- m 1 t1
= t1 i
= n j
* 4 n t2
=[] A t2 t3
= t3 v
+ i 1 t4
= t4 i
* 4 i t5
=[] A t5 t6
< t9 v B3
- j 1 t7
= t7 j
* 4 j t8
=[] A t8 t9
> t9 v B3
>= i j B6
* 4 i t10
=[] A t10 t11
= t11 x
* 4 i t12
[]= A t12 t13
… … … …
< i j B2
* 4 i t18
=[] A t18 t19
= t19 x
* 4 i t20
[]= A t20 t21
* 4 n t22
=[] A t22 t23
&= t23 t21 t21
* 4 n t24
[]= A t24 t25
&= x t25 t25
B1 B3
B4
B5
B6
B7
寻找回边以及自然循环
回边有,B2?B2,B3?B3,B6?B2。
B2?B2对应的循环是 {B2}
B3?B3对应的循环是 {B3}
B6?B2对应的循环是 {B2,B3,B4,B5,B6}
删除回边之后，得到的图是无回路的，
所以这个流图是可归纳流图。
寻找公共子表达式
4*i：在 B5,B7入口处可用 (U1)。
A[4*i]：在 B5,B7的入口处可用 (U2)。
4*j：在 B5的入口处可用 (U3)。
A[4*j]：在 B5的入口处可用 (U4)。
4*n：在 B7的入口处可用 (U5)。
A[4*n]：在 B7的入口处可用 (U6)。
公共子表达式的优化
- m 1 t1
= t1 i
= n j
* 4 n u5
= u5 t2
=[] A t2 u6
= u6 t3
= t3 v
+ i 1 t4
= t4 i
* 4 i u1
= u1 t5
=[] A t5 u2
= u2 t6
< t9 v B3
- j 1 t7
= t7 j
* 4 j u3
= u3 t8
=[] A t8 u4
= u4 t9
> t9 v B3
>= i j B6
= u1 t10
= u2 t11
= t11 x
* 4 i t12
[]= A t12 t13
… … … …
< i j B2
= u1 t18
= u2 t19
= t19 x
= u1 t20
[]= A t20 t21
= u5 t22
= u6 t23
&= t23 t21 t21
= u5 t24
[]= A t24 t25
&= x t25 t25
B1 B3
B4
B5
B6
B7
寻找归纳变量
基本归纳变量有 i,j。
归纳变量有：
– u1,i族,(i,4,0)
– u2,j族,(j,4,0)
如果分析得更加深入，会发现 []= 四元式得到的地址也是归纳变量。但是，由于我们不考虑对间接赋值的优化，同时地址的处理也不在范围之内，所以我们没有类出。
归纳变量的优化- m 1 t1
= t1 i
= n j
* 4 n u5
= u5 t2
=[] A t2 u6
= u6 t3
= t3 v
* 4 i u1
* 4 j u3
+ i 1 t4
= t4 i
+ u1 4 u1
=[] A u1 u2
= u2 t6
< t9 v B3
- j 1 t7
= t7 j
- u3 4 u3
=[] A u3 u4
= u4 t9
> t9 v B3
>= u1 u3 B6
= u2 t11
= t11 x
= u1 t12
[]= A t12 t13
… … … …
< u1 u3 B2
= u2 t19
= t19 x
= u1 t20
[]= A t20 t21
= u5 t22
= u6 t23
&= t23 t21 t21
= u5 t24
[]= A t24 t25
&= x t25 t25
B1 B3
B4
B5
B6
B7
优化结果- m 1 t1
= t1 i
= n j
* 4 n u5
= u5 t2
=[] A t2 u6
= u6 t3
= t3 v
* 4 i u1
* 4 j u3
+ u1 4 u1
=[] A u1 u2
= u2 t6
< t9 v B3
- u3 4 u3
=[] A u3 u4
= u4 t9
> t9 v B3
>= u1 u3 B6
= u2 t11
= t11 x
= u1 t12
[]= A t12 t13
… … … …
< u1 u3 B2
= u2 t19
= t19 x
= u1 t20
[]= A t20 t21
= u5 t22
= u6 t23
&= t23 t21 t21
= u5 t24
[]= A t24 t25
&= x t25 t25
B1 B3
B4
B5
B6
B7
窥孔优化
是指对代码局部进行改进的简单有效的技术。只考虑目标代码中的指令序列，
把可能的指令序列替换成为更短更快的指令。
– 冗余指令删除。
– 控制流优化
– 代数化简
– 特殊指令使用冗余指令删除
多余存取指令的删除：
– MOV b R0
– ADD c R0
– MOV R0 a
– MOV a R0
– SUB d R0
– MOV R0 c
第四条指令没有任何效果，可以删除。
如果有标号转向第四条指令，则不可以删除。
冗余指令删除
死代码删除：
– 将不会被执行的代码删除。
– 如果目标代码中有无条件转移指令，且其后的指令标号，那么后面的指令可以删除。
产生死代码的原因可以是调试信息，或者优化的结果。
对于条件转移指令，如果其条件永远成立或者永远不成立，可以转换成为等价的无条件转移指令。
控制流优化
在代码中出现转移指令到转移指令的情况时，
某些条件下可以使用一个转移指令来代替。
转移到转移
– GOTO L1;
– … …
– L1,GOTO L2;
显然第一个转移指令可以替代为 GOTO L2.
如果在没有其他的指令转移到 L1，那么第二个指令可以被删除。
控制流优化（续）
转移到条件转移：
– L0,GOTO L1 … …
– L1,IF b THEN GOTO L2;
– L3,… …
如果只有一个转移指令到达 L1，且 L1前面是无条件转移指令，那么可以修改成为：
– IF b THEN GOTO L2;
– GOTO L3
– L3,… …
控制流优化（续）
条件转移到转移
IF b THEN GOTO L1
… …
GOTO L3
可以被修改为
IF b THEN GOTO L3
… …
GOTO L3
代数化简
利用代数规则来优化代码。
例如：
–利用 x=x+0和 x=x*1来删除相应的指令。
–利用 x2=x*x来削减计算强度。
特殊指令的使用
充分利用目标系统的某些高效的特殊指令来提高代码效率。
这些指令只可以在某些情况下使用。而识别这样的情况是优化的基础。
例如,INC指令可以用来替代加 1的操作。
(第八章 代码优化 )
南京大学计算机系赵建华优化的概念
编译时刻为改进目标程序的质量而进行的各项工作。
– 空间效率
– 时间效率
空间效率和时间效率有时是一对矛盾，有时不能兼顾。
优化的要求：
– 必须是等价变换
– 为优化的努力必须是值得的。
– 有时优化后的代码的效率反而会下降。
优化的分类
机器相关性：
– 机器相关优化：寄存器优化，多处理器优化，特殊指令优化，无用指令消除等。
– 无关的优化：
优化范围：
– 局部优化：当个基本块范围内的优化，合并常量优化，消除公共子表达式，削减计算强度和删除无用代码。
– 全局优化：主要是基于循环的优化：循环不变式优化，归纳变量删除，计算强度削减。
– 优化语言级：
优化语言级：针对中间代码，针对机器语言。
代码优化程序的结构
控制流分析的主要目的是分析出程序的循环结构。循环结构中的代码的效率是整个程序的效率的关键。
数据流分析进行数据流信息的收集，主要是变量的值的获得和使用情况的数据流信息。
– 到达 -定值分析；活跃变量；可用表达式；
代码变换：根据上面的分析，对内部中间代码进行等价变换。
控制流分析 数据流分析 代码变换基本块和流图
基本块中，控制流是由第一个四元式进入，到达最后一个四元式离开。
流图：把一个程序的中间表示中所有的基本块作为节点集合。有边从节点 n到节点 n’当且仅当控制流可能从 n的最后的一个四元式到达 n’的第一个四元式。
首节点：对应的基本块的第一个四元式是程序的第一个四元式。
流图的构造
以所有的基本块为节点集合。
有 B1到 B2的边（ B2是 B1的后继）当且仅当：
– B1的最后一个四元式有条件或无条件地转移到 B2的第一个四元式。
– B2是紧紧跟随在 B1后面的四元式，且 B1的最后四元式不是无条件转向语句。
流图的例子
在转移语句中，目标标号转变称为基本块的编号，
可以避免因为四元式的变动而引起的麻烦。
= 1 _ i
= 1 _ f
= 0 _ a
>= i 10 B4
= f _ b
+ f a t1
= t1 _ f
= b _ a
+ i 1 t2
= t2 _ i
GO B2
= f fib
B1
B2
B3
B4
基本块的优化
合并常量计算
消除公共子表达式
削减计算强度
删除无用代码合并常量计算
例子,l = 2*3.14*r
– * 2 3.14 t1
– * t1 r t2
– = t2 l
2*3.1415926的值在编译时刻就可以确定。
– * 6.28 r t2
– = t2 l
消除公共子表达式
+ b c a - a d b
+ b c c - a d d
显然，第 2和 4个四元式计算的是同一个值，所以第四个四元式可以修改称为 = b _ d。
对于第 1和 3个四元式，虽然都是计算 b+c，但是他们的值其实是不同的，所以不能完成处理。
公共表达式：如果某个表达式先前已经计算，且从上次计算到现在,E中的变量的值没有改变。那么 E的这次出现称为公共子表达式。
利用先前的计算结果，可以避免对公共子表达式的重复计算。
例子
x+y*t-a*(x+y*t)/(y*t)
* y t t1 + x t1 t2
* y t t3 + x t3 t4
* a t4 t5 * y t t6
/ t5 t1 t7 - t2 t7 t8
消除公共子表达式之后：
* y t t1 + x t1 t2
* a t2 t5 / t5 t1 t7
- t2 t7 t8
削减计算强度
实现同样的运算可以有多种方式。用计算较快的运算代替较慢的运算。
X2 变成 x*x。
2*x或 2.0*x 变成 x+x
x/2 变成 x*0.5
anxn+an-1xn-1+…+a 1x+a0变成
– ((…(a nx+an-1)x+ an-2)…)x+a 1)x+a0
删除无用代码
如果四元式 op x y z之后,z的值再也没有被使用到，那么这个四元式是无用的。
无用的四元式往往意味着程序的错误，一般不会出现再正确的程序里面。
多数无用四元式是由优化引起的。
= t1 t3，如果我们尽量用 t1替代 t3，
可能使 t3不被使用，从而这个四元式称为无用的四元式。
等价变换的分类
保结构等价变换
– 删除公共子表达式和删除无用代码，重新命名临时变量和交换独立四元式的顺序等。
– + x y t变成 + x y u
– + a b t1 + x y t2变成
– + x y t2 + a b t1
代数等价变换利用了代数恒等性质，
– 削减计算强度。 2x=x+x,B and true = B.
– 需要考虑双目运算符的可交换特性。
基本块优化的实现
基本块内部优化的实现主要工具为 DAG图。
用 DAG图表示各个值的计算 /依赖关系。
图中的标记：
– 叶子节点的标记为标识符（变量名）或常数作为唯一的标记。叶子节点是标识符时，用下标 0表示它时初值。
– 内部节点用运算符号作为标记，表示计算的值。每个节点的值都可以用关于变量初始值的表达式表示。
– 各节点可能附加有一个或者多个标识符。同一个节点的标识符表示相同的值。
DAG图的例子
+ b c a
- a d b
+ b c c
- a d d
+
-
+
b0 c0
d0
b,d
a
四元式的分类
0型,= x _ y
1型,op x _ y(单目运算）
2型,op x y z
relop x y z(z是序号 )
基本块 DAG图构造算法
输入：一个基本块 输出：相应 DAG图
算法说明：
– 通过逐个扫描四元式来逐渐建立 DAG图。
– 函数 node(x)表示和标识符 x相应的最近建立的节点。他代表扫描到当前的四元式的时候，标识符 x的值对应的节点。
步骤 1：初始化：无任何节点,node对任何标识符无定义。
步骤 2：依次对基本块中的每个四元式 op x y z执行下面的步骤。
– 如果 node(x)没有定义，建立叶子节点，标记为 x，让 node(x)
等于这个节点。如果 node(y)没有定义，为 y建立节点。
– 如果四元式为 0型,n=node(x);
– 如果四元式为 1型，寻找标记为 op且子节点为 node(x)的节点，如果找不到，建立这样的节点。
基本块 DAG图构造算法（续）
– 对于 2型四元式，查看是否存在标记为 op的节点，且其左右子节点分别为 node(x)和 node(y)。如果找不到，建立这样的节点。
步骤 3：如果 z为标识符，从 node(z)中删除标识符 z，并把 z加入到步骤 4所找到或者建立的节点 n的标识符表中，并设置 node(z)
为 n。
说明：
– 处理 2型四元式的时候，如果 op是可交换的运算符，
可以其左右节点可以互换。
生成 DAG图的例子
* 4 i t1 =[] a t1 t2
* 4 i t3 =[] b t3 t4
* t2 t4 t5 + prod t5 t6
= t6 prod + i 1 t7
= t7 i <= i 20 (3)
a 4 i
*
=[] =[]
b
*
+
prod0
1
+ 20
<=
DAG图的应用
公共子表达式：构造中，寻找是否有标记为 op
且子节点为 node(x),node(y)的节点时，自然完成了公共子表达式的寻找。
在基本块中，其值被引用的标识符：构造了叶子节点的标识符。
结果能够在基本块外被引用的四元式 op x y z。
设它对应的节点为 n，如果 DAG图构造结束的时候,n的标志符表不为空。
[]=和 &=运算符的处理
对数组的赋值需要特别的处理，这是因为数组的下标是变量。
对于数组元素的赋值可能改变数组中任何一个元素的值。
=[] A i t1 []= A j t2
&= y t2 t2 =[] A i t3
A[i]并不是公共子表达式。
在处理对数组 A的元素的赋值四元式的时候，应该注销所有以
=[]为标记,A为左节点的节点。从而不可能在此节点的标识符表中再附上其他的标识符。
处理对指针所指空间的赋值的时候，同样要注销相应的节点。
如果不能确定指针指向的范围，那么，需要注销所有的节点。
A i
=[]
j
[]=t1 t2
y
&= =[]
从 DAG图到四元式序列
在 DAG图中，有些运算已经进行了合并。
如果不考虑 []=和 &=算符，可以依照 DAG图中的拓扑排序得到的次序进行。但是，有了 []=和 &=算符之后，计算的次序必须修正。
实际上，我们可以按照各个节点生成的顺序来从 DAG
图生成四元式序列。
从 DAG重建四元式序列算法
按照 DAG图中的各个节点生成的次序，对于每个节点作如下处理：
– 若是叶子节点，且附加标识符表为空，不生成四元式。
– 若是叶子节点，标记为 x，附加标识符为 z，生成 = x z。
– 若是内部节点，附加标识符为 z，根据其标记 op和子节点数目，生成下列 4种形式的四元式。
Op不是 =[]或者 []=，也不是 relop，有两个子节点，生成 op x y z
如果是 =[]或者 []=，生成 op x y z。
如果是 relop，生成 relop x y z,z是基本块序号。
只有一个子节点，生成 op x _ z。
从 DAG重建四元式序列算法 (续 )
– 若是内部节点，且无附加标识符，则添加一个局部于本基本块的临时性附加标识符，按照上一情况生成。
– 如果节点的标识符重包含多个附加标识符 z1,z2,…,zk 时：
若是叶子节点，标记为 z，生成一系列四元式
– = z z1
– = z z2
–… … …
– = z zn
不是叶子节点，生成四元式序列：
– = z z2
–… … …
– = z zn
使用 DAG图进行优化的例子
(四元式序列 )
四元式序列片断,
* 4 i t10 =[] A t10 t11
= t11 x * 4 i t12
[]= A t12 t13 * 4 j t14
=[] A t14 t15 &= t15 t13 t13
* 4 j t16 []= A t16 t17
&= x t17 t17 < i j B2
使用 DAG图进行优化的例子
(DAG图 )
在第 10个节点生成后,
node(t11)变成无定义,
1,4 2,i
3,* t10
4,A
t12
5:=[] t11 6:[]= t13
8:*
7,j
t14
9,=[] t15
10:&=
t16
11:[]= t17
12,&=
13,<
B2
x
从 DAG图到四元式序列
– *4 i t10 (3)
– =[] A t10 t11 (5)
–,= t11 x (5)
– []= A t10 t13 (6)
– * 4 j t14 (8)
– =[] A t14 t15 (9)
– &= t15 t13 t13 (10)
– []= A t14 t17 (11)
– &= x t17 t17 (12)
– < i j B2 (13)
DAG的其他应用
合并常量计算,
– * 2 pi t1
– * t1 r t2
– = t2 l
无用代码的删除,
– 对于 = t10 t12，如果 t12不需要使用，那么，这个四元式不需要生成。
*
*
2 pi r0
与循环有关的优化
循环不变表达式外提。
归纳变量删除。
计算强度削减循环不变式外提
有些表达式位于循环之内，但是该表达式的值不随着循环的重复执行而改变，
该表达式被称为循环的不变表达式。
如果按照前面讲的代码生成方案，每一次循环都讲计算一次。
如果把这个表达式提取到循环外面，该计算就只被执行一次。从而可以获得更加好的效率。
循环不变式的例子
计算半径为 r的从 10度到 360度的扇形的面积：
– for(n=1; n<36; n++)
– {S:=10/360*pi*r*r*n; printf(“Area is %f”,S); }
显然，表达式 10/360*pi*r*r中的各个量在循环过程中不改变。
可以修改程序如下：
– C= 10/360*pi*r*r*n;
– for(n=1; n<36; n++)
– {S:=C*n; printf(“Area is %f”,S); }
修改后的程序中,C的值只需要被计算一次，而原来的程序需要计算 36次。
四元式的循环不变式
= 1 n > n 36 (21)
GO (4) / 10 360 tl
* tl pi t2 * t2 r t3
* t3 r t4 * t4 n t5
= t5 S … … … …
+ n 1 t9 = t9 n
GO (4)
其中，四元式 4,5,6,7是循环不变四元式。
循环不变四元式的相对性
对于多重嵌套的循环，循环不变四元式是相对于某个循环而言的。可能对于更加外层的循环，它就不是循环不变式。
例子：
for(i = 1; i<10; i++)
for(n=1; n<360/(5*i); n++)
{S:=(5*i)/360*pi*r*r*n;...}
5*i和 (5*i)/360*pi*r*r对于 n的循环（内层循环）是不变表达式，但是对于外层循环，它们不是循环不变表达式。
循环不变表达式优化需要解决的问题
如何识别循环中的不变表达式？
把循环表达式外提到什么地方？
什么条件下，不变表达式可以外提？
归纳变量的删除（例子）
例子：
Prod=0; i = 1;
for(i = 1; i<= 20; i++)
prod += prod+A[i]*B[i];
i作为计数器。每次重复,i的值增加 1，而 A[i],
B[i]对应的地址 t1,t3增加 4。
我们可以删除 i，而使用 t1或者 t3进行循环结束条件的测试。
归纳变量的删除
在循环中，如果变量 i的值随着循环的每次重复都固定地增加或者减少某个常量，则称 i为循环的归纳变量。
如果在一个循环中有多个归纳变量，归纳变量的个数往往可以减少，甚至减少到 1个。减少归纳变量的优化称为归纳变量的删除。
归纳变量的删除（四元式例子）
= 0 prod
= l i
* 4 i t1
=[] a t1 t2
* 4 i t3
=[] b t3 t4
* t2 t4 t5
+ prod t5 t6
= t2 prod
+ i 1 t7
= t7 i
<= i 20 B2
= 0 prod
= 0 t1
* 4 i t1
=[] a t1 t2
=[] b t3 t4
* t2 t4 t5
+ prod t5 t6
= t6 prod
<= t1 80 B2
归纳变量的删除
归纳变量的删除一方面可以删除变量，
减少四元式，另外，删除归纳变量同时也削减了计算强度。
为了进行归纳变量删除优化，必要的是找出归纳变量。
计算强度削减
在删除归纳变量的过程中,已经将一些乘法运算转换称为加法运算。
还有一类经常可以被应用的是对于下标变量地址的计算。
计算强度削减（下标变量）
对于数组 T a[n1][n2]…[nm],其下标变量
a[i1][i2][i3]…[im] 的地址计算如下：
– base+d；其中 base为 a[0][0]…[0] 的地址。
– d=((…((i1*n2+i2)*n3+i3)…)*nm+im)*sizeof(T);
当满足某些情况的时候，地址的计算可以使用加法来代替乘法。
下标变量计算强度的削减（例子）
for(v1=v10; v1<v1f; v1++)
for(v2=v20; v2<v2f; v2++)
{… A[i1][i2][i3]…}
i1,i2,i3都可以表示成为：
Ck0+Ck1*V1+Ck2*V2(k=1,2,3);
A[i1][i2][i3]的地址为 base+d; d=(i1*n2*n3+i2*n3+i3);
将 i1,i2,i3的表达式代入 d的表达式，可以得到
d=C0’+C1’*V1+C2’*V2.
下标变量计算强度的削减（例子）
显然，在上面的例子中，每次内循环 d的值增加 C2’；
每次外循环,d的值增加 C1’（但是 V2被重置）。
显然我们可以这样计算 A[i1][i2][i3]的地址：
– 在循环开始的时候，设置初值 d1=(base+C0’)+C1’*V10;
– 在进入外层循环后，进入内存循环前，设置 d2=d1+C2’*V20
– 在内存循环，使用 d2作为地址获取 A[i1][i2][i3]的值。
– 内存循环体每次运行结束之前，将 d2的值增加 C2’。
– 每次外层循环体运行结束之前，将 d1的值增加 C1’。
显然，对于 A[i1][i2][i3]的地址计算变成了加法运算。
下标变量计算强度的削减结果
D1 = base+C0+C1’*V10;
for(v1=v10; v1<v1f; v1++)
{
D2 = D1+C2’*V20;
for(v2=v20; v2<v2f; v2++)
{ … *D2…;
D2+=C2’;}
D1+= C1’;
}
下标地址优化计算的条件
相应的数组是常界数组：数组的上下界都是常量。
下标变量中的下标表达式是循环控制变量的线性表达式。
满足上述条件的成为可优化下标变量。
在 C语言中，要求循环控制变量每次循环的变动是常数。
循环优化的实现
循环结构的识别
数据流分析
代码转换循环结构的识别
对于源程序来说，识别循环是比较方便的。但是代码的优化是针对四元式序列的，所以识别循环必须针对流图进行。
定义 8.3 如果流图中，从某个初始节点出发，每一条到达节点 n的路径都必须经过 m，那么称 m是节点 n的必经节点。记为 m dom n。
– 任何节点都是自己的必经节点。
– m为 n的前驱,n为 m的后继。
直接必经节点：从初始节点到达 n的所有路径上，节点
n的最后一个必经节点称为直接必经节点。
循环满足的条件
循环必须有唯一的入口节点，称为首节点。
对于循环中任何一个节点，必定至少有一个路径回到首节点。
回边和自然循环
定义 8.4 假定流图中存在两个节点 M和 N
满足 M dom N。如果存在从节点 N到 M的有向边 N->M，那么这条边称为回边。
定义 8.5 在流图中，给定一个回边 N->M，
对应与这个回边的自然循环为,M，以及所有可以不经过 M而到达 N的节点。 M
为该循环的首节点。
用节点的集合表示自然循环。
自然循环的例子
3 dom 4
回边 4->3
4 dom 7
回边 7->4
10->7的自然循环 {7，
8,10}
7-4的自然循环
{4,5,6,7,8,10}
4-3,8->3的自然循环
{3,4,5,6,7,8,10}
1
2
3
4
5 6
7
8
9 10
回边寻找算法
首先列出所有从首节点开始，不带圈的路径。
节点 N的必经节点的集合为满足一下条件的节点 M：
– 所有包含 N的路径 P,M都在 N的前面出现。
回边集合如下：
– {N-->M | N是一个节点,M在 N的必经节点集合中 }
寻找自然循环的算法
输入,回边 {N->M}; 输出,回边对应的自然循环,
算法,
设置 loop={N,M};
push(stack,N);
while non-empty(stack) do
{m = top(stack); pop(stack);
for m的每个前驱节点 p
{if p is_not_in loop then
{loop += p; push(stack,p);
}
}
算法的说明
节点 M在初始时刻已经在 loop中所以,M
的前驱不可能被加入到 loop中。
如果 N->M不是回边，那么，首节点会被加入到 loop中。此时算法不能得到自然循环。
相关概念
通常，循环互不相交，或者一个在另外一个里面。
内循环：不包含其他循环的循环称为内循环。
如果两个循环具有相同的首节点，那么很难说一个包含另外一个。此时把两个循环合并。
B0
B1
B2 B3
可归约流图
可归约流图：删除了其中回边之后，
可以构成无环有向图的流图。
– 不存在循环外向循环内部的转移，
进入循环必须通过其首节点。
实际的程序对应的流图一般都是可归约的流图。
没有 goto语句的结构化程序的流图总是可归约的。一般使用 goto语句的程序也是可归约的。
B1
B2 B3
数据流分析相关概念
变量获得值的方式：
– 通过赋值语句；
– 通过输入语句；
– 通过过程形式参数；
点：流图基本块中的位置，包括：第一个四元式之前，
两个相邻四元式之间，和最后的四元式之间。
定值：是变量 x获得值的四元式称为对 x的定值，一般用四元式的位置表示。
引用点：引用某个变量 x的四元式的位置称为 x的引用点。
数据流分析的种类
到达 -定值数据流方程
活跃变量数据流方程
可用表达式数据流方程到达 -定值数据流方程
到达 -定值：假定 x有定值 d，如果存在一个路径，从紧随 d的点到达某点 p，并且此路径上面没有被注销，则称 x的定值 d到达 p。这表明，在 p点使用变量 x的时候，
x的值可能是由 d点赋予的。
到达 -定值链：设变量 x有一个引用点 u，变量 x的所有能过到达 u的一切定值称为 x在 u点处的引用 -定值链，
简称 ud链。
显然，通过变量 x在引用点 u的 ud链，可以判断 x是否循环不变的。
到达定值数据流方程（记号）
IN[B],表示基本块 B的入口点处各个变量的定点集合。
– 如果 B中点 p之前有 x的定值点 d，且这个定值能够到达 p，则点 p处 x的 ud链是 {d}。
– 否则，点 p处 x的 ud链就是 IB[B]中关于 x的定值点的集合。
P[B],B的所有前驱基本块的集合。
GEN[B]：各个变量在 B内定值，并能够到达 B的出口点的所有定值的集合。
OUT[B]：各个变量的能够到达基本块 B的出口点的所有定值的集合。
KILL[B]：是各个变量在基本块 B中重新定值，因此才块内部被注销的定值点的集合。
到达定值数据流方程
IN[B] = U OUT[p] where p isin P[B]
OUT[B] = GEN[B] U (IN[B]-KILL[B])
其中：
– GEN[B]可以从基本块中求出：使用 DAG图就可以得到。
– KILL[B]中，对于整个流图中的所有 x的定值点，如果 B中有对 x的定值，那么该定值点在 KILL[B]中。
方程求解算法
使用迭代方法。
初始值设置为,IN[Bi]=空； OUT[B]=GEN[Bi];
change = TRUE;
while(change)
{
change = FALSE;
for each B do
{IN[B] = U OUT[p] where p isin P[B];
OUT[B] = GEN[B] U (IN[B]-KILL[B]);
oldout = OUT[B];
if(OUT[B] != oldout) change = TRUE;}
}
算法例子
GEN[B1]={d1,d2,d3}
KILL[B1]={d4,d5,d6,d7}
GEN[B2]={d4,d5}
KILL[B2]={d1,d2,d7}
GEN[B3]={d6}
KILL[B3]={d3}
GEN[B4]={d7}
KILL[B4]={d1,d4}
d1,- m 1 j
d2,= n j
d3,= u2 a
d4,+ i 1 i
d5,- j 1 j
d6,= u2 a
d7,= u3 i
B1
B2
B3
B4
计算过程
初始化：
– IN[B1] = IN[B2] = IN[B3] = IN[B4] =空
– OUT[B1]={d1,d2,d3},OUT[B2]={d4,d5}
– OUT[B3]={d6},OUT[B4]={d7}.
第一次循环：
– IN[B1]=空 ; IN[B2] ={d1,d2,d3,d7}; IN[B3]={d4,d5};
– IN[B4]={d4,d5,d6}; OUT[B1]={d1,d2,d3};
– OUT[B2]={d3,d4,d5}…
结果：
– IN[B1]=空； OUT[B1]={d1,d2,d3};
– IN[B2]={d1,d2,d3,d5,d6,d7}; OUT[B2]={d3,d4,d5,d6};
– IN[B3]={d3,d4,d5,d6}; OUT[B3]={d4,d5,d6};
– IN[B4]={d3,d4,d5,d6}; OUT[B4]={d3,d5,d6,d7};
活跃变量数据流方程
判断在基本块出口之后，变量的值是否还被引用的这种判断工作称为活跃变量分析。
消除复写四元式的依据就是对活跃变量的分析。如果某个变量的值在以后不被引用，那么该复写四元式可以被消除。
对于变量 x和流图上的某个点 p，存在一条从 p开始的路径，在此路径上在对 x定值之前引用变量 x的值，则称变量 x在点 p是活跃变量，否则称 x在点 x不活跃。
无用赋值：对于 x在点 p的定值，在所有基本块内不被引用，且在基本块出口之后又是不活跃的，那么 x在点 p的定值是无用的。
记号
L_IN[B],基本块 B的入口点的活跃变量集合。
L_OUT[B],是在基本块 B的出口点的活跃变量集合。
L_DEF[B],是在基本块 b内的定值，但是在定值前在 B中没有被引用的变量的集合。
L_USE[B],表示在基本块中引用，但是引用前在 B中没有被定值的变量集合。
其中,L_DEF[B]和 L_USE[B]是可以从基本块 B
中直接求得的量，因此在方程中作为已知量。
活跃变量数据流方程
L_IN[B] = L_USE[B] U(L_OUT[B]-L_DEF[B])
L_OUT[B] = U L_IN[s]，其中 s遍历 B的所有后继。
变量在某点活跃，表示变量在该点的值在以后会被使用。
第一个方程表示：
– 如果某个变量在 B中没有定值就使用了，显然，变量在在入口处的值会被使用。
– 如果这个变量在 B的出口处活跃，并且 B中没有对他进行定值，那么变量在入口处也是活跃的。
第二个方程表示：
– 在 B的某个后记中会使用该后继的入口处的值，那么他其实也可能使用 B的出口处的值。
活跃变量数据流方程求解
设置初值,L_IN[Bi]=空 ;
重复执行一下步骤知道 L_IN[Bi]不再改变：
for(i=1; i<n; i++)
{
L_OUT[Bi]=U L_IN[s]; s是 Bi的后继；
L_IN[Bi]=L_USE[Bi] U (L_OUT[Bi]-L_DEF[Bi]);
}
活跃变量数据流方程例子
L_DEF[B1]={i,j,a}
L_USE[B1]={m,n,
u1}
L_DEF[B2]=空
L_USE[B2]={i,j}
L_DEF[B3]={a}
L_USE[B3]={u2}
L_DEF[B4]={i}
L_USE[B4]={u3}
d1,- m 1 j
d2,= n j
d3,= u2 a
d4,+ i 1 i
d5,- j 1 j
d6,= u2 a
d7,= u3 i
迭代过程
第一次循环：
– L_OUT[B1]=空 L_IN[B1]={m,n,u1}
– L_OUT[B2]=空 L_IN[B2]={i,j}
– L_OUT[B3]={i,j} L_IN[B3]={i,j,u2}
– L_OUT[B4]={i,j,u2} L_IN[B4]={j,u2,u3}
第二次循环：
– L_OUT[B1]={i,j,u2,u3} L_IN[B1]={m,n,u1,u2,u3}
– L_OUT[B2]={i,j,u2,u3} L_IN[B2]={i,j,u2,u3}
– L_OUT[B3]={i,j,u2,u3} L_IN[B3]={i,j,u2,u3}
– L_OUT[B4]={i,j,u2,u3} L_IN[B4]={j,u2,u3}
第三次循环各个值不再改变，完成求解。
可用表达式数据流方程
如果一个流图的首节点到达点 p的每个路径上面都有对
x op y的计算，并且在最后一个这样的计算到点 p之间某有对 x,y进行定值，那么表达式 x op y在点 p是可用的。
表达式可用的直观意义：在点 p上,x op y已经在之前被计算过，不需要重新计算。
注意：如果对于有间接赋值四元式的情况，需要保证最后的计算 x op y的点之间不会间接改变 x,或者 y的值：
比如指针不会指向 x或者 y的存储区域，特别是当 x为某个数组的时候。
书上的讲解是针对没有间接赋值四元式的情况处理的。
概念
对表达式的注销：如果某个基本块 B对 x或者 y
定值，且以后没有重新计算 x op y，那么称 B注销表达式 x op y。
表达式的产生：如果某个基本块 B对 x op y进行计算，而以后并没有在对 x或者 y重新定值，那么称 B产生表达式 x op y。
表达式的全集：在计算某个流图中的可用表达式的时候，表达式的讨论范围被限定在该出现在流图中的四元式对应的表达式。
记号
E_OUT[B]：在基本块出口处的可用表达式集合。
E_IN[B]：在基本块入口处的可用表达式集合。
E_GEN[B]：基本块 B所产生的可用表达式的集合。
E_KILL[B]：基本块 B所注销掉的可用表达式的集合。
E_GEN[B]和 E_KILL[B]的值可以直接从流图计算出来。因此在数据流方程中，可以将 E_GEN[B]和
E_KILL[B]当作已知量看待。
E_GEN[B]的计算
对于一个基本块 B,E_GEN[B]的计算过程如下：
初始设置,E_GEN[B]=空；
顺序扫描每个四元式：
– 对于四元式 op x y z，把 x op y加入 E_GEN[B]，
– 从 E_GEN[B]中删除和 z相关的表达式。
最后的 E_GEN[B]就是相应的集合。
E_KILL[B]的计算
设流图的表达式全集为 E;
初始设置,EK = 空；
顺序扫描基本块的每个四元式：
– 对于四元式 op x y z，把表达式 x op y从 EK中消除；
– 把 E中所有和 z相关的四元式加入到 EK中。
扫描完所有的四元式之后,EK就是所求的
E_KILL[B]。
数据流方程
1,E_OUT[B] = (E_IN[B]-E_KILL[B]) U
E_GEN[B]
2,E_IN[B]= ∩E_OUT[p] B!=B1,p是 B的前驱。
3,E_IN[B1]=空集
说明：
– 在程序开始的时候，无可用表达式。 (3)
– 一个表达式在某个基本块的入口点可用，
必须要求它在所有前驱的出口点也可用。
（ 2）
– 一个表达式在某个基本块的出口点可用，
或者该表达式是由它的产生的；或者该表达式在入口点可用，且没有被注销掉。
（ 1）
B
p2p1 p3
IN
OUT
GEN -KILL
方程求解算法
迭代算法
初始化,E_IN[B1]=空 ;
E_OUT[B1]=E_GEN[B1];E_OUT[BI]=U-
E_KILL[Bi](i>=2)
重复执行下列算法直到 E_OUT稳定,
FOR（ i=2; i<=n ;i++)
{
E_IN[Bi]= ∩E_OUT[p],p是 Bi的前驱；
E_OUT[Bi]=E_GEN[Bi] ∪ (E_IN[Bi]-E_KILL[Bi]);
}
算法说明
初始化值和前面的两个算法不同。
E_OUT[Bi]的初值大于实际的值。
在迭代的过程种,E_OUT[Bi]的值逐渐缩小直到稳定。
U表示四元式的全集，就是四元式序列中所有表达式 x op y的集合。
寻找循环不变表达式算法
输入：循环 L，已经建立的 UD链
输出：不变四元式
步骤 1：如果四元式的运算分量或者是常数，或者其所有定值点在循环外部。
步骤 2：重复执行下面的步骤：
– 如果一个四元式没有被加过标记，且孙算分量要么是常数，要么其 UD链中的定值点在循环外，或者该定值点已经被加过标记。
说明：一个四元式的是不变的，当且仅当其分量在循环中是不变的。主要有三种情况：常量，定值点在循环外部，或者定值点的四元式也是不变的。
不变四元式外提方法
对于不变四元式，可以在进入循环之前首先计算该四元式的值，
然后在循环内部使用该值。
可以将四元式的值外体到紧靠循环之前。
首节点首节点前置节点代码外提不合法的情况（ 1）
= 1 i
< u v B3
= 2 i
+ u 1 u
- v 1 v
<= v 20 B5
= i j
= 1 i
< u v B3
+ u 1 u
- v 1 v
<= v 20 B5
= i j
= 2 i
代码外提不合法的情况（ 2）
= 1 i
= 3 i
< u v B3
= 2 i
+ u 1 u
- v 1 v
<= v 20 B5
= i j
= 1 i
= 3 i
< u v B3
= 2 i
+ u 1 u
- v 1 v
<= v 20 B5
= i j
代码外提不合法的情况（ 3）
= 1 i
= 0 k
< u v B3
= i k
+ u 1 u
= 2 i
- v 1 v
<= v 20 B5
= i j
= 1 i
= 0 k
= 2 i
< u v B3
= i k
+ u 1 u
- v 1 v
<= v 20 B5
= i j
不变四元式外提的条件
不变四元式 op x y z可以外提的条件：
– Q坐在的基本块节点是循环所有出口节点的必经节点。出口节点是指有后继节点在循环外的节点。（反例：情况 1）
– 循环中 z没有其他的定值点。（反例：情况 2）
– 循环中 z的引用点仅由 Q到达。（反例：情况 3）
外提算法
步骤 1：寻找一切不变四元式。
步骤 2：对于找到的每个循环，检查是否满足上面说的三个条件。
步骤 3：按照不变四元式找出的次序，把所找到的满足上述条件的四元式外提到前置节点中。
– 如果四元式有分量在循环中定值，只有将定值点外提后，该四元式才可以外提。
循环不变式外提的例子
= 1 i
= 0 k
1) + i 1 k
2) * 2 k t
< u v B3
+ u 1 u
- v 1 v
<= v 20 B5
= i j
= 1 i
= 0 k
< u v B3
+ u 1 u
- v 1 v
<= v 20 B5
= i j
1)+ i 1 k
2)* 2 k t
关于归纳变量的优化
基本归纳变量：如果循环中，对于 i的定值只有形状如 i = i + c的定值，那么 I称为循环的基本归纳变量。
归纳变量族：如果循环中对变量 j的定值都是形状如 j=C1*i+C2，且 i为基本归纳变量，那么称 j
为归纳变量，且属于 i族。 i属于 i族。
对于定值为 C1*i+C2的 I族归纳变量 j，我们用
(i,C1,C2)来表示。
对于 i族的归纳变量 (i,C1,C2)，要求循环内部对此变量进行定值的时候，一定是赋给 C1*i+C2。
例子（源程序）
for(i = 0; i<100; i++)
{
j = 4*i;
printf(“%i”,j);
}
i是基本归纳变量。 j是 i族归纳变量，可以表示为 (i,
4,0)。
寻找循环的归纳变量算法
步骤 1：扫描循环的四元式，找出所有基本归纳变量。对应于每个基本归纳变量的三元组如 (i,1,0)。
步骤 2：寻找循环中只有一个赋值的变量 k，且对它的定值为如下形式,k=j*b,k=b*j,k=j/b,k=j+(-)b,k=b+(-)j。其中 j
为基本归纳变量，或者已经找到的归纳变量。
– 如果 j为基本归纳变量，那么 k属于 j族。 k对应的三元式可以确定。
– 如果 j不是基本归纳变量，且属于 i族，那么我们还要求：
循环中对 j的赋值以及和对 k的赋值之间没有对 i的赋值，且
没有 j在循环外的定值可以到达 k的这个定值点。
j的三元式可以相应确定。
算法说明
关于 j不是基本归纳变量的时候，算法中的两个要求实际上是保证：对 k进行赋值的时候,j变量当时的值一定等于 C1*（ i
当时的值） +C2。
归纳变量的计算强度削减算法
对于每个基本归纳变量 i，对其族中的每个归纳变量 j(i,c,d)执行下列步骤：
– 建立新的临时变量 t。
– 用 = t j四元式代替对 j的赋值。
– 对于每个定值 i=i+n之后，添加 t=t+c*n。
– 在前值节点的末尾，添加四元式 * c i t和 +
t d t。使得在循环开始的时候,t=c*i+t。
当两个归纳变量具有同样的三元式的时候，
可以只建立一个临时变量。
算法的说明
在优化过程中，为 j(i,c,d)引入的变量 t保证了在任何时刻 (不包括在对 i新定值后并且在 t重新定值前，但是由于两者的四元式时紧连的）都满足 t=c*i+d。
如果在某些情况下，程序运行时对 j的定值的次数远远少于对 i的定值，经过优化的程序需要对 t多次赋值，实际的效率可能降低。
归纳变量的删除
有些归纳变量的作用就是控制循环的次数。如果循环出口处的判断可以使用其它的变量代替，那么可以删除这些归纳变量。
归纳变量的删除算法
步骤 1：对于每个基本归纳变量，取 i族的某个归纳变量 j（尽量使得 c,d简单）。把每个对 i的测试修改称为用 j代替。
– relop i x B修改为 relop i c*x+d B。
– relop i1 i2 B，如果能够找到三元组 (i1,c,d)和 (i2,c,d)，那么可以将其修改为 relop j1 j2 B(假设 c>0)。
– 如果归纳变量不再被引用，那么可以删除和它相关的四元式。
– 如果基本归纳变量在循环出口处活跃，上面的算法不可以直接使用。
步骤 2：考虑对 j的赋值 = t j。如果每次对 j引用和这个赋值四元式之间没有任何对 t的赋值（此时，每次使用 j的时候都有 t=j)，
可以在引用 j的地方用 t代替，同时删除四元式 = t j（如果 j在循环的出口处活跃，需要增加 = t j）。
全局公共子表达式消除
对于循环中某个四元式 op x y z，如果在所有到达这个四元式的路径上，已经计算了 x op y，且计算之后 x,y的值再没有修改过，那么显然我们可以使用以前计算得到的值。
可用表达式表达的就是这个概念。
如果有四元式 op x y z，且在四元式前，表达式 x op
y可用，那么我们可以用下面的方法优化：在前面不同的地方计算 x op y时，把值记录到同一个临时变量 u里面。把这个四元式改变为 = u z。
全局公共子表达式消除
对于四元式 Q(op x y z)，如果 x op y再 Q之前可用，那么执行如下步骤：
– 从 Q开始逆向寻找，找到所有离 Q最近的计算了 x op y四元式。
– 建立新的临时变量 u。
– 把步骤 1中找到的四元式 op x y t用下列四元式代替,op x y u和 = u t。
– 用 = u t替代 Q。
全局公共子表达式消除 (图示 )
… …
* x y t
… …
… …
* x y k
… …
… …
* x y l
… …
… …
* x y u
= u k
… …
… …
= u l
… …
… …
* x y u
= u t
… …
复写四元式的消除
中间代码的生成可能产生四元式。
消除公共子表达式和删除归纳变量的时候，也会产生复写四元式。
通过复写四元式传播的变量大多数是临时变量。而对临时变量可以使用复写传播来消除复写四元式。
原理,= x y的效果是 x和 y的值相等。如果某个引用 y的四元式运行的时候,x和 y的值一定相等。那么我们可以使用对 y的引用来替代对 x的引用。这样做有时可以消除复写四元式 = x y。
消除复写四元式的条件
对于复写四元式 d,= x y，如果对 y对应于 d点的一切引用点 u满足下列条件，
那么我们可以删除 d，并且在这些引用点上用对 x的引用代替对 y的引用。
– 此定值点是 d到达 u的唯一的 y的定值。
– 从 d到达 u的路径（可以包含圈和多个 u，但是不包含多个 d）上，没有对 x的定值。
这两个条件实际上是说，当程序运行到达 u点的时候,x和 y的值总是相等。
记号
C_GEN[B]：在基本块 B中的所有复写四元式 = x y，
并且从该四元式开始到 B的出口,x和 y都没有在定值。
C_KILL[B]：包含了所有在流图中出现并且满足下列条件的复写四元式 = x y,B中存在对 x或者 y的定值，并且之后在没有复写四元式 = x y出现。
C_IN[B]：表示在 B的入口点，有效的复写四元式 = x
y的集合，也就是到达入口的路径上都要经过 = x
y并且之后没有对 x或者 y定值。
C_OUT[B]：表示在 B的出口点有效的复写四元式的集合。
数据流方程
C_OUT[B] = C_GEN[B] ∪ (C_IN[B]-
C_KILL[B])
C_IN[B] = ∩E_OUT[p]；其中 B不等于 B1,p
是 B的前驱。
C_IN[B1] = 空集。
其中 C_GEN[B]和 C_IN[B]可以直接从流图得到，所以在方程中作为已知量处理。
求解方法和可用表达式的求解相同。
复写传播算法
对于每个复写四元式 d,= x y执行下列步骤。
– 找出该 y定值所能够到达的那些对 y的引用。
– 对于每个这样的 y，确定 d是否在 C_IN[B]中，
B使包含这个引用的基本块，而且 B中该引用的前面没有 x或者 y的定值。
– 如果 d满足条件 (2)，删除 d，且把步骤 1中找到的的对 y的引用用 x代替。
复写传播算法的例子
= x y
* y 2 t
= x y
* y 3 t2
+ x 1 y
循环优化的例子 (原始流图）
B2
- m 1 t1
= t1 i
= n j
* 4 n t2
=[] A t2 t3
= t3 v
+ i 1 t4
= t4 i
* 4 i t5
=[] A t5 t6
< t9 v B3
- j 1 t7
= t7 j
* 4 j t8
=[] A t8 t9
> t9 v B3
>= i j B6
* 4 i t10
=[] A t10 t11
= t11 x
* 4 i t12
[]= A t12 t13
… … … …
< i j B2
* 4 i t18
=[] A t18 t19
= t19 x
* 4 i t20
[]= A t20 t21
* 4 n t22
=[] A t22 t23
&= t23 t21 t21
* 4 n t24
[]= A t24 t25
&= x t25 t25
B1 B3
B4
B5
B6
B7
寻找回边以及自然循环
回边有,B2?B2,B3?B3,B6?B2。
B2?B2对应的循环是 {B2}
B3?B3对应的循环是 {B3}
B6?B2对应的循环是 {B2,B3,B4,B5,B6}
删除回边之后，得到的图是无回路的，
所以这个流图是可归纳流图。
寻找公共子表达式
4*i：在 B5,B7入口处可用 (U1)。
A[4*i]：在 B5,B7的入口处可用 (U2)。
4*j：在 B5的入口处可用 (U3)。
A[4*j]：在 B5的入口处可用 (U4)。
4*n：在 B7的入口处可用 (U5)。
A[4*n]：在 B7的入口处可用 (U6)。
公共子表达式的优化
- m 1 t1
= t1 i
= n j
* 4 n u5
= u5 t2
=[] A t2 u6
= u6 t3
= t3 v
+ i 1 t4
= t4 i
* 4 i u1
= u1 t5
=[] A t5 u2
= u2 t6
< t9 v B3
- j 1 t7
= t7 j
* 4 j u3
= u3 t8
=[] A t8 u4
= u4 t9
> t9 v B3
>= i j B6
= u1 t10
= u2 t11
= t11 x
* 4 i t12
[]= A t12 t13
… … … …
< i j B2
= u1 t18
= u2 t19
= t19 x
= u1 t20
[]= A t20 t21
= u5 t22
= u6 t23
&= t23 t21 t21
= u5 t24
[]= A t24 t25
&= x t25 t25
B1 B3
B4
B5
B6
B7
寻找归纳变量
基本归纳变量有 i,j。
归纳变量有：
– u1,i族,(i,4,0)
– u2,j族,(j,4,0)
如果分析得更加深入，会发现 []= 四元式得到的地址也是归纳变量。但是，由于我们不考虑对间接赋值的优化，同时地址的处理也不在范围之内，所以我们没有类出。
归纳变量的优化- m 1 t1
= t1 i
= n j
* 4 n u5
= u5 t2
=[] A t2 u6
= u6 t3
= t3 v
* 4 i u1
* 4 j u3
+ i 1 t4
= t4 i
+ u1 4 u1
=[] A u1 u2
= u2 t6
< t9 v B3
- j 1 t7
= t7 j
- u3 4 u3
=[] A u3 u4
= u4 t9
> t9 v B3
>= u1 u3 B6
= u2 t11
= t11 x
= u1 t12
[]= A t12 t13
… … … …
< u1 u3 B2
= u2 t19
= t19 x
= u1 t20
[]= A t20 t21
= u5 t22
= u6 t23
&= t23 t21 t21
= u5 t24
[]= A t24 t25
&= x t25 t25
B1 B3
B4
B5
B6
B7
优化结果- m 1 t1
= t1 i
= n j
* 4 n u5
= u5 t2
=[] A t2 u6
= u6 t3
= t3 v
* 4 i u1
* 4 j u3
+ u1 4 u1
=[] A u1 u2
= u2 t6
< t9 v B3
- u3 4 u3
=[] A u3 u4
= u4 t9
> t9 v B3
>= u1 u3 B6
= u2 t11
= t11 x
= u1 t12
[]= A t12 t13
… … … …
< u1 u3 B2
= u2 t19
= t19 x
= u1 t20
[]= A t20 t21
= u5 t22
= u6 t23
&= t23 t21 t21
= u5 t24
[]= A t24 t25
&= x t25 t25
B1 B3
B4
B5
B6
B7
窥孔优化
是指对代码局部进行改进的简单有效的技术。只考虑目标代码中的指令序列，
把可能的指令序列替换成为更短更快的指令。
– 冗余指令删除。
– 控制流优化
– 代数化简
– 特殊指令使用冗余指令删除
多余存取指令的删除：
– MOV b R0
– ADD c R0
– MOV R0 a
– MOV a R0
– SUB d R0
– MOV R0 c
第四条指令没有任何效果，可以删除。
如果有标号转向第四条指令，则不可以删除。
冗余指令删除
死代码删除：
– 将不会被执行的代码删除。
– 如果目标代码中有无条件转移指令，且其后的指令标号，那么后面的指令可以删除。
产生死代码的原因可以是调试信息，或者优化的结果。
对于条件转移指令，如果其条件永远成立或者永远不成立，可以转换成为等价的无条件转移指令。
控制流优化
在代码中出现转移指令到转移指令的情况时，
某些条件下可以使用一个转移指令来代替。
转移到转移
– GOTO L1;
– … …
– L1,GOTO L2;
显然第一个转移指令可以替代为 GOTO L2.
如果在没有其他的指令转移到 L1，那么第二个指令可以被删除。
控制流优化（续）
转移到条件转移：
– L0,GOTO L1 … …
– L1,IF b THEN GOTO L2;
– L3,… …
如果只有一个转移指令到达 L1，且 L1前面是无条件转移指令，那么可以修改成为：
– IF b THEN GOTO L2;
– GOTO L3
– L3,… …
控制流优化（续）
条件转移到转移
IF b THEN GOTO L1
… …
GOTO L3
可以被修改为
IF b THEN GOTO L3
… …
GOTO L3
代数化简
利用代数规则来优化代码。
例如：
–利用 x=x+0和 x=x*1来删除相应的指令。
–利用 x2=x*x来削减计算强度。
特殊指令的使用
充分利用目标系统的某些高效的特殊指令来提高代码效率。
这些指令只可以在某些情况下使用。而识别这样的情况是优化的基础。
例如,INC指令可以用来替代加 1的操作。
