From 55b2eb3ef828819a623444ce966e70ad86ad6da4 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Sun, 31 Aug 2003 20:01:57 +0000 Subject: Rename TarjanSCCIterator -> scc_iterator * Increases consistency with other iterators (e.g. df_iterator, po_iterator...) * It's shorter * We don't name classes by the implementation, we name it for the interface! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@8273 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/Support/SCCIterator.h | 37 ++++++++++++------------ include/llvm/ADT/SCCIterator.h | 37 ++++++++++++------------ lib/Analysis/DataStructure/MemoryDepAnalysis.cpp | 9 +++--- lib/Analysis/IPA/CallGraphSCCPass.cpp | 4 +-- lib/Analysis/IPA/MemoryDepAnalysis.cpp | 9 +++--- lib/Analysis/IPA/PrintSCC.cpp | 19 ++++++------ lib/Analysis/PrintSCC.cpp | 19 ++++++------ tools/analyze/PrintSCC.cpp | 19 ++++++------ tools/opt/PrintSCC.cpp | 19 ++++++------ 9 files changed, 86 insertions(+), 86 deletions(-) diff --git a/include/Support/SCCIterator.h b/include/Support/SCCIterator.h index 9daa6bd149..e8c4af6c8f 100644 --- a/include/Support/SCCIterator.h +++ b/include/Support/SCCIterator.h @@ -1,19 +1,18 @@ -//===-- Support/TarjanSCCIterator.h - Tarjan SCC iterator -------*- C++ -*-===// +//===-- Support/SCCIterator.h - SCC iterator --------------------*- C++ -*-===// // -// This builds on the Support/GraphTraits.h file to find the strongly -// connected components (SCCs) of a graph in O(N+E) time using -// Tarjan's DFS algorithm. +// This builds on the Support/GraphTraits.h file to find the strongly connected +// components (SCCs) of a graph in O(N+E) time using Tarjan's DFS algorithm. // -// The SCC iterator has the important property that if a node in SCC S1 -// has an edge to a node in SCC S2, then it visits S1 *after* S2. +// The SCC iterator has the important property that if a node in SCC S1 has an +// edge to a node in SCC S2, then it visits S1 *after* S2. // -// To visit S1 *before* S2, use the TarjanSCCIterator on the Inverse graph. +// To visit S1 *before* S2, use the scc_iterator on the Inverse graph. // (NOTE: This requires some simple wrappers and is not supported yet.) // //===----------------------------------------------------------------------===// -#ifndef SUPPORT_TARJANSCCITERATOR_H -#define SUPPORT_TARJANSCCITERATOR_H +#ifndef SUPPORT_SCCITERATOR_H +#define SUPPORT_SCCITERATOR_H #include "Support/GraphTraits.h" #include "Support/iterator" @@ -22,11 +21,11 @@ //===----------------------------------------------------------------------===// /// -/// TarjanSCC_iterator - Enumerate the SCCs of a directed graph, in +/// scc_iterator - Enumerate the SCCs of a directed graph, in /// reverse topological order of the SCC DAG. /// template > -class TarjanSCC_iterator +class scc_iterator : public forward_iterator, ptrdiff_t> { typedef typename GT::NodeType NodeType; typedef typename GT::ChildIteratorType ChildItTy; @@ -122,14 +121,14 @@ class TarjanSCC_iterator } } - inline TarjanSCC_iterator(NodeType *entryN) : visitNum(0) { + inline scc_iterator(NodeType *entryN) : visitNum(0) { DFSVisitOne(entryN); GetNextSCC(); } - inline TarjanSCC_iterator() { /* End is when DFS stack is empty */ } + inline scc_iterator() { /* End is when DFS stack is empty */ } public: - typedef TarjanSCC_iterator _Self; + typedef scc_iterator _Self; // Provide static "constructors"... static inline _Self begin(GraphT& G) { return _Self(GT::getEntryNode(G)); } @@ -180,15 +179,15 @@ public: }; -// Global constructor for the Tarjan SCC iterator. +// Global constructor for the SCC iterator. template -TarjanSCC_iterator tarj_begin(T G) { - return TarjanSCC_iterator::begin(G); +scc_iterator scc_begin(T G) { + return scc_iterator::begin(G); } template -TarjanSCC_iterator tarj_end(T G) { - return TarjanSCC_iterator::end(G); +scc_iterator scc_end(T G) { + return scc_iterator::end(G); } #endif diff --git a/include/llvm/ADT/SCCIterator.h b/include/llvm/ADT/SCCIterator.h index 9daa6bd149..e8c4af6c8f 100644 --- a/include/llvm/ADT/SCCIterator.h +++ b/include/llvm/ADT/SCCIterator.h @@ -1,19 +1,18 @@ -//===-- Support/TarjanSCCIterator.h - Tarjan SCC iterator -------*- C++ -*-===// +//===-- Support/SCCIterator.h - SCC iterator --------------------*- C++ -*-===// // -// This builds on the Support/GraphTraits.h file to find the strongly -// connected components (SCCs) of a graph in O(N+E) time using -// Tarjan's DFS algorithm. +// This builds on the Support/GraphTraits.h file to find the strongly connected +// components (SCCs) of a graph in O(N+E) time using Tarjan's DFS algorithm. // -// The SCC iterator has the important property that if a node in SCC S1 -// has an edge to a node in SCC S2, then it visits S1 *after* S2. +// The SCC iterator has the important property that if a node in SCC S1 has an +// edge to a node in SCC S2, then it visits S1 *after* S2. // -// To visit S1 *before* S2, use the TarjanSCCIterator on the Inverse graph. +// To visit S1 *before* S2, use the scc_iterator on the Inverse graph. // (NOTE: This requires some simple wrappers and is not supported yet.) // //===----------------------------------------------------------------------===// -#ifndef SUPPORT_TARJANSCCITERATOR_H -#define SUPPORT_TARJANSCCITERATOR_H +#ifndef SUPPORT_SCCITERATOR_H +#define SUPPORT_SCCITERATOR_H #include "Support/GraphTraits.h" #include "Support/iterator" @@ -22,11 +21,11 @@ //===----------------------------------------------------------------------===// /// -/// TarjanSCC_iterator - Enumerate the SCCs of a directed graph, in +/// scc_iterator - Enumerate the SCCs of a directed graph, in /// reverse topological order of the SCC DAG. /// template > -class TarjanSCC_iterator +class scc_iterator : public forward_iterator, ptrdiff_t> { typedef typename GT::NodeType NodeType; typedef typename GT::ChildIteratorType ChildItTy; @@ -122,14 +121,14 @@ class TarjanSCC_iterator } } - inline TarjanSCC_iterator(NodeType *entryN) : visitNum(0) { + inline scc_iterator(NodeType *entryN) : visitNum(0) { DFSVisitOne(entryN); GetNextSCC(); } - inline TarjanSCC_iterator() { /* End is when DFS stack is empty */ } + inline scc_iterator() { /* End is when DFS stack is empty */ } public: - typedef TarjanSCC_iterator _Self; + typedef scc_iterator _Self; // Provide static "constructors"... static inline _Self begin(GraphT& G) { return _Self(GT::getEntryNode(G)); } @@ -180,15 +179,15 @@ public: }; -// Global constructor for the Tarjan SCC iterator. +// Global constructor for the SCC iterator. template -TarjanSCC_iterator tarj_begin(T G) { - return TarjanSCC_iterator::begin(G); +scc_iterator scc_begin(T G) { + return scc_iterator::begin(G); } template -TarjanSCC_iterator tarj_end(T G) { - return TarjanSCC_iterator::end(G); +scc_iterator scc_end(T G) { + return scc_iterator::end(G); } #endif diff --git a/lib/Analysis/DataStructure/MemoryDepAnalysis.cpp b/lib/Analysis/DataStructure/MemoryDepAnalysis.cpp index 171df2e33b..110475a063 100644 --- a/lib/Analysis/DataStructure/MemoryDepAnalysis.cpp +++ b/lib/Analysis/DataStructure/MemoryDepAnalysis.cpp @@ -18,7 +18,7 @@ #include "llvm/iOther.h" #include "llvm/Support/InstVisitor.h" #include "llvm/Support/CFG.h" -#include "Support/TarjanSCCIterator.h" +#include "Support/SCCIterator.h" #include "Support/Statistic.h" #include "Support/STLExtras.h" #include "Support/hash_map" @@ -208,7 +208,7 @@ void MemoryDepAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { } -/// Basic dependence gathering algorithm, using TarjanSCCIterator on CFG: +/// Basic dependence gathering algorithm, using scc_iterator on CFG: /// /// for every SCC S in the CFG in PostOrder on the SCC DAG /// { @@ -290,7 +290,7 @@ void MemoryDepAnalysis::ProcessSCC(std::vector &S, ModRefInfoBuilder builder(*funcGraph, *funcModRef, ModRefCurrent); for (std::vector::iterator BI = S.begin(), BE = S.end(); BI != BE; ++BI) - // Note: BBs in the SCC<> created by TarjanSCCIterator are in postorder. + // Note: BBs in the SCC<> created by scc_iterator are in postorder. for (BasicBlock::reverse_iterator II=(*BI)->rbegin(), IE=(*BI)->rend(); II != IE; ++II) builder.visit(*II); @@ -438,8 +438,7 @@ bool MemoryDepAnalysis::runOnFunction(Function &F) { ModRefTable ModRefAfter; - for (TarjanSCC_iterator I = tarj_begin(&F), E = tarj_end(&F); - I != E; ++I) + for (scc_iterator I = scc_begin(&F), E = scc_end(&F); I != E; ++I) ProcessSCC(*I, ModRefAfter, I.hasLoop()); return true; diff --git a/lib/Analysis/IPA/CallGraphSCCPass.cpp b/lib/Analysis/IPA/CallGraphSCCPass.cpp index 031fb02d00..4f363dc1a0 100644 --- a/lib/Analysis/IPA/CallGraphSCCPass.cpp +++ b/lib/Analysis/IPA/CallGraphSCCPass.cpp @@ -10,7 +10,7 @@ #include "llvm/CallGraphSCCPass.h" #include "llvm/Analysis/CallGraph.h" -#include "Support/TarjanSCCIterator.h" +#include "Support/SCCIterator.h" /// getAnalysisUsage - For this class, we declare that we require and preserve /// the call graph. If the derived class implements this method, it should @@ -23,7 +23,7 @@ void CallGraphSCCPass::getAnalysisUsage(AnalysisUsage &AU) const { bool CallGraphSCCPass::run(Module &M) { CallGraph &CG = getAnalysis(); bool Changed = false; - for (TarjanSCC_iterator I = tarj_begin(&CG), E = tarj_end(&CG); + for (scc_iterator I = scc_begin(&CG), E = scc_end(&CG); I != E; ++I) Changed = runOnSCC(*I); return Changed; diff --git a/lib/Analysis/IPA/MemoryDepAnalysis.cpp b/lib/Analysis/IPA/MemoryDepAnalysis.cpp index 171df2e33b..110475a063 100644 --- a/lib/Analysis/IPA/MemoryDepAnalysis.cpp +++ b/lib/Analysis/IPA/MemoryDepAnalysis.cpp @@ -18,7 +18,7 @@ #include "llvm/iOther.h" #include "llvm/Support/InstVisitor.h" #include "llvm/Support/CFG.h" -#include "Support/TarjanSCCIterator.h" +#include "Support/SCCIterator.h" #include "Support/Statistic.h" #include "Support/STLExtras.h" #include "Support/hash_map" @@ -208,7 +208,7 @@ void MemoryDepAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { } -/// Basic dependence gathering algorithm, using TarjanSCCIterator on CFG: +/// Basic dependence gathering algorithm, using scc_iterator on CFG: /// /// for every SCC S in the CFG in PostOrder on the SCC DAG /// { @@ -290,7 +290,7 @@ void MemoryDepAnalysis::ProcessSCC(std::vector &S, ModRefInfoBuilder builder(*funcGraph, *funcModRef, ModRefCurrent); for (std::vector::iterator BI = S.begin(), BE = S.end(); BI != BE; ++BI) - // Note: BBs in the SCC<> created by TarjanSCCIterator are in postorder. + // Note: BBs in the SCC<> created by scc_iterator are in postorder. for (BasicBlock::reverse_iterator II=(*BI)->rbegin(), IE=(*BI)->rend(); II != IE; ++II) builder.visit(*II); @@ -438,8 +438,7 @@ bool MemoryDepAnalysis::runOnFunction(Function &F) { ModRefTable ModRefAfter; - for (TarjanSCC_iterator I = tarj_begin(&F), E = tarj_end(&F); - I != E; ++I) + for (scc_iterator I = scc_begin(&F), E = scc_end(&F); I != E; ++I) ProcessSCC(*I, ModRefAfter, I.hasLoop()); return true; diff --git a/lib/Analysis/IPA/PrintSCC.cpp b/lib/Analysis/IPA/PrintSCC.cpp index 0fbc240188..dfb7420542 100644 --- a/lib/Analysis/IPA/PrintSCC.cpp +++ b/lib/Analysis/IPA/PrintSCC.cpp @@ -2,9 +2,10 @@ // // This file provides passes to print out SCCs in a CFG or a CallGraph. // Normally, you would not use these passes; instead, you would use the -// TarjanSCCIterator directly to enumerate SCCs and process them in some way. -// These passes serve three purposes: -// (1) As a reference for how to use the TarjanSCCIterator. +// scc_iterator directly to enumerate SCCs and process them in some way. These +// passes serve three purposes: +// +// (1) As a reference for how to use the scc_iterator. // (2) To print out the SCCs for a CFG or a CallGraph: // analyze -cfgscc to print the SCCs in each CFG of a module. // analyze -cfgscc -stats to print the #SCCs and the maximum SCC size. @@ -13,7 +14,7 @@ // and similarly: // analyze -callscc [-stats] [-debug] to print SCCs in the CallGraph // -// (3) To test the TarjanSCCIterator. +// (3) To test the scc_iterator. // //===----------------------------------------------------------------------===// @@ -21,7 +22,7 @@ #include "llvm/Module.h" #include "llvm/Analysis/CallGraph.h" #include "llvm/Support/CFG.h" -#include "Support/TarjanSCCIterator.h" +#include "Support/SCCIterator.h" namespace { struct CFGSCC : public FunctionPass { @@ -57,8 +58,8 @@ namespace { bool CFGSCC::runOnFunction(Function &F) { unsigned sccNum = 0; std::cout << "SCCs for Function " << F.getName() << " in PostOrder:"; - for (TarjanSCC_iterator SCCI = tarj_begin(&F), - E = tarj_end(&F); SCCI != E; ++SCCI) { + for (scc_iterator SCCI = scc_begin(&F), + E = scc_end(&F); SCCI != E; ++SCCI) { std::vector &nextSCC = *SCCI; std::cout << "\nSCC #" << ++sccNum << " : "; for (std::vector::const_iterator I = nextSCC.begin(), @@ -78,8 +79,8 @@ bool CallGraphSCC::run(Module &M) { CallGraphNode* rootNode = getAnalysis().getRoot(); unsigned sccNum = 0; std::cout << "SCCs for the program in PostOrder:"; - for (TarjanSCC_iterator SCCI = tarj_begin(rootNode), - E = tarj_end(rootNode); SCCI != E; ++SCCI) { + for (scc_iterator SCCI = scc_begin(rootNode), + E = scc_end(rootNode); SCCI != E; ++SCCI) { const std::vector &nextSCC = *SCCI; std::cout << "\nSCC #" << ++sccNum << " : "; for (std::vector::const_iterator I = nextSCC.begin(), diff --git a/lib/Analysis/PrintSCC.cpp b/lib/Analysis/PrintSCC.cpp index 0fbc240188..dfb7420542 100644 --- a/lib/Analysis/PrintSCC.cpp +++ b/lib/Analysis/PrintSCC.cpp @@ -2,9 +2,10 @@ // // This file provides passes to print out SCCs in a CFG or a CallGraph. // Normally, you would not use these passes; instead, you would use the -// TarjanSCCIterator directly to enumerate SCCs and process them in some way. -// These passes serve three purposes: -// (1) As a reference for how to use the TarjanSCCIterator. +// scc_iterator directly to enumerate SCCs and process them in some way. These +// passes serve three purposes: +// +// (1) As a reference for how to use the scc_iterator. // (2) To print out the SCCs for a CFG or a CallGraph: // analyze -cfgscc to print the SCCs in each CFG of a module. // analyze -cfgscc -stats to print the #SCCs and the maximum SCC size. @@ -13,7 +14,7 @@ // and similarly: // analyze -callscc [-stats] [-debug] to print SCCs in the CallGraph // -// (3) To test the TarjanSCCIterator. +// (3) To test the scc_iterator. // //===----------------------------------------------------------------------===// @@ -21,7 +22,7 @@ #include "llvm/Module.h" #include "llvm/Analysis/CallGraph.h" #include "llvm/Support/CFG.h" -#include "Support/TarjanSCCIterator.h" +#include "Support/SCCIterator.h" namespace { struct CFGSCC : public FunctionPass { @@ -57,8 +58,8 @@ namespace { bool CFGSCC::runOnFunction(Function &F) { unsigned sccNum = 0; std::cout << "SCCs for Function " << F.getName() << " in PostOrder:"; - for (TarjanSCC_iterator SCCI = tarj_begin(&F), - E = tarj_end(&F); SCCI != E; ++SCCI) { + for (scc_iterator SCCI = scc_begin(&F), + E = scc_end(&F); SCCI != E; ++SCCI) { std::vector &nextSCC = *SCCI; std::cout << "\nSCC #" << ++sccNum << " : "; for (std::vector::const_iterator I = nextSCC.begin(), @@ -78,8 +79,8 @@ bool CallGraphSCC::run(Module &M) { CallGraphNode* rootNode = getAnalysis().getRoot(); unsigned sccNum = 0; std::cout << "SCCs for the program in PostOrder:"; - for (TarjanSCC_iterator SCCI = tarj_begin(rootNode), - E = tarj_end(rootNode); SCCI != E; ++SCCI) { + for (scc_iterator SCCI = scc_begin(rootNode), + E = scc_end(rootNode); SCCI != E; ++SCCI) { const std::vector &nextSCC = *SCCI; std::cout << "\nSCC #" << ++sccNum << " : "; for (std::vector::const_iterator I = nextSCC.begin(), diff --git a/tools/analyze/PrintSCC.cpp b/tools/analyze/PrintSCC.cpp index 0fbc240188..dfb7420542 100644 --- a/tools/analyze/PrintSCC.cpp +++ b/tools/analyze/PrintSCC.cpp @@ -2,9 +2,10 @@ // // This file provides passes to print out SCCs in a CFG or a CallGraph. // Normally, you would not use these passes; instead, you would use the -// TarjanSCCIterator directly to enumerate SCCs and process them in some way. -// These passes serve three purposes: -// (1) As a reference for how to use the TarjanSCCIterator. +// scc_iterator directly to enumerate SCCs and process them in some way. These +// passes serve three purposes: +// +// (1) As a reference for how to use the scc_iterator. // (2) To print out the SCCs for a CFG or a CallGraph: // analyze -cfgscc to print the SCCs in each CFG of a module. // analyze -cfgscc -stats to print the #SCCs and the maximum SCC size. @@ -13,7 +14,7 @@ // and similarly: // analyze -callscc [-stats] [-debug] to print SCCs in the CallGraph // -// (3) To test the TarjanSCCIterator. +// (3) To test the scc_iterator. // //===----------------------------------------------------------------------===// @@ -21,7 +22,7 @@ #include "llvm/Module.h" #include "llvm/Analysis/CallGraph.h" #include "llvm/Support/CFG.h" -#include "Support/TarjanSCCIterator.h" +#include "Support/SCCIterator.h" namespace { struct CFGSCC : public FunctionPass { @@ -57,8 +58,8 @@ namespace { bool CFGSCC::runOnFunction(Function &F) { unsigned sccNum = 0; std::cout << "SCCs for Function " << F.getName() << " in PostOrder:"; - for (TarjanSCC_iterator SCCI = tarj_begin(&F), - E = tarj_end(&F); SCCI != E; ++SCCI) { + for (scc_iterator SCCI = scc_begin(&F), + E = scc_end(&F); SCCI != E; ++SCCI) { std::vector &nextSCC = *SCCI; std::cout << "\nSCC #" << ++sccNum << " : "; for (std::vector::const_iterator I = nextSCC.begin(), @@ -78,8 +79,8 @@ bool CallGraphSCC::run(Module &M) { CallGraphNode* rootNode = getAnalysis().getRoot(); unsigned sccNum = 0; std::cout << "SCCs for the program in PostOrder:"; - for (TarjanSCC_iterator SCCI = tarj_begin(rootNode), - E = tarj_end(rootNode); SCCI != E; ++SCCI) { + for (scc_iterator SCCI = scc_begin(rootNode), + E = scc_end(rootNode); SCCI != E; ++SCCI) { const std::vector &nextSCC = *SCCI; std::cout << "\nSCC #" << ++sccNum << " : "; for (std::vector::const_iterator I = nextSCC.begin(), diff --git a/tools/opt/PrintSCC.cpp b/tools/opt/PrintSCC.cpp index 0fbc240188..dfb7420542 100644 --- a/tools/opt/PrintSCC.cpp +++ b/tools/opt/PrintSCC.cpp @@ -2,9 +2,10 @@ // // This file provides passes to print out SCCs in a CFG or a CallGraph. // Normally, you would not use these passes; instead, you would use the -// TarjanSCCIterator directly to enumerate SCCs and process them in some way. -// These passes serve three purposes: -// (1) As a reference for how to use the TarjanSCCIterator. +// scc_iterator directly to enumerate SCCs and process them in some way. These +// passes serve three purposes: +// +// (1) As a reference for how to use the scc_iterator. // (2) To print out the SCCs for a CFG or a CallGraph: // analyze -cfgscc to print the SCCs in each CFG of a module. // analyze -cfgscc -stats to print the #SCCs and the maximum SCC size. @@ -13,7 +14,7 @@ // and similarly: // analyze -callscc [-stats] [-debug] to print SCCs in the CallGraph // -// (3) To test the TarjanSCCIterator. +// (3) To test the scc_iterator. // //===----------------------------------------------------------------------===// @@ -21,7 +22,7 @@ #include "llvm/Module.h" #include "llvm/Analysis/CallGraph.h" #include "llvm/Support/CFG.h" -#include "Support/TarjanSCCIterator.h" +#include "Support/SCCIterator.h" namespace { struct CFGSCC : public FunctionPass { @@ -57,8 +58,8 @@ namespace { bool CFGSCC::runOnFunction(Function &F) { unsigned sccNum = 0; std::cout << "SCCs for Function " << F.getName() << " in PostOrder:"; - for (TarjanSCC_iterator SCCI = tarj_begin(&F), - E = tarj_end(&F); SCCI != E; ++SCCI) { + for (scc_iterator SCCI = scc_begin(&F), + E = scc_end(&F); SCCI != E; ++SCCI) { std::vector &nextSCC = *SCCI; std::cout << "\nSCC #" << ++sccNum << " : "; for (std::vector::const_iterator I = nextSCC.begin(), @@ -78,8 +79,8 @@ bool CallGraphSCC::run(Module &M) { CallGraphNode* rootNode = getAnalysis().getRoot(); unsigned sccNum = 0; std::cout << "SCCs for the program in PostOrder:"; - for (TarjanSCC_iterator SCCI = tarj_begin(rootNode), - E = tarj_end(rootNode); SCCI != E; ++SCCI) { + for (scc_iterator SCCI = scc_begin(rootNode), + E = scc_end(rootNode); SCCI != E; ++SCCI) { const std::vector &nextSCC = *SCCI; std::cout << "\nSCC #" << ++sccNum << " : "; for (std::vector::const_iterator I = nextSCC.begin(), -- cgit v1.2.3