org.jikesrvm.compilers.opt.regalloc

Class CompoundInterval

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.IncreasingStartIntervalSet

org.jikesrvm.compilers.opt.regalloc.CompoundInterval

All Implemented Interfaces:

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

Direct Known Subclasses:

SpillLocationInterval

class CompoundInterval
extends IncreasingStartIntervalSet

Implements a live interval with holes; i.e. an ordered set of basic live intervals. There is exactly one instance of this class for each Register.

The order that this set imposes is inconsistent with equals.

This class is designed for use by a single thread.

Field Summary

Fields

Modifier and Type	Field and Description
private boolean	_infrequent Is this compound interval fully contained in infrequent code?
private Register	reg The register this compound interval represents or null if this interval is not associated with a register (i.e. if it represents a spill location).
(package private) static long	serialVersionUID Support for Set serialization
private SpillLocationInterval	spillInterval A spill location assigned for this interval.

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

c

Constructor Summary

Constructors

Modifier	Constructor and Description
(package private)	CompoundInterval(BasicInterval i, Register register) Creates a new compound interval of a single Basic interval.
(package private)	CompoundInterval(int dfnBegin, int dfnEnd, Register register) Creates a new compound interval of a single Basic interval.
protected	CompoundInterval(Register r) Dangerous constructor: use with care.

Method Summary

Modifier and Type	Method and Description
(package private) void	addNonIntersectingInterval(CompoundInterval i, BasicInterval stop) Merges this interval with another, non-intersecting interval.
(package private) BasicInterval	addRange(RegisterAllocatorState regAllocState, LiveIntervalElement live, BasicBlock bb) Add a new live range to this compound interval.
(package private) void	assign(Register r) Assign this compound interval to a physical register.
(package private) CompoundInterval	copy(Register r) Copies the ranges from this interval into a new interval associated with a register.
(package private) CompoundInterval	copy(Register r, BasicInterval stop) Copies the basic intervals up to and including stop into a new interval.
(package private) Register	getAssignment(RegisterAllocatorState regAllocState)
(package private) BasicInterval	getBasicInterval(int n)
(package private) BasicInterval	getBasicInterval(RegisterAllocatorState dfnNumbers, Instruction s)
(package private) int	getLowerBound()
(package private) Register	getRegister()
(package private) SpillLocationInterval	getSpillInterval()
(package private) int	getUpperBound()
(package private) SortedSet<BasicInterval>	headSetInclusive(BasicInterval upperBound) Computes the headSet() [from java.util.SortedSet] but includes all elements less than upperBound inclusive.
(package private) SortedSet<BasicInterval>	headSetInclusive(int upperBound) Computes the headSet() [from java.util.SortedSet] but includes all elements less than upperBound inclusive.
(package private) boolean	intersects(CompoundInterval i)
(package private) boolean	isAssigned(RegisterAllocatorState regAllocState)
(package private) boolean	isInfrequent()
(package private) boolean	isSpilled(RegisterAllocatorState regAllocState)
(package private) CompoundInterval	removeIntervalsAndCache(CompoundInterval other) Removes some basic intervals from this compound interval, and returns the intervals actually removed.
(package private) void	setFrequent()
private boolean	shouldConcatenate(RegisterAllocatorState regAllocState, LiveIntervalElement live, BasicBlock bb) Should we simply merge the live interval live into a previous BasicInterval?
(package private) void	spill(SpillLocationManager spillManager, RegisterAllocatorState regAllocState) Assign this compound interval to a free spill location.
(package private) SortedSet<BasicInterval>	tailSetInclusive(int lowerBound) Computes the tailSet() [from java.util.SortedSet] but includes all elements greater than lowerBound inclusive.
String	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

_infrequent

private boolean _infrequent

Is this compound interval fully contained in infrequent code?

reg

private final Register reg

The register this compound interval represents or null if this interval is not associated with a register (i.e. if it represents a spill location).

spillInterval

private SpillLocationInterval spillInterval

A spill location assigned for this interval.

Constructor Detail

CompoundInterval

CompoundInterval(int dfnBegin,
                 int dfnEnd,
                 Register register)

Creates a new compound interval of a single Basic interval.

Parameters:

dfnBegin - interval's begin

dfnEnd - interval's end

register - the register for the compound interval

CompoundInterval

CompoundInterval(BasicInterval i,
                 Register register)

Creates a new compound interval of a single Basic interval.

Parameters:

i - interval providing start and end for the new interval

register - the register for the compound interval

CompoundInterval

protected CompoundInterval(Register r)

Dangerous constructor: use with care.

Creates a compound interval with a register but doesn't actually add any intervals to the compound interval.

Parameters:

r - a register

Method Detail

setFrequent

final void setFrequent()

isInfrequent

final boolean isInfrequent()

getSpillInterval

