The register allocator: what changed

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

Old	New		Line
1	1		back to contents [[FPC internals]]
2	2
3	3		## Introduction
4	4
5	5		Main unit for the register allocation is rgobj.pas Main class for the register allocation is TRgObj located in rgobj.pas
6	6
7	7		Register allocator provides imaginary registers for the assembler instructions during the code generation. Then it calculates the real registers to replace the imaginary ones.
8	8
9	9		The FPC register allocator uses Register coloring to determine the real registers. It also uses a register spilling technique - when there is not enough registers it uses memory.
10	10
11	11		## How to use the register allocator
12	12
13	13		This topic describes how to use the register allocator during the code generation. Described like a black box with the public methods you can call to get job done.
14	14
15	15		### Creating the Register allocator
16	16
17	17		Creating register allocator is the first step we make before we can use its functionality.
18	18
19	19		The low level code generator creates several instances of the TRgObj class. Normally this happens in:
20	20
21		-	~~`tcg.init_register_allocators`~~
	21	+	```text
	22	+	tcg.init_register_allocators
	23	+	```
22	24
23	25		And the instances are normally freed in:
24	26
25		-	~~`tcg.done_register_allocators`~~
	27	+	```text
	28	+	tcg.done_register_allocators
	29	+	```
26	30
27	31		Each TRgObj instance allocates registers of a certain type. For example, one register type is Integer registers. Another one is floating point (FPU) registers. That's why we have a few TRgObj instances, one for every type of register that the cpu supports.
28	32
29	33		They are created when the code generation of specific routine begins. Code generator works on subroutine level. The register allocator also allocates registers for specific method, procedure, function.
30	34
31	35		### Using registers in the code generation
32	36
33	37		To allocate a register use the following method:
34	38
35		-	~~`TRgObj.getRegister`~~
	39	+	```text
	40	+	TRgObj.getRegister
	41	+	```
36	42
37	43		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.
38	44
39	45		The code generator calls it in the following functions:
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		Additionally, the following methods:
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		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.
54	64
55	65		After allocating the register we can use it in some assembler instructions. For every instruction that generates, the code generator notifies the register allocator. It passes the instruction, also the imaginary register as parameters to the following method.
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		But for MOV instruction there is specific method that is used
60	72
61		-	~~` TRgObj.add_move_instruction(instr:Taicpu);`~~
	73	+	```text
	74	+	TRgObj.add_move_instruction(instr:Taicpu);
	75	+	```
62	76
63	77		Also weight is provided to determine which register should be spilled and which is better to use real cpu register.
64	78
65	79		### Generating of real registers
66	80
67	81		At the end when all the assembler instructions are generated we call
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		It calculates real registers for the imaginary ones.
72	88
73	89		Some instructions can use only certain types of registers. So, the register allocator can not choose from all the Cpu registers. For these instructions we notify the register allocator by calling the method:
74	90
75		-	~~`TRgObj.add_Edge`~~
	91	+	```text
	92	+	TRgObj.add_Edge
	93	+	```
