Write a flow and field insensitive pointer analysis

Remember that we need a graph, a solver and a set of analysis rules to implement a pointer analysis. Let us take a look at a simple flow- and field-insensitive inclusion-based pointer analysis implementation. You can simply write it in just around 100 lines of core code. You may also wish to refer to Andersen.h and Andersen.cpp for more detailed implementations.

1. Build a constraint graph from PAG:

PointerAnalysis::initialize(module);
consCG = new ConstraintGraph(pag);

2. Write a naive constraint solver (for more complex solvers, e.g., wave propagation, please refer to AndersenWave.cpp and AndersenWaveDiff.cpp):

while (!isWorklistEmpty()) {

    NodeID nodeId = popFromWorklist();

    /// process address PAG Edge
    for (ConstraintNode::const_iterator it = node->outgoingAddrsBegin(), eit =
                node->outgoingAddrsEnd(); it != eit; ++it) {
        processAddr(*it);
    }

    /// process Load/Store PAG Edge
    for (PointsTo::iterator piter = getPts(nodeId).begin(), epiter =
                getPts(nodeId).end(); piter != epiter; ++piter) {
        NodeID ptd = *piter;

        for (ConstraintNode::const_iterator it = node->outgoingLoadsBegin(),
                eit = node->outgoingLoadsEnd(); it != eit; ++it) {
            processLoad(ptd, *it);
        }

        for (ConstraintNode::const_iterator it = node->incomingStoresBegin(),
                eit = node->incomingStoresEnd(); it != eit; ++it) {
            processStore(ptd, *it);
        }
    }

    // process copy
    for (ConstraintNode::const_iterator it = node->directOutEdgeBegin(), eit =
                node->directOutEdgeEnd(); it != eit; ++it) {
            processCopy(nodeId, *it);
    }
}

3. Write rules for handling different constraints:

/*!
 * Process address edges
 * src --addr --> dst
 * pts(dst) |= {src}
 */
void Andersen::processAddr(const AddrCGEdge* addr) {
    if(addPts(addr->getDstID(),addr->getSrcID()))
        pushIntoWorklist(dst);
}

/*!
 * Process load edges
 *	src --load--> dst,
 *	node \in pts(src) ==>  node--copy-->dst
 */
void Andersen::processLoad(NodeID node, const ConstraintEdge* load) {
    return addCopyEdge(node, load->getDstID());
}

/*!
 * Process store edges
 *	src --store--> dst,
 *	node \in pts(dst) ==>  src--copy-->node
 */
void Andersen::processStore(NodeID node, const ConstraintEdge* store) {
    return addCopyEdge(store->getSrcID(), node);
}

/*!
 * Process copy edges
 *	node --copy--> dst,
 *	union pts(dst) with pts(node)
 */
void Andersen::processCopy(NodeID node, const ConstraintEdge* edge) {
    PointsTo& srcPts = getPts(node);
    bool changed = unionPts(edge->getDstID(),srcPts);
    if (changed)
        pushIntoWorklist(dst);
}