[llvm-dev] linear-scan RA

[Preston Briggs via llvm-dev]

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

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/64eb560a/attachment.html>