[LoopPredication] Report changes correctly when attempting loop exit predication

[DaniilSuchkov]

Summary

To make the IR easier to analyze, this pass makes some minor transformations.
After that, even if it doesn't decide to optimize anything, it can't report that
it changed nothing and preserved all the analyses.

[DaniilSuchkov]

Removed the pair of {} that became unnecessary.

[reames]

LGTM.

Your code is correct and fixes a real potential issue, but your test may not be the best one. From what I can tell, the changes being missed were strictly mutations/moves of instructions, not manipulations of the CFG. As a result, the CFG analysis you're testing being invalidated could actually be preserved with a bit of extra work.

[DaniilSuchkov]

In D109855#3004169, @reames wrote:

From what I can tell, the changes being missed were strictly mutations/moves of instructions, not manipulations of the CFG. As a result, the CFG analysis you're testing being invalidated could actually be preserved with a bit of extra work.

I agree with that, that's why left a note about it in the test in case someone breaks the test by making the pass preserve this analysis:

; NOTE: PreservedCFGCheckerAnalysis is an arbitrary analysis that just happens
;       to be calculated before this pass and isn't preserved by it.

To fix the test that person will need to find some other analysis that isn't preserved. Maybe it makes sense to add that to the note.

But, I think, the same can be said about basically any analysis: with some extra effort you can preserve all of them. The best solution would be to introduce some debug print that says either "this pass didn't preserve all analyses" or "this pass preserved everything", but I think at the moment just having a note in the test is somewhat adequate.

[reames]

In D109855#3004245, @DaniilSuchkov wrote:

In D109855#3004169, @reames wrote:

From what I can tell, the changes being missed were strictly mutations/moves of instructions, not manipulations of the CFG. As a result, the CFG analysis you're testing being invalidated could actually be preserved with a bit of extra work.

I agree with that, that's why left a note about it in the test in case someone breaks the test by making the pass preserve this analysis:

; NOTE: PreservedCFGCheckerAnalysis is an arbitrary analysis that just happens
;       to be calculated before this pass and isn't preserved by it.

To fix the test that person will need to find some other analysis that isn't preserved. Maybe it makes sense to add that to the note.

But, I think, the same can be said about basically any analysis: with some extra effort you can preserve all of them. The best solution would be to introduce some debug print that says either "this pass didn't preserve all analyses" or "this pass preserved everything", but I think at the moment just having a note in the test is somewhat adequate.

Makes sense, thanks for the explanation. Sorry for missing the comment in the test.

[mkazantsev]

llvm/lib/Transforms/Scalar/LoopPredication.cpp

1129

Why don't we invalidate SCEV cache after it? I think it's a bug.

[DaniilSuchkov]

llvm/lib/Transforms/Scalar/LoopPredication.cpp

1129

It's good you noticed it! Though I can't say for sure why it's a bug and if it's a bug at all, I don't know SCEV as good as you do. Maybe you happen to have a testcase that would demonstrate that SCEV is in invalid state after this transformation? Anyway, given your knowledge of SCEV and this pass, you seem to be way better equipped for proving that this is a bug and fixing it, so maybe you can handle it?

Just to clarify: the problem of a missed SCEV update doesn't seem directly related to the problem of "this pass incorrectly reports that it preserved everything", so I hope you're not implying that this patch must have fixed this problem too.

llvm/lib/Transforms/Scalar/LoopPredication.cpp

if (isa<SCEVCouldNotCompute>(LatchEC))
     return false; // profitability - want hot exit in analyzeable set
 
   // At this point, we have found an analyzeable latch, and a widenable
   // condition above the loop.  If we have a widenable exit within the loop
   // (for which we can't compute exit counts), drop the ability to further
   // widen so that we gain ability to analyze it's exit count and perform this
   // transform.  TODO: It'd be nice to know for sure the exit became
   // analyzeable after dropping widenability.
-  {
-    bool Invalidate = false;
+  bool ChangedLoop = false;
 
-    for (auto *ExitingBB : ExitingBlocks) {
-      if (LI->getLoopFor(ExitingBB) != L)
-        continue;
 
-      auto *BI = dyn_cast<BranchInst>(ExitingBB->getTerminator());
-      if (!BI)
-        continue;
 
-      Use *Cond, *WC;
-      BasicBlock *IfTrueBB, *IfFalseBB;
-      if (parseWidenableBranch(BI, Cond, WC, IfTrueBB, IfFalseBB) &&
-          L->contains(IfTrueBB)) {
-        WC->set(ConstantInt::getTrue(IfTrueBB->getContext()));
-        Invalidate = true;
-      }
-    }
-    if (Invalidate)
-      SE->forgetLoop(L);
-  }
+      ChangedLoop = true;
+  if (ChangedLoop)
 
   // The use of umin(all analyzeable exits) instead of latch is subtle, but
   // important for profitability.  We may have a loop which hasn't been fully
   // canonicalized just yet.  If the exit we chose to widen is provably never
   // taken, we want the widened form to *also* be provably never taken.  We
   // can't guarantee this as a current unanalyzeable exit may later become
   // analyzeable, but we can at least avoid the obvious cases.
   const SCEV *MinEC = getMinAnalyzeableBackedgeTakenCount(*SE, *DT, L);
   if (isa<SCEVCouldNotCompute>(MinEC) || MinEC->getType()->isPointerTy() ||
       !SE->isLoopInvariant(MinEC, L) ||
       !isSafeToExpandAt(MinEC, WidenableBR, *SE))
