diff options
Diffstat (limited to 'include/llvm/Analysis/LazyCallGraph.h')
| -rw-r--r-- | include/llvm/Analysis/LazyCallGraph.h | 566 |
1 files changed, 566 insertions, 0 deletions
diff --git a/include/llvm/Analysis/LazyCallGraph.h b/include/llvm/Analysis/LazyCallGraph.h new file mode 100644 index 000000000000..70a4df51c1ed --- /dev/null +++ b/include/llvm/Analysis/LazyCallGraph.h @@ -0,0 +1,566 @@ +//===- LazyCallGraph.h - Analysis of a Module's call graph ------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// +/// Implements a lazy call graph analysis and related passes for the new pass +/// manager. +/// +/// NB: This is *not* a traditional call graph! It is a graph which models both +/// the current calls and potential calls. As a consequence there are many +/// edges in this call graph that do not correspond to a 'call' or 'invoke' +/// instruction. +/// +/// The primary use cases of this graph analysis is to facilitate iterating +/// across the functions of a module in ways that ensure all callees are +/// visited prior to a caller (given any SCC constraints), or vice versa. As +/// such is it particularly well suited to organizing CGSCC optimizations such +/// as inlining, outlining, argument promotion, etc. That is its primary use +/// case and motivates the design. It may not be appropriate for other +/// purposes. The use graph of functions or some other conservative analysis of +/// call instructions may be interesting for optimizations and subsequent +/// analyses which don't work in the context of an overly specified +/// potential-call-edge graph. +/// +/// To understand the specific rules and nature of this call graph analysis, +/// see the documentation of the \c LazyCallGraph below. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_LAZY_CALL_GRAPH +#define LLVM_ANALYSIS_LAZY_CALL_GRAPH + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/PointerUnion.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/iterator.h" +#include "llvm/ADT/iterator_range.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Module.h" +#include "llvm/Support/Allocator.h" +#include <iterator> + +namespace llvm { +class ModuleAnalysisManager; +class PreservedAnalyses; +class raw_ostream; + +/// \brief A lazily constructed view of the call graph of a module. +/// +/// With the edges of this graph, the motivating constraint that we are +/// attempting to maintain is that function-local optimization, CGSCC-local +/// optimizations, and optimizations transforming a pair of functions connected +/// by an edge in the graph, do not invalidate a bottom-up traversal of the SCC +/// DAG. That is, no optimizations will delete, remove, or add an edge such +/// that functions already visited in a bottom-up order of the SCC DAG are no +/// longer valid to have visited, or such that functions not yet visited in +/// a bottom-up order of the SCC DAG are not required to have already been +/// visited. +/// +/// Within this constraint, the desire is to minimize the merge points of the +/// SCC DAG. The greater the fanout of the SCC DAG and the fewer merge points +/// in the SCC DAG, the more independence there is in optimizing within it. +/// There is a strong desire to enable parallelization of optimizations over +/// the call graph, and both limited fanout and merge points will (artificially +/// in some cases) limit the scaling of such an effort. +/// +/// To this end, graph represents both direct and any potential resolution to +/// an indirect call edge. Another way to think about it is that it represents +/// both the direct call edges and any direct call edges that might be formed +/// through static optimizations. Specifically, it considers taking the address +/// of a function to be an edge in the call graph because this might be +/// forwarded to become a direct call by some subsequent function-local +/// optimization. The result is that the graph closely follows the use-def +/// edges for functions. Walking "up" the graph can be done by looking at all +/// of the uses of a function. +/// +/// The roots of the call graph are the external functions and functions +/// escaped into global variables. Those functions can be called from outside +/// of the module or via unknowable means in the IR -- we may not be able to +/// form even a potential call edge from a function body which may dynamically +/// load the function and call it. +/// +/// This analysis still requires updates to remain valid after optimizations +/// which could potentially change the set of potential callees. The +/// constraints it operates under only make the traversal order remain valid. +/// +/// The entire analysis must be re-computed if full interprocedural +/// optimizations run at any point. For example, globalopt completely +/// invalidates the information in this analysis. +/// +/// FIXME: This class is named LazyCallGraph in a lame attempt to distinguish +/// it from the existing CallGraph. At some point, it is expected that this +/// will be the only call graph and it will be renamed accordingly. +class LazyCallGraph { +public: + class Node; + class SCC; + typedef SmallVector<PointerUnion<Function *, Node *>, 4> NodeVectorT; + typedef SmallVectorImpl<PointerUnion<Function *, Node *>> NodeVectorImplT; + + /// \brief A lazy iterator used for both the entry nodes and child nodes. + /// + /// 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 iterator + : public iterator_adaptor_base<iterator, NodeVectorImplT::iterator, + std::forward_iterator_tag, Node> { + friend class LazyCallGraph; + friend class LazyCallGraph::Node; + + LazyCallGraph *G; + NodeVectorImplT::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()) + ++I; + } + + public: + iterator() {} + + using iterator_adaptor_base::operator++; + iterator &operator++() { + do { + ++I; + } while (I != E && I->isNull()); + return *this; + } + + reference operator*() const { + if (I->is<Node *>()) + return *I->get<Node *>(); + + Function *F = I->get<Function *>(); + Node &ChildN = G->get(*F); + *I = &ChildN; + return ChildN; + } + }; + + /// \brief 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. + class Node { + friend class LazyCallGraph; + friend class LazyCallGraph::SCC; + + LazyCallGraph *G; + Function &F; + + // We provide for the DFS numbering and Tarjan walk lowlink numbers to be + // stored directly within the node. + int DFSNumber; + int LowLink; + + mutable NodeVectorT Callees; + DenseMap<Function *, size_t> CalleeIndexMap; + + /// \brief Basic constructor implements the scanning of F into Callees and + /// CalleeIndexMap. + Node(LazyCallGraph &G, Function &F); + + /// \brief Internal helper to insert a callee. + void insertEdgeInternal(Function &Callee); + + /// \brief Internal helper to insert a callee. + void insertEdgeInternal(Node &CalleeN); + + /// \brief Internal helper to remove a callee from this node. + void removeEdgeInternal(Function &Callee); + + public: + typedef LazyCallGraph::iterator iterator; + + Function &getFunction() const { + return F; + }; + + iterator begin() const { + return iterator(*G, Callees.begin(), Callees.end()); + } + iterator end() const { return iterator(*G, Callees.end(), Callees.end()); } + + /// Equality is defined as address equality. + bool operator==(const Node &N) const { return this == &N; } + bool operator!=(const Node &N) const { return !operator==(N); } + }; + + /// \brief An SCC of the call graph. + /// + /// This represents a Strongly Connected Component of the call graph as + /// a collection of call graph nodes. While the order of nodes in the SCC is + /// stable, it is not any particular order. + class SCC { + friend class LazyCallGraph; + friend class LazyCallGraph::Node; + + LazyCallGraph *G; + SmallPtrSet<SCC *, 1> ParentSCCs; + SmallVector<Node *, 1> Nodes; + + SCC(LazyCallGraph &G) : G(&G) {} + + void insert(Node &N); + + void + internalDFS(SmallVectorImpl<std::pair<Node *, Node::iterator>> &DFSStack, + SmallVectorImpl<Node *> &PendingSCCStack, Node *N, + SmallVectorImpl<SCC *> &ResultSCCs); + + public: + typedef SmallVectorImpl<Node *>::const_iterator iterator; + typedef pointee_iterator<SmallPtrSet<SCC *, 1>::const_iterator> parent_iterator; + + iterator begin() const { return Nodes.begin(); } + iterator end() const { return Nodes.end(); } + + parent_iterator parent_begin() const { return ParentSCCs.begin(); } + parent_iterator parent_end() const { return ParentSCCs.end(); } + + iterator_range<parent_iterator> parents() const { + return iterator_range<parent_iterator>(parent_begin(), parent_end()); + } + + /// \brief Test if this SCC is a parent of \a C. + bool isParentOf(const SCC &C) const { return C.isChildOf(*this); } + + /// \brief Test if this SCC is an ancestor of \a C. + bool isAncestorOf(const SCC &C) const { return C.isDescendantOf(*this); } + + /// \brief Test if this SCC is a child of \a C. + bool isChildOf(const SCC &C) const { + return ParentSCCs.count(const_cast<SCC *>(&C)); + } + + /// \brief Test if this SCC is a descendant of \a C. + bool isDescendantOf(const SCC &C) const; + + ///@{ + /// \name Mutation API + /// + /// These methods provide the core API for updating the call graph in the + /// presence of a (potentially still in-flight) DFS-found SCCs. + /// + /// Note that these methods sometimes have complex runtimes, so be careful + /// how you call them. + + /// \brief Insert an edge from one node in this SCC to another in this SCC. + /// + /// By the definition of an SCC, this does not change the nature or make-up + /// of any SCCs. + void insertIntraSCCEdge(Node &CallerN, Node &CalleeN); + + /// \brief 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); + + /// \brief Insert an edge whose tail is in a descendant SCC and head is in + /// this SCC. + /// + /// There must be an existing path from the callee to the caller in this + /// case. NB! This is has the potential to be a very expensive function. It + /// inherently forms a cycle in the prior SCC DAG and we have to merge SCCs + /// to resolve that cycle. But finding all of the SCCs which participate in + /// the cycle can in the worst case require traversing every SCC in the + /// graph. Every attempt is made to avoid that, but passes must still + /// exercise caution calling this routine repeatedly. + /// + /// 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); + + /// \brief Remove an edge whose source is in this SCC and target is *not*. + /// + /// This removes an inter-SCC edge. All inter-SCC edges originating from + /// this SCC have been fully explored by any in-flight DFS SCC formation, + /// so this is always safe to call once you have the source SCC. + /// + /// This operation does not change the set of SCCs or the members of the + /// SCCs and so is very inexpensive. It may change the connectivity graph + /// of the SCCs though, so be careful calling this while iterating over + /// them. + void removeInterSCCEdge(Node &CallerN, Node &CalleeN); + + /// \brief Remove an edge which is entirely within this SCC. + /// + /// Both the \a Caller and the \a Callee must be within this SCC. Removing + /// such an edge make break cycles that form this SCC and thus this + /// operation may change the SCC graph significantly. In particular, this + /// operation will re-form new SCCs based on the remaining connectivity of + /// the graph. The following invariants are guaranteed to hold after + /// calling this method: + /// + /// 1) This SCC is still an SCC in the graph. + /// 2) This SCC will be the parent of any new SCCs. Thus, this SCC is + /// preserved as the root of any new SCC directed graph formed. + /// 3) No SCC other than this SCC has its member set changed (this is + /// inherent in the definition of removing such an edge). + /// 4) All of the parent links of the SCC graph will be updated to reflect + /// the new SCC structure. + /// 5) All SCCs formed out of this SCC, excluding this SCC, will be + /// returned in a vector. + /// 6) The order of the SCCs in the vector will be a valid postorder + /// traversal of the new SCCs. + /// + /// These invariants are very important to ensure that we can build + /// optimization pipeliens on top of the CGSCC pass manager which + /// intelligently update the SCC graph without invalidating other parts of + /// the SCC graph. + /// + /// The runtime complexity of this method is, in the worst case, O(V+E) + /// where V is the number of nodes in this SCC and E is the number of edges + /// leaving the nodes in this SCC. Note that E includes both edges within + /// this SCC and edges from this SCC to child SCCs. Some effort has been + /// made to minimize the overhead of common cases such as self-edges and + /// edge removals which result in a spanning tree with no more cycles. + SmallVector<SCC *, 1> removeIntraSCCEdge(Node &CallerN, Node &CalleeN); + + ///@} + }; + + /// \brief A post-order depth-first SCC iterator over the call graph. + /// + /// This iterator triggers the Tarjan DFS-based formation of the SCC DAG for + /// the call graph, walking it lazily in depth-first post-order. That is, it + /// always visits SCCs for a callee prior to visiting the SCC for a caller + /// (when they are in different SCCs). + class postorder_scc_iterator + : public iterator_facade_base<postorder_scc_iterator, + std::forward_iterator_tag, SCC> { + friend class LazyCallGraph; + friend class LazyCallGraph::Node; + + /// \brief Nonce type to select the constructor for the end iterator. + struct IsAtEndT {}; + + LazyCallGraph *G; + SCC *C; + + // Build the begin iterator for a node. + postorder_scc_iterator(LazyCallGraph &G) : G(&G) { + C = G.getNextSCCInPostOrder(); + } + + // Build the end iterator for a node. This is selected purely by overload. + postorder_scc_iterator(LazyCallGraph &G, IsAtEndT /*Nonce*/) + : G(&G), C(nullptr) {} + + public: + bool operator==(const postorder_scc_iterator &Arg) const { + return G == Arg.G && C == Arg.C; + } + + reference operator*() const { return *C; } + + using iterator_facade_base::operator++; + postorder_scc_iterator &operator++() { + C = G->getNextSCCInPostOrder(); + return *this; + } + }; + + /// \brief Construct a graph for the given module. + /// + /// This sets up the graph and computes all of the entry points of the graph. + /// No function definitions are scanned until their nodes in the graph are + /// requested during traversal. + LazyCallGraph(Module &M); + + LazyCallGraph(LazyCallGraph &&G); + LazyCallGraph &operator=(LazyCallGraph &&RHS); + + iterator begin() { + return iterator(*this, EntryNodes.begin(), EntryNodes.end()); + } + iterator end() { return iterator(*this, EntryNodes.end(), EntryNodes.end()); } + + postorder_scc_iterator postorder_scc_begin() { + return postorder_scc_iterator(*this); + } + postorder_scc_iterator postorder_scc_end() { + return postorder_scc_iterator(*this, postorder_scc_iterator::IsAtEndT()); + } + + iterator_range<postorder_scc_iterator> postorder_sccs() { + return iterator_range<postorder_scc_iterator>(postorder_scc_begin(), + postorder_scc_end()); + } + + /// \brief Lookup a function in the graph which has already been scanned and + /// added. + Node *lookup(const Function &F) const { return NodeMap.lookup(&F); } + + /// \brief Lookup a function's SCC in the graph. + /// + /// \returns null if the function hasn't been assigned an SCC via the SCC + /// iterator walk. + SCC *lookupSCC(Node &N) const { return SCCMap.lookup(&N); } + + /// \brief Get a graph node for a given function, scanning it to populate the + /// graph data as necessary. + Node &get(Function &F) { + Node *&N = NodeMap[&F]; + if (N) + return *N; + + return insertInto(F, N); + } + + ///@{ + /// \name Pre-SCC Mutation API + /// + /// These methods are only valid to call prior to forming any SCCs for this + /// call graph. They can be used to update the core node-graph during + /// a node-based inorder traversal that precedes any SCC-based traversal. + /// + /// Once you begin manipulating a call graph's SCCs, you must perform all + /// mutation of the graph via the SCC methods. + + /// \brief Update the call graph after inserting a new edge. + void insertEdge(Node &Caller, Function &Callee); + + /// \brief Update the call graph after inserting a new edge. + void insertEdge(Function &Caller, Function &Callee) { + return insertEdge(get(Caller), Callee); + } + + /// \brief Update the call graph after deleting an edge. + void removeEdge(Node &Caller, Function &Callee); + + /// \brief Update the call graph after deleting an edge. + void removeEdge(Function &Caller, Function &Callee) { + return removeEdge(get(Caller), Callee); + } + + ///@} + +private: + /// \brief Allocator that holds all the call graph nodes. + SpecificBumpPtrAllocator<Node> BPA; + + /// \brief Maps function->node for fast lookup. + DenseMap<const Function *, Node *> NodeMap; + + /// \brief The entry nodes to the graph. + /// + /// These nodes are reachable through "external" means. Put another way, they + /// escape at the module scope. + NodeVectorT EntryNodes; + + /// \brief Map of the entry nodes in the graph to their indices in + /// \c EntryNodes. + DenseMap<Function *, size_t> EntryIndexMap; + + /// \brief Allocator that holds all the call graph SCCs. + SpecificBumpPtrAllocator<SCC> SCCBPA; + + /// \brief Maps Function -> SCC for fast lookup. + DenseMap<Node *, SCC *> SCCMap; + + /// \brief The leaf SCCs of the graph. + /// + /// These are all of the SCCs which have no children. + SmallVector<SCC *, 4> LeafSCCs; + + /// \brief Stack of nodes in the DFS walk. + SmallVector<std::pair<Node *, iterator>, 4> DFSStack; + + /// \brief Set of entry nodes not-yet-processed into SCCs. + SmallVector<Function *, 4> SCCEntryNodes; + + /// \brief Stack of nodes the DFS has walked but not yet put into a SCC. + SmallVector<Node *, 4> PendingSCCStack; + + /// \brief Counter for the next DFS number to assign. + int NextDFSNumber; + + /// \brief Helper to insert a new function, with an already looked-up entry in + /// the NodeMap. + Node &insertInto(Function &F, Node *&MappedN); + + /// \brief Helper to update pointers back to the graph object during moves. + void updateGraphPtrs(); + + /// \brief Helper to form a new SCC out of the top of a DFSStack-like + /// structure. + SCC *formSCC(Node *RootN, SmallVectorImpl<Node *> &NodeStack); + + /// \brief Retrieve the next node in the post-order SCC walk of the call graph. + SCC *getNextSCCInPostOrder(); +}; + +// Provide GraphTraits specializations for call graphs. +template <> struct GraphTraits<LazyCallGraph::Node *> { + typedef LazyCallGraph::Node NodeType; + typedef LazyCallGraph::iterator ChildIteratorType; + + static NodeType *getEntryNode(NodeType *N) { return N; } + static ChildIteratorType child_begin(NodeType *N) { return N->begin(); } + static ChildIteratorType child_end(NodeType *N) { return N->end(); } +}; +template <> struct GraphTraits<LazyCallGraph *> { + typedef LazyCallGraph::Node NodeType; + typedef LazyCallGraph::iterator ChildIteratorType; + + static NodeType *getEntryNode(NodeType *N) { return N; } + static ChildIteratorType child_begin(NodeType *N) { return N->begin(); } + static ChildIteratorType child_end(NodeType *N) { return N->end(); } +}; + +/// \brief An analysis pass which computes the call graph for a module. +class LazyCallGraphAnalysis { +public: + /// \brief Inform generic clients of the result type. + typedef LazyCallGraph Result; + + static void *ID() { return (void *)&PassID; } + + /// \brief Compute the \c LazyCallGraph for a the module \c M. + /// + /// This just builds the set of entry points to the call graph. The rest is + /// built lazily as it is walked. + LazyCallGraph run(Module *M) { return LazyCallGraph(*M); } + +private: + static char PassID; +}; + +/// \brief A pass which prints the call graph to a \c raw_ostream. +/// +/// This is primarily useful for testing the analysis. +class LazyCallGraphPrinterPass { + raw_ostream &OS; + +public: + explicit LazyCallGraphPrinterPass(raw_ostream &OS); + + PreservedAnalyses run(Module *M, ModuleAnalysisManager *AM); + + static StringRef name() { return "LazyCallGraphPrinterPass"; } +}; + +} + +#endif |