[SCEV][NFC] Apply mass forgetMemoizedResults queries where possible

[mkazantsev]

Summary

When forgetting multiple SCEVs, rather than doing this one by one, we can
instead use mass updates. We plan to make them more efficient than they
are now, potentially improving compile time.

[nikic]

This is an improvement in some cases, but less than I'd hoped: https://llvm-compile-time-tracker.com/compare.php?from=5e2c6abab42241c06680941be06fddcb9279e63d&to=18b24fb231b0dcbaf0dc304826974ac1aad77a01&stat=instructions

llvm/lib/Analysis/ScalarEvolution.cpp

7582

We should be collecting these into a vector as well.

12821

You can just pass S directly, no need to create SmallVector for single-element ArrayRef.

[mkazantsev]

I think we can do more of this kind, e.g. in forgetLoops. Will look into it more.

llvm/lib/Analysis/ScalarEvolution.cpp

7582

Good point!

[mkazantsev]

Found some more places where it can be done. @nikic could you please check the CT now?

[nikic]

Updated version looks better: https://llvm-compile-time-tracker.com/compare.php?from=5e2c6abab42241c06680941be06fddcb9279e63d&to=82329ed73bb4100f3641703982cb661f77b95344&stat=instructions (don't mind SPASS, that's noise)

And here's both patches together: http://llvm-compile-time-tracker.com/compare.php?from=943b3048484b7e3cf04f4d51c23c82fcece2185d&to=82329ed73bb4100f3641703982cb661f77b95344&stat=instructions

llvm/lib/Analysis/ScalarEvolution.cpp

7497

Just wondering, does the problem described in this comment affect the new invalidation mechanism?

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

7497

If I'm reading this correctly, the new mechanism will drop trip count cache. The notion that we can sometimes forget something not for correctness purposes, but for the sole purpose of getting better results, is interesting. If it doesn't lead to any dangling pointers or directly wrong cached results, maybe we should consider non-recursive invalidation here.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

7497

Giving it some more thought, I think this one might be a source of bugs. Imagine that exit count depends on a hypothetical SCEV (not corresponding to any existing instruction directly) which, in turn, uses value being forgotten. When it is destroyed, how do we ensure that we'll not end up with exit count referencing (indirectly) a dangling pointer?

[reames]

Max, a suggestion review structure wise. If you flip the order of this patch and the one it's currently built on (i.e. by adding a forgetMemoizedResults arrayref wrapper), this can be easily landed as NFC. It won't really have any benefit compile time wise on it's own, but the change itself is not unreasonable. Inverting the review stack this way makes it easier to track the overall state of what's in review.

In fact, if you want to do that, you can consider this a conditional LGTM.

[reames]

Two minor opportunities to exploit set invalidation for efficiency. I'll leave it to you whether these are worth separate review or not.

llvm/lib/Analysis/ScalarEvolution.cpp

12839

There's an opportunity to exploit the invalidation of sets at a time here by replacing multiple walks, with one walk and a set membership check.

12849

Same here. Though, I don't believe we have an set optimized contains_any already, so this might not be worth bothering with.

[mkazantsev]

Ok, I also think that this one can go first.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

12839

Good point, I'll try to make this in a follow-up.

[reames]

LGTM

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 computed for S.
-  void forgetMemoizedResults(const SCEV *S);
+  /// Drop memoized information for all \p SCEVs.
+  void forgetMemoizedResults(ArrayRef<const SCEV *> SCEVs);
 
   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.

