Andersen.cpp

Go to the documentation of this file.

//===- Andersen.cpp -- 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/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * Andersen.cpp
 *
 *  Created on: Nov 12, 2013
 *      Author: Yulei Sui
 */
 
#include "Graphs/ThreadCallGraph.h"
#include "MemoryModel/PointsTo.h"
#include "WPA/Andersen.h"
#include "WPA/Steensgaard.h"
#include "WPA/WPAStat.h"
#include "Util/CoreBitVector.h"
#include "Util/GeneralType.h"
#include "Util/Options.h"
#include "Util/SVFUtil.h"
 
#include <utility>
 
#include <algorithm>
#include <cstdint>
#include <vector>
 
using namespace SVF;
using namespace SVFUtil;
using namespace std;
 
 
u32_t AndersenBase::numOfProcessedAddr = 0;
u32_t AndersenBase::numOfProcessedCopy = 0;
u32_t AndersenBase::numOfProcessedGep = 0;
u32_t AndersenBase::numOfProcessedLoad = 0;
u32_t AndersenBase::numOfProcessedStore = 0;
u32_t AndersenBase::numOfSfrs = 0;
u32_t AndersenBase::numOfFieldExpand = 0;
 
u32_t AndersenBase::numOfSCCDetection = 0;
double AndersenBase::timeOfSCCDetection = 0;
double AndersenBase::timeOfSCCMerges = 0;
double AndersenBase::timeOfCollapse = 0;
 
u32_t AndersenBase::AveragePointsToSetSize = 0;
u32_t AndersenBase::MaxPointsToSetSize = 0;
double AndersenBase::timeOfProcessCopyGep = 0;
double AndersenBase::timeOfProcessLoadStore = 0;
double AndersenBase::timeOfUpdateCallGraph = 0;
 
AndersenBase::~AndersenBase()
{
    delete consCG;
    consCG = nullptr;
}
 
void AndersenBase::initialize()
{
    PointerAnalysis::initialize();
    stat = new AndersenStat(this);
    consCG = new ConstraintGraph(pag);
    setGraph(consCG);
    if (Options::ConsCGDotGraph())
        consCG->dump("consCG_initial");
}
 
void AndersenBase::finalize()
{
    if (Options::ConsCGDotGraph())
        consCG->dump("consCG_final");
 
    if (Options::PrintCGGraph())
        consCG->print();
    BVDataPTAImpl::finalize();
}
 
void AndersenBase::solveConstraints()
{
    // Start solving constraints
    DBOUT(DGENERAL, outs() << SVFUtil::pasMsg("Start Solving Constraints\n"));
 
    bool timeLimited = Options::AnderTimeLimit() > 0;
    if (timeLimited)
    {
        assert(Options::FsTimeLimit() == 0 && "both -ander-time-limit and -fs-time-limit set.");
        SVFUtil::startAnalysisLimitTimer(Options::AnderTimeLimit());
    }
 
    initWorklist();
    do
    {
        numOfIteration++;
        if (0 == numOfIteration % iterationForPrintStat)
            printStat();
 
        reanalyze = false;
 
        solveWorklist();
 
        if (updateCallGraph(getIndirectCallsites()))
            reanalyze = true;
 
    }
    while (reanalyze);
 
    // Analysis is finished, reset the alarm if we set it.
    if (timeLimited)
    {
        SVFUtil::stopAnalysisLimitTimer();
    }
 
    DBOUT(DGENERAL, outs() << SVFUtil::pasMsg("Finish Solving Constraints\n"));
}
 
void AndersenBase::analyze()
{
    if(!Options::ReadAnder().empty())
    {
        readPtsFromFile(Options::ReadAnder());
    }
    else
    {
        if(Options::WriteAnder().empty())
        {
            initialize();
            solveConstraints();
            finalize();
        }
        else
        {
            solveAndwritePtsToFile(Options::WriteAnder());
        }
    }
}
 
void AndersenBase::readPtsFromFile(const std::string& filename)
{
    initialize();
    if (!filename.empty())
        this->readFromFile(filename);
    finalize();
}
 
void AndersenBase:: solveAndwritePtsToFile(const std::string& filename)
{
    initialize();
    if (!filename.empty())
        this->writeObjVarToFile(filename);
    solveConstraints();
    if (!filename.empty())
        this->writeToFile(filename);
    finalize();
}
 
void AndersenBase::cleanConsCG(NodeID id)
{
    // Remove only this node from its representative's members. Erasing the whole
    // member set would leave every other member mapped to a representative that no
    // longer lists it, so sccSubNodes would stop being the inverse of sccRepNode.
    consCG->getSubs(consCG->sccRepNode(id)).reset(id);
    for (NodeID sub: consCG->getSubs(id))
        consCG->resetRep(sub);
    consCG->resetSubs(id);
    consCG->resetRep(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; 
    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);
        }
    }
 
    bool hasNewForkEdges = updateThreadCallGraph(callsites, 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()) || 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();
}
 
void AndersenBase::connectCaller2ForkedFunParams(const CallICFGNode* cs, const FunObjVar* F,
        NodePairSet& cpySrcNodes)
{
    assert(F);
 
    DBOUT(DAndersen, outs() << "connect parameters from indirect forksite "
          << cs->valueOnlyToString() << " to forked function "
          << *F << "\n");
 
    ThreadCallGraph *tdCallGraph = SVFUtil::dyn_cast<ThreadCallGraph>(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 FunObjVar* F, NodePairSet &cpySrcNodes)
{
    assert(F);
 
    DBOUT(DAndersen, outs() << "connect parameters from indirect callsite " << cs->valueOnlyToString() << " 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::ValVarList& csArgList = pag->getCallSiteArgsList(callBlockNode);
        const SVFIR::ValVarList& funArgList = pag->getFunArgsList(F);
        //Go through the fixed parameters.
        DBOUT(DPAGBuild, outs() << "      args:");
        SVFIR::ValVarList::const_iterator funArgIt = funArgList.begin(), funArgEit = funArgList.end();
        SVFIR::ValVarList::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() + ")");
        }
    }
}
 
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 = sccRepNode(it->second);
    }
    else
    {
        NodeID valNode = pag->addDummyValNode();
        NodeID objNode = pag->addDummyObjNode(cs->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));
}
 
void AndersenBase::normalizePointsTo()
{
    SVFIR::MemObjToFieldsMap &memToFieldsMap = pag->getMemToFieldsMap();
    SVFIR::OffsetToGepVarMap &GepObjVarMap = pag->getGepObjNodeMap();
 
    // clear GepObjVarMap/memToFieldsMap/nodeToSubsMap/nodeToRepMap
    // for redundant gepnodes and remove those nodes from pag
    for (NodeID n: redundantGepNodes)
    {
        NodeID base = pag->getBaseObjVarID(n);
        const GepObjVar* gepNode = pag->getGepObjVar(n);
        assert(gepNode && "Not a gep node in redundantGepNodes set");
        const APOffset apOffset = gepNode->getConstantFieldIdx();
        GepObjVarMap.erase(std::make_pair(base, apOffset));
        memToFieldsMap[base].reset(n);
        cleanConsCG(n);
 
        pag->removeGNode(const_cast<GepObjVar*>(gepNode));
    }
}
 
void Andersen::initialize()
{
    resetData();
    AndersenBase::initialize();
 
    if (Options::ClusterAnder()) cluster();
 
    processAllAddr();
}
 
void Andersen::finalize()
{
    // TODO: broken
    if (Options::ClusterAnder())
    {
        Map<std::string, std::string> stats;
        const PTDataTy *ptd = getPTDataTy();
        // TODO: should we use liveOnly?
        // TODO: parameterise final arg.
        NodeIDAllocator::Clusterer::evaluate(*PointsTo::getCurrentBestNodeMapping(), ptd->getAllPts(true), stats, true);
        if (print_stat)
        {
            NodeIDAllocator::Clusterer::printStats("post-main", stats);
        }
    }
 
    //  sanitizePts();
    AndersenBase::finalize();
}
 
