org.jikesrvm.compilers.opt.regalloc

Class ActiveSet

java.lang.Object

java.util.AbstractCollection<E>

java.util.AbstractSet<E>

java.util.TreeSet<BasicInterval>

org.jikesrvm.compilers.opt.regalloc.IntervalSet

org.jikesrvm.compilers.opt.regalloc.IncreasingEndMappedIntervalSet

org.jikesrvm.compilers.opt.regalloc.ActiveSet

All Implemented Interfaces:

Serializable, Cloneable, Iterable<BasicInterval>, Collection<BasicInterval>, NavigableSet<BasicInterval>, Set<BasicInterval>, SortedSet<BasicInterval>

final class ActiveSet
extends IncreasingEndMappedIntervalSet

"Active set" for linear scan register allocation. This version is maintained sorted in order of increasing live interval end point.

Field Summary

Fields

Modifier and Type	Field and Description
private IR	ir Governing ir
private RegisterAllocatorState	regAllocState
(package private) static long	serialVersionUID Support for Set serialization
private SpillCostEstimator	spillCost An object to help estimate spill costs
private boolean	spilled Have we spilled anything?
private SpillLocationManager	spillManager Manager of spill locations;

Fields inherited from class org.jikesrvm.compilers.opt.regalloc.IncreasingEndMappedIntervalSet

c

Constructor Summary

Constructors

Constructor and Description
ActiveSet(IR ir, SpillLocationManager sm, SpillCostEstimator cost)

Method Summary

Modifier and Type	Method and Description
(package private) void	allocate(BasicInterval newInterval, CompoundInterval container)
private boolean	allocateNewSymbolicToPhysical(Register symb, Register p) NOTE: This routine assumes we're processing the first interval of register symb; so p.isAvailable() is the key information needed.
private boolean	allocateToPhysical(CompoundInterval i, Register p) Checks whether it's ok to allocate an interval to a physical register.
private boolean	checkAssignmentIfSpilled(CompoundInterval i, CompoundInterval spill) Checks if it would be possible to assign an interval to the physical register of another interval if that other interval were spilled.
(package private) boolean	currentlyActive(Register r)
(package private) void	expireOldIntervals(BasicInterval newInterval) For each new basic interval, we scan the list of active basic intervals in order of increasing end point.
(package private) Register	findAvailableRegister(CompoundInterval ci)
(package private) Register	findAvailableRegister(Register symb)
(package private) void	freeInterval(MappedBasicInterval bi)
(package private) BasicInterval	getBasicInterval(Register r, Instruction s) Finds a basic interval for a register so that the interval contains the instruction.
(package private) CompoundInterval	getCurrentInterval(Register r)
private Register	getPhysicalPreference(CompoundInterval ci) Given the current state of the register allocator, compute the available physical register to which an interval has the highest preference.
private Register	getPhysicalPreference(Register r) Given the current state of the register allocator, compute the available physical register to which a symbolic register has the highest preference.
private CompoundInterval	getSpillCandidate(CompoundInterval newInterval)
(package private) boolean	spilledSomething()
private CompoundInterval	spillMinUnitCost(CompoundInterval newInterval) Chooses the interval with the minimal unit cost (defined as the number of defs and uses).
private void	updatePhysicalInterval(Register p, BasicInterval i) Updates the interval representing the allocations of a physical register p to include a new interval i.
private void	updatePhysicalInterval(Register p, CompoundInterval c, BasicInterval stop) Update the interval representing the allocations of a physical register p to include a new compound interval c.

Methods inherited from class org.jikesrvm.compilers.opt.regalloc.IntervalSet

toString

Methods inherited from class java.util.TreeSet

add, addAll, ceiling, clear, clone, comparator, contains, descendingIterator, descendingSet, first, floor, headSet, headSet, higher, isEmpty, iterator, last, lower, pollFirst, pollLast, remove, size, spliterator, subSet, subSet, tailSet, tailSet

Methods inherited from class java.util.AbstractSet

equals, hashCode, removeAll

Methods inherited from class java.util.AbstractCollection

containsAll, retainAll, toArray, toArray

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Set

containsAll, equals, hashCode, removeAll, retainAll, toArray, toArray

Methods inherited from interface java.util.Collection

parallelStream, removeIf, stream

Methods inherited from interface java.lang.Iterable

forEach

Field Detail

serialVersionUID

static final long serialVersionUID

Support for Set serialization

See Also:

Constant Field Values

ir

private final IR ir

Governing ir

regAllocState

private final RegisterAllocatorState regAllocState

spillManager

private final SpillLocationManager spillManager

