FlowSensitive.cpp

Go to the documentation of this file.

//===- FlowSensitive.cpp -- Sparse flow-sensitive pointer 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/>.
//
//===----------------------------------------------------------------------===//
 
/*
 * FlowSensitive.cpp
 *
 *  Created on: Oct 28, 2013
 *      Author: Yulei Sui
 */
 
#include "Util/Options.h"
#include "WPA/WPAStat.h"
#include "WPA/FlowSensitive.h"
#include "WPA/Andersen.h"
#include "MemoryModel/PointsTo.h"
 
using namespace SVF;
using namespace SVFUtil;
 
std::unique_ptr<FlowSensitive> FlowSensitive::fspta;
 
void FlowSensitive::initialize()
{
    PointerAnalysis::initialize();
 
    stat = new FlowSensitiveStat(this);
 
    // TODO: support clustered aux. Andersen's.
    assert(!Options::ClusterAnder() && "FlowSensitive::initialize: clustering auxiliary Andersen's unsupported.");
    ander = AndersenWaveDiff::createAndersenWaveDiff(getPAG());
 
    // If cluster option is not set, it will give us a no-mapping points-to set.
    assert(!(Options::ClusterFs() && Options::PlainMappingFs())
           && "FS::init: plain-mapping and cluster-fs are mutually exclusive.");
    if (Options::ClusterFs())
    {
        cluster();
        // Reset the points-to cache although empty so the new mapping could
        // be applied to the inserted empty set.
        getPtCache().reset();
    }
    else if (Options::PlainMappingFs())
    {
        plainMap();
        // As above.
        getPtCache().reset();
    }
 
    svfg = memSSA.buildPTROnlySVFG(ander);
 
    setGraph(svfg);
    //AndersenWaveDiff::releaseAndersenWaveDiff();
}
void FlowSensitive::solveConstraints()
{
    bool timeLimited = Options::FsTimeLimit() > 0;
    if (timeLimited)
    {
        SVFUtil::startAnalysisLimitTimer(Options::FsTimeLimit());
    }
 
    double start = stat->getClk(true);
    DBOUT(DGENERAL, outs() << SVFUtil::pasMsg("Start Solving Constraints\n"));
 
    do
    {
        numOfIteration++;
 
        if(0 == numOfIteration % OnTheFlyIterBudgetForStat)
            dumpStat();
 
        callGraphSCC->find();
 
        initWorklist();
        solveWorklist();
    }
    while (updateCallGraph(getIndirectCallsites()));
 
    DBOUT(DGENERAL, outs() << SVFUtil::pasMsg("Finish Solving Constraints\n"));
 
    // Reset the time-up alarm; analysis is done.
    if (timeLimited)
    {
        SVFUtil::stopAnalysisLimitTimer();
    }
 
    double end = stat->getClk(true);
    solveTime += (end - start) / TIMEINTERVAL;
 
}
 
void FlowSensitive::solveAndwritePtsToFile(const std::string& filename)
{
    initialize();
    if(!filename.empty())
        writeObjVarToFile(filename);
    solveConstraints();
    if(!filename.empty())
        writeToFile(filename);
    finalize();
}
 
void FlowSensitive::analyze()
{
    if(!Options::ReadAnder().empty())
    {
        readPtsFromFile(Options::ReadAnder());
    }
    else
    {
        if(Options::WriteAnder().empty())
        {
            initialize();
            solveConstraints();
            finalize();
        }
        else
        {
            solveAndwritePtsToFile(Options::WriteAnder());
        }
    }
}
 
void FlowSensitive::readPtsFromFile(const std::string& filename)
{
    initialize();
    if(!filename.empty())
        this->readFromFile(filename);
    finalize();
}
 
