clang/Analysis/CallGraph.h

0001 //===- CallGraph.h - AST-based Call graph -----------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 //  This file declares the AST-based CallGraph.
0010 //
0011 //  A call graph for functions whose definitions/bodies are available in the
0012 //  current translation unit. The graph has a "virtual" root node that contains
0013 //  edges to all externally available functions.
0014 //
0015 //===----------------------------------------------------------------------===//
0016
0017 #ifndef LLVM_CLANG_ANALYSIS_CALLGRAPH_H
0018 #define LLVM_CLANG_ANALYSIS_CALLGRAPH_H
0019
0020 #include "clang/AST/Decl.h"
0021 #include "clang/AST/DeclObjC.h"
0022 #include "clang/AST/DynamicRecursiveASTVisitor.h"
0023 #include "llvm/ADT/DenseMap.h"
0024 #include "llvm/ADT/GraphTraits.h"
0025 #include "llvm/ADT/STLExtras.h"
0026 #include "llvm/ADT/SetVector.h"
0027 #include "llvm/ADT/SmallVector.h"
0028 #include "llvm/ADT/iterator_range.h"
0029 #include <memory>
0030
0031 namespace clang {
0032
0033 class CallGraphNode;
0034 class Decl;
0035 class DeclContext;
0036 class Stmt;
0037
0038 /// The AST-based call graph.
0039 ///
0040 /// The call graph extends itself with the given declarations by implementing
0041 /// the recursive AST visitor, which constructs the graph by visiting the given
0042 /// declarations.
0043 class CallGraph : public DynamicRecursiveASTVisitor {
0044   friend class CallGraphNode;
0045
0046   using FunctionMapTy =
0047       llvm::DenseMap<const Decl *, std::unique_ptr<CallGraphNode>>;
0048
0049   /// FunctionMap owns all CallGraphNodes.
0050   FunctionMapTy FunctionMap;
0051
0052   /// This is a virtual root node that has edges to all the functions.
0053   CallGraphNode *Root;
0054
0055 public:
0056   CallGraph();
0057   ~CallGraph();
0058
0059   /// Populate the call graph with the functions in the given
0060   /// declaration.
0061   ///
0062   /// Recursively walks the declaration to find all the dependent Decls as well.
0063   void addToCallGraph(Decl *D) {
0064     TraverseDecl(D);
0065   }
0066
0067   /// Determine if a declaration should be included in the graph.
0068   static bool includeInGraph(const Decl *D);
0069
0070   /// Determine if a declaration should be included in the graph for the
0071   /// purposes of being a callee. This is similar to includeInGraph except
0072   /// it permits declarations, not just definitions.
0073   static bool includeCalleeInGraph(const Decl *D);
0074
0075   /// Lookup the node for the given declaration.
0076   CallGraphNode *getNode(const Decl *) const;
0077
0078   /// Lookup the node for the given declaration. If none found, insert
0079   /// one into the graph.
0080   CallGraphNode *getOrInsertNode(Decl *);
0081
0082   using iterator = FunctionMapTy::iterator;
0083   using const_iterator = FunctionMapTy::const_iterator;
0084
0085   /// Iterators through all the elements in the graph. Note, this gives
0086   /// non-deterministic order.
0087   iterator begin() { return FunctionMap.begin(); }
0088   iterator end()   { return FunctionMap.end();   }
0089   const_iterator begin() const { return FunctionMap.begin(); }
0090   const_iterator end()   const { return FunctionMap.end();   }
0091
0092   /// Get the number of nodes in the graph.
0093   unsigned size() const { return FunctionMap.size(); }
0094
0095   /// Get the virtual root of the graph, all the functions available externally
0096   /// are represented as callees of the node.
0097   CallGraphNode *getRoot() const { return Root; }
0098
0099   /// Iterators through all the nodes of the graph that have no parent. These
0100   /// are the unreachable nodes, which are either unused or are due to us
0101   /// failing to add a call edge due to the analysis imprecision.
0102   using nodes_iterator = llvm::SetVector<CallGraphNode *>::iterator;
0103   using const_nodes_iterator = llvm::SetVector<CallGraphNode *>::const_iterator;
0104
0105   void print(raw_ostream &os) const;
0106   void dump() const;
0107   void viewGraph() const;
0108
0109   void addNodesForBlocks(DeclContext *D);
0110
0111   /// Part of recursive declaration visitation. We recursively visit all the
0112   /// declarations to collect the root functions.
0113   bool VisitFunctionDecl(FunctionDecl *FD) override {
0114     // We skip function template definitions, as their semantics is
0115     // only determined when they are instantiated.
0116     if (includeInGraph(FD) && FD->isThisDeclarationADefinition()) {
0117       // Add all blocks declared inside this function to the graph.
0118       addNodesForBlocks(FD);
0119       // If this function has external linkage, anything could call it.
0120       // Note, we are not precise here. For example, the function could have
0121       // its address taken.
0122       addNodeForDecl(FD, FD->isGlobal());
0123     }
0124     return true;
0125   }
0126
0127   /// Part of recursive declaration visitation.
0128   bool VisitObjCMethodDecl(ObjCMethodDecl *MD) override {
0129     if (includeInGraph(MD)) {
0130       addNodesForBlocks(MD);
0131       addNodeForDecl(MD, true);
0132     }
0133     return true;
0134   }
0135
0136   // We are only collecting the declarations, so do not step into the bodies.
0137   bool TraverseStmt(Stmt *S) override { return true; }
0138
0139 private:
0140   /// Add the given declaration to the call graph.
0141   void addNodeForDecl(Decl *D, bool IsGlobal);
0142 };
0143
0144 class CallGraphNode {
0145 public:
0146   struct CallRecord {
0147     CallGraphNode *Callee;
0148     Expr *CallExpr;
0149
0150     CallRecord() = default;
0151
0152     CallRecord(CallGraphNode *Callee_, Expr *CallExpr_)
0153         : Callee(Callee_), CallExpr(CallExpr_) {}
0154
0155     // The call destination is the only important data here,
0156     // allow to transparently unwrap into it.
0157     operator CallGraphNode *() const { return Callee; }
0158   };
0159
0160 private:
0161   /// The function/method declaration.
0162   Decl *FD;
0163
0164   /// The list of functions called from this node.
0165   SmallVector<CallRecord, 5> CalledFunctions;
0166
0167 public:
0168   CallGraphNode(Decl *D) : FD(D) {}
0169
0170   using iterator = SmallVectorImpl<CallRecord>::iterator;
0171   using const_iterator = SmallVectorImpl<CallRecord>::const_iterator;
0172
0173   /// Iterators through all the callees/children of the node.
0174   iterator begin() { return CalledFunctions.begin(); }
0175   iterator end() { return CalledFunctions.end(); }
0176   const_iterator begin() const { return CalledFunctions.begin(); }
0177   const_iterator end() const { return CalledFunctions.end(); }
0178
0179   /// Iterator access to callees/children of the node.
0180   llvm::iterator_range<iterator> callees() {
0181     return llvm::make_range(begin(), end());
0182   }
0183   llvm::iterator_range<const_iterator> callees() const {
0184     return llvm::make_range(begin(), end());
0185   }
0186
0187   bool empty() const { return CalledFunctions.empty(); }
0188   unsigned size() const { return CalledFunctions.size(); }
0189
0190   void addCallee(CallRecord Call) { CalledFunctions.push_back(Call); }
0191
0192   Decl *getDecl() const { return FD; }
0193
0194   FunctionDecl *getDefinition() const {
0195     return getDecl()->getAsFunction()->getDefinition();
0196   }
0197
0198   void print(raw_ostream &os) const;
0199   void dump() const;
0200 };
0201
0202 // NOTE: we are comparing based on the callee only. So different call records
0203 // (with different call expressions) to the same callee will compare equal!
0204 inline bool operator==(const CallGraphNode::CallRecord &LHS,
0205                        const CallGraphNode::CallRecord &RHS) {
0206   return LHS.Callee == RHS.Callee;
0207 }
0208
0209 } // namespace clang
0210
0211 namespace llvm {
0212
0213 // Specialize DenseMapInfo for clang::CallGraphNode::CallRecord.
0214 template <> struct DenseMapInfo<clang::CallGraphNode::CallRecord> {
0215   static inline clang::CallGraphNode::CallRecord getEmptyKey() {
0216     return clang::CallGraphNode::CallRecord(
0217         DenseMapInfo<clang::CallGraphNode *>::getEmptyKey(),
0218         DenseMapInfo<clang::Expr *>::getEmptyKey());
0219   }
0220
0221   static inline clang::CallGraphNode::CallRecord getTombstoneKey() {
0222     return clang::CallGraphNode::CallRecord(
0223         DenseMapInfo<clang::CallGraphNode *>::getTombstoneKey(),
0224         DenseMapInfo<clang::Expr *>::getTombstoneKey());
0225   }
0226
0227   static unsigned getHashValue(const clang::CallGraphNode::CallRecord &Val) {
0228     // NOTE: we are comparing based on the callee only.
0229     // Different call records with the same callee will compare equal!
0230     return DenseMapInfo<clang::CallGraphNode *>::getHashValue(Val.Callee);
0231   }
0232
0233   static bool isEqual(const clang::CallGraphNode::CallRecord &LHS,
0234                       const clang::CallGraphNode::CallRecord &RHS) {
0235     return LHS == RHS;
0236   }
0237 };
0238
0239 // Graph traits for iteration, viewing.
0240 template <> struct GraphTraits<clang::CallGraphNode*> {
0241   using NodeType = clang::CallGraphNode;
0242   using NodeRef = clang::CallGraphNode *;
0243   using ChildIteratorType = NodeType::iterator;
0244
0245   static NodeType *getEntryNode(clang::CallGraphNode *CGN) { return CGN; }
0246   static ChildIteratorType child_begin(NodeType *N) { return N->begin();  }
0247   static ChildIteratorType child_end(NodeType *N) { return N->end(); }
0248 };
0249
0250 template <> struct GraphTraits<const clang::CallGraphNode*> {
0251   using NodeType = const clang::CallGraphNode;
0252   using NodeRef = const clang::CallGraphNode *;
0253   using ChildIteratorType = NodeType::const_iterator;
0254
0255   static NodeType *getEntryNode(const clang::CallGraphNode *CGN) { return CGN; }
0256   static ChildIteratorType child_begin(NodeType *N) { return N->begin();}
0257   static ChildIteratorType child_end(NodeType *N) { return N->end(); }
0258 };
0259
0260 template <> struct GraphTraits<clang::CallGraph*>
0261   : public GraphTraits<clang::CallGraphNode*> {
0262   static NodeType *getEntryNode(clang::CallGraph *CGN) {
0263     return CGN->getRoot();  // Start at the external node!
0264   }
0265
0266   static clang::CallGraphNode *
0267   CGGetValue(clang::CallGraph::const_iterator::value_type &P) {
0268     return P.second.get();
0269   }
0270
0271   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
0272   using nodes_iterator =
0273       mapped_iterator<clang::CallGraph::iterator, decltype(&CGGetValue)>;
0274
0275   static nodes_iterator nodes_begin(clang::CallGraph *CG) {
0276     return nodes_iterator(CG->begin(), &CGGetValue);
0277   }
0278
0279   static nodes_iterator nodes_end  (clang::CallGraph *CG) {
0280     return nodes_iterator(CG->end(), &CGGetValue);
0281   }
0282
0283   static unsigned size(clang::CallGraph *CG) { return CG->size(); }
0284 };
0285
0286 template <> struct GraphTraits<const clang::CallGraph*> :
0287   public GraphTraits<const clang::CallGraphNode*> {
0288   static NodeType *getEntryNode(const clang::CallGraph *CGN) {
0289     return CGN->getRoot();
0290   }
0291
0292   static clang::CallGraphNode *
0293   CGGetValue(clang::CallGraph::const_iterator::value_type &P) {
0294     return P.second.get();
0295   }
0296
0297   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
0298   using nodes_iterator =
0299       mapped_iterator<clang::CallGraph::const_iterator, decltype(&CGGetValue)>;
0300
0301   static nodes_iterator nodes_begin(const clang::CallGraph *CG) {
0302     return nodes_iterator(CG->begin(), &CGGetValue);
0303   }
0304
0305   static nodes_iterator nodes_end(const clang::CallGraph *CG) {
0306     return nodes_iterator(CG->end(), &CGGetValue);
0307   }
0308
0309   static unsigned size(const clang::CallGraph *CG) { return CG->size(); }
0310 };
0311
0312 } // namespace llvm
0313
0314 #endif // LLVM_CLANG_ANALYSIS_CALLGRAPH_H