mlcoal

mlcoal is a register coalescing program in OCaml initially written for Appel and George's "Optimal Coalescing Challenge." Now bridged with LAO from STMicroelectronics.

mlcoal is open source and available for download : source or linux 32 bits native code.
Basic usage: mlcoal [options] <input-graph-file> <output-file>
The most useful options are:

• -c to activate the "chordal" conservative rule
• -aggr naive to activate a first naïve aggressive phase
• -only-aggr to perform only aggressive coalescing (i.e., no de-coalescing phase)

Many more options are available, try mlcoal --help to see them.

The description of the input-graph-file and the output-file are given by Appel and George on the Optimal Coalescing Challenge web page. Please note that in their challenge, all nodes of the graphs have degree less than k (but for at most k nodes), while mlcoal accepts any graph that is greedy-k-colorable, i.e., k-colorable using the greedy scheme of Chaitin et al.