Global value numbers and redundant computations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Global value numbers and redundant computations

Full text

Pdf (1.96 MB)

Source

Annual Symposium on Principles of Programming Languages archive
Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages table of contents

San Diego, California, United States

Pages: 12 - 27

Year of Publication: 1988

ISBN:0-89791-252-7

Authors

B. K. Rosen	IBM Thomas J. Watson Research Center, Yorktown Heights, NY
M. N. Wegman	IBM Thomas J. Watson Research Center, Yorktown Heights, NY
F. K. Zadeck	Department of Computer Science, Brown University, Providence, RI

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 27, Downloads (12 Months): 126, Citation Count: 87

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/73560.73562 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Frances E. Allen, Control flow analysis, ACM SIGPLAN Notices, v.5 n.7, p.1-19, July 1970
	2	F. E. Allen. Program optimization. Ann. Rev. Automatic Programming, 5:239-307, 1969.
	3	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]
	4	Marc Auslander , Martin Hopkins, An overview of the PL.8 compiler, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.22-31, June 23-25, 1982, Boston, Massachusetts, United States
	5	G. J. Chaitin, Register allocation & spilling via graph coloring, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.98-105, June 23-25, 1982, Boston, Massachusetts, United States
	6	Frederick Chow , John Hennessy, Register allocation by priority-based coloring, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.222-232, June 17-22, 1984, Montreal, Canada
	7	John Cocke, Programming languages and their compilers: Preliminary notes, Courant Institute of Mathematical Sciences, New York University, 1969
	8	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]
	9	M. S. Hecht , J. D. Ullman, Characterizations of Reducible Flow Graphs, Journal of the ACM (JACM), v.21 n.3, p.367-375, July 1974 [doi>10.1145/321832.321835]
	10	M. S. Hecht and J. D. Ullman. A simple algorithm for global data flow analysis problems. SlAM J. Computing, 4(4):519-532, December 1975.
	11	David B. Loveman , Ross A. Faneuf, Program optimization - theory and practice, Proceedings of the conference on Programming languages and compilers for parallel and vector machines, p.97-102, March 18-19, 1975, New York, New York
	12	Edward S. Lowry , C. W. Medlock, Object code optimization, Communications of the ACM, v.12 n.1, p.13-22, Jan. 1969 [doi>10.1145/362835.362838]
	13	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]
	14	John H. Reif , Harry R. Lewis, Symbolic evaluation and the global value graph, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.104-118, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512961]
	15	J. H. Reif and R. E. Tarjan. Symbolic program analysis in almost linear time. SIAM J. Computing, 11(1):81-93, February 1982.
	16	Barry K. Rosen, Data Flow Analysis for Procedural Languages, Journal of the ACM (JACM), v.26 n.2, p.322-344, April 1979 [doi>10.1145/322123.322135]
	17	R. M. Shapiro and H. Saint. The Representation of Algorithms. Technical Report CA-7002-1432, Massachusetts Computer Associates, February 1970.
	18	R. E. Tarjan. Depth first search and linear graph algorithms. SIAM J. Computing, 1(2):146-160, 1972.
	19	R. E. Tarjan. Testing flow graph reducibility. J. Computer and System Sciences, 9:355-365, December 1974.

