Efficient Interprocedural Data-Flow Analysis using Treedepth and Treewidth

on YouTube ↗30m

" summary

Claims a concrete IFDS solver that exploits treedepth of the call graph and treewidth of control-flow graphs, constructs an exploded code graph, and achieves linear preprocessing in program size plus extra dependence on treedepth. Preprocessing runs minutes on benchmarks (average treedepth 43.8), queries run seconds overall and are constant-time per query w.r.t. input size; experiments show speedups of several orders of magnitude over classical IFDS/on-demand IFDS.

AI-written summary · about

" chapters (14)

1. 0:00Introduction
2. 0:24Data flow problems and IFDS
3. 6:05Inter-procedural data flow analysis challenges
4. 10:45IFDS limitations
5. 11:49Treewidth and treedepth for sparsity
6. 13:12Treedepth for call graphs
7. 16:26Observations on inter-procedural paths
8. 18:56Exploded call graph construction
9. 21:23Partial order trees preprocessing
10. 23:33Experimental results
11. 24:56Conclusion and future work
12. 25:18Q&A
13. 26:43Q&A on k-CFA and recursion
14. 28:27Q&A on scalability