On Fri, May 10, 2019 at 12:28 PM Rob Clark <robdcl...@gmail.com> wrote:
>
> On Fri, May 10, 2019 at 7:43 AM Connor Abbott <cwabbo...@gmail.com> wrote:
> >
> > On Fri, May 10, 2019 at 11:47 AM Connor Abbott <cwabbo...@gmail.com> wrote:
> > >
> > >
> > > This way of representing liveness, and then using a coloring register
> > > allocator, is a common anti-pattern in Mesa, that was initially copied
> > > from i965 which dates back to before we knew any better. I really
> > > don't want to see it spread to yet another driver :(.
> > >
> > > Representing live ranges like this is imprecise. If I have a program like
> > > this:
> > >
> > > foo = ...
> > > if (...) {
> > > bar = ...
> > > ... = bar; /* last use of "bar" */
> > > }
> > > ... = foo;
> >
> > Whoops, that should actually read:
> >
> > foo = ...
> > if (...) {
> > bar = ...
> > ... = bar; /* last use of "bar" */
> > } else {
> > ... = foo;
> > }
>
> hmm, my mind is a bit rusty on the live-range analysis, but foo and
> bar do interfere in the if() side of the if/else..
>
> I thought the case we didn't handle properly was more like a loop:
>
> foo = ...
> for (..) {
> bar = foo;
> ... stuff .. foo not live here..
> foo = ...
> }
> ... = foo
>
> where we end up considering foo live during the entire body of the
> loop even though it isn't really. I guess it is the same case as:
>
> foo = ...
> if () {
> bar = foo;
> ...
> foo = ...
> }
> ... = foo;
>
hmm, maybe I mis-read your example (damn gmail hiding quotes).. I
guess last use of bar is in the else block, so we are saying the same
(or similar) thing?
BR,
-R
> BR,
> -R
>
> >
> > >
> > > Then it will say that foo and bar interfere, even when they don't.
> > >
> > > Now, this approximation does make things a bit simpler. But, it turns
> > > out that if you're willing to make it, then the interference graph is
> > > trivially colorable via a simple linear-time algorithm. This is the
> > > basis of "linear-scan" register allocators, including the one in LLVM.
> > > If you want to go down this route, you can, but this hybrid is just
> > > useless as it gives you the worst of both worlds.
> > >
> > > If you want to properly build up the interference graph, it's actually
> > > not that hard. After doing the inter-basic-block liveness analysis,
> > > for each block, you initialize a bitset to the live-out bitset. Then
> > > you walk the block backwards, updating it at each instruction exactly
> > > as in liveness analysis, so that it always represents the live
> > > registers before each instruction. Then you add interferences between
> > > all of the live registers and the register(s) defined at the
> > > instruction.
> > >
> > > One last pitfall I'll mention is that in the real world, you'll also
> > > need to use reachability. If you have something like
> > >
> > > if (...)
> > > foo = ... /* only definition of "foo" */
> > >
> > > ... = foo;
> > >
> > > where foo is only partially defined, then the liveness of foo will
> > > "leak" through the if. To fix this you need to consider what's called
> > > "reachability," i.e. something is only live if, in addition to
> > > potentially being used sometime later, it is reachable (potentially
> > > defined sometime earlier). Reachability analysis is exactly like
> > > liveness analysis, but everything is backwards. i965 does this
> > > properly nowadays, and the change had a huge effect on spilling/RA.
> > >
> > _______________________________________________
> > mesa-dev mailing list
> > mesa-dev@lists.freedesktop.org
> > https://lists.freedesktop.org/mailman/listinfo/mesa-dev
_______________________________________________
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev
