Compiler register allocation

Hardware registers are expensive (both in terms of matrix area and the number of instruction bits required to eliminate them) and tend to be quite small overall. Spilling occurs when the number of live variables (or more precisely, the number of real-time ranges) at a given program point exceeds the number of available registers.

Consider the following example program running on an imaginary machine with two hardware registers. Suppose the compiler doesn't do any optimization other than register allocation.

a := 1   ; liveout: {a}
b := 2   ; liveout: {a,b}
c := 3   ; liveout: {a,b,c}
d := a + b + c

      

        
        
        
      

    

Since a

and b

are used in the determination of d

their live ranges overlap determination c

. But since the machine has only two registers, it is impossible for all a

, b

and c

kept in the register in the determination d

. At least one of them must be spilled.

In the simplest form of a spill, all spilled variable definitions are replaced by stores on a stack , and all uses are replaced by loads. Some compilers also have the ability to loop through registers for registration, which means that the value is stored and loaded from the register of another class. For example, on x86-64, the compiler can spill a value from a general-purpose rax

register of a type into a SIMD register, for example xmm0

. This helps reduce memory traffic.

As an alternative to spill, the compiler can do live range split instead. This involves splitting the bands in real time into smaller chunks - inserting loads and stores only at split points - to enable coloring of an otherwise non-colored interference graph.

As you can imagine, the choice of variable for the spill has a significant impact on the performance of the resulting code. Arbitrarily spilling a variable used or defined in a narrow loop can be disastrous. Thus, a good compiler will probably apply some form of heuristic to estimate the cost of spilling each variable before making its choice.