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