Register Pressure in Instruction Level Parallelism

"Sid Ahmed Ali TOUATI" <Sid-Ahmed-Ali.TOUATI@inria.fr>
28 Jun 2002 18:41:42 -0400

          From comp.compilers

Related articles
Register Pressure in Instruction Level Parallelism Sid-Ahmed-Ali.TOUATI@inria.fr (Sid Ahmed Ali TOUATI) (2002-06-28)
| List of all articles for this month |

From: "Sid Ahmed Ali TOUATI" <Sid-Ahmed-Ali.TOUATI@inria.fr>
Newsgroups: comp.compilers
Date: 28 Jun 2002 18:41:42 -0400
Organization: INRIA
Keywords: parallel, optimize, available
Posted-Date: 28 Jun 2002 18:41:42 EDT

Dear all,


I am honored to announce the final fulfillment of my Ph.D. degree in
computer science. My thesis is titled :


                "Register Pressure in Instruction Level Parallelism"


It was defended in June, 25 th 2002 at the University of Versailles
(FRANCE). The Ph.D. committee was composed of :


1. Pr. William Jalby, University of Versailles, Director
2. Dr. Christine Eisenbeis, INRIA, Director
3. Dr. Alain Darte, ENS Lyon, Referee
4. Pr. Reinhard Wilhelm, University of Saarlandes, Referee
5. Dr. Michael Schlansker, HP Labs, Referee
6. Pr. Dominique Barth, UVSQ, President
7. Pr. François Bodin, University of Rennes


An electronic version of the thesis can be retrieved via anonymous FTP
from the following address :
ftp://ftp.inria.fr/INRIA/Projects/a3/touati/thesis


A long version of the slides are available on :
http://www-rocq.inria.fr/~touati/thesis/slides


I would appreciate any feedback.


ABSTRACT
=========


It has become a truism that memory accesses play the major role of
degrading program performance. This is because the continuous increasing
of the gap between instruction level parallelism (ILP) processor speed
and memory access latency. Optimizing compilers must avoid requesting
data from memory if possible by using at the best the available
registers of underlying hardware.


This thesis reconsiders the register pressure concept so that it gets
higher priority than ILP scheduling, but with full respect to intrinsic
fine grain parallelism. We propose to handle register pressure early in
optimization process, before instruction scheduling. Two main strategies
are developed.


In the first strategy, we handle data dependence graphs (DDGs) so that
we guarantee register constraints without increasing critical execution
paths if possible. We introduce and study the concept of register
saturation (RS), which is the exact upper-bound of register requirement
for all valid schedules independently of architectural constraints. Its
aim is to add some serial arcs to the original DDG such that the worst
register need does not exceed the number of available registers. On the
other hand, register sufficiency (RF) is the exact minimal register
requirement. Its aim is to detect unavoidable spilling decisions when it
exceeds the number of available registers. After RS and RF analysis
steps, ILP scheduler is free from register constraints and final
allocator may not require avoidable spilling.


Our second strategy consists in directly applying an early register
allocation with optimized ILP loss. It is built directly into the input
DDG and hence register constraints are fixed.


Our thesis addresses basic blocks, acyclic control flow graphs (multiple
basic blocs with branches) and innermost loops intended for software
pipelining. We assume a generic architecture model so that it matches
current ILP processors. We give an exact formulation with integer
programming for all register pressure problems. We also provide
algorithmic solutions. Experimental results show that our heuristics are
nearly optimal. Our thesis proves that we can and must handle register
constraints early while keeping freedom for a further ILP scheduling.
This is more beneficial than a combined approach which tries to carry
out register allocation and ILP scheduling in a single complex pass.


KEYWORDS
==========
Instruction Level Parallelism, Register Allocation, Register Saturation,
Register Requirement, Register Sufficiency, Software Pipelining, Integer
Linear Programming, Code Optimization, Optimizing Compilation.


--
====================================================================
e-mail : Sid-Ahmed-Ali.Touati@inria.fr
URL : http://www-rocq.inria.fr/~touati
adresse : Projet A3. Inria-Roquencourt. Domaine de Voluceau, BP 105
                    78153 Le Chesnay cedex France
tel : 01 39 63 58 02
fax : 01 39 63 59 95
====================================================================


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.