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

Return to the comp.compilers page.
Search the comp.compilers archives again.