-//===----------------------------------------------------------------------===//
-//
-// DominatorTree - Calculate the immediate dominator tree for a function.
-//
-class DominatorTreeBase : public DominatorBase {
-protected:
- class Node2;
-public:
- typedef Node2 Node;
-protected:
- std::map<BasicBlock*, Node*> Nodes;
- void reset();
- typedef std::map<BasicBlock*, Node*> NodeMapType;
-public:
- class Node2 : public std::vector<Node*> {
- friend class DominatorTree;
- friend class PostDominatorTree;
- BasicBlock *TheNode;
- Node2 *IDom;
- public:
- inline BasicBlock *getNode() const { return TheNode; }
- inline Node2 *getIDom() const { return IDom; }
- inline const std::vector<Node*> &getChildren() const { return *this; }
-
- // dominates - Returns true iff this dominates N. Note that this is not a
- // constant time operation!
- inline bool dominates(const Node2 *N) const {
- const Node2 *IDom;
- while ((IDom = N->getIDom()) != 0 && IDom != this)
- N = IDom; // Walk up the tree
- return IDom != 0;
- }
+ /// findNearestCommonDominator - Find nearest common dominator basic block
+ /// for basic block A and B. If there is no such block then return NULL.
+ BasicBlock *findNearestCommonDominator(BasicBlock *A, BasicBlock *B);
+
+ // 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);
+
+ //===--------------------------------------------------------------------===//
+ // API to update (Post)DominatorTree information based on modifications to
+ // the CFG...
+
+ /// addNewBlock - Add a new node to the dominator tree information. This
+ /// creates a new node as a child of DomBB dominator node,linking it into
+ /// the children list of the immediate dominator.
+ DomTreeNode *addNewBlock(BasicBlock *BB, BasicBlock *DomBB) {
+ assert(getNode(BB) == 0 && "Block already in dominator tree!");
+ DomTreeNode *IDomNode = getNode(DomBB);
+ assert(IDomNode && "Not immediate dominator specified for block!");
+ DFSInfoValid = false;
+ return DomTreeNodes[BB] =
+ IDomNode->addChild(new DomTreeNode(BB, IDomNode));
+ }