Part of the problem is that, although program analysis and transformation are well-understood subjects, there is no reliable method for selecting from the astronomical number of possible transformation sequences. A strategy that has proven successful in the automatic generation of high-quality libraries is to execute on the target machine many different forms of the code to be generated and select the fastest. The total number of forms is usually too large for an exhaustive search and, therefore, simple heuristics and intelligent search strategies must be used. Systems that follow this approach include ATLAS, FFTW, and Spiral.
It has been suggested that this empirical search approach can be transplanted to conventional optimizing compilers. However, executing many versions of the target code tends to be expensive and the measured performance does not necessarily represent the performance of the code for all possible input data sets. The use of architectural models to evaluate performance and guide the search could help overcome this difficulty. In this talk, I will discuss our experience with library generators and the use of architectural models as a replacement of empirical models.