[Loop] Move block and loop dispo invalidation to makeLoopInvariant.

[fhahn]

Summary

makeLoopInvariant may recursively move its operands to make them
invariant, before moving the passed in instruction. Those recursively
moved instructions are currently missed when invalidating block and loop
dispositions.

To address this, move the invalidation code to Loop::makeLoopInvariant.

Fixes #58314.

[nikic]

Generally LGTM, but don't you need to adjust the usage in LoopSimplify as well?

[fhahn]

In D135909#3856806, @nikic wrote:

Generally LGTM, but don't you need to adjust the usage in LoopSimplify as well?

Yes we should probably update all users that preserve SCEV in general. We unfortunately don't have SCEV verification tests for LoopSimplify, but I'll see if I can add one.

[fhahn]

In D135909#3856829, @fhahn wrote:

In D135909#3856806, @nikic wrote:

Generally LGTM, but don't you need to adjust the usage in LoopSimplify as well?

Yes we should probably update all users that preserve SCEV in general. We unfortunately don't have SCEV verification tests for LoopSimplify, but I'll see if I can add one.

I wasn't able to come up with a loop-simplify test case, but I updated the use of makeLoopInvariant in LoopSimplify.

[nikic]

LGTM

llvm/include/llvm/Analysis/LoopInfo.h

public:
   /// set to true. This function can be used as a slightly more aggressive
   /// replacement for isLoopInvariant.
   ///
   /// If InsertPt is specified, it is the point to hoist instructions to.
   /// If null, the terminator of the loop preheader is used.
   ///
   bool makeLoopInvariant(Value *V, bool &Changed,
                          Instruction *InsertPt = nullptr,
-                         MemorySSAUpdater *MSSAU = nullptr) const;
+                         MemorySSAUpdater *MSSAU = nullptr,
+                         ScalarEvolution *SE = nullptr) const;
 
   /// If the given instruction is inside of the loop and it can be hoisted, do
   /// so to make it trivially loop-invariant.
   /// Return true if \c I is already loop-invariant, and false if \c I can't
   /// be made loop-invariant. If \c I is made loop-invariant, \c Changed is
   /// set to true. This function can be used as a slightly more aggressive
   /// replacement for isLoopInvariant.
   ///
   /// If InsertPt is specified, it is the point to hoist instructions to.
   /// If null, the terminator of the loop preheader is used.
   ///
   bool makeLoopInvariant(Instruction *I, bool &Changed,
                          Instruction *InsertPt = nullptr,
-                         MemorySSAUpdater *MSSAU = nullptr) const;
+                         MemorySSAUpdater *MSSAU = nullptr,
+                         ScalarEvolution *SE = nullptr) const;
 
   /// Check to see if the loop has a canonical induction variable: an integer
   /// recurrence that starts at 0 and increments by one each time through the
   /// loop. If so, return the phi node that corresponds to it.
   ///
   /// The IndVarSimplify pass transforms loops to have a canonical induction
   /// variable.
   ///

llvm/lib/Analysis/LoopInfo.cpp

bool Loop::isLoopInvariant(const Value *V) const {
   return true; // All non-instructions are loop invariant
 }
 
 bool Loop::hasLoopInvariantOperands(const Instruction *I) const {
   return all_of(I->operands(), [this](Value *V) { return isLoopInvariant(V); });
 }
 
 bool Loop::makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt,
-                             MemorySSAUpdater *MSSAU) const {
+                             MemorySSAUpdater *MSSAU,
+                             ScalarEvolution *SE) const {
   if (Instruction *I = dyn_cast<Instruction>(V))
-    return makeLoopInvariant(I, Changed, InsertPt, MSSAU);
+    return makeLoopInvariant(I, Changed, InsertPt, MSSAU, SE);
   return true; // All non-instructions are loop-invariant.
 }
 
 bool Loop::makeLoopInvariant(Instruction *I, bool &Changed,
-                             Instruction *InsertPt,
-                             MemorySSAUpdater *MSSAU) const {
+                             Instruction *InsertPt, MemorySSAUpdater *MSSAU,
+                             ScalarEvolution *SE) const {
   // Test if the value is already loop-invariant.
   if (isLoopInvariant(I))
     return true;
   if (!isSafeToSpeculativelyExecute(I))
     return false;
   if (I->mayReadFromMemory())
     return false;
   // EH block instructions are immobile.
   if (I->isEHPad())
     return false;
   // Determine the insertion point, unless one was given.
   if (!InsertPt) {
     BasicBlock *Preheader = getLoopPreheader();
     // Without a preheader, hoisting is not feasible.
     if (!Preheader)
       return false;
     InsertPt = Preheader->getTerminator();
   }
   // Don't hoist instructions with loop-variant operands.
   for (Value *Operand : I->operands())
-    if (!makeLoopInvariant(Operand, Changed, InsertPt, MSSAU))
+    if (!makeLoopInvariant(Operand, Changed, InsertPt, MSSAU, SE))
       return false;
 
   // Hoist.
   I->moveBefore(InsertPt);
   if (MSSAU)
     if (auto *MUD = MSSAU->getMemorySSA()->getMemoryAccess(I))
       MSSAU->moveToPlace(MUD, InsertPt->getParent(),
                          MemorySSA::BeforeTerminator);
 
   // There is possibility of hoisting this instruction above some arbitrary
   // condition. Any metadata defined on it can be control dependent on this
   // condition. Conservatively strip it here so that we don't give any wrong
   // information to the optimizer.
   I->dropUnknownNonDebugMetadata();
 
+  if (SE)
+    SE->forgetBlockAndLoopDispositions(I);
+
   Changed = true;
   return true;
 }
 
 bool Loop::getIncomingAndBackEdge(BasicBlock *&Incoming,
                                   BasicBlock *&Backedge) const {
   BasicBlock *H = getHeader();
 

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

for (PHINode &P : ExitBlock->phis()) {
           all_of(makeArrayRef(ExitingBlocks).slice(1), [&](BasicBlock *BB) {
             return incoming == P.getIncomingValueForBlock(BB);
           });
 
       if (!AllOutgoingValuesSame)
         break;
 
       if (Instruction *I = dyn_cast<Instruction>(incoming)) {
-        bool InstrMoved = false;
-        if (!L->makeLoopInvariant(I, InstrMoved, Preheader->getTerminator())) {
+        if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator(),
+                                  /*MSSAU=*/nullptr, &SE)) {
           AllEntriesInvariant = false;
           break;
         }
-        Changed |= InstrMoved;
-        if (InstrMoved) {
-          // Moving I to a different location may change its block disposition,
-          // so invalidate its SCEV.
-          SE.forgetBlockAndLoopDispositions(I);
-        }
       }
     }
   }
 
   if (!AllEntriesInvariant || !AllOutgoingValuesSame)
     return false;
 
   // Make sure that no instructions in the block have potential side-effects.

