ROSE  0.9.9.139
sequenceStructAnalysis.h
1 #ifndef SEQUENCE_STRUCT_ANALYSIS_H
2 #define SEQUENCE_STRUCT_ANALYSIS_H
3 
4 #include "genericDataflowCommon.h"
5 #include "VirtualCFGIterator.h"
6 #include "cfgUtils.h"
7 #include "CallGraphTraverse.h"
8 #include "analysisCommon.h"
9 #include "analysis.h"
10 #include "dataflow.h"
11 #include "latticeFull.h"
12 #include "divAnalysis.h"
13 #include "ConstrGraph.h"
14 #include "ConstrGraphAnalysis.h"
15 #include "liveDeadVarAnalysis.h"
16 #include "dominatorAnalysis.h"
17 #include "printAnalysisStates.h"
18 
19 extern int sequenceStructAnalysisDebugLevel;
20 
21 // Lattice that stores the structure of the sequence iterated by a variable
22 // or an array access
24 {
25  public:
26  // The sequence's starting and ending points
27  varID vInit;
28  varID vFin;
29  // The sequence's stride
30  int s;
31 
32  public:
33  // The different levels of this lattice
34  typedef enum {
35  // This object is uninitialized
36  uninitialized=0,
37  // No information is known about the sequence
38  bottom=1,
39  // The starting point of the sequence is known (vInit==vFin and s==0)
40  startKnown=2,
41  // The structure of the sequence is known (s!=0)
42  seqKnown=3,
43  // The sequence of values that this variable passes through is more complex than what
44  // can be represented using a lower/upper bound and a constant stride
45  top=4} seqLevel;
46 
47  private:
48  // This object's current level in the lattice: (uninitialized, bottom, startKnown, seqKnown, top)
49  seqLevel level;
50 
51  // The constraint graph associated with the same DataflowNode as this lattice and that holds
52  // the relationships between vInit, vFin and other variables.
53  ConstrGraph* cg;
54 
55  // The analysis that identifies the dominator relationships between DataflowNodes
56  DominatorAnalysis* dom;
57 
58  // The DataflowNode that this lattice corresponds to
59  const DataflowNode& n;
60 
61  public:
62  // Initializes the lattice to level=uninitialized
63  SeqStructLattice(ConstrGraph* cg, const DataflowNode& n, string indent="");
64 
65  // Initializes the lattice to level=startKnown and this->vInit=this->vFin=vInit
66  SeqStructLattice(ConstrGraph* cg, const DataflowNode& n, const varID& vInit, int startOffset, string indent="");
67  // Initializes the lattice to level=startKnown and this->vInit=this->vFin=init
68  SeqStructLattice(ConstrGraph* cg, const DataflowNode& n, int initVal, string indent="");
69 
70  // Initializes the lattice to level=seqKnown and this->vInit=initV this->vFin=finV, this->s=s
71  SeqStructLattice(ConstrGraph* cg, const DataflowNode& n, const varID& initV, const varID& finV, int s, string indent="");
72  // Initializes the lattice to level=seqKnown and this->vInit=initV this->vFin=finV, this->s=s
73  SeqStructLattice(ConstrGraph* cg, const DataflowNode& n, int initV, int finV, int s, string indent="");
74 
75  protected:
76  // Common initialization code for SeqStructLattice
77  void init(string indent="");
78 
79  public:
80  // Copy constructor
81  SeqStructLattice(const SeqStructLattice& that, string indent="");
82 
83  protected:
84  // Copies the state from That sequence to This. Returns true if this causes This to change and false otherwise.
85  bool copyFrom(const SeqStructLattice& that, string indent="");
86 
87  public:
88  // Initializes this Lattice to its default state, if it is not already initialized
89  void initialize();
90 
91  // Returns a copy of this lattice
92  Lattice* copy() const;
93 
94  // Overwrites the state of this Lattice with that of that Lattice
95  void copy(Lattice* that);
96 
97  // Called by analyses to create a copy of this lattice. However, if this lattice maintains any
98  // information on a per-variable basis, these per-variable mappings must be converted from
99  // the current set of variables to another set. This may be needed during function calls,
100  // when dataflow information from the caller/callee needs to be transferred to the callee/calleer.
101  // We do not force child classes to define their own versions of this function since not all
102  // Lattices have per-variable information.
103  // varNameMap - maps all variable names that have changed, in each mapping pair, pair->first is the
104  // old variable and pair->second is the new variable
105  // func - the function that the copy Lattice will now be associated with
106  void remapVars(const map<varID, varID>& varNameMap, const Function& newFunc);
107 
108  // Called by analyses to copy over from the that Lattice dataflow information into this Lattice.
109  // that contains data for a set of variables and incorporateVars must overwrite the state of just
110  // those variables, while leaving its state for other variables alone.
111  // We do not force child classes to define their own versions of this function since not all
112  // Lattices have per-variable information.
113  void incorporateVars(Lattice* that_arg);
114 
115  // Returns a Lattice that describes the information known within this lattice
116  // about the given expression. By default this could be the entire lattice or any portion of it.
117  // For example, a lattice that maintains lattices for different known variables and expression will
118  // return a lattice for the given expression. Similarly, a lattice that keeps track of constraints
119  // on values of variables and expressions will return the portion of the lattice that relates to
120  // the given expression.
121  // It it legal for this function to return NULL if no information is available.
122  // The function's caller is responsible for deallocating the returned object
123  Lattice* project(SgExpression* expr);
124 
125  // The inverse of project(). The call is provided with an expression and a Lattice that describes
126  // the dataflow state that relates to expression. This Lattice must be of the same type as the lattice
127  // returned by project(). unProject() must incorporate this dataflow state into the overall state it holds.
128  // Call must make an internal copy of the passed-in lattice and the caller is responsible for deallocating it.
129  // Returns true if this causes this to change and false otherwise.
130  bool unProject(SgExpression* expr, Lattice* exprState);
131 
132  // Computes the meet of this and that and saves the result in this
133  // returns true if this causes this to change and false otherwise
134  bool meetUpdate(Lattice* that_arg);
135 
136  // Set the level of this object to Bottom.
137  // Return true if this causes ths Lattice to change and false otherwise.
138  bool setToBottom();
139 
140  // Set the level of this object to Top.
141  // Return true if this causes ths Lattice to change and false otherwise.
142  bool setToTop();
143 
144  // Set the level of this object to startKnown, with the given variable starting point (vInit + startOffset).
145  // Return true if this causes ths Lattice to change and false otherwise.
146  bool setToStartKnown(varID vInit, int initOffset);
147 
148  // Set the level of this object to startKnown, with the given constant starting point.
149  // Return true if this causes ths Lattice to change and false otherwise.
150  bool setToStartKnown(int initVal);
151 
152  // Set the level of this object to seqKnown, with the given final point and stride
153  // Return true if this causes ths Lattice to change and false otherwise.
154  bool setToSeqKnown(varID vFin, int finOffset, int stride);
155 
156  // Return this lattice's level
157  seqLevel getLevel() const;
158 
159  bool operator==(Lattice* that);
160 
161  // The string that represents this object
162  // If indent!="", every line of this string must be prefixed by indent
163  // The last character of the returned string should not be '\n', even if it is a multi-line string.
164  string str(string indent="");
165 };
166 
168 {
169  protected:
170  static map<varID, Lattice*> constVars;
171  static bool constVars_init;
172 
173  // The LiveDeadVarsAnalysis that identifies the live/dead state of all application variables.
174  // Needed to create a FiniteVarsExprsProductLattice.
175  LiveDeadVarsAnalysis* ldva;
176 
177  // The DivAnalysis that computes information required for the construction of constraint graphs
178  DivAnalysis* divAnalysis;
179 
180  // The analysis that will be executed concurrently with this analysis and will maintain the relationships
181  // between variables as well as SeqStructLattice initial and final values using ConstrGraphs
182  ConstrGraphAnalysis* cgAnalysis;
183 
184  public:
186  {
187  this->ldva = ldva;
188  this->divAnalysis = divAnalysis;
189  cgAnalysis = new ConstrGraphAnalysis(ldva, divAnalysis);
190  }
191 
192  // generates the initial lattice state for the given dataflow node, in the given function, with the given NodeState
193  //vector<Lattice*> genInitState(const Function& func, const DataflowNode& n, const NodeState& state);
194  void genInitState(const Function& func, const DataflowNode& n, const NodeState& state,
195  vector<Lattice*>& initLattices, vector<NodeFact*>& initFacts);
196 
197  // Returns a map of special constant variables (such as zeroVar) and the lattices that correspond to them
198  // These lattices are assumed to be constants: it is assumed that they are never modified and it is legal to
199  // maintain only one copy of each lattice may for the duration of the analysis.
200  //map<varID, Lattice*>& genConstVarLattices() const;
201 
202  bool transfer(const Function& func, const DataflowNode& n, NodeState& state, const vector<Lattice*>& dfInfo);
203 };
204 
205 // Prints the Lattices set by the given SeqStructAnalysis
206 void printSeqStructAnalysisStates(SeqStructAnalysis* ssa, string indent="");
207 
208 
209 #endif
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.
Definition: lattice.h:9