Optimal Dyck Reachability for Data-Dependence and Alias Analysis

Watch a 23-minute conference presentation from POPL 2018 exploring breakthrough algorithms for Dyck reachability problems in static analysis. Learn about improved upper and lower bounds for field-sensitive points-to analysis on bidirected graphs, featuring an optimal O(m + n · α(n)) worst-case algorithm and O(m) average-case performance. Discover new approaches for context-sensitive data-dependence analysis of library code with callbacks, enabling nearly linear preprocessing time and linear complexity for client analysis. Examine theoretical results establishing conditional optimality of existing combinatorial algorithms for Dyck reachability on general graphs, including those with constant treewidth. See experimental results demonstrating significant performance improvements over existing methods for both alias analysis and data-dependence analysis on real-world benchmarks.