Optimizing for space and time usage with speculative partial redundancy elimination

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimizing for space and time usage with speculative partial redundancy elimination

Full text

Pdf (178 KB)

Source

Language, Compiler and Tool Support for Embedded Systems archive
Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems table of contents

Washington, DC, USA

SESSION: Compilers and optimization table of contents

Pages: 221 - 230

Year of Publication: 2004

ISBN:1-58113-806-7

Also published in ...

Authors

Bernhard Scholz	University of Sydney, Australia
Nigel Horspool	University of Victoria, Victoria, BC, Canada
Jens Knoop	Technische Universität Wien, Wien, Austria

Sponsors

ACM: Association for Computing Machinery
SIGBED: ACM Special Interest Group on Embedded Systems
SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

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

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

ABSTRACT

Speculative partial redundancy elimination (SPRE) uses execution profiles to improve the expected performance of programs. We show how the problem of placing expressions to achieve the optimal expected performance can be mapped to a particular kind of network flow problem and hence solved by well known techniques. Our solution is sufficiently efficient to be used in practice. Furthermore, the objective function may be chosen so that reduction in space requirements is the primary goal and execution time is secondary. One surprising result that an explosion in size may occur if speed is the sole goal, and consideration of space usage is therefore important.

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	Rastislav Bodik , Rajiv Gupta , Mary Lou Soffa, Path-sensitive, value-flow optimizations of programs (program analysis), 1999
	2	Rastislav Bodík , Rajiv Gupta , Mary Lou Soffa, Complete removal of redundant expressions, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.1-14, June 17-19, 1998, Montreal, Quebec, Canada
	3	Qiong Cai , Jingling Xue, Optimal and efficient speculation-based partial redundancy elimination, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
	4	L. Ford and D. Fulkerson. Flows in Networks. Princeton University Press, 1962.
	5	Andrew V. Goldberg , Robert E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM (JACM), v.35 n.4, p.921-940, Oct. 1988 [doi>10.1145/48014.61051]
	6	Rajiv Gupta , David A. Berson , Jesse Z. Fang, Path Profile Guided Partial Redundancy Elimination Using Speculation, Proceedings of the 1998 International Conference on Computer Languages, p.230, May 14-16, 1998
	7	Rajiv Gupta , Rastislav Bodík, Register Pressure Sensitive Redundancy Elimination, Proceedings of the 8th International Conference on Compiler Construction, Held as Part of the European Joint Conferences on the Theory and Practice of Software, ETAPS'99, p.107-121, March 22-28, 1999
	8	Max Hailperin, Cost-optimal code motion, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.6, p.1297-1322, Nov. 1998 [doi>10.1145/295656.295664]
	9	R. Nigel Horspool , H. C. Ho, Partial Redundancy Elimination Driven by a Cost-Benefit Analysis, Proceedings of the 8th Israeli Conference on Computer-Based Systems and Software Engineering, p.111, June 18-19, 1997
	10	V. King , S. Rao , R. Tarjan, A faster deterministic maximum flow algorithm, Journal of Algorithms, v.17 n.3, p.447-474, Nov. 1994
	11	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 [doi>10.1109/TPDS.2002.1011416]
	12	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 [doi>10.1145/183432.183443]
	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	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 [doi>10.1145/325694.325715]
	15	Bernhard Steffen, Property-Oriented Expansion, Proceedings of the Third International Symposium on Static Analysis, p.22-41, September 24-26, 1996
	16	H. Stone. Multiprocessor scheduling with the aid of network flow algorithms. IEEE Transactions on Software Engineering, vol. SE-3, 1, pages 85--93, January 1977.

CITED BY 3

	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
	Bernhard Scholz , Bernd Burgstaller , Jingling Xue, Minimal placement of bank selection instructions for partitioned memory architectures, ACM Transactions on Embedded Computing Systems (TECS), v.7 n.2, p.1-32, February 2008
	Brian R. Murphy , Vijay Menon , Florian T. Schneider , Tatiana Shpeisman , Ali-Reza Adl-Tabatabai, Fault-safe code motion for type-safe languages, Proceedings of the sixth annual IEEE/ACM international symposium on Code generation and optimization, April 05-09, 2008, Boston, MA, USA