void Andersen::processNode(NodeID nodeId)
{
    // sub nodes do not need to be processed
    if (sccRepNode(nodeId) != nodeId)
        return;
 
    ConstraintNode* node = consCG->getConstraintNode(nodeId);
    double insertStart = stat->getClk();
    handleLoadStore(node);
    double insertEnd = stat->getClk();
    timeOfProcessLoadStore += (insertEnd - insertStart) / TIMEINTERVAL;
 
    double propStart = stat->getClk();
    handleCopyGep(node);
    double propEnd = stat->getClk();
    timeOfProcessCopyGep += (propEnd - propStart) / TIMEINTERVAL;
}
 
void Andersen::handleCopyGep(ConstraintNode* node)
{
    NodeID nodeId = node->getId();
    computeDiffPts(nodeId);
 
    if (!getDiffPts(nodeId).empty())
    {
        for (ConstraintEdge* edge : node->getCopyOutEdges())
            processCopy(nodeId, edge);
        for (ConstraintEdge* edge : node->getGepOutEdges())
        {
            if (GepCGEdge* gepEdge = SVFUtil::dyn_cast<GepCGEdge>(edge))
                processGep(nodeId, gepEdge);
        }
    }
}
 
void Andersen::handleLoadStore(ConstraintNode *node)
{
    NodeID nodeId = node->getId();
    for (PointsTo::iterator piter = getPts(nodeId).begin(), epiter =
                getPts(nodeId).end(); piter != epiter; ++piter)
    {
        NodeID ptd = *piter;
        // handle load
        for (ConstraintNode::const_iterator it = node->outgoingLoadsBegin(),
                eit = node->outgoingLoadsEnd(); it != eit; ++it)
        {
            if (processLoad(ptd, *it))
                pushIntoWorklist(ptd);
        }
 
        // handle store
        for (ConstraintNode::const_iterator it = node->incomingStoresBegin(),
                eit = node->incomingStoresEnd(); it != eit; ++it)
        {
            if (processStore(ptd, *it))
                pushIntoWorklist((*it)->getSrcID());
        }
    }
}
 
void Andersen::processAllAddr()
{
    for (ConstraintGraph::const_iterator nodeIt = consCG->begin(), nodeEit = consCG->end(); nodeIt != nodeEit; nodeIt++)
    {
        ConstraintNode * cgNode = nodeIt->second;
        for (ConstraintNode::const_iterator it = cgNode->incomingAddrsBegin(), eit = cgNode->incomingAddrsEnd();
                it != eit; ++it)
            processAddr(SVFUtil::cast<AddrCGEdge>(*it));
    }
}
 
void Andersen::processAddr(const AddrCGEdge* addr)
{
    numOfProcessedAddr++;
 
    NodeID dst = addr->getDstID();
    NodeID src = addr->getSrcID();
    if(addPts(dst,src))
        pushIntoWorklist(dst);
}
 
bool Andersen::processLoad(NodeID node, const ConstraintEdge* load)
{
//  if (pag->isBlkObjOrConstantObj(node))
    if (pag->isConstantObj(node) || pag->getSVFVar(load->getDstID())->isPointer() == false)
        return false;
 
    numOfProcessedLoad++;
 
    NodeID dst = load->getDstID();
    return addCopyEdge(node, dst);
}
 
bool Andersen::processStore(NodeID node, const ConstraintEdge* store)
{
//  if (pag->isBlkObjOrConstantObj(node))
    if (pag->isConstantObj(node) || pag->getSVFVar(store->getSrcID())->isPointer() == false)
        return false;
 
    numOfProcessedStore++;
 
    NodeID src = store->getSrcID();
    return addCopyEdge(src, node);
}
 
