1
编译原理第七章 代码优化上海交通大学张冬茉
Email:zhang-dm@cs.sjtu.edu.cn
2004年 6月
2
本章目的代码优化是从生成的目标代码中识别出那些可以经过变换而提高效率的部分,并实施这种变换 。 这种优化并不是极值理论中的那种求极值点的优化,它只追求变换后的代码要比变换前的效率要高些 。
3
第七章 代码优化
§ 7.1 优化概述一,优化定义优化是一种等价、有效的程序变换。等价是指不改变程序运行结果，即对变换前后的程序给以相同的输入，
应有相同的输出，即变换是安全的。
而有效是指经变换后的程序与变换前的程序相比运行速度更快，所占空间更少，也即所谓时空效益要高。
时间短空间省，这两个要求可以是相容的，并行不悖的。数据不相关的两个循环，经循环合并构成一个循环，循环控制的开销节省了，代码长度也因此缩短了。
但有时，时间短空间省的要求可能会不可兼得，这时就有牺牲时间换取空间或牺牲空间换取时间两种策略，
需要有个综合分析和实事求是的取舍。
4
二、不同阶段的优化
(1)优化可以在源程序阶段也可以在编译阶段进行
(2)编译优化又可分成两个阶段，即中间代码优化与目标代码优化,编译优化工作中有一部分与目标机有关，有效而合理地使用机器资源便是目标代码优化阶段要实现的
(3) 中间代码的优化有局部化与非局部优化之分。局部优化是指基本块内的优化，非局部优化是指超越基本块的优化，因此对中间代码划分基本块，是优化所必需的。
(4) 非局部优化也有循环优化与全书局优化之分，将中间代码以基本块为结点，构造出程序流图，从中识别出循环结构
5
优化源程序优化编译优化中间代码优化目标代码优化非局部优化局部优化循环优化 全局优化图 7.1 在各个阶段的优化
6
三、程序流图的构造程序流图是程序的图形表示。我们把有唯一首结点
n0的有向图 G称为控制流程图。首结点 n0是到图中任何结点 n都有道路 n0?n的一个特殊的结点。
因此控制流程图是一个三元组 G=(N,E,n0)，
其中 N为结点集 (包括 n0),E为有向边集。通常将控制流程图简称为流图，或程序流图。对一个程序流图来说，结点代表计算，有向边代表控制流，
而首结点是程序起始位置所在的结点 (基本块 )。
1,基本块基本块是程序语句序列中满足下列条件的长度最长的子序列：这个语句子序列是顺序执行的；它只有一个入口即子序列的第一语句；只有一个出口即子序列的最后一个语句。停止语句和转向 (分支 )语句只可能是基本块的最末一个语句。
7
2,划分基本块的算法输入：三地址语句序列。
输出：基本块表。每个三地址语句，仅在一个基本块中。方法：
(1) 首先确定各个基本块的第一个语句即入口语句。
规则是：程序的第一个语句。
能由条件或无条件转移语句转移到的语句。
紧跟在条件转移语句后的那个语句。
(2) 由每个入口语句构造所在的基本块：①由一入口语句到转移或停止语句 (含转移或停止语句 )之间的语句序列。②由一入口语句到下一入口语句 (不含下一入口语句 )之间的语句序列。
(3) 凡未被归入基本块的语句，为程序控制流图不能到达的语句，因此为不可能执行的语句，故可从程序中删除。
8
3,构造流图的算法输入：划分基本块算法输出的基本块表输出：程序流图 G=(N,E,n0)
方法：
(1) 输入的基本块集即为 N。
(2) 含有程序第一个语句的基本块为首结点 n0。
(3) 对 N中任两个结点 (基本块 )Bi和 Bj如果 Bj紧跟在 Bi
之后，且 Bi的出口语句不是无条件转移或停止语句；
或 Bi的出口语句是转移语句，其转向点为 Bj的第一个语句。则结点 Bi和 Bj之间有一有向边 Bi?Bj。这些有向边的集合为 E。
9
§ 7.2 局部优化一、基本块内的优化局部优化是基本块内的优化，通常有：
1,合并已知量对于 A:=op B或 A:=B op C，其中 B及 C均为常数，则编译时即可计算出 op B或 B op C的值，作为 A的值，
而不必生成相应的代码。
2,删除公共子表达式也称为删除多余运算。如图 7.3的基本块 B5中，语句
(14),(16)计算相同的 4*I称为公共子表达式，在
(14)t6:=4*i计算后 (16)处只需将 t6的值复写给 t7即
t7:=t6就可以了。语句 (17),(20)也有公共子表达式 4*j，
故语句 (20)可变换成 t10:=t8，这样就避免了多余运算。
10
3,删除死代码死代码有两种情况：
(1) 在分支程序中，测试语句取固定值，如取 ture，则
false分支的代码是死代码。这种情况下删除死代码不可能局限在基本块内。
(2) 变量 A被定值后不再被引用，或者仅有的定值与引用为 A:=A+C的递归赋值形式，则该定值语句是死代码，称为无用赋值。例如基本块 B5中删除公共子表达式后 t7,t6有相同的值，故对 t7的引用可由 t6来代替，
同样对 t10的引用也可由 t8来代替。故语句 (19)可转换成 a[t6]:=t9，语句 (21)可转换成 a[t8]:=x。如果 t7,t10
出了基本块 B5后也不活跃 (即不再被引用 )，则 (16)的
t7:=t6和 (20)的 t10:=t8便成为无用赋值。在基本块范围内，变量 A在定值后未经引用又发生了对 A的第二次定值，则前一定值为无用赋值。
11
二、基本块的 dag表示可以用一个无环路有向 dag(directed acyclic graph)来表示一个基本,dag是实现基本块内优化变换的有效表示，可以决定基本块内的公共子表达式，并删除那些死代码；可以决定在基本块外定值而在基本块内被引用的变量名字；可以决定基本块内哪些变量名字的定值可以在基本块外被引用。
为了描述计算过程，我们在无环路有向图的结点上给出如下标记或附加标记：
12
(1) 图的叶结点用标识符 (标识变量名 )或常数作为唯一标记，表示该结点代表所标记的变量或常数的值。至于是变量的左一值还是右一值，可由作用于变量名的算符决定，通常为右一值。叶结点代表变量的初值，
加下标 0，以示区别。
(2) 图的内部结点用运算符 op作为标记，该结点的后继结点所代表的值，为参于运算的分量，因此该内部结点表示由它的后继结点代表的运算分量经 op运算后的表达式的结果。
(3) 图中各结点可能附加一个或多个标识符作为附加标记，表示这些附加的标记标识符具有该结点所代表的相同的值。
上述无环路有向图称为描述计算过程的 dag，简称为
dag.
13
三,dag的构造基本块的 dag是通过依次处理它的每一个语句而建立起来的，
这里所说的语句是指的三地址代码。通常的语句形式及它们所对应的 dag表示如图 7.5所示：
如果待处理的语句形如 x:=y op z，其处理的步骤为：
(1) 在已建立的 dag了图中寻找能代表 y,z当前值的结点。
(2) 若代表 y,z当前值的结点至少有一个标记为非常数，则执行步骤 (3)，否则执行下列步骤：
执行 y op z，令其结果常数为 x0。
如果,y或 z是执行当前语句 x:=y op z时新建立的结点，则删除它。
如果已建立的 dag子图中没有标记为 x0的常数叶结点，则建立新的结点 n，它的标记为 x0。
如果已建立的子图有标记为 x0的叶结点，则令该结点为 n。
执行步骤 (4)
14
(3) 在已建立的 dag子图中寻找这样的结点：它标记为 op，它的左子结点为代表 y当前值的结点它的右子结点为代表 z当前值的结点。也有两种可能：
已建立的 dag子图中寻找这样的结点：它标记为 op，它的左子结点为代表 y当前值的结点，它的右子结点为代表 z当前值的结点。也有两种可能：
在已建立的 dag子图中没有这样的结点，则建立一新的内部结
n，它以代表 y,z当前值的结点作为它的左右子结点，令它标记为 op。
在已建立的子图中存在这样的结点，不妨令它为 n。
(4) 对于在步骤 (2)或 (3)中找到的或新建立的结点 n，应将 x加入到该结点的附加标记集中，但在此之前如果 x(不是 x0)已出现在某个结点的附加标记集中，则应先将 x从这个附加标记集中删除。这表明此时 x已重新定值,x的当前值已不是原来的那个 x
了。
(5) 处理下一语句，直至结束。
15
[例 7.3] 与下列基本块相应的 dag的构造过程如图 7.6。
pi:=3.14
t1:=2*pi
t2:=R+r
A:=t1*t2
t3:=2*pi
t4:=R+r
t5:=t2*t4
t6:=R-r
t7:=t5*t6
A:=t7-A
16
n1 n1 n2n1n2 n3 n4
n5
+
t1
t2
pipi t1pi
3.14 3.14 6.28 3.14 6.28 R r
(a) (b) (c)
n2n1 n3 n4
n5
+
t1
t2
pi
3.14 6.28 R r
(d)
n6 A
*
n2n1 n3 n4
n5
+
t1,t3
t2
pi
3.14 6.28 R r
(e)
n6 A
*
n2n1 n3 n4
n5
+
t1,t3
t2,t4
pi
3.14 6.28 R r
(f)
n6 A
*
n2n1 n3 n4
n5
+
t1,t3
t2,t4
pi
3.14 6.28 R r
(g)
n6 A,t5
*
n2n1 n3 n4
n5 +
t1,t3
t2,t4
pi
3.14 6.28 R r
(h)
n6 A,t5
*
n7 t6-
17
n2n1 n3 n4
n5
+
t1,t3
t2,t4
pi
3.14 6.28 R r
(h)
n6 A,t5
*
n7 t6
-
n8
*
t7
n2n1 n3 n4
n5
+
t1,t3
t2,t4
pi
3.14 6.28 R r
(g)
n6 A,t5
*
n7 t6
-
n8
*
t7
n9
-
A
图 7.6 dag的构造过程
18
四,dag实现的优化从上述构造 dag的步骤及例 7.3中不难发现：
dag构造时已实现了如下优化：
1,合并已知量步骤 (2)对公共子表达式并不生成标记该运算的内部结点，而是执行运算，由结果常数参与构造 dag，实现了编译时合并已知量的优化。
2,删除多余运算步骤 (3)对公共子表达式并不生成重复的结点，
只是在结点的附加标记集中增加被赋值变量名 。
19
3,删除死代码步骤 (4)，在将 x附加到结点 n上之前，删除已出现在某个结点的附加标记集中的 x，那些定值后未被引用即被重新定值的 x，因 x的删除而成为死代码，其前一次的定值被删除。
此外，从 dag还可知道：
(1) 作为 dag叶结点标记的标识符，是在此之前的基本块内被定值并在本基本块内被引用的变量名。
(2) 作为 dag各结点附加标记的标识符是在基本块内定值并可以在基本块内和基本块后被引用的变量名，
如果确认某结点的一个附加标记在基本块后不会被引用 (称为不活跃 )，则该标识符的定值语句可作为死代码被删除。
20
[例 7.4] 如果例 7.3的 dag按结点建立次序重构基本块，则可得到经上述优化后的基本块。
pi:=3.14
t1:=6.28
t3:=6.28
t2:=R+r
t4:=t2
t5:=6.28*t2
t6:=R-r
t7:=t5*t6
A:=t7-t5
如果 pi及 t1-t7出基本块不活跃 (它们只是在计算表达式时使用的临时变量 )，则重构的基本块可进一步优化为：
S1:=R+r
S2:=6.28*S1
S3:=R-r
S4:=S2*S3
A:=S4-S2
21
§ 7.3 控制流分析及循环的查找循环是指程序中可能反复执行的代码序列。循环并不一定都是由程序语言中的循环语句形成的，事实上，
在中间代码级，除了对程序单元调用 (Call)和返回
(Return)语句外，均由条件转移和无条件转移语句形成了各种控制语句。因此，首先应对循环给出定义，
然后设法从程序中找出符合定义的循环，这需要对程序流图作控制流分析，并在这基础上作数据流分析，
最后，在数据流分析基础上，做循环优化和全局优化。
22
一、循环的定义定义 7.1 循环是程序流图中有唯一入口结点的强通的子图。 12345678910图 7.9 例 7.5的流图
(1) 入口结点是指子图中有下列性质的结点 n,n是流图的首结点，或者子图外有结 m，它有一有向边
m?n引向结点 n。
(2) 强连通子图：子图中任两个结 m,n之间互相可达，即 m至 n及 n至 m均有通路 (用表示 )，且通路上的结点均属于该子图。如果子图只含一个结点，则该结点应有一有向边引向该结点自身 (自环路 )。
循环要求强连通是很自然的，要求入口结点唯一是由于循环优先中需要将循环不变运算提到循环之外
(代码外提 )入口前的一个确定地点，这就要求入口结点是唯一的。
23
[例 7.5] 图 7.9给出了程序流图。
由结点序列 {5,6,7,8,9}组成的子图是强连通的，仅有的入口结点是 5。
由结点序列 {4,5}组成的子图是强连通的，但 4,5均为子图的入口结点，所以这子图不是循环。
由结点序列 {2,4}组成的子图不是强通的,4与 2之间虽有通路
4?10?2但通路上的 10不在子图中。
1
2
3
4
5
6
7 8
9
10
图 7.9 例 7.5的流图
24
二、必经结点集例 7.5告诉我们，必须给出一种方法来查找流图中的循环。首先得分析流图中结点间的控制关系。
定义 7.2 从流图的首结点出发到达结点 n的任一通路都必需经过结点 d，则称 d是 n的必经结点，记为 d
DOM n。
25
根据定义，容易看出：
(1) 每个结点是它本身的必经结点，即 n DOM n。
(2) 流图的首结点 n0，是流图中任一结点 n的必经结点,n0 DOM n。
(3) 循环 L的入口结点 d，是循环内任一结点的必经结点。如果 d不是首结点 n0，即 n0?L,n0在循环外，
则由 n0到循环中任一结点 n的任一通路，必经过 d而进入循环，故 d是 n的必经结点。
(4) 一个结点的必经结点可能不止一个，如对循环内除入口结点 n而言，它至少有三个必经结点：首结点 n0，循环入口结点 d，及结点 n自身。我们将流图中结点 n的所有必经结点称为 n的必经结点集，用 D(n)
表示。
26
如果将 DOM看成结点集 N上的一种二元关系，那么它具如下性质：
(1) 自反性。对任一 n?N,n DOM n；
(2) 反对称性。若 m,n?N,m DOM n且 n DOM n
则必有 m=n；
(3) 传递性。若 l,m,n?N，而 1 DOM m且 m DOM
n，则必有 1 DOM n.
因此,DOM是结点集 N上的一个偏序关系。
对于偏序关系，我们首先可得到 cover集,cover集中的 <d,n>，称 d是 n的直接必经结点，由 cover集得到描述偏序关系的哈斯图，是流图的必经结点树。
27
1
2
3
4
5
6
7 8
9
10
{1}
{1,2}
{1,2,3}
{1,2,4}
{1,2,4,5}
{1,2,4,5,6}
{1,2,4,5,6,7} {1,2,4,5,6,8}
{1,2,4,5,6,9}
{1,2,4,10}
图 7.10 图 7.9的必经结点集
1
2
4
10
3
5
6
7 8 9
图 7.11 图 7.9的必经结点树
28
这是迭代求解过程，其初值除首结点 D(n0)=n{0}外，
其余结点 n,D(n)=N。每次迭代中如果有一个结点 n
的新才 D(n)不相同，表明迭代未收敛，这由布尔变量
change来标志。集合可用位向量表示，此时集合运算
∪,∩ 就可用?,?来代替了。
D(n0)={n0}；
for(n?N-{n0})
{ D(n)=N； }
chang=true；
while(change)
{change=false； }
for(n?N-{n0})
{new={n}∪ D(p)； p?P(n)；
if (new != D(n))
{change=true； D(n)=new； }}
图 7.12 求必经结点集 D(n)的算法
29
三、自然循环循环 Loop是流图中有唯一入口结点 d的强连通子图，
它有这样两个性质：
(1) 这个入口结点 d必是循环中各结点的必经结点，
因为对任一 n?Loop，如果 d DOM n，则从首结点 n0，
必有一通路 n0?n，而这通路不经过 d，这就意味着循环外的结点可以不通过 d而进入循环，这与 d是唯一入口结点是矛盾的。
(2) 要使 Loop 中所有结点都有可能重复执行，则循环中至少有一条边回到 d，否则不可能强连通。
因此寻找循环，首先要找回边。
定义 7.3 流图 G=(N,E,n0)中的有向边 n?d，如果 d
DOM n，即 d?D(n)，则称 n?d为流图的回边。
30
主程序,stack=empty；
loop={d}；
insert(n)；
while(stack 非空 )
{上托 stack栈顶元素 m；
for(p?P(m))
{ insert(p)； }
}
过程,void insert(m)
{ if (m?loop) { loop=loopU{m}；
下推 m入栈 stack； }
}
图 7.13 构造由回边组成的循环的算法
31
[例 7.7] 图 7.9的流图，其必经结点已如图 7.10所示，
它有如下四条回边：
5?4，因 4?D(5)={1,2,4,5}
9?5，因 5?D(9)={1,2,4,5,6,9}
10?2，因 2?D(10)={1,2,4,10}
7?7,7?D(7)
定义 7.4 若 n?d是流图 G=(N,E,n0)的一条回边,M
是流图中有通路到达 n而该通路不经过 d 的结点集，
则 Loop={n,d} M，构成了 G的一个子图，称为由回边 n?d组成的自然循环。
32
四,可归约流图我们讨论的循环是一个自然循环,它是由回边为基础组成强连通的从而是可反复执行的子图,而且入口结点是唯一的 。 是不是所有可反复执行的代码都有这种性质呢？ 事实上,由回边构成的自然循环只是广义上的循环中的一类,
它们有这样的特点,删除了流图中的回边后,
成为一个无环路有向图 。
33
[例 7.9] 图 7.5的流图,删除了回边后如图 7.14所示,这是个无环路有向图 。
定义 7.5 一个流图删去了回边后的子图是个无环路的有向图，
则这个流图称为可归约流图。
[例 7.10] 图 7.15给出了最简单的不可归约流图，子图 {2,3}是可以重复执行的代码，但 2?3,3?2不是回边，结点 2,3都是这个广义循环的入口结点。
1
2
3
4
5
6
7 8
9
10
图 7.14 图 7.5删除了回边后无环路流图
1
2 3
图 7.15 不可归约流图
34
可归约流图是非常重要的流图,这是由于：
(1) 只由结构化控制语句构成的结构化程序,其流图总是可归约的,即使使用 goto语句的程序,几乎也都是可归约的 。
(2) 找出回边及由回边组成的自然循环,这类控制流的分析是容易实现的 。
(3) 对自然循环而言不存在循环外向循环内的转移,
进入循环必需通过入口结点 。 对两个循环来说,如果不是有相同的入口结点,那么它们要么是嵌套 (完全包含 ),要么是互不相交,这为循环优化提供了良好的基础 。 即使有相同入口结点而且不嵌套,我们也可以将它们合并看成是一个循环 。
35
五,深度优先搜索对流图的深度优先搜索,是对树的深度优先遍历的推广 。 它产 生 深 度 优 先 次 序 和 深 度 优 先 扩 展 树 DFST(depth fist
spanning tree),深度优先次序对提高流图中的很多迭代算法
（ 如 § 7.3,求必经结点集及 § 7.4解数据流方程 ） 的速度有利,
深度优先扩展树对于找回边则可算另辟蹊径 。
所谓深度优先的搜索,是指从首结点开始尽量往通路深处搜索新结点,直到搜索不到新结点时才退回到前驱结点,再由前驱结点沿着另一可能的通路再作这样的搜索,直至退回到首结点而没有新结点可搜索时止 。
在作深度优先搜索时,从首结点开始,当搜索到新结点时就画一条有向边,随着深度优先搜索,这些有向边依次构成一棵树,这便是深度优先扩展树 dfst。
结点的深度优先次序是前序遍历深度优先扩展树时最后访问结点次序的逆序 。
36
到 9，回到 7，回到 6才找另一通路上有新结点 8，再由 8回到 6，
5,4,2，又找到另一通路上的新结点 3，然后又退回 2,1。
其完整次序为：扩展树的前序遍历 1?2?4?5?6?7?9?10，
然后由 10回到 9，回到 7，回到 6才找另一通路上有新结点 8，
再由 8回到 6,5,4,2，又找到另一通路上的新结点 3，然后又退回 2,1。其完整次序为：
1 · 2 · 4 · 5 · 6 · 7 · 9 · 10 · 9 · 7 · 6 · 8 · 6 · 5 · 4 · 2 · 3 · 2 · 1
最后访问的结点由下划线给出了标记,其逆序为：
1,2,3,4,5,6,8,7,9,10，这便是结点的深度优先次序。
9
1
2
34
5
6
7 8
10
图 7.16深度优先扩展树
37
在流图的结点表中可以增加结点的深度优先次序的项目 DFN,DFN(n)就记录着结点 n的深度优先次序的值 。
构造深度优先的扩展树,计算各结点的深度优先次序的算法如图 7.17所示 。 算法首先对所有结点给了未访问标记,然后由首结点 n0 开始调用递归过程
search(n0)。
在调用 search(n)时，先将 n标记改为已访问，表示 n
已非新结点，如果 n的后继结点 S(n)中有标记为未访问的新结点 s，则将有向边 n?s加入到扩展树中，如果已没有这种新结点作为后继结点，则便可将 i作结点 n的深度优先次序，然后 i递减 1。 DFN[n]是深度为主的次序的值。在流图的结点表中可以增加结点的深度优先次序的项目 DFN,DFN(n)就记录着结点 n的深度优先次序的值。
38
构造深度优先的扩展树,计算各结点的深度优先次序的算法如图 7.17所示 。 算法首先对所有结点给了未访问标记,然后由首结点 n0 开始调用递归过程
search(n0)。
在调用 search(n)时，先将 n标记改为已访问，表示 n
已非新结点，如果 n的后继结点 S(n)中有标记为未访问的新结点 s，则将有向边 n?s加入到扩展树中，如果已没有这种新结点作为后继结点，则便可将 i作结点 n的深度优先次序，然后 i递减 1。 DFN[n]是深度为主的次序的值。
39
主程序为：
T=empty；
for(n?N)
{将 n标记为,未访问,； }
i=|N|；
search(n0)；
递归过程为：
void search(n)；
{ 将 n标记为,已访问,；
for(s?S(n))
{ if(s标记为,未访问,)
{将有向边 n?s加到 T中； search(s)； }
DFN[n]=i；
i=i-1；
}
}
图 7.17 构造深度优先扩展树，求深度优先次序的算法
40
§ 7.4 数据流分析控制流分析确定了程序流图及其结构,特别是循环 。
优化需要对数据流作出分析,程序中的变量或者是以赋值或读入这类定值方式出现,或者是以引用方式出现,数据流分析就是分析程序中所有变量的定值和引用之间的关系 。 这一节我们将讨论几类数据流分析及其在代码优化中的应用 。
在数据流分析时,一个语句如果对变量 x定值,则这 一个语句的位置 d称为变量 x的一个定值点；如果一个语句中有对变量 y的引用,则这个语句的位置 u称为变量 y的一个引用点 。 例如在 p处有语句 x:=y op
z(通常写为 p:x:=y or z),则 p是 x的定值点,是 y和 z的引用点 。
变量 x在 d点的定值到达 u点，是指流图中有一条通路 d?u，而在这条通路上没有 x的其他定值点。
41
一,到达一定值数据流方程和 ud链循环优化时,常常要判别循环不变量和循环不变运算 。 循环不变量是指循环中没有这个变量的定值点 。
循环不变运算 x:=y op z,是指参与运算的 y及 z只能是常数或循环不变量 。 y及 z在循环中没有定值点,也就是 y及 z的定值点全在循环外,因此循环不变运算可以外提到循环外而不在循环中重复执行了,这就是一种重要的循环优化 —— 外码外提 。
如果在 u点引用一个变量 y时,能知道它是在何处定值的,那么我们就可以判定它是否在循环外定值,即可以判定它是否是循环不变量了 。 但如何知道变量 y
到达引用点 u的所有定值点呢？ 为此引进下列定义：
42
定义 7.6 ud链 。 能到达 u点的变量 y的所有定值点的集合称为 y在引用点 u处的引用一定值链,简称称 ud
链 。
因此,只要知道变量 y在引用点 u处的 ud链,我们就可知道 u点的 y是在何处定值的,因而能判定它是否是循环不变量了 。
如何求得变量 y在 u点的 ud链呢？ 为此引进下列定义
43
定义 7.7 IN[B]。 能到达恰在基本块 B入口之前处的各个变量的所有定值点的集合 。
如果能求得流图中每个基本块的 IN[B],则在基本块 B中 u点处变量 y的 ud链便可按下列规则建立：
(1)如果在 B中 u点之前有 y的定值点 d,且这个定值能到达 u,则 u点处 y的 ud的链为 {d}。
(2) 如果在 B中 u点之前没有 y的定值,则 IN[B]中关于 y
变量的每个定值点都能到达 u,所以 u点处 y的 ud链为
IN[B]中关于 y的定值点集,它是 IN[B]的一个子集 。
44
因此为了求 ud链,必须求每个基本块的 IN[B],为了求 IN[B]引进下列定义：
定义 7.8 OUT[B]:能到达恰在基本块 B出口之后处的各个变量的所有定值点的集合 。 如果能求得流图中每个基本块的 OUT[B],能到基本块 B入口之前的所有变量的定值点的全体 (即 IN[B])当然是 B的所有前驱结点 p的 OUT[p]的并集即,
IN[B]=?OUT (p)
p?P(B)
其中 P(B)为 B的前驱结点集,显然如果能求得流图中每个基本块的 OUT[B],则 IN[B]自然也是容易求的 。
45
因此为了求 ud链,必须求每个基本块的 IN[B],为了求 IN[B]引进下列定义：
为了求 OUT[B],还需引入下列定义：
定义 7.9 GEN[B]在基本块 B中定值并能到达 B的出口之后的所有的定值点的集合 。
定义 7.10 KILL[B]。 在基本块 B外定值而所定值的变量在 B中又重新被定值的那些定值点的集合 。 也即由于在 B中重新定值,而使得在 B外的定值在 B中因此被注销的那些定值点集 。
46
能到达基本块 B出口之后的定值点有两种可能,一种可能是 B中定值并能到达 B的出口之后的那些定值点集即 GEN [B]；另一种可能则是 IN[B]中定值点集而又未被 B中的定值所注销的定值点 IN[B]- KILL[B]，
它也能到达 OUT[B],故有：
OUT[B]= GEN [B]∪ (IN[B]- KILL[B]) (7.3)
47
基本块内定值并能到达基本块出口之后的定值点集即 GEN [B]是可以由流图求出而作为已知量的,基本块外定值而又因基本块内定值而被注销的定值点集即
KILL[B]也是可以由流图求出而作为已知量的,因此有,IN[B]=?OUT [p]
p?P(B) (7.4)
OUT[B]= GEN [B]∪ (IN[B]- KILL[B])
如果流图有 n个基本块,则 (7.4)为 2n个变量 (n个
IN[B],n个 OUT[B])的 2n个方程的线性联立方程组 。
在给出初值 OUT[B]= GEN [B],IN[B]=?后用迭代法不难求解,然后利用求得的 IN[B]可在每个引用点为引用变量建立 ud链作为代码优化的信息 。
(7.4)称为到达一定值数据流方程 。
48
数据流方程的求解,
到达一定值数据方程 (7.4)可用下述方法求解：
可 以 用 迭 代 法 求 值 。 由于 IN[B],OUT[B],
GEN[B],KILL[B],都是全集的某个子集,设全集
|U|=m,则可用 m位的位向量来表示这些子集 。
方程 (7.4)依赖于前驱结点,迭代可按深度为主次序,
由前向后进行 。
方程 (7.4) 是与前驱或后继的并集有关,迭代初值空集?。
GEN[B],KILL[B],根据各自的定义都可由流图直接求出,它们直接影响着迭代结果 。
前后两次迭代结果相同时,便得到了解 。
49
(1)[例 7.12] 对图 7.18给出的流图,求解基本块入口之前定值点集 。 只考虑变量 I,J,流图中只关心 5个定值点即 d1… d5,基本块 B5中没有 I,J的定值点,故设位向量长度为 5,各基本块的 GEN[B],KILL[B],列于图
7.19,OUT[B]的初值取 GEN[B]，
IN[B]的初值取空集?,对每个基本块
B求 IN[B],OUT[B]。 求解按深度为主次序 B1,B2,… B5依次进行,各次迭代列于图 7.19的表中,第四次代迭代结果与第三次相同,认为已收敛 。
d1,I:=1
d2,J:=I+2
d3,I:=2
d4,J:=J-1
d5,J:=J+4
:= I
:= J B5
B4
B3
B2
B1
图 7.18 例 7.12的流图
50
基本块 KILL GEN 第一次 第二次 第三次 第四次
[B] [B] IN[B] OUT[B] IN[B] OUT[B] IN[B] OUT[B] IN[B] OUT[B]
B1 00111 11000 00100 11000 01100 11000 01111 11000 01111 11000
B2 10000 00100 11000 01100 11111 01111 11111 01111 11111 01111
B3 01001 00010 01100 00110 01111 00110 01111 00110 01111 00110
B4 01010 00001 00110 00101 00110 00101 00110 00101 00110 00101
B5 00000 00000 00111 00111 00111 00111 00111 00111 00111 00111
图 7.19 到达一定值数据流方程的求解过程
d1,I:=1
d2,J:=I+2
d3,I:=2
d4,J:=J-1
d5,J:=J+4
:= I
:= J
B5
B4
B3
B2
B1
图 7.18 例 7.12的流图
51
§ 7.5循环优化非局部优化是在结构分析和数据流分析基础上进行的，一般先作循环优化，有代码外提、强度削弱和删除归纳变量，然后作全局优化，主要是常数传播，合并已知量，删除公共子表达式及复写传播等。从优化效果看，循环优化特别是内层循环的优化最为显著。
为了描述循环优化，给出下列例子。
一、循环优化的例子若有一循环语句,for i:=1 to 10 do a[i,2*j]:=a[i,
2*j]+1；根据第五章讨论的思想可以生成图 7.20的中间代码，相应流图如图 7.21所示。
52
(1) i:=1
(2) if i>10 goto(16)
(3) t1=2*j
(4) t2=10*i
(5) t3=t2+t1
(6) t4=a0-11
(7) t5=2*j
(8) t6=10*i
(9) t7=t6+t5
(10) t8=a0-11
(11) t9:=t8[t7]
(12) t10:=t9+1
(13) t4[t3]:=t10
(14) i:=i+1
(15) goto (2)
(16)…
(3) t1=2*j
(4) t2=10*i
(5) t3=t2+t1
(6) t4=a0-11
(7) t5=2*j
(8) t6=10*i
(9) t7=t6+t5
(10) t8=a0-11
(11) t9:=t8[t7]
(12) t10:=t9+1
(13) t4[t3]:=t10
(14) i:=i+1
(15) goto (2)
(1) i:=1
(2) if i>10 goto(16)
(16)…
图 7.20 循环语句的中间代码 图 7.21 相应的流图
53
二、代码外提
1,循环不变运算。
循环 L中如 x:=y 。 op z一类计算，如果 y与 z是常数或者其定值点均在循环 L之外，则该计算称为循环不变运算，它在循环中每次都运算的结果是相同的，因此它其实不必在循环中每次运算，只要将它提到循环外某个恰当位置上作一次运算即可，这便是循环不变运算的代码外提，其优化效果是十分明显的。要判断循环不变运算并不困难，这只要看 y及 z是否都是常数，或者由该点的 ud链可查知 y或 z的定值点在 L之外。
54
2,前置结点。
将循环不变运算外提到循环外什么地方才适当呢？显然最适当的地方是在循环外即将进入循环的地方，即恰在循环的入口结点之前处。不难发现，我们所定义的循环强调有唯一入口结点，将保证代码外提的唯一性为保证代码外提点既在循环入口结点之前，又不在循环之中，因此在循环入口结点之前设置一前置结点，
从前置结点向入口结点引一有向边，原循环外引向入口结点的有向边改为引向前置结点，循环内引向入口结点的有向边则不变，经过上述变换后循环不变运算代码便可外提到前置结点中，
55
循环不变运算的查找算法：
(1)对循环 L中各基本块满足下列条件的语句作不变运算的标记：语句的每个运算对象，或为常数，或定值点在 L外 (这由 ud链可确定 )。
(2)依次查看未标记为“不变运算”的语句，如果它的每个运算对象或为常数，或定值点在 L外，或唯一能到达的定值点已被标记为“不变运算”，则将该语句也标记为“不变运算”。
(3) 重复 (2)。直至没有新的语句被标记为“不变运算”
时为止。
56
代码外提算法：
(1) 寻找循环 L中所有不变运算。
(2) 对每一不变运算 P,x:=y op z或 x:=op y或 x:=y，如果它满足下述两组条件中的一组
P点所在基本块是 L所有出口结点之必经结点；
x在 L中没有其他定值点；
L中引用 x处只有 P点的定值才能到达。
x在出 L之后不再活跃；
x在 L中没有其他定值点；
L中引用 x处只有 P点的定值才能到达。
则将满足条件的不变运算，按查找不变运算次序，依次外提到 L的前置结点中。
57
三、归纳变量定义 7.18
(1) 循环 L中变量有唯一的定值 i:=i± c，其中 c为常量，
则称 i为循环 L中的基本归纳变量。
(2) 循环 L中如果变量 j的定值均为 j:=c1*i± c2形式，
其 I为循环的基本归纳变量,c1,c2为循环不变量，则称 j为 i同族的归纳变量。
图 7.26中，变量 i只有语句 (14)为唯一的定值 i:=i+1，
故 i为基本归纳变量，此外
t2=10*i
t3=t2+t1=10*i+t1
t6=10*i
t7=t6+t5=10*i+t5
t1,t5均为循环不变量，故 t2,t3,t6,t7均为 i同族的归纳变量
58
四、强度削弱与基本归纳变量同族的归纳变量在循环中将随着基本归纳变量的变化而发生线性变化，相应计算代码中涉及的乘法和加法，
可依据变化规律变换成执行时间短的代码来代替，这当然也是一种优化，称为强度削弱。由于数组和循环在程序中被普遍作用，在以循环变量作为基本归纳变量的下标变量的地址计算中涉及这类线性函数的计算相当多，因此强度削弱的优化效果是不容忽视的。
图 7.26中 i为基本归纳变量，由语句 (14)，每循环一次,i增 1，
而 t2,t6是 i的线性函数,i增 1时,t2,t6分别增加 10，如果将语句 (4),(8)外提到 B2?中作为 t2,t6初始定值，而在语句 (14)后随递归增 1,t2,t6递归增 10，则程序的这种变换是等价的，如图
7.27(a)所示。但循环中二处乘法转换成二处加法，执行强度有了明显的削弱。
将乘法运算转换成加法类运算是一种强度削弱，将变通加法转换成变址器加法，同样可提高运算速度，因此对递归增加 10
的 t3,t7也可作类似的变换，如图 7.27(b)所示。
59
五、删除归纳变量基本归纳变量除了自身的递归定值外，往往只是作为循环控制和参于其他同族归纳变量的计算，在强度削弱后，其他同族归纳变量在循环中的运算因已转换成递归增加一个常量而已与基本归纳变量没有直接关系了，如图 7.27(b)中的 (4)(8)(5)(9)，因此只要将循环控制条件由依赖于基本归纳变量 i转换成依赖于它的同族归纳变量，此时基本归纳变量除了唯一的递归定值外，
已别无用处，因而可予删除。
图 7.27中由语句 (2)来实现循环控制，与 i同族的归纳变量为 t3，
t7，以 t3为例，它与 i的线性关系为 t3=10*i+t1,i终值为 10，此时
t3终值应为 100＋ t1，因此 i>10与 t3>100+t1应是等价的，语句 (2)
可变换为：
(2’) S:=100+t1
(2”) if t3>S goto
其中 (2’)是一循环不变运算，可外提至前置结点 B2?中，此时语句 (14)可删除，故有图 7.28。
在变换循环控制条件时，应选择循环中还要引用的或循环出口之后活跃的，当然与 i的线性函数关系应越简越好。
60
综上所述,强度削弱和删除归纳变量算法可描述如下：
(1) 寻找循环中的所有基本归纳变量 i。
(2) 寻找与基本归纳变量同族的归纳变量 j及其线性函数,通常它们具有下列形式：
j:=c*i,j:=i*c,j:=i/c,j:=i± c,j:=c± i。
(3) 设归纳变量 j与基本归纳变量 i的函数为 j=c1*i+c2,可按下列步骤作强度削弱：
在前置结点原有代码后增加
s:=c1*i
s:=s+c2
其中 s为增设的临时变量,c2=0时,后一语句可省略；
循环中原来 j的赋值改为 j:=s；
在基本归纳变量递归赋值语句 i:= i± c0后增加
t:=c1*c0
s:=s± t
其中 t为增设的临时变量 。
61
(4) 上述复写 j:=s至循环中引用 j处的通路上没有对 s的重新定值,
j在循环出口后不活跃,则作复写传播,即删除 j:=s,所有引用 j
处改为引用 。
(5) 基本归纳变量 i在循环出口后不活跃,循环中除递归赋值本身外,只在形如 if i rop x goto A或 if x rop i goto A控制语句中被引用,则按下列步骤删除归纳变量 。
选一与 i同族的归纳变量 j,使 j=c1*i+c2的函数应最简单,j在循环出口之后是活跃的,或 j在循环中还有其他引用；
用下列语句
x?:=c1*x
x?:= x?+c2
if j rop x? goto A(或 if x? rop j goto A)
来代替 if i rop x goto A(或 if x rop i goto A)；
删除循环中 i的递归赋值语句,i:=i± c。
编译原理第七章 代码优化上海交通大学张冬茉
Email:zhang-dm@cs.sjtu.edu.cn
2004年 6月
2
本章目的代码优化是从生成的目标代码中识别出那些可以经过变换而提高效率的部分,并实施这种变换 。 这种优化并不是极值理论中的那种求极值点的优化,它只追求变换后的代码要比变换前的效率要高些 。
3
第七章 代码优化
§ 7.1 优化概述一,优化定义优化是一种等价、有效的程序变换。等价是指不改变程序运行结果，即对变换前后的程序给以相同的输入，
应有相同的输出，即变换是安全的。
而有效是指经变换后的程序与变换前的程序相比运行速度更快，所占空间更少，也即所谓时空效益要高。
时间短空间省，这两个要求可以是相容的，并行不悖的。数据不相关的两个循环，经循环合并构成一个循环，循环控制的开销节省了，代码长度也因此缩短了。
但有时，时间短空间省的要求可能会不可兼得，这时就有牺牲时间换取空间或牺牲空间换取时间两种策略，
需要有个综合分析和实事求是的取舍。
4
二、不同阶段的优化
(1)优化可以在源程序阶段也可以在编译阶段进行
(2)编译优化又可分成两个阶段，即中间代码优化与目标代码优化,编译优化工作中有一部分与目标机有关，有效而合理地使用机器资源便是目标代码优化阶段要实现的
(3) 中间代码的优化有局部化与非局部优化之分。局部优化是指基本块内的优化，非局部优化是指超越基本块的优化，因此对中间代码划分基本块，是优化所必需的。
(4) 非局部优化也有循环优化与全书局优化之分，将中间代码以基本块为结点，构造出程序流图，从中识别出循环结构
5
优化源程序优化编译优化中间代码优化目标代码优化非局部优化局部优化循环优化 全局优化图 7.1 在各个阶段的优化
6
三、程序流图的构造程序流图是程序的图形表示。我们把有唯一首结点
n0的有向图 G称为控制流程图。首结点 n0是到图中任何结点 n都有道路 n0?n的一个特殊的结点。
因此控制流程图是一个三元组 G=(N,E,n0)，
其中 N为结点集 (包括 n0),E为有向边集。通常将控制流程图简称为流图，或程序流图。对一个程序流图来说，结点代表计算，有向边代表控制流，
而首结点是程序起始位置所在的结点 (基本块 )。
1,基本块基本块是程序语句序列中满足下列条件的长度最长的子序列：这个语句子序列是顺序执行的；它只有一个入口即子序列的第一语句；只有一个出口即子序列的最后一个语句。停止语句和转向 (分支 )语句只可能是基本块的最末一个语句。
7
2,划分基本块的算法输入：三地址语句序列。
输出：基本块表。每个三地址语句，仅在一个基本块中。方法：
(1) 首先确定各个基本块的第一个语句即入口语句。
规则是：程序的第一个语句。
能由条件或无条件转移语句转移到的语句。
紧跟在条件转移语句后的那个语句。
(2) 由每个入口语句构造所在的基本块：①由一入口语句到转移或停止语句 (含转移或停止语句 )之间的语句序列。②由一入口语句到下一入口语句 (不含下一入口语句 )之间的语句序列。
(3) 凡未被归入基本块的语句，为程序控制流图不能到达的语句，因此为不可能执行的语句，故可从程序中删除。
8
3,构造流图的算法输入：划分基本块算法输出的基本块表输出：程序流图 G=(N,E,n0)
方法：
(1) 输入的基本块集即为 N。
(2) 含有程序第一个语句的基本块为首结点 n0。
(3) 对 N中任两个结点 (基本块 )Bi和 Bj如果 Bj紧跟在 Bi
之后，且 Bi的出口语句不是无条件转移或停止语句；
或 Bi的出口语句是转移语句，其转向点为 Bj的第一个语句。则结点 Bi和 Bj之间有一有向边 Bi?Bj。这些有向边的集合为 E。
9
§ 7.2 局部优化一、基本块内的优化局部优化是基本块内的优化，通常有：
1,合并已知量对于 A:=op B或 A:=B op C，其中 B及 C均为常数，则编译时即可计算出 op B或 B op C的值，作为 A的值，
而不必生成相应的代码。
2,删除公共子表达式也称为删除多余运算。如图 7.3的基本块 B5中，语句
(14),(16)计算相同的 4*I称为公共子表达式，在
(14)t6:=4*i计算后 (16)处只需将 t6的值复写给 t7即
t7:=t6就可以了。语句 (17),(20)也有公共子表达式 4*j，
故语句 (20)可变换成 t10:=t8，这样就避免了多余运算。
10
3,删除死代码死代码有两种情况：
(1) 在分支程序中，测试语句取固定值，如取 ture，则
false分支的代码是死代码。这种情况下删除死代码不可能局限在基本块内。
(2) 变量 A被定值后不再被引用，或者仅有的定值与引用为 A:=A+C的递归赋值形式，则该定值语句是死代码，称为无用赋值。例如基本块 B5中删除公共子表达式后 t7,t6有相同的值，故对 t7的引用可由 t6来代替，
同样对 t10的引用也可由 t8来代替。故语句 (19)可转换成 a[t6]:=t9，语句 (21)可转换成 a[t8]:=x。如果 t7,t10
出了基本块 B5后也不活跃 (即不再被引用 )，则 (16)的
t7:=t6和 (20)的 t10:=t8便成为无用赋值。在基本块范围内，变量 A在定值后未经引用又发生了对 A的第二次定值，则前一定值为无用赋值。
11
二、基本块的 dag表示可以用一个无环路有向 dag(directed acyclic graph)来表示一个基本,dag是实现基本块内优化变换的有效表示，可以决定基本块内的公共子表达式，并删除那些死代码；可以决定在基本块外定值而在基本块内被引用的变量名字；可以决定基本块内哪些变量名字的定值可以在基本块外被引用。
为了描述计算过程，我们在无环路有向图的结点上给出如下标记或附加标记：
12
(1) 图的叶结点用标识符 (标识变量名 )或常数作为唯一标记，表示该结点代表所标记的变量或常数的值。至于是变量的左一值还是右一值，可由作用于变量名的算符决定，通常为右一值。叶结点代表变量的初值，
加下标 0，以示区别。
(2) 图的内部结点用运算符 op作为标记，该结点的后继结点所代表的值，为参于运算的分量，因此该内部结点表示由它的后继结点代表的运算分量经 op运算后的表达式的结果。
(3) 图中各结点可能附加一个或多个标识符作为附加标记，表示这些附加的标记标识符具有该结点所代表的相同的值。
上述无环路有向图称为描述计算过程的 dag，简称为
dag.
13
三,dag的构造基本块的 dag是通过依次处理它的每一个语句而建立起来的，
这里所说的语句是指的三地址代码。通常的语句形式及它们所对应的 dag表示如图 7.5所示：
如果待处理的语句形如 x:=y op z，其处理的步骤为：
(1) 在已建立的 dag了图中寻找能代表 y,z当前值的结点。
(2) 若代表 y,z当前值的结点至少有一个标记为非常数，则执行步骤 (3)，否则执行下列步骤：
执行 y op z，令其结果常数为 x0。
如果,y或 z是执行当前语句 x:=y op z时新建立的结点，则删除它。
如果已建立的 dag子图中没有标记为 x0的常数叶结点，则建立新的结点 n，它的标记为 x0。
如果已建立的子图有标记为 x0的叶结点，则令该结点为 n。
执行步骤 (4)
14
(3) 在已建立的 dag子图中寻找这样的结点：它标记为 op，它的左子结点为代表 y当前值的结点它的右子结点为代表 z当前值的结点。也有两种可能：
已建立的 dag子图中寻找这样的结点：它标记为 op，它的左子结点为代表 y当前值的结点，它的右子结点为代表 z当前值的结点。也有两种可能：
在已建立的 dag子图中没有这样的结点，则建立一新的内部结
n，它以代表 y,z当前值的结点作为它的左右子结点，令它标记为 op。
在已建立的子图中存在这样的结点，不妨令它为 n。
(4) 对于在步骤 (2)或 (3)中找到的或新建立的结点 n，应将 x加入到该结点的附加标记集中，但在此之前如果 x(不是 x0)已出现在某个结点的附加标记集中，则应先将 x从这个附加标记集中删除。这表明此时 x已重新定值,x的当前值已不是原来的那个 x
了。
(5) 处理下一语句，直至结束。
15
[例 7.3] 与下列基本块相应的 dag的构造过程如图 7.6。
pi:=3.14
t1:=2*pi
t2:=R+r
A:=t1*t2
t3:=2*pi
t4:=R+r
t5:=t2*t4
t6:=R-r
t7:=t5*t6
A:=t7-A
16
n1 n1 n2n1n2 n3 n4
n5
+
t1
t2
pipi t1pi
3.14 3.14 6.28 3.14 6.28 R r
(a) (b) (c)
n2n1 n3 n4
n5
+
t1
t2
pi
3.14 6.28 R r
(d)
n6 A
*
n2n1 n3 n4
n5
+
t1,t3
t2
pi
3.14 6.28 R r
(e)
n6 A
*
n2n1 n3 n4
n5
+
t1,t3
t2,t4
pi
3.14 6.28 R r
(f)
n6 A
*
n2n1 n3 n4
n5
+
t1,t3
t2,t4
pi
3.14 6.28 R r
(g)
n6 A,t5
*
n2n1 n3 n4
n5 +
t1,t3
t2,t4
pi
3.14 6.28 R r
(h)
n6 A,t5
*
n7 t6-
17
n2n1 n3 n4
n5
+
t1,t3
t2,t4
pi
3.14 6.28 R r
(h)
n6 A,t5
*
n7 t6
-
n8
*
t7
n2n1 n3 n4
n5
+
t1,t3
t2,t4
pi
3.14 6.28 R r
(g)
n6 A,t5
*
n7 t6
-
n8
*
t7
n9
-
A
图 7.6 dag的构造过程
18
四,dag实现的优化从上述构造 dag的步骤及例 7.3中不难发现：
dag构造时已实现了如下优化：
1,合并已知量步骤 (2)对公共子表达式并不生成标记该运算的内部结点，而是执行运算，由结果常数参与构造 dag，实现了编译时合并已知量的优化。
2,删除多余运算步骤 (3)对公共子表达式并不生成重复的结点，
只是在结点的附加标记集中增加被赋值变量名 。
19
3,删除死代码步骤 (4)，在将 x附加到结点 n上之前，删除已出现在某个结点的附加标记集中的 x，那些定值后未被引用即被重新定值的 x，因 x的删除而成为死代码，其前一次的定值被删除。
此外，从 dag还可知道：
(1) 作为 dag叶结点标记的标识符，是在此之前的基本块内被定值并在本基本块内被引用的变量名。
(2) 作为 dag各结点附加标记的标识符是在基本块内定值并可以在基本块内和基本块后被引用的变量名，
如果确认某结点的一个附加标记在基本块后不会被引用 (称为不活跃 )，则该标识符的定值语句可作为死代码被删除。
20
[例 7.4] 如果例 7.3的 dag按结点建立次序重构基本块，则可得到经上述优化后的基本块。
pi:=3.14
t1:=6.28
t3:=6.28
t2:=R+r
t4:=t2
t5:=6.28*t2
t6:=R-r
t7:=t5*t6
A:=t7-t5
如果 pi及 t1-t7出基本块不活跃 (它们只是在计算表达式时使用的临时变量 )，则重构的基本块可进一步优化为：
S1:=R+r
S2:=6.28*S1
S3:=R-r
S4:=S2*S3
A:=S4-S2
21
§ 7.3 控制流分析及循环的查找循环是指程序中可能反复执行的代码序列。循环并不一定都是由程序语言中的循环语句形成的，事实上，
在中间代码级，除了对程序单元调用 (Call)和返回
(Return)语句外，均由条件转移和无条件转移语句形成了各种控制语句。因此，首先应对循环给出定义，
然后设法从程序中找出符合定义的循环，这需要对程序流图作控制流分析，并在这基础上作数据流分析，
最后，在数据流分析基础上，做循环优化和全局优化。
22
一、循环的定义定义 7.1 循环是程序流图中有唯一入口结点的强通的子图。 12345678910图 7.9 例 7.5的流图
(1) 入口结点是指子图中有下列性质的结点 n,n是流图的首结点，或者子图外有结 m，它有一有向边
m?n引向结点 n。
(2) 强连通子图：子图中任两个结 m,n之间互相可达，即 m至 n及 n至 m均有通路 (用表示 )，且通路上的结点均属于该子图。如果子图只含一个结点，则该结点应有一有向边引向该结点自身 (自环路 )。
循环要求强连通是很自然的，要求入口结点唯一是由于循环优先中需要将循环不变运算提到循环之外
(代码外提 )入口前的一个确定地点，这就要求入口结点是唯一的。
23
[例 7.5] 图 7.9给出了程序流图。
由结点序列 {5,6,7,8,9}组成的子图是强连通的，仅有的入口结点是 5。
由结点序列 {4,5}组成的子图是强连通的，但 4,5均为子图的入口结点，所以这子图不是循环。
由结点序列 {2,4}组成的子图不是强通的,4与 2之间虽有通路
4?10?2但通路上的 10不在子图中。
1
2
3
4
5
6
7 8
9
10
图 7.9 例 7.5的流图
24
二、必经结点集例 7.5告诉我们，必须给出一种方法来查找流图中的循环。首先得分析流图中结点间的控制关系。
定义 7.2 从流图的首结点出发到达结点 n的任一通路都必需经过结点 d，则称 d是 n的必经结点，记为 d
DOM n。
25
根据定义，容易看出：
(1) 每个结点是它本身的必经结点，即 n DOM n。
(2) 流图的首结点 n0，是流图中任一结点 n的必经结点,n0 DOM n。
(3) 循环 L的入口结点 d，是循环内任一结点的必经结点。如果 d不是首结点 n0，即 n0?L,n0在循环外，
则由 n0到循环中任一结点 n的任一通路，必经过 d而进入循环，故 d是 n的必经结点。
(4) 一个结点的必经结点可能不止一个，如对循环内除入口结点 n而言，它至少有三个必经结点：首结点 n0，循环入口结点 d，及结点 n自身。我们将流图中结点 n的所有必经结点称为 n的必经结点集，用 D(n)
表示。
26
如果将 DOM看成结点集 N上的一种二元关系，那么它具如下性质：
(1) 自反性。对任一 n?N,n DOM n；
(2) 反对称性。若 m,n?N,m DOM n且 n DOM n
则必有 m=n；
(3) 传递性。若 l,m,n?N，而 1 DOM m且 m DOM
n，则必有 1 DOM n.
因此,DOM是结点集 N上的一个偏序关系。
对于偏序关系，我们首先可得到 cover集,cover集中的 <d,n>，称 d是 n的直接必经结点，由 cover集得到描述偏序关系的哈斯图，是流图的必经结点树。
27
1
2
3
4
5
6
7 8
9
10
{1}
{1,2}
{1,2,3}
{1,2,4}
{1,2,4,5}
{1,2,4,5,6}
{1,2,4,5,6,7} {1,2,4,5,6,8}
{1,2,4,5,6,9}
{1,2,4,10}
图 7.10 图 7.9的必经结点集
1
2
4
10
3
5
6
7 8 9
图 7.11 图 7.9的必经结点树
28
这是迭代求解过程，其初值除首结点 D(n0)=n{0}外，
其余结点 n,D(n)=N。每次迭代中如果有一个结点 n
的新才 D(n)不相同，表明迭代未收敛，这由布尔变量
change来标志。集合可用位向量表示，此时集合运算
∪,∩ 就可用?,?来代替了。
D(n0)={n0}；
for(n?N-{n0})
{ D(n)=N； }
chang=true；
while(change)
{change=false； }
for(n?N-{n0})
{new={n}∪ D(p)； p?P(n)；
if (new != D(n))
{change=true； D(n)=new； }}
图 7.12 求必经结点集 D(n)的算法
29
三、自然循环循环 Loop是流图中有唯一入口结点 d的强连通子图，
它有这样两个性质：
(1) 这个入口结点 d必是循环中各结点的必经结点，
因为对任一 n?Loop，如果 d DOM n，则从首结点 n0，
必有一通路 n0?n，而这通路不经过 d，这就意味着循环外的结点可以不通过 d而进入循环，这与 d是唯一入口结点是矛盾的。
(2) 要使 Loop 中所有结点都有可能重复执行，则循环中至少有一条边回到 d，否则不可能强连通。
因此寻找循环，首先要找回边。
定义 7.3 流图 G=(N,E,n0)中的有向边 n?d，如果 d
DOM n，即 d?D(n)，则称 n?d为流图的回边。
30
主程序,stack=empty；
loop={d}；
insert(n)；
while(stack 非空 )
{上托 stack栈顶元素 m；
for(p?P(m))
{ insert(p)； }
}
过程,void insert(m)
{ if (m?loop) { loop=loopU{m}；
下推 m入栈 stack； }
}
图 7.13 构造由回边组成的循环的算法
31
[例 7.7] 图 7.9的流图，其必经结点已如图 7.10所示，
它有如下四条回边：
5?4，因 4?D(5)={1,2,4,5}
9?5，因 5?D(9)={1,2,4,5,6,9}
10?2，因 2?D(10)={1,2,4,10}
7?7,7?D(7)
定义 7.4 若 n?d是流图 G=(N,E,n0)的一条回边,M
是流图中有通路到达 n而该通路不经过 d 的结点集，
则 Loop={n,d} M，构成了 G的一个子图，称为由回边 n?d组成的自然循环。
32
四,可归约流图我们讨论的循环是一个自然循环,它是由回边为基础组成强连通的从而是可反复执行的子图,而且入口结点是唯一的 。 是不是所有可反复执行的代码都有这种性质呢？ 事实上,由回边构成的自然循环只是广义上的循环中的一类,
它们有这样的特点,删除了流图中的回边后,
成为一个无环路有向图 。
33
[例 7.9] 图 7.5的流图,删除了回边后如图 7.14所示,这是个无环路有向图 。
定义 7.5 一个流图删去了回边后的子图是个无环路的有向图，
则这个流图称为可归约流图。
[例 7.10] 图 7.15给出了最简单的不可归约流图，子图 {2,3}是可以重复执行的代码，但 2?3,3?2不是回边，结点 2,3都是这个广义循环的入口结点。
1
2
3
4
5
6
7 8
9
10
图 7.14 图 7.5删除了回边后无环路流图
1
2 3
图 7.15 不可归约流图
34
可归约流图是非常重要的流图,这是由于：
(1) 只由结构化控制语句构成的结构化程序,其流图总是可归约的,即使使用 goto语句的程序,几乎也都是可归约的 。
(2) 找出回边及由回边组成的自然循环,这类控制流的分析是容易实现的 。
(3) 对自然循环而言不存在循环外向循环内的转移,
进入循环必需通过入口结点 。 对两个循环来说,如果不是有相同的入口结点,那么它们要么是嵌套 (完全包含 ),要么是互不相交,这为循环优化提供了良好的基础 。 即使有相同入口结点而且不嵌套,我们也可以将它们合并看成是一个循环 。
35
五,深度优先搜索对流图的深度优先搜索,是对树的深度优先遍历的推广 。 它产 生 深 度 优 先 次 序 和 深 度 优 先 扩 展 树 DFST(depth fist
spanning tree),深度优先次序对提高流图中的很多迭代算法
（ 如 § 7.3,求必经结点集及 § 7.4解数据流方程 ） 的速度有利,
深度优先扩展树对于找回边则可算另辟蹊径 。
所谓深度优先的搜索,是指从首结点开始尽量往通路深处搜索新结点,直到搜索不到新结点时才退回到前驱结点,再由前驱结点沿着另一可能的通路再作这样的搜索,直至退回到首结点而没有新结点可搜索时止 。
在作深度优先搜索时,从首结点开始,当搜索到新结点时就画一条有向边,随着深度优先搜索,这些有向边依次构成一棵树,这便是深度优先扩展树 dfst。
结点的深度优先次序是前序遍历深度优先扩展树时最后访问结点次序的逆序 。
36
到 9，回到 7，回到 6才找另一通路上有新结点 8，再由 8回到 6，
5,4,2，又找到另一通路上的新结点 3，然后又退回 2,1。
其完整次序为：扩展树的前序遍历 1?2?4?5?6?7?9?10，
然后由 10回到 9，回到 7，回到 6才找另一通路上有新结点 8，
再由 8回到 6,5,4,2，又找到另一通路上的新结点 3，然后又退回 2,1。其完整次序为：
1 · 2 · 4 · 5 · 6 · 7 · 9 · 10 · 9 · 7 · 6 · 8 · 6 · 5 · 4 · 2 · 3 · 2 · 1
最后访问的结点由下划线给出了标记,其逆序为：
1,2,3,4,5,6,8,7,9,10，这便是结点的深度优先次序。
9
1
2
34
5
6
7 8
10
图 7.16深度优先扩展树
37
在流图的结点表中可以增加结点的深度优先次序的项目 DFN,DFN(n)就记录着结点 n的深度优先次序的值 。
构造深度优先的扩展树,计算各结点的深度优先次序的算法如图 7.17所示 。 算法首先对所有结点给了未访问标记,然后由首结点 n0 开始调用递归过程
search(n0)。
在调用 search(n)时，先将 n标记改为已访问，表示 n
已非新结点，如果 n的后继结点 S(n)中有标记为未访问的新结点 s，则将有向边 n?s加入到扩展树中，如果已没有这种新结点作为后继结点，则便可将 i作结点 n的深度优先次序，然后 i递减 1。 DFN[n]是深度为主的次序的值。在流图的结点表中可以增加结点的深度优先次序的项目 DFN,DFN(n)就记录着结点 n的深度优先次序的值。
38
构造深度优先的扩展树,计算各结点的深度优先次序的算法如图 7.17所示 。 算法首先对所有结点给了未访问标记,然后由首结点 n0 开始调用递归过程
search(n0)。
在调用 search(n)时，先将 n标记改为已访问，表示 n
已非新结点，如果 n的后继结点 S(n)中有标记为未访问的新结点 s，则将有向边 n?s加入到扩展树中，如果已没有这种新结点作为后继结点，则便可将 i作结点 n的深度优先次序，然后 i递减 1。 DFN[n]是深度为主的次序的值。
39
主程序为：
T=empty；
for(n?N)
{将 n标记为,未访问,； }
i=|N|；
search(n0)；
递归过程为：
void search(n)；
{ 将 n标记为,已访问,；
for(s?S(n))
{ if(s标记为,未访问,)
{将有向边 n?s加到 T中； search(s)； }
DFN[n]=i；
i=i-1；
}
}
图 7.17 构造深度优先扩展树，求深度优先次序的算法
40
§ 7.4 数据流分析控制流分析确定了程序流图及其结构,特别是循环 。
优化需要对数据流作出分析,程序中的变量或者是以赋值或读入这类定值方式出现,或者是以引用方式出现,数据流分析就是分析程序中所有变量的定值和引用之间的关系 。 这一节我们将讨论几类数据流分析及其在代码优化中的应用 。
在数据流分析时,一个语句如果对变量 x定值,则这 一个语句的位置 d称为变量 x的一个定值点；如果一个语句中有对变量 y的引用,则这个语句的位置 u称为变量 y的一个引用点 。 例如在 p处有语句 x:=y op
z(通常写为 p:x:=y or z),则 p是 x的定值点,是 y和 z的引用点 。
变量 x在 d点的定值到达 u点，是指流图中有一条通路 d?u，而在这条通路上没有 x的其他定值点。
41
一,到达一定值数据流方程和 ud链循环优化时,常常要判别循环不变量和循环不变运算 。 循环不变量是指循环中没有这个变量的定值点 。
循环不变运算 x:=y op z,是指参与运算的 y及 z只能是常数或循环不变量 。 y及 z在循环中没有定值点,也就是 y及 z的定值点全在循环外,因此循环不变运算可以外提到循环外而不在循环中重复执行了,这就是一种重要的循环优化 —— 外码外提 。
如果在 u点引用一个变量 y时,能知道它是在何处定值的,那么我们就可以判定它是否在循环外定值,即可以判定它是否是循环不变量了 。 但如何知道变量 y
到达引用点 u的所有定值点呢？ 为此引进下列定义：
42
定义 7.6 ud链 。 能到达 u点的变量 y的所有定值点的集合称为 y在引用点 u处的引用一定值链,简称称 ud
链 。
因此,只要知道变量 y在引用点 u处的 ud链,我们就可知道 u点的 y是在何处定值的,因而能判定它是否是循环不变量了 。
如何求得变量 y在 u点的 ud链呢？ 为此引进下列定义
43
定义 7.7 IN[B]。 能到达恰在基本块 B入口之前处的各个变量的所有定值点的集合 。
如果能求得流图中每个基本块的 IN[B],则在基本块 B中 u点处变量 y的 ud链便可按下列规则建立：
(1)如果在 B中 u点之前有 y的定值点 d,且这个定值能到达 u,则 u点处 y的 ud的链为 {d}。
(2) 如果在 B中 u点之前没有 y的定值,则 IN[B]中关于 y
变量的每个定值点都能到达 u,所以 u点处 y的 ud链为
IN[B]中关于 y的定值点集,它是 IN[B]的一个子集 。
44
因此为了求 ud链,必须求每个基本块的 IN[B],为了求 IN[B]引进下列定义：
定义 7.8 OUT[B]:能到达恰在基本块 B出口之后处的各个变量的所有定值点的集合 。 如果能求得流图中每个基本块的 OUT[B],能到基本块 B入口之前的所有变量的定值点的全体 (即 IN[B])当然是 B的所有前驱结点 p的 OUT[p]的并集即,
IN[B]=?OUT (p)
p?P(B)
其中 P(B)为 B的前驱结点集,显然如果能求得流图中每个基本块的 OUT[B],则 IN[B]自然也是容易求的 。
45
因此为了求 ud链,必须求每个基本块的 IN[B],为了求 IN[B]引进下列定义：
为了求 OUT[B],还需引入下列定义：
定义 7.9 GEN[B]在基本块 B中定值并能到达 B的出口之后的所有的定值点的集合 。
定义 7.10 KILL[B]。 在基本块 B外定值而所定值的变量在 B中又重新被定值的那些定值点的集合 。 也即由于在 B中重新定值,而使得在 B外的定值在 B中因此被注销的那些定值点集 。
46
能到达基本块 B出口之后的定值点有两种可能,一种可能是 B中定值并能到达 B的出口之后的那些定值点集即 GEN [B]；另一种可能则是 IN[B]中定值点集而又未被 B中的定值所注销的定值点 IN[B]- KILL[B]，
它也能到达 OUT[B],故有：
OUT[B]= GEN [B]∪ (IN[B]- KILL[B]) (7.3)
47
基本块内定值并能到达基本块出口之后的定值点集即 GEN [B]是可以由流图求出而作为已知量的,基本块外定值而又因基本块内定值而被注销的定值点集即
KILL[B]也是可以由流图求出而作为已知量的,因此有,IN[B]=?OUT [p]
p?P(B) (7.4)
OUT[B]= GEN [B]∪ (IN[B]- KILL[B])
如果流图有 n个基本块,则 (7.4)为 2n个变量 (n个
IN[B],n个 OUT[B])的 2n个方程的线性联立方程组 。
在给出初值 OUT[B]= GEN [B],IN[B]=?后用迭代法不难求解,然后利用求得的 IN[B]可在每个引用点为引用变量建立 ud链作为代码优化的信息 。
(7.4)称为到达一定值数据流方程 。
48
数据流方程的求解,
到达一定值数据方程 (7.4)可用下述方法求解：
可 以 用 迭 代 法 求 值 。 由于 IN[B],OUT[B],
GEN[B],KILL[B],都是全集的某个子集,设全集
|U|=m,则可用 m位的位向量来表示这些子集 。
方程 (7.4)依赖于前驱结点,迭代可按深度为主次序,
由前向后进行 。
方程 (7.4) 是与前驱或后继的并集有关,迭代初值空集?。
GEN[B],KILL[B],根据各自的定义都可由流图直接求出,它们直接影响着迭代结果 。
前后两次迭代结果相同时,便得到了解 。
49
(1)[例 7.12] 对图 7.18给出的流图,求解基本块入口之前定值点集 。 只考虑变量 I,J,流图中只关心 5个定值点即 d1… d5,基本块 B5中没有 I,J的定值点,故设位向量长度为 5,各基本块的 GEN[B],KILL[B],列于图
7.19,OUT[B]的初值取 GEN[B]，
IN[B]的初值取空集?,对每个基本块
B求 IN[B],OUT[B]。 求解按深度为主次序 B1,B2,… B5依次进行,各次迭代列于图 7.19的表中,第四次代迭代结果与第三次相同,认为已收敛 。
d1,I:=1
d2,J:=I+2
d3,I:=2
d4,J:=J-1
d5,J:=J+4
:= I
:= J B5
B4
B3
B2
B1
图 7.18 例 7.12的流图
50
基本块 KILL GEN 第一次 第二次 第三次 第四次
[B] [B] IN[B] OUT[B] IN[B] OUT[B] IN[B] OUT[B] IN[B] OUT[B]
B1 00111 11000 00100 11000 01100 11000 01111 11000 01111 11000
B2 10000 00100 11000 01100 11111 01111 11111 01111 11111 01111
B3 01001 00010 01100 00110 01111 00110 01111 00110 01111 00110
B4 01010 00001 00110 00101 00110 00101 00110 00101 00110 00101
B5 00000 00000 00111 00111 00111 00111 00111 00111 00111 00111
图 7.19 到达一定值数据流方程的求解过程
d1,I:=1
d2,J:=I+2
d3,I:=2
d4,J:=J-1
d5,J:=J+4
:= I
:= J
B5
B4
B3
B2
B1
图 7.18 例 7.12的流图
51
§ 7.5循环优化非局部优化是在结构分析和数据流分析基础上进行的，一般先作循环优化，有代码外提、强度削弱和删除归纳变量，然后作全局优化，主要是常数传播，合并已知量，删除公共子表达式及复写传播等。从优化效果看，循环优化特别是内层循环的优化最为显著。
为了描述循环优化，给出下列例子。
一、循环优化的例子若有一循环语句,for i:=1 to 10 do a[i,2*j]:=a[i,
2*j]+1；根据第五章讨论的思想可以生成图 7.20的中间代码，相应流图如图 7.21所示。
52
(1) i:=1
(2) if i>10 goto(16)
(3) t1=2*j
(4) t2=10*i
(5) t3=t2+t1
(6) t4=a0-11
(7) t5=2*j
(8) t6=10*i
(9) t7=t6+t5
(10) t8=a0-11
(11) t9:=t8[t7]
(12) t10:=t9+1
(13) t4[t3]:=t10
(14) i:=i+1
(15) goto (2)
(16)…
(3) t1=2*j
(4) t2=10*i
(5) t3=t2+t1
(6) t4=a0-11
(7) t5=2*j
(8) t6=10*i
(9) t7=t6+t5
(10) t8=a0-11
(11) t9:=t8[t7]
(12) t10:=t9+1
(13) t4[t3]:=t10
(14) i:=i+1
(15) goto (2)
(1) i:=1
(2) if i>10 goto(16)
(16)…
图 7.20 循环语句的中间代码 图 7.21 相应的流图
53
二、代码外提
1,循环不变运算。
循环 L中如 x:=y 。 op z一类计算，如果 y与 z是常数或者其定值点均在循环 L之外，则该计算称为循环不变运算，它在循环中每次都运算的结果是相同的，因此它其实不必在循环中每次运算，只要将它提到循环外某个恰当位置上作一次运算即可，这便是循环不变运算的代码外提，其优化效果是十分明显的。要判断循环不变运算并不困难，这只要看 y及 z是否都是常数，或者由该点的 ud链可查知 y或 z的定值点在 L之外。
54
2,前置结点。
将循环不变运算外提到循环外什么地方才适当呢？显然最适当的地方是在循环外即将进入循环的地方，即恰在循环的入口结点之前处。不难发现，我们所定义的循环强调有唯一入口结点，将保证代码外提的唯一性为保证代码外提点既在循环入口结点之前，又不在循环之中，因此在循环入口结点之前设置一前置结点，
从前置结点向入口结点引一有向边，原循环外引向入口结点的有向边改为引向前置结点，循环内引向入口结点的有向边则不变，经过上述变换后循环不变运算代码便可外提到前置结点中，
55
循环不变运算的查找算法：
(1)对循环 L中各基本块满足下列条件的语句作不变运算的标记：语句的每个运算对象，或为常数，或定值点在 L外 (这由 ud链可确定 )。
(2)依次查看未标记为“不变运算”的语句，如果它的每个运算对象或为常数，或定值点在 L外，或唯一能到达的定值点已被标记为“不变运算”，则将该语句也标记为“不变运算”。
(3) 重复 (2)。直至没有新的语句被标记为“不变运算”
时为止。
56
代码外提算法：
(1) 寻找循环 L中所有不变运算。
(2) 对每一不变运算 P,x:=y op z或 x:=op y或 x:=y，如果它满足下述两组条件中的一组
P点所在基本块是 L所有出口结点之必经结点；
x在 L中没有其他定值点；
L中引用 x处只有 P点的定值才能到达。
x在出 L之后不再活跃；
x在 L中没有其他定值点；
L中引用 x处只有 P点的定值才能到达。
则将满足条件的不变运算，按查找不变运算次序，依次外提到 L的前置结点中。
57
三、归纳变量定义 7.18
(1) 循环 L中变量有唯一的定值 i:=i± c，其中 c为常量，
则称 i为循环 L中的基本归纳变量。
(2) 循环 L中如果变量 j的定值均为 j:=c1*i± c2形式，
其 I为循环的基本归纳变量,c1,c2为循环不变量，则称 j为 i同族的归纳变量。
图 7.26中，变量 i只有语句 (14)为唯一的定值 i:=i+1，
故 i为基本归纳变量，此外
t2=10*i
t3=t2+t1=10*i+t1
t6=10*i
t7=t6+t5=10*i+t5
t1,t5均为循环不变量，故 t2,t3,t6,t7均为 i同族的归纳变量
58
四、强度削弱与基本归纳变量同族的归纳变量在循环中将随着基本归纳变量的变化而发生线性变化，相应计算代码中涉及的乘法和加法，
可依据变化规律变换成执行时间短的代码来代替，这当然也是一种优化，称为强度削弱。由于数组和循环在程序中被普遍作用，在以循环变量作为基本归纳变量的下标变量的地址计算中涉及这类线性函数的计算相当多，因此强度削弱的优化效果是不容忽视的。
图 7.26中 i为基本归纳变量，由语句 (14)，每循环一次,i增 1，
而 t2,t6是 i的线性函数,i增 1时,t2,t6分别增加 10，如果将语句 (4),(8)外提到 B2?中作为 t2,t6初始定值，而在语句 (14)后随递归增 1,t2,t6递归增 10，则程序的这种变换是等价的，如图
7.27(a)所示。但循环中二处乘法转换成二处加法，执行强度有了明显的削弱。
将乘法运算转换成加法类运算是一种强度削弱，将变通加法转换成变址器加法，同样可提高运算速度，因此对递归增加 10
的 t3,t7也可作类似的变换，如图 7.27(b)所示。
59
五、删除归纳变量基本归纳变量除了自身的递归定值外，往往只是作为循环控制和参于其他同族归纳变量的计算，在强度削弱后，其他同族归纳变量在循环中的运算因已转换成递归增加一个常量而已与基本归纳变量没有直接关系了，如图 7.27(b)中的 (4)(8)(5)(9)，因此只要将循环控制条件由依赖于基本归纳变量 i转换成依赖于它的同族归纳变量，此时基本归纳变量除了唯一的递归定值外，
已别无用处，因而可予删除。
图 7.27中由语句 (2)来实现循环控制，与 i同族的归纳变量为 t3，
t7，以 t3为例，它与 i的线性关系为 t3=10*i+t1,i终值为 10，此时
t3终值应为 100＋ t1，因此 i>10与 t3>100+t1应是等价的，语句 (2)
可变换为：
(2’) S:=100+t1
(2”) if t3>S goto
其中 (2’)是一循环不变运算，可外提至前置结点 B2?中，此时语句 (14)可删除，故有图 7.28。
在变换循环控制条件时，应选择循环中还要引用的或循环出口之后活跃的，当然与 i的线性函数关系应越简越好。
60
综上所述,强度削弱和删除归纳变量算法可描述如下：
(1) 寻找循环中的所有基本归纳变量 i。
(2) 寻找与基本归纳变量同族的归纳变量 j及其线性函数,通常它们具有下列形式：
j:=c*i,j:=i*c,j:=i/c,j:=i± c,j:=c± i。
(3) 设归纳变量 j与基本归纳变量 i的函数为 j=c1*i+c2,可按下列步骤作强度削弱：
在前置结点原有代码后增加
s:=c1*i
s:=s+c2
其中 s为增设的临时变量,c2=0时,后一语句可省略；
循环中原来 j的赋值改为 j:=s；
在基本归纳变量递归赋值语句 i:= i± c0后增加
t:=c1*c0
s:=s± t
其中 t为增设的临时变量 。
61
(4) 上述复写 j:=s至循环中引用 j处的通路上没有对 s的重新定值,
j在循环出口后不活跃,则作复写传播,即删除 j:=s,所有引用 j
处改为引用 。
(5) 基本归纳变量 i在循环出口后不活跃,循环中除递归赋值本身外,只在形如 if i rop x goto A或 if x rop i goto A控制语句中被引用,则按下列步骤删除归纳变量 。
选一与 i同族的归纳变量 j,使 j=c1*i+c2的函数应最简单,j在循环出口之后是活跃的,或 j在循环中还有其他引用；
用下列语句
x?:=c1*x
x?:= x?+c2
if j rop x? goto A(或 if x? rop j goto A)
来代替 if i rop x goto A(或 if x rop i goto A)；
删除循环中 i的递归赋值语句,i:=i± c。
