ROSE  0.11.2.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 
77  std::vector<SgFunctionDeclaration*> solveConstructorInitializer ( SgConstructorInitializer* sgCtorInit);
78 
79  // Populates functionList with Properties of all functions that may get called.
80  ROSE_DLL_API void getPropertiesForExpression(SgExpression* exp,
81  ClassHierarchyWrapper* classHierarchy,
82  Rose_STL_Container<SgFunctionDeclaration*>& propList,
83  bool includePureVirtualFunc = false);
84 
89  void getDefinitionsForExpression(SgExpression* exp,
90  ClassHierarchyWrapper* classHierarchy,
91  Rose_STL_Container<SgFunctionDefinition*>& calleeList);
92 
95  void getDeclarationsForExpression(SgExpression* exp,
96  ClassHierarchyWrapper* classHierarchy,
97  Rose_STL_Container<SgFunctionDeclaration*>& calleeList,
98  bool includePureVirtualFunc = false);
99 
100  // Gets a vector of SgExpressions that are associated with the current SgFunctionDefinition.
101  // This functionality is necessary for virtual, interprocedural control flow graphs. However,
102  // it is costly and should be used infrequently (or optimized!).
103  void getExpressionsForDefinition(SgFunctionDefinition* targetDef,
104  ClassHierarchyWrapper* classHierarchy,
105  Rose_STL_Container<SgExpression*>& exps);
106 
107  // Gets the latest implementation of the member function from the ancestor hierarchy
108  SgFunctionDeclaration * getFirstVirtualFunctionDefinitionFromAncestors(SgClassType *crtClass,
109  SgMemberFunctionDeclaration *memberFunctionDeclaration,
110  ClassHierarchyWrapper *classHierarchy);
111 
112 };
113 
114 class ROSE_DLL_API FunctionData
115 {
116  public:
117 
118  bool hasDefinition;
119 
120  bool isDefined ();
121 
122  FunctionData(SgFunctionDeclaration* functionDeclaration, SgProject *project, ClassHierarchyWrapper * );
123 
125  Rose_STL_Container<SgFunctionDeclaration *> functionList;
126 
127  SgFunctionDeclaration* functionDeclaration;
128 
129  Rose_STL_Container<SgMemberFunctionDeclaration*> *findPointsToVirtualFunctions ( SgMemberFunctionDeclaration * );
130  bool compareFunctionDeclarations( SgFunctionDeclaration *f1, SgFunctionDeclaration *f2 );
131 };
132 
134 struct dummyFilter : public std::unary_function<bool,SgFunctionDeclaration*>
135 {
136  bool operator() (SgFunctionDeclaration* node) const; // always return true
137 };
138 
140 // Liao, 6/17/2012
141 struct ROSE_DLL_API builtinFilter : public std::unary_function<bool,SgFunctionDeclaration*>
142 {
143  bool operator() (SgFunctionDeclaration* node) const;
144 };
145 
146 class ROSE_DLL_API CallGraphBuilder
147 {
148  public:
149  CallGraphBuilder( SgProject *proj);
151  void buildCallGraph();
153  template<typename Predicate>
154  void buildCallGraph(Predicate pred);
156  SgIncidenceDirectedGraph *getGraph();
157  //void classifyCallGraph();
158 
159  //We map each function to the corresponding graph node
160  boost::unordered_map<SgFunctionDeclaration*, SgGraphNode*>& getGraphNodesMapping(){ return graphNodes; }
161 
163  SgGraphNode * hasGraphNodeFor(SgFunctionDeclaration * fdecl) const;
165  SgGraphNode * getGraphNodeFor(SgFunctionDeclaration * fdecl) const;
166 
167  private:
168  SgProject *project;
170  //We map each function to the corresponding graph node
171  typedef boost::unordered_map<SgFunctionDeclaration*, SgGraphNode*> GraphNodes;
172  GraphNodes graphNodes;
173 
174 };
176 //TODO this function is not defined? If so, need to be removed.
177 // AstDOTGeneration::writeIncidenceGraphToDOTFile() is used instead in the tutorial. Liao 6/17/2012
178 void GenerateDotGraph ( SgIncidenceDirectedGraph *graph, std::string fileName );
179 
180 class ROSE_DLL_API GetOneFuncDeclarationPerFunction : public std::unary_function<SgNode*, Rose_STL_Container<SgNode*> >
181 {
182  public:
183  result_type operator()(SgNode* node );
184 };
185 
186 template<typename Predicate>
187 void
189 {
190  // Adds additional constraints to the predicate. It makes no sense to analyze non-instantiated templates.
191  struct isSelected {
192  Predicate &pred;
193  isSelected(Predicate &pred): pred(pred) {}
194  bool operator()(SgNode *node) {
195  SgFunctionDeclaration *f = isSgFunctionDeclaration(node);
196  // TV (10/26/2018): FIXME ROSE-1487
197  // assert(!f || f==f->get_firstNondefiningDeclaration()); // node uniqueness test
198 #if 0
199  // 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.
200  if(isSgTemplateFunctionDeclaration(f)||isSgTemplateMemberFunctionDeclaration(f)) {
201  std::cerr<<"Error: CallGraphBuilder: call referring to node "<<f->class_name()<<" :: function-name:"<<f->get_qualified_name()<<std::endl;
202  }
203 #endif
204  return f && f==f->get_firstNondefiningDeclaration() && !isSgTemplateMemberFunctionDeclaration(f) && !isSgTemplateFunctionDeclaration(f) && pred(f);
205  }
206  };
207 
208  // Add nodes to the graph by querying the memory pool for function declarations, mapping them to unique declarations
209  // that can be used as keys in a map (using get_firstNondefiningDeclaration()), and filtering according to the predicate.
210  graph = new SgIncidenceDirectedGraph();
211  std::vector<FunctionData> callGraphData;
212  ClassHierarchyWrapper classHierarchy(project);
213  graphNodes.clear();
214  VariantVector vv(V_SgFunctionDeclaration);
216  std::vector<SgNode*> fdecl_nodes = NodeQuery::queryMemoryPool(defFunc, &vv);
217  BOOST_FOREACH(SgNode *node, fdecl_nodes) {
218  SgFunctionDeclaration *fdecl = isSgFunctionDeclaration(node);
219  SgFunctionDeclaration *unique = isSgFunctionDeclaration(fdecl->get_firstNondefiningDeclaration());
220 #if 0
221  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());
222  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());
223 #endif
224  if (isSelected(pred)(unique) && hasGraphNodeFor(unique) == NULL)
225  {
226 #if 0
227  printf ("Collect function calls in unique function: unique = %p \n",unique);
228 #endif
229  FunctionData fdata(unique, project, &classHierarchy); // computes functions called by unique
230  callGraphData.push_back(fdata);
231  std::string functionName = unique->get_qualified_name().getString();
232  SgGraphNode *graphNode = new SgGraphNode(functionName);
233  graphNode->set_SgNode(unique);
234  graphNodes[unique] = graphNode;
235  graph->addNode(graphNode);
236  }
237  else
238  {
239 #if 0
240  printf ("Function not selected for processing: unique = %p \n",unique);
241  printf (" --- isSelected(pred)(unique) = %s \n",isSelected(pred)(unique) ? "true" : "false");
242  printf (" --- graphNodes.find(unique)==graphNodes.end() = %s \n",graphNodes.find(unique)==graphNodes.end() ? "true" : "false");
243 #endif
244  }
245  }
246 
247  // Add edges to the graph
248  BOOST_FOREACH(FunctionData &currentFunction, callGraphData) {
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 
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:141
Rose_STL_Container< SgFunctionDeclaration * > functionList
All the callees of this function.
Definition: CallGraph.h:125
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:9311
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.
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:134
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 ...