Register allocation

Register allocation assigns program values to a processor’s limited registers during compilation. It aims to keep frequently used values in registers while preserving correct program behavior.

Live-variable analysis: A compiler analysis that determines where each variable’s current value may be used in the future. Its live ranges reveal which values need distinct registers at the same time.
Compiler: Software that translates source programs into another representation or executable code. Register allocation is usually performed as part of translating intermediate code into machine code.
Graph-coloring register allocation: A register-allocation strategy that models conflicts as a graph and assigns registers through graph coloring. It is a widely used strategy for balancing register use against spilling.
Just-in-time compilation: Compilation performed during program execution, typically translating code shortly before it runs. Its time constraints favor fast allocation methods such as linear scan.
Interference graph: A graph connecting entities that cannot share a resource under specified constraints. In register allocation, edges connect simultaneously live values that cannot occupy one register.
Intermediate representation: A compiler’s structured, machine-independent representation of a program. Allocators commonly analyze values and instructions in this representation before emitting machine code.
Priority-based register allocation: A family of allocation strategies that rank values or live ranges when assigning scarce registers. Priority heuristics provide alternatives to explicit interference-graph coloring.
Calling convention: A set of rules governing function calls, including argument passing and register preservation. The allocator must respect which registers calls may overwrite and which must be preserved.
Graph coloring: The assignment of colors to graph vertices so adjacent vertices receive different colors. Register assignment can be modeled as coloring an interference graph with registers as colors.
Control-flow graph: A directed graph whose nodes are program blocks and whose edges represent possible transfers of control. Control-flow paths determine where values remain live across branches and loops.

Linked from 6 pages