Effective null pointer check elimination utilizing hardware trap
Pages 139 - 149
Abstract
We present a new algorithm for eliminating null pointer checks from programs written in Java™. Our new algorithm is split into two phases. In the first phase, it moves null checks backward, and it is iterated for a few times with other optimizations to eliminate redundant null checks and maximize the effectiveness of other optimizations. In the second phase, it moves null checks forward and converts many null checks to hardware traps in order to minimize the execution cost of the remaining null checks. As a result, it eliminates many null checks effectively and exploits the maximum use of hardware traps. This algorithm has been implemented in the IBM cross-platform Java Just-in-Time (JIT) compiler. Our experimental results show that our approach improves performance by up to 71% for jBYTEmark and up to 10% for SPECjvm98 over the previously known best algorithm. They also show that it increases JIT compilation time by only 2.3%. Although we implemented our algorithm for Java, it is also applicable for other languages requiring null checking.
References
[1]
G. Aigner, and U. Holzle. Eliminating Virtual Function Calls in C++ Programs, In Proceedings of the 10th European Conference on Object-Oriented Programming - ECOOP '96, Volume 1098 of Lecture Notes in Computer Science, Springer-Varlag, pp. 142-166, 1996.
[2]
B. Alpern, C.R. Attanasio, J.J. Barton, M.G. Burke, P. Cheng, J.D. Choi, A. Cocchi, S.J. Fink, D. Grove, M. Hind, S.F. Hummel, D. Lieber, V. Litvinov, M.F. Mergen, T. Ngo, J.R. Russel, V. Sarkar, M.J. Serrano, J.C. Shepherd, S.E. Smith, V.C. Sreedhar, H. Srinivasan, J. Whaley, The Jalapeno virtual machine, IBM Systems Journal, Vol. 39, No. 1, 2000.
[3]
J. Dean, D. Grove, C. Chambers. Optimization of objectoriented programs using static class hierarchy, In Proceedings of the 9th European Conference on Object-Oriented Programming - ECOOP '95, Volume 952 of Lecture Notes in Computer Science, Springer-Varlag, pp. 77-101, 1995.
[4]
J. Gosling, B. Joy, and G. Steele, The Java Language Specification, Addison-Wesley Publishing Co., Reading, MA (1996).
[5]
HotSpot homepage is http://java.sun.com/products/hotspot/.
[6]
K. Ishizaki, M. Kawahito, T. Yasue, M. Takeuchi, T. Ogasawara, T. Suganuma, T. Onodera, H. Komatsu, and T. Nakatani. "Design, Implementation, and Evaluation of Optimizations in a Just-In-Time Compiler." In Proceedings of the ACM SIGPLAN Java Grande Conference, June 1999.
[7]
K. Ishizaki, M. Kawahito, T. Yasue, H. Komatsu, and T. Nakatani. "A Study of Devirtualization Techniques for a Java Just-In-Time Compiler." To appear in the Conference on Object Oriented Programming Systems, Languages & Applications - OOPSLA, 2000.
[8]
J. Knoop, O. Ruthing, and B. Steffen. Lazy code motion. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, ACM SIGPLAN Notices, Vol. 27, No. 7, pp. 224-234, San Francisco, CA, June 1992.
[9]
J. Knoop, O. Ruthing, and B. Steffen. Optimal code motion: Theory and practice. ACM Transactions on Programming Languages and Systems, Vol. 17, No. 5, pp. 777-802, 1995.
[10]
T. Lindholm, Frank Yellin, The Java Virtual Machine Specification, Addison-Wesley Publishing Co., Reading, MA (1996).
[11]
E. Morel and C. Renvoise. Global optimization by suppression of partial redundancies, CACM, Vol. 22, No. 2, Feb. 1979, pp. 96-103.
[12]
Standard Performance Evaluation Corp. "SPEC JVM98 Benchmarks," http://www.spec.org/osg/jvm98/
[13]
T. Suganuma, T. Ogasawara, M. Takeuchi, T. Yasue, M. Kawahito, K. Ishizaki, H. Komatsu, T. Nakatani. Overview of the IBM Java Just-in-Time Compiler, IBM Systems Journal, Vol. 39, No. 1, 2000.
[14]
J. Whaley. Dynamic optimization through the use of automatic runtime specialization. M.Eng., Massachusetts Institute of Technology, May 1999.
[15]
B.S. Yang, S.M. Moon, S. Park, J. Lee, S. Lee, J. Park, Y.C. Chung, S. Kim, K. Ebcioglu, E. Altman. LaTTe: A Java VM Just-in-Time Compiler with Fast and Efficient Register Allocation, Conference on Parallel Architectures and Compilation Techniques, October 1999.
Index Terms
- Effective null pointer check elimination utilizing hardware trap
Recommendations
Effective null pointer check elimination utilizing hardware trap
We present a new algorithm for eliminating null pointer checks from programs written in Java™. Our new algorithm is split into two phases. In the first phase, it moves null checks backward, and it is iterated for a few times with other ...
Effective null pointer check elimination utilizing hardware trap
We present a new algorithm for eliminating null pointer checks from programs written in Java™. Our new algorithm is split into two phases. In the first phase, it moves null checks backward, and it is iterated for a few times with other ...
Effective null pointer check elimination utilizing hardware trap
ASPLOS IX: Proceedings of the ninth international conference on Architectural support for programming languages and operating systemsWe present a new algorithm for eliminating null pointer checks from programs written in Java™. Our new algorithm is split into two phases. In the first phase, it moves null checks backward, and it is iterated for a few times with other ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2000 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 12 November 2000
Published in SIGARCH Volume 28, Issue 5
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations21Total Citations
- 894Total Downloads
- Downloads (Last 12 months)128
- Downloads (Last 6 weeks)23
Reflects downloads up to 13 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in