11.6.1 Register Allocation vs.Assignment

11.6.2 Register Allocation Schemes

11.6.3 Register Allocation by Usage Counts

11.6.4 Register Allocation by Graph Coloring

11.6.5 Register Assignment and Reassignment

11.6.4 Register Management

11.6.4 Register Allocation by Graph Coloring

Using data flow of uses and definitions of variables, set up use-def chains:

    A Use of a variable A is reached from the assignment A = if there is some path from the assignment along which A is used before being redefined.

    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

    Algorithm

    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