When one branch of condition is eliminated then head of the other

branch is not necessary immediate dominators of merge blcok in all cases.



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

3 files changed, 64 insertions, 22 deletions

diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index 41e6938459..ec6a67b60d 100644
--- a/include/llvm/Analysis/Dominators.h
+++ b/include/llvm/Analysis/Dominators.h
@@ -438,6 +438,26 @@ public:
   /// frontier to reflect this change.
   void splitBlock(BasicBlock *BB);
 
+  /// BasicBlock BB's new dominator is NewBB. Update BB's dominance frontier
+  /// to reflect this change.
+  void changeImmediateDominator(BasicBlock *BB, BasicBlock *NewBB,
+                                DominatorTree *DT) {
+    // NewBB is now  dominating BB. Which means BB's dominance
+    // frontier is now part of NewBB's dominance frontier. However, BB
+    // itself is not member of NewBB's dominance frontier.
+    DominanceFrontier::iterator NewDFI = find(NewBB);
+    DominanceFrontier::iterator DFI = find(BB);
+    DominanceFrontier::DomSetType BBSet = DFI->second;
+    for (DominanceFrontier::DomSetType::iterator BBSetI = BBSet.begin(),
+           BBSetE = BBSet.end(); BBSetI != BBSetE; ++BBSetI) {
+      BasicBlock *DFMember = *BBSetI;
+      // Insert only if NewBB dominates DFMember.
+      if (!DT->dominates(NewBB, DFMember))
+        NewDFI->second.insert(DFMember);
+    }
+    NewDFI->second.erase(BB);
+  }
+
 private:
   const DomSetType &calculate(const DominatorTree &DT,
                               const DomTreeNode *Node);
