All structured programs have small tree width and good register allocation (Q1271620)

The register-allocation problem for a program written in an imperative language is modeled as the coloring problem of the interference graph of the control-flow graph \(G\) of the program. The lifetime of a variable is a connected subgraph of \(G\), and the interference graph is the intersection graph of the set \(X\) of all lifetimes of variables. For general programs with unrestricted gotos, the control-flow graph can be any graph and so can interference graph. Therefore one cannot in polynomial time color the interference graph. The main result of this paper is the following statement. For structured (goto-free) programs, including for example, short circuit evaluation and multiple exits from loops, it is possible to do register allocation in polynomial time within a factor 4 form optimality.