Download: PDF.
“Value dependence graphs: Representation without taxation”
by Daniel Weise, Roger F. Crew,
Michael D. Ernst,
and Bjarne Steensgaard.
In POPL '94: Proceedings of the 21st Annual ACM SIGPLAN-SIGACT
Symposium on Principles of Programming Languages, (Portland, OR),
Jan. 1994, pp. 297-310.
A previous version appeared as Microsoft Research
technical report MSR-TR-94-03, (Redmond, WA), April 13, 1994.
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.
Download: PDF.
BibTeX entry:
@inproceedings{WeiseCES94:POPL,
author = {Daniel Weise and Roger F. Crew and Michael D. Ernst and
Bjarne Steensgaard},
title = {Value dependence graphs: Representation without taxation},
booktitle = {POPL '94: Proceedings of the 21st Annual ACM
SIGPLAN-SIGACT Symposium on Principles of Programming Languages},
pages = {297--310},
address = {Portland, OR},
month = jan,
year = {1994}
}
(This webpage was created with bibtex2web.)
Back to Michael Ernst's publications.