/*

 * Copyright (c) 2011, 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.schedule;

import static org.graalvm.compiler.core.common.GraalOptions.OptScheduleOutOfLoops;

import static org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph.strictlyDominates;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Formatter;

import java.util.List;

import org.graalvm.compiler.core.common.SuppressFBWarnings;

import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph;

import org.graalvm.compiler.core.common.cfg.BlockMap;

import org.graalvm.compiler.debug.Assertions;

import org.graalvm.compiler.graph.Graph.NodeEvent;

import org.graalvm.compiler.graph.Graph.NodeEventListener;

import org.graalvm.compiler.graph.Graph.NodeEventScope;

import org.graalvm.compiler.graph.Node;

import org.graalvm.compiler.graph.NodeBitMap;

import org.graalvm.compiler.graph.NodeMap;

import org.graalvm.compiler.graph.NodeStack;

import org.graalvm.compiler.nodes.AbstractBeginNode;

import org.graalvm.compiler.nodes.AbstractEndNode;

import org.graalvm.compiler.nodes.AbstractMergeNode;

import org.graalvm.compiler.nodes.ControlSinkNode;

import org.graalvm.compiler.nodes.ControlSplitNode;

import org.graalvm.compiler.nodes.DeoptimizeNode;

import org.graalvm.compiler.nodes.FixedNode;

import org.graalvm.compiler.nodes.GuardNode;

import org.graalvm.compiler.nodes.IfNode;

import org.graalvm.compiler.nodes.KillingBeginNode;

import org.graalvm.compiler.nodes.LoopBeginNode;

import org.graalvm.compiler.nodes.LoopExitNode;

import org.graalvm.compiler.nodes.PhiNode;

import org.graalvm.compiler.nodes.ProxyNode;

import org.graalvm.compiler.nodes.StartNode;

import org.graalvm.compiler.nodes.StructuredGraph;

import org.graalvm.compiler.nodes.StructuredGraph.GuardsStage;

import org.graalvm.compiler.nodes.StructuredGraph.ScheduleResult;

import org.graalvm.compiler.nodes.ValueNode;

import org.graalvm.compiler.nodes.VirtualState;

import org.graalvm.compiler.nodes.calc.ConvertNode;

import org.graalvm.compiler.nodes.calc.IsNullNode;

import org.graalvm.compiler.nodes.cfg.Block;

import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;

import org.graalvm.compiler.nodes.cfg.HIRLoop;

import org.graalvm.compiler.nodes.cfg.LocationSet;

import org.graalvm.compiler.nodes.memory.FloatingReadNode;

import org.graalvm.compiler.nodes.memory.MemoryCheckpoint;

import org.graalvm.compiler.nodes.spi.ValueProxy;

import org.graalvm.compiler.options.OptionValues;

import org.graalvm.compiler.phases.Phase;

import org.graalvm.word.LocationIdentity;

public final class SchedulePhase extends Phase {

    public enum SchedulingStrategy {

        EARLIEST,

        LATEST,

        LATEST_OUT_OF_LOOPS,

    }

    private final SchedulingStrategy selectedStrategy;

    private final boolean immutableGraph;

    public SchedulePhase(OptionValues options) {

        this(false, options);

    }

    public SchedulePhase(boolean immutableGraph, OptionValues options) {

        this(OptScheduleOutOfLoops.getValue(options) ? SchedulingStrategy.LATEST_OUT_OF_LOOPS : SchedulingStrategy.LATEST, immutableGraph);

    }

    public SchedulePhase(SchedulingStrategy strategy) {

        this(strategy, false);

    }

    public SchedulePhase(SchedulingStrategy strategy, boolean immutableGraph) {

        this.selectedStrategy = strategy;

        this.immutableGraph = immutableGraph;

    }

    private NodeEventScope verifyImmutableGraph(StructuredGraph graph) {

        if (immutableGraph && Assertions.assertionsEnabled()) {

            return graph.trackNodeEvents(new NodeEventListener() {

                @Override

                public void changed(NodeEvent e, Node node) {

                    assert false : "graph changed: " + e + " on node " + node;

                }

            });

        } else {

            return null;

        }

    }

    @Override

    @SuppressWarnings("try")

    protected void run(StructuredGraph graph) {

        try (NodeEventScope scope = verifyImmutableGraph(graph)) {

            Instance inst = new Instance();

            inst.run(graph, selectedStrategy, immutableGraph);

        }

    }

    public static void run(StructuredGraph graph, SchedulingStrategy strategy, ControlFlowGraph cfg) {

        Instance inst = new Instance(cfg);

        inst.run(graph, strategy, false);

    }

    public static class Instance {

        private static final double IMPLICIT_NULL_CHECK_OPPORTUNITY_PROBABILITY_FACTOR = 2;

        /**

         * Map from blocks to the nodes in each block.

         */

        protected ControlFlowGraph cfg;

        protected BlockMap<List<Node>> blockToNodesMap;

        protected NodeMap<Block> nodeToBlockMap;

        public Instance() {

            this(null);

        }

        public Instance(ControlFlowGraph cfg) {

            this.cfg = cfg;

        }

        @SuppressWarnings("try")

        public void run(StructuredGraph graph, SchedulingStrategy selectedStrategy, boolean immutableGraph) {

            // assert GraphOrder.assertNonCyclicGraph(graph);

            if (this.cfg == null) {

                this.cfg = ControlFlowGraph.compute(graph, true, true, true, false);

            }

            NodeMap<Block> currentNodeMap = graph.createNodeMap();

            NodeBitMap visited = graph.createNodeBitMap();

            BlockMap<List<Node>> earliestBlockToNodesMap = new BlockMap<>(cfg);

            this.nodeToBlockMap = currentNodeMap;

            this.blockToNodesMap = earliestBlockToNodesMap;

                // For non-earliest schedules, we need to do a second pass.

                BlockMap<List<Node>> latestBlockToNodesMap = new BlockMap<>(cfg);

                for (Block b : cfg.getBlocks()) {

                }

                BlockMap<ArrayList<FloatingReadNode>> watchListMap = calcLatestBlocks(selectedStrategy, currentNodeMap, earliestBlockToNodesMap, visited, latestBlockToNodesMap, immutableGraph);

                sortNodesLatestWithinBlock(cfg, earliestBlockToNodesMap, latestBlockToNodesMap, currentNodeMap, watchListMap, visited);

                assert verifySchedule(cfg, latestBlockToNodesMap, currentNodeMap);

                assert (!Assertions.detailedAssertionsEnabled(graph.getOptions())) || MemoryScheduleVerification.check(cfg.getStartBlock(), latestBlockToNodesMap);

                this.blockToNodesMap = latestBlockToNodesMap;

            }

            graph.setLastSchedule(new ScheduleResult(this.cfg, this.nodeToBlockMap, this.blockToNodesMap));

        }

        @SuppressFBWarnings(value = "RCN_REDUNDANT_NULLCHECK_WOULD_HAVE_BEEN_A_NPE", justification = "false positive found by findbugs")

        private BlockMap<ArrayList<FloatingReadNode>> calcLatestBlocks(SchedulingStrategy strategy, NodeMap<Block> currentNodeMap, BlockMap<List<Node>> earliestBlockToNodesMap, NodeBitMap visited,

                        BlockMap<List<Node>> latestBlockToNodesMap, boolean immutableGraph) {

            BlockMap<ArrayList<FloatingReadNode>> watchListMap = new BlockMap<>(cfg);

            Block[] reversePostOrder = cfg.reversePostOrder();

            for (int j = reversePostOrder.length - 1; j >= 0; --j) {

                Block currentBlock = reversePostOrder[j];

                List<Node> blockToNodes = earliestBlockToNodesMap.get(currentBlock);

                LocationSet killed = null;

                int previousIndex = blockToNodes.size();

                for (int i = blockToNodes.size() - 1; i >= 0; --i) {

                    Node currentNode = blockToNodes.get(i);

                    assert currentNodeMap.get(currentNode) == currentBlock;

                    assert !(currentNode instanceof PhiNode) && !(currentNode instanceof ProxyNode);

                    assert visited.isMarked(currentNode);

                    if (currentNode instanceof FixedNode) {

                        // For these nodes, the earliest is at the same time the latest block.

                    } else {

                        Block latestBlock = null;

                        LocationIdentity constrainingLocation = null;

                        if (currentNode instanceof FloatingReadNode) {

                            // We are scheduling a floating read node => check memory

                            // anti-dependencies.

                            FloatingReadNode floatingReadNode = (FloatingReadNode) currentNode;

                            LocationIdentity location = floatingReadNode.getLocationIdentity();

                            if (location.isMutable()) {

                                // Location can be killed.

                                constrainingLocation = location;

                                if (currentBlock.canKill(location)) {

                                    if (killed == null) {

                                        killed = new LocationSet();

                                    }

                                    fillKillSet(killed, blockToNodes.subList(i + 1, previousIndex));

                                    previousIndex = i;

                                    if (killed.contains(location)) {

                                        // Earliest block kills location => we need to stay within

                                        // earliest block.

                                        latestBlock = currentBlock;

                                    }

                                }

                            }

                        }

                        if (latestBlock == null) {

                            // We are not constraint within earliest block => calculate optimized

                            // schedule.

                            calcLatestBlock(currentBlock, strategy, currentNode, currentNodeMap, constrainingLocation, watchListMap, latestBlockToNodesMap, visited, immutableGraph);

                        } else {

                            selectLatestBlock(currentNode, currentBlock, latestBlock, currentNodeMap, watchListMap, constrainingLocation, latestBlockToNodesMap);

                        }

                    }

                }

            }

            return watchListMap;

        }

        protected static void selectLatestBlock(Node currentNode, Block currentBlock, Block latestBlock, NodeMap<Block> currentNodeMap, BlockMap<ArrayList<FloatingReadNode>> watchListMap,

                        LocationIdentity constrainingLocation, BlockMap<List<Node>> latestBlockToNodesMap) {

            assert checkLatestEarliestRelation(currentNode, currentBlock, latestBlock);

            if (currentBlock != latestBlock) {

                currentNodeMap.setAndGrow(currentNode, latestBlock);

                if (constrainingLocation != null && latestBlock.canKill(constrainingLocation)) {

                    if (watchListMap.get(latestBlock) == null) {

                        watchListMap.put(latestBlock, new ArrayList<>());

                    }

                    watchListMap.get(latestBlock).add((FloatingReadNode) currentNode);

                }

            }

            latestBlockToNodesMap.get(latestBlock).add(currentNode);

        }

        private static boolean checkLatestEarliestRelation(Node currentNode, Block earliestBlock, Block latestBlock) {

            assert AbstractControlFlowGraph.dominates(earliestBlock, latestBlock) || (currentNode instanceof VirtualState && latestBlock == earliestBlock.getDominator()) : String.format(

                            "%s %s (%s) %s (%s)", currentNode, earliestBlock, earliestBlock.getBeginNode(), latestBlock, latestBlock.getBeginNode());

            return true;

        }

        private static boolean verifySchedule(ControlFlowGraph cfg, BlockMap<List<Node>> blockToNodesMap, NodeMap<Block> nodeMap) {

            for (Block b : cfg.getBlocks()) {

                List<Node> nodes = blockToNodesMap.get(b);

                for (Node n : nodes) {

                    assert n.isAlive();

                    assert nodeMap.get(n) == b;

                    StructuredGraph g = (StructuredGraph) n.graph();

                    if (g.hasLoops() && g.getGuardsStage() == GuardsStage.AFTER_FSA && n instanceof DeoptimizeNode) {

                        assert b.getLoopDepth() == 0 : n;

                    }

                }

            }

            return true;

        }

        public static Block checkKillsBetween(Block earliestBlock, Block latestBlock, LocationIdentity location) {

            assert strictlyDominates(earliestBlock, latestBlock);

            Block current = latestBlock.getDominator();

            // Collect dominator chain that needs checking.

            List<Block> dominatorChain = new ArrayList<>();

            dominatorChain.add(latestBlock);

            while (current != earliestBlock) {

                // Current is an intermediate dominator between earliestBlock and latestBlock.

                assert strictlyDominates(earliestBlock, current) && strictlyDominates(current, latestBlock);

                if (current.canKill(location)) {

                    dominatorChain.clear();

                }

                dominatorChain.add(current);

                current = current.getDominator();

            }

            // The first element of dominatorChain now contains the latest possible block.

            assert dominatorChain.size() >= 1;

            assert dominatorChain.get(dominatorChain.size() - 1).getDominator() == earliestBlock;

            Block lastBlock = earliestBlock;

            for (int i = dominatorChain.size() - 1; i >= 0; --i) {

                Block currentBlock = dominatorChain.get(i);

                if (currentBlock.getLoopDepth() > lastBlock.getLoopDepth()) {

                    // We are entering a loop boundary. The new loops must not kill the location for

                    // the crossing to be safe.

                    if (currentBlock.getLoop() != null && ((HIRLoop) currentBlock.getLoop()).canKill(location)) {

                        break;

                    }

                }

                if (currentBlock.canKillBetweenThisAndDominator(location)) {

                    break;

                }

                lastBlock = currentBlock;

            }

            if (lastBlock.getBeginNode() instanceof KillingBeginNode) {

                LocationIdentity locationIdentity = ((KillingBeginNode) lastBlock.getBeginNode()).getLocationIdentity();

                if ((locationIdentity.isAny() || locationIdentity.equals(location)) && lastBlock != earliestBlock) {

                    // The begin of this block kills the location, so we *have* to schedule the node

                    // in the dominating block.

                    lastBlock = lastBlock.getDominator();

                }

            }

            return lastBlock;

        }

        private static void fillKillSet(LocationSet killed, List<Node> subList) {

            if (!killed.isAny()) {

                for (Node n : subList) {

                    // Check if this node kills a node in the watch list.

                    if (n instanceof MemoryCheckpoint.Single) {

                        LocationIdentity identity = ((MemoryCheckpoint.Single) n).getLocationIdentity();

                        killed.add(identity);

                        if (killed.isAny()) {

                            return;

                        }

                    } else if (n instanceof MemoryCheckpoint.Multi) {

                        for (LocationIdentity identity : ((MemoryCheckpoint.Multi) n).getLocationIdentities()) {

                            killed.add(identity);

                            if (killed.isAny()) {

                                return;

                            }

                        }

                    }

                }

            }

        }

        private static void sortNodesLatestWithinBlock(ControlFlowGraph cfg, BlockMap<List<Node>> earliestBlockToNodesMap, BlockMap<List<Node>> latestBlockToNodesMap, NodeMap<Block> currentNodeMap,

                        BlockMap<ArrayList<FloatingReadNode>> watchListMap, NodeBitMap visited) {

            for (Block b : cfg.getBlocks()) {

                sortNodesLatestWithinBlock(b, earliestBlockToNodesMap, latestBlockToNodesMap, currentNodeMap, watchListMap, visited);

            }

        }

        private static void sortNodesLatestWithinBlock(Block b, BlockMap<List<Node>> earliestBlockToNodesMap, BlockMap<List<Node>> latestBlockToNodesMap, NodeMap<Block> nodeMap,

                        BlockMap<ArrayList<FloatingReadNode>> watchListMap, NodeBitMap unprocessed) {

            List<Node> earliestSorting = earliestBlockToNodesMap.get(b);

            ArrayList<Node> result = new ArrayList<>(earliestSorting.size());

            ArrayList<FloatingReadNode> watchList = null;

            if (watchListMap != null) {

                watchList = watchListMap.get(b);

                assert watchList == null || !b.getKillLocations().isEmpty();

            }

            AbstractBeginNode beginNode = b.getBeginNode();

            if (beginNode instanceof LoopExitNode) {

                LoopExitNode loopExitNode = (LoopExitNode) beginNode;

                for (ProxyNode proxy : loopExitNode.proxies()) {

                    unprocessed.clear(proxy);

                    ValueNode value = proxy.value();

                    // if multiple proxies reference the same value, schedule the value of a

                    // proxy once

                    if (value != null && nodeMap.get(value) == b && unprocessed.isMarked(value)) {

                        sortIntoList(value, b, result, nodeMap, unprocessed, null);

                    }

                }

            }

            FixedNode endNode = b.getEndNode();

            FixedNode fixedEndNode = null;

            if (isFixedEnd(endNode)) {

                // Only if the end node is either a control split or an end node, we need to force

                // it to be the last node in the schedule.

                fixedEndNode = endNode;

            }

            for (Node n : earliestSorting) {

                if (n != fixedEndNode) {

                    if (n instanceof FixedNode) {

                        assert nodeMap.get(n) == b;

                        checkWatchList(b, nodeMap, unprocessed, result, watchList, n);

                        sortIntoList(n, b, result, nodeMap, unprocessed, null);

                    } else if (nodeMap.get(n) == b && n instanceof FloatingReadNode) {

                        FloatingReadNode floatingReadNode = (FloatingReadNode) n;

                        if (isImplicitNullOpportunity(floatingReadNode, b)) {

                            // Schedule at the beginning of the block.

                            sortIntoList(floatingReadNode, b, result, nodeMap, unprocessed, null);

                        } else {

                            LocationIdentity location = floatingReadNode.getLocationIdentity();

                            if (b.canKill(location)) {

                                // This read can be killed in this block, add to watch list.

                                if (watchList == null) {

                                    watchList = new ArrayList<>();

                                }

                                watchList.add(floatingReadNode);

                            }

                        }

                    }

                }

            }

            for (Node n : latestBlockToNodesMap.get(b)) {

                assert nodeMap.get(n) == b : n;

                assert !(n instanceof FixedNode);

                if (unprocessed.isMarked(n)) {

                    sortIntoList(n, b, result, nodeMap, unprocessed, fixedEndNode);

                }

            }

            if (endNode != null && unprocessed.isMarked(endNode)) {

                sortIntoList(endNode, b, result, nodeMap, unprocessed, null);

            }

            latestBlockToNodesMap.put(b, result);

        }

        private static void checkWatchList(Block b, NodeMap<Block> nodeMap, NodeBitMap unprocessed, ArrayList<Node> result, ArrayList<FloatingReadNode> watchList, Node n) {

            if (watchList != null && !watchList.isEmpty()) {

                // Check if this node kills a node in the watch list.

                if (n instanceof MemoryCheckpoint.Single) {

                    LocationIdentity identity = ((MemoryCheckpoint.Single) n).getLocationIdentity();

                    checkWatchList(watchList, identity, b, result, nodeMap, unprocessed);

                } else if (n instanceof MemoryCheckpoint.Multi) {

                    for (LocationIdentity identity : ((MemoryCheckpoint.Multi) n).getLocationIdentities()) {

                        checkWatchList(watchList, identity, b, result, nodeMap, unprocessed);

                    }

                }

            }

        }

        private static void checkWatchList(ArrayList<FloatingReadNode> watchList, LocationIdentity identity, Block b, ArrayList<Node> result, NodeMap<Block> nodeMap, NodeBitMap unprocessed) {

            if (identity.isImmutable()) {

                // Nothing to do. This can happen for an initialization write.

            } else if (identity.isAny()) {

                for (FloatingReadNode r : watchList) {

                    if (unprocessed.isMarked(r)) {

                        sortIntoList(r, b, result, nodeMap, unprocessed, null);

                    }

                }

                watchList.clear();

            } else {

                int index = 0;

                while (index < watchList.size()) {

                    FloatingReadNode r = watchList.get(index);

                    LocationIdentity locationIdentity = r.getLocationIdentity();

                    assert locationIdentity.isMutable();

                    if (unprocessed.isMarked(r)) {

                        if (identity.overlaps(locationIdentity)) {

                            sortIntoList(r, b, result, nodeMap, unprocessed, null);

                        } else {

                            ++index;

                            continue;

                        }

                    }

                    int lastIndex = watchList.size() - 1;

                    watchList.set(index, watchList.get(lastIndex));

                    watchList.remove(lastIndex);

                }

            }

        }

        private static void sortIntoList(Node n, Block b, ArrayList<Node> result, NodeMap<Block> nodeMap, NodeBitMap unprocessed, Node excludeNode) {

            assert unprocessed.isMarked(n) : n;

            assert nodeMap.get(n) == b;

            if (n instanceof PhiNode) {

                return;

            }

            unprocessed.clear(n);

            for (Node input : n.inputs()) {

                if (nodeMap.get(input) == b && unprocessed.isMarked(input) && input != excludeNode) {

                    sortIntoList(input, b, result, nodeMap, unprocessed, excludeNode);

                }

            }

            if (n instanceof ProxyNode) {

                // Skip proxy nodes.

            } else {

                result.add(n);