Recursive State Machine Guided Graph Folding for Context-Free Language Reachability

Explore a 15-minute conference talk from PLDI 2023 that presents an innovative approach to improving the scalability of context-free language reachability (CFL-reachability) in program analysis. Learn about a novel graph folding technique guided by recursive state machines (RSMs) that significantly reduces input graph size without affecting CFL-reachability results. Discover how this method identifies foldable node pairs by examining only their incoming and outgoing edges, leading to substantial performance improvements in alias analysis and value-flow analysis. Gain insights into the linear time complexity algorithm and its impressive results, including average reductions of up to 60.96% in graph nodes and 42.67% in edges, resulting in speedups of up to 4.65× and memory usage reductions of up to 65.19%.

[PLDI'23] Recursive State Machine Guided Graph Folding for Context-Free Language Reachability