void FlowSensitive::finalize()
{
    if(Options::DumpVFG())
        svfg->dump("fs_solved", true);
 
    NodeStack& nodeStack = WPASolver<SVFG*>::SCCDetect();
    while (nodeStack.empty() == false)
    {
        NodeID rep = nodeStack.top();
        nodeStack.pop();
        const NodeBS& subNodes = getSCCDetector()->subNodes(rep);
        if (subNodes.count() > maxSCCSize)
            maxSCCSize = subNodes.count();
        if (subNodes.count() > 1)
        {
            numOfNodesInSCC += subNodes.count();
            numOfSCC++;
        }
    }
 
    // TODO: check -stat too.
    if (Options::ClusterFs())
    {
        Map<std::string, std::string> stats;
        const PTDataTy *ptd = getPTDataTy();
        // TODO: should we use liveOnly?
        Map<PointsTo, unsigned> allPts = ptd->getAllPts(true);
        // TODO: parameterise final arg.
        NodeIDAllocator::Clusterer::evaluate(*PointsTo::getCurrentBestNodeMapping(), allPts, stats, true);
        if (print_stat)
        {
            NodeIDAllocator::Clusterer::printStats("post-main: best", stats);
        }
    }
 
    BVDataPTAImpl::finalize();
}
 
NodeStack& FlowSensitive::SCCDetect()
{
    double start = stat->getClk();
    NodeStack& nodeStack = WPASVFGFSSolver::SCCDetect();
    double end = stat->getClk();
    sccTime += (end - start) / TIMEINTERVAL;
    return nodeStack;
}
 
void FlowSensitive::processNode(NodeID nodeId)
{
    SVFGNode* node = svfg->getSVFGNode(nodeId);
    if (processSVFGNode(node))
        propagate(&node);
 
    clearAllDFOutVarFlag(node);
}
 
bool FlowSensitive::processSVFGNode(SVFGNode* node)
{
    double start = stat->getClk();
    bool changed = false;
    if (AddrSVFGNode* addr = SVFUtil::dyn_cast<AddrSVFGNode>(node))
    {
        numOfProcessedAddr++;
        if (processAddr(addr))
            changed = true;
    }
    else if (CopySVFGNode* copy = SVFUtil::dyn_cast<CopySVFGNode>(node))
    {
        numOfProcessedCopy++;
        if (processCopy(copy))
            changed = true;
    }
    else if (GepSVFGNode* gep = SVFUtil::dyn_cast<GepSVFGNode>(node))
    {
        numOfProcessedGep++;
        if(processGep(gep))
            changed = true;
    }
    else if (LoadSVFGNode* load = SVFUtil::dyn_cast<LoadSVFGNode>(node))
    {
        numOfProcessedLoad++;
        if(processLoad(load))
            changed = true;
    }
    else if (StoreSVFGNode* store = SVFUtil::dyn_cast<StoreSVFGNode>(node))
    {
        numOfProcessedStore++;
        if (processStore(store))
            changed = true;
    }
    else if (PHISVFGNode* phi = SVFUtil::dyn_cast<PHISVFGNode>(node))
    {
        numOfProcessedPhi++;
        if (processPhi(phi))
            changed = true;
    }
    else if (SVFUtil::isa<MSSAPHISVFGNode, FormalINSVFGNode,
             FormalOUTSVFGNode, ActualINSVFGNode,
             ActualOUTSVFGNode>(node))
    {
        numOfProcessedMSSANode++;
        changed = true;
    }
    else if (SVFUtil::isa<ActualParmSVFGNode, FormalParmSVFGNode,
             ActualRetSVFGNode, FormalRetSVFGNode,
             NullPtrSVFGNode>(node))
    {
        changed = true;
    }
    else if (SVFUtil::isa<CmpVFGNode, BinaryOPVFGNode>(node) ||
             SVFUtil::dyn_cast<UnaryOPVFGNode>(node))
    {
    }
    else
    {
        assert(false && "unexpected kind of SVFG nodes");
    }
 
    double end = stat->getClk();
    processTime += (end - start) / TIMEINTERVAL;
 
    return changed;
}
 
bool FlowSensitive::propFromSrcToDst(SVFGEdge* edge)
{
    double start = stat->getClk();
    bool changed = false;
 
    if (DirectSVFGEdge* dirEdge = SVFUtil::dyn_cast<DirectSVFGEdge>(edge))
        changed = propAlongDirectEdge(dirEdge);
    else if (IndirectSVFGEdge* indEdge = SVFUtil::dyn_cast<IndirectSVFGEdge>(edge))
        changed = propAlongIndirectEdge(indEdge);
    else
        assert(false && "new kind of svfg edge?");
 
    double end = stat->getClk();
    propagationTime += (end - start) /TIMEINTERVAL;
    return changed;
}
 
