org.jikesrvm.compilers.baseline

Class ReferenceMaps

java.lang.Object

org.jikesrvm.compilers.baseline.ReferenceMaps

public final class ReferenceMaps
extends Object

class that provides stack (and local var) map for a baseline compiled method GC uses the methods provided here

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private static class	ReferenceMaps.MergeOperation Kinds of merge operation when merging delta maps into table maps

Field Summary

Fields

Modifier and Type	Field and Description
private static int	BITS_PER_MAP_ELEMENT Number of bits in each map element
private int	bitsPerMap Number of bits in each map
(package private) short[]	byteToBlockMap identify which block a byte is part of
static byte	JSR_INDEX_MASK
static byte	JSR_MASK
private JSRInfo	jsrInfo
static SpinLock	jsrLock Serializes JSR processing
private int	mapCount Number of maps
private int[]	MCSites
static int	NOMORE
private byte[]	referenceMaps
static int	STARTINDEX

Constructor Summary

Constructors

Constructor and Description
ReferenceMaps(BaselineCompiledMethod cm, int[] stackHeights, byte[] localTypes)

Method Summary

Modifier and Type	Method and Description
private int	addUnusualMap(UnusualMaps jsrSiteMap) Add an UnusualMap to the array of unusual maps, expand the array and referencemap array if necessary
private int	bytesPerMap()
void	cleanupPointers() This routine is used to clean out the MethodMap of structures that were allocated from temporary storage.
private UnusualMaps	combineDeltaMaps(int jsrUnusualMapid) Merges unusual maps (occurs in nested jsr conditions) by merging each nested delta map ( as represented by the jsrMapid of the location site) into the jsrInfo.extraUnusualMap where the deltas are accumulated
private byte	convertMapElement(byte[] curBBMap, int offset, int len, byte reftype) Convert a portion of an array word of Bytes into a bitmap of references.
private void	copyBitMap(int extramapindex, int index) Copies a bit map into the extra unusualmap.
private void	finalMergeMaps(int jsrBaseMapIndex, UnusualMaps deltaMap) This method will merge the jsr invoker's base map with changes due to *all* nested jsr subroutines.
(package private) int	findUnusualMap(int mapid) Finds an unsual map with an index greater than 127.
int	getNextJSRAddressIndex(Offset nextMachineCodeOffset, NormalMethod m)
int	getNextJSRRefIndex(int index) Given an offset in the jsr reference map, return the offset where the next returnAddress can be found.
int	getNextJSRReturnAddrIndex(int index) Given an offset in the jsr returnAddress map, return the offset where the next returnAddress can be found.
private int	getNextMapElement()
int	getNextRefIndex(int index, int siteindex)
int	getStackDepth(int mapid)
boolean	isLocalRefType(RVMMethod method, Offset mcoff, int lidx) Query if a local variable has a reference type value
int	locateGCPoint(Offset machCodeOffset, RVMMethod method) Given a machine code instruction offset, return an index to identify the stack map closest to the offset ( but not beyond).
private void	mergeMap(int targetindex, int deltaindex, ReferenceMaps.MergeOperation Op) Merges a delta map into a target map.
void	recordingComplete() Called when all the recording for this map is complete.
void	recordJSRSubroutineMap(int byteindex, byte[] currReferenceMap, int BBLastPtr, int returnAddrIndex, boolean replacemap) Record a map for a point within a JSR Subroutine.
void	recordStkMap(int byteindex, byte[] byteMap, int BBLastPtr, boolean replacemap) Given the information about a GC point, record the information in the proper tables.
private int	scanByte(int bitnum, int bytenum, int toscan, byte[] map) Scans for a reference in a byte.
(package private) int	scanByteArray(byte[] byteMap, int BBLastPtr, byte refType, int mapslot, boolean skipOneBit) Scans the byte array to look for the type of information that was requested.
private int	scanForNextRef(int bitnum, int wordnum, int remaining, byte[] map) Scans the map for the next reference.
int	setupJSRSubroutineMap(int mapid) Setup a map within a JSR Subroutine.
void	showAMap(int MCSiteIndex) Show the basic information for a single map.
void	showInfo() Shows the basic information for each of the maps.
void	showOffsets() Show the offsets for all the maps.
int	showReferenceMapStatistics(RVMMethod method)
int	size()
void	startNewMaps(int gcPointCount, int jsrCount, int parameterWords)
void	translateByte2Machine(int[] b2m) After code is generated, translate the bytecode indices recorded in MCSites array into real machine code offsets.
private void	unusualMapcopy(UnusualMaps from) Makes a deep copy of from into jsrInfo.extraUnusualMap

