Detecting equality of variables in programs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Detecting equality of variables in programs

Full text

Pdf (1.25 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: 1 - 11

Year of Publication: 1988

ISBN:0-89791-252-7

Authors

B. Alpern	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): 32, Downloads (12 Months): 177, Citation Count: 83

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.73561 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.

	AH82	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
	AHU74	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	All70	Frances E. Allen, Control flow analysis, ACM SIGPLAN Notices, v.5 n.7, p.1-19, July 1970
	Bak77	Brenda S. Baker, An Algorithm for Structuring Flowgraphs, Journal of the ACM (JACM), v.24 n.1, p.98-120, Jan. 1977 [doi>10.1145/321992.321999]
	CS70	John Cocke, Programming languages and their compilers: Preliminary notes, Courant Institute of Mathematical Sciences, New York University, 1969
	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]
	GW76	Susan L. Graham , Mark Wegman, A Fast and Usually Linear Algorithm for Global Flow Analysis, Journal of the ACM (JACM), v.23 n.1, p.172-202, Jan. 1976 [doi>10.1145/321921.321939]
	Hop71	J. Hopcroft. An n log n algorithm for minimizing the states of a finite automaton. The Theory of Machines and Computations, 189-196, 1971.
	Pol86	Lori L Pollock, An approach to incremental compilation of optimized code, University of Pittsburgh, Pittsburgh, PA, 1986
	RL77	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]
	RL82	J.H. Reif and H. R. Lewis. Efficen* Symbolic Analysis of Programs. Technical Report TR-37- 82, Harvard University, Aiken Computation Laboratory, 33 Oxford St.,Cambridge, Mass 02138, 1982.
	RT82	J.H. Reif and R. E. Tarjan. Symbolic program analysis in almost linear time. SIAM J. Computing, 11(1):81-93, February 1982.
	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]
	Sha80	M. Sharir. Structural analysis: a new approach to flow analysis in optimizing compilers. Computer Languages, 5:141-153, 1980.
	SS70	R.M. Shapiro and H. Saint. The Representation of Algorithms. Technical Report CA-7002-1432, Massachusetts Computer Associates, February 1970.
	Weg75	B. Wegbreit. Property extraction in well-founded property sets. IEEE Trans. on Software Engineering, SE-1(3):270-285, September 1975.
	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]

