SVF::AndersenStat Class Reference

#include <WPAStat.h>

Inheritance diagram for SVF::AndersenStat:

Public Member Functions
	AndersenStat (AndersenBase *p)
virtual	~AndersenStat ()
virtual void	performStat ()
void	collectCycleInfo (ConstraintGraph *consCG)
void	statNullPtr ()
void	constraintGraphStat ()
Public Member Functions inherited from SVF::PTAStat
	PTAStat (PointerAnalysis *p)
virtual	~PTAStat ()
void	setMemUsageBefore (u32_t vmrss, u32_t vmsize)
void	setMemUsageAfter (u32_t vmrss, u32_t vmsize)
void	performStat () override
void	callgraphStat () override
Public Member Functions inherited from SVF::SVFStat
	SVFStat ()
virtual	~SVFStat ()
virtual void	startClk ()
virtual void	endClk ()
virtual void	printStat (std::string str="")
virtual void	performStatPerQuery (NodeID)
virtual void	printStatPerQuery (NodeID, const PointsTo &)

Public Attributes
u32_t	_NumOfNullPtr
u32_t	_NumOfConstantPtr
u32_t	_NumOfBlackholePtr
Public Attributes inherited from SVF::PTAStat
NodeBS	localVarInRecursion
Public Attributes inherited from SVF::SVFStat
NUMStatMap	generalNumMap
NUMStatMap	PTNumStatMap
TIMEStatMap	timeStatMap
double	startTime
double	endTime

Static Public Attributes
static const char *	CollapseTime = "CollapseTime"
static u32_t	_MaxPtsSize = 0
static u32_t	_NumOfCycles = 0
static u32_t	_NumOfPWCCycles = 0
static u32_t	_NumOfNodesInCycles = 0
static u32_t	_MaxNumOfNodesInSCC = 0
Static Public Attributes inherited from SVF::SVFStat
static bool	printGeneralStats = true
	SVF's general statistics are only printed once even if you run multiple anayses.
static double	timeOfBuildingLLVMModule = 0
static double	timeOfBuildingSymbolTable = 0
static double	timeOfBuildingSVFIR = 0

Private Attributes
AndersenBase *	pta

Additional Inherited Members
Public Types inherited from SVF::SVFStat
enum	ClockType { Wall , CPU }
typedef OrderedMap< std::string, u32_t >	NUMStatMap
typedef OrderedMap< std::string, double >	TIMEStatMap
Static Public Member Functions inherited from SVF::SVFStat
static double	getClk (bool mark=false)
Protected Attributes inherited from SVF::PTAStat
PointerAnalysis *	pta
u32_t	_vmrssUsageBefore
u32_t	_vmrssUsageAfter
u32_t	_vmsizeUsageBefore
u32_t	_vmsizeUsageAfter

Detailed Description

Statistics of Andersen's analysis

Definition at line 48 of file WPAStat.h.

Constructor & Destructor Documentation

AndersenStat()

AndersenStat::AndersenStat

(

AndersenBase *

p

)

Constructor

Definition at line 49 of file AndersenStat.cpp.

                                         : PTAStat(p),pta(p)
{
    _NumOfNullPtr = 0;
    _NumOfConstantPtr= 0;
    _NumOfBlackholePtr = 0;
    startClk();
}

~AndersenStat()

virtual SVF::AndersenStat::~AndersenStat ( )

inlinevirtual

Definition at line 68 of file WPAStat.h.

    {
 
    }

Member Function Documentation

collectCycleInfo()

void AndersenStat::collectCycleInfo

(

ConstraintGraph *

consCG

)

Collect cycle information

Definition at line 60 of file AndersenStat.cpp.