Methods inherited from class java.lang.Object

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

Field Detail

JSR_MASK

public static final byte JSR_MASK

See Also:

Constant Field Values

JSR_INDEX_MASK

public static final byte JSR_INDEX_MASK

See Also:

Constant Field Values

STARTINDEX

public static final int STARTINDEX

See Also:

Constant Field Values

NOMORE

public static final int NOMORE

See Also:

Constant Field Values

jsrLock

public static final SpinLock jsrLock

Serializes JSR processing

BITS_PER_MAP_ELEMENT

private static final int BITS_PER_MAP_ELEMENT

Number of bits in each map element

See Also:

Constant Field Values

referenceMaps

private byte[] referenceMaps

MCSites

private int[] MCSites

bitsPerMap

private final int bitsPerMap

Number of bits in each map

mapCount

private int mapCount

Number of maps

jsrInfo

private JSRInfo jsrInfo

byteToBlockMap

final short[] byteToBlockMap

identify which block a byte is part of

Constructor Detail

ReferenceMaps

ReferenceMaps(BaselineCompiledMethod cm,
              int[] stackHeights,
              byte[] localTypes)

Method Detail

bytesPerMap

private int bytesPerMap()

Returns:

size of individual maps

locateGCPoint

public int locateGCPoint(Offset machCodeOffset,
                         RVMMethod method)

Given a machine code instruction offset, return an index to identify the stack map closest to the offset ( but not beyond).

Usage note: "machCodeOffset" must point to the instruction *following* the actual instruction whose stack map is sought. This allows us to properly handle the case where the only address we have to work with is a return address (i.e. from a stackframe) or an exception address (i.e. from a null pointer dereference, array bounds check, or divide by zero) on a machine architecture with variable length instructions. In such situations we'd have no idea how far to back up the instruction pointer to point to the "call site" or "exception site".

If the located site is within the scope of a jsr subroutine the index value returned is a negative number.

Parameters:

machCodeOffset - offset into machine code (see above for constraints)

method - the method that contains the gc point

Returns:

index of the appropriate stack map

getNextRefIndex

public int getNextRefIndex(int index,
                           int siteindex)

Parameters:

index - offset in the reference stack frame,

siteindex - index that indicates the callsite (siteindex),

Returns:

return the offset where the next reference can be found, NOMORE when no more pointers can be found

getNextJSRRefIndex

public int getNextJSRRefIndex(int index)

Given an offset in the jsr reference map, return the offset where the next returnAddress can be found.

NOTE: There is only one JSR map for the entire method because it has to be constructed at GC time and would normally require additional storage.

To avoid this, the space for one map is pre-allocated and the map is built in that space. When multiple threads exist and if GC runs in multiple threads concurrently, then the MethodMap must be locked when a JSR map is being scanned. This should be a low probability event.

Parameters:

index - offset in the JSR reference map,

Returns:

The offset where the next reference can be found or NOMORE when no more pointers can be found

getNextJSRReturnAddrIndex

public int getNextJSRReturnAddrIndex(int index)

Given an offset in the jsr returnAddress map, return the offset where the next returnAddress can be found.

NOTE: there is only one jsr returnAddress map for the entire method because it has to be be constructed a GC time and would normally require additional storage. To avoid this, the space for one map is pre-allocated and the map is built in that space. When multiple threads exist and if GC runs in multiple threads concurrently, then the MethodMap must be locked when a jsr map is being scanned. This should be a low probability event.

NOTE: return addresses are handled separately from references because they point inside an object ( internal pointers)

