Rotating register allocation with multiple rotating branches

Abstract

A rotating register file is an architectural support for software pipelining, where many registers can be renamed at once when a rotating branch is executed. It has primarily been used for overcoming the cross-iteration register overwrites in modulo-scheduled, straight-line or if-converted loops. Recently, a new technique has been proposed to use rotating registers for loops with arbitrary control flows, scheduled by enhanced pipeline scheduling (EPS). EPS generates many hard-to-delete copies to overcome the cross-iteration register overwrites, but these copies may cause a stall in addition to taking resources. The proposed technique eliminates those copies by allocating rotating registers, avoiding a serious slowdown caused by them. Unfortunately, it could not eliminate enough copies, as much as those removed by the unroll-based copy elimination technique, although both techniques employ the same abstraction called an extended live range (ELR). This is due to the limitation that only a branch edge can be a rotating branch, while any edge can be an unrolling edge. In this paper, we propose an enhanced rotating register allocation technique where we can use more than one rotating branches in order to eliminate more copies. This requires an extension of the theory of ELR and the rotating register allocation algorithm. Our experimental results indicate that our proposed technique can eliminate 20% more copies than the previous technique, which results in a performance improvement as much as more than 10%.