This is the mail archive of the
mailing list for the GCC project.
Readings candidate? Optimal Spilling for CISC M. with Few Registers
- To: gcc at gcc dot gnu dot org
- Subject: Readings candidate? Optimal Spilling for CISC M. with Few Registers
- From: RDBrown at mira dot net
- Date: Thu, 2 Aug 2001 11:01:59 +1000 (EST)
- Reply-To: RDBrown at mira dot net,RBrown64 at csc dot com dot au
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.
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.