Building Practical Compilers Based On Adaptive Search Keith D. Cooper, Devika Subramanian, and Linda Torczon Department of Computer Science Rice University Houston, Texas, USA

Overview

The research program divides, roughly, into two thrusts:

• algorithms to find effective compiler configurations for a specific program, target, and objective function, and
• work on how to structure compilers in ways that make them suitable for use with an adaptive controller.

Algorithms for Adaptation

From a mathematical perspective, the compiler is looking for a minimizer (either local or global) inside a complex discrete space. We have performed a series of experiments to help us understand and characterize these search spaces. A typical space includes fifteen possible transformations; if we allow the compiler to choose a sequence of ten passes, the space contains 576,650,390,625 sequences (15 to the 10th power). The graph to the right shows a tiny subset of one such space: sequences of length four drawn from a set of five optimizations (625 points) for the MediaBench code ADPCM-C.

As you can see, the space is neither smooth nor convex. (No consistent reordering of the data helps, either.) These two talks show detailes results on the search space, beyond what appears in the papers: Keith's keynote talk at CGO 2004 (see particulary slides 23ff) and Keith's recent lecture in Pitt's distinguished lecture series.

We have designed a number of algorithms that appear to perform well in these search spaces. Our current work is focused on scaling up the experiments to demonstrate the efficacy of these algorithms.

Building Compilers That Can Adapt

To study the issues of structure and parameterization, we are conducting a number of studies.

1. We performed a series of experiments using adaptive control of command-line options to improve the performance of numerical linear algebra codes. We were able to achieve ATLAS-like results through automatic adaptation at the compiler level; this result offers the promise of a system that makes ATLAS-class performance available across a large class of applications. (See paper in 2003 LACSI Symposium, below)
   
   
2. We are experimenting with control of inline substitution, with the goal of understanding what makes a good parameterization for adaptive control. (Too often, compilers provide command-line flags that are not particularly useful for adaptive control.) This subproject will produce a source-to-source inliner that uses adaptation to discover program-specific inlining criteria.
   
   
3. We are experimenting with compilation order in the LLVM compiler system (V. Adve at UIUC). This project should demonstrate that the ideas from our work can apply in a compiler not of our own construction. We are gaining additional insight into what properties make adaptation easy and what properties make adaptation hard.

Publications

1. The paper that started it all: Optimizing for Reduced Code Space Using Genetic Algorithms from the 1999 LCTES Workshop
   
   
2. A vision paper on our ideas that appeared in the 2001 LACSI Symposium, Adaptive Optimizing Compilers for the 21st Century, and the corresponding talk. (Proceedings distributed electronically.)
   
   
3. This paper describes our experiments with command-line control of blocking for linear algebra codes (specifically, DGEMM). Investigating Adaptive Compilation using the MIPSPro Compiler appeared in the 2003 LACSI Symposium. (Proceedings distributed electronically.)
   
   
4. This technical report presents an analysis of the search spaces in which the compiler operates. It is currently unpublished.
   
   
5. This document is a preprint of a paper that appears in the 2004 LCTES Conference, Finding Effective Compilation Sequences. It describes both the enumeration and exploration experiments we have done to date (at least, through Spring 2004). It provides a prelimianry basis for understanding the efficacy of greedy methods, genetic algorithms, hill climbers, and random probing.
   
   
6. This paper, " Exploring the Structure of the Space of Compilation Sequences Using Randomized Search Algorithms," was presented at the 2004 LACSI Symposium, October 2004, in Santa Fe, NM, USA. (Proceedings distributed electronically.)
   
   
7. This paper, "Searching for Compilation Sequences," is a preliminary version that was submitted for publication. It discusses the merits of three search techniques and shows the apparent superiority of randomized, impatient hillclimbers for finding sequences of low-level scalar optimizations. It will not appear in print, although the material is being folded into a journal submission.
   
   
8. This paper, "ACME: Adaptive Compilation Made Efficient," describes two facets of the ACME tool: its user interface and its facility for virtual execution.

Standard Disclaimers