# HG changeset patch # User Miguel Garcia # Date 1399057513 -7200 # Node ID 01a8820c1228e7673848955d3de4412a6b9919d5 # Parent 09d721bcffe21c4983383ccdc2bee9a24e63c656 [flow-sensitive] minor refactorings for readability, documentation diff -r 09d721bcffe2 -r 01a8820c1228 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/BaseReduction.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/BaseReduction.java Fri May 02 11:04:51 2014 -0700 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/BaseReduction.java Fri May 02 21:05:13 2014 +0200 @@ -44,11 +44,16 @@ * disadvantages. *

* - * *

* This class makes available little more than a few fields and a few utility methods used * throughout the remaining components making up control-flow sensitive reductions. *

+ * + *

+ * The laundry-list of all flow-sensitive reductions is summarized in + * {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReduction} + *

+ * */ public abstract class BaseReduction extends PostOrderNodeIterator { @@ -83,6 +88,12 @@ this.deoptReason = deoptReason; } + /* + * TODO Actually, we want to emit instructions to signal "should-not-reach-here". An + * imperfect substitute (as done here) is emitting FixedGuard(false). + * "should-not-reach-here" would be better for the runtime error it raises, thus pointing to + * a bug in FlowSensitiveReduction (the code was reachable, after all). + */ public void doRewrite(LogicNode falseConstant) { StructuredGraph graph = fixed.graph(); // have to insert a FixedNode other than a ControlSinkNode diff -r 09d721bcffe2 -r 01a8820c1228 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/CheckCastReduction.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/CheckCastReduction.java Fri May 02 11:04:51 2014 -0700 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/CheckCastReduction.java Fri May 02 21:05:13 2014 +0200 @@ -41,6 +41,11 @@ * {@link com.oracle.graal.nodes.java.CheckCastNode}. *

* + *

+ * The laundry-list of all flow-sensitive reductions is summarized in + * {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReduction} + *

+ * * @see #visitCheckCastNode(com.oracle.graal.nodes.java.CheckCastNode) */ public abstract class CheckCastReduction extends GuardingPiReduction { @@ -51,17 +56,37 @@ /** *

- * This phase is able to refine the types of reference-values at use sites provided a - * {@link com.oracle.graal.nodes.extended.GuardingNode GuardingNode} is available witnessing - * that fact. + * Upon visiting a {@link com.oracle.graal.nodes.java.CheckCastNode}, based on flow-sensitive + * conditions, we need to determine whether: + *

*

* *

- * This method turns non-redundant {@link com.oracle.graal.nodes.java.CheckCastNode}s into - * {@link com.oracle.graal.nodes.GuardingPiNode}s. Once such lowering has been performed (during - * run N of this phase) follow-up runs attempt to further simplify the resulting node, see - * {@link EquationalReasoner#downcastGuardingPiNode(com.oracle.graal.nodes.GuardingPiNode, Witness)} - * and {@link #visitGuardingPiNode(com.oracle.graal.nodes.GuardingPiNode)} + * This method realizes the above by testing first for situations that require less work: + *

    + *
  1. the stamp of the subject deems the check-cast redundant or unsatisfiable (ie, + * always-succeeds or always-fails). A previous round of canonicalization takes care of this + * situation, however it can also arise due to consecutive runs of + * {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReductionPhase} without intervening + * {@link com.oracle.graal.phases.common.CanonicalizerPhase canonicalization}.
    2. + *
  2. + * flow-sensitive information reveals the subject to be null, trivially fulfilling the + * check-cast.
    3. + *
  3. + * flow-sensitive information reveals the subject to be narrower than it stamp says. If the + * narrower ("downcasted") value fulfills the check-cast, the check-cast is removed.
    4. + *
  4. + * otherwise the check-cast provides additional flow-sensitive information. For that, a + * {@link com.oracle.graal.nodes.FixedGuardNode} is needed, as described in + * {@link #lowerCheckCastAnchorFriendlyWay(com.oracle.graal.nodes.java.CheckCastNode, com.oracle.graal.nodes.ValueNode)} + * . Please notice this lowering is currently performed unconditionally: it might occur no + * flow-sensitive reduction is enabled down the road.
    5. + *
*

* *

@@ -155,19 +180,24 @@ * *

* Rather than tracking the CheckCastNode via {@link com.oracle.graal.phases.common.cfs.State - * State} (doing so woud add a special case because a + * State} (doing so would add a special case because a * {@link com.oracle.graal.nodes.java.CheckCastNode} isn't a - * {@link com.oracle.graal.nodes.extended.GuardingNode}) this method creates an anchor by - * lowering the CheckCastNode into a FixedGuardNode. Not the same way as done by - * {@link com.oracle.graal.nodes.java.CheckCastNode#lower(com.oracle.graal.nodes.spi.LoweringTool)} - * which lowers into a {@link com.oracle.graal.nodes.GuardingPiNode} (which is not a - * {@link com.oracle.graal.nodes.extended.GuardingNode}). + * {@link com.oracle.graal.nodes.extended.GuardingNode guarding node}) this method creates an + * anchor by lowering the CheckCastNode into a FixedGuardNode. Not the same as the + * {@link com.oracle.graal.nodes.java.CheckCastNode#lower(com.oracle.graal.nodes.spi.LoweringTool) + * lowering of a CheckCastNode} which results in a {@link com.oracle.graal.nodes.GuardingPiNode} + * (which is not a {@link com.oracle.graal.nodes.extended.GuardingNode guarding node}). *

* *

* With that, state tracking can proceed as usual. *

* + *

+ * TODO This lowering is currently performed unconditionally: it might occur no flow-sensitive + * reduction is enabled down the road + *

+ * * @see #visitCheckCastNode(com.oracle.graal.nodes.java.CheckCastNode) * */ diff -r 09d721bcffe2 -r 01a8820c1228 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 Fri May 02 11:04:51 2014 -0700 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/EquationalReasoner.java Fri May 02 21:05:13 2014 +0200 @@ -219,7 +219,7 @@ if (n == null) { return null; } - assert !(n instanceof GuardNode) : "This phase not yet ready to run during MidTier"; + assert !(n instanceof GuardNode) : "This phase not intended to run during MidTier"; if (!(n instanceof ValueNode)) { return n; } diff -r 09d721bcffe2 -r 01a8820c1228 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 Fri May 02 11:04:51 2014 -0700 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FixedGuardReduction.java Fri May 02 21:05:13 2014 +0200 @@ -33,6 +33,11 @@ * This class implements control-flow sensitive reductions for * {@link com.oracle.graal.nodes.FixedGuardNode}. *

+ * + *

+ * The laundry-list of all flow-sensitive reductions is summarized in + * {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReduction} + *

* * @see #visitFixedGuardNode(com.oracle.graal.nodes.FixedGuardNode) */ @@ -43,15 +48,33 @@ } /** - * In case the condition is constant, - * {@link com.oracle.graal.nodes.FixedGuardNode#simplify(com.oracle.graal.graph.spi.SimplifierTool) - * FixedGuardNode#simplify(SimplifierTool)} will eventually remove the - * {@link com.oracle.graal.nodes.FixedGuardNode} ("always succeeds") or kill the code that - * should be killed ("always fails"). + *

+ * Upon visiting a {@link com.oracle.graal.nodes.FixedGuardNode}, based on flow-sensitive + * conditions, we need to determine whether: + *

+ *

* *

- * The only thing we do here is tracking as true fact (from this program point onwards) the - * condition of the {@link com.oracle.graal.nodes.FixedGuardNode FixedGuardNode}. + * This method realizes the above by inspecting the + * {@link com.oracle.graal.nodes.FixedGuardNode}'s condition: + *

    + *
  1. a constant condition signals the node won't be reduced here
    2. + *
  2. the outcome of the condition can be predicted:
    3. + *
      + *
    • + * "always succeeds", after finding an equivalent (or stronger) + * {@link com.oracle.graal.nodes.extended.GuardingNode} in scope. The + * {@link com.oracle.graal.nodes.FixedGuardNode} is removed after replacing its usages with the + * existing guarding node
      • + *
    • + * "always fails", which warrants making that explicit by making the condition constant, see + * {@link #markFixedGuardNodeAlwaysFails(com.oracle.graal.nodes.FixedGuardNode)}
      • + *
    + *
  3. otherwise the condition is tracked flow-sensitively
    4. + *
*

* *

@@ -62,6 +85,8 @@ /* * A FixedGuardNode with LogicConstantNode condition is left untouched. + * `FixedGuardNode.simplify()` will eventually remove the FixedGuardNode (in case it + * "always succeeds") or kill code ("always fails"). */ if (f.condition() instanceof LogicConstantNode) { @@ -92,10 +117,10 @@ final boolean isTrue = !f.isNegated(); /* - * FixedGuardNode requires handling similar to that of GuardingPiNode, (ie the condition - * can't simply be deverbosified in place). A replacement anchor is needed, ie an anchor - * that amounts to the same combination of (negated, condition) for the FixedGuardNode at - * hand. + * 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 @@ -202,7 +227,8 @@ * Porcelain method. * *

- * The `replacement` guard must be such that it implies the `old` guard. + * The `replacement` guard must be such that it implies the `old` guard. Moreover, rhe + * `replacement` guard must be in scope. *

*/ private void removeFixedGuardNode(FixedGuardNode old, GuardingNode replacement) { diff -r 09d721bcffe2 -r 01a8820c1228 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FlowSensitiveReduction.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FlowSensitiveReduction.java Fri May 02 11:04:51 2014 -0700 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FlowSensitiveReduction.java Fri May 02 21:05:13 2014 +0200 @@ -43,20 +43,37 @@ /** *

- * All control-flow-sensitive reductions follow the common pattern of + * In a nutshell, {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReductionPhase} makes a + * single pass in dominator-based order over the graph: + *

    + *
  1. collecting properties of interest at control-splits; as well as for check-casts, + * guarding-pis, null-checks, and fixed-guards. Such flow-sensitive information is tracked via a + * dedicated {@link com.oracle.graal.phases.common.cfs.State state instance} for each control-flow + * path.
    2. + *
  2. performing rewritings that are safe at specific program-points. This comprises: *
      - *
    • Recognizing properties of interest (ie, LogicNode-s) at control-flow splits, as well as upon - * check-casts and fixed-guards.
      • - *
    • Using the information thus tracked to simplify - *
        - *
      • side-effects free expressions, via + *
      • simplification of side-effects free expressions, via * {@link com.oracle.graal.phases.common.cfs.EquationalReasoner#deverbosify(com.oracle.graal.graph.Node)} *
        • - *
      • control-flow, eg. by eliminating redundant fixed-guards and check-casts, ie which are known - * always to hold.
        • + *
      • simplification of control-flow: + *
          + *
        • + * by simplifying the input-condition to an {@link com.oracle.graal.nodes.IfNode}
          • + *
        • + * by eliminating redundant check-casts, guarding-pis, null-checks, and fixed-guards; where + * "redundancy" is determined using flow-sensitive information. In these cases, redundancy can be + * due to: + *
            + *
          • an equivalent, existing, guarding node is already in scope (thus, use it as replacement and + * remove the redundant one)
            • + *
          • "always fails" (thus, replace the node in question with FixedGuardNode(false))
            • *
          *
          • *
        + *
        • + *
      + *
      • + *
*

* * @see com.oracle.graal.phases.common.cfs.CheckCastReduction @@ -145,6 +162,9 @@ if (begin instanceof LoopExitNode) { state.clear(); + /* + * TODO return or not? (by not returning we agree it's ok to update the state as below) + */ } if (pred instanceof IfNode) { @@ -253,7 +273,7 @@ public boolean deverbosifyInputsInPlace(ValueNode parent) { boolean changed = false; for (ValueNode i : FlowUtil.distinctValueAndConditionInputs(parent)) { - assert !(i instanceof GuardNode) : "ConditionalElim shouldn't run in MidTier"; + assert !(i instanceof GuardNode) : "This phase not intended to run during MidTier"; ValueNode j = (ValueNode) reasoner.deverbosify(i); if (i != j) { changed = true; @@ -390,7 +410,7 @@ * Step 5: After special-case handling, we do our best for those FixedNode-s * where the effort to reduce their inputs might pay off. * - * Why is this useful? For example, by the time the AbstractBeginNode for an If-branch + * Why is this useful? For example, by the time the BeginNode for an If-branch * is visited (in general a ControlSplitNode), the If-condition will have gone already * through simplification (and thus potentially have been reduced to a * LogicConstantNode). @@ -407,8 +427,7 @@ paysOffToReduce = true; } - // TODO comb the remaining FixedWithNextNode subclasses, pick those with good changes of - // paying-off + // TODO comb remaining FixedWithNextNode subclasses, pick those with chances of paying-off // TODO UnsafeLoadNode takes a condition @@ -423,8 +442,7 @@ */ // TODO some nodes are GuardingNodes (eg, FixedAccessNode) we could use them to track state - // TODO others are additionally guarded (eg JavaReadNode), thus *their* guards could be - // simplified. + // TODO other nodes are guarded (eg JavaReadNode), thus *their* guards could be replaced. } @@ -498,11 +516,29 @@ } /** - * One or more arguments at `invoke` may have control-flow sensitive simplifications. In such - * case, a new {@link com.oracle.graal.nodes.java.MethodCallTargetNode MethodCallTargetNode} is - * prepared just for this callsite, consuming reduced arguments. This proves useful in - * connection with inlining, in order to specialize callees on the types of arguments other than - * the receiver (examples: multi-methods, the inlining problem, lambdas as arguments). + *

+ * For one or more `invoke` arguments, flow-sensitive information may suggest their narrowing or + * simplification. In those cases, a new + * {@link com.oracle.graal.nodes.java.MethodCallTargetNode MethodCallTargetNode} is prepared + * just for this callsite, consuming reduced arguments. + *

+ * + *

+ * Specializing the {@link com.oracle.graal.nodes.java.MethodCallTargetNode + * MethodCallTargetNode} as described above may enable two optimizations: + *

+ *

* *

* Precondition: inputs haven't been deverbosified yet. diff -r 09d721bcffe2 -r 01a8820c1228 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FlowUtil.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FlowUtil.java Fri May 02 11:04:51 2014 -0700 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FlowUtil.java Fri May 02 21:05:13 2014 +0200 @@ -23,10 +23,6 @@ package com.oracle.graal.phases.common.cfs; import com.oracle.graal.api.meta.ResolvedJavaType; -import com.oracle.graal.debug.Debug; -import com.oracle.graal.debug.DebugConfig; -import com.oracle.graal.debug.DebugConfigScope; -import com.oracle.graal.debug.internal.DebugScope; import com.oracle.graal.graph.InputType; import com.oracle.graal.graph.Node; import com.oracle.graal.graph.NodeClass; @@ -290,28 +286,4 @@ // `oldInput` if unused wil be removed in finished() } - public static StructuredGraph visualize(StructuredGraph graph, String title) { - DebugConfig debugConfig = DebugScope.getConfig(); - DebugConfig fixedConfig = Debug.fixedConfig(false, true, false, false, debugConfig.dumpHandlers(), debugConfig.output()); - try (DebugConfigScope s = Debug.setConfig(fixedConfig)) { - Debug.dump(graph, title); - - return graph; - } - } - - public static final String ANSI_RESET = "\u001B[0m"; - public static final String ANSI_BLACK = "\u001B[30m"; - public static final String ANSI_RED = "\u001B[31m"; - public static final String ANSI_GREEN = "\u001B[32m"; - public static final String ANSI_YELLOW = "\u001B[33m"; - public static final String ANSI_BLUE = "\u001B[34m"; - public static final String ANSI_PURPLE = "\u001B[35m"; - public static final String ANSI_CYAN = "\u001B[36m"; - public static final String ANSI_WHITE = "\u001B[37m"; - - public static void highlightInRed(String msg) { - System.out.println(ANSI_RED + msg + ANSI_RESET); - } - } diff -r 09d721bcffe2 -r 01a8820c1228 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/GuardingPiReduction.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/GuardingPiReduction.java Fri May 02 11:04:51 2014 -0700 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/GuardingPiReduction.java Fri May 02 21:05:13 2014 +0200 @@ -37,7 +37,12 @@ * This class implements control-flow sensitive reductions for * {@link com.oracle.graal.nodes.GuardingPiNode}. *

- * + * + *

+ * The laundry-list of all flow-sensitive reductions is summarized in + * {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReduction} + *

+ * * @see #visitGuardingPiNode(com.oracle.graal.nodes.GuardingPiNode) */ public abstract class GuardingPiReduction extends BaseReduction { @@ -139,6 +144,12 @@ FixedGuardNode fixedGuard = graph.add(new FixedGuardNode(envelope.condition(), envelope.getReason(), envelope.getAction(), envelope.isNegated())); graph.addBeforeFixed(envelope, fixedGuard); + /* + * + * TODO This lowering is currently performed unconditionally: it might occur no + * flow-sensitive reduction is enabled down the road + */ + if (!FlowUtil.lacksUsages(envelope)) { // not calling wrapInPiNode() because we don't want to rememberSubstitution() PiNode replacement = graph.unique(new PiNode(envelope.object(), envelope.stamp(), fixedGuard)); diff -r 09d721bcffe2 -r 01a8820c1228 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/Histogram.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/Histogram.java Fri May 02 11:04:51 2014 -0700 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/Histogram.java Fri May 02 21:05:13 2014 +0200 @@ -54,7 +54,7 @@ int percentOut = (int) (numCases / casesTotal * 100); String msg = prefix + String.format("%d iters in %4d cases (%2d %%)", entry.getKey(), numCases, percentOut); if (entry.getKey() > 3) { - FlowUtil.highlightInRed(msg); + highlightInRed(msg); } else { System.out.println(msg); } @@ -67,4 +67,11 @@ return (Histogram) super.clone(); } + public static final String ANSI_RESET = "\u001B[0m"; + public static final String ANSI_RED = "\u001B[31m"; + + public static void highlightInRed(String msg) { + System.out.println(ANSI_RED + msg + ANSI_RESET); + } + }