Incrementalizing lattice-based program analyses in Datalog
Tamás Szabó, Gábor Bergmann, Sebastian Thore Erdweg et al. · Proceedings of the ACM on Programming Languages · 2018
Program analyses detect errors in code, but when code changes frequently as in an IDE, repeated re-analysis from-scratch is unnecessary: It leads to poor performance unless we give up on precision and recall. Incremental program analysis promises to deliver fast feedback without giving up on precision or recall by deriving a new analysis result from the previous one. However, Datalog and other existing frameworks for incremental program analysis are limited in expressive power: They only support the powerset lattice as representation of analysis results, whereas many practically relevant analyses require custom lattices and aggregation over lattice values. To this end, we present a novel algorithm called DRedL that supports incremental maintenance of recursive lattice-value aggregation in Datalog. The key insight of DRedL is to dynamically recognize increasing replacements of old lattice values by new ones, which allows us to avoid the expensive deletion of the old value. We integrate DRedL into the analysis framework IncA and use IncA to realize incremental implementations of strong-update points-to analysis and string analysis for Java. As our performance evaluation demonstrates, both analyses react to code changes within milliseconds.
Cited by 52 works. doi:10.1145/3276509 Open-access PDF
Authors
References
- Rete: A fast algorithm for the many pattern/many object pattern match problem
- Introduction To Commutative Algebra
- Precise interprocedural dataflow analysis via graph reachability
- Principles of Program Analysis
- Maintaining views incrementally
- Maintenance of Materialized Views: Problems, Techniques, and Applications
- Maintenance of Materialized Views: Problems, Techniques, and Applications.
- Cloning-based context-sensitive pointer alias analysis using binary decision diagrams
- Efficient computation of flow insensitive interprocedural summary information
- What you always wanted to know about Datalog (and never dared to ask)