The register allocation problem for an imperative program is often mod
eled as the coloring problem of the interference graph of the control-
flow graph of the program. The interference graph of a flow graph G is
the intersection graph of some connected subgraphs of G. These connec
ted subgraphs represent the lives, or life times, of variables, so the
coloring problem models that two variables with overlapping life time
s should be in different registers. For general programs with unrestri
cted gotos, the interference graph can be any graph, and hence we cann
ot in general color within a factor O(n(epsilon)) from optimality unle
ss NP = P. It is shown that if a graph has tree width k, we can effici
ently color any intersection graph of connected subgraphs within a fac
tor ([k/2]+1) from optimality. Moreover, it is shown that structured (
=goto-free) programs, including, for example, short circuit evaluation
s and multiple exits from loops, have tree width at most 6. Thus, for
every structured program, we can do register allocation efficiently wi
thin a factor 4 from optimality, regardless of how many registers are
needed. The bounded tree decomposition may be derived directly from th
e parsing of a structured program, and it implies that the many techni
ques for bounded tree width may now be applied in compiler optimizatio
n, solving problems in linear time that are NP-hard, or even P-space h
ard, for general graphs. (C) 1998 Academic Press.