com.oracle.graal.lir.alloc.lsra

Class LinearScan

java.lang.Object

com.oracle.graal.lir.alloc.lsra.LinearScan

Direct Known Subclasses:

SSALinearScan, SSILinearScan, TraceLinearScan

public class LinearScan
extends Object

An implementation of the linear scan register allocator algorithm described in "Optimized Interval Splitting in a Linear Scan Register Allocator" by Christian Wimmer and Hanspeter Moessenboeck.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	LinearScan.BlockData
(package private) class	LinearScan.CheckConsumer
(package private) static class	LinearScan.IntervalPredicate
static class	LinearScan.Options

Field Summary

Fields

Modifier and Type	Field and Description
private BlockMap<LinearScan.BlockData>	blockData
static int	DOMINATOR_SPILL_MOVE_ID
private int	firstDerivedIntervalIndex The index of the first entry in intervals for a derived interval.
private int	firstVariableNumber The number of the first variable operand allocated.
private FrameMapBuilder	frameMapBuilder
private Interval[]	intervals
private int	intervalsSize The number of valid entries in intervals.
private LIR	ir
(package private) static LinearScan.IntervalPredicate	IS_PRECOLORED_INTERVAL
(package private) static LinearScan.IntervalPredicate	IS_STACK_INTERVAL
(package private) static LinearScan.IntervalPredicate	IS_VARIABLE_INTERVAL
private LIRGeneratorTool.SpillMoveFactory	moveFactory
private AbstractBlockBase<?>[]	opIdToBlockMap Map from an instruction id to the block containing the instruction.
private LIRInstruction[]	opIdToInstructionMap Map from an instruction id to the instruction.
private RegisterAllocationConfig	regAllocConfig
private RegisterAttributes[]	registerAttributes
private Register[]	registers
private List<? extends AbstractBlockBase<?>>	sortedBlocks List of blocks in linear-scan order.
private Interval[]	sortedIntervals Intervals sorted by Interval.from().
private static int	SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	LinearScan(TargetDescription target, LIRGenerationResult res, LIRGeneratorTool.SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, List<? extends AbstractBlockBase<?>> sortedBlocks)

Method Summary

Modifier and Type	Method and Description
(package private) static Interval	addToList(Interval first, Interval prev, Interval interval)
protected <B extends AbstractBlockBase<B>> void	allocate(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, LIRGeneratorTool.SpillMoveFactory spillMoveFactory, RegisterAllocationConfig registerAllocationConfig)
(package private) void	assignSpillSlot(Interval interval)
RegisterAttributes	attributes(Register reg) Gets an object describing the attributes of a given register according to this register configuration.
protected void	beforeSpillMoveElimination()
AbstractBlockBase<?>	blockAt(int index)
int	blockCount()
AbstractBlockBase<?>	blockForId(int opId) Gets the block containing a given instruction.
boolean	callKillsRegisters()
(package private) static StackSlotValue	canonicalSpillOpr(Interval interval)
(package private) boolean	coversBlockBegin(int opId1, int opId2)
protected LinearScanAssignLocationsPhase	createAssignLocationsPhase()
(package private) Interval	createDerivedInterval(Interval source) Creates an interval as a result of splitting or spilling another interval.
(package private) Interval	createInterval(AllocatableValue operand) Creates a new interval.
protected LinearScanLifetimeAnalysisPhase	createLifetimeAnalysisPhase()
protected MoveResolver	createMoveResolver()
protected LinearScanOptimizeSpillPositionPhase	createOptimizeSpillPositionPhase()
protected LinearScanRegisterAllocationPhase	createRegisterAllocationPhase()
protected LinearScanResolveDataFlowPhase	createResolveDataFlowPhase()
protected LinearScanEliminateSpillMovePhase	createSpillMoveEliminationPhase()
(package private) Interval.Pair	createUnhandledLists(LinearScan.IntervalPredicate isList1, LinearScan.IntervalPredicate isList2)
LinearScan.BlockData	getBlockData(AbstractBlockBase<?> block)
int	getFirstLirInstructionId(AbstractBlockBase<?> block)
FrameMapBuilder	getFrameMapBuilder()
int	getLastLirInstructionId(AbstractBlockBase<?> block)
LIR	getLIR()
Interval	getOrCreateInterval(AllocatableValue operand)
RegisterAllocationConfig	getRegisterAllocationConfig()
Register[]	getRegisters()
LIRGeneratorTool.SpillMoveFactory	getSpillMoveFactory()
(package private) boolean	hasCall(int opId) Determines if an LIRInstruction destroys all caller saved registers.
(package private) void	initBlockData(AbstractBlockBase<?> block)
(package private) void	initIntervals()
(package private) void	initOpIdMaps(int numInstructions)
LIRInstruction	instructionForId(int opId) Retrieves the LIRInstruction based on its id.
(package private) Interval	intervalFor(int operandNumber)
Interval	intervalFor(Value operand)
Interval[]	intervals() Map from operand numbers to intervals.
(package private) boolean	isBlockBegin(int opId)
(package private) boolean	isCallerSave(Value operand)
(package private) boolean	isMaterialized(AllocatableValue operand, int opId, LIRInstruction.OperandMode mode)
boolean	isProcessed(Value operand)
private static boolean	isSorted(Interval[] intervals)
static boolean	isVariableOrRegister(Value value)
int	liveSetSize() Gets the size of the LinearScan.BlockData.liveIn and LinearScan.BlockData.liveOut sets for a basic block.
(package private) int	maxOpId() Gets the highest instruction id allocated by this object.
(package private) int	maxRegisterNumber() Gets the highest operand number for a register operand.
(package private) int	numLoops()
(package private) int	operandNumber(Value operand) Converts an operand (variable or register) to an index in a flat address space covering all the variables and registers being processed by this allocator.
(package private) int	operandSize() Gets the number of operands.
private static int	opIdToIndex(int opId) Converts an instruction id to an instruction index.
void	printIntervals(String label)
void	printLir(String label, boolean hirValid)
(package private) void	putOpIdMaps(int index, LIRInstruction op, AbstractBlockBase<?> block)
List<? extends AbstractBlockBase<?>>	sortedBlocks()
(package private) void	sortIntervalsAfterAllocation()
protected void	sortIntervalsBeforeAllocation()
Interval	splitChildAtOpId(Interval interval, int opId, LIRInstruction.OperandMode mode)
(package private) boolean	verify()
protected void	verifyIntervals()
(package private) void	verifyNoOopsInFixedIntervals()
private void	verifyRegisters()

