# HG changeset patch
# User Lukas Stadler <lukas.stadler@oracle.com>
# Date 1395321235 -3600
# Node ID ba4b79da635134bc2b5fb2af1dac84ce7baac1d3
# Parent  6fd5f25b546c35cf51f46b068ab9ec4e24d98c2f
canonicalize certain shift-compare expressions

diff -r 6fd5f25b546c -r ba4b79da6351 graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/IntegerEqualsCanonicalizerTest.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/IntegerEqualsCanonicalizerTest.java	Thu Mar 20 14:13:55 2014 +0100
@@ -0,0 +1,123 @@
+/*
+ * Copyright (c) 2011, 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.
+ */
+package com.oracle.graal.compiler.test;
+
+import org.junit.*;
+
+import com.oracle.graal.nodes.*;
+import com.oracle.graal.phases.common.*;
+import com.oracle.graal.phases.tiers.*;
+
+public class IntegerEqualsCanonicalizerTest extends GraalCompilerTest {
+
+    @Test
+    public void testShiftEquals() {
+        /*
+         * tests the canonicalization of (x >>> const) == 0 to x |test| (-1 << const)
+         */
+        test("testShiftEqualsSnippet", "testShiftEqualsReference");
+    }
+
+    @SuppressWarnings("unused") private static int field;
+
+    public static void testShiftEqualsSnippet(int x, int[] array, int y) {
+        // optimize
+        field = (x >>> 10) == 0 ? 1 : 0;
+        field = (array.length >> 10) == 0 ? 1 : 0;
+        field = (x << 10) == 0 ? 1 : 0;
+        // don't optimize
+        field = (x >> 10) == 0 ? 1 : 0;
+        field = (x >>> y) == 0 ? 1 : 0;
+        field = (x >> y) == 0 ? 1 : 0;
+        field = (x << y) == 0 ? 1 : 0;
+        field = (x >>> y) == 1 ? 1 : 0;
+        field = (x >> y) == 1 ? 1 : 0;
+        field = (x << y) == 1 ? 1 : 0;
+    }
+
+    public static void testShiftEqualsReference(int x, int[] array, int y) {
+        field = (x & 0xfffffc00) == 0 ? 1 : 0;
+        field = (array.length & 0xfffffc00) == 0 ? 1 : 0;
+        field = (x & 0x3fffff) == 0 ? 1 : 0;
+        // don't optimize signed right shifts
+        field = (x >> 10) == 0 ? 1 : 0;
+        // don't optimize no-constant shift amounts
+        field = (x >>> y) == 0 ? 1 : 0;
+        field = (x >> y) == 0 ? 1 : 0;
+        field = (x << y) == 0 ? 1 : 0;
+        // don't optimize non-zero comparisons
+        field = (x >>> y) == 1 ? 1 : 0;
+        field = (x >> y) == 1 ? 1 : 0;
+        field = (x << y) == 1 ? 1 : 0;
+    }
+
+    @Test
+    public void testCompare() {
+        test("testCompareSnippet", "testCompareReference");
+    }
+
+    public static void testCompareSnippet(int x, int y, int[] array1, int[] array2) {
+        int tempX = x;
+        int array1Length = array1.length;
+        int array2Length = array2.length;
+        // optimize
+        field = x == tempX ? 1 : 0;
+        field = x != tempX ? 1 : 0;
+        field = array1Length != (-1 - array2Length) ? 1 : 0;
+        field = array1Length == (-1 - array2Length) ? 1 : 0;
+        // don't optimize
+        field = x == y ? 1 : 0;
+        field = array1Length == array2Length ? 1 : 0;
+        field = array1Length == (-array2Length) ? 1 : 0;
+    }
+
+    public static void testCompareReference(int x, int y, int[] array1, int[] array2) {
+        int array1Length = array1.length;
+        int array2Length = array2.length;
+        // optimize
+        field = 1;
+        field = 0;
+        field = 1;
+        field = 0;
+        // don't optimize (overlapping value ranges)
+        field = x == y ? 1 : 0;
+        field = array1Length == array2Length ? 1 : 0;
+        field = array1Length == (-array2Length) ? 1 : 0;
+    }
+
+    private void test(String snippet, String referenceSnippet) {
+        StructuredGraph graph = getCanonicalizedGraph(snippet);
+        StructuredGraph referenceGraph = getCanonicalizedGraph(referenceSnippet);
+        assertEquals(referenceGraph, graph);
+    }
+
+    private StructuredGraph getCanonicalizedGraph(String snippet) {
+        StructuredGraph graph = parse(snippet);
+        new CanonicalizerPhase(false).apply(graph, new PhaseContext(getProviders(), null));
+        for (FrameState state : graph.getNodes(FrameState.class).snapshot()) {
+            state.replaceAtUsages(null);
+            state.safeDelete();
+        }
+        return graph;
+    }
+}
diff -r 6fd5f25b546c -r ba4b79da6351 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerEqualsNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerEqualsNode.java	Fri Mar 21 10:45:16 2014 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerEqualsNode.java	Thu Mar 20 14:13:55 2014 +0100
@@ -26,6 +26,8 @@
 import com.oracle.graal.graph.*;
 import com.oracle.graal.graph.spi.*;
 import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.type.*;
