1 #include <featureTests.h>
2 #ifdef ROSE_ENABLE_SOURCE_ANALYSIS
7 #include "genericDataflowCommon.h"
17 #include "VirtualCFGIterator.h"
19 #include "CallGraphTraverse.h"
20 #include "analysisCommon.h"
23 #include "latticeFull.h"
24 #include "affineInequality.h"
25 #include "divAnalysis.h"
27 #include "liveDeadVarAnalysis.h"
29 extern int CGDebugLevel;
30 extern int CGmeetDebugLevel;
31 extern int CGprofileLevel;
32 extern int CGdebugTransClosure;
77 constrTypes constrType;
87 std::map<varID, std::map<varID, affineInequality> > vars2Value;
113 std::set<varID> vars;
124 std::set<varID> modifiedVars;
135 std::string annotName;
137 std::set<varID> varsToInclude;
139 n(n), state(state), annotName(annotName), annotVal(annotVal), varsToInclude(varsToInclude) {}
141 n(n), state(state), annotName(annotName), annotVal(annotVal) {}
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 {
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);
160 bool initialized=
true, std::string indent=
"");
165 bool initialized=
true, std::string indent=
"");
170 bool initialized=
true, std::string indent=
"");
185 std::string indent=
"");
190 std::string indent=
"");
200 void initCG(
const Function& func,
const std::set<NodeDesc>& nodes,
bool initialized, std::string indent=
"");
206 void initialize(std::string indent=
"");
219 std::string DivLattices2Str(std::string indent=
"");
227 bool addVar(
const varID& scalar, std::string indent=
"");
232 bool removeVar(
const varID& scalar, std::string indent=
"");
235 const varIDSet& getVars()
const;
238 varIDSet& getVarsMod();
253 bool copyFrom(
ConstrGraph &that, std::string indent=
"");
267 bool diffConstraints(
ConstrGraph &that, std::string indent=
"");
272 bool copyConstraints(
ConstrGraph &that, std::string indent=
"");
283 void eraseConstraints(
bool noBottomCheck=
false, std::string indent=
"");
291 bool eraseVarConstr(
const varID& eraseVar,
bool noConsistencyCheck=
false, std::string indent=
"");
298 bool eraseVarConstrNoDiv(
const varID& eraseVar,
bool noConsistencyCheck=
false, std::string indent=
"");
305 bool eraseVarConstrNoDivVars(
const varID& eraseVar,
bool noConsistencyCheck=
false, std::string indent=
"");
315 bool replaceVar(
const varID& origVar,
const varID& newVar,
bool noConsistencyCheck=
false, std::string indent=
"");
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=
"");
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=
"");
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=
"");
360 bool unionXYsubMap(std::map<varID, affineInequality>& subMap,
const varID& y,
const affineInequality& ineq, std::string indent=
"");
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=
"");
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=
"");
391 static bool varHasAnnot(
const varID& var,
const std::set<std::pair<std::string, void*> >& annots, std::string indent=
"");
396 static bool varHasAnnot(
const varID& var, std::string annotName,
void* annotVal, std::string indent=
"");
407 void remapVars(
const std::map<varID, varID>& varNameMap,
const Function& newFunc) {}
414 void incorporateVars(
Lattice* that) {}
431 bool unProject(
SgExpression* expr,
Lattice* exprState) {
return meetUpdate(exprState,
" "); }
436 ConstrGraph* getProjection(
const varIDSet& focusVars, std::string indent=
"");
443 std::string annotName,
const varIDSet& noAnnot, std::string indent=
"");
450 std::string annotName,
const varIDSet& noAnnot, std::string indent=
"");
456 bool removeVarAnnot(std::string annotName,
void* annot, std::string indent=
"");
461 bool replaceVarAnnot(std::string oldAnnotName,
void* oldAnnot,
462 std::string newAnnotName,
void* newAnnot, std::string indent=
"");
468 bool addVarAnnot(std::string tgtAnnotName,
void* tgtAnnotVal, std::string newAnnotName,
void* newAnnotVal, std::string indent=
"");
477 bool negate(std::string indent=
"");
483 bool assign(
varID x,
varID y,
int a,
int b,
int c, std::string indent=
"");
487 bool assignBot(
varID var, std::string indent=
"");
492 bool assignTop(
varID var, std::string indent=
"");
512 bool assertCond(
const varID& x,
const varID& y,
int a,
int b,
int c, std::string indent=
"");
518 bool assertEq(
const varID& x,
const varID& y,
int a=1,
int b=1,
int c=0, std::string indent=
"");
523 affineInequality::signs getVarSign(
const varID& var, std::string indent=
"");
526 bool isEqZero(
const varID& var, std::string indent=
"");
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); }
535 bool isEqVars(
const varID& v1,
const varID& v2,
int& a,
int& b,
int& c, std::string indent=
"");
539 std::map<varID, affineInequality> getEqVars(
varID var, std::string indent=
"");
542 bool lteVars(
const varID& v1,
const varID& v2,
int a=1,
int b=1,
int c=0, std::string indent=
"");
545 bool ltVars(
const varID& v1,
const varID& v2,
int a=1,
int b=1,
int c=0, std::string indent=
"");
552 std::map<varID, std::map<varID, affineInequality> >::const_iterator curX;
553 std::map<varID, affineInequality>::const_iterator curY;
557 const std::map<
varID, std::map<varID, affineInequality> >::
iterator& curX);
567 void operator ++ (
int);
569 bool operator==(
const leIterator& otherIt)
const;
570 bool operator!=(
const leIterator& otherIt)
const;
581 std::map<varID, std::map<varID, affineInequality> >::const_iterator curX;
582 std::map<varID, affineInequality>::const_iterator curY;
592 const std::map<
varID, std::map<varID, affineInequality> >::
iterator& curX,
593 const std::map<varID, affineInequality>::iterator& curY);
605 const varID& getX()
const;
610 void operator ++ (
int);
612 bool operator==(
const geIterator& otherIt)
const;
613 bool operator!=(
const geIterator& otherIt)
const;
623 bool widenUpdate(
InfiniteLattice* that) {
return widenUpdate(that,
""); }
628 bool widenUpdateLimitToThat(
InfiniteLattice* that, std::string indent=
"");
631 bool widenUpdate_ex(
InfiniteLattice* that_arg,
bool limitToThat, std::string indent=
"");
638 bool meetUpdate(
Lattice* that, std::string indent=
"");
639 bool meetUpdate(
Lattice* that) {
return meetUpdate(that,
""); }
644 bool meetUpdateLimitToThat(
InfiniteLattice* that, std::string indent=
"");
647 bool meetUpdate_ex(
Lattice* that_arg,
bool limitToThat, std::string indent=
"");
650 bool orUpd(
LogicalCond& that, std::string indent=
"");
652 {
return orUpd(that,
""); }
655 bool andUpd(
LogicalCond& that, std::string indent=
"");
657 {
return andUpd(that,
""); }
659 bool andUpd(
ConstrGraph* that, std::string indent=
"");
661 {
return andUpd(that,
""); }
667 bool OrAndWidenUpdate(
ConstrGraph* that,
bool meet,
bool OR,
bool limitToThat, std::string indent=
"");
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=
"");
684 void OrAndWidenUpdate_XinThatNotThis(
685 bool OR,
bool limitToThat,
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=
"");
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=
"");
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=
"");
715 bool transitiveClosure(std::string indent=
"");
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=
"");
740 bool localTransClosure(
const varID& tgtVar, std::string indent=
"");
747 bool checkSelfConsistency(std::string indent=
"");
781 bool containsVar(
const varID& var, std::string indent=
"");
794 bool setVal(
varID x,
varID y,
int a,
int b,
int c,
795 std::string indent=
"");
805 bool setToUninitialized_KeepState(std::string indent=
"");
809 bool setToBottom(std::string indent=
"");
814 bool setToConstrKnown(constrTypes ct,
bool eraseCurConstr=
true, std::string indent=
"");
820 bool setToInconsistent(std::string indent=
"");
825 bool setToTop(
bool onlyIfNotInit=
false, std::string indent=
"");
831 std::pair<levels, constrTypes> getLevel(
bool noConsistencyCheck=
false, std::string indent=
"");
836 bool isSelfConsistent(
bool noConsistencyCheck=
false, std::string indent=
"");
841 bool hasConsistentConstraints(
bool noConsistencyCheck=
false, std::string indent=
"");
847 bool isMaximalState(
bool noConsistencyCheck=
false, std::string indent=
"");
855 std::string str(std::string indent=
"");
856 void varSetStatusToStream(
const std::set<varID>& vars, std::ostringstream& outs,
bool &needEndl, std::string indent=
"");
867 std::string str(std::string indent,
bool useIsBottom);
871 std::string toDOT(std::string graphName);
875 std::string toDOT(std::string graphName, std::set<varID>& focusVars);
881 bool operator == (
Lattice* that);
888 bool mustOutsideRange(
varID x,
int b,
int c,
varID y, std::string indent=
"");
892 bool mayTrue(std::string indent=
"");
893 bool mayTrue() {
return mayTrue(
""); }
901 void beginTransaction(std::string indent=
"");
902 void endTransaction(std::string indent=
"");