Methods inherited from class java.lang.Object

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

Field Detail

DOMINATOR_SPILL_MOVE_ID

public static final int DOMINATOR_SPILL_MOVE_ID

See Also:

Constant Field Values

SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT

private static final int SPLIT_INTERVALS_CAPACITY_RIGHT_SHIFT

See Also:

Constant Field Values

ir

private final LIR ir

frameMapBuilder

private final FrameMapBuilder frameMapBuilder

registerAttributes

private final RegisterAttributes[] registerAttributes

registers

private final Register[] registers

regAllocConfig

private final RegisterAllocationConfig regAllocConfig

moveFactory

private final LIRGeneratorTool.SpillMoveFactory moveFactory

blockData

private final BlockMap<LinearScan.BlockData> blockData

sortedBlocks

private final List<? extends AbstractBlockBase<?>> sortedBlocks

List of blocks in linear-scan order. This is only correct as long as the CFG does not change.

intervals

private Interval[] intervals

See Also:

intervals()

intervalsSize

private int intervalsSize

The number of valid entries in intervals.

firstDerivedIntervalIndex

private int firstDerivedIntervalIndex

The index of the first entry in intervals for a derived interval.

sortedIntervals

private Interval[] sortedIntervals

Intervals sorted by Interval.from().

opIdToInstructionMap

private LIRInstruction[] opIdToInstructionMap

Map from an instruction id to the instruction. Entries should be retrieved with instructionForId(int) as the id is not simply an index into this array.

opIdToBlockMap

private AbstractBlockBase<?>[] opIdToBlockMap

Map from an instruction id to the block containing the instruction. Entries should be retrieved with blockForId(int) as the id is not simply an index into this array.

firstVariableNumber

private final int firstVariableNumber

The number of the first variable operand allocated.

IS_PRECOLORED_INTERVAL

static final LinearScan.IntervalPredicate IS_PRECOLORED_INTERVAL

IS_VARIABLE_INTERVAL

static final LinearScan.IntervalPredicate IS_VARIABLE_INTERVAL

IS_STACK_INTERVAL

static final LinearScan.IntervalPredicate IS_STACK_INTERVAL

Constructor Detail

LinearScan

protected LinearScan(TargetDescription target,
                     LIRGenerationResult res,
                     LIRGeneratorTool.SpillMoveFactory spillMoveFactory,
                     RegisterAllocationConfig regAllocConfig,
                     List<? extends AbstractBlockBase<?>> sortedBlocks)

Method Detail

getFirstLirInstructionId

public int getFirstLirInstructionId(AbstractBlockBase<?> block)

getLastLirInstructionId

public int getLastLirInstructionId(AbstractBlockBase<?> block)

getSpillMoveFactory

public LIRGeneratorTool.SpillMoveFactory getSpillMoveFactory()

createMoveResolver

protected MoveResolver createMoveResolver()

isVariableOrRegister

public static boolean isVariableOrRegister(Value value)

operandNumber

int operandNumber(Value operand)

Converts an operand (variable or register) to an index in a flat address space covering all the variables and registers being processed by this allocator.

operandSize

int operandSize()

Gets the number of operands. This value will increase by 1 for new variable.

maxRegisterNumber

int maxRegisterNumber()

Gets the highest operand number for a register operand. This value will never change.

getBlockData

public LinearScan.BlockData getBlockData(AbstractBlockBase<?> block)

initBlockData

void initBlockData(AbstractBlockBase<?> block)

attributes

public RegisterAttributes attributes(Register reg)

Gets an object describing the attributes of a given register according to this register configuration.

assignSpillSlot

void assignSpillSlot(Interval interval)

intervals

public Interval[] intervals()

