Mercurial > hg > truffle
changeset 5657:d71eb56d6bb0
new stamp inference in CanonicalizerPhase, IntegerStamp.mask
line wrap: on
line diff
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/CanonicalizerPhase.java Tue Jun 19 17:12:02 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/CanonicalizerPhase.java Tue Jun 19 20:03:06 2012 +0200 @@ -32,12 +32,15 @@ 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.*; public class CanonicalizerPhase extends Phase { private static final int MAX_ITERATION_PER_NODE = 10; private static final DebugMetric METRIC_CANONICALIZED_NODES = Debug.metric("CanonicalizedNodes"); private static final DebugMetric METRIC_CANONICALIZATION_CONSIDERED_NODES = Debug.metric("CanonicalizationConsideredNodes"); + private static final DebugMetric METRIC_INFER_STAMP_CALLED = Debug.metric("InferStampCalled"); + private static final DebugMetric METRIC_STAMP_CHANGED = Debug.metric("StampChanged"); private static final DebugMetric METRIC_SIMPLIFICATION_CONSIDERED_NODES = Debug.metric("SimplificationConsideredNodes"); public static final DebugMetric METRIC_GLOBAL_VALUE_NUMBERING_HITS = Debug.metric("GlobalValueNumberingHits"); @@ -129,29 +132,30 @@ graph.stopTrackingInputChange(); } - private void processNode(Node n, StructuredGraph graph) { - if (n.isAlive()) { + private void processNode(Node node, StructuredGraph graph) { + if (node.isAlive()) { METRIC_PROCESSED_NODES.increment(); - if (tryGlobalValueNumbering(n, graph)) { + if (tryGlobalValueNumbering(node, graph)) { return; } int mark = graph.getMark(); - tryCanonicalize(n, graph, tool); + tryCanonicalize(node, graph, tool); + tryInferStamp(node, graph); - for (Node node : graph.getNewNodes(mark)) { - workList.add(node); + for (Node newNode : graph.getNewNodes(mark)) { + workList.add(newNode); } } } - public static boolean tryGlobalValueNumbering(Node n, StructuredGraph graph) { - if (n.getNodeClass().valueNumberable()) { - Node newNode = graph.findDuplicate(n); + public static boolean tryGlobalValueNumbering(Node node, StructuredGraph graph) { + if (node.getNodeClass().valueNumberable()) { + Node newNode = graph.findDuplicate(node); if (newNode != null) { - assert !(n instanceof FixedNode || newNode instanceof FixedNode); - n.replaceAtUsages(newNode); - n.safeDelete(); + assert !(node instanceof FixedNode || newNode instanceof FixedNode); + node.replaceAtUsages(newNode); + node.safeDelete(); METRIC_GLOBAL_VALUE_NUMBERING_HITS.increment(); Debug.log("GVN applied and new node is %1s", newNode); return true; @@ -226,6 +230,30 @@ } } + /** + * Calls {@link ValueNode#inferStamp()} on the node and, if it returns true (which means that the stamp has + * changed), re-queues the node's usages . If the stamp has changed then this method also checks if the stamp + * now describes a constant integer value, in which case the node is replaced with a constant. + */ + private void tryInferStamp(Node node, StructuredGraph graph) { + if (node.isAlive() && node instanceof ValueNode) { + ValueNode valueNode = (ValueNode) node; + METRIC_INFER_STAMP_CALLED.increment(); + if (valueNode.inferStamp()) { + METRIC_STAMP_CHANGED.increment(); + if (valueNode.stamp() instanceof IntegerStamp && valueNode.integerStamp().lowerBound() == valueNode.integerStamp().upperBound()) { + ValueNode replacement = ConstantNode.forIntegerKind(valueNode.kind(), valueNode.integerStamp().lowerBound(), graph); + Debug.log("Canonicalizer: replacing %s with %s (inferStamp)", valueNode, replacement); + valueNode.replaceAtUsages(replacement); + } else { + for (Node usage : valueNode.usages()) { + workList.addAgain(usage); + } + } + } + } + } + private static final class Tool implements SimplifierTool { private final NodeWorkList nodeWorkSet;
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/PhiStampPhase.java Tue Jun 19 17:12:02 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/PhiStampPhase.java Tue Jun 19 20:03:06 2012 +0200 @@ -43,7 +43,7 @@ } private void iterativeInferPhi(PhiNode phi) { - if (phi.inferStamp()) { + if (phi.inferPhiStamp()) { for (PhiNode phiUsage : phi.usages().filter(PhiNode.class)) { iterativeInferPhi(phiUsage); } @@ -56,6 +56,6 @@ inferPhi(phiInput); } } - phi.inferStamp(); + phi.inferPhiStamp(); } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/PhiNode.java Tue Jun 19 17:12:02 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/PhiNode.java Tue Jun 19 20:03:06 2012 +0200 @@ -84,16 +84,19 @@ return values; } + @Override public boolean inferStamp() { - Stamp newStamp = StampFactory.meet(values()); - if (stamp().equals(newStamp)) { + if (type == PhiType.Value) { + return inferPhiStamp(); + } else { return false; - } else { - setStamp(newStamp); - return true; } } + public boolean inferPhiStamp() { + return updateStamp(StampTool.meet(values())); + } + @Override public boolean verify() { assertTrue(merge() != null, "missing merge");
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ValueNode.java Tue Jun 19 17:12:02 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ValueNode.java Tue Jun 19 20:03:06 2012 +0200 @@ -78,12 +78,39 @@ this.stamp = stamp; } + /** + * Checks if the given stamp is different than the current one ({@code newStamp.equals(oldStamp) == false}). If it + * is different then the new stamp will become the current stamp for this node. + * + * @return true if the stamp has changed, false otherwise. + */ + protected final boolean updateStamp(Stamp newStamp) { + if (newStamp.equals(stamp)) { + return false; + } else { + stamp = newStamp; + return true; + } + } + + /** + * This method can be overridden by subclasses of {@link ValueNode} if they need to recompute their stamp if their + * inputs change. A typical implementation will compute the stamp and pass it to {@link #updateStamp(Stamp)}, whose + * return value can be used as the result of this method. + * + * @return true if the stamp has changed, false otherwise. + */ + public boolean inferStamp() { + return false; + } + public Kind kind() { return stamp.kind(); } /** * Checks whether this value is a constant (i.e. it is of type {@link ConstantNode}. + * * @return {@code true} if this value is a constant */ public final boolean isConstant() { @@ -103,6 +130,7 @@ /** * Checks whether this value represents the null constant. + * * @return {@code true} if this value represents the null constant */ public final boolean isNullConstant() { @@ -111,8 +139,8 @@ /** * Convert this value to a constant if it is a constant, otherwise return null. - * @return the {@link Constant} represented by this value if it is a constant; {@code null} - * otherwise + * + * @return the {@link Constant} represented by this value if it is a constant; {@code null} otherwise */ public final Constant asConstant() { if (this instanceof ConstantNode) {
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ValueProxyNode.java Tue Jun 19 17:12:02 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ValueProxyNode.java Tue Jun 19 20:03:06 2012 +0200 @@ -22,11 +22,10 @@ */ package com.oracle.graal.nodes; -import com.oracle.graal.graph.Node; -import com.oracle.graal.graph.Node.*; +import com.oracle.graal.graph.*; +import com.oracle.graal.graph.Node.ValueNumberable; import com.oracle.graal.nodes.PhiNode.PhiType; import com.oracle.graal.nodes.calc.*; -import com.oracle.graal.nodes.type.*; /** * A value proxy that is inserted in the frame state of a loop exit for any value that is @@ -51,8 +50,8 @@ } @Override - public Stamp stamp() { - return value.stamp(); + public boolean inferStamp() { + return updateStamp(value.stamp()); } public BeginNode proxyPoint() {
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/AndNode.java Tue Jun 19 17:12:02 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/AndNode.java Tue Jun 19 20:03:06 2012 +0200 @@ -26,6 +26,7 @@ import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.type.*; @NodeInfo(shortName = "&") public final class AndNode extends LogicNode implements Canonicalizable, LIRLowerable { @@ -35,6 +36,11 @@ } @Override + public boolean inferStamp() { + return updateStamp(StampTool.and(x().integerStamp(), y().integerStamp())); + } + + @Override public ValueNode canonical(CanonicalizerTool tool) { if (x() == y()) { return x();
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/ConditionalNode.java Tue Jun 19 17:12:02 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/ConditionalNode.java Tue Jun 19 20:03:06 2012 +0200 @@ -22,6 +22,7 @@ */ package com.oracle.graal.nodes.calc; +import com.oracle.graal.api.meta.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.spi.*; @@ -53,6 +54,17 @@ @Override public ValueNode canonical(CanonicalizerTool tool) { + // this optimizes the case where a value that can only be 0 or 1 is materialized to 0 or 1 + if (x().isConstant() && y().isConstant() && condition instanceof IntegerEqualsNode) { + IntegerEqualsNode equals = (IntegerEqualsNode) condition; + if (equals.y().isConstant() && equals.y().asConstant().equals(Constant.INT_0)) { + if (equals.x().integerStamp().mask() == 1) { + if (x().asConstant().equals(Constant.INT_0) && y().asConstant().equals(Constant.INT_1)) { + return equals.x(); + } + } + } + } if (condition instanceof ConstantNode) { ConstantNode c = (ConstantNode) condition; if (c.asConstant().asBoolean()) {
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerAddNode.java Tue Jun 19 17:12:02 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerAddNode.java Tue Jun 19 20:03:06 2012 +0200 @@ -27,6 +27,7 @@ import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.spi.*; import com.oracle.graal.nodes.spi.types.*; +import com.oracle.graal.nodes.type.*; @NodeInfo(shortName = "+") public class IntegerAddNode extends IntegerArithmeticNode implements Canonicalizable, LIRLowerable, TypeFeedbackProvider { @@ -36,6 +37,11 @@ } @Override + public boolean inferStamp() { + return updateStamp(StampTool.add(x().integerStamp(), y().integerStamp())); + } + + @Override public ValueNode canonical(CanonicalizerTool tool) { if (x().isConstant() && !y().isConstant()) { return graph().unique(new IntegerAddNode(kind(), y(), x()));
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerDivNode.java Tue Jun 19 17:12:02 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerDivNode.java Tue Jun 19 20:03:06 2012 +0200 @@ -22,10 +22,12 @@ */ package com.oracle.graal.nodes.calc; +import com.oracle.graal.api.code.*; import com.oracle.graal.api.meta.*; import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.type.*; @NodeInfo(shortName = "/") public final class IntegerDivNode extends IntegerArithmeticNode implements Canonicalizable, LIRLowerable { @@ -35,6 +37,11 @@ } @Override + public boolean inferStamp() { + return updateStamp(StampTool.div(x().integerStamp(), y().integerStamp())); + } + + @Override public ValueNode canonical(CanonicalizerTool tool) { if (x().isConstant() && y().isConstant()) { long yConst = y().asConstant().asLong(); @@ -51,6 +58,8 @@ long c = y().asConstant().asLong(); if (c == 1) { return x(); + } else if (c > 0 && CodeUtil.isPowerOf2(c) && x().integerStamp().lowerBound() >= 0) { + return graph().unique(new UnsignedRightShiftNode(kind(), x(), ConstantNode.forInt(CodeUtil.log2(c), graph()))); } } return this;
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerRemNode.java Tue Jun 19 17:12:02 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerRemNode.java Tue Jun 19 20:03:06 2012 +0200 @@ -22,6 +22,7 @@ */ package com.oracle.graal.nodes.calc; +import com.oracle.graal.api.code.*; import com.oracle.graal.api.meta.*; import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; @@ -51,6 +52,8 @@ long c = y().asConstant().asLong(); if (c == 1 || c == -1) { return ConstantNode.forIntegerKind(kind(), 0, graph()); + } else if (c > 0 && CodeUtil.isPowerOf2(c) && x().integerStamp().lowerBound() >= 0) { + return graph().unique(new AndNode(kind(), x(), ConstantNode.forIntegerKind(kind(), c - 1, graph()))); } } return this;
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerSubNode.java Tue Jun 19 17:12:02 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/IntegerSubNode.java Tue Jun 19 20:03:06 2012 +0200 @@ -26,6 +26,7 @@ import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.type.*; @NodeInfo(shortName = "-") public final class IntegerSubNode extends IntegerArithmeticNode implements Canonicalizable, LIRLowerable { @@ -35,6 +36,11 @@ } @Override + public boolean inferStamp() { + return updateStamp(StampTool.sub(x().integerStamp(), y().integerStamp())); + } + + @Override public ValueNode canonical(CanonicalizerTool tool) { if (x() == y()) { return ConstantNode.forIntegerKind(kind(), 0, graph());
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/LeftShiftNode.java Tue Jun 19 17:12:02 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/LeftShiftNode.java Tue Jun 19 20:03:06 2012 +0200 @@ -26,6 +26,7 @@ import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.type.*; @NodeInfo(shortName = "<<") public final class LeftShiftNode extends ShiftNode implements Canonicalizable, LIRLowerable { @@ -35,6 +36,11 @@ } @Override + public boolean inferStamp() { + return updateStamp(StampTool.leftShift(x().integerStamp(), y().integerStamp())); + } + + @Override public ValueNode canonical(CanonicalizerTool tool) { if (y().isConstant()) { int amount = y().asConstant().asInt();
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/LogicNode.java Tue Jun 19 17:12:02 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/LogicNode.java Tue Jun 19 20:03:06 2012 +0200 @@ -38,6 +38,7 @@ */ public LogicNode(Kind kind, ValueNode x, ValueNode y) { super(kind, x, y); + assert kind == Kind.Int || kind == Kind.Long; } public static LogicNode and(ValueNode v1, ValueNode v2) {
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/NegateNode.java Tue Jun 19 17:12:02 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/NegateNode.java Tue Jun 19 20:03:06 2012 +0200 @@ -37,13 +37,18 @@ return x; } + @Override + public boolean inferStamp() { + return updateStamp(StampTool.negate(x().stamp())); + } + /** * Creates new NegateNode instance. * * @param x the instruction producing the value that is input to this instruction */ public NegateNode(ValueNode x) { - super(x.stamp() instanceof IntegerStamp ? StampFactory.negate((IntegerStamp) x.stamp()) : StampFactory.forKind(x.kind())); + super(StampTool.negate(x.stamp())); this.x = x; }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/OrNode.java Tue Jun 19 17:12:02 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/OrNode.java Tue Jun 19 20:03:06 2012 +0200 @@ -26,6 +26,7 @@ import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.type.*; @NodeInfo(shortName = "|") public final class OrNode extends LogicNode implements Canonicalizable, LIRLowerable { @@ -35,6 +36,11 @@ } @Override + public boolean inferStamp() { + return updateStamp(StampTool.or(x().integerStamp(), y().integerStamp())); + } + + @Override public ValueNode canonical(CanonicalizerTool tool) { if (x() == y()) { return x();
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/RightShiftNode.java Tue Jun 19 17:12:02 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/RightShiftNode.java Tue Jun 19 20:03:06 2012 +0200 @@ -36,6 +36,9 @@ @Override public ValueNode canonical(CanonicalizerTool tool) { + if (x().integerStamp().lowerBound() >= 0) { + return graph().unique(new UnsignedRightShiftNode(kind(), x(), y())); + } if (y().isConstant()) { int amount = y().asConstant().asInt(); int originalAmout = amount;
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/UnsignedRightShiftNode.java Tue Jun 19 17:12:02 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/UnsignedRightShiftNode.java Tue Jun 19 20:03:06 2012 +0200 @@ -26,6 +26,7 @@ import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.type.*; @NodeInfo(shortName = ">>>") public final class UnsignedRightShiftNode extends ShiftNode implements Canonicalizable, LIRLowerable { @@ -35,6 +36,11 @@ } @Override + public boolean inferStamp() { + return updateStamp(StampTool.unsignedRightShift(x().integerStamp(), y().integerStamp())); + } + + @Override public ValueNode canonical(CanonicalizerTool tool) { if (y().isConstant()) { int amount = y().asConstant().asInt();
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/IntegerStamp.java Tue Jun 19 17:12:02 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/IntegerStamp.java Tue Jun 19 20:03:06 2012 +0200 @@ -23,32 +23,56 @@ package com.oracle.graal.nodes.type; import com.oracle.graal.api.meta.*; +import com.oracle.graal.nodes.*; - +/** + * Describes the possible values of a {@link ValueNode} that produces an int or long result. + * + * The description consists of (inclusive) lower and upper bounds and a bit-mask. + */ public class IntegerStamp extends Stamp { private final long lowerBound; private final long upperBound; + private final long mask; public IntegerStamp(Kind kind) { - this(kind, kind.minValue(), kind.maxValue()); + this(kind, kind.minValue(), kind.maxValue(), defaultMask(kind)); } - public IntegerStamp(Kind kind, long lowerBound, long upperBound) { + public IntegerStamp(Kind kind, long lowerBound, long upperBound, long mask) { super(kind); assert lowerBound <= upperBound; + assert lowerBound >= kind.minValue(); + assert upperBound <= kind.maxValue(); + assert (mask & defaultMask(kind)) == mask; this.lowerBound = lowerBound; this.upperBound = upperBound; + this.mask = mask; } + /** + * The (inclusive) lower bound on the value described by this stamp. + */ public long lowerBound() { return lowerBound; } + /** + * The (inclusive) upper bound on the value described by this stamp. + */ public long upperBound() { return upperBound; } + /** + * This bit-mask describes the bits that can be set in the value described by this stamp. It is primarily used to + * represent values that are multiples of a known power of two. + */ + public long mask() { + return mask; + } + @Override public String toString() { StringBuilder str = new StringBuilder(); @@ -58,6 +82,9 @@ } else if (lowerBound != kind().minValue() || upperBound != kind().maxValue()) { str.append(" [").append(lowerBound).append(" - ").append(upperBound).append(']'); } + if (mask != defaultMask(kind())) { + str.append(" #").append(Long.toHexString(mask)); + } return str.toString(); } @@ -73,10 +100,11 @@ assert kind() == other.kind(); long meetUpperBound = Math.max(upperBound, other.upperBound); long meetLowerBound = Math.min(lowerBound, other.lowerBound); - if (meetLowerBound == lowerBound && meetUpperBound == upperBound) { + long meetMask = mask | other.mask; + if (meetLowerBound == lowerBound && meetUpperBound == upperBound && meetMask == mask) { return this; } else { - return new IntegerStamp(kind(), meetLowerBound, meetUpperBound); + return new IntegerStamp(kind(), meetLowerBound, meetUpperBound, meetMask); } } @@ -98,12 +126,27 @@ return false; } IntegerStamp other = (IntegerStamp) obj; - if (lowerBound != other.lowerBound || upperBound != other.upperBound) { + if (lowerBound != other.lowerBound || upperBound != other.upperBound || mask != other.mask) { return false; } return true; } + public static long defaultMask(Kind kind) { + if (kind == Kind.Int) { + return 0xFFFFFFFFL; + } else { + return 0xFFFFFFFFFFFFFFFFL; + } + } + + public static long maskFor(Kind kind, long lowerBound, long upperBound) { + long mask = lowerBound | upperBound; + if (mask == 0) { + return 0; + } else { + return ((-1L) >>> Long.numberOfLeadingZeros(mask)) & defaultMask(kind); + } + } } -
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/StampFactory.java Tue Jun 19 17:12:02 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/StampFactory.java Tue Jun 19 20:03:06 2012 +0200 @@ -22,8 +22,6 @@ */ package com.oracle.graal.nodes.type; -import java.util.*; - import com.oracle.graal.api.meta.*; import com.oracle.graal.graph.*; import com.oracle.graal.nodes.type.GenericStamp.GenericStampType; @@ -40,7 +38,7 @@ private static final Stamp conditionStamp = new GenericStamp(GenericStampType.Condition); private static final Stamp voidStamp = new GenericStamp(GenericStampType.Void); - private static final Stamp positiveInt = forInt(0, Integer.MAX_VALUE); + private static final Stamp positiveInt = forInteger(Kind.Int, 0, Integer.MAX_VALUE, Integer.MAX_VALUE); private static void setCache(Kind kind, Stamp stamp) { stampCache[kind.ordinal()] = stamp; @@ -96,12 +94,8 @@ return positiveInt; } - public static Stamp forInt(int lowerBound, int upperBound) { - return new IntegerStamp(Kind.Int, lowerBound, upperBound); - } - - public static Stamp forLong(long lowerBound, long upperBound) { - return new IntegerStamp(Kind.Long, lowerBound, upperBound); + public static Stamp forInteger(Kind kind, long lowerBound, long upperBound, long mask) { + return new IntegerStamp(kind, lowerBound, upperBound, mask); } public static Stamp forConstant(Constant value) { @@ -109,10 +103,8 @@ if (value.kind == Kind.Object) { throw new GraalInternalError("unexpected kind: %s", value.kind); } else { - if (value.kind == Kind.Int) { - return forInt(value.asInt(), value.asInt()); - } else if (value.kind == Kind.Long) { - return forLong(value.asLong(), value.asLong()); + if (value.kind == Kind.Int || value.kind == Kind.Long) { + return forInteger(value.kind, value.asLong(), value.asLong(), value.asLong() & IntegerStamp.defaultMask(value.kind)); } return forKind(value.kind.stackKind()); } @@ -128,14 +120,6 @@ } } - public static Stamp negate(IntegerStamp stamp) { - Kind kind = stamp.kind(); - if (stamp.lowerBound() != kind.minValue()) { - return new IntegerStamp(kind, -stamp.upperBound(), -stamp.lowerBound()); - } - return forKind(kind); - } - public static Stamp object() { return objectStamp; } @@ -166,22 +150,4 @@ public static Stamp exactNonNull(ResolvedJavaType type) { return new ObjectStamp(type, true, true); } - - public static Stamp or(Collection<? extends StampProvider> values) { - return meet(values); - } - - public static Stamp meet(Collection<? extends StampProvider> values) { - if (values.size() == 0) { - return forVoid(); - } else { - Iterator< ? extends StampProvider> iterator = values.iterator(); - Stamp stamp = iterator.next().stamp(); - - while (iterator.hasNext()) { - stamp = stamp.meet(iterator.next().stamp()); - } - return stamp; - } - } }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/StampTool.java Tue Jun 19 20:03:06 2012 +0200 @@ -0,0 +1,168 @@ +/* + * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.nodes.type; + +import java.util.*; + +import com.oracle.graal.api.meta.*; + +/** + * Helper class that is used to keep all stamp-related operations in one place. + */ +// TODO(ls) maybe move the contents into IntegerStamp +public class StampTool { + + public static Stamp negate(Stamp stamp) { + Kind kind = stamp.kind(); + if (stamp instanceof IntegerStamp) { + IntegerStamp integerStamp = (IntegerStamp) stamp; + if (integerStamp.lowerBound() != kind.minValue()) { + // TODO(ls) check if the mask calculation is correct... + return new IntegerStamp(kind, -integerStamp.upperBound(), -integerStamp.lowerBound(), IntegerStamp.defaultMask(kind) & (integerStamp.mask() | -integerStamp.mask())); + } + } + return StampFactory.forKind(kind); + } + + public static Stamp meet(Collection<? extends StampProvider> values) { + Iterator< ? extends StampProvider> iterator = values.iterator(); + if (iterator.hasNext()) { + Stamp stamp = iterator.next().stamp(); + while (iterator.hasNext()) { + stamp = stamp.meet(iterator.next().stamp()); + } + return stamp; + } else { + return StampFactory.forVoid(); + } + } + + public static Stamp add(IntegerStamp stamp1, IntegerStamp stamp2) { + Kind kind = stamp1.kind(); + assert kind == stamp2.kind(); + if (addOverflow(stamp1.lowerBound(), stamp2.lowerBound(), kind)) { + return StampFactory.forKind(kind); + } + if (addOverflow(stamp1.upperBound(), stamp2.upperBound(), kind)) { + return StampFactory.forKind(kind); + } + long lowerBound = stamp1.lowerBound() + stamp2.lowerBound(); + long upperBound = stamp1.upperBound() + stamp2.upperBound(); + long mask = IntegerStamp.maskFor(kind, lowerBound, upperBound) & (stamp1.mask() | stamp2.mask()); + + return StampFactory.forInteger(kind, lowerBound, upperBound, mask); + } + + public static Stamp sub(IntegerStamp stamp1, IntegerStamp stamp2) { + return add(stamp1, (IntegerStamp) StampTool.negate(stamp2)); + } + + public static Stamp div(IntegerStamp stamp1, IntegerStamp stamp2) { + Kind kind = stamp1.kind(); + if (stamp2.lowerBound() > 0) { + long lowerBound = stamp1.lowerBound() / stamp2.lowerBound(); + long upperBound = stamp1.upperBound() / stamp2.lowerBound(); + return StampFactory.forInteger(kind, lowerBound, upperBound, IntegerStamp.maskFor(kind, lowerBound, upperBound)); + } + return StampFactory.forKind(kind); + } + + private static boolean addOverflow(long x, long y, Kind kind) { + long result = x + y; + if (kind == Kind.Long) { + return ((x ^ result) & (y ^ result)) < 0; + } else { + assert kind == Kind.Int; + return result > Integer.MAX_VALUE || result < Integer.MIN_VALUE; + } + } + + private static final long INTEGER_SIGN_BIT = 0x80000000L; + private static final long LONG_SIGN_BIT = 0x8000000000000000L; + + private static Stamp stampForMask(Kind kind, long mask) { + long lowerBound; + long upperBound; + if (kind == Kind.Int && (mask & INTEGER_SIGN_BIT) != 0) { + // the mask is negative + lowerBound = Integer.MIN_VALUE; + upperBound = mask ^ INTEGER_SIGN_BIT; + } else if (kind == Kind.Long && (mask & LONG_SIGN_BIT) != 0) { + // the mask is negative + lowerBound = Long.MIN_VALUE; + upperBound = mask ^ LONG_SIGN_BIT; + } else { + lowerBound = 0; + upperBound = mask; + } + return StampFactory.forInteger(kind, lowerBound, upperBound, mask); + } + + public static Stamp and(IntegerStamp stamp1, IntegerStamp stamp2) { + Kind kind = stamp1.kind(); + long mask = stamp1.mask() & stamp2.mask(); + return stampForMask(kind, mask); + } + + public static Stamp or(IntegerStamp stamp1, IntegerStamp stamp2) { + Kind kind = stamp1.kind(); + long mask = stamp1.mask() | stamp2.mask(); + return stampForMask(kind, mask); + } + + public static Stamp unsignedRightShift(IntegerStamp value, IntegerStamp shift) { + Kind kind = value.kind(); + if (shift.lowerBound() == shift.upperBound()) { + long shiftMask = kind == Kind.Int ? 0x1FL : 0x3FL; + long shiftCount = shift.lowerBound() & shiftMask; + long lowerBound; + long upperBound; + if (value.lowerBound() < 0) { + lowerBound = 0; + upperBound = IntegerStamp.defaultMask(kind) >>> shiftCount; + } else { + lowerBound = value.lowerBound() >>> shiftCount; + upperBound = value.upperBound() >>> shiftCount; + } + long mask = value.mask() >>> shiftCount; + return StampFactory.forInteger(kind, lowerBound, upperBound, mask); + } + long mask = IntegerStamp.maskFor(kind, value.lowerBound(), value.upperBound()); + return stampForMask(kind, mask); + } + + public static Stamp leftShift(IntegerStamp value, IntegerStamp shift) { + Kind kind = value.kind(); + int shiftBits = kind == Kind.Int ? 5 : 6; + long shiftMask = kind == Kind.Int ? 0x1FL : 0x3FL; + if ((shift.lowerBound() >>> shiftBits) == (shift.upperBound() >>> shiftBits)) { + long mask = 0; + for (long i = shift.lowerBound() & shiftMask; i <= (shift.upperBound() & shiftMask); i++) { + mask |= value.mask() << i; + } + mask &= IntegerStamp.defaultMask(kind); + return stampForMask(kind, mask); + } + return StampFactory.forKind(kind); + } +}
--- a/graal/com.oracle.graal.tests/src/com/oracle/graal/compiler/tests/GraalCompilerTest.java Tue Jun 19 17:12:02 2012 +0200 +++ b/graal/com.oracle.graal.tests/src/com/oracle/graal/compiler/tests/GraalCompilerTest.java Tue Jun 19 20:03:06 2012 +0200 @@ -85,7 +85,16 @@ } } - private static String getCanonicalGraphString(StructuredGraph graph) { + protected void assertConstantReturn(StructuredGraph graph, int value) { + String graphString = getCanonicalGraphString(graph); + Assert.assertEquals("unexpected number of ReturnNodes: " + graphString, graph.getNodes(ReturnNode.class).count(), 1); + ValueNode result = graph.getNodes(ReturnNode.class).first().result(); + Assert.assertTrue("unexpected ReturnNode result node: " + graphString, result.isConstant()); + Assert.assertEquals("unexpected ReturnNode result kind: " + graphString, result.asConstant().kind, Kind.Int); + Assert.assertEquals("unexpected ReturnNode result: " + graphString, result.asConstant().asInt(), value); + } + + protected static String getCanonicalGraphString(StructuredGraph graph) { SchedulePhase schedule = new SchedulePhase(); schedule.apply(graph);
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.tests/src/com/oracle/graal/compiler/tests/StampCanonicalizerTest.java Tue Jun 19 20:03:06 2012 +0200 @@ -0,0 +1,104 @@ +/* + * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.compiler.tests; + +import org.junit.*; + +import com.oracle.graal.compiler.phases.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.type.*; + +/** + * This class tests some specific patterns the stamp system should be able to canonicalize away using + * {@link IntegerStamp#mask()}. + */ +public class StampCanonicalizerTest extends GraalCompilerTest { + + public static int andStamp(int a, int b) { + int v = (a & 0xffff00) & (b & 0xff0000f); + return v & 1; + } + + @Test + public void testAnd() { + testZeroReturn("andStamp"); + } + + public static int shiftLeftStamp1(int a) { + int v = a << 1; + return v & 1; + } + + public static int shiftLeftStamp2(int a) { + int v = a << 1; + if (a == 17) { + v = a * 4; + } + return v & 1; + } + + @Test + public void testShift() { + testZeroReturn("shiftLeftStamp1"); + testZeroReturn("shiftLeftStamp2"); + } + + public static int upperBoundShiftStamp1(int a) { + int v = a & 0xffff; + return (v << 4) & 0xff00000; + } + + public static int upperBoundShiftStamp2(int a) { + int v = a & 0xffff; + return (v >> 4) & 0xf000; + } + + @Test + public void testUpperBoundShift() { + testZeroReturn("upperBoundShiftStamp1"); + testZeroReturn("upperBoundShiftStamp2"); + } + + public static int divStamp1(int[] a) { + int v = a.length / 4; + return v & 0x80000000; + } + + public static int divStamp2(int[] a) { + int v = a.length / 5; + return v & 0x80000000; + } + + @Test + public void testDiv() { + testZeroReturn("divStamp1"); + testZeroReturn("divStamp2"); + } + + private void testZeroReturn(String methodName) { + StructuredGraph graph = parse(methodName); + new CanonicalizerPhase(null, runtime(), null).apply(graph); + new DeadCodeEliminationPhase().apply(graph); + assertConstantReturn(graph, 0); + } +}