Paper: IncSFS: Incremental Full-Sparse Flow-Sensitive Pointer Analysis for C/C++

From	John R Levine <johnl@taugh.com>
Newsgroups	comp.compilers
Subject	Paper: IncSFS: Incremental Full-Sparse Flow-Sensitive Pointer Analysis for C/C++
Date	2026-08-26 12:59 -0400
Organization	Compilers Central
Message-ID	<26-08-010@comp.compilers> (permalink)

Show all headers | View raw

Flow-sensitive pointer analysis is very effective but also very expensive.
This paper proposes a way to make it a lot cheaper.

Unlike a lot of recent papers, this one has nothing to do with LLMs.

Abstract
Pointer analysis is a fundamental technique for compiler optimization and
program analysis. Flow-sensitive pointer analysis provides high precision
but is difficult to scale to large projects. Tailored for rapid iteration
scenarios where software evolves continuously, we introduce IncSFS, the
first incremental full-sparse flow-sensitive pointer analysis algorithm
for C/C++ programs. IncSFS first transforms the value-flow graph into a
constraint graph and performs strongly connected component detection to
ensure precision. It then propagates increases and decreases in points-to
sets in an interleaved manner, supporting code deletion and insertion
within a single analysis pass. IncSFS is guaranteed to terminate and
compute the least fixed point when the points-to relation remains
object-acyclic during analysis. Experiments on six large-scale real-world
projects show that IncSFS is precise and efficient, achieving average
speedups of 9.60x over full flow-sensitive pointer analysis and 5.84x over
the traditional reset-recompute approach. It also improves efficiency by
15.8% over state-of-the-art incremental pointer analysis algorithms that
propagate points-to-set changes.

https://arxiv.org/abs/2608.24391

Regards,
John Levine, johnl@taugh.com, Taughannock Networks, Trumansburg NY
Please consider the environment before reading this e-mail. https://jl.ly

Back to comp.compilers | Previous | Next | Find similar | Unroll thread

Thread

Paper: IncSFS: Incremental Full-Sparse Flow-Sensitive Pointer Analysis for C/C++ John R Levine <johnl@taugh.com> - 2026-08-26 12:59 -0400

csiph-web