United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
Bug ID: JDK-5091921 Sign flip issues in loop optimizer
JDK-5091921 : Sign flip issues in loop optimizer

Details
Type:
Bug
Submit Date:
2004-08-25
Status:
Closed
Updated Date:
2011-05-16
Project Name:
JDK
Resolved Date:
2011-05-16
Component:
hotspot
OS:
solaris_8,linux_ubuntu,solaris_7,solaris_2.5.1,linux,generic,solaris_10,windows_xp,windows_7,windows_2000
Sub-Component:
compiler
CPU:
itanium,x86,sparc,other,generic
Priority:
P3
Resolution:
Fixed
Affected Versions:
hs20,1.4.2,5.0,6,6u6,6u10,6u12,6u14,6u16,6u18,6u21,6u23,6u26,6u28
Fixed Versions:
hs21 (b12)

Related Reports
Backport:
Backport:
Duplicate:
Duplicate:
Duplicate:
Duplicate:
Duplicate:
Duplicate:
Duplicate:
Duplicate:
Duplicate:
Duplicate:
Duplicate:
Duplicate:
Duplicate:
Duplicate:
Duplicate:
Duplicate:
Duplicate:
Duplicate:
Duplicate:
Duplicate:
Duplicate:
Duplicate:
Relates:
Relates:
Relates:
Relates:
Relates:
Relates:
Relates:
Relates:
Relates:
Relates:
Relates:

Sub Tasks

Description
Name: ks84122			Date: 08/25/2004


the tests below fail for server compiler, but pass for client compiler on the latest tiger build
/
* Test for the bug of transforming indx >= MININT to indx > MININT-1 */
/* Run with -Xcomp -XX:CompileOnly=ge1.test1 -XX:MaxInlineSize=1 */
public class ge1
{
  public static int result=1;
  public static int test1(int limit)
  {
    int indx;
    int sum = 0;
    for (indx = 500; indx >= limit; indx -= 2)
    {
      sum += 2000 / indx;
      result = sum;
    }
    return sum;
  }
  public static void main(String[] args)
  {
    int r = 0;
    try
    {
      r = test1(0x80000000);
      System.out.println(result);
      System.out.println("FAILED");
      System.exit(1);
    }
    catch (ArithmeticException e1)
    {
      System.out.println("Expected exception caught");
      if (result != 5986)
      {
        System.out.println(result);
        System.out.println("FAILED");
        System.exit(1);
      }
    }
    System.out.println("WORKED");
  }
}

====
/* Run with -Xcomp -XX:CompileOnly=wrap1.test1 -XX:MaxInlineSize=1 */
/* limit reset to ((limit-init+stride-1)/stride)*stride+init */
/* Calculation may overflow */
public class wrap1
{
  public static volatile int c = 1;
  public static int test1(int limit)
  {
    int indx;
    int sum = 0;
    for (indx = 0xffffffff; indx < limit; indx += 0x20000000)
    {
      sum += c;
    }
    return sum;
  }
  public static void main(String[] args)
  {
    int result;
    result = test1(0x7fffffff);
    if (result != 4)
    {
      System.out.println(result);
      System.out.println("FAILED");
      System.exit(1);
    }
    else
    {
      System.out.println("WORKED");
    }
  }
}
====
/* Test for range check elimination with bit flip issue for
   scale*i+offset<limit where offset is not 0 */
/* Run with -Xcomp -XX:CompileOnly=rce5.test1
 -XX:MaxInlineSize=1 */
public class rce5
{
  static int[] box = {1,2,3,4,5,6,7,8,9};
  public static int result=0;
  public static int test1(int[] b, int limit)
  {
    int indx;
    int sum = b[1];
    result = sum;
    for (indx = 0x80000000; indx < limit; ++indx)
    {
      if (indx > 0x80000000)
      {
        // this test is not issued in pre-loop but issued in main loop
        // trick rce into thinking expression is false when indx >= 0
        // in fact it is false when indx==0x80000001
        if (indx - 9 < -9)
        {
          sum += indx;
          result = sum;
          sum ^= b[indx & 7];
          result = sum;
        }
        else
          break;
      }
      else
      {
        sum += b[indx & 3];
        result = sum;
      }
    }
    return sum;
  }
  public static void main(String[] args)
  {
    int r = test1(box,0x80000100);
    if (result != 3)
    {
      System.out.println(result);
      System.exit(2);
    }
    else
    {
      System.out.println("WORKED");
    }
  }
}
====
/* Test for range check elimination with bit flip issue for
   scale*i<limit where scale > 1 */
/* Run with -Xcomp -XX:CompileOnly=rce6.test1
 -XX:MaxInlineSize=1 */
public class rce6
{
  static int[] box = {1,2,3,4,5,6,7,8,9};
  public static int result=0;
  public static int test1(int[] b, int limit)
  {
    int indx;
    int sum = b[1];
    result = sum;
    for (indx = 0x80000000; indx < limit; ++indx)
    {
      if (indx > 0x80000000)
      {
        // harmless rce target
        if (indx < 0)
        {
          sum += result;
          result = sum;
        }
        else
          break;
        // this test is not issued in pre-loop but issued in main loop
        // trick rce into thinking expression is false when indx >= 0
        // in fact it is false when indx==0x80000001
        // In compilers that transform mulI to shiftI may mask this issue.
        if (indx * 28 + 1 < 0)
        {
          sum += indx;
          result = sum;
          sum ^= b[indx & 7];
          result = sum;
        }
        else
          break;
      }
      else
      {
        sum += b[indx & 3];
        result = sum;
      }
    }
    return sum;
  }
  public static void main(String[] args)
  {
    int r = test1(box,0x80000100);
    if (result != 6)
    {
      System.out.println(result);
      System.exit(2);
    }
    else
    {
      System.out.println("WORKED");
    }
  }
}
====
/* Test for range check elimination with i <= limit */
/* Run with -Xcomp -XX:CompileOnly=rce7.test1
 -XX:MaxInlineSize=1 */
