26 assert(version !=
invalidVersion &&
"VersionedFlowSensitive::atKey: trying to use an invalid version!");
27 return std::make_pair(var, version);
39 if (SVFUtil::isa<ObjVar>(it->second))
equivalentObject[it->first] = it->first;
42 assert(!
Options::OPTSVFG() &&
"VFS: -opt-svfg not currently supported with VFS.");
81 if (
const StoreSVFGNode *stn = SVFUtil::dyn_cast<StoreSVFGNode>(ln))
85 NodeID p = stn->getPAGDstNodeID();
101 const MRSVFGNode *mr = SVFUtil::dyn_cast<MRSVFGNode>(ln);
132 std::vector<std::pair<const SVFGNode *, const PointsTo *>> prelabeledNodes;
138 isPrelabeled[
n] =
true;
142 if (
const StoreSVFGNode *store = SVFUtil::dyn_cast<StoreSVFGNode>(sn))
144 const NodeID p = store->getPAGDstNodeID();
148 prelabeledNodes.push_back(std::make_pair(sn, nPts));
153 std::vector<NodeID> nodesWhichNeedVersions;
160 std::mutex *versionMutexes =
new std::mutex[nodesWhichNeedVersions.size()];
165 std::queue<NodeID> objectQueue;
174 std::mutex objectQueueMutex;
175 std::mutex footprintOwnerMutex;
177 auto meldVersionWorker = [
this, &footprintOwner, &objectQueue,
178 &objectQueueMutex, &footprintOwnerMutex, &versionMutexes,
179 &prelabeledNodes, &isPrelabeled, &nodesWhichNeedVersions]
180 (
const unsigned thread)
186 std::lock_guard<std::mutex> guard(objectQueueMutex);
188 if (objectQueue.empty())
return;
189 o = objectQueue.front();
196 std::vector<const SVFGNode *> osStartingNodes;
197 for (std::pair<const SVFGNode *, const PointsTo *> snPts : prelabeledNodes)
203 if (pts->
test(o)) osStartingNodes.push_back(sn);
205 else if (
const MRSVFGNode *mr = SVFUtil::dyn_cast<MRSVFGNode>(sn))
207 if (mr->getPointsTo().test(o)) osStartingNodes.push_back(sn);
211 assert(
false &&
"VFS::meldLabel: unexpected prelabeled node!");
215 std::vector<int> partOf;
216 std::vector<const IndirectSVFGEdge *> footprint;
217 unsigned numSCCs =
SCC::detectSCCs(
this, this->
svfg, o, osStartingNodes, partOf, footprint);
221 std::lock_guard<std::mutex> guard(footprintOwnerMutex);
223 = footprintOwner.find(footprint);
224 if (canonOwner == footprintOwner.end())
227 footprintOwner[footprint] = o;
245 std::vector<MeldVersion> sccToMeldVersion(numSCCs);
250 std::vector<NodeID> todoList;
258 for (
const SVFGNode *sn : osStartingNodes) reachableNodes.insert(sn->getId());
259 for (
const SVFGEdge *se : footprint)
261 reachableNodes.insert(se->getSrcNode()->getId());
262 reachableNodes.insert(se->getDstNode()->getId());
265 for (
const NodeID n : reachableNodes)
269 if (this->
isStore(n)) storesYieldedMeldVersion[
n].set(bit);
270 else sccToMeldVersion[partOf[
n]].set(bit);
274 todoList.push_back(
n);
280 return partOf[
a] > partOf[
b];
282 std::sort(todoList.begin(), todoList.end(), cmp);
291 std::vector<Set<int>> sccReliance(numSCCs);
293 std::vector<int> storeSCC(numSCCs, -1);
294 for (
size_t i = 0; i < todoList.size(); ++i)
298 const bool nIsStore = this->
isStore(n);
300 int nSCC = partOf[
n];
301 if (nIsStore) storeSCC[nSCC] =
n;
306 const MeldVersion &nMV = nIsStore ? storesYieldedMeldVersion[
n] : sccToMeldVersion[nSCC];
316 int mSCC = partOf[m];
319 sccReliance[nSCC].insert(mSCC);
326 if (!this->
delta(m) && (nSCC != mSCC || nIsStore))
328 sccToMeldVersion[mSCC] |= nMV;
341 Version v = foundVersion == mvv.
end() ? mvv[mv] = ++curVersion : foundVersion->second;
342 sccToVersion[
scc] = v;
345 sccToMeldVersion.clear();
349 for (
auto const& nmv : storesYieldedMeldVersion)
355 Version v = foundVersion == mvv.
end() ? mvv[mv] = ++curVersion : foundVersion->second;
356 storesYieldedVersion[
n] = v;
359 storesYieldedMeldVersion.clear();
367 if (sccReliance[
scc].empty())
continue;
372 = storeSCC[
scc] != -1 ? storesYieldedVersion[storeSCC[
scc]] : sccToVersion[
scc];
374 std::vector<Version> &reliantVersions = osVersionReliance[version];
375 for (
const int reliantSCC : sccReliance[
scc])
377 const Version reliantVersion = sccToVersion[reliantSCC];
378 if (version != reliantVersion)
381 reliantVersions.push_back(reliantVersion);
390 for (
size_t i = 0; i < nodesWhichNeedVersions.size(); ++i)
392 const NodeID n = nodesWhichNeedVersions[i];
393 std::mutex &mutex = versionMutexes[i];
395 const int scc = partOf[
n];
396 if (
scc == -1)
continue;
398 std::lock_guard<std::mutex> guard(mutex);
404 if (this->
isStore(n) || this->
isLoad(n)) osStmtReliance[c].set(
n);
410 if (yIt != storesYieldedVersion.end()) this->
setYield(n, o, yIt->second);
416 std::vector<std::thread> workers;
418 for (std::thread &worker : workers) worker.join();
420 delete[] versionMutexes;
434 assert(l <
deltaMap.size() &&
"VFS::delta: deltaMap is missing SVFG nodes!");
440 assert(l <
deltaSourceMap.size() &&
"VFS::delta: deltaSourceMap is missing SVFG nodes!");
450 if (SVFUtil::isa<StoreSVFGNode>(it->second))
isStoreMap[it->first] =
true;
451 else if (SVFUtil::isa<LoadSVFGNode>(it->second))
isLoadMap[it->first] =
true;
457 assert(l <
isStoreMap.size() &&
"VFS::isStore: isStoreMap is missing SVFG nodes!");
463 assert(l <
isLoadMap.size() &&
"VFS::isLoad: isLoadMap is missing SVFG nodes!");
476 const NodeID l = it->first;
483 bool isDelta =
false;
489 isDelta = !callsites.empty();
494 for (
const CallICFGNode *cbn : callsites) deltaCBNs.insert(cbn);
499 isDelta = cbn->isIndirectCall();
500 if (isDelta) deltaCBNs.insert(cbn);
510 const NodeID l = it->first;
515 if (deltaCBNs.find(cbn) != deltaCBNs.end())
deltaSourceMap[l] =
true;
531 std::vector<SVFGEdge *> toDeleteFromIn;
534 if (SVFUtil::isa<IndirectSVFGEdge>(e)) toDeleteFromIn.push_back(e);
551 for (
Version r : reliantVersions)
577 else dvp = dvpIt->second;
579 assert(dvp !=
nullptr &&
"VFS::propagateVersion: propagation dummy node not found?");
609 SVFGNode *dstNode = e->getDstNode();
613 if (SVFUtil::isa<PHISVFGNode>(dstNode)
614 || SVFUtil::isa<FormalParmSVFGNode>(dstNode)
615 || SVFUtil::isa<ActualRetSVFGNode>(dstNode))
622 assert(ie !=
nullptr &&
"VFS::updateConnectedNodes: given direct edge?");
624 assert(
delta(dst) &&
"VFS::updateConnectedNodes: new edges should be to delta nodes!");
625 assert(
deltaSource(src) &&
"VFS::updateConnectedNodes: new indirect edges should be from delta source nodes!");
629 for (
const NodeID o : ept)
637 if (std::find(versionsRelyingOnSrcY.begin(), versionsRelyingOnSrcY.end(), dstC) == versionsRelyingOnSrcY.end())
639 versionsRelyingOnSrcY.push_back(dstC);
651 bool changed =
false;
698 if (ppt.
empty())
return false;
707 bool changed =
false;
724 changedObjects.
set(o);
742 for (
const ObjToVersionMap::value_type &oc :
consume[l])
744 const NodeID o = oc.first;
748 if (isSU && o == singleton)
continue;
754 changedObjects.
set(o);
763 if (!changedObjects.
empty())
765 for (
const NodeID o : changedObjects)
782 std::vector<std::pair<unsigned, unsigned>> keys;
786 unsigned v = pit->first;
789 keys.push_back(std::make_pair(v, occ));
806 const ObjToVersionMap::const_iterator foundVersion = ovm.find(op);
807 return foundVersion == ovm.end() ?
invalidVersion : foundVersion->second;
857 for (
const Map<
Version, std::vector<Version>>::value_type& vrv : ovrv.second)
860 SVFUtil::outs() <<
" Version " << v <<
" is a reliance for: ";
887 SVFUtil::outs() <<
" Version " << v <<
" is a reliance for statements: ";
889 const NodeBS &ss = vss.second;
912 const NodeID loc = it->first;
913 bool locPrinted =
false;
919 if (lvm->at(loc).empty())
continue;
929 for (
const ObjToVersionMap::value_type &ov : lvm->at(loc))
931 const NodeID o = ov.first;
933 SVFUtil::outs() << (first ?
"" :
", ") <<
"<" << o <<
", " << v <<
">";
966 if(!filename.empty())
968 SVFUtil::outs() <<
"Loading versioned pointer analysis results from '" << filename <<
"'...";
970 std::ifstream
F(filename.c_str());
1001 if(!filename.empty())
1004 if(!filename.empty())
1015 SVFUtil::outs() <<
"Storing Versioned Analysis Result to '" << filename <<
"'...";
1016 std::error_code err;
1017 std::fstream f(filename.c_str(), std::ios_base::app);
1031 for (
const VersionedFlowSensitive::ObjToVersionMap::value_type &ov : lov)
1033 const NodeID o = ov.first;
1037 f <<
"[ " <<o <<
" " <<v<<
" ]"<<
" -> { ";
1055 f <<
"---VERSIONED---\n";
1074 if (line ==
"---VERSIONED---")
break;
1075 std::string pair = line.substr(line.find(
"[ ")+1, line.find(
" ]"));
1078 std::istringstream ss(pair);
1081 ss>> nodeID >> nodeVersion;
1085 size_t pos = line.find(delimiter1);
1086 if (pos == std::string::npos)
break;
1087 if (line.back() !=
'}')
break;
1088 pos = pos + delimiter1.length();
1089 size_t len = line.length() - pos - delimiter2.length();
1094 std::istringstream pt(objs);
1111 const std::vector<const SVFGNode *> &startingNodes,
1112 std::vector<int> &partOf,
1113 std::vector<const IndirectSVFGEdge *> &footprint)
1116 std::fill(partOf.begin(), partOf.end(), -1);
1120 std::stack<const SVFGNode *> stack;
1125 for (
const SVFGNode *v : startingNodes)
1127 if (nodeData[v->getId()].index == -1)
1129 visit(vfs,
object, partOf, footprint, nodeData, stack,
index, currentSCC, v);
1134 std::sort(footprint.begin(), footprint.end());
1141 std::vector<int> &partOf,
1142 std::vector<const IndirectSVFGEdge *> &footprint,
1143 std::vector<NodeData> &nodeData,
1144 std::stack<const SVFGNode *> &stack,
1151 nodeData[vId].index =
index;
1152 nodeData[vId].lowlink =
index;
1156 nodeData[vId].onStack =
true;
1171 footprint.push_back(ie);
1178 if (nodeData[wId].
index == -1)
1180 visit(vfs,
object, partOf, footprint, nodeData, stack,
index, currentSCC, w);
1181 nodeData[vId].lowlink = std::min(nodeData[vId].lowlink, nodeData[wId].lowlink);
1183 else if (nodeData[wId].onStack)
1185 nodeData[vId].lowlink = std::min(nodeData[vId].lowlink, nodeData[wId].
index);
1189 if (nodeData[vId].lowlink == nodeData[vId].
index)
1197 nodeData[wId].onStack =
false;
1198 partOf[wId] = currentSCC;
virtual const PointsTo & getPts(NodeID id)
Operation of points-to set.
virtual void writeToFile(const std::string &filename)
Interface for analysis result storage on filesystem.
virtual void writeObjVarToFile(const std::string &filename)
VersionedPTDataTy * getVersionedPTDataTy() const
virtual void readAndSetObjFieldSensitivity(std::ifstream &f, const std::string &delimiterStr)
const PointsTo & getPts(NodeID id) override
virtual void readPtsResultFromFile(std::ifstream &f)
virtual void readGepObjVarMapFromFile(std::ifstream &f)
const_iterator end(void) const
bool push(const Data &data)
virtual void solveConstraints()
bool isStrongUpdate(const SVFGNode *node, NodeID &singleton)
Return TRUE if this is a strong update STORE statement.
SVFG::SVFGEdgeSetTy SVFGEdgeSetTy
double storeTime
time of store edges
void finalize() override
Finalize analysis.
bool processSVFGNode(SVFGNode *node)
double loadTime
time of load edges
bool updateCallGraph(const CallSiteToFunPtrMap &callsites) override
Update call graph.
void initialize() override
Initialize analysis.
std::vector< std::pair< hclust_fast_methods, std::vector< NodeID > > > candidateMappings
Save candidate mappings for evaluation's sake.
double updateTime
time of strong/weak updates.
NodeType * getDstNode() const
iterator begin()
Iterators.
IDToNodeMapTy::const_iterator const_iterator
u32_t getTotalNodeNum() const
Get total number of node/edge.
IDToNodeMapTy::iterator iterator
Node Iterators.
const GEdgeSetTy & getOutEdges() const
const GEdgeSetTy & getInEdges() const
const NodeBS & getPointsTo() const
const NodeBS & getPointsTo() const
Return points-to of the MR.
static std::vector< NodeID > cluster(BVDataPTAImpl *pta, const std::vector< std::pair< NodeID, unsigned >> keys, std::vector< std::pair< hclust_fast_methods, std::vector< NodeID >>> &candidates, std::string evalSubtitle="")
static std::vector< NodeID > getReverseNodeMapping(const std::vector< NodeID > &nodeMapping)
static Option< bool > OPTSVFG
static const Option< bool > PredictPtOcc
static const Option< u32_t > VersioningThreads
Number of threads for the versioning phase.
Set< const CallICFGNode * > CallInstSet
void getIndCallSitesInvokingCallee(const SVFFunction *callee, PTACallGraphEdge::CallInstSet &csSet)
PTATY
Pointer analysis type list.
bool isFieldInsensitive(NodeID id) const
virtual const NodeBS & getAllFieldsObjVars(NodeID id)
PTAStat * stat
Statistics.
PTACallGraph * getCallGraph() const
Return call graph.
bool empty() const
Returns true if set is empty.
std::shared_ptr< std::vector< NodeID > > MappingPtr
static void setCurrentBestNodeMapping(MappingPtr newCurrentBestNodeMapping, MappingPtr newCurrentBestReverseNodeMapping)
u32_t count() const
Returns number of elements.
void set(u32_t n)
Inserts n in the set.
bool test(u32_t n) const
Returns true if n is in this set.
NodeID getId() const
Get ID.
SVFGNode * getSVFGNode(NodeID id) const
Get a SVFG node.
const DummyVersionPropSVFGNode * addDummyVersionPropSVFGNode(const NodeID object, const NodeID version)
void removeSVFGEdge(SVFGEdge *edge)
Remove a SVFG edge.
const CallICFGNode * isCallSiteRetSVFGNode(const SVFGNode *node) const
Whether a node is callsite return SVFGNode.
const SVFFunction * isFunEntrySVFGNode(const SVFGNode *node) const
Whether a node is function entry SVFGNode.
const CallSiteToFunPtrMap & getIndirectCallsites() const
Add/get indirect callsites.
const MemObj * getObject(NodeID id) const
bool isConstantObj(NodeID id) const
static double getClk(bool mark=false)
virtual bool isPointer() const
Whether it is a pointer.
bool test(unsigned Idx) const
NodeID getPAGDstNodeID() const
NodeID getPAGSrcNodeID() const
PAGNode * getPAGSrcNode() const
PAGNode * getPAGDstNode() const
virtual const ICFGNode * getICFGNode() const
Return corresponding ICFG node.
static void visit(VersionedFlowSensitive *vfs, const NodeID object, std::vector< int > &partOf, std::vector< const IndirectSVFGEdge * > &footprint, std::vector< NodeData > &nodeData, std::stack< const SVFGNode * > &stack, int &index, int ¤tSCC, const SVFGNode *v)
Called by detectSCCs then called recursively.
static unsigned detectSCCs(VersionedFlowSensitive *vfs, const SVFG *svfg, const NodeID object, const std::vector< const SVFGNode * > &startingNodes, std::vector< int > &partOf, std::vector< const IndirectSVFGEdge * > &footprint)
Version getYield(const NodeID l, const NodeID o) const
Returns the yielded version of o at l. If no such version exists, returns invalidVersion.
void dumpLocVersionMaps(void) const
Dumps maps consume and yield.
BVDataPTAImpl::VersionedPTDataTy * vPtD
Points-to DS for working with versions.
std::vector< bool > deltaMap
LocVersionMap yield
Actual yield map. Yield analogue to consume.
std::vector< bool > isStoreMap
isStoreMap[l] means SVFG node l is a store node.
virtual void updateConnectedNodes(const SVFGEdgeSetTy &newEdges) override
Update nodes connected during updating call graph.
virtual bool processLoad(const LoadSVFGNode *load) override
static bool meld(MeldVersion &mv1, const MeldVersion &mv2)
Melds v2 into v1 (in place), returns whether a change occurred.
VersionRelianceMap versionReliance
o -> (version -> versions which rely on it).
u32_t numPrelabelVersions
Number of versions created during prelabeling.
void removeAllIndirectSVFGEdges(void)
Removes all indirect edges in the SVFG.
Map< NodeID, NodeID > equivalentObject
void readVersionedAnalysisResultFromFile(std::ifstream &F)
virtual void buildDeltaMaps(void)
Fills in deltaMap and deltaSourceMap for the SVFG.
NodeBS & getStmtReliance(const NodeID o, const Version v)
Returns the statements which rely on o:v.
static const Version invalidVersion
If this version appears, there has been an error.
virtual bool deltaSource(const NodeID l) const
double meldLabelingTime
Time to meld label SVFG.
static VersionedFlowSensitive * vfspta
static VersionedVar atKey(NodeID, Version)
Return key into vPtD for address-taken var of a specific version.
Version getVersion(const NodeID l, const NodeID o, const LocVersionMap &lvm) const
Shared code for getConsume and getYield. They wrap this function.
std::vector< bool > isLoadMap
isLoadMap[l] means SVFG node l is a load node.
static void dumpMeldVersion(MeldVersion &v)
Dumps a MeldVersion to stdout.
double prelabelingTime
Time to prelabel SVFG.
void propagateVersion(NodeID o, Version v)
void prelabel(void)
Prelabel the SVFG: set y(o) for stores and c(o) for delta nodes to a new version.
virtual void initialize() override
Initialize analysis.
virtual void processNode(NodeID n) override
Handle various constraints.
virtual void buildIsStoreLoadMaps(void)
Fills in isStoreMap and isLoadMap.
virtual bool isLoad(const NodeID l) const
Returns true if l is a load node.
void dumpReliances(void) const
Dumps versionReliance and stmtReliance.
virtual bool delta(const NodeID l) const
std::vector< ObjToVersionMap > LocVersionMap
virtual bool processStore(const StoreSVFGNode *store) override
Set< NodeID > prelabeledObjects
void setConsume(const NodeID l, const NodeID o, const Version v)
Sets the consumed version of o at l to v.
virtual bool isStore(const NodeID l) const
Returns true if l is a store node.
friend class VersionedFlowSensitiveStat
void meldLabel(void)
Meld label the prelabeled SVFG.
void writeVersionedAnalysisResultToFile(const std::string &filename)
VersionedFlowSensitive(SVFIR *_pag, PTATY type=VFS_WPA)
Constructor.
void setYield(const NodeID l, const NodeID o, const Version v)
Sets the yielded version of o at l to v.
void solveAndwritePtsToFile(const std::string &filename) override
virtual void finalize() override
Finalize analysis.
void setVersion(const NodeID l, const NodeID o, const Version v, LocVersionMap &lvm)
Shared code for setConsume and setYield. They wrap this function.
FIFOWorkList< NodeID > vWorklist
std::vector< Version > & getReliantVersions(const NodeID o, const Version v)
Returns the versions of o which rely on o:v.
void readPtsFromFile(const std::string &filename) override
virtual void cluster(void) override
Override since we want to assign different weights based on versioning.
std::vector< bool > deltaSourceMap
Map< NodeID, Map< Version, NodeBS > > stmtReliance
o x version -> statement nodes which rely on that o/version.
VarToPropNodeMap versionedVarToPropNode
double versionPropTime
Time to propagate versions to versions which rely on them.
Version getConsume(const NodeID l, const NodeID o) const
Returns the consumed version of o at l. If no such version exists, returns invalidVersion.
Map< NodeID, Version > ObjToVersionMap
u32_t numPrelabeledNodes
Additional statistics.
virtual bool unionPts(const VersionedKey &dstVar, const VersionedKey &srcVar)=0
virtual const DataSet & getPts(const VersionedKey &vk)=0
std::unique_ptr< SCC > scc
SCC.
virtual void pushIntoWorklist(NodeID id)
virtual void propagate(GNODE *v)
void setGraph(GraphType g)
std::ostream & outs()
Overwrite llvm::outs()
std::pair< NodeID, Version > VersionedVar
std::unordered_map< Key, Value, Hash, KeyEqual, Allocator > Map
std::unordered_set< Key, Hash, KeyEqual, Allocator > Set