Optimistic coalescing for heterogeneous register architectures

In this paper, Optimistic coalescing has been proven as an elegant and effective technique that provides better chances of safely coloring more registers in register allocation than other coalescing techniques. Its algorithm originally assumes homogeneous registers which are all gathered in the same register file. Although this register architecture is still common in most general-purpose processors, embedded processors often contain heterogeneous registers which are scattered in physically different register files dedicated for each dissimilar purpose and use. In this work, we developed a modified algorithm for optimal coalescing that helps a register allocator for an embedded processor to better handle such heterogeneity of the register architecture. In the experiment, an existing register allocator was able to achieve up to 10% reduction in code size through our coalescing, and avoid many spills that would have been generated without our scheme.