Mercurial > hg > graal-compiler

changeset 10786:745322b36359

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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)
author Doug Simon <doug.simon@oracle.com>
date Tue, 16 Jul 2013 17:29:39 +0200
parents debb9d8e0282
children 388fbd0dd4a4
files graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ConditionalEliminationTest.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LogicBinaryNode.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LogicConjunctionNode.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/LogicDisjunctionNode.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/CheckCastNode.java graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ExpandLogicPhase.java
diffstat 6 files changed, 42 insertions(+), 29 deletions(-) [+]
line wrap: on
line diff
--- 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);
--- 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 <b>not</b>
+     * 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) {
--- 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} <b>and</b> {@link #getY() y} are true.
+ * The short-circuit <b>AND</b> (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
--- 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} <b>or</b> {@link #getY() y} are true.
- * 
+ * The short-circuit <b>OR</b> (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
--- 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));
--- 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();
     }