Completely purge DomSet. This is the (hopefully) final patch for PR1171.

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

8 files changed, 16 insertions, 329 deletions

diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index 1a6320fde3..c359fb80fb 100644
--- a/include/llvm/Analysis/Dominators.h
+++ b/include/llvm/Analysis/Dominators.h
@@ -10,8 +10,7 @@
 // This file defines the following classes:
 //  1. ImmediateDominators: Calculates and holds a mapping between BasicBlocks
 //     and their immediate dominator.
-//  2. DominatorSet: Calculates the [reverse] dominator set for a function
-//  3. DominatorTree: Represent the ImmediateDominator as an explicit tree
+//  2. DominatorTree: Represent the ImmediateDominator as an explicit tree
 //     structure.
 //  4. ETForest: Efficient data structure for dominance comparisons and 
 //     nearest-common-ancestor queries.
@@ -175,127 +174,6 @@ private:
   void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo);
 };
 
-
-
-//===----------------------------------------------------------------------===//
-/// DominatorSet - Maintain a set<BasicBlock*> for every basic block in a
-/// function, that represents the blocks that dominate the block.  If the block
-/// is unreachable in this function, the set will be empty.  This cannot happen
-/// for reachable code, because every block dominates at least itself.
-///
-class DominatorSetBase : public DominatorBase {
-public:
-  typedef std::set<BasicBlock*> DomSetType;    // Dom set for a bb
-  // Map of dom sets
-  typedef std::map<BasicBlock*, DomSetType> DomSetMapType;
-protected:
-  DomSetMapType Doms;
-public:
-  DominatorSetBase(bool isPostDom) : DominatorBase(isPostDom) {}
-
-  virtual void releaseMemory() { Doms.clear(); }
-
-  // Accessor interface:
-  typedef DomSetMapType::const_iterator const_iterator;
-  typedef DomSetMapType::iterator iterator;
-  inline const_iterator begin() const { return Doms.begin(); }
-  inline       iterator begin()       { return Doms.begin(); }
-  inline const_iterator end()   const { return Doms.end(); }
-  inline       iterator end()         { return Doms.end(); }
-  inline const_iterator find(BasicBlock* B) const { return Doms.find(B); }
-  inline       iterator find(BasicBlock* B)       { return Doms.find(B); }
-
-
-  /// getDominators - Return the set of basic blocks that dominate the specified
-  /// block.
-  ///
-  inline const DomSetType &getDominators(BasicBlock *BB) const {
-    const_iterator I = find(BB);
-    assert(I != end() && "BB not in function!");
-    return I->second;
-  }
-
-  /// isReachable - Return true if the specified basicblock is reachable.  If
-  /// the block is reachable, we have dominator set information for it.
-  ///
-  bool isReachable(BasicBlock *BB) const {
-    return !getDominators(BB).empty();
-  }
-
-  /// dominates - Return true if A dominates B.
-  ///
-  inline bool dominates(BasicBlock *A, BasicBlock *B) const {
-    return getDominators(B).count(A) != 0;
-  }
-
-  /// properlyDominates - Return true if A dominates B and A != B.
-  ///
-  bool properlyDominates(BasicBlock *A, BasicBlock *B) const {
-    return dominates(A, B) && A != B;
-  }
-
-  /// print - Convert to human readable form
-  ///
-  virtual void print(std::ostream &OS, const Module* = 0) const;
-  void print(std::ostream *OS, const Module* M = 0) const {
-    if (OS) print(*OS, M);
-  }
-
-  /// dominates - Return true if A dominates B.  This performs the special
-  /// checks necessary if A and B are in the same basic block.
-  ///
-  bool dominates(Instruction *A, Instruction *B) const;
-
-  //===--------------------------------------------------------------------===//
-  // API to update (Post)DominatorSet information based on modifications to
-  // the CFG...
-
-  /// addBasicBlock - Call to update the dominator set with information about a
-  /// new block that was inserted into the function.
-  ///
-  void addBasicBlock(BasicBlock *BB, const DomSetType &Dominators) {
-    assert(find(BB) == end() && "Block already in DominatorSet!");
-    Doms.insert(std::make_pair(BB, Dominators));
-  }
-
-  /// addDominator - If a new block is inserted into the CFG, then method may be
-  /// called to notify the blocks it dominates that it is in their set.
-  ///
-  void addDominator(BasicBlock *BB, BasicBlock *NewDominator) {
-    iterator I = find(BB);
-    assert(I != end() && "BB is not in DominatorSet!");
-    I->second.insert(NewDominator);
-  }
-};
-
-
-//===-------------------------------------
-/// DominatorSet Class - Concrete subclass of DominatorSetBase that is used to
-/// compute a normal dominator set.
-///
-class DominatorSet : public DominatorSetBase {
-public:
-  DominatorSet() : DominatorSetBase(false) {}
-
-  virtual bool runOnFunction(Function &F);
-
-  BasicBlock *getRoot() const {
-    assert(Roots.size() == 1 && "Should always have entry node!");
-    return Roots[0];
-  }
-
-  /// getAnalysisUsage - This simply provides a dominator set
-  ///
-  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
-    AU.addRequired<ImmediateDominators>();
-    AU.setPreservesAll();
-  }
-
-  // stub - dummy function, just ignore it
-  static int stub;
-};
-
-
 //===----------------------------------------------------------------------===//
 /// DominatorTree - Calculate the immediate dominator tree for a function.
 ///
