Mercurial > hg > truffle
changeset 2899:80d27a8a022b
Fix on canonicalization plus canonicalization of shifts and integer arithmetics
line wrap: on
line diff
--- 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);
--- 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;
--- 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; } }
--- 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; + } + } }
--- 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; + } + } }
--- 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; + } + } }
--- 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; + } + } }
--- 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; + } + } }
--- 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; + } + } }
--- 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
--- 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; + } + } }
--- 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); } }
--- 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);