JDK-8003585 : strength reduce or eliminate range checks for power-of-two sized arrays
  • Type: Enhancement
  • Component: hotspot
  • Sub-Component: compiler
  • Priority: P4
  • Status: Resolved
  • Resolution: Fixed
  • Submitted: 2012-11-17
  • Updated: 2016-02-18
  • Resolved: 2016-02-02
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 9
9 b106Fixed
Related Reports
Blocks :  
Relates :  
Relates :  
Description
Integer expressions which perform bitwise and can be proven to be less than or equal to either operand, as long as the compared operand is non-negative.  In other words:
  (x & m) <= m, if and only if (m >= 0)

This means the left-hand test can be replaced by the simpler right-hand test.

There are also off-by-one versions, such as:
  (x & (m-1)) < m, if and only if (m > 0)

There are also unsigned versions:
  (x & m) u<= m, always
  (x & (m-1)) u< m, if and only if (m > 0)

The optimizer should recognize these patterns.  They are common in implicitly generated range checks for power-of-two sized arrays:

  int hash = ...;
  int bucket = hash & (array.length-1);
  Entry e = array[bucket];

The range check is:
  (hash & (array.length-1)) u< array.length

This check can be strength reduced to:
  array.length != 0

If the array is constant, or if user code has a dominating check for an empty array, this check will go away completely.
Comments
Here's a user reporting on a use case for this optimization: http://psy-lob-saw.blogspot.se/2014/11/the-mythical-modulo-mask.html
03-12-2014

Update patch so that it compiles (was affected by changes for JDK-8034812: remove IDX_INIT macro hack in Node classthat)
08-07-2014

Thanks for bringing the info here, Vladimir. I'd like to mention that the last two patterns were done so that the transformed comparison will match the pattern of array range checks generated by C2. This way, IfNode()::Ideal() gets a better chance of coalescing consecutive array range checks into a single strong check, effectively removing redundant range checks. IfNode()::Ideal() only recognizes the patterns of (x u< arraylength) and (arraylength u<= x).
14-02-2014

Not all optimizations in Description are valid. These changes do only next: Change ((x & m) u<= m) or ((m & x) u<= m) to always true Change ((x & (m - 1)) u< m) into (m > 0) Change ((x & (arraylength - 1)) u< m) into (arraylength u> 0) Change (arraylength <= 0) or (arraylength == 0) into (arraylength u<= 0) Change (arraylength != 0) into (arraylength u> 0)
14-02-2014

Nils, please, do all testing for these changes. And push it if everything is good. http://cr.openjdk.java.net/~kmo/8003585/webrev.02/ Thanks!
14-02-2014