[LLVMdev] PBQP spilling

Tue Mar 10 09:51:38 PDT 2015

FWIW: I've been out of the register allocator game for a few years (I used
to be deep in it, sadly), but in GCC, XLC, etc, we tried pre-splitting
approaches, and came to the same conclusion.

In GCC, for the new register allocator project, we tried optimistic
coalescing, iterated coalescing, and pre-splitting.

Pre-splitting turned out the worst of all three.
Optimistic was the best, performance wise.

(Since then, GCC currently has a complex register allocator that isn't
worth discussing in such generalities)

On Tue, Mar 10, 2015 at 9:30 AM, Quentin Colombet <qcolombet at apple.com>
wrote:

>
> On Mar 10, 2015, at 1:43 AM, Arnaud A. de Grandmaison <
> arnaud.degrandmaison at arm.com> wrote:
>
> Both approaches are not exclusive. I would even think it makes sense to
> have a pre-split pass to prepare the graph, with a global view, and later
> on use use trySplit (or an equivalent) to handle the local coloring issues.
>
>
> Indeed, however, a pre-split pass is against the paradigm used in the
> greedy allocator, which is aggressive coalescing, then split on demand.
>
> Cheers,
> -Quentin
>
>
> *From:* Quentin Colombet [mailto:qcolombet at apple.com <qcolombet at apple.com>
> ]
> *Sent:* 09 March 2015 23:08
> *To:* Lang Hames
> *Cc:* Jonas Paulsson; llvmdev at cs.uiuc.edu; Arnaud De Grandmaison
> *Subject:* Re: PBQP spilling
>
> Hi Lang,
>
> Thanks for the clarifications.
>
>
> On Mar 9, 2015, at 2:30 PM, Lang Hames <lhames at gmail.com> wrote:
>
> Hi Quentin, Jonas,
>
> Splitting fits in with PBQP reasonably well, at least conceptually. The
> PBQP graph is designed to be mutable, so there is no problem with updating
> it when splitting.
>
> As I see it, there are two logical places to integrate splitting into PBQP:
>
> 1) Split during spilling -- If a PBQP solution selects the spill option
> for a node, rather than spill immediately, split the interval first. This
> seems (superficially) like an opportunity to use trySplit, but I haven't
> looked at the code for it. If trySplit is looking at the existing
> allocation state to make those decisions we may have trouble: In RAGreedy
> some "current" colorings may be revisited, but during spilling in PBQP
> we're guaranteed that *all*  colorings will be revisited in the next round,
> which may throw trySplit's heuristics out.
>
>
> trySplit splits either the given virtual register or some of its
> interference to make it colorable based indeed on the current state of
> allocation. That being said, I do not know if would really be a problem if
> you would revisited everything in the next round. I guess it would depend
> how you handle coalescing for those new split points.
>
> I thought the PBQP was not revisiting everything that is why I believed
> trySplit as it is what not a good candidate for splitting in PBQP since it
> requires you reconsider some of the nodes you already colored. But now, I
> remember the IRC approach and yeah I believe it would work (modulo the
> coalescing of the new split points and the cost of rebuild/update part of
> the graph).
>
>
>
> 2) Pre-split -- We could have a pre-pass split live ranges at sensible
> points (e.g. around loops) before we enter the coloring/spilling loop. PBQP
> tries to coalesce as it colors, so it will try to undo these splits where
> possible. I assume trySplit would not be a good fit here, but we may be
> able to reuse other parts of the splitting code.
>
> I agree.
>
> Cheers,
> -Quentin
>
>
>
> We do want to add splitting support to PBQP, so we should be on the
> lookout for opportunities to share code where it makes sense.
>
> Cheers,
> Lang.
>
>
> On Sat, Mar 7, 2015 at 5:01 AM, Quentin Colombet <qcolombet at apple.com>
> wrote:
> Hi Jonas,
>
>
> On Mar 6, 2015, at 12:31 AM, Jonas Paulsson <jonas.paulsson at ericsson.com>
> wrote:
>
> Hi,
>
> I have worked a little on the PBQP register allocator, and it is quite
> clear (at least to me) that it is not even a serious alternative to
> RegAllocGreedy at the moment, due to the poor handling of spilling. As
> Arnaud wrote below, it is not optimizing spilling at all, but rather just
> spills anything that does not get an assignment. The result is a lot more
> spill/reload instructions than needed.
>
> In RegAllocBase.h it says “…Register allocation complexity, and generated
> code performance is determined by the effectiveness of live range splitting
> rather than optimal coloring…”. I would then think that any register
> allocation algorithm should benefit from this, but find that only
> RegAllocGreedy is doing live range splitting, and that the code for doing
> this is local to that allocator.
>
> I would like to suggest a refactoring to make RAGreedy::trySplit() and its
> sub functions callable from any register allocator. Perhaps part of
> SplitEditor?
>
>
> What do you expect from sure refactoring?
>
> In the current form, live-range splitting for the PBQP implies to rebuild
> part of the graph and I suspect it would be easier to rebuild it from
> scratch than trying to update it if we would want to use it.
> I believe that to have an efficient implementation, the PBQP splitting
> should work directly on the graph and not on the program as it is the case
> for the Greedy Allocator.
>
> Now, regarding the fast register allocator, I am not sure it could cope at
> all with live-range splitting as it would change some allocation decisions
> that were supposed to be final.
>
> The bottom line is I do not believe there is much to share here.
>
> Cheers,
> -Quentin
>
>
>
> What do you think about this?
>
> /Jonas
>
>
> *From:* Arnaud A. de Grandmaison [mailto:arnaud.degrandmaison at arm.com
> <arnaud.degrandmaison at arm.com>]
> *Sent:* den 4 mars 2015 15:43
> *To:* Jonas Paulsson; Lang Hames
> *Cc:* llvmdev at cs.uiuc.edu
> *Subject:* RE: PBQP spilling
>
> Yes, for now the spilling is done in the most basic way, i.e. it’s
> functionally correct --- but not efficient. The focus was on the allocator
> itself, not on the spilling. As you noticed, the work still to be done in
> this area is live range splitting, and smarter spill code insertion.
> Another area is improving the reduction order, to make the allocator less
> sensitive to the reduction order.
>
> There is no official plan; we started to discuss that with Lang some time
> ago, but none of us had time to dive into it yet. Any help appreciated
> there J.
>
> Cheers,
> Arnaud
>
> *From:* Jonas Paulsson [mailto:jonas.paulsson at ericsson.com
> <jonas.paulsson at ericsson.com>]
> *Sent:* 04 March 2015 13:51
> *To:* Lang Hames; Arnaud De Grandmaison
> *Cc:* llvmdev at cs.uiuc.edu
> *Subject:* PBQP spilling
>
> Hi,
>
> I would like to ask about PBQPs use of InlineSpiller. The code output when
> using PBQP gets a lot bigger compared to when using RegAllocGreedy. PBQP
> does not split the live intervals, and a lot more (often redundant) reload
> instructions are emitted as a result, it seems. I wonder why this is, and
> if there are any plans to improve on this point?
>
> /Jonas Paulsson
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150310/7ea254f3/attachment.html>