org.jikesrvm.compilers.opt.bc2ir
Class BBSet

java.lang.Object
  org.jikesrvm.compilers.opt.bc2ir.BBSet

All Implemented Interfaces:

IRGenOptions

final class BBSet
extends Object
implements IRGenOptions

A somewhat complex subtask of IR generation is to discover and maintain the set of basic blocks that are being generated. This class encapsulates that functionality. 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.

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.

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.

getEntry

BasicBlockLE getEntry()

return the entry BBLE

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()

Return 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. Returns bcodes.length() if x is currently the block with the highest starting bytecode index.

Parameters:

x - basic block to start at.

getNextEmptyBlock

BasicBlockLE getNextEmptyBlock(BasicBlockLE start)

Finds the next ungenerated block, starting at the argument block and searching forward, wrapping around to the beginning. If all blocks are generated, it returns null.

Parameters:

start - the basic block at which to start looking.

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

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.

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.

db

private void db(String val)

Print a debug string to the sysWrite stream.

Parameters:

val - string to print

parseExceptionTables

private void parseExceptionTables()

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

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

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

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

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?

getSuccessor

private BasicBlockLE getSuccessor(BasicBlockLE x,
                                  int value)

Returns the basic block which has the next-higher bytecode index. Returns null if x is the highest block.

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)

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)