编译原理代码优化.ppt

第 8 章 代码优化 8.2.1 常见的局部优化方法 8.2.1 常见的局部优化方法(续1) 8.2.3 基于DAG的局部优化方法 8.2.3 基于DAG的局部优化方法 基于DAG的局部优化练习 对以下基本块 T1=2 T2=A-B T3=A+B T4=T2*T3 T5=3*T1 T6=A+B L=A-B T7=T6*L T8=T5*4 M=T8+T7 L=M (1) 构造优化的 DAG 图； (2) 假设只有 L 在基本块出口之后还被引用，请写出优化后的四元式序列。 基于DAG的局部优化练习答案 * * 优化处理是指产生更高效的目标代码所做的工作。 8.1 优化的分类 8.2 局部优化 8.2.1 常见的局部优化方法 8.2.2 基本块及其划分 8.2.3 基于DAG的局部优化方法 【内容提要】 目标代码所占空间和执行速度 8.1 优化的分类 (1) 与机器无关的优化(在源代码或中间代码级上进行)； 又分三种： ① 全局优化 — 针对整个源程序。 ② 局部优化 — 除全局优化外皆属此类。 ③ 循环优化 — 对循环语句实施的优化。 (2) 与机器有关的优化(目标代码级上的优化)： 包括：① 寄存器分配的优化； ② 消除无用代码。 ※ 根据代码优化是否涉及具体的计算机来划分： 1. 常值表达式节省(常数合并) 如：a=5+3;b=a+1; ……. 5+3,a+1 皆为常值表达式！ 则可优化为 a=8;b=9; 2. 公共子表达式节省(删除多余运算) 3. 删除无用赋值 如：a=b+c;x=d-e;y=b;a=e-h/5; 则 a=b+c 为无用赋值！ 则可优化为 x=d-e;y=b;a=e-h/5; a 未有应用！！ 若：a=5+3;…;a=x…; a=a+1; 注 则 a+1不是常值表达式！ 如：a=b*d+1;e=b*d-2; …… b*d是公共表达式! 则可优化为 t=b*d; a=t+1; e=t-2; 若：b=b*d+1; e=b*d-2; 则 b*d不是公共表达式！ 注 4. 不变表达式外提（循环优化之一） 即把循环不变运算，提到循环外。 5. 消减运算强度（循环优化之二） 即把强度大的运算换算成强度小的运算。 如：i=1; while(i100){x=(k+a)/i;…;i++;} 则可优化为 i=1;t=k+a; while (i100){x=t/i;…;i++;} 循环不变表达式 如：i=1; while ( i100 ){ t=4*i; b=a↑2;…; i++; } 则可优化为 i=1;t=0; while (i100){t=t+4; b=a*a;…;i++;} t,i 线性 关系 8.2.2 基本块及其划分 ※ 局部优化算法是以基本块为单位进行的，基本块也是目标代码生成的基本单位。 【定义】基本块是程序中一段顺序执行的语句序列，其中只有一个入口和一个出口。 1．确定基本块的入口语句，它们是： (1) 程序的第一个语句或转向语句转移到的语句； (2) 紧跟在转向语句后面的语句。 2．确定基本块的出口语句，它们是： (1) 下一个入口语句的前导语句； (2) 转向语句(包括转向语句本身)； (3) 停语句(包括停语句本身)； 基本块划分算法： 【例8.1】设有源程序片段如下，划分出基本块； ※以基本块为结点的程序流图，如下所示： 对应的四元式序列 x=1; a:r=x*5; if(x10){x=x+1;goto a;} r=0; (1) x =1 (4) r = t1 (5) t2=x10 (6) if(t2) _ (7) t3 = x+1 (8) x = t3 (9) gt a (10) ie _ (2) lb a (3) t1=x*5 (11) r = 0 x=1 (2)lb a (3)t1=x*5 (4)r=t1 (5)t2=x10 (6) if(t2)_ (7)t3=x+1 (8)x=t3 (9) gt a (11) r=0 (10) ie _ B1 B2 B3 B4 四个基本块 8.2.2 基本块及其划分(续1) ※ 基本块内四元式的局部优化过程示例 【例8.2】 设 有语句片断： B=5; A=2*3.14/(R+r); B=2*3.14/(R+r)*(R-r); A=2*3.14/(R+