{
    _NumOfCycles = 0;
    _NumOfPWCCycles = 0;
    _NumOfNodesInCycles = 0;
    NodeSet repNodes;
    repNodes.clear();
    for(ConstraintGraph::iterator it = consCG->begin(), eit = consCG->end(); it!=eit; ++it)
    {
        // sub nodes have been removed from the constraint graph, only rep nodes are left.
        NodeID repNode = consCG->sccRepNode(it->first);
        NodeBS& subNodes = consCG->sccSubNodes(repNode);
        NodeBS clone = subNodes;
        for (NodeBS::iterator it = subNodes.begin(), eit = subNodes.end(); it != eit; ++it)
        {
            NodeID nodeId = *it;
            PAGNode* pagNode = pta->getPAG()->getGNode(nodeId);
            if (SVFUtil::isa<ObjVar>(pagNode) && pta->isFieldInsensitive(nodeId))
            {
                NodeID baseId = consCG->getBaseObjVar(nodeId);
                clone.reset(nodeId);
                clone.set(baseId);
            }
        }
        u32_t num = clone.count();
        if (num > 1)
        {
            if(repNodes.insert(repNode).second)
            {
                _NumOfNodesInCycles += num;
                if(consCG->isPWCNode(repNode))
                    _NumOfPWCCycles ++;
            }
            if( num > _MaxNumOfNodesInSCC)
                _MaxNumOfNodesInSCC = num;
        }
    }
    _NumOfCycles += repNodes.size();
}

constraintGraphStat()

void AndersenStat::constraintGraphStat

(

)

Definition at line 100 of file AndersenStat.cpp.