public class rce7
{
  static int[] box = {1,2,3,4,5,6,7,8,9,0x7fffffff};
  public static int result=0;
  public static int test1(int[] b)
  {
    int indx;
    int max = b[9];
    int sum = b[7];
    result = sum;
    for (indx = 0; indx < b.length; ++indx)
    {
      if (indx <= max)
      {
        sum += (indx ^ 15) + ((result != 0) ? 0 : sum);
        result = sum;
      }
      else
        throw new RuntimeException();
    }
    for (indx = -7; indx < b.length; ++indx)
    {
      if (indx <= 9)
      {
        sum += (sum ^ 15) + ((result != 0) ? 0 : sum);
        result = sum;
      }
      else
        throw new RuntimeException();
    }
    return sum;
  }
  public static void main(String[] args)
  {
    int r = test1(box);
    if (result != 14680079)
    {
      System.out.println(result);
      System.exit(2);
    }
    else
    {
      System.out.println("WORKED");
    }
  }
}
====
/* Test for range check elimination with i >= limit */
/* Run with -Xcomp -XX:CompileOnly=rce8.test1
 -XX:MaxInlineSize=1 */
public class rce8
{
  static int[] box = {-1,0,1,2,3,4,5,6,7,8,0x80000000};
  private static int result=0;
  public static int test1(int[] b)
  {
    int indx;
    int sum = b[5];
    int min = b[10];
    result = sum;
    for (indx = b.length-1; indx >= 0; --indx)
    {
      if (indx >= min)
      {
        sum += (sum ^ 9) + ((result != 0) ? 0 :sum);
        result = sum;
      }
      else
        throw new RuntimeException();
    }
    return sum;
  }
  public static void main(String[] args)
  {
    int r = test1(box);
    if (result != 16393)
    {
      System.out.println(result);
      System.exit(2);
    }
    else
    {
      System.out.println("WORKED");
    }
  }
}
====
/* Test for the bug of transforming indx <= MAXINT to indx < MAXINT+1 */
/* Run with -Xcomp -XX:CompileOnly=le1.test1 -XX:MaxInlineSize=1 */
public class le1
{
  public static int result = 0;
  public static int test1(int limit)
  {
    int indx;
    int sum = 0;
    for (indx = -500; indx <= limit; indx += 2)
    {
      sum += 3000 / indx;
      result = sum;
    }
    return sum;
  }
  public static void main(String[] args)
  {
    int r = 0;
    try
    {
      r = test1(0x7fffffff);
      System.out.println(result);
      System.out.println("FAILED");
      System.exit(1);
    }
    catch (ArithmeticException e1)
    {
      System.out.println("Expected exception caught");
      if (result != -9039)
      {
        System.out.println(result);
        System.out.println("FAILED");
        System.exit(1);
      }
    }
    System.out.println("WORKED");
  }
}
(Incident Review ID: 300690) 
======================================================================

                                    

Comments
EVALUATION

See Comments
                                     
2004-09-17
CONVERTED DATA

BugTraq+ Release Management Values

COMMIT TO FIX:
mustang


                                     
2004-09-17
EVALUATION

http://hg.openjdk.java.net/jdk7/hotspot-comp/hotspot/rev/bad7ecd0b6ed
                                     
2011-05-04
PUBLIC COMMENTS

Loop optimizer in Server VM does not take into account integer overflow when it generates code for loop limits calculation during counted loop construction, unrolling and range check elimination. As result generated code will behave incorrectly when an integer overflow happens.

1. Added limit check for Counted loops which, if failed, causes recompilation of the method without counted loop. It based on loop predication code we have already but we don't need to copy it after corresponding counted loop is created (this is why a new flag is passed to loop predicate copy methods).

if (limit > max_int-stride)
  uncommon_trap
counted_loop init, limit, stride

2. Long arithmetic is used to calculate exact limit only when it is needed: empty loop elimination and predicated range check elimination. New ideal macro node LoopLimitNode is used but corresponding mach node is created only for 32-bit x86 to get better assembler code. Sparc and x64 have long registers so generated assembler is good enough without specialized mach node. Also delay LoopLimitNode transformation until all loop optimizations are done (by marking LoopLimitNode as macro node).

3. New limit after unroll calculated as:

  new_limit = limit-stride
  new_limit = (limit < new_limit) ? MININT : new_limit;

instead of current expression:

  new_limit = init + (((limit-init)/stride)&(-2))*stride

Added other checks to avoid limit value overflow during unroll. Also fully unroll loops with up to 3 trip count.

4. Added underflow check for normal compares in loops which are optimized out using range check elimination code (I also refactored the code):

 MIN_INT <= scale*I+offset < limit

----------------------------------------------
These changes are put under flags to debug associated problems. I also allowed to print inlining decisions in product VM since PrintInlining is diagnostic flag now. New regression tests are added based on associated bug reports.

These changes cause performance regression in benchmarks. Some of regression cases can't not be avoided but some we will address in a future.

And finally I want to thank java VM team from HP who provided nice test cases and even suggested fix. I used their idea for unroll limit fix.
                                     
2011-05-04



Hardware and Software, Engineered to Work Together