Register Allocation using Pseudo-Boolean Optimization

Abstract

Register allocation is the process in which variables defined by the user-given pro- gram are assigned to a physical location in memory during the runtime of the program. Despite being a NP-hard problem, this step cannot be skipped during the process of compilation and thus is the subject of study. Generally, it is accepted that the programmer must choose between a balance of compilation speed and run time reduction. The better a register allocation is, measured by the reduction effect on the run time, the longer the register allocation pass generally takes. Even in cases where run time is the goal of the user, however, modern compilers such as Clang and GCC use heuristics to approximate the effectiveness of their solutions as to provide reasonable compile times. Curious as to alternate approaches to this problem, we explore the possibility of recruiting the use of NP-hard solvers in aiding us during register allocation. The chosen approach involves translating the register allocation into a pseudo- boolean optimization (PBO) problem. This specific NP-hard problem was chosen due to the similar nature that it had with register allocation, allowing to quick translation, and the strength of the solvers that were publicly available. Specifically, there is a natural mapping from the assignment of virtual registers to physical locations and stack slots at each program index to variables within the PBO problem. Furthermore, the translation between the correctness requirements to the constraints representable in PBO is quite easy as well. By performing this transformation of register allocation to a PBO problem, we hope that we can achieve the highest level of running time efficiency by sacrificing a large amount of time during compilation. This is not to replace the current standard algorithms used in practice today, but offer an extreme comparison between them and the theoretical optimal solution. As such, we will be able to understand how much room there is left in improvement to these heuristics and whether or not investing more work in them is worthwhile.