rusyaev-roman created this revision.
Herald added subscribers: mtrofin, carlosgalvezp, ormris, wenlei, okura,
jdoerfert, bmahjour, kuter, arphaman, rogfer01, hiraditya.
Herald added a project: All.
rusyaev-roman requested review of this revision.
Herald added a reviewer: jdoerfert.
Herald added a reviewer: sstefan1.
Herald added subscribers: cfe-commits, llvm-commits, vkmr.
Herald added projects: LLVM, clang-tools-extra.
As of C++17, for "range-based for loop" the types of the begin-expr and the
end-expr do not have to be the same,
and in fact the type of the end-expr does not have to be an iterator. This
makes it possible to delimit
a range by a predicate for graph traversal iterators. To be more specific, it's
not necessary to comapre
two containers in order to check that an iterator is the end iterator.
For more information see
https://en.cppreference.com/w/cpp/language/range-for#Notes
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D131448
Files:
clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp
llvm/include/llvm/ADT/BreadthFirstIterator.h
llvm/include/llvm/ADT/DepthFirstIterator.h
llvm/include/llvm/ADT/PostOrderIterator.h
llvm/include/llvm/ADT/SCCIterator.h
llvm/include/llvm/ADT/iterator_range.h
llvm/lib/Analysis/BlockFrequencyInfoImpl.cpp
llvm/lib/Analysis/BranchProbabilityInfo.cpp
llvm/lib/Analysis/CFGPrinter.cpp
llvm/lib/Analysis/DDG.cpp
llvm/lib/Analysis/DependenceGraphBuilder.cpp
llvm/lib/Analysis/GlobalsModRef.cpp
llvm/lib/Analysis/LoopCacheAnalysis.cpp
llvm/lib/Analysis/LoopNestAnalysis.cpp
llvm/lib/Analysis/MLInlineAdvisor.cpp
llvm/lib/Analysis/SyntheticCountsUtils.cpp
llvm/lib/IR/ModuleSummaryIndex.cpp
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
llvm/lib/Transforms/IPO/FunctionAttrs.cpp
llvm/lib/Transforms/IPO/SampleProfile.cpp
llvm/lib/Transforms/Scalar/StructurizeCFG.cpp
llvm/lib/Transforms/Utils/FixIrreducible.cpp
llvm/tools/llvm-profgen/CSPreInliner.cpp
llvm/tools/opt/PrintSCC.cpp
llvm/unittests/ADT/DirectedGraphTest.cpp
llvm/unittests/Transforms/Vectorize/VPlanTest.cpp
Index: llvm/unittests/Transforms/Vectorize/VPlanTest.cpp
===================================================================
--- llvm/unittests/Transforms/Vectorize/VPlanTest.cpp
+++ llvm/unittests/Transforms/Vectorize/VPlanTest.cpp
@@ -428,7 +428,8 @@
// Post-order.
FromIterator.clear();
- copy(post_order(Start), std::back_inserter(FromIterator));
+ copy(make_range(po_begin(Start), po_end(Start)),
+ std::back_inserter(FromIterator));
EXPECT_EQ(8u, FromIterator.size());
EXPECT_EQ(R2BB2, FromIterator[0]);
EXPECT_EQ(R2BB1, FromIterator[1]);
@@ -630,7 +631,8 @@
// Post-order.
FromIterator.clear();
- copy(post_order(Start), std::back_inserter(FromIterator));
+ copy(make_range(po_begin(Start), po_end(Start)),
+ std::back_inserter(FromIterator));
EXPECT_EQ(7u, FromIterator.size());
EXPECT_EQ(VPBB2, FromIterator[0]);
EXPECT_EQ(R3BB1, FromIterator[1]);
@@ -643,7 +645,8 @@
// Post-order, const VPRegionBlocks only.
VPBlockRecursiveTraversalWrapper<const VPBlockBase *> StartConst(VPBB1);
SmallVector<const VPRegionBlock *> FromIteratorVPRegion(
- VPBlockUtils::blocksOnly<const VPRegionBlock>(post_order(StartConst)));
+ VPBlockUtils::blocksOnly<const VPRegionBlock>(
+ make_range(po_begin(StartConst), po_end(StartConst))));
EXPECT_EQ(3u, FromIteratorVPRegion.size());
EXPECT_EQ(R3, FromIteratorVPRegion[0]);
EXPECT_EQ(R2, FromIteratorVPRegion[1]);
@@ -651,7 +654,8 @@
// Post-order, VPBasicBlocks only.
FromIterator.clear();
- copy(VPBlockUtils::blocksOnly<VPBasicBlock>(post_order(Start)),
+ copy(VPBlockUtils::blocksOnly<VPBasicBlock>(
+ make_range(po_begin(Start), po_end(Start))),
std::back_inserter(FromIterator));
EXPECT_EQ(FromIterator.size(), 4u);
EXPECT_EQ(VPBB2, FromIterator[0]);
Index: llvm/unittests/ADT/DirectedGraphTest.cpp
===================================================================
--- llvm/unittests/ADT/DirectedGraphTest.cpp
+++ llvm/unittests/ADT/DirectedGraphTest.cpp
@@ -270,8 +270,8 @@
// 2. {N4}
using NodeListTy = SmallPtrSet<DGTestNode *, 3>;
SmallVector<NodeListTy, 4> ListOfSCCs;
- for (auto &SCC : make_range(scc_begin(&DG), scc_end(&DG)))
- ListOfSCCs.push_back(NodeListTy(SCC.begin(), SCC.end()));
+ for (auto SCC : scc_traversal(&DG))
+ ListOfSCCs.push_back(NodeListTy(SCC->begin(), SCC->end()));
EXPECT_TRUE(ListOfSCCs.size() == 2);
Index: llvm/tools/opt/PrintSCC.cpp
===================================================================
--- llvm/tools/opt/PrintSCC.cpp
+++ llvm/tools/opt/PrintSCC.cpp
@@ -73,14 +73,13 @@
bool CFGSCC::runOnFunction(Function &F) {
unsigned sccNum = 0;
errs() << "SCCs for Function " << F.getName() << " in PostOrder:";
- for (scc_iterator<Function*> SCCI = scc_begin(&F); !SCCI.isAtEnd(); ++SCCI) {
- const std::vector<BasicBlock *> &nextSCC = *SCCI;
+ for (auto SCC : scc_traversal(&F)) {
errs() << "\nSCC #" << ++sccNum << " : ";
- for (BasicBlock *BB : nextSCC) {
+ for (BasicBlock *BB : *SCC) {
BB->printAsOperand(errs(), false);
errs() << ", ";
}
- if (nextSCC.size() == 1 && SCCI.hasCycle())
+ if (SCC->size() == 1 && SCC.hasCycle())
errs() << " (Has self-loop).";
}
errs() << "\n";
@@ -94,15 +93,14 @@
CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
unsigned sccNum = 0;
errs() << "SCCs for the program in PostOrder:";
- for (scc_iterator<CallGraph*> SCCI = scc_begin(&CG); !SCCI.isAtEnd();
- ++SCCI) {
- const std::vector<CallGraphNode*> &nextSCC = *SCCI;
+ for (auto SCC : scc_traversal(&CG)) {
errs() << "\nSCC #" << ++sccNum << " : ";
- for (std::vector<CallGraphNode*>::const_iterator I = nextSCC.begin(),
- E = nextSCC.end(); I != E; ++I)
- errs() << ((*I)->getFunction() ? (*I)->getFunction()->getName()
- : "external node") << ", ";
- if (nextSCC.size() == 1 && SCCI.hasCycle())
+ for (auto *N : *SCC)
+ errs() << (N->getFunction() ? N->getFunction()->getName()
+ : "external node")
+ << ", ";
+
+ if (SCC->size() == 1 && SCC.hasCycle())
errs() << " (Has self-loop).";
}
errs() << "\n";
Index: llvm/tools/llvm-profgen/CSPreInliner.cpp
===================================================================
--- llvm/tools/llvm-profgen/CSPreInliner.cpp
+++ llvm/tools/llvm-profgen/CSPreInliner.cpp
@@ -78,19 +78,17 @@
// Now that we have a profiled call graph, construct top-down order
// by building up SCC and reversing SCC order.
- scc_iterator<ProfiledCallGraph *> I = scc_begin(&ProfiledCG);
- while (!I.isAtEnd()) {
- auto Range = *I;
+ for (auto SCC : scc_traversal(&ProfiledCG)) {
+ auto Range = *SCC;
if (SortProfiledSCC) {
// Sort nodes in one SCC based on callsite hotness.
- scc_member_iterator<ProfiledCallGraph *> SI(*I);
+ scc_member_iterator<ProfiledCallGraph *> SI(*SCC);
Range = *SI;
}
for (auto *Node : Range) {
if (Node != ProfiledCG.getEntryNode())
Order.push_back(Node->Name);
}
- ++I;
}
std::reverse(Order.begin(), Order.end());
Index: llvm/lib/Transforms/Utils/FixIrreducible.cpp
===================================================================
--- llvm/lib/Transforms/Utils/FixIrreducible.cpp
+++ llvm/lib/Transforms/Utils/FixIrreducible.cpp
@@ -269,7 +269,7 @@
template <class Graph>
static bool makeReducible(LoopInfo &LI, DominatorTree &DT, Graph &&G) {
bool Changed = false;
- for (auto Scc = scc_begin(G); !Scc.isAtEnd(); ++Scc) {
+ for (auto Scc : scc_traversal(G)) {
if (Scc->size() < 2)
continue;
SetVector<BasicBlock *> Blocks;
Index: llvm/lib/Transforms/Scalar/StructurizeCFG.cpp
===================================================================
--- llvm/lib/Transforms/Scalar/StructurizeCFG.cpp
+++ llvm/lib/Transforms/Scalar/StructurizeCFG.cpp
@@ -385,7 +385,7 @@
scc_iterator<SubGraphTraits::NodeRef, SubGraphTraits>::begin(
EntryNode);
!SCCI.isAtEnd(); ++SCCI) {
- auto &SCC = *SCCI;
+ auto &SCC = **SCCI;
// An SCC up to the size of 2, can be reduced to an entry (the last node),
// and a possible additional node. Therefore, it is already in order, and
Index: llvm/lib/Transforms/IPO/SampleProfile.cpp
===================================================================
--- llvm/lib/Transforms/IPO/SampleProfile.cpp
+++ llvm/lib/Transforms/IPO/SampleProfile.cpp
@@ -1878,8 +1878,7 @@
// context in the profile.
std::unique_ptr<ProfiledCallGraph> ProfiledCG = buildProfiledCallGraph(*CG);
- scc_iterator<ProfiledCallGraph *> CGI = scc_begin(ProfiledCG.get());
- while (!CGI.isAtEnd()) {
+ for (auto CGI : scc_traversal(ProfiledCG.get())) {
auto Range = *CGI;
if (SortProfiledSCC) {
// Sort nodes in one SCC based on callsite hotness.
@@ -1891,17 +1890,14 @@
if (F && !F->isDeclaration() && F->hasFnAttribute("use-sample-profile"))
FunctionOrderList.push_back(F);
}
- ++CGI;
}
} else {
- scc_iterator<CallGraph *> CGI = scc_begin(CG);
- while (!CGI.isAtEnd()) {
+ for (auto CGI : scc_traversal(CG)) {
for (CallGraphNode *Node : *CGI) {
auto *F = Node->getFunction();
if (F && !F->isDeclaration() && F->hasFnAttribute("use-sample-profile"))
FunctionOrderList.push_back(F);
}
- ++CGI;
}
}
Index: llvm/lib/Transforms/IPO/FunctionAttrs.cpp
===================================================================
--- llvm/lib/Transforms/IPO/FunctionAttrs.cpp
+++ llvm/lib/Transforms/IPO/FunctionAttrs.cpp
@@ -531,9 +531,8 @@
};
// Call propagation functions on each SCC in the Index
- for (scc_iterator<ModuleSummaryIndex *> I = scc_begin(&Index); !I.isAtEnd();
- ++I) {
- std::vector<ValueInfo> Nodes(*I);
+ for (auto SCC : scc_traversal(&Index)) {
+ std::vector<ValueInfo> Nodes(*SCC);
PropagateAttributes(Nodes);
}
return Changed;
@@ -990,8 +989,8 @@
// made. If the definition doesn't have a 'nocapture' attribute by now, it
// captures.
- for (scc_iterator<ArgumentGraph *> I = scc_begin(&AG); !I.isAtEnd(); ++I) {
- const std::vector<ArgumentGraphNode *> &ArgumentSCC = *I;
+ for (auto SCC : scc_traversal(&AG)) {
+ const std::vector<ArgumentGraphNode *> &ArgumentSCC = SCC;
if (ArgumentSCC.size() == 1) {
if (!ArgumentSCC[0]->Definition)
continue; // synthetic root node
@@ -2035,11 +2034,11 @@
// synthesizing norecurse and so we can only save the singular SCCs as SCCs
// with multiple functions in them will clearly be recursive.
SmallVector<Function *, 16> Worklist;
- for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
- if (I->size() != 1)
+ for (auto SCC : scc_traversal(&CG)) {
+ if (SCC->size() != 1)
continue;
- Function *F = I->front()->getFunction();
+ Function *F = SCC->front()->getFunction();
if (F && !F->isDeclaration() && !F->doesNotRecurse() &&
F->hasInternalLinkage())
Worklist.push_back(F);
Index: llvm/lib/Transforms/IPO/AttributorAttributes.cpp
===================================================================
--- llvm/lib/Transforms/IPO/AttributorAttributes.cpp
+++ llvm/lib/Transforms/IPO/AttributorAttributes.cpp
@@ -2847,8 +2847,8 @@
// We use scc_iterator which uses Tarjan algorithm to find all the maximal
// SCCs.To detect if there's a cycle, we only need to find the maximal ones.
if (!SE || !LI) {
- for (scc_iterator<Function *> SCCI = scc_begin(&F); !SCCI.isAtEnd(); ++SCCI)
- if (SCCI.hasCycle())
+ for (auto SCC : scc_traversal(&F))
+ if (SCC.hasCycle())
return true;
return false;
}
Index: llvm/lib/IR/ModuleSummaryIndex.cpp
===================================================================
--- llvm/lib/IR/ModuleSummaryIndex.cpp
+++ llvm/lib/IR/ModuleSummaryIndex.cpp
@@ -353,17 +353,15 @@
// then delete this function and update its tests
LLVM_DUMP_METHOD
void ModuleSummaryIndex::dumpSCCs(raw_ostream &O) {
- for (scc_iterator<ModuleSummaryIndex *> I =
- scc_begin<ModuleSummaryIndex *>(this);
- !I.isAtEnd(); ++I) {
- O << "SCC (" << utostr(I->size()) << " node" << (I->size() == 1 ? "" : "s")
- << ") {\n";
- for (const ValueInfo &V : *I) {
+ for (auto SCC : scc_traversal(this)) {
+ O << "SCC (" << utostr(SCC->size()) << " node"
+ << (SCC->size() == 1 ? "" : "s") << ") {\n";
+ for (const ValueInfo &V : *SCC) {
FunctionSummary *F = nullptr;
if (V.getSummaryList().size())
F = cast<FunctionSummary>(V.getSummaryList().front().get());
O << " " << (F == nullptr ? "External" : "") << " " << utostr(V.getGUID())
- << (I.hasCycle() ? " (has cycle)" : "") << "\n";
+ << (SCC.hasCycle() ? " (has cycle)" : "") << "\n";
}
O << "}\n";
}
Index: llvm/lib/Analysis/SyntheticCountsUtils.cpp
===================================================================
--- llvm/lib/Analysis/SyntheticCountsUtils.cpp
+++ llvm/lib/Analysis/SyntheticCountsUtils.cpp
@@ -86,8 +86,8 @@
std::vector<SccTy> SCCs;
// Collect all the SCCs.
- for (auto I = scc_begin(CG); !I.isAtEnd(); ++I)
- SCCs.push_back(*I);
+ for (auto SCC : scc_traversal(CG))
+ SCCs.push_back(SCC);
// The callgraph-scc needs to be visited in top-down order for propagation.
// The scc iterator returns the scc in bottom-up order, so reverse the SCCs
Index: llvm/lib/Analysis/MLInlineAdvisor.cpp
===================================================================
--- llvm/lib/Analysis/MLInlineAdvisor.cpp
+++ llvm/lib/Analysis/MLInlineAdvisor.cpp
@@ -102,8 +102,8 @@
// heuristic's decisions - and, thus, equally important for training for
// improvement.
CallGraph CGraph(M);
- for (auto I = scc_begin(&CGraph); !I.isAtEnd(); ++I) {
- const std::vector<CallGraphNode *> &CGNodes = *I;
+ for (auto SCC : scc_traversal(&CGraph)) {
+ const std::vector<CallGraphNode *> &CGNodes = SCC;
unsigned Level = 0;
for (auto *CGNode : CGNodes) {
Function *F = CGNode->getFunction();
Index: llvm/lib/Analysis/LoopNestAnalysis.cpp
===================================================================
--- llvm/lib/Analysis/LoopNestAnalysis.cpp
+++ llvm/lib/Analysis/LoopNestAnalysis.cpp
@@ -41,7 +41,7 @@
LoopNest::LoopNest(Loop &Root, ScalarEvolution &SE)
: MaxPerfectDepth(getMaxPerfectDepth(Root, SE)) {
- append_range(Loops, breadth_first(&Root));
+ append_range(Loops, make_range(bf_begin(&Root), bf_end(&Root)));
}
std::unique_ptr<LoopNest> LoopNest::getLoopNest(Loop &Root,
Index: llvm/lib/Analysis/LoopCacheAnalysis.cpp
===================================================================
--- llvm/lib/Analysis/LoopCacheAnalysis.cpp
+++ llvm/lib/Analysis/LoopCacheAnalysis.cpp
@@ -581,7 +581,7 @@
}
LoopVectorTy Loops;
- append_range(Loops, breadth_first(&Root));
+ append_range(Loops, make_range(bf_begin(&Root), bf_end(&Root)));
if (!getInnerMostLoop(Loops)) {
LLVM_DEBUG(dbgs() << "Cannot compute cache cost of loop nest with more "
Index: llvm/lib/Analysis/GlobalsModRef.cpp
===================================================================
--- llvm/lib/Analysis/GlobalsModRef.cpp
+++ llvm/lib/Analysis/GlobalsModRef.cpp
@@ -452,11 +452,10 @@
// We do a bottom-up SCC traversal of the call graph. In other words, we
// visit all callees before callers (leaf-first).
unsigned SCCID = 0;
- for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
- const std::vector<CallGraphNode *> &SCC = *I;
- assert(!SCC.empty() && "SCC with no functions?");
+ for (auto SCC : scc_traversal(&CG)) {
+ assert(!SCC->empty() && "SCC with no functions?");
- for (auto *CGN : SCC)
+ for (auto *CGN : *SCC)
if (Function *F = CGN->getFunction())
FunctionToSCCMap[F] = SCCID;
++SCCID;
@@ -470,8 +469,8 @@
void GlobalsAAResult::AnalyzeCallGraph(CallGraph &CG, Module &M) {
// We do a bottom-up SCC traversal of the call graph. In other words, we
// visit all callees before callers (leaf-first).
- for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
- const std::vector<CallGraphNode *> &SCC = *I;
+ for (auto I : scc_traversal(&CG)) {
+ const std::vector<CallGraphNode *> &SCC = I;
assert(!SCC.empty() && "SCC with no functions?");
Function *F = SCC[0]->getFunction();
Index: llvm/lib/Analysis/DependenceGraphBuilder.cpp
===================================================================
--- llvm/lib/Analysis/DependenceGraphBuilder.cpp
+++ llvm/lib/Analysis/DependenceGraphBuilder.cpp
@@ -110,9 +110,9 @@
// list of nodes in an SCC. Note: trivial SCCs containing a single node are
// ignored.
SmallVector<NodeListType, 4> ListOfSCCs;
- for (auto &SCC : make_range(scc_begin(&Graph), scc_end(&Graph))) {
- if (SCC.size() > 1)
- ListOfSCCs.emplace_back(SCC.begin(), SCC.end());
+ for (auto SCC : scc_traversal(&Graph)) {
+ if (SCC->size() > 1)
+ ListOfSCCs.emplace_back(SCC->begin(), SCC->end());
}
for (NodeListType &NL : ListOfSCCs) {
Index: llvm/lib/Analysis/DDG.cpp
===================================================================
--- llvm/lib/Analysis/DDG.cpp
+++ llvm/lib/Analysis/DDG.cpp
@@ -188,8 +188,8 @@
// Put the basic blocks in program order for correct dependence
// directions.
BasicBlockListType BBList;
- for (const auto &SCC : make_range(scc_begin(&F), scc_end(&F)))
- append_range(BBList, SCC);
+ for (auto SCC : scc_traversal(&F))
+ append_range(BBList, *SCC);
std::reverse(BBList.begin(), BBList.end());
DDGBuilder(*this, D, BBList).populate();
}
Index: llvm/lib/Analysis/CFGPrinter.cpp
===================================================================
--- llvm/lib/Analysis/CFGPrinter.cpp
+++ llvm/lib/Analysis/CFGPrinter.cpp
@@ -311,7 +311,8 @@
};
/// The post order traversal iteration is done to know the status of
/// isOnDeoptOrUnreachablePath for all the successors on the current BB.
- llvm::for_each(post_order(&F->getEntryBlock()), evaluateBB);
+ for (auto &BB : post_order(&F->getEntryBlock()))
+ evaluateBB(BB);
}
bool DOTGraphTraits<DOTFuncInfo *>::isNodeHidden(const BasicBlock *Node,
Index: llvm/lib/Analysis/BranchProbabilityInfo.cpp
===================================================================
--- llvm/lib/Analysis/BranchProbabilityInfo.cpp
+++ llvm/lib/Analysis/BranchProbabilityInfo.cpp
@@ -219,16 +219,15 @@
// FIXME: We could only calculate this if the CFG is known to be irreducible
// (perhaps cache this info in LoopInfo if we can easily calculate it there?).
int SccNum = 0;
- for (scc_iterator<const Function *> It = scc_begin(&F); !It.isAtEnd();
- ++It, ++SccNum) {
+ for (auto SCC : scc_traversal(&F)) {
+ ++SccNum;
// Ignore single-block SCCs since they either aren't loops or LoopInfo will
// catch them.
- const std::vector<const BasicBlock *> &Scc = *It;
- if (Scc.size() == 1)
+ if (SCC->size() == 1)
continue;
LLVM_DEBUG(dbgs() << "BPI: SCC " << SccNum << ":");
- for (const auto *BB : Scc) {
+ for (const auto *BB : *SCC) {
LLVM_DEBUG(dbgs() << " " << BB->getName());
SccNums[BB] = SccNum;
calculateSccBlockType(BB, SccNum);
Index: llvm/lib/Analysis/BlockFrequencyInfoImpl.cpp
===================================================================
--- llvm/lib/Analysis/BlockFrequencyInfoImpl.cpp
+++ llvm/lib/Analysis/BlockFrequencyInfoImpl.cpp
@@ -807,12 +807,12 @@
assert((OuterLoop == nullptr) == (Insert == Loops.begin()));
auto Prev = OuterLoop ? std::prev(Insert) : Loops.end();
- for (auto I = scc_begin(G); !I.isAtEnd(); ++I) {
- if (I->size() < 2)
+ for (auto SCC : scc_traversal(G)) {
+ if (SCC->size() < 2)
continue;
// Translate the SCC into RPO.
- createIrreducibleLoop(*this, G, OuterLoop, Insert, *I);
+ createIrreducibleLoop(*this, G, OuterLoop, Insert, SCC);
}
if (OuterLoop)
Index: llvm/include/llvm/ADT/iterator_range.h
===================================================================
--- llvm/include/llvm/ADT/iterator_range.h
+++ llvm/include/llvm/ADT/iterator_range.h
@@ -46,6 +46,25 @@
bool empty() const { return begin_iterator == end_iterator; }
};
+/// As of C++17, the types of the begin-expr and the end-expr do not have to be
+/// the same in 'based-range for loop'. This class represents a tag that should
+/// be returned from the 'end' member function of an iterator.
+class iterator_sentinel {};
+
+/// A range adaptor for an iterator that wants iterator_sentinel as the
+/// end iterator. The iterator should provide operator!=(iterator_sentinel)
+/// function.
+template <typename IteratorT> class iterator_range_with_sentinel {
+ IteratorT begin_iterator;
+
+public:
+ explicit iterator_range_with_sentinel(IteratorT begin_iterator)
+ : begin_iterator(std::move(begin_iterator)) {}
+
+ IteratorT begin() const { return begin_iterator; }
+ iterator_sentinel end() const { return iterator_sentinel(); }
+};
+
/// Convenience function for iterating over sub-ranges.
///
/// This provides a bit of syntactic sugar to make using sub-ranges
@@ -58,6 +77,10 @@
return iterator_range<T>(std::move(p.first), std::move(p.second));
}
+template <typename T>
+iterator_range_with_sentinel<T> make_range_with_sentinel(T begin) {
+ return iterator_range_with_sentinel<T>(std::move(begin));
+}
}
#endif
Index: llvm/include/llvm/ADT/SCCIterator.h
===================================================================
--- llvm/include/llvm/ADT/SCCIterator.h
+++ llvm/include/llvm/ADT/SCCIterator.h
@@ -43,13 +43,12 @@
/// build up a vector of nodes in a particular SCC. Note that it is a forward
/// iterator and thus you cannot backtrack or re-visit nodes.
template <class GraphT, class GT = GraphTraits<GraphT>>
-class scc_iterator : public iterator_facade_base<
- scc_iterator<GraphT, GT>, std::forward_iterator_tag,
- const std::vector<typename GT::NodeRef>, ptrdiff_t> {
+class scc_iterator {
using NodeRef = typename GT::NodeRef;
using ChildItTy = typename GT::ChildIteratorType;
using SccTy = std::vector<NodeRef>;
- using reference = typename scc_iterator::reference;
+ using reference = const SccTy &;
+ using pointer = const SccTy *;
/// Element of VisitStack during DFS.
struct StackElement {
@@ -118,21 +117,58 @@
return VisitStack == x.VisitStack && CurrentSCC == x.CurrentSCC;
}
+ bool operator!=(const scc_iterator &x) const { return !(*this == x); }
+
+ bool operator==(iterator_sentinel) const { return isAtEnd(); }
+
+ bool operator!=(iterator_sentinel RHS) const { return !(*this == RHS); }
+
scc_iterator &operator++() {
GetNextSCC();
return *this;
}
- reference operator*() const {
+ /// A proxy object that is returned from scc_iterator operator* and operator->
+ /// member functions. It allows performing implicit conversion to SccTy and
+ /// provides operator* and operator-> member functions to access underlying
+ /// object with SccTy type. This class is necessary to provide additional
+ /// functionality (e.g. hasCycle) that cannot be provided by SccTy object.
+ class SCCProxy {
+ friend scc_iterator;
+
+ reference SCC;
+
+ SCCProxy(reference SCC) : SCC(SCC) {}
+
+ public:
+ operator reference() const { return SCC; }
+
+ reference operator*() const { return SCC; }
+ pointer operator->() const { return &SCC; }
+
+ /// Test if the current SCC has a cycle.
+ ///
+ /// If the SCC has more than one node, this is trivially true. If not, it
+ /// may still contain a cycle if the node has an edge back to itself.
+ bool hasCycle() const {
+ assert(!SCC.empty() && "Dereferencing END SCC iterator!");
+ if (SCC.size() > 1)
+ return true;
+ NodeRef N = SCC.front();
+ for (ChildItTy CI = GT::child_begin(N), CE = GT::child_end(N); CI != CE;
+ ++CI)
+ if (*CI == N)
+ return true;
+ return false;
+ }
+ };
+
+ SCCProxy operator*() const {
assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
return CurrentSCC;
}
- /// Test if the current SCC has a cycle.
- ///
- /// If the SCC has more than one node, this is trivially true. If not, it may
- /// still contain a cycle if the node has an edge back to itself.
- bool hasCycle() const;
+ SCCProxy operator->() const { return operator*(); }
/// This informs the \c scc_iterator that the specified \c Old node
/// has been deleted, and \c New is to be used in its place.
@@ -215,19 +251,6 @@
}
}
-template <class GraphT, class GT>
-bool scc_iterator<GraphT, GT>::hasCycle() const {
- assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
- if (CurrentSCC.size() > 1)
- return true;
- NodeRef N = CurrentSCC.front();
- for (ChildItTy CI = GT::child_begin(N), CE = GT::child_end(N); CI != CE;
- ++CI)
- if (*CI == N)
- return true;
- return false;
- }
-
/// Construct the begin iterator for a deduced graph type T.
template <class T> scc_iterator<T> scc_begin(const T &G) {
return scc_iterator<T>::begin(G);
@@ -238,6 +261,11 @@
return scc_iterator<T>::end(G);
}
+template <typename T>
+iterator_range_with_sentinel<scc_iterator<T>> scc_traversal(const T &G) {
+ return make_range_with_sentinel(scc_begin(G));
+}
+
/// Sort the nodes of a directed SCC in the decreasing order of the edge
/// weights. The instantiating GraphT type should have weighted edge type
/// declared in its graph traits in order to use this iterator.
Index: llvm/include/llvm/ADT/PostOrderIterator.h
===================================================================
--- llvm/include/llvm/ADT/PostOrderIterator.h
+++ llvm/include/llvm/ADT/PostOrderIterator.h
@@ -156,6 +156,9 @@
}
bool operator!=(const po_iterator &x) const { return !(*this == x); }
+ bool operator==(iterator_sentinel) const { return VisitStack.empty(); }
+ bool operator!=(iterator_sentinel x) const { return !(*this == x); }
+
const NodeRef &operator*() const { return VisitStack.back().first; }
// This is a nonstandard operator-> that dereferences the pointer an extra
@@ -186,8 +189,9 @@
template <class T>
po_iterator<T> po_end (const T &G) { return po_iterator<T>::end(G); }
-template <class T> iterator_range<po_iterator<T>> post_order(const T &G) {
- return make_range(po_begin(G), po_end(G));
+template <typename T>
+iterator_range_with_sentinel<po_iterator<T>> post_order(const T &G) {
+ return make_range_with_sentinel(po_begin(G));
}
// Provide global definitions of external postorder iterators...
@@ -208,8 +212,9 @@
}
template <class T, class SetType>
-iterator_range<po_ext_iterator<T, SetType>> post_order_ext(const T &G, SetType &S) {
- return make_range(po_ext_begin(G, S), po_ext_end(G, S));
+iterator_range_with_sentinel<po_ext_iterator<T, SetType>>
+post_order_ext(const T &G, SetType &S) {
+ return make_range_with_sentinel(po_ext_begin(G, S));
}
// Provide global definitions of inverse post order iterators...
@@ -231,8 +236,9 @@
}
template <class T>
-iterator_range<ipo_iterator<T>> inverse_post_order(const T &G) {
- return make_range(ipo_begin(G), ipo_end(G));
+iterator_range_with_sentinel<ipo_iterator<T>>
+inverse_post_order(const T &G) {
+ return make_range_with_sentinel(ipo_begin(G));
}
// Provide global definitions of external inverse postorder iterators...
@@ -255,9 +261,9 @@
}
template <class T, class SetType>
-iterator_range<ipo_ext_iterator<T, SetType>>
+iterator_range_with_sentinel<ipo_ext_iterator<T, SetType>>
inverse_post_order_ext(const T &G, SetType &S) {
- return make_range(ipo_ext_begin(G, S), ipo_ext_end(G, S));
+ return make_range_with_sentinel(ipo_ext_begin(G, S));
}
//===--------------------------------------------------------------------===//
Index: llvm/include/llvm/ADT/DepthFirstIterator.h
===================================================================
--- llvm/include/llvm/ADT/DepthFirstIterator.h
+++ llvm/include/llvm/ADT/DepthFirstIterator.h
@@ -166,6 +166,9 @@
}
bool operator!=(const df_iterator &x) const { return !(*this == x); }
+ bool operator==(iterator_sentinel) const { return VisitStack.empty(); }
+ bool operator!=(iterator_sentinel x) const { return !(*this == x); }
+
const NodeRef &operator*() const { return VisitStack.back().first; }
// This is a nonstandard operator-> that dereferences the pointer an extra
@@ -249,9 +252,9 @@
}
template <class T, class SetTy>
-iterator_range<df_ext_iterator<T, SetTy>> depth_first_ext(const T& G,
- SetTy &S) {
- return make_range(df_ext_begin(G, S), df_ext_end(G, S));
+iterator_range_with_sentinel<df_ext_iterator<T, SetTy>>
+depth_first_ext(const T &G, SetTy &S) {
+ return make_range_with_sentinel(df_ext_begin(G, S));
}
// Provide global definitions of inverse depth first iterators...
@@ -276,8 +279,9 @@
// Provide an accessor method to use them in range-based patterns.
template <class T>
-iterator_range<idf_iterator<T>> inverse_depth_first(const T& G) {
- return make_range(idf_begin(G), idf_end(G));
+iterator_range_with_sentinel<idf_iterator<T>>
+inverse_depth_first(const T &G) {
+ return make_range_with_sentinel(idf_begin(G));
}
// Provide global definitions of external inverse depth first iterators...
@@ -300,9 +304,9 @@
}
template <class T, class SetTy>
-iterator_range<idf_ext_iterator<T, SetTy>> inverse_depth_first_ext(const T& G,
- SetTy &S) {
- return make_range(idf_ext_begin(G, S), idf_ext_end(G, S));
+iterator_range_with_sentinel<idf_ext_iterator<T, SetTy>>
+inverse_depth_first_ext(const T &G, SetTy &S) {
+ return make_range_with_sentinel(idf_ext_begin(G, S));
}
} // end namespace llvm
Index: llvm/include/llvm/ADT/BreadthFirstIterator.h
===================================================================
--- llvm/include/llvm/ADT/BreadthFirstIterator.h
+++ llvm/include/llvm/ADT/BreadthFirstIterator.h
@@ -22,6 +22,7 @@
#include "llvm/ADT/None.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/iterator.h"
#include "llvm/ADT/iterator_range.h"
#include <iterator>
#include <queue>
@@ -124,6 +125,10 @@
bool operator!=(const bf_iterator &RHS) const { return !(*this == RHS); }
+ bool operator==(iterator_sentinel) const { return VisitQueue.empty(); }
+
+ bool operator!=(iterator_sentinel RHS) const { return !(*this == RHS); }
+
const NodeRef &operator*() const { return VisitQueue.front()->first; }
// This is a nonstandard operator-> that dereferences the pointer an extra
@@ -155,8 +160,9 @@
}
// Provide an accessor method to use them in range-based patterns.
-template <class T> iterator_range<bf_iterator<T>> breadth_first(const T &G) {
- return make_range(bf_begin(G), bf_end(G));
+template <class T>
+iterator_range_with_sentinel<bf_iterator<T>> breadth_first(const T &G) {
+ return make_range_with_sentinel(bf_begin(G));
}
} // end namespace llvm
Index: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp
===================================================================
--- clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp
+++ clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp
@@ -261,12 +261,10 @@
// Look for cycles in call graph,
// by looking for Strongly Connected Components (SCC's)
- for (llvm::scc_iterator<CallGraph *> SCCI = llvm::scc_begin(&CG),
- SCCE = llvm::scc_end(&CG);
- SCCI != SCCE; ++SCCI) {
- if (!SCCI.hasCycle()) // We only care about cycles, not standalone nodes.
+ for (auto SCC : llvm::scc_traversal(&CG)) {
+ if (!SCC.hasCycle()) // We only care about cycles, not standalone nodes.
continue;
- handleSCC(*SCCI);
+ handleSCC(*SCC);
}
}
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
