# HG changeset patch
# User Gilles Duboscq <gilles.duboscq@oracle.com>
# Date 1307540591 -7200
# Node ID 80d27a8a022b1b4063368cad87b0d8b0ab00deb3
# Parent  693e4e92346b912db24d9ebe4f5ba5eb6fbda75f
Fix on canonicalization plus canonicalization of shifts and integer arithmetics

diff -r 693e4e92346b -r 80d27a8a022b graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java	Wed Jun 08 13:06:45 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java	Wed Jun 08 15:43:11 2011 +0200
@@ -84,6 +84,7 @@
 
         if (C1XOptions.OptCanonicalizer) {
             new CanonicalizerPhase().apply(graph);
+            verifyAndPrint("After Canonicalization");
         }
 
         new SplitCriticalEdgesPhase().apply(graph);
diff -r 693e4e92346b -r 80d27a8a022b graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Compare.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Compare.java	Wed Jun 08 13:06:45 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Compare.java	Wed Jun 08 15:43:11 2011 +0200
@@ -27,6 +27,13 @@
 import com.oracle.max.graal.graph.*;
 import com.sun.cri.ci.*;
 
+/* (tw/gd) For high-level optimization purpose the compare node should be a boolean *value* (it is currently only a helper node)
+ * But in the back-end the comparison should not always be materialized (for example in x86 the comparison result will not be in a register but in a flag)
+ *
+ * Compare should probably be made a value (so that it can be canonicalized for example) and in later stages some Compare usage should be transformed
+ * into variants that do not materialize the value (CompareIf, CompareGuard...)
+ *
+ */
 public final class Compare extends FloatingNode {
 
     private static final int INPUT_COUNT = 2;
diff -r 693e4e92346b -r 80d27a8a022b graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/FloatDiv.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/FloatDiv.java	Wed Jun 08 13:06:45 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/FloatDiv.java	Wed Jun 08 15:43:11 2011 +0200
@@ -51,7 +51,8 @@
 
     @Override
     public Node copy(Graph into) {
-        return new FloatDiv(kind, null, null, isStrictFP(), into);
+        FloatDiv x = new FloatDiv(kind, null, null, isStrictFP(), into);
+        return x;
     }
 
 }
diff -r 693e4e92346b -r 80d27a8a022b graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/IntegerAdd.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/IntegerAdd.java	Wed Jun 08 13:06:45 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/IntegerAdd.java	Wed Jun 08 15:43:11 2011 +0200
@@ -22,12 +22,14 @@
  */
 package com.oracle.max.graal.compiler.ir;
 
+import com.oracle.max.graal.compiler.phases.CanonicalizerPhase.*;
 import com.oracle.max.graal.graph.*;
 import com.sun.cri.bytecode.*;
 import com.sun.cri.ci.*;
 
 
 public final class IntegerAdd extends IntegerArithmetic {
+    private static final IntegerAddCanonicalizerOp CANONICALIZER = new IntegerAddCanonicalizerOp();
 
     public IntegerAdd(CiKind kind, Value x, Value y, Graph graph) {
         super(kind, kind == CiKind.Int ? Bytecodes.IADD : Bytecodes.LADD, x, y, graph);
@@ -43,4 +45,51 @@
         return "+";
     }
 
+    @SuppressWarnings("unchecked")
+    @Override
+    public <T extends Op> T lookup(Class<T> clazz) {
+        if (clazz == CanonicalizerOp.class) {
+            return (T) CANONICALIZER;
+        }
+        return super.lookup(clazz);
+    }
+
+    private static class IntegerAddCanonicalizerOp implements CanonicalizerOp {
+        @Override
+        public Node canonical(Node node) {
+            IntegerAdd add = (IntegerAdd) node;
+            Value x = add.x();
+            Value y = add.y();
+            CiKind kind = add.kind;
+            Graph graph = add.graph();
+            if (x.isConstant() && !y.isConstant()) {
+                add.swapOperands();
+                Value t = y;
+                y = x;
+                x = t;
+            }
+            if (x.isConstant()) {
+                if (kind == CiKind.Int) {
+                    return Constant.forInt(x.asConstant().asInt() + y.asConstant().asInt(), graph);
+                } else {
+                    assert kind == CiKind.Long;
+                    return Constant.forLong(x.asConstant().asLong() + y.asConstant().asLong(), graph);
+                }
+            } else if (y.isConstant()) {
+                if (kind == CiKind.Int) {
+                    int c = y.asConstant().asInt();
+                    if (c == 0) {
+                        return x;
+                    }
+                } else {
+                    assert kind == CiKind.Long;
+                    long c = y.asConstant().asLong();
+                    if (c == 0) {
+                        return x;
+                    }
+                }
+            }
+            return add;
+        }
+    }
 }
