Test 3 and answers

  1. For the following expression, draw the tree and generate Jouette-machine instructions using Maximal Munch. Circle the tiles (as in Figure 9.2) numbering them and show corresponding sequence of Jouette instructions that result.

    MOVE(MEM( + ( + (CONST 1000, MEM(TEMP x)), TEMP fp)), MEM(TEMP y))

    4. LOAD t3 <- M[tx]

    3. ADDI t2 <- t3+1000

    2. ADD t1 <- t2+tfp

    1. MOVEM M[t1] <- M[ty]

     

  2. The IR at left translates into the Mips instructions with TEMPs at right. Give the def, use and succ sets.
MOVE(a,CONST(3))
LABEL(F)
MOVE(b,BINOP(BINOP.PLUS,a,CONST(5)))
CJUMP(Tree.CJUMP.NE, a, b, T, F)
MOVE(c,BINOP(BINOP.PLUS,a,b))
LABEL(T)
MOVE(c,c)

 		 0. OPER[li `d0 3][t33 ][][]
1. MOVE[ move `d0 `s0][t1][t33]
2. LABEL[F:][F]
3. OPER[add `d0 `s0 5][t34 ][t1 ][]
4. MOVE[ move `d0 `s0][t2][t34]
5. OPER[ bne `s0 `s1 T][][t1 t2 ][TF]
6. OPER[add `d0 `s0 `s1][t35 ][t1 t2 ][]
7. MOVE[ move `d0 `s0][t3][t35]
8. LABEL[T:][T]
9. MOVE[ move `d0 `s0][t3][t3]
use

0. {}
1. {t33}
2. {}
3. {t1}
4. {t34}
5. {t1, t2}
6. {t1 t2}
7. {t35}
8. {}
9. {t3}

 def

0. {t33}
1. {t1}
2. {}
3. {t34}
4. {t2}
5. {}
6. {t35}
7. {t3}
8. {}
9. {t3}

 succ

0. {1}
1. {2}
2. {3}
3. {4}
4. {5}
5. {2,8}
6. {7}
7. {8}
8. {9}
9. {}

3. Give the flow graph.

0: t33 <- ; goto 1
1: t1 <= t33 ; goto 2
2: <- ; goto 3
3: t34 <- t1 ; goto 4
4: t2 <= t34 ; goto 5
5: <- t1 t2 ; goto 2 8
6: t35 <- t1 t2 ; goto 7
7: t3 <= t35 ; goto 8
8: <- ; goto 9
9: t3 <= t3 ; goto

4. Give the first complete pass in computing live in and out sets starting at statement 9 to 0.

in

0:{ }
1:{ t33 }
2:{ }
3:{ t1 }
4:{ t34 }
5:{ t2 t1 }
6:{ t2 t1 }
7:{ t35 }
8:{ }
9:{ t3 }

 out

0:{ t33 }
1:{ }
2:{ t1 }
3:{ t34 }
4:{ t2 t1 }
5:{ }
6:{ t35 }
7:{ }
8:{ t3 }
9:{ }

 

5. From the given final def and out sets of the flow graph determine the interference graph.

def

0. {t33}
1. {t1}
2. {}
3. {t34}
4. {t2}
5. {}
6. {t35}
7. {t3}
8. {}
9. {t3}

 out

0:{ t3 t33 }
1:{ t3 t1 }
2:{ t3 t1 }
3:{ t3 t34 t1 }
4:{ t2 t3 t1 }
5:{ t3 t1 }
6:{ t35 }
7:{ t3 }
8:{ t3 }
9:{ }
for each node in the flow graph
  for each def temporary at that node
     for each live out temporary at that node
         addEdge(def, out);
         addEdge(out, def);
Interference Graph

t33: t33 t3
t3: t3 t2 t34 t1 t33
t1: t2 t34 t1 t3
t34: t1 t34 t3
t2: t1 t3 t2
t35: t35		            
           

6. The following program has been compiled for a machine with 3 registers: r1, r2, r3; r1 and r2 are caller-save argument registers and r3 is callee-save.

  1. Construct the interference graph; the interference intervals are given below.
  2. Show the steps of the register allocation process as on pages 229-232. When coalescing, state whether using Briggs or George criterion.
|     |              a¬r1
r1 r2 r3 c a b d e  
|   |           f:   c¬r3
|     |              a¬r1
      | |            b¬a+1
      | | |          d¬a+b
      | | | |        d¬d+1
      | | |          e¬a-b
      | | |   |      e¬e+a+b
      |              r3¬c
    |                return        (uses r3)

1. Coalesce d and e since do not interfere.
    Form union of interference edges.

 

 2. Spill c, used little, much interference.

                                           Stack

           spill c

 
3. Simplify e&d.                        Stack

           e&d
                                              spill c

 4. Simplify b.                      Stack

                    b
                                          e&d
                                         spill c
5. Coalesce r1 and a.            Stack

                            b
                                          e&d
                                         spill c

 6. Color attempt fails on c.

    Rewrite with actual spill of c.

 

r1 r2 r3 c' c'' a b d e  
|   |             f:   c'¬r3
|     |                M[cloc]¬c'
|                      a¬r1
          |            b¬a+1
          | |          d¬a+b
          | | |        d¬d+1
          | |          e¬a-b
          | |   |      e¬e+a+b
                       c''¬M[cloc]
        |              r3¬c''
    |                  return        (uses r3)

1. Coalesce c'' by George.
    Coalesce c' by Briggs.
 

 

 2. Coalesce e&d by George.

                                          

      

3. Simplify e&d.                Stack

    e&d

 4. Simplify b.                      Stack

                    b
                                          e&d
5. Coalesce r1 and a.       Stack

                   b
                                     e&d

 6. Color:
  • c'=r3
  • c''=r3
  • a=r1
  • b=r2
  • e=r3
  • d=r3

 

Apply coloring
f:   r3¬r3
     M[cloc]¬r3
     r1¬r1
     r2¬r1+1
     r3¬r1+r2
     r3¬r3+1
     r3¬r1-r2
     r3¬r3+r1+r2
     r3¬M[cloc]
     r3¬r3
     return        (uses r3)
Delete trivial MOVEs
f:  
     M[cloc]¬r3
    
     r2¬r1+1
     r3¬r1+r2
     r3¬r3+1
     r3¬r1-r2
     r3¬r3+r1+r2
     r3¬M[cloc]
    
     return        (uses r3)

 

7. The code at right is similar to that generated by MaximalMunch for the tree where temporaries are generated as needed. Give the register allocation for the code using SimpleAlloc, ALGORITHM 11.9.

      +
     /  \
    a   *
        /  \
       -    d
     /  \
    b    c     		   t1¬ M[a]
   t2¬ M[b]
   t3¬ M[c]
   t4¬ t2-t3
   t5¬ M[d]
   t6¬ t4*t5
   t7¬ t1+t6

   r1¬ M[a]
   r2¬ M[b]
   r3¬ M[c]
   r2¬ r2-r3
   r3¬ M[d]
   r2¬ r2*r3
   r1¬ r1+r2

 

 

8. Label using ALGORITHM 11.10, the need of each tile (node) of the tree in Question 7.

 2   +
     /  \
 1 a    *  2
        /  \
  2   -    d 1
     /  \
 1 b    c  1

 

 

9. Use ALGORITHM 11.11 to allocate registers for the labeled tree of Question 8; start with n=1. Note the correction in the notes to the algorithm.

   r1¬ M[b]
   r2¬ M[c]
   r1¬ r1-r2
   r2¬ M[d]
   r1¬ r1*r2
   r2¬ M[a]
   r1¬ r2+r1

 

10.