Name
Abstract | ||
|---|---|---|
Trace scheduling is an optimization technique that selects a sequence of basic blocks as a trace and schedules the operations from the trace together. If an operation is moved across basic block boundaries, one or more compensation copies may be required in the off-trace code. This article discusses the generation of compensation code in a trace scheduling compiler and presents techniques for limiting the amount of compensation code: avoidance (restricting code motion so that no compensation code is required) and suppression (analyzing the global flow of the program to detect when a copy is redundant). We evaluate the effectiveness of these techniques based on measurements for the SPEC89 suite and the Livermore Fortran Kernels, using our implementation of trace scheduling for a Multiflow Trace 7/300. The article compares different compiler models contrasting the performance of trace scheduling with the performance obtained from typical RISC compilation techniques.There are two key results of this study. First, the amount of compensation code generated is not large. For the SPEC89 suite, the average code size increase due to trace scheduling is 6%. Avoidance is more important than suppression, although there are some kernels that benefit significantly from compensation code suppression. Since compensation code is not a major issue, a compiler can be more aggressive in code motion and loop unrolling. Second, compensation code is not critical to obtain the benefits of trace scheduling. Our implementation of trace scheduling improves the SPEC mark rating by 30% over basic block scheduling, but restricting trace scheduling so that no compensation code is required improves the rating by 25%. This indicates that most basic block scheduling techniques can be extended to trace scheduling without requiring any complicated compensation code bookkeeping. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1145/183432.183446 | ACM Trans. Program. Lang. Syst. |
Keywords | Field | DocType |
off-trace code,basic block scheduling,compensation code,instruction-level parallelism,spec89,complicated compensation code bookkeeping,trace scheduling,performance evaluation,trace scheduling compiler,basic block scheduling technique,compensation code suppression,code motion,average code size increase,software engineering,code generation,operation,motion,scheduling,performance engineering,boundaries,parallel processing,sequences,compilers,instruction level parallelism,optimization,computer programming | Unreachable code,Dead code elimination,Programming language,Trace scheduling,Fair-share scheduling,Instruction scheduling,Loop-invariant code motion,Computer science,Parallel computing,Theoretical computer science,Redundant code,Dead code | Journal |
Volume | Issue | ISSN |
16 | 4 | 0164-0925 |
Citations | PageRank | References |
15 | 1.57 | 18 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stefan M. Freudenberger | 1 | 197 | 38.74 |
| Thomas R. Gross | 2 | 2807 | 404.74 |
| Geoff Lowney | 3 | 2140 | 136.12 |