+import com.oracle.graal.nodes.util.*;
 
 @NodeInfo(shortName = "==")
 public final class IntegerEqualsNode extends CompareNode {
@@ -69,17 +71,67 @@
 
     @Override
     public Node canonical(CanonicalizerTool tool) {
-        if (x() == y()) {
+        if (GraphUtil.unproxify(x()) == GraphUtil.unproxify(y())) {
             return LogicConstantNode.tautology(graph());
         } else if (x().stamp().alwaysDistinct(y().stamp())) {
             return LogicConstantNode.contradiction(graph());
         }
 
-        if (x() instanceof AndNode && y().isConstant() && y().asConstant().asLong() == 0) {
-            return graph().unique(new IntegerTestNode(((AndNode) x()).x(), ((AndNode) x()).y()));
-        } else if (y() instanceof AndNode && x().isConstant() && x().asConstant().asLong() == 0) {
-            return graph().unique(new IntegerTestNode(((AndNode) y()).x(), ((AndNode) y()).y()));
+        ValueNode result = canonicalizeSymmetric(x(), y());
+        if (result != null) {
+            return result;
         }
+
+        result = canonicalizeSymmetric(y(), x());
+        if (result != null) {
+            return result;
+        }
+
         return super.canonical(tool);
     }
+
+    private ValueNode canonicalizeSymmetric(ValueNode x, ValueNode y) {
+        if (y.isConstant() && y.asConstant().asLong() == 0) {
+            if (x instanceof AndNode) {
+                return graph().unique(new IntegerTestNode(((AndNode) x).x(), ((AndNode) x).y()));
+            } else if (x instanceof LeftShiftNode) {
+                LeftShiftNode shift = (LeftShiftNode) x;
+                if (shift.y().isConstant()) {
+                    int mask = shift.getShiftAmountMask();
+                    int amount = shift.y().asConstant().asInt() & mask;
+                    if (shift.x().getKind() == Kind.Int) {
+                        return graph().unique(new IntegerTestNode(shift.x(), ConstantNode.forInt(-1 >>> amount, graph())));
+                    } else {
+                        assert shift.x().getKind() == Kind.Long;
+                        return graph().unique(new IntegerTestNode(shift.x(), ConstantNode.forLong(-1L >>> amount, graph())));
+                    }
+                }
+            } else if (x instanceof RightShiftNode) {
+                RightShiftNode shift = (RightShiftNode) x;
+                if (shift.y().isConstant() && ((IntegerStamp) shift.x().stamp()).isPositive()) {
+                    int mask = shift.getShiftAmountMask();
+                    int amount = shift.y().asConstant().asInt() & mask;
+                    if (shift.x().getKind() == Kind.Int) {
+                        return graph().unique(new IntegerTestNode(shift.x(), ConstantNode.forInt(-1 << amount, graph())));
+                    } else {
+                        assert shift.x().getKind() == Kind.Long;
+                        return graph().unique(new IntegerTestNode(shift.x(), ConstantNode.forLong(-1L << amount, graph())));
+                    }
+                }
+            } else if (x instanceof UnsignedRightShiftNode) {
+                UnsignedRightShiftNode shift = (UnsignedRightShiftNode) x;
+                if (shift.y().isConstant()) {
+                    int mask = shift.getShiftAmountMask();
+                    int amount = shift.y().asConstant().asInt() & mask;
+                    if (shift.x().getKind() == Kind.Int) {
+                        return graph().unique(new IntegerTestNode(shift.x(), ConstantNode.forInt(-1 << amount, graph())));
+                    } else {
+                        assert shift.x().getKind() == Kind.Long;
+                        return graph().unique(new IntegerTestNode(shift.x(), ConstantNode.forLong(-1L << amount, graph())));
+                    }
+                }
+            }
+        }
+        return null;
+    }
 }
diff -r 6fd5f25b546c -r ba4b79da6351 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/LeftShiftNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/LeftShiftNode.java	Fri Mar 21 10:45:16 2014 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/LeftShiftNode.java	Thu Mar 20 14:13:55 2014 +0100
@@ -59,13 +59,7 @@
         } else if (y().isConstant()) {
             int amount = y().asConstant().asInt();
             int originalAmout = amount;
-            int mask;
-            if (getKind() == Kind.Int) {
-                mask = 0x1f;
-            } else {
-                assert getKind() == Kind.Long;
-                mask = 0x3f;
-            }
+            int mask = getShiftAmountMask();
             amount &= mask;
             if (amount == 0) {
                 return x();
diff -r 6fd5f25b546c -r ba4b79da6351 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/RightShiftNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/RightShiftNode.java	Fri Mar 21 10:45:16 2014 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/RightShiftNode.java	Thu Mar 20 14:13:55 2014 +0100
@@ -57,13 +57,7 @@
         } else if (y().isConstant()) {
             int amount = y().asConstant().asInt();
             int originalAmout = amount;
-            int mask;
-            if (getKind() == Kind.Int) {
-                mask = 0x1f;
-            } else {
-                assert getKind() == Kind.Long;
-                mask = 0x3f;
-            }
+            int mask = getShiftAmountMask();
             amount &= mask;
             if (amount == 0) {
                 return x();
diff -r 6fd5f25b546c -r ba4b79da6351 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/ShiftNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/ShiftNode.java	Fri Mar 21 10:45:16 2014 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/ShiftNode.java	Thu Mar 20 14:13:55 2014 +0100
@@ -22,6 +22,7 @@
  */
 package com.oracle.graal.nodes.calc;
 
+import com.oracle.graal.api.meta.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.nodes.type.*;
@@ -40,4 +41,15 @@
     public ShiftNode(Stamp stamp, ValueNode x, ValueNode s) {
         super(stamp, x, s);
     }
+
+    public int getShiftAmountMask() {
+        int mask;
+        if (getKind() == Kind.Int) {
+            mask = 0x1f;
+        } else {
+            assert getKind() == Kind.Long;
+            mask = 0x3f;
+        }
+        return mask;
+    }
 }
diff -r 6fd5f25b546c -r ba4b79da6351 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/UnsignedRightShiftNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/UnsignedRightShiftNode.java	Fri Mar 21 10:45:16 2014 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/UnsignedRightShiftNode.java	Thu Mar 20 14:13:55 2014 +0100
@@ -59,13 +59,7 @@
         } else if (y().isConstant()) {
             int amount = y().asConstant().asInt();
             int originalAmout = amount;
-            int mask;
-            if (getKind() == Kind.Int) {
-                mask = 0x1f;
-            } else {
-                assert getKind() == Kind.Long;
-                mask = 0x3f;
-            }
+            int mask = getShiftAmountMask();
             amount &= mask;
             if (amount == 0) {
                 return x();