MC97 Lab 7: Liveness analysis or register allocation (Spring 1999)

Due: May 19, 1999

For this lab, you may either implement a module that uses liveness analysis to construct an interference graph (chapter 10) or one that colors the interference graph in order to do register allocation (chapter 11). In either case you will have a full, working compiler, since I provide compiled versions of these modules and of the rest of the compiler. You will not need any code from prior labs.

Getting and using the compiler

Rather than give you a whole bunch of directories (one per package) with a whole bunch of .class files in them, I'm giving you a "jar" file, which is simply a single file containing all the various classes. Most of these are versions Appel wrote, or at most slight variants by me of his code. As such, they are covered by his license, which you should read.

To run the compiler, you will need to set your CLASSPATH to include java_cup (as in prior labs) and the tiger.jar file. You can do this as follows:

set max=~max
setenv CLASSPATH $max/JavaLib
setenv CLASSPATH \
 "$CLASSPATH":$max/www-docs/courses/S1999/MC97/labs/lab7/tiger.jar

Now you can run the compiler. First I'll show compiling the sample queens.tig program with the default liveness analysis and register allocation modules. (Later I'll show how to substitute in different modules.) You should do this in a fresh empty directory created for the purpose, since it creates lots of different output files. Note that the first line below ends with a space and then a dot.

cp ~max/www-docs/courses/S1999/MC97/tiger/testcases/queens.tig .
java Main.Main queens.tig

This should produce eight different output files. The MIPS assembly language output goes in queens.tig.s. (I'll explain how to assemble and run it below.) The abstract syntax tree is displayed in absyn.out. Then there are two files per function in the program. (The functions in the queens program are printboard, try, and tigmain, which is the anonymous top-level program). For each function name, str1.functionname contains the debugging output from compiler passes prior to construction of the interference graph, while foo.functionname contains a dump of the flow and interference graphs. (There are typically more than one flow and interference graph per file, because if the register allocator spills at all, the graph construction is repeated with the modified program.) These foo files will be important in your lab. They contain not only the graphs themselves, but also the times taken by the liveness analysis module to produce the interference graphs.

To actually assemble and run the queens.tig.s file, you will need to use one of the SGI machines (though you could log into it over the network). Alternatively, you could use the xspim simulator on any of our machines; see the separate instructions. On an SGI, you would download the runtime.c file, which contains definitions of library routines, and then do the following:

cc -c runtime.c
cc -c queens.tig.s
cc -o queens queens.tig.o runtime.o
./queens

The first line compiles the runtime library with the C compiler; you only need to do this once, and can use the resulting runtime.o with all your Tiger compilation results. The second line assembles the queens.tig.s file produced by the Tiger compiler and produces a corresponding queens.tig.o object file. The third line links these two object files together to produce an executable file, which it calls queens. The final line executes that program, which should output all the different board configurations that solve the 8-queens problem. You might also like to redirect the output to a file; this is particularly helpful when comparing output from multiple versions. Note that you can use essentially the same process to compile, assemble, link, and run any Tiger program; there is nothing special about queens.

I have actually provided you with three different implementations of liveness analysis. Thus you can try out the mechanism for swapping implementations even without writing one of your own. One uses the iterative approach with the nodes considered in forward program order each iteration, one does the same but with the nodes considered in reverse program order each iteration, and the third uses variable-at-a-time analysis. However, as a puzzle for you I have given them non-descriptive names. In no particular order, they are in the MaxA, MaxB, and MaxC packages. Try the three out, and from the times they take (which are in the foo files) try to guess which is which, or at least see if you can guess one of them.

To run the compiler with the MaxB version (for example), you would use the command

java -DRegAlloc.InterferenceGraphFactory=MaxB.InterferenceGraphFactory\
 Main.Main queens.tig

The default InterferenceGraphFactory if you don't specify is the MaxA version. If you choose to write your own liveness analysis module, you would select it in the same way. (See the next section.) You can also substitute in an alternative graph coloring module in a comparable way, though I have only provided one (Appel's) so this swapping mechanism is only useful if you write your own coloring module. To explicitly select Appel's (which is the default anyway), you would do

java -DRegAlloc.ColorFactory=Appel.ColorFactory\
 Main.Main queens.tig

