From a4499e9f73f10b2f29dc2d104ab6b3dc0df16d8c Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Tue, 2 Feb 2016 03:57:13 +0000 Subject: [LCG] Build an edge abstraction for the LazyCallGraph and use it to differentiate between indirect references to functions an direct calls. This doesn't do a whole lot yet other than change the print out produced by the analysis, but it lays the groundwork for a very major change I'm working on next: teaching the call graph to actually be a call graph, modeling *both* the indirect reference graph and the call graph simultaneously. More details on that in the next patch though. The rest of this is essentially a bunch of over-engineering that won't be interesting until the next patch. But this also isolates essentially all of the churn necessary to introduce the edge abstraction from the very important behavior change necessary in order to separately model the two graphs. So it should make review of the subsequent patch a bit easier at the cost of making this patch seem poorly motivated. ;] Differential Revision: http://reviews.llvm.org/D16038 llvm-svn: 259463 --- llvm/include/llvm/Analysis/LazyCallGraph.h | 253 ++++++++++++++++++++++------- 1 file changed, 198 insertions(+), 55 deletions(-) (limited to 'llvm/include') 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, 4> NodeVectorT; - typedef SmallVectorImpl> 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, 1, Kind> Value; + }; + + typedef SmallVector EdgeVectorT; + typedef SmallVectorImpl EdgeVectorImplT; /// A node in the call graph. /// @@ -125,31 +195,33 @@ public: int DFSNumber; int LowLink; - mutable NodeVectorT Callees; - DenseMap CalleeIndexMap; + mutable EdgeVectorT Edges; + DenseMap 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 { + class edge_iterator + : public iterator_adaptor_base { 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 { + friend class LazyCallGraph; + friend class LazyCallGraph::Node; - reference operator*() const { - if (I->is()) - return *I->get(); + EdgeVectorImplT::iterator E; - Function *F = I->get(); - 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> &DFSStack, + internalDFS(SmallVectorImpl> &DFSStack, SmallVectorImpl &PendingSCCStack, Node *N, SmallVectorImpl &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 insertIncomingEdge(Node &CallerN, Node &CalleeN); + SmallVector 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 removeIntraSCCEdge(Node &CallerN, Node &CalleeN); + SmallVector 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 EntryIndexMap; /// Allocator that holds all the call graph SCCs. @@ -487,7 +588,7 @@ private: SmallVector LeafSCCs; /// Stack of nodes in the DFS walk. - SmallVector, 4> DFSStack; + SmallVector, 4> DFSStack; /// Set of entry nodes not-yet-processed into SCCs. SmallVector 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()) + return *F; + + return P.get()->getFunction(); +} + +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) { + 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; +} + // Provide GraphTraits specializations for call graphs. template <> struct GraphTraits { 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 { }; template <> struct GraphTraits { 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(); } -- cgit v1.2.3