bool Andersen::processCopy(NodeID node, const ConstraintEdge* edge)
{
    numOfProcessedCopy++;
 
    assert((SVFUtil::isa<CopyCGEdge>(edge)) && "not copy/call/ret ??");
    NodeID dst = edge->getDstID();
    const PointsTo& srcPts = getDiffPts(node);
 
    bool changed = unionPts(dst, srcPts);
    if (changed)
        pushIntoWorklist(dst);
    return changed;
}
 
bool Andersen::processGep(NodeID, const GepCGEdge* edge)
{
    const PointsTo& srcPts = getDiffPts(edge->getSrcID());
    return processGepPts(srcPts, edge);
}
 
bool Andersen::processGepPts(const PointsTo& pts, const GepCGEdge* edge)
{
    numOfProcessedGep++;
 
    PointsTo tmpDstPts;
    if (SVFUtil::isa<VariantGepCGEdge>(edge))
    {
        // If a pointer is connected by a variant gep edge,
        // then set this memory object to be field insensitive,
        // unless the object is a black hole/constant.
        for (NodeID o : pts)
        {
            if (consCG->isBlkObjOrConstantObj(o))
            {
                tmpDstPts.set(o);
                continue;
            }
 
            if (!isFieldInsensitive(o))
            {
                setObjFieldInsensitive(o);
                consCG->addNodeToBeCollapsed(consCG->getBaseObjVarID(o));
            }
 
            // Add the field-insensitive node into pts.
            NodeID baseId = consCG->getFIObjVar(o);
            tmpDstPts.set(baseId);
        }
    }
    else if (const NormalGepCGEdge* normalGepEdge = SVFUtil::dyn_cast<NormalGepCGEdge>(edge))
    {
        // TODO: after the node is set to field insensitive, handling invariant
        // gep edge may lose precision because offsets here are ignored, and the
        // base object is always returned.
        for (NodeID o : pts)
        {
            if (consCG->isBlkObjOrConstantObj(o) || isFieldInsensitive(o))
            {
                tmpDstPts.set(o);
                continue;
            }
 
            NodeID fieldSrcPtdNode = consCG->getGepObjVar(o, normalGepEdge->getAccessPath().getConstantStructFldIdx());
            tmpDstPts.set(fieldSrcPtdNode);
        }
    }
    else
    {
        assert(false && "Andersen::processGepPts: New type GEP edge type?");
    }
 
    NodeID dstId = edge->getDstID();
    if (unionPts(dstId, tmpDstPts))
    {
        pushIntoWorklist(dstId);
        return true;
    }
 
    return false;
}
 
void Andersen::collapsePWCNode(NodeID nodeId)
{
    // If a node is a PWC node, collapse all its points-to target.
    // collapseNodePts() may change the points-to set of the nodes which have been processed
    // before, in this case, we may need to re-do the analysis.
    if (consCG->isPWCNode(nodeId) && collapseNodePts(nodeId))
        reanalyze = true;
}
 
void Andersen::collapseFields()
{
    while (consCG->hasNodesToBeCollapsed())
    {
        NodeID node = consCG->getNextCollapseNode();
        // collapseField() may change the points-to set of the nodes which have been processed
        // before, in this case, we may need to re-do the analysis.
        if (collapseField(node))
            reanalyze = true;
    }
}
 
/*
 * Merge constraint graph nodes based on SCC cycle detected.
 */
void Andersen::mergeSccCycle()
{
    NodeStack topoOrder = getSCCDetector()->topoNodeStack();
 
    while (!topoOrder.empty())
    {
        NodeID repNodeId = topoOrder.top();
        topoOrder.pop();
        const NodeBS& subNodes = getSCCDetector()->subNodes(repNodeId);
        // merge sub nodes to rep node
        mergeSccNodes(repNodeId, subNodes);
        if (subNodes.count() > 1)
        {
            pushIntoWorklist(repNodeId);
            reanalyze = true;
        }
    }
}
 
 
void Andersen::mergeSccNodes(NodeID repNodeId, const NodeBS& subNodes)
{
    for (NodeBS::iterator nodeIt = subNodes.begin(); nodeIt != subNodes.end(); nodeIt++)
    {
        NodeID subNodeId = *nodeIt;
        if (subNodeId != repNodeId)
        {
            mergeNodeToRep(subNodeId, repNodeId);
        }
    }
}
 
