# HG changeset patch
# User Lukas Stadler <lukas.stadler@oracle.com>
# Date 1403708096 -7200
# Node ID 561070049e730367e8e17a4ffcc3b6778bf66daf
# Parent  388b787a5fe6581a5d5933358aa0cdd0c0aaa5a4
implement Canonicalizable.Binary in the BinaryNode hierarchy

diff -r 388b787a5fe6 -r 561070049e73 graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopEx.java
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopEx.java	Wed Jun 25 16:35:17 2014 +0200
+++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopEx.java	Wed Jun 25 16:54:56 2014 +0200
@@ -141,11 +141,15 @@
             if (!BinaryNode.canTryReassociate(binary)) {
                 continue;
             }
-            BinaryNode result = BinaryNode.reassociate(binary, invariant);
+            BinaryNode result = BinaryNode.reassociate(binary, invariant, binary.getX(), binary.getY());
             if (result != binary) {
                 if (Debug.isLogEnabled()) {
                     Debug.log("%s : Reassociated %s into %s", MetaUtil.format("%H::%n", graph.method()), binary, result);
                 }
+                if (!result.isAlive()) {
+                    assert !result.isDeleted();
+                    result = graph.addOrUniqueWithInputs(result);
+                }
                 graph.replaceFloating(binary, result);
             }
         }
diff -r 388b787a5fe6 -r 561070049e73 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/AndNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/AndNode.java	Wed Jun 25 16:35:17 2014 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/AndNode.java	Wed Jun 25 16:54:56 2014 +0200
@@ -30,9 +30,10 @@
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.nodes.type.*;
+import com.oracle.graal.nodes.util.*;
 
 @NodeInfo(shortName = "&")
