Mes Remerciements

M Pierre Boulet

M Fabrice Rastello

Florent Bouchez

Mounira

Mouad, Michael, Ryiadh, Soane, Zheng, Walid, Ramakrishna, Cédric, Luidnel, Konrad Grigori Taj

Louis Phillipe

Olivier Noel

L'heure est venue de dire merci à tous ceux qui de près ou de loin m'ont soutenu, aidé ou encouragé durant ces années de thèse ou durant la redaction de ce manuscrit. Je suis conscient qu'il me faudrait sans doute l'équivalent d'un autre manuscrit pour remercier tout le monde monde et n'oublier personne. De ce fait, je tiens à remercier tous ceux dont les noms n'apparaissent pas dans ce document et qui m'ont, ne serait ce qu'une fois, aidé dans ma vie, même si ce fût par un petit sourire.

La première personne que je tiens à remercier est Albert Cohen, mon directeur de thèse, pour avoir accepté de diriger cette thèse. Je tiens aussi a le remercier pour toute la conance qu'il m'a accordé, sa gentillesse et ses conseils.

iii Je dédie cette thèse à ma mère Fatoumata Traoré, à mon père Alioune Diouf, à ma marraine Ta Ba, à mes nièces et neuveux, à qui j'ai donné le surnom de : The next generation, et à mon ami Cheikh Ada, notre voyage ensemble n'a pas duré bien longtemps. Puisse Dieu nous unir de nouveau dans ses hauts jardins

Introduction xxi

Résumé

Les programmes informatiques sont souvent écrits dans des langages de haut niveau et puis traduit en code machine, une forme dans laquelle ils pourront être exécutés par les ordinateurs. Cette traduction est eectuée par un logiciel appelé, compilateur. Globalement le rôle d'un compilateur est de traduire un programme source en un programme cible sans en modier la sémantique; il doit aussi signaler toutes les erreurs qu'il détecte durant le processus de traduction et essayer d'optimiser le code généré. Le programme cible peut être traduit en code machine ou dans un autre langage de programmation. Les optimisations eectuées, par le compilateur, cherchent à minimiser le temps d'execution, et ou, la taille du programme cible.

Le temps d'exécution d'un programme dépend du nombre d'instructions à exécuter mais aussi de la durée que prend chacune de ces instructions à s'exécuter. La durée d'exécution d'une instruction quant à elle peut varier d'une nanoseconde à plusieurs millisecondes selon le temps pris pour accéder aux données stockées dans la mémoire.

La variance dans les temps d'accès à la mémoire est due à une limitation technologique fondamentale: il est possible de concevoir des mémoires de petites capacités à accès rapide, il est aussi possible de concevoir des mémoires de grandes capacités à accès lent, mais il est impossible de concevoir des mémoires de grandes capacités à accès rapide. Il est impossible de fabriquer une mémoire de plusieurs giga-octets accessible en une nanoseconde, ce qui est la performance des processeurs hautes performances actuels. Pour réduire cette diérence de performance entre le processeur et la mémoire, les ordinateurs modernes utilisent une hierarchie mémoire. Cela correspond à une organisation de la mémoire en plusieurs niveaux. Les mémoires rapides et de petites capacités sont placées à coté du processeurs, ce qui accèlére les accès, alors que celles de grandes capacités et lentes en sont éloignées.

La gure 1 est un exemple de hierarchie mémoire typique utilisée dans les ordinateurs modernes. Les unités mémoires les plus proches du processeurs sont les registres (situés dans le processeur) qui sont les plus rapides d'accès dans un ordinateur. Ensuite, nous avons une mémoire RAM statique (SRAM) de petite capacité, souvent congurée en un ou plusieurs niveaux de mémoire-cache, allant de quelques kilo-octets à plusieurs mega-octets. La mémoire physique ou mémoire principale allant de quelques centaines de mega-octets à plusieurs giga-octets, faite de mémoire RAM dynamique (DRAM) représente le niveau suivant. Enn, le dernier niveau est formé par la mémoire virtuelle avec une capacité de plusieurs gigaoctets. Lorsqu'un accès mémoire survient, l'ordinateur cherche la donnée dans la mémoire la plus proche du processeur, et si la donnée ne s'y trouve pas, elle Les mémoires SRAM sont généralement congurées comme des mémoires caches gérées par le matériel. Une seconde conguration possible est de les gérer de manière logicielle. Dans le cas d'une gestion logicielle les mémoires SRAM, mémoire(s) locale(s), le développeur ou le compilateur insère explicitement des intructions pour transfèrer les données de la mémoire locale vers la mémoire principale. Les registres aussi, comme les mémoires locales, sont gérés de manière logicielle. Tous les autres niveaux de la mémoire sont gérés automatiquement.

Les registres sont les mémoires plus rapides d'accès, mais ils existent en trés petite quantité. Généralement toutes les variables d'un programme ne peuvent pas être stokées dans des registres. Les variables pour lesquelles il n'ya pas de registres disponibles sont stokées dans les couches supérieures de la mémoire qui sont plus éloignées du processeur, donc plus lentes. Pour réduire les accès à ces niveaux supérieurs, il convient donc d'utiliser au mieux les registres de la machine. Dans les compilateurs actuels, ce rôle est dédié à une optimisation appelée: allocation de registres. L'allocateur de registres attribue à chacune des variables du programme, soit un registre, soit un emplacement en mémoire. L'allocation de registres se décompose en deux étapes: l'allocation qui détermine à chaque xiii point du programme l'ensemble des variables (variables allouées) qui seront stockées en registres et l'assignation qui choisit un registre spécique pour chaque variable allouée.

De même que pour les registres, Il est important d'optimiser l'utilisation de la mémoire locale pour éviter d'accéder aux niveaux supérieurs de la mémoire, qui sont plus lents.

Dans les compilateurs, l'optimisation en charge de la gestion de la mémoire locale est appelée allocation de mémoire locale. L'allocateur de mémoire locale selectionne l'ensemble des variables qui seront stockées dans la mémoire locale à chaque point du programme.

Il choisit aussi pour chaque variable l'emplacement spécique qu'il va occuper, soit en mémoire locale, soit en mémoire principale. L'allocation de registres et l'allocation de mémoire locale sont deux problèmes qui sont NP-complets auxquels nous nous intéréssons dans cette thèse, qui est structurée en trois parties.

Dans la première partie de la thèse, nous nous penchons sur le problème de l'allocation de registres. Tout d'abord, nous proposons dans le contexte des compilateurs-juste-àtemps, une allocation de registres fractionnées, appelée split register allocation. Avec cette approche l'allocation de registres est eectuée en deux étapes: une faite durant la phase de compilation statique et l'autre pendant la phase de compilation dynamique. Ce qui permet de réduire le temps d'exécution des programmes avec un impact négligeable sur le temps de compilation. Ensuite Nous introduisons une allocation de registres incrémentale qui permet de résoudre d'une manière quasi-optimale le problème d'allocation. Cette méthode est pseudo-polynomiale alors que le problème d'allocation est NP-complet même à l'intérieur d'un basic block.

Dans la deuxième partie de la thèse nous nous intéressons au problème de l'allocation de mémoire locale. Au vu des dernières avancées dans le domaine de l'allocation de registres, nous étudions dans quelle mesure le problème d'allocation pourrait être séparé de celui de l'assignation dans le contexte des mémoires locales. Dans un premier temps nous validons expérimentalement que les problèmes d'allocation et d'assignation peuvent être résolus séparément. Ensuite, nous procédons à une étude plus théorique d'une approche découplée de l'allocation de mémoire locale. Cela permet d'introduire de nouveaux résultats sur le submarine-building problem, une variante du ship-building problem, que nous avons déni. L'un de ces résultats met en évidence pour la première fois une différence de complexité (P vs. NP-complet) entre les graphes d'intervalles et les graphes d'intervalles unitaires.

Dans la troisième partie de la thèse nous proposons une nouvelle heuristique, appelée clustering allocator fondée sur la construction de sous-graphes stables d'un graphe d'interférence, permettant de découpler aussi bien le problème d'allocation pour les regxiv istres que pour les mémoires locales. Cette nouvelle heuristique se veut le pont qui permettra de réconcilier les problèmes d'allocations de registres et de mémoire locale.

1 Allocation de Registres L'allocation de registres est un problème NP-complet. En eet, Chaitin et Dans cette première partie, nous proposons deux nouvelles techniques à savoir l'allocation de registres fractionnées, qui cherche à améliorer l'allocation de registres dans le contexte de la compilation juste-à-temps (JIT) et l'allocation de registres optimale itérée qui s'attaque au problème de la spill minimization.

Allocation de Registres Optimale Itérée

Les travaux en allocation de registres ont montré que lorsque les live ranges des variables sont assez nement découpés alors le problème de l'assignation devient quadratique dés lors qu'une allocation est possible. Il sut juste que le nombre maximal de variable en vie en un point du programme soit inférieur au nombre de registres disponibles. Cependant le problème de la minimisation de spills demeure NP-complet même à l'intérieur d'un basic block [START_REF] Farach-Colton | On local register allocation[END_REF]. Les solutions proposées pour la résolution sont loin d'être optimales. Ce problème est d'autant plus important sur les machines CISC, où le nombre de registres est trés limité.

Nous nous sommes attaqués au problème de la minimisation de spills. Notre approche, appelée allocation de registres optimale itérée, permet de résoudre le problème d'allocation de manière quasi-optimale et ceci rapidement. Notre solution peut être utilisée dans un contexte découplé ou non. Nous avons comparé notre approche avec la coloration de graphe, le linear scan, une nouvelle heuristique que nous avons conçu et appelé heuristique mixte et une allocation de registres optimale par programmation linéaire. Les résultats montrent que L'allocation de registres optimale itérée est souvent proche de xv l'allocation de registres optimale et produit de bien meilleurs résultats que les autres heuristiques. Un résultat trés intéréssant de notre approche est que, pour les programmes sous SSA, nous avons une garantie de pseudo-polynomialité.

Allocation de Registres Fractionnée

Dans le contexte de la compilation JIT, la compilation fait partie du processus global d'exécution des programmes. Ceci implique un compromis entre le temps de compilation, donc des optimisations et celui du temps d'exécution du code généré. En pratique, l'utilisation d'algorithmes de compléxité linéaire reste la régle pour la compilation JIT.

Notre approche de l'allocation de registres fractionnée montre qu'une compléxité linéaire n'implique pas forcément une réduction de la qualité du code généré. Notre approche est un exemple de compilation fractionnée, ou les analyses couteûses sont eectuées en avance pour guider des optimisations quasi-linéaires. Les informations collectées dans la phase hors-ligne de compilation statique, sont transmises à la phase en ligne, de compilation juste-à-temps, au moyen d'annotations de bytecode.

Notre allocateur de registres fractionnée garantie quatre propriétés: des annotations avec un impact minimal sur la taille du code, un traitement des annotations en temps linéaire, une perte minimale en qualité de code et la portabilité des annotations lorsque le nombre de registres disponibles varient. Nous avons implanté notre technique d'allocation de registres fractionnée dans JIkesRVM, la machine virtuelle de recherche d'IBM.

2 Allocation de Mémoire Locale Dans la majorité des systèmes embarqués, les mémoires locales sont préférées au caches, du fait des garanties qu'elles orent en prédictibilité, en adaptabilité (passage à l'échelle), L'allocation de mémoire locale est connectée à l'allocation de registres depuis au moins 30 ans. En eet, dans son papier phare [START_REF] Fabri | Automatic storage optimization[END_REF], Fabri a démontré l'existence de liens forts entre les allocations de registres et de mémoire locale. Ces liens ont été sous-exploités depuis lors et par conséquant, les nouvelles avancées, réformant le design des backend des compilateurs, dans le domaine de l'allocation de registres ont été complétement ignorées en allocation de mémoire locale. Notre travail sur l'allocation de registres a été motivé par les récéntes avancées en allocation de registres et par la volonté de mieux comprendre le probléme d'optimisation.

Validation expérimentale

Pour valider notre intuition d'une approche découplée de l'allocation de mémoire locale, similairement à l'approche découplée en allocation de registres, nous avons exprimé

Etude théorique

Aprés avoir expérimentalement validé une approche découplée de l'allocation de registres, nous avons pris une approche plus théorique qui a aboutit à des résultats fondamentaux dans le domaine de la gestion des mémoires locales par les compilateurs. Nous avons montré que la gestion des mémoires locales peut se modéliser comme un problème de coloration de graphes pondérés et nous avons étudié plusieurs variantes de ce problème.

Ce qui a mené aux contributions suivantes:

1. L'introduction d'une nouvelle forme de coloration par intervalle que nous avons appelé submarine-building.

2. Un nouvel algorithme linéaire et optimal résolvant le problème du submarinebuilding pour tout graphe d'intervalle propre et une preuve de NP-complétude de ce problème pour les graphes d'intervalle.

3. L'introduction d'un critère permettant de décider de la faisabilité ou non d'un problème de submarine-building sur les graphes d'intervalle propre. Lorsque le critère est satisfait, l'algorithme linéaire et optimal de résolution des problèmes submarinebuilding permet de résoudre le ship-building problème pour les graphes d'intervalle propre. and then translated into an executable code, a form in which they can be executed by these computers. This translation is done by a software program, called a compiler. Globally, the role of a compiler is to translate a source program into a target program without changing the semantics of the source code; it must also report any errors that it detects during the translation and try to optimize the generated target code. The target program can be an executable code or a program written in another programming language. The optimizations, done by a compiler, try to minimize the execution time, and or, the size of the target program.

When a programmer compiles a program from a source language to an executable code, he wants the compiled one to conserve the source code's semantics. He also wants the code to run in an acceptable time. The execution time depends on the number of instructions to compute, and also on the computation time of each of these instructions. The computation time of an instruction can vary signicantly, from nanoseconds to milliseconds, depending on the time taken to access data in memory.

The variance in memory access times is due to technological limitations: we can make small storage with fast access-time, we also can make large storage with slow access-time, but we cannot make large storage with fast access-time. It is impossible to make gigabytes of memory to be accessed in a nanosecond, the speed of high-performance processors. To reduce this performance gap between the processor and the memory, modern computers use a memory hierarchy. It corresponds to an organization of the memory into dierent levels of hierarchy. The faster and smaller levels of memory are placed closer to the processor, this speeds up access, and the slower and larger ones are placed farther from the processor.

Figure 1, taken from the Dragon Book [START_REF] Aho | Compilers: Principles, Techniques, and Tools[END_REF], shows an example of a typical memory hierarchy in a modern computer. The closest memory level to the processor is composed of a few registers (located in the processor) that are accessed faster than any other kind of memory. Then, we have a small amount of on-chip static RAM (SRAM), xxii Introduction usually congured as one or many levels of hardware-managed cache, going from some kilobytes to many megabytes in size. The next level is the physical (main) memory, made of dynamic RAM (DRAM), going from hundreds of megabytes to many gigabytes.

Finally, the last level in the hierarchy is the virtual memory with a size of many gigabytes. When a memory access occurs, the computer tries to nd the data in the closest memory, and then if the data is not there, it tries in the higher level, and so on.

123456789A9B3C8DE2F 123456789A9B3C8DE2F CF26789A9B3C CF26789A9B3C E7AA786A E7AA786A F47AA786A F47AA786A A2F4A3F8D3BAFFB3 A2F4A3F8D3BAFFB3 1234562789 1234564AA9226B7C9 B3A84688 !8888 !8"88#8 !88!#8" $8%B3EF $88 89F &&88 &8F #&88!&8F 88&8F 8F
Figure 1: A typical memory hierarchy conguration, from the Dragon book [START_REF] Aho | Compilers: Principles, Techniques, and Tools[END_REF] The alternative approach to manage the SRAM is to congure it as a softwarecontrolled local memory. In such an approach, the developer or the compiler must insert explicit instructions to transfer data between the local memory and the main memory. Like software-controlled local memories, registers also are managed by software. All the other levels of memory are managed automatically.

Register Allocation

Registers are the fastest type of memory within a computer. Registers are quickly accessed, but they exist in a very limited number. Usually, all the values of the executed code cannot reside in registers. The values not held in registers should reside in memory, xxiii which is farther from the processor and therefore slower to access. To reduce access to slower memory, it is essential to have an ecient usage of registers. In all modern compilers, there is a phase called register allocation which optimizes the use of registers. The register allocator, in a phase called allocation, decides at each program point which variables will be held in registers (allocated variables) and which variables will be stored in memory; it also assigns each allocated variable to a register and maps to other variables a location in memory.

The register allocation is NP-complete. Indeed, In this thesis we are interested in two topics: the spill minimization problem and the improvement of the register allocation in the context of Just-in-time (JIT) compilation.

Spill Minimization

Recent works in register allocation have shown that when enough live range splitting is allowed, the assignment problem can be solved in quadratic time as soon as the maximum number of simultaneously living variables is lower than the number of available registers. But unfortunately, the spill minimization problem (an allocation that minimizes the access latency) is still NP-complete even when enough live range splitting is allowed [START_REF] Farach-Colton | On local register allocation[END_REF].

The proposed solutions are far from being optimal. Thus, our aim is to propose good heuristics to solve this problem especially on systems like CISC machines where only few registers are available.

Improvements of JIT Register Allocation

In the context of Just-in-time compilation, the compilation time is part of the global execution process. This implies a trade-o between the time spent for compilation (optimizations) and the execution time of the produced code. In practice, (quasi-)linear complexity is the rule for JIT compilation. This severely impacts the aggressiveness of optimizations, like register allocation. We are interested in solutions that improve register allocation without lengthening the JIT compilation. In most embedded systems, local memories are often preferred to caches due to their better performance and predictability, their power eciency, and their smaller area cost [BSL + 02]. Predictability of data access and power consumption eciency are often essential to realtime and embedded applications. More specialized processors also utilize local memories, including stream-processing architectures such as graphical processors (GPUs) and network processors [START_REF]NVIDIA unied architecture GeForce 8800 GT[END_REF][START_REF] Burns | Implementing address assurance in the Intel IXP[END_REF].

To take advantage of all the potentials provided by local memories, it is essential to use them eciently. Within a compiler, the optimization which performs this task is called local memory allocation. It selects the set of variables that will reside in the local memory at each point of the program. It also nds the specied place in the local memory or in the main memory where a variable will reside in.

The local memory allocation problem is NP-complete [START_REF] Verma | Dynamic overlay of scratchpad memory for energy minimization[END_REF]. Previous studies addressed local memory allocation from dierent angles, targeting both application/code and data. Many heuristics-based approaches to the problem have been proposed [MFA01, VWM04, UDB06, LFX09, LXK11].

Our work on local memory allocation is motivated by the recent advances in register allocation and the desire for a better understanding of the local memory optimization problem.

Link between Register and Local Memory Allocations

Compilation-time local memory allocation has been connected to register allocation for at least 30 years. Indeed, in her seminal paper [START_REF] Fabri | Automatic storage optimization[END_REF], Fabri reported strong links between register allocation and local memory allocation. This have been overlooked until very recently. As a result, the series of, fundamental and applied advances impacting the design of compiler backends have also been ignored in the eld of local memory allocation [AG01, BDGR06a, HGG06, BDR07c, PP08].

The Local Memory Allocation Optimization Problem

While there exist many heuristics to the local memory allocation problem, theoretical foundations of the proposed heuristics are missing. More recently, Li et al. [START_REF] Li | Scratchpad memory allocation for data aggregates via interval coloring in superperfect graphs[END_REF] seriously improved the state of the art by proposing an approach to the problem, that has strong theoretical foundations. Nonetheless, little is known about the optimization problem, its complexity, and its interplay with other optimizations.

Outline xxv 3 Outline

This dissertation is divided into three parts. The rst part is devoted to register allocation, the second one tries to see in which context the fundamental advances in register allocation could be extended to local memory allocation, and the third one aims to rebuild a bridge between the domains of register and local memory allocations.

Register Allocation

In Chapter 1, we present the state of the art in register allocation. We introduce the terminology and the essential notions needed to understand register allocation. We describe the graph coloring and the linear scan approaches to register allocation and we show how separating the allocation phase from the assignment helps to ease and improve the register allocation.

In Chapter 2, we recall the approaches used to process programming languages: static compilation, interpretation, and JIT-compilation. We also introduce split compilation and show how it improves the quality of the code generated by JIT compilers.

In Chapter 3, we introduce the split register allocation which leverages the decoupled approach to improve register allocation in the context of JIT compilation. We experimentally validate the eectiveness of split register allocation and its portability with respect to register count variations, relying on annotations whose impact on the bytecode size is negligible.

Chapter 4 introduces a new decoupled approach, called iterated-optimal allocation, to register allocation. The iterated-optimal allocation algorithm achieves results close to optimal while oering pseudo-polynomial guarantees for SSA programs and fast allocations on general programs.

Local Memory Allocation

Chapter 5 sets the state of the art in local memory allocation. We introduce in this chapter static and dynamic methods for local memory allocation.

In Chapter 6, we explain the motivation of our work on local memory allocation. We also expose our approach to the problem, the preliminary assumptions we have made and our methodology to evaluate and compare our work.

Chapter 7 validates our intuition for decoupled approach to local memory allocation. It shows experimentally that after an optimal allocation phase relying on a generic and scalable integer linear program, the assignment phase could be achieved without any In Chapter 8, reinforced by results of Chapter 7, we study the local memory allocation in a more theoretical way setting the junction between local memory allocation for linearized programs and weighted interval graph coloring. We design and analyze a new variant of the ship-building problem called the submarine-building problem. We show that this problem is NP-complete on interval graphs, while it is solvable in linear time for proper interval graphs. We also give a criterion to guarantee the feasibility of the submarine-building problems for proper interval graphs and then we extend it to an extension of the class of proper interval graphs interval graphs. Our results show that while our approach represents an improvement over state of the art methods, it is limited so far in its practical application.

Reconciling Register and Local Memory Allocations

In Chapter 9, we propose a heuristic-based solution, the clustering allocator, which decouples the local memory allocation problem and aims to minimize the allocation cost. The clustering allocator while devised for local memory allocation, appears to be a very good solution to the register allocation problem. For register allocation, the results show that the clustering allocator outperforms both graph coloring and linear scan and is often close to the optimal solution. For local memory allocation the results are not as good as those for register allocation, but we do believe that the clustering allocator can be improved. Introduction

When a programmer compiles a program from a source language to an executable code, he wants the compiled one to conserve the source code's semantics. He also wants the code to run in an acceptable time. The execution time depends on the number of instructions to compute, and also on the computation time of each of these instructions. The computation time of an instruction can vary signicantly, from nanoseconds to milliseconds, depending on the time taken to access data in memory.

In a modern computer, it does not take more than one cycle of the CPU clock to read or write data into a register, while reading the data, from the cache or the main memory, is an order of magnitude slower. Registers are quickly accessed, but they exist in a very limited number. A 32-bit x86 architecture has only 8 general-purpose registers, ARM and PowerPC processors typically have 32 registers. Usually, all the values of the executed code cannot reside in registers. The values not held in registers should reside in memory. To reduce accesses to higher levels of memory it is essential to have an ecient usage of registers. Registers are software managed whereas all the other levels of the hierarchy are managed automatically. The management of the registers is done by the programmer, the application, or the compiler.

In all modern compilers, there is a phase called register allocation which optimizes the use of registers. The register allocation is usually one of the last phases of the compilation. It happens when all the candidate variables to register allocation are known. These candidate variables are composed of the variables already present in the source code and of the temporaries generated during preceding phases of compilation. The register allocation is dened [START_REF] Aho | Compilers: Principles, Techniques, and Tools[END_REF] as the problem which is often subdivided into two sub-problems: 6 Chapter 1. Register Allocation 1. the allocation which selects the set of variables that will reside in registers at each point of the program.

