Mercurial > hg > graal-compiler
changeset 14863:ea712c41c5a2
merge unsigned compare guards with constant indexes or limits
author | Tom Rodriguez <tom.rodriguez@oracle.com> |
---|---|
date | Thu, 27 Mar 2014 22:17:54 -0700 |
parents | 0e713dba33bb |
children | 8e7667515e31 ae7cbf13e765 |
files | graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/meta/HotSpotLoweringProvider.java graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/NewObjectSnippets.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/StampTool.java graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ConditionalEliminationPhase.java |
diffstat | 4 files changed, 233 insertions(+), 14 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/meta/HotSpotLoweringProvider.java Thu Mar 27 16:38:39 2014 -0700 +++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/meta/HotSpotLoweringProvider.java Thu Mar 27 22:17:54 2014 -0700 @@ -763,6 +763,15 @@ arrayLength = readArrayLength; } + if (arrayLength.isConstant() && n.index().isConstant()) { + int l = arrayLength.asConstant().asInt(); + int i = n.index().asConstant().asInt(); + if (i >= 0 && i < l) { + // unneeded range check + return null; + } + } + return tool.createGuard(n, g.unique(new IntegerBelowThanNode(n.index(), arrayLength)), BoundsCheckException, InvalidateReprofile); }
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/NewObjectSnippets.java Thu Mar 27 16:38:39 2014 -0700 +++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/NewObjectSnippets.java Thu Mar 27 22:17:54 2014 -0700 @@ -276,7 +276,7 @@ } /** - * Maximum number of long stores to emit when zeroing an object with a constant size Larger + * Maximum number of long stores to emit when zeroing an object with a constant size. Larger * objects have their bodies initialized in a loop. */ private static final int MAX_UNROLLED_OBJECT_ZEROING_STORES = 8;
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/StampTool.java Thu Mar 27 16:38:39 2014 -0700 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/StampTool.java Thu Mar 27 22:17:54 2014 -0700 @@ -462,4 +462,41 @@ } return v; } + + /** + * Compute the stamp resulting from the unsigned comparison being true. + * + * @return null if it's can't be true or it nothing useful can be encoded. + */ + public static Stamp unsignedCompare(Stamp stamp, Stamp stamp2) { + IntegerStamp x = (IntegerStamp) stamp; + IntegerStamp y = (IntegerStamp) stamp2; + if (x == x.unrestricted() && y == y.unrestricted()) { + // Don't know anything. + return null; + } + // c <| n, where c is a constant and n is known to be positive. + if (x.lowerBound() == x.upperBound()) { + if (y.isPositive()) { + if (x.lowerBound() == (1 << x.getBits()) - 1) { + // Constant is MAX_VALUE which must fail. + return null; + } + if (x.lowerBound() <= y.lowerBound()) { + // Test will fail. Return illegalStamp instead? + return null; + } + // If the test succeeds then this proves that n is at greater than c so the bounds + // are [c+1..-n.upperBound)]. + return StampFactory.forInteger(x.getBits(), false, x.lowerBound() + 1, y.upperBound()); + } + return null; + } + // n <| c, where c is a strictly positive constant + if (y.lowerBound() == y.upperBound() && y.isStrictlyPositive()) { + // The test proves that n is positive and less than c, [0..c-1] + return StampFactory.forInteger(y.getBits(), false, 0, y.lowerBound() - 1); + } + return null; + } }
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ConditionalEliminationPhase.java Thu Mar 27 16:38:39 2014 -0700 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ConditionalEliminationPhase.java Thu Mar 27 22:17:54 2014 -0700 @@ -27,6 +27,7 @@ import com.oracle.graal.api.meta.*; import com.oracle.graal.debug.*; +import com.oracle.graal.debug.Debug.Scope; import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.PhiNode.PhiType; @@ -63,7 +64,40 @@ @Override protected void run(StructuredGraph inputGraph) { graph = inputGraph; - new ConditionalElimination(graph.start(), new State()).apply(); + try (Scope s = Debug.scope("ConditionalElimination")) { + new ConditionalElimination(graph.start(), new State()).apply(); + } catch (Throwable e) { + throw Debug.handle(e); + } + } + + /** + * Type information about a {@code value} that it produced by a {@code guard}. Usage of the + * stamp information requires adopting the guard. Usually this means replacing an existing guard + * with this guard. + */ + static class GuardedStamp { + private final ValueNode value; + private final Stamp stamp; + private final GuardNode guard; + + GuardedStamp(ValueNode value, Stamp stamp, GuardNode guard) { + this.value = value; + this.stamp = stamp; + this.guard = guard; + } + + public Stamp getStamp() { + return stamp; + } + + public GuardNode getGuard() { + return guard; + } + + public ValueNode getValue() { + return value; + } } public static class State extends MergeableState<State> implements Cloneable { @@ -73,6 +107,7 @@ private HashSet<ValueNode> knownNull; private IdentityHashMap<LogicNode, ValueNode> trueConditions; private IdentityHashMap<LogicNode, ValueNode> falseConditions; + private IdentityHashMap<ValueNode, GuardedStamp> valueConstraints; public State() { this.knownTypes = new IdentityHashMap<>(); @@ -80,6 +115,7 @@ this.knownNull = new HashSet<>(); this.trueConditions = new IdentityHashMap<>(); this.falseConditions = new IdentityHashMap<>(); + this.valueConstraints = new IdentityHashMap<>(); } public State(State other) { @@ -88,6 +124,7 @@ this.knownNull = new HashSet<>(other.knownNull); this.trueConditions = new IdentityHashMap<>(other.trueConditions); this.falseConditions = new IdentityHashMap<>(other.falseConditions); + this.valueConstraints = new IdentityHashMap<>(other.valueConstraints); } @Override @@ -95,6 +132,7 @@ IdentityHashMap<ValueNode, ResolvedJavaType> newKnownTypes = new IdentityHashMap<>(); IdentityHashMap<LogicNode, ValueNode> newTrueConditions = new IdentityHashMap<>(); IdentityHashMap<LogicNode, ValueNode> newFalseConditions = new IdentityHashMap<>(); + IdentityHashMap<ValueNode, GuardedStamp> newValueConstraints = new IdentityHashMap<>(); HashSet<ValueNode> newKnownNull = new HashSet<>(knownNull); HashSet<ValueNode> newKnownNonNull = new HashSet<>(knownNonNull); @@ -191,6 +229,7 @@ this.knownNull = newKnownNull; this.trueConditions = newTrueConditions; this.falseConditions = newFalseConditions; + this.valueConstraints = newValueConstraints; return true; } @@ -404,32 +443,145 @@ } } - private void registerGuard(GuardNode guard) { + private GuardedStamp computeGuardedStamp(GuardNode guard) { + if (guard.condition() instanceof IntegerBelowThanNode) { + if (guard.negated()) { + // Not sure how to reason about negated guards + return null; + } + IntegerBelowThanNode below = (IntegerBelowThanNode) guard.condition(); + if (below.x().getKind() == Kind.Int && below.x().isConstant() && !below.y().isConstant()) { + Stamp stamp = StampTool.unsignedCompare(below.x().stamp(), below.y().stamp()); + if (stamp != null) { + return new GuardedStamp(below.y(), stamp, guard); + } + } + if (below.y().getKind() == Kind.Int && below.y().isConstant() && !below.x().isConstant()) { + Stamp stamp = StampTool.unsignedCompare(below.x().stamp(), below.y().stamp()); + if (stamp != null) { + return new GuardedStamp(below.x(), stamp, guard); + } + } + } + return null; + } + + private boolean eliminateTrivialGuard(GuardNode guard) { LogicNode condition = guard.condition(); ValueNode existingGuards = guard.negated() ? state.falseConditions.get(condition) : state.trueConditions.get(condition); if (existingGuards != null) { - guard.replaceAtUsages(existingGuards); - GraphUtil.killWithUnusedFloatingInputs(guard); - metricGuardsRemoved.increment(); + eliminateGuard(guard, existingGuards); + return true; } else { ValueNode anchor = state.trueConditions.get(condition); if (anchor != null) { if (!guard.negated()) { - guard.replaceAtUsages(anchor); - metricGuardsRemoved.increment(); - GraphUtil.killWithUnusedFloatingInputs(guard); + eliminateGuard(guard, anchor); + return true; } } else { anchor = state.falseConditions.get(condition); if (anchor != null) { if (guard.negated()) { - guard.replaceAtUsages(anchor); - metricGuardsRemoved.increment(); - GraphUtil.killWithUnusedFloatingInputs(guard); + eliminateGuard(guard, anchor); + return true; } + } + } + } + // Can't be eliminated so accumulate any type information from the guard + registerConditionalStamp(guard); + return false; + } + + /** + * Replace {@code guard} with {@code anchor} . + * + * @param guard The guard to eliminate. + * @param anchor Node to replace the guard. + */ + private void eliminateGuard(GuardNode guard, ValueNode anchor) { + guard.replaceAtUsages(anchor); + metricGuardsRemoved.increment(); + GraphUtil.killWithUnusedFloatingInputs(guard); + } + + /** + * See if a conditional type constraint can prove this guard. + * + * @param guard + * @return true if the guard was eliminated. + */ + private boolean testImpliedGuard(GuardNode guard) { + if (state.valueConstraints.size() == 0) { + // Nothing to do. + return false; + } + + GuardNode existingGuard = null; + if (guard.condition() instanceof IntegerBelowThanNode) { + IntegerBelowThanNode below = (IntegerBelowThanNode) guard.condition(); + IntegerStamp xStamp = (IntegerStamp) below.x().stamp(); + IntegerStamp yStamp = (IntegerStamp) below.y().stamp(); + GuardedStamp cstamp = state.valueConstraints.get(below.x()); + if (cstamp != null) { + xStamp = (IntegerStamp) cstamp.getStamp(); + } else { + cstamp = state.valueConstraints.get(below.y()); + if (cstamp != null) { + yStamp = (IntegerStamp) cstamp.getStamp(); + } + } + if (cstamp != null) { + if (cstamp.getGuard() == guard) { + // found ourselves + return false; + } + // See if we can use the other guard + if (!guard.negated() && !cstamp.getGuard().negated() && yStamp.isPositive()) { + if (xStamp.isPositive() && xStamp.upperBound() < yStamp.lowerBound()) { + // Proven true + existingGuard = cstamp.getGuard(); + Debug.log("existing guard %s %1s proves %1s", existingGuard, existingGuard.condition(), guard.condition()); + } else if (xStamp.isStrictlyNegative() || xStamp.lowerBound() >= yStamp.upperBound()) { + // An earlier guard proves that this will always fail but it's probably + // not worth trying to use it. + } + } + } + } + + if (existingGuard != null) { + // Found a guard which proves this guard to be true, so replace it. + eliminateGuard(guard, existingGuard); + return true; + } + return false; + } + + private void registerConditionalStamp(GuardNode guard) { + GuardedStamp conditional = computeGuardedStamp(guard); + if (conditional != null) { + GuardedStamp other = state.valueConstraints.get(conditional.getValue()); + if (other == null) { + state.valueConstraints.put(conditional.getValue(), conditional); + } else if (guard.negated() != other.getGuard().negated()) { + // This seems impossible + // Debug.log("negated and !negated guards %1s %1s", guard, other.getGuard()); + } else if (!guard.negated()) { + // two different constraints, pick the one with the tightest type + // information + Stamp result = conditional.getStamp().join(other.getStamp()); + if (result == conditional.getStamp()) { + Debug.log("%1s overrides existing value %1s", guard.condition(), other.getGuard().condition()); + state.valueConstraints.put(conditional.getValue(), conditional); + } else if (result == other.getStamp()) { + // existing type constraint is best + Debug.log("existing value is best %s", other.getGuard()); } else { - registerCondition(!guard.negated(), condition, guard); + // The merger produced some combination of values + Debug.log("type merge produced new type %s", result); } } } @@ -494,8 +646,29 @@ if (pred != null) { registerControlSplitInfo(pred, begin); } + + // First eliminate any guards which can be trivially removed and register any + // type constraints the guards produce. for (GuardNode guard : begin.guards().snapshot()) { - registerGuard(guard); + eliminateTrivialGuard(guard); + } + + // Collect the guards which have produced conditional stamps. + HashSet<GuardNode> provers = new HashSet<>(); + for (Map.Entry<ValueNode, GuardedStamp> e : state.valueConstraints.entrySet()) { + provers.add(e.getValue().getGuard()); + } + + // Process the remaining guards. Guards which produced some type constraint should + // just be registered since they aren't trivially deleteable. Test the other guards + // to see if they can be deleted using type constraints. + for (GuardNode guard : begin.guards().snapshot()) { + if (provers.contains(guard) || !testImpliedGuard(guard)) { + registerCondition(!guard.negated(), guard.condition(), guard); + } + } + for (GuardNode guard : provers) { + assert !testImpliedGuard(guard) : "provers shouldn't be trivially eliminatable"; } } else if (node instanceof FixedGuardNode) { FixedGuardNode guard = (FixedGuardNode) node;