org.jikesrvm.compilers.opt.bc2ir

Class BBSet

java.lang.Object

org.jikesrvm.compilers.opt.bc2ir.BBSet

final class BBSet
extends Object

Encapsulates the discovery and maintenance of the set of basic blocks that are being generated during construction of the IR.

The backing data store is a red/black tree, but there are a number of very specialized operations that are performed during search/insertion so we roll our own instead of using one from the standard library.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private static class	BBSet.TreeEnumerator

Field Summary

Fields

Modifier and Type	Field and Description
private BytecodeStream	bcodes associated bytecodes
private int[]	endPCs End bytecode index for each exception handler range
private BasicBlockLE	entry entry block of the CFG
private TypeOperand[]	exceptionTypes Type of exception handled by each exception handler range.
private GenerationContext	gc associated generation context
private int[]	handlerPCs Start bytecode index of each the exception handler
private boolean	noJSR is it the case that we can ignore JSR processing because BC2IR has not yet generated a JSR bytecode in this method?
private BasicBlockLE	root root of the backing red/black tree
private int[]	startPCs Start bytecode index for each exception handler ranges

Constructor Summary

Constructors

Constructor and Description
BBSet(GenerationContext gc, BytecodeStream bcodes, Operand[] localState) Initialize the BBSet to handle basic block generation for the argument generation context and bytecode info.

Method Summary

Modifier and Type	Method and Description
private BasicBlockLE	_createBBLE(int bcIndex, Operand[] simLocals, BasicBlockLE parent, boolean left) Allocate a new BBLE at the given bcIndex.
private BasicBlockLE	condCreateAndInit(BasicBlockLE x, boolean shouldCreate, int target, BasicBlockLE from, OperandStack simStack, Operand[] simLocals, boolean left) Conditionally create a block at the specified target as a child of x.
(package private) Enumeration<BasicBlockLE>	contents()
private int	countBlack(BasicBlockLE node)
private void	db(String val) Print a debug string to the sysWrite stream.
private int	exceptionEndRange(int bcIndex) Given a starting bytecode index, find the greatest bcIndex that is still has the same inscope exception handlers.
(package private) void	finalPass(boolean inlinedSomething) Do a final pass over the generated basic blocks to create the initial code ordering.
private void	fixupBBSet(BasicBlockLE x) Performs tree fixup (restore Red/Black invariants) after adding a new node to the tree.
(package private) BasicBlockLE	getEntry()
(package private) int	getNextBlockBytecodeIndex(BasicBlockLE x) Gets the bytecode index of the block in the set which has the next-higher bytecode index.
(package private) BasicBlockLE	getNextEmptyBlock(BasicBlockLE start) Finds the next ungenerated block, starting at the argument block and searching forward, wrapping around to the beginning.
private BasicBlockLE	getOrCreateBlock(BasicBlockLE x, boolean shouldCreate, int target, BasicBlockLE from, OperandStack simStack, Operand[] simLocals) Get or create a block at the specified target.
(package private) BasicBlockLE	getOrCreateBlock(int target, BasicBlockLE from, OperandStack simStack, Operand[] simLocals) Get or create a block at the specified target.
private BasicBlockLE	getSuccessor(BasicBlockLE x, int value) Returns the basic block's sucessor in bytecode sequence.
private void	initializeExceptionHandlers(BasicBlockLE bble, Operand[] simLocals) Initialize bble's handlers array based on startPCs/endPCs.
private void	injectMove(BasicBlock block, RegisterOperand res, Operand val)
private void	leftRotateBBSet(BasicBlockLE x)
private void	markBlockForRegeneration(BasicBlockLE p) Mark a previously generated block for regeneration.
private boolean	matchingJSRcontext(OperandStack simStack, Operand[] simLocals, BasicBlockLE candBBLE) We specialize basic blocks with respect to the return addresses they have on their expression stack and/or in their local variables on entry to the block.
private BasicBlockLE	minimumBB(BasicBlockLE x, int value)
private void	parseExceptionTables() Initializes the global exception handler arrays for the method.
(package private) void	rectifyLocals(Operand[] localState, BasicBlockLE p) Rectify the given local variable state with the local variable state stored in the given BBLE.
(package private) void	rectifyStacks(BasicBlock block, OperandStack stack, BasicBlockLE p) Rectify the given stack state with the state contained in the given BBLE, adding the necessary move instructions to the end of the given basic block to make register numbers agree and rectify mis-matched constants.
private void	rightRotateBBSet(BasicBlockLE x)
(package private) void	seenJSR() Notify the BBSet that BC2IR has encountered a JSR bytecode.
private void	treeInsert(BasicBlockLE parent, BasicBlockLE newBBLE, boolean left) Insert newBBLE as a child of parent in our Red/Black tree.
private void	verifyTree()
private void	verifyTree(BasicBlockLE node, int min, int max)

Methods inherited from class java.lang.Object

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

Field Detail

root

private BasicBlockLE root

root of the backing red/black tree

