A Comprehensive Approach to Array Bounds Check Elimination for Java

The Java programming language requires array referen e range he ks at run time to guarantee a program's safe exe ution. If the array index ex eeds the range, the run-time environment must throw an IndexOutOfBoundsEx eption at the pre ise program point where the array referen e o urs. Compilers generate onditional bran h instru tions for implementing array bounds he ks. A bran h instru tion has great performan e penalties in modern pipelined ar hite tures. Also, it makes many other optimizations diÆ ult. For array-intensive appli ations, array bounds he ks may ause a heavy run-time overhead, and thus it is bene ial to eliminate all he ks whi h a stati analysis an prove to be unneeded. Array bounds he ks are required by some other languages su h as Ada and Fortran, and some bounds he k elimination algorithms have been developed for these kinds of languages. How-ever, these algorithms are not dire tly appli able for Java appli ations be ause of the pre ise-ex eption requirement of the language. We present a new approa h to eliminate array bounds he ks in Java by using stati analyses. Our approa h is based upon a ow-sensitive intrapro edural analysi