西北工业大学编译原理课件第八章 代码优化.pptVIP

第八章 代码优化 为了让编译程序能够生成效率高的目标代码，应对中间代码进行优化 注意：优化≠最佳化 要求：相对合理性。应考虑空间和时间上的取舍，及二者的平衡。 本章将介绍语法制导翻译阶段的代码优化、线性窥孔(peep-hole)优化、基于结构信息的优化三种类型。 假定 优化对象是四元式序列的中间代码 8.1 语法制导翻译阶段的优化 在进行语法制导翻译的过程中,通过对原文法的改造,可以生成效率较高的代码. 例如,对于一些标准函数(strcpy(s1,s2), sin(x)等)的调用,可按一般函数调用来处理: fc_call → fc_nm ( )| fc_nm(P_list) P_list → P_list , param |param 也可将这类特殊函数直接作为表达式处理,从而省去参数传递、现场保护、转子及返回指令、恢复现场等操作: expr → STRCPY ( expr , expr ) 这类优化一般适用于用于特殊目的的专用语言. 8.2 线性窥孔优化 考查C程序段 int i;…;i=5;++i; return i+1; 翻译生成的中间代码为(类C-code): i=5; i+=1; T1=i; T1 =i; T1 +=1; ret_reg=T1; ret; 上述代码中有两个相同的赋值语句,它们是由于翻译时未考虑前后文环境,对++i和return i+1进行翻译的结果,显然二者之一可以删除. 由于这样的优化涉及到多个语句,在语法制导翻译阶段不可能进行,而窥孔优化可完成此工作. 窥孔优化的基本思想 窥孔优化的基本思想是,考察编译器所生成的中间代码(或目标代码)中相邻指令,将其中的某些组合替换为效率更高的指令组. 线性窥孔优化的特点: 优化的对象可以是中间代码,也可以是目标代码; 每次处理的是一组相邻的指令,仿佛将其暴露在一观察窗口 (窥孔)中; 对优化对象进行线性扫描. 窥孔优化项目有:强度削弱、常数合并、无用代码删除、寄存器分配等 8.2.1 强度削弱 ~是指用执行效率较高的等价地替换原操作. 例如,乘(或除)以2的n次方的运算可用左(或右)移n位实现(X*8等价于X3);类似地,以2的n次方为模的求模运算可用按位与实现(X%8==X7). 另外,用加法代替乘法也可提高效率.如x*=3可替换为:t=x; x+=t; x+=t;联合使用移位和加法,可以削弱乘法的强度:x*=9可替换为 t=x; t=3; x+=t; 即x*9 = x*8+x = (x3)+x 上述优化与具体的运算对象的值有关,有时会得不偿失,应权衡各方面的因素. 对于非算术运算也可削弱强度,如尽量多使用寄存器,少访问内存(或外存)等. 8.2.2 常数合并和常数传播 常数合并是指在编译时就将源程序中常数表达式之值先行算出,不必生成计算该表达式的代码. 例如, a+2*3可翻译成a+6. 表达式a+1+3在翻译阶段生成的代码为: T1=a; T1+=1; T1+=3;由于对T1的两次定值未被引用,可将其修改为: T1=a; T1+=4; 常数传播是指在程序运行时某段程序中的一些变量之值保持不变,故在此范围内对该变量的引用可替换对其值的直接引用,传播将一直延续到对其重新定值 例如, a=3; …/*未对a重新定值*/; b=a; 可改为: a=3;…;b=3; 8.2.3 无用变量与无用代码的删除 变量的最后一次引用到下次引用之前的最近一次赋值期间,可视为无用变量.在变量的无用期内,对其的任何赋值均可删除. 例如: t0=a;t0+=5; x=t0;…;t0+=1;…t0=b;其中的赋值t0+=1可被删除. 对于那些被赋值后从未被引用的变量,其赋值操作是无用赋值,可删除之. 无用代码是指控制永远到达不了的代码: if(0) {…},花括号内为无用代码. 联合使用常数传播与删除无用代码 无用代码的删除还会受常数传播的影响,例如, fool(){int i,j,array[10]; i=5;++i; j=array[i]; …} 其中,i并不是无用变量,但利用常数传播优化后: fool(){int i,j,array[10];i=5;++i; j=array[6];…} i变为无用变量,删除后程序为 fool(){int j,array[10]; j=array[6];…} 注意,对于与硬件相关的量(如监视I/O端口的变量),我们不能使用上述优化方案 (见P291-P292的例子).在C中可用关键字volatile(指明该变量的值不确定)屏蔽这类优化. 8.2.4 窥孔优化实例 例 对C程序: i=5; ++i; return i+1;编译程序产生的中间代码为: i=5; i+=1; T1=i; T1=i; T1+=1; ret_reg=T1; re