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