Two Birds with One Stone: Multi-Derivation for Fast Context-Free Language Reachability Analysis

Context free language CFL reachability is a fundamental framework for formulating program analyses CFL reachability analysis works on top of an edge labeled graph by deriving reachability relations and adding them as labeled edges to the graph Existing CFL reachability algorithms typically adopt a single reachability relation derivation SRD strategy i e one reachability relation is derived at a time Unfortunately this strategy can lead to redundancy hindering the efficiency of the analysis To address this problem this paper proposes Pearl a multi derivation approach that reduces derivation redundancy for transitive relations that frequently arise when solving reachability relations significantly improving the efficiency of CFL reachability analysis Our key insight is that multiple edges involving transitivity can be simultaneously derived via batch propagation of reachability relations on the transitivity aware subgraphs that are induced from the original edge labeled graph We evaluate the performance of Pearl on two clients i e context sensitive value flow analysis and field sensitive alias analysis for C C By eliminating a large amount of redundancy Pearl achieves average speedups of 82 73x for value flow analysis and 155 26x for alias analysis over the standard CFL reachability algorithm The comparison with Pocr a state of the art CFL reachability solver shows that Pearl runs 10 1x up to 29 2x and 2 37x up to 4 22x faster on average respectively for value flow analysis and alias analysis with less consumed memory