org.jikesrvm.adaptive.recompilation.instrumentation

Class InstrumentationSamplingFramework

java.lang.Object

org.jikesrvm.compilers.opt.driver.CompilerPhase

org.jikesrvm.adaptive.recompilation.instrumentation.InstrumentationSamplingFramework

public final class InstrumentationSamplingFramework
extends CompilerPhase

Transforms the method so that instrumentation is sampled, rather than executed exhaustively. Includes both the full-duplication and no-duplication variations. See Arnold-Ryder PLDI 2001, and the section 4.1 of Arnold's PhD thesis.

NOTE: This implementation uses yieldpoints to denote where checks should be placed (to transfer control into instrumented code). It is currently assumed that these are on method entries and backedges. When optimized yieldpoint placement exists either a) it should be turned off when using this phase, or b) this phase should detect its own check locations.

To avoid the complexity of duplicating exception handler maps, exception handler blocks are split and a check at the top of the handler. Thus exceptions from both the checking and duplicated code are handled by the same catch block, however the check at the top of the catch block ensures that the hander code has the opportunity to be sampled.

Field Summary

Fields

Modifier and Type	Field and Description
private RegisterOperand	cbsReg Temporary variables
private static Constructor<CompilerPhase>	constructor Constructor for this compiler phase
private static boolean	DEBUG These are local copies of optimizing compiler debug options that can be set via the command line arguments.
private static boolean	DEBUG2

Fields inherited from class org.jikesrvm.compilers.opt.driver.CompilerPhase

container

Constructor Summary

Constructors

Constructor and Description
InstrumentationSamplingFramework()

Method Summary

Modifier and Type	Method and Description
private static void	adjustPointersInDuplicatedCode(IR ir, HashMap<BasicBlock,BasicBlock> origToDupMap) Go through all blocks in duplicated code and adjust the edges as follows: All edges (in duplicated code) that go into a block with a yieldpoint must jump to back to the original code.
private void	appendLoad(BasicBlock bb, IR ir) Append a load of the global counter to the given basic block.
private void	cleanUp(IR ir) Cleans up the IR after the transformation is applied.
private void	conditionalizeInstrumentationOperation(IR ir, Instruction i, BasicBlock bb) Take an instrumentation operation (an instruction) and guard it with a counter-based check.
private void	createCheck(BasicBlock checkBB, BasicBlock noInstBB, BasicBlock instBB, boolean fallthroughToInstBB, IR ir) Append a check to a basic block, and make it jump to the right places.
static void	dumpCFG(IR ir)
private void	duplicateCode(IR ir, HashMap<BasicBlock,BasicBlock> origToDupMap, HashSet<BasicBlock> exceptionHandlerBlocks) Make a duplicate of all basic blocks down at the bottom of the code order.
Constructor<CompilerPhase>	getClassConstructor() Get a constructor object for this compiler phase
private static Instruction	getFirstInstWithOperator(Operator operator, BasicBlock bb) Go through all instructions and find the first with the given operator.
static Instruction	getFirstInstWithYieldPoint(BasicBlock bb) Go through all instructions and find one that is a yield point
String	getName()
private static RegisterOperand	getOrCreateDupReg(RegisterOperand ro, IR ir, Map<Register,Register> dupMappings) The given register a) does not span multiple basic block, and b) is used in a basic block that is being duplicated.
private void	insertCBSChecks(IR ir, HashMap<BasicBlock,BasicBlock> origToDupMap, HashSet<BasicBlock> exceptionHandlerBlocks) In the checking code, insert CBS checks at each yieldpoint, to transfer code into the duplicated (instrumented) code.
private static boolean	isInstrumentationInstruction(Instruction i) How to determine whether a given instruction is an "instrumentation instruction".
static boolean	isYieldpoint(Instruction i) Is the given instruction a yieldpoint?
private static BasicBlock	myCopyWithoutLinks(BasicBlock bb, IR ir) The same as BasicBlock.copyWithoutLinks except that it renames all temp variables that are never used outside the basic block.
void	perform(IR ir) This is the method that actually does the work of the phase.
private void	performVariationFullDuplication(IR ir) Perform the full duplication algorithm
private void	performVariationNoDuplication(IR ir) Perform the NoDuplication version of the framework (see Arnold-Ryder PLDI 2001).
private void	prependCounterReset(BasicBlock bb, IR ir) Prepend the code to reset the global counter to the given basic block.
private void	prependDecrement(BasicBlock bb, IR ir) Append a decrement of the global counter to the given basic block.
private void	prependStore(BasicBlock bb, IR ir) Append a store of the global counter to the given basic block.
private static void	removeInstrumentationFromOrig(IR ir, HashMap<BasicBlock,BasicBlock> origToDupMap) Remove instrumentation from the original version of all duplicated basic blocks.
boolean	shouldPerform(OptOptions options) This method determines if the phase should be run, based on the Options object it is passed.
private static void	updateTemps(BasicBlock bb, IR ir) Given an basic block, rename all of the temporary registers that are local to the block.

