[SimpleLoopUnswitch] Invalidate the topmost loop with ExitBB as exiting.

[fhahn]

Summary

SCEV caches the exiting blocks when computing exit counts. In
SimpleLoopUnswitch, we split the exit block of the loop to unswitch.

Currently we only invalidate the loop containing that exit block, but if
that block is the exiting block for a parent loop, we have stale cache
entries. We have to invalidate the top-most loop that contains the exit
block as exiting block. We might also be able to skip invalidating the
loop containing the exit block, if the exit block is not an exiting
block of that loop.

There are also 2 more places in SimpleLoopUnswitch, that use a similar
problematic approach to get the loop to invalidate. If the patch makes
sense, I will also update those places to a similar approach (they deal
with multiple exit blocks, so we cannot directly re-use
getTopMostExitingLoop).

[merge_guards_bot]

Build result: fail - 60324 tests passed, 15 failed and 732 were skipped.

failed: LLVM.Analysis/MemorySSA/pr40037.ll
failed: LLVM.Transforms/SimpleLoopUnswitch/2006-06-13-SingleEntryPHI.ll
failed: LLVM.Transforms/SimpleLoopUnswitch/2007-05-09-Unreachable.ll
failed: LLVM.Transforms/SimpleLoopUnswitch/2012-04-30-LoopUnswitch-LPad-Crash.ll
failed: LLVM.Transforms/SimpleLoopUnswitch/LIV-loop-condtion.ll
failed: LLVM.Transforms/SimpleLoopUnswitch/cleanuppad.ll
failed: LLVM.Transforms/SimpleLoopUnswitch/copy-metadata.ll
failed: LLVM.Transforms/SimpleLoopUnswitch/formDedicatedAfterTrivial1.ll
failed: LLVM.Transforms/SimpleLoopUnswitch/guards.ll
failed: LLVM.Transforms/SimpleLoopUnswitch/infinite-loop.ll
failed: LLVM.Transforms/SimpleLoopUnswitch/msan.ll
failed: LLVM.Transforms/SimpleLoopUnswitch/nontrivial-unswitch.ll
failed: LLVM.Transforms/SimpleLoopUnswitch/pr37888.ll
failed: LLVM.Transforms/SimpleLoopUnswitch/trivial-unswitch-iteration.ll
failed: LLVM.Transforms/SimpleLoopUnswitch/trivial-unswitch.ll

Log files: console-log.txt, CMakeCache.txt

[fhahn]

Account for Current being nullptr initially.

[merge_guards_bot]

Build result: pass - 60354 tests passed, 0 failed and 732 were skipped.

Log files: console-log.txt, CMakeCache.txt

[asbirlea]

Thank you for this fix. LGTM.

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

for (Loop *OldContainingL = OldParentL; OldContainingL != NewParentL;
     // unswitching it is possible to get new non-dedicated exits out of parent
     // loop so let's conservatively form dedicated exit blocks and figure out
     // if we can optimize later.
     formDedicatedExitBlocks(OldContainingL, &DT, &LI, MSSAU,
                             /*PreserveLCSSA*/ true);
   }
 }
 
+// Return the top-most loop containing ExitBB and having ExitBB as exiting block
+// or the loop containing ExitBB, if there is no parent loop containing ExitBB
+// as exiting block.
+static Loop *getTopMostExitingLoop(BasicBlock *ExitBB, LoopInfo &LI) {
+  Loop *TopMost = LI.getLoopFor(ExitBB);
+  Loop *Current = TopMost;
+  while (Current) {
+    if (Current->isLoopExiting(ExitBB))
+      TopMost = Current;
+    Current = Current->getParentLoop();
+  }
+  return TopMost;
+}
+
 /// Unswitch a trivial branch if the condition is loop invariant.
 ///
 /// This routine should only be called when loop code leading to the branch has
 /// been validated as trivial (no side effects). This routine checks if the
 /// condition is invariant and one of the successors is a loop exit. This
 /// allows us to unswitch without duplicating the loop, making it trivial.
 ///
 /// If this routine fails to unswitch the branch it returns false.
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.
+  // loop, the loop containing the exit block and the topmost parent loop
+  // exiting via LoopExitBB.
   if (SE) {
-    if (Loop *ExitL = LI.getLoopFor(LoopExitBB))
+    if (Loop *ExitL = getTopMostExitingLoop(LoopExitBB, LI))
       SE->forgetLoop(ExitL);
     else
       // Forget the entire nest as this exits the entire nest.
       SE->forgetTopmostLoop(&L);
   }
 
   if (MSSAU && VerifyMemorySSA)
     MSSAU->getMemorySSA()->verifyMemorySSA();

llvm/test/Transforms/SimpleLoopUnswitch/preserve-scev-exiting-multiple-loops.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+
+; We run -indvars before -simple-loop-unswitch to compute SCEV exit counts before
+; running -simple-loop-unswitch.
+; RUN:  opt -indvars -simple-loop-unswitch -S %s -verify-scev | FileCheck %s
+
+; Test for PR43972.
+
+; We have a 3 nested loops (l1 <- l2 <- l3). %for.cond.5 is the exit block of
+; l3 and the loop for it is l2. But it is also the exiting block of l1. That
+; means we have to invalidate l1 to preserve SCEV.
+
+define void @f() {
+; CHECK-LABEL: @f(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[LNOT:%.*]] = xor i1 undef, true
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond.loopexit:
+; CHECK-NEXT:    br label [[FOR_COND]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.cond1:
+; CHECK-NEXT:    br i1 true, label [[FOR_BODY]], label [[FOR_COND_LOOPEXIT:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    br i1 [[LNOT]], label [[FOR_BODY_SPLIT:%.*]], label [[FOR_COND5_SPLIT:%.*]]
+; CHECK:       for.body.split:
+; CHECK-NEXT:    br label [[LAND_RHS:%.*]]
+; CHECK:       for.cond2:
+; CHECK-NEXT:    br i1 true, label [[LAND_RHS]], label [[FOR_COND5:%.*]]
+; CHECK:       land.rhs:
+; CHECK-NEXT:    br label [[FOR_COND2:%.*]]
+; CHECK:       for.cond5:
+; CHECK-NEXT:    br label [[FOR_COND5_SPLIT]]
+; CHECK:       for.cond5.split:
+; CHECK-NEXT:    br i1 true, label [[FOR_BODY7:%.*]], label [[FOR_COND1:%.*]]
+; CHECK:       for.body7:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %lnot = xor i1 undef, true
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.cond1, %entry
+  br label %for.body
+
+for.cond1:                                        ; preds = %for.cond5
+  br i1 true, label %for.body, label %for.cond
+
+for.body:                                         ; preds = %for.cond1, %for.cond
+  br label %land.rhs
+
+for.cond2:                                        ; preds = %land.rhs
+  br i1 true, label %land.rhs, label %for.cond5
+
+land.rhs:                                         ; preds = %for.cond2, %for.body
+  br i1 %lnot, label %for.cond2, label %for.cond5
+
+for.cond5:                                        ; preds = %land.rhs, %for.cond2
+  br i1 true, label %for.body7, label %for.cond1
+
+for.body7:                                        ; preds = %for.cond5
+  ret void
+}