Home | History | Annotate | Download | only in Analysis
      1 //===- CallGraph.h - Build 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 //
     10 // This interface is used to build and manipulate a call graph, which is a very
     11 // useful tool for interprocedural optimization.
     12 //
     13 // Every function in a module is represented as a node in the call graph.  The
     14 // callgraph node keeps track of which functions the are called by the function
     15 // corresponding to the node.
     16 //
     17 // A call graph may contain nodes where the function that they correspond to is
     18 // null.  These 'external' nodes are used to represent control flow that is not
     19 // represented (or analyzable) in the module.  In particular, this analysis
     20 // builds one external node such that:
     21 //   1. All functions in the module without internal linkage will have edges
     22 //      from this external node, indicating that they could be called by
     23 //      functions outside of the module.
     24 //   2. All functions whose address is used for something more than a direct
     25 //      call, for example being stored into a memory location will also have an
     26 //      edge from this external node.  Since they may be called by an unknown
     27 //      caller later, they must be tracked as such.
     28 //
     29 // There is a second external node added for calls that leave this module.
     30 // Functions have a call edge to the external node iff:
     31 //   1. The function is external, reflecting the fact that they could call
     32 //      anything without internal linkage or that has its address taken.
     33 //   2. The function contains an indirect function call.
     34 //
     35 // As an extension in the future, there may be multiple nodes with a null
     36 // function.  These will be used when we can prove (through pointer analysis)
     37 // that an indirect call site can call only a specific set of functions.
     38 //
     39 // Because of these properties, the CallGraph captures a conservative superset
     40 // of all of the caller-callee relationships, which is useful for
     41 // transformations.
     42 //
     43 // The CallGraph class also attempts to figure out what the root of the
     44 // CallGraph is, which it currently does by looking for a function named 'main'.
     45 // If no function named 'main' is found, the external node is used as the entry
     46 // node, reflecting the fact that any function without internal linkage could
     47 // be called into (which is common for libraries).
     48 //
     49 //===----------------------------------------------------------------------===//
     50 
     51 #ifndef LLVM_ANALYSIS_CALLGRAPH_H
     52 #define LLVM_ANALYSIS_CALLGRAPH_H
     53 
     54 #include "llvm/ADT/GraphTraits.h"
     55 #include "llvm/ADT/STLExtras.h"
     56 #include "llvm/IR/Function.h"
     57 #include "llvm/Pass.h"
     58 #include "llvm/Support/CallSite.h"
     59 #include "llvm/Support/IncludeFile.h"
     60 #include "llvm/Support/ValueHandle.h"
     61 #include <map>
     62 
     63 namespace llvm {
     64 
     65 class Function;
     66 class Module;
     67 class CallGraphNode;
     68 
     69 //===----------------------------------------------------------------------===//
     70 // CallGraph class definition
     71 //
     72 class CallGraph {
     73 protected:
     74   Module *Mod;              // The module this call graph represents
     75 
     76   typedef std::map<const Function *, CallGraphNode *> FunctionMapTy;
     77   FunctionMapTy FunctionMap;    // Map from a function to its node
     78 
     79 public:
     80   static char ID; // Class identification, replacement for typeinfo
     81   //===---------------------------------------------------------------------
     82   // Accessors.
     83   //
     84   typedef FunctionMapTy::iterator iterator;
     85   typedef FunctionMapTy::const_iterator const_iterator;
     86 
     87   /// getModule - Return the module the call graph corresponds to.
     88   ///
     89   Module &getModule() const { return *Mod; }
     90 
     91   inline       iterator begin()       { return FunctionMap.begin(); }
     92   inline       iterator end()         { return FunctionMap.end();   }
     93   inline const_iterator begin() const { return FunctionMap.begin(); }
     94   inline const_iterator end()   const { return FunctionMap.end();   }
     95 
     96   // Subscripting operators, return the call graph node for the provided
     97   // function
     98   inline const CallGraphNode *operator[](const Function *F) const {
     99     const_iterator I = FunctionMap.find(F);
    100     assert(I != FunctionMap.end() && "Function not in callgraph!");
    101     return I->second;
    102   }
    103   inline CallGraphNode *operator[](const Function *F) {
    104     const_iterator I = FunctionMap.find(F);
    105     assert(I != FunctionMap.end() && "Function not in callgraph!");
    106     return I->second;
    107   }
    108 
    109   /// Returns the CallGraphNode which is used to represent undetermined calls
    110   /// into the callgraph.  Override this if you want behavioral inheritance.
    111   virtual CallGraphNode* getExternalCallingNode() const { return 0; }
    112   virtual CallGraphNode* getCallsExternalNode()   const { return 0; }
    113 
    114   /// Return the root/main method in the module, or some other root node, such
    115   /// as the externalcallingnode.  Overload these if you behavioral
    116   /// inheritance.
    117   virtual CallGraphNode* getRoot() { return 0; }
    118   virtual const CallGraphNode* getRoot() const { return 0; }
    119 
    120   //===---------------------------------------------------------------------
    121   // Functions to keep a call graph up to date with a function that has been
    122   // modified.
    123   //
    124 
    125   /// removeFunctionFromModule - Unlink the function from this module, returning
    126   /// it.  Because this removes the function from the module, the call graph
    127   /// node is destroyed.  This is only valid if the function does not call any
    128   /// other functions (ie, there are no edges in it's CGN).  The easiest way to
    129   /// do this is to dropAllReferences before calling this.
    130   ///
    131   Function *removeFunctionFromModule(CallGraphNode *CGN);
    132   Function *removeFunctionFromModule(Function *F) {
    133     return removeFunctionFromModule((*this)[F]);
    134   }
    135 
    136   /// getOrInsertFunction - This method is identical to calling operator[], but
    137   /// it will insert a new CallGraphNode for the specified function if one does
    138   /// not already exist.
    139   CallGraphNode *getOrInsertFunction(const Function *F);
    140 
    141   /// spliceFunction - Replace the function represented by this node by another.
    142   /// This does not rescan the body of the function, so it is suitable when
    143   /// splicing the body of one function to another while also updating all
    144   /// callers from the old function to the new.
    145   ///
    146   void spliceFunction(const Function *From, const Function *To);
    147 
    148   //===---------------------------------------------------------------------
    149   // Pass infrastructure interface glue code.
    150   //
    151 protected:
    152   CallGraph() {}
    153 
    154 public:
    155   virtual ~CallGraph() { destroy(); }
    156 
    157   /// initialize - Call this method before calling other methods,
    158   /// re/initializes the state of the CallGraph.
    159   ///
    160   void initialize(Module &M);
    161 
    162   void print(raw_ostream &o, Module *) const;
    163   void dump() const;
    164 protected:
    165   // destroy - Release memory for the call graph
    166   virtual void destroy();
    167 };
    168 
    169 //===----------------------------------------------------------------------===//
    170 // CallGraphNode class definition.
    171 //
    172 class CallGraphNode {
    173   friend class CallGraph;
    174 
    175   AssertingVH<Function> F;
    176 
    177   // CallRecord - This is a pair of the calling instruction (a call or invoke)
    178   // and the callgraph node being called.
    179 public:
    180   typedef std::pair<WeakVH, CallGraphNode*> CallRecord;
    181 private:
    182   std::vector<CallRecord> CalledFunctions;
    183 
    184   /// NumReferences - This is the number of times that this CallGraphNode occurs
    185   /// in the CalledFunctions array of this or other CallGraphNodes.
    186   unsigned NumReferences;
    187 
    188   CallGraphNode(const CallGraphNode &) LLVM_DELETED_FUNCTION;
    189   void operator=(const CallGraphNode &) LLVM_DELETED_FUNCTION;
    190 
    191   void DropRef() { --NumReferences; }
    192   void AddRef() { ++NumReferences; }
    193 public:
    194   typedef std::vector<CallRecord> CalledFunctionsVector;
    195 
    196 
    197   // CallGraphNode ctor - Create a node for the specified function.
    198   inline CallGraphNode(Function *f) : F(f), NumReferences(0) {}
    199   ~CallGraphNode() {
    200     assert(NumReferences == 0 && "Node deleted while references remain");
    201   }
    202 
    203   //===---------------------------------------------------------------------
    204   // Accessor methods.
    205   //
    206 
    207   typedef std::vector<CallRecord>::iterator iterator;
    208   typedef std::vector<CallRecord>::const_iterator const_iterator;
    209 
    210   // getFunction - Return the function that this call graph node represents.
    211   Function *getFunction() const { return F; }
    212 
    213   inline iterator begin() { return CalledFunctions.begin(); }
    214   inline iterator end()   { return CalledFunctions.end();   }
    215   inline const_iterator begin() const { return CalledFunctions.begin(); }
    216   inline const_iterator end()   const { return CalledFunctions.end();   }
    217   inline bool empty() const { return CalledFunctions.empty(); }
    218   inline unsigned size() const { return (unsigned)CalledFunctions.size(); }
    219 
    220   /// getNumReferences - Return the number of other CallGraphNodes in this
    221   /// CallGraph that reference this node in their callee list.
    222   unsigned getNumReferences() const { return NumReferences; }
    223 
    224   // Subscripting operator - Return the i'th called function.
    225   //
    226   CallGraphNode *operator[](unsigned i) const {
    227     assert(i < CalledFunctions.size() && "Invalid index");
    228     return CalledFunctions[i].second;
    229   }
    230 
    231   /// dump - Print out this call graph node.
    232   ///
    233   void dump() const;
    234   void print(raw_ostream &OS) const;
    235 
    236   //===---------------------------------------------------------------------
    237   // Methods to keep a call graph up to date with a function that has been
    238   // modified
    239   //
    240 
    241   /// removeAllCalledFunctions - As the name implies, this removes all edges
    242   /// from this CallGraphNode to any functions it calls.
    243   void removeAllCalledFunctions() {
    244     while (!CalledFunctions.empty()) {
    245       CalledFunctions.back().second->DropRef();
    246       CalledFunctions.pop_back();
    247     }
    248   }
    249 
    250   /// stealCalledFunctionsFrom - Move all the callee information from N to this
    251   /// node.
    252   void stealCalledFunctionsFrom(CallGraphNode *N) {
    253     assert(CalledFunctions.empty() &&
    254            "Cannot steal callsite information if I already have some");
    255     std::swap(CalledFunctions, N->CalledFunctions);
    256   }
    257 
    258 
    259   /// addCalledFunction - Add a function to the list of functions called by this
    260   /// one.
    261   void addCalledFunction(CallSite CS, CallGraphNode *M) {
    262     assert(!CS.getInstruction() ||
    263            !CS.getCalledFunction() ||
    264            !CS.getCalledFunction()->isIntrinsic());
    265     CalledFunctions.push_back(std::make_pair(CS.getInstruction(), M));
    266     M->AddRef();
    267   }
    268 
    269   void removeCallEdge(iterator I) {
    270     I->second->DropRef();
    271     *I = CalledFunctions.back();
    272     CalledFunctions.pop_back();
    273   }
    274 
    275 
    276   /// removeCallEdgeFor - This method removes the edge in the node for the
    277   /// specified call site.  Note that this method takes linear time, so it
    278   /// should be used sparingly.
    279   void removeCallEdgeFor(CallSite CS);
    280 
    281   /// removeAnyCallEdgeTo - This method removes all call edges from this node
    282   /// to the specified callee function.  This takes more time to execute than
    283   /// removeCallEdgeTo, so it should not be used unless necessary.
    284   void removeAnyCallEdgeTo(CallGraphNode *Callee);
    285 
    286   /// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite
    287   /// from this node to the specified callee function.
    288   void removeOneAbstractEdgeTo(CallGraphNode *Callee);
    289 
    290   /// replaceCallEdge - This method replaces the edge in the node for the
    291   /// specified call site with a new one.  Note that this method takes linear
    292   /// time, so it should be used sparingly.
    293   void replaceCallEdge(CallSite CS, CallSite NewCS, CallGraphNode *NewNode);
    294 
    295   /// allReferencesDropped - This is a special function that should only be
    296   /// used by the CallGraph class.
    297   void allReferencesDropped() {
    298     NumReferences = 0;
    299   }
    300 };
    301 
    302 //===----------------------------------------------------------------------===//
    303 // GraphTraits specializations for call graphs so that they can be treated as
    304 // graphs by the generic graph algorithms.
    305 //
    306 
    307 // Provide graph traits for tranversing call graphs using standard graph
    308 // traversals.
    309 template <> struct GraphTraits<CallGraphNode*> {
    310   typedef CallGraphNode NodeType;
    311 
    312   typedef CallGraphNode::CallRecord CGNPairTy;
    313   typedef std::pointer_to_unary_function<CGNPairTy, CallGraphNode*> CGNDerefFun;
    314 
    315   static NodeType *getEntryNode(CallGraphNode *CGN) { return CGN; }
    316 
    317   typedef mapped_iterator<NodeType::iterator, CGNDerefFun> ChildIteratorType;
    318 
    319   static inline ChildIteratorType child_begin(NodeType *N) {
    320     return map_iterator(N->begin(), CGNDerefFun(CGNDeref));
    321   }
    322   static inline ChildIteratorType child_end  (NodeType *N) {
    323     return map_iterator(N->end(), CGNDerefFun(CGNDeref));
    324   }
    325 
    326   static CallGraphNode *CGNDeref(CGNPairTy P) {
    327     return P.second;
    328   }
    329 
    330 };
    331 
    332 template <> struct GraphTraits<const CallGraphNode*> {
    333   typedef const CallGraphNode NodeType;
    334   typedef NodeType::const_iterator ChildIteratorType;
    335 
    336   static NodeType *getEntryNode(const CallGraphNode *CGN) { return CGN; }
    337   static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();}
    338   static inline ChildIteratorType child_end  (NodeType *N) { return N->end(); }
    339 };
    340 
    341 template<> struct GraphTraits<CallGraph*> : public GraphTraits<CallGraphNode*> {
    342   static NodeType *getEntryNode(CallGraph *CGN) {
    343     return CGN->getExternalCallingNode();  // Start at the external node!
    344   }
    345   typedef std::pair<const Function*, CallGraphNode*> PairTy;
    346   typedef std::pointer_to_unary_function<PairTy, CallGraphNode&> DerefFun;
    347 
    348   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
    349   typedef mapped_iterator<CallGraph::iterator, DerefFun> nodes_iterator;
    350   static nodes_iterator nodes_begin(CallGraph *CG) {
    351     return map_iterator(CG->begin(), DerefFun(CGdereference));
    352   }
    353   static nodes_iterator nodes_end  (CallGraph *CG) {
    354     return map_iterator(CG->end(), DerefFun(CGdereference));
    355   }
    356 
    357   static CallGraphNode &CGdereference(PairTy P) {
    358     return *P.second;
    359   }
    360 };
    361 
    362 template<> struct GraphTraits<const CallGraph*> :
    363   public GraphTraits<const CallGraphNode*> {
    364   static NodeType *getEntryNode(const CallGraph *CGN) {
    365     return CGN->getExternalCallingNode();
    366   }
    367   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
    368   typedef CallGraph::const_iterator nodes_iterator;
    369   static nodes_iterator nodes_begin(const CallGraph *CG) { return CG->begin(); }
    370   static nodes_iterator nodes_end  (const CallGraph *CG) { return CG->end(); }
    371 };
    372 
    373 } // End llvm namespace
    374 
    375 // Make sure that any clients of this file link in CallGraph.cpp
    376 FORCE_DEFINING_FILE_TO_BE_LINKED(CallGraph)
    377 
    378 #endif
    379