[SCEV] Support clearing Block/LoopDispositions for a single value.

[fhahn]

Summary

Extend forgetBlockAndLoopDisposition to allow clearing information for a
single value. This can be useful when only a single value is changed,
e.g. because the instruction is moved.

For loop dispositions, we also need to clear the cached values for all
SCEV users, because they may depend on the starting value's loop
disposition.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

8387

if (!V)
  return;
...

8395

I' not sure this is right. Imagine we have:

a = ...
x = a + 1;
y = b + 1;

Loop dispositions for a and y have been cached but not for x. If we stop at x, then y won't be invalidated.

Is this an impossible situation?

8406

not needed?

[fhahn]

Restructure code to use early exits as suggested, thanks!

[fhahn]

llvm/lib/Analysis/ScalarEvolution.cpp

8387

Simplified as suggested with a slight change to clear the full cache on this path, thanks!

8395

Loop dispositions for a and y have been cached but not for x. If we stop at x, then y won't be invalidated.

I might be missing something, but a specific value should only be passed in for invalidation if only this value changed in the IR (e.g. because it as hoisted or sunk). So if a's loop disposition becomes invalid, I think we would only need to invalidate x, because y doesn't use either a or x.

A slightly different scenario could be where y depends on x.

a = ...
x = a + 1;
y = x + 1;

Now if x would not be cached but y would, then we would not invalidate y at the moment.

I *think* this shouldn't happen, because when computing y's loop disposition I think we require x's disposition to already be known (ie. in the cache). From looking at the existing code, it doesn't look like current invalidation could introduce any such gaps.

Does that make sense? We could also go the more conservative route and remove the early continue, but I have a slight preference towards keeping it for now and revisit if any cases show up where the verifier runs into such gaps.

8406

Gone in the re-structured version, thanks!

[fhahn]

ping :)

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

8395

nit: Space after =

8399

nit: Line length

8400

I don't really get why loop and block dispositions get different handling here. Aren't block dispositions computed in essentially the same recursive way?

[fhahn]

Fix formatting, also clear block dispositions for all users recursively.

[fhahn]

llvm/lib/Analysis/ScalarEvolution.cpp

8395

Formatting should also be fixed now, sorry about that.

8400

You are right, my initial thinking only considered dominance between the changed expression and the SCEV users, but not considered that the cache relates SCEV expressions to arbitrary blocks. Updated!

[nikic]

LG

llvm/lib/Analysis/ScalarEvolution.cpp

8418

This line shouldn't be there?

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

92

Declaration can be moved inside the if.

[fhahn]

Address latest comments, planning to land shortly

[fhahn]

llvm/lib/Analysis/ScalarEvolution.cpp

8418

Yep, that was left over from earlier versions, removed, thanks!

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

92

Moved, thanks

llvm/include/llvm/Analysis/ScalarEvolution.h

public:
   /// recompute is simpler.
   void forgetLoopDispositions();
 
   /// Called when the client has changed the disposition of values in
   /// a loop or block.
   ///
   /// We don't have a way to invalidate per-loop/per-block dispositions. Clear
   /// and recompute is simpler.
-  void forgetBlockAndLoopDispositions();
+  void forgetBlockAndLoopDispositions(Value *V = nullptr);
 
   /// Determine the minimum number of zero bits that S is guaranteed to end in
   /// (at every loop iteration).  It is, at the same time, the minimum number
   /// of times S is divisible by 2.  For example, given {4,+,8} it returns 2.
   /// If S is guaranteed to be 0, it returns the bitwidth of S.
   uint32_t GetMinTrailingZeros(const SCEV *S);
 
   /// Determine the unsigned range for a particular SCEV.

llvm/lib/Analysis/ScalarEvolution.cpp

while (!Worklist.empty()) {
 
     PushDefUseChildren(I, Worklist, Visited);
   }
   forgetMemoizedResults(ToForget);
 }
 
 void ScalarEvolution::forgetLoopDispositions() { LoopDispositions.clear(); }
 
-void ScalarEvolution::forgetBlockAndLoopDispositions() {
+void ScalarEvolution::forgetBlockAndLoopDispositions(Value *V) {
+  // Unless a specific value is passed to invalidation, completely clear both
+  // caches.
+  if (!V) {
     BlockDispositions.clear();
     LoopDispositions.clear();
+    return;
+  }
+
+  const SCEV *S = getExistingSCEV(V);
+  if (!S)
+    return;
+
+  // Invalidate the block and loop dispositions cached for S. Dispositions of
+  // S's users may change if S's disposition changes (i.e. a user may change to
+  // loop-invariant, if S changes to loop invariant), so also invalidate
+  // dispositions of S's users recursively.
+  SmallVector<const SCEV *, 8> Worklist = {S};
+  SmallPtrSet<const SCEV *, 8> Seen = {S};
+  while (!Worklist.empty()) {
+    const SCEV *Curr = Worklist.pop_back_val();
+    if (!LoopDispositions.erase(Curr) && !BlockDispositions.erase(S))
+      continue;
+
+    auto Users = SCEVUsers.find(Curr);
+    if (Users != SCEVUsers.end())
+      for (const auto *User : Users->second)
+        if (Seen.insert(User).second)
+          Worklist.push_back(User);
+  }
 }
 
 /// Get the exact loop backedge taken count considering all loop exits. A
 /// computable result can only be returned for loops with all exiting blocks
 /// dominating the latch. howFarToZero assumes that the limit of each loop test
 /// is never skipped. This is a valid assumption as long as the loop exits via
 /// that test. For precise results, it is the caller's responsibility to specify
 /// the relevant loop exiting block using getExact(ExitingBlock, SE).
 const SCEV *
 ScalarEvolution::BackedgeTakenInfo::getExact(const Loop *L, ScalarEvolution *SE,

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

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

llvm/lib/Transforms/Scalar/LoopSink.cpp

for (Instruction &I : llvm::make_early_inc_range(llvm::reverse(*Preheader))) {
     if (isa<PHINode>(&I))
       continue;
     // No need to check for instruction's operands are loop invariant.
     assert(L.hasLoopInvariantOperands(&I) &&
            "Insts in a loop's preheader should have loop invariant operands!");
     if (!canSinkOrHoistInst(I, &AA, &DT, &L, MSSAU, false, LICMFlags))
       continue;
     if (sinkInstruction(L, I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI,
-                        &MSSAU))
+                        &MSSAU)) {
       Changed = true;
+      if (SE)
+        SE->forgetBlockAndLoopDispositions(&I);
+    }
   }
 
-  if (Changed && SE)
-    SE->forgetLoopDispositions();
   return Changed;
 }
 
 PreservedAnalyses LoopSinkPass::run(Function &F, FunctionAnalysisManager &FAM) {
   LoopInfo &LI = FAM.getResult<LoopAnalysis>(F);
   // Nothing to do if there are no loops.
   if (LI.empty())
     return PreservedAnalyses::all();

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, AnyInvariant,
+                Inst, InstInvariant,
                 Preheader ? Preheader->getTerminator() : nullptr, MSSAU)) {
           AllInvariant = false;
           break;
         }
-      }
-      if (AnyInvariant) {
-        Changed = true;
+        if (InstInvariant && SE) {
           // The loop disposition of all SCEV expressions that depend on any
           // hoisted values have also changed.
-        if (SE)
-          SE->forgetLoopDispositions();
+          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.
       if (!FoldBranchToCommonDest(BI, /*DTU=*/nullptr, MSSAU))
         continue;