A Hybrid Evolutionary Algorithm for Solving the Register Allocation Problem

Abstract

One of the strong impacts on runtime performance of a given code is the register allocation phase of compilation. It is crucial to provide aggressive and sophisticated register allocators for the embedded devices, where the excessive compilation time is tolerated because of its off-line nature. In this paper, we present a hybrid evolutionary algorithm for register allocation problem that combines genetic algorithms with a local search technique. Our algorithm exploits a novel, highly-specialized crossover operator that considers domain-specific information. Computational experiments performed on various synthetic benchmarks prove that our method significantly outperform the state-of-the-art algorithms with respect to all given comparison metrics on solution quality. © Springer-Verlag 2004.