Advanced Backend Optimization

Introduction

An open question that remains in computer science is how to define a program of good quality. At the semantic level, a good program is one that computes what is specified formally (either in an exact way, or even without an exact result but at least heading towards making a right decision). At the algorithmic level, a good program is one that has a reduced spatial and temporal complexity. This book does not tackle these two levels of program quality abstraction. We are interested in the aspects of code quality at the compilation level (after a coding and an implementation of an algorithm). When a program has been implemented, some quality can be quantified according to its efficiency, for instance. By the term “efficiency”, we mean a program that exploits the underlying hardware at its best, delivers the correct results as quickly as possible, has a reasonable memory footprint and a moderate energy consumption. There are also some quality criteria that are not easy to define, for instance the clarity of the code and its aptitude for being analyzed conveniently by automatic methods (worst-case execution time, data-flow dependence analysis, etc.).

Automatic code optimization, in general, focuses on two objectives that are not necessarily antagonists: the computation speed and the memory footprint of the code. These are the two principal quality criteria approached in this book. The computation speed is the most popular objective, but it remains difficult to model precisely. ...