14 #ifndef PERSISTENT_POINTSTO_H_
15 #define PERSISTENT_POINTSTO_H_
25 template <
typename Key,
typename KeySet,
typename Data,
typename DataSet>
26 class PersistentDFPTData;
27 template <
typename Key,
typename KeySet,
typename Data,
typename DataSet>
28 class PersistentIncDFPTData;
29 template <
typename Key,
typename KeySet,
typename Data,
typename DataSet,
typename VersionedKey,
typename VersionedKeySet>
30 class PersistentVersionedPTData;
33 template <
typename Key,
typename KeySet,
typename Data,
typename DataSet>
36 template <
typename K,
typename KS,
typename D,
typename DS,
typename VK,
typename VKS>
59 inline const DataSet&
getPts(
const Key &var)
override
65 inline const KeySet&
getRevPts(
const Data &data)
override
67 assert(this->
rev &&
"PersistentPTData::getRevPts: constructed without reverse PT support!");
71 inline bool addPts(
const Key &dstKey,
const Data &element)
override
79 inline bool unionPts(
const Key& dstKey,
const Key& srcKey)
override
85 inline bool unionPts(
const Key& dstKey,
const DataSet& srcData)
override
95 void clearPts(
const Key &var,
const Data &element)
override
98 toRemoveData.set(element);
102 if (varId != complementId)
104 ptsMap[var] = complementId;
125 for (
const typename KeyToIDMap::value_type &ki :
ptsMap)
147 return ptd->
getPTDTY() == PTDataTy::PersBase;
159 bool changed = newDstId != dstId;
162 ptsMap[dstKey] = newDstId;
199 template <
typename Key,
typename KeySet,
typename Data,
typename DataSet>
224 inline const DataSet &
getPts(
const Key& var)
override
229 inline const KeySet&
getRevPts(
const Data &data)
override
231 assert(this->
rev &&
"PersistentDiffPTData::getRevPts: constructed without reverse PT support!");
235 inline bool addPts(
const Key &dstKey,
const Data &element)
override
240 inline bool unionPts(
const Key& dstKey,
const Key& srcKey)
override
245 inline bool unionPts(
const Key &dstKey,
const DataSet &srcDataSet)
override
247 return persPTData.unionPts(dstKey, srcDataSet);
250 void clearPts(
const Key &var,
const Data &element)
override
318 return ptd->
getPTDTY() == PTDataTy::PersDiff;
333 template <
typename Key,
typename KeySet,
typename Data,
typename DataSet>
358 inline const DataSet &
getPts(
const Key& var)
override
365 assert(
false &&
"PersistentDFPTData::getRevPts: not supported yet!");
369 inline bool unionPts(
const Key& dstKey,
const Key& srcKey)
override
374 inline bool unionPts(
const Key& dstKey,
const DataSet &srcDataSet)
override
376 return persPTData.unionPts(dstKey, srcDataSet);
379 inline bool addPts(
const Key &dstKey,
const Data &element)
override
384 void clearPts(
const Key& var,
const Data &element)
override
416 typename DFKeyToIDMap::const_iterator foundInKeyToId =
dfInPtsMap.find(loc);
417 if (foundInKeyToId ==
dfInPtsMap.end())
return false;
418 const KeyToIDMap &inKeyToId = foundInKeyToId->second;
419 return (inKeyToId.find(var) != inKeyToId.end());
424 typename DFKeyToIDMap::const_iterator foundOutKeyToId =
dfOutPtsMap.find(loc);
425 if (foundOutKeyToId ==
dfOutPtsMap.end())
return false;
426 const KeyToIDMap &outKeyToId = foundOutKeyToId->second;
427 return (outKeyToId.find(var) != outKeyToId.end());
469 bool changed =
false;
473 for (
const typename KeyToIDMap::value_type &ki : inKeyToId)
475 const Key var = ki.first;
477 if (strongUpdates && var == singleton)
continue;
504 for (
const typename DFKeyToIDMap::value_type &lki :
dfInPtsMap)
506 for (
const typename KeyToIDMap::value_type &ki : lki.second)
512 for (
const typename DFKeyToIDMap::value_type &lki :
dfOutPtsMap)
514 for (
const typename KeyToIDMap::value_type &ki : lki.second)
543 return ptd->
getPTDTY() == PTDataTy::PersDataFlow
544 || ptd->
getPTDTY() == PTDataTy::PersIncDataFlow;
553 return oldDst != dst;
579 template <
typename Key,
typename KeySet,
typename Data,
typename DataSet>
662 bool changed =
false;
667 for (
const Key &var : vars)
670 if (strongUpdates && var == singleton)
continue;
705 for (
const Key &var : vars)
753 if (it !=
inUpdatedVarMap.end())
return it->second.find(var) != it->second.end();
783 if (it !=
outUpdatedVarMap.end())
return it->second.find(var) != it->second.end();
804 template <
typename Key,
typename KeySet,
typename Data,
typename DataSet,
typename VersionedKey,
typename VersionedKeySet>
826 const DataSet &
getPts(
const Key& vk)
override
830 const DataSet &
getPts(
const VersionedKey& vk)
override
837 assert(this->
rev &&
"PersistentVersionedPTData::getRevPts: constructed without reverse PT support!");
842 assert(this->
rev &&
"PersistentVersionedPTData::getVersionedKeyRevPts: constructed without reverse PT support!");
846 bool addPts(
const Key& k,
const Data &element)
override
850 bool addPts(
const VersionedKey& vk,
const Data &element)
override
855 bool unionPts(
const Key& dstVar,
const Key& srcVar)
override
857 return tlPTData.unionPts(dstVar, srcVar);
859 bool unionPts(
const VersionedKey& dstVar,
const VersionedKey& srcVar)
override
863 bool unionPts(
const VersionedKey& dstVar,
const Key& srcVar)
override
867 bool unionPts(
const Key& dstVar,
const VersionedKey& srcVar)
override
871 bool unionPts(
const Key &dstVar,
const DataSet &srcDataSet)
override
873 return tlPTData.unionPts(dstVar, srcDataSet);
875 bool unionPts(
const VersionedKey &dstVar,
const DataSet &srcDataSet)
override
880 void clearPts(
const Key& k,
const Data &element)
override
884 void clearPts(
const VersionedKey& vk,
const Data &element)
override
920 SVFUtil::mergePtsOccMaps<DataSet>(allPts,
tlPTData.ptCache.getAllPts());
930 SVFUtil::outs() <<
"== Address-taken points-to information\n";
943 return ptd->
getPTDTY() == PTDataTy::PersVersioned;
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.
DFPTData backed by a PersistentPointsToCache.
void clearFullPts(const Key &var) override
Fully clears the points-to set of var.
Map< LocID, KeyToIDMap > DFKeyToIDMap
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.
bool hasDFInSet(LocID loc) const override
const KeySet & getRevPts(const Data &) override
Get reverse points-to set of a datum.
bool updateDFInFromIn(LocID srcLoc, const Key &srcVar, LocID dstLoc, const Key &dstVar) override
bool updateDFInFromOut(LocID srcLoc, const Key &srcVar, LocID dstLoc, const Key &dstVar) override
Union (IN[dstLoc:dstVar], OUT[srcLoc:srcVar]).
const DataSet & getDFOutPtsSet(LocID loc, const Key &var) override
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.
const DataSet & getPts(const Key &var) override
Get points-to set of var.
bool unionPts(const Key &dstKey, const DataSet &srcDataSet) override
Performs pts(dstVar) = pts(dstVar) U srcDataSet.
bool unionPtsThroughIds(PointsToID &dst, PointsToID &src)
bool unionPts(const Key &dstKey, const Key &srcKey) override
Performs pts(dstVar) = pts(dstVar) U pts(srcVar).
PersistentPTData< Key, KeySet, Data, DataSet > persPTData
PTData for top-level pointers. We will also use its cache for address-taken pointers.
bool hasDFOutSet(LocID loc, const Key &var) const override
PTData< Key, KeySet, Data, DataSet > BasePTData
static bool classof(const PTData< Key, KeySet, Data, DataSet > *ptd)
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 clearPts(const Key &var, const Data &element) override
Clears element from the points-to set of var.
~PersistentDFPTData() override=default
void clearAllDFOutUpdatedVar(LocID) override
DFKeyToIDMap dfInPtsMap
Address-taken points-to sets in IN-sets.
BaseDFPTData::LocID LocID
PersistentDFPTData(PersistentPointsToCache< DataSet > &cache, bool reversePT=true, PTDataTy ty=PTDataTy::PersDataFlow)
bool addPts(const Key &dstKey, const Data &element) override
Adds element to the points-to set associated with var.
const DataSet & getDFInPtsSet(LocID loc, const Key &var) override
bool updateAllDFOutFromIn(LocID loc, const Key &singleton, bool strongUpdates) override
For each variable var in IN at loc, do updateDFOutFromIn(loc, var, loc, var).
PointsToID & getDFOutPtIdRef(LocID loc, const Key &var)
bool updateDFOutFromIn(LocID srcLoc, const Key &srcVar, LocID dstLoc, const Key &dstVar) override
Union (OUT[dstLoc:dstVar], IN[srcLoc:srcVar]).
void clear() override
Clears all points-to sets as if nothing is stored.
void dumpPTData() override
Dump stored keys and points-to sets.
BasePTData::PTDataTy PTDataTy
Map< DataSet, unsigned > getAllPts(bool liveOnly) const override
static bool classof(const PersistentDFPTData< Key, KeySet, Data, DataSet > *)
bool hasDFInSet(LocID loc, const Key &var) const override
DFKeyToIDMap dfOutPtsMap
Address-taken points-to sets in OUT-sets.
bool updateTLVPts(LocID srcLoc, const Key &srcVar, const Key &dstVar) override
Update points-to set of top-level pointers with IN[srcLoc:srcVar].
BasePersPTData::KeyToIDMap KeyToIDMap
void remapAllPts() override
Remaps all points-to sets to use the current mapping.
PersistentPointsToCache< DataSet > & ptCache
bool hasDFOutSet(LocID loc) const override
DFPTData< Key, KeySet, Data, DataSet > BaseDFPTData
PointsToID & getDFInPtIdRef(LocID loc, const Key &var)
PersistentPTData< Key, KeySet, Data, DataSet > BasePersPTData
DiffPTData implemented with a persistent points-to backing.
Map< DataSet, unsigned > getAllPts(bool liveOnly) const override
bool computeDiffPts(Key &var, const DataSet &all) override
PersistentPTData< Key, KeySet, Data, DataSet > persPTData
Backing to implement basic PTData methods. Allows us to avoid multiple inheritance.
PersistentDiffPTData(PersistentPointsToCache< DataSet > &cache, bool reversePT=true, PTDataTy ty=PTDataTy::PersDiff)
Constructor.
~PersistentDiffPTData() override=default
const DataSet & getDiffPts(Key &var) override
Get diff points to.
void dumpPTData() override
Dump stored keys and points-to sets.
DiffPTData< Key, KeySet, Data, DataSet > BaseDiffPTData
PersistentPointsToCache< DataSet > & ptCache
void clearPts(const Key &var, const Data &element) override
Clears element from the points-to set of var.
BasePersPTData::KeyToIDMap KeyToIDMap
static bool classof(const PTData< Key, KeySet, Data, DataSet > *ptd)
void clearPropaPts(Key &var) override
Clear propagated points-to set of var.
bool addPts(const Key &dstKey, const Data &element) override
Adds element to the points-to set associated with var.
BasePTData::PTDataTy PTDataTy
const KeySet & getRevPts(const Data &data) override
Get reverse points-to set of a datum.
PTData< Key, KeySet, Data, DataSet > BasePTData
PersistentPTData< Key, KeySet, Data, DataSet > BasePersPTData
void updatePropaPtsMap(Key &src, Key &dst) override
const DataSet & getPts(const Key &var) override
Get points-to set of var.
KeyToIDMap propaPtsMap
Points-to already propagated.
BasePersPTData::RevPtsMap RevPtsMap
void remapAllPts() override
Remaps all points-to sets to use the current mapping.
KeyToIDMap diffPtsMap
Diff points-to to be propagated.
bool unionPts(const Key &dstKey, const Key &srcKey) override
Performs pts(dstVar) = pts(dstVar) U pts(srcVar).
void clear() override
Clears all points-to sets as if nothing is stored.
void clearFullPts(const Key &var) override
Fully clears the points-to set of var.
bool unionPts(const Key &dstKey, const DataSet &srcDataSet) override
Performs pts(dstVar) = pts(dstVar) U srcDataSet.
static bool classof(const PersistentDiffPTData< Key, KeySet, Data, DataSet > *)
Incremental version of the persistent data-flow points-to data structure.
UpdatedVarMap outUpdatedVarMap
UpdatedVarMap inUpdatedVarMap
const KeySet & getDFInUpdatedVar(LocID loc)
Get all variables which have new pts information in loc's IN set.
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.
void setVarDFInSetUpdated(LocID loc, const Key &var)
Handle address-taken variables whose IN pts changed.
bool updateTLVPts(LocID srcLoc, const Key &srcVar, const Key &dstVar) override
Update points-to set of top-level pointers with IN[srcLoc:srcVar].
BasePTData::PTDataTy PTDataTy
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 PTData< Key, KeySet, Data, DataSet > *ptd)
PersistentIncDFPTData(PersistentPointsToCache< DataSet > &cache, bool reversePT=true, PTDataTy ty=BasePTData::PersIncDataFlow)
Constructor.
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.
bool varHasNewDFInPts(LocID loc, const Key &var)
Return TRUE if var has a new pts in loc's IN set.
bool updateDFInFromIn(LocID srcLoc, const Key &srcVar, LocID dstLoc, const Key &dstVar) override
static bool classof(const PersistentIncDFPTData< Key, KeySet, Data, DataSet > *)
PTData< Key, KeySet, Data, DataSet > BasePTData
BaseDFPTData::LocID LocID
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.
const KeySet & getDFOutUpdatedVar(LocID loc)
Get all variables which have new pts info in loc's OUT set.
void setVarDFOutSetUpdated(LocID loc, const Key &var)
bool updateDFOutFromIn(LocID srcLoc, const Key &srcVar, LocID dstLoc, const Key &dstVar) override
Union (OUT[dstLoc:dstVar], IN[srcLoc:srcVar]).
void clearAllDFOutUpdatedVar(LocID loc) override
Map< LocID, KeySet > UpdatedVarMap
PersistentDFPTData< Key, KeySet, Data, DataSet > BasePersDFPTData
PersistentPTData< Key, KeySet, Data, DataSet > BasePersPTData
void removeVarFromDFOutUpdatedSet(LocID loc, const Key &var)
Remove var from loc's OUT updated set.
void removeVarFromDFInUpdatedSet(LocID loc, const Key &var)
Remove var from loc's IN updated set.
void clear() override
Clears all points-to sets as if nothing is stored.
~PersistentIncDFPTData() override=default
bool varHasNewDFOutPts(LocID loc, const Key &var)
Return TRUE if var has a new pts in loc's OUT set.
DFPTData< Key, KeySet, Data, DataSet > BaseDFPTData
bool updateDFInFromOut(LocID srcLoc, const Key &srcVar, LocID dstLoc, const Key &dstVar) override
Union (IN[dstLoc:dstVar], OUT[srcLoc:srcVar]).
PTData backed by a PersistentPointsToCache.
bool unionPtsFromId(const Key &dstKey, PointsToID srcId)
PersistentPointsToCache< DataSet > & ptCache
static bool classof(const PersistentPTData< Key, KeySet, Data, DataSet > *)
void clearRevPts(const DataSet &pts, const Key &k)
const KeySet & getRevPts(const Data &data) override
Get reverse points-to set of a datum.
Map< DataSet, unsigned > getAllPts(bool liveOnly) const override
void clearSingleRevPts(KeySet &revSet, const Key &k)
bool addPts(const Key &dstKey, const Data &element) override
Adds element to the points-to set associated with var.
void clear() override
Clears all points-to sets as if nothing is stored.
static bool classof(const PTData< Key, KeySet, Data, DataSet > *ptd)
bool unionPts(const Key &dstKey, const Key &srcKey) override
Performs pts(dstVar) = pts(dstVar) U pts(srcVar).
PersistentPTData(PersistentPointsToCache< DataSet > &cache, bool reversePT=true, PTDataTy ty=PTDataTy::PersBase)
Constructor.
~PersistentPTData() override=default
BasePTData::PTDataTy PTDataTy
void remapAllPts() override
Remaps all points-to sets to use the current mapping.
PTData< Key, KeySet, Data, DataSet > BasePTData
void clearPts(const Key &var, const Data &element) override
Clears element from the points-to set of var.
void dumpPTData() override
Dump stored keys and points-to sets.
bool unionPts(const Key &dstKey, const DataSet &srcData) override
Performs pts(dstVar) = pts(dstVar) U srcDataSet.
const DataSet & getPts(const Key &var) override
Get points-to set of var.
Map< Key, PointsToID > KeyToIDMap
Map< Data, KeySet > RevPtsMap
void clearFullPts(const Key &var) override
Fully clears the points-to set of var.
PointsToID unionPts(PointsToID lhs, PointsToID rhs)
Unions lhs and rhs and returns their union's ID.
PointsToID intersectPts(PointsToID lhs, PointsToID rhs)
Intersects lhs and rhs (lhs AND rhs) and returns the intersection's ID.
PointsToID complementPts(PointsToID lhs, PointsToID rhs)
Relatively complements lhs and rhs (lhs \ rhs) and returns it's ID.
void remapAllPts(void)
Remaps all points-to sets stored in the cache to the current mapping.
static PointsToID emptyPointsToId(void)
PointsToID emplacePts(const Data &pts)
const Data & getActualPts(PointsToID id) const
Returns the points-to set which id represents. id must be stored in the cache.
Map< Data, unsigned > getAllPts(void)
void clearFullPts(const Key &k) override
Fully clears the points-to set of var.
bool unionPts(const Key &dstVar, const Key &srcVar) override
Performs pts(dstVar) = pts(dstVar) U pts(srcVar).
PersistentPTData< Key, KeySet, Data, DataSet >::KeyToIDMap KeyToIDMap
static bool classof(const PTData< Key, KeySet, Data, DataSet > *ptd)
static bool classof(const PersistentVersionedPTData< Key, KeySet, Data, DataSet, VersionedKey, VersionedKeySet > *)
PersistentPTData< Key, KeySet, Data, DataSet > tlPTData
PTData for Keys (top-level pointers, generally).
PersistentPTData< VersionedKey, VersionedKeySet, Data, DataSet >::KeyToIDMap VersionedKeyToIDMap
bool addPts(const VersionedKey &vk, const Data &element) override
const KeySet & getRevPts(const Data &data) override
Get reverse points-to set of a datum.
void clearPts(const Key &k, const Data &element) override
Clears element from the points-to set of var.
void remapAllPts() override
Remaps all points-to sets to use the current mapping.
PersistentVersionedPTData(PersistentPointsToCache< DataSet > &cache, bool reversePT=true, PTDataTy ty=PTDataTy::PersVersioned)
bool unionPts(const VersionedKey &dstVar, const Key &srcVar) override
BasePTData::PTDataTy PTDataTy
PersistentPTData< VersionedKey, VersionedKeySet, Data, DataSet > atPTData
PTData for VersionedKeys (address-taken objects, generally).
void clearPts(const VersionedKey &vk, const Data &element) override
~PersistentVersionedPTData() override=default
void clearFullPts(const VersionedKey &vk) override
bool unionPts(const Key &dstVar, const DataSet &srcDataSet) override
Performs pts(dstVar) = pts(dstVar) U srcDataSet.
void dumpPTData() override
Dump stored keys and points-to sets.
bool unionPts(const VersionedKey &dstVar, const DataSet &srcDataSet) override
VersionedPTData< Key, KeySet, Data, DataSet, VersionedKey, VersionedKeySet > BaseVersionedPTData
const DataSet & getPts(const Key &vk) override
Get points-to set of var.
bool addPts(const Key &k, const Data &element) override
Adds element to the points-to set associated with var.
const VersionedKeySet & getVersionedKeyRevPts(const Data &data) override
Map< DataSet, unsigned > getAllPts(bool liveOnly) const override
PTData< Key, KeySet, Data, DataSet > BasePTData
bool unionPts(const Key &dstVar, const VersionedKey &srcVar) override
bool unionPts(const VersionedKey &dstVar, const VersionedKey &srcVar) override
const DataSet & getPts(const VersionedKey &vk) override
void clear() override
Clears all points-to sets as if nothing is stored.
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