《川师编译原理课件11.ppt》由会员分享,可在线阅读,更多相关《川师编译原理课件11.ppt(43页珍藏版)》请在三一文库上搜索。
1、第十一 章 代码优化 教学目的教学目的:让学生了解几种常见的代让学生了解几种常见的代 码优化技术,掌握局部优化、循环优码优化技术,掌握局部优化、循环优 化、数据流分析方法。化、数据流分析方法。 教学重点教学重点:代码优化技术、基本块的代码优化技术、基本块的 DAGDAG及应用。及应用。 课时分配课时分配:4 4学时。学时。 教学过程教学过程: *1 11.1 优化技术简介 一、代码优化分类 编译前端 中间代码优化 目标代码 中间代码 目标代码优化 Date2 大学:莫礼平 1、按阶段分类 中间代码优化、目标代码优化。 2、按程序范围分类 局部(基本块)优化、循环优化、全 局优化。 二、代码优化
2、原则 等价原则、高效原则。 Date3 大学:莫礼平 三、代码优化技术三、代码优化技术 例:有如下例:有如下源程序段,求其四元式形式源程序段,求其四元式形式 的中间代码,并优化之的中间代码,并优化之( (设设A A为实型为实型 数组数组 ,每个元素占四个字节,每个元素占四个字节) ) 。 P P:=0=0; for i:=1 to 20 do for i:=1 to 20 do P:=P+Ai*Bi; P:=P+Ai*Bi; Date4 大学:莫礼平 1、数组的存储空间 n设数组中每个元素占t个存储空间,则 A1 A2 A3 A4 . 数组首地址Addr(A) Ai的地址为: Addr(A)+
3、(i-1)*t =Addr(A) -t +i*t 令为T=Addr(A) -t , 则Ai的地址为:T+i*t Date5 大学:莫礼平 (1)P:=0 (2)i:=1 (3)T1:=4*i (4)T2:=addr(A)-4 (5)T3:=T2T1 (=) (6)T4:=4*i (7)T5:=addr(B)-4 (8)T6:=T5T4 (9)T7:=T3*T6 (10)P:=P+T7 (11)i:=i+1 (12)IF iy( 如取x=20,y=15)时,j值应为1。 Date36 大学:莫礼平 i:=1 B1 if xy then goto B3 i=2; x:=x+1 B2 B3 y:=y
4、-1;if y=20 then goto B5 B4 j:=iB5 Date37 大学:莫礼平 2、代码外提规则 将循环不变运算s: A:=B op C 外提时,必须 满足下列条件(a)(b)之一: (a): 1) S所在的结点是L的所有出口点的必经点 ; 2) A在L中其它地方未定值; 3) L中所有A的引用点,只有s中A的定值才 能到达。 (b) : A在离开L之后不再是活跃(即不再被引用)的 。 Date38 大学:莫礼平 3、强度削弱和删除归纳变量 1)强度削弱 指将程序中执行时间较长的运算替换为执 行时间较短的运算。如将乘方换乘法,乘法换 加法等; 2)删除归纳变量 如果循环中有I:
5、=I+C;J=C1*I+C2,则对于 基本归纳变量I 的线性增长关系(C为循环不变 量)可转换成为与I同族的归纳变量J的线性增 长关系,从而可删除I的递归定值四元式。 3)删除归纳变量在强度削弱之后进行。 Date39 大学:莫礼平 11.4 数据流的分析与全局优化 一、基本概念 1、到达-定值: 定值点d到达p是指流图中从d有一条路 径到达p且该通路上没有A 的其它定值。 2、引用-定值链(u-d)链: 到达u的所有A的定值点的全体。 3、定值-引用链(d-u)链: d能到达的所有引用点的全体。 Date40 大学:莫礼平 二、到达-定值方程 1、方程: outs=(ins-kills)ge
6、ns inB:到达基本块入口前的变量定值点; killB:在基本块中被“注销”的定值点 ; genB:在B中定值并到达B出口之后的所 有定值点集。 2、例子: Date41 大学:莫礼平 d1: i=2; d2: j:=i+1 d3: i:=1 d4: j:=j+1 d5: j:=j-4 d6: a:=i; d7: b:=j B1 B2 B3 B4 B5 genB 位向量 killB 位向量 B1 d1,d2 1100000 d3,d4, d5 0011100 B2d30010000d11000000 B3d40001000 d2d5 0100100 B4d50000100 d2,d4 010
7、1000 B5 0000000 0000000 Date42 大学:莫礼平 n求ud链的迭代过程(in初值为,out初值为gen ) 一二三四 inoutinoutinoutinout B1(2 ) 0010 000 1100 000 0110 000 1100 000 0111 100 1100 000 0111 100 1100 000 B2(1, 5) 1100 000 0110 000 1111 100 0111 100 1111 100 0111 100 1111 100 0111 100 B3(2 ) 0110 000 0011 000 0111 100 0011 000 0111 100 0111 100 0111 100 0010 100 B4(3 ) 0011 000 0010 100 0011 000 0010 100 0011 000 0010 100 0011 000 0010 100 B5(3, 4) 0011 100 0011 100 0011 100 0011 100 0011 100 0011 100 0011 100 0011 100 Date43 大学:莫礼平
链接地址:https://www.31doc.com/p-2241903.html