org.jikesrvm.compilers.opt.controlflow

Class EstimateBlockFrequencies

java.lang.Object

org.jikesrvm.compilers.opt.driver.CompilerPhase

org.jikesrvm.compilers.opt.controlflow.EstimateBlockFrequencies

public class EstimateBlockFrequencies
extends CompilerPhase

Derive relative basic block execution frequencies from branch probabilities.

This code assumes that the loop structure tree can be constructed for the CFG in question. This implies that the CFG is reducible.

The basic algorithm is as follows:

• Construct the loop structure tree for the CFG.
• In a postorder traversal, compute the loop multiplier for each loop. The loop multiplier is a number such that the execution frequency of the loop pre-header times the loop multiplier is equal to the execution frequency of the loop head. This can be derived by computing the loop exit weight (the probability of exiting the loop) and applying Kirchoff's law that flow in is equal to flow out. Loop exit weight can be computed in a single topological (ignoring backedges) traversal of the nodes in the loop.
• Assign the entry node weight 1. In a topological traversal of the CFG (ignoring backedges), propagate the weights. When processing a loop head, multiply the incoming weight by the loop multiplier.

Field Summary

Fields

Modifier and Type	Field and Description
private static Constructor<CompilerPhase>	constructor Constructor for this compiler phase
private IR	ir The IR on which to operate.
private LSTGraph	lst The loop structure tree of said IR
private BasicBlock[]	topOrder Topological ordering (ignoring backedges) of CFG

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

container

Constructor Summary

Constructors

Constructor and Description
EstimateBlockFrequencies()

Method Summary

Modifier and Type	Method and Description
private void	computeBlockFrequencies()
private void	computeInfrequentBlocks(IR ir) Compute which blocks are infrequent.
private float	computeLoopExitWeight(LSTNode n)
private void	computeLoopMultipliers(LSTNode n) Postorder traversal of LST computing loop multiplier and loop exits for each loop.
private void	computeMultiplier(LSTNode n) Compute the loop multiplier for this loop nest
private void	computeNodeWeights(LSTNode n) Propagate execution frequencies through the loop.
Constructor<CompilerPhase>	getClassConstructor() Get a constructor object for this compiler phase
String	getName()
void	perform(IR _ir) Compute relative basic block frequencies for the argument IR based on the branch probability information on each conditional and multiway branch.
private void	processEdge(LSTNode n, BasicBlock source, BasicBlock target, float prob, float weight)
void	reportAdditionalStats() Called when printing a measure compilation report to enable a phase to report additional phase-specific statistics.
private void	setDumbFrequencies(IR ir) Set the frequency of each basic block to 1.0f.

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

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

Methods inherited from class java.lang.Object

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

Field Detail

ir

private IR ir

The IR on which to operate.

lst

private LSTGraph lst

The loop structure tree of said IR

constructor

private static final Constructor<CompilerPhase> constructor

Constructor for this compiler phase

topOrder

private BasicBlock[] topOrder

Topological ordering (ignoring backedges) of CFG

Constructor Detail

EstimateBlockFrequencies

public EstimateBlockFrequencies()

Method Detail

getClassConstructor

public Constructor<CompilerPhase> getClassConstructor()

Get a constructor object for this compiler phase

Overrides:

getClassConstructor in class CompilerPhase

Returns:

compiler phase constructor

getName

public String getName()

Specified by:

getName in class CompilerPhase

Returns:

a String which is the name of the phase.

reportAdditionalStats

public void reportAdditionalStats()

Description copied from class: CompilerPhase

Called when printing a measure compilation report to enable a phase to report additional phase-specific statistics.

Overrides:

reportAdditionalStats in class CompilerPhase

perform

public void perform(IR _ir)

Compute relative basic block frequencies for the argument IR based on the branch probability information on each conditional and multiway branch.

Assumptions:

1. LST is valid
2. basic block numbering is dense (compact has been called)

Specified by:

perform in class CompilerPhase

Parameters:

_ir - the IR on which to apply the phase

setDumbFrequencies

private void setDumbFrequencies(IR ir)

Set the frequency of each basic block to 1.0f.

Parameters:

ir - the IR that contains the blocks

computeInfrequentBlocks

private void computeInfrequentBlocks(IR ir)

Compute which blocks are infrequent.

Algorithm:

1. let f = INFREQUENT_THRESHOLD.
2. Start with S = {all basic blocks}.
3. Sort the blocks by frequency. Starting with the most frequent blocks, remove blocks from S until the sum of block frequencies in S <= f. Then blocks in S are infrequent.

Parameters:

ir - the governing IR.

computeLoopMultipliers

private void computeLoopMultipliers(LSTNode n)

Postorder traversal of LST computing loop multiplier and loop exits for each loop.

Parameters:

n - a node

computeMultiplier

private void computeMultiplier(LSTNode n)

Compute the loop multiplier for this loop nest

Parameters:

n - starting node

computeNodeWeights

private void computeNodeWeights(LSTNode n)

Propagate execution frequencies through the loop. Also records loop exit edges in loopExits.

Parameters:

n - starting node

processEdge

private void processEdge(LSTNode n,
                         BasicBlock source,
                         BasicBlock target,
                         float prob,
                         float weight)

computeLoopExitWeight

private float computeLoopExitWeight(LSTNode n)

computeBlockFrequencies

private void computeBlockFrequencies()