[SCEV] Only add uses to worklist for instrs in map, loop or phis.

[fhahn]

Summary

This patch limits the def-use traversal in forgetValue to defs that have
a value in ValueExprMap, are in the same loop as the starting
instructions or are phis. This should ensure that we invalidate SCEVs as
needed, but avoid traversing instructions for which no SCEVs exist or
which have already been invalidated.

In particular, it should still invalidate

• SCEVs for instructions if any of its operands have a SCEV which is invalidate,
• any add-recs that depend on a given value in the current loop,
• and LCSSA loop exit phis.

There's assertions to try to catch any cases where invalidation is
missed now, which should help to surface any edge-cases, if any.

This can cut down the time spent invalidating SCEVs. For some internal
workloads with very large functions, this reduces the time spent in
passes using SCEV by 2-5x.

For CTmark, there are also some notable improvements, mostly in ClamAV
(-0.91% with -O3):

• NewPM-O3: -0.12%
• NewPM-ReleaseThinLTO: -0.10%
• NewPM-ReleaseLTO-g: -0.07%

https://llvm-compile-time-tracker.com/compare.php?from=ccea4e9b0494787e56809f3a8d261f49c829b149&to=d41584481b8f4f0501ed8197590048bd70fa1e2c&stat=instructions:u

Depends on D144848.

[nikic]

I like the idea here, and have tried changes along these lines in the past, but always ran into issues. Some questions:

• If we have %y = add %x, 1; %z = add %y, 1 and create SCEV for %z, we will create one for %x, but not for %y. Doesn't this break the invalidation chain?
• Can we rely on LCSSA in SCEV? I don't think it's guaranteed.
• I don't really understand the LCSSA phi special case. The LCSSA phis themselves should already get added without the isa<PHINode> check by dint of being users of a loop value. Why do we need to enforce addition of the LCSSA users, but not its transitive users?

[mkazantsev]

LCSSA is not guaranteed, SCEV can be used in non-loop passes. I think Florian's intent here is to invalidate one-input Phis (which often happen to be LCSSA phis). I'd expect they are not in value map in this case.

llvm/include/llvm/Analysis/ScalarEvolution.h

private:
 
   /// Helper for forgetMemoizedResults.
   void forgetMemoizedResultsImpl(const SCEV *S);
 
   /// Iterate over instructions in \p Worlist 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);
+                          SmallVectorImpl<const SCEV *> &ToForget,
+                          const Loop *CurrL);
 
 #ifndef NDEBUG
   /// Iterate over instructions in \p Worlist and their users. Assert all users
   /// have been removed from ValueExprMap.
   void verifyAllUsersClearedFromMap(SmallVectorImpl<Instruction *> &Worklist,
                                     SmallPtrSetImpl<Instruction *> &Visited);
 #endif
 

llvm/lib/Analysis/ScalarEvolution.cpp

void ScalarEvolution::forgetAllLoops() {
   MinTrailingZerosCache.clear();
   PredicatedSCEVRewrites.clear();
   FoldCache.clear();
   FoldCacheUser.clear();
 }
 void ScalarEvolution::visitAndClearUsers(
     SmallVectorImpl<Instruction *> &Worklist,
     SmallPtrSetImpl<Instruction *> &Visited,
-    SmallVectorImpl<const SCEV *> &ToForget) {
+    SmallVectorImpl<const SCEV *> &ToForget, const Loop *CurrL) {
   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);
+    } else if ((CurrL && LI.getLoopFor(I->getParent()) == CurrL) ||
+               isa<PHINode>(I))
       PushDefUseChildren(I, Worklist, Visited);
   }
 }
 
 #ifndef NDEBUG
 void ScalarEvolution::verifyAllUsersClearedFromMap(
     SmallVectorImpl<Instruction *> &Worklist,
     SmallPtrSetImpl<Instruction *> &Visited) {
   while (!Worklist.empty()) {
if (LoopUsersItr != LoopUsers.end()) {
                 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);
+    visitAndClearUsers(Worklist, Visited, ToForget, CurrL);
 
     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::forgetValue(Value *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);
+  visitAndClearUsers(Worklist, Visited, ToForget,
+                     LI.getLoopFor(I->getParent()));
 
   forgetMemoizedResults(ToForget);
 
 #ifndef NDEBUG
   SmallVector<Instruction *, 16> VerificationWorklist;
   SmallPtrSet<Instruction *, 8> VerificationVisited;
   Worklist.push_back(cast<Instruction>(V));
   Visited.insert(cast<Instruction>(V));