Incrementalizing Lattice-Based Program Analyses in Datalog
summary
Presents DRedL, an algorithm that incrementalizes recursive lattice-value aggregation in Datalog and integrates it into the IncA framework, enabling strong-update points-to and string analyses for Java that update in a few milliseconds after edits. Key idea is detecting increasing replacements so deletions that are subsumed by new lattice values avoid expensive rollback. Initial analysis costs 6s–1min on 4 Java codebases (up to 70k LOC); incremental updates are orders of magnitude faster and preserve exactness.
AI-written summary · about