Exercise 11        Name __________________        Score __/38

1. 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. (5) Construct the interference graph; the interference intervals are given below.
  2. (25) Show the steps of the register allocation process as on pages 229-232. When coalescing, state whether using Briggs or George criterion.

When two nodes are MOVE related and interfere, ignore the MOVE since the edge is constrained.

r1 r2 r3 c p s t u  
|   |           f:   c¬r3
|     |              p¬r1
|     | |            if p== 0 goto L1
|     | |            t¬r1
|     | |   |        s¬p
|     | | | |        u¬r1+p
      |   | | |      u¬s+t+u
      |       |      goto L2
      |         L1: u¬1
      |       | L2: r1¬u
|     |              r3¬c
|   |                return        (uses r1, r3)

 

2. (3) 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.

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

 

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

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