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