diff options
| -rw-r--r-- | llvm/include/llvm/Analysis/CGSCCPassManager.h | 41 | ||||
| -rw-r--r-- | llvm/include/llvm/Analysis/LazyCallGraph.h | 452 | ||||
| -rw-r--r-- | llvm/lib/Analysis/LazyCallGraph.cpp | 1569 | ||||
| -rw-r--r-- | llvm/test/Analysis/LazyCallGraph/basic.ll | 231 | ||||
| -rw-r--r-- | llvm/unittests/Analysis/LazyCallGraphTest.cpp | 985 |
5 files changed, 2518 insertions, 760 deletions
diff --git a/llvm/include/llvm/Analysis/CGSCCPassManager.h b/llvm/include/llvm/Analysis/CGSCCPassManager.h index e7635eb1ab6..6b2600597a7 100644 --- a/llvm/include/llvm/Analysis/CGSCCPassManager.h +++ b/llvm/include/llvm/Analysis/CGSCCPassManager.h @@ -226,23 +226,24 @@ public: LazyCallGraph &CG = AM->getResult<LazyCallGraphAnalysis>(M); PreservedAnalyses PA = PreservedAnalyses::all(); - for (LazyCallGraph::SCC &C : CG.postorder_sccs()) { - PreservedAnalyses PassPA = Pass.run(C, &CGAM); - - // We know that the CGSCC pass couldn't have invalidated any other - // SCC's analyses (that's the contract of a CGSCC pass), so - // directly handle the CGSCC analysis manager's invalidation here. We - // also update the preserved set of analyses to reflect that invalidated - // analyses are now safe to preserve. - // FIXME: This isn't quite correct. We need to handle the case where the - // pass updated the CG, particularly some child of the current SCC, and - // invalidate its analyses. - PassPA = CGAM.invalidate(C, std::move(PassPA)); - - // Then intersect the preserved set so that invalidation of module - // analyses will eventually occur when the module pass completes. - PA.intersect(std::move(PassPA)); - } + for (LazyCallGraph::RefSCC &OuterC : CG.postorder_ref_sccs()) + for (LazyCallGraph::SCC &C : OuterC) { + PreservedAnalyses PassPA = Pass.run(C, &CGAM); + + // We know that the CGSCC pass couldn't have invalidated any other + // SCC's analyses (that's the contract of a CGSCC pass), so + // directly handle the CGSCC analysis manager's invalidation here. We + // also update the preserved set of analyses to reflect that invalidated + // analyses are now safe to preserve. + // FIXME: This isn't quite correct. We need to handle the case where the + // pass updated the CG, particularly some child of the current SCC, and + // invalidate its analyses. + PassPA = CGAM.invalidate(C, std::move(PassPA)); + + // Then intersect the preserved set so that invalidation of module + // analyses will eventually occur when the module pass completes. + PA.intersect(std::move(PassPA)); + } // By definition we preserve the proxy. This precludes *any* invalidation // of CGSCC analyses by the proxy, but that's OK because we've taken @@ -446,8 +447,8 @@ public: FAM = &AM->getResult<FunctionAnalysisManagerCGSCCProxy>(C).getManager(); PreservedAnalyses PA = PreservedAnalyses::all(); - for (LazyCallGraph::Node *N : C) { - PreservedAnalyses PassPA = Pass.run(N->getFunction(), FAM); + for (LazyCallGraph::Node &N : C) { + PreservedAnalyses PassPA = Pass.run(N.getFunction(), FAM); // We know that the function pass couldn't have invalidated any other // function's analyses (that's the contract of a function pass), so @@ -455,7 +456,7 @@ public: // Also, update the preserved analyses to reflect that once invalidated // these can again be preserved. if (FAM) - PassPA = FAM->invalidate(N->getFunction(), std::move(PassPA)); + PassPA = FAM->invalidate(N.getFunction(), std::move(PassPA)); // Then intersect the preserved set so that invalidation of module // analyses will eventually occur when the module pass completes. diff --git a/llvm/include/llvm/Analysis/LazyCallGraph.h b/llvm/include/llvm/Analysis/LazyCallGraph.h index d3bd2d19d7e..743b9890b3d 100644 --- a/llvm/include/llvm/Analysis/LazyCallGraph.h +++ b/llvm/include/llvm/Analysis/LazyCallGraph.h @@ -49,6 +49,7 @@ #include "llvm/IR/PassManager.h" #include "llvm/Support/Allocator.h" #include <iterator> +#include <utility> namespace llvm { class PreservedAnalyses; @@ -104,7 +105,9 @@ class LazyCallGraph { public: class Node; class SCC; + class RefSCC; class edge_iterator; + class call_edge_iterator; /// A class used to represent edges in the call graph. /// @@ -172,7 +175,11 @@ public: Node &getNode(LazyCallGraph &G); private: + friend class LazyCallGraph::Node; + PointerIntPair<PointerUnion<Function *, Node *>, 1, Kind> Value; + + void setKind(Kind K) { Value.setInt(K); } }; typedef SmallVector<Edge, 4> EdgeVectorT; @@ -191,12 +198,13 @@ public: Function &F; // We provide for the DFS numbering and Tarjan walk lowlink numbers to be - // stored directly within the node. + // stored directly within the node. These are both '-1' when nodes are part + // of an SCC (or RefSCC), or '0' when not yet reached in a DFS walk. int DFSNumber; int LowLink; mutable EdgeVectorT Edges; - DenseMap<Function *, size_t> EdgeIndexMap; + DenseMap<Function *, int> EdgeIndexMap; /// Basic constructor implements the scanning of F into Edges and /// EdgeIndexMap. @@ -208,12 +216,13 @@ public: /// Internal helper to insert an edge to a node. void insertEdgeInternal(Node &ChildN, Edge::Kind EK); + /// Internal helper to change an edge kind. + void setEdgeKind(Function &ChildF, Edge::Kind EK); + /// Internal helper to remove the edge to the given function. void removeEdgeInternal(Function &ChildF); public: - typedef LazyCallGraph::edge_iterator edge_iterator; - LazyCallGraph &getGraph() const { return *G; } Function &getFunction() const { return F; } @@ -223,6 +232,24 @@ public: } edge_iterator end() const { return edge_iterator(Edges.end(), Edges.end()); } + const Edge &operator[](int i) const { return Edges[i]; } + const Edge &operator[](Function &F) const { + assert(EdgeIndexMap.find(&F) != EdgeIndexMap.end() && "No such edge!"); + return Edges[EdgeIndexMap.find(&F)->second]; + } + const Edge &operator[](Node &N) const { return (*this)[N.getFunction()]; } + + call_edge_iterator call_begin() const { + return call_edge_iterator(Edges.begin(), Edges.end()); + } + call_edge_iterator call_end() const { + return call_edge_iterator(Edges.end(), Edges.end()); + } + + iterator_range<call_edge_iterator> calls() const { + return make_range(call_begin(), call_end()); + } + /// Equality is defined as address equality. bool operator==(const Node &N) const { return this == &N; } bool operator!=(const Node &N) const { return !operator==(N); } @@ -301,60 +328,146 @@ public: /// An SCC of the call graph. /// - /// This represents a Strongly Connected Component of the call graph as + /// This represents a Strongly Connected Component of the direct call graph + /// -- ignoring indirect calls and function references. It stores this as /// a collection of call graph nodes. While the order of nodes in the SCC is /// stable, it is not any particular order. + /// + /// The SCCs are nested within a \c RefSCC, see below for details about that + /// outer structure. SCCs do not support mutation of the call graph, that + /// must be done through the containing \c RefSCC in order to fully reason + /// about the ordering and connections of the graph. class SCC { friend class LazyCallGraph; friend class LazyCallGraph::Node; - LazyCallGraph *G; - SmallPtrSet<SCC *, 1> ParentSCCs; + RefSCC *OuterRefSCC; SmallVector<Node *, 1> Nodes; - SCC(LazyCallGraph &G) : G(&G) {} + template <typename NodeRangeT> + SCC(RefSCC &OuterRefSCC, NodeRangeT &&Nodes) + : OuterRefSCC(&OuterRefSCC), Nodes(std::forward<NodeRangeT>(Nodes)) {} - void insert(Node &N); + void clear() { + OuterRefSCC = nullptr; + Nodes.clear(); + } - void - internalDFS(SmallVectorImpl<std::pair<Node *, Node::edge_iterator>> &DFSStack, - SmallVectorImpl<Node *> &PendingSCCStack, Node *N, - SmallVectorImpl<SCC *> &ResultSCCs); +#ifndef NDEBUG + /// Verify invariants about the SCC. + /// + /// This will attempt to validate all of the basic invariants within an + /// SCC, but not that it is a strongly connected componet per-se. Primarily + /// useful while building and updating the graph to check that basic + /// properties are in place rather than having inexplicable crashes later. + void verify(); +#endif public: - typedef SmallVectorImpl<Node *>::const_iterator iterator; - typedef pointee_iterator<SmallPtrSet<SCC *, 1>::const_iterator> - parent_iterator; + typedef pointee_iterator<SmallVectorImpl<Node *>::const_iterator> iterator; iterator begin() const { return Nodes.begin(); } iterator end() const { return Nodes.end(); } - parent_iterator parent_begin() const { return ParentSCCs.begin(); } - parent_iterator parent_end() const { return ParentSCCs.end(); } + int size() const { return Nodes.size(); } + + RefSCC &getOuterRefSCC() const { return *OuterRefSCC; } + + /// Short name useful for debugging or logging. + /// + /// We use the name of the first function in the SCC to name the SCC for + /// the purposes of debugging and logging. + StringRef getName() const { return begin()->getFunction().getName(); } + }; + + /// A RefSCC of the call graph. + /// + /// This models a Strongly Connected Component of function reference edges in + /// the call graph. As opposed to actual SCCs, these can be used to scope + /// subgraphs of the module which are independent from other subgraphs of the + /// module because they do not reference it in any way. This is also the unit + /// where we do mutation of the graph in order to restrict mutations to those + /// which don't violate this independence. + /// + /// A RefSCC contains a DAG of actual SCCs. All the nodes within the RefSCC + /// are necessarily within some actual SCC that nests within it. Since + /// a direct call *is* a reference, there will always be at least one RefSCC + /// around any SCC. + class RefSCC { + friend class LazyCallGraph; + friend class LazyCallGraph::Node; + + LazyCallGraph *G; + SmallPtrSet<RefSCC *, 1> Parents; + + /// A postorder list of the inner SCCs. + SmallVector<SCC *, 4> SCCs; + + /// A map from SCC to index in the postorder list. + SmallDenseMap<SCC *, int, 4> SCCIndices; + + /// Fast-path constructor. RefSCCs should instead be constructed by calling + /// formRefSCCFast on the graph itself. + RefSCC(LazyCallGraph &G); + +#ifndef NDEBUG + /// Verify invariants about the RefSCC and all its SCCs. + /// + /// This will attempt to validate all of the invariants *within* the + /// RefSCC, but not that it is a strongly connected component of the larger + /// graph. This makes it useful even when partially through an update. + /// + /// Invariants checked: + /// - SCCs and their indices match. + /// - The SCCs list is in fact in post-order. + void verify(); +#endif + + public: + typedef pointee_iterator<SmallVectorImpl<SCC *>::const_iterator> iterator; + typedef iterator_range<iterator> range; + typedef pointee_iterator<SmallPtrSetImpl<RefSCC *>::const_iterator> + parent_iterator; + + iterator begin() const { return SCCs.begin(); } + iterator end() const { return SCCs.end(); } + + ssize_t size() const { return SCCs.size(); } + + SCC &operator[](int Idx) { return *SCCs[Idx]; } + + iterator find(SCC &C) const { + return SCCs.begin() + SCCIndices.find(&C)->second; + } + + parent_iterator parent_begin() const { return Parents.begin(); } + parent_iterator parent_end() const { return Parents.end(); } iterator_range<parent_iterator> parents() const { return make_range(parent_begin(), parent_end()); } /// Test if this SCC is a parent of \a C. - bool isParentOf(const SCC &C) const { return C.isChildOf(*this); } + bool isParentOf(const RefSCC &C) const { return C.isChildOf(*this); } - /// Test if this SCC is an ancestor of \a C. - bool isAncestorOf(const SCC &C) const { return C.isDescendantOf(*this); } + /// Test if this RefSCC is an ancestor of \a C. + bool isAncestorOf(const RefSCC &C) const { return C.isDescendantOf(*this); } - /// Test if this SCC is a child of \a C. - bool isChildOf(const SCC &C) const { - return ParentSCCs.count(const_cast<SCC *>(&C)); + /// Test if this RefSCC is a child of \a C. + bool isChildOf(const RefSCC &C) const { + return Parents.count(const_cast<RefSCC *>(&C)); } - /// Test if this SCC is a descendant of \a C. - bool isDescendantOf(const SCC &C) const; + /// Test if this RefSCC is a descendant of \a C. + bool isDescendantOf(const RefSCC &C) const; /// Short name useful for debugging or logging. /// /// We use the name of the first function in the SCC to name the SCC for /// the purposes of debugging and logging. - StringRef getName() const { return (*begin())->getFunction().getName(); } + StringRef getName() const { + return begin()->begin()->getFunction().getName(); + } ///@{ /// \name Mutation API @@ -365,81 +478,151 @@ public: /// Note that these methods sometimes have complex runtimes, so be careful /// how you call them. - /// Insert an edge from one node in this SCC to another in this SCC. + /// Make an existing internal ref edge into a call edge. + /// + /// This may form a larger cycle and thus collapse SCCs into TargetN's SCC. + /// If that happens, the deleted SCC pointers are returned. These SCCs are + /// not in a valid state any longer but the pointers will remain valid + /// until destruction of the parent graph instance for the purpose of + /// clearing cached information. + /// + /// After this operation, both SourceN's SCC and TargetN's SCC may move + /// position within this RefSCC's postorder list. Any SCCs merged are + /// merged into the TargetN's SCC in order to preserve reachability analyses + /// which took place on that SCC. + SmallVector<SCC *, 1> switchInternalEdgeToCall(Node &SourceN, + Node &TargetN); + + /// Make an existing internal call edge into a ref edge. + /// + /// If SourceN and TargetN are part of a single SCC, it may be split up due + /// to breaking a cycle in the call edges that formed it. If that happens, + /// then this routine will insert new SCCs into the postorder list *before* + /// the SCC of TargetN (previously the SCC of both). This preserves + /// postorder as the TargetN can reach all of the other nodes by definition + /// of previously being in a single SCC formed by the cycle from SourceN to + /// TargetN. The newly added nodes are added *immediately* and contiguously + /// prior to the TargetN SCC and so they may be iterated starting from + /// there. + void switchInternalEdgeToRef(Node &SourceN, Node &TargetN); + + /// Make an existing outgoing ref edge into a call edge. + /// + /// Note that this is trivial as there are no cyclic impacts and there + /// remains a reference edge. + void switchOutgoingEdgeToCall(Node &SourceN, Node &TargetN); + + /// Make an existing outgoing call edge into a ref edge. /// - /// By the definition of an SCC, this does not change the nature or make-up - /// of any SCCs. - void insertIntraSCCEdge(Node &ParentN, Node &ChildN, Edge::Kind EK); + /// This is trivial as there are no cyclic impacts and there remains + /// a reference edge. + void switchOutgoingEdgeToRef(Node &SourceN, Node &TargetN); - /// Insert an edge whose tail is in this SCC and head is in some child SCC. + /// Insert a ref edge from one node in this RefSCC to another in this + /// RefSCC. + /// + /// This is always a trivial operation as it doesn't change any part of the + /// graph structure besides connecting the two nodes. /// - /// There must be an existing path from the caller to the callee. This - /// operation is inexpensive and does not change the set of SCCs in the - /// graph. - void insertOutgoingEdge(Node &ParentN, Node &ChildN, Edge::Kind EK); + /// Note that we don't support directly inserting internal *call* edges + /// because that could change the graph structure and requires returning + /// information about what became invalid. As a consequence, the pattern + /// should be to first insert the necessary ref edge, and then to switch it + /// to a call edge if needed and handle any invalidation that results. See + /// the \c switchInternalEdgeToCall routine for details. + void insertInternalRefEdge(Node &SourceN, Node &TargetN); + + /// Insert an edge whose parent is in this RefSCC and child is in some + /// child RefSCC. + /// + /// There must be an existing path from the \p SourceN to the \p TargetN. + /// This operation is inexpensive and does not change the set of SCCs and + /// RefSCCs in the graph. + void insertOutgoingEdge(Node &SourceN, Node &TargetN, Edge::Kind EK); - /// Insert an edge whose tail is in a descendant SCC and head is in this - /// SCC. + /// Insert an edge whose source is in a descendant RefSCC and target is in + /// this RefSCC. + /// + /// There must be an existing path from the target to the source in this + /// case. + /// + /// NB! This is has the potential to be a very expensive function. It + /// inherently forms a cycle in the prior RefSCC DAG and we have to merge + /// RefSCCs to resolve that cycle. But finding all of the RefSCCs which + /// participate in the cycle can in the worst case require traversing every + /// RefSCC in the graph. Every attempt is made to avoid that, but passes + /// must still exercise caution calling this routine repeatedly. /// - /// There must be an existing path from the callee to the caller in this - /// case. NB! This is has the potential to be a very expensive function. It - /// inherently forms a cycle in the prior SCC DAG and we have to merge SCCs - /// to resolve that cycle. But finding all of the SCCs which participate in - /// the cycle can in the worst case require traversing every SCC in the - /// graph. Every attempt is made to avoid that, but passes must still - /// exercise caution calling this routine repeatedly. + /// Also note that this can only insert ref edges. In order to insert + /// a call edge, first insert a ref edge and then switch it to a call edge. + /// These are intentionally kept as separate interfaces because each step + /// of the operation invalidates a different set of data structures. + /// + /// This returns all the RefSCCs which were merged into the this RefSCC + /// (the target's). This allows callers to invalidate any cached + /// information. /// /// FIXME: We could possibly optimize this quite a bit for cases where the /// caller and callee are very nearby in the graph. See comments in the /// implementation for details, but that use case might impact users. - SmallVector<SCC *, 1> insertIncomingEdge(Node &ParentN, Node &ChildN, - Edge::Kind EK); - - /// Remove an edge whose source is in this SCC and target is *not*. - /// - /// This removes an inter-SCC edge. All inter-SCC edges originating from - /// this SCC have been fully explored by any in-flight DFS SCC formation, - /// so this is always safe to call once you have the source SCC. - /// - /// This operation does not change the set of SCCs or the members of the - /// SCCs and so is very inexpensive. It may change the connectivity graph - /// of the SCCs though, so be careful calling this while iterating over - /// them. - void removeInterSCCEdge(Node &ParentN, Node &ChildN); - - /// Remove an edge which is entirely within this SCC. - /// - /// Both the \a ParentN and the \a ChildN must be within this SCC. Removing - /// such an edge make break cycles that form this SCC and thus this - /// operation may change the SCC graph significantly. In particular, this - /// operation will re-form new SCCs based on the remaining connectivity of - /// the graph. The following invariants are guaranteed to hold after - /// calling this method: - /// - /// 1) This SCC is still an SCC in the graph. - /// 2) This SCC will be the parent of any new SCCs. Thus, this SCC is - /// preserved as the root of any new SCC directed graph formed. - /// 3) No SCC other than this SCC has its member set changed (this is + SmallVector<RefSCC *, 1> insertIncomingRefEdge(Node &SourceN, + Node &TargetN); + + /// Remove an edge whose source is in this RefSCC and target is *not*. + /// + /// This removes an inter-RefSCC edge. All inter-RefSCC edges originating + /// from this SCC have been fully explored by any in-flight DFS graph + /// formation, so this is always safe to call once you have the source + /// RefSCC. + /// + /// This operation does not change the cyclic structure of the graph and so + /// is very inexpensive. It may change the connectivity graph of the SCCs + /// though, so be careful calling this while iterating over them. + void removeOutgoingEdge(Node &SourceN, Node &TargetN); + + /// Remove a ref edge which is entirely within this RefSCC. + /// + /// Both the \a SourceN and the \a TargetN must be within this RefSCC. + /// Removing such an edge may break cycles that form this RefSCC and thus + /// this operation may change the RefSCC graph significantly. In + /// particular, this operation will re-form new RefSCCs based on the + /// remaining connectivity of the graph. The following invariants are + /// guaranteed to hold after calling this method: + /// + /// 1) This RefSCC is still a RefSCC in the graph. + /// 2) This RefSCC will be the parent of any new RefSCCs. Thus, this RefSCC + /// is preserved as the root of any new RefSCC DAG formed. + /// 3) No RefSCC other than this RefSCC has its member set changed (this is /// inherent in the definition of removing such an edge). - /// 4) All of the parent links of the SCC graph will be updated to reflect - /// the new SCC structure. - /// 5) All SCCs formed out of this SCC, excluding this SCC, will be - /// returned in a vector. - /// 6) The order of the SCCs in the vector will be a valid postorder - /// traversal of the new SCCs. + /// 4) All of the parent links of the RefSCC graph will be updated to + /// reflect the new RefSCC structure. + /// 5) All RefSCCs formed out of this RefSCC, excluding this RefSCC, will + /// be returned in post-order. + /// 6) The order of the RefSCCs in the vector will be a valid postorder + /// traversal of the new RefSCCs. /// /// These invariants are very important to ensure that we can build - /// optimization pipeliens on top of the CGSCC pass manager which - /// intelligently update the SCC graph without invalidating other parts of - /// the SCC graph. + /// optimization pipelines on top of the CGSCC pass manager which + /// intelligently update the RefSCC graph without invalidating other parts + /// of the RefSCC graph. + /// + /// Note that we provide no routine to remove a *call* edge. Instead, you + /// must first switch it to a ref edge using \c switchInternalEdgeToRef. + /// This split API is intentional as each of these two steps can invalidate + /// a different aspect of the graph structure and needs to have the + /// invalidation handled independently. /// /// The runtime complexity of this method is, in the worst case, O(V+E) - /// where V is the number of nodes in this SCC and E is the number of edges - /// leaving the nodes in this SCC. Note that E includes both edges within - /// this SCC and edges from this SCC to child SCCs. Some effort has been - /// made to minimize the overhead of common cases such as self-edges and - /// edge removals which result in a spanning tree with no more cycles. - SmallVector<SCC *, 1> removeIntraSCCEdge(Node &ParentN, Node &ChildN); + /// where V is the number of nodes in this RefSCC and E is the number of + /// edges leaving the nodes in this RefSCC. Note that E includes both edges + /// within this RefSCC and edges from this RefSCC to child RefSCCs. Some + /// effort has been made to minimize the overhead of common cases such as + /// self-edges and edge removals which result in a spanning tree with no + /// more cycles. There are also detailed comments within the implementation + /// on techniques which could substantially improve this routine's + /// efficiency. + SmallVector<RefSCC *, 1> removeInternalRefEdge(Node &SourceN, + Node &TargetN); ///@} }; @@ -450,9 +633,9 @@ public: /// the call graph, walking it lazily in depth-first post-order. That is, it /// always visits SCCs for a callee prior to visiting the SCC for a caller /// (when they are in different SCCs). - class postorder_scc_iterator - : public iterator_facade_base<postorder_scc_iterator, - std::forward_iterator_tag, SCC> { + class postorder_ref_scc_iterator + : public iterator_facade_base<postorder_ref_scc_iterator, + std::forward_iterator_tag, RefSCC> { friend class LazyCallGraph; friend class LazyCallGraph::Node; @@ -460,27 +643,27 @@ public: struct IsAtEndT {}; LazyCallGraph *G; - SCC *C; + RefSCC *C; // Build the begin iterator for a node. - postorder_scc_iterator(LazyCallGraph &G) : G(&G) { - C = G.getNextSCCInPostOrder(); + postorder_ref_scc_iterator(LazyCallGraph &G) : G(&G) { + C = G.getNextRefSCCInPostOrder(); } // Build the end iterator for a node. This is selected purely by overload. - postorder_scc_iterator(LazyCallGraph &G, IsAtEndT /*Nonce*/) + postorder_ref_scc_iterator(LazyCallGraph &G, IsAtEndT /*Nonce*/) : G(&G), C(nullptr) {} public: - bool operator==(const postorder_scc_iterator &Arg) const { + bool operator==(const postorder_ref_scc_iterator &Arg) const { return G == Arg.G && C == Arg.C; } reference operator*() const { return *C; } using iterator_facade_base::operator++; - postorder_scc_iterator &operator++() { - C = G->getNextSCCInPostOrder(); + postorder_ref_scc_iterator &operator++() { + C = G->getNextRefSCCInPostOrder(); return *this; } }; @@ -502,15 +685,16 @@ public: return edge_iterator(EntryEdges.end(), EntryEdges.end()); } - postorder_scc_iterator postorder_scc_begin() { - return postorder_scc_iterator(*this); + postorder_ref_scc_iterator postorder_ref_scc_begin() { + return postorder_ref_scc_iterator(*this); } - postorder_scc_iterator postorder_scc_end() { - return postorder_scc_iterator(*this, postorder_scc_iterator::IsAtEndT()); + postorder_ref_scc_iterator postorder_ref_scc_end() { + return postorder_ref_scc_iterator(*this, + postorder_ref_scc_iterator::IsAtEndT()); } - iterator_range<postorder_scc_iterator> postorder_sccs() { - return make_range(postorder_scc_begin(), postorder_scc_end()); + iterator_range<postorder_ref_scc_iterator> postorder_ref_sccs() { + return make_range(postorder_ref_scc_begin(), postorder_ref_scc_end()); } /// Lookup a function in the graph which has already been scanned and added. @@ -522,6 +706,17 @@ public: /// iterator walk. SCC *lookupSCC(Node &N) const { return SCCMap.lookup(&N); } + /// Lookup a function's RefSCC in the graph. + /// + /// \returns null if the function hasn't been assigned a RefSCC via the + /// RefSCC iterator walk. + RefSCC *lookupRefSCC(Node &N) const { + if (SCC *C = lookupSCC(N)) + return &C->getOuterRefSCC(); + + return nullptr; + } + /// Get a graph node for a given function, scanning it to populate the graph /// data as necessary. Node &get(Function &F) { @@ -561,6 +756,9 @@ public: ///@} private: + typedef SmallVectorImpl<Node *>::reverse_iterator node_stack_iterator; + typedef iterator_range<node_stack_iterator> node_stack_range; + /// Allocator that holds all the call graph nodes. SpecificBumpPtrAllocator<Node> BPA; @@ -574,7 +772,7 @@ private: EdgeVectorT EntryEdges; /// Map of the entry nodes in the graph to their indices in \c EntryEdges. - DenseMap<Function *, size_t> EntryIndexMap; + DenseMap<Function *, int> EntryIndexMap; /// Allocator that holds all the call graph SCCs. SpecificBumpPtrAllocator<SCC> SCCBPA; @@ -582,19 +780,22 @@ private: /// Maps Function -> SCC for fast lookup. DenseMap<Node *, SCC *> SCCMap; - /// The leaf SCCs of the graph. + /// Allocator that holds all the call graph RefSCCs. + SpecificBumpPtrAllocator<RefSCC> RefSCCBPA; + + /// The leaf RefSCCs of the graph. /// - /// These are all of the SCCs which have no children. - SmallVector<SCC *, 4> LeafSCCs; + /// These are all of the RefSCCs which have no children. + SmallVector<RefSCC *, 4> LeafRefSCCs; /// Stack of nodes in the DFS walk. SmallVector<std::pair<Node *, edge_iterator>, 4> DFSStack; - /// Set of entry nodes not-yet-processed into SCCs. - SmallVector<Function *, 4> SCCEntryNodes; + /// Set of entry nodes not-yet-processed into RefSCCs. + SmallVector<Function *, 4> RefSCCEntryNodes; /// Stack of nodes the DFS has walked but not yet put into a SCC. - SmallVector<Node *, 4> PendingSCCStack; + SmallVector<Node *, 4> PendingRefSCCStack; /// Counter for the next DFS number to assign. int NextDFSNumber; @@ -606,12 +807,31 @@ private: /// Helper to update pointers back to the graph object during moves. void updateGraphPtrs(); - /// Helper to form a new SCC out of the top of a DFSStack-like - /// structure. - SCC *formSCC(Node *RootN, SmallVectorImpl<Node *> &NodeStack); + /// Allocates an SCC and constructs it using the graph allocator. + /// + /// The arguments are forwarded to the constructor. + template <typename... Ts> SCC *createSCC(Ts &&... Args) { + return new (SCCBPA.Allocate()) SCC(std::forward<Ts>(Args)...); + } + + /// Allocates a RefSCC and constructs it using the graph allocator. + /// + /// The arguments are forwarded to the constructor. + template <typename... Ts> RefSCC *createRefSCC(Ts &&... Args) { + return new (RefSCCBPA.Allocate()) RefSCC(std::forward<Ts>(Args)...); + } + + /// Build the SCCs for a RefSCC out of a list of nodes. + void buildSCCs(RefSCC &RC, node_stack_range Nodes); + + /// Connect a RefSCC into the larger graph. + /// + /// This walks the edges to connect the RefSCC to its children's parent set, + /// and updates the root leaf list. + void connectRefSCC(RefSCC &RC); - /// Retrieve the next node in the post-order SCC walk of the call graph. - SCC *getNextSCCInPostOrder(); + /// Retrieve the next node in the post-order RefSCC walk of the call graph. + RefSCC *getNextRefSCCInPostOrder(); }; inline LazyCallGraph::Edge::Edge() : Value() {} diff --git a/llvm/lib/Analysis/LazyCallGraph.cpp b/llvm/lib/Analysis/LazyCallGraph.cpp index 11e1166001a..5de90782a31 100644 --- a/llvm/lib/Analysis/LazyCallGraph.cpp +++ b/llvm/lib/Analysis/LazyCallGraph.cpp @@ -21,7 +21,7 @@ using namespace llvm; #define DEBUG_TYPE "lcg" static void addEdge(SmallVectorImpl<LazyCallGraph::Edge> &Edges, - DenseMap<Function *, size_t> &EdgeIndexMap, Function &F, + DenseMap<Function *, int> &EdgeIndexMap, Function &F, LazyCallGraph::Edge::Kind EK) { // Note that we consider *any* function with a definition to be a viable // edge. Even if the function's definition is subject to replacement by @@ -34,17 +34,16 @@ static void addEdge(SmallVectorImpl<LazyCallGraph::Edge> &Edges, // strong definition's address would be an effective way to determine the // safety of optimizing a direct call edge. if (!F.isDeclaration() && - EdgeIndexMap.insert(std::make_pair(&F, Edges.size())).second) { + EdgeIndexMap.insert({&F, Edges.size()}).second) { DEBUG(dbgs() << " Added callable function: " << F.getName() << "\n"); Edges.emplace_back(LazyCallGraph::Edge(F, EK)); } } -static void findReferences( - SmallVectorImpl<Constant *> &Worklist, - SmallPtrSetImpl<Constant *> &Visited, - SmallVectorImpl<LazyCallGraph::Edge> &Edges, - DenseMap<Function *, size_t> &EdgeIndexMap) { +static void findReferences(SmallVectorImpl<Constant *> &Worklist, + SmallPtrSetImpl<Constant *> &Visited, + SmallVectorImpl<LazyCallGraph::Edge> &Edges, + DenseMap<Function *, int> &EdgeIndexMap) { while (!Worklist.empty()) { Constant *C = Worklist.pop_back_val(); @@ -94,23 +93,27 @@ LazyCallGraph::Node::Node(LazyCallGraph &G, Function &F) findReferences(Worklist, Visited, Edges, EdgeIndexMap); } -void LazyCallGraph::Node::insertEdgeInternal(Function &Child, Edge::Kind EK) { - if (Node *N = G->lookup(Child)) +void LazyCallGraph::Node::insertEdgeInternal(Function &Target, Edge::Kind EK) { + if (Node *N = G->lookup(Target)) return insertEdgeInternal(*N, EK); - EdgeIndexMap.insert(std::make_pair(&Child, Edges.size())); - Edges.emplace_back(Child, EK); + EdgeIndexMap.insert({&Target, Edges.size()}); + Edges.emplace_back(Target, EK); } -void LazyCallGraph::Node::insertEdgeInternal(Node &ChildN, Edge::Kind EK) { - EdgeIndexMap.insert(std::make_pair(&ChildN.getFunction(), Edges.size())); - Edges.emplace_back(ChildN, EK); +void LazyCallGraph::Node::insertEdgeInternal(Node &TargetN, Edge::Kind EK) { + EdgeIndexMap.insert({&TargetN.getFunction(), Edges.size()}); + Edges.emplace_back(TargetN, EK); } -void LazyCallGraph::Node::removeEdgeInternal(Function &Child) { - auto IndexMapI = EdgeIndexMap.find(&Child); +void LazyCallGraph::Node::setEdgeKind(Function &TargetF, Edge::Kind EK) { + Edges[EdgeIndexMap.find(&TargetF)->second].setKind(EK); +} + +void LazyCallGraph::Node::removeEdgeInternal(Function &Target) { + auto IndexMapI = EdgeIndexMap.find(&Target); assert(IndexMapI != EdgeIndexMap.end() && - "Child not in the edge set for this caller?"); + "Target not in the edge set for this caller?"); Edges[IndexMapI->second] = Edge(); EdgeIndexMap.erase(IndexMapI); @@ -121,7 +124,7 @@ LazyCallGraph::LazyCallGraph(Module &M) : NextDFSNumber(0) { << "\n"); for (Function &F : M) if (!F.isDeclaration() && !F.hasLocalLinkage()) - if (EntryIndexMap.insert(std::make_pair(&F, EntryEdges.size())).second) { + if (EntryIndexMap.insert({&F, EntryEdges.size()}).second) { DEBUG(dbgs() << " Adding '" << F.getName() << "' to entry set of the graph.\n"); EntryEdges.emplace_back(F, Edge::Ref); @@ -140,16 +143,16 @@ LazyCallGraph::LazyCallGraph(Module &M) : NextDFSNumber(0) { findReferences(Worklist, Visited, EntryEdges, EntryIndexMap); for (const Edge &E : EntryEdges) - SCCEntryNodes.push_back(&E.getFunction()); + RefSCCEntryNodes.push_back(&E.getFunction()); } LazyCallGraph::LazyCallGraph(LazyCallGraph &&G) : BPA(std::move(G.BPA)), NodeMap(std::move(G.NodeMap)), EntryEdges(std::move(G.EntryEdges)), EntryIndexMap(std::move(G.EntryIndexMap)), SCCBPA(std::move(G.SCCBPA)), - SCCMap(std::move(G.SCCMap)), LeafSCCs(std::move(G.LeafSCCs)), + SCCMap(std::move(G.SCCMap)), LeafRefSCCs(std::move(G.LeafRefSCCs)), DFSStack(std::move(G.DFSStack)), - SCCEntryNodes(std::move(G.SCCEntryNodes)), + RefSCCEntryNodes(std::move(G.RefSCCEntryNodes)), NextDFSNumber(G.NextDFSNumber) { updateGraphPtrs(); } @@ -161,405 +164,1068 @@ LazyCallGraph &LazyCallGraph::operator=(LazyCallGraph &&G) { EntryIndexMap = std::move(G.EntryIndexMap); SCCBPA = std::move(G.SCCBPA); SCCMap = std::move(G.SCCMap); - LeafSCCs = std::move(G.LeafSCCs); + LeafRefSCCs = std::move(G.LeafRefSCCs); DFSStack = std::move(G.DFSStack); - SCCEntryNodes = std::move(G.SCCEntryNodes); + RefSCCEntryNodes = std::move(G.RefSCCEntryNodes); NextDFSNumber = G.NextDFSNumber; updateGraphPtrs(); return *this; } -void LazyCallGraph::SCC::insert(Node &N) { - N.DFSNumber = N.LowLink = -1; - Nodes.push_back(&N); - G->SCCMap[&N] = this; +#ifndef NDEBUG +void LazyCallGraph::SCC::verify() { + assert(OuterRefSCC && "Can't have a null RefSCC!"); + assert(!Nodes.empty() && "Can't have an empty SCC!"); + + for (Node *N : Nodes) { + assert(N && "Can't have a null node!"); + assert(OuterRefSCC->G->lookupSCC(*N) == this && + "Node does not map to this SCC!"); + assert(N->DFSNumber == -1 && + "Must set DFS numbers to -1 when adding a node to an SCC!"); + 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 edge to a raw function!"); + } } +#endif -bool LazyCallGraph::SCC::isDescendantOf(const SCC &C) const { +LazyCallGraph::RefSCC::RefSCC(LazyCallGraph &G) : G(&G) {} + +#ifndef NDEBUG +void LazyCallGraph::RefSCC::verify() { + assert(G && "Can't have a null graph!"); + assert(!SCCs.empty() && "Can't have an empty SCC!"); + + // Verify basic properties of the SCCs. + for (SCC *C : SCCs) { + assert(C && "Can't have a null SCC!"); + C->verify(); + assert(&C->getOuterRefSCC() == this && + "SCC doesn't think it is inside this RefSCC!"); + } + + // Check that our indices map correctly. + for (auto &SCCIndexPair : SCCIndices) { + SCC *C = SCCIndexPair.first; + int i = SCCIndexPair.second; + assert(C && "Can't have a null SCC in the indices!"); + 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 (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 && + "Edge between SCCs violates post-order relationship."); + continue; + } + assert(TargetSCC.getOuterRefSCC().Parents.count(this) && + "Edge to a RefSCC missing us in its parent set."); + } + } +} +#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 SCC *, 4> AncestorWorklist; + SmallVector<const RefSCC *, 4> AncestorWorklist; AncestorWorklist.push_back(this); do { - const SCC *AncestorC = AncestorWorklist.pop_back_val(); + const RefSCC *AncestorC = AncestorWorklist.pop_back_val(); if (AncestorC->isChildOf(C)) return true; - for (const SCC *ParentC : AncestorC->ParentSCCs) + for (const RefSCC *ParentC : AncestorC->Parents) AncestorWorklist.push_back(ParentC); } while (!AncestorWorklist.empty()); return false; } -void LazyCallGraph::SCC::insertIntraSCCEdge(Node &ParentN, Node &ChildN, - Edge::Kind EK) { - // First insert it into the caller. - ParentN.insertEdgeInternal(ChildN, EK); +SmallVector<LazyCallGraph::SCC *, 1> +LazyCallGraph::RefSCC::switchInternalEdgeToCall(Node &SourceN, Node &TargetN) { + assert(!SourceN[TargetN].isCall() && "Must start with a ref edge!"); + + SmallVector<SCC *, 1> DeletedSCCs; + + SCC &SourceSCC = *G->lookupSCC(SourceN); + SCC &TargetSCC = *G->lookupSCC(TargetN); + + // If the two nodes are already part of the same SCC, we're also done as + // we've just added more connectivity. + if (&SourceSCC == &TargetSCC) { + SourceN.setEdgeKind(TargetN.getFunction(), Edge::Call); +#ifndef NDEBUG + // Check that the RefSCC is still valid. + verify(); +#endif + return DeletedSCCs; + } - assert(G->SCCMap.lookup(&ParentN) == this && "Parent must be in this SCC."); - assert(G->SCCMap.lookup(&ChildN) == this && "Child must be in this SCC."); + // At this point we leverage the postorder list of SCCs to detect when the + // insertion of an edge changes the SCC structure in any way. + // + // First and foremost, we can eliminate the need for any changes when the + // edge is toward the beginning of the postorder sequence because all edges + // flow in that direction already. Thus adding a new one cannot form a cycle. + int SourceIdx = SCCIndices[&SourceSCC]; + int TargetIdx = SCCIndices[&TargetSCC]; + if (TargetIdx < SourceIdx) { + SourceN.setEdgeKind(TargetN.getFunction(), Edge::Call); +#ifndef NDEBUG + // Check that the RefSCC is still valid. + verify(); +#endif + return DeletedSCCs; + } - // Nothing changes about this SCC or any other. + // When we do have an edge from an earlier SCC to a later SCC in the + // postorder sequence, all of the SCCs which may be impacted are in the + // closed range of those two within the postorder sequence. The algorithm to + // restore the state is as follows: + // + // 1) Starting from the source SCC, construct a set of SCCs which reach the + // source SCC consisting of just the source SCC. Then scan toward the + // target SCC in postorder and for each SCC, if it has an edge to an SCC + // in the set, add it to the set. Otherwise, the source SCC is not + // a successor, move it in the postorder sequence to immediately before + // the source SCC, shifting the source SCC and all SCCs in the set one + // position toward the target SCC. Stop scanning after processing the + // target SCC. + // 2) If the source SCC is now past the target SCC in the postorder sequence, + // and thus the new edge will flow toward the start, we are done. + // 3) Otherwise, starting from the target SCC, walk all edges which reach an + // SCC between the source and the target, and add them to the set of + // connected SCCs, then recurse through them. Once a complete set of the + // SCCs the target connects to is known, hoist the remaining SCCs between + // the source and the target to be above the target. Note that there is no + // need to process the source SCC, it is already known to connect. + // 4) At this point, all of the SCCs in the closed range between the source + // SCC and the target SCC in the postorder sequence are connected, + // including the target SCC and the source SCC. Inserting the edge from + // the source SCC to the target SCC will form a cycle out of precisely + // these SCCs. Thus we can merge all of the SCCs in this closed range into + // a single SCC. + // + // This process has various important properties: + // - Only mutates the SCCs when adding the edge actually changes the SCC + // structure. + // - Never mutates SCCs which are unaffected by the change. + // - Updates the postorder sequence to correctly satisfy the postorder + // constraint after the edge is inserted. + // - Only reorders SCCs in the closed postorder sequence from the source to + // the target, so easy to bound how much has changed even in the ordering. + // - Big-O is the number of edges in the closed postorder range of SCCs from + // source to target. + + assert(SourceIdx < TargetIdx && "Cannot have equal indices here!"); + SmallPtrSet<SCC *, 4> ConnectedSet; + + // Compute the SCCs which (transitively) reach the source. + ConnectedSet.insert(&SourceSCC); + auto IsConnected = [&](SCC &C) { + for (Node &N : C) + for (Edge &E : N.calls()) { + assert(E.getNode() && "Must have formed a node within an SCC!"); + if (ConnectedSet.count(G->lookupSCC(*E.getNode()))) + return true; + } + + return false; + }; + + for (SCC *C : + make_range(SCCs.begin() + SourceIdx + 1, SCCs.begin() + TargetIdx + 1)) + if (IsConnected(*C)) + ConnectedSet.insert(C); + + // Partition the SCCs in this part of the port-order sequence so only SCCs + // connecting to the source remain between it and the target. This is + // a benign partition as it preserves postorder. + auto SourceI = std::stable_partition( + SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx + 1, + [&ConnectedSet](SCC *C) { return !ConnectedSet.count(C); }); + 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. + if (!ConnectedSet.count(&TargetSCC)) { + assert(SourceI > (SCCs.begin() + SourceIdx) && + "Must have moved the source to fix the post-order."); + assert(*std::prev(SourceI) == &TargetSCC && + "Last SCC to move should have bene the target."); + SourceN.setEdgeKind(TargetN.getFunction(), Edge::Call); +#ifndef NDEBUG + verify(); +#endif + return DeletedSCCs; + } + + assert(SCCs[TargetIdx] == &TargetSCC && + "Should not have moved target if connected!"); + SourceIdx = SourceI - SCCs.begin(); + +#ifndef NDEBUG + // Check that the RefSCC is still valid. + verify(); +#endif + + // 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. + if (SourceIdx + 1 < TargetIdx) { + // Use a normal worklist to find which SCCs the target connects to. We still + // bound the search based on the range in the postorder list we care about, + // but because this is forward connectivity we just "recurse" through the + // edges. + ConnectedSet.clear(); + ConnectedSet.insert(&TargetSCC); + SmallVector<SCC *, 4> Worklist; + Worklist.push_back(&TargetSCC); + do { + SCC &C = *Worklist.pop_back_val(); + for (Node &N : C) + for (Edge &E : N) { + assert(E.getNode() && "Must have formed a node within an SCC!"); + if (!E.isCall()) + continue; + SCC &EdgeC = *G->lookupSCC(*E.getNode()); + if (&EdgeC.getOuterRefSCC() != this) + // Not in this RefSCC... + continue; + if (SCCIndices.find(&EdgeC)->second <= SourceIdx) + // Not in the postorder sequence between source and target. + continue; + + if (ConnectedSet.insert(&EdgeC).second) + Worklist.push_back(&EdgeC); + } + } while (!Worklist.empty()); + + // Partition SCCs so that only SCCs reached from the target remain between + // the source and the target. This preserves postorder. + auto TargetI = std::stable_partition( + SCCs.begin() + SourceIdx + 1, SCCs.begin() + TargetIdx + 1, + [&ConnectedSet](SCC *C) { return ConnectedSet.count(C); }); + 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!"); + +#ifndef NDEBUG + // Check that the RefSCC is still valid. + verify(); +#endif + } + + // 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 + // between the source and target in the postorder sequence participate in that + // cycle. This means that we need to merge all of these SCCs 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 + // other than the set of functions within it will not have changed. + auto MergeRange = + make_range(SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx); + for (SCC *C : MergeRange) { + assert(C != &TargetSCC && + "We merge *into* the target and shouldn't process it here!"); + SCCIndices.erase(C); + TargetSCC.Nodes.append(C->Nodes.begin(), C->Nodes.end()); + for (Node *N : C->Nodes) + G->SCCMap[N] = &TargetSCC; + C->clear(); + DeletedSCCs.push_back(C); + } + + // Erase the merged SCCs from the list and update the indices of the + // remaining SCCs. + int IndexOffset = MergeRange.end() - MergeRange.begin(); + auto EraseEnd = SCCs.erase(MergeRange.begin(), MergeRange.end()); + for (SCC *C : make_range(EraseEnd, SCCs.end())) + SCCIndices[C] -= IndexOffset; + + // Now that the SCC structure is finalized, flip the kind to call. + SourceN.setEdgeKind(TargetN.getFunction(), Edge::Call); + +#ifndef NDEBUG + // And we're done! Verify in debug builds that the RefSCC is coherent. + verify(); +#endif + return DeletedSCCs; } -void LazyCallGraph::SCC::insertOutgoingEdge(Node &ParentN, Node &ChildN, - Edge::Kind EK) { +void LazyCallGraph::RefSCC::switchInternalEdgeToRef(Node &SourceN, + Node &TargetN) { + assert(SourceN[TargetN].isCall() && "Must start with a call edge!"); + + SCC &SourceSCC = *G->lookupSCC(SourceN); + SCC &TargetSCC = *G->lookupSCC(TargetN); + + assert(&SourceSCC.getOuterRefSCC() == this && + "Source must be in this RefSCC."); + assert(&TargetSCC.getOuterRefSCC() == this && + "Target must be in this RefSCC."); + + // Set the edge kind. + SourceN.setEdgeKind(TargetN.getFunction(), Edge::Ref); + + // If this call edge is just connecting two separate SCCs within this RefSCC, + // there is nothing to do. + if (&SourceSCC != &TargetSCC) { +#ifndef NDEBUG + // Check that the RefSCC is still valid. + verify(); +#endif + return; + } + + // Otherwise we are removing a call edge from a single SCC. This may break + // the cycle. In order to compute the new set of SCCs, we need to do a small + // DFS over the nodes within the SCC to form any sub-cycles that remain as + // distinct SCCs and compute a postorder over the resulting SCCs. + // + // However, we specially handle the target node. The target node is known to + // reach all other nodes in the original SCC by definition. This means that + // we want the old SCC to be replaced with an SCC contaning that node as it + // will be the root of whatever SCC DAG results from the DFS. Assumptions + // about an SCC such as the set of functions called will continue to hold, + // etc. + + SCC &OldSCC = TargetSCC; + SmallVector<std::pair<Node *, call_edge_iterator>, 16> DFSStack; + SmallVector<Node *, 16> PendingSCCStack; + SmallVector<SCC *, 4> NewSCCs; + + // Prepare the nodes for a fresh DFS. + SmallVector<Node *, 16> Worklist; + Worklist.swap(OldSCC.Nodes); + for (Node *N : Worklist) { + N->DFSNumber = N->LowLink = 0; + G->SCCMap.erase(N); + } + + // Force the target node to be in the old SCC. This also enables us to take + // a very significant short-cut in the standard Tarjan walk to re-form SCCs + // below: whenever we build an edge that reaches the target node, we know + // that the target node eventually connects back to 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 this connection, and instead + // by relying on the fundamental guarantee coming into this operation (all + // nodes are reachable from the target due to previously forming an SCC). + TargetN.DFSNumber = TargetN.LowLink = -1; + OldSCC.Nodes.push_back(&TargetN); + G->SCCMap[&TargetN] = &OldSCC; + + // Scan down the stack and DFS across the call edges. + for (Node *RootN : Worklist) { + assert(DFSStack.empty() && + "Cannot begin a new root with a non-empty DFS stack!"); + assert(PendingSCCStack.empty() && + "Cannot begin a new root with pending nodes for an SCC!"); + + // Skip any nodes we've already reached in the DFS. + if (RootN->DFSNumber != 0) { + assert(RootN->DFSNumber == -1 && + "Shouldn't have any mid-DFS root nodes!"); + continue; + } + + RootN->DFSNumber = RootN->LowLink = 1; + int NextDFSNumber = 2; + + DFSStack.push_back({RootN, RootN->call_begin()}); + do { + Node *N; + call_edge_iterator I; + std::tie(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}); + + assert(!G->SCCMap.count(&ChildN) && + "Found a node with 0 DFS number but already in an SCC!"); + ChildN.DFSNumber = ChildN.LowLink = NextDFSNumber++; + N = &ChildN; + I = N->call_begin(); + E = N->call_end(); + continue; + } + + // Check for the child already being part of some component. + if (ChildN.DFSNumber == -1) { + if (G->lookupSCC(ChildN) == &OldSCC) { + // If the child is part of the old SCC, we know that it can reach + // every other node, so we have formed a cycle. Pull the entire DFS + // and pending stacks into it. See the comment above about setting + // up the old SCC for why we do this. + int OldSize = OldSCC.size(); + OldSCC.Nodes.push_back(N); + OldSCC.Nodes.append(PendingSCCStack.begin(), PendingSCCStack.end()); + PendingSCCStack.clear(); + while (!DFSStack.empty()) + OldSCC.Nodes.push_back(DFSStack.pop_back_val().first); + for (Node &N : make_range(OldSCC.begin() + OldSize, OldSCC.end())) { + N.DFSNumber = N.LowLink = -1; + G->SCCMap[&N] = &OldSCC; + } + N = nullptr; + break; + } + + // If the child has already been added to some child component, it + // couldn't impact the low-link of this parent because it isn't + // connected, and thus its low-link isn't relevant so skip it. + ++I; + continue; + } + + // Track the lowest linked child as the lowest link for this node. + assert(ChildN.LowLink > 0 && "Must have a positive low-link number!"); + if (ChildN.LowLink < N->LowLink) + N->LowLink = ChildN.LowLink; + + // Move to the next edge. + ++I; + } + if (!N) + // Cleared the DFS early, start another round. + break; + + // We've finished processing N and its descendents, put it on our pending + // SCC stack to eventually get merged into an SCC of nodes. + PendingSCCStack.push_back(N); + + // If this node is linked to some lower entry, continue walking up the + // stack. + if (N->LowLink != N->DFSNumber) + continue; + + // Otherwise, we've completed an SCC. Append it to our post order list of + // SCCs. + int RootDFSNumber = N->DFSNumber; + // Find the range of the node stack by walking down until we pass the + // root DFS number. + auto SCCNodes = make_range( + PendingSCCStack.rbegin(), + std::find_if(PendingSCCStack.rbegin(), PendingSCCStack.rend(), + [RootDFSNumber](Node *N) { + return N->DFSNumber < RootDFSNumber; + })); + + // Form a new SCC out of these nodes and then clear them off our pending + // stack. + NewSCCs.push_back(G->createSCC(*this, SCCNodes)); + for (Node &N : *NewSCCs.back()) { + N.DFSNumber = N.LowLink = -1; + G->SCCMap[&N] = NewSCCs.back(); + } + PendingSCCStack.erase(SCCNodes.end().base(), PendingSCCStack.end()); + } while (!DFSStack.empty()); + } + + // 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. + int OldIdx = SCCIndices[&OldSCC]; + SCCs.insert(SCCs.begin() + OldIdx, NewSCCs.begin(), NewSCCs.end()); + + // Update the mapping from SCC* to index to use the new SCC*s, and remove the + // old SCC from the mapping. + for (int Idx = OldIdx, Size = SCCs.size(); Idx < Size; ++Idx) + SCCIndices[SCCs[Idx]] = Idx; + +#ifndef NDEBUG + // We're done. Check the validity on our way out. + verify(); +#endif +} + +void LazyCallGraph::RefSCC::switchOutgoingEdgeToCall(Node &SourceN, + Node &TargetN) { + assert(!SourceN[TargetN].isCall() && "Must start with a ref edge!"); + + assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC."); + assert(G->lookupRefSCC(TargetN) != this && + "Target must not be in this RefSCC."); + assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) && + "Target must be a descendant of the Source."); + + // Edges between RefSCCs are the same regardless of call or ref, so we can + // just flip the edge here. + SourceN.setEdgeKind(TargetN.getFunction(), Edge::Call); + +#ifndef NDEBUG + // Check that the RefSCC is still valid. + verify(); +#endif +} + +void LazyCallGraph::RefSCC::switchOutgoingEdgeToRef(Node &SourceN, + Node &TargetN) { + assert(SourceN[TargetN].isCall() && "Must start with a call edge!"); + + assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC."); + assert(G->lookupRefSCC(TargetN) != this && + "Target must not be in this RefSCC."); + assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) && + "Target must be a descendant of the Source."); + + // Edges between RefSCCs are the same regardless of call or ref, so we can + // just flip the edge here. + SourceN.setEdgeKind(TargetN.getFunction(), Edge::Ref); + +#ifndef NDEBUG + // Check that the RefSCC is still valid. + verify(); +#endif +} + +void LazyCallGraph::RefSCC::insertInternalRefEdge(Node &SourceN, + Node &TargetN) { + assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC."); + assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC."); + + SourceN.insertEdgeInternal(TargetN, Edge::Ref); + +#ifndef NDEBUG + // Check that the RefSCC is still valid. + verify(); +#endif +} + +void LazyCallGraph::RefSCC::insertOutgoingEdge(Node &SourceN, Node &TargetN, + Edge::Kind EK) { // First insert it into the caller. - ParentN.insertEdgeInternal(ChildN, EK); + SourceN.insertEdgeInternal(TargetN, EK); - assert(G->SCCMap.lookup(&ParentN) == this && "Parent must be in this SCC."); + assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC."); - SCC &ChildC = *G->SCCMap.lookup(&ChildN); - assert(&ChildC != this && "Child must not be in this SCC."); - assert(ChildC.isDescendantOf(*this) && - "Child must be a descendant of the Parent."); + RefSCC &TargetC = *G->lookupRefSCC(TargetN); + assert(&TargetC != this && "Target must not be in this RefSCC."); + assert(TargetC.isDescendantOf(*this) && + "Target must be a descendant of the Source."); // The only change required is to add this SCC to the parent set of the // callee. - ChildC.ParentSCCs.insert(this); + TargetC.Parents.insert(this); + +#ifndef NDEBUG + // Check that the RefSCC is still valid. + verify(); +#endif } -SmallVector<LazyCallGraph::SCC *, 1> -LazyCallGraph::SCC::insertIncomingEdge(Node &ParentN, Node &ChildN, - Edge::Kind EK) { - // First insert it into the caller. - ParentN.insertEdgeInternal(ChildN, EK); +SmallVector<LazyCallGraph::RefSCC *, 1> +LazyCallGraph::RefSCC::insertIncomingRefEdge(Node &SourceN, Node &TargetN) { + assert(G->lookupRefSCC(TargetN) == this && "Target must be in this SCC."); - assert(G->SCCMap.lookup(&ChildN) == this && "Child must be in this SCC."); + // We store the RefSCCs found to be connected in postorder so that we can use + // that when merging. We also return this to the caller to allow them to + // invalidate information pertaining to these RefSCCs. + SmallVector<RefSCC *, 1> Connected; - SCC &ParentC = *G->SCCMap.lookup(&ParentN); - assert(&ParentC != this && "Parent must not be in this SCC."); - assert(ParentC.isDescendantOf(*this) && - "Parent must be a descendant of the Child."); + RefSCC &SourceC = *G->lookupRefSCC(SourceN); + assert(&SourceC != this && "Source must not be in this SCC."); + assert(SourceC.isDescendantOf(*this) && + "Source must be a descendant of the Target."); // The algorithm we use for merging SCCs based on the cycle introduced here - // is to walk the SCC inverted DAG formed by the parent SCC sets. The inverse - // graph has the same cycle properties as the actual DAG of the SCCs, and - // when forming SCCs lazily by a DFS, the bottom of the graph won't exist in - // many cases which should prune the search space. + // is to walk the RefSCC inverted DAG formed by the parent sets. The inverse + // graph has the same cycle properties as the actual DAG of the RefSCCs, and + // when forming RefSCCs lazily by a DFS, the bottom of the graph won't exist + // in many cases which should prune the search space. // - // FIXME: We can get this pruning behavior even after the incremental SCC + // FIXME: We can get this pruning behavior even after the incremental RefSCC // formation by leaving behind (conservative) DFS numberings in the nodes, // and pruning the search with them. These would need to be cleverly updated // during the removal of intra-SCC edges, but could be preserved // conservatively. + // + // FIXME: This operation currently creates ordering stability problems + // because we don't use stably ordered containers for the parent SCCs. - // The set of SCCs that are connected to the caller, and thus will + // The set of RefSCCs that are connected to the parent, and thus will // participate in the merged connected component. - SmallPtrSet<SCC *, 8> ConnectedSCCs; - ConnectedSCCs.insert(this); - ConnectedSCCs.insert(&ParentC); + SmallPtrSet<RefSCC *, 8> ConnectedSet; + ConnectedSet.insert(this); // We build up a DFS stack of the parents chains. - SmallVector<std::pair<SCC *, SCC::parent_iterator>, 8> DFSSCCs; - SmallPtrSet<SCC *, 8> VisitedSCCs; + SmallVector<std::pair<RefSCC *, parent_iterator>, 8> DFSStack; + SmallPtrSet<RefSCC *, 8> Visited; int ConnectedDepth = -1; - SCC *C = this; - parent_iterator I = parent_begin(), E = parent_end(); - for (;;) { + DFSStack.push_back({&SourceC, SourceC.parent_begin()}); + do { + auto DFSPair = DFSStack.pop_back_val(); + RefSCC *C = DFSPair.first; + parent_iterator I = DFSPair.second; + auto E = C->parent_end(); + while (I != E) { - SCC &ParentSCC = *I++; + RefSCC &Parent = *I++; // If we have already processed this parent SCC, skip it, and remember // whether it was connected so we don't have to check the rest of the // stack. This also handles when we reach a child of the 'this' SCC (the // callee) which terminates the search. - if (ConnectedSCCs.count(&ParentSCC)) { - ConnectedDepth = std::max<int>(ConnectedDepth, DFSSCCs.size()); + if (ConnectedSet.count(&Parent)) { + assert(ConnectedDepth < (int)DFSStack.size() && + "Cannot have a connected depth greater than the DFS depth!"); + ConnectedDepth = DFSStack.size(); continue; } - if (VisitedSCCs.count(&ParentSCC)) + if (Visited.count(&Parent)) continue; // We fully explore the depth-first space, adding nodes to the connected // set only as we pop them off, so "recurse" by rotating to the parent. - DFSSCCs.push_back(std::make_pair(C, I)); - C = &ParentSCC; - I = ParentSCC.parent_begin(); - E = ParentSCC.parent_end(); + DFSStack.push_back({C, I}); + C = &Parent; + I = C->parent_begin(); + E = C->parent_end(); } // If we've found a connection anywhere below this point on the stack (and // thus up the parent graph from the caller), the current node needs to be // added to the connected set now that we've processed all of its parents. - if ((int)DFSSCCs.size() == ConnectedDepth) { + if ((int)DFSStack.size() == ConnectedDepth) { --ConnectedDepth; // We're finished with this connection. - ConnectedSCCs.insert(C); + bool Inserted = ConnectedSet.insert(C).second; + (void)Inserted; + assert(Inserted && "Cannot insert a refSCC multiple times!"); + Connected.push_back(C); } else { // Otherwise remember that its parents don't ever connect. - assert(ConnectedDepth < (int)DFSSCCs.size() && + assert(ConnectedDepth < (int)DFSStack.size() && "Cannot have a connected depth greater than the DFS depth!"); - VisitedSCCs.insert(C); + Visited.insert(C); } - - if (DFSSCCs.empty()) - break; // We've walked all the parents of the caller transitively. - - // Pop off the prior node and position to unwind the depth first recursion. - std::tie(C, I) = DFSSCCs.pop_back_val(); - E = C->parent_end(); - } + } while (!DFSStack.empty()); // Now that we have identified all of the SCCs which need to be merged into // a connected set with the inserted edge, merge all of them into this SCC. - // FIXME: This operation currently creates ordering stability problems - // because we don't use stably ordered containers for the parent SCCs or the - // connected SCCs. - unsigned NewNodeBeginIdx = Nodes.size(); - for (SCC *C : ConnectedSCCs) { - if (C == this) - continue; - for (SCC *ParentC : C->ParentSCCs) - if (!ConnectedSCCs.count(ParentC)) - ParentSCCs.insert(ParentC); - C->ParentSCCs.clear(); - - for (Node *N : *C) { - for (Edge &E : *N) { - assert(E.getNode() && "Cannot have a null node within a visited SCC!"); - SCC &ChildC = *G->SCCMap.lookup(E.getNode()); - if (&ChildC != C) - ChildC.ParentSCCs.erase(C); + // We walk the newly connected RefSCCs in the reverse postorder of the parent + // DAG walk above and merge in each of their SCC postorder lists. This + // ensures a merged postorder SCC list. + SmallVector<SCC *, 16> MergedSCCs; + int SCCIndex = 0; + for (RefSCC *C : reverse(Connected)) { + assert(C != this && + "This RefSCC should terminate the DFS without being reached."); + + // Merge the parents which aren't part of the merge into the our parents. + for (RefSCC *ParentC : C->Parents) + if (!ConnectedSet.count(ParentC)) + Parents.insert(ParentC); + C->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 + // walk by updating the parent sets in some other manner. + for (SCC &InnerC : *C) { + InnerC.OuterRefSCC = this; + SCCIndices[&InnerC] = SCCIndex++; + for (Node &N : InnerC) { + G->SCCMap[&N] = &InnerC; + for (Edge &E : N) { + assert(E.getNode() && + "Cannot have a null node within a visited SCC!"); + RefSCC &ChildRC = *G->lookupRefSCC(*E.getNode()); + if (ConnectedSet.count(&ChildRC)) + continue; + ChildRC.Parents.erase(C); + ChildRC.Parents.insert(this); + } } - G->SCCMap[N] = this; - Nodes.push_back(N); } - C->Nodes.clear(); + + // Now merge in the SCCs. We can actually move here so try to reuse storage + // the first time through. + if (MergedSCCs.empty()) + MergedSCCs = std::move(C->SCCs); + else + MergedSCCs.append(C->SCCs.begin(), C->SCCs.end()); + C->SCCs.clear(); } - for (auto I = Nodes.begin() + NewNodeBeginIdx, E = Nodes.end(); I != E; ++I) - for (Edge &E : **I) { - assert(E.getNode() && "Cannot have a null node within a visited SCC!"); - SCC &ChildC = *G->SCCMap.lookup(E.getNode()); - if (&ChildC != this) - ChildC.ParentSCCs.insert(this); - } + + // Finally append our original SCCs to the merged list and move it into + // place. + for (SCC &InnerC : *this) + SCCIndices[&InnerC] = SCCIndex++; + MergedSCCs.append(SCCs.begin(), SCCs.end()); + SCCs = std::move(MergedSCCs); + + // At this point we have a merged RefSCC with a post-order SCCs list, just + // connect the nodes to form the new edge. + SourceN.insertEdgeInternal(TargetN, Edge::Ref); + +#ifndef NDEBUG + // Check that the RefSCC is still valid. + verify(); +#endif // We return the list of SCCs which were merged so that callers can // invalidate any data they have associated with those SCCs. Note that these // SCCs are no longer in an interesting state (they are totally empty) but // the pointers will remain stable for the life of the graph itself. - return SmallVector<SCC *, 1>(ConnectedSCCs.begin(), ConnectedSCCs.end()); + return Connected; } -void LazyCallGraph::SCC::removeInterSCCEdge(Node &ParentN, Node &ChildN) { +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(std::find(G->LeafRefSCCs.begin(), G->LeafRefSCCs.end(), this) == + G->LeafRefSCCs.end() && + "Cannot have a leaf RefSCC source."); + // First remove it from the node. - ParentN.removeEdgeInternal(ChildN.getFunction()); - - assert(G->SCCMap.lookup(&ParentN) == this && - "The caller must be a member of this SCC."); - - SCC &ChildC = *G->SCCMap.lookup(&ChildN); - assert(&ChildC != this && - "This API only supports the rmoval of inter-SCC edges."); - - assert(std::find(G->LeafSCCs.begin(), G->LeafSCCs.end(), this) == - G->LeafSCCs.end() && - "Cannot have a leaf SCC caller with a different SCC callee."); - - bool HasOtherEdgeToChildC = false; - bool HasOtherChildC = false; - for (Node *N : *this) { - for (Edge &E : *N) { - assert(E.getNode() && "Cannot have a missing node in a visited SCC!"); - SCC &OtherChildC = *G->SCCMap.lookup(E.getNode()); - if (&OtherChildC == &ChildC) { - HasOtherEdgeToChildC = true; - break; + SourceN.removeEdgeInternal(TargetN.getFunction()); + + bool HasOtherEdgeToChildRC = false; + bool HasOtherChildRC = false; + for (SCC *InnerC : SCCs) { + for (Node &N : *InnerC) { + for (Edge &E : N) { + assert(E.getNode() && "Cannot have a missing node in a visited SCC!"); + RefSCC &OtherChildRC = *G->lookupRefSCC(*E.getNode()); + if (&OtherChildRC == &TargetRC) { + HasOtherEdgeToChildRC = true; + break; + } + if (&OtherChildRC != this) + HasOtherChildRC = true; } - if (&OtherChildC != this) - HasOtherChildC = true; + if (HasOtherEdgeToChildRC) + break; } - if (HasOtherEdgeToChildC) + 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 parent SCC no longer connected to the child SCC. If so, we need to - // update the child SCC's map of its parents. - if (!HasOtherEdgeToChildC) { - bool Removed = ChildC.ParentSCCs.erase(this); + // 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 parent SCC in the child SCC's parent list!"); + "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 (ChildC.ParentSCCs.empty()) - DEBUG(dbgs() << "LCG: Update removing " << ParentN.getFunction().getName() - << " -> " << ChildN.getFunction().getName() + 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 Parent SCC a leaf SCC. - if (!HasOtherChildC) - G->LeafSCCs.push_back(this); + // It may make the Source SCC a leaf SCC. + if (!HasOtherChildRC) + G->LeafRefSCCs.push_back(this); + } } -void LazyCallGraph::SCC::internalDFS( - SmallVectorImpl<std::pair<Node *, Node::edge_iterator>> &DFSStack, - SmallVectorImpl<Node *> &PendingSCCStack, Node *N, - SmallVectorImpl<SCC *> &ResultSCCs) { - auto I = N->begin(); - N->LowLink = N->DFSNumber = 1; - int NextDFSNumber = 2; - for (;;) { - assert(N->DFSNumber != 0 && "We should always assign a DFS number " - "before processing a node."); +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"); - // We simulate recursion by popping out of the nested loop and continuing. - auto E = N->end(); - while (I != E) { - Node &ChildN = I->getNode(*G); - if (SCC *ChildSCC = G->SCCMap.lookup(&ChildN)) { - // Check if we have reached a node in the new (known connected) set of - // this SCC. If so, the entire stack is necessarily in that set and we - // can re-start. - if (ChildSCC == this) { - insert(*N); - while (!PendingSCCStack.empty()) - insert(*PendingSCCStack.pop_back_val()); - while (!DFSStack.empty()) - insert(*DFSStack.pop_back_val().first); - return; - } + // First remove the actual edge. + SourceN.removeEdgeInternal(TargetN.getFunction()); - // If this child isn't currently in this SCC, no need to process it. - // However, we do need to remove this SCC from its SCC's parent set. - ChildSCC->ParentSCCs.erase(this); - ++I; - continue; - } + // We return a list of the resulting *new* RefSCCs in post-order. + SmallVector<RefSCC *, 1> Result; - if (ChildN.DFSNumber == 0) { - // 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(std::make_pair(N, I)); + // Direct recursion doesn't impact the SCC graph at all. + if (&SourceN == &TargetN) + 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. + SCC &TargetC = *G->lookupSCC(TargetN); + for (Node &N : TargetC) + PostOrderMapping[&N] = RootPostOrderNumber; + + // 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; - // Continue, resetting to the child node. - ChildN.LowLink = ChildN.DFSNumber = NextDFSNumber++; - N = &ChildN; - I = ChildN.begin(); - E = ChildN.end(); - continue; - } + for (Node &N : *C) + N.DFSNumber = N.LowLink = 0; - // Track the lowest link of the children, if any are still in the stack. - // Any child not on the stack will have a LowLink of -1. - assert(ChildN.LowLink != 0 && - "Low-link must not be zero with a non-zero DFS number."); - if (ChildN.LowLink >= 0 && ChildN.LowLink < N->LowLink) - N->LowLink = ChildN.LowLink; - ++I; - } + Worklist.append(C->Nodes.begin(), C->Nodes.end()); + } - if (N->LowLink == N->DFSNumber) { - ResultSCCs.push_back(G->formSCC(N, PendingSCCStack)); - if (DFSStack.empty()) - return; - } else { - // At this point we know that N cannot ever be an SCC root. Its low-link - // is not its dfs-number, and we've processed all of its children. It is - // just sitting here waiting until some node further down the stack gets - // low-link == dfs-number and pops it off as well. Move it to the pending - // stack which is pulled into the next SCC to be formed. - PendingSCCStack.push_back(N); + auto MarkNodeForSCCNumber = [&PostOrderMapping](Node &N, int Number) { + N.DFSNumber = N.LowLink = -1; + PostOrderMapping[&N] = Number; + }; - assert(!DFSStack.empty() && "We shouldn't have an empty stack!"); + SmallVector<std::pair<Node *, edge_iterator>, 4> DFSStack; + SmallVector<Node *, 4> PendingRefSCCStack; + do { + assert(DFSStack.empty() && + "Cannot begin a new root with a non-empty DFS stack!"); + assert(PendingRefSCCStack.empty() && + "Cannot begin a new root with pending nodes for an SCC!"); + + Node *RootN = Worklist.pop_back_val(); + // Skip any nodes we've already reached in the DFS. + if (RootN->DFSNumber != 0) { + assert(RootN->DFSNumber == -1 && + "Shouldn't have any mid-DFS root nodes!"); + continue; } - N = DFSStack.back().first; - I = DFSStack.back().second; - DFSStack.pop_back(); - } -} + RootN->DFSNumber = RootN->LowLink = 1; + int NextDFSNumber = 2; -SmallVector<LazyCallGraph::SCC *, 1> -LazyCallGraph::SCC::removeIntraSCCEdge(Node &ParentN, Node &ChildN) { - // First remove it from the node. - ParentN.removeEdgeInternal(ChildN.getFunction()); + DFSStack.push_back({RootN, RootN->begin()}); + do { + Node *N; + edge_iterator I; + std::tie(N, I) = DFSStack.pop_back_val(); + auto E = N->end(); + + assert(N->DFSNumber != 0 && "We should always assign a DFS number " + "before processing a node."); + + while (I != E) { + Node &ChildN = I->getNode(*G); + if (ChildN.DFSNumber == 0) { + // 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}); + + // Continue, resetting to the child node. + ChildN.LowLink = ChildN.DFSNumber = NextDFSNumber++; + N = &ChildN; + I = ChildN.begin(); + E = ChildN.end(); + 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; + } - // We return a list of the resulting *new* SCCs in postorder. - SmallVector<SCC *, 1> ResultSCCs; + // 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); + ++I; + continue; + } - // Direct recursion doesn't impact the SCC graph at all. - if (&ParentN == &ChildN) - return ResultSCCs; + // Track the lowest link of the children, if any are still in the stack. + // Any child not on the stack will have a LowLink of -1. + assert(ChildN.LowLink != 0 && + "Low-link must not be zero with a non-zero DFS number."); + if (ChildN.LowLink >= 0 && ChildN.LowLink < N->LowLink) + N->LowLink = ChildN.LowLink; + ++I; + } + if (!N) + // We short-circuited this node. + break; - // The worklist is every node in the original SCC. - SmallVector<Node *, 1> Worklist; - Worklist.swap(Nodes); - for (Node *N : Worklist) { - // The nodes formerly in this SCC are no longer in any SCC. - N->DFSNumber = 0; - N->LowLink = 0; - G->SCCMap.erase(N); - } - assert(Worklist.size() > 1 && "We have to have at least two nodes to have an " - "edge between them that is within the SCC."); - - // The child can already reach every node in this SCC (by definition). It is - // the only node we know will stay inside this SCC. Everything which - // transitively reaches Child will also remain in the SCC. To model this we - // incrementally add any chain of nodes which reaches something in the new - // node set to the new node set. This short circuits one side of the Tarjan's - // walk. - insert(ChildN); - - // We're going to do a full mini-Tarjan's walk using a local stack here. - SmallVector<std::pair<Node *, Node::edge_iterator>, 4> DFSStack; - SmallVector<Node *, 4> PendingSCCStack; - do { - Node *N = Worklist.pop_back_val(); - if (N->DFSNumber == 0) - internalDFS(DFSStack, PendingSCCStack, N, ResultSCCs); + // We've finished processing N and its descendents, put it on our pending + // stack to eventually get merged into a RefSCC. + PendingRefSCCStack.push_back(N); + + // If this node is linked to some lower entry, continue walking up the + // stack. + if (N->LowLink != N->DFSNumber) { + assert(!DFSStack.empty() && + "We never found a viable root for a RefSCC to pop off!"); + continue; + } + + // Otherwise, form a new RefSCC from the top of the pending node stack. + 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(), + std::find_if(PendingRefSCCStack.rbegin(), PendingRefSCCStack.rend(), + [RootDFSNumber](Node *N) { + return N->DFSNumber < RootDFSNumber; + })); + + // 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); + + PendingRefSCCStack.erase(RefSCCNodes.end().base(), + PendingRefSCCStack.end()); + } while (!DFSStack.empty()); assert(DFSStack.empty() && "Didn't flush the entire DFS stack!"); - assert(PendingSCCStack.empty() && "Didn't flush all pending SCC nodes!"); + assert(PendingRefSCCStack.empty() && "Didn't flush all pending nodes!"); } while (!Worklist.empty()); - // Now we need to reconnect the current SCC to the graph. - bool IsLeafSCC = true; - for (Node *N : Nodes) { - for (Edge &E : *N) { - assert(E.getNode() && "Cannot have a missing node in a visited SCC!"); - SCC &ChildSCC = *G->SCCMap.lookup(E.getNode()); - if (&ChildSCC == this) - continue; - ChildSCC.ParentSCCs.insert(this); - IsLeafSCC = false; - } + // 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) + Result.push_back(G->createRefSCC(*G)); + + 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 && + "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; + + RefSCC &RC = *Result[SCCNumber - 1]; + int SCCIndex = RC.SCCs.size(); + RC.SCCs.push_back(C); + 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(std::remove_if(SCCs.begin(), SCCs.end(), + [&](SCC *C) { + return PostOrderMapping.lookup(&*C->begin()) != + RootPostOrderNumber; + }), + SCCs.end()); + +#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) { + assert(E.getNode() && "Cannot have a missing node in a visited SCC!"); + RefSCC &ChildRC = *G->lookupRefSCC(*E.getNode()); + if (&ChildRC == this) + continue; + ChildRC.Parents.insert(this); +#ifndef NDEBUG + IsLeaf = false; +#endif + } + } #ifndef NDEBUG - if (!ResultSCCs.empty()) - assert(!IsLeafSCC && "This SCC cannot be a leaf as we have split out new " - "SCCs by removing this edge."); - if (!std::any_of(G->LeafSCCs.begin(), G->LeafSCCs.end(), - [&](SCC *C) { return C == this; })) - assert(!IsLeafSCC && "This SCC cannot be a leaf as it already had child " - "SCCs before we removed this edge."); + if (!Result.empty()) + assert(!IsLeaf && "This SCC cannot be a leaf as we have split out new " + "SCCs by removing this edge."); + if (!std::any_of(G->LeafRefSCCs.begin(), G->LeafRefSCCs.end(), + [&](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 // If this SCC stopped being a leaf through this edge removal, remove it from - // the leaf SCC list. - if (!IsLeafSCC && !ResultSCCs.empty()) - G->LeafSCCs.erase(std::remove(G->LeafSCCs.begin(), G->LeafSCCs.end(), this), - G->LeafSCCs.end()); + // 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()); // Return the new list of SCCs. - return ResultSCCs; + return Result; } -void LazyCallGraph::insertEdge(Node &ParentN, Function &Child, Edge::Kind EK) { +void LazyCallGraph::insertEdge(Node &SourceN, Function &Target, Edge::Kind EK) { assert(SCCMap.empty() && DFSStack.empty() && "This method cannot be called after SCCs have been formed!"); - return ParentN.insertEdgeInternal(Child, EK); + return SourceN.insertEdgeInternal(Target, EK); } -void LazyCallGraph::removeEdge(Node &ParentN, Function &Child) { +void LazyCallGraph::removeEdge(Node &SourceN, Function &Target) { assert(SCCMap.empty() && DFSStack.empty() && "This method cannot be called after SCCs have been formed!"); - return ParentN.removeEdgeInternal(Child); + return SourceN.removeEdgeInternal(Target); } LazyCallGraph::Node &LazyCallGraph::insertInto(Function &F, Node *&MappedN) { @@ -578,125 +1244,258 @@ void LazyCallGraph::updateGraphPtrs() { Node *N = Worklist.pop_back_val(); N->G = this; for (Edge &E : N->Edges) - if (Node *ChildN = E.getNode()) - Worklist.push_back(ChildN); + if (Node *TargetN = E.getNode()) + Worklist.push_back(TargetN); } } // Process all SCCs updating the graph pointers. { - SmallVector<SCC *, 16> Worklist(LeafSCCs.begin(), LeafSCCs.end()); + SmallVector<RefSCC *, 16> Worklist(LeafRefSCCs.begin(), LeafRefSCCs.end()); while (!Worklist.empty()) { - SCC *C = Worklist.pop_back_val(); - C->G = this; - Worklist.insert(Worklist.end(), C->ParentSCCs.begin(), - C->ParentSCCs.end()); + RefSCC &C = *Worklist.pop_back_val(); + C.G = this; + for (RefSCC &ParentC : C.parents()) + Worklist.push_back(&ParentC); } } } -LazyCallGraph::SCC *LazyCallGraph::formSCC(Node *RootN, - SmallVectorImpl<Node *> &NodeStack) { - // The tail of the stack is the new SCC. Allocate the SCC and pop the stack - // into it. - SCC *NewSCC = new (SCCBPA.Allocate()) SCC(*this); +/// Build the internal SCCs for a RefSCC from a sequence of nodes. +/// +/// Appends the SCCs to the provided vector and updates the map with their +/// indices. Both the vector and map must be empty when passed into this +/// routine. +void LazyCallGraph::buildSCCs(RefSCC &RC, node_stack_range Nodes) { + assert(RC.SCCs.empty() && "Already built SCCs!"); + assert(RC.SCCIndices.empty() && "Already mapped SCC indices!"); - while (!NodeStack.empty() && NodeStack.back()->DFSNumber > RootN->DFSNumber) { - assert(NodeStack.back()->LowLink >= RootN->LowLink && + for (Node *N : Nodes) { + assert(N->LowLink >= (*Nodes.begin())->LowLink && "We cannot have a low link in an SCC lower than its root on the " "stack!"); - NewSCC->insert(*NodeStack.pop_back_val()); + + // This node will go into the next RefSCC, clear out its DFS and low link + // as we scan. + N->DFSNumber = N->LowLink = 0; } - NewSCC->insert(*RootN); - - // A final pass over all edges in the SCC (this remains linear as we only - // do this once when we build the SCC) to connect it to the parent sets of - // its children. - bool IsLeafSCC = true; - for (Node *SCCN : NewSCC->Nodes) - for (Edge &E : *SCCN) { - assert(E.getNode() && "Cannot have a missing node in a visited SCC!"); - SCC &ChildSCC = *SCCMap.lookup(E.getNode()); - if (&ChildSCC == NewSCC) - continue; - ChildSCC.ParentSCCs.insert(NewSCC); - IsLeafSCC = false; + + // Each RefSCC contains a DAG of the call SCCs. To build these, we do + // a direct walk of the call edges using Tarjan's algorithm. We reuse the + // internal storage as we won't need it for the outer graph's DFS any longer. + + SmallVector<std::pair<Node *, call_edge_iterator>, 16> DFSStack; + SmallVector<Node *, 16> PendingSCCStack; + + // Scan down the stack and DFS across the call edges. + for (Node *RootN : Nodes) { + assert(DFSStack.empty() && + "Cannot begin a new root with a non-empty DFS stack!"); + assert(PendingSCCStack.empty() && + "Cannot begin a new root with pending nodes for an SCC!"); + + // Skip any nodes we've already reached in the DFS. + if (RootN->DFSNumber != 0) { + assert(RootN->DFSNumber == -1 && + "Shouldn't have any mid-DFS root nodes!"); + continue; } - // For the SCCs where we fine no child SCCs, add them to the leaf list. - if (IsLeafSCC) - LeafSCCs.push_back(NewSCC); + RootN->DFSNumber = RootN->LowLink = 1; + int NextDFSNumber = 2; + + DFSStack.push_back({RootN, RootN->call_begin()}); + do { + Node *N; + call_edge_iterator I; + std::tie(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}); + + assert(!lookupSCC(ChildN) && + "Found a node with 0 DFS number but already in an SCC!"); + ChildN.DFSNumber = ChildN.LowLink = NextDFSNumber++; + N = &ChildN; + I = N->call_begin(); + E = N->call_end(); + continue; + } + + // If the child has already been added to some child component, it + // couldn't impact the low-link of this parent because it isn't + // connected, and thus its low-link isn't relevant so skip it. + if (ChildN.DFSNumber == -1) { + ++I; + continue; + } + + // Track the lowest linked child as the lowest link for this node. + assert(ChildN.LowLink > 0 && "Must have a positive low-link number!"); + if (ChildN.LowLink < N->LowLink) + N->LowLink = ChildN.LowLink; + + // Move to the next edge. + ++I; + } + + // We've finished processing N and its descendents, put it on our pending + // SCC stack to eventually get merged into an SCC of nodes. + PendingSCCStack.push_back(N); + + // If this node is linked to some lower entry, continue walking up the + // stack. + if (N->LowLink != N->DFSNumber) + continue; + + // Otherwise, we've completed an SCC. Append it to our post order list of + // SCCs. + int RootDFSNumber = N->DFSNumber; + // Find the range of the node stack by walking down until we pass the + // root DFS number. + auto SCCNodes = make_range( + PendingSCCStack.rbegin(), + std::find_if(PendingSCCStack.rbegin(), PendingSCCStack.rend(), + [RootDFSNumber](Node *N) { + return N->DFSNumber < RootDFSNumber; + })); + // Form a new SCC out of these nodes and then clear them off our pending + // stack. + RC.SCCs.push_back(createSCC(RC, SCCNodes)); + for (Node &N : *RC.SCCs.back()) { + N.DFSNumber = N.LowLink = -1; + SCCMap[&N] = RC.SCCs.back(); + } + PendingSCCStack.erase(SCCNodes.end().base(), PendingSCCStack.end()); + } while (!DFSStack.empty()); + } - return NewSCC; + // Wire up the SCC indices. + for (int i = 0, Size = RC.SCCs.size(); i < Size; ++i) + RC.SCCIndices[RC.SCCs[i]] = i; } -LazyCallGraph::SCC *LazyCallGraph::getNextSCCInPostOrder() { - Node *N; - Node::edge_iterator I; - if (!DFSStack.empty()) { - N = DFSStack.back().first; - I = DFSStack.back().second; - DFSStack.pop_back(); - } else { - // If we've handled all candidate entry nodes to the SCC forest, we're done. +// 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) { + assert(E.getNode() && + "Cannot have a missing node in a visited part of the graph!"); + RefSCC &ChildRC = *lookupRefSCC(*E.getNode()); + if (&ChildRC == &RC) + continue; + ChildRC.Parents.insert(&RC); + IsLeaf = false; + } + + // For the SCCs where we fine no child SCCs, add them to the leaf list. + if (IsLeaf) + LeafRefSCCs.push_back(&RC); +} + +LazyCallGraph::RefSCC *LazyCallGraph::getNextRefSCCInPostOrder() { + if (DFSStack.empty()) { + Node *N; do { - if (SCCEntryNodes.empty()) + // If we've handled all candidate entry nodes to the SCC forest, we're + // done. + if (RefSCCEntryNodes.empty()) return nullptr; - N = &get(*SCCEntryNodes.pop_back_val()); + N = &get(*RefSCCEntryNodes.pop_back_val()); } while (N->DFSNumber != 0); - I = N->begin(); + + // Found a new root, begin the DFS here. N->LowLink = N->DFSNumber = 1; NextDFSNumber = 2; + DFSStack.push_back({N, N->begin()}); } for (;;) { - assert(N->DFSNumber != 0 && "We should always assign a DFS number " - "before placing a node onto the stack."); + Node *N; + edge_iterator I; + std::tie(N, I) = DFSStack.pop_back_val(); + + assert(N->DFSNumber > 0 && "We should always assign a DFS number " + "before placing a node onto the stack."); auto E = N->end(); while (I != E) { Node &ChildN = I->getNode(*this); if (ChildN.DFSNumber == 0) { - // 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(std::make_pair(N, N->begin())); + // We haven't yet visited this child, so descend, pushing the current + // node onto the stack. + DFSStack.push_back({N, N->begin()}); - // Recurse onto this node via a tail call. assert(!SCCMap.count(&ChildN) && "Found a node with 0 DFS number but already in an SCC!"); ChildN.LowLink = ChildN.DFSNumber = NextDFSNumber++; N = &ChildN; - I = ChildN.begin(); - E = ChildN.end(); + I = N->begin(); + E = N->end(); + continue; + } + + // If the child has already been added to some child component, it + // couldn't impact the low-link of this parent because it isn't + // connected, and thus its low-link isn't relevant so skip it. + if (ChildN.DFSNumber == -1) { + ++I; continue; } - // Track the lowest link of the children, if any are still in the stack. - assert(ChildN.LowLink != 0 && - "Low-link must not be zero with a non-zero DFS number."); - if (ChildN.LowLink >= 0 && ChildN.LowLink < N->LowLink) + // Track the lowest linked child as the lowest link for this node. + assert(ChildN.LowLink > 0 && "Must have a positive low-link number!"); + if (ChildN.LowLink < N->LowLink) N->LowLink = ChildN.LowLink; + + // Move to the next edge. ++I; } - if (N->LowLink == N->DFSNumber) - // Form the new SCC out of the top of the DFS stack. - return formSCC(N, PendingSCCStack); - - // At this point we know that N cannot ever be an SCC root. Its low-link - // is not its dfs-number, and we've processed all of its children. It is - // just sitting here waiting until some node further down the stack gets - // low-link == dfs-number and pops it off as well. Move it to the pending - // stack which is pulled into the next SCC to be formed. - PendingSCCStack.push_back(N); - - assert(!DFSStack.empty() && "We never found a viable root!"); - N = DFSStack.back().first; - I = DFSStack.back().second; - DFSStack.pop_back(); + // We've finished processing N and its descendents, put it on our pending + // SCC stack to eventually get merged into an SCC of nodes. + PendingRefSCCStack.push_back(N); + + // If this node is linked to some lower entry, continue walking up the + // stack. + if (N->LowLink != N->DFSNumber) { + assert(!DFSStack.empty() && + "We never found a viable root for an SCC to pop off!"); + continue; + } + + // Otherwise, form a new RefSCC from the top of the pending node stack. + int RootDFSNumber = N->DFSNumber; + // Find the range of the node stack by walking down until we pass the + // root DFS number. + auto RefSCCNodes = node_stack_range( + PendingRefSCCStack.rbegin(), + std::find_if( + PendingRefSCCStack.rbegin(), PendingRefSCCStack.rend(), + [RootDFSNumber](Node *N) { return N->DFSNumber < RootDFSNumber; })); + // Form a new RefSCC out of these nodes and then clear them off our pending + // stack. + RefSCC *NewRC = createRefSCC(*this); + buildSCCs(*NewRC, RefSCCNodes); + connectRefSCC(*NewRC); + PendingRefSCCStack.erase(RefSCCNodes.end().base(), + PendingRefSCCStack.end()); + + // We return the new node here. This essentially suspends the DFS walk + // until another RefSCC is requested. + return NewRC; } } @@ -704,17 +1503,7 @@ char LazyCallGraphAnalysis::PassID; LazyCallGraphPrinterPass::LazyCallGraphPrinterPass(raw_ostream &OS) : OS(OS) {} -static void printNodes(raw_ostream &OS, LazyCallGraph::Node &N, - SmallPtrSetImpl<LazyCallGraph::Node *> &Printed) { - LazyCallGraph &G = N.getGraph(); - - // Recurse depth first through the nodes. - for (LazyCallGraph::Edge &E : N) { - LazyCallGraph::Node &ChildN = E.getNode(G); - if (Printed.insert(&ChildN).second) - printNodes(OS, ChildN, Printed); - } - +static void printNode(raw_ostream &OS, LazyCallGraph::Node &N) { OS << " Edges in function: " << N.getFunction().getName() << "\n"; for (const LazyCallGraph::Edge &E : N) OS << " " << (E.isCall() ? "call" : "ref ") << " -> " @@ -723,12 +1512,20 @@ static void printNodes(raw_ostream &OS, LazyCallGraph::Node &N, OS << "\n"; } -static void printSCC(raw_ostream &OS, LazyCallGraph::SCC &SCC) { - ptrdiff_t SCCSize = std::distance(SCC.begin(), SCC.end()); - OS << " SCC with " << SCCSize << " functions:\n"; +static void printSCC(raw_ostream &OS, LazyCallGraph::SCC &C) { + ptrdiff_t Size = std::distance(C.begin(), C.end()); + OS << " SCC with " << Size << " functions:\n"; + + for (LazyCallGraph::Node &N : C) + OS << " " << N.getFunction().getName() << "\n"; +} + +static void printRefSCC(raw_ostream &OS, LazyCallGraph::RefSCC &C) { + ptrdiff_t Size = std::distance(C.begin(), C.end()); + OS << " RefSCC with " << Size << " call SCCs:\n"; - for (LazyCallGraph::Node *N : SCC) - OS << " " << N->getFunction().getName() << "\n"; + for (LazyCallGraph::SCC &InnerC : C) + printSCC(OS, InnerC); OS << "\n"; } @@ -740,15 +1537,11 @@ PreservedAnalyses LazyCallGraphPrinterPass::run(Module &M, OS << "Printing the call graph for module: " << M.getModuleIdentifier() << "\n\n"; - SmallPtrSet<LazyCallGraph::Node *, 16> Printed; - for (LazyCallGraph::Edge &E : G) { - LazyCallGraph::Node &N = E.getNode(G); - if (Printed.insert(&N).second) - printNodes(OS, N, Printed); - } + for (Function &F : M) + printNode(OS, G.get(F)); - for (LazyCallGraph::SCC &SCC : G.postorder_sccs()) - printSCC(OS, SCC); + for (LazyCallGraph::RefSCC &C : G.postorder_ref_sccs()) + printRefSCC(OS, C); return PreservedAnalyses::all(); } diff --git a/llvm/test/Analysis/LazyCallGraph/basic.ll b/llvm/test/Analysis/LazyCallGraph/basic.ll index 418559578b4..edd45ea0e1f 100644 --- a/llvm/test/Analysis/LazyCallGraph/basic.ll +++ b/llvm/test/Analysis/LazyCallGraph/basic.ll @@ -125,52 +125,219 @@ define void @test2() { ret void } +@test3_ptr = external global void ()* + +define void @test3_aa1() { +; CHECK-LABEL: Edges in function: test3_aa1 +; CHECK-NEXT: call -> test3_aa2 +; CHECK-NEXT: ref -> test3_ab1 +; CHECK-NOT: -> + +entry: + call void @test3_aa2() + store void ()* @test3_ab1, void ()** @test3_ptr + ret void +} + +define void @test3_aa2() { +; CHECK-LABEL: Edges in function: test3_aa2 +; CHECK-NEXT: call -> test3_aa1 +; CHECK-NEXT: call -> test3_ab2 +; CHECK-NOT: -> + +entry: + call void @test3_aa1() + call void @test3_ab2() + ret void +} + +define void @test3_ab1() { +; CHECK-LABEL: Edges in function: test3_ab1 +; CHECK-NEXT: call -> test3_ab2 +; CHECK-NEXT: call -> test3_ac1 +; CHECK-NOT: -> + +entry: + call void @test3_ab2() + call void @test3_ac1() + ret void +} + +define void @test3_ab2() { +; CHECK-LABEL: Edges in function: test3_ab2 +; CHECK-NEXT: call -> test3_ab1 +; CHECK-NEXT: call -> test3_ba1 +; CHECK-NOT: -> + +entry: + call void @test3_ab1() + call void @test3_ba1() + ret void +} + +define void @test3_ac1() { +; CHECK-LABEL: Edges in function: test3_ac1 +; CHECK-NEXT: call -> test3_ac2 +; CHECK-NEXT: ref -> test3_aa2 +; CHECK-NOT: -> + +entry: + call void @test3_ac2() + store void ()* @test3_aa2, void ()** @test3_ptr + ret void +} + +define void @test3_ac2() { +; CHECK-LABEL: Edges in function: test3_ac2 +; CHECK-NEXT: call -> test3_ac1 +; CHECK-NEXT: ref -> test3_ba1 +; CHECK-NOT: -> + +entry: + call void @test3_ac1() + store void ()* @test3_ba1, void ()** @test3_ptr + ret void +} + +define void @test3_ba1() { +; CHECK-LABEL: Edges in function: test3_ba1 +; CHECK-NEXT: call -> test3_bb1 +; CHECK-NEXT: ref -> test3_ca1 +; CHECK-NOT: -> + +entry: + call void @test3_bb1() + store void ()* @test3_ca1, void ()** @test3_ptr + ret void +} + +define void @test3_bb1() { +; CHECK-LABEL: Edges in function: test3_bb1 +; CHECK-NEXT: call -> test3_ca2 +; CHECK-NEXT: ref -> test3_ba1 +; CHECK-NOT: -> + +entry: + call void @test3_ca2() + store void ()* @test3_ba1, void ()** @test3_ptr + ret void +} + +define void @test3_ca1() { +; CHECK-LABEL: Edges in function: test3_ca1 +; CHECK-NEXT: call -> test3_ca2 +; CHECK-NOT: -> + +entry: + call void @test3_ca2() + ret void +} + +define void @test3_ca2() { +; CHECK-LABEL: Edges in function: test3_ca2 +; CHECK-NEXT: call -> test3_ca3 +; CHECK-NOT: -> + +entry: + call void @test3_ca3() + ret void +} + +define void @test3_ca3() { +; CHECK-LABEL: Edges in function: test3_ca3 +; CHECK-NEXT: call -> test3_ca1 +; CHECK-NOT: -> + +entry: + call void @test3_ca1() + ret void +} + ; Verify the SCCs formed. ; -; CHECK-LABEL: SCC with 1 functions: -; CHECK-NEXT: f7 +; CHECK-LABEL: RefSCC with 1 call SCCs: +; CHECK-NEXT: SCC with 3 functions: +; CHECK-NEXT: test3_ca3 +; CHECK-NEXT: test3_ca1 +; CHECK-NEXT: test3_ca2 +; +; CHECK-LABEL: RefSCC with 2 call SCCs: +; CHECK-NEXT: SCC with 1 functions: +; CHECK-NEXT: test3_bb1 +; CHECK-NEXT: SCC with 1 functions: +; CHECK-NEXT: test3_ba1 +; +; CHECK-LABEL: RefSCC with 3 call SCCs: +; CHECK-NEXT: SCC with 2 functions: +; CHECK-NEXT: test3_ac2 +; CHECK-NEXT: test3_ac1 +; CHECK-NEXT: SCC with 2 functions: +; CHECK-NEXT: test3_ab2 +; CHECK-NEXT: test3_ab1 +; CHECK-NEXT: SCC with 2 functions: +; CHECK-NEXT: test3_aa2 +; CHECK-NEXT: test3_aa1 +; +; CHECK-LABEL: RefSCC with 1 call SCCs: +; CHECK-NEXT: SCC with 1 functions: +; CHECK-NEXT: f7 ; -; CHECK-LABEL: SCC with 1 functions: -; CHECK-NEXT: f6 +; CHECK-LABEL: RefSCC with 1 call SCCs: +; CHECK-NEXT: SCC with 1 functions: +; CHECK-NEXT: f6 ; -; CHECK-LABEL: SCC with 1 functions: -; CHECK-NEXT: f5 +; CHECK-LABEL: RefSCC with 1 call SCCs: +; CHECK-NEXT: SCC with 1 functions: +; CHECK-NEXT: f5 ; -; CHECK-LABEL: SCC with 1 functions: -; CHECK-NEXT: f4 +; CHECK-LABEL: RefSCC with 1 call SCCs: +; CHECK-NEXT: SCC with 1 functions: +; CHECK-NEXT: f4 ; -; CHECK-LABEL: SCC with 1 functions: -; CHECK-NEXT: f3 +; CHECK-LABEL: RefSCC with 1 call SCCs: +; CHECK-NEXT: SCC with 1 functions: +; CHECK-NEXT: f3 ; -; CHECK-LABEL: SCC with 1 functions: -; CHECK-NEXT: f2 +; CHECK-LABEL: RefSCC with 1 call SCCs: +; CHECK-NEXT: SCC with 1 functions: +; CHECK-NEXT: f2 ; -; CHECK-LABEL: SCC with 1 functions: -; CHECK-NEXT: f1 +; CHECK-LABEL: RefSCC with 1 call SCCs: +; CHECK-NEXT: SCC with 1 functions: +; CHECK-NEXT: f1 ; -; CHECK-LABEL: SCC with 1 functions: -; CHECK-NEXT: test2 +; CHECK-LABEL: RefSCC with 1 call SCCs: +; CHECK-NEXT: SCC with 1 functions: +; CHECK-NEXT: test2 ; -; CHECK-LABEL: SCC with 1 functions: -; CHECK-NEXT: f10 +; CHECK-LABEL: RefSCC with 1 call SCCs: +; CHECK-NEXT: SCC with 1 functions: +; CHECK-NEXT: f10 ; -; CHECK-LABEL: SCC with 1 functions: -; CHECK-NEXT: f12 +; CHECK-LABEL: RefSCC with 1 call SCCs: +; CHECK-NEXT: SCC with 1 functions: +; CHECK-NEXT: f12 ; -; CHECK-LABEL: SCC with 1 functions: -; CHECK-NEXT: f11 +; CHECK-LABEL: RefSCC with 1 call SCCs: +; CHECK-NEXT: SCC with 1 functions: +; CHECK-NEXT: f11 ; -; CHECK-LABEL: SCC with 1 functions: -; CHECK-NEXT: f9 +; CHECK-LABEL: RefSCC with 1 call SCCs: +; CHECK-NEXT: SCC with 1 functions: +; CHECK-NEXT: f9 ; -; CHECK-LABEL: SCC with 1 functions: -; CHECK-NEXT: f8 +; CHECK-LABEL: RefSCC with 1 call SCCs: +; CHECK-NEXT: SCC with 1 functions: +; CHECK-NEXT: f8 ; -; CHECK-LABEL: SCC with 1 functions: -; CHECK-NEXT: test1 +; CHECK-LABEL: RefSCC with 1 call SCCs: +; CHECK-NEXT: SCC with 1 functions: +; CHECK-NEXT: test1 ; -; CHECK-LABEL: SCC with 1 functions: -; CHECK-NEXT: f +; CHECK-LABEL: RefSCC with 1 call SCCs: +; CHECK-NEXT: SCC with 1 functions: +; CHECK-NEXT: f ; -; CHECK-LABEL: SCC with 1 functions: -; CHECK-NEXT: test0 +; CHECK-LABEL: RefSCC with 1 call SCCs: +; CHECK-NEXT: SCC with 1 functions: +; CHECK-NEXT: test0 diff --git a/llvm/unittests/Analysis/LazyCallGraphTest.cpp b/llvm/unittests/Analysis/LazyCallGraphTest.cpp index fb3eeb7d234..457c07dc308 100644 --- a/llvm/unittests/Analysis/LazyCallGraphTest.cpp +++ b/llvm/unittests/Analysis/LazyCallGraphTest.cpp @@ -202,12 +202,13 @@ TEST(LazyCallGraphTest, BasicGraphFormation) { EXPECT_EQ(D3.end(), std::next(D3.begin())); EXPECT_EQ("d1", D3.begin()->getFunction().getName()); - // Now lets look at the SCCs. - auto SCCI = CG.postorder_scc_begin(); + // Now lets look at the RefSCCs and SCCs. + auto J = CG.postorder_ref_scc_begin(); - LazyCallGraph::SCC &D = *SCCI++; - for (LazyCallGraph::Node *N : D) - Nodes.push_back(N->getFunction().getName()); + LazyCallGraph::RefSCC &D = *J++; + ASSERT_EQ(1, D.size()); + for (LazyCallGraph::Node &N : *D.begin()) + Nodes.push_back(N.getFunction().getName()); std::sort(Nodes.begin(), Nodes.end()); EXPECT_EQ(3u, Nodes.size()); EXPECT_EQ("d1", Nodes[0]); @@ -219,9 +220,10 @@ TEST(LazyCallGraphTest, BasicGraphFormation) { EXPECT_FALSE(D.isAncestorOf(D)); EXPECT_FALSE(D.isDescendantOf(D)); - LazyCallGraph::SCC &C = *SCCI++; - for (LazyCallGraph::Node *N : C) - Nodes.push_back(N->getFunction().getName()); + LazyCallGraph::RefSCC &C = *J++; + ASSERT_EQ(1, C.size()); + for (LazyCallGraph::Node &N : *C.begin()) + Nodes.push_back(N.getFunction().getName()); std::sort(Nodes.begin(), Nodes.end()); EXPECT_EQ(3u, Nodes.size()); EXPECT_EQ("c1", Nodes[0]); @@ -233,9 +235,10 @@ TEST(LazyCallGraphTest, BasicGraphFormation) { EXPECT_TRUE(C.isAncestorOf(D)); EXPECT_FALSE(C.isDescendantOf(D)); - LazyCallGraph::SCC &B = *SCCI++; - for (LazyCallGraph::Node *N : B) - Nodes.push_back(N->getFunction().getName()); + LazyCallGraph::RefSCC &B = *J++; + ASSERT_EQ(1, B.size()); + for (LazyCallGraph::Node &N : *B.begin()) + Nodes.push_back(N.getFunction().getName()); std::sort(Nodes.begin(), Nodes.end()); EXPECT_EQ(3u, Nodes.size()); EXPECT_EQ("b1", Nodes[0]); @@ -249,9 +252,10 @@ TEST(LazyCallGraphTest, BasicGraphFormation) { EXPECT_FALSE(B.isAncestorOf(C)); EXPECT_FALSE(C.isAncestorOf(B)); - LazyCallGraph::SCC &A = *SCCI++; - for (LazyCallGraph::Node *N : A) - Nodes.push_back(N->getFunction().getName()); + LazyCallGraph::RefSCC &A = *J++; + ASSERT_EQ(1, A.size()); + for (LazyCallGraph::Node &N : *A.begin()) + Nodes.push_back(N.getFunction().getName()); std::sort(Nodes.begin(), Nodes.end()); EXPECT_EQ(3u, Nodes.size()); EXPECT_EQ("a1", Nodes[0]); @@ -265,7 +269,7 @@ TEST(LazyCallGraphTest, BasicGraphFormation) { EXPECT_TRUE(A.isAncestorOf(C)); EXPECT_TRUE(A.isAncestorOf(D)); - EXPECT_EQ(CG.postorder_scc_end(), SCCI); + EXPECT_EQ(CG.postorder_ref_scc_end(), J); } static Function &lookupFunction(Module &M, StringRef Name) { @@ -323,57 +327,130 @@ TEST(LazyCallGraphTest, BasicGraphMutation) { EXPECT_EQ(0, std::distance(B.begin(), B.end())); } +TEST(LazyCallGraphTest, InnerSCCFormation) { + std::unique_ptr<Module> M = parseAssembly(DiamondOfTriangles); + LazyCallGraph CG(*M); + + // Now mutate the graph to connect every node into a single RefSCC to ensure + // that our inner SCC formation handles the rest. + CG.insertEdge(lookupFunction(*M, "d1"), lookupFunction(*M, "a1"), + LazyCallGraph::Edge::Ref); + + // Build vectors and sort them for the rest of the assertions to make them + // independent of order. + std::vector<std::string> Nodes; + + // We should build a single RefSCC for the entire graph. + auto I = CG.postorder_ref_scc_begin(); + LazyCallGraph::RefSCC &RC = *I++; + EXPECT_EQ(CG.postorder_ref_scc_end(), I); + + // Now walk the four SCCs which should be in post-order. + auto J = RC.begin(); + LazyCallGraph::SCC &D = *J++; + for (LazyCallGraph::Node &N : D) + Nodes.push_back(N.getFunction().getName()); + std::sort(Nodes.begin(), Nodes.end()); + EXPECT_EQ(3u, Nodes.size()); + EXPECT_EQ("d1", Nodes[0]); + EXPECT_EQ("d2", Nodes[1]); + EXPECT_EQ("d3", Nodes[2]); + Nodes.clear(); + + LazyCallGraph::SCC &B = *J++; + for (LazyCallGraph::Node &N : B) + Nodes.push_back(N.getFunction().getName()); + std::sort(Nodes.begin(), Nodes.end()); + EXPECT_EQ(3u, Nodes.size()); + EXPECT_EQ("b1", Nodes[0]); + EXPECT_EQ("b2", Nodes[1]); + EXPECT_EQ("b3", Nodes[2]); + Nodes.clear(); + + LazyCallGraph::SCC &C = *J++; + for (LazyCallGraph::Node &N : C) + Nodes.push_back(N.getFunction().getName()); + std::sort(Nodes.begin(), Nodes.end()); + EXPECT_EQ(3u, Nodes.size()); + EXPECT_EQ("c1", Nodes[0]); + EXPECT_EQ("c2", Nodes[1]); + EXPECT_EQ("c3", Nodes[2]); + Nodes.clear(); + + LazyCallGraph::SCC &A = *J++; + for (LazyCallGraph::Node &N : A) + Nodes.push_back(N.getFunction().getName()); + std::sort(Nodes.begin(), Nodes.end()); + EXPECT_EQ(3u, Nodes.size()); + EXPECT_EQ("a1", Nodes[0]); + EXPECT_EQ("a2", Nodes[1]); + EXPECT_EQ("a3", Nodes[2]); + Nodes.clear(); + + EXPECT_EQ(RC.end(), J); +} + TEST(LazyCallGraphTest, MultiArmSCC) { // Two interlocking cycles. The really useful thing about this SCC is that it // will require Tarjan's DFS to backtrack and finish processing all of the - // children of each node in the SCC. + // children of each node in the SCC. Since this involves call edges, both + // Tarjan implementations will have to successfully navigate the structure. std::unique_ptr<Module> M = parseAssembly( - "define void @a() {\n" + "define void @f1() {\n" "entry:\n" - " call void @b()\n" - " call void @d()\n" + " call void @f2()\n" + " call void @f4()\n" " ret void\n" "}\n" - "define void @b() {\n" + "define void @f2() {\n" "entry:\n" - " call void @c()\n" + " call void @f3()\n" " ret void\n" "}\n" - "define void @c() {\n" + "define void @f3() {\n" "entry:\n" - " call void @a()\n" + " call void @f1()\n" " ret void\n" "}\n" - "define void @d() {\n" + "define void @f4() {\n" "entry:\n" - " call void @e()\n" + " call void @f5()\n" " ret void\n" "}\n" - "define void @e() {\n" + "define void @f5() {\n" "entry:\n" - " call void @a()\n" + " call void @f1()\n" " ret void\n" "}\n"); LazyCallGraph CG(*M); // Force the graph to be fully expanded. - auto SCCI = CG.postorder_scc_begin(); - LazyCallGraph::SCC &SCC = *SCCI++; - EXPECT_EQ(CG.postorder_scc_end(), SCCI); - - LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); - LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); - LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); - LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); - LazyCallGraph::Node &E = *CG.lookup(lookupFunction(*M, "e")); - EXPECT_EQ(&SCC, CG.lookupSCC(A)); - EXPECT_EQ(&SCC, CG.lookupSCC(B)); - EXPECT_EQ(&SCC, CG.lookupSCC(C)); - EXPECT_EQ(&SCC, CG.lookupSCC(D)); - EXPECT_EQ(&SCC, CG.lookupSCC(E)); + auto I = CG.postorder_ref_scc_begin(); + LazyCallGraph::RefSCC &RC = *I++; + EXPECT_EQ(CG.postorder_ref_scc_end(), I); + + LazyCallGraph::Node &N1 = *CG.lookup(lookupFunction(*M, "f1")); + LazyCallGraph::Node &N2 = *CG.lookup(lookupFunction(*M, "f2")); + LazyCallGraph::Node &N3 = *CG.lookup(lookupFunction(*M, "f3")); + LazyCallGraph::Node &N4 = *CG.lookup(lookupFunction(*M, "f4")); + LazyCallGraph::Node &N5 = *CG.lookup(lookupFunction(*M, "f4")); + EXPECT_EQ(&RC, CG.lookupRefSCC(N1)); + EXPECT_EQ(&RC, CG.lookupRefSCC(N2)); + EXPECT_EQ(&RC, CG.lookupRefSCC(N3)); + EXPECT_EQ(&RC, CG.lookupRefSCC(N4)); + EXPECT_EQ(&RC, CG.lookupRefSCC(N5)); + + ASSERT_EQ(1, RC.size()); + + LazyCallGraph::SCC &C = *RC.begin(); + EXPECT_EQ(&C, CG.lookupSCC(N1)); + EXPECT_EQ(&C, CG.lookupSCC(N2)); + EXPECT_EQ(&C, CG.lookupSCC(N3)); + EXPECT_EQ(&C, CG.lookupSCC(N4)); + EXPECT_EQ(&C, CG.lookupSCC(N5)); } -TEST(LazyCallGraphTest, OutgoingSCCEdgeInsertion) { +TEST(LazyCallGraphTest, OutgoingEdgeMutation) { std::unique_ptr<Module> M = parseAssembly( "define void @a() {\n" "entry:\n" @@ -398,8 +475,8 @@ TEST(LazyCallGraphTest, OutgoingSCCEdgeInsertion) { LazyCallGraph CG(*M); // Force the graph to be fully expanded. - for (LazyCallGraph::SCC &C : CG.postorder_sccs()) - (void)C; + for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) + (void)RC; LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); @@ -409,24 +486,95 @@ TEST(LazyCallGraphTest, OutgoingSCCEdgeInsertion) { LazyCallGraph::SCC &BC = *CG.lookupSCC(B); LazyCallGraph::SCC &CC = *CG.lookupSCC(C); LazyCallGraph::SCC &DC = *CG.lookupSCC(D); - EXPECT_TRUE(AC.isAncestorOf(BC)); - EXPECT_TRUE(AC.isAncestorOf(CC)); - EXPECT_TRUE(AC.isAncestorOf(DC)); - EXPECT_TRUE(DC.isDescendantOf(AC)); - EXPECT_TRUE(DC.isDescendantOf(BC)); - EXPECT_TRUE(DC.isDescendantOf(CC)); + LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A); + LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B); + LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C); + LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D); + EXPECT_TRUE(ARC.isParentOf(BRC)); + EXPECT_TRUE(ARC.isParentOf(CRC)); + EXPECT_FALSE(ARC.isParentOf(DRC)); + EXPECT_TRUE(ARC.isAncestorOf(DRC)); + EXPECT_FALSE(DRC.isChildOf(ARC)); + EXPECT_TRUE(DRC.isDescendantOf(ARC)); + EXPECT_TRUE(DRC.isChildOf(BRC)); + EXPECT_TRUE(DRC.isChildOf(CRC)); EXPECT_EQ(2, std::distance(A.begin(), A.end())); - AC.insertOutgoingEdge(A, D, LazyCallGraph::Edge::Call); + ARC.insertOutgoingEdge(A, D, LazyCallGraph::Edge::Call); EXPECT_EQ(3, std::distance(A.begin(), A.end())); - EXPECT_TRUE(AC.isParentOf(DC)); + const LazyCallGraph::Edge &NewE = A[D]; + EXPECT_TRUE(NewE); + EXPECT_TRUE(NewE.isCall()); + EXPECT_EQ(&D, NewE.getNode()); + + // Only the parent and child tests sholud have changed. The rest of the graph + // remains the same. + EXPECT_TRUE(ARC.isParentOf(DRC)); + EXPECT_TRUE(ARC.isAncestorOf(DRC)); + EXPECT_TRUE(DRC.isChildOf(ARC)); + EXPECT_TRUE(DRC.isDescendantOf(ARC)); EXPECT_EQ(&AC, CG.lookupSCC(A)); EXPECT_EQ(&BC, CG.lookupSCC(B)); EXPECT_EQ(&CC, CG.lookupSCC(C)); EXPECT_EQ(&DC, CG.lookupSCC(D)); + EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); + EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); + EXPECT_EQ(&CRC, CG.lookupRefSCC(C)); + EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); + + ARC.switchOutgoingEdgeToRef(A, D); + EXPECT_FALSE(NewE.isCall()); + + // Verify the graph remains the same. + EXPECT_TRUE(ARC.isParentOf(DRC)); + EXPECT_TRUE(ARC.isAncestorOf(DRC)); + EXPECT_TRUE(DRC.isChildOf(ARC)); + EXPECT_TRUE(DRC.isDescendantOf(ARC)); + EXPECT_EQ(&AC, CG.lookupSCC(A)); + EXPECT_EQ(&BC, CG.lookupSCC(B)); + EXPECT_EQ(&CC, CG.lookupSCC(C)); + EXPECT_EQ(&DC, CG.lookupSCC(D)); + EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); + EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); + EXPECT_EQ(&CRC, CG.lookupRefSCC(C)); + EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); + + ARC.switchOutgoingEdgeToCall(A, D); + EXPECT_TRUE(NewE.isCall()); + + // Verify the graph remains the same. + EXPECT_TRUE(ARC.isParentOf(DRC)); + EXPECT_TRUE(ARC.isAncestorOf(DRC)); + EXPECT_TRUE(DRC.isChildOf(ARC)); + EXPECT_TRUE(DRC.isDescendantOf(ARC)); + EXPECT_EQ(&AC, CG.lookupSCC(A)); + EXPECT_EQ(&BC, CG.lookupSCC(B)); + EXPECT_EQ(&CC, CG.lookupSCC(C)); + EXPECT_EQ(&DC, CG.lookupSCC(D)); + EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); + EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); + EXPECT_EQ(&CRC, CG.lookupRefSCC(C)); + EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); + + ARC.removeOutgoingEdge(A, D); + EXPECT_EQ(2, std::distance(A.begin(), A.end())); + + // Now the parent and child tests fail again but the rest remains the same. + EXPECT_FALSE(ARC.isParentOf(DRC)); + EXPECT_TRUE(ARC.isAncestorOf(DRC)); + EXPECT_FALSE(DRC.isChildOf(ARC)); + EXPECT_TRUE(DRC.isDescendantOf(ARC)); + EXPECT_EQ(&AC, CG.lookupSCC(A)); + EXPECT_EQ(&BC, CG.lookupSCC(B)); + EXPECT_EQ(&CC, CG.lookupSCC(C)); + EXPECT_EQ(&DC, CG.lookupSCC(D)); + EXPECT_EQ(&ARC, CG.lookupRefSCC(A)); + EXPECT_EQ(&BRC, CG.lookupRefSCC(B)); + EXPECT_EQ(&CRC, CG.lookupRefSCC(C)); + EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); } -TEST(LazyCallGraphTest, IncomingSCCEdgeInsertion) { +TEST(LazyCallGraphTest, IncomingEdgeInsertion) { // We want to ensure we can add edges even across complex diamond graphs, so // we use the diamond of triangles graph defined above. The ascii diagram is // repeated here for easy reference. @@ -447,8 +595,8 @@ TEST(LazyCallGraphTest, IncomingSCCEdgeInsertion) { LazyCallGraph CG(*M); // Force the graph to be fully expanded. - for (LazyCallGraph::SCC &C : CG.postorder_sccs()) - (void)C; + for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs()) + (void)RC; LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1")); LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2")); @@ -462,18 +610,18 @@ TEST(LazyCallGraphTest, IncomingSCCEdgeInsertion) { LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1")); LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2")); LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3")); - LazyCallGraph::SCC &AC = *CG.lookupSCC(A1); - LazyCallGraph::SCC &BC = *CG.lookupSCC(B1); - LazyCallGraph::SCC &CC = *CG.lookupSCC(C1); - LazyCallGraph::SCC &DC = *CG.lookupSCC(D1); - ASSERT_EQ(&AC, CG.lookupSCC(A2)); - ASSERT_EQ(&AC, CG.lookupSCC(A3)); - ASSERT_EQ(&BC, CG.lookupSCC(B2)); - ASSERT_EQ(&BC, CG.lookupSCC(B3)); - ASSERT_EQ(&CC, CG.lookupSCC(C2)); - ASSERT_EQ(&CC, CG.lookupSCC(C3)); - ASSERT_EQ(&DC, CG.lookupSCC(D2)); - ASSERT_EQ(&DC, CG.lookupSCC(D3)); + LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A1); + LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B1); + LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C1); + LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D1); + ASSERT_EQ(&ARC, CG.lookupRefSCC(A2)); + ASSERT_EQ(&ARC, CG.lookupRefSCC(A3)); + ASSERT_EQ(&BRC, CG.lookupRefSCC(B2)); + ASSERT_EQ(&BRC, CG.lookupRefSCC(B3)); + ASSERT_EQ(&CRC, CG.lookupRefSCC(C2)); + ASSERT_EQ(&CRC, CG.lookupRefSCC(C3)); + ASSERT_EQ(&DRC, CG.lookupRefSCC(D2)); + ASSERT_EQ(&DRC, CG.lookupRefSCC(D3)); ASSERT_EQ(1, std::distance(D2.begin(), D2.end())); // Add an edge to make the graph: @@ -489,47 +637,51 @@ TEST(LazyCallGraphTest, IncomingSCCEdgeInsertion) { // a1 | // / \ | // a3--a2 | - CC.insertIncomingEdge(D2, C2, LazyCallGraph::Edge::Call); + auto MergedRCs = CRC.insertIncomingRefEdge(D2, C2); // Make sure we connected the nodes. - EXPECT_EQ(2, std::distance(D2.begin(), D2.end())); + for (LazyCallGraph::Edge E : D2) { + if (E.getNode() == &D3) + continue; + EXPECT_EQ(&C2, E.getNode()); + } + // And marked the D ref-SCC as no longer valid. + EXPECT_EQ(1u, MergedRCs.size()); + EXPECT_EQ(&DRC, MergedRCs[0]); // Make sure we have the correct nodes in the SCC sets. - EXPECT_EQ(&AC, CG.lookupSCC(A1)); - EXPECT_EQ(&AC, CG.lookupSCC(A2)); - EXPECT_EQ(&AC, CG.lookupSCC(A3)); - EXPECT_EQ(&BC, CG.lookupSCC(B1)); - EXPECT_EQ(&BC, CG.lookupSCC(B2)); - EXPECT_EQ(&BC, CG.lookupSCC(B3)); - EXPECT_EQ(&CC, CG.lookupSCC(C1)); - EXPECT_EQ(&CC, CG.lookupSCC(C2)); - EXPECT_EQ(&CC, CG.lookupSCC(C3)); - EXPECT_EQ(&CC, CG.lookupSCC(D1)); - EXPECT_EQ(&CC, CG.lookupSCC(D2)); - EXPECT_EQ(&CC, CG.lookupSCC(D3)); + EXPECT_EQ(&ARC, CG.lookupRefSCC(A1)); + EXPECT_EQ(&ARC, CG.lookupRefSCC(A2)); + EXPECT_EQ(&ARC, CG.lookupRefSCC(A3)); + EXPECT_EQ(&BRC, CG.lookupRefSCC(B1)); + EXPECT_EQ(&BRC, CG.lookupRefSCC(B2)); + EXPECT_EQ(&BRC, CG.lookupRefSCC(B3)); + EXPECT_EQ(&CRC, CG.lookupRefSCC(C1)); + EXPECT_EQ(&CRC, CG.lookupRefSCC(C2)); + EXPECT_EQ(&CRC, CG.lookupRefSCC(C3)); + EXPECT_EQ(&CRC, CG.lookupRefSCC(D1)); + EXPECT_EQ(&CRC, CG.lookupRefSCC(D2)); + EXPECT_EQ(&CRC, CG.lookupRefSCC(D3)); // And that ancestry tests have been updated. - EXPECT_TRUE(AC.isParentOf(BC)); - EXPECT_TRUE(AC.isParentOf(CC)); - EXPECT_FALSE(AC.isAncestorOf(DC)); - EXPECT_FALSE(BC.isAncestorOf(DC)); - EXPECT_FALSE(CC.isAncestorOf(DC)); + EXPECT_TRUE(ARC.isParentOf(CRC)); + EXPECT_TRUE(BRC.isParentOf(CRC)); } -TEST(LazyCallGraphTest, IncomingSCCEdgeInsertionMidTraversal) { +TEST(LazyCallGraphTest, IncomingEdgeInsertionMidTraversal) { // This is the same fundamental test as the previous, but we perform it - // having only partially walked the SCCs of the graph. + // having only partially walked the RefSCCs of the graph. std::unique_ptr<Module> M = parseAssembly(DiamondOfTriangles); LazyCallGraph CG(*M); - // Walk the SCCs until we find the one containing 'c1'. - auto SCCI = CG.postorder_scc_begin(), SCCE = CG.postorder_scc_end(); - ASSERT_NE(SCCI, SCCE); - LazyCallGraph::SCC &DC = *SCCI; - ASSERT_NE(&DC, nullptr); - ++SCCI; - ASSERT_NE(SCCI, SCCE); - LazyCallGraph::SCC &CC = *SCCI; - ASSERT_NE(&CC, nullptr); + // Walk the RefSCCs until we find the one containing 'c1'. + auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end(); + ASSERT_NE(I, E); + LazyCallGraph::RefSCC &DRC = *I; + ASSERT_NE(&DRC, nullptr); + ++I; + ASSERT_NE(I, E); + LazyCallGraph::RefSCC &CRC = *I; + ASSERT_NE(&CRC, nullptr); ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a1"))); ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a2"))); @@ -543,45 +695,55 @@ TEST(LazyCallGraphTest, IncomingSCCEdgeInsertionMidTraversal) { LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1")); LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2")); LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3")); - ASSERT_EQ(&CC, CG.lookupSCC(C1)); - ASSERT_EQ(&CC, CG.lookupSCC(C2)); - ASSERT_EQ(&CC, CG.lookupSCC(C3)); - ASSERT_EQ(&DC, CG.lookupSCC(D1)); - ASSERT_EQ(&DC, CG.lookupSCC(D2)); - ASSERT_EQ(&DC, CG.lookupSCC(D3)); + ASSERT_EQ(&CRC, CG.lookupRefSCC(C1)); + ASSERT_EQ(&CRC, CG.lookupRefSCC(C2)); + ASSERT_EQ(&CRC, CG.lookupRefSCC(C3)); + ASSERT_EQ(&DRC, CG.lookupRefSCC(D1)); + ASSERT_EQ(&DRC, CG.lookupRefSCC(D2)); + ASSERT_EQ(&DRC, CG.lookupRefSCC(D3)); ASSERT_EQ(1, std::distance(D2.begin(), D2.end())); - CC.insertIncomingEdge(D2, C2, LazyCallGraph::Edge::Call); - EXPECT_EQ(2, std::distance(D2.begin(), D2.end())); - - // Make sure we have the correct nodes in the SCC sets. - EXPECT_EQ(&CC, CG.lookupSCC(C1)); - EXPECT_EQ(&CC, CG.lookupSCC(C2)); - EXPECT_EQ(&CC, CG.lookupSCC(C3)); - EXPECT_EQ(&CC, CG.lookupSCC(D1)); - EXPECT_EQ(&CC, CG.lookupSCC(D2)); - EXPECT_EQ(&CC, CG.lookupSCC(D3)); - - // Check that we can form the last two SCCs now in a coherent way. - ++SCCI; - EXPECT_NE(SCCI, SCCE); - LazyCallGraph::SCC &BC = *SCCI; - EXPECT_NE(&BC, nullptr); - EXPECT_EQ(&BC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "b1")))); - EXPECT_EQ(&BC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "b2")))); - EXPECT_EQ(&BC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "b3")))); - ++SCCI; - EXPECT_NE(SCCI, SCCE); - LazyCallGraph::SCC &AC = *SCCI; - EXPECT_NE(&AC, nullptr); - EXPECT_EQ(&AC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "a1")))); - EXPECT_EQ(&AC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "a2")))); - EXPECT_EQ(&AC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "a3")))); - ++SCCI; - EXPECT_EQ(SCCI, SCCE); + auto MergedRCs = CRC.insertIncomingRefEdge(D2, C2); + // Make sure we connected the nodes. + for (LazyCallGraph::Edge E : D2) { + if (E.getNode() == &D3) + continue; + EXPECT_EQ(&C2, E.getNode()); + } + // And marked the D ref-SCC as no longer valid. + EXPECT_EQ(1u, MergedRCs.size()); + EXPECT_EQ(&DRC, MergedRCs[0]); + + // Make sure we have the correct nodes in the RefSCCs. + EXPECT_EQ(&CRC, CG.lookupRefSCC(C1)); + EXPECT_EQ(&CRC, CG.lookupRefSCC(C2)); + EXPECT_EQ(&CRC, CG.lookupRefSCC(C3)); + EXPECT_EQ(&CRC, CG.lookupRefSCC(D1)); + EXPECT_EQ(&CRC, CG.lookupRefSCC(D2)); + EXPECT_EQ(&CRC, CG.lookupRefSCC(D3)); + + // Check that we can form the last two RefSCCs now in a coherent way. + ++I; + EXPECT_NE(I, E); + LazyCallGraph::RefSCC &BRC = *I; + EXPECT_NE(&BRC, nullptr); + EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b1")))); + EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b2")))); + EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b3")))); + EXPECT_TRUE(BRC.isParentOf(CRC)); + ++I; + EXPECT_NE(I, E); + LazyCallGraph::RefSCC &ARC = *I; + EXPECT_NE(&ARC, nullptr); + EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a1")))); + EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a2")))); + EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a3")))); + EXPECT_TRUE(ARC.isParentOf(CRC)); + ++I; + EXPECT_EQ(E, I); } -TEST(LazyCallGraphTest, InterSCCEdgeRemoval) { +TEST(LazyCallGraphTest, InternalEdgeMutation) { std::unique_ptr<Module> M = parseAssembly( "define void @a() {\n" "entry:\n" @@ -590,79 +752,138 @@ TEST(LazyCallGraphTest, InterSCCEdgeRemoval) { "}\n" "define void @b() {\n" "entry:\n" + " call void @c()\n" + " ret void\n" + "}\n" + "define void @c() {\n" + "entry:\n" + " call void @a()\n" " ret void\n" "}\n"); LazyCallGraph CG(*M); // Force the graph to be fully expanded. - for (LazyCallGraph::SCC &C : CG.postorder_sccs()) - (void)C; + auto I = CG.postorder_ref_scc_begin(); + LazyCallGraph::RefSCC &RC = *I++; + EXPECT_EQ(CG.postorder_ref_scc_end(), I); LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); + LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); + EXPECT_EQ(&RC, CG.lookupRefSCC(A)); + EXPECT_EQ(&RC, CG.lookupRefSCC(B)); + EXPECT_EQ(&RC, CG.lookupRefSCC(C)); + EXPECT_EQ(1, RC.size()); + EXPECT_EQ(&*RC.begin(), CG.lookupSCC(A)); + EXPECT_EQ(&*RC.begin(), CG.lookupSCC(B)); + EXPECT_EQ(&*RC.begin(), CG.lookupSCC(C)); + + // Insert an edge from 'a' to 'c'. Nothing changes about the graph. + RC.insertInternalRefEdge(A, C); + EXPECT_EQ(2, std::distance(A.begin(), A.end())); + EXPECT_EQ(&RC, CG.lookupRefSCC(A)); + EXPECT_EQ(&RC, CG.lookupRefSCC(B)); + EXPECT_EQ(&RC, CG.lookupRefSCC(C)); + EXPECT_EQ(1, RC.size()); + EXPECT_EQ(&*RC.begin(), CG.lookupSCC(A)); + EXPECT_EQ(&*RC.begin(), CG.lookupSCC(B)); + EXPECT_EQ(&*RC.begin(), CG.lookupSCC(C)); + + // Switch the call edge from 'b' to 'c' to a ref edge. This will break the + // call cycle and cause us to form more SCCs. The RefSCC will remain the same + // though. + RC.switchInternalEdgeToRef(B, C); + EXPECT_EQ(&RC, CG.lookupRefSCC(A)); + EXPECT_EQ(&RC, CG.lookupRefSCC(B)); + EXPECT_EQ(&RC, CG.lookupRefSCC(C)); + auto J = RC.begin(); + // The SCCs must be in *post-order* which means successors before + // predecessors. At this point we have call edges from C to A and from A to + // B. The only valid postorder is B, A, C. + EXPECT_EQ(&*J++, CG.lookupSCC(B)); + EXPECT_EQ(&*J++, CG.lookupSCC(A)); + EXPECT_EQ(&*J++, CG.lookupSCC(C)); + EXPECT_EQ(RC.end(), J); + + // Test turning the ref edge from A to C into a call edge. This will form an + // SCC out of A and C. Since we previously had a call edge from C to A, the + // C SCC should be preserved and have A merged into it while the A SCC should + // be invalidated. LazyCallGraph::SCC &AC = *CG.lookupSCC(A); - LazyCallGraph::SCC &BC = *CG.lookupSCC(B); - - EXPECT_EQ("b", A.begin()->getFunction().getName()); - EXPECT_EQ(B.end(), B.begin()); - EXPECT_EQ(&AC, &*BC.parent_begin()); - - AC.removeInterSCCEdge(A, B); - - EXPECT_EQ(A.end(), A.begin()); - EXPECT_EQ(B.end(), B.begin()); - EXPECT_EQ(BC.parent_end(), BC.parent_begin()); + LazyCallGraph::SCC &CC = *CG.lookupSCC(C); + auto InvalidatedSCCs = RC.switchInternalEdgeToCall(A, C); + ASSERT_EQ(1u, InvalidatedSCCs.size()); + EXPECT_EQ(&AC, InvalidatedSCCs[0]); + EXPECT_EQ(2, CC.size()); + EXPECT_EQ(&CC, CG.lookupSCC(A)); + EXPECT_EQ(&CC, CG.lookupSCC(C)); + J = RC.begin(); + EXPECT_EQ(&*J++, CG.lookupSCC(B)); + EXPECT_EQ(&*J++, CG.lookupSCC(C)); + EXPECT_EQ(RC.end(), J); } -TEST(LazyCallGraphTest, IntraSCCEdgeInsertion) { - std::unique_ptr<Module> M1 = parseAssembly( - "define void @a() {\n" +TEST(LazyCallGraphTest, InternalEdgeRemoval) { + // A nice fully connected (including self-edges) RefSCC. + std::unique_ptr<Module> M = parseAssembly( + "define void @a(i8** %ptr) {\n" "entry:\n" - " call void @b()\n" + " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" + " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" + " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" " ret void\n" "}\n" - "define void @b() {\n" + "define void @b(i8** %ptr) {\n" "entry:\n" - " call void @c()\n" + " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" + " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" + " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" " ret void\n" "}\n" - "define void @c() {\n" + "define void @c(i8** %ptr) {\n" "entry:\n" - " call void @a()\n" + " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n" + " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" + " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n" " ret void\n" "}\n"); - LazyCallGraph CG1(*M1); + LazyCallGraph CG(*M); // Force the graph to be fully expanded. - auto SCCI = CG1.postorder_scc_begin(); - LazyCallGraph::SCC &SCC = *SCCI++; - EXPECT_EQ(CG1.postorder_scc_end(), SCCI); - - LazyCallGraph::Node &A = *CG1.lookup(lookupFunction(*M1, "a")); - LazyCallGraph::Node &B = *CG1.lookup(lookupFunction(*M1, "b")); - LazyCallGraph::Node &C = *CG1.lookup(lookupFunction(*M1, "c")); - EXPECT_EQ(&SCC, CG1.lookupSCC(A)); - EXPECT_EQ(&SCC, CG1.lookupSCC(B)); - EXPECT_EQ(&SCC, CG1.lookupSCC(C)); - - // Insert an edge from 'a' to 'c'. Nothing changes about the SCCs. - SCC.insertIntraSCCEdge(A, C, LazyCallGraph::Edge::Call); - EXPECT_EQ(2, std::distance(A.begin(), A.end())); - EXPECT_EQ(&SCC, CG1.lookupSCC(A)); - EXPECT_EQ(&SCC, CG1.lookupSCC(B)); - EXPECT_EQ(&SCC, CG1.lookupSCC(C)); + auto I = CG.postorder_ref_scc_begin(); + LazyCallGraph::RefSCC &RC = *I++; + EXPECT_EQ(CG.postorder_ref_scc_end(), I); - // Insert a self edge from 'a' back to 'a'. - SCC.insertIntraSCCEdge(A, A, LazyCallGraph::Edge::Call); - EXPECT_EQ(3, std::distance(A.begin(), A.end())); - EXPECT_EQ(&SCC, CG1.lookupSCC(A)); - EXPECT_EQ(&SCC, CG1.lookupSCC(B)); - EXPECT_EQ(&SCC, CG1.lookupSCC(C)); + LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); + LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); + LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); + EXPECT_EQ(&RC, CG.lookupRefSCC(A)); + EXPECT_EQ(&RC, CG.lookupRefSCC(B)); + EXPECT_EQ(&RC, CG.lookupRefSCC(C)); + + // Remove the edge from b -> a, which should leave the 3 functions still in + // a single connected component because of a -> b -> c -> a. + SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs = + RC.removeInternalRefEdge(B, A); + EXPECT_EQ(0u, NewRCs.size()); + EXPECT_EQ(&RC, CG.lookupRefSCC(A)); + EXPECT_EQ(&RC, CG.lookupRefSCC(B)); + EXPECT_EQ(&RC, CG.lookupRefSCC(C)); + + // Remove the edge from c -> a, which should leave 'a' in the original RefSCC + // and form a new RefSCC for 'b' and 'c'. + NewRCs = RC.removeInternalRefEdge(C, A); + EXPECT_EQ(1u, NewRCs.size()); + EXPECT_EQ(&RC, CG.lookupRefSCC(A)); + EXPECT_EQ(1, std::distance(RC.begin(), RC.end())); + LazyCallGraph::RefSCC *RC2 = CG.lookupRefSCC(B); + EXPECT_EQ(RC2, CG.lookupRefSCC(C)); + EXPECT_EQ(RC2, NewRCs[0]); } -TEST(LazyCallGraphTest, IntraSCCEdgeRemoval) { - // A nice fully connected (including self-edges) SCC. - std::unique_ptr<Module> M1 = parseAssembly( +TEST(LazyCallGraphTest, InternalCallEdgeToRef) { + // A nice fully connected (including self-edges) SCC (and RefSCC) + std::unique_ptr<Module> M = parseAssembly( "define void @a() {\n" "entry:\n" " call void @a()\n" @@ -684,37 +905,393 @@ TEST(LazyCallGraphTest, IntraSCCEdgeRemoval) { " call void @c()\n" " ret void\n" "}\n"); - LazyCallGraph CG1(*M1); + LazyCallGraph CG(*M); // Force the graph to be fully expanded. - auto SCCI = CG1.postorder_scc_begin(); - LazyCallGraph::SCC &SCC = *SCCI++; - EXPECT_EQ(CG1.postorder_scc_end(), SCCI); + auto I = CG.postorder_ref_scc_begin(); + LazyCallGraph::RefSCC &RC = *I++; + EXPECT_EQ(CG.postorder_ref_scc_end(), I); - LazyCallGraph::Node &A = *CG1.lookup(lookupFunction(*M1, "a")); - LazyCallGraph::Node &B = *CG1.lookup(lookupFunction(*M1, "b")); - LazyCallGraph::Node &C = *CG1.lookup(lookupFunction(*M1, "c")); - EXPECT_EQ(&SCC, CG1.lookupSCC(A)); - EXPECT_EQ(&SCC, CG1.lookupSCC(B)); - EXPECT_EQ(&SCC, CG1.lookupSCC(C)); + EXPECT_EQ(1, RC.size()); + LazyCallGraph::SCC &CallC = *RC.begin(); - // Remove the edge from b -> a, which should leave the 3 functions still in - // a single connected component because of a -> b -> c -> a. - SmallVector<LazyCallGraph::SCC *, 1> NewSCCs = SCC.removeIntraSCCEdge(B, A); - EXPECT_EQ(0u, NewSCCs.size()); - EXPECT_EQ(&SCC, CG1.lookupSCC(A)); - EXPECT_EQ(&SCC, CG1.lookupSCC(B)); - EXPECT_EQ(&SCC, CG1.lookupSCC(C)); + LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); + LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); + LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); + EXPECT_EQ(&CallC, CG.lookupSCC(A)); + EXPECT_EQ(&CallC, CG.lookupSCC(B)); + EXPECT_EQ(&CallC, CG.lookupSCC(C)); + + // Remove the call edge from b -> a to a ref edge, which should leave the + // 3 functions still in a single connected component because of a -> b -> + // c -> a. + RC.switchInternalEdgeToRef(B, A); + EXPECT_EQ(1, RC.size()); + EXPECT_EQ(&CallC, CG.lookupSCC(A)); + EXPECT_EQ(&CallC, CG.lookupSCC(B)); + EXPECT_EQ(&CallC, CG.lookupSCC(C)); // Remove the edge from c -> a, which should leave 'a' in the original SCC // and form a new SCC for 'b' and 'c'. - NewSCCs = SCC.removeIntraSCCEdge(C, A); - EXPECT_EQ(1u, NewSCCs.size()); - EXPECT_EQ(&SCC, CG1.lookupSCC(A)); - EXPECT_EQ(1, std::distance(SCC.begin(), SCC.end())); - LazyCallGraph::SCC *SCC2 = CG1.lookupSCC(B); - EXPECT_EQ(SCC2, CG1.lookupSCC(C)); - EXPECT_EQ(SCC2, NewSCCs[0]); + RC.switchInternalEdgeToRef(C, A); + EXPECT_EQ(2, RC.size()); + EXPECT_EQ(&CallC, CG.lookupSCC(A)); + LazyCallGraph::SCC &BCallC = *CG.lookupSCC(B); + EXPECT_NE(&BCallC, &CallC); + EXPECT_EQ(&BCallC, CG.lookupSCC(C)); + auto J = RC.find(CallC); + EXPECT_EQ(&CallC, &*J); + --J; + EXPECT_EQ(&BCallC, &*J); + EXPECT_EQ(RC.begin(), J); + + // Remove the edge from c -> b, which should leave 'b' in the original SCC + // and form a new SCC for 'c'. It shouldn't change 'a's SCC. + RC.switchInternalEdgeToRef(C, B); + EXPECT_EQ(3, RC.size()); + EXPECT_EQ(&CallC, CG.lookupSCC(A)); + EXPECT_EQ(&BCallC, CG.lookupSCC(B)); + LazyCallGraph::SCC &CCallC = *CG.lookupSCC(C); + EXPECT_NE(&CCallC, &CallC); + EXPECT_NE(&CCallC, &BCallC); + J = RC.find(CallC); + EXPECT_EQ(&CallC, &*J); + --J; + EXPECT_EQ(&BCallC, &*J); + --J; + EXPECT_EQ(&CCallC, &*J); + EXPECT_EQ(RC.begin(), J); +} + +TEST(LazyCallGraphTest, InternalRefEdgeToCall) { + // Basic tests for making a ref edge a call. This hits the basics of the + // process only. + std::unique_ptr<Module> M = parseAssembly( + "define void @a() {\n" + "entry:\n" + " call void @b()\n" + " call void @c()\n" + " store void()* @d, void()** undef\n" + " ret void\n" + "}\n" + "define void @b() {\n" + "entry:\n" + " store void()* @c, void()** undef\n" + " call void @d()\n" + " ret void\n" + "}\n" + "define void @c() {\n" + "entry:\n" + " store void()* @b, void()** undef\n" + " call void @d()\n" + " ret void\n" + "}\n" + "define void @d() {\n" + "entry:\n" + " store void()* @a, void()** undef\n" + " ret void\n" + "}\n"); + LazyCallGraph CG(*M); + + // Force the graph to be fully expanded. + auto I = CG.postorder_ref_scc_begin(); + LazyCallGraph::RefSCC &RC = *I++; + EXPECT_EQ(CG.postorder_ref_scc_end(), I); + + LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); + LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); + LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); + LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); + LazyCallGraph::SCC &AC = *CG.lookupSCC(A); + LazyCallGraph::SCC &BC = *CG.lookupSCC(B); + LazyCallGraph::SCC &CC = *CG.lookupSCC(C); + LazyCallGraph::SCC &DC = *CG.lookupSCC(D); + + // Check the initial post-order. Note that B and C could be flipped here (and + // in our mutation) without changing the nature of this test. + ASSERT_EQ(4, RC.size()); + EXPECT_EQ(&DC, &RC[0]); + EXPECT_EQ(&BC, &RC[1]); + EXPECT_EQ(&CC, &RC[2]); + EXPECT_EQ(&AC, &RC[3]); + + // Switch the ref edge from A -> D to a call edge. This should have no + // effect as it is already in postorder and no new cycles are formed. + auto MergedCs = RC.switchInternalEdgeToCall(A, D); + EXPECT_EQ(0u, MergedCs.size()); + ASSERT_EQ(4, RC.size()); + EXPECT_EQ(&DC, &RC[0]); + EXPECT_EQ(&BC, &RC[1]); + EXPECT_EQ(&CC, &RC[2]); + EXPECT_EQ(&AC, &RC[3]); + + // Switch B -> C to a call edge. This doesn't form any new cycles but does + // require reordering the SCCs. + MergedCs = RC.switchInternalEdgeToCall(B, C); + EXPECT_EQ(0u, MergedCs.size()); + ASSERT_EQ(4, RC.size()); + EXPECT_EQ(&DC, &RC[0]); + EXPECT_EQ(&CC, &RC[1]); + EXPECT_EQ(&BC, &RC[2]); + EXPECT_EQ(&AC, &RC[3]); + + // Switch C -> B to a call edge. This forms a cycle and forces merging SCCs. + MergedCs = RC.switchInternalEdgeToCall(C, B); + ASSERT_EQ(1u, MergedCs.size()); + EXPECT_EQ(&CC, MergedCs[0]); + ASSERT_EQ(3, RC.size()); + EXPECT_EQ(&DC, &RC[0]); + EXPECT_EQ(&BC, &RC[1]); + EXPECT_EQ(&AC, &RC[2]); + EXPECT_EQ(2, BC.size()); + EXPECT_EQ(&BC, CG.lookupSCC(B)); + EXPECT_EQ(&BC, CG.lookupSCC(C)); +} + +TEST(LazyCallGraphTest, InternalRefEdgeToCallNoCycleInterleaved) { + // Test for having a post-order prior to changing a ref edge to a call edge + // with SCCs connecting to the source and connecting to the target, but not + // connecting to both, interleaved between the source and target. This + // ensures we correctly partition the range rather than simply moving one or + // the other. + std::unique_ptr<Module> M = parseAssembly( + "define void @a() {\n" + "entry:\n" + " call void @b1()\n" + " call void @c1()\n" + " ret void\n" + "}\n" + "define void @b1() {\n" + "entry:\n" + " call void @c1()\n" + " call void @b2()\n" + " ret void\n" + "}\n" + "define void @c1() {\n" + "entry:\n" + " call void @b2()\n" + " call void @c2()\n" + " ret void\n" + "}\n" + "define void @b2() {\n" + "entry:\n" + " call void @c2()\n" + " call void @b3()\n" + " ret void\n" + "}\n" + "define void @c2() {\n" + "entry:\n" + " call void @b3()\n" + " call void @c3()\n" + " ret void\n" + "}\n" + "define void @b3() {\n" + "entry:\n" + " call void @c3()\n" + " call void @d()\n" + " ret void\n" + "}\n" + "define void @c3() {\n" + "entry:\n" + " store void()* @b1, void()** undef\n" + " call void @d()\n" + " ret void\n" + "}\n" + "define void @d() {\n" + "entry:\n" + " store void()* @a, void()** undef\n" + " ret void\n" + "}\n"); + LazyCallGraph CG(*M); + + // Force the graph to be fully expanded. + auto I = CG.postorder_ref_scc_begin(); + LazyCallGraph::RefSCC &RC = *I++; + EXPECT_EQ(CG.postorder_ref_scc_end(), I); + + LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); + LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1")); + LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2")); + LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3")); + LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1")); + LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2")); + LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3")); + LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); + LazyCallGraph::SCC &AC = *CG.lookupSCC(A); + LazyCallGraph::SCC &B1C = *CG.lookupSCC(B1); + LazyCallGraph::SCC &B2C = *CG.lookupSCC(B2); + LazyCallGraph::SCC &B3C = *CG.lookupSCC(B3); + LazyCallGraph::SCC &C1C = *CG.lookupSCC(C1); + LazyCallGraph::SCC &C2C = *CG.lookupSCC(C2); + LazyCallGraph::SCC &C3C = *CG.lookupSCC(C3); + LazyCallGraph::SCC &DC = *CG.lookupSCC(D); + + // Several call edges are initially present to force a particual post-order. + // Remove them now, leaving an interleaved post-order pattern. + RC.switchInternalEdgeToRef(B3, C3); + RC.switchInternalEdgeToRef(C2, B3); + RC.switchInternalEdgeToRef(B2, C2); + RC.switchInternalEdgeToRef(C1, B2); + RC.switchInternalEdgeToRef(B1, C1); + + // Check the initial post-order. We ensure this order with the extra edges + // that are nuked above. + ASSERT_EQ(8, RC.size()); + EXPECT_EQ(&DC, &RC[0]); + EXPECT_EQ(&C3C, &RC[1]); + EXPECT_EQ(&B3C, &RC[2]); + EXPECT_EQ(&C2C, &RC[3]); + EXPECT_EQ(&B2C, &RC[4]); + EXPECT_EQ(&C1C, &RC[5]); + EXPECT_EQ(&B1C, &RC[6]); + EXPECT_EQ(&AC, &RC[7]); + + // Switch C3 -> B1 to a call edge. This doesn't form any new cycles but does + // require reordering the SCCs in the face of tricky internal node + // structures. + auto MergedCs = RC.switchInternalEdgeToCall(C3, B1); + EXPECT_EQ(0u, MergedCs.size()); + ASSERT_EQ(8, RC.size()); + EXPECT_EQ(&DC, &RC[0]); + EXPECT_EQ(&B3C, &RC[1]); + EXPECT_EQ(&B2C, &RC[2]); + EXPECT_EQ(&B1C, &RC[3]); + EXPECT_EQ(&C3C, &RC[4]); + EXPECT_EQ(&C2C, &RC[5]); + EXPECT_EQ(&C1C, &RC[6]); + EXPECT_EQ(&AC, &RC[7]); +} + +TEST(LazyCallGraphTest, InternalRefEdgeToCallBothPartitionAndMerge) { + // Test for having a postorder where between the source and target are all + // three kinds of other SCCs: + // 1) One connected to the target only that have to be shifted below the + // source. + // 2) One connected to the source only that have to be shifted below the + // target. + // 3) One connected to both source and target that has to remain and get + // merged away. + // + // To achieve this we construct a heavily connected graph to force + // a particular post-order. Then we remove the forcing edges and connect + // a cycle. + // + // Diagram for the graph we want on the left and the graph we use to force + // the ordering on the right. Edges ponit down or right. + // + // A | A | + // / \ | / \ | + // B E | B \ | + // |\ | | |\ | | + // | D | | C-D-E | + // | \| | | \| | + // C F | \ F | + // \ / | \ / | + // G | G | + // + // And we form a cycle by connecting F to B. + std::unique_ptr<Module> M = parseAssembly( + "define void @a() {\n" + "entry:\n" + " call void @b()\n" + " call void @e()\n" + " ret void\n" + "}\n" + "define void @b() {\n" + "entry:\n" + " call void @c()\n" + " call void @d()\n" + " ret void\n" + "}\n" + "define void @c() {\n" + "entry:\n" + " call void @d()\n" + " call void @g()\n" + " ret void\n" + "}\n" + "define void @d() {\n" + "entry:\n" + " call void @e()\n" + " call void @f()\n" + " ret void\n" + "}\n" + "define void @e() {\n" + "entry:\n" + " call void @f()\n" + " ret void\n" + "}\n" + "define void @f() {\n" + "entry:\n" + " store void()* @b, void()** undef\n" + " call void @g()\n" + " ret void\n" + "}\n" + "define void @g() {\n" + "entry:\n" + " store void()* @a, void()** undef\n" + " ret void\n" + "}\n"); + LazyCallGraph CG(*M); + + // Force the graph to be fully expanded. + auto I = CG.postorder_ref_scc_begin(); + LazyCallGraph::RefSCC &RC = *I++; + EXPECT_EQ(CG.postorder_ref_scc_end(), I); + + LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a")); + LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b")); + LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c")); + LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d")); + LazyCallGraph::Node &E = *CG.lookup(lookupFunction(*M, "e")); + LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f")); + LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g")); + LazyCallGraph::SCC &AC = *CG.lookupSCC(A); + LazyCallGraph::SCC &BC = *CG.lookupSCC(B); + LazyCallGraph::SCC &CC = *CG.lookupSCC(C); + LazyCallGraph::SCC &DC = *CG.lookupSCC(D); + LazyCallGraph::SCC &EC = *CG.lookupSCC(E); + LazyCallGraph::SCC &FC = *CG.lookupSCC(F); + LazyCallGraph::SCC &GC = *CG.lookupSCC(G); + + // Remove the extra edges that were used to force a particular post-order. + RC.switchInternalEdgeToRef(C, D); + RC.switchInternalEdgeToRef(D, E); + + // Check the initial post-order. We ensure this order with the extra edges + // that are nuked above. + ASSERT_EQ(7, RC.size()); + EXPECT_EQ(&GC, &RC[0]); + EXPECT_EQ(&FC, &RC[1]); + EXPECT_EQ(&EC, &RC[2]); + EXPECT_EQ(&DC, &RC[3]); + EXPECT_EQ(&CC, &RC[4]); + EXPECT_EQ(&BC, &RC[5]); + EXPECT_EQ(&AC, &RC[6]); + + // Switch F -> B to a call edge. This merges B, D, and F into a single SCC, + // and has to place the C and E SCCs on either side of it: + // A A | + // / \ / \ | + // B E | E | + // |\ | \ / | + // | D | -> B | + // | \| / \ | + // C F C | | + // \ / \ / | + // G G | + auto MergedCs = RC.switchInternalEdgeToCall(F, B); + ASSERT_EQ(2u, MergedCs.size()); + EXPECT_EQ(&FC, MergedCs[0]); + EXPECT_EQ(&DC, MergedCs[1]); + EXPECT_EQ(3, BC.size()); + + // And make sure the postorder was updated. + ASSERT_EQ(5, RC.size()); + EXPECT_EQ(&GC, &RC[0]); + EXPECT_EQ(&CC, &RC[1]); + EXPECT_EQ(&BC, &RC[2]); + EXPECT_EQ(&EC, &RC[3]); + EXPECT_EQ(&AC, &RC[4]); } } |
