From 3b57b6f36e906d69cc578f3e2f72dcd263a72a30 Mon Sep 17 00:00:00 2001
From: Devang Patel <dpatel@apple.com>
Date: Tue, 20 Mar 2007 20:18:12 +0000
Subject: [PATCH] LoopSimplify::FindPHIToPartitionLoops() Use ETForest instead
 of DominatorSet.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@35221 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Transforms/Utils/LoopSimplify.cpp | 10 ++++++----
 lib/VMCore/Dominators.cpp             | 19 +++++++++++++++++++
 2 files changed, 25 insertions(+), 4 deletions(-)

diff --git a/lib/Transforms/Utils/LoopSimplify.cpp b/lib/Transforms/Utils/LoopSimplify.cpp
index ab850d58fc6..044ca5b0fc3 100644
--- a/lib/Transforms/Utils/LoopSimplify.cpp
+++ b/lib/Transforms/Utils/LoopSimplify.cpp
@@ -66,6 +66,7 @@ namespace {
       AU.addRequired<LoopInfo>();
       AU.addRequired<DominatorSet>();
       AU.addRequired<DominatorTree>();
+      AU.addRequired<ETForest>();
 
       AU.addPreserved<LoopInfo>();
       AU.addPreserved<DominatorSet>();
@@ -417,13 +418,13 @@ static void AddBlockAndPredsToSet(BasicBlock *BB, BasicBlock *StopBlock,
 
 /// FindPHIToPartitionLoops - The first part of loop-nestification is to find a
 /// PHI node that tells us how to partition the loops.
-static PHINode *FindPHIToPartitionLoops(Loop *L, DominatorSet &DS,
-                                        AliasAnalysis *AA) {
+static PHINode *FindPHIToPartitionLoops(Loop *L, ETForest *EF, 
+					AliasAnalysis *AA) {
   for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ) {
     PHINode *PN = cast<PHINode>(I);
     ++I;
     if (Value *V = PN->hasConstantValue())
-      if (!isa<Instruction>(V) || DS.dominates(cast<Instruction>(V), PN)) {
+      if (!isa<Instruction>(V) || EF->dominates(cast<Instruction>(V), PN)) {
         // This is a degenerate PHI already, don't modify it!
         PN->replaceAllUsesWith(V);
         if (AA) AA->deleteValue(PN);
@@ -497,7 +498,8 @@ void LoopSimplify::PlaceSplitBlockCarefully(BasicBlock *NewBB,
 /// created.
 ///
 Loop *LoopSimplify::SeparateNestedLoop(Loop *L) {
-  PHINode *PN = FindPHIToPartitionLoops(L, getAnalysis<DominatorSet>(), AA);
+  ETForest *EF = getAnalysisToUpdate<ETForest>();
+  PHINode *PN = FindPHIToPartitionLoops(L, EF, AA);
   if (PN == 0) return 0;  // No known way to partition.
 
   // Pull out all predecessors that have varying values in the loop.  This
diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp
index 3a6721aaabb..f7607061935 100644
--- a/lib/VMCore/Dominators.cpp
+++ b/lib/VMCore/Dominators.cpp
@@ -883,6 +883,25 @@ void ETForestBase::updateDFSNumbers()
   DFSInfoValid = true;
 }
 
+// dominates - Return true if A dominates B. THis performs the
+// special checks necessary if A and B are in the same basic block.
+bool ETForestBase::dominates(Instruction *A, Instruction *B) {
+  BasicBlock *BBA = A->getParent(), *BBB = B->getParent();
+  if (BBA != BBB) return dominates(BBA, BBB);
+  
+  // Loop through the basic block until we find A or B.
+  BasicBlock::iterator I = BBA->begin();
+  for (; &*I != A && &*I != B; ++I) /*empty*/;
+  
+  if(!IsPostDominators) {
+    // A dominates B if it is found first in the basic block.
+    return &*I == A;
+  } else {
+    // A post-dominates B if B is found first in the basic block.
+    return &*I == B;
+  }
+}
+
 ETNode *ETForest::getNodeForBlock(BasicBlock *BB) {
   ETNode *&BBNode = Nodes[BB];
   if (BBNode) return BBNode;
-- 
2.34.1