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 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. We recursively visit all the
 106   /// Declarations to collect the root functions.
 107   bool VisitFunctionDecl(FunctionDecl *FD) {
 108     // We skip function template definitions, as their semantics is
 109     // only determined when they are instantiated.
 110     if (includeInGraph(FD))
 111       // If this function has external linkage, anything could call it.
 112       // Note, we are not precise here. For example, the function could have
 113       // its address taken.
 114       addNodeForDecl(FD, FD->isGlobal());
 115     return true;
 116   }
 117
 118   /// Part of recursive declaration visitation.
 119   bool VisitObjCMethodDecl(ObjCMethodDecl *MD) {
 120     if (includeInGraph(MD))
 121       addNodeForDecl(MD, true);
 122     return true;
 123   }
 124
 125   // We are only collecting the declarations, so do not step into the bodies.
 126   bool TraverseStmt(Stmt *S) { return true; }
 127
 128   bool shouldWalkTypesOfTypeLocs() const { return false; }
 129
 130 private:
 131   /// \brief Add the given declaration to the call graph.
 132   void addNodeForDecl(Decl *D, bool IsGlobal);
 133
 134   /// \brief Allocate a new node in the graph.
 135   CallGraphNode *allocateNewNode(Decl *);
 136 };
 137
 138 class CallGraphNode {
 139 public:
 140   typedef CallGraphNode* CallRecord;
 141
 142 private:
 143   /// \brief The function/method declaration.
 144   Decl *FD;
 145
 146   /// \brief The list of functions called from this node.
 147   // Small vector might be more efficient since we are only tracking functions
 148   // whose definition is in the current TU.
 149   llvm::SmallVector<CallRecord, 5> CalledFunctions;
 150
 151 public:
 152   CallGraphNode(Decl *D) : FD(D) {}
 153
 154   typedef llvm::SmallVector<CallRecord, 5>::iterator iterator;
 155   typedef llvm::SmallVector<CallRecord, 5>::const_iterator const_iterator;
 156
 157   /// Iterators through all the callees/children of the node.
 158   inline iterator begin() { return CalledFunctions.begin(); }
 159   inline iterator end()   { return CalledFunctions.end(); }
 160   inline const_iterator begin() const { return CalledFunctions.begin(); }
 161   inline const_iterator end()   const { return CalledFunctions.end();   }
 162
 163   inline bool empty() const {return CalledFunctions.empty(); }
 164   inline unsigned size() const {return CalledFunctions.size(); }
 165
 166   void addCallee(CallGraphNode *N, CallGraph *CG) {
 167     CalledFunctions.push_back(N);
 168     CG->ParentlessNodes.remove(N);
 169   }
 170
 171   Decl *getDecl() const { return FD; }
 172
 173   StringRef getName() const;
 174
 175   void print(raw_ostream &os) const;
 176   void dump() const;
 177 };
 178
 179 } // end clang namespace
 180
 181 // Graph traits for iteration, viewing.
 182 namespace llvm {
 183 template <> struct GraphTraits<clang::CallGraphNode*> {
 184   typedef clang::CallGraphNode NodeType;
 185   typedef clang::CallGraphNode::CallRecord CallRecordTy;
 186   typedef std::pointer_to_unary_function<CallRecordTy,
 187                                          clang::CallGraphNode*> CGNDerefFun;
 188   static NodeType *getEntryNode(clang::CallGraphNode *CGN) { return CGN; }
 189   typedef mapped_iterator<NodeType::iterator, CGNDerefFun> ChildIteratorType;
 190   static inline ChildIteratorType child_begin(NodeType *N) {
 191     return map_iterator(N->begin(), CGNDerefFun(CGNDeref));
 192   }
 193   static inline ChildIteratorType child_end  (NodeType *N) {
 194     return map_iterator(N->end(), CGNDerefFun(CGNDeref));
 195   }
 196   static clang::CallGraphNode *CGNDeref(CallRecordTy P) {
 197     return P;
 198   }
 199 };
 200
 201 template <> struct GraphTraits<const clang::CallGraphNode*> {
 202   typedef const clang::CallGraphNode NodeType;
 203   typedef NodeType::const_iterator ChildIteratorType;
 204   static NodeType *getEntryNode(const clang::CallGraphNode *CGN) { return CGN; }
 205   static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();}
 206   static inline ChildIteratorType child_end  (NodeType *N) { return N->end(); }
 207 };
 208
 209 template <> struct GraphTraits<clang::CallGraph*>
 210   : public GraphTraits<clang::CallGraphNode*> {
 211
 212   static NodeType *getEntryNode(clang::CallGraph *CGN) {
 213     return CGN->getRoot();  // Start at the external node!
 214   }
 215   typedef std::pair<const clang::Decl*, clang::CallGraphNode*> PairTy;
 216   typedef std::pointer_to_unary_function<PairTy, clang::CallGraphNode&> DerefFun;
 217   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
 218   typedef mapped_iterator<clang::CallGraph::iterator, DerefFun> nodes_iterator;
 219
 220   static nodes_iterator nodes_begin(clang::CallGraph *CG) {
 221     return map_iterator(CG->begin(), DerefFun(CGdereference));
 222   }
 223   static nodes_iterator nodes_end  (clang::CallGraph *CG) {
 224     return map_iterator(CG->end(), DerefFun(CGdereference));
 225   }
 226   static clang::CallGraphNode &CGdereference(PairTy P) {
 227     return *(P.second);
 228   }
 229
 230   static unsigned size(clang::CallGraph *CG) {
 231     return CG->size();
 232   }
 233 };
 234
 235 template <> struct GraphTraits<const clang::CallGraph*> :
 236   public GraphTraits<const clang::CallGraphNode*> {
 237   static NodeType *getEntryNode(const clang::CallGraph *CGN) {
 238     return CGN->getRoot();
 239   }
 240   typedef std::pair<const clang::Decl*, clang::CallGraphNode*> PairTy;
 241   typedef std::pointer_to_unary_function<PairTy, clang::CallGraphNode&> DerefFun;
 242   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
 243   typedef mapped_iterator<clang::CallGraph::const_iterator,
 244                           DerefFun> nodes_iterator;
 245
 246   static nodes_iterator nodes_begin(const clang::CallGraph *CG) {
 247     return map_iterator(CG->begin(), DerefFun(CGdereference));
 248   }
 249   static nodes_iterator nodes_end(const clang::CallGraph *CG) {
 250     return map_iterator(CG->end(), DerefFun(CGdereference));
 251   }
 252   static clang::CallGraphNode &CGdereference(PairTy P) {
 253     return *(P.second);
 254   }
 255
 256   static unsigned size(const clang::CallGraph *CG) {
 257     return CG->size();
 258   }
 259 };
 260
 261 } // end llvm namespace
 262
 263 #endif