Register allocation for data flow graphs with conditional branches and loops

A new approach to the problem of register allocation in the presence of both conditional branches and loops in a data flow graph is presented. The authors algorithm exploits the possibility of register sharing among mutually exclusive variables using a transformational approach - sets of mutually exclusive variables are transformed into an equivalent set of non-mutually exclusive variables. The transformational approach is extended to the case of data flow graphs with loops. A new register allocation algorithm is then used to produce an allocation for the non-mutually exclusive variables. From such an allocation, a corresponding allocation for the original sets of mutually exclusive variables is derived. Experimental results show that the approach is quite effective