Accelerating Program Analyses in Datalog by Merging Library Facts
summary
Proposes 4DM, a Datalog transformation that inserts Abstract relations to merge sensitivity-domain values (e.g., contexts) so analyses run fewer times while remaining sound and monotone; learns per-library merging heuristics offline from DaCapo training programs with a greedy ActiveCoarsen-like algorithm; evaluates on points-to and liveness analyses with a Mahjong baseline and reports up to negligible precision loss (≤3% for points-to, average 4.9% for liveness) and an average 19.8% speed-up while eliminating per-program preanalysis.
AI-written summary · about
chapters (9)
- 0:00Intro
- 0:21Motivation Balancing between precision and scalability in program analysis
- 1:43Existing Work
- 2:49Our Contributions 4DM: Data-Driven Datalog Domain-wise Merging
- 8:03Learning Merging Heuristics
- 9:51Evaluation Setup
- 10:47Evaluation: Points-to Analysis
- 11:58Evaluation: Liveness Analysis
- 12:14Conclusion Data-driven Datalog Domain-wise Merging
related talks
17mBring Your Own Data Structures to Datalog
17mInteractive Debugging of Datalog Programs
36mOptimizing Relational Programs II
41mOptimizing Relational Programs I
52mI See What You Mean
17mBetter Together: Unifying Datalog and Equality Saturation
15mUniversal Scalability in Declarative Program Analysis (with Choice-Based Combination(…)
26mDebugging Large-Scale Datalog: A Scalable Provenance Evaluation Strategy