This project will study the use of integer programming for register allocation and for important compiler optimizations that interact with register allocation. The project will build on the preceding work which shows that integer programming can produce optimal or near-optimal register allocations in reasonable time, providing significant reductions in register allocation overhead. The project's first objective is to achieve order of magnitude speedup in integer-programming-based register allocation by discovering and implementing more efficient integer-programming formulations. The project's second objective is to extend the scope of the integer programming formulation to include other compiler optimizations that directly interact with register allocation, such as common subexpression elimination and loop-invariant code motion. The extended formulation will allow register allocation and these interacting optimizations to be done simultaneously, eliminating the traditional phase ordering problem. It is expected that the extended integer programming formulation will provide significant code quality improvements, and that the new optimization can be done in reasonable time.
