Daniel Weise
Michael Ernst
ABSTRACT
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 [KFS92, 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.
- AN90.Arvind and R. S. Nikhil. Executing a program on the MIT tagged-token dataflow architecture. IEEE Transactions on Computers, 39(3):300-318, March 1990.]] Google Scholar
Digital Library
- ASU86.Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools. Computer Science Series. Addison-Wesley, Reading, Massachusetts, 1986.]] Google ScholarDigital Library
- AWZ88.Bowen Alpern, Mark N. Wegman, and F. Kenneth Zadeck. Detecting equality of variables in programs, in Proceedings of the Fifteenth Annual A CM Symposium on Principles of Programming Languages, pages 1-11. ACM Press, January 1988.]] Google ScholarDigital Library
- BCT92.Preston Briggs, Keith D. Cooper, and Linda Torczon. Rematerialization. In Proceedings of the SIGPLAN '9~ Conference on Programming Language Design and Implementation, pages 311-321. ACM Press, June 1992.]] Google ScholarDigital Library
- BH92.Thomas Ball and Susan Horwitz. Slicing programs with arbitrary control flow. Technical Report 1128, University of Wisconsin - Madison, December 21, 1992.]]Google Scholar
- BJP91.Micah Beck, Richard Johnson, and Keshav Pingali. From control flow to dataflow. Journal of Parallel and Distributed Computing, 12:118-129, 1991.]] Google ScholarDigital Library
- BMO90.Robert A. Ballance, Arthur B. Maccabe, and Karl J. Ottenstein. The program dependence web: a representation supporting control-, data-, and demand-driven interpretation of imperative languages. In Proceedings of the SIGPLAN '90 Conference on Programming Language Design and Implementation, pages 257-271. ACM Press, June 1990.]] Google ScholarDigital Library
- BR91.David Bernstein and Michael Rodeh. Global instruction scheduling for superscalar machines. In Proceedings of the SIG- PLAN '91 Conference on Programming Language Design and Implementation, pages 241-255, June 1991.]] Google ScholarDigital Library
- CCF91.Jong-Deok Choi, Ron Cytron, and Jeanne Ferrante. Automatic construction of sparse data flow evaluation graphs. In Procedings of the Eighteenth Annual A CM Symposium on Principles of Programming Languages, pages 55-66. ACM Press, January 1991.]] Google ScholarDigital Library
- CF89.Robert Cartwright and Matthias Felleisen. The semantics of program dependence. In Proceedings of the SIGPLAN '89 Conference on Programming Language Design and Implementation, pages 13-27, Portland, OR, June 1989.]] Google ScholarDigital Library
- CFR+89.Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. An efficient method of computing static single assignment form. In Proceedings of the Sixteenth Annual A CM Symposium on Principles of Programming Languages, pages 25-35. ACM Press, January 1989.]] Google ScholarDigital Library
- CKB93.Philip L. Campbell, Ksheerabdhi Krishna, and Robert A. Ballance. Refining and defining the program dependence web. Technical Report CS93-6, University of New Mexico, Albuquerque, March 1993.]]Google Scholar
- Cli93a.Cliff Click. Combining analyses, combining optimizations. PhD thesis proposal, April 1993.]] Google ScholarDigital Library
- Cli93b.Cliff Click. From quads to graphs: An intermediate representation's journey. Submitted for publication, October 18, 1993.]]Google Scholar
- CLZ86.Ron Cytron, Andy Lowry, and Kenneth Zadeck. Code motion of control structures in high-level languages. In Proceedings of the Thirteenth Annual A CM Symposium on Principles of Programming Languages, pages 70-85, January 1986.]] Google ScholarDigital Library
- Coc70.John Cocke. Global common subexpression elimination. SIGPLAN Notices, 5(7):20-24, July 1970.]] Google ScholarDigital Library
- CS70.John Cocke and Jacob T. Schwartz. Programming languages and their compilers. Technical report, Courant Institute, NYU, April 1970. Preliminary notes.]] Google ScholarDigital Library
- Dha91.D. M. Dhamdhere. Practical adaptation of the global optimization algorithm of Morel and Renvoise. A CM Transactions on Programming Languages and Systems, 13(2):291-294, April 1991.]] Google ScholarDigital Library
- DRZ92.Dhananjay M. Dhamdere, Barry K. Rosen, and F. Kenneth Zadeck. How to analyze large programs efficiently and informatively. In Proceedings of the SIGPLAN '92 Conference on Programming Language Design and Implementation, pages 212-223, San Francisco, California, June 17-19, 1992. ACM Press.]] Google ScholarDigital Library
- DS93.Karl-Heinz Drechsler and Manfred P. Stadel. A variation of Knoop, Riithing, and Steffen's lazy code motion. A CM SIGPLAN Notices, 28(5):29-38, May 1993.]] Google ScholarDigital Library
- Ern93.Michael Ernst. Program slicing using the value dependence graph. In preparation, 1993.]]Google Scholar
- Fie92.John Field. A simple rewriting semantics for realistic imperative programs and its application to program analysis (preliminary report). In Proc. A CM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, pages 98-107, San Francisco, June 1992. Published as Yale University Technical Report YALEU/DCS/RR-909.]]Google Scholar
- FKCX94.Lawrence Feigen, David Kiappholz, Robert Casazza, and Xing Xue. The revival transformation. In Proceedings of the Twenty-first Annual A CM SIGPLAN-SIGA CT Symposium on Principles of Programming Languages, Portland, OR, January 1994.]] Google ScholarDigital Library
- FM85.Jeanne Ferrante and Mary Mace. On linearizing parallel code. in Proceedings of the Twelfth Annual ACM Symposium on Principles of Programming Languages, pages 179-190, January 1985.]] Google ScholarDigital Library
- FMS88.Jeanne Ferrante, Mary Mace, and Barbara Simons. Generating sequential code from parallel code. In Proceedings of the 1988 International Conference on Supercomputing, pages 582-592, June 1988.]] Google ScholarDigital Library
- FOW87.Jeanne Ferrante, Karl J. Ottenstein, and Joe D. Warren. The program dependence graph and its use in optimization. A CM Transactions on Programming Languages and Systems, 9(3):319-349, July 1987.]] Google ScholarDigital Library
- Har85.Dov Harel. A linear time algorithm for finding dominators in flow graphs and related problems. In Proceedings of the Seventeenth A CM Symposium on Theory of Computing, pages 185-194, May 1985.]] Google ScholarDigital Library
- Hav93.Paul Havlak. Construction of thinned gated singleassignment form. Draft -- Private distribution, February 20, 1993.]]Google Scholar
- HRB90.Susan Horwitz, Thomas Reps, and David Binkley. Interprocedural slicing using dependence graphs. ACM Transactions on Programming Languages and Systems, 12(1):26-60, January 1990.]] Google ScholarDigital Library
- JP93.Richard Johnson and Keshav Pingali. Dependence-based program analysis. In Proceedings of the SIGPLAN '93 Conference on Programming Language Design and Implementation, pages 78-89, Albuquerque, NM, June 23-25, 1993. ACM Press.]] Google ScholarDigital Library
- JPP93.Richard Johnson, David Pearson, and Keshav Pingali. Finding regions fast: Single entry single exit and control regions in linear time. Technical Report CTC93TR141, Cornell University, July 1993.]] Google ScholarDigital Library
- KRS92.Jens Knoop, Oliver Riithing, and Bernhard Steffen. Lazy code motion. In Proceedings of the SIGPLAN '92 Conference on Programming Language Design and Implementation, pages 224-234, San Francisco, California, June 17-19, 1992. ACM Press.]] Google ScholarDigital Library
- MR79.Etienne Morel and Claude Renvoise. Global optimization by suppression of partial redundancies. Communications of the A CM, 22(2):96-103, February 1979.]] Google ScholarDigital Library
- Ott78.Karl Joseph Ottenstein. Data-flow graphs as an intermediate program form. PhD thesis, Purdue University, August 1978.]]Google Scholar
- PBJ+90.Keshav Pingali, Micah Beck, Richard Johnson, Mayan Moudgill, and Paul Stodghill. Dependence flow graphs: An algebraic approach to program dependencies. Technical Report 90-1152, Department of Computer Science, Cornell University, Ithaca, NY 14853, September 1990.]] Google ScholarDigital Library
- RWZ88.Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Global value numbers and redundant computations. In Proceedings of the Fifteenth Annual A CM Symposium on Principles of Programming Languages, pages 12-27. ACM Press, January 1988.]] Google ScholarDigital Library
- SAF90.Barbara Simons, David Alpern, and Jeanne Ferrante. A foundation for sequentializing parallel code -- extended abstract. In Proceedings of the 2nd A CM Symposium on Parallel Algorithms and Architectures, pages 350-359, 1990.]] Google ScholarDigital Library
- SF93.Barbara Simons and Jeanne Ferrante. An efficient algorithm for constructing a control flow graph for parallel code. Technical Report TR 03.465, IBM, Santa Teresa Laboratory, San Jose, California, February 1993.]]Google Scholar
- SHKN76.T. A. Standish, D. C. Harriman, D. F. Kilber, and J. M. Neighbors. The Irvine program transformation catalogue. Technical Report 161, University of California at Irvine, Department of Information and Computer Science, January 1976.]]Google Scholar
- Ste93a.Bjarne Steensgaard. Sequentializing program dependence graphs for irreducible programs. Technical Report MSR- TR-93-14, Microsoft Research, Redmond, WA, August 1993.]]Google Scholar
- Ste93b.Bjarne Steensgaard. A store algebra for graphical program representations. In preparation, November 1993.]]Google Scholar
- Ven91.G.A. Venkatesh. The semantic approach to program slicing. In Proceedings of the SIGPLAN '91 Conference on Programming Language Design and Implementation, pages 107- 119, Toronto, Ontario, Canada, June 26-28, 1991.]] Google ScholarDigital Library
- WCRS91.Daniel Weise, Roland Conybeare, Erik Ruf, and Scott Seligman. Automatic online partial evaluation. In J. Hughes, editor, Functional Programming Languages and Computer Architecture, number 523 in Lecture Notes in Computer Science, pages 165-191, Cambridge, MA, August 26-30, 1991. ACM, Springer-Verlag.]] Google ScholarDigital Library
- Wei84.Mark Weiser. Program slicing. IEEE Transactions on Software Engineering, SE-10(4):352-357, July 1984.]]Google ScholarDigital Library
- Wei90.Daniel Weise. Graphs as an intermediate representation for partial evaluation. Technical Report CSL-TR-90-421, Stanford Computer Systems Laboratory, Stanford, CA, March 1990.]]Google Scholar
- WZ85.Mark N. Wegman and Frank Kenneth Zadeck. Constant propagation with condition branches. In Proceedings of the Twelfth Annual A CM Symposium on Principles of Programming Languages, pages 291-299, January 1985.]] Google ScholarDigital Library
- WZ89.Mark N. Wegman and F. Kenneth Zadeck. Constant propagation with conditional branches. Technical Report CS- 89-36, IBM T.J. Watson Research Center, Yorktown Heights, NY, May 1989.]]Google ScholarDigital Library
Recommendations
The program dependence graph and its use in optimization
In this paper we present an intermediate program representation, called the program dependence graph (PDG), that makes explicit both the data and control dependences for each operation in a program. Data dependences have been used to represent only the ...
Perfect Reconstructability of Control Flow from Demand Dependence Graphs
Demand-based dependence graphs (DDGs), such as the (Regionalized) Value State Dependence Graph ((R)VSDG), are intermediate representations (IRs) well suited for a wide range of program transformations. They explicitly model the flow of data and state, ...
Comments