diff options
| -rw-r--r-- | llvm/include/llvm/Analysis/LazyCallGraph.h | 253 | ||||
| -rw-r--r-- | llvm/lib/Analysis/LazyCallGraph.cpp | 293 | ||||
| -rw-r--r-- | llvm/test/Analysis/LazyCallGraph/basic.ll | 54 | ||||
| -rw-r--r-- | llvm/test/Analysis/LazyCallGraph/non-leaf-intrinsics.ll | 4 | ||||
| -rw-r--r-- | llvm/unittests/Analysis/LazyCallGraphTest.cpp | 62 |
5 files changed, 418 insertions, 248 deletions
diff --git a/llvm/include/llvm/Analysis/LazyCallGraph.h b/llvm/include/llvm/Analysis/LazyCallGraph.h index e02f3ab2de1..d3bd2d19d7e 100644 --- a/llvm/include/llvm/Analysis/LazyCallGraph.h +++ b/llvm/include/llvm/Analysis/LazyCallGraph.h @@ -104,9 +104,79 @@ class LazyCallGraph { public: class Node; class SCC; - class iterator; - typedef SmallVector<PointerUnion<Function *, Node *>, 4> NodeVectorT; - typedef SmallVectorImpl<PointerUnion<Function *, Node *>> NodeVectorImplT; + class edge_iterator; + + /// A class used to represent edges in the call graph. + /// + /// The lazy call graph models both *call* edges and *reference* edges. Call + /// edges are much what you would expect, and exist when there is a 'call' or + /// 'invoke' instruction of some function. Reference edges are also tracked + /// along side these, and exist whenever any instruction (transitively + /// through its operands) references a function. All call edges are + /// inherently reference edges, and so the reference graph forms a superset + /// of the formal call graph. + /// + /// Furthermore, edges also may point to raw \c Function objects when those + /// functions have not been scanned and incorporated into the graph (yet). + /// This is one of the primary ways in which the graph can be lazy. When + /// functions are scanned and fully incorporated into the graph, all of the + /// edges referencing them are updated to point to the graph \c Node objects + /// instead of to the raw \c Function objects. This class even provides + /// methods to trigger this scan on-demand by attempting to get the target + /// node of the graph and providing a reference back to the graph in order to + /// lazily build it if necessary. + /// + /// All of these forms of edges are fundamentally represented as outgoing + /// edges. The edges are stored in the source node and point at the target + /// node. This allows the edge structure itself to be a very compact data + /// structure: essentially a tagged pointer. + class Edge { + public: + /// The kind of edge in the graph. + enum Kind : bool { Ref = false, Call = true }; + + Edge(); + explicit Edge(Function &F, Kind K); + explicit Edge(Node &N, Kind K); + + /// Test whether the edge is null. + /// + /// This happens when an edge has been deleted. We leave the edge objects + /// around but clear them. + operator bool() const; + + /// Test whether the edge represents a direct call to a function. + /// + /// This requires that the edge is not null. + bool isCall() const; + + /// Get the function referenced by this edge. + /// + /// This requires that the edge is not null, but will succeed whether we + /// have built a graph node for the function yet or not. + Function &getFunction() const; + + /// Get the call graph node referenced by this edge if one exists. + /// + /// This requires that the edge is not null. If we have built a graph node + /// for the function this edge points to, this will return that node, + /// otherwise it will return null. + Node *getNode() const; + + /// Get the call graph node for this edge, building it if necessary. + /// + /// This requires that the edge is not null. If we have not yet built + /// a graph node for the function this edge points to, this will first ask + /// the graph to build that node, inserting it into all the relevant + /// structures. + Node &getNode(LazyCallGraph &G); + + private: + PointerIntPair<PointerUnion<Function *, Node *>, 1, Kind> Value; + }; + + typedef SmallVector<Edge, 4> EdgeVectorT; + typedef SmallVectorImpl<Edge> EdgeVectorImplT; /// A node in the call graph. /// @@ -125,31 +195,33 @@ public: int DFSNumber; int LowLink; - mutable NodeVectorT Callees; - DenseMap<Function *, size_t> CalleeIndexMap; + mutable EdgeVectorT Edges; + DenseMap<Function *, size_t> EdgeIndexMap; - /// Basic constructor implements the scanning of F into Callees and - /// CalleeIndexMap. + /// Basic constructor implements the scanning of F into Edges and + /// EdgeIndexMap. Node(LazyCallGraph &G, Function &F); - /// Internal helper to insert a callee. - void insertEdgeInternal(Function &Callee); + /// Internal helper to insert an edge to a function. + void insertEdgeInternal(Function &ChildF, Edge::Kind EK); - /// Internal helper to insert a callee. - void insertEdgeInternal(Node &CalleeN); + /// Internal helper to insert an edge to a node. + void insertEdgeInternal(Node &ChildN, Edge::Kind EK); - /// Internal helper to remove a callee from this node. - void removeEdgeInternal(Function &Callee); + /// Internal helper to remove the edge to the given function. + void removeEdgeInternal(Function &ChildF); public: - typedef LazyCallGraph::iterator iterator; + typedef LazyCallGraph::edge_iterator edge_iterator; + + LazyCallGraph &getGraph() const { return *G; } Function &getFunction() const { return F; } - iterator begin() const { - return iterator(*G, Callees.begin(), Callees.end()); + edge_iterator begin() const { + return edge_iterator(Edges.begin(), Edges.end()); } - iterator end() const { return iterator(*G, Callees.end(), Callees.end()); } + edge_iterator end() const { return edge_iterator(Edges.end(), Edges.end()); } /// Equality is defined as address equality. bool operator==(const Node &N) const { return this == &N; } @@ -162,42 +234,68 @@ public: /// be scanned for "calls" or uses of functions and its child information /// will be constructed. All of these results are accumulated and cached in /// the graph. - class iterator - : public iterator_adaptor_base<iterator, NodeVectorImplT::iterator, - std::forward_iterator_tag, Node> { + class edge_iterator + : public iterator_adaptor_base<edge_iterator, EdgeVectorImplT::iterator, + std::forward_iterator_tag> { friend class LazyCallGraph; friend class LazyCallGraph::Node; - LazyCallGraph *G; - NodeVectorImplT::iterator E; + EdgeVectorImplT::iterator E; - // Build the iterator for a specific position in a node list. - iterator(LazyCallGraph &G, NodeVectorImplT::iterator NI, - NodeVectorImplT::iterator E) - : iterator_adaptor_base(NI), G(&G), E(E) { - while (I != E && I->isNull()) + // Build the iterator for a specific position in the edge list. + edge_iterator(EdgeVectorImplT::iterator BaseI, + EdgeVectorImplT::iterator E) + : iterator_adaptor_base(BaseI), E(E) { + while (I != E && !*I) ++I; } public: - iterator() {} + edge_iterator() {} using iterator_adaptor_base::operator++; - iterator &operator++() { + edge_iterator &operator++() { do { ++I; - } while (I != E && I->isNull()); + } while (I != E && !*I); return *this; } + }; + + /// A lazy iterator over specifically call edges. + /// + /// This has the same iteration properties as the \c edge_iterator, but + /// restricts itself to edges which represent actual calls. + class call_edge_iterator + : public iterator_adaptor_base<call_edge_iterator, + EdgeVectorImplT::iterator, + std::forward_iterator_tag> { + friend class LazyCallGraph; + friend class LazyCallGraph::Node; - reference operator*() const { - if (I->is<Node *>()) - return *I->get<Node *>(); + EdgeVectorImplT::iterator E; - Function *F = I->get<Function *>(); - Node &ChildN = G->get(*F); - *I = &ChildN; - return ChildN; + /// Advance the iterator to the next valid, call edge. + void advanceToNextEdge() { + while (I != E && (!*I || !I->isCall())) + ++I; + } + + // Build the iterator for a specific position in the edge list. + call_edge_iterator(EdgeVectorImplT::iterator BaseI, + EdgeVectorImplT::iterator E) + : iterator_adaptor_base(BaseI), E(E) { + advanceToNextEdge(); + } + + public: + call_edge_iterator() {} + + using iterator_adaptor_base::operator++; + call_edge_iterator &operator++() { + ++I; + advanceToNextEdge(); + return *this; } }; @@ -219,7 +317,7 @@ public: void insert(Node &N); void - internalDFS(SmallVectorImpl<std::pair<Node *, Node::iterator>> &DFSStack, + internalDFS(SmallVectorImpl<std::pair<Node *, Node::edge_iterator>> &DFSStack, SmallVectorImpl<Node *> &PendingSCCStack, Node *N, SmallVectorImpl<SCC *> &ResultSCCs); @@ -271,14 +369,14 @@ public: /// /// By the definition of an SCC, this does not change the nature or make-up /// of any SCCs. - void insertIntraSCCEdge(Node &CallerN, Node &CalleeN); + void insertIntraSCCEdge(Node &ParentN, Node &ChildN, Edge::Kind EK); /// Insert an edge whose tail is in this SCC and head is in some child SCC. /// /// 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 &CallerN, Node &CalleeN); + void insertOutgoingEdge(Node &ParentN, Node &ChildN, Edge::Kind EK); /// Insert an edge whose tail is in a descendant SCC and head is in this /// SCC. @@ -294,7 +392,8 @@ public: /// 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 &CallerN, Node &CalleeN); + SmallVector<SCC *, 1> insertIncomingEdge(Node &ParentN, Node &ChildN, + Edge::Kind EK); /// Remove an edge whose source is in this SCC and target is *not*. /// @@ -306,11 +405,11 @@ public: /// 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 &CallerN, Node &CalleeN); + void removeInterSCCEdge(Node &ParentN, Node &ChildN); /// Remove an edge which is entirely within this SCC. /// - /// Both the \a Caller and the \a Callee must be within this SCC. Removing + /// 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 @@ -340,7 +439,7 @@ public: /// 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 &CallerN, Node &CalleeN); + SmallVector<SCC *, 1> removeIntraSCCEdge(Node &ParentN, Node &ChildN); ///@} }; @@ -396,10 +495,12 @@ public: LazyCallGraph(LazyCallGraph &&G); LazyCallGraph &operator=(LazyCallGraph &&RHS); - iterator begin() { - return iterator(*this, EntryNodes.begin(), EntryNodes.end()); + edge_iterator begin() { + return edge_iterator(EntryEdges.begin(), EntryEdges.end()); + } + edge_iterator end() { + return edge_iterator(EntryEdges.end(), EntryEdges.end()); } - iterator end() { return iterator(*this, EntryNodes.end(), EntryNodes.end()); } postorder_scc_iterator postorder_scc_begin() { return postorder_scc_iterator(*this); @@ -442,11 +543,11 @@ public: /// mutation of the graph via the SCC methods. /// Update the call graph after inserting a new edge. - void insertEdge(Node &Caller, Function &Callee); + void insertEdge(Node &Caller, Function &Callee, Edge::Kind EK); /// Update the call graph after inserting a new edge. - void insertEdge(Function &Caller, Function &Callee) { - return insertEdge(get(Caller), Callee); + void insertEdge(Function &Caller, Function &Callee, Edge::Kind EK) { + return insertEdge(get(Caller), Callee, EK); } /// Update the call graph after deleting an edge. @@ -470,9 +571,9 @@ private: /// /// These nodes are reachable through "external" means. Put another way, they /// escape at the module scope. - NodeVectorT EntryNodes; + EdgeVectorT EntryEdges; - /// Map of the entry nodes in the graph to their indices in \c EntryNodes. + /// Map of the entry nodes in the graph to their indices in \c EntryEdges. DenseMap<Function *, size_t> EntryIndexMap; /// Allocator that holds all the call graph SCCs. @@ -487,7 +588,7 @@ private: SmallVector<SCC *, 4> LeafSCCs; /// Stack of nodes in the DFS walk. - SmallVector<std::pair<Node *, iterator>, 4> DFSStack; + SmallVector<std::pair<Node *, edge_iterator>, 4> DFSStack; /// Set of entry nodes not-yet-processed into SCCs. SmallVector<Function *, 4> SCCEntryNodes; @@ -513,10 +614,52 @@ private: SCC *getNextSCCInPostOrder(); }; +inline LazyCallGraph::Edge::Edge() : Value() {} +inline LazyCallGraph::Edge::Edge(Function &F, Kind K) : Value(&F, K) {} +inline LazyCallGraph::Edge::Edge(Node &N, Kind K) : Value(&N, K) {} + +inline LazyCallGraph::Edge::operator bool() const { + return !Value.getPointer().isNull(); +} + +inline bool LazyCallGraph::Edge::isCall() const { + assert(*this && "Queried a null edge!"); + return Value.getInt() == Call; +} + +inline Function &LazyCallGraph::Edge::getFunction() const { + assert(*this && "Queried a null edge!"); + auto P = Value.getPointer(); + if (auto *F = P.dyn_cast<Function *>()) + return *F; + + return P.get<Node *>()->getFunction(); +} + +inline LazyCallGraph::Node *LazyCallGraph::Edge::getNode() const { + assert(*this && "Queried a null edge!"); + auto P = Value.getPointer(); + if (auto *N = P.dyn_cast<Node *>()) + return N; + + return nullptr; +} + +inline LazyCallGraph::Node &LazyCallGraph::Edge::getNode(LazyCallGraph &G) { + assert(*this && "Queried a null edge!"); + auto P = Value.getPointer(); + if (auto *N = P.dyn_cast<Node *>()) + return *N; + + Node &N = G.get(*P.get<Function *>()); + Value.setPointer(&N); + return N; +} + // Provide GraphTraits specializations for call graphs. template <> struct GraphTraits<LazyCallGraph::Node *> { typedef LazyCallGraph::Node NodeType; - typedef LazyCallGraph::iterator ChildIteratorType; + typedef LazyCallGraph::edge_iterator ChildIteratorType; static NodeType *getEntryNode(NodeType *N) { return N; } static ChildIteratorType child_begin(NodeType *N) { return N->begin(); } @@ -524,7 +667,7 @@ template <> struct GraphTraits<LazyCallGraph::Node *> { }; template <> struct GraphTraits<LazyCallGraph *> { typedef LazyCallGraph::Node NodeType; - typedef LazyCallGraph::iterator ChildIteratorType; + typedef LazyCallGraph::edge_iterator ChildIteratorType; static NodeType *getEntryNode(NodeType *N) { return N; } static ChildIteratorType child_begin(NodeType *N) { return N->begin(); } diff --git a/llvm/lib/Analysis/LazyCallGraph.cpp b/llvm/lib/Analysis/LazyCallGraph.cpp index 0f0f31e62ac..11e1166001a 100644 --- a/llvm/lib/Analysis/LazyCallGraph.cpp +++ b/llvm/lib/Analysis/LazyCallGraph.cpp @@ -20,30 +20,36 @@ using namespace llvm; #define DEBUG_TYPE "lcg" -static void findCallees( - SmallVectorImpl<Constant *> &Worklist, SmallPtrSetImpl<Constant *> &Visited, - SmallVectorImpl<PointerUnion<Function *, LazyCallGraph::Node *>> &Callees, - DenseMap<Function *, size_t> &CalleeIndexMap) { +static void addEdge(SmallVectorImpl<LazyCallGraph::Edge> &Edges, + DenseMap<Function *, size_t> &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 + // some other module (say, a weak definition) there may still be + // optimizations which essentially speculate based on the definition and + // a way to check that the specific definition is in fact the one being + // used. For example, this could be done by moving the weak definition to + // a strong (internal) definition and making the weak definition be an + // alias. Then a test of the address of the weak function against the new + // 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) { + 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) { while (!Worklist.empty()) { Constant *C = Worklist.pop_back_val(); if (Function *F = dyn_cast<Function>(C)) { - // 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 - // some other module (say, a weak definition) there may still be - // optimizations which essentially speculate based on the definition and - // a way to check that the specific definition is in fact the one being - // used. For example, this could be done by moving the weak definition to - // a strong (internal) definition and making the weak definition be an - // alias. Then a test of the address of the weak function against the new - // strong definition's address would be an effective way to determine the - // safety of optimizing a direct call edge. - if (!F->isDeclaration() && - CalleeIndexMap.insert(std::make_pair(F, Callees.size())).second) { - DEBUG(dbgs() << " Added callable function: " << F->getName() - << "\n"); - Callees.push_back(F); - } + addEdge(Edges, EdgeIndexMap, *F, LazyCallGraph::Edge::Ref); continue; } @@ -59,42 +65,55 @@ LazyCallGraph::Node::Node(LazyCallGraph &G, Function &F) << "' to the graph.\n"); SmallVector<Constant *, 16> Worklist; + SmallPtrSet<Function *, 4> Callees; SmallPtrSet<Constant *, 16> Visited; - // Find all the potential callees in this function. First walk the - // instructions and add every operand which is a constant to the worklist. + + // Find all the potential call graph edges in this function. We track both + // actual call edges and indirect references to functions. The direct calls + // are trivially added, but to accumulate the latter we walk the instructions + // and add every operand which is a constant to the worklist to process + // afterward. for (BasicBlock &BB : F) - for (Instruction &I : BB) + for (Instruction &I : BB) { + if (auto CS = CallSite(&I)) + if (Function *Callee = CS.getCalledFunction()) + if (Callees.insert(Callee).second) { + Visited.insert(Callee); + addEdge(Edges, EdgeIndexMap, *Callee, LazyCallGraph::Edge::Call); + } + for (Value *Op : I.operand_values()) if (Constant *C = dyn_cast<Constant>(Op)) if (Visited.insert(C).second) Worklist.push_back(C); + } // We've collected all the constant (and thus potentially function or // function containing) operands to all of the instructions in the function. // Process them (recursively) collecting every function found. - findCallees(Worklist, Visited, Callees, CalleeIndexMap); + findReferences(Worklist, Visited, Edges, EdgeIndexMap); } -void LazyCallGraph::Node::insertEdgeInternal(Function &Callee) { - if (Node *N = G->lookup(Callee)) - return insertEdgeInternal(*N); +void LazyCallGraph::Node::insertEdgeInternal(Function &Child, Edge::Kind EK) { + if (Node *N = G->lookup(Child)) + return insertEdgeInternal(*N, EK); - CalleeIndexMap.insert(std::make_pair(&Callee, Callees.size())); - Callees.push_back(&Callee); + EdgeIndexMap.insert(std::make_pair(&Child, Edges.size())); + Edges.emplace_back(Child, EK); } -void LazyCallGraph::Node::insertEdgeInternal(Node &CalleeN) { - CalleeIndexMap.insert(std::make_pair(&CalleeN.getFunction(), Callees.size())); - Callees.push_back(&CalleeN); +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::removeEdgeInternal(Function &Callee) { - auto IndexMapI = CalleeIndexMap.find(&Callee); - assert(IndexMapI != CalleeIndexMap.end() && - "Callee not in the callee set for this caller?"); +void LazyCallGraph::Node::removeEdgeInternal(Function &Child) { + auto IndexMapI = EdgeIndexMap.find(&Child); + assert(IndexMapI != EdgeIndexMap.end() && + "Child not in the edge set for this caller?"); - Callees[IndexMapI->second] = nullptr; - CalleeIndexMap.erase(IndexMapI); + Edges[IndexMapI->second] = Edge(); + EdgeIndexMap.erase(IndexMapI); } LazyCallGraph::LazyCallGraph(Module &M) : NextDFSNumber(0) { @@ -102,10 +121,10 @@ LazyCallGraph::LazyCallGraph(Module &M) : NextDFSNumber(0) { << "\n"); for (Function &F : M) if (!F.isDeclaration() && !F.hasLocalLinkage()) - if (EntryIndexMap.insert(std::make_pair(&F, EntryNodes.size())).second) { + if (EntryIndexMap.insert(std::make_pair(&F, EntryEdges.size())).second) { DEBUG(dbgs() << " Adding '" << F.getName() << "' to entry set of the graph.\n"); - EntryNodes.push_back(&F); + EntryEdges.emplace_back(F, Edge::Ref); } // Now add entry nodes for functions reachable via initializers to globals. @@ -118,21 +137,15 @@ LazyCallGraph::LazyCallGraph(Module &M) : NextDFSNumber(0) { DEBUG(dbgs() << " Adding functions referenced by global initializers to the " "entry set.\n"); - findCallees(Worklist, Visited, EntryNodes, EntryIndexMap); - - for (auto &Entry : EntryNodes) { - assert(!Entry.isNull() && - "We can't have removed edges before we finish the constructor!"); - if (Function *F = Entry.dyn_cast<Function *>()) - SCCEntryNodes.push_back(F); - else - SCCEntryNodes.push_back(&Entry.get<Node *>()->getFunction()); - } + findReferences(Worklist, Visited, EntryEdges, EntryIndexMap); + + for (const Edge &E : EntryEdges) + SCCEntryNodes.push_back(&E.getFunction()); } LazyCallGraph::LazyCallGraph(LazyCallGraph &&G) : BPA(std::move(G.BPA)), NodeMap(std::move(G.NodeMap)), - EntryNodes(std::move(G.EntryNodes)), + 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)), DFSStack(std::move(G.DFSStack)), @@ -144,7 +157,7 @@ LazyCallGraph::LazyCallGraph(LazyCallGraph &&G) LazyCallGraph &LazyCallGraph::operator=(LazyCallGraph &&G) { BPA = std::move(G.BPA); NodeMap = std::move(G.NodeMap); - EntryNodes = std::move(G.EntryNodes); + EntryEdges = std::move(G.EntryEdges); EntryIndexMap = std::move(G.EntryIndexMap); SCCBPA = std::move(G.SCCBPA); SCCMap = std::move(G.SCCMap); @@ -177,43 +190,46 @@ bool LazyCallGraph::SCC::isDescendantOf(const SCC &C) const { return false; } -void LazyCallGraph::SCC::insertIntraSCCEdge(Node &CallerN, Node &CalleeN) { +void LazyCallGraph::SCC::insertIntraSCCEdge(Node &ParentN, Node &ChildN, + Edge::Kind EK) { // First insert it into the caller. - CallerN.insertEdgeInternal(CalleeN); + ParentN.insertEdgeInternal(ChildN, EK); - assert(G->SCCMap.lookup(&CallerN) == this && "Caller must be in this SCC."); - assert(G->SCCMap.lookup(&CalleeN) == this && "Callee must be in this SCC."); + assert(G->SCCMap.lookup(&ParentN) == this && "Parent must be in this SCC."); + assert(G->SCCMap.lookup(&ChildN) == this && "Child must be in this SCC."); // Nothing changes about this SCC or any other. } -void LazyCallGraph::SCC::insertOutgoingEdge(Node &CallerN, Node &CalleeN) { +void LazyCallGraph::SCC::insertOutgoingEdge(Node &ParentN, Node &ChildN, + Edge::Kind EK) { // First insert it into the caller. - CallerN.insertEdgeInternal(CalleeN); + ParentN.insertEdgeInternal(ChildN, EK); - assert(G->SCCMap.lookup(&CallerN) == this && "Caller must be in this SCC."); + assert(G->SCCMap.lookup(&ParentN) == this && "Parent must be in this SCC."); - SCC &CalleeC = *G->SCCMap.lookup(&CalleeN); - assert(&CalleeC != this && "Callee must not be in this SCC."); - assert(CalleeC.isDescendantOf(*this) && - "Callee must be a descendant of the Caller."); + 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."); // The only change required is to add this SCC to the parent set of the // callee. - CalleeC.ParentSCCs.insert(this); + ChildC.ParentSCCs.insert(this); } SmallVector<LazyCallGraph::SCC *, 1> -LazyCallGraph::SCC::insertIncomingEdge(Node &CallerN, Node &CalleeN) { +LazyCallGraph::SCC::insertIncomingEdge(Node &ParentN, Node &ChildN, + Edge::Kind EK) { // First insert it into the caller. - CallerN.insertEdgeInternal(CalleeN); + ParentN.insertEdgeInternal(ChildN, EK); - assert(G->SCCMap.lookup(&CalleeN) == this && "Callee must be in this SCC."); + assert(G->SCCMap.lookup(&ChildN) == this && "Child must be in this SCC."); - SCC &CallerC = *G->SCCMap.lookup(&CallerN); - assert(&CallerC != this && "Caller must not be in this SCC."); - assert(CallerC.isDescendantOf(*this) && - "Caller must be a descendant of the Callee."); + 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."); // 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 @@ -231,7 +247,7 @@ LazyCallGraph::SCC::insertIncomingEdge(Node &CallerN, Node &CalleeN) { // participate in the merged connected component. SmallPtrSet<SCC *, 8> ConnectedSCCs; ConnectedSCCs.insert(this); - ConnectedSCCs.insert(&CallerC); + ConnectedSCCs.insert(&ParentC); // We build up a DFS stack of the parents chains. SmallVector<std::pair<SCC *, SCC::parent_iterator>, 8> DFSSCCs; @@ -298,8 +314,9 @@ LazyCallGraph::SCC::insertIncomingEdge(Node &CallerN, Node &CalleeN) { C->ParentSCCs.clear(); for (Node *N : *C) { - for (Node &ChildN : *N) { - SCC &ChildC = *G->SCCMap.lookup(&ChildN); + 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); } @@ -309,8 +326,9 @@ LazyCallGraph::SCC::insertIncomingEdge(Node &CallerN, Node &CalleeN) { C->Nodes.clear(); } for (auto I = Nodes.begin() + NewNodeBeginIdx, E = Nodes.end(); I != E; ++I) - for (Node &ChildN : **I) { - SCC &ChildC = *G->SCCMap.lookup(&ChildN); + 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); } @@ -322,64 +340,65 @@ LazyCallGraph::SCC::insertIncomingEdge(Node &CallerN, Node &CalleeN) { return SmallVector<SCC *, 1>(ConnectedSCCs.begin(), ConnectedSCCs.end()); } -void LazyCallGraph::SCC::removeInterSCCEdge(Node &CallerN, Node &CalleeN) { +void LazyCallGraph::SCC::removeInterSCCEdge(Node &ParentN, Node &ChildN) { // First remove it from the node. - CallerN.removeEdgeInternal(CalleeN.getFunction()); + ParentN.removeEdgeInternal(ChildN.getFunction()); - assert(G->SCCMap.lookup(&CallerN) == this && + assert(G->SCCMap.lookup(&ParentN) == this && "The caller must be a member of this SCC."); - SCC &CalleeC = *G->SCCMap.lookup(&CalleeN); - assert(&CalleeC != this && + 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 HasOtherCallToCalleeC = false; - bool HasOtherCallOutsideSCC = false; + bool HasOtherEdgeToChildC = false; + bool HasOtherChildC = false; for (Node *N : *this) { - for (Node &OtherCalleeN : *N) { - SCC &OtherCalleeC = *G->SCCMap.lookup(&OtherCalleeN); - if (&OtherCalleeC == &CalleeC) { - HasOtherCallToCalleeC = true; + 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; } - if (&OtherCalleeC != this) - HasOtherCallOutsideSCC = true; + if (&OtherChildC != this) + HasOtherChildC = true; } - if (HasOtherCallToCalleeC) + if (HasOtherEdgeToChildC) 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 caller no longer a parent of the callee. Walk the other call edges - // in the caller to tell. - if (!HasOtherCallToCalleeC) { - bool Removed = CalleeC.ParentSCCs.erase(this); + // 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); (void)Removed; assert(Removed && - "Did not find the caller SCC in the callee SCC's parent list!"); + "Did not find the parent SCC in the child 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 (CalleeC.ParentSCCs.empty()) - DEBUG(dbgs() << "LCG: Update removing " << CallerN.getFunction().getName() - << " -> " << CalleeN.getFunction().getName() + if (ChildC.ParentSCCs.empty()) + DEBUG(dbgs() << "LCG: Update removing " << ParentN.getFunction().getName() + << " -> " << ChildN.getFunction().getName() << " edge orphaned the callee's SCC!\n"); } - // It may make the Caller SCC a leaf SCC. - if (!HasOtherCallOutsideSCC) + // It may make the Parent SCC a leaf SCC. + if (!HasOtherChildC) G->LeafSCCs.push_back(this); } void LazyCallGraph::SCC::internalDFS( - SmallVectorImpl<std::pair<Node *, Node::iterator>> &DFSStack, + SmallVectorImpl<std::pair<Node *, Node::edge_iterator>> &DFSStack, SmallVectorImpl<Node *> &PendingSCCStack, Node *N, SmallVectorImpl<SCC *> &ResultSCCs) { - Node::iterator I = N->begin(); + auto I = N->begin(); N->LowLink = N->DFSNumber = 1; int NextDFSNumber = 2; for (;;) { @@ -387,9 +406,9 @@ void LazyCallGraph::SCC::internalDFS( "before processing a node."); // We simulate recursion by popping out of the nested loop and continuing. - Node::iterator E = N->end(); + auto E = N->end(); while (I != E) { - Node &ChildN = *I; + 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 @@ -455,15 +474,15 @@ void LazyCallGraph::SCC::internalDFS( } SmallVector<LazyCallGraph::SCC *, 1> -LazyCallGraph::SCC::removeIntraSCCEdge(Node &CallerN, Node &CalleeN) { +LazyCallGraph::SCC::removeIntraSCCEdge(Node &ParentN, Node &ChildN) { // First remove it from the node. - CallerN.removeEdgeInternal(CalleeN.getFunction()); + ParentN.removeEdgeInternal(ChildN.getFunction()); // We return a list of the resulting *new* SCCs in postorder. SmallVector<SCC *, 1> ResultSCCs; // Direct recursion doesn't impact the SCC graph at all. - if (&CallerN == &CalleeN) + if (&ParentN == &ChildN) return ResultSCCs; // The worklist is every node in the original SCC. @@ -478,16 +497,16 @@ LazyCallGraph::SCC::removeIntraSCCEdge(Node &CallerN, Node &CalleeN) { assert(Worklist.size() > 1 && "We have to have at least two nodes to have an " "edge between them that is within the SCC."); - // The callee can already reach every node in this SCC (by definition). It is + // 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 Callee will also remain in the SCC. To model this we + // 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(CalleeN); + insert(ChildN); // We're going to do a full mini-Tarjan's walk using a local stack here. - SmallVector<std::pair<Node *, Node::iterator>, 4> DFSStack; + SmallVector<std::pair<Node *, Node::edge_iterator>, 4> DFSStack; SmallVector<Node *, 4> PendingSCCStack; do { Node *N = Worklist.pop_back_val(); @@ -501,8 +520,9 @@ LazyCallGraph::SCC::removeIntraSCCEdge(Node &CallerN, Node &CalleeN) { // Now we need to reconnect the current SCC to the graph. bool IsLeafSCC = true; for (Node *N : Nodes) { - for (Node &ChildN : *N) { - SCC &ChildSCC = *G->SCCMap.lookup(&ChildN); + 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); @@ -528,18 +548,18 @@ LazyCallGraph::SCC::removeIntraSCCEdge(Node &CallerN, Node &CalleeN) { return ResultSCCs; } -void LazyCallGraph::insertEdge(Node &CallerN, Function &Callee) { +void LazyCallGraph::insertEdge(Node &ParentN, Function &Child, Edge::Kind EK) { assert(SCCMap.empty() && DFSStack.empty() && "This method cannot be called after SCCs have been formed!"); - return CallerN.insertEdgeInternal(Callee); + return ParentN.insertEdgeInternal(Child, EK); } -void LazyCallGraph::removeEdge(Node &CallerN, Function &Callee) { +void LazyCallGraph::removeEdge(Node &ParentN, Function &Child) { assert(SCCMap.empty() && DFSStack.empty() && "This method cannot be called after SCCs have been formed!"); - return CallerN.removeEdgeInternal(Callee); + return ParentN.removeEdgeInternal(Child); } LazyCallGraph::Node &LazyCallGraph::insertInto(Function &F, Node *&MappedN) { @@ -550,17 +570,16 @@ void LazyCallGraph::updateGraphPtrs() { // Process all nodes updating the graph pointers. { SmallVector<Node *, 16> Worklist; - for (auto &Entry : EntryNodes) - if (Node *EntryN = Entry.dyn_cast<Node *>()) + for (Edge &E : EntryEdges) + if (Node *EntryN = E.getNode()) Worklist.push_back(EntryN); while (!Worklist.empty()) { Node *N = Worklist.pop_back_val(); N->G = this; - for (auto &Callee : N->Callees) - if (!Callee.isNull()) - if (Node *CalleeN = Callee.dyn_cast<Node *>()) - Worklist.push_back(CalleeN); + for (Edge &E : N->Edges) + if (Node *ChildN = E.getNode()) + Worklist.push_back(ChildN); } } @@ -596,8 +615,9 @@ LazyCallGraph::SCC *LazyCallGraph::formSCC(Node *RootN, // its children. bool IsLeafSCC = true; for (Node *SCCN : NewSCC->Nodes) - for (Node &SCCChildN : *SCCN) { - SCC &ChildSCC = *SCCMap.lookup(&SCCChildN); + 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); @@ -613,7 +633,7 @@ LazyCallGraph::SCC *LazyCallGraph::formSCC(Node *RootN, LazyCallGraph::SCC *LazyCallGraph::getNextSCCInPostOrder() { Node *N; - Node::iterator I; + Node::edge_iterator I; if (!DFSStack.empty()) { N = DFSStack.back().first; I = DFSStack.back().second; @@ -635,9 +655,9 @@ LazyCallGraph::SCC *LazyCallGraph::getNextSCCInPostOrder() { assert(N->DFSNumber != 0 && "We should always assign a DFS number " "before placing a node onto the stack."); - Node::iterator E = N->end(); + auto E = N->end(); while (I != E) { - Node &ChildN = *I; + 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 @@ -686,14 +706,19 @@ 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::Node &ChildN : N) + for (LazyCallGraph::Edge &E : N) { + LazyCallGraph::Node &ChildN = E.getNode(G); if (Printed.insert(&ChildN).second) printNodes(OS, ChildN, Printed); + } - OS << " Call edges in function: " << N.getFunction().getName() << "\n"; - for (LazyCallGraph::iterator I = N.begin(), E = N.end(); I != E; ++I) - OS << " -> " << I->getFunction().getName() << "\n"; + OS << " Edges in function: " << N.getFunction().getName() << "\n"; + for (const LazyCallGraph::Edge &E : N) + OS << " " << (E.isCall() ? "call" : "ref ") << " -> " + << E.getFunction().getName() << "\n"; OS << "\n"; } @@ -716,9 +741,11 @@ PreservedAnalyses LazyCallGraphPrinterPass::run(Module &M, << "\n\n"; SmallPtrSet<LazyCallGraph::Node *, 16> Printed; - for (LazyCallGraph::Node &N : G) + for (LazyCallGraph::Edge &E : G) { + LazyCallGraph::Node &N = E.getNode(G); if (Printed.insert(&N).second) printNodes(OS, N, Printed); + } for (LazyCallGraph::SCC &SCC : G.postorder_sccs()) printSCC(OS, SCC); diff --git a/llvm/test/Analysis/LazyCallGraph/basic.ll b/llvm/test/Analysis/LazyCallGraph/basic.ll index fce453bc15d..418559578b4 100644 --- a/llvm/test/Analysis/LazyCallGraph/basic.ll +++ b/llvm/test/Analysis/LazyCallGraph/basic.ll @@ -3,7 +3,7 @@ ; Basic validation of the call graph analysis used in the new pass manager. define void @f() { -; CHECK-LABEL: Call edges in function: f +; CHECK-LABEL: Edges in function: f ; CHECK-NOT: -> entry: @@ -51,8 +51,8 @@ define void @f12() { declare i32 @__gxx_personality_v0(...) define void @test0() { -; CHECK-LABEL: Call edges in function: test0 -; CHECK-NEXT: -> f +; CHECK-LABEL: Edges in function: test0 +; CHECK-NEXT: call -> f ; CHECK-NOT: -> entry: @@ -64,19 +64,19 @@ entry: } define void ()* @test1(void ()** %x) personality i32 (...)* @__gxx_personality_v0 { -; CHECK-LABEL: Call edges in function: test1 -; CHECK-NEXT: -> f12 -; CHECK-NEXT: -> f11 -; CHECK-NEXT: -> f10 -; CHECK-NEXT: -> f7 -; CHECK-NEXT: -> f9 -; CHECK-NEXT: -> f8 -; CHECK-NEXT: -> f6 -; CHECK-NEXT: -> f5 -; CHECK-NEXT: -> f4 -; CHECK-NEXT: -> f3 -; CHECK-NEXT: -> f2 -; CHECK-NEXT: -> f1 +; CHECK-LABEL: Edges in function: test1 +; CHECK-NEXT: call -> f6 +; CHECK-NEXT: call -> f10 +; CHECK-NEXT: ref -> f12 +; CHECK-NEXT: ref -> f11 +; CHECK-NEXT: ref -> f7 +; CHECK-NEXT: ref -> f9 +; CHECK-NEXT: ref -> f8 +; CHECK-NEXT: ref -> f5 +; CHECK-NEXT: ref -> f4 +; CHECK-NEXT: ref -> f3 +; CHECK-NEXT: ref -> f2 +; CHECK-NEXT: ref -> f1 ; CHECK-NOT: -> entry: @@ -108,14 +108,14 @@ unwind: @h = constant void ()* @f7 define void @test2() { -; CHECK-LABEL: Call edges in function: test2 -; CHECK-NEXT: -> f7 -; CHECK-NEXT: -> f6 -; CHECK-NEXT: -> f5 -; CHECK-NEXT: -> f4 -; CHECK-NEXT: -> f3 -; CHECK-NEXT: -> f2 -; CHECK-NEXT: -> f1 +; CHECK-LABEL: Edges in function: test2 +; CHECK-NEXT: ref -> f7 +; CHECK-NEXT: ref -> f6 +; CHECK-NEXT: ref -> f5 +; CHECK-NEXT: ref -> f4 +; CHECK-NEXT: ref -> f3 +; CHECK-NEXT: ref -> f2 +; CHECK-NEXT: ref -> f1 ; CHECK-NOT: -> load i8*, i8** bitcast (void ()** @g to i8**) @@ -152,13 +152,13 @@ define void @test2() { ; CHECK-NEXT: test2 ; ; CHECK-LABEL: SCC with 1 functions: -; CHECK-NEXT: f12 +; CHECK-NEXT: f10 ; ; CHECK-LABEL: SCC with 1 functions: -; CHECK-NEXT: f11 +; CHECK-NEXT: f12 ; ; CHECK-LABEL: SCC with 1 functions: -; CHECK-NEXT: f10 +; CHECK-NEXT: f11 ; ; CHECK-LABEL: SCC with 1 functions: ; CHECK-NEXT: f9 diff --git a/llvm/test/Analysis/LazyCallGraph/non-leaf-intrinsics.ll b/llvm/test/Analysis/LazyCallGraph/non-leaf-intrinsics.ll index 89a21e542f7..ce6d63b7aff 100644 --- a/llvm/test/Analysis/LazyCallGraph/non-leaf-intrinsics.ll +++ b/llvm/test/Analysis/LazyCallGraph/non-leaf-intrinsics.ll @@ -8,7 +8,7 @@ define private void @f() { } define void @calls_statepoint(i8 addrspace(1)* %arg) gc "statepoint-example" { -; CHECK: Call edges in function: calls_statepoint +; CHECK: Edges in function: calls_statepoint ; CHECK-NEXT: -> f entry: %cast = bitcast i8 addrspace(1)* %arg to i64 addrspace(1)* @@ -17,7 +17,7 @@ entry: } define void @calls_patchpoint() { -; CHECK: Call edges in function: calls_patchpoint +; CHECK: Edges in function: calls_patchpoint ; CHECK-NEXT: -> f entry: %c = bitcast void()* @f to i8* diff --git a/llvm/unittests/Analysis/LazyCallGraphTest.cpp b/llvm/unittests/Analysis/LazyCallGraphTest.cpp index 6caccb89239..fb3eeb7d234 100644 --- a/llvm/unittests/Analysis/LazyCallGraphTest.cpp +++ b/llvm/unittests/Analysis/LazyCallGraphTest.cpp @@ -128,29 +128,29 @@ TEST(LazyCallGraphTest, BasicGraphFormation) { // the IR, and everything in our module is an entry node, so just directly // build variables for each node. auto I = CG.begin(); - LazyCallGraph::Node &A1 = *I++; + LazyCallGraph::Node &A1 = (I++)->getNode(CG); EXPECT_EQ("a1", A1.getFunction().getName()); - LazyCallGraph::Node &A2 = *I++; + LazyCallGraph::Node &A2 = (I++)->getNode(CG); EXPECT_EQ("a2", A2.getFunction().getName()); - LazyCallGraph::Node &A3 = *I++; + LazyCallGraph::Node &A3 = (I++)->getNode(CG); EXPECT_EQ("a3", A3.getFunction().getName()); - LazyCallGraph::Node &B1 = *I++; + LazyCallGraph::Node &B1 = (I++)->getNode(CG); EXPECT_EQ("b1", B1.getFunction().getName()); - LazyCallGraph::Node &B2 = *I++; + LazyCallGraph::Node &B2 = (I++)->getNode(CG); EXPECT_EQ("b2", B2.getFunction().getName()); - LazyCallGraph::Node &B3 = *I++; + LazyCallGraph::Node &B3 = (I++)->getNode(CG); EXPECT_EQ("b3", B3.getFunction().getName()); - LazyCallGraph::Node &C1 = *I++; + LazyCallGraph::Node &C1 = (I++)->getNode(CG); EXPECT_EQ("c1", C1.getFunction().getName()); - LazyCallGraph::Node &C2 = *I++; + LazyCallGraph::Node &C2 = (I++)->getNode(CG); EXPECT_EQ("c2", C2.getFunction().getName()); - LazyCallGraph::Node &C3 = *I++; + LazyCallGraph::Node &C3 = (I++)->getNode(CG); EXPECT_EQ("c3", C3.getFunction().getName()); - LazyCallGraph::Node &D1 = *I++; + LazyCallGraph::Node &D1 = (I++)->getNode(CG); EXPECT_EQ("d1", D1.getFunction().getName()); - LazyCallGraph::Node &D2 = *I++; + LazyCallGraph::Node &D2 = (I++)->getNode(CG); EXPECT_EQ("d2", D2.getFunction().getName()); - LazyCallGraph::Node &D3 = *I++; + LazyCallGraph::Node &D3 = (I++)->getNode(CG); EXPECT_EQ("d3", D3.getFunction().getName()); EXPECT_EQ(CG.end(), I); @@ -158,8 +158,8 @@ TEST(LazyCallGraphTest, BasicGraphFormation) { // independent of order. std::vector<std::string> Nodes; - for (LazyCallGraph::Node &N : A1) - Nodes.push_back(N.getFunction().getName()); + for (LazyCallGraph::Edge &E : A1) + Nodes.push_back(E.getFunction().getName()); std::sort(Nodes.begin(), Nodes.end()); EXPECT_EQ("a2", Nodes[0]); EXPECT_EQ("b2", Nodes[1]); @@ -171,8 +171,8 @@ TEST(LazyCallGraphTest, BasicGraphFormation) { EXPECT_EQ(A3.end(), std::next(A3.begin())); EXPECT_EQ("a1", A3.begin()->getFunction().getName()); - for (LazyCallGraph::Node &N : B1) - Nodes.push_back(N.getFunction().getName()); + for (LazyCallGraph::Edge &E : B1) + Nodes.push_back(E.getFunction().getName()); std::sort(Nodes.begin(), Nodes.end()); EXPECT_EQ("b2", Nodes[0]); EXPECT_EQ("d3", Nodes[1]); @@ -183,8 +183,8 @@ TEST(LazyCallGraphTest, BasicGraphFormation) { EXPECT_EQ(B3.end(), std::next(B3.begin())); EXPECT_EQ("b1", B3.begin()->getFunction().getName()); - for (LazyCallGraph::Node &N : C1) - Nodes.push_back(N.getFunction().getName()); + for (LazyCallGraph::Edge &E : C1) + Nodes.push_back(E.getFunction().getName()); std::sort(Nodes.begin(), Nodes.end()); EXPECT_EQ("c2", Nodes[0]); EXPECT_EQ("d2", Nodes[1]); @@ -298,23 +298,23 @@ TEST(LazyCallGraphTest, BasicGraphMutation) { EXPECT_EQ(2, std::distance(A.begin(), A.end())); EXPECT_EQ(0, std::distance(B.begin(), B.end())); - CG.insertEdge(B, lookupFunction(*M, "c")); + CG.insertEdge(B, lookupFunction(*M, "c"), LazyCallGraph::Edge::Call); EXPECT_EQ(1, std::distance(B.begin(), B.end())); - LazyCallGraph::Node &C = *B.begin(); + LazyCallGraph::Node &C = B.begin()->getNode(CG); EXPECT_EQ(0, std::distance(C.begin(), C.end())); - CG.insertEdge(C, B.getFunction()); + CG.insertEdge(C, B.getFunction(), LazyCallGraph::Edge::Call); EXPECT_EQ(1, std::distance(C.begin(), C.end())); - EXPECT_EQ(&B, &*C.begin()); + EXPECT_EQ(&B, C.begin()->getNode()); - CG.insertEdge(C, C.getFunction()); + CG.insertEdge(C, C.getFunction(), LazyCallGraph::Edge::Call); EXPECT_EQ(2, std::distance(C.begin(), C.end())); - EXPECT_EQ(&B, &*C.begin()); - EXPECT_EQ(&C, &*std::next(C.begin())); + EXPECT_EQ(&B, C.begin()->getNode()); + EXPECT_EQ(&C, std::next(C.begin())->getNode()); CG.removeEdge(C, B.getFunction()); EXPECT_EQ(1, std::distance(C.begin(), C.end())); - EXPECT_EQ(&C, &*C.begin()); + EXPECT_EQ(&C, C.begin()->getNode()); CG.removeEdge(C, C.getFunction()); EXPECT_EQ(0, std::distance(C.begin(), C.end())); @@ -417,7 +417,7 @@ TEST(LazyCallGraphTest, OutgoingSCCEdgeInsertion) { EXPECT_TRUE(DC.isDescendantOf(CC)); EXPECT_EQ(2, std::distance(A.begin(), A.end())); - AC.insertOutgoingEdge(A, D); + AC.insertOutgoingEdge(A, D, LazyCallGraph::Edge::Call); EXPECT_EQ(3, std::distance(A.begin(), A.end())); EXPECT_TRUE(AC.isParentOf(DC)); EXPECT_EQ(&AC, CG.lookupSCC(A)); @@ -489,7 +489,7 @@ TEST(LazyCallGraphTest, IncomingSCCEdgeInsertion) { // a1 | // / \ | // a3--a2 | - CC.insertIncomingEdge(D2, C2); + CC.insertIncomingEdge(D2, C2, LazyCallGraph::Edge::Call); // Make sure we connected the nodes. EXPECT_EQ(2, std::distance(D2.begin(), D2.end())); @@ -551,7 +551,7 @@ TEST(LazyCallGraphTest, IncomingSCCEdgeInsertionMidTraversal) { ASSERT_EQ(&DC, CG.lookupSCC(D3)); ASSERT_EQ(1, std::distance(D2.begin(), D2.end())); - CC.insertIncomingEdge(D2, C2); + 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. @@ -646,14 +646,14 @@ TEST(LazyCallGraphTest, IntraSCCEdgeInsertion) { EXPECT_EQ(&SCC, CG1.lookupSCC(C)); // Insert an edge from 'a' to 'c'. Nothing changes about the SCCs. - SCC.insertIntraSCCEdge(A, C); + 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)); // Insert a self edge from 'a' back to 'a'. - SCC.insertIntraSCCEdge(A, 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)); |