diff -r 693e4e92346b -r 80d27a8a022b graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/IntegerDiv.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/IntegerDiv.java	Wed Jun 08 13:06:45 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/IntegerDiv.java	Wed Jun 08 15:43:11 2011 +0200
@@ -22,12 +22,14 @@
  */
 package com.oracle.max.graal.compiler.ir;
 
+import com.oracle.max.graal.compiler.phases.CanonicalizerPhase.*;
 import com.oracle.max.graal.graph.*;
 import com.sun.cri.bytecode.*;
 import com.sun.cri.ci.*;
 
 
 public final class IntegerDiv extends IntegerArithmetic {
+    private static final IntegerDivCanonicalizerOp CANONICALIZER = new IntegerDivCanonicalizerOp();
 
     public IntegerDiv(CiKind kind, Value x, Value y, Graph graph) {
         super(kind, kind == CiKind.Int ? Bytecodes.IDIV : Bytecodes.LDIV, x, y, graph);
@@ -43,4 +45,41 @@
         return new IntegerDiv(kind, null, null, into);
     }
 
+    @SuppressWarnings("unchecked")
+    @Override
+    public <T extends Op> T lookup(Class<T> clazz) {
+        if (clazz == CanonicalizerOp.class) {
+            return (T) CANONICALIZER;
+        }
+        return super.lookup(clazz);
+    }
+
+    private static class IntegerDivCanonicalizerOp implements CanonicalizerOp {
+        @Override
+        public Node canonical(Node node) {
+            IntegerDiv div = (IntegerDiv) node;
+            Value x = div.x();
+            Value y = div.y();
+            CiKind kind = div.kind;
+            Graph graph = div.graph();
+            if (x.isConstant() && y.isConstant()) {
+                long yConst = y.asConstant().asLong();
+                if (yConst == 0) {
+                    return div; // this will trap, can not canonicalize
+                }
+                if (kind == CiKind.Int) {
+                    return Constant.forInt(x.asConstant().asInt() / (int) yConst, graph);
+                } else {
+                    assert kind == CiKind.Long;
+                    return Constant.forLong(x.asConstant().asLong() / yConst, graph);
+                }
+            } else if (y.isConstant()) {
+                long c = y.asConstant().asLong();
+                if (c == 1) {
+                    return x;
+                }
+            }
+            return div;
+        }
+    }
 }
diff -r 693e4e92346b -r 80d27a8a022b graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/IntegerMul.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/IntegerMul.java	Wed Jun 08 13:06:45 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/IntegerMul.java	Wed Jun 08 15:43:11 2011 +0200
@@ -22,12 +22,14 @@
  */
 package com.oracle.max.graal.compiler.ir;
 
