十章节代码优化演示教学.ppt

第十章代码优化优化的概念编译时刻为改进目标程序的质量而进行的各项工作。空间效率时间效率空间效率和时间效率有时是一对矛盾,有时不能兼顾。优化的要求:必须是等价变换(保持功能)为优化的努力必须是值得的。有时优化后的代码的效率反而会下降。优化的分类机器相关性机器相关优化:寄存器优化,多处理器优化,特殊指令优化,无用指令消除等。机器无关优化:优化范围局部优化:单个基本块范围内的优化,常量合并优化,公共子表达式删除,计算强度削弱和无用代码删除。全局优化:主要是基于循环的优化:循环不变优化,归纳变量删除,计算强度削减。优化语言级优化语言级:针对中间代码,针对机器语言。代码优化程序的结构控制流分析的主要目的是分析出程序的循环结构。循环结构中的代码的效率是整个程序的效率的关键。数据流分析进行数据流信息的收集,主要是变量的值的获得和使用情况的数据流信息。到达-定义分析;活跃变量分析;可用表达式分析;代码变换:根据上面的分析,对内部中间代码进行等价变换。控制流分析数据流分析代码变换流图的构造以所有的基本块为节点集合。有B1到B2的边(B2是B1的后继)当且仅当:B1的最后一个四元式有条件或无条件地转移到B2的第一个四元式。B2是紧紧跟随在B1后面的四元式,且B1的最后四元式不是无条件转向语句。流图的例子本节所用的例子i=m1;j=n;v=a[n]; (1)i:=m1while(1){ (2)j:=ndoi=i+1;while(a[i]<v); (3)t1:=4*ndoj=j1;while(a[j]>v); (4)v:=a[t1]if(i>=j)break; (5)i:=i+1x=a[i];a[i]=a[j];a[j]=x; (6)t2:=4*i} (7)t3:=a[t2]x=a[i];a[i]=a[n];a[n]=x;(8)ift3>vgoto(5)流图的例子本节所用的例子i=m1;j=n;v=a[n]; (9)j:=j1while(1){ (10)t4:=4*jdoi=i+1;while(a[i]<v); (11)t5:=a[t4] doj=j1;while(a[j]>v);(12)ift5>vgoto(9)if(i>=j)break; (13)ifi>=jgoto(23)x=a[i];a[i]=a[j];a[j]=x; (14)t6:=4*i} (15)x:=a[t6]x=a[i];a[i]=a[n];a[n]=x;...流图的例子i:=m1j:=nt1:=4*nv:=a[t1]i:=i+1t2:=4*it3:=a[t2]ift3>vgotoB2B1B2j:=j1t4:=4*jt5:=a[t4]ift5>vgotoB3ifi>=jgotoB6B4B3B5B6基本块的优化公共子表达式删除复制传播常量合并无用代码删除强度削弱