Mercurial > hg > graal-compiler
changeset 11409:1f302b6e16b0
Introduce LogicNegationNode and remove Negatable interface.
line wrap: on
line diff
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ConditionalEliminationTest.java Sat Aug 24 14:32:57 2013 +0200 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ConditionalEliminationTest.java Sat Aug 24 14:38:11 2013 +0200 @@ -169,8 +169,8 @@ IsNullNode x = graph.unique(new IsNullNode(graph.getLocal(0))); InstanceOfNode y = instanceOf; ShortCircuitOrNode disjunction = graph.unique(new ShortCircuitOrNode(x, false, y, false, NOT_FREQUENT_PROBABILITY)); - ifNode.setCondition(disjunction); - ifNode.negate(disjunction); + LogicNegationNode negation = graph.unique(new LogicNegationNode(disjunction)); + ifNode.setCondition(negation); new CanonicalizerPhase.Instance(runtime(), null, true).apply(graph); new ConditionalEliminationPhase(runtime()).apply(graph); new CanonicalizerPhase.Instance(runtime(), null, true).apply(graph);
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/FixedGuardNode.java Sat Aug 24 14:32:57 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/FixedGuardNode.java Sat Aug 24 14:38:11 2013 +0200 @@ -31,7 +31,7 @@ import com.oracle.graal.nodes.util.*; @NodeInfo(nameTemplate = "FixedGuard(!={p#negated}) {p#reason/s}") -public final class FixedGuardNode extends DeoptimizingFixedWithNextNode implements Simplifiable, Lowerable, Node.IterableNodeType, Negatable, GuardingNode { +public final class FixedGuardNode extends DeoptimizingFixedWithNextNode implements Simplifiable, Lowerable, Node.IterableNodeType, GuardingNode { @Input private LogicNode condition; private final DeoptimizationReason reason; @@ -82,6 +82,12 @@ @Override public void simplify(SimplifierTool tool) { + if (condition instanceof LogicNegationNode) { + LogicNegationNode negation = (LogicNegationNode) condition; + setCondition(negation.getInput()); + negated = !negated; + } + if (condition instanceof LogicConstantNode) { LogicConstantNode c = (LogicConstantNode) condition; if (c.getValue() == negated) { @@ -124,13 +130,6 @@ } @Override - public Negatable negate(LogicNode cond) { - assert cond == condition(); - negated = !negated; - return this; - } - - @Override public FixedGuardNode asNode() { return this; }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/GuardNode.java Sat Aug 24 14:32:57 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/GuardNode.java Sat Aug 24 14:38:11 2013 +0200 @@ -42,7 +42,7 @@ * control flow would have reached the guarded node (without taking exceptions into account). */ @NodeInfo(nameTemplate = "Guard(!={p#negated}) {p#reason/s}") -public final class GuardNode extends FloatingGuardedNode implements Canonicalizable, Node.IterableNodeType, Negatable, GuardingNode, GuardedNode { +public final class GuardNode extends FloatingGuardedNode implements Canonicalizable, Node.IterableNodeType, GuardingNode, GuardedNode { @Input private LogicNode condition; private final DeoptimizationReason reason; @@ -92,6 +92,10 @@ @Override public ValueNode canonical(CanonicalizerTool tool) { + if (condition() instanceof LogicNegationNode) { + LogicNegationNode negation = (LogicNegationNode) condition(); + return graph().unique(new GuardNode(negation.getInput(), getGuard(), reason, action, !negated)); + } if (condition() instanceof LogicConstantNode) { LogicConstantNode c = (LogicConstantNode) condition(); if (c.getValue() != negated) { @@ -101,10 +105,7 @@ return this; } - @Override - public Negatable negate(LogicNode cond) { - assert cond == condition(); + public void negate() { negated = !negated; - return this; } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java Sat Aug 24 14:32:57 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java Sat Aug 24 14:38:11 2013 +0200 @@ -41,7 +41,7 @@ * 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, Negatable { +public final class IfNode extends ControlSplitNode implements Simplifiable, LIRLowerable { @Successor private AbstractBeginNode trueSuccessor; @Successor private AbstractBeginNode falseSuccessor; @@ -108,19 +108,6 @@ return istrue ? trueSuccessor : falseSuccessor; } - @Override - public Negatable negate(LogicNode cond) { - assert cond == condition(); - AbstractBeginNode trueSucc = trueSuccessor(); - AbstractBeginNode falseSucc = falseSuccessor(); - setTrueSuccessor(null); - setFalseSuccessor(null); - setTrueSuccessor(falseSucc); - setFalseSuccessor(trueSucc); - setTrueSuccessorProbability(1 - trueSuccessorProbability); - return this; - } - public void setTrueSuccessorProbability(double prob) { assert prob >= -0.000000001 && prob <= 1.000000001 : "Probability out of bounds: " + prob; trueSuccessorProbability = Math.min(1.0, Math.max(0.0, prob)); @@ -152,6 +139,19 @@ @Override public void simplify(SimplifierTool tool) { + if (condition() instanceof LogicNegationNode) { + LogicNegationNode negation = (LogicNegationNode) condition(); + setCondition(negation.getInput()); + + AbstractBeginNode trueSucc = trueSuccessor(); + AbstractBeginNode falseSucc = falseSuccessor(); + setTrueSuccessor(null); + setFalseSuccessor(null); + setTrueSuccessor(falseSucc); + setFalseSuccessor(trueSucc); + setTrueSuccessorProbability(1 - trueSuccessorProbability); + } + if (condition() instanceof LogicConstantNode) { LogicConstantNode c = (LogicConstantNode) condition(); if (c.getValue()) {
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LogicNegationNode.java Sat Aug 24 14:38:11 2013 +0200 @@ -0,0 +1,51 @@ +/* + * Copyright (c) 2013, 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; + +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.spi.*; + +/** + * Logic node that negates its argument. + */ +public class LogicNegationNode extends LogicNode implements Canonicalizable, Node.IterableNodeType { + + @Input private LogicNode input; + + public LogicNegationNode(LogicNode input) { + this.input = input; + } + + public LogicNode getInput() { + return input; + } + + public ValueNode canonical(CanonicalizerTool tool) { + if (input instanceof LogicNegationNode) { + return ((LogicNegationNode) input).getInput(); + } else { + return this; + } + } + +}
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LogicNode.java Sat Aug 24 14:32:57 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LogicNode.java Sat Aug 24 14:38:11 2013 +0200 @@ -22,9 +22,7 @@ */ package com.oracle.graal.nodes; -import com.oracle.graal.graph.*; import com.oracle.graal.nodes.calc.*; -import com.oracle.graal.nodes.spi.*; import com.oracle.graal.nodes.type.*; public abstract class LogicNode extends FloatingNode { @@ -32,15 +30,4 @@ public LogicNode() { super(StampFactory.condition()); } - - /** - * Tells all usages of this node to negate their effect. For example, IfNodes should switch - * their true and false successors. - */ - public void negateUsages() { - for (Node n : usages().snapshot()) { - assert n instanceof Negatable; - ((Negatable) n).negate(this); - } - } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ShortCircuitAndNode.java Sat Aug 24 14:32:57 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ShortCircuitAndNode.java Sat Aug 24 14:38:11 2013 +0200 @@ -35,6 +35,11 @@ @Override public LogicNode canonical(CanonicalizerTool tool) { + ShortCircuitBooleanNode ret = canonicalizeNegation(); + if (ret != null) { + return ret; + } + LogicNode x = getX(); LogicNode y = getY(); if (x == y) { @@ -47,8 +52,7 @@ if (isXNegated()) { if (isYNegated()) { // !a && !a = !a - negateUsages(); - return x; + return graph().unique(new LogicNegationNode(x)); } else { // !a && a = false return LogicConstantNode.contradiction(graph()); @@ -66,9 +70,10 @@ if (x instanceof LogicConstantNode) { if (((LogicConstantNode) x).getValue() ^ isXNegated()) { if (isYNegated()) { - negateUsages(); + return graph().unique(new LogicNegationNode(y)); + } else { + return y; } - return y; } else { return LogicConstantNode.contradiction(graph()); } @@ -76,13 +81,19 @@ if (y instanceof LogicConstantNode) { if (((LogicConstantNode) y).getValue() ^ isYNegated()) { if (isXNegated()) { - negateUsages(); + return graph().unique(new LogicNegationNode(x)); + } else { + return x; } - return x; } else { return LogicConstantNode.contradiction(graph()); } } return this; } + + @Override + protected ShortCircuitBooleanNode createCopy(LogicNode xCond, boolean xNeg, LogicNode yCond, boolean yNeg, double probability) { + return new ShortCircuitAndNode(xCond, xNeg, yCond, yNeg, probability); + } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ShortCircuitBooleanNode.java Sat Aug 24 14:32:57 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ShortCircuitBooleanNode.java Sat Aug 24 14:38:11 2013 +0200 @@ -23,12 +23,11 @@ package com.oracle.graal.nodes; import com.oracle.graal.graph.*; -import com.oracle.graal.nodes.spi.*; /** * Base class for the short-circuit boolean operators. */ -public abstract class ShortCircuitBooleanNode extends LogicNode implements Negatable, Node.IterableNodeType { +public abstract class ShortCircuitBooleanNode extends LogicNode implements Node.IterableNodeType { @Input private LogicNode x; @Input private LogicNode y; @@ -68,14 +67,27 @@ return shortCircuitProbability; } - @Override - public Negatable negate(LogicNode condition) { - if (condition == x) { - xNegated = !xNegated; + protected abstract ShortCircuitBooleanNode createCopy(LogicNode xCond, boolean xNeg, LogicNode yCond, boolean yNeg, double probability); + + protected ShortCircuitBooleanNode canonicalizeNegation() { + LogicNode xCond = x; + boolean xNeg = xNegated; + while (xCond instanceof LogicNegationNode) { + xCond = ((LogicNegationNode) xCond).getInput(); + xNeg = !xNeg; } - if (condition == y) { - yNegated = !yNegated; + + LogicNode yCond = y; + boolean yNeg = yNegated; + while (yCond instanceof LogicNegationNode) { + yCond = ((LogicNegationNode) yCond).getInput(); + yNeg = !yNeg; } - return this; + + if (xCond != x || yCond != y) { + return graph().unique(createCopy(xCond, xNeg, yCond, yNeg, shortCircuitProbability)); + } else { + return null; + } } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ShortCircuitOrNode.java Sat Aug 24 14:32:57 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ShortCircuitOrNode.java Sat Aug 24 14:38:11 2013 +0200 @@ -35,6 +35,11 @@ @Override public LogicNode canonical(CanonicalizerTool tool) { + ShortCircuitBooleanNode ret = canonicalizeNegation(); + if (ret != null) { + return ret; + } + LogicNode x = getX(); LogicNode y = getY(); if (x == y) { @@ -47,8 +52,7 @@ if (isXNegated()) { if (isYNegated()) { // !a || !a = !a - negateUsages(); - return x; + return graph().unique(new LogicNegationNode(x)); } else { // !a || a = true return LogicConstantNode.tautology(graph()); @@ -68,9 +72,10 @@ return LogicConstantNode.tautology(graph()); } else { if (isYNegated()) { - negateUsages(); + return graph().unique(new LogicNegationNode(y)); + } else { + return y; } - return y; } } if (y instanceof LogicConstantNode) { @@ -78,12 +83,17 @@ return LogicConstantNode.tautology(graph()); } else { if (isXNegated()) { - negateUsages(); + return graph().unique(new LogicNegationNode(x)); + } else { + return x; } - return x; } } return this; } + @Override + protected ShortCircuitBooleanNode createCopy(LogicNode xCond, boolean xNeg, LogicNode yCond, boolean yNeg, double probability) { + return new ShortCircuitOrNode(xCond, xNeg, yCond, yNeg, probability); + } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/CompareNode.java Sat Aug 24 14:32:57 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/CompareNode.java Sat Aug 24 14:38:11 2013 +0200 @@ -92,8 +92,7 @@ return conditionalNode.condition(); } else { assert falseResult == true; - negateUsages(); - return conditionalNode.condition(); + return graph().unique(new LogicNegationNode(conditionalNode.condition())); } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/ConditionalNode.java Sat Aug 24 14:32:57 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/calc/ConditionalNode.java Sat Aug 24 14:38:11 2013 +0200 @@ -34,7 +34,7 @@ * The {@code ConditionalNode} class represents a comparison that yields one of two values. Note * that these nodes are not built directly from the bytecode but are introduced by canonicalization. */ -public final class ConditionalNode extends BinaryNode implements Canonicalizable, LIRLowerable, Negatable { +public final class ConditionalNode extends BinaryNode implements Canonicalizable, LIRLowerable { @Input private LogicNode condition; @@ -67,6 +67,11 @@ @Override public ValueNode canonical(CanonicalizerTool tool) { + if (condition instanceof LogicNegationNode) { + LogicNegationNode negated = (LogicNegationNode) condition; + return graph().unique(new ConditionalNode(negated.getInput(), falseValue(), trueValue())); + } + // 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; @@ -99,14 +104,6 @@ generator.emitConditional(this); } - @Override - public Negatable negate(LogicNode cond) { - assert condition() == cond; - ConditionalNode replacement = graph().unique(new ConditionalNode(condition, falseValue(), trueValue())); - graph().replaceFloating(this, replacement); - return replacement; - } - private ConditionalNode(Condition condition, ValueNode x, ValueNode y) { this(createCompareNode(condition, x, y)); }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/InstanceOfNode.java Sat Aug 24 14:32:57 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/InstanceOfNode.java Sat Aug 24 14:38:11 2013 +0200 @@ -76,8 +76,8 @@ } else { // the instanceof matches if the object is non-null, so return true depending on // the null-ness. - negateUsages(); - return graph().unique(new IsNullNode(object())); + IsNullNode isNull = graph().unique(new IsNullNode(object())); + return graph().unique(new LogicNegationNode(isNull)); } } else { if (objectStamp.isExactType()) {
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/Negatable.java Sat Aug 24 14:32:57 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,42 +0,0 @@ -/* - * 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.spi; - -import com.oracle.graal.nodes.*; - -/** - * This interface marks a node as being able to negate its effect, this is intended for nodes that - * depend on a BooleanNode condition. The canonical representation of has, for example, no way to - * represent a != b. If such an expression appears during canonicalization the negated expression - * will be created (a == b) and the usages will be negated, using this interface's - * {@link #negate(LogicNode)} method. - */ -public interface Negatable { - - /** - * Tells this node that a condition it depends has been negated, and that it thus needs to - * invert the effects of this condition. For example, an {@link IfNode} would switch its true - * and false successors. - */ - Negatable negate(LogicNode condition); -}