Register allocation
|
|
In compiler optimization, register allocation is the process of multiplexing a large number of target program variables onto a small number of CPU registers.
Most computer programs need to process large amounts of different data items. However, most CPUs can only perform operations on a small fixed number of "slots" called registers. Even on machines that support memory operands, register access is considerably faster than memory access. Therefore the data items to be processed have to be loaded into and out of the registers from RAM at the moments they are needed.
Register allocation is the process of planning this in advance when constructing machine code, with the aim to keep execution of the target program as fast as possible (usually by keeping the number of loads and stores between RAM and registers as small as possible).
Register allocation is NP-complete. Traditional allocators perform global register allocation using a graph coloring algorithm devised by Chaitin et al. More recently, optimal algorithms have been developed by Goodwin and Wilken using Integer Programming for regular architectures. These algorithms have been extended by Kong and Wilken for irregular architectures.
Graph coloring allocators produce efficient code, but their allocation time is high. In cases of static compilation, allocation time is not a significant concern. In cases of dynamic compilation, such as just-in-time (JIT) compilers, fast register allocation is important. An efficient technique proposed by Poletto and Sarkar is linear scan allocation (http://www.research.ibm.com/jalapeno/papers/toplas99.pdf). This technique requires only a single pass over the list of variable live ranges. Ranges with short lifetimes are assigned to registers, whereas those with long lifetimes tend to be spilled, or reside in memory. The results are comparable with graph coloring allocators.