1	/* IRA processing allocno lives to build allocno live ranges.
2	Copyright (C) 2006-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	#include "config.h"
22	#include "system.h"
23	#include "coretypes.h"
24	#include "backend.h"
25	#include "target.h"
26	#include "rtl.h"
27	#include "predict.h"
28	#include "df.h"
29	#include "memmodel.h"
30	#include "tm_p.h"
31	#include "insn-config.h"
32	#include "regs.h"
33	#include "ira.h"
34	#include "ira-int.h"
35	#include "sparseset.h"
36	#include "function-abi.h"
37	#include "except.h"
38
39	/* The code in this file is similar to one in global but the code
40	works on the allocno basis and creates live ranges instead of
41	pseudo-register conflicts. */
42
43	/* Program points are enumerated by numbers from range
44	0..IRA_MAX_POINT-1. There are approximately two times more program
45	points than insns. Program points are places in the program where
46	liveness info can be changed. In most general case (there are more
47	complicated cases too) some program points correspond to places
48	where input operand dies and other ones correspond to places where
49	output operands are born. */
50	int ira_max_point;
51
52	/* Arrays of size IRA_MAX_POINT mapping a program point to the allocno
53	live ranges with given start/finish point. */
54	live_range_t *ira_start_point_ranges, *ira_finish_point_ranges;
55
56	/* Number of the current program point. */
57	static int curr_point;
58
59	/* Point where register pressure excess started or -1 if there is no
60	register pressure excess. Excess pressure for a register class at
61	some point means that there are more allocnos of given register
62	class living at the point than number of hard-registers of the
63	class available for the allocation. It is defined only for
64	pressure classes. */
65	static int high_pressure_start_point[N_REG_CLASSES];
66
67	/* Objects live at current point in the scan. */
68	static sparseset objects_live;
69
70	/* A temporary bitmap used in functions that wish to avoid visiting an allocno
71	multiple times. */
72	static sparseset allocnos_processed;
73
74	/* Set of hard regs (except eliminable ones) currently live. */
75	static HARD_REG_SET hard_regs_live;
76
77	/* The loop tree node corresponding to the current basic block. */
78	static ira_loop_tree_node_t curr_bb_node;
79
80	/* The number of the last processed call. */
81	static int last_call_num;
82	/* The number of last call at which given allocno was saved. */
83	static int *allocno_saved_at_call;
84
85	/* The value returned by ira_setup_alts for the current instruction;
86	i.e. the set of alternatives that we should consider to be likely
87	candidates during reloading. */
88	static alternative_mask preferred_alternatives;
89
90	/* If non-NULL, the source operand of a register to register copy for which
91	we should not add a conflict with the copy's destination operand. */
92	static rtx ignore_reg_for_conflicts;
93
94	/* Record hard register REGNO as now being live. */
95	static void
96	make_hard_regno_live (int regno)
97	{
98	SET_HARD_REG_BIT (set&: hard_regs_live, bit: regno);
99	}
100
101	/* Process the definition of hard register REGNO. This updates
102	hard_regs_live and hard reg conflict information for living allocnos. */
103	static void
104	make_hard_regno_dead (int regno)
105	{
106	unsigned int i;
107	EXECUTE_IF_SET_IN_SPARSESET (objects_live, i)
108	{
109	ira_object_t obj = ira_object_id_map[i];
110
111	if (ignore_reg_for_conflicts != NULL_RTX
112	&& REGNO (ignore_reg_for_conflicts)
113	== (unsigned int) ALLOCNO_REGNO (OBJECT_ALLOCNO (obj)))
114	continue;
115
116	SET_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj), bit: regno);
117	SET_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), bit: regno);
118	}
119	CLEAR_HARD_REG_BIT (set&: hard_regs_live, bit: regno);
120	}
121
122	/* Record object OBJ as now being live. Set a bit for it in objects_live,
123	and start a new live range for it if necessary. */
124	static void
125	make_object_live (ira_object_t obj)
126	{
127	sparseset_set_bit (s: objects_live, OBJECT_CONFLICT_ID (obj));
128
129	live_range_t lr = OBJECT_LIVE_RANGES (obj);
130	if (lr == NULL
131	|| (lr->finish != curr_point && lr->finish + 1 != curr_point))
132	ira_add_live_range_to_object (obj, curr_point, -1);
133	}
134
135	/* Update ALLOCNO_EXCESS_PRESSURE_POINTS_NUM for the allocno
136	associated with object OBJ. */
137	static void
138	update_allocno_pressure_excess_length (ira_object_t obj)
139	{
140	ira_allocno_t a = OBJECT_ALLOCNO (obj);
141	int start, i;
142	enum reg_class aclass, pclass, cl;
143	live_range_t p;
144
145	aclass = ALLOCNO_CLASS (a);
146	pclass = ira_pressure_class_translate[aclass];
147	for (i = 0;
148	(cl = ira_reg_class_super_classes[pclass][i]) != LIM_REG_CLASSES;
149	i++)
150	{
151	if (! ira_reg_pressure_class_p[cl])
152	continue;
153	if (high_pressure_start_point[cl] < 0)
154	continue;
155	p = OBJECT_LIVE_RANGES (obj);
156	ira_assert (p != NULL);
157	start = (high_pressure_start_point[cl] > p->start
158	? high_pressure_start_point[cl] : p->start);
159	ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) += curr_point - start + 1;
160	}
161	}
162
163	/* Process the definition of object OBJ, which is associated with allocno A.
164	This finishes the current live range for it. */
165	static void
166	make_object_dead (ira_object_t obj)
167	{
168	live_range_t lr;
169	int regno;
170	int ignore_regno = -1;
171	int ignore_total_regno = -1;
172	int end_regno = -1;
173
174	sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (obj));
175
176	/* Check whether any part of IGNORE_REG_FOR_CONFLICTS already conflicts
177	with OBJ. */
178	if (ignore_reg_for_conflicts != NULL_RTX
179	&& REGNO (ignore_reg_for_conflicts) < FIRST_PSEUDO_REGISTER)
180	{
181	end_regno = END_REGNO (x: ignore_reg_for_conflicts);
182	ignore_regno = ignore_total_regno = REGNO (ignore_reg_for_conflicts);
183
184	for (regno = ignore_regno; regno < end_regno; regno++)
185	{
186	if (TEST_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj), bit: regno))
187	ignore_regno = end_regno;
188	if (TEST_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), bit: regno))
189	ignore_total_regno = end_regno;
190	}
191	}
192
193	OBJECT_CONFLICT_HARD_REGS (obj) |= hard_regs_live;
194	OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= hard_regs_live;
195
196	/* If IGNORE_REG_FOR_CONFLICTS did not already conflict with OBJ, make
197	sure it still doesn't. */
198	for (regno = ignore_regno; regno < end_regno; regno++)
199	CLEAR_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj), bit: regno);
200	for (regno = ignore_total_regno; regno < end_regno; regno++)
201	CLEAR_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), bit: regno);
202
203	lr = OBJECT_LIVE_RANGES (obj);
204	ira_assert (lr != NULL);
205	lr->finish = curr_point;
206	update_allocno_pressure_excess_length (obj);
207	}
208
209	/* The current register pressures for each pressure class for the current
210	basic block. */
211	static int curr_reg_pressure[N_REG_CLASSES];
212
213	/* Record that register pressure for PCLASS increased by N registers.
214	Update the current register pressure, maximal register pressure for
215	the current BB and the start point of the register pressure
216	excess. */
217	static void
218	inc_register_pressure (enum reg_class pclass, int n)
219	{
220	int i;
221	enum reg_class cl;
222
223	for (i = 0;
224	(cl = ira_reg_class_super_classes[pclass][i]) != LIM_REG_CLASSES;
225	i++)
226	{
227	if (! ira_reg_pressure_class_p[cl])
228	continue;
229	curr_reg_pressure[cl] += n;
230	if (high_pressure_start_point[cl] < 0
231	&& (curr_reg_pressure[cl] > ira_class_hard_regs_num[cl]))
232	high_pressure_start_point[cl] = curr_point;
233	if (curr_bb_node->reg_pressure[cl] < curr_reg_pressure[cl])
234	curr_bb_node->reg_pressure[cl] = curr_reg_pressure[cl];
235	}
236	}
237
238	/* Record that register pressure for PCLASS has decreased by NREGS
239	registers; update current register pressure, start point of the
240	register pressure excess, and register pressure excess length for
241	living allocnos. */
242
243	static void
244	dec_register_pressure (enum reg_class pclass, int nregs)
245	{
246	int i;
247	unsigned int j;
248	enum reg_class cl;
249	bool set_p = false;
250
251	for (i = 0;
252	(cl = ira_reg_class_super_classes[pclass][i]) != LIM_REG_CLASSES;
253	i++)
254	{
255	if (! ira_reg_pressure_class_p[cl])
256	continue;
257	curr_reg_pressure[cl] -= nregs;
258	ira_assert (curr_reg_pressure[cl] >= 0);
259	if (high_pressure_start_point[cl] >= 0
260	&& curr_reg_pressure[cl] <= ira_class_hard_regs_num[cl])
261	set_p = true;
262	}
263	if (set_p)
264	{
265	EXECUTE_IF_SET_IN_SPARSESET (objects_live, j)
266	update_allocno_pressure_excess_length (obj: ira_object_id_map[j]);
267	for (i = 0;
268	(cl = ira_reg_class_super_classes[pclass][i]) != LIM_REG_CLASSES;
269	i++)
270	{
271	if (! ira_reg_pressure_class_p[cl])
272	continue;
273	if (high_pressure_start_point[cl] >= 0
274	&& curr_reg_pressure[cl] <= ira_class_hard_regs_num[cl])
275	high_pressure_start_point[cl] = -1;
276	}
277	}
278	}
279
280	/* Determine from the objects_live bitmap whether REGNO is currently live,
281	and occupies only one object. Return false if we have no information. */
282	static bool
283	pseudo_regno_single_word_and_live_p (int regno)
284	{
285	ira_allocno_t a = ira_curr_regno_allocno_map[regno];
286	ira_object_t obj;
287
288	if (a == NULL)
289	return false;
290	if (ALLOCNO_NUM_OBJECTS (a) > 1)
291	return false;
292
293	obj = ALLOCNO_OBJECT (a, 0);
294
295	return sparseset_bit_p (s: objects_live, OBJECT_CONFLICT_ID (obj));
296	}
297
298	/* Mark the pseudo register REGNO as live. Update all information about
299	live ranges and register pressure. */
300	static void
301	mark_pseudo_regno_live (int regno)
302	{
303	ira_allocno_t a = ira_curr_regno_allocno_map[regno];
304	enum reg_class pclass;
305	int i, n, nregs;
306
307	if (a == NULL)
308	return;
309
310	/* Invalidate because it is referenced. */
311	allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
312
313	n = ALLOCNO_NUM_OBJECTS (a);
314	pclass = ira_pressure_class_translate[ALLOCNO_CLASS (a)];
315	nregs = ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)];
316	if (n > 1)
317	{
318	/* We track every subobject separately. */
319	gcc_assert (nregs == n);
320	nregs = 1;
321	}
322
323	for (i = 0; i < n; i++)
324	{
325	ira_object_t obj = ALLOCNO_OBJECT (a, i);
326
327	if (sparseset_bit_p (s: objects_live, OBJECT_CONFLICT_ID (obj)))
328	continue;
329
330	inc_register_pressure (pclass, n: nregs);
331	make_object_live (obj);
332	}
333	}
334
335	/* Like mark_pseudo_regno_live, but try to only mark one subword of
336	the pseudo as live. SUBWORD indicates which; a value of 0
337	indicates the low part. */
338	static void
339	mark_pseudo_regno_subword_live (int regno, int subword)
340	{
341	ira_allocno_t a = ira_curr_regno_allocno_map[regno];
342	int n;
343	enum reg_class pclass;
344	ira_object_t obj;
345
346	if (a == NULL)
347	return;
348
349	/* Invalidate because it is referenced. */
350	allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
351
352	n = ALLOCNO_NUM_OBJECTS (a);
353	if (n == 1)
354	{
355	mark_pseudo_regno_live (regno);
356	return;
357	}
358
359	pclass = ira_pressure_class_translate[ALLOCNO_CLASS (a)];
360	gcc_assert
361	(n == ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]);
362	obj = ALLOCNO_OBJECT (a, subword);
363
364	if (sparseset_bit_p (s: objects_live, OBJECT_CONFLICT_ID (obj)))
365	return;
366
367	inc_register_pressure (pclass, n: 1);
368	make_object_live (obj);
369	}
370
371	/* Mark the register REG as live. Store a 1 in hard_regs_live for
372	this register, record how many consecutive hardware registers it
373	actually needs. */
374	static void
375	mark_hard_reg_live (rtx reg)
376	{
377	int regno = REGNO (reg);
378
379	if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, bit: regno))
380	{
381	int last = END_REGNO (x: reg);
382	enum reg_class aclass, pclass;
383
384	while (regno < last)
385	{
386	if (! TEST_HARD_REG_BIT (set: hard_regs_live, bit: regno)
387	&& ! TEST_HARD_REG_BIT (set: eliminable_regset, bit: regno))
388	{
389	aclass = ira_hard_regno_allocno_class[regno];
390	pclass = ira_pressure_class_translate[aclass];
391	inc_register_pressure (pclass, n: 1);
392	make_hard_regno_live (regno);
393	}
394	regno++;
395	}
396	}
397	}
398
399	/* Mark a pseudo, or one of its subwords, as live. REGNO is the pseudo's
400	register number; ORIG_REG is the access in the insn, which may be a
401	subreg. */
402	static void
403	mark_pseudo_reg_live (rtx orig_reg, unsigned regno)
404	{
405	if (read_modify_subreg_p (orig_reg))
406	{
407	mark_pseudo_regno_subword_live (regno,
408	subword: subreg_lowpart_p (orig_reg) ? 0 : 1);
409	}
410	else
411	mark_pseudo_regno_live (regno);
412	}
413
414	/* Mark the register referenced by use or def REF as live. */
415	static void
416	mark_ref_live (df_ref ref)
417	{
418	rtx reg = DF_REF_REG (ref);
419	rtx orig_reg = reg;
420
421	if (GET_CODE (reg) == SUBREG)
422	reg = SUBREG_REG (reg);
423
424	if (REGNO (reg) >= FIRST_PSEUDO_REGISTER)
425	mark_pseudo_reg_live (orig_reg, REGNO (reg));
426	else
427	mark_hard_reg_live (reg);
428	}
429
430	/* Mark the pseudo register REGNO as dead. Update all information about
431	live ranges and register pressure. */
432	static void
433	mark_pseudo_regno_dead (int regno)
434	{
435	ira_allocno_t a = ira_curr_regno_allocno_map[regno];
436	int n, i, nregs;
437	enum reg_class cl;
438
439	if (a == NULL)
440	return;
441
442	/* Invalidate because it is referenced. */
443	allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
444
445	n = ALLOCNO_NUM_OBJECTS (a);
446	cl = ira_pressure_class_translate[ALLOCNO_CLASS (a)];
447	nregs = ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)];
448	if (n > 1)
449	{
450	/* We track every subobject separately. */
451	gcc_assert (nregs == n);
452	nregs = 1;
453	}
454	for (i = 0; i < n; i++)
455	{
456	ira_object_t obj = ALLOCNO_OBJECT (a, i);
457	if (!sparseset_bit_p (s: objects_live, OBJECT_CONFLICT_ID (obj)))
458	continue;
459
460	dec_register_pressure (pclass: cl, nregs);
461	make_object_dead (obj);
462	}
463	}
464
465	/* Like mark_pseudo_regno_dead, but called when we know that only part of the
466	register dies. SUBWORD indicates which; a value of 0 indicates the low part. */
467	static void
468	mark_pseudo_regno_subword_dead (int regno, int subword)
469	{
470	ira_allocno_t a = ira_curr_regno_allocno_map[regno];
471	int n;
472	enum reg_class cl;
473	ira_object_t obj;
474
475	if (a == NULL)
476	return;
477
478	/* Invalidate because it is referenced. */
479	allocno_saved_at_call[ALLOCNO_NUM (a)] = 0;
480
481	n = ALLOCNO_NUM_OBJECTS (a);
482	if (n == 1)
483	/* The allocno as a whole doesn't die in this case. */
484	return;
485
486	cl = ira_pressure_class_translate[ALLOCNO_CLASS (a)];
487	gcc_assert
488	(n == ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]);
489
490	obj = ALLOCNO_OBJECT (a, subword);
491	if (!sparseset_bit_p (s: objects_live, OBJECT_CONFLICT_ID (obj)))
492	return;
493
494	dec_register_pressure (pclass: cl, nregs: 1);
495	make_object_dead (obj);
496	}
497
498	/* Process the definition of hard register REG. This updates hard_regs_live
499	and hard reg conflict information for living allocnos. */
500	static void
501	mark_hard_reg_dead (rtx reg)
502	{
503	int regno = REGNO (reg);
504
505	if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, bit: regno))
506	{
507	int last = END_REGNO (x: reg);
508	enum reg_class aclass, pclass;
509
510	while (regno < last)
511	{
512	if (TEST_HARD_REG_BIT (set: hard_regs_live, bit: regno))
513	{
514	aclass = ira_hard_regno_allocno_class[regno];
515	pclass = ira_pressure_class_translate[aclass];
516	dec_register_pressure (pclass, nregs: 1);
517	make_hard_regno_dead (regno);
518	}
519	regno++;
520	}
521	}
522	}
523
524	/* Mark a pseudo, or one of its subwords, as dead. REGNO is the pseudo's
525	register number; ORIG_REG is the access in the insn, which may be a
526	subreg. */
527	static void
528	mark_pseudo_reg_dead (rtx orig_reg, unsigned regno)
529	{
530	if (read_modify_subreg_p (orig_reg))
531	{
532	mark_pseudo_regno_subword_dead (regno,
533	subword: subreg_lowpart_p (orig_reg) ? 0 : 1);
534	}
535	else
536	mark_pseudo_regno_dead (regno);
537	}
538
539	/* Mark the register referenced by definition DEF as dead, if the
540	definition is a total one. */
541	static void
542	mark_ref_dead (df_ref def)
543	{
544	rtx reg = DF_REF_REG (def);
545	rtx orig_reg = reg;
546
547	if (DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL))
548	return;
549
550	if (GET_CODE (reg) == SUBREG)
551	reg = SUBREG_REG (reg);
552
553	if (DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL)
554	&& (GET_CODE (orig_reg) != SUBREG
555	|| REGNO (reg) < FIRST_PSEUDO_REGISTER
556	|| !read_modify_subreg_p (orig_reg)))
557	return;
558
559	if (REGNO (reg) >= FIRST_PSEUDO_REGISTER)
560	mark_pseudo_reg_dead (orig_reg, REGNO (reg));
561	else
562	mark_hard_reg_dead (reg);
563	}
564
565	/* If REG is a pseudo or a subreg of it, and the class of its allocno
566	intersects CL, make a conflict with pseudo DREG. ORIG_DREG is the
567	rtx actually accessed, it may be identical to DREG or a subreg of it.
568	Advance the current program point before making the conflict if
569	ADVANCE_P. Return TRUE if we will need to advance the current
570	program point. */
571	static bool
572	make_pseudo_conflict (rtx reg, enum reg_class cl, rtx dreg, rtx orig_dreg,
573	bool advance_p)
574	{
575	rtx orig_reg = reg;
576	ira_allocno_t a;
577
578	if (GET_CODE (reg) == SUBREG)
579	reg = SUBREG_REG (reg);
580
581	if (! REG_P (reg) || REGNO (reg) < FIRST_PSEUDO_REGISTER)
582	return advance_p;
583
584	a = ira_curr_regno_allocno_map[REGNO (reg)];
585	if (! reg_classes_intersect_p (cl, ALLOCNO_CLASS (a)))
586	return advance_p;
587
588	if (advance_p)
589	curr_point++;
590
591	mark_pseudo_reg_live (orig_reg, REGNO (reg));
592	mark_pseudo_reg_live (orig_reg: orig_dreg, REGNO (dreg));
593	mark_pseudo_reg_dead (orig_reg, REGNO (reg));
594	mark_pseudo_reg_dead (orig_reg: orig_dreg, REGNO (dreg));
595
596	return false;
597	}
598
599	/* Check and make if necessary conflicts for pseudo DREG of class
600	DEF_CL of the current insn with input operand USE of class USE_CL.
601	ORIG_DREG is the rtx actually accessed, it may be identical to
602	DREG or a subreg of it. Advance the current program point before
603	making the conflict if ADVANCE_P. Return TRUE if we will need to
604	advance the current program point. */
605	static bool
606	check_and_make_def_use_conflict (rtx dreg, rtx orig_dreg,
607	enum reg_class def_cl, int use,
608	enum reg_class use_cl, bool advance_p)
609	{
610	if (! reg_classes_intersect_p (def_cl, use_cl))
611	return advance_p;
612
613	advance_p = make_pseudo_conflict (reg: recog_data.operand[use],
614	cl: use_cl, dreg, orig_dreg, advance_p);
615
616	/* Reload may end up swapping commutative operands, so you
617	have to take both orderings into account. The
618	constraints for the two operands can be completely
619	different. (Indeed, if the constraints for the two
620	operands are the same for all alternatives, there's no
621	point marking them as commutative.) */
622	if (use < recog_data.n_operands - 1
623	&& recog_data.constraints[use][0] == '%')
624	advance_p
625	= make_pseudo_conflict (reg: recog_data.operand[use + 1],
626	cl: use_cl, dreg, orig_dreg, advance_p);
627	if (use >= 1
628	&& recog_data.constraints[use - 1][0] == '%')
629	advance_p
630	= make_pseudo_conflict (reg: recog_data.operand[use - 1],
631	cl: use_cl, dreg, orig_dreg, advance_p);
632	return advance_p;
633	}
634
635	/* Check and make if necessary conflicts for definition DEF of class
636	DEF_CL of the current insn with input operands. Process only
637	constraints of alternative ALT.
638
639	One of three things is true when this function is called:
640
641	(1) DEF is an earlyclobber for alternative ALT. Input operands then
642	conflict with DEF in ALT unless they explicitly match DEF via 0-9
643	constraints.
644
645	(2) DEF matches (via 0-9 constraints) an operand that is an
646	earlyclobber for alternative ALT. Other input operands then
647	conflict with DEF in ALT.
648
649	(3) [FOR_TIE_P] Some input operand X matches DEF for alternative ALT.
650	Input operands with a different value from X then conflict with
651	DEF in ALT.
652
653	However, there's still a judgement call to make when deciding
654	whether a conflict in ALT is important enough to be reflected
655	in the pan-alternative allocno conflict set. */
656	static void
657	check_and_make_def_conflict (int alt, int def, enum reg_class def_cl,
658	bool for_tie_p)
659	{
660	int use, use_match;
661	ira_allocno_t a;
662	enum reg_class use_cl, acl;
663	bool advance_p;
664	rtx dreg = recog_data.operand[def];
665	rtx orig_dreg = dreg;
666
667	if (def_cl == NO_REGS)
668	return;
669
670	if (GET_CODE (dreg) == SUBREG)
671	dreg = SUBREG_REG (dreg);
672
673	if (! REG_P (dreg) || REGNO (dreg) < FIRST_PSEUDO_REGISTER)
674	return;
675
676	a = ira_curr_regno_allocno_map[REGNO (dreg)];
677	acl = ALLOCNO_CLASS (a);
678	if (! reg_classes_intersect_p (acl, def_cl))
679	return;
680
681	advance_p = true;
682
683	int n_operands = recog_data.n_operands;
684	const operand_alternative *op_alt = &recog_op_alt[alt * n_operands];
685	for (use = 0; use < n_operands; use++)
686	{
687	int alt1;
688
689	if (use == def || recog_data.operand_type[use] == OP_OUT)
690	continue;
691
692	/* An earlyclobber on DEF doesn't apply to an input operand X if X
693	explicitly matches DEF, but it applies to other input operands
694	even if they happen to be the same value as X.
695
696	In contrast, if an input operand X is tied to a non-earlyclobber
697	DEF, there's no conflict with other input operands that have the
698	same value as X. */
699	if (op_alt[use].matches == def
700	|| (for_tie_p
701	&& rtx_equal_p (recog_data.operand[use],
702	recog_data.operand[op_alt[def].matched])))
703	continue;
704
705	if (op_alt[use].anything_ok)
706	use_cl = ALL_REGS;
707	else
708	use_cl = op_alt[use].cl;
709	if (use_cl == NO_REGS)
710	continue;
711
712	/* If DEF is simply a tied operand, ignore cases in which this
713	alternative requires USE to have a likely-spilled class.
714	Adding a conflict would just constrain USE further if DEF
715	happens to be allocated first. */
716	if (for_tie_p && targetm.class_likely_spilled_p (use_cl))
717	continue;
718
719	/* If there's any alternative that allows USE to match DEF, do not
720	record a conflict. If that causes us to create an invalid
721	instruction due to the earlyclobber, reload must fix it up.
722
723	Likewise, if we're treating a tied DEF like a partial earlyclobber,
724	do not record a conflict if there's another alternative in which
725	DEF is neither tied nor earlyclobber. */
726	for (alt1 = 0; alt1 < recog_data.n_alternatives; alt1++)
727	{
728	if (!TEST_BIT (preferred_alternatives, alt1))
729	continue;
730	const operand_alternative *op_alt1
731	= &recog_op_alt[alt1 * n_operands];
732	if (op_alt1[use].matches == def
733	|| (use < n_operands - 1
734	&& recog_data.constraints[use][0] == '%'
735	&& op_alt1[use + 1].matches == def)
736	|| (use >= 1
737	&& recog_data.constraints[use - 1][0] == '%'
738	&& op_alt1[use - 1].matches == def))
739	break;
740	if (for_tie_p
741	&& !op_alt1[def].earlyclobber
742	&& op_alt1[def].matched < 0
743	&& alternative_class (alt: op_alt1, i: def) != NO_REGS
744	&& alternative_class (alt: op_alt1, i: use) != NO_REGS)
745	break;
746	}
747
748	if (alt1 < recog_data.n_alternatives)
749	continue;
750
751	advance_p = check_and_make_def_use_conflict (dreg, orig_dreg, def_cl,
752	use, use_cl, advance_p);
753
754	if ((use_match = op_alt[use].matches) >= 0)
755	{
756	gcc_checking_assert (use_match != def);
757
758	if (op_alt[use_match].anything_ok)
759	use_cl = ALL_REGS;
760	else
761	use_cl = op_alt[use_match].cl;
762	advance_p = check_and_make_def_use_conflict (dreg, orig_dreg, def_cl,
763	use, use_cl, advance_p);
764	}
765	}
766	}
767
768	/* Make conflicts of early clobber pseudo registers of the current
769	insn with its inputs. Avoid introducing unnecessary conflicts by
770	checking classes of the constraints and pseudos because otherwise
771	significant code degradation is possible for some targets.
772
773	For these purposes, tying an input to an output makes that output act
774	like an earlyclobber for inputs with a different value, since the output
775	register then has a predetermined purpose on input to the instruction. */
776	static void
777	make_early_clobber_and_input_conflicts (void)
778	{
779	int alt;
780	int def, def_match;
781	enum reg_class def_cl;
782
783	int n_alternatives = recog_data.n_alternatives;
784	int n_operands = recog_data.n_operands;
785	const operand_alternative *op_alt = recog_op_alt;
786	for (alt = 0; alt < n_alternatives; alt++, op_alt += n_operands)
787	if (TEST_BIT (preferred_alternatives, alt))
788	for (def = 0; def < n_operands; def++)
789	{
790	if (op_alt[def].anything_ok)
791	def_cl = ALL_REGS;
792	else
793	def_cl = op_alt[def].cl;
794	if (def_cl != NO_REGS)
795	{
796	if (op_alt[def].earlyclobber)
797	check_and_make_def_conflict (alt, def, def_cl, for_tie_p: false);
798	else if (op_alt[def].matched >= 0
799	&& !targetm.class_likely_spilled_p (def_cl))
800	check_and_make_def_conflict (alt, def, def_cl, for_tie_p: true);
801	}
802
803	if ((def_match = op_alt[def].matches) >= 0
804	&& (op_alt[def_match].earlyclobber
805	|| op_alt[def].earlyclobber))
806	{
807	if (op_alt[def_match].anything_ok)
808	def_cl = ALL_REGS;
809	else
810	def_cl = op_alt[def_match].cl;
811	check_and_make_def_conflict (alt, def, def_cl, for_tie_p: false);
812	}
813	}
814	}
815
816	/* Mark early clobber hard registers of the current INSN as live (if
817	LIVE_P) or dead. Return true if there are such registers. */
818	static bool
819	mark_hard_reg_early_clobbers (rtx_insn *insn, bool live_p)
820	{
821	df_ref def;
822	bool set_p = false;
823
824	FOR_EACH_INSN_DEF (def, insn)
825	if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
826	{
827	rtx dreg = DF_REF_REG (def);
828
829	if (GET_CODE (dreg) == SUBREG)
830	dreg = SUBREG_REG (dreg);
831	if (! REG_P (dreg) || REGNO (dreg) >= FIRST_PSEUDO_REGISTER)
832	continue;
833
834	/* Hard register clobbers are believed to be early clobber
835	because there is no way to say that non-operand hard
836	register clobbers are not early ones. */
837	if (live_p)
838	mark_ref_live (ref: def);
839	else
840	mark_ref_dead (def);
841	set_p = true;
842	}
843
844	return set_p;
845	}
846
847	/* Checks that CONSTRAINTS permits to use only one hard register. If
848	it is so, the function returns the class of the hard register.
849	Otherwise it returns NO_REGS. */
850	static enum reg_class
851	single_reg_class (const char *constraints, rtx op, rtx equiv_const)
852	{
853	int c;
854	enum reg_class cl, next_cl;
855	enum constraint_num cn;
856
857	cl = NO_REGS;
858	alternative_mask preferred = preferred_alternatives;
859	while ((c = *constraints))
860	{
861	if (c == '#')
862	preferred &= ~ALTERNATIVE_BIT (0);
863	else if (c == ',')
864	preferred >>= 1;
865	else if (preferred & 1)
866	switch (c)
867	{
868	case 'g':
869	return NO_REGS;
870
871	default:
872	/* ??? Is this the best way to handle memory constraints? */
873	cn = lookup_constraint (p: constraints);
874	if (insn_extra_memory_constraint (c: cn)
875	|| insn_extra_special_memory_constraint (c: cn)
876	|| insn_extra_relaxed_memory_constraint (cn)
877	|| insn_extra_address_constraint (c: cn))
878	return NO_REGS;
879	if (constraint_satisfied_p (x: op, c: cn)
880	|| (equiv_const != NULL_RTX
881	&& CONSTANT_P (equiv_const)
882	&& constraint_satisfied_p (x: equiv_const, c: cn)))
883	return NO_REGS;
884	next_cl = reg_class_for_constraint (c: cn);
885	if (next_cl == NO_REGS)
886	break;
887	if (cl == NO_REGS
888	? ira_class_singleton[next_cl][GET_MODE (op)] < 0
889	: (ira_class_singleton[cl][GET_MODE (op)]
890	!= ira_class_singleton[next_cl][GET_MODE (op)]))
891	return NO_REGS;
892	cl = next_cl;
893	break;
894
895	case '0': case '1': case '2': case '3': case '4':
896	case '5': case '6': case '7': case '8': case '9':
897	{
898	char *end;
899	unsigned long dup = strtoul (nptr: constraints, endptr: &end, base: 10);
900	constraints = end;
901	next_cl
902	= single_reg_class (constraints: recog_data.constraints[dup],
903	op: recog_data.operand[dup], NULL_RTX);
904	if (cl == NO_REGS
905	? ira_class_singleton[next_cl][GET_MODE (op)] < 0
906	: (ira_class_singleton[cl][GET_MODE (op)]
907	!= ira_class_singleton[next_cl][GET_MODE (op)]))
908	return NO_REGS;
909	cl = next_cl;
910	continue;
911	}
912	}
913	constraints += CONSTRAINT_LEN (c, constraints);
914	}
915	return cl;
916	}
917
918	/* The function checks that operand OP_NUM of the current insn can use
919	only one hard register. If it is so, the function returns the
920	class of the hard register. Otherwise it returns NO_REGS. */
921	static enum reg_class
922	single_reg_operand_class (int op_num)
923	{
924	if (op_num < 0 || recog_data.n_alternatives == 0)
925	return NO_REGS;
926	return single_reg_class (constraints: recog_data.constraints[op_num],
927	op: recog_data.operand[op_num], NULL_RTX);
928	}
929
930	/* The function sets up hard register set *SET to hard registers which
931	might be used by insn reloads because the constraints are too
932	strict. */
933	void
934	ira_implicitly_set_insn_hard_regs (HARD_REG_SET *set,
935	alternative_mask preferred)
936	{
937	int i, c, regno = 0;
938	enum reg_class cl;
939	rtx op;
940	machine_mode mode;
941
942	CLEAR_HARD_REG_SET (set&: *set);
943	for (i = 0; i < recog_data.n_operands; i++)
944	{
945	op = recog_data.operand[i];
946
947	if (GET_CODE (op) == SUBREG)
948	op = SUBREG_REG (op);
949
950	if (GET_CODE (op) == SCRATCH
951	|| (REG_P (op) && (regno = REGNO (op)) >= FIRST_PSEUDO_REGISTER))
952	{
953	const char *p = recog_data.constraints[i];
954
955	mode = (GET_CODE (op) == SCRATCH
956	? GET_MODE (op) : PSEUDO_REGNO_MODE (regno));
957	cl = NO_REGS;
958	for (; (c = *p); p += CONSTRAINT_LEN (c, p))
959	if (c == '#')
960	preferred &= ~ALTERNATIVE_BIT (0);
961	else if (c == ',')
962	preferred >>= 1;
963	else if (preferred & 1)
964	{
965	cl = reg_class_for_constraint (c: lookup_constraint (p));
966	if (cl != NO_REGS)
967	{
968	/* There is no register pressure problem if all of the
969	regs in this class are fixed. */
970	int regno = ira_class_singleton[cl][mode];
971	if (regno >= 0)
972	add_to_hard_reg_set (regs: set, mode, regno);
973	}
974	}
975	}
976	}
977	}
978	/* Processes input operands, if IN_P, or output operands otherwise of
979	the current insn with FREQ to find allocno which can use only one
980	hard register and makes other currently living allocnos conflicting
981	with the hard register. */
982	static void
983	process_single_reg_class_operands (bool in_p, int freq)
984	{
985	int i, regno;
986	unsigned int px;
987	enum reg_class cl;
988	rtx operand;
989	ira_allocno_t operand_a, a;
990
991	for (i = 0; i < recog_data.n_operands; i++)
992	{
993	operand = recog_data.operand[i];
994	if (in_p && recog_data.operand_type[i] != OP_IN
995	&& recog_data.operand_type[i] != OP_INOUT)
996	continue;
997	if (! in_p && recog_data.operand_type[i] != OP_OUT
998	&& recog_data.operand_type[i] != OP_INOUT)
999	continue;
1000	cl = single_reg_operand_class (op_num: i);
1001	if (cl == NO_REGS)
1002	continue;
1003
1004	operand_a = NULL;
1005
1006	if (GET_CODE (operand) == SUBREG)
1007	operand = SUBREG_REG (operand);
1008
1009	if (REG_P (operand)
1010	&& (regno = REGNO (operand)) >= FIRST_PSEUDO_REGISTER)
1011	{
1012	enum reg_class aclass;
1013
1014	operand_a = ira_curr_regno_allocno_map[regno];
1015	aclass = ALLOCNO_CLASS (operand_a);
1016	if (ira_class_subset_p[cl][aclass])
1017	{
1018	/* View the desired allocation of OPERAND as:
1019
1020	(REG:YMODE YREGNO),
1021
1022	a simplification of:
1023
1024	(subreg:YMODE (reg:XMODE XREGNO) OFFSET). */
1025	machine_mode ymode, xmode;
1026	int xregno, yregno;
1027	poly_int64 offset;
1028
1029	xmode = recog_data.operand_mode[i];
1030	xregno = ira_class_singleton[cl][xmode];
1031	gcc_assert (xregno >= 0);
1032	ymode = ALLOCNO_MODE (operand_a);
1033	offset = subreg_lowpart_offset (outermode: ymode, innermode: xmode);
1034	yregno = simplify_subreg_regno (xregno, xmode, offset, ymode);
1035	if (yregno >= 0
1036	&& ira_class_hard_reg_index[aclass][yregno] >= 0)
1037	{
1038	int cost;
1039
1040	ira_allocate_and_set_costs
1041	(vec: &ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a),
1042	aclass, val: 0);
1043	ira_init_register_move_cost_if_necessary (mode: xmode);
1044	cost = freq * (in_p
1045	? ira_register_move_cost[xmode][aclass][cl]
1046	: ira_register_move_cost[xmode][cl][aclass]);
1047	ALLOCNO_CONFLICT_HARD_REG_COSTS (operand_a)
1048	[ira_class_hard_reg_index[aclass][yregno]] -= cost;
1049	}
1050	}
1051	}
1052
1053	EXECUTE_IF_SET_IN_SPARSESET (objects_live, px)
1054	{
1055	ira_object_t obj = ira_object_id_map[px];
1056	a = OBJECT_ALLOCNO (obj);
1057	if (a != operand_a)
1058	{
1059	/* We could increase costs of A instead of making it
1060	conflicting with the hard register. But it works worse
1061	because it will be spilled in reload in anyway. */
1062	OBJECT_CONFLICT_HARD_REGS (obj) |= reg_class_contents[cl];
1063	OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= reg_class_contents[cl];
1064	}
1065	}
1066	}
1067	}
1068
1069	/* Look through the CALL_INSN_FUNCTION_USAGE of a call insn INSN, and see if
1070	we find a SET rtx that we can use to deduce that a register can be cheaply
1071	caller-saved. Return such a register, or NULL_RTX if none is found. */
1072	static rtx
1073	find_call_crossed_cheap_reg (rtx_insn *insn)
1074	{
1075	rtx cheap_reg = NULL_RTX;
1076	rtx exp = CALL_INSN_FUNCTION_USAGE (insn);
1077
1078	while (exp != NULL)
1079	{
1080	rtx x = XEXP (exp, 0);
1081	if (GET_CODE (x) == SET)
1082	{
1083	exp = x;
1084	break;
1085	}
1086	exp = XEXP (exp, 1);
1087	}
1088	if (exp != NULL)
1089	{
1090	basic_block bb = BLOCK_FOR_INSN (insn);
1091	rtx reg = SET_SRC (exp);
1092	rtx_insn *prev = PREV_INSN (insn);
1093	while (prev && !(INSN_P (prev)
1094	&& BLOCK_FOR_INSN (insn: prev) != bb))
1095	{
1096	if (NONDEBUG_INSN_P (prev))
1097	{
1098	rtx set = single_set (insn: prev);
1099
1100	if (set && rtx_equal_p (SET_DEST (set), reg))
1101	{
1102	rtx src = SET_SRC (set);
1103	if (!REG_P (src) || HARD_REGISTER_P (src)
1104	|| !pseudo_regno_single_word_and_live_p (REGNO (src)))
1105	break;
1106	if (!modified_between_p (src, prev, insn))
1107	cheap_reg = src;
1108	break;
1109	}
1110	if (set && rtx_equal_p (SET_SRC (set), reg))
1111	{
1112	rtx dest = SET_DEST (set);
1113	if (!REG_P (dest) || HARD_REGISTER_P (dest)
1114	|| !pseudo_regno_single_word_and_live_p (REGNO (dest)))
1115	break;
1116	if (!modified_between_p (dest, prev, insn))
1117	cheap_reg = dest;
1118	break;
1119	}
1120
1121	if (reg_set_p (reg, prev))
1122	break;
1123	}
1124	prev = PREV_INSN (insn: prev);
1125	}
1126	}
1127	return cheap_reg;
1128	}
1129
1130	/* Determine whether INSN is a register to register copy of the type where
1131	we do not need to make the source and destiniation registers conflict.
1132	If this is a copy instruction, then return the source reg. Otherwise,
1133	return NULL_RTX. */
1134	rtx
1135	non_conflicting_reg_copy_p (rtx_insn *insn)
1136	{
1137	/* Reload has issues with overlapping pseudos being assigned to the
1138	same hard register, so don't allow it. See PR87600 for details. */
1139	if (!targetm.lra_p ())
1140	return NULL_RTX;
1141
1142	rtx set = single_set (insn);
1143
1144	/* Disallow anything other than a simple register to register copy
1145	that has no side effects. */
1146	if (set == NULL_RTX
1147	|| !REG_P (SET_DEST (set))
1148	|| !REG_P (SET_SRC (set))
1149	|| side_effects_p (set))
1150	return NULL_RTX;
1151
1152	int dst_regno = REGNO (SET_DEST (set));
1153	int src_regno = REGNO (SET_SRC (set));
1154	machine_mode mode = GET_MODE (SET_DEST (set));
1155
1156	/* By definition, a register does not conflict with itself, therefore we
1157	do not have to handle it specially. Returning NULL_RTX now, helps
1158	simplify the callers of this function. */
1159	if (dst_regno == src_regno)
1160	return NULL_RTX;
1161
1162	/* Computing conflicts for register pairs is difficult to get right, so
1163	for now, disallow it. */
1164	if ((HARD_REGISTER_NUM_P (dst_regno)
1165	&& hard_regno_nregs (regno: dst_regno, mode) != 1)
1166	|| (HARD_REGISTER_NUM_P (src_regno)
1167	&& hard_regno_nregs (regno: src_regno, mode) != 1))
1168	return NULL_RTX;
1169
1170	return SET_SRC (set);
1171	}
1172
1173	#ifdef EH_RETURN_DATA_REGNO
1174
1175	/* Add EH return hard registers as conflict hard registers to allocnos
1176	living at end of BB. For most allocnos it is already done in
1177	process_bb_node_lives when we processing input edges but it does
1178	not work when and EH edge is edge out of the current region. This
1179	function covers such out of region edges. */
1180	static void
1181	process_out_of_region_eh_regs (basic_block bb)
1182	{
1183	edge e;
1184	edge_iterator ei;
1185	unsigned int i;
1186	bitmap_iterator bi;
1187	bool eh_p = false;
1188
1189	FOR_EACH_EDGE (e, ei, bb->succs)
1190	if ((e->flags & EDGE_EH)
1191	&& IRA_BB_NODE (e->dest)->parent != IRA_BB_NODE (bb)->parent)
1192	eh_p = true;
1193
1194	if (! eh_p)
1195	return;
1196
1197	EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb), FIRST_PSEUDO_REGISTER, i, bi)
1198	{
1199	ira_allocno_t a = ira_curr_regno_allocno_map[i];
1200	for (int n = ALLOCNO_NUM_OBJECTS (a) - 1; n >= 0; n--)
1201	{
1202	ira_object_t obj = ALLOCNO_OBJECT (a, n);
1203	for (int k = 0; ; k++)
1204	{
1205	unsigned int regno = EH_RETURN_DATA_REGNO (k);
1206	if (regno == INVALID_REGNUM)
1207	break;
1208	SET_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj), bit: regno);
1209	SET_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), bit: regno);
1210	}
1211	}
1212	}
1213	}
1214
1215	#endif
1216
1217	/* Add conflicts for object OBJ from REGION landing pads using CALLEE_ABI. */
1218	static void
1219	add_conflict_from_region_landing_pads (eh_region region, ira_object_t obj,
1220	function_abi callee_abi)
1221	{
1222	ira_allocno_t a = OBJECT_ALLOCNO (obj);
1223	rtx_code_label *landing_label;
1224	basic_block landing_bb;
1225
1226	for (eh_landing_pad lp = region->landing_pads; lp ; lp = lp->next_lp)
1227	{
1228	if ((landing_label = lp->landing_pad) != NULL
1229	&& (landing_bb = BLOCK_FOR_INSN (insn: landing_label)) != NULL
1230	&& (region->type != ERT_CLEANUP
1231	|| bitmap_bit_p (df_get_live_in (bb: landing_bb),
1232	ALLOCNO_REGNO (a))))
1233	{
1234	HARD_REG_SET new_conflict_regs
1235	= callee_abi.mode_clobbers (ALLOCNO_MODE (a));
1236	OBJECT_CONFLICT_HARD_REGS (obj) |= new_conflict_regs;
1237	OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= new_conflict_regs;
1238	return;
1239	}
1240	}
1241	}
1242
1243	/* Process insns of the basic block given by its LOOP_TREE_NODE to
1244	update allocno live ranges, allocno hard register conflicts,
1245	intersected calls, and register pressure info for allocnos for the
1246	basic block for and regions containing the basic block. */
1247	static void
1248	process_bb_node_lives (ira_loop_tree_node_t loop_tree_node)
1249	{
1250	int i, freq;
1251	unsigned int j;
1252	basic_block bb;
1253	rtx_insn *insn;
1254	bitmap_iterator bi;
1255	bitmap reg_live_out;
1256	unsigned int px;
1257	bool set_p;
1258
1259	bb = loop_tree_node->bb;
1260	if (bb != NULL)
1261	{
1262	for (i = 0; i < ira_pressure_classes_num; i++)
1263	{
1264	curr_reg_pressure[ira_pressure_classes[i]] = 0;
1265	high_pressure_start_point[ira_pressure_classes[i]] = -1;
1266	}
1267	curr_bb_node = loop_tree_node;
1268	reg_live_out = df_get_live_out (bb);
1269	sparseset_clear (s: objects_live);
1270	REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
1271	hard_regs_live &= ~(eliminable_regset | ira_no_alloc_regs);
1272	for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1273	if (TEST_HARD_REG_BIT (set: hard_regs_live, bit: i))
1274	{
1275	enum reg_class aclass, pclass, cl;
1276
1277	aclass = ira_allocno_class_translate[REGNO_REG_CLASS (i)];
1278	pclass = ira_pressure_class_translate[aclass];
1279	for (j = 0;
1280	(cl = ira_reg_class_super_classes[pclass][j])
1281	!= LIM_REG_CLASSES;
1282	j++)
1283	{
1284	if (! ira_reg_pressure_class_p[cl])
1285	continue;
1286	curr_reg_pressure[cl]++;
1287	if (curr_bb_node->reg_pressure[cl] < curr_reg_pressure[cl])
1288	curr_bb_node->reg_pressure[cl] = curr_reg_pressure[cl];
1289	ira_assert (curr_reg_pressure[cl]
1290	<= ira_class_hard_regs_num[cl]);
1291	}
1292	}
1293	EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
1294	mark_pseudo_regno_live (regno: j);
1295
1296	#ifdef EH_RETURN_DATA_REGNO
1297	process_out_of_region_eh_regs (bb);
1298	#endif
1299
1300	freq = REG_FREQ_FROM_BB (bb);
1301	if (freq == 0)
1302	freq = 1;
1303
1304	/* Invalidate all allocno_saved_at_call entries. */
1305	last_call_num++;
1306
1307	/* Scan the code of this basic block, noting which allocnos and
1308	hard regs are born or die.
1309
1310	Note that this loop treats uninitialized values as live until
1311	the beginning of the block. For example, if an instruction
1312	uses (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever
1313	set, FOO will remain live until the beginning of the block.
1314	Likewise if FOO is not set at all. This is unnecessarily
1315	pessimistic, but it probably doesn't matter much in practice. */
1316	FOR_BB_INSNS_REVERSE (bb, insn)
1317	{
1318	ira_allocno_t a;
1319	df_ref def, use;
1320	bool call_p;
1321
1322	if (!NONDEBUG_INSN_P (insn))
1323	continue;
1324
1325	if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1326	fprintf (stream: ira_dump_file, format: " Insn %u(l%d): point = %d\n",
1327	INSN_UID (insn), loop_tree_node->parent->loop_num,
1328	curr_point);
1329
1330	call_p = CALL_P (insn);
1331	ignore_reg_for_conflicts = non_conflicting_reg_copy_p (insn);
1332
1333	/* Mark each defined value as live. We need to do this for
1334	unused values because they still conflict with quantities
1335	that are live at the time of the definition.
1336
1337	Ignore DF_REF_MAY_CLOBBERs on a call instruction. Such
1338	references represent the effect of the called function
1339	on a call-clobbered register. Marking the register as
1340	live would stop us from allocating it to a call-crossing
1341	allocno. */
1342	FOR_EACH_INSN_DEF (def, insn)
1343	if (!call_p || !DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1344	mark_ref_live (ref: def);
1345
1346	/* If INSN has multiple outputs, then any value used in one
1347	of the outputs conflicts with the other outputs. Model this
1348	by making the used value live during the output phase.
1349
1350	It is unsafe to use !single_set here since it will ignore
1351	an unused output. Just because an output is unused does
1352	not mean the compiler can assume the side effect will not
1353	occur. Consider if ALLOCNO appears in the address of an
1354	output and we reload the output. If we allocate ALLOCNO
1355	to the same hard register as an unused output we could
1356	set the hard register before the output reload insn. */
1357	if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn))
1358	FOR_EACH_INSN_USE (use, insn)
1359	{
1360	int i;
1361	rtx reg;
1362
1363	reg = DF_REF_REG (use);
1364	for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
1365	{
1366	rtx set;
1367
1368	set = XVECEXP (PATTERN (insn), 0, i);
1369	if (GET_CODE (set) == SET
1370	&& reg_overlap_mentioned_p (reg, SET_DEST (set)))
1371	{
1372	/* After the previous loop, this is a no-op if
1373	REG is contained within SET_DEST (SET). */
1374	mark_ref_live (ref: use);
1375	break;
1376	}
1377	}
1378	}
1379
1380	preferred_alternatives = ira_setup_alts (insn);
1381	process_single_reg_class_operands (in_p: false, freq);
1382
1383	if (call_p)
1384	{
1385	/* Try to find a SET in the CALL_INSN_FUNCTION_USAGE, and from
1386	there, try to find a pseudo that is live across the call but
1387	can be cheaply reconstructed from the return value. */
1388	rtx cheap_reg = find_call_crossed_cheap_reg (insn);
1389	if (cheap_reg != NULL_RTX)
1390	add_reg_note (insn, REG_RETURNED, cheap_reg);
1391
1392	last_call_num++;
1393	sparseset_clear (s: allocnos_processed);
1394	/* The current set of live allocnos are live across the call. */
1395	EXECUTE_IF_SET_IN_SPARSESET (objects_live, i)
1396	{
1397	ira_object_t obj = ira_object_id_map[i];
1398	a = OBJECT_ALLOCNO (obj);
1399	int num = ALLOCNO_NUM (a);
1400	function_abi callee_abi = insn_callee_abi (insn);
1401
1402	/* Don't allocate allocnos that cross setjmps or any
1403	call, if this function receives a nonlocal
1404	goto. */
1405	if (cfun->has_nonlocal_label
1406	|| (!targetm.setjmp_preserves_nonvolatile_regs_p ()
1407	&& (find_reg_note (insn, REG_SETJMP, NULL_RTX)
1408	!= NULL_RTX)))
1409	{
1410	SET_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj));
1411	SET_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
1412	}
1413	eh_region r;
1414	if (can_throw_internal (insn)
1415	&& (r = get_eh_region_from_rtx (insn)) != NULL)
1416	add_conflict_from_region_landing_pads (region: r, obj, callee_abi);
1417	if (sparseset_bit_p (s: allocnos_processed, e: num))
1418	continue;
1419	sparseset_set_bit (s: allocnos_processed, e: num);
1420
1421	if (allocno_saved_at_call[num] != last_call_num)
1422	/* Here we are mimicking caller-save.cc behavior
1423	which does not save hard register at a call if
1424	it was saved on previous call in the same basic
1425	block and the hard register was not mentioned
1426	between the two calls. */
1427	ALLOCNO_CALL_FREQ (a) += freq;
1428	/* Mark it as saved at the next call. */
1429	allocno_saved_at_call[num] = last_call_num + 1;
1430	ALLOCNO_CALLS_CROSSED_NUM (a)++;
1431	ALLOCNO_CROSSED_CALLS_ABIS (a) |= 1 << callee_abi.id ();
1432	ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a)
1433	|= callee_abi.full_and_partial_reg_clobbers ();
1434	if (cheap_reg != NULL_RTX
1435	&& ALLOCNO_REGNO (a) == (int) REGNO (cheap_reg))
1436	ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a)++;
1437	}
1438	}
1439
1440	/* See which defined values die here. Note that we include
1441	the call insn in the lifetimes of these values, so we don't
1442	mistakenly consider, for e.g. an addressing mode with a
1443	side-effect like a post-increment fetching the address,
1444	that the use happens before the call, and the def to happen
1445	after the call: we believe both to happen before the actual
1446	call. (We don't handle return-values here.) */
1447	FOR_EACH_INSN_DEF (def, insn)
1448	if (!call_p || !DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1449	mark_ref_dead (def);
1450
1451	make_early_clobber_and_input_conflicts ();
1452
1453	curr_point++;
1454
1455	/* Mark each used value as live. */
1456	FOR_EACH_INSN_USE (use, insn)
1457	mark_ref_live (ref: use);
1458
1459	process_single_reg_class_operands (in_p: true, freq);
1460
1461	set_p = mark_hard_reg_early_clobbers (insn, live_p: true);
1462
1463	if (set_p)
1464	{
1465	mark_hard_reg_early_clobbers (insn, live_p: false);
1466
1467	/* Mark each hard reg as live again. For example, a
1468	hard register can be in clobber and in an insn
1469	input. */
1470	FOR_EACH_INSN_USE (use, insn)
1471	{
1472	rtx ureg = DF_REF_REG (use);
1473
1474	if (GET_CODE (ureg) == SUBREG)
1475	ureg = SUBREG_REG (ureg);
1476	if (! REG_P (ureg) || REGNO (ureg) >= FIRST_PSEUDO_REGISTER)
1477	continue;
1478
1479	mark_ref_live (ref: use);
1480	}
1481	}
1482
1483	curr_point++;
1484	}
1485	ignore_reg_for_conflicts = NULL_RTX;
1486
1487	if (bb_has_eh_pred (bb))
1488	for (j = 0; ; ++j)
1489	{
1490	unsigned int regno = EH_RETURN_DATA_REGNO (j);
1491	if (regno == INVALID_REGNUM)
1492	break;
1493	make_hard_regno_live (regno);
1494	}
1495
1496	/* Allocnos can't go in stack regs at the start of a basic block
1497	that is reached by an abnormal edge. Likewise for registers
1498	that are at least partly call clobbered, because caller-save,
1499	fixup_abnormal_edges and possibly the table driven EH machinery
1500	are not quite ready to handle such allocnos live across such
1501	edges. */
1502	if (bb_has_abnormal_pred (bb))
1503	{
1504	#ifdef STACK_REGS
1505	EXECUTE_IF_SET_IN_SPARSESET (objects_live, px)
1506	{
1507	ira_allocno_t a = OBJECT_ALLOCNO (ira_object_id_map[px]);
1508
1509	ALLOCNO_NO_STACK_REG_P (a) = true;
1510	ALLOCNO_TOTAL_NO_STACK_REG_P (a) = true;
1511	}
1512	for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
1513	make_hard_regno_live (regno: px);
1514	#endif
1515	/* No need to record conflicts for call clobbered regs if we
1516	have nonlocal labels around, as we don't ever try to
1517	allocate such regs in this case. */
1518	if (!cfun->has_nonlocal_label
1519	&& has_abnormal_call_or_eh_pred_edge_p (bb))
1520	for (px = 0; px < FIRST_PSEUDO_REGISTER; px++)
1521	if (eh_edge_abi.clobbers_at_least_part_of_reg_p (regno: px)
1522	#ifdef REAL_PIC_OFFSET_TABLE_REGNUM
1523	/* We should create a conflict of PIC pseudo with
1524	PIC hard reg as PIC hard reg can have a wrong
1525	value after jump described by the abnormal edge.
1526	In this case we cannot allocate PIC hard reg to
1527	PIC pseudo as PIC pseudo will also have a wrong
1528	value. This code is not critical as LRA can fix
1529	it but it is better to have the right allocation
1530	earlier. */
1531	|| (px == REAL_PIC_OFFSET_TABLE_REGNUM
1532	&& pic_offset_table_rtx != NULL_RTX
1533	&& REGNO (pic_offset_table_rtx) >= FIRST_PSEUDO_REGISTER)
1534	#endif
1535	)
1536	make_hard_regno_live (regno: px);
1537	}
1538
1539	EXECUTE_IF_SET_IN_SPARSESET (objects_live, i)
1540	make_object_dead (obj: ira_object_id_map[i]);
1541
1542	curr_point++;
1543
1544	}
1545	/* Propagate register pressure to upper loop tree nodes. */
1546	if (loop_tree_node != ira_loop_tree_root)
1547	for (i = 0; i < ira_pressure_classes_num; i++)
1548	{
1549	enum reg_class pclass;
1550
1551	pclass = ira_pressure_classes[i];
1552	if (loop_tree_node->reg_pressure[pclass]
1553	> loop_tree_node->parent->reg_pressure[pclass])
1554	loop_tree_node->parent->reg_pressure[pclass]
1555	= loop_tree_node->reg_pressure[pclass];
1556	}
1557	}
1558
1559	/* Create and set up IRA_START_POINT_RANGES and
1560	IRA_FINISH_POINT_RANGES. */
1561	static void
1562	create_start_finish_chains (void)
1563	{
1564	ira_object_t obj;
1565	ira_object_iterator oi;
1566	live_range_t r;
1567
1568	ira_start_point_ranges
1569	= (live_range_t *) ira_allocate (ira_max_point * sizeof (live_range_t));
1570	memset (s: ira_start_point_ranges, c: 0, n: ira_max_point * sizeof (live_range_t));
1571	ira_finish_point_ranges
1572	= (live_range_t *) ira_allocate (ira_max_point * sizeof (live_range_t));
1573	memset (s: ira_finish_point_ranges, c: 0, n: ira_max_point * sizeof (live_range_t));
1574	FOR_EACH_OBJECT (obj, oi)
1575	for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
1576	{
1577	r->start_next = ira_start_point_ranges[r->start];
1578	ira_start_point_ranges[r->start] = r;
1579	r->finish_next = ira_finish_point_ranges[r->finish];
1580	ira_finish_point_ranges[r->finish] = r;
1581	}
1582	}
1583
1584	/* Rebuild IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES after
1585	new live ranges and program points were added as a result if new
1586	insn generation. */
1587	void
1588	ira_rebuild_start_finish_chains (void)
1589	{
1590	ira_free (addr: ira_finish_point_ranges);
1591	ira_free (addr: ira_start_point_ranges);
1592	create_start_finish_chains ();
1593	}
1594
1595	/* Compress allocno live ranges by removing program points where
1596	nothing happens. */
1597	static void
1598	remove_some_program_points_and_update_live_ranges (void)
1599	{
1600	unsigned i;
1601	int n;
1602	int *map;
1603	ira_object_t obj;
1604	ira_object_iterator oi;
1605	live_range_t r, prev_r, next_r;
1606	sbitmap_iterator sbi;
1607	bool born_p, dead_p, prev_born_p, prev_dead_p;
1608
1609	auto_sbitmap born (ira_max_point);
1610	auto_sbitmap dead (ira_max_point);
1611	bitmap_clear (born);
1612	bitmap_clear (dead);
1613	FOR_EACH_OBJECT (obj, oi)
1614	for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
1615	{
1616	ira_assert (r->start <= r->finish);
1617	bitmap_set_bit (map: born, bitno: r->start);
1618	bitmap_set_bit (map: dead, bitno: r->finish);
1619	}
1620
1621	auto_sbitmap born_or_dead (ira_max_point);
1622	bitmap_ior (born_or_dead, born, dead);
1623	map = (int *) ira_allocate (sizeof (int) * ira_max_point);
1624	n = -1;
1625	prev_born_p = prev_dead_p = false;
1626	EXECUTE_IF_SET_IN_BITMAP (born_or_dead, 0, i, sbi)
1627	{
1628	born_p = bitmap_bit_p (map: born, bitno: i);
1629	dead_p = bitmap_bit_p (map: dead, bitno: i);
1630	if ((prev_born_p && ! prev_dead_p && born_p && ! dead_p)
1631	|| (prev_dead_p && ! prev_born_p && dead_p && ! born_p))
1632	map[i] = n;
1633	else
1634	map[i] = ++n;
1635	prev_born_p = born_p;
1636	prev_dead_p = dead_p;
1637	}
1638
1639	n++;
1640	if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1641	fprintf (stream: ira_dump_file, format: "Compressing live ranges: from %d to %d - %d%%\n",
1642	ira_max_point, n, 100 * n / ira_max_point);
1643	ira_max_point = n;
1644
1645	FOR_EACH_OBJECT (obj, oi)
1646	for (r = OBJECT_LIVE_RANGES (obj), prev_r = NULL; r != NULL; r = next_r)
1647	{
1648	next_r = r->next;
1649	r->start = map[r->start];
1650	r->finish = map[r->finish];
1651	if (prev_r == NULL || prev_r->start > r->finish + 1)
1652	{
1653	prev_r = r;
1654	continue;
1655	}
1656	prev_r->start = r->start;
1657	prev_r->next = next_r;
1658	ira_finish_live_range (r);
1659	}
1660
1661	ira_free (addr: map);
1662	}
1663
1664	/* Print live ranges R to file F. */
1665	void
1666	ira_print_live_range_list (FILE *f, live_range_t r)
1667	{
1668	for (; r != NULL; r = r->next)
1669	fprintf (stream: f, format: " [%d..%d]", r->start, r->finish);
1670	fprintf (stream: f, format: "\n");
1671	}
1672
1673	DEBUG_FUNCTION void
1674	debug (live_range &ref)
1675	{
1676	ira_print_live_range_list (stderr, r: &ref);
1677	}
1678
1679	DEBUG_FUNCTION void
1680	debug (live_range *ptr)
1681	{
1682	if (ptr)
1683	debug (ref&: *ptr);
1684	else
1685	fprintf (stderr, format: "<nil>\n");
1686	}
1687
1688	/* Print live ranges R to stderr. */
1689	void
1690	ira_debug_live_range_list (live_range_t r)
1691	{
1692	ira_print_live_range_list (stderr, r);
1693	}
1694
1695	/* Print live ranges of object OBJ to file F. */
1696	static void
1697	print_object_live_ranges (FILE *f, ira_object_t obj)
1698	{
1699	ira_print_live_range_list (f, OBJECT_LIVE_RANGES (obj));
1700	}
1701
1702	/* Print live ranges of allocno A to file F. */
1703	static void
1704	print_allocno_live_ranges (FILE *f, ira_allocno_t a)
1705	{
1706	int n = ALLOCNO_NUM_OBJECTS (a);
1707	int i;
1708
1709	for (i = 0; i < n; i++)
1710	{
1711	fprintf (stream: f, format: " a%d(r%d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
1712	if (n > 1)
1713	fprintf (stream: f, format: " [%d]", i);
1714	fprintf (stream: f, format: "):");
1715	print_object_live_ranges (f, ALLOCNO_OBJECT (a, i));
1716	}
1717	}
1718
1719	/* Print live ranges of allocno A to stderr. */
1720	void
1721	ira_debug_allocno_live_ranges (ira_allocno_t a)
1722	{
1723	print_allocno_live_ranges (stderr, a);
1724	}
1725
1726	/* Print live ranges of all allocnos to file F. */
1727	static void
1728	print_live_ranges (FILE *f)
1729	{
1730	ira_allocno_t a;
1731	ira_allocno_iterator ai;
1732
1733	FOR_EACH_ALLOCNO (a, ai)
1734	print_allocno_live_ranges (f, a);
1735	}
1736
1737	/* Print live ranges of all allocnos to stderr. */
1738	void
1739	ira_debug_live_ranges (void)
1740	{
1741	print_live_ranges (stderr);
1742	}
1743
1744	/* The main entry function creates live ranges, set up
1745	CONFLICT_HARD_REGS and TOTAL_CONFLICT_HARD_REGS for objects, and
1746	calculate register pressure info. */
1747	void
1748	ira_create_allocno_live_ranges (void)
1749	{
1750	objects_live = sparseset_alloc (n_elms: ira_objects_num);
1751	allocnos_processed = sparseset_alloc (n_elms: ira_allocnos_num);
1752	curr_point = 0;
1753	last_call_num = 0;
1754	allocno_saved_at_call
1755	= (int *) ira_allocate (ira_allocnos_num * sizeof (int));
1756	memset (s: allocno_saved_at_call, c: 0, n: ira_allocnos_num * sizeof (int));
1757	ira_traverse_loop_tree (true, ira_loop_tree_root, NULL,
1758	process_bb_node_lives);
1759	ira_max_point = curr_point;
1760	create_start_finish_chains ();
1761	if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1762	print_live_ranges (f: ira_dump_file);
1763	/* Clean up. */
1764	ira_free (addr: allocno_saved_at_call);
1765	sparseset_free (objects_live);
1766	sparseset_free (allocnos_processed);
1767	}
1768
1769	/* Compress allocno live ranges. */
1770	void
1771	ira_compress_allocno_live_ranges (void)
1772	{
1773	remove_some_program_points_and_update_live_ranges ();
1774	ira_rebuild_start_finish_chains ();
1775	if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1776	{
1777	fprintf (stream: ira_dump_file, format: "Ranges after the compression:\n");
1778	print_live_ranges (f: ira_dump_file);
1779	}
1780	}
1781
1782	/* Free arrays IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES. */
1783	void
1784	ira_finish_allocno_live_ranges (void)
1785	{
1786	ira_free (addr: ira_finish_point_ranges);
1787	ira_free (addr: ira_start_point_ranges);
1788	}
1789