The register allocator/fr
│
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
When we add edge we keep information on 2 places. One is in the interferenceBitmap And the other is in the adjList of the register information in
reginfo[u].adjList.add(v);
reginfo[v].adjList.add(u);
ibitmap[v, u] := true;
ibitmap[u, v] := true;
In the relation between these 2 registers there is no dependant. There is no primary one. They are both equal in it.
In reginfo you access the information by index. 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.
Arrière-plan
Groupement des instructions
More abstract look at the CPU instructions shows us that we have mainly few kinds of 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. Such as MOV, LAHF, POP, PUSH, LEA
- Third group of instructions are those to compare data. They do not change the data. just check it. Such instructions are TEST, COMPARE
- Fourth group of instructions are those who change the flow of the execution of the instructions such as: JMP, Jcc, JCXZ,
- Fifth group are instructions that changes data based on other data like ADD
Another grouping of instructions could be by the cpu version where the instruction first appear.
Another grouping of instructions could be based on the registers that can be used in the instruction. 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. Some registers have subregisters some do not.
Données dans les instructions
Almost all of the instructions operate on some data. Also uses some data to perform operation. The data can be in the cpu registers, memory, cpu flags.
Programmation utilisant les instructions
The instructions are independant one from other. However when a program is created there are some logical dependencies that programmer introduce. Programmer wants a few modifications to be performed on some data. Which can be performed by few instructions executed one after another. And at the end the needed data will be produced. But data is not exactly Cpu register, or memory address. Data is something the the programmer cares about. For example, we have some starting data that equals 1000. we can put it in cpu register we want to add to it 200. We can use Asm instruction add, but then we can move the value that we reached in another register. And then to increment it by 300 at the end we will have the needed value 1500. But we used two registers for one date. Normally we don't have to use two registers. We can do it using one. Cause we have to move the data to second register somewhere in the middle. And this is extra instruction. However more than one data is parallel processed. And sometimes we can use this extra move. Just to speed up executions on other data. This is normally needed when to datas are produced that will calculate third one.
This is not very important for the register allocator. 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
In the current implementation the getting of the registers and the allocation are mixed together. Also they share same structures, same class. But the data for each of them is used on the completely different phases. Mixing them togather brings more code on one place. Also its getting difficult to separate them when you work on them. They can be easily devided without lost of speed. 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. But at the end different allocators can process this data. It is difficult for further develop the register allocation cause many phases and logic was brought together on one place.
In the
TRgObj.colour_registers
method different approach can be performed.
Entering different states can be implemented. Instead checking the counts of all lists. It will be faster. Clear code. Easy for debugging. Easy to develop further.
Improvements can be made in the weights of the instructions. Or in the way the allocator decides which register to spill and which not.