ROSE  0.11.51.0
CallGraphTraverse.h
1 #include <featureTests.h>
2 #ifdef ROSE_ENABLE_SOURCE_ANALYSIS
3 
4 #ifndef CALL_GRAPH_TRAVERSE_H
5 #define CALL_GRAPH_TRAVERSE_H
6 
7 #include <sage3.h>
8 #include "CallGraph.h"
9 #include <map>
10 #include <set>
11 #include <list>
12 #include <string>
13 #include <utility>
14 
15 //namespace CallGraph
16 //{
17 
18 /* !!! NOTE: TraverseCallGraphDataflow LIMITED TO NON-RECURSIVE PROGRAMS (I.E. CONTROL FLOW GRAPHS WITH NO CYCLES) !!! */
19 
20 class Function
21 {
22  protected:
23  //SgFunctionDefinition* def;
24  //set<SgFunctionDeclaration*> decls;
26 
27  public:
28  Function();
29 
30  Function(std::string name);
31 
33 
35 
36  Function(SgFunctionCallExp* funcCall);
37 
38  void init(SgFunctionDeclaration* sample);
39 
40  public:
41  Function(const Function &that);
42 
43  Function(const Function *that);
44 
45  // returns a unique SgFunctionDeclaration* that is the canonical AST node that represents the given function
46  // A canonial declaration means a defining function declaration if available, or the first non-defining declaration
47  static SgFunctionDeclaration* getCanonicalDecl(SgFunctionDeclaration* decl);
48 
49  bool eq(const Function &that) const;
50 
51  bool operator == (const Function &that) const;
52  bool operator != (const Function &that) const;
53 
54  protected:
55  bool lessThan(const Function &that) const;
56  public:
57  bool operator < (const Function &that) const;
58  bool operator > (const Function &that) const;
59  bool operator <= (const Function &that) const;
60  bool operator >= (const Function &that) const;
61 
62  SgName get_name() const;
63 
64  // returns this function's definition or NULL of it does not have one
65  SgFunctionDefinition* get_definition() const;
66 
67  // returns one of this function's declarations. it is guaranteed to be the same each time get_declaration is called
68  SgFunctionDeclaration* get_declaration() const;
69 
70  // returns the file_info of the definition or one of the declarations if there is no definition
71  Sg_File_Info* get_file_info() const;
72 
73  // returns the parameters of this function
74  SgInitializedNamePtrList get_params() const;
75 
76  std::string str(std::string indent="") const;
77 };
78 
79 // extension of the generic function class that also contains all the SgGraphNodes that refer to the function
80 class CGFunction : public Function
81 {
82  std::set<SgGraphNode*> cgNodes;
84 
85  public:
86  CGFunction(std::string name, SgIncidenceDirectedGraph* graph);
87 
89 
91 
92  CGFunction(const CGFunction &that);
93 
94  CGFunction(const CGFunction *that);
95 
96  protected:
97  // initializes the cgNodes set
98  void initCGNodes();
99 
100  public:
101  bool operator == (const CGFunction &that) const;
102  bool operator != (const CGFunction &that) const;
103 
104  bool operator < (const CGFunction &that) const;
105  bool operator > (const CGFunction &that) const;
106  bool operator <= (const CGFunction &that) const;
107  bool operator >= (const CGFunction &that) const;
108 
109  // Traverses the callers or callees of this function
110  // A call graph may have multiple nodes for a same function, each node may have multiple in or out edges.
111  // So the iterator actually works on two levels:
112  // level 1: iterate through all nodes for a given function
113  // level 2: iterate through all in or out edges for each node, return the source or destination node
114  class iterator
115  {
116  // direction in which the iterator is going
117  //SgIncidenceDirectedGraph::EdgeDirection iterDir;
118  // side of an edge that we're going to be following
119  //SgIncidenceDirectedGraph::EdgeDirection edgeDir;
120 
121  // Direction in which the iterator is going (fw: from callers to callees, bw: from callees to callers)
122  public:
123  //typedef enum direction {fw=0, bw=1};
124  enum direction {fw=0, bw=1};
125  protected:
126  direction dir;
127 
128  std::set<SgGraphNode*>::iterator itn;
129  std::set<SgDirectedGraphEdge*> edges; // The current SgGraphNode's (*itn) incoming or outgoing edges
130  std::set<SgDirectedGraphEdge*>::iterator ite; // The current edge in edges
131 
132  // The set the SgGraphNodes that have already been visited by this iterator
133  // used to eliminate duplicates
134  std::set<SgGraphNode*> visitedCGNodes;
135 
136  const CGFunction* func;
137 
138  // =true if this iterator has reached the end of all the edges and =false if not
139  bool finished;
140 
141  public:
142  iterator()
143  {
144  finished = true;
145  }
146 
147  iterator(const CGFunction* const func, direction dir)
148  {
149  this->func = func;
150  this->dir = dir;
151 
152  finished=false;
153 
154  itn = func->cgNodes.begin();
155  if(dir == fw) edges = func->graph->computeEdgeSetOut(*itn);
156  else edges = func->graph->computeEdgeSetIn(*itn);
157  ite = edges.begin();
158 
159  advanceToNextValidPoint();
160  }
161 
162  // Returns a reference to CGFunction that matches the current SgGraphNode that this iterator refers to,
163  // pulling the reference from the given set of CGFunctions
164  const CGFunction* getTarget(std::set<CGFunction> &functions)
165  {
166  //printf("getTarget finished=%d\n", finished);
167  SgGraphNode* target = (dir == fw ? (*ite)->get_to() : (*ite)->get_from());
168  ROSE_ASSERT(isSgFunctionDeclaration(target->get_SgNode()));
169  assert(!isSgTemplateFunctionDeclaration(target->get_SgNode()));
170 
171  // Compiler-generated functions do not appear as nodes in the call graph
172  if(isSgFunctionDeclaration(target->get_SgNode())->get_file_info()->isCompilerGenerated()) return NULL;
173 
174  // Find the CGFunction in functions that matches the target SgGraphNode
175  for(std::set<CGFunction>::const_iterator it = functions.begin(); it!=functions.end(); it++)
176  {
177  //printf(" iteration. current: %s isCompilerGenerated=%d, target=%s, isCompilerGenerated=%d\n", (*it).get_name().str(), (*it).get_declaration()->get_file_info()->isCompilerGenerated(), target->functionDeclaration->get_name().str(), target->functionDeclaration->get_file_info()->isCompilerGenerated());
178  // If the target SgGraphNode can be found in the current CGFunction
179  if((&(*it))->cgNodes.find(target) != (&(*it))->cgNodes.end())
180  return &(*it);
181  }
182 
183  //printf("getTarget returning NULL\n");
184 
185  // If we can't find it, return NULL
186  ROSE_ASSERT(!"Error finding the target function of a call graph edge when the target is not compiler generated!");
187  return NULL;
188  }
189 
190  // Returns the function that this iterator is currently referring to
191  Function getTarget()
192  {
193  SgGraphNode* target = (dir == fw ? (*ite)->get_to() : (*ite)->get_from());
194  ROSE_ASSERT(isSgFunctionDeclaration(target->get_SgNode()));
195  assert(!isSgTemplateFunctionDeclaration(target->get_SgNode()));
196  Function result(isSgFunctionDeclaration(target->get_SgNode()));
197  return result;
198  }
199 
200  void operator ++( int )
201  {
202  ite++;
203 
204  advanceToNextValidPoint();
205  }
206 
207  // If the current <itn, ite> pair refers to a specific CallGraph node, does nothing.
208  // otherwise, advances the <itn, ite> pair until it does refer to a specific CallGraph node
209  void advanceToNextValidPoint()
210  {
211  //printf("Function::iterator::advanceToNextValidPoint()\n");
212  // Loop for as long as ite is not pointing to a valid node and hasn't reached the end of the node list
213  while(1)
214  {
215  // If ite is the last incoming/outgoing edge of the current SgGraphNode
216  if(ite == edges.end())
217  {
218  //printf("Function::iterator::advanceToNextValidPoint() while()\n");
219  // Advance to the next SgGraphNode in cgNodes
220  itn++;
221 
222  // If this is not the last SgGraphNode in cgNodes
223  if(itn != func->cgNodes.end())
224  {
225  // Set edges to the incoming/outgoing edges of the new SgGraphNode and set ite to refer to the first edge
226  if(dir == fw) edges = func->graph->computeEdgeSetOut(*itn);
227  else edges = func->graph->computeEdgeSetIn(*itn);
228  ite = edges.begin();
229  }
230  // otherwise, leave the loop since this iterator has reached the end
231  else
232  {
233  finished=true;
234  break;
235  }
236  }
237  // Else, if it is not the last edges
238  else
239  {
240  SgGraphNode* target = (dir == fw ? (*ite)->get_to() : (*ite)->get_from());
241  // If we've already seen this node
242  if(visitedCGNodes.find(target) != visitedCGNodes.end())
243  ite++;
244  // Else, we have a valid node. Record that we've visited it and break out since we've found a valid upstream/downstream node
245  else {
246  visitedCGNodes.insert(target);
247  break;
248  }
249  }
250  }
251  }
252 
253  bool operator == (const iterator& that)
254  {
255  // if either iterators are finished, then they're equal iff the other is finished, ignoring any other fields
256  if(finished) return that.finished;
257  else if(that.finished) return finished;
258 
259  // otherwise, they're equal only if all their other members are equal
260  return (dir == that.dir) &&
261  (itn == that.itn) &&
262  (edges == that.edges) &&
263  (ite == that.ite) &&
264  (func == that.func);
265  }
266 
267  bool operator != (const iterator& that)
268  { return !((*this) == that); }
269  };
270 
271  // Returns an iterator that traverses the callees of this function
272  iterator callees() const
273  {
274  iterator b(this, iterator::fw);
275  return b;
276  }
277  iterator successors() const
278  {
279  iterator b(this, iterator::fw);
280  return b;
281  }
282 
283  // Returns an iterator that traverses all the callers of this function
284  iterator callers() const
285  {
286  iterator b(this, iterator::bw);
287  return b;
288  }
289  iterator predecessors() const
290  {
291  iterator b(this, iterator::bw);
292  return b;
293  }
294 
295  iterator end() const
296  {
297  iterator b;
298  return b;
299  }
300 };
301 
303 {
304  protected:
306  // maps each SgFunctionDefinition to its associated SgGraphNodes
307  // (there may be more than one such node for a given SgFunctionDefinition)
308  //map<SgFunctionDefinition*, std::set<SgGraphNode*> > decl2CFNode;
309 
310  // The set of functions in this program
311  std::set<CGFunction> functions;
312 
313  // The number of functions that call each given function
314  //std::map<SgFunctionDefinition*, int> numCallers;
315  std::map<const CGFunction*, int> numCallers;
316 
317  // set of all the SgFunctionDefinition for all functions that are not called from other functions
318  //set<SgFunctionDefinition*> noPred;
319  // Set of functions that are not called from other functions.
320  // Just contains pointers to the CGFunction objects inside the functions set.
321  std::set<const CGFunction*> noPred;
322 
323  public:
325 
326  // Returns a pointer to a CGFunction that matches the given declaration.
327  // The memory of the object persists for the entire lifetime of this TraverseCallGraph object.
328  const CGFunction* getFunc(SgFunctionDeclaration* decl);
329 
330  // Returns a pointer to a CGFunction object that matches the given Function object.
331  // The memory of the object persists for the entire lifetime of this TraverseCallGraph object.
332  const CGFunction* getFunc(const Function& func);
333 };
334 
335 /* Un-ordered traversal of the call graph */
337 {
338  public:
340 
341  void traverse();
342 
343  virtual void visit(const CGFunction* func)=0;
344 
345  virtual ~TraverseCallGraphUnordered();
346 };
347 
348 template <class InheritedAttribute>
350 {
351  class funcRecord
352  {
353  public:
354  // the inherited attributes passed down from callers
355  std::list<InheritedAttribute> fromCallers;
356  };
357 
358  public:
360 
361  void traverse();
362 
363  virtual InheritedAttribute visit(const CGFunction* func, std::list<InheritedAttribute>& fromCallers)=0;
364 
365  virtual InheritedAttribute defaultAttrVal() { InheritedAttribute val; return val; }
366 
367  protected:
368  void traverse_rec(const CGFunction* fd,
369  std::map<const CGFunction*, funcRecord> &visitRecords,
370  std::set<std::pair<const CGFunction*, const CGFunction*> > &touchedEdges,
371  InheritedAttribute &fromCaller);
372 
373  public:
374  virtual ~TraverseCallGraphTopDown();
375 };
376 
377 
378 template <class SynthesizedAttribute>
380 {
381  public:
383 
384  void traverse();
385 
386  virtual SynthesizedAttribute visit(const CGFunction* func, std::list<SynthesizedAttribute> fromCallees)=0;
387 
388  virtual SynthesizedAttribute defaultAttrVal() { SynthesizedAttribute val; return val; }
389 
390  protected:
391  SynthesizedAttribute traverse_rec(const CGFunction* fd,
392  std::map<const CGFunction*, SynthesizedAttribute> &visitRecords,
393  std::set<std::pair<const CGFunction*, const CGFunction*> > &touchedEdges);
394 
395  public:
396  virtual ~TraverseCallGraphBottomUp();
397 };
398 
399 // CallGraph traversal useful for inter-procedural dataflow analyses because it starts
400 // at the functions that are not called by any other function and allows such
401 // analyses to keep adding more nodes depending on how function dataflow information changes
403 {
404  public:
405  // list of functions that still remain to be processed;
406  std::list<const CGFunction*> remaining;
407 
409 
410  void traverse();
411 
412  virtual void visit(const CGFunction* func)=0;
413 
414  // adds func to the back of the remaining list, if its not already there
415  void addToRemaining(const CGFunction* func);
416 
417  virtual ~TraverseCallGraphDataflow();
418 };
419 
420 /*********************************************************
421  *** numCallersAnnotator ***
422  *** Annotates every function's SgFunctionDefinition ***
423  *** node with a numCallersAttribute that contains the ***
424  *** number of functions that call the given function. ***
425  *********************************************************/
426 
427 // The attribute that is associated with each function's declaration to
428 // record its number of callers.
430 {
431  int numCallers;
432 
433  public:
435  {
436  numCallers = 0;
437  }
438 
439  numCallersAttribute(int numCallers)
440  {
441  this->numCallers = numCallers;
442  }
443 
445  {
446  this->numCallers = that.numCallers;
447  }
448 
449  int getNumCallers()
450  {
451  return numCallers;
452  }
453 };
454 
455 // Uses the numCallersAnnotator class to annotate every function's SgFunctionDefinition node
456 // with a numCallersAttribute that contains the number of functions that call the given function.
457 void annotateNumCallers(SgIncidenceDirectedGraph* graph);
458 
459 // Returns the number of functions that call this function or 0 if the function is compiler-generated.
460 int getNumCallers(const Function* fDecl);
461 
462 /*class funcCallersAnalysis
463 {
464  bool analyzed=false;
465 
466  // maps each function to the list of its callers, each caller record is a pair, containing the SgFunctionCallExp
467  // that is the function call and the function that this call is inside of
468  std::map<Function, std::list<std::pair<SgFunctionCallExp*, Function> > > callersMap;
469 
470  void analyze()
471  {
472  if(!analyzed)
473  {
474 
475  }
476  analyzed = true;
477  }
478 
479  public:
480  void resetAnalysis()
481  {
482  analyzed = false;
483  }
484 
485 
486  std::list<pair<SgFunctionCallExp*, Function> > getFuncCallers()
487  {
488 
489  }
490 }*/
491 //}
492 
493 #endif
494 #endif
This class represents the location of the code associated with the IR node in the original source cod...
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.).
Base class for all IR node attribute values.
This class represents strings within the IR nodes.
bool isCompilerGenerated() const
Simple test for if this is a compiler generated node.
This class represents the concept of a C++ function call (which is an expression).