bool FlowSensitive::propAlongDirectEdge(const DirectSVFGEdge* edge)
{
    double start = stat->getClk();
    bool changed = false;
 
    SVFGNode* src = edge->getSrcNode();
    SVFGNode* dst = edge->getDstNode();
    // If this is an actual-param or formal-ret, top-level pointer's pts must be
    // propagated from src to dst.
    if (ActualParmSVFGNode* ap = SVFUtil::dyn_cast<ActualParmSVFGNode>(src))
        changed = propagateFromAPToFP(ap, dst);
    else if (FormalRetSVFGNode* fp = SVFUtil::dyn_cast<FormalRetSVFGNode>(src))
        changed = propagateFromFRToAR(fp, dst);
    else
    {
        // Direct SVFG edge links between def and use of a top-level pointer.
        // There's no points-to information propagated along direct edge.
        // Since the top-level pointer's value has been changed at src node,
        // return TRUE to put dst node into the work list.
        changed = true;
    }
 
    double end = stat->getClk();
    directPropaTime += (end - start) / TIMEINTERVAL;
    return changed;
}
 
bool FlowSensitive::propagateFromAPToFP(const ActualParmSVFGNode* ap, const SVFGNode* dst)
{
    const FormalParmSVFGNode* fp = SVFUtil::dyn_cast<FormalParmSVFGNode>(dst);
    assert(fp && "expecting a formal param node");
 
    NodeID pagDst = fp->getParam()->getId();
    const PointsTo &srcCPts = getPts(ap->getParam()->getId());
    bool changed = unionPts(pagDst, srcCPts);
 
    return changed;
}
 
bool FlowSensitive::propagateFromFRToAR(const FormalRetSVFGNode* fr, const SVFGNode* dst)
{
    const ActualRetSVFGNode* ar = SVFUtil::dyn_cast<ActualRetSVFGNode>(dst);
    assert(ar && "expecting an actual return node");
 
    NodeID pagDst = ar->getRev()->getId();
    const PointsTo & srcCPts = getPts(fr->getRet()->getId());
    bool changed = unionPts(pagDst, srcCPts);
 
    return changed;
}
 
bool FlowSensitive::propAlongIndirectEdge(const IndirectSVFGEdge* edge)
{
    double start = stat->getClk();
 
    SVFGNode* src = edge->getSrcNode();
    SVFGNode* dst = edge->getDstNode();
 
    bool changed = false;
 
    // Get points-to targets may be used by next SVFG node.
    // Propagate points-to set for node used in dst.
    const NodeBS& pts = edge->getPointsTo();
    for (NodeBS::iterator ptdIt = pts.begin(), ptdEit = pts.end(); ptdIt != ptdEit; ++ptdIt)
    {
        NodeID ptd = *ptdIt;
 
        if (propVarPtsFromSrcToDst(ptd, src, dst))
            changed = true;
 
        if (isFieldInsensitive(ptd))
        {
            const NodeBS& allFields = getAllFieldsObjVars(ptd);
            for (NodeBS::iterator fieldIt = allFields.begin(), fieldEit = allFields.end();
                    fieldIt != fieldEit; ++fieldIt)
            {
                if (propVarPtsFromSrcToDst(*fieldIt, src, dst))
                    changed = true;
            }
        }
    }
 
    double end = stat->getClk();
    indirectPropaTime += (end - start) / TIMEINTERVAL;
    return changed;
}
 
bool FlowSensitive::propVarPtsFromSrcToDst(NodeID var, const SVFGNode* src, const SVFGNode* dst)
{
    bool changed = false;
    if (SVFUtil::isa<StoreSVFGNode>(src))
    {
        if (updateInFromOut(src, var, dst, var))
            changed = true;
    }
    else
    {
        if (updateInFromIn(src, var, dst, var))
            changed = true;
    }
    return changed;
}
 
bool FlowSensitive::processAddr(const AddrSVFGNode* addr)
{
    double start = stat->getClk();
    NodeID srcID = addr->getSrcNodeID();
    if (isFieldInsensitive(srcID))
        srcID = getFIObjVar(srcID);
    bool changed = addPts(addr->getDstNodeID(), srcID);
    double end = stat->getClk();
    addrTime += (end - start) / TIMEINTERVAL;
    return changed;
}
 
