36 #ifndef MUTABLE_POINTSTO_H_
37 #define MUTABLE_POINTSTO_H_
48 template <
typename Key,
typename KeySet,
typename Data,
typename DataSet>
52 template <
typename Key,
typename KeySet,
typename Data,
typename DataSet>
77 virtual inline void clear()
override
83 virtual inline const DataSet&
getPts(
const Key& var)
override
88 virtual inline const KeySet&
getRevPts(
const Data& datum)
override
90 assert(this->
rev &&
"MutablePTData::getRevPts: constructed without reverse PT support!");
94 virtual inline bool addPts(
const Key &dstKey,
const Data& element)
override
100 virtual inline bool unionPts(
const Key& dstKey,
const Key& srcKey)
override
106 virtual inline bool unionPts(
const Key& dstKey,
const DataSet& srcDataSet)
override
117 virtual void clearPts(
const Key& var,
const Data& element)
override
120 ptsMap[var].reset(element);
125 DataSet &pts =
ptsMap[var];
132 for (
typename PtsMap::value_type &ppt :
ptsMap) ppt.second.checkAndRemap();
138 for (
typename PtsMap::value_type ppt :
ptsMap)
140 const DataSet &pt = ppt.second;
156 return ptd->
getPTDTY() == PTDataTy::MutBase;
163 for (
PtsMapConstIter nodeIt = ptsSet.begin(); nodeIt != ptsSet.end(); nodeIt++)
165 const Key& var = nodeIt->first;
166 const DataSet & pts = nodeIt->second;
169 O << var <<
" ==> { ";
170 for(
typename DataSet::iterator cit = pts.begin(), ecit=pts.end(); cit!=ecit; ++cit)
181 inline bool unionPts(DataSet& dstDataSet,
const DataSet& srcDataSet)
183 return dstDataSet |= srcDataSet;
185 inline bool addPts(DataSet &d,
const Data& e)
187 return d.test_and_set(e);
196 inline void addRevPts(
const DataSet &ptsData,
const Key& tgr)
200 for(iterator it = ptsData.begin(), eit = ptsData.end(); it!=eit; ++it)
226 template <
typename Key,
typename KeySet,
typename Data,
typename DataSet>
251 virtual inline const DataSet&
getPts(
const Key& var)
override
256 virtual inline const KeySet&
getRevPts(
const Data& datum)
override
258 assert(this->
rev &&
"MutableDiffPTData::getRevPts: constructed without reverse PT support!");
262 virtual inline bool addPts(
const Key &dstKey,
const Data& element)
override
264 return mutPTData.addPts(dstKey, element);
267 virtual inline bool unionPts(
const Key& dstKey,
const Key& srcKey)
override
269 return mutPTData.unionPts(dstKey, srcKey);
272 virtual inline bool unionPts(
const Key& dstKey,
const DataSet& srcDataSet)
override
274 return mutPTData.unionPts(dstKey, srcDataSet);
277 virtual void clearPts(
const Key& var,
const Data& element)
override
290 for (
typename PtsMap::value_type &ppt :
diffPtsMap) ppt.second.checkAndRemap();
291 for (
typename PtsMap::value_type &ppt :
propaPtsMap) ppt.second.checkAndRemap();
311 diff.intersectWithComplement(all, propa);
313 return !diff.empty();
320 dstPropa &= srcPropa;
342 return ptd->
getPTDTY() == PTDataTy::MutDiff;
362 template <
typename Key,
typename KeySet,
typename Data,
typename DataSet>
388 virtual inline void clear()
override
393 virtual inline const DataSet&
getPts(
const Key& var)
override
398 virtual inline const KeySet&
getRevPts(
const Data& datum)
override
400 assert(this->
rev &&
"MutableDFPTData::getRevPts: constructed without reverse PT support!");
419 const PtsMap& ptsMap = it->second;
420 return (ptsMap.find(var) != ptsMap.end());
428 const PtsMap& ptsMap = it->second;
429 return (ptsMap.find(var) != ptsMap.end());
491 bool changed =
false;
496 for (
typename PtsMap::const_iterator ptsIt = ptsMap.begin(), ptsEit = ptsMap.end(); ptsIt != ptsEit; ++ptsIt)
498 const Key var = ptsIt->first;
500 if (strongUpdates && var == singleton)
526 virtual inline bool addPts(
const Key &dstKey,
const Key& srcKey)
override
530 virtual inline bool unionPts(
const Key& dstKey,
const Key& srcKey)
override
534 virtual inline bool unionPts(
const Key& dstKey,
const DataSet& srcDataSet)
override
538 virtual void clearPts(
const Key& var,
const Data& element)
override
549 for (
typename DFPtsMap::value_type &lopt :
dfInPtsMap)
551 for (
typename PtsMap::value_type &opt : lopt.second) opt.second.checkAndRemap();
554 for (
typename DFPtsMap::value_type &lopt :
dfOutPtsMap)
556 for (
typename PtsMap::value_type &opt : lopt.second) opt.second.checkAndRemap();
564 for (
typename DFPtsMap::value_type lptsmap :
dfInPtsMap)
566 for (
typename PtsMap::value_type vpt : lptsmap.second)
568 ++allPts[vpt.second];
572 for (
typename DFPtsMap::value_type lptm :
dfOutPtsMap)
574 for (
typename PtsMap::value_type vpt : lptm.second)
576 ++allPts[vpt.second];
599 inline bool unionPts(DataSet& dstDataSet,
const DataSet& srcDataSet)
601 return dstDataSet |= srcDataSet;
603 inline bool addPts(DataSet &d,
const Data& e)
605 return d.test_and_set(e);
617 std::error_code ErrInfo;
618 std::fstream f(
"svfg_pts.data", std::ios_base::out);
633 f <<
"Loc:" << loc <<
" IN:{";
640 f <<
"Loc:" << loc <<
" OUT:{";
657 for (
PtsMapConstIter nodeIt = ptsSet.begin(); nodeIt != ptsSet.end(); nodeIt++)
659 const Key& var = nodeIt->first;
660 const DataSet & pts = nodeIt->second;
663 O <<
"<" << var <<
",{";
681 template <
typename Key,
typename KeySet,
typename Data,
typename DataSet>
765 bool changed =
false;
770 for (
DataIter ptsIt = pts.begin(), ptsEit = pts.end(); ptsIt != ptsEit; ++ptsIt)
772 const Key var = *ptsIt;
774 if (strongUpdates && var == singleton)
808 for (
DataIter ptsIt = pts.begin(), ptsEit = pts.end(); ptsIt != ptsEit; ++ptsIt)
810 const Key var = *ptsIt;
841 it->second.reset(var);
848 return it->second.test(var);
870 it->second.reset(var);
877 return it->second.test(var);
891 template <
typename Key,
typename KeySet,
typename Data,
typename DataSet,
typename VersionedKey,
typename VersionedKeySet>
904 virtual inline void clear()
override
910 virtual const DataSet&
getPts(
const Key& vk)
override
914 virtual const DataSet&
getPts(
const VersionedKey& vk)
override
919 virtual const KeySet&
getRevPts(
const Data& datum)
override
921 assert(this->
rev &&
"MutableVersionedPTData::getRevPts: constructed without reverse PT support!");
926 assert(this->
rev &&
"MutableVersionedPTData::getVersionedKeyRevPts: constructed without reverse PT support!");
930 virtual bool addPts(
const Key& k,
const Data& element)
override
934 virtual bool addPts(
const VersionedKey& vk,
const Data& element)
override
939 virtual bool unionPts(
const Key& dstVar,
const Key& srcVar)
override
941 return tlPTData.unionPts(dstVar, srcVar);
943 virtual bool unionPts(
const VersionedKey& dstVar,
const VersionedKey& srcVar)
override
947 virtual bool unionPts(
const VersionedKey& dstVar,
const Key& srcVar)
override
951 virtual bool unionPts(
const Key& dstVar,
const VersionedKey& srcVar)
override
955 virtual bool unionPts(
const Key& dstVar,
const DataSet& srcDataSet)
override
957 return tlPTData.unionPts(dstVar, srcDataSet);
959 virtual bool unionPts(
const VersionedKey& dstVar,
const DataSet& srcDataSet)
override
964 virtual void clearPts(
const Key& k,
const Data& element)
override
968 virtual void clearPts(
const VersionedKey& vk,
const Data& element)
override
999 SVFUtil::outs() <<
"== Address-taken points-to information\n";
1012 return ptd->
getPTDTY() == PTDataTy::MutVersioned;
const PtsMap & getDFOutPtsMap(LocID loc)
Map< LocID, PtsMap > DFPtsMap
Data-flow point-to map.
virtual bool updateATVPts(const Key &srcVar, LocID dstLoc, const Key &dstVar) override
Update address-taken variables OUT[dstLoc:dstVar] with points-to of top-level pointers.
DFPTData< Key, KeySet, Data, DataSet > BaseDFPTData
virtual bool updateTLVPts(LocID srcLoc, const Key &srcVar, const Key &dstVar) override
Update points-to set of top-level pointers with IN[srcLoc:srcVar].
virtual bool updateAllDFInFromIn(LocID srcLoc, const Key &srcVar, LocID dstLoc, const Key &dstVar) override
Union (IN[dstLoc::dstVar], IN[srcLoc:srcVar]. There is no flag check, unlike the above.
PTData< Key, KeySet, Data, DataSet > BasePTData
virtual const KeySet & getRevPts(const Data &datum) override
Get reverse points-to set of a datum.
DFPtsMap::iterator DFPtsMapIter
BaseMutPTData::PtsMapConstIter PtsMapConstIter
virtual void clearAllDFOutUpdatedVar(LocID) override
virtual void clear() override
Clears all points-to sets as if nothing is stored.
virtual DataSet & getDFInPtsSet(LocID loc, const Key &var) override
virtual const DataSet & getPts(const Key &var) override
Get points-to set of var.
virtual bool updateAllDFOutFromIn(LocID loc, const Key &singleton, bool strongUpdates) override
For each variable var in IN at loc, do updateDFOutFromIn(loc, var, loc, var).
static bool classof(const MutableDFPTData< Key, KeySet, Data, DataSet > *)
const DFPtsMap & getDFOut()
const PtsMap & getDFInPtsMap(LocID loc)
virtual bool updateAllDFInFromOut(LocID srcLoc, const Key &srcVar, LocID dstLoc, const Key &dstVar) override
Union (IN[dstLoc::dstVar], OUT[srcLoc:srcVar]. There is no flag check, unlike the above.
virtual bool updateDFInFromOut(LocID srcLoc, const Key &srcVar, LocID dstLoc, const Key &dstVar) override
Union (IN[dstLoc:dstVar], OUT[srcLoc:srcVar]).
virtual const PtsMap & getPtsMap() const
bool unionPts(DataSet &dstDataSet, const DataSet &srcDataSet)
virtual void dumpPTData() override
virtual ~MutableDFPTData()
virtual bool hasDFInSet(LocID loc) const override
virtual bool hasDFInSet(LocID loc, const Key &var) const override
virtual void clearFullPts(const Key &var) override
Fully clears the points-to set of var.
virtual bool updateDFOutFromIn(LocID srcLoc, const Key &srcVar, LocID dstLoc, const Key &dstVar) override
Union (OUT[dstLoc:dstVar], IN[srcLoc:srcVar]).
virtual bool unionPts(const Key &dstKey, const DataSet &srcDataSet) override
Performs pts(dstVar) = pts(dstVar) U srcDataSet.
virtual DataSet & getDFOutPtsSet(LocID loc, const Key &var) override
virtual bool addPts(const Key &dstKey, const Key &srcKey) override
bool addPts(DataSet &d, const Data &e)
DFPtsMap dfInPtsMap
Data-flow IN set.
virtual bool updateDFInFromIn(LocID srcLoc, const Key &srcVar, LocID dstLoc, const Key &dstVar) override
virtual bool hasDFOutSet(LocID loc) const override
virtual Map< DataSet, unsigned > getAllPts(bool liveOnly) const override
static bool classof(const PTData< Key, KeySet, Data, DataSet > *ptd)
MutablePTData< Key, KeySet, Data, DataSet > mutPTData
MutablePTData< Key, KeySet, Data, DataSet > BaseMutPTData
virtual void remapAllPts(void) override
Remaps all points-to sets to use the current mapping.
DFPtsMap dfOutPtsMap
Data-flow OUT set.
virtual bool unionPts(const Key &dstKey, const Key &srcKey) override
Performs pts(dstVar) = pts(dstVar) U pts(srcVar).
DFPtsMap::const_iterator DFPtsMapconstIter
virtual void clearPts(const Key &var, const Data &element) override
Clears element from the points-to set of var.
BaseMutPTData::PtsMap PtsMap
BaseDFPTData::LocID LocID
virtual void dumpPts(const PtsMap &ptsSet, OutStream &O=SVFUtil::outs()) const
const DFPtsMap & getDFIn()
MutableDFPTData(bool reversePT=true, PTDataTy ty=BaseDFPTData::MutDataFlow)
Constructor.
BasePTData::PTDataTy PTDataTy
virtual bool hasDFOutSet(LocID loc, const Key &var) const override
DiffPTData implemented with points-to sets which are updated continuously.
virtual bool unionPts(const Key &dstKey, const Key &srcKey) override
Performs pts(dstVar) = pts(dstVar) U pts(srcVar).
static bool classof(const MutableDiffPTData< Key, KeySet, Data, DataSet > *)
virtual void updatePropaPtsMap(Key &src, Key &dst) override
MutablePTData< Key, KeySet, Data, DataSet > mutPTData
Backing to implement the basic PTData methods. This allows us to avoid multiple-inheritance.
virtual void clearPropaPts(Key &var) override
Clear propagated points-to set of var.
~MutableDiffPTData() override=default
DataSet & getPropaPts(Key &var)
Get propagated points to.
PTData< Key, KeySet, Data, DataSet > BasePTData
MutablePTData< Key, KeySet, Data, DataSet >::PtsMap PtsMap
virtual void clearPts(const Key &var, const Data &element) override
Clears element from the points-to set of var.
void clear() override
Clears all points-to sets as if nothing is stored.
virtual bool addPts(const Key &dstKey, const Data &element) override
Adds element to the points-to set associated with var.
virtual bool unionPts(const Key &dstKey, const DataSet &srcDataSet) override
Performs pts(dstVar) = pts(dstVar) U srcDataSet.
virtual void remapAllPts(void) override
Remaps all points-to sets to use the current mapping.
virtual const PtsMap & getPtsMap() const
virtual const DataSet & getDiffPts(Key &var) override
Get diff points to.
virtual void clearFullPts(const Key &var) override
Fully clears the points-to set of var.
BasePTData::PTDataTy PTDataTy
PtsMap diffPtsMap
Diff points-to to be propagated.
DiffPTData< Key, KeySet, Data, DataSet > BaseDiffPTData
virtual const DataSet & getPts(const Key &var) override
Get points-to set of var.
virtual bool computeDiffPts(Key &var, const DataSet &all) override
PtsMap propaPtsMap
Points-to already propagated.
virtual const KeySet & getRevPts(const Data &datum) override
Get reverse points-to set of a datum.
virtual Map< DataSet, unsigned > getAllPts(bool liveOnly) const override
virtual void dumpPTData() override
Dump stored keys and points-to sets.
MutableDiffPTData(bool reversePT=true, PTDataTy ty=PTDataTy::Diff)
Constructor.
static bool classof(const PTData< Key, KeySet, Data, DataSet > *ptd)
Incremental version of the mutable data-flow points-to data structure.
PTData< Key, KeySet, Data, DataSet > BasePTData
DataSet::iterator DataIter
virtual bool updateAllDFInFromOut(LocID srcLoc, const Key &srcVar, LocID dstLoc, const Key &dstVar) override
Union (IN[dstLoc::dstVar], OUT[srcLoc:srcVar]. There is no flag check, unlike the above.
void setVarDFInSetUpdated(LocID loc, const Key &var)
Handle address-taken variables whose IN pts changed.
virtual bool updateAllDFOutFromIn(LocID loc, const Key &singleton, bool strongUpdates) override
For each variable var in IN at loc, do updateDFOutFromIn(loc, var, loc, var).
DFPTData< Key, KeySet, Data, DataSet > BaseDFPTData
bool varHasNewDFOutPts(LocID loc, const Key &var)
Return TRUE if var has new pts in loc's OUT set.
MutableDFPTData< Key, KeySet, Data, DataSet > BaseMutDFPTData
BasePTData::PTDataTy PTDataTy
Map< LocID, DataSet > UpdatedVarMap
for propagating only newly added variable in IN/OUT set
BaseDFPTData::LocID LocID
virtual bool updateDFInFromIn(LocID srcLoc, const Key &srcVar, LocID dstLoc, const Key &dstVar) override
virtual bool updateTLVPts(LocID srcLoc, const Key &srcVar, const Key &dstVar) override
Update points-to set of top-level pointers with IN[srcLoc:srcVar].
void setVarDFOutSetUpdated(LocID loc, const Key &var)
Handle address-taken variables whose OUT pts changed.
static bool classof(const MutableIncDFPTData< Key, KeySet, Data, DataSet > *)
UpdatedVarMap::iterator UpdatedVarMapIter
void removeVarFromDFInUpdatedSet(LocID loc, const Key &var)
Remove var from loc's IN updated set.
MutablePTData< Key, KeySet, Data, DataSet > BaseMutPTData
MutableIncDFPTData(bool reversePT=true, PTDataTy ty=BasePTData::MutIncDataFlow)
Constructor.
virtual bool updateDFOutFromIn(LocID srcLoc, const Key &srcVar, LocID dstLoc, const Key &dstVar) override
Union (OUT[dstLoc:dstVar], IN[srcLoc:srcVar]).
static bool classof(const PTData< Key, KeySet, Data, DataSet > *ptd)
virtual bool updateATVPts(const Key &srcVar, LocID dstLoc, const Key &dstVar) override
Update address-taken variables OUT[dstLoc:dstVar] with points-to of top-level pointers.
UpdatedVarMap inUpdatedVarMap
void removeVarFromDFOutUpdatedSet(LocID loc, const Key &var)
Remove var from loc's OUT updated set.
virtual void clearAllDFOutUpdatedVar(LocID loc) override
virtual bool updateDFInFromOut(LocID srcLoc, const Key &srcVar, LocID dstLoc, const Key &dstVar) override
Union (IN[dstLoc:dstVar], OUT[srcLoc:srcVar]).
const DataSet & getDFOutUpdatedVar(LocID loc)
Get all var which have new pts information in loc's OUT set.
virtual bool updateAllDFInFromIn(LocID srcLoc, const Key &srcVar, LocID dstLoc, const Key &dstVar) override
Union (IN[dstLoc::dstVar], IN[srcLoc:srcVar]. There is no flag check, unlike the above.
virtual ~MutableIncDFPTData()
const DataSet & getDFInUpdatedVar(LocID loc)
Get all var which have new pts information in loc's IN set.
bool varHasNewDFInPts(LocID loc, const Key &var)
Return TRUE if var has new pts in loc's IN set.
UpdatedVarMap outUpdatedVarMap
UpdatedVarMap::const_iterator UpdatedVarconstIter
PTData implemented using points-to sets which are created once and updated continuously.
virtual bool unionPts(const Key &dstKey, const Key &srcKey) override
Performs pts(dstVar) = pts(dstVar) U pts(srcVar).
virtual bool unionPts(const Key &dstKey, const DataSet &srcDataSet) override
Performs pts(dstVar) = pts(dstVar) U srcDataSet.
virtual void dumpPTData() override
Dump stored keys and points-to sets.
virtual const KeySet & getRevPts(const Data &datum) override
Get reverse points-to set of a datum.
virtual void remapAllPts(void) override
Remaps all points-to sets to use the current mapping.
virtual void clearFullPts(const Key &var) override
Fully clears the points-to set of var.
void addSingleRevPts(KeySet &revData, const Key &tgr)
MutablePTData(bool reversePT=true, PTDataTy ty=PTDataTy::MutBase)
Constructor.
void clearSingleRevPts(KeySet &revSet, const Key &k)
static bool classof(const PTData< Key, KeySet, Data, DataSet > *ptd)
static bool classof(const MutablePTData< Key, KeySet, Data, DataSet > *)
virtual void clearPts(const Key &var, const Data &element) override
Clears element from the points-to set of var.
Map< Data, KeySet > RevPtsMap
void clearRevPts(const DataSet &pts, const Key &k)
virtual const PtsMap & getPtsMap() const
Return Points-to map.
bool addPts(DataSet &d, const Data &e)
BasePTData::PTDataTy PTDataTy
virtual bool addPts(const Key &dstKey, const Data &element) override
Adds element to the points-to set associated with var.
PTData< Key, KeySet, Data, DataSet > BasePTData
bool unionPts(DataSet &dstDataSet, const DataSet &srcDataSet)
virtual const DataSet & getPts(const Key &var) override
Get points-to set of var.
virtual void clear() override
Clears all points-to sets as if nothing is stored.
PtsMap::iterator PtsMapIter
virtual Map< DataSet, unsigned > getAllPts(bool liveOnly) const override
void addRevPts(const DataSet &ptsData, const Key &tgr)
Map< Key, DataSet > PtsMap
DataSet::iterator iterator
PtsMap::const_iterator PtsMapConstIter
virtual void dumpPts(const PtsMap &ptsSet, OutStream &O=SVFUtil::outs()) const
virtual bool addPts(const Key &k, const Data &element) override
Adds element to the points-to set associated with var.
MutablePTData< Key, KeySet, Data, DataSet > tlPTData
PTData for Keys (top-level pointers, generally).
virtual void clearPts(const VersionedKey &vk, const Data &element) override
PTData< Key, KeySet, Data, DataSet > BasePTData
MutablePTData< VersionedKey, VersionedKeySet, Data, DataSet > atPTData
PTData for VersionedKeys (address-taken objects, generally).
virtual bool unionPts(const VersionedKey &dstVar, const Key &srcVar) override
virtual bool unionPts(const VersionedKey &dstVar, const VersionedKey &srcVar) override
static bool classof(const PTData< Key, KeySet, Data, DataSet > *ptd)
static bool classof(const MutableVersionedPTData< Key, KeySet, Data, DataSet, VersionedKey, VersionedKeySet > *)
virtual Map< DataSet, unsigned > getAllPts(bool liveOnly) const override
virtual void remapAllPts(void) override
Remaps all points-to sets to use the current mapping.
virtual void dumpPTData() override
Dump stored keys and points-to sets.
virtual const KeySet & getRevPts(const Data &datum) override
Get reverse points-to set of a datum.
virtual bool unionPts(const Key &dstVar, const VersionedKey &srcVar) override
virtual void clearFullPts(const Key &k) override
Fully clears the points-to set of var.
VersionedPTData< Key, KeySet, Data, DataSet, VersionedKey, VersionedKeySet > BaseVersionedPTData
virtual bool unionPts(const Key &dstVar, const DataSet &srcDataSet) override
Performs pts(dstVar) = pts(dstVar) U srcDataSet.
virtual bool unionPts(const VersionedKey &dstVar, const DataSet &srcDataSet) override
virtual void clearFullPts(const VersionedKey &vk) override
virtual const DataSet & getPts(const Key &vk) override
Get points-to set of var.
virtual void clearPts(const Key &k, const Data &element) override
Clears element from the points-to set of var.
virtual void clear() override
Clears all points-to sets as if nothing is stored.
MutableVersionedPTData(bool reversePT=true, PTDataTy ty=PTDataTy::MutVersioned)
virtual ~MutableVersionedPTData()
virtual bool unionPts(const Key &dstVar, const Key &srcVar) override
Performs pts(dstVar) = pts(dstVar) U pts(srcVar).
virtual bool addPts(const VersionedKey &vk, const Data &element) override
BasePTData::PTDataTy PTDataTy
virtual const VersionedKeySet & getVersionedKeyRevPts(const Data &datum) override
virtual const DataSet & getPts(const VersionedKey &vk) override
bool rev
Whether we maintain reverse points-to sets or not.
PTDataTy
Types of a points-to data structures.
PTDataTy getPTDTY() const
Get the type of points-to data structure that this is.
void dumpSet(NodeBS To, OutStream &O=SVFUtil::outs())
Dump sparse bitvector set.
std::ostream & outs()
Overwrite llvm::outs()
void removeKey(const Key &key, KeySet &keySet)
Removes an element from a Set/CondSet (or anything implementing ::erase).
void insertKey(const Key &key, KeySet &keySet)
Inserts an element into a Set/CondSet (with ::insert).
std::unordered_map< Key, Value, Hash, KeyEqual, Allocator > Map