Parameters:

index - offset in the JSR returnAddress map,

Returns:

The offset where the next reference can be found or NOMORE when no more pointers can be found

getStackDepth

public int getStackDepth(int mapid)

size

public int size()

startNewMaps

public void startNewMaps(int gcPointCount,
                         int jsrCount,
                         int parameterWords)

recordStkMap

public void recordStkMap(int byteindex,
                         byte[] byteMap,
                         int BBLastPtr,
                         boolean replacemap)

Given the information about a GC point, record the information in the proper tables.

Parameters:

byteindex - the index in the bytecode of this site

byteMap - a byte array that describes the contents of the local variables and the java stack

BBLastPtr - the last offset of a byte that contains information about the map

replacemap - whether this map is a replacement for a currently existing map

recordJSRSubroutineMap

public void recordJSRSubroutineMap(int byteindex,
                                   byte[] currReferenceMap,
                                   int BBLastPtr,
                                   int returnAddrIndex,
                                   boolean replacemap)

Record a map for a point within a JSR Subroutine. This requires setting up one of the unusual maps.

Parameters:

byteindex - index into the byte code array of the point for the map

currReferenceMap - map of references and return addresses that were set within the JSR Subroutine

BBLastPtr - map runs from -1 to BBLastPtr inclusively

returnAddrIndex - Index in the stack where the return address for the jsr routine (in which this gcpoint is located) can be found

replacemap - false if this is the first time this map point has been recorded.

addUnusualMap

private int addUnusualMap(UnusualMaps jsrSiteMap)

Add an UnusualMap to the array of unusual maps, expand the array and referencemap array if necessary

Parameters:

jsrSiteMap - unusualMap to be added to array

Returns:

number of the added map in the array

setupJSRSubroutineMap

public int setupJSRSubroutineMap(int mapid)

Setup a map within a JSR Subroutine. This requires using up one of the unusual maps. This routine is called when the caller gets a negative mapindex value return from locateGCPoint(org.vmmagic.unboxed.Offset, org.jikesrvm.classloader.RVMMethod). This routine searches the map tables and uses its stack frameAddress input to build reference and returnAddress maps. The caller uses the getNext... routines to scan these maps for offsets in the frame of the related references.

Steps for this routine:

1. use the mapid to get index of the Unusual Map
2. from the unusual map and the frame - get the location of the jsr invoker
3. from the invoker address and the code base address - get the machine code offset from the machine code offset locate the map for that instruction
4. if the invoker was itself in a jsr- merge the delta maps of each jsr and compute the new total delta maps
5. else the invoker was not already in a jsr merge the unusual map differences with the invoker map

Parameters:

mapid - Index of map of instruction where map is required ( this value was returned by locateGCpoint)

Returns:

the index of the JSR invoker

getNextJSRAddressIndex

public int getNextJSRAddressIndex(Offset nextMachineCodeOffset,
                                  NormalMethod m)

recordingComplete

public void recordingComplete()

Called when all the recording for this map is complete. Can now sort or perform other cleanups

translateByte2Machine

public void translateByte2Machine(int[] b2m)

After code is generated, translate the bytecode indices recorded in MCSites array into real machine code offsets.

Parameters:

b2m - map of byte code index to machine code offsets

convertMapElement

private byte convertMapElement(byte[] curBBMap,
                               int offset,
                               int len,
                               byte reftype)

Convert a portion of an array word of Bytes into a bitmap of references.

Parameters:

curBBMap - a byte array that describes the contents of the local variables and the java stack

offset - a starting offset in the array

len - length of the scan, max is BITS_PER_MAP_ELEMENT

reftype - the type of byte to scan for

Returns:

a bitword

getNextMapElement

private int getNextMapElement()

Returns:

next free word in referencemaps for GC call sites

scanForNextRef

private int scanForNextRef(int bitnum,
                           int wordnum,
                           int remaining,
                           byte[] map)

Scans the map for the next reference.

Parameters:

bitnum - starting bitnumber in a map (inclusive)

wordnum - index of the corresponding byte,

