1. 试把以下程序划分为基本块并作出其程序流图。

      read C

      A:=0

      B:=1

L1:  A:=A+B

      if B≥C goto L2

      B:=B+1

      goto L1

L2:  write A

      halt

解题思路：要画出程序的控制流程图,先得将程序划分成基本块的形式。基本块的划分分为3个步骤: 第1步：满足下列3个条件中任一个的语句可充当入口。

1)程序的第一个语句。

2)能由条件转移语句或无条件转移语句转移到的语句。

3)紧跟在条件转移语句后面的语句。 第2步：根据第1步求出的每一入口语句,构造其所属的基本块。 1)由该人口语句到另一入口语句(不包括该入口语句)之间组成的语句序列,或

2)由该入口语句到-转移语句(包括该转移语句)之间组成的语句序列,或

3)由该入口语句到一停语句(包括该停语句)之间组成的语句序列。

第3步：凡未被纳入某一基本块中的语句,都是程序中控制流程无法到达的语句,从而也是不会被执行的语句,可把它们从程序中删除。解答

根据第1个步骤,程序中的入口有程序的第1个语句(read(C)),转移语句能转移到的有2个语句(其语句标号分别为L1、L2),以及条件语句(标号为L1)之后的语句(B:=B+1)。总共找出4个入口。因此,程序至少可分为4个基本块。 根据第2个步骤有:由第1个入口(程序的第1个语句)到下一入口语句(标号为L1的转移语句,不包括该入口语句)之间组成的语句序列为第1个基本块;第2入口语句到if B≥C goto L2为第二个基本块;第3个入口到一转移语句(goto L1,包括该转移语句)之间组成的语句序列为第3个基本块;第4个入口到停语句(包括该转移语句)为第4个基本块。

第2步做完后,程序中不存在控制流程无法到达的语句,因此不需要进行语句的删除操作。基本块划分好之后,可根据基本块间执行的可能顺序构造出基本块间的有向边,从而得到程序的流图。 因此，程序共分为4个基本块(B1到B4),以及相应的程序流图如图所示(一个方框代表一个基本块)。

2. 试把以下程序划分为基本块并作出其程序流图。

      read A, B

      F:=1

      C:=A*A

      D:=B*B

      if C100 goto L2

      halt

L2:  F:=F-1

      goto L1

答：

根据第1个步骤,程序中的入口有程序的第1个语句(read(A,B)),转移语句能转移到的有2个语句(其语句标号分别为L1、L2),以及2个条件语句(if C100 goto L2）之后的语句（halt）。总共找出5个入口。因此,程序至少可分为5个基本块。 根据第2个步骤有:由第1个入口(程序的第1个语句)到下一入口语句(第二个基本块,不包括该入口语句)之间组成的语句序列为第1个基本块;第2入口语句E:=A*A到halt为第2个基本块;第3个入口到一转移语句(if E>100 goto L2,包括该转移语句)之间组成的语句序列为第3个基本块;if E>100 goto L2之后的halt为第4个基本块。L2到转移语句(goto L1)为第5个基本块。

第2步做完后,程序中不存在控制流程无法到达的语句,因此不需要进行语句的删除操作。基本块划分好之后,可根据基本块间执行的可能顺序构造出基本块间的有向边,从而得到程序的流图。

该程序可划分为5个基本块:B1、B2、B3、B4和B5。

其程序流图如下图所示。

3. 试对以下基本块B1和B2：

B1: A:=B*C                B2:  B:=3

      D:=B/C                        D:=A+C

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

      F:=2*E                        G:=B*F

      G:=B*C                       H:=A+C

      H:=G*G                      I:=A*C

      F:=H*G                       J:=H+I

      L:=F                           K:=B*5

      M:=L                           L:=K+J

                                         M:=L

分别应用DAG对它们进行优化，并就以下两种情况分别写出优化后的四元式序列：

（1）假设只有G、L、M在基本块后面还要被引用；

（2）假设只有L在基本块后面还要被引用。

【解答】(1）基本块B1的DAG构造。

 根据构造基本块的DAG的算法，处理每一个四元式后构造出的DAG如图中各子图所示（其步骤从略）。图(a),(b)，…，(i）分别对应于四元式①，②，…，⑨。

现在写出基本块B1优化后的四元式序列。 若只有G，L，M在基本块B1后仍要引用,则优化后的四元式序列为

G:=B*C

H=G*G

L:=H*G

M:=L

或者

若只有L在基本块后面还要被引用，则优化后的四元式序列为

G:=B*C

H=G*G

L:=G*H

或者

S1 :=B*C

S2 :=S1*S1

L:=S2*S1 (S1、S2为临时变量)

(2)B2的DAG构造过程

处理每一个四元式后构造出的DAG如图中各子图所示（步骤从略）。图(a),(b) , …,(k)分别对应于四元式①，②,…，

若只有G、L、M在基本块后还要被引用，在优化后的四元式序列为:

现在写出基本块B优化后的四元式序列。

L，M，G在B2后仍要被引用，则优化后的四元式序列为：

D:=A+C

E:=A*C

F:=D+E

G:=3*F

L:=F+15

M:=L

若只有L在基本块后还要被引用，则优化后的四元式序列为:

D:=A+C

E:=A*C

F:=D +E

L:= 15 + F

或者

S1:=A+C

S2:=A*C

S3:=S1+S2

L:= 15+S3 (s1、s2、S3为临时变量)

4. 对以下四元式程序，对其中循环进行循环优化。

      I: =1

      read J, K

L:   A:=K*I

      B:=J*I

      C:=A*B

      write  C

      I:=I+1

      if   I