split dom frontier handling stuff out to its own DominanceFrontier header,

so that Dominators.h is *just* domtree.  Also prune #includes a bit.



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

1 files changed, 218 insertions, 0 deletions

diff --git a/include/llvm/Analysis/DominanceFrontier.h b/include/llvm/Analysis/DominanceFrontier.h
new file mode 100644
index 0000000000..d5669ea36f
--- /dev/null
+++ b/include/llvm/Analysis/DominanceFrontier.h
@@ -0,0 +1,218 @@
+//===- llvm/Analysis/DominanceFrontier.h - Dominator Frontiers --*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the DominanceFrontier class, which calculate and holds the
+// dominance frontier for a function.
+//
+// This should be considered deprecated, don't add any more uses of this data
+// structure.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_DOMINANCEFRONTIER_H
+#define LLVM_ANALYSIS_DOMINANCEFRONTIER_H
+
+#include "llvm/Analysis/Dominators.h"
+#include <map>
+#include <set>
+
+namespace llvm {
+  
+//===----------------------------------------------------------------------===//
+/// DominanceFrontierBase - Common base class for computing forward and inverse
+/// dominance frontiers for a function.
+///
+class DominanceFrontierBase : public FunctionPass {
+public:
+  typedef std::set<BasicBlock*>             DomSetType;    // Dom set for a bb
+  typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
+protected:
+  DomSetMapType Frontiers;
+  std::vector<BasicBlock*> Roots;
+  const bool IsPostDominators;
+
+public:
+  DominanceFrontierBase(char &ID, bool isPostDom)
+    : FunctionPass(ID), IsPostDominators(isPostDom) {}
+
+  /// getRoots - Return the root blocks of the current CFG.  This may include
+  /// multiple blocks if we are computing post dominators.  For forward
+  /// dominators, this will always be a single block (the entry node).
+  ///
+  inline const std::vector<BasicBlock*> &getRoots() const { return Roots; }
+
+  /// isPostDominator - Returns true if analysis based of postdoms
+  ///
+  bool isPostDominator() const { return IsPostDominators; }
+
+  virtual void releaseMemory() { Frontiers.clear(); }
+
+  // Accessor interface:
+  typedef DomSetMapType::iterator iterator;
+  typedef DomSetMapType::const_iterator const_iterator;
+  iterator       begin()       { return Frontiers.begin(); }
+  const_iterator begin() const { return Frontiers.begin(); }
+  iterator       end()         { return Frontiers.end(); }
+  const_iterator end()   const { return Frontiers.end(); }
+  iterator       find(BasicBlock *B)       { return Frontiers.find(B); }
+  const_iterator find(BasicBlock *B) const { return Frontiers.find(B); }
+
+  iterator addBasicBlock(BasicBlock *BB, const DomSetType &frontier) {
+    assert(find(BB) == end() && "Block already in DominanceFrontier!");
+    return Frontiers.insert(std::make_pair(BB, frontier)).first;
+  }
+
+  /// removeBlock - Remove basic block BB's frontier.
+  void removeBlock(BasicBlock *BB) {
+    assert(find(BB) != end() && "Block is not in DominanceFrontier!");
+    for (iterator I = begin(), E = end(); I != E; ++I)
+      I->second.erase(BB);
+    Frontiers.erase(BB);
+  }
+
+  void addToFrontier(iterator I, BasicBlock *Node) {
+    assert(I != end() && "BB is not in DominanceFrontier!");
+    I->second.insert(Node);
+  }
+
+  void removeFromFrontier(iterator I, BasicBlock *Node) {
+    assert(I != end() && "BB is not in DominanceFrontier!");
+    assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
+    I->second.erase(Node);
+  }
+
+  /// compareDomSet - Return false if two domsets match. Otherwise
+  /// return true;
+  bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const {
+    std::set<BasicBlock *> tmpSet;
+    for (DomSetType::const_iterator I = DS2.begin(),
+           E = DS2.end(); I != E; ++I)
+      tmpSet.insert(*I);
+
+    for (DomSetType::const_iterator I = DS1.begin(),
+           E = DS1.end(); I != E; ) {
+      BasicBlock *Node = *I++;
+
+      if (tmpSet.erase(Node) == 0)
+        // Node is in DS1 but not in DS2.
+        return true;
+    }
+
+    if (!tmpSet.empty())
+      // There are nodes that are in DS2 but not in DS1.
+      return true;
+
+    // DS1 and DS2 matches.
+    return false;
+  }
+
+  /// compare - Return true if the other dominance frontier base matches
+  /// this dominance frontier base. Otherwise return false.
+  bool compare(DominanceFrontierBase &Other) const {
+    DomSetMapType tmpFrontiers;
+    for (DomSetMapType::const_iterator I = Other.begin(),
+           E = Other.end(); I != E; ++I)
+      tmpFrontiers.insert(std::make_pair(I->first, I->second));
+
+    for (DomSetMapType::iterator I = tmpFrontiers.begin(),
+           E = tmpFrontiers.end(); I != E; ) {
+      BasicBlock *Node = I->first;
+      const_iterator DFI = find(Node);
+      if (DFI == end())
+        return true;
+
+      if (compareDomSet(I->second, DFI->second))
+        return true;
+
+      ++I;
+      tmpFrontiers.erase(Node);
+    }
+
+    if (!tmpFrontiers.empty())
+      return true;
+
+    return false;
+  }
+
+  /// print - Convert to human readable form
+  ///
+  virtual void print(raw_ostream &OS, const Module* = 0) const;
+
+  /// dump - Dump the dominance frontier to dbgs().
+  void dump() const;
+};
+
+
+//===-------------------------------------
+/// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is
+/// used to compute a forward dominator frontiers.
+///
+class DominanceFrontier : public DominanceFrontierBase {
+public:
+  static char ID; // Pass ID, replacement for typeid
+  DominanceFrontier() :
+    DominanceFrontierBase(ID, false) {
+      initializeDominanceFrontierPass(*PassRegistry::getPassRegistry());
+    }
+
+  BasicBlock *getRoot() const {
+    assert(Roots.size() == 1 && "Should always have entry node!");
+    return Roots[0];
+  }
+
+  virtual bool runOnFunction(Function &) {
+    Frontiers.clear();
+    DominatorTree &DT = getAnalysis<DominatorTree>();
+    Roots = DT.getRoots();
+    assert(Roots.size() == 1 && "Only one entry block for forward domfronts!");
+    calculate(DT, DT[Roots[0]]);
+    return false;
+  }
+
+  virtual void verifyAnalysis() const;
+
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+    AU.setPreservesAll();
+    AU.addRequired<DominatorTree>();
+  }
+
+  /// splitBlock - BB is split and now it has one successor. Update dominance
+  /// 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);
+    // If BB was an entry block then its frontier is empty.
+    if (DFI == end())
+      return;
+    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);
+  }
+
+  const DomSetType &calculate(const DominatorTree &DT,
+                              const DomTreeNode *Node);
+};
+
+} // End llvm namespace
+
+#endif