Difference between revisions of "The register allocator/fr"

From Free Pascal wiki
Jump to navigationJump to search
(Created page with "{{The_register_allocator}} Retour au contenu FPC internals == Introduction == Main unit for the register allocation is rgobj.pas Main class for the regi...")
 
 
(16 intermediate revisions by the same user not shown)
Line 4: Line 4:
  
 
== Introduction ==
 
== Introduction ==
Main unit for the register allocation is rgobj.pas
+
L'unité principale pour l'allocation de registre est <tt>rgobj.pas</tt>.
Main class for the register allocation is TRgObj located in rgobj.pas
+
La classe principale pour l'allocation de registre <tt>TRgObj</tt> qui se trouve dans <tt>rgobj.pas</tt>.
  
Register allocator provides imaginary registers for the assembler instructions during the code generation.
+
L'allocateur de registre fournit des registres imaginaires pour les instructions en assembleur pendant la génération de code.
Then it calculates the real registers to replace the imaginary ones.
+
Ensuite il calcule les registres réels pour remplacer les imaginaires.
  
The FPC register allocator uses Register coloring to determine the real registers.
+
L'allocateur de registre de FPC utilise la coloration de registre pour déterminer les registres réels.
It also uses a register spilling technique - when there is not enough registers it uses memory.
+
Il utilise aussi une technique de débordement (''spilling'') de registre - quand il n'y a pas assez de registres, il utilise la mémoire.
  
 
== Comment utiliser l'allocateur de registre ==
 
== Comment utiliser l'allocateur de registre ==
This topic describes how to use the register allocator during the code generation.
+
Ce sujet décrit comment utiliser l'allocateur de registre pendant la génération de code.
Described like a black box with the public methods you can call to get job done.
+
Décrit comme une boîte noire avec des méthodes publiques que vous pouvez appeler pour faire le travail.
  
 
=== Création de l'allocateur de registre ===
 
=== Création de l'allocateur de registre ===
Creating register allocator is the first step we make before we can use its functionality.
+
La première étape consiste à créer l'allocateur de registre avnt de pouvoir utiliser ses fonctionnalités.
  
The low level code generator creates several instances of the TRgObj class. Normally this happens in:
+
Le générateur de code de bas niveau créée plusieurs instances de la classe <tt>TRgObj</tt>. Normalement, cela se produit dans :
 
  tcg.init_register_allocators
 
  tcg.init_register_allocators
And the instances are normally freed in:
+
Et les instances sont normalement libérées dans :
  tcg.done_register_allocators
+
  tcg.done_register_allocators  
Each TRgObj instance allocates registers of a certain type.
+
Chaque instance <tt>TRgObj</tt> alloue des registres d'un certain type.
For example, one register type is Integer registers.
+
Par exemple, un type de registre définit les registres entiers.
Another one is floating point (FPU) registers.
+
Un autre définit les registres en virgule flottante (FPU).
That's why we have a few TRgObj instances, one for every type of register that the cpu supports.
+
C'est pourquoi nous avons quelques instances <tt>TRgObj</tt>, une pour chaque type de registre que la CPU supporte.
  
They are created when the code generation of specific routine begins.
+
Ils sont créés quand la génération de code d'une routine spécifique commence.
Code generator works on subroutine level.
+
Le générateur de code travaille au niveau sous-routines.
The register allocator also allocates registers for specific method, procedure, function.
+
L'allocateur de registre alloue aussi les registrer pour une méthode, procédure ou fonction spécifique.
  
 
=== Utilisation des registres dans la génération de code ===
 
=== Utilisation des registres dans la génération de code ===
  
To allocate a register use the following method:
+
Pour allouer un registre, utilisez la méthode suivante :
 
  TRgObj.getRegister
 
  TRgObj.getRegister
 +
