The task of register allocation is to map virtual registers to a limited number of physical registers. The number of virtual registers may be reduced by splitting live ranges into smaller ones (resulting in additional costs for moving values from one register to another) or by assigning a location in memory to a virtual register (increasing the costs to access the values). As other techniques do, the fusion-based approach considers register allocation as a problem of coloring an interference graph, the nodes of which represent live ranges connected by edges if they exist simultaneously. It starts by considering the interference graphs for regions, which may be defined by any suitable technique and may range from basic blocks to large blocks. Then, graphs are fused step-by-step along edges. The earlier an edge is considered by the fusion process, the less likely it is that live ranges are split along that edge. Therefore, register allocation can be controlled by suitably ordering the edges and forming regions.
The first two sections introduce both the problem and the terminology clearly, making the paper self-contained. In the third section, the authors briefly describe the phases that are typical of their approach and go into the details of the fusion operation. In section 4, they review other approaches and compare the approach with an improved Chaitin-style approach. Finally, they discuss experiments concerning compilation and execution time.
Overall, this is a clearly written research paper of interest mainly to compiler designers.