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)

1. No non-precolored nodes degree < 3, pick c for spilling.

 2. (p,s), (t, r1) and (p,r1) are constrained, remove MOVE.

 

 spill c
3. (George) Coalesce u and r1 - every neighbor of u is a neighbor of r1.
Could also have coalesced u and p by George; no (p,u) interference.

 4. Spill t since it is high degree, low use node.

 spill t
spill c
5. Simplify p since low degree, high use.

 6. Simplify s.

 s
p
spill t
spill c

7. Color - u assigned r1, color s with r2 and p with r3. Node t turns into actual spill since no remaining colors.

8. Since actual spilling occurred must rewrite to include spill.

r1 r2 r3 c1 c2 p s t1 t2 u  
|   |               f:   c1¬r3
|     |                  M[cloc]¬c1
|                        p¬r1
|         |              if p== 0 goto L1
|         |              t1¬r1
|         |   |          M[tloc]¬t1
|         |              s¬p
|         | |            u¬r1+p
            |     |      t2¬M[tloc]
            |   | |      u¬s+t2+u
                  |      goto L2
                    L1: u¬1
                  | L2: r1¬u
|                        c2¬M[cloc]
|       |                r3¬c2
|   |                    return        (uses r1, r3)

9. (George) Coalesce c1 and r3, c2 and r3c1.
Or could have simplified t1, then p first.

 10. (George) Coalesce  r1 and u.

 Stack
11. Simplify t1.

 12. Simplify p.

 p
t1
13. Simplify t2.

 14. Simplify s.

 s
t2
p
t1
15. Start popping and assigning registers; u, c1 and c2 are precolored. Rebuild graph making color assignments.

Node    Color

c1        r3
c2        r3
u         r1
s         r3
t2        r2
p         r2
t1        r3
 

 

 16. Rewrite program with assignments.
 
f:   r3¬r3
     M[cloc]¬r3
     r2¬r1
     if r2== 0 goto L1
     r3¬r1
     M[tloc]¬r3
     r3¬r2
     u¬r1+r2
     r2¬M[tloc]
     r1¬r3+r2+r1
     goto L2
L1: r1¬1
L2: r1¬r1
     r3¬M[cloc]
     r3¬r3
     return        (uses r1, r3)
17. Remove unneeded MOVEs.
 
f:   M[cloc]¬r3
     r2¬r1
     if r2== 0 goto L1
     r3¬r1
     M[tloc]¬r3
     r3¬r2
     u¬r1+r2
     r2¬M[tloc]
     r1¬r3+r2+r1
     goto L2
L1: r1¬1
L2: r3¬M[cloc]
     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
   r1¬ M[a]
   r2¬ M[b]
   r3¬ M[c]
   r2¬ r2-r3
   r1¬ r1*r2
   r2¬ M[d]
   r1¬ r1+r2

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

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

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.

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