2. the assignment which picks the specied register where a variable will reside in.

The variables mapped to registers are called allocated variables and the rest, stored in memory, are called spilled variables. In this chapter, we intend to present the state of the art in register allocation. Section 1.2 introduces the terms and notions necessary to understand register allocation. Section 1.3 presents some aspects of the register allocation problem, with a sub-section on its complexity. Then, Sections 1.4 and 1.5 present respectively graph coloring and linear scan as two approaches to register allocation; the former is the dominant approach, and the latter is an alternative mostly implemented in just-in-time compilers. Finally, Section 1.6 presents a new approach to register allocation which decouples its allocation and assignment phases.

Terminology

We set here the meaning of some terms and notions needed or used in register allocation.

Basic Block.

A basic block is a maximal sequence of instructions with the following properties:

• it has a unique entry point as its rst instruction. Any instruction within the basic block but this entry point cannot be a destination of a jump instruction.

• it has a unique exit point as its last instruction, meaning that no instruction but the last one can cause to leave the block.

Within a basic block, when the rst instruction is executed all the other instructions of the basic block are executed. Figure 1.2(b) shows an example of four basic blocks: We say that a variable v is dened by an instruction if it is a result of that instruction. We also say that it is used by an instruction if it is read by that instruction. Notice that a variable can be dened and used by the same instruction. For instance, the variable b in Figure 1.2(b) is dened by the rst instruction. The variable d is re-dened and used by the instruction number 7. A variable v is said to be live at the point p if there exists a path in the control-ow graph from p to the exit point where v is used without being re-dened.

Live range.

The live range of a variable v is the list of program points where it is live. Figure 1.3 shows the live ranges of the variables of the example program given in Figure 1.2(a). The variable a is supposed to be live in, which means it is live at the beginning of the basic block, it stays live until it is read, by the instruction 6 if the left branch is taken, and the instruction 8 if the right branch is taken. By abuse of terminology in this dissertation, as it is common in the literature, we sometimes use the term live range to designate the variable it refers to.

Interference.

Two variables interfere if the intersection of their live ranges is nonempty. Two interfering variables cannot share the same register because this will cause one of them to overwrite the content of the other. The variables a and b interfere because their live ranges represented in Figure 1.3 intersect, whereas the variables d and f do not.

Spilling.

An essential notion to register allocation is spilling. It is frequent that the number of available registers in an architecture cannot map all the variables of a program. Therefore, it is sometimes necessary to have some variables that remain in the memory. We say that these variables are spilled. In certain architectures, e.g., RISC architecture, memory can only be accessed through load and store instructions. This means that to use a variable v at address a, we need to load the value at address a (which is the value of v) into a register and then use this register as an operand. Thus, even if a variable is spilled, it must be loaded into a register from memory before each of its use, and stored from a register after each of its denition, and the added instructions are called spill code. In architectures like x86, an instruction's operand can be directly accessed from memory. It means that to manipulate a variable v at address a in the memory, we can use a as an operand to directly use or dene v. Such a kind of operand is called a memory operand. But even for these architectures, some restrictions may exist, for instance on IA-32 architectures, move instructions cannot have more than one memory operand.

Coalescing.

Two variables related by a copy instruction and which do not interfere can be assigned to the same register. That is, the copy instruction becomes useless and can be safely removed. We say that these two variables are coalesced. A good register allocator will also strive as most as possible to coalesce variables that can be coalesced, because it will improve the quality of the generated code. For illustration, the variables a and f in Figure 1.3 should be coalesced, by looking at instruction 8.

Live range splitting.

A variable v live at two dierent instructions i1 and i2 can be split into two separate variables renamed v 1 live at instruction i 1 and v 2 live i 2 . To avoid changing the semantics of the program, sometimes it is necessary to join instructions v 1 and v 2 , with a copy instruction from v 1 to v 2 . This process of splitting the variable v is called live range splitting. The live range of a variable v can be very long and can have a non-empty intersection with many other variables's live ranges. Splitting the live range of such kind of variables tends to reduce the interference between variables and thus The scope of register allocation can be local, global, or interprocedural. It is local when it is restricted to a basic block, global when it is performed over a procedure or a method, and interprocedural when it is performed across multiple procedures. Register allocation has been performed since the rst compiler for FORTRAN. It has been widely studied and shown to be NP-complete. It has also been shown to have strong interactions with the instruction scheduling optimization. Depending on the trade-o between the diculty of the register allocation problem and the quality of the solution of the problem (memory-access-latency minimization). We can identify at least three types of problems that can be considered: Spill everywhere. It corresponds to the coarser grain of the register allocation problem, where the live range of each variable is viewed as an atom [START_REF] Poletto | Linear scan register allocation[END_REF], there is no live range splitting. In this context, a variable cannot be spilled at some part of the code and allocated at some other part: it is spilled everywhere. This approach does not give best results but it is simple and when compile time is in concern like in JIT compilers, it can be well suited.

Register allocation with live range splitting. This approach is ner than the rst one. The live range of a variable can be split at some points, for instance, at points where variables are redened or spilled (to avoid loosing previous assignment). In this context, a variable can be assigned to a register r 1 sometimes and spilled or allocated to another register r 2 at a dierent moment. This second approach is harder but superior to the rst one and SSA-based techniques and recent work on register allocation focus on it [START_REF] Traub | Quality and speed in linear-scan register allocation[END_REF][START_REF] Hack | Register allocation for programs in SSA-form[END_REF][START_REF] Bouchez | On the complexity of register coalescing[END_REF].

Load-store optimization. The third approach of the nest granularity. The goal is to optimize each load and store separately in order to minimize the memory access time.

In this context, the variables's live ranges can be split between every two instructions that can be consecutive [START_REF] Appel | Optimal spilling for CISC machines with few registers[END_REF]. This approach gives much better results than the two preceding level of granularity, but it is also harder to solve. Coalescing problem. The coalescing reduces the cost of move instructions between variables that do not interfere. The problem of looking for an allocation of minimal cost (where each pair of coalescable variables has been assigned a cost) is NP-complete [START_REF] Bouchez | On the complexity of register coalescing[END_REF].

Aliasing problem. When an assignment to a register name can aect the content of another register name, such register names are said to alias. As shown in Figure 1.5, in the IA-32 architecture, the two lower bytes of the 32-bit general-purpose registers EAX and EBX can be referenced with names AX and BX. The rst byte of AX and BX can be respectively referenced with AH and BL (high bytes) and their last bytes can be referenced with AL and BL (low bytes). In this example the register names EAX and AX, EAX and AH, or AX and AL alias. Lee et al. [START_REF] Lee | Aliased register allocation for straight-line programs is NP-compl ete[END_REF] show that aliased register allocation is NP-complete even for straight-line programs, which are very simple programs without control-ows.

Pre-coloring problem. We say that a variable is pre-colored if it must be assigned to a register due to some architectural constraints. For instance, in many architectures, Register allocation is not the only optimization performed by the compiler. It is part of a ow of optimizations which may impact on each other. In particular, it has strong interactions with instruction scheduling optimization. The instruction scheduling is used to increase the Instruction Level-Parallelism (the number of simultaneously executed instructions during a computer cycle). It looks for an ordering capable of improving the instruction level-parallelism. Instruction scheduling can be done before or after register allocation. If it is done before register allocation, it can increase the number of needed registers and make the code harder to color. If it is done after register allocation, some ordering opportunities may then turn impossible due to the performed register allocation. The interplay between these two problems have been studied and many approaches that consider both of these two problems have been proposed in the literature [START_REF] Eisenbeis | Early Periodic Register Allocation on ILP Processors[END_REF][START_REF] Bradlee | Integrating register allocation and instruction scheduling for riscs[END_REF][START_REF] Norris | An experimental study of several cooperative register allocation and instruction scheduling strategies[END_REF]. Register allocation with instruction scheduling considerations is beyond the scope of this dissertation: we assume that we have a xed scheduling.

Graph Coloring

The graph coloring is the dominant approach to register allocation. The idea of abstracting the register allocation problem to a graph coloring problem dates from the early 1960s [START_REF] Lavrov | Store economy in closed operator schemes[END_REF]. The rst graph coloring framework for register allocation has been implemented by Chaitin et al. [Cha82, CAC + 81]. We need rst to introduce some terms about graphs before presenting the graph coloring approach to register allocation.

A graph G = (V, E) consists of two sets, V the set of vertices or nodes, and E the set of edges. Every edge (v 1 , v 2 ) of E has two end points v 1 ∈ V and v 2 ∈ V . We say that v 1 and v 2 are adjacent(s) or are neighbor(s) if (v 1 , v 2 ) ∈ E. The number of neighbors of a vertex v is called the degree of v. Here, We only consider undirected graphs, i.e., we do not make dierence between the edges (v 1 , v 2 ) and (v 2 , v 1 ).

A clique is a set of vertices, where every pair of distinct vertices is adjacent. A clique is maximum if there is no clique of G of larger cardinality. The number of vertices in a maximum clique of G is denoted ω(G) and is called the clique number of G.

A vertex coloring (or coloring) of a graph G is a function C that maps each vertex v of G into a color c v such that adjacent vertices are mapped to dierent colors. We say that I is a k-coloring of G, if the number of colors used to color G is equal to k. The chromatic number χ(G) is the smallest k for which it is possible to nd a k-coloring of G. A proper coloring of a maximum clique A of G requires at least ω(G) colors, because otherwise there will be at least two vertices of A having the same color. Hence, for any graph G we always have:

ω(G) ≤ χ(G).
The technique presented here abstracts the register allocation to an interference graph coloring problem. The interference graph G of a given program is the intersection graph of the variables's live ranges in that program. Each variable is represented by a vertex in G and the vertices of two interfering variables are adjacent in G. If we consider each register as a color, thus for a given program, the register allocation problem corresponds to a graph coloring problem.

Chaitin et al. use the Kempe's heuristic to color the interference graph. Given a graph G and k available colors, the heuristic tries to nd a k-coloring of G. Assume that there exists a node n in G of low degree, that is, a node which has less than k neighbors. From a k-coloring of G -{n}, it is easy to nd a k-coloring of G, it suces to assign to n a color that diers from the colors of its neighbors. Thus, n is always colorable and

G is k-colorable if G -{n} is k-colorable.
The node n can be removed (with its edges) from G and placed on a stack. When n is removed from G, the dregrees of its neighbors are lowered and this may turn some of its neighbors into low degree nodes in the new graph and prove that they are colorable. If this procedure can be iterated until the graph becomes empty, then G is showed to be k-colorable. To color G, it suces to pop nodes from the stack, to insert them back into the graph and to map them to colors (the reverse order of their removal). A node n popped from the stack is inserted into the graph and the edges removed at the moment of its removal are restored. Coalesce removes unnecessary move instructions. Two names that do not interfere and that are related by a move instruction are coalesced into one node adjacent to the neighbors of the nodes being replaced. When no more coalescing is possible, the graph is re-build to trigger new opportunities for coalescing. The Build and Coalesce phases are repeated until no more coalescing is possible.

Spill costs computes the cost of spilling each name. The cost of spilling a name is an estimation of the impact of spilling it on the execution time of the program.

Simplify nds the set of nodes to be colored and order them. It rst constructs an empty stack and looks repeatedly for a low degree node:

1. if such a node exists, it removes it from the graph and pushes it on the stack.

2. otherwise, all nodes are of signicant degree (degree ≥ k) and it chooses according to the spill costs a node to spill and removes it from the graph.

This procedure is repeated until the graph becomes empty.

Spill Code inserts loads and stores instructions if some nodes have been spilled during the simplication phase. For each spilled name n, it adds a load instruction before every use of n and a store instruction after every denition of n. Thus, n will be replaced into a collection of new names with tiny live ranges. Hopefully, due to their tiny live ranges, these new names will not interfere with several other names. After this step, the whole procedure is restarted from Renumber. These iterations from Renumber to Simplify are repeated until no node is spilled. But, in practice one or two iterations often suce.

Chapter 1. Register Allocation Select assigns colors to the nodes of the graph in the reverse order of their removal.

It pops a node n from the stack and inserts it back into the graph. The node is assigned a color dierent from the colors of all its neighbors.

Figure 1.6 taken from Brigg's paper [START_REF] Briggs | Improvements to graph coloring register allocation[END_REF] shows the inter-connexion between the dierent steps of the Chaitin's allocator. [START_REF] Briggs | Improvements to graph coloring register allocation[END_REF]. This is possible because the condition for nding a low degree node is sucient but not necessary: a node can have more than k (k being the number of colors) neighbors and be colorable. This improvement is called optimistic coloring.

Briggs et al. also pointed out that when the coalescing is done too aggressively, it can make the interference graph uncolorable and lead to excessive spilling. They introduced the notion of conservative coalescing which ensures that whenever two nodes are coalesced, the resulting graph remains colorable, if it was the case for the original graph. They used the following criterion to conserve this colorability property: two nodes are coalesced only if the resulting node will not have more than k neighbors [START_REF] Briggs | Improvements to graph coloring register allocation[END_REF].

After the improvements of Briggs et al., George and Appel have proposed the iterated register coalescing that was mostly focused on coalescing [START_REF] George | Iterated register coalescing[END_REF]. They noticed that the Briggs's allocator was too conservative and left in the program too many move instructions that could be removed. They have shown that interlacing the simplify phase with the coalesce phase permits to be much more aggressive in the coalescing without turning the graph uncolorable. The basic idea is that, when conservative coalescing is performed before simplication, the move-related nodes of signicant degree might not be coalesced, while they sometimes can be turned into low-degree node after simplication. Hence, in the described allocator, the simplify phase removes non-move-related nodes one at a time.

Then, when no more simplication is possible, the coalesce phase merges move-related nodes in Brigg's style. If a resulting node is no longer move-related, it will be simplied in the next round of simplify. The simplify and coalesce phases are repeated until there remains only signicant-degree nodes or move-related nodes in the graph. When such a case is reached, the freeze phase looks for a move-related node and mark it as nonmove-related. All the remaining moves involving this node will not be removed. Then, the simplify and coalesce phases are resumed. Figure 1 add i to active 10: end for Algorithm 1 shows the dierent steps of the linear scan register allocation. The number of registers available on the architecture is called R. It is assumed that live intervals have been computed and list is a list that contains all the live intervals sorted by increasing start point. At each step of the algorithm, the list called active maintains the live intervals placed in registers that overlap the current point; active is sorted by increasing end point of live intervals. For each starting live interval i, ExpireOldIntervals(i) removes from active all the live intervals that do not overlap i's start point. If the size of active is lower than R then i is assigned a register and is added to active. Otherwise, SpillAtInterval(i) spills the interval that goes further in the future between i and last, the last interval of active. If last is spilled, i is assigned to its register and added to active.

The linear scan algorithm is interesting because it is fast, simple and produces codes of relatively good quality. This makes it a serious candidate for register allocation in just-in-time compilers, where compilation time is of the utmost importance. That is why the linear scan register allocation is implemented in the Java Hotspot and the LLVM compilers. A weakness of the original version of linear scan is the inaccuracy of live intervals. Indeed, the live interval characterizing the entire live range of variables may contain some idle holes. Those holes correspond either to program points dominated by a redenition of the variable (the variable is eectively dead at those points), or to a hole resulting from the order in which the basic blocks are numbered (a control-ow artifact). For instance, in Figure 1.9, the variable d is still live when the hole within its live interval starts. Wimmer et al. make use of these holes when implementing an optimized version of the linear scan algorithm for Java HotSpot compiler [START_REF] Wimmer | Optimized interval splitting in a linear scan register allocator[END_REF]. Mössenböck et al. also improved the quality of the linear scan thanks to the live interval holes and the SSA form which tends to produce short live intervals [START_REF] Mössenböck | Linear scan register allocation in the context of ssa form and register constraints[END_REF]. The most recent work that we will discuss in the next section, called extended linear scan, has been done by Sakar et al. [START_REF] Sarkar | Extended linear scan: An alternate foundation for global register allocation[END_REF].

Decoupled Register Allocation

We present the new approaches to register allocation that decouple its allocation and assignment phases.

The intuition for decoupled register allocation derives from the observation that live range splitting is almost always protable if it allows to reduce the number of register spills, even at the cost of extra register moves. The decoupled approach focuses on spill minimization only, pushing the minimization of register moves to a later register coalescing phase [START_REF] Appel | Optimal spilling for CISC machines with few registers[END_REF][START_REF] Bouchez | Advanced conservative and optimistic register coalescing[END_REF].

A rst two-phase approach

In 2001, Appel and George have proposed a register allocator adopting a two-phase approach [START_REF] Appel | Optimal spilling for CISC machines with few registers[END_REF]. In the allocation phase, they allowed live range splitting at each program point (between every two consecutive instructions), and they formulated an integer linear program that was able to nd rapidly (tenth of milliseconds) the optimal sets of split points and spills. To ensure that the resulting interference graph was k-colorable, they copied every variable to a freshly named temporary to decrease the register pressure. As a result, they needed to have special care on coalescing, and thus, their assignment phase was dedicated to coalescing and coloring. They used a variant of Park and Moon's optimistic coalescing algorithm and obtained code of good quality [START_REF] Park | Optimistic register coalescing[END_REF]. Even if there was no theoretical reason showing that solving the spilling and coloring problem separately leads to an optimal solution of the original problem, Appel and George's paper has the virtue of showing that such an approach can give very good results.

SSA-based Register Allocation

In 2003, Anderson tested a huge number of interference graphs from the SML/NJ of Appel and George [START_REF] Andersson | Register allocation by optimal graph coloring[END_REF]. He found that for every interference graph G he tested, χ(G) = ω(G).

In the same way, Pereira and Palsberg found that 95% of the methods in the Java 1.5 library have chordal interference graphs when compiled with the JoeQ compiler [START_REF] Magno | Register allocation via coloring of chordal graphs[END_REF]. Based on that observation they proposed a greedy algorithm which can optimally color the 1.6. Decoupled Register Allocation 21 chordal interference graphs in linear time according to the number of edges. They also gave good heuristics for coalescing and spilling. Comparing their algorithm with the iterated register coalescing, they produced better results for conguration with few registers and comparable results for conguration with many registers. The works of Anderson and Pereira et al. experimentally validated that many of the interference graphs could be colored optimally and in polynomial time.

In A vertex v of a graph G is simplicial if its neighbors form a clique in G. An ordering v 1 , v 2 , . . . , v n of the vertices of a graph G is a perfect elimination order (PEO) if each v i is a simplicial vertex in G {v i ,v i+1 ,...,vn} , the graph remaining from G when all the vertices preceding v i in the ordering have been removed. Given a PEO of a graph G, it is possible to color G with the following procedure [START_REF] Charles | Algorithmic Graph Theory and Perfect Graphs[END_REF]:

1. Remove all the vertices of G in the order they appear in the PEO and push them into a stack.

2. Pop the vertex v on top of the stack, re-insert it in the graph, and assign it to a color not used by any of its neighbors. Since the neighbors of v already present in the graph form a clique, the number of colors used currently is bound by the size of the maximum clique present in the graph.

3. Repeat the step 2 until the stack becomes empty.

This procedure will use exactly as many colors as the size of the largest clique in G and thus gives an optimal coloring of G. It is well known in perfect graph theory that a graph for which there exits a PEO is chordal and therefore perfect [START_REF] Charles | Algorithmic Graph Theory and Perfect Graphs[END_REF]. For a perfect graph G the maximum clique number ω(G) is equal to χ(G) the smallest k for which it is possible to nd a coloring.

Hack et al. have shown that a variable v of an interference graph G of a program in strict SSA-form, where every use of a variable is dominated 1 by its denition, can be added to a PEO, if all variables, whose denitions are dominated by the denition of v have already been added to the PEO. The intuition is that, whenever v is added to a PEO, the only neighbors of v remaining in G are those dominating v; since they dominate v, they are all live when v is dened and hence form a clique. A PEO of the vertices of G can be obtained by a post-order walk over the program's dominance tree and thus in quadratic time according to the number of vertices of G. Hack et al. also demonstrate that for every clique in the interference graph, there exists a point in the program where all the variables in the clique are live. Thus, a spilling algorithm can make an interference graph k-colorable by reducing the number of live variables at each program point down to k. This shows that the register allocation problem can be decoupled into two phases that can be solved separately:

1. If MaxLive, the maximum number of simultaneously live variables, is greater than k, use a spilling algorithm to decrease MaxLive down to k.

2. Color the chordal graph optimally and coalesce as much as possible.

For register allocation again, SSA permits to ease the optimization problem. Specifically, the SSA-based register allocation techniques collapse the register coalescing with the hard problem of getting out of SSA [HGG06, BDdD + 09], as one of the last backend compiler passes.

1.6.3

A Decoupled Linear Scan Sarkar and Barik have introduced Extended Linear Scan [START_REF] Sarkar | Extended linear scan: An alternate foundation for global register allocation[END_REF], a new version of linear scan which adopts a decoupled approach to register allocation. Extended Linear scan considers separately the sub-intervals which compose the live intervals (a live interval can be composed of many sub-intervals interleaved with holes). The allocation decisions are performed at the end points of these sub-intervals; we call them decision points. In the allocation phase, at each decision point where count, the number of simultaneously living variables, exceeds k, the number of available registers, countk variables are spilled. In the assignment phase, non-spilled variables are assigned to registers, notice that a nonspilled variable can be assigned to a dierent register for each of its sub-intervals. This can lead to some inconsistencies in the generated code. For instance, in Figure 1.9, if the variable d is assigned to the register r 1 during the rst sub-interval of its live interval and then is assigned to r 2 during the second sub-interval of its live interval, r 2 may hold a wrong value of d if the rst branch of the control-ow is taken. Extended Linear Scan eliminates these inconsistencies at the cost of inserting some move instructions.

Conclusion

In this chapter, we have introduced the background of register allocation upon which our dissertation is based. We have presented the graph coloring and the linear scan approaches to register allocation and we have shown how separating the allocation phase from the assignment helps to ease and improve the register allocation.

Chapter 2

Split Compilation

Traditionally, there are two approaches to translate programs, written in programming languages, into a form that is executable (machine code or native code) on a target machine: compilation and interpretation.

