/*
 * Copyright (c) 2015, 2016, 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.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;
import java.util.function.Function;

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.core.common.type.TypeReference;
import org.graalvm.compiler.debug.Debug;
import org.graalvm.compiler.debug.DebugCounter;
import org.graalvm.compiler.graph.Node;
import org.graalvm.compiler.graph.NodeMap;
import org.graalvm.compiler.graph.spi.CanonicalizerTool;
import org.graalvm.compiler.nodeinfo.InputType;
import org.graalvm.compiler.nodes.AbstractBeginNode;
import org.graalvm.compiler.nodes.BeginNode;
import org.graalvm.compiler.nodes.BinaryOpLogicNode;
import org.graalvm.compiler.nodes.ConditionAnchorNode;
import org.graalvm.compiler.nodes.ConstantNode;
import org.graalvm.compiler.nodes.DeoptimizeNode;
import org.graalvm.compiler.nodes.DeoptimizingGuard;
import org.graalvm.compiler.nodes.FixedGuardNode;
import org.graalvm.compiler.nodes.FixedNode;
import org.graalvm.compiler.nodes.GuardNode;
import org.graalvm.compiler.nodes.GuardProxyNode;
import org.graalvm.compiler.nodes.IfNode;
import org.graalvm.compiler.nodes.LogicNode;
import org.graalvm.compiler.nodes.LoopExitNode;
import org.graalvm.compiler.nodes.ParameterNode;
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.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.ObjectEqualsNode;
import org.graalvm.compiler.nodes.calc.PointerEqualsNode;
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.LoadFieldNode;
import org.graalvm.compiler.nodes.java.TypeSwitchNode;
import org.graalvm.compiler.nodes.spi.NodeWithState;
import org.graalvm.compiler.nodes.util.GraphUtil;
import org.graalvm.compiler.phases.BasePhase;
import org.graalvm.compiler.phases.common.LoweringPhase.Frame;
import org.graalvm.compiler.phases.schedule.SchedulePhase;
import org.graalvm.compiler.phases.tiers.PhaseContext;

import jdk.vm.ci.meta.JavaConstant;
import jdk.vm.ci.meta.TriState;

public class DominatorConditionalEliminationPhase 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 counterLFFolded = Debug.counter("ConstantLFFolded");
    private final boolean fullSchedule;

    public DominatorConditionalEliminationPhase(boolean fullSchedule) {
        this.fullSchedule = fullSchedule;
    }

    @Override
    @SuppressWarnings("try")
    protected void run(StructuredGraph graph, PhaseContext context) {
        try (Debug.Scope s = Debug.scope("DominatorConditionalElimination")) {
            Function<Block, Iterable<? extends Node>> blockToNodes;
            Function<Node, Block> nodeToBlock;
            Block startBlock;

            if (fullSchedule) {
                SchedulePhase schedule = new SchedulePhase(SchedulePhase.SchedulingStrategy.EARLIEST);
                schedule.apply(graph);
                ControlFlowGraph cfg = graph.getLastSchedule().getCFG();
                cfg.computePostdominators();
                blockToNodes = b -> graph.getLastSchedule().getBlockToNodesMap().get(b);
                nodeToBlock = n -> graph.getLastSchedule().getNodeToBlockMap().get(n);
                startBlock = cfg.getStartBlock();
            } else {
                ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, true, true);
                BlockMap<List<FixedNode>> nodes = new BlockMap<>(cfg);
                for (Block b : cfg.getBlocks()) {
                    ArrayList<FixedNode> curNodes = new ArrayList<>();
                    for (FixedNode node : b.getNodes()) {
                        if (node instanceof AbstractBeginNode || node instanceof FixedGuardNode || node instanceof ConditionAnchorNode || node instanceof IfNode) {
                            curNodes.add(node);
                        }
                    }
                    nodes.put(b, curNodes);
                }
                blockToNodes = b -> nodes.get(b);
                nodeToBlock = n -> cfg.blockFor(n);
                startBlock = cfg.getStartBlock();
            }
            new Instance(graph, blockToNodes, nodeToBlock, context).processBlock(startBlock);
        }
    }

    public static class Instance {
        protected NodeMap<Info> map;
        protected Deque<LoopExitNode> loopExits;
        protected final Function<Block, Iterable<? extends Node>> blockToNodes;
        protected final Function<Node, Block> nodeToBlock;
        protected final CanonicalizerTool tool;
        
Tests which may be eliminated because post dominating tests to prove a broader condition.
/**
         * Tests which may be eliminated because post dominating tests to prove a broader condition.
         */
        private Deque<PendingTest> pendingTests;

        public Instance(StructuredGraph graph, Function<Block, Iterable<? extends Node>> blockToNodes,
                        Function<Node, Block> nodeToBlock, PhaseContext context) {
            map = graph.createNodeMap();
            loopExits = new ArrayDeque<>();
            this.blockToNodes = blockToNodes;
            this.nodeToBlock = nodeToBlock;
            pendingTests = new ArrayDeque<>();
            tool = GraphUtil.getDefaultSimplifier(context.getMetaAccess(), context.getConstantReflection(), context.getConstantFieldProvider(), false, graph.getAssumptions(), context.getLowerer());
        }

        public void processBlock(Block startBlock) {
            LoweringPhase.processBlock(new InstanceFrame(startBlock, null));
        }

        public class InstanceFrame extends LoweringPhase.Frame<InstanceFrame> {
            protected List<Runnable> undoOperations = new ArrayList<>();

            public InstanceFrame(Block block, InstanceFrame parent) {
                super(block, parent);
            }

            @Override
            public Frame<?> enter(Block b) {
                return new InstanceFrame(b, this);
            }

            @Override
            public void postprocess() {
                Debug.log("[Post Processing block %s]", block);
                undoOperations.forEach(x -> x.run());
            }

            protected void processConditionAnchor(ConditionAnchorNode node) {
                tryProveCondition(node.condition(), (guard, result) -> {
                    if (result != node.isNegated()) {
                        node.replaceAtUsages(guard);
                        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) -> {
                    if (result != node.isNegated()) {
                        node.replaceAndDelete(guard);
                    } 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) -> {
                    if (result != node.isNegated()) {
                        node.replaceAtUsages(guard);
                        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) -> {
                    AbstractBeginNode survivingSuccessor = node.getSuccessor(result);
                    survivingSuccessor.replaceAtUsages(InputType.Guard, guard);
                    survivingSuccessor.replaceAtPredecessor(null);
                    node.replaceAtPredecessor(survivingSuccessor);
                    GraphUtil.killCFG(node);
                    if (survivingSuccessor instanceof BeginNode) {
                        undoOperations.add(() -> {
                            if (survivingSuccessor.isAlive()) {
                                ((BeginNode) survivingSuccessor).trySimplify();
                            }
                        });
                    }
                    Debug.log("Kill if");
                    counterIfsKilled.increment();
                    return true;
                });
            }

            @Override
            public void preprocess() {
                Debug.log("[Pre Processing block %s]", block);
                AbstractBeginNode beginNode = block.getBeginNode();
                if (beginNode instanceof LoopExitNode && beginNode.isAlive()) {
                    LoopExitNode loopExitNode = (LoopExitNode) beginNode;
                    Instance.this.loopExits.push(loopExitNode);
                    undoOperations.add(() -> loopExits.pop());
                } else if (block.getDominator() != null && (block.getDominator().getLoopDepth() > block.getLoopDepth() ||
                                (block.getDominator().getLoopDepth() == block.getLoopDepth() && block.getDominator().getLoop() != block.getLoop()))) {
                    // We are exiting the loop, but there is not a single loop exit block along our
                    // dominator tree (e.g., we are a merge of two loop exits).
                    final NodeMap<Info> oldMap = map;
                    final Deque<LoopExitNode> oldLoopExits = loopExits;
                    map = map.graph().createNodeMap();
                    loopExits = new ArrayDeque<>();
                    undoOperations.add(() -> {
                        map = oldMap;
                        loopExits = oldLoopExits;
                    });
                }

                // For now conservatively collect guards only within the same block.
                pendingTests.clear();
                for (Node n : blockToNodes.apply(block)) {
                    if (n.isAlive()) {
                        processNode(n);
                    }
                }
            }

            protected void processNode(Node node) {
                if (node instanceof NodeWithState && !(node instanceof GuardingNode)) {
                    pendingTests.clear();
                }
                if (node instanceof AbstractBeginNode) {
                    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 {
                    return;
                }
            }

            protected void registerNewCondition(LogicNode condition, boolean negated, ValueNode guard) {
                if (!negated && condition instanceof PointerEqualsNode) {
                    PointerEqualsNode pe = (PointerEqualsNode) condition;
                    ValueNode x = pe.getX();
                    ValueNode y = pe.getY();
                    if (y.isConstant()) {
                        JavaConstant constant = y.asJavaConstant();
                        Stamp succeeding = pe.getSucceedingStampForX(negated);
                        if (succeeding == null && pe instanceof ObjectEqualsNode && guard instanceof FixedGuardNode) {
                            succeeding = y.stamp();
                        }
                        if (succeeding != null) {
                            if (y.stamp() instanceof ObjectStamp) {
                                GuardedConstantStamp cos = new GuardedConstantStamp(constant, (ObjectStamp) succeeding);
                                registerNewStamp(x, cos, guard);
                                return;
                            }
                        }
                    }
                }
                if (condition instanceof UnaryOpLogicNode) {
                    UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) condition;
                    Stamp newStamp = unaryLogicNode.getSucceedingStampForValue(negated);
                    registerNewStamp(unaryLogicNode.getValue(), newStamp, guard);
                } else if (condition instanceof BinaryOpLogicNode) {
                    BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) condition;
                    ValueNode x = binaryOpLogicNode.getX();
                    if (!x.isConstant()) {
                        Stamp newStampX = binaryOpLogicNode.getSucceedingStampForX(negated);
                        registerNewStamp(x, newStampX, guard);
                    }

                    ValueNode y = binaryOpLogicNode.getY();
                    if (!y.isConstant()) {
                        Stamp newStampY = binaryOpLogicNode.getSucceedingStampForY(negated);
                        registerNewStamp(y, newStampY, guard);
                    }
                    if (condition instanceof IntegerEqualsNode && guard instanceof DeoptimizingGuard && !negated) {
                        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(and.getX().stamp(), y.stamp());
                                registerNewStamp(and.getX(), newStampX, guard);
                            }
                        }
                    }
                }
                if (guard instanceof DeoptimizingGuard) {
                    pendingTests.push(new PendingTest(condition, (DeoptimizingGuard) guard));
                }
                registerCondition(condition, negated, guard);
            }

            @SuppressWarnings("try")
            protected Pair<InfoElement, Stamp> foldFromConstLoadField(LoadFieldNode loadFieldNode, InfoElementProvider info) {
                ValueNode object = loadFieldNode.object();
                if (!loadFieldNode.field().isStatic()) {
                    // look if we got stamp info for the object and return the constant stamp
                    Pair<InfoElement, Stamp> pair = getConstantObjectStamp(info, object);
                    if (pair == null) {
                        pair = recursiveFoldStamp(object, info);
                    }
                    if (pair != null) {
                        Stamp s = pair.second;
                        if (s instanceof GuardedConstantStamp) {
                            ConstantNode c = tryFoldFromLoadField(loadFieldNode, pair.second);
                            if (c != null) {
                                counterLFFolded.increment();
                                if (c.stamp() instanceof ObjectStamp) {
                                    GuardedConstantStamp cos = new GuardedConstantStamp(c.asJavaConstant(), (ObjectStamp) c.stamp());
                                    return new Pair<>(pair.first, cos);
                                }
                                return new Pair<>(pair.first, c.stamp());
                            }
                        }
                    }
                }
                return null;
            }

            private ConstantNode tryFoldFromLoadField(LoadFieldNode lf, Stamp x) {
                GuardedConstantStamp cos = (GuardedConstantStamp) x;
                return lf.asConstant(tool, cos.objectConstant);
            }

            private Pair<InfoElement, Stamp> getConstantObjectStamp(InfoElementProvider infos, ValueNode n) {
                for (InfoElement infoElement : infos.getInfoElements(n)) {
                    Stamp s = infoElement.getStamp();
                    if (s instanceof GuardedConstantStamp) {
                        return new Pair<>(infoElement, s);
                    }
                }
                return null;
            }

            Pair<InfoElement, Stamp> recursiveFoldStamp(Node node, InfoElementProvider info) {
                if (node instanceof LoadFieldNode) {
                    Pair<InfoElement, Stamp> pair = foldFromConstLoadField((LoadFieldNode) node, info);
                    if (pair != null) {
                        return pair;
                    }
                }
                if (node instanceof UnaryNode) {
                    UnaryNode unary = (UnaryNode) node;
                    ValueNode value = unary.getValue();
                    for (InfoElement infoElement : info.getInfoElements(value)) {
                        Stamp result = unary.foldStamp(infoElement.getStamp());
                        if (result != null) {
                            return new Pair<>(infoElement, result);
                        }
                    }
                    Pair<InfoElement, Stamp> foldResult = recursiveFoldStamp(value, info);
                    if (foldResult != null) {
                        Stamp result = unary.foldStamp(foldResult.second);
                        if (result != null) {
                            return new Pair<>(foldResult.first, result);
                        }
                    }
                } else if (node instanceof BinaryNode) {
                    BinaryNode binary = (BinaryNode) node;
                    ValueNode y = binary.getY();
                    ValueNode x = binary.getX();
                    if (y.isConstant()) {
                        for (InfoElement infoElement : info.getInfoElements(x)) {
                            Stamp result = binary.foldStamp(infoElement.stamp, y.stamp());
                            if (result != null) {
                                return new Pair<>(infoElement, result);
                            }
                        }
                        Pair<InfoElement, Stamp> foldResult = recursiveFoldStamp(x, info);
                        if (foldResult != null) {
                            Stamp result = binary.foldStamp(foldResult.second, y.stamp());
                            if (result != null) {
                                return new Pair<>(foldResult.first, result);
                            }
                        }
                    } else if (x instanceof LoadFieldNode || y instanceof LoadFieldNode) {
                        boolean useX = x instanceof LoadFieldNode;
                        Pair<InfoElement, Stamp> foldResult = recursiveFoldStamp(useX ? x : y, info);
                        if (foldResult != null) {
                            Stamp result = binary.foldStamp(useX ? foldResult.second : x.stamp(), useX ? y.stamp() : foldResult.second);
                            if (result != null) {
                                return new Pair<>(foldResult.first, result);
                            }
                        }
                    }
                }
                return null;
            }

            
