Changes in directory llvm/lib/Analysis:
PostDominators.cpp updated: 1.53 -> 1.54
---
Log message:
Initial implementation of the ET-Forest data structure for dominators and
post-dominators. This code was written/adapted by Daniel Berlin!
---
Diffs of the changes: (+63 -0)
PostDominators.cpp | 63 +++++++++++++++++++++++++++++++++++++++++++++++++++++
1 files changed, 63 insertions(+)
Index: llvm/lib/Analysis/PostDominators.cpp
diff -u llvm/lib/Analysis/PostDominators.cpp:1.53
llvm/lib/Analysis/PostDominators.cpp:1.54
--- llvm/lib/Analysis/PostDominators.cpp:1.53 Fri Nov 18 01:28:26 2005
+++ llvm/lib/Analysis/PostDominators.cpp Sun Jan 8 02:22:18 2006
@@ -205,6 +205,69 @@
}
}
}
+//===----------------------------------------------------------------------===//
+// PostETForest Implementation
+//===----------------------------------------------------------------------===//
+
+static RegisterAnalysis<PostETForest>
+G("postetforest", "Post-ET-Forest Construction", true);
+
+ETNode *PostETForest::getNodeForBlock(BasicBlock *BB) {
+ ETNode *&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<ImmediatePostDominators>()[BB];
+
+ // If we are unreachable, we may not have an immediate dominator.
+ if (!IDom)
+ return BBNode = new ETNode(BB);
+ else {
+ ETNode *IDomNode = getNodeForBlock(IDom);
+
+ // Add a new tree node for this BasicBlock, and link it as a child of
+ // IDomNode
+ BBNode = new ETNode(BB);
+ BBNode->setFather(IDomNode);
+ return BBNode;
+ }
+}
+
+void PostETForest::calculate(const ImmediatePostDominators &ID) {
+ for (unsigned i = 0, e = Roots.size(); i != e; ++i)
+ Nodes[Roots[i]] = new ETNode(Roots[i]); // Add a node for the root
+
+ // Iterate over all nodes in inverse depth first order.
+ for (unsigned i = 0, e = Roots.size(); i != e; ++i)
+ for (idf_iterator<BasicBlock*> I = idf_begin(Roots[i]),
+ E = idf_end(Roots[i]); I != E; ++I) {
+ BasicBlock *BB = *I;
+ ETNode *&BBNode = Nodes[BB];
+ if (!BBNode) {
+ ETNode *IDomNode = NULL;
+
+ if (ID.get(BB))
+ IDomNode = getNodeForBlock(ID.get(BB));
+
+ // Add a new ETNode for this BasicBlock, and set it's parent
+ // to it's immediate dominator.
+ BBNode = new ETNode(BB);
+ if (IDomNode)
+ BBNode->setFather(IDomNode);
+ }
+ }
+
+ int dfsnum = 0;
+ // Iterate over all nodes in depth first order...
+ for (unsigned i = 0, e = Roots.size(); i != e; ++i)
+ for (idf_iterator<BasicBlock*> I = idf_begin(Roots[i]),
+ E = idf_end(Roots[i]); I != E; ++I) {
+ if (!getNodeForBlock(*I)->hasFather())
+ getNodeForBlock(*I)->assignDFSNumber(dfsnum);
+ }
+ DFSInfoValid = true;
+}
//===----------------------------------------------------------------------===//
// PostDominanceFrontier Implementation
_______________________________________________
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
