From 2d3e1ee93cd1d3423897ef9cd4faf26864730d0b Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Thu, 13 Nov 2003 02:01:41 +0000 Subject: [PATCH] Minor cleanups git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@9958 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/Support/SCCIterator.h | 81 ++++++++++++++++------------------ include/llvm/ADT/SCCIterator.h | 81 ++++++++++++++++------------------ 2 files changed, 76 insertions(+), 86 deletions(-) diff --git a/include/Support/SCCIterator.h b/include/Support/SCCIterator.h index f21c7d162e5..4b4eadf704f 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) { diff --git a/include/llvm/ADT/SCCIterator.h b/include/llvm/ADT/SCCIterator.h index f21c7d162e5..4b4eadf704f 100644 --- a/include/llvm/ADT/SCCIterator.h +++ b/include/llvm/ADT/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) { -- 2.34.1