第11章代码优化ppt课件.ppt

第11章 代码优化,11.1 代码优化技术 11.2 局部优化11.3 控制流程分析和循环,【学习目标】 通过本章学习： 理解所谓代码优化是指什么？ 知道最常用的代码优化技术有哪些？ 知道实现代码优化要进行哪些工作？ 【学习指南】 所谓代码优化是指对程序代码进行等价变换。程序代码可以是中间代码(如四元式代码)，也可以是目标代码。优化的含义是最终生成的目标代码短(而运行速度快)，时空效率优化。最常用的代码优化技术有删除多余运算，循环不变代码外提，强度削弱，变换循环控制条件，合并已知量与复写传播，以及删除无用赋值等等。 【难重点】 从概念上理解什么是代码优化，编译过程中可进行哪些优化，以及进行优化所需要的基础都没有难点，但在实现上是有相当复杂的工作。,11.0 概述,源语言程序经过词法分析、语法分析、语义分析和中间代码生成等编译前期工作（编译前端），得到了与源程序等价的中间代码程序。中间代码程序的质量将直接影响目标程序执行的效率。程序执行的效率体现在两个方面：目标程序运行时刻所占用的存储空间和目标程序运行时刻所耗费的时间。,所谓优化，是为了提高程序的执行效率而对程序代码进行的等价变换。使得变换后的代码运行结果与变换前代码运行结果相同，而运行速度加大或占用存储空间少，或两者都有。,编译过程中可进行的优化可按阶段划分：优化可在编译的不同阶段进行，分为中间代码一级和目标代码一级的优化。可按优化涉及的程序范围划分：对同一阶段，分为局部优化,循环优化和全局优化。可按优化是否涉及具体计算机来划分：分为与计算机有关的优化和与计算机无关的优化。,优化可在编译的不同阶段进行，对同一阶段，涉及的程序范围也有所不同，在同一范围内，可进行多种优化。目前编译程序的优化工作一般是在中间代码生成之后和（或）目标代码生成之后进行。如图11.1所示。,中间代码的优化是对中间代码进行等价变换。目标代码的优化是在目标代码生成之后进行的，因为生成的目标代码对应于具体的计算机，因此，这一类优化在很大程度上依赖于具体的机器，我们不做详细讨论。,另外依据优化所涉及的程序范围，又可分为局部优化、循环优化和全局优化三个不同的级别。局部优化指的是在只有一个入口、一个出口的基本程序块上进行的优化。循环优化是对循环中的代码进行的优化。全局优化是在整个程序范围内进行的优化。,编译程序的优化工作旨在生成较好性能的目标代码，为此，编译程序需要对代码（中间代码或目标代码）进行各种方式的变换。变换的宗旨是：,等价经优化工作变换后的代码运行结果应与原来程序运行结果一样。,有效经优化工作变换后的代码应运行时间较短，占用的存储空间较小。,合算获得较好性能的目标代码是优化工作的意图，而优化本身包括大量的代码分析和变换工作，这里有个权衡：应尽可能以较低的代价取得较好的优化效果。,11.1 代码优化技术,常用的优化技术有：删除多余运算；循环不变代码外提；强度削弱；变换循环控制条件；合并已知量与复写传播；删除无用赋值。为了说明这些常用的优化技术，我们来看下面这个例子。,例11.1 源程序是： P=0 for （I=1；I=20；I=+） P=P+AI*BI； 经过编译得到的中间代码如图11.2所示，这个程序段由B1和B2两个部分组成，B2是一个循环，假定每个元素按4字节编址。那么，对于这个中间代码段，如何进行上述优化。,图11.2 中间代码段,数组元素地址计算的常量部分T2,数组元素地址计算的增量部分T1,P=0for （I=1；I=20；I=+） P=P+AI*BI；,1）删除多余运算（删除公共子表达式）,优化的目的在于使生成的目标代码较少而执行速度较快。四元式（6）变换成：T4=T1。这种优化称为删除多余运算或称为删除公共子表达式。,图11.2 中间代码段,2）代码外提,减少循环中代码总数的一个重要办法是循环不变代码外提。这种变换把循环不变运算，即其结果独立于循环执行次数的表达式，提到循环的前面,使之只在循环外计算一次。上例中，我们可以把四元式（4）和四元式（7）提到循环外。经过删除多余运算和代码外提后，代码变换成图11.3。,图11.3 删除公共子表达式和代码外提,3）强度削弱,强度削弱的思想是把强度大的运算换算成强度小的运算。循环中计算T1值的乘法运算变换成在循环前进行一次乘法运算，而在循环中将其变换成加法运算。变换后如图11.4所示。,图11.4强度削弱,4）变换循环控制条件,图11.4的代码中，四元式（12）的循环控制条件I20变换成T180，这样整个程序的运行结果不变。这种变换称为变换循环控制条件。经过这一变换后，循环中I的值在循环后不会被引用，四元式（11）成为多余运算，可以从循环中删除。变换循环控制条件可以达到代码优化的目的。,图 11.5变换循环控制条件，合并已知量，复写传播,图11.4中，四元式（3）可变为T14，这种变换称为合并已知量。图11.4中，四元式(6)把T1的值复写到T4中，四元式（8）要引用T4的值，而从四元式（6）到四元式（8）之间未改变T4和T1的值，则将四元式（8）改为T6=T5T1，这种变换称为复写传播.复写传播之后运算结果保持不变。图11.4经过变换循环控制条件，合并已知量和复写传播等变换后，变为图11.5。,图 11.5变换循环控制条件，合并已知量，复写传播,6）删除无用赋值,在图11.5中，（6）对T4赋值，但T4未被引用；另外，（2）和（11）对I赋值，但只有（11）引用I。所以，只要程序中其它地方不需要引用T4和I，则（6），（2）和（11）对程序的运行结果无任何作用。我们称之为无用赋值，无用赋值可以从程序中删除，如图11.6所示。比较图11.2和图11.6可看出，经过优化后的代码的执行效率提高了很多。当然，实现这些优化的一系列工作是非常复杂的，代价也是很大的。,图 11.6 删除无用赋值,11.2 局部优化,我们所说的局部优化是指基本块内的优化。,所谓基本块，是指程序中一个单入口、单出口的线性程序块（顺序执行的语句序列）。,控制流只能从其入口语句进入，从其出口语句退出,没有中途停止或分支。,局部优化工作包括对于一个给定的程序，把它划分为一系列的基本块,在各个基本块范围内分别进行优化。,局限于基本块范围内的优化称为基本块内的优化，也称为局部优化。,11.2.1 基本块的划分,我们先定义基本块的入口语句。 所谓入口语句有三种，就是： 程序的第一个语句； 条件转移语句或无条件转移语句的转移目标语句； 紧跟在条件转移语句后面的语句。,有了入口语句的概念之后，我们就可以给出划分中间代码（四元式程序）为基本块的算法。,划分中间代码（四元式程序）为基本块的算法：, 求出四元式程序中各个基本块的入口语句。 对每一入口语句，构造其所属的基本块。它是由该入口语句到下一入口语句（不包括下一入口语句），或到一转移语句（包括该转移语句），或到一停语句（包括该停语句）之间的语句序列组成的。 凡未被纳入某一基本块的语句、都是程序中控制流程无法到达的语句，因而也是不会被执行到的语句，可以把它们删除。,我们以下述四元式程序为例来说明如何划分基本块的。例11.1:有四元式程序如下，构造其基本块。(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,先求出四元式程序中各个基本块的入口语句：语句（1）是程序的第一个语句，因此它是入口语句。语句（4）和语句（8）是条件转移语句或无条件转移语句的转移目标语句，因此是入口语句。语句（6）是紧跟在条件转移语句后面的语句，因此是入口语句。,(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,基本块：语句（1），（2）和（3）构成第一个基本块；语句（4）和（5）构成第二个基本块；语句（6）和（7）构成第三个基本块；语句（8）和（9）构成第四个基本块。,11.2.2 基本块内的优化变换,很多优化变换可作用于基本块而不改变它计算的表达式集合，这样的变换对改进代码的质量是很有用的。有两类重要的局部等价变换可用于基本块；它们是保结构的变换和代数变换。,基本块的主要保结构变换是：删除公共子表达式删除无用代码重新命名临时变量交换语句次序,对于删除公共子表达式和删除无用代码这两种优化技术，我们在11.1中已经讨论过，这里简单介绍重新命名临时变量和交换语句次序是什么含义。重新命名临时变量：假如有语句t=b+c，其中t是临时变量。如果把这个语句改为u=b+c，其中u是新的临时变量，并且把这个t的所有引用改成u，那么基本块的运算结果不变。,交换语句次序： 如果基本块有两个相邻的语句： t1=b+c t2=x+y当且仅当x和y都不是t1，b和c都不是t2时，我们可以交换这两个语句的次序。,代数变换可以把基本块计算的表达式集合变换成代数等价的集合。其中常用的变换是那些可以简化表达式或用较快运算代替较慢运算的变换。例如：x=x+0或x=x*1这样的语句可以从基本块中删除而不改变它计算的表达式集合，又如x=y*2的指数算符通常要用函数调用来实现，使用代数变换，这个语句可由快速、等价的语句x=y*y来代替。,我们从下面例子理解这些变换。,有四元式程序：t1 := 4 2t2 := t1 /2t3 := a * t2t4 := t3 * t1t5 := b + t4c := t5 * t5,进行合并已知量变换后得到：t1 := 2t2 := t1 /2t3 := a * t2t4 := t3 * t1t5 := b + t4c := t5 * t5,再进行复写传播和删除无用赋值等变换后得到：t2 := 2 /2t3 := a * t2t4 := t3 * 2t5 := b + t4c := t5 * t5,再进行合并已知量变换后得到：t2 := 1t3 := a * t2t4 := t3 * 2t5 := b + t4c := t5 * t5,再进行合并已知量变换后得到：t2 := 1t3 := a * t2t4 := t3 * 2t5 := b + t4c := t5 * t5,再进行复写传播和删除无用赋值等变换后得到：t3 := a * 1t4 := t3 * 2t5 := b + t4c := t5 * t5,接着使用代数变换后有：t3 := at4 := t3 * 2t5 := b + t4c := t5 * t5,使用复写传播和删除无用赋值变换后又有：t4 := a * 2t5 := b + t4c := t5 * t5,再使用代数变换：t4 := a + at5 := b + t4c := t5 * t5,重新命名临时变量：t1 := a + at5 := b + t1c := t5 * t5,还可减少临时变量：t1 := a + at1 := b + t1c := t1 * t1,使用复写传播和删除无用赋值变换后又有：t4 := a * 2t5 := b + t4c := t5 * t5,11.2.3 基本块的DAG表示,现在我们介绍如何应用有向图来进行基本块的优化工作。先将所要使用的DAG作一说明。在一个有向图中，我们称任一有向边ninj(或表示为有序对（ni，nj）)中的结点ni为结点nj的前驱（父结），结点nj为结点ni的后继（子结）。又称任一有向边序列n1n2，n2n3，nk-1nk为从结点n1到结点nk的一条通路。如果其中n1nk，则称该通路为环路。该结点序列也记为（n1，n2，nk）。,例如，图11.7中有向图的通路（n2，n2）和（n3，n4，n3）就是环路。如果有向图中任一通路都不是环路，则称该有向图为无环路有向图，简称DAG。,图11.8的有向图就是一个DAG。在DAG中，如果（n1，n2，nk）是其中一条通路，则称结点n1为结点nk的祖先，结点nk为结点n1的后代。图11.8中结点n6就是结点n9的祖先，n9是n6的后代。,我们要用到的有向图，是一种其结点带有下述标记或附加信息的DAG：,图的叶结点，即无后继的结点，以一标识符（变量名）或常数作为标记，表示这个结点代表该变量或常数的值。如果叶结点用来代表某变量A的地址，则用addr（A）作为这个结点的标记。通常把叶结点上作为标记的标识符加上下标0，以表示它是该变量的初值。图的内部结点，即有后继的结点,以一运算符作为标记，表示这个结点代表应用该运算符对其后继结点所代表的值进行运算的结果。图中各个结点上可能附加一个或多个标识符，表示这些变量具有该结点所代表的值。,上述这种DAG可用来描述计算过程，又称为描述计算过程的DAG。在以下的讨论中，我们简称为DAG。,基本块的DAG表示与构造:,一个基本块，可用一个DAG来表示。下面列出各种四元式及相对应的DAG的结点形式。图中ni为结点编号，结点下面的符号（运算符、标识符或常数）是各结点的标记，各结点右边的标识符是结点的附加标识符。,四元式,DAG,（0）A:=B （:=，B，-，A）,（1）A:=op B （op，B，-，A）,（2）A:=B op C （op，B，C，A）,（3）A：=BC （= ，BC，-，A）,（4）if B rop C goto （s） （jrop，B，C，(s)）,（5）DC：=B （ =，B，-，DC）,（6）goto （s） （j，-，-，（s）,(1) T0=3.14(2) T1=2 * T0(3) T2=R + r (4) A=T1 * T2(5) B=A(6) T3=2 * T0(7) T4=R + r(8) T5=T3 * T4(9) T6=Rr (10) B=T5 * T6,(1) T0=3.14(2) T1=2 * T0(3) T2=R + r (4) A=T1 * T2(5) B=A(6) T3=2 * T0(7) T4=R + r(8) T5=T3 * T4(9) T6=Rr (10) B=T5 * T6,(1) T0=3.14(2) T1=2 * T0(3) T2=R + r (4) A=T1 * T2(5) B=A(6) T3=2 * T0(7) T4=R + r(8) T5=T3 * T4(9) T6=Rr (10) B=T5 * T6,(1) T0=3.14(2) T1=2 * T0(3) T2=R + r (4) A=T1 * T2(5) B=A(6) T3=2 * T0(7) T4=R + r(8) T5=T3 * T4(9) T6=Rr (10) B=T5 * T6,(1) T0=3.14(2) T1=2 * T0(3) T2=R + r (4) A=T1 * T2(5) B=A(6) T3=2 * T0(7) T4=R + r(8) T5=T3 * T4(9) T6=Rr (10) B=T5 * T6,(1) T0=3.14(2) T1=2 * T0(3) T2=R + r (4) A=T1 * T2(5) B=A(6) T3=2 * T0(7) T4=R + r(8) T5=T3 * T4(9) T6=Rr (10) B=T5 * T6,(1) T0=3.14(2) T1=2 * T0(3) T2=R + r (4) A=T1 * T2(5) B=A(6) T3=2 * T0(7) T4=R + r(8) T5=T3 * T4(9) T6=Rr (10) B=T5 * T6,(1) T0=3.14(2) T1=2 * T0(3) T2=R + r (4) A=T1 * T2(5) B=A(6) T3=2 * T0(7) T4=R + r(8) T5=T3 * T4(9) T6=Rr (10) B=T5 * T6,(1) T0=3.14(2) T1=2 * T0(3) T2=R + r (4) A=T1 * T2(5) B=A(6) T3=2 * T0(7) T4=R + r(8) T5=T3 * T4(9) T6=Rr (10) B=T5 * T6,(1) T0=3.14(2) T1=2 * T0(3) T2=R + r (4) A=T1 * T2(5) B=A(6) T3=2 * T0(7) T4=R + r(8) T5=T3 * T4(9) T6=Rr (10) B=T5 * T6,11.2.4 DAG的应用,将四元式表示成相应的DAG后，可以利用DAG来进行优化。首先由DAG构造优化的四元式序列。回顾一下DAG构造算法中几个步骤的作用。对于步骤2，如果参与运算的对象都是编译时的已知量，则它并不生成计算该结点值的内部结点，而是执行该运算，将计算结果生成一个叶结点。显然，步骤2起到了合并已知量的作用。步骤3的作用是检查公共子表达式，对具有公共子表达式的所有四元式，它只产生一个计算该表达式值的内部结点，而把那些被赋值的变量标识符附加到该结点上。这样可删除多余运算。步骤4具有删除无用赋值的作用。如果某变量被赋值后，在它被引用前又被重新赋值，则步骤4把该变量从具有前一个值的结点上删除。这样，在一个基本块被构造成相应的DAG的过程中已经进行了一些基本的优化工作。而后，我们可由DAG重新生成原基本块的一个优化的代码序列。,例11.5 我们将图11.10（j）的基本块G的DAG按原来构造其结点的顺序，重新写成四元式。,得到以下的四元式序列G：(1) T0=3.14(2) T1=6.28(3) T3=6.28(4) T2=R+r(5) T4=T2(6) A=6.28*T2(7) T5=A(8) T6=Rr (9) B=A*T6,(1) T0=3.14(2) T1=2 * T0(3) T2=R + r (4) A=T1 * T2(5) B=A(6) T3=2 * T0(7) T4=R + r(8) T5=T3 * T4(9) T6=Rr (10) B=T5 * T6,把G和原基本块G相比，可以看出：1 G中的代码（2）和（6）的已知量都已合并。2 G中（5）的无用赋值已被删除。3 G中（3）和（7）的公共子表达式R+r只被计算一次，删除了多余运算。 所以G是G的优化结果。,再来看看DAG提供的优化信息 :,除了可应用DAG进行上述的优化外，我们还可从基本块的DAG中得到一些其它优化信息。,这些信息是： 在基本块外被定值并在基本块内被引用的所有标识符，就是作为叶子结点上标记的那些标识符。 在基本块内被定值且该值能在基本块后被引用的所有标识符，就是DAG各结点上的那些附加标识符。,前面我们所删除的无用赋值只是其中一种情况，在这里，我们利用这些信息，根据有关变量在基本块后被引用的情况，可以进一步删除基本块中的其它情况的无用赋值。,例11.6 上例中，假设T0，T1，T6在基本块的后面都没有被引用，则可将G重写为如下代码序列：,(1) T0=3.14(2) T1=6.28(3) T3=6.28(4) T2=R+r(5) T4=T2(6) A=6.28*T2(7) T5=A(8) T6=Rr (9) B=A*T6,(1) S1=R+r(2) A=6.28*S1(3) S2=R-r(4) B=A *S2其中S1和S2用于存放中间临时变量。整个序列中，没有生成对T0，T1，T6赋值的代码。,11.3 控制流分析和循环优化,控制流程图（流图）：具有唯一首结点的有向图。我们可以把一个控制流程图表示成一个三元组 G。记为：,N：结点集,基本块集,E：有向边集,n0 ：首结点,包含程序第一个语句的基本块,G(N，E，n0),所谓首结点，就是从它开始到控制流程图中任何结点都有一条通路的结点。,11.3.1 程序流图与循环,一个程序可用一个流图来表示。流图中的有限结点集N就是程序的基本块集，流图中的结点就是程序中的基本块。流图的首结点就是包含程序第一个语句的基本块。程序流图中的有向边集E是这样构成的：假设流图中结点i和结点j分别对应于程序的基本块i和基本块j，则当下述条件1)或2)有一个成立时，从结点i有一有向边引向结点j：1). 基本块j在程序中的位置紧跟在基本块i之后，并且基本块的出口语句不是无条件转移语句goto（s）或停语句。2). 基本块i的出口语句是goto（s）或ifgoto（s），并且（s）是基本块j的入口语句。,11.3.2 循环,在一个程序流程中，循环是必不可少的一种控制结构。所谓循环，粗略地说，就是程序中那些可能反复执行的代码序列。因为循环中的代码要反复执行，因而为了提高目标代码的效率必须着重考虑循环的代码优化。要进行循环优化。首先必须找出程序中的循环，为找出程序中的循环，就需要对程序的控制流程进行分析。,在程序流图中，我们称具有下列性质的结点序列为一个循环： 它们是强连通的。也即，其中任意两个结点之间，必有一条通路，而且该通路上各结点都属于该结点序列。如果序列只包含一个结点，则必有一有向边从该结点引到其自身。 它们中间有且只有一个是入口结点。所谓入口结点，是指序列中具有下述性质的结点：从序列外某结点，有一有向边引到它，或者它就是程序流图的首结点。因此，我们定义的循环就是程序流图中具有唯一入口结点的强连通子图，从循环外要进入循环，必须首先经过循环的入口结点。,例11.8 图11.12中的程序流图，根据定义，结点序列6，4，5，6，7以及2，3，4，5，6，7都是循环；而结点序列2，4，2，3，4，4，6，7以及4，5，7虽然都是强连通的，但因它们的入口结点不唯一，所以都不是上述意义下的循环。不难看出,图11.11中的程序流图里,B2，B3是程序中的循环，而B2是唯一的入口结点,图 11.12 程序流图,11.3.3 循环的查找,为了找出程序流图中的循环，需要分析流图中结点的控制关系。为此，我们引入必经结点和必经结点集的定义。在程序流图中，对任意两个结点m和n，如果从流图的首结点出发，到达n的任一通路都要经过m，则称m是n的必经结点，记为m DOM n。流图中结点n的所有必经结点的集合，称为结点n的必经结点集，记为D（n）。显然，循环的入口结点是循环中所有结点的必经结点。,把DOM可以看作流图结点集上定义的一个关系，则由定义容易看出，它具有以下性质：1. 自反性：对流图中任意结点a，有a DOM a。2. 传递性：对流图中任意结点a、b和c。若a DOM b，b DOM c，则有a DOM c。3. 反对称性：若a DOM b且b DOM a，则必有ab。因此，关系DOM是一个偏序关系。任何结点n的必经结点集是一个有序集。,例11.8 求图11.12中各结点的D（n）。直接由定义和DOM的性质，可以求得：必经结点集:D(1)=1D(2)=1,2D(3)=1,2,3D(4)=1,2,4D(5)=1,2,4,5D(6)=1,2,4,6D(7)=1,2,4,7,图 11.12 程序流图,循环的查找,循环的查找算法:,回边：假设,a,b,是流图中的一条有向边，如果,b DOM a,，则,称,a,b,是流图中的一条回边。,有向边,nd,是回边，组成的循环是由结点,d,，结点,n,以及有,通路到达,n,而该通路不经过,d,的所有结点组成，并且,d,是该循,环的唯一入口结点。,应用上述的必经结点集，可以求出流图中的回边，利用回边，就可以找出流图中的循环。,例11.9 求图11.12中流图的所有回边。 由流图可以看出，有向边66、74、42是回边。 因为根据前例的结果有6 DOM 6，4 DOM 7，2 DOM 4，其它有向边都不是回边。 对于图11.12流图中的例子，我们很容易看出。由回边66组成的循环就是6,由回边74组成的循环是4，5，6，7；由回边42组成的循环是2，3，4，5，6，7。,图 11.12 程序流图,11.3.4 循环优化,在找出了程序流图中的循环之后，我们就可以针对每个循环进行优化工作。因为循环内的指令是重复执行的，故而循环中进行的优化在整个优化工作中是非常重要的。,循环优化的三种重要技术是：代码外提；删除归纳变量和强度削弱。,我们只对代码外提再进行一些讨论.代码外提:减少循环中代码数目的一个重要办法是代码外提。,前面已经介绍了一个代码外提的例子。这种变换把循环不变运算，即产生的结果独立于循环执行次数的表达式，放到循环的前面。这里，所讨论的循环只存在一个入口。实行代码外提时，在循环的入口结点前面建立一个新结点（基本块），称之为循环的前置结点。循环的前置结点以循环的入口结点为其唯一后继，原来流图中从循环外引到循环入口结点的有向边，改成引到循环前置结点，如图11.13所示：,我们考虑的循环结构，其入口结点是唯一的。所以，前置结点也是唯一的。循环中外提的代码将全部提至前置结点中。前面介绍的图11.3和图11.4都是图11.2的代码外提的结果。在那个例子中，我们可以很明显地看到代码外提的优化作用。是否在任何情况下，都可把循环不变运算外提呢?下面我们看一个例子。,例11.10 考察图11.14的流图。 容易看出B2，B3，B4是循环，其中B2是循环的入口结点，B4是出口结点。所谓出口结点，是指循环中具有这样性质的结点：从该结点有一有向边引到循环外的某结点。 图11.14的B3中i=2是循环不变运算。如果我们把i=2提到循环 的前置结点B2中，如图11.15所示。,图 11.15 程序流图,如果我们按照图11.15的程序流图执行，执行到B5时，i的值总为2，则j的值也为2。事实上，按图11.14的流图，若x30，y25，则B3不被执行，执行到B5时，i和j的值都为1，所以图11.15的流图改变了原来程序的运行结果。,问题的原因在于B3不是循环出口结点B4的必经结点。所以，当把一个不变运算提到循环的前置结点时，要求该不变运算所在的结点是循环所有出口结点的必经结点。此外，如果循环中i的所有引用点只是B2中i的定值点（“点”指某一四元式的位置，对变量的“定值”指对变量赋值或输入值）所能达到的，i在循环中不再有其它定值点，并且出循环后不再引用该i的值，那么，即使B3不是B4的必经结点，也还可以把i =2提到B2中，因为这不影响原来程序的运行结果。 这里所说的定值点指变量在该点被赋值或输入值，引用点则指在该点使用了该变量。,如果把图11.14中的B2改为i:= 3；if xy goto B3试考虑B2中不变运算i:= 3的外提问题。,现在i:= 3所在的结点B2是循环出口结点的必经结点。但因为循环中除B2外，B3也对i定值，如果把B2中不变运算i:= 3外提到循环的前置结点中，则程序的执行流程是B2B3B4B2B4B5，那么到达B5时i的值是2，而j的值也是2；可是如果不把B2中不变运算i:= 3外提，经以上执行流程到达B5时i的值是3，而j的值也是3，并不是2。从该例看到，当把循环中不变运算A：=B op C外提时，要求循环中其它地方不再有A的定值点。,当把循环中的不变运算s:A:=B op C外提时注意：,（,2,）,要求循环中其它地方不再有A的定值点；,（3,）,要求循环中A的所有引用点都是而且仅仅是这个定值所能达到的；,（1）要求s所在结点是循环的所有出口结点的必经结点；,（4）要求A在离开循环之后不再是活跃的。,【本章小结】,代码优化是对程序实施各种等价变换，使得变换后的程序利于生成更有效的目标代码。编译程序可以在中间代码一级进行优化，也可以在目标代码一级进行优化。根据优化所涉及的程序范围，可分为局部优化，循环优化和全局优化三个级别。本章介绍了常用的优化技术，如代码外提，强度削弱，合并已知量，删除无用赋值以及复写传播等等。对控制流和数据流分析的概念也给予了简单的描述。,作业271页练习 3题，6题,