diff options
author | Chris Lattner <sabre@nondot.org> | 2003-11-13 02:01:41 +0000 |
---|---|---|
committer | Chris Lattner <sabre@nondot.org> | 2003-11-13 02:01:41 +0000 |
commit | 2d3e1ee93cd1d3423897ef9cd4faf26864730d0b (patch) | |
tree | 03e370cdddc7e89541c7c7e1d19d69f8cef8864e /include/Support/SCCIterator.h | |
parent | 95724a4aecc8f94e7f5ce2a65fbcfb987870ade3 (diff) | |
download | llvm-2d3e1ee93cd1d3423897ef9cd4faf26864730d0b.tar.gz llvm-2d3e1ee93cd1d3423897ef9cd4faf26864730d0b.tar.bz2 llvm-2d3e1ee93cd1d3423897ef9cd4faf26864730d0b.tar.xz |
Minor cleanups
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@9958 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'include/Support/SCCIterator.h')
-rw-r--r-- | include/Support/SCCIterator.h | 81 |
1 files changed, 38 insertions, 43 deletions
diff --git a/include/Support/SCCIterator.h b/include/Support/SCCIterator.h index f21c7d162e..4b4eadf704 100644 --- a/include/Support/SCCIterator.h +++ b/include/Support/SCCIterator.h @@ -78,56 +78,51 @@ class scc_iterator // The stack-based DFS traversal; defined below. void DFSVisitChildren() { assert(!VisitStack.empty()); - while (VisitStack.back().second != GT::child_end(VisitStack.back().first)) - { // TOS has at least one more child so continue DFS - NodeType *childN = *VisitStack.back().second++; - if (nodeVisitNumbers.find(childN) == nodeVisitNumbers.end()) - { // this node has never been seen - DFSVisitOne(childN); - } - else - { - unsigned childNum = nodeVisitNumbers[childN]; - if (MinVisitNumStack.back() > childNum) - MinVisitNumStack.back() = childNum; - } + while (VisitStack.back().second != GT::child_end(VisitStack.back().first)) { + // TOS has at least one more child so continue DFS + NodeType *childN = *VisitStack.back().second++; + if (!nodeVisitNumbers.count(childN)) { + // this node has never been seen + DFSVisitOne(childN); + } else { + unsigned childNum = nodeVisitNumbers[childN]; + if (MinVisitNumStack.back() > childNum) + MinVisitNumStack.back() = childNum; } + } } // Compute the next SCC using the DFS traversal. void GetNextSCC() { assert(VisitStack.size() == MinVisitNumStack.size()); CurrentSCC.clear(); // Prepare to compute the next SCC - while (! VisitStack.empty()) - { - DFSVisitChildren(); - - assert(VisitStack.back().second == - GT::child_end(VisitStack.back().first)); - NodeType* visitingN = VisitStack.back().first; - unsigned minVisitNum = MinVisitNumStack.back(); - VisitStack.pop_back(); - MinVisitNumStack.pop_back(); - if (! MinVisitNumStack.empty() && MinVisitNumStack.back() > minVisitNum) - MinVisitNumStack.back() = minVisitNum; - - //DEBUG(std::cerr << "TarjanSCC: Popped node " << visitingN << - // " : minVisitNum = " << minVisitNum << "; Node visit num = " << - // nodeVisitNumbers[visitingN] << "\n"); - - if (minVisitNum == nodeVisitNumbers[visitingN]) - { // A full SCC is on the SCCNodeStack! It includes all nodes below - // visitingN on the stack. Copy those nodes to CurrentSCC, - // reset their minVisit values, and return (this suspends - // the DFS traversal till the next ++). - do { - CurrentSCC.push_back(SCCNodeStack.back()); - SCCNodeStack.pop_back(); - nodeVisitNumbers[CurrentSCC.back()] = ~0UL; - } while (CurrentSCC.back() != visitingN); - return; - } - } + while (!VisitStack.empty()) { + DFSVisitChildren(); + assert(VisitStack.back().second ==GT::child_end(VisitStack.back().first)); + NodeType* visitingN = VisitStack.back().first; + unsigned minVisitNum = MinVisitNumStack.back(); + VisitStack.pop_back(); + MinVisitNumStack.pop_back(); + if (!MinVisitNumStack.empty() && MinVisitNumStack.back() > minVisitNum) + MinVisitNumStack.back() = minVisitNum; + + //DEBUG(std::cerr << "TarjanSCC: Popped node " << visitingN << + // " : minVisitNum = " << minVisitNum << "; Node visit num = " << + // nodeVisitNumbers[visitingN] << "\n"); + + if (minVisitNum == nodeVisitNumbers[visitingN]) { + // A full SCC is on the SCCNodeStack! It includes all nodes below + // visitingN on the stack. Copy those nodes to CurrentSCC, + // reset their minVisit values, and return (this suspends + // the DFS traversal till the next ++). + do { + CurrentSCC.push_back(SCCNodeStack.back()); + SCCNodeStack.pop_back(); + nodeVisitNumbers[CurrentSCC.back()] = ~0UL; + } while (CurrentSCC.back() != visitingN); + return; + } + } } inline scc_iterator(NodeType *entryN) : visitNum(0) { |