[LLVMdev] Supporting Complex Register Allocation Constraints (PBQP Allocator Status Update)

[Jakob Stoklund Olesen]

On Sep 20, 2010, at 4:11 PM, Lang Hames wrote:
> 
> The PBQP allocator uses the aggressive coalescer and optionally adds coalescing costs for any remaining copies to the PBQP problem (if you use -pbqp-coalescing). Unfortunately relying on PBQP's coalescing alone is not an option - the graphs coming out of PHI elimination are very large and without aggressive coalescing to bring the size down the heuristics don't cope well.

Interesting. It sounds like PBQP is pretty much in the same boat as linear scan in that regard.

Another thing to consider is that just because phi elimination generates tons of copies, it doesn't mean those copies are in the right places. An example is a register that is used a lot before and after a loop, but not inside the loop. We may want to spill that register for the duration of the loop, but phi elimination hasn't created any helpful copies near the loop.

PBQP should be able to do well with -disable-physical-join, if it can model all the hinting properly. You might even be able to model multi-register hinting. Currently, CalcSpillWeights.cpp only uses the most desirable register for a hint. PBQP can properly take a second best hint, third best hint, etc as well.


> Currently the PBQP allocator does not do any splitting, however I expect that it should be easy to add support for on-demand splitting, and I'll be looking into it soon-ish.
> 
> I haven't had time to work on the LoopSplitter recently. It looks like SplitKit has subsumed LoopSplitter's functionality. If that's the case then I can go ahead and kill off LoopSplitter.

SplitKit is currently pretty broken, but I am working on fixing it. It turns out you need a good deal of logic to correctly update LiveIntervals after a split. The intention is that you can cut out any connected region of the CFG and use a new register there. Examples of split regions are:

- A loop.
- A well connected cluster of basic blocks.
- A single basic block.
- A sequence of instructions inside a basic block.