changeset 27353:05d844f1a81a

8003585: strength reduce or eliminate range checks for power-of-two sized arrays Summary: change ((x & m) u<= m) to always true and ((x & (m - 1)) u< m) into (m > 0) Reviewed-by: kvn, roland
author kmo
date Tue, 19 Jan 2016 14:52:33 +0100
parents 7d123e3d170c
children 52a316ae594d
files src/share/vm/opto/addnode.cpp src/share/vm/opto/subnode.cpp test/compiler/rangechecks/PowerOf2SizedArraysChecks.java
diffstat 3 files changed, 223 insertions(+), 4 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/vm/opto/addnode.cpp	Mon Feb 01 19:45:26 2016 +0300
+++ b/src/share/vm/opto/addnode.cpp	Tue Jan 19 14:52:33 2016 +0100
@@ -61,7 +61,7 @@
 
 //------------------------------commute----------------------------------------
 // Commute operands to move loads and constants to the right.
-static bool commute( Node *add, int con_left, int con_right ) {
+static bool commute(Node *add, bool con_left, bool con_right) {
   Node *in1 = add->in(1);
   Node *in2 = add->in(2);
 
@@ -110,8 +110,8 @@
 Node *AddNode::Ideal(PhaseGVN *phase, bool can_reshape) {
   const Type *t1 = phase->type( in(1) );
   const Type *t2 = phase->type( in(2) );
-  int con_left  = t1->singleton();
-  int con_right = t2->singleton();
+  bool con_left  = t1->singleton();
+  bool con_right = t2->singleton();
 
   // Check for commutative operation desired
   if( commute(this,con_left,con_right) ) return this;
--- a/src/share/vm/opto/subnode.cpp	Mon Feb 01 19:45:26 2016 +0300
+++ b/src/share/vm/opto/subnode.cpp	Tue Jan 19 14:52:33 2016 +0100
@@ -1334,6 +1334,65 @@
     return new BoolNode( ncmp, _test.negate() );
   }
 
+  // Change ((x & m) u<= m) or ((m & x) u<= m) to always true
+  // Same with ((x & m) u< m+1) and ((m & x) u< m+1)
+  if (cop == Op_CmpU &&
+      cmp1->Opcode() == Op_AndI) {
+    Node* bound = NULL;
+    if (_test._test == BoolTest::le) {
+      bound = cmp2;
+    } else if (_test._test == BoolTest::lt &&
+               cmp2->Opcode() == Op_AddI &&
+               cmp2->in(2)->find_int_con(0) == 1) {
+      bound = cmp2->in(1);
+    }
+    if (cmp1->in(2) == bound || cmp1->in(1) == bound) {
+      return ConINode::make(1);
+    }
+  }
+
+  // Change ((x & (m - 1)) u< m) into (m > 0)
+  // This is the off-by-one variant of the above
+  if (cop == Op_CmpU &&
+      _test._test == BoolTest::lt &&
+      cmp1->Opcode() == Op_AndI) {
+    Node* l = cmp1->in(1);
+    Node* r = cmp1->in(2);
+    for (int repeat = 0; repeat < 2; repeat++) {
+      bool match = r->Opcode() == Op_AddI && r->in(2)->find_int_con(0) == -1 &&
+                   r->in(1) == cmp2;
+      if (match) {
+        // arraylength known to be non-negative, so a (arraylength != 0) is sufficient,
+        // but to be compatible with the array range check pattern, use (arraylength u> 0)
+        Node* ncmp = cmp2->Opcode() == Op_LoadRange
+                     ? phase->transform(new CmpUNode(cmp2, phase->intcon(0)))
+                     : phase->transform(new CmpINode(cmp2, phase->intcon(0)));
+        return new BoolNode(ncmp, BoolTest::gt);
+      } else {
+        // commute and try again
+        l = cmp1->in(2);
+        r = cmp1->in(1);
+      }
+    }
+  }
+
+  // Change (arraylength <= 0) or (arraylength == 0)
+  //   into (arraylength u<= 0)
+  // Also change (arraylength != 0) into (arraylength u> 0)
+  // The latter version matches the code pattern generated for
+  // array range checks, which will more likely be optimized later.
+  if (cop == Op_CmpI &&
+      cmp1->Opcode() == Op_LoadRange &&
+      cmp2->find_int_con(-1) == 0) {
+    if (_test._test == BoolTest::le || _test._test == BoolTest::eq) {
+      Node* ncmp = phase->transform(new CmpUNode(cmp1, cmp2));
+      return new BoolNode(ncmp, BoolTest::le);
+    } else if (_test._test == BoolTest::ne) {
+      Node* ncmp = phase->transform(new CmpUNode(cmp1, cmp2));
+      return new BoolNode(ncmp, BoolTest::gt);
+    }
+  }
+
   // Change "bool eq/ne (cmp (Conv2B X) 0)" into "bool eq/ne (cmp X 0)".
   // This is a standard idiom for branching on a boolean value.
   Node *c2b = cmp1;
@@ -1496,4 +1555,3 @@
   double d = t1->getd();
   return TypeD::make( StubRoutines::intrinsic_log10( d ) );
 }
-
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/compiler/rangechecks/PowerOf2SizedArraysChecks.java	Tue Jan 19 14:52:33 2016 +0100
@@ -0,0 +1,161 @@
+/*
+ * Copyright (c) 2015, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ *
+ */
+
+/**
+ * @test
+ * @bug 8003585
+ * @summary strength reduce or eliminate range checks for power-of-two sized arrays
+ * @run main/othervm -XX:CompileCommand=compileonly,PowerOf2SizedArraysChecks::test* -XX:-BackgroundCompilation PowerOf2SizedArraysChecks
+ *
+ */
+
+import java.util.function.*;
+
+public class PowerOf2SizedArraysChecks {
+
+    static void check_result(String name, int x, int m, boolean expected, boolean res) {
+        if (expected != res) {
+            throw new RuntimeException("Bad result in " + name + " for x =  " + x + " m = " + m + " expected " + expected  + " got " + res);
+        }
+    }
+
+    static void helper(String name, BiFunction<Integer, int[], Boolean> test, int[] x_values, int[] m_values, boolean[][] expected) {
+        for (int i = 0; i < x_values.length; i++) {
+            int x = x_values[i];
+            for (int j = 0; j < m_values.length; j++) {
+                int m = m_values[j];
+                int[] array = new int[m];
+                boolean res = test.apply(x, array);
+                check_result(name, x, m, expected[i][j], res);
+            }
+        }
+    }
+
+    static void check_result(String name, int m, boolean expected, boolean res) {
+        if (expected != res) {
+            throw new RuntimeException("Bad result in " + name + " for m = " + m + " expected " + expected  + " got " + res);
+        }
+    }
+
+    static void helper2(String name, Function<int[], Boolean> test, int[] m_values, boolean[] expected) {
+        for (int j = 0; j < m_values.length; j++) {
+            int m = m_values[j];
+            int[] array = new int[m];
+            boolean res = test.apply(array);
+            check_result(name, m, expected[j], res);
+        }
+    }
+
+    // ((x & m) u<= m) is always true
+    static boolean test1(int x, int[] array) {
+        int m = array.length;
+        if ((x & m) < 0 || (x & m) > m) {
+            return false;
+        }
+        return true;
+    }
+
+    // ((x & (m - 1)) u< m) iff (m > 0)
+    static boolean test2(int x, int[] array) {
+        int m = array.length;
+        if ((x & (m-1)) < 0 || (x & (m-1)) >= m) {
+            return false;
+        }
+        return true;
+    }
+
+    static boolean test3(int x, int[] array) {
+        try {
+            int v = array[x & (array.length-1)];
+        } catch(ArrayIndexOutOfBoundsException aioobe) {
+            return false;
+        }
+        return true;
+    }
+
+    // arraylength <= 0 to arraylength u<= 0
+    static boolean test4(int[] array) {
+        if (array.length <= 0) {
+            return false;
+        }
+        return true;
+    }
+
+    // arraylength == 0 to arraylength u<= 0
+    static boolean test5(int[] array) {
+        if (array.length == 0) {
+            return false;
+        }
+        return true;
+    }
+
+    // arraylength != 0 to arraylength u> 0
+    static boolean test6(int[] array) {
+        if (array.length != 0) {
+            return false;
+        }
+        return true;
+    }
+
+    static public void main(String[] args) {
+        int[] x_values = {-10, -5, 0, 5, 8, 16, 100};
+        int[] m_values = { 16, 10, 0 };
+
+        boolean[][] test1_expected = new boolean[x_values.length][m_values.length];
+        for (int i = 0; i < x_values.length; i++) {
+            for (int j = 0; j < m_values.length; j++) {
+                test1_expected[i][j] = true;
+            }
+        }
+
+        boolean[][] test2_expected = new boolean[x_values.length][m_values.length];
+        for (int i = 0; i < x_values.length; i++) {
+            for (int j = 0; j < m_values.length; j++) {
+                test2_expected[i][j] = (m_values[j] > 0);
+            }
+        }
+
+        boolean[] test4_expected = new boolean[m_values.length];
+        for (int i = 0; i < m_values.length; i++) {
+            test4_expected[i] = (m_values[i] > 0);
+        }
+        boolean[] test5_expected = new boolean[m_values.length];
+        for (int i = 0; i < m_values.length; i++) {
+            test5_expected[i] = (m_values[i] != 0);
+        }
+        boolean[] test6_expected = new boolean[m_values.length];
+        for (int i = 0; i < m_values.length; i++) {
+            test6_expected[i] = (m_values[i] == 0);
+        }
+
+        for (int i = 0; i < 20000; i++) {
+            helper("test1", PowerOf2SizedArraysChecks::test1, x_values, m_values, test1_expected);
+            helper("test2", PowerOf2SizedArraysChecks::test2, x_values, m_values, test2_expected);
+            helper("test3", PowerOf2SizedArraysChecks::test3, x_values, m_values, test2_expected);
+            helper2("test4", PowerOf2SizedArraysChecks::test4, m_values, test4_expected);
+            helper2("test5", PowerOf2SizedArraysChecks::test5, m_values, test5_expected);
+            helper2("test6", PowerOf2SizedArraysChecks::test6, m_values, test6_expected);
+        }
+    }
+}