[Mesa-dev] [RFC 11/12] nir: Add return lowering pass

[Jason Ekstrand]

On Dec 26, 2015 8:15 PM, "Connor Abbott" <cwabbott0 at gmail.com> wrote:
>
> On Sat, Dec 26, 2015 at 9:55 PM, Jason Ekstrand <jason at jlekstrand.net>
wrote:
> >
> >
> > On Sat, Dec 26, 2015 at 5:15 PM, Jason Ekstrand <jason at jlekstrand.net>
> > wrote:
> >>
> >>
> >>
> >> On Sat, Dec 26, 2015 at 4:59 PM, Connor Abbott <cwabbott0 at gmail.com>
> >> wrote:
> >>>
> >>> On Sat, Dec 26, 2015 at 7:08 PM, Jason Ekstrand <jason at jlekstrand.net>
> >>> wrote:
> >>> >
> >>> > On Dec 26, 2015 3:04 PM, "Connor Abbott" <cwabbott0 at gmail.com>
wrote:
> >>> >>
> >>> >> On Sat, Dec 26, 2015 at 5:57 PM, Jason Ekstrand <
jason at jlekstrand.net>
> >>> >> wrote:
> >>> >> >
> >>> >> > On Dec 26, 2015 2:22 PM, "Connor Abbott" <cwabbott0 at gmail.com>
> >>> >> > wrote:
> >>
> >>
> >> [snip]
> >>
> >>>
> >>> >> >> There are a few problems with this approach.
> >>> >> >>
> >>> >> >> First off, imagine something like:
> >>> >> >>
> >>> >> >> if (...) {
> >>> >> >>   if (...) return;
> >>> >> >> }
> >>> >> >> ...
> >>> >> >>
> >>> >> >> If I'm reading this correctly, we'd lower this to:
> >>> >> >>
> >>> >> >> if (...) {
> >>> >> >>    if (...) ;
> >>> >> >> }
> >>> >> >> ...
> >>> >> >
> >>> >> > Oops... You're right.  I meant to add returns.  This
> >>> >> >
> >>> >> > if (...) {
> >>> >> >    if (...) return;
> >>> >> >    // foo
> >>> >> > }
> >>> >> >
> >>> >> > Should be lowered to
> >>> >> >
> >>> >> > if (...) {
> >>> >> >    if (...) {
> >>> >> >    } else {
> >>> >> >       // foo
> >>> >> >    }
> >>> >> >    return;
> >>> >> > }
> >>> >> >
> >>> >> > Which we can then lower further.
> >>> >>
> >>> >> I don't think that's correct though. What if there's stuff after
the
> >>> >> outer if? It'll only get executed if the outer if condition is
false,
> >>> >> instead of if either one is false. I think we really need the flag
in
> >>> >> this case.
> >>> >
> >>> > If there's stuff in the outer if, it gets moved into the else
> >>>
> >>> Stuff after the outer if, not in it.
> >>
> >>
> >> Right.  I'm thinking what we probably want is a two-pass approach.
> >>
> >> Pass 1: Loops.  We recurs into all loops and lower returns to set the
> >> return flag and break.  This pass goes top-down and depth-first to
ensure
> >> that we hit the "if (return_flag) return" after the loop it belongs
to.  I
> >> also just realized that "if (return_flag return" needs to be inserted
after
> >> the phi nodes.  We'll need a new cursor helper for that.
> >>
> >> Pass 2: If's not in loops.  At this point, we can ignore loops
completely
> >> since we've already lowered all of them and we need only consider
blocks.
> >> This pass is a post-order bottom-up DFS.  We look at if/else blocks
and, if
> >> one of them has a return, move the stuff after the node into whichever
case
> >> doesn't return and put a return after the node.
> >>
> >> How does that sound?
> >
> >
> > Bah!  I just realized why this won't work  If I have
> >
> > if (...) {
> >    // foo
> >    return;
> > }
> > // bar
> >
> > it'll get replace with
> >
> > if (...) {
> >    // foo
> > } else {
> >    // bar
> > }
> >
> > and we're still left with the problem of where to place the return.  I'm
> > trying to get rid of it, so it seems natural to place it outside the
> > function.  However, bar might not have returned at the end. so we may
need
> > to keep going.  For top-level, I thing this works ok because we can just
> > pull the rest of the function into the else.  However, for nested if's,
it
> > doesn't work.  I guess I do need the return_flag for everything.  Let's
hope
> > dead_cf does a good job...
> >
>
> Yeah. The way I think about it is that if we have the following:
>
> if (A) {
>   if (B) return;
>   foo();
> }
> bar();
>
> then bar is predicated on !(A and B), but if we simply pull things
> into the other branch, then we get:
>
> if (A) {
>   if (!B) {
>     foo();
>   }
>   return;
> }
> bar();
>
> and now bar is predicated on !A. In other words, when we moved the
> return down we messed up the condition under which code after the if
> is run, which is only ok if there isn't stuff after the if (i.e. if
> we're on the top level). I think we need something similar to what you
> have now, except that when we hit a return outside of a loop, we emit
> code to set return_flag and return progress, propagating it upwards,
> and then when we've made progress on either branch of an if we need to
> wrap the stuff after the if (if there is any) in if (!return_flag) {}.
> Then, pulling stuff into the other branch becomes an optimization, one
> that we can either do here or with a few other passes as I mentioned
> earlier (or perhaps both). I'm a fan of the "keep it simple and
> correct, then optimize" approach, even if it means more code, so I'd
> prefer to clean up the mess afterwards.

Yup.  That's my new plan.  I was trying to be too clever.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freedesktop.org/archives/mesa-dev/attachments/20151226/c48fa6b9/attachment.html>