| 
|
Topic: register allocation
topics >
computer science >
programming >
code optimization
Topic:
code optimization by special case analysis
Topic:
intermediate representation of code
Topic:
machine code and assembly language
Topic:
memory cache
Topic:
register arguments to subroutines
Topic:
register allocation by graph coloring
Topic:
register allocation by usage counts
Topic:
register allocation by use-def graphs
Topic:
stack machine
Topic:
temporary data objects
Summary
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: usage density
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: intermediate language
Quote: assign registers to variables with the highest usage density; efficiently captures split live intervals; faster than other allocators [»thamS11_2004]
Subtopic: register spill
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: dynamic programming
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: instruction scheduling
Quote: use dynamic programming to assign index registers in tree-structured programs with minimal cost [»agresWW1_1979]
Subtopic: history
Quote: perform instruction scheduling before and after register allocation
Subtopic: linear scan
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: optimizations
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: track machine state
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: coagulation
Quote: during code generation model machine state by value assignments and their usage counts [»freiRA11_1974]
Subtopic: size of register set
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: stack registers
Quote: code for 4-register PDP-11 can be nearly the same size as for an 8-register one [»yuvaG3_1977]
Quote: caching the top of stack removes register allocation but worsens context switching
[»ditzDR3_1982, OK]
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)