Value dependence graphs: representation without taxation

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.

REFERENCES

• AN90: K. Arvind , Rishiyur S. Nikhil, Executing a Program on the MIT Tagged-Token Dataflow Architecture, IEEE Transactions on Computers, v.39 n.3, p.300-318, March 1990 [doi>10.1109/12.48862]
• ASU86: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• AWZ88: B. Alpern , M. N. Wegman , F. K. Zadeck, Detecting equality of variables in programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-11, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73561]
• BCT92: Preston Briggs , Keith D. Cooper , Linda Torczon, Rematerialization, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.311-321, June 15-19, 1992, San Francisco, California, United States
• BH92: Thomas Ball and Susan Horwitz. Slicing programs with arbitrary control flow. Technical Report 1128, University of Wisconsin - Madison, December 21, 1992.
• BJP91: Micah Beck , Richard Johnson , Keshav Pingali, From control flow to dataflow, Journal of Parallel and Distributed Computing, v.12 n.2, p.118-129, June 1991 [doi>10.1016/0743-7315(91)90016-3]
• BMO90: Karl J. Ottenstein , Robert A. Ballance , Arthur B. MacCabe, The program dependence web: a representation supporting control-, data-, and demand-driven interpretation of imperative languages, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.257-271, June 1990, White Plains, New York, United States
• BR91: David Bernstein , Michael Rodeh, Global instruction scheduling for superscalar machines, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.241-255, June 24-28, 1991, Toronto, Ontario, Canada
• CCF91: Jong-Deok Choi , Ron Cytron , Jeanne Ferrante, Automatic construction of sparse data flow evaluation graphs, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.55-66, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99594]
• CF89: E. Cartwright , M. Felleisen, The semantics of program dependence, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.13-27, June 19-23, 1989, Portland, Oregon, United States
• CFR+89: R. Cytron , J. Ferrante , B. K. Rosen , M. N. Wegman , F. K. Zadeck, An efficient method of computing static single assignment form, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.25-35, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75280]
• 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.
• Cli93a: Clifford Noel Click, Jr., Combining analyses, combining optimizations, Rice University, Houston, TX, 1996
• Cli93b: Cliff Click. From quads to graphs: An intermediate representation's journey. Submitted for publication, October 18, 1993.
• CLZ86: Ron Cytron , Andy Lowry , F. Kenneth Zadeck, Code motion of control structures in high-level languages, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.70-85, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512651]
• Coc70: John Cocke, Global common subexpression elimination, ACM SIGPLAN Notices, v.5 n.7, p.20-24, July 1970
• CS70: John Cocke and Jacob T. Schwartz. Programming languages and their compilers. Technical report, Courant Institute, NYU, April 1970. Preliminary notes.
• Dha91: D. M. Dhamdhere, Practical adaption of the global optimization algorithm of Morel and Renvoise, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.291-294, April 1991 [doi>10.1145/103135.214520]
• DRZ92: Dhananjay M. Dhamdhere , Barry K. Rosen , F. Kenneth Zadeck, How to analyze large programs efficiently and informatively, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.212-223, June 15-19, 1992, San Francisco, California, United States
• DS93: Karl-Heinz Drechsler , Manfred P. Stadel, A variation of Knoop, Rüthing, and Steffen's Lazy Code Motion, ACM SIGPLAN Notices, v.28 n.5, p.29-38, May 1993 [doi>10.1145/152819.152823]
• Ern93: Michael Ernst. Program slicing using the value dependence graph. In preparation, 1993.
• 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.
• FKCX94: Lawrence Feigen , David Klappholz , Robert Casazza , Xing Xue, The revival transformation, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.421-434, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.178043]
• FM85: Jeanne Ferrante , Mary Mace, On linearizing parallel code, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.179-190, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318636]
• FMS88: J. Ferrante , M. Mace , B. Simons, Generating sequential code from parallel code, Proceedings of the 2nd international conference on Supercomputing, p.582-592, June 1988, St. Malo, France [doi>10.1145/55364.55421]
• FOW87: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• Har85: D Harel, A linear algorithm for finding dominators in flow graphs and related problems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.185-194, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22166]
• Hav93: Paul Havlak. Construction of thinned gated singleassignment form. Draft -- Private distribution, February 20, 1993.
• HRB90: Susan Horwitz , Thomas Reps , David Binkley, Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.26-60, Jan. 1990 [doi>10.1145/77606.77608]
• JP93: Richard Johnson , Keshav Pingali, Dependence-based program analysis, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.78-89, June 21-25, 1993, Albuquerque, New Mexico, United States
• JPP93: Richard Johnson , David Pearson , Keshav Pingali, Finding Regions Fast: Single Entry Single Exit and Control Regions in Linear Time, Cornell University, Ithaca, NY, 1993
• KRS92: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Lazy code motion, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.224-234, June 15-19, 1992, San Francisco, California, United States
• MR79: E. Morel , C. Renvoise, Global optimization by suppression of partial redundancies, Communications of the ACM, v.22 n.2, p.96-103, Feb. 1979 [doi>10.1145/359060.359069]
• Ott78: Karl Joseph Ottenstein. Data-flow graphs as an intermediate program form. PhD thesis, Purdue University, August 1978.
• PBJ+90: Keshav Pingali , Micah Beck , Richard C. Johnson , Mayan Moudgill , Paul Stodghill, Dependence Flow Graphs: An Algebraic Approach to Program Dependencies, Cornell University, Ithaca, NY, 1990
• RWZ88: B. K. Rosen , M. N. Wegman , F. K. Zadeck, Global value numbers and redundant computations, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.12-27, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73562]
• SAF90: B. Simons , D. Alpern , J. Ferrante, A foundation for sequentializing parallel code, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.350-359, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97702]
• 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.
• 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.
• Ste93a: Bjarne Steensgaard. Sequentializing program dependence graphs for irreducible programs. Technical Report MSR- TR-93-14, Microsoft Research, Redmond, WA, August 1993.
• Ste93b: Bjarne Steensgaard. A store algebra for graphical program representations. In preparation, November 1993.
• Ven91: G. A. Venkatesh, The semantic approach to program slicing, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.107-119, June 24-28, 1991, Toronto, Ontario, Canada
• WCRS91: Daniel Weise , Roland Conybeare , Erik Ruf , Scott Seligman, Automatic online partial evaluation, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.165-191, June 1991, Cambridge, Massachusetts, United States
• Wei84: Mark Weiser. Program slicing. IEEE Transactions on Software Engineering, SE-10(4):352-357, July 1984.
• 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.
• WZ85: Mark N. Wegman , Frank Kenneth Zadeck, Constant propagation with conditional branches, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.291-299, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318659]
• 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.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

General Terms:
Theory