CITED BY 87

	Jaejin Lee , Samuel P. Midkiff , David A. Padua, A Constant Propagation Algorithm for Explicitly Parallel Programs, International Journal of Parallel Programming, v.26 n.5, p.563-589, October 1998
	Cliff Click, Global code motion/global value numbering, ACM SIGPLAN Notices, v.30 n.6, p.246-257, June 1995
	Jens Knoop , Oliver Rüthing , Bernhard Steffen, Lazy code motion, ACM SIGPLAN Notices, v.27 n.7, p.224-234, July 1992
	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
	Carl McConnell , Ralph E. Johnson, Using static single assignment form in a code optimizer, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.2, p.152-160, June 1992
	Paul Havlak , Ken Kennedy, Experience with interprocedural analysis of array side effects, Proceedings of the 1990 conference on Supercomputing, p.952-961, October 1990, New York, New York, United States
	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
	Ron Cytron , Jeanne Ferrante , V. Sarkar, Compact representations for control dependence, ACM SIGPLAN Notices, v.25 n.6, p.337-351, Jun. 1990
	Wuu Yang , Susan Horwitz , Thomas Reps, A program integration algorithm that accommodates semantics-preserving transformations, ACM SIGSOFT Software Engineering Notes, v.15 n.6, p.133-143, Dec. 1990
	Preston Briggs , Keith D. Cooper, Effective partial redundancy elimination, ACM SIGPLAN Notices, v.29 n.6, p.159-170, June 1994
	Michael Wolfe, Beyond induction variables, ACM SIGPLAN Notices, v.27 n.7, p.162-174, July 1992
	Robert Kennedy , Sun Chan , Shin-Ming Liu , Raymond Lo , Peng Tu , Fred Chow, Partial redundancy elimination in SSA form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.3, p.627-676, May 1999
	Rastislav Bodík , Rajiv Gupta , Mary Lou Soffa, Load-reuse analysis: design and evaluation, ACM SIGPLAN Notices, v.34 n.5, p.64-76, May 1999
	Christopher Lapkowski , Laurie J. Hendren, Extended SSA numbering: introducing SSA properties to languages with multi-level pointers, Proceedings of the 1996 conference of the Centre for Advanced Studies on Collaborative research, p.23, November 12-14, 1996, Toronto, Ontario, Canada
	Mark N. Wegman , F. Kenneth Zadeck, Constant propagation with conditional branches, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.181-210, April 1991
	Dhananjay M. Dhamdhere , Barry K. Rosen , F. Kenneth Zadeck, How to analyze large programs efficiently and informatively, ACM SIGPLAN Notices, v.27 n.7, p.212-223, July 1992
	Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991
	Dhruva R. Chakrabarti , Prithviraj Banerjee, Global optimization techniques for automatic parallelization of hybrid applications, Proceedings of the 15th international conference on Supercomputing, p.166-180, June 2001, Sorrento, Italy
	Fred Chow , Sun Chan , Robert Kennedy , Shin-Ming Liu , Raymond Lo , Peng Tu, A new algorithm for partial redundancy elimination based on SSA form, ACM SIGPLAN Notices, v.32 n.5, p.273-286, May 1997
	Marc M. Brandis , Hanspeter Mössenböck, Single-pass generation of static single-assignment form for structured languages, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.6, p.1684-1698, Nov. 1994
	Jens Knoop , Oliver Rüthing , Bernhard Steffen, Optimal code motion: theory and practice, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.4, p.1117-1155, July 1994
	Evelyn Duesterwald , Rajiv Gupta , Mary Lou Soffa, Demand-driven computation of interprocedural data flow, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.37-48, January 23-25, 1995, San Francisco, California, United States
	Susan Horwitz , Thomas Reps, The use of program dependence graphs in software engineering, Proceedings of the 14th international conference on Software engineering, p.392-411, May 11-15, 1992, Melbourne, Australia
	Arnaud Gotlieb , Bernard Botella , Michel Rueher, Automatic test data generation using constraint solving techniques, ACM SIGSOFT Software Engineering Notes, v.23 n.2, p.53-62, March 1998
	Arthur Stoutchinin , Francois de Ferriere, Efficient static single assignment form for predication, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
	Peng Tu , David Padua, Gated SSA-based demand-driven symbolic analysis for parallelizing compilers, Proceedings of the 9th international conference on Supercomputing, p.414-423, July 03-07, 1995, Barcelona, Spain
	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
	Evelyn Duesterwald , Rajiv Gupta , Mary Lou Soffa, A practical framework for demand-driven interprocedural data flow analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.6, p.992-1030, Nov. 1997
	Karthik Gargi, A sparse algorithm for predicated global value numbering, ACM SIGPLAN Notices, v.37 n.5, May 2002
	Rastisalv Bodík , Sadun Anik, Path-sensitive value-flow analysis, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.237-251, January 19-21, 1998, San Diego, California, United States
	Adam Webber, Optimization of functional programs by grammar thinning, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.2, p.293-330, March 1995
	A. V. S. Sastry , Roy D. C. Ju, A new algorithm for scalar register promotion based on SSA form, ACM SIGPLAN Notices, v.33 n.5, p.15-25, May 1998
	Peng Tu , David Padua, Efficient building and placing of gating functions, ACM SIGPLAN Notices, v.30 n.6, p.47-55, June 1995
	Vugranam C. Sreedhar , Guang R. Gao, A linear time algorithm for placing &phgr;-nodes, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.62-73, January 23-25, 1995, San Francisco, California, United States
	Kathleen Knobe , Vivek Sarkar, Array SSA form and its use in parallelization, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.107-120, January 19-21, 1998, San Diego, California, United States
	Harini Srinivasan , James Hook , Michael Wolfe, Static single assignment for explicitly parallel programs, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.260-272, March 1993, Charleston, South Carolina, United States
	Elana D. Granston , Alexander V. Veidenbaum, Detecting redundant accesses to array data, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.854-865, November 18-22, 1991, Albuquerque, New Mexico, United States
	Allen Leung , Lal George, Static single assignment form for machine code, ACM SIGPLAN Notices, v.34 n.5, p.204-214, May 1999
	P. Havlak , K. Kennedy, An Implementation of Interprocedural Bounded Regular Section Analysis, IEEE Transactions on Parallel and Distributed Systems, v.2 n.3, p.350-360, July 1991
	Norman Ramsey , Simon Peyton Jones, A single intermediate language that supports multiple implementations of exceptions, ACM SIGPLAN Notices, v.35 n.5, p.285-298, May 2000
	Wuu Yang , Susan Horwitz , Thomas Reps, A program integration algorithm that accommodates semantics-preserving transformations, ACM Transactions on Software Engineering and Methodology (TOSEM), v.1 n.3, p.310-354, July 1992
	Akira Koseki , Hideaki Komatsu , Yoshiaki Fukazawa, A register allocation technique using guarded PDG, Proceedings of the 10th international conference on Supercomputing, p.270-277, May 25-28, 1996, Philadelphia, Pennsylvania, United States
	Stefan M. Freudenberger , Thomas R. Gross , P. Geoffrey Lowney, Avoidance and suppression of compensation code in a trace scheduling compiler, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.4, p.1156-1214, July 1994
	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
	Daniel Weise , Roger F. Crew , Michael Ernst , Bjarne Steensgaard, Value dependence graphs: representation without taxation, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.297-310, January 16-19, 1994, Portland, Oregon, United States
	Dhananjay M. Dhamdhere, E-path_PRE: partial redundancy elimination made easy, ACM SIGPLAN Notices, v.37 n.8, August 2002
	Igor Pechtchanski , Vivek Sarkar, Immutability specification and its applications, Proceedings of the 2002 joint ACM-ISCOPE conference on Java Grande, p.202-211, November 03-05, 2002, Seattle, Washington, USA
	Sumit Gulwani , George C. Necula, Global value numbering using random interpretation, ACM SIGPLAN Notices, v.39 n.1, p.342-352, January 2004
	Litong Song , Krishna Kavi, What can we gain by unfolding loops?, ACM SIGPLAN Notices, v.39 n.2, February 2004
	Jong-Deok Choi , R. Cytron , J. Ferrante, On the Efficient Engineering of Ambitious Program Analysis, IEEE Transactions on Software Engineering, v.20 n.2, p.105-114, February 1994
	Susan Horwitz, Identifying the semantic and textual differences between two versions of a program, ACM SIGPLAN Notices, v.25 n.6, p.234-245, Jun. 1990
	William Pugh , David Wonnacott, Constraint-based array dependence analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.3, p.635-678, May 1998
	Uday P. Khedker , Dhananjay M. Dhamdhere, Bidirectional data flow analysis: myths and reality, ACM SIGPLAN Notices, v.34 n.6, June 1999
	Reinhard von Hanxleden , Ken Kennedy, A balanced code placement framework, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.5, p.816-860, Sept. 2000
	Jens Knoop , Oliver Rüthing , Bernhard Steffen, Partial dead code elimination, ACM SIGPLAN Notices, v.29 n.6, p.147-158, June 1994
	Ron K. Cytron , Jeanne Ferrante, Efficiently computing Φ-nodes on-the-fly, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.3, p.487-506, May 1995
	Jens Knoop , Oliver Rüthing , Bernhard Steffen, Lazy code motion, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Christian W. Probst , Andreas Gal , Michael Franz, Average case vs. worst case: margins of safety in system design, Proceedings of the 2005 workshop on New security paradigms, September 20-23, 2005, Lake Arrowhead, California
	Jens Knoop , Eduard Mehofer, Distribution Assignment Placement: Effective Optimization of Redistribution Costs, IEEE Transactions on Parallel and Distributed Systems, v.13 n.6, p.628-647, June 2002
	Thomas Fahringer , Bernhard Scholz, A Unified Symbolic Evaluation Framework for Parallelizing Compilers, IEEE Transactions on Parallel and Distributed Systems, v.11 n.11, p.1105-1125, November 2000
	Sumit Gulwani , George C. Necula, Precise interprocedural analysis using random interpretation, ACM SIGPLAN Notices, v.40 n.1, p.324-337, January 2005
	Sumit Gulwani , George C. Necula, Discovering affine equalities using random interpretation, ACM SIGPLAN Notices, v.38 n.1, p.74-84, January 2003
	Yasuhiko Minamide, Static approximation of dynamically generated Web pages, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan
	Ciaran O'Donnell, High Level Compiling for Low Level Machines, Proceedings of the IFIP WG10.3. Working Conference on Architectures and Compilation Techniques for Fine and Medium Grain Parallelism, p.309-320, January 20-22, 1993
	Daniel Chavarría-Miranda , John Mellor-Crummey, Effective communication coalescing for data-parallel applications, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA
	Dibyendu Das , U. Ramakrishna, A practical and fast iterative algorithm for φ-function computation using DJ graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.3, p.426-440, May 2005
	Jeffery von Ronne , Ning Wang , Michael Franz, Interpreting programs in static single assignment form, Proceedings of the 2004 workshop on Interpreters, virtual machines and emulators, June 07-07, 2004, Washington, D.C.
	Akira Mori , Tomonori Izumida , Toshimi Sawada , Tadashi Inoue, A tool for analyzing and detecting malicious mobile code, Proceeding of the 28th international conference on Software engineering, May 20-28, 2006, Shanghai, China
	Dhruva R. Chakrabarti , Prithviraj Banerjee, Static Single Assignment Form for Message-Passing Programs, International Journal of Parallel Programming, v.29 n.2, p.139-184, April 2001
	Sumit Gulwani , George C. Necula, A polynomial-time algorithm for global value numbering, Science of Computer Programming, v.64 n.1, p.97-114, January, 2007
	Douglas Gregor , Sibylle Schupp, STLlint: lifting static checking from languages to libraries, Software—Practice & Experience, v.36 n.3, p.225-254, March 2006
	Jingling Xue , Qiong Cai, A lifetime optimal algorithm for speculative PRE, ACM Transactions on Architecture and Code Optimization (TACO), v.3 n.2, p.115-155, June 2006
	Fridtjof Siebert, Proving the absence of RTSJ related runtime errors through data flow analysis, Proceedings of the 4th international workshop on Java technologies for real-time and embedded systems, October 11-13, 2006, Paris, France
	Nic Volanschi, Condate: a proto-language at the confluence between checking and compiling, Proceedings of the 8th ACM SIGPLAN symposium on Principles and practice of declarative programming, July 10-12, 2006, Venice, Italy
	Yutaka Matsuno , Atsushi Ohori, A type system equivalent to static single assignment, Proceedings of the 8th ACM SIGPLAN symposium on Principles and practice of declarative programming, July 10-12, 2006, Venice, Italy
	Philip Brisk , Majid Sarrafzadeh, Interference graphs for procedures in static single information form are interval graphs, Proceedingsof the 10th international workshop on Software & compilers for embedded systems, April 20-20, 2007, Nice, France
	Andreas Bauer, Creating a portable programming language using open source software, Proceedings of the USENIX Annual Technical Conference 2004 on USENIX Annual Technical Conference, p.40-40, June 27-July 02, 2004, Boston, MA
	Adam Sah , Jon Blow, A new architecture for the implementation of scripting languages, Proceedings of the USENIX 1994 Very High Level Languages Symposium Proceedings on USENIX 1994 Very High Level Languages Symposium Proceedings, p.3-3, October 26-28, 1994, Santa Fe, New Mexico
	Yuan-Shin Hwang_cor , Joel Saltz, Interprocedural definition-use chains of dynamic pointer-linked data structures, Scientific Programming, v.11 n.1, p.3-37, January 2003
	Vugranam C. Sreedhar , Guang R. Gao , Yong-fong Lee, Incremental computation of dominator trees, ACM SIGPLAN Notices, v.30 n.3, p.1-12, March 1993
	David A. Berson , Rajiv Gupta , Mary Lou Soffa, GURRR: a global unified resource requirements representation, ACM SIGPLAN Notices, v.30 n.3, p.23-34, March 1993
	Cliff Click , Michael Paleczny, A simple graph-based intermediate representation, ACM SIGPLAN Notices, v.30 n.3, p.35-49, March 1993
	Lennart Beringer, Functional Elimination of Φ-instructions, Electronic Notes in Theoretical Computer Science (ENTCS), v.176 n.3, p.3-20, July, 2007
	Nic Volanschi , Christian Rinderknecht, Unparsed patterns: easy user-extensibility of program manipulation tools, Proceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, January 07-08, 2008, San Francisco, California, USA
	Nomair A. Naeem , Ondrej Lhoták, Efficient alias set analysis using SSA form, Proceedings of the 2009 international symposium on Memory management, June 19-20, 2009, Dublin, Ireland
	Sudheendra Hangal , Monica S. Lam, Automatic dimension inference and checking for object-oriented programs, Proceedings of the 2009 IEEE 31st International Conference on Software Engineering, p.155-165, May 16-24, 2009
	Jun Cao , Ayush Goyal , Krista A. Novstrup , Samuel P. Midkiff , James M. Caruthers, An optimizing compiler for parallel chemistry simulations, International Journal of Parallel Programming, v.37 n.2, p.127-152, April 2009