/*
 * Copyright (c) 2009, 2020, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */


package org.graalvm.compiler.nodes;

import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_1;
import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.Objects;

import jdk.internal.vm.compiler.collections.EconomicMap;
import jdk.internal.vm.compiler.collections.Equivalence;
import org.graalvm.compiler.bytecode.BytecodeDisassembler;
import org.graalvm.compiler.bytecode.Bytecodes;
import org.graalvm.compiler.bytecode.Bytes;
import org.graalvm.compiler.bytecode.ResolvedJavaMethodBytecode;
import org.graalvm.compiler.core.common.calc.Condition;
import org.graalvm.compiler.core.common.type.FloatStamp;
import org.graalvm.compiler.core.common.type.IntegerStamp;
import org.graalvm.compiler.core.common.type.PrimitiveStamp;
import org.graalvm.compiler.core.common.type.Stamp;
import org.graalvm.compiler.core.common.type.StampFactory;
import org.graalvm.compiler.debug.CounterKey;
import org.graalvm.compiler.debug.DebugCloseable;
import org.graalvm.compiler.debug.DebugContext;
import org.graalvm.compiler.debug.GraalError;
import org.graalvm.compiler.graph.IterableNodeType;
import org.graalvm.compiler.graph.Node;
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.Simplifiable;
import org.graalvm.compiler.graph.spi.SimplifierTool;
import org.graalvm.compiler.nodeinfo.InputType;
import org.graalvm.compiler.nodeinfo.NodeInfo;
import org.graalvm.compiler.nodes.calc.AddNode;
import org.graalvm.compiler.nodes.calc.CompareNode;
import org.graalvm.compiler.nodes.calc.ConditionalNode;
import org.graalvm.compiler.nodes.calc.FloatNormalizeCompareNode;
import org.graalvm.compiler.nodes.calc.IntegerBelowNode;
import org.graalvm.compiler.nodes.calc.IntegerEqualsNode;
import org.graalvm.compiler.nodes.calc.IntegerLessThanNode;
import org.graalvm.compiler.nodes.calc.IntegerNormalizeCompareNode;
import org.graalvm.compiler.nodes.calc.IsNullNode;
import org.graalvm.compiler.nodes.calc.ObjectEqualsNode;
import org.graalvm.compiler.nodes.cfg.Block;
import org.graalvm.compiler.nodes.extended.UnboxNode;
import org.graalvm.compiler.nodes.java.InstanceOfNode;
import org.graalvm.compiler.nodes.java.LoadFieldNode;
import org.graalvm.compiler.nodes.spi.LIRLowerable;
import org.graalvm.compiler.nodes.spi.NodeLIRBuilderTool;
import org.graalvm.compiler.nodes.spi.SwitchFoldable;
import org.graalvm.compiler.nodes.util.GraphUtil;

import jdk.vm.ci.code.CodeUtil;
import jdk.vm.ci.meta.Constant;
import jdk.vm.ci.meta.JavaConstant;
import jdk.vm.ci.meta.JavaKind;
import jdk.vm.ci.meta.MetaAccessProvider;
import jdk.vm.ci.meta.PrimitiveConstant;
import jdk.vm.ci.meta.ResolvedJavaMethod;
import jdk.vm.ci.meta.ResolvedJavaType;
import jdk.vm.ci.meta.TriState;