{
 
 
    ConstraintGraph* consCG = pta->getConstraintGraph();
 
    u32_t numOfCopys = 0;
    u32_t numOfGeps = 0;
    // collect copy and gep edges
    for(ConstraintEdge::ConstraintEdgeSetTy::iterator it = consCG->getDirectCGEdges().begin(),
            eit = consCG->getDirectCGEdges().end(); it!=eit; ++it)
    {
        if(SVFUtil::isa<CopyCGEdge>(*it))
            numOfCopys++;
        else if(SVFUtil::isa<GepCGEdge>(*it))
            numOfGeps++;
        else
            assert(false && "what else!!");
    }
 
    u32_t totalNodeNumber = 0;
    u32_t cgNodeNumber = 0;
    u32_t objNodeNumber = 0;
    u32_t addrtotalIn = 0;
    u32_t addrmaxIn = 0;
    u32_t addrmaxOut = 0;
    u32_t copytotalIn = 0;
    u32_t copymaxIn = 0;
    u32_t copymaxOut = 0;
    u32_t loadtotalIn = 0;
    u32_t loadmaxIn = 0;
    u32_t loadmaxOut = 0;
    u32_t storetotalIn = 0;
    u32_t storemaxIn = 0;
    u32_t storemaxOut = 0;
 
 
    for (ConstraintGraph::ConstraintNodeIDToNodeMapTy::iterator nodeIt = consCG->begin(), nodeEit = consCG->end();
            nodeIt != nodeEit; nodeIt++)
    {
        totalNodeNumber++;
        if(nodeIt->second->getInEdges().empty() && nodeIt->second->getOutEdges().empty())
            continue;
        cgNodeNumber++;
        if(SVFUtil::isa<ObjVar>(pta->getPAG()->getGNode(nodeIt->first)))
            objNodeNumber++;
 
        u32_t nCopyIn = nodeIt->second->getDirectInEdges().size();
        if(nCopyIn > copymaxIn)
            copymaxIn = nCopyIn;
        copytotalIn +=nCopyIn;
        u32_t nCopyOut = nodeIt->second->getDirectOutEdges().size();
        if(nCopyOut > copymaxOut)
            copymaxOut = nCopyOut;
        u32_t nLoadIn = nodeIt->second->getLoadInEdges().size();
        if(nLoadIn > loadmaxIn)
            loadmaxIn = nLoadIn;
        loadtotalIn +=nLoadIn;
        u32_t nLoadOut = nodeIt->second->getLoadOutEdges().size();
        if(nLoadOut > loadmaxOut)
            loadmaxOut = nLoadOut;
        u32_t nStoreIn = nodeIt->second->getStoreInEdges().size();
        if(nStoreIn > storemaxIn)
            storemaxIn = nStoreIn;
        storetotalIn +=nStoreIn;
        u32_t nStoreOut = nodeIt->second->getStoreOutEdges().size();
        if(nStoreOut > storemaxOut)
            storemaxOut = nStoreOut;
        u32_t nAddrIn = nodeIt->second->getAddrInEdges().size();
        if(nAddrIn > addrmaxIn)
            addrmaxIn = nAddrIn;
        addrtotalIn +=nAddrIn;
        u32_t nAddrOut = nodeIt->second->getAddrOutEdges().size();
        if(nAddrOut > addrmaxOut)
            addrmaxOut = nAddrOut;
    }
    double storeavgIn = (double)storetotalIn/cgNodeNumber;
    double loadavgIn = (double)loadtotalIn/cgNodeNumber;
    double copyavgIn = (double)copytotalIn/cgNodeNumber;
    double addravgIn = (double)addrtotalIn/cgNodeNumber;
    double avgIn = (double)(addrtotalIn + copytotalIn + loadtotalIn + storetotalIn)/cgNodeNumber;
 
 
    PTNumStatMap["NumOfCGNode"] = totalNodeNumber;
    PTNumStatMap["NumOfValidNode"] = cgNodeNumber;
    PTNumStatMap["NumOfValidObjNode"] = objNodeNumber;
    PTNumStatMap["NumOfCGEdge"] = consCG->getLoadCGEdges().size() + consCG->getStoreCGEdges().size()
                                  + numOfCopys + numOfGeps;
    PTNumStatMap["NumOfAddrs"] =  consCG->getAddrCGEdges().size();
    PTNumStatMap["NumOfCopys"] = numOfCopys;
    PTNumStatMap["NumOfGeps"] =  numOfGeps;
    PTNumStatMap["NumOfLoads"] = consCG->getLoadCGEdges().size();
    PTNumStatMap["NumOfStores"] = consCG->getStoreCGEdges().size();
    PTNumStatMap["MaxInCopyEdge"] = copymaxIn;
    PTNumStatMap["MaxOutCopyEdge"] = copymaxOut;
    PTNumStatMap["MaxInLoadEdge"] = loadmaxIn;
    PTNumStatMap["MaxOutLoadEdge"] = loadmaxOut;
    PTNumStatMap["MaxInStoreEdge"] = storemaxIn;
    PTNumStatMap["MaxOutStoreEdge"] = storemaxOut;
    PTNumStatMap["MaxInAddrEdge"] = addrmaxIn;
    PTNumStatMap["MaxOutAddrEdge"] = addrmaxOut;
    timeStatMap["AvgIn/OutStoreEdge"] = storeavgIn;
    timeStatMap["AvgIn/OutCopyEdge"] = copyavgIn;
    timeStatMap["AvgIn/OutLoadEdge"] = loadavgIn;
    timeStatMap["AvgIn/OutAddrEdge"] = addravgIn;
    timeStatMap["AvgIn/OutEdge"] = avgIn;
}

performStat()

void AndersenStat::performStat ( )

virtual

Start here

Implements SVF::SVFStat.

Definition at line 264 of file AndersenStat.cpp.

