JDK-5073662 : Range check elimination interferes with regular loop unrolling
  • Type: Enhancement
  • Component: hotspot
  • Sub-Component: compiler
  • Affected Version: 6,9,10
  • Priority: P3
  • Status: Closed
  • Resolution: Not an Issue
  • OS: generic
  • CPU: sparc
  • Submitted: 2004-07-14
  • Updated: 2020-06-30
  • Resolved: 2020-06-30
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.
Other
tbdResolved
Description
Name: ks84122			Date: 07/13/2004


public class loopissue
{
  static volatile int[] v = null;

  public static int checkme(int[] box)
  {
    int sum = 0;
    int i;
    for (i = 0; i < 225; i += 5)
    {
      sum += box[i];
      sum ^= box[i + 1];
      sum += box[i + 2];
      sum ^= box[i + 3];
      sum += box[i + 4];
    }
    return sum;
  }
  public static void main(String[] args)
  {
    int s = 0;
    for (int i = 0; i < 10000; ++i)
    {
      v = new int[256];
      s += checkme(v);
    }
    System.out.println(s);
  }
}

/opt/jdk1.4.2/bin/java_g -server -XX:+PrintOptoAssembly -XX:+PrintCompilation loopissue

You see the integer divisions and multiplications being generated
in each trip!

094     SETX   #1717986919,R_G5 ! long
09c +   SRA    R_L1,0,R_G1      ! int->long
0a0 +   MULX   R_G1,R_G5,R_G1   ! long
0a4 +   SRA    R_L1,#31,R_L0
0a8     SRAX   R_G1,#33,R_L2
0ac +   SUB    R_L2,R_L0,R_L0
0b0 +   SLL    R_L0,#2,R_L2
0b4 +   ADD    R_L2,R_L0,R_L0
0b8 +   SRA    R_L0,0,R_G1      ! int->long
0bc +   MULX   R_G1,R_G5,R_G1   ! long
0c0 +   SRA    R_L0,#31,R_L1
0c4     SRAX   R_G1,#33,R_L0
0c8 +   SUB    R_L0,R_L1,R_L1
0cc +   AND    R_L1,#-2,R_L0
0d0 +   SLL    R_L0,#2,R_L2

I comment on a bad interaction between range check elimination
and regular loop unrolling.  In the case when the loop starting value
and the ending value are both constants, when the pre-loop is created
by range check elimination, the main loop initial value changes from
a constant to "phi + stride".  Thus the loop trip count is no longer
a constant.  When regular unrolling modifies the main loop ending
limit, the new limit is created:

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

(the purpose is to remove the last odd trip from happening)

This optimizes to constant if 'limit', 'init', and 'stride' are all
constant.  But in this case 'init' is no longer constant.  It ends up
doing a division and multiply every trip!
(Incident Review ID: 280099) 
======================================================================

Comments
Range check is not Sparc specific code which could affect generated code for other platforms. But we use Loop Predicates now and as result the code is good. Tested with JDK 15 on linux-x64: $ java -XX:-TieredCompilation -Xbatch -XX:CICompilerCount=1 -XX:+PrintOptoAssembly -XX:+PrintCompilation loopissue 070 B7: # out( B7 B8 ) <- in( B6 B7 ) Loop( B7-B7 inner main of N52) Freq: 45.7752 070 addl RAX, [R9 + #16 + R10 << #2] # int 075 xorl RAX, [R9 + #20 + R10 << #2] # int 07a addl RAX, [R9 + #24 + R10 << #2] # int 07f xorl RAX, [R9 + #28 + R10 << #2] # int 084 addl RAX, [R9 + #32 + R10 << #2] # int 089 addl RAX, [R9 + #36 + R10 << #2] # int 08e xorl RAX, [R9 + #40 + R10 << #2] # int 093 addl RAX, [R9 + #44 + R10 << #2] # int 098 xorl RAX, [R9 + #48 + R10 << #2] # int 09d addl RAX, [R9 + #52 + R10 << #2] # int 0a2 addl RAX, [R9 + #56 + R10 << #2] # int 0a7 xorl RAX, [R9 + #60 + R10 << #2] # int 0ac addl RAX, [R9 + #64 + R10 << #2] # int 0b1 xorl RAX, [R9 + #68 + R10 << #2] # int 0b6 addl RAX, [R9 + #72 + R10 << #2] # int 0bb addl RAX, [R9 + #76 + R10 << #2] # int 0c0 xorl RAX, [R9 + #80 + R10 << #2] # int 0c5 addl RAX, [R9 + #84 + R10 << #2] # int 0ca xorl RAX, [R9 + #88 + R10 << #2] # int 0cf addl RAX, [R9 + #92 + R10 << #2] # int 0d4 addl RAX, [R9 + #96 + R10 << #2] # int 0d9 xorl RAX, [R9 + #100 + R10 << #2] # int 0de addl RAX, [R9 + #104 + R10 << #2] # int 0e3 xorl RAX, [R9 + #108 + R10 << #2] # int 0e8 addl RAX, [R9 + #112 + R10 << #2] # int 0ed addl RAX, [R9 + #116 + R10 << #2] # int 0f2 xorl RAX, [R9 + #120 + R10 << #2] # int 0f7 addl RAX, [R9 + #124 + R10 << #2] # int 0fc xorl RAX, [R9 + #128 + R10 << #2] # int 104 addl RAX, [R9 + #132 + R10 << #2] # int 10c addl RAX, [R9 + #136 + R10 << #2] # int 114 xorl RAX, [R9 + #140 + R10 << #2] # int 11c addl RAX, [R9 + #144 + R10 << #2] # int 124 xorl RAX, [R9 + #148 + R10 << #2] # int 12c addl RAX, [R9 + #152 + R10 << #2] # int 134 addl RAX, [R9 + #156 + R10 << #2] # int 13c xorl RAX, [R9 + #160 + R10 << #2] # int 144 addl RAX, [R9 + #164 + R10 << #2] # int 14c xorl RAX, [R9 + #168 + R10 << #2] # int 154 addl RAX, [R9 + #172 + R10 << #2] # int 15c addl R10, #40 # int 160 cmpl R10, #190 167 jl B7 # loop end P=0.978154 C=6582.000000
30-06-2020

CONVERTED DATA BugTraq+ Release Management Values COMMIT TO FIX: mustang
16-07-2004

EVALUATION ###@###.### 2004-07-14 There is no time to fix it in Tiger. We work on it in the next release.
14-07-2004