head 1.1; branch 1.1.1; access; symbols netbsd-11-0-RC4:1.1.1.9 netbsd-11-0-RC3:1.1.1.9 netbsd-11-0-RC2:1.1.1.9 netbsd-11-0-RC1:1.1.1.9 perseant-exfatfs-base-20250801:1.1.1.9 netbsd-11:1.1.1.9.0.10 netbsd-11-base:1.1.1.9 netbsd-10-1-RELEASE:1.1.1.9 perseant-exfatfs-base-20240630:1.1.1.9 perseant-exfatfs:1.1.1.9.0.8 perseant-exfatfs-base:1.1.1.9 netbsd-8-3-RELEASE:1.1.1.6 netbsd-9-4-RELEASE:1.1.1.8 netbsd-10-0-RELEASE:1.1.1.9 netbsd-10-0-RC6:1.1.1.9 netbsd-10-0-RC5:1.1.1.9 netbsd-10-0-RC4:1.1.1.9 netbsd-10-0-RC3:1.1.1.9 netbsd-10-0-RC2:1.1.1.9 netbsd-10-0-RC1:1.1.1.9 netbsd-10:1.1.1.9.0.6 netbsd-10-base:1.1.1.9 netbsd-9-3-RELEASE:1.1.1.8 cjep_sun2x:1.1.1.9.0.4 cjep_sun2x-base:1.1.1.9 cjep_staticlib_x-base1:1.1.1.9 netbsd-9-2-RELEASE:1.1.1.8 cjep_staticlib_x:1.1.1.9.0.2 cjep_staticlib_x-base:1.1.1.9 netbsd-9-1-RELEASE:1.1.1.8 phil-wifi-20200421:1.1.1.9 phil-wifi-20200411:1.1.1.9 phil-wifi-20200406:1.1.1.9 netbsd-8-2-RELEASE:1.1.1.6 netbsd-9-0-RELEASE:1.1.1.8 netbsd-9-0-RC2:1.1.1.8 netbsd-9-0-RC1:1.1.1.8 netbsd-9:1.1.1.8.0.2 netbsd-9-base:1.1.1.8 phil-wifi-20190609:1.1.1.8 netbsd-8-1-RELEASE:1.1.1.6 netbsd-8-1-RC1:1.1.1.6 pgoyette-compat-merge-20190127:1.1.1.7.2.1 pgoyette-compat-20190127:1.1.1.8 pgoyette-compat-20190118:1.1.1.8 pgoyette-compat-1226:1.1.1.8 pgoyette-compat-1126:1.1.1.8 pgoyette-compat-1020:1.1.1.8 pgoyette-compat-0930:1.1.1.8 pgoyette-compat-0906:1.1.1.8 netbsd-7-2-RELEASE:1.1.1.3.2.1 pgoyette-compat-0728:1.1.1.8 clang-337282:1.1.1.8 netbsd-8-0-RELEASE:1.1.1.6 phil-wifi:1.1.1.7.0.4 phil-wifi-base:1.1.1.7 pgoyette-compat-0625:1.1.1.7 netbsd-8-0-RC2:1.1.1.6 pgoyette-compat-0521:1.1.1.7 pgoyette-compat-0502:1.1.1.7 pgoyette-compat-0422:1.1.1.7 netbsd-8-0-RC1:1.1.1.6 pgoyette-compat-0415:1.1.1.7 pgoyette-compat-0407:1.1.1.7 pgoyette-compat-0330:1.1.1.7 pgoyette-compat-0322:1.1.1.7 pgoyette-compat-0315:1.1.1.7 netbsd-7-1-2-RELEASE:1.1.1.3.2.1 pgoyette-compat:1.1.1.7.0.2 pgoyette-compat-base:1.1.1.7 netbsd-7-1-1-RELEASE:1.1.1.3.2.1 clang-319952:1.1.1.7 matt-nb8-mediatek:1.1.1.6.0.10 matt-nb8-mediatek-base:1.1.1.6 clang-309604:1.1.1.7 perseant-stdc-iso10646:1.1.1.6.0.8 perseant-stdc-iso10646-base:1.1.1.6 netbsd-8:1.1.1.6.0.6 netbsd-8-base:1.1.1.6 prg-localcount2-base3:1.1.1.6 prg-localcount2-base2:1.1.1.6 prg-localcount2-base1:1.1.1.6 prg-localcount2:1.1.1.6.0.4 prg-localcount2-base:1.1.1.6 pgoyette-localcount-20170426:1.1.1.6 bouyer-socketcan-base1:1.1.1.6 pgoyette-localcount-20170320:1.1.1.6 netbsd-7-1:1.1.1.3.2.1.0.6 netbsd-7-1-RELEASE:1.1.1.3.2.1 netbsd-7-1-RC2:1.1.1.3.2.1 clang-294123:1.1.1.6 netbsd-7-nhusb-base-20170116:1.1.1.3.2.1 bouyer-socketcan:1.1.1.6.0.2 bouyer-socketcan-base:1.1.1.6 clang-291444:1.1.1.6 pgoyette-localcount-20170107:1.1.1.5 netbsd-7-1-RC1:1.1.1.3.2.1 pgoyette-localcount-20161104:1.1.1.5 netbsd-7-0-2-RELEASE:1.1.1.3.2.1 localcount-20160914:1.1.1.5 netbsd-7-nhusb:1.1.1.3.2.1.0.4 netbsd-7-nhusb-base:1.1.1.3.2.1 clang-280599:1.1.1.5 pgoyette-localcount-20160806:1.1.1.5 pgoyette-localcount-20160726:1.1.1.5 pgoyette-localcount:1.1.1.5.0.2 pgoyette-localcount-base:1.1.1.5 netbsd-7-0-1-RELEASE:1.1.1.3.2.1 clang-261930:1.1.1.5 netbsd-7-0:1.1.1.3.2.1.0.2 netbsd-7-0-RELEASE:1.1.1.3.2.1 netbsd-7-0-RC3:1.1.1.3.2.1 netbsd-7-0-RC2:1.1.1.3.2.1 netbsd-7-0-RC1:1.1.1.3.2.1 clang-237755:1.1.1.4 clang-232565:1.1.1.4 clang-227398:1.1.1.4 tls-maxphys-base:1.1.1.3 tls-maxphys:1.1.1.3.0.4 netbsd-7:1.1.1.3.0.2 netbsd-7-base:1.1.1.3 clang-215315:1.1.1.3 clang-209886:1.1.1.3 yamt-pagecache:1.1.1.2.0.4 yamt-pagecache-base9:1.1.1.2 tls-earlyentropy:1.1.1.2.0.2 tls-earlyentropy-base:1.1.1.3 riastradh-xf86-video-intel-2-7-1-pre-2-21-15:1.1.1.2 riastradh-drm2-base3:1.1.1.2 clang-202566:1.1.1.2 clang-201163:1.1.1.1 clang-199312:1.1.1.1 clang-198450:1.1.1.1 clang-196603:1.1.1.1 clang-195771:1.1.1.1 LLVM:1.1.1; locks; strict; comment @// @; 1.1 date 2013.11.28.14.14.49; author joerg; state Exp; branches 1.1.1.1; next ; commitid ow8OybrawrB1f3fx; 1.1.1.1 date 2013.11.28.14.14.49; author joerg; state Exp; branches; next 1.1.1.2; commitid ow8OybrawrB1f3fx; 1.1.1.2 date 2014.03.04.19.54.04; author joerg; state Exp; branches 1.1.1.2.2.1 1.1.1.2.4.1; next 1.1.1.3; commitid 29z1hJonZISIXprx; 1.1.1.3 date 2014.05.30.18.14.40; author joerg; state Exp; branches 1.1.1.3.2.1 1.1.1.3.4.1; next 1.1.1.4; commitid 8q0kdlBlCn09GACx; 1.1.1.4 date 2015.01.29.19.57.33; author joerg; state Exp; branches; next 1.1.1.5; commitid mlISSizlPKvepX7y; 1.1.1.5 date 2016.02.27.22.11.54; author joerg; state Exp; branches 1.1.1.5.2.1; next 1.1.1.6; commitid tIimz3oDlh1NpBWy; 1.1.1.6 date 2017.01.11.10.34.45; author joerg; state Exp; branches; next 1.1.1.7; commitid CNnUNfII1jgNmxBz; 1.1.1.7 date 2017.08.01.19.35.36; author joerg; state Exp; branches 1.1.1.7.2.1 1.1.1.7.4.1; next 1.1.1.8; commitid pMuDy65V0VicSx1A; 1.1.1.8 date 2018.07.17.18.31.08; author joerg; state Exp; branches; next 1.1.1.9; commitid wDzL46ALjrCZgwKA; 1.1.1.9 date 2019.11.13.22.19.20; author joerg; state dead; branches; next ; commitid QD8YATxuNG34YJKB; 1.1.1.2.2.1 date 2014.08.10.07.08.07; author tls; state Exp; branches; next ; commitid t01A1TLTYxkpGMLx; 1.1.1.2.4.1 date 2014.03.04.19.54.04; author yamt; state dead; branches; next 1.1.1.2.4.2; commitid WSrDtL5nYAUyiyBx; 1.1.1.2.4.2 date 2014.05.22.16.18.26; author yamt; state Exp; branches; next ; commitid WSrDtL5nYAUyiyBx; 1.1.1.3.2.1 date 2015.06.04.20.04.27; author snj; state Exp; branches; next ; commitid yRnjq9fueSo6n9oy; 1.1.1.3.4.1 date 2014.05.30.18.14.40; author tls; state dead; branches; next 1.1.1.3.4.2; commitid jTnpym9Qu0o4R1Nx; 1.1.1.3.4.2 date 2014.08.19.23.47.26; author tls; state Exp; branches; next ; commitid jTnpym9Qu0o4R1Nx; 1.1.1.5.2.1 date 2017.03.20.06.52.36; author pgoyette; state Exp; branches; next ; commitid jjw7cAwgyKq7RfKz; 1.1.1.7.2.1 date 2018.07.28.04.33.16; author pgoyette; state Exp; branches; next ; commitid 1UP1xAIUxv1ZgRLA; 1.1.1.7.4.1 date 2019.06.10.21.45.20; author christos; state Exp; branches; next 1.1.1.7.4.2; commitid jtc8rnCzWiEEHGqB; 1.1.1.7.4.2 date 2020.04.13.07.46.31; author martin; state dead; branches; next ; commitid X01YhRUPVUDaec4C; desc @@ 1.1 log @Initial revision @ text @//== CallGraph.cpp - AST-based Call graph ----------------------*- C++ -*--==// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This file defines the AST-based CallGraph. // //===----------------------------------------------------------------------===// #define DEBUG_TYPE "CallGraph" #include "clang/Analysis/CallGraph.h" #include "clang/AST/ASTContext.h" #include "clang/AST/Decl.h" #include "clang/AST/StmtVisitor.h" #include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/Statistic.h" #include "llvm/Support/GraphWriter.h" using namespace clang; STATISTIC(NumObjCCallEdges, "Number of Objective-C method call edges"); STATISTIC(NumBlockCallEdges, "Number of block call edges"); namespace { /// A helper class, which walks the AST and locates all the call sites in the /// given function body. class CGBuilder : public StmtVisitor { CallGraph *G; CallGraphNode *CallerNode; public: CGBuilder(CallGraph *g, CallGraphNode *N) : G(g), CallerNode(N) {} void VisitStmt(Stmt *S) { VisitChildren(S); } Decl *getDeclFromCall(CallExpr *CE) { if (FunctionDecl *CalleeDecl = CE->getDirectCallee()) return CalleeDecl; // Simple detection of a call through a block. Expr *CEE = CE->getCallee()->IgnoreParenImpCasts(); if (BlockExpr *Block = dyn_cast(CEE)) { NumBlockCallEdges++; return Block->getBlockDecl(); } return 0; } void addCalledDecl(Decl *D) { if (G->includeInGraph(D)) { CallGraphNode *CalleeNode = G->getOrInsertNode(D); CallerNode->addCallee(CalleeNode, G); } } void VisitCallExpr(CallExpr *CE) { if (Decl *D = getDeclFromCall(CE)) addCalledDecl(D); } // Adds may-call edges for the ObjC message sends. void VisitObjCMessageExpr(ObjCMessageExpr *ME) { if (ObjCInterfaceDecl *IDecl = ME->getReceiverInterface()) { Selector Sel = ME->getSelector(); // Find the callee definition within the same translation unit. Decl *D = 0; if (ME->isInstanceMessage()) D = IDecl->lookupPrivateMethod(Sel); else D = IDecl->lookupPrivateClassMethod(Sel); if (D) { addCalledDecl(D); NumObjCCallEdges++; } } } void VisitChildren(Stmt *S) { for (Stmt::child_range I = S->children(); I; ++I) if (*I) static_cast(this)->Visit(*I); } }; } // end anonymous namespace void CallGraph::addNodesForBlocks(DeclContext *D) { if (BlockDecl *BD = dyn_cast(D)) addNodeForDecl(BD, true); for (DeclContext::decl_iterator I = D->decls_begin(), E = D->decls_end(); I!=E; ++I) if (DeclContext *DC = dyn_cast(*I)) addNodesForBlocks(DC); } CallGraph::CallGraph() { Root = getOrInsertNode(0); } CallGraph::~CallGraph() { if (!FunctionMap.empty()) { for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); I != E; ++I) delete I->second; FunctionMap.clear(); } } bool CallGraph::includeInGraph(const Decl *D) { assert(D); if (!D->getBody()) return false; if (const FunctionDecl *FD = dyn_cast(D)) { // We skip function template definitions, as their semantics is // only determined when they are instantiated. if (!FD->isThisDeclarationADefinition() || FD->isDependentContext()) return false; IdentifierInfo *II = FD->getIdentifier(); if (II && II->getName().startswith("__inline")) return false; } if (const ObjCMethodDecl *ID = dyn_cast(D)) { if (!ID->isThisDeclarationADefinition()) return false; } return true; } void CallGraph::addNodeForDecl(Decl* D, bool IsGlobal) { assert(D); // Allocate a new node, mark it as root, and process it's calls. CallGraphNode *Node = getOrInsertNode(D); // Process all the calls by this function as well. CGBuilder builder(this, Node); if (Stmt *Body = D->getBody()) builder.Visit(Body); } CallGraphNode *CallGraph::getNode(const Decl *F) const { FunctionMapTy::const_iterator I = FunctionMap.find(F); if (I == FunctionMap.end()) return 0; return I->second; } CallGraphNode *CallGraph::getOrInsertNode(Decl *F) { CallGraphNode *&Node = FunctionMap[F]; if (Node) return Node; Node = new CallGraphNode(F); // Make Root node a parent of all functions to make sure all are reachable. if (F != 0) Root->addCallee(Node, this); return Node; } void CallGraph::print(raw_ostream &OS) const { OS << " --- Call graph Dump --- \n"; // We are going to print the graph in reverse post order, partially, to make // sure the output is deterministic. llvm::ReversePostOrderTraversal RPOT(this); for (llvm::ReversePostOrderTraversal::rpo_iterator I = RPOT.begin(), E = RPOT.end(); I != E; ++I) { const CallGraphNode *N = *I; OS << " Function: "; if (N == Root) OS << "< root >"; else N->print(OS); OS << " calls: "; for (CallGraphNode::const_iterator CI = N->begin(), CE = N->end(); CI != CE; ++CI) { assert(*CI != Root && "No one can call the root node."); (*CI)->print(OS); OS << " "; } OS << '\n'; } OS.flush(); } void CallGraph::dump() const { print(llvm::errs()); } void CallGraph::viewGraph() const { llvm::ViewGraph(this, "CallGraph"); } void CallGraphNode::print(raw_ostream &os) const { if (const NamedDecl *ND = dyn_cast_or_null(FD)) return ND->printName(os); os << "< >"; } void CallGraphNode::dump() const { print(llvm::errs()); } namespace llvm { template <> struct DOTGraphTraits : public DefaultDOTGraphTraits { DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} static std::string getNodeLabel(const CallGraphNode *Node, const CallGraph *CG) { if (CG->getRoot() == Node) { return "< root >"; } if (const NamedDecl *ND = dyn_cast_or_null(Node->getDecl())) return ND->getNameAsString(); else return "< >"; } }; } @ 1.1.1.1 log @Import Clang 3.4rc1 r195771. @ text @@ 1.1.1.2 log @Import Clang 3.5svn r202566. @ text @d109 6 a114 1 llvm::DeleteContainerSeconds(FunctionMap); @ 1.1.1.2.2.1 log @Rebase. @ text @d13 2 a24 2 #define DEBUG_TYPE "CallGraph" d52 1 a52 1 return nullptr; d73 1 a73 1 Decl *D = nullptr; d98 3 a100 2 for (auto *I : D->decls()) if (auto *DC = dyn_cast(I)) d105 1 a105 1 Root = getOrInsertNode(nullptr); d151 1 a151 1 if (I == FunctionMap.end()) return nullptr; d162 1 a162 1 if (F) @ 1.1.1.3 log @Import Clang 3.5svn r209886. @ text @d13 2 a24 2 #define DEBUG_TYPE "CallGraph" d52 1 a52 1 return nullptr; d73 1 a73 1 Decl *D = nullptr; d98 3 a100 2 for (auto *I : D->decls()) if (auto *DC = dyn_cast(I)) d105 1 a105 1 Root = getOrInsertNode(nullptr); d151 1 a151 1 if (I == FunctionMap.end()) return nullptr; d162 1 a162 1 if (F) @ 1.1.1.3.2.1 log @Update LLVM to 3.6.1, requested by joerg in ticket 824. @ text @d113 1 a113 1 if (!D->hasBody()) d119 2 a120 1 if (FD->isDependentContext()) d128 5 a154 3 if (F && !isa(F)) F = F->getCanonicalDecl(); @ 1.1.1.4 log @Import Clang 3.6RC1 r227398. @ text @d113 1 a113 1 if (!D->hasBody()) d119 2 a120 1 if (FD->isDependentContext()) d128 5 a154 3 if (F && !isa(F)) F = F->getCanonicalDecl(); @ 1.1.1.5 log @Import Clang 3.8.0rc3 r261930. @ text @d86 3 a88 3 for (Stmt *SubStmt : S->children()) if (SubStmt) this->Visit(SubStmt); @ 1.1.1.5.2.1 log @Sync with HEAD @ text @d58 1 a58 1 CallerNode->addCallee(CalleeNode); d107 3 a109 1 CallGraph::~CallGraph() {} d145 1 a145 1 return I->second.get(); d152 1 a152 1 std::unique_ptr &Node = FunctionMap[F]; d154 1 a154 1 return Node.get(); d156 1 a156 1 Node = llvm::make_unique(F); d159 2 a160 2 Root->addCallee(Node.get()); return Node.get(); d191 1 a191 1 LLVM_DUMP_METHOD void CallGraph::dump() const { d205 1 a205 1 LLVM_DUMP_METHOD void CallGraphNode::dump() const { @ 1.1.1.6 log @Import Clang pre-4.0.0 r291444. @ text @d58 1 a58 1 CallerNode->addCallee(CalleeNode); d107 3 a109 1 CallGraph::~CallGraph() {} d145 1 a145 1 return I->second.get(); d152 1 a152 1 std::unique_ptr &Node = FunctionMap[F]; d154 1 a154 1 return Node.get(); d156 1 a156 1 Node = llvm::make_unique(F); d159 2 a160 2 Root->addCallee(Node.get()); return Node.get(); d191 1 a191 1 LLVM_DUMP_METHOD void CallGraph::dump() const { d205 1 a205 1 LLVM_DUMP_METHOD void CallGraphNode::dump() const { @ 1.1.1.7 log @Import clang r309604 from branches/release_50 @ text @a64 1 VisitChildren(CE); @ 1.1.1.7.4.1 log @Sync with HEAD @ text @d1 1 a1 1 //===- CallGraph.cpp - AST-based Call graph -------------------------------===// a12 1 d14 1 a15 5 #include "clang/AST/DeclBase.h" #include "clang/AST/DeclObjC.h" #include "clang/AST/Expr.h" #include "clang/AST/ExprObjC.h" #include "clang/AST/Stmt.h" a16 2 #include "clang/Basic/IdentifierTable.h" #include "clang/Basic/LLVM.h" a17 1 #include "llvm/ADT/STLExtras.h" a18 3 #include "llvm/Support/Casting.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/DOTGraphTraits.h" a19 4 #include "llvm/Support/raw_ostream.h" #include #include #include a28 1 d36 2 a37 1 CGBuilder(CallGraph *g, CallGraphNode *N) : G(g), CallerNode(N) {} d93 1 a93 1 } // namespace d108 1 a108 1 CallGraph::~CallGraph() = default; d167 2 a168 2 llvm::ReversePostOrderTraversal RPOT(this); for (llvm::ReversePostOrderTraversal::rpo_iterator d212 2 a213 1 DOTGraphTraits (bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {} d225 1 d227 1 a227 2 } // namespace llvm @ 1.1.1.7.4.2 log @Mostly merge changes from HEAD upto 20200411 @ text @@ 1.1.1.7.2.1 log @Sync with HEAD @ text @d1 1 a1 1 //===- CallGraph.cpp - AST-based Call graph -------------------------------===// a12 1 d14 1 a15 5 #include "clang/AST/DeclBase.h" #include "clang/AST/DeclObjC.h" #include "clang/AST/Expr.h" #include "clang/AST/ExprObjC.h" #include "clang/AST/Stmt.h" a16 2 #include "clang/Basic/IdentifierTable.h" #include "clang/Basic/LLVM.h" a17 1 #include "llvm/ADT/STLExtras.h" a18 3 #include "llvm/Support/Casting.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/DOTGraphTraits.h" a19 4 #include "llvm/Support/raw_ostream.h" #include #include #include a28 1 d36 2 a37 1 CGBuilder(CallGraph *g, CallGraphNode *N) : G(g), CallerNode(N) {} d93 1 a93 1 } // namespace d108 1 a108 1 CallGraph::~CallGraph() = default; d167 2 a168 2 llvm::ReversePostOrderTraversal RPOT(this); for (llvm::ReversePostOrderTraversal::rpo_iterator d212 2 a213 1 DOTGraphTraits (bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {} d225 1 d227 1 a227 2 } // namespace llvm @ 1.1.1.8 log @Import clang r337282 from trunk @ text @d1 1 a1 1 //===- CallGraph.cpp - AST-based Call graph -------------------------------===// a12 1 d14 1 a15 5 #include "clang/AST/DeclBase.h" #include "clang/AST/DeclObjC.h" #include "clang/AST/Expr.h" #include "clang/AST/ExprObjC.h" #include "clang/AST/Stmt.h" a16 2 #include "clang/Basic/IdentifierTable.h" #include "clang/Basic/LLVM.h" a17 1 #include "llvm/ADT/STLExtras.h" a18 3 #include "llvm/Support/Casting.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/DOTGraphTraits.h" a19 4 #include "llvm/Support/raw_ostream.h" #include #include #include a28 1 d36 2 a37 1 CGBuilder(CallGraph *g, CallGraphNode *N) : G(g), CallerNode(N) {} d93 1 a93 1 } // namespace d108 1 a108 1 CallGraph::~CallGraph() = default; d167 2 a168 2 llvm::ReversePostOrderTraversal RPOT(this); for (llvm::ReversePostOrderTraversal::rpo_iterator d212 2 a213 1 DOTGraphTraits (bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {} d225 1 d227 1 a227 2 } // namespace llvm @ 1.1.1.9 log @Mark old LLVM instance as dead. @ text @@ 1.1.1.3.4.1 log @file CallGraph.cpp was added on branch tls-maxphys on 2014-08-19 23:47:26 +0000 @ text @d1 231 @ 1.1.1.3.4.2 log @Rebase to HEAD as of a few days ago. @ text @a0 231 //== CallGraph.cpp - AST-based Call graph ----------------------*- C++ -*--==// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This file defines the AST-based CallGraph. // //===----------------------------------------------------------------------===// #include "clang/Analysis/CallGraph.h" #include "clang/AST/ASTContext.h" #include "clang/AST/Decl.h" #include "clang/AST/StmtVisitor.h" #include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/Statistic.h" #include "llvm/Support/GraphWriter.h" using namespace clang; #define DEBUG_TYPE "CallGraph" STATISTIC(NumObjCCallEdges, "Number of Objective-C method call edges"); STATISTIC(NumBlockCallEdges, "Number of block call edges"); namespace { /// A helper class, which walks the AST and locates all the call sites in the /// given function body. class CGBuilder : public StmtVisitor { CallGraph *G; CallGraphNode *CallerNode; public: CGBuilder(CallGraph *g, CallGraphNode *N) : G(g), CallerNode(N) {} void VisitStmt(Stmt *S) { VisitChildren(S); } Decl *getDeclFromCall(CallExpr *CE) { if (FunctionDecl *CalleeDecl = CE->getDirectCallee()) return CalleeDecl; // Simple detection of a call through a block. Expr *CEE = CE->getCallee()->IgnoreParenImpCasts(); if (BlockExpr *Block = dyn_cast(CEE)) { NumBlockCallEdges++; return Block->getBlockDecl(); } return nullptr; } void addCalledDecl(Decl *D) { if (G->includeInGraph(D)) { CallGraphNode *CalleeNode = G->getOrInsertNode(D); CallerNode->addCallee(CalleeNode, G); } } void VisitCallExpr(CallExpr *CE) { if (Decl *D = getDeclFromCall(CE)) addCalledDecl(D); } // Adds may-call edges for the ObjC message sends. void VisitObjCMessageExpr(ObjCMessageExpr *ME) { if (ObjCInterfaceDecl *IDecl = ME->getReceiverInterface()) { Selector Sel = ME->getSelector(); // Find the callee definition within the same translation unit. Decl *D = nullptr; if (ME->isInstanceMessage()) D = IDecl->lookupPrivateMethod(Sel); else D = IDecl->lookupPrivateClassMethod(Sel); if (D) { addCalledDecl(D); NumObjCCallEdges++; } } } void VisitChildren(Stmt *S) { for (Stmt::child_range I = S->children(); I; ++I) if (*I) static_cast(this)->Visit(*I); } }; } // end anonymous namespace void CallGraph::addNodesForBlocks(DeclContext *D) { if (BlockDecl *BD = dyn_cast(D)) addNodeForDecl(BD, true); for (auto *I : D->decls()) if (auto *DC = dyn_cast(I)) addNodesForBlocks(DC); } CallGraph::CallGraph() { Root = getOrInsertNode(nullptr); } CallGraph::~CallGraph() { llvm::DeleteContainerSeconds(FunctionMap); } bool CallGraph::includeInGraph(const Decl *D) { assert(D); if (!D->getBody()) return false; if (const FunctionDecl *FD = dyn_cast(D)) { // We skip function template definitions, as their semantics is // only determined when they are instantiated. if (!FD->isThisDeclarationADefinition() || FD->isDependentContext()) return false; IdentifierInfo *II = FD->getIdentifier(); if (II && II->getName().startswith("__inline")) return false; } if (const ObjCMethodDecl *ID = dyn_cast(D)) { if (!ID->isThisDeclarationADefinition()) return false; } return true; } void CallGraph::addNodeForDecl(Decl* D, bool IsGlobal) { assert(D); // Allocate a new node, mark it as root, and process it's calls. CallGraphNode *Node = getOrInsertNode(D); // Process all the calls by this function as well. CGBuilder builder(this, Node); if (Stmt *Body = D->getBody()) builder.Visit(Body); } CallGraphNode *CallGraph::getNode(const Decl *F) const { FunctionMapTy::const_iterator I = FunctionMap.find(F); if (I == FunctionMap.end()) return nullptr; return I->second; } CallGraphNode *CallGraph::getOrInsertNode(Decl *F) { CallGraphNode *&Node = FunctionMap[F]; if (Node) return Node; Node = new CallGraphNode(F); // Make Root node a parent of all functions to make sure all are reachable. if (F) Root->addCallee(Node, this); return Node; } void CallGraph::print(raw_ostream &OS) const { OS << " --- Call graph Dump --- \n"; // We are going to print the graph in reverse post order, partially, to make // sure the output is deterministic. llvm::ReversePostOrderTraversal RPOT(this); for (llvm::ReversePostOrderTraversal::rpo_iterator I = RPOT.begin(), E = RPOT.end(); I != E; ++I) { const CallGraphNode *N = *I; OS << " Function: "; if (N == Root) OS << "< root >"; else N->print(OS); OS << " calls: "; for (CallGraphNode::const_iterator CI = N->begin(), CE = N->end(); CI != CE; ++CI) { assert(*CI != Root && "No one can call the root node."); (*CI)->print(OS); OS << " "; } OS << '\n'; } OS.flush(); } void CallGraph::dump() const { print(llvm::errs()); } void CallGraph::viewGraph() const { llvm::ViewGraph(this, "CallGraph"); } void CallGraphNode::print(raw_ostream &os) const { if (const NamedDecl *ND = dyn_cast_or_null(FD)) return ND->printName(os); os << "< >"; } void CallGraphNode::dump() const { print(llvm::errs()); } namespace llvm { template <> struct DOTGraphTraits : public DefaultDOTGraphTraits { DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} static std::string getNodeLabel(const CallGraphNode *Node, const CallGraph *CG) { if (CG->getRoot() == Node) { return "< root >"; } if (const NamedDecl *ND = dyn_cast_or_null(Node->getDecl())) return ND->getNameAsString(); else return "< >"; } }; } @ 1.1.1.2.4.1 log @file CallGraph.cpp was added on branch yamt-pagecache on 2014-05-22 16:18:26 +0000 @ text @d1 232 @ 1.1.1.2.4.2 log @sync with head. for a reference, the tree before this commit was tagged as yamt-pagecache-tag8. this commit was splitted into small chunks to avoid a limitation of cvs. ("Protocol error: too many arguments") @ text @a0 232 //== CallGraph.cpp - AST-based Call graph ----------------------*- C++ -*--==// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // This file defines the AST-based CallGraph. // //===----------------------------------------------------------------------===// #define DEBUG_TYPE "CallGraph" #include "clang/Analysis/CallGraph.h" #include "clang/AST/ASTContext.h" #include "clang/AST/Decl.h" #include "clang/AST/StmtVisitor.h" #include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/Statistic.h" #include "llvm/Support/GraphWriter.h" using namespace clang; STATISTIC(NumObjCCallEdges, "Number of Objective-C method call edges"); STATISTIC(NumBlockCallEdges, "Number of block call edges"); namespace { /// A helper class, which walks the AST and locates all the call sites in the /// given function body. class CGBuilder : public StmtVisitor { CallGraph *G; CallGraphNode *CallerNode; public: CGBuilder(CallGraph *g, CallGraphNode *N) : G(g), CallerNode(N) {} void VisitStmt(Stmt *S) { VisitChildren(S); } Decl *getDeclFromCall(CallExpr *CE) { if (FunctionDecl *CalleeDecl = CE->getDirectCallee()) return CalleeDecl; // Simple detection of a call through a block. Expr *CEE = CE->getCallee()->IgnoreParenImpCasts(); if (BlockExpr *Block = dyn_cast(CEE)) { NumBlockCallEdges++; return Block->getBlockDecl(); } return 0; } void addCalledDecl(Decl *D) { if (G->includeInGraph(D)) { CallGraphNode *CalleeNode = G->getOrInsertNode(D); CallerNode->addCallee(CalleeNode, G); } } void VisitCallExpr(CallExpr *CE) { if (Decl *D = getDeclFromCall(CE)) addCalledDecl(D); } // Adds may-call edges for the ObjC message sends. void VisitObjCMessageExpr(ObjCMessageExpr *ME) { if (ObjCInterfaceDecl *IDecl = ME->getReceiverInterface()) { Selector Sel = ME->getSelector(); // Find the callee definition within the same translation unit. Decl *D = 0; if (ME->isInstanceMessage()) D = IDecl->lookupPrivateMethod(Sel); else D = IDecl->lookupPrivateClassMethod(Sel); if (D) { addCalledDecl(D); NumObjCCallEdges++; } } } void VisitChildren(Stmt *S) { for (Stmt::child_range I = S->children(); I; ++I) if (*I) static_cast(this)->Visit(*I); } }; } // end anonymous namespace void CallGraph::addNodesForBlocks(DeclContext *D) { if (BlockDecl *BD = dyn_cast(D)) addNodeForDecl(BD, true); for (DeclContext::decl_iterator I = D->decls_begin(), E = D->decls_end(); I!=E; ++I) if (DeclContext *DC = dyn_cast(*I)) addNodesForBlocks(DC); } CallGraph::CallGraph() { Root = getOrInsertNode(0); } CallGraph::~CallGraph() { llvm::DeleteContainerSeconds(FunctionMap); } bool CallGraph::includeInGraph(const Decl *D) { assert(D); if (!D->getBody()) return false; if (const FunctionDecl *FD = dyn_cast(D)) { // We skip function template definitions, as their semantics is // only determined when they are instantiated. if (!FD->isThisDeclarationADefinition() || FD->isDependentContext()) return false; IdentifierInfo *II = FD->getIdentifier(); if (II && II->getName().startswith("__inline")) return false; } if (const ObjCMethodDecl *ID = dyn_cast(D)) { if (!ID->isThisDeclarationADefinition()) return false; } return true; } void CallGraph::addNodeForDecl(Decl* D, bool IsGlobal) { assert(D); // Allocate a new node, mark it as root, and process it's calls. CallGraphNode *Node = getOrInsertNode(D); // Process all the calls by this function as well. CGBuilder builder(this, Node); if (Stmt *Body = D->getBody()) builder.Visit(Body); } CallGraphNode *CallGraph::getNode(const Decl *F) const { FunctionMapTy::const_iterator I = FunctionMap.find(F); if (I == FunctionMap.end()) return 0; return I->second; } CallGraphNode *CallGraph::getOrInsertNode(Decl *F) { CallGraphNode *&Node = FunctionMap[F]; if (Node) return Node; Node = new CallGraphNode(F); // Make Root node a parent of all functions to make sure all are reachable. if (F != 0) Root->addCallee(Node, this); return Node; } void CallGraph::print(raw_ostream &OS) const { OS << " --- Call graph Dump --- \n"; // We are going to print the graph in reverse post order, partially, to make // sure the output is deterministic. llvm::ReversePostOrderTraversal RPOT(this); for (llvm::ReversePostOrderTraversal::rpo_iterator I = RPOT.begin(), E = RPOT.end(); I != E; ++I) { const CallGraphNode *N = *I; OS << " Function: "; if (N == Root) OS << "< root >"; else N->print(OS); OS << " calls: "; for (CallGraphNode::const_iterator CI = N->begin(), CE = N->end(); CI != CE; ++CI) { assert(*CI != Root && "No one can call the root node."); (*CI)->print(OS); OS << " "; } OS << '\n'; } OS.flush(); } void CallGraph::dump() const { print(llvm::errs()); } void CallGraph::viewGraph() const { llvm::ViewGraph(this, "CallGraph"); } void CallGraphNode::print(raw_ostream &os) const { if (const NamedDecl *ND = dyn_cast_or_null(FD)) return ND->printName(os); os << "< >"; } void CallGraphNode::dump() const { print(llvm::errs()); } namespace llvm { template <> struct DOTGraphTraits : public DefaultDOTGraphTraits { DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} static std::string getNodeLabel(const CallGraphNode *Node, const CallGraph *CG) { if (CG->getRoot() == Node) { return "< root >"; } if (const NamedDecl *ND = dyn_cast_or_null(Node->getDecl())) return ND->getNameAsString(); else return "< >"; } }; } @