# HG changeset patch # User Doug Simon # Date 1373988579 -7200 # Node ID 745322b363597d783fc9e68c3a01cfe95156f114 # Parent debb9d8e0282010fd4d592c2ae988c2dc66ee3dc added a field to LogicBinaryNode capturing the probability that the evaluation of the logic node is short-circuited (i.e. only the left input is evaluated) diff -r debb9d8e0282 -r 745322b36359 graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ConditionalEliminationTest.java --- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ConditionalEliminationTest.java Tue Jul 16 16:36:21 2013 +0200 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ConditionalEliminationTest.java Tue Jul 16 17:29:39 2013 +0200 @@ -163,7 +163,9 @@ new CanonicalizerPhase.Instance(runtime(), null, true).apply(graph); IfNode ifNode = (IfNode) graph.start().next(); InstanceOfNode instanceOf = (InstanceOfNode) ifNode.condition(); - LogicDisjunctionNode disjunction = graph.unique(new LogicDisjunctionNode(graph.unique(new IsNullNode(graph.getLocal(0))), instanceOf)); + IsNullNode x = graph.unique(new IsNullNode(graph.getLocal(0))); + InstanceOfNode y = instanceOf; + LogicDisjunctionNode disjunction = graph.unique(new LogicDisjunctionNode(x, false, y, false, 0.1D)); ifNode.setCondition(disjunction); ifNode.negate(disjunction); new CanonicalizerPhase.Instance(runtime(), null, true).apply(graph); diff -r debb9d8e0282 -r 745322b36359 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LogicBinaryNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LogicBinaryNode.java Tue Jul 16 16:36:21 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LogicBinaryNode.java Tue Jul 16 17:29:39 2013 +0200 @@ -25,22 +25,23 @@ import com.oracle.graal.graph.*; import com.oracle.graal.nodes.spi.*; +/** + * Base class for the short-circuit boolean operators. + */ public abstract class LogicBinaryNode extends LogicNode implements Negatable, Node.IterableNodeType { @Input private LogicNode x; @Input private LogicNode y; private boolean xNegated; private boolean yNegated; + private double shortCircuitProbability; - public LogicBinaryNode(LogicNode x, LogicNode y) { - this(x, false, y, false); - } - - public LogicBinaryNode(LogicNode x, boolean xNegated, LogicNode y, boolean yNegated) { + public LogicBinaryNode(LogicNode x, boolean xNegated, LogicNode y, boolean yNegated, double shortCircuitProbability) { this.x = x; this.xNegated = xNegated; this.y = y; this.yNegated = yNegated; + this.shortCircuitProbability = shortCircuitProbability; } public LogicNode getX() { @@ -59,6 +60,14 @@ return yNegated; } + /** + * Gets the probability that the {@link #getY() y} part of this binary node is not + * evaluated. This is the probability that this operator will short-circuit its execution. + */ + public double getShortCircuitProbability() { + return shortCircuitProbability; + } + @Override public Negatable negate(LogicNode condition) { if (condition == x) { diff -r debb9d8e0282 -r 745322b36359 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LogicConjunctionNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LogicConjunctionNode.java Tue Jul 16 16:36:21 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LogicConjunctionNode.java Tue Jul 16 17:29:39 2013 +0200 @@ -25,16 +25,12 @@ import com.oracle.graal.nodes.spi.*; /** - * This node is true if {@link #getX() x} and {@link #getY() y} are true. + * The short-circuit AND (i.e. {@code &&} in Java) operator. */ public class LogicConjunctionNode extends LogicBinaryNode implements Canonicalizable { - public LogicConjunctionNode(LogicNode x, LogicNode y) { - this(x, false, y, false); - } - - public LogicConjunctionNode(LogicNode x, boolean xNegated, LogicNode y, boolean yNegated) { - super(x, xNegated, y, yNegated); + public LogicConjunctionNode(LogicNode x, boolean xNegated, LogicNode y, boolean yNegated, double shortCircuitProbability) { + super(x, xNegated, y, yNegated, shortCircuitProbability); } @Override diff -r debb9d8e0282 -r 745322b36359 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LogicDisjunctionNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LogicDisjunctionNode.java Tue Jul 16 16:36:21 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LogicDisjunctionNode.java Tue Jul 16 17:29:39 2013 +0200 @@ -25,17 +25,12 @@ import com.oracle.graal.nodes.spi.*; /** - * This node is true if {@link #getX() x} or {@link #getY() y} are true. - * + * The short-circuit OR (i.e. {@code ||} in Java) operator. */ public class LogicDisjunctionNode extends LogicBinaryNode implements Canonicalizable { - public LogicDisjunctionNode(LogicNode x, LogicNode y) { - this(x, false, y, false); - } - - public LogicDisjunctionNode(LogicNode x, boolean xNegated, LogicNode y, boolean yNegated) { - super(x, xNegated, y, yNegated); + public LogicDisjunctionNode(LogicNode x, boolean xNegated, LogicNode y, boolean yNegated, double shortCircuitProbability) { + super(x, xNegated, y, yNegated, shortCircuitProbability); } @Override diff -r debb9d8e0282 -r 745322b36359 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/CheckCastNode.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/CheckCastNode.java Tue Jul 16 16:36:21 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/CheckCastNode.java Tue Jul 16 17:29:39 2013 +0200 @@ -27,7 +27,7 @@ import com.oracle.graal.api.code.*; import com.oracle.graal.api.meta.*; -import com.oracle.graal.api.meta.ProfilingInfo.*; +import com.oracle.graal.api.meta.ProfilingInfo.TriState; import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.calc.*; @@ -117,7 +117,17 @@ condition = typeTest; stamp = stamp.join(StampFactory.objectNonNull()); } else { - condition = graph().unique(new LogicDisjunctionNode(graph().unique(new IsNullNode(object)), typeTest)); + double shortCircuitProbability; + if (profile == null) { + shortCircuitProbability = 0.1D; + } else { + // Tell the instanceof it does not need to do a null check + typeTest.setProfile(new JavaTypeProfile(TriState.FALSE, profile.getNotRecordedProbability(), profile.getTypes())); + + // TODO (ds) replace with probability of null-seen when available + shortCircuitProbability = 0.1D; + } + condition = graph().unique(new LogicDisjunctionNode(graph().unique(new IsNullNode(object)), false, typeTest, false, shortCircuitProbability)); } } GuardingPiNode checkedObject = graph().add(new GuardingPiNode(object, condition, false, forStoreCheck ? ArrayStoreException : ClassCastException, InvalidateReprofile, stamp)); diff -r debb9d8e0282 -r 745322b36359 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ExpandLogicPhase.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ExpandLogicPhase.java Tue Jul 16 16:36:21 2013 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ExpandLogicPhase.java Tue Jul 16 17:29:39 2013 +0200 @@ -44,9 +44,9 @@ processBinary((LogicBinaryNode) usage); } else if (usage instanceof IfNode) { if (binary instanceof LogicConjunctionNode) { - processIf(binary.getX(), binary.isXNegated(), binary.getY(), binary.isYNegated(), (IfNode) usage, false); + processIf(binary.getX(), binary.isXNegated(), binary.getY(), binary.isYNegated(), (IfNode) usage, false, binary.getShortCircuitProbability()); } else if (binary instanceof LogicDisjunctionNode) { - processIf(binary.getX(), !binary.isXNegated(), binary.getY(), !binary.isYNegated(), (IfNode) usage, true); + processIf(binary.getX(), !binary.isXNegated(), binary.getY(), !binary.isYNegated(), (IfNode) usage, true, binary.getShortCircuitProbability()); } else { throw GraalInternalError.shouldNotReachHere(); } @@ -65,10 +65,11 @@ binary.safeDelete(); } - private static void processIf(LogicNode x, boolean xNegated, LogicNode y, boolean yNegated, IfNode ifNode, boolean negateTargets) { + private static void processIf(LogicNode x, boolean xNegated, LogicNode y, boolean yNegated, IfNode ifNode, boolean negateTargets, double shortCircuitProbability) { AbstractBeginNode trueTarget = negateTargets ? ifNode.falseSuccessor() : ifNode.trueSuccessor(); AbstractBeginNode falseTarget = negateTargets ? ifNode.trueSuccessor() : ifNode.falseSuccessor(); - double p = Math.sqrt(ifNode.probability(trueTarget)); + double firstIfProbability = shortCircuitProbability; + double secondIfProbability = 1 - ifNode.probability(trueTarget); ifNode.clearSuccessors(); Graph graph = ifNode.graph(); MergeNode falseTargetMerge = graph.add(new MergeNode()); @@ -79,8 +80,8 @@ falseTargetMerge.addForwardEnd(secondFalseEnd); AbstractBeginNode firstFalseTarget = AbstractBeginNode.begin(firstFalseEnd); AbstractBeginNode secondFalseTarget = AbstractBeginNode.begin(secondFalseEnd); - AbstractBeginNode secondIf = AbstractBeginNode.begin(graph.add(new IfNode(y, yNegated ? firstFalseTarget : trueTarget, yNegated ? trueTarget : firstFalseTarget, yNegated ? 1 - p : p))); - IfNode firstIf = graph.add(new IfNode(x, xNegated ? secondFalseTarget : secondIf, xNegated ? secondIf : secondFalseTarget, xNegated ? 1 - p : p)); + AbstractBeginNode secondIf = AbstractBeginNode.begin(graph.add(new IfNode(y, yNegated ? firstFalseTarget : trueTarget, yNegated ? trueTarget : firstFalseTarget, secondIfProbability))); + IfNode firstIf = graph.add(new IfNode(x, xNegated ? secondFalseTarget : secondIf, xNegated ? secondIf : secondFalseTarget, firstIfProbability)); ifNode.replaceAtPredecessor(firstIf); ifNode.safeDelete(); }