diff --git a/llvm/include/llvm/Analysis/LazyCallGraph.h b/llvm/include/llvm/Analysis/LazyCallGraph.h --- a/llvm/include/llvm/Analysis/LazyCallGraph.h +++ b/llvm/include/llvm/Analysis/LazyCallGraph.h @@ -441,17 +441,17 @@ // of enclosing namespaces for friend function declarations. friend raw_ostream &operator<<(raw_ostream &OS, const SCC &C) { OS << '('; - int i = 0; + int I = 0; for (LazyCallGraph::Node &N : C) { - if (i > 0) + if (I > 0) OS << ", "; // Elide the inner elements if there are too many. - if (i > 8) { + if (I > 8) { OS << "..., " << *C.Nodes.back(); break; } OS << N; - ++i; + ++I; } OS << ')'; return OS; @@ -563,17 +563,17 @@ // of enclosing namespaces for friend function declarations. friend raw_ostream &operator<<(raw_ostream &OS, const RefSCC &RC) { OS << '['; - int i = 0; + int I = 0; for (LazyCallGraph::SCC &C : RC) { - if (i > 0) + if (I > 0) OS << ", "; // Elide the inner elements if there are too many. - if (i > 4) { + if (I > 4) { OS << "..., " << *RC.SCCs.back(); break; } OS << C; - ++i; + ++I; } OS << ']'; return OS; @@ -1156,14 +1156,14 @@ /// Allocates an SCC and constructs it using the graph allocator. /// /// The arguments are forwarded to the constructor. - template SCC *createSCC(Ts &&... Args) { + template SCC *createSCC(Ts &&...Args) { return new (SCCBPA.Allocate()) SCC(std::forward(Args)...); } /// Allocates a RefSCC and constructs it using the graph allocator. /// /// The arguments are forwarded to the constructor. - template RefSCC *createRefSCC(Ts &&... Args) { + template RefSCC *createRefSCC(Ts &&...Args) { return new (RefSCCBPA.Allocate()) RefSCC(std::forward(Args)...); } diff --git a/llvm/lib/Analysis/LazyCallGraph.cpp b/llvm/lib/Analysis/LazyCallGraph.cpp --- a/llvm/lib/Analysis/LazyCallGraph.cpp +++ b/llvm/lib/Analysis/LazyCallGraph.cpp @@ -7,6 +7,7 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/LazyCallGraph.h" + #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/Sequence.h" @@ -14,7 +15,6 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/iterator_range.h" #include "llvm/Analysis/TargetLibraryInfo.h" -#include "llvm/Config/llvm-config.h" #include "llvm/IR/Constants.h" #include "llvm/IR/Function.h" #include "llvm/IR/GlobalVariable.h" @@ -28,11 +28,6 @@ #include "llvm/Support/GraphWriter.h" #include "llvm/Support/raw_ostream.h" #include -#include -#include -#include -#include -#include #ifdef EXPENSIVE_CHECKS #include "llvm/ADT/ScopeExit.h" @@ -44,7 +39,7 @@ void LazyCallGraph::EdgeSequence::insertEdgeInternal(Node &TargetN, Edge::Kind EK) { - EdgeIndexMap.insert({&TargetN, Edges.size()}); + EdgeIndexMap.try_emplace(&TargetN, Edges.size()); Edges.emplace_back(TargetN, EK); } @@ -65,7 +60,7 @@ static void addEdge(SmallVectorImpl &Edges, DenseMap &EdgeIndexMap, LazyCallGraph::Node &N, LazyCallGraph::Edge::Kind EK) { - if (!EdgeIndexMap.insert({&N, Edges.size()}).second) + if (!EdgeIndexMap.try_emplace(&N, Edges.size()).second) return; LLVM_DEBUG(dbgs() << " Added callable function: " << N.getName() << "\n"); @@ -118,7 +113,7 @@ } // We've collected all the constant (and thus potentially function or - // function containing) operands to all of the instructions in the function. + // function containing) operands to all the instructions in the function. // Process them (recursively) collecting every function found. visitReferences(Worklist, Visited, [&](Function &F) { addEdge(Edges->Edges, Edges->EdgeIndexMap, G->get(F), @@ -212,8 +207,7 @@ LazyCallGraph::LazyCallGraph(LazyCallGraph &&G) : BPA(std::move(G.BPA)), NodeMap(std::move(G.NodeMap)), EntryEdges(std::move(G.EntryEdges)), SCCBPA(std::move(G.SCCBPA)), - SCCMap(std::move(G.SCCMap)), - LibFunctions(std::move(G.LibFunctions)) { + SCCMap(std::move(G.SCCMap)), LibFunctions(std::move(G.LibFunctions)) { updateGraphPtrs(); } @@ -354,24 +348,22 @@ } // Check that our indices map correctly. - for (auto &SCCIndexPair : SCCIndices) { - SCC *C = SCCIndexPair.first; - int i = SCCIndexPair.second; + for (auto [C, I] : SCCIndices) { assert(C && "Can't have a null SCC in the indices!"); assert(SCCSet.count(C) && "Found an index for an SCC not in the RefSCC!"); - assert(SCCs[i] == C && "Index doesn't point to SCC!"); + assert(SCCs[I] == C && "Index doesn't point to SCC!"); } // Check that the SCCs are in fact in post-order. - for (int i = 0, Size = SCCs.size(); i < Size; ++i) { - SCC &SourceSCC = *SCCs[i]; + for (int I = 0, Size = SCCs.size(); I < Size; ++I) { + SCC &SourceSCC = *SCCs[I]; for (Node &N : SourceSCC) for (Edge &E : *N) { if (!E.isCall()) continue; SCC &TargetSCC = *G->lookupSCC(E.getNode()); if (&TargetSCC.getOuterRefSCC() == this) { - assert(SCCIndices.find(&TargetSCC)->second <= i && + assert(SCCIndices.find(&TargetSCC)->second <= I && "Edge between SCCs violates post-order relationship."); continue; } @@ -533,8 +525,8 @@ auto SourceI = std::stable_partition( SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx + 1, [&ConnectedSet](SCCT *C) { return !ConnectedSet.count(C); }); - for (int i = SourceIdx, e = TargetIdx + 1; i < e; ++i) - SCCIndices.find(SCCs[i])->second = i; + for (int I = SourceIdx, E = TargetIdx + 1; I < E; ++I) + SCCIndices.find(SCCs[I])->second = I; // If the target doesn't connect to the source, then we've corrected the // post-order and there are no cycles formed. @@ -555,7 +547,6 @@ assert(SCCs[SourceIdx] == &SourceSCC && "Bad updated index computation for the source SCC!"); - // See whether there are any remaining intervening SCCs between the source // and target. If so we need to make sure they all are reachable form the // target. @@ -568,22 +559,21 @@ auto TargetI = std::stable_partition( SCCs.begin() + SourceIdx + 1, SCCs.begin() + TargetIdx + 1, [&ConnectedSet](SCCT *C) { return ConnectedSet.count(C); }); - for (int i = SourceIdx + 1, e = TargetIdx + 1; i < e; ++i) - SCCIndices.find(SCCs[i])->second = i; + for (int I = SourceIdx + 1, E = TargetIdx + 1; I < E; ++I) + SCCIndices.find(SCCs[I])->second = I; TargetIdx = std::prev(TargetI) - SCCs.begin(); assert(SCCs[TargetIdx] == &TargetSCC && "Should always end with the target!"); } // At this point, we know that connecting source to target forms a cycle - // because target connects back to source, and we know that all of the SCCs + // because target connects back to source, and we know that all the SCCs // between the source and target in the postorder sequence participate in that // cycle. return make_range(SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx); } -bool -LazyCallGraph::RefSCC::switchInternalEdgeToCall( +bool LazyCallGraph::RefSCC::switchInternalEdgeToCall( Node &SourceN, Node &TargetN, function_ref MergeSCCs)> MergeCB) { assert(!(*SourceN)[TargetN].isCall() && "Must start with a ref edge!"); @@ -699,8 +689,8 @@ verify(); #endif - // Otherwise we need to merge all of the SCCs in the cycle into a single - // result SCC. + // Otherwise we need to merge all the SCCs in the cycle into a single result + // SCC. // // NB: We merge into the target because all of these functions were already // reachable from the target, meaning any SCC-wide properties deduced about it @@ -739,10 +729,8 @@ auto VerifyOnExit = make_scope_exit([&]() { verify(); }); #endif - assert(G->lookupRefSCC(SourceN) == this && - "Source must be in this RefSCC."); - assert(G->lookupRefSCC(TargetN) == this && - "Target must be in this RefSCC."); + assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC."); + assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC."); assert(G->lookupSCC(SourceN) != G->lookupSCC(TargetN) && "Source and Target must be in separate SCCs for this to be trivial!"); @@ -759,10 +747,8 @@ auto VerifyOnExit = make_scope_exit([&]() { verify(); }); #endif - assert(G->lookupRefSCC(SourceN) == this && - "Source must be in this RefSCC."); - assert(G->lookupRefSCC(TargetN) == this && - "Target must be in this RefSCC."); + assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC."); + assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC."); SCC &TargetSCC = *G->lookupSCC(TargetN); assert(G->lookupSCC(SourceN) == &TargetSCC && "Source and Target must be in " @@ -826,18 +812,16 @@ RootN->DFSNumber = RootN->LowLink = 1; int NextDFSNumber = 2; - DFSStack.push_back({RootN, (*RootN)->call_begin()}); + DFSStack.emplace_back(RootN, (*RootN)->call_begin()); do { - Node *N; - EdgeSequence::call_iterator I; - std::tie(N, I) = DFSStack.pop_back_val(); + auto [N, I] = DFSStack.pop_back_val(); auto E = (*N)->call_end(); while (I != E) { Node &ChildN = I->getNode(); if (ChildN.DFSNumber == 0) { // We haven't yet visited this child, so descend, pushing the current // node onto the stack. - DFSStack.push_back({N, I}); + DFSStack.emplace_back(N, I); assert(!G->SCCMap.count(&ChildN) && "Found a node with 0 DFS number but already in an SCC!"); @@ -921,8 +905,8 @@ // Insert the remaining SCCs before the old one. The old SCC can reach all // other SCCs we form because it contains the target node of the removed edge - // of the old SCC. This means that we will have edges into all of the new - // SCCs, which means the old one must come last for postorder. + // of the old SCC. This means that we will have edges into all the new SCCs, + // which means the old one must come last for postorder. int OldIdx = SCCIndices[&OldSCC]; SCCs.insert(SCCs.begin() + OldIdx, NewSCCs.begin(), NewSCCs.end()); @@ -1088,14 +1072,14 @@ SourceC, *this, G->PostOrderRefSCCs, G->RefSCCIndices, ComputeSourceConnectedSet, ComputeTargetConnectedSet); - // Build a set so we can do fast tests for whether a RefSCC will end up as + // Build a set, so we can do fast tests for whether a RefSCC will end up as // part of the merged RefSCC. SmallPtrSet MergeSet(MergeRange.begin(), MergeRange.end()); // This RefSCC will always be part of that set, so just insert it here. MergeSet.insert(this); - // Now that we have identified all of the SCCs which need to be merged into + // Now that we have identified all the SCCs which need to be merged into // a connected set with the inserted edge, merge all of them into this SCC. SmallVector MergedSCCs; int SCCIndex = 0; @@ -1251,11 +1235,9 @@ RootN->DFSNumber = RootN->LowLink = 1; int NextDFSNumber = 2; - DFSStack.push_back({RootN, (*RootN)->begin()}); + DFSStack.emplace_back(RootN, (*RootN)->begin()); do { - Node *N; - EdgeSequence::iterator I; - std::tie(N, I) = DFSStack.pop_back_val(); + auto [N, I] = DFSStack.pop_back_val(); auto E = (*N)->end(); assert(N->DFSNumber != 0 && "We should always assign a DFS number " @@ -1267,7 +1249,7 @@ // Mark that we should start at this child when next this node is the // top of the stack. We don't start at the next child to ensure this // child's lowlink is reflected. - DFSStack.push_back({N, I}); + DFSStack.emplace_back(N, I); // Continue, resetting to the child node. ChildN.LowLink = ChildN.DFSNumber = NextDFSNumber++; @@ -1327,7 +1309,7 @@ // If we find a cycle containing all nodes originally in this RefSCC then // the removal hasn't changed the structure at all. This is an important - // special case and we can directly exit the entire routine more + // special case, and we can directly exit the entire routine more // efficiently as soon as we discover it. if (llvm::size(RefSCCNodes) == NumRefSCCNodes) { // Clear out the low link field as we won't need it. @@ -1353,7 +1335,7 @@ // a radix-sort style map from postorder number to these new RefSCCs. We then // append SCCs to each of these RefSCCs in the order they occurred in the // original SCCs container. - for (int i = 0; i < PostOrderNumber; ++i) + for (int I = 0; I < PostOrderNumber; ++I) Result.push_back(G->createRefSCC(*G)); // Insert the resulting postorder sequence into the global graph postorder @@ -1367,13 +1349,13 @@ G->PostOrderRefSCCs.erase(G->PostOrderRefSCCs.begin() + Idx); G->PostOrderRefSCCs.insert(G->PostOrderRefSCCs.begin() + Idx, Result.begin(), Result.end()); - for (int i : seq(Idx, G->PostOrderRefSCCs.size())) - G->RefSCCIndices[G->PostOrderRefSCCs[i]] = i; + for (int I : seq(Idx, G->PostOrderRefSCCs.size())) + G->RefSCCIndices[G->PostOrderRefSCCs[I]] = I; for (SCC *C : SCCs) { // We store the SCC number in the node's low-link field above. int SCCNumber = C->begin()->LowLink; - // Clear out all of the SCC's node's low-link fields now that we're done + // Clear out all the SCC's node's low-link fields now that we're done // using them as side-storage. for (Node &N : *C) { assert(N.LowLink == SCCNumber && @@ -1419,11 +1401,11 @@ #endif // First insert it into the source or find the existing edge. - auto InsertResult = - SourceN->EdgeIndexMap.insert({&TargetN, SourceN->Edges.size()}); - if (!InsertResult.second) { + auto [Iterator, Inserted] = + SourceN->EdgeIndexMap.try_emplace(&TargetN, SourceN->Edges.size()); + if (!Inserted) { // Already an edge, just update it. - Edge &E = SourceN->Edges[InsertResult.first->second]; + Edge &E = SourceN->Edges[Iterator->second]; if (E.isCall()) return; // Nothing to do! E.setKind(Edge::Call); @@ -1446,9 +1428,10 @@ #endif // First insert it into the source or find the existing edge. - auto InsertResult = - SourceN->EdgeIndexMap.insert({&TargetN, SourceN->Edges.size()}); - if (!InsertResult.second) + auto [Iterator, Inserted] = + SourceN->EdgeIndexMap.try_emplace(&TargetN, SourceN->Edges.size()); + (void)Iterator; + if (!Inserted) // Already an edge, we're done. return; @@ -1649,9 +1632,9 @@ // SCC, since that case was handled earlier. If the edge from the // original function to the new function was a call edge, then we need // to insert the newly created function's SCC before the original - // function's SCC. Otherwise either the new SCC comes after the original - // function's SCC, or it doesn't matter, and in both cases we can add it - // to the very end. + // function's SCC. Otherwise, either the new SCC comes after the + // original function's SCC, or it doesn't matter, and in both cases we + // can add it to the very end. int InsertIndex = EK == Edge::Kind::Call ? NewRC->SCCIndices[OriginalC] : NewRC->SCCIndices.size(); NewRC->SCCs.insert(NewRC->SCCs.begin() + InsertIndex, NewC); @@ -1772,7 +1755,7 @@ void LazyCallGraph::updateGraphPtrs() { // Walk the node map to update their graph pointers. While this iterates in - // an unstable order, the order has no effect so it remains correct. + // an unstable order, the order has no effect, so it remains correct. for (auto &FunctionNodePair : NodeMap) FunctionNodePair.second->G = this; @@ -1815,18 +1798,16 @@ RootN->DFSNumber = RootN->LowLink = 1; int NextDFSNumber = 2; - DFSStack.push_back({RootN, GetBegin(*RootN)}); + DFSStack.emplace_back(RootN, GetBegin(*RootN)); do { - Node *N; - EdgeItT I; - std::tie(N, I) = DFSStack.pop_back_val(); + auto [N, I] = DFSStack.pop_back_val(); auto E = GetEnd(*N); while (I != E) { Node &ChildN = GetNode(I); if (ChildN.DFSNumber == 0) { // We haven't yet visited this child, so descend, pushing the current // node onto the stack. - DFSStack.push_back({N, I}); + DFSStack.emplace_back(N, I); ChildN.DFSNumber = ChildN.LowLink = NextDFSNumber++; N = &ChildN; @@ -1914,8 +1895,8 @@ }); // Wire up the SCC indices. - for (int i = 0, Size = RC.SCCs.size(); i < Size; ++i) - RC.SCCIndices[RC.SCCs[i]] = i; + for (int I = 0, Size = RC.SCCs.size(); I < Size; ++I) + RC.SCCIndices[RC.SCCs[I]] = I; } void LazyCallGraph::buildRefSCCs() { @@ -1946,7 +1927,7 @@ // Push the new node into the postorder list and remember its position // in the index map. bool Inserted = - RefSCCIndices.insert({NewRC, PostOrderRefSCCs.size()}).second; + RefSCCIndices.try_emplace(NewRC, PostOrderRefSCCs.size()).second; (void)Inserted; assert(Inserted && "Cannot already have this RefSCC in the index map!"); PostOrderRefSCCs.push_back(NewRC);