编译原理与技术讲义-第11章.ppt

《编译原理与技术讲义-第11章.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、编译原理与技术第11章代码优化青岛大学信息工程学院主要内容优化的概念代码优化的基本技术局部优化机器代码优化－窥孔技术编译原理与技术211.1代码优化的概念代码优化在整个编译过程的位置编译前端中间代码优化目标代码生成中间代码生成源程序目标程序中间代码中间代码目标代码优化中间代码编译前端编译器可以改进过程调用、循环和地址计算目标代码生成中间代码源程序目标程序程序员可以改进算法，改变循环编译器可以利用寄存器，选择指令和窥孔优转换程序员和编译器可能改上程序的位置编译原理与技术311.1代码优化的概念设计和实现编译程序代码优化的原则：（1）等价原则：经过优化后的代码应该保持程序的输入输出，不应改变程序

2、运行的结果。（2）有效原则：优化后的代码应该在占用空间、运行速度这两个方面，或者其中的一个方面得到改善。（3）经济原则：代码优化需要占用计算机和编译程序的资源，代码优化取得的效果应该超出优化工作所付出的代价。否则，代码优化就失去了意义。编译原理与技术411.1代码优化的概念代码优化依据机器相关性、优化范围和优化语言级别的分类按照与机器相关的程度，可以分为与机器相关的代码优化和与机器无关的代码优化。与机器相关的优化一般有寄存器的优化、多处理器的优化、特殊指令的优化以及无用指令的消除等技术。显然，这几类优化与具体机器的特性密切相关，例如寄存器的总数，寄存器的具体使用规定，等等。这类优化通常的在目

3、标代码生成之后进行。与机器无关的优化是在目标代码生成以前进行，主要是根据程序的控制信息和数据信息，对程序进行优化，与机器无关。编译原理与技术511.1代码优化的概念根据优化的范围，可以划分为局部优化和全局优化两类。考察一个基本块的三地址中间代码序列就可以完成的优化，称为局部优化。而全局优化则必须在考察基本块之间的相互联系与作用的基础上才能完成。代码优化总是在内部的中间代码和目标代码上进行的。在通常的编译程序中，代码优化往往是在中间代码这一级执行，例如对源程序的三地址代码或抽象语法树上采取优化措施。相对于在目标代码级别的优化，在中间代码优化的好处是：（1）容易从中间代码中识别处进行优化的情况，

4、对目标语言代码的信息识别要困难，成本较高；（2）中间代码于机器无关，因此，一个代码优化的程序可以适用于多种型号的机器。有时也在目标代码语言级上进行代码优化，如寄存器优化等。在目标代码级别上进行全局优化的代价昂贵，本书仅仅讨论局部范围的目标代码优化技术，即所谓的窥孔优化。编译原理与技术611.2代码优化的基本技术分类：与机器无关的、在中间代码语言级的代码优化主要包括：删除公共子表达式复写传播删除无用代码代码外提强度消弱删除归纳变量其中最后三种是专门针对循环语句的优化。编译原理与技术711.2代码优化的基本技术voidquicksort(m,n)intm,n;{inti,j,v,x;if(n<=

5、m)return;/*程序段开始*/i=m－1;j=n;v=a[n];while(1){doi=i＋1;while(a[i]v);if(i>=j)break;x=a[i];a[i]=a[j];a[j]=x;}x=a[i];a[i]=a[n];a[n]=x/*程序段结束*/quicksort(m,j);quicksort(i+1,n);}图11.3快速排序的C代码(1)i:=m－1(2)j:=n(3)t1:=4n(4)v:=a[t1](5)i:=i＋1(6)t2:=4i(7)t3:=a[t2](8)ift3>vgoto(5)(9)j:=j－1(

6、10)t4:=4j(11)t5:=a[t4](12)ift5>vgoto(9)(13)ifi>=jgoto(23)(14)t6:=4i(15)x:=a[t6](16)t7:=4i(17)t8:=4j(18)t9:=a[t8](19)a[t7]:=t9(20)t10:=4j(21)a[t10]:=x(22)goto(5)(23)t11:=ai(24)x:=a[t11](25)t12:=4i(26)t13:=4n(27)t14:=a[t12](28)a[t12]:=t14(29)t15:=4n(30)a[t15]:=x图11.4快速排序部分程序的三地址代码编译原理与技术811.

7、2代码优化的基本技术删除公共子表达式i:=m－1j:=nt1:=4nv:=a[t1]t11:=4ix:=a[t11]t12:=4it13:=4nt14:=a[t12]a[t12]:=t14t15:=4na[t15]:=xi:=i＋1t2:=4it3:=a[t2]ift3>vgotoB1ifi>=jgotoB6B1B2B4j:=j－1t4:=4jt5:=a[t4]ift5>vgotoB3t6:=4