Integer Programming Based Register Allocation

this paper is based on that prior work. The primary objective of this project is to significantly speedup the integer programming based register allocator ORA (Optimal Register Allocator). Significant speedup is expected from the discovery of application-specific methods for solving register allocation integer programs. Discovery and implementation of more efficient integer programming formulations is also expected to produce significant speedup. The speedup achieved from this project will make integer programming based register allocation more broadly applicable. The study of efficient formulation methods and application-specific integer program solution methods will also lead to better understanding of the register allocation problem. Efficient integer programming formulations to the register allocation problem can produce significant speedup in the time required to solve the integer program. There are several methods that can be implemented to achieve this speedup. One of these methods currently being implemented is the identification of nonspilling symbolic registers. Prior to the register allocation phase of compilation, there are an unlimited number of symbolic registers used to represent variables and compiler generated temporaries that must be allocated to real registers when they are used during program execution. Symbolic registers that are not residing in a real register are said to have been spilled to memory. If a symbolic register has been spilled, it must be loaded from memory prior to each use of that symbolic register. Likewise, after each assignment (definition) of a symbolic register that must be spilled, a store instruction is required. It is then left to the register allocator to determine whether a symbolic register is spilled at a given point in t..