ROSE  0.9.9.109
CallGraph.h
1 
2 #ifndef CALL_GRAPH_H
3 #define CALL_GRAPH_H
4 
5 #include <AstInterface.h>
6 #include <GraphDotOutput.h>
7 #include <VirtualGraphCreate.h>
8 
9 #include "AstDiagnostics.h"
10 
11 #include <sstream>
12 #include <iostream>
13 #include <string>
14 #include <functional>
15 #include <queue>
16 #include <boost/foreach.hpp>
17 #include <boost/unordered_map.hpp>
18 
19 class FunctionData;
20 
21 typedef Rose_STL_Container<SgFunctionDeclaration *> SgFunctionDeclarationPtrList;
22 typedef Rose_STL_Container<SgClassDefinition *> SgClassDefinitionPtrList;
23 
24 // DQ (1/31/2006): Changed name and made global function type symbol table a static data member.
25 // extern SgFunctionTypeTable Sgfunc_type_table;
26 // This header has to be here since it uses type SgFunctionDeclarationPtrList
27 #include "ClassHierarchyGraph.h"
28 
29 
30 //AS(090707) Added the CallTargetSet namespace to replace the CallGraphFunctionSolver class
31 namespace CallTargetSet
32 {
33  typedef Rose_STL_Container<SgFunctionDeclaration *> SgFunctionDeclarationPtrList;
34  typedef Rose_STL_Container<SgClassDefinition *> SgClassDefinitionPtrList;
35  // returns the list of declarations of all functions that may get called via the specified pointer
36  std::vector<SgFunctionDeclaration*> solveFunctionPointerCall ( SgPointerDerefExp *, SgProject * );
37 
38  // returns the list of declarations of all functions that may get called via a member function pointer
39  std::vector<SgFunctionDeclaration*> solveMemberFunctionPointerCall ( SgExpression *,ClassHierarchyWrapper * );
40  Rose_STL_Container<SgFunctionDeclaration*> solveFunctionPointerCallsFunctional(SgNode* node, SgFunctionType* functionType );
41 
42  // returns the list of declarations of all functions that may get called via a
43  // member function (non/polymorphic) call
44  std::vector<SgFunctionDeclaration*> solveMemberFunctionCall (
45  SgClassType *, ClassHierarchyWrapper *, SgMemberFunctionDeclaration *, bool , bool includePureVirtualFunc = false );
46 
51  std::vector<SgFunctionDeclaration*> solveConstructorInitializer ( SgConstructorInitializer* sgCtorInit);
52 
53  // Populates functionList with Properties of all functions that may get called.
54  ROSE_DLL_API void getPropertiesForExpression(SgExpression* exp,
55  ClassHierarchyWrapper* classHierarchy,
56  Rose_STL_Container<SgFunctionDeclaration*>& propList,
57  bool includePureVirtualFunc = false);
58 
63  void getDefinitionsForExpression(SgExpression* exp,
64  ClassHierarchyWrapper* classHierarchy,
65  Rose_STL_Container<SgFunctionDefinition*>& calleeList);
66 
69  void getDeclarationsForExpression(SgExpression* exp,
70  ClassHierarchyWrapper* classHierarchy,
71  Rose_STL_Container<SgFunctionDeclaration*>& calleeList,
72  bool includePureVirtualFunc = false);
73 
74  // Gets a vector of SgExpressions that are associated with the current SgFunctionDefinition.
75  // This functionality is necessary for virtual, interprocedural control flow graphs. However,
76  // it is costly and should be used infrequently (or optimized!).
77  void getExpressionsForDefinition(SgFunctionDefinition* targetDef,
78  ClassHierarchyWrapper* classHierarchy,
79  Rose_STL_Container<SgExpression*>& exps);
80 
81  // Gets the latest implementation of the member function from the ancestor hierarchy
82  SgFunctionDeclaration * getFirstVirtualFunctionDefinitionFromAncestors(SgClassType *crtClass,
83  SgMemberFunctionDeclaration *memberFunctionDeclaration,
84  ClassHierarchyWrapper *classHierarchy);
85 
86 };
87 
88 class ROSE_DLL_API FunctionData
89 {
90  public:
91 
92  bool hasDefinition;
93 
94  bool isDefined ();
95 
96  FunctionData(SgFunctionDeclaration* functionDeclaration, SgProject *project, ClassHierarchyWrapper * );
97 
99  Rose_STL_Container<SgFunctionDeclaration *> functionList;
100 
101  SgFunctionDeclaration* functionDeclaration;
102 
103  Rose_STL_Container<SgMemberFunctionDeclaration*> *findPointsToVirtualFunctions ( SgMemberFunctionDeclaration * );
104  bool compareFunctionDeclarations( SgFunctionDeclaration *f1, SgFunctionDeclaration *f2 );
105 };
106 
108 struct dummyFilter : public std::unary_function<bool,SgFunctionDeclaration*>
109 {
110  bool operator() (SgFunctionDeclaration* node) const; // always return true
111 };
112 
114 // Liao, 6/17/2012
115 struct ROSE_DLL_API builtinFilter : public std::unary_function<bool,SgFunctionDeclaration*>
116 {
117  bool operator() (SgFunctionDeclaration* node) const;
118 };
119 
120 class ROSE_DLL_API CallGraphBuilder
121 {
122  public:
123  CallGraphBuilder( SgProject *proj);
125  void buildCallGraph();
127  template<typename Predicate>
128  void buildCallGraph(Predicate pred);
130  SgIncidenceDirectedGraph *getGraph();
131  //void classifyCallGraph();
132 
133  //We map each function to the corresponding graph node
134  boost::unordered_map<SgFunctionDeclaration*, SgGraphNode*>& getGraphNodesMapping(){ return graphNodes; }
135 
136  private:
137  SgProject *project;
139  //We map each function to the corresponding graph node
140  typedef boost::unordered_map<SgFunctionDeclaration*, SgGraphNode*> GraphNodes;
141  GraphNodes graphNodes;
142 
143 };
145 //TODO this function is not defined? If so, need to be removed.
146 // AstDOTGeneration::writeIncidenceGraphToDOTFile() is used instead in the tutorial. Liao 6/17/2012
147 void GenerateDotGraph ( SgIncidenceDirectedGraph *graph, std::string fileName );
148 
149 class ROSE_DLL_API GetOneFuncDeclarationPerFunction : public std::unary_function<SgNode*, Rose_STL_Container<SgNode*> >
150 {
151  public:
152  result_type operator()(SgNode* node );
153 };
154 
155 template<typename Predicate>
156 void
158 {
159  // Adds additional constraints to the predicate. It makes no sense to analyze non-instantiated templates.
160  struct isSelected {
161  Predicate &pred;
162  isSelected(Predicate &pred): pred(pred) {}
163  bool operator()(SgNode *node) {
164  SgFunctionDeclaration *f = isSgFunctionDeclaration(node);
165  assert(!f || f==f->get_firstNondefiningDeclaration()); // node uniqueness test
166 #if 0
167  // DQ (8/25/2016): This is not a meaningful test since all functions will be in the memory pool, including template functions and template member functions.
168  if(isSgTemplateFunctionDeclaration(f)||isSgTemplateMemberFunctionDeclaration(f)) {
169  std::cerr<<"Error: CallGraphBuilder: call referring to node "<<f->class_name()<<" :: function-name:"<<f->get_qualified_name()<<std::endl;
170  }
171 #endif
172  return f && !isSgTemplateMemberFunctionDeclaration(f) && !isSgTemplateFunctionDeclaration(f) && pred(f);
173  }
174  };
175 
176  // Add nodes to the graph by querying the memory pool for function declarations, mapping them to unique declarations
177  // that can be used as keys in a map (using get_firstNondefiningDeclaration()), and filtering according to the predicate.
178  graph = new SgIncidenceDirectedGraph();
179  std::vector<FunctionData> callGraphData;
180  ClassHierarchyWrapper classHierarchy(project);
181  graphNodes.clear();
182  VariantVector vv(V_SgFunctionDeclaration);
184  std::vector<SgNode*> fdecl_nodes = NodeQuery::queryMemoryPool(defFunc, &vv);
185  BOOST_FOREACH(SgNode *node, fdecl_nodes) {
186  SgFunctionDeclaration *fdecl = isSgFunctionDeclaration(node);
187  SgFunctionDeclaration *unique = isSgFunctionDeclaration(fdecl->get_firstNondefiningDeclaration());
188 #if 0
189  printf ("In buildCallGraph(): loop over functions from memory pool: fdecl = %p = %s name = %s \n",fdecl,fdecl->class_name().c_str(),fdecl->get_name().str());
190  printf ("In buildCallGraph(): loop over functions from memory pool: unique = %p = %s name = %s \n",unique,unique->class_name().c_str(),unique->get_name().str());
191 #endif
192  if (isSelected(pred)(unique) && graphNodes.find(unique)==graphNodes.end())
193  {
194 #if 0
195  printf ("Collect function calls in unique function: unique = %p \n",unique);
196 #endif
197  FunctionData fdata(unique, project, &classHierarchy); // computes functions called by unique
198  callGraphData.push_back(fdata);
199  std::string functionName = unique->get_qualified_name().getString();
200  SgGraphNode *graphNode = new SgGraphNode(functionName);
201  graphNode->set_SgNode(unique);
202  graphNodes[unique] = graphNode;
203  graph->addNode(graphNode);
204  }
205  else
206  {
207 #if 0
208  printf ("Function not selected for processing: unique = %p \n",unique);
209  printf (" --- isSelected(pred)(unique) = %s \n",isSelected(pred)(unique) ? "true" : "false");
210  printf (" --- graphNodes.find(unique)==graphNodes.end() = %s \n",graphNodes.find(unique)==graphNodes.end() ? "true" : "false");
211 #endif
212  }
213  }
214 
215  // Add edges to the graph
216  BOOST_FOREACH(FunctionData &currentFunction, callGraphData) {
217  SgGraphNode *srcNode = graphNodes.find(currentFunction.functionDeclaration)->second; // we inserted it above
218  std::vector<SgFunctionDeclaration*> &callees = currentFunction.functionList;
219  BOOST_FOREACH(SgFunctionDeclaration *callee, callees) {
220  if (isSelected(pred)(callee)) {
221  GraphNodes::iterator dstNodeFound = graphNodes.find(callee);
222  assert(dstNodeFound!=graphNodes.end()); // should have been added above
223  SgGraphNode *dstNode = dstNodeFound->second;
224  if (graph->checkIfDirectedGraphEdgeExists(srcNode, dstNode) == false)
225  graph->addDirectedEdge(srcNode, dstNode);
226  }
227  }
228  }
229 }
230 
231 // endif for CALL_GRAPH_H
232 #endif
233 
A function object to filter out builtin functions in a call graph (only non-builtin functions will be...
Definition: CallGraph.h:115
Rose_STL_Container< SgFunctionDeclaration * > functionList
All the callees of this function.
Definition: CallGraph.h:99
This class represents the concept of a member function declaration statement.
This class represents the concept of a function declaration statement.
This class represents the concept of a scope in C++ (e.g. global scope, fuction scope, etc.).
void buildCallGraph()
Default builder filtering nothing in the call graph.
This class represents the notion of an expression. Expressions are derived from SgLocatedNodes, since similar to statement, expressions have a concrete location within the user's source code.
This class represents the base class for all IR nodes within Sage III.
Definition: Cxx_Grammar.h:8322
SgGraphNode * addNode(const std::string &name="", SgNode *sg_node=NULL)
Support for adding SgGraphNode to SgGraph.
SgDirectedGraphEdge * addDirectedEdge(SgGraphNode *a, SgGraphNode *b, const std::string &name="")
Support for adding SgGraphEdge to SgGraph.
This class represents a type for all functions.
virtual std::string class_name() const ROSE_OVERRIDE
returns a string representing the class name
This class represents a source project, with a list of SgFile objects and global information about th...
A function object to be used as a predicate to filter out functions in a call graph: it does not filt...
Definition: CallGraph.h:108
This class represents the notion of an initializer for a variable declaration or expression in a func...
SgDeclarationStatement * get_firstNondefiningDeclaration() const
This is an access function for the SgDeclarationStatement::p_firstNondefiningDeclaration data member ...