A Translation Validation Algorithm for LLVM Register Allocators

Register allocation is a crucial and complex phase of any modern production compiler. In this work, we present a translation validation algorithm that verifies each single instance of register allocation. Our algorithm is external to the compiler and independent of the register allocation algorithm. We support all major register allocation optimizations such as live range splitting, register coalescing, and rematerialization. We developed a prototype of this approach for the production-quality register allocation phase of LLVM. We evaluated this prototype for compiling the source code of SPECint 2006 benchmark, and we were able to verify the register allocation of over 88% of supported functions in the benchmark, using all 4 register allocators available in LLVM 5.0.2.