Update dominator info for the middle blocks created while spliting

exit edge to preserve LCSSA.

Fix dominance frontier update during loop unswitch. This fixes PR 1589.



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

3 files changed, 115 insertions, 22 deletions

diff --git a/lib/Transforms/Scalar/LoopUnswitch.cpp b/lib/Transforms/Scalar/LoopUnswitch.cpp
index 3a10bd7ae5..f787b82582 100644
--- a/lib/Transforms/Scalar/LoopUnswitch.cpp
+++ b/lib/Transforms/Scalar/LoopUnswitch.cpp
@@ -543,17 +543,8 @@ void LoopUnswitch::EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val,
     std::swap(TrueDest, FalseDest);
 
   // Insert the new branch.
-  BranchInst *BRI = new BranchInst(TrueDest, FalseDest, BranchVal, InsertPt);
-
-  // Update dominator info.
-  // BranchVal is a new preheader so it dominates true and false destination
-  // loop headers.
-  if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>()) {
-    DT->changeImmediateDominator(TrueDest, BRI->getParent());
-    DT->changeImmediateDominator(FalseDest, BRI->getParent());
-  }
-  // No need to update DominanceFrontier. BRI->getParent() dominated TrueDest
-  // and FalseDest anyway. Now it immediately dominates them.
+  new BranchInst(TrueDest, FalseDest, BranchVal, InsertPt);
+
 }
 
 
@@ -635,12 +626,14 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val,
 
   // Split all of the edges from inside the loop to their exit blocks.  Update
   // the appropriate Phi nodes as we do so.
