ROSE  0.9.9.109
ConstrGraph.h
1 #ifndef CONSTR_GRAPH_H
2 #define CONSTR_GRAPH_H
3 
4 #include "genericDataflowCommon.h"
5 
6 #include <sstream>
7 #include <iostream>
8 #include <string>
9 #include <functional>
10 #include <queue>
11 #include <map>
12 #include <set>
13 
14 #include "VirtualCFGIterator.h"
15 #include "cfgUtils.h"
16 #include "CallGraphTraverse.h"
17 #include "analysisCommon.h"
18 #include "analysis.h"
19 #include "dataflow.h"
20 #include "latticeFull.h"
21 #include "affineInequality.h"
22 #include "divAnalysis.h"
23 // GB : 2011-03-05 (Removing Sign Lattice Dependence)#include "sgnAnalysis.h"
24 #include "liveDeadVarAnalysis.h"
25 
26 extern int CGDebugLevel;
27 extern int CGmeetDebugLevel;
28 extern int CGprofileLevel;
29 extern int CGdebugTransClosure;
30 
31 // top - relations between each pair of variables are unknown or too complex to be representable as affine inequalities (minimal information)
32 // intermediate - some concrete information is known about some variable pairs
33 // bottom - impossible situation (maximal information) (bottom flag = true)
34 
35 // By default the constraint graph is = top. Since this implies a top inequality between every pair, we don't
36 // actually maintain such affineInequality objects. Instead, if there is no affineInequality between a pair of
37 // variables, this itself implies that this affineInequality=top.
38 class ConstrGraph : public virtual InfiniteLattice, public dottable//, public virtual LogicalCond
39 {
40 public:
41  // Possible levels of this constraint graph, defined by their information content in ascending order.
42  typedef enum levels {
43  // Uninitialized constraint graph. Uninitialized constraint graphs behave
44  // just like regular constraint graphs but they are not equal to any other graph
45  // until they are initialized. Any operation that modifies or reads the state
46  // of a constraint graph (not including comparisons or other operations that don't
47  // access individual variable mappings) causes it to become initialized (if it
48  // wasn't already). An uninitialized constraint graph is !=bottom.
49  // printing a graph's contents does not make it initialized.
50  uninitialized = 0,
51  // Constraint graph that has no constraints
52  bottom,
53  // This graph's constraints are defined as a conjunction or disjunction of inequalities.
54  // More details are provided in constrType field
55  constrKnown,
56  // The set of constraints in this graph are too complex to be described as a conjunction of inequalities or
57  // a negation of such a conjunction
58  top};
59 protected:
60  levels level;
61 
62 public:
63  typedef enum {
64  unknown,
65  // This graph's constraints are represented as a conjunction of inequalities.
66  conj,
67  // Constraints are representes as the negation of a conjunction of inequalities.
68  // This is the same as a disjunction of the negations of the same inequalities.
69  negConj,
70  // This graph's constrants are mutually-inconsistent
71  inconsistent
72  } constrTypes;
73 protected:
74  constrTypes constrType;
75 
76  // The function and DataflowNode that this constraint graph corresponds to
77  // as well as the node's state
78  const Function& func;
79  //const DataflowNode& n;
80  const NodeState& state;
81 
82  // Represents constrants (x<=y+c). vars2Value[x] maps to a set of constraint::<y, a, b, c>
83  //std::map<varID, std::map<varID, constraint> > vars2Value;
84  std::map<varID, std::map<varID, affineInequality> > vars2Value;
85 
86  // The LiveDeadVarsAnalysis that identifies the live/dead state of all application variables.
87  // Needed to create a FiniteVarsExprsProductLattice.
89 
90  // To allow the user to modify the graph in several spots before calling isSelfConsistent()
91  // we allow them to perform their modifications inside a transaction and call isSelfConsistent only
92  // at the end of the transaction
93  bool inTransaction;
94 
95  // The divisibility lattices associated with the current CFG node
96  // divL is a map from annotations to product lattices. Each product lattice will only be used to
97  // reason about variables that have the same annotation. When a variable has multiple annotations
98  // only one matching product lattice will be used.
99  // The annotation ""->NULL matches all variables
100  std::map<std::pair<std::string, void*>, FiniteVarsExprsProductLattice*> divL;
101 
102  // The sign lattices associated with the current CFG node
103  // sgnL is a map from annotations to product lattices. Each product lattice will only be used to
104  // reason about variables that have the same annotation. When a variable has multiple annotations
105  // only one matching product lattice will be used.
106  // The annotation ""->NULL matches all variables
107  // GB : 2011-03-05 (Removing Sign Lattice Dependence) std::map<std::pair<std::string, void*>, FiniteVarsExprsProductLattice*> sgnL;
108 
109  // Set of live variables that this constraint graph applies to
110  std::set<varID> vars;
111 
112  // set of variables for which we have divisibility information
113  // noDivVars std::set<varID> divVars;
114 
115  // Flag indicating whether some of the constraints have changed since the last time
116  // this graph was checked for bottom-ness
117  bool constrChanged;
118  // Set of variables the for which we've added constraints since the last transitive closure
119  /* GB 2011-06-02 : newConstrVars->modifiedVars : set<varID> newConstrVars; */
120  // Set of variables the constraints on which have been modified since the last transitive closure
121  std::set<varID> modifiedVars;
122 
123 
124  /**** Constructors & Destructors ****/
125  public:
126  // DataflowNode Descriptor object that summarizes the key info about a DataflowNode
127  // in case this ConstrGraph must represent the state of multiple nodes
128  class NodeDesc {
129  public:
130  const DataflowNode& n;
131  const NodeState& state;
132  std::string annotName;
133  void* annotVal;
134  std::set<varID> varsToInclude; // Set of variables that must be included in the ConstrGraph that describes this node, even if they are not live
135  NodeDesc(const DataflowNode& n, const NodeState& state, std::string annotName, void* annotVal, const std::set<varID>& varsToInclude) :
136  n(n), state(state), annotName(annotName), annotVal(annotVal), varsToInclude(varsToInclude) {}
137  NodeDesc(const DataflowNode& n, const NodeState& state, std::string annotName, void* annotVal) :
138  n(n), state(state), annotName(annotName), annotVal(annotVal) {}
139  NodeDesc(const DataflowNode& n, const NodeState& state) :
140  n(n), state(state), annotName(""), annotVal(NULL) {}
141  bool operator==(const NodeDesc& that) const { return n==that.n && &state==&(that.state) && annotName==that.annotName && annotVal==that.annotVal && varsToInclude==that.varsToInclude; }
142  bool operator<(const NodeDesc& that) const {
143  return (n<that.n) ||
144  (n==that.n && &state< &(that.state)) ||
145  (n==that.n && &state==&(that.state) && annotName<that.annotName) ||
146  (n==that.n && &state==&(that.state) && annotName==that.annotName && annotVal<that.annotVal) ||
147  (n==that.n && &state==&(that.state) && annotName==that.annotName && annotVal==that.annotVal && varsToInclude<that.varsToInclude);
148  }
149  };
150 
151 protected:
152  ConstrGraph(const Function& func, const DataflowNode& n, const NodeState& state, bool initialized=false, std::string indent="");
153 
154 public:
155  ConstrGraph(const Function& func, const DataflowNode& n, const NodeState& state,
156  LiveDeadVarsAnalysis* ldva, FiniteVarsExprsProductLattice* divL, // GB : 2011-03-05 (Removing Sign Lattice Dependence) FiniteVarsExprsProductLattice* sgnL,
157  bool initialized=true, std::string indent="");
158  ConstrGraph(const Function& func, const DataflowNode& n, const NodeState& state,
159  LiveDeadVarsAnalysis* ldva,
160  const std::map<std::pair<std::string, void*>, FiniteVarsExprsProductLattice*>& divL,
161  // GB : 2011-03-05 (Removing Sign Lattice Dependence)const std::map<std::pair<std::string, void*>, FiniteVarsExprsProductLattice*>& sgnL,
162  bool initialized=true, std::string indent="");
163  ConstrGraph(const Function& func, const std::set<NodeDesc>& nodes, const NodeState& state,
164  LiveDeadVarsAnalysis* ldva,
165  const std::map<std::pair<std::string, void*>, FiniteVarsExprsProductLattice*>& divL,
166  // GB : 2011-03-05 (Removing Sign Lattice Dependence)const std::map<std::pair<std::string, void*>, FiniteVarsExprsProductLattice*>& sgnL,
167  bool initialized=true, std::string indent="");
168 
169  //ConstrGraph(const varIDSet& scalars, const varIDSet& arrays, bool initialized=true);
170 
171  //ConstrGraph(varIDSet& arrays, varIDSet& scalars, FiniteVarsExprsProductLattice* divL, bool initialized=true);
172 
173  ConstrGraph(ConstrGraph &that, bool initialized=true, std::string indent="");
174 
175  ConstrGraph(const ConstrGraph* that, bool initialized=true, std::string indent="");
176 
177  // Creates a constraint graph that contains the given set of inequalities,
179  ConstrGraph(const std::set<varAffineInequality>& ineqs, const Function& func, const DataflowNode& n, const NodeState& state,
181  // GB : 2011-03-05 (Removing Sign Lattice Dependence)FiniteVarsExprsProductLattice* sgnL,
182  std::string indent="");
183  ConstrGraph(const std::set<varAffineInequality>& ineqs, const Function& func, const DataflowNode& n, const NodeState& state,
184  LiveDeadVarsAnalysis* ldva,
185  const std::map<std::pair<std::string, void*>, FiniteVarsExprsProductLattice*>& divL,
186  // GB : 2011-03-05 (Removing Sign Lattice Dependence)const std::map<std::pair<std::string, void*>, FiniteVarsExprsProductLattice*>& sgnL,
187  std::string indent="");
188 
189  protected:
190  // Initialization code that is common to multiple constructors.
191  // func - The function that the object corresponds to
192  // nodes - set of NodeDesc objects, each of which contains
193  // n - a Dataflow node this ConstrGraph corresponds to
194  // state - the NodeState of node n
195  // annotName/annotVal - the annotation that will be associated with all variables live at node n
196  // initialized - If false, starts this ConstrGraph as uninitialized. If false, starts it at bottom.
197  void initCG(const Function& func, const std::set<NodeDesc>& nodes, bool initialized, std::string indent="");
198 
199  public:
200  ~ConstrGraph ();
201 
202  // Initializes this Lattice to its default state, if it is not already initialized
203  void initialize(std::string indent="");
204  void initialize()
205  { initialize(""); }
206 
207  // For a given variable returns the corresponding divisibility variable
208  // noDivVars static varID getDivVar(const varID& scalar);
209 
210  // Returns true if the given variable is a divisibility variable and false otherwise
211  // noDivVars static bool isDivVar(const varID& scalar);
212 
213  // Returns a divisibility product lattice that matches the given variable
214  FiniteVarsExprsProductLattice* getDivLattice(const varID& var, std::string indent="");
215 
216  std::string DivLattices2Str(std::string indent="");
217 
218  // Returns a sign product lattice that matches the given variable
219  // GB : 2011-03-05 (Removing Sign Lattice Dependence)
220  // FiniteVarsExprsProductLattice* getSgnLattice(const varID& var, std::string indent="");
221 
222  // Adds the given variable to the variables list, returning true if this causes
223  // the constraint graph to change and false otherwise.
224  bool addVar(const varID& scalar, std::string indent="");
225 
226  // Removes the given variable and its divisibility variables (if one exists) from the variables list
227  // and removes any constraints that involve them.
228  // Returning true if this causes the constraint graph to change and false otherwise.
229  bool removeVar(const varID& scalar, std::string indent="");
230 
231  // Returns a reference to the constraint graph's set of variables
232  const varIDSet& getVars() const;
233 
234  // Returns a modifiable reference to the constraint graph's set of variables
235  varIDSet& getVarsMod();
236 
237  /***** Copying *****/
238 
239  // Overwrites the state of this Lattice with that of that Lattice
240  void copy(Lattice* that);
241 
242  // Returns a copy of this lattice
243  Lattice* copy() const;
244 
245  // Returns a copy of this LogicalCond object
246  //LogicalCond* copy();
247 
248  // Copies the state of that to this constraint graph
249  // Returns true if this causes this constraint graph's state to change
250  bool copyFrom(ConstrGraph &that, std::string indent="");
251 
252  // Copies the state of That into This constraint graph, but mapping constraints of varFrom to varTo, even
253  // if varFrom is not mapped by This and is only mapped by That. varTo must be mapped by This.
254  // Returns true if this causes this constraint graph's state to change.
255  bool copyFromReplace(ConstrGraph &that, varID varTo, varID varFrom, std::string indent="");
256 
257  // Copies the given var and its associated constrants from that to this.
258  // Returns true if this causes this constraint graph's state to change; false otherwise.
259  bool copyVar(const ConstrGraph& that, const varID& var);
260 
261 protected:
262  // Determines whether constraints in cg are different from
263  // the constraints in this
264  bool diffConstraints(ConstrGraph &that, std::string indent="");
265 
266 public:
267  // Copies the constraints of cg into this constraint graph.
268  // Returns true if this causes this constraint graph's state to change.
269  bool copyConstraints(ConstrGraph &that, std::string indent="");
270 
271  // Copies the constraints of cg associated with varFrom into this constraint graph,
272  // but mapping them instead to varTo.
273  // Returns true if this causes this constraint graph's state to change.
274  bool copyConstraintsReplace(ConstrGraph &that, varID varTo, varID varFrom, std::string indent="");
275 
276  /**** Erasing ****/
277  // erases all constraints from this constraint graph
278  // noBottomCheck - flag indicating whether this function should do nothing if this isBottom() returns
279  // true (=false) or to not bother checking with isBottom (=true)
280  void eraseConstraints(bool noBottomCheck=false, std::string indent="");
281 
282 public:
283  // Erases all constraints that relate to variable eraseVar and its corresponding divisibility variable
284  // from this constraint graph
285  // Returns true if this causes the constraint graph to change and false otherwise
286  // noConsistencyCheck - flag indicating whether this function should explicitly check the self-consisteny of this graph (=false)
287  // or to not bother checking self-consistency and just return the last-known value (=true)
288  bool eraseVarConstr(const varID& eraseVar, bool noConsistencyCheck=false, std::string indent="");
289 
290  // Erases all constraints that relate to variable eraseVar but not its divisibility variable from
291  // this constraint graph
292  // Returns true if this causes the constraint graph to change and false otherwise
293  // noConsistencyCheck - flag indicating whether this function should explicitly check the self-consisteny of this graph (=false)
294  // or to not bother checking self-consistency and just return the last-known value (=true)
295  bool eraseVarConstrNoDiv(const varID& eraseVar, bool noConsistencyCheck=false, std::string indent="");
296 
297  // Erases all constraints between eraseVar and scalars in this constraint graph but leave the constraints
298  // that relate to its divisibility variable alone
299  // Returns true if this causes the constraint graph to change and false otherwise
300  // noConsistencyCheck - flag indicating whether this function should explicitly check the self-consisteny of this graph (=false)
301  // or to not bother checking self-consistency and just return the last-known value (=true)
302  bool eraseVarConstrNoDivVars(const varID& eraseVar, bool noConsistencyCheck=false, std::string indent="");
303 
304  // Removes any constraints between the given pair of variables
305  // Returns true if this causes the constraint graph to change and false otherwise
306  //bool disconnectVars(const varID& x, const varID& y);
307 
308  // Replaces all instances of origVar with newVar. Both are assumed to be scalars.
309  // Returns true if this causes the constraint graph to change and false otherwise
310  // noConsistencyCheck - flag indicating whether this function should explicitly check the self-consisteny of this graph (=false)
311  // or to not bother checking self-consistency and just return the last-known value (=true)
312  bool replaceVar(const varID& origVar, const varID& newVar, bool noConsistencyCheck=false, std::string indent="");
313 
314  protected:
315  // Used by copyAnnotVars() and mergeAnnotVars() to identify variables that are interesting
316  // from their perspective.
317  bool annotInterestingVar(const varID& var, const std::set<std::pair<std::string, void*> >& noCopyAnnots, const std::set<varID>& noCopyVars,
318  const std::string& annotName, void* annotVal, std::string indent="");
319 
320  public:
321  // Copies the constrains on all the variables that have the given annotation (srcAnnotName -> srcAnnotVal).
322  // For each such variable we create a copy variable that is identical except that the
323  // (srcAnnotName -> srcAnnotVal) annotation is replaced with the (tgtAnnotName -> tgtAnnotVal) annotation.
324  // If two variables match the (srcAnnotName -> srcAnnotVal) annotation and the constraint graph has a relation
325  // between them, their copies will have the same relation between each other but will have no relation to the
326  // original variables. If two variables have a relation and only one is copied, then the copy maintains the
327  // original relation to the non-copied variable.
328  // A variable matches the given (srcAnnotName -> srcAnnotVal) annotation if this is one of the variable's annotations
329  // or if srcAnnotName=="" and the variable has no annotations.
330  // Avoids copying variables with annotations in the noCopyAnnots set and variables in the noCopyVars set.
331  // Returns true if this causes the constraint graph to change and false otherwise.
332  bool copyAnnotVars(std::string srcAnnotName, void* srcAnnotVal,
333  std::string tgtAnnotName, void* tgtAnnotVal,
334  const std::set<std::pair<std::string, void*> >& noCopyAnnots,
335  const std::set<varID>& noCopyVars, std::string indent="");
336 
337  // Merges the state of the variables in the constraint graph with the [finalAnnotName -> finalAnnotVal] annotation
338  // with the state of the variables with the [remAnnotName -> remAnnotVal]. Each constraint that involves a variable
339  // with the former annotation and the same variable with the latter annotation is replaced with the union of the
340  // two constraints and will only involve the variable with the [finalAnnotName -> finalAnnotVal] (latter) annotation.
341  // All variables with the [remAnnotName -> remAnnotVal] annotation are removed from the constraint graph.
342  // A variable matches the given (srcAnnotName -> srcAnnotVal) annotation if this is one of the variable's annotations
343  // or if srcAnnotName=="" and the variable has no annotations.
344  // Avoids merging variables with annotations in the noCopyAnnots set and variables in the noCopyVars set.
345  // Returns true if this causes the constraint graph to change and false otherwise.
346  // It is assumed that variables that match [finalAnnotName -> finalAnnotVal] differ from variables that match
347  // [remAnnotName -> remAnnotVal] in only that annotation.
348  bool mergeAnnotVars(const std::string& finalAnnotName, void* finalAnnotVal,
349  const std::string& remAnnotName, void* remAnnotVal,
350  const std::set<std::pair<std::string, void*> >& noCopyAnnots,
351  const std::set<varID>& noCopyVars, std::string indent="");
352 
353 
354  protected:
355  // Union the current inequality for y in the given subMap of vars2Value with the given affine inequality
356  // Returns true if this causes a change in the subMap, false otherwise.
357  bool unionXYsubMap(std::map<varID, affineInequality>& subMap, const varID& y, const affineInequality& ineq, std::string indent="");
358 
359  // Merges the given sub-map of var2Vals, just like mergeAnnotVars. Specifically, for every variable in the subMap
360  // that has a [remAnnotName -> remAnnotVal] annotation,
361  // If there exists a corresponding variable that has the [finalAnnotName -> finalAnnotVal] annotation,
362  // their respective inequalities are unioned. This union is left with the latter variable and the former
363  // variable's entry in subMap is removed
364  // If one does not exist, we simply replace the variable's record with an identical one that now belongs
365  // to its counterpart with the [finalAnnotName -> finalAnnotVal] annotation.
366  // Other entries are left alone.
367  // Returns true if this causes the subMap to change, false otherwise.
368  bool mergeAnnotVarsSubMap(std::map<varID, affineInequality>& subMap,
369  std::string finalAnnotName, void* finalAnnotVal,
370  std::string remAnnotName, void* remAnnotVal,
371  const std::set<std::pair<std::string, void*> >& noCopyAnnots,
372  const std::set<varID>& noCopyVars, std::string indent="");
373 
374  // Support routine for mergeAnnotVars(). Filters out any rem variables in the given set, replacing
375  // them with their corresponding final versions if those final versions are not already in the set
376  // Returns true if this causes the set to change, false otherwise.
377  bool mergeAnnotVarsSet(std::set<varID> varsSet,
378  std::string finalAnnotName, void* finalAnnotVal,
379  std::string remAnnotName, void* remAnnotVal,
380  const std::set<std::pair<std::string, void*> >& noCopyAnnots,
381  const std::set<varID>& noCopyVars, std::string indent="");
382 
383  public:
384 
385  // Returns true if the given variable has an annotation in the given set and false otherwise.
386  // The variable matches an annotation if its name and value directly match or if the variable
387  // has no annotations and the annotation's name is "".
388  static bool varHasAnnot(const varID& var, const std::set<std::pair<std::string, void*> >& annots, std::string indent="");
389 
390  // Returns true if the given variable has an annotation in the given set and false otherwise.
391  // The variable matches an annotation if its name and value directly match or if the variable
392  // has no annotations and the annotName=="".
393  static bool varHasAnnot(const varID& var, std::string annotName, void* annotVal, std::string indent="");
394 
395  // Called by analyses to create a copy of this lattice. However, if this lattice maintains any
396  // information on a per-variable basis, these per-variable mappings must be converted from
397  // the current set of variables to another set. This may be needed during function calls,
398  // when dataflow information from the caller/callee needs to be transferred to the callee/calleer.
399  // We do not force child classes to define their own versions of this function since not all
400  // Lattices have per-variable information.
401  // varNameMap - maps all variable names that have changed, in each mapping pair, pair->first is the
402  // old variable and pair->second is the new variable
403  // func - the function that the copy Lattice will now be associated with
404  void remapVars(const std::map<varID, varID>& varNameMap, const Function& newFunc) {}
405 
406  // Called by analyses to copy over from the that Lattice dataflow information into this Lattice.
407  // that contains data for a set of variables and incorporateVars must overwrite the state of just
408  // those variables, while leaving its state for other variables alone.
409  // We do not force child classes to define their own versions of this function since not all
410  // Lattices have per-variable information.
411  void incorporateVars(Lattice* that) {}
412 
413  // Returns a Lattice that describes the information known within this lattice
414  // about the given expression. By default this could be the entire lattice or any portion of it.
415  // For example, a lattice that maintains lattices for different known variables and expression will
416  // return a lattice for the given expression. Similarly, a lattice that keeps track of constraints
417  // on values of variables and expressions will return the portion of the lattice that relates to
418  // the given expression.
419  // It it legal for this function to return NULL if no information is available.
420  // The function's caller is responsible for deallocating the returned object
421  Lattice* project(SgExpression* expr) { return copy(); }
422 
423  // The inverse of project(). The call is provided with an expression and a Lattice that describes
424  // the dataflow state that relates to expression. This Lattice must be of the same type as the lattice
425  // returned by project(). unProject() must incorporate this dataflow state into the overall state it holds.
426  // Call must make an internal copy of the passed-in lattice and the caller is responsible for deallocating it.
427  // Returns true if this causes this to change and false otherwise.
428  bool unProject(SgExpression* expr, Lattice* exprState) { return meetUpdate(exprState, " "); }
429 
430  // Returns a constraint graph that only includes the constrains in this constraint graph that involve the
431  // variables in focusVars and their respective divisibility variables, if any.
432  // It is assumed that focusVars only contains scalars and not array ranges.
433  ConstrGraph* getProjection(const varIDSet& focusVars, std::string indent="");
434 
435  // Creates a new constraint graph that is the disjoint union of the two given constraint graphs.
436  // The variables in cg1 and cg2 that are not in the noAnnot set, are annotated with cg1Annot and cg2Annot, respectively,
437  // under the name annotName.
438  // cg1 and cg2 are assumed to have identical constraints between variables in the noAnnotset.
439  static ConstrGraph* joinCG(ConstrGraph* cg1, void* cg1Annot, ConstrGraph* cg2, void* cg2Annot,
440  std::string annotName, const varIDSet& noAnnot, std::string indent="");
441 
442  protected:
443  // Copies the per-variable contents of srcCG to tgtCG, while ensuring that in tgtCG all variables that are not
444  // in noAnnot are annotated with the annotName->annot label. For variables in noAnnot, the function ensures
445  // that tgtCG does not have inconsistent mappings between such variables.
446  static void joinCG_copyState(ConstrGraph* tgtCG, ConstrGraph* srcCG, void* annot,
447  std::string annotName, const varIDSet& noAnnot, std::string indent="");
448 
449  public:
450  // Replaces all references to variables with the given annotName->annot annotation to
451  // references to variables without the annotation
452  // Returns true if this causes the constraint graph to change and false otherwise
453  bool removeVarAnnot(std::string annotName, void* annot, std::string indent="");
454 
455  // Replaces all references to variables with the given annotName->annot annotation to
456  // references to variables without the annotation
457  // Returns true if this causes the constraint graph to change and false otherwise
458  bool replaceVarAnnot(std::string oldAnnotName, void* oldAnnot,
459  std::string newAnnotName, void* newAnnot, std::string indent="");
460 
461  // For all variables that have a string (tgtAnnotName -> tgtAnnotVal) annotation
462  // (or if tgtAnnotName=="" and the variable has no annotation), add the annotation
463  // (newAnnotName -> newAnnotVal).
464  // Returns true if this causes the constraint graph to change and false otherwise
465  bool addVarAnnot(std::string tgtAnnotName, void* tgtAnnotVal, std::string newAnnotName, void* newAnnotVal, std::string indent="");
466 
467  // adds a new range into this constraint graph
468  //void addRange(varID rangeVar);
469 
470 public:
471  /**** Transfer Function-Related Updates ****/
472  // Negates the constraint graph.
473  // Returns true if this causes the constraint graph to change and false otherwise
474  bool negate(std::string indent="");
475 
476  // Updates the constraint graph with the information that x*a = y*b+c
477  // Returns true if this causes the constraint graph to change and false otherwise
478  bool assign(const varAffineInequality& cond, std::string indent="");
479  bool assign(varID x, varID y, const affineInequality& ineq, std::string indent="");
480  bool assign(varID x, varID y, int a, int b, int c, std::string indent="");
481 
482  // Updates the constraint graph to record that there are no constraints in the given variable.
483  // Returns true if this causes the constraint graph to change and false otherwise
484  bool assignBot(varID var, std::string indent="");
485 
486  // Updates the constraint graph to record that the constraints between the given variable and
487  // other variables are Top.
488  // Returns true if this causes the constraint graph to change and false otherwise
489  bool assignTop(varID var, std::string indent="");
490 
491 /* // Undoes the i = j + c assignment for backwards analysis
492  void undoAssignment( quad i, quad j, quad c );*/
493 
494 /* // kills all links from variable x to every other variable
495  void killVariable( quad x );
496 */
497 
498  // Add the condition (x*a <= y*b + c) to this constraint graph. The addition is done via a conjunction operator,
499  // meaning that the resulting graph will be left with either (x*a <= y*b + c) or the original condition, whichever is stronger.
500  // returns true if this causes the constraint graph to change and false otherwise
501  bool assertCond(const varAffineInequality& cond, std::string indent="");
502 
503  // add the condition (x*a <= y*b + c) to this constraint graph
504  // returns true if this causes the constraint graph to change and false otherwise
505  bool assertCond(const varID& x, const varID& y, const affineInequality& ineq, std::string indent="");
506 
507  // add the condition (x*a <= y*b + c) to this constraint graph
508  // returns true if this causes the constraint graph to change and false otherwise
509  bool assertCond(const varID& x, const varID& y, int a, int b, int c, std::string indent="");
510 
511  // add the condition (x*a = y*b + c) to this constraint graph
512  // returns true if this causes the constraint graph to change and false otherwise
513  bool assertEq(const varAffineInequality& cond, std::string indent="");
514  bool assertEq(varID x, varID y, const affineInequality& ineq, std::string indent="");
515  bool assertEq(const varID& x, const varID& y, int a=1, int b=1, int c=0, std::string indent="");
516 
517  /**** Dataflow Functions ****/
518 
519  // returns the sign of the given variable
520  affineInequality::signs getVarSign(const varID& var, std::string indent="");
521 
522  // returns true of the given variable is =0 and false otherwise
523  bool isEqZero(const varID& var, std::string indent="");
524 
525  // Returns true if v1*a = v2*b + c and false otherwise
526  bool eqVars(const varID& v1, const varID& v2, int a=1, int b=1, int c=0, std::string indent="");
527  bool eqVars(const varID& v1, const varID& v2, std::string indent="")
528  { return eqVars(v1, v2, 1, 1, 0, indent); }
529 
530  // If v1*a = v2*b + c, sets a, b and c appropriately and returns true.
531  // Otherwise, returns false.
532  bool isEqVars(const varID& v1, const varID& v2, int& a, int& b, int& c, std::string indent="");
533 
534  // Returns a list of variables that are equal to var in this constraint graph as a list of pairs
535  // <x, ineq>, where var*ineq.getA() = x*ineq.getB() + ineq.getC()
536  std::map<varID, affineInequality> getEqVars(varID var, std::string indent="");
537 
538  // Returns true if v1*a <= v2*b + c and false otherwise
539  bool lteVars(const varID& v1, const varID& v2, int a=1, int b=1, int c=0, std::string indent="");
540 
541  // Returns true if v1*a < v2*b + c and false otherwise
542  bool ltVars(const varID& v1, const varID& v2, int a=1, int b=1, int c=0, std::string indent="");
543 
544  // Class used to iterate over all the constraints x*a <= y*b + c for a given variable x
546  {
547  varID x;
548  const ConstrGraph* parent;
549  std::map<varID, std::map<varID, affineInequality> >::const_iterator curX;
550  std::map<varID, affineInequality>::const_iterator curY;
551 
552  public:
553  leIterator(const ConstrGraph* parent,
554  const std::map<varID, std::map<varID, affineInequality> >::iterator& curX);
555 
556  leIterator(const ConstrGraph* parent,
557  const varID& x);
558 
559  bool isDone() const;
560 
561  varAffineInequality operator*() const ;
562 
563  void operator ++ ();
564  void operator ++ (int);
565 
566  bool operator==(const leIterator& otherIt) const;
567  bool operator!=(const leIterator& otherIt) const;
568  };
569  // Beginning and end points of the iteration over all constraints x*a <= y*b + c for a
570  // given variable x.
571  leIterator leBegin(const varID& y);
572  leIterator leEnd();
573 
574  // Class used to iterate over all the constraints x*a <= y*b + c for a given variable y
576  {
577  bool isEnd; // true if this is the end iterator
578  std::map<varID, std::map<varID, affineInequality> >::const_iterator curX;
579  std::map<varID, affineInequality>::const_iterator curY;
580  const ConstrGraph* parent;
581  const varID y;
582 
583  public:
584  geIterator();
585 
586  geIterator(const ConstrGraph* parent, const varID& y);
587 
588  geIterator(const ConstrGraph* parent, const varID& y,
589  const std::map<varID, std::map<varID, affineInequality> >::iterator& curX,
590  const std::map<varID, affineInequality>::iterator& curY);
591 
592  // Advances curX and curY by one step. Returns false if curX/curY is already at the
593  // end of parent.vars2Value and true otherwise (i.e. successful step).
594  bool step();
595 
596  // Move curX/curY to the next x/y pair with a matching y (may leave curX/curY already satisfy this).
597  // Returns true if there are no more such pairs.
598  bool advance();
599 
600  bool isDone() const;
601 
602  const varID& getX() const;
603 
604  varAffineInequality operator*() const ;
605 
606  void operator ++ ();
607  void operator ++ (int);
608 
609  bool operator==(const geIterator& otherIt) const;
610  bool operator!=(const geIterator& otherIt) const;
611  };
612  // Beginning and End points of the iteration over all constraints x*a <= y*b + c for a
613  // given variable y.
614  geIterator geBegin(const varID& y);
615  geIterator geEnd();
616 
617  // widens this from that and saves the result in this
618  // returns true if this causes this to change and false otherwise
619  bool widenUpdate(InfiniteLattice* that, std::string indent="");
620  bool widenUpdate(InfiniteLattice* that) { return widenUpdate(that, ""); }
621 
622  // Widens this from that and saves the result in this, while ensuring that if a given constraint
623  // doesn't exist in that, its counterpart in this is not modified
624  // returns true if this causes this to change and false otherwise
625  bool widenUpdateLimitToThat(InfiniteLattice* that, std::string indent="");
626 
627  // Common code for widenUpdate() and widenUpdateLimitToThat()
628  bool widenUpdate_ex(InfiniteLattice* that_arg, bool limitToThat, std::string indent="");
629 
630  // computes the meet of this and that and saves the result in this
631  // returns true if this causes this to change and false otherwise
632  // The meet is the intersection of constraints: the set of constraints
633  // that is common to both constraint graphs. Thus, the result is the loosest
634  // set of constraints that satisfies both sets and therefore also the information union.
635  bool meetUpdate(Lattice* that, std::string indent="");
636  bool meetUpdate(Lattice* that) { return meetUpdate(that, ""); }
637 
638  // Meet this and that and saves the result in this, while ensuring that if a given constraint
639  // doesn't exist in that, its counterpart in this is not modified
640  // returns true if this causes this to change and false otherwise
641  bool meetUpdateLimitToThat(InfiniteLattice* that, std::string indent="");
642 
643  // Common code for meetUpdate() and meetUpdateLimitToThat()
644  bool meetUpdate_ex(Lattice* that_arg, bool limitToThat, std::string indent="");
645 
646  // <from LogicalCond>
647  bool orUpd(LogicalCond& that, std::string indent="");
648  bool orUpd(LogicalCond& that)
649  { return orUpd(that, ""); }
650 
651  // <from LogicalCond>
652  bool andUpd(LogicalCond& that, std::string indent="");
653  bool andUpd(LogicalCond& that)
654  { return andUpd(that, ""); }
655 
656  bool andUpd(ConstrGraph* that, std::string indent="");
657  bool andUpd(ConstrGraph* that)
658  { return andUpd(that, ""); }
659 
660  // Unified function for Or(meet), And and Widening
661  // If meet == true, this function computes the meet and if =false, computes the widening.
662  // If OR == true, the function computes the OR of each pair of inequalities and otherwise, computes the AND.
663  // if limitToThat == true, if a given constraint does not exist in that, this has no effect on the meet/widening
664  bool OrAndWidenUpdate(ConstrGraph* that, bool meet, bool OR, bool limitToThat, std::string indent="");
665 
666 
667  // Portion of OrAndWidenUpdate that deals with x variables for which there exist x->y mapping
668  // in This but not in That. Increments itThisX and updates modified and modifiedVars in case this
669  // function modifies the constraint graph.
670  void OrAndWidenUpdate_XinThisNotThat(
671  bool OR, bool limitToThat,
672  std::map<varID, std::map<varID, affineInequality> >::iterator& itThisX, bool& modified,
673  std::string indent="");
674 
675  // Portion of OrAndWidenUpdate that deals with x variables for which there exist x->y mapping
676  // in That but not in This. Increments itThisX and updates modified and modifiedVars in case this
677  // function modifies the constraint graph.
678  // additionsToThis - Records the new additions to vars2Value that need to be made after we are done iterating
679  // over it. It guaranteed that the keys mapped by the first level of additionsToThis are not mapped
680  // at the first level by vals2Value.
681  void OrAndWidenUpdate_XinThatNotThis(
682  bool OR, bool limitToThat,
683  ConstrGraph* that,
684  std::map<varID, std::map<varID, affineInequality> >::iterator& itThatX,
685  std::map<varID, std::map<varID, affineInequality> >& additionsToThis,
686  bool& modified, std::string indent="");
687 
688  // Portion of OrAndWidenUpdate that deals with x->y pairs for which there exist x->y mapping
689  // in This but not in That. Increments itThisX and updates modified and modifiedVars in case this
690  // function modifies the constraint graph.
691  void OrAndWidenUpdate_YinThisNotThat(
692  bool OR, bool limitToThat,
693  std::map<varID, std::map<varID, affineInequality> >::iterator& itThisX,
694  std::map<varID, affineInequality>::iterator& itThisY,
695  bool& modified, std::string indent="");
696 
697  // Portion of OrAndWidenUpdate that deals with x->y pairs for which there exist x->y mapping
698  // in That but not in This. Increments itThisX and updates modified and modifiedVars in case this
699  // function modifies the constraint graph.
700  // additionsToThis - Records the new additions to vars2Value[itThisX->first] that need to be made after
701  // we are done iterating over it. It guaranteed that the keys mapped by additionsToThis are not mapped
702  // at the first level by vals2Value[itThisX->first].
703  void OrAndWidenUpdate_YinThatNotThis(
704  bool OR, bool limitToThat,
705  std::map<varID, std::map<varID, affineInequality> >::iterator& itThatX,
706  std::map<varID, affineInequality>::iterator& itThatY,
707  std::map<varID, affineInequality>& additionsToThis,
708  bool& modified, std::string indent="");
709 
710  // Computes the transitive closure of the given constraint graph, and updates the graph to be that transitive closure.
711  // Returns true if this causes the graph to change and false otherwise.
712  bool transitiveClosure(std::string indent="");
713  protected:
714  bool transitiveClosureDiv(std::string indent="");
715  void transitiveClosureY(const varID& x, const varID& y, bool& modified, int& numSteps, int& numInfers, bool& iterModified, std::string indent="");
716  void transitiveClosureZ(const varID& x, const varID& y, const varID& z, bool& modified, int& numSteps, int& numInfers, bool& iterModified, std::string indent="");
717 
718  public:
719  // Computes the transitive closure of the given constraint graph,
720  // focusing on the constraints of scalars that have divisibility variables
721  // we only bother propagating constraints to each such variable through its divisibility variable
722  // Returns true if this causes the graph to change and false otherwise.
723  // noDivVars bool divVarsClosure(std::string indent="");
724 
725  // The portion of divVarsClosure that is called for every y variable. Thus, given x and x' (x's divisibility variable)
726  // divVarsClosure_perY() is called for every scalar or array y to infer the x->y connection thru x->x'->y and
727  // infer the y->x connection thru x->x'->x
728  // Returns true if this causes the graph to change and false otherwise.
729  // noDivVars bool divVarsClosure_perY(const varID& x, const varID& divX, const varID& y,
730  // noDivVars affineInequality* constrXDivX, affineInequality* constrDivXX/*,
731  // noDivVars affineInequality::signs xSign, affineInequality::signs ySign*/,
732  // noDivVars std::string indent="");
733 
734  // Computes the transitive closure of this constraint graph while modifying
735  // only the constraints that involve the given variable
736  // Returns true if this causes the graph to change and false otherwise.
737  bool localTransClosure(const varID& tgtVar, std::string indent="");
738 
739 protected:
740  // Searches this constraint graph for negative cycles, which indicates that the constraints represented
741  // by the graph are not self-consistent (the code region where the graph holds is unreachable). Modifies
742  // the level of this graph as needed.
743  // Returns true if this call caused a modification in the graph and false otherwise.
744  bool checkSelfConsistency(std::string indent="");
745 
746 public:
747 
748  // Creates a divisibility variable for the given variable and adds it to the constraint graph
749  // If var = r (mod d), then the relationship between x and x' (the divisibility variable)
750  // will be x = x'*d + r
751  // returns true if this causes the constraint graph to be modified (it may not if this
752  // information is already in the graph) and false otherwise
753  // noDivVars bool addDivVar(varID var/*, int div, int rem*/, bool killDivVar=false, std::string indent="");
754 
755  // Disconnect this variable from all other variables except its divisibility variable. This is done
756  // in order to compute the original variable's relationships while taking its divisibility information
757  // into account.
758  // Returns true if this causes the constraint graph to be modified and false otherwise
759  // noDivVars bool disconnectDivOrigVar(varID var/*, int div, int rem*/, std::string indent="");
760 
761  // Finds the variable within this constraint graph that corresponds to the given divisibility variable.
762  // If such a variable exists, returns the pair <variable, true>.
763  // Otherwise, returns <???, false>.
764  // noDivVars std::pair<varID, bool> divVar2Var(const varID& divVar, std::string indent="");
765 
766  // Adds a new divisibility lattice, with the associated anotation
767  // Returns true if this causes the constraint graph to be modified and false otherwise
768  bool addDivL(FiniteVarsExprsProductLattice* divLattice, std::string annotName, void* annot, std::string indent="");
769 
770  // Adds a new sign lattice, with the associated anotation
771  // Returns true if this causes the constraint graph to be modified and false otherwise
772  // GB : 2011-03-05 (Removing Sign Lattice Dependence)
773  // bool addSgnL(FiniteVarsExprsProductLattice* sgnLattice, std::string annotName, void* annot, std::string indent="");
774 
775  /**** State Accessor Functions *****/
776  // Returns true if this constraint graph includes constraints for the given variable
777  // and false otherwise
778  bool containsVar(const varID& var, std::string indent="");
779 
780  // returns the x->y constraint in this constraint graph
781  affineInequality* getVal(varID x, varID y, std::string indent="");
782 
783  // set the x->y connection in this constraint graph to c
784  // return true if this results this ConstrGraph being changed, false otherwise
785  // xSign, ySign: the default signs for x and y. If they're set to unknown, setVal computes them on its own using getVarSign.
786  // otherwise, it uses the given signs
787  // GB : 2011-03-05 (Removing Sign Lattice Dependence)
788  /*bool setVal(varID x, varID y, int a, int b, int c,
789  affineInequality::signs xSign=affineInequality::unknownSgn, affineInequality::signs ySign=affineInequality::unknownSgn,
790  std::string indent="");*/
791  bool setVal(varID x, varID y, int a, int b, int c,
792  std::string indent="");
793  /*{ return setVal(x, y, a, b, c,
794  // GB : 2011-03-05 (Removing Sign Lattice Dependence)affineInequality::unknownSgn, affineInequality::unknownSgn,
795  indent); }*/
796 
797  bool setVal(varID x, varID y, const affineInequality& ineq, std::string indent="");
798 
799  // Sets the state of this constraint graph to Uninitialized, without modifying its contents. Thus,
800  // the graph will register as uninitalized but when it is next used, its state will already be set up.
801  // Returns true if this causes the constraint graph to be modified and false otherwise.
802  bool setToUninitialized_KeepState(std::string indent="");
803 
804  // Sets the state of this constraint graph to Bottom
805  // Returns true if this causes the constraint graph to be modified and false otherwise.
806  bool setToBottom(std::string indent="");
807 
808  // Sets the state of this constraint graph to constrKnown, with the given constraintType
809  // eraseCurConstr - if true, erases the current set of constraints and if false, leaves them alone
810  // Returns true if this causes the constraint graph to be modified and false otherwise.
811  bool setToConstrKnown(constrTypes ct, bool eraseCurConstr=true, std::string indent="");
812 
813  // Sets the state of this constraint graph to Inconsistent
814  // noConsistencyCheck - flag indicating whether this function should do nothing if this noConsistencyCheck() returns
815  // true (=false) or to not bother checking with isBottom (=true)
816  // Returns true if this causes the constraint graph to be modified and false otherwise.
817  bool setToInconsistent(std::string indent="");
818 
819  // Sets the state of this constraint graph to top
820  // If onlyIfNotInit=true, this is only done if the graph is currently uninitialized
821  // Returns true if this causes the constraint graph to be modified and false otherwise.
822  bool setToTop(bool onlyIfNotInit=false, std::string indent="");
823 
824 
825  // Returns the level and constraint type of this constraint graph
826  // noConsistencyCheck - flag indicating whether this function should explicitly check the self-consisteny of this graph (=false)
827  // or to not bother checking self-consistency and just return the last-known value (=true)
828  std::pair<levels, constrTypes> getLevel(bool noConsistencyCheck=false, std::string indent="");
829 
830  // Returns true if this graph is self-consistent and false otherwise
831  // noConsistencyCheck - flag indicating whether this function should explicitly check the self-consisteny of this graph (=false)
832  // or to not bother checking self-consistency and just return the last-known value (=true)
833  bool isSelfConsistent(bool noConsistencyCheck=false, std::string indent="");
834 
835  // Returns true if this graph has valid constraints and is self-consistent
836  // noConsistencyCheck - flag indicating whether this function should explicitly check the self-consisteny of this graph (=false)
837  // or to not bother checking self-consistency and just return the last-known value (=true)
838  bool hasConsistentConstraints(bool noConsistencyCheck=false, std::string indent="");
839 
840  // Returns true if this constraint graph is maximal in that it can never reach a higher lattice state: it is
841  // either top or inconsistent). Returns false if it not maximal.
842  // noConsistencyCheck - flag indicating whether this function should explicitly check the self-consisteny of this graph (=false)
843  // or to not bother checking self-consistency and just return the last-known value (=true)
844  bool isMaximalState(bool noConsistencyCheck=false, std::string indent="");
845 
846  /**** String Output *****/
847 
848  // Returns the string representation of the constraints held by this constraint graph,
849  // with a line for each pair of variables for which the constraint is < bottom. It also prints
850  // the names of all the arrays that have empty ranges in this constraint graph
851  // There is no \n on the last line of output, even if it is a multi-line string
852  std::string str(std::string indent="");
853  void varSetStatusToStream(const std::set<varID>& vars, std::ostringstream& outs, bool &needEndl, std::string indent="");
854 
855 //protected:
856  // Returns the string representation of the constraints held by this constraint graph,
857  // with a line for each pair of variables for which the constraint is < bottom. It also prints
858  // the names of all the arrays that have empty ranges in this constraint graph
859  // There is no \n on the last line of output, even if it is a multi-line string
860  // If useIsBottom=true, isBottom() is used to determine whether the graph is =bottom.
861  // Otherwise, the bottom variable is checked.
862  // If useIsBottom=true, isBottom() is used to determine whether the graph is =bottom.
863  // Otherwise, the bottom variable is checked.
864  std::string str(std::string indent, bool useIsBottom);
865 
866  // Returns a string that containts the representation of this constraint graph as a graph in the DOT language
867  // that has the given name
868  std::string toDOT(std::string graphName);
869 
870  // Returns a string that containts the representation of this constraint graph as a graph in the DOT language
871  // that has the given name, focusing the graph on just the variables inside focusVars.
872  std::string toDOT(std::string graphName, std::set<varID>& focusVars);
873 
874 public:
875  /**** Comparison Functions ****/
876  bool operator != (ConstrGraph &that);
877  bool operator == (ConstrGraph &that);
878  bool operator == (Lattice* that);
879  bool operator <<= (ConstrGraph &that);
880 
881 
882  // Returns true if x*b+c MUST be outside the range of y and false otherwise.
883  // If two variables are unrelated, it is assumed that there is no information
884  // about their relationship and mustOutsideRange() thus proceeds conservatively (returns true).
885  bool mustOutsideRange(varID x, int b, int c, varID y, std::string indent="");
886 
887  // returns true if this logical condition must be true and false otherwise
888  // <from LogicalCond>
889  bool mayTrue(std::string indent="");
890  bool mayTrue() { return mayTrue(""); }
891 
892 /* // returns true if x+c MUST be inside the range of y and false otherwise
893  // If two variables are unrelated, it is assumed that there is no information
894  // about their relationship and mustInsideRange() thus proceeds conservatively.
895  bool mustInsideRange(varID x, int b, int c, varID y);*/
896 
897  /* Transactions */
898  void beginTransaction(std::string indent="");
899  void endTransaction(std::string indent="");
900 };
901 
902 
903 
904 #endif
905 
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