Google Research

Perfect Reconstructability of Control Flow from Demand Dependence Graphs

  • Helge Bahmann
  • Nico Reissmann
  • Magnus Jahre
  • Jan Christian Meyer
Transactions on Architecture and Code Optimization (2014) (to appear)

Abstract

Functional demand-based dependence graphs, such as the Regionalized Value State Dependence Graph, are intermediate representations that only model the flow of data and state with implicit and severely restricted control flow. While suitable for formulation of program transformations, they require algorithms for conversion from and to representations with explicit control flow such as CFG. Existing solutions exhibit structural constraints limiting quality of generated control flow, but we show that this is not intrinsic to RVSDGs. We provide algorithms capable of perfect round-trip conversions, prove their correctness and empirically evaluate their run-time performance and representation overhead.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work