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