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