Readings candidate? Optimal Spilling for CISC M. with Few Registers

[RDBrown@mira.net]

Is the following paper a candidate for the reading list?

Optimal spilling for CISC machines with few registers
Andrew W Appel & Lal George
p 243-253  ACM SIGPLAN Notices Vol 36 No 5  May 2001

Also available as a Princeton Technical Report.

< http://ncstrl.cs.Princeton.EDU/expand.php?id=TR-630-00 >

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.