The Bounded Pathwidth of Control-Flow Graphs

Explore a groundbreaking 17-minute conference talk from OOPSLA2 2023 that introduces the concept of bounded pathwidth in control-flow graphs. Delve into how this novel approach can revolutionize static analysis and compiler optimization. Learn why pathwidth is a stronger parameter than treewidth for analyzing program structures, and discover its potential to simplify algorithm design and significantly improve performance in tasks like register allocation. Examine the presenters' proof that control-flow graphs of structured programs have bounded pathwidth, and understand the implications for developing more efficient verification algorithms. Gain insights from extensive experimental results demonstrating practical runtime improvements of 2-3 orders of magnitude in real-world embedded benchmarks. Uncover the theoretical and practical benefits of adopting pathwidth as a key parameter in program analysis and optimization techniques.