sun编译原理第7章代码优化(第22-23讲).ppt

《sun编译原理第7章代码优化(第22-23讲).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、7.1优化概述源程序经过词法分析、语法分析、语义分析等阶段的编译工作，得到与源程序功能等价的中间代码。但是，由于这种中间代码是“机械生成”的，必然存在效率不高，有冗余代码的现象，还需进行代码的优化。代码优化的含义是：对代码进行等价变换，使得变换后的代码具有更高的时间效率和空间效率。代码优化的目的是：提高目标代码的质量。代码优化与机器无关的优化——在中间代码上进行与机器有关的优化（窥孔优化）——在目标代码上进行局部优化循环优化全局优化10/16/20211信息学院孙丽云t1=i*5;t2=t1+6;t3=i*5;t4=b/t3;t5=t2-t4;a=t5t1=i*5;t2=t1+6;t

2、3=t1;t4=b/t3;t5=t2-t4;a=t5局部优化技术■删除公共子表达式a=i*5+6–b/(i*5);10/16/20212信息学院孙丽云t1=56;t2=t1–b;a=t2;■常数合并a=10*5+6-b;t1=10*5;t2=t1+6;t3=t2-b;a=t3;10/16/20213信息学院孙丽云t4=0;f0=t4;t5=1;f1=t5;t6=2;i=t6;f0=0;f1=1;i=2;■常数传播10/16/20214信息学院孙丽云x+0=x0+x=xx*1=x1*x=x0/x=0x-0=xb&&true=bb&&false=falseb

3、

4、true=trueb

5、

6、f

7、alse=b■代数简化10/16/20215信息学院孙丽云i*2=2*i=i+i=i<<1（“<<”为C语言中的移位运算符，表示左移一位）b)i/2=(int)(i*0.5)c)0-1=-1d)f*2=2.0*f=f+fe)f/2.0=f*0.5■降低运算强度10/16/20216信息学院孙丽云基本块：是指程序中顺序执行的语句序列。基本块内的语句要么全执行，要么全不执行，而不能只执行一部分。基本块只有一个入口和一个出口，只能从入口进入，出口退出，不存在转入、分支等操作。局部优化——基本块内的优化例：下面的三地址语句序列组成了一个基本块。T1=a*aT2=T1+aT3=5+T2为了叙述

8、方便，本章将四元式写成更为直观的三地址代码形式。10/16/20217信息学院孙丽云基本块的入口可能是下述3种情况之一：(1)程序的第一个语句；(2)转移的目标语句；(3)条件语句之后的第一个语句。基本块的出口可能是下述3种情况之一：(1)下一个入口语句的前导语句；(2)转移语句；(3)停语句。■基本块的入口10/16/20218信息学院孙丽云■划分基本块的算法1.求基本块的入口语句；2.求基本块的出口语句；3.凡未被纳入某一基本块的语句，都是程序中控制流程无法到达的语句，因而也是不会被执行到的语句，把它们删除。10/16/20219信息学院孙丽云例：对下列语句划分基本块(1)rea

9、d(C)(2)A:=0(3)B:=1(4)L1:A:=A+B(5)ifB>=CgotoL2(6)B:=B+1(7)gotoL1(8)L2:write(A)(9)halt解：划分成四个基本块B1，B2，B3，B4(1)(2)(3)(4)(5)(6)(7)(8)(9)B1B2B3B4B>=CB

10、*Bif(C100)gotoL2haltL2:F=F-1gotoL119F=F+110/16/202111信息学院孙丽云■思考有语句如下：while(A

11、

12、C&&E)if(x==0)x=y*z;elsex=y+z;z=x;（1）求其四元式序列；（2）对四元式序列划分基本块且画出程序流图。10/16/202112信息学院孙丽云■基本块的DAG表示及其应用DAG是一种有向无环图，常用来对基本块进行优化。基本块内一般可实行3种优化：合并已知量、删除无用赋值、

13、删除公共子表达式（删除多余运算）。利用DAG进行基本块优化的基本思想：首先顺序对一个基本块内的所有四元式构造成一个DAG，接着按构造结点的次序将DAG还原成四元式序列。构造DAG的同时已做了局部优化，所以最后得到的四元式序列已经得到了优化。10/16/202113信息学院孙丽云基本块的DAG是在结点上带有如下标记的DAG：图的叶结点（无后继的结点）：以一标识符（变量名）或常数作为标记，表示该结点代表该变量或常数的值。图的内部结点（有后继的结点）：以运算符作