llvm/lib/Transforms/Utils/LoopSimplify.cpp

for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
       // Attempt to hoist out all instructions except for the
       // comparison and the branch.
       bool AllInvariant = true;
       bool AnyInvariant = false;
       for (auto I = ExitingBlock->instructionsWithoutDebug().begin(); &*I != BI; ) {
         Instruction *Inst = &*I++;
         if (Inst == CI)
           continue;
-        bool InstInvariant = false;
         if (!L->makeLoopInvariant(
-                Inst, InstInvariant,
-                Preheader ? Preheader->getTerminator() : nullptr, MSSAU)) {
+                Inst, AnyInvariant,
+                Preheader ? Preheader->getTerminator() : nullptr, MSSAU, SE)) {
           AllInvariant = false;
           break;
         }
-        if (InstInvariant && SE) {
-          // The loop disposition of all SCEV expressions that depend on any
-          // hoisted values have also changed.
-          SE->forgetBlockAndLoopDispositions(Inst);
-        }
-        AnyInvariant |= InstInvariant;
       }
       if (AnyInvariant)
         Changed = true;
       if (!AllInvariant) continue;
 
       // The block has now been cleared of all instructions except for
       // a comparison and a conditional branch. SimplifyCFG may be able
       // to fold it now.

llvm/test/Transforms/LoopDeletion/invalidate-scev-after-hoisting.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes='loop(indvars,loop-deletion),verify<scalar-evolution>,print<scalar-evolution>' -S %s 2>&1| FileCheck %s
 
 ; Make sure the SCEV for %invar is invalidated properly when the instruction is
 ; moved by LoopDeletion.
 
 ; CHECK:      Determining loop execution counts for: @test
 ; CHECK-NEXT: Loop %inner: backedge-taken count is (405 + %invar)<nuw><nsw>
 ; CHECK-NEXT: Loop %inner: max backedge-taken count is 405
 ; CHECK-NEXT: Loop %inner: Predicated backedge-taken count is (405 + %invar)<nuw><nsw>
 
-define void @test() {
-; CHECK-LABEL: @test(
+define void @test_pr57837() {
+; CHECK-LABEL: @test_pr57837(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
 ; CHECK:       outer.header:
 ; CHECK-NEXT:    br i1 true, label [[INNER_PH:%.*]], label [[OUTER_LATCH:%.*]]
 ; CHECK:       inner.ph:
 ; CHECK-NEXT:    [[INVAR:%.*]] = ashr i32 0, 3
 ; CHECK-NEXT:    br label [[INNER:%.*]]
 ; CHECK:       inner:

 inner.3:
   %l = load i32, ptr %src, align 4
   br i1 false, label %outer.latch, label %inner.3
 
 outer.latch:
   %outer.iv.next = add nsw i32 %l, %trunc
   br label %outer.header
 }
+
+define void @test_pr58314() {
+; CHECK-LABEL: @test_pr58314(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
+; CHECK:       outer.header:
+; CHECK-NEXT:    [[C:%.*]] = icmp ne i16 0, 0
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[C]], i1 false, i1 true
+; CHECK-NEXT:    br label [[INNER:%.*]]
+; CHECK:       inner:
+; CHECK-NEXT:    br i1 true, label [[INNER]], label [[OUTER_LATCH:%.*]]
+; CHECK:       outer.latch:
+; CHECK-NEXT:    [[SEL_LCSSA:%.*]] = phi i1 [ [[SEL]], [[INNER]] ]
+; CHECK-NEXT:    br i1 [[SEL_LCSSA]], label [[OUTER_HEADER]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %outer.header
+
+outer.header:
+  br label %inner
+
+inner:
+  %c = icmp ne i16 0, 0
+  %sel = select i1 %c, i1 false, i1 true
+  br i1 true, label %inner, label %outer.latch
+
+outer.latch:
+  br i1 %sel, label %outer.header, label %exit
+
+exit:
+  ret void
+}