--- a/hotspot/src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.phases.common/src/org/graalvm/compiler/phases/common/NewConditionalEliminationPhase.java Fri May 12 13:14:25 2017 -0700
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,1035 +0,0 @@
-/*
- * Copyright (c) 2015, 2017, 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 java.util.ArrayDeque;
-import java.util.Deque;
-import java.util.List;
-
-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.Debug;
-import org.graalvm.compiler.debug.DebugCloseable;
-import org.graalvm.compiler.debug.DebugCounter;
-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.LogicNode;
-import org.graalvm.compiler.nodes.LoopExitNode;
-import org.graalvm.compiler.nodes.MergeNode;
-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.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.TypeSwitchNode;
-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.tiers.PhaseContext;
-import org.graalvm.util.EconomicMap;
-import org.graalvm.util.Equivalence;
-import org.graalvm.util.MapCursor;
-import org.graalvm.util.Pair;
-
-import jdk.vm.ci.meta.JavaConstant;
-import jdk.vm.ci.meta.TriState;
-
-public class NewConditionalEliminationPhase extends BasePhase<PhaseContext> {
-
- private static final DebugCounter counterStampsRegistered = Debug.counter("StampsRegistered");
- private static final DebugCounter counterStampsFound = Debug.counter("StampsFound");
- private static final DebugCounter counterIfsKilled = Debug.counter("CE_KilledIfs");
- private static final DebugCounter counterPhiStampsImproved = Debug.counter("CE_ImprovedPhis");
- private final boolean fullSchedule;
-
- public NewConditionalEliminationPhase(boolean fullSchedule) {
- this.fullSchedule = fullSchedule;
- }
-
- @Override
- @SuppressWarnings("try")
- protected void run(StructuredGraph graph, PhaseContext context) {
- try (Debug.Scope s = Debug.scope("DominatorConditionalElimination")) {
- BlockMap<List<Node>> blockToNodes = null;
- ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, true, true);
- if (fullSchedule) {
- cfg.visitDominatorTree(new MoveGuardsUpwards(), graph.hasValueProxies());
- SchedulePhase.run(graph, SchedulePhase.SchedulingStrategy.EARLIEST, cfg);
- blockToNodes = graph.getLastSchedule().getBlockToNodesMap();
- }
-
- Instance visitor = new Instance(graph, blockToNodes, context);
- cfg.visitDominatorTree(visitor, graph.hasValueProxies());
- }
- }
-
- 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;
- for (GuardNode guard : mergeNode.guards().snapshot()) {
- try (DebugCloseable closeable = guard.withNodeSourcePosition()) {
- GuardNode newlyCreatedGuard = new GuardNode(guard.getCondition(), anchorBlock.getBeginNode(), guard.getReason(), guard.getAction(), guard.isNegated(), guard.getSpeculation());
- GuardNode newGuard = mergeNode.graph().unique(newlyCreatedGuard);
- guard.replaceAndDelete(newGuard);
- }
- }
- }
-
- 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()) {
- JavaConstant 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);
- 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 class Instance implements ControlFlowGraph.RecursiveVisitor<Integer> {
- protected final NodeMap<InfoElement> map;
- protected final BlockMap<List<Node>> blockToNodes;
- protected final CanonicalizerTool tool;
- protected final NodeStack undoOperations;
- protected final StructuredGraph graph;
- protected final EconomicMap<MergeNode, EconomicMap<ValuePhiNode, PhiInfoElement>> mergeMaps;
-
- /**
- * Tests which may be eliminated because post dominating tests to prove a broader condition.
- */
- private Deque<PendingTest> pendingTests;
-
- public Instance(StructuredGraph graph, BlockMap<List<Node>> blockToNodes, PhaseContext context) {
- this.graph = graph;
- this.blockToNodes = blockToNodes;
- this.undoOperations = new NodeStack();
- this.map = graph.createNodeMap();
- pendingTests = new ArrayDeque<>();
- tool = GraphUtil.getDefaultSimplifier(context.getMetaAccess(), context.getConstantReflection(), context.getConstantFieldProvider(), false, graph.getAssumptions(), graph.getOptions(),
- context.getLowerer());
- mergeMaps = EconomicMap.create();
- }
-
- 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());
- } else {
- DeoptimizeNode deopt = node.graph().add(new DeoptimizeNode(node.getAction(), node.getReason(), node.getSpeculation()));
- AbstractBeginNode beginNode = (AbstractBeginNode) node.getAnchor();
- FixedNode next = beginNode.next();
- beginNode.setNext(deopt);
- GraphUtil.killCFG(next);
- }
- 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);
- } else {
- DeoptimizeNode deopt = node.graph().add(new DeoptimizeNode(node.getAction(), node.getReason(), node.getSpeculation()));
- deopt.setStateBefore(node.stateBefore());
- node.replaceAtPredecessor(deopt);
- GraphUtil.killCFG(node);
- }
- Debug.log("Kill fixed guard guard");
- return true;
- })) {
- registerNewCondition(node.condition(), node.isNegated(), node);
- }
- }
-
- protected void processIf(IfNode node) {
- tryProveCondition(node.condition(), (guard, result, guardedValueStamp, newInput) -> {
- AbstractBeginNode survivingSuccessor = node.getSuccessor(result);
- survivingSuccessor.replaceAtUsages(InputType.Guard, guard.asNode());
- survivingSuccessor.replaceAtPredecessor(null);
- node.replaceAtPredecessor(survivingSuccessor);
- GraphUtil.killCFG(node);
- counterIfsKilled.increment();
- return true;
- });
- }
-
- @Override
- public Integer enter(Block block) {
- int mark = undoOperations.size();
- Debug.log("[Pre Processing block %s]", block);
- // For now conservatively collect guards only within the same block.
- pendingTests.clear();
- if (blockToNodes != null) {
- for (Node n : blockToNodes.get(block)) {
- if (n.isAlive()) {
- processNode(n);
- }
- }
- } else {
- processBlock(block);
- }
- return mark;
- }
-
- 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);
- }
- }
- }
-
- private 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();
- PhiInfoElement phiInfoElements = entries.getValue();
- Stamp bestPossibleStamp = null;
- for (int i = 0; i < phi.valueCount(); ++i) {
- ValueNode valueAt = phi.valueAt(i);
- Stamp curBestStamp = valueAt.stamp();
- 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();
- 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 {
- 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()).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;
- }
- ValueNode valueNode = graph.maybeAddOrUnique(PiNode.create(input, curBestStamp, (ValueNode) infoElement.guard));
- valueAt = valueNode;
- }
- newPhi.addInput(valueAt);
- }
- counterPhiStampsImproved.increment();
- phi.replaceAtUsagesAndDelete(newPhi);
- }
- }
- }
- }
- }
-
- private 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().tryImproveWith(newStamp) != null) {
- if (mergeMap == null) {
- mergeMap = EconomicMap.create();
- 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)) {
- Stamp newStamp = unaryLogicNode.getSucceedingStampForValue(negated);
- registerNewStamp(value, newStamp, guard);
- }
- } 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()).getOr();
- IntegerStamp newStampX = (IntegerStamp) op.foldStamp(getSafeStamp(andX), getOtherSafeStamp(y));
- registerNewStamp(andX, newStampX, guard);
- }
- }
- }
- }
- if (guard instanceof DeoptimizingGuard) {
- pendingTests.push(new PendingTest(condition, (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());
- 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();
- }
-
- /**
- * 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()) {
- return x.stamp();
- }
- return x.stamp().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);
- }
-
- protected boolean foldPendingTest(DeoptimizingGuard thisGuard, ValueNode original, Stamp newStamp, GuardRewirer rewireGuardFunction) {
- for (PendingTest pending : pendingTests) {
- TriState result = TriState.UNKNOWN;
- if (pending.condition instanceof UnaryOpLogicNode) {
- UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) pending.condition;
- if (unaryLogicNode.getValue() == original) {
- result = unaryLogicNode.tryFold(newStamp);
- }
- } else if (pending.condition instanceof BinaryOpLogicNode) {
- BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) pending.condition;
- 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. For now limit it to
- * the original node and constants.
- */
- InputFilter v = new InputFilter(original);
- thisGuard.getCondition().applyInputs(v);
- if (v.ok && foldGuard(thisGuard, pending.guard, newStamp, rewireGuardFunction)) {
- return true;
- }
- }
- }
- return false;
- }
-
- protected boolean foldGuard(DeoptimizingGuard thisGuard, DeoptimizingGuard otherGuard, Stamp guardedValueStamp, GuardRewirer rewireGuardFunction) {
- if (otherGuard.getAction() == thisGuard.getAction() && otherGuard.getSpeculation() == thisGuard.getSpeculation()) {
- LogicNode condition = (LogicNode) thisGuard.getCondition().copyWithInputs();
- GuardRewirer rewirer = (guard, result, innerGuardedValueStamp, newInput) -> {
- if (rewireGuardFunction.rewire(guard, result, innerGuardedValueStamp, newInput)) {
- otherGuard.setCondition(condition, thisGuard.isNegated());
- return true;
- }
- condition.safeDelete();
- return false;
- };
- // Move the later test up
- return rewireGuards(otherGuard, !thisGuard.isNegated(), null, guardedValueStamp, rewirer);
- }
- return false;
- }
-
- protected void registerCondition(LogicNode condition, boolean negated, GuardingNode guard) {
- if (condition.getUsageCount() > 1) {
- registerNewStamp(condition, negated ? StampFactory.contradiction() : StampFactory.tautology(), guard);
- }
- }
-
- protected InfoElement getInfoElements(ValueNode proxiedValue) {
- ValueNode value = GraphUtil.skipPi(proxiedValue);
- if (value == null) {
- return null;
- }
- return map.getAndGrow(value);
- }
-
- protected boolean rewireGuards(GuardingNode guard, boolean result, ValueNode proxifiedInput, Stamp guardedValueStamp, GuardRewirer rewireGuardFunction) {
- counterStampsFound.increment();
- 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);
- if (infoElement != null) {
- assert infoElement.getStamp() == StampFactory.tautology() || infoElement.getStamp() == StampFactory.contradiction();
- // No proxified input and stamp required.
- return rewireGuards(infoElement.getGuard(), infoElement.getStamp() == StampFactory.tautology(), 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;
- infoElement = getInfoElements(binaryOpLogicNode);
- while (infoElement != null) {
- if (infoElement.getStamp().equals(StampFactory.contradiction())) {
- return rewireGuards(infoElement.getGuard(), false, infoElement.getProxifiedInput(), null, rewireGuardFunction);
- } else if (infoElement.getStamp().equals(StampFactory.tautology())) {
- return rewireGuards(infoElement.getGuard(), true, infoElement.getProxifiedInput(), null, rewireGuardFunction);
- }
- infoElement = nextElement(infoElement);
- }
-
- ValueNode x = binaryOpLogicNode.getX();
- ValueNode y = binaryOpLogicNode.getY();
- infoElement = getInfoElements(x);
- while (infoElement != null) {
- TriState result = binaryOpLogicNode.tryFold(infoElement.getStamp(), y.stamp());
- 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());
- 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(), 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());
- TriState result = binaryOpLogicNode.tryFold(newStampX, y.stamp());
- 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()).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) {
- assert maybeProxiedValue != null;
- assert guard != null;
- if (newStamp != null) {
- ValueNode value = maybeProxiedValue;
- Stamp stamp = newStamp;
- ValueNode proxiedValue = null;
- if (value instanceof PiNode) {
- proxiedValue = value;
- }
- do {
- counterStampsRegistered.increment();
- Debug.log("\t Saving stamp for node %s stamp %s guarded by %s", value, stamp, guard);
- assert value instanceof LogicNode || stamp.isCompatible(value.stamp()) : stamp + " vs. " + value.stamp() + " (" + value + ")";
- map.setAndGrow(value, new InfoElement(stamp, guard, proxiedValue, map.getAndGrow(value)));
- undoOperations.push(value);
- if (value instanceof StampInverter) {
- StampInverter stampInverter = (StampInverter) value;
- value = stampInverter.getValue();
- stamp = stampInverter.invertStamp(stamp);
- } else {
- value = null;
- stamp = null;
- }
- } while (value != null && stamp != null);
- }
- }
-
- 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;
- }
- }
-
- 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, Integer state) {
- int mark = state;
- while (undoOperations.size() > mark) {
- Node node = undoOperations.pop();
- if (node.isAlive()) {
- map.set(node, map.get(node).getParent());
- }
- }
- }
- }
-
- @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 class PendingTest {
- private final LogicNode condition;
- private final DeoptimizingGuard guard;
-
- public PendingTest(LogicNode condition, DeoptimizingGuard guard) {
- this.condition = condition;
- this.guard = guard;
- }
- }
-
- 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;
- }
-}