Advanced Backend Code Optimization

Sid Touati, Benoit Dupont de Dinechin

• Publisher: Wiley-ISTE
• Year: 2014
• Print ISBN: 9781848215382
• eBook ISBN: 9781118648957
• Edition: 1
• Topic: Computer Science
• Subtopic: Software Development
• Index: Computer Science

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.

PART 1

Prolog: Optimizing Compilation

1

On the Decidability of Phase Ordering in Optimizing Compilation

We are interested in the computing frontier around an essential question about compiler construction: having a program

and a set

of non-parametric compiler optimization modules (also called phases), is it possible to find a sequence s of these phases such that the performance (for instance, execution time) of the final generated program

′ is optimal? We proved in [TOU 06] that this problem is undecidable in two general schemes of optimizing compilation: iterative compilation and library optimization/generation. Fortunately, we give some simplified cases when this problem becomes decidable, and we provide some algorithms (not necessarily efficient) that can answer our main question.

Another essential problem that we are interested in is parameter space exploration in optimizing compilation (tuning optimizing compilation parameters). In this case, we assume a fixed sequence of compiler optimizations, but each optimization phase is allowed to have a parameter. We try to figure out how to compute the best parameter values for all program transformations when the compilation sequence is given. We also prove that this general problem is undecidable and we provide some simplified decidable instances.

1.1. Introduction to the phase ordering problem

The notion of an optimal program is sometimes ambiguous in optimizing compilation. Using an absolute definition, an optimal program

^* means that there is no other equivalent program

faster than

^*, whatever the input data be. This is equivalent to stating that the optimal program should run as fast as the longest dependence chain in its trace. This notion of optimality cannot exist in practice: Schwiegelshohn et al. showed [SCH 91] that there are loops with conditional jumps for which no semantically equivalent time-optimal program exists on parallel machines, even with speculative execution¹. More precisely, they showed why it is impossible to write a program that is the fastest for any input data. This is because the presence of conditional jumps makes the program execution paths dependent on the input data; so it is not guaranteed that a program shown faster for a considered input data set (i.e. for a given execution path) remains the fastest for all possible input data. Furthermore, Schwiegelshohn et al. convinced us that optimal codes for loops with branches (with arbitrary input data) require the ability to express and execute a program with an unbounded speculative window. Since any real speculative feature is limited in practice², it is impossible to write an optimal code for some loops with branches on real machines.

In our result, we define the program optimality according to the input data. So, we say that a program

^* is optimal if there is not another equivalent program

faster than

^* considering the same input data. Of course, the optimal program

^* related to the considered input data I^* must still execute correctly for any other input data, but not necessarily in the fastest speed of execution. In other words, we do not try to build efficient specialized programs, i.e. we should not generate programs that execute only for a certain input data set. Otherwise, a simple program that only prints the results would be sufficient for fixed input data.

With this notion of optimality, we can ask the general question: how can we build a compiler that generates an optimal program given an input data set? Such a question is very difficult to answer, since until now we have not been able to enumerate all the possible automatic program rewriting methods in compilation (some are present in the literature; others have to be set up in the future). So, we first address in this chapter another similar question: given a finite set of compiler optimization modules

, how can we build an automatic method to combine them in a finite sequence that produces an optimal program? By compiler optimization module, we mean a program transformation that rewrites the original code. Unless they are encapsulated inside code optimization modules, we exclude program analysis passes since they do not modify the code.

This chapter provides a formalism for some general questions about phase ordering. Our formal writing allows us to give preliminary answers from the computer science perspective about decidability (what we can really do by automatic computation) and undecidability (what we can never do by automatic computation). We will show that our answers are strongly correlated to the nature of the models (functions) used to predict or evaluate the program’s performances. Note that we are not interested in the efficiency aspects of compilation and code optimization: we know that most of the code optimization problems are inherently NP-complete. Consequently, the proposed algorithms in this chapter are not necessarily efficient, and are written for the purpose of demonstrating the decidability of some problems. Proposing efficient algorithms for decidable problems is another research aspect outside the current scope.

This chapter is organized as follows. Sec...

Table of contents

• Cover
• Contents
• Title Page
• Copyright
• Introduction
• Part 1: Prolog: Optimizing Compilation
• Part 2: Instruction Scheduling
• Part 3: Register Optimization
• Part 4: Epilog: Performance, Open Problems
• Conclusion
• Appendix 1: Presentation of the Benchmarks Used in Our Experiments
• Appendix 2: Register Saturation Computation on Stand-Alone Ddg
• Appendix 3: Efficiency Of Sira on the Benchmarks
• Appendix 4: Efficiency of Non-Positive Circuit Elimination in the Sira Framework
• Appendix 5: Loop Unroll Degree Minimization: Experimental Results
• Appendix 6: Experimental Efficiency of Software Data Preloading and Prefetching for Embedded Vliw
• Appendix 7: Appendix of the Speedup-Test Protocol
• Bibliography
• Lists of Figures, Tables and Algorithms
• Index