Punctual coalescing

Abstract. Compilers use register coalescing to avoid generating code for copy instructions. For architectures with register aliasing such as x86, Smith, Ramsey, and Holloway (2004) presented a polynomial-time ap-proach, while Scholz and Eckstein (2002) presented an optimal, exponen-tial-time approach together with a near-optimal, quadratic-time heuris-tic. Both methods scale poorly after aggressive live range splitting, espe-cially for programs in elementary form where live ranges are split at ev-ery program point. In contrast, we mentioned in a previous paper (2008), without giving details, that we have a scalable, linear-time heuristic for programs in elementary form. In an effort to formalize that heuristic, we discovered an even better algorithm, called Punctual Coalescing, which we present here. Punctual Coalescing is scalable, linear time, locally op-timal in general, close to globally optimal for straight-line code, and proven correct with the Twelf theorem prover. We define global optimal-ity with an ILP-formulation and we show via experiments that Punctual Coalescing compares well to this and two other approaches.