com.oracle.graal.compiler.common.alloc

Class ComputeBlockOrder

java.lang.Object

com.oracle.graal.compiler.common.alloc.ComputeBlockOrder

public final class ComputeBlockOrder
extends Object

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.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private static class	ComputeBlockOrder.BlockOrderComparator<T extends AbstractBlockBase<T>> Comparator for sorting blocks based on loop depth and probability.

Field Summary

Fields

Modifier and Type	Field and Description
private static int	INITIAL_WORKLIST_CAPACITY The initial capacities of the worklists used for iteratively finding the block order.
private static int	PENALTY_VERSUS_UNSCHEDULED Divisor used for degrading the probability of the current path versus unscheduled paths at a merge node when calculating the linear scan order.

Constructor Summary

Constructors

Constructor and Description
ComputeBlockOrder()

Method Summary

Modifier and Type	Method and Description
private static <T extends AbstractBlockBase<T>> void	addBlock(T header, List<T> order) Adds a block to the ordering.
private static <T extends AbstractBlockBase<T>> void	addPathToCodeEmittingOrder(T initialBlock, List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) Add a linear path to the code emission order greedily following the most likely successor.
private static <T extends AbstractBlockBase<T>> void	addPathToLinearScanOrder(T block, List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) Add a linear path to the linear scan order greedily following the most likely successor.
private static boolean	checkOrder(List<? extends AbstractBlockBase<?>> order, int expectedBlockCount) Checks that the ordering contains the expected number of blocks.
static <T extends AbstractBlockBase<T>> List<T>	computeCodeEmittingOrder(int blockCount, T startBlock) Computes the block order used for code emission.
private static <T extends AbstractBlockBase<T>> void	computeCodeEmittingOrder(List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) Iteratively adds paths to the code emission block order.
static <T extends AbstractBlockBase<T>> List<T>	computeLinearScanOrder(int blockCount, T startBlock) Computes the block order used for the linear scan register allocator.
private static <T extends AbstractBlockBase<T>> void	computeLinearScanOrder(List<T> order, PriorityQueue<T> worklist, BitSet visitedBlocks) Iteratively adds paths to the linear scan block order.
private static <T extends AbstractBlockBase<T>> void	enqueueSuccessors(T block, PriorityQueue<T> worklist, BitSet visitedBlocks) Add successor blocks into the given work list if they are not already marked as visited.
private static <T extends AbstractBlockBase<T>> T	findAndMarkMostLikelySuccessor(T block, BitSet visitedBlocks) Find the highest likely unvisited successor block of a given block.
private static <T extends AbstractBlockBase<T>> PriorityQueue<T>	initializeWorklist(T startBlock, BitSet visitedBlocks) Initializes the priority queue used for the work list of blocks and adds the start block.
private static <T extends AbstractBlockBase<T>> boolean	skipLoopHeader(AbstractBlockBase<T> block) Skip the loop header block if the loop consists of more than one block and it has only a single loop end block.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

INITIAL_WORKLIST_CAPACITY

private static final int INITIAL_WORKLIST_CAPACITY

The initial capacities of the worklists used for iteratively finding the block order.

See Also:

Constant Field Values

PENALTY_VERSUS_UNSCHEDULED

private static final int PENALTY_VERSUS_UNSCHEDULED

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.

See Also:

Constant Field Values

Constructor Detail

ComputeBlockOrder

public ComputeBlockOrder()

Method Detail

computeLinearScanOrder

public static <T extends AbstractBlockBase<T>> List<T> computeLinearScanOrder(int blockCount,
                                                                              T startBlock)

Computes the block order used for the linear scan register allocator.

Returns:

sorted list of blocks

computeCodeEmittingOrder

public static <T extends AbstractBlockBase<T>> List<T> computeCodeEmittingOrder(int blockCount,
                                                                                T startBlock)

Computes the block order used for code emission.

Returns:

sorted list of blocks

computeCodeEmittingOrder

private static <T extends AbstractBlockBase<T>> void computeCodeEmittingOrder(List<T> order,
                                                                              PriorityQueue<T> worklist,
                                                                              BitSet visitedBlocks)

Iteratively adds paths to the code emission block order.

computeLinearScanOrder

private static <T extends AbstractBlockBase<T>> void computeLinearScanOrder(List<T> order,
                                                                            PriorityQueue<T> worklist,
                                                                            BitSet visitedBlocks)

Iteratively adds paths to the linear scan block order.

initializeWorklist

private static <T extends AbstractBlockBase<T>> PriorityQueue<T> initializeWorklist(T startBlock,
                                                                                    BitSet visitedBlocks)

Initializes the priority queue used for the work list of blocks and adds the start block.

addPathToLinearScanOrder

private static <T extends AbstractBlockBase<T>> void addPathToLinearScanOrder(T block,
                                                                              List<T> order,
                                                                              PriorityQueue<T> worklist,
                                                                              BitSet visitedBlocks)

Add a linear path to the linear scan order greedily following the most likely successor.

addPathToCodeEmittingOrder

private static <T extends AbstractBlockBase<T>> void addPathToCodeEmittingOrder(T initialBlock,
                                                                                List<T> order,
                                                                                PriorityQueue<T> worklist,
                                                                                BitSet visitedBlocks)

Add a linear path to the code emission order greedily following the most likely successor.

addBlock

private static <T extends AbstractBlockBase<T>> void addBlock(T header,
                                                              List<T> order)

Adds a block to the ordering.

findAndMarkMostLikelySuccessor

private static <T extends AbstractBlockBase<T>> T findAndMarkMostLikelySuccessor(T block,
                                                                                 BitSet visitedBlocks)

Find the highest likely unvisited successor block of a given block.

enqueueSuccessors

private static <T extends AbstractBlockBase<T>> void enqueueSuccessors(T block,
                                                                       PriorityQueue<T> worklist,
                                                                       BitSet visitedBlocks)

Add successor blocks into the given work list if they are not already marked as visited.

skipLoopHeader

private static <T extends AbstractBlockBase<T>> boolean skipLoopHeader(AbstractBlockBase<T> block)

Skip the loop header block if the loop consists of more than one block and it has only a single loop end block.

checkOrder

private static boolean checkOrder(List<? extends AbstractBlockBase<?>> order,
                                  int expectedBlockCount)

Checks that the ordering contains the expected number of blocks.