See the section on the coloring module for more on swapping in your own one of these. You can also specify a choice for both the InterferenceGraphFactory and the ColorFactory, if you want to be super explicit.

Writing your own liveness analysis

If you choose to write your own liveness analysis, you will need to write at least two classes. One must implement the interface RegAlloc.InterferenceGraphFactory while the other must be a concrete class that extends the abstract class RegAlloc.InterferenceGraph. You can call these two classes by any names you like, so long as they are in your own package. The factory class must construct instances of the interference graph class. Suppose you call your factory class Joe.IGF (i.e., the IGF class within the Joe package). Suppose further that Joe is a subdirectory of your current directory, and that IGF.java is a file in that directory containing your classes. Then you could compile your module and specify that it should be used (rather than mine) in compiling the queens program as follows:

set max=~max
setenv CLASSPATH $max/JavaLib
setenv CLASSPATH \
 "$CLASSPATH":$max/www-docs/courses/S1999/MC97/labs/lab7/tiger.jar
setenv CLASSPATH "$CLASSPATH":.
cp ~max/www-docs/courses/S1999/MC97/tiger/testcases/queens.tig .
java -DRegAlloc.InterferenceGraphFactory=Joe.IGF Main.Main queens.tig

Here are some helpful hints. Be sure to ask if you need more:

I provided a constructor for Graph.Node that takes a String to use as the Node's name. In order for your interference graphs (in the foo files) to look the same as mine, you should name each Node in the interference graph with the name of the corresponding Temp.
In order to use the above constructor for Graph.Node, you will have to ignore (not use) the newNode method in the Graph.Graph class. If g is a Graph, g.newNode() is completely equivalent to new Graph.Node(g). You should use the latter of these two versions, but with an extra String argument passed to the constructor to specify the Node's name.
Note that although an interference graph is conceptually undirected, Appel has chosen to represent it as an asymmetrical directed graph, and says (on page 233) which direction the edges should point. If you get this backwards, your graph won't match mine, and your assembly language output may also (as a result) be different, but it should still produce the same ultimate output when assembled and run. The simplest would be to follow Appel's convention.
Before the interference graph is printed out to the foo file or used for register allocation, I sort it into alphabetical order, so that if we produce the same graph but list the nodes in different orders, we will get identical output files.
The RegAlloc.InterferenceGraph. class provides an implementation of spillCost that pretends all nodes cost 1 to spill. You can just ignore this issue, implementing only the other methods in your concrete subclass.

Once you have a working liveness analysis, compare the times it take (for various flowgraphs) with those of the MaxA,B,C versions. Since you know what algorithm you used, you may now have a better guess which of my versions is which.

Writing your own coloring module

If you choose to write your own coloring module, you will need to write at least two classes. One must implement the interface RegAlloc.ColorFactory while the other must implement the interface RegAlloc.Color. You would set your CLASSPATH, compile your classes, and use them in place of mine by a process analogous to that described in the prior section.

Here are some helpful hints. Be sure to ask if you need more:

These two interfaces are a slight deviation from Appel's description, in which he has Color as a concrete class. This is to allow switching of implementations. The arguments to the factory's getColor method are those that would be provided to the constructor of Color, were Color a concrete class.
Appel's implementation doesn't do any coalescing. You might want to skip it too in order to make your life easier and your results more comparable.
In any case, your results are not likely to be identical to Appel's, because of the arbitrary choices made in the course of coloring. Compare the assembly language output by hand to see if the differences seem reasonable, and check that when you assemble and run the output, it produces the same behavior.
If spilling is necessary, you just need to make the list of spills available. The part of the compiler I provide will then take care of rebuilding the flow and interference graphs and invoking your coloring module again.

Write-up

If you choose to implement the liveness analysis (interference graph construction), include the following in your lab report:

your performance comparison of my three implementations, and any a priori speculations on which algorithm each of them uses
your decision of which algorithm to implement, and other important design decisions you made, such as what data structures to use
your code
evidence that your module works correctly
performance comparison of your module with mine, and any modification to your speculation on my algorithms.

If you choose to implement the graph coloring module (register allocator), include the following in your lab report:

simplifying decisions you have made (such as parts of the full algorithm to leave out)
design decisions, such as data structures used
your code
evidence that your module works correctly

Instructor: Max Hailperin