Redundancy elimination revisited

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Redundancy elimination revisited

Full text

Pdf (311 KB)

Source

PACT archive
Proceedings of the 17th international conference on Parallel architectures and compilation techniques table of contents

Toronto, Ontario, Canada

SESSION: Compilation table of contents

Pages 12-21

Year of Publication: 2008

ISBN:978-1-60558-282-5

Authors

Keith Cooper	Rice University, Houston, TX, USA
Jason Eckhardt	Rice University, Houston, TX, USA
Ken Kennedy	Rice University, Houston, TX, USA

Sponsors

ACM: Association for Computing Machinery
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 166, Citation Count: 0

Additional Information:

abstract references 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/1454115.1454120 What is a DOI?

ABSTRACT

This work proposes and evaluates improvements to previously known algorithms for redundancy elimination.

Enhanced Scalar Replacement combines two classic techniques, scalar replacement and hash-based value numbering. The former detects redundant array references within and across loop iterations, while the latter detects a large class of redundancies, but only within a single loop iteration. By integrating the two techniques, ESR detects and eliminates a wider range of expression redundancies across loop iterations.

We also extend hash-based value numbering to perform reassociation. Classic redundancy elimination techniques operate on an intermediate representation of the program in which operand association and order is of fixed shape. This rigidity in code shape may sometimes obscure redundancies. Our optimizer attempts to shape the code by changing associativity, exposing more redundancies. Opportunities for ESR, in particular, are increased with reassociation.

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	Randy Allen , Ken Kennedy, Vector Register Allocation, IEEE Transactions on Computers, v.41 n.10, p.1290-1317, October 1992 [doi>10.1109/12.166606]
	2	Ken Kennedy , John R. Allen, Optimizing compilers for modern architectures: a dependence-based approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
	3	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 [doi>10.1145/268946.268966]
	4	Rastislav Bodík , Rajiv Gupta , Mary Lou Soffa, Load-reuse analysis: design and evaluation, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.64-76, May 01-04, 1999, Atlanta, Georgia, United States
	5	I. Bomze, M. Budinich, P. Pardalos, and M. Pelillo. The maximum clique problem. In D.-Z. Du and P. M. Pardalos, editors, Handbook of Combinatorial Optimization, volume 4. Kluwer Academic Publishers, Boston, MA, 1999.
	6	Melvin A. Breuer, Generation of optimal code for expressions via factorization, Communications of the ACM, v.12 n.6, p.333-340, June 1969 [doi>10.1145/363011.363153]
	7	Preston Briggs , Keith D. Cooper, Effective partial redundancy elimination, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.159-170, June 20-24, 1994, Orlando, Florida, United States
	8	Preston Briggs , Keith D. Cooper , L. Taylor Simpson, Value numbering, Software—Practice & Experience, v.27 n.6, p.701-724, June 1997 [doi>10.1002/(SICI)1097-024X(199706)27:6<701::AID-SPE104>3.3.CO;2-S]
	9	David Callahan , Steve Carr , Ken Kennedy, Improving register allocation for subscripted variables, ACM SIGPLAN Notices, v.25 n.6, p.53-65, Jun. 1990
	10	John Cocke, Programming languages and their compilers: Preliminary notes, Courant Institute of Mathematical Sciences, New York University, 1969
	11	Steven J. Deitz , Bradford L. Chamberlain , Lawrence Snyder, Eliminating redundancies in sum-of-product array computations, Proceedings of the 15th international conference on Supercomputing, p.65-77, June 2001, Sorrento, Italy [doi>10.1145/377792.377807]
	12	A. P. Ershov, On programming of arithmetic operations, Communications of the ACM, v.1 n.8, p.3-6, Aug. 1958 [doi>10.1145/368892.368907]
	13	Andrei P. Ershov. Programming Programme for the BESM Computer. Pergamon Press, 1959.
	14	J. Felsenstein, S. Sawyer, and R. Kochin. An efficient method for matching nucleic acid sequences. Nucleic Acids Research, 10(1):133--139, 1982.
	15	Dennis J. Frailey, Expression optimization using unary complement operators, ACM SIGPLAN Notices, v.5 n.7, p.67-85, July 1970
	16	Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
	17	Hans Kellerer, Ulrich Pferschy, and David Pisinger. Knapsack Problems. Springer, Berlin, Germany, 2004.