Three goals of the Java** programming language¹ and execution environment are bit-for-bit reproducibility of results on different platforms, safety of execution, and ease of programming and testing. A crucial component of the Java language specification for achieving the latter two goals is that a program only be allowed to access objects via a valid pointer, and that programs only be allowed to access elements of an array that are part of the defined extent of the array. A naive implementation of this specification component requires every access to every element of an array to check the validity of all base pointers and indices involved in the access.

Figure 1 shows a typical representation of a four-dimensional array in Java. A naive checking of a reference to element A[1][2][3][4], indicated in the figure, would require four base pointer tests and four range tests: A, A[1], A[1][2], and A[1][2][3] must all be tested as valid pointers; 1, 2, 3, and 4 must all be tested as valid indices along the corresponding axes of the array. If the entire array is accessed, a total of 4N base pointer tests and 4N range tests will be necessary, where N is the total number of elements in the array. In this paper, we present a suite of techniques to greatly reduce the number of run-time tests. In many cases, the run-time tests can be completely eliminated.

Figure 1

The above-mentioned goal of bit-for-bit reproducibility of results, combined with the ability to catch exceptions and examine the state of the program at the time the exception was thrown, imply that it is not sufficient to determine that an invalid reference occurred. Rather, any optimizations of valid reference checking must cause all exceptions that would have been thrown in the original program to still be thrown. The exceptions must be thrown in precisely the same order, with respect to the rest of the computation, dictated by the original program semantics. The techniques we describe fulfill this requirement. Our methods also handle loops that catch exceptions within their bodies (i.e., with nested try blocks).

We note that the techniques and methods described here are not restricted to Java. They can be applied to any language in which the bounds of an array can be determined at run time. They could be used, for example, in C and FORTRAN compilers that want to provide an option to check array references.

The rest of this paper is organized as follows. The next section presents an informal overview of our optimizations and is followed by an introduction to the concept of safe bounds, used throughout the paper. The fourth section presents the first of our optimization techniques, the exact method. The succeeding sections present other techniques, the general, compact, and restricted methods, respectively. The eighth section discusses an inspector-executor variant of our methods, to handle more complex cases. The ninth section explains our optimizations in the context of multithreaded execution. The tenth section presents some experimental results, followed by a discussion of related work. Finally, we present our conclusions.

Overview of the optimizations

doubleA[] = new double[lo(A):up(A)]

declares a one-dimensional array A of doubles. Note that we allow an explicit declaration of the lower bound lo(A) of array A. In Java, the lower bound is always zero. Also, Java array declarations specify the number of elements of the array. Therefore, the Java declaration

double A[] = new double[n]

would correspond to the declaration

double A[] = new double[0:n - 1]

in our notation.

An array element reference is denoted by A[], where is an index into the array. For the reference to be valid, A must not be null, and must be within the valid range of indices for A: lo(A), lo(A) + 1, ... , up(A). If A is null, then the reference causes a null pointer violation. In Java, this corresponds to the throwing of a NullPointerException. If A is a valid pointer and is less than the lower bound lo(A) of the array, then the reference causes a lower bound violation. If A is a valid pointer and is greater than the upper bound up(A) of the array, then the reference causes an upper bound violation. Java does not distinguish between lower and upper bound violations. A bound violation (lower or upper) in Java causes an ArrayIndexOutOfBoundsException to be thrown.

Multidimensional arrays are treated as arrays of arrays:

double M[][] = new double[l₁:u₁] [l₂:u₂]

declares an array M with lower bound l₁ and upper bound u₁. Each element of M is an array of doubles, with lower bound l₂ and upper bound u₂. M is an example of a rectangular array. Rectangular arrays have uncoupled bounds along each axis. As in Java, we also allow ragged arrays, where the bounds for one axis depend on the coordinate along another axis. A triangular array is an example of a ragged array:

double T[][] = new double[1:n][]

T[i] = new double[1:i], i = 1,...,n

