org.jikesrvm.compilers.opt.controlflow

Class ReorderingPhase

java.lang.Object

org.jikesrvm.compilers.opt.driver.CompilerPhase

org.jikesrvm.compilers.opt.controlflow.ReorderingPhase

public final class ReorderingPhase
extends CompilerPhase

Reorder code layout of basic blocks for improved I-cache locality and branch prediction. This code assumes that basic block frequencies have been computed and blocks have been marked infrequent. This pass actually implements two code placement algorithms:

• (1) A simple 'fluff' removal pass that moves all infrequent basic blocks to the end of the code order.
• (2) Pettis and Hansen Algo2.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private static class	ReorderingPhase.ChainInfo
private static class	ReorderingPhase.Edge

Field Summary

Fields

Modifier and Type	Field and Description
private static boolean	DEBUG

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

container

Constructor Summary

Constructors

Constructor and Description
ReorderingPhase()

Method Summary

Modifier and Type	Method and Description
private void	doPettisHansenAlgo2(IR ir) Reorder code using Algo2 (Bottom-Up Positioning) from Pettis and Hansen PLDI'90.
private void	dumpChain(BasicBlock head)
private void	exileInfrequentBlocks(IR ir) Select a new basic block ordering via a simple heuristic that moves all infrequent basic blocks to the end.
String	getName()
CompilerPhase	newExecution(IR ir) Return this instance of this phase.
void	perform(IR ir) Reorder basic blocks either by trivially moving infrequent blocks to the end of the code order or by applying Pettis and Hansen Algo2.
boolean	printingEnabled(OptOptions options, boolean before) Returns true if the phase wants the IR dumped before and/or after it runs.
boolean	shouldPerform(OptOptions options) This method determines if the phase should be run, based on the Options object it is passed.

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

Constructor Detail

ReorderingPhase

public ReorderingPhase()

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

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.

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)

Reorder basic blocks either by trivially moving infrequent blocks to the end of the code order or by applying Pettis and Hansen Algo2. We will rearrange basic blocks and insert/remove unconditional GOTO's if needed. It does not clean up branches, by reversing the branch condition, however. That is saved for BranchOptimizations.

Specified by:

perform in class CompilerPhase

Parameters:

ir - the IR on which to apply the phase

exileInfrequentBlocks

private void exileInfrequentBlocks(IR ir)

Select a new basic block ordering via a simple heuristic that moves all infrequent basic blocks to the end.

Parameters:

ir - the IR object to reorder

doPettisHansenAlgo2

private void doPettisHansenAlgo2(IR ir)

Reorder code using Algo2 (Bottom-Up Positioning) from Pettis and Hansen PLDI'90.

Parameters:

ir - the IR to reorder.

dumpChain

private void dumpChain(BasicBlock head)