[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

7576

We should be collecting these into a vector as well.

12813

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

7576

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

7494

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

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

7494

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

7494

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:
 
   /// 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.
   bool checkValidity(const SCEV *S) const;

llvm/lib/Analysis/ScalarEvolution.cpp

while (!Worklist.empty()) {
       // 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);
         }
     }
for (auto I = PredicatedSCEVRewrites.begin();
       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);
+      forgetMemoizedResults(LoopUsersItr->second);
       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);
         if (PHINode *PN = dyn_cast<PHINode>(I))
           ConstantEvolutionLoopExitValue.erase(PN);
       }
 
       PushDefUseChildren(I, Worklist);
     }
 
     LoopPropertiesCache.erase(CurrL);
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) {
+  SmallVector<const SCEV *> ToForget;
+  ToForget.push_back(S);
+  forgetMemoizedResults(ToForget);
+}
+
+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);