lotus

previous page: 9.6) Object-Oriented Technology ftp: 56 Teaching Intro to OO Slides, T. Budd
  
page up: Object-Oriented Technology FAQ
  
next page: 9.6) Object-Oriented Technology ftp: 58 Various on OO

9.6) Object-Oriented Technology ftp: 57 Value Dependence Graphs




Description

This article is from the Object-Oriented Technology FAQ, by Bob Hathaway rjh@geodesic.com with numerous contributions by others.

9.6) Object-Oriented Technology ftp: 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 ftp://research.microsoft.com/pub/papers/
(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"
}

 

Continue to:













TOP
previous page: 9.6) Object-Oriented Technology ftp: 56 Teaching Intro to OO Slides, T. Budd
  
page up: Object-Oriented Technology FAQ
  
next page: 9.6) Object-Oriented Technology ftp: 58 Various on OO