ROSE  0.11.145.0
divAnalysis.h
1 #include <featureTests.h>
2 #ifdef ROSE_ENABLE_SOURCE_ANALYSIS
3
4 #ifndef DIV_ANALYSIS_H
5 #define DIV_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"
16 #include "printAnalysisStates.h"
17 #include "VariableStateTransfer.h"
18
19 #include <map>
20 #include <string>
21 #include <vector>
22
23 extern int divAnalysisDebugLevel;
24
25 // Maintains value information about live variables. If a given variable may have more than one value,
26 // this object maintains divisibility information about all the possible values (i.e. they're all divisible
27 // by x, with y as the remainder), with the divisior,remainder = (1,0) if nothing better can be found.
28 // There is one DivLattice object for every variable
29 class DivLattice : public FiniteLattice
30 {
31  private:
32  // the current value of the variable (if known)
33  long value;
34  // the <divisor, remainder> pair where for all possible values v of the variable
35  // there exists a multiplier m s.t v = div * m + rem
36  long div;
37  long rem;
38
39  public:
40  // The different levels of this lattice
41  // no information is known about the value of the variable
42  static const int bottom=1;
43  // the value of the variable is known
44  static const int valKnown=2;
45  // value is unknown but the divisibility (div and rem) of this variable is known
46  static const int divKnown=3;
47  // this variable holds more values than can be represented using a single value and divisibility
48  static const int top=4;
49
50  private:
51  // this object's current level in the lattice: (bottom, valKnown, divKnown, top)
52  short level;
53
54  public:
55
56  DivLattice()
57  {
58  value=0;
59  div=-1;
60  rem=-1;
61  level=bottom;
62  }
63
64  DivLattice(long value) {
65  this->value = value;
66  div = -1;
67  rem = -1;
68  level = valKnown;
69  }
70
71  DivLattice(long div, long rem) {
72  value = 0;
73  this->div = div;
74  this->rem = rem;
75  level = divKnown;
76  }
77
78  DivLattice(const DivLattice& that)
79  {
80  this->value = that.value;
81  this->div = that.div;
82  this->rem = that.rem;
83  this->level = that.level;
84  }
85
86  // initializes this Lattice to its default state
87  void initialize()
88  { }
89
90  // returns a copy of this lattice
91  Lattice* copy() const;
92
93  // overwrites the state of this Lattice with that of that Lattice
94  void copy(Lattice* that);
95
96  // returns true if the given value matches the given div, rem combo and false otherwise
97  static bool matchDiv(long value, long div, long rem);
98
99  // Takes two lattices at level divKnown. If the two objects have matching div, rem pairs, returns
100  // true and sets div and rem to those mathching values. Otherwise, returns false;
101  static bool matchDiv(DivLattice* one, DivLattice* two, long& div, long& rem);
102
103  // Takes two lattices at level divKnown. If the two objects have div, rem pairs that make it
104  // possible to add or subtract them them and produce div/rem information where div>1,
105  // returns true and sets div and rem to correspond to the sum of these values.
106  // Otherwise, returns false.
107  // plus - true if the caller want to see one+two and false if one-two
108  static bool matchDivAddSubt(DivLattice* one, DivLattice* two, long& div, long& rem, bool plus);
109
110  // computes the meet of this and that and saves the result in this
111  // returns true if this causes this to change and false otherwise
112  bool meetUpdate(Lattice* that);
113
114  // computes the meet of this and that and returns the result
115  //Lattice* meet(Lattice* that) const;
116
117  bool operator==(Lattice* that);
118
119  /*// widens this from that and saves the result in this
120  // returns true if this causes this to change and false otherwise
121  bool widenUpdate(InfiniteLattice* that);*/
122
123  // returns the current state of this object
124  long getValue() const;
125  long getDiv() const;
126  long getRem() const;
127  short getLevel() const;
128
129  // Sets the state of this lattice to bottom
130  // returns true if this causes the lattice's state to change, false otherwise
131  bool setBot();
132
133  // Sets the state of this lattice to the given value.
134  // returns true if this causes the lattice's state to change, false otherwise
135  bool set(long value);
136
137  // Sets the state of this lattice to the given div/rem state.
138  // returns true if this causes the lattice's state to change, false otherwise
139  bool set(long div, long rem);
140
141  // Sets the state of this lattice to top
142  // returns true if this causes the lattice's state to change, false otherwise
143  bool setTop();
144
145  // Increments the state of this object by increment
146  // returns true if this causes the lattice's state to change, false otherwise
147  bool incr(long increment);
148
149  // Multiplies the state of this object by value
150  // returns true if this causes the lattice's state to change, false otherwise
151  bool mult(long multiplier);
152
153  std::string str(std::string indent="");
154 };
155
156 class DivAnalysisTransfer : public VariableStateTransfer<DivLattice>
157 {
158  template <class T>
159  void visitIntegerValue(T *sgn);
160  void transferIncrement(SgUnaryOp *sgn);
162
163  typedef void (DivAnalysisTransfer::*TransferOp)(DivLattice *, DivLattice *, DivLattice *);
164  template <typename T>
165  void transferArith(SgBinaryOp *sgn, T transferOp);
166  void transferArith(SgBinaryOp *sgn, TransferOp transferOp);
168  void transferMultiplicative(DivLattice *arg1Lat, DivLattice *arg2Lat, DivLattice *resLat);
169  void transferDivision(DivLattice *arg1Lat, DivLattice *arg2Lat, DivLattice *resLat);
170  void transferMod(DivLattice *arg1Lat, DivLattice *arg2Lat, DivLattice *resLat);
171
172 public:
173  // void visit(SgNode *);
174  void visit(SgLongLongIntVal *sgn);
175  void visit(SgLongIntVal *sgn);
176  void visit(SgIntVal *sgn);
177  void visit(SgShortVal *sgn);
178  void visit(SgUnsignedLongLongIntVal *sgn);
179  void visit(SgUnsignedLongVal *sgn);
180  void visit(SgUnsignedIntVal *sgn);
181  void visit(SgUnsignedShortVal *sgn);
182  void visit(SgValueExp *sgn);
183  void visit(SgPlusAssignOp *sgn);
184  void visit(SgMinusAssignOp *sgn);
185  void visit(SgMultAssignOp *sgn);
186  void visit(SgDivAssignOp *sgn);
187  void visit(SgModAssignOp *sgn);
189  void visit(SgSubtractOp *sgn);
190  void visit(SgMultiplyOp *sgn);
191  void visit(SgDivideOp *sgn);
192  void visit(SgModOp *sgn);
193  void visit(SgPlusPlusOp *sgn);
194  void visit(SgMinusMinusOp *sgn);
196  void visit(SgMinusOp *sgn);
197  bool finish() { return modified; }
198
199  DivAnalysisTransfer(const Function& func, const DataflowNode& n, NodeState& state, const std::vector<Lattice*>& dfInfo);
200 };
201
203 {
204  protected:
205  static std::map<varID, Lattice*> constVars;
206  static bool constVars_init;
207
208  // The LiveDeadVarsAnalysis that identifies the live/dead state of all application variables.
209  // Needed to create a FiniteVarsExprsProductLattice.
211
212  public:
214  {
215  this->ldva = ldva;
216  }
217
218  /*// generates the initial variable-specific lattice state for a dataflow node
219  Lattice* genInitVarState(const Function& func, const DataflowNode& n, const NodeState& state);
220
221  // generates the initial non-variable-specific lattice state for a dataflow node
222  Lattice* genInitNonVarState(const Function& func, const DataflowNode& n, const NodeState& state);*/
223
224  // generates the initial lattice state for the given dataflow node, in the given function, with the given NodeState
225  //std::vector<Lattice*> genInitState(const Function& func, const DataflowNode& n, const NodeState& state);
226  void genInitState(const Function& func, const DataflowNode& n, const NodeState& state,
227  std::vector<Lattice*>& initLattices, std::vector<NodeFact*>& initFacts);
228
229  // Returns a map of special constant variables (such as zeroVar) and the lattices that correspond to them
230  // These lattices are assumed to be constants: it is assumed that they are never modified and it is legal to
231  // maintain only one copy of each lattice may for the duration of the analysis.
232  //std::map<varID, Lattice*>& genConstVarLattices() const;
233
234  bool transfer(const Function& func, const DataflowNode& n, NodeState& state, const std::vector<Lattice*>& dfInfo)
235  { ROSE_ABORT(); }
236  boost::shared_ptr<IntraDFTransferVisitor> getTransferVisitor(const Function& func, const DataflowNode& n,
237  NodeState& state, const std::vector<Lattice*>& dfInfo)
238  { return boost::shared_ptr<IntraDFTransferVisitor>(new DivAnalysisTransfer(func, n, state, dfInfo)); }
239 };
240
241 // prints the Lattices set by the given DivAnalysis
242 void printDivAnalysisStates(DivAnalysis* da, std::string indent="");
243
244 #endif
245 #endif
This class represents the notion of a binary operator. It is derived from a SgExpression because oper...
This class represents the notion of a unary operator. It is derived from a SgExpression because opera...
This class represents the notion of an value (expression value).
This class represents the numeric negation of a value. Not to be confused with SgSubtractOp.