/*
 * 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 jdk.internal.vm.compiler.collections.Equivalence.IDENTITY;
import static org.graalvm.compiler.core.common.GraalOptions.GuardPriorities;
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.Comparator;
import java.util.EnumMap;
import java.util.Formatter;
import java.util.Iterator;
import java.util.List;
import java.util.SortedSet;
import java.util.TreeSet;
import java.util.function.Function;

import jdk.internal.vm.compiler.collections.EconomicSet;
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.StaticDeoptimizingNode;
import org.graalvm.compiler.nodes.StaticDeoptimizingNode.GuardPriority;
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 jdk.internal.vm.compiler.word.LocationIdentity;

public final class SchedulePhase extends Phase {

    public enum SchedulingStrategy {
        EARLIEST_WITH_GUARD_ORDER,
        EARLIEST,
        LATEST,
        LATEST_OUT_OF_LOOPS,
        FINAL_SCHEDULE;

        public boolean isEarliest() {
            return this == EARLIEST || this == EARLIEST_WITH_GUARD_ORDER;
        }

        public boolean isLatest() {
            return !isEarliest();
        }
    }

    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.
/**
         * 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;

            scheduleEarliestIterative(earliestBlockToNodesMap, currentNodeMap, visited, graph, immutableGraph, selectedStrategy == SchedulingStrategy.EARLIEST_WITH_GUARD_ORDER);

            if (!selectedStrategy.isEarliest()) {
                // For non-earliest schedules, we need to do a second pass.
                BlockMap<List<Node>> latestBlockToNodesMap = new BlockMap<>(cfg);
                for (Block b : cfg.getBlocks()) {
                    latestBlockToNodesMap.put(b, new ArrayList<>());
                }

                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;

            }
            cfg.setNodeToBlock(currentNodeMap);

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

        }

        protected void calcLatestBlock(Block earliestBlock, SchedulingStrategy strategy, Node currentNode, NodeMap<Block> currentNodeMap, LocationIdentity constrainingLocation,
                        BlockMap<ArrayList<FloatingReadNode>> watchListMap, BlockMap<List<Node>> latestBlockToNodesMap, NodeBitMap visited, boolean immutableGraph) {
            Block latestBlock = null;
            if (!currentNode.hasUsages()) {
                assert currentNode instanceof GuardNode;
                latestBlock = earliestBlock;
            } else {
                assert currentNode.hasUsages();
                for (Node usage : currentNode.usages()) {
                    if (immutableGraph && !visited.contains(usage)) {
                        /*
                         * Normally, dead nodes are deleted by the scheduler before we reach this
                         * point. Only when the scheduler is asked to not modify a graph, we can see
                         * dead nodes here.
                         */
                        continue;
                    }
                    latestBlock = calcBlockForUsage(currentNode, usage, latestBlock, currentNodeMap);
                }

                assert latestBlock != null : currentNode;

                if (strategy == SchedulingStrategy.FINAL_SCHEDULE || strategy == SchedulingStrategy.LATEST_OUT_OF_LOOPS) {
                    Block currentBlock = latestBlock;
                    while (currentBlock.getLoopDepth() > earliestBlock.getLoopDepth() && currentBlock != earliestBlock.getDominator()) {
                        Block previousCurrentBlock = currentBlock;
                        currentBlock = currentBlock.getDominator();
                        if (previousCurrentBlock.isLoopHeader()) {
                            if (currentBlock.probability() < latestBlock.probability() || ((StructuredGraph) currentNode.graph()).hasValueProxies()) {
                                // Only assign new latest block if frequency is actually lower or if
                                // loop proxies would be required otherwise.
                                latestBlock = currentBlock;
                            }
                        }
                    }
                }

                if (latestBlock != earliestBlock && latestBlock != earliestBlock.getDominator() && constrainingLocation != null) {
                    latestBlock = checkKillsBetween(earliestBlock, latestBlock, constrainingLocation);
                }
            }

            if (latestBlock != earliestBlock && currentNode instanceof FloatingReadNode) {

                FloatingReadNode floatingReadNode = (FloatingReadNode) currentNode;
                if (isImplicitNullOpportunity(floatingReadNode, earliestBlock) && earliestBlock.probability() < latestBlock.probability() * IMPLICIT_NULL_CHECK_OPPORTUNITY_PROBABILITY_FACTOR) {
                    latestBlock = earliestBlock;
                }
            }

            selectLatestBlock(currentNode, earliestBlock, latestBlock, currentNodeMap, watchListMap, constrainingLocation, latestBlockToNodesMap);
        }

        private static boolean isImplicitNullOpportunity(FloatingReadNode floatingReadNode, Block block) {

            Node pred = block.getBeginNode().predecessor();
            if (pred instanceof IfNode) {
                IfNode ifNode = (IfNode) pred;
                if (ifNode.condition() instanceof IsNullNode) {
                    IsNullNode isNullNode = (IsNullNode) ifNode.condition();
                    if (getUnproxifiedUncompressed(floatingReadNode.getAddress().getBase()) == getUnproxifiedUncompressed(isNullNode.getValue())) {
                        return true;
                    }
                }
            }
            return false;
        }

        private static Node getUnproxifiedUncompressed(Node node) {
            Node result = node;
            while (true) {
                if (result instanceof ValueProxy) {
                    ValueProxy valueProxy = (ValueProxy) result;
                    result = valueProxy.getOriginalNode();
                } else if (result instanceof ConvertNode) {
                    ConvertNode convertNode = (ConvertNode) result;
                    if (convertNode.mayNullCheckSkipConversion()) {
                        result = convertNode.getValue();
                    } else {
                        break;
                    }
                } else {
                    break;
                }
            }
            return result;
        }

        private static Block calcBlockForUsage(Node node, Node usage, Block startBlock, NodeMap<Block> currentNodeMap) {
            assert !(node instanceof PhiNode);
            Block currentBlock = startBlock;
            if (usage instanceof PhiNode) {
                // An input to a PhiNode is used at the end of the predecessor block that
                // corresponds to the PhiNode input. One PhiNode can use an input multiple times.
                PhiNode phi = (PhiNode) usage;
                AbstractMergeNode merge = phi.merge();
                Block mergeBlock = currentNodeMap.get(merge);
                for (int i = 0; i < phi.valueCount(); ++i) {
                    if (phi.valueAt(i) == node) {
                        Block otherBlock = mergeBlock.getPredecessors()[i];
                        currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, otherBlock);
                    }
                }
            } else if (usage instanceof AbstractBeginNode) {
                AbstractBeginNode abstractBeginNode = (AbstractBeginNode) usage;
                if (abstractBeginNode instanceof StartNode) {
                    currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, currentNodeMap.get(abstractBeginNode));
                } else {
                    Block otherBlock = currentNodeMap.get(abstractBeginNode).getDominator();
                    currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, otherBlock);
                }
            } else {
                // All other types of usages: Put the input into the same block as the usage.
                Block otherBlock = currentNodeMap.get(usage);
                if (usage instanceof ProxyNode) {
                    ProxyNode proxyNode = (ProxyNode) usage;
                    otherBlock = currentNodeMap.get(proxyNode.proxyPoint());

                }
                currentBlock = AbstractControlFlowGraph.commonDominatorTyped(currentBlock, otherBlock);
            }
            return currentBlock;
        }

        
