AndersenSCD.cpp

Go to the documentation of this file.

//===- AndersenSCD.cpp -- SCD based field-sensitive Andersen's analysis-------//
//
//                     SVF: Static Value-Flow Analysis
//
// Copyright (C) <2013-2017>  <Yulei Sui>
//
 
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
 
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
 
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * AndersenSCD.cpp
 *
 *  Created on: 09, Feb, 2019
 *      Author: Yuxiang Lei
 */
 
#include "WPA/AndersenPWC.h"
#include "MemoryModel/PointsTo.h"
#include "Util/Options.h"
#include "Util/PTAStat.h"
 
using namespace SVF;
using namespace SVFUtil;
using namespace std;
 
AndersenSCD* AndersenSCD::scdAndersen = nullptr;
 
 
void AndersenSCD::solveWorklist()
{
    // Initialize the nodeStack via a whole SCC detection
    // Nodes in nodeStack are in topological order by default.
    NodeStack& nodeStack = SCCDetect();
 
    for (NodeID nId : sccCandidates)
        pushIntoWorklist(nId);
    sccCandidates.clear();
 
    // propagate point-to sets
    while (!nodeStack.empty())
    {
        NodeID nodeId = nodeStack.top();
        nodeStack.pop();
 
        if (sccRepNode(nodeId) == nodeId)
        {
            collapsePWCNode(nodeId);
 
            if (isInWorklist(nodeId))
                // push the rep of node into worklist
                pushIntoWorklist(nodeId);
 
            double propStart = stat->getClk();
            // propagate pts through copy and gep edges
            ConstraintNode* node = consCG->getConstraintNode(nodeId);
            handleCopyGep(node);
            double propEnd = stat->getClk();
            timeOfProcessCopyGep += (propEnd - propStart) / TIMEINTERVAL;
 
            collapseFields();
        }
    }
 
    // New nodes will be inserted into workList during processing.
    while (!isWorklistEmpty())
    {
        NodeID nodeId = popFromWorklist();
 
        double insertStart = stat->getClk();
        // add copy edges via processing load or store edges
        ConstraintNode* node = consCG->getConstraintNode(nodeId);
        handleLoadStore(node);
        double insertEnd = stat->getClk();
        timeOfProcessLoadStore += (insertEnd - insertStart) / TIMEINTERVAL;
    }
}
 
 
NodeStack& AndersenSCD::SCCDetect()
{
    numOfSCCDetection++;
 
    double sccStart = stat->getClk();
    getSCCDetector()->find(sccCandidates);
    double sccEnd = stat->getClk();
    timeOfSCCDetection +=  (sccEnd - sccStart)/TIMEINTERVAL;
 
    double mergeStart = stat->getClk();
    mergeSccCycle();
    double mergeEnd = stat->getClk();
    timeOfSCCMerges +=  (mergeEnd - mergeStart)/TIMEINTERVAL;
 
    if (!Options::DetectPWC())
    {
        sccStart = stat->getClk();
        PWCDetect();
        sccEnd = stat->getClk();
        timeOfSCCDetection += (sccEnd - sccStart) / TIMEINTERVAL;
    }
 
    return getSCCDetector()->topoNodeStack();
}
 
 
void AndersenSCD::PWCDetect()
{
    // replace scc candidates by their reps
    NodeSet tmpSccCandidates = sccCandidates;
    sccCandidates.clear();
    for (NodeID candidate : tmpSccCandidates)
        sccCandidates.insert(sccRepNode(candidate));
    tmpSccCandidates.clear();
 
    // set scc edge type as direct edge
    bool pwcFlag = Options::DetectPWC();
    setDetectPWC(true);
 
    getSCCDetector()->find(sccCandidates);
 
    // reset scc edge type
    setDetectPWC(pwcFlag);
}
 
 
void AndersenSCD::handleCopyGep(ConstraintNode* node)
{
    NodeID nodeId = node->getId();
 
    if (!Options::DetectPWC() && getSCCDetector()->subNodes(nodeId).count() > 1)
        processPWC(node);
    else if(isInWorklist(nodeId))
        Andersen::handleCopyGep(node);
}
 
 
void AndersenSCD::processPWC(ConstraintNode* rep)
{
    NodeID repId = rep->getId();
 
    NodeSet pwcNodes;
    for (NodeID nId : getSCCDetector()->subNodes(repId))
        pwcNodes.insert(nId);
 
    WorkList tmpWorkList;
    for (NodeID subId : pwcNodes)
        if (isInWorklist(subId))
            tmpWorkList.push(subId);
 
    while (!tmpWorkList.empty())
    {
        NodeID nodeId = tmpWorkList.pop();
        computeDiffPts(nodeId);
 
        if (!getDiffPts(nodeId).empty())
        {
            ConstraintNode *node = consCG->getConstraintNode(nodeId);
            for (ConstraintEdge* edge : node->getCopyOutEdges())
            {
                bool changed = processCopy(nodeId, edge);
                if (changed && pwcNodes.find(edge->getDstID()) != pwcNodes.end())
                    tmpWorkList.push(edge->getDstID());
            }
            for (ConstraintEdge* edge : node->getGepOutEdges())
            {
                if (GepCGEdge *gepEdge = SVFUtil::dyn_cast<GepCGEdge>(edge))
                {
                    bool changed = processGep(nodeId, gepEdge);
                    if (changed && pwcNodes.find(edge->getDstID()) != pwcNodes.end())
                        tmpWorkList.push(edge->getDstID());
                }
            }
        }
    }
}
 
 
void AndersenSCD::handleLoadStore(ConstraintNode* node)
{
    double insertStart = stat->getClk();
 
    NodeID nodeId = node->getId();
    // handle load
    for (ConstraintNode::const_iterator it = node->outgoingLoadsBegin(),
            eit = node->outgoingLoadsEnd(); it != eit; ++it)
        for (PointsTo::iterator piter = getPts(nodeId).begin(), epiter =
                    getPts(nodeId).end(); piter != epiter; ++piter)
        {
            NodeID ptd = *piter;
            if (processLoad(ptd, *it))
            {
                reanalyze = true;
            }
        }
 
    // handle store
    for (ConstraintNode::const_iterator it = node->incomingStoresBegin(),
            eit = node->incomingStoresEnd(); it != eit; ++it)
        for (PointsTo::iterator piter = getPts(nodeId).begin(), epiter =
                    getPts(nodeId).end(); piter != epiter; ++piter)
        {
            NodeID ptd = *piter;
            if (processStore(ptd, *it))
            {
                reanalyze = true;
            }
        }
 
    double insertEnd = stat->getClk();
    timeOfProcessLoadStore += (insertEnd - insertStart) / TIMEINTERVAL;
}
 
 
void AndersenSCD::processAddr(const AddrCGEdge *addr)
{
    numOfProcessedAddr++;
 
    NodeID dst = addr->getDstID();
    NodeID src = addr->getSrcID();
    addPts(dst,src);
    addSccCandidate(dst);
}
 
 
bool AndersenSCD::addCopyEdge(NodeID src, NodeID dst)
{
    if (Andersen::addCopyEdge(src, dst))
    {
        addSccCandidate(src);
        return true;
    }
    return false;
}
 
 
bool AndersenSCD::updateCallGraph(const PointerAnalysis::CallSiteToFunPtrMap& callsites)
{
    double cgUpdateStart = stat->getClk();
 
    CallEdgeMap newEdges;
    onTheFlyCallGraphSolve(callsites,newEdges);
    NodePairSet cpySrcNodes;    
    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);
        }
    }
 
    double cgUpdateEnd = stat->getClk();
    timeOfUpdateCallGraph += (cgUpdateEnd - cgUpdateStart) / TIMEINTERVAL;
 
    return (!newEdges.empty());
}