Indexing the Extended Dyck-CFL Reachability for Context-Sensitive Program Analysis
summary
This paper presents a cheap reduction that transforms extended Dyck-CFL reachability to conventional graph reachability, builds a two-copy indexed graph with summary edges, and then applies off-the-shelf reachability indexes such as GRAIL and PASTRY (and a path-tree for path reconstruction). Preprocessing time and memory stay near-linear; queries run in almost constant time. Implementations for pointer alias and information-flow analyses show 100×–100,000× speedups with only moderate space overhead.
AI-written summary · about
chapters (19)
- 0:00Introduction
- 1:05Dyck-CFL reachability in analysis
- 3:11Context sensitivity limits
- 6:25Extending to partial matches
- 8:32Approaches and trade-offs
- 10:21Two-step extended reachability
- 11:23Step 1: Summary edges
- 13:11Step 2: Copied graphs
- 15:25Reduction to reachability
- 16:29Step 2: Query acceleration
- 17:13Grail for efficient reachability
- 21:52Pre-processing efficiency
- 22:14Information flow analysis
- 22:36Alias analysis
- 23:58Scalability on large graphs
- 24:20Performance vs transitive closure
- 26:51Analysis and databases
- 27:12Conclusion
- 27:56Q&A
related talks
14mFast Client-Driven CFL-Reachability via Regularization-Based Graph Simplification
13mAccelerating Program Analyses in Datalog by Merging Library Facts
41mOptimizing Relational Programs I
53mData Deduplication For Redundant Graph Structures Files
15mUniversal Scalability in Declarative Program Analysis (with Choice-Based Combination(…)
20mGraphWalker: An I/O-Efficient and Resource-Friendly Graph Analytic System...
06mWhen All Context Matters: Extended Cache Augmented Generation
01h 00mGraph Mastery to AI