Uploaded image for project: 'Harmony'
  1. Harmony
  2. HARMONY-2147

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

    XMLWordPrintableJSON

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: None
    • Component/s: DRLVM
    • Labels:
      None
    • Environment:
      Any

      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

        Attachments

        1. LowBoundCheck.java
          0.5 kB
          Elena Sayapina
        2. abcdTest1.java
          0.6 kB
          Elena Sayapina

          Activity

            People

            • Assignee:
              Unassigned
              Reporter:
              evs Elena Sayapina
            • Votes:
              0 Vote for this issue
              Watchers:
              0 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: