llvm dev - Sep 2010 - [LLVMdev] Supporting Complex Register Allocation Constraints (PBQP Allocator Status Update)

Hi Jakob,

> Out of curiosity, how are you dealing with live range splitting and
> coalescing in PBQP? I know you added the LoopSplitter pass.
>
> For linear scan in LLVM we are going in the direction of aggressive
> coalescing before allocation, and on-demand splitting during allocation.
>
> I know that other allocators use no early coalescing, and coalesce during
> allocation.

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.

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.

Cheers,
Lang.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20100921/add0835d/attachment.html>

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.

Hi Jakob,

> PBQP should be able to do well with -disable-physical-join, if it can model
> all the hinting properly.

That's a good point. I'll run some tests and see what it does to
allocation
quality.

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

That sounds fantastic. I'll start playing around with it.

LoopSplitter is currently broken too. I'd agree with your observation on
updating LiveIntervals - I had similar trouble.


Cheers,
Lang.

Regards,
Lang.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20100921/0ba977f5/attachment.html>