编译原理（王晓斌）第十二章.ppt

程序设计语言与编译 第十二章代码优化和目标代码生成第十二章代码优化和目标代码生成 本章主要讨论以下两个问题： 1.如何对中间代码进行优化； 2.如何由优化后的中间代码生成有效和目标代码 ； 电子科技大学计算机科学与工程学院 程序设计语言与编译 一、优化的定义 第一节 局部优化 优化是一种等价的，有效的程序变换 等价不改变程序运行结果 有效时空效率要高 电子科技大学计算机科学与工程学院 程序设计语言与编译 二、不同阶段的优化 局部优化：在基本块内的优化 全局优化：超越基本块，在基本块之间的优化 1. 源程序阶段的优化：考虑DS和算法 2. 编译优化中间代码优化和目标代码优化 电子科技大学计算机科学与工程学院 中间代码优化局部优化和全局优化 程序设计语言与编译 三、划分基本块和构造程序流图 1. 划分基本块 基本块基本块是指程序中的一段语句（四元式）序列。 一个入口语句，即程序中该语句序列的第一个语句； 一个出口语句，即该语句序列的最后一个语句； （1）入口语句 紧跟在条件转向语句后的那个语句 程序的第一条语句 能由条件或无条件转向语句转移到的语句 (2)出口语句 转向语句 停止语句 电子科技大学计算机科学与工程学院 程序设计语言与编译 入口语句 入口语句 入口语句 入口语句 转向语句 停语句 (3)确定基本块 删除未被划入基本块的语句 电子科技大学计算机科学与工程学院 程序设计语言与编译 电子科技大学计算机科学与工程学院 (1)i:=m-1 (2)j:=n (3)t1:=4*n (4)v:=at1 (5)i:=i+1 (6)t2:=4*i (7)t3:=at2 (8)if t3v goto (9)goto (9) (13)if i=j goto (23)goto (23) (14)t6:=4*i (15)x:=at6 (16)t7:=4*i (17)t8:=4*j (18)t9:=at8 (19)at7:=t9 (20)t10:=4*j (21)at10:=x (22)goto (5)goto (5) (23)t11:=4*i (24)x:=at11 (25)t12:=4*i (26)t13:=4*n (27)t14:=at13 (28)at12:=t14 (29)t15:=4*n (30)at15:=x B1 B2 B3 B4 B5 B6 例 程序设计语言与编译 2.构造流图 G = ( N , E , n0 ） (1)基本块集即为结点集N; (2)含程序第一个语句的基本块为首结点n0; (3)设Bi,Bj N，若满足下列条件之一，则Bi Bj Bj 紧跟在Bi 之后，且Bi 的出口语句 不是无条件转向或停止语句 Bi 的出口语句为转向语句，其转向 点恰为Bj 的入口语 电子科技大学计算机科学与工程学院 程序设计语言与编译 电子科技大学计算机科学与工程学院 (1)i:=m-1 (2)j:=n (3)t1:=4*n (4)v:=at1 (5)i:=i+1 (6)t2:=4*i (7)t3:=at2 (8)if t3v goto (9)goto (9) (13)if i=j goto (23)goto (23) (14)t6:=4*i (15)x:=at6 (16)t7:=4*i (17)t8:=4*j (18)t9:=at8 (19)at7:=t9 (20)t10:=4*j (21)at10:=x (22)goto (5)goto (5) (23)t11:=4*i (24)x:=at11 (25)t12:=4*i (26)t13:=4*n (27)t14:=at13 (28)at12:=t14 (29)t15:=4*n (30)at15:=x B B1 1 B B2 2 B B3 3 B B4 4 B B5 5 B B6 6 程序设计语言与编译 四、基本块内的优化 对于A:= OP B 或 A:=B OP C这样的语句，若B及C为常数 ，则编译时可以把它们计算出来，把值存放在临时单元中 ，相应的语句变成A:=T; 1. 合并已知量 2. 删除公共子表达式 也叫删除多余运算；例如两条赋值语句 A:=B+C*D U:=V-C*D 中有两次C*D运算。 只计算一次，将值存在临时单元中T 第二个语句改为：U:=V-T 电子科技大学计算机科学与工程学院 程序设计语言与编译 4. 删除死代码 例如四元式序列 (p) A:=B+D (q) A:=M+N 中没有对A的引用，则第一个赋值无用，可删除。 3. 删除无用赋值 iF语句条件为定值 电子科技大学计算机科学与工程学院 程序设计语言与编译 F:=1F:=1I:=H*G C:=F F+EJ:=D/4D/4 D:=F+3 D:=F+3 K:=J+CJ+C B:=A*AL:=H G:=B-D DL:=I-J J H:=E 合并已知量 F:=1I:=H*G C:=1+EJ:=1 D:=4K:=2+E B:=A*AL:=HL:=H G:=B-4L:=I-1 H:=E 删除公共子表达式；I:=E*G 删除无用赋值； 假定F,C,D和J在基本块外不再引用，可得结果： B:=A*A G:=B-4 K:=2+E I:=E*G L:=I-1 电子科技大学计算机科学与工程学院 例1 程序设计语言与编译 (14)t6:=4*i (15)x:=at6 (16)t7:=4*i (17)t8:=4*j (18)t9:=at8 (19)at7:=t9 (20)t10:=4*j (21)at10:=x (22)goto (5) (14)t6:=4*i (15)x:=at6 (17)t8:=4*j (18)t9:=at8 (19)at6:=t9 (21)at8:=x (22)goto (5) 优化后 例2 电子科技大学计算机科学与工程学院 删除公共子表达式 程序设计语言与编译 第二节 全局优化 一、循环的定义 全局优化有很多种，本节只讨论循环优化； 如何找出程序中的所有循环？ 循环优化有哪些？ 循环是程序流图中有唯一入口结点的强连通子图 入口结点入口结点:子图中满足下列条件的结点n: 或者n是流图的首结点, 或者在子图外有一结点m, 它有一有向边mn引向结点n; 强连通子图强连通子图:任意两个结点可互相连联通 电子科技大学计算机科学与工程学院 程序设计语言与编译 1 2 3 4 5 6 78 9 10 5,6,7,8,9 例: 电子科技大学计算机科学与工程学院 是循环 , 4， 不是循环 不是循环 程序设计语言与编译 二、循环的的查找 1. 必经节点 从流图的首结点出发到达结点n的任一通路都必须 经过的结点d, 称d为n的必经结点，记为d DOM n 流图的首结点是流图中任一结点的必经结点 即n0 DOM n 每个结点是它本身的必经结点，即n DOM n 必经结点集必经结点集：流图中结点n的所有必经结点的集 合，称为n的必经结点集，记为D(n) 电子科技大学计算机科学与工程学院 程序设计语言与编译 1 2 3 4 5 6 78 9 10 D(1)=1 D(2)=1,2 D(3)=1,2,3 D(4)=1,2,4 D(5)=1,2,4,5 D(6)=1,2,4,5,6 D(7)=1,2,4,5,6,7 D(8)=1,2,4,5,6,8 D(9)=1,2,4,5,6,9 D(10)=1,2,4,10 电子科技大学计算机科学与工程学院 程序设计语言与编译 必经结点具有如下性质必经结点具有如下性质： 自反性自反性：即对任意结点n，有n DOM n 传递性传递性：若n1 DOM n2, n2 DOM n3，则n1 DOM n3 反对称性反对称性：若n1 DOM n2, n2 DOM n1，则n1=n2 电子科技大学计算机科学与工程学院 程序设计语言与编译 1 2 3 4 5 6 78 9 10 2. 回边 流图G=(N，E，n0)中的有 向边nd，如果d是n的必 经结点, 即dD(n),则称 nd为流图的一条回边。 54, 95, 102 电子科技大学计算机科学与工程学院 程序设计语言与编译 电子科技大学计算机科学与工程学院 若nd是流图G=(N,E,0)的一条回边，M是流图中有通路到 达n而该通路不经过d的结点集,则集合 LOOP=n,dM 组成了G的一个子图, 称为由回边nd组成的循环循环。 该流图有三条回边： 1. 1. 回边回边5 54 4构成循环 5,4,6,7,8,9 2. 2. 回边回边9 95 5构成循环 9,5,6,7,8 3. 3. 回边回边10102 2构成循环 10,2,3,4,5,6,7,8,9 3.由回边构成的循环 1 2 4 3 5 6 9 10 78 1 2 4 3 5 6 9 10 78 1 2 4 3 5 6 9 10 78 1 2 4 3 5 6 9 10 78 程序设计语言与编译 二、循环优化 1.代码外提 2.强度削弱 基本归纳变量，i有唯一定值，i := i c 同族归纳变量，j := c1 i c2 变成j := j c1 c , 但j必须在循 环外赋初值 j : c1 * i c2 电子科技大学计算机科学与工程学院 程序设计语言与编译 3.删除归纳变量 即改用同族归纳变量作为判断条件 例如将 i 10 改为 t3 100 + t1 因原来t3 := 10 * i + t1 ， 而100 t1 即 10 * 10 + t1 电子科技大学计算机科学与工程学院 程序设计语言与编译 电子科技大学计算机科学与工程学院 (1)i:=1 (2)if i10 goto (16) (3)t1:=2*j (4)t2:=10*i (5)t3:=t2+t1 (6)t4:=a0-11 (7)t5:=2*j (8)t6:=10*i (9)t7:=t6+t5 (10)t8:=a0-11 (11)t9:=t8t7 (12)t10:=t9+1 (13)t4t3:=t10 (14)i:=i+1 (15)goto (2) (16) . B B1 1 B B2 2 B B3 3 B B4 4 例 (1)i:=1 (4)t2:=10*i (5)t3:=t2+t1 (8)t6:=10*i (9)t7:=t6+t5 (11)t9:=t8t7 (12)t10:=t9+1 (13)t4t3:=t10 (14)i:=i+1 (15)goto (2) (16) . (2)if i10 goto (16) (3)t1:=2*j (6)t4:=a0-11 (7)t5:=2*j (10)t8:=a0-11 B B1 1 B B2 2 B B3 3 B B4 4 BB 2 2 代码外提后的流图代码外提后的流图 程序设计语言与编译 电子科技大学计算机科学与工程学院 (1)i:=1 (11)t9:=t8t7 (12)t10:=t9+1 (13)t4t3:=t10 (14)i:=i+1 (4)t2:=t2+10 (8)t6:=t6+10 (5)t3:=t3+10 (9)t7:=t7+10 (15)goto (2) (16) . (2)if i10 goto (16) (3)t1:=2*j (6)t4:=a0-11 (7)t5:=2*j (10)t8:=a0-11 (4)t2:=10*i (8)t6:=10*i (5)t3:=t2+t1 (9)t7:=t6+t5 B B1 1 B B2 2 B B3 3 B B4 4 BB 2 2 强度削弱后的流图强度削弱后的流图 (1)i:=1 (11)t9:=t8t7 (12)t10:=t9+1 (13)t4t3:=t10 (4)t2:=t2+10 (8)t6:=t6+10 (5)t3:=t3+10 (9)t7:=t7+10 (15)goto (2) (16) . (2)if t3s goto (16) (3)t1:=2*j (6)t4:=a0-11 (7)t5:=2*j (10)t8:=a0-11 (4)t2:=10*i (8)t6:=10*i (5)t3:=t2+t1 (9)t7:=t6+t5 (2)s:=100+t1 B B1 1 B B2 2 B B3 3 B B4 4 BB 2 2 删除归纳变量后的流图删除归纳变量后的流图 2106优化后 06413优化前 变址加加法数乘法数语句数B 3 3 B B3 3 优化前后的比较优化前后的比较 程序设计语言与编译 另例： (1)PROD := 0 (2)I := 1 (3)T1 := 4 * I (4)T2 := a0 4 (5)T3 := T2T1 (6)T4 := 4 * I (7)T5 := b0 4 (8)T6 := T5T4 (9)T7 := T3 * T6 (10)PROD := PROD + T7 (11)I := I + 1 (12)if I 20 goto (3) 电子科技大学计算机科学与工程学院 删除多余运算，代码外提 程序设计语言与编译 删除多余运算，代码外提 (1)PROD := 0 (2)I := 1 (4)T2 := a0 4 (7)T5 := b0 4 (3)T1 := 4 * I (5)T3 := T2T1 (6)T4 := T1 (8)T6 := T5T4 (9)T7 := T3 * T6 (10) PROD := PROD + T7 (11) I := I +1 (12)if I20 goto (3) 电子科技大学计算机科学与工程学院 强度削弱 程序设计语言与编译 强度削弱 (1)PROD := 0 (2)I := 1 (4)T2 := a0 4 (7) T5 := b0 4 (3) T1 := 4 * I (5)T3 := T2T1 (6)T4 := T1 (8) T6 := T5T4 (9) T7 := T3 * T6 (10) PROD := PROD + T7 (11) I := I +1 (3)T1 := T1 + 4 (12) if I 20 goto (5) 电子科技大学计算机科学与工程学院 程序设计语言与编译 强度削弱 (1) PROD := 0 (2) I := 1 (4) T2 := a0 4 (7) T5 := b0 4 (3) T1 := 4 * I (5) T3 := T2T1 (8) T6 := T5T1 (9) T7 := T3 * T6 (10) PROD := PROD + T7 (11) I := I +1 (3)T1 := T1 + 4 (12) if I 20 goto (5) 电子科技大学计算机科学与工程学院 变换循环控制条件 程序设计语言与编译 变换循环控制条件 (1)PROD := 0 (2)I := 1 (4)T2 := a0 4 (7) T5 := b0 4 (3) T1 := 4 * I (5)T3 := T2T1 (8) T6 := T5T1 (9) T7 := T3 * T6 (10) PROD := PROD + T7 (11) I := I +1 (3)T1 := T1 + 4 (12) if T1 80 goto (5) 电子科技大学计算机科学与工程学院 合并已知量 程序设计语言与编译 (1)PROD := 0 (2)I := 1 (4)T2 := a0 4 (7) T5 := b0 4 (3) T1 := 4 (5)T3 := T2T1 (8) T6 := T5T1 (9) T7 := T3 * T6 (10) PROD := PROD + T7 (3)T1 := T1 + 4 (12) if T1 80 goto (5) 电子科技大学计算机科学与工程学院 程序设计语言与编译 1. 代码生成的任务 将中间代码翻译成等价有效的目标代码 2. 代码生成器的输入 中间代码，符号表 3. 代码生成器的输出 目标代码 绝对机器代码 可重定位代码 汇编码 第三节 目标代码生成 电子科技大学计算机科学与工程学院 程序设计语言与编译 op 源，目的 其中op是操作码；源和目的是两个操作对象， 可以是内存地址、寄存器或常数 （1）直接地址型 op Ri , M (Ri) op (M) = Ri （2）寄存器型 op Ri, Rj (Ri) op (Rj) = Ri 4.抽象机的指令形式 电子科技大学计算机科学与工程学院 程序设计语言与编译 （3）变址型 op Ri , C(Rj) (Ri) op (Rj) + C) = Ri （4）间接型 op Ri , *Rj (Ri) op (Rj) = Ri op Ri , *M (Ri) op (M) = Ri op Ri , *C(Rj) (Ri) op (Rj) + C) = Ri 电子科技大学计算机科学与工程学院 程序设计语言与编译 （5）其它几种常用指令 MOV Ri , M (Ri) = M MOV M , Ri (M) = Ri J x goto x 电子科技大学计算机科学与工程学院 程序设计语言与编译 5.简单的代码生成方法 （1) p: x:= y op z 的翻译 MOV y , Ri op Ri , z 电子科技大学计算机科学与工程学院 结果（x 的值）在寄存器Ri中 程序设计语言与编译 (2)为 结果（x） 分配寄存器的方法 1.y 本身占有寄存器Ri，且y在p点后不再被引用 2.有空余的可用寄存器Ri 3.寄存器均被占用：保存副本，选择一个 最好选择占用Ri的变量在主存中已有副本的 或者在p点后该变量不再被引用的 或者在离p点最远处才被引用的 电子科技大学计算机科学与工程学院 程序设计语言与编译 例:基本块中有如下指令： t:=a-b u:=a+c v:=a-t w:=v+u MOV a , R0 SUB R0, b (t占用R0) MOV a , R1 ADD R1, c (u占用R1) MOV R1, u (释放R1) MOV a , R1 SUB R1 , R0 (v占用R1） MOV R1, v (释放R1) ADD R1, u (w占用R1) 假设可以两个寄存器 电子科技大学计算机科学与工程学院 程序设计语言与编译 6.循环中的寄存器的分配 (1)指令的执行代价 该指令访问主存的次数 寄存器型 op Ri，Rj 执行代价为1 直接地址型 op Ri，M 执行代价为2 变址型 op Ri，C(Rj) 执行代价为2 间址型 op Ri, *Rj 执行代价为2 op Ri, *M 执行代价为3 op Ri, *C(Rj) 执行代价为3 电子科技大学计算机科学与工程学院 程序设计语言与编译 BL （2）固定分配寄存器节省的代价计算 I.设USE ( x , B ) 为x在B 中被定值前的引用次数， 则循环L执行一次，可省的执行代价为 USE(x, B) II.对基本块中定值基本块后的活跃变量x，省去指令 MOV Ri , Mx, 可省执行代价 (2*LIVE(x,B) BL 省的执行代价 BL USE(x, B) +(2*LIVE(x,B) BL 电子科技大学计算机科学与工程学院 程序设计语言与编译 a:=b+c d:=d-b e:=a+f f:=a-db:=d+f e:=a-c b:=d+c acdef cdef bcdef bcdef B1 B2 B3 B4 电子科技大学计算机科学与工程学院 程序设计语言与编译 B1 B2 B3 B4 a bcd e f 1 1 22 2 2 1 1 1 1 1 1 1 22 2 1 2 1 46 3644 若有三个可固定分配的寄存器, 则 b、d可固定分配寄存器， 另一个分配给a、e、f中的一个 电子科技大学计算机科学与工程学院 程序设计语言与编译 电子科技大学计算机科学与工程学院 作业作业 12.1，12.5，12.6，12.7, 12.8 程序设计语言与编译 电子科技大学计算机科学与工程学院 内容回顾 1.局部优化 2.全局优化 基本块的划分 出口语句 入口语句 入口语句 入口语句 循环优化循环的定义 程序流图G = ( N , E , n0 ） 循环的查找 必经节点 回边 合并已知量 公共子表达式 无用赋值 死代码 必经节点集 回边循环 程序设计语言与编译 第五节第五节 参数传递参数传递 先看例子: procedure swap (a , b : integer); var temp : integer; begin temp := a; a := b; b := temp end; call swap(x, y); . 形式参数 实在参数 程序设计语言与编译 1. 程序单元间通信方式有非局部环境和参数传递 2. 参数，形参，实参 3. 参数传递的三种类型： 数据参数传递 过程参数传递 类型参数传递 几点说明