Register allocation
In computer science, register allocation is the assignment of variables or intermediate computations from a high-level language (HLL) to physical registers or memory locations. Register allocation occurs during the code generation phase of a compiler.
Typically, a compiler will translate a source language written in an HLL to a target in assembly language or machine code. There are a few critical differences between the source and target languages. In particular, HLLs allow for a large or unlimited number of variables, while the typical microprocessor only allows for efficient access to a small number of variables, called registers, and inefficient access to main memory. For efficiency reasons, there is incentive to place as many variables as possible into registers, and as few as possible into memory.
Since only a small percentage of the variables within a computer program are used at one time, there is an opportunity to place multiple variables into the same register---but only if those variables are not used at the same time.
More formally, if at any point during program execution two variables each hold some value that will later be read by a future operation, then those two variables are said to interfere. Unfortunately, it is not always possible to determine if two variables interfere (a consequence of the halting problem), and thus a compiler must act conservatively and assume that they do interfere unless they can be shown not to.
The register allocation problem is to assign a register or memory location to each variable in a computer program, in such a way that no two interfering variables share a register or memory location. A trivial solution to the register allocation problem is to assign each variable a distinct memory location using a stack frame. Although this solution produces correct results, they are generally quite inefficient in computation time and memory space.
The most popular solution to the register allocation problem is register allocation by graph coloring as presented by Briggs in 1992.