In compiler optimization, register allocation is a well-known process of mapping program variables (also referred to as “pseudos”) with central processing unit (CPU) or processor registers. The number of processor registers on a processor is considered constraint since that number depends on the architectural design of the processor, and regardless of how large the number of processor registers, it is still considered a smaller number compared to the large (and unconstraint) number of program variables a typical software programs has to process. This discrepancy of not having enough processor registers to hold program variables is known as “high register pressure”, which leads to what is typically referred to as “spilling” or “register spilling”.
Spilling occurs when there are more live program variables than the available processor registers to hold them and thus, a compiler is forced to spill some of the program variables to memory, which leads to inefficiency because accessing memory is typically slower than accessing processor registers. Register allocation can be local (e.g., restricted to a small section of a procedure or a basic block), global (e.g., performed on the whole procedure), or interprocedural (e.g., performed in-between or across multiple procedures). A number of conventional solutions exist to manage register allocation and memory spilling, but none of the existing solution is without its shortcomings.
One well-known solution is register allocation by graph coloring (“GC”). However, this solution does not provide for proper selection of program variables for spilling (to memory) which leads to high allocation time and inefficiency in register allocation. Another solution is extended linear scan (“ELS”). Although this solution is considered an improvement for spilling over GC, but only a small improvement. When considering a spill, ELS is static in its analysis of whether to spill a program variable to memory and further, it is limited to the program variable at hand and does not give consideration to other program variables or their relationship with the variable that is to be spilled.