ROSE  0.9.9.109
lattice.h
1 #ifndef LATTICE_H
2 #define LATTICE_H
3 
4 #include "CallGraphTraverse.h"
5 #include "variables.h"
6 #include <string>
7 #include <map>
8 
9 class Lattice : public printable
10 {
11  public:
12  // initializes this Lattice to its default state, if it is not already initialized
13  virtual void initialize()=0;
14  // returns a copy/clone of this lattice: TODO rename it to clone, avoid name confusing with copy(Lattice*)
15  virtual Lattice* copy() const=0;
16  // overwrites the state of this Lattice with that of that Lattice
17  virtual void copy(Lattice* that)=0;
18 
19  // Called by analyses to replace variables within the current lattice (pointed by this pointer) with new variables.
20  // This is often needed to propagate lattices across function calls, when dataflow information from
21  // the caller/callee needs to be transferred to the callee/calleer.
22  // The formal arguments/variables will be replaced with actual arguments, or vice versa.
23  //
24  // varNameMap - a read-only map containing information for all variable names that have changed,
25  // in each mapping pair, pair->first is the old variable and pair->second is the new variable
26  // This map is used to update variables within the current lattice.
27  // func - the function that the copy Lattice will now be associated with
28  //
29  // However, if this lattice maintains any information on a per-variable basis, these per-variable mappings
30  // must be converted from the current set of variables to another set.
31  //
32  // We do not force child classes to define their own versions of this function since not all
33  // Lattices have per-variable information.
34  //
35  virtual void remapVars(const std::map<varID, varID>& varNameMap, const Function& newFunc) {}
36 
37  // Called by analyses to copy over from the that Lattice dataflow information into this Lattice.
38  // that contains data for a set of variables.
39  // This function must overwrite the state of just those variables, while leaving its state for other
40  // variables alone.
41  //
42  // We do not force child classes to define their own versions of this function since not all
43  // Lattices have per-variable information.
44  virtual void incorporateVars(Lattice* that) {}
45 
46  // A lattice (this lattice) may contain more information than what is relevant to a given expr.
47  // This function will create a new, potentially smaller, lattice for a given expr.
48  // to describes the information known within this lattice
49  // about the given expression.
50 
51  // By default this could be the entire lattice or any portion of it.
52  //
53  // For example, a live variable lattice may contain a set of live variables. But only one live variable
54  // may relevant to a given expression. This function will create a new lattice containing only a single
55  // variable corresponding to the input expression.
56  //
57  // Another example, a lattice that maintains lattices for different known variables and expression will
58  // return a lattice for the given expression. Similarly, a lattice that keeps track of constraints
59  // on values of variables and expressions will return the portion of the lattice that relates to
60  // the given expression.
61  //
62  // It is legal for this function to return NULL or an empty lattice if no information is available.
63  // The function's caller is responsible for deallocating the returned object
64  //
65  // TODO: this function name really does not refect what it does.
66  // A better name: Lattice * createRelevantLattice(SgExpression* expr)
67  virtual Lattice* project(SgExpression* expr) { return copy(); }
68 
69  // Cherry pick the lattice information which is relevant to expr from exprState, and
70  // merge the picked information into this lattice.
71  // Parameters and return:
72  // - expr: the expression in question
73  // - exprState: a lattice which may or may NOT have information about expr.
74  // - Return true if this lattice is changed by this process.
75  //
76  // The inverse of project(). The call is provided with an expression and a Lattice that describes
77  // the dataflow state that relates to expression. This Lattice must be of the same type as the lattice
78  // returned by project(). unProject() must incorporate this dataflow state into the overall state it holds.
79  // Call must make an internal copy of the passed-in lattice and the caller is responsible for deallocating it.
80  // Returns true if this causes this to change and false otherwise.
81  //
82  // TODO: the semantics of this function is not the exact inverse of project()
83  // TODO: a better name: bool meetRelevantLattice (SgExpression* expr, Lattice* exprState);
84  virtual bool unProject(SgExpression* expr, Lattice* exprState) { return meetUpdate(exprState); }
85 
86  // computes the meet of this lattice and that lattice and saves the result in this lattice
87  // returns true if this causes this lattice to change and false otherwise
88  virtual bool meetUpdate(Lattice* that)=0;
89 
90  // computes the meet of this and that and returns the result
91  //virtual Lattice* meet(Lattice* that)=0;
92 
94  virtual bool finiteLattice()=0;
95 
96  // Equal operator: note the pointer type of that lattice
97  virtual bool operator==(Lattice* that) /*const*/=0;
98  bool operator!=(Lattice* that) {
99  return !(*this == that);
100  }
101  bool operator==(Lattice& that) {
102  return *this == &that;
103  }
104  bool operator!=(Lattice& that) {
105  return !(*this == that);
106  }
107 
108  // Functions used to inform this lattice that a given variable is now in use (e.g. a variable has entered
109  // scope or an expression is being analyzed) or is no longer in use (e.g. a variable has exited scope or
110  // an expression or variable is dead).
111  // It is assumed that a newly-added variable has not been added before and that a variable that is being
112  // removed was previously added
113  /*virtual void addVar(varID var)=0;
114  virtual void remVar(varID var)=0;*/
115 
116  // The string that represents this object
117  // If indent!="", every line of this string must be prefixed by indent
118  // The last character of the returned string should not be '\n', even if it is a multi-line string.
119  //virtual string str(string indent="") /*const*/=0;
120 };
121 
122 class FiniteLattice : public virtual Lattice
123 {
124  public:
126  { return true; }
127 };
128 
129 class InfiniteLattice : public virtual Lattice
130 {
131  public:
133  { return false; }
134 
135  // widens this from that and saves the result in this
136  // returns true if this causes this to change and false otherwise
137  virtual bool widenUpdate(InfiniteLattice* that)=0;
138 };
139 
140 #endif
bool finiteLattice()
Check if this lattice is finite or not.
Definition: lattice.h:125
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.
virtual bool finiteLattice()=0
Check if this lattice is finite or not.
bool finiteLattice()
Check if this lattice is finite or not.
Definition: lattice.h:132
Definition: lattice.h:9