ROSE  0.11.101.0
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;
47  std::vector<SgFunctionDeclaration*> solveFunctionPointerCall ( SgPointerDerefExp *);
48 
49  // returns the list of declarations of all functions that may get called via a member function pointer
50  std::vector<SgFunctionDeclaration*> solveMemberFunctionPointerCall ( SgExpression *,ClassHierarchyWrapper * );
51 
66  Rose_STL_Container<SgFunctionDeclaration*> solveFunctionPointerCallsFunctional(SgNode* node, SgFunctionType* functionType );
67 
68  // returns the list of declarations of all functions that may get called via a
69  // member function (non/polymorphic) call
70  std::vector<SgFunctionDeclaration*> solveMemberFunctionCall (
71  SgClassType *, ClassHierarchyWrapper *, SgMemberFunctionDeclaration *, bool , bool includePureVirtualFunc = false );
72 
74  std::vector<SgFunctionDeclaration*> solveConstructorInitializer ( SgConstructorInitializer* sgCtorInit);
75 
76  // Populates functionList with Properties of all functions that may get called.
77  ROSE_DLL_API void getPropertiesForExpression(SgExpression* exp,
78  ClassHierarchyWrapper* classHierarchy,
79  Rose_STL_Container<SgFunctionDeclaration*>& propList,
80  bool includePureVirtualFunc = false);
81 
86  void getDefinitionsForExpression(SgExpression* exp,
87  ClassHierarchyWrapper* classHierarchy,
88  Rose_STL_Container<SgFunctionDefinition*>& calleeList);
89 
92  void getDeclarationsForExpression(SgExpression* exp,
93  ClassHierarchyWrapper* classHierarchy,
94  Rose_STL_Container<SgFunctionDeclaration*>& calleeList,
95  bool includePureVirtualFunc = false);
96 
97  // Gets a vector of SgExpressions that are associated with the current SgFunctionDefinition.
98  // This functionality is necessary for virtual, interprocedural control flow graphs. However,
99  // it is costly and should be used infrequently (or optimized!).
100  void getExpressionsForDefinition(SgFunctionDefinition* targetDef,
101  ClassHierarchyWrapper* classHierarchy,
102  Rose_STL_Container<SgExpression*>& exps);
103 
104  // Gets the latest implementation of the member function from the ancestor hierarchy
105  SgFunctionDeclaration * getFirstVirtualFunctionDefinitionFromAncestors(SgClassType *crtClass,
106  SgMemberFunctionDeclaration *memberFunctionDeclaration,
107  ClassHierarchyWrapper *classHierarchy);
108 
109 };
110 
111 class ROSE_DLL_API FunctionData
112 {
113  public:
114 
115  bool hasDefinition;
116 
117  bool isDefined ();
118 
119  FunctionData(SgFunctionDeclaration* functionDeclaration, SgProject *project, ClassHierarchyWrapper * );
120 
122  Rose_STL_Container<SgFunctionDeclaration *> functionList;
123 
124  SgFunctionDeclaration* functionDeclaration;
125 
126  Rose_STL_Container<SgMemberFunctionDeclaration*> *findPointsToVirtualFunctions ( SgMemberFunctionDeclaration * );
127  bool compareFunctionDeclarations( SgFunctionDeclaration *f1, SgFunctionDeclaration *f2 );
128 };
129 
131 struct dummyFilter : public std::unary_function<bool,SgFunctionDeclaration*>
132 {
133  bool operator() (SgFunctionDeclaration* node) const; // always return true
134 };
135 
137 // Liao, 6/17/2012
138 struct ROSE_DLL_API builtinFilter : public std::unary_function<bool,SgFunctionDeclaration*>
139 {
140  bool operator() (SgFunctionDeclaration* node) const;
141 };
142 
143 class ROSE_DLL_API CallGraphBuilder
144 {
145  public:
146  CallGraphBuilder( SgProject *proj);
148  void buildCallGraph();
150  template<typename Predicate>
151  void buildCallGraph(Predicate pred);
153  SgIncidenceDirectedGraph *getGraph();
154  //void classifyCallGraph();
155 
156  //We map each function to the corresponding graph node
157  boost::unordered_map<SgFunctionDeclaration*, SgGraphNode*>& getGraphNodesMapping(){ return graphNodes; }
158 
160  SgGraphNode * hasGraphNodeFor(SgFunctionDeclaration * fdecl) const;
162  SgGraphNode * getGraphNodeFor(SgFunctionDeclaration * fdecl) const;
163 
164  private:
165  SgProject *project;
167  //We map each function to the corresponding graph node
168  typedef boost::unordered_map<SgFunctionDeclaration*, SgGraphNode*> GraphNodes;
169  GraphNodes graphNodes;
170 
171 };
173 //TODO this function is not defined? If so, need to be removed.
174 // AstDOTGeneration::writeIncidenceGraphToDOTFile() is used instead in the tutorial. Liao 6/17/2012
175 void GenerateDotGraph ( SgIncidenceDirectedGraph *graph, std::string fileName );
176 
177 class ROSE_DLL_API GetOneFuncDeclarationPerFunction : public std::unary_function<SgNode*, Rose_STL_Container<SgNode*> >
178 {
179  public:
180  result_type operator()(SgNode* node );
181 };
182 
183 template<typename Predicate>
184 void
186 {
187  // Adds additional constraints to the predicate. It makes no sense to analyze non-instantiated templates.
188  struct isSelected {
189  Predicate &pred;
190  isSelected(Predicate &pred): pred(pred) {}
191  bool operator()(SgNode *node) {
192  SgFunctionDeclaration *f = isSgFunctionDeclaration(node);
193  // TV (10/26/2018): FIXME ROSE-1487
194  // assert(!f || f==f->get_firstNondefiningDeclaration()); // node uniqueness test
195 #if 0
196  // 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.
197  if(isSgTemplateFunctionDeclaration(f)||isSgTemplateMemberFunctionDeclaration(f)) {
198  std::cerr<<"Error: CallGraphBuilder: call referring to node "<<f->class_name()<<" :: function-name:"<<f->get_qualified_name()<<std::endl;
199  }
200 #endif
201  return f && f==f->get_firstNondefiningDeclaration() && !isSgTemplateMemberFunctionDeclaration(f) && !isSgTemplateFunctionDeclaration(f) && pred(f);
202  }
203  };
204 
205  // Add nodes to the graph by querying the memory pool for function declarations, mapping them to unique declarations
206  // that can be used as keys in a map (using get_firstNondefiningDeclaration()), and filtering according to the predicate.
207  graph = new SgIncidenceDirectedGraph();
208  std::vector<FunctionData> callGraphData;
209  ClassHierarchyWrapper classHierarchy(project);
210  graphNodes.clear();
211  VariantVector vv(V_SgFunctionDeclaration);
213  std::vector<SgNode*> fdecl_nodes = NodeQuery::queryMemoryPool(defFunc, &vv);
214  BOOST_FOREACH(SgNode *node, fdecl_nodes) {
215  SgFunctionDeclaration *fdecl = isSgFunctionDeclaration(node);
216  SgFunctionDeclaration *unique = isSgFunctionDeclaration(fdecl->get_firstNondefiningDeclaration());
217 #if 0 //debug
218  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());
219  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());
220 #endif
221  if (isSelected(pred)(unique) && hasGraphNodeFor(unique) == NULL)
222  {
223 #if 0 //debug
224  printf ("Collect function calls in unique function: unique = %p \n",unique);
225 #endif
226  FunctionData fdata(unique, project, &classHierarchy); // computes functions called by unique
227  callGraphData.push_back(fdata);
228  std::string functionName = unique->get_qualified_name().getString();
229  SgGraphNode *graphNode = new SgGraphNode(functionName);
230  graphNode->set_SgNode(unique);
231  graphNodes[unique] = graphNode;
232  graph->addNode(graphNode);
233  printf("Added function %s %p\n", functionName.c_str(), unique);
234  }
235  else
236  {
237 #if 0 //debug
238  printf ("Function not selected for processing: unique = %p \n",unique);
239  printf (" --- isSelected(pred)(unique) = %s \n",isSelected(pred)(unique) ? "true" : "false");
240  printf (" --- graphNodes.find(unique)==graphNodes.end() = %s \n",graphNodes.find(unique)==graphNodes.end() ? "true" : "false");
241 #endif
242  }
243  }
244 
245  // Add edges to the graph
246  BOOST_FOREACH(FunctionData &currentFunction, callGraphData) {
247  SgFunctionDeclaration* curFuncDecl = currentFunction.functionDeclaration;
248  std::string curFuncName = curFuncDecl->get_qualified_name().getString();
249  SgGraphNode * srcNode = hasGraphNodeFor(currentFunction.functionDeclaration);
250  ROSE_ASSERT(srcNode != NULL);
251  std::vector<SgFunctionDeclaration*> & callees = currentFunction.functionList;
252  BOOST_FOREACH(SgFunctionDeclaration * callee, callees) {
253  if (isSelected(pred)(callee)) {
254  SgGraphNode * dstNode = getGraphNodeFor(callee); //getGraphNode here, see function comment
255  ROSE_ASSERT(dstNode != NULL);
256  if (graph->checkIfDirectedGraphEdgeExists(srcNode, dstNode) == false)
257  graph->addDirectedEdge(srcNode, dstNode);
258  }
259  }
260  }
261 }
262 
263 // endif for CALL_GRAPH_H
264 #endif
265 
virtual std::string class_name() const override
returns a string representing the class name
SgGraphNode * getGraphNodeFor(SgFunctionDeclaration *fdecl) const
Retrieve the node matching a function declaration (using mangled name to resolve across translation u...
A function object to filter out builtin functions in a call graph (only non-builtin functions will be...
Definition: CallGraph.h:138
Rose_STL_Container< SgFunctionDeclaration * > functionList
All the callees of this function.
Definition: CallGraph.h:122
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:9433
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.
SgGraphNode * hasGraphNodeFor(SgFunctionDeclaration *fdecl) const
Retrieve the node matching a function declaration using firstNondefiningDeclaration (does not work ac...
This class represents a type for all functions.
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:131
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 ...