Copyright © 2006 Gradiance Corporation.

 

 

     

Intermediate-Code Generation --- Control Flow

 

 

 

questions on translation of loops and branches; backpatching.

 

1.  

A certain boolean expression B has the form:

B1 && (B2 || B3) && !(B4 || B5)

Here, B1 through B5 can be complex boolean expressions themselves. If we translate this source code into intermediate code, the sequence of 3-address statements will have the form:

i1: Code(B1)
i2: Code(B2)
i3: Code(B3)
i4: Code(B4)
i5: Code(B5)

Here, i1,...,i5 are statement labels, and Code(...) represents the sequence of three-address statements that comes from the corresponding source construct. For example, Code(B1) represents the statements that are generated to evaluate subexpression B1, and i1 is the label of the first of these statements.

When we implement this translation using backpatching, we maintain, for each subexpression Bi, two lists of places in the code for Bi, which we denote by Bi.true and Bi.false. The places on list Bi.true are those places where we eventually put the label of the statement to which control must flow whenever Bi is true. Bi.false similarly lists the places where we put the label that control flows to when Bi is found to be false.

Assume that the expression B is translated to intermediate code in the normal left-to-right manner, and that the "lazy" interpretation of expression evaluation is used (do not evaluate a subexpression if expressions to its left have already determined the truth or falsehood of B). As we process expression B, some of these lists can be backpatched --- that is, they are replaced by one of the labels i1,...,i5. Other lists become part of the list B.true or B.false, that are places that will eventually be backpatched when it is determined where control must flow when B as a whole is found to be true, or false, respectively. For each of the lists Bi.true and Bi.false, decide whether it belongs on list B.true, on list B.false, or is backpatched to one of the labels i1,...,i5. Then, identify the true statement from the list below.

 

 

 

 a) 

B3.false is backpatched to i2

 

 b) 

B5.false becomes part of B.false

 

 c) 

B3.true is backpatched to i4

 

 d) 

B4.false becomes part of B.true

 

 

 

 

 

2.  

This question concerns the processing of the boolean expression below, using backpatching. Assume that the expression is translated to intermediate code in the normal left-to-right manner, and that the "lazy" interpretation of expression evaluation is used (do not evaluate a subexpression if expressions to its left have already determined its truth or falsehood). 

 
-------------B6--------------
          ---------B5--------
           --------B4--------
--B1--      --B2--    --B3--
a == b && !(c == d || e == f)
 

The elementary boolean conditions are represented by B1, B2, and B3. Subexpression B4 is the OR of B2 and B3; B5 is the negation of B4, and B6 is the entire expression. When we implement this translation using backpatching, we maintain, for each boolean expression B, two lists of places in the code for B, which we denote by B.true and B.false. The places on list B.true are those places where we eventually put the label of the statement to which control must flow whenever B is true; B.false similarly lists the places where we put the label that control flows to when B is found to be false.

There are rules for how the lists for B4, B5, and B6 are derived from the the lists for their subexpressions. You should look up or derive these rules, and write each of them down. Then, identify the correct rule from the list below.

 

 

 

 a) 

B6.true = B1.true [union] B5.true

 

 b) 

B6.false = B1.false [union] B5.false

 

 c) 

B5.false = B4.false

 

 d) 

B6.false = B1.false

 

 

 

 

 

3.  

Consider the following sketch of C code, where Ei represents some boolean expression and S1, S2, and S3 represent some statement that does not involve control-flow, e.g., assignment statements. We also show statements S4 through S8 representing the higher-level control-flow constructs. For example, S4 represents the while-statement while(E3)S1, and S7 represents the if-then-else statement. 

     S8|             while (E1) {
       | S7|             if (E2)
       |   |     S4|         while (E3)
       |   |       |             S1;
       |   |             else {
       |   | S6| S5|         if (E4)
       |   |   |   |             S2;
       |   |   |             S3
       |   |             }
       |             }

