ROSE  0.9.9.109
dataflow.h
1 #ifndef DATAFLOW_H
2 #define DATAFLOW_H
3 
4 #include "analysisCommon.h"
5 #include "nodeState.h"
6 #include "functionState.h"
7 #include "analysis.h"
8 #include "lattice.h"
9 
10 #include <boost/shared_ptr.hpp>
11 #include <vector>
12 #include <set>
13 #include <map>
14 #include <string>
15 
16 // !!! NOTE: THE CURRENT INTER-/INTRA-PROCEDURAL ANALYSIS API EFFECTIVELY ASSUMES THAT EACH ANALYSIS WILL BE EXECUTED
17 // !!! ONCE BECAUSE DURING A GIVEN ANALYSIS PASS THE INTRA- ANALYSIS MAY ACCUMULATE STATE AND THERE IS NO
18 // !!! API FUNCTION THAT THE INTER- ANALYSIS CAN USE THE RE-INITIALIZE THE STATE OF THE INTRA- ANALYSIS.
19 
20 /*************************
21  *** Dataflow Analyses ***
22  *************************/
24 
26 {
27  public:
28  // generates the initial lattice state for the given dataflow node, in the given function, with the given NodeState
29  //virtual std::vector<Lattice*> genInitState(const Function& func, const DataflowNode& n, const NodeState& state)=0;
30 
31  // !!! NOTE: THIS FUNCTION SHOULD BE AMENDED TO MAKE IT POSSIBLE TO SPECIFY THAT WE WANT THE INITIAL STATE
32  // !!! FOR ABOVE THIS NODE, BELOW THIS NODE OR A UNION OF BOTH. THIS IS IMPORTANT FOR LATTICES THAT
33  // !!! MAINTAIN DIFFERENT INFORMATION FOR THE DIFFERENT CASES, SUCH AS VarsExprsProductLattice, WHERE
34  // !!! DIFFERENT VARIABLES ARE LIVE BEFORE AND AFTER THE NODE. IN PARTICULAR, THIS WOULD BE USEFUL FOR
35  // !!! INTERPROCEDURAL ANALYSES WHERE THE SAME SgFunctionDefinition SgNode IS BOTH THE FIRST AND LAST
36  // !!! VirtualCFG NODE OF EACH FUNCTION WITH DIFFERENT INDEXES AND THE STATE BELOW IT CORRESPONDS TO THE
37  // !!! START OF THE FUNCTION AND THE STATE ABOVE IT CORRESPONDS TO THE END.
38  virtual void genInitState(const Function& func, const DataflowNode& n, const NodeState& state,
39  std::vector<Lattice*>& initLattices, std::vector<NodeFact*>& initFacts)=0;
40 
41 
42  // Set of functions that have already been visited by this analysis, used
43  // to make sure that the dataflow state of previously-visited functions is
44  // not re-initialized when they are visited again.
45  std::set<Function> visited;
46 
47  void setInterAnalysis(InterProceduralDataflow* interDataflowAnalysis)
48  { this->interAnalysis = (InterProceduralAnalysis*)interDataflowAnalysis; }
49 
50  void setInterAnalysis(IntraProceduralDataflow* intraDFAnalysis)
51  { this->interAnalysis = intraDFAnalysis->interAnalysis; }
52 
53  // Dataflow version of the function that intra-procedural analysis on the given function.
54  // Takes in:
55  // state - the function's NodeState
56  // analyzeDueToCallers - true if this function is analyzed due to changes in the the dataflow state from
57  // its caller functions at their call sites to this function
58  // calleesUpdated - true if the function is analyzed due to changes of dataflow state of functions called
59  // by this function at their exit points (i.e. points where this state affects the caller)
60  // Returns true if the function's NodeState gets modified as a result and false otherwise
61  virtual bool runAnalysis(const Function& func, NodeState* state, bool analyzeDueToCallers, std::set<Function> calleesUpdated)=0;
62 
63  // Calls the full dataflow runAnalysis with dummy arguments to make it possible to use IntraProceduralDataflow
64  // as if it were an IntraProceduralAnalysis
65  bool runAnalysis(const Function& func, NodeState* state)
66  {
67  // Each function is analyzed as if it were called directly by the language's runtime, ignoring
68  // the application's actual call graph
69  bool analyzeDueToCallers = true;
70 
71  // We ignore the application's call graph, so it doesn't matter whether this function calls other functions
72  std::set<Function> calleesUpdated;
73 
74  return runAnalysis(func, state, analyzeDueToCallers, calleesUpdated);
75  }
76 
77  InterProceduralDataflow* getInterAnalysis() const
78  {
79  return (InterProceduralDataflow*)interAnalysis;
80  }
81 };
82 
85 {
86 protected:
87  // Common arguments to the underlying transfer function
88  const Function &func;
89  const DataflowNode &dfNode;
90  NodeState &nodeState;
91  const std::vector<Lattice*> &dfInfo;
92 
93 public:
94 
95  IntraDFTransferVisitor(const Function &f, const DataflowNode &n, NodeState &s, const std::vector<Lattice*> &d)
96  : func(f), dfNode(n), nodeState(s), dfInfo(d)
97  { }
98 
99  virtual bool finish() = 0;
100  virtual ~IntraDFTransferVisitor() { }
101 };
102 
104 {
105  public:
106 
107  // the transfer function that is applied to every node
108  // n - the dataflow node that is being processed
109  // state - the NodeState object that describes the state of the node, as established by earlier
110  // analysis passes
111  // dfInfo - the Lattices that this transfer function operates on. The function takes these lattices
112  // as input and overwrites them with the result of the transfer.
113  // Returns true if any of the input lattices changed as a result of the transfer function and
114  // false otherwise.
115  virtual bool transfer(const Function& func, const DataflowNode& n, NodeState& state, const std::vector<Lattice*>& dfInfo)=0;
116 
118  {
119  bool modified;
120  IntraUnitDataflow *analysis;
121  public:
122  DefaultTransfer(const Function& func_, const DataflowNode& n_, NodeState& state_, const std::vector<Lattice*>& dfInfo_, IntraUnitDataflow *a)
123  : IntraDFTransferVisitor(func_, n_, state_, dfInfo_), modified(false), analysis(a)
124  { }
125 
126 
127  void visit(SgNode *n) { modified = analysis->transfer(func, dfNode, nodeState, dfInfo); }
128  bool finish() { return modified; }
129  };
130 
131 
132  // \todo \pp IMO. the function getTransferVisitor is not necessary and can be removed.
133  // Users wanting to write the analysis based on visitors can do so
134  // in the transfer function. (This safes one memory allocation, deallocation,
135  // and boost::shared_pointer management overhead per transfer).
136  // A transfer function using the visitor would look like (if desired this can be
137  // simplified by providing a convenience function taking a visitor as argument):
138  // \code
139  // virtual bool transfer(const Function& func, const DataflowNode& n, NodeState& state, const std::vector<Lattice*>& dfInfo, std::vector<Lattice*>** retState, bool fw)
140  // {
141  // MyTransferVisitor visitor(myarguments, func, n, ...);
142  // n.getNode().accept(visitor);
143  // return visitor.finish();
144  // }
145  // \endcode
146  virtual boost::shared_ptr<IntraDFTransferVisitor> getTransferVisitor(const Function& func, const DataflowNode& n,
147  NodeState& state, const std::vector<Lattice*>& dfInfo)
148  { return boost::shared_ptr<IntraDFTransferVisitor>(new DefaultTransfer(func, n, state, dfInfo, this)); }
149 };
150 
152 {
153  public:
154  InterProceduralDataflow(IntraProceduralDataflow* intraDataflowAnalysis);
155 
156  // the transfer function that is applied to SgFunctionCallExp nodes to perform the appropriate state transfers
157  // fw - =true if this is a forward analysis and =false if this is a backward analysis
158  // n - the dataflow node that is being processed
159  // state - the NodeState object that describes the dataflow state immediately before (if fw=true) or immediately after
160  // (if fw=false) the SgFunctionCallExp node, as established by earlier analysis passes
161  // dfInfo - the Lattices that this transfer function operates on. The function propagates them
162  // to the calling function and overwrites them with the dataflow result of calling this function.
163  // retState - Pointer reference to a Lattice* vector that will be assigned to point to the lattices of
164  // the function call's return value. The callee may not modify these lattices.
165  // Returns true if any of the input lattices changed as a result of the transfer function and
166  // false otherwise.
167  virtual bool transfer(const Function& func, const DataflowNode& n, NodeState& state,
168  const std::vector<Lattice*>& dfInfo, std::vector<Lattice*>** retState, bool fw)=0;
169 };
170 
172 {
173  //std::vector<Lattice*> initState;
174  IntraProceduralDataflow* dfAnalysis;
175 
176  public:
177  InitDataflowState(IntraProceduralDataflow* dfAnalysis/*, std::vector<Lattice*> &initState*/)
178  {
179  this->dfAnalysis = dfAnalysis;
180  this->filter = dfAnalysis->filter; // Must transfer the custom CFG filter, this is tricky!!
181  //this->initState = initState;
182  }
183 
184  void visit(const Function& func, const DataflowNode& n, NodeState& state);
185 };
186 
187 // Analysis that finds the DataflowNodes that corresponds to calls to a given set of functions
189 {
190  // The set of functions that we wish to find the calls to
191  const std::set<Function>& funcsToFind;
192 
193  // Maps each function in funcsToFind to a set of DataflowNodes that hold calls to this function
194  std::map<Function, std::set<DataflowNode> > funcCalls;
195 
196  public:
197  FindAllFunctionCalls(const std::set<Function>& funcsToFind): funcsToFind(funcsToFind)
198  { }
199 
200  void visit(const Function& func, const DataflowNode& n, NodeState& state);
201 
202  // Returns a reference to funcCalls
203  std::map<Function, std::set<DataflowNode> >& getFuncCalls() { return funcCalls; }
204 };
205 
206 /* Base class of Uni-directional (Forward or Backward) Intra-Procedural Dataflow Analyses */
208 {
209  public:
210 
211  // Runs the intra-procedural analysis on the given function and returns true if
212  // the function's NodeState gets modified as a result and false otherwise
213  // state - the function's NodeState
214  bool runAnalysis(const Function& func, NodeState* state, bool analyzeDueToCallers, std::set<Function> calleesUpdated);
215 
216  protected:
217  // propagates the dataflow info from the current node's NodeState (curNodeState) to the next node's
218  // NodeState (nextNodeState)
219  bool propagateStateToNextNode(
220  const std::vector<Lattice*>& curNodeState, DataflowNode curDFNode, int nodeIndex,
221  const std::vector<Lattice*>& nextNodeState, DataflowNode nextDFNode);
222 
223  std::vector<DataflowNode> gatherDescendants(std::vector<DataflowEdge> edges,
224  DataflowNode (DataflowEdge::*edgeFn)() const);
225 
226  virtual NodeState*initializeFunctionNodeState(const Function &func, NodeState *fState) = 0;
227  virtual VirtualCFG::dataflow*
228  getInitialWorklist(const Function &func, bool firstVisit, bool analyzeDueToCallers, const set<Function> &calleesUpdated, NodeState *fState) = 0;
229  virtual vector<Lattice*> getLatticeAnte(NodeState *state) = 0;
230  virtual vector<Lattice*> getLatticePost(NodeState *state) = 0;
231 
232  // If we're currently at a function call, use the associated inter-procedural
233  // analysis to determine the effect of this function call on the dataflow state.
234  virtual void transferFunctionCall(const Function &func, const DataflowNode &n, NodeState *state) = 0;
235 
236 
237  virtual vector<DataflowNode> getDescendants(const DataflowNode &n) = 0;
238  virtual DataflowNode getUltimate(const Function &func) = 0;
239 };
240 
241 /* Forward Intra-Procedural Dataflow Analysis */
243 {
244  public:
245 
247  {}
248 
249  NodeState* initializeFunctionNodeState(const Function &func, NodeState *fState);
251  getInitialWorklist(const Function &func, bool firstVisit, bool analyzeDueToCallers, const set<Function> &calleesUpdated, NodeState *fState);
252  vector<Lattice*> getLatticeAnte(NodeState *state);
253  vector<Lattice*> getLatticePost(NodeState *state);
254  void transferFunctionCall(const Function &func, const DataflowNode &n, NodeState *state);
255  vector<DataflowNode> getDescendants(const DataflowNode &n);
256  DataflowNode getUltimate(const Function &func);
257 };
258 
259 /* Backward Intra-Procedural Dataflow Analysis */
261 {
262  public:
263 
265  {}
266 
267  NodeState* initializeFunctionNodeState(const Function &func, NodeState *fState);
269  getInitialWorklist(const Function &func, bool firstVisit, bool analyzeDueToCallers, const set<Function> &calleesUpdated, NodeState *fState);
270  virtual vector<Lattice*> getLatticeAnte(NodeState *state);
271  virtual vector<Lattice*> getLatticePost(NodeState *state);
272  void transferFunctionCall(const Function &func, const DataflowNode &n, NodeState *state);
273  vector<DataflowNode> getDescendants(const DataflowNode &n);
274  DataflowNode getUltimate(const Function &func);
275 };
276 
277 /*// Dataflow class that maintains a Lattice for every currently live variable
278 class IntraFWPerVariableDataflow : public IntraFWDataflow
279 {
280  private:
281  bool includeScalars;
282  bool includeArrays;
283 
284 
285  public:
286  IntraFWPerVariableDataflow(bool includeScalars, bool includeArrays);
287 
288  // returns the set of global variables(scalars and/or arrays)
289  varIDSet& getGlobalVars();
290 
291  // returns the set of variables(scalars and/or arrays) declared in this function
292  varIDSet& getLocalVars(Function func);
293 
294  // returns the set of variables(scalars and/or arrays) referenced in this function
295  varIDSet& getRefVars(Function func);
296 
297  // generates the initial variable-specific lattice state for a dataflow node
298  virtual Lattice* genInitVarState(const Function& func, const DataflowNode& n, const NodeState& state)=0;
299 
300  // generates the initial non-variable-specific lattice state for a dataflow node
301  virtual Lattice* genInitNonVarState(const Function& func, const DataflowNode& n, const NodeState& state)=0;
302 
303  // Generates a map of special constant variables (such as zeroVar) and the lattices that correspond to them
304  // These lattices are assumed to be constants: it is assumed that they are never modified and it is legal to
305  // maintain only one copy of each lattice may for the duration of the analysis.
306  virtual std::map<varID, Lattice*> genConstVarLattices() const=0;
307 
308  private:
309  // maps variables to the index of their respective Lattice objects in a given function
310  std::map<Function, std::map<varID, int> > varLatticeIndex;
311  // map of lattices that correspond to constant variables
312  std::map<varID, Lattice*> constVarLattices;
313  // =true if constVarLattices has been initialized and =false otherwise
314  bool constVarLattices_init;
315 
316  public:
317  // generates the initial lattice state for the given dataflow node, in the given function, with the given NodeState
318  std::vector<Lattice*> genInitState(const Function& func, const DataflowNode& n, const NodeState& state);
319 
320  Lattice* getVarLattice(const Function& func, const varID& var, const std::vector<Lattice*>& dfInfo);
321 };*/
322 
323 /******************************************************
324  *** printDataflowInfoPass ***
325  *** Prints out the dataflow information associated ***
326  *** with a given analysis for every CFG node a ***
327  *** function. ***
328  ******************************************************/
330 {
331  Analysis* analysis;
332 
333  public:
335  {
336  this->analysis = analysis;
337  }
338 
339  // generates the initial lattice state for the given dataflow node, in the given function, with the given NodeState
340  //std::vector<Lattice*> genInitState(const Function& func, const DataflowNode& n, const NodeState& state);
341  void genInitState(const Function& func, const DataflowNode& n, const NodeState& state,
342  std::vector<Lattice*>& initLattices, std::vector<NodeFact*>& initFacts);
343 
344  bool transfer(const Function& func, const DataflowNode& n, NodeState& state, const std::vector<Lattice*>& dfInfo);
345 };
346 
347 /**********************************************************************
348  *** UnstructuredPassInterDataflow ***
349  *** The trivial inter-procedural dataflow where a intra-procedural ***
350  *** dataflow analysis is executed once on every function in the ***
351  *** application, with no guarantees about how dataflow information ***
352  *** is transmitted across function calls. ***
353  **********************************************************************/
355 {
356  public:
357 
359  : InterProceduralAnalysis((IntraProceduralAnalysis*)intraDataflowAnalysis), InterProceduralDataflow(intraDataflowAnalysis)
360  {}
361 
362  // the transfer function that is applied to SgFunctionCallExp nodes to perform the appropriate state transfers
363  // fw - =true if this is a forward analysis and =false if this is a backward analysis
364  // n - the dataflow node that is being processed
365  // state - the NodeState object that describes the dataflow state immediately before (if fw=true) or immediately after
366  // (if fw=false) the SgFunctionCallExp node, as established by earlier analysis passes
367  // dfInfo - the Lattices that this transfer function operates on. The function propagates them
368  // to the calling function and overwrites them with the dataflow result of calling this function.
369  // retState - Pointer reference to a Lattice* vector that will be assigned to point to the lattices of
370  // the function call's return value. The callee may not modify these lattices.
371  // Returns true if any of the input lattices changed as a result of the transfer function and
372  // false otherwise.
373  bool transfer(const Function& func, const DataflowNode& n, NodeState& state,
374  const std::vector<Lattice*>& dfInfo, std::vector<Lattice*>** retState, bool fw)
375  {
376  return false;
377  }
378 
379  void runAnalysis();
380 };
381 
382 // Analysis that merges the dataflow states belonging to the given Analysis at all the return statements in the given function
383 // and produces a list of merged lattices (same number of lattices as were maintained by the nodes in the function).
384 // NOTE: The callers of this analysis are responsible for deallocating the lattices stored n mergedLatsRetStmt
385 // and mergedLatsRetVal at the end of the analysis pass.
387 {
388  // Analysis whose states we'll be merging
389  Analysis* analysis;
390 
391  // List of merged lattices of all the return statements and the returned values
392  std::vector<Lattice*> mergedLatsRetStmt;
393  std::vector<Lattice*> mergedLatsRetVal;
394 
395  public:
396  //typedef enum ab {above=0, below=1};
397  protected:
398  //ab latSide;
399 
400  // After the analysis is complete, records true if the state of the mergedLattices changed
401  // during the analysis and false otherwise
402  bool modified;
403 
404  public:
405  MergeAllReturnStates(Analysis* analysis/*, ab latSide*/): analysis(analysis)/*, latSide(latSide)*/
406  { modified=false; }
407 
408  MergeAllReturnStates(Analysis* analysis, const std::vector<Lattice*>& mergedLatsRetStmt, const std::vector<Lattice*>& mergedLatsRetVal/*, ab latSide*/):
409  analysis(analysis), mergedLatsRetStmt(mergedLatsRetStmt), mergedLatsRetVal(mergedLatsRetVal)/*, latSide(latSide)*/
410  { modified=false; }
411 
412  void visit(const Function& func, const DataflowNode& n, NodeState& state);
413 
414  // Merges the lattices in the given vector into mergedLat, which may be mergedLatsRetStmt or mergedLatsRetVal
415  // Returns true of mergedLatsStmt changes as a result and false otherwise.
416  static bool mergeLats(std::vector<Lattice*>& mergedLat, const std::vector<Lattice*>& lats);
417 
418  // Returns a reference to mergedLatsRetStmt
419  std::vector<Lattice*>& getMergedLatsRetStmt() { return mergedLatsRetStmt; }
420 
421  // Returns a reference to mergedLatsRetVal
422  std::vector<Lattice*>& getMergedLatsRetVal() { return mergedLatsRetVal; }
423 
424  // Returns the value of modified
425  bool getModified() { return modified; }
426 
427  // Deallocates all the merged lattices
429 };
430 
431 // A NodeFact associated with a FunctionState that stores the merge of the lattices immediately
432 // above all return statements in a given function.
434 {
435  // The dataflow state at the end of the function, merged over all the return statements
436  // and the implicit return at the end of the function
437  std::vector<Lattice*>& latsAtFuncReturn;
438  // The dataflow state of the return value, merged over all the return statements
439  std::vector<Lattice*>& latsRetVal;
440 
441  public:
442  //DFStateAtReturns();
443 
444  DFStateAtReturns(std::vector<Lattice*>& latsAtFuncReturn, std::vector<Lattice*>& latsRetVal);
445 
446  // Returns a copy of this node fact
447  NodeFact* copy() const;
448 
449  // Applies the MergeAllReturnStates analysis on the given function, incorporating the results into
450  // the lattices held by this object.
451  // Returns true of the lattices change as a result and false otherwise.
452  bool mergeReturnStates(const Function& func, FunctionState* fState, IntraProceduralDataflow* intraAnalysis);
453 
454  // Returns a reference to latsAtFuncReturn
455  std::vector<Lattice*>& getLatsAtFuncReturn() { return latsAtFuncReturn; }
456 
457  // Returns a reference to latsRetVal
458  std::vector<Lattice*>& getLatsRetVal() { return latsRetVal; }
459 
460  std::string str(std::string indent);
461 };
462 
464 {
465  // list of functions that still remain to be processed
466  //list<Function> remaining;
467 
468  // The functions that still remain to be processed.
469 
470  // These functions need to be processed because they are called by functions that have been processed
471  // or are called at startup such as main() and the constructors of static objects.
472  std::set<Function> remainingDueToCallers;
473 
474  // Each function F in this map needs to be processed because it has called other functions and those functions
475  // have now been analyzed and the dataflow information at their exit points has changed since the last time
476  // F was analyzed. remainingDueToCalls maps each F to all such functions. As such, F needs to be re-analyzed,
477  // starting at the calls to these functions.
478  std::map<Function, std::set<Function> > remainingDueToCalls;
479 
480  public:
482 
483  public:
484 
485  // the transfer function that is applied to SgFunctionCallExp nodes to perform the appropriate state transfers
486  // fw - =true if this is a forward analysis and =false if this is a backward analysis
487  // n - the dataflow node that is being processed
488  // state - the NodeState object that describes the dataflow state immediately before (if fw=true) or immediately after
489  // (if fw=false) the SgFunctionCallExp node, as established by earlier analysis passes
490  // dfInfo - the Lattices that this transfer function operates on. The function propagates them
491  // to the calling function and overwrites them with the dataflow result of calling this function.
492  // retState - Pointer reference to a Lattice* vector that will be assigned to point to the lattices of
493  // the function call's return value. The callee may not modify these lattices.
494  // Returns true if any of the input lattices changed as a result of the transfer function and
495  // false otherwise.
496  bool transfer(const Function& func, const DataflowNode& n, NodeState& state,
497  const std::vector<Lattice*>& dfInfo, std::vector<Lattice*>** retState, bool fw);
498 
499  // Uses TraverseCallGraphDataflow to traverse the call graph.
500  void runAnalysis();
501 
502  // Runs the intra-procedural analysis every time TraverseCallGraphDataflow passes a function.
503  void visit(const CGFunction* func);
504 };
505 
506 #endif
Apply an analysis A's transfer function at a particular AST node type.
Definition: dataflow.h:84
This class represents the base class for all IR nodes within Sage III.
Definition: Cxx_Grammar.h:8322