This is the mail archive of the
mailing list for the GCC project.
Re: Readings candidate? Optimal Spilling for CISC M. with Few Registers
- To: RDBrown at mira dot net
- Subject: Re: Readings candidate? Optimal Spilling for CISC M. with Few Registers
- From: Daniel Berlin <dan at cgsoftware dot com>
- Date: Wed, 01 Aug 2001 21:17:24 -0400
- Cc: RBrown64 at csc dot com dot au, gcc at gcc dot gnu dot org
- References: <E15S6sB-0002ib-00@urtur>
> Is the following paper a candidate for the reading list?
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.
> 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!"