Recursive State Machine Guided Graph Folding for Context-Free Language Reachability
Recursive State Machine Guided Graph Folding for Context-Free Language Reachability
复制标题
DOI：
10.1145/3591233
复制
发表时间：
2023-06
影响因子：
--
通讯作者：
Yuxiang Lei;Yulei Sui;Shin Hwei Tan;Qirun Zhang
中科院分区：
文献类型：
--
作者：
Yuxiang Lei;Yulei Sui;Shin Hwei Tan;Qirun Zhang
无上下文的语言意识（CFL可行性）是程序分析的基本框架。一条可及的路径，即，在给定的CFL的弦乐中，其边缘标签形成了一个符号。对输入图的尺寸的子立方度时间复杂性。透视图 - 降低输入图可以通过将两个节点与所有边缘连接在一起的节点折叠的两个节点可以折叠。 ），一种替代形式，我们提出了一种识别可折叠节点对的方法，而无需验证基本的可及路径（这等同于解决CFL可得出的问题）。基于g和rsm中状态转换之间的对应关系，我们提出了一个图形折叠原理，它可以通过检查两个相邻的节点是否仅通过检查其输入和是否可以折叠外向的边缘。我们对两个客户的评估（别名分析和价值分析）表明，GF通过降低输入图的大小可显着加速RSM/CFL的性能，以供价值流分析，GF降低了60.96％的节点和42.67％的节点。输入图的边缘，获得4.65倍的加速度，并减少了57.35％的存储器。图形，获得3.21倍的加速度，存储使用减少为65.19％。
Context-free language reachability (CFL-reachability) is a fundamental framework for program analysis. A large variety of static analyses can be formulated as CFL-reachability problems, which determines whether specific source-sink pairs in an edge-labeled graph are connected by a reachable path, i.e., a path whose edge labels form a string accepted by the given CFL. Computing CFL-reachability is expensive. The fastest algorithm exhibits a slightly subcubic time complexity with respect to the input graph size. Improving the scalability of CFL-reachability is of practical interest, but reducing the time complexity is inherently difficult. In this paper, we focus on improving the scalability of CFL-reachability from a more practical perspective---reducing the input graph size. Our idea arises from the existence of trivial edges, i.e., edges that do not affect any reachable path in CFL-reachability. We observe that two nodes joined by trivial edges can be folded---by merging the two nodes with all the edges joining them removed---without affecting the CFL-reachability result. By studying the characteristic of the recursive state machines (RSMs), an alternative form of CFLs, we propose an approach to identify foldable node pairs without the need to verify the underlying reachable paths (which is equivalent to solving the CFL-reachability problem). In particular, given a CFL-reachability problem instance with an input graph G and an RSM, based on the correspondence between paths in G and state transitions in RSM, we propose a graph folding principle, which can determine whether two adjacent nodes are foldable by examining only their incoming and outgoing edges. On top of the graph folding principle, we propose an efficient graph folding algorithm GF. The time complexity of GF is linear with respect to the number of nodes in the input graph. Our evaluations on two clients (alias analysis and value-flow analysis) show that GF significantly accelerates RSM/CFL-reachability by reducing the input graph size. On average, for value-flow analysis, GF reduces 60.96% of nodes and 42.67% of edges of the input graphs, obtaining a speedup of 4.65× and a memory usage reduction of 57.35%. For alias analysis, GF reduces 38.93% of nodes and 35.61% of edges of the input graphs, obtaining a speedup of 3.21× and a memory usage reduction of 65.19%.