This repository contains a Go adaptation of Steensgaard's pointer analysis algorithm. The result of the static analysis can be used to determine the set of objects that a variable may point to at run-time. It can also be used to construct a call graph where dynamically dispatched calls have been resolved using the computed points-to information.
The analysis is field-sensitive, context-insensitive, and aims to be sound.
Due to field-sensitivity the analysis cannot run in
This implementation makes many of the same design choices as the implementation of Andersen's algorithm. Notably, arrays (and slices) are modelled as having 1 element, conversions using unsafe.Pointer are not modelled soundly, and the effects of opaque code (runtime, Cgo, etc.) are under-approximated. The API is also similar.
Contrary to the implementation of Andersen's algorithm, no special modelling is offered for reflection (which is available under a flag there). Also, in this implementation constraint generation is interleaved with constraint solving. This makes it easy to only generate constraints for reachable code, which the Andersen implementation does not do.
The benchmark submodule contains some code for benchmarking the analysis against Andersen's pointer analysis on a few popular Go projects. It measures analysis time, analysis precision, and a couple of call graph metrics.
The benchmarking code is not mature nor rigorous. On my machine crunch.py outputs:
Benchmark results for 14 modules
Steensgaard stats:
Average analysis time: 2.22s
Average # of non-static edges: 65570.14
Average # of reachable functions: 12886.21
Andersen stats:
Average analysis time: 14.89s
Average # of non-static edges: 30481.00
Average # of reachable functions: 13160.00