Eliminating Exception Checks and Partial Redundancies for Java Just-in-Time Compilers

The Java language has a powerful exception-handling mechanism, which is useful for error handling, program control, and safety preservation. However, any instruction capable of throwing an exception inhibits a compiler's ability to optimize the program. In general, a program written in Java tends to have many such instructions, which become barriers to code motion and thus significantly reduce the scope of optimizations. For example, null pointer checks are required for every instance variable access, method call, and array access. Also, array bound checks are required for every array access. In fact, these operations are quite common in typical Java programs.
JIT compilers can optimize Java programs more effectively if runtime trace information is used for optimizations. In the latest version of our JIT compiler, we modified the interpreter to collect the outcome of the first execution of every conditional branch and to pass that information to the JIT compiler to enhance partial redundancy elimination. It is not an ideal solution, in that the interpreter does not always pass accurate branch statistics but only the outcome of the first occurrence, but this is a trade off for increased efficiency of interpretation. Collecting precise branch statistics by the interpreter may significantly slow down its execution.
In this paper, we present a new algorithm for null pointer check elimination, array bound check elimination, and trace-based partial redundancy elimination, all of which have been implemented in the latest IBM JavaTM Just-in-Time (JIT) compiler. Our new algorithm moves null pointer checks out of loops and utilizes the hardware trap mechanism. We enhanced Gupta's algorithm to eliminate more array bound checks. We use runtime trace information and eliminate common subexpressions more aggressively on the first-taken path, employing a variant of the partial redundancy elimination algorithm. We conducted experiments by running SpecJVM98 benchmark programs on Pentium III 600MHz, Windows NT 4.0, and IBM Developer Kit for Windows(R), JavaTM Technology Edition, Version 1.2.2. Our preliminary performance results show significant improvements over previous approaches.