Value dependence graphs paper available

Michael D. Ernst <>
Tue, 9 Nov 1993 00:59:36 GMT

          From comp.compilers

Related articles
Value dependence graphs paper available (Michael D. Ernst) (1993-11-09)
| List of all articles for this month |

Newsgroups: comp.compilers
From: Michael D. Ernst <>
Keywords: optimize, analysis, report, FTP, bibliography
Organization: Compilers Central
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
        (or file vdg.ps635 if you have a HP LaserJet 4 printer).
2. Reply to 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 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,
    OPTpages = "",
    year = 1994,
    month = jan,
    address = "Portland, OR"

-Michael Ernst

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.