A comprehensive approach to array bounds check elimination for Java /

We present a new approach to eliminate array bounds checks in Java by using static analyses. Our approach is based upon a flow-sensitive intraprocedural analysis called variable constraint analysis (VCA). VCA collects constraints between locals related to array references. The array bounds check problem is formulated as solving a system of difference constraints. The analysis builds a small constraint graph for each important point in a method, and then computes the shortest-path weight of the graph. The shortest-path weights from upper bound to array index and from the index to lower bound indicates the safety of checks. Using VCA as the base analysis, we also show how two further analyses can improve the results of VCA. Array field analysis is applied on each class and provides information about some arrays stored in fields, while rectangular array analysis is an interprocedural analysis to approximate the shape of arrays, and is useful for finding rectangular (non-ragged) arrays. (Abstract shortened by UMI.