Register allocation for data flow graphs with conditional branchesand loops

摘要

A new approach to the problem of register allocation in thenpresence of both conditional branches and loops in a data flow graph isnpresented. The authors algorithm exploits the possibility of registernsharing among mutually exclusive variables using a transformationalnapproach - sets of mutually exclusive variables are transformed into annequivalent set of non-mutually exclusive variables. The transformationalnapproach is extended to the case of data flow graphs with loops. A newnregister allocation algorithm is then used to produce an allocation fornthe non-mutually exclusive variables. From such an allocation, ancorresponding allocation for the original sets of mutually exclusivenvariables is derived. Experimental results show that the approach isnquite effective