diff options
author | Devang Patel <dpatel@apple.com> | 2006-09-14 01:27:42 +0000 |
---|---|---|
committer | Devang Patel <dpatel@apple.com> | 2006-09-14 01:27:42 +0000 |
commit | 57d12f962d5af0c23283e0a129b95b106a517e46 (patch) | |
tree | 05e31488da9abe9c753e7073c758035dabffd19a /lib/VMCore/Dominators.cpp | |
parent | 08c33011d1443ce3e12b6c4026cde975b24c8e37 (diff) | |
download | llvm-57d12f962d5af0c23283e0a129b95b106a517e46.tar.gz llvm-57d12f962d5af0c23283e0a129b95b106a517e46.tar.bz2 llvm-57d12f962d5af0c23283e0a129b95b106a517e46.tar.xz |
Avoid recursion in assignDFSNumber(). Move def from ET-Forest.h
to Dominators.h
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@30309 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/VMCore/Dominators.cpp')
-rw-r--r-- | lib/VMCore/Dominators.cpp | 33 |
1 files changed, 33 insertions, 0 deletions
diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp index 9f7e5d9365..fd193b8d7a 100644 --- a/lib/VMCore/Dominators.cpp +++ b/lib/VMCore/Dominators.cpp @@ -890,6 +890,39 @@ void ETForest::calculate(const ImmediateDominators &ID) { updateDFSNumbers (); } +// Walk ETNode and its children using DFS algorithm and assign +// DFSNumIn and DFSNumOut numbers for each node. +void ETNode::assignDFSNumber(int &num) { + + std::vector<ETNode *> DFSInStack; + std::set<ETNode *> visited; + + DFSInStack.push_back(this); + + visited.insert(this); + + while(!DFSInStack.empty()) { + ETNode *Parent = DFSInStack.back(); + DFSInStack.pop_back(); + Parent->DFSNumIn = num++; + Parent->DFSNumOut = Parent->DFSNumIn + 1; + + ETNode *son = Parent->Son; + if (son && visited.count(son) == 0) { + + DFSInStack.push_back(son); + son->DFSNumIn = Parent->DFSNumIn + 1; + visited.insert(son); + + for (ETNode *s = son->Right; s != son; s = s->Right) { + DFSInStack.push_back(s); + s->DFSNumIn = Parent->DFSNumIn + 1; + visited.insert(s); + } + } + } +} + //===----------------------------------------------------------------------===// // ETForestBase Implementation //===----------------------------------------------------------------------===// |