4 #include "genericDataflowCommon.h"
14 #include "VirtualCFGIterator.h"
16 #include "CallGraphTraverse.h"
17 #include "analysisCommon.h"
20 #include "latticeFull.h"
21 #include "affineInequality.h"
22 #include "divAnalysis.h"
24 #include "liveDeadVarAnalysis.h"
26 extern int CGDebugLevel;
27 extern int CGmeetDebugLevel;
28 extern int CGprofileLevel;
29 extern int CGdebugTransClosure;
74 constrTypes constrType;
84 std::map<varID, std::map<varID, affineInequality> > vars2Value;
110 std::set<varID> vars;
121 std::set<varID> modifiedVars;
132 std::string annotName;
134 std::set<varID> varsToInclude;
136 n(n), state(state), annotName(annotName), annotVal(annotVal), varsToInclude(varsToInclude) {}
138 n(n), state(state), annotName(annotName), annotVal(annotVal) {}
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 {
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);
157 bool initialized=
true, std::string indent=
"");
162 bool initialized=
true, std::string indent=
"");
167 bool initialized=
true, std::string indent=
"");
182 std::string indent=
"");
187 std::string indent=
"");
197 void initCG(
const Function& func,
const std::set<NodeDesc>& nodes,
bool initialized, std::string indent=
"");
203 void initialize(std::string indent=
"");
216 std::string DivLattices2Str(std::string indent=
"");
224 bool addVar(
const varID& scalar, std::string indent=
"");
229 bool removeVar(
const varID& scalar, std::string indent=
"");
232 const varIDSet& getVars()
const;
235 varIDSet& getVarsMod();
250 bool copyFrom(
ConstrGraph &that, std::string indent=
"");
264 bool diffConstraints(
ConstrGraph &that, std::string indent=
"");
269 bool copyConstraints(
ConstrGraph &that, std::string indent=
"");
280 void eraseConstraints(
bool noBottomCheck=
false, std::string indent=
"");
288 bool eraseVarConstr(
const varID& eraseVar,
bool noConsistencyCheck=
false, std::string indent=
"");
295 bool eraseVarConstrNoDiv(
const varID& eraseVar,
bool noConsistencyCheck=
false, std::string indent=
"");
302 bool eraseVarConstrNoDivVars(
const varID& eraseVar,
bool noConsistencyCheck=
false, std::string indent=
"");
312 bool replaceVar(
const varID& origVar,
const varID& newVar,
bool noConsistencyCheck=
false, std::string indent=
"");
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=
"");
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=
"");
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=
"");
357 bool unionXYsubMap(std::map<varID, affineInequality>& subMap,
const varID& y,
const affineInequality& ineq, std::string indent=
"");
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=
"");
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=
"");
388 static bool varHasAnnot(
const varID& var,
const std::set<std::pair<std::string, void*> >& annots, std::string indent=
"");
393 static bool varHasAnnot(
const varID& var, std::string annotName,
void* annotVal, std::string indent=
"");
404 void remapVars(
const std::map<varID, varID>& varNameMap,
const Function& newFunc) {}
411 void incorporateVars(
Lattice* that) {}
428 bool unProject(
SgExpression* expr,
Lattice* exprState) {
return meetUpdate(exprState,
" "); }
433 ConstrGraph* getProjection(
const varIDSet& focusVars, std::string indent=
"");
440 std::string annotName,
const varIDSet& noAnnot, std::string indent=
"");
447 std::string annotName,
const varIDSet& noAnnot, std::string indent=
"");
453 bool removeVarAnnot(std::string annotName,
void* annot, std::string indent=
"");
458 bool replaceVarAnnot(std::string oldAnnotName,
void* oldAnnot,
459 std::string newAnnotName,
void* newAnnot, std::string indent=
"");
465 bool addVarAnnot(std::string tgtAnnotName,
void* tgtAnnotVal, std::string newAnnotName,
void* newAnnotVal, std::string indent=
"");
474 bool negate(std::string indent=
"");
480 bool assign(
varID x,
varID y,
int a,
int b,
int c, std::string indent=
"");
484 bool assignBot(
varID var, std::string indent=
"");
489 bool assignTop(
varID var, std::string indent=
"");
509 bool assertCond(
const varID& x,
const varID& y,
int a,
int b,
int c, std::string indent=
"");
515 bool assertEq(
const varID& x,
const varID& y,
int a=1,
int b=1,
int c=0, std::string indent=
"");
520 affineInequality::signs getVarSign(
const varID& var, std::string indent=
"");
523 bool isEqZero(
const varID& var, std::string indent=
"");
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); }
532 bool isEqVars(
const varID& v1,
const varID& v2,
int& a,
int& b,
int& c, std::string indent=
"");
536 std::map<varID, affineInequality> getEqVars(
varID var, std::string indent=
"");
539 bool lteVars(
const varID& v1,
const varID& v2,
int a=1,
int b=1,
int c=0, std::string indent=
"");
542 bool ltVars(
const varID& v1,
const varID& v2,
int a=1,
int b=1,
int c=0, std::string indent=
"");
549 std::map<varID, std::map<varID, affineInequality> >::const_iterator curX;
550 std::map<varID, affineInequality>::const_iterator curY;
554 const std::map<
varID, std::map<varID, affineInequality> >::
iterator& curX);
564 void operator ++ (
int);
566 bool operator==(
const leIterator& otherIt)
const;
567 bool operator!=(
const leIterator& otherIt)
const;
578 std::map<varID, std::map<varID, affineInequality> >::const_iterator curX;
579 std::map<varID, affineInequality>::const_iterator curY;
589 const std::map<
varID, std::map<varID, affineInequality> >::
iterator& curX,
590 const std::map<varID, affineInequality>::iterator& curY);
602 const varID& getX()
const;
607 void operator ++ (
int);
609 bool operator==(
const geIterator& otherIt)
const;
610 bool operator!=(
const geIterator& otherIt)
const;
620 bool widenUpdate(
InfiniteLattice* that) {
return widenUpdate(that,
""); }
625 bool widenUpdateLimitToThat(
InfiniteLattice* that, std::string indent=
"");
628 bool widenUpdate_ex(
InfiniteLattice* that_arg,
bool limitToThat, std::string indent=
"");
635 bool meetUpdate(
Lattice* that, std::string indent=
"");
636 bool meetUpdate(
Lattice* that) {
return meetUpdate(that,
""); }
641 bool meetUpdateLimitToThat(
InfiniteLattice* that, std::string indent=
"");
644 bool meetUpdate_ex(
Lattice* that_arg,
bool limitToThat, std::string indent=
"");
647 bool orUpd(
LogicalCond& that, std::string indent=
"");
649 {
return orUpd(that,
""); }
652 bool andUpd(
LogicalCond& that, std::string indent=
"");
654 {
return andUpd(that,
""); }
656 bool andUpd(
ConstrGraph* that, std::string indent=
"");
658 {
return andUpd(that,
""); }
664 bool OrAndWidenUpdate(
ConstrGraph* that,
bool meet,
bool OR,
bool limitToThat, std::string indent=
"");
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=
"");
681 void OrAndWidenUpdate_XinThatNotThis(
682 bool OR,
bool limitToThat,
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=
"");
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=
"");
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=
"");
712 bool transitiveClosure(std::string indent=
"");
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=
"");
737 bool localTransClosure(
const varID& tgtVar, std::string indent=
"");
744 bool checkSelfConsistency(std::string indent=
"");
778 bool containsVar(
const varID& var, std::string indent=
"");
791 bool setVal(
varID x,
varID y,
int a,
int b,
int c,
792 std::string indent=
"");
802 bool setToUninitialized_KeepState(std::string indent=
"");
806 bool setToBottom(std::string indent=
"");
811 bool setToConstrKnown(constrTypes ct,
bool eraseCurConstr=
true, std::string indent=
"");
817 bool setToInconsistent(std::string indent=
"");
822 bool setToTop(
bool onlyIfNotInit=
false, std::string indent=
"");
828 std::pair<levels, constrTypes> getLevel(
bool noConsistencyCheck=
false, std::string indent=
"");
833 bool isSelfConsistent(
bool noConsistencyCheck=
false, std::string indent=
"");
838 bool hasConsistentConstraints(
bool noConsistencyCheck=
false, std::string indent=
"");
844 bool isMaximalState(
bool noConsistencyCheck=
false, std::string indent=
"");
852 std::string str(std::string indent=
"");
853 void varSetStatusToStream(
const std::set<varID>& vars, std::ostringstream& outs,
bool &needEndl, std::string indent=
"");
864 std::string str(std::string indent,
bool useIsBottom);
868 std::string toDOT(std::string graphName);
872 std::string toDOT(std::string graphName, std::set<varID>& focusVars);
878 bool operator == (
Lattice* that);
885 bool mustOutsideRange(
varID x,
int b,
int c,
varID y, std::string indent=
"");
889 bool mayTrue(std::string indent=
"");
890 bool mayTrue() {
return mayTrue(
""); }
898 void beginTransaction(std::string indent=
"");
899 void endTransaction(std::string indent=
"");
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.