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