@@ -691,7 +569,4 @@ private:
 
 } // End llvm namespace
 
-// Make sure that any clients of this file link in Dominators.cpp
-FORCE_DEFINING_FILE_TO_BE_LINKED(DominatorSet)
-
 #endif
diff --git a/include/llvm/Analysis/PostDominators.h b/include/llvm/Analysis/PostDominators.h
index 4d8d140373..aea901374e 100644
--- a/include/llvm/Analysis/PostDominators.h
+++ b/include/llvm/Analysis/PostDominators.h
@@ -38,29 +38,6 @@ private:
   void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo);
 };
 
-/// PostDominatorSet Class - Concrete subclass of DominatorSetBase that is used
-/// to compute the post-dominator set.  Because there can be multiple exit nodes
-/// in an LLVM function, we calculate post dominators with a special null block
-/// which is the virtual exit node that the real exit nodes all virtually branch
-/// to.  Clients should be prepared to see an entry in the dominator sets with a
-/// null BasicBlock*.
-///
-struct PostDominatorSet : public DominatorSetBase {
-  PostDominatorSet() : DominatorSetBase(true) {}
-  
-  virtual bool runOnFunction(Function &F);
-  
-  /// getAnalysisUsage - This simply provides a dominator set
-  ///
-  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
-    AU.addRequired<ImmediatePostDominators>();
-    AU.setPreservesAll();
-  }
-  
-  // stub - dummy function, just ignore it
-  static void stub();
-};
-
 /// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
 /// compute the a post-dominator tree.
 ///
diff --git a/include/llvm/LinkAllPasses.h b/include/llvm/LinkAllPasses.h
index 6d85154eae..7481c82025 100644
--- a/include/llvm/LinkAllPasses.h
+++ b/include/llvm/LinkAllPasses.h
@@ -114,7 +114,6 @@ namespace {
 
       (void)new llvm::IntervalPartition();
       (void)new llvm::ImmediateDominators();
-      (void)new llvm::PostDominatorSet();
       (void)new llvm::FindUsedTypes();
       (void)new llvm::ScalarEvolution();
       ((llvm::Function*)0)->viewCFGOnly();
diff --git a/include/llvm/Transforms/Utils/BasicBlockUtils.h b/include/llvm/Transforms/Utils/BasicBlockUtils.h
index 25f3839dc7..9c49c5e685 100644
--- a/include/llvm/Transforms/Utils/BasicBlockUtils.h
+++ b/include/llvm/Transforms/Utils/BasicBlockUtils.h
@@ -61,7 +61,7 @@ bool isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum,
                     bool AllowIdenticalEdges = false);
 
 /// SplitCriticalEdge - If this edge is a critical edge, insert a new node to
-/// split the critical edge.  This will update DominatorSet, ImmediateDominator,
+/// split the critical edge.  This will update ETForest, ImmediateDominator,
 /// DominatorTree, and DominatorFrontier information if it is available, thus
 /// calling this pass will not invalidate either of them.  This returns true if
 /// the edge was split, false otherwise.  If MergeIdenticalEdges is true (the
