| The motivation of this text lies in what we believe is the inadequacy of current frameworks to reason about the flow of data in imperative programs. This inadequacy clearly shows up when dealing with the individual side effects of loop iterations. Indeed, we face a paradoxical situation where, on the one hand, a typical program spends most of its execution time iterating or recursing on a few lines of codes, and, on the other hand, current optimization frameworks are clumsy when trying to capture the effects of each incarnation of these few lines—frameworks we inherited from designs made decades ago.
The reasons are manyfold, but one of them stands out: The same concepts have been used, on the one hand, to represent and manipulate programs internally in compilers and, on the other hand, to allow us humans to reason about optimizations. Unfortunately, these two uses have different aims and constraints. An example of such a situation is given by control-flow graphs of basic blocks, which have been extremely useful in practice as an internal representation of programs, but which are not always adequate or convenient to formally think about programs and specify their transformations. In some cases, definitions based on control-flow graphs can be overly restrictive. Dominance, studied in Chapter 4, is a good example.
The consequence of these low-level representations is that many analyses and optimizations are defined constructively, by giving an algorithm instead of defining what the goal is: Instead of first telling what, they tell how. Then there is no specification against which the implementation can be checked.
In addition, implementation-oriented definitions of analyses and optimizations are often clumsy at representing one key aspect of programs: data flow. The flow of data is one key characteristic of algorithms, which programs implement. Unfortunately, because of its intrinsic reuse of memory, imperative programming blurs the data flow and hides the algorithm it implements even more so. If the compiler could extract the algorithm from the text of the program, it could apply extremely sophisticated optimizations.
We argue that the closer a compiler (or we humans) gets to the underlying algorithm, the wider the spectrum of transformations it can apply. And indeed, one sure way to understand the algorithm is to first understand the data flow. |
