Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-5091921

Sign flip issues in loop optimizer

    Details

    • Type: Bug
    • Status: Closed
    • Priority: P3
    • Resolution: Fixed
    • Affects Version/s: hs20, 1.4.2, 5.0, 6, 6u6, 6u10, 6u12, 6u14, 6u16, 6u18, 6u21, 6u23, 6u26, 6u28
    • Fix Version/s: hs21
    • Component/s: hotspot
    • Labels:
    • Subcomponent:
    • Resolved In Build:
      b12
    • CPU:
      generic, other, x86, sparc, itanium
    • OS:
      generic, linux, linux_ubuntu, solaris_2.5.1, solaris_7, solaris_8, solaris_10, windows_2000, windows_xp, windows_7
    • Verification:
      Verified

      Backports

        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)
        ======================================================================

          Issue Links

            Activity

            Hide
            defectconv Defect Conversion BT2 (Inactive) added a comment -
            BT2:EVALUATION

            See Comments
            Show
            defectconv Defect Conversion BT2 (Inactive) added a comment - BT2:EVALUATION See Comments
            Hide
            defectconv Defect Conversion BT2 (Inactive) added a comment -
            BT2:CONVERTED DATA

            BugTraq+ Release Management Values

            COMMIT TO FIX:
            mustang

            Show
            defectconv Defect Conversion BT2 (Inactive) added a comment - BT2:CONVERTED DATA BugTraq+ Release Management Values COMMIT TO FIX: mustang
            Show
            jprtbugupd JPRT Bug Updates (Inactive) added a comment - BT2:EVALUATION http://hg.openjdk.java.net/jdk7/hotspot-comp/hotspot/rev/bad7ecd0b6ed
            Hide
            kvn Vladimir Kozlov added a comment -
            BT2: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.
            Show
            kvn Vladimir Kozlov added a comment - BT2: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.

              People

              • Assignee:
                kvn Vladimir Kozlov
                Reporter:
                ksoshals Kirill Soshalskiy (Inactive)
              • Votes:
                0 Vote for this issue
                Watchers:
                5 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved:
                  Imported:
                  Indexed: