Browse Prior Art Database

A method for eliminating array bounds checks by using loop unrolling

IP.com Disclosure Number: IPCOM000022650D
Original Publication Date: 2004-Mar-23
Included in the Prior Art Database: 2004-Mar-23
Document File: 2 page(s) / 9K

Publishing Venue

IBM

Abstract

Disclosed is a method for eliminating array bounds checks by using a loop unrolling technique. Previous loop unrolling techniques did not optimize array bounds checks in a loop whose iteration count is not loop invariant. This disclosure attempts to optimize array bounds checks in such loops.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 68% of the total text.

Page 1 of 2

A method for eliminating array bounds checks by using loop unrolling

At first, loop unrolling is applied to loops whose iteration count is not loop invariant. Next, we make a guard code to split the original loop and the unrolled loop body. This guard code checks whether unrolled loop body is safe or not. We use an example in Figure 1 to explain this disclosure.

i = 0; do {

BOUNDCHECK i, a[]; // Previous techniques cannot optimize this check.

if (a[i] == 0) break;

i++; } while(true); Figure 1. Sample program

Previous techniques still leave the array bound check of a[i] in Figure 1. This is because the exit condition of the loop depends only on the array's value. This disclosure transforms Figure 1 to Figure 2.

i = 0; do {

if (i+4 <= a.length){ -- (1) // Guard code if (a[i] == 0) break; // Safe path
i++;
if (a[i] == 0) break;
i++;
if (a[i] == 0) break;
i++;
if (a[i] == 0) break;
i++;

} else {

do {

BOUNDCHECK i, a[]; // Unsafe path

if (a[i] == 0) goto exit_outerloop;

i++;

} while(true);

}

} while(true);

exit_outerloop:

Figure 2. Optimization result of Figure 1 (Unroll factor is 4)

By this transformation, we can reduce execution count of array bounds checks, because the guard code (1) is often satisfied. Figures 3 and 4 show one more example.

int example2(int a[])

{

int i = 0, result;

while(true){

result = method(i);

if (result == 0) break;

BOUNDCHECK i, a[]; // Previous techniques cannot optimize this check.

a[i] = result;

i++;

}

return i;

}

1

Page 2 of 2

Figure 3. Sample...