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

433

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

[meheff]

lib/Transforms/Utils/LoopUnroll.cpp

433

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

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.
+/// 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 loop must be removed from ScalarEvolution by
+/// calling ScalarEvolution::forgetLoop because SE may have references to the
+/// eliminated BB.  The parameter LoopForgotten indicates that the loop has
+/// 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) {
+                                            LPPassManager *LPM,
+                                            bool &LoopForgotten) {
   // 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;
static BasicBlock *FoldBlockIntoPredecessor(BasicBlock *BB, LoopInfo* LI,
   OnlyPred->getInstList().splice(OnlyPred->end(), BB->getInstList());
 
   // 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 (!LoopForgotten && LPM) {
     if (ScalarEvolution *SE = LPM->getAnalysisIfAvailable<ScalarEvolution>()) {
-      if (Loop *L = LI->getLoopFor(BB))
+      if (Loop *L = LI->getLoopFor(BB)) {
         SE->forgetLoop(L);
+        LoopForgotten = true;
+      }
     }
   }
   LI->removeBlock(BB);
 
   // Inherit predecessor's name if it exists...
   if (!OldName.empty() && !OnlyPred->hasName())
     OnlyPred->setName(OldName);
 
if (NeedConditional) {
       }
       // Replace the conditional branch with an unconditional one.
       BranchInst::Create(Dest, Term);
       Term->eraseFromParent();
     }
   }
 
   // Merge adjacent basic blocks, if possible.
+  bool LoopForgotten = false;
   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,
+                                                      LoopForgotten))
         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.