1	/* IRA processing allocno lives to build allocno live ranges.
2	Copyright (C) 2006-2024 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	/* Go through the operands of the extracted insn looking for operand
1070	alternatives that apply a register filter. Record any such filters
1071	in the operand's allocno. */
1072	static void
1073	process_register_constraint_filters ()
1074	{
1075	for (int opno = 0; opno < recog_data.n_operands; ++opno)
1076	{
1077	rtx op = recog_data.operand[opno];
1078	if (SUBREG_P (op))
1079	op = SUBREG_REG (op);
1080	if (REG_P (op) && !HARD_REGISTER_P (op))
1081	{
1082	ira_allocno_t a = ira_curr_regno_allocno_map[REGNO (op)];
1083	for (int alt = 0; alt < recog_data.n_alternatives; alt++)
1084	{
1085	if (!TEST_BIT (preferred_alternatives, alt))
1086	continue;
1087
1088	auto *op_alt = &recog_op_alt[alt * recog_data.n_operands];
1089	auto cl = alternative_class (alt: op_alt, i: opno);
1090	/* The two extremes are easy:
1091
1092	- We should record the filter if CL matches the
1093	allocno class.
1094
1095	- We should ignore the filter if CL and the allocno class
1096	are disjoint. We'll either pick a different alternative
1097	or reload the operand.
1098
1099	Things are trickier if the classes overlap. However:
1100
1101	- If the allocno class includes registers that are not
1102	in CL, some choices of hard register will need a reload
1103	anyway. It isn't obvious that reloads due to filters
1104	are worse than reloads due to regnos being outside CL.
1105
1106	- Conversely, if the allocno class is a subset of CL,
1107	any allocation will satisfy the class requirement.
1108	We should try to make sure it satisfies the filter
1109	requirement too. This is useful if, for example,
1110	an allocno needs to be in "low" registers to satisfy
1111	some uses, and its allocno class is therefore those
1112	low registers, but the allocno is elsewhere allowed
1113	to be in any even-numbered register. Picking an
1114	even-numbered low register satisfies both types of use. */
1115	if (!ira_class_subset_p[ALLOCNO_CLASS (a)][cl])
1116	continue;
1117
1118	auto filters = alternative_register_filters (alt: op_alt, i: opno);
1119	if (!filters)
1120	continue;
1121
1122	filters |= ALLOCNO_REGISTER_FILTERS (a);
1123	ALLOCNO_SET_REGISTER_FILTERS (a, filters);
1124	}
1125	}
1126	}
1127	}
1128
1129	/* Look through the CALL_INSN_FUNCTION_USAGE of a call insn INSN, and see if
1130	we find a SET rtx that we can use to deduce that a register can be cheaply
1131	caller-saved. Return such a register, or NULL_RTX if none is found. */
1132	static rtx
1133	find_call_crossed_cheap_reg (rtx_insn *insn)
1134	{
1135	rtx cheap_reg = NULL_RTX;
1136	rtx exp = CALL_INSN_FUNCTION_USAGE (insn);
1137
1138	while (exp != NULL)
1139	{
1140	rtx x = XEXP (exp, 0);
1141	if (GET_CODE (x) == SET)
1142	{
1143	exp = x;
1144	break;
1145	}
1146	exp = XEXP (exp, 1);
1147	}
1148	if (exp != NULL)
1149	{
1150	basic_block bb = BLOCK_FOR_INSN (insn);
1151	rtx reg = SET_SRC (exp);
1152	rtx_insn *prev = PREV_INSN (insn);
1153	while (prev && !(INSN_P (prev)
1154	&& BLOCK_FOR_INSN (insn: prev) != bb))
1155	{
1156	if (NONDEBUG_INSN_P (prev))
1157	{
1158	rtx set = single_set (insn: prev);
1159
1160	if (set && rtx_equal_p (SET_DEST (set), reg))
1161	{
1162	rtx src = SET_SRC (set);
1163	if (!REG_P (src) || HARD_REGISTER_P (src)
1164	|| !pseudo_regno_single_word_and_live_p (REGNO (src)))
1165	break;
1166	if (!modified_between_p (src, prev, insn))
1167	cheap_reg = src;
1168	break;
1169	}
1170	if (set && rtx_equal_p (SET_SRC (set), reg))
1171	{
1172	rtx dest = SET_DEST (set);
1173	if (!REG_P (dest) || HARD_REGISTER_P (dest)
1174	|| !pseudo_regno_single_word_and_live_p (REGNO (dest)))
1175	break;
1176	if (!modified_between_p (dest, prev, insn))
1177	cheap_reg = dest;
1178	break;
1179	}
1180
1181	if (reg_set_p (reg, prev))
1182	break;
1183	}
1184	prev = PREV_INSN (insn: prev);
1185	}
1186	}
1187	return cheap_reg;
1188	}
1189
1190	/* Determine whether INSN is a register to register copy of the type where
1191	we do not need to make the source and destiniation registers conflict.
1192	If this is a copy instruction, then return the source reg. Otherwise,
1193	return NULL_RTX. */
1194	rtx
1195	non_conflicting_reg_copy_p (rtx_insn *insn)
1196	{
1197	/* Reload has issues with overlapping pseudos being assigned to the
1198	same hard register, so don't allow it. See PR87600 for details. */
1199	if (!targetm.lra_p ())
1200	return NULL_RTX;
1201
1202	rtx set = single_set (insn);
1203
1204	/* Disallow anything other than a simple register to register copy
1205	that has no side effects. */
1206	if (set == NULL_RTX
1207	|| !REG_P (SET_DEST (set))
1208	|| !REG_P (SET_SRC (set))
1209	|| side_effects_p (set))
1210	return NULL_RTX;
1211
1212	int dst_regno = REGNO (SET_DEST (set));
1213	int src_regno = REGNO (SET_SRC (set));
1214	machine_mode mode = GET_MODE (SET_DEST (set));
1215
1216	/* By definition, a register does not conflict with itself, therefore we
1217	do not have to handle it specially. Returning NULL_RTX now, helps
1218	simplify the callers of this function. */
1219	if (dst_regno == src_regno)
1220	return NULL_RTX;
1221
1222	/* Computing conflicts for register pairs is difficult to get right, so
1223	for now, disallow it. */
1224	if ((HARD_REGISTER_NUM_P (dst_regno)
1225	&& hard_regno_nregs (regno: dst_regno, mode) != 1)
1226	|| (HARD_REGISTER_NUM_P (src_regno)
1227	&& hard_regno_nregs (regno: src_regno, mode) != 1))
1228	return NULL_RTX;
1229
1230	return SET_SRC (set);
1231	}
1232
1233	#ifdef EH_RETURN_DATA_REGNO
1234
1235	/* Add EH return hard registers as conflict hard registers to allocnos
1236	living at end of BB. For most allocnos it is already done in
1237	process_bb_node_lives when we processing input edges but it does
1238	not work when and EH edge is edge out of the current region. This
1239	function covers such out of region edges. */
1240	static void
1241	process_out_of_region_eh_regs (basic_block bb)
1242	{
1243	edge e;
1244	edge_iterator ei;
1245	unsigned int i;
1246	bitmap_iterator bi;
1247	bool eh_p = false;
1248
1249	FOR_EACH_EDGE (e, ei, bb->succs)
1250	if ((e->flags & EDGE_EH)
1251	&& IRA_BB_NODE (e->dest)->parent != IRA_BB_NODE (bb)->parent)
1252	eh_p = true;
1253
1254	if (! eh_p)
1255	return;
1256
1257	EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb), FIRST_PSEUDO_REGISTER, i, bi)
1258	{
1259	ira_allocno_t a = ira_curr_regno_allocno_map[i];
1260	for (int n = ALLOCNO_NUM_OBJECTS (a) - 1; n >= 0; n--)
1261	{
1262	ira_object_t obj = ALLOCNO_OBJECT (a, n);
1263	for (int k = 0; ; k++)
1264	{
1265	unsigned int regno = EH_RETURN_DATA_REGNO (k);
1266	if (regno == INVALID_REGNUM)
1267	break;
1268	SET_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj), bit: regno);
1269	SET_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), bit: regno);
1270	}
1271	}
1272	}
1273	}
1274
1275	#endif
1276
1277	/* Add conflicts for object OBJ from REGION landing pads using CALLEE_ABI. */
1278	static void
1279	add_conflict_from_region_landing_pads (eh_region region, ira_object_t obj,
1280	function_abi callee_abi)
1281	{
1282	ira_allocno_t a = OBJECT_ALLOCNO (obj);
1283	rtx_code_label *landing_label;
1284	basic_block landing_bb;
1285
1286	for (eh_landing_pad lp = region->landing_pads; lp ; lp = lp->next_lp)
1287	{
1288	if ((landing_label = lp->landing_pad) != NULL
1289	&& (landing_bb = BLOCK_FOR_INSN (insn: landing_label)) != NULL
1290	&& (region->type != ERT_CLEANUP
1291	|| bitmap_bit_p (df_get_live_in (bb: landing_bb),
1292	ALLOCNO_REGNO (a))))
1293	{
1294	HARD_REG_SET new_conflict_regs
1295	= callee_abi.mode_clobbers (ALLOCNO_MODE (a));
1296	OBJECT_CONFLICT_HARD_REGS (obj) |= new_conflict_regs;
1297	OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= new_conflict_regs;
1298	return;
1299	}
1300	}
1301	}
1302
1303	/* Process insns of the basic block given by its LOOP_TREE_NODE to
1304	update allocno live ranges, allocno hard register conflicts,
1305	intersected calls, and register pressure info for allocnos for the
1306	basic block for and regions containing the basic block. */
1307	static void
1308	process_bb_node_lives (ira_loop_tree_node_t loop_tree_node)
1309	{
1310	int i, freq;
1311	unsigned int j;
1312	basic_block bb;
1313	rtx_insn *insn;
1314	bitmap_iterator bi;
1315	bitmap reg_live_out;
1316	unsigned int px;
1317	bool set_p;
1318
1319	bb = loop_tree_node->bb;
1320	if (bb != NULL)
1321	{
1322	for (i = 0; i < ira_pressure_classes_num; i++)
1323	{
1324	curr_reg_pressure[ira_pressure_classes[i]] = 0;
1325	high_pressure_start_point[ira_pressure_classes[i]] = -1;
1326	}
1327	curr_bb_node = loop_tree_node;
1328	reg_live_out = df_get_live_out (bb);
1329	sparseset_clear (s: objects_live);
1330	REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
1331	hard_regs_live &= ~(eliminable_regset | ira_no_alloc_regs);
1332	for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1333	if (TEST_HARD_REG_BIT (set: hard_regs_live, bit: i))
1334	{
1335	enum reg_class aclass, pclass, cl;
1336
1337	aclass = ira_allocno_class_translate[REGNO_REG_CLASS (i)];
1338	pclass = ira_pressure_class_translate[aclass];
1339	for (j = 0;
1340	(cl = ira_reg_class_super_classes[pclass][j])
1341	!= LIM_REG_CLASSES;
1342	j++)
1343	{
1344	if (! ira_reg_pressure_class_p[cl])
1345	continue;
1346	curr_reg_pressure[cl]++;
1347	if (curr_bb_node->reg_pressure[cl] < curr_reg_pressure[cl])
1348	curr_bb_node->reg_pressure[cl] = curr_reg_pressure[cl];
1349	ira_assert (curr_reg_pressure[cl]
1350	<= ira_class_hard_regs_num[cl]);
1351	}
1352	}
1353	EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
1354	mark_pseudo_regno_live (regno: j);
1355
1356	#ifdef EH_RETURN_DATA_REGNO
1357	process_out_of_region_eh_regs (bb);
1358	#endif
1359
1360	freq = REG_FREQ_FROM_BB (bb);
1361	if (freq == 0)
1362	freq = 1;
1363
1364	/* Invalidate all allocno_saved_at_call entries. */
1365	last_call_num++;
1366
1367	/* Scan the code of this basic block, noting which allocnos and
1368	hard regs are born or die.
1369
1370	Note that this loop treats uninitialized values as live until
1371	the beginning of the block. For example, if an instruction
1372	uses (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever
1373	set, FOO will remain live until the beginning of the block.
1374	Likewise if FOO is not set at all. This is unnecessarily
1375	pessimistic, but it probably doesn't matter much in practice. */
1376	FOR_BB_INSNS_REVERSE (bb, insn)
1377	{
1378	ira_allocno_t a;
1379	df_ref def, use;
1380	bool call_p;
1381
1382	if (!NONDEBUG_INSN_P (insn))
1383	continue;
1384
1385	if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1386	fprintf (stream: ira_dump_file, format: " Insn %u(l%d): point = %d\n",
1387	INSN_UID (insn), loop_tree_node->parent->loop_num,
1388	curr_point);
1389
1390	call_p = CALL_P (insn);
1391	ignore_reg_for_conflicts = non_conflicting_reg_copy_p (insn);
1392
1393	/* Mark each defined value as live. We need to do this for
1394	unused values because they still conflict with quantities
1395	that are live at the time of the definition.
1396
1397	Ignore DF_REF_MAY_CLOBBERs on a call instruction. Such
1398	references represent the effect of the called function
1399	on a call-clobbered register. Marking the register as
1400	live would stop us from allocating it to a call-crossing
1401	allocno. */
1402	FOR_EACH_INSN_DEF (def, insn)
1403	if (!call_p || !DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1404	mark_ref_live (ref: def);
1405
1406	/* If INSN has multiple outputs, then any value used in one
1407	of the outputs conflicts with the other outputs. Model this
1408	by making the used value live during the output phase.
1409
1410	It is unsafe to use !single_set here since it will ignore
1411	an unused output. Just because an output is unused does
1412	not mean the compiler can assume the side effect will not
1413	occur. Consider if ALLOCNO appears in the address of an
1414	output and we reload the output. If we allocate ALLOCNO
1415	to the same hard register as an unused output we could
1416	set the hard register before the output reload insn. */
1417	if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn))
1418	FOR_EACH_INSN_USE (use, insn)
1419	{
1420	int i;
1421	rtx reg;
1422
1423	reg = DF_REF_REG (use);
1424	for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
1425	{
1426	rtx set;
1427
1428	set = XVECEXP (PATTERN (insn), 0, i);
1429	if (GET_CODE (set) == SET
1430	&& reg_overlap_mentioned_p (reg, SET_DEST (set)))
1431	{
1432	/* After the previous loop, this is a no-op if
1433	REG is contained within SET_DEST (SET). */
1434	mark_ref_live (ref: use);
1435	break;
1436	}
1437	}
1438	}
1439
1440	preferred_alternatives = ira_setup_alts (insn);
1441	process_register_constraint_filters ();
1442	process_single_reg_class_operands (in_p: false, freq);
1443
1444	if (call_p)
1445	{
1446	/* Try to find a SET in the CALL_INSN_FUNCTION_USAGE, and from
1447	there, try to find a pseudo that is live across the call but
1448	can be cheaply reconstructed from the return value. */
1449	rtx cheap_reg = find_call_crossed_cheap_reg (insn);
1450	if (cheap_reg != NULL_RTX)
1451	add_reg_note (insn, REG_RETURNED, cheap_reg);
1452
1453	last_call_num++;
1454	sparseset_clear (s: allocnos_processed);
1455	/* The current set of live allocnos are live across the call. */
1456	EXECUTE_IF_SET_IN_SPARSESET (objects_live, i)
1457	{
1458	ira_object_t obj = ira_object_id_map[i];
1459	a = OBJECT_ALLOCNO (obj);
1460	int num = ALLOCNO_NUM (a);
1461	function_abi callee_abi = insn_callee_abi (insn);
1462
1463	/* Don't allocate allocnos that cross setjmps or any
1464	call, if this function receives a nonlocal
1465	goto. */
1466	if (cfun->has_nonlocal_label
1467	|| (!targetm.setjmp_preserves_nonvolatile_regs_p ()
1468	&& (find_reg_note (insn, REG_SETJMP, NULL_RTX)
1469	!= NULL_RTX)))
1470	{
1471	SET_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj));
1472	SET_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
1473	}
1474	eh_region r;
1475	if (can_throw_internal (insn)
1476	&& (r = get_eh_region_from_rtx (insn)) != NULL)
1477	add_conflict_from_region_landing_pads (region: r, obj, callee_abi);
1478	if (sparseset_bit_p (s: allocnos_processed, e: num))
1479	continue;
1480	sparseset_set_bit (s: allocnos_processed, e: num);
1481
1482	if (allocno_saved_at_call[num] != last_call_num)
1483	/* Here we are mimicking caller-save.cc behavior
1484	which does not save hard register at a call if
1485	it was saved on previous call in the same basic
1486	block and the hard register was not mentioned
1487	between the two calls. */
1488	ALLOCNO_CALL_FREQ (a) += freq;
1489	/* Mark it as saved at the next call. */
1490	allocno_saved_at_call[num] = last_call_num + 1;
1491	ALLOCNO_CALLS_CROSSED_NUM (a)++;
1492	ALLOCNO_CROSSED_CALLS_ABIS (a) |= 1 << callee_abi.id ();
1493	ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a)
1494	|= callee_abi.full_and_partial_reg_clobbers ();
1495	if (cheap_reg != NULL_RTX
1496	&& ALLOCNO_REGNO (a) == (int) REGNO (cheap_reg))
1497	ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a)++;
1498	}
1499	}
1500
1501	/* See which defined values die here. Note that we include
1502	the call insn in the lifetimes of these values, so we don't
1503	mistakenly consider, for e.g. an addressing mode with a
1504	side-effect like a post-increment fetching the address,
1505	that the use happens before the call, and the def to happen
1506	after the call: we believe both to happen before the actual
1507	call. (We don't handle return-values here.) */
1508	FOR_EACH_INSN_DEF (def, insn)
1509	if (!call_p || !DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1510	mark_ref_dead (def);
1511
1512	make_early_clobber_and_input_conflicts ();
1513
1514	curr_point++;
1515
1516	/* Mark each used value as live. */
1517	FOR_EACH_INSN_USE (use, insn)
1518	mark_ref_live (ref: use);
1519
1520	process_single_reg_class_operands (in_p: true, freq);
1521
1522	set_p = mark_hard_reg_early_clobbers (insn, live_p: true);
1523
1524	if (set_p)
1525	{
1526	mark_hard_reg_early_clobbers (insn, live_p: false);
1527
1528	/* Mark each hard reg as live again. For example, a
1529	hard register can be in clobber and in an insn
1530	input. */
1531	FOR_EACH_INSN_USE (use, insn)
1532	{
1533	rtx ureg = DF_REF_REG (use);
1534
1535	if (GET_CODE (ureg) == SUBREG)
1536	ureg = SUBREG_REG (ureg);
1537	if (! REG_P (ureg) || REGNO (ureg) >= FIRST_PSEUDO_REGISTER)
1538	continue;
1539
1540	mark_ref_live (ref: use);
1541	}
1542	}
1543
1544	curr_point++;
1545	}
1546	ignore_reg_for_conflicts = NULL_RTX;
1547
1548	if (bb_has_eh_pred (bb))
1549	for (j = 0; ; ++j)
1550	{
1551	unsigned int regno = EH_RETURN_DATA_REGNO (j);
1552	if (regno == INVALID_REGNUM)
1553	break;
1554	make_hard_regno_live (regno);
1555	}
1556
1557	/* Allocnos can't go in stack regs at the start of a basic block
1558	that is reached by an abnormal edge. Likewise for registers
1559	that are at least partly call clobbered, because caller-save,
1560	fixup_abnormal_edges and possibly the table driven EH machinery
1561	are not quite ready to handle such allocnos live across such
1562	edges. */
1563	if (bb_has_abnormal_pred (bb))
1564	{
1565	#ifdef STACK_REGS
1566	EXECUTE_IF_SET_IN_SPARSESET (objects_live, px)
1567	{
1568	ira_allocno_t a = OBJECT_ALLOCNO (ira_object_id_map[px]);
1569
1570	ALLOCNO_NO_STACK_REG_P (a) = true;
1571	ALLOCNO_TOTAL_NO_STACK_REG_P (a) = true;
1572	}
1573	for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
1574	make_hard_regno_live (regno: px);
1575	#endif
1576	/* No need to record conflicts for call clobbered regs if we
1577	have nonlocal labels around, as we don't ever try to
1578	allocate such regs in this case. */
1579	if (!cfun->has_nonlocal_label
1580	&& has_abnormal_call_or_eh_pred_edge_p (bb))
1581	for (px = 0; px < FIRST_PSEUDO_REGISTER; px++)
1582	if (eh_edge_abi.clobbers_at_least_part_of_reg_p (regno: px)
1583	#ifdef REAL_PIC_OFFSET_TABLE_REGNUM
1584	/* We should create a conflict of PIC pseudo with
1585	PIC hard reg as PIC hard reg can have a wrong
1586	value after jump described by the abnormal edge.
1587	In this case we cannot allocate PIC hard reg to
1588	PIC pseudo as PIC pseudo will also have a wrong
1589	value. This code is not critical as LRA can fix
1590	it but it is better to have the right allocation
1591	earlier. */
1592	|| (px == REAL_PIC_OFFSET_TABLE_REGNUM
1593	&& pic_offset_table_rtx != NULL_RTX
1594	&& REGNO (pic_offset_table_rtx) >= FIRST_PSEUDO_REGISTER)
1595	#endif
1596	)
1597	make_hard_regno_live (regno: px);
1598	}
1599
1600	EXECUTE_IF_SET_IN_SPARSESET (objects_live, i)
1601	make_object_dead (obj: ira_object_id_map[i]);
1602
1603	curr_point++;
1604
1605	}
1606	/* Propagate register pressure to upper loop tree nodes. */
1607	if (loop_tree_node != ira_loop_tree_root)
1608	for (i = 0; i < ira_pressure_classes_num; i++)
1609	{
1610	enum reg_class pclass;
1611
1612	pclass = ira_pressure_classes[i];
1613	if (loop_tree_node->reg_pressure[pclass]
1614	> loop_tree_node->parent->reg_pressure[pclass])
1615	loop_tree_node->parent->reg_pressure[pclass]
1616	= loop_tree_node->reg_pressure[pclass];
1617	}
1618	}
1619
1620	/* Create and set up IRA_START_POINT_RANGES and
1621	IRA_FINISH_POINT_RANGES. */
1622	static void
1623	create_start_finish_chains (void)
1624	{
1625	ira_object_t obj;
1626	ira_object_iterator oi;
1627	live_range_t r;
1628
1629	ira_start_point_ranges
1630	= (live_range_t *) ira_allocate (ira_max_point * sizeof (live_range_t));
1631	memset (s: ira_start_point_ranges, c: 0, n: ira_max_point * sizeof (live_range_t));
1632	ira_finish_point_ranges
1633	= (live_range_t *) ira_allocate (ira_max_point * sizeof (live_range_t));
1634	memset (s: ira_finish_point_ranges, c: 0, n: ira_max_point * sizeof (live_range_t));
1635	FOR_EACH_OBJECT (obj, oi)
1636	for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
1637	{
1638	r->start_next = ira_start_point_ranges[r->start];
1639	ira_start_point_ranges[r->start] = r;
1640	r->finish_next = ira_finish_point_ranges[r->finish];
1641	ira_finish_point_ranges[r->finish] = r;
1642	}
1643	}
1644
1645	/* Rebuild IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES after
1646	new live ranges and program points were added as a result if new
1647	insn generation. */
1648	void
1649	ira_rebuild_start_finish_chains (void)
1650	{
1651	ira_free (addr: ira_finish_point_ranges);
1652	ira_free (addr: ira_start_point_ranges);
1653	create_start_finish_chains ();
1654	}
1655
1656	/* Compress allocno live ranges by removing program points where
1657	nothing happens. */
1658	static void
1659	remove_some_program_points_and_update_live_ranges (void)
1660	{
1661	unsigned i;
1662	int n;
1663	int *map;
1664	ira_object_t obj;
1665	ira_object_iterator oi;
1666	live_range_t r, prev_r, next_r;
1667	sbitmap_iterator sbi;
1668	bool born_p, dead_p, prev_born_p, prev_dead_p;
1669
1670	auto_sbitmap born (ira_max_point);
1671	auto_sbitmap dead (ira_max_point);
1672	bitmap_clear (born);
1673	bitmap_clear (dead);
1674	FOR_EACH_OBJECT (obj, oi)
1675	for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
1676	{
1677	ira_assert (r->start <= r->finish);
1678	bitmap_set_bit (map: born, bitno: r->start);
1679	bitmap_set_bit (map: dead, bitno: r->finish);
1680	}
1681
1682	auto_sbitmap born_or_dead (ira_max_point);
1683	bitmap_ior (born_or_dead, born, dead);
1684	map = (int *) ira_allocate (sizeof (int) * ira_max_point);
1685	n = -1;
1686	prev_born_p = prev_dead_p = false;
1687	EXECUTE_IF_SET_IN_BITMAP (born_or_dead, 0, i, sbi)
1688	{
1689	born_p = bitmap_bit_p (map: born, bitno: i);
1690	dead_p = bitmap_bit_p (map: dead, bitno: i);
1691	if ((prev_born_p && ! prev_dead_p && born_p && ! dead_p)
1692	|| (prev_dead_p && ! prev_born_p && dead_p && ! born_p))
1693	map[i] = n;
1694	else
1695	map[i] = ++n;
1696	prev_born_p = born_p;
1697	prev_dead_p = dead_p;
1698	}
1699
1700	n++;
1701	if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1702	fprintf (stream: ira_dump_file, format: "Compressing live ranges: from %d to %d - %d%%\n",
1703	ira_max_point, n, 100 * n / ira_max_point);
1704	ira_max_point = n;
1705
1706	FOR_EACH_OBJECT (obj, oi)
1707	for (r = OBJECT_LIVE_RANGES (obj), prev_r = NULL; r != NULL; r = next_r)
1708	{
1709	next_r = r->next;
1710	r->start = map[r->start];
1711	r->finish = map[r->finish];
1712	if (prev_r == NULL || prev_r->start > r->finish + 1)
1713	{
1714	prev_r = r;
1715	continue;
1716	}
1717	prev_r->start = r->start;
1718	prev_r->next = next_r;
1719	ira_finish_live_range (r);
1720	}
1721
1722	ira_free (addr: map);
1723	}
1724
1725	/* Print live ranges R to file F. */
1726	void
1727	ira_print_live_range_list (FILE *f, live_range_t r)
1728	{
1729	for (; r != NULL; r = r->next)
1730	fprintf (stream: f, format: " [%d..%d]", r->start, r->finish);
1731	fprintf (stream: f, format: "\n");
1732	}
1733
1734	DEBUG_FUNCTION void
1735	debug (live_range &ref)
1736	{
1737	ira_print_live_range_list (stderr, r: &ref);
1738	}
1739
1740	DEBUG_FUNCTION void
1741	debug (live_range *ptr)
1742	{
1743	if (ptr)
1744	debug (ref&: *ptr);
1745	else
1746	fprintf (stderr, format: "<nil>\n");
1747	}
1748
1749	/* Print live ranges R to stderr. */
1750	void
1751	ira_debug_live_range_list (live_range_t r)
1752	{
1753	ira_print_live_range_list (stderr, r);
1754	}
1755
1756	/* Print live ranges of object OBJ to file F. */
1757	static void
1758	print_object_live_ranges (FILE *f, ira_object_t obj)
1759	{
1760	ira_print_live_range_list (f, OBJECT_LIVE_RANGES (obj));
1761	}
1762
1763	/* Print live ranges of allocno A to file F. */
1764	static void
1765	print_allocno_live_ranges (FILE *f, ira_allocno_t a)
1766	{
1767	int n = ALLOCNO_NUM_OBJECTS (a);
1768	int i;
1769
1770	for (i = 0; i < n; i++)
1771	{
1772	fprintf (stream: f, format: " a%d(r%d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
1773	if (n > 1)
1774	fprintf (stream: f, format: " [%d]", i);
1775	fprintf (stream: f, format: "):");
1776	print_object_live_ranges (f, ALLOCNO_OBJECT (a, i));
1777	}
1778	}
1779
1780	/* Print live ranges of allocno A to stderr. */
1781	void
1782	ira_debug_allocno_live_ranges (ira_allocno_t a)
1783	{
1784	print_allocno_live_ranges (stderr, a);
1785	}
1786
1787	/* Print live ranges of all allocnos to file F. */
1788	static void
1789	print_live_ranges (FILE *f)
1790	{
1791	ira_allocno_t a;
1792	ira_allocno_iterator ai;
1793
1794	FOR_EACH_ALLOCNO (a, ai)
1795	print_allocno_live_ranges (f, a);
1796	}
1797
1798	/* Print live ranges of all allocnos to stderr. */
1799	void
1800	ira_debug_live_ranges (void)
1801	{
1802	print_live_ranges (stderr);
1803	}
1804
1805	/* The main entry function creates live ranges, set up
1806	CONFLICT_HARD_REGS and TOTAL_CONFLICT_HARD_REGS for objects, and
1807	calculate register pressure info. */
1808	void
1809	ira_create_allocno_live_ranges (void)
1810	{
1811	objects_live = sparseset_alloc (n_elms: ira_objects_num);
1812	allocnos_processed = sparseset_alloc (n_elms: ira_allocnos_num);
1813	curr_point = 0;
1814	last_call_num = 0;
1815	allocno_saved_at_call
1816	= (int *) ira_allocate (ira_allocnos_num * sizeof (int));
1817	memset (s: allocno_saved_at_call, c: 0, n: ira_allocnos_num * sizeof (int));
1818	ira_traverse_loop_tree (true, ira_loop_tree_root, NULL,
1819	process_bb_node_lives);
1820	ira_max_point = curr_point;
1821	create_start_finish_chains ();
1822	if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1823	print_live_ranges (f: ira_dump_file);
1824	/* Clean up. */
1825	ira_free (addr: allocno_saved_at_call);
1826	sparseset_free (objects_live);
1827	sparseset_free (allocnos_processed);
1828	}
1829
1830	/* Compress allocno live ranges. */
1831	void
1832	ira_compress_allocno_live_ranges (void)
1833	{
1834	remove_some_program_points_and_update_live_ranges ();
1835	ira_rebuild_start_finish_chains ();
1836	if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1837	{
1838	fprintf (stream: ira_dump_file, format: "Ranges after the compression:\n");
1839	print_live_ranges (f: ira_dump_file);
1840	}
1841	}
1842
1843	/* Free arrays IRA_START_POINT_RANGES and IRA_FINISH_POINT_RANGES. */
1844	void
1845	ira_finish_allocno_live_ranges (void)
1846	{
1847	ira_free (addr: ira_finish_point_ranges);
1848	ira_free (addr: ira_start_point_ranges);
1849	}
1850