From a6a8663894c4eff0bd183a6209f8165680b8c913 Mon Sep 17 00:00:00 2001
From: Devang Patel <dpatel@apple.com>
Date: Tue, 14 Aug 2007 18:35:57 +0000
Subject: [PATCH] Fix dominance frontier update while removing blocks.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@41082 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Transforms/Scalar/LoopIndexSplit.cpp | 37 +++++++++++++++++++-----
 1 file changed, 30 insertions(+), 7 deletions(-)

diff --git a/lib/Transforms/Scalar/LoopIndexSplit.cpp b/lib/Transforms/Scalar/LoopIndexSplit.cpp
index 02a812be0c2..1398692afde 100644
--- a/lib/Transforms/Scalar/LoopIndexSplit.cpp
+++ b/lib/Transforms/Scalar/LoopIndexSplit.cpp
@@ -97,8 +97,10 @@ namespace {
     /// loop may not be eliminated.
     bool safeExitBlock(SplitInfo &SD, BasicBlock *BB);
 
-    /// removeBlocks - Remove basic block BB and all blocks dominated by BB.
-    void removeBlocks(BasicBlock *InBB, Loop *LP);
+    /// removeBlocks - Remove basic block DeadBB and all blocks dominated by DeadBB.
+    /// This routine is used to remove split condition's dead branch, dominated by
+    /// DeadBB. LiveBB dominates split conidition's other branch.
+    void removeBlocks(BasicBlock *DeadBB, Loop *LP, BasicBlock *LiveBB);
 
     /// Find cost of spliting loop L.
     unsigned findSplitCost(Loop *L, SplitInfo &SD);
@@ -589,11 +591,14 @@ unsigned LoopIndexSplit::findSplitCost(Loop *L, SplitInfo &SD) {
   return Cost;
 }
 
-/// removeBlocks - Remove basic block BB and all blocks dominated by BB.
-void LoopIndexSplit::removeBlocks(BasicBlock *InBB, Loop *LP) {
+/// removeBlocks - Remove basic block DeadBB and all blocks dominated by DeadBB.
+/// This routine is used to remove split condition's dead branch, dominated by
+/// DeadBB. LiveBB dominates split conidition's other branch.
+void LoopIndexSplit::removeBlocks(BasicBlock *DeadBB, Loop *LP, 
+                                  BasicBlock *LiveBB) {
 
   SmallVector<std::pair<BasicBlock *, succ_iterator>, 8> WorkList;
-  WorkList.push_back(std::make_pair(InBB, succ_begin(InBB)));
+  WorkList.push_back(std::make_pair(DeadBB, succ_begin(DeadBB)));
   while (!WorkList.empty()) {
     BasicBlock *BB = WorkList.back(). first; 
     succ_iterator SIter =WorkList.back().second;
@@ -630,10 +635,28 @@ void LoopIndexSplit::removeBlocks(BasicBlock *InBB, Loop *LP) {
             break;
         }
 
+        DT->changeImmediateDominator(SuccBB, LiveBB);
+
         // If BB is not dominating SuccBB then SuccBB is in BB's dominance
         // frontiner. 
         DominanceFrontier::iterator BBDF = DF->find(BB);
         DF->removeFromFrontier(BBDF, SuccBB);
+
+        // LiveBB is now  dominating SuccBB. Which means SuccBB's dominance
+        // frontier is member of LiveBB's dominance frontier. However, SuccBB
+        // itself is not member of LiveBB's dominance frontier.
+        DominanceFrontier::iterator LiveDF = DF->find(LiveBB);
+        DominanceFrontier::iterator SuccDF = DF->find(SuccBB);
+        DominanceFrontier::DomSetType SuccBBSet = SuccDF->second;
+        for (DominanceFrontier::DomSetType::iterator SuccBBSetI = SuccBBSet.begin(),
+               SuccBBSetE = SuccBBSet.end(); SuccBBSetI != SuccBBSetE; ++SuccBBSetI) {
+          BasicBlock *DFMember = *SuccBBSetI;
+          // Insert only if LiveBB dominates DFMember.
+          if (!DT->dominates(LiveBB, DFMember))
+            LiveDF->second.insert(DFMember);
+        }
+        DF->removeFromFrontier(LiveDF, SuccBB);
+
       }
     }
   }
@@ -747,7 +770,7 @@ bool LoopIndexSplit::splitLoop(SplitInfo &SD) {
   BranchInst *BR = cast<BranchInst>(SplitBlock->getTerminator());
   BasicBlock *FBB = BR->getSuccessor(1);
   BR->setUnconditionalDest(BR->getSuccessor(0));
-  removeBlocks(FBB, L);
+  removeBlocks(FBB, L, BR->getSuccessor(0));
 
   //[*] Update True loop's exit value using new exit value.
   ExitCondition->setOperand(ExitValueNum, TLExitValue);
@@ -757,7 +780,7 @@ bool LoopIndexSplit::splitLoop(SplitInfo &SD) {
   BranchInst *FBR = cast<BranchInst>(FSplitBlock->getTerminator());
   BasicBlock *TBB = FBR->getSuccessor(0);
   FBR->setUnconditionalDest(FBR->getSuccessor(1));
-  removeBlocks(TBB, FalseLoop);
+  removeBlocks(TBB, FalseLoop, cast<BasicBlock>(FBR->getSuccessor(0)));
 
   return true;
 }
-- 
2.34.1