JDK-5091921 : Sign flip issues in loop optimizer
  • Type: Bug
  • Component: hotspot
  • Sub-Component: compiler
  • Affected Version:
    hs20,1.4.2,5.0,6,6u6,6u10,6u12,6u14,6u16,6u18,6u21,6u23,6u26,6u28 hs20,1.4.2,5.0,6,6u6,6u10,6u12,6u14,6u16,6u18,6u21,6u23,6u26,6u28
  • Priority: P3
  • Status: Closed
  • Resolution: Fixed
  • OS:
    generic,linux,linux_ubuntu,solaris_2.5.1,solaris_7,solaris_8,solaris_10,windows_2000,windows_xp,windows_7 generic,linux,linux_ubuntu,solaris_2.5.1,solaris_7,solaris_8,solaris_10,windows_2000,windows_xp,windows_7
  • CPU: generic,other,x86,sparc,itanium
  • Submitted: 2004-08-25
  • Updated: 2016-03-29
  • Resolved: 2011-05-16
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
JDK 7 Other
7Fixed hs21Fixed
Related Reports
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 :  
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
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.
04-05-2011

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

CONVERTED DATA BugTraq+ Release Management Values COMMIT TO FIX: mustang
17-09-2004

EVALUATION See Comments
17-09-2004