next up previous contents
Next: 7.3 Super Block Scheduling Up: 7 Scheduling Algorithms for Previous: 7.1 Trace Scheduling   Contents

7.2 Trace Scheduling - 2

Trace scheduling - 2 goes beyond the original trace scheduling in that it allows nonlinear code motion, i.e. it allows operations from both sides of a conditional branch to be moved above the branch. Trace scheduling usually misses code motions that are speculative or moves operations from one trace to another. Trace scheduling - 2 on the other hand uses an expected value function called speculative yield to consider the cost of speculative execution and decide whether or not to move operations from one block to another. Unlike trace scheduling which operates on a linear sequence of blocks, the newer algorithm works by picking clusters of operations where each cluster is a maximal set of operations that are connected without back edges in the flow graph of the program. The actual details of the algorithm are beyond the scope of this article.

Binu K. Mathew