llvm/lib/Analysis/ScalarEvolution.cpp

 }
 
 void ScalarEvolution::forgetSymbolicName(Instruction *PN, const SCEV *SymName) {
   SmallVector<Instruction *, 16> Worklist;
   PushDefUseChildren(PN, Worklist);
 
   SmallPtrSet<Instruction *, 8> Visited;
   Visited.insert(PN);
+  SmallVector<const SCEV *, 8> ToForget;
   while (!Worklist.empty()) {
     Instruction *I = Worklist.pop_back_val();
     if (!Visited.insert(I).second)
       continue;
 
     auto It = ValueExprMap.find_as(static_cast<Value *>(I));
     if (It != ValueExprMap.end()) {
       const SCEV *Old = It->second;
if (It != ValueExprMap.end()) {
       // additional loop trip count information isn't going to change anything.
       // In the second case, createNodeForPHI will perform the necessary
       // updates on its own when it gets to that point. In the third, we do
       // want to forget the SCEVUnknown.
       if (!isa<PHINode>(I) ||
           !isa<SCEVUnknown>(Old) ||
           (I != PN && Old == SymName)) {
         eraseValueFromMap(It->first);
-        forgetMemoizedResults(Old);
+        ToForget.push_back(Old);
       }
     }
 
     PushDefUseChildren(I, Worklist);
   }
+  forgetMemoizedResults(ToForget);
 }
 
 namespace {
 
 /// Takes SCEV S and Loop L. For each AddRec sub-expression, use its start
 /// expression in case its Loop is L. If it is not L then
 /// if IgnoreOtherLoops is true then use AddRec itself
 /// otherwise rewrite cannot be done.
#endif // LLVM_ENABLE_STATS || !defined(NDEBUG)
   // conservative estimates made without the benefit of trip count
   // information. This is similar to the code in forgetLoop, except that
   // it handles SCEVUnknown PHI nodes specially.
   if (Result.hasAnyInfo()) {
     SmallVector<Instruction *, 16> Worklist;
     PushLoopPHIs(L, Worklist);
 
     SmallPtrSet<Instruction *, 8> Discovered;
+    SmallVector<const SCEV *, 8> ToForget;
     while (!Worklist.empty()) {
       Instruction *I = Worklist.pop_back_val();
 
       ValueExprMapType::iterator It =
         ValueExprMap.find_as(static_cast<Value *>(I));
       if (It != ValueExprMap.end()) {
         const SCEV *Old = It->second;
 
         // SCEVUnknown for a PHI either means that it has an unrecognized
         // structure, or it's a PHI that's in the progress of being computed
         // by createNodeForPHI.  In the former case, additional loop trip
         // count information isn't going to change anything. In the later
         // case, createNodeForPHI will perform the necessary updates on its
         // own when it gets to that point.
         if (!isa<PHINode>(I) || !isa<SCEVUnknown>(Old)) {
           eraseValueFromMap(It->first);
-          forgetMemoizedResults(Old);
+          ToForget.push_back(Old);
         }
         if (PHINode *PN = dyn_cast<PHINode>(I))
           ConstantEvolutionLoopExitValue.erase(PN);
       }
 
       // Since we don't need to invalidate anything for correctness and we're
       // only invalidating to make SCEV's results more precise, we get to stop
       // early to avoid invalidating too much.  This is especially important in
       // cases like:
       //
       //   %v = f(pn0, pn1) // pn0 and pn1 used through some other phi node
       // loop0:
       //   %pn0 = phi
       //   ...
       // loop1:
       //   %pn1 = phi
       //   ...
       //
       // where both loop0 and loop1's backedge taken count uses the SCEV
       // expression for %v.  If we don't have the early stop below then in cases
       // like the above, getBackedgeTakenInfo(loop1) will clear out the trip
       // count for loop0 and getBackedgeTakenInfo(loop0) will clear out the trip
       // count for loop1, effectively nullifying SCEV's trip count cache.
       for (auto *U : I->users())
         if (auto *I = dyn_cast<Instruction>(U)) {
           auto *LoopForUser = LI.getLoopFor(I->getParent());
           if (LoopForUser && L->contains(LoopForUser) &&
               Discovered.insert(I).second)
             Worklist.push_back(I);
         }
     }
+    forgetMemoizedResults(ToForget);
   }
 
   // Re-lookup the insert position, since the call to
   // computeBackedgeTakenCount above could result in a
   // recusive call to getBackedgeTakenInfo (on a different
   // loop), which would invalidate the iterator computed
   // earlier.
   return BackedgeTakenCounts.find(L)->second = std::move(Result);
void ScalarEvolution::forgetAllLoops() {
   MinTrailingZerosCache.clear();
   PredicatedSCEVRewrites.clear();
 }
 
 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;
 
   // 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.
     BackedgeTakenCounts.erase(CurrL);
     PredicatedBackedgeTakenCounts.erase(CurrL);
 
     // Drop information about predicated SCEV rewrites for this loop.
     for (auto I = PredicatedSCEVRewrites.begin();
          I != PredicatedSCEVRewrites.end();) {
       std::pair<const SCEV *, const Loop *> Entry = I->first;
       if (Entry.second == CurrL)
         PredicatedSCEVRewrites.erase(I++);
       else
         ++I;
     }
 
     auto LoopUsersItr = LoopUsers.find(CurrL);
     if (LoopUsersItr != LoopUsers.end()) {
-      for (auto *S : LoopUsersItr->second)
-        forgetMemoizedResults(S);
+      ToForget.insert(ToForget.end(), LoopUsersItr->second.begin(),
+                      LoopUsersItr->second.end());
       LoopUsers.erase(LoopUsersItr);
     }
 
     // Drop information about expressions based on loop-header PHIs.
     PushLoopPHIs(CurrL, Worklist);
 
     while (!Worklist.empty()) {
       Instruction *I = Worklist.pop_back_val();
       if (!Visited.insert(I).second)
         continue;
 
       ValueExprMapType::iterator It =
           ValueExprMap.find_as(static_cast<Value *>(I));
       if (It != ValueExprMap.end()) {
         eraseValueFromMap(It->first);
-        forgetMemoizedResults(It->second);
+        ToForget.push_back(It->second);
         if (PHINode *PN = dyn_cast<PHINode>(I))
           ConstantEvolutionLoopExitValue.erase(PN);
       }
 
       PushDefUseChildren(I, Worklist);
     }
 
     LoopPropertiesCache.erase(CurrL);
     // Forget all contained loops too, to avoid dangling entries in the
     // ValuesAtScopes map.
     LoopWorklist.append(CurrL->begin(), CurrL->end());
   }
+
+  forgetMemoizedResults(ToForget);
 }
 
 void ScalarEvolution::forgetTopmostLoop(const Loop *L) {
   while (Loop *Parent = L->getParentLoop())
     L = Parent;
   forgetLoop(L);
 }
 
 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;
   Worklist.push_back(I);
 
   SmallPtrSet<Instruction *, 8> Visited;
