rusyaev-roman updated this revision to Diff 451208.
rusyaev-roman added a comment.
Herald added subscribers: bzcheeseman, sdasgup3, wenzhicui, wrengr, cota,
teijeong, rdzhabarov, tatianashp, msifontes, jurahul, Kayjukh, grosul1,
Joonsoo, stephenneuendorffer, liufengdb, aartbik, mgester, arpith-jacob,
nicolasvasilache, antiagainst, shauheen, rriddle, mehdi_amini.
Herald added a reviewer: aartbik.
Herald added a project: MLIR.
Fix mlir build and rebase
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D131448/new/
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
mlir/lib/Analysis/CallGraph.cpp
Index: mlir/lib/Analysis/CallGraph.cpp
===================================================================
--- mlir/lib/Analysis/CallGraph.cpp
+++ mlir/lib/Analysis/CallGraph.cpp
@@ -215,9 +215,9 @@
os << "// -- SCCs --\n";
- for (auto &scc : make_range(llvm::scc_begin(this), llvm::scc_end(this))) {
+ for (auto scc : llvm::scc_traversal(this)) {
os << "// - SCC : \n";
- for (auto &node : scc) {
+ for (auto &node : *scc) {
os << "// -- Node :";
emitNodeName(node);
os << "\n";
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
@@ -42,14 +42,12 @@
/// This is implemented using Tarjan's DFS algorithm using an internal stack to
/// 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> {
+template <class GraphT, class GT = GraphTraits<GraphT>> 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 +116,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 +250,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 +260,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,8 @@
}
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 +260,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,8 @@
// 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 +303,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
