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

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

XMLWordPrintable

    • b106

      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.

            roland Roland Westrelin
            jrose John Rose
            Votes:
            0 Vote for this issue
            Watchers:
            11 Start watching this issue

              Created:
              Updated:
              Resolved: