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

[Connor Abbott]

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.