| Optimizing compilers have a fundamental problem. No matter how powerful their optimizations
are, they are no substitute for good application algorithms. Consider the case of
sorting. For sufficiently large data sets, a merge sort algorithm compiled with a less powerful
optimizer will always out-perform a selection sort algorithm compiled with the most
powerful optimizer. Or consider the case of solving systems of equations. For sufficiently
large data sets, a Gaussian Elimination algorithm compiled with a less powerful optimizer
will always out-perform a Cramer’s rule algorithm compiled with the most powerful optimizer.
Developers of optimizing compilers also have an opportunity to leverage an under-used
asset. There are several high-quality numerical libraries that are publicly available, such
as the BLAS and LAPACK, that provide broadly applicable algorithms for scientific and
engineering computing. Vendors of high performance computers often provide versions of
these libraries that have been highly tuned to their particular system architecture. Users of
high performance computers sometimes employ these libraries. Unfortunately, many users
are unaware of their existence, and don’t use them even when they are available.
What if compilers could recognize a poor algorithp written by a user, and replace it
with the best implementation of a better algorithm that solves the same problem? Given
reasonable implementations of both algorithms, such a replacement would result in as
significant performance improvement. This book explains an approach that makes this
possible.
The scope over which compilers perform optimizations has steadily increased in the
past three decades. Initially, they performed optimizations on a sequence of statements that
would be executed as a unit, e.g. a basic block. During the 1970’s, researchers developed
control flow analysis, data flow analysis and name association algorithms. This made it
possible for compilers to do optimizations across an entire procedure. During the 1980’s,
researchers extended these analyses across procedure boundaries (lo), as well as adding
side effect analysis (9). This made it possible for compilers to do optimizations across an
entire program. |