-    return false;
+    return ChangedLoop;
 
   // Subtlety: We need to avoid inserting additional uses of the WC.  We know
   // that it can only have one transitive use at the moment, and thus moving
   // that use to just before the branch and inserting code before it and then
   // modifying the operand is legal.
   auto *IP = cast<Instruction>(WidenableBR->getCondition());
+  // Here we unconditionally modify the IR, so after this point we should return
+  // only `true`!
   IP->moveBefore(WidenableBR);
   if (MSSAU)
     if (auto *MUD = MSSAU->getMemorySSA()->getMemoryAccess(IP))
        MSSAU->moveToPlace(MUD, WidenableBR->getParent(),
                           MemorySSA::BeforeTerminator);
   Rewriter.setInsertPoint(IP);
   IRBuilder<> B(IP);
 
-  bool Changed = false;
+  bool InvalidateLoop = false;
   Value *MinECV = nullptr; // lazily generated if needed
   for (BasicBlock *ExitingBB : ExitingBlocks) {
     // If our exiting block exits multiple loops, we can only rewrite the
     // innermost one.  Otherwise, we're changing how many times the innermost
     // loop runs before it exits.
     if (LI->getLoopFor(ExitingBB) != L)
       continue;
 
for (BasicBlock *ExitingBB : ExitingBlocks) {
     // branch without introducing UB.  See NOTE ON POISON/UNDEF above for
     // context.
     NewCond = B.CreateFreeze(NewCond);
 
     widenWidenableBranch(WidenableBR, NewCond);
 
     Value *OldCond = BI->getCondition();
     BI->setCondition(ConstantInt::get(OldCond->getType(), !ExitIfTrue));
-    Changed = true;
+    InvalidateLoop = true;
   }
 
-  if (Changed)
+  if (InvalidateLoop)
     // We just mutated a bunch of loop exits changing there exit counts
     // widely.  We need to force recomputation of the exit counts given these
     // changes.  Note that all of the inserted exits are never taken, and
     // should be removed next time the CFG is modified.
     SE->forgetLoop(L);
-  return Changed;
+
+  // Always return `true` since we have moved the WidenableBR's condition.
+  return true;
 }
 
 bool LoopPredication::runOnLoop(Loop *Loop) {
   L = Loop;
 
   LLVM_DEBUG(dbgs() << "Analyzing ");
   LLVM_DEBUG(L->dump());
 

llvm/test/Transforms/LoopPredication/invalidate-analyses.ll

 ; RUN: opt -S -passes='require<scalar-evolution>,loop-mssa(loop-predication)' -debug-pass-manager < %s 2>&1 | FileCheck %s
 
-; FIXME: We should invalidate PreservedCFGCheckerAnalysis after LoopPredicationPass!
 ; NOTE: PreservedCFGCheckerAnalysis is an arbitrary analysis that just happens
 ;       to be calculated before this pass and isn't preserved by it. If after
 ;       your change this analysis is preserved by the pass, please update this
 ;       test some other analysis that isn't preserved.
 
 ; CHECK: Running analysis: PreservedCFGCheckerAnalysis on drop_a_wc_and_leave_early
 ; CHECK: Running pass: LoopPredicationPass on Loop at depth 1 containing: %loop<header><exiting>,%guarded<exiting>,%guarded2<latch><exiting>
+; CHECK-NEXT: Invalidating analysis: PreservedCFGCheckerAnalysis on drop_a_wc_and_leave_early
 ; CHECK-NEXT: Running analysis: PreservedCFGCheckerAnalysis on drop_a_wc_and_leave
 ; CHECK: Running pass: LoopPredicationPass on Loop at depth 1 containing: %loop<header><exiting>,%guarded<exiting>,%guarded2<latch><exiting>
-; CHECK-NEXT: Running pass: VerifierPass
+; CHECK-NEXT: Invalidating analysis: PreservedCFGCheckerAnalysis on drop_a_wc_and_leave
 
 
 ; This test makes the pass drop its attempts to optimize the exit condition in
 ; `%loop` BB by using unanalyzable `%cond_0` as an exit condition.
 define i64 @drop_a_wc_and_leave_early(i64 %length, i64 %n, i1 %cond_0, i1 %cond_1) {
 ; Make sure the pass has only replaced `%wc2` with `true` in the definition of `%wb_cond`.
 ; CHECK-LABEL: define i64 @drop_a_wc_and_leave_early(i64 %length, i64 %n, i1 %cond_0, i1 %cond_1) {
 ; CHECK-NEXT: entry: