Page MenuHomePhabricator

[PM/LoopUnswitch] Add partial non-trivial unswitching for invariant conditions feeding a chain of `and`s or `or`s for a branch.

Authored by chandlerc on May 30 2018, 2:33 AM.



Much like with full non-trivial unswitching, we rely on the pass manager to
handle iterating until all of the profitable unswitches have been done. This is
to allow other more profitable unswitches to fire on any of the cloned, simpler
versions of the loop if viable.

Threading the partial unswiching through the non-trivial unswitching logic
motivated some minor refactorings. If those are too disruptive to make it
reasonable to review this patch, I can separate them out, but it'll be somewhat
timeconsuming so I wanted to send it for initial review as-is. Feel free to
tell me whether it warrants pulling apart.

I've tried to re-use (and factor out) logic form the partial trivial
unswitching, but not as much could be shared as I had haped. Still, this wasn't
as bad as I naively expected.

Some basic testing is added, but I probably need more. Suggestions for things
you'd like to see tested more than welcome. One thing I'd like to do is add
some testing that when we schedule this with loop-instsimplify it effectively
cleans up the cruft created.

Last but not least, this uncovered a bug that has been in loop cloning the
entire time for non-trivial unswitching. Specifically, we didn't correctly add
the outer-most cloned loop to the list of cloned loops. This meant that LCSSA
wouldn't be updated for it hypothetically, and more significantly that we would
never visit it in the loop pass manager. I noticed this while checking
loop-instsimplify by hand. I'll try to separate this bugfix out into its own
patch with a more focused test. But it is just one line, so shouldn't
significantly confuse the review here.

Depends on D46706 for the trivial case.

After this patch, the only missing "feature" in this unswitch I'm aware of us
non-trivial unswitching of switches. I'll try implementing *full* non-trivial
unswitching of switches (which is at least a sound thing to implement), but
*partial* non-trivial unswitching of switches is something I don't see any
sound and principled way to implement. I also have no interesting test cases
for the latter, so I'm not really worried. The rest of the things that need to
be ported are bug-fixes and more narrow / targeted support for specific issues.

Diff Detail


Event Timeline

chandlerc created this revision.May 30 2018, 2:33 AM
chandlerc updated this revision to Diff 149600.Jun 1 2018, 7:03 PM

Rebase and ping.

chandlerc updated this revision to Diff 150041.Jun 5 2018, 2:18 PM

Rebase and ping again. Really looking for review on this one as well.

Logic lgtm.

162 ↗(On Diff #149600)

Nit (feel free to ignore): I would find clearer the intention if this was written as:

if (Direction)
   for all invariants
        Cond = CreateOr(Cond, Inv)
   for all invariants
        Cond = CreateAnd(Cond, Inv)

( or are you relying on this being unswitched in bootstrap? :-) )

1809 ↗(On Diff #149600)


1814 ↗(On Diff #149600)

Is it possible for neither LoopPH or ClonedPH to dominate the invariant use?

chandlerc updated this revision to Diff 150195.Jun 6 2018, 1:29 PM
chandlerc marked an inline comment as done.

Fix typo spotted in review.

Thanks for the review! Based on LGTM, I'll land once the dependent patch lands. Give a shout if you still have concerns though.

162 ↗(On Diff #149600)

The reason I don't want to do this is because it requires the for loop itself to be duplicated which has some logic in it, so I'd rather keep this factoring.

(But no, I wasn't just *trying* to exercise the self)

1814 ↗(On Diff #149600)

Yeah. Consider a user completely outside of the loop, for example some random other use of a function argument.

asbirlea accepted this revision.Jun 18 2018, 2:57 PM


This revision is now accepted and ready to land.Jun 18 2018, 2:57 PM
This revision was automatically updated to reflect the committed changes.