diff options
Diffstat (limited to 'lib/Analysis/LazyCallGraph.cpp')
| -rw-r--r-- | lib/Analysis/LazyCallGraph.cpp | 564 |
1 files changed, 190 insertions, 374 deletions
diff --git a/lib/Analysis/LazyCallGraph.cpp b/lib/Analysis/LazyCallGraph.cpp index d287f81985fd..54299d078be5 100644 --- a/lib/Analysis/LazyCallGraph.cpp +++ b/lib/Analysis/LazyCallGraph.cpp @@ -8,15 +8,31 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/LazyCallGraph.h" +#include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/ScopeExit.h" #include "llvm/ADT/Sequence.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/iterator_range.h" +#include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/IR/CallSite.h" -#include "llvm/IR/InstVisitor.h" -#include "llvm/IR/Instructions.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/GlobalVariable.h" +#include "llvm/IR/Instruction.h" +#include "llvm/IR/Module.h" #include "llvm/IR/PassManager.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" #include "llvm/Support/GraphWriter.h" +#include "llvm/Support/raw_ostream.h" +#include <algorithm> +#include <cassert> +#include <cstddef> +#include <iterator> +#include <string> +#include <tuple> #include <utility> using namespace llvm; @@ -175,7 +191,7 @@ LazyCallGraph::LazyCallGraph(Module &M, TargetLibraryInfo &TLI) { 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)), LeafRefSCCs(std::move(G.LeafRefSCCs)), + SCCMap(std::move(G.SCCMap)), LibFunctions(std::move(G.LibFunctions)) { updateGraphPtrs(); } @@ -186,7 +202,6 @@ LazyCallGraph &LazyCallGraph::operator=(LazyCallGraph &&G) { EntryEdges = std::move(G.EntryEdges); SCCBPA = std::move(G.SCCBPA); SCCMap = std::move(G.SCCMap); - LeafRefSCCs = std::move(G.LeafRefSCCs); LibFunctions = std::move(G.LibFunctions); updateGraphPtrs(); return *this; @@ -212,7 +227,7 @@ void LazyCallGraph::SCC::verify() { assert(N->LowLink == -1 && "Must set low link to -1 when adding a node to an SCC!"); for (Edge &E : **N) - assert(E.getNode() && "Can't have an unpopulated node!"); + assert(E.getNode().isPopulated() && "Can't have an unpopulated node!"); } } #endif @@ -313,38 +328,49 @@ void LazyCallGraph::RefSCC::verify() { "Edge between SCCs violates post-order relationship."); continue; } - assert(TargetSCC.getOuterRefSCC().Parents.count(this) && - "Edge to a RefSCC missing us in its parent set."); } } - - // Check that our parents are actually parents. - for (RefSCC *ParentRC : Parents) { - assert(ParentRC != this && "Cannot be our own parent!"); - auto HasConnectingEdge = [&] { - for (SCC &C : *ParentRC) - for (Node &N : C) - for (Edge &E : *N) - if (G->lookupRefSCC(E.getNode()) == this) - return true; - return false; - }; - assert(HasConnectingEdge() && "No edge connects the parent to us!"); - } } #endif -bool LazyCallGraph::RefSCC::isDescendantOf(const RefSCC &C) const { - // Walk up the parents of this SCC and verify that we eventually find C. - SmallVector<const RefSCC *, 4> AncestorWorklist; - AncestorWorklist.push_back(this); +bool LazyCallGraph::RefSCC::isParentOf(const RefSCC &RC) const { + if (&RC == this) + return false; + + // Search all edges to see if this is a parent. + for (SCC &C : *this) + for (Node &N : C) + for (Edge &E : *N) + if (G->lookupRefSCC(E.getNode()) == &RC) + return true; + + return false; +} + +bool LazyCallGraph::RefSCC::isAncestorOf(const RefSCC &RC) const { + if (&RC == this) + return false; + + // For each descendant of this RefSCC, see if one of its children is the + // argument. If not, add that descendant to the worklist and continue + // searching. + SmallVector<const RefSCC *, 4> Worklist; + SmallPtrSet<const RefSCC *, 4> Visited; + Worklist.push_back(this); + Visited.insert(this); do { - const RefSCC *AncestorC = AncestorWorklist.pop_back_val(); - if (AncestorC->isChildOf(C)) - return true; - for (const RefSCC *ParentC : AncestorC->Parents) - AncestorWorklist.push_back(ParentC); - } while (!AncestorWorklist.empty()); + const RefSCC &DescendantRC = *Worklist.pop_back_val(); + for (SCC &C : DescendantRC) + for (Node &N : C) + for (Edge &E : *N) { + auto *ChildRC = G->lookupRefSCC(E.getNode()); + if (ChildRC == &RC) + return true; + if (!ChildRC || !Visited.insert(ChildRC).second) + continue; + Worklist.push_back(ChildRC); + } + } while (!Worklist.empty()); return false; } @@ -907,17 +933,13 @@ void LazyCallGraph::RefSCC::insertOutgoingEdge(Node &SourceN, Node &TargetN, assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC."); - RefSCC &TargetC = *G->lookupRefSCC(TargetN); - assert(&TargetC != this && "Target must not be in this RefSCC."); + assert(G->lookupRefSCC(TargetN) != this && + "Target must not be in this RefSCC."); #ifdef EXPENSIVE_CHECKS - assert(TargetC.isDescendantOf(*this) && + assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) && "Target must be a descendant of the Source."); #endif - // The only change required is to add this SCC to the parent set of the - // callee. - TargetC.Parents.insert(this); - #ifndef NDEBUG // Check that the RefSCC is still valid. verify(); @@ -957,22 +979,20 @@ LazyCallGraph::RefSCC::insertIncomingRefEdge(Node &SourceN, Node &TargetN) { // RefSCCs (and their edges) are visited here. auto ComputeSourceConnectedSet = [&](SmallPtrSetImpl<RefSCC *> &Set) { Set.insert(&SourceC); - SmallVector<RefSCC *, 4> Worklist; - Worklist.push_back(&SourceC); - do { - RefSCC &RC = *Worklist.pop_back_val(); - for (RefSCC &ParentRC : RC.parents()) { - // Skip any RefSCCs outside the range of source to target in the - // postorder sequence. - int ParentIdx = G->getRefSCCIndex(ParentRC); - assert(ParentIdx > SourceIdx && "Parent cannot precede source in postorder!"); - if (ParentIdx > TargetIdx) - continue; - if (Set.insert(&ParentRC).second) - // First edge connecting to this parent, add it to our worklist. - Worklist.push_back(&ParentRC); - } - } while (!Worklist.empty()); + auto IsConnected = [&](RefSCC &RC) { + for (SCC &C : RC) + for (Node &N : C) + for (Edge &E : *N) + if (Set.count(G->lookupRefSCC(E.getNode()))) + return true; + + return false; + }; + + for (RefSCC *C : make_range(G->PostOrderRefSCCs.begin() + SourceIdx + 1, + G->PostOrderRefSCCs.begin() + TargetIdx + 1)) + if (IsConnected(*C)) + Set.insert(C); }; // Use a normal worklist to find which SCCs the target connects to. We still @@ -1023,12 +1043,6 @@ LazyCallGraph::RefSCC::insertIncomingRefEdge(Node &SourceN, Node &TargetN) { assert(RC != this && "We're merging into the target RefSCC, so it " "shouldn't be in the range."); - // Merge the parents which aren't part of the merge into the our parents. - for (RefSCC *ParentRC : RC->Parents) - if (!MergeSet.count(ParentRC)) - Parents.insert(ParentRC); - RC->Parents.clear(); - // Walk the inner SCCs to update their up-pointer and walk all the edges to // update any parent sets. // FIXME: We should try to find a way to avoid this (rather expensive) edge @@ -1036,16 +1050,8 @@ LazyCallGraph::RefSCC::insertIncomingRefEdge(Node &SourceN, Node &TargetN) { for (SCC &InnerC : *RC) { InnerC.OuterRefSCC = this; SCCIndices[&InnerC] = SCCIndex++; - for (Node &N : InnerC) { + for (Node &N : InnerC) G->SCCMap[&N] = &InnerC; - for (Edge &E : *N) { - RefSCC &ChildRC = *G->lookupRefSCC(E.getNode()); - if (MergeSet.count(&ChildRC)) - continue; - ChildRC.Parents.erase(RC); - ChildRC.Parents.insert(this); - } - } } // Now merge in the SCCs. We can actually move here so try to reuse storage @@ -1087,12 +1093,8 @@ LazyCallGraph::RefSCC::insertIncomingRefEdge(Node &SourceN, Node &TargetN) { void LazyCallGraph::RefSCC::removeOutgoingEdge(Node &SourceN, Node &TargetN) { assert(G->lookupRefSCC(SourceN) == this && "The source must be a member of this RefSCC."); - - RefSCC &TargetRC = *G->lookupRefSCC(TargetN); - assert(&TargetRC != this && "The target must not be a member of this RefSCC"); - - assert(!is_contained(G->LeafRefSCCs, this) && - "Cannot have a leaf RefSCC source."); + assert(G->lookupRefSCC(TargetN) != this && + "The target must not be a member of this RefSCC"); #ifndef NDEBUG // In a debug build, verify the RefSCC is valid to start with and when this @@ -1105,122 +1107,72 @@ void LazyCallGraph::RefSCC::removeOutgoingEdge(Node &SourceN, Node &TargetN) { bool Removed = SourceN->removeEdgeInternal(TargetN); (void)Removed; assert(Removed && "Target not in the edge set for this caller?"); - - bool HasOtherEdgeToChildRC = false; - bool HasOtherChildRC = false; - for (SCC *InnerC : SCCs) { - for (Node &N : *InnerC) { - for (Edge &E : *N) { - RefSCC &OtherChildRC = *G->lookupRefSCC(E.getNode()); - if (&OtherChildRC == &TargetRC) { - HasOtherEdgeToChildRC = true; - break; - } - if (&OtherChildRC != this) - HasOtherChildRC = true; - } - if (HasOtherEdgeToChildRC) - break; - } - if (HasOtherEdgeToChildRC) - break; - } - // Because the SCCs form a DAG, deleting such an edge cannot change the set - // of SCCs in the graph. However, it may cut an edge of the SCC DAG, making - // the source SCC no longer connected to the target SCC. If so, we need to - // update the target SCC's map of its parents. - if (!HasOtherEdgeToChildRC) { - bool Removed = TargetRC.Parents.erase(this); - (void)Removed; - assert(Removed && - "Did not find the source SCC in the target SCC's parent list!"); - - // It may orphan an SCC if it is the last edge reaching it, but that does - // not violate any invariants of the graph. - if (TargetRC.Parents.empty()) - DEBUG(dbgs() << "LCG: Update removing " << SourceN.getFunction().getName() - << " -> " << TargetN.getFunction().getName() - << " edge orphaned the callee's SCC!\n"); - - // It may make the Source SCC a leaf SCC. - if (!HasOtherChildRC) - G->LeafRefSCCs.push_back(this); - } } SmallVector<LazyCallGraph::RefSCC *, 1> -LazyCallGraph::RefSCC::removeInternalRefEdge(Node &SourceN, Node &TargetN) { - assert(!(*SourceN)[TargetN].isCall() && - "Cannot remove a call edge, it must first be made a ref edge"); +LazyCallGraph::RefSCC::removeInternalRefEdge(Node &SourceN, + ArrayRef<Node *> TargetNs) { + // We return a list of the resulting *new* RefSCCs in post-order. + SmallVector<RefSCC *, 1> Result; #ifndef NDEBUG - // In a debug build, verify the RefSCC is valid to start with and when this - // routine finishes. + // In a debug build, verify the RefSCC is valid to start with and that either + // we return an empty list of result RefSCCs and this RefSCC remains valid, + // or we return new RefSCCs and this RefSCC is dead. verify(); - auto VerifyOnExit = make_scope_exit([&]() { verify(); }); + auto VerifyOnExit = make_scope_exit([&]() { + // If we didn't replace our RefSCC with new ones, check that this one + // remains valid. + if (G) + verify(); + }); #endif - // First remove the actual edge. - bool Removed = SourceN->removeEdgeInternal(TargetN); - (void)Removed; - assert(Removed && "Target not in the edge set for this caller?"); + // First remove the actual edges. + for (Node *TargetN : TargetNs) { + assert(!(*SourceN)[*TargetN].isCall() && + "Cannot remove a call edge, it must first be made a ref edge"); - // We return a list of the resulting *new* RefSCCs in post-order. - SmallVector<RefSCC *, 1> Result; + bool Removed = SourceN->removeEdgeInternal(*TargetN); + (void)Removed; + assert(Removed && "Target not in the edge set for this caller?"); + } - // Direct recursion doesn't impact the SCC graph at all. - if (&SourceN == &TargetN) + // Direct self references don't impact the ref graph at all. + if (llvm::all_of(TargetNs, + [&](Node *TargetN) { return &SourceN == TargetN; })) return Result; - // If this ref edge is within an SCC then there are sufficient other edges to - // form a cycle without this edge so removing it is a no-op. + // If all targets are in the same SCC as the source, because no call edges + // were removed there is no RefSCC structure change. SCC &SourceC = *G->lookupSCC(SourceN); - SCC &TargetC = *G->lookupSCC(TargetN); - if (&SourceC == &TargetC) + if (llvm::all_of(TargetNs, [&](Node *TargetN) { + return G->lookupSCC(*TargetN) == &SourceC; + })) return Result; // We build somewhat synthetic new RefSCCs by providing a postorder mapping - // for each inner SCC. We also store these associated with *nodes* rather - // than SCCs because this saves a round-trip through the node->SCC map and in - // the common case, SCCs are small. We will verify that we always give the - // same number to every node in the SCC such that these are equivalent. - const int RootPostOrderNumber = 0; - int PostOrderNumber = RootPostOrderNumber + 1; - SmallDenseMap<Node *, int> PostOrderMapping; - - // Every node in the target SCC can already reach every node in this RefSCC - // (by definition). It is the only node we know will stay inside this RefSCC. - // Everything which transitively reaches Target will also remain in the - // RefSCC. We handle this by pre-marking that the nodes in the target SCC map - // back to the root post order number. - // - // This also enables us to take a very significant short-cut in the standard - // Tarjan walk to re-form RefSCCs below: whenever we build an edge that - // references the target node, we know that the target node eventually - // references all other nodes in our walk. As a consequence, we can detect - // and handle participants in that cycle without walking all the edges that - // form the connections, and instead by relying on the fundamental guarantee - // coming into this operation. - for (Node &N : TargetC) - PostOrderMapping[&N] = RootPostOrderNumber; + // for each inner SCC. We store these inside the low-link field of the nodes + // rather than associated with SCCs because this saves a round-trip through + // the node->SCC map and in the common case, SCCs are small. We will verify + // that we always give the same number to every node in the SCC such that + // these are equivalent. + int PostOrderNumber = 0; // Reset all the other nodes to prepare for a DFS over them, and add them to // our worklist. SmallVector<Node *, 8> Worklist; for (SCC *C : SCCs) { - if (C == &TargetC) - continue; - for (Node &N : *C) N.DFSNumber = N.LowLink = 0; Worklist.append(C->Nodes.begin(), C->Nodes.end()); } - auto MarkNodeForSCCNumber = [&PostOrderMapping](Node &N, int Number) { - N.DFSNumber = N.LowLink = -1; - PostOrderMapping[&N] = Number; - }; + // Track the number of nodes in this RefSCC so that we can quickly recognize + // an important special case of the edge removal not breaking the cycle of + // this RefSCC. + const int NumRefSCCNodes = Worklist.size(); SmallVector<std::pair<Node *, EdgeSequence::iterator>, 4> DFSStack; SmallVector<Node *, 4> PendingRefSCCStack; @@ -1267,31 +1219,8 @@ LazyCallGraph::RefSCC::removeInternalRefEdge(Node &SourceN, Node &TargetN) { continue; } if (ChildN.DFSNumber == -1) { - // Check if this edge's target node connects to the deleted edge's - // target node. If so, we know that every node connected will end up - // in this RefSCC, so collapse the entire current stack into the root - // slot in our SCC numbering. See above for the motivation of - // optimizing the target connected nodes in this way. - auto PostOrderI = PostOrderMapping.find(&ChildN); - if (PostOrderI != PostOrderMapping.end() && - PostOrderI->second == RootPostOrderNumber) { - MarkNodeForSCCNumber(*N, RootPostOrderNumber); - while (!PendingRefSCCStack.empty()) - MarkNodeForSCCNumber(*PendingRefSCCStack.pop_back_val(), - RootPostOrderNumber); - while (!DFSStack.empty()) - MarkNodeForSCCNumber(*DFSStack.pop_back_val().first, - RootPostOrderNumber); - // Ensure we break all the way out of the enclosing loop. - N = nullptr; - break; - } - // If this child isn't currently in this RefSCC, no need to process - // it. However, we do need to remove this RefSCC from its RefSCC's - // parent set. - RefSCC &ChildRC = *G->lookupRefSCC(ChildN); - ChildRC.Parents.erase(this); + // it. ++I; continue; } @@ -1304,9 +1233,6 @@ LazyCallGraph::RefSCC::removeInternalRefEdge(Node &SourceN, Node &TargetN) { N->LowLink = ChildN.LowLink; ++I; } - if (!N) - // We short-circuited this node. - break; // We've finished processing N and its descendents, put it on our pending // stack to eventually get merged into a RefSCC. @@ -1321,146 +1247,98 @@ LazyCallGraph::RefSCC::removeInternalRefEdge(Node &SourceN, Node &TargetN) { } // Otherwise, form a new RefSCC from the top of the pending node stack. + int RefSCCNumber = PostOrderNumber++; int RootDFSNumber = N->DFSNumber; + // Find the range of the node stack by walking down until we pass the - // root DFS number. - auto RefSCCNodes = make_range( - PendingRefSCCStack.rbegin(), - find_if(reverse(PendingRefSCCStack), [RootDFSNumber](const Node *N) { - return N->DFSNumber < RootDFSNumber; - })); + // root DFS number. Update the DFS numbers and low link numbers in the + // process to avoid re-walking this list where possible. + auto StackRI = find_if(reverse(PendingRefSCCStack), [&](Node *N) { + if (N->DFSNumber < RootDFSNumber) + // We've found the bottom. + return true; - // Mark the postorder number for these nodes and clear them off the - // stack. We'll use the postorder number to pull them into RefSCCs at the - // end. FIXME: Fuse with the loop above. - int RefSCCNumber = PostOrderNumber++; - for (Node *N : RefSCCNodes) - MarkNodeForSCCNumber(*N, RefSCCNumber); + // Update this node and keep scanning. + N->DFSNumber = -1; + // Save the post-order number in the lowlink field so that we can use + // it to map SCCs into new RefSCCs after we finish the DFS. + N->LowLink = RefSCCNumber; + return false; + }); + auto RefSCCNodes = make_range(StackRI.base(), PendingRefSCCStack.end()); + + // 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 + // efficiently as soon as we discover it. + if (std::distance(RefSCCNodes.begin(), RefSCCNodes.end()) == + NumRefSCCNodes) { + // Clear out the low link field as we won't need it. + for (Node *N : RefSCCNodes) + N->LowLink = -1; + // Return the empty result immediately. + return Result; + } - PendingRefSCCStack.erase(RefSCCNodes.end().base(), - PendingRefSCCStack.end()); + // We've already marked the nodes internally with the RefSCC number so + // just clear them off the stack and continue. + PendingRefSCCStack.erase(RefSCCNodes.begin(), PendingRefSCCStack.end()); } while (!DFSStack.empty()); assert(DFSStack.empty() && "Didn't flush the entire DFS stack!"); assert(PendingRefSCCStack.empty() && "Didn't flush all pending nodes!"); } while (!Worklist.empty()); - // We now have a post-order numbering for RefSCCs and a mapping from each - // node in this RefSCC to its final RefSCC. We create each new RefSCC node - // (re-using this RefSCC node for the root) and build a radix-sort style map - // from postorder number to the RefSCC. We then append SCCs to each of these - // RefSCCs in the order they occured in the original SCCs container. - for (int i = 1; i < PostOrderNumber; ++i) + assert(PostOrderNumber > 1 && + "Should never finish the DFS when the existing RefSCC remains valid!"); + + // Otherwise we create a collection of new RefSCC nodes and build + // 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 occured in the + // original SCCs container. + for (int i = 0; i < PostOrderNumber; ++i) Result.push_back(G->createRefSCC(*G)); // Insert the resulting postorder sequence into the global graph postorder - // sequence before the current RefSCC in that sequence. The idea being that - // this RefSCC is the target of the reference edge removed, and thus has - // a direct or indirect edge to every other RefSCC formed and so must be at - // the end of any postorder traversal. + // sequence before the current RefSCC in that sequence, and then remove the + // current one. // // FIXME: It'd be nice to change the APIs so that we returned an iterator // range over the global postorder sequence and generally use that sequence // rather than building a separate result vector here. - if (!Result.empty()) { - int Idx = G->getRefSCCIndex(*this); - G->PostOrderRefSCCs.insert(G->PostOrderRefSCCs.begin() + Idx, - Result.begin(), Result.end()); - for (int i : seq<int>(Idx, G->PostOrderRefSCCs.size())) - G->RefSCCIndices[G->PostOrderRefSCCs[i]] = i; - assert(G->PostOrderRefSCCs[G->getRefSCCIndex(*this)] == this && - "Failed to update this RefSCC's index after insertion!"); - } + int Idx = G->getRefSCCIndex(*this); + G->PostOrderRefSCCs.erase(G->PostOrderRefSCCs.begin() + Idx); + G->PostOrderRefSCCs.insert(G->PostOrderRefSCCs.begin() + Idx, Result.begin(), + Result.end()); + for (int i : seq<int>(Idx, G->PostOrderRefSCCs.size())) + G->RefSCCIndices[G->PostOrderRefSCCs[i]] = i; for (SCC *C : SCCs) { - auto PostOrderI = PostOrderMapping.find(&*C->begin()); - assert(PostOrderI != PostOrderMapping.end() && - "Cannot have missing mappings for nodes!"); - int SCCNumber = PostOrderI->second; -#ifndef NDEBUG - for (Node &N : *C) - assert(PostOrderMapping.find(&N)->second == SCCNumber && + // 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 + // using them as side-storage. + for (Node &N : *C) { + assert(N.LowLink == SCCNumber && "Cannot have different numbers for nodes in the same SCC!"); -#endif - if (SCCNumber == 0) - // The root node is handled separately by removing the SCCs. - continue; + N.LowLink = -1; + } - RefSCC &RC = *Result[SCCNumber - 1]; + RefSCC &RC = *Result[SCCNumber]; int SCCIndex = RC.SCCs.size(); RC.SCCs.push_back(C); RC.SCCIndices[C] = SCCIndex; C->OuterRefSCC = &RC; } - // FIXME: We re-walk the edges in each RefSCC to establish whether it is - // a leaf and connect it to the rest of the graph's parents lists. This is - // really wasteful. We should instead do this during the DFS to avoid yet - // another edge walk. - for (RefSCC *RC : Result) - G->connectRefSCC(*RC); - - // Now erase all but the root's SCCs. - SCCs.erase(remove_if(SCCs, - [&](SCC *C) { - return PostOrderMapping.lookup(&*C->begin()) != - RootPostOrderNumber; - }), - SCCs.end()); + // Now that we've moved things into the new RefSCCs, clear out our current + // one. + G = nullptr; + SCCs.clear(); SCCIndices.clear(); - for (int i = 0, Size = SCCs.size(); i < Size; ++i) - SCCIndices[SCCs[i]] = i; #ifndef NDEBUG - // Now we need to reconnect the current (root) SCC to the graph. We do this - // manually because we can special case our leaf handling and detect errors. - bool IsLeaf = true; -#endif - for (SCC *C : SCCs) - for (Node &N : *C) { - for (Edge &E : *N) { - RefSCC &ChildRC = *G->lookupRefSCC(E.getNode()); - if (&ChildRC == this) - continue; - ChildRC.Parents.insert(this); -#ifndef NDEBUG - IsLeaf = false; -#endif - } - } -#ifndef NDEBUG - if (!Result.empty()) - assert(!IsLeaf && "This SCC cannot be a leaf as we have split out new " - "SCCs by removing this edge."); - if (none_of(G->LeafRefSCCs, [&](RefSCC *C) { return C == this; })) - assert(!IsLeaf && "This SCC cannot be a leaf as it already had child " - "SCCs before we removed this edge."); -#endif - // And connect both this RefSCC and all the new ones to the correct parents. - // The easiest way to do this is just to re-analyze the old parent set. - SmallVector<RefSCC *, 4> OldParents(Parents.begin(), Parents.end()); - Parents.clear(); - for (RefSCC *ParentRC : OldParents) - for (SCC &ParentC : *ParentRC) - for (Node &ParentN : ParentC) - for (Edge &E : *ParentN) { - RefSCC &RC = *G->lookupRefSCC(E.getNode()); - if (&RC != ParentRC) - RC.Parents.insert(ParentRC); - } - - // If this SCC stopped being a leaf through this edge removal, remove it from - // the leaf SCC list. Note that this DTRT in the case where this was never - // a leaf. - // FIXME: As LeafRefSCCs could be very large, we might want to not walk the - // entire list if this RefSCC wasn't a leaf before the edge removal. - if (!Result.empty()) - G->LeafRefSCCs.erase( - std::remove(G->LeafRefSCCs.begin(), G->LeafRefSCCs.end(), this), - G->LeafRefSCCs.end()); - -#ifndef NDEBUG - // Verify all of the new RefSCCs. + // Verify the new RefSCCs we've built. for (RefSCC *RC : Result) RC->verify(); #endif @@ -1477,18 +1355,13 @@ void LazyCallGraph::RefSCC::handleTrivialEdgeInsertion(Node &SourceN, // after this edge insertion. assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC."); RefSCC &TargetRC = *G->lookupRefSCC(TargetN); - if (&TargetRC == this) { - + if (&TargetRC == this) return; - } #ifdef EXPENSIVE_CHECKS assert(TargetRC.isDescendantOf(*this) && "Target must be a descendant of the Source."); #endif - // The only change required is to add this RefSCC to the parent set of the - // target. This is a set and so idempotent if the edge already existed. - TargetRC.Parents.insert(this); } void LazyCallGraph::RefSCC::insertTrivialCallEdge(Node &SourceN, @@ -1646,24 +1519,6 @@ void LazyCallGraph::removeDeadFunction(Function &F) { assert(C.size() == 1 && "Dead functions must be in a singular SCC"); assert(RC.size() == 1 && "Dead functions must be in a singular RefSCC"); - // Clean up any remaining reference edges. Note that we walk an unordered set - // here but are just removing and so the order doesn't matter. - for (RefSCC &ParentRC : RC.parents()) - for (SCC &ParentC : ParentRC) - for (Node &ParentN : ParentC) - if (ParentN) - ParentN->removeEdgeInternal(N); - - // Now remove this RefSCC from any parents sets and the leaf list. - for (Edge &E : *N) - if (RefSCC *TargetRC = lookupRefSCC(E.getNode())) - TargetRC->Parents.erase(&RC); - // FIXME: This is a linear operation which could become hot and benefit from - // an index map. - auto LRI = find(LeafRefSCCs, &RC); - if (LRI != LeafRefSCCs.end()) - LeafRefSCCs.erase(LRI); - auto RCIndexI = RefSCCIndices.find(&RC); int RCIndex = RCIndexI->second; PostOrderRefSCCs.erase(PostOrderRefSCCs.begin() + RCIndex); @@ -1674,8 +1529,11 @@ void LazyCallGraph::removeDeadFunction(Function &F) { // Finally clear out all the data structures from the node down through the // components. N.clear(); + N.G = nullptr; + N.F = nullptr; C.clear(); RC.clear(); + RC.G = nullptr; // Nothing to delete as all the objects are allocated in stable bump pointer // allocators. @@ -1686,32 +1544,13 @@ LazyCallGraph::Node &LazyCallGraph::insertInto(Function &F, Node *&MappedN) { } void LazyCallGraph::updateGraphPtrs() { - // Process all nodes updating the graph pointers. - { - SmallVector<Node *, 16> Worklist; - for (Edge &E : EntryEdges) - Worklist.push_back(&E.getNode()); - - while (!Worklist.empty()) { - Node &N = *Worklist.pop_back_val(); - N.G = this; - if (N) - for (Edge &E : *N) - Worklist.push_back(&E.getNode()); - } - } + // 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. + for (auto &FunctionNodePair : NodeMap) + FunctionNodePair.second->G = this; - // Process all SCCs updating the graph pointers. - { - SmallVector<RefSCC *, 16> Worklist(LeafRefSCCs.begin(), LeafRefSCCs.end()); - - while (!Worklist.empty()) { - RefSCC &C = *Worklist.pop_back_val(); - C.G = this; - for (RefSCC &ParentC : C.parents()) - Worklist.push_back(&ParentC); - } - } + for (auto *RC : PostOrderRefSCCs) + RC->G = this; } template <typename RootsT, typename GetBeginT, typename GetEndT, @@ -1719,7 +1558,7 @@ template <typename RootsT, typename GetBeginT, typename GetEndT, void LazyCallGraph::buildGenericSCCs(RootsT &&Roots, GetBeginT &&GetBegin, GetEndT &&GetEnd, GetNodeT &&GetNode, FormSCCCallbackT &&FormSCC) { - typedef decltype(GetBegin(std::declval<Node &>())) EdgeItT; + using EdgeItT = decltype(GetBegin(std::declval<Node &>())); SmallVector<std::pair<Node *, EdgeItT>, 16> DFSStack; SmallVector<Node *, 16> PendingSCCStack; @@ -1871,7 +1710,6 @@ void LazyCallGraph::buildRefSCCs() { [this](node_stack_range Nodes) { RefSCC *NewRC = createRefSCC(*this); buildSCCs(*NewRC, Nodes); - connectRefSCC(*NewRC); // Push the new node into the postorder list and remember its position // in the index map. @@ -1886,28 +1724,6 @@ void LazyCallGraph::buildRefSCCs() { }); } -// FIXME: We should move callers of this to embed the parent linking and leaf -// tracking into their DFS in order to remove a full walk of all edges. -void LazyCallGraph::connectRefSCC(RefSCC &RC) { - // Walk all edges in the RefSCC (this remains linear as we only do this once - // when we build the RefSCC) to connect it to the parent sets of its - // children. - bool IsLeaf = true; - for (SCC &C : RC) - for (Node &N : C) - for (Edge &E : *N) { - RefSCC &ChildRC = *lookupRefSCC(E.getNode()); - if (&ChildRC == &RC) - continue; - ChildRC.Parents.insert(&RC); - IsLeaf = false; - } - - // For the SCCs where we find no child SCCs, add them to the leaf list. - if (IsLeaf) - LeafRefSCCs.push_back(&RC); -} - AnalysisKey LazyCallGraphAnalysis::Key; LazyCallGraphPrinterPass::LazyCallGraphPrinterPass(raw_ostream &OS) : OS(OS) {} |