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