HP Labs Technical Reports

Global Code Generation for Instruction-Level Parallelism: Trace Scheduling-2

Fisher, Joseph A.

HPL-93-43

Keyword(s):

Abstract: Trace Scheduling-2 is a method of code generation for instruction- level parallel architectures. Like its predecessor, Trace Scheduling , it relies on estimates of likely program jump directions to select operations to move from basic block to basic block. Unlike trace scheduling, trace scheduling-2 is "nonlinear", that is it allows code to move above a conditional jump from both sides at the same time. Code which falls below the predicted less-likely branch is treated as a first-class citizen. Trace scheduling-2 differs from other techniques with similar objectives in allowing the code generator, rather than a stand-alone phase of the compiler, to make the fundamental choices of code motion. by using an expected value function, the speculative yield, trace scheduling-2 can decide whether to move operations between blocks in a manner that is considerate of the cost of speculative execution, and in a manner that interacts naturally with standard scheduling priority functions, such as DAG height. Speculative yield is useful in solving some problems that have appeared in trace scheduling implementations as well. In order to generate good code for instruction-level parallel systems, accurate jump predictions must be possible. This paper reports on some measures of how realistic it is to expect to have good enough predictions at compile time. Trace scheduling-2 is now being implemented. This paper considers some of the design issues and challenges of that implementation, reviews trace scheduling and some of its proposed extensions, presents the motivation for and main algorithms of trace scheduling-2, and discusses the issue of data-driven predictions of flow of control, which is central to an accurate speculative yield function.

Back to Index