HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

A New Fast Algorithm for Optimal Register Allocation in Modulo Scheduled Loops

Sylvain Lelait 1 Guang R. Gao Christine Eisenbeis 1
1 A3 - Advanced analysis to code optimization
UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France
Abstract : In this paper, we focus on the register allocation phase of software pipelinin- g. We are interested in optimal register allocation. This means that the number of registers used must be equal to the maximum number of simultaneously alive variables of the loop. Usually two different means are used to achieve this, namely register renaming or loop unrolling. As these methods have both drawbacks, we introduce here a solution which is a trade-off between inserting {\em move} operations and unrolling the loop. We present a new algorithmic framework of optimal register allocation for modulo scheduled loops. The proposed algorithm, called U&M, is simple and efficient. We have implemented it in MOST (Modulo Scheduling Toolset). An experimental study of our algorithm on more than 1000 loops has been performed and we report asummary of the main results. This new algorithm, that combines loop unrolling and register renaming, performs consistently better than several other existing methods.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 12:36:11 PM
Last modification on : Friday, January 21, 2022 - 4:04:19 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:51:48 PM


  • HAL Id : inria-00073352, version 1


Sylvain Lelait, Guang R. Gao, Christine Eisenbeis. A New Fast Algorithm for Optimal Register Allocation in Modulo Scheduled Loops. [Research Report] RR-3337, INRIA. 1998. ⟨inria-00073352⟩



Record views


Files downloads