bool Andersen::collapseNodePts(NodeID nodeId)
{
    bool changed = false;
    const PointsTo& nodePts = getPts(nodeId);
    PointsTo ptsClone = nodePts;
    for (PointsTo::iterator ptsIt = ptsClone.begin(), ptsEit = ptsClone.end(); ptsIt != ptsEit; ptsIt++)
    {
        if (isFieldInsensitive(*ptsIt))
            continue;
 
        if (collapseField(*ptsIt))
            changed = true;
    }
    return changed;
}
 
bool Andersen::collapseField(NodeID nodeId)
{
    if (consCG->isBlkObjOrConstantObj(nodeId))
        return false;
 
    bool changed = false;
 
    double start = stat->getClk();
 
    // set base node field-insensitive.
    setObjFieldInsensitive(nodeId);
 
    // replace all occurrences of each field with the field-insensitive node
    NodeID baseId = consCG->getFIObjVar(nodeId);
    NodeID baseRepNodeId = consCG->sccRepNode(baseId);
    NodeBS & allFields = consCG->getAllFieldsObjVars(baseId);
    for (NodeBS::iterator fieldIt = allFields.begin(), fieldEit = allFields.end(); fieldIt != fieldEit; fieldIt++)
    {
        NodeID fieldId = *fieldIt;
        if (fieldId != baseId)
        {
            // use the reverse pts of this field node to find all pointers point to it
            const NodeSet revPts = getRevPts(fieldId);
            for (const NodeID o : revPts)
            {
                // change the points-to target from field to base node
                clearPts(o, fieldId);
                addPts(o, baseId);
                pushIntoWorklist(o);
 
                changed = true;
            }
            // merge field node into base node, including edges and pts.
            NodeID fieldRepNodeId = consCG->sccRepNode(fieldId);
            mergeNodeToRep(fieldRepNodeId, baseRepNodeId);
            if (fieldId != baseRepNodeId)
            {
                // gep node fieldId becomes redundant if it is merged to its base node who is set as field-insensitive
                // two node IDs should be different otherwise this field is actually the base and should not be removed.
                redundantGepNodes.set(fieldId);
            }
        }
    }
 
    if (consCG->isPWCNode(baseRepNodeId))
        if (collapseNodePts(baseRepNodeId))
            changed = true;
 
    double end = stat->getClk();
    timeOfCollapse += (end - start) / TIMEINTERVAL;
 
    return changed;
}
 
NodeStack& Andersen::SCCDetect()
{
    numOfSCCDetection++;
 
    double sccStart = stat->getClk();
    WPAConstraintSolver::SCCDetect();
    double sccEnd = stat->getClk();
 
    timeOfSCCDetection +=  (sccEnd - sccStart)/TIMEINTERVAL;
 
    double mergeStart = stat->getClk();
 
    mergeSccCycle();
 
    double mergeEnd = stat->getClk();
 
    timeOfSCCMerges +=  (mergeEnd - mergeStart)/TIMEINTERVAL;
 
    return getSCCDetector()->topoNodeStack();
}
 
bool Andersen::mergeSrcToTgt(NodeID nodeId, NodeID newRepId)
{
 
    if(nodeId==newRepId)
        return false;
 
    updatePropaPts(newRepId, nodeId);
    unionPts(newRepId,nodeId);
 
    ConstraintNode* node = consCG->getConstraintNode(nodeId);
    bool pwc = consCG->moveEdgesToRepNode(node, consCG->getConstraintNode(newRepId));
 
    if(node->isPWCNode())
        pwc = true;
 
    updateNodeRepAndSubs(node->getId(),newRepId);
 
    consCG->removeConstraintNode(node);
 
    return pwc;
}
/*
 * Merge a node to its rep node based on SCC detection
 */