noJSR

private boolean noJSR

is it the case that we can ignore JSR processing because BC2IR has not yet generated a JSR bytecode in this method?

entry

private final BasicBlockLE entry

entry block of the CFG

gc

private final GenerationContext gc

associated generation context

bcodes

private final BytecodeStream bcodes

associated bytecodes

startPCs

private int[] startPCs

Start bytecode index for each exception handler ranges

endPCs

private int[] endPCs

End bytecode index for each exception handler range

handlerPCs

private int[] handlerPCs

Start bytecode index of each the exception handler

exceptionTypes

private TypeOperand[] exceptionTypes

Type of exception handled by each exception handler range.

Constructor Detail

BBSet

BBSet(GenerationContext gc,
      BytecodeStream bcodes,
      Operand[] localState)

Initialize the BBSet to handle basic block generation for the argument generation context and bytecode info.

Parameters:

gc - the generation context to generate blocks for

bcodes - the bytecodes of said generation context

localState - the state of the local variables for the block beginning at bytecode 0.

Method Detail

getEntry

BasicBlockLE getEntry()

seenJSR

void seenJSR()

Notify the BBSet that BC2IR has encountered a JSR bytecode. This enables more complex logic in getOrCreateBlock to drive the basic block specialization that is the key to JSR inlining.

contents

Enumeration<BasicBlockLE> contents()

Returns:

a enumeration of the BasicBlockLE's currently in the BBSet

getNextBlockBytecodeIndex

int getNextBlockBytecodeIndex(BasicBlockLE x)

Gets the bytecode index of the block in the set which has the next-higher bytecode index.

Parameters:

x - basic block to start at.

Returns:

the bytecode index of the block in the set with the next-higher bytecode index. If x is currently the block with the highest starting bytecode index, return bcodes.length().

getNextEmptyBlock

BasicBlockLE getNextEmptyBlock(BasicBlockLE start)

Finds the next ungenerated block, starting at the argument block and searching forward, wrapping around to the beginning.

Parameters:

start - the basic block at which to start looking.

Returns:

null if all blocks are generated, the next ungenerated block otherwise

getOrCreateBlock

BasicBlockLE getOrCreateBlock(int target,
                              BasicBlockLE from,
                              OperandStack simStack,
                              Operand[] simLocals)

Get or create a block at the specified target. If simStack is non-null, rectifies stack state with target stack state. If simLocals is non-null, rectifies local state with target local state. Any instructions needed to rectify stack/local state are appended to from.

Parameters:

target - target index

from - the block from which control is being transfered and to which rectification instructions are added.

simStack - stack state to rectify, or null

simLocals - local state to rectify, or null

Returns:

a block, never null

markBlockForRegeneration

private void markBlockForRegeneration(BasicBlockLE p)

Mark a previously generated block for regeneration. We define this method here so that in the future we can implement a more efficient getNextEmptyBlock that (1) avoids generating lots of blocks when a CFG predecessor has a pending regeneration and (2) avoids the scan through all blocks when there are no more blocks left to generate.

Parameters:

p - the block to mark for regeneration

rectifyStacks

void rectifyStacks(BasicBlock block,
                   OperandStack stack,
                   BasicBlockLE p)

Rectify the given stack state with the state contained in the given BBLE, adding the necessary move instructions to the end of the given basic block to make register numbers agree and rectify mis-matched constants.

Parameters:

block - basic block to append move instructions to

stack - stack to copy

p - BBLE to copy stack state into

injectMove

private void injectMove(BasicBlock block,
                        RegisterOperand res,
                        Operand val)

rectifyLocals

void rectifyLocals(Operand[] localState,
                   BasicBlockLE p)

Rectify the given local variable state with the local variable state stored in the given BBLE.

Parameters:

localState - local variable state to rectify

p - target BBLE to rectify state to

finalPass

void finalPass(boolean inlinedSomething)

Do a final pass over the generated basic blocks to create the initial code ordering. All blocks generated for the method will be inserted after gc.prologue.

NOTE: Only some CFG edges are created here..... we're mainly just patching together a code linearization.

Parameters:

inlinedSomething - was a normal method (i.e. non-magic) inlined?

db

private void db(String val)

Print a debug string to the sysWrite stream.

Parameters:

val - string to print

parseExceptionTables

private void parseExceptionTables()

Initializes the global exception handler arrays for the method.

initializeExceptionHandlers

private void initializeExceptionHandlers(BasicBlockLE bble,
                                         Operand[] simLocals)

Initialize bble's handlers array based on startPCs/endPCs. In the process, new HandlerBlockLE's may be created (by the call to getOrCreateBlock).

PRECONDITION: bble.low and bble.max have already been correctly set to reflect the invariant that a basic block is in exactly one "handler range."

Also initializes bble.block.exceptionHandlers.

Parameters:

bble - the block whose handlers are to be initialized

simLocals - local variables

exceptionEndRange

private int exceptionEndRange(int bcIndex)

