Skip to Main content Skip to Navigation

Cyclic Register Pressure and Allocation for Modulo Scheduled Loops

Sid Touati 1 Christine Eisenbeis 1
1 A3 - Advanced analysis to code optimization
UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France
Abstract : In a previous work, we have introduced the notion of register saturation in directed acyclic graphs (basic blocks) which is the maximal number of registers needed to complete a computation in a multiple issue processor. In this report, we extend our work to the cyclic case¸: given a data dependence graph of a simple loop, the cyclic register saturation is the maximal number of registers needed by any modulo schedule of this DDG. If the register saturation is lower than the number of available registers R, then we can build a software pipelining schedule without including the registers constraints¸: we are sure that any schedule does not need more than R registers, and so no spill code has to be generated. If not, we add some arcs in the DDG such that any modulo schedule would not require more than R registers, while minimizing the critical circuit. Next, we introduce and study the dual notion¸: the cyclic register sufficiency is the minimal number of registers needed by any modulo schedule of the DDG. If this factor is greater than R, spill code cannot be avoided. Finally, we shall show how to construct a cyclic register allocation in the data dependence graph independently from any software pipelined schedule. We insert some anti-depend- ences into the original DDG to express the register reuse relations between statements, such that the number of consumed registers does not exceed R under a fixed execution rate (initiation interval).
Document type :
Complete list of metadata
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 7:54:18 PM
Last modification on : Wednesday, September 16, 2020 - 4:57:21 PM
Long-term archiving on: : Sunday, April 4, 2010 - 10:55:25 PM


  • HAL Id : inria-00072146, version 1



Sid Touati, Christine Eisenbeis. Cyclic Register Pressure and Allocation for Modulo Scheduled Loops. [Research Report] RR-4442, INRIA. 2002. ⟨inria-00072146⟩



Record views


Files downloads