[SCEV] Skip instrs with non-scevable types in forget[Loop,Value].

[fhahn]

Summary

No SCEVs are formed for instructions with non-scevable types, so no
other SCEV expressions can depend on them. Skip those instructions and
their users when invalidating SCEV expressions.

To catch potential missed cases, the full def-use chains are traversed
after the cleanup to assert no entries in ValueExprMap remain.

Depends on D144847.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

8447

Hm, isn't the verification supposed to omit this check?

[mkazantsev]

This comment has been deleted.

llvm/include/llvm/Analysis/ScalarEvolution.h

2053

typo: Worlist -> Worklist

llvm/lib/Analysis/ScalarEvolution.cpp

8447

I guess we can skip it. We can't have them in ValueExprMap anyways.

[mkazantsev]

Should this be under VerifySCEV ?

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

8447

Maybe even assert on that.

[fhahn]

Adjust condition to skip instructions in verifyAllUsersClearedFromMap.

[fhahn]

In D144848#4154876, @mkazantsev wrote:

Should this be under VerifySCEV ?

The main reason I didn't use VerifySCEV is that this would require a check of the VerifySCEV variable on each verifyAllUsersClearedFromMap, whereas with the current setup it is free for builds without assertions.

llvm/lib/Analysis/ScalarEvolution.cpp

8447

The issue is that non-SCEVable instructions can be operands for SCEVable instructions (e.g. a floating point instruction used by an fcmp). I think in all those cases, the SCEV-able instruction needs to be a SCEVUnknown and the SCEV def-use chain is broken and we should be able to stop invalidation for this instruction.

I updated the condition to more explicitly check for this.

[fhahn]

Also fix typo

[fhahn]

llvm/include/llvm/Analysis/ScalarEvolution.h

2053

Fixed, thanks!

[mkazantsev]

LG, thanks!

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

8447

I think the general change here is right, but I'm not sure this verification is actually verifying anything useful. We aren't going to invalidate the same set of values (by design), so there doesn't really seem anything to verify.

My understanding of this change is that we only want to visit users for which the value may contribute towards the user's SCEV expression. Non-scevable types are one case that can never contribute. The other are instructions that always produce SCEVUnknown, e.g. it doesn't really make sense to follow the use chain across a load regardless of which types it works on (this is probably more common than non-scevable types).

The caveat here is that while they cannot contribute towards SCEVs, it's still theoretically possible to contribute towards cached analysis results, e.g. a SCEVUnknown could be caching no longer valid ValueTracking results.

[fhahn]

llvm/lib/Analysis/ScalarEvolution.cpp

8447

The current verification here is not super useful for the change here itself, the main use case where it would become more useful should be D144849. I can also just remove it from the current patch.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

8447

In that case I'd drop it from this patch.

[fhahn]

Strip off verification. I'll update the description and I am planning on committing this soon.

llvm/include/llvm/Analysis/ScalarEvolution.h

private:
   void forgetMemoizedResultsImpl(const SCEV *S);
 
   /// Iterate over instructions in \p Worklist and their users. Erase entries
   /// from ValueExprMap and collect SCEV expressions in \p ToForget
   void visitAndClearUsers(SmallVectorImpl<Instruction *> &Worklist,
                           SmallPtrSetImpl<Instruction *> &Visited,
                           SmallVectorImpl<const SCEV *> &ToForget);
 
+#ifndef NDEBUG
+  /// Iterate over instructions in \p Worklist and their users. Assert all users
+  /// have been removed from ValueExprMap.
+  void verifyAllUsersClearedFromMap(SmallVectorImpl<Instruction *> &Worklist,
+                                    SmallPtrSetImpl<Instruction *> &Visited);
+#endif
+
   /// Return an existing SCEV for V if there is one, otherwise return nullptr.
   const SCEV *getExistingSCEV(Value *V);
 
   /// Erase Value from ValueExprMap and ExprValueMap.
   void eraseValueFromMap(Value *V);
 
   /// Insert V to S mapping into ValueExprMap and ExprValueMap.
   void insertValueToMap(Value *V, const SCEV *S);

llvm/lib/Analysis/ScalarEvolution.cpp

void ScalarEvolution::forgetAllLoops() {
   FoldCacheUser.clear();
 }
 void ScalarEvolution::visitAndClearUsers(
     SmallVectorImpl<Instruction *> &Worklist,
     SmallPtrSetImpl<Instruction *> &Visited,
     SmallVectorImpl<const SCEV *> &ToForget) {
   while (!Worklist.empty()) {
     Instruction *I = Worklist.pop_back_val();
+    if (!isSCEVable(I->getType()))
+      continue;
 
     ValueExprMapType::iterator It =
         ValueExprMap.find_as(static_cast<Value *>(I));
     if (It != ValueExprMap.end()) {
       eraseValueFromMap(It->first);
       ToForget.push_back(It->second);
       if (PHINode *PN = dyn_cast<PHINode>(I))
         ConstantEvolutionLoopExitValue.erase(PN);
     }
 
     PushDefUseChildren(I, Worklist, Visited);
   }
 }
 
