-void cfg::DominatorTree::calculate(const DominatorSet &DS) {
- Nodes[Root] = new Node(Root, 0); // Add a node for the root...
-
- if (!isPostDominator()) {
- // Iterate over all nodes in depth first order...
- for (df_iterator<BasicBlock*> I = df_begin(Root), E = df_end(Root);
- I != E; ++I) {
- const BasicBlock *BB = *I;
- const DominatorSet::DomSetType &Dominators = DS.getDominators(BB);
- unsigned DomSetSize = Dominators.size();
- if (DomSetSize == 1) continue; // Root node... IDom = null
-
- // Loop over all dominators of this node. This corresponds to looping over
- // nodes in the dominator chain, looking for a node whose dominator set is
- // equal to the current nodes, except that the current node does not exist
- // in it. This means that it is one level higher in the dom chain than the
- // current node, and it is our idom! We know that we have already added
- // a DominatorTree node for our idom, because the idom must be a
- // predecessor in the depth first order that we are iterating through the
- // method.
- //
- DominatorSet::DomSetType::const_iterator I = Dominators.begin();
- DominatorSet::DomSetType::const_iterator End = Dominators.end();
- for (; I != End; ++I) { // Iterate over dominators...
- // All of our dominators should form a chain, where the number of
- // elements in the dominator set indicates what level the node is at in
- // the chain. We want the node immediately above us, so it will have
- // an identical dominator set, except that BB will not dominate it...
- // therefore it's dominator set size will be one less than BB's...
- //
- if (DS.getDominators(*I).size() == DomSetSize - 1) {
- // We know that the immediate dominator should already have a node,
- // because we are traversing the CFG in depth first order!
- //
- Node *IDomNode = Nodes[*I];
- assert(IDomNode && "No node for IDOM?");
-
- // Add a new tree node for this BasicBlock, and link it as a child of
- // IDomNode
- Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
- break;
- }
- }
- }
- } else if (Root) {
- // Iterate over all nodes in depth first order...
- for (idf_iterator<BasicBlock*> I = idf_begin(Root), E = idf_end(Root);
- I != E; ++I) {
- const BasicBlock *BB = *I;
- const DominatorSet::DomSetType &Dominators = DS.getDominators(BB);
- unsigned DomSetSize = Dominators.size();
- if (DomSetSize == 1) continue; // Root node... IDom = null
-
- // Loop over all dominators of this node. This corresponds to looping
- // over nodes in the dominator chain, looking for a node whose dominator
- // set is equal to the current nodes, except that the current node does
- // not exist in it. This means that it is one level higher in the dom
- // chain than the current node, and it is our idom! We know that we have
- // already added a DominatorTree node for our idom, because the idom must
- // be a predecessor in the depth first order that we are iterating through
- // the method.
- //
- DominatorSet::DomSetType::const_iterator I = Dominators.begin();
- DominatorSet::DomSetType::const_iterator End = Dominators.end();
- for (; I != End; ++I) { // Iterate over dominators...
- // All of our dominators should form a chain, where the number
- // of elements in the dominator set indicates what level the
- // node is at in the chain. We want the node immediately
- // above us, so it will have an identical dominator set,
- // except that BB will not dominate it... therefore it's
- // dominator set size will be one less than BB's...
- //
- if (DS.getDominators(*I).size() == DomSetSize - 1) {
- // We know that the immediate dominator should already have a node,
- // because we are traversing the CFG in depth first order!
- //
- Node *IDomNode = Nodes[*I];
- assert(IDomNode && "No node for IDOM?");
-
- // Add a new tree node for this BasicBlock, and link it as a child of
- // IDomNode
- Nodes[BB] = IDomNode->addChild(new Node(BB, IDomNode));
- break;
- }
+DominatorTreeBase::Node *DominatorTree::getNodeForBlock(BasicBlock *BB) {
+ Node *&BBNode = Nodes[BB];
+ if (BBNode) return BBNode;
+
+ // Haven't calculated this node yet? Get or calculate the node for the
+ // immediate dominator.
+ BasicBlock *IDom = getAnalysis<ImmediateDominators>()[BB];
+ Node *IDomNode = getNodeForBlock(IDom);
+
+ // Add a new tree node for this BasicBlock, and link it as a child of
+ // IDomNode
+ return BBNode = IDomNode->addChild(new Node(BB, IDomNode));
+}
+
+void DominatorTree::calculate(const ImmediateDominators &ID) {
+ assert(Roots.size() == 1 && "DominatorTree should have 1 root block!");
+ BasicBlock *Root = Roots[0];
+ Nodes[Root] = RootNode = new Node(Root, 0); // Add a node for the root...
+
+ Function *F = Root->getParent();
+ // Loop over all of the reachable blocks in the function...
+ for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
+ if (BasicBlock *ImmDom = ID.get(I)) { // Reachable block.
+ Node *&BBNode = Nodes[I];
+ if (!BBNode) { // Haven't calculated this node yet?
+ // Get or calculate the node for the immediate dominator
+ Node *IDomNode = getNodeForBlock(ImmDom);
+
+ // Add a new tree node for this BasicBlock, and link it as a child of
+ // IDomNode
+ BBNode = IDomNode->addChild(new Node(I, IDomNode));