Topic: register allocation

topics > computer science > programming > Group: code generation

code optimization
code optimization by special case analysis
intermediate representation of code
machine code and assembly language
memory cache
register arguments to subroutines
register allocation by graph coloring
register allocation by usage counts
register allocation by use-def graphs
stack machine
temporary data objects


Efficient code is largely dependent on effective register allocation. Registers contain temporary values and component references, with varying lifetimes. Values not maintained in registers must be stored in memory or on a stack. Global analysis is needed to determine which values may share registers. But one study indicates little effect between the number of available registers and the quality of generated code. Register allocation is most critical at labels where different execution paths merge, and allocated registers must match. Structured programming reduces the number of possible paths. Loop labels are especially difficult, yet critical for efficient code generation. (cbb 5/80)

Some methods are usage counts, use-definition graphs, basic blocks, coalescing locally optimal code, dynamic programming, graph coloring, rules of thumb. A multi-pass approach works well. The first passe collects information on variable liveness and usage; then register allocations for labels are defined and allocation is made using a model of the current assignments.

The early FORTRAN compilers used surprisingly sophisticated, register allocation. Stack models avoid register allocation altogether. (cbb 12/92)

Subtopic: register allocation up

Quote: register allocation maps unlimited symbolic registers into real registers [»chaiGJ_1981]
Quote: if too few registers, need to allocate registers to minimize loads and stores [»freiRA11_1974]
Quote: values can automatically reside in a register, must reside, be destroyed, or be preserved [»webeM2_1980]

Subtopic: usage density up

Quote: assign registers to variables with the highest usage density; efficiently captures split live intervals; faster than other allocators [»thamS11_2004]

Subtopic: intermediate language up

Quote: 32-bit, register-based intermediate language for PL.8; similar to target machines [»auslM6_1982]
Quote: C-- replaces C as a portable assembly language; includes a low-level, reusable run-time system that hides calling conventions and stack allocation; permits register allocation, liveness analysis, and garbage collection [»joneSP9_1999]

Subtopic: register spill up

Quote: except for spilling, graph coloring register allocation did well; avoided spilling by doubling hardware registers to 32 [»auslM6_1982]
Quote: estimate cost of spilling a register by count of definitions, uses, and execution frequency [»chaiGJ2_1986]
Quote: register allocation by computing cost of allocating a variable to a register [»webeM2_1980]
Quote: manage register spills by optimizing the common case where no spills occur; and if necessary, spill the register whose next use is most distant [»frasCW1_1992]

Subtopic: dynamic programming up

Quote: use dynamic programming to assign index registers in tree-structured programs with minimal cost [»agresWW1_1979]

Subtopic: instruction scheduling up

Quote: perform instruction scheduling before and after register allocation

Subtopic: history up

Quote: FORTRAN ordered program areas for register assignment by frequency of execution [»alleFE_1982, OK]
Quote: FORTRAN tried different register assignments if mismatch across basic blocks
Quote: FORTRAN registers assigned in basic blocks by distance_to_next_use [»alleFE_1982]

Subtopic: linear scan up

Quote: use linear scan for global register allocation; up to several times faster than graph coloring, within 12% as efficient [»poleM9_1999]
Quote: binpacking generates better code than linear scan but 2-3x slower; keeps track of lifetime holes [»poleM9_1999]
Quote: linear scan determines the live interval of a variable in the intermediate representation; needs live variable information from data-flow analysis [»poleM9_1999]
Quote: linear scan overhead for live variable analysis and construction of live intervals; experimented with strongly-connected components, but poor code [»poleM9_1999]

Subtopic: optimizations up

Quote: automatic scalars and subroutine arguments should be kept in registers [»chaiGJ_1981]
Quote: allocate registers under the assumption that explicit goto's are rare and loops easily recognized [»webeM2_1980]
QuoteRef: zelkMV1_1974 ;;55 temporaries in registers while variables always stored (not a=5, a=6) but temporizes almost immediately used
Quote: optimizations: loop control variables in registers, unused assignments, strength reduction, duplicate elimination, packed constants [»goodJB8_1976]

Subtopic: track machine state up

Quote: during code generation model machine state by value assignments and their usage counts [»freiRA11_1974]

Subtopic: coagulation up

Quote: do instruction selection and register allocation together by coagulating locally optimal code, most frequent first [»karrM6_1984]
Quote: code generation by coagulation not implemented; expect better code slower [»karrM6_1984]

Subtopic: size of register set up

Quote: code for 4-register PDP-11 can be nearly the same size as for an 8-register one [»yuvaG3_1977]

Subtopic: stack registers up

Quote: caching the top of stack removes register allocation but worsens context switching
[»ditzDR3_1982, OK]

Related Topics up

Topic: code optimization (54 items)
Topic: code optimization by special case analysis (22 items)
Topic: intermediate representation of code (31 items)
Topic: machine code and assembly language (49 items)
Topic: memory cache (29 items)
Topic: register arguments to subroutines (2 items)
Topic: register allocation by graph coloring (21 items)
Topic: register allocation by usage counts (12 items)
Topic: register allocation by use-def graphs (9 items)
Topic: stack machine (10 items)
Topic: temporary data objects
(6 items)

Updated barberCB 12/04
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.