org.jikesrvm.compilers.opt.instrsched
Class Scheduler

java.lang.Object
  org.jikesrvm.compilers.opt.instrsched.Scheduler

final class Scheduler
extends Object

This a simple list-based instruction scheduler.

TODO:

• Add more priority lists
• When scheduling an instruction, verify that its predecessors have already been scheduled.
• Change forward propagation of earliest time to computing it from the scheduling time of predecessors + latencies.
• Change bubble sort to insertion sort.

VERBOSE

private static final int VERBOSE

Debugging level.

See Also:

Constant Field Values

PRINT_CRITICAL_PATH_LENGTH

private static final boolean PRINT_CRITICAL_PATH_LENGTH

Should we print the length of the critical path for each basic block?

See Also:

Constant Field Values

PREPASS

public static final int PREPASS

A constant signifying pre-pass scheduling phase.

See Also:

Constant Field Values

POSTPASS

public static final int POSTPASS

A constant signifying post-pass scheduling phase.

WARNING: POSTPASS INSTRUCTION SCHEDULING (AFTER REGISTER ALLOCATION) Cannot be done safely due to failure to update GCMapping information.

See Also:

Constant Field Values

PhaseName

public static final String[] PhaseName

Names of various scheduling phases.

phase

private final int phase

Current phase (prepass/postpass).

ir

private IR ir

Current IR.

bb

private BasicBlock bb

Current basic block.

dg

private DepGraph dg

Dependence graph for current basic block.

i2gn

private DepGraphNode[] i2gn

Mapping from Instruction to DepGraphNode.

Scheduler

Scheduler(int phase)

Initialize scheduler for a given phase.

Parameters:

phase - the scheduling phase

printDepgraph

private boolean printDepgraph(OptOptions options)

Should we print the dependence graph?

Parameters:

options - the options object

Returns:

true if we should print depgraph, false otherwise

perform

void perform(IR _ir)

For each basic block, build the dependence graph and perform instruction scheduling. This is an MIR to MIR transformation.

Parameters:

_ir - the IR in question

debug

private static void debug(String s)

Output debugging information.

Parameters:

s - string to print

debug

private static void debug(int depth,
                          String s)

Output debugging information with indentation.

Parameters:

depth - level of indenting

s - string to print

setGraphNode

private void setGraphNode(Instruction i,
                          DepGraphNode n)

Set corresponding graph node for instruction.

Parameters:

i - given instruction

n - dependence graph node for instruction

getGraphNode

private DepGraphNode getGraphNode(Instruction i)

Return corresponding graph node for instruction.

Parameters:

i - given instruction

computeCriticalPath

private void computeCriticalPath(DepGraphNode n,
                                 int depth)

Perform DFS to compute critical path for all instructions.

Parameters:

n - start node

depth - current DFS depth

computeEarliestTime

private int computeEarliestTime(Instruction i)

Compute earliest scheduling time for an instruction.

Parameters:

i - given instruction

sortBasicBlock

private boolean sortBasicBlock(int maxtime)

Sort basic block by Scheduled Time. Uses bucket sort on time, with equal times ordered by critical path.

Parameters:

maxtime - the maximum scheduled time

scheduleBasicBlock

private void scheduleBasicBlock()

Schedule a basic block.