Map from operand numbers to intervals.

initIntervals

void initIntervals()

createInterval

Interval createInterval(AllocatableValue operand)

Creates a new interval.

Parameters:

operand - the operand for the interval

Returns:

the created interval

createDerivedInterval

Interval createDerivedInterval(Interval source)

Creates an interval as a result of splitting or spilling another interval.

Parameters:

source - an interval being split of spilled

Returns:

a new interval derived from source

blockCount

public int blockCount()

blockAt

public AbstractBlockBase<?> blockAt(int index)

liveSetSize

public int liveSetSize()

Gets the size of the LinearScan.BlockData.liveIn and LinearScan.BlockData.liveOut sets for a basic block. These sets do not include any operands allocated as a result of creating derived intervals.

numLoops

int numLoops()

intervalFor

Interval intervalFor(int operandNumber)

intervalFor

public Interval intervalFor(Value operand)

getOrCreateInterval

public Interval getOrCreateInterval(AllocatableValue operand)

initOpIdMaps

void initOpIdMaps(int numInstructions)

putOpIdMaps

void putOpIdMaps(int index,
                 LIRInstruction op,
                 AbstractBlockBase<?> block)

maxOpId

int maxOpId()

Gets the highest instruction id allocated by this object.

opIdToIndex

private static int opIdToIndex(int opId)

Converts an instruction id to an instruction index. All LIR instructions in a method have an index one greater than their linear-scan order predecessor with the first instruction having an index of 0.

instructionForId

public LIRInstruction instructionForId(int opId)

Retrieves the LIRInstruction based on its id.

Parameters:

opId - an instruction id

Returns:

the instruction whose LIRInstruction.id == id

blockForId

public AbstractBlockBase<?> blockForId(int opId)

Gets the block containing a given instruction.

Parameters:

opId - an instruction id

Returns:

the block containing the instruction denoted by opId

isBlockBegin

boolean isBlockBegin(int opId)

coversBlockBegin

boolean coversBlockBegin(int opId1,
                         int opId2)

hasCall

boolean hasCall(int opId)

Determines if an LIRInstruction destroys all caller saved registers.

Parameters:

opId - an instruction id

Returns:

true if the instruction denoted by id destroys all caller saved registers.

isProcessed

public boolean isProcessed(Value operand)

isSorted

private static boolean isSorted(Interval[] intervals)

addToList

static Interval addToList(Interval first,
                          Interval prev,
                          Interval interval)

createUnhandledLists

Interval.Pair createUnhandledLists(LinearScan.IntervalPredicate isList1,
                                   LinearScan.IntervalPredicate isList2)

sortIntervalsBeforeAllocation

protected void sortIntervalsBeforeAllocation()

sortIntervalsAfterAllocation

void sortIntervalsAfterAllocation()

splitChildAtOpId

public Interval splitChildAtOpId(Interval interval,
                                 int opId,
                                 LIRInstruction.OperandMode mode)

canonicalSpillOpr

static StackSlotValue canonicalSpillOpr(Interval interval)

isMaterialized

boolean isMaterialized(AllocatableValue operand,
                       int opId,
                       LIRInstruction.OperandMode mode)

isCallerSave

boolean isCallerSave(Value operand)

allocate

protected <B extends AbstractBlockBase<B>> void allocate(TargetDescription target,
                                                         LIRGenerationResult lirGenRes,
                                                         List<B> codeEmittingOrder,
                                                         List<B> linearScanOrder,
                                                         LIRGeneratorTool.SpillMoveFactory spillMoveFactory,
                                                         RegisterAllocationConfig registerAllocationConfig)

beforeSpillMoveElimination

protected void beforeSpillMoveElimination()

createLifetimeAnalysisPhase

protected LinearScanLifetimeAnalysisPhase createLifetimeAnalysisPhase()

createRegisterAllocationPhase

protected LinearScanRegisterAllocationPhase createRegisterAllocationPhase()

createOptimizeSpillPositionPhase

protected LinearScanOptimizeSpillPositionPhase createOptimizeSpillPositionPhase()

createResolveDataFlowPhase

protected LinearScanResolveDataFlowPhase createResolveDataFlowPhase()

createSpillMoveEliminationPhase

protected LinearScanEliminateSpillMovePhase createSpillMoveEliminationPhase()

createAssignLocationsPhase

protected LinearScanAssignLocationsPhase createAssignLocationsPhase()

printIntervals

public void printIntervals(String label)

printLir

public void printLir(String label,
                     boolean hirValid)

verify

boolean verify()

verifyRegisters

private void verifyRegisters()

verifyIntervals

protected void verifyIntervals()

verifyNoOopsInFixedIntervals

void verifyNoOopsInFixedIntervals()

getLIR

public LIR getLIR()

getFrameMapBuilder

public FrameMapBuilder getFrameMapBuilder()

sortedBlocks

public List<? extends AbstractBlockBase<?>> sortedBlocks()

getRegisters

public Register[] getRegisters()

getRegisterAllocationConfig

public RegisterAllocationConfig getRegisterAllocationConfig()

callKillsRegisters

public boolean callKillsRegisters()