# HG changeset patch
# User Miguel Garcia <miguel.m.garcia@oracle.com>
# Date 1399212764 -7200
# Node ID 49a917f9fa073973109052d62671c922af3c86cf
# Parent  45a54859fd7d704ed61da03b79d7d3a43df30856
[flow-sensitive] refactoring, factor out evidence-search

diff -r 45a54859fd7d -r 49a917f9fa07 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/EquationalReasoner.java
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/EquationalReasoner.java	Sat May 03 16:19:43 2014 +0200
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/EquationalReasoner.java	Sun May 04 16:12:44 2014 +0200
@@ -489,7 +489,7 @@
             return isNull;
         }
         ValueNode scrutinee = GraphUtil.unproxify(isNull.object());
-        GuardingNode evidence = nonTrivialNullAnchor(scrutinee);
+        GuardingNode evidence = state.nonTrivialNullAnchor(scrutinee);
         if (evidence != null) {
             metricNullCheckRemoved.increment();
             return trueConstant;
@@ -684,24 +684,6 @@
     }
 
     /**
-     * <p>
-     * If the argument is known null due to its stamp, there's no need to have an anchor for that
-     * fact and this method returns null.
-     * </p>
-     *
-     * <p>
-     * Otherwise, if an anchor is found it is returned, null otherwise.
-     * </p>
-     */
-    public GuardingNode nonTrivialNullAnchor(ValueNode object) {
-        assert FlowUtil.hasLegalObjectStamp(object);
-        if (StampTool.isObjectAlwaysNull(object)) {
-            return null;
-        }
-        return state.knownNull.get(GraphUtil.unproxify(object));
-    }
-
-    /**
      *
      * This method returns:
      * <ul>
@@ -718,7 +700,7 @@
      */
     public PiNode nonTrivialNull(ValueNode object) {
         assert FlowUtil.hasLegalObjectStamp(object);
-        GuardingNode anchor = nonTrivialNullAnchor(object);
+        GuardingNode anchor = state.nonTrivialNullAnchor(object);
         if (anchor == null) {
             return null;
         }
diff -r 45a54859fd7d -r 49a917f9fa07 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/Evidence.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/Evidence.java	Sun May 04 16:12:44 2014 +0200
@@ -0,0 +1,61 @@
+/*
+ * 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.phases.common.cfs;
+
+import com.oracle.graal.nodes.extended.GuardingNode;
+
+public class Evidence {
+
+    public final GuardingNode success;
+    public final boolean failure;
+
+    public Evidence(GuardingNode success, boolean failure) {
+        this.success = success;
+        this.failure = failure;
+        assert repOK();
+    }
+
+    public Evidence(GuardingNode success) {
+        this(success, false);
+    }
+
+    private Evidence(boolean failure) {
+        this(null, failure);
+    }
+
+    public boolean isPositive() {
+        return success != null;
+    }
+
+    public boolean isNegative() {
+        return failure;
+    }
+
+    private boolean repOK() {
+        // either success or failure, ie boolean-XOR
+        return (success != null) != failure;
+    }
+
+    public static Evidence COUNTEREXAMPLE = new Evidence(true);
+
+}
diff -r 45a54859fd7d -r 49a917f9fa07 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FixedGuardReduction.java
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FixedGuardReduction.java	Sat May 03 16:19:43 2014 +0200
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FixedGuardReduction.java	Sun May 04 16:12:44 2014 +0200
@@ -23,9 +23,7 @@
 package com.oracle.graal.phases.common.cfs;
 
 import com.oracle.graal.nodes.*;
-import com.oracle.graal.nodes.calc.IsNullNode;
 import com.oracle.graal.nodes.extended.GuardingNode;
-import com.oracle.graal.nodes.java.*;
 import com.oracle.graal.phases.tiers.PhaseContext;
 
 /**
@@ -99,118 +97,33 @@
             return;
         }
 
-        /*
-         * Attempt to eliminate the current FixedGuardNode by using another GuardingNode already in
-         * scope and with equivalent condition.
-         */
+        final boolean isTrue = !f.isNegated();
+        final Evidence evidence = state.outcome(isTrue, f.condition());
 
-        GuardingNode existingGuard = f.isNegated() ? state.falseFacts.get(f.condition()) : state.trueFacts.get(f.condition());
-        if (existingGuard != null) {
-            // assert existingGuard instanceof FixedGuardNode;
-            metricFixedGuardNodeRemoved.increment();
-            f.replaceAtUsages(existingGuard.asNode());
-            graph.removeFixed(f);
+        // can't produce evidence, must be information gain
+        if (evidence == null) {
+            state.addFact(isTrue, f.condition(), f);
             return;
         }
 
-        final LogicNode cond = f.condition();
-        final boolean isTrue = !f.isNegated();
-
-        /*
-         * A FixedGuardNode can only be removed provided a replacement anchor is found (so called
-         * "evidence"), ie an anchor that amounts to the same combination of (negated, condition) as
-         * for the FixedGuardNode at hand. Just deverbosifying the condition in place isn't
-         * semantics-preserving.
-         */
-
-        // TODO what about isDependencyTainted
-
-        if (cond instanceof IsNullNode) {
-            final IsNullNode isNullNode = (IsNullNode) cond;
-            if (isTrue) {
-                // grab an anchor attesting nullness
-                final GuardingNode replacement = reasoner.nonTrivialNullAnchor(isNullNode.object());
-                if (replacement != null) {
-                    removeFixedGuardNode(f, replacement);
-                    return;
-                }
-                if (state.isNonNull(isNullNode.object())) {
-                    markFixedGuardNodeAlwaysFails(f);
-                    return;
-                }
-                // can't produce evidence, fall-through to addFact
-            } else {
-                // grab an anchor attesting non-nullness
-                final Witness w = state.typeInfo(isNullNode.object());
-                if (w != null && w.isNonNull()) {
-                    removeFixedGuardNode(f, w.guard());
-                    return;
-                }
-                if (state.isNull(isNullNode.object())) {
-                    markFixedGuardNodeAlwaysFails(f);
-                    return;
-                }
-                // can't produce evidence, fall-through to addFact
-            }
-        } else if (cond instanceof InstanceOfNode) {
-            final InstanceOfNode iOf = (InstanceOfNode) cond;
-            final Witness w = state.typeInfo(iOf.object());
-            if (isTrue) {
-                // grab an anchor attesting instanceof
-                if (w != null) {
-                    if (w.isNonNull() && w.type() != null) {
-                        if (iOf.type().isAssignableFrom(w.type())) {
-                            removeFixedGuardNode(f, w.guard());
-                            return;
-                        }
-                        if (State.knownNotToConform(w.type(), iOf.type())) {
-                            markFixedGuardNodeAlwaysFails(f);
-                            return;
-                        }
-                    }
-                }
-                if (state.isNull(iOf.object())) {
-                    markFixedGuardNodeAlwaysFails(f);
-                    return;
-                }
-                // can't produce evidence, fall-through to addFact
-            } else {
-                // grab an anchor attesting not-instanceof
-                // (1 of 2) attempt determining nullness
-                final GuardingNode nullGuard = reasoner.nonTrivialNullAnchor(iOf.object());
-                if (nullGuard != null) {
-                    removeFixedGuardNode(f, nullGuard);
-                    return;
-                }
-                // (2 of 2) attempt determining known-not-to-conform
-                if (w != null && !w.cluelessAboutType()) {
-                    if (State.knownNotToConform(w.type(), iOf.type())) {
-                        removeFixedGuardNode(f, w.guard());
-                        return;
-                    }
-                }
-                // can't produce evidence, fall-through to addFact
-            }
-        } else if (isTrue && cond instanceof ShortCircuitOrNode) {
-            CastCheckExtractor cce = CastCheckExtractor.extract(cond);
-            if (cce != null && !State.isDependencyTainted(cce.subject, f)) {
-                // grab an anchor attesting check-cast
-                Witness w = state.typeInfo(cce.subject);
-                if (w != null && w.type() != null) {
-                    if (cce.type.isAssignableFrom(w.type())) {
-                        removeFixedGuardNode(f, w.guard());
-                        return;
-                    }
-                    if (State.knownNotToConform(w.type(), cce.type)) {
-                        markFixedGuardNodeAlwaysFails(f);
-                        return;
-                    }
-                }
-            }
-            // can't produce evidence, fall-through to addFact
+        if (evidence.isPositive()) {
+            /*
+             * A FixedGuardNode can only be removed provided a replacement anchor is found (so
+             * called "evidence"), ie an anchor that amounts to the same combination of (negated,
+             * condition) as for the FixedGuardNode at hand. Just deverbosifying the condition in
+             * place isn't semantics-preserving.
+             * 
+             * Eliminate the current FixedGuardNode by using another GuardingNode already in scope,
+             * a GuardingNode that guards a condition that is at least as strong as that of the
+             * FixedGuardNode.
+             */
+            removeFixedGuardNode(f, evidence.success);
+            return;
         }
 
-        state.addFact(isTrue, cond, f);
+        assert evidence.isNegative();
+        markFixedGuardNodeAlwaysFails(f);
+
     }
 
     /**
@@ -232,9 +145,7 @@
      * </p>
      */
     private void removeFixedGuardNode(FixedGuardNode old, GuardingNode replacement) {
-        if (replacement == null) {
-            return;
-        }
+        assert replacement != null;
         metricFixedGuardNodeRemoved.increment();
         old.replaceAtUsages(replacement.asNode());
         graph.removeFixed(old);
diff -r 45a54859fd7d -r 49a917f9fa07 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/State.java
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/State.java	Sat May 03 16:19:43 2014 +0200
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/State.java	Sun May 04 16:12:44 2014 +0200
@@ -422,6 +422,10 @@
         assert FlowUtil.hasLegalObjectStamp(object);
         assert !to.isPrimitive();
         final ValueNode scrutinee = GraphUtil.unproxify(object);
+        if (isNull(scrutinee)) {
+            // known-null means it conforms to whatever `to`
+            return false;
+        }
         if (!isNonNull(scrutinee)) {
             // unless `null` can be ruled out, a positive answer isn't safe
             return false;
@@ -814,4 +818,178 @@
         falseFacts.clear();
     }
 
+    /**
+     * <p>
+     * If the argument is known null due to its stamp, there's no need to have an anchor for that
+     * fact and this method returns null.
+     * </p>
+     *
+     * <p>
+     * Otherwise, if an anchor is found it is returned, null otherwise.
+     * </p>
+     */
+    public GuardingNode nonTrivialNullAnchor(ValueNode object) {
+        assert FlowUtil.hasLegalObjectStamp(object);
+        if (StampTool.isObjectAlwaysNull(object)) {
+            return null;
+        }
+        return knownNull.get(GraphUtil.unproxify(object));
+    }
+
+    /**
+     * This method:
+     * <ul>
+     * <li>
+     * attempts to find an existing {@link com.oracle.graal.nodes.extended.GuardingNode} that
+     * implies the property stated by the arguments. If found, returns it as positive evidence.</li>
+     * <li>
+     * otherwise, if the property of interest is known not to hold, negative evidence is returned.</li>
+     * <li>
+     * otherwise, null is returned.</li>
+     * </ul>
+     */
+    public Evidence outcome(boolean isTrue, LogicNode cond) {
+
+        // attempt to find an anchor for the condition of interest, verbatim
+        if (isTrue) {
+            GuardingNode existingGuard = trueFacts.get(cond);
+            if (existingGuard != null) {
+                return new Evidence(existingGuard);
+            }
+            if (falseFacts.containsKey(cond)) {
+                return Evidence.COUNTEREXAMPLE;
+            }
+        } else {
+            GuardingNode existingGuard = falseFacts.get(cond);
+            if (existingGuard != null) {
+                return new Evidence(existingGuard);
+            }
+            if (trueFacts.containsKey(cond)) {
+                return Evidence.COUNTEREXAMPLE;
+            }
+        }
+
+        if (cond instanceof IsNullNode) {
+            return outcomeIsNullNode(isTrue, (IsNullNode) cond);
+        }
+
+        if (cond instanceof InstanceOfNode) {
+            return outcomeInstanceOfNode(isTrue, (InstanceOfNode) cond);
+        }
+
+        if (cond instanceof ShortCircuitOrNode) {
+            return outcomeShortCircuitOrNode(isTrue, (ShortCircuitOrNode) cond);
+        }
+
+        // can't produce evidence
+        return null;
+    }
+
+    /**
+     * Utility method for {@link #outcome(boolean, com.oracle.graal.nodes.LogicNode)}
+     */
+    private Evidence outcomeIsNullNode(boolean isTrue, IsNullNode isNullNode) {
+        if (isTrue) {
+            // grab an anchor attesting nullness
+            final GuardingNode replacement = nonTrivialNullAnchor(isNullNode.object());
+            if (replacement != null) {
+                return new Evidence(replacement);
+            }
+            if (isNonNull(isNullNode.object())) {
+                return Evidence.COUNTEREXAMPLE;
+            }
+        } else {
+            // grab an anchor attesting non-nullness
+            final Witness w = typeInfo(isNullNode.object());
+            if (w != null && w.isNonNull()) {
+                return new Evidence(w.guard());
+            }
+            if (isNull(isNullNode.object())) {
+                return Evidence.COUNTEREXAMPLE;
+            }
+        }
+        // can't produce evidence
+        return null;
+    }
+
+    /**
+     * Utility method for {@link #outcome(boolean, com.oracle.graal.nodes.LogicNode)}
+     */
+    private Evidence outcomeInstanceOfNode(boolean isTrue, InstanceOfNode iOf) {
+        final Witness w = typeInfo(iOf.object());
+        if (isTrue) {
+            if (isNull(iOf.object())) {
+                return Evidence.COUNTEREXAMPLE;
+            }
+            // grab an anchor attesting instanceof
+            if ((w != null) && (w.type() != null)) {
+                if (w.isNonNull()) {
+                    if (iOf.type().isAssignableFrom(w.type())) {
+                        return new Evidence(w.guard());
+                    }
+                }
+                if (State.knownNotToConform(w.type(), iOf.type())) {
+                    // null -> fails instanceof
+                    // non-null but non-conformant -> also fails instanceof
+                    return Evidence.COUNTEREXAMPLE;
+                }
+            }
+        } else {
+            // grab an anchor attesting not-instanceof
+            // (1 of 2) attempt determining nullness
+            final GuardingNode nullGuard = nonTrivialNullAnchor(iOf.object());
+            if (nullGuard != null) {
+                return new Evidence(nullGuard);
+            }
+            // (2 of 2) attempt determining known-not-to-conform
+            if (w != null && !w.cluelessAboutType()) {
+                if (State.knownNotToConform(w.type(), iOf.type())) {
+                    return new Evidence(w.guard());
+                }
+            }
+        }
+        // can't produce evidence
+        return null;
+    }
+
+    /**
+     * Utility method for {@link #outcome(boolean, com.oracle.graal.nodes.LogicNode)}
+     */
+    private Evidence outcomeShortCircuitOrNode(boolean isTrue, ShortCircuitOrNode orNode) {
+        if (!isTrue) {
+            // too tricky to reason about
+            return null;
+        }
+        CastCheckExtractor cce = CastCheckExtractor.extract(orNode);
+        if (cce != null) {
+            // grab an anchor attesting check-cast
+            Witness w = typeInfo(cce.subject);
+            if (w != null && w.type() != null) {
+                if (cce.type.isAssignableFrom(w.type())) {
+                    return new Evidence(w.guard());
+                }
+                if (isNonNull(cce.subject) && State.knownNotToConform(w.type(), cce.type)) {
+                    return Evidence.COUNTEREXAMPLE;
+                }
+            }
+        }
+        // search for positive-evidence for the first or-input
+        Evidence evidenceX = outcome(!orNode.isXNegated(), orNode.getX());
+        if (evidenceX != null && evidenceX.isPositive()) {
+            return evidenceX;
+        }
+        // search for positive-evidence for the second or-input
+        Evidence evidenceY = outcome(!orNode.isYNegated(), orNode.getY());
+        if (evidenceY != null && evidenceY.isPositive()) {
+            return evidenceY;
+        }
+        // check for contradictions on both or-inputs
+        if (evidenceX != null && evidenceY != null) {
+            assert evidenceX.isNegative() && evidenceY.isNegative();
+            return Evidence.COUNTEREXAMPLE;
+        }
+        // can't produce evidence
+        return null;
+    }
+
 }