编译原理简明教程（第3版）-课件 第8章 代码优化

新工科建设·计算机类系列教材

免费提供编译原理16目录第一章概述第二章形式语言理论基础第三章自动机理论基础第四章词法分析第五章语法分析—自顶向下分析方法第六章语法分析—自底向上分析方法第七章语义分析及中间代码的生成第八章代码优化第九章目标代码的生成第十章符号表和出错处理第十一章

面向对象语言的编译第十二章

并行编译技术第十三章

软件构造22024/11/63学习目标代码优化的概念循环优化局部优化代码优化的分类8代码优化重点：代码优化的定义和代码优化的分类难点：局部优化、循环优化

目录8.1代码优化概述8.2局部优化8.3循环优化8.4本章小结4定义

所谓优化，实质上是对代码进行等价变换，使得变换后的代码具有更高的效率，包括时间效率和空间效率。目的

获得性能较好的代码，即要尽量缩小存储空间，还要尽量提高运行速度。

58.1代码优化概述8.1.1代码优化的定义优化可在编译的不同阶段进行：源代码设计阶段--程序员选择好的算法和语句语义分析阶段--如何生成高质量的中间代码中间代码--采用优化技术目标代码--有效利用寄存器、指令、处理机

678.1.2代码优化的分类1、与机器的相关性

与机器有关的优化：寄存器的优化、多处理机的优化、特殊指令的优化、无用代码的消除。与机器无关的优化：基本块的优化、循环优化。2、优化范围

局部优化：基本程序块上进行的优化

全局优化：全局程序范围内的优化88.1.2代码优化的分类1、局部优化：基本程序块上进行的优化

基本程序块---只有一个入口、一个出口的基本程序块

合并常量和已知量

消除公共子表达式

削减运算强度

删除无用代码2、全局优化：全局程序范围内的优化

循环优化是全局优化：

外提循环不变表达式

削减计算强度

删除归纳变量1、合并常量运算

运算对象是常量或在编译时已知，则在编译时直接计算出结果，不必等到运行时再去计算。

例：

x:=3.14*2;y:=2*5*a;z:=x+0.5;合并常量运算后： x:=6.28;y:=10*a;z:=6.78;98.1.3优化技术简介优化前的四元式：(1)(*

,3.14,2,T1)(2)(:=,T1

,_,

x)(3)(*

,2

,5,T2)(4)(*

,T2

,a,T3)(5)(:=,T3

,_,

y)(6)(+

,x

,0.5,T4)(7)(:=,T4

,

_,

z)优化后：

(1) (:=,6.28,_,x)(2)(*

,10

,a,y)(3)(:=,6.78,_,z)

102、删除无用赋值

删除程序中对运行结果没有任何作用的赋值变量。

例：

x:=2+a；

y:=2+b；

x:=2*a*b;y:=x*y;删除无用赋值后：

y:=2+b；

x:=2*a*b;y:=x*y;11优化前的四元式：(1)(+,2,a,x)(2)(+,2,b,y)(3)(*,2,

a,T1)(4)(*,T1,b,x)(5)(*,x,y,y)优化后的四元式：

(1)(+,2，b,y)(2)(*,2，a,T1)(3)(*,T1，b,x)(4)(*,x，y,y)

123、削减运算强度（运算强度大→小）

例：

fori:=1to100doa:=10*i；削减运算强度后：a:=0；fori:=1to100doa:=a+10;优化后的四元式：

(1)(:=,0

,_,a)(2)(:=,1

,_,i)(3)(<=,i,100,T1)(4)(BF,(8),T1,_)(5)(+

,a,10,a)(6)(+

,i,1,

i)(7)(BR,(3),_,_)(8)()134、删除多余运算(或删除公共子表达式)公共子表达式：重复使用两次以上的子表达式，且表达式中变量的值没有发生变化。

例：x:=a*(b+c)+d;y:=a*(b+c)-d;

14优化前：

(1)(+,b,c,T1)

(2)(*,a,T1,T2)(3)(+,T2,d,x)

(4)(+,b,c,T3)

(5)(*,a,T3,T4)(6)(-,T4,d,y)优化后：

(1)(+,b,c,T1)(2)(*,a,T1,T2)(3)(+,T2,d,x)(4)(-,T2,d,y)

155、外提不变表达式不变表达式：循环中其值始终保持不变的表达式

例：fori:=1to100dobeginx:=(a+b)*(c+d)*i;y:=x+i；end优化后的程序：e:=(a+b)*(c+d);fori:=1to100dobeginx:=e*i;y:=x+i；end16优化前的四元式：(1)(:=,1,_,i)(2)(<=,i,100,T1)(3)(BF,(11),T1,_)(4)(+, a,b,T2)(5)(+, c,d,T3)(6)(*, T2,T3,T4)(7)(*, T4,i,x)(8)(+, x,i,y)(9)(+, i,1,i)(10)(BR,(2),_,_)(11)( )

17优化后的四元式：(1)(:=,1,_，i)(2)(+,a,b,T1)(3)(+,c,d,T2)(4)(*,T1,T2,e)(5)(<=,i,100,T3)(6)(BF,(11),T3,_)(7)(*,e,i,x)(8)(+,x,i,y)(9)(+,i,1,i)(10)(BR,(5),_,_)(11)( )

18198.2局部优化a=10;b=a*10;