Even though ragged arrays are allowed and treated by our techniques, we do have optimizations that take advantage of rectangular arrays.

Arbitrary array lower bounds, the distinction between lower bound and upper bound violations, and treatment for rectangular arrays are features of our work that are not strictly necessary for Java applications. Our motivation to include them is twofold: First, we want our methods to be applicable to other programming languages, in particular C, C++, and FORTRAN 90. Second, we want to be prepared to handle extensions to Java that are being considered to efficiently support numerical computing, as described in Reference 2.

Array accesses typically occur in the body of loops. Our optimizations operate on do-loops, which are for-loops of the form:

for (i = l; iu; i++){
	B(i)
}

where i is the index variable of the loop, l defines the lower bound of the loop, and u defines the upper bound of the loop. The iteration space of the loop is defined by the range of values that i takes: l, l + 1, ... , u. All loops have a unit step, and therefore a loop with l > u has an empty iteration space. B(i) is the body of the loop, which typically contains references to the loop index variable i. As a shorthand, we represent the above loop structure by the notation L(i, l, u, B(i)). Note that loops with positive nonunity strides can be normalized by the transformation

	for (i = l; iu; i = i + s){
		B(i)
	}
becomes
	for (i = 0; i (u - l)/s ; i++){
		B(l + is)
	}
A loop with negative stride can be first transformed into a loop with a positive stride:
	for (i = u; i l; i = i - s){
		B(i)
	}
becomes
	for (i = l; i u; i = i + s){
		B(u + l - i)
	}

Loops are often nested within other loops. Standard control-flow and data-flow techniques³ can be used to recognize many for, while, and do-while loops, which occur in Java and C, as do-loops. Many goto loops, occurring in C and FORTRAN, can be recognized as do-loops as well.

Four different tests can be applied to an array reference A[i]. A null test verifies whether A is a null pointer. An lb test verifies whether i lo(A), and a ub test verifies whether i up(A). Finally, a test called all tests verifies whether lo(A) i up(A). Tests for bounds subsume null tests, since a null array can be set to have an empty extent. Furthermore, we show in the next section that for do-loops only one of three cases can occur for each iteration and each array reference: (1) an lb test is required, (2) a ub test is required, or (3) no test is required. In many situations it is possible to precisely determine which case occurs. In other situations, one has to be conservative and adopt a stronger test than absolutely required. In particular, an all tests can be used to detect any possible violations.

We introduce later a method for deriving the minimum set of tests required at each iteration of a simple loop with no nesting. This method will be referred to as the exact method. It provides the general framework that is used by the subsequent methods, which handle nested loops. The exact method specifies, for each iteration and each array reference, which test of the three named above is required, if any. A loop with array references in its body is split at compile time into up to 3 consecutive regions, each with a specialized version of the loop body. At run time, no more than 2 + 1 regions are actually executed.

This level of code replication is not practical in general. However, one can reduce the number of code versions by merging together regions, at the expense of performing superfluous tests. This is shown in the section describing the general method. In practice, this does not increase execution time. The regions where tests are required will usually be found to be empty at run time so that the tests in these regions are never normally executed. Reducing the number of distinct regions will not only decrease code size, but may also decrease execution time. A practical version of the exact method splits an iteration space i = l, l + 1, ... , u into three regions:

1. A region of the iteration space where no tests are needed. This region is defined by a safe lower bound l^s and a safe upper bound u^s. The range of values of i in this region is l^s, l^s + 1, ... , u^s.
2. A region of the iteration space where the index variable has values smaller than the safe lower bound l^s. For this region i = l, l + 1, ... , l^s - 1.
3. A region of the iteration space where the index variable has values greater than the safe upper bound u^s For this region i = u^s + 1, u^s + 2, ... , u.

We extend this method to nested loops in the later section, "The general method," recursively splitting each iteration space into three regions. When applied to a perfect d-dimensional loop nest, this method leads to 3^d distinct loop nests, each potentially executing a different code version. One can reduce the number of distinct code versions by merging different versions. In the extreme case, it is possible to use only two versions. This method will be referred to as the general method.

