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

strength reduce or eliminate range checks for power-of-two sized arrays

    Details

    • Type: Enhancement
    • Status: Resolved
    • Priority: P4
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 9
    • Component/s: hotspot
    • Subcomponent:
    • Resolved In Build:
      b106

      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.

        Issue Links

          Activity

          Hide
          kvn Vladimir Kozlov added a comment -
          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!
          Show
          kvn Vladimir Kozlov added a comment - 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!
          Hide
          kvn Vladimir Kozlov added a comment -
          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)
          Show
          kvn Vladimir Kozlov added a comment - 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)
          Hide
          kmo Krystal Mo added a comment -
          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).
          Show
          kmo Krystal Mo added a comment - 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).
          Hide
          psandoz Paul Sandoz added a comment -
          Update patch so that it compiles (was affected by changes for JDK-8034812: remove IDX_INIT macro hack in Node classthat)
          Show
          psandoz Paul Sandoz added a comment - Update patch so that it compiles (was affected by changes for JDK-8034812 : remove IDX_INIT macro hack in Node classthat)
          Hide
          jrose John Rose added a comment -
          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
          Show
          jrose John Rose added a comment - 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
          Hide
          hgupdate HG Updates added a comment -
          URL: http://hg.openjdk.java.net/jdk9/hs-comp/hotspot/rev/05d844f1a81a
          User: roland
          Date: 2016-02-02 15:10:02 +0000
          Show
          hgupdate HG Updates added a comment - URL: http://hg.openjdk.java.net/jdk9/hs-comp/hotspot/rev/05d844f1a81a User: roland Date: 2016-02-02 15:10:02 +0000
          Hide
          hgupdate HG Updates added a comment -
          URL: http://hg.openjdk.java.net/jdk9/jdk9/hotspot/rev/05d844f1a81a
          User: lana
          Date: 2016-02-17 20:42:36 +0000
          Show
          hgupdate HG Updates added a comment - URL: http://hg.openjdk.java.net/jdk9/jdk9/hotspot/rev/05d844f1a81a User: lana Date: 2016-02-17 20:42:36 +0000

            People

            • Assignee:
              roland Roland Westrelin
              Reporter:
              jrose John Rose
            • Votes:
              0 Vote for this issue
              Watchers:
              10 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: