clang  6.0.0svn
CallGraph.cpp
Go to the documentation of this file.
1 //===- CallGraph.cpp - AST-based Call graph -------------------------------===//
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 defines the AST-based CallGraph.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "clang/AST/Decl.h"
16 #include "clang/AST/DeclBase.h"
17 #include "clang/AST/DeclObjC.h"
18 #include "clang/AST/Expr.h"
19 #include "clang/AST/ExprObjC.h"
20 #include "clang/AST/Stmt.h"
21 #include "clang/AST/StmtVisitor.h"
23 #include "clang/Basic/LLVM.h"
24 #include "llvm/ADT/PostOrderIterator.h"
25 #include "llvm/ADT/STLExtras.h"
26 #include "llvm/ADT/Statistic.h"
27 #include "llvm/Support/Casting.h"
28 #include "llvm/Support/Compiler.h"
29 #include "llvm/Support/DOTGraphTraits.h"
30 #include "llvm/Support/GraphWriter.h"
31 #include "llvm/Support/raw_ostream.h"
32 #include <cassert>
33 #include <memory>
34 #include <string>
35 
36 using namespace clang;
37 
38 #define DEBUG_TYPE "CallGraph"
39 
40 STATISTIC(NumObjCCallEdges, "Number of Objective-C method call edges");
41 STATISTIC(NumBlockCallEdges, "Number of block call edges");
42 
43 namespace {
44 
45 /// A helper class, which walks the AST and locates all the call sites in the
46 /// given function body.
47 class CGBuilder : public StmtVisitor<CGBuilder> {
48  CallGraph *G;
49  CallGraphNode *CallerNode;
50 
51 public:
52  CGBuilder(CallGraph *g, CallGraphNode *N) : G(g), CallerNode(N) {}
53 
54  void VisitStmt(Stmt *S) { VisitChildren(S); }
55 
56  Decl *getDeclFromCall(CallExpr *CE) {
57  if (FunctionDecl *CalleeDecl = CE->getDirectCallee())
58  return CalleeDecl;
59 
60  // Simple detection of a call through a block.
61  Expr *CEE = CE->getCallee()->IgnoreParenImpCasts();
62  if (BlockExpr *Block = dyn_cast<BlockExpr>(CEE)) {
63  NumBlockCallEdges++;
64  return Block->getBlockDecl();
65  }
66 
67  return nullptr;
68  }
69 
70  void addCalledDecl(Decl *D) {
71  if (G->includeInGraph(D)) {
72  CallGraphNode *CalleeNode = G->getOrInsertNode(D);
73  CallerNode->addCallee(CalleeNode);
74  }
75  }
76 
77  void VisitCallExpr(CallExpr *CE) {
78  if (Decl *D = getDeclFromCall(CE))
79  addCalledDecl(D);
80  VisitChildren(CE);
81  }
82 
83  // Adds may-call edges for the ObjC message sends.
84  void VisitObjCMessageExpr(ObjCMessageExpr *ME) {
85  if (ObjCInterfaceDecl *IDecl = ME->getReceiverInterface()) {
86  Selector Sel = ME->getSelector();
87 
88  // Find the callee definition within the same translation unit.
89  Decl *D = nullptr;
90  if (ME->isInstanceMessage())
91  D = IDecl->lookupPrivateMethod(Sel);
92  else
93  D = IDecl->lookupPrivateClassMethod(Sel);
94  if (D) {
95  addCalledDecl(D);
96  NumObjCCallEdges++;
97  }
98  }
99  }
100 
101  void VisitChildren(Stmt *S) {
102  for (Stmt *SubStmt : S->children())
103  if (SubStmt)
104  this->Visit(SubStmt);
105  }
106 };
107 
108 } // namespace
109 
111  if (BlockDecl *BD = dyn_cast<BlockDecl>(D))
112  addNodeForDecl(BD, true);
113 
114  for (auto *I : D->decls())
115  if (auto *DC = dyn_cast<DeclContext>(I))
116  addNodesForBlocks(DC);
117 }
118 
120  Root = getOrInsertNode(nullptr);
121 }
122 
123 CallGraph::~CallGraph() = default;
124 
126  assert(D);
127  if (!D->hasBody())
128  return false;
129 
130  if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
131  // We skip function template definitions, as their semantics is
132  // only determined when they are instantiated.
133  if (FD->isDependentContext())
134  return false;
135 
136  IdentifierInfo *II = FD->getIdentifier();
137  if (II && II->getName().startswith("__inline"))
138  return false;
139  }
140 
141  return true;
142 }
143 
144 void CallGraph::addNodeForDecl(Decl* D, bool IsGlobal) {
145  assert(D);
146 
147  // Allocate a new node, mark it as root, and process it's calls.
148  CallGraphNode *Node = getOrInsertNode(D);
149 
150  // Process all the calls by this function as well.
151  CGBuilder builder(this, Node);
152  if (Stmt *Body = D->getBody())
153  builder.Visit(Body);
154 }
155 
157  FunctionMapTy::const_iterator I = FunctionMap.find(F);
158  if (I == FunctionMap.end()) return nullptr;
159  return I->second.get();
160 }
161 
163  if (F && !isa<ObjCMethodDecl>(F))
164  F = F->getCanonicalDecl();
165 
166  std::unique_ptr<CallGraphNode> &Node = FunctionMap[F];
167  if (Node)
168  return Node.get();
169 
170  Node = llvm::make_unique<CallGraphNode>(F);
171  // Make Root node a parent of all functions to make sure all are reachable.
172  if (F)
173  Root->addCallee(Node.get());
174  return Node.get();
175 }
176 
177 void CallGraph::print(raw_ostream &OS) const {
178  OS << " --- Call graph Dump --- \n";
179 
180  // We are going to print the graph in reverse post order, partially, to make
181  // sure the output is deterministic.
182  llvm::ReversePostOrderTraversal<const CallGraph *> RPOT(this);
183  for (llvm::ReversePostOrderTraversal<const CallGraph *>::rpo_iterator
184  I = RPOT.begin(), E = RPOT.end(); I != E; ++I) {
185  const CallGraphNode *N = *I;
186 
187  OS << " Function: ";
188  if (N == Root)
189  OS << "< root >";
190  else
191  N->print(OS);
192 
193  OS << " calls: ";
194  for (CallGraphNode::const_iterator CI = N->begin(),
195  CE = N->end(); CI != CE; ++CI) {
196  assert(*CI != Root && "No one can call the root node.");
197  (*CI)->print(OS);
198  OS << " ";
199  }
200  OS << '\n';
201  }
202  OS.flush();
203 }
204 
205 LLVM_DUMP_METHOD void CallGraph::dump() const {
206  print(llvm::errs());
207 }
208 
209 void CallGraph::viewGraph() const {
210  llvm::ViewGraph(this, "CallGraph");
211 }
212 
213 void CallGraphNode::print(raw_ostream &os) const {
214  if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(FD))
215  return ND->printName(os);
216  os << "< >";
217 }
218 
219 LLVM_DUMP_METHOD void CallGraphNode::dump() const {
220  print(llvm::errs());
221 }
222 
223 namespace llvm {
224 
225 template <>
226 struct DOTGraphTraits<const CallGraph*> : public DefaultDOTGraphTraits {
227  DOTGraphTraits (bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
228 
229  static std::string getNodeLabel(const CallGraphNode *Node,
230  const CallGraph *CG) {
231  if (CG->getRoot() == Node) {
232  return "< root >";
233  }
234  if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(Node->getDecl()))
235  return ND->getNameAsString();
236  else
237  return "< >";
238  }
239 };
240 
241 } // namespace llvm
The AST-based call graph.
Definition: CallGraph.h:42
FunctionDecl - An instance of this class is created to represent a function declaration or definition...
Definition: Decl.h:1698
Smart pointer class that efficiently represents Objective-C method names.
void dump() const
Definition: CallGraph.cpp:205
Selector getSelector() const
Definition: ExprObjC.cpp:312
virtual Stmt * getBody() const
getBody - If this Decl represents a declaration for a body of code, such as a function or method defi...
Definition: DeclBase.h:974
DominatorTree GraphTraits specialization so the DominatorTree can be iterable by generic graph iterat...
Definition: Dominators.h:26
Stmt - This represents one statement.
Definition: Stmt.h:66
ObjCInterfaceDecl * getReceiverInterface() const
Retrieve the Objective-C interface to which this message is being directed, if known.
Definition: ExprObjC.cpp:333
const T * get() const
Retrieve the stored node as type T.
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:86
void dump() const
Definition: CallGraph.cpp:219
SmallVectorImpl< CallRecord >::const_iterator const_iterator
Definition: CallGraph.h:158
decl_range decls() const
decls_begin/decls_end - Iterate over the declarations stored in this context.
Definition: DeclBase.h:1576
CallGraphNode * getOrInsertNode(Decl *)
Lookup the node for the given declaration.
Definition: CallGraph.cpp:162
void addCallee(CallGraphNode *N)
Definition: CallGraph.h:169
One of these records is kept for each identifier that is lexed.
Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified...
child_range children()
Definition: Stmt.cpp:226
void addNodesForBlocks(DeclContext *D)
Definition: CallGraph.cpp:110
Represents an ObjC class declaration.
Definition: DeclObjC.h:1191
virtual Decl * getCanonicalDecl()
Retrieves the "canonical" declaration of the given declaration.
Definition: DeclBase.h:865
Decl * getDecl() const
Definition: CallGraph.h:173
static std::string getNodeLabel(const CallGraphNode *Node, const CallGraph *CG)
Definition: CallGraph.cpp:229
STATISTIC(NumObjCCallEdges, "Number of Objective-C method call edges")
BlockDecl - This represents a block literal declaration, which is like an unnamed FunctionDecl...
Definition: Decl.h:3689
Expr - This represents one expression.
Definition: Expr.h:106
BlockExpr - Adaptor class for mixing a BlockDecl with expressions.
Definition: Expr.h:4851
const Expr * getCallee() const
Definition: Expr.h:2249
Defines the clang::IdentifierInfo, clang::IdentifierTable, and clang::Selector interfaces.
An expression that sends a message to the given Objective-C object or class.
Definition: ExprObjC.h:903
void print(raw_ostream &os) const
Definition: CallGraph.cpp:177
virtual bool hasBody() const
Returns true if this Decl represents a declaration for a body of code, such as a function or method d...
Definition: DeclBase.h:980
static bool includeInGraph(const Decl *D)
Determine if a declaration should be included in the graph.
Definition: CallGraph.cpp:125
StmtVisitor - This class implements a simple visitor for Stmt subclasses.
Definition: StmtVisitor.h:183
void viewGraph() const
Definition: CallGraph.cpp:209
void print(raw_ostream &os) const
Definition: CallGraph.cpp:213
StringRef getName() const
Return the actual identifier string.
ast_type_traits::DynTypedNode Node
Dataflow Directional Tag Classes.
DeclContext - This is used only as base class of specific decl types that can act as declaration cont...
Definition: DeclBase.h:1252
CallGraphNode * getNode(const Decl *) const
Lookup the node for the given declaration.
Definition: CallGraph.cpp:156
FunctionDecl * getDirectCallee()
If the callee is a FunctionDecl, return it. Otherwise return 0.
Definition: Expr.cpp:1216
CallGraphNode * getRoot() const
\ brief Get the virtual root of the graph, all the functions available externally are represented as ...
Definition: CallGraph.h:91
iterator begin()
Iterators through all the callees/children of the node.
Definition: CallGraph.h:161
Expr * IgnoreParenImpCasts() LLVM_READONLY
IgnoreParenImpCasts - Ignore parentheses and implicit casts.
Definition: Expr.cpp:2550
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
Definition: Expr.h:2209
NamedDecl - This represents a decl with a name.
Definition: Decl.h:245
bool isInstanceMessage() const
Determine whether this is an instance message to either a computed object or to super.
Definition: ExprObjC.h:1194