void Andersen::mergeNodeToRep(NodeID nodeId,NodeID newRepId)
{
 
    if (mergeSrcToTgt(nodeId,newRepId))
        consCG->setPWCNode(newRepId);
}
 
/*
 * Updates subnodes of its rep, and rep node of its subs
 */
void Andersen::updateNodeRepAndSubs(NodeID nodeId, NodeID newRepId)
{
    consCG->setRep(nodeId,newRepId);
    NodeBS repSubs;
    repSubs.set(nodeId);
    //  update nodeToSubsMap, union its subs with its rep Subs
    NodeBS& nodeSubs = consCG->sccSubNodes(nodeId);
    for(NodeBS::iterator sit = nodeSubs.begin(), esit = nodeSubs.end(); sit!=esit; ++sit)
    {
        NodeID subId = *sit;
        consCG->setRep(subId,newRepId);
    }
    repSubs |= nodeSubs;
    consCG->setSubs(newRepId,repSubs);
    consCG->resetSubs(nodeId);
}
 
NodeBS Andersen::getMayAliases(NodeID node)
{
    // Reuse this expansion for the index lookup and, when necessary, every
    // comparison in the exhaustive fallback.
    PointsTo expandedPts;
    expandFIObjs(getPts(node), expandedPts);
    if (auto aliases = collectMayAliasesFromIndex(expandedPts))
        return std::move(*aliases);
 
    NodeBS aliases;
    const bool queryPointsToBlackHole = containBlackHoleNode(expandedPts);
    for (SVFIR::iterator it = pag->begin(), eit = pag->end(); it != eit; ++it)
    {
        const NodeID candidate = it->first;
        if (queryPointsToBlackHole)
        {
            aliases.set(candidate);
            continue;
        }
 
        PointsTo candidatePts;
        expandFIObjs(getPts(candidate), candidatePts);
        if (containBlackHoleNode(candidatePts) ||
                expandedPts.intersects(candidatePts))
            aliases.set(candidate);
    }
    return aliases;
}
 
std::optional<NodeBS> Andersen::collectMayAliasesFromIndex(const PointsTo& expandedPts)
{
    if (!getPTDataTy()->hasReversePts() || containBlackHoleNode(expandedPts))
        return std::nullopt;
 
    NodeBS objects;
    const u32_t nodeBound = pag->getTotalNodeNum();
    for (NodeID object : expandedPts)
    {
        objects.set(object);
        const NodeID base = pag->getBaseObjVarID(object);
        objects.set(base);
        if (isFieldInsensitive(base))
            objects |= pag->getAllFieldsObjVars(base);
    }
    objects.set(pag->getBlackHoleNode());
 
    const size_t wordCount = (static_cast<size_t>(nodeBound) +
                              CoreBitVector::WordSize - 1) / CoreBitVector::WordSize;
    CoreBitVector representatives(wordCount);
    for (NodeID object : objects)
    {
        for (NodeID key : getRevPts(object))
        {
            const NodeID representative = sccRepNode(key);
            // Reverse points-to sets can retain stale postings. Confirm the
            // posting with one current-set bit test before treating it as an
            // alias witness, unless an earlier object already confirmed it.
            if (!representatives.test(representative) &&
                    getPts(representative).test(object))
                representatives.set(representative);
        }
    }
 
    // SCC subnode sets are individually ordered, but their concatenation is
    // not globally ordered. Collect them densely before inserting into the
    // sparse result, where backward insertions would be costly.
    CoreBitVector answer(wordCount);
    for (NodeID representative : representatives)
    {
        for (NodeID subNode : sccSubNodes(representative))
            answer.set(subNode);
    }
 
    // normalizePointsTo can remove field nodes while their ids remain in
    // points-to sets. Do not return those stale nodes.
    NodeBS aliases;
    for (NodeID id : answer)
    {
        if (pag->hasGNode(id))
            aliases.set(id);
    }
    return aliases;
}
 
