llvm dev - Sep 2018 - linear-scan RA

Why have we ended up using linear-scan register allocation
by default (instead of, e.g., coloring)?

Thanks,
Preston
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180910/2f468e56/attachment.html>

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/3cf75b3d/attachment.html>

How precise is the interference checking (to my mind, a great weakness of
linear scan)?
Is there way to do coalescing (the great strength of coloring)?

I ask these questions because we (guys I work with) see loops
where there's a little register juggling that seems unnecessary.

Is there a paper that describes what y'all do?

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