Mercurial > hg > truffle
changeset 15483:01a8820c1228
[flow-sensitive] minor refactorings for readability, documentation
line wrap: on
line diff
--- 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. * </p> * - * * <p> * 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. * </p> + * + * <p> + * The laundry-list of all flow-sensitive reductions is summarized in + * {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReduction} + * </p> + * */ public abstract class BaseReduction extends PostOrderNodeIterator<State> { @@ -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
--- 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}. * </p> * + * <p> + * The laundry-list of all flow-sensitive reductions is summarized in + * {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReduction} + * </p> + * * @see #visitCheckCastNode(com.oracle.graal.nodes.java.CheckCastNode) */ public abstract class CheckCastReduction extends GuardingPiReduction { @@ -51,17 +56,37 @@ /** * <p> - * 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: + * <ul> + * <li>it is redundant (in which case it should be simplified), or</li> + * <li>flow-sensitive information can be gained from it. "Gain information from it" requires + * lowering the {@link com.oracle.graal.nodes.java.CheckCastNode} such that a + * {@link com.oracle.graal.nodes.extended.GuardingNode GuardingNode} becomes available.</li> + * </ul> * </p> * * <p> - * 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: + * <ol> + * <li>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}.</li> + * <li> + * flow-sensitive information reveals the subject to be null, trivially fulfilling the + * check-cast.</li> + * <li> + * 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.</li> + * <li> + * 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.</li> + * </ol> * </p> * * <p> @@ -155,19 +180,24 @@ * * <p> * 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}). * </p> * * <p> * With that, state tracking can proceed as usual. * </p> * + * <p> + * TODO This lowering is currently performed unconditionally: it might occur no flow-sensitive + * reduction is enabled down the road + * </p> + * * @see #visitCheckCastNode(com.oracle.graal.nodes.java.CheckCastNode) * */
--- 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; }
--- 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}. * </p> + * + * <p> + * The laundry-list of all flow-sensitive reductions is summarized in + * {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReduction} + * </p> * * @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"). + * <p> + * Upon visiting a {@link com.oracle.graal.nodes.FixedGuardNode}, based on flow-sensitive + * conditions, we need to determine whether: + * <ul> + * <li>it is redundant (in which case it should be simplified), or</li> + * <li>flow-sensitive information can be gained from it.</li> + * </ul> + * </p> * * <p> - * 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: + * <ol> + * <li>a constant condition signals the node won't be reduced here</li> + * <li>the outcome of the condition can be predicted:</li> + * <ul> + * <li> + * "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</li> + * <li> + * "always fails", which warrants making that explicit by making the condition constant, see + * {@link #markFixedGuardNodeAlwaysFails(com.oracle.graal.nodes.FixedGuardNode)}</li> + * </ul> + * <li>otherwise the condition is tracked flow-sensitively</li> + * </ol> * </p> * * <p> @@ -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. * * <p> - * 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. * </p> */ private void removeFixedGuardNode(FixedGuardNode old, GuardingNode replacement) {
--- 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 @@ /** * <p> - * 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: + * <ol> + * <li>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.</li> + * <li>performing rewritings that are safe at specific program-points. This comprises: * <ul> - * <li>Recognizing properties of interest (ie, LogicNode-s) at control-flow splits, as well as upon - * check-casts and fixed-guards.</li> - * <li>Using the information thus tracked to simplify - * <ul> - * <li>side-effects free expressions, via + * <li>simplification of side-effects free expressions, via * {@link com.oracle.graal.phases.common.cfs.EquationalReasoner#deverbosify(com.oracle.graal.graph.Node)} * </li> - * <li>control-flow, eg. by eliminating redundant fixed-guards and check-casts, ie which are known - * always to hold.</li> + * <li>simplification of control-flow: + * <ul> + * <li> + * by simplifying the input-condition to an {@link com.oracle.graal.nodes.IfNode}</li> + * <li> + * 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: + * <ul> + * <li>an equivalent, existing, guarding node is already in scope (thus, use it as replacement and + * remove the redundant one)</li> + * <li>"always fails" (thus, replace the node in question with <code>FixedGuardNode(false)</code>)</li> * </ul> * </li> * </ul> + * </li> + * </ul> + * </li> + * </ol> * </p> * * @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). + * <p> + * 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. + * </p> + * + * <p> + * Specializing the {@link com.oracle.graal.nodes.java.MethodCallTargetNode + * MethodCallTargetNode} as described above may enable two optimizations: + * <ul> + * <li> + * devirtualization of an + * {@link com.oracle.graal.nodes.java.MethodCallTargetNode.InvokeKind#Interface} or + * {@link com.oracle.graal.nodes.java.MethodCallTargetNode.InvokeKind#Virtual} callsite + * (devirtualization made possible after narrowing the type of the receiver)</li> + * <li> + * (future work) actual-argument-aware inlining, ie, to specialize callees on the types of + * arguments other than the receiver (examples: multi-methods, the inlining problem, lambdas as + * arguments).</li> + * + * </ul> + * </p> * * <p> * Precondition: inputs haven't been deverbosified yet.
--- 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); - } - }
--- 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}. * </p> - * + * + * <p> + * The laundry-list of all flow-sensitive reductions is summarized in + * {@link com.oracle.graal.phases.common.cfs.FlowSensitiveReduction} + * </p> + * * @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));
--- 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); + } + }