Scholarlink

<p>Context-free language (CFL) reachability is a fundamental computational framework for formulating key static analyses (e.g., alias analysis, value-flow analysis, and points-to analysis) as well as some other graph analysis problems. Achieving high performance in universal CFL-reachability solvers remains a significant challenge. Specialized tools such as <span>Pearl</span> and <span>Gigascale</span> are optimized for specific CFLs but lack general applicability, whereas existing universal CFL-reachability solvers often do not scale well in important cases. In particular, prior efforts to leverage high-performance linear algebra operations in universal CFL-reachability solvers produced a matrix-based solver, <span>MatrixCFPQ</span>, that excels at performing common navigational queries on RDF graphs (which are unrelated to program analysis) but is inefficient when it comes to modeling static analyses. In this work, we introduce <span>FastMatrixCFPQ</span>, a universal matrix-based CFL-reachability solver that overcomes the limitations of <span>MatrixCFPQ</span> by leveraging the properties of the CFL-semiring, common patterns in context-free grammars, and the features of the SuiteSparse:GraphBLAS sparse linear algebra library. We prove that the optimized matrix-based algorithm for CFL-reachability has a worst-case running time of <InlineEquation ID="IEq1"> <EquationSource Format="MATHML"><math> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>3</mn> </msup> <mo stretchy="false">)</mo> </math></EquationSource> <EquationSource Format="TEX">$\mathcal{O}(n^{3})$</EquationSource> </InlineEquation> in the number of graph vertices <InlineEquation ID="IEq2"> <EquationSource Format="MATHML"><math> <mi>n</mi> </math></EquationSource> <EquationSource Format="TEX">$n$</EquationSource> </InlineEquation>. Our experimental results demonstrate that <span>FastMatrixCFPQ</span> outperforms the state-of-the-art universal CFL-reachability solvers across five client analyses—often by orders of magnitude—and, in many cases, even surpasses the speed of specialized solvers designed for specific CFLs.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

FastMatrixCFPQ: an efficient linear-algebra-based approach to CFL-reachability

  • 期刊论文

  • 发表日期：

    2026年5月21日

查看全文
  • Ilia Muravev,
  • Semyon Grigorev

摘要

Context-free language (CFL) reachability is a fundamental computational framework for formulating key static analyses (e.g., alias analysis, value-flow analysis, and points-to analysis) as well as some other graph analysis problems. Achieving high performance in universal CFL-reachability solvers remains a significant challenge. Specialized tools such as Pearl and Gigascale are optimized for specific CFLs but lack general applicability, whereas existing universal CFL-reachability solvers often do not scale well in important cases. In particular, prior efforts to leverage high-performance linear algebra operations in universal CFL-reachability solvers produced a matrix-based solver, MatrixCFPQ, that excels at performing common navigational queries on RDF graphs (which are unrelated to program analysis) but is inefficient when it comes to modeling static analyses. In this work, we introduce FastMatrixCFPQ, a universal matrix-based CFL-reachability solver that overcomes the limitations of MatrixCFPQ by leveraging the properties of the CFL-semiring, common patterns in context-free grammars, and the features of the SuiteSparse:GraphBLAS sparse linear algebra library. We prove that the optimized matrix-based algorithm for CFL-reachability has a worst-case running time of O ( n 3 ) $\mathcal{O}(n^{3})$ in the number of graph vertices n $n$ . Our experimental results demonstrate that FastMatrixCFPQ outperforms the state-of-the-art universal CFL-reachability solvers across five client analyses—often by orders of magnitude—and, in many cases, even surpasses the speed of specialized solvers designed for specific CFLs.