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

[Rob Clark]

On Fri, May 10, 2019 at 12:28 PM Rob Clark <robdclark at gmail.com> wrote:
>
> 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;
>

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