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