contrib/llvm/tools/clang/include/clang/Analysis/CallGraph.h

   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 /// \brief 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 functions.
  43   CallGraphNode *Root;
  44
  45 public:
  46   CallGraph();
  47   ~CallGraph();
  48
  49   /// \brief Populate the call graph with the functions in the given
  50   /// declaration.
  51   ///
  52   /// Recursively walks the declaration to find all the dependent Decls as well.
  53   void addToCallGraph(Decl *D) {
  54     TraverseDecl(D);
  55   }
  56
  57   /// \brief Determine if a declaration should be included in the graph.
  58   static bool includeInGraph(const Decl *D);
  59
  60   /// \brief Lookup the node for the given declaration.
  61   CallGraphNode *getNode(const Decl *) const;
  62
  63   /// \brief Lookup the node for the given declaration. If none found, insert
  64   /// one into the graph.
  65   CallGraphNode *getOrInsertNode(Decl *);
  66
  67   /// Iterators through all the elements in the graph. Note, this gives
  68   /// non-deterministic order.
  69   typedef FunctionMapTy::iterator iterator;
  70   typedef FunctionMapTy::const_iterator const_iterator;
  71   iterator begin() { return FunctionMap.begin(); }
  72   iterator end()   { return FunctionMap.end();   }
  73   const_iterator begin() const { return FunctionMap.begin(); }
  74   const_iterator end()   const { return FunctionMap.end();   }
  75
  76   /// \brief Get the number of nodes in the graph.
  77   unsigned size() const { return FunctionMap.size(); }
  78
  79   /// \ brief Get the virtual root of the graph, all the functions available
  80   /// externally are represented as callees of the node.
  81   CallGraphNode *getRoot() const { return Root; }
  82
  83   /// Iterators through all the nodes of the graph that have no parent. These
  84   /// are the unreachable nodes, which are either unused or are due to us
  85   /// failing to add a call edge due to the analysis imprecision.
  86   typedef llvm::SetVector<CallGraphNode *>::iterator nodes_iterator;
  87   typedef llvm::SetVector<CallGraphNode *>::const_iterator const_nodes_iterator;
  88
  89   void print(raw_ostream &os) const;
  90   void dump() const;
  91   void viewGraph() const;
  92
  93   void addNodesForBlocks(DeclContext *D);
  94
  95   /// Part of recursive declaration visitation. We recursively visit all the
  96   /// declarations to collect the root functions.
  97   bool VisitFunctionDecl(FunctionDecl *FD) {
  98     // We skip function template definitions, as their semantics is
  99     // only determined when they are instantiated.
 100     if (includeInGraph(FD)) {
 101       // Add all blocks declared inside this function to the graph.
 102       addNodesForBlocks(FD);
 103       // If this function has external linkage, anything could call it.
 104       // Note, we are not precise here. For example, the function could have
 105       // its address taken.
 106       addNodeForDecl(FD, FD->isGlobal());
 107     }
 108     return true;
 109   }
 110
 111   /// Part of recursive declaration visitation.
 112   bool VisitObjCMethodDecl(ObjCMethodDecl *MD) {
 113     if (includeInGraph(MD)) {
 114       addNodesForBlocks(MD);
 115       addNodeForDecl(MD, true);
 116     }
 117     return true;
 118   }
 119
 120   // We are only collecting the declarations, so do not step into the bodies.
 121   bool TraverseStmt(Stmt *S) { return true; }
 122
 123   bool shouldWalkTypesOfTypeLocs() const { return false; }
 124
 125 private:
 126   /// \brief Add the given declaration to the call graph.
 127   void addNodeForDecl(Decl *D, bool IsGlobal);
 128
 129   /// \brief Allocate a new node in the graph.
 130   CallGraphNode *allocateNewNode(Decl *);
 131 };
 132
 133 class CallGraphNode {
 134 public:
 135   typedef CallGraphNode* CallRecord;
 136
 137 private:
 138   /// \brief The function/method declaration.
 139   Decl *FD;
 140
 141   /// \brief The list of functions called from this node.
 142   SmallVector<CallRecord, 5> CalledFunctions;
 143
 144 public:
 145   CallGraphNode(Decl *D) : FD(D) {}
 146
 147   typedef SmallVector<CallRecord, 5>::iterator iterator;
 148   typedef SmallVector<CallRecord, 5>::const_iterator const_iterator;
 149
 150   /// Iterators through all the callees/children of the node.
 151   inline iterator begin() { return CalledFunctions.begin(); }
 152   inline iterator end()   { return CalledFunctions.end(); }
 153   inline const_iterator begin() const { return CalledFunctions.begin(); }
 154   inline const_iterator end()   const { return CalledFunctions.end();   }
 155
 156   inline bool empty() const {return CalledFunctions.empty(); }
 157   inline unsigned size() const {return CalledFunctions.size(); }
 158
 159   void addCallee(CallGraphNode *N, CallGraph *CG) {
 160     CalledFunctions.push_back(N);
 161   }
 162
 163   Decl *getDecl() const { return FD; }
 164
 165   void print(raw_ostream &os) const;
 166   void dump() const;
 167 };
 168
 169 } // end clang namespace
 170
 171 // Graph traits for iteration, viewing.
 172 namespace llvm {
 173 template <> struct GraphTraits<clang::CallGraphNode*> {
 174   typedef clang::CallGraphNode NodeType;
 175   typedef clang::CallGraphNode::CallRecord CallRecordTy;
 176   typedef std::pointer_to_unary_function<CallRecordTy,
 177                                          clang::CallGraphNode*> CGNDerefFun;
 178   static NodeType *getEntryNode(clang::CallGraphNode *CGN) { return CGN; }
 179   typedef mapped_iterator<NodeType::iterator, CGNDerefFun> ChildIteratorType;
 180   static inline ChildIteratorType child_begin(NodeType *N) {
 181     return map_iterator(N->begin(), CGNDerefFun(CGNDeref));
 182   }
 183   static inline ChildIteratorType child_end  (NodeType *N) {
 184     return map_iterator(N->end(), CGNDerefFun(CGNDeref));
 185   }
 186   static clang::CallGraphNode *CGNDeref(CallRecordTy P) {
 187     return P;
 188   }
 189 };
 190
 191 template <> struct GraphTraits<const clang::CallGraphNode*> {
 192   typedef const clang::CallGraphNode NodeType;
 193   typedef NodeType::const_iterator ChildIteratorType;
 194   static NodeType *getEntryNode(const clang::CallGraphNode *CGN) { return CGN; }
 195   static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();}
 196   static inline ChildIteratorType child_end(NodeType *N) { return N->end(); }
 197 };
 198
 199 template <> struct GraphTraits<clang::CallGraph*>
 200   : public GraphTraits<clang::CallGraphNode*> {
 201
 202   static NodeType *getEntryNode(clang::CallGraph *CGN) {
 203     return CGN->getRoot();  // Start at the external node!
 204   }
 205   typedef std::pair<const clang::Decl*, clang::CallGraphNode*> PairTy;
 206   typedef std::pointer_to_unary_function<PairTy, clang::CallGraphNode&> DerefFun;
 207   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
 208   typedef mapped_iterator<clang::CallGraph::iterator, DerefFun> nodes_iterator;
 209
 210   static nodes_iterator nodes_begin(clang::CallGraph *CG) {
 211     return map_iterator(CG->begin(), DerefFun(CGdereference));
 212   }
 213   static nodes_iterator nodes_end  (clang::CallGraph *CG) {
 214     return map_iterator(CG->end(), DerefFun(CGdereference));
 215   }
 216   static clang::CallGraphNode &CGdereference(PairTy P) {
 217     return *(P.second);
 218   }
 219
 220   static unsigned size(clang::CallGraph *CG) {
 221     return CG->size();
 222   }
 223 };
 224
 225 template <> struct GraphTraits<const clang::CallGraph*> :
 226   public GraphTraits<const clang::CallGraphNode*> {
 227   static NodeType *getEntryNode(const clang::CallGraph *CGN) {
 228     return CGN->getRoot();
 229   }
 230   typedef std::pair<const clang::Decl*, clang::CallGraphNode*> PairTy;
 231   typedef std::pointer_to_unary_function<PairTy, clang::CallGraphNode&> DerefFun;
 232   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
 233   typedef mapped_iterator<clang::CallGraph::const_iterator,
 234                           DerefFun> nodes_iterator;
 235
 236   static nodes_iterator nodes_begin(const clang::CallGraph *CG) {
 237     return map_iterator(CG->begin(), DerefFun(CGdereference));
 238   }
 239   static nodes_iterator nodes_end(const clang::CallGraph *CG) {
 240     return map_iterator(CG->end(), DerefFun(CGdereference));
 241   }
 242   static clang::CallGraphNode &CGdereference(PairTy P) {
 243     return *(P.second);
 244   }
 245
 246   static unsigned size(const clang::CallGraph *CG) {
 247     return CG->size();
 248   }
 249 };
 250
 251 } // end llvm namespace
 252
 253 #endif