Recently researchers have proposed modeling register allocation as an integer linear programming (IP) problem and solving it optimally for general purpose processors [17, 20] and for dedicated embedded systems [23]. 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.