bool FlowSensitive::processCopy(const CopySVFGNode* copy)
{
    double start = stat->getClk();
    bool changed = unionPts(copy->getDstNodeID(), copy->getSrcNodeID());
    double end = stat->getClk();
    copyTime += (end - start) / TIMEINTERVAL;
    return changed;
}
 
bool FlowSensitive::processPhi(const PHISVFGNode* phi)
{
    double start = stat->getClk();
    bool changed = false;
    NodeID pagDst = phi->getRes()->getId();
    for (PHISVFGNode::OPVers::const_iterator it = phi->opVerBegin(), eit = phi->opVerEnd(); it != eit; ++it)
    {
        NodeID src = it->second->getId();
        const PointsTo& srcPts = getPts(src);
        if (unionPts(pagDst, srcPts))
            changed = true;
    }
 
    double end = stat->getClk();
    phiTime += (end - start) / TIMEINTERVAL;
    return changed;
}
 
bool FlowSensitive::processGep(const GepSVFGNode* edge)
{
    double start = stat->getClk();
    bool changed = false;
    const PointsTo& srcPts = getPts(edge->getSrcNodeID());
 
    PointsTo tmpDstPts;
    const GepStmt* gepStmt = SVFUtil::cast<GepStmt>(edge->getSVFStmt());
    if (gepStmt->isVariantFieldGep())
    {
        for (NodeID o : srcPts)
        {
            if (isBlkObjOrConstantObj(o))
            {
                tmpDstPts.set(o);
                continue;
            }
 
            setObjFieldInsensitive(o);
            tmpDstPts.set(getFIObjVar(o));
        }
    }
    else
    {
        for (NodeID o : srcPts)
        {
            if (isBlkObjOrConstantObj(o) || isFieldInsensitive(o))
            {
                tmpDstPts.set(o);
                continue;
            }
 
            NodeID fieldSrcPtdNode = getGepObjVar(o, gepStmt->getAccessPath().getConstantStructFldIdx());
            tmpDstPts.set(fieldSrcPtdNode);
        }
    }
 
    if (unionPts(edge->getDstNodeID(), tmpDstPts))
        changed = true;
 
    double end = stat->getClk();
    gepTime += (end - start) / TIMEINTERVAL;
    return changed;
}
 
 
bool FlowSensitive::processLoad(const LoadSVFGNode* load)
{
    double start = stat->getClk();
    bool changed = false;
 
    NodeID dstVar = load->getDstNodeID();
 
    const PointsTo& srcPts = getPts(load->getSrcNodeID());
 
    // p = *q, the type of p must be a pointer
    if(load->getDstNode()->isPointer())
    {
        for (PointsTo::iterator ptdIt = srcPts.begin(); ptdIt != srcPts.end(); ++ptdIt)
        {
            NodeID ptd = *ptdIt;
 
            if (pag->isConstantObj(ptd))
                continue;
 
            if (unionPtsFromIn(load, ptd, dstVar))
                changed = true;
 
            if (isFieldInsensitive(ptd))
            {
                const NodeBS& allFields = getAllFieldsObjVars(ptd);
                for (NodeBS::iterator fieldIt = allFields.begin(), fieldEit = allFields.end();
                        fieldIt != fieldEit; ++fieldIt)
                {
                    if (unionPtsFromIn(load, *fieldIt, dstVar))
                        changed = true;
                }
            }
        }
    }
    double end = stat->getClk();
    loadTime += (end - start) / TIMEINTERVAL;
    return changed;
}
 
bool FlowSensitive::processStore(const StoreSVFGNode* store)
{
 
    const PointsTo & dstPts = getPts(store->getDstNodeID());
 
    if (dstPts.empty())
        return false;
 
    double start = stat->getClk();
    bool changed = false;
 
    // *p = q, the type of q must be a pointer
    if(getPts(store->getSrcNodeID()).empty() == false && store->getSrcNode()->isPointer())
    {
        for (PointsTo::iterator it = dstPts.begin(), eit = dstPts.end(); it != eit; ++it)
        {
            NodeID ptd = *it;
 
            if (pag->isConstantObj(ptd))
                continue;
 
            if (unionPtsFromTop(store, store->getSrcNodeID(), ptd))
                changed = true;
        }
    }
 
    double end = stat->getClk();
    storeTime += (end - start) / TIMEINTERVAL;
 
    double updateStart = stat->getClk();
    // also merge the DFInSet to DFOutSet.
    NodeID singleton;
    bool isSU = isStrongUpdate(store, singleton);
    if (isSU)
    {
        svfgHasSU.set(store->getId());
        if (strongUpdateOutFromIn(store, singleton))
            changed = true;
    }
    else
    {
        svfgHasSU.reset(store->getId());
        if (weakUpdateOutFromIn(store))
            changed = true;
    }
    double updateEnd = stat->getClk();
    updateTime += (updateEnd - updateStart) / TIMEINTERVAL;
 
    return changed;
}
 
