山东理工大学《编译原理》考试

(2)已开始而尚未执行完毕标号为11的语句时运行栈的内容是中间表0-15右侧表16-26的内容,右侧表20-22的内容是此时Display表的内容。

第十章 优化

1. 在循环中可采用 、 和删除归纳变量三种优化措施。

答:代码外提,强度削弱

2.根据优化所涉及的范围,可将优化可分为 , 和循环优化。 答:局部优化,全局优化

3.试对以下基本块构造其DAG图,分别利用DAG图对它们进行优化,并就以下两种情况分别写出优化后的四元式序列:

(1) 假设只有G,L,M在基本块后面还要被引用; (2) 假设只有L在基本块后面还要被引用。

B:=3 D:=A+C E:=A*C F:=D+E G:=B*F H:=A+C I:=A*C J:=H+I K:=B*5 L:=K+J M:=L

解答:

该基本块的DAG图:

n7 Gn9 L,M + *

n1 Bn6 F,J n8 K

3 + 15

n5 E,I n4 D,H

* +

n2 n3

A0 C0

(1) 假设只有G,L,M在基本块后面还要被引用,该基本块优化后的四元式序列为:

D := A + C E := A * C F := D + E G := 3 * F L := 15 + F M := L

(2) 假设只有L在基本块后面还要被引用,该基本块优化后的四元式序列为:

D := A + C E := A * C

11

F := D + E L := 15 + F

第十一章 目标代码生成

1.指令的执行代价定义为 + . 答:该指令访问内存的次数 1(取该指令访问内存的次数) 2. 设有基本块P T0 := 3 T1 := 8 / T0 T2 := S – C T3 := S + C R := T0 * T3 H := R

T4 := 10 / T1 T5 := S + C T6 := T4 * T5 H := T6 / T2

(1) 构造其DAG图,写出用DAG图优化后的三地址代码序列;

(2) 假定只有R,H在基本块出口是活跃的,试写出优化后的三地址代码序列;

(3)假定只有两个寄存器R0和R1,试写出在(2)中优化后代码序列的目标代码,同时列出代码生成过程中的寄存器描述RVALUE和地址描述AVALUE。 解答:

(1) 该基本块对应的DAG图:

n10 H / n7 Rn9 T6

* *

重建代码:T0:=3 T3:=S+C T4:=3.75

n6 T3,T5 n5 T2 + n1 T0 n2 T1 3

2.67

n3 S0

- n4 C0

n8 T4 3.75 T1:=2.67 T5:= T3 T6:=3.75 * T3

T2:=S-C R:=3*T3 H:= T6/T2

(2)假定只有R,H在基本口是活跃的,优化后的三地址代码序列:

T2:=S-C T3:=S+C R=3*T3 T6:=3.75 *T3 H:= T6/T2

三地址代码 目标代码 寄存器描述 地址描述

12

(3) 三地址代码 目标代码 寄存器描述 地址描述

T2:=S-C LD R0,S

SUB R0,C R0含T2 T2在R0

T3:=S+C LD R1,S R0含T2 T2在R0

ADD R1,C R1含T3 T3在R1 R:=3*T3 ST R0,T2 T2在内存 LD R0,#3 R1含T3 T3在R1 MUL R0,R1 R0含R R在R0 T6:=3.75 *T3 ST R0,R R在内存 LD R0,3.75 R1含T3 T3在R1 MUL R0,R1 R0含T6 T6在R0

H:= T6/T2 DIV R0,T2

ST R0,H R0含H H在R0和内存

13

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4