A solution to a problem with Morel and Renvoise's “Global optimization by suppression of partial redundancies”

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A solution to a problem with Morel and Renvoise's “Global optimization by suppression of partial redundancies”

Full text

Pdf (337 KB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 10 , Issue 4 (October 1988) table of contents

Pages: 635 - 640

Year of Publication: 1988

ISSN:0164-0925

Authors

Karl-Heinz Drechsler	Siemens AG, ZTI SOF 22, Otto-Hahn-Ring 6, 800O München 83, Federal Republic of Germany
Manfred P. Stadel	Siemens AG, ZTI SOF 22, Otto-Hahn-Ring 6, 800O München 83, Federal Republic of Germany

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 32, Citation Count: 34

Additional Information:

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

ABSTRACT

Morel and Renvoise have previously described a method for global optimization and code motion by suppression of partial redundancies [l]. Morel and Renvoise use data flow analysis to determine expression computations that should be inserted at the end of certain basic blocks and to determine redundant computations that can be eliminated. The execution of these techniques results in the movement of loop invariant expressions out of the loop. In addition to [l] Morel and Renvoise's techniques can also be applied to subexpressions of larger expressions. Then, however, in certain special cases these optimization techniques move expressions to places where some of its subexpressions are neither available nor moved together with the expression. In this paper we present a modification of Morel and Renvoise's algorithm that avoids the above described situations.

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.

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]

CITED BY 34

	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
	Oliver Rüthing , Jens Knoop , Bernhard Steffen, Sparse code motion, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.170-183, January 19-21, 2000, Boston, MA, USA
	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
	Preston Briggs , Keith D. Cooper, Effective partial redundancy elimination, ACM SIGPLAN Notices, v.29 n.6, p.159-170, June 1994
	Dhananjay M. Dhamdhere, E-path_PRE: partial redundancy elimination made easy, ACM SIGPLAN Notices, v.37 n.8, August 2002
	D. M. Dhamdhere , Harish Patil, An elimination algorithm for bidirectional data flow problems using edge placement, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.2, p.312-336, April 1993
	Richard Johnson , Keshav Pingali, Dependence-based program analysis, ACM SIGPLAN Notices, v.28 n.6, p.78-89, June 1993
	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
	Gagan Agrawal , Joel Saltz , Raja Das, Interprocedural partial redundancy elimination and its application to distributed memory compilation, ACM SIGPLAN Notices, v.30 n.6, p.258-269, June 1995
	Jens Knoop , Oliver Rüthing , Bernhard Steffen, The power of assignment motion, ACM SIGPLAN Notices, v.30 n.6, p.233-245, June 1995
	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
	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
	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
	Rastislav Bodík , Rajiv Gupta , Mary Lou Soffa, Complete removal of redundant expressions, ACM SIGPLAN Notices, v.33 n.5, p.1-14, May 1998
	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
	Reinhard von Hanxleden , Ken Kennedy, GIVE-N-TAKE—a balanced code placement framework, ACM SIGPLAN Notices, v.29 n.6, p.107-120, June 1994
	Uday P. Khedker , Dhananjay M. Dhamdhere, Bidirectional data flow analysis: myths and reality, ACM SIGPLAN Notices, v.34 n.6, June 1999
	Gagan Agrawal, Interprocedural Partial Redundancy Elimination With Application to Distributed Memory Compilation, IEEE Transactions on Parallel and Distributed Systems, v.9 n.7, p.609-625, July 1998
	Steve Carr , Philip Sweany, An experimental evaluation of scalar replacement on scientific benchmarks, Software—Practice & Experience, v.33 n.15, p.1419-1445, December 2003
	Keith D. Cooper , Philip J. Schielke , Devika Subramanian, Optimizing for reduced code space using genetic algorithms, ACM SIGPLAN Notices, v.34 n.7, p.1-9, July 1999
	Jens Knoop , Oliver Rüthing , Bernhard Steffen, Partial dead code elimination, ACM SIGPLAN Notices, v.29 n.6, p.147-158, June 1994
	David Callahan , Steve Carr , Ken Kennedy, Improving register allocation for subscripted variables, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Jens Knoop , Oliver Rüthing , Bernhard Steffen, Lazy code motion, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Rastislav Bodík , Rajiv Gupta , Mary Lou Soffa, Complete removal of redundant expressions, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Arthur Sorkin, Some comments on “A solution to a problem with Morel and Renvoise's 'Global optimization by suppression of partial redundancies'”, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.666-668, Oct. 1989
	Ando Saabas , Tarmo Uustalu, Proof optimization for partial redundancy elimination, Proceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, January 07-08, 2008, San Francisco, California, USA
	Arthur Sorkin, Some comments on Morel and Renvoise's “global optimization by suppression of partial redundancies”, ACM SIGPLAN Notices, v.31 n.12, p.69-72, Dec. 1996
	Arthur Sorkin, Some comments on Morel and Renvoise's “global optimization by suppression of partial redundancies”, ACM SIGPLAN Notices, v.31 n.12, p.69-72, Dec. 1996
	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
	K. H. Drechsler , M. P. Stadel, The Pascal-XT code generator, ACM SIGPLAN Notices, v.22 n.8, p.57-78, August 1, 1987
	Cliff Click , Michael Paleczny, A simple graph-based intermediate representation, ACM SIGPLAN Notices, v.30 n.3, p.35-49, March 1993
	D. L. Uvarov, An Optimal Algorithm for Purging Regular Schemes, Programming and Computing Software, v.26 n.6, p.306-325, November-December 2000