MCS-388 Homework 6 (Spring 2003)

Due: May 19, 2003

Note: I strongly encourage you to get me to check individual problems as you do them, in advance of the due date for this assignment.

In this homework, you will carry out the process of register allocation by graph coloring. You will be using the optimistic coloring method described in Briggs et al.'s paper. You will be able to skip the "renumber" step, as our example program has only one live range per name. You will also be able to skip rebuilding the interference graph after performing coalesces, as this makes no difference in the example at hand. As a final simplification, you will also be able to avoid spilling, as we have enough registers.

Here is the three-address intermediate code version of the procedure that you will be working on. Note that it is only a slight variant of the one we have used in class; the outcome may be different, though. We can assume that an invisible definition of the name $a0 reaches the top of the program, and that the name $v0 is live at the bottom of the program, because of an invisible use of $v0 somewhere later on. The parenthesized numbers to the left of each assignment statement will be used to refer to them later in the homework. 

fib:
(1)     n := $a0
(2)     old := 1
(3)     new := 1
(4)     i := 1

loop:
(5)     x1 := i >= n
        if x1 goto done

(6)     x2 := new
(7)     x3 := old + new
(8)     old := x2
(9)     new := x3
(10)    i := i + 1
        goto loop

done:
(11)    $v0 := new

Problem 1

Make a table with four columns and one row for each assignment in the three-address code. The first column should be the instruction number (the parenthesized number in front of the instruction). The second column should be the name defined by the instruction. The third column should be a list of the names used by the instruction. These first three columns are easy, so fill them in first.

The fourth column should be a list of the names live out from the instruction. Don't forget that the code isn't all one long basic block: there is a loop. Also, don't miss the use of x1 in the conditional branch. You should be able to do the necessary data flow analysis by informal understanding of the program, though you could do it by really carrying out one of the data flow analysis algorithms given in the textbook, if you wanted to.

Problem 2

Draw an interference graph with one node for each name in the three address code. You should base the edges of your graph on the table in problem 1. Label each edge with a list of instruction numbers, namely the ones that necessitate the edge. Two nodes are adjacent if one of them is live at a definition point of the other. However, you should not make the source and target of a copy instruction interfere with each other based on that instruction, even if the source continues to be live. You should add additional edges making a clique of $v0, $a0, $t0, $t1, and $t2 nodes, since the intent is that these nodes be precolored with the corresponding (different) registers. Once these edges are in place, add a dotted edge between each pair of nodes connected by a copy instruction. Label the dotted edges with the instruction number(s) of the copy instruction(s) done between that pair of names. For your own use in the following part of the homework, you'll also want a pencil copy of this graph from which you can progressively erase. That pencil copy need not have the edges labeled with instruction numbers.

Also, to make sure your graph is clear to me for grading, please transcribe the information from it into the following tables. First, for every solid edge, enter the instruction numbers that are labeling that edge into the corresponding cell of this table; for the edges between precolored nodes, just enter an X:
$a0$v0$t0$t1$t2noldnewix1x2
$v0          ------------------------------------------------------------
$t0                    ------------------------------------------------------
$t1                              ------------------------------------------------
$t2                                        ------------------------------------------
n                                                  ------------------------------------
old                                                            ------------------------------
new                                                                      ------------------------
i                                                                                ------------------
x1                                                                                          ------------
x2                                                                                                    ------
x3                                                                                                              

Now do the same but for the dotted edges:
$a0$v0$t0$t1$t2noldnewix1x2
$v0          ------------------------------------------------------------
$t0                    ------------------------------------------------------
$t1                              ------------------------------------------------
$t2                                        ------------------------------------------
n                                                  ------------------------------------
old                                                            ------------------------------
new                                                                      ------------------------
i                                                                                ------------------
x1                                                                                          ------------
x2                                                                                                    ------
x3                                                                                                              

Problem 3

Coalesce together any two nodes that are connected by a dotted edge but not a solid one. Suppose they are A and B. On your penciled copy of the graph, modify the node A to be labelled A/B and to have as additional neighbors all of B's neighbors that weren't already neighbors of A. (These neighbors transfered from B to A/B should still be connected using the same kind of line as before: dotted or solid.) Now erase B and the edges connecting to it. Add the pair A/B to a list of coalesces you've done, which is what you should turn in for this problem. Now repeat this coalescing step again, so long as there is any eligible pair of nodes.

Problem 4

Color the coalesced graph using five colors, namely $a0, $v0, $t0, $t1, and $t2, using the procedure from the Briggs et al. paper.

Show your work using a two column table. The first row will be for the first simplify step you do, the second row will be for the second simplify step, etc. You will fill the first column of the table in, working down the table, and then turn around and fill the second column in headed back up the table, during the select phase of the process.

As you work down the table, fill in the first column with the node you have chosen to remove. For each row, you may freely choose any legal simplify step. As you go, use your pencil (particularly the eraser end) to update your penciled copy of the graph. You should be able to reduce the whole graph to nothing but precolored nodes in this way.

Now turn around and head back up the table from bottom to top, doing the select phase of the algorithm. For each row, add the node shown in column one (let's call it A) back into your penciled graph and connect it back up with those of its neighbors that are currently in the penciled graph. Choose a color (register) for the node A. You may choose any of the five registers that doesn't doesn't conflict with the coloring of A's neighbors that are currently in the penciled graph. Put the register (color) you chose in the second column of your table.

Problem 5

Make a new version of the three-address code shown at the beginning of this assignment. Replace each of the names n, old, new, i, x1, x2, and x3 with the register you assigned it in problem 4. However, leave out any copy instructions that would copy from a register to itself.

Instructor: Max Hailperin