This project consists in the design and implementation of a noniterative algorithm for register allocation based on graph coloring. We present a simple, lineartime algorithm which is competitive with the iterated register coalescing strategy of George and Appel. We base the new algorithm on the observation that more than 95% of the methods in the Java 1.5 library have chordal interference graphs. A greedy algorithm can color a chordal graph optimally in linear time, and we can easily add powerful heuristics for spilling and coalescing. Our experimental results show that the new algorithm produces better results than iterated register coalescing for settings with few registers and comparable results for settings with many registers. The implementation of the proposed algorithm, as well as our implementation of the iterated register coalesing algorithm can be downloaded in the links below.
This manuscript describes the implementation of our noniterative algorithm, and shows comparative results between it and the iterated register coalescing of George and Appel. Accepted in APLAS 2005. Due to copyright constraints, the camera ready version is not displayed in this homepage.  
This file contains several bibtex entries on papers about Graph Theory. More specifically, it lists papers related to chordal and perfect graphs, as well as graph coloring.  
This file contains several bibtex entries on papers about register allocation. More specifically, it lists papers related to register allocation based on graph coloring, but also it contains entries about SSA form, linear scan and ILP based register allocation.  
This file contains the implementation of our algorithm, as well as the Iterated
Register Coalescing. The programs are written in Java, and are grouped in a
package called FernandoGraph . In addition to the source code, this
file contains examples of interference graphs that can be colored with the
command java FernandoGraph.MCSGraph FernandoGraph/graphs/fileName.txt
output.txt numregs , where output.txt is the name of the
text file in which the colored graph will be generated, and numregs
denotes the number of registers available for the allocation.


This file contains the programs used in the performance tests. Our
algorithms is tested against the Iterated Register Coalescing allocator.
Besides Java code, some shell scripts can be found here. In order
to compile this files, it is necessary a copy of the JoeQ compiler,
which can be found here.
After setting your execution environment, try the command
./runJava true false 6 . All the class in the standard Java
library will be converted to SSA, back to three address code with
copy instructions, and colored with our algorithm using 6 registers.
The parameters of the command line are as follows: the first parameter
indicates if the SSA transformation must be carried out or not. The
second indicates which algorithm will be used. A true value calls the
iterated register coalescing. False invokes our algorithm. The last
parameter points how many registers must be used in the allocation
process.


This file contains some examples of interference graphs.
Such graphs are in the
Graphivz format.
They have been obtained from the compilation of
java.awt.Component , and can be
used as running cases for graph coloring algorithms.


This file contains a library to handle graphs. It has been implemented with Java 1.5; thus the code is more readable, due to the generic types. But, pay attention, this library is not the one used in the implementation of the register allocation algorithm. This can be found in the links above.  
This file contains an implementation of the chordality test. The main file,
ChordalVerifier.java can be used to test if graphs in the format
of George and Appel (here)
are chordal or not. You can try with those graphs first. Notice that the
precolored registers are not considered in the chordality test. That is
because they have intermittent live ranges, and, if they were
counted, most of the graphs would not be chordal. The source code is small,
and contains comments that can help the reader to understand how the
chordality test works. In order to run this program, it is necessary to
download the
(Graph)
library.


This file contains the implementation of a tool that generates a .dot file from
Java methods. In order to use it, you point your classpath to an implementation
of JoeQ, and to the CFGV package, of course. Then type
java CFGV.DrawerVisitor class [options] . There are some optional
arguments: s to convert the program to SSA form, p to separate branches from
basic blocks, and x to convert PHI functions to copy instructions. If x is
used, then use s and p to generate correct code. One .dot file will be
produced for each method of the target class. This files can be visualized with
graphviz. This visualizer can be freely downloaded in
graphviz.org.
Here is an example of usage:
java5 classpath .:/u/gs3/fernando/Programs/Java/JoeQ :/u/gs3/fernando/Programs/Java/jwutil/main/src/java CFGV.DrawerVisitor java.lang.String d results/ or (if you download the jar files below): java5 classpath .:jwutil.jar:JoeQ.jar CFGV.DrawerVisitor java.lang.String d results/ 

This jar file contains the version of JoeQ that we have used in our project. For the most recent version, check the official website.  
This jar file is the package jwutil , which contains auxiliary classes used
by the JoeQ implementatioin. For the most recent version, check the JoeQ
website.


The API javadoc for the the control flow graph visualizer.  
This file contains the results of the analysis of 23683 methods found in the Java 1.5 library. The columns are organized as follows: First column: the name of the method. Notice that we do not provide the name of the class where the method is defined. Second column: true if the method has a chordal interference graph, and false otherwise. Third column: The number of temporary registers found by our compiler when analyzing the method. Put in another way, that is the number of nodes of the interference graph. Fourth column: the chromatic number of the chordal graph. This is the minimum number of colors necessary to color the interference graph. If the graph is chordal, this number is exact. Otherwise, we report the number or colors found by the greedy coloring when applied on that graph. Fifth column: the number of spills produced by our compiler when coloring that graph. Sixth column: the number of coalescing operations successfully accomplished by our compiler. Seventh column: the number of move instructions found in the control flow graph that gave origin to the interference graph. 
Última atualização:
12 de Novembro 2005.