{
 
    assert(SVFUtil::isa<AndersenBase>(pta) && "not an andersen pta pass!! what else??");
    endClk();
 
    SVFIR* pag = pta->getPAG();
    ConstraintGraph* consCG = pta->getConstraintGraph();
 
    // collect constraint graph cycles
    collectCycleInfo(consCG);
 
    // stat null ptr number
    statNullPtr();
 
    u32_t totalPointers = 0;
    u32_t totalTopLevPointers = 0;
    u32_t totalPtsSize = 0;
    u32_t totalTopLevPtsSize = 0;
    for (SVFIR::iterator iter = pta->getPAG()->begin(), eiter = pta->getPAG()->end();
            iter != eiter; ++iter)
    {
        NodeID node = iter->first;
        const PointsTo& pts = pta->getPts(node);
        u32_t size = pts.count();
        totalPointers++;
        totalPtsSize+=size;
 
        if(pta->getPAG()->isValidTopLevelPtr(pta->getPAG()->getGNode(node)))
        {
            totalTopLevPointers++;
            totalTopLevPtsSize+=size;
        }
 
        if(size > _MaxPtsSize )
            _MaxPtsSize = size;
    }
 
 
    PTAStat::performStat();
 
    constraintGraphStat();
 
    timeStatMap["TotalTime"] = (endTime - startTime)/TIMEINTERVAL;
    timeStatMap["SCCDetectTime"] = Andersen::timeOfSCCDetection;
    timeStatMap["SCCMergeTime"] =  Andersen::timeOfSCCMerges;
    timeStatMap[CollapseTime] =  Andersen::timeOfCollapse;
 
    timeStatMap["LoadStoreTime"] =  Andersen::timeOfProcessLoadStore;
    timeStatMap["CopyGepTime"] =  Andersen::timeOfProcessCopyGep;
    timeStatMap["UpdateCGTime"] =  Andersen::timeOfUpdateCallGraph;
 
    PTNumStatMap["TotalPointers"] = pag->getValueNodeNum();
    PTNumStatMap["TotalObjects"] = pag->getObjectNodeNum();
 
 
    PTNumStatMap["AddrProcessed"] = Andersen::numOfProcessedAddr;
    PTNumStatMap["CopyProcessed"] = Andersen::numOfProcessedCopy;
    PTNumStatMap["GepProcessed"] = Andersen::numOfProcessedGep;
    PTNumStatMap["LoadProcessed"] = Andersen::numOfProcessedLoad;
    PTNumStatMap["StoreProcessed"] = Andersen::numOfProcessedStore;
 
    PTNumStatMap["NumOfSFRs"] = Andersen::numOfSfrs;
    PTNumStatMap["NumOfFieldExpand"] = Andersen::numOfFieldExpand;
 
    PTNumStatMap["Pointers"] = pag->getValueNodeNum();
    PTNumStatMap["MemObjects"] = pag->getObjectNodeNum();
    PTNumStatMap["DummyFieldPtrs"] = pag->getFieldValNodeNum();
    PTNumStatMap["FieldObjs"] = pag->getFieldObjNodeNum();
 
    timeStatMap["AvgPtsSetSize"] = (double)totalPtsSize/totalPointers;;
    timeStatMap["AvgTopLvlPtsSize"] = (double)totalTopLevPtsSize/totalTopLevPointers;;
 
    PTNumStatMap["MaxPtsSetSize"] = _MaxPtsSize;
 
    PTNumStatMap["SolveIterations"] = pta->numOfIteration;
 
    PTNumStatMap["IndCallSites"] = consCG->getIndirectCallsites().size();
    PTNumStatMap["IndEdgeSolved"] = pta->getNumOfResolvedIndCallEdge();
 
    PTNumStatMap["NumOfSCCDetect"] = Andersen::numOfSCCDetection;
    PTNumStatMap["TotalCycleNum"] = _NumOfCycles;
    PTNumStatMap["TotalPWCCycleNum"] = _NumOfPWCCycles;
    PTNumStatMap["NodesInCycles"] = _NumOfNodesInCycles;
    PTNumStatMap["MaxNodesInSCC"] = _MaxNumOfNodesInSCC;
    PTNumStatMap["NullPointer"] = _NumOfNullPtr;
    PTNumStatMap["PointsToConstPtr"] = _NumOfConstantPtr;
    PTNumStatMap["PointsToBlkPtr"] = _NumOfBlackholePtr;
 
    PTAStat::printStat("Andersen Pointer Analysis Stats");
}

