]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
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 | //===----------------------------------------------------------------------===// | |
13 | #include "clang/Analysis/CallGraph.h" | |
14 | ||
15 | #include "clang/AST/ASTContext.h" | |
16 | #include "clang/AST/Decl.h" | |
17 | #include "clang/AST/StmtVisitor.h" | |
18 | ||
19 | #include "llvm/Support/GraphWriter.h" | |
20 | ||
21 | using namespace clang; | |
22 | ||
23 | namespace { | |
24 | /// A helper class, which walks the AST and locates all the call sites in the | |
25 | /// given function body. | |
26 | class CGBuilder : public StmtVisitor<CGBuilder> { | |
27 | CallGraph *G; | |
28 | CallGraphNode *CallerNode; | |
29 | ||
30 | public: | |
31 | CGBuilder(CallGraph *g, CallGraphNode *N) | |
32 | : G(g), CallerNode(N) {} | |
33 | ||
34 | void VisitStmt(Stmt *S) { VisitChildren(S); } | |
35 | ||
36 | void VisitCallExpr(CallExpr *CE) { | |
37 | // TODO: We need to handle ObjC method calls as well. | |
38 | if (FunctionDecl *CalleeDecl = CE->getDirectCallee()) | |
39 | if (G->includeInGraph(CalleeDecl)) { | |
40 | CallGraphNode *CalleeNode = G->getOrInsertNode(CalleeDecl); | |
41 | CallerNode->addCallee(CalleeNode, G); | |
42 | } | |
43 | } | |
44 | ||
45 | void VisitChildren(Stmt *S) { | |
46 | for (Stmt::child_range I = S->children(); I; ++I) | |
47 | if (*I) | |
48 | static_cast<CGBuilder*>(this)->Visit(*I); | |
49 | } | |
50 | }; | |
51 | ||
52 | } // end anonymous namespace | |
53 | ||
54 | CallGraph::CallGraph() { | |
55 | Root = getOrInsertNode(0); | |
56 | } | |
57 | ||
58 | CallGraph::~CallGraph() { | |
59 | if (!FunctionMap.empty()) { | |
60 | for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); | |
61 | I != E; ++I) | |
62 | delete I->second; | |
63 | FunctionMap.clear(); | |
64 | } | |
65 | } | |
66 | ||
67 | bool CallGraph::includeInGraph(const Decl *D) { | |
68 | if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { | |
69 | // We skip function template definitions, as their semantics is | |
70 | // only determined when they are instantiated. | |
71 | if (!FD->isThisDeclarationADefinition() || | |
72 | FD->isDependentContext()) | |
73 | return false; | |
74 | ||
75 | IdentifierInfo *II = FD->getIdentifier(); | |
76 | if (II && II->getName().startswith("__inline")) | |
77 | return false; | |
78 | } | |
79 | ||
80 | if (const ObjCMethodDecl *ID = dyn_cast<ObjCMethodDecl>(D)) { | |
81 | if (!ID->isThisDeclarationADefinition()) | |
82 | return false; | |
83 | } | |
84 | ||
85 | return true; | |
86 | } | |
87 | ||
88 | void CallGraph::addNodeForDecl(Decl* D, bool IsGlobal) { | |
89 | assert(D); | |
90 | ||
91 | // Do nothing if the node already exists. | |
92 | if (FunctionMap.find(D) != FunctionMap.end()) | |
93 | return; | |
94 | ||
95 | // Allocate a new node, mark it as root, and process it's calls. | |
96 | CallGraphNode *Node = getOrInsertNode(D); | |
97 | if (IsGlobal) | |
98 | Root->addCallee(Node, this); | |
99 | ||
100 | // Process all the calls by this function as well. | |
101 | CGBuilder builder(this, Node); | |
102 | if (Stmt *Body = D->getBody()) | |
103 | builder.Visit(Body); | |
104 | } | |
105 | ||
106 | CallGraphNode *CallGraph::getNode(const Decl *F) const { | |
107 | FunctionMapTy::const_iterator I = FunctionMap.find(F); | |
108 | if (I == FunctionMap.end()) return 0; | |
109 | return I->second; | |
110 | } | |
111 | ||
112 | CallGraphNode *CallGraph::getOrInsertNode(Decl *F) { | |
113 | CallGraphNode *&Node = FunctionMap[F]; | |
114 | if (Node) | |
115 | return Node; | |
116 | ||
117 | Node = new CallGraphNode(F); | |
118 | // If not root, add to the parentless list. | |
119 | if (F != 0) | |
120 | ParentlessNodes.insert(Node); | |
121 | return Node; | |
122 | } | |
123 | ||
124 | void CallGraph::print(raw_ostream &OS) const { | |
125 | OS << " --- Call graph Dump --- \n"; | |
126 | for (const_iterator I = begin(), E = end(); I != E; ++I) { | |
127 | OS << " Function: "; | |
128 | if (I->second == Root) | |
129 | OS << "< root >"; | |
130 | else | |
131 | I->second->print(OS); | |
132 | OS << " calls: "; | |
133 | for (CallGraphNode::iterator CI = I->second->begin(), | |
134 | CE = I->second->end(); CI != CE; ++CI) { | |
135 | assert(*CI != Root && "No one can call the root node."); | |
136 | (*CI)->print(OS); | |
137 | OS << " "; | |
138 | } | |
139 | OS << '\n'; | |
140 | } | |
141 | OS.flush(); | |
142 | } | |
143 | ||
144 | void CallGraph::dump() const { | |
145 | print(llvm::errs()); | |
146 | } | |
147 | ||
148 | void CallGraph::viewGraph() const { | |
149 | llvm::ViewGraph(this, "CallGraph"); | |
150 | } | |
151 | ||
152 | StringRef CallGraphNode::getName() const { | |
153 | if (const FunctionDecl *D = dyn_cast_or_null<FunctionDecl>(FD)) | |
154 | if (const IdentifierInfo *II = D->getIdentifier()) | |
155 | return II->getName(); | |
156 | return "< >"; | |
157 | } | |
158 | ||
159 | void CallGraphNode::print(raw_ostream &os) const { | |
160 | os << getName(); | |
161 | } | |
162 | ||
163 | void CallGraphNode::dump() const { | |
164 | print(llvm::errs()); | |
165 | } | |
166 | ||
167 | namespace llvm { | |
168 | ||
169 | template <> | |
170 | struct DOTGraphTraits<const CallGraph*> : public DefaultDOTGraphTraits { | |
171 | ||
172 | DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} | |
173 | ||
174 | static std::string getNodeLabel(const CallGraphNode *Node, | |
175 | const CallGraph *CG) { | |
176 | if (CG->getRoot() == Node) { | |
177 | return "< root >"; | |
178 | } | |
179 | return Node->getName(); | |
180 | } | |
181 | ||
182 | }; | |
183 | } |