Methods inherited from class org.jikesrvm.compilers.opt.driver.CompilerPhase

dumpIR, dumpIR, getCompilerPhaseConstructor, getCompilerPhaseConstructor, newExecution, performPhase, printingEnabled, reportAdditionalStats, setContainer, verify

Methods inherited from class java.lang.Object

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

Field Detail

DEBUG

private static boolean DEBUG

These are local copies of optimizing compiler debug options that can be set via the command line arguments.

DEBUG2

private static boolean DEBUG2

cbsReg

private RegisterOperand cbsReg

Temporary variables

constructor

private static final Constructor<CompilerPhase> constructor

Constructor for this compiler phase

Constructor Detail

InstrumentationSamplingFramework

public InstrumentationSamplingFramework()

Method Detail

getClassConstructor

public Constructor<CompilerPhase> getClassConstructor()

Get a constructor object for this compiler phase

Overrides:

getClassConstructor in class CompilerPhase

Returns:

compiler phase constructor

shouldPerform

public boolean shouldPerform(OptOptions options)

Description copied from class: CompilerPhase

This method determines if the phase should be run, based on the Options object it is passed. By default, phases are always performed. Subclasses should override this method if they only want to be performed conditionally.

Overrides:

shouldPerform in class CompilerPhase

Parameters:

options - the compiler options for the compilation

Returns:

true if the phase should be performed

getName

public String getName()

Specified by:

getName in class CompilerPhase

Returns:

a String which is the name of the phase.

perform

public void perform(IR ir)

Description copied from class: CompilerPhase

This is the method that actually does the work of the phase.

Specified by:

perform in class CompilerPhase

Parameters:

ir - the IR on which to apply the phase

cleanUp

private void cleanUp(IR ir)

Cleans up the IR after the transformation is applied.

Parameters:

ir - the IR to clean up

performVariationFullDuplication

private void performVariationFullDuplication(IR ir)

Perform the full duplication algorithm

Parameters:

ir - the governing IR

duplicateCode

private void duplicateCode(IR ir,
                           HashMap<BasicBlock,BasicBlock> origToDupMap,
                           HashSet<BasicBlock> exceptionHandlerBlocks)

Make a duplicate of all basic blocks down at the bottom of the code order. For now, this is done in a slightly ackward way. After duplication, the control flow within the duplicated code is not complete because each block immediately transfers you back to the original code. This gets fixed in adjustPointersInDuplicatedCode

Parameters:

ir - the governing IR

origToDupMap - a map (initially empty) that will store the mapping of original blocks to their duplicates

