From b75eea52d7bd16ea1cd707326a762c10abce93e3 Mon Sep 17 00:00:00 2001 From: joelyyoung Date: Thu, 19 Sep 2024 23:31:17 +0800 Subject: [PATCH 1/7] move updateCallGraph to AndersenBase --- svf/include/WPA/Andersen.h | 13 +++--- svf/include/WPA/Steensgaard.h | 4 +- svf/lib/WPA/Andersen.cpp | 87 ++++++++++++++++++++++++----------- svf/lib/WPA/Steensgaard.cpp | 60 ++++++++++++------------ 4 files changed, 98 insertions(+), 66 deletions(-) diff --git a/svf/include/WPA/Andersen.h b/svf/include/WPA/Andersen.h index bb600602a..388a86806 100644 --- a/svf/include/WPA/Andersen.h +++ b/svf/include/WPA/Andersen.h @@ -82,10 +82,11 @@ class AndersenBase: public WPAConstraintSolver, public BVDataPTAImpl virtual void finalize() override; /// Implement it in child class to update call graph - virtual inline bool updateCallGraph(const CallSiteToFunPtrMap&) override - { - return false; - } + virtual bool updateCallGraph(const CallSiteToFunPtrMap&) override; + + /// Connect formal and actual parameters for indirect callsites + virtual void connectCaller2CalleeParams(const CallICFGNode* cs, const SVFFunction* F, + NodePairSet& cpySrcNodes) { }; /// Methods for support type inquiry through isa, cast, and dyn_cast: //@{ @@ -311,8 +312,8 @@ class Andersen: public AndersenBase return false; } - /// Update call graph for the input indirect callsites - virtual bool updateCallGraph(const CallSiteToFunPtrMap& callsites); +// /// Update call graph for the input indirect callsites +// virtual bool updateCallGraph(const CallSiteToFunPtrMap& callsites); /// Connect formal and actual parameters for indirect callsites void connectCaller2CalleeParams(const CallICFGNode* cs, const SVFFunction* F, NodePairSet& cpySrcNodes); diff --git a/svf/include/WPA/Steensgaard.h b/svf/include/WPA/Steensgaard.h index 24ff2de4b..fc18107d1 100644 --- a/svf/include/WPA/Steensgaard.h +++ b/svf/include/WPA/Steensgaard.h @@ -123,8 +123,8 @@ class Steensgaard : public AndersenBase ///< a heap allocator void heapAllocatorViaIndCall(const CallICFGNode* cs, NodePairSet& cpySrcNodes); - /// Update call graph for the input indirect callsites - virtual bool updateCallGraph(const CallSiteToFunPtrMap& callsites); +// /// Update call graph for the input indirect callsites +// virtual bool updateCallGraph(const CallSiteToFunPtrMap& callsites); /// Connect formal and actual parameters for indirect callsites void connectCaller2CalleeParams(const CallICFGNode* cs, const SVFFunction* F, diff --git a/svf/lib/WPA/Andersen.cpp b/svf/lib/WPA/Andersen.cpp index 4fa4c02bb..6c8f5ceac 100644 --- a/svf/lib/WPA/Andersen.cpp +++ b/svf/lib/WPA/Andersen.cpp @@ -187,6 +187,37 @@ void AndersenBase::cleanConsCG(NodeID id) assert(!consCG->hasGNode(id) && "this is either a rep nodeid or a sub nodeid should have already been merged to its field-insensitive base! "); } +bool AndersenBase::updateCallGraph(const CallSiteToFunPtrMap& callsites) +{ + + double cgUpdateStart = stat->getClk(); + + CallEdgeMap newEdges; + onTheFlyCallGraphSolve(callsites, newEdges); + NodePairSet cpySrcNodes; /// nodes as a src of a generated new copy edge + for (CallEdgeMap::iterator it = newEdges.begin(), eit = newEdges.end(); + it != eit; ++it) + { + for (FunctionSet::iterator cit = it->second.begin(), + ecit = it->second.end(); + cit != ecit; ++cit) + { + connectCaller2CalleeParams(it->first, *cit, cpySrcNodes); + } + } + for (NodePairSet::iterator it = cpySrcNodes.begin(), + eit = cpySrcNodes.end(); + it != eit; ++it) + { + pushIntoWorklist(it->first); + } + + double cgUpdateEnd = stat->getClk(); + timeOfUpdateCallGraph += (cgUpdateEnd - cgUpdateStart) / TIMEINTERVAL; + + return (!newEdges.empty()); +} + void AndersenBase::normalizePointsTo() { SVFIR::MemObjToFieldsMap &memToFieldsMap = pag->getMemToFieldsMap(); @@ -648,34 +679,34 @@ NodeStack& Andersen::SCCDetect() return getSCCDetector()->topoNodeStack(); } -/*! - * Update call graph for the input indirect callsites - */ -bool Andersen::updateCallGraph(const CallSiteToFunPtrMap& callsites) -{ - - double cgUpdateStart = stat->getClk(); - - CallEdgeMap newEdges; - onTheFlyCallGraphSolve(callsites,newEdges); - NodePairSet cpySrcNodes; /// nodes as a src of a generated new copy edge - for(CallEdgeMap::iterator it = newEdges.begin(), eit = newEdges.end(); it!=eit; ++it ) - { - for(FunctionSet::iterator cit = it->second.begin(), ecit = it->second.end(); cit!=ecit; ++cit) - { - connectCaller2CalleeParams(it->first,*cit,cpySrcNodes); - } - } - for(NodePairSet::iterator it = cpySrcNodes.begin(), eit = cpySrcNodes.end(); it!=eit; ++it) - { - pushIntoWorklist(it->first); - } - - double cgUpdateEnd = stat->getClk(); - timeOfUpdateCallGraph += (cgUpdateEnd - cgUpdateStart) / TIMEINTERVAL; - - return (!newEdges.empty()); -} +///*! +// * Update call graph for the input indirect callsites +// */ +//bool Andersen::updateCallGraph(const CallSiteToFunPtrMap& callsites) +//{ +// +// double cgUpdateStart = stat->getClk(); +// +// CallEdgeMap newEdges; +// onTheFlyCallGraphSolve(callsites,newEdges); +// NodePairSet cpySrcNodes; /// nodes as a src of a generated new copy edge +// for(CallEdgeMap::iterator it = newEdges.begin(), eit = newEdges.end(); it!=eit; ++it ) +// { +// for(FunctionSet::iterator cit = it->second.begin(), ecit = it->second.end(); cit!=ecit; ++cit) +// { +// connectCaller2CalleeParams(it->first,*cit,cpySrcNodes); +// } +// } +// for(NodePairSet::iterator it = cpySrcNodes.begin(), eit = cpySrcNodes.end(); it!=eit; ++it) +// { +// pushIntoWorklist(it->first); +// } +// +// double cgUpdateEnd = stat->getClk(); +// timeOfUpdateCallGraph += (cgUpdateEnd - cgUpdateStart) / TIMEINTERVAL; +// +// return (!newEdges.empty()); +//} void Andersen::heapAllocatorViaIndCall(const CallICFGNode* cs, NodePairSet &cpySrcNodes) { diff --git a/svf/lib/WPA/Steensgaard.cpp b/svf/lib/WPA/Steensgaard.cpp index 3667ee6fa..3d94d7f2e 100644 --- a/svf/lib/WPA/Steensgaard.cpp +++ b/svf/lib/WPA/Steensgaard.cpp @@ -124,36 +124,36 @@ void Steensgaard::processAllAddr() } } -bool Steensgaard::updateCallGraph(const CallSiteToFunPtrMap& callsites) -{ - - double cgUpdateStart = stat->getClk(); - - CallEdgeMap newEdges; - onTheFlyCallGraphSolve(callsites, newEdges); - NodePairSet cpySrcNodes; /// nodes as a src of a generated new copy edge - for (CallEdgeMap::iterator it = newEdges.begin(), eit = newEdges.end(); - it != eit; ++it) - { - for (FunctionSet::iterator cit = it->second.begin(), - ecit = it->second.end(); - cit != ecit; ++cit) - { - connectCaller2CalleeParams(it->first, *cit, cpySrcNodes); - } - } - for (NodePairSet::iterator it = cpySrcNodes.begin(), - eit = cpySrcNodes.end(); - it != eit; ++it) - { - pushIntoWorklist(it->first); - } - - double cgUpdateEnd = stat->getClk(); - timeOfUpdateCallGraph += (cgUpdateEnd - cgUpdateStart) / TIMEINTERVAL; - - return (!newEdges.empty()); -} +//bool Steensgaard::updateCallGraph(const CallSiteToFunPtrMap& callsites) +//{ +// +// double cgUpdateStart = stat->getClk(); +// +// CallEdgeMap newEdges; +// onTheFlyCallGraphSolve(callsites, newEdges); +// NodePairSet cpySrcNodes; /// nodes as a src of a generated new copy edge +// for (CallEdgeMap::iterator it = newEdges.begin(), eit = newEdges.end(); +// it != eit; ++it) +// { +// for (FunctionSet::iterator cit = it->second.begin(), +// ecit = it->second.end(); +// cit != ecit; ++cit) +// { +// connectCaller2CalleeParams(it->first, *cit, cpySrcNodes); +// } +// } +// for (NodePairSet::iterator it = cpySrcNodes.begin(), +// eit = cpySrcNodes.end(); +// it != eit; ++it) +// { +// pushIntoWorklist(it->first); +// } +// +// double cgUpdateEnd = stat->getClk(); +// timeOfUpdateCallGraph += (cgUpdateEnd - cgUpdateStart) / TIMEINTERVAL; +// +// return (!newEdges.empty()); +//} void Steensgaard::heapAllocatorViaIndCall(const CallICFGNode* cs, NodePairSet& cpySrcNodes) { From 4ed53eb19daec010ebd1639457c396726a2b0b24 Mon Sep 17 00:00:00 2001 From: joelyyoung Date: Fri, 20 Sep 2024 00:17:49 +0800 Subject: [PATCH 2/7] move connectCaller2CalleeParams to AndersenBase --- svf/include/WPA/Andersen.h | 28 ++-- svf/include/WPA/Steensgaard.h | 20 +-- svf/lib/WPA/Andersen.cpp | 273 +++++++++++++++------------------- svf/lib/WPA/Steensgaard.cpp | 164 +------------------- 4 files changed, 147 insertions(+), 338 deletions(-) diff --git a/svf/include/WPA/Andersen.h b/svf/include/WPA/Andersen.h index 388a86806..dbec01712 100644 --- a/svf/include/WPA/Andersen.h +++ b/svf/include/WPA/Andersen.h @@ -54,6 +54,9 @@ typedef WPASolver WPAConstraintSolver; class AndersenBase: public WPAConstraintSolver, public BVDataPTAImpl { +public: + typedef OrderedMap CallSite2DummyValPN; + public: /// Constructor @@ -86,7 +89,7 @@ class AndersenBase: public WPAConstraintSolver, public BVDataPTAImpl /// Connect formal and actual parameters for indirect callsites virtual void connectCaller2CalleeParams(const CallICFGNode* cs, const SVFFunction* F, - NodePairSet& cpySrcNodes) { }; + NodePairSet& cpySrcNodes); /// Methods for support type inquiry through isa, cast, and dyn_cast: //@{ @@ -118,12 +121,22 @@ class AndersenBase: public WPAConstraintSolver, public BVDataPTAImpl { return consCG->sccRepNode(id); } + virtual inline NodeID getSubstitudeID(NodeID id) const + { + return sccRepNode(id); + } inline NodeBS& sccSubNodes(NodeID repId) { return consCG->sccSubNodes(repId); } //@} + /// Add copy edge on constraint graph + virtual inline bool addCopyEdge(NodeID src, NodeID dst) + { + return false; + } + /// dump statistics inline void printStat() { @@ -161,6 +174,11 @@ class AndersenBase: public WPAConstraintSolver, public BVDataPTAImpl protected: /// Constraint Graph ConstraintGraph* consCG; + CallSite2DummyValPN + callsite2DummyValPN; ///< Map an instruction to a dummy obj which + ///< created at an indirect callsite, which invokes + ///< a heap allocator + void heapAllocatorViaIndCall(const CallICFGNode* cs, NodePairSet& cpySrcNodes); }; /*! @@ -172,7 +190,6 @@ class Andersen: public AndersenBase public: typedef SCCDetection CGSCC; - typedef OrderedMap CallSite2DummyValPN; /// Constructor Andersen(SVFIR* _pag, PTATY type = Andersen_WPA, bool alias_check = true) @@ -244,7 +261,6 @@ class Andersen: public AndersenBase protected: CallSite2DummyValPN callsite2DummyValPN; ///< Map an instruction to a dummy obj which created at an indirect callsite, which invokes a heap allocator - void heapAllocatorViaIndCall(const CallICFGNode* cs,NodePairSet &cpySrcNodes); /// Handle diff points-to set. virtual inline void computeDiffPts(NodeID id) @@ -312,12 +328,6 @@ class Andersen: public AndersenBase return false; } -// /// Update call graph for the input indirect callsites -// virtual bool updateCallGraph(const CallSiteToFunPtrMap& callsites); - - /// Connect formal and actual parameters for indirect callsites - void connectCaller2CalleeParams(const CallICFGNode* cs, const SVFFunction* F, NodePairSet& cpySrcNodes); - /// Merge sub node to its rep virtual void mergeNodeToRep(NodeID nodeId,NodeID newRepId); diff --git a/svf/include/WPA/Steensgaard.h b/svf/include/WPA/Steensgaard.h index fc18107d1..17b17d9f4 100644 --- a/svf/include/WPA/Steensgaard.h +++ b/svf/include/WPA/Steensgaard.h @@ -23,7 +23,6 @@ class Steensgaard : public AndersenBase public: typedef Map NodeToEquivClassMap; typedef Map> NodeToSubsMap; - typedef OrderedMap CallSite2DummyValPN; /// Constructor Steensgaard(SVFIR* _pag) : AndersenBase(_pag, Steensgaard_WPA, true) {} @@ -98,6 +97,11 @@ class Steensgaard : public AndersenBase else return it->second; } + /// Universal API for getting the substitude of a ConsG Node + virtual inline NodeID getSubstitudeID(NodeID id) const + { + return getEC(id); + } void setEC(NodeID node, NodeID rep); inline Set& getSubNodes(NodeID id) @@ -116,20 +120,6 @@ class Steensgaard : public AndersenBase return consCG->addCopyCGEdge(src, dst); } -protected: - CallSite2DummyValPN - callsite2DummyValPN; ///< Map an instruction to a dummy obj which - ///< created at an indirect callsite, which invokes - ///< a heap allocator - void heapAllocatorViaIndCall(const CallICFGNode* cs, NodePairSet& cpySrcNodes); - -// /// Update call graph for the input indirect callsites -// virtual bool updateCallGraph(const CallSiteToFunPtrMap& callsites); - - /// Connect formal and actual parameters for indirect callsites - void connectCaller2CalleeParams(const CallICFGNode* cs, const SVFFunction* F, - NodePairSet& cpySrcNodes); - private: static Steensgaard* steens; // static instance NodeToEquivClassMap nodeToECMap; diff --git a/svf/lib/WPA/Andersen.cpp b/svf/lib/WPA/Andersen.cpp index 6c8f5ceac..14317c60e 100644 --- a/svf/lib/WPA/Andersen.cpp +++ b/svf/lib/WPA/Andersen.cpp @@ -218,6 +218,128 @@ bool AndersenBase::updateCallGraph(const CallSiteToFunPtrMap& callsites) return (!newEdges.empty()); } +///*! +// * Connect formal and actual parameters for indirect callsites +// */ +void AndersenBase::connectCaller2CalleeParams(const CallICFGNode* cs, const SVFFunction* F, NodePairSet &cpySrcNodes) +{ + assert(F); + + DBOUT(DAndersen, outs() << "connect parameters from indirect callsite " << cs.getInstruction()->toString() << " to callee " << *F << "\n"); + + const CallICFGNode* callBlockNode = cs; + const RetICFGNode* retBlockNode = cs->getRetICFGNode(); + + if(SVFUtil::isHeapAllocExtFunViaRet(F) && pag->callsiteHasRet(retBlockNode)) + { + heapAllocatorViaIndCall(cs,cpySrcNodes); + } + + if (pag->funHasRet(F) && pag->callsiteHasRet(retBlockNode)) + { + const PAGNode* cs_return = pag->getCallSiteRet(retBlockNode); + const PAGNode* fun_return = pag->getFunRet(F); + if (cs_return->isPointer() && fun_return->isPointer()) + { + NodeID dstrec = getSubstitudeID(cs_return->getId()); + NodeID srcret = getSubstitudeID(fun_return->getId()); + if(addCopyEdge(srcret, dstrec)) + { + cpySrcNodes.insert(std::make_pair(srcret,dstrec)); + } + } + else + { + DBOUT(DAndersen, outs() << "not a pointer ignored\n"); + } + } + + if (pag->hasCallSiteArgsMap(callBlockNode) && pag->hasFunArgsList(F)) + { + + // connect actual and formal param + const SVFIR::SVFVarList& csArgList = pag->getCallSiteArgsList(callBlockNode); + const SVFIR::SVFVarList& funArgList = pag->getFunArgsList(F); + //Go through the fixed parameters. + DBOUT(DPAGBuild, outs() << " args:"); + SVFIR::SVFVarList::const_iterator funArgIt = funArgList.begin(), funArgEit = funArgList.end(); + SVFIR::SVFVarList::const_iterator csArgIt = csArgList.begin(), csArgEit = csArgList.end(); + for (; funArgIt != funArgEit; ++csArgIt, ++funArgIt) + { + //Some programs (e.g. Linux kernel) leave unneeded parameters empty. + if (csArgIt == csArgEit) + { + DBOUT(DAndersen, outs() << " !! not enough args\n"); + break; + } + const PAGNode *cs_arg = *csArgIt ; + const PAGNode *fun_arg = *funArgIt; + + if (cs_arg->isPointer() && fun_arg->isPointer()) + { + DBOUT(DAndersen, outs() << "process actual parm " << cs_arg->toString() << " \n"); + NodeID srcAA = getSubstitudeID(cs_arg->getId()); + NodeID dstFA = getSubstitudeID(fun_arg->getId()); + if(addCopyEdge(srcAA, dstFA)) + { + cpySrcNodes.insert(std::make_pair(srcAA,dstFA)); + } + } + } + + //Any remaining actual args must be varargs. + if (F->isVarArg()) + { + NodeID vaF = getSubstitudeID(pag->getVarargNode(F)); + DBOUT(DPAGBuild, outs() << "\n varargs:"); + for (; csArgIt != csArgEit; ++csArgIt) + { + const PAGNode *cs_arg = *csArgIt; + if (cs_arg->isPointer()) + { + NodeID vnAA = getSubstitudeID(cs_arg->getId()); + if (addCopyEdge(vnAA,vaF)) + { + cpySrcNodes.insert(std::make_pair(vnAA,vaF)); + } + } + } + } + if(csArgIt != csArgEit) + { + writeWrnMsg("too many args to non-vararg func."); + writeWrnMsg("(" + cs->getSourceLoc() + ")"); + } + } +} + +void AndersenBase::heapAllocatorViaIndCall(const CallICFGNode* cs, NodePairSet &cpySrcNodes) +{ + assert(cs->getCalledFunction() == nullptr && "not an indirect callsite?"); + const RetICFGNode* retBlockNode = cs->getRetICFGNode(); + const PAGNode* cs_return = pag->getCallSiteRet(retBlockNode); + NodeID srcret; + CallSite2DummyValPN::const_iterator it = callsite2DummyValPN.find(cs); + if(it != callsite2DummyValPN.end()) + { + srcret = getSubstitudeID(it->second); + } + else + { + NodeID valNode = pag->addDummyValNode(); + NodeID objNode = pag->addDummyObjNode(cs->getCallSite()->getType()); + addPts(valNode,objNode); + callsite2DummyValPN.insert(std::make_pair(cs,valNode)); + consCG->addConstraintNode(new ConstraintNode(valNode),valNode); + consCG->addConstraintNode(new ConstraintNode(objNode),objNode); + srcret = valNode; + } + + NodeID dstrec = getSubstitudeID(cs_return->getId()); + if(addCopyEdge(srcret, dstrec)) + cpySrcNodes.insert(std::make_pair(srcret,dstrec)); +} + void AndersenBase::normalizePointsTo() { SVFIR::MemObjToFieldsMap &memToFieldsMap = pag->getMemToFieldsMap(); @@ -679,157 +801,6 @@ NodeStack& Andersen::SCCDetect() return getSCCDetector()->topoNodeStack(); } -///*! -// * Update call graph for the input indirect callsites -// */ -//bool Andersen::updateCallGraph(const CallSiteToFunPtrMap& callsites) -//{ -// -// double cgUpdateStart = stat->getClk(); -// -// CallEdgeMap newEdges; -// onTheFlyCallGraphSolve(callsites,newEdges); -// NodePairSet cpySrcNodes; /// nodes as a src of a generated new copy edge -// for(CallEdgeMap::iterator it = newEdges.begin(), eit = newEdges.end(); it!=eit; ++it ) -// { -// for(FunctionSet::iterator cit = it->second.begin(), ecit = it->second.end(); cit!=ecit; ++cit) -// { -// connectCaller2CalleeParams(it->first,*cit,cpySrcNodes); -// } -// } -// for(NodePairSet::iterator it = cpySrcNodes.begin(), eit = cpySrcNodes.end(); it!=eit; ++it) -// { -// pushIntoWorklist(it->first); -// } -// -// double cgUpdateEnd = stat->getClk(); -// timeOfUpdateCallGraph += (cgUpdateEnd - cgUpdateStart) / TIMEINTERVAL; -// -// return (!newEdges.empty()); -//} - -void Andersen::heapAllocatorViaIndCall(const CallICFGNode* cs, NodePairSet &cpySrcNodes) -{ - assert(cs->getCalledFunction() == nullptr && "not an indirect callsite?"); - const RetICFGNode* retBlockNode = cs->getRetICFGNode(); - const PAGNode* cs_return = pag->getCallSiteRet(retBlockNode); - NodeID srcret; - CallSite2DummyValPN::const_iterator it = callsite2DummyValPN.find(cs); - if(it != callsite2DummyValPN.end()) - { - srcret = sccRepNode(it->second); - } - else - { - NodeID valNode = pag->addDummyValNode(); - NodeID objNode = pag->addDummyObjNode(cs->getCallSite()->getType()); - addPts(valNode,objNode); - callsite2DummyValPN.insert(std::make_pair(cs,valNode)); - consCG->addConstraintNode(new ConstraintNode(valNode),valNode); - consCG->addConstraintNode(new ConstraintNode(objNode),objNode); - srcret = valNode; - } - - NodeID dstrec = sccRepNode(cs_return->getId()); - if(addCopyEdge(srcret, dstrec)) - cpySrcNodes.insert(std::make_pair(srcret,dstrec)); -} - -/*! - * Connect formal and actual parameters for indirect callsites - */ -void Andersen::connectCaller2CalleeParams(const CallICFGNode* cs, const SVFFunction* F, NodePairSet &cpySrcNodes) -{ - assert(F); - - DBOUT(DAndersen, outs() << "connect parameters from indirect callsite " << cs.getInstruction()->toString() << " to callee " << *F << "\n"); - - const CallICFGNode* callBlockNode = cs; - const RetICFGNode* retBlockNode = cs->getRetICFGNode(); - - if(SVFUtil::isHeapAllocExtFunViaRet(F) && pag->callsiteHasRet(retBlockNode)) - { - heapAllocatorViaIndCall(cs,cpySrcNodes); - } - - if (pag->funHasRet(F) && pag->callsiteHasRet(retBlockNode)) - { - const PAGNode* cs_return = pag->getCallSiteRet(retBlockNode); - const PAGNode* fun_return = pag->getFunRet(F); - if (cs_return->isPointer() && fun_return->isPointer()) - { - NodeID dstrec = sccRepNode(cs_return->getId()); - NodeID srcret = sccRepNode(fun_return->getId()); - if(addCopyEdge(srcret, dstrec)) - { - cpySrcNodes.insert(std::make_pair(srcret,dstrec)); - } - } - else - { - DBOUT(DAndersen, outs() << "not a pointer ignored\n"); - } - } - - if (pag->hasCallSiteArgsMap(callBlockNode) && pag->hasFunArgsList(F)) - { - - // connect actual and formal param - const SVFIR::SVFVarList& csArgList = pag->getCallSiteArgsList(callBlockNode); - const SVFIR::SVFVarList& funArgList = pag->getFunArgsList(F); - //Go through the fixed parameters. - DBOUT(DPAGBuild, outs() << " args:"); - SVFIR::SVFVarList::const_iterator funArgIt = funArgList.begin(), funArgEit = funArgList.end(); - SVFIR::SVFVarList::const_iterator csArgIt = csArgList.begin(), csArgEit = csArgList.end(); - for (; funArgIt != funArgEit; ++csArgIt, ++funArgIt) - { - //Some programs (e.g. Linux kernel) leave unneeded parameters empty. - if (csArgIt == csArgEit) - { - DBOUT(DAndersen, outs() << " !! not enough args\n"); - break; - } - const PAGNode *cs_arg = *csArgIt ; - const PAGNode *fun_arg = *funArgIt; - - if (cs_arg->isPointer() && fun_arg->isPointer()) - { - DBOUT(DAndersen, outs() << "process actual parm " << cs_arg->toString() << " \n"); - NodeID srcAA = sccRepNode(cs_arg->getId()); - NodeID dstFA = sccRepNode(fun_arg->getId()); - if(addCopyEdge(srcAA, dstFA)) - { - cpySrcNodes.insert(std::make_pair(srcAA,dstFA)); - } - } - } - - //Any remaining actual args must be varargs. - if (F->isVarArg()) - { - NodeID vaF = sccRepNode(pag->getVarargNode(F)); - DBOUT(DPAGBuild, outs() << "\n varargs:"); - for (; csArgIt != csArgEit; ++csArgIt) - { - const PAGNode *cs_arg = *csArgIt; - if (cs_arg->isPointer()) - { - NodeID vnAA = sccRepNode(cs_arg->getId()); - if (addCopyEdge(vnAA,vaF)) - { - cpySrcNodes.insert(std::make_pair(vnAA,vaF)); - } - } - } - } - if(csArgIt != csArgEit) - { - writeWrnMsg("too many args to non-vararg func."); - writeWrnMsg("(" + cs->getSourceLoc() + ")"); - } - } -} - /*! * merge nodeId to newRepId. Return true if the newRepId is a PWC node */ diff --git a/svf/lib/WPA/Steensgaard.cpp b/svf/lib/WPA/Steensgaard.cpp index 3d94d7f2e..14f8f46d1 100644 --- a/svf/lib/WPA/Steensgaard.cpp +++ b/svf/lib/WPA/Steensgaard.cpp @@ -122,166 +122,4 @@ void Steensgaard::processAllAddr() pushIntoWorklist(dst); } } -} - -//bool Steensgaard::updateCallGraph(const CallSiteToFunPtrMap& callsites) -//{ -// -// double cgUpdateStart = stat->getClk(); -// -// CallEdgeMap newEdges; -// onTheFlyCallGraphSolve(callsites, newEdges); -// NodePairSet cpySrcNodes; /// nodes as a src of a generated new copy edge -// for (CallEdgeMap::iterator it = newEdges.begin(), eit = newEdges.end(); -// it != eit; ++it) -// { -// for (FunctionSet::iterator cit = it->second.begin(), -// ecit = it->second.end(); -// cit != ecit; ++cit) -// { -// connectCaller2CalleeParams(it->first, *cit, cpySrcNodes); -// } -// } -// for (NodePairSet::iterator it = cpySrcNodes.begin(), -// eit = cpySrcNodes.end(); -// it != eit; ++it) -// { -// pushIntoWorklist(it->first); -// } -// -// double cgUpdateEnd = stat->getClk(); -// timeOfUpdateCallGraph += (cgUpdateEnd - cgUpdateStart) / TIMEINTERVAL; -// -// return (!newEdges.empty()); -//} - -void Steensgaard::heapAllocatorViaIndCall(const CallICFGNode* cs, NodePairSet& cpySrcNodes) -{ - assert(cs->getCalledFunction() == nullptr && "not an indirect callsite?"); - const RetICFGNode* retBlockNode = cs->getRetICFGNode(); - const PAGNode* cs_return = pag->getCallSiteRet(retBlockNode); - NodeID srcret; - CallSite2DummyValPN::const_iterator it = callsite2DummyValPN.find(cs); - if (it != callsite2DummyValPN.end()) - { - srcret = getEC(it->second); - } - else - { - NodeID valNode = pag->addDummyValNode(); - NodeID objNode = pag->addDummyObjNode(cs->getCallSite()->getType()); - addPts(valNode, objNode); - callsite2DummyValPN.insert(std::make_pair(cs, valNode)); - consCG->addConstraintNode(new ConstraintNode(valNode), valNode); - consCG->addConstraintNode(new ConstraintNode(objNode), objNode); - srcret = valNode; - } - - NodeID dstrec = getEC(cs_return->getId()); - if (addCopyEdge(srcret, dstrec)) - cpySrcNodes.insert(std::make_pair(srcret, dstrec)); -} - -/*! - * Connect formal and actual parameters for indirect callsites - */ -void Steensgaard::connectCaller2CalleeParams(const CallICFGNode* cs, const SVFFunction* F, - NodePairSet& cpySrcNodes) -{ - assert(F); - - DBOUT(DAndersen, outs() << "connect parameters from indirect callsite " - << cs.getInstruction()->toString() << " to callee " - << *F << "\n"); - - const CallICFGNode* callBlockNode = cs; - const RetICFGNode* retBlockNode = cs->getRetICFGNode(); - - if (SVFUtil::isHeapAllocExtFunViaRet(F) && - pag->callsiteHasRet(retBlockNode)) - { - heapAllocatorViaIndCall(cs, cpySrcNodes); - } - - if (pag->funHasRet(F) && pag->callsiteHasRet(retBlockNode)) - { - const PAGNode* cs_return = pag->getCallSiteRet(retBlockNode); - const PAGNode* fun_return = pag->getFunRet(F); - if (cs_return->isPointer() && fun_return->isPointer()) - { - NodeID dstrec = getEC(cs_return->getId()); - NodeID srcret = getEC(fun_return->getId()); - if (addCopyEdge(srcret, dstrec)) - { - cpySrcNodes.insert(std::make_pair(srcret, dstrec)); - } - } - else - { - DBOUT(DAndersen, outs() << "not a pointer ignored\n"); - } - } - - if (pag->hasCallSiteArgsMap(callBlockNode) && pag->hasFunArgsList(F)) - { - - // connect actual and formal param - const SVFIR::SVFVarList& csArgList = - pag->getCallSiteArgsList(callBlockNode); - const SVFIR::SVFVarList& funArgList = pag->getFunArgsList(F); - // Go through the fixed parameters. - DBOUT(DPAGBuild, outs() << " args:"); - SVFIR::SVFVarList::const_iterator funArgIt = funArgList.begin(), - funArgEit = funArgList.end(); - SVFIR::SVFVarList::const_iterator csArgIt = csArgList.begin(), - csArgEit = csArgList.end(); - for (; funArgIt != funArgEit; ++csArgIt, ++funArgIt) - { - // Some programs (e.g. Linux kernel) leave unneeded parameters - // empty. - if (csArgIt == csArgEit) - { - DBOUT(DAndersen, outs() << " !! not enough args\n"); - break; - } - const PAGNode* cs_arg = *csArgIt; - const PAGNode* fun_arg = *funArgIt; - - if (cs_arg->isPointer() && fun_arg->isPointer()) - { - DBOUT(DAndersen, outs() << "process actual parm " - << cs_arg->toString() << " \n"); - NodeID srcAA = getEC(cs_arg->getId()); - NodeID dstFA = getEC(fun_arg->getId()); - if (addCopyEdge(srcAA, dstFA)) - { - cpySrcNodes.insert(std::make_pair(srcAA, dstFA)); - } - } - } - - // Any remaining actual args must be varargs. - if (F->isVarArg()) - { - NodeID vaF = getEC(pag->getVarargNode(F)); - DBOUT(DPAGBuild, outs() << "\n varargs:"); - for (; csArgIt != csArgEit; ++csArgIt) - { - const PAGNode* cs_arg = *csArgIt; - if (cs_arg->isPointer()) - { - NodeID vnAA = getEC(cs_arg->getId()); - if (addCopyEdge(vnAA, vaF)) - { - cpySrcNodes.insert(std::make_pair(vnAA, vaF)); - } - } - } - } - if (csArgIt != csArgEit) - { - writeWrnMsg("too many args to non-vararg func."); - writeWrnMsg("(" + cs->getSourceLoc() + ")"); - } - } -} +} \ No newline at end of file From a5f0150e1477a1b1eba26de630fd4d04c577fcb8 Mon Sep 17 00:00:00 2001 From: joelyyoung Date: Fri, 20 Sep 2024 09:17:12 +0800 Subject: [PATCH 3/7] remove getSubstitudeNode --- svf/include/WPA/Andersen.h | 5 +---- svf/include/WPA/Steensgaard.h | 14 +++++++------- svf/lib/WPA/Andersen.cpp | 16 ++++++++-------- 3 files changed, 16 insertions(+), 19 deletions(-) diff --git a/svf/include/WPA/Andersen.h b/svf/include/WPA/Andersen.h index dbec01712..b766e5f23 100644 --- a/svf/include/WPA/Andersen.h +++ b/svf/include/WPA/Andersen.h @@ -121,10 +121,6 @@ class AndersenBase: public WPAConstraintSolver, public BVDataPTAImpl { return consCG->sccRepNode(id); } - virtual inline NodeID getSubstitudeID(NodeID id) const - { - return sccRepNode(id); - } inline NodeBS& sccSubNodes(NodeID repId) { return consCG->sccSubNodes(repId); @@ -134,6 +130,7 @@ class AndersenBase: public WPAConstraintSolver, public BVDataPTAImpl /// Add copy edge on constraint graph virtual inline bool addCopyEdge(NodeID src, NodeID dst) { + assert(false && "this function should never be executed!"); return false; } diff --git a/svf/include/WPA/Steensgaard.h b/svf/include/WPA/Steensgaard.h index 17b17d9f4..87c9ca676 100644 --- a/svf/include/WPA/Steensgaard.h +++ b/svf/include/WPA/Steensgaard.h @@ -45,7 +45,7 @@ class Steensgaard : public AndersenBase steens = nullptr; } - virtual void solveWorklist(); + virtual void solveWorklist() override; void processAllAddr(); @@ -68,18 +68,18 @@ class Steensgaard : public AndersenBase //@} /// Operation of points-to set - virtual inline const PointsTo& getPts(NodeID id) + virtual inline const PointsTo& getPts(NodeID id) override { return getPTDataTy()->getPts(getEC(id)); } /// pts(id) = pts(id) U target - virtual inline bool unionPts(NodeID id, const PointsTo& target) + virtual inline bool unionPts(NodeID id, const PointsTo& target) override { id = getEC(id); return getPTDataTy()->unionPts(id, target); } /// pts(id) = pts(id) U pts(ptd) - virtual inline bool unionPts(NodeID id, NodeID ptd) + virtual inline bool unionPts(NodeID id, NodeID ptd) override { id = getEC(id); ptd = getEC(ptd); @@ -97,8 +97,8 @@ class Steensgaard : public AndersenBase else return it->second; } - /// Universal API for getting the substitude of a ConsG Node - virtual inline NodeID getSubstitudeID(NodeID id) const + /// Return getEC(id) + inline NodeID sccRepNode(NodeID id) const override { return getEC(id); } @@ -115,7 +115,7 @@ class Steensgaard : public AndersenBase } /// Add copy edge on constraint graph - virtual inline bool addCopyEdge(NodeID src, NodeID dst) + virtual inline bool addCopyEdge(NodeID src, NodeID dst) override { return consCG->addCopyCGEdge(src, dst); } diff --git a/svf/lib/WPA/Andersen.cpp b/svf/lib/WPA/Andersen.cpp index 14317c60e..791ee3a64 100644 --- a/svf/lib/WPA/Andersen.cpp +++ b/svf/lib/WPA/Andersen.cpp @@ -241,8 +241,8 @@ void AndersenBase::connectCaller2CalleeParams(const CallICFGNode* cs, const SVFF const PAGNode* fun_return = pag->getFunRet(F); if (cs_return->isPointer() && fun_return->isPointer()) { - NodeID dstrec = getSubstitudeID(cs_return->getId()); - NodeID srcret = getSubstitudeID(fun_return->getId()); + NodeID dstrec = sccRepNode(cs_return->getId()); + NodeID srcret = sccRepNode(fun_return->getId()); if(addCopyEdge(srcret, dstrec)) { cpySrcNodes.insert(std::make_pair(srcret,dstrec)); @@ -278,8 +278,8 @@ void AndersenBase::connectCaller2CalleeParams(const CallICFGNode* cs, const SVFF if (cs_arg->isPointer() && fun_arg->isPointer()) { DBOUT(DAndersen, outs() << "process actual parm " << cs_arg->toString() << " \n"); - NodeID srcAA = getSubstitudeID(cs_arg->getId()); - NodeID dstFA = getSubstitudeID(fun_arg->getId()); + NodeID srcAA = sccRepNode(cs_arg->getId()); + NodeID dstFA = sccRepNode(fun_arg->getId()); if(addCopyEdge(srcAA, dstFA)) { cpySrcNodes.insert(std::make_pair(srcAA,dstFA)); @@ -290,14 +290,14 @@ void AndersenBase::connectCaller2CalleeParams(const CallICFGNode* cs, const SVFF //Any remaining actual args must be varargs. if (F->isVarArg()) { - NodeID vaF = getSubstitudeID(pag->getVarargNode(F)); + NodeID vaF = sccRepNode(pag->getVarargNode(F)); DBOUT(DPAGBuild, outs() << "\n varargs:"); for (; csArgIt != csArgEit; ++csArgIt) { const PAGNode *cs_arg = *csArgIt; if (cs_arg->isPointer()) { - NodeID vnAA = getSubstitudeID(cs_arg->getId()); + NodeID vnAA = sccRepNode(cs_arg->getId()); if (addCopyEdge(vnAA,vaF)) { cpySrcNodes.insert(std::make_pair(vnAA,vaF)); @@ -322,7 +322,7 @@ void AndersenBase::heapAllocatorViaIndCall(const CallICFGNode* cs, NodePairSet & CallSite2DummyValPN::const_iterator it = callsite2DummyValPN.find(cs); if(it != callsite2DummyValPN.end()) { - srcret = getSubstitudeID(it->second); + srcret = sccRepNode(it->second); } else { @@ -335,7 +335,7 @@ void AndersenBase::heapAllocatorViaIndCall(const CallICFGNode* cs, NodePairSet & srcret = valNode; } - NodeID dstrec = getSubstitudeID(cs_return->getId()); + NodeID dstrec = sccRepNode(cs_return->getId()); if(addCopyEdge(srcret, dstrec)) cpySrcNodes.insert(std::make_pair(srcret,dstrec)); } From f4280bd9cac1d3431e9f8cb3a1e8ee24de46ca1d Mon Sep 17 00:00:00 2001 From: joelyyoung Date: Fri, 20 Sep 2024 09:22:51 +0800 Subject: [PATCH 4/7] change addCopyEdge to a virtual function in AndersenBase --- svf/include/WPA/Andersen.h | 6 +----- svf/include/WPA/TypeAnalysis.h | 13 ++++++++++--- 2 files changed, 11 insertions(+), 8 deletions(-) diff --git a/svf/include/WPA/Andersen.h b/svf/include/WPA/Andersen.h index b766e5f23..9a7dbfba5 100644 --- a/svf/include/WPA/Andersen.h +++ b/svf/include/WPA/Andersen.h @@ -128,11 +128,7 @@ class AndersenBase: public WPAConstraintSolver, public BVDataPTAImpl //@} /// Add copy edge on constraint graph - virtual inline bool addCopyEdge(NodeID src, NodeID dst) - { - assert(false && "this function should never be executed!"); - return false; - } + virtual inline bool addCopyEdge(NodeID src, NodeID dst) = 0; /// dump statistics inline void printStat() diff --git a/svf/include/WPA/TypeAnalysis.h b/svf/include/WPA/TypeAnalysis.h index b078b4f41..ea492fd11 100644 --- a/svf/include/WPA/TypeAnalysis.h +++ b/svf/include/WPA/TypeAnalysis.h @@ -51,13 +51,20 @@ class TypeAnalysis: public AndersenBase } /// Type analysis - void analyze(); + void analyze() override; /// Initialize analysis - void initialize(); + void initialize() override; /// Finalize analysis - virtual inline void finalize(); + virtual inline void finalize() override; + + /// Add copy edge on constraint graph + inline bool addCopyEdge(NodeID src, NodeID dst) override + { + assert(false && "this function should never be executed!"); + return false; + } /// Resolve callgraph based on CHA void callGraphSolveBasedOnCHA(const CallSiteToFunPtrMap& callsites, CallEdgeMap& newEdges); From c4d70ac021f0e8729f1edeecd1510c175c9e95ad Mon Sep 17 00:00:00 2001 From: joelyyoung Date: Fri, 20 Sep 2024 16:22:18 +0800 Subject: [PATCH 5/7] implement on the fly pta respecting forksite --- svf-llvm/lib/SVFIRExtAPI.cpp | 3 +- svf/include/Graphs/ThreadCallGraph.h | 15 +++- svf/include/MemoryModel/PointerAnalysis.h | 2 +- svf/include/Util/SVFUtil.h | 2 +- svf/include/Util/ThreadAPI.h | 10 ++- svf/include/WPA/Andersen.h | 15 +++- svf/lib/Graphs/ThreadCallGraph.cpp | 2 + svf/lib/Util/ThreadAPI.cpp | 20 +++-- svf/lib/WPA/Andersen.cpp | 98 ++++++++++++++++++++++- 9 files changed, 151 insertions(+), 16 deletions(-) diff --git a/svf-llvm/lib/SVFIRExtAPI.cpp b/svf-llvm/lib/SVFIRExtAPI.cpp index ff4a66026..7ccdd2d03 100644 --- a/svf-llvm/lib/SVFIRExtAPI.cpp +++ b/svf-llvm/lib/SVFIRExtAPI.cpp @@ -259,7 +259,8 @@ void SVFIRBuilder::handleExtCall(const CallBase* cs, const SVFFunction* svfCalle if (const SVFFunction* forkedFun = SVFUtil::dyn_cast(getForkedFun(callICFGNode))) { forkedFun = forkedFun->getDefFunForMultipleModule(); - const SVFValue* actualParm = getActualParmAtForkSite(callICFGNode); + const SVFVar* actualParmVar = getActualParmAtForkSite(callICFGNode); + const SVFValue* actualParm = actualParmVar->getValue(); /// pthread_create has 1 arg. /// apr_thread_create has 2 arg. assert((forkedFun->arg_size() <= 2) && "Size of formal parameter of start routine should be one"); diff --git a/svf/include/Graphs/ThreadCallGraph.h b/svf/include/Graphs/ThreadCallGraph.h index 529a9db3e..29bab5a06 100644 --- a/svf/include/Graphs/ThreadCallGraph.h +++ b/svf/include/Graphs/ThreadCallGraph.h @@ -31,13 +31,13 @@ #define RCG_H_ #include "Graphs/CallGraph.h" -#include "MemoryModel/PointerAnalysisImpl.h" namespace SVF { class SVFModule; class ThreadAPI; +class PointerAnalysis; /*! * PTA thread fork edge from fork site to the entry of a start routine function */ @@ -201,7 +201,8 @@ class ThreadCallGraph: public CallGraph /// whether this call instruction has a valid call graph edge inline bool hasThreadForkEdge(const CallICFGNode* cs) const { - return callinstToThreadForkEdgesMap.find(cs) != callinstToThreadForkEdgesMap.end(); + return callinstToThreadForkEdgesMap.find(cs) != + callinstToThreadForkEdgesMap.end(); } inline ForkEdgeSet::const_iterator getForkEdgeBegin(const CallICFGNode* cs) const { @@ -250,6 +251,14 @@ class ThreadCallGraph: public CallGraph } //@} + /// Get callees from an indirect callsite + ///@{ + inline CallEdgeMap& getIndForkMap() + { + return indirectForkMap; + } + //@} + /// Whether a callsite is a fork or join or hare_parallel_for ///@{ inline bool isForksite(const CallICFGNode* csInst) @@ -407,6 +416,8 @@ class ThreadCallGraph: public CallGraph CallInstToForkEdgesMap callinstToThreadForkEdgesMap; ///< Map a call instruction to its corresponding fork edges CallInstToJoinEdgesMap callinstToThreadJoinEdgesMap; ///< Map a call instruction to its corresponding join edges CallInstToParForEdgesMap callinstToHareParForEdgesMap; ///< Map a call instruction to its corresponding hare_parallel_for edges + + CallEdgeMap indirectForkMap; ///< Indirect call map }; } // End namespace SVF diff --git a/svf/include/MemoryModel/PointerAnalysis.h b/svf/include/MemoryModel/PointerAnalysis.h index fd5123edc..535be9878 100644 --- a/svf/include/MemoryModel/PointerAnalysis.h +++ b/svf/include/MemoryModel/PointerAnalysis.h @@ -34,7 +34,7 @@ #include #include "Graphs/CHG.h" -#include "Graphs/CallGraph.h" +#include "Graphs/ThreadCallGraph.h" #include "Graphs/SCC.h" #include "MemoryModel/AbstractPointsToDS.h" #include "MemoryModel/ConditionalPT.h" diff --git a/svf/include/Util/SVFUtil.h b/svf/include/Util/SVFUtil.h index 15c9f829b..541547299 100644 --- a/svf/include/Util/SVFUtil.h +++ b/svf/include/Util/SVFUtil.h @@ -457,7 +457,7 @@ inline bool isBarrierWaitCall(const CallICFGNode* cs) /// Return sole argument of the thread routine //@{ -inline const SVFValue* getActualParmAtForkSite(const CallICFGNode* cs) +inline const SVFVar* getActualParmAtForkSite(const CallICFGNode* cs) { return ThreadAPI::getThreadAPI()->getActualParmAtForkSite(cs); } diff --git a/svf/include/Util/ThreadAPI.h b/svf/include/Util/ThreadAPI.h index 592ed4bbf..e75681d4c 100644 --- a/svf/include/Util/ThreadAPI.h +++ b/svf/include/Util/ThreadAPI.h @@ -38,6 +38,7 @@ namespace SVF class SVFModule; class ICFGNode; class CallICFGNode; +class SVFVar; /* * ThreadAPI class contains interfaces for pthread programs @@ -128,11 +129,16 @@ class ThreadAPI /// Note that, it could be function type or a void* pointer const SVFValue* getForkedFun(const CallICFGNode *inst) const; - /// Return the forth argument of the call, + /// Return the actual param of forksite /// Note that, it is the sole argument of start routine ( a void* pointer ) - const SVFValue* getActualParmAtForkSite(const CallICFGNode *inst) const; + const SVFVar* getActualParmAtForkSite(const CallICFGNode *inst) const; + + /// Return the formal parm of forked function (the first arg in pthread) + const SVFVar* getFormalParmOfForkedFun(const SVFFunction* F) const; //@} + + /// Return true if this call create a new thread //@{ bool isTDFork(const CallICFGNode *inst) const; diff --git a/svf/include/WPA/Andersen.h b/svf/include/WPA/Andersen.h index 9a7dbfba5..6e0ca08d3 100644 --- a/svf/include/WPA/Andersen.h +++ b/svf/include/WPA/Andersen.h @@ -47,6 +47,8 @@ namespace SVF class SVFModule; +class ThreadCallGraph; + /*! * Abstract class of inclusion-based Pointer Analysis */ @@ -84,13 +86,24 @@ class AndersenBase: public WPAConstraintSolver, public BVDataPTAImpl /// Finalize analysis virtual void finalize() override; - /// Implement it in child class to update call graph + /// Update call graph virtual bool updateCallGraph(const CallSiteToFunPtrMap&) override; + /// Update thread call graph + virtual bool updateThreadCallGraph(const CallSiteToFunPtrMap&, NodePairSet&); + + /// Connect formal and actual parameters for indirect forksites + virtual void connectCaller2ForkedFunParams(const CallICFGNode* cs, const SVFFunction* F, + NodePairSet& cpySrcNodes); + /// Connect formal and actual parameters for indirect callsites virtual void connectCaller2CalleeParams(const CallICFGNode* cs, const SVFFunction* F, NodePairSet& cpySrcNodes); + /// On the fly thread call graph construction respecting forksite + virtual void onTheFlyThreadCallGraphSolve(const CallSiteToFunPtrMap& callsites, + CallEdgeMap& newForkEdges); + /// Methods for support type inquiry through isa, cast, and dyn_cast: //@{ static inline bool classof(const AndersenBase *) diff --git a/svf/lib/Graphs/ThreadCallGraph.cpp b/svf/lib/Graphs/ThreadCallGraph.cpp index c04b90412..eed4a285f 100644 --- a/svf/lib/Graphs/ThreadCallGraph.cpp +++ b/svf/lib/Graphs/ThreadCallGraph.cpp @@ -30,6 +30,8 @@ #include "SVFIR/SVFModule.h" #include "Graphs/ThreadCallGraph.h" #include "Util/ThreadAPI.h" +#include "SVFIR/SVFIR.h" +#include "MemoryModel/PointerAnalysisImpl.h" using namespace SVF; using namespace SVFUtil; diff --git a/svf/lib/Util/ThreadAPI.cpp b/svf/lib/Util/ThreadAPI.cpp index 766243d56..61d75e17a 100644 --- a/svf/lib/Util/ThreadAPI.cpp +++ b/svf/lib/Util/ThreadAPI.cpp @@ -172,12 +172,22 @@ const SVFValue* ThreadAPI::getForkedFun(const CallICFGNode *inst) const return inst->getArgument(2); } -/// Return the forth argument of the call, -/// Note that, it is the sole argument of start routine ( a void* pointer ) -const SVFValue* ThreadAPI::getActualParmAtForkSite(const CallICFGNode *inst) const +const SVFVar* ThreadAPI::getActualParmAtForkSite(const CallICFGNode* inst) const { - assert(isTDFork(inst) && "not a thread fork function!"); - return inst->getArgument(3); + assert(PAG::getPAG()->hasCallSiteArgsMap(inst) && "forksite has no args list!"); + const SVFIR::SVFVarList& csArgList = PAG::getPAG()->getCallSiteArgsList(inst); + // pthread_create has 4 parameters + assert(csArgList.size() == 4 && "num of forksite args is not 4"); + return csArgList[3]; +} + +const SVFVar* ThreadAPI::getFormalParmOfForkedFun(const SVFFunction* F) const +{ + assert(PAG::getPAG()->hasFunArgsList(F) && "forked function has no args list!"); + const SVFIR::SVFVarList& funArgList = PAG::getPAG()->getFunArgsList(F); + // in pthread, forked functions are of type void *()(void *args) + assert(funArgList.size() == 1 && "num of pthread forked function args is not 1!"); + return funArgList[0]; } const SVFValue* ThreadAPI::getRetParmAtJoinedSite(const CallICFGNode *inst) const diff --git a/svf/lib/WPA/Andersen.cpp b/svf/lib/WPA/Andersen.cpp index 791ee3a64..b0d96161c 100644 --- a/svf/lib/WPA/Andersen.cpp +++ b/svf/lib/WPA/Andersen.cpp @@ -205,6 +205,9 @@ bool AndersenBase::updateCallGraph(const CallSiteToFunPtrMap& callsites) connectCaller2CalleeParams(it->first, *cit, cpySrcNodes); } } + + bool hasNewForkEdges = updateThreadCallGraph(callsites, cpySrcNodes); + for (NodePairSet::iterator it = cpySrcNodes.begin(), eit = cpySrcNodes.end(); it != eit; ++it) @@ -215,17 +218,65 @@ bool AndersenBase::updateCallGraph(const CallSiteToFunPtrMap& callsites) double cgUpdateEnd = stat->getClk(); timeOfUpdateCallGraph += (cgUpdateEnd - cgUpdateStart) / TIMEINTERVAL; - return (!newEdges.empty()); + return ((!newEdges.empty()) || hasNewForkEdges); +} + +bool AndersenBase::updateThreadCallGraph(const CallSiteToFunPtrMap& callsites, + NodePairSet& cpySrcNodes) +{ + CallEdgeMap newForkEdges; + onTheFlyThreadCallGraphSolve(callsites, newForkEdges); + for (CallEdgeMap::iterator it = newForkEdges.begin(), eit = newForkEdges.end(); it != eit; it++){ + for (FunctionSet::iterator cit = it->second.begin(), + ecit = it->second.end(); + cit != ecit; ++cit) + { + connectCaller2ForkedFunParams(it->first, *cit, cpySrcNodes); + } + } + return !newForkEdges.empty(); +} + +/*! + * Connect formal and actual parameters for indirect forksites + */ +void AndersenBase::connectCaller2ForkedFunParams(const CallICFGNode* cs, const SVFFunction* F, + NodePairSet& cpySrcNodes) +{ + assert(F); + + DBOUT(DAndersen, outs() << "connect parameters from indirect forksite " + << cs.getInstruction()->toString() << " to forked function " + << *F << "\n"); + + ThreadCallGraph *tdCallGraph = SVFUtil::dyn_cast(callgraph); + + const PAGNode *cs_arg = tdCallGraph->getThreadAPI()->getActualParmAtForkSite(cs); + const PAGNode *fun_arg = tdCallGraph->getThreadAPI()->getFormalParmOfForkedFun(F); + + if(cs_arg->isPointer() && fun_arg->isPointer()) + { + DBOUT(DAndersen, outs() << "process actual parm" + << cs_arg->toString() << "\n"); + NodeID srcAA = sccRepNode(cs_arg->getId()); + NodeID dstFA = sccRepNode(fun_arg->getId()); + if (addCopyEdge(srcAA, dstFA)) + { + cpySrcNodes.insert(std::make_pair(srcAA, dstFA)); + } + } } ///*! // * Connect formal and actual parameters for indirect callsites // */ -void AndersenBase::connectCaller2CalleeParams(const CallICFGNode* cs, const SVFFunction* F, NodePairSet &cpySrcNodes) +void AndersenBase::connectCaller2CalleeParams(const CallICFGNode* cs, + const SVFFunction* F, NodePairSet &cpySrcNodes) { assert(F); - DBOUT(DAndersen, outs() << "connect parameters from indirect callsite " << cs.getInstruction()->toString() << " to callee " << *F << "\n"); + DBOUT(DAndersen, outs() << "connect parameters from indirect callsite " << + cs.getInstruction()->toString() << " to callee " << *F << "\n"); const CallICFGNode* callBlockNode = cs; const RetICFGNode* retBlockNode = cs->getRetICFGNode(); @@ -313,6 +364,47 @@ void AndersenBase::connectCaller2CalleeParams(const CallICFGNode* cs, const SVFF } } +/*! + * On the fly call graph construction respecting forksite + * callsites is candidate indirect callsites need to be analyzed based on points-to results + * newEdges is the new indirect call edges discovered + */ +void AndersenBase::onTheFlyThreadCallGraphSolve(const CallSiteToFunPtrMap& callsites, + CallEdgeMap& newForkEdges) +{ + // add indirect fork edges + if(ThreadCallGraph *tdCallGraph = SVFUtil::dyn_cast(callgraph)) + { + for(CallSiteSet::const_iterator it = tdCallGraph->forksitesBegin(), + eit = tdCallGraph->forksitesEnd(); it != eit; ++it) + { + const SVFValue* forkedVal =tdCallGraph->getThreadAPI()->getForkedFun(*it); + if(SVFUtil::dyn_cast(forkedVal) == nullptr) + { + SVFIR *pag = this->getPAG(); + const NodeBS targets = this->getPts(pag->getValueNode(forkedVal)).toNodeBS(); + for(NodeBS::iterator ii = targets.begin(), ie = targets.end(); ii != ie; ++ii) + { + if(ObjVar *objPN = SVFUtil::dyn_cast(pag->getGNode(*ii))) + { + const MemObj *obj = pag->getObject(objPN); + if(obj->isFunction()) + { + const SVFFunction *svfForkedFun = SVFUtil::cast(obj->getValue()); + if(tdCallGraph->getIndForkMap()[*it].count(svfForkedFun) == 0) + { + tdCallGraph->addIndirectForkEdge(*it, svfForkedFun); + newForkEdges[*it].insert(svfForkedFun); + tdCallGraph->getIndForkMap()[*it].insert(svfForkedFun); + } + } + } + } + } + } + } +} + void AndersenBase::heapAllocatorViaIndCall(const CallICFGNode* cs, NodePairSet &cpySrcNodes) { assert(cs->getCalledFunction() == nullptr && "not an indirect callsite?"); From 3037f6bd3ad32363715d3dbb945e461b70732068 Mon Sep 17 00:00:00 2001 From: joelyyoung Date: Fri, 20 Sep 2024 18:16:06 +0800 Subject: [PATCH 6/7] remove indForkEdgeMap --- svf/include/Graphs/ThreadCallGraph.h | 14 +------ svf/include/MemoryModel/PointerAnalysisImpl.h | 4 ++ svf/include/WPA/Andersen.h | 4 -- svf/lib/Graphs/ThreadCallGraph.cpp | 12 ++++-- svf/lib/MemoryModel/PointerAnalysisImpl.cpp | 37 +++++++++++++++++ svf/lib/WPA/Andersen.cpp | 41 ------------------- 6 files changed, 51 insertions(+), 61 deletions(-) diff --git a/svf/include/Graphs/ThreadCallGraph.h b/svf/include/Graphs/ThreadCallGraph.h index 29bab5a06..ace02fb44 100644 --- a/svf/include/Graphs/ThreadCallGraph.h +++ b/svf/include/Graphs/ThreadCallGraph.h @@ -251,14 +251,6 @@ class ThreadCallGraph: public CallGraph } //@} - /// Get callees from an indirect callsite - ///@{ - inline CallEdgeMap& getIndForkMap() - { - return indirectForkMap; - } - //@} - /// Whether a callsite is a fork or join or hare_parallel_for ///@{ inline bool isForksite(const CallICFGNode* csInst) @@ -354,8 +346,8 @@ class ThreadCallGraph: public CallGraph /// Add direct/indirect thread fork edges //@{ - void addDirectForkEdge(const CallICFGNode* cs); - void addIndirectForkEdge(const CallICFGNode* cs, const SVFFunction* callee); + bool addDirectForkEdge(const CallICFGNode* cs); + bool addIndirectForkEdge(const CallICFGNode* cs, const SVFFunction* callee); //@} /// Add thread join edges @@ -416,8 +408,6 @@ class ThreadCallGraph: public CallGraph CallInstToForkEdgesMap callinstToThreadForkEdgesMap; ///< Map a call instruction to its corresponding fork edges CallInstToJoinEdgesMap callinstToThreadJoinEdgesMap; ///< Map a call instruction to its corresponding join edges CallInstToParForEdgesMap callinstToHareParForEdgesMap; ///< Map a call instruction to its corresponding hare_parallel_for edges - - CallEdgeMap indirectForkMap; ///< Indirect call map }; } // End namespace SVF diff --git a/svf/include/MemoryModel/PointerAnalysisImpl.h b/svf/include/MemoryModel/PointerAnalysisImpl.h index 00d1a0b5c..43c0ff472 100644 --- a/svf/include/MemoryModel/PointerAnalysisImpl.h +++ b/svf/include/MemoryModel/PointerAnalysisImpl.h @@ -199,6 +199,10 @@ class BVDataPTAImpl : public PointerAnalysis /// On the fly call graph construction virtual void onTheFlyCallGraphSolve(const CallSiteToFunPtrMap& callsites, CallEdgeMap& newEdges); + /// On the fly thread call graph construction respecting forksite + virtual void onTheFlyThreadCallGraphSolve(const CallSiteToFunPtrMap& callsites, + CallEdgeMap& newForkEdges); + /// Normalize points-to information for field-sensitive analysis, /// i.e., replace fieldObj with baseObj if it is field-insensitive virtual void normalizePointsTo(); diff --git a/svf/include/WPA/Andersen.h b/svf/include/WPA/Andersen.h index 6e0ca08d3..5daf1abd6 100644 --- a/svf/include/WPA/Andersen.h +++ b/svf/include/WPA/Andersen.h @@ -100,10 +100,6 @@ class AndersenBase: public WPAConstraintSolver, public BVDataPTAImpl virtual void connectCaller2CalleeParams(const CallICFGNode* cs, const SVFFunction* F, NodePairSet& cpySrcNodes); - /// On the fly thread call graph construction respecting forksite - virtual void onTheFlyThreadCallGraphSolve(const CallSiteToFunPtrMap& callsites, - CallEdgeMap& newForkEdges); - /// Methods for support type inquiry through isa, cast, and dyn_cast: //@{ static inline bool classof(const AndersenBase *) diff --git a/svf/lib/Graphs/ThreadCallGraph.cpp b/svf/lib/Graphs/ThreadCallGraph.cpp index eed4a285f..aa5b3a8d4 100644 --- a/svf/lib/Graphs/ThreadCallGraph.cpp +++ b/svf/lib/Graphs/ThreadCallGraph.cpp @@ -121,7 +121,7 @@ void ThreadCallGraph::updateJoinEdge(PointerAnalysis* pta) /*! * Add direct fork edges */ -void ThreadCallGraph::addDirectForkEdge(const CallICFGNode* cs) +bool ThreadCallGraph::addDirectForkEdge(const CallICFGNode* cs) { CallGraphNode* caller = getCallGraphNode(cs->getCaller()); @@ -139,13 +139,15 @@ void ThreadCallGraph::addDirectForkEdge(const CallICFGNode* cs) addEdge(edge); addThreadForkEdgeSetMap(cs, edge); - } + return true; + }else + return false; } /*! * Add indirect fork edge to update call graph */ -void ThreadCallGraph::addIndirectForkEdge(const CallICFGNode* cs, const SVFFunction* calleefun) +bool ThreadCallGraph::addIndirectForkEdge(const CallICFGNode* cs, const SVFFunction* calleefun) { CallGraphNode* caller = getCallGraphNode(cs->getCaller()); CallGraphNode* callee = getCallGraphNode(calleefun); @@ -161,7 +163,9 @@ void ThreadCallGraph::addIndirectForkEdge(const CallICFGNode* cs, const SVFFunct addEdge(edge); addThreadForkEdgeSetMap(cs, edge); - } + return true; + }else + return false; } /*! diff --git a/svf/lib/MemoryModel/PointerAnalysisImpl.cpp b/svf/lib/MemoryModel/PointerAnalysisImpl.cpp index 5346dfce9..3a1efb7e7 100644 --- a/svf/lib/MemoryModel/PointerAnalysisImpl.cpp +++ b/svf/lib/MemoryModel/PointerAnalysisImpl.cpp @@ -507,6 +507,43 @@ void BVDataPTAImpl::onTheFlyCallGraphSolve(const CallSiteToFunPtrMap& callsites, } } +/*! + * On the fly call graph construction respecting forksite + * callsites is candidate indirect callsites need to be analyzed based on points-to results + * newEdges is the new indirect call edges discovered + */ +void BVDataPTAImpl::onTheFlyThreadCallGraphSolve(const CallSiteToFunPtrMap& callsites, + CallEdgeMap& newForkEdges) +{ + // add indirect fork edges + if(ThreadCallGraph *tdCallGraph = SVFUtil::dyn_cast(callgraph)) + { + for(CallSiteSet::const_iterator it = tdCallGraph->forksitesBegin(), + eit = tdCallGraph->forksitesEnd(); it != eit; ++it) + { + const SVFValue* forkedVal =tdCallGraph->getThreadAPI()->getForkedFun(*it); + if(SVFUtil::dyn_cast(forkedVal) == nullptr) + { + SVFIR *pag = this->getPAG(); + const NodeBS targets = this->getPts(pag->getValueNode(forkedVal)).toNodeBS(); + for(NodeBS::iterator ii = targets.begin(), ie = targets.end(); ii != ie; ++ii) + { + if(ObjVar *objPN = SVFUtil::dyn_cast(pag->getGNode(*ii))) + { + const MemObj *obj = pag->getObject(objPN); + if(obj->isFunction()) + { + const SVFFunction *svfForkedFun = SVFUtil::cast(obj->getValue()); + if(tdCallGraph->addIndirectForkEdge(*it, svfForkedFun)) + newForkEdges[*it].insert(svfForkedFun); + } + } + } + } + } + } +} + /*! * Normalize points-to information for field-sensitive analysis */ diff --git a/svf/lib/WPA/Andersen.cpp b/svf/lib/WPA/Andersen.cpp index b0d96161c..fb987be5a 100644 --- a/svf/lib/WPA/Andersen.cpp +++ b/svf/lib/WPA/Andersen.cpp @@ -364,47 +364,6 @@ void AndersenBase::connectCaller2CalleeParams(const CallICFGNode* cs, } } -/*! - * On the fly call graph construction respecting forksite - * callsites is candidate indirect callsites need to be analyzed based on points-to results - * newEdges is the new indirect call edges discovered - */ -void AndersenBase::onTheFlyThreadCallGraphSolve(const CallSiteToFunPtrMap& callsites, - CallEdgeMap& newForkEdges) -{ - // add indirect fork edges - if(ThreadCallGraph *tdCallGraph = SVFUtil::dyn_cast(callgraph)) - { - for(CallSiteSet::const_iterator it = tdCallGraph->forksitesBegin(), - eit = tdCallGraph->forksitesEnd(); it != eit; ++it) - { - const SVFValue* forkedVal =tdCallGraph->getThreadAPI()->getForkedFun(*it); - if(SVFUtil::dyn_cast(forkedVal) == nullptr) - { - SVFIR *pag = this->getPAG(); - const NodeBS targets = this->getPts(pag->getValueNode(forkedVal)).toNodeBS(); - for(NodeBS::iterator ii = targets.begin(), ie = targets.end(); ii != ie; ++ii) - { - if(ObjVar *objPN = SVFUtil::dyn_cast(pag->getGNode(*ii))) - { - const MemObj *obj = pag->getObject(objPN); - if(obj->isFunction()) - { - const SVFFunction *svfForkedFun = SVFUtil::cast(obj->getValue()); - if(tdCallGraph->getIndForkMap()[*it].count(svfForkedFun) == 0) - { - tdCallGraph->addIndirectForkEdge(*it, svfForkedFun); - newForkEdges[*it].insert(svfForkedFun); - tdCallGraph->getIndForkMap()[*it].insert(svfForkedFun); - } - } - } - } - } - } - } -} - void AndersenBase::heapAllocatorViaIndCall(const CallICFGNode* cs, NodePairSet &cpySrcNodes) { assert(cs->getCalledFunction() == nullptr && "not an indirect callsite?"); From ee956ea4623497fd2d98aaced3933b01c094b89c Mon Sep 17 00:00:00 2001 From: joelyyoung Date: Fri, 20 Sep 2024 18:22:27 +0800 Subject: [PATCH 7/7] change SVFValue to SVFVar in SVFIRExtAPI --- svf-llvm/lib/SVFIRExtAPI.cpp | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) diff --git a/svf-llvm/lib/SVFIRExtAPI.cpp b/svf-llvm/lib/SVFIRExtAPI.cpp index 7ccdd2d03..78163791f 100644 --- a/svf-llvm/lib/SVFIRExtAPI.cpp +++ b/svf-llvm/lib/SVFIRExtAPI.cpp @@ -259,8 +259,7 @@ void SVFIRBuilder::handleExtCall(const CallBase* cs, const SVFFunction* svfCalle if (const SVFFunction* forkedFun = SVFUtil::dyn_cast(getForkedFun(callICFGNode))) { forkedFun = forkedFun->getDefFunForMultipleModule(); - const SVFVar* actualParmVar = getActualParmAtForkSite(callICFGNode); - const SVFValue* actualParm = actualParmVar->getValue(); + const SVFVar* actualParm = getActualParmAtForkSite(callICFGNode); /// pthread_create has 1 arg. /// apr_thread_create has 2 arg. assert((forkedFun->arg_size() <= 2) && "Size of formal parameter of start routine should be one"); @@ -268,10 +267,10 @@ void SVFIRBuilder::handleExtCall(const CallBase* cs, const SVFFunction* svfCalle { const SVFArgument* formalParm = forkedFun->getArg(0); /// Connect actual parameter to formal parameter of the start routine - if (actualParm->getType()->isPointerTy() && formalParm->getType()->isPointerTy()) + if (actualParm->isPointer() && formalParm->getType()->isPointerTy()) { FunEntryICFGNode *entry = pag->getICFG()->getFunEntryICFGNode(forkedFun); - addThreadForkEdge(pag->getValueNode(actualParm), pag->getValueNode(formalParm), callICFGNode, entry); + addThreadForkEdge(actualParm->getId(), pag->getValueNode(formalParm), callICFGNode, entry); } } }