[Mesa-dev] [RFC PATCH 03/17] eir: add live ranges pass

[Rob Clark]

On Fri, May 10, 2019 at 7:43 AM Connor Abbott <cwabbott0 at gmail.com> wrote:
>
> On Fri, May 10, 2019 at 11:47 AM Connor Abbott <cwabbott0 at 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;

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 at lists.freedesktop.org
> https://lists.freedesktop.org/mailman/listinfo/mesa-dev