ROSE 0.11.145.192
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
22extern 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
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.
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
209void printSeqStructAnalysisStates(SeqStructAnalysis* ssa, string indent="");
210
211
212#endif
213#endif
This class represents the notion of an expression. Expressions are derived from SgLocatedNodes,...