This is an archive of the discontinued LLVM Phabricator instance.

[PM/LoopUnswitch] Fix PR37651 by correctly invalidating SCEV when unswitching loops.
ClosedPublic

Authored by chandlerc on Jun 1 2018, 3:41 AM.

Details

Summary

Original patch trying to address this was sent in D47624, but that didn't quite
handle things correctly. There are two key principles used to select whether
and how to invalidate SCEV-cached information about loops:

  1. We must invalidate any info SCEV has cached before unswitching as we may change (or destroy) the loop structure by the act of unswitching, and make it hard to recover everything we want to invalidate within SCEV.
  1. We need to invalidate all of the loops whose CFGs are mutated by the unswitching. Notably, this isn't the *entire* loop nest, this is every loop contained by the outermost loop reached by an exit block relevant to the unswitch.

And we need to do this even when doing trivial unswitching.

I've added more focused tests that directly check that SCEV starts off with
imprecise information and after unswitching (and simplifying instructions)
re-querying SCEV will produce precise information. These tests also
specifically work to check that an *outer* loop's information becomes precise.

However, the testing here is still a bit imperfect. Crafting test cases that
reliably fail to be analyzed by SCEV before unswitching and succeed afterward
proved ... very, very hard. It took me several hours and careful work to build
these, and I'm not optimistic about necessarily coming up with more to cover
more elaborate possibilities. Fortunately, the code pattern we are testing here
in the pass is really straightforward and reliable.

Thanks to Max Kazantsev for the initial work on this and to Hal Finkel for
helping me talk through approaches to test this stuff even if it didn't come to
much.

Diff Detail

Event Timeline

mkazantsev created this revision.Jun 1 2018, 3:41 AM

I don't know SimpleLoopUnswitch but this fix at least makes the crash I saw go away, and similar fixes have been done in several other passes already so it looks good to me.

Thanks for looking at this!

lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
2015 ↗(On Diff #149427)

Definitely isn't. Feel free to make the FIXME more explicit. Also, do you have a minimal test case? Good to put that in a PR.

2017 ↗(On Diff #149427)

We need this to happen for both pass managers. I would suggest passing SCEV into unswitchLoop for both and sinking this invalidation into that common code.

test/Transforms/SimpleLoopUnswitch/invalidate_scev.ll
1 ↗(On Diff #149427)

Can you instead just require SCEV before and verify it after unswitch? Would seem more focused.

mkazantsev added inline comments.Jun 3 2018, 6:50 PM
lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
2015 ↗(On Diff #149427)

It fails 2 existing unit tests, I will add them into the comment.

mkazantsev added inline comments.Jun 3 2018, 8:41 PM
lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
2017 ↗(On Diff #149427)

I agree that we should do it, however we need to get rid of this isInvalid() check before. Once this code becomes just if (Changed), we can sink it to the common part. I will add a TODO on that.

mkazantsev added inline comments.Jun 3 2018, 9:08 PM
test/Transforms/SimpleLoopUnswitch/invalidate_scev.ll
1 ↗(On Diff #149427)

I tried to construct a simpler test, but it appears to not be so easy. The tricky bit is that we don't just need SCEV to be constructed, we also need some requests of explicit taken count calculation made (it is calculated lazily), so that some data gets into the cache first and then becomes invalid because of unswitching. I will try to write it as a C++ unit test on that.

mkazantsev added inline comments.Jun 3 2018, 9:20 PM
test/Transforms/SimpleLoopUnswitch/invalidate_scev.ll
1 ↗(On Diff #149427)

Never mind, print<scalar-evolution> is enough to make the right queries.

mkazantsev added inline comments.Jun 3 2018, 10:02 PM
lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
2017 ↗(On Diff #149427)

Same tests fails under new PM, so it makes sense to sink now.

mkazantsev marked 3 inline comments as done.
chandlerc commandeered this revision.Jun 5 2018, 2:13 PM
chandlerc edited reviewers, added: mkazantsev; removed: chandlerc.

I think a significantly different approach to invalidating this is necessary. Also, i'd like to much more directly test the SCEV updates. Let me create a new patch here and see what you think.

chandlerc updated this revision to Diff 150039.Jun 5 2018, 2:16 PM
chandlerc retitled this revision from [SimpleLoopUnswitch] Invalidate SCEV after making structural changes to a loop to [PM/LoopUnswitch] Fix PR37651 by correctly invalidating SCEV when unswitching loops..
chandlerc edited the summary of this revision. (Show Details)

Update with a new approach and some new testing.

Add Hal to this review since I was discussing it with him.

mkazantsev added inline comments.Jun 7 2018, 8:03 PM
llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
489

Why it is enough? Imagine that you have

for (...) { // Loop 1
  for (...) { // Loop 2
    for (...) { // Loop 3
      ...
     }
  }
}

Let L be Loop 3 and all exits from L lead to Loop 2. Then, if I understand the code correctly, OuterL will be found as Loop 2 and we invalidate it (and its internals). But what if what we are going to do with Loop 3 also affects trip count in Loop 1?

chandlerc added inline comments.Jun 7 2018, 10:22 PM
llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
489

Do you know how to build such a test case? I wasn't able to craft anything, but I'm not a SCEV expert.

Not sure how to construct a test that will fail an assert, however the general idea is that, for example, a block that goes to method exit from the innermost look is also an exiting block for all its containing loops, up to the topmost parent. It means that this exiting block may be considered for iter count calculation for all those loops. From this point of view, there is no practical difference between the immediate parent and any other top loop.

mkazantsev added inline comments.Jun 8 2018, 10:59 PM
llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
489

Not sure how to construct a test that will fail an assert, however the general idea is that, for example, a block that goes to method exit from the innermost look is also an exiting block for all its containing loops, up to the topmost parent. It means that this exiting block may be considered for iter count calculation for all those loops. From this point of view, there is no practical difference between the immediate parent and any other top loop.

chandlerc added inline comments.Jun 8 2018, 11:20 PM
llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp
489

Yes, but this code finds the outermost exit block and uses that as the root to invalidate. So the case you're describing should be correctly handled.

The question is can a loop outside of this outermost exit block's loop have its iteration count change. I keep trying to build a test case for this and failing.

Notably, the best idea I had doesn't actually work: if you have a loop-invariant full exit from the loop nest which will make the number of loop exits go from 2 to 1 after unswitching, it might seem like this will impact every loop in the nest. But in practice, we will unswitch this one loop at a time. So if we have loops A, B, and C (C is the inner most), we will move the multi-exit from C to B in the first one. Both A and B will still be multi-exit after this, so invalidating A can't help anything.

Ka-Ka added a subscriber: Ka-Ka.Jun 11 2018, 11:25 PM
mkazantsev accepted this revision.Jun 12 2018, 5:54 PM

LGTM

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

I don't have a counter-argument that would convince at least myself that you are wrong, but I still don't feel 100% sure that it will be enough for all cases. However we already have experience of tracking down issues of this kind, so if there is a bug here, it is easy to catch and fix it later. Let's agree on your point.

llvm/test/Transforms/SimpleLoopUnswitch/update-scev.ll
189

EOF

This revision is now accepted and ready to land.Jun 12 2018, 5:54 PM

Will you submit this chandlerc or is there anything preventing that?

Thanks!

chandlerc updated this revision to Diff 153878.Jul 3 2018, 2:14 AM
chandlerc marked an inline comment as done.

Rebase, merge with all the work, and clean up a few loose ends.

Thanks for review and for the prompting. Landing this now. Sorry I lost track of it a bit.

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

Honestly, I'm in the same boat as you -- I don't feel 100%. But I don't think we should blindly invalidate without at least a clear rationale, and ideally a test case to demonstrate the nature of the failure.

So yeah, let's leave as-is, and if we can come up with a test case, we'll be able to expand it easily.