Object-Orientation FAQ

57 Value Dependence Graphs

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:
  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 01.06.95.