Perfect Reconstructability of Control Flow from Demand Dependence Graphs
Venue
Transactions on Architecture and Code Optimization (2014) (to appear)
Publication Year
2014
Authors
Helge Bahmann, Nico Reissmann, Magnus Jahre, Jan Christian Meyer
BibTeX
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.