The IfNode represents a branch that can go one of two directions depending on the outcome of a comparison.
/** * The {@code IfNode} represents a branch that can go one of two directions depending on the outcome * of a comparison. */
@NodeInfo(cycles = CYCLES_1, size = SIZE_2, sizeRationale = "2 jmps") public final class IfNode extends ControlSplitNode implements Simplifiable, LIRLowerable, IterableNodeType, SwitchFoldable { public static final NodeClass<IfNode> TYPE = NodeClass.create(IfNode.class); private static final CounterKey CORRECTED_PROBABILITIES = DebugContext.counter("CorrectedProbabilities"); /* * Any change to successor fields (reordering, renaming, adding or removing) would need an * according update to SimplifyingGraphDecoder#earlyCanonicalization. */ @Successor AbstractBeginNode trueSuccessor; @Successor AbstractBeginNode falseSuccessor; @Input(InputType.Condition) LogicNode condition; protected double trueSuccessorProbability; public LogicNode condition() { return condition; } public void setCondition(LogicNode x) { updateUsages(condition, x); condition = x; } public IfNode(LogicNode condition, FixedNode trueSuccessor, FixedNode falseSuccessor, double trueSuccessorProbability) { this(condition, BeginNode.begin(trueSuccessor), BeginNode.begin(falseSuccessor), trueSuccessorProbability); } public IfNode(LogicNode condition, AbstractBeginNode trueSuccessor, AbstractBeginNode falseSuccessor, double trueSuccessorProbability) { super(TYPE, StampFactory.forVoid()); this.condition = condition; this.falseSuccessor = falseSuccessor; this.trueSuccessor = trueSuccessor; setTrueSuccessorProbability(trueSuccessorProbability); }
Gets the true successor.
Returns:the true successor
/** * Gets the true successor. * * @return the true successor */
public AbstractBeginNode trueSuccessor() { return trueSuccessor; }
Gets the false successor.
Returns:the false successor
/** * Gets the false successor. * * @return the false successor */
public AbstractBeginNode falseSuccessor() { return falseSuccessor; } public double getTrueSuccessorProbability() { return this.trueSuccessorProbability; } public void setTrueSuccessor(AbstractBeginNode node) { updatePredecessor(trueSuccessor, node); trueSuccessor = node; } public void setFalseSuccessor(AbstractBeginNode node) { updatePredecessor(falseSuccessor, node); falseSuccessor = node; }
Gets the node corresponding to the specified outcome of the branch.
Params:
  • istrue – true if the true successor is requested, false otherwise
Returns:the corresponding successor
/** * Gets the node corresponding to the specified outcome of the branch. * * @param istrue {@code true} if the true successor is requested, {@code false} otherwise * @return the corresponding successor */
public AbstractBeginNode successor(boolean istrue) { return istrue ? trueSuccessor : falseSuccessor; } public void setTrueSuccessorProbability(double prob) { assert prob >= -0.000000001 && prob <= 1.000000001 : "Probability out of bounds: " + prob; trueSuccessorProbability = Math.min(1.0, Math.max(0.0, prob)); } @Override public double probability(AbstractBeginNode successor) { return successor == trueSuccessor ? trueSuccessorProbability : 1 - trueSuccessorProbability; } @Override public void generate(NodeLIRBuilderTool gen) { gen.emitIf(this); } @Override public boolean verify() { assertTrue(condition() != null, "missing condition"); assertTrue(trueSuccessor() != null, "missing trueSuccessor"); assertTrue(falseSuccessor() != null, "missing falseSuccessor"); return super.verify(); } private boolean compareCallContext(NodeSourcePosition successorPosition) { NodeSourcePosition position = getNodeSourcePosition(); NodeSourcePosition successor = successorPosition; while (position != null) { assertTrue(Objects.equals(position.getMethod(), successor.getMethod()), "method mismatch"); position = position.getCaller(); successor = successor.getCaller(); } assertTrue(successor == null, "successor position has more methods"); return true; } @Override public boolean verifySourcePosition() { NodeSourcePosition sourcePosition = getNodeSourcePosition(); assertTrue(sourcePosition != null, "missing IfNode source position"); NodeSourcePosition trueSuccessorPosition = trueSuccessor.getNodeSourcePosition(); assertTrue(trueSuccessorPosition != null, "missing IfNode true successor source position"); NodeSourcePosition falseSuccessorPosition = falseSuccessor.getNodeSourcePosition(); assertTrue(falseSuccessorPosition != null, "missing IfNode false successor source position"); int bci = sourcePosition.getBCI(); ResolvedJavaMethod method = sourcePosition.getMethod(); int bytecode = BytecodeDisassembler.getBytecodeAt(method, bci); if (!Bytecodes.isIfBytecode(bytecode)) { return true; } byte[] code = (new ResolvedJavaMethodBytecode(method)).getCode(); int targetBCI = bci + Bytes.beS2(code, bci + 1); int nextBCI = bci + Bytecodes.lengthOf(bytecode); // At least one successor should have the correct BCI to indicate any possible negation that // occurred after bytecode parsing boolean matchingSuccessorFound = false; if (trueSuccessorPosition.getBCI() == nextBCI || trueSuccessorPosition.getBCI() == targetBCI) { assertTrue(compareCallContext(trueSuccessorPosition), "call context different from IfNode in trueSuccessor"); matchingSuccessorFound = true; } if (falseSuccessorPosition.getBCI() == nextBCI || falseSuccessorPosition.getBCI() == targetBCI) { assertTrue(compareCallContext(falseSuccessorPosition), "call context different from IfNode in falseSuccessor"); matchingSuccessorFound = true; } assertTrue(matchingSuccessorFound, "no matching successor position found in IfNode"); assertTrue(trueSuccessorPosition.getBCI() != falseSuccessorPosition.getBCI(), "successor positions same in IfNode"); return true; } public void eliminateNegation() { AbstractBeginNode oldTrueSuccessor = trueSuccessor; AbstractBeginNode oldFalseSuccessor = falseSuccessor; trueSuccessor = oldFalseSuccessor; falseSuccessor = oldTrueSuccessor; trueSuccessorProbability = 1 - trueSuccessorProbability; setCondition(((LogicNegationNode) condition).getValue()); } @Override public void simplify(SimplifierTool tool) { if (trueSuccessor().next() instanceof DeoptimizeNode) { if (trueSuccessorProbability != 0) { CORRECTED_PROBABILITIES.increment(getDebug()); trueSuccessorProbability = 0; } } else if (falseSuccessor().next() instanceof DeoptimizeNode) { if (trueSuccessorProbability != 1) { CORRECTED_PROBABILITIES.increment(getDebug()); trueSuccessorProbability = 1; } } if (condition() instanceof LogicNegationNode) { eliminateNegation(); } if (condition() instanceof LogicConstantNode) { LogicConstantNode c = (LogicConstantNode) condition(); if (c.getValue()) { tool.deleteBranch(falseSuccessor()); tool.addToWorkList(trueSuccessor()); graph().removeSplit(this, trueSuccessor()); } else { tool.deleteBranch(trueSuccessor()); tool.addToWorkList(falseSuccessor()); graph().removeSplit(this, falseSuccessor()); } return; } if (tool.allUsagesAvailable() && trueSuccessor().hasNoUsages() && falseSuccessor().hasNoUsages()) { pushNodesThroughIf(tool); if (checkForUnsignedCompare(tool) || removeOrMaterializeIf(tool)) { return; } } if (removeIntermediateMaterialization(tool)) { return; } if (conditionalNodeOptimization(tool)) { return; } if (switchTransformationOptimization(tool)) { return; } if (falseSuccessor().hasNoUsages() && (!(falseSuccessor() instanceof LoopExitNode)) && falseSuccessor().next() instanceof IfNode && !(((IfNode) falseSuccessor().next()).falseSuccessor() instanceof LoopExitNode)) { AbstractBeginNode intermediateBegin = falseSuccessor(); IfNode nextIf = (IfNode) intermediateBegin.next(); double probabilityB = (1.0 - this.trueSuccessorProbability) * nextIf.trueSuccessorProbability; if (this.trueSuccessorProbability < probabilityB) { // Reordering of those two if statements is beneficial from the point of view of // their probabilities. if (prepareForSwap(tool, condition(), nextIf.condition())) { // Reordering is allowed from (if1 => begin => if2) to (if2 => begin => if1). assert intermediateBegin.next() == nextIf; AbstractBeginNode bothFalseBegin = nextIf.falseSuccessor(); nextIf.setFalseSuccessor(null); intermediateBegin.setNext(null); this.setFalseSuccessor(null); this.replaceAtPredecessor(nextIf); nextIf.setFalseSuccessor(intermediateBegin); intermediateBegin.setNext(this); this.setFalseSuccessor(bothFalseBegin); NodeSourcePosition intermediateBeginPosition = intermediateBegin.getNodeSourcePosition(); intermediateBegin.setNodeSourcePosition(bothFalseBegin.getNodeSourcePosition()); bothFalseBegin.setNodeSourcePosition(intermediateBeginPosition); nextIf.setTrueSuccessorProbability(probabilityB); if (probabilityB == 1.0) { this.setTrueSuccessorProbability(0.0); } else { double newProbability = this.trueSuccessorProbability / (1.0 - probabilityB); this.setTrueSuccessorProbability(Math.min(1.0, newProbability)); } return; } } } if (tryEliminateBoxedReferenceEquals(tool)) { return; } } private static boolean isUnboxedFrom(MetaAccessProvider meta, NodeView view, ValueNode x, ValueNode src) { if (x == src) { return true; } else if (x instanceof UnboxNode) { return isUnboxedFrom(meta, view, ((UnboxNode) x).getValue(), src); } else if (x instanceof PiNode) { PiNode pi = (PiNode) x; return isUnboxedFrom(meta, view, pi.getOriginalNode(), src); } else if (x instanceof LoadFieldNode) { LoadFieldNode load = (LoadFieldNode) x; ResolvedJavaType integerType = meta.lookupJavaType(Integer.class); if (load.getValue().stamp(view).javaType(meta).equals(integerType)) { return isUnboxedFrom(meta, view, load.getValue(), src); } else { return false; } } else { return false; } }
Attempts to replace the following pattern:
Integer x = ...;
Integer y = ...;
if ((x == y) || x.equals(y)) { ... }
with:
Integer x = ...;
Integer y = ...;
if (x.equals(y)) { ... }
whenever the probability that the reference check will pass is relatively small. See GR-1315 for more information.
/** * Attempts to replace the following pattern: * * <pre> * Integer x = ...; * Integer y = ...; * if ((x == y) || x.equals(y)) { ... } * </pre> * * with: * * <pre> * Integer x = ...; * Integer y = ...; * if (x.equals(y)) { ... } * </pre> * * whenever the probability that the reference check will pass is relatively small. * * See GR-1315 for more information. */
private boolean tryEliminateBoxedReferenceEquals(SimplifierTool tool) { if (!(condition instanceof ObjectEqualsNode)) { return false; } MetaAccessProvider meta = tool.getMetaAccess(); ObjectEqualsNode equalsCondition = (ObjectEqualsNode) condition; ValueNode x = equalsCondition.getX(); ValueNode y = equalsCondition.getY(); ResolvedJavaType integerType = meta.lookupJavaType(Integer.class); // At least one argument for reference equal must be a boxed primitive. NodeView view = NodeView.from(tool); if (!x.stamp(view).javaType(meta).equals(integerType) && !y.stamp(view).javaType(meta).equals(integerType)) { return false; } // The reference equality check is usually more efficient compared to a boxing check. // The success of the reference equals must therefore be relatively rare, otherwise it makes // no sense to eliminate it. if (getTrueSuccessorProbability() > 0.4) { return false; } // True branch must be empty. if (trueSuccessor instanceof BeginNode || trueSuccessor instanceof LoopExitNode) { if (trueSuccessor.next() instanceof EndNode) { // Empty true branch. } else { return false; } } else { return false; } // False branch must only check the unboxed values. UnboxNode unbox = null; FixedGuardNode unboxCheck = null; for (FixedNode node : falseSuccessor.getBlockNodes()) { if (!(node instanceof BeginNode || node instanceof UnboxNode || node instanceof FixedGuardNode || node instanceof EndNode || node instanceof LoadFieldNode || node instanceof LoopExitNode)) { return false; } if (node instanceof UnboxNode) { if (unbox == null) { unbox = (UnboxNode) node; } else { return false; } } if (!(node instanceof FixedGuardNode)) { continue; } FixedGuardNode fixed = (FixedGuardNode) node; if (!(fixed.condition() instanceof IntegerEqualsNode)) { continue; } IntegerEqualsNode equals = (IntegerEqualsNode) fixed.condition(); if ((isUnboxedFrom(meta, view, equals.getX(), x) && isUnboxedFrom(meta, view, equals.getY(), y)) || (isUnboxedFrom(meta, view, equals.getX(), y) && isUnboxedFrom(meta, view, equals.getY(), x))) { unboxCheck = fixed; } } if (unbox == null || unboxCheck == null) { return false; } // Falsify the reference check. setCondition(graph().addOrUniqueWithInputs(LogicConstantNode.contradiction())); return true; } // SwitchFoldable implementation. @Override public Node getNextSwitchFoldableBranch() { return falseSuccessor(); } @Override public boolean isInSwitch(ValueNode switchValue) { return SwitchFoldable.maybeIsInSwitch(condition()) && SwitchFoldable.sameSwitchValue(condition(), switchValue); } @Override public void cutOffCascadeNode() { setTrueSuccessor(null); } @Override public void cutOffLowestCascadeNode() { setFalseSuccessor(null); setTrueSuccessor(null); } @Override public AbstractBeginNode getDefault() { return falseSuccessor(); } @Override public ValueNode switchValue() { if (SwitchFoldable.maybeIsInSwitch(condition())) { return ((IntegerEqualsNode) condition()).getX(); } return null; } @Override public boolean isNonInitializedProfile() { return getTrueSuccessorProbability() == 0.5d; } @Override public int intKeyAt(int i) { assert i == 0; return ((IntegerEqualsNode) condition()).getY().asJavaConstant().asInt(); } @Override public double keyProbability(int i) { assert i == 0; return getTrueSuccessorProbability(); } @Override public AbstractBeginNode keySuccessor(int i) { assert i == 0; return trueSuccessor(); } @Override public double defaultProbability() { return 1.0d - getTrueSuccessorProbability(); }
Try to optimize this as if it were a ConditionalNode.
/** * Try to optimize this as if it were a {@link ConditionalNode}. */
private boolean conditionalNodeOptimization(SimplifierTool tool) { if (trueSuccessor().next() instanceof AbstractEndNode && falseSuccessor().next() instanceof AbstractEndNode) { AbstractEndNode trueEnd = (AbstractEndNode) trueSuccessor().next(); AbstractEndNode falseEnd = (AbstractEndNode) falseSuccessor().next(); if (trueEnd.merge() != falseEnd.merge()) { return false; } if (!(trueEnd.merge() instanceof MergeNode)) { return false; } MergeNode merge = (MergeNode) trueEnd.merge(); if (!merge.hasExactlyOneUsage() || merge.phis().count() != 1) { return false; } if (trueSuccessor().hasAnchored() || falseSuccessor().hasAnchored()) { return false; } if (falseSuccessor instanceof LoopExitNode && ((LoopExitNode) falseSuccessor).stateAfter != null) { return false; } PhiNode phi = merge.phis().first(); ValueNode falseValue = phi.valueAt(falseEnd); ValueNode trueValue = phi.valueAt(trueEnd); NodeView view = NodeView.from(tool); ValueNode result = ConditionalNode.canonicalizeConditional(condition, trueValue, falseValue, phi.stamp(view), view); if (result != null) { /* * canonicalizeConditional returns possibly new nodes so add them to the graph. */ if (result.graph() == null) { result = graph().addOrUniqueWithInputs(result); } result = proxyReplacement(result); /* * This optimization can be performed even if multiple values merge at this phi * since the two inputs get simplified into one. */ phi.setValueAt(trueEnd, result); removeThroughFalseBranch(tool, merge); return true; } } return false; } private void pushNodesThroughIf(SimplifierTool tool) { assert trueSuccessor().hasNoUsages() && falseSuccessor().hasNoUsages(); // push similar nodes upwards through the if, thereby deduplicating them do { AbstractBeginNode trueSucc = trueSuccessor(); AbstractBeginNode falseSucc = falseSuccessor(); if (trueSucc instanceof BeginNode && falseSucc instanceof BeginNode && trueSucc.next() instanceof FixedWithNextNode && falseSucc.next() instanceof FixedWithNextNode) { FixedWithNextNode trueNext = (FixedWithNextNode) trueSucc.next(); FixedWithNextNode falseNext = (FixedWithNextNode) falseSucc.next(); NodeClass<?> nodeClass = trueNext.getNodeClass(); if (trueNext.getClass() == falseNext.getClass()) { if (trueNext instanceof AbstractBeginNode) { // Cannot do this optimization for begin nodes, because it could // move guards above the if that need to stay below a branch. } else if (nodeClass.equalInputs(trueNext, falseNext) && trueNext.valueEquals(falseNext)) { falseNext.replaceAtUsages(trueNext); graph().removeFixed(falseNext); GraphUtil.unlinkFixedNode(trueNext); graph().addBeforeFixed(this, trueNext); for (Node usage : trueNext.usages().snapshot()) { if (usage.isAlive()) { NodeClass<?> usageNodeClass = usage.getNodeClass(); if (usageNodeClass.valueNumberable() && !usageNodeClass.isLeafNode()) { Node newNode = graph().findDuplicate(usage); if (newNode != null) { usage.replaceAtUsagesAndDelete(newNode); } } if (usage.isAlive()) { tool.addToWorkList(usage); } } } continue; } } } break; } while (true); }
Recognize a couple patterns that can be merged into an unsigned compare.
Params:
  • tool –
Returns:true if a replacement was done.
/** * Recognize a couple patterns that can be merged into an unsigned compare. * * @param tool * @return true if a replacement was done. */
@SuppressWarnings("try") private boolean checkForUnsignedCompare(SimplifierTool tool) { assert trueSuccessor().hasNoUsages() && falseSuccessor().hasNoUsages(); if (condition() instanceof IntegerLessThanNode) { NodeView view = NodeView.from(tool); IntegerLessThanNode lessThan = (IntegerLessThanNode) condition(); Constant y = lessThan.getY().stamp(view).asConstant(); if (y instanceof PrimitiveConstant && ((PrimitiveConstant) y).asLong() == 0 && falseSuccessor().next() instanceof IfNode) { IfNode ifNode2 = (IfNode) falseSuccessor().next(); if (ifNode2.condition() instanceof IntegerLessThanNode) { IntegerLessThanNode lessThan2 = (IntegerLessThanNode) ifNode2.condition(); AbstractBeginNode falseSucc = ifNode2.falseSuccessor(); AbstractBeginNode trueSucc = ifNode2.trueSuccessor(); IntegerBelowNode below = null; /* * Convert x >= 0 && x < positive which is represented as !(x < 0) && x < * <positive> into an unsigned compare. */ if (lessThan2.getX() == lessThan.getX() && lessThan2.getY().stamp(view) instanceof IntegerStamp && ((IntegerStamp) lessThan2.getY().stamp(view)).isPositive() && sameDestination(trueSuccessor(), ifNode2.falseSuccessor)) { below = graph().unique(new IntegerBelowNode(lessThan2.getX(), lessThan2.getY())); // swap direction AbstractBeginNode tmp = falseSucc; falseSucc = trueSucc; trueSucc = tmp; } else if (lessThan2.getY() == lessThan.getX() && sameDestination(trueSuccessor(), ifNode2.trueSuccessor)) { /* * Convert x >= 0 && x <= positive which is represented as !(x < 0) && * !(<positive> > x), into x <| positive + 1. This can only be done for * constants since there isn't a IntegerBelowEqualThanNode but that doesn't * appear to be interesting. */ JavaConstant positive = lessThan2.getX().asJavaConstant(); if (positive != null && positive.asLong() > 0 && positive.asLong() < positive.getJavaKind().getMaxValue()) { ConstantNode newLimit = ConstantNode.forIntegerStamp(lessThan2.getX().stamp(view), positive.asLong() + 1, graph()); below = graph().unique(new IntegerBelowNode(lessThan.getX(), newLimit)); } } if (below != null) { try (DebugCloseable position = ifNode2.withNodeSourcePosition()) { ifNode2.setTrueSuccessor(null); ifNode2.setFalseSuccessor(null); IfNode newIfNode = graph().add(new IfNode(below, falseSucc, trueSucc, 1 - trueSuccessorProbability)); // Remove the < 0 test. tool.deleteBranch(trueSuccessor); graph().removeSplit(this, falseSuccessor); // Replace the second test with the new one. ifNode2.predecessor().replaceFirstSuccessor(ifNode2, newIfNode); ifNode2.safeDelete(); return true; } } } } else if (y instanceof PrimitiveConstant && ((PrimitiveConstant) y).asLong() < 0 && falseSuccessor().next() instanceof IfNode) { IfNode ifNode2 = (IfNode) falseSuccessor().next(); AbstractBeginNode falseSucc = ifNode2.falseSuccessor(); AbstractBeginNode trueSucc = ifNode2.trueSuccessor(); IntegerBelowNode below = null; if (ifNode2.condition() instanceof IntegerLessThanNode) { ValueNode x = lessThan.getX(); IntegerLessThanNode lessThan2 = (IntegerLessThanNode) ifNode2.condition(); /* * Convert x >= -C1 && x < C2, represented as !(x < -C1) && x < C2, into an * unsigned compare. This condition is equivalent to x + C1 |<| C1 + C2 if C1 + * C2 does not overflow. */ Constant c2 = lessThan2.getY().stamp(view).asConstant(); if (lessThan2.getX() == x && c2 instanceof PrimitiveConstant && ((PrimitiveConstant) c2).asLong() > 0 && x.stamp(view).isCompatible(lessThan.getY().stamp(view)) && x.stamp(view).isCompatible(lessThan2.getY().stamp(view)) && sameDestination(trueSuccessor(), ifNode2.falseSuccessor)) { long newLimitValue = -((PrimitiveConstant) y).asLong() + ((PrimitiveConstant) c2).asLong(); // Make sure the limit fits into the target type without overflow. if (newLimitValue > 0 && newLimitValue <= CodeUtil.maxValue(PrimitiveStamp.getBits(x.stamp(view)))) { ConstantNode newLimit = ConstantNode.forIntegerStamp(x.stamp(view), newLimitValue, graph()); ConstantNode c1 = ConstantNode.forIntegerStamp(x.stamp(view), -((PrimitiveConstant) y).asLong(), graph()); ValueNode addNode = graph().addOrUniqueWithInputs(AddNode.create(x, c1, view)); below = graph().unique(new IntegerBelowNode(addNode, newLimit)); } } } if (below != null) { try (DebugCloseable position = ifNode2.withNodeSourcePosition()) { ifNode2.setTrueSuccessor(null); ifNode2.setFalseSuccessor(null); IfNode newIfNode = graph().add(new IfNode(below, trueSucc, falseSucc, trueSuccessorProbability)); // Remove the < -C1 test. tool.deleteBranch(trueSuccessor); graph().removeSplit(this, falseSuccessor); // Replace the second test with the new one. ifNode2.predecessor().replaceFirstSuccessor(ifNode2, newIfNode); ifNode2.safeDelete(); return true; } } } } return false; }
Check it these two blocks end up at the same place. Meeting at the same merge, or deoptimizing in the same way.
/** * Check it these two blocks end up at the same place. Meeting at the same merge, or * deoptimizing in the same way. */
public static boolean sameDestination(AbstractBeginNode succ1, AbstractBeginNode succ2) { Node next1 = succ1.next(); Node next2 = succ2.next(); if (next1 instanceof AbstractEndNode && next2 instanceof AbstractEndNode) { AbstractEndNode end1 = (AbstractEndNode) next1; AbstractEndNode end2 = (AbstractEndNode) next2; if (end1.merge() == end2.merge()) { for (PhiNode phi : end1.merge().phis()) { if (phi.valueAt(end1) != phi.valueAt(end2)) { return false; } } // They go to the same MergeNode and merge the same values return true; } } else if (next1 instanceof DeoptimizeNode && next2 instanceof DeoptimizeNode) { DeoptimizeNode deopt1 = (DeoptimizeNode) next1; DeoptimizeNode deopt2 = (DeoptimizeNode) next2; if (deopt1.getReason() == deopt2.getReason() && deopt1.getAction() == deopt2.getAction()) { // Same deoptimization reason and action. return true; } } else if (next1 instanceof LoopExitNode && next2 instanceof LoopExitNode) { LoopExitNode exit1 = (LoopExitNode) next1; LoopExitNode exit2 = (LoopExitNode) next2; if (exit1.loopBegin() == exit2.loopBegin() && exit1.stateAfter() == exit2.stateAfter() && exit1.stateAfter() == null && sameDestination(exit1, exit2)) { // Exit the same loop and end up at the same place. return true; } } else if (next1 instanceof ReturnNode && next2 instanceof ReturnNode) { ReturnNode exit1 = (ReturnNode) next1; ReturnNode exit2 = (ReturnNode) next2; if (exit1.result() == exit2.result()) { // Exit the same loop and end up at the same place. return true; } } return false; } private static boolean prepareForSwap(SimplifierTool tool, LogicNode a, LogicNode b) { DebugContext debug = a.getDebug(); if (a instanceof InstanceOfNode) { InstanceOfNode instanceOfA = (InstanceOfNode) a; if (b instanceof IsNullNode) { IsNullNode isNullNode = (IsNullNode) b; if (isNullNode.getValue() == instanceOfA.getValue()) { debug.log("Can swap instanceof and isnull if"); return true; } } else if (b instanceof InstanceOfNode) { InstanceOfNode instanceOfB = (InstanceOfNode) b; if (instanceOfA.getValue() == instanceOfB.getValue() && !instanceOfA.type().getType().isInterface() && !instanceOfB.type().getType().isInterface() && !instanceOfA.type().getType().isAssignableFrom(instanceOfB.type().getType()) && !instanceOfB.type().getType().isAssignableFrom(instanceOfA.type().getType())) { // Two instanceof on the same value with mutually exclusive types. debug.log("Can swap instanceof for types %s and %s", instanceOfA.type(), instanceOfB.type()); return true; } } } else if (a instanceof CompareNode) { CompareNode compareA = (CompareNode) a; Condition conditionA = compareA.condition().asCondition(); if (compareA.unorderedIsTrue()) { return false; } if (b instanceof CompareNode) { CompareNode compareB = (CompareNode) b; if (compareA == compareB) { debug.log("Same conditions => do not swap and leave the work for global value numbering."); return false; } if (compareB.unorderedIsTrue()) { return false; } Condition comparableCondition = null; Condition conditionB = compareB.condition().asCondition(); if (compareB.getX() == compareA.getX() && compareB.getY() == compareA.getY()) { comparableCondition = conditionB; } else if (compareB.getX() == compareA.getY() && compareB.getY() == compareA.getX()) { comparableCondition = conditionB.mirror(); } if (comparableCondition != null) { if (conditionA.trueIsDisjoint(comparableCondition)) { // The truth of the two conditions is disjoint => can reorder. debug.log("Can swap disjoint coditions on same values: %s and %s", conditionA, comparableCondition); return true; } } else if (conditionA == Condition.EQ && conditionB == Condition.EQ) { boolean canSwap = false; if ((compareA.getX() == compareB.getX() && valuesDistinct(tool, compareA.getY(), compareB.getY()))) { canSwap = true; } else if ((compareA.getX() == compareB.getY() && valuesDistinct(tool, compareA.getY(), compareB.getX()))) { canSwap = true; } else if ((compareA.getY() == compareB.getX() && valuesDistinct(tool, compareA.getX(), compareB.getY()))) { canSwap = true; } else if ((compareA.getY() == compareB.getY() && valuesDistinct(tool, compareA.getX(), compareB.getX()))) { canSwap = true; } if (canSwap) { debug.log("Can swap equality condition with one shared and one disjoint value."); return true; } } } } return false; } private static boolean valuesDistinct(SimplifierTool tool, ValueNode a, ValueNode b) { if (a.isConstant() && b.isConstant()) { Boolean equal = tool.getConstantReflection().constantEquals(a.asConstant(), b.asConstant()); if (equal != null) { return !equal.booleanValue(); } } NodeView view = NodeView.from(tool); Stamp stampA = a.stamp(view); Stamp stampB = b.stamp(view); return stampA.alwaysDistinct(stampB); }
Tries to remove an empty if construct or replace an if construct with a materialization.
Returns:true if a transformation was made, false otherwise
/** * Tries to remove an empty if construct or replace an if construct with a materialization. * * @return true if a transformation was made, false otherwise */
private boolean removeOrMaterializeIf(SimplifierTool tool) { assert trueSuccessor().hasNoUsages() && falseSuccessor().hasNoUsages(); if (trueSuccessor().next() instanceof AbstractEndNode && falseSuccessor().next() instanceof AbstractEndNode) { AbstractEndNode trueEnd = (AbstractEndNode) trueSuccessor().next(); AbstractEndNode falseEnd = (AbstractEndNode) falseSuccessor().next(); AbstractMergeNode merge = trueEnd.merge(); if (falseSuccessor instanceof LoopExitNode && ((LoopExitNode) falseSuccessor).stateAfter != null) { return false; } if (merge == falseEnd.merge() && trueSuccessor().anchored().isEmpty() && falseSuccessor().anchored().isEmpty()) { PhiNode singlePhi = null; int distinct = 0; for (PhiNode phi : merge.phis()) { ValueNode trueValue = phi.valueAt(trueEnd); ValueNode falseValue = phi.valueAt(falseEnd); if (trueValue != falseValue) { distinct++; singlePhi = phi; } } if (distinct == 0) { /* * Multiple phis but merging same values for true and false, so simply delete * the path */ removeThroughFalseBranch(tool, merge); return true; } else if (distinct == 1) { // Fortify: Suppress Null Dereference false positive assert singlePhi != null; ValueNode trueValue = singlePhi.valueAt(trueEnd); ValueNode falseValue = singlePhi.valueAt(falseEnd); ValueNode conditional = canonicalizeConditionalCascade(tool, trueValue, falseValue); if (conditional != null) { conditional = proxyReplacement(conditional); singlePhi.setValueAt(trueEnd, conditional); removeThroughFalseBranch(tool, merge); return true; } } } } if (trueSuccessor().next() instanceof ReturnNode && falseSuccessor().next() instanceof ReturnNode) { ReturnNode trueEnd = (ReturnNode) trueSuccessor().next(); ReturnNode falseEnd = (ReturnNode) falseSuccessor().next(); ValueNode trueValue = trueEnd.result(); ValueNode falseValue = falseEnd.result(); ValueNode value = null; boolean needsProxy = false; if (trueValue != null) { if (trueValue == falseValue) { value = trueValue; } else { value = canonicalizeConditionalCascade(tool, trueValue, falseValue); if (value == null) { return false; } needsProxy = true; } } if (trueSuccessor() instanceof LoopExitNode) { FrameState stateAfter = ((LoopExitNode) trueSuccessor()).stateAfter(); LoopBeginNode loopBegin = ((LoopExitNode) trueSuccessor()).loopBegin(); assert loopBegin == ((LoopExitNode) falseSuccessor()).loopBegin(); LoopExitNode loopExitNode = graph().add(new LoopExitNode(loopBegin)); loopExitNode.setStateAfter(stateAfter); graph().addBeforeFixed(this, loopExitNode); if (graph().hasValueProxies() && needsProxy) { value = graph().addOrUnique(new ValueProxyNode(value, loopExitNode)); } } ReturnNode newReturn = graph().add(new ReturnNode(value)); replaceAtPredecessor(newReturn); GraphUtil.killCFG(this); return true; } return false; } private ValueNode proxyReplacement(ValueNode replacement) { /* * Special case: Every empty diamond we collapse to a conditional node can potentially * contain loop exit nodes on both branches. See the graph below: The two loop exits * (instanceof begin node) exit the same loop. The resulting phi is defined outside the * loop, but the resulting conditional node will be inside the loop, so we need to proxy the * resulting conditional node. Callers of this method ensure that true and false successor * have no usages, therefore a and b in the graph below can never be proxies themselves. */ // @formatter:off // +--+ // |If| // +--+ +-----+ +-----+ // +----+ +----+ | a | | b | // |Lex | |Lex | +----^+ +^----+ // +----+ +----+ | | // +-------+ +---+ // | Merge +---------+Phi| // +-------+ +---+ // @formatter:on if (this.graph().hasValueProxies()) { if (trueSuccessor instanceof LoopExitNode && falseSuccessor instanceof LoopExitNode) { assert ((LoopExitNode) trueSuccessor).loopBegin() == ((LoopExitNode) falseSuccessor).loopBegin(); /* * we can collapse all proxy nodes on one loop exit, the surviving one, which will * be the true successor */ if (falseSuccessor.anchored().isEmpty() && falseSuccessor.hasUsages()) { for (Node n : falseSuccessor.usages().snapshot()) { assert n instanceof ProxyNode; ((ProxyNode) n).setProxyPoint((LoopExitNode) trueSuccessor); } } /* * The true successor (surviving loop exit) can have usages, namely proxy nodes, the * false successor however, must not have usages any more after the code above */ assert trueSuccessor.anchored().isEmpty() && falseSuccessor.hasNoUsages(); return this.graph().addOrUnique(new ValueProxyNode(replacement, (LoopExitNode) trueSuccessor)); } } return replacement; } protected void removeThroughFalseBranch(SimplifierTool tool, AbstractMergeNode merge) { // If the LoopExitNode and the Merge still have states then it's incorrect to arbitrarily // pick one side of the branch the represent the control flow. The state on the merge is the // real after state but it would need to be adjusted to represent the effects of the // conditional conversion. assert !(falseSuccessor instanceof LoopExitNode) || ((LoopExitNode) falseSuccessor).stateAfter == null; AbstractBeginNode trueBegin = trueSuccessor(); LogicNode conditionNode = condition(); graph().removeSplitPropagate(this, trueBegin); tool.addToWorkList(trueBegin); if (conditionNode != null) { GraphUtil.tryKillUnused(conditionNode); } if (merge.isAlive() && merge.forwardEndCount() > 1) { for (FixedNode end : merge.forwardEnds()) { Node cur = end; while (cur != null && cur.predecessor() instanceof BeginNode) { cur = cur.predecessor(); } if (cur != null && cur.predecessor() instanceof IfNode) { tool.addToWorkList(cur.predecessor()); } } } } private ValueNode canonicalizeConditionalViaImplies(ValueNode trueValue, ValueNode falseValue) { ValueNode collapsedTrue = trueValue; ValueNode collapsedFalse = falseValue; boolean simplify = false; if (trueValue instanceof ConditionalNode) { TriState result = condition().implies(false, ((ConditionalNode) trueValue).condition()); if (result.isKnown()) { simplify = true; collapsedTrue = result.toBoolean() ? ((ConditionalNode) trueValue).trueValue() : ((ConditionalNode) trueValue).falseValue(); } } if (falseValue instanceof ConditionalNode) { TriState result = condition().implies(true, ((ConditionalNode) falseValue).condition()); if (result.isKnown()) { simplify = true; collapsedFalse = result.toBoolean() ? ((ConditionalNode) falseValue).trueValue() : ((ConditionalNode) falseValue).falseValue(); } } if (simplify) { return graph().unique(new ConditionalNode(condition(), collapsedTrue, collapsedFalse)); } return null; } private List<Node> getNodesForBlock(AbstractBeginNode successor) { StructuredGraph.ScheduleResult schedule = graph().getLastSchedule(); if (schedule == null) { return null; } if (schedule.getCFG().getNodeToBlock().isNew(successor)) { // This can occur when nodes were created after the last schedule. return null; } Block block = schedule.getCFG().blockFor(successor); if (block == null) { return null; } return schedule.nodesFor(block); }
Check whether conversion of an If to a Conditional causes extra unconditional work. Generally that transformation is beneficial if it doesn't result in extra work in the main path.
/** * Check whether conversion of an If to a Conditional causes extra unconditional work. Generally * that transformation is beneficial if it doesn't result in extra work in the main path. */
private boolean isSafeConditionalInput(ValueNode value, AbstractBeginNode successor) { assert successor.hasNoUsages(); if (value.isConstant() || condition.inputs().contains(value)) { // Assume constants are cheap to evaluate. Any input to the condition itself is also // unconditionally evaluated. return true; } if (graph().isAfterFixedReadPhase()) { if (value instanceof ParameterNode) { // Assume Parameters are always evaluated but only apply this logic to graphs after // inlining. Checking for ParameterNode causes it to apply to graphs which are going // to be inlined into other graphs which is incorrect. return true; } if (value instanceof FixedNode) { List<Node> nodes = getNodesForBlock(successor); // The successor block is empty so assume that this input evaluated before the // condition. return nodes != null && nodes.size() == 2; } } return false; } private ValueNode canonicalizeConditionalCascade(SimplifierTool tool, ValueNode trueValue, ValueNode falseValue) { if (trueValue.getStackKind() != falseValue.getStackKind()) { return null; } if (trueValue.getStackKind() != JavaKind.Int && trueValue.getStackKind() != JavaKind.Long) { return null; } if (isSafeConditionalInput(trueValue, trueSuccessor) && isSafeConditionalInput(falseValue, falseSuccessor)) { return graph().unique(new ConditionalNode(condition(), trueValue, falseValue)); } ValueNode value = canonicalizeConditionalViaImplies(trueValue, falseValue); if (value != null) { return value; } if (!graph().isAfterExpandLogic()) { /* * !isAfterExpandLogic() => Cannot spawn NormalizeCompareNodes after lowering in the * ExpandLogicPhase. */ ConditionalNode conditional = null; ValueNode constant = null; boolean negateCondition; if (trueValue instanceof ConditionalNode && falseValue.isConstant()) { conditional = (ConditionalNode) trueValue; constant = falseValue; negateCondition = true; } else if (falseValue instanceof ConditionalNode && trueValue.isConstant()) { conditional = (ConditionalNode) falseValue; constant = trueValue; negateCondition = false; } else { return null; } boolean negateConditionalCondition = false; ValueNode otherValue = null; if (constant == conditional.trueValue()) { otherValue = conditional.falseValue(); negateConditionalCondition = false; } else if (constant == conditional.falseValue()) { otherValue = conditional.trueValue(); negateConditionalCondition = true; } if (otherValue != null && otherValue.isConstant()) { double shortCutProbability = probability(trueSuccessor()); LogicNode newCondition = LogicNode.or(condition(), negateCondition, conditional.condition(), negateConditionalCondition, shortCutProbability); return graph().unique(new ConditionalNode(newCondition, constant, otherValue)); } if (constant.isJavaConstant() && conditional.trueValue().isJavaConstant() && conditional.falseValue().isJavaConstant() && condition() instanceof CompareNode && conditional.condition() instanceof CompareNode) { CompareNode condition1 = (CompareNode) condition(); Condition cond1 = condition1.condition().asCondition(); if (negateCondition) { cond1 = cond1.negate(); } // cond1 is EQ, NE, LT, or GE CompareNode condition2 = (CompareNode) conditional.condition(); Condition cond2 = condition2.condition().asCondition(); ValueNode x = condition1.getX(); ValueNode y = condition1.getY(); ValueNode x2 = condition2.getX(); ValueNode y2 = condition2.getY(); // `x cond1 y ? c1 : (x2 cond2 y2 ? c2 : c3)` boolean sameVars = x == x2 && y == y2; if (!sameVars && x == y2 && y == x2) { sameVars = true; cond2 = cond2.mirror(); } if (sameVars) { JavaKind stackKind = conditional.trueValue().stamp(NodeView.from(tool)).getStackKind(); assert !stackKind.isNumericFloat(); long c1 = constant.asJavaConstant().asLong(); long c2 = conditional.trueValue().asJavaConstant().asLong(); long c3 = conditional.falseValue().asJavaConstant().asLong(); // canonicalize cond2 cond2 = cond2.join(cond1.negate()); if (cond2 == null) { // mixing signed and unsigned cases, or useless combination of conditions return null; } // derive cond3 from cond1 and cond2 Condition cond3 = cond1.negate().join(cond2.negate()); if (cond3 == null) { // mixing signed and unsigned cases, or useless combination of conditions return null; } boolean unsigned = cond1.isUnsigned() || cond2.isUnsigned(); boolean floatingPoint = x.stamp(NodeView.from(tool)) instanceof FloatStamp; assert !floatingPoint || y.stamp(NodeView.from(tool)) instanceof FloatStamp; assert !(floatingPoint && unsigned); long expected1 = expectedConstantForNormalize(cond1); long expected2 = expectedConstantForNormalize(cond2); long expected3 = expectedConstantForNormalize(cond3); if (c1 == expected1 && c2 == expected2 && c3 == expected3) { // normal order } else if (c1 == 0 - expected1 && c2 == 0 - expected2 && c3 == 0 - expected3) { // reverse order ValueNode tmp = x; x = y; y = tmp; } else { // cannot be expressed by NormalizeCompareNode return null; } if (floatingPoint) { boolean unorderedLess = false; if (((FloatStamp) x.stamp).canBeNaN() || ((FloatStamp) y.stamp).canBeNaN()) { // we may encounter NaNs, check the unordered value // (following the original condition's "unorderedIsTrue" path) long unorderedValue = condition1.unorderedIsTrue() ? c1 : condition2.unorderedIsTrue() ? c2 : c3; if (unorderedValue == 0) { // returning "0" for unordered is not possible return null; } unorderedLess = unorderedValue == -1; } return graph().unique(new FloatNormalizeCompareNode(x, y, stackKind, unorderedLess)); } else { return graph().unique(new IntegerNormalizeCompareNode(x, y, stackKind, unsigned)); } } } } return null; } private static long expectedConstantForNormalize(Condition condition) { if (condition == Condition.EQ) { return 0; } else if (condition == Condition.LT || condition == Condition.BT) { return -1; } else { assert condition == Condition.GT || condition == Condition.AT; return 1; } } public enum NodeColor { NONE, CONDITION_USAGE, TRUE_BRANCH, FALSE_BRANCH, PHI_MIXED, MIXED }
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:
contains(list, e, yes, no) {
    if (list == null || e == null) {
        condition = false;
    } else {
        condition = false;
        for (i in list) {
            if (i.equals(e)) {
                condition = true;
                break;
            }
        }
    }
    if (condition) {
        return yes;
    } else {
        return no;
    }
}
will be transformed into:
contains(list, e, yes, no) {
    if (list == null || e == null) {
        return no;
    } else {
        condition = false;
        for (i in list) {
            if (i.equals(e)) {
                return yes;
            }
        }
        return no;
    }
}
Returns:true if a transformation was made, false otherwise
/** * 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: * * <pre> * contains(list, e, yes, no) { * if (list == null || e == null) { * condition = false; * } else { * condition = false; * for (i in list) { * if (i.equals(e)) { * condition = true; * break; * } * } * } * if (condition) { * return yes; * } else { * return no; * } * } * </pre> * * will be transformed into: * * <pre> * contains(list, e, yes, no) { * if (list == null || e == null) { * return no; * } else { * condition = false; * for (i in list) { * if (i.equals(e)) { * return yes; * } * } * return no; * } * } * </pre> * * @return true if a transformation was made, false otherwise */
private boolean removeIntermediateMaterialization(SimplifierTool tool) { if (!(predecessor() instanceof AbstractMergeNode) || predecessor() instanceof LoopBeginNode) { return false; } AbstractMergeNode merge = (AbstractMergeNode) predecessor(); if (!(condition() instanceof CompareNode)) { return false; } CompareNode compare = (CompareNode) condition(); if (compare.getUsageCount() != 1) { return false; } // Only consider merges with a single usage that is both a phi and an operand of the // comparison NodeIterable<Node> mergeUsages = merge.usages(); if (mergeUsages.count() != 1) { return false; } Node singleUsage = mergeUsages.first(); if (!(singleUsage instanceof ValuePhiNode) || (singleUsage != compare.getX() && singleUsage != compare.getY())) { return false; } if (trueSuccessor().isUsedAsGuardInput() || falseSuccessor().isUsedAsGuardInput()) { return false; } // Ensure phi is used by at most the comparison and the merge's frame state (if any) ValuePhiNode phi = (ValuePhiNode) singleUsage; NodeIterable<Node> phiUsages = phi.usages(); for (Node usage : phiUsages) { if (usage == compare) { continue; } if (usage == merge.stateAfter()) { continue; } // Checkstyle: stop // @formatter:off // // We also want to allow the usage to be on the loop-proxy if one of the branches is a // loop exit. // // This pattern: // // if------->cond // / \ // begin begin // | | // end end C1 V2 // \ / \ / // merge---------->phi<------ C1 // | ^ \ / // if-------------|-------->== // / \ | // A B<--------Proxy // // Must be simplified to: // // if---------------------->cond // / \ // A B<--------Proxy------>V2 // // @formatter:on // Checkstyle: resume if (usage instanceof ValueProxyNode) { ValueProxyNode proxy = (ValueProxyNode) usage; if (proxy.proxyPoint() == trueSuccessor || proxy.proxyPoint() == falseSuccessor) { continue; } } return false; } List<EndNode> mergePredecessors = merge.cfgPredecessors().snapshot(); assert phi.valueCount() == merge.forwardEndCount(); Constant[] xs = constantValues(compare.getX(), merge, false); Constant[] ys = constantValues(compare.getY(), merge, false); if (xs == null || ys == null) { return false; } if (merge.stateAfter() != null && !GraphUtil.mayRemoveSplit(this)) { return false; } List<EndNode> falseEnds = new ArrayList<>(mergePredecessors.size()); List<EndNode> trueEnds = new ArrayList<>(mergePredecessors.size()); EconomicMap<AbstractEndNode, ValueNode> phiValues = EconomicMap.create(Equivalence.IDENTITY, mergePredecessors.size()); AbstractBeginNode oldFalseSuccessor = falseSuccessor(); AbstractBeginNode oldTrueSuccessor = trueSuccessor(); setFalseSuccessor(null); setTrueSuccessor(null); Iterator<EndNode> ends = mergePredecessors.iterator(); for (int i = 0; i < xs.length; i++) { EndNode end = ends.next(); phiValues.put(end, phi.valueAt(end)); if (compare.condition().foldCondition(xs[i], ys[i], tool.getConstantReflection(), compare.unorderedIsTrue())) { trueEnds.add(end); } else { falseEnds.add(end); } } assert !ends.hasNext(); assert falseEnds.size() + trueEnds.size() == xs.length; connectEnds(falseEnds, phi, phiValues, oldFalseSuccessor, merge, tool); connectEnds(trueEnds, phi, phiValues, oldTrueSuccessor, merge, tool); if (this.trueSuccessorProbability == 0.0) { for (AbstractEndNode endNode : trueEnds) { propagateZeroProbability(endNode); } } if (this.trueSuccessorProbability == 1.0) { for (AbstractEndNode endNode : falseEnds) { propagateZeroProbability(endNode); } } /* * Remove obsolete ends only after processing all ends, otherwise oldTrueSuccessor or * oldFalseSuccessor might have been removed if it is a LoopExitNode. */ if (falseEnds.isEmpty()) { GraphUtil.killCFG(oldFalseSuccessor); } if (trueEnds.isEmpty()) { GraphUtil.killCFG(oldTrueSuccessor); } GraphUtil.killCFG(merge); assert !merge.isAlive() : merge; assert !phi.isAlive() : phi; assert !compare.isAlive() : compare; assert !this.isAlive() : this; return true; } private static void propagateZeroProbability(FixedNode startNode) { Node prev = null; for (FixedNode node : GraphUtil.predecessorIterable(startNode)) { if (node instanceof IfNode) { IfNode ifNode = (IfNode) node; if (ifNode.trueSuccessor() == prev) { if (ifNode.trueSuccessorProbability == 0.0) { return; } else if (ifNode.trueSuccessorProbability == 1.0) { continue; } else { ifNode.setTrueSuccessorProbability(0.0); return; } } else if (ifNode.falseSuccessor() == prev) { if (ifNode.trueSuccessorProbability == 1.0) { return; } else if (ifNode.trueSuccessorProbability == 0.0) { continue; } else { ifNode.setTrueSuccessorProbability(1.0); return; } } else { throw new GraalError("Illegal state"); } } else if (node instanceof AbstractMergeNode && !(node instanceof LoopBeginNode)) { for (AbstractEndNode endNode : ((AbstractMergeNode) node).cfgPredecessors()) { propagateZeroProbability(endNode); } return; } prev = node; } }
Connects a set of ends to a given successor, inserting a merge node if there is more than one end. If ends is not empty, then successor is added to tool's work list.
Params:
  • phi – the original single-usage phi of the preceding merge
  • phiValues – the values of the phi at the merge, keyed by the merge ends
  • oldMerge – the merge being removed
/** * 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}. * * @param phi the original single-usage phi of the preceding merge * @param phiValues the values of the phi at the merge, keyed by the merge ends * @param oldMerge the merge being removed */
private void connectEnds(List<EndNode> ends, ValuePhiNode phi, EconomicMap<AbstractEndNode, ValueNode> phiValues, AbstractBeginNode successor, AbstractMergeNode oldMerge, SimplifierTool tool) { if (!ends.isEmpty()) { // If there was a value proxy usage, then the proxy needs a new value. ValueProxyNode valueProxy = null; if (successor instanceof LoopExitNode) { for (Node usage : phi.usages()) { if (usage instanceof ValueProxyNode && ((ValueProxyNode) usage).proxyPoint() == successor) { valueProxy = (ValueProxyNode) usage; } } } final ValueProxyNode proxy = valueProxy; if (ends.size() == 1) { AbstractEndNode end = ends.get(0); if (proxy != null) { phi.replaceAtUsages(phiValues.get(end), n -> n == proxy); } ((FixedWithNextNode) end.predecessor()).setNext(successor); oldMerge.removeEnd(end); GraphUtil.killCFG(end); } else { // Need a new phi in case the frame state is used by more than the merge being // removed. NodeView view = NodeView.from(tool); AbstractMergeNode newMerge = graph().add(new MergeNode()); PhiNode oldPhi = (PhiNode) oldMerge.usages().first(); PhiNode newPhi = graph().addWithoutUnique(new ValuePhiNode(oldPhi.stamp(view), newMerge)); if (proxy != null) { phi.replaceAtUsages(newPhi, n -> n == proxy); } for (EndNode end : ends) { newPhi.addInput(phiValues.get(end)); newMerge.addForwardEnd(end); } FrameState stateAfter = oldMerge.stateAfter(); if (stateAfter != null) { stateAfter = stateAfter.duplicate(); stateAfter.replaceFirstInput(oldPhi, newPhi); newMerge.setStateAfter(stateAfter); } newMerge.setNext(successor); } tool.addToWorkList(successor); } }
Gets an array of constants derived from a node that is either a ConstantNode or a PhiNode whose input values are all constants. The length of the returned array is equal to the number of ends terminating in a given merge node.
Returns:null if node is neither a ConstantNode nor a PhiNode whose input values are all constants
/** * Gets an array of constants derived from a node that is either a {@link ConstantNode} or a * {@link PhiNode} whose input values are all constants. The length of the returned array is * equal to the number of ends terminating in a given merge node. * * @return null if {@code node} is neither a {@link ConstantNode} nor a {@link PhiNode} whose * input values are all constants */
public static Constant[] constantValues(ValueNode node, AbstractMergeNode merge, boolean allowNull) { if (node.isConstant()) { Constant[] result = new Constant[merge.forwardEndCount()]; Arrays.fill(result, node.asConstant()); return result; } if (node instanceof PhiNode) { PhiNode phi = (PhiNode) node; if (phi.merge() == merge && phi instanceof ValuePhiNode && phi.valueCount() == merge.forwardEndCount()) { Constant[] result = new Constant[merge.forwardEndCount()]; int i = 0; for (ValueNode n : phi.values()) { if (!allowNull && !n.isConstant()) { return null; } result[i++] = n.asConstant(); } return result; } } return null; } @Override public AbstractBeginNode getPrimarySuccessor() { return null; } public AbstractBeginNode getSuccessor(boolean result) { return result ? this.trueSuccessor() : this.falseSuccessor(); } @Override public boolean setProbability(AbstractBeginNode successor, double value) { if (successor == this.trueSuccessor()) { this.setTrueSuccessorProbability(value); return true; } else if (successor == this.falseSuccessor()) { this.setTrueSuccessorProbability(1.0 - value); return true; } return false; } @Override public int getSuccessorCount() { return 2; } }