This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: Readings candidate? Optimal Spilling for CISC M. with Few Registers writes:
Okay, they still have time bounds that are unacceptable.

Unless you consider 44 vs 1522 seconds for compiling acceptable.
That's with AMPL and CPLEX.
This is for both optimal spilling, and optimal register allocation.
For the other result, all they've done is taken park and moon's algorithm, and hooked
optimal spilling in front so that they know that they can always
de-coalesce nodes and get a color for them (since the spill points
have already been chosen).
Well duh.

If someone can come up with an implementation of optimal spilling that
is easily able to be hooked up to the new register allocator, doesn't
need a large commercial solving package, and runs in a 
reasonable amount of time, i'll happily look at it.

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

"Winny would spend all of his time practicing limbo.  He got
pretty good.  He could go under a rug.
"-Steven Wright

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]