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

[Vladimir Kozlov]

Changes are fine now.

I am mostly concern about correctness of optimization and not that range 
check is folded. But any test is good so, please, add it.
For foo*() method you can also compare returned value with value from 
array's element it should read.

Thanks,
Vladimir

On 2/14/14 2:47 PM, Krystal Mok wrote:
> 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 <mailto: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/
>             <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>
>             <mailto: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/>
>
>             <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
>
>