Iterative-Epoch Online Cycle Elimination for Context-Free Language Reachability
summary
An iterative-epoch framework identifies grammar transitive symbols and collapses on-the-fly cycles in CFL-reachability graphs, reducing worklist blowup and graph size. Implemented with both unordered and ordered solvers and evaluated on SPEC 2017 value-flow and capital benchmark alias tasks, it runs ~9.7 epochs (value-flow) and ~6.4 epochs (alias) to collapse cycles and delivers up to 17.17× and 13.94× speedups on the standard solver with 48.8%/45.0% memory cuts, and 14.32×/8.36× with 55.2%/57.8% memory savings on the ordered solver.
AI-written summary · about
chapters (18)
- 0:00Introduction
- 0:22Problem and motivation
- 1:05Context-free language reachability
- 2:31Program analysis applications
- 3:13Standard dynamic algorithms
- 4:37Grammar normalization
- 5:20Dynamic solving process
- 6:33Cycle problem
- 6:55Cycle elimination motivation
- 7:38Iterative-Epoch Online Cycle Elimination
- 8:43Algorithm design differences
- 9:27Collapsing cycles and steps
- 9:49Beyond CFL reachability
- 10:10Evaluation setup
- 10:31Nodes and edges reduction
- 11:15Performance improvements
- 11:39Redundancy reduction
- 12:24Q&A
related talks
15mRecursive State Machine Guided Graph Folding for Context-Free Language Reachability
19mContext-Free Language Reachability via Skewed Tabulation
14mFast Client-Driven CFL-Reachability via Regularization-Based Graph Simplification
17mA Better Approximation for Interleaved Dyck Reachability
15mDetecting and explaining (in-)equivalence of context-free grammars
15mFaster Reachability Analysis for LR(1) Parsers
24mOptimism in Equality Saturation
25mA Semi-Persistent E-Graph with Native AC Canonization and Leapfrog AC Matching.