--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/State.java	Thu May 08 15:00:52 2014 +0200
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/State.java	Thu May 08 16:44:53 2014 +0200
@@ -97,32 +97,26 @@
 
     /**
      * <p>
-     * This map semantically tracks "facts" (ie, properties valid for the program-point the state
-     * refers to) as opposed to floating-guard-dependent properties. The
-     * {@link com.oracle.graal.nodes.extended.GuardingNode} being tracked comes handy at
-     * {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReduction#visitFixedGuardNode(com.oracle.graal.nodes.FixedGuardNode)}
-     * .
+     * This map tracks properties about reference-values, ie combinations of: definitely-null,
+     * known-to-be-non-null, seen-type.
      * </p>
      *
      * <p>
-     * On a related note, {@link #typeRefinements} also captures information the way
-     * {@link #trueFacts} and {@link #falseFacts} do, including "witnessing" guards. Why not just
-     * standardize on one of them, and drop the other? Because the {@link #typeRefinements} eagerly
-     * aggregates information for easier querying afterwards, e.g. when producing a "downcasted"
-     * value (which involves building a {@link com.oracle.graal.nodes.PiNode}, see
-     * {@link EquationalReasoner#downcast(com.oracle.graal.nodes.ValueNode) downcast()}
+     * In contrast to {@link #trueFacts} and {@link #falseFacts}, this map can answer queries even
+     * though the exact {@link LogicNode} standing for such query hasn't been tracked. For example,
+     * queries about subtyping. Additionally, a {@link Witness} can combine separate pieces of
+     * information more flexibly, eg, two separate observations about non-null and check-cast are
+     * promoted to an instance-of witness.
      * </p>
      *
      */
     private Map<ValueNode, Witness> typeRefinements;
 
-    Map<ValueNode, GuardingNode> knownNull;
     Map<LogicNode, GuardingNode> trueFacts;
     Map<LogicNode, GuardingNode> falseFacts;
 
     public State() {
         this.typeRefinements = newNodeIdentityMap();
-        this.knownNull = newNodeIdentityMap();
         this.trueFacts = newNodeIdentityMap();
         this.falseFacts = newNodeIdentityMap();
     }
@@ -134,7 +128,6 @@
         for (Map.Entry<ValueNode, Witness> entry : other.typeRefinements.entrySet()) {
             this.typeRefinements.put(entry.getKey(), new Witness(entry.getValue()));
         }
-        this.knownNull = newNodeIdentityMap(other.knownNull);
         this.trueFacts = newNodeIdentityMap(other.trueFacts);
         this.falseFacts = newNodeIdentityMap(other.falseFacts);
     }
@@ -144,10 +137,6 @@
         for (LogicNode trueFact : trueFacts.keySet()) {
             assert !falseFacts.containsKey(trueFact) : trueFact + " tracked as both true and false fact.";
         }
-        // no scrutinee tracked as both known-null and known-non-null
-        for (ValueNode subject : knownNull.keySet()) {
-            assert !isNonNull(subject) : subject + " tracked as both known-null and known-non-null.";
-        }
         return true;
     }
 
@@ -189,31 +178,6 @@
         return newKnownTypes;
     }
 
-    private Map<ValueNode, GuardingNode> mergeKnownNull(MergeNode merge, ArrayList<State> withReachableStates) {
-        // newKnownNull starts empty
-        Map<ValueNode, GuardingNode> newKnownNull = newNodeIdentityMap();
-        for (Map.Entry<ValueNode, GuardingNode> entry : knownNull.entrySet()) {
-            ValueNode key = entry.getKey();
-            GuardingNode newGN = entry.getValue();
-            boolean missing = false;
-
-            for (State other : withReachableStates) {
-                GuardingNode otherGuard = other.knownNull.get(key);
-                if (otherGuard == null) {
-                    missing = true;
-                    break;
-                }
-                if (otherGuard != newGN) {
-                    newGN = merge;
-                }
-            }
-            if (!missing) {
-                newKnownNull.put(key, newGN);
-            }
-        }
-        return newKnownNull;
-    }
-
     /**
      * <p>
      * This method handles phis, by adding to the resulting state any information that can be gained
@@ -231,7 +195,7 @@
      * when merging type-witnesses and known-null maps.
      * </p>
      */
