第八章代码优化 ·为了让编译程序能够生成效率高的目标代码，应 对中间代码进行优化 ·注意：优化最佳化 要求：相对合理性。应考虑空间和时间上的取舍， 及二者的平衡。 ·本章将介绍语法制导翻译阶级的代码优化、线性 窥孔(peep-hole)优化、基于猪构信复的优化三种 类型。 假定优化对象是四元式序列的中间代码
第八章 代码优化 • 为了让编译程序能够生成效率高的目标代码，应 对中间代码进行优化 • 注意：优化≠最佳化 • 要求：相对合理性。应考虑空间和时间上的取舍， 及二者的平衡。 • 本章将介绍语法制导翻译阶段的代码优化、线性 窥孔(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.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线性窥孔优T化 ·考查C程序段 int i;...;i=5;++i;return i+1; ·翻译生成的中间代码为（类C-code): i=5;i+=1;T=i;T=i;T+=1;ret_reg=T1;ret; ·上述代码中有两个相同的赋值语句，它们是由于翻 译时未考虑前后文环境，对++i和return i+1进行翻 译的结果，显然二者之一可以删除 ● 由于这样的优化涉及到多个语句，在语法制导翻译 阶段不可能进行，而窥孔优化可完成此工作
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进行翻 译的结果,显然二者之一可以删除. • 由于这样的优化涉及到多个语句,在语法制导翻译 阶段不可能进行,而窥孔优化可完成此工作
窥子孔优化的基本思想 窥好孔优化的基本恩想是，考察编译器所生成的中 间代码（或目标代码）中相邻指令，将其中的某些组 合替换为效率更高的指令组. ● 线性窥子孔优化的特点： 1.优化的对象可以是中间代码，也可以是目标代码： 2.每次处理的是一组相邻的指令，仿佛将其暴露在一观 察窗☐（窥孔）中； 3.对优化对象进行线性扫描 窥子孔优化项目有：强度削弱、常数合并、无用代 码册别除、寄存器分配等
窥孔优化的基本思想 • 窥孔优化的基本思想是,考察编译器所生成的中 间代码(或目标代码)中相邻指令,将其中的某些组 合替换为效率更高的指令组. • 线性窥孔优化的特点: 1. 优化的对象可以是中间代码,也可以是目标代码; 2. 每次处理的是一组相邻的指令,仿佛将其暴露在一观 察窗口 (窥孔)中; 3. 对优化对象进行线性扫描. • 窥孔优化项目有:强度削弱、常数合并、无用代 码删除、寄存器分配等
8.2.1强度)3 ~是指用执行效率较高的等价地替换原操作 例如，乘（或除）以2的次方的运算可用左（或右）移位实现 置8等价于X<<3);类似地，以2的次方为模的求模运算可用 按位与实现X%8==X&7). ·另外，用加法代替乘法也可提高效率如=3可替换为： +=+=t联合使用移位和加法，可以削弱乘法的强度=9 可替换为【=<<=3：+t即x*9=X*8+x=(X<<3)+X ·上述优化与具体的运算对象的值有关，有时会得不偿失，应 权衡各方面的因素. 对于非算术运算也可削弱强度，如尽量多使用寄存器，少访 问内存（或外存）等
8.2.1 强度削弱 • ~是指用执行效率较高的等价地替换原操作. • 例如,乘(或除)以2的n次方的运算可用左(或右)移n位实现 (X*8等价于X<<3);类似地,以2的n次方为模的求模运算可用 按位与实现(X%8==X&7). • 另外,用加法代替乘法也可提高效率.如x*=3可替换为:t=x; x+=t; x+=t;联合使用移位和加法,可以削弱乘法的强度:x*=9 可替换为t=x; t<<=3; x+=t; 即x*9 = x*8+x = (x<<3)+x • 上述优化与具体的运算对象的值有关,有时会得不偿失,应 权衡各方面的因素. • 对于非算术运算也可削弱强度,如尽量多使用寄存器,少访 问内存(或外存)等
8.2.2常数合并和常数传播 ·常数合并是指在编译时就将源程序中常数表达式之值先行 算出，不必生成计算该表达式的代码. ·例如，a+23可翻译成a+6.表达式a+1+3在翻译阶段生成的代 码为：TT1+=T1+=3由于对T1的两次定值未被引用，可将 其修改为：TTt=4 ·常数传播是指在程序运行时某段程序中的一些变量之值保 持不变，故在此范围内对该变量的引用可替换对其值的直接 引用，传播将一直延续到对其重新定值 例如，a=3;-未对a重新定值：b=;可改为：a=3:-3；
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可被删除 ·对于那些被赋值后从未被引用的变量，其赋值操作是无用赋 值，可删除之 。 无用代码是指控制永运到达不了的代码：f(0){【},花括号 内为无用代码
8.2.3 无用变量与无用代码的删除 • 变量的最后一次引用到下次引用之前的最近一次赋值期间, 可视为无用变量.在变量的无用期内,对其的任何赋值均可 删除. • 例如: t0=a;t0+=5; x=t0;…;t0+=1;…t0=b;其中的赋值 t0+=1可被删除. • 对于那些被赋值后从未被引用的变量,其赋值操作是无用赋 值,可删除之. • 无用代码是指控制永远到达不了的代码: if(0) {…},花括号 内为无用代码
联合使用常数传播与册除无用代马 ·无用代码的删除还会受常数传播的影响，例如， fool(fint i,j,array[10];i=5;++i;j=array[i];... ·其中，并不是无用变量，但利用常数传播优化后： fool()fint i,j,array[10];i=5;++i;j=array[6];...} ·变为无用变量，删除后程序为 fool()fint j,array[10];j=array[6];...} 注意，对于与硬件相关的量（如监视/0端口的变量），我们不 能使用上述优化方案（见P291-P292的例子）.在C中可用关 键字volatile(指明该变量的值不确定)屏蔽这类优化
联合使用常数传播与删除无用代码 • 无用代码的删除还会受常数传播的影响,例如, 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;ret; 首先建立一以变量名为关键字的符号表，其中每个变量的登记 项含有当前可确定的内容； 1.第一遍扫描完成计算常数表达式的值，修改符号表相关内容， 将变量引用改为对其值的引用： 读第一行时，表中建立的登记项，初值为5；再读第二行，因1 已登记，修改其值，得代码：=5；=6； 现在，读第三，四行，此时==6，于是将对的引用改为对其值 的引用：T1=6;T1=6;
8.2.4 窥孔优化实例 • 例 对C程序: i=5; ++i; return i+1;编译程序产生的中间代 码为: i=5; i+=1; T1=i; T1=i; T1+=1; ret_reg=T1; ret; 首先建立一以变量名为关键字的符号表,其中每个变量的登记 项含有当前可确定的内容; 1.第一遍扫描完成计算常数表达式的值,修改符号表相关内容, 将变量引用改为对其值的引用: 读第一行时,表中建立 i的登记项,初值为5;再读第二行,因i 已登记,修改其值,得代码:i=5;i=6; 现在,读第三,四行,此时i==6, 于是将对i的引用改为对其值 的引用:T1=6;T1=6;
此时在表中建立T的登记项，值为6；读第五行，变量T被再 定值，修改其登记项内容及输出T=7; 扫描第六行，T,的当前值为7：ret_reg=7; 最后一行无变量，不变.最后得 i=5;i=6;T=6;T=6;T=7;ret_reg=7;ret; 2.第二遍扫描完成无用变量的删除： 清除符号表登记项，扫描代码，对作为源操作数出现的每个 变量，在表中建立相应的项， 显然扫描完后所有以目的操作数形式出现，且在表中无登 记项的变量都是无用的，相应的操作可删去.本例中，T1是无 用的，其相关操作均可删除得： i=5;i=6;ret_reg=7;ret; 注意：由于是用户定义的变量，无法断定其是否不再引用， 不能作为无用变量：
此时在表中建立T1的登记项,值为6;读第五行, 变量T1被再 定值,修改其登记项内容及输出T1=7; 扫描第六行,T1的当前值为7: ret_reg=7; 最后一行无变量,不变.最后得 i=5;i=6;T1=6;T1=6;T1=7;ret_reg=7;ret; 2.第二遍扫描完成无用变量的删除: 清除符号表登记项,扫描代码,对作为源操作数出现的每个 变量,在表中建立相应的项. 显然扫描完后所有以目的操作数形式出现,且在表中无登 记项的变量都是无用的,相应的操作可删去.本例中,T1是无 用的,其相关操作均可删除,得: i=5;i=6;ret_reg=7;ret; 注意:由于i是用户定义的变量,无法断定其是否不再引用, 不能作为无用变量