Called Overlapping lifetimes
Using data flow of uses and definitions of variables, set up
use-def chains:
Link a def with all its uses to form a chain
Two program quantities cannot share the same register if their
use-def chains overlap.
Called Overlapping lifetimes
Register Allocation by Coloring
For each program quantity to be allocated to a register,
Create A Node
Draw an arc between nodes whose lifetimes overlap
Colorgraph(n)
Called an Interference Graph
If n registers, and graph can be colored with n
colors, registers can be assigned.
An NP-Complete Problem