contrib/llvm-project/clang/include/clang/Analysis/CallGraph.h

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