/*
 * Copyright (c) 2009, 2011, 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.core.common.alloc;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
import org.graalvm.compiler.core.common.cfg.Loop;

Computes an ordering of the block that can be used by the linear scan register allocator and the
machine code generator. The machine code generation order will start with the first block and
produce a straight sequence always following the most likely successor. Then it will continue
with the most likely path that was left out during this process. The process iteratively
continues until all blocks are scheduled. Additionally, it is guaranteed that all blocks of a
loop are scheduled before any block following the loop is scheduled.
The machine code generator order includes reordering of loop headers such that the backward jump
is a conditional jump if there is only one loop end block. Additionally, the target of loop
backward jumps are always marked as aligned. Aligning the target of conditional jumps does not
bring a measurable benefit and is therefore avoided to keep the code size small.
The linear scan register allocator order has an additional mechanism that prevents merge nodes
from being scheduled if there is at least one highly likely predecessor still unscheduled. This
increases the probability that the merge node and the corresponding predecessor are more closely
together in the schedule thus decreasing the probability for inserted phi moves. Also, the
algorithm sets the linear scan order number of the block that corresponds to its index in the
linear scan order.
/**
 * Computes an ordering of the block that can be used by the linear scan register allocator and the
 * machine code generator. The machine code generation order will start with the first block and
 * produce a straight sequence always following the most likely successor. Then it will continue
 * with the most likely path that was left out during this process. The process iteratively
 * continues until all blocks are scheduled. Additionally, it is guaranteed that all blocks of a
 * loop are scheduled before any block following the loop is scheduled.
 *
 * The machine code generator order includes reordering of loop headers such that the backward jump
 * is a conditional jump if there is only one loop end block. Additionally, the target of loop
 * backward jumps are always marked as aligned. Aligning the target of conditional jumps does not
 * bring a measurable benefit and is therefore avoided to keep the code size small.
 *
 * The linear scan register allocator order has an additional mechanism that prevents merge nodes
 * from being scheduled if there is at least one highly likely predecessor still unscheduled. This
 * increases the probability that the merge node and the corresponding predecessor are more closely
 * together in the schedule thus decreasing the probability for inserted phi moves. Also, the
 * algorithm sets the linear scan order number of the block that corresponds to its index in the
 * linear scan order.
 */
public final class ComputeBlockOrder {

    
The initial capacities of the worklists used for iteratively finding the block order.
/**
     * The initial capacities of the worklists used for iteratively finding the block order.
     */
    private static final int INITIAL_WORKLIST_CAPACITY = 10;

    
Divisor used for degrading the probability of the current path versus unscheduled paths at a
merge node when calculating the linear scan order. A high value means that predecessors of
merge nodes are more likely to be scheduled before the merge node.
/**
     * Divisor used for degrading the probability of the current path versus unscheduled paths at a
     * merge node when calculating the linear scan order. A high value means that predecessors of
     * merge nodes are more likely to be scheduled before the merge node.
     */
    private static final int PENALTY_VERSUS_UNSCHEDULED = 10;

    
Computes the block order used for the linear scan register allocator.
Returns:
sorted list of blocks/**
     * Computes the block order used for the linear scan register allocator.
     *
     * @return sorted list of blocks
     */
    public static <T extends AbstractBlockBase<T>> AbstractBlockBase<?>[] computeLinearScanOrder(int blockCount, T startBlock) {
        List<T> order = new ArrayList<>();
        BitSet visitedBlocks = new BitSet(blockCount);
        PriorityQueue<T> worklist = initializeWorklist(startBlock, visitedBlocks);
        computeLinearScanOrder(order, worklist, visitedBlocks);
        assert checkOrder(order, blockCount);
        return order.toArray(new AbstractBlockBase<?>[0]);
    }

    
Computes the block order used for code emission.
Returns:
sorted list of blocks/**
     * Computes the block order used for code emission.
     *
     * @return sorted list of blocks
     */
    public static <T extends AbstractBlockBase<T>> AbstractBlockBase<?>[] computeCodeEmittingOrder(int blockCount, T startBlock) {
        List<T> order = new ArrayList<>();
        BitSet visitedBlocks = new BitSet(blockCount);
        PriorityQueue<T> worklist = initializeWorklist(startBlock, visitedBlocks);
        computeCodeEmittingOrder(order, worklist, visitedBlocks);
        assert checkOrder(order, blockCount);
        return order.toArray(new AbstractBlockBase<?>[0]);
    }

    
Iteratively adds paths to the code emission block order.
/**
     * Iteratively adds paths to the code emission block order.
     */
    private static <T extends AbstractBlockBase<T>> void computeCodeEmittingOrder(List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) {
        while (!worklist.isEmpty()) {
            T nextImportantPath = worklist.poll();
            addPathToCodeEmittingOrder(nextImportantPath, order, worklist, visitedBlocks);
        }
    }

    
Iteratively adds paths to the linear scan block order.
/**
     * Iteratively adds paths to the linear scan block order.
     */
    private static <T extends AbstractBlockBase<T>> void computeLinearScanOrder(List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) {
        while (!worklist.isEmpty()) {
            T nextImportantPath = worklist.poll();
            do {
                nextImportantPath = addPathToLinearScanOrder(nextImportantPath, order, worklist, visitedBlocks);
            } while (nextImportantPath != null);
        }
    }

    
Initializes the priority queue used for the work list of blocks and adds the start block.
/**
     * Initializes the priority queue used for the work list of blocks and adds the start block.
     */
    private static <T extends AbstractBlockBase<T>> PriorityQueue<T> initializeWorklist(T startBlock, BitSet visitedBlocks) {
        PriorityQueue<T> result = new PriorityQueue<>(INITIAL_WORKLIST_CAPACITY, new BlockOrderComparator<>());
        result.add(startBlock);
        visitedBlocks.set(startBlock.getId());
        return result;
    }

    
Add a linear path to the linear scan order greedily following the most likely successor.
/**
     * Add a linear path to the linear scan order greedily following the most likely successor.
     */
    private static <T extends AbstractBlockBase<T>> T addPathToLinearScanOrder(T block, List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) {
        block.setLinearScanNumber(order.size());
        order.add(block);
        T mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks);
        enqueueSuccessors(block, worklist, visitedBlocks);
        if (mostLikelySuccessor != null) {
            if (!mostLikelySuccessor.isLoopHeader() && mostLikelySuccessor.getPredecessorCount() > 1) {
                // We are at a merge. Check probabilities of predecessors that are not yet
                // scheduled.
                double unscheduledSum = 0.0;
                for (T pred : mostLikelySuccessor.getPredecessors()) {
                    if (pred.getLinearScanNumber() == -1) {
                        unscheduledSum += pred.probability();
                    }
                }

                if (unscheduledSum > block.probability() / PENALTY_VERSUS_UNSCHEDULED) {
                    // Add this merge only after at least one additional predecessor gets scheduled.
                    visitedBlocks.clear(mostLikelySuccessor.getId());
                    return null;
                }
            }
            return mostLikelySuccessor;
        }
        return null;
    }

    
