Advanced Backend Code Optimization

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