一句话：提出通用增量算法 IncIDFA，可精确高效地增量更新任意单调迭代数据流分析。
迭代数据流分析是编译器优化、理解与验证等任务的重要静态分析。程序变换会使已有数据流解失效，穷尽重算代价高，而现有增量方法常损失精度、难以处理任意格与数据流函数，或需要人工定制。IncIDFA 是一种针对任意单调迭代数据流分析的通用增量算法，采用两遍方法维持精度，并在处理强连通区域和任意程序变更时避免将数据流解重置为最不精确值。作者形式化证明了其对任意数据流问题与程序变更的精度保证，并在 IMOP 编译器中面向 OpenMP C 实现，无需额外增量代码即可实例化十种分析。在两种架构的真实优化 pass 上，其增量更新时间最高加速 11 倍（几何平均 2.6 倍），总编译时间最高改善 46%（几何平均 15.1%）。
Iterative dataflow analyses (IDFAs) are important static analyses employed by tools like compilers for enabling program optimizations, comprehension, verification, and more. During compilation of a program, optimizations/transformations can render existing dataflow solutions stale, jeopardizing the optimality and correctness of subsequent compiler passes. Exhaustively recomputing these solutions can be costly. Since most program changes impact only small portions of the flowgraph, several incrementalization approaches have been proposed for various subclasses of IDFAs. However, these approaches face one or more of these limitations: (i) loss of precision compared to exhaustive analysis, (ii) inability to handle arbitrary lattices and dataflow functions, and (iii) lacking fully automated incrementalization of the IDFA. As a result, mainstream compilers lack frameworks for generating precise incremental versions of arbitrary IDFAs, leaving analysis writers to create ad hoc algorithms for incrementalization – an often cumbersome and error-prone task. To tackle these challenges, we introduce IncIDFA , a novel algorithm that delivers precise and efficient incremental variants of any monotone IDFA. IncIDFA utilizes a two-pass approach to maintain precision. Unlike prior works, IncIDFA avoids resetting the dataflow solutions to least informative values when dealing with strongly-connected regions and arbitrary program changes. We formally prove the precision guarantees of IncIDFA for arbitrary dataflow problems and program changes. IncIDFA has been implemented in the IMOP compiler framework for parallel OpenMP C programs. To showcase its generality, we have instantiated IncIDFA to ten specific dataflow analyses, without requiring any additional code for incrementalization. We present an evaluation of IncIDFA on a real-world set of optimization passes, across two different architectures. As compared to exhaustive recomputation, IncIDFA resulted in a speedup of up to 11× (geomean 2.6×) in incremental-update time, and improvement of up to 46% (geomean 15.1%) in the total compilation time.
@article{paperbot3201,
title = {IncIDFA: An Efficient and Generic Algorithm for Incremental Iterative Dataflow Analysis},
author = {Aman Nougrahiya and V. Krishna Nandivada},
journal = {Proceedings of the ACM on Programming Languages},
volume = {9},
number = {OOPSLA1},
year = {2025},
doi = {10.1145/3720436}
}