一句话：提出 MoYe，用正则近似简化图并剪除无用边，在保证指定点对可达性精确的前提下加速客户端驱动的 CFL 可达性分析。
CFL 可达性是许多程序分析的核心框架，但其三次或近三次时间复杂度常导致客户端应用性能显著下降。实际中客户端往往只关心特定源—汇节点对的可达性，这带来了定向优化机会。本文提出 MoYe，一种基于正则化的图简化技术：先对 CFL 进行正则近似，识别并剪除不参与任何指定 CFL 可达路径的边，同时保证所有指定节点对的精确可达结果；该过程关于边数线性运行，可作为轻量预处理。在两类主流 CFL 可达性客户端应用上的评估表明，MoYe 显著降低时间与内存开销，并优于近期领先的图简化方法。
Context-free language (CFL) reachability is a critical framework for various program analyses, widely adopted despite its computational challenges due to cubic or near-cubic time complexity. This often leads to significant performance degradation in client applications. Notably, in real-world scenarios, clients typically require reachability information only for specific source-to-sink pairs, offering opportunities for targeted optimization. We introduce MoYe, an effective regularization-based graph simplification technique designed to enhance the performance of client-driven CFL-reachability analyses by pruning non-contributing edges—those that do not participate in any specified CFL-reachable paths. MoYe employs a regular approximation to ensure exact reachability results for all designated node pairs and operates linearly with respect to the number of edges in the graph. This lightweight efficiency makes MoYe a valuable pre-processing step that substantially reduces both computational time and memory requirements for CFL-reachability analysis, outperforming a recent leading graph simplification approach. Our evaluations with two prominent CFL-reachability client applications demonstrate that MoYe can substantially improve performance and reduce resource consumption.
@article{paperbot3022,
title = {Fast Client-Driven CFL-Reachability via Regularization-Based Graph Simplification},
author = {Chenghang Shi and Dongjie He and Haofeng Li and Jie Lu and Lian Li and Jingling Xue},
journal = {Proceedings of the ACM on Programming Languages},
volume = {9},
number = {OOPSLA2},
year = {2025},
doi = {10.1145/3763065}
}