+  SmallVector<const SCEV *, 8> ToForget;
   while (!Worklist.empty()) {
     I = Worklist.pop_back_val();
     if (!Visited.insert(I).second)
       continue;
 
     ValueExprMapType::iterator It =
       ValueExprMap.find_as(static_cast<Value *>(I));
     if (It != ValueExprMap.end()) {
       eraseValueFromMap(It->first);
-      forgetMemoizedResults(It->second);
+      ToForget.push_back(It->second);
       if (PHINode *PN = dyn_cast<PHINode>(I))
         ConstantEvolutionLoopExitValue.erase(PN);
     }
 
     PushDefUseChildren(I, Worklist);
   }
+  forgetMemoizedResults(ToForget);
 }
 
 void ScalarEvolution::forgetLoopDispositions(const Loop *L) {
   LoopDispositions.clear();
 }
 
 /// Get the exact loop backedge taken count considering all loop exits. A
 /// computable result can only be returned for loops with all exiting blocks

 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(const SCEV *S) {
+void ScalarEvolution::forgetMemoizedResults(ArrayRef<const SCEV *> SCEVs) {
   SmallPtrSet<const SCEV *, 16> Visited;
   SmallVector<const SCEV *, 16> Worklist;
-  Visited.insert(S);
+  for (auto *S : SCEVs)
+    if (Visited.insert(S).second)
       Worklist.push_back(S);
+
   while (!Worklist.empty()) {
     const SCEV *Curr = Worklist.pop_back_val();
     auto Users = SCEVUsers.find(Curr);
     if (Users != SCEVUsers.end())
       for (auto *User : Users->second)
         if (Visited.insert(User).second)
           Worklist.push_back(User);
   }
void ScalarEvolution::forgetMemoizedResultsImpl(const SCEV *S) {
   SignedRanges.erase(S);
   ExprValueMap.erase(S);
   HasRecMap.erase(S);
   MinTrailingZerosCache.erase(S);
 
   for (auto I = PredicatedSCEVRewrites.begin();
        I != PredicatedSCEVRewrites.end();) {
     std::pair<const SCEV *, const Loop *> Entry = I->first;
     if (Entry.first == S)
       PredicatedSCEVRewrites.erase(I++);
     else
       ++I;
   }
 
   auto RemoveSCEVFromBackedgeMap =
       [S](DenseMap<const Loop *, BackedgeTakenInfo> &Map) {
         for (auto I = Map.begin(), E = Map.end(); I != E;) {
           BackedgeTakenInfo &BEInfo = I->second;
           if (BEInfo.hasOperand(S))
             Map.erase(I++);
           else
             ++I;
         }
       };
 
   RemoveSCEVFromBackedgeMap(BackedgeTakenCounts);
   RemoveSCEVFromBackedgeMap(PredicatedBackedgeTakenCounts);