c=a+b;s=0;k=1;if(k<5)s=s+k;elses=s-k;一个基本块不是一个基本块

局部优化是指局部范围内的优化。把程序划分为若干个“基本块”，优化的工作将分别在各个基本块内进行。8.2.1基本块的划分

基本块，是指程序中一组顺序执行的语句序列，其中只有一个入口和一个出口，执行时只能从其入口进入，从其出口退出。即基本块内的运算要么都被执行，要么都不执行。208.2.1基本块的划分例题8.1、

考察下列四元式序列：(1)(=,(2)(+,(3)(>,(4)(

BF,(5)(_,(6)(=,(7)(BR,(8)(*,(9)(end,100,i,k,(8),

k,T3

,

(3),i,_,_,j,T1

,

T2

,

1,_,_,j,_,k)T1)T2))T3)k)_)k)_)图8.1基本块划分示例

由图8.1可以看出，以上程序段可以划分为四个基本块B1、B2、B3、B4

，而且各基本块之间通过一些有向边连接起来，这种有向图称为程序流图或流图。218.2.2基本块的DAG表示8.2.2基本块的DAG表示

为了便于对基本块进行优化，引进一种有效的数据结构——无回路有向图(DirectedAcyclicGraph，DAG)。228.2.2基本块的DAG表示

图8.2一个带环路的有向图图8.3一个无环路的有向图238.2.2基本块的DAG表示(1)(=,3.14,_,

T1)(2)(*,2,

T1

,T2)(3)(+,R,r,

T3)(4)(*,T2

,T3

,A)(5)(=,A,_,

B)(6)(*,2,

T1

,T4)(7)(+,R,r,

T5)(8)(*,T4

,T5

,T6)(9)(−,R,

r,T7)(10)(*,T5

,T7

,

B)例题8.2构造以下基本块G1的DAG248.2.2基本块的DAG表示利用算法8.2对以上基本块中10个四元式逐个进行处理，新产生的DAG

子图依次如图8.5(a)~(j)所示，其中，图8.5(j)即为要构造的DAG。图8.5基本块G

的

DAG258.2.3基本块优化的实现将四元式表示成相应的DAG

后，就可利用DAG对基本块进行优化。实际上，在对基本块执行算法8.2的过程中，已完成了对基本块进行优化的一系列基本工作。268.2.3基本块优化的实现利用这样的DAG，按照原来构造其节点的顺序，重建四元式序列G2如下：(=,3.14,_,T1)(2)(=,6.28,_,T2)(3)(=,6.28,_,T4)(4)(+,R,r,T3)(5)(=,T3,_,T5)(6)(*,6.28,T3,A)(7)(=,A,_,T6)(8)(_,R,r,T7)(9)(=,T5,T7,B)278.3循环优化循环是程序设计中一种重要的数据结构，程序运行时花费在循环上的时间往往占整个运行时间的很大部分，因此对循环的优化实为提高程序运行效率的重要途径。对循环的优化实为提高程序运行效率的重要途径。288.3.1循环的查找为了进行循环的优化，首先要查找程序中的循环。在程序流图中，具有下列性质的节点序列(即一组基本块)称为程序中的一个循环：①在这组节点中，有且只有一个是入口节点。②这组节点是强连通的，即任意两个节点之间必有一条通路(特别当这组节点仅含一个节点时，必有从此节点到其自身的有向边)。298.3.1循环的查找【例8.3】图8.6是一个程序流图。按照上述关于循环的定义可知，图8.6中，节点序列{6，7，8}以及{4，6，7，8}、{4，5，6，7，8}、{3，4，5，6，7，8}都是循环；而节点序列{3，4}、{4，5，6，7}虽然是强连通的，但因它们的入口节点不唯一，所以不是循环。图8.6一个程序流图308.3.2循环优化的实现循环优化的三种主要技术削减运算强度外提循环中的不变表达式删除归纳变量1、外提循环中的不变表达式318.3.2循环优化的实现所谓循环中的不变表达式是指该表达式的值不随循环的重复执行而改变。为了实现循环中不变表达式的外提，需解决如下三个问题：①如何查找循环中的不变表达式；②找到的不变表达式是否可以外提；③把不变表达式提到循环外的什么地方。328.3.2循环优化的实现相关概念：（1）变量的“定值点”：是指在四元式序列中变量被赋值或输入值的某一四元式的位置。（2）变量的“引用点”：是指在四元式序列中变量被引用的某一四元式的位置。（3）“到达一定值点”：是指变量在某点定值后到达的一点。（4）“活跃变量”：是指在流图中，从某一点P出发的通路上有该变量的引用点。（5）“循环的前置节点”：是指在循环的入口节点前面建立一个新节点(基本块)。338.3.2循环优化的实现例题、

x=10,y=20时，执行路径为B2→B3→B4→B5

，j=2;x=30,y=22时，执行路径为B2

→B4

→B2

→B4

→B5,j=1。图8.7在循环L

前设置前置节点图8.8程序流程一2、削减运算强度348.3.2循环优化的实现

削减运算强度是把程序中执行时间较长的运算替换为执行时间较短的运算，以提高目标程序的执行效率。358.3.2循环优化的实现例如，对于如下循环语句:i=a;while(i<=b){…

x=i*k…}把循环中的乘法运算用递归加法运算来实现。368.3.2循环优化的实现假定k和n都是在循环中不变的常量，且在循环中没有x

的其他定值点，那