Value dependence graphs

The value dependence graph (VDG) is a sparse dataflow-like representation that simplifies program analysis and transformation. It is a functional representation that represents control flow as data flow and makes explicit all machine quantities, such as stores and I/O channels. We are developing a compiler that builds a VDG representing a program, analyzes and transforms the VDG, then produces a control flow graph (CFG) ASU86 from the optimized VDG. This framework simplifies transformations and improves upon several published results. For example, it enables more powerful code motion than CLZ86, FOW87, eliminates as many redundancies as AWZ88, RWZ88 (except for redundant loops), and provides important information to the code scheduler BR91. We exhibit a fast, one-pass method for elimination of partial redundancies that never performs redundant code motion KFS92, DS93 and is simpler than the classical MR79, Dha91 or SSA RWZ88 methods. These results accrue from eliminating the CFG from the analysis/transformation phases and using demand dependences in preference to control dependences.