+#ifndef NDEBUG
+void ScalarEvolution::verifyAllUsersClearedFromMap(
+    SmallVectorImpl<Instruction *> &Worklist,
+    SmallPtrSetImpl<Instruction *> &Visited) {
+  while (!Worklist.empty()) {
+    Instruction *I = Worklist.pop_back_val();
+    // If I is an SCEVUnknown and we reached it via a non-SCEVable operand,
+    // invalidation for the instruction stops here as the SCEV def-use chain is
+    // broken by the SCEVUnknown.
+    if (any_of(I->operands(),
+               [this, &Visited](Value *Op) {
+                 auto *OpI = dyn_cast<Instruction>(Op);
+                 return OpI && Visited.contains(OpI) &&
+                        !isSCEVable(Op->getType());
+               }) &&
+        isSCEVable(I->getType()) &&
+        cast_if_present<SCEVUnknown>(getExistingSCEV(I)))
+      continue;
+    assert(ValueExprMap.count(I) == 0 &&
+           "entry for I has not been removed properly");
+    PushDefUseChildren(I, Worklist, Visited);
+  }
+}
+#endif
+
 void ScalarEvolution::forgetLoop(const Loop *L) {
   SmallVector<const Loop *, 16> LoopWorklist(1, L);
   SmallVector<Instruction *, 32> Worklist;
   SmallPtrSet<Instruction *, 16> Visited;
   SmallVector<const SCEV *, 16> ToForget;
 
+#ifndef NDEBUG
+  SmallVector<Instruction *, 16> VerificationWorklist;
+  SmallPtrSet<Instruction *, 8> VerificationVisited;
+#endif
+
   // Iterate over all the loops and sub-loops to drop SCEV information.
   while (!LoopWorklist.empty()) {
     auto *CurrL = LoopWorklist.pop_back_val();
 
     // Drop any stored trip count value.
     forgetBackedgeTakenCounts(CurrL, /* Predicated */ false);
     forgetBackedgeTakenCounts(CurrL, /* Predicated */ true);
 
while (!LoopWorklist.empty()) {
     auto LoopUsersItr = LoopUsers.find(CurrL);
     if (LoopUsersItr != LoopUsers.end()) {
       ToForget.insert(ToForget.end(), LoopUsersItr->second.begin(),
                 LoopUsersItr->second.end());
     }
 
     // Drop information about expressions based on loop-header PHIs.
     PushLoopPHIs(CurrL, Worklist, Visited);
+#ifndef NDEBUG
+    PushLoopPHIs(CurrL, VerificationWorklist, VerificationVisited);
+#endif
     visitAndClearUsers(Worklist, Visited, ToForget);
 
     LoopPropertiesCache.erase(CurrL);
     // Forget all contained loops too, to avoid dangling entries in the
     // ValuesAtScopes map.
     LoopWorklist.append(CurrL->begin(), CurrL->end());
   }
   forgetMemoizedResults(ToForget);
+
+#ifndef NDEBUG
+  verifyAllUsersClearedFromMap(VerificationWorklist, VerificationVisited);
+#endif
 }
 
 void ScalarEvolution::forgetTopmostLoop(const Loop *L) {
   forgetLoop(L->getOutermostLoop());
 }
 
 void ScalarEvolution::forgetValue(Value *V) {
   Instruction *I = dyn_cast<Instruction>(V);
   if (!I) return;
 
   // Drop information about expressions based on loop-header PHIs.
   SmallVector<Instruction *, 16> Worklist;
   SmallPtrSet<Instruction *, 8> Visited;
   SmallVector<const SCEV *, 8> ToForget;
   Worklist.push_back(I);
   Visited.insert(I);
   visitAndClearUsers(Worklist, Visited, ToForget);
 
   forgetMemoizedResults(ToForget);
+
+#ifndef NDEBUG
+  SmallVector<Instruction *, 16> VerificationWorklist;
+  SmallPtrSet<Instruction *, 8> VerificationVisited;
+  Worklist.push_back(cast<Instruction>(V));
+  Visited.insert(cast<Instruction>(V));
+  verifyAllUsersClearedFromMap(VerificationWorklist, VerificationVisited);
+#endif
 }
 
 void ScalarEvolution::forgetLoopDispositions() { LoopDispositions.clear(); }
 
 void ScalarEvolution::forgetBlockAndLoopDispositions(Value *V) {
   // Unless a specific value is passed to invalidation, completely clear both
   // caches.
   if (!V) {