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.

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

EstimateBlockFrequencies

public EstimateBlockFrequencies()

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.

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.

computeMultiplier

private void computeMultiplier(LSTNode n)

Compute the loop multiplier for this loop nest

computeNodeWeights

private void computeNodeWeights(LSTNode n)

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

processEdge

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

computeLoopExitWeight

private float computeLoopExitWeight(LSTNode n)

computeBlockFrequencies

private void computeBlockFrequencies()