[llvm-dev] linear-scan RA

[Preston Briggs via llvm-dev]

The phi instruction is irrelevant; just the way I think about things.
The question is if the allocator believes that t0 and t2 interfere.

Perhaps the coalescing example was too simple.
In the general case, we can't coalesce without a notion of interference.
My worry is that looking at interference by ranges of instruction numbers
leads to inaccuracies when a range is introduced by a copy.

But perhaps I should focus on the links and, as you suggested,
the debugging info.

Thanks,
Preston




On Mon, Sep 10, 2018 at 5:02 PM, Matthias Braun <mbraun at apple.com> wrote:

>
>
> On Sep 10, 2018, at 4:53 PM, Preston Briggs <preston.briggs at gmail.com>
> wrote:
>
>
> > The underlying liveness datastructure is a list of ranges where each
> vreg is alive
> > (ranges in terms of instructions numbered). I remember a couple of later
> linear scan
> > papers describing the same thing (Traub et.al. being the first if I
> remember correctly).
> > That should be as accurate as you can get in terms of liveness
> information.
>
> It depends on the details.
> For example, given
>
> t0 = mumble
>
> if (something) {
>   t2 = 3
> }
> else {
>   t3 = t0 + 3
>   print t0
> }
> t4 = phi(t2, t3)
>
>
> it's clear that t2 and t0 shouldn't interfere,
> but some folks might say the ranges overlap.
>
>
> Similarly,
>
> t6 = mumble
> t7 = t6
> t8 = t6 + 5
> t9 = t7 + 10
> print t8, t9
>
>
> Chaitin points out that t6 and t7 shouldn't interfere,
> even though the live ranges overlap.
>
> - We go out of SSA form before allocating registers so you won't see phi
> instruction.
> - In the second case the copy coalesceing pass should have coalesced t6
> and t7.
>
> I would expect both cases to work as you expect.
>
> - Matthias
>
>
>
> Anyway, I'll look at the links.
>
> Thanks,
> Preston
>
>
>
>
>
>>
>> We have separate aggressive coalescing pass before allocation. The
>> register allocator will later perform live range splitting inside the main
>> allocation loop as it seems fit.
>>
>>
>> I ask these questions because we (guys I work with) see loops
>> where there's a little register juggling that seems unnecessary.
>>
>> Well your best bet is to learn reading the output of `-mllvm
>> -print-machineinstrs -mllvm -debug-only=regalloc` (which can take a
>> while)...
>>
>>
>> Is there a paper that describes what y'all do?
>>
>>
>> I'm only aware of a blog post:
>> http://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html
>> and a dev conference talk in 2011:
>> https://llvm.org/devmtg/2011-11/
>>
>> - Matthias
>>
>>
>> Thanks,
>> Preston
>>
>>
>> On Mon, Sep 10, 2018 at 9:57 AM, Matthias Braun <mbraun at apple.com> wrote:
>>
>>> I would not describe LLVMs register allocator as linear scan, it's
>>> closer to graph coloring than linear scan IMO (though doesn't really
>>> matcher either approach).
>>>
>>> RegAllocGreedy assigns the registers in an order based on the priority
>>> value computed in enqueu() we are not just scanning from top to bottom of
>>> the program. We also perform actual interference checks we just don't
>>> happen to build up an explicit interference graph up front.
>>>
>>> - Matthias
>>>
>>> On Sep 10, 2018, at 9:49 AM, Preston Briggs via llvm-dev <
>>> llvm-dev at lists.llvm.org> wrote:
>>>
>>> Why have we ended up using linear-scan register allocation
>>> by default (instead of, e.g., coloring)?
>>>
>>> Thanks,
>>> Preston
>>>
>>>
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> llvm-dev at lists.llvm.org
>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>
>>>
>>>
>>
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20180910/5e5a936b/attachment.html>