What Does Register Allocation Mean?
Register allocation refers to the practice of assigning variables to registers as well as handling transfer of data into and out of registers. Register allocation may occur:
- On a basic block, known as local register allocation
- Over an entire function or procedure, known as global register allocation
- Over function boundaries traversed by means of a call graph, known as inter-procedural register allocation
Techopedia Explains Register Allocation
During the course of compilation, the compiler should determine the way in which variables are allocated to a small, specific range of registers. Some of the variables may not be in use or are said to be "live" simultaneously. This leads to assigning some registers to multiple variables. Nonetheless, no two simultaneous live variables can be allotted to the exact same register without corrupting the value.
Variables that cannot be allotted to some registers need to be stored in RAM and should be loaded in and out for each read and write, respectively, a procedure known as spilling. Accessing registers is much faster than accessing RAM. In addition, it speeds up the execution time of the compiled program; therefore, efficient compilers aim at assigning as many variables to registers as they can.
Generally, most register allocators assign every variable to main memory or a central processing unit (CPU) register. Speed is the key benefit when using a register. Computers feature a finite range of registers, which means that not all the available variables can be allotted to registers. The process of shifting a variable from a register to the memory is known as spilling, whereas the reverse procedure of moving a variable from memory to a register is known as filling. Intelligent register allocation is a crucial step for any compilers.
There are two types of register allocation:
- Local register allocation: This is a process of allocating one basic block (or hyper block or super block) at a time. Local register allocation boosts speed.
- Global register allocation: If the register utilization is poor using local allocation, it is important to make use of global register allocation. In simple global register allocation, the most active values are allocated in every inner loop. Full global register allocation uses a procedure to identify live ranges in a control flow graph, assign live ranges and also split ranges as required.