Perfect Reconstructability of Control Flow from Demand Dependence Graphs

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.

• Algorithms and Theory

• Software Systems