diff --git a/lib/Transforms/Scalar/LoopIndexSplit.cpp b/lib/Transforms/Scalar/LoopIndexSplit.cpp
index 565e00c895..980990ea65 100644
--- a/lib/Transforms/Scalar/LoopIndexSplit.cpp
+++ b/lib/Transforms/Scalar/LoopIndexSplit.cpp
@@ -603,6 +603,7 @@ void LoopIndexSplit::removeBlocks(BasicBlock *DeadBB, Loop *LP,
                                   BasicBlock *LiveBB) {
 
   // First update DeadBB's dominance frontier. 
+  SmallVector<BasicBlock *, 8> FrontierBBs;
   DominanceFrontier::iterator DeadBBDF = DF->find(DeadBB);
   if (DeadBBDF != DF->end()) {
     SmallVector<BasicBlock *, 8> PredBlocks;
@@ -611,7 +612,8 @@ void LoopIndexSplit::removeBlocks(BasicBlock *DeadBB, Loop *LP,
     for (DominanceFrontier::DomSetType::iterator DeadBBSetI = DeadBBSet.begin(),
            DeadBBSetE = DeadBBSet.end(); DeadBBSetI != DeadBBSetE; ++DeadBBSetI) {
       BasicBlock *FrontierBB = *DeadBBSetI;
-      
+      FrontierBBs.push_back(FrontierBB);
+
       // Rremove any PHI incoming edge from blocks dominated by DeadBB.
       PredBlocks.clear();
       for(pred_iterator PI = pred_begin(FrontierBB), PE = pred_end(FrontierBB);
@@ -620,7 +622,8 @@ void LoopIndexSplit::removeBlocks(BasicBlock *DeadBB, Loop *LP,
         if (P == DeadBB || DT->dominates(DeadBB, P))
           PredBlocks.push_back(P);
       }
-      
+
+      BasicBlock *NewDominator = NULL;
       for(BasicBlock::iterator FBI = FrontierBB->begin(), FBE = FrontierBB->end();
           FBI != FBE; ++FBI) {
         if (PHINode *PN = dyn_cast<PHINode>(FBI)) {
@@ -629,27 +632,14 @@ void LoopIndexSplit::removeBlocks(BasicBlock *DeadBB, Loop *LP,
             BasicBlock *P = *PI;
             PN->removeIncomingValue(P);
           }
+          // If we have not identified new dominator then see if we can identify
+          // one based on remaining incoming PHINode values.
+          if (NewDominator == NULL && PN->getNumIncomingValues() == 1)
+            NewDominator = PN->getIncomingBlock(0);
         }
         else
           break;
-      }
-
-      DT->changeImmediateDominator(FrontierBB, LiveBB);
-
-      // LiveBB is now  dominating FrontierBB. Which means FrontierBB's dominance
-      // frontier is member of LiveBB's dominance frontier. However, FrontierBB
-      // itself is not member of LiveBB's dominance frontier.
-      DominanceFrontier::iterator LiveDF = DF->find(LiveBB);
-      DominanceFrontier::iterator FrontierDF = DF->find(FrontierBB);
-      DominanceFrontier::DomSetType FrontierBBSet = FrontierDF->second;
-      for (DominanceFrontier::DomSetType::iterator FrontierBBSetI = FrontierBBSet.begin(),
-             FrontierBBSetE = FrontierBBSet.end(); FrontierBBSetI != FrontierBBSetE; ++FrontierBBSetI) {
-        BasicBlock *DFMember = *FrontierBBSetI;
-        // Insert only if LiveBB dominates DFMember.
-        if (!DT->dominates(LiveBB, DFMember))
-          LiveDF->second.insert(DFMember);
-      }
-      LiveDF->second.erase(FrontierBB);
+      }      
     }
   }
   
@@ -660,7 +650,7 @@ void LoopIndexSplit::removeBlocks(BasicBlock *DeadBB, Loop *LP,
          E = df_end(DN); DI != E; ++DI) {
     BasicBlock *BB = DI->getBlock();
     WorkList.push_back(BB);
-    BB->getTerminator()->eraseFromParent();
+    BB->replaceAllUsesWith(UndefValue::get(Type::LabelTy));
   }
 
   while (!WorkList.empty()) {
@@ -677,6 +667,31 @@ void LoopIndexSplit::removeBlocks(BasicBlock *DeadBB, Loop *LP,
     LI->removeBlock(BB);
     BB->eraseFromParent();
   }
+
+  // Update Frontier BBs' dominator info.
+  while (!FrontierBBs.empty()) {
+    BasicBlock *FBB = FrontierBBs.back(); FrontierBBs.pop_back();
+    BasicBlock *NewDominator = FBB->getSinglePredecessor();
+    if (!NewDominator) {
+      pred_iterator PI = pred_begin(FBB), PE = pred_end(FBB);
+      NewDominator = *PI;
+      ++PI;
+      if (NewDominator != LiveBB) {
+        for(; PI != PE; ++PI) {
+          BasicBlock *P = *PI;
+          if (P == LiveBB) {
+            NewDominator = LiveBB;
+            break;
+          }
+          NewDominator = DT->findNearestCommonDominator(NewDominator, P);
+        }
+      }
+    }
+    assert (NewDominator && "Unable to fix dominator info.");
+    DT->changeImmediateDominator(FBB, NewDominator);
+    DF->changeImmediateDominator(FBB, NewDominator, DT);
+  }
+
 }
 
 bool LoopIndexSplit::splitLoop(SplitInfo &SD) {
@@ -696,6 +711,12 @@ bool LoopIndexSplit::splitLoop(SplitInfo &SD) {
           || Latch == SplitTerminator->getSuccessor(1)))
     return false;
 
+
+  BasicBlock *Succ0 = SplitTerminator->getSuccessor(0);
+  BasicBlock *Succ1 = SplitTerminator->getSuccessor(1);
+  if (DT->dominates(Succ0, Latch) || DT->dominates(Succ1, Latch))
+    return false;
+
   // True loop is original loop. False loop is cloned loop.
 
   bool SignedPredicate = ExitCondition->isSignedPredicate();  
diff --git a/lib/Transforms/Utils/LCSSA.cpp b/lib/Transforms/Utils/LCSSA.cpp
index 466136dea7..465214cba9 100644
--- a/lib/Transforms/Utils/LCSSA.cpp
+++ b/lib/Transforms/Utils/LCSSA.cpp
@@ -107,7 +107,8 @@ bool LCSSA::runOnLoop(Loop *L, LPPassManager &LPM) {
   
   LI = &LPM.getAnalysis<LoopInfo>();
   DT = &getAnalysis<DominatorTree>();
-    
+  DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>();
+
   // Speed up queries by creating a sorted list of blocks
   LoopBlocks.clear();
   LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end());