Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #3747 > unrolled thread

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

Back to article view | Back to comp.compilers

Contents

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

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

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

[toc] | [standalone]

Back to top | Article view | comp.compilers

csiph-web