Register allocation

In compiler optimization, register allocation is the process of assigning local automatic variables and expression results to a limited number of processor registers. Register allocation can happen over a basic block (local register allocation), over a whole function/procedure (global register allocation), or across function boundaries traversed via call-graph (interprocedural register allocation). When done per function/procedure the calling convention may require insertion of save/restore around each call-site.

In compiler optimization, register allocation is the process of assigning local automatic variables and expression results to a limited number of processor registers. Register allocation can happen over a basic block (local register allocation), over a whole function/procedure (global register allocation), or across function boundaries traversed via call-graph (interprocedural register allocation). When done per function/procedure the calling convention may require insertion of save/restore around each call-site. ===Common problems raised in register allocation=== Register allocation raises several problems that can be tackled (or avoided) by different register allocation approaches. Three of the most common problems are identified as follows: Aliasing: In some architectures, assigning a value to one register can affect the value of another: this is called aliasing. For example, the x86 architecture has four general purpose 32-bit registers that can also be used as 16-bit or 8-bit registers. In this case, assigning a 32-bit value to the eax register will affect the value of the al register. Pre-coloring: This problem is an act to force some variables to be assigned to particular registers. For example, in PowerPC calling conventions, parameters are commonly passed in R3-R10 and the return value is passed in R3. NP-Problem: Chaitin et al. showed that optimal register allocation is an NP-complete problem. This NP-completeness is entirely dependent upon exactly how the problem is structured. It has been shown that for programs in SSA form, the graph coloring portion of the register allocation problem can be solved in linear time. What causes the general graph coloring problem to be NP-complete and what causes the some versions of the register allocation problem to be NP-complete are distinct. if length(active) = R then SpillAtInterval(i) else register[i] ← a register removed from pool of free registers add i to active, sorted by increasing end point ExpireOldIntervals(i) for each interval j in active, in order of increasing end point do if endpoint[j] ≥ startpoint[i] then return remove j from active add register[j] to pool of free registers SpillAtInterval(i) spill ← last interval in active if endpoint[spill] > endpoint[i] then register[i] ← register[spill] location[spill] ← new stack location remove spill from active add i to active, sorted by increasing end point else location[i] ← new stack location ===Rematerialization=== ==See also== Strahler number, the minimum number of registers needed to evaluate an expression tree. Register (keyword), the hint in C and C++ for a variable to be placed in a register. Sethi–Ullman algorithm, an algorithm to produce the most efficient register allocation for evaluating a single expression when the number of registers required to evaluate the expression exceeds the number of available registers. ==References== ==External links== A Tutorial on Integer Programming Conference Integer Programming and Combinatorial Optimization, IPCO The Aussois Combinatorial Optimization Workshop Bosscher, Steven; and Novillo, Diego. GCC gets a new Optimizer Framework. An article about GCC's use of SSA and how it improves over older IRs. The SSA Bibliography. Extensive catalogue of SSA research papers. Zadeck, F. Kenneth. "The Development of Static Single Assignment Form" , December 2007 talk on the origins of SSA. VV.AA. "SSA-based Compiler Design" (2014) Citations from CiteSeer Optimization manuals by Agner Fog - documentation about x86 processor architecture and low-level code optimization

Text derived from https://en.wikipedia.org/w/index.php?oldid=1353703885 under CC BY-SA 4.0; modifications have been made.