Mercurial > hg > truffle
changeset 5083:1093243c09ad
experimental type storage/query infrastructure, part 3:
split/conditional type feedback, type canonicalization
line wrap: on
line diff
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java Wed Mar 14 17:46:39 2012 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java Wed Mar 14 17:50:59 2012 +0100 @@ -26,13 +26,14 @@ import com.oracle.max.cri.ci.*; import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.spi.types.*; import com.oracle.graal.nodes.type.*; /** * The {@code IfNode} represents a branch that can go one of two directions depending on the outcome of a * comparison. */ -public final class IfNode extends ControlSplitNode implements Simplifiable, LIRLowerable { +public final class IfNode extends ControlSplitNode implements Simplifiable, LIRLowerable, SplitTypeFeedbackProvider { public static final int TRUE_EDGE = 0; public static final int FALSE_EDGE = 1; @@ -176,4 +177,11 @@ falseEnd.safeDelete(); tool.addToWorkList(next); } + + @Override + public void typeFeedback(int blockSuccessor, TypeFeedbackTool tool) { + if (compare instanceof ConditionalTypeFeedbackProvider) { + ((ConditionalTypeFeedbackProvider) compare).typeFeedback(blockSuccessor == TRUE_EDGE ? tool : tool.negate()); + } + } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/CompareNode.java Wed Mar 14 17:46:39 2012 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/CompareNode.java Wed Mar 14 17:50:59 2012 +0100 @@ -26,6 +26,7 @@ import com.oracle.max.cri.ri.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.spi.types.*; import com.oracle.graal.nodes.type.*; /* TODO (thomaswue/gdub) For high-level optimization purpose the compare node should be a boolean *value* (it is currently only a helper node) @@ -34,7 +35,7 @@ * 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 CompareNode extends BooleanNode implements Canonicalizable, LIRLowerable { +public final class CompareNode extends BooleanNode implements Canonicalizable, LIRLowerable, ConditionalTypeFeedbackProvider, TypeCanonicalizable { @Input private ValueNode x; @Input private ValueNode y; @@ -197,4 +198,108 @@ } return this; } + + @Override + public void typeFeedback(TypeFeedbackTool tool) { + CiKind kind = x().kind(); + assert y().kind() == kind; + if (kind == CiKind.Object) { + assert condition == Condition.EQ || condition == Condition.NE; + if (y().isConstant() && !x().isConstant()) { + tool.addObject(x()).constantBound(condition, y().asConstant()); + } else if (x().isConstant() && !y().isConstant()) { + tool.addObject(y()).constantBound(condition.mirror(), x().asConstant()); + } else if (!x().isConstant() && !y.isConstant()) { + tool.addObject(x()).valueBound(condition, y()); + tool.addObject(y()).valueBound(condition.mirror(), x()); + } else { + // both are constant, this should be canonicalized... + } + } else if (kind == CiKind.Int || kind == CiKind.Long) { + assert condition != Condition.NOF && condition != Condition.OF; + if (y().isConstant() && !x().isConstant()) { + tool.addScalar(x()).constantBound(condition, y().asConstant()); + } else if (x().isConstant() && !y().isConstant()) { + tool.addScalar(y()).constantBound(condition.mirror(), x().asConstant()); + } else if (!x().isConstant() && !y.isConstant()) { + tool.addScalar(x()).valueBound(condition, y(), tool.queryScalar(y())); + tool.addScalar(y()).valueBound(condition.mirror(), x(), tool.queryScalar(x())); + } else { + // both are constant, this should be canonicalized... + } + } else if (kind == CiKind.Float || kind == CiKind.Double) { + // nothing yet... + } + } + + @Override + public Result canonical(TypeFeedbackTool tool) { + CiKind kind = x().kind(); + if (kind == CiKind.Int || kind == CiKind.Long) { + assert condition != Condition.NOF && condition != Condition.OF; + ScalarTypeQuery queryX = tool.queryScalar(x()); + if (y().isConstant() && !x().isConstant()) { + if (queryX.constantBound(condition, y().asConstant())) { + return new Result(ConstantNode.forBoolean(true, graph()), queryX); + } else if (queryX.constantBound(condition.negate(), y().asConstant())) { + return new Result(ConstantNode.forBoolean(false, graph()), queryX); + } + } else { + ScalarTypeQuery queryY = tool.queryScalar(y()); + if (x().isConstant() && !y().isConstant()) { + if (queryY.constantBound(condition.mirror(), x().asConstant())) { + return new Result(ConstantNode.forBoolean(true, graph()), queryY); + } else if (queryY.constantBound(condition.mirror().negate(), x().asConstant())) { + return new Result(ConstantNode.forBoolean(false, graph()), queryY); + } + } else if (!x().isConstant() && !y.isConstant()) { + if (condition == Condition.BT || condition == Condition.BE) { + if (queryY.constantBound(Condition.GE, new CiConstant(kind, 0))) { + if (queryX.constantBound(Condition.GE, new CiConstant(kind, 0))) { + if (queryX.valueBound(condition == Condition.BT ? Condition.LT : Condition.LE, y())) { + return new Result(ConstantNode.forBoolean(true, graph()), queryX, queryY); + } + } + } + } + + if (queryX.valueBound(condition, y())) { + return new Result(ConstantNode.forBoolean(true, graph()), queryX); + } else if (queryX.valueBound(condition.negate(), y())) { + return new Result(ConstantNode.forBoolean(false, graph()), queryX); + } + } else { + // both are constant, this should be canonicalized... + } + } + } else if (kind == CiKind.Object) { + assert condition == Condition.EQ || condition == Condition.NE; + ObjectTypeQuery queryX = tool.queryObject(x()); + if (y().isConstant() && !x().isConstant()) { + if (queryX.constantBound(condition, y().asConstant())) { + return new Result(ConstantNode.forBoolean(true, graph()), queryX); + } else if (queryX.constantBound(condition.negate(), y().asConstant())) { + return new Result(ConstantNode.forBoolean(false, graph()), queryX); + } + } else { + ObjectTypeQuery queryY = tool.queryObject(y()); + if (x().isConstant() && !y().isConstant()) { + if (queryY.constantBound(condition.mirror(), x().asConstant())) { + return new Result(ConstantNode.forBoolean(true, graph()), queryY); + } else if (queryY.constantBound(condition.mirror().negate(), x().asConstant())) { + return new Result(ConstantNode.forBoolean(false, graph()), queryY); + } + } else if (!x().isConstant() && !y.isConstant()) { + if (queryX.valueBound(condition, y())) { + return new Result(ConstantNode.forBoolean(true, graph()), queryX); + } else if (queryX.valueBound(condition.negate(), y())) { + return new Result(ConstantNode.forBoolean(false, graph()), queryX); + } + } else { + // both are constant, this should be canonicalized... + } + } + } + return null; + } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/NullCheckNode.java Wed Mar 14 17:46:39 2012 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/NullCheckNode.java Wed Mar 14 17:50:59 2012 +0100 @@ -25,9 +25,10 @@ import com.oracle.max.cri.ci.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.spi.types.*; import com.oracle.graal.nodes.type.*; -public final class NullCheckNode extends BooleanNode implements Canonicalizable, LIRLowerable { +public final class NullCheckNode extends BooleanNode implements Canonicalizable, LIRLowerable, ConditionalTypeFeedbackProvider, TypeCanonicalizable { @Input private ValueNode object; @Data public final boolean expectedNull; @@ -77,4 +78,22 @@ public BooleanNode negate() { return graph().unique(new NullCheckNode(object(), !expectedNull)); } + + @Override + public void typeFeedback(TypeFeedbackTool tool) { + Condition expectedCondition = expectedNull ? Condition.EQ : Condition.NE; + tool.addObject(object()).constantBound(expectedCondition, CiConstant.NULL_OBJECT); + } + + @Override + public Result canonical(TypeFeedbackTool tool) { + Condition expectedCondition = expectedNull ? Condition.EQ : Condition.NE; + ObjectTypeQuery query = tool.queryObject(object()); + if (query.constantBound(expectedCondition, CiConstant.NULL_OBJECT)) { + return new Result(ConstantNode.forBoolean(true, graph()), query); + } else if (query.constantBound(expectedCondition.negate(), CiConstant.NULL_OBJECT)) { + return new Result(ConstantNode.forBoolean(false, graph()), query); + } + return null; + } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/CheckCastNode.java Wed Mar 14 17:46:39 2012 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/CheckCastNode.java Wed Mar 14 17:50:59 2012 +0100 @@ -22,20 +22,22 @@ */ package com.oracle.graal.nodes.java; -import com.oracle.max.cri.ci.*; -import com.oracle.max.cri.ri.*; import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.*; import com.oracle.graal.nodes.extended.*; import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.spi.types.*; import com.oracle.graal.nodes.type.*; +import com.oracle.max.cri.ci.*; +import com.oracle.max.cri.ri.*; /** * The {@code CheckCastNode} represents a {@link Bytecodes#CHECKCAST}. * * The {@link #targetClass()} of a CheckCastNode can be null for array store checks! */ -public final class CheckCastNode extends TypeCheckNode implements Canonicalizable, LIRLowerable, Node.IterableNodeType { +public final class CheckCastNode extends TypeCheckNode implements Canonicalizable, LIRLowerable, Node.IterableNodeType, TypeFeedbackProvider, TypeCanonicalizable { @Input protected final FixedNode anchor; @Data protected final boolean emitCode; @@ -116,4 +118,24 @@ public BooleanNode negate() { throw new Error("A CheckCast does not produce a boolean value, so it should actually not be a subclass of BooleanNode"); } + + @Override + public void typeFeedback(TypeFeedbackTool tool) { + if (targetClass() != null) { + tool.addObject(object()).declaredType(targetClass(), false); + } + } + + @Override + public Result canonical(TypeFeedbackTool tool) { + ObjectTypeQuery query = tool.queryObject(object()); + if (query.constantBound(Condition.EQ, CiConstant.NULL_OBJECT)) { + return new Result(object(), query); + } else if (targetClass() != null) { + if (query.declaredType(targetClass())) { + return new Result(object(), query); + } + } + return null; + } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/InstanceOfNode.java Wed Mar 14 17:46:39 2012 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/InstanceOfNode.java Wed Mar 14 17:50:59 2012 +0100 @@ -27,12 +27,13 @@ import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.calc.*; import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.spi.types.*; import com.oracle.graal.nodes.type.*; /** * The {@code InstanceOfNode} represents an instanceof test. */ -public final class InstanceOfNode extends TypeCheckNode implements Canonicalizable, LIRLowerable { +public final class InstanceOfNode extends TypeCheckNode implements Canonicalizable, LIRLowerable, ConditionalTypeFeedbackProvider, TypeCanonicalizable { @Data private final boolean negated; @@ -97,4 +98,31 @@ public BooleanNode negate() { return graph().unique(new InstanceOfNode(targetClassInstruction(), targetClass(), object(), hints(), hintsExact(), !negated)); } + + @Override + public void typeFeedback(TypeFeedbackTool tool) { + if (negated) { + tool.addObject(object()).notDeclaredType(targetClass(), true); + } else { + tool.addObject(object()).declaredType(targetClass(), true); + } + } + + @Override + public Result canonical(TypeFeedbackTool tool) { + ObjectTypeQuery query = tool.queryObject(object()); + if (query.constantBound(Condition.EQ, CiConstant.NULL_OBJECT)) { + return new Result(ConstantNode.forBoolean(negated, graph()), query); + } else if (targetClass() != null) { + if (query.notDeclaredType(targetClass())) { + return new Result(ConstantNode.forBoolean(negated, graph()), query); + } + if (query.constantBound(Condition.NE, CiConstant.NULL_OBJECT)) { + if (query.declaredType(targetClass())) { + return new Result(ConstantNode.forBoolean(!negated, graph()), query); + } + } + } + return null; + } }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/ConditionalTypeFeedbackProvider.java Wed Mar 14 17:50:59 2012 +0100 @@ -0,0 +1,28 @@ +/* + * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.nodes.spi.types; + +public interface ConditionalTypeFeedbackProvider { + + void typeFeedback(TypeFeedbackTool tool); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/SplitTypeFeedbackProvider.java Wed Mar 14 17:50:59 2012 +0100 @@ -0,0 +1,28 @@ +/* + * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.nodes.spi.types; + +public interface SplitTypeFeedbackProvider { + + void typeFeedback(int blockSuccessor, TypeFeedbackTool tool); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/TypeCanonicalizable.java Wed Mar 14 17:50:59 2012 +0100 @@ -0,0 +1,79 @@ +/* + * Copyright (c) 2012, 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.spi.types; + +import java.util.*; + +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.*; + +public interface TypeCanonicalizable { + + Node[] EMPTY_ARRAY = new Node[0]; + + public static class Result { + public final ValueNode replacement; + public final Node[] dependencies; + + public Result(ValueNode replacement) { + this.replacement = replacement; + this.dependencies = EMPTY_ARRAY; + } + + public Result(ValueNode replacement, TypeQuery query) { + assert query != null; + this.replacement = replacement; + if (query.dependency() != null) { + this.dependencies = new Node[] {query.dependency()}; + } else { + this.dependencies = EMPTY_ARRAY; + } + } + + public Result(ValueNode replacement, TypeQuery... queries) { + this.replacement = replacement; + HashSet<Node> deps = new HashSet<>(); + for (TypeQuery query : queries) { + if (query.dependency() != null) { + deps.add(query.dependency()); + } + } + this.dependencies = deps.toArray(new Node[deps.size()]); + } + + @Override + public String toString() { + StringBuilder str = new StringBuilder().append('['); + str.append(replacement); + if (dependencies.length > 0) { + str.append(" @"); + for (Node dep : dependencies) { + str.append(' ').append(dep); + } + } + return str.append(']').toString(); + } + } + + Result canonical(TypeFeedbackTool tool); +}
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/TypeFeedbackTool.java Wed Mar 14 17:46:39 2012 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/types/TypeFeedbackTool.java Wed Mar 14 17:50:59 2012 +0100 @@ -23,7 +23,6 @@ package com.oracle.graal.nodes.spi.types; import com.oracle.max.cri.ri.*; -import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; public interface TypeFeedbackTool {