Register Allocation by Pseudo-Boolean Optimization

Abstract

Register Allocation is a part of the compilation process in which virtual registers are mapped to a physical memory location. This problem is NP-hard yet also an integral part of the compilation process which has led to the development of various efficient heuristics for achieving near optimal allocations. These heuristics are used in modern compilers such as gcc and clang. In this thesis, we investigate register allocation via the solving a pseudo-Boolean optimization (PBO) problem. We develop a suitable encoding of Register Allocation as a PBO Problem. This PBO Problem has constraints relating to virtual and physical register liveness and a cost model developed to find not just a correct register allocation, but the optimal register allocation with respect to number of spills and expected program execution. We allow the PBO Solver to run for a specified amount of time (the longest trial being 6 hours per function) before the most optimal solution to the PBO problem found is used to perform register allocation. We find that the heuristics are able to outperform the PBO Register Allocator. However, we find optimal solutions to 81% of functions in under 65 seconds and have runtimes within 3% of industry strength register allocation methods. Further work will add live-range splitting to the PBO Register Allocator which should improve performance against the heuristics.