next up previous contents
Next: 7.2 Trace Scheduling - Up: 7 Scheduling Algorithms for Previous: 7 Scheduling Algorithms for   Contents

7.1 Trace Scheduling

Many compilers for first-generation ILP processors used a three phase method to generate code. The phases were:

This three phase approach fails to exploit much of the ILP available in the program for two reasons.

Trace scheduling is a profile driven method developed by Joseph Fisher to circumvent this problem. In trace scheduling, a set of commonly executed sequence of blocks is gathered together into a trace and the whole trace is scheduled together.

The trace scheduling algorithm works as follows.

1. Generate a possibly unoptimized version of the program, run it on sample input and collect statistics. Estimate the probability of each conditional branch.

2. From the basic block level data precedence graph of the program (also commonly called DAG for Directed Acylic Graph), select a loop free linear sequence of basic blocks which have a high probability of execution. Such a sequence is called a trace. The compiler may use other optimizations like loop unrolling or procedure inlining to generate DAGs from which suitable traces can be selected.

3. Consider the trace as if it were a basic block. Build a DAG for it considering branches like all other operations. If an operation controlled by a conditional jump could over write a value that is live on the off-trace edge, add an edge that makes the operation dependent on the branch so that the operation cannot be moved ahead of the branch. Also, add edges to preserve the relative order of conditional branches.

4. Schedule the resulting DAG as if it were a basic block doing register allocation and function unit selection as each operation is scheduled.

5. Generate compensation code for mistakes made by considering the trace as a basic block. In particular:

a. If an operation that used to precede a conditional branch in the sequential code is moved after that branch, then add a copy of that operation preceding the off-trace target of the conditional jump.

b. If an operation that succeeded a point of entry into the trace from outside the trace is moved ahead of that point of entry, place a copy of that operation outside the trace, on the path that leads to that point of entry.

c. Ensure that rejoins that used to enter the trace enter the new trace only at a point after which no operation is found in the new trace that were not below the rejoin point in the old trace.

6. Link the new trace back into the old DAG.

7. After scheduling the very first trace, new operations would have been added to the original DAG. Pick a different frequent trace and schedule it. Repeat till the DAG has been covered using disjoint traces and no unscheduled operations remain.

next up previous contents
Next: 7.2 Trace Scheduling - Up: 7 Scheduling Algorithms for Previous: 7 Scheduling Algorithms for   Contents
Binu K. Mathew