bool FlowSensitive::isStrongUpdate(const SVFGNode* node, NodeID& singleton)
{
    bool isSU = false;
    if (const StoreSVFGNode* store = SVFUtil::dyn_cast<StoreSVFGNode>(node))
    {
        const PointsTo& dstCPSet = getPts(store->getDstNodeID());
        if (dstCPSet.count() == 1)
        {
            PointsTo::iterator it = dstCPSet.begin();
            singleton = *it;
 
            // Strong update can be made if this points-to target is not heap, array or field-insensitive.
            if (!isHeapMemObj(singleton) && !isArrayMemObj(singleton))
            {
                assert(pag->getBaseObject(singleton)->isFieldInsensitive() == pag->getBaseObject(singleton)->isFieldInsensitive());
                if (pag->getBaseObject(singleton)->isFieldInsensitive() == false
                        && !isLocalVarInRecursiveFun(singleton))
                {
                    isSU = true;
                }
            }
        }
    }
    return isSU;
}
 
bool FlowSensitive::updateCallGraph(const CallSiteToFunPtrMap& callsites)
{
    double start = stat->getClk();
    CallEdgeMap newEdges;
    onTheFlyCallGraphSolve(callsites, newEdges);
 
    // Bound the new edges by the Andersen's call graph.
    // TODO: we want this to be an assertion eventually.
    const CallEdgeMap &andersCallEdgeMap = ander->getIndCallMap();
    for (typename CallEdgeMap::value_type &csfs : newEdges)
    {
        const CallICFGNode *potentialCallSite = csfs.first;
        FunctionSet &potentialFunctionSet = csfs.second;
 
        // Check this callsite even calls anything per Andersen's.
        typename CallEdgeMap::const_iterator andersFunctionSetIt
            = andersCallEdgeMap.find(potentialCallSite);
        if (andersFunctionSetIt == andersCallEdgeMap.end())
        {
            potentialFunctionSet.clear();
        }
 
        const FunctionSet &andersFunctionSet = andersFunctionSetIt->second;
        for (FunctionSet::iterator potentialFunctionIt = potentialFunctionSet.begin();
                potentialFunctionIt != potentialFunctionSet.end(); )
        {
            const FunObjVar *potentialFunction = *potentialFunctionIt;
            if (andersFunctionSet.find(potentialFunction) == andersFunctionSet.end())
            {
                // potentialFunction is not in the Andersen's call graph -- remove it.
                potentialFunctionIt = potentialFunctionSet.erase(potentialFunctionIt);
            }
            else
            {
                // potentialFunction is in the Andersen's call graph -- keep it..
                ++potentialFunctionIt;
            }
        }
    }
 
    SVFGEdgeSetTy svfgEdges;
    connectCallerAndCallee(newEdges, svfgEdges);
 
    updateConnectedNodes(svfgEdges);
 
    double end = stat->getClk();
    updateCallGraphTime += (end - start) / TIMEINTERVAL;
    return (!newEdges.empty());
}
 
void FlowSensitive::connectCallerAndCallee(const CallEdgeMap& newEdges, SVFGEdgeSetTy& edges)
{
    CallEdgeMap::const_iterator iter = newEdges.begin();
    CallEdgeMap::const_iterator eiter = newEdges.end();
    for (; iter != eiter; iter++)
    {
        const CallICFGNode* cs = iter->first;
        const FunctionSet & functions = iter->second;
        for (FunctionSet::const_iterator func_iter = functions.begin(); func_iter != functions.end(); func_iter++)
        {
            const FunObjVar*  func = *func_iter;
            svfg->connectCallerAndCallee(cs, func, edges);
        }
    }
}
 
