Coloring register pairs

Reviewer: Martin Joseph Jourdan

Register allocation is one of the tasks of a compiler back end that is crucial for producing efficient code. One of the best-performing register allocation algorithms up to now was developed by Chaitin and colleagues and is based on graph coloring. That algorithm behaves badly on machines with operations requiring that their operands be placed in adjacent register pairs, however. In such cases, it overestimates the need for spilling, because it invokes spilling as soon as the interference graph might be non-colorable (pessimistic behavior); as the authors show, requiring register pairs creates many more opportunities for this. This research paper proposes a better alternative. It is based on a variation of Chaitin's algorithm, devised by the same authors, in which spilling is handled optimistically by leaving the decision to the phase that determines the coloring; hence, spilling is invoked only when the coloring actually fails. On this basis, the authors present a way to construct the interference graph to handle register pairs, and they use examples to show that their method performs better than Chaitin's. The paper is well written and easy to understand. Since the problem it contributes to solving is important, reading it is worthwhile for everybody interested or involved in compiler construction. This paper is a perfect example of the kind of works LOPLAS seeks to publish: concise, clear, interesting, and immediately applicable.