CITED BY 83

	Jaejin Lee , David A. Padua , Samuel P. Midkiff, Basic compiler algorithms for parallel programs, ACM SIGPLAN Notices, v.34 n.8, p.1-12, Aug. 1999
	Cliff Click, Global code motion/global value numbering, ACM SIGPLAN Notices, v.30 n.6, p.246-257, June 1995
	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
	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
	Cliff Click , Keith D. Cooper, Combining analyses, combining optimizations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.2, p.181-196, March 1995
	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
	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
	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
	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
	Dan Grove , Linda Torczon, Interprocedural constant propagation: a study of jump function implementation, ACM SIGPLAN Notices, v.28 n.6, p.90-99, June 1993
	Joel Auslander , Matthai Philipose , Craig Chambers , Susan J. Eggers , Brian N. Bershad, Fast, effective dynamic compilation, ACM SIGPLAN Notices, v.31 n.5, p.149-159, May 1996
	Cormac Flanagan , James B. Saxe, Avoiding exponential explosion: generating compact verification conditions, ACM SIGPLAN Notices, v.36 n.3, p.193-205, March 2001
	Raja Das , Paul Havlak , Joel Saltz , Ken Kennedy, Index array flattening through program transformation, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.70-es, December 04-08, 1995, San Diego, California, United States
	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
	Keith D. Cooper , L. Taylor Simpson , Christopher A. Vick, Operator strength reduction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.5, p.603-625, September 2001
	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, ACM SIGPLAN Notices, v.25 n.6, p.257-271, Jun. 1990
	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
	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
	Rastislav Bodík , Rajiv Gupta , Vivek Sarkar, ABCD: eliminating array bounds checks on demand, ACM SIGPLAN Notices, v.35 n.5, p.321-333, May 2000
	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
	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
	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
	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
	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
	Ron Cytron , Reid Gershbein, Efficient accommodation of may-alias information in SSA form, ACM SIGPLAN Notices, v.28 n.6, p.36-45, June 1993
	Jiazhen Cai , Robert A. Paige, Look ma, no hashing, and no arrays neither, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.143-154, January 21-23, 1991, Orlando, Florida, United States
	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
	Peng Tu , David Padua, Efficient building and placing of gating functions, ACM SIGPLAN Notices, v.30 n.6, p.47-55, June 1995
	Ron Cytron , Jeanne Ferrante , V. Sarkar, Compact representations for control dependence, ACM SIGPLAN Notices, v.25 n.6, p.337-351, Jun. 1990
	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
	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
	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
	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
	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
	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
	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
	Keith D. Cooper , Li Xu, An efficient static analysis algorithm to detect redundant memory operations, ACM SIGPLAN Notices, v.38 n.2 supplement, p.97-107, February 2003
	Darko Marinov , Robert O'Callahan, Object equality profiling, ACM SIGPLAN Notices, v.38 n.11, November 2003
	Sumit Gulwani , George C. Necula, Global value numbering using random interpretation, ACM SIGPLAN Notices, v.39 n.1, p.342-352, January 2004
	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
	Manuvir Das , Thomas Reps , Pascal van Hentenryck, Semantic foundations of binding-time analysis for imperative programs, Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.100-110, June 21-23, 1995, La Jolla, California, United States
	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
	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
	Sagar Chaki , Alex Groce , Ofer Strichman, Explaining abstract counterexamples, ACM SIGSOFT Software Engineering Notes, v.29 n.6, November 2004
	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
	Chi-Keung Luk , Robert Muth , Harish Patil , Richard Weiss , P. Geoffrey Lowney , Robert Cohn, Profile-guided post-link stride prefetching, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA
	Sumit Gulwani , George C. Necula, Discovering affine equalities using random interpretation, ACM SIGPLAN Notices, v.38 n.1, p.74-84, January 2003
	L. Almagor , Keith D. Cooper , Alexander Grosul , Timothy J. Harvey , Steven W. Reeves , Devika Subramanian , Linda Torczon , Todd Waterman, Finding effective compilation sequences, ACM SIGPLAN Notices, v.39 n.7, July 2004
	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
	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
	K. Rustan M. Leino, Efficient weakest preconditions, Information Processing Letters, v.93 n.6, p.281-288, 31 March 2005
	Keith D. Cooper , Alexander Grosul , Timothy J. Harvey , Steven Reeves , Devika Subramanian , Linda Torczon , Todd Waterman, ACME: adaptive compilation made efficient, ACM SIGPLAN Notices, v.40 n.7, July 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
	Keith D. Cooper , Alexander Grosul , Timothy J. Harvey , Steve Reeves , Devika Subramanian , Linda Torczon , Todd Waterman, Exploring the structure of the space of compilation sequences using randomized search algorithms, The Journal of Supercomputing, v.36 n.2, p.135-151, May 2006
	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
	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
	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
	Shivali Agarwal , Rajkishore Barik , Vivek Sarkar , Rudrapatna K. Shyamasundar, May-happen-in-parallel analysis of X10 programs, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA
	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
	Christoph Reichenbach , Michael G. Burke , Igor Peshansky , Mukund Raghavachari, Analysis of imperative XML programs, Information Systems, v.34 n.7, p.624-642, November, 2009
	Wolfram Amme , Jeffery von Ronne , Michael Franz, SSA-based mobile code: Implementation and empirical evaluation, ACM Transactions on Architecture and Code Optimization (TACO), v.4 n.2, p.13-es, June 2007
	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
	Richard D. Ferrante , James R. Allard, Introducing a CPS style optimizer into an existing compiler, ACM SIGPLAN Notices, v.31 n.12, p.73-79, Dec. 1996
	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
	Ross Tate , Michael Stepp , Zachary Tatlock , Sorin Lerner, Equality saturation: a new approach to optimization, Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 21-23, 2009, Savannah, GA, USA
	Yi Fang , Lenore D. Zuck, Improved Invariant Generation for Tvoc, Electronic Notes in Theoretical Computer Science (ENTCS), v.176 n.3, p.21-35, July, 2007
	Ondřej Lhoták , Laurie Hendren, Evaluating the benefits of context-sensitive points-to analysis using a BDD-based implementation, ACM Transactions on Software Engineering and Methodology (TOSEM), v.18 n.1, p.1-53, September 2008
	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
	Benoit Boissinot , Alain Darte , Fabrice Rastello , Benoit Dupont de Dinechin , Christophe Guillon, Revisiting Out-of-SSA Translation for Correctness, Code Quality and Efficiency, Proceedings of the 2009 International Symposium on Code Generation and Optimization, p.114-125, March 22-25, 2009
	Tristan Ravitch , Steve Jackson , Eric Aderhold , Ben Liblit, Automatic generation of library bindings using static analysis, ACM SIGPLAN Notices, v.44 n.6, June 2009