[SCEV] Don't walk uses of phis without SCEV expression when forgetting

[nikic]

Summary

I've run into some cases where a large fraction of compile-time is spent invalidating SCEV. One of the causes is forgetLoop(), which walks all values that are def-use reachable from the loop header phis. When invalidating a topmost loop, that might be close to all values in a function. Additionally, it's fairly common for there to not actually be anything to invalidate, but we'll still be performing this walk again and again.

My first thought was that we don't need to continue walking the uses if the current value doesn't have a SCEV expression. However, this isn't quite right, because SCEV construction can skip over values (e.g. for chain of adds, we might only create a SCEV expression for the final value).

What this patch does instead is to only walk the (full) def-use chain of loop phis that have a SCEV expression. If there's no expression for a phi, then we also don't have any dependent expressions to invalidate.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

7100

I don't quite get why is that supposed to help the compile time. We perform the same very check few lines below. Are you saving time on pushing/popping to the queue?

[mkazantsev]

llvm/include/llvm/Analysis/ScalarEvolution.h

2060

... const?

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

7100

The problem is that PushDefUseChildren() gets called even if the current value is not in ValueExprMap, and that's where all time ends up being spent, as it will visit all direct and indirect users for the phi.

[nikic]

Add const qualifier.

[mkazantsev]

Ok, looks good!

[bkramer]

Can this have an effect on codegen? I'm seeing a loop being turned into an infinite loop with this change, trying to extract a test case but it's buried inside of an enormous JIT'ed program.

[uabelho]

I wrote
https://bugs.llvm.org/show_bug.cgi?id=49967
about a crash that started appearing with this patch.

[nikic]

In D100264#2690562, @uabelho wrote:

I wrote
https://bugs.llvm.org/show_bug.cgi?id=49967
about a crash that started appearing with this patch.

Thanks, that was enlightening. I've left a comment there on why this broke. Unfortunately, the assumption this patch is based on turns out to be wrong :)

llvm/include/llvm/Analysis/ScalarEvolution.h

private:
   ///
   /// The first component of the returned tuple is the SCEV if found and null
   /// otherwise.  The second component is the `FoldingSetNodeID` that was
   /// constructed to look up the SCEV and the third component is the insertion
   /// point.
   std::tuple<SCEV *, FoldingSetNodeID, void *>
   findExistingSCEVInCache(SCEVTypes SCEVType, ArrayRef<const SCEV *> Ops);
 
+  /// Push PHI nodes in the header of the given loop onto the given Worklist
+  /// if they have a cached SCEV expression. If no expression is cached, then
+  /// there also aren't any dependent expressions to invalidate.
+  void pushCachedLoopPHIs(const Loop *L,
+                          SmallVectorImpl<Instruction *> &Worklist) const;
+
   FoldingSet<SCEV> UniqueSCEVs;
   FoldingSet<SCEVPredicate> UniquePreds;
   BumpPtrAllocator SCEVAllocator;
 
   /// This maps loops to a list of SCEV expressions that (transitively) use said
   /// loop.
   DenseMap<const Loop *, SmallVector<const SCEV *, 4>> LoopUsers;
 

llvm/lib/Analysis/ScalarEvolution.cpp

const SCEV *ScalarEvolution::getBackedgeTakenCount(const Loop *L,
   llvm_unreachable("Invalid ExitCountKind!");
 }
 
 bool ScalarEvolution::isBackedgeTakenCountMaxOrZero(const Loop *L) {
   return getBackedgeTakenInfo(L).isConstantMaxOrZero(this);
 }
 
 /// Push PHI nodes in the header of the given loop onto the given Worklist.
-static void
-PushLoopPHIs(const Loop *L, SmallVectorImpl<Instruction *> &Worklist) {
+/// Only push PHIs for which a SCEV expression has been cached, otherwise there
+/// cannot be any dependent expressions to invalidate.
+void ScalarEvolution::pushCachedLoopPHIs(
+    const Loop *L, SmallVectorImpl<Instruction *> &Worklist) const {
   BasicBlock *Header = L->getHeader();
-
-  // Push all Loop-header PHIs onto the Worklist stack.
-  for (PHINode &PN : Header->phis())
+  for (PHINode &PN : Header->phis()) {
+    auto It = ValueExprMap.find_as(static_cast<Value *>(&PN));
+    if (It != ValueExprMap.end())
       Worklist.push_back(&PN);
   }
+}
 
 const ScalarEvolution::BackedgeTakenInfo &
 ScalarEvolution::getPredicatedBackedgeTakenInfo(const Loop *L) {
   auto &BTI = getBackedgeTakenInfo(L);
   if (BTI.hasFullInfo())
     return BTI;
 
   auto Pair = PredicatedBackedgeTakenCounts.insert({L, BackedgeTakenInfo()});
#endif // LLVM_ENABLE_STATS || !defined(NDEBUG)
 
   // Now that we know more about the trip count for this loop, forget any
   // existing SCEV values for PHI nodes in this loop since they are only
   // 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);
+    pushCachedLoopPHIs(L, Worklist);
 
     SmallPtrSet<Instruction *, 8> Discovered;
     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
while (!LoopWorklist.empty()) {
     auto LoopUsersItr = LoopUsers.find(CurrL);
     if (LoopUsersItr != LoopUsers.end()) {
       for (auto *S : LoopUsersItr->second)
         forgetMemoizedResults(S);
       LoopUsers.erase(LoopUsersItr);
     }
 
     // Drop information about expressions based on loop-header PHIs.
-    PushLoopPHIs(CurrL, Worklist);
+    pushCachedLoopPHIs(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));