The register allocator/fr: what changed

Revision 0 to 1. Removed lines have a minus sign; added lines have a plus sign.

Title: The register allocator/fr

New		Line
1	+	Retour au contenu [[FPC internals/fr\|FPC internals]]
2	+
3	+	## Introduction
4	+
5	+	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`.
6	+
7	+	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.
8	+
9	+	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.
10	+
11	+	## Comment utiliser l'allocateur de registre
12	+
13	+	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.
14	+
15	+	### Création de l'allocateur de registre
16	+
17	+	La première étape consiste à créer l'allocateur de registre avnt de pouvoir utiliser ses fonctionnalités.
18	+
19	+	Le générateur de code de bas niveau créée plusieurs instances de la classe `TRgObj`. Normalement, cela se produit dans :
20	+
21	+	`tcg.init_register_allocators`
22	+
23	+	Et les instances sont normalement libérées dans :
24	+
25	+	`tcg.done_register_allocators `
26	+
27	+	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.
28	+
29	+	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.
30	+
31	+	### Utilisation des registres dans la génération de code
32	+
33	+	Pour allouer un registre, utilisez la méthode suivante :
34	+
35	+	`TRgObj.getRegister`
36	+
37	+	à 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.
38	+
39	+	Le générateur de code l'appelle dans les fonctions suivantes :
40	+
41	+	`tcg.GetIntRegister`\
42	+	`tcg.GetAddressRegister`\
43	+	`tcg.GetFPURegister`\
44	+	`tcg.GetMMRegister`
45	+
46	+	En outre, les méthodes suivantes :
47	+
48	+	`TRgObj.getCpuRegister`\
49	+	`TRgObj.ungetCpuRegister`\
50	+	`TRgObj.allocCpuRegisters`\
51	+	`TRgObj.deallocCpuRegisters`
52	+
53	+	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.
54	+
55	+	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.
56	+
57	+	` TRgObj.add_reg_instruction(instr, r, cg.executionweight);`
58	+
59	+	Mais pour l'instruction MOV, une méthode spécifique est utilisée
60	+
61	+	` TRgObj.add_move_instruction(instr:Taicpu);`
62	+
63	+	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.
64	+
65	+	### Générer les registres réels
66	+
67	+	A la fin, quand tous les instruction assembleur sont générées, nous appelons
68	+
69	+	` do_register_allocation(list: TAsmList; headerTai: TAi)`
70	+
71	+	Il calcule les registres réels pour les imaginaires.
72	+
73	+	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
74	+
75	+	`TRgObj.add_Edge`
76	+
77	+	Ces interférences sont construites pendant l'allocation de registre. Chaque descendant qui veut ajouter des interférences surcharge la méthode
78	+
79	+	``` pascal
80	+	procedure TRgObj.add_cpu_interferences(p: TAi); virtual;
81	+	```
82	+
83	+	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.
84	+
85	+	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.
86	+
87	+	## Conseil
88	+
89	+	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é.
90	+
91	+	## Hiérarchie des appels pour les méthodes publiques
92	+
93	+	``` pascal
94	+	Public
95	+
96	+	constructor
97	+
98	+	destructor
99	+
100	+	do_register_allocation - level 1 is ordered by calling
101	+	insert_regalloc_info_all
102	+	generate_interference_graph
103	+	add_edges_used(1, 2) get_alias add_edge
104	+	add_edge ibitmap.s
105	+	prepare_colouring
106	+	make_work_list ri_coalesced
107	+	sort_simplify_worklist
108	+	colour_registers
109	+	simplify ri_coalesced
110	+	decrement_degree ri_coalesced
111	+	coalesce get_alias simplifyworklist.add(v); ibitmap
112	+	conservative ri_coalesced
113	+	adjacent_ok ri_coalesced ibitmap
114	+	add_worklist simplifyworklist.add(u);
115	+	combine ibitmap, add_edge
116	+	enable_moves
117	+	decrement_degree ri_coalesced simplifyworklist.add(m)
118	+	add_edge ibitmap.s
119	+	freeze
120	+	freeze_moves(, 2) get_alias(3)
121	+	select_spill
122	+	freeze_moves(, 2) get_alias(3)
123	+	assign_colours(, 2) get_alias
124	+	epilogue_colouring Destroys the objects used during the coloring - worklist_moves, active_moves, frozen_moves, coalesced_moves, constrained_moves, reginfo.movelist
125	+	spill_registers
126	+	clear_interferences ibitmap.s
127	+	instr_spill_register get_alias
128	+	getregisterinline
129	+	add_edges_used(2, 2) get_alias
130	+	add_edge ibitmap.s
131	+	ungetregisterinline
132	+	get_spill_subreg
133	+	do_spill_replace
134	+	do_spill_read
135	+	do_spill_written
136	+	translate_registers
137	+	assign_colours(, 2) get_alias
138	+
139	+	getregister
140	+
141	+	add_move_instruction
142	+	add_to_movelist
143	+
144	+	combine ri_coalesced(s)
145	+	enable_moves
146	+	decrement_degree ri_coalesced
147	+
148	+	-----------------------------------------
149	+	Properties
150	+
151	+	live_range_direction
152	+	set_live_range_direction
153	+
154	+	live_start
155	+	get_live_start
156	+	set_live_start
157	+
158	+	live_end
159	+	get_live_end
160	+	set_live_end
161	+	```
162	+
163	+	## Classe TRgObj
164	+
165	+	### Description
166	+
167	+	Classe principale pour l'allocation de registre dans FPC
168	+
169	+	### Méthodes publiques
170	+
171	+	### Méthodes protégées
172	+
173	+	### Méthodes privées
174	+
175	+	## Registres imaginaires
176	+
177	+	### Stockage des registres imaginaires
178	+
179	+	`TRgObj` stockent les registres imaginaires dans une liste de structure `TRegInfo`.
180	+
181	+	### Vie d'un registre imaginaire
182	+
183	+	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.
184	+
185	+
186	+	`live_start: TAi;` indique quelle est l'instruction assembleur où le registre est utilisé pour la première fois.
187	+
188	+	`live_end: TAi;` indique quelle est l'instruction assembleur où le registre est utilisé pour la dernière fois.
189	+
190	+	## Interférences
191	+
192	+	Interférences
193	+
194	+	Hiérarchie d'appel:
195	+
196	+	` generate_interference_graph`\
197	+	` add_edges_used(1, 2) get_alias add_edge`\
198	+	` add_edge ibitmap.s`
199	+
200	+	### generate_interference_graph
201	+
202	+	Cette méthode itère sur la liste assembleur. Recherchant l'instruction `reg_alloc` avec le bon `regType`.
203	+
204	+	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`.
205	+
206	+	Après l'ajout ou le retrait dans `live_registers`, elle appelle `add_edges_used`.
207	+
208	+	### add_edges_used
209	+
210	+	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.
211	+
212	+	### add_edge
213	+
214	+	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:
215	+
216	+	``` pascal
217	+	reginfo[u].adjList.add(v);
218	+	reginfo[v].adjList.add(u);
219	+	ibitmap[v, u] := true;
220	+	ibitmap[u, v] := true;
221	+	```
222	+
223	+	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.
224	+
225	+	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.
226	+
227	+	Interférences travaillent avec les super registres.
228	+
229	+	## Arrière-plan
230	+
231	+	### Groupement des instructions
232	+
233	+	Un regard plus abstrait sur les instructions CPU nous montre que nous avons principalement peu de sortes d'instructions.
234	+
235	+	- Le premier groupe contient des instructions qui modifient quelques données.
236	+
237	+	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
238	+
239	+	- Le second groupe sont des instructions qui déplacent les données d'un endroit à un autre.
240	+
241	+	Telle que MOV, LAHF, POP, PUSH, LEA
242	+
243	+	- Le troisième groupe d'instructions sont celles qui comparent les données et ne font aucune modification, il suffit de les contrôler.
244	+
245	+	De telles instructions sont TEST, COMPARE
246	+
247	+	- Le quatrième groupe d'instructions sont celles qui changent le flot d'exécution des instructions, telles que JMP, JCC, JCXZ,
248	+
249	+	- Le cinquième groupe sont les instructions qui changent des données basées sur d'autres données comme ADD
250	+
251	+	Un autre regroupement d'instructions pourrait être par la version de la CPU où l'instruction apparaît en premier.
252	+
253	+	Encore un autre groupement pourrait être basé sur les registres qui peuvent être utilisés dans l'instruction.
254	+
255	+	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.
256	+
257	+	Certains registres ont des sous-registres, d'autres non.
258	+
259	+	### Données dans les instructions
260	+
261	+	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.
262	+
263	+	### Programmation utilisant les instructions
264	+
265	+	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.
266	+
267	+	### Lignes directrices de la conception objet
268	+
269	+	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.
270	+
271	+	Dans la méthode
272	+
273	+	``` pascal
274	+	TRgObj.colour_registers
275	+	```
276	+
277	+	, 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.
278	+
279	+	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.
280	+
281	+	---
282	+	From the Free Pascal wiki, page "The register allocator/fr", as it stood on 2021-03-20 after a change by E-ric, out of the wiki's dump of 2024-05-26. Copyright stays with the author who wrote it, according to the old wiki's [[Licensing]] page. If you have concerns about this material, [message the admin](/wiki-contact).

Back to history