Given a starting bytecode index, find the greatest bcIndex that is still has the same inscope exception handlers.

Parameters:

bcIndex - the start bytecode index

Returns:

greatest bytecode index with the same in scope exception handlers

matchingJSRcontext

private boolean matchingJSRcontext(OperandStack simStack,
                                   Operand[] simLocals,
                                   BasicBlockLE candBBLE)

We specialize basic blocks with respect to the return addresses they have on their expression stack and/or in their local variables on entry to the block. This has the effect of inlining the subroutine body at all of the JSR sites that invoke it. This is the key routine: it determines whether or not the argument simState (stack and locals) contains compatible return addresses as the candidate BasicBlockLE.

The main motivation for inlining away all JSR's is that it eliminates the "JSR problem" for type accurate GC. It is also simpler to implement and arguably results in more efficient generated code (assuming that we don't get horrific code bloat). To deal with the code bloat, we detect excessive code duplication and stop IR generation (bail out to the baseline compiler).

Parameters:

simStack - The expression stack to match

simLocals - The local variables to match

candBBLE - The candidate BaseicBlockLE

Returns:

true if and only if a matching JSR context (see above) was found

getOrCreateBlock

private BasicBlockLE getOrCreateBlock(BasicBlockLE x,
                                      boolean shouldCreate,
                                      int target,
                                      BasicBlockLE from,
                                      OperandStack simStack,
                                      Operand[] simLocals)

Get or create a block at the specified target. If simStack is non-null, rectifies stack state with target stack state. If simLocals is non-null, rectifies local state with target local state. Any instructions needed to rectify stack/local state are appended to from. As blocks are created, they are added to the red/black tree below x.

Parameters:

x - starting node for search.

shouldCreate - should we create the block if we run off the tree?

target - target index

from - the block from which control is being transfered and to which rectification instructions are added.

simStack - stack state to rectify, or null

simLocals - local state to rectify, or null

Returns:

a new block, never null

condCreateAndInit

private BasicBlockLE condCreateAndInit(BasicBlockLE x,
                                       boolean shouldCreate,
                                       int target,
                                       BasicBlockLE from,
                                       OperandStack simStack,
                                       Operand[] simLocals,
                                       boolean left)

Conditionally create a block at the specified target as a child of x. If simStack is non-null, rectifies stack state with target stack state. If simLocals is non-null, rectifies local state with target local state. Any instructions needed to rectify stack/local state are appended to from.

Parameters:

x - starting node for search.

shouldCreate - should we create the block if we run off the tree?

target - target index

from - the block from which control is being transfered and to which rectification instructions are added.

simStack - stack state to rectify, or null

simLocals - local state to rectify, or null

left - are we creating a left child of parent?

Returns:

the newly created block, or null if !shouldCreate

_createBBLE

private BasicBlockLE _createBBLE(int bcIndex,
                                 Operand[] simLocals,
                                 BasicBlockLE parent,
                                 boolean left)

Allocate a new BBLE at the given bcIndex. If bcIndex is the start of an handler block, then a HandlerBlockLE is created. After the BBLE is created, its handlers data structure is initialized (which may cause other blocks to be created).

Parameters:

bcIndex - the bytecode index at which the block should be created.

simLocals - the localState to pass (via initializeExceptionHandler)to to getOrCreateBlock if we need to create BBLEs for exception handlers. This is only actually used if !noJSR. We don't need the expression stack, since the only thing on the expression stack on entry to a handler block is the exception object (and thus we can skip scanning the expression stack for return addresses when creating a handler block).

parent - parent in Red/Black tree

left - are we creating a left child of parent?

Returns:

a new BBLE

getSuccessor

private BasicBlockLE getSuccessor(BasicBlockLE x,
                                  int value)

Returns the basic block's sucessor in bytecode sequence.

Parameters:

x - basic block at which to start the search for a higher block

value - the contents of x.low (makes tail call elim work better if we avoid the obvious 1 argument wrapper function)

Returns:

null if x is the block with the highest bytecode index, the block with the next-higher bytecode index otherwise.

minimumBB

private BasicBlockLE minimumBB(BasicBlockLE x,
                               int value)

treeInsert

private void treeInsert(BasicBlockLE parent,
                        BasicBlockLE newBBLE,
                        boolean left)

Insert newBBLE as a child of parent in our Red/Black tree.

Parameters:

parent - the parent node

newBBLE - the new child node

left - is the child the left or right child of parent?

fixupBBSet

private void fixupBBSet(BasicBlockLE x)

Performs tree fixup (restore Red/Black invariants) after adding a new node to the tree.

Parameters:

x - node that was added.

leftRotateBBSet

private void leftRotateBBSet(BasicBlockLE x)

rightRotateBBSet

private void rightRotateBBSet(BasicBlockLE x)

verifyTree

private void verifyTree()

verifyTree

private void verifyTree(BasicBlockLE node,
                        int min,
                        int max)

countBlack

private int countBlack(BasicBlockLE node)