+import com.oracle.max.graal.compiler.phases.CanonicalizerPhase.*;
 import com.oracle.max.graal.graph.*;
 import com.sun.cri.bytecode.*;
 import com.sun.cri.ci.*;
 
 
 public final class IntegerMul extends IntegerArithmetic {
+    private static final IntegerMulCanonicalizerOp CANONICALIZER = new IntegerMulCanonicalizerOp();
 
     public IntegerMul(CiKind kind, Value x, Value y, Graph graph) {
         super(kind, kind == CiKind.Int ? Bytecodes.IMUL : Bytecodes.LMUL, x, y, graph);
@@ -43,4 +45,49 @@
         return new IntegerMul(kind, null, null, into);
     }
 
+    @SuppressWarnings("unchecked")
+    @Override
+    public <T extends Op> T lookup(Class<T> clazz) {
+        if (clazz == CanonicalizerOp.class) {
+            return (T) CANONICALIZER;
+        }
+        return super.lookup(clazz);
+    }
+
+    private static class IntegerMulCanonicalizerOp implements CanonicalizerOp {
+        @Override
+        public Node canonical(Node node) {
+            IntegerMul mul = (IntegerMul) node;
+            Value x = mul.x();
+            Value y = mul.y();
+            CiKind kind = mul.kind;
+            Graph graph = mul.graph();
+            if (x.isConstant() && !y.isConstant()) {
+                mul.swapOperands();
+                Value t = y;
+                y = x;
+                x = t;
+            }
+            if (x.isConstant()) {
+                if (kind == CiKind.Int) {
+                    return Constant.forInt(x.asConstant().asInt() * y.asConstant().asInt(), graph);
+                } else {
+                    assert kind == CiKind.Long;
+                    return Constant.forLong(x.asConstant().asLong() * y.asConstant().asLong(), graph);
+                }
+            } else if (y.isConstant()) {
+                long c = y.asConstant().asLong();
+                if (c == 1) {
+                    return x;
+                }
+                if (c == 0) {
+                    return Constant.forInt(0, graph);
+                }
+                if (c > 0 && CiUtil.isPowerOf2(c)) {
+                    return new LeftShift(kind, x, Constant.forInt(CiUtil.log2(c), graph), graph);
+                }
+            }
+            return mul;
+        }
+    }
 }
diff -r 693e4e92346b -r 80d27a8a022b graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/IntegerSub.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/IntegerSub.java	Wed Jun 08 13:06:45 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/IntegerSub.java	Wed Jun 08 15:43:11 2011 +0200
@@ -22,12 +22,14 @@
  */
 package com.oracle.max.graal.compiler.ir;
 
