[LPM] Switch LICM to actively use LCSSA in addition to preserving it.

Fixes PR18753 and PR18782.

This is necessary for LICM to preserve LCSSA correctly and efficiently.
There is still some active discussion about whether we should be using
LCSSA, but we can't just immediately stop using it and we *need* LICM to
preserve it while we are using it. We can restore the old SSAUpdater
driven code if and when there is a serious effort to remove the reliance
on LCSSA from all of the loop passes.

However, this also serves as a great example of why LCSSA is very nice
to have. This change significantly simplifies the process of sinking
instructions for LICM, and makes it quite a bit less expensive.

It wouldn't even be as complex as it is except that I had to start the
process of removing the big recursive LCSSA formation hammer in order to
switch even this much of the re-forming code to asserting that LCSSA was
preserved. I'll fully remove that next just to tidy things up until the
LCSSA debate settles one way or the other.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@201148 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 90 insertions, 152 deletions

diff --git a/lib/Transforms/Scalar/LICM.cpp b/lib/Transforms/Scalar/LICM.cpp
index 24ef172794..43247ea9b7 100644
--- a/lib/Transforms/Scalar/LICM.cpp
+++ b/lib/Transforms/Scalar/LICM.cpp
@@ -51,6 +51,7 @@
 #include "llvm/Support/CFG.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
+#include "llvm/Support/PredIteratorCache.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetLibraryInfo.h"
 #include "llvm/Transforms/Utils/Local.h"
@@ -187,7 +188,8 @@ namespace {
 
     void PromoteAliasSet(AliasSet &AS,
                          SmallVectorImpl<BasicBlock*> &ExitBlocks,
-                         SmallVectorImpl<Instruction*> &InsertPts);
+                         SmallVectorImpl<Instruction*> &InsertPts,
+                         PredIteratorCache &PIC);
   };
 }
 
