[SCEV] Remove invalid SCEVUnknowns from value map

[nikic]

Summary

When invalidating a SCEVUnknown via CallbackVH, also drop all references to the SCEVUnknown or SCEV expressions using it from the ValueToExpr map. This means we no longer need to check for validity in getExistingSCEV().

[nikic]

I have a suspicion that ValueExprMap and ExprValueMap may not always be sync, need to double check that first.

[nikic]

This has been mostly replaced by D113349. The remaining change is to drop the checkValidity() call, but that's NFC after that patch.

llvm/include/llvm/Analysis/ScalarEvolution.h

private:
   /// prove them individually.
   bool isKnownPredicateViaSplitting(ICmpInst::Predicate Pred, const SCEV *LHS,
                                     const SCEV *RHS);
 
   /// Try to match the Expr as "(L + R)<Flags>".
   bool splitBinaryAdd(const SCEV *Expr, const SCEV *&L, const SCEV *&R,
                       SCEV::NoWrapFlags &Flags);
 
-  /// Drop memoized information for all \p SCEVs.
-  void forgetMemoizedResults(ArrayRef<const SCEV *> SCEVs);
+  /// Drop memoized information for all \p SCEVs. If \ForgetValues is enabled,
+  /// also drop the corresponding Value <-> SCEV mappings.
+  void forgetMemoizedResults(ArrayRef<const SCEV *> SCEVs,
+                             bool ForgetValues = false);
 
   /// Helper for forgetMemoizedResults.
   void forgetMemoizedResultsImpl(const SCEV *S);
 
   /// Return an existing SCEV for V if there is one, otherwise return nullptr.
   const SCEV *getExistingSCEV(Value *V);
 
-  /// Return false iff given SCEV contains a SCEVUnknown with NULL value-
-  /// pointer.
-  bool checkValidity(const SCEV *S) const;
-
   /// Return true if `ExtendOpTy`({`Start`,+,`Step`}) can be proved to be
   /// equal to {`ExtendOpTy`(`Start`),+,`ExtendOpTy`(`Step`)}.  This is
   /// equivalent to proving no signed (resp. unsigned) wrap in
   /// {`Start`,+,`Step`} if `ExtendOpTy` is `SCEVSignExtendExpr`
   /// (resp. `SCEVZeroExtendExpr`).
   template <typename ExtendOpTy>
   bool proveNoWrapByVaryingStart(const SCEV *Start, const SCEV *Step,
                                  const Loop *L);

llvm/lib/Analysis/ScalarEvolution.cpp

SCEVSignExtendExpr::SCEVSignExtendExpr(const FoldingSetNodeIDRef ID,
                                        const SCEV *op, Type *ty)
     : SCEVIntegralCastExpr(ID, scSignExtend, op, ty) {
   assert(getOperand()->getType()->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
          "Cannot sign extend non-integer value!");
 }
 
 void SCEVUnknown::deleted() {
   // Clear this SCEVUnknown from various maps.
-  SE->forgetMemoizedResults(this);
+  SE->forgetMemoizedResults(this, /* ForgetValues */ true);
 
   // Remove this SCEVUnknown from the uniquing map.
   SE->UniqueSCEVs.RemoveNode(this);
 
   // Release the value.
   setValPtr(nullptr);
 }
 

 Type *ScalarEvolution::getWiderType(Type *T1, Type *T2) const {
   return  getTypeSizeInBits(T1) >= getTypeSizeInBits(T2) ? T1 : T2;
 }
 
 const SCEV *ScalarEvolution::getCouldNotCompute() {
   return CouldNotCompute.get();
 }
 
-bool ScalarEvolution::checkValidity(const SCEV *S) const {
-  bool ContainsNulls = SCEVExprContains(S, [](const SCEV *S) {
-    auto *SU = dyn_cast<SCEVUnknown>(S);
-    return SU && SU->getValue() == nullptr;
-  });
-
-  return !ContainsNulls;
-}
-
 bool ScalarEvolution::containsAddRecurrence(const SCEV *S) {
   HasRecMapType::iterator I = HasRecMap.find(S);
   if (I != HasRecMap.end())
     return I->second;
 
   bool FoundAddRec =
       SCEVExprContains(S, [](const SCEV *S) { return isa<SCEVAddRecExpr>(S); });
   HasRecMap.insert({S, FoundAddRec});
const SCEV *ScalarEvolution::getSCEV(Value *V) {
   }
   return S;
 }
 
 const SCEV *ScalarEvolution::getExistingSCEV(Value *V) {
   assert(isSCEVable(V->getType()) && "Value is not SCEVable!");
 
   ValueExprMapType::iterator I = ValueExprMap.find_as(V);
-  if (I != ValueExprMap.end()) {
-    const SCEV *S = I->second;
-    if (checkValidity(S))
-      return S;
-    eraseValueFromMap(V);
-    forgetMemoizedResults(S);
-  }
-  return nullptr;
+  return I != ValueExprMap.end() ? I->second : nullptr;
 }
 
 /// Return a SCEV corresponding to -V = -1*V
 const SCEV *ScalarEvolution::getNegativeSCEV(const SCEV *V,
                                              SCEV::NoWrapFlags Flags) {
   if (const SCEVConstant *VC = dyn_cast<SCEVConstant>(V))
     return getConstant(
                cast<ConstantInt>(ConstantExpr::getNeg(VC->getValue())));

 bool ScalarEvolution::properlyDominates(const SCEV *S, const BasicBlock *BB) {
   return getBlockDisposition(S, BB) == ProperlyDominatesBlock;
 }
 
 bool ScalarEvolution::hasOperand(const SCEV *S, const SCEV *Op) const {
   return SCEVExprContains(S, [&](const SCEV *Expr) { return Expr == Op; });
 }
 
-void ScalarEvolution::forgetMemoizedResults(ArrayRef<const SCEV *> SCEVs) {
+void ScalarEvolution::forgetMemoizedResults(ArrayRef<const SCEV *> SCEVs,
+                                            bool ForgetValues) {
   SmallPtrSet<const SCEV *, 8> ToForget(SCEVs.begin(), SCEVs.end());
   SmallVector<const SCEV *, 8> Worklist(ToForget.begin(), ToForget.end());
 
   while (!Worklist.empty()) {
     const SCEV *Curr = Worklist.pop_back_val();
     auto Users = SCEVUsers.find(Curr);
     if (Users != SCEVUsers.end())
       for (auto *User : Users->second)
auto RemoveSCEVFromBackedgeMap = [&ToForget](
             Map.erase(I++);
           else
             ++I;
         }
   };
 
   RemoveSCEVFromBackedgeMap(BackedgeTakenCounts);
   RemoveSCEVFromBackedgeMap(PredicatedBackedgeTakenCounts);
+
+  if (ForgetValues) {
+    for (const SCEV *S : ToForget) {
+      auto ExprIt = ExprValueMap.find(S);
+      if (ExprIt == ExprValueMap.end())
+        continue;
+
+      for (auto &ValueAndOffset : ExprIt->second) {
+        auto ValueIt = ValueExprMap.find_as(ValueAndOffset.first);
+        if (ValueIt != ValueExprMap.end())
+          ValueExprMap.erase(ValueIt);
+      }
+      ExprValueMap.erase(ExprIt);
+    }
+  }
 }
 
 void ScalarEvolution::forgetMemoizedResultsImpl(const SCEV *S) {
   ValuesAtScopes.erase(S);
   LoopDispositions.erase(S);
   BlockDispositions.erase(S);
   UnsignedRanges.erase(S);
   SignedRanges.erase(S);