Removing redundancy via exception check motion

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Removing redundancy via exception check motion

Full text

Pdf (253 KB)

Source

Code Generation and Optimization archive
Proceedings of the sixth annual IEEE/ACM international symposium on Code generation and optimization table of contents

Boston, MA, USA

SESSION: Compiler optimization table of contents

Pages 134-143

Year of Publication: 2008

ISBN:978-1-59593-978-4

Authors

Vijay Sundaresan	IBM Canada Ltd., Toronto, ON, Canada
Mark Stoodley	IBM Canada Ltd., Toronto, ON, Canada
Pramod Ramarao	IBM Canada Ltd., Toronto, ON, Canada

Sponsors

ACM: Association for Computing Machinery
SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing
SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	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/1356058.1356077 What is a DOI?

ABSTRACT

Partial redundancy elimination aims to reduce the number of times an expression is computed more than once. The traditional Lazy Code Motion (LCM) algorithm formulated by Knoop, Ruthing and Steffen, through its reliance on unordered bit vectors, is severely limited in its ability to remove redundancy when precise exception semantics are required because bit vectors cannot express the order of exception checks. This paper describes our new PRE algorithm Exception Check Motion that uses the LCM algorithm to treat and optimize exception checks in a similar way to any other expression. Unlike earlier techniques that can remove only the compare instruction of a partially redundant exception check, our solution can eliminate both the compare and trap instructions without any run time code patching or expensive recovery operations. Since it is the trap instructions that restrict subsequent code motions, our technique gives downstream optimizations more flexibility to improve the performance of the resulting code once the partially redundant checks are eliminated. Our analysis has been implemented in the IBM® Testarossa (TR) just-in-time (JIT) compiler in the IBM Developer Kit for Java Release 5.0 as part of the J9 Virtual Machine. We measure performance improvements up to 7.6% and averaging 2.5% across 22 SPEC and DaCapo benchmarks on 4-way IBM pSeries (PowerPC) hardware.

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	Stephen M. Blackburn , Robin Garner , Chris Hoffmann , Asjad M. Khang , Kathryn S. McKinley , Rotem Bentzur , Amer Diwan , Daniel Feinberg , Daniel Frampton , Samuel Z. Guyer , Martin Hirzel , Antony Hosking , Maria Jump , Han Lee , J. Eliot B. Moss , B. Moss , Aashish Phansalkar , Darko Stefanović , Thomas VanDrunen , Daniel von Dincklage , Ben Wiedermann, The DaCapo benchmarks: java benchmarking development and analysis, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
	2	Rastislav Bodík , Rajiv Gupta , Vivek Sarkar, ABCD: eliminating array bounds checks on demand, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.321-333, June 18-21, 2000, Vancouver, British Columbia, Canada
	3	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
	4	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
	5	James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
	6	Manish Gupta , Jong-Deok Choi , Michael Hind, Optimizing Java Programs in the Presence of Exceptions, Proceedings of the 14th European Conference on Object-Oriented Programming, p.422-446, June 12-16, 2000
	7	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
	8	IBM developer kits. http://www-128.ibm.com/developerworks/java/jdk/index.html
	9	Motohiro Kawahito , Hideaki Komatsu , Toshio Nakatani, Effective null pointer check elimination utilizing hardware trap, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.139-149, November 2000, Cambridge, Massachusetts, United States
	10	Jens Knoop , Oliver Rüthing , Bernhard Steffen, Lazy code motion, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.224-234, June 15-19, 1992, San Francisco, California, United States
	11	Jens Knoop , Oliver Rüthing , Bernhard Steffen, The power of assignment motion, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.233-245, June 18-21, 1995, La Jolla, California, United States
	12	Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
	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	National Institute of Standards and Technology. SciMark 2.0 http://math.nist.gov/scimark2/
	15	Rei Odaira , Kei Hiraki, Sentinel PRE: Hoisting beyond Exception Dependency with Dynamic Deoptimization, Proceedings of the international symposium on Code generation and optimization, p.328-338, March 20-23, 2005 [doi>10.1109/CGO.2005.32]
	16	Standard Performance Evaluation Corporation SPECjbb2005 (Java Server Benchmark) http://www.spec.org/jbb2005/
	17	Standard Performance Evaluation Corporation SPECjbb2000 (Java Business Benchmark) http://www.spec.org/jbb2000/
	18	Standard Performance Evaluation Corporation SPECjvm98 Benchmarks. http://www.spec.org/jvm98/
	19	Mark Stoodley , Vijay Sundaresan, Automatically Reducing Repetitive Synchronization with a Just-in-Time Compiler for Java, Proceedings of the international symposium on Code generation and optimization, p.27-36, March 20-23, 2005 [doi>10.1109/CGO.2005.7]
	20	Vijay Sundaresan , Daryl Maier , Pramod Ramarao , Mark Stoodley, Experiences with Multi-threading and Dynamic Class Loading in a Java Just-In-Time Compiler, Proceedings of the International Symposium on Code Generation and Optimization, p.87-97, March 26-29, 2006 [doi>10.1109/CGO.2006.16]