Fast Client-Driven CFL-Reachability via Regularization-Based Graph Simplification

Learn about MoYe, a novel regularization-based graph simplification technique that significantly enhances the performance of client-driven context-free language (CFL) reachability analyses in this 14-minute conference presentation from OOPSLA 2025. Discover how this innovative approach addresses the computational challenges of CFL-reachability, which typically suffers from cubic or near-cubic time complexity that degrades performance in client applications. Explore the core methodology behind MoYe's ability to prune non-contributing edges—those that don't participate in specified CFL-reachable paths—while maintaining exact reachability results for all designated node pairs. Understand how the technique employs regular approximation and operates with linear complexity relative to the number of graph edges, making it an efficient preprocessing step that substantially reduces both computational time and memory requirements. Examine the evaluation results demonstrating MoYe's superior performance compared to existing graph simplification approaches and its practical benefits in two prominent CFL-reachability client applications. Gain insights into how this lightweight optimization technique can be integrated as a valuable preprocessing step to improve resource consumption and overall analysis performance in real-world program analysis scenarios where clients require reachability information only for specific source-to-sink pairs.