-public final class AndNode extends BitLogicNode implements Canonicalizable, NarrowableArithmeticNode {
+public final class AndNode extends BitLogicNode implements NarrowableArithmeticNode {
 
     public AndNode(ValueNode x, ValueNode y) {
         super(StampTool.and(x.stamp(), y.stamp()), x, y);
@@ -51,40 +52,39 @@
     }
 
     @Override
-    public Node canonical(CanonicalizerTool tool) {
-        if (getX() == getY()) {
-            return getX();
+    public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
+        if (GraphUtil.unproxify(forX) == GraphUtil.unproxify(forY)) {
+            return forX;
         }
-        if (getX().isConstant() && !getY().isConstant()) {
-            return graph().unique(new AndNode(getY(), getX()));
+        if (forX.isConstant() && !forY.isConstant()) {
+            return new AndNode(forY, forX);
         }
-        if (getX().isConstant()) {
-            return ConstantNode.forPrimitive(stamp(), evalConst(getX().asConstant(), getY().asConstant()), graph());
-        } else if (getY().isConstant()) {
-            long rawY = getY().asConstant().asLong();
+        if (forX.isConstant()) {
+            return ConstantNode.forPrimitive(stamp(), evalConst(forX.asConstant(), forY.asConstant()));
+        } else if (forY.isConstant()) {
+            long rawY = forY.asConstant().asLong();
             long mask = IntegerStamp.defaultMask(PrimitiveStamp.getBits(stamp()));
             if ((rawY & mask) == mask) {
-                return getX();
+                return forX;
             }
             if ((rawY & mask) == 0) {
-                return ConstantNode.forIntegerStamp(stamp(), 0, graph());
+                return ConstantNode.forIntegerStamp(stamp(), 0);
             }
-            if (getX() instanceof SignExtendNode) {
-                SignExtendNode ext = (SignExtendNode) getX();
+            if (forX instanceof SignExtendNode) {
+                SignExtendNode ext = (SignExtendNode) forX;
                 if (rawY == ((1L << ext.getInputBits()) - 1)) {
-                    ValueNode result = graph().unique(new ZeroExtendNode(ext.getValue(), ext.getResultBits()));
-                    return result;
+                    return new ZeroExtendNode(ext.getValue(), ext.getResultBits());
                 }
             }
-            if (getX().stamp() instanceof IntegerStamp) {
-                IntegerStamp xStamp = (IntegerStamp) getX().stamp();
+            if (forX.stamp() instanceof IntegerStamp) {
+                IntegerStamp xStamp = (IntegerStamp) forX.stamp();
                 if (((xStamp.upMask() | xStamp.downMask()) & ~rawY) == 0) {
                     // No bits are set which are outside the mask, so the mask will have no effect.
-                    return getX();
+                    return forX;
                 }
             }
 
-            return BinaryNode.reassociate(this, ValueNode.isConstantPredicate());
+            return BinaryNode.reassociate(this, ValueNode.isConstantPredicate(), forX, forY);
         }
         return this;
     }
diff -r 388b787a5fe6 -r 561070049e73 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/BinaryNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/BinaryNode.java	Wed Jun 25 16:35:17 2014 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/BinaryNode.java	Wed Jun 25 16:54:56 2014 +0200
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2009, 2014, 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
@@ -25,12 +25,13 @@
 import com.oracle.graal.compiler.common.*;
 import com.oracle.graal.compiler.common.type.*;
 import com.oracle.graal.graph.iterators.*;
+import com.oracle.graal.graph.spi.*;
 import com.oracle.graal.nodes.*;
 
 /**
  * The {@code BinaryNode} class is the base of arithmetic and logic operations with two inputs.
  */
-public abstract class BinaryNode extends FloatingNode {
+public abstract class BinaryNode extends FloatingNode implements Canonicalizable.Binary<ValueNode> {
 
     @Input private ValueNode x;
     @Input private ValueNode y;
@@ -157,8 +158,11 @@
      * <p>
      * This method accepts only {@linkplain #canTryReassociate(BinaryNode) reassociable} operations
      * such as +, -, *, &amp;, | and ^
+     *
+     * @param forY
+     * @param forX
      */
-    public static BinaryNode reassociate(BinaryNode node, NodePredicate criterion) {
+    public static BinaryNode reassociate(BinaryNode node, NodePredicate criterion, ValueNode forX, ValueNode forY) {
         assert canTryReassociate(node);
         ReassociateMatch match1 = findReassociate(node, criterion);
         if (match1 == null) {
@@ -203,29 +207,28 @@
         ValueNode a = match2.getOtherValue(other);
         if (node instanceof IntegerAddNode || node instanceof IntegerSubNode) {
             BinaryNode associated;
-            StructuredGraph graph = node.graph();
             if (invertM1) {
-                associated = IntegerArithmeticNode.sub(graph, m2, m1);
+                associated = IntegerArithmeticNode.sub(m2, m1);
             } else if (invertM2) {
-                associated = IntegerArithmeticNode.sub(graph, m1, m2);
+                associated = IntegerArithmeticNode.sub(m1, m2);
             } else {
-                associated = IntegerArithmeticNode.add(graph, m1, m2);
+                associated = IntegerArithmeticNode.add(m1, m2);
             }
             if (invertA) {
-                return IntegerArithmeticNode.sub(graph, associated, a);
+                return IntegerArithmeticNode.sub(associated, a);
             }
             if (aSub) {
-                return IntegerArithmeticNode.sub(graph, a, associated);
+                return IntegerArithmeticNode.sub(a, associated);
             }
-            return IntegerArithmeticNode.add(graph, a, associated);
+            return IntegerArithmeticNode.add(a, associated);
         } else if (node instanceof IntegerMulNode) {
-            return IntegerArithmeticNode.mul(node.graph(), a, IntegerAddNode.mul(node.graph(), m1, m2));
+            return IntegerArithmeticNode.mul(a, IntegerAddNode.mul(m1, m2));
         } else if (node instanceof AndNode) {
-            return BitLogicNode.and(node.graph(), a, BitLogicNode.and(node.graph(), m1, m2));
+            return BitLogicNode.and(a, BitLogicNode.and(m1, m2));
         } else if (node instanceof OrNode) {
-            return BitLogicNode.or(node.graph(), a, BitLogicNode.or(node.graph(), m1, m2));
+            return BitLogicNode.or(a, BitLogicNode.or(m1, m2));
         } else if (node instanceof XorNode) {
-            return BitLogicNode.xor(node.graph(), a, BitLogicNode.xor(node.graph(), m1, m2));
+            return BitLogicNode.xor(a, BitLogicNode.xor(m1, m2));
         } else {
             throw GraalInternalError.shouldNotReachHere();
         }
diff -r 388b787a5fe6 -r 561070049e73 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/FloatAddNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/FloatAddNode.java	Wed Jun 25 16:35:17 2014 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/FloatAddNode.java	Wed Jun 25 16:54:56 2014 +0200
@@ -30,7 +30,7 @@
 import com.oracle.graal.nodes.spi.*;
 
 @NodeInfo(shortName = "+")
-public final class FloatAddNode extends FloatArithmeticNode implements Canonicalizable {
+public final class FloatAddNode extends FloatArithmeticNode {
 
     public FloatAddNode(ValueNode x, ValueNode y, boolean isStrictFP) {
         super(x.stamp().unrestricted(), x, y, isStrictFP);
@@ -48,12 +48,12 @@
     }
 
     @Override
-    public Node canonical(CanonicalizerTool tool) {
-        if (getX().isConstant() && !getY().isConstant()) {
-            return graph().unique(new FloatAddNode(getY(), getX(), isStrictFP()));
+    public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
+        if (forX.isConstant() && !forY.isConstant()) {
+            return new FloatAddNode(forY, forX, isStrictFP());
         }
-        if (getX().isConstant()) {
-            return ConstantNode.forPrimitive(evalConst(getX().asConstant(), getY().asConstant()), graph());
+        if (forX.isConstant()) {
+            return ConstantNode.forConstant(evalConst(forX.asConstant(), forY.asConstant()), null);
         }
         // Constant 0.0 can't be eliminated since it can affect the sign of the result.
         return this;
diff -r 388b787a5fe6 -r 561070049e73 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/FloatDivNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/FloatDivNode.java	Wed Jun 25 16:35:17 2014 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/FloatDivNode.java	Wed Jun 25 16:54:56 2014 +0200
@@ -30,7 +30,7 @@
 import com.oracle.graal.nodes.spi.*;
 
 @NodeInfo(shortName = "/")
-public final class FloatDivNode extends FloatArithmeticNode implements Canonicalizable {
+public final class FloatDivNode extends FloatArithmeticNode {
 
     public FloatDivNode(ValueNode x, ValueNode y, boolean isStrictFP) {
         super(x.stamp().unrestricted(), x, y, isStrictFP);
@@ -48,9 +48,9 @@
     }
 
     @Override
-    public Node canonical(CanonicalizerTool tool) {
-        if (getX().isConstant() && getY().isConstant()) {
-            return ConstantNode.forPrimitive(evalConst(getX().asConstant(), getY().asConstant()), graph());
+    public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
+        if (forX.isConstant() && forY.isConstant()) {
+            return ConstantNode.forPrimitive(evalConst(forX.asConstant(), forY.asConstant()));
         }
         return this;
     }
diff -r 388b787a5fe6 -r 561070049e73 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/FloatMulNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/FloatMulNode.java	Wed Jun 25 16:35:17 2014 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/FloatMulNode.java	Wed Jun 25 16:54:56 2014 +0200
@@ -30,7 +30,7 @@
 import com.oracle.graal.nodes.spi.*;
 
 @NodeInfo(shortName = "*")
-public final class FloatMulNode extends FloatArithmeticNode implements Canonicalizable {
+public final class FloatMulNode extends FloatArithmeticNode {
 
     public FloatMulNode(ValueNode x, ValueNode y, boolean isStrictFP) {
         super(x.stamp().unrestricted(), x, y, isStrictFP);
@@ -48,12 +48,12 @@
     }
 
     @Override
-    public Node canonical(CanonicalizerTool tool) {
-        if (getX().isConstant() && !getY().isConstant()) {
-            return graph().unique(new FloatMulNode(getY(), getX(), isStrictFP()));
+    public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
+        if (forX.isConstant() && !forY.isConstant()) {
+            return new FloatMulNode(forY, forX, isStrictFP());
         }
-        if (getX().isConstant()) {
-            return ConstantNode.forPrimitive(evalConst(getX().asConstant(), getY().asConstant()), graph());
+        if (forX.isConstant()) {
+            return ConstantNode.forPrimitive(evalConst(forX.asConstant(), forY.asConstant()));
         }
         return this;
     }
diff -r 388b787a5fe6 -r 561070049e73 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/FloatRemNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/FloatRemNode.java	Wed Jun 25 16:35:17 2014 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/FloatRemNode.java	Wed Jun 25 16:54:56 2014 +0200
@@ -30,7 +30,7 @@
 import com.oracle.graal.nodes.spi.*;
 
 @NodeInfo(shortName = "%")
-public class FloatRemNode extends FloatArithmeticNode implements Canonicalizable, Lowerable {
+public class FloatRemNode extends FloatArithmeticNode implements Lowerable {
 
     public FloatRemNode(ValueNode x, ValueNode y, boolean isStrictFP) {
         super(x.stamp().unrestricted(), x, y, isStrictFP);
@@ -48,9 +48,9 @@
     }
 
     @Override
-    public Node canonical(CanonicalizerTool tool) {
-        if (getX().isConstant() && getY().isConstant()) {
-            return ConstantNode.forPrimitive(evalConst(getX().asConstant(), getY().asConstant()), graph());
+    public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
+        if (forX.isConstant() && forY.isConstant()) {
+            return ConstantNode.forPrimitive(evalConst(getX().asConstant(), getY().asConstant()));
         }
         return this;
     }
diff -r 388b787a5fe6 -r 561070049e73 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/FloatSubNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/FloatSubNode.java	Wed Jun 25 16:35:17 2014 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/FloatSubNode.java	Wed Jun 25 16:54:56 2014 +0200
@@ -28,9 +28,10 @@
 import com.oracle.graal.lir.gen.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.spi.*;
+import com.oracle.graal.nodes.util.*;
 
 @NodeInfo(shortName = "-")
-public final class FloatSubNode extends FloatArithmeticNode implements Canonicalizable {
+public final class FloatSubNode extends FloatArithmeticNode {
 
     public FloatSubNode(ValueNode x, ValueNode y, boolean isStrictFP) {
         super(x.stamp().unrestricted(), x, y, isStrictFP);
@@ -48,12 +49,12 @@
     }
 
     @Override
-    public Node canonical(CanonicalizerTool tool) {
-        if (getX() == getY()) {
-            return ConstantNode.forFloatingStamp(stamp(), 0.0f, graph());
+    public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
+        if (GraphUtil.unproxify(forX) == GraphUtil.unproxify(forY)) {
+            return ConstantNode.forFloatingStamp(stamp(), 0.0f);
         }
-        if (getX().isConstant() && getY().isConstant()) {
-            return ConstantNode.forPrimitive(evalConst(getX().asConstant(), getY().asConstant()), graph());
+        if (forX.isConstant() && forY.isConstant()) {
+            return ConstantNode.forPrimitive(evalConst(forX.asConstant(), forY.asConstant()));
         }
         // Constant 0.0 can't be eliminated since it can affect the sign of the result.
         return this;
diff -r 388b787a5fe6 -r 561070049e73 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerAddNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerAddNode.java	Wed Jun 25 16:35:17 2014 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerAddNode.java	Wed Jun 25 16:54:56 2014 +0200
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2011, 2014, 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
@@ -32,7 +32,7 @@
 import com.oracle.graal.nodes.type.*;
 
 @NodeInfo(shortName = "+")
-public class IntegerAddNode extends IntegerArithmeticNode implements Canonicalizable, NarrowableArithmeticNode {
+public class IntegerAddNode extends IntegerArithmeticNode implements NarrowableArithmeticNode {
 
     public IntegerAddNode(ValueNode x, ValueNode y) {
         super(StampTool.add(x.stamp(), y.stamp()), x, y);
@@ -50,41 +50,41 @@
     }
 
     @Override
-    public Node canonical(CanonicalizerTool tool) {
-        if (getX().isConstant() && !getY().isConstant()) {
-            return graph().unique(new IntegerAddNode(getY(), getX()));
+    public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
+        if (forX.isConstant() && !forY.isConstant()) {
+            return new IntegerAddNode(forY, forX);
         }
-        if (getX() instanceof IntegerSubNode) {
-            IntegerSubNode sub = (IntegerSubNode) getX();
-            if (sub.getY() == getY()) {
+        if (forX instanceof IntegerSubNode) {
+            IntegerSubNode sub = (IntegerSubNode) forX;
+            if (sub.getY() == forY) {
                 // (a - b) + b
                 return sub.getX();
             }
         }
-        if (getY() instanceof IntegerSubNode) {
-            IntegerSubNode sub = (IntegerSubNode) getY();
-            if (sub.getY() == getX()) {
+        if (forY instanceof IntegerSubNode) {
+            IntegerSubNode sub = (IntegerSubNode) forY;
+            if (sub.getY() == forX) {
                 // b + (a - b)
                 return sub.getX();
             }
         }
-        if (getX().isConstant()) {
-            return ConstantNode.forPrimitive(evalConst(getX().asConstant(), getY().asConstant()), graph());
-        } else if (getY().isConstant()) {
-            long c = getY().asConstant().asLong();
+        if (forX.isConstant()) {
+            return ConstantNode.forPrimitive(evalConst(forX.asConstant(), forY.asConstant()));
+        } else if (forY.isConstant()) {
+            long c = forY.asConstant().asLong();
             if (c == 0) {
-                return getX();
+                return forX;
             }
             // canonicalize expressions like "(a + 1) + 2"
-            BinaryNode reassociated = BinaryNode.reassociate(this, ValueNode.isConstantPredicate());
+            BinaryNode reassociated = BinaryNode.reassociate(this, ValueNode.isConstantPredicate(), forX, forY);
             if (reassociated != this) {
                 return reassociated;
             }
         }
-        if (getX() instanceof NegateNode) {
-            return IntegerArithmeticNode.sub(graph(), getY(), ((NegateNode) getX()).getValue());
-        } else if (getY() instanceof NegateNode) {
-            return IntegerArithmeticNode.sub(graph(), getX(), ((NegateNode) getY()).getValue());
+        if (forX instanceof NegateNode) {
+            return IntegerArithmeticNode.sub(forY, ((NegateNode) forX).getValue());
+        } else if (forY instanceof NegateNode) {
+            return IntegerArithmeticNode.sub(forX, ((NegateNode) forY).getValue());
         }
         return this;
     }
diff -r 388b787a5fe6 -r 561070049e73 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerArithmeticNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerArithmeticNode.java	Wed Jun 25 16:35:17 2014 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerArithmeticNode.java	Wed Jun 25 16:54:56 2014 +0200
@@ -37,11 +37,23 @@
         return graph.unique(new IntegerAddNode(v1, v2));
     }
 
+    public static IntegerAddNode add(ValueNode v1, ValueNode v2) {
+        return new IntegerAddNode(v1, v2);
+    }
+
     public static IntegerMulNode mul(StructuredGraph graph, ValueNode v1, ValueNode v2) {
         return graph.unique(new IntegerMulNode(v1, v2));
     }
 
+    public static IntegerMulNode mul(ValueNode v1, ValueNode v2) {
+        return new IntegerMulNode(v1, v2);
+    }
+
     public static IntegerSubNode sub(StructuredGraph graph, ValueNode v1, ValueNode v2) {
         return graph.unique(new IntegerSubNode(v1, v2));
     }
+
+    public static IntegerSubNode sub(ValueNode v1, ValueNode v2) {
+        return new IntegerSubNode(v1, v2);
+    }
 }
diff -r 388b787a5fe6 -r 561070049e73 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerDivNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerDivNode.java	Wed Jun 25 16:35:17 2014 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerDivNode.java	Wed Jun 25 16:54:56 2014 +0200
@@ -66,13 +66,13 @@
                 // no rounding if dividend is positive or if its low bits are always 0
                 if (stampX.canBeNegative() || (stampX.upMask() & (abs - 1)) != 0) {
                     int bits = PrimitiveStamp.getBits(stamp());
-                    RightShiftNode sign = graph().unique(new RightShiftNode(x(), ConstantNode.forInt(bits - 1, graph())));
-                    UnsignedRightShiftNode round = graph().unique(new UnsignedRightShiftNode(sign, ConstantNode.forInt(bits - log2, graph())));
-                    dividend = IntegerArithmeticNode.add(graph(), dividend, round);
+                    RightShiftNode sign = new RightShiftNode(x(), ConstantNode.forInt(bits - 1));
+                    UnsignedRightShiftNode round = new UnsignedRightShiftNode(sign, ConstantNode.forInt(bits - log2));
+                    dividend = IntegerArithmeticNode.add(dividend, round);
                 }
-                RightShiftNode shift = graph().unique(new RightShiftNode(dividend, ConstantNode.forInt(log2, graph())));
+                RightShiftNode shift = new RightShiftNode(dividend, ConstantNode.forInt(log2));
                 if (c < 0) {
-                    return graph().unique(new NegateNode(shift));
+                    return new NegateNode(shift);
                 }
                 return shift;
             }
diff -r 388b787a5fe6 -r 561070049e73 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerMulNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerMulNode.java	Wed Jun 25 16:35:17 2014 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerMulNode.java	Wed Jun 25 16:54:56 2014 +0200
@@ -32,7 +32,7 @@
 import com.oracle.graal.nodes.spi.*;
 
 @NodeInfo(shortName = "*")
-public class IntegerMulNode extends IntegerArithmeticNode implements Canonicalizable, NarrowableArithmeticNode {
+public class IntegerMulNode extends IntegerArithmeticNode implements NarrowableArithmeticNode {
 
     public IntegerMulNode(ValueNode x, ValueNode y) {
         super(x.stamp().unrestricted(), x, y);
@@ -46,31 +46,31 @@
     }
 
     @Override
-    public Node canonical(CanonicalizerTool tool) {
-        if (getX().isConstant() && !getY().isConstant()) {
-            return graph().unique(new IntegerMulNode(getY(), getX()));
+    public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
+        if (forX.isConstant() && !forY.isConstant()) {
+            return new IntegerMulNode(forY, forX);
         }
-        if (getX().isConstant()) {
-            return ConstantNode.forPrimitive(evalConst(getX().asConstant(), getY().asConstant()), graph());
-        } else if (getY().isConstant()) {
-            long c = getY().asConstant().asLong();
+        if (forX.isConstant()) {
+            return ConstantNode.forPrimitive(evalConst(forX.asConstant(), forY.asConstant()));
+        } else if (forY.isConstant()) {
+            long c = forY.asConstant().asLong();
             if (c == 1) {
-                return getX();
+                return forX;
             }
             if (c == 0) {
-                return ConstantNode.forIntegerStamp(stamp(), 0, graph());
+                return ConstantNode.forIntegerStamp(stamp(), 0);
             }
             long abs = Math.abs(c);
             if (abs > 0 && CodeUtil.isPowerOf2(abs)) {
-                LeftShiftNode shift = graph().unique(new LeftShiftNode(getX(), ConstantNode.forInt(CodeUtil.log2(abs), graph())));
+                LeftShiftNode shift = new LeftShiftNode(forX, ConstantNode.forInt(CodeUtil.log2(abs)));
                 if (c < 0) {
-                    return graph().unique(new NegateNode(shift));
+                    return new NegateNode(shift);
                 } else {
                     return shift;
                 }
             }
             // canonicalize expressions like "(a * 1) * 2"
-            return BinaryNode.reassociate(this, ValueNode.isConstantPredicate());
+            return BinaryNode.reassociate(this, ValueNode.isConstantPredicate(), forX, forY);
         }
         return this;
     }
diff -r 388b787a5fe6 -r 561070049e73 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerRemNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerRemNode.java	Wed Jun 25 16:35:17 2014 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerRemNode.java	Wed Jun 25 16:54:56 2014 +0200
@@ -49,13 +49,13 @@
             if (y == 0) {
                 return this; // this will trap, can not canonicalize
             }
-            return ConstantNode.forIntegerStamp(stamp(), x().asConstant().asLong() % y, graph());
+            return ConstantNode.forIntegerStamp(stamp(), x().asConstant().asLong() % y);
         } else if (y().isConstant()) {
             long c = y().asConstant().asLong();
             if (c == 1 || c == -1) {
-                return ConstantNode.forIntegerStamp(stamp(), 0, graph());
+                return ConstantNode.forIntegerStamp(stamp(), 0);
             } else if (c > 0 && CodeUtil.isPowerOf2(c) && x().stamp() instanceof IntegerStamp && ((IntegerStamp) x().stamp()).isPositive()) {
-                return graph().unique(new AndNode(x(), ConstantNode.forIntegerStamp(stamp(), c - 1, graph())));
+                return new AndNode(x(), ConstantNode.forIntegerStamp(stamp(), c - 1));
             }
         }
         return this;
diff -r 388b787a5fe6 -r 561070049e73 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerSubNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerSubNode.java	Wed Jun 25 16:35:17 2014 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerSubNode.java	Wed Jun 25 16:54:56 2014 +0200
@@ -30,9 +30,10 @@
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.nodes.type.*;
+import com.oracle.graal.nodes.util.*;
 
 @NodeInfo(shortName = "-")
-public class IntegerSubNode extends IntegerArithmeticNode implements Canonicalizable, NarrowableArithmeticNode {
+public class IntegerSubNode extends IntegerArithmeticNode implements NarrowableArithmeticNode {
 
     public IntegerSubNode(ValueNode x, ValueNode y) {
         super(StampTool.sub(x.stamp(), y.stamp()), x, y);
@@ -50,69 +51,69 @@
     }
 
     @Override
-    public Node canonical(CanonicalizerTool tool) {
-        if (getX() == getY()) {
-            return ConstantNode.forIntegerStamp(stamp(), 0, graph());
+    public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
+        if (GraphUtil.unproxify(forX) == GraphUtil.unproxify(forY)) {
+            return ConstantNode.forIntegerStamp(stamp(), 0);
         }
-        if (getX() instanceof IntegerAddNode) {
-            IntegerAddNode x = (IntegerAddNode) getX();
-            if (x.getY() == getY()) {
+        if (forX instanceof IntegerAddNode) {
+            IntegerAddNode x = (IntegerAddNode) forX;
+            if (x.getY() == forY) {
                 // (a + b) - b
                 return x.getX();
             }
-            if (x.getX() == getY()) {
+            if (x.getX() == forY) {
                 // (a + b) - a
                 return x.getY();
             }
-        } else if (getX() instanceof IntegerSubNode) {
-            IntegerSubNode x = (IntegerSubNode) getX();
-            if (x.getX() == getY()) {
+        } else if (forX instanceof IntegerSubNode) {
+            IntegerSubNode x = (IntegerSubNode) forX;
+            if (x.getX() == forY) {
                 // (a - b) - a
-                return graph().unique(new NegateNode(x.getY()));
+                return new NegateNode(x.getY());
             }
         }
-        if (getY() instanceof IntegerAddNode) {
-            IntegerAddNode y = (IntegerAddNode) getY();
-            if (y.getX() == getX()) {
+        if (forY instanceof IntegerAddNode) {
+            IntegerAddNode y = (IntegerAddNode) forY;
+            if (y.getX() == forX) {
                 // a - (a + b)
-                return graph().unique(new NegateNode(y.getY()));
+                return new NegateNode(y.getY());
             }
-            if (y.getY() == getX()) {
+            if (y.getY() == forX) {
                 // b - (a + b)
-                return graph().unique(new NegateNode(y.getX()));
+                return new NegateNode(y.getX());
             }
-        } else if (getY() instanceof IntegerSubNode) {
-            IntegerSubNode y = (IntegerSubNode) getY();
-            if (y.getX() == getX()) {
+        } else if (forY instanceof IntegerSubNode) {
+            IntegerSubNode y = (IntegerSubNode) forY;
+            if (y.getX() == forX) {
                 // a - (a - b)
                 return y.getY();
             }
         }
-        if (getX().isConstant() && getY().isConstant()) {
-            return ConstantNode.forPrimitive(evalConst(getX().asConstant(), getY().asConstant()), graph());
-        } else if (getY().isConstant()) {
-            long c = getY().asConstant().asLong();
+        if (forX.isConstant() && forY.isConstant()) {
+            return ConstantNode.forPrimitive(evalConst(forX.asConstant(), forY.asConstant()));
+        } else if (forY.isConstant()) {
+            long c = forY.asConstant().asLong();
             if (c == 0) {
-                return getX();
+                return forX;
             }
-            BinaryNode reassociated = BinaryNode.reassociate(this, ValueNode.isConstantPredicate());
+            BinaryNode reassociated = BinaryNode.reassociate(this, ValueNode.isConstantPredicate(), forX, forY);
             if (reassociated != this) {
                 return reassociated;
             }
-            if (c < 0 || ((IntegerStamp) StampFactory.forKind(getY().getKind())).contains(-c)) {
+            if (c < 0 || ((IntegerStamp) StampFactory.forKind(forY.getKind())).contains(-c)) {
                 // Adding a negative is more friendly to the backend since adds are
                 // commutative, so prefer add when it fits.
-                return IntegerArithmeticNode.add(graph(), getX(), ConstantNode.forIntegerStamp(stamp(), -c, graph()));
+                return IntegerArithmeticNode.add(forX, ConstantNode.forIntegerStamp(stamp(), -c));
             }
-        } else if (getX().isConstant()) {
-            long c = getX().asConstant().asLong();
+        } else if (forX.isConstant()) {
+            long c = forX.asConstant().asLong();
             if (c == 0) {
-                return graph().unique(new NegateNode(getY()));
+                return new NegateNode(forY);
             }
-            return BinaryNode.reassociate(this, ValueNode.isConstantPredicate());
+            return BinaryNode.reassociate(this, ValueNode.isConstantPredicate(), forX, forY);
         }
-        if (getY() instanceof NegateNode) {
-            return IntegerArithmeticNode.add(graph(), getX(), ((NegateNode) getY()).getValue());
+        if (forY instanceof NegateNode) {
+            return IntegerArithmeticNode.add(forX, ((NegateNode) forY).getValue());
         }
         return this;
     }
diff -r 388b787a5fe6 -r 561070049e73 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	Wed Jun 25 16:35:17 2014 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/LeftShiftNode.java	Wed Jun 25 16:54:56 2014 +0200
@@ -31,7 +31,7 @@
 import com.oracle.graal.nodes.type.*;
 
 @NodeInfo(shortName = "<<")
-public final class LeftShiftNode extends ShiftNode implements Canonicalizable {
+public final class LeftShiftNode extends ShiftNode {
 
     public LeftShiftNode(ValueNode x, ValueNode y) {
         super(x, y);
@@ -54,39 +54,39 @@
     }
 
     @Override
-    public Node canonical(CanonicalizerTool tool) {
-        if (getX().isConstant() && getY().isConstant()) {
-            return ConstantNode.forPrimitive(evalConst(getX().asConstant(), getY().asConstant()), graph());
-        } else if (getY().isConstant()) {
-            int amount = getY().asConstant().asInt();
+    public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
+        if (forX.isConstant() && forY.isConstant()) {
+            return ConstantNode.forPrimitive(evalConst(forX.asConstant(), forY.asConstant()));
+        } else if (forY.isConstant()) {
+            int amount = forY.asConstant().asInt();
             int originalAmout = amount;
             int mask = getShiftAmountMask();
             amount &= mask;
             if (amount == 0) {
-                return getX();
+                return forX;
             }
-            if (getX() instanceof ShiftNode) {
-                ShiftNode other = (ShiftNode) getX();
+            if (forX instanceof ShiftNode) {
+                ShiftNode other = (ShiftNode) forX;
                 if (other.getY().isConstant()) {
                     int otherAmount = other.getY().asConstant().asInt() & mask;
                     if (other instanceof LeftShiftNode) {
                         int total = amount + otherAmount;
                         if (total != (total & mask)) {
-                            return ConstantNode.forIntegerKind(getKind(), 0, graph());
+                            return ConstantNode.forIntegerKind(getKind(), 0);
                         }
-                        return graph().unique(new LeftShiftNode(other.getX(), ConstantNode.forInt(total, graph())));
+                        return new LeftShiftNode(other.getX(), ConstantNode.forInt(total));
                     } else if ((other instanceof RightShiftNode || other instanceof UnsignedRightShiftNode) && otherAmount == amount) {
                         if (getKind() == Kind.Long) {
-                            return graph().unique(new AndNode(other.getX(), ConstantNode.forLong(-1L << amount, graph())));
+                            return new AndNode(other.getX(), ConstantNode.forLong(-1L << amount));
                         } else {
                             assert getKind() == Kind.Int;
-                            return graph().unique(new AndNode(other.getX(), ConstantNode.forInt(-1 << amount, graph())));
+                            return new AndNode(other.getX(), ConstantNode.forInt(-1 << amount));
                         }
                     }
                 }
             }
             if (originalAmout != amount) {
-                return graph().unique(new LeftShiftNode(getX(), ConstantNode.forInt(amount, graph())));
+                return new LeftShiftNode(forX, ConstantNode.forInt(amount));
             }
         }
         return this;
diff -r 388b787a5fe6 -r 561070049e73 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/NormalizeCompareNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/NormalizeCompareNode.java	Wed Jun 25 16:35:17 2014 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/NormalizeCompareNode.java	Wed Jun 25 16:54:56 2014 +0200
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2009, 2012, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2009, 2014, 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
@@ -24,6 +24,7 @@
 
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.compiler.common.type.*;
+import com.oracle.graal.graph.spi.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.spi.*;
 
@@ -50,6 +51,12 @@
     }
 
     @Override
+    public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
+        // nothing to do
+        return this;
+    }
+
+    @Override
     public void lower(LoweringTool tool) {
         LogicNode equalComp;
         LogicNode lessComp;
diff -r 388b787a5fe6 -r 561070049e73 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/OrNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/OrNode.java	Wed Jun 25 16:35:17 2014 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/OrNode.java	Wed Jun 25 16:54:56 2014 +0200
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2011, 2014, 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
@@ -30,9 +30,10 @@
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.nodes.type.*;
+import com.oracle.graal.nodes.util.*;
 
 @NodeInfo(shortName = "|")
-public final class OrNode extends BitLogicNode implements Canonicalizable {
+public final class OrNode extends BitLogicNode {
 
     public OrNode(ValueNode x, ValueNode y) {
         super(StampTool.or(x.stamp(), y.stamp()), x, y);
@@ -51,25 +52,25 @@
     }
 
     @Override
-    public Node canonical(CanonicalizerTool tool) {
-        if (getX() == getY()) {
-            return getX();
+    public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
+        if (GraphUtil.unproxify(forX) == GraphUtil.unproxify(forY)) {
+            return forX;
         }
-        if (getX().isConstant() && !getY().isConstant()) {
-            return graph().unique(new OrNode(getY(), getX()));
+        if (forX.isConstant() && !forY.isConstant()) {
+            return new OrNode(forY, forX);
         }
-        if (getX().isConstant()) {
-            return ConstantNode.forPrimitive(stamp(), evalConst(getX().asConstant(), getY().asConstant()), graph());
-        } else if (getY().isConstant()) {
-            long rawY = getY().asConstant().asLong();
+        if (forX.isConstant()) {
+            return ConstantNode.forPrimitive(stamp(), evalConst(forX.asConstant(), forY.asConstant()));
+        } else if (forY.isConstant()) {
+            long rawY = forY.asConstant().asLong();
             long mask = IntegerStamp.defaultMask(PrimitiveStamp.getBits(stamp()));
             if ((rawY & mask) == mask) {
-                return ConstantNode.forIntegerStamp(stamp(), mask, graph());
+                return ConstantNode.forIntegerStamp(stamp(), mask);
             }
             if ((rawY & mask) == 0) {
-                return getX();
+                return forX;
             }
-            return BinaryNode.reassociate(this, ValueNode.isConstantPredicate());
+            return BinaryNode.reassociate(this, ValueNode.isConstantPredicate(), forX, forY);
         }
         return this;
     }
diff -r 388b787a5fe6 -r 561070049e73 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	Wed Jun 25 16:35:17 2014 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/RightShiftNode.java	Wed Jun 25 16:54:56 2014 +0200
@@ -31,7 +31,7 @@
 import com.oracle.graal.nodes.spi.*;
 
 @NodeInfo(shortName = ">>")
-public final class RightShiftNode extends ShiftNode implements Canonicalizable {
+public final class RightShiftNode extends ShiftNode {
 
     public RightShiftNode(ValueNode x, ValueNode y) {
         super(x, y);
@@ -49,22 +49,22 @@
     }
 
     @Override
-    public Node canonical(CanonicalizerTool tool) {
-        if (getX().stamp() instanceof IntegerStamp && ((IntegerStamp) getX().stamp()).isPositive()) {
-            return graph().unique(new UnsignedRightShiftNode(getX(), getY()));
+    public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
+        if (forX.stamp() instanceof IntegerStamp && ((IntegerStamp) forX.stamp()).isPositive()) {
+            return new UnsignedRightShiftNode(forX, forY);
         }
-        if (getX().isConstant() && getY().isConstant()) {
-            return ConstantNode.forPrimitive(evalConst(getX().asConstant(), getY().asConstant()), graph());
-        } else if (getY().isConstant()) {
-            int amount = getY().asConstant().asInt();
+        if (forX.isConstant() && forY.isConstant()) {
+            return ConstantNode.forPrimitive(evalConst(forX.asConstant(), forY.asConstant()));
+        } else if (forY.isConstant()) {
+            int amount = forY.asConstant().asInt();
             int originalAmout = amount;
             int mask = getShiftAmountMask();
             amount &= mask;
             if (amount == 0) {
-                return getX();
+                return forX;
             }
-            if (getX() instanceof ShiftNode) {
-                ShiftNode other = (ShiftNode) getX();
+            if (forX instanceof ShiftNode) {
+                ShiftNode other = (ShiftNode) forX;
                 if (other.getY().isConstant()) {
                     int otherAmount = other.getY().asConstant().asInt() & mask;
                     if (other instanceof RightShiftNode) {
@@ -74,10 +74,10 @@
                             IntegerStamp istamp = (IntegerStamp) other.getX().stamp();
 
                             if (istamp.isPositive()) {
-                                return ConstantNode.forIntegerKind(getKind(), 0, graph());
+                                return ConstantNode.forIntegerKind(getKind(), 0);
                             }
                             if (istamp.isStrictlyNegative()) {
-                                return ConstantNode.forIntegerKind(getKind(), -1L, graph());
+                                return ConstantNode.forIntegerKind(getKind(), -1L);
                             }
 
                             /*
@@ -85,14 +85,14 @@
                              * full shift for this kind
                              */
                             assert total >= mask;
-                            return graph().unique(new RightShiftNode(other.getX(), ConstantNode.forInt(mask, graph())));
+                            return new RightShiftNode(other.getX(), ConstantNode.forInt(mask));
                         }
-                        return graph().unique(new RightShiftNode(other.getX(), ConstantNode.forInt(total, graph())));
+                        return new RightShiftNode(other.getX(), ConstantNode.forInt(total));
                     }
                 }
             }
             if (originalAmout != amount) {
-                return graph().unique(new RightShiftNode(getX(), ConstantNode.forInt(amount, graph())));
+                return new RightShiftNode(forX, ConstantNode.forInt(amount));
             }
         }
         return this;
diff -r 388b787a5fe6 -r 561070049e73 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/UnsignedRemNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/UnsignedRemNode.java	Wed Jun 25 16:35:17 2014 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/UnsignedRemNode.java	Wed Jun 25 16:54:56 2014 +0200
@@ -47,9 +47,9 @@
         } else if (y().isConstant()) {
             long c = y().asConstant().asLong();
             if (c == 1) {
-                return ConstantNode.forIntegerStamp(stamp(), 0, graph());
+                return ConstantNode.forIntegerStamp(stamp(), 0);
             } else if (CodeUtil.isPowerOf2(c)) {
-                return graph().unique(new AndNode(x(), ConstantNode.forIntegerStamp(stamp(), c - 1, graph())));
+                return new AndNode(x(), ConstantNode.forIntegerStamp(stamp(), c - 1));
             }
         }
         return this;
diff -r 388b787a5fe6 -r 561070049e73 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	Wed Jun 25 16:35:17 2014 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/UnsignedRightShiftNode.java	Wed Jun 25 16:54:56 2014 +0200
@@ -31,7 +31,7 @@
 import com.oracle.graal.nodes.type.*;
 
 @NodeInfo(shortName = ">>>")
-public final class UnsignedRightShiftNode extends ShiftNode implements Canonicalizable {
+public final class UnsignedRightShiftNode extends ShiftNode {
 
     public UnsignedRightShiftNode(ValueNode x, ValueNode y) {
         super(x, y);
@@ -54,39 +54,39 @@
     }
 
     @Override
-    public Node canonical(CanonicalizerTool tool) {
-        if (getX().isConstant() && getY().isConstant()) {
-            return ConstantNode.forPrimitive(evalConst(getX().asConstant(), getY().asConstant()), graph());
-        } else if (getY().isConstant()) {
-            int amount = getY().asConstant().asInt();
+    public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
+        if (forX.isConstant() && forY.isConstant()) {
+            return ConstantNode.forPrimitive(evalConst(forX.asConstant(), forY.asConstant()));
+        } else if (forY.isConstant()) {
+            int amount = forY.asConstant().asInt();
             int originalAmout = amount;
             int mask = getShiftAmountMask();
             amount &= mask;
             if (amount == 0) {
-                return getX();
+                return forX;
             }
-            if (getX() instanceof ShiftNode) {
-                ShiftNode other = (ShiftNode) getX();
+            if (forX instanceof ShiftNode) {
+                ShiftNode other = (ShiftNode) forX;
                 if (other.getY().isConstant()) {
                     int otherAmount = other.getY().asConstant().asInt() & mask;
                     if (other instanceof UnsignedRightShiftNode) {
                         int total = amount + otherAmount;
                         if (total != (total & mask)) {
-                            return ConstantNode.forIntegerKind(getKind(), 0, graph());
+                            return ConstantNode.forIntegerKind(getKind(), 0);
                         }
-                        return graph().unique(new UnsignedRightShiftNode(other.getX(), ConstantNode.forInt(total, graph())));
+                        return new UnsignedRightShiftNode(other.getX(), ConstantNode.forInt(total));
                     } else if (other instanceof LeftShiftNode && otherAmount == amount) {
                         if (getKind() == Kind.Long) {
-                            return graph().unique(new AndNode(other.getX(), ConstantNode.forLong(-1L >>> amount, graph())));
+                            return new AndNode(other.getX(), ConstantNode.forLong(-1L >>> amount));
                         } else {
                             assert getKind() == Kind.Int;
-                            return graph().unique(new AndNode(other.getX(), ConstantNode.forInt(-1 >>> amount, graph())));
+                            return new AndNode(other.getX(), ConstantNode.forInt(-1 >>> amount));
                         }
                     }
                 }
             }
             if (originalAmout != amount) {
-                return graph().unique(new UnsignedRightShiftNode(getX(), ConstantNode.forInt(amount, graph())));
+                return new UnsignedRightShiftNode(forX, ConstantNode.forInt(amount));
             }
         }
         return this;
diff -r 388b787a5fe6 -r 561070049e73 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/XorNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/XorNode.java	Wed Jun 25 16:35:17 2014 +0200
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/XorNode.java	Wed Jun 25 16:54:56 2014 +0200
@@ -30,9 +30,10 @@
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.nodes.type.*;
+import com.oracle.graal.nodes.util.*;
 
 @NodeInfo(shortName = "^")
-public final class XorNode extends BitLogicNode implements Canonicalizable {
+public final class XorNode extends BitLogicNode {
 
     public XorNode(ValueNode x, ValueNode y) {
         super(StampTool.xor(x.stamp(), y.stamp()), x, y);
@@ -51,24 +52,24 @@
     }
 
     @Override
-    public Node canonical(CanonicalizerTool tool) {
-        if (getX() == getY()) {
-            return ConstantNode.forIntegerStamp(stamp(), 0, graph());
+    public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
+        if (GraphUtil.unproxify(forX) == GraphUtil.unproxify(forY)) {
+            return ConstantNode.forIntegerStamp(stamp(), 0);
         }
-        if (getX().isConstant() && !getY().isConstant()) {
-            return graph().unique(new XorNode(getY(), getX()));
+        if (forX.isConstant() && !forY.isConstant()) {
+            return new XorNode(forY, forX);
         }
-        if (getX().isConstant()) {
-            return ConstantNode.forPrimitive(stamp(), evalConst(getX().asConstant(), getY().asConstant()), graph());
-        } else if (getY().isConstant()) {
-            long rawY = getY().asConstant().asLong();
+        if (forX.isConstant()) {
+            return ConstantNode.forPrimitive(stamp(), evalConst(forX.asConstant(), forY.asConstant()));
+        } else if (forY.isConstant()) {
+            long rawY = forY.asConstant().asLong();
             long mask = IntegerStamp.defaultMask(PrimitiveStamp.getBits(stamp()));
             if ((rawY & mask) == 0) {
-                return getX();
+                return forX;
             } else if ((rawY & mask) == mask) {
-                return graph().unique(new NotNode(getX()));
+                return new NotNode(forX);
             }
-            return BinaryNode.reassociate(this, ValueNode.isConstantPredicate());
+            return BinaryNode.reassociate(this, ValueNode.isConstantPredicate(), forX, forY);
         }
         return this;
     }
diff -r 388b787a5fe6 -r 561070049e73 graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/nodes/arithmetic/IntegerAddExactNode.java
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/nodes/arithmetic/IntegerAddExactNode.java	Wed Jun 25 16:35:17 2014 +0200
+++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/nodes/arithmetic/IntegerAddExactNode.java	Wed Jun 25 16:54:56 2014 +0200
@@ -24,7 +24,6 @@
 
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.compiler.common.type.*;
-import com.oracle.graal.graph.*;
 import com.oracle.graal.graph.spi.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.calc.*;
@@ -36,7 +35,7 @@
  * Node representing an exact integer addition that will throw an {@link ArithmeticException} in
  * case the addition would overflow the 32 bit range.
  */
-public class IntegerAddExactNode extends IntegerAddNode implements Canonicalizable, IntegerExactArithmeticNode {
+public class IntegerAddExactNode extends IntegerAddNode implements IntegerExactArithmeticNode {
 
     public IntegerAddExactNode(ValueNode x, ValueNode y) {
         super(x, y);
@@ -50,13 +49,13 @@
     }
 
     @Override
-    public Node canonical(CanonicalizerTool tool) {
-        if (getX().isConstant() && !getY().isConstant()) {
-            return graph().unique(new IntegerAddExactNode(getY(), getX()));
+    public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
+        if (forX.isConstant() && !forY.isConstant()) {
+            return new IntegerAddExactNode(forY, forX);
         }
-        if (getX().isConstant()) {
-            Constant xConst = getX().asConstant();
-            Constant yConst = getY().asConstant();
+        if (forX.isConstant()) {
+            Constant xConst = forX.asConstant();
+            Constant yConst = forY.asConstant();
             assert xConst.getKind() == yConst.getKind();
             try {
                 if (xConst.getKind() == Kind.Int) {
@@ -68,10 +67,10 @@
             } catch (ArithmeticException ex) {
                 // The operation will result in an overflow exception, so do not canonicalize.
             }
-        } else if (getY().isConstant()) {
-            long c = getY().asConstant().asLong();
+        } else if (forY.isConstant()) {
+            long c = forY.asConstant().asLong();
             if (c == 0) {
-                return getX();
+                return forX;
             }
         }
         return this;
diff -r 388b787a5fe6 -r 561070049e73 graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/nodes/arithmetic/IntegerMulExactNode.java
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/nodes/arithmetic/IntegerMulExactNode.java	Wed Jun 25 16:35:17 2014 +0200
+++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/nodes/arithmetic/IntegerMulExactNode.java	Wed Jun 25 16:54:56 2014 +0200
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2013, 2014, 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
@@ -24,7 +24,6 @@
 
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.compiler.common.type.*;
-import com.oracle.graal.graph.*;
 import com.oracle.graal.graph.spi.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.calc.*;
@@ -35,7 +34,7 @@
  * Node representing an exact integer multiplication that will throw an {@link ArithmeticException}
  * in case the addition would overflow the 32 bit range.
  */
-public class IntegerMulExactNode extends IntegerMulNode implements Canonicalizable, IntegerExactArithmeticNode {
+public class IntegerMulExactNode extends IntegerMulNode implements IntegerExactArithmeticNode {
 
     public IntegerMulExactNode(ValueNode x, ValueNode y) {
         super(x, y);
@@ -43,31 +42,31 @@
     }
 
     @Override
-    public Node canonical(CanonicalizerTool tool) {
-        if (getX().isConstant() && !getY().isConstant()) {
-            return graph().unique(new IntegerMulExactNode(getY(), getX()));
+    public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
+        if (forX.isConstant() && !forY.isConstant()) {
+            return new IntegerMulExactNode(forY, forX);
         }
-        if (getX().isConstant()) {
-            Constant xConst = getX().asConstant();
-            Constant yConst = getY().asConstant();
+        if (forX.isConstant()) {
+            Constant xConst = forX.asConstant();
+            Constant yConst = forY.asConstant();
             assert xConst.getKind() == yConst.getKind();
             try {
                 if (xConst.getKind() == Kind.Int) {
-                    return ConstantNode.forInt(ExactMath.multiplyExact(xConst.asInt(), yConst.asInt()), graph());
+                    return ConstantNode.forInt(ExactMath.multiplyExact(xConst.asInt(), yConst.asInt()));
                 } else {
                     assert xConst.getKind() == Kind.Long;
-                    return ConstantNode.forLong(ExactMath.multiplyExact(xConst.asLong(), yConst.asLong()), graph());
+                    return ConstantNode.forLong(ExactMath.multiplyExact(xConst.asLong(), yConst.asLong()));
                 }
             } catch (ArithmeticException ex) {
                 // The operation will result in an overflow exception, so do not canonicalize.
             }
-        } else if (getY().isConstant()) {
-            long c = getY().asConstant().asLong();
+        } else if (forY.isConstant()) {
+            long c = forY.asConstant().asLong();
             if (c == 1) {
-                return getX();
+                return forX;
             }
             if (c == 0) {
-                return ConstantNode.forIntegerStamp(stamp(), 0, graph());
+                return ConstantNode.forIntegerStamp(stamp(), 0);
             }
         }
         return this;
diff -r 388b787a5fe6 -r 561070049e73 graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/nodes/arithmetic/IntegerMulHighNode.java
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/nodes/arithmetic/IntegerMulHighNode.java	Wed Jun 25 16:35:17 2014 +0200
+++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/nodes/arithmetic/IntegerMulHighNode.java	Wed Jun 25 16:54:56 2014 +0200
@@ -22,10 +22,13 @@
  */
 package com.oracle.graal.truffle.nodes.arithmetic;
 
+import java.util.function.*;
+
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.compiler.common.*;
 import com.oracle.graal.compiler.common.type.*;
 import com.oracle.graal.graph.*;
+import com.oracle.graal.graph.spi.*;
 import com.oracle.graal.lir.gen.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.calc.*;
@@ -56,10 +59,13 @@
         }
     }
 
-    @Override
-    public boolean inferStamp() {
-        IntegerStamp xStamp = (IntegerStamp) getX().stamp();
-        IntegerStamp yStamp = (IntegerStamp) getY().stamp();
+    /**
+     * Determines the minimum and maximum result of this node for the given inputs and returns the
+     * result of the given BiFunction on the minimum and maximum values.
+     */
+    private <T> T processExtremes(ValueNode forX, ValueNode forY, BiFunction<Long, Long, T> op) {
+        IntegerStamp xStamp = (IntegerStamp) forX.stamp();
+        IntegerStamp yStamp = (IntegerStamp) forY.stamp();
 
         Kind kind = getKind();
         assert kind == Kind.Int || kind == Kind.Long;
@@ -74,7 +80,18 @@
                 max = Math.max(max, result);
             }
         }
-        return updateStamp(StampFactory.forInteger(getKind(), min, max));
+        return op.apply(min, max);
+    }
+
+    @Override
+    public boolean inferStamp() {
+        return updateStamp(processExtremes(getX(), getY(), (min, max) -> StampFactory.forInteger(getKind(), min, max)));
+    }
+
+    @SuppressWarnings("cast")
+    @Override
+    public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
+        return processExtremes(forX, forY, (min, max) -> min == (long) max ? ConstantNode.forIntegerKind(getKind(), min) : this);
     }
 
     @Override
diff -r 388b787a5fe6 -r 561070049e73 graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/nodes/arithmetic/IntegerSubExactNode.java
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/nodes/arithmetic/IntegerSubExactNode.java	Wed Jun 25 16:35:17 2014 +0200
+++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/nodes/arithmetic/IntegerSubExactNode.java	Wed Jun 25 16:54:56 2014 +0200
@@ -24,19 +24,19 @@
 
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.compiler.common.type.*;
-import com.oracle.graal.graph.*;
 import com.oracle.graal.graph.spi.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.calc.*;
 import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.nodes.type.*;
+import com.oracle.graal.nodes.util.*;
 import com.oracle.truffle.api.*;
 
 /**
  * Node representing an exact integer substraction that will throw an {@link ArithmeticException} in
  * case the addition would overflow the 32 bit range.
  */
-public class IntegerSubExactNode extends IntegerSubNode implements Canonicalizable, IntegerExactArithmeticNode {
+public class IntegerSubExactNode extends IntegerSubNode implements IntegerExactArithmeticNode {
 
     public IntegerSubExactNode(ValueNode x, ValueNode y) {
         super(x, y);
@@ -50,13 +50,13 @@
     }
 
     @Override
-    public Node canonical(CanonicalizerTool tool) {
-        if (getX() == getY()) {
-            return ConstantNode.forIntegerStamp(stamp(), 0, graph());
+    public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
+        if (GraphUtil.unproxify(forX) == GraphUtil.unproxify(forY)) {
+            return ConstantNode.forIntegerStamp(stamp(), 0);
         }
-        if (getX().isConstant() && getY().isConstant()) {
-            Constant xConst = getX().asConstant();
-            Constant yConst = getY().asConstant();
+        if (forX.isConstant() && forY.isConstant()) {
+            Constant xConst = forX.asConstant();
+            Constant yConst = forY.asConstant();
             assert xConst.getKind() == yConst.getKind();
             try {
                 if (xConst.getKind() == Kind.Int) {
@@ -68,10 +68,10 @@
             } catch (ArithmeticException ex) {
                 // The operation will result in an overflow exception, so do not canonicalize.
             }
-        } else if (getY().isConstant()) {
-            long c = getY().asConstant().asLong();
+        } else if (forY.isConstant()) {
+            long c = forY.asConstant().asLong();
             if (c == 0) {
-                return getX();
+                return forX;
             }
         }
         return this;
diff -r 388b787a5fe6 -r 561070049e73 graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/nodes/arithmetic/UnsignedMulHighNode.java
--- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/nodes/arithmetic/UnsignedMulHighNode.java	Wed Jun 25 16:35:17 2014 +0200
+++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/nodes/arithmetic/UnsignedMulHighNode.java	Wed Jun 25 16:54:56 2014 +0200
@@ -22,10 +22,13 @@
  */
 package com.oracle.graal.truffle.nodes.arithmetic;
 
+import java.util.function.*;
+
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.compiler.common.*;
 import com.oracle.graal.compiler.common.type.*;
 import com.oracle.graal.graph.*;
+import com.oracle.graal.graph.spi.*;
 import com.oracle.graal.lir.gen.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.calc.*;
@@ -56,6 +59,45 @@
         }
     }
 
+    /**
+     * Determines the minimum and maximum result of this node for the given inputs and returns the
+     * result of the given BiFunction on the minimum and maximum values. Note that the minima and
+     * maxima are calculated using signed min/max functions, while the values themselves are
+     * unsigned.
+     */
+    private <T> T processExtremes(ValueNode forX, ValueNode forY, BiFunction<Long, Long, T> op) {
+        IntegerStamp xStamp = (IntegerStamp) forX.stamp();
+        IntegerStamp yStamp = (IntegerStamp) forY.stamp();
+
+        Kind kind = getKind();
+        assert kind == Kind.Int || kind == Kind.Long;
+        long[] xExtremes = {xStamp.lowerBound(), xStamp.upperBound()};
+        long[] yExtremes = {yStamp.lowerBound(), yStamp.upperBound()};
+        long min = Long.MAX_VALUE;
+        long max = Long.MIN_VALUE;
+        for (long a : xExtremes) {
+            for (long b : yExtremes) {
+                long result = kind == Kind.Int ? ExactMath.multiplyHighUnsigned((int) a, (int) b) : ExactMath.multiplyHighUnsigned(a, b);
+                min = Math.min(min, result);
+                max = Math.max(max, result);
+            }
+        }
+        return op.apply(min, max);
+    }
+
+    @SuppressWarnings("cast")
+    @Override
+    public boolean inferStamp() {
+        // if min is negative, then the value can reach into the unsigned range
+        return updateStamp(processExtremes(getX(), getY(), (min, max) -> (min == (long) max || min >= 0) ? StampFactory.forInteger(getKind(), min, max) : StampFactory.forKind(getKind())));
+    }
+
+    @SuppressWarnings("cast")
+    @Override
+    public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
+        return processExtremes(forX, forY, (min, max) -> min == (long) max ? ConstantNode.forIntegerKind(getKind(), min) : this);
+    }
+
     @Override
     public void generate(NodeMappableLIRBuilder builder, ArithmeticLIRGenerator gen) {
         Value a = builder.operand(getX());