statNullPtr()

void AndersenStat::statNullPtr

(

)

Stat null pointers

TODO: change the condition here to fetch the points-to set

Definition at line 210 of file AndersenStat.cpp.

{
 
    _NumOfNullPtr = 0;
    for (SVFIR::iterator iter = pta->getPAG()->begin(), eiter = pta->getPAG()->end();
            iter != eiter; ++iter)
    {
        NodeID pagNodeId = iter->first;
        PAGNode* pagNode = iter->second;
        if (SVFUtil::isa<ValVar>(pagNode) == false)
            continue;
        SVFStmt::SVFStmtSetTy& inComingStore = pagNode->getIncomingEdges(SVFStmt::Store);
        SVFStmt::SVFStmtSetTy& outGoingLoad = pagNode->getOutgoingEdges(SVFStmt::Load);
        if (inComingStore.empty()==false || outGoingLoad.empty()==false)
        {
            const PointsTo& pts = pta->getPts(pagNodeId);
            if (pta->containBlackHoleNode(pts))
                _NumOfBlackholePtr++;
 
            if (pta->containConstantNode(pts))
                _NumOfConstantPtr++;
 
            if(pts.empty())
            {
                std::string str;
                std::stringstream rawstr(str);
                if (!SVFUtil::isa<DummyValVar>(pagNode) && !SVFUtil::isa<DummyObjVar>(pagNode) )
                {
                    // if a pointer is in dead function, we do not care
                    if(pagNode->ptrInUncalledFunction() == false)
                    {
                        _NumOfNullPtr++;
                        rawstr << "##Null Pointer : (NodeID " << pagNode->getId()
                               << ") PtrName:" << pagNode->getName();
                        writeWrnMsg(rawstr.str());
                        //pagNode->getValue()->dump();
                    }
                }
                else
                {
                    _NumOfNullPtr++;
                    rawstr << "##Null Pointer : (NodeID " << pagNode->getId() << ")";
                    writeWrnMsg(rawstr.str());
                }
            }
        }
    }
 
}

Member Data Documentation

_MaxNumOfNodesInSCC

u32_t AndersenStat::_MaxNumOfNodesInSCC = 0

static

Definition at line 61 of file WPAStat.h.

_MaxPtsSize

u32_t AndersenStat::_MaxPtsSize = 0

static

Definition at line 57 of file WPAStat.h.

_NumOfBlackholePtr

u32_t SVF::AndersenStat::_NumOfBlackholePtr

Definition at line 64 of file WPAStat.h.

_NumOfConstantPtr

u32_t SVF::AndersenStat::_NumOfConstantPtr

Definition at line 63 of file WPAStat.h.

_NumOfCycles

u32_t AndersenStat::_NumOfCycles = 0

static

Definition at line 58 of file WPAStat.h.

_NumOfNodesInCycles

u32_t AndersenStat::_NumOfNodesInCycles = 0

static

Definition at line 60 of file WPAStat.h.

_NumOfNullPtr

u32_t SVF::AndersenStat::_NumOfNullPtr

Definition at line 62 of file WPAStat.h.

_NumOfPWCCycles

u32_t AndersenStat::_NumOfPWCCycles = 0

static

Definition at line 59 of file WPAStat.h.

CollapseTime

const char * AndersenStat::CollapseTime = "CollapseTime"

static

Definition at line 55 of file WPAStat.h.

pta

AndersenBase* SVF::AndersenStat::pta

private

Definition at line 52 of file WPAStat.h.

---

The documentation for this class was generated from the following files:

• /home/runner/work/SVF/SVF/svf/include/WPA/WPAStat.h
• /home/runner/work/SVF/SVF/svf/lib/WPA/AndersenStat.cpp