This is an archive of the discontinued LLVM Phabricator instance.

[PM/LoopUnswitch] Detect irreducible control flow within loops and skip unswitching non-trivial edges.
ClosedPublic

Authored by chandlerc on Apr 17 2018, 11:12 PM.

Details

Summary

This fixes the bug pointed out in review with non-trivial unswitching.

This also provides a basis that should make it pretty easy to finish
fleshing out a routine to scan an entire function body for irreducible
control flow, but this patch remains minimal for disabling loop
unswitch.

Diff Detail

Event Timeline

chandlerc created this revision.Apr 17 2018, 11:12 PM

@dcaballe added a containsIrreduciableCFG function to include/llvm/Analysis/CFG.h in D40874. I do not have time to take a close look today, but it seems at least for the attached test case, containsIrreduciableCFG does the right thing.

chandlerc planned changes to this revision.Apr 18 2018, 11:00 AM

@dcaballe added a containsIrreduciableCFG function to include/llvm/Analysis/CFG.h in D40874. I do not have time to take a close look today, but it seems at least for the attached test case, containsIrreduciableCFG does the right thing.

Gah.

I looked and looked, even looked specifically in this area, and asked around, all without success at finding this. Now I'm sad I wasted time building a new one. Thanks for pointing it out.

The approaches are... surprisingly different. I computed a slightly different thing. But I think I like the approach of the existing one quite a bit more, although I'm sad about the cost. But I'm willing for us to get bug reports about the cost of this before we really start stressing.

Lemme adjust this to just call that routine. Maybe I can even call it somewhat later to minimize the cost more.

Thanks, Florian!

I looked and looked, even looked specifically in this area, and asked around, all without success at finding this. Now I'm sad I wasted time building a new one. Thanks for pointing it out.

Sorry to hear that. The same was about to happen to me but I just found that implementation in ShrinkWrap and generalized it. Glad to see it's useful somehow.

Thanks,
Diego

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
1932

typo -> complexity

chandlerc updated this revision to Diff 142998.Apr 18 2018, 2:24 PM

Use the existing facilities and sink this past the point where we find actual
unswitch candidates. This should at least avoid the cost of the loop traversal
when there are no loop invariant conditions.

chandlerc updated this revision to Diff 142999.Apr 18 2018, 2:26 PM

And fix typo.

OK, should be ready for review again! A much, much simpler patch now.

fhahn accepted this revision.Apr 19 2018, 7:27 AM

Thanks, LGTM.

Having a single function to detect irreducible CFGs allows us to test it more widely and in case it turns out to be a bottleneck, I think there are a couple of things we can do to improve the performance. The most prominent issue is probably that we re-do work for inner loops
, when loops are processed from inner to outer loop nests.

This revision is now accepted and ready to land.Apr 19 2018, 7:27 AM

Thanks, LGTM.

Having a single function to detect irreducible CFGs allows us to test it more widely and in case it turns out to be a bottleneck, I think there are a couple of things we can do to improve the performance. The most prominent issue is probably that we re-do work for inner loops
, when loops are processed from inner to outer loop nests.

Thanks for the review, and totally agree about the tradeoffs.

This revision was automatically updated to reflect the committed changes.

Ahem... sorry for checking it only now, but this does not seem to address a testcase from PR36379, so it must be a different issue.
I will put this to more testing to see if it improves anything on our workflow.

Hang off on doing more testing. I have more failures w/ non-trivial
unswitching just in the test suite, so I already have multiple
reproductions that I'm working on.