à partir de l'instance appropriée d'allocateur de registre (en fonction du type de registre) pour obtenir le registre d'une instruction assembleur. De cette façon, un registre '''imaginaire''' est alloué et peut être utilisé après cela dans une instruction d'assembleur spécifique.
  
for the appropriate register allocator instance (depending on the register type) to get register for some assembler instruction. This way an '''imaginary''' register is allocated and can be used after that in a specific assembler instruction.
+
Le générateur de code l'appelle dans les fonctions suivantes :
 
 
The code generator calls it in the following functions:
 
 
  tcg.GetIntRegister
 
  tcg.GetIntRegister
 
  tcg.GetAddressRegister
 
  tcg.GetAddressRegister
Line 46: Line 45:
 
  tcg.GetMMRegister
 
  tcg.GetMMRegister
  
 
+
En outre, les méthodes suivantes :
Additionally, the following methods:
 
 
 
 
  TRgObj.getCpuRegister
 
  TRgObj.getCpuRegister
 
  TRgObj.ungetCpuRegister
 
  TRgObj.ungetCpuRegister
Line 54: Line 51:
 
  TRgObj.deallocCpuRegisters
 
  TRgObj.deallocCpuRegisters
  
allocate or free one or multiple '''real''' registers (not imaginary ones!) This is usually used for instructions that require a specific register (for example SHL/SHR/SAR on x86, which always uses ECX). This is also used when doing a function call to indicate that certain registers (which depend on the calling convention) may be destroyed by the called function.
+
allouent ou libèrent un ou plusieurs registres '''réels''' (pas les imaginaires !). Ceci est généralement utilisé pour les instructions qui demandent un registre spécifique (par exemple SHL/SHR/SAR on x86, qui utilisent toujours ECX). C'est aussi utilisé quand on fait un appel de fonction pour indiquer que certains registres (ce qui dépend de la convention d'appel) peuvent être détruits par l'appel de fonction.
  
After allocating the register we can use it in some assembler instructions.
+
Après l'allocation du registre, nous pouvons l'utiliser dans des insrtructions assembleur.
For every instruction that generates, the code generator notifies the register allocator.
+
Pour chaque instruction qu'il génère, le générateur de code notifie l'allocateur de registre.
It passes the instruction, also the imaginary register as parameters to the following method.
+
Il passe l'instruction, ainsi que le registre imaginaire comme paramètres à la méthode suivante.
 
           TRgObj.add_reg_instruction(instr, r, cg.executionweight);
 
           TRgObj.add_reg_instruction(instr, r, cg.executionweight);
But for MOV instruction there is specific method that is used
+
Mais pour l'instruction MOV, une méthode spécifique est utilisée
 
           TRgObj.add_move_instruction(instr:Taicpu);
 
           TRgObj.add_move_instruction(instr:Taicpu);
  
Also weight is provided to determine which register should be spilled and which is better to use real cpu register.
+
Un poids est également fourni pour déterminer quel registre doit être débordé (''spilled'') et lequel il est préférable d'utiliser un vrai registre CPU.
  
 
=== Générer les registres réels ===
 
=== Générer les registres réels ===
  
At the end when all the assembler instructions are generated we call
+
A la fin, quand tous les instruction assembleur sont générées, nous appelons
 
         do_register_allocation(list: TAsmList; headerTai: TAi)
 
         do_register_allocation(list: TAsmList; headerTai: TAi)
It calculates real registers for the imaginary ones.
+
Il calcule les registres réels pour les imaginaires.
  
Some instructions can use only certain types of registers. So, the register allocator can not choose from all the Cpu registers.
+
Des instructions peuvent utiliser seulement certain types de registres. Ainsi, l'allocateur de registre ne peut pas choisir tous les registres CPU.
For these instructions we notify the register allocator by calling the method:
+
Pour ces instructions, nous notifions l'allocateur de registre en appelant la méthode
  
 
  TRgObj.add_Edge
 
  TRgObj.add_Edge
  
These interferences are build during the register allocation.  
+
Ces interférences sont construites pendant l'allocation de registre.
Every descendent that wants to add some interferences overrides the method
+
Chaque descendant qui veut ajouter des interférences surcharge la méthode
  
 
<syntaxhighlight lang=pascal>
 
<syntaxhighlight lang=pascal>
Line 83: Line 80:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
We have descendents of TRgObj for the different kind of processors.
+
Nous avons des descendants de <tt>TRgObj</tt> pour les différents types de processeurs.
They call add_edge in add_cpu_interferences depending on the specific CPU architecture.
+
Ils appellent <tt>add_edge</tt> dans <tt>add_cpu_interferences</tt> selon l'architecture CPU particulière.
It is used for Arm processors, x86 processors etc.
+
C'est utilisé pour les processeurs ARM, x86 etc.
  
In method tcgprocinfo.generate_code which is located in unit psub.pas  
+
Dans la méthode <tt>tcgprocinfo.generate_code</tt>, qui se trouve dans l'unité <tt>psub.pas</tt>, est implémentée la création d'allocateurs de registre, l'obtention des registres, la génération de registres réels.
is implemented the creation of register allocators, getting the registers, generation of real registers.
+
Cette méthode occupe une place centrale dans la génération de code qui l'allocation de registre.
This method is central place for code generation which includes the register allocation.
+
Dans celle-ci, vous pouvez trouver un appel à <tt>hlcg.init_register_allocators</tt> pour créer les allocateurs de registre.
Inside it you can find call to hlcg.init_register_allocators to create the Register Allocators
+
Faites appel à <tt>cg.do_register_allocation(aktproccode,headertai);</tt> - pour faire l'allocation effective et aussi à <tt>hlcg.done_register_allocators;</tt> pour les libérer les allocateurs.
call to cg.do_register_allocation(aktproccode,headertai); - to do the actual allocation
 
also to hlcg.done_register_allocators; - to free the allocators
 
  
== Conseils ==
+
== Conseil ==
  
You can compile your project by using the -sr switch. This will leave the immaginary register names in the generated .s file
+
Vous pouvez compiler votre projet en utilisant le commutateur -sr. Cela permettra de conserver les noms de registre imaginaire dans le fichier .s généré.
  
 
== Hiérarchie des appels pour les méthodes publiques ==
 
== Hiérarchie des appels pour les méthodes publiques ==
Line 175: Line 170:
 
=== Description ===
 
=== Description ===
  
Main class for register allocation in FPC
+
Classe principale pour l'allocation de registre dans FPC
  
 
=== Méthodes publiques ===
 
=== Méthodes publiques ===
Line 187: Line 182:
 
=== Stockage des registres imaginaires===
 
=== Stockage des registres imaginaires===
  
TRgObj stores the imaginary registers in list of TRegInfo structure.
+
<tt>TRgObj</tt> stockent les registres imaginaires dans une liste de structure <tt>TRegInfo</tt>.
  
 
=== Vie d'un registre imaginaire ===
 
=== Vie d'un registre imaginaire ===
  
Life of imaginary register starts when it is first used by assembler instruction.
+
La vie d'un registre imaginaire commence quand il est utilisé la première fois pas une instruction assembleur.
When it first appears in an assembler instruction in the assembler list for the specific routine.
+
Lorsqu'il apparaît pour la première fois dans une instruction assembleur dans la liste assembleur pour la routine spécifique.  
And ends when it is last used in an assembler instruction.
+
Et finit quand il est utilisé pour la dernière fois dans une instruction assembleur.
In the TRegInfo structure for the specific imaginary register there are 2 fields for the life of the register.
+
Dans la structure <tt>TRegInfo</tt> pour le registre imaginaire particulier, il y a deux champs pour la vie du registre.
live_start: TAi; indicates which is the assembler instruction where the register is first used.
+
:<tt>live_start: TAi;</tt> indique quelle est l'instruction assembleur où le registre est utilisé pour la première fois.
live_end: TAi; indicates which is the assembler instruction where the register is last used.
+
:<tt>live_end: TAi;</tt> indique quelle est l'instruction assembleur où le registre est utilisé pour la dernière fois.
  
 
== Interférences ==
 
== Interférences ==
Line 202: Line 197:
 
Interférences
 
Interférences
  
Call hierarchy
+
Hiérarchie d'appel:
 
   generate_interference_graph
 
   generate_interference_graph
 
     add_edges_used(1, 2) get_alias add_edge
 
     add_edges_used(1, 2) get_alias add_edge
Line 210: Line 205:
 
=== generate_interference_graph ===
 
=== generate_interference_graph ===
  
This method iterates the assembler list. Looking for reg_alloc instruction, with the proper regType.
+
Cette méthode itère sur la liste assembleur. Recherchant l'instruction <tt>reg_alloc</tt> avec le bon <tt>regType</tt>.
  
During the iteration we keep all register that are live in list - live_registers.
+
Pendant cette itération, nous gardons tout registre en vie dans la liste - <tt>live_registers</tt>.
if its allocating it adds the superregister to the live_registers.
+
S'il est alloué, elle ajoute le superregistre à <tt>live_registers</tt>
if its dealloc it removes it from the live_registers.
+
S'il est désalloué, elle le retire de <tt>live_registers</tt>.
  
After adding or removing in live_registers it calls add_edges_used
+
Après l'ajout ou le retrait dans <tt>live_registers</tt>, elle appelle <tt>add_edges_used</tt>.
  
 
=== add_edges_used ===
 
=== add_edges_used ===
  
Iterates all live_registers and calls add_edge it gets the alias of the current live_register.
+
Itère sur tout <tt>live_registers</tt> et appelle <tt>add_edge</tt>
and the super register u that is passed to the method.
+
Itère tous les live_register et appelle <tt>add_edge</tt>, elle obtient l'alias du live_register actuel et le super registre qui est à la méthode.
  
 
=== add_edge ===
 
=== add_edge ===
  
When we add edge we keep information on 2 places.
+
Quand nous ajoutons un bord, nous gardons l'information sur deux endroits.
One is in the interferenceBitmap
+
L'un est dans le <tt>interferenceBitmap</tt>. Et l'autre dans la <tt>adjList</tt> de l'information de registre dans:
And the other is in the adjList of the register information in
 
  
 
<syntaxhighlight lang=pascal>
 
<syntaxhighlight lang=pascal>
Line 236: Line 230:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
In the relation between these 2 registers there is no dependant.
+
Dans la relation entre ces deux registres, il n'y a pas de dépendance. Il n'y a pas de primaire , ils sont égaux dedans.
There is no primary one. They are both equal in it.
 
  
In reginfo you access the information by index.
+
Dans <tt>reginfo</tt>, vous accédez à l'information par un index et dans la Bitmap vous faites pareil. C'est à peu près la même chose en vitesse.
And in bitmap you do the same. This is prity much the same as speed.
 
Why we have this duplicate information on 2 places.
 
  
Interferences work with super registers.
+
Interférences travaillent avec les super registres.
  
 
== Arrière-plan ==
 
== Arrière-plan ==
Line 249: Line 240:
 
=== Groupement des instructions ===
 
=== Groupement des instructions ===
  
More abstract look at the CPU instructions shows us that we have mainly few kinds of instructions.
+
Un regard plus abstrait sur les instructions CPU nous montre que nous avons principalement peu de sortes d'instructions.
- The first group contains instructions that changes some data.
 
This data remains on the same place but it is changed. Also do not need extra data ot perform the change
 
Some instructions like these are
 
inc, dec, CLC, CLD
 
  
- Second group are instructions that move date from one place to another.
+
* Le premier groupe contient des instructions qui modifient quelques données.
Such as
+
Ces données restent à la même place mais sont modifiées. Vous n'avez pas non plus besoin de données supplémentaires pour effectuer le changement.
MOV, LAHF, POP, PUSH, LEA
+
Quelques instructions de ce groupe sont INC, DEC, CLC, CLD
  
- Third group of instructions are those to compare data.
+
* Le second groupe sont des instructions qui déplacent les données d'un endroit à un autre.
They do not change the data. just check it.
+
Telle que MOV, LAHF, POP, PUSH, LEA
Such instructions are
 
TEST, COMPARE
 
  
- Fourth group of instructions are those who change the flow of the execution of the instructions
+
* Le troisième groupe d'instructions sont celles qui comparent les données et ne font aucune modification, il suffit de les contrôler.
such as:
+
De telles instructions sont TEST, COMPARE
JMP, Jcc, JCXZ,
 
  
- Fifth group are instructions that changes data based on other data
+
* Le quatrième groupe d'instructions sont celles qui changent le flot d'exécution des instructions, telles que JMP, JCC, JCXZ,
like
 
ADD
 
  
Another grouping of instructions could be by the cpu version where the instruction first appear.
+
* Le cinquième groupe sont les instructions qui changent des données basées sur d'autres données comme ADD
  
Another grouping of instructions could be based on the registers that can be used in the instruction.
+
Un autre regroupement d'instructions pourrait être par la version de la CPU où l'instruction apparaît en premier.
Some instructions can use only specific registers for the address - mov ax, [bx + si + 1000] You can choose between for example only these registers - BP, BX, SI and DI.
+
 
Some instructions can use only registers, some addresses, some both.
+
Encore un autre groupement pourrait être basé sur les registres qui peuvent être utilisés dans l'instruction.
Some registers have subregisters some do not.
+
 
 +
Certaines instructions peuvent utiliser seulement des registres spécifiques pour l'adresse - mov ax, [bx + si + 1000]. Vous pouvez choisir seulement entre par exemple ces registres - BP, BX, SI et DI.
 +
Certaines instructions peuvent utiliser seulement des registres, d'autres des adresses, d'autres encore les deux.
 +
 
 +
Certains registres ont des sous-registres, d'autres non.
  
 
=== Données dans les instructions ===
 
=== Données dans les instructions ===
  
Almost all of the instructions operate on some data. Also uses some data to perform operation.
+
Presque toutes les instructions opèrent sur des données. Aussi elles utilisent de la données pour réaliser l'opération.
The data can be in the cpu registers, memory, cpu flags.
+
La donnée peut être dans les registres CPU, la mémoire ou dans les drapeaux de la CPU.
  
 
=== Programmation utilisant les instructions ===
 
=== Programmation utilisant les instructions ===
  
The instructions are independant one from other.
+
Les instructions sont indépendantes l'une de l'autre.
However when a program is created there are some logical dependencies that programmer introduce.
+
Pourtant, quand un programme est créé, il y a des dépendances logiques que le programmeur introduit.
Programmer wants a few modifications to be performed on some data.
+
Un programmeur veut que des modifiées soient apportées à certaines données.
Which can be performed by few instructions executed one after another.
+
Ce qui peut être réalisé par un peu d'instructions exécutées les unes après les autres.
And at the end the needed data will be produced.
+
Et à la fin, les données voulues seront produites.
But data is not exactly Cpu register, or memory address.
+
Mais la donnée n'est pas exactement un registre CPU ou une adresse mémoire.
Data is something the the programmer cares about.
+
Les données sont quelque chose dont le programmeur se soucie.  
For example, we have some starting data that equals 1000. we can put it in cpu register we want to add to it 200.
+
Par exemple, nous avons une donnée qui vaut 1000 au départ. Nous pouvons la placée dans un registre CPU que nous voulons pour y ajouter 200.
We can use Asm instruction add, but then we can move the value that we reached in another register.
+
Nous  pouvons utilmiser une instruction assembleur ADD mais ensuite nous pouvons déplacer la valeur que nous avons atteinte dans un autre registre.
And then to increment it by 300 at the end we will have the needed value 1500.
+
Et alors l'incrémenter de 300 à la fin, nous aurons la valeur recherchée 1500.
But we used two registers for one date.
+
Mais nous utilisons deux registres pour une seule donnée, ce que nous n'avons pas besoin normalement.
Normally we don't have to use two registers.
+
Nous pouvons le faire en en utilisant un seul.
We can do it using one.
+
Parce que nous devons déplacer les données vers le deuxième registre quelque part au milieu.  
Cause we have to move the data to second register somewhere in the middle.
+
Et cela est une intruction supplémentaire.
And this is extra instruction.
+
Cependant, plusieurs données sont traitées en parallèle.  
However more than one data is parallel processed.
+
Et parfois nous utilisons ce déplacement supplémentaire , seulement pour accélerer les exécutions sur d'autres données.
And sometimes we can use this extra move.
+
Ceci est normalement nécessaire lorsque des données sont produites pour calculer la troisième.
Just to speed up executions on other data.
+
Ce n'est pas très important pour l'allocateur de registre, c'est plus destiné au générateur de code.
This is normally needed when to datas are produced that will calculate third one.
+
Le générateur de code pourrait décider où ajouter des instructions supplémentaires, pour accélérer d'autres exécutions.
 
+
Il semble que l'allocateur de registre ne devrait pas s'en soucier.
This is not very important for the register allocator.
+
Mais il est bon d'y penser.
It is more dedicated to the code generator.
 
Code generator could decide where to add extra instruction, to speed other executions.
 
It look like register allocator should not care about this.
 
But it's good to thing about it.
 
  
 
=== Lignes directrices de la conception objet ===
 
=== Lignes directrices de la conception objet ===
  
In the current implementation the getting of the registers and the allocation are mixed together.
+
Dans l'implémentation actuelle, l'obtention des registres et l'attribution sont mélangées.
Also they share same structures, same class.
+
Ils partagent également les mêmes structures, la même classe.
But the data for each of them is used on the completely different phases.
+
Mais les données pour chacun d'entre eux sont utilisées sur des phases complètement différentes.
Mixing them togather brings more code on one place.
+
Les mélanger ensemble apporte plus de code en un seul endroit.
Also its getting difficult to separate them when you work on them.
+
De plus, il devient difficile de les séparer lorsque vous travaillez dessus.
They can be easily devided without lost of speed.
+
Ils peuvent être facilement divisés sans perte de vitesse.
Also different types of register allocations can be used. The getting of the registers and setting the weights, also life … can be on one place.
+
Différents types d'allocations de registre peuvent également être utilisés. L'obtention des registres et le réglage des poids, ainsi que la vie ... peuvent être en un seul endroit.
But at the end different allocators can process this data.
+
Mais à la fin, différents allocateurs peuvent traiter ces données.
It is difficult for further develop the register allocation cause many phases and logic was brought together on one place.
+
Il est difficile de développer davantage l'attribution du registre car de nombreuses phases et la logique ont été réunies en un seul endroit.
  
In the <syntaxhighlight lang=pascal>TRgObj.colour_registers</syntaxhighlight> method different approach can be performed.
+
Dans la méthode <syntaxhighlight lang = pascal> TRgObj.colour_registers </syntaxhighlight>, une approche différente peut être effectuée.
Entering different states can be implemented.
+
La saisie de différents états peut être implémentée.
Instead checking the counts of all lists.
+
Vérifiez plutôt les décomptes de toutes les listes.
It will be faster. Clear code. Easy for debugging. Easy to develop further.
+
Ce sera plus rapide. Code clair. Facile à déboguer. Facile à développer davantage.
  
Improvements can be made in the weights of the instructions. Or in the way the allocator decides which register to spill and which not.
+
Des améliorations peuvent être apportées aux poids des instructions. Ou de la manière dont l'allocateur décide quel registre déverser et lequel non.
  
 
<!--[[Category:FPC]]
 
<!--[[Category:FPC]]
 
[[Category:FPC internals]]-->
 
[[Category:FPC internals]]-->

Latest revision as of 10:06, 20 March 2021

English (en) français (fr)

Retour au contenu FPC internals

Introduction

L'unité principale pour l'allocation de registre est rgobj.pas. La classe principale pour l'allocation de registre TRgObj qui se trouve dans rgobj.pas.

L'allocateur de registre fournit des registres imaginaires pour les instructions en assembleur pendant la génération de code. Ensuite il calcule les registres réels pour remplacer les imaginaires.

L'allocateur de registre de FPC utilise la coloration de registre pour déterminer les registres réels. Il utilise aussi une technique de débordement (spilling) de registre - quand il n'y a pas assez de registres, il utilise la mémoire.

Comment utiliser l'allocateur de registre

Ce sujet décrit comment utiliser l'allocateur de registre pendant la génération de code. Décrit comme une boîte noire avec des méthodes publiques que vous pouvez appeler pour faire le travail.

Création de l'allocateur de registre

La première étape consiste à créer l'allocateur de registre avnt de pouvoir utiliser ses fonctionnalités.

Le générateur de code de bas niveau créée plusieurs instances de la classe TRgObj. Normalement, cela se produit dans :

tcg.init_register_allocators

Et les instances sont normalement libérées dans :

tcg.done_register_allocators 

Chaque instance TRgObj alloue des registres d'un certain type. Par exemple, un type de registre définit les registres entiers. Un autre définit les registres en virgule flottante (FPU). C'est pourquoi nous avons quelques instances TRgObj, une pour chaque type de registre que la CPU supporte.

Ils sont créés quand la génération de code d'une routine spécifique commence. Le générateur de code travaille au niveau sous-routines. L'allocateur de registre alloue aussi les registrer pour une méthode, procédure ou fonction spécifique.

Utilisation des registres dans la génération de code

Pour allouer un registre, utilisez la méthode suivante :

TRgObj.getRegister

à partir de l'instance appropriée d'allocateur de registre (en fonction du type de registre) pour obtenir le registre d'une instruction assembleur. De cette façon, un registre imaginaire est alloué et peut être utilisé après cela dans une instruction d'assembleur spécifique.

Le générateur de code l'appelle dans les fonctions suivantes :

tcg.GetIntRegister
tcg.GetAddressRegister
tcg.GetFPURegister
tcg.GetMMRegister

En outre, les méthodes suivantes :

TRgObj.getCpuRegister
TRgObj.ungetCpuRegister
TRgObj.allocCpuRegisters
TRgObj.deallocCpuRegisters

allouent ou libèrent un ou plusieurs registres réels (pas les imaginaires !). Ceci est généralement utilisé pour les instructions qui demandent un registre spécifique (par exemple SHL/SHR/SAR on x86, qui utilisent toujours ECX). C'est aussi utilisé quand on fait un appel de fonction pour indiquer que certains registres (ce qui dépend de la convention d'appel) peuvent être détruits par l'appel de fonction.

Après l'allocation du registre, nous pouvons l'utiliser dans des insrtructions assembleur. Pour chaque instruction qu'il génère, le générateur de code notifie l'allocateur de registre. Il passe l'instruction, ainsi que le registre imaginaire comme paramètres à la méthode suivante.

         TRgObj.add_reg_instruction(instr, r, cg.executionweight);

Mais pour l'instruction MOV, une méthode spécifique est utilisée

         TRgObj.add_move_instruction(instr:Taicpu);

Un poids est également fourni pour déterminer quel registre doit être débordé (spilled) et lequel il est préférable d'utiliser un vrai registre CPU.

Générer les registres réels

A la fin, quand tous les instruction assembleur sont générées, nous appelons

       do_register_allocation(list: TAsmList; headerTai: TAi)

Il calcule les registres réels pour les imaginaires.

Des instructions peuvent utiliser seulement certain types de registres. Ainsi, l'allocateur de registre ne peut pas choisir tous les registres CPU. Pour ces instructions, nous notifions l'allocateur de registre en appelant la méthode

TRgObj.add_Edge

Ces interférences sont construites pendant l'allocation de registre. Chaque descendant qui veut ajouter des interférences surcharge la méthode

procedure TRgObj.add_cpu_interferences(p: TAi); virtual;

Nous avons des descendants de TRgObj pour les différents types de processeurs. Ils appellent add_edge dans add_cpu_interferences selon l'architecture CPU particulière. C'est utilisé pour les processeurs ARM, x86 etc.

Dans la méthode tcgprocinfo.generate_code, qui se trouve dans l'unité psub.pas, est implémentée la création d'allocateurs de registre, l'obtention des registres, la génération de registres réels. Cette méthode occupe une place centrale dans la génération de code qui l'allocation de registre. Dans celle-ci, vous pouvez trouver un appel à hlcg.init_register_allocators pour créer les allocateurs de registre. Faites appel à cg.do_register_allocation(aktproccode,headertai); - pour faire l'allocation effective et aussi à hlcg.done_register_allocators; pour les libérer les allocateurs.

Conseil

Vous pouvez compiler votre projet en utilisant le commutateur -sr. Cela permettra de conserver les noms de registre imaginaire dans le fichier .s généré.

Hiérarchie des appels pour les méthodes publiques

Public


constructor

destructor

do_register_allocation - level 1 is ordered by calling
  insert_regalloc_info_all
  generate_interference_graph
    add_edges_used(1, 2)			get_alias						add_edge
      add_edge												ibitmap.s
  prepare_colouring
    make_work_list				ri_coalesced
      sort_simplify_worklist
  colour_registers
    simplify					ri_coalesced
      decrement_degree				ri_coalesced
    coalesce					get_alias		simplifyworklist.add(v);	ibitmap
      conservative				ri_coalesced
      adjacent_ok				ri_coalesced						ibitmap
      add_worklist							simplifyworklist.add(u);
      combine												ibitmap, add_edge
        enable_moves
        decrement_degree			ri_coalesced		simplifyworklist.add(m)
        add_edge											ibitmap.s
    freeze
      freeze_moves(, 2)				get_alias(3)
    select_spill
      freeze_moves(, 2)				get_alias(3)
    assign_colours(, 2)				get_alias
  epilogue_colouring		Destroys the objects used during the coloring - worklist_moves, active_moves, frozen_moves, coalesced_moves, constrained_moves, reginfo.movelist
  spill_registers
    clear_interferences											ibitmap.s
    instr_spill_register			get_alias
      getregisterinline
        add_edges_used(2, 2)			get_alias
	  add_edge											ibitmap.s
      ungetregisterinline
      get_spill_subreg
      do_spill_replace
      do_spill_read
      do_spill_written
  translate_registers
    assign_colours(, 2)				get_alias

getregister

add_move_instruction
  add_to_movelist

combine						ri_coalesced(s)
  enable_moves
  decrement_degree				ri_coalesced

-----------------------------------------
Properties

live_range_direction
  set_live_range_direction

live_start
  get_live_start
  set_live_start

live_end
  get_live_end
  set_live_end

Classe TRgObj

Description

Classe principale pour l'allocation de registre dans FPC

Méthodes publiques

Méthodes protégées

Méthodes privées

Registres imaginaires

Stockage des registres imaginaires

TRgObj stockent les registres imaginaires dans une liste de structure TRegInfo.

Vie d'un registre imaginaire

La vie d'un registre imaginaire commence quand il est utilisé la première fois pas une instruction assembleur. Lorsqu'il apparaît pour la première fois dans une instruction assembleur dans la liste assembleur pour la routine spécifique. Et finit quand il est utilisé pour la dernière fois dans une instruction assembleur. Dans la structure TRegInfo pour le registre imaginaire particulier, il y a deux champs pour la vie du registre.

live_start: TAi; indique quelle est l'instruction assembleur où le registre est utilisé pour la première fois.
live_end: TAi; indique quelle est l'instruction assembleur où le registre est utilisé pour la dernière fois.

Interférences

Interférences

Hiérarchie d'appel:

 generate_interference_graph
   add_edges_used(1, 2)			get_alias						add_edge
     add_edge												ibitmap.s


generate_interference_graph

Cette méthode itère sur la liste assembleur. Recherchant l'instruction reg_alloc avec le bon regType.

Pendant cette itération, nous gardons tout registre en vie dans la liste - live_registers. S'il est alloué, elle ajoute le superregistre à live_registers S'il est désalloué, elle le retire de live_registers.

Après l'ajout ou le retrait dans live_registers, elle appelle add_edges_used.

add_edges_used

Itère sur tout live_registers et appelle add_edge Itère tous les live_register et appelle add_edge, elle obtient l'alias du live_register actuel et le super registre qui est à la méthode.

add_edge

Quand nous ajoutons un bord, nous gardons l'information sur deux endroits. L'un est dans le interferenceBitmap. Et l'autre dans la adjList de l'information de registre dans:

reginfo[u].adjList.add(v);
reginfo[v].adjList.add(u);
ibitmap[v, u] := true;
ibitmap[u, v] := true;

Dans la relation entre ces deux registres, il n'y a pas de dépendance. Il n'y a pas de primaire , ils sont égaux dedans.

Dans reginfo, vous accédez à l'information par un index et dans la Bitmap vous faites pareil. C'est à peu près la même chose en vitesse.

Interférences travaillent avec les super registres.

Arrière-plan

Groupement des instructions

Un regard plus abstrait sur les instructions CPU nous montre que nous avons principalement peu de sortes d'instructions.

  • Le premier groupe contient des instructions qui modifient quelques données.

Ces données restent à la même place mais sont modifiées. Vous n'avez pas non plus besoin de données supplémentaires pour effectuer le changement. Quelques instructions de ce groupe sont INC, DEC, CLC, CLD

  • Le second groupe sont des instructions qui déplacent les données d'un endroit à un autre.

Telle que MOV, LAHF, POP, PUSH, LEA

  • Le troisième groupe d'instructions sont celles qui comparent les données et ne font aucune modification, il suffit de les contrôler.

De telles instructions sont TEST, COMPARE

  • Le quatrième groupe d'instructions sont celles qui changent le flot d'exécution des instructions, telles que JMP, JCC, JCXZ,
  • Le cinquième groupe sont les instructions qui changent des données basées sur d'autres données comme ADD

Un autre regroupement d'instructions pourrait être par la version de la CPU où l'instruction apparaît en premier.

Encore un autre groupement pourrait être basé sur les registres qui peuvent être utilisés dans l'instruction.

Certaines instructions peuvent utiliser seulement des registres spécifiques pour l'adresse - mov ax, [bx + si + 1000]. Vous pouvez choisir seulement entre par exemple ces registres - BP, BX, SI et DI. Certaines instructions peuvent utiliser seulement des registres, d'autres des adresses, d'autres encore les deux.

Certains registres ont des sous-registres, d'autres non.

Données dans les instructions

Presque toutes les instructions opèrent sur des données. Aussi elles utilisent de la données pour réaliser l'opération. La donnée peut être dans les registres CPU, la mémoire ou dans les drapeaux de la CPU.

Programmation utilisant les instructions

Les instructions sont indépendantes l'une de l'autre. Pourtant, quand un programme est créé, il y a des dépendances logiques que le programmeur introduit. Un programmeur veut que des modifiées soient apportées à certaines données. Ce qui peut être réalisé par un peu d'instructions exécutées les unes après les autres. Et à la fin, les données voulues seront produites. Mais la donnée n'est pas exactement un registre CPU ou une adresse mémoire. Les données sont quelque chose dont le programmeur se soucie. Par exemple, nous avons une donnée qui vaut 1000 au départ. Nous pouvons la placée dans un registre CPU que nous voulons pour y ajouter 200. Nous pouvons utilmiser une instruction assembleur ADD mais ensuite nous pouvons déplacer la valeur que nous avons atteinte dans un autre registre. Et alors l'incrémenter de 300 à la fin, nous aurons la valeur recherchée 1500. Mais nous utilisons deux registres pour une seule donnée, ce que nous n'avons pas besoin normalement. Nous pouvons le faire en en utilisant un seul. Parce que nous devons déplacer les données vers le deuxième registre quelque part au milieu. Et cela est une intruction supplémentaire. Cependant, plusieurs données sont traitées en parallèle. Et parfois nous utilisons ce déplacement supplémentaire , seulement pour accélerer les exécutions sur d'autres données. Ceci est normalement nécessaire lorsque des données sont produites pour calculer la troisième. Ce n'est pas très important pour l'allocateur de registre, c'est plus destiné au générateur de code. Le générateur de code pourrait décider où ajouter des instructions supplémentaires, pour accélérer d'autres exécutions. Il semble que l'allocateur de registre ne devrait pas s'en soucier. Mais il est bon d'y penser.

Lignes directrices de la conception objet

Dans l'implémentation actuelle, l'obtention des registres et l'attribution sont mélangées. Ils partagent également les mêmes structures, la même classe. Mais les données pour chacun d'entre eux sont utilisées sur des phases complètement différentes. Les mélanger ensemble apporte plus de code en un seul endroit. De plus, il devient difficile de les séparer lorsque vous travaillez dessus. Ils peuvent être facilement divisés sans perte de vitesse. Différents types d'allocations de registre peuvent également être utilisés. L'obtention des registres et le réglage des poids, ainsi que la vie ... peuvent être en un seul endroit. Mais à la fin, différents allocateurs peuvent traiter ces données. Il est difficile de développer davantage l'attribution du registre car de nombreuses phases et la logique ont été réunies en un seul endroit.

Dans la méthode

 TRgObj.colour_registers

, une approche différente peut être effectuée.

La saisie de différents états peut être implémentée. Vérifiez plutôt les décomptes de toutes les listes. Ce sera plus rapide. Code clair. Facile à déboguer. Facile à développer davantage.

Des améliorations peuvent être apportées aux poids des instructions. Ou de la manière dont l'allocateur décide quel registre déverser et lequel non.