38 using namespace SVFUtil;
52 assert(!
Options::ClusterAnder() &&
"FlowSensitive::initialize: clustering auxiliary Andersen's unsupported.");
57 &&
"FS::init: plain-mapping and cluster-fs are mutually exclusive.");
72 svfg = memSSA.buildPTROnlySVFG(ander);
81 double start = stat->getClk(
true);
89 if(0 == numOfIteration % OnTheFlyIterBudgetForStat)
97 while (updateCallGraph(getIndirectCallsites()));
104 double end = stat->getClk(
true);
116 if(!filename.empty())
117 writeObjVarToFile(filename);
119 if(!filename.empty())
120 writeToFile(filename);
154 if(!filename.empty())
155 this->readFromFile(filename);
166 svfg->dump(
"fs_solved",
true);
169 while (nodeStack.empty() ==
false)
171 NodeID rep = nodeStack.top();
173 const NodeBS& subNodes = getSCCDetector()->subNodes(rep);
174 if (subNodes.
count() > maxSCCSize)
175 maxSCCSize = subNodes.
count();
176 if (subNodes.
count() > 1)
178 numOfNodesInSCC += subNodes.
count();
187 const PTDataTy *ptd = getPTDataTy();
211 double start = stat->getClk();
213 double end = stat->getClk();
223 SVFGNode* node = svfg->getSVFGNode(nodeId);
224 if (processSVFGNode(node))
227 clearAllDFOutVarFlag(node);
235 double start = stat->getClk();
236 bool changed =
false;
237 if (
AddrSVFGNode* addr = SVFUtil::dyn_cast<AddrSVFGNode>(node))
239 numOfProcessedAddr++;
240 if (processAddr(addr))
245 numOfProcessedCopy++;
246 if (processCopy(
copy))
249 else if (
GepSVFGNode* gep = SVFUtil::dyn_cast<GepSVFGNode>(node))
255 else if (
LoadSVFGNode* load = SVFUtil::dyn_cast<LoadSVFGNode>(node))
257 numOfProcessedLoad++;
258 if(processLoad(load))
261 else if (
StoreSVFGNode* store = SVFUtil::dyn_cast<StoreSVFGNode>(node))
263 numOfProcessedStore++;
264 if (processStore(store))
267 else if (
PHISVFGNode* phi = SVFUtil::dyn_cast<PHISVFGNode>(node))
277 numOfProcessedMSSANode++;
286 else if (SVFUtil::isa<CmpVFGNode, BinaryOPVFGNode>(node) ||
287 SVFUtil::dyn_cast<UnaryOPVFGNode>(node))
292 assert(
false &&
"unexpected kind of SVFG nodes");
295 double end = stat->getClk();
311 double start = stat->getClk();
312 bool changed =
false;
314 if (
DirectSVFGEdge* dirEdge = SVFUtil::dyn_cast<DirectSVFGEdge>(edge))
315 changed = propAlongDirectEdge(dirEdge);
316 else if (
IndirectSVFGEdge* indEdge = SVFUtil::dyn_cast<IndirectSVFGEdge>(edge))
317 changed = propAlongIndirectEdge(indEdge);
319 assert(
false &&
"new kind of svfg edge?");
321 double end = stat->getClk();
331 double start = stat->getClk();
332 bool changed =
false;
339 changed = propagateFromAPToFP(ap, dst);
341 changed = propagateFromFRToAR(fp, dst);
351 double end = stat->getClk();
363 assert(fp &&
"expecting a formal param node");
367 bool changed = unionPts(pagDst, srcCPts);
379 assert(ar &&
"expecting an actual return node");
383 bool changed = unionPts(pagDst, srcCPts);
393 double start = stat->getClk();
398 bool changed =
false;
407 if (propVarPtsFromSrcToDst(ptd, src, dst))
410 if (isFieldInsensitive(ptd))
413 const NodeBS& allFields = getAllFieldsObjVars(ptd);
415 fieldIt != fieldEit; ++fieldIt)
417 if (propVarPtsFromSrcToDst(*fieldIt, src, dst))
423 double end = stat->getClk();
433 bool changed =
false;
434 if (SVFUtil::isa<StoreSVFGNode>(src))
436 if (updateInFromOut(src, var, dst, var))
441 if (updateInFromIn(src, var, dst, var))
452 double start = stat->getClk();
456 if (isFieldInsensitive(srcID))
457 srcID = getFIObjVar(srcID);
459 double end = stat->getClk();
469 double start = stat->getClk();
470 bool changed = unionPts(
copy->getPAGDstNodeID(),
copy->getPAGSrcNodeID());
471 double end = stat->getClk();
481 double start = stat->getClk();
482 bool changed =
false;
486 NodeID src = it->second->getId();
487 const PointsTo& srcPts = getPts(src);
488 if (unionPts(pagDst, srcPts))
492 double end = stat->getClk();
502 double start = stat->getClk();
503 bool changed =
false;
512 if (isBlkObjOrConstantObj(o))
518 setObjFieldInsensitive(o);
519 tmpDstPts.
set(getFIObjVar(o));
526 if (isBlkObjOrConstantObj(o) || isFieldInsensitive(o))
533 tmpDstPts.
set(fieldSrcPtdNode);
540 double end = stat->getClk();
554 double start = stat->getClk();
555 bool changed =
false;
568 if (pag->isConstantObj(ptd))
571 if (unionPtsFromIn(load, ptd, dstVar))
574 if (isFieldInsensitive(ptd))
578 const NodeBS& allFields = getAllFieldsObjVars(ptd);
580 fieldIt != fieldEit; ++fieldIt)
582 if (unionPtsFromIn(load, *fieldIt, dstVar))
588 double end = stat->getClk();
613 double start = stat->getClk();
614 bool changed =
false;
623 if (pag->isConstantObj(ptd))
631 double end = stat->getClk();
634 double updateStart = stat->getClk();
638 bool isSU = isStrongUpdate(store, singleton);
641 svfgHasSU.set(store->
getId());
642 if (strongUpdateOutFromIn(store, singleton))
647 svfgHasSU.reset(store->
getId());
648 if (weakUpdateOutFromIn(store))
651 double updateEnd = stat->getClk();
663 if (
const StoreSVFGNode* store = SVFUtil::dyn_cast<StoreSVFGNode>(node))
665 const PointsTo& dstCPSet = getPts(store->getPAGDstNodeID());
666 if (dstCPSet.
count() == 1)
673 if (!isHeapMemObj(singleton) && !isArrayMemObj(singleton)
674 && pag->getBaseObj(singleton)->isFieldInsensitive() ==
false
675 && !isLocalVarInRecursiveFun(singleton))
689 double start = stat->getClk();
691 onTheFlyCallGraphSolve(callsites, newEdges);
695 const CallEdgeMap &andersCallEdgeMap = ander->getIndCallMap();
696 for (
typename CallEdgeMap::value_type &csfs : newEdges)
702 typename CallEdgeMap::const_iterator andersFunctionSetIt
703 = andersCallEdgeMap.find(potentialCallSite);
704 if (andersFunctionSetIt == andersCallEdgeMap.end())
706 potentialFunctionSet.clear();
709 const FunctionSet &andersFunctionSet = andersFunctionSetIt->second;
710 for (FunctionSet::iterator potentialFunctionIt = potentialFunctionSet.begin();
711 potentialFunctionIt != potentialFunctionSet.end(); )
713 const SVFFunction *potentialFunction = *potentialFunctionIt;
714 if (andersFunctionSet.find(potentialFunction) == andersFunctionSet.end())
717 potentialFunctionIt = potentialFunctionSet.erase(potentialFunctionIt);
722 ++potentialFunctionIt;
728 connectCallerAndCallee(newEdges, svfgEdges);
730 updateConnectedNodes(svfgEdges);
732 double end = stat->getClk();
734 return (!newEdges.empty());
742 CallEdgeMap::const_iterator iter = newEdges.begin();
743 CallEdgeMap::const_iterator eiter = newEdges.end();
744 for (; iter != eiter; iter++)
748 for (FunctionSet::const_iterator func_iter = functions.begin(); func_iter != functions.end(); func_iter++)
751 svfg->connectCallerAndCallee(cs, func, edges);
764 SVFGNode* dstNode = edge->getDstNode();
765 if (SVFUtil::isa<PHISVFGNode>(dstNode))
769 pushIntoWorklist(dstNode->
getId());
771 else if (SVFUtil::isa<FormalINSVFGNode, ActualOUTSVFGNode>(dstNode))
775 bool changed =
false;
777 SVFGNode* srcNode = edge->getSrcNode();
779 const NodeBS& pts = SVFUtil::cast<IndirectSVFGEdge>(edge)->getPointsTo();
784 if (propVarPtsAfterCGUpdated(ptd, srcNode, dstNode))
787 if (isFieldInsensitive(ptd))
790 const NodeBS& allFields = getAllFieldsObjVars(ptd);
792 fieldIt != fieldEit; ++fieldIt)
794 if (propVarPtsAfterCGUpdated(*fieldIt, srcNode, dstNode))
801 pushIntoWorklist(dstNode->
getId());
812 if (SVFUtil::isa<StoreSVFGNode>(src))
814 if (propDFOutToIn(src, var, dst, var))
819 if (propDFInToIn(src, var, dst, var))
827 std::vector<std::pair<unsigned, unsigned>> keys;
828 for (
const auto& pair : *pag)
829 keys.emplace_back(pair.first, 1);
842 &&
"FS::cluster: plain mapping requires dense allocation strategy.");
847 for (
NodeID i = 0; i < plainMapping->size(); ++i)
849 plainMapping->at(i) = i;
850 reversePlainMapping->at(i) = i;
858 for (std::pair<NodeID, NodeID> locPA : cmp)
862 for (std::pair<NodeID, NodeID> locPB : cmp)
864 if (locPB == locPA)
continue;
877 assert(
"Not May/NoAlias?");
#define DBOUT(TYPE, X)
LLVM debug macros, define type of your DBUG model of each pass.
APOffset getConstantStructFldIdx() const
Get methods.
const PAGNode * getParam() const
Return parameter.
const PAGNode * getRev() const
Receive parameter at callsite.
static AndersenWaveDiff * createAndersenWaveDiff(SVFIR *_pag)
Create an singleton instance directly instead of invoking llvm pass manager.
void finalize() override
Finalization of pointer analysis, and normalize points-to information to Bit Vector representation.
void processNode(NodeID nodeId) override
Handle various constraints.
virtual void solveConstraints()
virtual void updateConnectedNodes(const SVFGEdgeSetTy &edges)
Update nodes connected during updating call graph.
static std::unique_ptr< FlowSensitive > fspta
virtual bool propagateFromAPToFP(const ActualParmSVFGNode *ap, const SVFGNode *dst)
virtual bool propagateFromFRToAR(const FormalRetSVFGNode *fr, const SVFGNode *dst)
NodeStack & SCCDetect() override
SCC detection.
bool isStrongUpdate(const SVFGNode *node, NodeID &singleton)
Return TRUE if this is a strong update STORE statement.
virtual void readPtsFromFile(const std::string &filename)
virtual void plainMap(void) const
Sets the global best mapping as a plain mapping, i.e. n -> n.
SVFG::SVFGEdgeSetTy SVFGEdgeSetTy
void analyze() override
Flow sensitive analysis.
bool propFromSrcToDst(SVFGEdge *edge) override
Propagation.
virtual void cluster(void)
void finalize() override
Finalize analysis.
virtual void countAliases(Set< std::pair< NodeID, NodeID >> cmp, unsigned *mayAliases, unsigned *noAliases)
Fills may/noAliases for the location/pointer pairs in cmp.
bool processSVFGNode(SVFGNode *node)
virtual bool processLoad(const LoadSVFGNode *load)
bool propVarPtsAfterCGUpdated(NodeID var, const SVFGNode *src, const SVFGNode *dst)
virtual bool processPhi(const PHISVFGNode *phi)
virtual bool processStore(const StoreSVFGNode *store)
virtual bool processCopy(const CopySVFGNode *copy)
bool updateCallGraph(const CallSiteToFunPtrMap &callsites) override
Update call graph.
virtual bool processAddr(const AddrSVFGNode *addr)
virtual bool propAlongDirectEdge(const DirectSVFGEdge *edge)
Propagate points-to information along a DIRECT SVFG edge.
void initialize() override
Initialize analysis.
void connectCallerAndCallee(const CallEdgeMap &newEdges, SVFGEdgeSetTy &edges)
Connect nodes in SVFG.
virtual bool processGep(const GepSVFGNode *edge)
virtual bool propVarPtsFromSrcToDst(NodeID var, const SVFGNode *src, const SVFGNode *dst)
Propagate points-to information of a certain variable from src to dst.
virtual bool propAlongIndirectEdge(const IndirectSVFGEdge *edge)
Propagate points-to information along an INDIRECT SVFG edge.
virtual void solveAndwritePtsToFile(const std::string &filename)
NodeType * getSrcNode() const
NodeType * getDstNode() const
GEdgeSetTy::const_iterator const_iterator
bool isVariantFieldGep() const
Gep statement with a variant field index (pointer arithmetic) for struct field access.
const AccessPath & getAccessPath() const
const NodeBS & getPointsTo() const
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 void printStats(std::string title, Map< std::string, std::string > &stats)
static void evaluate(const std::vector< NodeID > &nodeMap, const Map< PointsTo, unsigned > pointsToSets, Map< std::string, std::string > &stats, bool accountForOcc)
Fills in *NumWords statistics in stats..
static NodeIDAllocator * get(void)
Return (singleton) allocator.
NodeID getNumObjects(void) const
Returns the total number of memory objects.
static const Option< bool > PlainMappingFs
Use an explicitly plain mapping with flow-sensitive (not null).
static const OptionMap< SVF::NodeIDAllocator::Strategy > NodeAllocStrat
static const Option< std::string > ReadAnder
static const Option< bool > ClusterAnder
Whether to stage Andersen's with Steensgaard and cluster based on that data.
static const Option< u32_t > FsTimeLimit
Time limit for the main phase (i.e., the actual solving) of FS analyses.
static const Option< bool > ClusterFs
Whether to cluster FS or VFS with the auxiliary Andersen's.
static const Option< std::string > WriteAnder
static const Option< bool > DumpVFG
OPVers::const_iterator opVerBegin() const
const PAGNode * getRes() const
OPVers::const_iterator opVerEnd() const
virtual Map< DataSet, unsigned > getAllPts(bool liveOnly) const =0
OrderedMap< const CallICFGNode *, FunctionSet > CallEdgeMap
virtual void initialize()
Initialization of a pointer analysis, including building symbol table and SVFIR etc.
Set< const SVFFunction * > FunctionSet
SVFIR::CallSiteToFunPtrMap CallSiteToFunPtrMap
bool empty() const
Returns true if set is empty.
const_iterator end() const
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.
const_iterator begin() const
static MappingPtr getCurrentBestNodeMapping()
NodeID getId() const
Get ID.
virtual bool isPointer() const
Whether it is a pointer.
NodeID getPAGDstNodeID() const
const PAGEdge * getPAGEdge() const
NodeID getPAGSrcNodeID() const
PAGNode * getPAGSrcNode() const
PAGNode * getPAGDstNode() const
virtual NodeStack & SCCDetect()
SCC detection.
virtual NodeStack & SCCDetect()
SCC detection.
std::string hclustMethodToString(hclust_fast_methods method)
Returns a string representation of a hclust method.
void stopAnalysisLimitTimer(bool limitTimerSet)
std::string pasMsg(const std::string &msg)
Print each pass/phase message by converting a string into blue string output.
LLVM_NODISCARD bool isa(const Y &Val)
bool startAnalysisLimitTimer(unsigned timeLimit)
std::ostream & outs()
Overwrite llvm::outs()
std::stack< NodeID > NodeStack
std::unordered_map< Key, Value, Hash, KeyEqual, Allocator > Map
std::unordered_set< Key, Hash, KeyEqual, Allocator > Set