29 assert(version !=
invalidVersion &&
"VersionedFlowSensitive::atKey: trying to use an invalid version!");
30 return std::make_pair(var, version);
42 if (SVFUtil::isa<ObjVar>(it->second)) equivalentObject[it->first] = it->first;
45 assert(!
Options::OPTSVFG() &&
"VFS: -opt-svfg not currently supported with VFS.");
78 double start =
stat->getClk(
true);
119 double end =
stat->getClk(
true);
125 double start =
stat->getClk(
true);
135 std::vector<std::pair<const SVFGNode *, const PointsTo *>> prelabeledNodes;
137 std::vector<bool> isPrelabeled(
svfg->getTotalNodeNum(),
false);
141 isPrelabeled[
n] =
true;
147 const NodeID p = store->getDstNodeID();
148 nPts = &(this->
ander->getPts(
p));
151 prelabeledNodes.push_back(std::make_pair(sn, nPts));
156 std::vector<NodeID> nodesWhichNeedVersions;
163 std::mutex *versionMutexes =
new std::mutex[nodesWhichNeedVersions.size()];
168 std::queue<NodeID> objectQueue;
177 std::mutex objectQueueMutex;
178 std::mutex footprintOwnerMutex;
180 auto meldVersionWorker = [
this, &footprintOwner, &objectQueue,
181 &objectQueueMutex, &footprintOwnerMutex, &versionMutexes,
182 &prelabeledNodes, &isPrelabeled, &nodesWhichNeedVersions]
183 (
const unsigned thread)
189 std::lock_guard<std::mutex> guard(objectQueueMutex);
191 if (objectQueue.empty())
return;
192 o = objectQueue.front();
199 std::vector<const SVFGNode *> osStartingNodes;
200 for (std::pair<const SVFGNode *, const PointsTo *> snPts : prelabeledNodes)
206 if (pts->
test(o)) osStartingNodes.push_back(sn);
210 if (mr->getPointsTo().test(o)) osStartingNodes.push_back(sn);
214 assert(
false &&
"VFS::meldLabel: unexpected prelabeled node!");
218 std::vector<int> partOf;
219 std::vector<const IndirectSVFGEdge *> footprint;
220 unsigned numSCCs = SCC::detectSCCs(
this, this->
svfg, o, osStartingNodes, partOf, footprint);
224 std::lock_guard<std::mutex> guard(footprintOwnerMutex);
226 = footprintOwner.find(footprint);
227 if (canonOwner == footprintOwner.end())
230 footprintOwner[footprint] = o;
248 std::vector<MeldVersion> sccToMeldVersion(numSCCs);
253 std::vector<NodeID> todoList;
261 for (
const SVFGNode *sn : osStartingNodes) reachableNodes.insert(sn->getId());
262 for (
const SVFGEdge *se : footprint)
264 reachableNodes.insert(se->getSrcNode()->getId());
265 reachableNodes.insert(se->getDstNode()->getId());
268 for (
const NodeID n : reachableNodes)
272 if (this->
isStore(n)) storesYieldedMeldVersion[
n].set(bit);
273 else sccToMeldVersion[partOf[
n]].set(bit);
277 todoList.push_back(
n);
283 return partOf[
a] > partOf[
b];
285 std::sort(todoList.begin(), todoList.end(), cmp);
294 std::vector<Set<int>> sccReliance(numSCCs);
296 std::vector<int> storeSCC(numSCCs, -1);
297 for (
size_t i = 0; i < todoList.size(); ++i)
301 const bool nIsStore = this->
isStore(n);
303 int nSCC = partOf[
n];
304 if (nIsStore) storeSCC[nSCC] =
n;
309 const MeldVersion &nMV = nIsStore ? storesYieldedMeldVersion[
n] : sccToMeldVersion[nSCC];
319 int mSCC = partOf[m];
322 sccReliance[nSCC].insert(mSCC);
329 if (!this->
delta(m) && (nSCC != mSCC || nIsStore))
331 sccToMeldVersion[mSCC] |= nMV;
344 Version v = foundVersion == mvv.end() ? mvv[mv] = ++curVersion : foundVersion->second;
345 sccToVersion[
scc] = v;
348 sccToMeldVersion.clear();
352 for (
auto const& nmv : storesYieldedMeldVersion)
358 Version v = foundVersion == mvv.end() ? mvv[mv] = ++curVersion : foundVersion->second;
359 storesYieldedVersion[
n] = v;
362 storesYieldedMeldVersion.clear();
370 if (sccReliance[
scc].empty())
continue;
375 = storeSCC[
scc] != -1 ? storesYieldedVersion[storeSCC[
scc]] : sccToVersion[
scc];
377 std::vector<Version> &reliantVersions = osVersionReliance[version];
378 for (
const int reliantSCC : sccReliance[
scc])
380 const Version reliantVersion = sccToVersion[reliantSCC];
381 if (version != reliantVersion)
384 reliantVersions.push_back(reliantVersion);
393 for (
size_t i = 0; i < nodesWhichNeedVersions.size(); ++i)
395 const NodeID n = nodesWhichNeedVersions[i];
396 std::mutex &mutex = versionMutexes[i];
398 const int scc = partOf[
n];
399 if (
scc == -1)
continue;
401 std::lock_guard<std::mutex> guard(mutex);
407 if (this->
isStore(n) || this->
isLoad(n)) osStmtReliance[c].set(
n);
413 if (yIt != storesYieldedVersion.end()) this->
setYield(n, o, yIt->second);
419 std::vector<std::thread> workers;
421 for (std::thread &worker : workers) worker.join();
423 delete[] versionMutexes;
425 double end =
stat->getClk(
true);
437 assert(l <
deltaMap.size() &&
"VFS::delta: deltaMap is missing SVFG nodes!");
443 assert(l <
deltaSourceMap.size() &&
"VFS::delta: deltaSourceMap is missing SVFG nodes!");
460 assert(l <
isStoreMap.size() &&
"VFS::isStore: isStoreMap is missing SVFG nodes!");
466 assert(l <
isLoadMap.size() &&
"VFS::isLoad: isLoadMap is missing SVFG nodes!");
479 const NodeID l = it->first;
486 bool isDelta =
false;
491 ander->getCallGraph()->getIndCallSitesInvokingCallee(fn, callsites);
492 isDelta = !callsites.empty();
497 for (
const CallICFGNode *cbn : callsites) deltaCBNs.insert(cbn);
502 isDelta = cbn->isIndirectCall();
503 if (isDelta) deltaCBNs.insert(cbn);
513 const NodeID l = it->first;
518 if (deltaCBNs.find(cbn) != deltaCBNs.end())
deltaSourceMap[l] =
true;
534 std::vector<SVFGEdge *> toDeleteFromIn;
540 for (
SVFGEdge *e : toDeleteFromIn)
svfg->removeSVFGEdge(e);
551 double start =
stat->getClk();
554 for (
Version r : reliantVersions)
559 double end =
stat->getClk();
565 double start = time ?
stat->getClk() : 0.0;
569 if (
vPtD->unionPts(dstVar, srcVar))
577 dvp =
svfg->addDummyVersionPropSVFGNode(o, vp);
580 else dvp = dvpIt->second;
582 assert(dvp !=
nullptr &&
"VFS::propagateVersion: propagation dummy node not found?");
589 double end = time ?
stat->getClk() : 0.0;
612 SVFGNode *dstNode = e->getDstNode();
613 NodeID src = e->getSrcNode()->getId();
625 assert(ie !=
nullptr &&
"VFS::updateConnectedNodes: given direct edge?");
627 assert(
delta(dst) &&
"VFS::updateConnectedNodes: new edges should be to delta nodes!");
628 assert(
deltaSource(src) &&
"VFS::updateConnectedNodes: new indirect edges should be from delta source nodes!");
632 for (
const NodeID o : ept)
640 if (std::find(versionsRelyingOnSrcY.begin(), versionsRelyingOnSrcY.end(), dstC) == versionsRelyingOnSrcY.end())
642 versionsRelyingOnSrcY.push_back(dstC);
652 double start =
stat->getClk();
654 bool changed =
false;
667 if (
pag->isConstantObj(o))
continue;
691 double end =
stat->getClk();
701 if (ppt.
empty())
return false;
709 double start =
stat->getClk();
710 bool changed =
false;
721 if (
pag->isConstantObj(o))
continue;
727 changedObjects.
set(o);
733 double end =
stat->getClk();
736 double updateStart =
stat->getClk();
745 for (
const ObjToVersionMap::value_type &oc :
consume[l])
747 const NodeID o = oc.first;
751 if (isSU && o == singleton)
continue;
757 changedObjects.
set(o);
761 double updateEnd =
stat->getClk();
766 if (!changedObjects.
empty())
768 for (
const NodeID o : changedObjects)
785 std::vector<std::pair<unsigned, unsigned>> keys;
790 unsigned v = pit->first;
793 keys.push_back(std::make_pair(v, occ));
797 std::make_shared<std::vector<NodeID>>(
812 const ObjToVersionMap::const_iterator foundVersion = ovm.find(op);
813 return foundVersion == ovm.end() ?
invalidVersion : foundVersion->second;
863 for (
const Map<
Version, std::vector<Version>>::value_type& vrv : ovrv.second)
866 SVFUtil::outs() <<
" Version " << v <<
" is a reliance for: ";
893 SVFUtil::outs() <<
" Version " << v <<
" is a reliance for statements: ";
895 const NodeBS &ss = vss.second;
918 const NodeID loc = it->first;
919 bool locPrinted =
false;
925 if (lvm->at(loc).empty())
continue;
935 for (
const ObjToVersionMap::value_type &ov : lvm->at(loc))
937 const NodeID o = ov.first;
939 SVFUtil::outs() << (first ?
"" :
", ") <<
"<" << o <<
", " << v <<
">";
972 if(!filename.empty())
974 SVFUtil::outs() <<
"Loading versioned pointer analysis results from '" << filename <<
"'...";
976 std::ifstream F(filename.c_str());
1007 if(!filename.empty())
1010 if(!filename.empty())
1021 SVFUtil::outs() <<
"Storing Versioned Analysis Result to '" << filename <<
"'...";
1022 std::error_code err;
1023 std::fstream f(filename.c_str(), std::ios_base::app);
1037 for (
const VersionedFlowSensitive::ObjToVersionMap::value_type &ov : lov)
1039 const NodeID o = ov.first;
1041 if (
vPtD->getPts(
atKey(o, v)).empty())
continue;
1043 f <<
"[ " <<o <<
" " <<v<<
" ]"<<
" -> { ";
1061 f <<
"---VERSIONED---\n";
1074 std::string delimiter1 =
" -> { ";
1075 std::string delimiter2 =
" }";
1080 if (line ==
"---VERSIONED---")
break;
1081 std::string pair = line.substr(line.find(
"[ ")+1, line.find(
" ]"));
1084 std::istringstream ss(pair);
1087 ss>> nodeID >> nodeVersion;
1091 size_t pos = line.find(delimiter1);
1092 if (pos == std::string::npos)
break;
1093 if (line.back() !=
'}')
break;
1094 pos = pos + delimiter1.length();
1095 size_t len = line.length() - pos - delimiter2.length();
1096 std::string objs = line.substr(pos, len);
1100 std::istringstream pt(objs);
1110 vPtD->unionPts(keyPair, dstPts);
1117 const std::vector<const SVFGNode *> &startingNodes,
1118 std::vector<int> &partOf,
1119 std::vector<const IndirectSVFGEdge *> &footprint)
1121 partOf.resize(
svfg->getTotalNodeNum());
1122 std::fill(partOf.begin(), partOf.end(), -1);
1125 std::vector<NodeData> nodeData(
svfg->getTotalNodeNum(), { -1, -1, false});
1126 std::stack<const SVFGNode *>
stack;
1131 for (
const SVFGNode *v : startingNodes)
1133 if (nodeData[v->getId()].index == -1)
1135 visit(vfs,
object, partOf, footprint, nodeData,
stack,
index, currentSCC, v);
1140 std::sort(footprint.begin(), footprint.end());
1147 std::vector<int> &partOf,
1148 std::vector<const IndirectSVFGEdge *> &footprint,
1149 std::vector<NodeData> &nodeData,
1150 std::stack<const SVFGNode *> &
stack,
1157 nodeData[vId].index =
index;
1158 nodeData[vId].lowlink =
index;
1162 nodeData[vId].onStack =
true;
1177 footprint.push_back(ie);
1184 if (nodeData[wId].
index == -1)
1186 visit(vfs,
object, partOf, footprint, nodeData,
stack,
index, currentSCC, w);
1187 nodeData[vId].lowlink = std::min(nodeData[vId].lowlink, nodeData[wId].lowlink);
1189 else if (nodeData[wId].onStack)
1191 nodeData[vId].lowlink = std::min(nodeData[vId].lowlink, nodeData[wId].
index);
1195 if (nodeData[vId].lowlink == nodeData[vId].
index)
1203 nodeData[wId].onStack =
false;
1204 partOf[wId] = currentSCC;
VersionedPTDataTy * getVersionedPTDataTy() const
virtual void writeToFile(const std::string &filename)
Interface for analysis result storage on filesystem.
virtual void writeObjVarToFile(const std::string &filename)
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)
Set< const CallICFGNode * > CallInstSet
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.
FlowSensitive(SVFIR *_pag, PTATY type=PTATY::FSSPARSE_WPA)
Constructor.
double updateTime
time of strong/weak updates.
NodeType * getDstNode() const
IDToNodeMapTy::const_iterator const_iterator
IDToNodeMapTy::iterator iterator
const GEdgeSetTy & getOutEdges() const
const GEdgeSetTy & getInEdges() const
const NodeBS & getPointsTo() const
const ValVar * getDstNode() const
const NodeBS & getPointsTo() const
Return points-to of the MR.
static std::vector< NodeID > getReverseNodeMapping(const std::vector< NodeID > &nodeMapping)
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="", bool printStat=true)
static Option< bool > OPTSVFG
static const Option< bool > PredictPtOcc
static const Option< u32_t > VersioningThreads
Number of threads for the versioning phase.
bool isFieldInsensitive(NodeID id) const
bool print_stat
User input flags.
PTAStat * stat
Statistics.
virtual const NodeBS & getAllFieldsObjVars(NodeID id)
bool empty() const
Returns true if set is empty.
std::shared_ptr< std::vector< NodeID > > MappingPtr
static void setCurrentBestNodeMapping(MappingPtr newCurrentBestNodeMapping, MappingPtr newCurrentBestReverseNodeMapping)
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.
virtual bool isPointer() const
Check if this variable represents a pointer.
bool test(unsigned Idx) const
NodeID getSrcNodeID() const
NodeID getDstNodeID() const
const ValVar * getSrcNode() const
virtual const ICFGNode * getICFGNode() const
Return corresponding ICFG node.
VFGNodeIDToNodeMapTy::const_iterator const_iterator
VFGNodeIDToNodeMapTy::iterator iterator
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.
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.
CoreBitVector MeldVersion
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.
VersionedFlowSensitive(SVFIR *_pag, PTATY type=PTATY::VFS_WPA)
Constructor.
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)
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.
std::unique_ptr< SCC > scc
SCC.
virtual void pushIntoWorklist(NodeID id)
virtual void propagate(GNODE *v)
void setGraph(GraphType g)
LLVM_NODISCARD bool isa(const Y &Val)
std::ostream & outs()
Overwrite llvm::outs().
LLVM_NODISCARD std::enable_if_t<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type > dyn_cast(const Y &Val)
std::pair< NodeID, Version > VersionedVar
PTATY
Pointer analysis type list.
std::unordered_set< Key, Hash, KeyEqual, Allocator > Set
StoreVFGNode StoreSVFGNode
std::unordered_map< Key, Value, Hash, KeyEqual, Allocator > Map