Incrementalizing Lattice-Based Program Analyses in Datalog

Tamas Szabo, Gábor Bergmann, Sebastian Erdweg, Markus Voelter

Research output: Contribution to journalArticleScientificpeer-review

14 Citations (Scopus)
33 Downloads (Pure)


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.
Original languageEnglish
Article number139
Pages (from-to)1-29
Number of pages29
JournalProceedings of the ACM on Programming Languages
Issue numberOOPSLA
Publication statusPublished - 2018

Fingerprint Dive into the research topics of 'Incrementalizing Lattice-Based Program Analyses in Datalog'. Together they form a unique fingerprint.

Cite this