Micro block that is allocated for each fixed node and captures all floating nodes that
need to be scheduled immediately after the corresponding fixed node.
/**
         * Micro block that is allocated for each fixed node and captures all floating nodes that
         * need to be scheduled immediately after the corresponding fixed node.
         */
        private static class MicroBlock {
            private final int id;
            private int nodeCount;
            private NodeEntry head;
            private NodeEntry tail;

            MicroBlock(int id) {
                this.id = id;
            }

            
Adds a new floating node into the micro block.
/**
             * Adds a new floating node into the micro block.
             */
            public void add(Node node) {
                assert !(node instanceof FixedNode) : node;
                NodeEntry newTail = new NodeEntry(node);
                if (tail == null) {
                    tail = head = newTail;
                } else {
                    tail.next = newTail;
                    tail = newTail;
                }
                nodeCount++;
            }

            
Number of nodes in this micro block.
/**
             * Number of nodes in this micro block.
             */
            public int getNodeCount() {
                assert getActualNodeCount() == nodeCount : getActualNodeCount() + " != " + nodeCount;
                return nodeCount;
            }

            private int getActualNodeCount() {
                int count = 0;
                for (NodeEntry e = head; e != null; e = e.next) {
                    count++;
                }
                return count;
            }

            
The id of the micro block, with a block always associated with a lower id than its
successors.
/**
             * The id of the micro block, with a block always associated with a lower id than its
             * successors.
             */
            public int getId() {
                return id;
            }

            
First node of the linked list of nodes of this micro block.
/**
             * First node of the linked list of nodes of this micro block.
             */
            public NodeEntry getFirstNode() {
                return head;
            }

            
Takes all nodes in this micro blocks and prepends them to the nodes of the given
parameter.
Params:
newBlock – the new block for the nodes/**
             * Takes all nodes in this micro blocks and prepends them to the nodes of the given
             * parameter.
             *
             * @param newBlock the new block for the nodes
             */
            public void prependChildrenTo(MicroBlock newBlock) {
                if (tail != null) {
                    assert head != null;
                    tail.next = newBlock.head;
                    newBlock.head = head;
                    head = tail = null;
                    newBlock.nodeCount += nodeCount;
                    nodeCount = 0;
                }
            }

            @Override
            public String toString() {
                return String.format("MicroBlock[id=%d]", id);
            }

            @Override
            public int hashCode() {
                return id;
            }
        }

        
