On Dec 26, 2015 8:15 PM, "Connor Abbott" <<a href="mailto:cwabbott0@gmail.com">cwabbott0@gmail.com</a>> wrote: > > On Sat, Dec 26, 2015 at 9:55 PM, Jason Ekstrand <<a href="mailto:jason@jlekstrand.net">jason@jlekstrand.net</a>> wrote: > > > > > > On Sat, Dec 26, 2015 at 5:15 PM, Jason Ekstrand <<a href="mailto:jason@jlekstrand.net">jason@jlekstrand.net</a>> > > wrote: > >> > >> > >> > >> On Sat, Dec 26, 2015 at 4:59 PM, Connor Abbott <<a href="mailto:cwabbott0@gmail.com">cwabbott0@gmail.com</a>> > >> wrote: > >>> > >>> On Sat, Dec 26, 2015 at 7:08 PM, Jason Ekstrand <<a href="mailto:jason@jlekstrand.net">jason@jlekstrand.net</a>> > >>> wrote: > >>> > > >>> > On Dec 26, 2015 3:04 PM, "Connor Abbott" <<a href="mailto:cwabbott0@gmail.com">cwabbott0@gmail.com</a>> wrote: > >>> >> > >>> >> On Sat, Dec 26, 2015 at 5:57 PM, Jason Ekstrand <<a href="mailto:jason@jlekstrand.net">jason@jlekstrand.net</a>> > >>> >> wrote: > >>> >> > > >>> >> > On Dec 26, 2015 2:22 PM, "Connor Abbott" <<a href="mailto:cwabbott0@gmail.com">cwabbott0@gmail.com</a>> > >>> >> > 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.