org.jikesrvm.compilers.opt.controlflow

Class StaticSplitting

java.lang.Object

org.jikesrvm.compilers.opt.driver.CompilerPhase

org.jikesrvm.compilers.opt.controlflow.StaticSplitting

public class StaticSplitting
extends CompilerPhase

Static splitting based on very simple hints left by guarded inlining (off blocks marked as infrequent) and semantic knowledge of tests. The goal of this pass is to create 'common-case' traces. This is done by eliminating merge points where uncommon-case code merges back into common case code by code duplication. We rely on a later pass to eliminate redundant tests on the common-case trace.

We use semantic knowledge of the tests to reduce the code replicated. The key idea is that for a guarded inlining, it is correct to take the 'off' branch even if test would select the on-branch. Therefore we can avoid replicating the on-branch code downstream of the replicated test, at the possible cost of trapping an execution in the uncommon-case trace that might have been able to use a subset of to common-case trace.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private static class	StaticSplitting.CandInfo

Field Summary

Fields

Modifier and Type	Field and Description
private BranchOptimizations	branchOpts
private StaticSplitting.CandInfo	cands
private static boolean	DEBUG

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

container

Constructor Summary

Constructors

Constructor and Description
StaticSplitting()

Method Summary

Modifier and Type	Method and Description
private boolean	containsOSRPoint(BasicBlock bb)
private BasicBlock	findColdPrev(BasicBlock bb)
private BasicBlock	findColdSucc(Instruction test)
private Instruction	getCandidateTest(BasicBlock bb)
String	getName()
private boolean	haveCandidates()
CompilerPhase	newExecution(IR ir) Return this instance of this phase.
private StaticSplitting.CandInfo	nextCandidate()
void	perform(IR ir) Do simplistic static splitting to create hot traces with that do not have incoming edges from blocks that are statically predicted to be cold.
boolean	printingEnabled(OptOptions options, boolean before) Returns true if the phase wants the IR dumped before and/or after it runs.
private void	pushCandidate(BasicBlock cand, BasicBlock prev, BasicBlock succ, Instruction test)
boolean	shouldPerform(OptOptions options) This method determines if the phase should be run, based on the Options object it is passed.
private void	simpleCandidateSearch(IR ir) Identify candidate blocks by using a very simplistic algorithm.
private void	splitCandidate(StaticSplitting.CandInfo ci, IR ir) Splits a node where we can safely not replicate the on-branch in the cloned node.
private boolean	tooBig(BasicBlock bb, int maxCost) Simplistic cost estimate; since we are doing the splitting based on static hints, we are only willing to copy a very small amount of code.

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

dumpIR, dumpIR, getClassConstructor, getCompilerPhaseConstructor, getCompilerPhaseConstructor, performPhase, 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 final boolean DEBUG

See Also:

Constant Field Values

branchOpts

private final BranchOptimizations branchOpts

cands

private StaticSplitting.CandInfo cands

Constructor Detail

StaticSplitting

public StaticSplitting()

Method Detail

newExecution

public CompilerPhase newExecution(IR ir)

Return this instance of this phase. This phase contains no per-compilation instance fields.

Overrides:

newExecution in class CompilerPhase

Parameters:

ir - not used

Returns:

this

getName

public String getName()

Specified by:

getName in class CompilerPhase

Returns:

a String which is the name of the phase.

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

printingEnabled

public boolean printingEnabled(OptOptions options,
                               boolean before)

Description copied from class: CompilerPhase

Returns true if the phase wants the IR dumped before and/or after it runs. By default, printing is not enabled. Subclasses should override this method if they want to provide IR dumping.

Overrides:

printingEnabled in class CompilerPhase

Parameters:

options - the compiler options for the compilation

before - true when invoked before perform, false otherwise.

Returns:

true if the IR should be printed, false otherwise.

perform

public void perform(IR ir)

Do simplistic static splitting to create hot traces with that do not have incoming edges from blocks that are statically predicted to be cold.

Specified by:

perform in class CompilerPhase

Parameters:

ir - The IR on which to apply the phase

simpleCandidateSearch

private void simpleCandidateSearch(IR ir)

Identify candidate blocks by using a very simplistic algorithm.

• Find all blocks that end in a test that is statically known to be likely to create a common case trace. For example, blocks that end in IG_METHOD_TEST, IG_CLASS_TEST and IG_PATCH_POINT. Note that these tests also have the property that it is correct (but less desirable) to execute the off branch when the test would have selected the on branch.
• If such a block has a control flow predecessor that is marked as infrequent, and if the block is relatively small, then it is almost certainly profitable to duplicate the block and transfer the infrequent predecessor to go to the cloned block. This has the effect of freeing the common-case path from the pollution of the infrequently executed block. Therefore we identify the block as a splitting candidate.

Parameters:

ir - the governing IR

splitCandidate

private void splitCandidate(StaticSplitting.CandInfo ci,
                            IR ir)

Splits a node where we can safely not replicate the on-branch in the cloned node.

Parameters:

ci - description of the split candidate.

ir - the governing IR

getCandidateTest

private Instruction getCandidateTest(BasicBlock bb)

Parameters:

bb - a basic block

Returns:

the candidate test or null if there is no single test (i.e. no test or multiple tests)

findColdPrev

private BasicBlock findColdPrev(BasicBlock bb)

Parameters:

bb - a basic block

Returns:

the cold predecessor to the argument block. If there is not exactly 1, return null.

findColdSucc

private BasicBlock findColdSucc(Instruction test)

Parameters:

test - an instruction for a candidate test

Returns:

the off-trace successor of b (on and off relative to the argument test)

tooBig

private boolean tooBig(BasicBlock bb,
                       int maxCost)

Simplistic cost estimate; since we are doing the splitting based on static hints, we are only willing to copy a very small amount of code.

Parameters:

bb - block to check

maxCost - maximum cost that is acceptable

Returns:

whether the block is too big

containsOSRPoint

private boolean containsOSRPoint(BasicBlock bb)

pushCandidate

private void pushCandidate(BasicBlock cand,
                           BasicBlock prev,
                           BasicBlock succ,
                           Instruction test)

haveCandidates

private boolean haveCandidates()

nextCandidate

private StaticSplitting.CandInfo nextCandidate()