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.