Related Field Analysis

Aneesh Aggarwal
Keith H. Randall

2001 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'01)
Snowbird, Utah, June 20 - 22, 2001.

[Full text in Postscript, 119KB]


We present an extension of field analysis called related field analysis which is a general technique for proving relationships between two or more fields of an object. We demonstrate the feasibility and applicability of related field analysis by applying it to the problem of removing array bounds checks. For array bounds check removal, we define a pair of related fields to be an integer field and an array field for which the integer field has a known relationship to the length of the array. This related field information can then be used to remove array bounds checks from accesses to the array field. Our results show that related field analysis can remove an average of 50% of the dynamic array bounds checks on a wide range of applications.

We describe the implementation of related field analysis in the Swift optimizing compiler for Java, as well as the optimizations that exploit the results of related field analysis.