38 using namespace SVFUtil;
83 consCG->dump(
"consCG_initial");
93 consCG->dump(
"consCG_final");
111 if (0 == numOfIteration % iterationForPrintStat)
118 if (updateCallGraph(getIndirectCallsites()))
160 if (!filename.empty())
161 this->readFromFile(filename);
172 if (!filename.empty())
173 this->writeObjVarToFile(filename);
175 if (!filename.empty())
176 this->writeToFile(filename);
182 consCG->resetSubs(consCG->getRep(
id));
183 for (
NodeID sub: consCG->getSubs(
id))
184 consCG->resetRep(sub);
185 consCG->resetSubs(
id);
186 consCG->resetRep(
id);
187 assert(!consCG->hasGNode(
id) &&
"this is either a rep nodeid or a sub nodeid should have already been merged to its field-insensitive base! ");
193 double cgUpdateStart = stat->getClk();
196 onTheFlyCallGraphSolve(callsites, newEdges);
198 for (CallEdgeMap::iterator it = newEdges.begin(), eit = newEdges.end();
201 for (FunctionSet::iterator cit = it->second.begin(),
202 ecit = it->second.end();
205 connectCaller2CalleeParams(it->first, *cit, cpySrcNodes);
209 bool hasNewForkEdges = updateThreadCallGraph(callsites, cpySrcNodes);
211 for (NodePairSet::iterator it = cpySrcNodes.begin(),
212 eit = cpySrcNodes.end();
215 pushIntoWorklist(it->first);
218 double cgUpdateEnd = stat->getClk();
219 timeOfUpdateCallGraph += (cgUpdateEnd - cgUpdateStart) /
TIMEINTERVAL;
221 return ((!newEdges.empty()) || hasNewForkEdges);
228 onTheFlyThreadCallGraphSolve(callsites, newForkEdges);
229 for (CallEdgeMap::iterator it = newForkEdges.begin(), eit = newForkEdges.end(); it != eit; it++)
231 for (FunctionSet::iterator cit = it->second.begin(),
232 ecit = it->second.end();
235 connectCaller2ForkedFunParams(it->first, *cit, cpySrcNodes);
238 return !newForkEdges.empty();
253 ThreadCallGraph *tdCallGraph = SVFUtil::dyn_cast<ThreadCallGraph>(callgraph);
264 if (addCopyEdge(srcAA, dstFA))
266 cpySrcNodes.insert(std::make_pair(srcAA, dstFA));
286 heapAllocatorViaIndCall(cs,cpySrcNodes);
289 if (pag->funHasRet(
F) && pag->callsiteHasRet(retBlockNode))
291 const PAGNode* cs_return = pag->getCallSiteRet(retBlockNode);
292 const PAGNode* fun_return = pag->getFunRet(
F);
297 if(addCopyEdge(srcret, dstrec))
299 cpySrcNodes.insert(std::make_pair(srcret,dstrec));
308 if (pag->hasCallSiteArgsMap(callBlockNode) && pag->hasFunArgsList(
F))
316 SVFIR::SVFVarList::const_iterator funArgIt = funArgList.begin(), funArgEit = funArgList.end();
317 SVFIR::SVFVarList::const_iterator csArgIt = csArgList.begin(), csArgEit = csArgList.end();
318 for (; funArgIt != funArgEit; ++csArgIt, ++funArgIt)
321 if (csArgIt == csArgEit)
326 const PAGNode *cs_arg = *csArgIt ;
327 const PAGNode *fun_arg = *funArgIt;
334 if(addCopyEdge(srcAA, dstFA))
336 cpySrcNodes.insert(std::make_pair(srcAA,dstFA));
344 NodeID vaF = sccRepNode(pag->getVarargNode(
F));
346 for (; csArgIt != csArgEit; ++csArgIt)
348 const PAGNode *cs_arg = *csArgIt;
352 if (addCopyEdge(vnAA,vaF))
354 cpySrcNodes.insert(std::make_pair(vnAA,vaF));
359 if(csArgIt != csArgEit)
371 const PAGNode* cs_return = pag->getCallSiteRet(retBlockNode);
373 CallSite2DummyValPN::const_iterator it = callsite2DummyValPN.find(cs);
374 if(it != callsite2DummyValPN.end())
376 srcret = sccRepNode(it->second);
380 NodeID valNode = pag->addDummyValNode();
382 addPts(valNode,objNode);
383 callsite2DummyValPN.insert(std::make_pair(cs,valNode));
390 if(addCopyEdge(srcret, dstrec))
391 cpySrcNodes.insert(std::make_pair(srcret,dstrec));
401 for (
NodeID n: redundantGepNodes)
403 NodeID base = pag->getBaseObjVar(
n);
404 GepObjVar *gepNode = SVFUtil::dyn_cast<GepObjVar>(pag->getGNode(
n));
405 assert(gepNode &&
"Not a gep node in redundantGepNodes set");
407 GepObjVarMap.erase(std::make_pair(base, apOffset));
408 memToFieldsMap[base].reset(
n);
411 pag->removeGNode(gepNode);
439 const PTDataTy *ptd = getPTDataTy();
458 if (sccRepNode(nodeId) != nodeId)
462 double insertStart = stat->getClk();
463 handleLoadStore(node);
464 double insertEnd = stat->getClk();
465 timeOfProcessLoadStore += (insertEnd - insertStart) /
TIMEINTERVAL;
467 double propStart = stat->getClk();
469 double propEnd = stat->getClk();
470 timeOfProcessCopyGep += (propEnd - propStart) /
TIMEINTERVAL;
479 computeDiffPts(nodeId);
481 if (!getDiffPts(nodeId).empty())
484 processCopy(nodeId, edge);
487 if (
GepCGEdge* gepEdge = SVFUtil::dyn_cast<GepCGEdge>(edge))
488 processGep(nodeId, gepEdge);
500 getPts(nodeId).end(); piter != epiter; ++piter)
507 if (processLoad(ptd, *it))
508 pushIntoWorklist(ptd);
515 if (processStore(ptd, *it))
516 pushIntoWorklist((*it)->getSrcID());
531 processAddr(SVFUtil::cast<AddrCGEdge>(*it));
540 numOfProcessedAddr++;
545 pushIntoWorklist(dst);
559 if (pag->isConstantObj(node) || pag->getGNode(load->
getDstID())->isPointer() ==
false)
562 numOfProcessedLoad++;
565 return addCopyEdge(node, dst);
579 if (pag->isConstantObj(node) || pag->getGNode(store->
getSrcID())->isPointer() ==
false)
582 numOfProcessedStore++;
585 return addCopyEdge(src, node);
595 numOfProcessedCopy++;
597 assert((SVFUtil::isa<CopyCGEdge>(edge)) &&
"not copy/call/ret ??");
599 const PointsTo& srcPts = getDiffPts(node);
601 bool changed = unionPts(dst, srcPts);
603 pushIntoWorklist(dst);
616 return processGepPts(srcPts, edge);
627 if (SVFUtil::isa<VariantGepCGEdge>(edge))
634 if (consCG->isBlkObjOrConstantObj(o))
640 if (!isFieldInsensitive(o))
642 setObjFieldInsensitive(o);
643 consCG->addNodeToBeCollapsed(consCG->getBaseObjVar(o));
647 NodeID baseId = consCG->getFIObjVar(o);
648 tmpDstPts.
set(baseId);
651 else if (
const NormalGepCGEdge* normalGepEdge = SVFUtil::dyn_cast<NormalGepCGEdge>(edge))
658 if (consCG->isBlkObjOrConstantObj(o) || isFieldInsensitive(o))
664 NodeID fieldSrcPtdNode = consCG->getGepObjVar(o, normalGepEdge->getAccessPath().getConstantStructFldIdx());
665 tmpDstPts.
set(fieldSrcPtdNode);
670 assert(
false &&
"Andersen::processGepPts: New type GEP edge type?");
674 if (unionPts(dstId, tmpDstPts))
676 pushIntoWorklist(dstId);
691 if (consCG->isPWCNode(nodeId) && collapseNodePts(nodeId))
697 while (consCG->hasNodesToBeCollapsed())
699 NodeID node = consCG->getNextCollapseNode();
702 if (collapseField(node))
713 NodeStack & topoOrder = getSCCDetector()->topoNodeStack();
714 while (!topoOrder.empty())
716 NodeID repNodeId = topoOrder.top();
718 revTopoOrder.push(repNodeId);
719 const NodeBS& subNodes = getSCCDetector()->subNodes(repNodeId);
721 mergeSccNodes(repNodeId, subNodes);
725 while (!revTopoOrder.empty())
727 NodeID nodeId = revTopoOrder.top();
729 topoOrder.push(nodeId);
742 NodeID subNodeId = *nodeIt;
743 if (subNodeId != repNodeId)
745 mergeNodeToRep(subNodeId, repNodeId);
755 bool changed =
false;
756 const PointsTo& nodePts = getPts(nodeId);
761 if (isFieldInsensitive(*ptsIt))
764 if (collapseField(*ptsIt))
779 if (consCG->isBlkObjOrConstantObj(nodeId))
782 bool changed =
false;
784 double start = stat->getClk();
787 setObjFieldInsensitive(nodeId);
790 NodeID baseId = consCG->getFIObjVar(nodeId);
791 NodeID baseRepNodeId = consCG->sccRepNode(baseId);
792 NodeBS & allFields = consCG->getAllFieldsObjVars(baseId);
795 NodeID fieldId = *fieldIt;
796 if (fieldId != baseId)
799 const NodeSet revPts = getRevPts(fieldId);
800 for (
const NodeID o : revPts)
803 clearPts(o, fieldId);
810 NodeID fieldRepNodeId = consCG->sccRepNode(fieldId);
811 mergeNodeToRep(fieldRepNodeId, baseRepNodeId);
812 if (fieldId != baseRepNodeId)
816 redundantGepNodes.set(fieldId);
821 if (consCG->isPWCNode(baseRepNodeId))
822 if (collapseNodePts(baseRepNodeId))
825 double end = stat->getClk();
838 double sccStart = stat->getClk();
840 double sccEnd = stat->getClk();
844 double mergeStart = stat->getClk();
848 double mergeEnd = stat->getClk();
850 timeOfSCCMerges += (mergeEnd - mergeStart)/
TIMEINTERVAL;
852 return getSCCDetector()->topoNodeStack();
865 updatePropaPts(newRepId, nodeId);
866 unionPts(newRepId,nodeId);
870 bool pwc = consCG->moveEdgesToRepNode(node, consCG->getConstraintNode(newRepId));
880 updateNodeRepAndSubs(node->
getId(),newRepId);
882 consCG->removeConstraintNode(node);
892 if (mergeSrcToTgt(nodeId,newRepId))
893 consCG->setPWCNode(newRepId);
901 consCG->setRep(nodeId,newRepId);
906 NodeBS& nodeSubs = consCG->sccSubNodes(nodeId);
910 consCG->setRep(subId,newRepId);
913 consCG->setSubs(newRepId,repSubs);
914 consCG->resetSubs(nodeId);
919 assert(
Options::MaxFieldLimit() == 0 &&
"Andersen::cluster: clustering for Andersen's is currently only supported in field-insensitive analysis");
921 std::vector<std::pair<unsigned, unsigned>> keys;
924 keys.push_back(std::make_pair(pit->first, 1));
927 std::vector<std::pair<hclust_fast_methods, std::vector<NodeID>>> candidates;
941 for (OrderedNodeSet::iterator nIter = this->getAllValidPtrs().begin();
942 nIter != this->getAllValidPtrs().end(); ++nIter)
944 const PAGNode* node = getPAG()->getGNode(*nIter);
945 if (getPAG()->isValidTopLevelPtr(node))
948 outs() <<
"\nNodeID " << node->
getId() <<
" ";
952 outs() <<
"\t\tPointsTo: {empty}\n";
956 outs() <<
"\t\tPointsTo: { ";
958 multiset<u32_t> line;
964 for (multiset<u32_t>::const_iterator it = line.begin(); it != line.end(); ++it)
967 if (
auto gepNode = SVFUtil::dyn_cast<GepObjVar>(pag->getGNode(*it)))
970 outs() << *it <<
" ";
972 outs() << *it <<
" ";
#define DBOUT(TYPE, X)
LLVM debug macros, define type of your DBUG model of each pass.
static double timeOfSCCMerges
static u32_t numOfProcessedCopy
Number of processed Addr edge.
static u32_t numOfSCCDetection
virtual void normalizePointsTo() override
static u32_t numOfSfrs
Number of processed Store edge.
virtual void finalize() override
Finalize analysis.
static double timeOfUpdateCallGraph
static u32_t numOfProcessedStore
Number of processed Load edge.
virtual void connectCaller2CalleeParams(const CallICFGNode *cs, const SVFFunction *F, NodePairSet &cpySrcNodes)
Connect formal and actual parameters for indirect callsites.
static u32_t numOfProcessedAddr
Statistics.
virtual bool updateCallGraph(const CallSiteToFunPtrMap &) override
Update call graph.
void heapAllocatorViaIndCall(const CallICFGNode *cs, NodePairSet &cpySrcNodes)
virtual void readPtsFromFile(const std::string &filename)
static u32_t numOfProcessedLoad
Number of processed Gep edge.
static double timeOfSCCDetection
virtual void initialize() override
Initialize analysis.
~AndersenBase() override
Destructor.
virtual void analyze() override
Andersen analysis.
static u32_t numOfFieldExpand
static double timeOfProcessLoadStore
static u32_t numOfProcessedGep
Number of processed Copy edge.
static double timeOfProcessCopyGep
static u32_t MaxPointsToSetSize
virtual void solveConstraints()
virtual bool updateThreadCallGraph(const CallSiteToFunPtrMap &, NodePairSet &)
Update thread call graph.
static double timeOfCollapse
static u32_t AveragePointsToSetSize
virtual void solveAndwritePtsToFile(const std::string &filename)
void cleanConsCG(NodeID id)
remove redundant gepnodes in constraint graph
virtual void connectCaller2ForkedFunParams(const CallICFGNode *cs, const SVFFunction *F, NodePairSet &cpySrcNodes)
Connect formal and actual parameters for indirect forksites.
virtual void handleLoadStore(ConstraintNode *node)
void mergeSccNodes(NodeID repNodeId, const NodeBS &subNodes)
Merge sub node in a SCC cycle to their rep node.
virtual void processNode(NodeID nodeId)
Override WPASolver function in order to use the default solver.
virtual void initialize()
Initialize analysis.
virtual NodeStack & SCCDetect()
SCC detection.
virtual void mergeNodeToRep(NodeID nodeId, NodeID newRepId)
Merge sub node to its rep.
bool collapseNodePts(NodeID nodeId)
virtual bool processGep(NodeID node, const GepCGEdge *edge)
virtual void handleCopyGep(ConstraintNode *node)
virtual bool processLoad(NodeID node, const ConstraintEdge *load)
void collapseFields()
collapse positive weight cycles of a graph
virtual bool processStore(NodeID node, const ConstraintEdge *load)
virtual bool processCopy(NodeID node, const ConstraintEdge *edge)
virtual bool processGepPts(const PointsTo &pts, const GepCGEdge *edge)
virtual void processAddr(const AddrCGEdge *addr)
void updateNodeRepAndSubs(NodeID nodeId, NodeID newRepId)
Updates subnodes of its rep, and rep node of its subs.
virtual void finalize()
Finalize analysis.
void processAllAddr()
handling various constraints
virtual void cluster(void) const
virtual bool mergeSrcToTgt(NodeID srcId, NodeID tgtId)
virtual void collapsePWCNode(NodeID nodeId)
Collapse a field object into its base for field insensitive analysis.
bool collapseField(NodeID nodeId)
void finalize() override
Finalization of pointer analysis, and normalize points-to information to Bit Vector representation.
const SVFFunction * getCalledFunction() const
const std::string getSourceLoc() const override
const RetICFGNode * getRetICFGNode() const
Return callsite.
bool isPWCNode() const
Whether a node involves in PWC, if so, all its points-to elements should become field-insensitive.
const_iterator outgoingLoadsEnd() const
const_iterator incomingAddrsBegin() const
const ConstraintEdge::ConstraintEdgeSetTy & getGepOutEdges() const
const_iterator incomingStoresBegin() const
const_iterator incomingStoresEnd() const
ConstraintEdge::ConstraintEdgeSetTy::const_iterator const_iterator
const ConstraintEdge::ConstraintEdgeSetTy & getCopyOutEdges() const
const_iterator incomingAddrsEnd() const
const_iterator outgoingLoadsBegin() const
NodeID getSrcID() const
get methods of the components
IDToNodeMapTy::const_iterator const_iterator
IDToNodeMapTy::iterator iterator
Node Iterators.
APOffset getConstantFieldIdx() const
offset of the mem object
NodeID getBaseNode(void) const
Return the base object from which this GEP node came from.
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 const Option< u32_t > AnderTimeLimit
Time limit for the Andersen's analyses.
static const Option< bool > PrintFieldWithBasePrefix
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< bool > PrintCGGraph
static const Option< u32_t > MaxFieldLimit
Maximum number of field derivations for an object.
static const Option< std::string > WriteAnder
static const Option< bool > ConsCGDotGraph
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.
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)
void set(u32_t n)
Inserts n in the set.
const_iterator begin() const
static MappingPtr getCurrentBestNodeMapping()
virtual const SVFType * getType() const
NodeID getId() const
Get ID.
const std::string valueOnlyToString() const
std::vector< const SVFVar * > SVFVarList
Map< NodeID, NodeBS > MemObjToFieldsMap
Map< NodeOffset, NodeID > NodeOffsetMap
virtual bool isPointer() const
Whether it is a pointer.
virtual const std::string toString() const
static Steensgaard * createSteensgaard(SVFIR *_pag)
Create an singleton instance.
const SVFVar * getFormalParmOfForkedFun(const SVFFunction *F) const
Return the formal parm of forked function (the first arg in pthread)
const SVFVar * getActualParmAtForkSite(const CallICFGNode *inst) const
ThreadAPI * getThreadAPI() const
Thread API.
virtual NodeStack & SCCDetect()
SCC detection.
void stopAnalysisLimitTimer(bool limitTimerSet)
bool isHeapAllocExtFunViaRet(const SVFFunction *fun)
Return true if the call is a heap allocator/reallocator.
std::string pasMsg(const std::string &msg)
Print each pass/phase message by converting a string into blue string output.
bool startAnalysisLimitTimer(unsigned timeLimit)
void writeWrnMsg(const std::string &msg)
Writes a message run through wrnMsg.
std::ostream & outs()
Overwrite llvm::outs()
std::stack< NodeID > NodeStack
std::unordered_map< Key, Value, Hash, KeyEqual, Allocator > Map
Set< NodePair > NodePairSet