/*

 * 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);