Sparrow Pointer Analysis — Inclusion AA

Overview

SparrowAA is an inclusion-based points-to analysis.

Location: lib/Alias/SparrowAA
Algorithm: Inclusion/subset-based pointer analysis with constraint graph construction and worklist-based solving.
Typical Use: Fast whole-program call-graph and mod/ref precomputation

Analysis Modes

Flow-insensitive, context-insensitive (CI)
Flow-insensitive, context-sensitive (1-CFA, 2-CFA)

Constraint Types

The analysis builds a constraint graph over program pointers using standard pointer constraints:

p = &x → address-of constraint
p = q → copy constraint
p = *q → load constraint
*p = q → store constraint
p = &x->field / GEP → field/offset constraint

After collecting constraints, a worklist-based solver propagates points-to sets until a fixed point is reached.

Optimizations

The implementation supports several optional optimizations (see the README in lib/Alias/SparrowAA for details):

HVN / HU – Hash-based value numbering and Heintze–Ullman style equivalence to collapse redundant nodes.
HCD / LCD – Hybrid and lazy cycle detection to identify strongly connected components and speed up convergence.

Optimizations (optional, disabled by default): * HVN / HU – Hash-based value numbering and Heintze–Ullman style equivalence * HCD / LCD – Hybrid and lazy cycle detection for SCC identification

All optimizations are disabled by default and can be enabled via tool-specific command-line flags.

Features

Inclusion-based algorithm
Fast analysis for large codebases
Supports multiple context sensitivities
Optional optimizations for improved performance

Usage

The engine is wrapped as a reusable AA component and also exposed via a standalone tool:

./build/bin/sparrow-aa example.bc

In integrated settings (e.g., Clam or LotusAA), it can be selected through the corresponding configuration files or command-line switches.

Note: this module have some redundancies with aserpta, and reuses some header files from it (from context abstraction).