Write a flow and field insensitive pointer analysis

Remember that we need a graph, a solver and 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.cpp for more detailed implementations).

1. Build Constraint Graph using PAG

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

2. Write a naive constraint solver

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);
}