ROSE  0.11.96.11
latticeFull.h
1 #include <featureTests.h>
2 #ifdef ROSE_ENABLE_SOURCE_ANALYSIS
3 
4 #ifndef LATTICE_FULL_H
5 #define LATTICE_FULL_H
6 
7 #include "cfgUtils.h"
8 #include "variables.h"
9 #include "nodeState.h"
10 #include "lattice.h"
11 #include <string>
12 #include <map>
13 #include <vector>
14 
15 /******************************
16  *** Commonly used lattices ***
17  ******************************/
18 
20 {
21  // state can be:
22  // -1 : unset (default value)
23  // 0 : false
24  // 1 : true
25  int state;
26 
27  public:
29  { state = -1; }
30 
31  private:
32  BoolAndLattice(int state)
33  { this->state = state; }
34 
35  public:
36  BoolAndLattice(bool state)
37  { this->state = state; }
38 
39  // initializes this Lattice to its default state
40  void initialize()
41  { state = -1; }
42 
43  // returns a copy of this lattice
44  Lattice* copy() const;
45 
46  // overwrites the state of this Lattice with that of that Lattice
47  void copy(Lattice* that);
48 
49  // computes the meet of this and that and saves the result in this
50  // returns true if this causes this to change and false otherwise
51  bool meetUpdate(Lattice* that);
52 
53  // computes the meet of this and that and returns the result
54  //Lattice* meet(Lattice* that);
55 
56  bool operator==(Lattice* that);
57 
58  // returns the current state of this object
59  bool get() const;
60 
61  // sets the state of this BoolAndLattice to the given value
62  // returns true if this causes the BoolAndLattice state to change, false otherwise
63  bool set(bool state);
64 
65  // sets the state of this lattice to the conjunction of the BoolAndLattice's current state and the given value
66  // returns true if this causes the BoolAndLattice state to change, false otherwise
67  bool andUpd(bool state);
68 
69  // Functions used to inform this lattice that a given variable is now in use (e.g. a variable has entered
70  // scope or an expression is being analyzed) or is no longer in use (e.g. a variable has exited scope or
71  // an expression or variable is dead).
72  // It is assumed that a newly-added variable has not been added before and that a variable that is being
73  // removed was previously added
74  // These are empty in this lattice since it is now explicitly aware of variables.
75  /*void addVar(varID var) {};
76  void remVar(varID var) {};*/
77 
78  std::string str(std::string indent="");
79 };
80 
82 {
83  int state;
84 
85  public:
86  static const int infinity;// = 32768;
87 
89  {
90  state = -1;
91  }
92 
93  IntMaxLattice(int state)
94  {
95  this->state = state;
96  }
97 
98  // initializes this Lattice to its default state
99  void initialize()
100  {
101  state = -1;
102  }
103 
104  // returns a copy of this lattice
105  Lattice* copy() const;
106 
107  // overwrites the state of this Lattice with that of that Lattice
108  void copy(Lattice* that);
109 
110  // computes the meet of this and that and saves the result in this
111  // returns true if this causes this to change and false otherwise
112  bool meetUpdate(Lattice* that);
113 
114  // computes the meet of this and that and returns the result
115  //Lattice* meet(Lattice* that);
116 
117  bool operator==(Lattice* that);
118 
119  // widens this from that and saves the result in this
120  // returns true if this causes this to change and false otherwise
121  bool widenUpdate(InfiniteLattice* that);
122 
123  // returns the current state of this object
124  int get() const;
125 
126  // sets the state of this lattice to the given value
127  // returns true if this causes the lattice's state to change, false otherwise
128  bool set(int state);
129 
130  // increments the state of this lattice by the given value
131  // returns true if this causes the lattice's state to change, false otherwise
132  bool incr(int increment);
133 
134  // computes the maximum of the given value and the state of this lattice and saves
135  // the result in this lattice
136  // returns true if this causes the lattice's state to change, false otherwise
137  bool maximum(int value);
138 
139  // Functions used to inform this lattice that a given variable is now in use (e.g. a variable has entered
140  // scope or an expression is being analyzed) or is no longer in use (e.g. a variable has exited scope or
141  // an expression or variable is dead).
142  // It is assumed that a newly-added variable has not been added before and that a variable that is being
143  // removed was previously added
144  // These are empty in this lattice since it is now explicitly aware of variables.
145  /*void addVar(varID var) {};
146  void remVar(varID var) {};*/
147 
148  std::string str(std::string indent="");
149 };
150 
151 /*########################
152  ### Utility lattices ###
153  ########################*/
154 
155 // A container lattice to store other lattices
156 class ProductLattice : public virtual Lattice
157 {
158  public:
159  // The different levels of this lattice
160  static const int uninitialized=0;
161  static const int initialized=1;
162  // This object's current level in the lattice: (uninitialized or initialized)
163  short level;
164 
165  protected:
166  std::vector<Lattice*> lattices;
167 
168  public:
169  ProductLattice();
170  ProductLattice(const std::vector<Lattice*>& lattices);
171  ~ProductLattice();
172 
173  void init(const std::vector<Lattice*>& lattices);
174 
175  // initializes this Lattice to its default state
176  void initialize();
177 
178  const std::vector<Lattice*>& getLattices();
179 
180  // initializes the given vector with a copy of the lattices vector
181  void copy_lattices(std::vector<Lattice*>& newLattices) const;
182 
183  // overwrites the state of this Lattice with that of that Lattice
184  virtual void copy(Lattice* that);
185 
186  // computes the meet of this and that and saves the result in this
187  // returns true if this causes this to change and false otherwise
188  virtual bool meetUpdate(Lattice* that);
189 
190  virtual bool operator==(Lattice* that);
191 
192  int getLevel() { return level; }
193 
194  // Functions used to inform this lattice that a given variable is now in use (e.g. a variable has entered
195  // scope or an expression is being analyzed) or is no longer in use (e.g. a variable has exited scope or
196  // an expression or variable is dead).
197  // It is assumed that a newly-added variable has not been added before and that a variable that is being
198  // removed was previously added
199  // These are empty in this lattice since it is now explicitly aware of variables.
200  /*void addVar(varID var) {};
201  void remVar(varID var) {};*/
202 
203  // The string that represents this object
204  // If indent!="", every line of this string must be prefixed by indent
205  // The last character of the returned string should not be '\n', even if it is a multi-line string.
206  virtual std::string str(std::string indent="");
207 };
208 
209 class FiniteProductLattice : public virtual ProductLattice, public virtual FiniteLattice
210 {
211  public:
213  {}
214 
215  FiniteProductLattice(const std::vector<Lattice*>& lattices) : ProductLattice(lattices), FiniteLattice()
216  {
217  verifyFinite();
218  }
219 
221  {
222  verifyFinite();
223  }
224 
225  void verifyFinite()
226  {
227  for(std::vector<Lattice*>::iterator it = lattices.begin(); it!=lattices.end(); it++)
228  ROSE_ASSERT((*it)->finiteLattice());
229  }
230 
231  // Returns a copy of this lattice
232  Lattice* copy() const
233  {
234  return new FiniteProductLattice(*this);
235  }
236 };
237 
238 class InfiniteProductLattice : public virtual ProductLattice, public virtual InfiniteLattice
239 {
240  public:
242  {}
243 
244  InfiniteProductLattice(const std::vector<Lattice*>& lattices) : ProductLattice(lattices), InfiniteLattice()
245  {}
246 
248  {}
249 
250  // returns a copy of this lattice
251  Lattice* copy() const
252  {
253  return new InfiniteProductLattice(*this);
254  }
255 
256  // Widens this from that and saves the result in this.
257  // Returns true if this causes this to change and false otherwise.
258  bool widenUpdate(InfiniteLattice* that);
259 };
260 
261 
263 {
264  protected:
265  // if =true, a lattice is created for each scalar variable
266  bool includeScalars;
267  // if =true, a lattice is created for each array variable
268  bool includeArrays;
269  // the function that this lattice is associated with
270  Function func;
271  // map of lattices that correspond to constant variables, for quick search
272  std::map<varID, Lattice*> constVarLattices;
273  // lattice that corresponds to allVar;
274  Lattice* allVarLattice;
275 
276  // sample lattice that will be initially associated with every variable (before the analysis)
277  Lattice* perVarLattice;
278 
279  // maps variables in a given function to the index of their respective Lattice objects in
280  // the ProductLattice::lattice[] array
281  static std::map<Function, std::map<varID, int> > varLatticeIndex;
282 
283  public:
284  // creates a new VariablesProductLattice
285  // includeScalars - if =true, a lattice is created for each scalar variable
286  // includeArrays - if =true, a lattice is created for each array variable
287  // perVarLattice - sample lattice that will be associated with every variable in scope at node n
288  // it should be assumed that the object pointed to by perVarLattice will be either
289  // used internally by this VariablesProductLattice object or deallocated
290  // constVarLattices - map of additional variables and their associated lattices, that will be
291  // incorporated into this VariablesProductLattice in addition to any other lattices for
292  // currently live variables (these correspond to various useful constant variables like zeroVar)
293  // allVarLattice - the lattice associated with allVar (the variable that represents all of memory)
294  // if allVarLattice==NULL, no support is provided for allVar
295  // func - the current function
296  // n - the dataflow node that this lattice will be associated with
297  // state - the NodeState at this dataflow node
298  VariablesProductLattice(bool includeScalars, bool includeArrays, Lattice* perVarLattice,
299  const std::map<varID, Lattice*>& constVarLattices, Lattice* allVarLattice,
300  const Function& func, const DataflowNode& n, const NodeState& state);
301 
302  // copy constructor
304 
305  public:
306 
307  Lattice* getVarLattice(const Function& func, const varID& var);
308 
309  protected:
310  // sets up the varLatticeIndex map, if necessary
311  void setUpVarLatticeIndex();
312 
313  // returns the index of var among the variables associated with func
314  // or -1 otherwise
315  int getVarIndex(const Function& func, const varID& var);
316 
317  public:
318 
319  // returns the set of global variables(scalars and/or arrays)
320  varIDSet& getGlobalVars() const;
321  static varIDSet& getGlobalVars(bool includeScalars, bool includeArrays);
322 
323  // returns the set of variables(scalars and/or arrays) declared in this function
324  varIDSet& getLocalVars(Function func) const;
325 
326  // returns the set of variables(scalars and/or arrays) referenced in this function
327  varIDSet& getRefVars(Function func) const;
328 
329  // returns the set of variables(scalars and/or arrays) visible in this function
330  varIDSet getVisibleVars(Function func) const;
331 
332  // returns a copy of this lattice
333  //Lattice* copy() const;
334 
335  // overwrites the state of this Lattice with that of that Lattice
336  void copy(Lattice* that);
337 
338  // Called by analyses to create a copy of this lattice. However, if this lattice maintains any
339  // information on a per-variable basis, these per-variable mappings must be converted from
340  // the current set of variables to another set. This may be needed during function calls,
341  // when dataflow information from the caller/callee needs to be transferred to the callee/calleer.
342  // We do not force child classes to define their own versions of this function since not all
343  // Lattices have per-variable information.
344  // varNameMap - maps all variable names that have changed, in each mapping pair, pair->first is the
345  // old variable and pair->second is the new variable
346  // func - the function that the copy Lattice will now be associated with
347  /*Lattice**/void remapVars(const std::map<varID, varID>& varNameMap, const Function& newFunc);
348 
349  // Called by analyses to copy over from the that Lattice dataflow information into this Lattice.
350  // that contains data for a set of variables and incorporateVars must overwrite the state of just
351  // those variables, while leaving its state for other variables alone.
352  // We do not force child classes to define their own versions of this function since not all
353  // Lattices have per-variable information.
354  void incorporateVars(Lattice* that);
355 
356  // Functions used to inform this lattice that a given variable is now in use (e.g. a variable has entered
357  // scope or an expression is being analyzed) or is no longer in use (e.g. a variable has exited scope or
358  // an expression or variable is dead).
359  // It is assumed that a newly-added variable has not been added before and that a variable that is being
360  // removed was previously added
361  /*void addVar(varID var);
362  void remVar(varID var);*/
363 
364  // The string that represents this object
365  // If indent!="", every line of this string must be prefixed by indent
366  // The last character of the returned string should not be '\n', even if it is a multi-line string.
367  std::string str(std::string indent="");
368 };
369 
371 {
372  public:
373  // creates a new VariablesProductLattice
374  // perVarLattice - sample lattice that will be associated with every variable in scope at node n
375  // it should be assumed that the object pointed to by perVarLattice will be either
376  // used internally by this VariablesProductLattice object or deallocated
377  // constVarLattices - map of additional variables and their associated lattices, that will be
378  // incorporated into this VariablesProductLattice in addition to any other lattices for
379  // currently live variables (these correspond to various useful constant variables like zeroVar)
380  // allVarLattice - the lattice associated with allVar (the variable that represents all of memory)
381  // if allVarLattice==NULL, no support is provided for allVar
382  // func - the current function
383  // n - the dataflow node that this lattice will be associated with
384  // state - the NodeState at this dataflow node
385  FiniteVariablesProductLattice(bool includeScalars, bool includeArrays,
386  Lattice* perVarLattice, const std::map<varID, Lattice*>& constVarLattices, Lattice* allVarLattice,
387  const Function& func, const DataflowNode& n, const NodeState& state) :
388  VariablesProductLattice(includeScalars, includeArrays, perVarLattice, constVarLattices, allVarLattice, func, n, state),
390  {
391  verifyFinite();
392  }
393 
396  {
397  verifyFinite();
398  }
399 
400  // returns a copy of this lattice
401  Lattice* copy() const
402  {
403  return new FiniteVariablesProductLattice(*this);
404  }
405 };
406 
408 {
409  public:
410  // creates a new VariablesProductLattice
411  // perVarLattice - sample lattice that will be associated with every variable in scope at node n
412  // it should be assumed that the object pointed to by perVarLattice will be either
413  // used internally by this VariablesProductLattice object or deallocated
414  // constVarLattices - map of additional variables and their associated lattices, that will be
415  // incorporated into this VariablesProductLattice in addition to any other lattices for
416  // currently live variables (these correspond to various useful constant variables like zeroVar)
417  // allVarLattice - the lattice associated with allVar (the variable that represents all of memory)
418  // if allVarLattice==NULL, no support is provided for allVar
419  // func - the current function
420  // n - the dataflow node that this lattice will be associated with
421  // state - the NodeState at this dataflow node
422  InfiniteVariablesProductLattice(bool includeScalars, bool includeArrays,
423  Lattice* perVarLattice, std::map<varID, Lattice*> constVarLattices, Lattice* allVarLattice,
424  const Function& func, const DataflowNode& n, const NodeState& state) :
425  VariablesProductLattice(includeScalars, includeArrays, perVarLattice, constVarLattices, allVarLattice, func, n, state),
427  {
428  }
429 
432  {
433  }
434 
435  // returns a copy of this lattice
436  Lattice* copy() const
437  {
438  return new InfiniteVariablesProductLattice(*this);
439  }
440 };
441 
442 #endif
443 #endif
Lattice
Definition: lattice.h:12
NodeState
Definition: nodeState.h:92
VirtualCFG::DataflowNode
Definition: DataflowCFG.h:19
FiniteProductLattice
Definition: latticeFull.h:209
InfiniteLattice
Definition: lattice.h:132
VariablesProductLattice
Definition: latticeFull.h:262
FiniteVariablesProductLattice
Definition: latticeFull.h:370
FiniteLattice
Definition: lattice.h:125
InfiniteProductLattice
Definition: latticeFull.h:238
varID
Definition: variables.h:62
BoolAndLattice
Definition: latticeFull.h:19
ProductLattice
Definition: latticeFull.h:156
InfiniteVariablesProductLattice
Definition: latticeFull.h:407
Function
Definition: CallGraphTraverse.h:20
IntMaxLattice
Definition: latticeFull.h:81