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