76	94
77	95		These interferences are build during the register allocation. Every descendent that wants to add some interferences overrides the method
78	96
79	97		``` pascal
80	98		procedure TRgObj.add_cpu_interferences(p: TAi); virtual;
81	99		```
82	100
83	101		We have descendents of TRgObj for the different kind of processors. They call add_edge in add_cpu_interferences depending on the specific CPU architecture. It is used for Arm processors, x86 processors etc.
84	102
85	103		In method tcgprocinfo.generate_code which is located in unit psub.pas is implemented the creation of register allocators, getting the registers, generation of real registers. This method is central place for code generation which includes the register allocation. Inside it you can find call to hlcg.init_register_allocators to create the Register Allocators call to cg.do_register_allocation(aktproccode,headertai); - to do the actual allocation also to hlcg.done_register_allocators; - to free the allocators
86	104
87	105		## Tips
88	106
89	107		You can compile your project by using the -sr switch. This will leave the immaginary register names in the generated .s file
90	108
91	109		## Calls hierarchy for the public methods
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		## Class TRgObj
164	182
165	183		### Description
166	184
167	185		Main class for register allocation in FPC
168	186
169	187		### Public methods
170	188
171	189		### Protected methods
172	190
173	191		### Private methods
174	192
175	193		## Imaginary registers
176	194
177	195		### Storing imaginary registers
178	196
179	197		TRgObj stores the imaginary registers in list of TRegInfo structure.
180	198
181	199		### Life of imaginary register
182	200
183	201		Life of imaginary register starts when it is first used by assembler instruction. When it first appears in an assembler instruction in the assembler list for the specific routine. And ends when it is last used in an assembler instruction. In the TRegInfo structure for the specific imaginary register there are 2 fields for the life of the register. live_start: TAi; indicates which is the assembler instruction where the register is first used. live_end: TAi; indicates which is the assembler instruction where the register is last used.
184	202
185	203		## Interferences
186	204
187	205		Interferences
188	206
189	207		Call hierarchy
190	208
191		-	~~` generate_interference_graph`\~~
192		-	~~` add_edges_used(1, 2) get_alias add_edge`\~~
193		-	~~` add_edge ibitmap.s`~~
	209	+	```text
	210	+	generate_interference_graph
	211	+	add_edges_used(1, 2) get_alias add_edge
	212	+	add_edge ibitmap.s
	213	+	```
194	214
195	215		### generate_interference_graph
196	216
197	217		This method iterates the assembler list. Looking for reg_alloc instruction, with the proper regType.
198	218
199	219		During the iteration we keep all register that are live in list - live_registers. if its allocating it adds the superregister to the live_registers. if its dealloc it removes it from the live_registers.
200	220
201	221		After adding or removing in live_registers it calls add_edges_used
202	222
203	223		### add_edges_used
204	224
205	225		Iterates all live_registers and calls add_edge it gets the alias of the current live_register. and the super register u that is passed to the method.
206	226
207	227		### add_edge
208	228
209	229		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
210	230
211	231		``` pascal
212	232		reginfo[u].adjList.add(v);
213	233		reginfo[v].adjList.add(u);
214	234		ibitmap[v, u] := true;
215	235		ibitmap[u, v] := true;
216	236		```
217	237
218	238		In the relation between these 2 registers there is no dependant. There is no primary one. They are both equal in it.
219	239
220	240		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.
221	241
222	242		Interferences work with super registers.
223	243
224	244		## Backgrounds
225	245
226	246		### Grouping the instructions
227	247
228	248		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
229	249
230	250		\- Second group are instructions that move date from one place to another. Such as MOV, LAHF, POP, PUSH, LEA
231	251
232	252		\- Third group of instructions are those to compare data. They do not change the data. just check it. Such instructions are TEST, COMPARE
233	253
234	254		\- Fourth group of instructions are those who change the flow of the execution of the instructions such as: JMP, Jcc, JCXZ,
235	255
236	256		\- Fifth group are instructions that changes data based on other data like ADD
237	257
238	258		Another grouping of instructions could be by the cpu version where the instruction first appear.
239	259
240	260		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.
241	261
242	262		### Data in the instructions
243	263
244	264		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.
245	265
246	266		### Programming using the instructions
247	267
248	268		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.
249	269
250	270		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.
251	271
252	272		### Object Design guidelines
253	273
254	274		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.
255	275
256	276		In the
257	277
258	278		``` pascal
259	279		TRgObj.colour_registers
260	280		```
261	281
262	282		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.
263	283
264	284		Improvements can be made in the weights of the instructions. Or in the way the allocator decides which register to spill and which not.
265	285
266	286		---
267	287		From the Free Pascal wiki, page "The register allocator", as it stood on 2020-12-28 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