Add a linear path to the code emission order greedily following the most likely successor.
/**
     * Add a linear path to the code emission order greedily following the most likely successor.
     */
    private static <T extends AbstractBlockBase<T>> void addPathToCodeEmittingOrder(T initialBlock, List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) {
        T block = initialBlock;
        while (block != null) {
            // Skip loop headers if there is only a single loop end block to
            // make the backward jump be a conditional jump.
            if (!skipLoopHeader(block)) {

                // Align unskipped loop headers as they are the target of the backward jump.
                if (block.isLoopHeader()) {
                    block.setAlign(true);
                }
                addBlock(block, order);
            }

            Loop<T> loop = block.getLoop();
            if (block.isLoopEnd() && skipLoopHeader(loop.getHeader())) {

                // This is the only loop end of a skipped loop header.
                // Add the header immediately afterwards.
                addBlock(loop.getHeader(), order);

                // Make sure the loop successors of the loop header are aligned
                // as they are the target
                // of the backward jump.
                for (T successor : loop.getHeader().getSuccessors()) {
                    if (successor.getLoopDepth() == block.getLoopDepth()) {
                        successor.setAlign(true);
                    }
                }
            }

            T mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks);
            enqueueSuccessors(block, worklist, visitedBlocks);
            block = mostLikelySuccessor;
        }
    }

    
Adds a block to the ordering.
/**
     * Adds a block to the ordering.
     */
    private static <T extends AbstractBlockBase<T>> void addBlock(T header, List<T> order) {
        assert !order.contains(header) : "Cannot insert block twice";
        order.add(header);
    }

    
Find the highest likely unvisited successor block of a given block.
/**
     * Find the highest likely unvisited successor block of a given block.
     */
    private static <T extends AbstractBlockBase<T>> T findAndMarkMostLikelySuccessor(T block, BitSet visitedBlocks) {
        T result = null;
        for (T successor : block.getSuccessors()) {
            assert successor.probability() >= 0.0 : "Probabilities must be positive";
            if (!visitedBlocks.get(successor.getId()) && successor.getLoopDepth() >= block.getLoopDepth() && (result == null || successor.probability() >= result.probability())) {
                result = successor;
            }
        }
        if (result != null) {
            visitedBlocks.set(result.getId());
        }
        return result;
    }

    
Add successor blocks into the given work list if they are not already marked as visited.
/**
     * Add successor blocks into the given work list if they are not already marked as visited.
     */
    private static <T extends AbstractBlockBase<T>> void enqueueSuccessors(T block, PriorityQueue<T> worklist, BitSet visitedBlocks) {
        for (T successor : block.getSuccessors()) {
            if (!visitedBlocks.get(successor.getId())) {
                visitedBlocks.set(successor.getId());
                worklist.add(successor);
            }
        }
    }

    
Skip the loop header block if the loop consists of more than one block and it has only a
single loop end block.
/**
     * Skip the loop header block if the loop consists of more than one block and it has only a
     * single loop end block.
     */
    private static <T extends AbstractBlockBase<T>> boolean skipLoopHeader(AbstractBlockBase<T> block) {
        return (block.isLoopHeader() && !block.isLoopEnd() && block.getLoop().numBackedges() == 1);
    }

    
Checks that the ordering contains the expected number of blocks.
/**
     * Checks that the ordering contains the expected number of blocks.
     */
    private static boolean checkOrder(List<? extends AbstractBlockBase<?>> order, int expectedBlockCount) {
        assert order.size() == expectedBlockCount : String.format("Number of blocks in ordering (%d) does not match expected block count (%d)", order.size(), expectedBlockCount);
        return true;
    }

    
Comparator for sorting blocks based on loop depth and probability.
/**
     * Comparator for sorting blocks based on loop depth and probability.
     */
    private static class BlockOrderComparator<T extends AbstractBlockBase<T>> implements Comparator<T> {
        private static final double EPSILON = 1E-6;

        @Override
        public int compare(T a, T b) {
            // Loop blocks before any loop exit block. The only exception are blocks that are
            // (almost) impossible to reach.
            if (a.probability() > EPSILON && b.probability() > EPSILON) {
                int diff = b.getLoopDepth() - a.getLoopDepth();
                if (diff != 0) {
                    return diff;
                }
            }

            // Blocks with high probability before blocks with low probability.
            if (a.probability() > b.probability()) {
                return -1;
            } else {
                return 1;
            }
        }
    }
}