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; 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