Anna Zaks | 196b8cf | 2012-03-08 00:42:23 +0000 | [diff] [blame] | 1 | //== CallGraph.cpp - 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 defines the AST-based CallGraph. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
Anna Zaks | 4f858df | 2012-12-21 01:19:15 +0000 | [diff] [blame] | 13 | #define DEBUG_TYPE "CallGraph" |
| 14 | |
Anna Zaks | 196b8cf | 2012-03-08 00:42:23 +0000 | [diff] [blame] | 15 | #include "clang/Analysis/CallGraph.h" |
Anna Zaks | 196b8cf | 2012-03-08 00:42:23 +0000 | [diff] [blame] | 16 | #include "clang/AST/ASTContext.h" |
| 17 | #include "clang/AST/Decl.h" |
| 18 | #include "clang/AST/StmtVisitor.h" |
Anna Zaks | bd80231 | 2012-12-21 17:27:01 +0000 | [diff] [blame] | 19 | #include "llvm/ADT/PostOrderIterator.h" |
Anna Zaks | 4f858df | 2012-12-21 01:19:15 +0000 | [diff] [blame] | 20 | #include "llvm/ADT/Statistic.h" |
Anna Zaks | 196b8cf | 2012-03-08 00:42:23 +0000 | [diff] [blame] | 21 | #include "llvm/Support/GraphWriter.h" |
| 22 | |
| 23 | using namespace clang; |
| 24 | |
Anna Zaks | 08165d8 | 2012-12-21 17:27:04 +0000 | [diff] [blame] | 25 | STATISTIC(NumObjCCallEdges, "Number of Objective-C method call edges"); |
Anna Zaks | 4f858df | 2012-12-21 01:19:15 +0000 | [diff] [blame] | 26 | STATISTIC(NumBlockCallEdges, "Number of block call edges"); |
| 27 | |
Anna Zaks | 6a86082 | 2012-04-12 22:36:48 +0000 | [diff] [blame] | 28 | namespace { |
| 29 | /// A helper class, which walks the AST and locates all the call sites in the |
| 30 | /// given function body. |
| 31 | class CGBuilder : public StmtVisitor<CGBuilder> { |
| 32 | CallGraph *G; |
Anna Zaks | 6a86082 | 2012-04-12 22:36:48 +0000 | [diff] [blame] | 33 | CallGraphNode *CallerNode; |
| 34 | |
| 35 | public: |
Benjamin Kramer | facde17 | 2012-06-06 17:32:50 +0000 | [diff] [blame] | 36 | CGBuilder(CallGraph *g, CallGraphNode *N) |
| 37 | : G(g), CallerNode(N) {} |
Anna Zaks | 6a86082 | 2012-04-12 22:36:48 +0000 | [diff] [blame] | 38 | |
| 39 | void VisitStmt(Stmt *S) { VisitChildren(S); } |
| 40 | |
Anna Zaks | 4f858df | 2012-12-21 01:19:15 +0000 | [diff] [blame] | 41 | Decl *getDeclFromCall(CallExpr *CE) { |
Anna Zaks | 6a86082 | 2012-04-12 22:36:48 +0000 | [diff] [blame] | 42 | if (FunctionDecl *CalleeDecl = CE->getDirectCallee()) |
Anna Zaks | 4f858df | 2012-12-21 01:19:15 +0000 | [diff] [blame] | 43 | return CalleeDecl; |
| 44 | |
| 45 | // Simple detection of a call through a block. |
| 46 | Expr *CEE = CE->getCallee()->IgnoreParenImpCasts(); |
| 47 | if (BlockExpr *Block = dyn_cast<BlockExpr>(CEE)) { |
| 48 | NumBlockCallEdges++; |
| 49 | return Block->getBlockDecl(); |
| 50 | } |
| 51 | |
| 52 | return 0; |
| 53 | } |
| 54 | |
| 55 | void addCalledDecl(Decl *D) { |
| 56 | if (G->includeInGraph(D)) { |
| 57 | CallGraphNode *CalleeNode = G->getOrInsertNode(D); |
| 58 | CallerNode->addCallee(CalleeNode, G); |
| 59 | } |
| 60 | } |
| 61 | |
| 62 | void VisitCallExpr(CallExpr *CE) { |
| 63 | if (Decl *D = getDeclFromCall(CE)) |
| 64 | addCalledDecl(D); |
| 65 | } |
| 66 | |
| 67 | // Adds may-call edges for the ObjC message sends. |
| 68 | void VisitObjCMessageExpr(ObjCMessageExpr *ME) { |
| 69 | if (ObjCInterfaceDecl *IDecl = ME->getReceiverInterface()) { |
| 70 | Selector Sel = ME->getSelector(); |
| 71 | |
Anna Zaks | 08165d8 | 2012-12-21 17:27:04 +0000 | [diff] [blame] | 72 | // Find the callee definition within the same translation unit. |
Anna Zaks | 4f858df | 2012-12-21 01:19:15 +0000 | [diff] [blame] | 73 | Decl *D = 0; |
| 74 | if (ME->isInstanceMessage()) |
| 75 | D = IDecl->lookupPrivateMethod(Sel); |
| 76 | else |
| 77 | D = IDecl->lookupPrivateClassMethod(Sel); |
| 78 | if (D) { |
| 79 | addCalledDecl(D); |
| 80 | NumObjCCallEdges++; |
Anna Zaks | 6a86082 | 2012-04-12 22:36:48 +0000 | [diff] [blame] | 81 | } |
Anna Zaks | 4f858df | 2012-12-21 01:19:15 +0000 | [diff] [blame] | 82 | } |
Anna Zaks | 6a86082 | 2012-04-12 22:36:48 +0000 | [diff] [blame] | 83 | } |
| 84 | |
| 85 | void VisitChildren(Stmt *S) { |
| 86 | for (Stmt::child_range I = S->children(); I; ++I) |
| 87 | if (*I) |
| 88 | static_cast<CGBuilder*>(this)->Visit(*I); |
| 89 | } |
| 90 | }; |
| 91 | |
| 92 | } // end anonymous namespace |
| 93 | |
Anna Zaks | 4f858df | 2012-12-21 01:19:15 +0000 | [diff] [blame] | 94 | void CallGraph::addNodesForBlocks(DeclContext *D) { |
| 95 | if (BlockDecl *BD = dyn_cast<BlockDecl>(D)) |
| 96 | addNodeForDecl(BD, true); |
| 97 | |
| 98 | for (DeclContext::decl_iterator I = D->decls_begin(), E = D->decls_end(); |
| 99 | I!=E; ++I) |
| 100 | if (DeclContext *DC = dyn_cast<DeclContext>(*I)) |
| 101 | addNodesForBlocks(DC); |
| 102 | } |
| 103 | |
Anna Zaks | 6a86082 | 2012-04-12 22:36:48 +0000 | [diff] [blame] | 104 | CallGraph::CallGraph() { |
| 105 | Root = getOrInsertNode(0); |
| 106 | } |
| 107 | |
| 108 | CallGraph::~CallGraph() { |
| 109 | if (!FunctionMap.empty()) { |
| 110 | for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); |
| 111 | I != E; ++I) |
| 112 | delete I->second; |
| 113 | FunctionMap.clear(); |
| 114 | } |
| 115 | } |
| 116 | |
| 117 | bool CallGraph::includeInGraph(const Decl *D) { |
Anna Zaks | 4f858df | 2012-12-21 01:19:15 +0000 | [diff] [blame] | 118 | assert(D); |
| 119 | if (!D->getBody()) |
| 120 | return false; |
| 121 | |
Anna Zaks | 196b8cf | 2012-03-08 00:42:23 +0000 | [diff] [blame] | 122 | if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { |
| 123 | // We skip function template definitions, as their semantics is |
| 124 | // only determined when they are instantiated. |
| 125 | if (!FD->isThisDeclarationADefinition() || |
| 126 | FD->isDependentContext()) |
| 127 | return false; |
| 128 | |
| 129 | IdentifierInfo *II = FD->getIdentifier(); |
| 130 | if (II && II->getName().startswith("__inline")) |
| 131 | return false; |
| 132 | } |
| 133 | |
| 134 | if (const ObjCMethodDecl *ID = dyn_cast<ObjCMethodDecl>(D)) { |
| 135 | if (!ID->isThisDeclarationADefinition()) |
| 136 | return false; |
| 137 | } |
| 138 | |
| 139 | return true; |
| 140 | } |
| 141 | |
Anna Zaks | 6a86082 | 2012-04-12 22:36:48 +0000 | [diff] [blame] | 142 | void CallGraph::addNodeForDecl(Decl* D, bool IsGlobal) { |
Anna Zaks | d277661 | 2012-03-08 23:16:26 +0000 | [diff] [blame] | 143 | assert(D); |
Anna Zaks | 196b8cf | 2012-03-08 00:42:23 +0000 | [diff] [blame] | 144 | |
Anna Zaks | 6a86082 | 2012-04-12 22:36:48 +0000 | [diff] [blame] | 145 | // Allocate a new node, mark it as root, and process it's calls. |
| 146 | CallGraphNode *Node = getOrInsertNode(D); |
Anna Zaks | 196b8cf | 2012-03-08 00:42:23 +0000 | [diff] [blame] | 147 | |
| 148 | // Process all the calls by this function as well. |
Benjamin Kramer | facde17 | 2012-06-06 17:32:50 +0000 | [diff] [blame] | 149 | CGBuilder builder(this, Node); |
Ted Kremenek | bb3d20f | 2012-04-05 04:03:23 +0000 | [diff] [blame] | 150 | if (Stmt *Body = D->getBody()) |
| 151 | builder.Visit(Body); |
Anna Zaks | 196b8cf | 2012-03-08 00:42:23 +0000 | [diff] [blame] | 152 | } |
| 153 | |
Anna Zaks | a5d531f | 2012-03-09 21:13:53 +0000 | [diff] [blame] | 154 | CallGraphNode *CallGraph::getNode(const Decl *F) const { |
Matt Beaumont-Gay | d53e877 | 2012-03-14 20:21:25 +0000 | [diff] [blame] | 155 | FunctionMapTy::const_iterator I = FunctionMap.find(F); |
| 156 | if (I == FunctionMap.end()) return 0; |
| 157 | return I->second; |
Anna Zaks | a5d531f | 2012-03-09 21:13:53 +0000 | [diff] [blame] | 158 | } |
| 159 | |
Anna Zaks | 6a86082 | 2012-04-12 22:36:48 +0000 | [diff] [blame] | 160 | CallGraphNode *CallGraph::getOrInsertNode(Decl *F) { |
Anna Zaks | 196b8cf | 2012-03-08 00:42:23 +0000 | [diff] [blame] | 161 | CallGraphNode *&Node = FunctionMap[F]; |
| 162 | if (Node) |
| 163 | return Node; |
| 164 | |
| 165 | Node = new CallGraphNode(F); |
Anna Zaks | bd80231 | 2012-12-21 17:27:01 +0000 | [diff] [blame] | 166 | // Make Root node a parent of all functions to make sure all are reachable. |
Anna Zaks | d277661 | 2012-03-08 23:16:26 +0000 | [diff] [blame] | 167 | if (F != 0) |
Anna Zaks | bd80231 | 2012-12-21 17:27:01 +0000 | [diff] [blame] | 168 | Root->addCallee(Node, this); |
Anna Zaks | 196b8cf | 2012-03-08 00:42:23 +0000 | [diff] [blame] | 169 | return Node; |
| 170 | } |
| 171 | |
| 172 | void CallGraph::print(raw_ostream &OS) const { |
| 173 | OS << " --- Call graph Dump --- \n"; |
Anna Zaks | bd80231 | 2012-12-21 17:27:01 +0000 | [diff] [blame] | 174 | |
| 175 | // We are going to print the graph in reverse post order, partially, to make |
| 176 | // sure the output is deterministic. |
| 177 | llvm::ReversePostOrderTraversal<const clang::CallGraph*> RPOT(this); |
| 178 | for (llvm::ReversePostOrderTraversal<const clang::CallGraph*>::rpo_iterator |
| 179 | I = RPOT.begin(), E = RPOT.end(); I != E; ++I) { |
| 180 | const CallGraphNode *N = *I; |
| 181 | |
Anna Zaks | 196b8cf | 2012-03-08 00:42:23 +0000 | [diff] [blame] | 182 | OS << " Function: "; |
Anna Zaks | bd80231 | 2012-12-21 17:27:01 +0000 | [diff] [blame] | 183 | if (N == Root) |
Anna Zaks | 196b8cf | 2012-03-08 00:42:23 +0000 | [diff] [blame] | 184 | OS << "< root >"; |
| 185 | else |
Anna Zaks | bd80231 | 2012-12-21 17:27:01 +0000 | [diff] [blame] | 186 | N->print(OS); |
| 187 | |
Anna Zaks | 196b8cf | 2012-03-08 00:42:23 +0000 | [diff] [blame] | 188 | OS << " calls: "; |
Anna Zaks | bd80231 | 2012-12-21 17:27:01 +0000 | [diff] [blame] | 189 | for (CallGraphNode::const_iterator CI = N->begin(), |
| 190 | CE = N->end(); CI != CE; ++CI) { |
Anna Zaks | 196b8cf | 2012-03-08 00:42:23 +0000 | [diff] [blame] | 191 | assert(*CI != Root && "No one can call the root node."); |
| 192 | (*CI)->print(OS); |
| 193 | OS << " "; |
| 194 | } |
| 195 | OS << '\n'; |
| 196 | } |
| 197 | OS.flush(); |
| 198 | } |
| 199 | |
| 200 | void CallGraph::dump() const { |
| 201 | print(llvm::errs()); |
| 202 | } |
| 203 | |
| 204 | void CallGraph::viewGraph() const { |
| 205 | llvm::ViewGraph(this, "CallGraph"); |
| 206 | } |
| 207 | |
Anna Zaks | 196b8cf | 2012-03-08 00:42:23 +0000 | [diff] [blame] | 208 | void CallGraphNode::print(raw_ostream &os) const { |
Anna Zaks | 4f858df | 2012-12-21 01:19:15 +0000 | [diff] [blame] | 209 | if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(FD)) |
| 210 | return ND->printName(os); |
| 211 | os << "< >"; |
Anna Zaks | 196b8cf | 2012-03-08 00:42:23 +0000 | [diff] [blame] | 212 | } |
| 213 | |
| 214 | void CallGraphNode::dump() const { |
| 215 | print(llvm::errs()); |
| 216 | } |
| 217 | |
| 218 | namespace llvm { |
| 219 | |
| 220 | template <> |
| 221 | struct DOTGraphTraits<const CallGraph*> : public DefaultDOTGraphTraits { |
| 222 | |
| 223 | DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} |
| 224 | |
| 225 | static std::string getNodeLabel(const CallGraphNode *Node, |
| 226 | const CallGraph *CG) { |
| 227 | if (CG->getRoot() == Node) { |
| 228 | return "< root >"; |
| 229 | } |
Anna Zaks | 4f858df | 2012-12-21 01:19:15 +0000 | [diff] [blame] | 230 | if (const NamedDecl *ND = dyn_cast_or_null<NamedDecl>(Node->getDecl())) |
| 231 | return ND->getNameAsString(); |
| 232 | else |
| 233 | return "< >"; |
Anna Zaks | 196b8cf | 2012-03-08 00:42:23 +0000 | [diff] [blame] | 234 | } |
| 235 | |
| 236 | }; |
| 237 | } |