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