Home | History | Annotate | Download | only in Analysis 
      1 //== CallGraph.h - AST-based 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 file declares the AST-based CallGraph.
     11 //
     12 //  A call graph for functions whose definitions/bodies are available in the
     13 //  current translation unit. The graph has a "virtual" root node that contains
     14 //  edges to all externally available functions.
     15 //===----------------------------------------------------------------------===//
     16 
     17 #ifndef LLVM_CLANG_ANALYSIS_CALLGRAPH
     18 #define LLVM_CLANG_ANALYSIS_CALLGRAPH
     19 
     20 #include "clang/AST/DeclBase.h"
     21 #include "clang/AST/RecursiveASTVisitor.h"
     22 #include "llvm/ADT/DenseMap.h"
     23 #include "llvm/ADT/GraphTraits.h"
     24 #include "llvm/ADT/SetVector.h"
     25 
     26 namespace clang {
     27 class CallGraphNode;
     28 
     29 /// \class The AST-based call graph.
     30 ///
     31 /// The call graph extends itself with the given declarations by implementing
     32 /// the recursive AST visitor, which constructs the graph by visiting the given
     33 /// declarations.
     34 class CallGraph : public RecursiveASTVisitor<CallGraph> {
     35   friend class CallGraphNode;
     36 
     37   typedef llvm::DenseMap<const Decl *, CallGraphNode *> FunctionMapTy;
     38 
     39   /// FunctionMap owns all CallGraphNodes.
     40   FunctionMapTy FunctionMap;
     41 
     42   /// This is a virtual root node that has edges to all the global functions -
     43   /// 'main' or functions accessible from other translation units.
     44   CallGraphNode *Root;
     45 
     46   /// The list of nodes that have no parent. These are unreachable from Root.
     47   /// Declarations can get to this list due to impressions in the graph, for
     48   /// example, we do not track functions whose addresses were taken.
     49   llvm::SetVector<CallGraphNode *> ParentlessNodes;
     50 
     51 public:
     52   CallGraph();
     53   ~CallGraph();
     54 
     55   /// \brief Populate the call graph with the functions in the given
     56   /// declaration.
     57   ///
     58   /// Recursively walks the declaration to find all the dependent Decls as well.
     59   void addToCallGraph(Decl *D) {
     60     TraverseDecl(D);
     61   }
     62 
     63   /// \brief Determine if a declaration should be included in the graph.
     64   static bool includeInGraph(const Decl *D);
     65 
     66   /// \brief Lookup the node for the given declaration.
     67   CallGraphNode *getNode(const Decl *) const;
     68 
     69   /// \brief Lookup the node for the given declaration. If none found, insert
     70   /// one into the graph.
     71   CallGraphNode *getOrInsertNode(Decl *);
     72 
     73   /// Iterators through all the elements in the graph. Note, this gives
     74   /// non-deterministic order.
     75   typedef FunctionMapTy::iterator iterator;
     76   typedef FunctionMapTy::const_iterator const_iterator;
     77   iterator begin() { return FunctionMap.begin(); }
     78   iterator end()   { return FunctionMap.end();   }
     79   const_iterator begin() const { return FunctionMap.begin(); }
     80   const_iterator end()   const { return FunctionMap.end();   }
     81 
     82   /// \brief Get the number of nodes in the graph.
     83   unsigned size() const { return FunctionMap.size(); }
     84 
     85   /// \ brief Get the virtual root of the graph, all the functions available
     86   /// externally are represented as callees of the node.
     87   CallGraphNode *getRoot() const { return Root; }
     88 
     89   /// Iterators through all the nodes of the graph that have no parent. These
     90   /// are the unreachable nodes, which are either unused or are due to us
     91   /// failing to add a call edge due to the analysis imprecision.
     92   typedef llvm::SetVector<CallGraphNode *>::iterator nodes_iterator;
     93   typedef llvm::SetVector<CallGraphNode *>::const_iterator const_nodes_iterator;
     94   nodes_iterator parentless_begin() { return ParentlessNodes.begin(); }
     95   nodes_iterator parentless_end() { return ParentlessNodes.end(); }
     96   const_nodes_iterator
     97     parentless_begin() const { return ParentlessNodes.begin(); }
     98   const_nodes_iterator
     99     parentless_end() const { return ParentlessNodes.end(); }
    100 
    101   void print(raw_ostream &os) const;
    102   void dump() const;
    103   void viewGraph() const;
    104 
    105   /// Part of recursive declaration visitation.
    106   bool VisitFunctionDecl(FunctionDecl *FD) {
    107     // We skip function template definitions, as their semantics is
    108     // only determined when they are instantiated.
    109     if (includeInGraph(FD))
    110       // If this function has external linkage, anything could call it.
    111       // Note, we are not precise here. For example, the function could have
    112       // its address taken.
    113       addNodeForDecl(FD, FD->isGlobal());
    114     return true;
    115   }
    116 
    117   /// Part of recursive declaration visitation.
    118   bool VisitObjCMethodDecl(ObjCMethodDecl *MD) {
    119     if (includeInGraph(MD))
    120       addNodeForDecl(MD, true);
    121     return true;
    122   }
    123 
    124 private:
    125   /// \brief Add the given declaration to the call graph.
    126   void addNodeForDecl(Decl *D, bool IsGlobal);
    127 
    128   /// \brief Allocate a new node in the graph.
    129   CallGraphNode *allocateNewNode(Decl *);
    130 };
    131 
    132 class CallGraphNode {
    133 public:
    134   typedef CallGraphNode* CallRecord;
    135 
    136 private:
    137   /// \brief The function/method declaration.
    138   Decl *FD;
    139 
    140   /// \brief The list of functions called from this node.
    141   // Small vector might be more efficient since we are only tracking functions
    142   // whose definition is in the current TU.
    143   llvm::SmallVector<CallRecord, 5> CalledFunctions;
    144 
    145 public:
    146   CallGraphNode(Decl *D) : FD(D) {}
    147 
    148   typedef llvm::SmallVector<CallRecord, 5>::iterator iterator;
    149   typedef llvm::SmallVector<CallRecord, 5>::const_iterator const_iterator;
    150 
    151   /// Iterators through all the callees/children of the node.
    152   inline iterator begin() { return CalledFunctions.begin(); }
    153   inline iterator end()   { return CalledFunctions.end(); }
    154   inline const_iterator begin() const { return CalledFunctions.begin(); }
    155   inline const_iterator end()   const { return CalledFunctions.end();   }
    156 
    157   inline bool empty() const {return CalledFunctions.empty(); }
    158   inline unsigned size() const {return CalledFunctions.size(); }
    159 
    160   void addCallee(CallGraphNode *N, CallGraph *CG) {
    161     CalledFunctions.push_back(N);
    162     CG->ParentlessNodes.remove(N);
    163   }
    164 
    165   Decl *getDecl() const { return FD; }
    166 
    167   StringRef getName() const;
    168 
    169   void print(raw_ostream &os) const;
    170   void dump() const;
    171 };
    172 
    173 } // end clang namespace
    174 
    175 // Graph traits for iteration, viewing.
    176 namespace llvm {
    177 template <> struct GraphTraits<clang::CallGraphNode*> {
    178   typedef clang::CallGraphNode NodeType;
    179   typedef clang::CallGraphNode::CallRecord CallRecordTy;
    180   typedef std::pointer_to_unary_function<CallRecordTy,
    181                                          clang::CallGraphNode*> CGNDerefFun;
    182   static NodeType *getEntryNode(clang::CallGraphNode *CGN) { return CGN; }
    183   typedef mapped_iterator<NodeType::iterator, CGNDerefFun> ChildIteratorType;
    184   static inline ChildIteratorType child_begin(NodeType *N) {
    185     return map_iterator(N->begin(), CGNDerefFun(CGNDeref));
    186   }
    187   static inline ChildIteratorType child_end  (NodeType *N) {
    188     return map_iterator(N->end(), CGNDerefFun(CGNDeref));
    189   }
    190   static clang::CallGraphNode *CGNDeref(CallRecordTy P) {
    191     return P;
    192   }
    193 };
    194 
    195 template <> struct GraphTraits<const clang::CallGraphNode*> {
    196   typedef const clang::CallGraphNode NodeType;
    197   typedef NodeType::const_iterator ChildIteratorType;
    198   static NodeType *getEntryNode(const clang::CallGraphNode *CGN) { return CGN; }
    199   static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();}
    200   static inline ChildIteratorType child_end  (NodeType *N) { return N->end(); }
    201 };
    202 
    203 template <> struct GraphTraits<clang::CallGraph*>
    204   : public GraphTraits<clang::CallGraphNode*> {
    205 
    206   static NodeType *getEntryNode(clang::CallGraph *CGN) {
    207     return CGN->getRoot();  // Start at the external node!
    208   }
    209   typedef std::pair<const clang::Decl*, clang::CallGraphNode*> PairTy;
    210   typedef std::pointer_to_unary_function<PairTy, clang::CallGraphNode&> DerefFun;
    211   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
    212   typedef mapped_iterator<clang::CallGraph::iterator, DerefFun> nodes_iterator;
    213 
    214   static nodes_iterator nodes_begin(clang::CallGraph *CG) {
    215     return map_iterator(CG->begin(), DerefFun(CGdereference));
    216   }
    217   static nodes_iterator nodes_end  (clang::CallGraph *CG) {
    218     return map_iterator(CG->end(), DerefFun(CGdereference));
    219   }
    220   static clang::CallGraphNode &CGdereference(PairTy P) {
    221     return *(P.second);
    222   }
    223 
    224   static unsigned size(clang::CallGraph *CG) {
    225     return CG->size();
    226   }
    227 };
    228 
    229 template <> struct GraphTraits<const clang::CallGraph*> :
    230   public GraphTraits<const clang::CallGraphNode*> {
    231   static NodeType *getEntryNode(const clang::CallGraph *CGN) {
    232     return CGN->getRoot();
    233   }
    234   typedef std::pair<const clang::Decl*, clang::CallGraphNode*> PairTy;
    235   typedef std::pointer_to_unary_function<PairTy, clang::CallGraphNode&> DerefFun;
    236   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
    237   typedef mapped_iterator<clang::CallGraph::const_iterator,
    238                           DerefFun> nodes_iterator;
    239 
    240   static nodes_iterator nodes_begin(const clang::CallGraph *CG) {
    241     return map_iterator(CG->begin(), DerefFun(CGdereference));
    242   }
    243   static nodes_iterator nodes_end(const clang::CallGraph *CG) {
    244     return map_iterator(CG->end(), DerefFun(CGdereference));
    245   }
    246   static clang::CallGraphNode &CGdereference(PairTy P) {
    247     return *(P.second);
    248   }
    249 
    250   static unsigned size(const clang::CallGraph *CG) {
    251     return CG->size();
    252   }
    253 };
    254 
    255 } // end llvm namespace
    256 
    257 #endif
    258