8000 Refactor pta by JoelYYoung · Pull Request #1552 · SVF-tools/SVF · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Refactor pta #1552

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 8 commits into from
Sep 20, 2024
Merged

Refactor pta #1552

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
8 commits
Select commit Hold shift + click to select a range
b75eea5
move updateCallGraph to AndersenBase
JoelYYoung Sep 19, 2024
4ed53eb
move connectCaller2CalleeParams to AndersenBase
JoelYYoung Sep 19, 2024
34f960f
Merge branch 'master' of https://github.com/SVF-tools/SVF
JoelYYoung Sep 19, 2024
a5f0150
remove getSubstitudeNode
JoelYYoung Sep 20, 2024
f4280bd
change addCopyEdge to a virtual function in AndersenBase
JoelYYoung Sep 20, 2024
c4d70ac
implement on the fly pta respecting forksite
JoelYYoung Sep 20, 2024
3037f6b
remove indForkEdgeMap
JoelYYoung Sep 20, 2024
ee956ea
change SVFValue to SVFVar in SVFIRExtAPI
JoelYYoung Sep 20, 2024
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
6 changes: 3 additions & 3 deletions svf-llvm/lib/SVFIRExtAPI.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -259,18 +259,18 @@ void SVFIRBuilder::handleExtCall(const CallBase* cs, const SVFFunction* svfCalle
if (const SVFFunction* forkedFun = SVFUtil::dyn_cast<SVFFunction>(getForkedFun(callICFGNode)))
{
forkedFun = forkedFun->getDefFunForMultipleModule();
const SVFValue* actualParm = getActualParmAtForkSite(callICFGNode);
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");
if (forkedFun->arg_size() <= 2 && forkedFun->arg_size() >= 1)
{
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);
}
}
}
Expand Down
9 changes: 5 additions & 4 deletions svf/include/Graphs/ThreadCallGraph.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -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
*/
Expand Down Expand Up @@ -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
{
Expand Down Expand Up @@ -345,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
Expand Down
2 changes: 1 addition & 1 deletion svf/include/MemoryModel/PointerAnalysis.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -34,7 +34,7 @@
#include <signal.h>

#include "Graphs/CHG.h"
#include "Graphs/CallGraph.h"
#include "Graphs/ThreadCallGraph.h"
#include "Graphs/SCC.h"
#include "MemoryModel/AbstractPointsToDS.h"
#include "MemoryModel/ConditionalPT.h"
Expand Down
4 changes: 4 additions & 0 deletions svf/include/MemoryModel/PointerAnalysisImpl.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -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,
8000 CallEdgeMap& newForkEdges);

/// Normalize points-to information for field-sensitive analysis,
/// i.e., replace fieldObj with baseObj if it is field-insensitive
virtual void normalizePointsTo();
Expand Down
2 changes: 1 addition & 1 deletion svf/include/Util/SVFUtil.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -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);
}
Expand Down
10 changes: 8 additions & 2 deletions svf/include/Util/ThreadAPI.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -38,6 +38,7 @@ namespace SVF
class SVFModule;
class ICFGNode;
class CallICFGNode;
class SVFVar;

/*
* ThreadAPI class contains interfaces for pthread programs
Expand Down Expand Up @@ -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;
Expand Down
39 changes: 26 additions & 13 deletions svf/include/WPA/Andersen.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -47,13 +47,18 @@ namespace SVF

class SVFModule;

class ThreadCallGraph;

/*!
* Abstract class of inclusion-based Pointer Analysis
*/
typedef WPASolver<ConstraintGraph*> WPAConstraintSolver;

class AndersenBase: public WPAConstraintSolver, public BVDataPTAImpl
{
public:
typedef OrderedMap<const CallICFGNode*, NodeID> CallSite2DummyValPN;

public:

/// Constructor
Expand Down Expand Up @@ -81,11 +86,19 @@ class AndersenBase: public WPAConstraintSolver, public BVDataPTAImpl
/// Finalize analysis
virtual void finalize() override;

/// Implement it in child class to update call graph
virtual inline bool updateCallGraph(const CallSiteToFunPtrMap&) override
{
return false;
}
/// 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);

/// Methods for support type inquiry through isa, cast, and dyn_cast:
//@{
Expand Down Expand Up @@ -123,6 +136,9 @@ class AndersenBase: public WPAConstraintSolver, public BVDataPTAImpl
}
//@}

/// Add copy edge on constraint graph
virtual inline bool addCopyEdge(NodeID src, NodeID dst) = 0;

/// dump statistics
inline void printStat()
{
Expand Down Expand Up @@ -160,6 +176,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);
};

