--- a/src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.nodes/src/org/graalvm/compiler/nodes/IfNode.java Thu Oct 31 14:23:06 2019 -0700
+++ b/src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.nodes/src/org/graalvm/compiler/nodes/IfNode.java Thu Oct 31 16:54:16 2019 -0700
@@ -54,7 +54,6 @@
import org.graalvm.compiler.graph.NodeClass;
import org.graalvm.compiler.graph.NodeSourcePosition;
import org.graalvm.compiler.graph.iterators.NodeIterable;
-import org.graalvm.compiler.graph.spi.Canonicalizable;
import org.graalvm.compiler.graph.spi.Simplifiable;
import org.graalvm.compiler.graph.spi.SimplifierTool;
import org.graalvm.compiler.nodeinfo.InputType;
@@ -95,9 +94,6 @@
public final class IfNode extends ControlSplitNode implements Simplifiable, LIRLowerable, IterableNodeType, SwitchFoldable {
public static final NodeClass<IfNode> TYPE = NodeClass.create(IfNode.class);
- private static final int MAX_USAGE_COLOR_SET_SIZE = 64;
- private static final int MAX_FRAMESTATE_SEARCH_DEPTH = 4;
-
private static final CounterKey CORRECTED_PROBABILITIES = DebugContext.counter("CorrectedProbabilities");
@Successor AbstractBeginNode trueSuccessor;
@@ -297,10 +293,6 @@
return;
}
- if (splitIfAtPhi(tool)) {
- return;
- }
-
if (conditionalNodeOptimization(tool)) {
return;
}
@@ -1185,400 +1177,6 @@
}
/**
- * Take an if that is immediately dominated by a merge with a single phi and split off any paths
- * where the test would be statically decidable creating a new merge below the appropriate side
- * of the IfNode. Any undecidable tests will continue to use the original IfNode.
- *
- * @param tool
- */
- @SuppressWarnings("try")
- private boolean splitIfAtPhi(SimplifierTool tool) {
- if (!(predecessor() instanceof MergeNode)) {
- return false;
- }
- MergeNode merge = (MergeNode) predecessor();
- if (merge.forwardEndCount() == 1) {
- // Don't bother.
- return false;
- }
- if (merge.getUsageCount() != 1 || merge.phis().count() != 1) {
- // Don't trigger with multiple phis. Would require more rewiring.
- // Most of the time the additional phis are memory phis that are removed after
- // fixed read phase.
- return false;
- }
- if (graph().getGuardsStage().areFrameStatesAtSideEffects() && merge.stateAfter() == null) {
- return false;
- }
-
- PhiNode generalPhi = merge.phis().first();
- if (!(generalPhi instanceof ValuePhiNode)) {
- return false;
- }
-
- if (trueSuccessor().isUsedAsGuardInput() || falseSuccessor().isUsedAsGuardInput()) {
- return false;
- }
-
- ValuePhiNode phi = (ValuePhiNode) generalPhi;
-
- EconomicMap<Node, NodeColor> coloredNodes = EconomicMap.create(Equivalence.IDENTITY, 8);
-
- /*
- * Check that the condition uses the phi and that there is only one user of the condition
- * expression.
- */
- if (!conditionUses(condition(), phi, coloredNodes)) {
- return false;
- }
-
- if (!mayRemoveSplit(merge)) {
- return false;
- }
-
- LogicNode[] results = new LogicNode[merge.forwardEndCount()];
- boolean success = false;
- for (int i = 0; i < results.length; ++i) {
- ValueNode value = phi.valueAt(i);
- LogicNode curResult = computeCondition(tool, condition, phi, value);
- if (curResult != condition) {
- for (Node n : curResult.inputs()) {
- if (n instanceof ConstantNode || n instanceof ParameterNode || n instanceof FixedNode) {
- // Constant inputs or parameters or fixed nodes are OK.
- } else if (n == value) {
- // References to the value itself are also OK.
- } else {
- // Input may cause scheduling issues.
- curResult = condition;
- break;
- }
- }
- success = true;
- }
- results[i] = curResult;
- }
-
- if (!success) {
- return false;
- }
-
- for (Node usage : phi.usages()) {
- if (usage == merge.stateAfter()) {
- // This usage can be ignored, because it is directly in the state after.
- } else {
- NodeColor color = colorUsage(coloredNodes, usage, merge, this.trueSuccessor(), this.falseSuccessor());
- if (color == NodeColor.MIXED) {
- return false;
- }
- }
- }
-
- /*
- * We could additionally filter for the case that at least some of the Phi inputs or one of
- * the condition inputs are constants but there are cases where a non-constant is
- * simplifiable, usually where the stamp allows the question to be answered.
- */
-
- /* Each successor of the if gets a new merge if needed. */
- MergeNode trueMerge = null;
- MergeNode falseMerge = null;
- int i = 0;
- for (EndNode end : merge.forwardEnds().snapshot()) {
- ValueNode value = phi.valueAt(end);
- LogicNode result = results[i++];
- if (result instanceof LogicConstantNode) {
- if (((LogicConstantNode) result).getValue()) {
- if (trueMerge == null) {
- trueMerge = insertMerge(trueSuccessor(), phi, merge.stateAfter(), tool);
- replaceNodesInBranch(coloredNodes, NodeColor.TRUE_BRANCH, phi, trueMerge.phis().first());
- }
- trueMerge.phis().first().addInput(value);
- trueMerge.addForwardEnd(end);
- } else {
- if (falseMerge == null) {
- falseMerge = insertMerge(falseSuccessor(), phi, merge.stateAfter(), tool);
- replaceNodesInBranch(coloredNodes, NodeColor.FALSE_BRANCH, phi, falseMerge.phis().first());
- }
- falseMerge.phis().first().addInput(value);
- falseMerge.addForwardEnd(end);
- }
- merge.removeEnd(end);
- } else if (result != condition) {
- // Build a new IfNode using the new condition
- BeginNode trueBegin = graph().add(new BeginNode());
- trueBegin.setNodeSourcePosition(trueSuccessor().getNodeSourcePosition());
- BeginNode falseBegin = graph().add(new BeginNode());
- falseBegin.setNodeSourcePosition(falseSuccessor().getNodeSourcePosition());
-
- if (result.graph() == null) {
- result = graph().addOrUniqueWithInputs(result);
- result.setNodeSourcePosition(condition.getNodeSourcePosition());
- }
- IfNode newIfNode = graph().add(new IfNode(result, trueBegin, falseBegin, trueSuccessorProbability));
- newIfNode.setNodeSourcePosition(getNodeSourcePosition());
-
- if (trueMerge == null) {
- trueMerge = insertMerge(trueSuccessor(), phi, merge.stateAfter(), tool);
- replaceNodesInBranch(coloredNodes, NodeColor.TRUE_BRANCH, phi, trueMerge.phis().first());
- }
- trueMerge.phis().first().addInput(value);
- trueBegin.setNext(graph().add(new EndNode()));
- trueMerge.addForwardEnd((EndNode) trueBegin.next());
-
- if (falseMerge == null) {
- falseMerge = insertMerge(falseSuccessor(), phi, merge.stateAfter(), tool);
- replaceNodesInBranch(coloredNodes, NodeColor.FALSE_BRANCH, phi, falseMerge.phis().first());
- }
- falseMerge.phis().first().addInput(value);
- falseBegin.setNext(graph().add(new EndNode()));
- falseMerge.addForwardEnd((EndNode) falseBegin.next());
-
- merge.removeEnd(end);
- ((FixedWithNextNode) end.predecessor()).setNext(newIfNode);
- end.safeDelete();
- }
- }
-
- cleanupMerge(merge);
- cleanupMerge(trueMerge);
- cleanupMerge(falseMerge);
-
- return true;
- }
-
- private static void replaceNodesInBranch(EconomicMap<Node, NodeColor> coloredNodes, NodeColor branch, ValuePhiNode phi, ValueNode newValue) {
- for (Node n : phi.usages().snapshot()) {
- if (coloredNodes.get(n) == branch) {
- n.replaceAllInputs(phi, newValue);
- } else if (coloredNodes.get(n) == NodeColor.PHI_MIXED) {
- assert n instanceof PhiNode;
- PhiNode phiNode = (PhiNode) n;
- AbstractMergeNode merge = phiNode.merge();
- for (int i = 0; i < merge.forwardEndCount(); ++i) {
- if (phiNode.valueAt(i) == phi && coloredNodes.get(merge.forwardEndAt(i)) == branch) {
- phiNode.setValueAt(i, newValue);
- }
- }
- }
- }
- }
-
- private NodeColor colorUsage(EconomicMap<Node, NodeColor> coloredNodes, Node node, MergeNode merge, AbstractBeginNode trueSucc, AbstractBeginNode falseSucc) {
- NodeColor color = coloredNodes.get(node);
- if (color == null) {
-
- if (coloredNodes.size() >= MAX_USAGE_COLOR_SET_SIZE) {
- return NodeColor.MIXED;
- }
-
- coloredNodes.put(node, NodeColor.MIXED);
-
- if (node == merge) {
- color = NodeColor.MIXED;
- } else if (node == trueSucc) {
- color = NodeColor.TRUE_BRANCH;
- } else if (node == falseSucc) {
- color = NodeColor.FALSE_BRANCH;
- } else {
- if (node instanceof AbstractMergeNode) {
- AbstractMergeNode mergeNode = (AbstractMergeNode) node;
- NodeColor combinedColor = null;
- for (int i = 0; i < mergeNode.forwardEndCount(); ++i) {
- NodeColor curColor = colorUsage(coloredNodes, mergeNode.forwardEndAt(i), merge, trueSucc, falseSucc);
- if (combinedColor == null) {
- combinedColor = curColor;
- } else if (combinedColor != curColor) {
- combinedColor = NodeColor.MIXED;
- break;
- }
- }
- color = combinedColor;
- } else if (node instanceof StartNode) {
- color = NodeColor.MIXED;
- } else if (node instanceof FixedNode) {
- FixedNode fixedNode = (FixedNode) node;
- Node predecessor = fixedNode.predecessor();
- assert predecessor != null : fixedNode;
- color = colorUsage(coloredNodes, predecessor, merge, trueSucc, falseSucc);
- } else if (node instanceof PhiNode) {
- PhiNode phiNode = (PhiNode) node;
- AbstractMergeNode phiMerge = phiNode.merge();
-
- if (phiMerge instanceof LoopBeginNode) {
- color = colorUsage(coloredNodes, phiMerge, merge, trueSucc, falseSucc);
- } else {
-
- for (int i = 0; i < phiMerge.forwardEndCount(); ++i) {
- NodeColor curColor = colorUsage(coloredNodes, phiMerge.forwardEndAt(i), merge, trueSucc, falseSucc);
- if (curColor != NodeColor.TRUE_BRANCH && curColor != NodeColor.FALSE_BRANCH) {
- color = NodeColor.MIXED;
- break;
- }
- }
-
- if (color == null) {
- // Each of the inputs to the phi are either coming unambigously from
- // true or false branch.
- color = NodeColor.PHI_MIXED;
- assert node instanceof PhiNode;
- }
- }
- } else {
- NodeColor combinedColor = null;
- for (Node n : node.usages()) {
- if (n != node) {
- NodeColor curColor = colorUsage(coloredNodes, n, merge, trueSucc, falseSucc);
- if (combinedColor == null) {
- combinedColor = curColor;
- } else if (combinedColor != curColor) {
- combinedColor = NodeColor.MIXED;
- break;
- }
- }
- }
- if (combinedColor == NodeColor.PHI_MIXED) {
- combinedColor = NodeColor.MIXED;
- }
- if (combinedColor == null) {
- // Floating node without usages => association unclear.
- combinedColor = NodeColor.MIXED;
- }
- color = combinedColor;
- }
- }
-
- assert color != null : node;
- coloredNodes.put(node, color);
- }
- return color;
- }
-
- /**
- * @param condition
- * @param phi
- * @param coloredNodes
- * @return true if the passed in {@code condition} uses {@code phi} and the condition is only
- * used once. Since the phi will go dead the condition using it will also have to be
- * dead after the optimization.
- */
- private static boolean conditionUses(LogicNode condition, PhiNode phi, EconomicMap<Node, NodeColor> coloredNodes) {
- if (!condition.hasExactlyOneUsage()) {
- return false;
- }
- if (condition instanceof ShortCircuitOrNode) {
- if (condition.graph().getGuardsStage().areDeoptsFixed()) {
- /*
- * It can be unsafe to simplify a ShortCircuitOr before deopts are fixed because
- * conversion to guards assumes that all the required conditions are being tested.
- * Simplfying the condition based on context before this happens may lose a
- * condition.
- */
- ShortCircuitOrNode orNode = (ShortCircuitOrNode) condition;
- return (conditionUses(orNode.x, phi, coloredNodes) || conditionUses(orNode.y, phi, coloredNodes));
- }
- } else if (condition instanceof Canonicalizable.Unary<?>) {
- Canonicalizable.Unary<?> unary = (Canonicalizable.Unary<?>) condition;
- if (unary.getValue() == phi) {
- coloredNodes.put(condition, NodeColor.CONDITION_USAGE);
- return true;
- }
- } else if (condition instanceof Canonicalizable.Binary<?>) {
- Canonicalizable.Binary<?> binary = (Canonicalizable.Binary<?>) condition;
- if (binary.getX() == phi || binary.getY() == phi) {
- coloredNodes.put(condition, NodeColor.CONDITION_USAGE);
- return true;
- }
- }
- return false;
- }
-
- /**
- * Canonicalize {@code} condition using {@code value} in place of {@code phi}.
- *
- * @param tool
- * @param condition
- * @param phi
- * @param value
- * @return an improved LogicNode or the original condition
- */
- @SuppressWarnings("unchecked")
- private static LogicNode computeCondition(SimplifierTool tool, LogicNode condition, PhiNode phi, Node value) {
- if (condition instanceof ShortCircuitOrNode) {
- if (condition.graph().getGuardsStage().areDeoptsFixed() && !condition.graph().isAfterExpandLogic()) {
- ShortCircuitOrNode orNode = (ShortCircuitOrNode) condition;
- LogicNode resultX = computeCondition(tool, orNode.x, phi, value);
- LogicNode resultY = computeCondition(tool, orNode.y, phi, value);
- if (resultX != orNode.x || resultY != orNode.y) {
- LogicNode result = orNode.canonical(tool, resultX, resultY);
- if (result != orNode) {
- return result;
- }
- /*
- * Create a new node to carry the optimized inputs.
- */
- ShortCircuitOrNode newOr = new ShortCircuitOrNode(resultX, orNode.xNegated, resultY,
- orNode.yNegated, orNode.getShortCircuitProbability());
- return newOr.canonical(tool);
- }
- return orNode;
- }
- } else if (condition instanceof Canonicalizable.Binary<?>) {
- Canonicalizable.Binary<Node> compare = (Canonicalizable.Binary<Node>) condition;
- if (compare.getX() == phi || compare.getY() == phi) {
- return (LogicNode) compare.canonical(tool, compare.getX() == phi ? value : compare.getX(), compare.getY() == phi ? value : compare.getY());
- }
- } else if (condition instanceof Canonicalizable.Unary<?>) {
- Canonicalizable.Unary<Node> compare = (Canonicalizable.Unary<Node>) condition;
- if (compare.getValue() == phi) {
- return (LogicNode) compare.canonical(tool, value);
- }
- }
- if (condition instanceof Canonicalizable) {
- return (LogicNode) ((Canonicalizable) condition).canonical(tool);
- }
- return condition;
- }
-
- private void cleanupMerge(MergeNode merge) {
- if (merge != null && merge.isAlive()) {
- if (merge.forwardEndCount() == 0) {
- GraphUtil.killCFG(merge);
- } else if (merge.forwardEndCount() == 1) {
- graph().reduceTrivialMerge(merge);
- }
- }
- }
-
- @SuppressWarnings("try")
- private MergeNode insertMerge(AbstractBeginNode begin, ValuePhiNode oldPhi, FrameState stateAfter, SimplifierTool tool) {
- MergeNode merge = graph().add(new MergeNode());
-
- AbstractBeginNode newBegin;
- try (DebugCloseable position = begin.withNodeSourcePosition()) {
- newBegin = graph().add(new BeginNode());
- begin.replaceAtPredecessor(newBegin);
- newBegin.setNext(begin);
- }
-
- FixedNode next = newBegin.next();
- next.replaceAtPredecessor(merge);
- newBegin.setNext(graph().add(new EndNode()));
- merge.addForwardEnd((EndNode) newBegin.next());
-
- ValuePhiNode phi = begin.graph().addOrUnique(new ValuePhiNode(oldPhi.stamp(NodeView.DEFAULT), merge));
- phi.addInput(oldPhi);
-
- if (stateAfter != null) {
- FrameState newState = stateAfter.duplicate();
- newState.replaceAllInputs(oldPhi, phi);
- merge.setStateAfter(newState);
- }
- merge.setNext(next);
- tool.addToWorkList(begin);
- return merge;
- }
-
- /**
* Tries to connect code that initializes a variable directly with the successors of an if
* construct that switches on the variable. For example, the pseudo code below:
*
@@ -1709,7 +1307,7 @@
return false;
}
- if (!mayRemoveSplit(merge)) {
+ if (merge.stateAfter() != null && !GraphUtil.mayRemoveSplit(this)) {
return false;
}
@@ -1771,15 +1369,6 @@
return true;
}
- private boolean mayRemoveSplit(AbstractMergeNode merge) {
-
- if (merge.stateAfter() != null && (!checkFrameState(trueSuccessor, MAX_FRAMESTATE_SEARCH_DEPTH) || !checkFrameState(trueSuccessor, MAX_FRAMESTATE_SEARCH_DEPTH))) {
- return false;
- }
-
- return true;
- }
-
private static void propagateZeroProbability(FixedNode startNode) {
Node prev = null;
for (FixedNode node : GraphUtil.predecessorIterable(startNode)) {
@@ -1817,53 +1406,6 @@
}
/**
- * Snippet lowerings may produce patterns without a frame state on the merge. We need to take
- * extra care when optimizing these patterns.
- */
- private static boolean checkFrameState(FixedNode start, int maxDepth) {
- if (maxDepth == 0) {
- return false;
- }
- FixedNode node = start;
- while (true) {
- if (node instanceof AbstractMergeNode) {
- AbstractMergeNode mergeNode = (AbstractMergeNode) node;
- if (mergeNode.stateAfter() == null) {
- return false;
- } else {
- return true;
- }
- } else if (node instanceof StateSplit) {
- StateSplit stateSplitNode = (StateSplit) node;
- if (stateSplitNode.stateAfter() != null) {
- return true;
- }
- }
-
- if (node instanceof ControlSplitNode) {
- ControlSplitNode controlSplitNode = (ControlSplitNode) node;
- for (Node succ : controlSplitNode.cfgSuccessors()) {
- if (checkFrameState((FixedNode) succ, maxDepth - 1)) {
- return true;
- }
- }
- return false;
- } else if (node instanceof FixedWithNextNode) {
- FixedWithNextNode fixedWithNextNode = (FixedWithNextNode) node;
- node = fixedWithNextNode.next();
- } else if (node instanceof AbstractEndNode) {
- AbstractEndNode endNode = (AbstractEndNode) node;
- node = endNode.merge();
- } else if (node instanceof ControlSinkNode) {
- return true;
- } else {
- assert false : "unexpected node";
- return false;
- }
- }
- }
-
- /**
* Connects a set of ends to a given successor, inserting a merge node if there is more than one
* end. If {@code ends} is not empty, then {@code successor} is added to {@code tool}'s
* {@linkplain SimplifierTool#addToWorkList(org.graalvm.compiler.graph.Node) work list}.