When we implement this translation using backpatching, we maintain, for each boolean expression E, two lists of places in the code for E, which we denote by E.true and E.false. The places on list E.true are those places where we eventually put the label of the statement to which control must flow whenever E is true; E.false similarly lists the places where we put the label that control flows to when E is found to be false. Also, we maintain for each statement S, a list of places where we must put the label to which control flows when S is finished.

There are rules for how S.next is computed from components of the statement S. You should look up or derive the rules for the case when S is a while-statement, an if-statement, an if-then-else statement, and a block of statements. Apply these rules to the higher-level statements S4 through S8. Then identify the correct formula for one of the S.next's from the list below.

 

 

 

 a) 

S5.next = S2.next

 

 b) 

S7.next = S4.next [union] E4.false

 

 c) 

S8.next = E1.false

 

 d) 

S5.next = E4.false

 

 

 

 

 

4.  

In the following expression:

C1 && C2 || C3 && C4

C1, C2, C3, and C4 are simple conditions like x<y that can appear in a single 3-address branching statement. Assume the semantics of AND and OR are the usual "lazy" semantics: evaluate the first argument, and only evaluate the second argument if the result is still in doubt.

Our goal is to generate a jump to label Ltrue whenever the expression is true and generate a jump to Lfalse whenever the expression is false. There are several translations to intermediate code that we could use. Identify a correct translation from the list of choices below.

 

 

 

 a) 

1)

 

ifTrue C1 goto L1

2)

L3:

ifTrue C3 goto L2

3)

 

goto Lfalse

4)

L1:

ifTrue C2 goto L3

5)

 

goto Lfalse

6)

L2:

ifTrue C4 goto Ltrue

7)

 

goto Lfalse

 

 b) 

1)

 

ifTrue C1 goto L1

2)

L3:

ifTrue C3 goto L2

3)

 

goto Lfalse

4)

L1:

ifTrue C2 goto Ltrue

5)

 

goto L3

6)

L2:

ifTrue C4 goto Ltrue

7)

 

goto Lfalse

 

 c) 

1)

 

ifFalse C1 goto L1

2)

 

ifTrue C2 goto Ltrue

3)

 

ifFalse C3 goto Lfalse

4)

L1:

ifTrue C4 goto Ltrue

5)

 

goto Lfalse

 

 d) 

1)

 

ifTrue C3 goto L1

2)

L3:

ifTrue C1 goto L2

3)

 

goto Lfalse

4)

L1:

ifTrue C4 goto Ltrue

5)

 

goto L3

6)

L2:

ifTrue C2 goto Ltrue

7)

 

goto Lfalse

 

 

 

 

 

5.  

Consider the following sketch of C code, where Ei represents some boolean expression and Sj represents some statement or sequence of statements that does not involve control-flow, e.g., assignment statements. 

     while (E1) {
         if (E2)
              while (E3)
                  S1;
         else {
             if (E4)
                 S2;
             S3
         }
     }

If we translate this source code into intermediate code, the sequence of 3-address statements will have the form: 

i1: Code(E1)
i2: Code(E2)
i3: Code(E3)
i4: Code(S1)
i5: Code(E4)
i6: Code(S2)
i7: Code(S3)
i8:

Here, i1,...,i8 are statement labels, and Code(...) represents the sequence of three-address statements that comes from the corresponding source construct. For example, Code(S1) represents the statements that come from the source code statement(s) represented by S1, and i4 is the label of the first of these statements.

When we implement this translation using backpatching, we maintain, for each boolean expression E, two lists of places in the code for E, which we denote by E.true and E.false. The places on list E.true are those places where we eventually put the label of the statement to which control must flow whenever E is true; E.false similarly lists the places where we put the label that control flows to when E is found to be false. Also, we maintain for each statement S, a list of places where we must put the label to which control flows when S is finished.

For each of the four expressions E, determine what label eventually becomes the value of the places on lists E.true and do the same for E.false. For each of the three statements S, determine the eventual value of the places on list S.next. Then, identify from the choices below the statement that is NOT true.

 

 

 

 a) 

E4.false → i1

 

 b) 

E2.false → i5

 

 c) 

S2.next → i7

 

 d) 

S1.next → i3