+import com.oracle.max.graal.compiler.phases.CanonicalizerPhase.*;
 import com.oracle.max.graal.graph.*;
 import com.sun.cri.bytecode.*;
 import com.sun.cri.ci.*;
 
 
 public final class IntegerSub extends IntegerArithmetic {
+    private static final IntegerSubCanonicalizerOp CANONICALIZER = new IntegerSubCanonicalizerOp();
 
     public IntegerSub(CiKind kind, Value x, Value y, Graph graph) {
         super(kind, kind == CiKind.Int ? Bytecodes.ISUB : Bytecodes.LSUB, x, y, graph);
@@ -42,4 +44,59 @@
     public String shortName() {
         return "-";
     }
+
+    @SuppressWarnings("unchecked")
+    @Override
+    public <T extends Op> T lookup(Class<T> clazz) {
+        if (clazz == CanonicalizerOp.class) {
+            return (T) CANONICALIZER;
+        }
+        return super.lookup(clazz);
+    }
+
+    private static class IntegerSubCanonicalizerOp implements CanonicalizerOp {
+        @Override
+        public Node canonical(Node node) {
+            IntegerSub sub = (IntegerSub) node;
+            Value x = sub.x();
+            Value y = sub.y();
+            CiKind kind = sub.kind;
+            Graph graph = sub.graph();
+            if (x == y) {
+                if (kind == CiKind.Int) {
+                    return Constant.forInt(0, graph);
+                } else {
+                    assert kind == CiKind.Long;
+                    return Constant.forLong(0, graph);
+                }
+            }
+            if (x.isConstant() && y.isConstant()) {
+                if (kind == CiKind.Int) {
+                    return Constant.forInt(x.asConstant().asInt() - y.asConstant().asInt(), graph);
+                } else {
+                    assert kind == CiKind.Long;
+                    return Constant.forLong(x.asConstant().asLong() - y.asConstant().asLong(), graph);
+                }
+            } else if (y.isConstant()) {
+                if (kind == CiKind.Int) {
+                    int c = y.asConstant().asInt();
+                    if (c == 0) {
+                        return x;
+                    }
+                } else {
+                    assert kind == CiKind.Long;
+                    long c = y.asConstant().asLong();
+                    if (c == 0) {
+                        return x;
+                    }
+                }
+            } else if (x.isConstant()) {
+                long c = x.asConstant().asLong();
+                if (c == 0) {
+                    return new Negate(y, graph);
+                }
+            }
+            return sub;
+        }
+    }
 }
diff -r 693e4e92346b -r 80d27a8a022b graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LeftShift.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LeftShift.java	Wed Jun 08 13:06:45 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LeftShift.java	Wed Jun 08 15:43:11 2011 +0200
@@ -22,20 +22,15 @@
  */
 package com.oracle.max.graal.compiler.ir;
 
+import com.oracle.max.graal.compiler.phases.CanonicalizerPhase.CanonicalizerOp;
 import com.oracle.max.graal.graph.*;
 import com.sun.cri.bytecode.*;
 import com.sun.cri.ci.*;
 
 
 public final class LeftShift extends Shift {
+    private static final LeftShiftCanonicalizerOp CANONICALIZER = new LeftShiftCanonicalizerOp();
 
-    /**
-     * @param opcode
-     * @param kind
-     * @param x
-     * @param y
-     * @param graph
-     */
     public LeftShift(CiKind kind, Value x, Value y, Graph graph) {
         super(kind, kind == CiKind.Int ? Bytecodes.ISHL : Bytecodes.LSHL, x, y, graph);
     }
@@ -51,4 +46,70 @@
         return ls;
     }
 
+    @SuppressWarnings("unchecked")
+    @Override
+    public <T extends Op> T lookup(Class<T> clazz) {
+        if (clazz == CanonicalizerOp.class) {
+            return (T) CANONICALIZER;
+        }
+        return super.lookup(clazz);
+    }
+
+    private static class LeftShiftCanonicalizerOp implements CanonicalizerOp {
+        @Override
+        public Node canonical(Node node) {
+            LeftShift leftShift = (LeftShift) node;
+            CiKind kind = leftShift.kind;
+            Graph graph = leftShift.graph();
+            Value value = leftShift.x();
+            Value y = leftShift.y();
+            if (y.isConstant()) {
+                int amount = y.asConstant().asInt();
+                int originalAmout = amount;
+                int mask;
+                if (kind == CiKind.Int) {
+                    mask = 0x1f;
+                } else {
+                    assert kind == CiKind.Long;
+                    mask = 0x3f;
+                }
+                amount &= mask;
+                if (value.isConstant()) {
+                    if (kind == CiKind.Int) {
+                        return Constant.forInt(value.asConstant().asInt() << amount, graph);
+                    } else {
+                        assert kind == CiKind.Long;
+                        return Constant.forLong(value.asConstant().asLong() << amount, graph);
+                    }
+                }
+                if (amount == 0) {
+                    return value;
+                }
+                if (value instanceof Shift) {
+                    Shift other = (Shift) value;
+                    if (other.y().isConstant()) {
+                        int otherAmount = other.y().asConstant().asInt() & mask;
+                        if (other instanceof LeftShift) {
+                            int total = amount + otherAmount;
+                            if (total != (total & mask)) {
+                                return Constant.forInt(0, graph);
+                            }
+                            return new LeftShift(kind, other.x(), Constant.forInt(total, graph), graph);
+                        } else if ((other instanceof RightShift || other instanceof UnsignedRightShift) && otherAmount == amount) {
+                            if (kind == CiKind.Long) {
+                                return new And(kind, other.x(), Constant.forLong(-1L << amount, graph), graph);
+                            } else {
+                                assert kind == CiKind.Int;
+                                return new And(kind, other.x(), Constant.forInt(-1 << amount, graph), graph);
+                            }
+                        }
+                    }
+                }
+                if (originalAmout != amount) {
+                    return new LeftShift(kind, value, Constant.forInt(amount, graph), graph);
+                }
+            }
+            return leftShift;
+        }
+    }
 }
diff -r 693e4e92346b -r 80d27a8a022b graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/RightShift.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/RightShift.java	Wed Jun 08 13:06:45 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/RightShift.java	Wed Jun 08 15:43:11 2011 +0200
@@ -22,20 +22,15 @@
  */
 package com.oracle.max.graal.compiler.ir;
 
+import com.oracle.max.graal.compiler.phases.CanonicalizerPhase.*;
 import com.oracle.max.graal.graph.*;
 import com.sun.cri.bytecode.*;
 import com.sun.cri.ci.*;
 
 
 public final class RightShift extends Shift {
+    private static final RighShiftCanonicalizerOp CANONICALIZER = new RighShiftCanonicalizerOp();
 
-    /**
-     * @param opcode
-     * @param kind
-     * @param x
-     * @param y
-     * @param graph
-     */
     public RightShift(CiKind kind, Value x, Value y, Graph graph) {
         super(kind, kind == CiKind.Int ? Bytecodes.ISHR : Bytecodes.LSHR, x, y, graph);
     }
@@ -51,4 +46,63 @@
         return rs;
     }
 
+    @SuppressWarnings("unchecked")
+    @Override
+    public <T extends Op> T lookup(Class<T> clazz) {
+        if (clazz == CanonicalizerOp.class) {
+            return (T) CANONICALIZER;
+        }
+        return super.lookup(clazz);
+    }
+
+    private static class RighShiftCanonicalizerOp implements CanonicalizerOp {
+        @Override
+        public Node canonical(Node node) {
+            RightShift rightShift = (RightShift) node;
+            CiKind kind = rightShift.kind;
+            Graph graph = rightShift.graph();
+            Value value = rightShift.x();
+            Value y = rightShift.y();
+            if (y.isConstant()) {
+                int amount = y.asConstant().asInt();
+                int originalAmout = amount;
+                int mask;
+                if (kind == CiKind.Int) {
+                    mask = 0x1f;
+                } else {
+                    assert kind == CiKind.Long;
+                    mask = 0x3f;
+                }
+                amount &= mask;
+                if (value.isConstant()) {
+                    if (kind == CiKind.Int) {
+                        return Constant.forInt(value.asConstant().asInt() >> amount, graph);
+                    } else {
+                        assert kind == CiKind.Long;
+                        return Constant.forLong(value.asConstant().asLong() >> amount, graph);
+                    }
+                }
+                if (amount == 0) {
+                    return value;
+                }
+                if (value instanceof Shift) {
+                    Shift other = (Shift) value;
+                    if (other.y().isConstant()) {
+                        int otherAmount = other.y().asConstant().asInt() & mask;
+                        if (other instanceof RightShift) {
+                            int total = amount + otherAmount;
+                            if (total != (total & mask)) {
+                                return Constant.forInt(0, graph);
+                            }
+                            return new RightShift(kind, other.x(), Constant.forInt(total, graph), graph);
+                        }
+                    }
+                }
+                if (originalAmout != amount) {
+                    return new RightShift(kind, value, Constant.forInt(amount, graph), graph);
+                }
+            }
+            return rightShift;
+        }
+    }
 }
diff -r 693e4e92346b -r 80d27a8a022b graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Shift.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Shift.java	Wed Jun 08 13:06:45 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Shift.java	Wed Jun 08 15:43:11 2011 +0200
@@ -38,10 +38,11 @@
      * Creates a new shift operation.
      * @param opcode the opcode of the shift
      * @param x the first input value
-     * @param y the second input value
+     * @param s the second input value
      */
