logo of the SSW institute
Institut für Systemsoftware
Johannes Kepler Universität Linz
Fachbereich Informatik
logo of the Cristian Doppler Research Association
Christian Doppler Labor
Monitoring and Evolution of Very-Large-Scale Software Systems

Home

General
Staff
Contact
Partners
Alumni

Research
Areas
Projects
Papers
Books
Reports
Awards

Teaching
Lectures
Exams
B.Projects
M.Theses
PhD Theses
Go Abroad

Misc
Library
Seminars
Gallery
Links
Search

Webmaster


logo of the Johannes Kepler University (JKU)

Array Bounds Check Elimination for the Java HotSpot™ Client Compiler

Thomas Würthinger
Institute for System Software
wuerthinger@ssw.jku.at

Christian Wimmer
Institute for System Software
wimmer@ssw.jku.at

Hanspeter Mössenböck
Institute for System Software
Christian Doppler Laboratory for Automated Software Engineering
moessenboeck@ssw.uni-linz.ac.at


Abstract

Whenever an array element is accessed, Java virtual machines execute a compare instruction to ensure that the index value is within the valid bounds. This reduces the execution speed of Java programs. Array bounds check elimination identifies situations in which such checks are redundant and can be removed. We present an array bounds check elimination algorithm for the Java HotSpot™ VM based on static analysis in the just-in-time compiler.

The algorithm works on an intermediate representation in static single assignment form and maintains conditions for index expressions. It fully removes bounds checks if it can be proven that they never fail. Whenever possible, it moves bounds checks out of loops. The static number of checks remains the same, but a check inside a loop is likely to be executed more often. If such a check fails, the executing program falls back to interpreted mode, avoiding the problem that an exception is thrown at the wrong place.

The evaluation shows a speedup near to the theoretical maximum for the scientific SciMark benchmark suite (40% on average). The algorithm also improves the execution speed for the SPECjvm98 benchmark suite (2% on average, 12% maximum).


Download as PDF

© ACM, 2007. This is the author's version of the work. It is posted here for your personal use. Not for redistribution.
Published in the Proceedings of the 5th International Symposium on Principles and Practice of Programming in Java (PPPJ'07), pp. 125-133. Lisboa, Portugal, September 2007.
http://doi.acm.org/10.1145/1294325.1294343