-    private void mergePhis(MergeNode merge, List<State> withStates, Map<ValueNode, Witness> newKnownPhiTypes, Map<ValueNode, GuardingNode> newKnownNullPhis) {
+    private void mergePhis(MergeNode merge, List<State> withStates, Map<ValueNode, Witness> newKnownPhiTypes) {
 
         if (merge instanceof LoopBeginNode) {
             return;
@@ -254,20 +218,21 @@
                 ObjectStamp phiStamp = (ObjectStamp) phi.stamp();
                 ObjectStamp nonPollutedStamp = (ObjectStamp) StampTool.meet(reachingValues);
                 Witness w = new Witness(nonPollutedStamp, merge);
-                if (FlowUtil.isMorePrecise(w.type(), phiStamp.type())) {
+                if (w.isNull() && !phiStamp.alwaysNull()) {
+                    // precision gain: null
+                    newKnownPhiTypes.put(phi, w);
+                } else if (FlowUtil.isMorePrecise(w.type(), phiStamp.type())) {
                     // precision gain regarding type
                     newKnownPhiTypes.put(phi, w);
                     // confirm no precision loss regarding nullness
                     assert implies(phiStamp.nonNull(), w.isNonNull());
+                    assert implies(phiStamp.alwaysNull(), w.isNull());
                 } else if (w.isNonNull() && !phiStamp.nonNull()) {
-                    // precision gain regarding nullness
+                    // precision gain: non-null
                     newKnownPhiTypes.put(phi, w);
                     // confirm no precision loss regarding type
                     assert !FlowUtil.isMorePrecise(phiStamp.type(), w.type());
                 }
-                if (nonPollutedStamp.alwaysNull()) {
-                    newKnownNullPhis.put(phi, merge);
-                }
             }
         }
 
@@ -294,7 +259,6 @@
 
         if (isUnreachable) {
             typeRefinements.clear();
-            knownNull.clear();
             trueFacts.clear();
             falseFacts.clear();
             return true;
@@ -303,10 +267,8 @@
         // may also get updated in a moment, during processing of phi nodes.
         Map<ValueNode, Witness> newKnownTypes = mergeKnownTypes(merge, withReachableStates);
         // may also get updated in a moment, during processing of phi nodes.
-        Map<ValueNode, GuardingNode> newKnownNull = mergeKnownNull(merge, withReachableStates);
-        mergePhis(merge, withStates, newKnownTypes, newKnownNull);
+        mergePhis(merge, withStates, newKnownTypes);
         this.typeRefinements = newKnownTypes;
-        this.knownNull = newKnownNull;
 
         this.trueFacts = mergeTrueFacts(withReachableStates, merge);
         this.falseFacts = mergeFalseFacts(withReachableStates, merge);
@@ -375,7 +337,12 @@
      */
     public boolean isNull(ValueNode object) {
         assert FlowUtil.hasLegalObjectStamp(object);
-        return StampTool.isObjectAlwaysNull(object) || knownNull.containsKey(GraphUtil.unproxify(object));
+        if (StampTool.isObjectAlwaysNull(object)) {
+            return true;
+        }
+        ValueNode scrutinee = GraphUtil.unproxify(object);
+        Witness w = typeRefinements.get(scrutinee);
+        return (w != null) && w.isNull();
     }
 
     /**
@@ -809,23 +776,24 @@
             return;
         }
         assert anchor instanceof FixedNode;
-        ValueNode original = GraphUtil.unproxify(value);
-        boolean wasNull = isNull(original);
-        boolean wasNonNull = isNonNull(original);
+        ValueNode scrutinee = GraphUtil.unproxify(value);
+        boolean wasNull = isNull(scrutinee);
+        boolean wasNonNull = isNonNull(scrutinee);
         if (isNull) {
             if (wasNonNull) {
                 impossiblePath();
             } else {
                 metricNullnessRegistered.increment();
                 versionNr++;
-                knownNull.put(original, anchor);
+                Witness w = getOrElseAddTypeInfo(scrutinee);
+                w.trackDN(anchor);
             }
         } else {
             if (wasNull) {
                 impossiblePath();
             } else {
                 metricNullnessRegistered.increment();
-                trackNN(original, anchor);
+                trackNN(scrutinee, anchor);
             }
         }
         assert repOK();
@@ -861,7 +829,6 @@
         versionNr = 0;
         isUnreachable = false;
         typeRefinements.clear();
-        knownNull.clear();
         trueFacts.clear();
         falseFacts.clear();
     }
@@ -881,7 +848,12 @@
         if (StampTool.isObjectAlwaysNull(object)) {
             return null;
         }
-        return knownNull.get(GraphUtil.unproxify(object));
+        ValueNode scrutinee = GraphUtil.unproxify(object);
+        Witness w = typeRefinements.get(scrutinee);
+        if (w != null && w.isNull()) {
+            return w.guard();
+        }
+        return null;
     }
 
     /**

--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/Witness.java	Thu May 08 15:00:52 2014 +0200
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/Witness.java	Thu May 08 16:44:53 2014 +0200
@@ -86,7 +86,8 @@
         CLUELESS,
         NN,
         CC,
-        IO
+        IO,
+        DN
     }
 
     private boolean atNonNull() {
@@ -101,6 +102,10 @@
         return level == LEVEL.IO;
     }
 
+    private boolean atDefinitelyNull() {
+        return level == LEVEL.DN;
+    }
+
     private void transition(LEVEL to, GuardingNode newAnchor) {
         this.level = to;
         this.gn = newAnchor;
@@ -122,37 +127,41 @@
     public Witness(ObjectStamp stamp, GuardingNode anchor) {
         assert stamp.isLegal();
         assert anchor != null;
-        boolean isNonIface = (stamp.type() != null && !stamp.type().isInterface());
-        if (stamp.nonNull()) {
-            if (isNonIface) {
-                seen = stamp.type();
-                transition(LEVEL.IO, anchor);
+        if (stamp.alwaysNull()) {
+            // seen left null
+            transition(LEVEL.DN, anchor);
+        } else {
+            boolean isNonIface = (stamp.type() != null && !stamp.type().isInterface());
+            if (stamp.nonNull()) {
+                if (isNonIface) {
+                    seen = stamp.type();
+                    transition(LEVEL.IO, anchor);
+                } else {
+                    seen = null;
+                    transition(LEVEL.NN, anchor);
+                }
             } else {
-                seen = null;
-                transition(LEVEL.NN, anchor);
-            }
-        } else {
-            if (isNonIface) {
-                seen = stamp.type();
-                transition(LEVEL.CC, anchor);
-            } else {
-                seen = null;
-                transition(LEVEL.CLUELESS, null);
-                assert clueless();
+                if (isNonIface) {
+                    seen = stamp.type();
+                    transition(LEVEL.CC, anchor);
+                } else {
+                    seen = null;
+                    transition(LEVEL.CLUELESS, null);
+                    assert clueless();
+                }
             }
         }
         assert repOK();
     }
 
-    /**
-     * Type-witnesses aren't tracked for known-to-be-null. Therefore, although method
-     * {@link #isNonNull() isNonNull()} can be found in this class there's on purpose no companion
-     * <code>isNull()</code> .
-     */
     public boolean isNonNull() {
         return atNonNull() || atInstanceOf();
     }
 
+    public boolean isNull() {
+        return atDefinitelyNull();
+    }
+
     /**
      * The most precise type known so far about the scrutinee. (Please notice that nothing can be
      * deduced about the non-nullness-status of the scrutinee from invoking this method alone).
@@ -163,7 +172,7 @@
 
     public ObjectStamp asStamp() {
         boolean isKnownExact = (seen != null && seen.equals(seen.asExactType()));
-        return new ObjectStamp(seen, isKnownExact, isNonNull(), false);
+        return new ObjectStamp(seen, isKnownExact, isNonNull(), isNull());
     }
 
     private LEVEL level = LEVEL.CLUELESS;
@@ -219,15 +228,14 @@
             assert level == LEVEL.CLUELESS;
             return true;
         }
-        if (level == LEVEL.NN) {
+        if (atNonNull() || atDefinitelyNull()) {
             assert seen == null;
         }
         if (seen != null) {
             assert !seen.isInterface();
             assert !seen.isPrimitive();
         }
-        boolean gnOK = gn instanceof BeginNode || gn instanceof LoopExitNode || gn instanceof MergeNode || gn instanceof FixedGuardNode;
-        assert gnOK;
+        assert gn instanceof BeginNode || gn instanceof LoopExitNode || gn instanceof MergeNode || gn instanceof FixedGuardNode;
         return true;
     }
 
@@ -235,7 +243,7 @@
      * Helper method for readability in complex conditions.
      */
     public boolean clueless() {
-        return cluelessAboutType() && cluelessAboutNonNullness();
+        return cluelessAboutType() && cluelessAboutNullity();
     }
 
     /**
@@ -249,8 +257,8 @@
     /**
      * Helper method for readability in complex conditions.
      */
-    public boolean cluelessAboutNonNullness() {
-        return !atNonNull() && !atInstanceOf();
+    public boolean cluelessAboutNullity() {
+        return !atNonNull() && !atInstanceOf() && !atDefinitelyNull();
     }
 
     /**
@@ -276,6 +284,9 @@
      * @return whether the state was updated (iff the observation adds any new information)
      */
     private boolean refinesSeenType(ResolvedJavaType observed) {
+        if (isNull()) {
+            return false;
+        }
         if (cluelessAboutType() || FlowUtil.isMorePrecise(observed, seen)) {
             seen = observed;
             return true;
@@ -294,6 +305,7 @@
      */
     public boolean trackNN(GuardingNode anchor) {
         assert repOK();
+        assert !isNull();
         try {
             if (atInstanceOf()) {
                 return false;
@@ -313,6 +325,29 @@
     }
 
     /**
+     * Updates this {@link Witness Witness} to account for an observation about the scrutinee being
+     * null.
+     *
+     * @return whether this {@link Witness Witness} was updated (iff the observation adds any new
+     *         information)
+     */
+    public boolean trackDN(GuardingNode anchor) {
+        assert repOK();
+        assert !isNonNull();
+        try {
+            if (atDefinitelyNull()) {
+                return false;
+            }
+            assert level == LEVEL.CLUELESS || atCheckCast();
+            seen = null;
+            transition(LEVEL.DN, anchor);
+            return true;
+        } finally {
+            assert repOK();
+        }
+    }
+
+    /**
      * Updates this {@link Witness Witness} to account for an observation about the scrutinee
      * conforming to the provided type. In case instanceof was observed,
      * {@link #trackIO(com.oracle.graal.api.meta.ResolvedJavaType, com.oracle.graal.nodes.extended.GuardingNode)
@@ -366,6 +401,7 @@
      */
     public boolean trackIO(ResolvedJavaType observed, GuardingNode anchor) {
         assert repOK();
+        assert !isNull();
         try {
             boolean gotMorePreciseType = refinesSeenType(observed);
             if (!atInstanceOf() || gotMorePreciseType) {
@@ -405,12 +441,62 @@
             return;
         }
 
+        // preserve guarding node only if matches other, otherwise settle on `merge`
+        final GuardingNode resultGuard = (guard() == that.guard()) ? guard() : merge;
+
+        if (isNull()) {
+            switch (that.level) {
+                case CLUELESS:
+                case NN:
+                    // lose is-null status, gain nothing
+                    level = LEVEL.CLUELESS;
+                    seen = null;
+                    break;
+                case CC:
+                case IO:
+                    // demote to check-cast
+                    level = LEVEL.CC;
+                    seen = that.seen;
+                    break;
+                case DN:
+                    // keep is-null status
+            }
+            gn = resultGuard;
+            return;
+        }
+
+        if (that.isNull()) {
+            /*
+             * Same decisions as above (based on this-being-null and that-level) are now made based
+             * on (that-being-null and this-level). Because merge is commutative.
+             */
+            switch (level) {
+                case CLUELESS:
+                case NN:
+                    // lose is-null status, gain nothing
+                    level = LEVEL.CLUELESS;
+                    seen = null;
+                    break;
+                case CC:
+                    break;
+                case IO:
+                    // demote to check-cast
+                    level = LEVEL.CC;
+                    // keep this.seen as-is
+                    break;
+                case DN:
+                    // keep is-null status
+            }
+            gn = resultGuard;
+            return;
+        }
+
+        // by now we know neither this nor that are known-to-be-null
+        assert !isNull() && !that.isNull();
+
         // umbrella type over the observations from both witnesses
         ResolvedJavaType newSeen = (seen == null || that.seen == null) ? null : FlowUtil.widen(seen, that.seen);
 
-        // preserve guarding node only if matches other, otherwise settle on `merge`
-        final GuardingNode resultGuard = guard() == that.guard() ? guard() : merge;
-
         /*
          * guarantee on (both conformance and non-nullness) required from each input in order for
          * the result to be able to offer such guarantee