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