/*!
Expand All @@ -171,7 +192,6 @@ class Andersen: public AndersenBase

public:
typedef SCCDetection<ConstraintGraph*> CGSCC;
typedef OrderedMap<const CallICFGNode*, NodeID> CallSite2DummyValPN;

/// Constructor
Andersen(SVFIR* _pag, PTATY type = Andersen_WPA, bool alias_check = true)
Expand Down Expand Up @@ -243,7 +263,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)
Expand Down Expand Up @@ -311,12 +330,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);

Expand Down
30 changes: 10 additions & 20 deletions svf/include/WPA/Steensgaard.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -23,7 +23,6 @@
public:
typedef Map<NodeID, NodeID> NodeToEquivClassMap;
typedef Map<NodeID, Set<NodeID>> NodeToSubsMap;
typedef OrderedMap<const CallICFGNode*, NodeID> CallSite2DummyValPN;

/// Constructor
Steensgaard(SVFIR* _pag) : AndersenBase(_pag, Steensgaard_WPA, true) {}
Expand All @@ -46,7 +45,7 @@
steens = nullptr;
}

virtual void solveWorklist();
virtual void solveWorklist() override;

void processAllAddr();

Expand All @@ -69,18 +68,18 @@
//@}

/// Operation of points-to set
virtual inline const PointsTo& getPts(NodeID id)
virtual inline const PointsTo& getPts(NodeID id) override

Check warning on line 71 in svf/include/WPA/Steensgaard.h

View check run for this annotation

Codecov / codecov/patch

svf/include/WPA/Steensgaard.h#L71 

Added line #L71 was not covered by tests
{
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

Check warning on line 76 in svf/include/WPA/Steensgaard.h

View check run for this annotation

Codecov / codecov/patch

svf/include/WPA/Steensgaard.h#L76 

Added line #L76 was not covered by tests
{
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

Check warning on line 82 in svf/include/WPA/Steensgaard.h

View check run for this annotation

Codecov / codecov/patch

svf/include/WPA/Steensgaard.h#L82 

Added line #L82 was not covered by tests
{
id = getEC(id);
ptd = getEC(ptd);
Expand All @@ -98,6 +97,11 @@
else
return it->second;
}
/// Return getEC(id)
inline NodeID sccRepNode(NodeID id) const override

Check warning on line 101 in svf/include/WPA/Steensgaard.h

View check run for this annotation

Codecov / codecov/patch

svf/include/WPA/Steensgaard.h#L101 

Added line #L101 was not covered by tests
{
return getEC(id);

Check warning on line 103 in svf/include/WPA/Steensgaard.h

View check run for this annotation

Codecov / codecov/patch

svf/include/WPA/Steensgaard.h#L103 

Added line #L103 was not covered by tests
}
void setEC(NodeID node, NodeID rep);

inline Set<NodeID>& getSubNodes(NodeID id)
Expand All @@ -111,25 +115,11 @@
}

/// Add copy edge on constraint graph
virtual inline bool addCopyEdge(NodeID src, NodeID dst)
virtual inline bool addCopyEdge(NodeID src, NodeID dst) override

Check warning on line 118 in svf/include/WPA/Steensgaard.h

View check run for this annotation

Codecov / codecov/patch

svf/include/WPA/Steensgaard.h#L118 

Added line #L118 was not covered by tests
{
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;
Expand Down
13 changes: 10 additions & 3 deletions svf/include/WPA/TypeAnalysis.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -51,13 +51,20 @@
}

/// 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

Check warning on line 63 in svf/include/WPA/TypeAnalysis.h

View check run for this annotation

Codecov / codecov/patch

svf/include/WPA/TypeAnalysis.h#L63 

Added line #L63 was not covered by tests
{
assert(false && "this function should never be executed!");

Check warning on line 65 in svf/include/WPA/TypeAnalysis.h

View check run for this annotation

Codecov / codecov/patch

svf/include/WPA/TypeAnalysis.h#L65 

Added line #L65 was not covered by tests
return false;
}

/// Resolve callgraph based on CHA
void callGraphSolveBasedOnCHA(const CallSiteToFunPtrMap& callsites, CallEdgeMap& newEdges);
Expand Down
14 changes: 10 additions & 4 deletions svf/lib/Graphs/ThreadCallGraph.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -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;
Expand Down Expand Up @@ -119,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());
Expand All @@ -137,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);
Expand All @@ -159,7 +163,9 @@ void ThreadCallGraph::addIndirectForkEdge(const CallICFGNode* cs, const SVFFunct

addEdge(edge);
addThreadForkEdgeSetMap(cs, edge);
}
return true;
}else
return false;
}

/*!
Expand Down
Loading
Loading
0