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>
> On Sep 10, 2018, at 4:27 PM, Preston Briggs <preston.briggs at gmail.com> wrote: > > 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)?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. 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 <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/ <https://llvm.org/devmtg/2011-11/> - Matthias> > Thanks, > Preston > > > On Mon, Sep 10, 2018 at 9:57 AM, Matthias Braun <mbraun at apple.com <mailto: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 <mailto: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 <mailto:llvm-dev at lists.llvm.org> >> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev <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/06aa8c80/attachment-0001.html>
> The underlying liveness datastructure is a list of ranges where each vregis alive> (ranges in terms of instructions numbered). I remember a couple of laterlinear scan> papers describing the same thing (Traub et.al. being the first if Iremember correctly).> That should be as accurate as you can get in terms of livenessinformation. 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>