Advanced Backend Code Optimization

This book is a summary of more than a decade of research in the area of backend optimization. It contains the latest fundamental research results in this field. While existing books are often more oriented toward Masters students, this book is aimed more towards professors and researchers as it contains more advanced subjects.
It is unique in the sense that it contains information that has not previously been covered by other books in the field, with chapters on phase ordering in optimizing compilation; register saturation in instruction level parallelism; code size reduction for software pipelining; memory hierarchy effects and instruction level parallelism.
Other chapters provide the latest research results in well-known topics such as register need, and software pipelining and periodic register allocation.

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

Sid Touati is Full professor at the university of Nice Sophia-Antipolis, France.