Searching for Compilation Sequences
Keith D. Cooper, Alexander Grosul, Timothy J. Harvey, Steve Reeves, Devika Subramanian, Linda Torczon, Todd Waterman · 2004
A growing body of literature on adaptive compilation suggests that using program-specific [7] or function-specific [24] compilation sequences can produce consistent improvements over compiling the same code with a traditional fixed-sequence compiler [18, 1, 27, 24]. The early work on this problem used genetic algorithms (GAs) [7]. GAs find good solutions to these problems. However, they must probe the search space thousands of times; each probe compiles and evaluates the code. To build a practical compiler that discovers good compilation sequences, we need techniques that find good sequences with much less effort than the GAs require. To find such techniques, we embarked on a detailed study of the search spaces in which the compiler operates. By understanding the properties of these spaces, we can design more effective searches. This paper focuses on effective search algorithms for the problem of choosing compilation sequences – an ordered list of optimizations to apply to the input program. It summarizes the search-space properties that we discovered in our studies. It presents and evaluates two new search methods, designed with knowledge of the search-space properties. It compares the new methods against the best sequence-finding GA that we have developed. Our new search methods can find good solutions with 400 to 600 probes. The first GA for sequence finding required 10,000 to 20,000 probes [7]. Our most effective GA runs for 2,300 probes. The strength of these results validates our paradigm – learn about the spaces and use that knowledge to improve the search techniques. ∗This work has been supported by the Los Alamos Computer Science Institute and by the National Science Foundation through grant CCR-0205303. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Copyright 200X ACM X-XXXXX-XX-X/XX/XX ...$5.00.