编译原理分知识点习题代码优化.docx
《编译原理分知识点习题代码优化.docx》由会员分享，可在线阅读，更多相关《编译原理分知识点习题代码优化.docx（27页珍藏版）》请在冰点文库上搜索。
编译原理分知识点习题代码优化
1．与机器有关的代码优化有那些种类，请分别举例说明。
解答：
与机器有关的优化有：
寄存器优化，多处理优化，特殊的指令优化，无用的指令消除等四类。
冗余指令删除
假设源程序指令序列
a:
=b+c;c:
=a-d;
编译程序为其生成的代码很可能是下列指令序列：
MOVb,R0
ADDc,R0
MOVR0,a
SUBd,R0
MOVR0,c
假如第四条指令没有标号，上述两个赋值语句在一个基本块内，则第四条指令是多余的，可删除。
特殊指令的使用
例如，如果目标机器指令系统包含增1指令INC，对于i:
=i+1的目标代码
MOVi,R0
ADD#1,R0
MOVR0,i
便可被代之以1条指令
Inci
说明：
优化的特点是每个改进可能会引发新的改进机会，为了得到最好的改进，一般可能需要对目标代码重复扫描进行优化。
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）
合并常量后的三元式序列为：
（1）（:
=,20，a）
（2）（:
=,600,b）
（3）（:
=,12000,c）
3、试写出算术表达式
a+b*c-（c*b+a-e）/（b*c+d）
优化后的四元式序列。
解答：
该表达式的四元式序列为：
（1）（*，b,c,T1）
（2）（+,a,T1,T2）
（3）（*,c,b,T3）
（4）（+,T3,a,T4）
（5）（-,T4,e,T5）
（6）（*,b,c,T6）
（7）（+,T6,d,T7）
（8）（/,T5,T7,T8）
（9）（-,T2,T8,T9）
可对该表达式进行删除公共子表达式的优化。
优化后的四元式序列为：
（1）（*，b,c,T1）
（2）（+,a,T1,T2）
（3）（-,T2,e,T5）
（4）（+,T1,d,T7）
（5）（/,T5,T7,T8）
（6）（-,T2,T8,T9）
4.设有算术表示式
（a*b+c）/（a*b-c）+（c*b+a-d）/（a*b+c）
试给出其优化后的三元式序列。
解答：
该算术表达式的三元序列为：
（1）（*,a,b）
（2）（+,
（1）,c）
（3）（*,a,b）
（4）（-,（3）,c）
（5）（/,
（2）,（4））
（6）（*,c,b）
（7）（+,（6）,a）
（8）（-,（7）,d）
（9）（*,a,b）
（10）（+,（9）,c）
（11）（/,（8）,（10））
（12）（+,（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
并就以下两种情况分别写出优化后的四元式序列：
（1）假设G、L、M在基本块后面要被引用;
（2）假设只有L在基本块后面要被引用。
解答:
一般应用DAG在一个基本块内可以进行三种优化:
合并常量、删除无用赋值以及多余运算。
对于基本块B1,其DAG如图7.1所示。
F,L,M*
E
*+
H*A,GD
*/
BC2
图7.1基本块B1的DAG图
优化后的四元式序列如下:
（1）若只有G、L、M在基本块后面要被引用
G:
=B*C或G:
=B*C
H:
=G*GS:
=G*G
L:
=H*GL:
=S*G
M:
=LM:
=L（S为临时变量）
（2）若只有L在基本块后面要被引用
G:
=B*C或S1:
=B*C
H:
=G*GS2:
=S1*S1
L:
=H*GL:
=S2*S1（S1、S2为临时变量）
对于基本块B2,其DAG如图7.2所示。
GL,M
*F,J+
+
D,HE,L
+*
BK
3AC15
图7.2基本块B2的DAG图
优化后的四元式序列如下:
（1）若只有G、L、M在基本块后面要被引用
D:
=A+C
E:
=A*C
F:
=D+E
G:
=3*F
L:
=F+15
M:
=L
（2）若只有L在基本块后面要被引用
D:
=A+C或S1:
=A+C
E:
=A*CS2:
=A*C
F:
=D+ES3:
=S1+S2
L:
=F+15L:
=S3+15
（S1、S2、S3为临时变量）
6.对于基本块P
S0:
=2
S1:
=3/S0
S2:
=T-C
S3:
=T+C
R:
=S0/S3
H:
=R
S4:
=3/S1
S5:
=T+C
S6:
=S4/S5
H:
=S6*S2
（1）试应用DAG进行优化。
（2）假定只有R、H在基本块出口是活跃的,试写出优化后的四元式序列。
（3）假定只有两个寄存器R0、R1试写出上述优化后的四元式序列的目标代码。
解答:
（1）构造DAG如图7.3所示。
H
R,,S6
S2
/-
S3,S5
+
S0,S4S1
21.5TC
图7.3基本块P的DAG图
优化后的四元式序列为:
S0:
=2
S4:
=2
S1:
=1.5
S2:
=T-C
S3:
=T+C
S5:
=S3
R:
=2/S3
S6:
=R
H:
=S6*S2
（2）若只有R、H在基本块出口是活跃的,优化后的四元式序列为:
S2:
=T-C
S3:
=T+C
R:
=2/S3
H:
=R*S2
（3）假定只有两个寄存器R0、R1,上述优化后的四元式序列的目标代码为:
LDR0T
SUBR0C
STR0S2
LDR0T
ADDR0C
LDR12
DIVR1R0
LDR0S2
MULR1R0
STR1H
7.设有入图7.4所示的程序流程图:
图7.4程序流图
（1）求出流图中各个结点n的必经结点集D（n）;
（2）求出该流图中的回边;
（3）求出该流图中的循环。
解答:
（1）在程序流图中,对任意的结点ni和nj,如果从流图的首结点出发,到达nj的任一通路都必须经过ni,则称ni是nj的必经结点,记为niDOMnj。
流图中结点n的所有必经结点称为结点n的必经结点集,记为D（n）。
流图中各结点n的必经结点集D（n）为:
D（B1）={B1}
D（B2）={B1,B2}
D（B3）={B1,B2,B3}
D（B4）={B1,B2,B3,B4}
D（B5）={B1,B2,B3,B5}
D（B6）={B1,B2,B3,B6}
D（B7）={B1,B2,B7}
D（B8）={B1,B2,B7,B8}
（2）流图的回边是指:
若a→b是流图中一条有向边,且有bDOMa,则称a→b是流图的一条回边。
题目所给流图中,有有向边B7→B2,又有D（B7）={B1,B2,B7},所以,B2DOMB7,
即B7→B2是流图的回边。
且无其他回边。
（3）该流图中的循环可利用回边求得。
如果以知有向边n→d是一回边,由它组成的循环就是由结点d、结点n以及有通路到达n而该通路不经过d的所有结点组成,且d是该循环的唯一入口结点。
题目所给出流图中,只有一条回边B7→B2,在该流图中,凡是不能经过结点B2有通路到达结点B7的结点,只有B3,B4,B5,B6,所以,由回边B7→B2组成的循环是{B2,B3,B4,B5,B6,B7}。
8.（中国科学院计算机所1997年）试画出如下中间代码序列的程序流图,并求出:
（1）各结点的必经结点集合D（n）;
（2）流图中的回边与循环。
J:
=0;
L1:
I:
=0;
ifI<8gotoL3;
L2:
A:
=B+C;
B:
=D*C;
L3:
ifB=0gotoL4;
WriteB;
gotoL5;
L4:
I:
=I+1;
ifI<8gotoL2;
L5:
J:
=J+1;
ifJ<=3gotoL1;
HALT
解答:
程序的流图入图7.5所示。
（1）各结点的必经结点集分别为:
D（n0）={n0}
D（n1）={n0,n1}
D（n2）={n0,n1,n2}
D（n3）={n0,n1,n3}
D（n4）={n0,n1,n3,n4}
D（n5）={n0,n1,n3,n5}
D（n6）={n0,n1,n3,n6}
D（n7）={n0,n1,n3,n6,n7}
n0
n1
n2
n3
n4
n5
n6
n7
图7.5程序流图
（2）流图中的回边有一条：
即n6n1
该回边表示的循环为：
（n1,n2,n3,n4,n5,n6）,入口为n1,出口为n6
9.（武汉大学1991年）试对下面的程序段进行尽可能的优化：
i：
=１
j：
=１０
read k
l：
x：
=k*i
y:
=j*i
z:
=x*y
writej
i:
=i+1
ifi<100gotol
halt
并指明你进行了何种优化，给出优化过程的简要说明及每种优化后的结果形式。
解答：
程序的流程图如下所示：
Ｂ1：
Ｂ2:
Ｂ3:
图7.6程序流图
由程序流图可知，｛Ｂ２｝为一个循环。
对于本题中的循环可进行以下优化：
· 削减强度
循环中有
x:
=x*i
y:
=y*i
j,k在循环中不改变值。
i每次增加１,x和y的赋值运算可进行强度削减，于是程序流图变为图7.7所示。
B1:
B2ˊ:
Ｂ２：
B3:
图7.7削减强度后的程序流图
· 删除归纳变量
由于i是循环中的基本归纳变量，x、y是与y同族的归纳变量，且有线性关系
x：
=k*iy：
=j*i
所以，i<100完全可用x<100*k或y<100*j代替。
于是，进一步优化为图7.8所示。
· 代码外提
将循环中不变运算
writej
tl:
=100*k
提到循环外的前置节点B21中，于是程序流图变为7.9所示的情形。
B1:
B¹2
B2:
B3:
图7.8归纳变量后的程序流图
B1:
B2¹:
B2:
B3:
图7.9代码外提后的程序流图
10.在循环优化中，为什么要代码外提？
试说明在哪些情况下代码可外提？
解答：
代码外提可以减少循环中的指令数目，从而节省目标代码运行的时间。
对于循环中L的每一个不变运算
s：
A：
=BopC或A：
=B
检查它是否满足以下两个条件：
（1）（a）s所在的节点是L的所有的出口节点的必经节点；
（b）Ａ在Ｌ中其他地方未再定值；
（c）Ｌ中所有Ａ的引用点只有s中Ａ的定植才能到达。
（2）Ａ离开Ｌ后不再是活跃的，并且条件（１）中的（a）和（b）成立，所谓Ａ离开Ｌ后不再是活跃的，是指Ａ在Ｌ的任何出口节点的后继节点（当然是指那些不属于Ｌ的后继）入口处不是活跃的。
符合上述（１）或（２）的不变运算s可以外提到Ｌ的前置节点中。
但是。
S的运算对象（Ｂ或Ｃ）是在Ｌ中定植的，那么只有当这些定植代码都已外提到前置节点中时。
才能把s也提到前置节点中。
11.以下循环是最内循环，是对其进行循环优化。
A:
=0
I:
=1
L1:
B:
=J+1
C:
=B+I
A:
=C+A
IFI=100GOTOL2
I:
=I+1
GOTOL1
L2:
解答：
程序的流程图如图所表示
有流程图可见，{B2,B3}是一个循环，该循环可进行以下有话：
代码外提
B2中的B:
=J+1是循环的不变运算，可提到循环外。
删除归纳变量
I是循环的基本归纳变量，C是与I同组的归纳变量，且二者有如下线性关系：
C:
:
=B+I于是I=100完全可用C=B+100代替。
相应的I:
=I+1可用C:
=C+1代替。
于是流程图变为图所表示
图7.10优化后的程序流图
14．设有循环语句
FORi:
=1TOnDO
BEGINa
a:
=u*v
b:
=m*m
c:
=c+b*b
END
试写出循环外提后的结果。
解答：
该语句的四元式为：
（1）（:
=，1,,i）
（2））（-,n,i,T0）
（3）（BMZ,T0,，（14））
（4）（*，u,v,T1）
（5）（:
=,T1，，a）
（6）（*，m,m,T2）
（7）（:
=,T2，，b）
（8）（*，b,b,T3）
（9）（+，c，T3，T4）
（10）（：
=，T4，，c）
（11）（+，1，i,T5）
（12）（:
=,T5,,i）
（13）（BR,,,
（2））
由于a:
=u*v；b:
=m*m是循环的不变运算，均可外提；且b:
=m*m；外提后，b*b也是循环的不变运算，也可外提。
优化后的四元式如下：
（1）（:
=，1,,i）
（2）（*，u,v,T1）
（3）（:
=,T1，，a）
（4）（*，m,m,T2）
（5）（:
=,T2，，b）
（6）（*，b,b,T3）
（7）（:
=，0，，c）
（8））（-,n,i,T0）
（9）（BMZ,T0,，（14））
（10）（+，c，T3，T4）
（11）（：
=，T4，，c）
（12）（+，1，i,T5）
（13）（:
=,T5,,i）
（14）（BR,,,（8））
（15）
（9）（+，c，T3，T4）
（10）（：
=，T4，，c）
（11）（+，1，i,T5）
（15）（:
=,T5,,i）
（16）（BR,,,
（2））
15.如何理解有的程序优化后质量反而下降？
解答：
进行了代码优化后生成的目标代码，对于极个别的源程序来说，可能质量可能非但没有改进，发而有所下降。
这是因为，源程序形形色色，内涵丰富，某种语言结构组合可能进行优化反而降低质量的反例。
这并不矛盾，只要对于大多数源程序有较明显的质量改进就可以认为所做的优化成功。
升级会员 