ROSE  0.9.9.139
liveDeadVarAnalysis.h
1 #ifndef LIVE_DEAD_VAR_ANALYSIS_H
2 #define LIVE_DEAD_VAR_ANALYSIS_H
3 
4 #include "genericDataflowCommon.h"
5 #include "VirtualCFGIterator.h"
6 #include "cfgUtils.h"
7 #include "CallGraphTraverse.h"
8 #include "analysisCommon.h"
9 #include "analysis.h"
10 #include "dataflow.h"
11 #include "latticeFull.h"
12 #include "printAnalysisStates.h"
13 
14 #include <map>
15 #include <set>
16 #include <vector>
17 #include <string>
18 #include <iostream>
19 
20 extern int liveDeadAnalysisDebugLevel;
21 
22 // Lattice that stores the variables that are live at a given DataflowNode
24 {
25  public:
26  std::set<varID> liveVars;
27 
28  public:
30  LiveVarsLattice(const varID& var);
31  LiveVarsLattice(const std::set<varID>& liveVars);
32 
33  // Initializes this Lattice to its default state, if it is not already initialized
34  void initialize();
35 
36  // Returns a copy of this lattice
37  Lattice* copy() const;
38 
39  // Overwrites the state of this Lattice with that of that Lattice
40  void copy(Lattice* that);
41 
42  // Called by analyses to create a copy of this lattice. However, if this lattice maintains any
43  // information on a per-variable basis, these per-variable mappings must be converted from
44  // the current set of variables to another set. This may be needed during function calls,
45  // when dataflow information from the caller/callee needs to be transferred to the callee/calleer.
46  // We do not force child classes to define their own versions of this function since not all
47  // Lattices have per-variable information.
48  // varNameMap - maps all variable names that have changed, in each mapping pair, pair->first is the
49  // old variable and pair->second is the new variable
50  // func - the function that the copy Lattice will now be associated with
51  void remapVars(const std::map<varID, varID>& varNameMap, const Function& newFunc);
52 
53  // Called by analyses to copy over from the that Lattice dataflow information into this Lattice.
54  // that contains data for a set of variables and incorporateVars must overwrite the state of just
55  // those variables, while leaving its state for other variables alone.
56  // We do not force child classes to define their own versions of this function since not all
57  // Lattices have per-variable information.
58  void incorporateVars(Lattice* that_arg);
59 
60  // Returns a Lattice that describes the information known within this lattice
61  // about the given expression. By default this could be the entire lattice or any portion of it.
62  // For example, a lattice that maintains lattices for different known variables and expression will
63  // return a lattice for the given expression. Similarly, a lattice that keeps track of constraints
64  // on values of variables and expressions will return the portion of the lattice that relates to
65  // the given expression.
66  // It it legal for this function to return NULL if no information is available.
67  // The function's caller is responsible for deallocating the returned object
68  Lattice* project(SgExpression* expr);
69 
70  // The inverse of project(). The call is provided with an expression and a Lattice that describes
71  // the dataflow state that relates to expression. This Lattice must be of the same type as the lattice
72  // returned by project(). unProject() must incorporate this dataflow state into the overall state it holds.
73  // Call must make an internal copy of the passed-in lattice and the caller is responsible for deallocating it.
74  // Returns true if this causes this to change and false otherwise.
75  bool unProject(SgExpression* expr, Lattice* exprState);
76 
77  // computes the meet of this and that and saves the result in this
78  // returns true if this causes this to change and false otherwise
79  bool meetUpdate(Lattice* that_arg);
80 
81  bool operator==(Lattice* that);
82 
83  // Functions used to inform this lattice that a given variable is now in use (e.g. a variable has entered
84  // scope or an expression is being analyzed) or is no longer in use (e.g. a variable has exited scope or
85  // an expression or variable is dead).
86  // It is assumed that a newly-added variable has not been added before and that a variable that is being
87  // removed was previously added
88  // Returns true if this causes the lattice to change and false otherwise.
89  bool addVar(const varID& var);
90  bool remVar(const varID& var);
91 
92  // Returns true if the given variable is recorded as live and false otherwise
93  bool isLiveVar(varID var);
94 
95  // The string that represents this object
96  // If indent!="", every line of this string must be prefixed by indent
97  // The last character of the returned string should not be '\n', even if it is a multi-line string.
98  std::string str(std::string indent="");
99 };
100 
101 // Virtual class that allows users of the LiveDeadVarsAnalysis to mark certain variables as
102 // being used inside a function call if the function's body is not available.
104 {
105 public:
106  // Returns the set of variables that are used in a call to the given function for which a body has not been provided.
107  // The function is also provided with the DataflowNode where the function was called, as well as its state.
108  virtual std::set<varID> usedVarsInFunc(const Function& func, const DataflowNode& n, NodeState& state)=0;
109 };
110 
112 {
113  std::string indent;
114  LiveVarsLattice* liveLat;
115 
116  bool modified;
117  // Expressions that are assigned by the current operation
118  std::set<SgExpression*> assignedExprs;
119  // Variables that are assigned by the current operation
120  std::set<varID> assignedVars;
121  // Variables that are used/read by the current operation
122  std::set<varID> usedVars;
123 
124  funcSideEffectUses *fseu;
125 
126  friend class LDVAExpressionTransfer;
127 
128  // Note that the variable corresponding to this expression is used
129  void used(SgExpression *);
130 
131 public:
132  LiveDeadVarsTransfer(const Function &f, const DataflowNode &n, NodeState &s, const std::vector<Lattice*> &d, funcSideEffectUses *fseu_)
133  : IntraDFTransferVisitor(f, n, s, d), indent(" "), liveLat(dynamic_cast<LiveVarsLattice*>(*(dfInfo.begin()))), modified(false), fseu(fseu_)
134  {
135  if(liveDeadAnalysisDebugLevel>=1) Dbg::dbg << indent << "liveLat="<<liveLat->str(indent + " ")<<std::endl;
136  // Make sure that all the lattice is initialized
137  liveLat->initialize();
138  }
139 
140  bool finish();
141 
142  void visit(SgExpression *);
143  void visit(SgInitializedName *);
144  void visit(SgReturnStmt *);
145  void visit(SgExprStatement *);
146  void visit(SgCaseOptionStmt *);
147  void visit(SgIfStmt *);
148  void visit(SgForStatement *);
149  void visit(SgWhileStmt *);
150  void visit(SgDoWhileStmt *);
151 };
152 
153 /* Computes an over-approximation of the set of variables that are live at each DataflowNode. It may consider a given
154  variable as live when in fact it is not. */
155 // !!! CURRENTLY THE ANALYSIS IS IMPRECISE BECAUSE:
156 // !!! - IF THERE IS A VARIABLE USE WHERE THE IDENTITY OF THE VARIABLE IS COMPUTED THROUGH AN EXPRESSION, WE DO NOT
157 // !!! RESPOND BY CONSERVATIVELY MAKING ALL VARIABLES LIVE.
158 // !!! - IT DOES NOT CONSIDER INTERNALS OF ARRAYS OR OTHER HEAP MEMORY
160 {
161  protected:
162  funcSideEffectUses* fseu;
163 
164  public:
165  LiveDeadVarsAnalysis(SgProject *project, funcSideEffectUses* fseu=NULL);
166 
167  // Generates the initial lattice state for the given dataflow node, in the given function, with the given NodeState
168  void genInitState(const Function& func, const DataflowNode& n, const NodeState& state,
169  std::vector<Lattice*>& initLattices, std::vector<NodeFact*>& initFacts);
170 
171  boost::shared_ptr<IntraDFTransferVisitor> getTransferVisitor(const Function& func, const DataflowNode& n,
172  NodeState& state, const std::vector<Lattice*>& dfInfo)
173  { return boost::shared_ptr<IntraDFTransferVisitor>(new LiveDeadVarsTransfer(func, n, state, dfInfo, fseu)); }
174 
175  bool transfer(const Function& func, const DataflowNode& n, NodeState& state, const std::vector<Lattice*>& dfInfo) { assert(0); return false; }
176 };
177 
178 // Initialize vars to hold all the variables and expressions that are live at DataflowNode n
179 //void getAllLiveVarsAt(LiveDeadVarsAnalysis* ldva, const DataflowNode& n, const NodeState& state, std::set<varID>& vars, std::string indent="");
180 void getAllLiveVarsAt(LiveDeadVarsAnalysis* ldva, const NodeState& state, std::set<varID>& vars, std::string indent="");
181 
182 // Returns the set of variables and expressions that are live at DataflowNode n
183 //std::set<varID> getAllLiveVarsAt(LiveDeadVarsAnalysis* ldva, const DataflowNode& n, const NodeState& state, std::string indent="");
184 std::set<varID> getAllLiveVarsAt(LiveDeadVarsAnalysis* ldva, const NodeState& state, std::string indent="");
185 
186 // get Live-In lattice for a control flow graph node generated from a SgNode with an index
187 LiveVarsLattice* getLiveInVarsAt(LiveDeadVarsAnalysis* ldva, SgNode* n, unsigned int index = 0);
188 
189 // get Live-Out lattice for a control flow graph node generated from a SgNode with an index
190 LiveVarsLattice* getLiveOutVarsAt(LiveDeadVarsAnalysis* ldva, SgNode* n, unsigned int index = 0);
191 
193 {
194  protected:
195  // Sample lattice that will be initially associated with every variable (before the analysis)
196  Lattice* perVarLattice;
197 
198  // Lattice that corresponds to allVar;
199  Lattice* allVarLattice;
200 
201  // Map of lattices that correspond to constant variables
202  std::map<varID, Lattice*> constVarLattices;
203 
204  // Maps variables in a given function to the index of their respective Lattice objects in
205  // the ProductLattice::lattice[] array
206  std::map<varID, int> varLatticeIndex;
207 
208  // The analysis that identified the variables that are live at this Dataflow node
209  LiveDeadVarsAnalysis* ldva;
210 
211  bool (*filter) (CFGNode cfgn);
212 
213  // Dataflow node that this lattice is associated with and its corresponding node state.
214  DataflowNode n;
215  const NodeState& state;
216 
217  protected:
218  // Minimal constructor that initializes just the portions of the object required to make an
219  // initial blank VarsExprsProductLattice
220  VarsExprsProductLattice(const DataflowNode& n, const NodeState& state, bool (*filter) (CFGNode cfgn));
221 
222  // Returns a blank instance of a VarsExprsProductLattice that only has the fields n and state set
223  virtual VarsExprsProductLattice* blankVEPL(const DataflowNode& n, const NodeState& state)=0;
224 
225  public:
226  // creates a new VarsExprsProductLattice
227  // perVarLattice - sample lattice that will be associated with every variable in scope at node n
228  // it should be assumed that the object pointed to by perVarLattice will be either
229  // used internally by this VarsExprsProductLatticeobject or deallocated
230  // constVarLattices - map of additional variables and their associated lattices, that will be
231  // incorporated into this VarsExprsProductLatticein addition to any other lattices for
232  // currently live variables (these correspond to various useful constant variables like zeroVar)
233  // allVarLattice - the lattice associated with allVar (the variable that represents all of memory)
234  // if allVarLattice==NULL, no support is provided for allVar
235  // ldva - liveness analysis result. This can be set to NULL. Or only live variables at a CFG node will be used to initialize the product lattice
236  // n - the dataflow node that this lattice will be associated with
237  // state - the NodeState at this dataflow node
238  VarsExprsProductLattice(Lattice* perVarLattice,
239  const std::map<varID, Lattice*>& constVarLattices,
240  Lattice* allVarLattice,
241  LiveDeadVarsAnalysis* ldva,
242  const DataflowNode& n, const NodeState& state);
243 
244  // Create a copy of that. It is assumed that the types of all the lattices in VarsExprsProductLattice that are
245  // the same as in this.
247 
249 
250  public:
251 
252  // Returns the Lattice mapped to the given variable or NULL if nothing is mapped to it
253  Lattice* getVarLattice(const varID& var);
254 
255  // Returns the set of all variables mapped by this VarsExprsProductLattice
256  std::set<varID> getAllVars();
257 
258  protected:
259 
260  // Returns the index of var among the variables associated with func
261  // or -1 otherwise
262  int getVarIndex(const varID& var);
263 
264  public:
265 
266  // Overwrites the state of this Lattice with that of that Lattice
267  void copy(Lattice* that);
268  // Set this to be a copy of that. It is assumed that the types of all the lattices in VarsExprsProductLattice
269  // that are the same as in this.
270  void copy(const VarsExprsProductLattice* that);
271 
272  bool meetUpdate(Lattice *that);
273 
274  // Called by analyses to create a copy of this lattice. However, if this lattice maintains any
275  // information on a per-variable basis, these per-variable mappings must be converted from
276  // the current set of variables to another set. This may be needed during function calls,
277  // when dataflow information from the caller/callee needs to be transferred to the callee/calleer.
278  // We do not force child classes to define their own versions of this function since not all
279  // Lattices have per-variable information.
280  // varNameMap - maps all variable names that have changed, in each mapping pair, pair->first is the
281  // old variable and pair->second is the new variable
282  // func - the function that the copy Lattice will now be associated with
283 
285  /*Lattice**/void remapVars(const std::map<varID, varID>& varNameMap, const Function& newFunc);
286 
287  // Called by analyses to copy over from the that Lattice dataflow information into this Lattice.
288  // that contains data for a set of variables and incorporateVars must overwrite the state of just
289  // those variables, while leaving its state for other variables alone.
290  // We do not force child classes to define their own versions of this function since not all
291  // Lattices have per-variable information.
292  void incorporateVars(Lattice* that);
293 
294  // Returns a Lattice that describes the information known within this lattice
295  // about the given expression. By default this could be the entire lattice or any portion of it.
296  // For example, a lattice that maintains lattices for different known variables and expression will
297  // return a lattice for the given expression. Similarly, a lattice that keeps track of constraints
298  // on values of variables and expressions will return the portion of the lattice that relates to
299  // the given expression.
300  // It it legal for this function to return NULL if no information is available.
301  // The function's caller is responsible for deallocating the returned object
302  Lattice* project(SgExpression* expr);
303 
304  // The inverse of project(). The call is provided with an expression and a Lattice that describes
305  // the dataflow state that relates to expression. This Lattice must be of the same type as the lattice
306  // returned by project(). unProject() must incorporate this dataflow state into the overall state it holds.
307  // Call must make an internal copy of the passed-in lattice and the caller is responsible for deallocating it.
308  // Returns true if this causes this to change and false otherwise.
309  bool unProject(SgExpression* expr, Lattice* exprState);
310 
311  // Functions used to inform this lattice that a given variable is now in use (e.g. a variable has entered
312  // scope or an expression is being analyzed) or is no longer in use (e.g. a variable has exited scope or
313  // an expression or variable is dead).
314  // Returns true if this causes this Lattice to change and false otherwise.
315  bool addVar(const varID& var);
316  bool remVar(const varID& var);
317 
318  // Sets the lattice of the given var to be lat.
319  // If the variable is already mapped to some other Lattice,
320  // If *(the current lattice) == *lat, the mapping is not changed
321  // If *(the current lattice) != *lat, the current lattice is deallocated and var is mapped to lat->copy()
322  // Returns true if this causes this Lattice to change and false otherwise.
323  bool addVar(const varID& var, Lattice* lat);
324 
325  // The string that represents this object
326  // If indent!="", every line of this string must be prefixed by indent
327  // The last character of the returned string should not be '\n', even if it is a multi-line string.
328  std::string str(std::string indent="");
329 };
330 
332 {
333  protected:
334  // Minimal constructor that initializes just the portions of the object required to make an
335  // initial blank VarsExprsProductLattice
336  FiniteVarsExprsProductLattice(const DataflowNode& n, const NodeState& state);
337 
338  // Returns a blank instance of a VarsExprsProductLattice that only has the fields n and state set
339  VarsExprsProductLattice* blankVEPL(const DataflowNode& n, const NodeState& state);
340 
341  public:
342  // creates a new VarsExprsProductLattice
343  // perVarLattice - sample lattice that will be associated with every variable in scope at node n
344  // it should be assumed that the object pointed to by perVarLattice will be either
345  // used internally by this VarsExprsProductLattice object or deallocated
346  // constVarLattices - map of additional variables and their associated lattices, that will be
347  // incorporated into this VarsExprsProductLattice in addition to any other lattices for
348  // currently live variables (these correspond to various useful constant variables like zeroVar)
349  // allVarLattice - the lattice associated with allVar (the variable that represents all of memory)
350  // if allVarLattice==NULL, no support is provided for allVar
351  // func - the current function
352  // n - the dataflow node that this lattice will be associated with
353  // state - the NodeState at this dataflow node
354  FiniteVarsExprsProductLattice(Lattice* perVarLattice,
355  const std::map<varID, Lattice*>& constVarLattices,
356  Lattice* allVarLattice,
357  LiveDeadVarsAnalysis* ldva,
358  const DataflowNode& n, const NodeState& state);
359 
361 
362  // returns a copy of this lattice
363  Lattice* copy() const;
364 };
365 
367 {
368  protected:
369  // Minimal constructor that initializes just the portions of the object required to make an
370  // initial blank VarsExprsProductLattice
372 
373  // Returns a blank instance of a VarsExprsProductLattice that only has the fields n and state set
374  VarsExprsProductLattice* blankVEPL(const DataflowNode& n, const NodeState& state);
375 
376  public:
377  // creates a new VarsExprsProductLattice
378  // perVarLattice - sample lattice that will be associated with every variable in scope at node n
379  // it should be assumed that the object pointed to by perVarLattice will be either
380  // used internally by this VarsExprsProductLatticeobject or deallocated
381  // constVarLattices - map of additional variables and their associated lattices, that will be
382  // incorporated into this VarsExprsProductLatticein addition to any other lattices for
383  // currently live variables (these correspond to various useful constant variables like zeroVar)
384  // allVarLattice - the lattice associated with allVar (the variable that represents all of memory)
385  // if allVarLattice==NULL, no support is provided for allVar
386  // func - the current function
387  // n - the dataflow node that this lattice will be associated with
388  // state - the NodeState at this dataflow node
390  const std::map<varID, Lattice*>& constVarLattices,
391  Lattice* allVarLattice,
392  LiveDeadVarsAnalysis* ldva,
393  const DataflowNode& n, const NodeState& state);
394 
396 
397  // returns a copy of this lattice
398  Lattice* copy() const;
399 };
400 
401 // prints the Lattices set by the given LiveDeadVarsAnalysis
402 void printLiveDeadVarsAnalysisStates(LiveDeadVarsAnalysis* da, std::string indent="");
403 
404 #endif
This class represents the concept of a C or C++ statement which contains a expression.
This class represents the concept of a do-while statement.
This class represents the notion of a declared variable.
This class represents the concept of a C and C++ case option (used within a switch statement)...
This class represents the concept of a C Assembler statement (untested).
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.
Apply an analysis A's transfer function at a particular AST node type.
Definition: dataflow.h:84
A node in the control flow graph.
Definition: virtualCFG.h:67
This class represents the base class for all IR nodes within Sage III.
Definition: Cxx_Grammar.h:8322
This class represents the concept of a for loop.
This class represents the concept of an "if" construct.
This class represents the concept of a do-while statement.
This class represents a source project, with a list of SgFile objects and global information about th...
Definition: lattice.h:9
void remapVars(const std::map< varID, varID > &varNameMap, const Function &newFunc)
*Lattice**/void remapVars(const std::map& varNameMap, const Function& newFunc...