Partially fix PR20058: reduce compile time for loop unrolling with very high count

[meheff]

Summary

This patch removes redundant calls to ScalarEvolution::forgetLoop when loop unrolling. For very high loop count loops this cuts the compile time (such as the one in the PR) by about a factor of two.

[hfinkel]

lib/Transforms/Utils/LoopUnroll.cpp

438–439

How do you know that LI->getLoopFor(Dest) returns the same Loop for all Dest in this loop?

[meheff]

lib/Transforms/Utils/LoopUnroll.cpp

438–439

Good point. Changed to using a pointer set to keep track of forgotten loops.

[hfinkel]

LGTM. Thanks!

Also, can you add an explicit note in ScalarEvolution.h above the forgetLoop declaration warning that the call is potentially expensive.

[meheff]

On Wed, Jun 25, 2014 at 9:34 AM, Eli Bendersky <[e-mail]> wrote:

Is this part of the code well covered by tests? Maybe some more targeted
tests can be crafted.

There are a few tests which require forgetting more than one loop (eg test/Transforms/LoopUnroll/pr11361.ll). One case where this can occur is if an inner loop is fully unrolled. In this case both the inner loop and the containing loop are forgotten.

On Mon, Jun 30, 2014 at 3:29 PM, [e-mail] <[e-mail]> wrote:

Also, can you add an explicit note in ScalarEvolution.h above the forgetLoop declaration warning that the call is potentially expensive.

Done.

[meheff]

commited as r212782.

include/llvm/Analysis/ScalarEvolution.h

public:
     const SCEV *getMaxBackedgeTakenCount(const Loop *L);
 
     /// hasLoopInvariantBackedgeTakenCount - Return true if the specified loop
     /// has an analyzable loop-invariant backedge-taken count.
     bool hasLoopInvariantBackedgeTakenCount(const Loop *L);
 
     /// forgetLoop - 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.
+    /// compute a trip count, or if the loop is deleted.  This call is
+    /// potentially expensive for large loop bodies.
     void forgetLoop(const Loop *L);
 
     /// forgetValue - This method should be called by the client when it has
     /// changed a value in a way that may effect its value, or which may
     /// disconnect it from a def-use chain linking it to a loop.
     void forgetValue(Value *V);
 
     /// \brief Called when the client has changed the disposition of values in

lib/Transforms/Utils/LoopUnroll.cpp

 // unrolling.
 //
 // The process of unrolling can produce extraneous basic blocks linked with
 // unconditional branches.  This will be corrected in the future.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/UnrollLoop.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopIterator.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/DiagnosticInfo.h"
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
       if (It != VMap.end())
         PN->setIncomingBlock(i, cast<BasicBlock>(It->second));
     }
   }
 }
 
 /// FoldBlockIntoPredecessor - Folds a basic block into its predecessor if it
 /// only has one predecessor, and that predecessor only has one successor.
-/// The LoopInfo Analysis that is passed will be kept consistent.
-/// Returns the new combined block.
-static BasicBlock *FoldBlockIntoPredecessor(BasicBlock *BB, LoopInfo* LI,
-                                            LPPassManager *LPM) {
+/// The LoopInfo Analysis that is passed will be kept consistent.  If folding is
+/// successful references to the containing loop must be removed from
+/// ScalarEvolution by calling ScalarEvolution::forgetLoop because SE may have
+/// references to the eliminated BB.  The argument ForgottenLoops contains a set
+/// of loops that have already been forgotten to prevent redundant, expensive
+/// calls to ScalarEvolution::forgetLoop.  Returns the new combined block.
+static BasicBlock *
+FoldBlockIntoPredecessor(BasicBlock *BB, LoopInfo* LI, LPPassManager *LPM,
+                         SmallPtrSetImpl<Loop *> &ForgottenLoops) {
   // Merge basic blocks into their predecessor if there is only one distinct
   // pred, and if there is only one distinct successor of the predecessor, and
   // if there are no PHI nodes.
   BasicBlock *OnlyPred = BB->getSinglePredecessor();
   if (!OnlyPred) return nullptr;
 
   if (OnlyPred->getTerminator()->getNumSuccessors() != 1)
     return nullptr;
FoldBlockIntoPredecessor(BasicBlock *BB, LoopInfo* LI, LPPassManager *LPM,
   // OldName will be valid until erased.
   StringRef OldName = BB->getName();
 
   // Erase basic block from the function...
 
   // ScalarEvolution holds references to loop exit blocks.
   if (LPM) {
     if (ScalarEvolution *SE = LPM->getAnalysisIfAvailable<ScalarEvolution>()) {
-      if (Loop *L = LI->getLoopFor(BB))
+      if (Loop *L = LI->getLoopFor(BB)) {
+        if (ForgottenLoops.insert(L))
           SE->forgetLoop(L);
       }
     }
+  }
   LI->removeBlock(BB);
 
   // Inherit predecessor's name if it exists...
   if (!OldName.empty() && !OnlyPred->hasName())
     OnlyPred->setName(OldName);
 
   BB->eraseFromParent();
 
if (NeedConditional) {
       }
       // Replace the conditional branch with an unconditional one.
       BranchInst::Create(Dest, Term);
       Term->eraseFromParent();
     }
   }
 
   // Merge adjacent basic blocks, if possible.
+  SmallPtrSet<Loop *, 4> ForgottenLoops;
   for (unsigned i = 0, e = Latches.size(); i != e; ++i) {
     BranchInst *Term = cast<BranchInst>(Latches[i]->getTerminator());
     if (Term->isUnconditional()) {
       BasicBlock *Dest = Term->getSuccessor(0);
-      if (BasicBlock *Fold = FoldBlockIntoPredecessor(Dest, LI, LPM))
+      if (BasicBlock *Fold = FoldBlockIntoPredecessor(Dest, LI, LPM,
+                                                      ForgottenLoops))
         std::replace(Latches.begin(), Latches.end(), Dest, Fold);
     }
   }
 
   DominatorTree *DT = nullptr;
   if (PP) {
     // FIXME: Reconstruct dom info, because it is not preserved properly.
     // Incrementally updating domtree after loop unrolling would be easy.