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

Path	csiph.com!weretis.net!feeder9.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From	John R Levine <johnl@taugh.com>
Newsgroups	comp.compilers
Subject	Paper: IncSFS: Incremental Full-Sparse Flow-Sensitive Pointer Analysis for C/C++
Date	Wed, 26 Aug 2026 12:59:34 -0400
Organization	Compilers Central
Sender	johnl%iecc.com
Approved	comp.compilers@iecc.com
Message-ID	<26-08-010@comp.compilers> (permalink)
MIME-Version	1.0
Content-Type	text/plain; charset="UTF-8"
Injection-Info	gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="44247"; mail-complaints-to="abuse@iecc.com"
Keywords	paper, analysis
Posted-Date	26 Aug 2026 13:01:53 EDT
X-submission-address	compilers@iecc.com
X-moderator-address	compilers-request@iecc.com
X-FAQ-and-archives	http://compilers.iecc.com
Xref	csiph.com comp.compilers:3747

Show key headers only | 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