DomTreeNode *IDom;
ETNode *ETN;
std::vector<DomTreeNode*> Children;
+ int DFSNumIn, DFSNumOut;
+
public:
typedef std::vector<DomTreeNode*>::iterator iterator;
typedef std::vector<DomTreeNode*>::const_iterator const_iterator;
inline const std::vector<DomTreeNode*> &getChildren() const { return Children; }
inline DomTreeNode(BasicBlock *BB, DomTreeNode *iDom, ETNode *E)
- : TheBB(BB), IDom(iDom), ETN(E) {
+ : TheBB(BB), IDom(iDom), ETN(E), DFSNumIn(-1), DFSNumOut(-1) {
if (IDom)
ETN->setFather(IDom->getETNode());
}
inline DomTreeNode *addChild(DomTreeNode *C) { Children.push_back(C); return C; }
void setIDom(DomTreeNode *NewIDom);
+
+ // Return true if this node is dominated by other. Use this only if DFS info is valid.
+ bool DominatedBy(const DomTreeNode *other) const {
+ return this->DFSNumIn >= other->DFSNumIn &&
+ this->DFSNumOut <= other->DFSNumOut;
+ }
+
+ /// assignDFSNumber - Assign In and Out numbers while walking dominator tree
+ /// in dfs order.
+ void assignDFSNumber(int num);
};
//===----------------------------------------------------------------------===//
ETNode *NodeB = B->getETNode();
if (DFSInfoValid)
- return NodeB->DominatedBy(NodeA);
+ return B->DominatedBy(A);
+ //return NodeB->DominatedBy(NodeA);
// If we end up with too many slow queries, just update the
// DFS numbers on the theory that we are going to keep querying.
SlowQueries++;
if (SlowQueries > 32) {
updateDFSNumbers();
- return NodeB->DominatedBy(NodeA);
+ return B->DominatedBy(A);
+ //return NodeB->DominatedBy(NodeA);
}
//return NodeB->DominatedBySlow(NodeA);
return dominatedBySlowTreeWalk(A, B);
BasicBlock *BB = *I;
DomTreeNode *BBNode = getNode(BB);
if (BBNode) {
- ETNode *ETN = BBNode->getETNode();
- if (ETN && !ETN->hasFather())
- ETN->assignDFSNumber(dfsnum);
+ if (!BBNode->getIDom())
+ BBNode->assignDFSNumber(dfsnum);
+ //ETNode *ETN = BBNode->getETNode();
+ //if (ETN && !ETN->hasFather())
+ // ETN->assignDFSNumber(dfsnum);
}
}
SlowQueries = 0;
return NULL;
}
+/// assignDFSNumber - Assign In and Out numbers while walking dominator tree
+/// in dfs order.
+void DomTreeNode::assignDFSNumber(int num) {
+ std::vector<DomTreeNode *> workStack;
+ std::set<DomTreeNode *> visitedNodes;
+
+ workStack.push_back(this);
+ visitedNodes.insert(this);
+ this->DFSNumIn = num++;
+
+ while (!workStack.empty()) {
+ DomTreeNode *Node = workStack.back();
+
+ bool visitChild = false;
+ for (std::vector<DomTreeNode*>::iterator DI = Node->begin(),
+ E = Node->end(); DI != E && !visitChild; ++DI) {
+ DomTreeNode *Child = *DI;
+ if (visitedNodes.count(Child) == 0) {
+ visitChild = true;
+ Child->DFSNumIn = num++;
+ workStack.push_back(Child);
+ visitedNodes.insert(Child);
+ }
+ }
+ if (!visitChild) {
+ // If we reach here means all children are visited
+ Node->DFSNumOut = num++;
+ workStack.pop_back();
+ }
+ }
+}
+
void DomTreeNode::setIDom(DomTreeNode *NewIDom) {
assert(IDom && "No immediate dominator?");
if (IDom != NewIDom) {