Optimal Spilling for CISC Machines with Few Registers

Abstract:

Many graph-coloring register-allocation algorithms don't work well for
machines with few registers. Heuristics for live-range splitting are
complex or suboptimal; heuristics for register assignment rarely
factor the presence of fancy addressing modes;
these problems are more severe the fewer registers there are to work
with. We show how to optimally split live ranges and optimally use
addressing modes, where the optimality condition measures dynamically
weighted loads and stores but not register-register moves. Our
algorithm uses integer linear programming but is much more efficient
than previous ILP-based approaches to register allocation. We then
show a variant of Park and Moon's optimistic coalescing algorithm that
does a very good (though not provably optimal) job of removing the
register-register moves. The result is Pentium code that is 9.5%
faster than code generated by SSA-based splitting with iterated
register coalescing.

Revised version, March 2001: [Postscript
][PDF]