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

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.

`$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 | $t2 | n | old | new | i | x1 | x2 | |
---|---|---|---|---|---|---|---|---|---|---|---|

$v0 | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | |

$t0 | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ||

$t1 | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | |||

$t2 | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ||||

n | ------ | ------ | ------ | ------ | ------ | ------ | |||||

old | ------ | ------ | ------ | ------ | ------ | ||||||

new | ------ | ------ | ------ | ------ | |||||||

i | ------ | ------ | ------ | ||||||||

x1 | ------ | ------ | |||||||||

x2 | ------ | ||||||||||

x3 |

Now do the same but for the dotted edges:

$a0 | $v0 | $t0 | $t1 | $t2 | n | old | new | i | x1 | x2 | |
---|---|---|---|---|---|---|---|---|---|---|---|

$v0 | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | |

$t0 | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ||

$t1 | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ | |||

$t2 | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ||||

n | ------ | ------ | ------ | ------ | ------ | ------ | |||||

old | ------ | ------ | ------ | ------ | ------ | ||||||

new | ------ | ------ | ------ | ------ | |||||||

i | ------ | ------ | ------ | ||||||||

x1 | ------ | ------ | |||||||||

x2 | ------ | ||||||||||

x3 |

`$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.

`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