ALL STRUCTURED PROGRAMS HAVE SMALL TREE WIDTH AND GOOD REGISTER ALLOCATION

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.