Changes in directory llvm/lib/VMCore:
Dominators.cpp updated: 1.75 -> 1.76
---
Log message:
Use iterative algorith to assign DFS number. This reduces
call stack depth.
---
Diffs of the changes: (+47 -0)
Dominators.cpp | 47 +++++++++++++++++++++++++++++++++++++++++++++++
1 files changed, 47 insertions(+)
Index: llvm/lib/VMCore/Dominators.cpp
diff -u llvm/lib/VMCore/Dominators.cpp:1.75 llvm/lib/VMCore/Dominators.cpp:1.76
--- llvm/lib/VMCore/Dominators.cpp:1.75 Thu Sep 14 16:43:24 2006
+++ llvm/lib/VMCore/Dominators.cpp Thu Sep 21 20:05:33 2006
@@ -809,6 +809,53 @@
return occmin->OccFor;
}
+void ETNode::assignDFSNumber(int num) {
+ std::vector<ETNode *> workStack;
+ std::set<ETNode *> visitedNodes;
+
+ workStack.push_back(this);
+ visitedNodes.insert(this);
+ this->DFSNumIn = num++;
+
+ while (!workStack.empty()) {
+ ETNode *Node = workStack.back();
+
+ // If this is leaf node then set DFSNumOut and pop the stack
+ if (!Node->Son) {
+ Node->DFSNumOut = num++;
+ workStack.pop_back();
+ continue;
+ }
+
+ ETNode *son = Node->Son;
+
+ // Visit Node->Son first
+ if (visitedNodes.count(son) == 0) {
+ son->DFSNumIn = num++;
+ workStack.push_back(son);
+ visitedNodes.insert(son);
+ continue;
+ }
+
+ bool visitChild = false;
+ // Visit remaining children
+ for (ETNode *s = son->Right; s != son && !visitChild; s = s->Right) {
+ if (visitedNodes.count(s) == 0) {
+ visitChild = true;
+ s->DFSNumIn = num++;
+ workStack.push_back(s);
+ visitedNodes.insert(s);
+ }
+ }
+
+ if (!visitChild) {
+ // If we reach here means all children are visited
+ Node->DFSNumOut = num++;
+ workStack.pop_back();
+ }
+ }
+}
+
//===----------------------------------------------------------------------===//
// ETForest implementation
//===----------------------------------------------------------------------===//
_______________________________________________
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
