Request for Reviews (S): JDK-8003585 strength reduce or eliminate range checks for power-of-two sized arrays (Was: Re: A simple optimization proposal)

[Krystal Mok]

Hi Vladimir,

Thanks for catching it. Another one of the left overs. But it's interesting
that it's only missing a chance to do the transformation earlier; the
expected optimizations were still performed by C2 in a later phase even
when I got that line wrong...so I didn't notice I missed a place.

Webrev updated in place again.

The test that I used locally to verify the generated code patterns was:

import java.util.*;

public class TestArrayRangeCheck {
  private static Object foo1(Object[] a, int x) throws Exception {
    if (a.length == 0) throw new Exception();
    return a[x & (a.length - 1)];
  }

  private static Object foo2(Object[] a, int x) throws Exception {
    a[1] = a[2];
    return a[(a.length - 1) & x];
  }

  private static Object foo3(Object[] a, int x) throws Exception {
    if (a.length != 0) {
      return a[x & (a.length - 1)];
    }
    return null;
  }

  private static Object foo4(Object[] a, int x) throws Exception {
    if (a.length > 0) {
      return a[x & (a.length - 1)];
    }
    return null;
  }

  public static void main(String[] args) throws Exception {
    foo1(a, 6);
    foo1(a, 6);
    foo2(a, 6);
    foo2(a, 6);
    foo3(a, 6);
    foo3(a, 6);
    foo4(a, 6);
    foo4(a, 6);

    HashMap<String, Integer> map = new HashMap<>();
    String[] strs = new String[] {
      "alpha", "beta", "charlie", "delta", "echo", "foxtrot", "golf",
"helios"
    };

    for (String s : strs) {
      map.put(s, s.length());
    }

    for (int i = 0; i < 100; i++) {
      int index = i % strs.length;
      String key = strs[index];
      int len = map.get(key);
      if (len != key.length()) throw new Exception("unexpected
HashMap.getNode");
    }

    System.in.read();
  }
}

The "foo" methods were for manual inspection of the generated code, and the
big loop in main() was to verify HashMap.getNode() still runs correctly
after compilation.

The command to run the test was:

java -XX:CompileCommand="compileonly java/util/HashMap get*"
-XX:CompileCommand="dontinline java/util/HashMap getNode"
-XX:CompileCommand="compileonly TestArrayRangeCheck foo*"
-XX:-TieredCompilation -XX:CICompilerCount=1 -XX:CompileThreshold=6
-XX:PrintIdealGraphLevel=4 -XX:PrintIdealGraphFile=ideal_hash.xml
-XX:+PrintCompilation -XX:+PrintAssembly TestArrayRangeCheck

If that's the kind of test that you're looking for, then I can
rename/refactor the code a little bit and fit it into HotSpot's unit test.

Thanks,
Kris



On Fri, Feb 14, 2014 at 11:59 AM, Vladimir Kozlov <
vladimir.kozlov at oracle.com> wrote:

> I found a problem:
>
> 1231         Node* ncmp = r->Opcode() == Op_LoadRange
>
> should be
>
> 1231         Node* ncmp = cmp2->Opcode() == Op_LoadRange
>
> because r->Opcode() == Op_AddI
>
> Kris, can you also add a test to verify correctness of these
> transformations?
>
> Thanks,
> Vlaidmir
>
>
> On 2/14/14 11:48 AM, Vladimir Kozlov wrote:
>
>> I assigned it to Nils, he will sponsor these changes.
>> We need to do more testing than just JPRT before the push.
>>
>> Thanks,
>> Vladimir
>>
>> On 2/14/14 11:16 AM, Krystal Mok wrote:
>>
>>> Hi Vladimir,
>>>
>>> Thank you for your reviews, Vladimir.
>>>
>>> I've removed the bogus comment and updated the webrev in place:
>>> http://cr.openjdk.java.net/~kmo/8003585/webrev.02/
>>>
>>> Could someone on the compiler team run JPRT tests and push for me?
>>>
>>> Thanks,
>>> Kris
>>>
>>> On Fri, Feb 14, 2014 at 11:10 AM, Vladimir Kozlov
>>> <vladimir.kozlov at oracle.com <mailto:vladimir.kozlov at oracle.com>> wrote:
>>>
>>>     Hi Kris,
>>>
>>>     Changes are good.
>>>
>>>     Next comment does not describe the following optimization correctly:
>>>
>>>     +  // Integer expressions which perform bitwise and can be proven to
>>>     +  // be less than or equal (unsigned) to either operand, as long
>>> as the
>>>     +  // compared operand is non-negative.
>>>
>>>     originally it was for "(x & m) <= m, if and only if (m >= 0)".
>>>
>>>     Thanks,
>>>     Vladimir
>>>
>>>
>>>     On 2/13/14 7:57 PM, Krystal Mok wrote:
>>>
>>>         Hi all,
>>>
>>>         I've updated the patch again,
>>>         Webrev: http://cr.openjdk.java.net/~__kmo/8003585/webrev.02/
>>>         <http://cr.openjdk.java.net/~kmo/8003585/webrev.02/>
>>>
>>>         This version slightly differs from the original equivalence
>>>         patterns as
>>>         stated in the bug report, in that it doesn't transform the
>>>         following:
>>>             (x & array.length) < array.length
>>>         to:
>>>             array.length != 0
>>>         and instead transforms it to:
>>>             array.length u> 0
>>>         which are semantically the same.
>>>
>>>         This is done to better align with the code pattern that C2
>>>         generates for
>>>         array range checks, so that the logic in IfNode::Ideal() can
>>> better
>>>         remove redundant range checks.
>>>
>>>         Also, I've added one more pattern matching to transform:
>>>             array.length > 0
>>>         to:
>>>             array.length u> 0
>>>         (the actually code implements it inverted)
>>>         This is safe because array lengths are always >= 0, while
>>>         changing the
>>>         form makes them more likely to get optimized by IfNode::Ideal()
>>>         later.
>>>
>>>         With this patch, C2 can now elide redundant range checks in the
>>>         following two cases:
>>>
>>>         Case 1:
>>>            array[1] = array[2]; // ensures array.length > 2
>>>            Object o = array[x & (array.length - 1)];
>>>
>>>         Case 2:
>>>            if (array.length > 0) { // this is a signed comparison
>>>              Object o = array[x & (array.length - 1)];
>>>            }
>>>
>>>         I've tested the patch to compile java.util.HashMap.getNode(), and
>>>         confirmed that redundant array bounds checks are elided (matches
>>>         Case 2
>>>         above).
>>>
>>>         Thanks,
>>>         Kris
>>>
>>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/attachments/20140214/1590ce4f/attachment-0001.html