In the sixth section we present a method that avoids this exponential blow-up in static code size. This method is referred to as the compact method. When applied to a perfect d-dimensional loop nest, it results in 2d + 1 loop nests. Depending on the simplifications adopted, it can use from 2 up to 2d + 1 different code versions.

Finally, in the seventh section we describe a tiling method that can be applied to certain types of loop nests. It effectively implements the compact method through generated code of a very simple form. The method uses two versions for each loop body (no tests and all tests enabled). This method is referred to as the restricted method.

These four methods apply to Java as well as to FORTRAN or C and work for all machine architectures. Additional optimizations are possible in important special cases. We briefly discuss two of these optimizations now: how to determine a valid index with a single test and how to test for null pointers. We do not discuss special optimization techniques any further in this paper.

In the particular case of Java an all tests test can be implemented with a single comparison. Because Java does not distinguish between lower bound and upper bound violations, and because lo(A) = 0 always, it suffices to test if i < up(A) + 1 using unsigned arithmetic. A negative number appears, in unsigned arithmetic, as a very large positive number which, by the Java language specification, is always larger than the largest possible array extent. This technique is used, for example, in the IBM HPCJ (High-Performance Compiler for Java) project.⁴

The optimization of checks for null pointer violations in array references is a direct consequence of the optimization of checks for bound violations, as discussed in the next section. There are also many ad hoc solutions to the optimization of null pointer violations. For machines with segmented memory architecture, such as the IBM POWER2 Architecture*, null pointers can be represented by a pointer to a protected segment. For machines with linear, but paged, memory architecture, a protected segment can be simulated with a region of protected pages. Any attempts at access through a null pointer will immediately cause a hardware exception that can then be translated into the appropriate software exception. This implementation completely eliminates the need for any explicit checks for null pointer violations in the code. It is also applicable to all pointer dereferences, not just array accesses. Despite the complications in properly translating a hardware exception, this technique has been successfully used, for example, in the CACAO project.⁵

Computing safe bounds

We illustrate the computation of safe regions with a simple example. We then proceed to formalize it to more general cases. Consider the simple loop:

for (i = l; i u; i++){
	B(i)
}

which we represent as L(i, l, u, B(i)). B(i) is the body of the loop and, in general, contains references to the loop index variable i. The iteration space of this loop consists of the range of values i = l, l + 1, ... , u.

Let there be a single array reference A[i] in the loop body B(i). We denote the lower bound of A by lo(A) and the upper bound of A by up(A). Therefore, for the array reference A[i] to be valid we must have lo(A) i up(A). If A is null, we define lo(A) = 0 and up(A) = - 1. This guarantees that A[i] is never valid if A is null. We can split the iteration space of the loop into three regions [1], [2], and [3], defined as follows:

[1] : (l i u) ^ (i < lo(A))	(1)
[2] : (l i u) ^ (lo(A) i up(A))	(2)
[3] : (l i u) ^ (i > up(A))	(3)

Region [1] corresponds to those iterations of the loop for which the index i into array A is too small. Therefore, an lb test is required before each array reference in this region. No tests are required in region [2], since the index i falls within the bounds of A. Finally, a ub test is required in region [3], because the values of i are too large to index A.

Using Equation 2, we can compute the lower and upper bounds and of the safe region:

= max(l, lo(A))	(4)
= min(u, up(A))	(5)
[2] : i = ,...,	(6)

Similarly, we use Equation 1 and Equation 3 to compute the lower and upper bounds of regions [1] and [3], respectively:

[1] : i = l,..., min(u + 1, lo(A)) - 1	(7)
[3] : i = max(l - 1, up(A)) + 1,..., u	(8)

Note that min(u + 1, lo(A)) = , except when lo(A) < l or lo(A) > u + 1. In the former case, [1] is empty; in the latter case, [2] is empty. To handle these cases, and the symmetric upper bound cases, we redefine

= min(u + 1, max(l, lo(A)))	(9)
= max(l - 1, min(u, up(A)))	(10)

We can now express the bounds of each of the regions just in terms of l, u, , and :

[1] : i = l,..., - 1	(11)
[2] : i = ,...,	(12)
[3] : i = + 1,..., u	(13)

Equations 11-13 define the same regions as Equations 6-8. The values of region bounds are different only for empty regions, but they are still empty.

In Figure 2 we illustrate the values of and for different relative positions of iteration bounds and array bounds. Figure 2A has empty regions [1] and [3], whereas region [2] comprises the entire iteration space. Region [1] is empty in Figure 2B, whereas region [3] is empty in Figure 2C. All three regions are nonempty in Figure 2D. Regions [2] and [3] are empty in Figure 2E, because all values of i fall below the lower bound of A. Finally, regions [1] and [2] are empty in Figure 2F, since all values of i fall above the upper bound of A.

Figure 2

In the general case, we have an array reference of the form A[f(i)] in the body B(i) of a loop. Depending on the behavior of f(i), we can compute safe bounds and that partition the iteration space into three regions, as defined by Equations 11-13. Region [2] is safe, and no test is defined in it. We define tests [1] and [3] that are sufficient for regions [1] and [3], respectively. Expressions for , , and for various forms of f(i) are described in Appendix A. The safe bounds are computed so that we always have - 1 and + 1. These properties are important for the correct functioning of our methods.

An exact method

In this section we treat references of the form A[f(i)] that allow the computation of safe bounds as described in the previous section. The eighth section discusses how to handle more complex subscripts. We first describe how the method generates optimized code, and then we illustrate the method with an example.

Code generation. The method works as follows. Let L(i, l, u, B(i)) be a loop on index variable i and body B(i). Let there be references of the form A_j[f_j(i)], j = 1, ... , , in body B(i). Each array reference A_j[f_j(i)] partitions the iteration space into three (each possibly empty) regions:

^j[1] : i = l,..., ^j - 1

^j[2] : i = ^j,..., ^j

^j[3] : i = ^j + 1,..., u

as defined by Equations 11-13. We call these regions defined by a single array reference simple regions. Also, each region ^j[k] has a test ^j[k] associated with it, which describes what kind of test has to be performed for reference A_j[f_j(i)] in that region. The test ^j[2] for region ^j[2] always specifies no test, because ^j[2] is a safe region with respect to this reference. The tests ^j[1] and ^j[3], for regions ^j[1] and ^j[3], respectively, can be any one of ub test (an upper bound test), lb test (a lower bound test), or all tests (both a lower and an upper bound test). The exact choice depends on characteristics of the array reference A_j[f_j(i)]. This issue is discussed in detail in Appendix A. For each region ^j[k] we denote its lower bound by ^j[k].l and its upper bound by ^j[k].u.

Two references A_j[f_j(i)] and A_k[f_k(i)] can be thought of as partitioning the iteration space into five regions defined by the four points ^j, ^j, ^k, and ^k. We illustrate this in Figure 3 for two references, A₁[f₁(i)] and A₂[f₂(i)]. Note that some of the resulting regions may be empty, in general. The resulting regions are a subset of the 3 · 3 = 9 regions formed by all combinations of intersections of two simple regions, one from each reference.

Figure 3

In general, given the references A_j[f_j(i)], we can create a vector of all 3 regions formed by intersecting the simple regions from different array references:

[x1·x2·...·x ] =
¹[x1] ²[x2] ... [x]	(14)

Each index x_k is 1, 2, or 3. The lower bound of a region [x₁ · x₂ · ... · x] is the maximum of the lower bounds of the forming simple regions. Correspondingly, its upper bound is the minimum of the upper bounds of the forming simple regions:

[x1 · x2 · ... · x].l =
	max (¹ [x1].l, ² [x2].l,..., [x].l)	(15)
[x1 · x2 · ... · x].u =
	min(¹ [x1].u, ² [x2].u,..., [x].u)	(16)

Finally, the tests that characterize region [x₁ · x₂ · ... · x ] can be described by:

[x1·x2·...· x] = {j [xj], j = 1,..., }

(17)

That is, the combination of the tests for each simple region ^j [x_j].

Using this partitioning of the iteration space into 3 regions, the loop

for (i = l; i u; i++){       B(i) }

(18)

can be transformed into 3 loops, each one implementing one of the regions [x₁ · x₂ · ... · x]. The body of each region can be specialized to perform exactly the tests described by [x₁ · x₂ · ... · x_{]. We use Bx1x2... x}(i) to denote the body B(i) specialized with the tests described by [x₁ · x₂ · ... · x]:

for (i = [1 · 1 ·...· 1].l;      i [1 · 1 ·...· 1].u; i++) {B11...1(i)} for (i = [1 · 1 ·...· 2].l;      i [1 · 1 ·...· 2].u; i++) {B11...2(i)} for (i = [1 · 1 ·...· 3].l;      i [1 · 1 ·...· 3].l; i++) {B11...3(i)} · · · for (i = [1 · 2 ·...· 1].l;      i [1 · 2 ·...· 1].u; i++) {B12...1(i)} for (i = [1 · 2 ·...· 2].l;      i [1·2·...·2].u; i++) {B12...2(i)} for (i [1 · 2 ·...· 3].l;       i [1 · 2 ·...· 3].u; i++){B12...3(i)} · · · for (i = [3 · 3 ·...· 1].l;      i [3 · 3 ·...· 1].u; i++) {B33...1(i)} for (i = [3 · 3 ·...· 2].l;      i [3·3·...·2].u; i++) {B33...2(i)} for (i = [3 · 3 ·...· 3].l;      i [3 · 3 ·...· 3].u; i++) {B33...3(i)}

(19)

Note that the order of the resulting loops is important, although there are many correct orders. The requirement is that, for any value of j, region [x₁ · ... · x - 1 · 1 · x_j + 1 · ... · x] has to precede [x₁ · ... · x_{j - 1} · 2 · x_{j + 1} · ... · x] which in turn has to precede [x₁ · ... · x_{j - 1} · 3 · x_{j + 1} · ... · x].

Out of the 3 possible regions formed by the intersection of the simple regions, no more than 2 + 1 are nonempty and are actually executed at run time. Which of the 3 regions are nonempty depends on the relative positions of the 2 safe bounds ¹,..., , ¹,..., . Let p₁,..., p₂ be the list obtained by sorting ¹, ..., , ¹ + 1,..., + 1 in ascending order. Define p₀ = l and p _{2 + 1} = u + 1. The safe bounds ¹,..., , ¹, ... , partition the iteration space into 2 + 1 (each possibly empty) regions [k], k = 0, 1,..., 2 defined by

[k] : i = pk,...,pk + 1 - 1

(20)

Each region [k] corresponds to a region [x₁ · x₂ · ... · x] defined by

xj =

