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

[Daniel Berlin <dan at cgsoftware dot com>]

RDBrown@mira.net writes:

> Is the following paper a candidate for the reading list?

No.
It's not really a viable approach, unless it's changed since 
the 2000 version.
It might have, i'll check it out.


> 
> 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.

-- 
"The other night I came home late, and tried to unlock my house
with my car keys.  I started the house up.  So, I drove it
around for a while.  I was speeding, and a cop pulled me over.
He asked where I lived.  I said, "right here, officer".  Later,
I parked it on the freeway, got out, and yelled at all the cars,
"Get out of my driveway!"
"-Steven Wright