-    public Shift(CiKind kind, int opcode, Value x, Value y, Graph graph) {
-        super(kind, opcode, x, y, INPUT_COUNT, SUCCESSOR_COUNT, graph);
+    public Shift(CiKind kind, int opcode, Value x, Value s, Graph graph) {
+        super(kind, opcode, x, s, INPUT_COUNT, SUCCESSOR_COUNT, graph);
+        assert x == null || x.kind == kind;
     }
 
     @Override
diff -r 693e4e92346b -r 80d27a8a022b graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/UnsignedRightShift.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/UnsignedRightShift.java	Wed Jun 08 13:06:45 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/UnsignedRightShift.java	Wed Jun 08 15:43:11 2011 +0200
@@ -22,20 +22,15 @@
  */
 package com.oracle.max.graal.compiler.ir;
 
+import com.oracle.max.graal.compiler.phases.CanonicalizerPhase.*;
 import com.oracle.max.graal.graph.*;
 import com.sun.cri.bytecode.*;
 import com.sun.cri.ci.*;
 
 
 public final class UnsignedRightShift extends Shift {
+    private static final UnsignedRightShiftCanonicalizerOp CANONICALIZER = new UnsignedRightShiftCanonicalizerOp();
 
-    /**
-     * @param opcode
-     * @param kind
-     * @param x
-     * @param y
-     * @param graph
-     */
     public UnsignedRightShift(CiKind kind, Value x, Value y, Graph graph) {
         super(kind, kind == CiKind.Int ? Bytecodes.IUSHR : Bytecodes.LUSHR, x, y, graph);
     }
@@ -51,4 +46,70 @@
         return x;
     }
 
+    @SuppressWarnings("unchecked")
+    @Override
+    public <T extends Op> T lookup(Class<T> clazz) {
+        if (clazz == CanonicalizerOp.class) {
+            return (T) CANONICALIZER;
+        }
+        return super.lookup(clazz);
+    }
+
+    private static class UnsignedRightShiftCanonicalizerOp implements CanonicalizerOp {
+        @Override
+        public Node canonical(Node node) {
+            UnsignedRightShift ushr = (UnsignedRightShift) node;
+            CiKind kind = ushr.kind;
+            Graph graph = ushr.graph();
+            Value value = ushr.x();
+            Value y = ushr.y();
+            if (y.isConstant()) {
+                int amount = y.asConstant().asInt();
+                int originalAmout = amount;
+                int mask;
+                if (kind == CiKind.Int) {
+                    mask = 0x1f;
+                } else {
+                    assert kind == CiKind.Long;
+                    mask = 0x3f;
+                }
+                amount &= mask;
+                if (value.isConstant()) {
+                    if (kind == CiKind.Int) {
+                        return Constant.forInt(value.asConstant().asInt() >>> amount, graph);
+                    } else {
+                        assert kind == CiKind.Long;
+                        return Constant.forLong(value.asConstant().asLong() >>> amount, graph);
+                    }
+                }
+                if (amount == 0) {
+                    return value;
+                }
+                if (value instanceof Shift) {
+                    Shift other = (Shift) value;
+                    if (other.y().isConstant()) {
+                        int otherAmount = other.y().asConstant().asInt() & mask;
+                        if (other instanceof UnsignedRightShift) {
+                            int total = amount + otherAmount;
+                            if (total != (total & mask)) {
+                                return Constant.forInt(0, graph);
+                            }
+                            return new UnsignedRightShift(kind, other.x(), Constant.forInt(total, graph), graph);
+                        } else if (other instanceof LeftShift && otherAmount == amount) {
+                            if (kind == CiKind.Long) {
+                                return new And(kind, other.x(), Constant.forLong(-1L >>> amount, graph), graph);
+                            } else {
+                                assert kind == CiKind.Int;
+                                return new And(kind, other.x(), Constant.forInt(-1 >>> amount, graph), graph);
+                            }
+                        }
+                    }
+                }
+                if (originalAmout != amount) {
+                    return new UnsignedRightShift(kind, value, Constant.forInt(amount, graph), graph);
+                }
+            }
+            return ushr;
+        }
+    }
 }
diff -r 693e4e92346b -r 80d27a8a022b graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/CanonicalizerPhase.java
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/CanonicalizerPhase.java	Wed Jun 08 13:06:45 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/CanonicalizerPhase.java	Wed Jun 08 15:43:11 2011 +0200
@@ -38,7 +38,7 @@
             if (n == null) {
                 continue;
             }
-            if (!visited.isMarked(n)) {
+            if (!n.isDeleted() && !visited.isMarked(n)) {
                 this.canonicalize(n, visited);
             }
         }
diff -r 693e4e92346b -r 80d27a8a022b graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Node.java
--- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Node.java	Wed Jun 08 13:06:45 2011 +0200
+++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Node.java	Wed Jun 08 15:43:11 2011 +0200
@@ -115,7 +115,7 @@
     public boolean isDeleted() {
         return id == DeletedID;
     }
-    
+
     public void forceDelete() {
         for (Node n : usages) {
             n.inputs.silentRemove(this);