The register allocator/fr: what changed

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

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