Recursively try to fold stamps within this expression using information from getInfoElements(ValueNode). It's only safe to use constants and one InfoElement otherwise more than one guard would be required. 
Params:
node – 
Returns:
the pair of the @{link InfoElement} used and the stamp produced for the whole
        expression/**
             * 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, (value) -> getInfoElements(value));
            }

            
Recursively try to fold stamps within this expression using newStamp if the node original is encountered in the expression. It's only safe to use constants and the passed in stamp otherwise more than one guard would be required. 
Params:
node – 
original – 
newStamp – 
Returns:
the improved stamp or null is nothing could be done/**
             * Recursively try to fold stamps within this expression using {@code newStamp} if the
             * node {@code original} is encountered in the expression. It's only safe to use
             * constants and the passed in stamp otherwise more than one guard would be required.
             *
             * @param node
             * @param original
             * @param newStamp
             * @return the improved stamp or null is nothing could be done
             */
            @SuppressWarnings("unchecked")
            Stamp recursiveFoldStamp(Node node, ValueNode original, Stamp newStamp) {
                Debug.log("Recursively fold stamp for node %s original %s stamp %s", node, original, newStamp);
                InfoElement element = new InfoElement(newStamp, original);
                Pair<InfoElement, Stamp> result = recursiveFoldStamp(node, (value) -> value == original ? Collections.singleton(element) : Collections.EMPTY_LIST);
                if (result != null) {
                    return result.second;
                }
                return null;
            }

            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);
                        }
                        if (!result.isKnown()) {
                            Stamp foldResult = recursiveFoldStamp(unaryLogicNode.getValue(), original, newStamp);
                            if (foldResult != null) {
                                result = unaryLogicNode.tryFold(foldResult);
                            }
                        }
                    } else if (pending.condition instanceof BinaryOpLogicNode) {
                        BinaryOpLogicNode binaryOpLogicNode = (BinaryOpLogicNode) pending.condition;
                        ValueNode x = binaryOpLogicNode.getX();
                        ValueNode y = binaryOpLogicNode.getY();
                        if (binaryOpLogicNode.getX() == original) {
                            result = binaryOpLogicNode.tryFold(newStamp, binaryOpLogicNode.getY().stamp());
                        } 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, y.stamp()), y.stamp());
                            }
                        }
                        if (!result.isKnown() && y.isConstant()) {
                            Stamp foldResult = recursiveFoldStamp(x, original, newStamp);
                            if (foldResult != null) {
                                result = binaryOpLogicNode.tryFold(foldResult, y.stamp());
                            }
                        }
                    }
                    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, rewireGuardFunction)) {
                            return true;
                        }
                    }
                }
                return false;
            }

            protected boolean foldGuard(DeoptimizingGuard thisGuard, DeoptimizingGuard otherGuard, GuardRewirer rewireGuardFunction) {
                if (otherGuard.getAction() == thisGuard.getAction() && otherGuard.getReason() == thisGuard.getReason() && otherGuard.getSpeculation() == thisGuard.getSpeculation()) {
                    LogicNode condition = (LogicNode) thisGuard.getCondition().copyWithInputs();
                    GuardRewirer rewirer = (guard, result) -> {
                        if (rewireGuardFunction.rewire(guard, result)) {
                            otherGuard.setCondition(condition, thisGuard.isNegated());
                            return true;
                        }
                        condition.safeDelete();
                        return false;
                    };
                    // Move the later test up
                    return rewireGuards(otherGuard.asNode(), !thisGuard.isNegated(), rewirer);
                }
                return false;
            }

            protected void registerCondition(LogicNode condition, boolean negated, ValueNode guard) {
                registerNewStamp(condition, negated ? StampFactory.contradiction() : StampFactory.tautology(), guard);
            }

            protected Iterable<InfoElement> getInfoElements(ValueNode proxiedValue) {
                ValueNode value = GraphUtil.unproxify(proxiedValue);
                if (value == null) {
                    return Collections.emptyList();
                }
                Info info = map.get(value);
                if (info == null) {
                    return Collections.emptyList();
                } else {
                    return info.getElements();
                }
            }

            protected boolean rewireGuards(ValueNode guard, boolean result, GuardRewirer rewireGuardFunction) {
                assert guard instanceof GuardingNode;
                counterStampsFound.increment();
                ValueNode proxiedGuard = proxyGuard(guard);
                return rewireGuardFunction.rewire(proxiedGuard, result);
            }

            protected ValueNode proxyGuard(ValueNode guard) {
                ValueNode proxiedGuard = guard;
                if (!Instance.this.loopExits.isEmpty()) {
                    while (proxiedGuard instanceof GuardProxyNode) {
                        proxiedGuard = ((GuardProxyNode) proxiedGuard).value();
                    }
                    Block guardBlock = nodeToBlock.apply(proxiedGuard);
                    assert guardBlock != null;
                    for (Iterator<LoopExitNode> iter = loopExits.descendingIterator(); iter.hasNext();) {
                        LoopExitNode loopExitNode = iter.next();
                        Block loopExitBlock = nodeToBlock.apply(loopExitNode);
                        if (guardBlock != loopExitBlock && AbstractControlFlowGraph.dominates(guardBlock, loopExitBlock)) {
                            Block loopBeginBlock = nodeToBlock.apply(loopExitNode.loopBegin());
                            if (!AbstractControlFlowGraph.dominates(guardBlock, loopBeginBlock) || guardBlock == loopBeginBlock) {
                                proxiedGuard = proxiedGuard.graph().unique(new GuardProxyNode((GuardingNode) proxiedGuard, loopExitNode));
                            }
                        }
                    }
                }
                return proxiedGuard;
            }

            protected boolean tryProveCondition(LogicNode node, GuardRewirer rewireGuardFunction) {
                return tryProveGuardCondition(null, node, rewireGuardFunction);
            }

            protected boolean tryProveGuardCondition(DeoptimizingGuard thisGuard, LogicNode node, GuardRewirer rewireGuardFunction) {
                for (InfoElement infoElement : getInfoElements(node)) {
                    Stamp stamp = infoElement.getStamp();
                    JavaConstant constant = (JavaConstant) stamp.asConstant();
                    if (constant != null) {
                        return rewireGuards(infoElement.getGuard(), constant.asBoolean(), rewireGuardFunction);
                    }
                }
                if (node instanceof UnaryOpLogicNode) {
                    UnaryOpLogicNode unaryLogicNode = (UnaryOpLogicNode) node;
                    ValueNode value = unaryLogicNode.getValue();
                    for (InfoElement infoElement : getInfoElements(value)) {
                        Stamp stamp = infoElement.getStamp();
                        TriState result = unaryLogicNode.tryFold(stamp);
                        if (result.isKnown()) {
                            return rewireGuards(infoElement.getGuard(), result.toBoolean(), rewireGuardFunction);
                        }
                    }
                    Pair<InfoElement, Stamp> foldResult = recursiveFoldStampFromInfo(value);
                    if (foldResult != null) {
                        TriState result = unaryLogicNode.tryFold(foldResult.second);
                        if (result.isKnown()) {
                            return rewireGuards(foldResult.first.getGuard(), result.toBoolean(), 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;
                    for (InfoElement infoElement : getInfoElements(binaryOpLogicNode)) {
                        if (infoElement.getStamp().equals(StampFactory.contradiction())) {
                            return rewireGuards(infoElement.getGuard(), false, rewireGuardFunction);
                        } else if (infoElement.getStamp().equals(StampFactory.tautology())) {
                            return rewireGuards(infoElement.getGuard(), true, rewireGuardFunction);
                        }
                    }

                    ValueNode x = binaryOpLogicNode.getX();
                    ValueNode y = binaryOpLogicNode.getY();
                    for (InfoElement infoElement : getInfoElements(x)) {
                        TriState result = binaryOpLogicNode.tryFold(infoElement.getStamp(), y.stamp());
                        if (result.isKnown()) {
                            return rewireGuards(infoElement.getGuard(), result.toBoolean(), rewireGuardFunction);
                        }
                    }

                    if (y.isConstant()) {
                        Pair<InfoElement, Stamp> foldResult = recursiveFoldStampFromInfo(x);
                        if (foldResult != null) {
                            TriState result = binaryOpLogicNode.tryFold(foldResult.second, y.stamp());
                            if (result.isKnown()) {
                                return rewireGuards(foldResult.first.getGuard(), result.toBoolean(), rewireGuardFunction);
                            }
                        }
                    } else {
                        for (InfoElement infoElement : getInfoElements(y)) {
                            TriState result = binaryOpLogicNode.tryFold(x.stamp(), infoElement.getStamp());
                            if (result.isKnown()) {
                                return rewireGuards(infoElement.getGuard(), result.toBoolean(), rewireGuardFunction);
                            }
                        }
                    }

                    /*
                     * 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()) {
                            for (InfoElement infoElement : getInfoElements(binary.getX())) {
                                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(), rewireGuardFunction);
                                }
                            }
                        }
                    }
                    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(and.getX().stamp(), y.stamp());
                                if (foldPendingTest(thisGuard, and.getX(), newStampX, rewireGuardFunction)) {
                                    return true;
                                }
                            }
                        }
                    }
                    if (thisGuard != null) {
                        if (!x.isConstant()) {
                            Stamp newStampX = binaryOpLogicNode.getSucceedingStampForX(thisGuard.isNegated());
                            if (newStampX != null && foldPendingTest(thisGuard, x, newStampX, rewireGuardFunction)) {
                                return true;
                            }
                        }
                        if (!y.isConstant()) {
                            Stamp newStampY = binaryOpLogicNode.getSucceedingStampForY(thisGuard.isNegated());
                            if (newStampY != null && foldPendingTest(thisGuard, y, newStampY, rewireGuardFunction)) {
                                return true;
                            }
                        }
                    }
                } else if (node instanceof ShortCircuitOrNode) {
                    final ShortCircuitOrNode shortCircuitOrNode = (ShortCircuitOrNode) node;
                    if (Instance.this.loopExits.isEmpty()) {
                        return tryProveCondition(shortCircuitOrNode.getX(), (guard, result) -> {
                            if (result == !shortCircuitOrNode.isXNegated()) {
                                return rewireGuards(guard, true, rewireGuardFunction);
                            } else {
                                return tryProveCondition(shortCircuitOrNode.getY(), (innerGuard, innerResult) -> {
                                    if (innerGuard == guard) {
                                        return rewireGuards(guard, innerResult ^ shortCircuitOrNode.isYNegated(), rewireGuardFunction);
                                    }
                                    return false;
                                });
                            }
                        });
                    }
                }

                return false;
            }

            protected void registerNewStamp(ValueNode proxiedValue, Stamp newStamp, ValueNode guard) {
                assert proxiedValue != null;
                assert guard != null;
                if (newStamp != null) {
                    ValueNode value = GraphUtil.unproxify(proxiedValue);
                    Info info = map.get(value);
                    if (info == null) {
                        info = new Info();
                        map.set(value, info);
                    }
                    counterStampsRegistered.increment();
                    final Info finalInfo = info;
                    Debug.log("\t Saving stamp for node %s stamp %s guarded by %s", value, newStamp, guard == null ? "null" : guard);
                    finalInfo.pushElement(new InfoElement(newStamp, guard));
                    undoOperations.add(() -> finalInfo.popElement());
                }
            }

            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, predecessor, typeSwitch);
                } else if (predecessor instanceof IntegerSwitchNode) {
                    IntegerSwitchNode integerSwitchNode = (IntegerSwitchNode) predecessor;
                    processIntegerSwitch(beginNode, predecessor, integerSwitchNode);
                }
            }

            protected void processIntegerSwitch(AbstractBeginNode beginNode, Node predecessor, IntegerSwitchNode integerSwitchNode) {
                Stamp stamp = null;
                for (int i = 0; i < integerSwitchNode.keyCount(); i++) {
                    if (integerSwitchNode.keySuccessor(i) == predecessor) {
                        if (stamp == null) {
                            stamp = StampFactory.forConstant(integerSwitchNode.keyAt(i));
                        } else {
                            stamp = stamp.meet(StampFactory.forConstant(integerSwitchNode.keyAt(i)));
                        }
                    }
                }

                if (stamp != null) {
                    registerNewStamp(integerSwitchNode.value(), stamp, beginNode);
                }
            }

            protected void processTypeSwitch(AbstractBeginNode beginNode, Node predecessor, TypeSwitchNode typeSwitch) {
                ValueNode hub = typeSwitch.value();
                if (hub instanceof LoadHubNode) {
                    LoadHubNode loadHub = (LoadHubNode) hub;
                    Stamp stamp = null;
                    for (int i = 0; i < typeSwitch.keyCount(); i++) {
                        if (typeSwitch.keySuccessor(i) == predecessor) {
                            if (stamp == null) {
                                stamp = StampFactory.objectNonNull(TypeReference.createExactTrusted(typeSwitch.typeAt(i)));
                            } else {
                                stamp = stamp.meet(StampFactory.objectNonNull(TypeReference.createExactTrusted(typeSwitch.typeAt(i))));
                            }
                        }
                    }
                    if (stamp != null) {
                        registerNewStamp(loadHub.getValue(), stamp, beginNode);
                    }
                }
            }
        }
    }

    protected static class Pair<F, S> {
        public final F first;
        public final S second;

        Pair(F first, S second) {
            this.first = first;
            this.second = second;
        }

        @Override
        public int hashCode() {
            return first.hashCode() * 31 ^ second.hashCode();
        }

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof Pair<?, ?>) {
                Pair<?, ?> other = (Pair<?, ?>) obj;
                return this.first.equals(other.first) && this.second.equals(other.second);
            }
            return false;
        }
    }

    @FunctionalInterface
    protected interface InfoElementProvider {
        Iterable<InfoElement> getInfoElements(ValueNode value);
    }

    
Checks for safe nodes when moving pending tests up.
/**
     * 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 (!(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 (result) under guard. Return whether a transformation could be applied. /**
         * Called if the condition could be proven to have a constant value ({@code result}) under
         * {@code guard}.
         *
         * Return whether a transformation could be applied.
         */
        boolean rewire(ValueNode guard, boolean result);
    }

    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 ValueNode guard;

        public InfoElement(Stamp stamp, ValueNode guard) {
            this.stamp = stamp;
            this.guard = guard;
        }

        public Stamp getStamp() {
            return stamp;
        }

        public ValueNode getGuard() {
            return guard;
        }

        @Override
        public String toString() {
            return stamp + " -> " + guard;
        }
    }

    protected static final class Info {
        private final ArrayList<InfoElement> infos;

        public Info() {
            infos = new ArrayList<>();
        }

        public Iterable<InfoElement> getElements() {
            return infos;
        }

        public void pushElement(InfoElement element) {
            Debug.log(Debug.VERBOSE_LOG_LEVEL, "Pushing an info element:%s", element);
            infos.add(element);
        }

        public void popElement() {
            infos.remove(infos.size() - 1);
        }
    }

    private static class GuardedConstantStamp extends ObjectStamp {
        private final JavaConstant objectConstant;

        GuardedConstantStamp(JavaConstant objectConstant, ObjectStamp succeedingStamp) {
            super(succeedingStamp.type(), succeedingStamp.isExactType(), succeedingStamp.nonNull(), succeedingStamp.alwaysNull());
            this.objectConstant = objectConstant;
        }

    }

    @Override
    public float codeSizeIncrease() {
        return 1.5f;
    }
}