Value dependence graphs paper available

From: Michael D. Ernst <>
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"



  Order Dept.
  Jacob Way
  Reading, MA 01867
  (800) 447-2226

Additional information can be obtained from

ACM OO Messenger
ACM SigPlan Notices

  Publications Office
  ACM, 1515 Broadway
  NY, NY 10056
  (212)869-7440, FAX: (212)869-0481

American Programmer (Yourdon's Newsletter)

  American Programmer, Inc.
  Dept. 13
  161 West 86th Street
  New York, NY  10024-3411

  Send for complementary copy.

CASE Trends Magazine

The Coad Letter

  Object International, Inc.
  3202 W. Anderson Lane, Suite 208-724
  Austin, TX  78757-1022
  Tel: 800-926-9306, 512-795-0202
  Fax: 512-795-0332

C++ Report
Journal of Object-Oriented Programming
Object Magazine
The Smalltalk Report (9/year)  (Dept SML)

  Subscriber Services, Dept OOP
  PO 3000
  Denville NJ  07834-9970
  Phone: 212.274.0640
  Fax:   212.274.0646

The Guerilla Programmer

  New, by Ed Yourdon.

  Phone:  800-964-8702 or 617-648-9702
  Fax:    800-888-1816 or 617-648-1950

Object-Oriented Systems (New)


  Journals Promotion Dept., Chapman & Hall, 29 West 35th
  Street, New York, NY 20001-2299, USA.
  Tel: (212) 244 3336
  Fax: (212) 244 3426

  Journals Promotions Dept., Chapman & Hall, 2-6 Boundary Row, London
  SE1 8HN, UK.
  Tel: +44 (0)71 865 0066
  Fax: +44 (0)71 522 9623
Go Back Up

Go To Previous