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.
$t2nodes, 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.
$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.
x3with 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