Register allocation
From Wikipedia, the free encyclopedia
In compiler optimization, register allocation is the process of multiplexing a large number of target program variables onto a small number of CPU registers. The goal is to keep as many operands as possible in registers to maximise the execution speed of software programs. Register allocation can happen over a basic block (local register allocation) or a whole function/procedure (global register allocation).
Most computer programs need to process large numbers 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.
[edit] Challenges
Register allocation is an NP-complete problem. The number of variables in a typical program is much larger than the number of available registers in a processor, so the contents of some variables have to be spilled (saved) into memory locations. The cost of such spilling is minimised by spilling the least frequently used variables first, however it is not easy to know which variables will be used the least. In addition to this the hardware and operating system may impose restrictions on the usage of some registers.
[edit] Global register allocation
Like most other compiler optimizations, register allocation is based on the result of some compiler analysis, mostly the result of live variable analysis from data flow analysis.
Traditional allocators perform global register allocation using a graph coloring algorithm devised by Chaitin et al. It can be divided into two phases:
- Machine instructions are generated as if there are an infinite number of symbolic registers. So all variables suitable to being in registers will be assigned to numbered logical registers. The phase is sometimes called register variable recognition.
- symbolic registers are replaced by physical registers in a target machine, with the minimum cost of spills.
In phase two, a graph is constructed where nodes are symbolic registers and an edge connects two nodes if one is live when the other is defined, which means two variables will be live together some time during the execution. The problem then equals to color the graph using k colors, where k is the number of actual available physical registers. To do so, the graph is reduced in size in repeating steps until no further simplication is possible
- Removing action: Repeatedly remove a node in graph if it has fewer than k neighbors connected by edges. Also remove related edges. This step eliminates all variables with less than k other concurrently living variables.
- Stop: If the result simplified graph has no nodes left, all removed nodes will be colored in the reverse order in which they were removed, ensuring a different color is used compared to its neighbors.
- Spilling action: If the result graph have nodes left and each of them has more than k neighbors, choose one node to be spilled. Remove the spilled node and its edges and repeat the removing and spilling actions until the graph is empty.
Major attention has been paid to choose the right nodes to be spilled. The less frequently used variables are often the victims.
[edit] Recent development
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. 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.
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.
While the worst case execution time is exponential, the experimental results show that the actual time is typically of order O(n2.5) of the number of constraints (Kong, Wilken, Precise Register Allocation for Irregular Architectures, [1]).
