第11章代码优化ppt课件.ppt
《第11章代码优化ppt课件.ppt》由会员分享,可在线阅读,更多相关《第11章代码优化ppt课件.ppt(74页珍藏版)》请在三一办公上搜索。
1、第11章 代码优化,11.1 代码优化技术 11.2 局部优化11.3 控制流程分析和循环,【学习目标】 通过本章学习: 理解所谓代码优化是指什么? 知道最常用的代码优化技术有哪些? 知道实现代码优化要进行哪些工作? 【学习指南】 所谓代码优化是指对程序代码进行等价变换。程序代码可以是中间代码(如四元式代码),也可以是目标代码。优化的含义是最终生成的目标代码短(而运行速度快),时空效率优化。最常用的代码优化技术有删除多余运算,循环不变代码外提,强度削弱,变换循环控制条件,合并已知量与复写传播,以及删除无用赋值等等。 【难重点】 从概念上理解什么是代码优化,编译过程中可进行哪些优化,以及进行优化
2、所需要的基础都没有难点,但在实现上是有相当复杂的工作。,11.0 概述,源语言程序经过词法分析、语法分析、语义分析和中间代码生成等编译前期工作(编译前端),得到了与源程序等价的中间代码程序。中间代码程序的质量将直接影响目标程序执行的效率。程序执行的效率体现在两个方面:目标程序运行时刻所占用的存储空间和目标程序运行时刻所耗费的时间。,所谓优化,是为了提高程序的执行效率而对程序代码进行的等价变换。使得变换后的代码运行结果与变换前代码运行结果相同,而运行速度加大或占用存储空间少,或两者都有。,编译过程中可进行的优化可按阶段划分:优化可在编译的不同阶段进行,分为中间代码一级和目标代码一级的优化。可按优
3、化涉及的程序范围划分:对同一阶段,分为局部优化,循环优化和全局优化。可按优化是否涉及具体计算机来划分:分为与计算机有关的优化和与计算机无关的优化。,优化可在编译的不同阶段进行,对同一阶段,涉及的程序范围也有所不同,在同一范围内,可进行多种优化。目前编译程序的优化工作一般是在中间代码生成之后和(或)目标代码生成之后进行。如图11.1所示。,中间代码的优化是对中间代码进行等价变换。目标代码的优化是在目标代码生成之后进行的,因为生成的目标代码对应于具体的计算机,因此,这一类优化在很大程度上依赖于具体的机器,我们不做详细讨论。,另外依据优化所涉及的程序范围,又可分为局部优化、循环优化和全局优化三个不同
4、的级别。局部优化指的是在只有一个入口、一个出口的基本程序块上进行的优化。循环优化是对循环中的代码进行的优化。全局优化是在整个程序范围内进行的优化。,编译程序的优化工作旨在生成较好性能的目标代码,为此,编译程序需要对代码(中间代码或目标代码)进行各种方式的变换。变换的宗旨是:,等价经优化工作变换后的代码运行结果应与原来程序运行结果一样。,有效经优化工作变换后的代码应运行时间较短,占用的存储空间较小。,合算获得较好性能的目标代码是优化工作的意图,而优化本身包括大量的代码分析和变换工作,这里有个权衡:应尽可能以较低的代价取得较好的优化效果。,11.1 代码优化技术,常用的优化技术有:删除多余运算;循
5、环不变代码外提;强度削弱;变换循环控制条件;合并已知量与复写传播;删除无用赋值。为了说明这些常用的优化技术,我们来看下面这个例子。,例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、的目标代码较少而执行速度较快。四元式(6)变换成:T4=T1。这种优化称为删除多余运算或称为删除公共子表达式。,图11.2 中间代码段,2)代码外提,减少循环中代码总数的一个重要办法是循环不变代码外提。这种变换把循环不变运算,即其结果独立于循环执行次数的表达式,提到循环的前面,使之只在循环外计算一次。上例中,我们可以把四元式(4)和四元式(7)提到循环外。经过删除多余运算和代码外提后,代码变换成图11.3。,图11.3 删除公共子表达式和代码外提,3)强度削弱,强度削弱的思想是把强度大的运算换算成强度小的运算。循环中计算T1值的乘法运算变换成在循环前进行一次乘法运算,而在循环中将其变换成加法运
7、算。变换后如图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
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可看出,经过优化后的代码的执行效率提高了很多。当然,实现这些优化的一系列工作是非常复
9、杂的,代价也是很大的。,图 11.6 删除无用赋值,11.2 局部优化,我们所说的局部优化是指基本块内的优化。,所谓基本块,是指程序中一个单入口、单出口的线性程序块(顺序执行的语句序列)。,控制流只能从其入口语句进入,从其出口语句退出,没有中途停止或分支。,局部优化工作包括对于一个给定的程序,把它划分为一系列的基本块,在各个基本块范围内分别进行优化。,局限于基本块范围内的优化称为基本块内的优化,也称为局部优化。,11.2.1 基本块的划分,我们先定义基本块的入口语句。 所谓入口语句有三种,就是: 程序的第一个语句; 条件转移语句或无条件转移语句的转移目标语句; 紧跟在条件转移语句后面的语句。,
10、有了入口语句的概念之后,我们就可以给出划分中间代码(四元式程序)为基本块的算法。,划分中间代码(四元式程序)为基本块的算法:, 求出四元式程序中各个基本块的入口语句。 对每一入口语句,构造其所属的基本块。它是由该入口语句到下一入口语句(不包括下一入口语句),或到一转移语句(包括该转移语句),或到一停语句(包括该停语句)之间的语句序列组成的。 凡未被纳入某一基本块的语句、都是程序中控制流程无法到达的语句,因而也是不会被执行到的语句,可以把它们删除。,我们以下述四元式程序为例来说明如何划分基本块的。例11.1:有四元式程序如下,构造其基本块。(1) read (C)(2) A:= 0(3) B:=
11、 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
12、(A)(9) halt,基本块:语句(1),(2)和(3)构成第一个基本块;语句(4)和(5)构成第二个基本块;语句(6)和(7)构成第三个基本块;语句(8)和(9)构成第四个基本块。,11.2.2 基本块内的优化变换,很多优化变换可作用于基本块而不改变它计算的表达式集合,这样的变换对改进代码的质量是很有用的。有两类重要的局部等价变换可用于基本块;它们是保结构的变换和代数变换。,基本块的主要保结构变换是:删除公共子表达式删除无用代码重新命名临时变量交换语句次序,对于删除公共子表达式和删除无用代码这两种优化技术,我们在11.1中已经讨论过,这里简单介绍重新命名临时变量和交换语句次序是什么含义。重
13、新命名临时变量:假如有语句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的指数算符通常要用函数调用来实现,使用代数变换,这个语句可由快
14、速、等价的语句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 *
15、 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
16、:= 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的
17、后继(子结)。又称任一有向边序列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:,图的叶结
18、点,即无后继的结点,以一标识符(变量名)或常数作为标记,表示这个结点代表该变量或常数的值。如果叶结点用来代表某变量A的地址,则用addr(A)作为这个结点的标记。通常把叶结点上作为标记的标识符加上下标0,以表示它是该变量的初值。图的内部结点,即有后继的结点,以一运算符作为标记,表示这个结点代表应用该运算符对其后继结点所代表的值进行运算的结果。图中各个结点上可能附加一个或多个标识符,表示这些变量具有该结点所代表的值。,上述这种DAG可用来描述计算过程,又称为描述计算过程的DAG。在以下的讨论中,我们简称为DAG。,基本块的DAG表示与构造:,一个基本块,可用一个DAG来表示。下面列出各种四元式及
19、相对应的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)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 11 代码 优化 ppt 课件
链接地址:https://www.31ppt.com/p-1353952.html