This project consists in the design and implementation of a non-iterative algorithm for register allocation based on graph coloring. We present a simple, linear-time 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 non-iterative 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 home-page.|
|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
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
This file contains some examples of interference graphs.
Such graphs are in the
They have been obtained from the compilation of
|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,
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
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
|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.|
12 de Novembro 2005.