diff --git a/include/llvm/Transforms/Utils/FunctionUtils.h b/include/llvm/Transforms/Utils/FunctionUtils.h
index 12291cb473..a09c9010c6 100644
--- a/include/llvm/Transforms/Utils/FunctionUtils.h
+++ b/include/llvm/Transforms/Utils/FunctionUtils.h
@@ -19,7 +19,6 @@
 
 namespace llvm {
   class BasicBlock;
-  class DominatorSet;
   class Function;
   class Loop;
 
diff --git a/lib/Analysis/PostDominators.cpp b/lib/Analysis/PostDominators.cpp
index d1fe9dd7f6..24399405fc 100644
--- a/lib/Analysis/PostDominators.cpp
+++ b/lib/Analysis/PostDominators.cpp
@@ -167,73 +167,6 @@ bool ImmediatePostDominators::runOnFunction(Function &F) {
 }
 
 //===----------------------------------------------------------------------===//
-//  PostDominatorSet Implementation
-//===----------------------------------------------------------------------===//
-
-static RegisterPass<PostDominatorSet>
-B("postdomset", "Post-Dominator Set Construction", true);
-
-// Postdominator set construction.  This converts the specified function to only
-// have a single exit node (return stmt), then calculates the post dominance
-// sets for the function.
-//
-bool PostDominatorSet::runOnFunction(Function &F) {
-  // Scan the function looking for the root nodes of the post-dominance
-  // relationships.  These blocks end with return and unwind instructions.
-  // While we are iterating over the function, we also initialize all of the
-  // domsets to empty.
-  Roots.clear();
-  for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
-    if (succ_begin(I) == succ_end(I))
-      Roots.push_back(I);
-
-  // If there are no exit nodes for the function, postdomsets are all empty.
-  // This can happen if the function just contains an infinite loop, for
-  // example.
-  ImmediatePostDominators &IPD = getAnalysis<ImmediatePostDominators>();
-  Doms.clear();   // Reset from the last time we were run...
-  if (Roots.empty()) return false;
-
-  // If we have more than one root, we insert an artificial "null" exit, which
-  // has "virtual edges" to each of the real exit nodes.
-  //if (Roots.size() > 1)
-  //  Doms[0].insert(0);
-
-  // Root nodes only dominate themselves.
-  for (unsigned i = 0, e = Roots.size(); i != e; ++i)
-    Doms[Roots[i]].insert(Roots[i]);
-  
-  // Loop over all of the blocks in the function, calculating dominator sets for
-  // each function.
-  for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
-    if (BasicBlock *IPDom = IPD[I]) {   // Get idom if block is reachable
-      DomSetType &DS = Doms[I];
-      assert(DS.empty() && "PostDomset already filled in for this block?");
-      DS.insert(I);  // Blocks always dominate themselves
-
-      // Insert all dominators into the set...
-      while (IPDom) {
-        // If we have already computed the dominator sets for our immediate post
-        // dominator, just use it instead of walking all the way up to the root.
-        DomSetType &IPDS = Doms[IPDom];
-        if (!IPDS.empty()) {
-          DS.insert(IPDS.begin(), IPDS.end());
-          break;
-        } else {
-          DS.insert(IPDom);
-          IPDom = IPD[IPDom];
-        }
-      }
-    } else {
-      // Ensure that every basic block has at least an empty set of nodes.  This
-      // is important for the case when there is unreachable blocks.
-      Doms[I];
-    }
-
-  return false;
-}
-
-//===----------------------------------------------------------------------===//
 //  PostDominatorTree Implementation
 //===----------------------------------------------------------------------===//
 
diff --git a/lib/Transforms/Scalar/LoopStrengthReduce.cpp b/lib/Transforms/Scalar/LoopStrengthReduce.cpp
index 676285c200..0cc9851f72 100644
--- a/lib/Transforms/Scalar/LoopStrengthReduce.cpp
+++ b/lib/Transforms/Scalar/LoopStrengthReduce.cpp
@@ -154,7 +154,6 @@ namespace {
       // many analyses if they are around.
       AU.addPreservedID(LoopSimplifyID);
       AU.addPreserved<LoopInfo>();
-      AU.addPreserved<DominatorSet>();
       AU.addPreserved<ETForest>();
       AU.addPreserved<ImmediateDominators>();
       AU.addPreserved<DominanceFrontier>();
diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp
index 9bd51bf4d9..4988049c8b 100644
--- a/lib/VMCore/Dominators.cpp
+++ b/lib/VMCore/Dominators.cpp
@@ -251,113 +251,6 @@ void ImmediateDominatorsBase::print(std::ostream &o, const Module* ) const {
   o << "\n";
 }
 
-
-
-//===----------------------------------------------------------------------===//
-//  DominatorSet Implementation
-//===----------------------------------------------------------------------===//
-
-static RegisterPass<DominatorSet>
-B("domset", "Dominator Set Construction", 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 DominatorSetBase::dominates(Instruction *A, Instruction *B) const {
-  BasicBlock *BBA = A->getParent(), *BBB = B->getParent();
-  if (BBA != BBB) return dominates(BBA, BBB);
-
-  // It is not possible to determine dominance between two PHI nodes 
-  // based on their ordering.
-  if (isa<PHINode>(A) && isa<PHINode>(B)) 
-    return false;
-
-  // 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;
-  }
-}
-
-
-// runOnFunction - This method calculates the forward dominator sets for the
-// specified function.
-//
-bool DominatorSet::runOnFunction(Function &F) {
-  BasicBlock *Root = &F.getEntryBlock();
-  Roots.clear();
-  Roots.push_back(Root);
-  assert(pred_begin(Root) == pred_end(Root) &&
-         "Root node has predecessors in function!");
-
-  ImmediateDominators &ID = getAnalysis<ImmediateDominators>();
-  Doms.clear();
-  if (Roots.empty()) return false;
-
-  // Root nodes only dominate themselves.
-  for (unsigned i = 0, e = Roots.size(); i != e; ++i)
-    Doms[Roots[i]].insert(Roots[i]);
-
-  // Loop over all of the blocks in the function, calculating dominator sets for
-  // each function.
-  for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
-    if (BasicBlock *IDom = ID[I]) {   // Get idom if block is reachable
-      DomSetType &DS = Doms[I];
-      assert(DS.empty() && "Domset already filled in for this block?");
-      DS.insert(I);  // Blocks always dominate themselves
-
-      // Insert all dominators into the set...
-      while (IDom) {
-        // If we have already computed the dominator sets for our immediate
-        // dominator, just use it instead of walking all the way up to the root.
-        DomSetType &IDS = Doms[IDom];
-        if (!IDS.empty()) {
-          DS.insert(IDS.begin(), IDS.end());
-          break;
-        } else {
-          DS.insert(IDom);
-          IDom = ID[IDom];
-        }
-      }
-    } else {
-      // Ensure that every basic block has at least an empty set of nodes.  This
-      // is important for the case when there is unreachable blocks.
-      Doms[I];
-    }
-
-  return false;
-}
-
-namespace llvm {
-static std::ostream &operator<<(std::ostream &o,
-                                const std::set<BasicBlock*> &BBs) {
-  for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end();
-       I != E; ++I)
-    if (*I)
-      WriteAsOperand(o, *I, false);
-    else
-      o << " <<exit node>>";
-  return o;
-}
-}
-
-void DominatorSetBase::print(std::ostream &o, const Module* ) const {
-  for (const_iterator I = begin(), E = end(); I != E; ++I) {
-    o << "  DomSet For BB: ";
-    if (I->first)
-      WriteAsOperand(o, I->first, false);
-    else
-      o << " <<exit node>>";
-    o << " is:\t" << I->second << "\n";
-  }
-}
-
 //===----------------------------------------------------------------------===//
 //  DominatorTree Implementation
 //===----------------------------------------------------------------------===//
@@ -528,6 +421,20 @@ DominanceFrontier::calculate(const DominatorTree &DT,
   return *Result;
 }
 
+namespace llvm {
+static std::ostream &operator<<(std::ostream &o,
+                                const std::set<BasicBlock*> &BBs) {
+  for (std::set<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end();
+       I != E; ++I)
+    if (*I)
+      WriteAsOperand(o, *I, false);
+    else
+      o << " <<exit node>>";
+  return o;
+}
+}
+
+
 void DominanceFrontierBase::print(std::ostream &o, const Module* ) const {
   for (const_iterator I = begin(), E = end(); I != E; ++I) {
     o << "  DomFrontier for BB";
@@ -1071,5 +978,3 @@ void ETForestBase::print(std::ostream &o, const Module *) const {
   }
   o << "\n";
 }
-
-DEFINING_FILE_FOR(DominatorSet)