Home | History | Annotate | Download | only in Analysis
      1 //===- LazyCallGraph.h - Analysis of a Module's call graph ------*- C++ -*-===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 /// \file
     10 ///
     11 /// Implements a lazy call graph analysis and related passes for the new pass
     12 /// manager.
     13 ///
     14 /// NB: This is *not* a traditional call graph! It is a graph which models both
     15 /// the current calls and potential calls. As a consequence there are many
     16 /// edges in this call graph that do not correspond to a 'call' or 'invoke'
     17 /// instruction.
     18 ///
     19 /// The primary use cases of this graph analysis is to facilitate iterating
     20 /// across the functions of a module in ways that ensure all callees are
     21 /// visited prior to a caller (given any SCC constraints), or vice versa. As
     22 /// such is it particularly well suited to organizing CGSCC optimizations such
     23 /// as inlining, outlining, argument promotion, etc. That is its primary use
     24 /// case and motivates the design. It may not be appropriate for other
     25 /// purposes. The use graph of functions or some other conservative analysis of
     26 /// call instructions may be interesting for optimizations and subsequent
     27 /// analyses which don't work in the context of an overly specified
     28 /// potential-call-edge graph.
     29 ///
     30 /// To understand the specific rules and nature of this call graph analysis,
     31 /// see the documentation of the \c LazyCallGraph below.
     32 ///
     33 //===----------------------------------------------------------------------===//
     34 
     35 #ifndef LLVM_ANALYSIS_LAZYCALLGRAPH_H
     36 #define LLVM_ANALYSIS_LAZYCALLGRAPH_H
     37 
     38 #include "llvm/ADT/DenseMap.h"
     39 #include "llvm/ADT/PointerUnion.h"
     40 #include "llvm/ADT/STLExtras.h"
     41 #include "llvm/ADT/SetVector.h"
     42 #include "llvm/ADT/SmallPtrSet.h"
     43 #include "llvm/ADT/SmallVector.h"
     44 #include "llvm/ADT/iterator.h"
     45 #include "llvm/ADT/iterator_range.h"
     46 #include "llvm/IR/BasicBlock.h"
     47 #include "llvm/IR/Function.h"
     48 #include "llvm/IR/Module.h"
     49 #include "llvm/IR/PassManager.h"
     50 #include "llvm/Support/Allocator.h"
     51 #include <iterator>
     52 
     53 namespace llvm {
     54 class PreservedAnalyses;
     55 class raw_ostream;
     56 
     57 /// \brief A lazily constructed view of the call graph of a module.
     58 ///
     59 /// With the edges of this graph, the motivating constraint that we are
     60 /// attempting to maintain is that function-local optimization, CGSCC-local
     61 /// optimizations, and optimizations transforming a pair of functions connected
     62 /// by an edge in the graph, do not invalidate a bottom-up traversal of the SCC
     63 /// DAG. That is, no optimizations will delete, remove, or add an edge such
     64 /// that functions already visited in a bottom-up order of the SCC DAG are no
     65 /// longer valid to have visited, or such that functions not yet visited in
     66 /// a bottom-up order of the SCC DAG are not required to have already been
     67 /// visited.
     68 ///
     69 /// Within this constraint, the desire is to minimize the merge points of the
     70 /// SCC DAG. The greater the fanout of the SCC DAG and the fewer merge points
     71 /// in the SCC DAG, the more independence there is in optimizing within it.
     72 /// There is a strong desire to enable parallelization of optimizations over
     73 /// the call graph, and both limited fanout and merge points will (artificially
     74 /// in some cases) limit the scaling of such an effort.
     75 ///
     76 /// To this end, graph represents both direct and any potential resolution to
     77 /// an indirect call edge. Another way to think about it is that it represents
     78 /// both the direct call edges and any direct call edges that might be formed
     79 /// through static optimizations. Specifically, it considers taking the address
     80 /// of a function to be an edge in the call graph because this might be
     81 /// forwarded to become a direct call by some subsequent function-local
     82 /// optimization. The result is that the graph closely follows the use-def
     83 /// edges for functions. Walking "up" the graph can be done by looking at all
     84 /// of the uses of a function.
     85 ///
     86 /// The roots of the call graph are the external functions and functions
     87 /// escaped into global variables. Those functions can be called from outside
     88 /// of the module or via unknowable means in the IR -- we may not be able to
     89 /// form even a potential call edge from a function body which may dynamically
     90 /// load the function and call it.
     91 ///
     92 /// This analysis still requires updates to remain valid after optimizations
     93 /// which could potentially change the set of potential callees. The
     94 /// constraints it operates under only make the traversal order remain valid.
     95 ///
     96 /// The entire analysis must be re-computed if full interprocedural
     97 /// optimizations run at any point. For example, globalopt completely
     98 /// invalidates the information in this analysis.
     99 ///
    100 /// FIXME: This class is named LazyCallGraph in a lame attempt to distinguish
    101 /// it from the existing CallGraph. At some point, it is expected that this
    102 /// will be the only call graph and it will be renamed accordingly.
    103 class LazyCallGraph {
    104 public:
    105   class Node;
    106   class SCC;
    107   typedef SmallVector<PointerUnion<Function *, Node *>, 4> NodeVectorT;
    108   typedef SmallVectorImpl<PointerUnion<Function *, Node *>> NodeVectorImplT;
    109 
    110   /// \brief A lazy iterator used for both the entry nodes and child nodes.
    111   ///
    112   /// When this iterator is dereferenced, if not yet available, a function will
    113   /// be scanned for "calls" or uses of functions and its child information
    114   /// will be constructed. All of these results are accumulated and cached in
    115   /// the graph.
    116   class iterator
    117       : public iterator_adaptor_base<iterator, NodeVectorImplT::iterator,
    118                                      std::forward_iterator_tag, Node> {
    119     friend class LazyCallGraph;
    120     friend class LazyCallGraph::Node;
    121 
    122     LazyCallGraph *G;
    123     NodeVectorImplT::iterator E;
    124 
    125     // Build the iterator for a specific position in a node list.
    126     iterator(LazyCallGraph &G, NodeVectorImplT::iterator NI,
    127              NodeVectorImplT::iterator E)
    128         : iterator_adaptor_base(NI), G(&G), E(E) {
    129       while (I != E && I->isNull())
    130         ++I;
    131     }
    132 
    133   public:
    134     iterator() {}
    135 
    136     using iterator_adaptor_base::operator++;
    137     iterator &operator++() {
    138       do {
    139         ++I;
    140       } while (I != E && I->isNull());
    141       return *this;
    142     }
    143 
    144     reference operator*() const {
    145       if (I->is<Node *>())
    146         return *I->get<Node *>();
    147 
    148       Function *F = I->get<Function *>();
    149       Node &ChildN = G->get(*F);
    150       *I = &ChildN;
    151       return ChildN;
    152     }
    153   };
    154 
    155   /// \brief A node in the call graph.
    156   ///
    157   /// This represents a single node. It's primary roles are to cache the list of
    158   /// callees, de-duplicate and provide fast testing of whether a function is
    159   /// a callee, and facilitate iteration of child nodes in the graph.
    160   class Node {
    161     friend class LazyCallGraph;
    162     friend class LazyCallGraph::SCC;
    163 
    164     LazyCallGraph *G;
    165     Function &F;
    166 
    167     // We provide for the DFS numbering and Tarjan walk lowlink numbers to be
    168     // stored directly within the node.
    169     int DFSNumber;
    170     int LowLink;
    171 
    172     mutable NodeVectorT Callees;
    173     DenseMap<Function *, size_t> CalleeIndexMap;
    174 
    175     /// \brief Basic constructor implements the scanning of F into Callees and
    176     /// CalleeIndexMap.
    177     Node(LazyCallGraph &G, Function &F);
    178 
    179     /// \brief Internal helper to insert a callee.
    180     void insertEdgeInternal(Function &Callee);
    181 
    182     /// \brief Internal helper to insert a callee.
    183     void insertEdgeInternal(Node &CalleeN);
    184 
    185     /// \brief Internal helper to remove a callee from this node.
    186     void removeEdgeInternal(Function &Callee);
    187 
    188   public:
    189     typedef LazyCallGraph::iterator iterator;
    190 
    191     Function &getFunction() const {
    192       return F;
    193     }
    194 
    195     iterator begin() const {
    196       return iterator(*G, Callees.begin(), Callees.end());
    197     }
    198     iterator end() const { return iterator(*G, Callees.end(), Callees.end()); }
    199 
    200     /// Equality is defined as address equality.
    201     bool operator==(const Node &N) const { return this == &N; }
    202     bool operator!=(const Node &N) const { return !operator==(N); }
    203   };
    204 
    205   /// \brief An SCC of the call graph.
    206   ///
    207   /// This represents a Strongly Connected Component of the call graph as
    208   /// a collection of call graph nodes. While the order of nodes in the SCC is
    209   /// stable, it is not any particular order.
    210   class SCC {
    211     friend class LazyCallGraph;
    212     friend class LazyCallGraph::Node;
    213 
    214     LazyCallGraph *G;
    215     SmallPtrSet<SCC *, 1> ParentSCCs;
    216     SmallVector<Node *, 1> Nodes;
    217 
    218     SCC(LazyCallGraph &G) : G(&G) {}
    219 
    220     void insert(Node &N);
    221 
    222     void
    223     internalDFS(SmallVectorImpl<std::pair<Node *, Node::iterator>> &DFSStack,
    224                 SmallVectorImpl<Node *> &PendingSCCStack, Node *N,
    225                 SmallVectorImpl<SCC *> &ResultSCCs);
    226 
    227   public:
    228     typedef SmallVectorImpl<Node *>::const_iterator iterator;
    229     typedef pointee_iterator<SmallPtrSet<SCC *, 1>::const_iterator> parent_iterator;
    230 
    231     iterator begin() const { return Nodes.begin(); }
    232     iterator end() const { return Nodes.end(); }
    233 
    234     parent_iterator parent_begin() const { return ParentSCCs.begin(); }
    235     parent_iterator parent_end() const { return ParentSCCs.end(); }
    236 
    237     iterator_range<parent_iterator> parents() const {
    238       return make_range(parent_begin(), parent_end());
    239     }
    240 
    241     /// \brief Test if this SCC is a parent of \a C.
    242     bool isParentOf(const SCC &C) const { return C.isChildOf(*this); }
    243 
    244     /// \brief Test if this SCC is an ancestor of \a C.
    245     bool isAncestorOf(const SCC &C) const { return C.isDescendantOf(*this); }
    246 
    247     /// \brief Test if this SCC is a child of \a C.
    248     bool isChildOf(const SCC &C) const {
    249       return ParentSCCs.count(const_cast<SCC *>(&C));
    250     }
    251 
    252     /// \brief Test if this SCC is a descendant of \a C.
    253     bool isDescendantOf(const SCC &C) const;
    254 
    255     /// \brief Short name useful for debugging or logging.
    256     ///
    257     /// We use the name of the first function in the SCC to name the SCC for
    258     /// the purposes of debugging and logging.
    259     StringRef getName() const { return (*begin())->getFunction().getName(); }
    260 
    261     ///@{
    262     /// \name Mutation API
    263     ///
    264     /// These methods provide the core API for updating the call graph in the
    265     /// presence of a (potentially still in-flight) DFS-found SCCs.
    266     ///
    267     /// Note that these methods sometimes have complex runtimes, so be careful
    268     /// how you call them.
    269 
    270     /// \brief Insert an edge from one node in this SCC to another in this SCC.
    271     ///
    272     /// By the definition of an SCC, this does not change the nature or make-up
    273     /// of any SCCs.
    274     void insertIntraSCCEdge(Node &CallerN, Node &CalleeN);
    275 
    276     /// \brief Insert an edge whose tail is in this SCC and head is in some
    277     /// child SCC.
    278     ///
    279     /// There must be an existing path from the caller to the callee. This
    280     /// operation is inexpensive and does not change the set of SCCs in the
    281     /// graph.
    282     void insertOutgoingEdge(Node &CallerN, Node &CalleeN);
    283 
    284     /// \brief Insert an edge whose tail is in a descendant SCC and head is in
    285     /// this SCC.
    286     ///
    287     /// There must be an existing path from the callee to the caller in this
    288     /// case. NB! This is has the potential to be a very expensive function. It
    289     /// inherently forms a cycle in the prior SCC DAG and we have to merge SCCs
    290     /// to resolve that cycle. But finding all of the SCCs which participate in
    291     /// the cycle can in the worst case require traversing every SCC in the
    292     /// graph. Every attempt is made to avoid that, but passes must still
    293     /// exercise caution calling this routine repeatedly.
    294     ///
    295     /// FIXME: We could possibly optimize this quite a bit for cases where the
    296     /// caller and callee are very nearby in the graph. See comments in the
    297     /// implementation for details, but that use case might impact users.
    298     SmallVector<SCC *, 1> insertIncomingEdge(Node &CallerN, Node &CalleeN);
    299 
    300     /// \brief Remove an edge whose source is in this SCC and target is *not*.
    301     ///
    302     /// This removes an inter-SCC edge. All inter-SCC edges originating from
    303     /// this SCC have been fully explored by any in-flight DFS SCC formation,
    304     /// so this is always safe to call once you have the source SCC.
    305     ///
    306     /// This operation does not change the set of SCCs or the members of the
    307     /// SCCs and so is very inexpensive. It may change the connectivity graph
    308     /// of the SCCs though, so be careful calling this while iterating over
    309     /// them.
    310     void removeInterSCCEdge(Node &CallerN, Node &CalleeN);
    311 
    312     /// \brief Remove an edge which is entirely within this SCC.
    313     ///
    314     /// Both the \a Caller and the \a Callee must be within this SCC. Removing
    315     /// such an edge make break cycles that form this SCC and thus this
    316     /// operation may change the SCC graph significantly. In particular, this
    317     /// operation will re-form new SCCs based on the remaining connectivity of
    318     /// the graph. The following invariants are guaranteed to hold after
    319     /// calling this method:
    320     ///
    321     /// 1) This SCC is still an SCC in the graph.
    322     /// 2) This SCC will be the parent of any new SCCs. Thus, this SCC is
    323     ///    preserved as the root of any new SCC directed graph formed.
    324     /// 3) No SCC other than this SCC has its member set changed (this is
    325     ///    inherent in the definition of removing such an edge).
    326     /// 4) All of the parent links of the SCC graph will be updated to reflect
    327     ///    the new SCC structure.
    328     /// 5) All SCCs formed out of this SCC, excluding this SCC, will be
    329     ///    returned in a vector.
    330     /// 6) The order of the SCCs in the vector will be a valid postorder
    331     ///    traversal of the new SCCs.
    332     ///
    333     /// These invariants are very important to ensure that we can build
    334     /// optimization pipeliens on top of the CGSCC pass manager which
    335     /// intelligently update the SCC graph without invalidating other parts of
    336     /// the SCC graph.
    337     ///
    338     /// The runtime complexity of this method is, in the worst case, O(V+E)
    339     /// where V is the number of nodes in this SCC and E is the number of edges
    340     /// leaving the nodes in this SCC. Note that E includes both edges within
    341     /// this SCC and edges from this SCC to child SCCs. Some effort has been
    342     /// made to minimize the overhead of common cases such as self-edges and
    343     /// edge removals which result in a spanning tree with no more cycles.
    344     SmallVector<SCC *, 1> removeIntraSCCEdge(Node &CallerN, Node &CalleeN);
    345 
    346     ///@}
    347   };
    348 
    349   /// \brief A post-order depth-first SCC iterator over the call graph.
    350   ///
    351   /// This iterator triggers the Tarjan DFS-based formation of the SCC DAG for
    352   /// the call graph, walking it lazily in depth-first post-order. That is, it
    353   /// always visits SCCs for a callee prior to visiting the SCC for a caller
    354   /// (when they are in different SCCs).
    355   class postorder_scc_iterator
    356       : public iterator_facade_base<postorder_scc_iterator,
    357                                     std::forward_iterator_tag, SCC> {
    358     friend class LazyCallGraph;
    359     friend class LazyCallGraph::Node;
    360 
    361     /// \brief Nonce type to select the constructor for the end iterator.
    362     struct IsAtEndT {};
    363 
    364     LazyCallGraph *G;
    365     SCC *C;
    366 
    367     // Build the begin iterator for a node.
    368     postorder_scc_iterator(LazyCallGraph &G) : G(&G) {
    369       C = G.getNextSCCInPostOrder();
    370     }
    371 
    372     // Build the end iterator for a node. This is selected purely by overload.
    373     postorder_scc_iterator(LazyCallGraph &G, IsAtEndT /*Nonce*/)
    374         : G(&G), C(nullptr) {}
    375 
    376   public:
    377     bool operator==(const postorder_scc_iterator &Arg) const {
    378       return G == Arg.G && C == Arg.C;
    379     }
    380 
    381     reference operator*() const { return *C; }
    382 
    383     using iterator_facade_base::operator++;
    384     postorder_scc_iterator &operator++() {
    385       C = G->getNextSCCInPostOrder();
    386       return *this;
    387     }
    388   };
    389 
    390   /// \brief Construct a graph for the given module.
    391   ///
    392   /// This sets up the graph and computes all of the entry points of the graph.
    393   /// No function definitions are scanned until their nodes in the graph are
    394   /// requested during traversal.
    395   LazyCallGraph(Module &M);
    396 
    397   LazyCallGraph(LazyCallGraph &&G);
    398   LazyCallGraph &operator=(LazyCallGraph &&RHS);
    399 
    400   iterator begin() {
    401     return iterator(*this, EntryNodes.begin(), EntryNodes.end());
    402   }
    403   iterator end() { return iterator(*this, EntryNodes.end(), EntryNodes.end()); }
    404 
    405   postorder_scc_iterator postorder_scc_begin() {
    406     return postorder_scc_iterator(*this);
    407   }
    408   postorder_scc_iterator postorder_scc_end() {
    409     return postorder_scc_iterator(*this, postorder_scc_iterator::IsAtEndT());
    410   }
    411 
    412   iterator_range<postorder_scc_iterator> postorder_sccs() {
    413     return make_range(postorder_scc_begin(), postorder_scc_end());
    414   }
    415 
    416   /// \brief Lookup a function in the graph which has already been scanned and
    417   /// added.
    418   Node *lookup(const Function &F) const { return NodeMap.lookup(&F); }
    419 
    420   /// \brief Lookup a function's SCC in the graph.
    421   ///
    422   /// \returns null if the function hasn't been assigned an SCC via the SCC
    423   /// iterator walk.
    424   SCC *lookupSCC(Node &N) const { return SCCMap.lookup(&N); }
    425 
    426   /// \brief Get a graph node for a given function, scanning it to populate the
    427   /// graph data as necessary.
    428   Node &get(Function &F) {
    429     Node *&N = NodeMap[&F];
    430     if (N)
    431       return *N;
    432 
    433     return insertInto(F, N);
    434   }
    435 
    436   ///@{
    437   /// \name Pre-SCC Mutation API
    438   ///
    439   /// These methods are only valid to call prior to forming any SCCs for this
    440   /// call graph. They can be used to update the core node-graph during
    441   /// a node-based inorder traversal that precedes any SCC-based traversal.
    442   ///
    443   /// Once you begin manipulating a call graph's SCCs, you must perform all
    444   /// mutation of the graph via the SCC methods.
    445 
    446   /// \brief Update the call graph after inserting a new edge.
    447   void insertEdge(Node &Caller, Function &Callee);
    448 
    449   /// \brief Update the call graph after inserting a new edge.
    450   void insertEdge(Function &Caller, Function &Callee) {
    451     return insertEdge(get(Caller), Callee);
    452   }
    453 
    454   /// \brief Update the call graph after deleting an edge.
    455   void removeEdge(Node &Caller, Function &Callee);
    456 
    457   /// \brief Update the call graph after deleting an edge.
    458   void removeEdge(Function &Caller, Function &Callee) {
    459     return removeEdge(get(Caller), Callee);
    460   }
    461 
    462   ///@}
    463 
    464 private:
    465   /// \brief Allocator that holds all the call graph nodes.
    466   SpecificBumpPtrAllocator<Node> BPA;
    467 
    468   /// \brief Maps function->node for fast lookup.
    469   DenseMap<const Function *, Node *> NodeMap;
    470 
    471   /// \brief The entry nodes to the graph.
    472   ///
    473   /// These nodes are reachable through "external" means. Put another way, they
    474   /// escape at the module scope.
    475   NodeVectorT EntryNodes;
    476 
    477   /// \brief Map of the entry nodes in the graph to their indices in
    478   /// \c EntryNodes.
    479   DenseMap<Function *, size_t> EntryIndexMap;
    480 
    481   /// \brief Allocator that holds all the call graph SCCs.
    482   SpecificBumpPtrAllocator<SCC> SCCBPA;
    483 
    484   /// \brief Maps Function -> SCC for fast lookup.
    485   DenseMap<Node *, SCC *> SCCMap;
    486 
    487   /// \brief The leaf SCCs of the graph.
    488   ///
    489   /// These are all of the SCCs which have no children.
    490   SmallVector<SCC *, 4> LeafSCCs;
    491 
    492   /// \brief Stack of nodes in the DFS walk.
    493   SmallVector<std::pair<Node *, iterator>, 4> DFSStack;
    494 
    495   /// \brief Set of entry nodes not-yet-processed into SCCs.
    496   SmallVector<Function *, 4> SCCEntryNodes;
    497 
    498   /// \brief Stack of nodes the DFS has walked but not yet put into a SCC.
    499   SmallVector<Node *, 4> PendingSCCStack;
    500 
    501   /// \brief Counter for the next DFS number to assign.
    502   int NextDFSNumber;
    503 
    504   /// \brief Helper to insert a new function, with an already looked-up entry in
    505   /// the NodeMap.
    506   Node &insertInto(Function &F, Node *&MappedN);
    507 
    508   /// \brief Helper to update pointers back to the graph object during moves.
    509   void updateGraphPtrs();
    510 
    511   /// \brief Helper to form a new SCC out of the top of a DFSStack-like
    512   /// structure.
    513   SCC *formSCC(Node *RootN, SmallVectorImpl<Node *> &NodeStack);
    514 
    515   /// \brief Retrieve the next node in the post-order SCC walk of the call graph.
    516   SCC *getNextSCCInPostOrder();
    517 };
    518 
    519 // Provide GraphTraits specializations for call graphs.
    520 template <> struct GraphTraits<LazyCallGraph::Node *> {
    521   typedef LazyCallGraph::Node NodeType;
    522   typedef LazyCallGraph::iterator ChildIteratorType;
    523 
    524   static NodeType *getEntryNode(NodeType *N) { return N; }
    525   static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
    526   static ChildIteratorType child_end(NodeType *N) { return N->end(); }
    527 };
    528 template <> struct GraphTraits<LazyCallGraph *> {
    529   typedef LazyCallGraph::Node NodeType;
    530   typedef LazyCallGraph::iterator ChildIteratorType;
    531 
    532   static NodeType *getEntryNode(NodeType *N) { return N; }
    533   static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
    534   static ChildIteratorType child_end(NodeType *N) { return N->end(); }
    535 };
    536 
    537 /// \brief An analysis pass which computes the call graph for a module.
    538 class LazyCallGraphAnalysis {
    539 public:
    540   /// \brief Inform generic clients of the result type.
    541   typedef LazyCallGraph Result;
    542 
    543   static void *ID() { return (void *)&PassID; }
    544 
    545   static StringRef name() { return "Lazy CallGraph Analysis"; }
    546 
    547   /// \brief Compute the \c LazyCallGraph for the module \c M.
    548   ///
    549   /// This just builds the set of entry points to the call graph. The rest is
    550   /// built lazily as it is walked.
    551   LazyCallGraph run(Module &M) { return LazyCallGraph(M); }
    552 
    553 private:
    554   static char PassID;
    555 };
    556 
    557 /// \brief A pass which prints the call graph to a \c raw_ostream.
    558 ///
    559 /// This is primarily useful for testing the analysis.
    560 class LazyCallGraphPrinterPass {
    561   raw_ostream &OS;
    562 
    563 public:
    564   explicit LazyCallGraphPrinterPass(raw_ostream &OS);
    565 
    566   PreservedAnalyses run(Module &M, ModuleAnalysisManager *AM);
    567 
    568   static StringRef name() { return "LazyCallGraphPrinterPass"; }
    569 };
    570 
    571 }
    572 
    573 #endif
    574