Genetic programming applied to compiler heuristic optimization

Genetic programming (GP) has a natural niche in the optimization of small but high payoff software heuristics. We use GP to optimize the priority functions associated with two well known compiler heuristics: predicated hyperblock formation, and register allocation. Our system achieves impressive speedups over a standard baseline for both problems. For hyperblock selection, application-specific heuristics obtain an average speedup of 23% (up to 73%) for the applications in our suite. By evolving the compiler's heuristic over several benchmarks, the best general-purpose heuristic our system found improves the predication algorithm by an average of 25% on our training set, and 9% on a completely unrelated test set. We also improve a well-studied register allocation heuristic. On average, our system obtains a 6% speedup when it specializes the register allocation algorithm for individual applications. The general-purpose heuristic for register allocation achieves a 3% improvement.