+  SmallVector<BasicBlock *,8> MiddleBlocks;
   for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
     BasicBlock *ExitBlock = ExitBlocks[i];
     std::vector<BasicBlock*> Preds(pred_begin(ExitBlock), pred_end(ExitBlock));
 
     for (unsigned j = 0, e = Preds.size(); j != e; ++j) {
       BasicBlock* MiddleBlock = SplitEdge(Preds[j], ExitBlock, this);
+      MiddleBlocks.push_back(MiddleBlock);
       BasicBlock* StartBlock = Preds[j];
       BasicBlock* EndBlock;
       if (MiddleBlock->getSinglePredecessor() == ExitBlock) {
@@ -685,6 +678,9 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val,
   // Add exit blocks to the loop blocks.
   LoopBlocks.insert(LoopBlocks.end(), ExitBlocks.begin(), ExitBlocks.end());
 
+  DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>();
+  DominatorTree *DT = getAnalysisToUpdate<DominatorTree>();
+
   // Next step, clone all of the basic blocks that make up the loop (including
   // the loop preheader and exit blocks), keeping track of the mapping between
   // the instructions and blocks.
@@ -698,16 +694,21 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val,
     LPM->cloneBasicBlockSimpleAnalysis(LoopBlocks[i], New, L);
   }
 
-  // Update dominator info
-  DominanceFrontier *DF = getAnalysisToUpdate<DominanceFrontier>();
-  if (DominatorTree *DT = getAnalysisToUpdate<DominatorTree>())
-    for (unsigned i = 0, e = LoopBlocks.size(); i != e; ++i) {
-      BasicBlock *LBB = LoopBlocks[i];
-      BasicBlock *NBB = NewBlocks[i];
-      CloneDomInfo(NBB, LBB, NewPreheader, OrigPreheader, 
-                   OrigHeader, DT, DF, ValueMap);
+  // OutSiders are basic block that are dominated by original header and
+  // at the same time they are not part of loop.
+  SmallPtrSet<BasicBlock *, 8> OutSiders;
+  if (DT) {
+    DomTreeNode *OrigHeaderNode = DT->getNode(OrigHeader);
+    for(std::vector<DomTreeNode*>::iterator DI = OrigHeaderNode->begin(), 
+          DE = OrigHeaderNode->end();  DI != DE; ++DI) {
+      BasicBlock *B = (*DI)->getBlock();
+
+      DenseMap<const Value*, Value*>::iterator VI = ValueMap.find(B);
+      if (VI == ValueMap.end()) 
+        OutSiders.insert(B);
     }
-  
+  }
+
   // Splice the newly inserted blocks into the function right before the
   // original preheader.
   F->getBasicBlockList().splice(LoopBlocks[0], F->getBasicBlockList(),
@@ -759,7 +760,61 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val,
   EmitPreheaderBranchOnCondition(LIC, Val, NewBlocks[0], LoopBlocks[0], OldBR);
   OldBR->eraseFromParent();
   LPM->deleteSimpleAnalysisValue(OldBR, L);
-  
+
+  // Update dominator info
+  if (DF && DT) {
+
+    // Clone dominator info for all cloned basic block.
+    for (unsigned i = 0, e = LoopBlocks.size(); i != e; ++i) {
+      BasicBlock *LBB = LoopBlocks[i];
+      BasicBlock *NBB = NewBlocks[i];
+      CloneDomInfo(NBB, LBB, NewPreheader, OrigPreheader, 
+                   OrigHeader, DT, DF, ValueMap);
+
+      // Remove any OutSiders from LBB and NBB's dominance frontier.
+      DominanceFrontier::iterator LBBI = DF->find(LBB);
+      if (LBBI != DF->end()) {
+        DominanceFrontier::DomSetType &LBSet = LBBI->second;
+        for (DominanceFrontier::DomSetType::iterator LI = LBSet.begin(),
+               LE = LBSet.end(); LI != LE; ++LI) {
+          BasicBlock *B = *LI;
+          if (OutSiders.count(B))
+            DF->removeFromFrontier(LBBI, B);
+        }
+      }
+
+      // Remove any OutSiders from LBB and NBB's dominance frontier.
+      DominanceFrontier::iterator NBBI = DF->find(NBB);
+      if (NBBI != DF->end()) {
+        DominanceFrontier::DomSetType NBSet = NBBI->second;
+        for (DominanceFrontier::DomSetType::iterator NI = NBSet.begin(),
+               NE = NBSet.end(); NI != NE; ++NI) {
+          BasicBlock *B = *NI;
+          if (OutSiders.count(B))
+            DF->removeFromFrontier(NBBI, B);
+        }
+      }
+    }
+
+    // MiddleBlocks are dominated by original pre header. SplitEdge updated
+    // MiddleBlocks' dominance frontier appropriately.
+    for (unsigned i = 0, e = MiddleBlocks.size(); i != e; ++i) {
+      BasicBlock *MBB = MiddleBlocks[i];
+      DT->changeImmediateDominator(MBB, OrigPreheader);
+    }
+
+    // All Outsiders are now dominated by original pre header.
+    for (SmallPtrSet<BasicBlock *, 8>::iterator OI = OutSiders.begin(),
+           OE = OutSiders.end(); OI != OE; ++OI) {
+      BasicBlock *OB = *OI;
+      DT->changeImmediateDominator(OB, OrigPreheader);
+    }
+
+    // New loop headers are dominated by original preheader
+    DT->changeImmediateDominator(NewBlocks[0], OrigPreheader);
+    DT->changeImmediateDominator(LoopBlocks[0], OrigPreheader);
+  }
+
   LoopProcessWorklist.push_back(NewLoop);
   redoLoop = true;
 
diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp
index 9b5ee1bb40..91b422c704 100644
--- a/lib/VMCore/Dominators.cpp
+++ b/lib/VMCore/Dominators.cpp
@@ -627,6 +627,15 @@ void DominanceFrontier::splitBlock(BasicBlock *NewBB) {
   if (!DT.dominates(NewBB, NewBBSucc))
     NewBBDominatesNewBBSucc = false;
 
+  // NewBBSucc inherites original NewBB frontier.
+  DominanceFrontier::iterator NewBBI = find(NewBB);
+  if (NewBBI != end()) {
+    DominanceFrontier::DomSetType NewBBSet = NewBBI->second;
+    DominanceFrontier::DomSetType NewBBSuccSet;
+    NewBBSuccSet.insert(NewBBSet.begin(), NewBBSet.end());
+    addBasicBlock(NewBBSucc, NewBBSuccSet);
+  }
+
   // If NewBB dominates NewBBSucc, then DF(NewBB) is now going to be the
   // DF(PredBlocks[0]) without the stuff that the new block does not dominate
   // a predecessor of.
@@ -648,7 +657,6 @@ void DominanceFrontier::splitBlock(BasicBlock *NewBB) {
           ++SetI;
       }
 
-      DominanceFrontier::iterator NewBBI = find(NewBB);
       if (NewBBI != end()) {
         DominanceFrontier::DomSetType NewBBSet = NewBBI->second;
         NewBBSet.insert(Set.begin(), Set.end());
diff --git a/test/Transforms/LoopUnswitch/2007-08-01-Dom.ll b/test/Transforms/LoopUnswitch/2007-08-01-Dom.ll
new file mode 100644
index 0000000000..9673e2e96a
--- /dev/null
+++ b/test/Transforms/LoopUnswitch/2007-08-01-Dom.ll
@@ -0,0 +1,30 @@
+; RUN: llvm-as < %s | opt -licm -loop-unswitch -disable-output 
+; PR 1589
+
+      	%struct.QBasicAtomic = type { i32 }
+
+define void @_ZNK5QDate9addMonthsEi(%struct.QBasicAtomic* sret  %agg.result, %struct.QBasicAtomic* %this, i32 %nmonths) {
+entry:
+	br label %cond_true90
+
+bb16:		; preds = %cond_true90
+	br i1 false, label %bb93, label %cond_true90
+
+bb45:		; preds = %cond_true90
+	br i1 false, label %bb53, label %bb58
+
+bb53:		; preds = %bb45
+	br i1 false, label %bb93, label %cond_true90
+
+bb58:		; preds = %bb45
+	store i32 0, i32* null, align 4
+	br i1 false, label %cond_true90, label %bb93
+
+cond_true90:		; preds = %bb58, %bb53, %bb16, %entry
+	%nmonths_addr.016.1 = phi i32 [ %nmonths, %entry ], [ 0, %bb16 ], [ 0, %bb53 ], [ %nmonths_addr.016.1, %bb58 ]		; <i32> [#uses=2]
+	%tmp14 = icmp slt i32 %nmonths_addr.016.1, -11		; <i1> [#uses=1]
+	br i1 %tmp14, label %bb16, label %bb45
+
+bb93:		; preds = %bb58, %bb53, %bb16
+	ret void
+}