A compiler is a software-program that translates a source program, usually written in a programming language, into a target one written in machine code or another programming language. If the target program is executable, it can then be run and fed with inputs to produce outputs. Another approach used to translate programs is to combine both compilation and interpretation. In this approach, the source program is generally compiled into an intermediate form, called bytecode (e.g. the Java .class les), that: is independent of any particular hardware, cannot be run directly, and is close to machine instructions. This rst compilation is usually called o-line compilation. The bytecode is then interpreted by a virtual machine, which is a software implementation that emulates the functioning of a physical machine or computer. For instance, such an approach is used for programming languages like Smalltalk [START_REF] Goldberg | Smalltalk-80: the language and its implementation[END_REF] and Java [START_REF] Gosling | Java(TM) Language Specication, The (3rd Edition) (Java[END_REF].

The advantage of the above-mentioned strategy is that the bytecode is portable across many architectures and operating systems for which a virtual machine exists. Indeed, the bytecode can be compiled on a computer and run on another one, or over the network. The imported bytecode is checked for errors before it is executed. This is to prevent misuses which may be deliberate or not. In addition, if the bytecode is at a higher level than machine code, it becomes more compact: it is smaller in size and carry, implicitly, much more semantic information [START_REF] Aycock | A brief history of just-in-time[END_REF]. This compactness is crucial in environments, like embedded systems, where the code size is an important issue.

Just-In-Time Compilation

To speed up the execution of programs, some virtual machines use just-in-time (JIT) compilers, which dynamically compile (online compilation) the bytecode into machine code (native code) just before it is executed. JIT compilation leverages advantages of both static compilation and interpretation. These advantages are listed below:

Execution speed. The machine code produced by a JIT compiler, like one produced with a static compiler, runs usually faster than an interpreted code.

More optimizations. During the execution, some information that is target-dependent or that was unavailable prior to execution becomes accessible. For instance, input parameters, target machine specics and other types information are often unaccessible before runtime. This additional information enables more optimizations for JIT compilers compared to static ones.

Program analysis and optimizations performed during static compilation can be very expensive in time. Usually, JIT compilers cannot aord expensive program analysis and optimizations since the compilation time is part of the global execution process. Thus, there is a trade-o between the time spent for compilation (optimizations) and the execution time of the produced code.

Annotations-Enhanced JIT Compilers

In order to reduce the online compilation (optimizations) time and thus the global execution time, some annotation-based techniques have been proposed. These techniques annotate the bytecode (namely Java bytecode) with analysis information that are timeconsuming to collect. The works of Pominville et al. [PQVR + 01] and Chrintz et al. [START_REF] Krintz | Using annotations to reduce dynamic optimization time[END_REF] are good examples of such annotations-enhanced JIT compilation.

In order to guarantee the safe execution of Java programs, Java virtual machines must check if the array index exceeds the range and throw an exception (notice of an error) if it is the case. For array-based application, array bounds checks may incur severe overhead at runtime. Pominville et al. [PQVR + 01] proposed a method to eliminate array bounds and null pointer checks that can be proven unnecessary by static analysis. They convey information, on usefulness of checks or not, through bytecode annotations.

Following a similar approach, Krintz and Calder [START_REF] Krintz | Using annotations to reduce dynamic optimization time[END_REF] proposed an annotation framework that reduces the online compilation time overhead of Java programs. They devised four kinds of annotations. The rst one was used to transmit to the dynamic compiler statically collected data that are needed for some optimizations (e.g. global register allocation) and that precomputed oine (before the online compilation). The second kind of annotations indicate to the compiler which data should be generated once and stored for reuse instead of being regenerated. The third annotation marks a method for optimization or not, or selects the level of optimizations to perform on a method. This helps to avoid wasting time optimizing methods that will not improve the execution performance. The last kind of annotation guide the selection of protable optimizations to perform on a method.

Chapter 2. Split Compilation

The techniques that are presented here reduce the compilation time and thus the global execution time. However, they do not improve the performance of the produced code.

Split Compilation

The aim of split compilation is to reduce both the compilation and execution times.

The traditional approach to process bytecode language is to distribute the roles among oine and online compilers. Verication and code compaction are typically assigned to oine compilation, while target-specic optimizations are performed by online compilation.

Split compilation reconsiders this notion: it allows a single optimization algorithm to be split into multiple compilation steps, transferring the semantic information between dierent moments of the lifetime of a program through carefully designed (bytecode) language annotations. Split compilation has the potential to combine the advantages of oine and online compilations: running expensive analyses oine to prune the optimization space, deferring a more educated optimization decision to the online step, when the precise execution context is known. Many JIT compilation eorts tried to leverage the accuracy of dynamic analysis to outperform native compilers; but split compilation is a concrete path to get the best of both worlds.

One of the rst split compilation works is the AJIT (annotation-aware Just-In-Time) framework of Azevedo et al. [START_REF] Azevedo | Java annotation-aware justin-time (ajit) compilation system[END_REF]. In order to improve the quality of the code generated by the JIT compiler, the authors removed some runtime checks, like array accesses checks, and mostly focused on splitting the register allocation optimization into two steps:

• The rst step performed oine implements a variant of priority based graph coloring algorithm. A priority-based coloring algorithm uses heuristics and cost analysis to sort variables. The most frequently accessed variables have highest priority and are assigned to colors rst. Based on this priority list and assuming an innite number of registers, called virtual registers, they assign each variable to a virtual register (the most important variables are assigned to virtual registers of lowest numbers). Since real machines have small number of registers, the authors try to maintain the number of used virtual registers as small as possible. That is, many non-interfering variables are assigned to the same virtual register. This information on variables mapped to their virtual registers are transmitted to the online step through annotation.

• The second step of the algorithm, performed online, uses the annotations to retrieve the assignment of variables to virtual registers. It rst replaces virtual registers of lowest numbers with physical ones. The variables assigned to virtual registers for which there is no physical register available are spilled.

Azevedo et al. implemented this approach with the public domain JIT compiler system Kae [START_REF] Wilkinson | A free jit virtual machine to run java code[END_REF]. They showed that on average the code they produced runs two times faster than the code originally produced by Kae. This work, while being interesting, does not handle the live range eect of the calling conventions which sometimes leads to extra spilling and performance degradation. In addition, by moving some array bounds checks and in the absence of analysis in the AJIT virtual machine implementation to verify such accesses, some safety constraints of the Java virtual machine design are violated [START_REF] Jones | Annotating mobile code for performance[END_REF].

Following a similar approach, Jones [START_REF] Jones | Annotating mobile code for performance[END_REF] extended the idea of virtual register annotation with the swap annotations. The swap annotations leverage the non uniform use of variables throughout a method to improve register allocation. For instance, a variable v assigned to a register r cannot be accessed within a loop l. Thus, a variable v ′ that is frequently accessed within l may be locally assigned to r. Swap annotations were generated to locally increase the priority of a virtual register into the priority of a higher one. In addition, Jones forces that the values held by a given virtual register are of the same type. This permits to verify easily the virtual registers annotations with a simple extension of the standard Java virtual machine verication procedure. These verication guarantees that every virtual register access is compatible with all other accesses. This work also addressed the calling convention issues and portability to deal with architectures that dier in number of registers.

Split compilation is not restricted to register allocation. Indeed, the split compilation term was rst coined in the context of JIT vectorization [LCC + 07].

Conclusion

This chapter reviews the dierent approaches to process programming languages. It emphasizes on how split compilation improves the quality of the code generated by JIT compilers.

Chapter 3

Split Register Allocation

Introduction

Just-In-Time (JIT) compilers rely on continuous, feedback-directed (re-)compilation frameworks to select hot functions (frequently executed) for online optimizations. These online optimizations must make important trade-os in terms of reducing compilation time for decreased generated code performance. Reducing compilation overhead has two main benets, low-complexity algorithms simultaneously increase the amount of code being optimized while reducing the compilation time for hot functions. In practice, (quasi-)linear complexity is the rule for JIT compilation. This severely impacts what kind of optimizations are admissible and how aggressive they may be.

A Case for Split Compilation

Traditional bytecode language tool chains distribute the roles among oine and online compilers. Verication and code compaction are typically assigned to oine compilation, while target-specic optimizations are performed by online compilation. Split compilation reconsiders this notion: it allows a single optimization algorithm to be split into an oine and an online stage, transferring the semantic information between those stages through carefully designed bytecode annotations. Split compilation has the potential to combine the advantages of oine and online compilation: running expensive analyses oine to prune the optimization space, deferring a more educated optimization decision to the online stage, when the precise execution context is known. Many JIT compilation eorts tried to leverage the accuracy of dynamic analysis to outperform native compilers; but split compilation is a concrete path to get the best of both worlds.

Chapter 3. Split Register Allocation

To make a concrete case for split compilation, we selected the (spill-everywhere) register allocation problem [CAC + 81, BCT94]. Register allocation is an ideal candidate to demonstrate how split compilation impacts the design of future bytecode languages and compilers, and how it diers from plain annotation-enhanced JIT compilation [START_REF] Krintz | Using annotations to reduce dynamic optimization time[END_REF]. Indeed:

• the principles of register allocation are reasonably well understood;

• it is one of the most important components of all JIT compilers;

• it is challenging to design an oine analysis that would improve online register allocation, while ignoring the exact register count of the target.

Outline of the chapter

This chapter makes two important contributions.

1. We design bytecode annotations enabling a linear-time online algorithm to achieve high-quality register allocation, with negligible impact on the size of the bytecode.

2. We demonstrate how such annotations are robust to variations in the number of registers. With additional provisions in the oine stage, it is even possible to accommodate radical changes in the instruction set target architecture.

Our method is implemented in the JikesRVM open source JIT compiler for Java [START_REF] Alpern | The Jikes RVM project: Building an open source research community[END_REF], and evaluated on x86. We do believe that it would be easy to port it to multi-language JIT frameworks like the ECMA-335 CLI standard. 2The chapter is organized as follows. Section 3.2 presents the split register allocation ow and algorithms. Section 3.3 evaluates split register allocation, with coverage of performance improvements as well as annotation compaction and portability. Section 3.4 explores more complex compilation scenarios. Finally, Section 6.3 discusses related work on annotation-enhanced just-in-time compilation.

Split Register Allocation

We rst introduce some terminology. An interval characterizing the entire lifetime of a local variable or temporary may contain some idle holes. The live range of a variable x is the set of program points where x is live; it corresponds to a union of basic intervals.

When linearising the control ow (e.g., when generating code), the basic interval of a given live range are interleaved with holes. Those holes correspond either to program points dominated by a redenition of the variable (the variable is eectively dead at those points), or to a hole resulting from the order in which the basic blocks are numbered (a control-ow artifact). Register pressure refers to the amount of locally live variables.

Considering that a variable is not alive during its idle holes can help in reducing the register pressure. Jikes RVM takes advantage of this.

Optimization Problem and Baseline Algorithm

Since our primary focus is to illustrate the split compilation concept, we limit ourselves to the most basic register allocation and assignment problem:

• Spill everywhere allocation: spill the whole live range.

• Single-color assignment: when such a live range is allocated, all its basic intervals must be assigned to the same register. Some live ranges may be preassigned due to function call conventions and operand restrictions of some target instructions;

Throughout the chapter, we handle register allocation in dierent register classes separately (e.g., general purpose, oating point), and call R the number of registers in the current class of interest.

Algorithm 2 recalls the main steps of the linear scan algorithm, as implemented in JikesRVM. Every time a basic interval i becomes active, Algorithm 2 calls the function assignOrSuggestSpillCandidate(V (i)), where V (i) is the live range corresponding to i. According to the allocation that has been performed up to this point, function assignOrSuggestSpillCandidate(V (i)) returns, either a live range or ⊥ (bottom): if it returns a live range, it is the one to be spilled in order to continue allocation; if it returns ⊥ it was possible to assign V (i) without spilling. These algorithms are the basic framework upon which the oine and online phases of our split register allocation are constructed.

3.2.2

The ILP Model Here, we discuss our formulation of spilling in register allocation as an ILP problem. We obtain spilling decisions oine and pass this information to the online compilation phase using annotations. Considering a set S of live ranges, a spill set of S is any subset S ′ of S such that S \ S ′ can be allocated over the R registers (without spilling). We also consider a function which assigns to each live range in S the cost of spilling it. The cost of a spill set is the sum of the costs of live ranges within that set. An optimal register allocation is associated with a spill set with the minimal cost.

We build an ILP model that is optimal among spill-everywhere, single-color allocations, for a given cost model.

We model register allocation as a {0, 1} linear program, the objective function being the cost of the spill set. We support multiple classes of registers, each register class is further decomposed into 2 subclasses: caller-saved (scratch register) and callee-saved (non-scratch register). Live ranges are partitioned according to register classes, and can be of the volatile, non-volatile or preassigned kinds: a non -volatile live range can only be assigned to some callee-saved register, and a preassigned live range can only be assigned to a specic physical register. We create a {0, 1} variable l r for each live range l and register r that l may be assigned to (considering class and volatility constraints): l r = 1 if and only if l is assigned to r. These variables are constrained by 3 kinds of (in)equalities.

1. At most one register per live range (single color assignment):

1≤r≤R l r ≤ 1 . 2.
Interfering live ranges cannot be assigned to the same register:

l r + l ′ r ≤ 1.
3. The third constraint states that if a live range l interferes with a live range l ′ preassigned to r, then l r = 0.

Annotation Semantics

The oine stage generates annotations that can be used by an online stage to characterize important properties of some live ranges. The online stage may run on a target that may not match what was used to generate the annotations in the oine stage. This triggers portability problems: we address register count variations in this section, and defer the discussion of other problems to Section 3.4.

In the context of register allocation, the most specic portability issue is related to variations in the number of registers. To dene portable annotations, it would be ideal to prove a general result about the inclusion of an optimal spill set for a given number of physical registers into one of the optimal spill sets for a lower number of registers. Unfortunately, this is not true in general. Figure 3.1 shows a counter example on the allocation of 5 live ranges the horizontal bars. Every number on top of a horizontal bar denotes the cost of spilling the corresponding live range. Dashed black lines correspond to spilled live ranges. For the left graph, we assume R = 2 registers. For the graph on the right, R = 1 register only. When R = 2, we may optimally spill i 3 to assign i 1 and i 4 to one register and to assign i 2 and i 5 to the another one. When R = 1, the single optimal allocation is to spill i 2 and i 4 and to assign i 1 , i 3 and i 5 to the single register. In this example we see clearly that an optimal spill set for two registers is not included in the optimal spill set for one register. Although such an inclusion property does not always hold, we experimentally validated that only few live ranges should be spilled for R + 1 registers but allocated for R registers. For example, considering the x86 instruction-set architecture, when moving incrementally by one register from the minimum number of registers, to a spill-free 3 number of registers for each method, inclusion property was violated for only 0.13% of the live ranges over the whole SPEC JVM suite. This validates the intuition that the semantics of an allocate/spill-oriented annotation is portable across variations in the register count.

The Oine Procedure

Our split register allocation procedure derives from three key observations. 1. First, once the ILP solver nds an optimal spill set, it would be possible to directly annotate the code with the best spill set. This can lead to annotation bloat (although linear), with total annotation size potentially larger than the bytecode itself. Jones and Kamin do not address the problem [START_REF] Jones | Annotating java class les with virtual registers for performance[END_REF].

2. Second, the more detailed the annotation, the more sensitive it is to low-level decisions on instruction selection and scheduling that may happen after register allocation. To make the annotation portable, it is important to focus it on semantic properties that preserve the essence of the oine optimization while maximizing independence w.r.t. post-pass optimizations in the online compilation stage. The idea here is to focus the annotation on long live ranges whose interferences do not vary much w.r.t. post-register allocation instruction selection and scheduling. Indeed, short live ranges are likely to be allocated due to their limited interferences and high-rate register usage.

3. Third, notice that a greedy allocation algorithm is typically too conservative, allocating a live range that should have been spilled or assigning an inappropriate register/color. This means that annotations should only pertain to must-spill information.

With those three observations in mind, we devised Algorithm 4. The intuition behind this algorithm is natural: why store annotations for live ranges on which a greedy, linear procedure can readily make the right decision?

The algorithm uses an oracle-driven version of the linear scan. Every time the greedy heuristic wishes to spill a live range which does not belong to the annotations, the algorithm forces it to spill a live range which is currently active and which belongs to the annotations. By doing so, we discover live ranges in the optimal spill set that the linear scan cannot nd on its own.

Considering Algorithm 4, at a step where live range V (i) is active (according to the allocation performed since the beginning of the method being allocated), function as-signOrSuggestSpillCandidate(V (i)) returns, either a live range or ⊥ (bottom): if it returns a live range, it is the one to be spilled in order to continue allocation; if it returns ⊥ it was possible to assign i without spilling. Function findActiveLiv-eRange(optimalSpills) returns a currently active live range that is in the set optimalSpills, and set annotation records live ranges that will not be found by the linear scan.

The algorithm returns live ranges that will not be optimally allocated by the linear scan and keeps those as the constituents for the compressed annotations.

The nal step consists of pairing the live ranges returned by Algorithm 4 with a must-spill tag. This pairing should be as economical as possible to represent, but it should also make sense across dierent targets and carry relevant allocation information.

For each live range l, we compute the maximal value of R for which l must be spilled, denoting it as R max (l). We do not care much about oine compilation time in this study:

the computation thus boils down to iterating the ILP model over decreasing values of R, pre-spilling live ranges spilled at the previous step (for R + 1 register) to guarantee inclusion.

Finally, annotated live ranges need to be stored in a compact persistent format, together with the bytecode program. Rather than storing every pair (i, R max (l)), we cluster end if 14: end for Return: annotation: the compressed annotations live ranges with the same value of R max (l), sort those clusters, and serialize the list of live ranges in every cluster, prepending each cluster's list with the corresponding value of R max (l). We end up with separate strings, one for each size s of the register set, listing the live ranges that must be spilled for s registers and that were not already listed in a string associated with size s ′ greater than s. This way, most of the space is used to store live range names, for which we conservatively count up to 4 bytes per live range.

3.2.5

The Online Procedure

The online stage performs allocation based on a compact spill set collected by the oine stage, and carried as bytecode annotations.

Our online algorithm follows the steps of Algorithm 2. In addition, at the beginning of every basic interval , it checks whether the corresponding live range is present in the annotation. If so, then spill it (if the live range was not previously spilled).

This algorithm takes its roots in the decoupled allocation/assignment approach. As our experiments will conrm, the annotation-enhanced linear scan algorithm results in a much better quality allocation. Yet it does not optimally preserve the information available in the annotation and may yield spurious spill code. The reason is simple: register assignment on a colorable (spill-free) graph is equivalent to a graph coloring decision problem, which is NP-complete on live ranges end if 9: end for Return: sets of spilled live ranges and register assignments live-range splitting: linear complexity can be achieved on SSA form following a perfect elimination order a greedy reverse post-order traversal of the SSA graph [START_REF] Bouchez | On the complexity of spill everywhere under ssa form[END_REF]. It is clearly the way to go for optimality preservation, but it also implies a major engineering endeavor that has not yet been undertaken in a full-scale JIT compiler. Fortunately, the interference graphs that arise in non-SSA code are mostly chordal [START_REF] Magno | Register allocation via coloring of chordal graphs[END_REF], which guarantees the existence of a perfect elimination order in most cases; this motivates the decoupled approach and explains the observed quality of our online algorithm.

Experimental Evaluation

We implemented split register allocation in JikesRVM version 3.0.1 [START_REF] Alpern | The Jikes RVM project: Building an open source research community[END_REF], relying on CPLEX 4 for the oine resolution of optimal allocation problems.

Methodology

To assess the cost of a spill, we need to dene the optimal solution we are aiming for.

The cost model of the spill-everywhere problem is implemented in Jikes RVM; it combines dynamic edge proling, static use count and instruction type.

We illustrate split register allocation on SPEC JVM benchmarks. Experiments on the DaCapo benchmarks [START_REF] Blackburn | The dacapo benchmarks: java benchmarking development and analysis[END_REF] could not be included at the time of the submission, but we are working hard on it. We target a 2.67GHz Intel Core 2 Quad, running in 32-bit mode, in a PC platform. This conguration is favorable to register allocation experiments due to the low number of registers, although the cost of spilling is often marginal due to 4 http://www.ilog.com/products/cplex 40 Chapter 3. Split Register Allocation out-of-order execution and to the sophisticated memory hierarchy. Each gure was obtained from 100 individual runs of the benchmark, eliminating the 10% best and 10% worst performing points. We did not conduct a systematic statistical study of the performance distribution. Instead, we eliminated the largest source of variation by selecting a non-adaptive, aggressive (maximal optimization), prole-directed strategy (with embedded replay), using the following compilation ags:

-Xmx1024M -Xms1024M -X:irc:O3 -X:aos:enable_recompilation=false -X:aos:initial_compiler=opt -X:aos:enable_replay_compile=true -X:vm:edgeCounterFile=my_edge_counter_file Split compilation is of course compatible with adaptive optimization. This methodology diers from the standard practices in that we do not run an adaptive compilation scheme [START_REF] Blackburn | The dacapo benchmarks: java benchmarking development and analysis[END_REF][START_REF] Georges | Java performance evaluation through rigorous replay compilation[END_REF]. We claim our methodology is relevant in the context of split compilation:

• it eliminates the instability triggered by monitoring-based decisions, allowing to focus on the eect of the register allocation itself;

• an adaptive execution methodology is needed to compare the relative contributions of JIT-compilation, monitoring, garbage collection, and the eect of the optimizations themselves [START_REF] Georges | Java performance evaluation through rigorous replay compilation[END_REF]; our methodology allows for a fair comparison nonetheless, since the online stage of the split allocation does not introduce signicant overhead w.r.t. the original linear scan implementation. Thanks to its Java API, it was easy to connect CPLEX to our framework. The total resolution time for the optimal register allocation of all SPEC JVM benchmarks running with aggressive optimization including inlining and unrolling takes less than 4 minutes on a Core 2 Quad processor at 2.67GHz with 4GB of RAM. Preserving the information collected in the oine stage requires at most 0.26% of the live ranges to be annotated. This is several orders of magnitude more eective than state-of-the-art approaches [START_REF] Jones | Annotating java class les with virtual registers for performance[END_REF], and even comes with a formal guarantee about optimality. The addition compression row reports the benets of Algorithm 4, and conrm its important role in making the annotation size negligible w.r.t. the bytecode size. Table 3.2 Considers the analytical cost model of Jikes RVM as a metric. All live ranges annotation correspond to annotation produced by Algorithm 4; LIR5 live ranges annotation correspond to the intersection between the set of live ranges present in the LIR and all live ranges annotation; Java local variables annotation correspond the set of Java local variables present in all live ranges annotation. Table 3.2 shows the penalty (allocation cost / optimal cost) of using the Original Jikes RVM (linear scan), All live ranges annotation, LIR live ranges annotation and Java local variable annotation methods in terms of percentage of the optimal spill cost achieved by the ILP model. The Jikes RVM linear-scan misses the optimal cost by 32% on average, whereas the split allocation only incurs a 11% average penalty. The case for annotation portability is validated by the very close gures for the full annotation (All live ranges) and the LIR-only annotation (LIR live ranges). However, when only annotating Java variables, the annotation loses its eectiveness. Using the LIR-only annotation appears as the best performance/portability trade-o.

Considering wall-clock execution time as a metric (JIT compilation plus execution time), Table 3.3 shows the speedup of split register allocation w.r.t. original JikesRVM's allocation algorithm. In most cases, the speedup is consistent between the optimal and split approaches. Nevertheless, the annotation does not help much on some benchmarks like javac. The strong improvement in the corresponding column in Table 3.2 indicates that the cost model itself misses the complex interplay between optimizations and important components of the target architecture.

Portability Across Variations of the Register Count

We showed there is no formal inclusion property among optimal spill sets in general.

Nevertheless, for every method and among millions of live ranges, we varied R from a minimum equal to the number of pre-allocated physical registers for the method to the spill-free number of registers. Through all these allocation problems only 0.13% of the intervals spilled for R + 1 registers did not belong to the optimal spill set for R registers.

To make the annotation portable across variations in the register count, the compression algorithm must not eliminate a live interval that may be useless for a given number of registers but useful for a smaller number of registers. We thus run Algorithm 4 on R = R min registers, where R min is the minimal number of registers to enable code generation on the target.

3.4

Looking Forward

So far, we ignored important issues related with the practical applicability of split register allocation.

Portability of the Annotation

Let us rst consider the portability of annotation names. The names of the annotated live ranges must remain consistent between the two stages. Some annotations may be missing or extraneous, but an annotation designating a live range during the oine stage must designate to the same live range during the online stage. There are practical solutions for most portability scenarios.

1. The majority of live ranges correspond to Java variables, locations in the operand stack, and other live ranges synthesized in the intermediate, target-independent passes of JikesRVM (the LIR). For those live ranges, a non-ambiguous name can 3.4. Looking Forward 43 be crafted that is independent of the execution context when the JIT compiler is triggered.

2. A fraction of live ranges are synthesized along the target-dependent compilation ow: address computation temporaries, conditional predicates, etc. We discard annotations regarding those live ranges when compiling for another instruction-set architecture (ISA). 6 Fortunately, besides representing a small minority, these live ranges also feature a very short temporal locality and a low degree of interference with other live ranges. This reduces the chances of impacting an important allocation decision that would result in a signicant performance dierence. Indeed, we showed that annotation associated with target-dependent live ranges have negligible impact on performance.

Besides the live range names, annotation properties themselves need to be portable over multiple targets: liveness properties may vary signicantly over the targets if no assumption is made on the optimization ow. To achieve portability, we thus make one important assumption: optimizations selected by dierent JIT compilers must not vary signicantly before the pass where annotations are loaded and attached to the intermediate representation. This restriction does not impact target-specic, post-register allocation passes like instruction selection and local scheduling.

This restriction does not solve all portability problems: reusing annotations across ISAs remains an issue. There are multiple reasons to be optimistic. Some of these are due to the context in which JIT compilation is employed, and some to the nature of the optimizations being performed before register allocation:

• Embedded system designs value the code compression and safety benets of bytecode languages, but do not stress portability to the extreme. Although many processors and hardware congurations may exist, Java or CLI applications are likely to run on some variant of the ARM instruction set. Varying the number of registers is important to support the ARM's compact instruction encoding options, and to support extensions like vector instructions of ARM NEON. On general-purpose platforms, an analogous situation holds, with portability issues from the 32 and 64 bit variants of the x86 instruction set, dierent vector instruction sets and sizes, etc.

• Bytecode languages are important for link-time optimization. Complex software architectures built of thousands of independently designed components bring many opportunities for inter-module optimization at link-time. Again, the ISA portability issue is only secondary to many of these applications.

• Beyond ISA portability, bytecode languages are used for operating system portability. In this case, the JIT compiler is minimally impacted, and annotations are expected to be robust to changes to the underlying OS.

• Eventually, the software provider may easily specialize the oine stage to generate annotations for a particular family of targets and for a particular optimization ow, tagging the annotated bytecode accordingly. This consists of constructing a (lossless) union annotation considering all live ranges that occur when compiling to the dierent targets. Since many live ranges will remain the same (e.g., those associated with Java local variables and constant pool, as opposed to operand stack or target-specic temporaries), the union will not signicantly increase the size of the annotation.

Separate Compilation

Realistic compilation scenarios will run the oine stage separately on the dierent modules of the application and on its library dependences. This raises a modularity problem for any annotation-based online compilation approach.

In the context of object-oriented and functional languages, function inlining is of utmost importance to reach performance levels on par with lower level imperative implementations. It raises the following dilemma:

• what is the point of annotating code in functions that will later be inlined, since the eective interference graph will only be known after inlining;

• what is the point of annotating functions whose calling context heavily inuences the internal control ow, hence the spill costs?

Our approach to modular split compilation is twofold.

No performance regression. First of all, if one module depends on a module without annotations (such as a package form the Java Development Kit), only the code in the annotated module will benet from split compilation. This is not ideal, but not worse than the usual penalty of separate compilation in oine, static compilers. Conversely, when optimizing a library module, it is always possible to run a context-insensitive splitcompilation ow, relying on a representative execution prole; this again is consistent with the traditional way of optimizing libraries in static compilation.

Multiversioning for cross-boundary optimization. Nevertheless, JIT compilation opens many opportunities for link-time optimization, and JIT compilers for object-oriented and functional languages do implement such advanced techniques, eectively optimizing across module boundaries (e.g., across application-library boundaries). Split register allocation is possible in this context. First of all, a context-sensitive annotation of the callee can be tuned according to the most frequent calling context(s). This is only impactful when the costs of the live ranges depend on the calling context, which may be the case when the callee contains complex, data-dependent control-ow.

A more aggressive approach consists in generating multiple versions of the annotations for the most frequent call trees. For example, if a library method m 2 is frequently called from an application method m 1 , the oine stage of the split register allocation may inline m 2 into m 1 , optimize the resulting new method, and generate the annotation for it. This specialized version of the inlined methods can later be checked for consistency with the dynamic execution context (indeed, the library code may have changed in the mean time, or dynamic class loading may have occurred), and used directly in favor of performing all the optimizations online and dropping the (irrelevant) per-method annotation. Practical ways to implement this scheme have been proposed in the QuickSilver project [START_REF] Serrano | Quicksilver: A quasi-static compiler for java[END_REF]. This scheme has all the benets of running a JIT compiler oine (better optimizations, lower overhead) while preserving modularity (up to dynamic class loading) and the eectiveness of split compilation.

Related Work

Annotations are an optional part of the Java bytecode specication from the start and are part of the class le attributes. They have been used in debugging and integrated development environments. Syntactic support has been added in recent versions of Java.

The same applies to the ECMA-335 CLI. Interestingly, annotation-driven JIT compilation was rst directed to register allocation, with the pioneering work of Azevedo et al. [START_REF] Azevedo | Java annotation-aware justin-time (ajit) compilation system[END_REF]. This work demonstrated how to achieve performance competitive with native priority-based graph coloring allocation. Jones and Kamin [START_REF] Jones | Annotating java class les with virtual registers for performance[END_REF] extended their virtual register allocation approach, dealing with correctness, calling conventions and portability (addressing variations of the number of physical registers only).

The split compilation term was rst coined in the context of JIT vectorization [LCC + 07]. Split register allocation improves on Jones and Kamin's annotation-driven approach by leveraging the decoupled allocation (spilling) and assignment (coloring) phases of register allocation. Decoupled register allocation is the key to the compactness and the portability of our annotation. The intuition behind decoupled register allocation is that the assignment problem (mapping of variables to registers with no additional spill) is very easy, as long as the cost of live-range splitting (the introduction or register moves) is neglected. This intuition is backed by the important property that spill-free assignment is always possible if the maximal number of simultaneously live variables (MaxLive) is lower than the number of available registers. The online stage can rely on the colorability guarantee inherited from the oine stage through the annotation: these strong ties between the ofine and online stages are specic to split compilation algorithms, as opposed to classical annotation-driven JIT compilation.

A fully decoupled approach has been used by Appel and George [START_REF] Appel | Optimal spilling for CISC machines with few registers[END_REF], and studied in the context of SSA-based register allocation [START_REF] Magno | Register allocation via coloring of chordal graphs[END_REF][START_REF] Hack | Register allocation for programs in SSA-form[END_REF][START_REF] Bouchez | Register allocation: What does the NP-completeness proof of Chaitin et al. really prove? or revisiting register allocation: Why and how[END_REF]. Notice that recent versions of the linear scan algorithm are capable of live range splitting [START_REF] Wimmer | Optimized interval splitting in a linear scan register allocator[END_REF][START_REF] Sarkar | Extended linear scan: An alternate foundation for global register allocation[END_REF]; they are implicitly based on this decoupled approach. This is not the case for the linear scan implemented in JikesRVM, and leads in practice to spurious spills (to our disadvantage), as we conrmed in our evaluation.

Pominiville et al. [PQVR + 01] used annotations to mitigate the performance penalty of Java pointers and arrays, and designed a generic annotation-driven compilation framework (Soot). Eventually, Krintz and Calder [START_REF] Krintz | Using annotations to reduce dynamic optimization time[END_REF] proposed a comprehensive method to reduce the compilation time overhead through bytecode annotations, enabling rapid method selection and optimization selection, and precomputing simple method statistics.

Several papers address two additional important questions related to register allocation in JIT compilers: is there any room for performance improvement, and is it important to use a linear-time allocation algorithm? Cavazos provides an original answer relying on adaptive optimization [START_REF] Cavazos | Hybrid optimizations: Which optimization algorithm to use? CC'06[END_REF]. Annotation-enhanced versions of this method would be worth investigating.

When using annotations for optimization, safety issues immediately arise because of incorrect or malicious uses. Solutions can be found in proof-carrying code [START_REF] Necula | Proof-carrying code[END_REF], encryption, or correct-by construction annotation designs. We choose the latter approach, relying on annotations whose misuse can at worst lead to performance degradations.

Conclusion

We designed a split compilation framework dedicated to register allocation. We experimentally validated the eectiveness of split register allocation and its portability with 3.6. Conclusion 47 respect to register count variations, relying on annotations whose impact on the bytecode size is negligible. This combination of results is a strong improvement over the state of the art. It was made possible by revisiting the decoupling of the spilling and coloring (a.k.a. assignment) phases. Nevertheless, the approach still depends on the stability of the upstream optimization ow in the JIT compiler. Although this restriction is acceptable in a majority of use cases, it would be useful to design a split register allocation framework that would be more robust to changes in the optimization ow. One direction of work consists in revisiting the context of pre-pass allocation to control register-pressure by inserting additional constraints in the data dependence graph [START_REF] Touati | Early periodic register allocation on ilp processors[END_REF]. This would accommodate for scheduling (local and global) changes, and possibly for code motion, redundancy elimination and hoisting as well.

Chapter 4

Iterated-Optimal Register Allocation

Recent works on register allocation have shown that when enough live range splitting is allowed, the assignment problem can be solved in quadratic time as soon as the maximum number of simultaneously living variables is lower than the number of available registers.

However, the spill minimization problem (an allocation of minimal cost) is NP-complete even when enough live range splitting is allowed [START_REF] Farach-Colton | On local register allocation[END_REF]. Thus, good techniques are needed to solve this problem and especially on systems like CISC machines where only few registers are available.

In this chapter we address the spill minimization problem. Our aim is to achieve fast allocations that are close to optimal ones. We present an iterative register allocation algorithm, called iterated-optimal allocation, which can be used to perform allocation in both decoupled and non-decoupled contexts. We compare it with the graph coloring, the linear scan, a newly devised heuristics called mixed heuristic, and an optimal ILP-based register allocation algorithm. The results show that the iterative ILP-based algorithm outperforms the other heuristics and is often close to the optimal. An interesting result of our approach is that, for SSA programs, the iterated-optimal allocation method has a pseudo-polynomial time complexity.

4.1

The Approach

In the rest of this chapter we address both the spill everywhere and the register allocation problem with live range splitting. We assume that an estimated spill cost has been computed for each variable. A spill cost represents the access frequency of a variable, it is high when the variable is frequently accessed and low when it is not. We denote R the number of available registers and R min the minimal number of registers to enable code generation on the target architecture. We assume that R min is small, in our experiments 50 Chapter 4. Iterated-Optimal Register Allocation with JikesRVM running on x86 machine, R min is equal to 2. The spill minimization problem is NP-complete for programs in SSA form [BDR07c, YG87] and thus for general programs. An important result, proven independently by Yannakakis et al. [START_REF] Yannakakis | The maximum k-colorable subgraph problem for chordal graphs[END_REF] and Bouchez et al. [START_REF] Bouchez | On the complexity of spill everywhere under ssa form[END_REF], is that the spill minimization problem for SSA programs is pseudo-polynomial. That is, it is solvable, by dynamic programming, when R is xed to a small number. The intuition of our solution derives from this result. Our approach is to solve the spill minimization problem for general programs with R registers by iteratively optimally solving the spill minimization problem with few registers. Even if, the spill minimization problem is only pseudo-polynomial for SSA programs, we validate in our experiments that, for general programs, iteratively solving the the spill minimization problem with few registers gives results close to optimal while being much faster than directly solving the optimal problem with many registers (with R registers, where R is not constrained to be small).

Algorithm 6 iterated-optimal allocation

Input: var_list: The list of variables Var: allocated_list: The list of so far allocated variables 1: result ← OptimalAllocation(var_list, R min ) 2: add every variable of result to allocated_list 3: remove every variable of result from var_list Algorithm 6, which depicts our approach, receives as input var_list, the list of variables that are candidate to register allocation. It then returns as result allocated_list, the list of variables that have been allocated with R registers. In its rst step (lines 1 to 4), Algorithm 6 calls the function OptimalAllocation which returns the optimal set of allocated variables minimizing the spill cost (optimal allocation set), with a register count of R min . It adds the returned variables to allocated_list, and then removes them from var_list. In its second step (lines 5 to 10), Algorithm 6 iteratively nds the optimal allocation set, with a register count of step, among the variables that have not yet been allocated (currently in var_list). Like R min , the parameter step is a small number (we used 2 in our experiments) which guarantees that the function OptimalAllocation will be polynomial in the case of SSA programs and fast in the case of general programs. In its last step (lines 11 to 15), Algorithm 6 nds the set of variables that minimizes the spill cost among the variables remaining in var_list if Rcount registers are available.

We can notice that Rcount is smaller than step. The function OptimalAllocation optimally solves the spill minimization problem, e.g. by dynamic programming, integer linear programming (ILP), or logic programming.

In Algorithm 6, the number of registers available at each iteration is limited to step registers because we do not want to increase the complexity of the problem, with registers that have been considered and allocated at the previous step.

Close to optimal. Our method described in Algorithm 6 does not produce an optimal allocation. This is for the same reason as the spill set inclusion does not always hold as shown in Figure 3.1. Let us assume that R is equal to 2, R min is equal to one, step is also set to one, and we run Algorithm 6 on the ve variables: i 1 , i 2 , i 3 , i 4 and i 5 . In its rst step, Algorithm 6 will nd the optimal allocation set composed of variables i 1 , i 3 and i 5 , and mark them as allocated. In its second step, it will nd an optimal allocation composed of either i 2 or i 4 . Finally, Algorithm 6 will return either {i 1 , i 2 , i 3 , i 5 } or {i 1 , i 3 , i 4 , i 5 } of spill cost 2 as result, while the optimal allocation set is {i 1 , i 2 , i 4 , i 5 } of spill cost 1.

Pseudo-polynomial on SSA programs. For SSA programs, the complexity of the function OptimalAllocation is polynomial, if it is solved by dynamic programming and for a small register count. Thus, Algorithm 6 is also polynomial if R min and step are chosen to be small numbers.

Experimental Evaluation

Methodology

In order to evaluate our approach, we have dumped all the register allocation problem instances obtained during the JIT compilation of the methods of the SPEC JVM 98. The methods have been compiled with the following options of JikesRVM:

-Xmx1024M -Xms1024M -X:irc:O3 -X:aos:enable_recompilation=false -X:aos:initial_compiler=opt -X:aos:enable_replay_compile=true -X:vm:edgeCounterFile=my_edge_counter_file

In our experiments, the function OptimalAllocation, which returns the optimal allocation set, is implemented by ILP. R min is xed to 2 because, on x86 architecture JikesRVM performs precoloration with two registers. The variable step is set to 2. We also considered dierent congurations of register count going from 2 to 16 registers. For each instance of the register allocation problem and for each conguration, we compared our approach with the following algorithms:

1. Default linear scan: the linear scan algorithm which takes advantage of holes.

2. Belady linear scan: the linear scan algorithm which takes advantage of holes and which uses the furthest rst strategy to choose between two variables to spill if their costs are close enough according to a chosen threshold.

3. Mixed heuristic: an algorithm which chooses the algorithm which has the smaller spill cost among the linear scan and an algorithm which spills as a priority the most constrained variables.

4. GC: the graph coloring algorithm.

5. Optimal: an optimal ILP-based allocation algorithm which computes the optimal allocation.

Results

Figure 4.1 shows the allocation costs of all the benchmarks for each register count. The allocation costs have been normalized using the optimal allocation's cost. The iteratedoptimal allocation algorithm is close to the optimal except for register counts 14 and 16, it always outperforms the others. Figure 4.2 reports the allocation costs for each benchmark, normalized using the optimal allocation's cost, when the register count is 6, the register count of x86 machines. We see that here again, the iterated-optimal allocation algorithm performs close to optimal allocation and outperforms all the other allocation algorithms.

Table 4.1 shows, for all benchmarks, the time spent in milliseconds to solve the ILPprograms of the optimal and the iterated-optimal allocations. We see that when the register count is 2, the time spent to solve optimal ILP-programs and iterated-optimal are almost the same. But for all the register counts, we notice important speedups when Iterative-optimal compared to other allocators when the register count is 6 using the iterated-optimal allocation algorithm compared to using the optimal one, while producing approximately the same allocation. With 6 registers we have a speedup of 8x and when we exceed 8 registers the speedups reach 100x. This shows great improvements and shows that it is possible to achieve fast allocations that are close to optimal. Register allocation algorithms often rely on spilling algorithms to perform spill minimization.

Chapter 4. Iterated-Optimal Register Allocation

In static compilation the dominant approach to register allocation is the graph coloring in which the spilling and coloring (assignment) algorithms are interleaved. During the Simplify phase, whenever all the remaining nodes have at least k degrees, a node needs to be marked as spilled or pushed onto the stack (optimistic coloring) and removed from the graph. A natural intuition is to choose a node that has a low spilling cost and which interferes a lot. Many graph-coloring-based allocators are based on this intuition and use the quantity cost(v)/deg(v) to choose the variables to spill [START_REF] Chaitin | Register allocation & spilling via graph coloring[END_REF]. Thus, the spilling algorithm uses a global information over the whole program that combines the interference degree and the spilling cost.

In the context of just-in-time compilation, the compilation time is part of the global execution time and (quasi-)linear complexity remains a driving force in the design of optimization algorithm. Moreover, when embedded systems are addressed, the limited memory resources is also an important issue. The linear scan which is one of the most used register allocation algorithm on JIT compilers has a worst case complexity of O(n × k), where n is the number of variables in the program and k is the number of available registers on the target architecture. The original spilling heuristic used in linear scan [START_REF] Poletto | Linear scan register allocation[END_REF] is based on the Belady's furthest rst algorithm [START_REF] Belady | A study of replacement algorithms for virtual storage computers[END_REF]. This algorithm relies on local information to perform spilling: At a point p where registers are not enough to hold all the live variables, spill the variables whose live ranges go farther in the future.

May be the variable chosen for spilling will not interfere a lot in the future and will be accessed many times or may be it will only be accessed once after this point. But, since

we are using a local information we cannot answer this question at the point p. Recent versions of linear scan use more elaborate algorithms which are based on variables's spill cost estimation and even sometimes use the same spilling heuristics used by graph coloring [START_REF] Sarkar | Extended linear scan: An alternate foundation for global register allocation[END_REF]. This gives more global information on which to rely to make spilling decisions in linear scan.

The idea of improving the spill minimization in a decoupled approach, where the allocation is decoupled from the assignment, has been explored by Proebsting and Fischer [START_REF] Proebsting | Probabilistic register allocation[END_REF], and by Braun and Hack [START_REF] Braun | Register spilling and live-range splitting for ssa-form programs[END_REF]. Braun and Hack generalized the Belady's furthest rst algorithm, which works very well on straight-line code, to control-ow graphs.

Their approach, while being applicable as a pre-spill phase in any compiler, is more adapted to a use in SSA-based register allocation. In their evaluation, they reported that with their approach they reduced the number of reload instructions by 54.5% compared to the linear scan and by 58.2% compared to the graph coloring. Like the approach of Braun and Hack, the iterated-optimal allocation algorithm is fast and can be applied as a pre-spill phase or a non-decoupled allocation for general programs and as a decoupled allocation phase for SSA programs. However, unlike Braun and Hack, we experimentally show how the iterated-optimal allocation algorithm is close to optimal allocations.

Conclusion

We have presented the iterated-optimal allocation algorithm which is a new approach to solve the spill minimization problem. It is fast and produces allocations that are close to optimal ones. The iterated-optimal allocation algorithm is pseudo-polynomial (polynomial, when step and R min are xed to small numbers) on SSA programs. It can be used in a non-decoupled context for general programs, in a decoupled context for SSA programs, and as a pre-spill phase in any compiler.

Part II Local Memory Allocation

Chapter 5

Local Memories and Allocation Techniques

Introduction

In Chapter 1, we saw that to reduce the performance gap between the processor and the memory, modern computers use a memory hierarchy. It corresponds to an organization of the memory into dierent levels based on their size and speed of access. The faster and smaller levels of memory are placed closer to the processor and the slower and larger ones are placed farther from the processor. Typically, modern computers, have a small number of registers, followed by a small amount of on-chip static RAM (SRAM) going from some kilobytes to many megabytes in size. The next level is the physical main memory (ochip memory) going from hundreds of megabytes to many gigabytes of dynamic RAM (DRAM). Usually, in desktop computers, the on-chip SRAM is congured as a hardware cache. The hardware mechanism automatically stores frequently used instructions and data into the cache memories.

The alternative approach to manage on-chip SRAM is to congure them as softwarecontrolled local memories, also called local memories or scratchpad memories. In such an approach the developer or the compiler must insert explicit instructions to transfer data between the local memory and the main memory. Local memories are often preferred to caches due to their better performance, their power eciency, and their smaller area cost. Indeed, in a detailed study Banakar et al. [BSL + 02] make a comparison between local memories and caches. The authors measured 18% runtime improvements in cycles for a conguration using local memory over one using a cache, when the allocation was performed with a simple knapsack-based algorithm. They also found that on average, 60 Chapter 5. Local Memories and Allocation Techniques compared with a cache of same capacity, a local memory occupies an area 34% smaller and reduces the power consumption by about 40%. Moreover, local memory guarantee better time predictability for real time systems. Indeed, the access time of each memory object can be predicted, since the compiler or the developer exactly knows where it is located, either in the local memoryor the main memory. Given all the above-mentioned advantages of software-controlled local memories over caches, one may ask why caches are still used in desktop computers? The reason is that with caches it is possible to guarantee the binary code portability [UDB06], while local memories do not provide such a guarantee. It is possible for the same program to be executed across dierent computers with dierent cache sizes. In contrast, a code compiled for a local memory of a given size is not portable across architectures of dierent local memory sizes. The binary portability is not the main issue in the embedded world because the hardware is known and software is often loaded in it within the factory and is rarely modied afterwards.

Most ARM processors have an on-chip local memory [START_REF] Arm | ARM DDI 0084D[END_REF], and more generally, it is typical for DSPs and embedded processors to have local memories [START_REF] Motorola | [END_REF][START_REF]Texas Instruments[END_REF]. More specialized processors also utilize local memories, including stream-processing architectures such as graphical processors (GPUs) and network processors [START_REF]NVIDIA unied architecture GeForce 8800 GT[END_REF][START_REF] Burns | Implementing address assurance in the Intel IXP[END_REF]. Most processor(s) may directly access the main memory, but few exceptions exist. The IBM Cell broadband engine's synergistic processing units (SPU) [KDH + 05] which rely exclusively on Direct Memory Access (DMA) for instruction and data transfers with main memory.

To take advantage of all the potentials provided by local memories, it is essential to use them eciently. This is the goal of an optimization problem called local memory allocation. The local memory allocation is dened as comprised of the following two sub-problems which are solved either together or separately:

1. the allocation which selects the set of variables that will reside in the local memory at each point of the program.

2. the assignment which nds the specied place in the local memory where a variable will reside.

Previous work on local memory allocation addressed it from dierent angles, targeting for both application code and data placement. All the existing allocation methods can be classied in two categories: static allocation methods and dynamic ones. Static methods place variables in the local memory only once in the beginning, and throughout the entire execution the contents of local memory remains invariant. In contrast, dynamic methods place data/code in the local memory at a certain moment during the execution and in the main memory at a dierent moment depending on its access frequency. Dynamic methods reect the dynamic behavior of the program and generally outperform static ones except when code size is extremely constrained [START_REF] Sumesh Udayakumaran | Dynamic allocation for scratch-pad memory using compile-time decisions[END_REF]. As a result, recent research mainly focuses on dynamic methods. The two next sections present respectively the main works that have been done in static and dynamic allocation strategies.

Static Allocation Methods

Early techniques for local memory allocation were mostly static. Among these static allocation methods, we mention the works of Steinke et al. [START_REF] Steinke | Assigning program and data objects to scratchpad for energy reduction[END_REF], Sjodin and Von Platen [START_REF] Sjödin | Storage allocation for embedded processors[END_REF], and Avissar et al. [START_REF] Avissar | An optimal memory allocation scheme for scratch-pad-based embedded systems[END_REF]. The method proposed by Steinke et al. analyses the application and decides which part of both data and code to place in the local memory. They formulated the problem as an integer linear programming (ILP) knapsack problem and proved an improvement between 12% and 43% in energy consumption over a cache solution.

Sjodin et al. used an ILP formulation to solve the static local memory allocation problem [START_REF] Sjödin | Storage allocation for embedded processors[END_REF]. In their work, the authors handled global variables and focused on the fact that it is very common to have dierent native pointers that are used to access the dierent kinds of memory available in embedded systems. For instance, the Intel 8051 has three native pointer types: an 8-bit pointer to access the internal memory, a 16-bit pointer to access the external memory, and a 16-bit pointer to access the code memory. They optimized the use of native pointer types to improve the execution speed and to reduce the code size.

Avissar et al. also proposed an ILP formulation to perform a static allocation over dierent types of memory (local memory, main memory) [START_REF] Avissar | An optimal memory allocation scheme for scratch-pad-based embedded systems[END_REF]. In contrast to Sjodin et al. who only managed global variables, Avissar et al. considered also stack variables in their allocation. Moreover, they used a distributed stack technique [START_REF] Barua | Compiler support for scalable and ecient memory systems[END_REF] which distributes stack variables among dierent memory units (local memory, main memory). The results show 44% reduction in runtime when using the distributed stack strategy compared to using a unied stack. They also reported a reduction of 11% in runtime when using ILP compared to using a greedy strategy consisting of sorting the variables according to their size and then trying to allocate the variables of smallest size to the fastest memory.

Static allocation methods are however limited compared to dynamic ones because they do not handle the dynamic behaviours of the program being executed. That is, they do not maintain the set of frequently accessed data in the local memory, at each time. This issue is addressed by dynamic methods presented in the next section.

Dynamic Allocation Methods

The rst dynamic allocation methods were restricted to software-caching techniques [MFA01 [START_REF] Verma | Dynamic overlay of scratchpad memory for energy minimization[END_REF]. In their approach, they solved separately the allocation and the assignment problems. The rst step of their solution identies the candidate variables which are composed of global variables, non-scalar local variables and frequently executed code segments. In the second step, a liveness analysis is performed. The controlow graph 7 (CFG) edges are chosen to be the points where allocation decisions and data transfers between the local memory and the main memory will be performed. The third step optimally nds the set of allocated variables and the nal step nds an address in the local memory for each allocated variable under the restriction that a variable is assigned to the same address each time it is allocated. This technique, compared with a static allocation technique, shows improvements of 34% in energy consumption and 18 % in execution time. However, this technique is limited by two practicability issues. First, for large programs the solution times can be exponential. Second, due to intellectual property issues it is rare to nd an industrial compiler which integrates an ILP solver.

An interesting work that does not suer from the above-cited problems has been introduced by Udayakumaran et al. [START_REF] Sumesh Udayakumaran | Dynamic allocation for scratch-pad memory using compile-time decisions[END_REF]. The authors propose an approach for the compiler-assisted dynamic allocation of global and stack data, and explain how to extend this approach with some minor modications to also allocate program code. They split the program into dierent regions, which are dened as the code between successive program points. Each program point starts before a procedure call or before loop beginning. At every program point, they keep track of timestamps, where a timestamp refers to one path beginning from the entry to a parent node of the current point. They allocate data onto the scratch-pad memory between program regions. More specically, they allocate based on the access frequency-per-byte of a variable in a region, collected from the prole data. For each program point visited in the timestamp order, they choose the variables to place in the local memory among the ones that are going to be accessed in the next region. The allocation remains xed within a region. In a separate phase, the method performs an assignment for each region as follows:

1. The method collects the list of free holes in the local memory. These holes are due to de-allocation of variables that are either dead or spilled.

2. It attempts to allocate the incoming variables to the available free holes. The largest variables are placed rst in a best-t fashion.

3. When, a hole of adequate size cannot be found for a variable, compaction, which is the process of moving variables in order to reduce fragmentation, is considered. It is performed if it is more protable than spilling the variable.

4. If the compaction is not protable, the method tries to nd a cheaper variable to spill among the already assigned variables in the local memory. If such a variable cannot be found, it is spilled to o-chip memory.

This method is quite successful and in their experiments the authors reported on average improvements of 39% in runtime and 31% in energy consumption depending on the local memory size used, when comparing with an optimal static allocation.

Li et al. introduced another approach which uses an existing graph coloring technique to perform memory allocation for arrays [LGX05, LFX09

]. There are three main parts in the presented approach, where in the rst phase, local memory is partitioned into a pseudo-register le with interchangeable and aliased registers. This phase is followed by a live-range splitting phase, where suitable program points are generated based on the live-ranges of the arrays. The copy statements between the local memory and the ochip memory are inserted at these points. Third, memory coloring is performed within a register allocation framework, to remove unnecessary copy statements during live-range splitting. The advantages of this work are that it uses a very mature framework (the graph coloring) and leverages live-range splitting to optimize the exploitation of the local memory. The weakness is that the partitioning of the local memory into dierent register class can lead to excessive fragmentation.

In a recent work, Li et al. take a more theoretical approach and proposed a way to eectively decouple the local memory allocation with optimal guarantees in the assignment phase [START_REF] Li | Scratchpad allocation for data aggregates in superperfect graphs[END_REF][START_REF] Li | Scratchpad memory allocation for data aggregates via interval coloring in superperfect graphs[END_REF]. The authors observed that in many embedded applications most arrays present a specic live range behavior. Specically, for any two arrays, their live ranges (the list of program points where they are live 8 ) are either disjoint or one of them is contained by the other one (containment property). They showed that, for the tested benchmarks, it is extremely rare to have two live ranges which interfere with one another without containment. When this happens, they extend the live range of one of the arrays to contain the other. Authors proved that the interference graph of an application with such a property is a comparability graph which is a superperfect graph and hence optimal interval-coloring for these array interference graphs is possible. Based on this observation, they rely on the maximum weighted clique to guarantee the optimal colorability of generated interference graph. When the maximum weighted clique exceeds the size of the local memory, they use heuristics to spill or split some of the live ranges until the resulting graph is optimally colorable. While this work is interesting, it is restricted to applications where most arrays satisfy the containment property.

Conclusion

In this chapter, we have seen that in the embedded world, local memories are often preferred to caches due to their better performance, their power eciency, their smaller area cost and their better time predictability. We have presented rst the static techniques to local memory allocation and then the dynamic methods which are often superior to static ones.

Chapter 6

Motivation and Approach to Local Memory Allocation

Software-controlled local memories are widely used to provide fast, predictable, and power ecient access to critical data. Compilation-time local memory allocation has been connected to register allocation for at least 30 years. Indeed, in her seminal paper [START_REF] Fabri | Automatic storage optimization[END_REF], Fabri reported strong links between register allocation and local memory allocation. The author also presented fundamental results and practical insights about the interplay with loop transformations. Much of this has been ignored until very recently. As a result, the series of tremendous, fundamental and applied advances redening design of compiler backends have also been ignored in the eld of local memory allocation [AG01, BDGR06a, HGG06, BDR07c, PP08].

In this chapter we explain what has been motivating our work on local memory allocation, what is our approach to tackle the problem, and how we compare it to previous works.

Motivation

Our work on local memory allocation is motivated by recent progress in register allocation and the question of optimality in local memory allocation.

Decoupled Allocation

Recent progress in register allocation leverages the complexity and performance benets of decoupling its allocation and assignment phases [START_REF] Appel | Optimal spilling for CISC machines with few registers[END_REF][START_REF] Bouchez | On the complexity of spill everywhere under ssa form[END_REF]. The allocation phase decides which variables to spill and which to assign to registers. The assignment phase 66 Chapter 6. Motivation and Approach to Local Memory Allocation chooses which variable to assign to which register.

The allocation phase relies on the maximal number of simultaneously living variables, called MaxLive, a measure of register pressure 9 . When ne-grain enough live-range splitting is allowed, it is sucient, for all the live ranges to be allocated, that MaxLive is less or equal to the number of available registers to guarantee that the forthcoming assignment phase can be done without further spill. In many cases, assignment can even be achieved in linear time [START_REF] Bouchez | On the complexity of spill everywhere under ssa form[END_REF]. If at some program point the pressure exceeds the number of available registers, needs to be reduced through spilling.

This decoupled approach permits to focus on the hard problem, namely the spilling • most papers assume a local copy operation with a much lower cost than loading or storing to main memory;

9 Not the sum of array block sizes.

Motivation

67

• one may also address each local-memory-allocated array block with its own dedicated pointer; this increases register pressure but brings down the cost of oset reconciliation to a plain pointer copy.

In the context of local memory management, the maximum size of simultaneously living arrays10 , called MaxSize, gives a measure of local-memory pressure. Again, like for register allocation, live-range splitting helps to reduce the local-memory pressure. Since arrays are frequently accessed inside loops, local memory allocation algorithms often split arrays at loop-entry points , we call these points: decision points. Decision points can also be chosen in a ner manner, after loops or before array accesses. Local memory pressure can also be reduced by loop-transformations like strip-mining, and tiling, which reduce the portion of accessed arrays. Moreover local memory oset reconciliation can be implemented with pointer copies. With such an assumption, the array move/spill ratio becomes negligible w.r.t. the already low register move/spill ratio. For all these reasons, the study of a decoupled approach in the local memory allocation context seems very appealing.

Example

// Nested within outer loops for (i=0; i<N; i++) for (j=0; j<N; j++)

C[i][j] = /* ... */; F[0][0]=1; F[0][1]=2; F[0][2]=1; F[1][0]=2; F[1][1]=4; F[1][2]=2; F[2][0]=1; F[2][1]=2; F[2][2]=1;
Figure 6.1: Example: Edge-Detect Figure 6.1 shows a code fragment from the UTDSP benchmarks [START_REF] Lee | UTDSP benchmarks[END_REF]. This fragment has been slightly simplied for the sake of the exposition, preserving the original array data ow. Generally, arrays are frequently accessed inside loops. As a result, local memory allocation algorithms often (re)consider allocation decisions at loop entry points; a form of live-range splitting. On this code fragment, if live-range splitting is only considered at loop entry points, accesses to C will articially coincide with accesses to F. Zooming to the grain of individual program statements, the live ranges of these two arrays are in fact disjoint. Finer grain decision points would be benecial. It is interesting to take allocation The previous example shows the importance of the selection of decision points (live-ranges splitting) to take advantage of the dynamic behavior of the program for local memory allocation.

In the following, main memory refers to the main typically o-chip DRAM memory resources; local memory refers to typically on-chip SRAM low-latency, high-bandwidth memories to exploit temporal locality and hide the cost of accessing the main memory.

We will only consider single-threaded code running on a single local memory. To extend our results to single-threaded code running on multiple local memories with dierent characteristics, the gap is expected to be very narrow, analogous to register allocation on multiple register classes and register les.

Having set the context of the optimization problem, we present in the following the preliminary analyses and transformations we assume already performed and we present three live range splitting schemes that can be adopted to tackle the problem.

Preliminary Analyses and Transformations

We make several assumptions while formulating the local memory allocation and assignment problem. We currently restrict our approach to uniform array accesses only. On the abstracted program, array blocks play the role of scalar variables in a register allocation problem, with the exception of cost modeling. We keep track of the access frequency of each execution point to capture the number of accesses for each array block.

To benet from its algorithmic properties, we extend the SSA form to operate on array blocks. This extension diers from Array SSA proposals [START_REF] Knobe | Array SSA form and its use in parallelization[END_REF][START_REF] Rus | Region array SSA[END_REF], in that it does not attempt to model the data ow of individual array elements. In this form, array blocks are fully renamed, and name conicts at control-ow points are handled with Φ functions following the rules of strict SSA form.

From array blocks, one need to extract live ranges which will be the subject of the allocation and assignment decisions. Live ranges generalize live intervals in basic blocks to arbitrary control ow; in SSA form, extraction of live ranges can be done in linear time [START_REF] Hack | Register allocation for programs in SSA-form[END_REF]. Live ranges and detailed proling of the application is then used to generate the frequencies for dynamic allocation. Using these live ranges, for each decision point (as will be explained in more detail in Chapter 7) and for each array block alive at this point we keep track of the access frequencies. From these access frequencies and from the size of each array block we compute an estimated of the cost of accessing an array block in the local memory or in main memory. The cost of accessing array blocks in main memory depends on the access pattern of the considered architecture. On systems that rely exclusively on DMA, for data transfers, accessing a single element of an array block is as expensive as accessing the whole array block. In contrast, on systems where the main memory can be accessed directly, accessing a single element is much cheaper than accessing the whole array block. Note that, moving array blocks within the local memory at every decision point may add severe overheads, limiting the eective benets of live-range splitting. To avoid such penalties, we only move the pointers of these array blocks rather than moving the chunk of data.

In fact, this low-cost solution may seem so appealing to the reader that she may wonder why it was not considered in the state-of-the-art techniques. The main reason is of course that a decoupled allocation/assignment scheme is necessary to make sure that all array block moves induced by the assignment phase are associated with oset reconciliation across dierent control-ow paths. When resorting to a unied allocation-and-assignment algorithm with live-range splitting [START_REF] Sumesh Udayakumaran | Dynamic allocation for scratch-pad memory using compile-time decisions[END_REF], there is no such guarantee. Some moves are associated with real needs for array block displacement. Another reason is the increased pressure on the registers: we consider that a register spill is a lot cheaper than local memory block-copying, and even if repeated register spills occur in an inner loop (which is very unlikely on RISC or VLIW processors), it will not be more expensive than an array block displacement; further experimental analysis and tradeos should be explored in the future.

Following Udayakumaran et al. [START_REF] Udayakumaran | Compiler-decided dynamic memory allocation for scratch-pad based embedded systems[END_REF], we extend every basic block with a nal program point. This extra point will be used to capture any live range load or eviction at the end of the basic block, isolating the formalization of this decision from the reconciliation of the decisions associated with incoming/outgoing control-ow arcs. Thanks to this extra point, the only cross-basic-block equations will be reconciliation equations.

Allocation Schemes

Live-range splitting can be implemented at dierent decision points depending on a customizable grain/aggressiveness. One objective could be to optimize local memory usage at every instruction execution, whereas another one could be to statically allocate the arrays for the whole execution of the program. This is analogous to the options in the register allocation problem, where the compiler designer needs to trade latency minimization for complexity. This tradeo can be instantiated into three typical schemes:

Scheme 1. One could make decisions at ne granularity points, where a point indicates 6.3. Related Work 71 an abstract array block instruction. This will exploit the array allocation and assignment at instruction granularity, providing a full latency minimization. However, modeling this scheme as an ILP-program may incur excessive complexity, due to the number of decision points.

Scheme 2. The second approach is similar to the SSA-based register allocation approach, where one may only take allocation decisions at points where a live range becomes alive.

Scheme 3. The third approach is to make an allocation decision per array block, without any splitting. This approach is called static in the context of LM management, and corresponds to the spill-everywhere register allocation problem. In this case, there are no program/decision points, leading to a much simpler optimization problem. However, the connection between MaxSize and colorability is lost, and the execution latency will be higher compared to the previous schemes.

Related Work

While previous studies addressed local memory allocation from dierent angles, targeting both code and data, we are especially interested in data allocation [KRI + 01, IBMD07]. We target dynamic methods which are superior to static ones except when code size is extremely constrained [START_REF] Sumesh Udayakumaran | Dynamic allocation for scratch-pad memory using compile-time decisions[END_REF]. We elaborate on three recent series of results targeting stack and global array allocation in local memories, embracing the analogies with register allocation. The rst approach [LGX05, LFX09], uses an existing graph coloring technique to perform memory allocation for arrays. The second approach [UB03, UDB06, ABS02] allocates data onto the scratch-pad memory between program regions separated by specic program points. The closest work to ours is the third approach [START_REF] Li | Scratchpad memory allocation for data aggregates via interval coloring in superperfect graphs[END_REF], where authors observed that in many embedded applications it is extremely rare to have two live ranges which does not respect the containment property. While this work is interesting, it is restricted to applications where most arrays satisfy the containment property. Compared to these three approaches, our work leverages the decoupled allocation/assignment approach, allowing scalable and more eective algorithms. Moreover, it oers much more exibility in terms of integration of architecture constraints and performance models. We are able to analyze the tradeos involving live range splitting, like SSA-based techniques, as well as the eects of loop transformations.

Conclusion

We presented in this chapter the reasons that motivate our work on local memory allocation. We then presented the assumptions we made and the approach we chose to solve this problem and we nally show how our work is related to previous ones.

Chapter 7 Experimental Validation

In this chapter we intend to experimentally validate our intuition of a decoupled approach to the local memory allocation problem. First, we express the allocation of array blocks as an ILP-program (the decoupled ILP-program), which minimizes the cost of accesslatency (execution time). A solution to this ILP-program can then be used in a subsequent assignment stage, to set the osets of the allocated array blocks into the local memory.

Because of the fragmentation of the local memory into uneven regions, this is not sucient to guarantee that the assignment stage will succeed without further spilling. This is a major dierence with the classical register assignment problem. A solution consists in adding fragmentation-avoidance constraints to the ILP-program (the integrated ILPprogram). We then compare, for each of the used benchmarks, the cost returned by the decoupled ILP-program to the one returned by the integrated ILP-program. If the costs are equal, we can envisage a theoretical study of a decoupled approach to the local memory allocation problem.

Allocation

This section addresses the execution time minimization problem using integer linear programming. All the variables in the ILP-program are associated with decision points within a given program. These points represent live range splitting points where allocation decisions are taken and memory transfer instructions may be inserted. There are various outcomes for each live range, each one being characterized by the ILP-program: (i) evict the live range from the local memory, (ii) load the live range from main memory to the local memory, (iii) keep the live range in the local memory, (iv) leave the live range in the main memory. In this regard, ILP variables closely match those introduced by Appel and George [START_REF] George | Iterated register coalescing[END_REF].

Let us formalize the ILP-program. The size of the local memory is denoted as S; the size of live range v is denoted as s v . The access frequency of a live range is dened as the frequency per byte of its corresponding array block; the access frequency per byte of live range v at point p is denoted as fpb v,p .

For each point p and for each live range v alive at p, we dene the following variables:

• r v,p is a {0, 1} variable, set to one when v is allocated to the local memory at point p. Otherwise, it is set to zero. Since r v,p is a {0, 1} variable, 1r v,p captures the live ranges residing in main memory.

• l v,p is a {0, 1} variable, set to one when v is loaded into the local memory at point p. Otherwise, it is set to zero. This variable is related to r v,p and r v,p-1 : if v is not in the local memory at point p -1, i.e., if r v,p-1 = 0, and if it is in the local memory at point p (r v,p = 1), then v is loaded at point p.

• e v,p is a {0, 1} variable, set to one when v is evicted from the local memory at point p. Otherwise, it is set to zero.

• d v,p is a {0, 1} variable, set to one when v is dirty, i.e., when v is updated and needs to be written back to the main memory in case of an eviction. Otherwise, it is set to zero.

• u v,p is a {0, 1} variable, set to one when v needs to be updated. That is, if v is evicted and dirty, it will be written back to the main memory. More specically, it is the logical AND of e v,p (evict) and d v,p (dirty).

In a basic block, we capture the values of l v,p and e v,p using r v,p at successive points p -1 and p:

l v,p ≥ r v,p -r v,p-1 . (7.1)
This constraint makes sure that live range v is loaded if it was not in local memory at point p -1 whereas it is in local memory at point p. At points where there is an explicit assignment to v, we set l v,p to 0 since the array block is being modied and a local copy would be useless. Notice that we are dealing with partial updates of array blocks, and assignment points are not necessary kill points for live ranges.

Similar to a load, a live range v is evicted if it is in the local memory at point p -1 but it is not anymore in the local memory at point p: e v,p ≥ r v,p-1r v,p .

(7.2) 7.1. Allocation 75 However, this is not enough to characterize every eviction since we only set a ≥ inequality and we do not have any term that (in)directly minimizes eviction in the objective function. Indeed, eviction can be free, such as when the data is being evicted but it has not changed. Setting an equality constraint would not be correct either. To prevent this, we add the following constraints to provide additional upper-bounds on e v,p :

e v,p ≤ r v,p-1 . (7.3)
If v is in the local memory at point p or if it is not in local memory at point p -1, then e v,p will be forced to 0. However, if we do not add these constraints, it could be either 0 or 1 depending on the update.

Every assignment statement will mark the target live range as dirty. We formalize this as:

∀p i , d v,p i = 1
, where variable v is modied. (

Moreover, if v in the local memory is dirty, it should be continuously dirty until it is written back to the main memory. We enforce the following constraint at every point except those where live range v is modied. For those cases, Equation 7.4 will be used:

d v,p ≥ d v,p-1 -u v,p-1
, where variable v is not modied. (7.5) This constraint makes sure that if v is dirty at point p -1 and it is still in the local memory at point p, then it should be dirty at point p as well. This, in a sense, operates as dirty bit in a cache coherence protocol. Also, d v,p will be forced to be set as 0, if v is not in the local memory at point p -1. This will ensure that, if v is loaded at point p it will not be dirty:

d v,p ≤ r v,p-1
, where variable v is not modied. (

Deriving from dirty variables, update variables u v,p are set to 1 if v is evicted at point p and is marked as dirty. We formally express this boolean AND as follows:

u v,p ≥ e v,p + d v,p -1 ∧ u v,p ≤ e v,p ∧ u v,p ≤ d v,p . (7.7)
We also need to make sure that the available local memory space is not exceeded. At every point p we add the following constraint:

∀p, v r v,p × s v ≤ S. (7.8)
Finally, we need to make sure that the local memory remains in the same state as we iterate through the basic blocks of the application CFG. To ensure this, we add entry and exit points to basic blocks. This way, we check the states at every merge/split point whether they are in the local memory or not. More specically, for such pairs of points p and p ′ :

∀v, r v,p = r v,p ′ . (7.9)
The objective function to be minimized is the following:

v,p r v,p × lr v,p + l v,p × ll v,p + u v,p × le v,p + (1 -r v,p ) × lm v,p .
It models the cost of array block load, eviction, access in the local memory, and access in the main memory. Since we follow a decoupled allocation/assignment approach, it does not account for reconciliation costs, implemented as negligible-cost register moves. This function depends on the following additional notations:

• lr v,p is the sum of all latencies incurred by an access to v between p and p + 1, the following point, where v was in the local memory at p:

lr v,p = latency_LM × fpb v,p × s v .
• ll v,p is the sum of all latencies incurred by an access to v between p and p + 1, where v was in the main memory before p, and in the local memory after p: ll v,p = latency_reload(s v ) × point_frequency p .

• le v,p is the sum of all latencies incurred by an access to v between p and p + 1, where v was in the local memory before p and in the main memory after p:

le v,p = s v × latency_spill(s v ) × point_frequency p .
• lm v,p is the sum of all latencies incurred by an access to v between p and p + 1, where v was in the main memory before, and after p:

lm v,p = latency_MM × fpb v,p × s v .
Each update variable acts as a switch to turn on or o the cost of the eviction, depending on the dirtiness of the corresponding live range.

This linear program is exible w.r.t. the tradeos between live-range splitting and complexity, and adapts to the three proposed schemes, mentioned in Chapter 6. Of course, the p subscript will disappear for Scheme 3. For Scheme 1, r v,p , l v,p and e v,p will be dened for all program points. They will be dened at live range beginnings for Scheme 2.

Assignment

Due to fragmentation, the colorability result, when MaxSize is below the local memory size (for the rst three schemes), is not sucient to guarantee an atomic allocation of array blocks. In practice, it is known that classical fragmentation-avoidance heuristics perform very well, even on rather constrained problems [START_REF] Sumesh Udayakumaran | Dynamic allocation for scratch-pad memory using compile-time decisions[END_REF]. Those heuristics derive from dynamic, heap memory allocation algorithms like the buddy system. This pragmatic approach leads to a very simple, greedy assignment algorithm like Belady's furthest rst method [START_REF] Bouchez | On the complexity of spill everywhere under ssa form[END_REF][START_REF] Belady | A study of replacement algorithms for virtual storage computers[END_REF]. Of course, when implementing Scheme 1, one must be careful to always assign the same oset to a given (local-memory-allocated) live range within a given basic block. Since live range splitting at SSA denition points is sucient to guarantee the colorability, this restriction does not induce spurious spills. If fragmentation-induced spills must be avoided at all costs, we need to dene additional {0, 1} variables to handle the assignment directly. Of course, this breaks the decoupling of the allocation and assignment phases. The immediate, expected impact is a dramatic increase in algorithmic complexity.

We dene a pair of variables for each point p and live range v alive at p:

• o v,p a {1, S} variable, which represents the oset of the variable v in the local memory at p; this variable is valid only if r v,p = 1, that is, if v is not in the local memory, we set this variable to 0.

• m v,p a {0, 1} variable, which represents the displacement of variable v in the local memory at p; this is measured by the osets at point p (o v,p ) and at point p -1 (o v,p-1 ).

To account for the relative placement of live ranges in the local memory, we also need a very large set of variables b v,v ′ ,p in {0, S -1}. Each variable indicates whether v comes before v ′ in the local memory at point p (and how far it does). In addition to these new variables, we introduce additional constraints and a modied objective function which captures both the assignment and allocation costs. First, we modify the previous local memory size constraint with multiple constraints operating on the variable osets. Specically, we change (7.1) into:

o v,p + s v ≤ S + 1 + (1 -r v,p ) × S.
(7.10) This constraint ascertains that at each point, the size of allocated variables does not exceed the size of the local memory. Moreover, we set the oset of any variable, o v,p , to 0 if that variable is not within the local memory. Note that, r v,p will be equal to 0 for such variables forcing o v,p to 0: (7.11) In addition to the upper bound on the oset, we ensure the lower oset bound of a local memory resident variable. If a live range is in local memory, oset will be set to be greater than or equal to 1, otherwise it will be greater than or equal to 0:

o v,p ≤ r v,p × S.
o v,p ≥ r v,p .
(7.12)

As indicated above, we use b v,v ′ ,p to express whether v comes before v ′ in the local memory, through a comparison between the osets of v and v ′ . To characterize this variable, we add the following constraints:

b v,v ′ ,p ≤ r v,p ∧ b v,v ′ ,p ≤ r v ′ ,p (7.13)
These constraints make sure that variable b v,v ′ ,p is only valid for local-memory-allocated live ranges: if the variable is not residing in local memory it will have an oset of 0.

b v,v ′ ,p + b v ′ ,v,p ≤ 1. (7.14)
On the other hand, to force the ordering between live ranges, we set an upper bound of 1 to the above sum. Moreover, if both v and v ′ are in the local memory, then either b v,v ′ ,p or b v ′ ,v,p must be set to 1 to capture the relative position of the two live ranges. This is ensured by an AND operation between r v,p and r v ′ ,p which will set one of b v,v ′ ,p and b v ′ ,v,p to 1 through a ≥ inequality:

b v,v ′ ,p + b v ′ ,v,p ≥ r v,p + r v ′ ,p -1. (7.15)
Next, for all v and v ′ , osets should be assigned such that array blocks are not intersecting.

o v ′ ,p -o v,p ≥ s v × b v,v ′ ,p + (b v,v ′ ,p -1) × S. (7.16)
As mentioned earlier, we capture the array block displacements through the osets. Specifically, we take the dierence of osets at point p (o v,p ) and at point p -1 (o v,p-1 ):

m v,p × S ≥ |o v,p -o v,p-1 | + (r v,p -1) × S + (r v,p-1 -1) × S.
(7.17) Note that, in the above constraint, we force m v,p variable to the oset distance (|o v,po v,p-1 |) only if v is in the local memory at both points p -1 and p. This is enforced through the terms (r v,p -1) × S and (r v,p-1 -1) × S. If variable v is not in the local memory at any of these points, then it will add -S to the right part of the constraint which will set m v,p to 0 since the oset distance cannot be larger than the local memory size S and the objective function is minimized in the optimization.

We modify (7.9) which ascertains that local memory remains in the same state throughout the ow between basic blocks. We now need to keep the osets same in order to preserve the same state. That is, we check the states at every merge/split point via the variable osets. More specically, for such points p and p ′ : ∀v, o v,p = o v,p ′ . (7.18) The objective function also needs to be updated, to include movements between dierent execution points. This is the purpose of the last term in the following objective function: (7.19) where moving_cost(v, p) is the function giving the latency incurred by the displacement of v at point p within the local memory: moving_cost(v, p) = latency_move(s v ) × point_frequency(p).

v,p r v,p × lr v,p + l v,p × ll v,p + u v,p × le v,p + (1 -r v,p ) × lm v,p + v,p m v,p × moving_cost(v, p),

Experimental Results

Experiments on real hardware are out of the scope of this work. This section aims at validating the fundamental hypotheses and the relevance of the decoupled approach for We validate our approach on three array-intensive benchmarks from the UTDSP [START_REF] Lee | UTDSP benchmarks[END_REF] and Perfect Club [ea88] suites, and on matrix multiplication, see Table 7.1. Table 7.2 lists the model parameters. We use Scheme 2 for all experiments, a good tradeo between expressiveness and complexity. Figure 7.1 shows the cost model results for each benchmark. The left bar (dark) refers to the cost achieved by the allocation phase alone, selecting which live ranges will reside in the local memory at which point. The one on the right (light) refers to the cost achieved by the integrated allocation and assignment, a much more complex and inexible optimization taking osets and fragmentation into account. The second bar can only be identical or higher than the rst, since more constraints are taken into account.

We consider dierent local memory sizes: minimal_size corresponds to the the biggest array block in the program; tting_size is the total size of all array blocks; maxsize_size is the maximum of the total size of array blocks simultaneously alive at any given point; the minimal size plus 20% of the maxsize_size; and the minimal size plus 40% of the maxsize_size. We also state minimal_size and tting_size in percentage of maxsize_size.

The size qualier has been omitted from the gure.

These experiments validate the two main insights motivating our approach:

1. For all benchmarks, and all local memory sizes, the decoupled and integrated algorithms compute the same cost. This is a strong conrmation that decoupled local memory allocation behaves as good as decoupled register allocation, despite the fragmentation constraints.

2. For all benchmarks, the cost is optimal same as for tting_size as soon as the local memory size reaches maxsize_size while the cost immediately increases for smaller local memory sizes (maxsize_size-1 ). This conrms that MaxSize is the relevant criterion.

Conclusion

This chapter opens a window on exciting research and applications about local memory allocation. Despite strong progress in the recent years, the state-of-the-art ignores the tremendous advances in decoupled and SSA-based register allocation. We set up a new bridge between the two optimization problems. Our experiments validate the decoupling of the allocation and assignment stages in the context of local memory allocation: after an optimal allocation phase relying on a generic and scalable integer linear program, we demonstrate a total absence of fragmentation-induced spills, during the assignmentphase.

Chapter 8

Decoupled Local Memory Allocation for Linearized Programs

In Chapter 7, we experimentally validated that a decoupled approach could be adopted to solve the local memory allocation problem. We consider here such a decoupled approach, but with a more theoretical point of view. We show that the local memory allocation for linearized programs, where the live ranges of variables or arrays are represented as intervals, is equivalent to a weighted interval-graph coloring problem that we call the submarine-building problem. The submarine-building problem diers slightly from the classical ship-building problem [START_REF] Charles | Algorithmic Graph Theory and Perfect Graphs[END_REF] by allowing a color interval to wrap around. We show that the submarine-building problem is NP-complete, while it is solvable in linear time for weighted proper interval graphs.

Weighted Graph Coloring and Local Memory Allocation

This section sets the terminology and denitions used in the rest of the chapter.

Weighted Graphs

A graph G = (V, E) consists of two sets, V the set of vertices, and E the set of edges. Every edge (v 1 , v 2 ) of E has two end points v 1 ∈ V and v 2 ∈ V . We consider undirected graphs only, i.e., we do not dierentiate between the edges (v 1 , v 2 ) and (v 2 , v 1 ).

A graph G is called an interval graph if its vertices can be put into one-to-one correspondence with a set of intervals I of a linearly ordered set such that two vertices are 84 Chapter 8. Decoupled Local Memory Allocation for Linearized Programs connected by an edge of G if and only if their corresponding intervals have a nonempty intersection.

Assuming each vertex v of G = (V, E) is associated with a non-negative number w(v), the weight of a subset S ⊂ V is expressed as:

w(S) = v∈S w(v).
The graph G associated with the function w is called a weighted graph and denoted G w . Moreover, G w is a weighted interval graph if G is an interval graph.

An interval coloring of a weighted graph G w is a function I mapping each vertex v ∈ V onto a (topologically) open interval I v of w(v) + 1 consecutive integers of the real line, such that adjacent vertices are mapped to disjoint intervals; that is,

(v 1 , v 2 ) ∈ E implies I v 1 I v 2 = ∅.
We say that I is a k-coloring of G w if I v ∈ {0, . . . , k}, ∀v ∈ V . The chromatic number χ(G w ) is the smallest k for which we can nd a k-coloring of G w . Given an intermediate representation of an arbitrary program on which live range splitting has already been applied, the intermediate representation pseudo-instructions can be numbered according to some order. We dene a linearized program as a program for which such kind of numbering [START_REF] Poletto | Linear scan register allocation[END_REF] has been performed and for each variable v in this program, we represent its live range as the live interval [i, j[, i being the number of the rst instruction where v is rst dened and j being the number of the instruction where v is last used. There can be some some pseudo-instructions between i and j where v is not live, but with a successful live range splitting this problem can become marginal. In the context of just-in-time compilation where compilation time is critical, linearizing programs can pay o because it is fast to linearize a program and potentially the produced code could be of relative quality [START_REF] Sarkar | Extended linear scan: An alternate foundation for global register allocation[END_REF].

The linearization attens the program's control-ow graph and the generated live intervals form an interval graph. From a linearized program we construct a corresponding weighted graph called interference graph. For each variable in this program, we create a vertex and associate the size of the variable to this vertex. We create an edge between two vertices if there is a point in the program where the two variables are simultaneously live. Thus, an edge connects a pair of vertices if and only if the variables are simultaneously alive. The constructed weighted graph is a weighted interval graph because each vertex corresponds to an interval dened by the denition point and the end point of the variable.

From Weighted Interval Graphs to Local Memories.

We use a method similar to the one presented by Lee et al. [START_REF] Lee | Aliased register allocation for straight-line programs is NP-compl ete[END_REF] to show that, for any weighted interval graph, we can nd a corresponding linearized program.

Chen [START_REF] Chen | Optimal parallel time bounds for the maximum clique problem on intervals[END_REF] and Saha [START_REF] Saha | Selection of programme slots of television channels for giving advertisement: A graph theoretic approach[END_REF] et al. have shown how to convert an interval graph with q intervals to an isomorphic program like interval graph in O(q log q) time. An interval graph is program-like if the intervals representing the vertices of the graph have start points and end points that are all dierent, and the start points and end points of the intervals form a set {1, . . . , 2q}, where q is the number of intervals.

The Ship-Building Problem

We report here the Ship-Building Problem as presented in the book of Golumbic [START_REF] Charles | Algorithmic Graph Theory and Perfect Graphs[END_REF].

In certain shipyards the sections of a ship are constructed on a dry dock, called the welding plane, according to a rigid time schedule. Each section s requires a certain width w(s) on the dock during construction. Can the sections be assigned space on a welding plane of total width k so that no spot is reserved for two sections at the same time?

Let the sections be represented by the vertices of a graph G and connect two vertices if their corresponding sections have intersecting time intervals. Thus G w is a weighted interval graph. An interval coloring of G w will provide the assignment of the sections to spaces, of appropriate size, on the welding plane. This assignment will be consistent with the intersecting time restrictions. The reader must be careful to distinguish between the time intervals which produced the edges of G w and the color intervals which provide a solution to the assignment of space on the dock.

Weighted Graph Coloring

87

A weighted graph built from a linearized program associated with a number k (corresponding to the size of the local memory) is an instance of the ship-building problem. For a graph G w and a number k, we call ship(G w , k) an instance of the ship-building problem.

Determining whether χ(G w ) ≤ k is an NP-complete problem [START_REF] Charles | Algorithmic Graph Theory and Perfect Graphs[END_REF][START_REF] Lee | Aliased register allocation for straight-line programs is NP-compl ete[END_REF] 11 , even if G is an interval graph and the weight function w is restricted to the values 1 and 2. It follows that the ship-building problem is also NP-complete.

8.2.2

The Submarine-Building Problem

Since the local memory size is generally power-of-two, it is common to mask the addresses (in software or hardware) to let loads and stores wrap around to the local memory transparently. The submarine-building problem is a new variant of the ship-building problem.

Like in the ship-building problem, a vertex must occupy a contiguous color-interval, but a circular allocation scheme can be adopted permitting to a color-interval to wrap around.

It extends the ship-building problem's interval coloring to circular interval coloring. It follows that a solution of the ship-building problem is a solution of the submarine-building problem, but the converse is not generally true. For a weighted graph G w and a number k, we call submarine(G w , k) an instance of the submarine-building problem. For the rest of the chapter we say that G w is k-shipcolorable, if ship(G, k) has a solution, and we also say that G w is k-submarine-colorable, if submarine(G w , k) has a solution.

To the best of our knowledge, this variant of the ship-building problem has never been carefully studied, and it has not been applied to the decoupling of the spilling and assignment problems in local memory management. Many open questions about fragmentation, optimality, complexity and feasibility are tied to this new variant of the ship-building problem.

Unfortunately, the submarine-building problem is also NP-complete on weighted interval graphs as we demonstrate below. Theorem 8.2.1. The submarine-building problem is NP-complete.

Proof.

The submarine-building problem is in NP because we can easily see that a solution of the problem can be veried polynomially. To show that the submarine-building problem is NP-hard, we will build from an instance ship(G, k) of the ship-building problem an instance submarine(G w , k + 1) of the submarine-building problem.

A problem in NP.

The submarine-building problem is in NP because a solution of the problem can be veried polynomially.

Reduction.

From an instance ship(G w , k) of the ship-building problem, we build an instance submarine(G w , k + 1) of the submarine-building problem. Let f and ℓ be respectively the minimum of the startpoints of all intervals in G w and the maximum of the endpoints of all intervals in G w . The graph G ′ w consists of all intervals of G w and the interval β: [f, ℓ[ of weight one.

Let θ be a solution of ship(G w , k); θ maps each interval of G w to a color interval between 0 and k. We dene θ ′ , a function mapping each interval α of G ′ w to a color interval between 0 and k + 1:

∀α ∈ G ′ w θ ′ (α) = θ(α) if α ∈ G w θ ′ (α) = [k, k + 1[ if α / ∈ G w It follows that θ ′ is a solution of submarine(G w , k + 1).
Now, we study the converse case. Let θ ′ be a solution of submarine(G w , k + 1). We

θ(α) = mod (δ(θ ′ (α), k -s))
The interval β of G ′ w is live from f to ℓ, therefore there is no other interval of We study the properties of weighted proper interval graphs, a subclass of weighted interval graphs. This class is interesting because we will show the submarine-building problem is solvable in linear time for this class: any instance G w of this class is colorable with ω(G w ) colors and in linear time. For this subclass, we also have a sucient criterion permitting to decouple the ship-building problem. Proof i ≺ i ′ implies that either i starts before i ′ or i andi ′ starts at the same time:

• i starts before i ′ . Since i cannot properly contain i ′ , then i ends before i ′ .

• i and i ′ start at the same time. Since, none of these two intervals cannot properly contain the other, then they end at the same time. k-submarine-coloring of G w =⇒ ω(G w ) ≤ k.

Any k-submarine-coloring of G w must assign color intervals that do not overlap to the intervals of a clique of weight ω(G w ) and this is only possible if ω(G w ) ≤ k.

Reciprocal. ω(G w ) ≤ k =⇒ k-submarine-coloring of G w .
We will call a point, the moment an interval starts. Let P be the following property: at point n, the live intervals i j , i j+1 , . . . , i n (sorted according to the proper ordering) are assigned to contiguous color intervals that do not overlap in a clockwise manner, in this order: color(i j ), color(i j+1 ), . . . color(i n ). The property P is an invariant at every point of Algorithm 7. If the graph contains m nodes, we have consequently m intervals and m points. The proof will be done inductively on points.

Just before the point 1, where the rst interval i 1 starts, none of the color intervals are used. At point 1, algorithm 7 assigns to i 1 a color interval starting at 0 and property P is trivially satised.

Suppose that property P is satised from point 1 to point n, and let us see if property P is satised at point n + 1 (we assume that we have at least n + 1 intervals in the graph).

We call d the number of dead intervals between n and n + 1 (d can be zero, or nj), we prove four claims successively:

1. i j+d is live. Indeed, if i j+d was dead then all intervals preceding it would also be dead. Therefore, we would have d + 1 intervals that are dead, which contradicts the denition of d.

2. All the intervals between i j+d and i n are live too. If an interval i k between i j+d and i n is dead then i j+d is also dead because i j+d ≺ i k ; this leads to a contradiction with the rst claim. 4. Algorithm 7 assigns to the new interval i n+1 a color interval contiguous to the last used color interval (the color of i n ) in a clockwise manner. Therefore, the color intervals assigned to live intervals are contiguous in a clockwise manner, in this order: color(i j+d ), color(i j+d+1 ), . . . color(i n ), color(i n+1 ). The colors do not overlap because they are all contiguous and they do not exceed ω(G w ) which does not exceed k.

From the fourth claim, we conclude that at the point n+1 the property P is again veried. Hence, using Algorithm 7 guarantees that at every point, all the live intervals are assigned to contiguous color intervals that do not overlap, and the next starting interval will be assigned to a color interval. Thus, a k-submarine-coloring can be found for

G w if ω(G w ) ≤ k.
As far as we are aware, this is the rst time a decision problem is shown to be NPcomplete on interval graphs and polynomial on proper interval graphs.

8.4

Weighted Not-So-Proper Interval Graphs

We say that two intervals A and B properly interfere if A interferes with B such that A strictly starts before B and B strictly ends after A or vice versa. We dene a weighted Not-So-Proper (NSP) interval graph as a weighted interval graph, where each pair of properly interfering intervals A and B, is such that A and B must not be contained in any interval of the graph. The weighted NSP graphs are the class of graphs that includes the weighted proper interval graphs and the superperfect graphs dened by Li et al. [START_REF] Li | Scratchpad memory allocation for data aggregates via interval coloring in superperfect graphs[END_REF]. Thus, when the submarine assignment is allowed the weighted NSP interval graphs are guaranteed to be MaxSize-colorable. MaxSize as a criterion to ensure that the assignment phase is feasible without spills. Thus, the allocation algorithm can be decoupled thanks to MaxSize criterion. For arbitrary weighted interval graphs, the problem is NP-complete and a heuristic-based solution must be envisaged. We devised a solution that takes advantage of our submarine assignment algorithm. This solution, that decouples the allocation and assignment, performs the two following steps:

1. it approximates an arbitrary weighted interval graph into a weighted NSP interval graph through spilling and splitting.

it performs the assignment with Algorithm 8

We have implemented our approach to approximate weighted interval graphs into weighted NSP interval graphs. We have evaluated it on generated weighted interval graphs, but so far the approximation algorithm has shown modest results and does not perform very well. We are trying to improve it and we do not report the results here, since it is still being studied.

Conclusion

In this chapter we designed and analyzed a new variant of the ship-building problem called the submarine-building problem. We showed that this problem is NP-complete on 8.6. Conclusion 95 interval graphs, while it is solvable in linear time for proper interval graphs. We also give a criterion to guarantee the feasibility of the submarine-building problems for proper interval graphs and then we extended it to weighted NSP interval graphs. These results oer a general solution (more general than the solution of Li et al. [START_REF] Li | Scratchpad memory allocation for data aggregates via interval coloring in superperfect graphs[END_REF]) to decouple spill code generation from local memory assignment. Such a decoupling has been missing for a long time, limiting the transfer to local memory management of the recent wave of algorithmic and experimental successes in register allocation. We believe our results will enable the design of simpler and more robust compilation-time algorithms for local memory management. However, while our approach represents an improvement over state of the art methods, it is limited so far in its practical application.

Part III Reconciling Register and Local Memory Allocations

Chapter 9

The Clustering Allocator

In Chapter 8, we intended a theoretical study of the decoupled local memory allocation. This study showed encouraging results that can be theoretical foundations of a decoupled approach for local memory allocation, but it is limited so far in its practical application.

In this chapter, we propose a heuristic-based solution, the clustering allocator, which decouples the local memory allocation problem and aims to minimize the allocation cost. The clustering allocator while devised for local memory allocation appears to be a very good solution to the register allocation problem. After many years of separation, this new algorithm seems to be a bridge to reconcile the local memory allocation and the register allocation problems.

For the sake of exposition, we will rst present the version of the clustering allocator devoted to the register allocation and then we will present the general version for the local memory allocation.

9.1

The Clustering Register Allocator

Here, we present a new decoupled register allocation algorithm called clustering allocator. The algorithm has three steps. It rst packs the variables by clusters. Then, it performs allocation on the clusters, allocating all the variables of clusters or spilling all of them. Finally, it assigns each allocated cluster to a physical register.

Clustering of Variables

We assume here that an estimated spill cost has been computed for each variable. This spill cost represents the access frequency of a variable, it is high when the variable is frequently accessed and low when it is not. We dene a cluster as a group of variables which do not interfere with each other.

The cost of a cluster is dened as being the sum of the spill costs of the variables within it. A cluster corresponds to a stable in an interference graph. The goal when performing register allocation is to optimize the use of registers. Imagine that only one register is available on the target architecture. An allocation of minimum spill cost for a program on this architecture will assign a cluster of maximal cost to the register. Imagine now that there are k available registers on the target architecture. An allocation which assigns the k clusters of highest costs to the k registers will not necessarily be of minimum spill cost, but hopefully it will not be far from the allocation of the minimum cost. This is the intuition upon which the clustering allocator is based and the trick is in the approximation of clusters of higher costs since we are not computing them optimally. We rst approximate the cluster of maximal cost and then the cluster of maximal cost which does not contain any interval of the rst cluster, and so on, until we put all the variables into a clusters. The cluster of maximal cost, computed from a list of variables, has more chances to contain high cost variables than other variables. Thus, to compute the cluster of maximal cost we iteratively add, as a priority, high cost variables which do not interfere with the variables already present in the cluster. The clustering is performed by Algorithm 9 which transforms vars_list, a list of a program's variables ordered by decreasing cost, into clusters_list, a list of clusters. It constructs a new cluster at each iteration of the while-loop. To compute the new cluster, each variable v of vars_list is added to the cluster if it does not interfere with any of the variables already within the cluster. Every time a variable v is added to cluster, 9.2. The Clustering Local Memory Allocator 101 the cluster being created, it is added to removal. When all the variables have been tested, cluster is added to clusters_list and all the variables in removal are removed from vars_list. Then, the next round of while-loop starts. Finally, Algorithm 9 ends when every variable is in a cluster. We assume, like in the specialized version for register allocation, that an estimated spill cost has been computed for each array block. We dene a batch as a set of array blocks such that each array block of the set interferes at least with another array block of the set. We say that an array block A interferes with a batch B, if A interferes at least with one array block of B. We also say that a batch B 1 interferes with another batch B 2 , if an array of B 1 interferes with B 2 or vice versa. A batch has a size which is dened as the sum of the size of the array blocks within the batch. The cost of a batch is dened as the sum of the spill costs of all the array blocks within the batch.

Unlike for register allocation where the variables of same size compete for registers, for local memory allocation, we have many array blocks of dierent sizes that will share the local memory. Thus, the goal is now to maximize the use of the dierent portions of the local memory. Let us assume we have a portion P of the local memory of size S. We want to nd a set of array blocks (cluster) of maximal cost that can be allocated to P . Like for register allocation, we can dene a cluster as a set of array blocks that do not interfere each other. But since, array blocks can have dierent sizes and many of them can be in P at the same time, our solution is to successively assign batches, which do not interfere and are of size smaller than S, to P . Thus, we re-dene a cluster as a set of batches that do not interfere each other. We also dene the size of a cluster as the size of the portion of the local memory where it will be assigned. Now comes the question of how the size of the portions are chosen (the sizes of clusters) and how the clusters are constructed? Algorithm 13 depicts our method. It transforms arrays_list, a list of array blocks ordered by decreasing size, into clusters_list, a list of clusters. Algorithm 13 picks up A, the rst array block (the array block of maximum size) of arrays_list, removes it from arrays_list, and creates cluster, a cluster of the size of A. It creates batch and adds it to cluster. Then, it adds to potentials, all the array blocks that can be potentially added to cluster, which are the array blocks that do not interfere with batch. Afterwards, Algorithm 13 constructs iteratively the other batches to add to cluster (line 16 to 34). It adds the rst array block of potentials to the batch and while the size of the batch does not exceed A.size (the size of A), it adds to the batch the array blocks that interfere with one of the array block already in the batch. Once it becomes impossible to add a new array block to the batch, all the array blocks of the batch are removed from potentials and arrays_list. All the array blocks that interfere with batch are also removed from potentials, because two array blocks of two dierent batch of the same cluster cannot interfere. When potentials becomes empty, cluster is added to the clusters_list and a new cluster is constructed. Finally, all the array blocks will be in a cluster and Algorithm 13 returns the clusters_list. Algorithm 16 performs all the complete steps of the clustering allocator algorithm.

Experimental Evaluation

We report here the evaluation of our clustering allocator algorithm for register and local memory allocations.

Register Allocation

Methodology

These experiments have been performed with the same methodology used for experiments of Chapter 4. We compare our clustering allocator algorithm with the iterated-optimal allocation and the other algorithms presented in Section 4.2. .1 shows the allocation costs normalized over the cost of the optimal allocation's cost, for congurations with dierent register counts going from 2 to 16 registers. For almost all the register counts, the clustering allocator heuristic is close to the optimal and to the iterated-optimal allocation algorithm. For the congurations with 14 and 16 registers, the optimal allocation outperforms both the clustering allocator and the iterated-optimal allocation algorithms. For the conguration with 16 registers the clustering allocator is slightly better than the iterated-optimal allocation algorithm. .2 reports for each individual benchmark the normalized allocation costs when we have a register count of six registers. For check, jess, javac, and jack, we note a degradation up to 60% of the optimal. But for the rest of the benchmarks, the clustering allocator algorithm is always close to the optimal and to the iterated-optimal allocation algorithm.

Results

Normalized Allocation's costs of all benchmarks

Normalized Allocation's costs with 6 registers

We can notice that the clustering allocator algorithm gives good results compared to the iterated-optimal allocation algorithm, although it has a quadratic time complexity. Indeed the function Interfere(v, cluster) can be done in constant time if we represent the live range of a cluster as the union of all the live ranges within the cluster and then perform a simple interference test between the live range of the cluster and the live range of the variable.

The clustering allocator and the iterated-optimal allocation algorithm are also very similar because they both proceed iteratively, but there is a subtle dierence. The iteratedoptimal allocation nds iteratively the set of variables to allocate, while the clustering allocator continues the process until the end before it decides which cluster it is more benecial to allocate and can sometimes achieve better allocation than the iterated-optimal allocation as shown in Figure 9.1 for the conguration with 16 registers.

Local Memory Allocation

To evaluate the clustering allocator algorithm in the context of local memory allocation, we have generated many weighted interval graphs. We are able to generate the graphs, to dierentiate them and we also have control over the density of generated graphs.

Graph Generation

Graphs we have generated for testing our heuristic are based on Scheinerman's studies on random interval graphs [START_REF] Scheinerman | Random interval graphs[END_REF]. To create an interval graph with n intervals we generate 2n independent random variables L 1 , L 2 , ..., L n , R 1 , R 2 , ..., R n and by coupling these random variables we form intervals [L 1 , R 1 ], ..., [L n , R n ]. We associated weights and costs to these intervals. Eventually these intervals form the random interval graph.

In order to represent the data structures in real life applications, we have added some constraints and limits on these graphs. We not only have control on the number of intervals but also on the minimum length of intervals, the maximum number of concurrently live intervals, the weights and the costs of intervals during the graph generation process.

During the graph generation, we also control the density of the generated graph. For a graph G = (V, E) where n V is number of vertices and n E is number of edges in the graph, the density D is calculated with the following formula. We are also capable of dierentiating the interval graphs before generating weights and costs for them. We did this to justify that our heuristic does not only give good results for some specic type of graphs.

Methodology

For the purpose of our experiments, we have generated 500 graphs of density between 0% and 35%, we call these graphs (35% dense). We also generated 500 graphs of density between 36% and 70% called graphs (70% dense). We nally generated 500 graphs of density between 71% and 100%, called graphs (+70% dense).

We compared our clustering allocator with an ILP-based allocator and a best-t allocator, which assigns an array block, represented here by our intervals, to the place in the local memory where it ts best. For each generated graph we use a local memory of size MaxSize. Due to the normalization, we use for these experiments the gain instead of the costs since the ILP-allocator can give for certain graphs a spill cost of zero. We also stop the ILP-allocator, for each graph, after half-an hour, if it does not return a solution. shows that for graphs 70% dense the clustering allocator and the best-t are quite similar and produces better results than the ILP allcoator. For graphs that are denser (+70% dense), as depicted in Figure 9.3(c), the clustering allocator is slightly better than both the ILP allocator and the best-t.

When evaluating the clustering allocator for local memory allocation, we noticed that the ILP-programs were not easy to solve and this shows how the problem is hard. The results we report may appear not very encouraging when comparing to the best-t, but so far we do not know of a better heuristic to perform local memory allocation and we have asked the questions to many experienced researchers. We also think that the version of clustering allocator for local memory allocation has still room for improvements.

Discussions about the Algorithm

This section discusses some practical issues, that are specic to register allocation, when using the clustering allocator algorithm. We also discuss how the clustering allocator can be used to perform allocation while the assignment is performed with another algorithm. When dening the clustering allocator we did not explain how we dealt with the spilled variables. As we previously saw in Chapter 1, when a variable is spilled it does not disappear, it is replaced by a set of tiny variables which must be taken into account. We have two possible solutions for this issue:

1. We can handle them like the linear scan, which assigns them to a free register whenever they are read or written. If there is no available register it spills locally an allocated variable and uses its register. On architecture like x86, we can also take advantage of the complex addressing mode which permits to get operands directly from memory.

2. We can also restart the process like the graph coloring until we nd an allocation which does not spill. For both the local memory and register allocations, the clustering allocator algorithm can be used for only the allocation phase and another algorithm can be used to perform assignment. In a context where there is no guarantee about the fact that the assignment will be performed without further spills, using another assignment algorithm can result in some extra-spilling after the allocation phase.

In the context of decoupled register allocation of SSA programs, where the assignment can be solved polynomially, the clustering allocator algorithm can be used for the allocation phase. After the allocation, we can guarantee that an assignment is possible and the assignment algorithm will nd it. The reason is that the interference graph of a program under (strict) SSA-form is a chordal graph and it will be chordal after an allocation with the clustering allocator. After the allocation, some nodes will be suppressed from the graphs or transformed into a set of tiny live ranges but the resulting graph will still be chordal.

For the same reason, in the context of local memory allocation, when the weighted graphs are superperfect [START_REF] Li | Scratchpad memory allocation for data aggregates via interval coloring in superperfect graphs[END_REF] or proper, the clustering allocator algorithm can be used to perform allocation with the guarantee that the forthcoming assignment will be done without further spills.

Conclusion

In this chapter we have introduced a very interesting heuristic called clustering allocator which appears to work for both register and local memory allocations. For register allocation, the results show that the clustering allocator outperforms the graph coloring and the linear scan and is often close to the optimal. We hope that its simplicity and its low quadratic-complexity will make it a very serious rival to both linear scan and graph coloring approaches.

For local memory allocation, the results obtained so far are not exceptional but we do believe that the clustering allocator can be improved.

Conclusion and Perspectives

This thesis addressed two memory optimizations, namely register allocation and local memory allocation, performed by the compiler, that aim to optimize the use of registers and local memories within a computer.

Register allocation has been shown to be NP-complete. Indeed, Chaitin et al. have shown that the spill-free problem is equivalent to the graph coloring problem [CAC + 81]. Moreover, register allocation is not only bounded to the spill-free problem; if the answer to the spill-free problem is no, the goal of register allocation is also to reduce the impact of the spilled variables on the execution time of the program (spill minimization ).

The local memory allocation problem is NP-complete [START_REF] Verma | Dynamic overlay of scratchpad memory for energy minimization[END_REF]. While there exist many heuristics to deal with the local memory allocation problem, little is known about the optimization problem, its complexity, and its interplay with other optimizations.

Contributions

This dissertation makes the following contributions:

1. Split Register Allocation: we designed a split compilation framework dedicated to register allocation. We experimentally validated the eectiveness of split register allocation and its portability with respect to register count variations, relying on annotations whose impact on the bytecode size is negligible.

2. Iterated-Optimal Allocation: we have introduced a fast register allocator that performs allocations that are close to optimal ones, by iteratively solving optimal sub-problems of the global allocation problem. The iterated-optimal allocation algorithm is pseudo-polynomial (polynomial, when parameters are xed to small values) on SSA programs.

Experimental Validation of a Decoupled

Local Memory Allocation: we validate the decoupling of the allocation and assignment stages in the context of 112 Conclusion and Perspectives local memory allocation; after an optimal allocation phase relying on a generic and scalable integer linear program, we demonstrated a total absence of fragmentationinduced spills during the assignment-phase.

4. Basis of Theoretical Foundations for Decoupled Local Memory Allocation: we designed and analyzed a new variant of the ship-building problem called the submarine-building problem. We showed that this problem is NP-complete on interval graphs, while it is solvable in linear time for proper interval graphs. We also give a criterion to guarantee the feasibility of the submarine-building problems for proper interval graphs and then we extend it to weighted not-so-proper interval graphs.

5. Clustering Allocator: we propose a heuristic-based solution, the clustering allocator, which decouples the local memory allocation problem and aims to minimize the allocation cost. The clustering allocator algorithms packs the variables or array blocks into clusters and performs the allocation on these clusters. The clustering allocator while devised for local memory allocation is a very good solution for the register allocation problem.

Perspectives

We are aware that our work is not exhaustive and could be improved in many ways. Here we point out some extensions that can complement this work.

1. We would like to implement the iterated-optimal allocation and the clustering allocator in the context of a SSA-based register allocator oered in a framework like LLVM. This would help us to validate the interesting results presented in Chapter 4 and Chapter 9. Especially, we would like to apply the clustering allocator algorithm to the aliased register allocation where the size of the dierent variables (8, 16, 32, or 64 bytes) will vary in a limited manner.

2. We have shown that MaxSize can be used as a colorability criterion. We want to extend this colorability criterion to a more general class of graphs or to nd a good solution to approximate weighted interval graphs into weighted NSP graphs, while achieving good results. In case of a good approximation algorithm, we plan a complete automation of it and of the clustering allocator algorithm in a research compiler, relying on integrated polyhedral compilation techniques for data-ow analysis, loop transformation and code generation.

2. Perspectives 113 3. In our approach to local memory allocation, we only considered single-threaded code running on a single local memory, we would like to extend this work to environments with many threads sharing the same local memory. We are particularly interested in deterministic thread-level parallelism and synchronous languages where the interactions between live ranges in concurrent threads is well behaved 4. GPU architectures are evolving towards shared memories that are increasingly bigger (AMD Fusion, ARM MALI, Intel Larrabee). Programming these architectures more eciently requires more attention to memory locality. In such a context, we are interested in new architectures with a (possibly partitioned) global address space and programming models (as HMPP 12 and OpenCL), that furnish more support for software-controlled local memories, and thus help the developer or the compiler manage these software-controlled local memories in a more transparent way. We would like to consider these new models in our future work.

List of Figures

Figure 1 :

 1 Figure 1: La hierarchie mémoire

  en ecience énergétique, en rapidité d'accès aux données et du faible espace occupé sur la puce [BSL + 02]. La predictibilité et une bonne consommation d'energie sont souvent es- sentielles aux applications temps réél et embarqués. D'autres processeurs plus spécialisés, tels que les stream-processors et les processeurs graphiques, utilisent aussi les mémoires locales [NVI08, BPMR03]. Pour bien exploiter tout le potentiel des mémoires locales, il est essentiel de les utiliser de manière eciente. Dans les compilateurs, cette tâche est à la charge d'une optimisation appelée allocation de mémoire locale. L'allocateur de mémoire locale selectionne l'ensemble des variables qui seront stockées dans la mémoire locale à chaque point du programme. Il choisit aussi pour chaque variable l'emplacement spécique qu'il va occuper, xvi soit en mémoire locale, soit en mémoire principale. L'allocation de mémoire locale est un problème NP-complet [VWM04]. Les travaux précédants ont porté sur diérents angles, ciblant aussi bien une allocation du code et des données du programme. Plusieurs heuristiques ont été proposées à la résolution du problème d'allocation de mémoire locale. [MFA01, VWM04, UDB06, LFX09, LXK11].

  l'allocation des tableaux en programmation linéaire pour résoudre le problème optimalement (en minimisant le coût des latences d'accès) en utilisant MaxSize comme critère. MaxSize est la taille maximale occupé par les tableaux en vie au même moment. Une fois le problème d'allocation résolu, la phase d'assignation se charge d'assigner aux tableaux alloués des emplacements dans la mémoire locale. Cependant, due à la possible fragmentation que la phase d'assignation peut entrainer, une solution du probléme d'allocation ne garantie pas forcément une solution au problème d'assignation. Néanmoins, nous avons expérimentalement montré, sur une série de benchmarks, que dés lors que le problème d'allocation admettait une solution alors le problème d'assignation aussi en admettait une sans spills supplémentaires.

4 .

 4 Nous exhibons pour la première fois un problème NP-complet pour les graphes d'intervalle et polynomial pour les graphes d'intervalle propre (qui sont équivalents aux graphes d'intervalle unitaire). Les évaluations eectuées ont montré que l'approximation des graphes d'intervalle par des graphes d'intervalle propre ne fournit pas de très bons résultats. Ces résultats décevants nous ont poussé à la conception d'une nouvelle méthode heuristique de résolution du problème de la gestion des mémoire locale. 3 Allocation par Clustering Notre étude théorique d'une approche découplée de l'allocation de mémoire locale a aboutit à des résultats encourageants. Cependant cette approche n'est pas encore assez mature pour qu'on puisse l'utiliser dans la pratique. De ce fait nous avons considéré une méthode heuristique que nous avons appelée, clustering allocator. Cette approche, bien qu'elle ait été conçue pour l'allocation de mémoire locale, fournit de trés bons résultats en allocation de registres. Donc après plusieurs année de séparation, le clustering allocator semble rétablir un pont entre les problèmes d'allocations de mémoire locale et de registres. Le clustering allocator decouple les problème d'allocation et d'assignation et cherche à minimiser le coût de l'allocation par la construction de sous-graphes stables d'un graphe d'interférence. Durant la phase d'allocation, notre algorithme regroupe les variables par clusters qui seront alloués, ou spillés globalement. Pour les problèmes d'allocation de registres, le clustering allocator fournit des résultats presques optimaux et est beaucoup plus performant que les autres heuristiques xviii Introduction Programs running on computers are often written in high-level programming languages

  Figure 1.1: An example of register allocation

Figure 1 . 2 :

 12 Figure 1.2: The control-ow graph of an example program.

Figure 1 .

 1 Figure 1.2(b) shows the control-ow graph of the portion of code given in Figure 1.2(a).

Figure 1 . 3 :

 13 Figure 1.3: The variables's live ranges in Figure 1.2(a).

Figure 1 . 8 :

 18 Figure 1.8: Live intervals of the variables in Figure 1.2(a).

Figure 1 . 9 :

 19 Figure 1.9: Live intervals with holes of the variables in Figure 1.2(a).

Figure 2 . 1 :Figure 2 Figure 2 . 3 :

 21223 Figure 2.1: Compilation process, from the Dragon book [ALSU06]

Figure 3

 3 Figure 3.1: Counter example to spill set inclusion

4 :

 4 count ← R min 5: while var_list = ⊥ ∧ (count + step) ≤ R do 6: result ← OptimalAllocation(var_list, step)

Figure 4 .

 4 Figure 4.1: Iterated-optimal compared to other allocators for dierent register counts Normalized Allocation's costs with 6 registers

  decisions. It also improves the understanding of the interplay between live-range splitting and the expressiveness and complexity of register allocation. This is best illustrated by the success of SSA-based allocation[START_REF] Bouchez | Register allocation: What does the NP-completeness proof of Chaitin et al. really prove?[END_REF][START_REF] Hack | Register allocation for programs in SSA-form[END_REF][START_REF] Bouchez | On the complexity of spill everywhere under ssa form[END_REF][START_REF] Bouchez | On the complexity of register coalescing[END_REF].The intuition for decoupled register allocation derives from the observation that liverange splitting is almost always protable if it allows to reduce the number of register spills, even at the cost of extra register moves. The decoupled approach focuses on spill minimization only, pushing the minimization of register moves to a latter register coalescing phase [AG01, BDR08]. Here again, SSA-based techniques have won the game, collapsing the register coalescing with the hard problem of getting out of SSA [HGG06, BDdD + 09], as one of the last backend compiler passes. The domain of local memory allocation tells a very dierent story. Some heuristics exist [UDB06, KRI + 01, LFX09] but little is known about the optimization problem, its complexity and the interplay with other optimizations. The burning hot question is of course: does the decoupled approach hold for the local memory allocation problem? Surprisingly, the state-of-the-art of local memory allocation completely ignores all the advances in register allocation. When focusing on arrays, the similarity between register and local memory allocation is obvious nonetheless: Local memory allocation. Deciding which array blocks to spill to main memory and which array blocks to allocate to the local memory. Spilling is typically supported by DMA units. Local memory assignment. Deciding at which local memory oset to assign which allocated array block. When reconciling the osets across control-ow regions or over multiple incoming paths, there is no unique equivalent of register moves:

Figure 7 . 1 :

 71 Figure 7.1: Experimental results for decoupled and integrated approaches.

Figure 8 .

 8 Figure 8.1 shows two colorings of a weighted graph shown in Figure 8.1(a). The rst coloring given in 8.1(b) is a 6-coloring of the weighted graph and the second coloring shown in 8.1(c) shows a 5-coloring of the weighted graph. The chromatic number of this graph is 5.

  From a program-like weighted interval graph G w , we construct in O(q) time the following straight-line program (with pseudo-C syntax) which consists of a set of 2q statements: ∀i ∈ {1, . . . , 2q}     type I v I = • • •where sizeof(type I ) = w(I), if the interval I of weight w(I) begins at i• • • = v I ifthe interval I ends at i 8.2 Weighted Graph Coloring Thirty years ago, in her seminal paper [Fab79], Fabri already envisaged to model the so-called problem of automatic storage allocation as a weighted graph coloring problem. She mentions the investigation of special subclasses of weighted graphs that are likely to occur. We construct a weighted graph G w from a given linearized program. Finding an allocation for variables of the linearized program within a local memory of size k corresponds to nding a k-coloring of G w . This section introduces the ship-building problem which is related to weighted interval graph coloring. It also denes a new variant, called the submarine-building problem, very well suited to the local memory allocation problems on modern processors, and exhibiting interesting complexity results and potentially good approximation heuristics.

Figure 8 .Figure 8 . 2 :

 882 Figure 8.2: An example of a 4-submarine-coloring

8. 3 .

 3 Weighted Proper Interval Graph Coloring 89 dene for a color interval [s, e[, an integer k, and the functions δ and mod: δ([s, e[, d) = [s + d, e + d[ mod([s, e[) = [s mod (k + 1), e mod (k + 1)[Let θ ′ (β) = [s, s + 1[ (βis of weight one). We dene for each interval α of G w the function θ:

Figure 8 . 4 :

 84 Figure 8.4: An example of weighted NSP graph

8. 4 . 143 Figure 8 . 5 :

 414385 Figure 8.5: Two graphs that are not weighted NSP graphs

100 Chapter 9 .

 9 The Clustering Allocator

Algorithm 9

 9 Cluster_Variables Input: vars_list: a list of variables ordered by decreasing spill cost Var: clusters_list: a list of clusters 1: while vars_list = ∅ do 2: cluster ← ⊥

  Algorithm 14 performs the allocation. It receives as input clusters_list, a list of clusters, and LM Size, the size of the local memory. It then returns allocated_clusters, the list of allocated clusters. It sorts the list of clusters and adds the clusters to allocated_clusters while their size does not exceed LM Size. When (cluster.size + size) ≥ LM Size, the function DecreaseToGoal(cluster, goal) tries to compute a new cluster of size goal from the array blocks of cluster.

  Input: allocated_clusters: the list of allocated clusters Var: LM Size: the size of the local memory Var: map: an array that maps each array to an oset in the local memory 1: of f set ← 0 2: foreach: cluster ∈ allocated_clusters do 3: foreach: batch ∈ cluster.batchs do 4: current_of f set ← of f set 5: foreach: array ∈ batch do 6: map[array] ← current_of f set 7: current_of f set ← current_of f set + array.size of f set ← of f set + cluster.size 11: end for 12: return map Algorithm 15 assigns to each array block an oset in the local memory. Algorithm 16 Clustering_LM_Allocator Input: vars_list: a list of array blocks ordered by decreasing size Input: LMSize: the size of the local memory Var: map: an array that map each cluster to a register 1: clusters_list ← Cluster_arrays(clusters_list) 2: allocated_clusters ← Allocate_Arrays(clusters_list, LM Size) 3: map ← Assign_Arrays(allocated_clusters, LM Size) 4: return map

Figure 9 .

 9 Figure 9.1: clustering allocator compared to other allocators for dierent register counts

Figure 9 .Figure 9

 99 Figure 9.2: clustering allocator compared to other allocators when the register count is 6

Figure 9 . 3 :

 93 Figure 9.3: clustering allocator for local memory allocation

Figure 9 .

 9 3(a) shows the normalized allocation gain for graphs 35% dense. It does not show a strong improvement for our clustering allocator algorithm which is outperformed 9.4. Discussions about the Algorithm 109 by the best-t allocator which is in turn outperformed by the ILP allocator.

Figure 9 .

 9 3(b)

9. 4

 4 .1 Practicability in the context of Register Allocation

9. 4

 4 .2 Using the Clustering Allocator for Allocation only

1

  La hierarchie mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii 1 A typical memory hierarchy conguration, from the Dragon book [ALSU06] xxii 1.1 An example of register allocation . . . . . . . . . . . . . . . . . . . . . . . 1.2 The control-ow graph of an example program. . . . . . . . . . . . . . . . 1.3 The variables's live ranges in Figure 1.2(a). . . . . . . . . . . . . . . . . . . 1.4 The program in 1.2(a) in SSA form. . . . . . . . . . . . . . . . . . . . . . . 1.5 An example of aliasing registers's names . . . . . . . . . . . . . . . . . . . 1.6 The Chaitin et al.'s Allocator . . . . . . . . . . . . . . . . . . . . . . . . . 1.7 Iterated Register Coalescing . . . . . . . . . . . . . . . . . . . . . . . . . . 1.8 Live intervals of the variables in Figure 1.2(a). . . . . . . . . . . . . . . . . 1.9 Live intervals with holes of the variables in Figure 1.2(a). . . . . . . . . . . 2.1 Compilation process, from the Dragon book [ALSU06] . . . . . . . . . . . 2.2 Execution of a target program, from the Dragon book [ALSU06] . . . . . . 2.3 Interpretation, from the Dragon book [ALSU06] . . . . . . . . . . . . . . . 3.1 Counter example to spill set inclusion . . . . . . . . . . . . . . . . . . . . . 4.1 Iterated-optimal compared to other allocators for dierent register counts . 4.2 Iterative-optimal compared to other allocators when the register count is 6 6.1 Example: Edge-Detect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Homogeneous blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Abstract model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.1 Experimental results for decoupled and integrated approaches. . . . . . . . 8.1 Two colorings of a weighted graph . . . . . . . . . . . . . . . . . . . . . . . 8.2 An example of a 4-submarine-coloring . . . . . . . . . . . . . . . . . . . . .

  al. ont montré que le problème de l'existence d'une allocation sans spills (sill-free ) est équivalent au problème de la coloration de graphe [CAC + 81]. En plus, le problème de l'allocation de registres ne se limite pas uniquement au problème du spill-free; si la réponse au problème du spill-free est non, alors le but de l'allocation de registres est aussi de réduire l'impact

des variables spillées sur le temps d'exécution du programme. Ce problème est connu sous le nom de, minimisation des coûts de spills ou minimisation de spills. Plusieurs heuristiques et techniques d'approximation au problème d'allocation de registres ont été proposé dans la litterature [CAC + 81, BCT94, PS99, THS98, HGG06, PP08].

  Chaitin et al. have shown that the spill-free problem is equivalent to the graph coloring problem [CAC + 81]. Moreover, register allocation is not bound to the spill-free problem; if the answer to the spillfree problem is no, the goal of register allocation is also to reduce the impact of the spilled variables on the execution time of the program (spill cost minimization ). Many heuristics and approximation techniques have been proposed to solve register allocation [CAC + 81, BCT94, PS99, THS98, HGG06, PP08].

  BB 1 , BB 2 , BB 3 and BB 4 . Control-ow graph. A control-ow graph is an intermediate representation describing all the possible sequencing of instructions that may occur during the execution of the program. It is a directed graph where each node is a basic block. There is an edge from the basic block B to the basic block C, if the rst instruction of C can follow immediately the last instruction of B. B is called a predecessor of C and C is called a successor of B. A control-ow graph must have a unique entry point and a unique exit point. That is why often an entry block and an exit block are added to the control-ow graph.

		11 2
		12 3425464746 12 3425464746
		82 9425464A46 82 9425464A46
	1234252625	B2 6425434C46 B2 6425434C46 D2 EF46441 D2 EF46441
	7234252825
	5234212925
	AB2C52D2EF
	23425282 234272625	11 3	11 4
	234222	2 425464A4 2 425464A4	42 F42546 42 F42546
		2 425494746 2 425494746	42 4254F474F 42 4254F474F
	B23425	2 42544C4 2 42544C4	12 42544C4F 12 42544C4F
	2342B262B
	234222B
	234228E
			11 5
		112 42544A41 112 42544A41

  and that is also dominated by any other basic block d that dominates n. A basic block cannot be its own immediate dominator. The graph containing every node of the controlow graph, and for every node n and edge from idom(n) to n is called the dominator tree. It is a tree because each node has exactly one immediate dominator.

	Liveness.

Dominators.

A node d of a control-ow graph dominates a node n if every path of directed edges from s 0 , the entry point, to n must go through d

[START_REF] Appel | Modern Compiler Implementation in Java[END_REF]

. Every node dominates itself. An immediate dominator idom(n) of n is a basic block that dominates n

11 2 11 3 11 4 11 5

  φ-function is inserted at the beginning of the basic block BB 4 . The variable d 2 and d 3 used as the operands of the φ-function indicate which denitions of d reach the join node. Subsequent uses of the variable d are replaced with uses of the variable d 4 . The φ-functions do not correspond to hardware instructions and after the optimizations have been done upon it, a program in SSA form must be translated into an executable representation without φ-functions.

	Chapter 1. Register Allocation minimizes the number of registers required by a program. Static Single-Assignment (SSA) Form. The SSA form is an intermediate represen-tation in which each variable has only one denition in the program text [AP02, CFR + 91, RWZ88]. The SSA form facilitates many other optimizations like constant propagation, dead code elimination, and register allocation, as we will see later. In straight line code (e.g. in a basic block), which is a code without control-ow, each denition of a variable v is given a new name such as (v 1 , v 2 , . . .), and each use of a variable v is renamed to the most recently dened version of the variable. In programs with control-ows, With two control-ow paths merging together, a special form of variable's denition called φ-function, is inserted. 12 3 1 42546 7 4846 7 92 A 1 42546 7 4B46 7 C2 6 1 42543 1 4D46 7 E2 F46 1 4417 12 3 1 42546 7 4846 7 92 A 1 42546 7 4B46 7 C2 6 1 42543 1 4D46 7 E2 F46 1 4417 2 1 42546 1 4B4 2 1 4254A 1 4846 1 2 9 4254 1 4D4 1 2 1 42546 1 4B4 2 1 4254A 1 4846 1 2 9 4254 1 4D4 1 42 1 42546 1 42 9 4254 1 484 1 172 C 4254 9 4D4 1 42 1 42546 1 42 9 4254 1 484 1 172 C 4254 9 4D4 1 112 E 42541 9 B C 192 4254 E 4B41 112 E 42541 9 B C 192 4254 E 4B41 Figure 1.4: The program in 1.2(a) in SSA form. In Figure 1.4, a 1.3. Aspects of the Optimization Problem 1.3 Aspects of the Optimization Problem	11

  It is mapped to a color dierent from all its current neighbors, though it can have some other neighbors not yet re-inserted into the graph. The allocator proposed by Chaitin et al. handles both spill code insertion and coalescing. The principal phases of this allocator are: Renumber performs live ranges splitting. Each variable v is renamed every time it is dened. It creates a new sub-variable v i for each denition of v. At each use point of v, it merges together the v i of v that reach the use. At the end of this process, each variable v is represented by a set of sub-variables called names. Build constructs the interference graph where each node represents a name.

  is said to be the live range of the variable v, if there is no instruction with number i ′ < i, such that v is live at that instruction, and there is no instruction with number j ′ > j such that v is live at that instruction. There may exist some sub-ranges of [i, j] where v is not live, this inaccuracy in the live ranges approximation is ignored for the sake of fast computation. Live interval information can be computed with one pass through the intermediate representation from live variable information. Figure1.8 shows the live intervals of variables in the example program in Figure1.2(a).

	11 2	1	2	3	4	6	5
	.7, taken from Modern compiler implementation in Java [AP02] shows the ow chart of the allocator proposed by George and Appel. 12345267 12345267 8925A 8925A BCD5E1BE BCD5E1BE 4CFEF2D5 14255 4CFEF2D5 14255 6EEE 6EEE 1E5EBF 1E5EBF DBF9D5 14255 DBF9D5 14255 1 1 Rebuild the graph if there were any actual spills Figure 1.7: Iterated Register Coalescing 1.5 Linear Scan The linear scan has been introduced by Poletto and Sarkar as an alternative to the graph coloring approach for fast global register allocation [PS99]. It is suitable for applications where compile time is a concern, such as just-in-time compilers or dynamic compilation systems. The linear scan is based on the notion of live interval which is a conservative ap-proximation of a variable's live range. Given some numbering of a code's intermediate 82 9425464A46 B2 6425434C46 D2 EF46441 12 3425464746 82 9425464A46 B2 6425434C46 D2 EF46441 42 F42546 42 4254F474F 12 42544C4F 42 F42546 42 4254F474F 12 42544C4F 112 42544A41 112 42544A41 11 3 11 4 2 425464A4 2 425494746 2 425464A4 2 425494746 representation, [i, j] 12 3425464746 2 42544C4 2 42544C4

The interferences among variables are captured with their live intervals. Two variables interfere if their corresponding live intervals overlap. The linear scan assigns as many live intervals (variables) as possible to a register so that two overlapping live intervals are

  2005, three teams, namely Bouchez et al., Brisk et al., and Hack et al., independantly discovered that the interference graph of a program in SSA form is chordal. We will report here how Hack et al. show this property of interference graphs of programs in SSA form.

  : list: the list of basic intervals ordered by increasing start point Input: optimalSpills: the set of live ranges to be spilled as decided by the optimal allocator

	Algorithm 4 compressAnnotation
	1: annotation ← ∅
	2: foreach: i ∈ list do 3: toSpill ← assignOrSuggestSpillCandidate(V (i)) 4: if toSpill = ⊥ then
	5: 6:	if toSpill / ∈ optimalSpills then toSpill ← findActiveLiveRange(optimalSpills)
	7:	annotation ← annotation ∪ toSpill
	8:	end if
	9:	if toSpill = V (i) then
	10:	Assign V (i) to the register freed by toSpill
	11:	end if
	12:	Spill live range toSpill
	13:

Input

  [CAC + 81]. It is not NP-complete with sucient Algorithm 5 onlineAllocation Input: list: the list of basic intervals sorted in increasing start point Input: annotation: a set of annotated live ranges 1: foreach: i ∈ list do

	2:	if V (i) is not spilled then
	3:	if V (i) ∈ annotation then
	4:	Spill V (i)
	5: 6: 7:	else assignOrSuggestSpillCandidate(V (i) end if
	8:

Table 3

 3

	.1: Annotation compression

Table 3 .

 3 3: Wall-clock speedups of split register allocation Table3.1 illustrates the eectiveness of the annotation compression scheme: it shows the total number of live ranges (Live ranges); the eective number of live ranges within the annotations (Annotations); the Annotations/Live ranges ratio (Compression, in percentage); the number of live ranges within the optimal spill sets (Optimal spill set); the Annotations/Optimal Spill set ratio (Remaining spills, in percentage); and the size over-

head w.r.t. the bytecode itself (Bytecode, in percentage, counting 4 bytes per annotation).

Normalized Allocation's costs of all benchmarks

	Normalized Allocation's cost	0.0 0.5 1.0 1.5 2.0 2.5
		2 registers	4 registers	6 registers	8 registers	10 registers	12 registers	14 registers	16 registers
					Number of available registers
			Default linear scan Belady linear scan	Mixed heuristic	GC Iterated Optimal Optimal

  ,[START_REF] Hallnor | A fully associative software-managed cache design[END_REF]. Moritz et al., manage the local memory as a cache. They substitute the tagmemory and the cache controller, present on architectures with caches, with a compiler managed tag-like data structure, address translation and tag checks. As a result, this incurs software overhead which is, in some cases, optimized by the compiler. They showed that even without any hardware support, their approach outperforms hardware caches by improving caching eectiveness. The approach of Moritz et al., like other software-caching techniques [BCZ90, Iye99, CR95], incurs signicant overheads in runtime, code and data size, energy consumption, and has unpredictable execution times[START_REF] Sumesh Udayakumaran | Dynamic allocation for scratch-pad memory using compile-time decisions[END_REF]. These drawbacks led to other dynamic methods which do not emulate the functioning of caches.Verma et al. proposed an ILP-based approach to solve the dynamic local memory allocation problem

  array at the points where it is going to be frequently accessed (if its usage justies memory transfers). Of course, the cost of (un)loading whole array blocks to the local memory is too high to authorize live-range splitting at every instruction (a.k.a. load/store optimization[START_REF] Appel | Optimal spilling for CISC machines with few registers[END_REF][START_REF] Magno | Register allocation by puzzle solving[END_REF]). More advanced strategies would integrate loop transformations such as loop distribution and strip-mining[START_REF] Joseph | High Performance Compilers for Parallel Computing[END_REF].

	for (i=0; i<N; i++)
	// Outer strip-mined loop
	for (jj=0; jj<N+B-1; jj+=s)	for (i=0; i<N; i++)
	// Inner strip-mined loop	// Outer strip-mined loop
	for (j=jj; j<N && j<jj+s; j++)	for (jj=0; jj<N+B-1; jj+=s)
	C[i][j] = /* ... */;	STORE(C[i][jj..min(jj+B-1,N-1)]);
	F[0][0]=1; /* ... */ F[2][2]=1;	STORE(F[0..2][0..2]);
	Figure 6.2: Homogeneous blocks	Figure 6.3: Abstract model
	decisions for each 6.2 Our Approach to the Problem

  6.2. Our Approach to the Problem 69Non-uniform accesses may also be exploited through the use of symbolic expressions, approximations or pre-pass loop and data-layout transformations[START_REF] Mahmut | Array unication: A locality optimization technique[END_REF][START_REF] De | Array regrouping and its use in compiling data-intensive embedded applications[END_REF][START_REF] Kodukula | Data-centric multi-level blocking[END_REF].Those techniques are complementary to our work, and we consider loop nests that have been previously tiled for locality, together with data layout compaction and uniformization. As a rule of thumb, those transformations should favor the emergence of homogeneous array blocks. Here, homogeneous means that for a given array A, the loop transformations must strive to strip-mine the computation such that inner loops traverse a xed-size block of A in a dense manner. Most numerical and signal-processing codes exhibit a vast majority of dense, uniform sum of loop iterator plus a constant access patterns. In such cases, homogenization is trivial: it is sucient to set a constant stripmining factor for all loops operating over a given array A[START_REF] Sumesh Udayakumaran | Dynamic allocation for scratch-pad memory using compile-time decisions[END_REF]. The last step is to abstract the transformed code, isolating array block operations into atomic regions. Considering the motivating example, these two steps are illustrated on Figures 6.2 and 6.3; s is the homogeneous block size for array C.

This abstraction is sucient to collect prole information on the homogenized version of the loop nest, to solve the allocation and assignment problems. When generating the code for a real target, one needs to insert back the array block load, store, and pointer moves. Again, standard techniques exist to handle this, at least when array accesses are uniform [UDB06, KRI

+ 01].

Table 7

 7

	.2: Model parameters.

  G ′ w that occupies the color interval [s, s + 1[. θ([s, s + 1[) = [k, k + 1[, and the value on which function θ is equal to [k, k + 1[ is [s, s + 1[.Thus, θ assigns to each interval α of G w an interval of some color between 0 and k. If two interfering intervals α and α ′ have two non-overlapping color intervals c and c ′ then θ(α) and θ(α ′ ) are non-overlapping too. It follows that θ is a solution of ship(G w , k) if θ ′ is a solution of the submarine(G w , k + 1).

	8.3	Weighted Proper Interval Graph Coloring

  An interval graph G is a proper interval graph if it is constructed from a family of intervals such that no interval properly contains another[START_REF] Charles | Algorithmic Graph Theory and Perfect Graphs[END_REF]. An interval graph is a unit interval graph if all of its intervals have the same length. It has been shown that the classes of proper interval graphs and the unit interval graphs coincide. A weighted graph G w is a weighted proper interval graph if G is a proper interval graph. Figure8.3 shows properly ordered weighted-intervals of the real line and their corresponding weighted proper interval graph.Let us consider the representation of G w , a weighted proper interval graph, on the real line, where the vertices of G w correspond to intervals on the real line. Let us sort these An example of a weighted proper interval graph intervals according to their start points. If two intervals i and i ′ start at the same point, we can place either i before i ′ or i ′ before i. This kind of ordering can be found for any weighted proper interval graph, and is called proper ordering in our approach. A proper ordering of the graph in Figure8.3 is: A, B, c, d, E, F. Based on this ordering, we say that i ≺ i ′ , if i is before i ′ . Lemma 8.3.1. If i ≺ i ′ then, either i ends before i ′ or i and i ′ start and nish at the same time.

		6CD		1C7		7	8	7
				3C8		1	2	5
					2C8
					4C7
					5C7
					7	6	3	4
	E	8	7	F	D		8	7
				9B		9AB
				Figure 8.3:
		8.3.1	Proper Interval Graph
		8.3.2	Proper Ordering

  7 performs a k-submarine-coloring of intervals of a weighted proper interval graph G w . It takes as input a sequence of intervals of G w sorted according to a proper ordering. It assigns to each interval a color interval contiguous to the color interval assigned to the previous interval (according to the proper ordering) in a clockwise manner. Finally, it gives a k-submarine-coloring of the graph as output. Theorem 8.3.1. For any weighted proper interval graph G w , Algorithm 7 guarantees a k-submarine-coloring if and only if ω(G w ) ≤ k.

	8.3. Weighted Proper Interval Graph Coloring	91
	Algorithm 7 Submarine_Assignment_Algorithm
	Input: intervals: a list of properly ordered intervals
	Var: map: an array associating to each interval an oset
	1: of f set ← 0
	2: foreach: i ∈ intervals do
	3: 4:	map[i]← index mod k of f set = of f set + WeightOf(i)
	5: end for
	6: return map
	Direct.
	8.3.3	Decoupled Submarine-Building Problem
	Proof.

Algorithm

  3. From the two rst claims and the satisfaction of proposition P at point n, we deduce that all live intervals i j+d , i j+d+1 , . . . , i n are assigned to contiguous colors that do not 92 Chapter 8. Decoupled Local Memory Allocation for Linearized Programs overlap, in a clockwise manner, in this order: color(i j+d ), color(i j+d+1 ), . . . color(i n ).

  Algorithm 8 NSP_Assignment_Algorithm Input: intervals: a list of intervals sorted by increasing start point Var: map: an array associating to each interval an oset Var: stack: a stack used to keep track of contained intervals It receives as input intervals, a list of intervals sorted by increasing start point, and returns at the end map, a map that associates to each interval an oset into the local memory. Algorithm 8 makes dierence between intervals that are not contained in any other interval, called containers and those contained in an interval. The contained intervals are stocked into stack, a stack which keeps track of them. The variable container keeps track of the last starting container. When a new interval, i, starts, it is veried for containment. If it is not contained in the currently live intervals, it is set as the new container. The function Contains(container, i) returns true, if i is contained in container and false otherwise. Then all the dead intervals are removed from stack and the oset is updated. The function WeightOf(i) returns the weight of the interval i. If i is contained into another interval, it is pushed on stack. Finally, i is assigned to the current oset, which is then updated.As explained in Section 8.2, from a linearized program it is possible to construct a corresponding weighted interval graph. If the resulting graph is a weighted proper or NSP interval graph, when the submarine assignment is allowed, it is always possible to use

	1: of f set ← 0 2: container ← ⊥ 3: foreach: i ∈ intervals do 4: if container = ⊥ ∨ ¬(Contains(container, i)) then 5: container ← i 6: end if 7: while stack = ∅ do 8: if ¬(Contains(Peek(stack), i) then 9: contained ← Pop(stack) 10: of f set ← (of f set + MaxSize -WeightOf(contained)) mod MaxSize 11: else 12: break out of the loop 13: end if 14: end while 15: if container = i ∧ (Contains(container, i)) then 16: Push(stack, i) 17: end if 18: map[i]← index mod k 19: index = index + WeightOf(i) 20: end for 21: return map Algorithm 8 performs a submarine assignment for a weighted NSP graph on a local memory of size MaxSize. 8.5 Extension to Weighted Interval Graphs

  After the clusters have been computed, Algorithm 10 selects the set of allocated clusters. The k clusters that maximize the sum of their costs are allocated, k being the number of available registers.Algorithm 11 performs assignment by mapping each cluster to a physical register.Algorithm 12 performs all the complete steps of the clustering allocator algorithm.

	Algorithm 12 Clustering_Register_Allocator
	Input: vars_list: a list of variables ordered by decreasing spill cost
	Input: registers: the array of k available registers
	9.1.2 Var: map: an array that map each cluster to a register Allocation and Assignment 1: clusters_list ← Cluster_Variables(vars_list) 2: allocated_clusters ← Allocate_Variables(clusters_list, k) 3: map ← Assign_Variables(allocated_clusters, registers) 4: return map
	9.2.1	Clustering of Array Blocks
	Algorithm 10 Allocate_Variables
	Input: clusters_list: a list of clusters
	Input: k: the number of available registers
	1: sort clusters_list by decreasing cost
	2: if size > k then
	3:		remove the last (size -k) clusters from clusters_list
	4: end if
	5: return clusters_list
	Algorithm 11 Assign_Variables Input: clusters_list: a list of k clusters Input: registers: the array of k available registers Var: map: an array that maps each cluster to a register
	1: i ← 0
	2: foreach: c ∈ clusters_list do
	3:		map[c] ← registers[i]
	4:		i ← i + 1
	5: end for
	6: return map
	9.2	The Clustering Local Memory Allocator
	We present here the generalization of the clustering allocator algorithm for local memory
	allocation. The main changes between this generalization and the register allocation
	version are in the computation of clusters which is changed to take into account the
	dierent sizes of array blocks.

1.2. Terminology

1.5. Linear Scan

An instruction i dominates another instruction j if all paths, in the control-ow graph, form the entry point to j contains i.

Chapter 2. Split Compilation

http://www.ecma-international.org/publications/standards/Ecma-335.htm

3.2. Split Register Allocation

Low-level Intermediate Representation of JikesRVM, which does not include yet all the characteristics of the target architecture.

Such annotations remain usable when varying the register count (or the calling convention) for a given ISA.

Chapter 3. Split Register Allocation

A denition of CFG can be found in Chapter 1.5.3. Dynamic Allocation Methods

Not the number of simultaneously living arrays.

Chapter 7. Experimental Validation

This has been previously proven by Stockmeyer, but to the best of our knowledge, the proof of Lee et al. is the rst publicly available one[START_REF] Lee | Aliased register allocation for straight-line programs is NP-compl ete[END_REF].

Chapter 8. Decoupled Local Memory Allocation for Linearized Programs

http://www.openhmpp.org

Remerciements