Next: MINIMUM LOCAL REGISTER ALLOCATION Up: Code Generation Previous: Code Generation Index

### MINIMUM REGISTER SUFFICIENCY

- INSTANCE: Directed acyclic graph .

- SOLUTION: Computation for G that uses k registers, i.e., an ordering of the vertices in V and a sequence of subsets of V, each satisfying , such that S0 is empty, Sn contains all vertices with in-degree 0 in G, and, for , , , and Si-1 contains all vertices u for which .

- MEASURE: Number of registers, i.e., k.

- Good News: Approximable within [305].

- Garey and Johnson: PO1