Cycles in Field Sensitive Pointer Analysis

In the original Field-Sensitive paper by Pearce, this problem was described as the Positive Weight Cycle problem. Let’s first look at this problem as formulated in the original paper.

Consider the following C code, that has a void* pointer.

typedef struct { int *f1; int *f2; } aggr;

int main(void) {

    aggr a, *p; void *q;

    q = &a; // q {a}

    p = q; // p ⊇ q

    q = &(p->f2); // q ⊇ p + 1

    // do stuff with q

    return 0;

}

This leads to a weighted cycle — p → q, q — 1 → p. Unlike non-weighted cycles, the nodes in a weighted cycle don’t share the same solution, and it can lead to infinite derivations. 

For example, 

q = {a}

p = {a}

q = {a, r}, where r is the field at the index 1 from the base object a.

Then, because it’s a cycle, the derivation continues,

p = {a, r}
q = {a, r, s}, where s is the field at the index 1 from the base object r.

So on and so forth. Pearce et.al. basically puts a limit to these derivations, and say that the maximum number of fields we’ll support is N.

Leave a Reply