[HARMONY-2147] [drlvm][jit][opt] ABCD pass incorrectly removes low bound check in some cases

• Type: Bug
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Component/s: DRLVM
• Environment: Any
• Assignee: Unassigned
• Reporter: Elena Sayapina
• Created: 10/Nov/06 13:30
• Updated: 26/Apr/09 19:16
• Resolved: 06/Jun/07 08:05

Description

ABCD pass incorrectly removes low bound check in some cases.

Consider a loop where the value of the loop control variable and the index of array element called inside the loop depend on each other. As the result of this dependency an array element called with negative index on some iteration.

Quotation from J2SE API Spec:
"public class ArrayIndexOutOfBoundsException extends IndexOutOfBoundsException
Thrown to indicate that an array has been accessed with an illegal index. The
index is either negative or greater than or equal to the size of the array."

But redundant array bounds check elimination (abcd pass) erroneously removes low bound check and ArrayIndexOutOfBoundsException isn't thrown.

Please, see code example below

Code for reproducing:

public class abcdTest1 {

private final int limit = 1000;

public static void main(String[] args)

{ System.exit(new abcdTest1().test()); }

public int test() {
System.out.println("Start abcdTest1 ...");
int arr[] = new int[limit];
try {
for(int k=1; k<limit; )

{ System.out.println("k=" + k + ": arr[" + (k-1) + "] will be called"); k=arr[k-1]; }

} catch (ArrayIndexOutOfBoundsException e)

{ System.out.println("TEST PASSED: ArrayIndexOutOfBoundsException was thrown"); return 0; }

System.out.println("TEST FAILED: ArrayIndexOutOfBoundsException wasn't thrown");
return 1;
}

}

Steps to Reproduce:
Compile abcdTest1 class and run it on Harmony with '-Xem:server_static' option.

Output on Windows:

Apache Harmony Launcher : (c) Copyright 1991, 2006 The Apache Software Foundation or its licensors,
as applicable.
java version "1.5.0"
pre-alpha : not complete or compatible
svn = r473012, (Nov 10 2006), Windows/ia32/msvc 1310, release build
http://incubator.apache.org/harmony
Start abcdTest1 ...
k=1: arr[0] will be called
k=0: arr[-1] will be called
TEST FAILED: ArrayIndexOutOfBoundsException wasn't thrown

Output on Linux:

Apache Harmony Launcher : (c) Copyright 1991, 2006 The Apache Software Foundation or its licensors, as applicable.
java version "1.5.0"
pre-alpha : not complete or compatible
svn = r473012, (Nov 10 2006), Linux/ia32/icc 900, release build
http://incubator.apache.org/harmony
Start abcdTest1 ...
k=1: arr[0] will be called
k=0: arr[-1] will be called
TEST FAILED: ArrayIndexOutOfBoundsException wasn't thrown

Output on RI:
Start abcdTest1 ...
k=1: arr[0] will be called
k=0: arr[-1] will be called
TEST PASSED: ArrayIndexOutOfBoundsException was thrown

Another simpler test case for this bug is:

public class LowBoundCheck {

static int num = 0;

public static void main(String[] args) {
System.out.println("Start LowBoundCheck Test ...");
try {
int[] arr = new int[5];
int limit = arr.length-1;
for (int j=limit; j > 0; j--)

{ System.out.println("Call arr[" + (j-3) + "]"); num = arr[j-3]; }

System.out.println("TEST FAILED: ArrayIndexOutOfBoundsException wasn't thrown");
} catch (ArrayIndexOutOfBoundsException ae)

{ System.out.println("TEST PASSED"); }

}
}

There is no dependence between the value of the loop control variable and the array element index.

Steps to Reproduce:
Compile LowBoundCheck class and run it on Harmony with '-Xem:server_static' option.

Output on Windows:

Apache Harmony Launcher : (c) Copyright 1991, 2006 The Apache Software Foundation or its licensors,
as applicable.
java version "1.5.0"
pre-alpha : not complete or compatible
svn = r473012, (Nov 10 2006), Windows/ia32/msvc 1310, release build
http://incubator.apache.org/harmony
Start LowBoundCheck Test ...
Call arr[1]
Call arr[0]
Call arr[-1]
Call arr[-2]
TEST FAILED: ArrayIndexOutOfBoundsException wasn't thrown

Output on Linux:

Apache Harmony Launcher : (c) Copyright 1991, 2006 The Apache Software Foundation or its licensors, as applicable.
java version "1.5.0"
pre-alpha : not complete or compatible
svn = r473012, (Nov 10 2006), Linux/ia32/icc 900, release build
http://incubator.apache.org/harmony
Start LowBoundCheck Test ...
Call arr[1]
Call arr[0]
Call arr[-1]
Call arr[-2]
TEST FAILED: ArrayIndexOutOfBoundsException wasn't thrown

Output on RI:
Start LowBoundCheck Test ...
Call arr[1]
Call arr[0]
Call arr[-1]
TEST PASSED