org.jikesrvm.compilers.opt.regalloc
Class LinearScan.ActiveSet

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractSet<E>
          java.util.TreeSet<LinearScan.BasicInterval>
              org.jikesrvm.compilers.opt.regalloc.LinearScan.IntervalSet
                  org.jikesrvm.compilers.opt.regalloc.LinearScan.IncreasingEndMappedIntervalSet
                      org.jikesrvm.compilers.opt.regalloc.LinearScan.ActiveSet

All Implemented Interfaces:

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

Enclosing class:

LinearScan

static final class LinearScan.ActiveSet
extends LinearScan.IncreasingEndMappedIntervalSet

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

serialVersionUID

static final long serialVersionUID

Support for Set serialization

See Also:

Constant Field Values

ir

private final IR ir

Governing ir

spillManager

private final LinearScan.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?

LinearScan.ActiveSet

LinearScan.ActiveSet(IR ir,
                     LinearScan.SpillLocationManager sm)

Default constructor

spilledSomething

boolean spilledSomething()

Have we spilled anything?

expireOldIntervals

void expireOldIntervals(LinearScan.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(LinearScan.MappedBasicInterval bi)

Take action when a basic interval becomes inactive

allocate

void allocate(LinearScan.BasicInterval newInterval,
              LinearScan.CompoundInterval container)

Assign a basic interval to either a register or a spill location.

updatePhysicalInterval

private void updatePhysicalInterval(Register p,
                                    LinearScan.BasicInterval i)

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

updatePhysicalInterval

private void updatePhysicalInterval(Register p,
                                    LinearScan.CompoundInterval c,
                                    LinearScan.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.

currentlyActive

boolean currentlyActive(Register r)

Is a particular physical register currently allocated to an interval in the active set?

getCurrentInterval

LinearScan.CompoundInterval getCurrentInterval(Register r)

Given that a physical register r is currently allocated to an interval in the active set, return the interval.

findAvailableRegister

Register findAvailableRegister(LinearScan.CompoundInterval ci)

try to find a free physical register to allocate to the compound interval. if no free physical register is found, return null;

findAvailableRegister

Register findAvailableRegister(Register symb)

Try to find a free physical register to allocate to a symbolic register.

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(LinearScan.CompoundInterval ci)

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

Returns:

the preferred register. null if no preference found.

allocateToPhysical

private boolean allocateToPhysical(LinearScan.CompoundInterval i,
                                   Register p)

Check whether it's ok to allocate an interval i to physical register p. If so, return true; If not, return false.

allocateNewSymbolicToPhysical

private boolean allocateNewSymbolicToPhysical(Register symb,
                                              Register p)

Check whether it's ok to allocate symbolic register to a physical register p. If so, return true; If not, return false. NOTE: This routine assumes we're processing the first interval of register symb; so p.isAvailable() is the key information needed.

getSpillCandidate

private LinearScan.CompoundInterval getSpillCandidate(LinearScan.CompoundInterval newInterval)

choose one of the active intervals or the newInterval to spill.

spillMinUnitCost

private LinearScan.CompoundInterval spillMinUnitCost(LinearScan.CompoundInterval newInterval)

Choose the interval with the min unit cost (defined as the number of defs and uses)

checkAssignmentIfSpilled

private boolean checkAssignmentIfSpilled(LinearScan.CompoundInterval i,
                                         LinearScan.CompoundInterval spill)

Check whether, if we spilled interval spill, we could then assign interval i to physical register spill.getRegister().

Returns:

true if the allocation would fit. false otherwise

getBasicInterval

LinearScan.BasicInterval getBasicInterval(Register r,
                                          Instruction s)

Find the basic interval for register r containing instruction s. If there are two such intervals, return the 1st one. If there is none, return null.