Manager of spill locations;

spillCost

private final transient SpillCostEstimator spillCost

An object to help estimate spill costs

spilled

private boolean spilled

Have we spilled anything?

Constructor Detail

ActiveSet

ActiveSet(IR ir,
          SpillLocationManager sm,
          SpillCostEstimator cost)

Method Detail

spilledSomething

boolean spilledSomething()

expireOldIntervals

void expireOldIntervals(BasicInterval newInterval)

For each new basic interval, we scan the list of active basic intervals in order of increasing end point. We remove any "expired" intervals - those intervals that no longer overlap the new interval because their end point precedes the new interval's start point - and makes the corresponding register available for allocation

Parameters:

newInterval - the new interval

freeInterval

void freeInterval(MappedBasicInterval bi)

allocate

void allocate(BasicInterval newInterval,
              CompoundInterval container)

updatePhysicalInterval

private void updatePhysicalInterval(Register p,
                                    BasicInterval i)

Updates the interval representing the allocations of a physical register p to include a new interval i.

Parameters:

p - a physical register

i - the new interval

updatePhysicalInterval

private void updatePhysicalInterval(Register p,
                                    CompoundInterval c,
                                    BasicInterval stop)

Update the interval representing the allocations of a physical register p to include a new compound interval c. Include only those basic intervals in c up to and including basic interval stop.

Parameters:

p - a physical register

c - the new interval

stop - the last interval to be included

currentlyActive

boolean currentlyActive(Register r)

Parameters:

r - a physical register

Returns:

whether the particular physical register is currently allocated to an interval in the active set

getCurrentInterval

CompoundInterval getCurrentInterval(Register r)

Parameters:

r - a physical register

Returns:

the interval that the physical register is allocated to

Throws:

OptimizingCompilerException - if the register is not currently allocated to any interval

findAvailableRegister

Register findAvailableRegister(CompoundInterval ci)

Parameters:

ci - interval to allocate

Returns:

a free physical register to allocate to the compound interval, null if no free physical register is found

findAvailableRegister

Register findAvailableRegister(Register symb)

Parameters:

symb - symbolic register to allocate

Returns:

a free physical register to allocate to the symbolic register, null if no free physical register is found

getPhysicalPreference

private Register getPhysicalPreference(Register r)

Given the current state of the register allocator, compute the available physical register to which a symbolic register has the highest preference.

Parameters:

r - the symbolic register in question.

Returns:

the preferred register, null if no preference found.

getPhysicalPreference

private Register getPhysicalPreference(CompoundInterval ci)

Given the current state of the register allocator, compute the available physical register to which an interval has the highest preference.

Parameters:

ci - the interval in question

Returns:

the preferred register, null if no preference found

allocateToPhysical

private boolean allocateToPhysical(CompoundInterval i,
                                   Register p)

Checks whether it's ok to allocate an interval to a physical register.

Parameters:

i - the interval to allocate

p - the physical register

Returns:

true if it's ok to allocate the interval to the given physical register, false otherwise

allocateNewSymbolicToPhysical

private boolean allocateNewSymbolicToPhysical(Register symb,
                                              Register p)

NOTE: This routine assumes we're processing the first interval of register symb; so p.isAvailable() is the key information needed.

Parameters:

symb - the symbolic register

p - the physical register

Returns:

whether it's ok to allocate the symbolic register to the physical register

getSpillCandidate

private CompoundInterval getSpillCandidate(CompoundInterval newInterval)

Parameters:

newInterval - a new interval

Returns:

an interval that can be spilled. This may be chosen from the existing candidates and the new interval

spillMinUnitCost

private CompoundInterval spillMinUnitCost(CompoundInterval newInterval)

Chooses the interval with the minimal unit cost (defined as the number of defs and uses).

Parameters:

newInterval - a new interval

Returns:

the interval with the minimal number of defs and uses

checkAssignmentIfSpilled

private boolean checkAssignmentIfSpilled(CompoundInterval i,
                                         CompoundInterval spill)

Checks if it would be possible to assign an interval to the physical register of another interval if that other interval were spilled.

Parameters:

spill - the interval that's a candidate for spilling

i - the interval that we want to assign to the register of the spill interval

Returns:

true if the allocation would fit, false otherwise

getBasicInterval

BasicInterval getBasicInterval(Register r,
                               Instruction s)

Finds a basic interval for a register so that the interval contains the instruction.

Parameters:

r - the register whose interval is desired

s - the reference instruction

Returns:

null if there is no basic interval for the given register that contains the instruction, the interval otherwise. If there are multiple intervals, the first one will be returned.