void Andersen::validateSuccessTests(std::string fun)
{
    AndersenBase::validateSuccessTests(fun);
 
    PointerAnalysis* pta = this;
    const FunObjVar* checkFun = pag->getFunObjVar(fun);
    if (!checkFun)
        return;
    for (const CallICFGNode* callNode : pag->getCallSiteSet())
    {
        if (callNode->getCalledFunction() != checkFun)
            continue;
        for (u32_t i = 0; i < callNode->arg_size(); ++i)
        {
            NodeID ptr = callNode->getArgument(i)->getId();
            NodeBS expected;
            for (SVFIR::iterator it = pag->begin(), eit = pag->end(); it != eit; ++it)
            {
                if (mayAlias(ptr, it->first))
                    expected.set(it->first);
            }
            if (pta->getMayAliases(ptr) == expected)
                outs() << sucMsg("\t SUCCESS :") << "getMayAliases check <id:" << ptr << "> at ("
                       << callNode->getSourceLoc() << ")\n";
            else
            {
                SVFUtil::errs() << errMsg("\t FAILURE :") << "getMayAliases check <id:" << ptr
                                << "> at (" << callNode->getSourceLoc() << ")\n";
                assert(false && "getMayAliases disagrees with mayAlias!");
            }
        }
    }
}
 
void Andersen::cluster(void) const
{
    assert(Options::MaxFieldLimit() == 0 && "Andersen::cluster: clustering for Andersen's is currently only supported in field-insensitive analysis");
    Steensgaard *steens = Steensgaard::createSteensgaard(pag);
    std::vector<std::pair<unsigned, unsigned>> keys;
    for (SVFIR::iterator pit = pag->begin(); pit != pag->end(); ++pit)
    {
        keys.push_back(std::make_pair(pit->first, 1));
    }
 
    std::vector<std::pair<hclust_fast_methods, std::vector<NodeID>>> candidates;
    PointsTo::MappingPtr nodeMapping =
        std::make_shared<std::vector<NodeID>>(
            NodeIDAllocator::Clusterer::cluster(steens, keys, candidates, "aux-steens", print_stat)
        );
    PointsTo::MappingPtr reverseNodeMapping =
        std::make_shared<std::vector<NodeID>>(NodeIDAllocator::Clusterer::getReverseNodeMapping(*nodeMapping));
 
    PointsTo::setCurrentBestNodeMapping(nodeMapping, reverseNodeMapping);
}
 
void Andersen::dumpTopLevelPtsTo()
{
    for (OrderedNodeSet::iterator nIter = this->getAllValidPtrs().begin();
            nIter != this->getAllValidPtrs().end(); ++nIter)
    {
        const SVFVar* node = getPAG()->getSVFVar(*nIter);
        if (getPAG()->isValidTopLevelPtr(node))
        {
            const PointsTo& pts = this->getPts(node->getId());
            outs() << "\nNodeID " << node->getId() << " ";
 
            if (pts.empty())
            {
                outs() << "\t\tPointsTo: {empty}\n";
            }
            else
            {
                outs() << "\t\tPointsTo: { ";
 
                multiset<u32_t> line;
                for (PointsTo::iterator it = pts.begin(), eit = pts.end();
                        it != eit; ++it)
                {
                    line.insert(*it);
                }
                for (multiset<u32_t>::const_iterator it = line.begin(); it != line.end(); ++it)
                {
                    if(Options::PrintFieldWithBasePrefix())
                        if (auto gepNode = pag->getGepObjVar(*it))
                            outs() << gepNode->getBaseNode() << "_" << gepNode->getConstantFieldIdx() << " ";
                        else
                            outs() << *it << " ";
                    else
                        outs() << *it << " ";
                }
                outs() << "}\n";
            }
        }
    }
 
    outs().flush();
}