remaining - remaining number of bits in the map,

map - map to search

Returns:

TODO document me

scanByte

private int scanByte(int bitnum,
                     int bytenum,
                     int toscan,
                     byte[] map)

Scans for a reference in a byte.

Parameters:

bitnum - bitnumber in the map

bytenum - index of the corresponding map byte

toscan - the remaining number of bits in the byte,

map - the map

Returns:

next ref in the byte or zero if not found

scanByteArray

int scanByteArray(byte[] byteMap,
                  int BBLastPtr,
                  byte refType,
                  int mapslot,
                  boolean skipOneBit)

Scans the byte array to look for the type of information that was requested. Builds a bit array in the stack maps with the information.

Parameters:

byteMap - bytearray where each byte describes the corresponding word on a stack

BBLastPtr - length of the byte array

refType - type of information that is to be scanned

mapslot - slot where map should be stored, 0 for next free slot

skipOneBit - should a bit in the bitarray be skipped? Necessary for setRef and setNonRef maps so so they are properly merged with jsr base maps.

Returns:

index of the map in the reference map

unusualMapcopy

private void unusualMapcopy(UnusualMaps from)

Makes a deep copy of from into jsrInfo.extraUnusualMap

Parameters:

from - the map to copy from

copyBitMap

private void copyBitMap(int extramapindex,
                        int index)

Copies a bit map into the extra unusualmap.

Parameters:

extramapindex - the index of the map in the jsrInfo.extraUnusualMap ie the "to" map

index - he index of the map to copy ie the "from" map

combineDeltaMaps

private UnusualMaps combineDeltaMaps(int jsrUnusualMapid)

Merges unusual maps (occurs in nested jsr conditions) by merging each nested delta map ( as represented by the jsrMapid of the location site) into the jsrInfo.extraUnusualMap where the deltas are accumulated

Parameters:

jsrUnusualMapid - the delta map's id

Returns:

merged map

mergeMap

private void mergeMap(int targetindex,
                      int deltaindex,
                      ReferenceMaps.MergeOperation Op)

Merges a delta map into a target map.

Parameters:

targetindex - the delta map's index in the reference map table

deltaindex - the target map's index in the reference map tbale

Op - the merge operation to use

finalMergeMaps

private void finalMergeMaps(int jsrBaseMapIndex,
                            UnusualMaps deltaMap)

This method will merge the jsr invoker's base map with changes due to *all* nested jsr subroutines.

The nested jsr subroutine maps were merged into a single delta map prior to the calling of this method. We therefore know that the base map can never be due to a subroutine (since all subroutines have been merged), and therefore that there are no return address maps due to the invoker (since return addresses are only due to the subroutine maps).

Parameters:

jsrBaseMapIndex - The map index for the invoker

deltaMap - The map for the invoked subroutine/s (all nested subroutine maps are guaranteed to have been combined prior to calling this)

cleanupPointers

public void cleanupPointers()

This routine is used to clean out the MethodMap of structures that were allocated from temporary storage. Temporary storage is freed up between stack frames as the GC scans the stack.

findUnusualMap

int findUnusualMap(int mapid)

Finds an unsual map with an index greater than 127. It returns the index by doing a sequential scan and looking for the mapid in the normal map directory.

Parameters:

mapid - the map's id

Returns:

the map's index

showInfo

public void showInfo()

Shows the basic information for each of the maps. This is for testing use.

showAMap

public void showAMap(int MCSiteIndex)

Show the basic information for a single map. This is for testing use.

Parameters:

MCSiteIndex - index of the machine code site

showOffsets

public void showOffsets()

Show the offsets for all the maps. This is for test use.

showReferenceMapStatistics

public int showReferenceMapStatistics(RVMMethod method)

isLocalRefType

public boolean isLocalRefType(RVMMethod method,
                              Offset mcoff,
                              int lidx)

Query if a local variable has a reference type value

Parameters:

method - The method we're asking about.

mcoff - The machine code offset of the instruction *following* the actual instruction.

lidx - the local index

Returns:

true, if it is a reference type. false, otherwise