An Incremental Algorithm for Algebraic Program Analysis
summary
Method builds an API tree data structure that linearizes CFGs so edits map to leaf insert/delete/update and interpretation values are updated by traversing changed leaf-to-root paths; deletions are handled lazily by assigning the unit element and periodic rebalancing keeps the tree small. Implementation runs on 13 DaCapo Java apps and measures three edit classes; incremental interpretation plus expression updates yield dramatic speedups, reported between 160X–4761X over nonincremental baselines.
AI-written summary · about
chapters (10)
- 0:00Incremental algebraic analysis intro
- 1:27Why incremental analysis matters
- 4:20Challenges in incremental APA
- 6:28Motivation for incremental design
- 8:13Three innovations for APA
- 9:55Building the API tree
- 11:42Handling incremental changes
- 13:51Lazy deletion and tree balancing
- 14:55Experimental evaluation
- 17:44Q&A
related talks
42mFrom Linear to Incremental
17mEfficient Bottom-Up Synthesis for Programs with Local Variables
01h 05mFrom meta frameworks and transformations to distributed computing and more
27mTaming Unsoundness with Gradual Abstract Interpretation
14mFast Incremental PEG Parsing
20mInteractive Abstract Interpretation with Demanded Summarization
37mA Tour of Program Optimization
19mIncremental Computation for Efficient Programmable Inference in Probabilistic Programs