diff options
| -rw-r--r-- | include/clang/Analysis/CallGraph.h | 216 | ||||
| -rw-r--r-- | lib/Analysis/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | lib/Analysis/CallGraph.cpp | 207 | ||||
| -rw-r--r-- | lib/StaticAnalyzer/Checkers/Checkers.td | 8 | ||||
| -rw-r--r-- | lib/StaticAnalyzer/Checkers/DebugCheckers.cpp | 41 | ||||
| -rw-r--r-- | test/Analysis/debug-CallGraph.c | 21 |
6 files changed, 494 insertions, 0 deletions
diff --git a/include/clang/Analysis/CallGraph.h b/include/clang/Analysis/CallGraph.h new file mode 100644 index 0000000000..156f890e4b --- /dev/null +++ b/include/clang/Analysis/CallGraph.h @@ -0,0 +1,216 @@ +//== CallGraph.h - 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 declares the AST-based CallGraph. +// +// A call graph for functions whose definitions/bodies are available in the +// current translation unit. The graph has a "virtual" root node that contains +// edges to all externally available functions. +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_CALLGRAPH +#define LLVM_CLANG_ANALYSIS_CALLGRAPH + +#include "clang/AST/DeclBase.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/SetVector.h" + +namespace clang { +class CallGraphNode; + +class CallGraph { + friend class CallGraphNode; + typedef llvm::DenseMap<Decl *, CallGraphNode *> FunctionMapTy; + + /// FunctionMap owns all CallGraphNodes. + FunctionMapTy FunctionMap; + + /// This is a virtual root node that has edges to all the global functions - + /// 'main' or functions accessible from other translation units. + CallGraphNode *Root; + + /// The list of nodes that have no parent. These are unreachable from Root. + /// Declarations can get to this list due to impressions in the graph, for + /// example, we do not track functions whose addresses were taken. + llvm::SetVector<CallGraphNode *> ParentlessNodes; + +public: + CallGraph(); + ~CallGraph(); + + /// \brief Add the given declaration to the call graph. + void addToCallGraph(Decl *D, bool IsGlobal); + + /// \brief Populate the call graph with the functions in the given DeclContext. + void addToCallGraph(DeclContext *DC); + + /// \brief Lookup the node for the given declaration. If none found, insert + /// one into the graph. + CallGraphNode *getOrInsertFunction(Decl *); + + /// Iterators through all the elements in the graph. Note, this gives + /// non-deterministic order. + typedef FunctionMapTy::iterator iterator; + typedef FunctionMapTy::const_iterator const_iterator; + iterator begin() { return FunctionMap.begin(); } + iterator end() { return FunctionMap.end(); } + const_iterator begin() const { return FunctionMap.begin(); } + const_iterator end() const { return FunctionMap.end(); } + + /// \brief Get the number of nodes in the graph. + unsigned size() const { return FunctionMap.size(); } + + /// \ brief Get the virtual root of the graph, all the functions available + /// externally are represented as callees of the node. + CallGraphNode *getRoot() const { return Root; } + + /// Iterators through all the nodes of the graph that have no parent. These + /// are the unreachable nodes, which are either unused or are due to us + /// failing to add a call edge due to the analysis imprecision. + typedef llvm::SetVector<CallGraphNode *>::iterator nodes_iterator; + typedef llvm::SetVector<CallGraphNode *>::const_iterator const_nodes_iterator; + nodes_iterator parentless_begin() { return ParentlessNodes.begin(); } + nodes_iterator parentless_end() { return ParentlessNodes.end(); } + const_nodes_iterator + parentless_begin() const { return ParentlessNodes.begin(); } + const_nodes_iterator + parentless_end() const { return ParentlessNodes.end(); } + + void print(raw_ostream &os) const; + void dump() const; + void viewGraph() const; +}; + +class CallGraphNode { +public: + typedef CallGraphNode* CallRecord; + +private: + /// \brief The function/method declaration. + Decl *FD; + + /// \brief The list of functions called from this node. + // Small vector might be more efficient since we are only tracking functions + // whose definition is in the current TU. + llvm::SmallVector<CallRecord, 5> CalledFunctions; + +public: + CallGraphNode(Decl *D) : FD(D) {} + + typedef llvm::SmallVector<CallRecord, 5>::iterator iterator; + typedef llvm::SmallVector<CallRecord, 5>::const_iterator const_iterator; + + /// Iterators through all the callees/children of the node. + inline iterator begin() { return CalledFunctions.begin(); } + inline iterator end() { return CalledFunctions.end(); } + inline const_iterator begin() const { return CalledFunctions.begin(); } + inline const_iterator end() const { return CalledFunctions.end(); } + + inline bool empty() const {return CalledFunctions.empty(); } + inline unsigned size() const {return CalledFunctions.size(); } + + void addCallee(CallGraphNode *N, CallGraph *CG) { + CalledFunctions.push_back(N); + CG->ParentlessNodes.remove(N); + } + + Decl *getDecl() const { return FD; } + + StringRef getName() const; + + void print(raw_ostream &os) const; + void dump() const; +}; + +} // end clang namespace + +// Graph traits for iteration, viewing. +namespace llvm { +template <> struct GraphTraits<clang::CallGraphNode*> { + typedef clang::CallGraphNode NodeType; + typedef clang::CallGraphNode::CallRecord CallRecordTy; + typedef std::pointer_to_unary_function<CallRecordTy, + clang::CallGraphNode*> CGNDerefFun; + static NodeType *getEntryNode(clang::CallGraphNode *CGN) { return CGN; } + typedef mapped_iterator<NodeType::iterator, CGNDerefFun> ChildIteratorType; + static inline ChildIteratorType child_begin(NodeType *N) { + return map_iterator(N->begin(), CGNDerefFun(CGNDeref)); + } + static inline ChildIteratorType child_end (NodeType *N) { + return map_iterator(N->end(), CGNDerefFun(CGNDeref)); + } + static clang::CallGraphNode *CGNDeref(CallRecordTy P) { + return P; + } +}; + +template <> struct GraphTraits<const clang::CallGraphNode*> { + typedef const clang::CallGraphNode NodeType; + typedef NodeType::const_iterator ChildIteratorType; + static NodeType *getEntryNode(const clang::CallGraphNode *CGN) { return CGN; } + static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();} + static inline ChildIteratorType child_end (NodeType *N) { return N->end(); } +}; + +template <> struct GraphTraits<clang::CallGraph*> + : public GraphTraits<clang::CallGraphNode*> { + + static NodeType *getEntryNode(clang::CallGraph *CGN) { + return CGN->getRoot(); // Start at the external node! + } + typedef std::pair<clang::Decl*, clang::CallGraphNode*> PairTy; + typedef std::pointer_to_unary_function<PairTy, clang::CallGraphNode&> DerefFun; + // nodes_iterator/begin/end - Allow iteration over all nodes in the graph + typedef mapped_iterator<clang::CallGraph::iterator, DerefFun> nodes_iterator; + + static nodes_iterator nodes_begin(clang::CallGraph *CG) { + return map_iterator(CG->begin(), DerefFun(CGdereference)); + } + static nodes_iterator nodes_end (clang::CallGraph *CG) { + return map_iterator(CG->end(), DerefFun(CGdereference)); + } + static clang::CallGraphNode &CGdereference(PairTy P) { + return *(P.second); + } + + static unsigned size(clang::CallGraph *CG) { + return CG->size(); + } +}; + +template <> struct GraphTraits<const clang::CallGraph*> : + public GraphTraits<const clang::CallGraphNode*> { + static NodeType *getEntryNode(const clang::CallGraph *CGN) { + return CGN->getRoot(); + } + typedef std::pair<clang::Decl*, clang::CallGraphNode*> PairTy; + typedef std::pointer_to_unary_function<PairTy, clang::CallGraphNode&> DerefFun; + // nodes_iterator/begin/end - Allow iteration over all nodes in the graph + typedef mapped_iterator<clang::CallGraph::const_iterator, + DerefFun> nodes_iterator; + + static nodes_iterator nodes_begin(const clang::CallGraph *CG) { + return map_iterator(CG->begin(), DerefFun(CGdereference)); + } + static nodes_iterator nodes_end(const clang::CallGraph *CG) { + return map_iterator(CG->end(), DerefFun(CGdereference)); + } + static clang::CallGraphNode &CGdereference(PairTy P) { + return *(P.second); + } + + static unsigned size(const clang::CallGraph *CG) { + return CG->size(); + } +}; + +} // end llvm namespace + +#endif diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt index 4b88ad279a..43c3ffbaf1 100644 --- a/lib/Analysis/CMakeLists.txt +++ b/lib/Analysis/CMakeLists.txt @@ -2,6 +2,7 @@ set(LLVM_USED_LIBS clangBasic clangAST clangIndex) add_clang_library(clangAnalysis AnalysisDeclContext.cpp + CallGraph.cpp CFG.cpp CFGReachabilityAnalysis.cpp CFGStmtMap.cpp diff --git a/lib/Analysis/CallGraph.cpp b/lib/Analysis/CallGraph.cpp new file mode 100644 index 0000000000..2aaeaf132d --- /dev/null +++ b/lib/Analysis/CallGraph.cpp @@ -0,0 +1,207 @@ +//== 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/Support/GraphWriter.h" + +using namespace clang; + +/// Determine if a declaration should be included in the graph. +static bool includeInGraph(const Decl *D) { + if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(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<ObjCMethodDecl>(D)) { + if (!ID->isThisDeclarationADefinition()) + return false; + } + + return true; +} + +namespace { +/// A helper class, which walks the AST and locates all the call sites in the +/// given function body. +class CGBuilder : public StmtVisitor<CGBuilder> { + CallGraph *G; + const Decl *FD; + CallGraphNode *CallerNode; + +public: + CGBuilder(CallGraph *g, const Decl *D, CallGraphNode *N) + : G(g), FD(D), CallerNode(N) {} + + void VisitStmt(Stmt *S) { VisitChildren(S); } + + void VisitCallExpr(CallExpr *CE) { + // TODO: We need to handle ObjC method calls as well. + if (FunctionDecl *CalleeDecl = CE->getDirectCallee()) + if (includeInGraph(CalleeDecl)) { + CallGraphNode *CalleeNode = G->getOrInsertFunction(CalleeDecl); + CallerNode->addCallee(CalleeNode, G); + } + }; + + void VisitChildren(Stmt *S) { + for (Stmt::child_range I = S->children(); I; ++I) + if (*I) + static_cast<CGBuilder*>(this)->Visit(*I); + } +}; +} // end anonymous namespace + +CallGraph::CallGraph() { + Root = getOrInsertFunction(0); +} + +CallGraph::~CallGraph() { + if (!FunctionMap.empty()) { + for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); + I != E; ++I) + delete I->second; + FunctionMap.clear(); + } +} + +void CallGraph::addToCallGraph(Decl* D, bool IsGlobal) { + CallGraphNode *Node = getOrInsertFunction(D); + + if (IsGlobal) + Root->addCallee(Node, this); + + // Process all the calls by this function as well. + CGBuilder builder(this, D, Node); + builder.Visit(D->getBody()); +} + +void CallGraph::addToCallGraph(DeclContext *DC) { + for (DeclContext::decl_iterator I = DC->decls_begin(), E = DC->decls_end(); + I != E; ++I) { + Decl *D = *I; + switch (D->getKind()) { + case Decl::CXXConstructor: + case Decl::CXXDestructor: + case Decl::CXXConversion: + case Decl::CXXMethod: + case Decl::Function: { + FunctionDecl *FD = cast<FunctionDecl>(D); + // We skip function template definitions, as their semantics is + // only determined when they are instantiated. + if (includeInGraph(FD)) + // If this function has external linkage, anything could call it. + // Note, we are not precise here. For example, the function could have + // its address taken. + addToCallGraph(FD, FD->isGlobal()); + break; + } + + case Decl::ObjCCategoryImpl: + case Decl::ObjCImplementation: { + ObjCImplDecl *ID = cast<ObjCImplDecl>(D); + for (ObjCContainerDecl::method_iterator MI = ID->meth_begin(), + ME = ID->meth_end(); MI != ME; ++MI) { + if (includeInGraph(*MI)) + addToCallGraph(*MI, true); + } + break; + } + + default: + break; + } + } +} + +CallGraphNode *CallGraph::getOrInsertFunction(Decl *F) { + CallGraphNode *&Node = FunctionMap[F]; + if (Node) + return Node; + + Node = new CallGraphNode(F); + ParentlessNodes.insert(Node); + return Node; +} + +void CallGraph::print(raw_ostream &OS) const { + OS << " --- Call graph Dump --- \n"; + for (const_iterator I = begin(), E = end(); I != E; ++I) { + OS << " Function: "; + if (I->second == Root) + OS << "< root >"; + else + I->second->print(OS); + OS << " calls: "; + for (CallGraphNode::iterator CI = I->second->begin(), + CE = I->second->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"); +} + +StringRef CallGraphNode::getName() const { + if (const FunctionDecl *D = dyn_cast_or_null<FunctionDecl>(FD)) + if (const IdentifierInfo *II = D->getIdentifier()) + return II->getName(); + return "< >"; +} + +void CallGraphNode::print(raw_ostream &os) const { + os << getName(); +} + +void CallGraphNode::dump() const { + print(llvm::errs()); +} + +namespace llvm { + +template <> +struct DOTGraphTraits<const CallGraph*> : public DefaultDOTGraphTraits { + + DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} + + static std::string getNodeLabel(const CallGraphNode *Node, + const CallGraph *CG) { + if (CG->getRoot() == Node) { + return "< root >"; + } + return Node->getName(); + } + +}; +} diff --git a/lib/StaticAnalyzer/Checkers/Checkers.td b/lib/StaticAnalyzer/Checkers/Checkers.td index cf8b884f7a..96a8d26c34 100644 --- a/lib/StaticAnalyzer/Checkers/Checkers.td +++ b/lib/StaticAnalyzer/Checkers/Checkers.td @@ -467,6 +467,14 @@ def CFGDumper : Checker<"DumpCFG">, HelpText<"Display Control-Flow Graphs">, DescFile<"DebugCheckers.cpp">; +def CallGraphViewer : Checker<"ViewCallGraph">, + HelpText<"View Call Graph using GraphViz">, + DescFile<"DebugCheckers.cpp">; + +def CallGraphDumper : Checker<"DumpCallGraph">, + HelpText<"Display Call Graph">, + DescFile<"DebugCheckers.cpp">; + def AnalyzerStatsChecker : Checker<"Stats">, HelpText<"Emit warnings with analyzer statistics">, DescFile<"AnalyzerStatsChecker.cpp">; diff --git a/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp b/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp index d7e7af1c8e..900c305543 100644 --- a/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp +++ b/lib/StaticAnalyzer/Checkers/DebugCheckers.cpp @@ -16,6 +16,7 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" #include "clang/Analysis/Analyses/LiveVariables.h" #include "clang/Analysis/Analyses/Dominators.h" +#include "clang/Analysis/CallGraph.h" #include "llvm/Support/Process.h" using namespace clang; @@ -103,3 +104,43 @@ public: void ento::registerCFGDumper(CheckerManager &mgr) { mgr.registerChecker<CFGDumper>(); } + +//===----------------------------------------------------------------------===// +// CallGraphViewer +//===----------------------------------------------------------------------===// + +namespace { +class CallGraphViewer : public Checker< check::ASTDecl<TranslationUnitDecl> > { +public: + void checkASTDecl(const TranslationUnitDecl *TU, AnalysisManager& mgr, + BugReporter &BR) const { + CallGraph CG; + CG.addToCallGraph(const_cast<TranslationUnitDecl*>(TU)); + CG.viewGraph(); + } +}; +} + +void ento::registerCallGraphViewer(CheckerManager &mgr) { + mgr.registerChecker<CallGraphViewer>(); +} + +//===----------------------------------------------------------------------===// +// CallGraphDumper +//===----------------------------------------------------------------------===// + +namespace { +class CallGraphDumper : public Checker< check::ASTDecl<TranslationUnitDecl> > { +public: + void checkASTDecl(const TranslationUnitDecl *TU, AnalysisManager& mgr, + BugReporter &BR) const { + CallGraph CG; + CG.addToCallGraph(const_cast<TranslationUnitDecl*>(TU)); + CG.dump(); + } +}; +} + +void ento::registerCallGraphDumper(CheckerManager &mgr) { + mgr.registerChecker<CallGraphDumper>(); +} diff --git a/test/Analysis/debug-CallGraph.c b/test/Analysis/debug-CallGraph.c new file mode 100644 index 0000000000..b7c7c8a844 --- /dev/null +++ b/test/Analysis/debug-CallGraph.c @@ -0,0 +1,21 @@ +// RUN: %clang_cc1 -analyze -analyzer-checker=debug.DumpCallGraph %s 2>&1 | FileCheck %s + +static void mmm(int y) { + if (y != 0) + y++; + y = y/0; +} + +static int foo(int x, int y) { + mmm(y); + if (x != 0) + x++; + return 5/x; +} + +void aaa() { + foo(1,2); +} + +// CHECK:--- Call graph Dump --- +// CHECK: Function: < root > calls: aaa |