Table of Contents
Introduction xiii
Part 1 Prolog: Optimizing Compilation 1
Chapter 1 On the Decidability of Phase Ordering in Optimizing Compilation 3
Part 2 Instruction Scheduling 23
Chapter 2 Instruction Scheduling Problems and Overview 25
Chapter 3 Applications of Machine Scheduling to Instruction Scheduling 39
Chapter 4 Instruction Scheduling Before Register Allocation 51
Chapter 5 Instruction Scheduling After Register Allocation 77
Chapter 6 Dealing in Practice with Memory Hierarchy Effects and Instruction Level Parallelism 91
Part 3 Register Optimization 119
Chapter 7 The Register Need of a Fixed Instruction Schedule 121
Chapter 8 The Register Saturation 141
Chapter 9 Spill Code Reduction 159
Chapter 10 Exploiting the Register Access Delays Before Instruction Scheduling 177
Chapter 11 Loop Unrolling Degree Minimization for Periodic Register Allocation 191
Part 4 Epilog: Performance, Open Problems 231
Chapter 12 Statistical Performance Analysis: The Speedup-Test Protocol 233
Conclusion 257
Appendix 1 Presentation of the Benchmarks Used in Our Experiments 263
Appendix 2 Register Saturation Computation on Stand-Alone DDG 271
Appendix 3 Efficiency of SIRA on the Benchmarks 279
Appendix 4 Efficiency of Non-Positive Circuit Elimination in the SIRA Framework 293
Appendix 5 Loop Unroll Degree Minimization: Experimental Results 303
Appendix 6 Experimental Efficiency of Software Data Preloading and Prefetching for Embedded VLIW 313
Appendix 7 Appendix of the Speedup-Test Protocol 319
Bibliography 327
Lists of Figures, Tables and Algorithms 345
Index 353
