SIMD-Accelerated Sparse Bit-Vectors for Pointer Analysis

Abstract

Pointer analysis is a core component of program-analysis frameworks. Inclusion-based solvers repeatedly update points-to sets, and the resulting set operations frequently dominate end-to-end runtime. In existing sparse bit-vector representations, we find that the main cost is not bitmap arithmetic but irregular index matching: identifying allocation-site representatives shared by two operands before combining their corresponding blocks. We accelerate this kernel by recasting index matching as a branch-free SIMD primitive. The key is a sparse layout that stores allocation-site indices and their blocks in contiguous arrays, enabling parallel scans over indices and masked SIMD updates of blocks while preserving sparsity. We evaluate the technique on 12 real-world programs under both context-insensitive and context-sensitive variants. Compared to a conventional sparse bit-vector baseline, our approach reduces analysis time by up to 3.8× (geomean: 2.0×) and peak memory by up to 86% (geomean: 58%), with larger gains for more precise analyses. The improvements persist across alternative set representations and constraint solving strategies.