Register Allocation via Coloring of Chordal Graphs

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.

Download it 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.
Download it 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.
Download it 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.
Download it 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 num-regs, where output.txt is the name of the text file in which the colored graph will be generated, and num-regs denotes the number of registers available for the allocation.
Download it 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.
Download it 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.
Download it 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.
Download it 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 pre-colored 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.
Download it 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/
Download it This jar file contains the version of JoeQ that we have used in our project. For the most recent version, check the official website.
Download it 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.
Download it The API javadoc for the the control flow graph visualizer.
Download it 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.


Write to me

Última atualização: 12 de Novembro 2005.

Last update: November 12th, 2005.