ROSE  0.9.11.42
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  // TV (10/26/2018): FIXME ROSE-1487
166  // assert(!f || f==f->get_firstNondefiningDeclaration()); // node uniqueness test
167 #if 0
168  // 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.
169  if(isSgTemplateFunctionDeclaration(f)||isSgTemplateMemberFunctionDeclaration(f)) {
170  std::cerr<<"Error: CallGraphBuilder: call referring to node "<<f->class_name()<<" :: function-name:"<<f->get_qualified_name()<<std::endl;
171  }
172 #endif
173  return f && f==f->get_firstNondefiningDeclaration() && !isSgTemplateMemberFunctionDeclaration(f) && !isSgTemplateFunctionDeclaration(f) && pred(f);
174  }
175  };
176 
177  // Add nodes to the graph by querying the memory pool for function declarations, mapping them to unique declarations
178  // that can be used as keys in a map (using get_firstNondefiningDeclaration()), and filtering according to the predicate.
179  graph = new SgIncidenceDirectedGraph();
180  std::vector<FunctionData> callGraphData;
181  ClassHierarchyWrapper classHierarchy(project);
182  graphNodes.clear();
183  VariantVector vv(V_SgFunctionDeclaration);
185  std::vector<SgNode*> fdecl_nodes = NodeQuery::queryMemoryPool(defFunc, &vv);
186  BOOST_FOREACH(SgNode *node, fdecl_nodes) {
187  SgFunctionDeclaration *fdecl = isSgFunctionDeclaration(node);
188  SgFunctionDeclaration *unique = isSgFunctionDeclaration(fdecl->get_firstNondefiningDeclaration());
189 #if 0
190  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());
191  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());
192 #endif
193  if (isSelected(pred)(unique) && graphNodes.find(unique)==graphNodes.end())
194  {
195 #if 0
196  printf ("Collect function calls in unique function: unique = %p \n",unique);
197 #endif
198  FunctionData fdata(unique, project, &classHierarchy); // computes functions called by unique
199  callGraphData.push_back(fdata);
200  std::string functionName = unique->get_qualified_name().getString();
201  SgGraphNode *graphNode = new SgGraphNode(functionName);
202  graphNode->set_SgNode(unique);
203  graphNodes[unique] = graphNode;
204  graph->addNode(graphNode);
205  }
206  else
207  {
208 #if 0
209  printf ("Function not selected for processing: unique = %p \n",unique);
210  printf (" --- isSelected(pred)(unique) = %s \n",isSelected(pred)(unique) ? "true" : "false");
211  printf (" --- graphNodes.find(unique)==graphNodes.end() = %s \n",graphNodes.find(unique)==graphNodes.end() ? "true" : "false");
212 #endif
213  }
214  }
215 
216  // Add edges to the graph
217  BOOST_FOREACH(FunctionData &currentFunction, callGraphData) {
218  SgGraphNode *srcNode = graphNodes.find(currentFunction.functionDeclaration)->second; // we inserted it above
219  std::vector<SgFunctionDeclaration*> &callees = currentFunction.functionList;
220  BOOST_FOREACH(SgFunctionDeclaration *callee, callees) {
221  if (isSelected(pred)(callee)) {
222  GraphNodes::iterator dstNodeFound = graphNodes.find(callee);
223  assert(dstNodeFound!=graphNodes.end()); // should have been added above
224  SgGraphNode *dstNode = dstNodeFound->second;
225  if (graph->checkIfDirectedGraphEdgeExists(srcNode, dstNode) == false)
226  graph->addDirectedEdge(srcNode, dstNode);
227  }
228  }
229  }
230 }
231 
232 // endif for CALL_GRAPH_H
233 #endif
234 
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:8908
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 ...