-}
-
-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_const_iterator 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;
- }
+
+ Vertex.push_back(0);
+
+ // Step #1: Number blocks in depth-first order and initialize variables used
+ // in later stages of the algorithm.
+ unsigned N = 0;
+ for (unsigned i = 0, e = Roots.size(); i != e; ++i)
+ N = DFSPass(Roots[i], N);
+
+ for (unsigned i = N; i >= 2; --i) {
+ BasicBlock *W = Vertex[i];
+ InfoRec &WInfo = Info[W];
+
+ // Step #2: Calculate the semidominators of all vertices
+ for (succ_iterator SI = succ_begin(W), SE = succ_end(W); SI != SE; ++SI)
+ if (Info.count(*SI)) { // Only if this predecessor is reachable!
+ unsigned SemiU = Info[Eval(*SI)].Semi;
+ if (SemiU < WInfo.Semi)
+ WInfo.Semi = SemiU;