An approximation algorithm for the register allocation problem

In this paper we study the problem of register allocation in the presence o f parallel conditional branches with a given branching depth d. We start fr om a scheduled flow graph and the goal is to find an assignment of the vari ables in the flow graph to a minimum number of registers. This problem can be solved by coloring the corresponding conflict graph G = (V, E). We descr ibe a new approximation algorithm with constant worst case rate for flow gr aphs with constant branching depth. The algorithm works in two steps. In the first step, the lifetimes are enla rged such that the lifetimes form one unique interval across the different possible execution paths for each variable. We prove that the conflict grap h G with enlarged lifetimes satisfies omega((G) over bar)) less than or equ al to (2d + 1)omega(G) where omega(G) is the cardinality of a maximum cliqu e in G. In the second step, we propose an algorithm with approximation boun d (d + 1)chi((G) over bar for (G) over bar, using its specific structure. ( C) 1998 Elsevier Science B.V. All rights reserved.