void FlowSensitive::updateConnectedNodes(const SVFGEdgeSetTy& edges)
{
    for (const SVFGEdge* edge : edges)
    {
        SVFGNode* dstNode = edge->getDstNode();
        if (SVFUtil::isa<PHISVFGNode>(dstNode))
        {
            pushIntoWorklist(dstNode->getId());
        }
        else if (SVFUtil::isa<FormalINSVFGNode, ActualOUTSVFGNode>(dstNode))
        {
            bool changed = false;
 
            SVFGNode* srcNode = edge->getSrcNode();
 
            const NodeBS& pts = SVFUtil::cast<IndirectSVFGEdge>(edge)->getPointsTo();
            for (NodeBS::iterator ptdIt = pts.begin(), ptdEit = pts.end(); ptdIt != ptdEit; ++ptdIt)
            {
                NodeID ptd = *ptdIt;
 
                if (propVarPtsAfterCGUpdated(ptd, srcNode, dstNode))
                    changed = true;
 
                if (isFieldInsensitive(ptd))
                {
                    const NodeBS& allFields = getAllFieldsObjVars(ptd);
                    for (NodeBS::iterator fieldIt = allFields.begin(), fieldEit = allFields.end();
                            fieldIt != fieldEit; ++fieldIt)
                    {
                        if (propVarPtsAfterCGUpdated(*fieldIt, srcNode, dstNode))
                            changed = true;
                    }
                }
            }
 
            if (changed)
                pushIntoWorklist(dstNode->getId());
        }
    }
}
 
 
bool FlowSensitive::propVarPtsAfterCGUpdated(NodeID var, const SVFGNode* src, const SVFGNode* dst)
{
    if (SVFUtil::isa<StoreSVFGNode>(src))
    {
        if (propDFOutToIn(src, var, dst, var))
            return true;
    }
    else
    {
        if (propDFInToIn(src, var, dst, var))
            return true;
    }
    return false;
}
 
void FlowSensitive::cluster(void)
{
    std::vector<std::pair<unsigned, unsigned>> keys;
    for (const auto& pair : *pag)
        keys.emplace_back(pair.first, 1);
 
    PointsTo::MappingPtr nodeMapping =
        std::make_shared<std::vector<NodeID>>(
            NodeIDAllocator::Clusterer::cluster(ander, keys, candidateMappings, "aux-ander", print_stat)
        );
    PointsTo::MappingPtr reverseNodeMapping =
        std::make_shared<std::vector<NodeID>>(NodeIDAllocator::Clusterer::getReverseNodeMapping(*nodeMapping));
 
    PointsTo::setCurrentBestNodeMapping(nodeMapping, reverseNodeMapping);
}
 
void FlowSensitive::plainMap(void) const
{
    assert(Options::NodeAllocStrat() == NodeIDAllocator::Strategy::DENSE
           && "FS::cluster: plain mapping requires dense allocation strategy.");
 
    const size_t numObjects = NodeIDAllocator::get()->getNumObjects();
    PointsTo::MappingPtr plainMapping = std::make_shared<std::vector<NodeID>>(numObjects);
    PointsTo::MappingPtr reversePlainMapping = std::make_shared<std::vector<NodeID>>(numObjects);
    for (NodeID i = 0; i < plainMapping->size(); ++i)
    {
        plainMapping->at(i) = i;
        reversePlainMapping->at(i) = i;
    }
 
    PointsTo::setCurrentBestNodeMapping(plainMapping, reversePlainMapping);
}
 
void FlowSensitive::countAliases(Set<std::pair<NodeID, NodeID>> cmp, unsigned *mayAliases, unsigned *noAliases)
{
    for (std::pair<NodeID, NodeID> locPA : cmp)
    {
        // loc doesn't make a difference for FSPTA.
        NodeID p = locPA.second;
        for (std::pair<NodeID, NodeID> locPB : cmp)
        {
            if (locPB == locPA) continue;
 
            NodeID q = locPB.second;
 
            switch (alias(p, q))
            {
            case AliasResult::NoAlias:
                ++(*noAliases);
                break;
            case AliasResult::MayAlias:
                ++(*mayAliases);
                break;
            default:
                assert("Not May/NoAlias?");
            }
        }
    }
 
}