编译原理——编译程序构造实践教程 教学课件 作者 张幸儿 戴新宇 701编译程序构造与实践教程第七章.ppt

《编译原理——编译程序构造实践教程 教学课件 作者 张幸儿 戴新宇 701编译程序构造与实践教程第七章.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第七章中间表示代码与代码优化7.1概况7.1.1代码优化与代码优化程序•代码优化的必要性假定有下列C语言语句序列：a=b+c*d;e=a+c*d;按第六章相应翻译方案将生成目标代码(左边)如下：MOVc,R1cR1MOVc,R0cR0MPYd,R1c*dR1MPYd,R0c*dR0MOVb,R0bR0MOVR0,R1c*dR1ADDR1,R0b+c*dR0ADDb,R0b+c*dR0MOVR0,aR0aMOVR0,ab+c*daMOVc,R1cR1ADDR0,R1a+c*dR1MPYd,R1c*dR1MOVR1,ea+c*

2、deMOVa,R0aR0ADDR1R0a+c*dR0（手工生成）MOVR0,ea+c*de试比较两者的功效。又如，设有if语句if(a+b>0)x=(a+b)*2;elsex=(a+b)/2;按第六章相应翻译方案将生成下列目标代码：(1)MOVa,R0(10)MOVR2,x(2)ADDb,R0(11)GOTO(17)(3)CMPR0,#0(12)MOVa,R3(4)CJ>(6)(13)ADDb,R3(5)GOTO(12)(14)MOVR3,R4(6)MOVa,R1(15)DIV#2,R4(7)ADDb,R1(16)MOVR4,x(8)MOV

3、R1,R2(17)(9)MPY#2,R2如果用手工编写，将会有如下的代码：(1)MOVa,R0(5)MPY#2,R0(2)ADDb,R0(6)GOTO(8)(3)CMPR0,#0(7)DIV#2,R0(4)CJ≤(7)(8)MOVR0,x两者相比，前者的目标指令数多达16条，竟是后者的两倍，且临时变量（寄存器）5个。编译程序只考虑共性，不能考虑个性，生成的目标代码必然是质量不高的，•改进程序的运行效率的途径通常有4种：改进算法、利用系统提供的库程序、源程序级程序变换、编译时刻代码优化、这里，代码优化指的是：编译时刻为改进目标程序的质量而进行的代码优

4、化。代码优化指的是编译时刻为改进目标程序质量而进行的各项工作。目的是改进目标程序质量，包括减少存储空间与缩短运行时间。代码优化的思路是：在语义分析时仅生成中间表示代码,对中间表示代码进行优化，从优化了的中间表示代码生成目标代码，然后再对目标代码进行小范围的优化，即，所谓的窥孔优化。编译程序中完成代码优化工作的部分称为代码优化程序。代码优化程序的输入是语义分析阶段生成的某种中间表示代码。代码优化程序的输出是改进了的中间表示代码。中间表示代码的种类包括：四元式序列三元式序列抽象语法树逆波兰表示重点讨论四元式序列。7.1.2代码优化的分类从下列三个角度分

5、类。1.与机器相关性分为：与机器相关的和与机器无关的与机器相关的优化一般有涉及寄存器的优化、多处理器的优化、特殊指令的优化及消除无用指令的优化等4类。2.优化范围分为：局部优化和全局优化对基本块的优化(局部优化):合并常量计算、消除公共子表达式、削减计算强度、删除无用代码对循环的优化(全局优化)：循环不变表达式外提、归纳变量删除、计算强度削减。3.优化语言级分为：内部中间表示级和目标代码级通常代码优化是在中间表示代码一级上进行；在目标代码级上进行的优化特称为窥孔优化。控制流分析数据流分析代码变换概括起来，本章讨论的重点是在中间表示代码级上的、与机器

6、无关的局部优化和全局优化。代码优化程序通常由三个部分组成，即，控制流分析、数据流分析与代码变换。示意图如下所示。控制流分析：基于流图，识别出循环结构。数据流分析：进行数据流信息的收集(包括到达_定值、活跃变量与可用表达式等)代码变换：对中间表示代码进行等价变换，完成对基本块的局部优化、与循环相关的优化及全局优化，最终完成代码优化。7.2源程序的中间表示代码中间表示代码可以是：抽象语法树、逆波兰表示、四元式序列、三元式序列。重点讨论四元式序列。7.2.1四元式序列1.表示法约定四元式：运算符运算分量运算分量结果例表达式x+y*z的四元式序列是：运算符

7、运算分量运算分量结果*+yxzt1t1t2对于双目运算xopy的四元式：OPxyt对于单目运算OPx：OPxt对于赋值语句x=y：:=yx与&:=yx(前者是通常的赋值，后者是间接赋值)对于转向语句gotoL：GOLL对于按关系运算符relop：relopxyL(xrelopy为真时控制转向L为标号的四元式)对于无条件控制转移到序号为L：GOL对于函数调用语句p(x1,x2,…,xm)：PARAMx1PARAMx2…PARAMxmCALLpm若是函数有返回值,则呈下形：CALLpmt其中，t中存放回送结果。关于一维数组元素A[i]的四元式表示。例A

8、[j]=B[k+m]的四元式表示如下：(1)+kmt2(2)=[]Bt2t3(3)[]=Ajt1(4)&:=t3t1其中，