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

436–437

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

[meheff]

lib/Transforms/Utils/LoopUnroll.cpp

436–437

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.

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"
if (PHINode *PN = dyn_cast<PHINode>(I)) {
     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
       ValueToValueMapTy::iterator It = VMap.find(PN->getIncomingBlock(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) {
+/// 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.  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.