Sample graph coloring problems
Want to investigate graph-coloring algorithms without writing a compiler to generate the data? This file contains 27,922 actual register-interference graphs generated by Standard ML of New Jersey version 1.09, compiling itself. The format is
Graph 374:
K=21
32 --> 6 7 8 0 1 2
33 --> 6 7 8 0 1
34 --> 7 8 0 6 35 36 37 38 39
35 --> 34 8 0 7 36 37 38 39 1
36 --> 34 35 0 8 37 38 39 1 6
37 --> 34 35 36 0 38 39 1 6 7
38 --> 34 35 36 37
39 --> 35 36 37 34 1 6 7 8
3<->32 2<->33 1<->34 6<->35 7<->36 8<->37 0<->38 34<->1 35<->6 36<->7 37<->8 39<->0
The notation K=21 at the beginning of each graph indicates the number of registers (colors) that the compiler has available for coloring this graph. We assume there are K precolored nodes, numbered 0 through K-1, that all interfere with each other. But the clique of precolored nodes is not explicitly listed in the file. The interference edges are listed with a single-headed arrow. In the example, node 32 interferes with nodes 6, 7, 8, 0, 1, and 2.
Furthermore, "move" edges are shown. The last line indicates that there is a move between nodes 3 and 32, a move between 2 and 33, and so on. If possible, nodes 3 and 32 should be colored with the same color.
Background information
Based on the number of registers available on the machine, the compiler (or human tuner of the compiler) chooses several parameters: - How many registers to use for parameter passing
- How agressively to spread n-tuples (records) out into registers
- How many callee-save registers to use
- How many registers to reserve for special purposes such as the heap-limit indicator Higher values for these parameters leads to more register pressure and (if there are not too many spills) less memory traffic. Better graph-coloring algorithms would, in principle, allow higher values for these parameters without undue spilling.
These graphs are generated for a 32-register machine, but with 11 registers reserved by the machine architecture and the ML system for special purposes; thus K=21.
Perhaps an interesting experiment would be to try to color these graphs using a smaller K value than 21. In this case, for example K=18, there would be only 18 precolored nodes, and only 18 colors would be available for coloring. If the graphs could be successfully colored without too much spilling, this would indicate that the parameters 1-4 (above) could be increased, leading to better performance.
Limitations
A graph-coloring register allocator sometimes needs to spill, that is, when the graph is not K-colorable it must keep some variables in memory instead of registers. Spilling must be guided by spill-cost information; that is, for each node in the graph it is useful to know how often it is used in inner loops, etc. Unfortunately the graphs presented here lack spill-cost information. Citation
If you use this data for measurements that you publish, please give appropriate credit to Andrew W. Appel and Lal George. Disclaimer
This is not the data used in empirical measurements reported in: Iterated Register Coalescing, Lal George and Andrew W. Appel, ACM Transactions on Programming Languages and Systems 18(3) 300-324, May 1996. ©1996 ACM.