Taming Transitive Redundancy for Context-Free Language Reachability

on YouTube ↗15m

" summary

CFL-reachability uses on-the-fly edge derivation; this work introduces POCR running on a hybrid spanning-tree + adjacency-list representation to enforce a partial order on derivations so each summary edge is produced once. The implementation eliminates about 98.50% and 97.26% of redundant derivations for value-flow and alias analyses, yields 21.48× and 19.57× speedups over the standard algorithm, and is ≈3.67× faster than Graspan and Souffle on the evaluated C/C++ SPEC CPU2017 workloads.

AI-written summary · about

" chapters (9)

1. 0:00Transitive redundancy in CFA
2. 0:26Context-free reachability background
3. 3:19Limitations of standard CFA
4. 5:28Eliminating transitive redundancy
5. 6:11Hybrid data structure for redundancy
6. 8:45Partially ordered CFA algorithm
7. 12:46Grammar-based optimizations
8. 13:27Performance gains evaluation
9. 14:34Implementation and resources