（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