编译原理分知识点习题代码优化.doc
文本预览下载声明
1.与机器有关的代码优化有那些种类,请分别举例说明。
解答:与机器有关的优化有:寄存器优化,多处理优化,特殊的指令优化,无用的指令消除等四类。
冗余指令删除
假设源程序指令序列
a:=b+c; c:=a-d;
编译程序为其生成的代码很可能是下列指令序列:
MOV b, R0
ADD c, R0
MOV R0,a
SUB d, R0
MOV R0,c
假如第四条指令没有标号,上述两个赋值语句在一个基本块内,则第四条指令是多余的,可删除。
特殊指令的使用
例如,如果目标机器指令系统包含增1指令INC,对于i:=i+1的目标代码
MOV i, R0
ADD #1, R0
MOV R0, i
便可被代之以1条指令
Inc i
说明:优化的特点是每个改进可能会引发新的改进机会,为了得到最好的改进,一般可能需要对目标代码重复扫描进行优化。
2.设有语句序列
a:=20
b:=a*(a+10);
c:=a*b;
试写出合并常量后的三元式序列。
解答:该语句序列对应的三元式序列为:
(1) (:=, 20,a)
(2) (+, a, 10)
(3) (*, a, (2) )
(4) (:=, a, b)
(5) (* a, b)
(6) (:=, (5), c)
合并常量后的三元式序列为:
(:=, 20,a)
(:=, 600, b)
(:=, 12000, c)
3、试写出算术表达式
a+b*c-(c*b+a-e)/(b*c+d)
优化后的四元式序列。
解答:该表达式的四元式序列为:
(*,b,c,T1)
(+,a,T1,T2)
(*,c,b,T3)
(+,T3,a,T4)
(-,T4,e,T5)
(*,b,c,T6)
(+,T6,d,T7)
(/,T5,T7,T8)
(-,T2,T8,T9)
可对该表达式进行删除公共子表达式的优化。优化后的四元式序列为:
(*,b,c,T1)
(+,a,T1,T2)
(-,T2,e,T5)
(+,T1,d,T7)
(/,T5,T7,T8)
(-,T2,T8,T9)
4.设有算术表示式
(a*b+c)/(a*b-c)+(c*b+a-d)/(a*b+c)
试给出其优化后的三元式序列。
解答:该算术表达式的三元序列为:
(*,a,b)
(+,(1),c)
(*,a,b)
(-,(3),c)
(/,(2),(4))
(*,c,b)
(+,(6),a)
(-,(7),d)
(*,a,b)
(+,(9),c)
(/,(8),(10))
(+,(5),(11))
可对其进行删除公共子表达式的优化。优化后的三元式列为:
(1)(*,a,b)
(2) (+,(1),c)
(3) (-,(1),c)
(4) (/,(2),(3))
(5) (*, c, b)
(6) (+,(5),a)
(7) (-,(6),d)
(8) (/,(7),(2))
(9) (+,(4),(8))
5.试对以下基本块B1和B2应用DAG进行优化
B1: A:=B*C
D:=B/C
E:=A+D
F:=E*2
G:=B*C
H:=G*G
F:=H*G
L:=F
M:=L
B2: 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
并就以下两种情况分别写出优化后的四元式序列:
假设G、L、M在基本块后面要被引用;
假设只有L在基本块后面要被引用。
解答:一般应用DAG在一个基本块内可以进行三种优化:合并常量、删除无用赋值以及多余运算。
对于基本块B1,其DAG如图7.1所示。
F , L , M *
E
* +
H * A , G D
* /
B
显示全部