[NFC][SCEV] Give hints on why we forget loops

[mkazantsev]

Summary

Following discussion in D120303, introduce API that allows us to
notify SCEV that some loop will be broken or entirely deleted with
all its subloops, and therefore there is no need to store cached data
for them. The conservative fallback is "loop may stay, keep dependencies
that should stay alive".

[reames]

I'm having a hard time wrapping my head around what this patch does and is expected to do.

If I'm reading the prior review correct, clearing the LoopUsers can result in functional bugs. Given that, this "hint" isn't really a hint. You must get it right, or you may have a functional bug. But this patch seems to be adding more cases where we clear LoopUsers? Is this a functional fix?

If not, what is the compile time impact of leaving LoopUsers in place when we could clear it? Is it significant? If not, introducing complexity here does not seem worthwhile.

As an aside, I'd naively expect the loop association to be cleared when the AddRec is. Is there a reason we can't identify the loop dependent SCEVS, forgetValue them, and let forgetValue handle the actual map manipulation? Seems conceptually cleaner and less error prone. (Unless I'm missing something - which is very possible.)

llvm/include/llvm/Analysis/ScalarEvolution.h

public:
 
   // This method should be called by the client when it made any change that
   // would invalidate SCEV's answers, and the client wants to remove all loop
   // information held internally by ScalarEvolution. This is intended to be used
   // when the alternative to forget a loop is too expensive (i.e. large loop
   // bodies).
   void forgetAllLoops();
 
+  /// Defines the type of invalidation on forgetLoop.
+  /// `Recompute` means that we change some essential facts to the loop (such as
+  /// exiting blocks), but the loop itself may stay in the IR. It is also the
+  /// reason that should be used when we just request forgetLoop to get more
+  /// precise results, or as a safe default option when we don't know whether
+  /// the loop will stay or not.
+  /// `WillBreak` means that we are going to break the loop itself (e.g. break
+  /// its backedge), but its header and some of the contained loops may stay
+  /// reachable. In this case we can safely drop cached information related to
+  /// this immediate loop.
+  /// `WillDelete` means that the header of this loop is no longer reachable,
+  /// and therefore this loop itself and all its contained loops will be
+  /// deleted. In this case we may safely drop cached information related to the
+  /// loop itself and all its subloops recursively.
+  enum ForgetLoopReason {
+    Recompute,
+    WillBreak,
+    WillDelete,
+  };
   /// This method should be called by the client when it has changed a loop in
   /// a way that may effect ScalarEvolution's ability to compute a trip count,
   /// or if the loop is deleted.  This call is potentially expensive for large
-  /// loop bodies.
-  void forgetLoop(const Loop *L);
+  /// loop bodies. The parameter \p WillDelete gives a hint on what will happen
+  /// next to this loop (if we are going to break it or delete with all
+  /// subloops), and this allows us to manage cached data more carefully.
+  void forgetLoop(const Loop *L, ForgetLoopReason ForgetReason = Recompute);
 
   // This method invokes forgetLoop for the outermost loop of the given loop
   // \p L, making ScalarEvolution forget about all this subtree. This needs to
   // be done whenever we make a transform that may affect the parameters of the
   // outer loop, such as exit counts for branches.
   void forgetTopmostLoop(const Loop *L);
 
   /// This method should be called by the client when it has changed a value

llvm/lib/Analysis/ScalarEvolution.cpp

void ScalarEvolution::forgetAllLoops() {
   UnsignedRanges.clear();
   SignedRanges.clear();
   ExprValueMap.clear();
   HasRecMap.clear();
   MinTrailingZerosCache.clear();
   PredicatedSCEVRewrites.clear();
 }
 
-void ScalarEvolution::forgetLoop(const Loop *L) {
+void ScalarEvolution::forgetLoop(const Loop *L, ForgetLoopReason ForgetReason) {
   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();
for (auto I = PredicatedSCEVRewrites.begin();
       else
         ++I;
     }
 
     auto LoopUsersItr = LoopUsers.find(CurrL);
     if (LoopUsersItr != LoopUsers.end()) {
       ToForget.insert(ToForget.end(), LoopUsersItr->second.begin(),
                 LoopUsersItr->second.end());
+      // All subloops will be destroyed, so no need to keep their users.
+      if (ForgetReason == WillDelete)
+        LoopUsers.erase(CurrL);
     }
 
     // Drop information about expressions based on loop-header PHIs.
     PushLoopPHIs(CurrL, Worklist, Visited);
 
     while (!Worklist.empty()) {
       Instruction *I = Worklist.pop_back_val();
 
while (!LoopWorklist.empty()) {
     }
 
     LoopPropertiesCache.erase(CurrL);
     // Forget all contained loops too, to avoid dangling entries in the
     // ValuesAtScopes map.
     LoopWorklist.append(CurrL->begin(), CurrL->end());
   }
   forgetMemoizedResults(ToForget);
+  // This loop will be broken, so no need to store its users.
+  if (ForgetReason == WillBreak)
+    LoopUsers.erase(L);
 }
 
 void ScalarEvolution::forgetTopmostLoop(const Loop *L) {
   while (Loop *Parent = L->getParentLoop())
     L = Parent;
   forgetLoop(L);
 }
 

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

static LoopDeletionResult deleteLoopIfDead(Loop *L, DominatorTree &DT,
 
   BasicBlock *ExitBlock = L->getUniqueExitBlock();
 
   if (ExitBlock && isLoopNeverExecuted(L)) {
     LLVM_DEBUG(dbgs() << "Loop is proven to never execute, delete it!");
     // We need to forget the loop before setting the incoming values of the exit
     // phis to undef, so we properly invalidate the SCEV expressions for those
     // phis.
-    SE.forgetLoop(L);
+    SE.forgetLoop(L, ScalarEvolution::ForgetLoopReason::WillDelete);
     // Set incoming value to undef for phi nodes in the exit block.
     for (PHINode &P : ExitBlock->phis()) {
       std::fill(P.incoming_values().begin(), P.incoming_values().end(),
                 UndefValue::get(P.getType()));
     }
     ORE.emit([&]() {
       return OptimizationRemark(DEBUG_TYPE, "NeverExecutes", L->getStartLoc(),
                                 L->getHeader())

llvm/lib/Transforms/Utils/LoopUtils.cpp

 
 void llvm::breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE,
                              LoopInfo &LI, MemorySSA *MSSA) {
   auto *Latch = L->getLoopLatch();
   assert(Latch && "multiple latches not yet supported");
   auto *Header = L->getHeader();
   Loop *OutermostLoop = getOutermostLoop(L);
 
-  SE.forgetLoop(L);
+  SE.forgetLoop(L, ScalarEvolution::ForgetLoopReason::WillBreak);
 
   std::unique_ptr<MemorySSAUpdater> MSSAU;
   if (MSSA)
     MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
 
   // Update the CFG and domtree.  We chose to special case a couple of
   // of common cases for code quality and test readability reasons.
   [&]() -> void {