Index: llvm/trunk/include/llvm/Analysis/LazyCallGraph.h =================================================================== --- llvm/trunk/include/llvm/Analysis/LazyCallGraph.h +++ llvm/trunk/include/llvm/Analysis/LazyCallGraph.h @@ -106,6 +106,7 @@ class LazyCallGraph { public: class Node; + class EdgeSequence; class SCC; class RefSCC; class edge_iterator; @@ -121,16 +122,6 @@ /// 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 @@ -141,7 +132,6 @@ 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. @@ -158,197 +148,251 @@ /// This requires that the edge is not null. bool isCall() const; - /// Get the function referenced by this edge. + /// Get the call graph node 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; + /// This requires that the edge is not null. + Node &getNode() const; - /// Get the call graph node referenced by this edge if one exists. + /// Get the function referenced by this edge. /// - /// 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); + /// This requires that the edge is not null. + Function &getFunction() const; private: - friend class LazyCallGraph::Node; + friend class LazyCallGraph::EdgeSequence; friend class LazyCallGraph::RefSCC; - PointerIntPair, 1, Kind> Value; + PointerIntPair Value; void setKind(Kind K) { Value.setInt(K); } }; - typedef SmallVector EdgeVectorT; - typedef SmallVectorImpl EdgeVectorImplT; - - /// A node in the call graph. + /// The edge sequence object. /// - /// This represents a single node. It's primary roles are to cache the list of - /// callees, de-duplicate and provide fast testing of whether a function is - /// a callee, and facilitate iteration of child nodes in the graph. - class Node { + /// This typically exists entirely within the node but is exposed as + /// a separate type because a node doesn't initially have edges. An explicit + /// population step is required to produce this sequence at first and it is + /// then cached in the node. It is also used to represent edges entering the + /// graph from outside the module to model the graph's roots. + /// + /// The sequence itself both iterable and indexable. The indexes remain + /// stable even as the sequence mutates (including removal). + class EdgeSequence { friend class LazyCallGraph; - friend class LazyCallGraph::SCC; + friend class LazyCallGraph::Node; friend class LazyCallGraph::RefSCC; - LazyCallGraph *G; - Function &F; + typedef SmallVector VectorT; + typedef SmallVectorImpl VectorImplT; - // We provide for the DFS numbering and Tarjan walk lowlink numbers to be - // 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; + public: + /// An iterator used for the edges to both entry nodes and child nodes. + class iterator + : public iterator_adaptor_base { + friend class LazyCallGraph; + friend class LazyCallGraph::Node; + + VectorImplT::iterator E; + + // Build the iterator for a specific position in the edge list. + iterator(VectorImplT::iterator BaseI, VectorImplT::iterator E) + : iterator_adaptor_base(BaseI), E(E) { + while (I != E && !*I) + ++I; + } - mutable EdgeVectorT Edges; - DenseMap EdgeIndexMap; + public: + iterator() {} - /// Basic constructor implements the scanning of F into Edges and - /// EdgeIndexMap. - Node(LazyCallGraph &G, Function &F); + using iterator_adaptor_base::operator++; + iterator &operator++() { + do { + ++I; + } while (I != E && !*I); + return *this; + } + }; - /// Internal helper to insert an edge to a function. - void insertEdgeInternal(Function &ChildF, Edge::Kind EK); + /// An iterator over specifically call edges. + /// + /// This has the same iteration properties as the \c iterator, but + /// restricts itself to edges which represent actual calls. + class call_iterator + : public iterator_adaptor_base { + friend class LazyCallGraph; + friend class LazyCallGraph::Node; + + VectorImplT::iterator E; + + /// Advance the iterator to the next valid, call edge. + void advanceToNextEdge() { + while (I != E && (!*I || !I->isCall())) + ++I; + } - /// Internal helper to insert an edge to a node. - void insertEdgeInternal(Node &ChildN, Edge::Kind EK); + // Build the iterator for a specific position in the edge list. + call_iterator(VectorImplT::iterator BaseI, VectorImplT::iterator E) + : iterator_adaptor_base(BaseI), E(E) { + advanceToNextEdge(); + } - /// Internal helper to change an edge kind. - void setEdgeKind(Function &ChildF, Edge::Kind EK); + public: + call_iterator() {} - /// Internal helper to remove the edge to the given function. - void removeEdgeInternal(Function &ChildF); + using iterator_adaptor_base::operator++; + call_iterator &operator++() { + ++I; + advanceToNextEdge(); + return *this; + } + }; - void clear() { - Edges.clear(); - EdgeIndexMap.clear(); - } + iterator begin() { return iterator(Edges.begin(), Edges.end()); } + iterator end() { return iterator(Edges.end(), Edges.end()); } - /// Print the name of this node's function. - friend raw_ostream &operator<<(raw_ostream &OS, const Node &N) { - return OS << N.F.getName(); + Edge &operator[](int i) { return Edges[i]; } + Edge &operator[](Node &N) { + assert(EdgeIndexMap.find(&N) != EdgeIndexMap.end() && "No such edge!"); + return Edges[EdgeIndexMap.find(&N)->second]; + } + Edge *lookup(Node &N) { + auto EI = EdgeIndexMap.find(&N); + return EI != EdgeIndexMap.end() ? &Edges[EI->second] : nullptr; } - /// Dump the name of this node's function to stderr. - void dump() const; + call_iterator call_begin() { + return call_iterator(Edges.begin(), Edges.end()); + } + call_iterator call_end() { return call_iterator(Edges.end(), Edges.end()); } - public: - LazyCallGraph &getGraph() const { return *G; } + iterator_range calls() { + return make_range(call_begin(), call_end()); + } - Function &getFunction() const { return F; } + bool empty() { + for (auto &E : Edges) + if (E) + return false; - edge_iterator begin() const { - return edge_iterator(Edges.begin(), Edges.end()); + return true; } - 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()]; } + private: + VectorT Edges; + DenseMap EdgeIndexMap; - const Edge *lookup(Function &F) const { - auto EI = EdgeIndexMap.find(&F); - return EI != EdgeIndexMap.end() ? &Edges[EI->second] : nullptr; - } + EdgeSequence() = default; - 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()); - } + /// Internal helper to insert an edge to a node. + void insertEdgeInternal(Node &ChildN, Edge::Kind EK); - iterator_range calls() const { - return make_range(call_begin(), call_end()); - } + /// Internal helper to change an edge kind. + void setEdgeKind(Node &ChildN, Edge::Kind EK); - /// Equality is defined as address equality. - bool operator==(const Node &N) const { return this == &N; } - bool operator!=(const Node &N) const { return !operator==(N); } + /// Internal helper to remove the edge to the given function. + bool removeEdgeInternal(Node &ChildN); + + /// Internal helper to replace an edge key with a new one. + /// + /// This should be used when the function for a particular node in the + /// graph gets replaced and we are updating all of the edges to that node + /// to use the new function as the key. + void replaceEdgeKey(Function &OldTarget, Function &NewTarget); }; - /// A lazy iterator used for both the entry nodes and child nodes. + /// A node in the call graph. + /// + /// This represents a single node. It's primary roles are to cache the list of + /// callees, de-duplicate and provide fast testing of whether a function is + /// a callee, and facilitate iteration of child nodes in the graph. /// - /// When this iterator is dereferenced, if not yet available, a function will - /// 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 edge_iterator - : public iterator_adaptor_base { + /// The node works much like an optional in order to lazily populate the + /// edges of each node. Until populated, there are no edges. Once populated, + /// you can access the edges by dereferencing the node or using the `->` + /// operator as if the node was an `Optional`. + class Node { friend class LazyCallGraph; - friend class LazyCallGraph::Node; + friend class LazyCallGraph::RefSCC; - EdgeVectorImplT::iterator E; + public: + LazyCallGraph &getGraph() const { return *G; } - // 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; - } + Function &getFunction() const { return *F; } - public: - edge_iterator() {} + StringRef getName() const { return F->getName(); } - using iterator_adaptor_base::operator++; - edge_iterator &operator++() { - do { - ++I; - } while (I != E && !*I); - return *this; - } - }; + /// Equality is defined as address equality. + bool operator==(const Node &N) const { return this == &N; } + bool operator!=(const Node &N) const { return !operator==(N); } - /// 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 { - friend class LazyCallGraph; - friend class LazyCallGraph::Node; + /// Tests whether the node has been populated with edges. + operator bool() const { return Edges.hasValue(); } - EdgeVectorImplT::iterator E; + // We allow accessing the edges by dereferencing or using the arrow + // operator, essentially wrapping the internal optional. + EdgeSequence &operator*() const { + // Rip const off because the node itself isn't changing here. + return const_cast(*Edges); + } + EdgeSequence *operator->() const { return &**this; } + + /// Populate the edges of this node if necessary. + /// + /// The first time this is called it will populate the edges for this node + /// in the graph. It does this by scanning the underlying function, so once + /// this is done, any changes to that function must be explicitly reflected + /// in updates to the graph. + /// + /// \returns the populated \c EdgeSequence to simplify walking it. + /// + /// This will not update or re-scan anything if called repeatedly. Instead, + /// the edge sequence is cached and returned immediately on subsequent + /// calls. + EdgeSequence &populate() { + if (Edges) + return *Edges; - /// Advance the iterator to the next valid, call edge. - void advanceToNextEdge() { - while (I != E && (!*I || !I->isCall())) - ++I; + return populateSlow(); } - // 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(); - } + private: + LazyCallGraph *G; + Function *F; - public: - call_edge_iterator() {} + // We provide for the DFS numbering and Tarjan walk lowlink numbers to be + // 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; - using iterator_adaptor_base::operator++; - call_edge_iterator &operator++() { - ++I; - advanceToNextEdge(); - return *this; + Optional Edges; + + /// Basic constructor implements the scanning of F into Edges and + /// EdgeIndexMap. + Node(LazyCallGraph &G, Function &F) + : G(&G), F(&F), DFSNumber(0), LowLink(0) {} + + /// Implementation of the scan when populating. + EdgeSequence &populateSlow(); + + /// Internal helper to directly replace the function with a new one. + /// + /// This is used to facilitate tranfsormations which need to replace the + /// formal Function object but directly move the body and users from one to + /// the other. + void replaceFunction(Function &NewF); + + void clear() { Edges.reset(); } + + /// Print the name of this node's function. + friend raw_ostream &operator<<(raw_ostream &OS, const Node &N) { + return OS << N.F->getName(); } + + /// Dump the name of this node's function to stderr. + void dump() const; }; /// An SCC of the call graph. @@ -789,6 +833,17 @@ /// already existing edges. void insertTrivialRefEdge(Node &SourceN, Node &TargetN); + /// Directly replace a node's function with a new function. + /// + /// This should be used when moving the body and users of a function to + /// a new formal function object but not otherwise changing the call graph + /// structure in any way. + /// + /// It requires that the old function in the provided node have zero uses + /// and the new function must have calls and references to it establishing + /// an equivalent graph. + void replaceNodeFunction(Node &N, Function &NewF); + ///@} }; @@ -852,12 +907,8 @@ LazyCallGraph(LazyCallGraph &&G); LazyCallGraph &operator=(LazyCallGraph &&RHS); - edge_iterator begin() { - return edge_iterator(EntryEdges.begin(), EntryEdges.end()); - } - edge_iterator end() { - return edge_iterator(EntryEdges.end(), EntryEdges.end()); - } + EdgeSequence::iterator begin() { return EntryEdges.begin(); } + EdgeSequence::iterator end() { return EntryEdges.end(); } void buildRefSCCs(); @@ -921,19 +972,19 @@ /// below. /// Update the call graph after inserting a new edge. - void insertEdge(Node &Caller, Function &Callee, Edge::Kind EK); + void insertEdge(Node &SourceN, Node &TargetN, Edge::Kind EK); /// Update the call graph after inserting a new edge. - void insertEdge(Function &Caller, Function &Callee, Edge::Kind EK) { - return insertEdge(get(Caller), Callee, EK); + void insertEdge(Function &Source, Function &Target, Edge::Kind EK) { + return insertEdge(get(Source), get(Target), EK); } /// Update the call graph after deleting an edge. - void removeEdge(Node &Caller, Function &Callee); + void removeEdge(Node &SourceN, Node &TargetN); /// Update the call graph after deleting an edge. - void removeEdge(Function &Caller, Function &Callee) { - return removeEdge(get(Caller), Callee); + void removeEdge(Function &Source, Function &Target) { + return removeEdge(get(Source), get(Target)); } ///@} @@ -1014,14 +1065,11 @@ /// Maps function->node for fast lookup. DenseMap NodeMap; - /// The entry nodes to the graph. + /// The entry edges into the graph. /// - /// These nodes are reachable through "external" means. Put another way, they + /// These edges are from "external" sources. Put another way, they /// escape at the module scope. - EdgeVectorT EntryEdges; - - /// Map of the entry nodes in the graph to their indices in \c EntryEdges. - DenseMap EntryIndexMap; + EdgeSequence EntryEdges; /// Allocator that holds all the call graph SCCs. SpecificBumpPtrAllocator SCCBPA; @@ -1107,12 +1155,9 @@ }; 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 LazyCallGraph::Edge::operator bool() const { return Value.getPointer(); } inline LazyCallGraph::Edge::Kind LazyCallGraph::Edge::getKind() const { assert(*this && "Queried a null edge!"); @@ -1124,51 +1169,32 @@ return getKind() == Call; } -inline Function &LazyCallGraph::Edge::getFunction() const { +inline LazyCallGraph::Node &LazyCallGraph::Edge::getNode() const { assert(*this && "Queried a null edge!"); - auto P = Value.getPointer(); - if (auto *F = P.dyn_cast()) - return *F; - - return P.get()->getFunction(); + return *Value.getPointer(); } -inline LazyCallGraph::Node *LazyCallGraph::Edge::getNode() const { - assert(*this && "Queried a null edge!"); - auto P = Value.getPointer(); - if (auto *N = P.dyn_cast()) - return N; - - return nullptr; -} - -inline LazyCallGraph::Node &LazyCallGraph::Edge::getNode(LazyCallGraph &G) { +inline Function &LazyCallGraph::Edge::getFunction() const { assert(*this && "Queried a null edge!"); - auto P = Value.getPointer(); - if (auto *N = P.dyn_cast()) - return *N; - - Node &N = G.get(*P.get()); - Value.setPointer(&N); - return N; + return getNode().getFunction(); } // Provide GraphTraits specializations for call graphs. template <> struct GraphTraits { typedef LazyCallGraph::Node *NodeRef; - typedef LazyCallGraph::edge_iterator ChildIteratorType; + typedef LazyCallGraph::EdgeSequence::iterator ChildIteratorType; static NodeRef getEntryNode(NodeRef N) { return N; } - static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } - static ChildIteratorType child_end(NodeRef N) { return N->end(); } + static ChildIteratorType child_begin(NodeRef N) { return (*N)->begin(); } + static ChildIteratorType child_end(NodeRef N) { return (*N)->end(); } }; template <> struct GraphTraits { typedef LazyCallGraph::Node *NodeRef; - typedef LazyCallGraph::edge_iterator ChildIteratorType; + typedef LazyCallGraph::EdgeSequence::iterator ChildIteratorType; static NodeRef getEntryNode(NodeRef N) { return N; } - static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } - static ChildIteratorType child_end(NodeRef N) { return N->end(); } + static ChildIteratorType child_begin(NodeRef N) { return (*N)->begin(); } + static ChildIteratorType child_end(NodeRef N) { return (*N)->end(); } }; /// An analysis pass which computes the call graph for a module. Index: llvm/trunk/lib/Analysis/CGSCCPassManager.cpp =================================================================== --- llvm/trunk/lib/Analysis/CGSCCPassManager.cpp +++ llvm/trunk/lib/Analysis/CGSCCPassManager.cpp @@ -274,9 +274,9 @@ // demoted edges. SmallVector Worklist; SmallPtrSet Visited; - SmallPtrSet RetainedEdges; - SmallSetVector PromotedRefTargets; - SmallSetVector DemotedCallTargets; + SmallPtrSet RetainedEdges; + SmallSetVector PromotedRefTargets; + SmallSetVector DemotedCallTargets; // First walk the function and handle all called functions. We do this first // because if there is a single call edge, whether there are ref edges is @@ -285,7 +285,8 @@ if (auto CS = CallSite(&I)) if (Function *Callee = CS.getCalledFunction()) if (Visited.insert(Callee).second && !Callee->isDeclaration()) { - const Edge *E = N.lookup(*Callee); + Node &CalleeN = *G.lookup(*Callee); + Edge *E = N->lookup(CalleeN); // FIXME: We should really handle adding new calls. While it will // make downstream usage more complex, there is no fundamental // limitation and it will allow passes within the CGSCC to be a bit @@ -294,9 +295,9 @@ assert(E && "No function transformations should introduce *new* " "call edges! Any new calls should be modeled as " "promoted existing ref edges!"); - RetainedEdges.insert(Callee); + RetainedEdges.insert(&CalleeN); if (!E->isCall()) - PromotedRefTargets.insert(Callee); + PromotedRefTargets.insert(&CalleeN); } // Now walk all references. @@ -307,24 +308,25 @@ Worklist.push_back(C); LazyCallGraph::visitReferences(Worklist, Visited, [&](Function &Referee) { - const Edge *E = N.lookup(Referee); + Node &RefereeN = *G.lookup(Referee); + Edge *E = N->lookup(RefereeN); // FIXME: Similarly to new calls, we also currently preclude // introducing new references. See above for details. assert(E && "No function transformations should introduce *new* ref " "edges! Any new ref edges would require IPO which " "function passes aren't allowed to do!"); - RetainedEdges.insert(&Referee); + RetainedEdges.insert(&RefereeN); if (E->isCall()) - DemotedCallTargets.insert(&Referee); + DemotedCallTargets.insert(&RefereeN); }); // First remove all of the edges that are no longer present in this function. // We have to build a list of dead targets first and then remove them as the // data structures will all be invalidated by removing them. SmallVector, 4> DeadTargets; - for (Edge &E : N) - if (!RetainedEdges.count(&E.getFunction())) - DeadTargets.push_back({E.getNode(), E.getKind()}); + for (Edge &E : *N) + if (!RetainedEdges.count(&E.getNode())) + DeadTargets.push_back({&E.getNode(), E.getKind()}); for (auto DeadTarget : DeadTargets) { Node &TargetN = *DeadTarget.getPointer(); bool IsCall = DeadTarget.getInt() == Edge::Call; @@ -398,9 +400,8 @@ // Next demote all the call edges that are now ref edges. This helps make // the SCCs small which should minimize the work below as we don't want to // form cycles that this would break. - for (Function *RefTarget : DemotedCallTargets) { - Node &TargetN = *G.lookup(*RefTarget); - SCC &TargetC = *G.lookupSCC(TargetN); + for (Node *RefTarget : DemotedCallTargets) { + SCC &TargetC = *G.lookupSCC(*RefTarget); RefSCC &TargetRC = TargetC.getOuterRefSCC(); // The easy case is when the target RefSCC is not this RefSCC. This is @@ -408,10 +409,10 @@ if (&TargetRC != RC) { assert(RC->isAncestorOf(TargetRC) && "Cannot potentially form RefSCC cycles here!"); - RC->switchOutgoingEdgeToRef(N, TargetN); + RC->switchOutgoingEdgeToRef(N, *RefTarget); if (DebugLogging) dbgs() << "Switch outgoing call edge to a ref edge from '" << N - << "' to '" << TargetN << "'\n"; + << "' to '" << *RefTarget << "'\n"; continue; } @@ -419,7 +420,7 @@ // some SCCs. if (C != &TargetC) { // For separate SCCs this is trivial. - RC->switchTrivialInternalEdgeToRef(N, TargetN); + RC->switchTrivialInternalEdgeToRef(N, *RefTarget); continue; } @@ -431,14 +432,13 @@ // structure is changed. AM.invalidate(*C, PreservedAnalyses::none()); // Now update the call graph. - C = incorporateNewSCCRange(RC->switchInternalEdgeToRef(N, TargetN), G, - N, C, AM, UR, DebugLogging); + C = incorporateNewSCCRange(RC->switchInternalEdgeToRef(N, *RefTarget), G, N, + C, AM, UR, DebugLogging); } // Now promote ref edges into call edges. - for (Function *CallTarget : PromotedRefTargets) { - Node &TargetN = *G.lookup(*CallTarget); - SCC &TargetC = *G.lookupSCC(TargetN); + for (Node *CallTarget : PromotedRefTargets) { + SCC &TargetC = *G.lookupSCC(*CallTarget); RefSCC &TargetRC = TargetC.getOuterRefSCC(); // The easy case is when the target RefSCC is not this RefSCC. This is @@ -446,22 +446,22 @@ if (&TargetRC != RC) { assert(RC->isAncestorOf(TargetRC) && "Cannot potentially form RefSCC cycles here!"); - RC->switchOutgoingEdgeToCall(N, TargetN); + RC->switchOutgoingEdgeToCall(N, *CallTarget); if (DebugLogging) dbgs() << "Switch outgoing ref edge to a call edge from '" << N - << "' to '" << TargetN << "'\n"; + << "' to '" << *CallTarget << "'\n"; continue; } if (DebugLogging) dbgs() << "Switch an internal ref edge to a call edge from '" << N - << "' to '" << TargetN << "'\n"; + << "' to '" << *CallTarget << "'\n"; // Otherwise we are switching an internal ref edge to a call edge. This // may merge away some SCCs, and we add those to the UpdateResult. We also // need to make sure to update the worklist in the event SCCs have moved // before the current one in the post-order sequence. auto InitialSCCIndex = RC->find(*C) - RC->begin(); - auto InvalidatedSCCs = RC->switchInternalEdgeToCall(N, TargetN); + auto InvalidatedSCCs = RC->switchInternalEdgeToCall(N, *CallTarget); if (!InvalidatedSCCs.empty()) { C = &TargetC; assert(G.lookupSCC(N) == C && "Failed to update current SCC!"); Index: llvm/trunk/lib/Analysis/LazyCallGraph.cpp =================================================================== --- llvm/trunk/lib/Analysis/LazyCallGraph.cpp +++ llvm/trunk/lib/Analysis/LazyCallGraph.cpp @@ -24,21 +24,44 @@ #define DEBUG_TYPE "lcg" +void LazyCallGraph::EdgeSequence::insertEdgeInternal(Node &TargetN, + Edge::Kind EK) { + EdgeIndexMap.insert({&TargetN, Edges.size()}); + Edges.emplace_back(TargetN, EK); +} + +void LazyCallGraph::EdgeSequence::setEdgeKind(Node &TargetN, Edge::Kind EK) { + Edges[EdgeIndexMap.find(&TargetN)->second].setKind(EK); +} + +bool LazyCallGraph::EdgeSequence::removeEdgeInternal(Node &TargetN) { + auto IndexMapI = EdgeIndexMap.find(&TargetN); + if (IndexMapI == EdgeIndexMap.end()) + return false; + + Edges[IndexMapI->second] = Edge(); + EdgeIndexMap.erase(IndexMapI); + return true; +} + static void addEdge(SmallVectorImpl &Edges, - DenseMap &EdgeIndexMap, Function &F, - LazyCallGraph::Edge::Kind EK) { - if (!EdgeIndexMap.insert({&F, Edges.size()}).second) + DenseMap &EdgeIndexMap, + LazyCallGraph::Node &N, LazyCallGraph::Edge::Kind EK) { + if (!EdgeIndexMap.insert({&N, Edges.size()}).second) return; - DEBUG(dbgs() << " Added callable function: " << F.getName() << "\n"); - Edges.emplace_back(LazyCallGraph::Edge(F, EK)); + DEBUG(dbgs() << " Added callable function: " << N.getName() << "\n"); + Edges.emplace_back(LazyCallGraph::Edge(N, EK)); } -LazyCallGraph::Node::Node(LazyCallGraph &G, Function &F) - : G(&G), F(F), DFSNumber(0), LowLink(0) { - DEBUG(dbgs() << " Adding functions called by '" << F.getName() +LazyCallGraph::EdgeSequence &LazyCallGraph::Node::populateSlow() { + assert(!Edges && "Must not have already populated the edges for this node!"); + + DEBUG(dbgs() << " Adding functions called by '" << getName() << "' to the graph.\n"); + Edges = EdgeSequence(); + SmallVector Worklist; SmallPtrSet Callees; SmallPtrSet Visited; @@ -59,14 +82,15 @@ // 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. - for (BasicBlock &BB : F) + for (BasicBlock &BB : *F) for (Instruction &I : BB) { if (auto CS = CallSite(&I)) if (Function *Callee = CS.getCalledFunction()) if (!Callee->isDeclaration()) if (Callees.insert(Callee).second) { Visited.insert(Callee); - addEdge(Edges, EdgeIndexMap, *Callee, LazyCallGraph::Edge::Call); + addEdge(Edges->Edges, Edges->EdgeIndexMap, G->get(*Callee), + LazyCallGraph::Edge::Call); } for (Value *Op : I.operand_values()) @@ -79,34 +103,16 @@ // function containing) operands to all of the instructions in the function. // Process them (recursively) collecting every function found. visitReferences(Worklist, Visited, [&](Function &F) { - addEdge(Edges, EdgeIndexMap, F, LazyCallGraph::Edge::Ref); + addEdge(Edges->Edges, Edges->EdgeIndexMap, G->get(F), + LazyCallGraph::Edge::Ref); }); -} - -void LazyCallGraph::Node::insertEdgeInternal(Function &Target, Edge::Kind EK) { - if (Node *N = G->lookup(Target)) - return insertEdgeInternal(*N, EK); - EdgeIndexMap.insert({&Target, Edges.size()}); - Edges.emplace_back(Target, EK); -} - -void LazyCallGraph::Node::insertEdgeInternal(Node &TargetN, Edge::Kind EK) { - EdgeIndexMap.insert({&TargetN.getFunction(), Edges.size()}); - Edges.emplace_back(TargetN, EK); + return *Edges; } -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() && - "Target not in the edge set for this caller?"); - - Edges[IndexMapI->second] = Edge(); - EdgeIndexMap.erase(IndexMapI); +void LazyCallGraph::Node::replaceFunction(Function &NewF) { + assert(F != &NewF && "Must not replace a function with itself!"); + F = &NewF; } #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) @@ -119,12 +125,11 @@ DEBUG(dbgs() << "Building CG for module: " << M.getModuleIdentifier() << "\n"); for (Function &F : M) - if (!F.isDeclaration() && !F.hasLocalLinkage()) - 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); - } + if (!F.isDeclaration() && !F.hasLocalLinkage()) { + DEBUG(dbgs() << " Adding '" << F.getName() + << "' to entry set of the graph.\n"); + addEdge(EntryEdges.Edges, EntryEdges.EdgeIndexMap, get(F), Edge::Ref); + } // Now add entry nodes for functions reachable via initializers to globals. SmallVector Worklist; @@ -137,14 +142,14 @@ DEBUG(dbgs() << " Adding functions referenced by global initializers to the " "entry set.\n"); visitReferences(Worklist, Visited, [&](Function &F) { - addEdge(EntryEdges, EntryIndexMap, F, LazyCallGraph::Edge::Ref); + addEdge(EntryEdges.Edges, EntryEdges.EdgeIndexMap, get(F), + LazyCallGraph::Edge::Ref); }); } 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)), + EntryEdges(std::move(G.EntryEdges)), SCCBPA(std::move(G.SCCBPA)), SCCMap(std::move(G.SCCMap)), LeafRefSCCs(std::move(G.LeafRefSCCs)) { updateGraphPtrs(); } @@ -153,7 +158,6 @@ 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); LeafRefSCCs = std::move(G.LeafRefSCCs); @@ -180,8 +184,8 @@ "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!"); + for (Edge &E : **N) + assert(E.getNode() && "Can't have an unpopulated node!"); } } #endif @@ -191,10 +195,9 @@ return false; for (Node &N : *this) - for (Edge &E : N.calls()) - if (Node *CalleeN = E.getNode()) - if (OuterRefSCC->G->lookupSCC(*CalleeN) == &C) - return true; + for (Edge &E : N->calls()) + if (OuterRefSCC->G->lookupSCC(E.getNode()) == &C) + return true; // No edges found. return false; @@ -214,11 +217,8 @@ do { const SCC &C = *Worklist.pop_back_val(); for (Node &N : C) - for (Edge &E : N.calls()) { - Node *CalleeN = E.getNode(); - if (!CalleeN) - continue; - SCC *CalleeC = G.lookupSCC(*CalleeN); + for (Edge &E : N->calls()) { + SCC *CalleeC = G.lookupSCC(E.getNode()); if (!CalleeC) continue; @@ -277,10 +277,10 @@ for (int i = 0, Size = SCCs.size(); i < Size; ++i) { SCC &SourceSCC = *SCCs[i]; for (Node &N : SourceSCC) - for (Edge &E : N) { + for (Edge &E : *N) { if (!E.isCall()) continue; - SCC &TargetSCC = *G->lookupSCC(*E.getNode()); + SCC &TargetSCC = *G->lookupSCC(E.getNode()); if (&TargetSCC.getOuterRefSCC() == this) { assert(SCCIndices.find(&TargetSCC)->second <= i && "Edge between SCCs violates post-order relationship."); @@ -297,8 +297,8 @@ auto HasConnectingEdge = [&] { for (SCC &C : *ParentRC) for (Node &N : C) - for (Edge &E : N) - if (G->lookupRefSCC(*E.getNode()) == this) + for (Edge &E : *N) + if (G->lookupRefSCC(E.getNode()) == this) return true; return false; }; @@ -459,7 +459,7 @@ SmallVector LazyCallGraph::RefSCC::switchInternalEdgeToCall(Node &SourceN, Node &TargetN) { - assert(!SourceN[TargetN].isCall() && "Must start with a ref edge!"); + assert(!(*SourceN)[TargetN].isCall() && "Must start with a ref edge!"); SmallVector DeletedSCCs; #ifndef NDEBUG @@ -475,7 +475,7 @@ // 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); + SourceN->setEdgeKind(TargetN, Edge::Call); return DeletedSCCs; } @@ -488,7 +488,7 @@ int SourceIdx = SCCIndices[&SourceSCC]; int TargetIdx = SCCIndices[&TargetSCC]; if (TargetIdx < SourceIdx) { - SourceN.setEdgeKind(TargetN.getFunction(), Edge::Call); + SourceN->setEdgeKind(TargetN, Edge::Call); return DeletedSCCs; } @@ -502,11 +502,9 @@ 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()))) + for (Edge &E : N->calls()) + if (ConnectedSet.count(G->lookupSCC(E.getNode()))) return true; - } return false; }; @@ -533,11 +531,10 @@ 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!"); + for (Edge &E : *N) { if (!E.isCall()) continue; - SCC &EdgeC = *G->lookupSCC(*E.getNode()); + SCC &EdgeC = *G->lookupSCC(E.getNode()); if (&EdgeC.getOuterRefSCC() != this) // Not in this RefSCC... continue; @@ -563,7 +560,7 @@ // new cycles. We're done. if (MergeRange.begin() == MergeRange.end()) { // Now that the SCC structure is finalized, flip the kind to call. - SourceN.setEdgeKind(TargetN.getFunction(), Edge::Call); + SourceN->setEdgeKind(TargetN, Edge::Call); return DeletedSCCs; } @@ -598,7 +595,7 @@ SCCIndices[C] -= IndexOffset; // Now that the SCC structure is finalized, flip the kind to call. - SourceN.setEdgeKind(TargetN.getFunction(), Edge::Call); + SourceN->setEdgeKind(TargetN, Edge::Call); // And we're done! return DeletedSCCs; @@ -606,7 +603,7 @@ void LazyCallGraph::RefSCC::switchTrivialInternalEdgeToRef(Node &SourceN, Node &TargetN) { - assert(SourceN[TargetN].isCall() && "Must start with a call edge!"); + assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!"); #ifndef NDEBUG // In a debug build, verify the RefSCC is valid to start with and when this @@ -623,12 +620,12 @@ "Source and Target must be in separate SCCs for this to be trivial!"); // Set the edge kind. - SourceN.setEdgeKind(TargetN.getFunction(), Edge::Ref); + SourceN->setEdgeKind(TargetN, Edge::Ref); } iterator_range LazyCallGraph::RefSCC::switchInternalEdgeToRef(Node &SourceN, Node &TargetN) { - assert(SourceN[TargetN].isCall() && "Must start with a call edge!"); + assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!"); #ifndef NDEBUG // In a debug build, verify the RefSCC is valid to start with and when this @@ -648,7 +645,7 @@ "full CG update."); // Set the edge kind. - SourceN.setEdgeKind(TargetN.getFunction(), Edge::Ref); + SourceN->setEdgeKind(TargetN, Edge::Ref); // 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 @@ -663,7 +660,7 @@ // etc. SCC &OldSCC = TargetSCC; - SmallVector, 16> DFSStack; + SmallVector, 16> DFSStack; SmallVector PendingSCCStack; SmallVector NewSCCs; @@ -704,14 +701,14 @@ RootN->DFSNumber = RootN->LowLink = 1; int NextDFSNumber = 2; - DFSStack.push_back({RootN, RootN->call_begin()}); + DFSStack.push_back({RootN, (*RootN)->call_begin()}); do { Node *N; - call_edge_iterator I; + EdgeSequence::call_iterator I; std::tie(N, I) = DFSStack.pop_back_val(); - auto E = N->call_end(); + auto E = (*N)->call_end(); while (I != E) { - Node &ChildN = *I->getNode(); + Node &ChildN = I->getNode(); if (ChildN.DFSNumber == 0) { // We haven't yet visited this child, so descend, pushing the current // node onto the stack. @@ -721,8 +718,8 @@ "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(); + I = (*N)->call_begin(); + E = (*N)->call_end(); continue; } @@ -815,7 +812,7 @@ void LazyCallGraph::RefSCC::switchOutgoingEdgeToCall(Node &SourceN, Node &TargetN) { - assert(!SourceN[TargetN].isCall() && "Must start with a ref edge!"); + 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 && @@ -827,7 +824,7 @@ // 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); + SourceN->setEdgeKind(TargetN, Edge::Call); #ifndef NDEBUG // Check that the RefSCC is still valid. @@ -837,7 +834,7 @@ void LazyCallGraph::RefSCC::switchOutgoingEdgeToRef(Node &SourceN, Node &TargetN) { - assert(SourceN[TargetN].isCall() && "Must start with a call edge!"); + 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 && @@ -849,7 +846,7 @@ // 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); + SourceN->setEdgeKind(TargetN, Edge::Ref); #ifndef NDEBUG // Check that the RefSCC is still valid. @@ -862,7 +859,7 @@ 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); + SourceN->insertEdgeInternal(TargetN, Edge::Ref); #ifndef NDEBUG // Check that the RefSCC is still valid. @@ -873,7 +870,7 @@ void LazyCallGraph::RefSCC::insertOutgoingEdge(Node &SourceN, Node &TargetN, Edge::Kind EK) { // First insert it into the caller. - SourceN.insertEdgeInternal(TargetN, EK); + SourceN->insertEdgeInternal(TargetN, EK); assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC."); @@ -957,9 +954,8 @@ RefSCC &RC = *Worklist.pop_back_val(); for (SCC &C : RC) for (Node &N : C) - for (Edge &E : N) { - assert(E.getNode() && "Must have formed a node!"); - RefSCC &EdgeRC = *G->lookupRefSCC(*E.getNode()); + for (Edge &E : *N) { + RefSCC &EdgeRC = *G->lookupRefSCC(E.getNode()); if (G->getRefSCCIndex(EdgeRC) <= SourceIdx) // Not in the postorder sequence between source and target. continue; @@ -1009,10 +1005,8 @@ 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()); + for (Edge &E : *N) { + RefSCC &ChildRC = *G->lookupRefSCC(E.getNode()); if (MergeSet.count(&ChildRC)) continue; ChildRC.Parents.erase(RC); @@ -1048,7 +1042,7 @@ // 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); + SourceN->insertEdgeInternal(TargetN, Edge::Ref); // 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 @@ -1075,15 +1069,16 @@ #endif // First remove it from the node. - SourceN.removeEdgeInternal(TargetN.getFunction()); + bool Removed = SourceN->removeEdgeInternal(TargetN); + (void)Removed; + assert(Removed && "Target not in the edge set for this caller?"); bool HasOtherEdgeToChildRC = false; bool HasOtherChildRC = false; for (SCC *InnerC : SCCs) { for (Node &N : *InnerC) { - for (Edge &E : N) { - assert(E.getNode() && "Cannot have a missing node in a visited SCC!"); - RefSCC &OtherChildRC = *G->lookupRefSCC(*E.getNode()); + for (Edge &E : *N) { + RefSCC &OtherChildRC = *G->lookupRefSCC(E.getNode()); if (&OtherChildRC == &TargetRC) { HasOtherEdgeToChildRC = true; break; @@ -1122,7 +1117,7 @@ SmallVector LazyCallGraph::RefSCC::removeInternalRefEdge(Node &SourceN, Node &TargetN) { - assert(!SourceN[TargetN].isCall() && + assert(!(*SourceN)[TargetN].isCall() && "Cannot remove a call edge, it must first be made a ref edge"); #ifndef NDEBUG @@ -1133,7 +1128,9 @@ #endif // First remove the actual edge. - SourceN.removeEdgeInternal(TargetN.getFunction()); + bool Removed = SourceN->removeEdgeInternal(TargetN); + (void)Removed; + assert(Removed && "Target not in the edge set for this caller?"); // We return a list of the resulting *new* RefSCCs in post-order. SmallVector Result; @@ -1192,7 +1189,7 @@ PostOrderMapping[&N] = Number; }; - SmallVector, 4> DFSStack; + SmallVector, 4> DFSStack; SmallVector PendingRefSCCStack; do { assert(DFSStack.empty() && @@ -1211,18 +1208,18 @@ RootN->DFSNumber = RootN->LowLink = 1; int NextDFSNumber = 2; - DFSStack.push_back({RootN, RootN->begin()}); + DFSStack.push_back({RootN, (*RootN)->begin()}); do { Node *N; - edge_iterator I; + EdgeSequence::iterator I; std::tie(N, I) = DFSStack.pop_back_val(); - auto E = N->end(); + 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); + Node &ChildN = I->getNode(); 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 @@ -1232,8 +1229,8 @@ // Continue, resetting to the child node. ChildN.LowLink = ChildN.DFSNumber = NextDFSNumber++; N = &ChildN; - I = ChildN.begin(); - E = ChildN.end(); + I = ChildN->begin(); + E = ChildN->end(); continue; } if (ChildN.DFSNumber == -1) { @@ -1388,9 +1385,8 @@ #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()); + for (Edge &E : *N) { + RefSCC &ChildRC = *G->lookupRefSCC(E.getNode()); if (&ChildRC == this) continue; ChildRC.Parents.insert(this); @@ -1414,9 +1410,8 @@ for (RefSCC *ParentRC : OldParents) for (SCC &ParentC : *ParentRC) for (Node &ParentN : ParentC) - for (Edge &E : ParentN) { - assert(E.getNode() && "Cannot have a missing node in a visited SCC!"); - RefSCC &RC = *G->lookupRefSCC(*E.getNode()); + for (Edge &E : *ParentN) { + RefSCC &RC = *G->lookupRefSCC(E.getNode()); if (&RC != ParentRC) RC.Parents.insert(ParentRC); } @@ -1481,17 +1476,17 @@ #endif // NDEBUG // First insert it into the source or find the existing edge. - auto InsertResult = SourceN.EdgeIndexMap.insert( - {&TargetN.getFunction(), SourceN.Edges.size()}); + auto InsertResult = + SourceN->EdgeIndexMap.insert({&TargetN, SourceN->Edges.size()}); if (!InsertResult.second) { // Already an edge, just update it. - Edge &E = SourceN.Edges[InsertResult.first->second]; + Edge &E = SourceN->Edges[InsertResult.first->second]; if (E.isCall()) return; // Nothing to do! E.setKind(Edge::Call); } else { // Create the new edge. - SourceN.Edges.emplace_back(TargetN, Edge::Call); + SourceN->Edges.emplace_back(TargetN, Edge::Call); } // Now that we have the edge, handle the graph fallout. @@ -1514,31 +1509,64 @@ #endif // NDEBUG // First insert it into the source or find the existing edge. - auto InsertResult = SourceN.EdgeIndexMap.insert( - {&TargetN.getFunction(), SourceN.Edges.size()}); + auto InsertResult = + SourceN->EdgeIndexMap.insert({&TargetN, SourceN->Edges.size()}); if (!InsertResult.second) // Already an edge, we're done. return; // Create the new edge. - SourceN.Edges.emplace_back(TargetN, Edge::Ref); + SourceN->Edges.emplace_back(TargetN, Edge::Ref); // Now that we have the edge, handle the graph fallout. handleTrivialEdgeInsertion(SourceN, TargetN); } -void LazyCallGraph::insertEdge(Node &SourceN, Function &Target, Edge::Kind EK) { +void LazyCallGraph::RefSCC::replaceNodeFunction(Node &N, Function &NewF) { + Function &OldF = N.getFunction(); + +#ifndef NDEBUG + // Check that the RefSCC is still valid when we finish. + auto ExitVerifier = make_scope_exit([this] { verify(); }); + + assert(G->lookupRefSCC(N) == this && + "Cannot replace the function of a node outside this RefSCC."); + + assert(G->NodeMap.find(&NewF) == G->NodeMap.end() && + "Must not have already walked the new function!'"); + + // It is important that this replacement not introduce graph changes so we + // insist that the caller has already removed every use of the original + // function and that all uses of the new function correspond to existing + // edges in the graph. The common and expected way to use this is when + // replacing the function itself in the IR without changing the call graph + // shape and just updating the analysis based on that. + assert(&OldF != &NewF && "Cannot replace a function with itself!"); + assert(OldF.use_empty() && + "Must have moved all uses from the old function to the new!"); +#endif + + N.replaceFunction(NewF); + + // Update various call graph maps. + G->NodeMap.erase(&OldF); + G->NodeMap[&NewF] = &N; +} + +void LazyCallGraph::insertEdge(Node &SourceN, Node &TargetN, Edge::Kind EK) { assert(SCCMap.empty() && "This method cannot be called after SCCs have been formed!"); - return SourceN.insertEdgeInternal(Target, EK); + return SourceN->insertEdgeInternal(TargetN, EK); } -void LazyCallGraph::removeEdge(Node &SourceN, Function &Target) { +void LazyCallGraph::removeEdge(Node &SourceN, Node &TargetN) { assert(SCCMap.empty() && "This method cannot be called after SCCs have been formed!"); - return SourceN.removeEdgeInternal(Target); + bool Removed = SourceN->removeEdgeInternal(TargetN); + (void)Removed; + assert(Removed && "Target not in the edge set for this caller?"); } void LazyCallGraph::removeDeadFunction(Function &F) { @@ -1547,12 +1575,6 @@ assert(F.use_empty() && "This routine should only be called on trivially dead functions!"); - auto EII = EntryIndexMap.find(&F); - if (EII != EntryIndexMap.end()) { - EntryEdges[EII->second] = Edge(); - EntryIndexMap.erase(EII); - } - auto NI = NodeMap.find(&F); if (NI == NodeMap.end()) // Not in the graph at all! @@ -1561,6 +1583,9 @@ Node &N = *NI->second; NodeMap.erase(NI); + // Remove this from the entry edges if present. + EntryEdges.removeEdgeInternal(N); + if (SCCMap.empty()) { // No SCCs have been formed, so removing this is fine and there is nothing // else necessary at this point but clearing out the node. @@ -1585,10 +1610,9 @@ assert(RC.Parents.empty() && "Cannot have parents of a dead RefSCC!"); // Now remove this RefSCC from any parents sets and the leaf list. - for (Edge &E : N) - if (Node *TargetN = E.getNode()) - if (RefSCC *TargetRC = lookupRefSCC(*TargetN)) - TargetRC->Parents.erase(&RC); + for (Edge &E : *N) + if (RefSCC *TargetRC = lookupRefSCC(E.getNode())) + TargetRC->Parents.erase(&RC); // FIXME: This is a linear operation which could become hot and benefit from // an index map. auto LRI = find(LeafRefSCCs, &RC); @@ -1621,15 +1645,14 @@ { SmallVector Worklist; for (Edge &E : EntryEdges) - if (Node *EntryN = E.getNode()) - Worklist.push_back(EntryN); + Worklist.push_back(&E.getNode()); while (!Worklist.empty()) { - Node *N = Worklist.pop_back_val(); - N->G = this; - for (Edge &E : N->Edges) - if (Node *TargetN = E.getNode()) - Worklist.push_back(TargetN); + Node &N = *Worklist.pop_back_val(); + N.G = this; + if (N) + for (Edge &E : *N) + Worklist.push_back(&E.getNode()); } } @@ -1759,19 +1782,17 @@ // 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. - buildGenericSCCs(Nodes, [](Node &N) { return N.call_begin(); }, - [](Node &N) { return N.call_end(); }, - [](call_edge_iterator I) -> Node & { - // For SCCs, all the nodes should already be formed. - return *I->getNode(); - }, - [this, &RC](node_stack_range Nodes) { - RC.SCCs.push_back(createSCC(RC, Nodes)); - for (Node &N : *RC.SCCs.back()) { - N.DFSNumber = N.LowLink = -1; - SCCMap[&N] = RC.SCCs.back(); - } - }); + buildGenericSCCs( + Nodes, [](Node &N) { return N->call_begin(); }, + [](Node &N) { return N->call_end(); }, + [](EdgeSequence::call_iterator I) -> Node & { return I->getNode(); }, + [this, &RC](node_stack_range Nodes) { + RC.SCCs.push_back(createSCC(RC, Nodes)); + for (Node &N : *RC.SCCs.back()) { + N.DFSNumber = N.LowLink = -1; + SCCMap[&N] = RC.SCCs.back(); + } + }); // Wire up the SCC indices. for (int i = 0, Size = RC.SCCs.size(); i < Size; ++i) @@ -1787,18 +1808,21 @@ SmallVector Roots; for (Edge &E : *this) - Roots.push_back(&E.getNode(*this)); + Roots.push_back(&E.getNode()); // The roots will be popped of a stack, so use reverse to get a less // surprising order. This doesn't change any of the semantics anywhere. std::reverse(Roots.begin(), Roots.end()); buildGenericSCCs( - Roots, [](Node &N) { return N.begin(); }, [](Node &N) { return N.end(); }, - [this](edge_iterator I) -> Node & { - // Form the node if we haven't yet. - return I->getNode(*this); + Roots, + [](Node &N) { + // We need to populate each node as we begin to walk its edges. + N.populate(); + return N->begin(); }, + [](Node &N) { return N->end(); }, + [](EdgeSequence::iterator I) -> Node & { return I->getNode(); }, [this](node_stack_range Nodes) { RefSCC *NewRC = createRefSCC(*this); buildSCCs(*NewRC, Nodes); @@ -1826,10 +1850,8 @@ 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()); + for (Edge &E : *N) { + RefSCC &ChildRC = *lookupRefSCC(E.getNode()); if (&ChildRC == &RC) continue; ChildRC.Parents.insert(&RC); @@ -1847,7 +1869,7 @@ static void printNode(raw_ostream &OS, LazyCallGraph::Node &N) { OS << " Edges in function: " << N.getFunction().getName() << "\n"; - for (const LazyCallGraph::Edge &E : N) + for (LazyCallGraph::Edge &E : N.populate()) OS << " " << (E.isCall() ? "call" : "ref ") << " -> " << E.getFunction().getName() << "\n"; @@ -1895,7 +1917,7 @@ static void printNodeDOT(raw_ostream &OS, LazyCallGraph::Node &N) { std::string Name = "\"" + DOT::EscapeString(N.getFunction().getName()) + "\""; - for (const LazyCallGraph::Edge &E : N) { + for (LazyCallGraph::Edge &E : N.populate()) { OS << " " << Name << " -> \"" << DOT::EscapeString(E.getFunction().getName()) << "\""; if (!E.isCall()) // It is a ref edge. Index: llvm/trunk/lib/Transforms/IPO/Inliner.cpp =================================================================== --- llvm/trunk/lib/Transforms/IPO/Inliner.cpp +++ llvm/trunk/lib/Transforms/IPO/Inliner.cpp @@ -900,8 +900,8 @@ // below. for (Function *InlinedCallee : InlinedCallees) { LazyCallGraph::Node &CalleeN = *CG.lookup(*InlinedCallee); - for (LazyCallGraph::Edge &E : CalleeN) - RC->insertTrivialRefEdge(N, *E.getNode()); + for (LazyCallGraph::Edge &E : *CalleeN) + RC->insertTrivialRefEdge(N, E.getNode()); } InlinedCallees.clear(); Index: llvm/trunk/unittests/Analysis/LazyCallGraphTest.cpp =================================================================== --- llvm/trunk/unittests/Analysis/LazyCallGraphTest.cpp +++ llvm/trunk/unittests/Analysis/LazyCallGraphTest.cpp @@ -225,29 +225,29 @@ // 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++)->getNode(CG); + LazyCallGraph::Node &A1 = (I++)->getNode(); EXPECT_EQ("a1", A1.getFunction().getName()); - LazyCallGraph::Node &A2 = (I++)->getNode(CG); + LazyCallGraph::Node &A2 = (I++)->getNode(); EXPECT_EQ("a2", A2.getFunction().getName()); - LazyCallGraph::Node &A3 = (I++)->getNode(CG); + LazyCallGraph::Node &A3 = (I++)->getNode(); EXPECT_EQ("a3", A3.getFunction().getName()); - LazyCallGraph::Node &B1 = (I++)->getNode(CG); + LazyCallGraph::Node &B1 = (I++)->getNode(); EXPECT_EQ("b1", B1.getFunction().getName()); - LazyCallGraph::Node &B2 = (I++)->getNode(CG); + LazyCallGraph::Node &B2 = (I++)->getNode(); EXPECT_EQ("b2", B2.getFunction().getName()); - LazyCallGraph::Node &B3 = (I++)->getNode(CG); + LazyCallGraph::Node &B3 = (I++)->getNode(); EXPECT_EQ("b3", B3.getFunction().getName()); - LazyCallGraph::Node &C1 = (I++)->getNode(CG); + LazyCallGraph::Node &C1 = (I++)->getNode(); EXPECT_EQ("c1", C1.getFunction().getName()); - LazyCallGraph::Node &C2 = (I++)->getNode(CG); + LazyCallGraph::Node &C2 = (I++)->getNode(); EXPECT_EQ("c2", C2.getFunction().getName()); - LazyCallGraph::Node &C3 = (I++)->getNode(CG); + LazyCallGraph::Node &C3 = (I++)->getNode(); EXPECT_EQ("c3", C3.getFunction().getName()); - LazyCallGraph::Node &D1 = (I++)->getNode(CG); + LazyCallGraph::Node &D1 = (I++)->getNode(); EXPECT_EQ("d1", D1.getFunction().getName()); - LazyCallGraph::Node &D2 = (I++)->getNode(CG); + LazyCallGraph::Node &D2 = (I++)->getNode(); EXPECT_EQ("d2", D2.getFunction().getName()); - LazyCallGraph::Node &D3 = (I++)->getNode(CG); + LazyCallGraph::Node &D3 = (I++)->getNode(); EXPECT_EQ("d3", D3.getFunction().getName()); EXPECT_EQ(CG.end(), I); @@ -255,7 +255,7 @@ // independent of order. std::vector Nodes; - for (LazyCallGraph::Edge &E : A1) + for (LazyCallGraph::Edge &E : A1.populate()) Nodes.push_back(E.getFunction().getName()); std::sort(Nodes.begin(), Nodes.end()); EXPECT_EQ("a2", Nodes[0]); @@ -263,41 +263,50 @@ EXPECT_EQ("c3", Nodes[2]); Nodes.clear(); - EXPECT_EQ(A2.end(), std::next(A2.begin())); - EXPECT_EQ("a3", A2.begin()->getFunction().getName()); - EXPECT_EQ(A3.end(), std::next(A3.begin())); - EXPECT_EQ("a1", A3.begin()->getFunction().getName()); + A2.populate(); + EXPECT_EQ(A2->end(), std::next(A2->begin())); + EXPECT_EQ("a3", A2->begin()->getFunction().getName()); + A3.populate(); + EXPECT_EQ(A3->end(), std::next(A3->begin())); + EXPECT_EQ("a1", A3->begin()->getFunction().getName()); - for (LazyCallGraph::Edge &E : B1) + for (LazyCallGraph::Edge &E : B1.populate()) Nodes.push_back(E.getFunction().getName()); std::sort(Nodes.begin(), Nodes.end()); EXPECT_EQ("b2", Nodes[0]); EXPECT_EQ("d3", Nodes[1]); Nodes.clear(); - EXPECT_EQ(B2.end(), std::next(B2.begin())); - EXPECT_EQ("b3", B2.begin()->getFunction().getName()); - EXPECT_EQ(B3.end(), std::next(B3.begin())); - EXPECT_EQ("b1", B3.begin()->getFunction().getName()); + B2.populate(); + EXPECT_EQ(B2->end(), std::next(B2->begin())); + EXPECT_EQ("b3", B2->begin()->getFunction().getName()); + B3.populate(); + EXPECT_EQ(B3->end(), std::next(B3->begin())); + EXPECT_EQ("b1", B3->begin()->getFunction().getName()); - for (LazyCallGraph::Edge &E : C1) + for (LazyCallGraph::Edge &E : C1.populate()) Nodes.push_back(E.getFunction().getName()); std::sort(Nodes.begin(), Nodes.end()); EXPECT_EQ("c2", Nodes[0]); EXPECT_EQ("d2", Nodes[1]); Nodes.clear(); - EXPECT_EQ(C2.end(), std::next(C2.begin())); - EXPECT_EQ("c3", C2.begin()->getFunction().getName()); - EXPECT_EQ(C3.end(), std::next(C3.begin())); - EXPECT_EQ("c1", C3.begin()->getFunction().getName()); - - EXPECT_EQ(D1.end(), std::next(D1.begin())); - EXPECT_EQ("d2", D1.begin()->getFunction().getName()); - EXPECT_EQ(D2.end(), std::next(D2.begin())); - EXPECT_EQ("d3", D2.begin()->getFunction().getName()); - EXPECT_EQ(D3.end(), std::next(D3.begin())); - EXPECT_EQ("d1", D3.begin()->getFunction().getName()); + C2.populate(); + EXPECT_EQ(C2->end(), std::next(C2->begin())); + EXPECT_EQ("c3", C2->begin()->getFunction().getName()); + C3.populate(); + EXPECT_EQ(C3->end(), std::next(C3->begin())); + EXPECT_EQ("c1", C3->begin()->getFunction().getName()); + + D1.populate(); + EXPECT_EQ(D1->end(), std::next(D1->begin())); + EXPECT_EQ("d2", D1->begin()->getFunction().getName()); + D2.populate(); + EXPECT_EQ(D2->end(), std::next(D2->begin())); + EXPECT_EQ("d3", D2->begin()->getFunction().getName()); + D3.populate(); + EXPECT_EQ(D3->end(), std::next(D3->begin())); + EXPECT_EQ("d1", D3->begin()->getFunction().getName()); // Now lets look at the RefSCCs and SCCs. CG.buildRefSCCs(); @@ -402,32 +411,35 @@ LazyCallGraph::Node &A = CG.get(lookupFunction(*M, "a")); LazyCallGraph::Node &B = CG.get(lookupFunction(*M, "b")); - EXPECT_EQ(2, std::distance(A.begin(), A.end())); - EXPECT_EQ(0, std::distance(B.begin(), B.end())); + A.populate(); + EXPECT_EQ(2, std::distance(A->begin(), A->end())); + B.populate(); + EXPECT_EQ(0, std::distance(B->begin(), B->end())); + + LazyCallGraph::Node &C = CG.get(lookupFunction(*M, "c")); + C.populate(); + CG.insertEdge(B, C, LazyCallGraph::Edge::Call); + EXPECT_EQ(1, std::distance(B->begin(), B->end())); + EXPECT_EQ(0, std::distance(C->begin(), C->end())); + + CG.insertEdge(C, B, LazyCallGraph::Edge::Call); + EXPECT_EQ(1, std::distance(C->begin(), C->end())); + EXPECT_EQ(&B, &C->begin()->getNode()); + + CG.insertEdge(C, C, LazyCallGraph::Edge::Call); + EXPECT_EQ(2, std::distance(C->begin(), C->end())); + EXPECT_EQ(&B, &C->begin()->getNode()); + EXPECT_EQ(&C, &std::next(C->begin())->getNode()); + + CG.removeEdge(C, B); + EXPECT_EQ(1, std::distance(C->begin(), C->end())); + EXPECT_EQ(&C, &C->begin()->getNode()); - CG.insertEdge(B, lookupFunction(*M, "c"), LazyCallGraph::Edge::Call); - EXPECT_EQ(1, std::distance(B.begin(), B.end())); - LazyCallGraph::Node &C = B.begin()->getNode(CG); - EXPECT_EQ(0, std::distance(C.begin(), C.end())); - - CG.insertEdge(C, B.getFunction(), LazyCallGraph::Edge::Call); - EXPECT_EQ(1, std::distance(C.begin(), C.end())); - EXPECT_EQ(&B, C.begin()->getNode()); - - CG.insertEdge(C, C.getFunction(), LazyCallGraph::Edge::Call); - EXPECT_EQ(2, std::distance(C.begin(), C.end())); - 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()->getNode()); + CG.removeEdge(C, C); + EXPECT_EQ(0, std::distance(C->begin(), C->end())); - CG.removeEdge(C, C.getFunction()); - EXPECT_EQ(0, std::distance(C.begin(), C.end())); - - CG.removeEdge(B, C.getFunction()); - EXPECT_EQ(0, std::distance(B.begin(), B.end())); + CG.removeEdge(B, C); + EXPECT_EQ(0, std::distance(B->begin(), B->end())); } TEST(LazyCallGraphTest, InnerSCCFormation) { @@ -437,8 +449,11 @@ // 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); + LazyCallGraph::Node &D1 = CG.get(lookupFunction(*M, "d1")); + LazyCallGraph::Node &A1 = CG.get(lookupFunction(*M, "a1")); + A1.populate(); + D1.populate(); + CG.insertEdge(D1, A1, LazyCallGraph::Edge::Ref); // Build vectors and sort them for the rest of the assertions to make them // independent of order. @@ -614,13 +629,13 @@ EXPECT_TRUE(DRC.isChildOf(CRC)); EXPECT_TRUE(DC.isChildOf(CC)); - EXPECT_EQ(2, std::distance(A.begin(), A.end())); + EXPECT_EQ(2, std::distance(A->begin(), A->end())); ARC.insertOutgoingEdge(A, D, LazyCallGraph::Edge::Call); - EXPECT_EQ(3, std::distance(A.begin(), A.end())); - const LazyCallGraph::Edge &NewE = A[D]; + EXPECT_EQ(3, std::distance(A->begin(), A->end())); + const LazyCallGraph::Edge &NewE = (*A)[D]; EXPECT_TRUE(NewE); EXPECT_TRUE(NewE.isCall()); - EXPECT_EQ(&D, NewE.getNode()); + EXPECT_EQ(&D, &NewE.getNode()); // Only the parent and child tests sholud have changed. The rest of the graph // remains the same. @@ -684,7 +699,7 @@ EXPECT_EQ(&DRC, CG.lookupRefSCC(D)); ARC.removeOutgoingEdge(A, D); - EXPECT_EQ(2, std::distance(A.begin(), A.end())); + 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)); @@ -755,7 +770,7 @@ 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())); + ASSERT_EQ(1, std::distance(D2->begin(), D2->end())); // Add an edge to make the graph: // @@ -772,10 +787,10 @@ // a3--a2 | auto MergedRCs = CRC.insertIncomingRefEdge(D2, C2); // Make sure we connected the nodes. - for (LazyCallGraph::Edge E : D2) { - if (E.getNode() == &D3) + for (LazyCallGraph::Edge E : *D2) { + if (&E.getNode() == &D3) continue; - EXPECT_EQ(&C2, E.getNode()); + EXPECT_EQ(&C2, &E.getNode()); } // And marked the D ref-SCC as no longer valid. EXPECT_EQ(1u, MergedRCs.size()); @@ -847,7 +862,7 @@ 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())); + ASSERT_EQ(1, std::distance(D2->begin(), D2->end())); // Add an edge to make the graph: // @@ -864,10 +879,10 @@ // a3--a2 | auto MergedRCs = CRC.insertIncomingRefEdge(D2, C2); // Make sure we connected the nodes. - for (LazyCallGraph::Edge E : D2) { - if (E.getNode() == &D3) + for (LazyCallGraph::Edge E : *D2) { + if (&E.getNode() == &D3) continue; - EXPECT_EQ(&C2, E.getNode()); + EXPECT_EQ(&C2, &E.getNode()); } // And marked the D ref-SCC as no longer valid. EXPECT_EQ(1u, MergedRCs.size()); @@ -946,8 +961,8 @@ // Connect the top to the bottom forming a large RefSCC made up mostly of calls. auto MergedRCs = ARC.insertIncomingRefEdge(D, A); // Make sure we connected the nodes. - EXPECT_NE(D.begin(), D.end()); - EXPECT_EQ(&A, D.begin()->getNode()); + EXPECT_NE(D->begin(), D->end()); + EXPECT_EQ(&A, &D->begin()->getNode()); // Check that we have the dead RCs, but ignore the order. EXPECT_EQ(3u, MergedRCs.size()); @@ -1020,8 +1035,8 @@ // references. auto MergedRCs = ARC.insertIncomingRefEdge(D, A); // Make sure we connected the nodes. - EXPECT_NE(D.begin(), D.end()); - EXPECT_EQ(&A, D.begin()->getNode()); + EXPECT_NE(D->begin(), D->end()); + EXPECT_EQ(&A, &D->begin()->getNode()); // Check that we have the dead RCs, but ignore the order. EXPECT_EQ(3u, MergedRCs.size()); @@ -1093,7 +1108,7 @@ 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())); + ASSERT_EQ(1, std::distance(D2->begin(), D2->end())); // Delete d2 from the graph, as if it had been inlined. // @@ -1227,7 +1242,7 @@ // 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(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)); @@ -1884,4 +1899,84 @@ EXPECT_TRUE(GRC.isParentOf(FRC)); } +TEST(LazyCallGraphTest, ReplaceNodeFunction) { + LLVMContext Context; + // A graph with several different kinds of edges pointing at a particular + // function. + std::unique_ptr M = + parseAssembly(Context, + "define void @a(i8** %ptr) {\n" + "entry:\n" + " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n" + " ret void\n" + "}\n" + "define void @b(i8** %ptr) {\n" + "entry:\n" + " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n" + " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n" + " call void @d(i8** %ptr)" + " ret void\n" + "}\n" + "define void @c(i8** %ptr) {\n" + "entry:\n" + " call void @d(i8** %ptr)" + " call void @d(i8** %ptr)" + " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n" + " ret void\n" + "}\n" + "define void @d(i8** %ptr) {\n" + "entry:\n" + " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n" + " call void @c(i8** %ptr)" + " call void @d(i8** %ptr)" + " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n" + " ret void\n" + "}\n"); + LazyCallGraph CG(*M); + + // Force the graph to be fully expanded. + CG.buildRefSCCs(); + auto I = CG.postorder_ref_scc_begin(); + LazyCallGraph::RefSCC &RC1 = *I++; + LazyCallGraph::RefSCC &RC2 = *I++; + EXPECT_EQ(CG.postorder_ref_scc_end(), I); + + ASSERT_EQ(2u, RC1.size()); + LazyCallGraph::SCC &C1 = RC1[0]; + LazyCallGraph::SCC &C2 = RC1[1]; + + LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a")); + LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b")); + LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c")); + LazyCallGraph::Node &DN = *CG.lookup(lookupFunction(*M, "d")); + EXPECT_EQ(&C1, CG.lookupSCC(DN)); + EXPECT_EQ(&C1, CG.lookupSCC(CN)); + EXPECT_EQ(&C2, CG.lookupSCC(BN)); + EXPECT_EQ(&RC1, CG.lookupRefSCC(DN)); + EXPECT_EQ(&RC1, CG.lookupRefSCC(CN)); + EXPECT_EQ(&RC1, CG.lookupRefSCC(BN)); + EXPECT_EQ(&RC2, CG.lookupRefSCC(AN)); + + // Now we need to build a new function 'e' with the same signature as 'd'. + Function &D = DN.getFunction(); + Function &E = *Function::Create(D.getFunctionType(), D.getLinkage(), "e"); + D.getParent()->getFunctionList().insert(D.getIterator(), &E); + + // Change each use of 'd' to use 'e'. This is particularly easy as they have + // the same type. + D.replaceAllUsesWith(&E); + + // Splice the body of the old function into the new one. + E.getBasicBlockList().splice(E.begin(), D.getBasicBlockList()); + // And fix up the one argument. + D.arg_begin()->replaceAllUsesWith(&*E.arg_begin()); + E.arg_begin()->takeName(&*D.arg_begin()); + + // Now replace the function in the graph. + RC1.replaceNodeFunction(DN, E); + + EXPECT_EQ(&E, &DN.getFunction()); + EXPECT_EQ(&DN, &(*CN)[DN].getNode()); + EXPECT_EQ(&DN, &(*BN)[DN].getNode()); +} }