Michael Matz - Re: Register Allocation (original) (raw)

This is the mail archive of the gcc@gcc.gnu.orgmailing list for the GCC project.

• From: Michael Matz
• To: Peter Bergner
• Cc: Andrew MacLeod , gcc mailing list
• Date: Wed, 23 Nov 2005 15:05:57 +0100 (CET)
• Subject: Re: Register Allocation
• References: <1132246411.10098.153.camel@localhost.localdomain> <1132687596.7748.32.camel@otta.rchland.ibm.com>

Hi,

On Tue, 22 Nov 2005, Peter Bergner wrote:

Spill Location Optimizer [page(s) 11]: * The IBM iSeries backend has this optimization. During spilling, it inserts copies to/from spill pseudos (essentially like another register class) which represent the stores/loads from the stack. These spill pseudos can then be dead code eliminated, coalesced and colored (using an interference graph) just like any other normal pseudo. Normal Chaitin coloring (using k = infinity) does a good job of minimizing the amount of stack space used for spilled pseudos.

This is btw. also done by the new-ra branch. Instead of spilling to stack directly it spills to special new pseudo regs. The obvious problem with that is a phase ordering problem, namely that if you only have pseudo stack locations (the pseudo regs in this case) you don't know the final insn sequence (e.g. if the final stack offset happens to be unrepresentable so that insns are necessary to actually construct the stack address for the load/store). That's why new-ra leaves the stack slots as pseudos only for one round, and then assign real stack positions to them (and recolors the possibly new insns and affected pseudos).

Spill Cost Engine [page(s) 26-29]: * The register allocator should not be estimating the execution frequency of a basic block as 10^nesting level. That information should be coming from the cfg which comes from profile data or from a good static profile. The problem with 10^loop nesting level is that we can overestimate the spill costs for some pseudos. For example: while (...) { <use of "a"> if (...) <use of "b"> else <use of "b" } In the code above, "b"'s spill cost will be twice that of "a", when they really should have the same spill cost.

Nearly. "b" is more costly to spill, code size wise. All else being equal it's better to spill "a" in this case. But the cost is of course not twice as large, as you say. I.e. I agree with you that the metric should be based exclusively on the BB frequencies attached to the CFG, not any nesting level. Also like in new-ra ;)

Ciao, Michael.

• Follow-Ups:
  • Re: Register Allocation
    * From: Peter Bergner
• References:
  • Register Allocation
    * From: Andrew MacLeod
  • Re: Register Allocation
    * From: Peter Bergner