SpillLocationInterval getSpillInterval()

getRegister

Register getRegister()

Returns:

the register this interval represents

copy

CompoundInterval copy(Register r)

Copies the ranges from this interval into a new interval associated with a register.

Parameters:

r - the register for the new interval

Returns:

the new interval

copy

CompoundInterval copy(Register r,
                      BasicInterval stop)

Copies the basic intervals up to and including stop into a new interval. The new interval is associated with the given register.

Parameters:

r - the register for the new interval

stop - the interval to stop at

Returns:

the new interval

addRange

BasicInterval addRange(RegisterAllocatorState regAllocState,
                       LiveIntervalElement live,
                       BasicBlock bb)

Add a new live range to this compound interval.

Parameters:

regAllocState - depth-first numbers for for instructions

live - the new live range

bb - the basic block for live

Returns:

the new basic interval if one was created; null otherwise

shouldConcatenate

private boolean shouldConcatenate(RegisterAllocatorState regAllocState,
                                  LiveIntervalElement live,
                                  BasicBlock bb)

Should we simply merge the live interval live into a previous BasicInterval?

Parameters:

regAllocState - depth-first numbers for for instructions

live - the live interval being queried

bb - the basic block in which live resides.

Returns:

true if the interval should be concatenated, false if it should'nt

spill

void spill(SpillLocationManager spillManager,
           RegisterAllocatorState regAllocState)

Assign this compound interval to a free spill location.

Parameters:

spillManager - governing spill location manager

regAllocState - current state of the register allocator

isSpilled

boolean isSpilled(RegisterAllocatorState regAllocState)

assign

void assign(Register r)

Assign this compound interval to a physical register.

Parameters:

r - the register to assign to

isAssigned

boolean isAssigned(RegisterAllocatorState regAllocState)

Parameters:

regAllocState - current state of the register allocator

Returns:

true if this interval has been assigned to a physical register

getAssignment

Register getAssignment(RegisterAllocatorState regAllocState)

Parameters:

regAllocState - current state of the register allocator

Returns:

the physical register this interval is assigned to, null if none assigned

addNonIntersectingInterval

void addNonIntersectingInterval(CompoundInterval i,
                                BasicInterval stop)

Merges this interval with another, non-intersecting interval.

Precondition: BasicInterval stop is an interval in i. This version will only merge basic intervals up to and including stop into this.

Parameters:

i - a non-intersecting interval for merging

stop - a interval to stop at

headSetInclusive

SortedSet<BasicInterval> headSetInclusive(BasicInterval upperBound)

Computes the headSet() [from java.util.SortedSet] but includes all elements less than upperBound inclusive.

Parameters:

upperBound - the interval acting as upper bound

Returns:

the head set

See Also:

SortedSet.headSet(Object)

headSetInclusive

SortedSet<BasicInterval> headSetInclusive(int upperBound)

Computes the headSet() [from java.util.SortedSet] but includes all elements less than upperBound inclusive.

Parameters:

upperBound - the instruction number acting as upper bound

Returns:

the head set

See Also:

SortedSet.headSet(Object)

tailSetInclusive

SortedSet<BasicInterval> tailSetInclusive(int lowerBound)

Computes the tailSet() [from java.util.SortedSet] but includes all elements greater than lowerBound inclusive.

Parameters:

lowerBound - the instruction number acting as lower bound

Returns:

the tail set

See Also:

SortedSet.tailSet(Object)

removeIntervalsAndCache

CompoundInterval removeIntervalsAndCache(CompoundInterval other)

Removes some basic intervals from this compound interval, and returns the intervals actually removed.

PRECONDITION: All basic intervals in the other interval that have the same begin as an interval in this compound interval must have the same end. For example, for a compound interval [(1,2)(2,3)], the other interval would be allowed to contain (1,2) and/or (2,2) but not (1,3).

A violation of the precondition that would have an effect will trigger an assertion failure in assertion-enabled builds.

Parameters:

other - interval to check for intervals that we want to remove from this

Returns:

the basic intervals that were removed

getLowerBound

int getLowerBound()

Returns:

the lowest DFN in this compound interval at this time

getUpperBound

int getUpperBound()

Returns:

the highest DFN in this compound interval at this time

intersects

boolean intersects(CompoundInterval i)

getBasicInterval

BasicInterval getBasicInterval(RegisterAllocatorState dfnNumbers,
                               Instruction s)

Parameters:

dfnNumbers - depth-first numbers for for instructions

s - The instruction in question

Returns:

the first basic interval that contains a given instruction, null if there is no such interval

getBasicInterval

BasicInterval getBasicInterval(int n)

Parameters:

n - The DFN of the instruction in question

Returns:

the first basic interval that contains a given instruction, null if there is no such interval

toString

public String toString()

Overrides:

toString in class IntervalSet