IncIDFA: An Efficient and Generic Algorithm for Incremental Iterative Dataflow Analysis
summary
Algorithm IncIDFA produces precise incremental variants for any monotone IDFA using a two-pass approach plus per-SEC stabilization and safe/under-approximated sets to avoid global resets. It’s implemented in IMOP for OpenMP C, auto-instantiates ten classic analyses, and proves termination and precision. On 24 benchmarks it cuts nodes processed (as low as ~27–34%) and yields up to 11× incremental speedup (geomean 2.6×) and up to 46% total compilation improvement (geomean 15.1%).
AI-written summary · about
chapters (13)
- 0:00incIDFA for incremental dataflow analysis
- 1:01Why incremental updates matter
- 2:04Iterative dataflow analysis basics
- 3:29Stale solutions after transformations
- 4:11Limitations of restarting iterations
- 4:52incIDFA’s two-step approach
- 5:33Optimizing initialization sets
- 6:37Processing SCCs efficiently
- 8:00Formal proof and implementation
- 9:45Evaluation setup and benchmarks
- 10:28Performance gains over recomputation
- 11:30incIDFA’s precision and efficiency
- 11:52Opening the floor for questions
related talks
18mBoosting the Performance of Alias-Aware IFDS Analysis with CFL-based Environment(…)
19mAn Incremental Algorithm for Algebraic Program Analysis
16mTermination Analysis for Evolving Programs: An Incremental Approach by Reusing Certified Modules
15mAutomatic Synthesis of Data-Flow Analyzers
19mIncremental Computation for Efficient Programmable Inference in Probabilistic Programs
11mIDFuzz: Intelligent Directed Grey-box Fuzzing
24mIncremental Computation: What Is the Essence? (Invited Contribution)
50mRecent Advances in Floating-point (Static) Analyses