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

Register Saturation in Data Dependence Graphs

Sid Touati 1 François Thomasset 1
1 A3 - Advanced analysis to code optimization
UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France
Abstract : Register constraints in ILP scheduling can be taken into account during the scheduling phase of a code. The complexity of this problem is very high. In this work, we present a new approach consisting in manipulating data dependence graphs to reduce the number of «potential» \vsa without assuming any schedule. We study theoretically the exact upper-bound of the register need for all valid schedules of a code¸: we call this limit the register saturation. It is used to build a modified data dependence graph such that any schedule of this graph will verify the register constraint- s and avoid introducing spill code. We study the case of Direct Acyclic Graphs and then we extend it to loops intended to software pipelining schedule. Experimental study shows that many DAGs and loops do not need register constraints during scheduling.
Document type :
Complete list of metadata

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


  • HAL Id : inria-00072669, version 1


Sid Touati, François Thomasset. Register Saturation in Data Dependence Graphs. [Research Report] RR-3978, INRIA. 2000. ⟨inria-00072669⟩



Record views


Files downloads