@@ -222,6 +224,8 @@ bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) {
   TD = getAnalysisIfAvailable<DataLayout>();
   TLI = &getAnalysis<TargetLibraryInfo>();
 
+  assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.");
+
   CurAST = new AliasSetTracker(*AA);
   // Collect Alias info from subloops.
   for (Loop::iterator LoopItr = L->begin(), LoopItrE = L->end();
@@ -284,11 +288,12 @@ bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) {
   if (!DisablePromotion && (Preheader || L->hasDedicatedExits())) {
     SmallVector<BasicBlock *, 8> ExitBlocks;
     SmallVector<Instruction *, 8> InsertPts;
+    PredIteratorCache PIC;
 
     // Loop over all of the alias sets in the tracker object.
     for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end();
          I != E; ++I)
-      PromoteAliasSet(*I, ExitBlocks, InsertPts);
+      PromoteAliasSet(*I, ExitBlocks, InsertPts, PIC);
 
     // Once we have promoted values across the loop body we have to recursively
     // reform LCSSA as any nested loop may now have values defined within the
@@ -298,19 +303,14 @@ bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) {
     // it as it went.
     if (Changed)
       formLCSSARecursively(*L, *DT, getAnalysisIfAvailable<ScalarEvolution>());
-
-  } else if (Changed) {
-    // If we have successfully changed the loop but not used SSAUpdater to
-    // re-write instructions throughout the loop body, re-form LCSSA just for
-    // this loop.
-    formLCSSA(*L, *DT, getAnalysisIfAvailable<ScalarEvolution>());
   }
 
-  // Regardless of how we changed the loop, reform LCSSA on its parent as
-  // hoisting or sinking could have disrupted it.
-  if (Changed)
-    if (Loop *ParentL = L->getParentLoop())
-      formLCSSA(*ParentL, *DT, getAnalysisIfAvailable<ScalarEvolution>());
+  // Check that neither this loop nor its parent have had LCSSA broken. LICM is
+  // specifically moving instructions across the loop boundary and so it is
+  // especially in need of sanity checking here.
+  assert(L->isLCSSAForm(*DT) && "Loop not left in LCSSA form after LICM!");
+  assert((!L->getParentLoop() || L->getParentLoop()->isLCSSAForm(*DT)) &&
+         "Parent loop not left in LCSSA form after LICM!");
 
   // Clear out loops state information for the next iteration
   CurLoop = 0;
@@ -528,22 +528,6 @@ bool LICM::isNotUsedInLoop(Instruction &I) {
   return true;
 }
 
-static BasicBlock::iterator
-replaceTrivialPHIsAndGetInsertionPt(BasicBlock &BB, Instruction &I) {
-  BasicBlock::iterator II = BB.begin();
-  while (PHINode *PN = dyn_cast<PHINode>(II)) {
-    ++II;
-    if (isTriviallyReplacablePHI(*PN, I)) {
-      PN->replaceAllUsesWith(&I);
-      PN->eraseFromParent();
-    }
-  }
-  if (isa<LandingPadInst>(II))
-    ++II;
-
-  return II;
-}
-
 /// sink - When an instruction is found to only be used outside of the loop,
 /// this function moves it to the exit blocks and patches up SSA form as needed.
 /// This method is guaranteed to remove the original instruction from its
@@ -552,126 +536,59 @@ replaceTrivialPHIsAndGetInsertionPt(BasicBlock &BB, Instruction &I) {
 void LICM::sink(Instruction &I) {
   DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n");
 
-  SmallVector<BasicBlock*, 8> ExitBlocks;
-  CurLoop->getUniqueExitBlocks(ExitBlocks);
-
   if (isa<LoadInst>(I)) ++NumMovedLoads;
   else if (isa<CallInst>(I)) ++NumMovedCalls;
   ++NumSunk;
   Changed = true;
 
-  // The case where there is only a single exit node of this loop is common
-  // enough that we handle it as a special (more efficient) case.  It is more
-  // efficient to handle because there are no PHI nodes that need to be placed.
-  if (ExitBlocks.size() == 1) {
-    if (!DT->dominates(I.getParent(), ExitBlocks[0])) {
-      // Instruction is not used, just delete it.
-      CurAST->deleteValue(&I);
-      // If I has users in unreachable blocks, eliminate.
-      // If I is not void type then replaceAllUsesWith undef.
-      // This allows ValueHandlers and custom metadata to adjust itself.
-      if (!I.use_empty())
-        I.replaceAllUsesWith(UndefValue::get(I.getType()));
-      I.eraseFromParent();
-    } else {
-      // Look for any LCSSA PHI nodes for this instruction in the exit blocks
-      // and replace them.
-      BasicBlock::iterator II =
-          replaceTrivialPHIsAndGetInsertionPt(*ExitBlocks[0], I);
-
-      // Move the instruction to the start of the exit block, after any PHI
-      // nodes in it.
-      I.moveBefore(II);
-
-      // This instruction is no longer in the AST for the current loop, because
-      // we just sunk it out of the loop.  If we just sunk it into an outer
-      // loop, we will rediscover the operation when we process it.
-      CurAST->deleteValue(&I);
-    }
-    return;
-  }
-
-  if (ExitBlocks.empty()) {
-    // The instruction is actually dead if there ARE NO exit blocks.
-    CurAST->deleteValue(&I);
-    // If I has users in unreachable blocks, eliminate.
-    // If I is not void type then replaceAllUsesWith undef.
-    // This allows ValueHandlers and custom metadata to adjust itself.
-    if (!I.use_empty())
-      I.replaceAllUsesWith(UndefValue::get(I.getType()));
-    I.eraseFromParent();
-    return;
-  }
-
-  // Otherwise, if we have multiple exits, use the SSAUpdater to do all of the
-  // hard work of inserting PHI nodes as necessary.
-  SmallVector<PHINode*, 8> NewPHIs;
-  SSAUpdater SSA(&NewPHIs);
-
-  if (!I.use_empty())
-    SSA.Initialize(I.getType(), I.getName());
-
-  // Insert a copy of the instruction in each exit block of the loop that is
-  // dominated by the instruction.  Each exit block is known to only be in the
-  // ExitBlocks list once.
-  BasicBlock *InstOrigBB = I.getParent();
-  unsigned NumInserted = 0;
-
-  for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
-    BasicBlock *ExitBlock = ExitBlocks[i];
-
-    if (!DT->dominates(InstOrigBB, ExitBlock))
-      continue;
-
-    // Look for any LCSSA PHI nodes for this instruction in the exit blocks
-    // and replace them. Then get the insertion point after the last PHI.
-    BasicBlock::iterator InsertPt =
-      replaceTrivialPHIsAndGetInsertionPt(*ExitBlock, I);
-
-    // If this is the first exit block processed, just move the original
-    // instruction, otherwise clone the original instruction and insert
-    // the copy.
-    Instruction *New;
-    if (NumInserted++ == 0) {
-      I.moveBefore(InsertPt);
-      New = &I;
-    } else {
-      New = I.clone();
-      if (!I.getName().empty())
-        New->setName(I.getName()+".le");
-      ExitBlock->getInstList().insert(InsertPt, New);
-    }
-
-    // Now that we have inserted the instruction, inform SSAUpdater.
-    if (!I.use_empty())
-      SSA.AddAvailableValue(ExitBlock, New);
-  }
-
-  // If the instruction doesn't dominate any exit blocks, it must be dead.
-  if (NumInserted == 0) {
-    CurAST->deleteValue(&I);
-    if (!I.use_empty())
-      I.replaceAllUsesWith(UndefValue::get(I.getType()));
-    I.eraseFromParent();
-    return;
-  }
+#ifndef NDEBUG
+  SmallVector<BasicBlock *, 32> ExitBlocks;
+  CurLoop->getUniqueExitBlocks(ExitBlocks);
+  SmallPtrSet<BasicBlock *, 32> ExitBlockSet(ExitBlocks.begin(), ExitBlocks.end());
+#endif
+
+  // If this instruction is only used outside of the loop, then all users are
+  // PHI nodes in exit blocks due to LCSSA form. Just RAUW them with clones of
+  // the instruction.
+  while (!I.use_empty()) {
+    // The user must be a PHI node.
+    PHINode *PN = cast<PHINode>(I.use_back());
+
+    BasicBlock *ExitBlock = PN->getParent();
+    assert(ExitBlockSet.count(ExitBlock) &&
+           "The LCSSA PHI is not in an exit block!");
+
+    Instruction *New = I.clone();
+    ExitBlock->getInstList().insert(ExitBlock->getFirstInsertionPt(), New);
+    if (!I.getName().empty())
+      New->setName(I.getName() + ".le");
+
+    // Build LCSSA PHI nodes for any in-loop operands. Note that this is
+    // particularly cheap because we can rip off the PHI node that we're
+    // replacing for the number and blocks of the predecessors.
+    // OPT: If this shows up in a profile, we can instead finish sinking all
+    // invariant instructions, and then walk their operands to re-establish
+    // LCSSA. That will eliminate creating PHI nodes just to nuke them when
+    // sinking bottom-up.
+    for (User::op_iterator OI = New->op_begin(), OE = New->op_end(); OI != OE;
+         ++OI)
+      if (Instruction *OInst = dyn_cast<Instruction>(*OI))
+        if (Loop *OLoop = LI->getLoopFor(OInst->getParent()))
+          if (!OLoop->contains(PN)) {
+            PHINode *OpPN = PHINode::Create(
+                OInst->getType(), PN->getNumIncomingValues(),
+                OInst->getName() + ".lcssa", ExitBlock->begin());
+            for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
+              OpPN->addIncoming(OInst, PN->getIncomingBlock(i));
+            *OI = OpPN;
+          }
 
-  // Next, rewrite uses of the instruction, inserting PHI nodes as needed.
-  for (Value::use_iterator UI = I.use_begin(), UE = I.use_end(); UI != UE; ) {
-    // Grab the use before incrementing the iterator.
-    Use &U = UI.getUse();
-    // Increment the iterator before removing the use from the list.
-    ++UI;
-    SSA.RewriteUseAfterInsertions(U);
+    PN->replaceAllUsesWith(New);
+    PN->eraseFromParent();
   }
 
-  // Update CurAST for NewPHIs if I had pointer type.
-  if (I.getType()->isPointerTy())
-    for (unsigned i = 0, e = NewPHIs.size(); i != e; ++i)
-      CurAST->copyValue(&I, NewPHIs[i]);
-
-  // Finally, remove the instruction from CurAST.  It is no longer in the loop.
   CurAST->deleteValue(&I);
+  I.eraseFromParent();
 }
 
 /// hoist - When an instruction is found to only use loop invariant operands
@@ -742,21 +659,39 @@ namespace {
     SmallPtrSet<Value*, 4> &PointerMustAliases;
     SmallVectorImpl<BasicBlock*> &LoopExitBlocks;
     SmallVectorImpl<Instruction*> &LoopInsertPts;
+    PredIteratorCache &PredCache;
     AliasSetTracker &AST;
+    LoopInfo &LI;
     DebugLoc DL;
     int Alignment;
     MDNode *TBAATag;
+
+    Value *maybeInsertLCSSAPHI(Value *V, BasicBlock *BB) const {
+      if (Instruction *I = dyn_cast<Instruction>(V))
+        if (Loop *L = LI.getLoopFor(I->getParent()))
+          if (!L->contains(BB)) {
+            // We need to create an LCSSA PHI node for the incoming value and
+            // store that.
+            PHINode *PN = PHINode::Create(
+                I->getType(), PredCache.GetNumPreds(BB),
+                I->getName() + ".lcssa", BB->begin());
+            for (BasicBlock **PI = PredCache.GetPreds(BB); *PI; ++PI)
+              PN->addIncoming(I, *PI);
+            return PN;
+          }
+      return V;
+    }
+
   public:
-    LoopPromoter(Value *SP,
-                 const SmallVectorImpl<Instruction*> &Insts, SSAUpdater &S,
-                 SmallPtrSet<Value*, 4> &PMA,
-                 SmallVectorImpl<BasicBlock*> &LEB,
-                 SmallVectorImpl<Instruction*> &LIP,
-                 AliasSetTracker &ast, DebugLoc dl, int alignment,
+    LoopPromoter(Value *SP, const SmallVectorImpl<Instruction *> &Insts,
+                 SSAUpdater &S, SmallPtrSet<Value *, 4> &PMA,
+                 SmallVectorImpl<BasicBlock *> &LEB,
+                 SmallVectorImpl<Instruction *> &LIP, PredIteratorCache &PIC,
+                 AliasSetTracker &ast, LoopInfo &li, DebugLoc dl, int alignment,
                  MDNode *TBAATag)
-      : LoadAndStorePromoter(Insts, S), SomePtr(SP),
-        PointerMustAliases(PMA), LoopExitBlocks(LEB), LoopInsertPts(LIP),
-        AST(ast), DL(dl), Alignment(alignment), TBAATag(TBAATag) {}
+        : LoadAndStorePromoter(Insts, S), SomePtr(SP), PointerMustAliases(PMA),
+          LoopExitBlocks(LEB), LoopInsertPts(LIP), PredCache(PIC), AST(ast),
+          LI(li), DL(dl), Alignment(alignment), TBAATag(TBAATag) {}
 
     virtual bool isInstInList(Instruction *I,
                               const SmallVectorImpl<Instruction*> &) const {
@@ -776,8 +711,10 @@ namespace {
       for (unsigned i = 0, e = LoopExitBlocks.size(); i != e; ++i) {
         BasicBlock *ExitBlock = LoopExitBlocks[i];
         Value *LiveInValue = SSA.GetValueInMiddleOfBlock(ExitBlock);
+        LiveInValue = maybeInsertLCSSAPHI(LiveInValue, ExitBlock);
+        Value *Ptr = maybeInsertLCSSAPHI(SomePtr, ExitBlock);
         Instruction *InsertPos = LoopInsertPts[i];
-        StoreInst *NewSI = new StoreInst(LiveInValue, SomePtr, InsertPos);
+        StoreInst *NewSI = new StoreInst(LiveInValue, Ptr, InsertPos);
         NewSI->setAlignment(Alignment);
         NewSI->setDebugLoc(DL);
         if (TBAATag) NewSI->setMetadata(LLVMContext::MD_tbaa, TBAATag);
@@ -801,7 +738,8 @@ namespace {
 ///
 void LICM::PromoteAliasSet(AliasSet &AS,
                            SmallVectorImpl<BasicBlock*> &ExitBlocks,
-                           SmallVectorImpl<Instruction*> &InsertPts) {
+                           SmallVectorImpl<Instruction*> &InsertPts,
+                           PredIteratorCache &PIC) {
   // We can promote this alias set if it has a store, if it is a "Must" alias
   // set, if the pointer is loop invariant, and if we are not eliminating any
   // volatile loads or stores.
@@ -933,7 +871,7 @@ void LICM::PromoteAliasSet(AliasSet &AS,
   SmallVector<PHINode*, 16> NewPHIs;
   SSAUpdater SSA(&NewPHIs);
   LoopPromoter Promoter(SomePtr, LoopUses, SSA, PointerMustAliases, ExitBlocks,
-                        InsertPts, *CurAST, DL, Alignment, TBAATag);
+                        InsertPts, PIC, *CurAST, *LI, DL, Alignment, TBAATag);
 
   // Set up the preheader to have a definition of the value.  It is the live-out
   // value from the preheader that uses in the loop will use.