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

[chandlerc]

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.

2. 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.

[uabelho]

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.

[chandlerc]

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]

lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

2015 ↗

(On Diff #149427)

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

[mkazantsev]

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]

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]

test/Transforms/SimpleLoopUnswitch/invalidate_scev.ll

1 ↗

(On Diff #149427)

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

[mkazantsev]

lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

2017 ↗

(On Diff #149427)

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

[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]

Update with a new approach and some new testing.

[chandlerc]

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

[mkazantsev]

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]

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.

[mkazantsev]

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]

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]

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.

[mkazantsev]

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

[uabelho]

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

Thanks!

[chandlerc]

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

[chandlerc]

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.

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

 ///
 /// If this routine fails to unswitch the branch it returns false.
 ///
 /// If the branch can be unswitched, this routine splits the preheader and
 /// hoists the branch above that split. Preserves loop simplified form
 /// (splitting the exit block as necessary). It simplifies the branch within
 /// the loop to an unconditional branch but doesn't remove it entirely. Further
 /// cleanup can be done with some simplify-cfg like pass.
+///
+/// If `SE` is not null, it will be updated based on the potential loop SCEVs
+/// invalidated by this.
 static bool unswitchTrivialBranch(Loop &L, BranchInst &BI, DominatorTree &DT,
-                                  LoopInfo &LI) {
+                                  LoopInfo &LI, ScalarEvolution *SE) {
   assert(BI.isConditional() && "Can only unswitch a conditional branch!");
   LLVM_DEBUG(dbgs() << "  Trying to unswitch branch: " << BI << "\n");
 
   // The loop invariant values that we want to unswitch.
   TinyPtrVector<Value *> Invariants;
 
   // When true, we're fully unswitching the branch rather than just unswitching
   // some input conditions to the branch.
LLVM_DEBUG({
     for (Value *Invariant : Invariants) {
       dbgs() << "      " << *Invariant << " == true";
       if (Invariant != Invariants.back())
         dbgs() << " ||";
       dbgs() << "\n";
     }
   });
 
+  // If we have scalar evolutions, we need to invalidate them including this
+  // loop and the loop containing the exit block.
+  if (SE) {
+    if (Loop *ExitL = LI.getLoopFor(LoopExitBB))
+      SE->forgetLoop(ExitL);
+    else
+      // Forget the entire nest as this exits the entire nest.
+      SE->forgetTopmostLoop(&L);
+  }
+
   // Split the preheader, so that we know that there is a safe place to insert
   // the conditional branch. We will change the preheader to have a conditional
   // branch on LoopCond.
   BasicBlock *OldPH = L.getLoopPreheader();
   BasicBlock *NewPH = SplitEdge(OldPH, L.getHeader(), &DT, &LI);
 
   // Now that we have a place to insert the conditional branch, create a place
   // to branch to: this is the exit block out of the loop that we are

 /// (splitting the exit blocks as necessary). It simplifies the switch within
 /// the loop by removing now-dead cases. If the default case is one of those
 /// unswitched, it replaces its destination with a new basic block containing
 /// only unreachable. Such basic blocks, while technically loop exits, are not
 /// considered for unswitching so this is a stable transform and the same
 /// switch will not be revisited. If after unswitching there is only a single
 /// in-loop successor, the switch is further simplified to an unconditional
 /// branch. Still more cleanup can be done with some simplify-cfg like pass.
+///
+/// If `SE` is not null, it will be updated based on the potential loop SCEVs
+/// invalidated by this.
 static bool unswitchTrivialSwitch(Loop &L, SwitchInst &SI, DominatorTree &DT,
-                                  LoopInfo &LI) {
+                                  LoopInfo &LI, ScalarEvolution *SE) {
   LLVM_DEBUG(dbgs() << "  Trying to unswitch switch: " << SI << "\n");
   Value *LoopCond = SI.getCondition();
 
   // If this isn't switching on an invariant condition, we can't unswitch it.
   if (!L.isLoopInvariant(LoopCond))
     return false;
 
   auto *ParentBB = SI.getParent();
if (!L.contains(SI.getDefaultDest()) &&
       areLoopExitPHIsLoopInvariant(L, *ParentBB, *SI.getDefaultDest()) &&
       !isa<UnreachableInst>(SI.getDefaultDest()->getTerminator()))
     DefaultExitBB = SI.getDefaultDest();
   else if (ExitCaseIndices.empty())
     return false;
 
   LLVM_DEBUG(dbgs() << "    unswitching trivial cases...\n");
 
+  // We may need to invalidate SCEVs for the outermost loop reached by any of
+  // the exits.
+  Loop *OuterL = &L;
+
   SmallVector<std::pair<ConstantInt *, BasicBlock *>, 4> ExitCases;
   ExitCases.reserve(ExitCaseIndices.size());
   // We walk the case indices backwards so that we remove the last case first
   // and don't disrupt the earlier indices.
   for (unsigned Index : reverse(ExitCaseIndices)) {
     auto CaseI = SI.case_begin() + Index;
+    // Compute the outer loop from this exit.
+    Loop *ExitL = LI.getLoopFor(CaseI->getCaseSuccessor());
+    if (!ExitL || ExitL->contains(OuterL))
+      OuterL = ExitL;
     // Save the value of this case.
     ExitCases.push_back({CaseI->getCaseValue(), CaseI->getCaseSuccessor()});
     // Delete the unswitched cases.
     SI.removeCase(CaseI);
   }
 
+  if (SE) {
+    if (OuterL)
+      SE->forgetLoop(OuterL);
+    else
+      SE->forgetTopmostLoop(&L);
+  }
+
   // Check if after this all of the remaining cases point at the same
   // successor.
   BasicBlock *CommonSuccBB = nullptr;
   if (SI.getNumCases() > 0 &&
       std::all_of(std::next(SI.case_begin()), SI.case_end(),
                   [&SI](const SwitchInst::CaseHandle &Case) {
                     return Case.getCaseSuccessor() ==
                            SI.case_begin()->getCaseSuccessor();

 /// any side effects occur. These can potentially be unswitched without
 /// duplicating the loop. If a branch or switch is successfully unswitched the
 /// scanning continues to see if subsequent branches or switches have become
 /// trivial. Once all trivial candidates have been unswitched, this routine
 /// returns.
 ///
 /// The return value indicates whether anything was unswitched (and therefore
 /// changed).
+///
+/// If `SE` is not null, it will be updated based on the potential loop SCEVs
+/// invalidated by this.
 static bool unswitchAllTrivialConditions(Loop &L, DominatorTree &DT,
-                                         LoopInfo &LI) {
+                                         LoopInfo &LI, ScalarEvolution *SE) {
   bool Changed = false;
 
   // If loop header has only one reachable successor we should keep looking for
   // trivial condition candidates in the successor as well. An alternative is
   // to constant fold conditions and merge successors into loop header (then we
   // only need to check header's terminator). The reason for not doing this in
   // LoopUnswitch pass is that it could potentially break LoopPassManager's
   // invariants. Folding dead branches could either eliminate the current loop
do {
 
     if (auto *SI = dyn_cast<SwitchInst>(CurrentTerm)) {
       // Don't bother trying to unswitch past a switch with a constant
       // condition. This should be removed prior to running this pass by
       // simplify-cfg.
       if (isa<Constant>(SI->getCondition()))
         return Changed;
 
-      if (!unswitchTrivialSwitch(L, *SI, DT, LI))
+      if (!unswitchTrivialSwitch(L, *SI, DT, LI, SE))
         // Couldn't unswitch this one so we're done.
         return Changed;
 
       // Mark that we managed to unswitch something.
       Changed = true;
 
       // If unswitching turned the terminator into an unconditional branch then
       // we can continue. The unswitching logic specifically works to fold any
do {
     // Don't bother trying to unswitch past an unconditional branch or a branch
     // with a constant value. These should be removed by simplify-cfg prior to
     // running this pass.
     if (!BI->isConditional() || isa<Constant>(BI->getCondition()))
       return Changed;
 
     // Found a trivial condition candidate: non-foldable conditional branch. If
     // we fail to unswitch this, we can't do anything else that is trivial.
-    if (!unswitchTrivialBranch(L, *BI, DT, LI))
+    if (!unswitchTrivialBranch(L, *BI, DT, LI, SE))
       return Changed;
 
     // Mark that we managed to unswitch something.
     Changed = true;
 
     // If we only unswitched some of the conditions feeding the branch, we won't
     // have collapsed it to a single successor.
     BI = cast<BranchInst>(CurrentBB->getTerminator());
for (DomTreeNode *ChildN : *N) {
       DomWorklist.push_back(ChildN);
     }
   } while (!DomWorklist.empty());
 }
 
 static bool unswitchNontrivialInvariants(
     Loop &L, TerminatorInst &TI, ArrayRef<Value *> Invariants,
     DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC,
-    function_ref<void(bool, ArrayRef<Loop *>)> UnswitchCB) {
+    function_ref<void(bool, ArrayRef<Loop *>)> UnswitchCB,
+    ScalarEvolution *SE) {
   auto *ParentBB = TI.getParent();
   BranchInst *BI = dyn_cast<BranchInst>(&TI);
   SwitchInst *SI = BI ? nullptr : cast<SwitchInst>(&TI);
 
   // We can only unswitch switches, conditional branches with an invariant
   // condition, or combining invariant conditions with an instruction.
   assert((SI || BI->isConditional()) &&
          "Can only unswitch switches and conditional branch!");
if (!NewOuterExitL) {
       // We exited the entire nest with this block, so we're done.
       OuterExitL = nullptr;
       break;
     }
     if (NewOuterExitL != OuterExitL && NewOuterExitL->contains(OuterExitL))
       OuterExitL = NewOuterExitL;
   }
 
+  // At this point, we're definitely going to unswitch something so invalidate
+  // any cached information in ScalarEvolution for the outer most loop
+  // containing an exit block and all nested loops.
+  if (SE) {
+    if (OuterExitL)
+      SE->forgetLoop(OuterExitL);
+    else
+      SE->forgetTopmostLoop(&L);
+  }
+
   // If the edge from this terminator to a successor dominates that successor,
   // store a map from each block in its dominator subtree to it. This lets us
   // tell when cloning for a particular successor if a block is dominated by
   // some *other* successor with a single data structure. We use this to
   // significantly reduce cloning.
   SmallDenseMap<BasicBlock *, BasicBlock *, 16> DominatingSucc;
   for (auto *SuccBB : llvm::concat<BasicBlock *const>(
            makeArrayRef(RetainedSuccBB), UnswitchedSuccBBs))
int Cost = std::accumulate(
         return Sum + computeDomSubtreeCost(*ChildN, BBCostMap, DTCostMap);
       });
   bool Inserted = DTCostMap.insert({&N, Cost}).second;
   (void)Inserted;
   assert(Inserted && "Should not insert a node while visiting children!");
   return Cost;
 }
 
-static bool unswitchBestCondition(
-    Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC,
-    TargetTransformInfo &TTI,
-    function_ref<void(bool, ArrayRef<Loop *>)> UnswitchCB) {
+static bool
+unswitchBestCondition(Loop &L, DominatorTree &DT, LoopInfo &LI,
+                      AssumptionCache &AC, TargetTransformInfo &TTI,
+                      function_ref<void(bool, ArrayRef<Loop *>)> UnswitchCB,
+                      ScalarEvolution *SE) {
   // Collect all invariant conditions within this loop (as opposed to an inner
   // loop which would be handled when visiting that inner loop).
   SmallVector<std::pair<TerminatorInst *, TinyPtrVector<Value *>>, 4>
       UnswitchCandidates;
   for (auto *BB : L.blocks()) {
     if (LI.getLoopFor(BB) != &L)
       continue;
 
LLVM_DEBUG(dbgs() << "Cannot unswitch, lowest cost found: "
                       << BestUnswitchCost << "\n");
     return false;
   }
 
   LLVM_DEBUG(dbgs() << "  Trying to unswitch non-trivial (cost = "
                     << BestUnswitchCost << ") terminator: " << *BestUnswitchTI
                     << "\n");
   return unswitchNontrivialInvariants(
-      L, *BestUnswitchTI, BestUnswitchInvariants, DT, LI, AC, UnswitchCB);
+      L, *BestUnswitchTI, BestUnswitchInvariants, DT, LI, AC, UnswitchCB, SE);
 }
 
 /// Unswitch control flow predicated on loop invariant conditions.
 ///
 /// This first hoists all branches or switches which are trivial (IE, do not
 /// require duplicating any part of the loop) out of the loop body. It then
 /// looks at other loop invariant control flows and tries to unswitch those as
 /// well by cloning the loop if the result is small enough.
-static bool
-unswitchLoop(Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC,
-             TargetTransformInfo &TTI, bool NonTrivial,
-             function_ref<void(bool, ArrayRef<Loop *>)> UnswitchCB) {
+///
+/// The `DT`, `LI`, `AC`, `TTI` parameters are required analyses that are also
+/// updated based on the unswitch.
+///
+/// If either `NonTrivial` is true or the flag `EnableNonTrivialUnswitch` is
+/// true, we will attempt to do non-trivial unswitching as well as trivial
+/// unswitching.
+///
+/// The `UnswitchCB` callback provided will be run after unswitching is
+/// complete, with the first parameter set to `true` if the provided loop
+/// remains a loop, and a list of new sibling loops created.
+///
+/// If `SE` is non-null, we will update that analysis based on the unswitching
+/// done.
+static bool unswitchLoop(Loop &L, DominatorTree &DT, LoopInfo &LI,
+                         AssumptionCache &AC, TargetTransformInfo &TTI,
+                         bool NonTrivial,
+                         function_ref<void(bool, ArrayRef<Loop *>)> UnswitchCB,
+                         ScalarEvolution *SE) {
   assert(L.isRecursivelyLCSSAForm(DT, LI) &&
          "Loops must be in LCSSA form before unswitching.");
   bool Changed = false;
 
   // Must be in loop simplified form: we need a preheader and dedicated exits.
   if (!L.isLoopSimplifyForm())
     return false;
 
   // Try trivial unswitch first before loop over other basic blocks in the loop.
-  if (unswitchAllTrivialConditions(L, DT, LI)) {
+  if (unswitchAllTrivialConditions(L, DT, LI, SE)) {
     // If we unswitched successfully we will want to clean up the loop before
     // processing it further so just mark it as unswitched and return.
     UnswitchCB(/*CurrentLoopValid*/ true, {});
     return true;
   }
 
   // If we're not doing non-trivial unswitching, we're done. We both accept
   // a parameter but also check a local flag that can be used for testing
   // a debugging.
   if (!NonTrivial && !EnableNonTrivialUnswitch)
     return false;
 
   // For non-trivial unswitching, because it often creates new loops, we rely on
   // the pass manager to iterate on the loops rather than trying to immediately
   // reach a fixed point. There is no substantial advantage to iterating
   // internally, and if any of the new loops are simplified enough to contain
   // trivial unswitching we want to prefer those.
 
   // Try to unswitch the best invariant condition. We prefer this full unswitch to
   // a partial unswitch when possible below the threshold.
-  if (unswitchBestCondition(L, DT, LI, AC, TTI, UnswitchCB))
+  if (unswitchBestCondition(L, DT, LI, AC, TTI, UnswitchCB, SE))
     return true;
 
   // No other opportunities to unswitch.
   return Changed;
 }
 
 PreservedAnalyses SimpleLoopUnswitchPass::run(Loop &L, LoopAnalysisManager &AM,
                                               LoopStandardAnalysisResults &AR,
auto UnswitchCB = [&L, &U, &LoopName](bool CurrentLoopValid,
     // If the current loop remains valid, we should revisit it to catch any
     // other unswitch opportunities. Otherwise, we need to mark it as deleted.
     if (CurrentLoopValid)
       U.revisitCurrentLoop();
     else
       U.markLoopAsDeleted(L, LoopName);
   };
 
-  if (!unswitchLoop(L, AR.DT, AR.LI, AR.AC, AR.TTI, NonTrivial,
-                    UnswitchCB))
+  if (!unswitchLoop(L, AR.DT, AR.LI, AR.AC, AR.TTI, NonTrivial, UnswitchCB,
+                    &AR.SE))
     return PreservedAnalyses::all();
 
   // Historically this pass has had issues with the dominator tree so verify it
   // in asserts builds.
   assert(AR.DT.verify(DominatorTree::VerificationLevel::Fast));
   return getLoopPassPreservedAnalyses();
 }
 
bool SimpleLoopUnswitchLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) {
   LLVM_DEBUG(dbgs() << "Unswitching loop in " << F.getName() << ": " << *L
                     << "\n");
 
   auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
   auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
 
+  auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
+  auto *SE = SEWP ? &SEWP->getSE() : nullptr;
+
   auto UnswitchCB = [&L, &LPM](bool CurrentLoopValid,
                                ArrayRef<Loop *> NewLoops) {
     // If we did a non-trivial unswitch, we have added new (cloned) loops.
     for (auto *NewL : NewLoops)
       LPM.addLoop(*NewL);
 
     // If the current loop remains valid, re-add it to the queue. This is
     // a little wasteful as we'll finish processing the current loop as well,
     // but it is the best we can do in the old PM.
     if (CurrentLoopValid)
       LPM.addLoop(*L);
     else
       LPM.markLoopAsDeleted(*L);
   };
 
-  bool Changed =
-      unswitchLoop(*L, DT, LI, AC, TTI, NonTrivial, UnswitchCB);
+  bool Changed = unswitchLoop(*L, DT, LI, AC, TTI, NonTrivial, UnswitchCB, SE);
 
   // If anything was unswitched, also clear any cached information about this
   // loop.
   LPM.deleteSimpleAnalysisLoop(L);
 
   // Historically this pass has had issues with the dominator tree so verify it
   // in asserts builds.
   assert(DT.verify(DominatorTree::VerificationLevel::Fast));

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

+; RUN: opt -passes='print<scalar-evolution>,loop(unswitch,loop-instsimplify),print<scalar-evolution>' -enable-nontrivial-unswitch -S < %s 2>%t.scev | FileCheck %s
+; RUN: FileCheck %s --check-prefix=SCEV < %t.scev
+
+target triple = "x86_64-unknown-linux-gnu"
+
+declare void @f()
+
+; Check that trivially unswitching an inner loop resets both the inner and outer
+; loop trip count.
+define void @test1(i32 %n, i32 %m, i1 %cond) {
+; Check that SCEV has no trip count before unswitching.
+; SCEV-LABEL: Determining loop execution counts for: @test1
+; SCEV: Loop %inner_loop_begin: <multiple exits> Unpredictable backedge-taken count.
+; SCEV: Loop %outer_loop_begin: Unpredictable backedge-taken count.
+;
+; Now check that after unswitching and simplifying instructions we get clean
+; backedge-taken counts.
+; SCEV-LABEL: Determining loop execution counts for: @test1
+; SCEV: Loop %inner_loop_begin: backedge-taken count is (-1 + (1 smax %m))<nsw>
+; SCEV: Loop %outer_loop_begin: backedge-taken count is (-1 + (1 smax %n))<nsw>
+;
+; And verify the code matches what we expect.
+; CHECK-LABEL: define void @test1(
+entry:
+  br label %outer_loop_begin
+; Ensure the outer loop didn't get unswitched.
+; CHECK:       entry:
+; CHECK-NEXT:    br label %outer_loop_begin
+
+outer_loop_begin:
+  %i = phi i32 [ %i.next, %outer_loop_latch ], [ 0, %entry ]
+  ; Block unswitching of the outer loop with a noduplicate call.
+  call void @f() noduplicate
+  br label %inner_loop_begin
+; Ensure the inner loop got unswitched into the outer loop.
+; CHECK:       outer_loop_begin:
+; CHECK-NEXT:    %{{.*}} = phi i32
+; CHECK-NEXT:    call void @f()
+; CHECK-NEXT:    br i1 %cond,    
+
+inner_loop_begin:
+  %j = phi i32 [ %j.next, %inner_loop_latch ], [ 0, %outer_loop_begin ]
+  br i1 %cond, label %inner_loop_latch, label %inner_loop_early_exit
+
+inner_loop_latch:
+  %j.next = add nsw i32 %j, 1
+  %j.cmp = icmp slt i32 %j.next, %m
+  br i1 %j.cmp, label %inner_loop_begin, label %inner_loop_late_exit
+
+inner_loop_early_exit:
+  %j.lcssa = phi i32 [ %i, %inner_loop_begin ]
+  br label %outer_loop_latch
+
+inner_loop_late_exit:
+  br label %outer_loop_latch
+
+outer_loop_latch:
+  %i.phi = phi i32 [ %j.lcssa, %inner_loop_early_exit ], [ %i, %inner_loop_late_exit ]
+  %i.next = add nsw i32 %i.phi, 1
+  %i.cmp = icmp slt i32 %i.next, %n
+  br i1 %i.cmp, label %outer_loop_begin, label %exit
+
+exit:
+  ret void
+}
+
+; Check that trivially unswitching an inner loop resets both the inner and outer
+; loop trip count.
+define void @test2(i32 %n, i32 %m, i32 %cond) {
+; Check that SCEV has no trip count before unswitching.
+; SCEV-LABEL: Determining loop execution counts for: @test2
+; SCEV: Loop %inner_loop_begin: <multiple exits> Unpredictable backedge-taken count.
+; SCEV: Loop %outer_loop_begin: Unpredictable backedge-taken count. 
+;
+; Now check that after unswitching and simplifying instructions we get clean
+; backedge-taken counts.
+; SCEV-LABEL: Determining loop execution counts for: @test2
+; SCEV: Loop %inner_loop_begin: backedge-taken count is (-1 + (1 smax %m))<nsw>
+; FIXME: The following backedge taken count should be known but isn't apparently
+; just because of a switch in the outer loop.
+; SCEV: Loop %outer_loop_begin: Unpredictable backedge-taken count.
+;
+; CHECK-LABEL: define void @test2(
+entry:
+  br label %outer_loop_begin
+; Ensure the outer loop didn't get unswitched.
+; CHECK:       entry:
+; CHECK-NEXT:    br label %outer_loop_begin
+
+outer_loop_begin:
+  %i = phi i32 [ %i.next, %outer_loop_latch ], [ 0, %entry ]
+  ; Block unswitching of the outer loop with a noduplicate call.
+  call void @f() noduplicate
+  br label %inner_loop_begin
+; Ensure the inner loop got unswitched into the outer loop.
+; CHECK:       outer_loop_begin:
+; CHECK-NEXT:    %{{.*}} = phi i32
+; CHECK-NEXT:    call void @f()
+; CHECK-NEXT:    switch i32 %cond,    
+
+inner_loop_begin:
+  %j = phi i32 [ %j.next, %inner_loop_latch ], [ 0, %outer_loop_begin ]
+  switch i32 %cond, label %inner_loop_early_exit [
+    i32 1, label %inner_loop_latch
+    i32 2, label %inner_loop_latch
+  ]
+
+inner_loop_latch:
+  %j.next = add nsw i32 %j, 1
+  %j.cmp = icmp slt i32 %j.next, %m
+  br i1 %j.cmp, label %inner_loop_begin, label %inner_loop_late_exit
+
+inner_loop_early_exit:
+  %j.lcssa = phi i32 [ %i, %inner_loop_begin ]
+  br label %outer_loop_latch
+
+inner_loop_late_exit:
+  br label %outer_loop_latch
+
+outer_loop_latch:
+  %i.phi = phi i32 [ %j.lcssa, %inner_loop_early_exit ], [ %i, %inner_loop_late_exit ]
+  %i.next = add nsw i32 %i.phi, 1
+  %i.cmp = icmp slt i32 %i.next, %n
+  br i1 %i.cmp, label %outer_loop_begin, label %exit
+
+exit:
+  ret void
+}
+
+; Check that non-trivial unswitching of a branch in an inner loop into the outer
+; loop invalidates both inner and outer.
+define void @test3(i32 %n, i32 %m, i1 %cond) {
+; Check that SCEV has no trip count before unswitching.
+; SCEV-LABEL: Determining loop execution counts for: @test3
+; SCEV: Loop %inner_loop_begin: <multiple exits> Unpredictable backedge-taken count.
+; SCEV: Loop %outer_loop_begin: Unpredictable backedge-taken count.
+;
+; Now check that after unswitching and simplifying instructions we get clean
+; backedge-taken counts.
+; SCEV-LABEL: Determining loop execution counts for: @test3
+; SCEV: Loop %inner_loop_begin{{.*}}: backedge-taken count is (-1 + (1 smax %m))<nsw>
+; SCEV: Loop %outer_loop_begin: backedge-taken count is (-1 + (1 smax %n))<nsw>
+;
+; And verify the code matches what we expect.
+; CHECK-LABEL: define void @test3(
+entry:
+  br label %outer_loop_begin
+; Ensure the outer loop didn't get unswitched.
+; CHECK:       entry:
+; CHECK-NEXT:    br label %outer_loop_begin
+
+outer_loop_begin:
+  %i = phi i32 [ %i.next, %outer_loop_latch ], [ 0, %entry ]
+  ; Block unswitching of the outer loop with a noduplicate call.
+  call void @f() noduplicate
+  br label %inner_loop_begin
+; Ensure the inner loop got unswitched into the outer loop.
+; CHECK:       outer_loop_begin:
+; CHECK-NEXT:    %{{.*}} = phi i32
+; CHECK-NEXT:    call void @f()
+; CHECK-NEXT:    br i1 %cond,    
+
+inner_loop_begin:
+  %j = phi i32 [ %j.next, %inner_loop_latch ], [ 0, %outer_loop_begin ]
+  %j.tmp = add nsw i32 %j, 1
+  br i1 %cond, label %inner_loop_latch, label %inner_loop_early_exit
+
+inner_loop_latch:
+  %j.next = add nsw i32 %j, 1
+  %j.cmp = icmp slt i32 %j.next, %m
+  br i1 %j.cmp, label %inner_loop_begin, label %inner_loop_late_exit
+
+inner_loop_early_exit:
+  %j.lcssa = phi i32 [ %j.tmp, %inner_loop_begin ]
+  br label %outer_loop_latch
+
+inner_loop_late_exit:
+  br label %outer_loop_latch
+
+outer_loop_latch:
+  %inc.phi = phi i32 [ %j.lcssa, %inner_loop_early_exit ], [ 1, %inner_loop_late_exit ]
+  %i.next = add nsw i32 %i, %inc.phi
+  %i.cmp = icmp slt i32 %i.next, %n
+  br i1 %i.cmp, label %outer_loop_begin, label %exit
+
+exit:
+  ret void
+}