{

1 if j pk + 1 3 if j < pk 2 if ( j < pk + 1) ^ (j pk)

(21)

(It can occur that both ^j p_k + 1 and ^j < p_k. In that case, region [k] is necessarily empty, and the choice of x_j is irrelevant.) Let M(k) be the function that defines the correspondence [M(k)] [k] for k = 0,..., 2. Then the loop

for (i = l; i u; i++){      B(i) }

(22)

can be transformed to

for (k = 0; k 2; k++){      for (i = pk; i < pk + 1; i++){            BM(k)(i) }

(23)

If the order of the safe bounds ¹,..., , ¹,..., is known at compile time, the mapping function M(k) can also be determined. In this case, only the loop body versions that are actually executed need to be generated. In general, the order of the safe bounds is not known, and B_M(k)(i) has to be selected at run time from the set of all possible 3 body versions.

An example. In the interest of conciseness, we use a very simple code fragment to illustrate this method. Figure 4A illustrates the original loop to be transformed. It has two array references, A₁[i - 2] and A₂[i + 2], each generating three simple regions: ¹[1:3] and ²[1:3], respectively. The straightforwardly transformed code, using the exact method, is shown in Figure 4B. We note that:

¹ =	min(u + 1, max(l, 3))	(24)
² =	min(u + 1, max(l, - 1))	(25)
¹ =	max(l - 1, min(u, n + 2))	(26)
² =	max(l - 1, min(u, n - 2))	(27)
¹[1] = ²[1] =	lb test	(28)
¹[3] = ²[3] =	ub test	(29)

which does not provide us with enough information to order the safe bounds ¹, ², ¹, and ². We implement the code in Figure 4B according to Equation 19. We could have used the method in Equation 23, but it would still have required all 3 body versions to be generated.

Figure 4

Now let n = 10, as shown in Figure 5A. In this case, the expressions for the safe bounds become:

¹ = min(u + 1, max(l, 3))	(30)
² = min(u + 1, max(l, - 1))	(31)
¹ = max(l - 1, min(u, 12))	(32)
² = max(l - 1, min(u, 8))	(33)

and we can order ² ¹ ² ¹. In particular, this is the ordering shown in Figure 3. We only need to generate code for five loops, as shown in Figure 5B. In some cases, a compiler with appropriate symbolic analysis can even eliminate some of these five loops. For example, if the compiler could prove that l > 2, neither of the first two loops (body versions B₁₁(i) and B₁₂(i)) would be necessary.

Figure 5

Summary of the exact method. The exact method transforms code so that, for each iteration of the original loop, only those tests that cannot be shown to be unnecessary are performed. In the straightforward application of the method to a loop with array references in its body, 3 new loops are generated, each with a slightly different body. No more than 2 + 1 of these loops are actually executed at run time. In some situations, compile-time analysis can show that some of these loops implement empty regions of the iteration space and, therefore, can be discarded.

The general method

The general method works by partitioning the iteration space of a loop always into three regions, independent of the number of array references in the body of the loop. One of the regions is a safe region: no array reference in that region can cause a violation. Another region precedes the safe region, in iteration order. Finally, the third region succeeds the safe region, in iteration order. This method can be applied to each and every loop of an arbitrary loop nest individually. The general method does not specialize the tests as much as the exact method, but it does identify the same safe regions that can be executed without any tests.

Transforming a single loop. Consider the loop L(i, l, u, B(i)), with references of the form A_j[f_j(i)] in its body. Using the concepts developed in the previous two sections, we can compute its safe region as the intersection of all simple safe regions. This safe region is defined by the range of values of i = l^s, l^s + 1, ... , u^s where:

ls=max(¹, ²,..., )	(34)
us=max(ls-1, min(¹, ²,..., ))	(35)

The l^s - 1 term in the expression for u^s is necessary to handle cases where the safe region is empty. We can then partition the iteration space of the loop into three (each possibly empty) regions:

[1] : i = l,..., ls-1	(36)
[2] : i = ls,..., us	(37)
[3] : i = us+1,..., u	(38)

This partitioning is not very different from our very first example in the third section, except that now it applies to a loop with an arbitrary number of array references in its body. We illustrate this for two references: A₁[f₁(i)] and A₂[f₂(i)] in Figure 6. Region [2] is the intersection of the safe simple regions ¹[2] and ²[2]. Correspondingly, region [1] is the union of the unsafe simple regions ¹[1] and ²[1]. Region [3] is the union of the unsafe simple regions ¹[3] and ²[3]. With reference to Figure 3, [1] is formed by merging all regions preceding [2 · 2], and region [3] is formed by merging all regions succeeding region [2 · 2].

Figure 6

Region [2] is the safe region, and its body can be implemented without any tests. We denote this version of the loop body by B(notest(i)). Conversely, the bodies of regions [1] and [3] need at least some tests. For simplicity, we can implement both with a version B(test(i)) of body B(i). This version performs an all tests test before each and every array reference.

The implementation of the general method consists of the transformation:

for(i = l; iu; i++){      B(i) }

becomes

for (i = l; ils-1; i++){      B(test(i)) } for (i = ls; ius; i++){      B(notest(i)) } for (i = us+1; iu; i++){      B(test(i)) }

(39)

or, in shorthand:

L(i, l, u, B(i))

{

L1(i, l, ls-1, B(test(i))) L2(i, ls, us, B(notest(i))) L3(i, us+1, u, B(test(i)))

(40)

The code expansion in this case is only twofold, since the same code for B(test(i)) can be used twice. Methods to realize all three resulting loops using only two instances of B(i) are discussed in Appendix B.

Recursive application of the transformation. If the body B of a loop contains other loops, then the same transformation can be applied to each of the loops in B. The transformation can be applied individually to each and every loop in a general loop nest. In fact, the final result is independent of the order in which the individual loops are transformed.

Consider the case of the two-dimensional loop nest L(i, l_i, u_i, L'(j, l_j, u_j, B(i, j))). By first applying the transformation to the L loop, we generate a region without any tests on array references indexed by i:

L(i, l_i, u_i, L'(j, l_j, u_j, B(i, j)))

becomes

L₁(i, l_i, l_i^s-1, L'(j, l_j, u_j, B(test(i), j)))
L₂(i, l_i^s, u_i^s, L'(j, l_j, u_j, B(notest(i), j)))
L₃(i, u_i^s+1, u_i, L'(j, l_j, u_j, B(test(i), j)))

We can now apply the transformation to each of the three L' loops. This will generate two regions without any tests on array references indexed by j and one region without any tests on array references indexed by either i or j as seen in Figure 7. This transformation partitions the iteration space into nine regions, and requires four different versions of the loop body B(i).

Figure 7

An example of the general method. For simplicity, we give an example of single-threaded code with rectangular arrays. In the ninth section is a discussion of the application of these optimizations to multithreaded code. The program of Figure 8 will be used in this example. It implements a step of a two-dimensional Jacobi relaxation.⁶ We chose it because it is a well-known operation that illustrates a loop nest with various array references in its body. Also, the array references all use slightly different indices, making our example more interesting.

Figure 8

Figure 9 shows the loop implemented with naive tests. The statement

ifAccessViolation(A,i) throwException

throws the appropriate exception if A is a null pointer, i is below the lower bound of A, or i is above the upper bound of A. In the actual executable code, the tests would be interweaved with the individual array references, and the order of tests would be slightly different, but this example gives an idea of the cost of naive testing. Figure 10 shows the loop nest optimized for testing using the general method. In each of the resulting loops, we list the violations that can occur in its body. The code with explicit tests for the different versions of the loop body are shown in Figure 11. The minimal tests needed for the i₁ and i₃ loops differ in that the i₁ loop only needs to test for lower bounds violations, and the i₃ loop only needs to test for upper bounds violations. By using the transformation of Equation 39, the version for both loops can be the same, as indicated in Figure 10.

Figure 9 Figure 10 Figure 11

Transforming the loops. The optimized code is the result of the following transformations. First, the outer i loop is split into three loops (i₁, i₂, and i₃), as shown in Figure 10. The middle loop, i₂, corresponds to those iterations of the original i loop that cannot cause bound violations on array references indexed by i. Within this loop, these array references need not be tested. This is the safe region for loop i.

The first loop, i₁, executes those iterations of the original i loop whose values of i precede the safe region. Within this loop, all array references indexed by i need to be tested. Because the subscript expressions on i are monotonically increasing across the iteration space of the i loop, only lower bound violations can occur in the i₁ region.

The third loop, i₃, executes those iterations of the original i loop whose values of i succeed the safe region. Again, within this loop, all array references indexed by i need to be tested. Because the subscript expressions on i are monotonically increasing across the iteration space of the i loop, only upper bound violations can occur in the i₃ region.

Within each of the resulting loops i₁, i₂, and i₃ the j loop is similarly split. For example, the body of resulting loop j_1,3 executes all iterations of the nest that attempt to reference elements of a or b that are below the corresponding lower bound, and elements of b[i], a[i], a[i + 1], and a[i - 1] that are above the corresponding upper bound. In a typical correct numerical code, where all references are in bounds, only the body of loop j_2,2 will execute. This body is represented by B(notest(i), notest(j)), and because it has no tests, it executes faster.

Computing the bounds of the split loops. To compute the bounds for the resulting i₁, i₂, and i₃ loops, we first have to compute the safe bounds for loop i: l_i^s and u_i^s. In the body of the i loop there are five array references indexed by i: b[i], a[i] (appearing twice), a[i + 1], and a[i - 1]. The values of _i^k and _i^k are shown in Figure 12A. They are computed using Equation 64 of Appendix A. The values of l_i^s and u_i^s can be computed according to Equations 34 and 35:

l_i^s = max(_i¹, _i², _i³, _i⁴, _i⁵)

u_i^s = max(l_i^s-1, min(_i¹, _i², _i³, _i⁴, _i⁵))

The bounds for the resulting j loops are computed similarly. In the body of the j loop there are five array references indexed by j: (a[i])[j + 1], (a[i])[j - 1], (a[i + 1])[j], (a[i - 1])[j], and (b[i])[j]. Note that b[i], a[i], a[i + 1], and a[i - 1] are the arrays being accessed. The values of l_j^s and u_j^s can be computed by Equations 34 and 35, using values of _j^k and _j^k obtained through Equation 64 and shown in Figure 12B. In this example, the arrays are rectangular, and the lower and upper bounds for a[i], a[i + 1], a[i - 1], and b[i] do not depend on the value of i. (Note that, in general, l_j^s and u_j^s would be functions of i.)

Figure 12

Checks that must still be done. The transformation just discussed creates regions of the loop that are free from violations on array references indexed by either i, j, or both. Figure 10 lists the specific violations that can occur in each region. Note that this particular behavior is specific to this loop. We chose to implement the loop using versions of the body that perform tests covering more than the strictly necessary violations. This allowed us to use only four versions of the loop body, as shown in Figure 10 and detailed in Figure 11. We perform an all tests test on any i reference when outside the safe region for i. Correspondingly, we perform an all tests on any j reference when outside the safe region for j.

Summary of the general method. The exact method of the previous section formed a different region of the iteration space of a loop for each possible combination of necessary array reference tests. The general method always partitions the iteration space of a loop into three regions: (1) a region for those iterations that need no test (the safe region), (2) a region for those iterations that occur prior to the safe region, and (3) a region for those iterations that occur after the safe region. In each of the nonsafe loop regions, any test that might be needed for a reference in any iteration of that region is performed in all iterations of that region. This means that some additional tests might be executed compared to the exact method. For a nest of loops, the general method can be applied to each and every loop recursively and independently. Thus, for a loop nest of depth d, 3^d loop regions are created.

When generating code for the regions, several approaches can be taken. One approach generates a different version of the loop body for each region. When applied to the example of Figure 10, this would generate only lower bound tests on arrays indexed by i in the i₁ loop and only upper bound tests in the i₃ loop. This approach leads to 3^d versions of the loop body for a loop nest of depth d. A second approach, actually used in our example of Figures 10 and 11, uses only two versions of the loop body for each loop index: one with no tests on that index and one with all tests. This leads to 2^d versions of the loop body for a loop nest of depth d. A third approach would be to generate only two versions of the loop body, independent of the number of nested loops: one with all tests on all indices and one with no tests on any index. Obviously, the version with no tests can only be used in that region where no violations in any array reference can occur.

The compact method