From: Michael D. Ernst <mernst@research.microsoft.com> Subject: Value dependence graphs paper available Date: Tue, 9 Nov 1993 00:59:36 GMT
The paper "Value Dependence Graphs: Representation Without Taxation", which describes a new intermediate representation which is particularly amenable to optimization, is available. (This version corrects typos and clarifies a few minor points that may not have been completely clear in the version which will appear in the POPL 94 proceedings.) You can get a copy in three ways:
1. Via anonymous ftp, obtain file research.microsoft.com:/pub/papers/vdg.ps
(or file vdg.ps635 if you have a HP LaserJet 4 printer).
2. Reply to mernst@research.microsoft.com requesting PostScript by email,
and I will send you the PostScript file of your choice. (The files are
483K and 1018K bytes, respectively.)
3. Reply to mernst@research.microsoft.com sending me your physical mail
address, and I will mail you a hardcopy.
The abstract is:
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 [KRS92, 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.
The paper's full citation is:
@InProceedings{WeiseCES94,
author = "Daniel Weise and Roger F. Crew and Michael Ernst and
Bjarne Steensgaard",
title = "Value Dependence Graphs: Representation Without Taxation",
booktitle = POPL94,
pages = "297-310",
year = 1994,
month = jan,
address = "Portland, OR"
}
This document was translated by ms2html v1.8 on 04.06.96.