Safe, Multiphase Bounds Check Elimination in Java

dc.contributor.authorGampe, Andreas
dc.contributor.authorNiedzielski, David
dc.contributor.authorvon Ronne, Jeffery
dc.contributor.authorPsarris, Kleanthis
dc.description.abstractAs part of its type-safety regime, the Java semantics require precise exceptions at runtime when programs attempt out-of-bound array accesses. This paper describes a Java implementation that utilizes a multiphase approach to identifying safe array accesses. This approach reduces runtime overhead by spreading the out-of-bounds checking effort across three phases of compilation and execution: production of mobile code from source code, JIT compilation in the virtual machine, and application code execution. The code producer uses multiple passes (including common subexpression elimination, load elimination, induction variable substitution, speculation of dynamically-verified invariants, and inequality constraint analysis) to identify and prove redundancy of bounds checks. During class-loading and JIT compilation, the virtual machine verifies the proofs, inserts code to dynamically validate speculated invariants, and generates code specialized under the assumption that the speculated invariants hold. At runtime, the method parameters and other inputs are checked against the speculated invariants, and execution reverts to unoptimized code if the speculated invariants do not hold. The combined effect of the multiple phases is to shift the effort associated with bounds-checking array access to phases that are executed earlier and less frequently, thus, reducing runtime overhead. Experimental results show that this approach is able to eliminate more bounds checks than prior approaches with minimal overhead during JIT compilation. These results also show the contribution of each of the passes to the overall elimination. Furthermore, using our multiphase bounds check elimination method increased the speed at which the benchmarks executed by up to 16%.
dc.description.departmentComputer Science
dc.description.sponsorshipThis research was supported in part by the Air Force Research Laboratory under grant F30602-02-1-0001 and the National Science Foundation under grants CCF-0846010, EIA-0117255, CCF-0702527, and CNS-0855247.
dc.publisherUTSA Department of Computer Science
dc.relation.ispartofseriesTechnical Report; CS-TR-2010-001
dc.titleSafe, Multiphase Bounds Check Elimination in Java
dc.typeTechnical Report


Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
300.21 KB
Adobe Portable Document Format

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
1.86 KB
Item-specific license agreed upon to submission