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.

        Attachments

          Issue Links

            Activity

              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: