1	/* Assign reload pseudos.
2	Copyright (C) 2010-2023 Free Software Foundation, Inc.
3	Contributed by Vladimir Makarov <vmakarov@redhat.com>.
4
5	This file is part of GCC.
6
7	GCC is free software; you can redistribute it and/or modify it under
8	the terms of the GNU General Public License as published by the Free
9	Software Foundation; either version 3, or (at your option) any later
10	version.
11
12	GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13	WARRANTY; without even the implied warranty of MERCHANTABILITY or
14	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15	for more details.
16
17	You should have received a copy of the GNU General Public License
18	along with GCC; see the file COPYING3. If not see
19	<http://www.gnu.org/licenses/>. */
20
21
22	/* This file's main objective is to assign hard registers to reload
23	pseudos. It also tries to allocate hard registers to other
24	pseudos, but at a lower priority than the reload pseudos. The pass
25	does not transform the RTL.
26
27	We must allocate a hard register to every reload pseudo. We try to
28	increase the chances of finding a viable allocation by assigning
29	the pseudos in order of fewest available hard registers first. If
30	we still fail to find a hard register, we spill other (non-reload)
31	pseudos in order to make room.
32
33	find_hard_regno_for finds hard registers for allocation without
34	spilling. spill_for does the same with spilling. Both functions
35	use a cost model to determine the most profitable choice of hard
36	and spill registers.
37
38	Once we have finished allocating reload pseudos, we also try to
39	assign registers to other (non-reload) pseudos. This is useful if
40	hard registers were freed up by the spilling just described.
41
42	We try to assign hard registers by collecting pseudos into threads.
43	These threads contain reload and inheritance pseudos that are
44	connected by copies (move insns). Doing this improves the chances
45	of pseudos in the thread getting the same hard register and, as a
46	result, of allowing some move insns to be deleted.
47
48	When we assign a hard register to a pseudo, we decrease the cost of
49	using the same hard register for pseudos that are connected by
50	copies.
51
52	If two hard registers have the same frequency-derived cost, we
53	prefer hard registers with higher priorities. The mapping of
54	registers to priorities is controlled by the register_priority
55	target hook. For example, x86-64 has a few register priorities:
56	hard registers with and without REX prefixes have different
57	priorities. This permits us to generate smaller code as insns
58	without REX prefixes are shorter.
59
60	If a few hard registers are still equally good for the assignment,
61	we choose the least used hard register. It is called leveling and
62	may be profitable for some targets.
63
64	Only insns with changed allocation pseudos are processed on the
65	next constraint pass.
66
67	The pseudo live-ranges are used to find conflicting pseudos.
68
69	For understanding the code, it is important to keep in mind that
70	inheritance, split, and reload pseudos created since last
71	constraint pass have regno >= lra_constraint_new_regno_start.
72	Inheritance and split pseudos created on any pass are in the
73	corresponding bitmaps. Inheritance and split pseudos since the
74	last constraint pass have also the corresponding non-negative
75	restore_regno. */
76
77	#include "config.h"
78	#include "system.h"
79	#include "coretypes.h"
80	#include "backend.h"
81	#include "target.h"
82	#include "rtl.h"
83	#include "tree.h"
84	#include "predict.h"
85	#include "df.h"
86	#include "memmodel.h"
87	#include "tm_p.h"
88	#include "insn-config.h"
89	#include "regs.h"
90	#include "ira.h"
91	#include "recog.h"
92	#include "rtl-error.h"
93	#include "sparseset.h"
94	#include "lra.h"
95	#include "lra-int.h"
96	#include "function-abi.h"
97
98	/* Current iteration number of the pass and current iteration number
99	of the pass after the latest spill pass when any former reload
100	pseudo was spilled. */
101	int lra_assignment_iter;
102	int lra_assignment_iter_after_spill;
103
104	/* Flag of spilling former reload pseudos on this pass. */
105	static bool former_reload_pseudo_spill_p;
106
107	/* Array containing corresponding values of function
108	lra_get_allocno_class. It is used to speed up the code. */
109	static enum reg_class *regno_allocno_class_array;
110
111	/* Array containing lengths of pseudo live ranges. It is used to
112	speed up the code. */
113	static int *regno_live_length;
114
115	/* Information about the thread to which a pseudo belongs. Threads are
116	a set of connected reload and inheritance pseudos with the same set of
117	available hard registers. Lone registers belong to their own threads. */
118	struct regno_assign_info
119	{
120	/* First/next pseudo of the same thread. */
121	int first, next;
122	/* Frequency of the thread (execution frequency of only reload
123	pseudos in the thread when the thread contains a reload pseudo).
124	Defined only for the first thread pseudo. */
125	int freq;
126	};
127
128	/* Map regno to the corresponding regno assignment info. */
129	static struct regno_assign_info *regno_assign_info;
130
131	/* All inherited, subreg or optional pseudos created before last spill
132	sub-pass. Such pseudos are permitted to get memory instead of hard
133	regs. */
134	static bitmap_head non_reload_pseudos;
135
136	/* Process a pseudo copy with execution frequency COPY_FREQ connecting
137	REGNO1 and REGNO2 to form threads. */
138	static void
139	process_copy_to_form_thread (int regno1, int regno2, int copy_freq)
140	{
141	int last, regno1_first, regno2_first;
142
143	lra_assert (regno1 >= lra_constraint_new_regno_start
144	&& regno2 >= lra_constraint_new_regno_start);
145	regno1_first = regno_assign_info[regno1].first;
146	regno2_first = regno_assign_info[regno2].first;
147	if (regno1_first != regno2_first)
148	{
149	for (last = regno2_first;
150	regno_assign_info[last].next >= 0;
151	last = regno_assign_info[last].next)
152	regno_assign_info[last].first = regno1_first;
153	regno_assign_info[last].first = regno1_first;
154	regno_assign_info[last].next = regno_assign_info[regno1_first].next;
155	regno_assign_info[regno1_first].next = regno2_first;
156	regno_assign_info[regno1_first].freq
157	+= regno_assign_info[regno2_first].freq;
158	}
159	regno_assign_info[regno1_first].freq -= 2 * copy_freq;
160	lra_assert (regno_assign_info[regno1_first].freq >= 0);
161	}
162
163	/* Initialize REGNO_ASSIGN_INFO and form threads. */
164	static void
165	init_regno_assign_info (void)
166	{
167	int i, regno1, regno2, max_regno = max_reg_num ();
168	lra_copy_t cp;
169
170	regno_assign_info = XNEWVEC (struct regno_assign_info, max_regno);
171	for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
172	{
173	regno_assign_info[i].first = i;
174	regno_assign_info[i].next = -1;
175	regno_assign_info[i].freq = lra_reg_info[i].freq;
176	}
177	/* Form the threads. */
178	for (i = 0; (cp = lra_get_copy (i)) != NULL; i++)
179	if ((regno1 = cp->regno1) >= lra_constraint_new_regno_start
180	&& (regno2 = cp->regno2) >= lra_constraint_new_regno_start
181	&& reg_renumber[regno1] < 0 && lra_reg_info[regno1].nrefs != 0
182	&& reg_renumber[regno2] < 0 && lra_reg_info[regno2].nrefs != 0
183	&& (ira_class_hard_regs_num[regno_allocno_class_array[regno1]]
184	== ira_class_hard_regs_num[regno_allocno_class_array[regno2]]))
185	process_copy_to_form_thread (regno1, regno2, copy_freq: cp->freq);
186	}
187
188	/* Free REGNO_ASSIGN_INFO. */
189	static void
190	finish_regno_assign_info (void)
191	{
192	free (ptr: regno_assign_info);
193	}
194
195	/* The function is used to sort *reload* and *inheritance* pseudos to
196	try to assign them hard registers. We put pseudos from the same
197	thread always nearby. */
198	static int
199	reload_pseudo_compare_func (const void *v1p, const void *v2p)
200	{
201	int r1 = *(const int *) v1p, r2 = *(const int *) v2p;
202	enum reg_class cl1 = regno_allocno_class_array[r1];
203	enum reg_class cl2 = regno_allocno_class_array[r2];
204	int diff;
205
206	lra_assert (r1 >= lra_constraint_new_regno_start
207	&& r2 >= lra_constraint_new_regno_start);
208
209	/* Prefer to assign reload registers with smaller classes first to
210	guarantee assignment to all reload registers. */
211	if ((diff = (ira_class_hard_regs_num[cl1]
212	- ira_class_hard_regs_num[cl2])) != 0)
213	return diff;
214	/* Allocate bigger pseudos first to avoid register file
215	fragmentation. */
216	if ((diff
217	= (ira_reg_class_max_nregs[cl2][lra_reg_info[r2].biggest_mode]
218	- ira_reg_class_max_nregs[cl1][lra_reg_info[r1].biggest_mode])) != 0)
219	return diff;
220	if ((diff = (regno_assign_info[regno_assign_info[r2].first].freq
221	- regno_assign_info[regno_assign_info[r1].first].freq)) != 0)
222	return diff;
223	/* Put pseudos from the thread nearby. */
224	if ((diff = regno_assign_info[r1].first - regno_assign_info[r2].first) != 0)
225	return diff;
226	/* Prefer pseudos with longer live ranges. It sets up better
227	prefered hard registers for the thread pseudos and decreases
228	register-register moves between the thread pseudos. */
229	if ((diff = regno_live_length[r2] - regno_live_length[r1]) != 0)
230	return diff;
231	/* If regs are equally good, sort by their numbers, so that the
232	results of qsort leave nothing to chance. */
233	return r1 - r2;
234	}
235
236	/* The function is used to sort *non-reload* pseudos to try to assign
237	them hard registers. The order calculation is simpler than in the
238	previous function and based on the pseudo frequency usage. */
239	static int
240	pseudo_compare_func (const void *v1p, const void *v2p)
241	{
242	int r1 = *(const int *) v1p, r2 = *(const int *) v2p;
243	int diff;
244
245	/* Assign hard reg to static chain pointer first pseudo when
246	non-local goto is used. */
247	if ((diff = (non_spilled_static_chain_regno_p (regno: r2)
248	- non_spilled_static_chain_regno_p (regno: r1))) != 0)
249	return diff;
250
251	/* Prefer to assign more frequently used registers first. */
252	if ((diff = lra_reg_info[r2].freq - lra_reg_info[r1].freq) != 0)
253	return diff;
254
255	/* If regs are equally good, sort by their numbers, so that the
256	results of qsort leave nothing to chance. */
257	return r1 - r2;
258	}
259
260	/* Arrays of size LRA_LIVE_MAX_POINT mapping a program point to the
261	pseudo live ranges with given start point. We insert only live
262	ranges of pseudos interesting for assignment purposes. They are
263	reload pseudos and pseudos assigned to hard registers. */
264	static lra_live_range_t *start_point_ranges;
265
266	/* Used as a flag that a live range is not inserted in the start point
267	chain. */
268	static struct lra_live_range not_in_chain_mark;
269
270	/* Create and set up START_POINT_RANGES. */
271	static void
272	create_live_range_start_chains (void)
273	{
274	int i, max_regno;
275	lra_live_range_t r;
276
277	start_point_ranges = XCNEWVEC (lra_live_range_t, lra_live_max_point);
278	max_regno = max_reg_num ();
279	for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
280	if (i >= lra_constraint_new_regno_start || reg_renumber[i] >= 0)
281	{
282	for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
283	{
284	r->start_next = start_point_ranges[r->start];
285	start_point_ranges[r->start] = r;
286	}
287	}
288	else
289	{
290	for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
291	r->start_next = &not_in_chain_mark;
292	}
293	}
294
295	/* Insert live ranges of pseudo REGNO into start chains if they are
296	not there yet. */
297	static void
298	insert_in_live_range_start_chain (int regno)
299	{
300	lra_live_range_t r = lra_reg_info[regno].live_ranges;
301
302	if (r->start_next != &not_in_chain_mark)
303	return;
304	for (; r != NULL; r = r->next)
305	{
306	r->start_next = start_point_ranges[r->start];
307	start_point_ranges[r->start] = r;
308	}
309	}
310
311	/* Free START_POINT_RANGES. */
312	static void
313	finish_live_range_start_chains (void)
314	{
315	gcc_assert (start_point_ranges != NULL);
316	free (ptr: start_point_ranges);
317	start_point_ranges = NULL;
318	}
319
320	/* Map: program point -> bitmap of all pseudos living at the point and
321	assigned to hard registers. */
322	static bitmap_head *live_hard_reg_pseudos;
323	static bitmap_obstack live_hard_reg_pseudos_bitmap_obstack;
324
325	/* reg_renumber corresponding to pseudos marked in
326	live_hard_reg_pseudos. reg_renumber might be not matched to
327	live_hard_reg_pseudos but live_pseudos_reg_renumber always reflects
328	live_hard_reg_pseudos. */
329	static int *live_pseudos_reg_renumber;
330
331	/* Sparseset used to calculate living hard reg pseudos for some program
332	point range. */
333	static sparseset live_range_hard_reg_pseudos;
334
335	/* Sparseset used to calculate living reload/inheritance pseudos for
336	some program point range. */
337	static sparseset live_range_reload_inheritance_pseudos;
338
339	/* Allocate and initialize the data about living pseudos at program
340	points. */
341	static void
342	init_lives (void)
343	{
344	int i, max_regno = max_reg_num ();
345
346	live_range_hard_reg_pseudos = sparseset_alloc (n_elms: max_regno);
347	live_range_reload_inheritance_pseudos = sparseset_alloc (n_elms: max_regno);
348	live_hard_reg_pseudos = XNEWVEC (bitmap_head, lra_live_max_point);
349	bitmap_obstack_initialize (&live_hard_reg_pseudos_bitmap_obstack);
350	for (i = 0; i < lra_live_max_point; i++)
351	bitmap_initialize (head: &live_hard_reg_pseudos[i],
352	obstack: &live_hard_reg_pseudos_bitmap_obstack);
353	live_pseudos_reg_renumber = XNEWVEC (int, max_regno);
354	for (i = 0; i < max_regno; i++)
355	live_pseudos_reg_renumber[i] = -1;
356	}
357
358	/* Free the data about living pseudos at program points. */
359	static void
360	finish_lives (void)
361	{
362	sparseset_free (live_range_hard_reg_pseudos);
363	sparseset_free (live_range_reload_inheritance_pseudos);
364	free (ptr: live_hard_reg_pseudos);
365	bitmap_obstack_release (&live_hard_reg_pseudos_bitmap_obstack);
366	free (ptr: live_pseudos_reg_renumber);
367	}
368
369	/* Update the LIVE_HARD_REG_PSEUDOS and LIVE_PSEUDOS_REG_RENUMBER
370	entries for pseudo REGNO. Assume that the register has been
371	spilled if FREE_P, otherwise assume that it has been assigned
372	reg_renumber[REGNO] (if >= 0). We also insert the pseudo live
373	ranges in the start chains when it is assumed to be assigned to a
374	hard register because we use the chains of pseudos assigned to hard
375	registers during allocation. */
376	static void
377	update_lives (int regno, bool free_p)
378	{
379	int p;
380	lra_live_range_t r;
381
382	if (reg_renumber[regno] < 0)
383	return;
384	live_pseudos_reg_renumber[regno] = free_p ? -1 : reg_renumber[regno];
385	for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
386	{
387	for (p = r->start; p <= r->finish; p++)
388	if (free_p)
389	bitmap_clear_bit (&live_hard_reg_pseudos[p], regno);
390	else
391	{
392	bitmap_set_bit (&live_hard_reg_pseudos[p], regno);
393	insert_in_live_range_start_chain (regno);
394	}
395	}
396	}
397
398	/* Sparseset used to calculate reload pseudos conflicting with a given
399	pseudo when we are trying to find a hard register for the given
400	pseudo. */
401	static sparseset conflict_reload_and_inheritance_pseudos;
402
403	/* Map: program point -> bitmap of all reload and inheritance pseudos
404	living at the point. */
405	static bitmap_head *live_reload_and_inheritance_pseudos;
406	static bitmap_obstack live_reload_and_inheritance_pseudos_bitmap_obstack;
407
408	/* Allocate and initialize data about living reload pseudos at any
409	given program point. */
410	static void
411	init_live_reload_and_inheritance_pseudos (void)
412	{
413	int i, p, max_regno = max_reg_num ();
414	lra_live_range_t r;
415
416	conflict_reload_and_inheritance_pseudos = sparseset_alloc (n_elms: max_regno);
417	live_reload_and_inheritance_pseudos = XNEWVEC (bitmap_head, lra_live_max_point);
418	bitmap_obstack_initialize (&live_reload_and_inheritance_pseudos_bitmap_obstack);
419	for (p = 0; p < lra_live_max_point; p++)
420	bitmap_initialize (head: &live_reload_and_inheritance_pseudos[p],
421	obstack: &live_reload_and_inheritance_pseudos_bitmap_obstack);
422	for (i = lra_constraint_new_regno_start; i < max_regno; i++)
423	{
424	for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
425	for (p = r->start; p <= r->finish; p++)
426	bitmap_set_bit (&live_reload_and_inheritance_pseudos[p], i);
427	}
428	}
429
430	/* Finalize data about living reload pseudos at any given program
431	point. */
432	static void
433	finish_live_reload_and_inheritance_pseudos (void)
434	{
435	sparseset_free (conflict_reload_and_inheritance_pseudos);
436	free (ptr: live_reload_and_inheritance_pseudos);
437	bitmap_obstack_release (&live_reload_and_inheritance_pseudos_bitmap_obstack);
438	}
439
440	/* The value used to check that cost of given hard reg is really
441	defined currently. */
442	static int curr_hard_regno_costs_check = 0;
443	/* Array used to check that cost of the corresponding hard reg (the
444	array element index) is really defined currently. */
445	static int hard_regno_costs_check[FIRST_PSEUDO_REGISTER];
446	/* The current costs of allocation of hard regs. Defined only if the
447	value of the corresponding element of the previous array is equal to
448	CURR_HARD_REGNO_COSTS_CHECK. */
449	static int hard_regno_costs[FIRST_PSEUDO_REGISTER];
450
451	/* Adjust cost of HARD_REGNO by INCR. Reset the cost first if it is
452	not defined yet. */
453	static inline void
454	adjust_hard_regno_cost (int hard_regno, int incr)
455	{
456	if (hard_regno_costs_check[hard_regno] != curr_hard_regno_costs_check)
457	hard_regno_costs[hard_regno] = 0;
458	hard_regno_costs_check[hard_regno] = curr_hard_regno_costs_check;
459	hard_regno_costs[hard_regno] += incr;
460	}
461
462	/* Try to find a free hard register for pseudo REGNO. Return the
463	hard register on success and set *COST to the cost of using
464	that register. (If several registers have equal cost, the one with
465	the highest priority wins.) Return -1 on failure.
466
467	If FIRST_P, return the first available hard reg ignoring other
468	criteria, e.g. allocation cost. This approach results in less hard
469	reg pool fragmentation and permit to allocate hard regs to reload
470	pseudos in complicated situations where pseudo sizes are different.
471
472	If TRY_ONLY_HARD_REGNO >= 0, consider only that hard register,
473	otherwise consider all hard registers in REGNO's class.
474
475	If REGNO_SET is not empty, only hard registers from the set are
476	considered. */
477	static int
478	find_hard_regno_for_1 (int regno, int *cost, int try_only_hard_regno,
479	bool first_p, HARD_REG_SET regno_set)
480	{
481	HARD_REG_SET conflict_set;
482	int best_cost = INT_MAX, best_priority = INT_MIN, best_usage = INT_MAX;
483	lra_live_range_t r;
484	int p, i, j, rclass_size, best_hard_regno, priority, hard_regno;
485	int hr, conflict_hr, nregs;
486	machine_mode biggest_mode;
487	unsigned int k, conflict_regno;
488	poly_int64 offset;
489	int val, biggest_nregs, nregs_diff;
490	enum reg_class rclass;
491	bitmap_iterator bi;
492	bool *rclass_intersect_p;
493	HARD_REG_SET impossible_start_hard_regs, available_regs;
494
495	if (hard_reg_set_empty_p (x: regno_set))
496	conflict_set = lra_no_alloc_regs;
497	else
498	conflict_set = ~regno_set | lra_no_alloc_regs;
499	rclass = regno_allocno_class_array[regno];
500	rclass_intersect_p = ira_reg_classes_intersect_p[rclass];
501	curr_hard_regno_costs_check++;
502	sparseset_clear (s: conflict_reload_and_inheritance_pseudos);
503	sparseset_clear (s: live_range_hard_reg_pseudos);
504	conflict_set |= lra_reg_info[regno].conflict_hard_regs;
505	biggest_mode = lra_reg_info[regno].biggest_mode;
506	for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
507	{
508	EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
509	if (rclass_intersect_p[regno_allocno_class_array[k]])
510	sparseset_set_bit (s: live_range_hard_reg_pseudos, e: k);
511	EXECUTE_IF_SET_IN_BITMAP (&live_reload_and_inheritance_pseudos[r->start],
512	0, k, bi)
513	if (lra_reg_info[k].preferred_hard_regno1 >= 0
514	&& live_pseudos_reg_renumber[k] < 0
515	&& rclass_intersect_p[regno_allocno_class_array[k]])
516	sparseset_set_bit (s: conflict_reload_and_inheritance_pseudos, e: k);
517	for (p = r->start + 1; p <= r->finish; p++)
518	{
519	lra_live_range_t r2;
520
521	for (r2 = start_point_ranges[p];
522	r2 != NULL;
523	r2 = r2->start_next)
524	{
525	if (live_pseudos_reg_renumber[r2->regno] < 0
526	&& r2->regno >= lra_constraint_new_regno_start
527	&& lra_reg_info[r2->regno].preferred_hard_regno1 >= 0
528	&& rclass_intersect_p[regno_allocno_class_array[r2->regno]])
529	sparseset_set_bit (s: conflict_reload_and_inheritance_pseudos,
530	e: r2->regno);
531	else if (live_pseudos_reg_renumber[r2->regno] >= 0
532	&& rclass_intersect_p
533	[regno_allocno_class_array[r2->regno]])
534	sparseset_set_bit (s: live_range_hard_reg_pseudos, e: r2->regno);
535	}
536	}
537	}
538	if ((hard_regno = lra_reg_info[regno].preferred_hard_regno1) >= 0)
539	{
540	adjust_hard_regno_cost
541	(hard_regno, incr: -lra_reg_info[regno].preferred_hard_regno_profit1);
542	if ((hard_regno = lra_reg_info[regno].preferred_hard_regno2) >= 0)
543	adjust_hard_regno_cost
544	(hard_regno, incr: -lra_reg_info[regno].preferred_hard_regno_profit2);
545	}
546	#ifdef STACK_REGS
547	if (lra_reg_info[regno].no_stack_p)
548	for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
549	SET_HARD_REG_BIT (set&: conflict_set, bit: i);
550	#endif
551	sparseset_clear_bit (conflict_reload_and_inheritance_pseudos, regno);
552	val = lra_reg_info[regno].val;
553	offset = lra_reg_info[regno].offset;
554	impossible_start_hard_regs = lra_reg_info[regno].exclude_start_hard_regs;
555	EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
556	{
557	conflict_hr = live_pseudos_reg_renumber[conflict_regno];
558	if (lra_reg_val_equal_p (regno: conflict_regno, val, offset))
559	{
560	conflict_hr = live_pseudos_reg_renumber[conflict_regno];
561	nregs = hard_regno_nregs (regno: conflict_hr,
562	mode: lra_reg_info[conflict_regno].biggest_mode);
563	/* Remember about multi-register pseudos. For example, 2
564	hard register pseudos can start on the same hard register
565	but cannot start on HR and HR+1/HR-1. */
566	for (hr = conflict_hr + 1;
567	hr < FIRST_PSEUDO_REGISTER && hr < conflict_hr + nregs;
568	hr++)
569	SET_HARD_REG_BIT (set&: impossible_start_hard_regs, bit: hr);
570	for (hr = conflict_hr - 1;
571	hr >= 0 && (int) end_hard_regno (mode: biggest_mode, regno: hr) > conflict_hr;
572	hr--)
573	SET_HARD_REG_BIT (set&: impossible_start_hard_regs, bit: hr);
574	}
575	else
576	{
577	machine_mode biggest_conflict_mode
578	= lra_reg_info[conflict_regno].biggest_mode;
579	int biggest_conflict_nregs
580	= hard_regno_nregs (regno: conflict_hr, mode: biggest_conflict_mode);
581
582	nregs_diff
583	= (biggest_conflict_nregs
584	- hard_regno_nregs (regno: conflict_hr,
585	PSEUDO_REGNO_MODE (conflict_regno)));
586	add_to_hard_reg_set (regs: &conflict_set,
587	mode: biggest_conflict_mode,
588	regno: conflict_hr
589	- (WORDS_BIG_ENDIAN ? nregs_diff : 0));
590	if (hard_reg_set_subset_p (reg_class_contents[rclass],
591	y: conflict_set))
592	return -1;
593	}
594	}
595	EXECUTE_IF_SET_IN_SPARSESET (conflict_reload_and_inheritance_pseudos,
596	conflict_regno)
597	if (!lra_reg_val_equal_p (regno: conflict_regno, val, offset))
598	{
599	lra_assert (live_pseudos_reg_renumber[conflict_regno] < 0);
600	if ((hard_regno
601	= lra_reg_info[conflict_regno].preferred_hard_regno1) >= 0)
602	{
603	adjust_hard_regno_cost
604	(hard_regno,
605	incr: lra_reg_info[conflict_regno].preferred_hard_regno_profit1);
606	if ((hard_regno
607	= lra_reg_info[conflict_regno].preferred_hard_regno2) >= 0)
608	adjust_hard_regno_cost
609	(hard_regno,
610	incr: lra_reg_info[conflict_regno].preferred_hard_regno_profit2);
611	}
612	}
613	/* Make sure that all registers in a multi-word pseudo belong to the
614	required class. */
615	conflict_set |= ~reg_class_contents[rclass];
616	lra_assert (rclass != NO_REGS);
617	rclass_size = ira_class_hard_regs_num[rclass];
618	best_hard_regno = -1;
619	hard_regno = ira_class_hard_regs[rclass][0];
620	biggest_nregs = hard_regno_nregs (regno: hard_regno, mode: biggest_mode);
621	nregs_diff = (biggest_nregs
622	- hard_regno_nregs (regno: hard_regno, PSEUDO_REGNO_MODE (regno)));
623	available_regs = reg_class_contents[rclass] & ~lra_no_alloc_regs;
624	for (i = 0; i < rclass_size; i++)
625	{
626	if (try_only_hard_regno >= 0)
627	hard_regno = try_only_hard_regno;
628	else
629	hard_regno = ira_class_hard_regs[rclass][i];
630	if (! overlaps_hard_reg_set_p (regs: conflict_set,
631	PSEUDO_REGNO_MODE (regno), regno: hard_regno)
632	&& targetm.hard_regno_mode_ok (hard_regno,
633	PSEUDO_REGNO_MODE (regno))
634	/* We cannot use prohibited_class_mode_regs for all classes
635	because it is not defined for all classes. */
636	&& (ira_allocno_class_translate[rclass] != rclass
637	|| ! TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs
638	[rclass][PSEUDO_REGNO_MODE (regno)],
639	bit: hard_regno))
640	&& ! TEST_HARD_REG_BIT (set: impossible_start_hard_regs, bit: hard_regno)
641	&& (nregs_diff == 0
642	|| (WORDS_BIG_ENDIAN
643	? (hard_regno - nregs_diff >= 0
644	&& TEST_HARD_REG_BIT (set: available_regs,
645	bit: hard_regno - nregs_diff))
646	: TEST_HARD_REG_BIT (set: available_regs,
647	bit: hard_regno + nregs_diff))))
648	{
649	if (hard_regno_costs_check[hard_regno]
650	!= curr_hard_regno_costs_check)
651	{
652	hard_regno_costs_check[hard_regno] = curr_hard_regno_costs_check;
653	hard_regno_costs[hard_regno] = 0;
654	}
655	for (j = 0;
656	j < hard_regno_nregs (regno: hard_regno, PSEUDO_REGNO_MODE (regno));
657	j++)
658	if (! crtl->abi->clobbers_full_reg_p (regno: hard_regno + j)
659	&& ! df_regs_ever_live_p (hard_regno + j))
660	/* It needs save restore. */
661	hard_regno_costs[hard_regno]
662	+= (2
663	* REG_FREQ_FROM_BB (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb)
664	+ 1);
665	priority = targetm.register_priority (hard_regno);
666	if (best_hard_regno < 0 || hard_regno_costs[hard_regno] < best_cost
667	|| (hard_regno_costs[hard_regno] == best_cost
668	&& (priority > best_priority
669	|| (targetm.register_usage_leveling_p ()
670	&& priority == best_priority
671	&& best_usage > lra_hard_reg_usage[hard_regno]))))
672	{
673	best_hard_regno = hard_regno;
674	best_cost = hard_regno_costs[hard_regno];
675	best_priority = priority;
676	best_usage = lra_hard_reg_usage[hard_regno];
677	}
678	}
679	if (try_only_hard_regno >= 0 || (first_p && best_hard_regno >= 0))
680	break;
681	}
682	if (best_hard_regno >= 0)
683	*cost = best_cost - lra_reg_info[regno].freq;
684	return best_hard_regno;
685	}
686
687	/* A wrapper for find_hard_regno_for_1 (see comments for that function
688	description). This function tries to find a hard register for
689	preferred class first if it is worth. */
690	static int
691	find_hard_regno_for (int regno, int *cost, int try_only_hard_regno, bool first_p)
692	{
693	int hard_regno;
694	HARD_REG_SET regno_set;
695
696	/* Only original pseudos can have a different preferred class. */
697	if (try_only_hard_regno < 0 && regno < lra_new_regno_start)
698	{
699	enum reg_class pref_class = reg_preferred_class (regno);
700
701	if (regno_allocno_class_array[regno] != pref_class)
702	{
703	hard_regno = find_hard_regno_for_1 (regno, cost, try_only_hard_regno: -1, first_p,
704	reg_class_contents[pref_class]);
705	if (hard_regno >= 0)
706	return hard_regno;
707	}
708	}
709	CLEAR_HARD_REG_SET (set&: regno_set);
710	return find_hard_regno_for_1 (regno, cost, try_only_hard_regno, first_p,
711	regno_set);
712	}
713
714	/* Current value used for checking elements in
715	update_hard_regno_preference_check. */
716	static int curr_update_hard_regno_preference_check;
717	/* If an element value is equal to the above variable value, then the
718	corresponding regno has been processed for preference
719	propagation. */
720	static int *update_hard_regno_preference_check;
721
722	/* Update the preference for using HARD_REGNO for pseudos that are
723	connected directly or indirectly with REGNO. Apply divisor DIV
724	to any preference adjustments.
725
726	The more indirectly a pseudo is connected, the smaller its effect
727	should be. We therefore increase DIV on each "hop". */
728	static void
729	update_hard_regno_preference (int regno, int hard_regno, int div)
730	{
731	int another_regno, cost;
732	lra_copy_t cp, next_cp;
733
734	/* Search depth 5 seems to be enough. */
735	if (div > (1 << 5))
736	return;
737	for (cp = lra_reg_info[regno].copies; cp != NULL; cp = next_cp)
738	{
739	if (cp->regno1 == regno)
740	{
741	next_cp = cp->regno1_next;
742	another_regno = cp->regno2;
743	}
744	else if (cp->regno2 == regno)
745	{
746	next_cp = cp->regno2_next;
747	another_regno = cp->regno1;
748	}
749	else
750	gcc_unreachable ();
751	if (reg_renumber[another_regno] < 0
752	&& (update_hard_regno_preference_check[another_regno]
753	!= curr_update_hard_regno_preference_check))
754	{
755	update_hard_regno_preference_check[another_regno]
756	= curr_update_hard_regno_preference_check;
757	cost = cp->freq < div ? 1 : cp->freq / div;
758	lra_setup_reload_pseudo_preferenced_hard_reg
759	(another_regno, hard_regno, cost);
760	update_hard_regno_preference (regno: another_regno, hard_regno, div: div * 2);
761	}
762	}
763	}
764
765	/* Return prefix title for pseudo REGNO. */
766	static const char *
767	pseudo_prefix_title (int regno)
768	{
769	return
770	(regno < lra_constraint_new_regno_start ? ""
771	: bitmap_bit_p (&lra_inheritance_pseudos, regno) ? "inheritance "
772	: bitmap_bit_p (&lra_split_regs, regno) ? "split "
773	: bitmap_bit_p (&lra_optional_reload_pseudos, regno) ? "optional reload "
774	: bitmap_bit_p (&lra_subreg_reload_pseudos, regno) ? "subreg reload "
775	: "reload ");
776	}
777
778	/* Update REG_RENUMBER and other pseudo preferences by assignment of
779	HARD_REGNO to pseudo REGNO and print about it if PRINT_P. */
780	void
781	lra_setup_reg_renumber (int regno, int hard_regno, bool print_p)
782	{
783	int i, hr;
784
785	/* We cannot just reassign hard register. */
786	lra_assert (hard_regno < 0 || reg_renumber[regno] < 0);
787	if ((hr = hard_regno) < 0)
788	hr = reg_renumber[regno];
789	reg_renumber[regno] = hard_regno;
790	lra_assert (hr >= 0);
791	for (i = 0; i < hard_regno_nregs (regno: hr, PSEUDO_REGNO_MODE (regno)); i++)
792	if (hard_regno < 0)
793	lra_hard_reg_usage[hr + i] -= lra_reg_info[regno].freq;
794	else
795	lra_hard_reg_usage[hr + i] += lra_reg_info[regno].freq;
796	if (print_p && lra_dump_file != NULL)
797	fprintf (stream: lra_dump_file, format: " Assign %d to %sr%d (freq=%d)\n",
798	reg_renumber[regno], pseudo_prefix_title (regno),
799	regno, lra_reg_info[regno].freq);
800	if (hard_regno >= 0)
801	{
802	curr_update_hard_regno_preference_check++;
803	update_hard_regno_preference (regno, hard_regno, div: 1);
804	}
805	}
806
807	/* Pseudos which occur in insns containing a particular pseudo. */
808	static bitmap_head insn_conflict_pseudos;
809
810	/* Bitmaps used to contain spill pseudos for given pseudo hard regno
811	and best spill pseudos for given pseudo (and best hard regno). */
812	static bitmap_head spill_pseudos_bitmap, best_spill_pseudos_bitmap;
813
814	/* Current pseudo check for validity of elements in
815	TRY_HARD_REG_PSEUDOS. */
816	static int curr_pseudo_check;
817	/* Array used for validity of elements in TRY_HARD_REG_PSEUDOS. */
818	static int try_hard_reg_pseudos_check[FIRST_PSEUDO_REGISTER];
819	/* Pseudos who hold given hard register at the considered points. */
820	static bitmap_head try_hard_reg_pseudos[FIRST_PSEUDO_REGISTER];
821
822	/* Set up try_hard_reg_pseudos for given program point P and class
823	RCLASS. Those are pseudos living at P and assigned to a hard
824	register of RCLASS. In other words, those are pseudos which can be
825	spilled to assign a hard register of RCLASS to a pseudo living at
826	P. */
827	static void
828	setup_try_hard_regno_pseudos (int p, enum reg_class rclass)
829	{
830	int i, hard_regno;
831	machine_mode mode;
832	unsigned int spill_regno;
833	bitmap_iterator bi;
834
835	/* Find what pseudos could be spilled. */
836	EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[p], 0, spill_regno, bi)
837	{
838	mode = PSEUDO_REGNO_MODE (spill_regno);
839	hard_regno = live_pseudos_reg_renumber[spill_regno];
840	if (overlaps_hard_reg_set_p (reg_class_contents[rclass],
841	mode, regno: hard_regno))
842	{
843	for (i = hard_regno_nregs (regno: hard_regno, mode) - 1; i >= 0; i--)
844	{
845	if (try_hard_reg_pseudos_check[hard_regno + i]
846	!= curr_pseudo_check)
847	{
848	try_hard_reg_pseudos_check[hard_regno + i]
849	= curr_pseudo_check;
850	bitmap_clear (&try_hard_reg_pseudos[hard_regno + i]);
851	}
852	bitmap_set_bit (&try_hard_reg_pseudos[hard_regno + i],
853	spill_regno);
854	}
855	}
856	}
857	}
858
859	/* Assign temporarily HARD_REGNO to pseudo REGNO. Temporary
860	assignment means that we might undo the data change. */
861	static void
862	assign_temporarily (int regno, int hard_regno)
863	{
864	int p;
865	lra_live_range_t r;
866
867	for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
868	{
869	for (p = r->start; p <= r->finish; p++)
870	if (hard_regno < 0)
871	bitmap_clear_bit (&live_hard_reg_pseudos[p], regno);
872	else
873	{
874	bitmap_set_bit (&live_hard_reg_pseudos[p], regno);
875	insert_in_live_range_start_chain (regno);
876	}
877	}
878	live_pseudos_reg_renumber[regno] = hard_regno;
879	}
880
881	/* Return true iff there is a reason why pseudo SPILL_REGNO should not
882	be spilled. */
883	static bool
884	must_not_spill_p (unsigned spill_regno)
885	{
886	if ((pic_offset_table_rtx != NULL
887	&& spill_regno == REGNO (pic_offset_table_rtx))
888	|| ((int) spill_regno >= lra_constraint_new_regno_start
889	&& ! bitmap_bit_p (&lra_inheritance_pseudos, spill_regno)
890	&& ! bitmap_bit_p (&lra_split_regs, spill_regno)
891	&& ! bitmap_bit_p (&lra_subreg_reload_pseudos, spill_regno)
892	&& ! bitmap_bit_p (&lra_optional_reload_pseudos, spill_regno)))
893	return true;
894	/* A reload pseudo that requires a singleton register class should
895	not be spilled.
896	FIXME: this mitigates the issue on certain i386 patterns, but
897	does not solve the general case where existing reloads fully
898	cover a limited register class. */
899	if (!bitmap_bit_p (&non_reload_pseudos, spill_regno)
900	&& reg_class_size [reg_preferred_class (spill_regno)] == 1
901	&& reg_alternate_class (spill_regno) == NO_REGS)
902	return true;
903	return false;
904	}
905
906	/* Array used for sorting reload pseudos for subsequent allocation
907	after spilling some pseudo. */
908	static int *sorted_reload_pseudos;
909
910	/* Spill some pseudos for a reload pseudo REGNO and return hard
911	register which should be used for pseudo after spilling. The
912	function adds spilled pseudos to SPILLED_PSEUDO_BITMAP. When we
913	choose hard register (and pseudos occupying the hard registers and
914	to be spilled), we take into account not only how REGNO will
915	benefit from the spills but also how other reload pseudos not yet
916	assigned to hard registers benefit from the spills too. In very
917	rare cases, the function can fail and return -1.
918
919	If FIRST_P, return the first available hard reg ignoring other
920	criteria, e.g. allocation cost and cost of spilling non-reload
921	pseudos. This approach results in less hard reg pool fragmentation
922	and permit to allocate hard regs to reload pseudos in complicated
923	situations where pseudo sizes are different. */
924	static int
925	spill_for (int regno, bitmap spilled_pseudo_bitmap, bool first_p)
926	{
927	int i, j, n, p, hard_regno, best_hard_regno, cost, best_cost, rclass_size;
928	int reload_hard_regno, reload_cost;
929	bool static_p, best_static_p;
930	machine_mode mode;
931	enum reg_class rclass;
932	unsigned int spill_regno, reload_regno, uid;
933	int insn_pseudos_num, best_insn_pseudos_num;
934	int bad_spills_num, smallest_bad_spills_num;
935	lra_live_range_t r;
936	bitmap_iterator bi;
937
938	rclass = regno_allocno_class_array[regno];
939	lra_assert (reg_renumber[regno] < 0 && rclass != NO_REGS);
940	bitmap_clear (&insn_conflict_pseudos);
941	bitmap_clear (&best_spill_pseudos_bitmap);
942	EXECUTE_IF_SET_IN_BITMAP (&lra_reg_info[regno].insn_bitmap, 0, uid, bi)
943	{
944	struct lra_insn_reg *ir;
945
946	for (ir = lra_get_insn_regs (uid); ir != NULL; ir = ir->next)
947	if (ir->regno >= FIRST_PSEUDO_REGISTER)
948	bitmap_set_bit (&insn_conflict_pseudos, ir->regno);
949	}
950	best_hard_regno = -1;
951	best_cost = INT_MAX;
952	best_static_p = true;
953	best_insn_pseudos_num = INT_MAX;
954	smallest_bad_spills_num = INT_MAX;
955	rclass_size = ira_class_hard_regs_num[rclass];
956	mode = PSEUDO_REGNO_MODE (regno);
957	/* Invalidate try_hard_reg_pseudos elements. */
958	curr_pseudo_check++;
959	for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
960	for (p = r->start; p <= r->finish; p++)
961	setup_try_hard_regno_pseudos (p, rclass);
962	for (i = 0; i < rclass_size; i++)
963	{
964	hard_regno = ira_class_hard_regs[rclass][i];
965	bitmap_clear (&spill_pseudos_bitmap);
966	for (j = hard_regno_nregs (regno: hard_regno, mode) - 1; j >= 0; j--)
967	{
968	if (hard_regno + j >= FIRST_PSEUDO_REGISTER)
969	break;
970	if (try_hard_reg_pseudos_check[hard_regno + j] != curr_pseudo_check)
971	continue;
972	lra_assert (!bitmap_empty_p (&try_hard_reg_pseudos[hard_regno + j]));
973	bitmap_ior_into (&spill_pseudos_bitmap,
974	&try_hard_reg_pseudos[hard_regno + j]);
975	}
976	/* Spill pseudos. */
977	static_p = false;
978	EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
979	if (must_not_spill_p (spill_regno))
980	goto fail;
981	else if (non_spilled_static_chain_regno_p (regno: spill_regno))
982	static_p = true;
983	insn_pseudos_num = 0;
984	bad_spills_num = 0;
985	if (lra_dump_file != NULL)
986	fprintf (stream: lra_dump_file, format: " Trying %d:", hard_regno);
987	sparseset_clear (s: live_range_reload_inheritance_pseudos);
988	EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
989	{
990	if (bitmap_bit_p (&insn_conflict_pseudos, spill_regno))
991	insn_pseudos_num++;
992	if (spill_regno >= (unsigned int) lra_bad_spill_regno_start)
993	bad_spills_num++;
994	for (r = lra_reg_info[spill_regno].live_ranges;
995	r != NULL;
996	r = r->next)
997	{
998	for (p = r->start; p <= r->finish; p++)
999	{
1000	lra_live_range_t r2;
1001
1002	for (r2 = start_point_ranges[p];
1003	r2 != NULL;
1004	r2 = r2->start_next)
1005	if (r2->regno >= lra_constraint_new_regno_start)
1006	sparseset_set_bit (s: live_range_reload_inheritance_pseudos,
1007	e: r2->regno);
1008	}
1009	}
1010	}
1011	n = 0;
1012	if (sparseset_cardinality (s: live_range_reload_inheritance_pseudos)
1013	<= (unsigned)param_lra_max_considered_reload_pseudos)
1014	EXECUTE_IF_SET_IN_SPARSESET (live_range_reload_inheritance_pseudos,
1015	reload_regno)
1016	if ((int) reload_regno != regno
1017	&& (ira_reg_classes_intersect_p
1018	[rclass][regno_allocno_class_array[reload_regno]])
1019	&& live_pseudos_reg_renumber[reload_regno] < 0
1020	&& find_hard_regno_for (regno: reload_regno, cost: &cost, try_only_hard_regno: -1, first_p) < 0)
1021	sorted_reload_pseudos[n++] = reload_regno;
1022	EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
1023	{
1024	update_lives (regno: spill_regno, free_p: true);
1025	if (lra_dump_file != NULL)
1026	fprintf (stream: lra_dump_file, format: " spill %d(freq=%d)",
1027	spill_regno, lra_reg_info[spill_regno].freq);
1028	}
1029	hard_regno = find_hard_regno_for (regno, cost: &cost, try_only_hard_regno: -1, first_p);
1030	if (hard_regno >= 0)
1031	{
1032	assign_temporarily (regno, hard_regno);
1033	qsort (sorted_reload_pseudos, n, sizeof (int),
1034	reload_pseudo_compare_func);
1035	for (j = 0; j < n; j++)
1036	{
1037	reload_regno = sorted_reload_pseudos[j];
1038	lra_assert (live_pseudos_reg_renumber[reload_regno] < 0);
1039	if ((reload_hard_regno
1040	= find_hard_regno_for (regno: reload_regno,
1041	cost: &reload_cost, try_only_hard_regno: -1, first_p)) >= 0)
1042	{
1043	if (lra_dump_file != NULL)
1044	fprintf (stream: lra_dump_file, format: " assign %d(cost=%d)",
1045	reload_regno, reload_cost);
1046	assign_temporarily (regno: reload_regno, hard_regno: reload_hard_regno);
1047	cost += reload_cost;
1048	}
1049	}
1050	EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
1051	{
1052	rtx_insn_list *x;
1053
1054	cost += lra_reg_info[spill_regno].freq;
1055	if (ira_reg_equiv[spill_regno].memory != NULL
1056	|| ira_reg_equiv[spill_regno].constant != NULL)
1057	for (x = ira_reg_equiv[spill_regno].init_insns;
1058	x != NULL;
1059	x = x->next ())
1060	cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (x->insn ()));
1061	}
1062	/* Avoid spilling static chain pointer pseudo when non-local
1063	goto is used. */
1064	if ((! static_p && best_static_p)
1065	|| (static_p == best_static_p
1066	&& (best_insn_pseudos_num > insn_pseudos_num
1067	|| (best_insn_pseudos_num == insn_pseudos_num
1068	&& (bad_spills_num < smallest_bad_spills_num
1069	|| (bad_spills_num == smallest_bad_spills_num
1070	&& best_cost > cost))))))
1071	{
1072	best_insn_pseudos_num = insn_pseudos_num;
1073	smallest_bad_spills_num = bad_spills_num;
1074	best_static_p = static_p;
1075	best_cost = cost;
1076	best_hard_regno = hard_regno;
1077	bitmap_copy (&best_spill_pseudos_bitmap, &spill_pseudos_bitmap);
1078	if (lra_dump_file != NULL)
1079	fprintf (stream: lra_dump_file,
1080	format: " Now best %d(cost=%d, bad_spills=%d, insn_pseudos=%d)\n",
1081	hard_regno, cost, bad_spills_num, insn_pseudos_num);
1082	}
1083	assign_temporarily (regno, hard_regno: -1);
1084	for (j = 0; j < n; j++)
1085	{
1086	reload_regno = sorted_reload_pseudos[j];
1087	if (live_pseudos_reg_renumber[reload_regno] >= 0)
1088	assign_temporarily (regno: reload_regno, hard_regno: -1);
1089	}
1090	}
1091	if (lra_dump_file != NULL)
1092	fprintf (stream: lra_dump_file, format: "\n");
1093	/* Restore the live hard reg pseudo info for spilled pseudos. */
1094	EXECUTE_IF_SET_IN_BITMAP (&spill_pseudos_bitmap, 0, spill_regno, bi)
1095	update_lives (regno: spill_regno, free_p: false);
1096	fail:
1097	;
1098	}
1099	/* Spill: */
1100	EXECUTE_IF_SET_IN_BITMAP (&best_spill_pseudos_bitmap, 0, spill_regno, bi)
1101	{
1102	if ((int) spill_regno >= lra_constraint_new_regno_start)
1103	former_reload_pseudo_spill_p = true;
1104	if (lra_dump_file != NULL)
1105	fprintf (stream: lra_dump_file, format: " Spill %sr%d(hr=%d, freq=%d) for r%d\n",
1106	pseudo_prefix_title (regno: spill_regno),
1107	spill_regno, reg_renumber[spill_regno],
1108	lra_reg_info[spill_regno].freq, regno);
1109	update_lives (regno: spill_regno, free_p: true);
1110	lra_setup_reg_renumber (regno: spill_regno, hard_regno: -1, print_p: false);
1111	}
1112	bitmap_ior_into (spilled_pseudo_bitmap, &best_spill_pseudos_bitmap);
1113	return best_hard_regno;
1114	}
1115
1116	/* Assign HARD_REGNO to REGNO. */
1117	static void
1118	assign_hard_regno (int hard_regno, int regno)
1119	{
1120	int i;
1121
1122	lra_assert (hard_regno >= 0);
1123	lra_setup_reg_renumber (regno, hard_regno, print_p: true);
1124	update_lives (regno, free_p: false);
1125	for (i = 0;
1126	i < hard_regno_nregs (regno: hard_regno, mode: lra_reg_info[regno].biggest_mode);
1127	i++)
1128	df_set_regs_ever_live (hard_regno + i, true);
1129	}
1130
1131	/* Array used for sorting different pseudos. */
1132	static int *sorted_pseudos;
1133
1134	/* The constraints pass is allowed to create equivalences between
1135	pseudos that make the current allocation "incorrect" (in the sense
1136	that pseudos are assigned to hard registers from their own conflict
1137	sets). The global variable check_and_force_assignment_correctness_p says
1138	whether this might have happened.
1139
1140	Process pseudos assigned to hard registers (less frequently used
1141	first), spill if a conflict is found, and mark the spilled pseudos
1142	in SPILLED_PSEUDO_BITMAP. Set up LIVE_HARD_REG_PSEUDOS from
1143	pseudos, assigned to hard registers. */
1144	static void
1145	setup_live_pseudos_and_spill_after_risky_transforms (bitmap
1146	spilled_pseudo_bitmap)
1147	{
1148	int p, i, j, n, regno, hard_regno, biggest_nregs, nregs_diff;
1149	unsigned int k, conflict_regno;
1150	poly_int64 offset;
1151	int val;
1152	HARD_REG_SET conflict_set;
1153	machine_mode mode, biggest_mode;
1154	lra_live_range_t r;
1155	bitmap_iterator bi;
1156	int max_regno = max_reg_num ();
1157
1158	if (! check_and_force_assignment_correctness_p)
1159	{
1160	for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1161	if (reg_renumber[i] >= 0 && lra_reg_info[i].nrefs > 0)
1162	update_lives (regno: i, free_p: false);
1163	return;
1164	}
1165	for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1166	if ((pic_offset_table_rtx == NULL_RTX
1167	|| i != (int) REGNO (pic_offset_table_rtx))
1168	&& (hard_regno = reg_renumber[i]) >= 0 && lra_reg_info[i].nrefs > 0)
1169	{
1170	biggest_mode = lra_reg_info[i].biggest_mode;
1171	biggest_nregs = hard_regno_nregs (regno: hard_regno, mode: biggest_mode);
1172	nregs_diff = (biggest_nregs
1173	- hard_regno_nregs (regno: hard_regno, PSEUDO_REGNO_MODE (i)));
1174	enum reg_class rclass = lra_get_allocno_class (regno: i);
1175
1176	if ((WORDS_BIG_ENDIAN
1177	&& (hard_regno - nregs_diff < 0
1178	|| !TEST_HARD_REG_BIT (reg_class_contents[rclass],
1179	bit: hard_regno - nregs_diff)))
1180	|| (!WORDS_BIG_ENDIAN
1181	&& (hard_regno + nregs_diff >= FIRST_PSEUDO_REGISTER
1182	|| !TEST_HARD_REG_BIT (reg_class_contents[rclass],
1183	bit: hard_regno + nregs_diff))))
1184	{
1185	/* Hard registers of paradoxical sub-registers are out of
1186	range of pseudo register class. Spill the pseudo. */
1187	reg_renumber[i] = -1;
1188	continue;
1189	}
1190	sorted_pseudos[n++] = i;
1191	}
1192	qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
1193	if (pic_offset_table_rtx != NULL_RTX
1194	&& (regno = REGNO (pic_offset_table_rtx)) >= FIRST_PSEUDO_REGISTER
1195	&& reg_renumber[regno] >= 0 && lra_reg_info[regno].nrefs > 0)
1196	sorted_pseudos[n++] = regno;
1197	for (i = n - 1; i >= 0; i--)
1198	{
1199	regno = sorted_pseudos[i];
1200	hard_regno = reg_renumber[regno];
1201	lra_assert (hard_regno >= 0);
1202	mode = lra_reg_info[regno].biggest_mode;
1203	sparseset_clear (s: live_range_hard_reg_pseudos);
1204	for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
1205	{
1206	EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
1207	sparseset_set_bit (s: live_range_hard_reg_pseudos, e: k);
1208	for (p = r->start + 1; p <= r->finish; p++)
1209	{
1210	lra_live_range_t r2;
1211
1212	for (r2 = start_point_ranges[p];
1213	r2 != NULL;
1214	r2 = r2->start_next)
1215	if (live_pseudos_reg_renumber[r2->regno] >= 0)
1216	sparseset_set_bit (s: live_range_hard_reg_pseudos, e: r2->regno);
1217	}
1218	}
1219	conflict_set = lra_no_alloc_regs;
1220	conflict_set |= lra_reg_info[regno].conflict_hard_regs;
1221	val = lra_reg_info[regno].val;
1222	offset = lra_reg_info[regno].offset;
1223	EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
1224	if (!lra_reg_val_equal_p (regno: conflict_regno, val, offset)
1225	/* If it is multi-register pseudos they should start on
1226	the same hard register. */
1227	|| hard_regno != reg_renumber[conflict_regno])
1228	{
1229	int conflict_hard_regno = reg_renumber[conflict_regno];
1230
1231	biggest_mode = lra_reg_info[conflict_regno].biggest_mode;
1232	biggest_nregs = hard_regno_nregs (regno: conflict_hard_regno,
1233	mode: biggest_mode);
1234	nregs_diff
1235	= (biggest_nregs
1236	- hard_regno_nregs (regno: conflict_hard_regno,
1237	PSEUDO_REGNO_MODE (conflict_regno)));
1238	add_to_hard_reg_set (regs: &conflict_set,
1239	mode: biggest_mode,
1240	regno: conflict_hard_regno
1241	- (WORDS_BIG_ENDIAN ? nregs_diff : 0));
1242	}
1243	if (! overlaps_hard_reg_set_p (regs: conflict_set, mode, regno: hard_regno))
1244	{
1245	update_lives (regno, free_p: false);
1246	continue;
1247	}
1248	bitmap_set_bit (spilled_pseudo_bitmap, regno);
1249	for (j = 0;
1250	j < hard_regno_nregs (regno: hard_regno, PSEUDO_REGNO_MODE (regno));
1251	j++)
1252	lra_hard_reg_usage[hard_regno + j] -= lra_reg_info[regno].freq;
1253	reg_renumber[regno] = -1;
1254	if (regno >= lra_constraint_new_regno_start)
1255	former_reload_pseudo_spill_p = true;
1256	if (lra_dump_file != NULL)
1257	fprintf (stream: lra_dump_file, format: " Spill r%d after risky transformations\n",
1258	regno);
1259	}
1260	}
1261
1262	/* Improve allocation by assigning the same hard regno of inheritance
1263	pseudos to the connected pseudos. We need this because inheritance
1264	pseudos are allocated after reload pseudos in the thread and when
1265	we assign a hard register to a reload pseudo we don't know yet that
1266	the connected inheritance pseudos can get the same hard register.
1267	Add pseudos with changed allocation to bitmap CHANGED_PSEUDOS. */
1268	static void
1269	improve_inheritance (bitmap changed_pseudos)
1270	{
1271	unsigned int k;
1272	int regno, another_regno, hard_regno, another_hard_regno, cost, i, n;
1273	lra_copy_t cp, next_cp;
1274	bitmap_iterator bi;
1275
1276	if (lra_inheritance_iter > LRA_MAX_INHERITANCE_PASSES)
1277	return;
1278	n = 0;
1279	EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, k, bi)
1280	if (reg_renumber[k] >= 0 && lra_reg_info[k].nrefs != 0)
1281	sorted_pseudos[n++] = k;
1282	qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
1283	for (i = 0; i < n; i++)
1284	{
1285	regno = sorted_pseudos[i];
1286	hard_regno = reg_renumber[regno];
1287	lra_assert (hard_regno >= 0);
1288	for (cp = lra_reg_info[regno].copies; cp != NULL; cp = next_cp)
1289	{
1290	if (cp->regno1 == regno)
1291	{
1292	next_cp = cp->regno1_next;
1293	another_regno = cp->regno2;
1294	}
1295	else if (cp->regno2 == regno)
1296	{
1297	next_cp = cp->regno2_next;
1298	another_regno = cp->regno1;
1299	}
1300	else
1301	gcc_unreachable ();
1302	/* Don't change reload pseudo allocation. It might have
1303	this allocation for a purpose and changing it can result
1304	in LRA cycling. */
1305	if ((another_regno < lra_constraint_new_regno_start
1306	|| bitmap_bit_p (&lra_inheritance_pseudos, another_regno))
1307	&& (another_hard_regno = reg_renumber[another_regno]) >= 0
1308	&& another_hard_regno != hard_regno)
1309	{
1310	if (lra_dump_file != NULL)
1311	fprintf
1312	(stream: lra_dump_file,
1313	format: " Improving inheritance for %d(%d) and %d(%d)...\n",
1314	regno, hard_regno, another_regno, another_hard_regno);
1315	update_lives (regno: another_regno, free_p: true);
1316	lra_setup_reg_renumber (regno: another_regno, hard_regno: -1, print_p: false);
1317	if (hard_regno == find_hard_regno_for (regno: another_regno, cost: &cost,
1318	try_only_hard_regno: hard_regno, first_p: false))
1319	assign_hard_regno (hard_regno, regno: another_regno);
1320	else
1321	assign_hard_regno (hard_regno: another_hard_regno, regno: another_regno);
1322	bitmap_set_bit (changed_pseudos, another_regno);
1323	}
1324	}
1325	}
1326	}
1327
1328
1329	/* Bitmap finally containing all pseudos spilled on this assignment
1330	pass. */
1331	static bitmap_head all_spilled_pseudos;
1332	/* All pseudos whose allocation was changed. */
1333	static bitmap_head changed_pseudo_bitmap;
1334
1335
1336	/* Add to LIVE_RANGE_HARD_REG_PSEUDOS all pseudos conflicting with
1337	REGNO and whose hard regs can be assigned to REGNO. */
1338	static void
1339	find_all_spills_for (int regno)
1340	{
1341	int p;
1342	lra_live_range_t r;
1343	unsigned int k;
1344	bitmap_iterator bi;
1345	enum reg_class rclass;
1346	bool *rclass_intersect_p;
1347
1348	rclass = regno_allocno_class_array[regno];
1349	rclass_intersect_p = ira_reg_classes_intersect_p[rclass];
1350	for (r = lra_reg_info[regno].live_ranges; r != NULL; r = r->next)
1351	{
1352	EXECUTE_IF_SET_IN_BITMAP (&live_hard_reg_pseudos[r->start], 0, k, bi)
1353	if (rclass_intersect_p[regno_allocno_class_array[k]])
1354	sparseset_set_bit (s: live_range_hard_reg_pseudos, e: k);
1355	for (p = r->start + 1; p <= r->finish; p++)
1356	{
1357	lra_live_range_t r2;
1358
1359	for (r2 = start_point_ranges[p];
1360	r2 != NULL;
1361	r2 = r2->start_next)
1362	{
1363	if (live_pseudos_reg_renumber[r2->regno] >= 0
1364	&& ! sparseset_bit_p (s: live_range_hard_reg_pseudos, e: r2->regno)
1365	&& rclass_intersect_p[regno_allocno_class_array[r2->regno]]
1366	&& ((int) r2->regno < lra_constraint_new_regno_start
1367	|| bitmap_bit_p (&lra_inheritance_pseudos, r2->regno)
1368	|| bitmap_bit_p (&lra_split_regs, r2->regno)
1369	|| bitmap_bit_p (&lra_optional_reload_pseudos, r2->regno)
1370	/* There is no sense to consider another reload
1371	pseudo if it has the same class. */
1372	|| regno_allocno_class_array[r2->regno] != rclass))
1373	sparseset_set_bit (s: live_range_hard_reg_pseudos, e: r2->regno);
1374	}
1375	}
1376	}
1377	}
1378
1379	/* Assign hard registers to reload pseudos and other pseudos. Return
1380	true if we was not able to assign hard registers to all reload
1381	pseudos. */
1382	static bool
1383	assign_by_spills (void)
1384	{
1385	int i, n, nfails, iter, regno, regno2, hard_regno, cost;
1386	rtx restore_rtx;
1387	bitmap_head changed_insns, do_not_assign_nonreload_pseudos;
1388	unsigned int u, conflict_regno;
1389	bitmap_iterator bi;
1390	bool reload_p, fails_p = false;
1391	int max_regno = max_reg_num ();
1392
1393	for (n = 0, i = lra_constraint_new_regno_start; i < max_regno; i++)
1394	if (reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0
1395	&& regno_allocno_class_array[i] != NO_REGS)
1396	sorted_pseudos[n++] = i;
1397	bitmap_initialize (head: &insn_conflict_pseudos, obstack: &reg_obstack);
1398	bitmap_initialize (head: &spill_pseudos_bitmap, obstack: &reg_obstack);
1399	bitmap_initialize (head: &best_spill_pseudos_bitmap, obstack: &reg_obstack);
1400	update_hard_regno_preference_check = XCNEWVEC (int, max_regno);
1401	curr_update_hard_regno_preference_check = 0;
1402	memset (s: try_hard_reg_pseudos_check, c: 0, n: sizeof (try_hard_reg_pseudos_check));
1403	for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1404	bitmap_initialize (head: &try_hard_reg_pseudos[i], obstack: &reg_obstack);
1405	curr_pseudo_check = 0;
1406	bitmap_initialize (head: &changed_insns, obstack: &reg_obstack);
1407	bitmap_initialize (head: &non_reload_pseudos, obstack: &reg_obstack);
1408	bitmap_ior (&non_reload_pseudos, &lra_inheritance_pseudos, &lra_split_regs);
1409	bitmap_ior_into (&non_reload_pseudos, &lra_subreg_reload_pseudos);
1410	bitmap_ior_into (&non_reload_pseudos, &lra_optional_reload_pseudos);
1411	for (iter = 0; iter <= 1; iter++)
1412	{
1413	qsort (sorted_pseudos, n, sizeof (int), reload_pseudo_compare_func);
1414	nfails = 0;
1415	for (i = 0; i < n; i++)
1416	{
1417	regno = sorted_pseudos[i];
1418	if (reg_renumber[regno] >= 0)
1419	continue;
1420	if (lra_dump_file != NULL)
1421	fprintf (stream: lra_dump_file, format: " Assigning to %d "
1422	"(cl=%s, orig=%d, freq=%d, tfirst=%d, tfreq=%d)...\n",
1423	regno, reg_class_names[regno_allocno_class_array[regno]],
1424	ORIGINAL_REGNO (regno_reg_rtx[regno]),
1425	lra_reg_info[regno].freq, regno_assign_info[regno].first,
1426	regno_assign_info[regno_assign_info[regno].first].freq);
1427	hard_regno = find_hard_regno_for (regno, cost: &cost, try_only_hard_regno: -1, first_p: iter == 1);
1428	reload_p = ! bitmap_bit_p (&non_reload_pseudos, regno);
1429	if (hard_regno < 0 && reload_p)
1430	hard_regno = spill_for (regno, spilled_pseudo_bitmap: &all_spilled_pseudos, first_p: iter == 1);
1431	if (hard_regno < 0)
1432	{
1433	if (reload_p) {
1434	/* Put unassigned reload pseudo first in the
1435	array. */
1436	regno2 = sorted_pseudos[nfails];
1437	sorted_pseudos[nfails++] = regno;
1438	sorted_pseudos[i] = regno2;
1439	}
1440	}
1441	else
1442	{
1443	/* This register might have been spilled by the previous
1444	pass. Indicate that it is no longer spilled. */
1445	bitmap_clear_bit (&all_spilled_pseudos, regno);
1446	assign_hard_regno (hard_regno, regno);
1447	if (! reload_p || regno_allocno_class_array[regno] == ALL_REGS)
1448	/* As non-reload pseudo assignment is changed we should
1449	reconsider insns referring for the pseudo. Do the same if a
1450	reload pseudo did not refine its class which can happens
1451	when the pseudo occurs only in reload insns. */
1452	bitmap_set_bit (&changed_pseudo_bitmap, regno);
1453	}
1454	}
1455	if (nfails == 0 || iter > 0)
1456	{
1457	fails_p = nfails != 0;
1458	break;
1459	}
1460	/* This is a very rare event. We cannot assign a hard register
1461	to reload pseudo because the hard register was assigned to
1462	another reload pseudo on a previous assignment pass. For x86
1463	example, on the 1st pass we assigned CX (although another
1464	hard register could be used for this) to reload pseudo in an
1465	insn, on the 2nd pass we need CX (and only this) hard
1466	register for a new reload pseudo in the same insn. Another
1467	possible situation may occur in assigning to multi-regs
1468	reload pseudos when hard regs pool is too fragmented even
1469	after spilling non-reload pseudos.
1470
1471	We should do something radical here to succeed. Here we
1472	spill *all* conflicting pseudos and reassign them. */
1473	if (lra_dump_file != NULL)
1474	fprintf (stream: lra_dump_file, format: " 2nd iter for reload pseudo assignments:\n");
1475	sparseset_clear (s: live_range_hard_reg_pseudos);
1476	for (i = 0; i < nfails; i++)
1477	{
1478	if (lra_dump_file != NULL)
1479	fprintf (stream: lra_dump_file, format: " Reload r%d assignment failure\n",
1480	sorted_pseudos[i]);
1481	find_all_spills_for (regno: sorted_pseudos[i]);
1482	}
1483	EXECUTE_IF_SET_IN_SPARSESET (live_range_hard_reg_pseudos, conflict_regno)
1484	{
1485	if ((int) conflict_regno >= lra_constraint_new_regno_start)
1486	{
1487	sorted_pseudos[nfails++] = conflict_regno;
1488	former_reload_pseudo_spill_p = true;
1489	}
1490	else
1491	/* It is better to do reloads before spilling as after the
1492	spill-subpass we will reload memory instead of pseudos
1493	and this will make reusing reload pseudos more
1494	complicated. Going directly to the spill pass in such
1495	case might result in worse code performance or even LRA
1496	cycling if we have few registers. */
1497	bitmap_set_bit (&all_spilled_pseudos, conflict_regno);
1498	if (lra_dump_file != NULL)
1499	fprintf (stream: lra_dump_file, format: " Spill %s r%d(hr=%d, freq=%d)\n",
1500	pseudo_prefix_title (regno: conflict_regno), conflict_regno,
1501	reg_renumber[conflict_regno],
1502	lra_reg_info[conflict_regno].freq);
1503	update_lives (regno: conflict_regno, free_p: true);
1504	lra_setup_reg_renumber (regno: conflict_regno, hard_regno: -1, print_p: false);
1505	}
1506	if (n < nfails)
1507	n = nfails;
1508	}
1509	improve_inheritance (changed_pseudos: &changed_pseudo_bitmap);
1510	bitmap_clear (&non_reload_pseudos);
1511	bitmap_clear (&changed_insns);
1512	if (! lra_simple_p)
1513	{
1514	/* We should not assign to original pseudos of inheritance
1515	pseudos or split pseudos if any its inheritance pseudo did
1516	not get hard register or any its split pseudo was not split
1517	because undo inheritance/split pass will extend live range of
1518	such inheritance or split pseudos. */
1519	bitmap_initialize (head: &do_not_assign_nonreload_pseudos, obstack: &reg_obstack);
1520	EXECUTE_IF_SET_IN_BITMAP (&lra_inheritance_pseudos, 0, u, bi)
1521	if ((restore_rtx = lra_reg_info[u].restore_rtx) != NULL_RTX
1522	&& REG_P (restore_rtx)
1523	&& reg_renumber[u] < 0
1524	&& bitmap_bit_p (&lra_inheritance_pseudos, u))
1525	bitmap_set_bit (&do_not_assign_nonreload_pseudos, REGNO (restore_rtx));
1526	EXECUTE_IF_SET_IN_BITMAP (&lra_split_regs, 0, u, bi)
1527	if ((restore_rtx = lra_reg_info[u].restore_rtx) != NULL_RTX
1528	&& reg_renumber[u] >= 0)
1529	{
1530	lra_assert (REG_P (restore_rtx));
1531	bitmap_set_bit (&do_not_assign_nonreload_pseudos, REGNO (restore_rtx));
1532	}
1533	for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1534	if (((i < lra_constraint_new_regno_start
1535	&& ! bitmap_bit_p (&do_not_assign_nonreload_pseudos, i))
1536	|| (bitmap_bit_p (&lra_inheritance_pseudos, i)
1537	&& lra_reg_info[i].restore_rtx != NULL_RTX)
1538	|| (bitmap_bit_p (&lra_split_regs, i)
1539	&& lra_reg_info[i].restore_rtx != NULL_RTX)
1540	|| bitmap_bit_p (&lra_subreg_reload_pseudos, i)
1541	|| bitmap_bit_p (&lra_optional_reload_pseudos, i))
1542	&& reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0
1543	&& regno_allocno_class_array[i] != NO_REGS)
1544	sorted_pseudos[n++] = i;
1545	bitmap_clear (&do_not_assign_nonreload_pseudos);
1546	if (n != 0 && lra_dump_file != NULL)
1547	fprintf (stream: lra_dump_file, format: " Reassigning non-reload pseudos\n");
1548	qsort (sorted_pseudos, n, sizeof (int), pseudo_compare_func);
1549	for (i = 0; i < n; i++)
1550	{
1551	regno = sorted_pseudos[i];
1552	hard_regno = find_hard_regno_for (regno, cost: &cost, try_only_hard_regno: -1, first_p: false);
1553	if (hard_regno >= 0)
1554	{
1555	assign_hard_regno (hard_regno, regno);
1556	/* We change allocation for non-reload pseudo on this
1557	iteration -- mark the pseudo for invalidation of used
1558	alternatives of insns containing the pseudo. */
1559	bitmap_set_bit (&changed_pseudo_bitmap, regno);
1560	}
1561	else
1562	{
1563	enum reg_class rclass = lra_get_allocno_class (regno);
1564	enum reg_class spill_class;
1565
1566	if (targetm.spill_class == NULL
1567	|| lra_reg_info[regno].restore_rtx == NULL_RTX
1568	|| ! bitmap_bit_p (&lra_inheritance_pseudos, regno)
1569	|| (spill_class
1570	= ((enum reg_class)
1571	targetm.spill_class
1572	((reg_class_t) rclass,
1573	PSEUDO_REGNO_MODE (regno)))) == NO_REGS)
1574	continue;
1575	regno_allocno_class_array[regno] = spill_class;
1576	hard_regno = find_hard_regno_for (regno, cost: &cost, try_only_hard_regno: -1, first_p: false);
1577	if (hard_regno < 0)
1578	regno_allocno_class_array[regno] = rclass;
1579	else
1580	{
1581	setup_reg_classes
1582	(regno, spill_class, spill_class, spill_class);
1583	assign_hard_regno (hard_regno, regno);
1584	bitmap_set_bit (&changed_pseudo_bitmap, regno);
1585	}
1586	}
1587	}
1588	}
1589	free (ptr: update_hard_regno_preference_check);
1590	bitmap_clear (&best_spill_pseudos_bitmap);
1591	bitmap_clear (&spill_pseudos_bitmap);
1592	bitmap_clear (&insn_conflict_pseudos);
1593	return fails_p;
1594	}
1595
1596	/* Entry function to assign hard registers to new reload pseudos
1597	starting with LRA_CONSTRAINT_NEW_REGNO_START (by possible spilling
1598	of old pseudos) and possibly to the old pseudos. The function adds
1599	what insns to process for the next constraint pass. Those are all
1600	insns who contains non-reload and non-inheritance pseudos with
1601	changed allocation.
1602
1603	Return true if we did not spill any non-reload and non-inheritance
1604	pseudos. Set up FAILS_P if we failed to assign hard registers to
1605	all reload pseudos. */
1606	bool
1607	lra_assign (bool &fails_p)
1608	{
1609	int i;
1610	unsigned int u;
1611	bitmap_iterator bi;
1612	bitmap_head insns_to_process;
1613	bool no_spills_p;
1614	int max_regno = max_reg_num ();
1615
1616	timevar_push (tv: TV_LRA_ASSIGN);
1617	lra_assignment_iter++;
1618	if (lra_dump_file != NULL)
1619	fprintf (stream: lra_dump_file, format: "\n********** Assignment #%d: **********\n\n",
1620	lra_assignment_iter);
1621	init_lives ();
1622	sorted_pseudos = XNEWVEC (int, max_regno);
1623	sorted_reload_pseudos = XNEWVEC (int, max_regno);
1624	regno_allocno_class_array = XNEWVEC (enum reg_class, max_regno);
1625	regno_live_length = XNEWVEC (int, max_regno);
1626	for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1627	{
1628	int l;
1629	lra_live_range_t r;
1630
1631	regno_allocno_class_array[i] = lra_get_allocno_class (regno: i);
1632	for (l = 0, r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
1633	l += r->finish - r->start + 1;
1634	regno_live_length[i] = l;
1635	}
1636	former_reload_pseudo_spill_p = false;
1637	init_regno_assign_info ();
1638	bitmap_initialize (head: &all_spilled_pseudos, obstack: &reg_obstack);
1639	create_live_range_start_chains ();
1640	setup_live_pseudos_and_spill_after_risky_transforms (&all_spilled_pseudos);
1641	if (! lra_hard_reg_split_p && ! lra_asm_error_p && flag_checking)
1642	/* Check correctness of allocation but only when there are no hard reg
1643	splits and asm errors as in the case of errors explicit insns involving
1644	hard regs are added or the asm is removed and this can result in
1645	incorrect allocation. */
1646	for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1647	if (lra_reg_info[i].nrefs != 0
1648	&& reg_renumber[i] >= 0
1649	&& overlaps_hard_reg_set_p (regs: lra_reg_info[i].conflict_hard_regs,
1650	PSEUDO_REGNO_MODE (i), regno: reg_renumber[i]))
1651	gcc_unreachable ();
1652	/* Setup insns to process on the next constraint pass. */
1653	bitmap_initialize (head: &changed_pseudo_bitmap, obstack: &reg_obstack);
1654	init_live_reload_and_inheritance_pseudos ();
1655	fails_p = assign_by_spills ();
1656	finish_live_reload_and_inheritance_pseudos ();
1657	bitmap_ior_into (&changed_pseudo_bitmap, &all_spilled_pseudos);
1658	no_spills_p = true;
1659	EXECUTE_IF_SET_IN_BITMAP (&all_spilled_pseudos, 0, u, bi)
1660	/* We ignore spilled pseudos created on last inheritance pass
1661	because they will be removed. */
1662	if (lra_reg_info[u].restore_rtx == NULL_RTX)
1663	{
1664	no_spills_p = false;
1665	break;
1666	}
1667	finish_live_range_start_chains ();
1668	bitmap_clear (&all_spilled_pseudos);
1669	bitmap_initialize (head: &insns_to_process, obstack: &reg_obstack);
1670	EXECUTE_IF_SET_IN_BITMAP (&changed_pseudo_bitmap, 0, u, bi)
1671	bitmap_ior_into (&insns_to_process, &lra_reg_info[u].insn_bitmap);
1672	bitmap_clear (&changed_pseudo_bitmap);
1673	EXECUTE_IF_SET_IN_BITMAP (&insns_to_process, 0, u, bi)
1674	{
1675	lra_push_insn_by_uid (u);
1676	/* Invalidate alternatives for insn should be processed. */
1677	lra_set_used_insn_alternative_by_uid (u, -1);
1678	}
1679	bitmap_clear (&insns_to_process);
1680	finish_regno_assign_info ();
1681	free (ptr: regno_live_length);
1682	free (ptr: regno_allocno_class_array);
1683	free (ptr: sorted_pseudos);
1684	free (ptr: sorted_reload_pseudos);
1685	finish_lives ();
1686	timevar_pop (tv: TV_LRA_ASSIGN);
1687	if (former_reload_pseudo_spill_p)
1688	lra_assignment_iter_after_spill++;
1689	/* This is conditional on flag_checking because valid code can take
1690	more than this maximum number of iteration, but at the same time
1691	the test can uncover errors in machine descriptions. */
1692	if (flag_checking
1693	&& (lra_assignment_iter_after_spill
1694	> LRA_MAX_ASSIGNMENT_ITERATION_NUMBER))
1695	internal_error
1696	("maximum number of LRA assignment passes is achieved (%d)",
1697	LRA_MAX_ASSIGNMENT_ITERATION_NUMBER);
1698	/* Reset the assignment correctness flag: */
1699	check_and_force_assignment_correctness_p = false;
1700	return no_spills_p;
1701	}
1702
1703	/* Find start and finish insns for reload pseudo REGNO. Return true
1704	if we managed to find the expected insns. Return false,
1705	otherwise. */
1706	static bool
1707	find_reload_regno_insns (int regno, rtx_insn * &start, rtx_insn * &finish)
1708	{
1709	unsigned int uid;
1710	bitmap_iterator bi;
1711	int insns_num = 0;
1712	bool clobber_p = false;
1713	rtx_insn *prev_insn, *next_insn;
1714	rtx_insn *start_insn = NULL, *first_insn = NULL, *second_insn = NULL;
1715
1716	EXECUTE_IF_SET_IN_BITMAP (&lra_reg_info[regno].insn_bitmap, 0, uid, bi)
1717	{
1718	if (start_insn == NULL)
1719	start_insn = lra_insn_recog_data[uid]->insn;
1720	if (GET_CODE (PATTERN (lra_insn_recog_data[uid]->insn)) == CLOBBER)
1721	clobber_p = true;
1722	else
1723	insns_num++;
1724	}
1725	/* For reload pseudo we should have at most 3 insns besides clobber referring for
1726	it: input/output reload insns and the original insn. */
1727	if (insns_num > 3)
1728	return false;
1729	if (clobber_p)
1730	insns_num++;
1731	if (insns_num > 1)
1732	{
1733	for (prev_insn = PREV_INSN (insn: start_insn),
1734	next_insn = NEXT_INSN (insn: start_insn);
1735	insns_num != 1 && (prev_insn != NULL
1736	|| (next_insn != NULL && second_insn == NULL)); )
1737	{
1738	if (prev_insn != NULL)
1739	{
1740	if (bitmap_bit_p (&lra_reg_info[regno].insn_bitmap,
1741	INSN_UID (insn: prev_insn)))
1742	{
1743	first_insn = prev_insn;
1744	insns_num--;
1745	}
1746	prev_insn = PREV_INSN (insn: prev_insn);
1747	}
1748	if (next_insn != NULL && second_insn == NULL)
1749	{
1750	if (! bitmap_bit_p (&lra_reg_info[regno].insn_bitmap,
1751	INSN_UID (insn: next_insn)))
1752	next_insn = NEXT_INSN (insn: next_insn);
1753	else
1754	{
1755	second_insn = next_insn;
1756	insns_num--;
1757	}
1758	}
1759	}
1760	if (insns_num > 1)
1761	return false;
1762	}
1763	start = first_insn != NULL ? first_insn : start_insn;
1764	finish = second_insn != NULL ? second_insn : start_insn;
1765	return true;
1766	}
1767
1768	/* Process reload pseudos which did not get a hard reg, split a hard
1769	reg live range in live range of a reload pseudo, and then return
1770	TRUE. If we did not split a hard reg live range, report an error,
1771	and return FALSE. */
1772	bool
1773	lra_split_hard_reg_for (void)
1774	{
1775	int i, regno;
1776	rtx_insn *insn, *first, *last;
1777	unsigned int u;
1778	bitmap_iterator bi;
1779	enum reg_class rclass;
1780	int max_regno = max_reg_num ();
1781	/* We did not assign hard regs to reload pseudos after two
1782	iterations. Either it's an asm and something is wrong with the
1783	constraints, or we have run out of spill registers; error out in
1784	either case. */
1785	bool asm_p = false, spill_p = false;
1786	bitmap_head failed_reload_insns, failed_reload_pseudos, over_split_insns;
1787
1788	if (lra_dump_file != NULL)
1789	fprintf (stream: lra_dump_file,
1790	format: "\n****** Splitting a hard reg after assignment #%d: ******\n\n",
1791	lra_assignment_iter);
1792	bitmap_initialize (head: &failed_reload_pseudos, obstack: &reg_obstack);
1793	bitmap_initialize (head: &non_reload_pseudos, obstack: &reg_obstack);
1794	bitmap_ior (&non_reload_pseudos, &lra_inheritance_pseudos, &lra_split_regs);
1795	bitmap_ior_into (&non_reload_pseudos, &lra_subreg_reload_pseudos);
1796	bitmap_ior_into (&non_reload_pseudos, &lra_optional_reload_pseudos);
1797	bitmap_initialize (head: &over_split_insns, obstack: &reg_obstack);
1798	for (i = lra_constraint_new_regno_start; i < max_regno; i++)
1799	if (reg_renumber[i] < 0 && lra_reg_info[i].nrefs != 0
1800	&& (rclass = lra_get_allocno_class (regno: i)) != NO_REGS
1801	&& ! bitmap_bit_p (&non_reload_pseudos, i))
1802	{
1803	if (! find_reload_regno_insns (regno: i, start&: first, finish&: last))
1804	continue;
1805	if (BLOCK_FOR_INSN (insn: first) == BLOCK_FOR_INSN (insn: last))
1806	{
1807	/* Check that we are not trying to split over the same insn
1808	requiring reloads to avoid splitting the same hard reg twice or
1809	more. If we need several hard regs splitting over the same insn
1810	it can be finished on the next iterations.
1811
1812	The following loop iteration number is small as we split hard
1813	reg in a very small range. */
1814	for (insn = first;
1815	insn != NEXT_INSN (insn: last);
1816	insn = NEXT_INSN (insn))
1817	if (bitmap_bit_p (&over_split_insns, INSN_UID (insn)))
1818	break;
1819	if (insn != NEXT_INSN (insn: last)
1820	|| !spill_hard_reg_in_range (i, rclass, first, last))
1821	{
1822	bitmap_set_bit (&failed_reload_pseudos, i);
1823	}
1824	else
1825	{
1826	for (insn = first;
1827	insn != NEXT_INSN (insn: last);
1828	insn = NEXT_INSN (insn))
1829	bitmap_set_bit (&over_split_insns, INSN_UID (insn));
1830	spill_p = true;
1831	}
1832	}
1833	}
1834	bitmap_clear (&over_split_insns);
1835	if (spill_p)
1836	{
1837	bitmap_clear (&failed_reload_pseudos);
1838	return true;
1839	}
1840	bitmap_clear (&non_reload_pseudos);
1841	bitmap_initialize (head: &failed_reload_insns, obstack: &reg_obstack);
1842	EXECUTE_IF_SET_IN_BITMAP (&failed_reload_pseudos, 0, u, bi)
1843	{
1844	regno = u;
1845	bitmap_ior_into (&failed_reload_insns,
1846	&lra_reg_info[regno].insn_bitmap);
1847	lra_setup_reg_renumber
1848	(regno, ira_class_hard_regs[lra_get_allocno_class (regno)][0], print_p: false);
1849	}
1850	EXECUTE_IF_SET_IN_BITMAP (&failed_reload_insns, 0, u, bi)
1851	{
1852	insn = lra_insn_recog_data[u]->insn;
1853	if (asm_noperands (PATTERN (insn)) >= 0)
1854	{
1855	asm_p = true;
1856	lra_asm_insn_error (insn);
1857	}
1858	else if (!asm_p)
1859	{
1860	error ("unable to find a register to spill");
1861	fatal_insn ("this is the insn:", insn);
1862	}
1863	}
1864	bitmap_clear (&failed_reload_pseudos);
1865	bitmap_clear (&failed_reload_insns);
1866	return false;
1867	}
1868