exceptionHandlerBlocks - a set that (initially empty) that is used to remember the exception handlers. Those need to be known because they need special checks (see insertCBSChecks(IR, HashMap, HashSet).

insertCBSChecks

private void insertCBSChecks(IR ir,
                             HashMap<BasicBlock,BasicBlock> origToDupMap,
                             HashSet<BasicBlock> exceptionHandlerBlocks)

In the checking code, insert CBS checks at each yieldpoint, to transfer code into the duplicated (instrumented) code. For now, checks are inserted at all yieldpoints (See comment at top of file).

Parameters:

ir - the governing IR

origToDupMap - a mapping of baisc block blocks to their duplicates

exceptionHandlerBlocks - a set that of exception handler basic blocks

createCheck

private void createCheck(BasicBlock checkBB,
                         BasicBlock noInstBB,
                         BasicBlock instBB,
                         boolean fallthroughToInstBB,
                         IR ir)

Append a check to a basic block, and make it jump to the right places.

Parameters:

checkBB - The block to append the CBS check to.

noInstBB - The basic block to jump to if the CBS check fails

instBB - The basicBlock to jump to if the CBS check succeeds

fallthroughToInstBB - Should checkBB fallthrough to instBB (otherwise it must fallthrough to noInstBB)

ir - the IR that contains the blocks

appendLoad

private void appendLoad(BasicBlock bb,
                        IR ir)

Append a load of the global counter to the given basic block. WARNING: Tested for LIR only!

Parameters:

bb - The block to append the load to

ir - The IR

prependStore

private void prependStore(BasicBlock bb,
                          IR ir)

Append a store of the global counter to the given basic block. WARNING: Tested in LIR only!

Parameters:

bb - The block to append the load to

ir - The IR

prependDecrement

private void prependDecrement(BasicBlock bb,
                              IR ir)

Append a decrement of the global counter to the given basic block. Tested in LIR only!

Parameters:

bb - The block to append the load to

ir - The IR

prependCounterReset

private void prependCounterReset(BasicBlock bb,
                                 IR ir)

Prepend the code to reset the global counter to the given basic block. Warning: Tested in LIR only!

Parameters:

bb - The block to append the load to

ir - The IR

getFirstInstWithOperator

private static Instruction getFirstInstWithOperator(Operator operator,
                                                    BasicBlock bb)

Go through all instructions and find the first with the given operator.

Parameters:

operator - The operator to look for

bb - The basic block in which to look

Returns:

The first instruction in bb that has operator operator.

getFirstInstWithYieldPoint

public static Instruction getFirstInstWithYieldPoint(BasicBlock bb)

Go through all instructions and find one that is a yield point

Parameters:

bb - The basic block in which to look

Returns:

The first instruction in bb that has a yield point

isYieldpoint

public static boolean isYieldpoint(Instruction i)

Is the given instruction a yieldpoint?

For now we ignore epilogue yieldpoints since we are only concerned with method entries and backedges.

Parameters:

i - the instruction to examine

Returns:

whether the instruction is a non-epilogue yieldpoint

adjustPointersInDuplicatedCode

private static void adjustPointersInDuplicatedCode(IR ir,
                                                   HashMap<BasicBlock,BasicBlock> origToDupMap)

Go through all blocks in duplicated code and adjust the edges as follows:

1. All edges (in duplicated code) that go into a block with a yieldpoint must jump to back to the original code. This is actually already satisfied because we appended goto's to all duplicated bb's (the goto's go back to orig code)
2. All edges that do NOT go into a yieldpoint block must stay (either fallthrough or jump to a block in) in the duplicated code.

Parameters:

origToDupMap - mapping of basic blocks to their duplicates

ir - the governing IR

removeInstrumentationFromOrig

private static void removeInstrumentationFromOrig(IR ir,
                                                  HashMap<BasicBlock,BasicBlock> origToDupMap)

Remove instrumentation from the original version of all duplicated basic blocks.

The yieldpoints can also be removed from either the original or the duplicated code. If you remove them from the original, it will make it run faster (since it is executed more than the duplicated) however that means that you can't turn off the instrumentation or you could infinitely loop without executing yieldpoints!

Parameters:

ir - the governing IR

origToDupMap - mapping of basic blocks to their duplicates

myCopyWithoutLinks

private static BasicBlock myCopyWithoutLinks(BasicBlock bb,
                                             IR ir)

The same as BasicBlock.copyWithoutLinks except that it renames all temp variables that are never used outside the basic block. This 1) helps eliminate the artificially large live ranges that might have been created (assuming the reg allocator isn't too smart) and 2) it prevents BURS from crashing.

PRECONDITION: the spansBasicBlock bit must be correct by calling DefUse.recomputeSpansBasicBlock(IR);

Parameters:

bb - the basic block to process

ir - the IR that contains the block

Returns:

the copied block

updateTemps

private static void updateTemps(BasicBlock bb,
                                IR ir)

Given an basic block, rename all of the temporary registers that are local to the block.

Parameters:

bb - the block

ir - the IR that contains the block

getOrCreateDupReg

private static RegisterOperand getOrCreateDupReg(RegisterOperand ro,
                                                 IR ir,
                                                 Map<Register,Register> dupMappings)

The given register a) does not span multiple basic block, and b) is used in a basic block that is being duplicated. It is therefore safe to replace all occurrences of the register with a new register. This method returns the duplicated register that is associated with the given register. If a duplicated register does not exist, it is created and recorded.

Parameters:

ro - the register operand to duplicate

ir - the IR that contains the register operand

dupMappings - the mappings of registers to duplicates

Returns:

a duplicated register operand

performVariationNoDuplication

private void performVariationNoDuplication(IR ir)

Perform the NoDuplication version of the framework (see Arnold-Ryder PLDI 2001). Instrumentation operations are wrapped in a conditional, but no code duplication is performed.

Parameters:

ir - the IR to process

conditionalizeInstrumentationOperation

private void conditionalizeInstrumentationOperation(IR ir,
                                                    Instruction i,
                                                    BasicBlock bb)

Take an instrumentation operation (an instruction) and guard it with a counter-based check.

1. split the basic block before and after the i to get A -> B -> C
2. Add check to A, making it go to B if it succeeds, otherwise C

Parameters:

ir - the IR that contains the instruction

i - the instruction

bb - the basic block that contains the instruction

isInstrumentationInstruction

private static boolean isInstrumentationInstruction(Instruction i)

How to determine whether a given instruction is an "instrumentation instruction". In other words, it should be executed only when a sample is being taken.

Parameters:

i - an instruction

Returns:

true if and only if this is an instrumentation instruction

dumpCFG

public static void dumpCFG(IR ir)