1	/* Build live ranges for pseudos.
2	Copyright (C) 2010-2023 Free Software Foundation, Inc.
3	Contributed by Vladimir Makarov <vmakarov@redhat.com>.
4
5	This file is part of GCC.
6
7	GCC is free software; you can redistribute it and/or modify it under
8	the terms of the GNU General Public License as published by the Free
9	Software Foundation; either version 3, or (at your option) any later
10	version.
11
12	GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13	WARRANTY; without even the implied warranty of MERCHANTABILITY or
14	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15	for more details.
16
17	You should have received a copy of the GNU General Public License
18	along with GCC; see the file COPYING3. If not see
19	<http://www.gnu.org/licenses/>. */
20
21
22	/* This file contains code to build pseudo live-ranges (analogous
23	structures used in IRA, so read comments about the live-ranges
24	there) and other info necessary for other passes to assign
25	hard-registers to pseudos, coalesce the spilled pseudos, and assign
26	stack memory slots to spilled pseudos. */
27
28	#include "config.h"
29	#include "system.h"
30	#include "coretypes.h"
31	#include "backend.h"
32	#include "rtl.h"
33	#include "tree.h"
34	#include "predict.h"
35	#include "df.h"
36	#include "memmodel.h"
37	#include "tm_p.h"
38	#include "insn-config.h"
39	#include "regs.h"
40	#include "ira.h"
41	#include "recog.h"
42	#include "cfganal.h"
43	#include "sparseset.h"
44	#include "lra-int.h"
45	#include "target.h"
46	#include "function-abi.h"
47
48	/* Program points are enumerated by numbers from range
49	0..LRA_LIVE_MAX_POINT-1. There are approximately two times more
50	program points than insns. Program points are places in the
51	program where liveness info can be changed. In most general case
52	(there are more complicated cases too) some program points
53	correspond to places where input operand dies and other ones
54	correspond to places where output operands are born. */
55	int lra_live_max_point;
56
57	/* Accumulated execution frequency of all references for each hard
58	register. */
59	int lra_hard_reg_usage[FIRST_PSEUDO_REGISTER];
60
61	/* A global flag whose true value says to build live ranges for all
62	pseudos, otherwise the live ranges only for pseudos got memory is
63	build. True value means also building copies and setting up hard
64	register preferences. The complete info is necessary only for the
65	assignment pass. The complete info is not needed for the
66	coalescing and spill passes. */
67	static bool complete_info_p;
68
69	/* Pseudos live at current point in the RTL scan. */
70	static sparseset pseudos_live;
71
72	/* Pseudos probably living through calls and setjumps. As setjump is
73	a call too, if a bit in PSEUDOS_LIVE_THROUGH_SETJUMPS is set up
74	then the corresponding bit in PSEUDOS_LIVE_THROUGH_CALLS is set up
75	too. These data are necessary for cases when only one subreg of a
76	multi-reg pseudo is set up after a call. So we decide it is
77	probably live when traversing bb backward. We are sure about
78	living when we see its usage or definition of the pseudo. */
79	static sparseset pseudos_live_through_calls;
80	static sparseset pseudos_live_through_setjumps;
81
82	/* Set of hard regs (except eliminable ones) currently live. */
83	static HARD_REG_SET hard_regs_live;
84
85	/* Set of pseudos and hard registers start living/dying in the current
86	insn. These sets are used to update REG_DEAD and REG_UNUSED notes
87	in the insn. */
88	static sparseset start_living, start_dying;
89
90	/* Set of pseudos and hard regs dead and unused in the current
91	insn. */
92	static sparseset unused_set, dead_set;
93
94	/* Bitmap used for holding intermediate bitmap operation results. */
95	static bitmap_head temp_bitmap;
96
97	/* Pool for pseudo live ranges. */
98	static object_allocator<lra_live_range> lra_live_range_pool ("live ranges");
99
100	/* Free live range list LR. */
101	static void
102	free_live_range_list (lra_live_range_t lr)
103	{
104	lra_live_range_t next;
105
106	while (lr != NULL)
107	{
108	next = lr->next;
109	lra_live_range_pool.remove (object: lr);
110	lr = next;
111	}
112	}
113
114	/* Create and return pseudo live range with given attributes. */
115	static lra_live_range_t
116	create_live_range (int regno, int start, int finish, lra_live_range_t next)
117	{
118	lra_live_range_t p = lra_live_range_pool.allocate ();
119	p->regno = regno;
120	p->start = start;
121	p->finish = finish;
122	p->next = next;
123	return p;
124	}
125
126	/* Copy live range R and return the result. */
127	static lra_live_range_t
128	copy_live_range (lra_live_range_t r)
129	{
130	return new (lra_live_range_pool) lra_live_range (*r);
131	}
132
133	/* Copy live range list given by its head R and return the result. */
134	lra_live_range_t
135	lra_copy_live_range_list (lra_live_range_t r)
136	{
137	lra_live_range_t p, first, *chain;
138
139	first = NULL;
140	for (chain = &first; r != NULL; r = r->next)
141	{
142	p = copy_live_range (r);
143	*chain = p;
144	chain = &p->next;
145	}
146	return first;
147	}
148
149	/* Merge *non-intersected* ranges R1 and R2 and returns the result.
150	The function maintains the order of ranges and tries to minimize
151	size of the result range list. Ranges R1 and R2 may not be used
152	after the call. */
153	lra_live_range_t
154	lra_merge_live_ranges (lra_live_range_t r1, lra_live_range_t r2)
155	{
156	lra_live_range_t first, last;
157
158	if (r1 == NULL)
159	return r2;
160	if (r2 == NULL)
161	return r1;
162	for (first = last = NULL; r1 != NULL && r2 != NULL;)
163	{
164	if (r1->start < r2->start)
165	std::swap (a&: r1, b&: r2);
166
167	if (r1->start == r2->finish + 1)
168	{
169	/* Joint ranges: merge r1 and r2 into r1. */
170	r1->start = r2->start;
171	lra_live_range_t temp = r2;
172	r2 = r2->next;
173	lra_live_range_pool.remove (object: temp);
174	}
175	else
176	{
177	gcc_assert (r2->finish + 1 < r1->start);
178	/* Add r1 to the result. */
179	if (first == NULL)
180	first = last = r1;
181	else
182	{
183	last->next = r1;
184	last = r1;
185	}
186	r1 = r1->next;
187	}
188	}
189	if (r1 != NULL)
190	{
191	if (first == NULL)
192	first = r1;
193	else
194	last->next = r1;
195	}
196	else
197	{
198	lra_assert (r2 != NULL);
199	if (first == NULL)
200	first = r2;
201	else
202	last->next = r2;
203	}
204	return first;
205	}
206
207	/* Return TRUE if live ranges R1 and R2 intersect. */
208	bool
209	lra_intersected_live_ranges_p (lra_live_range_t r1, lra_live_range_t r2)
210	{
211	/* Remember the live ranges are always kept ordered. */
212	while (r1 != NULL && r2 != NULL)
213	{
214	if (r1->start > r2->finish)
215	r1 = r1->next;
216	else if (r2->start > r1->finish)
217	r2 = r2->next;
218	else
219	return true;
220	}
221	return false;
222	}
223
224	enum point_type {
225	DEF_POINT,
226	USE_POINT
227	};
228
229	/* Return TRUE if set A contains a pseudo register, otherwise, return FALSE. */
230	static bool
231	sparseset_contains_pseudos_p (sparseset a)
232	{
233	int regno;
234	EXECUTE_IF_SET_IN_SPARSESET (a, regno)
235	if (!HARD_REGISTER_NUM_P (regno))
236	return true;
237	return false;
238	}
239
240	/* Mark pseudo REGNO as living or dying at program point POINT, depending on
241	whether TYPE is a definition or a use. If this is the first reference to
242	REGNO that we've encountered, then create a new live range for it. */
243
244	static void
245	update_pseudo_point (int regno, int point, enum point_type type)
246	{
247	lra_live_range_t p;
248
249	/* Don't compute points for hard registers. */
250	if (HARD_REGISTER_NUM_P (regno))
251	return;
252
253	if (complete_info_p || lra_get_regno_hard_regno (regno) < 0)
254	{
255	if (type == DEF_POINT)
256	{
257	if (sparseset_bit_p (s: pseudos_live, e: regno))
258	{
259	p = lra_reg_info[regno].live_ranges;
260	lra_assert (p != NULL);
261	p->finish = point;
262	}
263	}
264	else /* USE_POINT */
265	{
266	if (!sparseset_bit_p (s: pseudos_live, e: regno)
267	&& ((p = lra_reg_info[regno].live_ranges) == NULL
268	|| (p->finish != point && p->finish + 1 != point)))
269	lra_reg_info[regno].live_ranges
270	= create_live_range (regno, start: point, finish: -1, next: p);
271	}
272	}
273	}
274
275	/* The corresponding bitmaps of BB currently being processed. */
276	static bitmap bb_killed_pseudos, bb_gen_pseudos;
277
278	/* Record hard register REGNO as now being live. It updates
279	living hard regs and START_LIVING. */
280	static void
281	make_hard_regno_live (int regno)
282	{
283	lra_assert (HARD_REGISTER_NUM_P (regno));
284	if (TEST_HARD_REG_BIT (set: hard_regs_live, bit: regno)
285	|| TEST_HARD_REG_BIT (set: eliminable_regset, bit: regno))
286	return;
287	SET_HARD_REG_BIT (set&: hard_regs_live, bit: regno);
288	sparseset_set_bit (s: start_living, e: regno);
289	if (fixed_regs[regno] || TEST_HARD_REG_BIT (set: hard_regs_spilled_into, bit: regno))
290	bitmap_set_bit (bb_gen_pseudos, regno);
291	}
292
293	/* Process the definition of hard register REGNO. This updates
294	hard_regs_live, START_DYING and conflict hard regs for living
295	pseudos. */
296	static void
297	make_hard_regno_dead (int regno)
298	{
299	if (TEST_HARD_REG_BIT (set: eliminable_regset, bit: regno))
300	return;
301
302	lra_assert (HARD_REGISTER_NUM_P (regno));
303	unsigned int i;
304	EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
305	SET_HARD_REG_BIT (set&: lra_reg_info[i].conflict_hard_regs, bit: regno);
306
307	if (! TEST_HARD_REG_BIT (set: hard_regs_live, bit: regno))
308	return;
309	CLEAR_HARD_REG_BIT (set&: hard_regs_live, bit: regno);
310	sparseset_set_bit (s: start_dying, e: regno);
311	if (fixed_regs[regno] || TEST_HARD_REG_BIT (set: hard_regs_spilled_into, bit: regno))
312	{
313	bitmap_clear_bit (bb_gen_pseudos, regno);
314	bitmap_set_bit (bb_killed_pseudos, regno);
315	}
316	}
317
318	/* Mark pseudo REGNO as now being live and update START_LIVING. */
319	static void
320	mark_pseudo_live (int regno)
321	{
322	lra_assert (!HARD_REGISTER_NUM_P (regno));
323	if (sparseset_bit_p (s: pseudos_live, e: regno))
324	return;
325
326	sparseset_set_bit (s: pseudos_live, e: regno);
327	sparseset_set_bit (s: start_living, e: regno);
328	}
329
330	/* Mark pseudo REGNO as now being dead and update START_DYING. */
331	static void
332	mark_pseudo_dead (int regno)
333	{
334	lra_assert (!HARD_REGISTER_NUM_P (regno));
335	lra_reg_info[regno].conflict_hard_regs |= hard_regs_live;
336	if (!sparseset_bit_p (s: pseudos_live, e: regno))
337	return;
338
339	sparseset_clear_bit (pseudos_live, regno);
340	sparseset_set_bit (s: start_dying, e: regno);
341	}
342
343	/* Mark register REGNO (pseudo or hard register) in MODE as being live
344	and update BB_GEN_PSEUDOS. */
345	static void
346	mark_regno_live (int regno, machine_mode mode)
347	{
348	int last;
349
350	if (HARD_REGISTER_NUM_P (regno))
351	{
352	for (last = end_hard_regno (mode, regno); regno < last; regno++)
353	make_hard_regno_live (regno);
354	}
355	else
356	{
357	mark_pseudo_live (regno);
358	bitmap_set_bit (bb_gen_pseudos, regno);
359	}
360	}
361
362
363	/* Mark register REGNO (pseudo or hard register) in MODE as being dead
364	and update BB_GEN_PSEUDOS and BB_KILLED_PSEUDOS. */
365	static void
366	mark_regno_dead (int regno, machine_mode mode)
367	{
368	int last;
369
370	if (HARD_REGISTER_NUM_P (regno))
371	{
372	for (last = end_hard_regno (mode, regno); regno < last; regno++)
373	make_hard_regno_dead (regno);
374	}
375	else
376	{
377	mark_pseudo_dead (regno);
378	bitmap_clear_bit (bb_gen_pseudos, regno);
379	bitmap_set_bit (bb_killed_pseudos, regno);
380	}
381	}
382
383
384
385	/* This page contains code for making global live analysis of pseudos.
386	The code works only when pseudo live info is changed on a BB
387	border. That might be a consequence of some global transformations
388	in LRA, e.g. PIC pseudo reuse or rematerialization. */
389
390	/* Structure describing local BB data used for pseudo
391	live-analysis. */
392	class bb_data_pseudos
393	{
394	public:
395	/* Basic block about which the below data are. */
396	basic_block bb;
397	bitmap_head killed_pseudos; /* pseudos killed in the BB. */
398	bitmap_head gen_pseudos; /* pseudos generated in the BB. */
399	};
400
401	/* Array for all BB data. Indexed by the corresponding BB index. */
402	typedef class bb_data_pseudos *bb_data_t;
403
404	/* All basic block data are referred through the following array. */
405	static bb_data_t bb_data;
406
407	/* Two small functions for access to the bb data. */
408	static inline bb_data_t
409	get_bb_data (basic_block bb)
410	{
411	return &bb_data[(bb)->index];
412	}
413
414	static inline bb_data_t
415	get_bb_data_by_index (int index)
416	{
417	return &bb_data[index];
418	}
419
420	/* Bitmap with all hard regs. */
421	static bitmap_head all_hard_regs_bitmap;
422
423	/* The transfer function used by the DF equation solver to propagate
424	live info through block with BB_INDEX according to the following
425	equation:
426
427	bb.livein = (bb.liveout - bb.kill) OR bb.gen
428	*/
429	static bool
430	live_trans_fun (int bb_index)
431	{
432	basic_block bb = get_bb_data_by_index (index: bb_index)->bb;
433	bitmap bb_liveout = df_get_live_out (bb);
434	bitmap bb_livein = df_get_live_in (bb);
435	bb_data_t bb_info = get_bb_data (bb);
436
437	bitmap_and_compl (&temp_bitmap, bb_liveout, &all_hard_regs_bitmap);
438	return bitmap_ior_and_compl (DST: bb_livein, A: &bb_info->gen_pseudos,
439	B: &temp_bitmap, C: &bb_info->killed_pseudos);
440	}
441
442	/* The confluence function used by the DF equation solver to set up
443	live info for a block BB without predecessor. */
444	static void
445	live_con_fun_0 (basic_block bb)
446	{
447	bitmap_and_into (df_get_live_out (bb), &all_hard_regs_bitmap);
448	}
449
450	/* The confluence function used by the DF equation solver to propagate
451	live info from successor to predecessor on edge E according to the
452	following equation:
453
454	bb.liveout = 0 for entry block | OR (livein of successors)
455	*/
456	static bool
457	live_con_fun_n (edge e)
458	{
459	basic_block bb = e->src;
460	basic_block dest = e->dest;
461	bitmap bb_liveout = df_get_live_out (bb);
462	bitmap dest_livein = df_get_live_in (bb: dest);
463
464	return bitmap_ior_and_compl_into (A: bb_liveout,
465	B: dest_livein, C: &all_hard_regs_bitmap);
466	}
467
468	/* Indexes of all function blocks. */
469	static bitmap_head all_blocks;
470
471	/* Allocate and initialize data needed for global pseudo live
472	analysis. */
473	static void
474	initiate_live_solver (void)
475	{
476	bitmap_initialize (head: &all_hard_regs_bitmap, obstack: &reg_obstack);
477	bitmap_set_range (&all_hard_regs_bitmap, 0, FIRST_PSEUDO_REGISTER);
478	bb_data = XNEWVEC (class bb_data_pseudos, last_basic_block_for_fn (cfun));
479	bitmap_initialize (head: &all_blocks, obstack: &reg_obstack);
480
481	basic_block bb;
482	FOR_ALL_BB_FN (bb, cfun)
483	{
484	bb_data_t bb_info = get_bb_data (bb);
485	bb_info->bb = bb;
486	bitmap_initialize (head: &bb_info->killed_pseudos, obstack: &reg_obstack);
487	bitmap_initialize (head: &bb_info->gen_pseudos, obstack: &reg_obstack);
488	bitmap_set_bit (&all_blocks, bb->index);
489	}
490	}
491
492	/* Free all data needed for global pseudo live analysis. */
493	static void
494	finish_live_solver (void)
495	{
496	basic_block bb;
497
498	bitmap_clear (&all_blocks);
499	FOR_ALL_BB_FN (bb, cfun)
500	{
501	bb_data_t bb_info = get_bb_data (bb);
502	bitmap_clear (&bb_info->killed_pseudos);
503	bitmap_clear (&bb_info->gen_pseudos);
504	}
505	free (ptr: bb_data);
506	bitmap_clear (&all_hard_regs_bitmap);
507	}
508
509
510
511	/* Insn currently scanned. */
512	static rtx_insn *curr_insn;
513	/* The insn data. */
514	static lra_insn_recog_data_t curr_id;
515	/* The insn static data. */
516	static struct lra_static_insn_data *curr_static_id;
517
518	/* Vec containing execution frequencies of program points. */
519	static vec<int> point_freq_vec;
520
521	/* The start of the above vector elements. */
522	int *lra_point_freq;
523
524	/* Increment the current program point POINT to the next point which has
525	execution frequency FREQ. */
526	static void
527	next_program_point (int &point, int freq)
528	{
529	point_freq_vec.safe_push (obj: freq);
530	lra_point_freq = point_freq_vec.address ();
531	point++;
532	}
533
534	/* Update the preference of HARD_REGNO for pseudo REGNO by PROFIT. */
535	void
536	lra_setup_reload_pseudo_preferenced_hard_reg (int regno,
537	int hard_regno, int profit)
538	{
539	lra_assert (regno >= lra_constraint_new_regno_start);
540	if (lra_reg_info[regno].preferred_hard_regno1 == hard_regno)
541	lra_reg_info[regno].preferred_hard_regno_profit1 += profit;
542	else if (lra_reg_info[regno].preferred_hard_regno2 == hard_regno)
543	lra_reg_info[regno].preferred_hard_regno_profit2 += profit;
544	else if (lra_reg_info[regno].preferred_hard_regno1 < 0)
545	{
546	lra_reg_info[regno].preferred_hard_regno1 = hard_regno;
547	lra_reg_info[regno].preferred_hard_regno_profit1 = profit;
548	}
549	else if (lra_reg_info[regno].preferred_hard_regno2 < 0
550	|| profit > lra_reg_info[regno].preferred_hard_regno_profit2)
551	{
552	lra_reg_info[regno].preferred_hard_regno2 = hard_regno;
553	lra_reg_info[regno].preferred_hard_regno_profit2 = profit;
554	}
555	else
556	return;
557	/* Keep the 1st hard regno as more profitable. */
558	if (lra_reg_info[regno].preferred_hard_regno1 >= 0
559	&& lra_reg_info[regno].preferred_hard_regno2 >= 0
560	&& (lra_reg_info[regno].preferred_hard_regno_profit2
561	> lra_reg_info[regno].preferred_hard_regno_profit1))
562	{
563	std::swap (a&: lra_reg_info[regno].preferred_hard_regno1,
564	b&: lra_reg_info[regno].preferred_hard_regno2);
565	std::swap (a&: lra_reg_info[regno].preferred_hard_regno_profit1,
566	b&: lra_reg_info[regno].preferred_hard_regno_profit2);
567	}
568	if (lra_dump_file != NULL)
569	{
570	if ((hard_regno = lra_reg_info[regno].preferred_hard_regno1) >= 0)
571	fprintf (stream: lra_dump_file,
572	format: " Hard reg %d is preferable by r%d with profit %d\n",
573	hard_regno, regno,
574	lra_reg_info[regno].preferred_hard_regno_profit1);
575	if ((hard_regno = lra_reg_info[regno].preferred_hard_regno2) >= 0)
576	fprintf (stream: lra_dump_file,
577	format: " Hard reg %d is preferable by r%d with profit %d\n",
578	hard_regno, regno,
579	lra_reg_info[regno].preferred_hard_regno_profit2);
580	}
581	}
582
583	/* Check whether REGNO lives through calls and setjmps and clear
584	the corresponding bits in PSEUDOS_LIVE_THROUGH_CALLS and
585	PSEUDOS_LIVE_THROUGH_SETJUMPS. All calls in the region described
586	by PSEUDOS_LIVE_THROUGH_CALLS have the given ABI. */
587
588	static inline void
589	check_pseudos_live_through_calls (int regno, const function_abi &abi)
590	{
591	if (! sparseset_bit_p (s: pseudos_live_through_calls, e: regno))
592	return;
593
594	machine_mode mode = PSEUDO_REGNO_MODE (regno);
595
596	sparseset_clear_bit (pseudos_live_through_calls, regno);
597	lra_reg_info[regno].conflict_hard_regs |= abi.mode_clobbers (mode);
598	if (! sparseset_bit_p (s: pseudos_live_through_setjumps, e: regno))
599	return;
600	sparseset_clear_bit (pseudos_live_through_setjumps, regno);
601	/* Don't allocate pseudos that cross setjmps or any call, if this
602	function receives a nonlocal goto. */
603	SET_HARD_REG_SET (lra_reg_info[regno].conflict_hard_regs);
604	}
605
606	/* Return true if insn REG is an early clobber operand in alternative
607	NALT. Negative NALT means that we don't know the current insn
608	alternative. So assume the worst. */
609	static inline bool
610	reg_early_clobber_p (const struct lra_insn_reg *reg, int n_alt)
611	{
612	return (n_alt == LRA_UNKNOWN_ALT
613	? reg->early_clobber_alts != 0
614	: (n_alt != LRA_NON_CLOBBERED_ALT
615	&& TEST_BIT (reg->early_clobber_alts, n_alt)));
616	}
617
618	/* Clear pseudo REGNO in SET or all hard registers of REGNO in MODE in SET. */
619	static void
620	clear_sparseset_regnos (sparseset set, int regno, enum machine_mode mode)
621	{
622	if (regno >= FIRST_PSEUDO_REGISTER)
623	{
624	sparseset_clear_bit (dead_set, regno);
625	return;
626	}
627	for (int last = end_hard_regno (mode, regno); regno < last; regno++)
628	sparseset_clear_bit (set, regno);
629	}
630
631	/* Return true if pseudo REGNO is in SET or all hard registers of REGNO in MODE
632	are in SET. */
633	static bool
634	regnos_in_sparseset_p (sparseset set, int regno, enum machine_mode mode)
635	{
636	if (regno >= FIRST_PSEUDO_REGISTER)
637	return sparseset_bit_p (s: dead_set, e: regno);
638	for (int last = end_hard_regno (mode, regno); regno < last; regno++)
639	if (!sparseset_bit_p (s: set, e: regno))
640	return false;
641	return true;
642	}
643
644	/* Process insns of the basic block BB to update pseudo live ranges,
645	pseudo hard register conflicts, and insn notes. We do it on
646	backward scan of BB insns. CURR_POINT is the program point where
647	BB ends. The function updates this counter and returns in
648	CURR_POINT the program point where BB starts. The function also
649	does local live info updates and can delete the dead insns if
650	DEAD_INSN_P. It returns true if pseudo live info was
651	changed at the BB start. */
652	static bool
653	process_bb_lives (basic_block bb, int &curr_point, bool dead_insn_p)
654	{
655	int i, regno, freq;
656	unsigned int j;
657	bitmap_iterator bi;
658	bitmap reg_live_out;
659	unsigned int px;
660	rtx_insn *next;
661	rtx link, *link_loc;
662	bool need_curr_point_incr;
663	/* Only has a meaningful value once we've seen a call. */
664	function_abi last_call_abi = default_function_abi;
665
666	reg_live_out = df_get_live_out (bb);
667	sparseset_clear (s: pseudos_live);
668	sparseset_clear (s: pseudos_live_through_calls);
669	sparseset_clear (s: pseudos_live_through_setjumps);
670	REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
671	hard_regs_live &= ~eliminable_regset;
672	EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
673	{
674	update_pseudo_point (regno: j, point: curr_point, type: USE_POINT);
675	mark_pseudo_live (regno: j);
676	}
677
678	bb_gen_pseudos = &get_bb_data (bb)->gen_pseudos;
679	bb_killed_pseudos = &get_bb_data (bb)->killed_pseudos;
680	bitmap_clear (bb_gen_pseudos);
681	bitmap_clear (bb_killed_pseudos);
682	freq = REG_FREQ_FROM_BB (bb);
683
684	if (lra_dump_file != NULL)
685	fprintf (stream: lra_dump_file, format: " BB %d\n", bb->index);
686
687	/* Scan the code of this basic block, noting which pseudos and hard
688	regs are born or die.
689
690	Note that this loop treats uninitialized values as live until the
691	beginning of the block. For example, if an instruction uses
692	(reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever set,
693	FOO will remain live until the beginning of the block. Likewise
694	if FOO is not set at all. This is unnecessarily pessimistic, but
695	it probably doesn't matter much in practice. */
696	FOR_BB_INSNS_REVERSE_SAFE (bb, curr_insn, next)
697	{
698	bool call_p;
699	int n_alt, dst_regno, src_regno;
700	rtx set;
701	struct lra_insn_reg *reg;
702
703	if (!NONDEBUG_INSN_P (curr_insn))
704	continue;
705
706	curr_id = lra_get_insn_recog_data (insn: curr_insn);
707	curr_static_id = curr_id->insn_static_data;
708	n_alt = curr_id->used_insn_alternative;
709	if (lra_dump_file != NULL)
710	fprintf (stream: lra_dump_file, format: " Insn %u: point = %d, n_alt = %d\n",
711	INSN_UID (insn: curr_insn), curr_point, n_alt);
712
713	set = single_set (insn: curr_insn);
714
715	if (dead_insn_p && set != NULL_RTX
716	&& REG_P (SET_DEST (set)) && !HARD_REGISTER_P (SET_DEST (set))
717	&& find_reg_note (curr_insn, REG_EH_REGION, NULL_RTX) == NULL_RTX
718	&& ! may_trap_p (PATTERN (insn: curr_insn))
719	/* Don't do premature remove of pic offset pseudo as we can
720	start to use it after some reload generation. */
721	&& (pic_offset_table_rtx == NULL_RTX
722	|| pic_offset_table_rtx != SET_DEST (set)))
723	{
724	bool remove_p = true;
725
726	for (reg = curr_id->regs; reg != NULL; reg = reg->next)
727	if (reg->type != OP_IN
728	&& (reg->regno < FIRST_PSEUDO_REGISTER
729	? TEST_HARD_REG_BIT (set: hard_regs_live, bit: reg->regno)
730	: sparseset_bit_p (s: pseudos_live, e: reg->regno)))
731	{
732	remove_p = false;
733	break;
734	}
735	for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
736	if (reg->type != OP_IN)
737	{
738	remove_p = false;
739	break;
740	}
741
742	if (remove_p && ! volatile_refs_p (PATTERN (insn: curr_insn)))
743	{
744	dst_regno = REGNO (SET_DEST (set));
745	if (lra_dump_file != NULL)
746	fprintf (stream: lra_dump_file, format: " Deleting dead insn %u\n",
747	INSN_UID (insn: curr_insn));
748	lra_set_insn_deleted (curr_insn);
749	if (lra_reg_info[dst_regno].nrefs == 0)
750	{
751	/* There might be some debug insns with the pseudo. */
752	unsigned int uid;
753	rtx_insn *insn;
754
755	bitmap_copy (&temp_bitmap, &lra_reg_info[dst_regno].insn_bitmap);
756	EXECUTE_IF_SET_IN_BITMAP (&temp_bitmap, 0, uid, bi)
757	{
758	insn = lra_insn_recog_data[uid]->insn;
759	lra_substitute_pseudo_within_insn (insn, dst_regno,
760	SET_SRC (set), true);
761	lra_update_insn_regno_info (insn);
762	}
763	}
764	continue;
765	}
766	}
767
768	/* Update max ref width and hard reg usage. */
769	for (reg = curr_id->regs; reg != NULL; reg = reg->next)
770	{
771	int regno = reg->regno;
772
773	if (partial_subreg_p (outermode: lra_reg_info[regno].biggest_mode,
774	innermode: reg->biggest_mode))
775	lra_reg_info[regno].biggest_mode = reg->biggest_mode;
776	if (HARD_REGISTER_NUM_P (regno))
777	lra_hard_reg_usage[regno] += freq;
778	}
779
780	call_p = CALL_P (curr_insn);
781
782	/* If we have a simple register copy and the source reg is live after
783	this instruction, then remove the source reg from the live set so
784	that it will not conflict with the destination reg. */
785	rtx ignore_reg = non_conflicting_reg_copy_p (curr_insn);
786	if (ignore_reg != NULL_RTX)
787	{
788	int ignore_regno = REGNO (ignore_reg);
789	if (HARD_REGISTER_NUM_P (ignore_regno)
790	&& TEST_HARD_REG_BIT (set: hard_regs_live, bit: ignore_regno))
791	CLEAR_HARD_REG_BIT (set&: hard_regs_live, bit: ignore_regno);
792	else if (!HARD_REGISTER_NUM_P (ignore_regno)
793	&& sparseset_bit_p (s: pseudos_live, e: ignore_regno))
794	sparseset_clear_bit (pseudos_live, ignore_regno);
795	else
796	/* We don't need any special handling of the source reg if
797	it is dead after this instruction. */
798	ignore_reg = NULL_RTX;
799	}
800
801	src_regno = (set != NULL_RTX && REG_P (SET_SRC (set))
802	? REGNO (SET_SRC (set)) : -1);
803	dst_regno = (set != NULL_RTX && REG_P (SET_DEST (set))
804	? REGNO (SET_DEST (set)) : -1);
805	if (complete_info_p
806	&& src_regno >= 0 && dst_regno >= 0
807	/* Check that source regno does not conflict with
808	destination regno to exclude most impossible
809	preferences. */
810	&& (((!HARD_REGISTER_NUM_P (src_regno)
811	&& (! sparseset_bit_p (s: pseudos_live, e: src_regno)
812	|| (!HARD_REGISTER_NUM_P (dst_regno)
813	&& lra_reg_val_equal_p (regno: src_regno,
814	val: lra_reg_info[dst_regno].val,
815	offset: lra_reg_info[dst_regno].offset))))
816	|| (HARD_REGISTER_NUM_P (src_regno)
817	&& ! TEST_HARD_REG_BIT (set: hard_regs_live, bit: src_regno)))
818	/* It might be 'inheritance pseudo <- reload pseudo'. */
819	|| (src_regno >= lra_constraint_new_regno_start
820	&& dst_regno >= lra_constraint_new_regno_start
821	/* Remember to skip special cases where src/dest regnos are
822	the same, e.g. insn SET pattern has matching constraints
823	like =r,0. */
824	&& src_regno != dst_regno)))
825	{
826	int hard_regno = -1, regno = -1;
827
828	if (dst_regno >= lra_constraint_new_regno_start
829	&& src_regno >= lra_constraint_new_regno_start)
830	{
831	/* It might be still an original (non-reload) insn with
832	one unused output and a constraint requiring to use
833	the same reg for input/output operands. In this case
834	dst_regno and src_regno have the same value, we don't
835	need a misleading copy for this case. */
836	if (dst_regno != src_regno)
837	lra_create_copy (dst_regno, src_regno, freq);
838	}
839	else if (dst_regno >= lra_constraint_new_regno_start)
840	{
841	if (!HARD_REGISTER_NUM_P (hard_regno = src_regno))
842	hard_regno = reg_renumber[src_regno];
843	regno = dst_regno;
844	}
845	else if (src_regno >= lra_constraint_new_regno_start)
846	{
847	if (!HARD_REGISTER_NUM_P (hard_regno = dst_regno))
848	hard_regno = reg_renumber[dst_regno];
849	regno = src_regno;
850	}
851	if (regno >= 0 && hard_regno >= 0)
852	lra_setup_reload_pseudo_preferenced_hard_reg
853	(regno, hard_regno, profit: freq);
854	}
855
856	sparseset_clear (s: start_living);
857
858	/* Mark each defined value as live. We need to do this for
859	unused values because they still conflict with quantities
860	that are live at the time of the definition. */
861	for (reg = curr_id->regs; reg != NULL; reg = reg->next)
862	if (reg->type != OP_IN)
863	{
864	update_pseudo_point (regno: reg->regno, point: curr_point, type: USE_POINT);
865	mark_regno_live (regno: reg->regno, mode: reg->biggest_mode);
866	/* ??? Should be a no-op for unused registers. */
867	check_pseudos_live_through_calls (regno: reg->regno, abi: last_call_abi);
868	}
869
870	for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
871	if (reg->type != OP_IN)
872	make_hard_regno_live (regno: reg->regno);
873
874	if (curr_id->arg_hard_regs != NULL)
875	for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
876	if (!HARD_REGISTER_NUM_P (regno))
877	/* It is a clobber. */
878	make_hard_regno_live (regno: regno - FIRST_PSEUDO_REGISTER);
879
880	sparseset_copy (unused_set, start_living);
881
882	sparseset_clear (s: start_dying);
883
884	/* See which defined values die here. */
885	for (reg = curr_id->regs; reg != NULL; reg = reg->next)
886	if (reg->type != OP_IN
887	&& ! reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
888	{
889	if (reg->type == OP_OUT)
890	update_pseudo_point (regno: reg->regno, point: curr_point, type: DEF_POINT);
891	mark_regno_dead (regno: reg->regno, mode: reg->biggest_mode);
892	}
893
894	for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
895	if (reg->type != OP_IN
896	&& ! reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
897	make_hard_regno_dead (regno: reg->regno);
898
899	if (curr_id->arg_hard_regs != NULL)
900	for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
901	if (!HARD_REGISTER_NUM_P (regno))
902	/* It is a clobber. */
903	make_hard_regno_dead (regno: regno - FIRST_PSEUDO_REGISTER);
904
905	if (call_p)
906	{
907	function_abi call_abi = insn_callee_abi (curr_insn);
908
909	if (last_call_abi != call_abi)
910	EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
911	check_pseudos_live_through_calls (regno: j, abi: last_call_abi);
912
913	last_call_abi = call_abi;
914
915	sparseset_ior (pseudos_live_through_calls,
916	pseudos_live_through_calls, pseudos_live);
917	if (cfun->has_nonlocal_label
918	|| (!targetm.setjmp_preserves_nonvolatile_regs_p ()
919	&& (find_reg_note (curr_insn, REG_SETJMP, NULL_RTX)
920	!= NULL_RTX)))
921	sparseset_ior (pseudos_live_through_setjumps,
922	pseudos_live_through_setjumps, pseudos_live);
923	}
924
925	/* Increment the current program point if we must. */
926	if (sparseset_contains_pseudos_p (a: unused_set)
927	|| sparseset_contains_pseudos_p (a: start_dying))
928	next_program_point (point&: curr_point, freq);
929
930	/* If we removed the source reg from a simple register copy from the
931	live set above, then add it back now so we don't accidentally add
932	it to the start_living set below. */
933	if (ignore_reg != NULL_RTX)
934	{
935	int ignore_regno = REGNO (ignore_reg);
936	if (HARD_REGISTER_NUM_P (ignore_regno))
937	SET_HARD_REG_BIT (set&: hard_regs_live, bit: ignore_regno);
938	else
939	sparseset_set_bit (s: pseudos_live, e: ignore_regno);
940	}
941
942	sparseset_clear (s: start_living);
943
944	/* Mark each used value as live. */
945	for (reg = curr_id->regs; reg != NULL; reg = reg->next)
946	if (reg->type != OP_OUT)
947	{
948	if (reg->type == OP_IN)
949	update_pseudo_point (regno: reg->regno, point: curr_point, type: USE_POINT);
950	mark_regno_live (regno: reg->regno, mode: reg->biggest_mode);
951	check_pseudos_live_through_calls (regno: reg->regno, abi: last_call_abi);
952	}
953
954	for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
955	if (reg->type != OP_OUT)
956	make_hard_regno_live (regno: reg->regno);
957
958	if (curr_id->arg_hard_regs != NULL)
959	/* Make argument hard registers live. */
960	for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
961	if (HARD_REGISTER_NUM_P (regno))
962	make_hard_regno_live (regno);
963
964	sparseset_and_compl (dead_set, start_living, start_dying);
965
966	sparseset_clear (s: start_dying);
967
968	/* Mark early clobber outputs dead. */
969	for (reg = curr_id->regs; reg != NULL; reg = reg->next)
970	if (reg->type != OP_IN
971	&& reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
972	{
973	if (reg->type == OP_OUT)
974	update_pseudo_point (regno: reg->regno, point: curr_point, type: DEF_POINT);
975	mark_regno_dead (regno: reg->regno, mode: reg->biggest_mode);
976
977	/* We're done processing inputs, so make sure early clobber
978	operands that are both inputs and outputs are still live. */
979	if (reg->type == OP_INOUT)
980	mark_regno_live (regno: reg->regno, mode: reg->biggest_mode);
981	}
982
983	for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
984	if (reg->type != OP_IN
985	&& reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
986	{
987	struct lra_insn_reg *reg2;
988
989	/* We can have early clobbered non-operand hard reg and
990	the same hard reg as an insn input. Don't make hard
991	reg dead before the insns. */
992	for (reg2 = curr_static_id->hard_regs; reg2 != NULL; reg2 = reg2->next)
993	if (reg2->type != OP_OUT && reg2->regno == reg->regno)
994	break;
995	if (reg2 == NULL)
996	make_hard_regno_dead (regno: reg->regno);
997	}
998
999	/* Increment the current program point if we must. */
1000	if (sparseset_contains_pseudos_p (a: dead_set)
1001	|| sparseset_contains_pseudos_p (a: start_dying))
1002	next_program_point (point&: curr_point, freq);
1003
1004	/* Update notes. */
1005	for (link_loc = &REG_NOTES (curr_insn); (link = *link_loc) != NULL_RTX;)
1006	{
1007	if (REG_NOTE_KIND (link) != REG_DEAD
1008	&& REG_NOTE_KIND (link) != REG_UNUSED)
1009	;
1010	else if (REG_P (XEXP (link, 0)))
1011	{
1012	rtx note_reg = XEXP (link, 0);
1013	int note_regno = REGNO (note_reg);
1014
1015	if ((REG_NOTE_KIND (link) == REG_DEAD
1016	&& ! regnos_in_sparseset_p (set: dead_set, regno: note_regno,
1017	GET_MODE (note_reg)))
1018	|| (REG_NOTE_KIND (link) == REG_UNUSED
1019	&& ! regnos_in_sparseset_p (set: unused_set, regno: note_regno,
1020	GET_MODE (note_reg))))
1021	{
1022	*link_loc = XEXP (link, 1);
1023	continue;
1024	}
1025	if (REG_NOTE_KIND (link) == REG_DEAD)
1026	clear_sparseset_regnos (set: dead_set, regno: note_regno,
1027	GET_MODE (note_reg));
1028	else if (REG_NOTE_KIND (link) == REG_UNUSED)
1029	clear_sparseset_regnos (set: unused_set, regno: note_regno,
1030	GET_MODE (note_reg));
1031	}
1032	link_loc = &XEXP (link, 1);
1033	}
1034	EXECUTE_IF_SET_IN_SPARSESET (dead_set, j)
1035	add_reg_note (curr_insn, REG_DEAD, regno_reg_rtx[j]);
1036	EXECUTE_IF_SET_IN_SPARSESET (unused_set, j)
1037	add_reg_note (curr_insn, REG_UNUSED, regno_reg_rtx[j]);
1038	}
1039
1040	if (bb_has_eh_pred (bb))
1041	/* Any pseudos that are currently live conflict with the eh_return
1042	data registers. For liveness purposes, these registers are set
1043	by artificial definitions at the start of the BB, so are not
1044	actually live on entry. */
1045	for (j = 0; ; ++j)
1046	{
1047	unsigned int regno = EH_RETURN_DATA_REGNO (j);
1048
1049	if (regno == INVALID_REGNUM)
1050	break;
1051
1052	make_hard_regno_live (regno);
1053	make_hard_regno_dead (regno);
1054	}
1055
1056	/* Pseudos can't go in stack regs at the start of a basic block that
1057	is reached by an abnormal edge. Likewise for registers that are at
1058	least partly call clobbered, because caller-save, fixup_abnormal_edges
1059	and possibly the table driven EH machinery are not quite ready to
1060	handle such pseudos live across such edges. */
1061	if (bb_has_abnormal_pred (bb))
1062	{
1063	HARD_REG_SET clobbers;
1064
1065	CLEAR_HARD_REG_SET (set&: clobbers);
1066	#ifdef STACK_REGS
1067	EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, px)
1068	lra_reg_info[px].no_stack_p = true;
1069	for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
1070	SET_HARD_REG_BIT (set&: clobbers, bit: px);
1071	#endif
1072	/* No need to record conflicts for call clobbered regs if we
1073	have nonlocal labels around, as we don't ever try to
1074	allocate such regs in this case. */
1075	if (!cfun->has_nonlocal_label
1076	&& has_abnormal_call_or_eh_pred_edge_p (bb))
1077	for (px = 0; HARD_REGISTER_NUM_P (px); px++)
1078	if (eh_edge_abi.clobbers_at_least_part_of_reg_p (regno: px)
1079	#ifdef REAL_PIC_OFFSET_TABLE_REGNUM
1080	/* We should create a conflict of PIC pseudo with PIC
1081	hard reg as PIC hard reg can have a wrong value after
1082	jump described by the abnormal edge. In this case we
1083	cannot allocate PIC hard reg to PIC pseudo as PIC
1084	pseudo will also have a wrong value. */
1085	|| (px == REAL_PIC_OFFSET_TABLE_REGNUM
1086	&& pic_offset_table_rtx != NULL_RTX
1087	&& !HARD_REGISTER_P (pic_offset_table_rtx))
1088	#endif
1089	)
1090	SET_HARD_REG_BIT (set&: clobbers, bit: px);
1091
1092	clobbers &= ~hard_regs_live;
1093	for (px = 0; HARD_REGISTER_NUM_P (px); px++)
1094	if (TEST_HARD_REG_BIT (set: clobbers, bit: px))
1095	{
1096	make_hard_regno_live (regno: px);
1097	make_hard_regno_dead (regno: px);
1098	}
1099	}
1100
1101	bool live_change_p = false;
1102	/* Check if bb border live info was changed. */
1103	unsigned int live_pseudos_num = 0;
1104	EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb),
1105	FIRST_PSEUDO_REGISTER, j, bi)
1106	{
1107	live_pseudos_num++;
1108	if (! sparseset_bit_p (s: pseudos_live, e: j))
1109	{
1110	live_change_p = true;
1111	if (lra_dump_file != NULL)
1112	fprintf (stream: lra_dump_file,
1113	format: " r%d is removed as live at bb%d start\n", j, bb->index);
1114	break;
1115	}
1116	}
1117	if (! live_change_p
1118	&& sparseset_cardinality (s: pseudos_live) != live_pseudos_num)
1119	{
1120	live_change_p = true;
1121	if (lra_dump_file != NULL)
1122	EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
1123	if (! bitmap_bit_p (df_get_live_in (bb), j))
1124	fprintf (stream: lra_dump_file,
1125	format: " r%d is added to live at bb%d start\n", j, bb->index);
1126	}
1127	/* See if we'll need an increment at the end of this basic block.
1128	An increment is needed if the PSEUDOS_LIVE set is not empty,
1129	to make sure the finish points are set up correctly. */
1130	need_curr_point_incr = (sparseset_cardinality (s: pseudos_live) > 0);
1131
1132	EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
1133	{
1134	update_pseudo_point (regno: i, point: curr_point, type: DEF_POINT);
1135	mark_pseudo_dead (regno: i);
1136	}
1137
1138	EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, j, bi)
1139	{
1140	if (sparseset_cardinality (s: pseudos_live_through_calls) == 0)
1141	break;
1142	if (sparseset_bit_p (s: pseudos_live_through_calls, e: j))
1143	check_pseudos_live_through_calls (regno: j, abi: last_call_abi);
1144	}
1145
1146	for (i = 0; HARD_REGISTER_NUM_P (i); ++i)
1147	{
1148	if (!TEST_HARD_REG_BIT (set: hard_regs_live, bit: i))
1149	continue;
1150
1151	if (!TEST_HARD_REG_BIT (set: hard_regs_spilled_into, bit: i))
1152	continue;
1153
1154	if (bitmap_bit_p (df_get_live_in (bb), i))
1155	continue;
1156
1157	live_change_p = true;
1158	if (lra_dump_file)
1159	fprintf (stream: lra_dump_file,
1160	format: " hard reg r%d is added to live at bb%d start\n", i,
1161	bb->index);
1162	bitmap_set_bit (df_get_live_in (bb), i);
1163	}
1164
1165	if (need_curr_point_incr)
1166	next_program_point (point&: curr_point, freq);
1167
1168	return live_change_p;
1169	}
1170
1171	/* Compress pseudo live ranges by removing program points where
1172	nothing happens. Complexity of many algorithms in LRA is linear
1173	function of program points number. To speed up the code we try to
1174	minimize the number of the program points here. */
1175	static void
1176	remove_some_program_points_and_update_live_ranges (void)
1177	{
1178	unsigned i;
1179	int n, max_regno;
1180	int *map;
1181	lra_live_range_t r, prev_r, next_r;
1182	sbitmap_iterator sbi;
1183	bool born_p, dead_p, prev_born_p, prev_dead_p;
1184
1185	auto_sbitmap born (lra_live_max_point);
1186	auto_sbitmap dead (lra_live_max_point);
1187	bitmap_clear (born);
1188	bitmap_clear (dead);
1189	max_regno = max_reg_num ();
1190	for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1191	{
1192	for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
1193	{
1194	lra_assert (r->start <= r->finish);
1195	bitmap_set_bit (map: born, bitno: r->start);
1196	bitmap_set_bit (map: dead, bitno: r->finish);
1197	}
1198	}
1199	auto_sbitmap born_or_dead (lra_live_max_point);
1200	bitmap_ior (born_or_dead, born, dead);
1201	map = XCNEWVEC (int, lra_live_max_point);
1202	n = -1;
1203	prev_born_p = prev_dead_p = false;
1204	EXECUTE_IF_SET_IN_BITMAP (born_or_dead, 0, i, sbi)
1205	{
1206	born_p = bitmap_bit_p (map: born, bitno: i);
1207	dead_p = bitmap_bit_p (map: dead, bitno: i);
1208	if ((prev_born_p && ! prev_dead_p && born_p && ! dead_p)
1209	|| (prev_dead_p && ! prev_born_p && dead_p && ! born_p))
1210	{
1211	map[i] = n;
1212	lra_point_freq[n] = MAX (lra_point_freq[n], lra_point_freq[i]);
1213	}
1214	else
1215	{
1216	map[i] = ++n;
1217	lra_point_freq[n] = lra_point_freq[i];
1218	}
1219	prev_born_p = born_p;
1220	prev_dead_p = dead_p;
1221	}
1222	n++;
1223	if (lra_dump_file != NULL)
1224	fprintf (stream: lra_dump_file, format: "Compressing live ranges: from %d to %d - %d%%\n",
1225	lra_live_max_point, n,
1226	lra_live_max_point ? 100 * n / lra_live_max_point : 100);
1227	if (n < lra_live_max_point)
1228	{
1229	lra_live_max_point = n;
1230	for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1231	{
1232	for (prev_r = NULL, r = lra_reg_info[i].live_ranges;
1233	r != NULL;
1234	r = next_r)
1235	{
1236	next_r = r->next;
1237	r->start = map[r->start];
1238	r->finish = map[r->finish];
1239	if (prev_r == NULL || prev_r->start > r->finish + 1)
1240	{
1241	prev_r = r;
1242	continue;
1243	}
1244	prev_r->start = r->start;
1245	prev_r->next = next_r;
1246	lra_live_range_pool.remove (object: r);
1247	}
1248	}
1249	}
1250	free (ptr: map);
1251	}
1252
1253	/* Print live ranges R to file F. */
1254	void
1255	lra_print_live_range_list (FILE *f, lra_live_range_t r)
1256	{
1257	for (; r != NULL; r = r->next)
1258	fprintf (stream: f, format: " [%d..%d]", r->start, r->finish);
1259	fprintf (stream: f, format: "\n");
1260	}
1261
1262	DEBUG_FUNCTION void
1263	debug (lra_live_range &ref)
1264	{
1265	lra_print_live_range_list (stderr, r: &ref);
1266	}
1267
1268	DEBUG_FUNCTION void
1269	debug (lra_live_range *ptr)
1270	{
1271	if (ptr)
1272	debug (ref&: *ptr);
1273	else
1274	fprintf (stderr, format: "<nil>\n");
1275	}
1276
1277	/* Print live ranges R to stderr. */
1278	void
1279	lra_debug_live_range_list (lra_live_range_t r)
1280	{
1281	lra_print_live_range_list (stderr, r);
1282	}
1283
1284	/* Print live ranges of pseudo REGNO to file F. */
1285	static void
1286	print_pseudo_live_ranges (FILE *f, int regno)
1287	{
1288	if (lra_reg_info[regno].live_ranges == NULL)
1289	return;
1290	fprintf (stream: f, format: " r%d:", regno);
1291	lra_print_live_range_list (f, r: lra_reg_info[regno].live_ranges);
1292	}
1293
1294	/* Print live ranges of pseudo REGNO to stderr. */
1295	void
1296	lra_debug_pseudo_live_ranges (int regno)
1297	{
1298	print_pseudo_live_ranges (stderr, regno);
1299	}
1300
1301	/* Print live ranges of all pseudos to file F. */
1302	static void
1303	print_live_ranges (FILE *f)
1304	{
1305	int i, max_regno;
1306
1307	max_regno = max_reg_num ();
1308	for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1309	print_pseudo_live_ranges (f, regno: i);
1310	}
1311
1312	/* Print live ranges of all pseudos to stderr. */
1313	void
1314	lra_debug_live_ranges (void)
1315	{
1316	print_live_ranges (stderr);
1317	}
1318
1319	/* Compress pseudo live ranges. */
1320	static void
1321	compress_live_ranges (void)
1322	{
1323	remove_some_program_points_and_update_live_ranges ();
1324	if (lra_dump_file != NULL)
1325	{
1326	fprintf (stream: lra_dump_file, format: "Ranges after the compression:\n");
1327	print_live_ranges (f: lra_dump_file);
1328	}
1329	}
1330
1331
1332
1333	/* The number of the current live range pass. */
1334	int lra_live_range_iter;
1335
1336	/* The function creates live ranges only for memory pseudos (or for
1337	all ones if ALL_P), set up CONFLICT_HARD_REGS for the pseudos. It
1338	also does dead insn elimination if DEAD_INSN_P and global live
1339	analysis only for pseudos and only if the pseudo live info was
1340	changed on a BB border. Return TRUE if the live info was
1341	changed. */
1342	static bool
1343	lra_create_live_ranges_1 (bool all_p, bool dead_insn_p)
1344	{
1345	basic_block bb;
1346	int i, hard_regno, max_regno = max_reg_num ();
1347	int curr_point;
1348	bool bb_live_change_p, have_referenced_pseudos = false;
1349
1350	timevar_push (tv: TV_LRA_CREATE_LIVE_RANGES);
1351
1352	complete_info_p = all_p;
1353	if (lra_dump_file != NULL)
1354	fprintf (stream: lra_dump_file,
1355	format: "\n********** Pseudo live ranges #%d: **********\n\n",
1356	++lra_live_range_iter);
1357	memset (s: lra_hard_reg_usage, c: 0, n: sizeof (lra_hard_reg_usage));
1358	for (i = 0; i < max_regno; i++)
1359	{
1360	lra_reg_info[i].live_ranges = NULL;
1361	CLEAR_HARD_REG_SET (set&: lra_reg_info[i].conflict_hard_regs);
1362	lra_reg_info[i].preferred_hard_regno1 = -1;
1363	lra_reg_info[i].preferred_hard_regno2 = -1;
1364	lra_reg_info[i].preferred_hard_regno_profit1 = 0;
1365	lra_reg_info[i].preferred_hard_regno_profit2 = 0;
1366	#ifdef STACK_REGS
1367	lra_reg_info[i].no_stack_p = false;
1368	#endif
1369	/* The biggest mode is already set but its value might be to
1370	conservative because of recent transformation. Here in this
1371	file we recalculate it again as it costs practically
1372	nothing. */
1373	if (!HARD_REGISTER_NUM_P (i) && regno_reg_rtx[i] != NULL_RTX)
1374	lra_reg_info[i].biggest_mode = GET_MODE (regno_reg_rtx[i]);
1375	else
1376	lra_reg_info[i].biggest_mode = VOIDmode;
1377	if (!HARD_REGISTER_NUM_P (i)
1378	&& lra_reg_info[i].nrefs != 0)
1379	{
1380	if ((hard_regno = reg_renumber[i]) >= 0)
1381	lra_hard_reg_usage[hard_regno] += lra_reg_info[i].freq;
1382	have_referenced_pseudos = true;
1383	}
1384	}
1385	lra_free_copies ();
1386
1387	/* Under some circumstances, we can have functions without pseudo
1388	registers. For such functions, lra_live_max_point will be 0,
1389	see e.g. PR55604, and there's nothing more to do for us here. */
1390	if (! have_referenced_pseudos)
1391	{
1392	timevar_pop (tv: TV_LRA_CREATE_LIVE_RANGES);
1393	return false;
1394	}
1395
1396	pseudos_live = sparseset_alloc (n_elms: max_regno);
1397	pseudos_live_through_calls = sparseset_alloc (n_elms: max_regno);
1398	pseudos_live_through_setjumps = sparseset_alloc (n_elms: max_regno);
1399	start_living = sparseset_alloc (n_elms: max_regno);
1400	start_dying = sparseset_alloc (n_elms: max_regno);
1401	dead_set = sparseset_alloc (n_elms: max_regno);
1402	unused_set = sparseset_alloc (n_elms: max_regno);
1403	curr_point = 0;
1404	unsigned new_length = get_max_uid () * 2;
1405	point_freq_vec.truncate (size: 0);
1406	point_freq_vec.reserve_exact (nelems: new_length);
1407	lra_point_freq = point_freq_vec.address ();
1408	int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
1409	int n = inverted_rev_post_order_compute (cfun, rpo);
1410	lra_assert (n == n_basic_blocks_for_fn (cfun));
1411	bb_live_change_p = false;
1412	for (i = 0; i < n; ++i)
1413	{
1414	bb = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
1415	if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb
1416	== ENTRY_BLOCK_PTR_FOR_FN (cfun))
1417	continue;
1418	if (process_bb_lives (bb, curr_point, dead_insn_p))
1419	bb_live_change_p = true;
1420	}
1421	free (ptr: rpo);
1422	if (bb_live_change_p)
1423	{
1424	/* We need to clear pseudo live info as some pseudos can
1425	disappear, e.g. pseudos with used equivalences. */
1426	FOR_EACH_BB_FN (bb, cfun)
1427	{
1428	bitmap_clear_range (df_get_live_in (bb), FIRST_PSEUDO_REGISTER,
1429	max_regno - FIRST_PSEUDO_REGISTER);
1430	bitmap_clear_range (df_get_live_out (bb), FIRST_PSEUDO_REGISTER,
1431	max_regno - FIRST_PSEUDO_REGISTER);
1432	}
1433	/* As we did not change CFG since LRA start we can use
1434	DF-infrastructure solver to solve live data flow problem. */
1435	for (int i = 0; HARD_REGISTER_NUM_P (i); ++i)
1436	{
1437	if (TEST_HARD_REG_BIT (set: hard_regs_spilled_into, bit: i))
1438	bitmap_clear_bit (&all_hard_regs_bitmap, i);
1439	}
1440	df_simple_dataflow
1441	(DF_BACKWARD, NULL, live_con_fun_0, live_con_fun_n,
1442	live_trans_fun, &all_blocks,
1443	df_get_postorder (DF_BACKWARD), df_get_n_blocks (DF_BACKWARD));
1444	if (lra_dump_file != NULL)
1445	{
1446	fprintf (stream: lra_dump_file,
1447	format: "Global pseudo live data have been updated:\n");
1448	basic_block bb;
1449	FOR_EACH_BB_FN (bb, cfun)
1450	{
1451	bb_data_t bb_info = get_bb_data (bb);
1452	bitmap bb_livein = df_get_live_in (bb);
1453	bitmap bb_liveout = df_get_live_out (bb);
1454
1455	fprintf (stream: lra_dump_file, format: "\nBB %d:\n", bb->index);
1456	lra_dump_bitmap_with_title (" gen:",
1457	&bb_info->gen_pseudos, bb->index);
1458	lra_dump_bitmap_with_title (" killed:",
1459	&bb_info->killed_pseudos, bb->index);
1460	lra_dump_bitmap_with_title (" livein:", bb_livein, bb->index);
1461	lra_dump_bitmap_with_title (" liveout:", bb_liveout, bb->index);
1462	}
1463	}
1464	}
1465	lra_live_max_point = curr_point;
1466	if (lra_dump_file != NULL)
1467	print_live_ranges (f: lra_dump_file);
1468	/* Clean up. */
1469	sparseset_free (unused_set);
1470	sparseset_free (dead_set);
1471	sparseset_free (start_dying);
1472	sparseset_free (start_living);
1473	sparseset_free (pseudos_live_through_calls);
1474	sparseset_free (pseudos_live_through_setjumps);
1475	sparseset_free (pseudos_live);
1476	compress_live_ranges ();
1477	timevar_pop (tv: TV_LRA_CREATE_LIVE_RANGES);
1478	return bb_live_change_p;
1479	}
1480
1481	/* The main entry function creates live-ranges and other live info
1482	necessary for the assignment sub-pass. It uses
1483	lra_creates_live_ranges_1 -- so read comments for the
1484	function. */
1485	void
1486	lra_create_live_ranges (bool all_p, bool dead_insn_p)
1487	{
1488	if (! lra_create_live_ranges_1 (all_p, dead_insn_p))
1489	return;
1490	if (lra_dump_file != NULL)
1491	fprintf (stream: lra_dump_file, format: "Live info was changed -- recalculate it\n");
1492	/* Live info was changed on a bb border. It means that some info,
1493	e.g. about conflict regs, calls crossed, and live ranges may be
1494	wrong. We need this info for allocation. So recalculate it
1495	again but without removing dead insns which can change live info
1496	again. Repetitive live range calculations are expensive therefore
1497	we stop here as we already have correct info although some
1498	improvement in rare cases could be possible on this sub-pass if
1499	we do dead insn elimination again (still the improvement may
1500	happen later). */
1501	lra_clear_live_ranges ();
1502	bool res = lra_create_live_ranges_1 (all_p, dead_insn_p: false);
1503	lra_assert (! res);
1504	}
1505
1506	/* Finish all live ranges. */
1507	void
1508	lra_clear_live_ranges (void)
1509	{
1510	int i;
1511
1512	for (i = 0; i < max_reg_num (); i++)
1513	free_live_range_list (lr: lra_reg_info[i].live_ranges);
1514	point_freq_vec.release ();
1515	}
1516
1517	/* Initialize live ranges data once per function. */
1518	void
1519	lra_live_ranges_init (void)
1520	{
1521	bitmap_initialize (head: &temp_bitmap, obstack: &reg_obstack);
1522	initiate_live_solver ();
1523	}
1524
1525	/* Finish live ranges data once per function. */
1526	void
1527	lra_live_ranges_finish (void)
1528	{
1529	finish_live_solver ();
1530	bitmap_clear (&temp_bitmap);
1531	lra_live_range_pool.release ();
1532	}
1533