A Faster Optimal Register Allocator
Changqing Fu and Kent Wilken
Department of Electrical and Computer Engineering
University of California, Davis
Abstract:
Recently researchers have proposed modeling register allocation problem
as an integer linear programming (IP) problem and solving it optimally
for general purpose processors and for dedicated embedded systems.
Compared with traditional graph-coloring approaches, the IP-based
allocators can improve a program's performance. However, the solution
times are much slower.
This paper presents an IP-based optimal register allocator which is much
faster than previous work. We present several local and global reduction
techniques to identify locations in a program's control-flow graph where
spill decisions and register deallocation decisions are unnecessary
for optimal register allocation. We propose a hierarchical reduction
approach to efficiently remove the corresponding redundant decisions and
constraints from the IP model. This allocator is built into the Gnu C
Compiler and is evaluated experimentally using the SPEC92INT
benchmarks. The results show that the improved IP model is much simpler.
The number of constraints produced is almost linear with the function
size. The optimal allocation time is much faster, with a speedup factor of
about 150 for hard allocation problems.
Web Site:
http://www.ece.ucdavis.edu/cerl/cerl_arch/index.html