/*
 * 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.FixedWithNextNode;
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,
        FINAL_SCHEDULE
    }

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

            if (selectedStrategy != SchedulingStrategy.EARLIEST) {
                // 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<Node>());
                }

                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) {
                    assert latestBlock != null;
                    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, null);
                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() {
                return nodeCount;
            }

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

        
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, NodeEntry next) {
                this.node = node;
                this.next = next;
            }

            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) {

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

            // Initialize with fixed nodes.
            MicroBlock startBlock = null;
            int nextId = 1;
            for (Block b : cfg.reversePostOrder()) {
                FixedNode current = b.getBeginNode();
                while (true) {
                    MicroBlock microBlock = new MicroBlock(nextId++);
                    entries.put(current, microBlock);
                    visited.checkAndMarkInc(current);

                    if (startBlock == null) {
                        startBlock = microBlock;
                    }

                    // Process inputs of this fixed node.
                    for (Node input : current.inputs()) {
                        if (entries.get(input) == null) {
                            processStack(input, startBlock, entries, visited, stack);
                        }
                    }

                    if (current == b.getEndNode()) {
                        // Break loop when reaching end node.
                        break;
                    }

                    current = ((FixedWithNextNode) current).next();
                }
            }

            // Now process guards.
            for (GuardNode guardNode : graph.getNodes(GuardNode.TYPE)) {
                if (entries.get(guardNode) == null) {
                    processStack(guardNode, startBlock, entries, visited, stack);
                }
            }

            // Now process inputs of fixed nodes.
            for (Block b : cfg.reversePostOrder()) {
                FixedNode current = b.getBeginNode();
                while (true) {

                    // Process inputs of this fixed node.
                    for (Node input : current.inputs()) {
                        if (entries.get(input) == null) {
                            processStack(input, startBlock, entries, visited, stack);
                        }
                    }

                    if (current == b.getEndNode()) {
                        // Break loop when reaching end node.
                        break;
                    }

                    current = ((FixedWithNextNode) current).next();
                }
            }

            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);
                    MicroBlock primarySuccessor = entries.get(controlSplitNode.getPrimarySuccessor());
                    endBlock.prependChildrenTo(primarySuccessor);
                }
            }

            // Initialize with begin nodes
            for (Block b : cfg.reversePostOrder()) {

                FixedNode current = b.getBeginNode();
                int totalCount = 0;
                while (true) {

                    MicroBlock microBlock = entries.get(current);
                    totalCount += microBlock.getNodeCount() + 1;

                    if (current == b.getEndNode()) {
                        // Break loop when reaching end node.
                        break;
                    }

                    current = ((FixedWithNextNode) current).next();
                }

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

                current = b.getBeginNode();
                while (true) {

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

                    if (current == b.getEndNode()) {
                        // Break loop when reaching end node.
                        break;
                    }

                    current = ((FixedWithNextNode) current).next();
                }
            }

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

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

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

}