Register Allocation in Structured Programs

In this article we look at the register allocation problem. In the literature this problem is frequently reduced to the general graph coloring problem and the solutions to the problem are obtained from graph coloring heuristics. Hence, no algorithm with a good performance guarantee is known. Here we show that when attention is restricted to structured programs which we define to be programs whose control-flow graphs are series-parallel, there is an efficient algorithm that produces a solution which is within a factor of 2 of the optimal solution. We note that even with the previous restriction the resulting coloring problem is NP-complete. We also consider how to delete a minimum number of edges from arbitrary control-flow graphs to make them series-parallel and to apply our algorithm. We show that this problem is MaxSNP hard. However, we define the notion of an approximate articulation point and we give efficient algorithms to find approximate articulation points. We present a heuristic for the edge deletion problem based on this notion which seems to work well when the given graph is close to series-parallel.