src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.phases.common/src/org/graalvm/compiler/phases/common/ConditionalEliminationPhase.java
/*
* Copyright (c) 2015, 2019, 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.phases.common;
import static org.graalvm.compiler.nodes.StaticDeoptimizingNode.mergeActions;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;
import jdk.internal.vm.compiler.collections.EconomicMap;
import jdk.internal.vm.compiler.collections.Equivalence;
import jdk.internal.vm.compiler.collections.MapCursor;
import jdk.internal.vm.compiler.collections.Pair;
import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph;
import org.graalvm.compiler.core.common.cfg.BlockMap;
import org.graalvm.compiler.core.common.type.ArithmeticOpTable;
import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp;
import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp.And;
import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp.Or;
import org.graalvm.compiler.core.common.type.IntegerStamp;
import org.graalvm.compiler.core.common.type.ObjectStamp;
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.graph.Node;
import org.graalvm.compiler.graph.NodeMap;
import org.graalvm.compiler.graph.NodeStack;
import org.graalvm.compiler.graph.spi.CanonicalizerTool;
import org.graalvm.compiler.nodeinfo.InputType;
import org.graalvm.compiler.nodes.AbstractBeginNode;
import org.graalvm.compiler.nodes.AbstractMergeNode;
import org.graalvm.compiler.nodes.BinaryOpLogicNode;
import org.graalvm.compiler.nodes.ConditionAnchorNode;
import org.graalvm.compiler.nodes.DeoptimizeNode;
import org.graalvm.compiler.nodes.DeoptimizingGuard;
import org.graalvm.compiler.nodes.EndNode;
import org.graalvm.compiler.nodes.FixedGuardNode;
import org.graalvm.compiler.nodes.FixedNode;
import org.graalvm.compiler.nodes.FixedWithNextNode;
import org.graalvm.compiler.nodes.GuardNode;
import org.graalvm.compiler.nodes.IfNode;
import org.graalvm.compiler.nodes.LogicConstantNode;
import org.graalvm.compiler.nodes.LogicNode;
import org.graalvm.compiler.nodes.LoopExitNode;
import org.graalvm.compiler.nodes.MergeNode;
import org.graalvm.compiler.nodes.NodeView;
import org.graalvm.compiler.nodes.ParameterNode;
import org.graalvm.compiler.nodes.PiNode;
import org.graalvm.compiler.nodes.ProxyNode;
import org.graalvm.compiler.nodes.ShortCircuitOrNode;
import org.graalvm.compiler.nodes.StructuredGraph;
import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult;
import org.graalvm.compiler.nodes.UnaryOpLogicNode;
import org.graalvm.compiler.nodes.ValueNode;
import org.graalvm.compiler.nodes.ValuePhiNode;
import org.graalvm.compiler.nodes.calc.AndNode;
import org.graalvm.compiler.nodes.calc.BinaryArithmeticNode;
import org.graalvm.compiler.nodes.calc.BinaryNode;
import org.graalvm.compiler.nodes.calc.IntegerEqualsNode;
import org.graalvm.compiler.nodes.calc.UnaryNode;
import org.graalvm.compiler.nodes.cfg.Block;
import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
import org.graalvm.compiler.nodes.extended.GuardingNode;
import org.graalvm.compiler.nodes.extended.IntegerSwitchNode;
import org.graalvm.compiler.nodes.extended.LoadHubNode;
import org.graalvm.compiler.nodes.extended.ValueAnchorNode;
import org.graalvm.compiler.nodes.java.InstanceOfNode;
import org.graalvm.compiler.nodes.java.TypeSwitchNode;
import org.graalvm.compiler.nodes.spi.CoreProviders;
import org.graalvm.compiler.nodes.spi.NodeWithState;
import org.graalvm.compiler.nodes.spi.StampInverter;
import org.graalvm.compiler.nodes.util.GraphUtil;
import org.graalvm.compiler.phases.BasePhase;
import org.graalvm.compiler.phases.schedule.SchedulePhase;
import org.graalvm.compiler.phases.schedule.SchedulePhase.SchedulingStrategy;
import jdk.vm.ci.meta.DeoptimizationAction;
import jdk.vm.ci.meta.JavaConstant;
import jdk.vm.ci.meta.SpeculationLog.Speculation;
import jdk.vm.ci.meta.TriState;
public class ConditionalEliminationPhase extends BasePhase<CoreProviders> {
private static final CounterKey counterStampsRegistered = DebugContext.counter("StampsRegistered");
private static final CounterKey counterStampsFound = DebugContext.counter("StampsFound");
private static final CounterKey counterIfsKilled = DebugContext.counter("CE_KilledIfs");
private static final CounterKey counterPhiStampsImproved = DebugContext.counter("CE_ImprovedPhis");
private final boolean fullSchedule;
private final boolean moveGuards;
public ConditionalEliminationPhase(boolean fullSchedule) {
this(fullSchedule, true);
}
public ConditionalEliminationPhase(boolean fullSchedule, boolean moveGuards) {
this.fullSchedule = fullSchedule;
this.moveGuards = moveGuards;
}
@Override
@SuppressWarnings("try")
protected void run(StructuredGraph graph, CoreProviders context) {
try (DebugContext.Scope s = graph.getDebug().scope("DominatorConditionalElimination")) {
BlockMap<List<Node>> blockToNodes = null;
NodeMap<Block> nodeToBlock = null;
ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, true, true);
if (fullSchedule) {
if (moveGuards) {
cfg.visitDominatorTree(new MoveGuardsUpwards(), graph.hasValueProxies());
}
try (DebugContext.Scope scheduleScope = graph.getDebug().scope(SchedulePhase.class)) {
SchedulePhase.run(graph, SchedulingStrategy.EARLIEST_WITH_GUARD_ORDER, cfg);
} catch (Throwable t) {
throw graph.getDebug().handle(t);
}
ScheduleResult r = graph.getLastSchedule();
blockToNodes = r.getBlockToNodesMap();
nodeToBlock = r.getNodeToBlockMap();
} else {
nodeToBlock = cfg.getNodeToBlock();
blockToNodes = getBlockToNodes(cfg);
}
ControlFlowGraph.RecursiveVisitor<?> visitor = createVisitor(graph, cfg, blockToNodes, nodeToBlock, context);
cfg.visitDominatorTree(visitor, graph.hasValueProxies());
}
}
protected BlockMap<List<Node>> getBlockToNodes(@SuppressWarnings("unused") ControlFlowGraph cfg) {
return null;
}
protected ControlFlowGraph.RecursiveVisitor<?> createVisitor(StructuredGraph graph, @SuppressWarnings("unused") ControlFlowGraph cfg, BlockMap<List<Node>> blockToNodes,
NodeMap<Block> nodeToBlock, CoreProviders context) {
return new Instance(graph, blockToNodes, nodeToBlock, context);
}
public static class MoveGuardsUpwards implements ControlFlowGraph.RecursiveVisitor<Block> {
Block anchorBlock;
@Override
@SuppressWarnings("try")
public Block enter(Block b) {
Block oldAnchorBlock = anchorBlock;
if (b.getDominator() == null || b.getDominator().getPostdominator() != b) {
// New anchor.
anchorBlock = b;
}
AbstractBeginNode beginNode = b.getBeginNode();
if (beginNode instanceof AbstractMergeNode && anchorBlock != b) {
AbstractMergeNode mergeNode = (AbstractMergeNode) beginNode;
mergeNode.replaceAtUsages(InputType.Anchor, anchorBlock.getBeginNode());
mergeNode.replaceAtUsages(InputType.Guard, anchorBlock.getBeginNode());
assert mergeNode.anchored().isEmpty();
}
FixedNode endNode = b.getEndNode();
if (endNode instanceof IfNode) {
IfNode node = (IfNode) endNode;
// Check if we can move guards upwards.
AbstractBeginNode trueSuccessor = node.trueSuccessor();
EconomicMap<LogicNode, GuardNode> trueGuards = EconomicMap.create(Equivalence.IDENTITY);
for (GuardNode guard : trueSuccessor.guards()) {
LogicNode condition = guard.getCondition();
if (condition.hasMoreThanOneUsage()) {
trueGuards.put(condition, guard);
}
}
if (!trueGuards.isEmpty()) {
for (GuardNode guard : node.falseSuccessor().guards().snapshot()) {
GuardNode otherGuard = trueGuards.get(guard.getCondition());
if (otherGuard != null && guard.isNegated() == otherGuard.isNegated()) {
Speculation speculation = otherGuard.getSpeculation();
if (speculation == null) {
speculation = guard.getSpeculation();
} else if (guard.getSpeculation() != null && guard.getSpeculation() != speculation) {
// Cannot optimize due to different speculations.
continue;
}
try (DebugCloseable closeable = guard.withNodeSourcePosition()) {
GuardNode newlyCreatedGuard = new GuardNode(guard.getCondition(), anchorBlock.getBeginNode(), guard.getReason(), guard.getAction(), guard.isNegated(), speculation,
guard.getNoDeoptSuccessorPosition());
GuardNode newGuard = node.graph().unique(newlyCreatedGuard);
if (otherGuard.isAlive()) {
otherGuard.replaceAndDelete(newGuard);
}
guard.replaceAndDelete(newGuard);
}
}
}
}
}
return oldAnchorBlock;
}
@Override
public void exit(Block b, Block value) {
anchorBlock = value;
}
}
private static final class PhiInfoElement {
private EconomicMap<EndNode, InfoElement> infoElements;
public void set(EndNode end, InfoElement infoElement) {
if (infoElements == null) {
infoElements = EconomicMap.create(Equivalence.IDENTITY);
}
infoElements.put(end, infoElement);
}
public InfoElement get(EndNode end) {
if (infoElements == null) {
return null;
}
return infoElements.get(end);
}
}
public static final class Marks {
final int infoElementOperations;
final int conditions;
public Marks(int infoElementOperations, int conditions) {
this.infoElementOperations = infoElementOperations;
this.conditions = conditions;
}
}
protected static final class GuardedCondition {
private final GuardingNode guard;
private final LogicNode condition;
private final boolean negated;
public GuardedCondition(GuardingNode guard, LogicNode condition, boolean negated) {
this.guard = guard;
this.condition = condition;
this.negated = negated;
}
public GuardingNode getGuard() {
return guard;
}
public LogicNode getCondition() {
return condition;
}
public boolean isNegated() {
return negated;
}
}
public static class Instance implements ControlFlowGraph.RecursiveVisitor<Marks> {
protected final NodeMap<InfoElement> map;
protected final BlockMap<List<Node>> blockToNodes;
protected final NodeMap<Block> nodeToBlock;
protected final CanonicalizerTool tool;
protected final NodeStack undoOperations;
protected final StructuredGraph graph;
protected final DebugContext debug;
protected final EconomicMap<MergeNode, EconomicMap<ValuePhiNode, PhiInfoElement>> mergeMaps;
protected final ArrayDeque<GuardedCondition> conditions;
/**
* Tests which may be eliminated because post dominating tests to prove a broader condition.
*/
private Deque<DeoptimizingGuard> pendingTests;
public Instance(StructuredGraph graph, BlockMap<List<Node>> blockToNodes, NodeMap<Block> nodeToBlock, CoreProviders context) {
this.graph = graph;
this.debug = graph.getDebug();
this.blockToNodes = blockToNodes;
this.nodeToBlock = nodeToBlock;
this.undoOperations = new NodeStack();
this.map = graph.createNodeMap();
this.pendingTests = new ArrayDeque<>();
this.conditions = new ArrayDeque<>();
tool = GraphUtil.getDefaultSimplifier(context.getMetaAccess(), context.getConstantReflection(), context.getConstantFieldProvider(), false, graph.getAssumptions(), graph.getOptions(),
context.getLowerer());
mergeMaps = EconomicMap.create(Equivalence.IDENTITY);
}
protected void processConditionAnchor(ConditionAnchorNode node) {
tryProveCondition(node.condition(), (guard, result, guardedValueStamp, newInput) -> {
if (result != node.isNegated()) {
node.replaceAtUsages(guard.asNode());
GraphUtil.unlinkFixedNode(node);
GraphUtil.killWithUnusedFloatingInputs(node);
} else {
ValueAnchorNode valueAnchor = node.graph().add(new ValueAnchorNode(null));
node.replaceAtUsages(valueAnchor);
node.graph().replaceFixedWithFixed(node, valueAnchor);
}
return true;
});
}
protected void processGuard(GuardNode node) {
if (!tryProveGuardCondition(node, node.getCondition(), (guard, result, guardedValueStamp, newInput) -> {
if (result != node.isNegated()) {
node.replaceAndDelete(guard.asNode());
if (guard instanceof DeoptimizingGuard && !((DeoptimizingGuard) guard).isNegated()) {
rebuildPiNodes((DeoptimizingGuard) guard);
}
} else {
AbstractBeginNode beginNode = (AbstractBeginNode) node.getAnchor();
if (beginNode.next() instanceof DeoptimizeNode) {
// This branch is already dead.
} else {
/*
* Don't kill this branch immediately because `killCFG` can have complex
* implications in the presence of loops: it might replace or delete nodes
* in other branches or even above the kill point. Instead of killing
* immediately, just leave the graph in a state that is easy to simplify by
* a subsequent canonicalizer phase.
*/
FixedGuardNode deopt = new FixedGuardNode(LogicConstantNode.forBoolean(result, node.graph()), node.getReason(), node.getAction(), node.getSpeculation(), node.isNegated(),
node.getNodeSourcePosition());
graph.addAfterFixed(beginNode, node.graph().add(deopt));
}
}
return true;
})) {
registerNewCondition(node.getCondition(), node.isNegated(), node);
}
}
protected void processFixedGuard(FixedGuardNode node) {
if (!tryProveGuardCondition(node, node.condition(), (guard, result, guardedValueStamp, newInput) -> {
if (result != node.isNegated()) {
node.replaceAtUsages(guard.asNode());
GraphUtil.unlinkFixedNode(node);
GraphUtil.killWithUnusedFloatingInputs(node);
if (guard instanceof DeoptimizingGuard && !((DeoptimizingGuard) guard).isNegated()) {
rebuildPiNodes((DeoptimizingGuard) guard);
}
} else {
node.setCondition(LogicConstantNode.forBoolean(result, node.graph()), node.isNegated());
// Don't kill this branch immediately, see `processGuard`.
}
debug.log("Kill fixed guard %s", node);
return true;
})) {
registerNewCondition(node.condition(), node.isNegated(), node);
}
}
private void rebuildPiNodes(DeoptimizingGuard guard) {
LogicNode newCondition = guard.getCondition();
if (newCondition instanceof InstanceOfNode) {
InstanceOfNode inst = (InstanceOfNode) newCondition;
ValueNode originalValue = GraphUtil.skipPi(inst.getValue());
PiNode pi = null;
// Ensure that any Pi that's weaker than what the instanceof proves is
// replaced by one derived from the instanceof itself.
for (PiNode existing : guard.asNode().usages().filter(PiNode.class).snapshot()) {
if (!existing.isAlive()) {
continue;
}
if (originalValue != GraphUtil.skipPi(existing.object())) {
// Somehow these are unrelated values so leave it alone
continue;
}
// If the pi has a weaker stamp or the same stamp but a different input
// then replace it.
boolean strongerStamp = !existing.piStamp().join(inst.getCheckedStamp()).equals(inst.getCheckedStamp());
boolean differentCheckedStamp = !existing.piStamp().equals(inst.getCheckedStamp());
boolean differentObject = existing.object() != inst.getValue();
if (!strongerStamp && (differentCheckedStamp || differentObject)) {
if (pi == null) {
pi = graph.unique(new PiNode(inst.getValue(), inst.getCheckedStamp(), (ValueNode) guard));
}
if (!pi.stamp(NodeView.DEFAULT).join(existing.stamp(NodeView.DEFAULT)).equals(pi.stamp(NodeView.DEFAULT))) {
/*
* With a code sequence like null check, type check, null check of type
* checked value, CE will use the first null check to prove the second
* null check so the graph ends up a Pi guarded by the first null check
* but consuming the output Pi from the type check check. In this case
* we should still canonicalize the checked stamp for consistency.
*/
if (differentCheckedStamp) {
PiNode alternatePi = graph.unique(new PiNode(existing.object(), inst.getCheckedStamp(), (ValueNode) guard));
/*
* If the resulting stamp is as good or better then do the
* replacement. However when interface types are involved it's
* possible that improving the checked stamp merges types which
* appear unrelated so there's we must skip the replacement.
*/
if (alternatePi.stamp(NodeView.DEFAULT).join(existing.stamp(NodeView.DEFAULT)).equals(alternatePi.stamp(NodeView.DEFAULT))) {
existing.replaceAndDelete(alternatePi);
}
}
continue;
}
existing.replaceAndDelete(pi);
}
}
}
}
protected void processIf(IfNode node) {
tryProveCondition(node.condition(), (guard, result, guardedValueStamp, newInput) -> {
node.setCondition(LogicConstantNode.forBoolean(result, node.graph()));
AbstractBeginNode survivingSuccessor = node.getSuccessor(result);
survivingSuccessor.replaceAtUsages(InputType.Guard, guard.asNode());
// Don't kill the other branch immediately, see `processGuard`.
counterIfsKilled.increment(debug);
return true;
});
}
@Override
public Marks enter(Block block) {
int infoElementsMark = undoOperations.size();
int conditionsMark = conditions.size();
debug.log("[Pre Processing block %s]", block);
// For now conservatively collect guards only within the same block.
pendingTests.clear();
processNodes(block);
return new Marks(infoElementsMark, conditionsMark);
}
protected void processNodes(Block block) {
if (blockToNodes != null) {
for (Node n : blockToNodes.get(block)) {
if (n.isAlive()) {
processNode(n);
}
}
} else {
processBlock(block);
}
}
private void processBlock(Block block) {
FixedNode n = block.getBeginNode();
FixedNode endNode = block.getEndNode();
debug.log("[Processing block %s]", block);
while (n != endNode) {
if (n.isDeleted() || endNode.isDeleted()) {
// This branch was deleted!
return;
}
FixedNode next = ((FixedWithNextNode) n).next();
processNode(n);
n = next;
}
if (endNode.isAlive()) {
processNode(endNode);
}
}
@SuppressWarnings("try")
protected void processNode(Node node) {
try (DebugCloseable closeable = node.withNodeSourcePosition()) {
if (node instanceof NodeWithState && !(node instanceof GuardingNode)) {
pendingTests.clear();
}
if (node instanceof MergeNode) {
introducePisForPhis((MergeNode) node);
}
if (node instanceof AbstractBeginNode) {
if (node instanceof LoopExitNode && graph.hasValueProxies()) {
// Condition must not be used down this path.
return;
}
processAbstractBegin((AbstractBeginNode) node);
} else if (node instanceof FixedGuardNode) {
processFixedGuard((FixedGuardNode) node);
} else if (node instanceof GuardNode) {
processGuard((GuardNode) node);
} else if (node instanceof ConditionAnchorNode) {
processConditionAnchor((ConditionAnchorNode) node);
} else if (node instanceof IfNode) {
processIf((IfNode) node);
} else if (node instanceof EndNode) {
processEnd((EndNode) node);
}
}
}
protected void introducePisForPhis(MergeNode merge) {
EconomicMap<ValuePhiNode, PhiInfoElement> mergeMap = this.mergeMaps.get(merge);
if (mergeMap != null) {
MapCursor<ValuePhiNode, PhiInfoElement> entries = mergeMap.getEntries();
while (entries.advance()) {
ValuePhiNode phi = entries.getKey();
assert phi.isAlive() || phi.isDeleted();
/*
* Phi might have been killed already via a conditional elimination in another
* branch.
*/
if (phi.isDeleted()) {
continue;
}
PhiInfoElement phiInfoElements = entries.getValue();
Stamp bestPossibleStamp = null;
for (int i = 0; i < phi.valueCount(); ++i) {
ValueNode valueAt = phi.valueAt(i);
Stamp curBestStamp = valueAt.stamp(NodeView.DEFAULT);
InfoElement infoElement = phiInfoElements.get(merge.forwardEndAt(i));
if (infoElement != null) {
curBestStamp = curBestStamp.join(infoElement.getStamp());
}
if (bestPossibleStamp == null) {
bestPossibleStamp = curBestStamp;
} else {
bestPossibleStamp = bestPossibleStamp.meet(curBestStamp);
}
}
Stamp oldStamp = phi.stamp(NodeView.DEFAULT);
if (oldStamp.tryImproveWith(bestPossibleStamp) != null) {
// Need to be careful to not run into stamp update cycles with the iterative
// canonicalization.
boolean allow = false;
if (bestPossibleStamp instanceof ObjectStamp) {
// Always allow object stamps.
allow = true;
} else if (bestPossibleStamp instanceof IntegerStamp) {
IntegerStamp integerStamp = (IntegerStamp) bestPossibleStamp;
IntegerStamp oldIntegerStamp = (IntegerStamp) oldStamp;
if (integerStamp.isPositive() != oldIntegerStamp.isPositive()) {
allow = true;
} else if (integerStamp.isNegative() != oldIntegerStamp.isNegative()) {
allow = true;
} else if (integerStamp.isStrictlyPositive() != oldIntegerStamp.isStrictlyPositive()) {
allow = true;
} else if (integerStamp.isStrictlyNegative() != oldIntegerStamp.isStrictlyNegative()) {
allow = true;
} else if (integerStamp.asConstant() != null) {
allow = true;
} else if (oldStamp.isUnrestricted()) {
allow = true;
}
} else {
// Fortify: Suppress Null Dereference false positive
assert bestPossibleStamp != null;
allow = (bestPossibleStamp.asConstant() != null);
}
if (allow) {
ValuePhiNode newPhi = graph.addWithoutUnique(new ValuePhiNode(bestPossibleStamp, merge));
for (int i = 0; i < phi.valueCount(); ++i) {
ValueNode valueAt = phi.valueAt(i);
if (bestPossibleStamp.meet(valueAt.stamp(NodeView.DEFAULT)).equals(bestPossibleStamp)) {
// Pi not required here.
} else {
InfoElement infoElement = phiInfoElements.get(merge.forwardEndAt(i));
assert infoElement != null;
Stamp curBestStamp = infoElement.getStamp();
ValueNode input = infoElement.getProxifiedInput();
if (input == null) {
input = valueAt;
}
valueAt = graph.maybeAddOrUnique(PiNode.create(input, curBestStamp, (ValueNode) infoElement.guard));
}
newPhi.addInput(valueAt);
}
counterPhiStampsImproved.increment(debug);
phi.replaceAtUsagesAndDelete(newPhi);
}
}
}
}
}
protected void processEnd(EndNode end) {
AbstractMergeNode abstractMerge = end.merge();
if (abstractMerge instanceof MergeNode) {
MergeNode merge = (MergeNode) abstractMerge;
EconomicMap<ValuePhiNode, PhiInfoElement> mergeMap = this.mergeMaps.get(merge);
for (ValuePhiNode phi : merge.valuePhis()) {
ValueNode valueAt = phi.valueAt(end);
InfoElement infoElement = this.getInfoElements(valueAt);
while (infoElement != null) {
Stamp newStamp = infoElement.getStamp();
if (phi.stamp(NodeView.DEFAULT).tryImproveWith(newStamp) != null) {
if (mergeMap == null) {
mergeMap = EconomicMap.create(Equivalence.IDENTITY);
mergeMaps.put(merge, mergeMap);
}
PhiInfoElement phiInfoElement = mergeMap.get(phi);
if (phiInfoElement == null) {
phiInfoElement = new PhiInfoElement();
mergeMap.put(phi, phiInfoElement);
}
phiInfoElement.set(end, infoElement);
break;
}
infoElement = nextElement(infoElement);
}
}
}
}
protected void registerNewCondition(LogicNode condition, boolean negated, GuardingNode guard) {
if (condition instanceof UnaryOpLogicNode) {
UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) condition;
ValueNode value = unaryLogicNode.getValue();
if (maybeMultipleUsages(value)) {
// getSucceedingStampForValue doesn't take the (potentially a Pi Node) input
// stamp into account, so it can be safely propagated.
Stamp newStamp = unaryLogicNode.getSucceedingStampForValue(negated);
registerNewStamp(value, newStamp, guard, true);
}
} else if (condition instanceof BinaryOpLogicNode) {
BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) condition;
ValueNode x = binaryOpLogicNode.getX();
ValueNode y = binaryOpLogicNode.getY();
if (!x.isConstant() && maybeMultipleUsages(x)) {
Stamp newStampX = binaryOpLogicNode.getSucceedingStampForX(negated, getSafeStamp(x), getOtherSafeStamp(y));
registerNewStamp(x, newStampX, guard);
}
if (!y.isConstant() && maybeMultipleUsages(y)) {
Stamp newStampY = binaryOpLogicNode.getSucceedingStampForY(negated, getOtherSafeStamp(x), getSafeStamp(y));
registerNewStamp(y, newStampY, guard);
}
if (condition instanceof IntegerEqualsNode && guard instanceof DeoptimizingGuard && !negated) {
if (y.isConstant() && x instanceof AndNode) {
AndNode and = (AndNode) x;
ValueNode andX = and.getX();
if (and.getY() == y && maybeMultipleUsages(andX)) {
/*
* This 'and' proves something about some of the bits in and.getX().
* It's equivalent to or'ing in the mask value since those values are
* known to be set.
*/
BinaryOp<Or> op = ArithmeticOpTable.forStamp(x.stamp(NodeView.DEFAULT)).getOr();
IntegerStamp newStampX = (IntegerStamp) op.foldStamp(getSafeStamp(andX), getOtherSafeStamp(y));
registerNewStamp(andX, newStampX, guard);
}
}
}
}
if (guard instanceof DeoptimizingGuard) {
assert ((DeoptimizingGuard) guard).getCondition() == condition;
pendingTests.push((DeoptimizingGuard) guard);
}
registerCondition(condition, negated, guard);
}
Pair<InfoElement, Stamp> recursiveFoldStamp(Node node) {
if (node instanceof UnaryNode) {
UnaryNode unary = (UnaryNode) node;
ValueNode value = unary.getValue();
InfoElement infoElement = getInfoElements(value);
while (infoElement != null) {
Stamp result = unary.foldStamp(infoElement.getStamp());
if (result != null) {
return Pair.create(infoElement, result);
}
infoElement = nextElement(infoElement);
}
} else if (node instanceof BinaryNode) {
BinaryNode binary = (BinaryNode) node;
ValueNode y = binary.getY();
ValueNode x = binary.getX();
if (y.isConstant()) {
InfoElement infoElement = getInfoElements(x);
while (infoElement != null) {
Stamp result = binary.foldStamp(infoElement.stamp, y.stamp(NodeView.DEFAULT));
if (result != null) {
return Pair.create(infoElement, result);
}
infoElement = nextElement(infoElement);
}
}
}
return null;
}
/**
* Get the stamp that may be used for the value for which we are registering the condition.
* We may directly use the stamp here without restriction, because any later lookup of the
* registered info elements is in the same chain of pi nodes.
*/
private static Stamp getSafeStamp(ValueNode x) {
return x.stamp(NodeView.DEFAULT);
}
/**
* We can only use the stamp of a second value involved in the condition if we are sure that
* we are not implicitly creating a dependency on a pi node that is responsible for that
* stamp. For now, we are conservatively only using the stamps of constants. Under certain
* circumstances, we may also be able to use the stamp of the value after skipping pi nodes
* (e.g., the stamp of a parameter after inlining, or the stamp of a fixed node that can
* never be replaced with a pi node via canonicalization).
*/
private static Stamp getOtherSafeStamp(ValueNode x) {
if (x.isConstant() || x.graph().isAfterFixedReadPhase()) {
return x.stamp(NodeView.DEFAULT);
}
return x.stamp(NodeView.DEFAULT).unrestricted();
}
/**
* Recursively try to fold stamps within this expression using information from
* {@link #getInfoElements(ValueNode)}. It's only safe to use constants and one
* {@link InfoElement} otherwise more than one guard would be required.
*
* @param node
* @return the pair of the @{link InfoElement} used and the stamp produced for the whole
* expression
*/
Pair<InfoElement, Stamp> recursiveFoldStampFromInfo(Node node) {
return recursiveFoldStamp(node);
}
/**
* Look for a preceding guard whose condition is implied by {@code thisGuard}. If we find
* one, try to move this guard just above that preceding guard so that we can fold it:
*
* <pre>
* guard(C1); // preceding guard
* ...
* guard(C2); // thisGuard
* </pre>
*
* If C2 => C1, transform to:
*
* <pre>
* guard(C2);
* ...
* </pre>
*/
protected boolean foldPendingTest(DeoptimizingGuard thisGuard, ValueNode original, Stamp newStamp, GuardRewirer rewireGuardFunction) {
for (DeoptimizingGuard pendingGuard : pendingTests) {
LogicNode pendingCondition = pendingGuard.getCondition();
TriState result = TriState.UNKNOWN;
if (pendingCondition instanceof UnaryOpLogicNode) {
UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) pendingCondition;
if (unaryLogicNode.getValue() == original) {
result = unaryLogicNode.tryFold(newStamp);
}
} else if (pendingCondition instanceof BinaryOpLogicNode) {
BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) pendingCondition;
ValueNode x = binaryOpLogicNode.getX();
ValueNode y = binaryOpLogicNode.getY();
if (x == original) {
result = binaryOpLogicNode.tryFold(newStamp, getOtherSafeStamp(y));
} else if (y == original) {
result = binaryOpLogicNode.tryFold(getOtherSafeStamp(x), newStamp);
} else if (binaryOpLogicNode instanceof IntegerEqualsNode && y.isConstant() && x instanceof AndNode) {
AndNode and = (AndNode) x;
if (and.getY() == y && and.getX() == original) {
BinaryOp<And> andOp = ArithmeticOpTable.forStamp(newStamp).getAnd();
result = binaryOpLogicNode.tryFold(andOp.foldStamp(newStamp, getOtherSafeStamp(y)), getOtherSafeStamp(y));
}
}
}
if (result.isKnown()) {
/*
* The test case be folded using the information available but the test can only
* be moved up if we're sure there's no schedule dependence.
*/
if (canScheduleAbove(thisGuard.getCondition(), pendingGuard.asNode(), original) && foldGuard(thisGuard, pendingGuard, result.toBoolean(), newStamp, rewireGuardFunction)) {
return true;
}
}
}
return false;
}
private boolean canScheduleAbove(Node n, Node target, ValueNode knownToBeAbove) {
Block targetBlock = nodeToBlock.get(target);
Block testBlock = nodeToBlock.get(n);
if (targetBlock != null && testBlock != null) {
if (targetBlock == testBlock) {
for (Node fixed : blockToNodes.get(targetBlock)) {
if (fixed == n) {
return true;
} else if (fixed == target) {
break;
}
}
} else if (AbstractControlFlowGraph.dominates(testBlock, targetBlock)) {
return true;
}
}
InputFilter v = new InputFilter(knownToBeAbove);
n.applyInputs(v);
return v.ok;
}
protected boolean foldGuard(DeoptimizingGuard thisGuard, DeoptimizingGuard otherGuard, boolean outcome, Stamp guardedValueStamp, GuardRewirer rewireGuardFunction) {
DeoptimizationAction action = mergeActions(otherGuard.getAction(), thisGuard.getAction());
if (action != null && otherGuard.getSpeculation() == thisGuard.getSpeculation()) {
LogicNode condition = (LogicNode) thisGuard.getCondition().copyWithInputs();
/*
* We have ...; guard(C1); guard(C2);...
*
* Where the first guard is `otherGuard` and the second one `thisGuard`.
*
* Depending on `outcome`, we have C2 => C1 or C2 => !C1.
*
* - If C2 => C1, `mustDeopt` below is false and we transform to ...; guard(C2); ...
*
* - If C2 => !C1, `mustDeopt` is true and we transform to ..; guard(C1); deopt;
*/
// for the second case, the action of the deopt is copied from there:
thisGuard.setAction(action);
GuardRewirer rewirer = (guard, result, innerGuardedValueStamp, newInput) -> {
// `result` is `outcome`, `guard` is `otherGuard`
boolean mustDeopt = result == otherGuard.isNegated();
if (rewireGuardFunction.rewire(guard, mustDeopt == thisGuard.isNegated(), innerGuardedValueStamp, newInput)) {
if (!mustDeopt) {
otherGuard.setCondition(condition, thisGuard.isNegated());
otherGuard.setAction(action);
otherGuard.setReason(thisGuard.getReason());
}
return true;
}
condition.safeDelete();
return false;
};
// Move the later test up
return rewireGuards(otherGuard, outcome, null, guardedValueStamp, rewirer);
}
return false;
}
protected void registerCondition(LogicNode condition, boolean negated, GuardingNode guard) {
if (condition.hasMoreThanOneUsage()) {
registerNewStamp(condition, negated ? StampFactory.contradiction() : StampFactory.tautology(), guard);
}
conditions.push(new GuardedCondition(guard, condition, negated));
}
protected InfoElement getInfoElements(ValueNode proxiedValue) {
if (proxiedValue == null) {
return null;
}
InfoElement infoElement = map.getAndGrow(proxiedValue);
if (infoElement == null) {
infoElement = map.getAndGrow(GraphUtil.skipPi(proxiedValue));
}
return infoElement;
}
protected boolean rewireGuards(GuardingNode guard, boolean result, ValueNode proxifiedInput, Stamp guardedValueStamp, GuardRewirer rewireGuardFunction) {
counterStampsFound.increment(debug);
return rewireGuardFunction.rewire(guard, result, guardedValueStamp, proxifiedInput);
}
protected boolean tryProveCondition(LogicNode node, GuardRewirer rewireGuardFunction) {
return tryProveGuardCondition(null, node, rewireGuardFunction);
}
private InfoElement nextElement(InfoElement current) {
InfoElement parent = current.getParent();
if (parent != null) {
return parent;
} else {
ValueNode proxifiedInput = current.getProxifiedInput();
if (proxifiedInput instanceof PiNode) {
PiNode piNode = (PiNode) proxifiedInput;
return getInfoElements(piNode.getOriginalNode());
}
}
return null;
}
protected boolean tryProveGuardCondition(DeoptimizingGuard thisGuard, LogicNode node, GuardRewirer rewireGuardFunction) {
InfoElement infoElement = getInfoElements(node);
while (infoElement != null) {
Stamp stamp = infoElement.getStamp();
JavaConstant constant = (JavaConstant) stamp.asConstant();
if (constant != null) {
// No proxified input and stamp required.
return rewireGuards(infoElement.getGuard(), constant.asBoolean(), null, null, rewireGuardFunction);
}
infoElement = nextElement(infoElement);
}
for (GuardedCondition guardedCondition : this.conditions) {
TriState result = guardedCondition.getCondition().implies(guardedCondition.isNegated(), node);
if (result.isKnown()) {
return rewireGuards(guardedCondition.guard, result.toBoolean(), null, null, rewireGuardFunction);
}
}
if (node instanceof UnaryOpLogicNode) {
UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) node;
ValueNode value = unaryLogicNode.getValue();
infoElement = getInfoElements(value);
while (infoElement != null) {
Stamp stamp = infoElement.getStamp();
TriState result = unaryLogicNode.tryFold(stamp);
if (result.isKnown()) {
return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), infoElement.getStamp(), rewireGuardFunction);
}
infoElement = nextElement(infoElement);
}
Pair<InfoElement, Stamp> foldResult = recursiveFoldStampFromInfo(value);
if (foldResult != null) {
TriState result = unaryLogicNode.tryFold(foldResult.getRight());
if (result.isKnown()) {
return rewireGuards(foldResult.getLeft().getGuard(), result.toBoolean(), foldResult.getLeft().getProxifiedInput(), foldResult.getRight(), rewireGuardFunction);
}
}
if (thisGuard != null) {
Stamp newStamp = unaryLogicNode.getSucceedingStampForValue(thisGuard.isNegated());
if (newStamp != null && foldPendingTest(thisGuard, value, newStamp, rewireGuardFunction)) {
return true;
}
}
} else if (node instanceof BinaryOpLogicNode) {
BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) node;
ValueNode x = binaryOpLogicNode.getX();
ValueNode y = binaryOpLogicNode.getY();
infoElement = getInfoElements(x);
while (infoElement != null) {
TriState result = binaryOpLogicNode.tryFold(infoElement.getStamp(), y.stamp(NodeView.DEFAULT));
if (result.isKnown()) {
return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), infoElement.getStamp(), rewireGuardFunction);
}
infoElement = nextElement(infoElement);
}
if (y.isConstant()) {
Pair<InfoElement, Stamp> foldResult = recursiveFoldStampFromInfo(x);
if (foldResult != null) {
TriState result = binaryOpLogicNode.tryFold(foldResult.getRight(), y.stamp(NodeView.DEFAULT));
if (result.isKnown()) {
return rewireGuards(foldResult.getLeft().getGuard(), result.toBoolean(), foldResult.getLeft().getProxifiedInput(), foldResult.getRight(), rewireGuardFunction);
}
}
} else {
infoElement = getInfoElements(y);
while (infoElement != null) {
TriState result = binaryOpLogicNode.tryFold(x.stamp(NodeView.DEFAULT), infoElement.getStamp());
if (result.isKnown()) {
return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), infoElement.getStamp(), rewireGuardFunction);
}
infoElement = nextElement(infoElement);
}
}
/*
* For complex expressions involving constants, see if it's possible to fold the
* tests by using stamps one level up in the expression. For instance, (x + n < y)
* might fold if something is known about x and all other values are constants. The
* reason for the constant restriction is that if more than 1 real value is involved
* the code might need to adopt multiple guards to have proper dependences.
*/
if (x instanceof BinaryArithmeticNode<?> && y.isConstant()) {
BinaryArithmeticNode<?> binary = (BinaryArithmeticNode<?>) x;
if (binary.getY().isConstant()) {
infoElement = getInfoElements(binary.getX());
while (infoElement != null) {
Stamp newStampX = binary.foldStamp(infoElement.getStamp(), binary.getY().stamp(NodeView.DEFAULT));
TriState result = binaryOpLogicNode.tryFold(newStampX, y.stamp(NodeView.DEFAULT));
if (result.isKnown()) {
return rewireGuards(infoElement.getGuard(), result.toBoolean(), infoElement.getProxifiedInput(), newStampX, rewireGuardFunction);
}
infoElement = nextElement(infoElement);
}
}
}
if (thisGuard != null && binaryOpLogicNode instanceof IntegerEqualsNode && !thisGuard.isNegated()) {
if (y.isConstant() && x instanceof AndNode) {
AndNode and = (AndNode) x;
if (and.getY() == y) {
/*
* This 'and' proves something about some of the bits in and.getX().
* It's equivalent to or'ing in the mask value since those values are
* known to be set.
*/
BinaryOp<Or> op = ArithmeticOpTable.forStamp(x.stamp(NodeView.DEFAULT)).getOr();
IntegerStamp newStampX = (IntegerStamp) op.foldStamp(getSafeStamp(and.getX()), getOtherSafeStamp(y));
if (foldPendingTest(thisGuard, and.getX(), newStampX, rewireGuardFunction)) {
return true;
}
}
}
}
if (thisGuard != null) {
if (!x.isConstant()) {
Stamp newStampX = binaryOpLogicNode.getSucceedingStampForX(thisGuard.isNegated(), getSafeStamp(x), getOtherSafeStamp(y));
if (newStampX != null && foldPendingTest(thisGuard, x, newStampX, rewireGuardFunction)) {
return true;
}
}
if (!y.isConstant()) {
Stamp newStampY = binaryOpLogicNode.getSucceedingStampForY(thisGuard.isNegated(), getOtherSafeStamp(x), getSafeStamp(y));
if (newStampY != null && foldPendingTest(thisGuard, y, newStampY, rewireGuardFunction)) {
return true;
}
}
}
} else if (node instanceof ShortCircuitOrNode) {
final ShortCircuitOrNode shortCircuitOrNode = (ShortCircuitOrNode) node;
return tryProveCondition(shortCircuitOrNode.getX(), (guard, result, guardedValueStamp, newInput) -> {
if (result == !shortCircuitOrNode.isXNegated()) {
return rewireGuards(guard, true, newInput, guardedValueStamp, rewireGuardFunction);
} else {
return tryProveCondition(shortCircuitOrNode.getY(), (innerGuard, innerResult, innerGuardedValueStamp, innerNewInput) -> {
ValueNode proxifiedInput = newInput;
if (proxifiedInput == null) {
proxifiedInput = innerNewInput;
} else if (innerNewInput != null) {
if (innerNewInput != newInput) {
// Cannot canonicalize due to different proxied inputs.
return false;
}
}
// Can only canonicalize if the guards are equal.
if (innerGuard == guard) {
return rewireGuards(guard, innerResult ^ shortCircuitOrNode.isYNegated(), proxifiedInput, guardedValueStamp, rewireGuardFunction);
}
return false;
});
}
});
}
return false;
}
protected void registerNewStamp(ValueNode maybeProxiedValue, Stamp newStamp, GuardingNode guard) {
registerNewStamp(maybeProxiedValue, newStamp, guard, false);
}
protected void registerNewStamp(ValueNode maybeProxiedValue, Stamp newStamp, GuardingNode guard, boolean propagateThroughPis) {
assert maybeProxiedValue != null;
assert guard != null;
if (newStamp == null || newStamp.isUnrestricted()) {
return;
}
ValueNode value = maybeProxiedValue;
Stamp stamp = newStamp;
while (stamp != null && value != null) {
ValueNode proxiedValue = null;
if (value instanceof PiNode) {
proxiedValue = value;
}
counterStampsRegistered.increment(debug);
debug.log("\t Saving stamp for node %s stamp %s guarded by %s", value, stamp, guard);
assert value instanceof LogicNode || stamp.isCompatible(value.stamp(NodeView.DEFAULT)) : stamp + " vs. " + value.stamp(NodeView.DEFAULT) + " (" + value + ")";
map.setAndGrow(value, new InfoElement(stamp, guard, proxiedValue, map.getAndGrow(value)));
undoOperations.push(value);
if (propagateThroughPis && value instanceof PiNode) {
PiNode piNode = (PiNode) value;
value = piNode.getOriginalNode();
} else if (value instanceof StampInverter) {
StampInverter stampInverter = (StampInverter) value;
value = stampInverter.getValue();
stamp = stampInverter.invertStamp(stamp);
} else {
break;
}
}
}
protected void processAbstractBegin(AbstractBeginNode beginNode) {
Node predecessor = beginNode.predecessor();
if (predecessor instanceof IfNode) {
IfNode ifNode = (IfNode) predecessor;
boolean negated = (ifNode.falseSuccessor() == beginNode);
LogicNode condition = ifNode.condition();
registerNewCondition(condition, negated, beginNode);
} else if (predecessor instanceof TypeSwitchNode) {
TypeSwitchNode typeSwitch = (TypeSwitchNode) predecessor;
processTypeSwitch(beginNode, typeSwitch);
} else if (predecessor instanceof IntegerSwitchNode) {
IntegerSwitchNode integerSwitchNode = (IntegerSwitchNode) predecessor;
processIntegerSwitch(beginNode, integerSwitchNode);
}
}
private static boolean maybeMultipleUsages(ValueNode value) {
if (value.hasMoreThanOneUsage()) {
return true;
} else {
return value instanceof ProxyNode ||
value instanceof PiNode ||
value instanceof StampInverter;
}
}
protected void processIntegerSwitch(AbstractBeginNode beginNode, IntegerSwitchNode integerSwitchNode) {
ValueNode value = integerSwitchNode.value();
if (maybeMultipleUsages(value)) {
Stamp stamp = integerSwitchNode.getValueStampForSuccessor(beginNode);
if (stamp != null) {
registerNewStamp(value, stamp, beginNode);
}
}
}
protected void processTypeSwitch(AbstractBeginNode beginNode, TypeSwitchNode typeSwitch) {
ValueNode hub = typeSwitch.value();
if (hub instanceof LoadHubNode) {
LoadHubNode loadHub = (LoadHubNode) hub;
ValueNode value = loadHub.getValue();
if (maybeMultipleUsages(value)) {
Stamp stamp = typeSwitch.getValueStampForSuccessor(beginNode);
if (stamp != null) {
registerNewStamp(value, stamp, beginNode);
}
}
}
}
@Override
public void exit(Block b, Marks marks) {
int infoElementsMark = marks.infoElementOperations;
while (undoOperations.size() > infoElementsMark) {
Node node = undoOperations.pop();
if (node.isAlive()) {
map.set(node, map.get(node).getParent());
}
}
int conditionsMark = marks.conditions;
while (conditions.size() > conditionsMark) {
conditions.pop();
}
}
}
@FunctionalInterface
protected interface InfoElementProvider {
Iterable<InfoElement> getInfoElements(ValueNode value);
}
/**
* Checks for safe nodes when moving pending tests up.
*/
static class InputFilter extends Node.EdgeVisitor {
boolean ok;
private ValueNode value;
InputFilter(ValueNode value) {
this.value = value;
this.ok = true;
}
@Override
public Node apply(Node node, Node curNode) {
if (!ok) {
// Abort the recursion
return curNode;
}
if (!(curNode instanceof ValueNode)) {
ok = false;
return curNode;
}
ValueNode curValue = (ValueNode) curNode;
if (curValue.isConstant() || curValue == value || curValue instanceof ParameterNode) {
return curNode;
}
if (curValue instanceof BinaryNode || curValue instanceof UnaryNode) {
curValue.applyInputs(this);
} else {
ok = false;
}
return curNode;
}
}
@FunctionalInterface
protected interface GuardRewirer {
/**
* Called if the condition could be proven to have a constant value ({@code result}) under
* {@code guard}.
*
* @param guard the guard whose result is proven
* @param result the known result of the guard
* @param newInput new input to pi nodes depending on the new guard
* @return whether the transformation could be applied
*/
boolean rewire(GuardingNode guard, boolean result, Stamp guardedValueStamp, ValueNode newInput);
}
protected static final class InfoElement {
private final Stamp stamp;
private final GuardingNode guard;
private final ValueNode proxifiedInput;
private final InfoElement parent;
public InfoElement(Stamp stamp, GuardingNode guard, ValueNode proxifiedInput, InfoElement parent) {
this.stamp = stamp;
this.guard = guard;
this.proxifiedInput = proxifiedInput;
this.parent = parent;
}
public InfoElement getParent() {
return parent;
}
public Stamp getStamp() {
return stamp;
}
public GuardingNode getGuard() {
return guard;
}
public ValueNode getProxifiedInput() {
return proxifiedInput;
}
@Override
public String toString() {
return stamp + " -> " + guard;
}
}
@Override
public float codeSizeIncrease() {
return 1.5f;
}
}