Entry in the linked list of nodes.
/**
         * Entry in the linked list of nodes.
         */
        private static class NodeEntry {
            private final Node node;
            private NodeEntry next;

            NodeEntry(Node node) {
                this.node = node;
                this.next = null;
            }

            public NodeEntry getNext() {
                return next;
            }

            public Node getNode() {
                return node;
            }
        }

        private void scheduleEarliestIterative(BlockMap<List<Node>> blockToNodes, NodeMap<Block> nodeToBlock, NodeBitMap visited, StructuredGraph graph, boolean immutableGraph,
                        boolean withGuardOrder) {

            NodeMap<MicroBlock> entries = graph.createNodeMap();
            NodeStack stack = new NodeStack();

            // Initialize with fixed nodes.
            MicroBlock startBlock = null;
            int nextId = 1;
            for (Block b : cfg.reversePostOrder()) {
                for (FixedNode current : b.getBeginNode().getBlockNodes()) {
                    MicroBlock microBlock = new MicroBlock(nextId++);
                    entries.set(current, microBlock);
                    boolean isNew = visited.checkAndMarkInc(current);
                    assert isNew;
                    if (startBlock == null) {
                        startBlock = microBlock;
                    }
                }
            }

            if (graph.getGuardsStage().allowsFloatingGuards() && graph.getNodes(GuardNode.TYPE).isNotEmpty()) {
                // Now process guards.
                if (GuardPriorities.getValue(graph.getOptions()) && withGuardOrder) {
                    EnumMap<GuardPriority, List<GuardNode>> guardsByPriority = new EnumMap<>(GuardPriority.class);
                    for (GuardNode guard : graph.getNodes(GuardNode.TYPE)) {
                        guardsByPriority.computeIfAbsent(guard.computePriority(), p -> new ArrayList<>()).add(guard);
                    }
                    // `EnumMap.values` returns values in "natural" key order
                    for (List<GuardNode> guards : guardsByPriority.values()) {
                        processNodes(visited, entries, stack, startBlock, guards);
                    }
                    GuardOrder.resortGuards(graph, entries, stack);
                } else {
                    processNodes(visited, entries, stack, startBlock, graph.getNodes(GuardNode.TYPE));
                }
            } else {
                assert graph.getNodes(GuardNode.TYPE).isEmpty();
            }

            // Now process inputs of fixed nodes.
            for (Block b : cfg.reversePostOrder()) {
                for (FixedNode current : b.getBeginNode().getBlockNodes()) {
                    processNodes(visited, entries, stack, startBlock, current.inputs());
                }
            }

            if (visited.getCounter() < graph.getNodeCount()) {
                // Visit back input edges of loop phis.
                boolean changed;
                boolean unmarkedPhi;
                do {
                    changed = false;
                    unmarkedPhi = false;
                    for (LoopBeginNode loopBegin : graph.getNodes(LoopBeginNode.TYPE)) {
                        for (PhiNode phi : loopBegin.phis()) {
                            if (visited.isMarked(phi)) {
                                for (int i = 0; i < loopBegin.getLoopEndCount(); ++i) {
                                    Node node = phi.valueAt(i + loopBegin.forwardEndCount());
                                    if (node != null && entries.get(node) == null) {
                                        changed = true;
                                        processStack(node, startBlock, entries, visited, stack);
                                    }
                                }
                            } else {
                                unmarkedPhi = true;
                            }
                        }
                    }

                    /*
                     * the processing of one loop phi could have marked a previously checked loop
                     * phi, therefore this needs to be iterative.
                     */
                } while (unmarkedPhi && changed);
            }

            // Check for dead nodes.
            if (!immutableGraph && visited.getCounter() < graph.getNodeCount()) {
                for (Node n : graph.getNodes()) {
                    if (!visited.isMarked(n)) {
                        n.clearInputs();
                        n.markDeleted();
                    }
                }
            }

            for (Block b : cfg.reversePostOrder()) {
                FixedNode fixedNode = b.getEndNode();
                if (fixedNode instanceof ControlSplitNode) {
                    ControlSplitNode controlSplitNode = (ControlSplitNode) fixedNode;
                    MicroBlock endBlock = entries.get(fixedNode);
                    AbstractBeginNode primarySuccessor = controlSplitNode.getPrimarySuccessor();
                    if (primarySuccessor != null) {
                        endBlock.prependChildrenTo(entries.get(primarySuccessor));
                    } else {
                        assert endBlock.tail == null;
                    }
                }
            }

            // Create lists for each block
            for (Block b : cfg.reversePostOrder()) {
                // Count nodes in block
                int totalCount = 0;
                for (FixedNode current : b.getBeginNode().getBlockNodes()) {
                    MicroBlock microBlock = entries.get(current);
                    totalCount += microBlock.getNodeCount() + 1;
                }

                // Initialize with begin node, it is always the first node.
                ArrayList<Node> nodes = new ArrayList<>(totalCount);
                blockToNodes.put(b, nodes);

                for (FixedNode current : b.getBeginNode().getBlockNodes()) {
                    MicroBlock microBlock = entries.get(current);
                    nodeToBlock.set(current, b);
                    nodes.add(current);
                    NodeEntry next = microBlock.getFirstNode();
                    while (next != null) {
                        Node nextNode = next.getNode();
                        nodeToBlock.set(nextNode, b);
                        nodes.add(nextNode);
                        next = next.getNext();
                    }
                }
            }

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

        private static void processNodes(NodeBitMap visited, NodeMap<MicroBlock> entries, NodeStack stack, MicroBlock startBlock, Iterable<? extends Node> nodes) {
            for (Node node : nodes) {
                if (entries.get(node) == null) {
                    processStack(node, startBlock, entries, visited, stack);
                }
            }
        }

        private static void processStackPhi(NodeStack stack, PhiNode phiNode, NodeMap<MicroBlock> nodeToBlock, NodeBitMap visited) {
            stack.pop();
            if (visited.checkAndMarkInc(phiNode)) {
                MicroBlock mergeBlock = nodeToBlock.get(phiNode.merge());
                assert mergeBlock != null : phiNode;
                nodeToBlock.set(phiNode, mergeBlock);
                AbstractMergeNode merge = phiNode.merge();
                for (int i = 0; i < merge.forwardEndCount(); ++i) {
                    Node input = phiNode.valueAt(i);
                    if (input != null && nodeToBlock.get(input) == null) {
                        stack.push(input);
                    }
                }
            }
        }

        private static void processStackProxy(NodeStack stack, ProxyNode proxyNode, NodeMap<MicroBlock> nodeToBlock, NodeBitMap visited) {
            stack.pop();
            if (visited.checkAndMarkInc(proxyNode)) {
                nodeToBlock.set(proxyNode, nodeToBlock.get(proxyNode.proxyPoint()));
                Node input = proxyNode.value();
                if (input != null && nodeToBlock.get(input) == null) {
                    stack.push(input);
                }
            }
        }

        private static void processStack(Node first, MicroBlock startBlock, NodeMap<MicroBlock> nodeToMicroBlock, NodeBitMap visited, NodeStack stack) {
            assert stack.isEmpty();
            assert !visited.isMarked(first);
            stack.push(first);
            Node current = first;
            while (true) {
                if (current instanceof PhiNode) {
                    processStackPhi(stack, (PhiNode) current, nodeToMicroBlock, visited);
                } else if (current instanceof ProxyNode) {
                    processStackProxy(stack, (ProxyNode) current, nodeToMicroBlock, visited);
                } else {
                    MicroBlock currentBlock = nodeToMicroBlock.get(current);
                    if (currentBlock == null) {
                        MicroBlock earliestBlock = processInputs(nodeToMicroBlock, stack, startBlock, current);
                        if (earliestBlock == null) {
                            // We need to delay until inputs are processed.
                        } else {
                            // Can immediately process and pop.
                            stack.pop();
                            visited.checkAndMarkInc(current);
                            nodeToMicroBlock.set(current, earliestBlock);
                            earliestBlock.add(current);
                        }
                    } else {
                        stack.pop();
                    }
                }

                if (stack.isEmpty()) {
                    break;
                }
                current = stack.peek();
            }
        }

        private static class GuardOrder {
            
After an earliest schedule, this will re-sort guards to honor their priority. Note that this only changes the order of nodes within 
micro-blocks, nodes will not be moved from one micro-block to another. /**
             * After an earliest schedule, this will re-sort guards to honor their
             * {@linkplain StaticDeoptimizingNode#computePriority() priority}.
             *
             * Note that this only changes the order of nodes within {@linkplain MicroBlock
             * micro-blocks}, nodes will not be moved from one micro-block to another.
             */
            private static void resortGuards(StructuredGraph graph, NodeMap<MicroBlock> entries, NodeStack stack) {
                assert stack.isEmpty();
                EconomicSet<MicroBlock> blocksWithGuards = EconomicSet.create(IDENTITY);
                for (GuardNode guard : graph.getNodes(GuardNode.TYPE)) {
                    MicroBlock block = entries.get(guard);
                    assert block != null : guard + "should already be scheduled to a micro-block";
                    blocksWithGuards.add(block);
                }
                assert !blocksWithGuards.isEmpty();
                NodeMap<GuardPriority> priorities = graph.createNodeMap();
                NodeBitMap blockNodes = graph.createNodeBitMap();
                for (MicroBlock block : blocksWithGuards) {
                    MicroBlock newBlock = resortGuards(block, stack, blockNodes, priorities);
                    assert stack.isEmpty();
                    assert blockNodes.isEmpty();
                    if (newBlock != null) {
                        assert block.getNodeCount() == newBlock.getNodeCount();
                        block.head = newBlock.head;
                        block.tail = newBlock.tail;
                    }
                }
            }

            
This resorts guards within one micro-block. stack, blockNodes and priorities are just temporary data-structures which are allocated once by the callers of this method. They should be in their "initial"/"empty" state when calling this method and when it returns. /**
             * This resorts guards within one micro-block.
             *
             * {@code stack}, {@code blockNodes} and {@code priorities} are just temporary
             * data-structures which are allocated once by the callers of this method. They should
             * be in their "initial"/"empty" state when calling this method and when it returns.
             */
            private static MicroBlock resortGuards(MicroBlock block, NodeStack stack, NodeBitMap blockNodes, NodeMap<GuardPriority> priorities) {
                if (!propagatePriority(block, stack, priorities, blockNodes)) {
                    return null;
                }

                Function<GuardNode, GuardPriority> transitiveGuardPriorityGetter = priorities::get;
                Comparator<GuardNode> globalGuardPriorityComparator = Comparator.comparing(transitiveGuardPriorityGetter).thenComparing(GuardNode::computePriority).thenComparingInt(Node::hashCode);

                SortedSet<GuardNode> availableGuards = new TreeSet<>(globalGuardPriorityComparator);
                MicroBlock newBlock = new MicroBlock(block.getId());

                NodeBitMap sorted = blockNodes;
                sorted.invert();

                for (NodeEntry e = block.head; e != null; e = e.next) {
                    checkIfAvailable(e.node, stack, sorted, newBlock, availableGuards, false);
                }
                do {
                    while (!stack.isEmpty()) {
                        checkIfAvailable(stack.pop(), stack, sorted, newBlock, availableGuards, true);
                    }
                    Iterator<GuardNode> iterator = availableGuards.iterator();
                    if (iterator.hasNext()) {
                        addNodeToResort(iterator.next(), stack, sorted, newBlock, true);
                        iterator.remove();
                    }
                } while (!stack.isEmpty() || !availableGuards.isEmpty());

                blockNodes.clearAll();
                return newBlock;
            }

            
This checks if n can be scheduled, if it is the case, it schedules it now by calling addNodeToResort(Node, NodeStack, NodeBitMap, MicroBlock, boolean). /**
             * This checks if {@code n} can be scheduled, if it is the case, it schedules it now by
             * calling {@link #addNodeToResort(Node, NodeStack, NodeBitMap, MicroBlock, boolean)}.
             */
            private static void checkIfAvailable(Node n, NodeStack stack, NodeBitMap sorted, Instance.MicroBlock newBlock, SortedSet<GuardNode> availableGuardNodes, boolean pushUsages) {
                if (sorted.isMarked(n)) {
                    return;
                }
                for (Node in : n.inputs()) {
                    if (!sorted.isMarked(in)) {
                        return;
                    }
                }
                if (n instanceof GuardNode) {
                    availableGuardNodes.add((GuardNode) n);
                } else {
                    addNodeToResort(n, stack, sorted, newBlock, pushUsages);
                }
            }

            
Add a node to the re-sorted micro-block. This also pushes nodes that need to be
(re-)examined on the stack.
/**
             * Add a node to the re-sorted micro-block. This also pushes nodes that need to be
             * (re-)examined on the stack.
             */
            private static void addNodeToResort(Node n, NodeStack stack, NodeBitMap sorted, MicroBlock newBlock, boolean pushUsages) {
                sorted.mark(n);
                newBlock.add(n);
                if (pushUsages) {
                    for (Node u : n.usages()) {
                        if (!sorted.isMarked(u)) {
                            stack.push(u);
                        }
                    }
                }
            }

            
This fills in a map of transitive priorities (priorities). It also marks the nodes from this micro-block in blockNodes. The transitive priority of a guard is the highest of its priority and the priority of the guards that depend on it (transitively). This method returns false if no re-ordering is necessary in this micro-block. /**
             * This fills in a map of transitive priorities ({@code priorities}). It also marks the
             * nodes from this micro-block in {@code blockNodes}.
             *
             * The transitive priority of a guard is the highest of its priority and the priority of
             * the guards that depend on it (transitively).
             *
             * This method returns {@code false} if no re-ordering is necessary in this micro-block.
             */
            private static boolean propagatePriority(MicroBlock block, NodeStack stack, NodeMap<GuardPriority> priorities, NodeBitMap blockNodes) {
                assert stack.isEmpty();
                assert blockNodes.isEmpty();
                GuardPriority lowestPriority = GuardPriority.highest();
                for (NodeEntry e = block.head; e != null; e = e.next) {
                    blockNodes.mark(e.node);
                    if (e.node instanceof GuardNode) {
                        GuardNode guard = (GuardNode) e.node;
                        GuardPriority priority = guard.computePriority();
                        if (lowestPriority != null) {
                            if (priority.isLowerPriorityThan(lowestPriority)) {
                                lowestPriority = priority;
                            } else if (priority.isHigherPriorityThan(lowestPriority)) {
                                lowestPriority = null;
                            }
                        }
                        stack.push(guard);
                        priorities.set(guard, priority);
                    }
                }
                if (lowestPriority != null) {
                    stack.clear();
                    blockNodes.clearAll();
                    return false;
                }

                do {
                    Node current = stack.pop();
                    assert blockNodes.isMarked(current);
                    GuardPriority priority = priorities.get(current);
                    for (Node input : current.inputs()) {
                        if (!blockNodes.isMarked(input)) {
                            continue;
                        }
                        GuardPriority inputPriority = priorities.get(input);
                        if (inputPriority == null || inputPriority.isLowerPriorityThan(priority)) {
                            priorities.set(input, priority);
                            stack.push(input);
                        }
                    }
                } while (!stack.isEmpty());
                return true;
            }
        }

        
Processes the inputs of given block. Pushes unprocessed inputs onto the stack. Returns
null if there were still unprocessed inputs, otherwise returns the earliest block given
node can be scheduled in.
/**
         * Processes the inputs of given block. Pushes unprocessed inputs onto the stack. Returns
         * null if there were still unprocessed inputs, otherwise returns the earliest block given
         * node can be scheduled in.
         */
        private static MicroBlock processInputs(NodeMap<MicroBlock> nodeToBlock, NodeStack stack, MicroBlock startBlock, Node current) {
            if (current.getNodeClass().isLeafNode()) {
                return startBlock;
            }

            MicroBlock earliestBlock = startBlock;
            for (Node input : current.inputs()) {
                MicroBlock inputBlock = nodeToBlock.get(input);
                if (inputBlock == null) {
                    earliestBlock = null;
                    stack.push(input);
                } else if (earliestBlock != null && inputBlock.getId() > earliestBlock.getId()) {
                    earliestBlock = inputBlock;
                }
            }
            return earliestBlock;
        }

        private static boolean isFixedEnd(FixedNode endNode) {
            return endNode instanceof ControlSplitNode || endNode instanceof ControlSinkNode || endNode instanceof AbstractEndNode;
        }

        public String printScheduleHelper(String desc) {
            Formatter buf = new Formatter();
            buf.format("=== %s / %s ===%n", getCFG().getStartBlock().getBeginNode().graph(), desc);
            for (Block b : getCFG().getBlocks()) {
                buf.format("==== b: %s (loopDepth: %s). ", b, b.getLoopDepth());
                buf.format("dom: %s. ", b.getDominator());
                buf.format("preds: %s. ", Arrays.toString(b.getPredecessors()));
                buf.format("succs: %s ====%n", Arrays.toString(b.getSuccessors()));

                if (blockToNodesMap.get(b) != null) {
                    for (Node n : nodesFor(b)) {
                        printNode(n);
                    }
                } else {
                    for (Node n : b.getNodes()) {
                        printNode(n);
                    }
                }
            }
            buf.format("%n");
            return buf.toString();
        }

        private static void printNode(Node n) {
            Formatter buf = new Formatter();
            buf.format("%s", n);
            if (n instanceof MemoryCheckpoint.Single) {
                buf.format(" // kills %s", ((MemoryCheckpoint.Single) n).getLocationIdentity());
            } else if (n instanceof MemoryCheckpoint.Multi) {
                buf.format(" // kills ");
                for (LocationIdentity locid : ((MemoryCheckpoint.Multi) n).getLocationIdentities()) {
                    buf.format("%s, ", locid);
                }
            } else if (n instanceof FloatingReadNode) {
                FloatingReadNode frn = (FloatingReadNode) n;
                buf.format(" // from %s", frn.getLocationIdentity());
                buf.format(", lastAccess: %s", frn.getLastLocationAccess());
                buf.format(", address: %s", frn.getAddress());
            } else if (n instanceof GuardNode) {
                buf.format(", anchor: %s", ((GuardNode) n).getAnchor());
            }
            n.getDebug().log("%s", buf);
        }

        public ControlFlowGraph getCFG() {
            return cfg;
        }

        
Gets the nodes in a given block.
/**
         * Gets the nodes in a given block.
         */
        public List<Node> nodesFor(Block block) {
            return blockToNodesMap.get(block);
        }
    }

}