# HG changeset patch # User Miguel Garcia # Date 1399560293 -7200 # Node ID 5699bb48a436693be4868b84ba3cace8f13d29ed # Parent de3dca7cc6fdacb51b5232e24328f6600f21727c [flow-sensitive] consolidating nullness-tracking in typeRefinements diff -r de3dca7cc6fd -r 5699bb48a436 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 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 @@ /** *

- * 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. *

* *

- * 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. *

* */ private Map typeRefinements; - Map knownNull; Map trueFacts; Map falseFacts; public State() { this.typeRefinements = newNodeIdentityMap(); - this.knownNull = newNodeIdentityMap(); this.trueFacts = newNodeIdentityMap(); this.falseFacts = newNodeIdentityMap(); } @@ -134,7 +128,6 @@ for (Map.Entry 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 mergeKnownNull(MergeNode merge, ArrayList withReachableStates) { - // newKnownNull starts empty - Map newKnownNull = newNodeIdentityMap(); - for (Map.Entry 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; - } - /** *

* 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. *

*/ - private void mergePhis(MergeNode merge, List withStates, Map newKnownPhiTypes, Map newKnownNullPhis) { + private void mergePhis(MergeNode merge, List withStates, Map 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 newKnownTypes = mergeKnownTypes(merge, withReachableStates); // may also get updated in a moment, during processing of phi nodes. - Map 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; } /** diff -r de3dca7cc6fd -r 5699bb48a436 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/Witness.java --- 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 - * isNull() . - */ 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