代码优化哈工大王宏志

《代码优化哈工大王宏志》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章代码优化优化的概念编译时刻为改进目标程序的质量而进行的各项工作。空间效率时间效率空间效率和时间效率有时是一对矛盾，有时不能兼顾。优化的要求：必须是等价变换为优化的努力必须是值得的。有时优化后的代码的效率反而会下降。优化的分类机器相关性：机器相关优化：寄存器优化，多处理器优化，特殊指令优化，无用指令消除等。无关的优化：优化范围：局部优化：单个基本块范围内的优化，常量合并优化，公共子表达式删除，计算强度削弱和无用代码删除。全局优化：主要是基于循环的优化：循环不变优化，归纳变量删除，计算强度削减。优化语言级：优化语言级：针对中间代

2、码，针对机器语言。代码优化程序的结构控制流分析的主要目的是分析出程序的循环结构。循环结构中的代码的效率是整个程序的效率的关键。数据流分析进行数据流信息的收集，主要是变量的值的获得和使用情况的数据流信息。到达-定义分析；活跃变量；可用表达式；代码变换：根据上面的分析，对内部中间代码进行等价变换。控制流分析数据流分析代码变换基本块和流图基本块中，控制流是由第一个四元式进入，到达最后一个四元式离开。流图：把一个程序的中间表示中所有的基本块作为节点集合。有边从节点n到节点n’当且仅当控制流可能从n的最后的一个四元式到达n’的第一个四元式。

3、首节点：对应的基本块的第一个四元式是程序的第一个四元式。流图的构造以所有的基本块为节点集合。有B1到B2的边（B2是B1的后继）当且仅当：B1的最后一个四元式有条件或无条件地转移到B2的第一个四元式。B2是紧紧跟随在B1后面的四元式，且B1的最后四元式不是无条件转向语句。流图的例子在转移语句中，目标标号转变称为基本块的编号，可以避免因为四元式的变动而引起的麻烦。=1_i=1_f=0_a>=i10B4=f_b+fat1=t1_f=b_a+i1t2=t2_iGOB2=ffibB1B2B3B4基本块的优化常量合并公共子表达式删除强度削弱

4、无用代码删除常量合并例子：l=2*3.14*r*23.14t1*t1rt2=t2l2*3.1415926的值在编译时刻就可以确定。*6.28rt2=t2l公共子表达式删除+bca-adb+bcc-add显然，第2和4个四元式计算的是同一个值，所以第四个四元式可以修改为=b_d。对于第1和3个四元式，虽然都是计算b+c，但是他们的值其实是不同的，所以不能完成处理。公共子表达式：如果某个表达式先前已经计算，且从上次计算到现在，E中的变量的值没有改变。那么E的这次出现就称为公共子表达式。利用先前的计算结果，可以避免对公共子表达式的重复计

5、算。例子x+y*t-a*(x+y*t)/(y*t)*ytt1+xt1t2*ytt3+xt3t4*at4t5*ytt6/t5t1t7-t2t7t8消除公共子表达式之后：*ytt1+xt1t2*at2t5/t5t1t7-t2t7t8强度削弱实现同样的运算可以有多种方式。用计算较快的运算代替较慢的运算。X2变成x*x。2*x或2.0*x变成x+xx/2变成x*0.5anxn+an-1xn-1+…+a1x+a0变成((…(anx+an-1)x+an-2)…)x+a1)x+a0无用代码删除如果四元式opxyz之后，z的值再也没有被使用到，那

6、么这个四元式是无用的。无用的四元式往往意味着程序的错误，一般不会出现在正确的程序里面。多数无用四元式是由优化引起的。=t1t3，如果我们尽量用t1替代t3，可能使t3不被使用，从而这个四元式称为无用的四元式。等价变换的分类保结构等价变换删除公共子表达式和删除无用代码，重新命名临时变量和交换独立四元式的顺序等。+xyt变成+xyu+abt1+xyt2变成+xyt2+abt1代数等价变换利用了代数恒等性质，强度削弱。2x=x+x,Bandtrue=B.需要考虑双目运算符的可交换特性。基本块优化的实现基本块内部优化的实现的主要工具为DA

7、G图。用DAG图表示各个值的计算/依赖关系。图中的标记：叶子节点的标记为标识符（变量名）或常数作为唯一的标记。叶子节点是标识符时，用下标0表示它时初值。内部节点用运算符号作为标记，表示计算的值。每个节点的值都可以用关于变量初始值的表达式表示。各节点可能附加有一个或者多个标识符。同一个节点的标识符表示相同的值。DAG图的例子+bca-adb+bcc-add+-+b0c0d0b,da四元式的分类0型：=x_y1型：opx_y(单目运算）2型：opxyzrelopxyz(z是序号)基本块DAG图构造算法输入：一个基本块输出：相应DAG图

8、算法说明：通过逐个扫描四元式来逐步建立DAG图。函数node(x)表示和标识符x相应的最近建立的节点。他代表扫描到当前的四元式的时候，标识符x的值对应的节点。步骤1：初始化：无任何节点，node对任何标识符无定义。步骤2：依次对基本块中的每个四元式