Andersen's Pointer Analysis

andersens pointer analysis

StatementInclusion Constraint
a = bPointsToSet(b) ⊆ PointsToSet(a)
a = &bb ∈ PointsToSet(a)
a = *b∀c ∈ PointsToSet(b): PointsToSet(c) ⊆ PointsToSet(a)
*a = b∀c ∈ PointsToSet(a): PointsToSet(b) ⊆ PointsToSet(c)
InputsDescription
Aa set of n pointers
Sa set of m statements

m ≤ 4*n^2 unique statements

OutputDescription
ExhaustiveReturn PointsToSet(a) for all pointers a ∈ A
On-demandReturn if b ∈ PointsToSet(a) for a specific pair a, b ∈ A

  1. [POPL 2021] The Fine-Grained and Parallel Complexity of Andersen's Pointer Analysis
Last updated: February 12, 2023