1	/* Integrated Register Allocator (IRA) entry point.
2	Copyright (C) 2006-2023 Free Software Foundation, Inc.
3	Contributed by Vladimir Makarov <vmakarov@redhat.com>.
4
5	This file is part of GCC.
6
7	GCC is free software; you can redistribute it and/or modify it under
8	the terms of the GNU General Public License as published by the Free
9	Software Foundation; either version 3, or (at your option) any later
10	version.
11
12	GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13	WARRANTY; without even the implied warranty of MERCHANTABILITY or
14	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15	for more details.
16
17	You should have received a copy of the GNU General Public License
18	along with GCC; see the file COPYING3. If not see
19	<http://www.gnu.org/licenses/>. */
20
21	/* The integrated register allocator (IRA) is a
22	regional register allocator performing graph coloring on a top-down
23	traversal of nested regions. Graph coloring in a region is based
24	on Chaitin-Briggs algorithm. It is called integrated because
25	register coalescing, register live range splitting, and choosing a
26	better hard register are done on-the-fly during coloring. Register
27	coalescing and choosing a cheaper hard register is done by hard
28	register preferencing during hard register assigning. The live
29	range splitting is a byproduct of the regional register allocation.
30
31	Major IRA notions are:
32
33	o *Region* is a part of CFG where graph coloring based on
34	Chaitin-Briggs algorithm is done. IRA can work on any set of
35	nested CFG regions forming a tree. Currently the regions are
36	the entire function for the root region and natural loops for
37	the other regions. Therefore data structure representing a
38	region is called loop_tree_node.
39
40	o *Allocno class* is a register class used for allocation of
41	given allocno. It means that only hard register of given
42	register class can be assigned to given allocno. In reality,
43	even smaller subset of (*profitable*) hard registers can be
44	assigned. In rare cases, the subset can be even smaller
45	because our modification of Chaitin-Briggs algorithm requires
46	that sets of hard registers can be assigned to allocnos forms a
47	forest, i.e. the sets can be ordered in a way where any
48	previous set is not intersected with given set or is a superset
49	of given set.
50
51	o *Pressure class* is a register class belonging to a set of
52	register classes containing all of the hard-registers available
53	for register allocation. The set of all pressure classes for a
54	target is defined in the corresponding machine-description file
55	according some criteria. Register pressure is calculated only
56	for pressure classes and it affects some IRA decisions as
57	forming allocation regions.
58
59	o *Allocno* represents the live range of a pseudo-register in a
60	region. Besides the obvious attributes like the corresponding
61	pseudo-register number, allocno class, conflicting allocnos and
62	conflicting hard-registers, there are a few allocno attributes
63	which are important for understanding the allocation algorithm:
64
65	- *Live ranges*. This is a list of ranges of *program points*
66	where the allocno lives. Program points represent places
67	where a pseudo can be born or become dead (there are
68	approximately two times more program points than the insns)
69	and they are represented by integers starting with 0. The
70	live ranges are used to find conflicts between allocnos.
71	They also play very important role for the transformation of
72	the IRA internal representation of several regions into a one
73	region representation. The later is used during the reload
74	pass work because each allocno represents all of the
75	corresponding pseudo-registers.
76
77	- *Hard-register costs*. This is a vector of size equal to the
78	number of available hard-registers of the allocno class. The
79	cost of a callee-clobbered hard-register for an allocno is
80	increased by the cost of save/restore code around the calls
81	through the given allocno's life. If the allocno is a move
82	instruction operand and another operand is a hard-register of
83	the allocno class, the cost of the hard-register is decreased
84	by the move cost.
85
86	When an allocno is assigned, the hard-register with minimal
87	full cost is used. Initially, a hard-register's full cost is
88	the corresponding value from the hard-register's cost vector.
89	If the allocno is connected by a *copy* (see below) to
90	another allocno which has just received a hard-register, the
91	cost of the hard-register is decreased. Before choosing a
92	hard-register for an allocno, the allocno's current costs of
93	the hard-registers are modified by the conflict hard-register
94	costs of all of the conflicting allocnos which are not
95	assigned yet.
96
97	- *Conflict hard-register costs*. This is a vector of the same
98	size as the hard-register costs vector. To permit an
99	unassigned allocno to get a better hard-register, IRA uses
100	this vector to calculate the final full cost of the
101	available hard-registers. Conflict hard-register costs of an
102	unassigned allocno are also changed with a change of the
103	hard-register cost of the allocno when a copy involving the
104	allocno is processed as described above. This is done to
105	show other unassigned allocnos that a given allocno prefers
106	some hard-registers in order to remove the move instruction
107	corresponding to the copy.
108
109	o *Cap*. If a pseudo-register does not live in a region but
110	lives in a nested region, IRA creates a special allocno called
111	a cap in the outer region. A region cap is also created for a
112	subregion cap.
113
114	o *Copy*. Allocnos can be connected by copies. Copies are used
115	to modify hard-register costs for allocnos during coloring.
116	Such modifications reflects a preference to use the same
117	hard-register for the allocnos connected by copies. Usually
118	copies are created for move insns (in this case it results in
119	register coalescing). But IRA also creates copies for operands
120	of an insn which should be assigned to the same hard-register
121	due to constraints in the machine description (it usually
122	results in removing a move generated in reload to satisfy
123	the constraints) and copies referring to the allocno which is
124	the output operand of an instruction and the allocno which is
125	an input operand dying in the instruction (creation of such
126	copies results in less register shuffling). IRA *does not*
127	create copies between the same register allocnos from different
128	regions because we use another technique for propagating
129	hard-register preference on the borders of regions.
130
131	Allocnos (including caps) for the upper region in the region tree
132	*accumulate* information important for coloring from allocnos with
133	the same pseudo-register from nested regions. This includes
134	hard-register and memory costs, conflicts with hard-registers,
135	allocno conflicts, allocno copies and more. *Thus, attributes for
136	allocnos in a region have the same values as if the region had no
137	subregions*. It means that attributes for allocnos in the
138	outermost region corresponding to the function have the same values
139	as though the allocation used only one region which is the entire
140	function. It also means that we can look at IRA work as if the
141	first IRA did allocation for all function then it improved the
142	allocation for loops then their subloops and so on.
143
144	IRA major passes are:
145
146	o Building IRA internal representation which consists of the
147	following subpasses:
148
149	* First, IRA builds regions and creates allocnos (file
150	ira-build.cc) and initializes most of their attributes.
151
152	* Then IRA finds an allocno class for each allocno and
153	calculates its initial (non-accumulated) cost of memory and
154	each hard-register of its allocno class (file ira-cost.c).
155
156	* IRA creates live ranges of each allocno, calculates register
157	pressure for each pressure class in each region, sets up
158	conflict hard registers for each allocno and info about calls
159	the allocno lives through (file ira-lives.cc).
160
161	* IRA removes low register pressure loops from the regions
162	mostly to speed IRA up (file ira-build.cc).
163
164	* IRA propagates accumulated allocno info from lower region
165	allocnos to corresponding upper region allocnos (file
166	ira-build.cc).
167
168	* IRA creates all caps (file ira-build.cc).
169
170	* Having live-ranges of allocnos and their classes, IRA creates
171	conflicting allocnos for each allocno. Conflicting allocnos
172	are stored as a bit vector or array of pointers to the
173	conflicting allocnos whatever is more profitable (file
174	ira-conflicts.cc). At this point IRA creates allocno copies.
175
176	o Coloring. Now IRA has all necessary info to start graph coloring
177	process. It is done in each region on top-down traverse of the
178	region tree (file ira-color.cc). There are following subpasses:
179
180	* Finding profitable hard registers of corresponding allocno
181	class for each allocno. For example, only callee-saved hard
182	registers are frequently profitable for allocnos living
183	through colors. If the profitable hard register set of
184	allocno does not form a tree based on subset relation, we use
185	some approximation to form the tree. This approximation is
186	used to figure out trivial colorability of allocnos. The
187	approximation is a pretty rare case.
188
189	* Putting allocnos onto the coloring stack. IRA uses Briggs
190	optimistic coloring which is a major improvement over
191	Chaitin's coloring. Therefore IRA does not spill allocnos at
192	this point. There is some freedom in the order of putting
193	allocnos on the stack which can affect the final result of
194	the allocation. IRA uses some heuristics to improve the
195	order. The major one is to form *threads* from colorable
196	allocnos and push them on the stack by threads. Thread is a
197	set of non-conflicting colorable allocnos connected by
198	copies. The thread contains allocnos from the colorable
199	bucket or colorable allocnos already pushed onto the coloring
200	stack. Pushing thread allocnos one after another onto the
201	stack increases chances of removing copies when the allocnos
202	get the same hard reg.
203
204	We also use a modification of Chaitin-Briggs algorithm which
205	works for intersected register classes of allocnos. To
206	figure out trivial colorability of allocnos, the mentioned
207	above tree of hard register sets is used. To get an idea how
208	the algorithm works in i386 example, let us consider an
209	allocno to which any general hard register can be assigned.
210	If the allocno conflicts with eight allocnos to which only
211	EAX register can be assigned, given allocno is still
212	trivially colorable because all conflicting allocnos might be
213	assigned only to EAX and all other general hard registers are
214	still free.
215
216	To get an idea of the used trivial colorability criterion, it
217	is also useful to read article "Graph-Coloring Register
218	Allocation for Irregular Architectures" by Michael D. Smith
219	and Glen Holloway. Major difference between the article
220	approach and approach used in IRA is that Smith's approach
221	takes register classes only from machine description and IRA
222	calculate register classes from intermediate code too
223	(e.g. an explicit usage of hard registers in RTL code for
224	parameter passing can result in creation of additional
225	register classes which contain or exclude the hard
226	registers). That makes IRA approach useful for improving
227	coloring even for architectures with regular register files
228	and in fact some benchmarking shows the improvement for
229	regular class architectures is even bigger than for irregular
230	ones. Another difference is that Smith's approach chooses
231	intersection of classes of all insn operands in which a given
232	pseudo occurs. IRA can use bigger classes if it is still
233	more profitable than memory usage.
234
235	* Popping the allocnos from the stack and assigning them hard
236	registers. If IRA cannot assign a hard register to an
237	allocno and the allocno is coalesced, IRA undoes the
238	coalescing and puts the uncoalesced allocnos onto the stack in
239	the hope that some such allocnos will get a hard register
240	separately. If IRA fails to assign hard register or memory
241	is more profitable for it, IRA spills the allocno. IRA
242	assigns the allocno the hard-register with minimal full
243	allocation cost which reflects the cost of usage of the
244	hard-register for the allocno and cost of usage of the
245	hard-register for allocnos conflicting with given allocno.
246
247	* Chaitin-Briggs coloring assigns as many pseudos as possible
248	to hard registers. After coloring we try to improve
249	allocation with cost point of view. We improve the
250	allocation by spilling some allocnos and assigning the freed
251	hard registers to other allocnos if it decreases the overall
252	allocation cost.
253
254	* After allocno assigning in the region, IRA modifies the hard
255	register and memory costs for the corresponding allocnos in
256	the subregions to reflect the cost of possible loads, stores,
257	or moves on the border of the region and its subregions.
258	When default regional allocation algorithm is used
259	(-fira-algorithm=mixed), IRA just propagates the assignment
260	for allocnos if the register pressure in the region for the
261	corresponding pressure class is less than number of available
262	hard registers for given pressure class.
263
264	o Spill/restore code moving. When IRA performs an allocation
265	by traversing regions in top-down order, it does not know what
266	happens below in the region tree. Therefore, sometimes IRA
267	misses opportunities to perform a better allocation. A simple
268	optimization tries to improve allocation in a region having
269	subregions and containing in another region. If the
270	corresponding allocnos in the subregion are spilled, it spills
271	the region allocno if it is profitable. The optimization
272	implements a simple iterative algorithm performing profitable
273	transformations while they are still possible. It is fast in
274	practice, so there is no real need for a better time complexity
275	algorithm.
276
277	o Code change. After coloring, two allocnos representing the
278	same pseudo-register outside and inside a region respectively
279	may be assigned to different locations (hard-registers or
280	memory). In this case IRA creates and uses a new
281	pseudo-register inside the region and adds code to move allocno
282	values on the region's borders. This is done during top-down
283	traversal of the regions (file ira-emit.cc). In some
284	complicated cases IRA can create a new allocno to move allocno
285	values (e.g. when a swap of values stored in two hard-registers
286	is needed). At this stage, the new allocno is marked as
287	spilled. IRA still creates the pseudo-register and the moves
288	on the region borders even when both allocnos were assigned to
289	the same hard-register. If the reload pass spills a
290	pseudo-register for some reason, the effect will be smaller
291	because another allocno will still be in the hard-register. In
292	most cases, this is better then spilling both allocnos. If
293	reload does not change the allocation for the two
294	pseudo-registers, the trivial move will be removed by
295	post-reload optimizations. IRA does not generate moves for
296	allocnos assigned to the same hard register when the default
297	regional allocation algorithm is used and the register pressure
298	in the region for the corresponding pressure class is less than
299	number of available hard registers for given pressure class.
300	IRA also does some optimizations to remove redundant stores and
301	to reduce code duplication on the region borders.
302
303	o Flattening internal representation. After changing code, IRA
304	transforms its internal representation for several regions into
305	one region representation (file ira-build.cc). This process is
306	called IR flattening. Such process is more complicated than IR
307	rebuilding would be, but is much faster.
308
309	o After IR flattening, IRA tries to assign hard registers to all
310	spilled allocnos. This is implemented by a simple and fast
311	priority coloring algorithm (see function
312	ira_reassign_conflict_allocnos::ira-color.cc). Here new allocnos
313	created during the code change pass can be assigned to hard
314	registers.
315
316	o At the end IRA calls the reload pass. The reload pass
317	communicates with IRA through several functions in file
318	ira-color.cc to improve its decisions in
319
320	* sharing stack slots for the spilled pseudos based on IRA info
321	about pseudo-register conflicts.
322
323	* reassigning hard-registers to all spilled pseudos at the end
324	of each reload iteration.
325
326	* choosing a better hard-register to spill based on IRA info
327	about pseudo-register live ranges and the register pressure
328	in places where the pseudo-register lives.
329
330	IRA uses a lot of data representing the target processors. These
331	data are initialized in file ira.cc.
332
333	If function has no loops (or the loops are ignored when
334	-fira-algorithm=CB is used), we have classic Chaitin-Briggs
335	coloring (only instead of separate pass of coalescing, we use hard
336	register preferencing). In such case, IRA works much faster
337	because many things are not made (like IR flattening, the
338	spill/restore optimization, and the code change).
339
340	Literature is worth to read for better understanding the code:
341
342	o Preston Briggs, Keith D. Cooper, Linda Torczon. Improvements to
343	Graph Coloring Register Allocation.
344
345	o David Callahan, Brian Koblenz. Register allocation via
346	hierarchical graph coloring.
347
348	o Keith Cooper, Anshuman Dasgupta, Jason Eckhardt. Revisiting Graph
349	Coloring Register Allocation: A Study of the Chaitin-Briggs and
350	Callahan-Koblenz Algorithms.
351
352	o Guei-Yuan Lueh, Thomas Gross, and Ali-Reza Adl-Tabatabai. Global
353	Register Allocation Based on Graph Fusion.
354
355	o Michael D. Smith and Glenn Holloway. Graph-Coloring Register
356	Allocation for Irregular Architectures
357
358	o Vladimir Makarov. The Integrated Register Allocator for GCC.
359
360	o Vladimir Makarov. The top-down register allocator for irregular
361	register file architectures.
362
363	*/
364
365
366	#include "config.h"
367	#include "system.h"
368	#include "coretypes.h"
369	#include "backend.h"
370	#include "target.h"
371	#include "rtl.h"
372	#include "tree.h"
373	#include "df.h"
374	#include "memmodel.h"
375	#include "tm_p.h"
376	#include "insn-config.h"
377	#include "regs.h"
378	#include "ira.h"
379	#include "ira-int.h"
380	#include "diagnostic-core.h"
381	#include "cfgrtl.h"
382	#include "cfgbuild.h"
383	#include "cfgcleanup.h"
384	#include "expr.h"
385	#include "tree-pass.h"
386	#include "output.h"
387	#include "reload.h"
388	#include "cfgloop.h"
389	#include "lra.h"
390	#include "dce.h"
391	#include "dbgcnt.h"
392	#include "rtl-iter.h"
393	#include "shrink-wrap.h"
394	#include "print-rtl.h"
395
396	struct target_ira default_target_ira;
397	class target_ira_int default_target_ira_int;
398	#if SWITCHABLE_TARGET
399	struct target_ira *this_target_ira = &default_target_ira;
400	class target_ira_int *this_target_ira_int = &default_target_ira_int;
401	#endif
402
403	/* A modified value of flag `-fira-verbose' used internally. */
404	int internal_flag_ira_verbose;
405
406	/* Dump file of the allocator if it is not NULL. */
407	FILE *ira_dump_file;
408
409	/* The number of elements in the following array. */
410	int ira_spilled_reg_stack_slots_num;
411
412	/* The following array contains info about spilled pseudo-registers
413	stack slots used in current function so far. */
414	class ira_spilled_reg_stack_slot *ira_spilled_reg_stack_slots;
415
416	/* Correspondingly overall cost of the allocation, overall cost before
417	reload, cost of the allocnos assigned to hard-registers, cost of
418	the allocnos assigned to memory, cost of loads, stores and register
419	move insns generated for pseudo-register live range splitting (see
420	ira-emit.cc). */
421	int64_t ira_overall_cost, overall_cost_before;
422	int64_t ira_reg_cost, ira_mem_cost;
423	int64_t ira_load_cost, ira_store_cost, ira_shuffle_cost;
424	int ira_move_loops_num, ira_additional_jumps_num;
425
426	/* All registers that can be eliminated. */
427
428	HARD_REG_SET eliminable_regset;
429
430	/* Value of max_reg_num () before IRA work start. This value helps
431	us to recognize a situation when new pseudos were created during
432	IRA work. */
433	static int max_regno_before_ira;
434
435	/* Temporary hard reg set used for a different calculation. */
436	static HARD_REG_SET temp_hard_regset;
437
438	#define last_mode_for_init_move_cost \
439	(this_target_ira_int->x_last_mode_for_init_move_cost)
440
441
442	/* The function sets up the map IRA_REG_MODE_HARD_REGSET. */
443	static void
444	setup_reg_mode_hard_regset (void)
445	{
446	int i, m, hard_regno;
447
448	for (m = 0; m < NUM_MACHINE_MODES; m++)
449	for (hard_regno = 0; hard_regno < FIRST_PSEUDO_REGISTER; hard_regno++)
450	{
451	CLEAR_HARD_REG_SET (ira_reg_mode_hard_regset[hard_regno][m]);
452	for (i = hard_regno_nregs (regno: hard_regno, mode: (machine_mode) m) - 1;
453	i >= 0; i--)
454	if (hard_regno + i < FIRST_PSEUDO_REGISTER)
455	SET_HARD_REG_BIT (ira_reg_mode_hard_regset[hard_regno][m],
456	bit: hard_regno + i);
457	}
458	}
459
460
461	#define no_unit_alloc_regs \
462	(this_target_ira_int->x_no_unit_alloc_regs)
463
464	/* The function sets up the three arrays declared above. */
465	static void
466	setup_class_hard_regs (void)
467	{
468	int cl, i, hard_regno, n;
469	HARD_REG_SET processed_hard_reg_set;
470
471	ira_assert (SHRT_MAX >= FIRST_PSEUDO_REGISTER);
472	for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
473	{
474	temp_hard_regset = reg_class_contents[cl] & ~no_unit_alloc_regs;
475	CLEAR_HARD_REG_SET (set&: processed_hard_reg_set);
476	for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
477	{
478	ira_non_ordered_class_hard_regs[cl][i] = -1;
479	ira_class_hard_reg_index[cl][i] = -1;
480	}
481	for (n = 0, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
482	{
483	#ifdef REG_ALLOC_ORDER
484	hard_regno = reg_alloc_order[i];
485	#else
486	hard_regno = i;
487	#endif
488	if (TEST_HARD_REG_BIT (set: processed_hard_reg_set, bit: hard_regno))
489	continue;
490	SET_HARD_REG_BIT (set&: processed_hard_reg_set, bit: hard_regno);
491	if (! TEST_HARD_REG_BIT (set: temp_hard_regset, bit: hard_regno))
492	ira_class_hard_reg_index[cl][hard_regno] = -1;
493	else
494	{
495	ira_class_hard_reg_index[cl][hard_regno] = n;
496	ira_class_hard_regs[cl][n++] = hard_regno;
497	}
498	}
499	ira_class_hard_regs_num[cl] = n;
500	for (n = 0, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
501	if (TEST_HARD_REG_BIT (set: temp_hard_regset, bit: i))
502	ira_non_ordered_class_hard_regs[cl][n++] = i;
503	ira_assert (ira_class_hard_regs_num[cl] == n);
504	}
505	}
506
507	/* Set up global variables defining info about hard registers for the
508	allocation. These depend on USE_HARD_FRAME_P whose TRUE value means
509	that we can use the hard frame pointer for the allocation. */
510	static void
511	setup_alloc_regs (bool use_hard_frame_p)
512	{
513	#ifdef ADJUST_REG_ALLOC_ORDER
514	ADJUST_REG_ALLOC_ORDER;
515	#endif
516	no_unit_alloc_regs = fixed_nonglobal_reg_set;
517	if (! use_hard_frame_p)
518	add_to_hard_reg_set (regs: &no_unit_alloc_regs, Pmode,
519	HARD_FRAME_POINTER_REGNUM);
520	setup_class_hard_regs ();
521	}
522
523
524
525	#define alloc_reg_class_subclasses \
526	(this_target_ira_int->x_alloc_reg_class_subclasses)
527
528	/* Initialize the table of subclasses of each reg class. */
529	static void
530	setup_reg_subclasses (void)
531	{
532	int i, j;
533	HARD_REG_SET temp_hard_regset2;
534
535	for (i = 0; i < N_REG_CLASSES; i++)
536	for (j = 0; j < N_REG_CLASSES; j++)
537	alloc_reg_class_subclasses[i][j] = LIM_REG_CLASSES;
538
539	for (i = 0; i < N_REG_CLASSES; i++)
540	{
541	if (i == (int) NO_REGS)
542	continue;
543
544	temp_hard_regset = reg_class_contents[i] & ~no_unit_alloc_regs;
545	if (hard_reg_set_empty_p (x: temp_hard_regset))
546	continue;
547	for (j = 0; j < N_REG_CLASSES; j++)
548	if (i != j)
549	{
550	enum reg_class *p;
551
552	temp_hard_regset2 = reg_class_contents[j] & ~no_unit_alloc_regs;
553	if (! hard_reg_set_subset_p (x: temp_hard_regset,
554	y: temp_hard_regset2))
555	continue;
556	p = &alloc_reg_class_subclasses[j][0];
557	while (*p != LIM_REG_CLASSES) p++;
558	*p = (enum reg_class) i;
559	}
560	}
561	}
562
563
564
565	/* Set up IRA_MEMORY_MOVE_COST and IRA_MAX_MEMORY_MOVE_COST. */
566	static void
567	setup_class_subset_and_memory_move_costs (void)
568	{
569	int cl, cl2, mode, cost;
570	HARD_REG_SET temp_hard_regset2;
571
572	for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
573	ira_memory_move_cost[mode][NO_REGS][0]
574	= ira_memory_move_cost[mode][NO_REGS][1] = SHRT_MAX;
575	for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
576	{
577	if (cl != (int) NO_REGS)
578	for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
579	{
580	ira_max_memory_move_cost[mode][cl][0]
581	= ira_memory_move_cost[mode][cl][0]
582	= memory_move_cost ((machine_mode) mode,
583	(reg_class_t) cl, false);
584	ira_max_memory_move_cost[mode][cl][1]
585	= ira_memory_move_cost[mode][cl][1]
586	= memory_move_cost ((machine_mode) mode,
587	(reg_class_t) cl, true);
588	/* Costs for NO_REGS are used in cost calculation on the
589	1st pass when the preferred register classes are not
590	known yet. In this case we take the best scenario. */
591	if (!targetm.hard_regno_mode_ok (ira_class_hard_regs[cl][0],
592	(machine_mode) mode))
593	continue;
594
595	if (ira_memory_move_cost[mode][NO_REGS][0]
596	> ira_memory_move_cost[mode][cl][0])
597	ira_max_memory_move_cost[mode][NO_REGS][0]
598	= ira_memory_move_cost[mode][NO_REGS][0]
599	= ira_memory_move_cost[mode][cl][0];
600	if (ira_memory_move_cost[mode][NO_REGS][1]
601	> ira_memory_move_cost[mode][cl][1])
602	ira_max_memory_move_cost[mode][NO_REGS][1]
603	= ira_memory_move_cost[mode][NO_REGS][1]
604	= ira_memory_move_cost[mode][cl][1];
605	}
606	}
607	for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
608	for (cl2 = (int) N_REG_CLASSES - 1; cl2 >= 0; cl2--)
609	{
610	temp_hard_regset = reg_class_contents[cl] & ~no_unit_alloc_regs;
611	temp_hard_regset2 = reg_class_contents[cl2] & ~no_unit_alloc_regs;
612	ira_class_subset_p[cl][cl2]
613	= hard_reg_set_subset_p (x: temp_hard_regset, y: temp_hard_regset2);
614	if (! hard_reg_set_empty_p (x: temp_hard_regset2)
615	&& hard_reg_set_subset_p (reg_class_contents[cl2],
616	reg_class_contents[cl]))
617	for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
618	{
619	cost = ira_memory_move_cost[mode][cl2][0];
620	if (cost > ira_max_memory_move_cost[mode][cl][0])
621	ira_max_memory_move_cost[mode][cl][0] = cost;
622	cost = ira_memory_move_cost[mode][cl2][1];
623	if (cost > ira_max_memory_move_cost[mode][cl][1])
624	ira_max_memory_move_cost[mode][cl][1] = cost;
625	}
626	}
627	for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
628	for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
629	{
630	ira_memory_move_cost[mode][cl][0]
631	= ira_max_memory_move_cost[mode][cl][0];
632	ira_memory_move_cost[mode][cl][1]
633	= ira_max_memory_move_cost[mode][cl][1];
634	}
635	setup_reg_subclasses ();
636	}
637
638
639
640	/* Define the following macro if allocation through malloc if
641	preferable. */
642	#define IRA_NO_OBSTACK
643
644	#ifndef IRA_NO_OBSTACK
645	/* Obstack used for storing all dynamic data (except bitmaps) of the
646	IRA. */
647	static struct obstack ira_obstack;
648	#endif
649
650	/* Obstack used for storing all bitmaps of the IRA. */
651	static struct bitmap_obstack ira_bitmap_obstack;
652
653	/* Allocate memory of size LEN for IRA data. */
654	void *
655	ira_allocate (size_t len)
656	{
657	void *res;
658
659	#ifndef IRA_NO_OBSTACK
660	res = obstack_alloc (&ira_obstack, len);
661	#else
662	res = xmalloc (len);
663	#endif
664	return res;
665	}
666
667	/* Free memory ADDR allocated for IRA data. */
668	void
669	ira_free (void *addr ATTRIBUTE_UNUSED)
670	{
671	#ifndef IRA_NO_OBSTACK
672	/* do nothing */
673	#else
674	free (ptr: addr);
675	#endif
676	}
677
678
679	/* Allocate and returns bitmap for IRA. */
680	bitmap
681	ira_allocate_bitmap (void)
682	{
683	return BITMAP_ALLOC (obstack: &ira_bitmap_obstack);
684	}
685
686	/* Free bitmap B allocated for IRA. */
687	void
688	ira_free_bitmap (bitmap b ATTRIBUTE_UNUSED)
689	{
690	/* do nothing */
691	}
692
693
694
695	/* Output information about allocation of all allocnos (except for
696	caps) into file F. */
697	void
698	ira_print_disposition (FILE *f)
699	{
700	int i, n, max_regno;
701	ira_allocno_t a;
702	basic_block bb;
703
704	fprintf (stream: f, format: "Disposition:");
705	max_regno = max_reg_num ();
706	for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
707	for (a = ira_regno_allocno_map[i];
708	a != NULL;
709	a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
710	{
711	if (n % 4 == 0)
712	fprintf (stream: f, format: "\n");
713	n++;
714	fprintf (stream: f, format: " %4d:r%-4d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
715	if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
716	fprintf (stream: f, format: "b%-3d", bb->index);
717	else
718	fprintf (stream: f, format: "l%-3d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
719	if (ALLOCNO_HARD_REGNO (a) >= 0)
720	fprintf (stream: f, format: " %3d", ALLOCNO_HARD_REGNO (a));
721	else
722	fprintf (stream: f, format: " mem");
723	}
724	fprintf (stream: f, format: "\n");
725	}
726
727	/* Outputs information about allocation of all allocnos into
728	stderr. */
729	void
730	ira_debug_disposition (void)
731	{
732	ira_print_disposition (stderr);
733	}
734
735
736
737	/* Set up ira_stack_reg_pressure_class which is the biggest pressure
738	register class containing stack registers or NO_REGS if there are
739	no stack registers. To find this class, we iterate through all
740	register pressure classes and choose the first register pressure
741	class containing all the stack registers and having the biggest
742	size. */
743	static void
744	setup_stack_reg_pressure_class (void)
745	{
746	ira_stack_reg_pressure_class = NO_REGS;
747	#ifdef STACK_REGS
748	{
749	int i, best, size;
750	enum reg_class cl;
751	HARD_REG_SET temp_hard_regset2;
752
753	CLEAR_HARD_REG_SET (set&: temp_hard_regset);
754	for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
755	SET_HARD_REG_BIT (set&: temp_hard_regset, bit: i);
756	best = 0;
757	for (i = 0; i < ira_pressure_classes_num; i++)
758	{
759	cl = ira_pressure_classes[i];
760	temp_hard_regset2 = temp_hard_regset & reg_class_contents[cl];
761	size = hard_reg_set_size (set: temp_hard_regset2);
762	if (best < size)
763	{
764	best = size;
765	ira_stack_reg_pressure_class = cl;
766	}
767	}
768	}
769	#endif
770	}
771
772	/* Find pressure classes which are register classes for which we
773	calculate register pressure in IRA, register pressure sensitive
774	insn scheduling, and register pressure sensitive loop invariant
775	motion.
776
777	To make register pressure calculation easy, we always use
778	non-intersected register pressure classes. A move of hard
779	registers from one register pressure class is not more expensive
780	than load and store of the hard registers. Most likely an allocno
781	class will be a subset of a register pressure class and in many
782	cases a register pressure class. That makes usage of register
783	pressure classes a good approximation to find a high register
784	pressure. */
785	static void
786	setup_pressure_classes (void)
787	{
788	int cost, i, n, curr;
789	int cl, cl2;
790	enum reg_class pressure_classes[N_REG_CLASSES];
791	int m;
792	HARD_REG_SET temp_hard_regset2;
793	bool insert_p;
794
795	if (targetm.compute_pressure_classes)
796	n = targetm.compute_pressure_classes (pressure_classes);
797	else
798	{
799	n = 0;
800	for (cl = 0; cl < N_REG_CLASSES; cl++)
801	{
802	if (ira_class_hard_regs_num[cl] == 0)
803	continue;
804	if (ira_class_hard_regs_num[cl] != 1
805	/* A register class without subclasses may contain a few
806	hard registers and movement between them is costly
807	(e.g. SPARC FPCC registers). We still should consider it
808	as a candidate for a pressure class. */
809	&& alloc_reg_class_subclasses[cl][0] < cl)
810	{
811	/* Check that the moves between any hard registers of the
812	current class are not more expensive for a legal mode
813	than load/store of the hard registers of the current
814	class. Such class is a potential candidate to be a
815	register pressure class. */
816	for (m = 0; m < NUM_MACHINE_MODES; m++)
817	{
818	temp_hard_regset
819	= (reg_class_contents[cl]
820	& ~(no_unit_alloc_regs
821	| ira_prohibited_class_mode_regs[cl][m]));
822	if (hard_reg_set_empty_p (x: temp_hard_regset))
823	continue;
824	ira_init_register_move_cost_if_necessary (mode: (machine_mode) m);
825	cost = ira_register_move_cost[m][cl][cl];
826	if (cost <= ira_max_memory_move_cost[m][cl][1]
827	|| cost <= ira_max_memory_move_cost[m][cl][0])
828	break;
829	}
830	if (m >= NUM_MACHINE_MODES)
831	continue;
832	}
833	curr = 0;
834	insert_p = true;
835	temp_hard_regset = reg_class_contents[cl] & ~no_unit_alloc_regs;
836	/* Remove so far added pressure classes which are subset of the
837	current candidate class. Prefer GENERAL_REGS as a pressure
838	register class to another class containing the same
839	allocatable hard registers. We do this because machine
840	dependent cost hooks might give wrong costs for the latter
841	class but always give the right cost for the former class
842	(GENERAL_REGS). */
843	for (i = 0; i < n; i++)
844	{
845	cl2 = pressure_classes[i];
846	temp_hard_regset2 = (reg_class_contents[cl2]
847	& ~no_unit_alloc_regs);
848	if (hard_reg_set_subset_p (x: temp_hard_regset, y: temp_hard_regset2)
849	&& (temp_hard_regset != temp_hard_regset2
850	|| cl2 == (int) GENERAL_REGS))
851	{
852	pressure_classes[curr++] = (enum reg_class) cl2;
853	insert_p = false;
854	continue;
855	}
856	if (hard_reg_set_subset_p (x: temp_hard_regset2, y: temp_hard_regset)
857	&& (temp_hard_regset2 != temp_hard_regset
858	|| cl == (int) GENERAL_REGS))
859	continue;
860	if (temp_hard_regset2 == temp_hard_regset)
861	insert_p = false;
862	pressure_classes[curr++] = (enum reg_class) cl2;
863	}
864	/* If the current candidate is a subset of a so far added
865	pressure class, don't add it to the list of the pressure
866	classes. */
867	if (insert_p)
868	pressure_classes[curr++] = (enum reg_class) cl;
869	n = curr;
870	}
871	}
872	#ifdef ENABLE_IRA_CHECKING
873	{
874	HARD_REG_SET ignore_hard_regs;
875
876	/* Check pressure classes correctness: here we check that hard
877	registers from all register pressure classes contains all hard
878	registers available for the allocation. */
879	CLEAR_HARD_REG_SET (set&: temp_hard_regset);
880	CLEAR_HARD_REG_SET (set&: temp_hard_regset2);
881	ignore_hard_regs = no_unit_alloc_regs;
882	for (cl = 0; cl < LIM_REG_CLASSES; cl++)
883	{
884	/* For some targets (like MIPS with MD_REGS), there are some
885	classes with hard registers available for allocation but
886	not able to hold value of any mode. */
887	for (m = 0; m < NUM_MACHINE_MODES; m++)
888	if (contains_reg_of_mode[cl][m])
889	break;
890	if (m >= NUM_MACHINE_MODES)
891	{
892	ignore_hard_regs |= reg_class_contents[cl];
893	continue;
894	}
895	for (i = 0; i < n; i++)
896	if ((int) pressure_classes[i] == cl)
897	break;
898	temp_hard_regset2 |= reg_class_contents[cl];
899	if (i < n)
900	temp_hard_regset |= reg_class_contents[cl];
901	}
902	for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
903	/* Some targets (like SPARC with ICC reg) have allocatable regs
904	for which no reg class is defined. */
905	if (REGNO_REG_CLASS (i) == NO_REGS)
906	SET_HARD_REG_BIT (set&: ignore_hard_regs, bit: i);
907	temp_hard_regset &= ~ignore_hard_regs;
908	temp_hard_regset2 &= ~ignore_hard_regs;
909	ira_assert (hard_reg_set_subset_p (temp_hard_regset2, temp_hard_regset));
910	}
911	#endif
912	ira_pressure_classes_num = 0;
913	for (i = 0; i < n; i++)
914	{
915	cl = (int) pressure_classes[i];
916	ira_reg_pressure_class_p[cl] = true;
917	ira_pressure_classes[ira_pressure_classes_num++] = (enum reg_class) cl;
918	}
919	setup_stack_reg_pressure_class ();
920	}
921
922	/* Set up IRA_UNIFORM_CLASS_P. Uniform class is a register class
923	whose register move cost between any registers of the class is the
924	same as for all its subclasses. We use the data to speed up the
925	2nd pass of calculations of allocno costs. */
926	static void
927	setup_uniform_class_p (void)
928	{
929	int i, cl, cl2, m;
930
931	for (cl = 0; cl < N_REG_CLASSES; cl++)
932	{
933	ira_uniform_class_p[cl] = false;
934	if (ira_class_hard_regs_num[cl] == 0)
935	continue;
936	/* We cannot use alloc_reg_class_subclasses here because move
937	cost hooks does not take into account that some registers are
938	unavailable for the subtarget. E.g. for i686, INT_SSE_REGS
939	is element of alloc_reg_class_subclasses for GENERAL_REGS
940	because SSE regs are unavailable. */
941	for (i = 0; (cl2 = reg_class_subclasses[cl][i]) != LIM_REG_CLASSES; i++)
942	{
943	if (ira_class_hard_regs_num[cl2] == 0)
944	continue;
945	for (m = 0; m < NUM_MACHINE_MODES; m++)
946	if (contains_reg_of_mode[cl][m] && contains_reg_of_mode[cl2][m])
947	{
948	ira_init_register_move_cost_if_necessary (mode: (machine_mode) m);
949	if (ira_register_move_cost[m][cl][cl]
950	!= ira_register_move_cost[m][cl2][cl2])
951	break;
952	}
953	if (m < NUM_MACHINE_MODES)
954	break;
955	}
956	if (cl2 == LIM_REG_CLASSES)
957	ira_uniform_class_p[cl] = true;
958	}
959	}
960
961	/* Set up IRA_ALLOCNO_CLASSES, IRA_ALLOCNO_CLASSES_NUM,
962	IRA_IMPORTANT_CLASSES, and IRA_IMPORTANT_CLASSES_NUM.
963
964	Target may have many subtargets and not all target hard registers can
965	be used for allocation, e.g. x86 port in 32-bit mode cannot use
966	hard registers introduced in x86-64 like r8-r15). Some classes
967	might have the same allocatable hard registers, e.g. INDEX_REGS
968	and GENERAL_REGS in x86 port in 32-bit mode. To decrease different
969	calculations efforts we introduce allocno classes which contain
970	unique non-empty sets of allocatable hard-registers.
971
972	Pseudo class cost calculation in ira-costs.cc is very expensive.
973	Therefore we are trying to decrease number of classes involved in
974	such calculation. Register classes used in the cost calculation
975	are called important classes. They are allocno classes and other
976	non-empty classes whose allocatable hard register sets are inside
977	of an allocno class hard register set. From the first sight, it
978	looks like that they are just allocno classes. It is not true. In
979	example of x86-port in 32-bit mode, allocno classes will contain
980	GENERAL_REGS but not LEGACY_REGS (because allocatable hard
981	registers are the same for the both classes). The important
982	classes will contain GENERAL_REGS and LEGACY_REGS. It is done
983	because a machine description insn constraint may refers for
984	LEGACY_REGS and code in ira-costs.cc is mostly base on investigation
985	of the insn constraints. */
986	static void
987	setup_allocno_and_important_classes (void)
988	{
989	int i, j, n, cl;
990	bool set_p;
991	HARD_REG_SET temp_hard_regset2;
992	static enum reg_class classes[LIM_REG_CLASSES + 1];
993
994	n = 0;
995	/* Collect classes which contain unique sets of allocatable hard
996	registers. Prefer GENERAL_REGS to other classes containing the
997	same set of hard registers. */
998	for (i = 0; i < LIM_REG_CLASSES; i++)
999	{
1000	temp_hard_regset = reg_class_contents[i] & ~no_unit_alloc_regs;
1001	for (j = 0; j < n; j++)
1002	{
1003	cl = classes[j];
1004	temp_hard_regset2 = reg_class_contents[cl] & ~no_unit_alloc_regs;
1005	if (temp_hard_regset == temp_hard_regset2)
1006	break;
1007	}
1008	if (j >= n || targetm.additional_allocno_class_p (i))
1009	classes[n++] = (enum reg_class) i;
1010	else if (i == GENERAL_REGS)
1011	/* Prefer general regs. For i386 example, it means that
1012	we prefer GENERAL_REGS over INDEX_REGS or LEGACY_REGS
1013	(all of them consists of the same available hard
1014	registers). */
1015	classes[j] = (enum reg_class) i;
1016	}
1017	classes[n] = LIM_REG_CLASSES;
1018
1019	/* Set up classes which can be used for allocnos as classes
1020	containing non-empty unique sets of allocatable hard
1021	registers. */
1022	ira_allocno_classes_num = 0;
1023	for (i = 0; (cl = classes[i]) != LIM_REG_CLASSES; i++)
1024	if (ira_class_hard_regs_num[cl] > 0)
1025	ira_allocno_classes[ira_allocno_classes_num++] = (enum reg_class) cl;
1026	ira_important_classes_num = 0;
1027	/* Add non-allocno classes containing to non-empty set of
1028	allocatable hard regs. */
1029	for (cl = 0; cl < N_REG_CLASSES; cl++)
1030	if (ira_class_hard_regs_num[cl] > 0)
1031	{
1032	temp_hard_regset = reg_class_contents[cl] & ~no_unit_alloc_regs;
1033	set_p = false;
1034	for (j = 0; j < ira_allocno_classes_num; j++)
1035	{
1036	temp_hard_regset2 = (reg_class_contents[ira_allocno_classes[j]]
1037	& ~no_unit_alloc_regs);
1038	if ((enum reg_class) cl == ira_allocno_classes[j])
1039	break;
1040	else if (hard_reg_set_subset_p (x: temp_hard_regset,
1041	y: temp_hard_regset2))
1042	set_p = true;
1043	}
1044	if (set_p && j >= ira_allocno_classes_num)
1045	ira_important_classes[ira_important_classes_num++]
1046	= (enum reg_class) cl;
1047	}
1048	/* Now add allocno classes to the important classes. */
1049	for (j = 0; j < ira_allocno_classes_num; j++)
1050	ira_important_classes[ira_important_classes_num++]
1051	= ira_allocno_classes[j];
1052	for (cl = 0; cl < N_REG_CLASSES; cl++)
1053	{
1054	ira_reg_allocno_class_p[cl] = false;
1055	ira_reg_pressure_class_p[cl] = false;
1056	}
1057	for (j = 0; j < ira_allocno_classes_num; j++)
1058	ira_reg_allocno_class_p[ira_allocno_classes[j]] = true;
1059	setup_pressure_classes ();
1060	setup_uniform_class_p ();
1061	}
1062
1063	/* Setup translation in CLASS_TRANSLATE of all classes into a class
1064	given by array CLASSES of length CLASSES_NUM. The function is used
1065	make translation any reg class to an allocno class or to an
1066	pressure class. This translation is necessary for some
1067	calculations when we can use only allocno or pressure classes and
1068	such translation represents an approximate representation of all
1069	classes.
1070
1071	The translation in case when allocatable hard register set of a
1072	given class is subset of allocatable hard register set of a class
1073	in CLASSES is pretty simple. We use smallest classes from CLASSES
1074	containing a given class. If allocatable hard register set of a
1075	given class is not a subset of any corresponding set of a class
1076	from CLASSES, we use the cheapest (with load/store point of view)
1077	class from CLASSES whose set intersects with given class set. */
1078	static void
1079	setup_class_translate_array (enum reg_class *class_translate,
1080	int classes_num, enum reg_class *classes)
1081	{
1082	int cl, mode;
1083	enum reg_class aclass, best_class, *cl_ptr;
1084	int i, cost, min_cost, best_cost;
1085
1086	for (cl = 0; cl < N_REG_CLASSES; cl++)
1087	class_translate[cl] = NO_REGS;
1088
1089	for (i = 0; i < classes_num; i++)
1090	{
1091	aclass = classes[i];
1092	for (cl_ptr = &alloc_reg_class_subclasses[aclass][0];
1093	(cl = *cl_ptr) != LIM_REG_CLASSES;
1094	cl_ptr++)
1095	if (class_translate[cl] == NO_REGS)
1096	class_translate[cl] = aclass;
1097	class_translate[aclass] = aclass;
1098	}
1099	/* For classes which are not fully covered by one of given classes
1100	(in other words covered by more one given class), use the
1101	cheapest class. */
1102	for (cl = 0; cl < N_REG_CLASSES; cl++)
1103	{
1104	if (cl == NO_REGS || class_translate[cl] != NO_REGS)
1105	continue;
1106	best_class = NO_REGS;
1107	best_cost = INT_MAX;
1108	for (i = 0; i < classes_num; i++)
1109	{
1110	aclass = classes[i];
1111	temp_hard_regset = (reg_class_contents[aclass]
1112	& reg_class_contents[cl]
1113	& ~no_unit_alloc_regs);
1114	if (! hard_reg_set_empty_p (x: temp_hard_regset))
1115	{
1116	min_cost = INT_MAX;
1117	for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
1118	{
1119	cost = (ira_memory_move_cost[mode][aclass][0]
1120	+ ira_memory_move_cost[mode][aclass][1]);
1121	if (min_cost > cost)
1122	min_cost = cost;
1123	}
1124	if (best_class == NO_REGS || best_cost > min_cost)
1125	{
1126	best_class = aclass;
1127	best_cost = min_cost;
1128	}
1129	}
1130	}
1131	class_translate[cl] = best_class;
1132	}
1133	}
1134
1135	/* Set up array IRA_ALLOCNO_CLASS_TRANSLATE and
1136	IRA_PRESSURE_CLASS_TRANSLATE. */
1137	static void
1138	setup_class_translate (void)
1139	{
1140	setup_class_translate_array (ira_allocno_class_translate,
1141	ira_allocno_classes_num, ira_allocno_classes);
1142	setup_class_translate_array (ira_pressure_class_translate,
1143	ira_pressure_classes_num, ira_pressure_classes);
1144	}
1145
1146	/* Order numbers of allocno classes in original target allocno class
1147	array, -1 for non-allocno classes. */
1148	static int allocno_class_order[N_REG_CLASSES];
1149
1150	/* The function used to sort the important classes. */
1151	static int
1152	comp_reg_classes_func (const void *v1p, const void *v2p)
1153	{
1154	enum reg_class cl1 = *(const enum reg_class *) v1p;
1155	enum reg_class cl2 = *(const enum reg_class *) v2p;
1156	enum reg_class tcl1, tcl2;
1157	int diff;
1158
1159	tcl1 = ira_allocno_class_translate[cl1];
1160	tcl2 = ira_allocno_class_translate[cl2];
1161	if (tcl1 != NO_REGS && tcl2 != NO_REGS
1162	&& (diff = allocno_class_order[tcl1] - allocno_class_order[tcl2]) != 0)
1163	return diff;
1164	return (int) cl1 - (int) cl2;
1165	}
1166
1167	/* For correct work of function setup_reg_class_relation we need to
1168	reorder important classes according to the order of their allocno
1169	classes. It places important classes containing the same
1170	allocatable hard register set adjacent to each other and allocno
1171	class with the allocatable hard register set right after the other
1172	important classes with the same set.
1173
1174	In example from comments of function
1175	setup_allocno_and_important_classes, it places LEGACY_REGS and
1176	GENERAL_REGS close to each other and GENERAL_REGS is after
1177	LEGACY_REGS. */
1178	static void
1179	reorder_important_classes (void)
1180	{
1181	int i;
1182
1183	for (i = 0; i < N_REG_CLASSES; i++)
1184	allocno_class_order[i] = -1;
1185	for (i = 0; i < ira_allocno_classes_num; i++)
1186	allocno_class_order[ira_allocno_classes[i]] = i;
1187	qsort (ira_important_classes, ira_important_classes_num,
1188	sizeof (enum reg_class), comp_reg_classes_func);
1189	for (i = 0; i < ira_important_classes_num; i++)
1190	ira_important_class_nums[ira_important_classes[i]] = i;
1191	}
1192
1193	/* Set up IRA_REG_CLASS_SUBUNION, IRA_REG_CLASS_SUPERUNION,
1194	IRA_REG_CLASS_SUPER_CLASSES, IRA_REG_CLASSES_INTERSECT, and
1195	IRA_REG_CLASSES_INTERSECT_P. For the meaning of the relations,
1196	please see corresponding comments in ira-int.h. */
1197	static void
1198	setup_reg_class_relations (void)
1199	{
1200	int i, cl1, cl2, cl3;
1201	HARD_REG_SET intersection_set, union_set, temp_set2;
1202	bool important_class_p[N_REG_CLASSES];
1203
1204	memset (s: important_class_p, c: 0, n: sizeof (important_class_p));
1205	for (i = 0; i < ira_important_classes_num; i++)
1206	important_class_p[ira_important_classes[i]] = true;
1207	for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1208	{
1209	ira_reg_class_super_classes[cl1][0] = LIM_REG_CLASSES;
1210	for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1211	{
1212	ira_reg_classes_intersect_p[cl1][cl2] = false;
1213	ira_reg_class_intersect[cl1][cl2] = NO_REGS;
1214	ira_reg_class_subset[cl1][cl2] = NO_REGS;
1215	temp_hard_regset = reg_class_contents[cl1] & ~no_unit_alloc_regs;
1216	temp_set2 = reg_class_contents[cl2] & ~no_unit_alloc_regs;
1217	if (hard_reg_set_empty_p (x: temp_hard_regset)
1218	&& hard_reg_set_empty_p (x: temp_set2))
1219	{
1220	/* The both classes have no allocatable hard registers
1221	-- take all class hard registers into account and use
1222	reg_class_subunion and reg_class_superunion. */
1223	for (i = 0;; i++)
1224	{
1225	cl3 = reg_class_subclasses[cl1][i];
1226	if (cl3 == LIM_REG_CLASSES)
1227	break;
1228	if (reg_class_subset_p (ira_reg_class_intersect[cl1][cl2],
1229	(enum reg_class) cl3))
1230	ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3;
1231	}
1232	ira_reg_class_subunion[cl1][cl2] = reg_class_subunion[cl1][cl2];
1233	ira_reg_class_superunion[cl1][cl2] = reg_class_superunion[cl1][cl2];
1234	continue;
1235	}
1236	ira_reg_classes_intersect_p[cl1][cl2]
1237	= hard_reg_set_intersect_p (x: temp_hard_regset, y: temp_set2);
1238	if (important_class_p[cl1] && important_class_p[cl2]
1239	&& hard_reg_set_subset_p (x: temp_hard_regset, y: temp_set2))
1240	{
1241	/* CL1 and CL2 are important classes and CL1 allocatable
1242	hard register set is inside of CL2 allocatable hard
1243	registers -- make CL1 a superset of CL2. */
1244	enum reg_class *p;
1245
1246	p = &ira_reg_class_super_classes[cl1][0];
1247	while (*p != LIM_REG_CLASSES)
1248	p++;
1249	*p++ = (enum reg_class) cl2;
1250	*p = LIM_REG_CLASSES;
1251	}
1252	ira_reg_class_subunion[cl1][cl2] = NO_REGS;
1253	ira_reg_class_superunion[cl1][cl2] = NO_REGS;
1254	intersection_set = (reg_class_contents[cl1]
1255	& reg_class_contents[cl2]
1256	& ~no_unit_alloc_regs);
1257	union_set = ((reg_class_contents[cl1] | reg_class_contents[cl2])
1258	& ~no_unit_alloc_regs);
1259	for (cl3 = 0; cl3 < N_REG_CLASSES; cl3++)
1260	{
1261	temp_hard_regset = reg_class_contents[cl3] & ~no_unit_alloc_regs;
1262	if (hard_reg_set_empty_p (x: temp_hard_regset))
1263	continue;
1264
1265	if (hard_reg_set_subset_p (x: temp_hard_regset, y: intersection_set))
1266	{
1267	/* CL3 allocatable hard register set is inside of
1268	intersection of allocatable hard register sets
1269	of CL1 and CL2. */
1270	if (important_class_p[cl3])
1271	{
1272	temp_set2
1273	= (reg_class_contents
1274	[ira_reg_class_intersect[cl1][cl2]]);
1275	temp_set2 &= ~no_unit_alloc_regs;
1276	if (! hard_reg_set_subset_p (x: temp_hard_regset, y: temp_set2)
1277	/* If the allocatable hard register sets are
1278	the same, prefer GENERAL_REGS or the
1279	smallest class for debugging
1280	purposes. */
1281	|| (temp_hard_regset == temp_set2
1282	&& (cl3 == GENERAL_REGS
1283	|| ((ira_reg_class_intersect[cl1][cl2]
1284	!= GENERAL_REGS)
1285	&& hard_reg_set_subset_p
1286	(reg_class_contents[cl3],
1287	reg_class_contents
1288	[(int)
1289	ira_reg_class_intersect[cl1][cl2]])))))
1290	ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3;
1291	}
1292	temp_set2
1293	= (reg_class_contents[ira_reg_class_subset[cl1][cl2]]
1294	& ~no_unit_alloc_regs);
1295	if (! hard_reg_set_subset_p (x: temp_hard_regset, y: temp_set2)
1296	/* Ignore unavailable hard registers and prefer
1297	smallest class for debugging purposes. */
1298	|| (temp_hard_regset == temp_set2
1299	&& hard_reg_set_subset_p
1300	(reg_class_contents[cl3],
1301	reg_class_contents
1302	[(int) ira_reg_class_subset[cl1][cl2]])))
1303	ira_reg_class_subset[cl1][cl2] = (enum reg_class) cl3;
1304	}
1305	if (important_class_p[cl3]
1306	&& hard_reg_set_subset_p (x: temp_hard_regset, y: union_set))
1307	{
1308	/* CL3 allocatable hard register set is inside of
1309	union of allocatable hard register sets of CL1
1310	and CL2. */
1311	temp_set2
1312	= (reg_class_contents[ira_reg_class_subunion[cl1][cl2]]
1313	& ~no_unit_alloc_regs);
1314	if (ira_reg_class_subunion[cl1][cl2] == NO_REGS
1315	|| (hard_reg_set_subset_p (x: temp_set2, y: temp_hard_regset)
1316
1317	&& (temp_set2 != temp_hard_regset
1318	|| cl3 == GENERAL_REGS
1319	/* If the allocatable hard register sets are the
1320	same, prefer GENERAL_REGS or the smallest
1321	class for debugging purposes. */
1322	|| (ira_reg_class_subunion[cl1][cl2] != GENERAL_REGS
1323	&& hard_reg_set_subset_p
1324	(reg_class_contents[cl3],
1325	reg_class_contents
1326	[(int) ira_reg_class_subunion[cl1][cl2]])))))
1327	ira_reg_class_subunion[cl1][cl2] = (enum reg_class) cl3;
1328	}
1329	if (hard_reg_set_subset_p (x: union_set, y: temp_hard_regset))
1330	{
1331	/* CL3 allocatable hard register set contains union
1332	of allocatable hard register sets of CL1 and
1333	CL2. */
1334	temp_set2
1335	= (reg_class_contents[ira_reg_class_superunion[cl1][cl2]]
1336	& ~no_unit_alloc_regs);
1337	if (ira_reg_class_superunion[cl1][cl2] == NO_REGS
1338	|| (hard_reg_set_subset_p (x: temp_hard_regset, y: temp_set2)
1339
1340	&& (temp_set2 != temp_hard_regset
1341	|| cl3 == GENERAL_REGS
1342	/* If the allocatable hard register sets are the
1343	same, prefer GENERAL_REGS or the smallest
1344	class for debugging purposes. */
1345	|| (ira_reg_class_superunion[cl1][cl2] != GENERAL_REGS
1346	&& hard_reg_set_subset_p
1347	(reg_class_contents[cl3],
1348	reg_class_contents
1349	[(int) ira_reg_class_superunion[cl1][cl2]])))))
1350	ira_reg_class_superunion[cl1][cl2] = (enum reg_class) cl3;
1351	}
1352	}
1353	}
1354	}
1355	}
1356
1357	/* Output all uniform and important classes into file F. */
1358	static void
1359	print_uniform_and_important_classes (FILE *f)
1360	{
1361	int i, cl;
1362
1363	fprintf (stream: f, format: "Uniform classes:\n");
1364	for (cl = 0; cl < N_REG_CLASSES; cl++)
1365	if (ira_uniform_class_p[cl])
1366	fprintf (stream: f, format: " %s", reg_class_names[cl]);
1367	fprintf (stream: f, format: "\nImportant classes:\n");
1368	for (i = 0; i < ira_important_classes_num; i++)
1369	fprintf (stream: f, format: " %s", reg_class_names[ira_important_classes[i]]);
1370	fprintf (stream: f, format: "\n");
1371	}
1372
1373	/* Output all possible allocno or pressure classes and their
1374	translation map into file F. */
1375	static void
1376	print_translated_classes (FILE *f, bool pressure_p)
1377	{
1378	int classes_num = (pressure_p
1379	? ira_pressure_classes_num : ira_allocno_classes_num);
1380	enum reg_class *classes = (pressure_p
1381	? ira_pressure_classes : ira_allocno_classes);
1382	enum reg_class *class_translate = (pressure_p
1383	? ira_pressure_class_translate
1384	: ira_allocno_class_translate);
1385	int i;
1386
1387	fprintf (stream: f, format: "%s classes:\n", pressure_p ? "Pressure" : "Allocno");
1388	for (i = 0; i < classes_num; i++)
1389	fprintf (stream: f, format: " %s", reg_class_names[classes[i]]);
1390	fprintf (stream: f, format: "\nClass translation:\n");
1391	for (i = 0; i < N_REG_CLASSES; i++)
1392	fprintf (stream: f, format: " %s -> %s\n", reg_class_names[i],
1393	reg_class_names[class_translate[i]]);
1394	}
1395
1396	/* Output all possible allocno and translation classes and the
1397	translation maps into stderr. */
1398	void
1399	ira_debug_allocno_classes (void)
1400	{
1401	print_uniform_and_important_classes (stderr);
1402	print_translated_classes (stderr, pressure_p: false);
1403	print_translated_classes (stderr, pressure_p: true);
1404	}
1405
1406	/* Set up different arrays concerning class subsets, allocno and
1407	important classes. */
1408	static void
1409	find_reg_classes (void)
1410	{
1411	setup_allocno_and_important_classes ();
1412	setup_class_translate ();
1413	reorder_important_classes ();
1414	setup_reg_class_relations ();
1415	}
1416
1417
1418
1419	/* Set up the array above. */
1420	static void
1421	setup_hard_regno_aclass (void)
1422	{
1423	int i;
1424
1425	for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1426	{
1427	#if 1
1428	ira_hard_regno_allocno_class[i]
1429	= (TEST_HARD_REG_BIT (no_unit_alloc_regs, bit: i)
1430	? NO_REGS
1431	: ira_allocno_class_translate[REGNO_REG_CLASS (i)]);
1432	#else
1433	int j;
1434	enum reg_class cl;
1435	ira_hard_regno_allocno_class[i] = NO_REGS;
1436	for (j = 0; j < ira_allocno_classes_num; j++)
1437	{
1438	cl = ira_allocno_classes[j];
1439	if (ira_class_hard_reg_index[cl][i] >= 0)
1440	{
1441	ira_hard_regno_allocno_class[i] = cl;
1442	break;
1443	}
1444	}
1445	#endif
1446	}
1447	}
1448
1449
1450
1451	/* Form IRA_REG_CLASS_MAX_NREGS and IRA_REG_CLASS_MIN_NREGS maps. */
1452	static void
1453	setup_reg_class_nregs (void)
1454	{
1455	int i, cl, cl2, m;
1456
1457	for (m = 0; m < MAX_MACHINE_MODE; m++)
1458	{
1459	for (cl = 0; cl < N_REG_CLASSES; cl++)
1460	ira_reg_class_max_nregs[cl][m]
1461	= ira_reg_class_min_nregs[cl][m]
1462	= targetm.class_max_nregs ((reg_class_t) cl, (machine_mode) m);
1463	for (cl = 0; cl < N_REG_CLASSES; cl++)
1464	for (i = 0;
1465	(cl2 = alloc_reg_class_subclasses[cl][i]) != LIM_REG_CLASSES;
1466	i++)
1467	if (ira_reg_class_min_nregs[cl2][m]
1468	< ira_reg_class_min_nregs[cl][m])
1469	ira_reg_class_min_nregs[cl][m] = ira_reg_class_min_nregs[cl2][m];
1470	}
1471	}
1472
1473
1474
1475	/* Set up IRA_PROHIBITED_CLASS_MODE_REGS, IRA_EXCLUDE_CLASS_MODE_REGS, and
1476	IRA_CLASS_SINGLETON. This function is called once IRA_CLASS_HARD_REGS has
1477	been initialized. */
1478	static void
1479	setup_prohibited_and_exclude_class_mode_regs (void)
1480	{
1481	int j, k, hard_regno, cl, last_hard_regno, count;
1482
1483	for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
1484	{
1485	temp_hard_regset = reg_class_contents[cl] & ~no_unit_alloc_regs;
1486	for (j = 0; j < NUM_MACHINE_MODES; j++)
1487	{
1488	count = 0;
1489	last_hard_regno = -1;
1490	CLEAR_HARD_REG_SET (ira_prohibited_class_mode_regs[cl][j]);
1491	CLEAR_HARD_REG_SET (ira_exclude_class_mode_regs[cl][j]);
1492	for (k = ira_class_hard_regs_num[cl] - 1; k >= 0; k--)
1493	{
1494	hard_regno = ira_class_hard_regs[cl][k];
1495	if (!targetm.hard_regno_mode_ok (hard_regno, (machine_mode) j))
1496	SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1497	bit: hard_regno);
1498	else if (in_hard_reg_set_p (regs: temp_hard_regset,
1499	mode: (machine_mode) j, regno: hard_regno))
1500	{
1501	last_hard_regno = hard_regno;
1502	count++;
1503	}
1504	else
1505	{
1506	SET_HARD_REG_BIT (ira_exclude_class_mode_regs[cl][j], bit: hard_regno);
1507	}
1508	}
1509	ira_class_singleton[cl][j] = (count == 1 ? last_hard_regno : -1);
1510	}
1511	}
1512	}
1513
1514	/* Clarify IRA_PROHIBITED_CLASS_MODE_REGS by excluding hard registers
1515	spanning from one register pressure class to another one. It is
1516	called after defining the pressure classes. */
1517	static void
1518	clarify_prohibited_class_mode_regs (void)
1519	{
1520	int j, k, hard_regno, cl, pclass, nregs;
1521
1522	for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
1523	for (j = 0; j < NUM_MACHINE_MODES; j++)
1524	{
1525	CLEAR_HARD_REG_SET (ira_useful_class_mode_regs[cl][j]);
1526	for (k = ira_class_hard_regs_num[cl] - 1; k >= 0; k--)
1527	{
1528	hard_regno = ira_class_hard_regs[cl][k];
1529	if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j], bit: hard_regno))
1530	continue;
1531	nregs = hard_regno_nregs (regno: hard_regno, mode: (machine_mode) j);
1532	if (hard_regno + nregs > FIRST_PSEUDO_REGISTER)
1533	{
1534	SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1535	bit: hard_regno);
1536	continue;
1537	}
1538	pclass = ira_pressure_class_translate[REGNO_REG_CLASS (hard_regno)];
1539	for (nregs-- ;nregs >= 0; nregs--)
1540	if (((enum reg_class) pclass
1541	!= ira_pressure_class_translate[REGNO_REG_CLASS
1542	(hard_regno + nregs)]))
1543	{
1544	SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1545	bit: hard_regno);
1546	break;
1547	}
1548	if (!TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1549	bit: hard_regno))
1550	add_to_hard_reg_set (regs: &ira_useful_class_mode_regs[cl][j],
1551	mode: (machine_mode) j, regno: hard_regno);
1552	}
1553	}
1554	}
1555
1556	/* Allocate and initialize IRA_REGISTER_MOVE_COST, IRA_MAY_MOVE_IN_COST
1557	and IRA_MAY_MOVE_OUT_COST for MODE. */
1558	void
1559	ira_init_register_move_cost (machine_mode mode)
1560	{
1561	static unsigned short last_move_cost[N_REG_CLASSES][N_REG_CLASSES];
1562	bool all_match = true;
1563	unsigned int i, cl1, cl2;
1564	HARD_REG_SET ok_regs;
1565
1566	ira_assert (ira_register_move_cost[mode] == NULL
1567	&& ira_may_move_in_cost[mode] == NULL
1568	&& ira_may_move_out_cost[mode] == NULL);
1569	CLEAR_HARD_REG_SET (set&: ok_regs);
1570	for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1571	if (targetm.hard_regno_mode_ok (i, mode))
1572	SET_HARD_REG_BIT (set&: ok_regs, bit: i);
1573
1574	/* Note that we might be asked about the move costs of modes that
1575	cannot be stored in any hard register, for example if an inline
1576	asm tries to create a register operand with an impossible mode.
1577	We therefore can't assert have_regs_of_mode[mode] here. */
1578	for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1579	for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1580	{
1581	int cost;
1582	if (!hard_reg_set_intersect_p (x: ok_regs, reg_class_contents[cl1])
1583	|| !hard_reg_set_intersect_p (x: ok_regs, reg_class_contents[cl2]))
1584	{
1585	if ((ira_reg_class_max_nregs[cl1][mode]
1586	> ira_class_hard_regs_num[cl1])
1587	|| (ira_reg_class_max_nregs[cl2][mode]
1588	> ira_class_hard_regs_num[cl2]))
1589	cost = 65535;
1590	else
1591	cost = (ira_memory_move_cost[mode][cl1][0]
1592	+ ira_memory_move_cost[mode][cl2][1]) * 2;
1593	}
1594	else
1595	{
1596	cost = register_move_cost (mode, (enum reg_class) cl1,
1597	(enum reg_class) cl2);
1598	ira_assert (cost < 65535);
1599	}
1600	all_match &= (last_move_cost[cl1][cl2] == cost);
1601	last_move_cost[cl1][cl2] = cost;
1602	}
1603	if (all_match && last_mode_for_init_move_cost != -1)
1604	{
1605	ira_register_move_cost[mode]
1606	= ira_register_move_cost[last_mode_for_init_move_cost];
1607	ira_may_move_in_cost[mode]
1608	= ira_may_move_in_cost[last_mode_for_init_move_cost];
1609	ira_may_move_out_cost[mode]
1610	= ira_may_move_out_cost[last_mode_for_init_move_cost];
1611	return;
1612	}
1613	last_mode_for_init_move_cost = mode;
1614	ira_register_move_cost[mode] = XNEWVEC (move_table, N_REG_CLASSES);
1615	ira_may_move_in_cost[mode] = XNEWVEC (move_table, N_REG_CLASSES);
1616	ira_may_move_out_cost[mode] = XNEWVEC (move_table, N_REG_CLASSES);
1617	for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1618	for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1619	{
1620	int cost;
1621	enum reg_class *p1, *p2;
1622
1623	if (last_move_cost[cl1][cl2] == 65535)
1624	{
1625	ira_register_move_cost[mode][cl1][cl2] = 65535;
1626	ira_may_move_in_cost[mode][cl1][cl2] = 65535;
1627	ira_may_move_out_cost[mode][cl1][cl2] = 65535;
1628	}
1629	else
1630	{
1631	cost = last_move_cost[cl1][cl2];
1632
1633	for (p2 = &reg_class_subclasses[cl2][0];
1634	*p2 != LIM_REG_CLASSES; p2++)
1635	if (ira_class_hard_regs_num[*p2] > 0
1636	&& (ira_reg_class_max_nregs[*p2][mode]
1637	<= ira_class_hard_regs_num[*p2]))
1638	cost = MAX (cost, ira_register_move_cost[mode][cl1][*p2]);
1639
1640	for (p1 = &reg_class_subclasses[cl1][0];
1641	*p1 != LIM_REG_CLASSES; p1++)
1642	if (ira_class_hard_regs_num[*p1] > 0
1643	&& (ira_reg_class_max_nregs[*p1][mode]
1644	<= ira_class_hard_regs_num[*p1]))
1645	cost = MAX (cost, ira_register_move_cost[mode][*p1][cl2]);
1646
1647	ira_assert (cost <= 65535);
1648	ira_register_move_cost[mode][cl1][cl2] = cost;
1649
1650	if (ira_class_subset_p[cl1][cl2])
1651	ira_may_move_in_cost[mode][cl1][cl2] = 0;
1652	else
1653	ira_may_move_in_cost[mode][cl1][cl2] = cost;
1654
1655	if (ira_class_subset_p[cl2][cl1])
1656	ira_may_move_out_cost[mode][cl1][cl2] = 0;
1657	else
1658	ira_may_move_out_cost[mode][cl1][cl2] = cost;
1659	}
1660	}
1661	}
1662
1663
1664
1665	/* This is called once during compiler work. It sets up
1666	different arrays whose values don't depend on the compiled
1667	function. */
1668	void
1669	ira_init_once (void)
1670	{
1671	ira_init_costs_once ();
1672	lra_init_once ();
1673
1674	ira_use_lra_p = targetm.lra_p ();
1675	}
1676
1677	/* Free ira_max_register_move_cost, ira_may_move_in_cost and
1678	ira_may_move_out_cost for each mode. */
1679	void
1680	target_ira_int::free_register_move_costs (void)
1681	{
1682	int mode, i;
1683
1684	/* Reset move_cost and friends, making sure we only free shared
1685	table entries once. */
1686	for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
1687	if (x_ira_register_move_cost[mode])
1688	{
1689	for (i = 0;
1690	i < mode && (x_ira_register_move_cost[i]
1691	!= x_ira_register_move_cost[mode]);
1692	i++)
1693	;
1694	if (i == mode)
1695	{
1696	free (ptr: x_ira_register_move_cost[mode]);
1697	free (ptr: x_ira_may_move_in_cost[mode]);
1698	free (ptr: x_ira_may_move_out_cost[mode]);
1699	}
1700	}
1701	memset (s: x_ira_register_move_cost, c: 0, n: sizeof x_ira_register_move_cost);
1702	memset (s: x_ira_may_move_in_cost, c: 0, n: sizeof x_ira_may_move_in_cost);
1703	memset (s: x_ira_may_move_out_cost, c: 0, n: sizeof x_ira_may_move_out_cost);
1704	last_mode_for_init_move_cost = -1;
1705	}
1706
1707	target_ira_int::~target_ira_int ()
1708	{
1709	free_ira_costs ();
1710	free_register_move_costs ();
1711	}
1712
1713	/* This is called every time when register related information is
1714	changed. */
1715	void
1716	ira_init (void)
1717	{
1718	this_target_ira_int->free_register_move_costs ();
1719	setup_reg_mode_hard_regset ();
1720	setup_alloc_regs (flag_omit_frame_pointer != 0);
1721	setup_class_subset_and_memory_move_costs ();
1722	setup_reg_class_nregs ();
1723	setup_prohibited_and_exclude_class_mode_regs ();
1724	find_reg_classes ();
1725	clarify_prohibited_class_mode_regs ();
1726	setup_hard_regno_aclass ();
1727	ira_init_costs ();
1728	}
1729
1730
1731	#define ira_prohibited_mode_move_regs_initialized_p \
1732	(this_target_ira_int->x_ira_prohibited_mode_move_regs_initialized_p)
1733
1734	/* Set up IRA_PROHIBITED_MODE_MOVE_REGS. */
1735	static void
1736	setup_prohibited_mode_move_regs (void)
1737	{
1738	int i, j;
1739	rtx test_reg1, test_reg2, move_pat;
1740	rtx_insn *move_insn;
1741
1742	if (ira_prohibited_mode_move_regs_initialized_p)
1743	return;
1744	ira_prohibited_mode_move_regs_initialized_p = true;
1745	test_reg1 = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1);
1746	test_reg2 = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 2);
1747	move_pat = gen_rtx_SET (test_reg1, test_reg2);
1748	move_insn = gen_rtx_INSN (VOIDmode, prev_insn: 0, next_insn: 0, bb: 0, pattern: move_pat, location: 0, code: -1, reg_notes: 0);
1749	for (i = 0; i < NUM_MACHINE_MODES; i++)
1750	{
1751	SET_HARD_REG_SET (ira_prohibited_mode_move_regs[i]);
1752	for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1753	{
1754	if (!targetm.hard_regno_mode_ok (j, (machine_mode) i))
1755	continue;
1756	set_mode_and_regno (test_reg1, (machine_mode) i, j);
1757	set_mode_and_regno (test_reg2, (machine_mode) i, j);
1758	INSN_CODE (move_insn) = -1;
1759	recog_memoized (insn: move_insn);
1760	if (INSN_CODE (move_insn) < 0)
1761	continue;
1762	extract_insn (move_insn);
1763	/* We don't know whether the move will be in code that is optimized
1764	for size or speed, so consider all enabled alternatives. */
1765	if (! constrain_operands (1, get_enabled_alternatives (move_insn)))
1766	continue;
1767	CLEAR_HARD_REG_BIT (ira_prohibited_mode_move_regs[i], bit: j);
1768	}
1769	}
1770	}
1771
1772
1773
1774	/* Extract INSN and return the set of alternatives that we should consider.
1775	This excludes any alternatives whose constraints are obviously impossible
1776	to meet (e.g. because the constraint requires a constant and the operand
1777	is nonconstant). It also excludes alternatives that are bound to need
1778	a spill or reload, as long as we have other alternatives that match
1779	exactly. */
1780	alternative_mask
1781	ira_setup_alts (rtx_insn *insn)
1782	{
1783	int nop, nalt;
1784	bool curr_swapped;
1785	const char *p;
1786	int commutative = -1;
1787
1788	extract_insn (insn);
1789	preprocess_constraints (insn);
1790	alternative_mask preferred = get_preferred_alternatives (insn);
1791	alternative_mask alts = 0;
1792	alternative_mask exact_alts = 0;
1793	/* Check that the hard reg set is enough for holding all
1794	alternatives. It is hard to imagine the situation when the
1795	assertion is wrong. */
1796	ira_assert (recog_data.n_alternatives
1797	<= (int) MAX (sizeof (HARD_REG_ELT_TYPE) * CHAR_BIT,
1798	FIRST_PSEUDO_REGISTER));
1799	for (nop = 0; nop < recog_data.n_operands; nop++)
1800	if (recog_data.constraints[nop][0] == '%')
1801	{
1802	commutative = nop;
1803	break;
1804	}
1805	for (curr_swapped = false;; curr_swapped = true)
1806	{
1807	for (nalt = 0; nalt < recog_data.n_alternatives; nalt++)
1808	{
1809	if (!TEST_BIT (preferred, nalt) || TEST_BIT (exact_alts, nalt))
1810	continue;
1811
1812	const operand_alternative *op_alt
1813	= &recog_op_alt[nalt * recog_data.n_operands];
1814	int this_reject = 0;
1815	for (nop = 0; nop < recog_data.n_operands; nop++)
1816	{
1817	int c, len;
1818
1819	this_reject += op_alt[nop].reject;
1820
1821	rtx op = recog_data.operand[nop];
1822	p = op_alt[nop].constraint;
1823	if (*p == 0 || *p == ',')
1824	continue;
1825
1826	bool win_p = false;
1827	do
1828	switch (c = *p, len = CONSTRAINT_LEN (c, p), c)
1829	{
1830	case '#':
1831	case ',':
1832	c = '\0';
1833	/* FALLTHRU */
1834	case '\0':
1835	len = 0;
1836	break;
1837
1838	case '%':
1839	/* The commutative modifier is handled above. */
1840	break;
1841
1842	case '0': case '1': case '2': case '3': case '4':
1843	case '5': case '6': case '7': case '8': case '9':
1844	{
1845	char *end;
1846	unsigned long dup = strtoul (nptr: p, endptr: &end, base: 10);
1847	rtx other = recog_data.operand[dup];
1848	len = end - p;
1849	if (MEM_P (other)
1850	? rtx_equal_p (other, op)
1851	: REG_P (op) || SUBREG_P (op))
1852	goto op_success;
1853	win_p = true;
1854	}
1855	break;
1856
1857	case 'g':
1858	goto op_success;
1859	break;
1860
1861	default:
1862	{
1863	enum constraint_num cn = lookup_constraint (p);
1864	rtx mem = NULL;
1865	switch (get_constraint_type (c: cn))
1866	{
1867	case CT_REGISTER:
1868	if (reg_class_for_constraint (c: cn) != NO_REGS)
1869	{
1870	if (REG_P (op) || SUBREG_P (op))
1871	goto op_success;
1872	win_p = true;
1873	}
1874	break;
1875
1876	case CT_CONST_INT:
1877	if (CONST_INT_P (op)
1878	&& (insn_const_int_ok_for_constraint
1879	(INTVAL (op), cn)))
1880	goto op_success;
1881	break;
1882
1883	case CT_ADDRESS:
1884	goto op_success;
1885
1886	case CT_MEMORY:
1887	case CT_RELAXED_MEMORY:
1888	mem = op;
1889	/* Fall through. */
1890	case CT_SPECIAL_MEMORY:
1891	if (!mem)
1892	mem = extract_mem_from_operand (op);
1893	if (MEM_P (mem))
1894	goto op_success;
1895	win_p = true;
1896	break;
1897
1898	case CT_FIXED_FORM:
1899	if (constraint_satisfied_p (x: op, c: cn))
1900	goto op_success;
1901	break;
1902	}
1903	break;
1904	}
1905	}
1906	while (p += len, c);
1907	if (!win_p)
1908	break;
1909	/* We can make the alternative match by spilling a register
1910	to memory or loading something into a register. Count a
1911	cost of one reload (the equivalent of the '?' constraint). */
1912	this_reject += 6;
1913	op_success:
1914	;
1915	}
1916
1917	if (nop >= recog_data.n_operands)
1918	{
1919	alts |= ALTERNATIVE_BIT (nalt);
1920	if (this_reject == 0)
1921	exact_alts |= ALTERNATIVE_BIT (nalt);
1922	}
1923	}
1924	if (commutative < 0)
1925	break;
1926	/* Swap forth and back to avoid changing recog_data. */
1927	std::swap (a&: recog_data.operand[commutative],
1928	b&: recog_data.operand[commutative + 1]);
1929	if (curr_swapped)
1930	break;
1931	}
1932	return exact_alts ? exact_alts : alts;
1933	}
1934
1935	/* Return the number of the output non-early clobber operand which
1936	should be the same in any case as operand with number OP_NUM (or
1937	negative value if there is no such operand). ALTS is the mask
1938	of alternatives that we should consider. SINGLE_INPUT_OP_HAS_CSTR_P
1939	should be set in this function, it indicates whether there is only
1940	a single input operand which has the matching constraint on the
1941	output operand at the position specified in return value. If the
1942	pattern allows any one of several input operands holds the matching
1943	constraint, it's set as false, one typical case is destructive FMA
1944	instruction on target rs6000. Note that for a non-NO_REG preferred
1945	register class with no free register move copy, if the parameter
1946	PARAM_IRA_CONSIDER_DUP_IN_ALL_ALTS is set to one, this function
1947	will check all available alternatives for matching constraints,
1948	even if it has found or will find one alternative with non-NO_REG
1949	regclass, it can respect more cases with matching constraints. If
1950	PARAM_IRA_CONSIDER_DUP_IN_ALL_ALTS is set to zero,
1951	SINGLE_INPUT_OP_HAS_CSTR_P is always true, it will stop to find
1952	matching constraint relationship once it hits some alternative with
1953	some non-NO_REG regclass. */
1954	int
1955	ira_get_dup_out_num (int op_num, alternative_mask alts,
1956	bool &single_input_op_has_cstr_p)
1957	{
1958	int curr_alt, c, original;
1959	bool ignore_p, use_commut_op_p;
1960	const char *str;
1961
1962	if (op_num < 0 || recog_data.n_alternatives == 0)
1963	return -1;
1964	/* We should find duplications only for input operands. */
1965	if (recog_data.operand_type[op_num] != OP_IN)
1966	return -1;
1967	str = recog_data.constraints[op_num];
1968	use_commut_op_p = false;
1969	single_input_op_has_cstr_p = true;
1970
1971	rtx op = recog_data.operand[op_num];
1972	int op_regno = reg_or_subregno (op);
1973	enum reg_class op_pref_cl = reg_preferred_class (op_regno);
1974	machine_mode op_mode = GET_MODE (op);
1975
1976	ira_init_register_move_cost_if_necessary (mode: op_mode);
1977	/* If the preferred regclass isn't NO_REG, continue to find the matching
1978	constraint in all available alternatives with preferred regclass, even
1979	if we have found or will find one alternative whose constraint stands
1980	for a REG (non-NO_REG) regclass. Note that it would be fine not to
1981	respect matching constraint if the register copy is free, so exclude
1982	it. */
1983	bool respect_dup_despite_reg_cstr
1984	= param_ira_consider_dup_in_all_alts
1985	&& op_pref_cl != NO_REGS
1986	&& ira_register_move_cost[op_mode][op_pref_cl][op_pref_cl] > 0;
1987
1988	/* Record the alternative whose constraint uses the same regclass as the
1989	preferred regclass, later if we find one matching constraint for this
1990	operand with preferred reclass, we will visit these recorded
1991	alternatives to check whether if there is one alternative in which no
1992	any INPUT operands have one matching constraint same as our candidate.
1993	If yes, it means there is one alternative which is perfectly fine
1994	without satisfying this matching constraint. If no, it means in any
1995	alternatives there is one other INPUT operand holding this matching
1996	constraint, it's fine to respect this matching constraint and further
1997	create this constraint copy since it would become harmless once some
1998	other takes preference and it's interfered. */
1999	alternative_mask pref_cl_alts;
2000
2001	for (;;)
2002	{
2003	pref_cl_alts = 0;
2004
2005	for (curr_alt = 0, ignore_p = !TEST_BIT (alts, curr_alt),
2006	original = -1;;)
2007	{
2008	c = *str;
2009	if (c == '\0')
2010	break;
2011	if (c == '#')
2012	ignore_p = true;
2013	else if (c == ',')
2014	{
2015	curr_alt++;
2016	ignore_p = !TEST_BIT (alts, curr_alt);
2017	}
2018	else if (! ignore_p)
2019	switch (c)
2020	{
2021	case 'g':
2022	goto fail;
2023	default:
2024	{
2025	enum constraint_num cn = lookup_constraint (p: str);
2026	enum reg_class cl = reg_class_for_constraint (c: cn);
2027	if (cl != NO_REGS && !targetm.class_likely_spilled_p (cl))
2028	{
2029	if (respect_dup_despite_reg_cstr)
2030	{
2031	/* If it's free to move from one preferred class to
2032	the one without matching constraint, it doesn't
2033	have to respect this constraint with costs. */
2034	if (cl != op_pref_cl
2035	&& (ira_reg_class_intersect[cl][op_pref_cl]
2036	!= NO_REGS)
2037	&& (ira_may_move_in_cost[op_mode][op_pref_cl][cl]
2038	== 0))
2039	goto fail;
2040	else if (cl == op_pref_cl)
2041	pref_cl_alts |= ALTERNATIVE_BIT (curr_alt);
2042	}
2043	else
2044	goto fail;
2045	}
2046	if (constraint_satisfied_p (x: op, c: cn))
2047	goto fail;
2048	break;
2049	}
2050
2051	case '0': case '1': case '2': case '3': case '4':
2052	case '5': case '6': case '7': case '8': case '9':
2053	{
2054	char *end;
2055	int n = (int) strtoul (nptr: str, endptr: &end, base: 10);
2056	str = end;
2057	if (original != -1 && original != n)
2058	goto fail;
2059	gcc_assert (n < recog_data.n_operands);
2060	if (respect_dup_despite_reg_cstr)
2061	{
2062	const operand_alternative *op_alt
2063	= &recog_op_alt[curr_alt * recog_data.n_operands];
2064	/* Only respect the one with preferred rclass, without
2065	respect_dup_despite_reg_cstr it's possible to get
2066	one whose regclass isn't preferred first before,
2067	but it would fail since there should be other
2068	alternatives with preferred regclass. */
2069	if (op_alt[n].cl == op_pref_cl)
2070	original = n;
2071	}
2072	else
2073	original = n;
2074	continue;
2075	}
2076	}
2077	str += CONSTRAINT_LEN (c, str);
2078	}
2079	if (original == -1)
2080	goto fail;
2081	if (recog_data.operand_type[original] == OP_OUT)
2082	{
2083	if (pref_cl_alts == 0)
2084	return original;
2085	/* Visit these recorded alternatives to check whether
2086	there is one alternative in which no any INPUT operands
2087	have one matching constraint same as our candidate.
2088	Give up this candidate if so. */
2089	int nop, nalt;
2090	for (nalt = 0; nalt < recog_data.n_alternatives; nalt++)
2091	{
2092	if (!TEST_BIT (pref_cl_alts, nalt))
2093	continue;
2094	const operand_alternative *op_alt
2095	= &recog_op_alt[nalt * recog_data.n_operands];
2096	bool dup_in_other = false;
2097	for (nop = 0; nop < recog_data.n_operands; nop++)
2098	{
2099	if (recog_data.operand_type[nop] != OP_IN)
2100	continue;
2101	if (nop == op_num)
2102	continue;
2103	if (op_alt[nop].matches == original)
2104	{
2105	dup_in_other = true;
2106	break;
2107	}
2108	}
2109	if (!dup_in_other)
2110	return -1;
2111	}
2112	single_input_op_has_cstr_p = false;
2113	return original;
2114	}
2115	fail:
2116	if (use_commut_op_p)
2117	break;
2118	use_commut_op_p = true;
2119	if (recog_data.constraints[op_num][0] == '%')
2120	str = recog_data.constraints[op_num + 1];
2121	else if (op_num > 0 && recog_data.constraints[op_num - 1][0] == '%')
2122	str = recog_data.constraints[op_num - 1];
2123	else
2124	break;
2125	}
2126	return -1;
2127	}
2128
2129
2130
2131	/* Search forward to see if the source register of a copy insn dies
2132	before either it or the destination register is modified, but don't
2133	scan past the end of the basic block. If so, we can replace the
2134	source with the destination and let the source die in the copy
2135	insn.
2136
2137	This will reduce the number of registers live in that range and may
2138	enable the destination and the source coalescing, thus often saving
2139	one register in addition to a register-register copy. */
2140
2141	static void
2142	decrease_live_ranges_number (void)
2143	{
2144	basic_block bb;
2145	rtx_insn *insn;
2146	rtx set, src, dest, dest_death, note;
2147	rtx_insn *p, *q;
2148	int sregno, dregno;
2149
2150	if (! flag_expensive_optimizations)
2151	return;
2152
2153	if (ira_dump_file)
2154	fprintf (stream: ira_dump_file, format: "Starting decreasing number of live ranges...\n");
2155
2156	FOR_EACH_BB_FN (bb, cfun)
2157	FOR_BB_INSNS (bb, insn)
2158	{
2159	set = single_set (insn);
2160	if (! set)
2161	continue;
2162	src = SET_SRC (set);
2163	dest = SET_DEST (set);
2164	if (! REG_P (src) || ! REG_P (dest)
2165	|| find_reg_note (insn, REG_DEAD, src))
2166	continue;
2167	sregno = REGNO (src);
2168	dregno = REGNO (dest);
2169
2170	/* We don't want to mess with hard regs if register classes
2171	are small. */
2172	if (sregno == dregno
2173	|| (targetm.small_register_classes_for_mode_p (GET_MODE (src))
2174	&& (sregno < FIRST_PSEUDO_REGISTER
2175	|| dregno < FIRST_PSEUDO_REGISTER))
2176	/* We don't see all updates to SP if they are in an
2177	auto-inc memory reference, so we must disallow this
2178	optimization on them. */
2179	|| sregno == STACK_POINTER_REGNUM
2180	|| dregno == STACK_POINTER_REGNUM)
2181	continue;
2182
2183	dest_death = NULL_RTX;
2184
2185	for (p = NEXT_INSN (insn); p; p = NEXT_INSN (insn: p))
2186	{
2187	if (! INSN_P (p))
2188	continue;
2189	if (BLOCK_FOR_INSN (insn: p) != bb)
2190	break;
2191
2192	if (reg_set_p (src, p) || reg_set_p (dest, p)
2193	/* If SRC is an asm-declared register, it must not be
2194	replaced in any asm. Unfortunately, the REG_EXPR
2195	tree for the asm variable may be absent in the SRC
2196	rtx, so we can't check the actual register
2197	declaration easily (the asm operand will have it,
2198	though). To avoid complicating the test for a rare
2199	case, we just don't perform register replacement
2200	for a hard reg mentioned in an asm. */
2201	|| (sregno < FIRST_PSEUDO_REGISTER
2202	&& asm_noperands (PATTERN (insn: p)) >= 0
2203	&& reg_overlap_mentioned_p (src, PATTERN (insn: p)))
2204	/* Don't change hard registers used by a call. */
2205	|| (CALL_P (p) && sregno < FIRST_PSEUDO_REGISTER
2206	&& find_reg_fusage (p, USE, src))
2207	/* Don't change a USE of a register. */
2208	|| (GET_CODE (PATTERN (p)) == USE
2209	&& reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
2210	break;
2211
2212	/* See if all of SRC dies in P. This test is slightly
2213	more conservative than it needs to be. */
2214	if ((note = find_regno_note (p, REG_DEAD, sregno))
2215	&& GET_MODE (XEXP (note, 0)) == GET_MODE (src))
2216	{
2217	int failed = 0;
2218
2219	/* We can do the optimization. Scan forward from INSN
2220	again, replacing regs as we go. Set FAILED if a
2221	replacement can't be done. In that case, we can't
2222	move the death note for SRC. This should be
2223	rare. */
2224
2225	/* Set to stop at next insn. */
2226	for (q = next_real_insn (insn);
2227	q != next_real_insn (p);
2228	q = next_real_insn (q))
2229	{
2230	if (reg_overlap_mentioned_p (src, PATTERN (insn: q)))
2231	{
2232	/* If SRC is a hard register, we might miss
2233	some overlapping registers with
2234	validate_replace_rtx, so we would have to
2235	undo it. We can't if DEST is present in
2236	the insn, so fail in that combination of
2237	cases. */
2238	if (sregno < FIRST_PSEUDO_REGISTER
2239	&& reg_mentioned_p (dest, PATTERN (insn: q)))
2240	failed = 1;
2241
2242	/* Attempt to replace all uses. */
2243	else if (!validate_replace_rtx (src, dest, q))
2244	failed = 1;
2245
2246	/* If this succeeded, but some part of the
2247	register is still present, undo the
2248	replacement. */
2249	else if (sregno < FIRST_PSEUDO_REGISTER
2250	&& reg_overlap_mentioned_p (src, PATTERN (insn: q)))
2251	{
2252	validate_replace_rtx (dest, src, q);
2253	failed = 1;
2254	}
2255	}
2256
2257	/* If DEST dies here, remove the death note and
2258	save it for later. Make sure ALL of DEST dies
2259	here; again, this is overly conservative. */
2260	if (! dest_death
2261	&& (dest_death = find_regno_note (q, REG_DEAD, dregno)))
2262	{
2263	if (GET_MODE (XEXP (dest_death, 0)) == GET_MODE (dest))
2264	remove_note (q, dest_death);
2265	else
2266	{
2267	failed = 1;
2268	dest_death = 0;
2269	}
2270	}
2271	}
2272
2273	if (! failed)
2274	{
2275	/* Move death note of SRC from P to INSN. */
2276	remove_note (p, note);
2277	XEXP (note, 1) = REG_NOTES (insn);
2278	REG_NOTES (insn) = note;
2279	}
2280
2281	/* DEST is also dead if INSN has a REG_UNUSED note for
2282	DEST. */
2283	if (! dest_death
2284	&& (dest_death
2285	= find_regno_note (insn, REG_UNUSED, dregno)))
2286	{
2287	PUT_REG_NOTE_KIND (dest_death, REG_DEAD);
2288	remove_note (insn, dest_death);
2289	}
2290
2291	/* Put death note of DEST on P if we saw it die. */
2292	if (dest_death)
2293	{
2294	XEXP (dest_death, 1) = REG_NOTES (p);
2295	REG_NOTES (p) = dest_death;
2296	}
2297	break;
2298	}
2299
2300	/* If SRC is a hard register which is set or killed in
2301	some other way, we can't do this optimization. */
2302	else if (sregno < FIRST_PSEUDO_REGISTER && dead_or_set_p (p, src))
2303	break;
2304	}
2305	}
2306	}
2307
2308
2309
2310	/* Return nonzero if REGNO is a particularly bad choice for reloading X. */
2311	static bool
2312	ira_bad_reload_regno_1 (int regno, rtx x)
2313	{
2314	int x_regno, n, i;
2315	ira_allocno_t a;
2316	enum reg_class pref;
2317
2318	/* We only deal with pseudo regs. */
2319	if (! x || GET_CODE (x) != REG)
2320	return false;
2321
2322	x_regno = REGNO (x);
2323	if (x_regno < FIRST_PSEUDO_REGISTER)
2324	return false;
2325
2326	/* If the pseudo prefers REGNO explicitly, then do not consider
2327	REGNO a bad spill choice. */
2328	pref = reg_preferred_class (x_regno);
2329	if (reg_class_size[pref] == 1)
2330	return !TEST_HARD_REG_BIT (reg_class_contents[pref], bit: regno);
2331
2332	/* If the pseudo conflicts with REGNO, then we consider REGNO a
2333	poor choice for a reload regno. */
2334	a = ira_regno_allocno_map[x_regno];
2335	n = ALLOCNO_NUM_OBJECTS (a);
2336	for (i = 0; i < n; i++)
2337	{
2338	ira_object_t obj = ALLOCNO_OBJECT (a, i);
2339	if (TEST_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), bit: regno))
2340	return true;
2341	}
2342	return false;
2343	}
2344
2345	/* Return nonzero if REGNO is a particularly bad choice for reloading
2346	IN or OUT. */
2347	bool
2348	ira_bad_reload_regno (int regno, rtx in, rtx out)
2349	{
2350	return (ira_bad_reload_regno_1 (regno, x: in)
2351	|| ira_bad_reload_regno_1 (regno, x: out));
2352	}
2353
2354	/* Add register clobbers from asm statements. */
2355	static void
2356	compute_regs_asm_clobbered (void)
2357	{
2358	basic_block bb;
2359
2360	FOR_EACH_BB_FN (bb, cfun)
2361	{
2362	rtx_insn *insn;
2363	FOR_BB_INSNS_REVERSE (bb, insn)
2364	{
2365	df_ref def;
2366
2367	if (NONDEBUG_INSN_P (insn) && asm_noperands (PATTERN (insn)) >= 0)
2368	FOR_EACH_INSN_DEF (def, insn)
2369	{
2370	unsigned int dregno = DF_REF_REGNO (def);
2371	if (HARD_REGISTER_NUM_P (dregno))
2372	add_to_hard_reg_set (regs: &crtl->asm_clobbers,
2373	GET_MODE (DF_REF_REAL_REG (def)),
2374	regno: dregno);
2375	}
2376	}
2377	}
2378	}
2379
2380
2381	/* Set up ELIMINABLE_REGSET, IRA_NO_ALLOC_REGS, and
2382	REGS_EVER_LIVE. */
2383	void
2384	ira_setup_eliminable_regset (void)
2385	{
2386	int i;
2387	static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
2388	int fp_reg_count = hard_regno_nregs (HARD_FRAME_POINTER_REGNUM, Pmode);
2389
2390	/* Setup is_leaf as frame_pointer_required may use it. This function
2391	is called by sched_init before ira if scheduling is enabled. */
2392	crtl->is_leaf = leaf_function_p ();
2393
2394	/* FIXME: If EXIT_IGNORE_STACK is set, we will not save and restore
2395	sp for alloca. So we can't eliminate the frame pointer in that
2396	case. At some point, we should improve this by emitting the
2397	sp-adjusting insns for this case. */
2398	frame_pointer_needed
2399	= (! flag_omit_frame_pointer
2400	|| (cfun->calls_alloca && EXIT_IGNORE_STACK)
2401	/* We need the frame pointer to catch stack overflow exceptions if
2402	the stack pointer is moving (as for the alloca case just above). */
2403	|| (STACK_CHECK_MOVING_SP
2404	&& flag_stack_check
2405	&& flag_exceptions
2406	&& cfun->can_throw_non_call_exceptions)
2407	|| crtl->accesses_prior_frames
2408	|| (SUPPORTS_STACK_ALIGNMENT && crtl->stack_realign_needed)
2409	|| targetm.frame_pointer_required ());
2410
2411	/* The chance that FRAME_POINTER_NEEDED is changed from inspecting
2412	RTL is very small. So if we use frame pointer for RA and RTL
2413	actually prevents this, we will spill pseudos assigned to the
2414	frame pointer in LRA. */
2415
2416	if (frame_pointer_needed)
2417	for (i = 0; i < fp_reg_count; i++)
2418	df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM + i, true);
2419
2420	ira_no_alloc_regs = no_unit_alloc_regs;
2421	CLEAR_HARD_REG_SET (set&: eliminable_regset);
2422
2423	compute_regs_asm_clobbered ();
2424
2425	/* Build the regset of all eliminable registers and show we can't
2426	use those that we already know won't be eliminated. */
2427	for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
2428	{
2429	bool cannot_elim
2430	= (! targetm.can_eliminate (eliminables[i].from, eliminables[i].to)
2431	|| (eliminables[i].to == STACK_POINTER_REGNUM && frame_pointer_needed));
2432
2433	if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, bit: eliminables[i].from))
2434	{
2435	SET_HARD_REG_BIT (set&: eliminable_regset, bit: eliminables[i].from);
2436
2437	if (cannot_elim)
2438	SET_HARD_REG_BIT (ira_no_alloc_regs, bit: eliminables[i].from);
2439	}
2440	else if (cannot_elim)
2441	error ("%s cannot be used in %<asm%> here",
2442	reg_names[eliminables[i].from]);
2443	else
2444	df_set_regs_ever_live (eliminables[i].from, true);
2445	}
2446	if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
2447	{
2448	for (i = 0; i < fp_reg_count; i++)
2449	if (global_regs[HARD_FRAME_POINTER_REGNUM + i])
2450	/* Nothing to do: the register is already treated as live
2451	where appropriate, and cannot be eliminated. */
2452	;
2453	else if (!TEST_HARD_REG_BIT (crtl->asm_clobbers,
2454	HARD_FRAME_POINTER_REGNUM + i))
2455	{
2456	SET_HARD_REG_BIT (set&: eliminable_regset,
2457	HARD_FRAME_POINTER_REGNUM + i);
2458	if (frame_pointer_needed)
2459	SET_HARD_REG_BIT (ira_no_alloc_regs,
2460	HARD_FRAME_POINTER_REGNUM + i);
2461	}
2462	else if (frame_pointer_needed)
2463	error ("%s cannot be used in %<asm%> here",
2464	reg_names[HARD_FRAME_POINTER_REGNUM + i]);
2465	else
2466	df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM + i, true);
2467	}
2468	}
2469
2470
2471
2472	/* Vector of substitutions of register numbers,
2473	used to map pseudo regs into hardware regs.
2474	This is set up as a result of register allocation.
2475	Element N is the hard reg assigned to pseudo reg N,
2476	or is -1 if no hard reg was assigned.
2477	If N is a hard reg number, element N is N. */
2478	short *reg_renumber;
2479
2480	/* Set up REG_RENUMBER and CALLER_SAVE_NEEDED (used by reload) from
2481	the allocation found by IRA. */
2482	static void
2483	setup_reg_renumber (void)
2484	{
2485	int regno, hard_regno;
2486	ira_allocno_t a;
2487	ira_allocno_iterator ai;
2488
2489	caller_save_needed = 0;
2490	FOR_EACH_ALLOCNO (a, ai)
2491	{
2492	if (ira_use_lra_p && ALLOCNO_CAP_MEMBER (a) != NULL)
2493	continue;
2494	/* There are no caps at this point. */
2495	ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2496	if (! ALLOCNO_ASSIGNED_P (a))
2497	/* It can happen if A is not referenced but partially anticipated
2498	somewhere in a region. */
2499	ALLOCNO_ASSIGNED_P (a) = true;
2500	ira_free_allocno_updated_costs (a);
2501	hard_regno = ALLOCNO_HARD_REGNO (a);
2502	regno = ALLOCNO_REGNO (a);
2503	reg_renumber[regno] = (hard_regno < 0 ? -1 : hard_regno);
2504	if (hard_regno >= 0)
2505	{
2506	int i, nwords;
2507	enum reg_class pclass;
2508	ira_object_t obj;
2509
2510	pclass = ira_pressure_class_translate[REGNO_REG_CLASS (hard_regno)];
2511	nwords = ALLOCNO_NUM_OBJECTS (a);
2512	for (i = 0; i < nwords; i++)
2513	{
2514	obj = ALLOCNO_OBJECT (a, i);
2515	OBJECT_TOTAL_CONFLICT_HARD_REGS (obj)
2516	|= ~reg_class_contents[pclass];
2517	}
2518	if (ira_need_caller_save_p (a, regno: hard_regno))
2519	{
2520	ira_assert (!optimize || flag_caller_saves
2521	|| (ALLOCNO_CALLS_CROSSED_NUM (a)
2522	== ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a))
2523	|| regno >= ira_reg_equiv_len
2524	|| ira_equiv_no_lvalue_p (regno));
2525	caller_save_needed = 1;
2526	}
2527	}
2528	}
2529	}
2530
2531	/* Set up allocno assignment flags for further allocation
2532	improvements. */
2533	static void
2534	setup_allocno_assignment_flags (void)
2535	{
2536	int hard_regno;
2537	ira_allocno_t a;
2538	ira_allocno_iterator ai;
2539
2540	FOR_EACH_ALLOCNO (a, ai)
2541	{
2542	if (! ALLOCNO_ASSIGNED_P (a))
2543	/* It can happen if A is not referenced but partially anticipated
2544	somewhere in a region. */
2545	ira_free_allocno_updated_costs (a);
2546	hard_regno = ALLOCNO_HARD_REGNO (a);
2547	/* Don't assign hard registers to allocnos which are destination
2548	of removed store at the end of loop. It has no sense to keep
2549	the same value in different hard registers. It is also
2550	impossible to assign hard registers correctly to such
2551	allocnos because the cost info and info about intersected
2552	calls are incorrect for them. */
2553	ALLOCNO_ASSIGNED_P (a) = (hard_regno >= 0
2554	|| ALLOCNO_EMIT_DATA (a)->mem_optimized_dest_p
2555	|| (ALLOCNO_MEMORY_COST (a)
2556	- ALLOCNO_CLASS_COST (a)) < 0);
2557	ira_assert
2558	(hard_regno < 0
2559	|| ira_hard_reg_in_set_p (hard_regno, ALLOCNO_MODE (a),
2560	reg_class_contents[ALLOCNO_CLASS (a)]));
2561	}
2562	}
2563
2564	/* Evaluate overall allocation cost and the costs for using hard
2565	registers and memory for allocnos. */
2566	static void
2567	calculate_allocation_cost (void)
2568	{
2569	int hard_regno, cost;
2570	ira_allocno_t a;
2571	ira_allocno_iterator ai;
2572
2573	ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
2574	FOR_EACH_ALLOCNO (a, ai)
2575	{
2576	hard_regno = ALLOCNO_HARD_REGNO (a);
2577	ira_assert (hard_regno < 0
2578	|| (ira_hard_reg_in_set_p
2579	(hard_regno, ALLOCNO_MODE (a),
2580	reg_class_contents[ALLOCNO_CLASS (a)])));
2581	if (hard_regno < 0)
2582	{
2583	cost = ALLOCNO_MEMORY_COST (a);
2584	ira_mem_cost += cost;
2585	}
2586	else if (ALLOCNO_HARD_REG_COSTS (a) != NULL)
2587	{
2588	cost = (ALLOCNO_HARD_REG_COSTS (a)
2589	[ira_class_hard_reg_index
2590	[ALLOCNO_CLASS (a)][hard_regno]]);
2591	ira_reg_cost += cost;
2592	}
2593	else
2594	{
2595	cost = ALLOCNO_CLASS_COST (a);
2596	ira_reg_cost += cost;
2597	}
2598	ira_overall_cost += cost;
2599	}
2600
2601	if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2602	{
2603	fprintf (stream: ira_dump_file,
2604	format: "+++Costs: overall %" PRId64
2605	", reg %" PRId64
2606	", mem %" PRId64
2607	", ld %" PRId64
2608	", st %" PRId64
2609	", move %" PRId64,
2610	ira_overall_cost, ira_reg_cost, ira_mem_cost,
2611	ira_load_cost, ira_store_cost, ira_shuffle_cost);
2612	fprintf (stream: ira_dump_file, format: "\n+++ move loops %d, new jumps %d\n",
2613	ira_move_loops_num, ira_additional_jumps_num);
2614	}
2615
2616	}
2617
2618	#ifdef ENABLE_IRA_CHECKING
2619	/* Check the correctness of the allocation. We do need this because
2620	of complicated code to transform more one region internal
2621	representation into one region representation. */
2622	static void
2623	check_allocation (void)
2624	{
2625	ira_allocno_t a;
2626	int hard_regno, nregs, conflict_nregs;
2627	ira_allocno_iterator ai;
2628
2629	FOR_EACH_ALLOCNO (a, ai)
2630	{
2631	int n = ALLOCNO_NUM_OBJECTS (a);
2632	int i;
2633
2634	if (ALLOCNO_CAP_MEMBER (a) != NULL
2635	|| (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0)
2636	continue;
2637	nregs = hard_regno_nregs (regno: hard_regno, ALLOCNO_MODE (a));
2638	if (nregs == 1)
2639	/* We allocated a single hard register. */
2640	n = 1;
2641	else if (n > 1)
2642	/* We allocated multiple hard registers, and we will test
2643	conflicts in a granularity of single hard regs. */
2644	nregs = 1;
2645
2646	for (i = 0; i < n; i++)
2647	{
2648	ira_object_t obj = ALLOCNO_OBJECT (a, i);
2649	ira_object_t conflict_obj;
2650	ira_object_conflict_iterator oci;
2651	int this_regno = hard_regno;
2652	if (n > 1)
2653	{
2654	if (REG_WORDS_BIG_ENDIAN)
2655	this_regno += n - i - 1;
2656	else
2657	this_regno += i;
2658	}
2659	FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2660	{
2661	ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2662	int conflict_hard_regno = ALLOCNO_HARD_REGNO (conflict_a);
2663	if (conflict_hard_regno < 0)
2664	continue;
2665	if (ira_soft_conflict (a, conflict_a))
2666	continue;
2667
2668	conflict_nregs = hard_regno_nregs (regno: conflict_hard_regno,
2669	ALLOCNO_MODE (conflict_a));
2670
2671	if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1
2672	&& conflict_nregs == ALLOCNO_NUM_OBJECTS (conflict_a))
2673	{
2674	if (REG_WORDS_BIG_ENDIAN)
2675	conflict_hard_regno += (ALLOCNO_NUM_OBJECTS (conflict_a)
2676	- OBJECT_SUBWORD (conflict_obj) - 1);
2677	else
2678	conflict_hard_regno += OBJECT_SUBWORD (conflict_obj);
2679	conflict_nregs = 1;
2680	}
2681
2682	if ((conflict_hard_regno <= this_regno
2683	&& this_regno < conflict_hard_regno + conflict_nregs)
2684	|| (this_regno <= conflict_hard_regno
2685	&& conflict_hard_regno < this_regno + nregs))
2686	{
2687	fprintf (stderr, format: "bad allocation for %d and %d\n",
2688	ALLOCNO_REGNO (a), ALLOCNO_REGNO (conflict_a));
2689	gcc_unreachable ();
2690	}
2691	}
2692	}
2693	}
2694	}
2695	#endif
2696
2697	/* Allocate REG_EQUIV_INIT. Set up it from IRA_REG_EQUIV which should
2698	be already calculated. */
2699	static void
2700	setup_reg_equiv_init (void)
2701	{
2702	int i;
2703	int max_regno = max_reg_num ();
2704
2705	for (i = 0; i < max_regno; i++)
2706	reg_equiv_init (i) = ira_reg_equiv[i].init_insns;
2707	}
2708
2709	/* Update equiv regno from movement of FROM_REGNO to TO_REGNO. INSNS
2710	are insns which were generated for such movement. It is assumed
2711	that FROM_REGNO and TO_REGNO always have the same value at the
2712	point of any move containing such registers. This function is used
2713	to update equiv info for register shuffles on the region borders
2714	and for caller save/restore insns. */
2715	void
2716	ira_update_equiv_info_by_shuffle_insn (int to_regno, int from_regno, rtx_insn *insns)
2717	{
2718	rtx_insn *insn;
2719	rtx x, note;
2720
2721	if (! ira_reg_equiv[from_regno].defined_p
2722	&& (! ira_reg_equiv[to_regno].defined_p
2723	|| ((x = ira_reg_equiv[to_regno].memory) != NULL_RTX
2724	&& ! MEM_READONLY_P (x))))
2725	return;
2726	insn = insns;
2727	if (NEXT_INSN (insn) != NULL_RTX)
2728	{
2729	if (! ira_reg_equiv[to_regno].defined_p)
2730	{
2731	ira_assert (ira_reg_equiv[to_regno].init_insns == NULL_RTX);
2732	return;
2733	}
2734	ira_reg_equiv[to_regno].defined_p = false;
2735	ira_reg_equiv[to_regno].caller_save_p = false;
2736	ira_reg_equiv[to_regno].memory
2737	= ira_reg_equiv[to_regno].constant
2738	= ira_reg_equiv[to_regno].invariant
2739	= ira_reg_equiv[to_regno].init_insns = NULL;
2740	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2741	fprintf (stream: ira_dump_file,
2742	format: " Invalidating equiv info for reg %d\n", to_regno);
2743	return;
2744	}
2745	/* It is possible that FROM_REGNO still has no equivalence because
2746	in shuffles to_regno<-from_regno and from_regno<-to_regno the 2nd
2747	insn was not processed yet. */
2748	if (ira_reg_equiv[from_regno].defined_p)
2749	{
2750	ira_reg_equiv[to_regno].defined_p = true;
2751	if ((x = ira_reg_equiv[from_regno].memory) != NULL_RTX)
2752	{
2753	ira_assert (ira_reg_equiv[from_regno].invariant == NULL_RTX
2754	&& ira_reg_equiv[from_regno].constant == NULL_RTX);
2755	ira_assert (ira_reg_equiv[to_regno].memory == NULL_RTX
2756	|| rtx_equal_p (ira_reg_equiv[to_regno].memory, x));
2757	ira_reg_equiv[to_regno].memory = x;
2758	if (! MEM_READONLY_P (x))
2759	/* We don't add the insn to insn init list because memory
2760	equivalence is just to say what memory is better to use
2761	when the pseudo is spilled. */
2762	return;
2763	}
2764	else if ((x = ira_reg_equiv[from_regno].constant) != NULL_RTX)
2765	{
2766	ira_assert (ira_reg_equiv[from_regno].invariant == NULL_RTX);
2767	ira_assert (ira_reg_equiv[to_regno].constant == NULL_RTX
2768	|| rtx_equal_p (ira_reg_equiv[to_regno].constant, x));
2769	ira_reg_equiv[to_regno].constant = x;
2770	}
2771	else
2772	{
2773	x = ira_reg_equiv[from_regno].invariant;
2774	ira_assert (x != NULL_RTX);
2775	ira_assert (ira_reg_equiv[to_regno].invariant == NULL_RTX
2776	|| rtx_equal_p (ira_reg_equiv[to_regno].invariant, x));
2777	ira_reg_equiv[to_regno].invariant = x;
2778	}
2779	if (find_reg_note (insn, REG_EQUIV, x) == NULL_RTX)
2780	{
2781	note = set_unique_reg_note (insn, REG_EQUIV, copy_rtx (x));
2782	gcc_assert (note != NULL_RTX);
2783	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2784	{
2785	fprintf (stream: ira_dump_file,
2786	format: " Adding equiv note to insn %u for reg %d ",
2787	INSN_UID (insn), to_regno);
2788	dump_value_slim (ira_dump_file, x, 1);
2789	fprintf (stream: ira_dump_file, format: "\n");
2790	}
2791	}
2792	}
2793	ira_reg_equiv[to_regno].init_insns
2794	= gen_rtx_INSN_LIST (VOIDmode, insn,
2795	ira_reg_equiv[to_regno].init_insns);
2796	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2797	fprintf (stream: ira_dump_file,
2798	format: " Adding equiv init move insn %u to reg %d\n",
2799	INSN_UID (insn), to_regno);
2800	}
2801
2802	/* Fix values of array REG_EQUIV_INIT after live range splitting done
2803	by IRA. */
2804	static void
2805	fix_reg_equiv_init (void)
2806	{
2807	int max_regno = max_reg_num ();
2808	int i, new_regno, max;
2809	rtx set;
2810	rtx_insn_list *x, *next, *prev;
2811	rtx_insn *insn;
2812
2813	if (max_regno_before_ira < max_regno)
2814	{
2815	max = vec_safe_length (v: reg_equivs);
2816	grow_reg_equivs ();
2817	for (i = FIRST_PSEUDO_REGISTER; i < max; i++)
2818	for (prev = NULL, x = reg_equiv_init (i);
2819	x != NULL_RTX;
2820	x = next)
2821	{
2822	next = x->next ();
2823	insn = x->insn ();
2824	set = single_set (insn);
2825	ira_assert (set != NULL_RTX
2826	&& (REG_P (SET_DEST (set)) || REG_P (SET_SRC (set))));
2827	if (REG_P (SET_DEST (set))
2828	&& ((int) REGNO (SET_DEST (set)) == i
2829	|| (int) ORIGINAL_REGNO (SET_DEST (set)) == i))
2830	new_regno = REGNO (SET_DEST (set));
2831	else if (REG_P (SET_SRC (set))
2832	&& ((int) REGNO (SET_SRC (set)) == i
2833	|| (int) ORIGINAL_REGNO (SET_SRC (set)) == i))
2834	new_regno = REGNO (SET_SRC (set));
2835	else
2836	gcc_unreachable ();
2837	if (new_regno == i)
2838	prev = x;
2839	else
2840	{
2841	/* Remove the wrong list element. */
2842	if (prev == NULL_RTX)
2843	reg_equiv_init (i) = next;
2844	else
2845	XEXP (prev, 1) = next;
2846	XEXP (x, 1) = reg_equiv_init (new_regno);
2847	reg_equiv_init (new_regno) = x;
2848	}
2849	}
2850	}
2851	}
2852
2853	#ifdef ENABLE_IRA_CHECKING
2854	/* Print redundant memory-memory copies. */
2855	static void
2856	print_redundant_copies (void)
2857	{
2858	int hard_regno;
2859	ira_allocno_t a;
2860	ira_copy_t cp, next_cp;
2861	ira_allocno_iterator ai;
2862
2863	FOR_EACH_ALLOCNO (a, ai)
2864	{
2865	if (ALLOCNO_CAP_MEMBER (a) != NULL)
2866	/* It is a cap. */
2867	continue;
2868	hard_regno = ALLOCNO_HARD_REGNO (a);
2869	if (hard_regno >= 0)
2870	continue;
2871	for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2872	if (cp->first == a)
2873	next_cp = cp->next_first_allocno_copy;
2874	else
2875	{
2876	next_cp = cp->next_second_allocno_copy;
2877	if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL
2878	&& cp->insn != NULL_RTX
2879	&& ALLOCNO_HARD_REGNO (cp->first) == hard_regno)
2880	fprintf (stream: ira_dump_file,
2881	format: " Redundant move from %d(freq %d):%d\n",
2882	INSN_UID (insn: cp->insn), cp->freq, hard_regno);
2883	}
2884	}
2885	}
2886	#endif
2887
2888	/* Setup preferred and alternative classes for new pseudo-registers
2889	created by IRA starting with START. */
2890	static void
2891	setup_preferred_alternate_classes_for_new_pseudos (int start)
2892	{
2893	int i, old_regno;
2894	int max_regno = max_reg_num ();
2895
2896	for (i = start; i < max_regno; i++)
2897	{
2898	old_regno = ORIGINAL_REGNO (regno_reg_rtx[i]);
2899	ira_assert (i != old_regno);
2900	setup_reg_classes (i, reg_preferred_class (old_regno),
2901	reg_alternate_class (old_regno),
2902	reg_allocno_class (old_regno));
2903	if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2904	fprintf (stream: ira_dump_file,
2905	format: " New r%d: setting preferred %s, alternative %s\n",
2906	i, reg_class_names[reg_preferred_class (old_regno)],
2907	reg_class_names[reg_alternate_class (old_regno)]);
2908	}
2909	}
2910
2911
2912	/* The number of entries allocated in reg_info. */
2913	static int allocated_reg_info_size;
2914
2915	/* Regional allocation can create new pseudo-registers. This function
2916	expands some arrays for pseudo-registers. */
2917	static void
2918	expand_reg_info (void)
2919	{
2920	int i;
2921	int size = max_reg_num ();
2922
2923	resize_reg_info ();
2924	for (i = allocated_reg_info_size; i < size; i++)
2925	setup_reg_classes (i, GENERAL_REGS, ALL_REGS, GENERAL_REGS);
2926	setup_preferred_alternate_classes_for_new_pseudos (allocated_reg_info_size);
2927	allocated_reg_info_size = size;
2928	}
2929
2930	/* Return TRUE if there is too high register pressure in the function.
2931	It is used to decide when stack slot sharing is worth to do. */
2932	static bool
2933	too_high_register_pressure_p (void)
2934	{
2935	int i;
2936	enum reg_class pclass;
2937
2938	for (i = 0; i < ira_pressure_classes_num; i++)
2939	{
2940	pclass = ira_pressure_classes[i];
2941	if (ira_loop_tree_root->reg_pressure[pclass] > 10000)
2942	return true;
2943	}
2944	return false;
2945	}
2946
2947
2948
2949	/* Indicate that hard register number FROM was eliminated and replaced with
2950	an offset from hard register number TO. The status of hard registers live
2951	at the start of a basic block is updated by replacing a use of FROM with
2952	a use of TO. */
2953
2954	void
2955	mark_elimination (int from, int to)
2956	{
2957	basic_block bb;
2958	bitmap r;
2959
2960	FOR_EACH_BB_FN (bb, cfun)
2961	{
2962	r = DF_LR_IN (bb);
2963	if (bitmap_bit_p (r, from))
2964	{
2965	bitmap_clear_bit (r, from);
2966	bitmap_set_bit (r, to);
2967	}
2968	if (! df_live)
2969	continue;
2970	r = DF_LIVE_IN (bb);
2971	if (bitmap_bit_p (r, from))
2972	{
2973	bitmap_clear_bit (r, from);
2974	bitmap_set_bit (r, to);
2975	}
2976	}
2977	}
2978
2979
2980
2981	/* The length of the following array. */
2982	int ira_reg_equiv_len;
2983
2984	/* Info about equiv. info for each register. */
2985	struct ira_reg_equiv_s *ira_reg_equiv;
2986
2987	/* Expand ira_reg_equiv if necessary. */
2988	void
2989	ira_expand_reg_equiv (void)
2990	{
2991	int old = ira_reg_equiv_len;
2992
2993	if (ira_reg_equiv_len > max_reg_num ())
2994	return;
2995	ira_reg_equiv_len = max_reg_num () * 3 / 2 + 1;
2996	ira_reg_equiv
2997	= (struct ira_reg_equiv_s *) xrealloc (ira_reg_equiv,
2998	ira_reg_equiv_len
2999	* sizeof (struct ira_reg_equiv_s));
3000	gcc_assert (old < ira_reg_equiv_len);
3001	memset (s: ira_reg_equiv + old, c: 0,
3002	n: sizeof (struct ira_reg_equiv_s) * (ira_reg_equiv_len - old));
3003	}
3004
3005	static void
3006	init_reg_equiv (void)
3007	{
3008	ira_reg_equiv_len = 0;
3009	ira_reg_equiv = NULL;
3010	ira_expand_reg_equiv ();
3011	}
3012
3013	static void
3014	finish_reg_equiv (void)
3015	{
3016	free (ptr: ira_reg_equiv);
3017	}
3018
3019
3020
3021	struct equivalence
3022	{
3023	/* Set when a REG_EQUIV note is found or created. Use to
3024	keep track of what memory accesses might be created later,
3025	e.g. by reload. */
3026	rtx replacement;
3027	rtx *src_p;
3028
3029	/* The list of each instruction which initializes this register.
3030
3031	NULL indicates we know nothing about this register's equivalence
3032	properties.
3033
3034	An INSN_LIST with a NULL insn indicates this pseudo is already
3035	known to not have a valid equivalence. */
3036	rtx_insn_list *init_insns;
3037
3038	/* Loop depth is used to recognize equivalences which appear
3039	to be present within the same loop (or in an inner loop). */
3040	short loop_depth;
3041	/* Nonzero if this had a preexisting REG_EQUIV note. */
3042	unsigned char is_arg_equivalence : 1;
3043	/* Set when an attempt should be made to replace a register
3044	with the associated src_p entry. */
3045	unsigned char replace : 1;
3046	/* Set if this register has no known equivalence. */
3047	unsigned char no_equiv : 1;
3048	/* Set if this register is mentioned in a paradoxical subreg. */
3049	unsigned char pdx_subregs : 1;
3050	};
3051
3052	/* reg_equiv[N] (where N is a pseudo reg number) is the equivalence
3053	structure for that register. */
3054	static struct equivalence *reg_equiv;
3055
3056	/* Used for communication between the following two functions. */
3057	struct equiv_mem_data
3058	{
3059	/* A MEM that we wish to ensure remains unchanged. */
3060	rtx equiv_mem;
3061
3062	/* Set true if EQUIV_MEM is modified. */
3063	bool equiv_mem_modified;
3064	};
3065
3066	/* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified.
3067	Called via note_stores. */
3068	static void
3069	validate_equiv_mem_from_store (rtx dest, const_rtx set ATTRIBUTE_UNUSED,
3070	void *data)
3071	{
3072	struct equiv_mem_data *info = (struct equiv_mem_data *) data;
3073
3074	if ((REG_P (dest)
3075	&& reg_overlap_mentioned_p (dest, info->equiv_mem))
3076	|| (MEM_P (dest)
3077	&& anti_dependence (info->equiv_mem, dest)))
3078	info->equiv_mem_modified = true;
3079	}
3080
3081	static bool equiv_init_varies_p (rtx x);
3082
3083	enum valid_equiv { valid_none, valid_combine, valid_reload };
3084
3085	/* Verify that no store between START and the death of REG invalidates
3086	MEMREF. MEMREF is invalidated by modifying a register used in MEMREF,
3087	by storing into an overlapping memory location, or with a non-const
3088	CALL_INSN.
3089
3090	Return VALID_RELOAD if MEMREF remains valid for both reload and
3091	combine_and_move insns, VALID_COMBINE if only valid for
3092	combine_and_move_insns, and VALID_NONE otherwise. */
3093	static enum valid_equiv
3094	validate_equiv_mem (rtx_insn *start, rtx reg, rtx memref)
3095	{
3096	rtx_insn *insn;
3097	rtx note;
3098	struct equiv_mem_data info = { .equiv_mem: memref, .equiv_mem_modified: false };
3099	enum valid_equiv ret = valid_reload;
3100
3101	/* If the memory reference has side effects or is volatile, it isn't a
3102	valid equivalence. */
3103	if (side_effects_p (memref))
3104	return valid_none;
3105
3106	for (insn = start; insn; insn = NEXT_INSN (insn))
3107	{
3108	if (!INSN_P (insn))
3109	continue;
3110
3111	if (find_reg_note (insn, REG_DEAD, reg))
3112	return ret;
3113
3114	if (CALL_P (insn))
3115	{
3116	/* We can combine a reg def from one insn into a reg use in
3117	another over a call if the memory is readonly or the call
3118	const/pure. However, we can't set reg_equiv notes up for
3119	reload over any call. The problem is the equivalent form
3120	may reference a pseudo which gets assigned a call
3121	clobbered hard reg. When we later replace REG with its
3122	equivalent form, the value in the call-clobbered reg has
3123	been changed and all hell breaks loose. */
3124	ret = valid_combine;
3125	if (!MEM_READONLY_P (memref)
3126	&& (!RTL_CONST_OR_PURE_CALL_P (insn)
3127	|| equiv_init_varies_p (XEXP (memref, 0))))
3128	return valid_none;
3129	}
3130
3131	note_stores (insn, validate_equiv_mem_from_store, &info);
3132	if (info.equiv_mem_modified)
3133	return valid_none;
3134
3135	/* If a register mentioned in MEMREF is modified via an
3136	auto-increment, we lose the equivalence. Do the same if one
3137	dies; although we could extend the life, it doesn't seem worth
3138	the trouble. */
3139
3140	for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
3141	if ((REG_NOTE_KIND (note) == REG_INC
3142	|| REG_NOTE_KIND (note) == REG_DEAD)
3143	&& REG_P (XEXP (note, 0))
3144	&& reg_overlap_mentioned_p (XEXP (note, 0), memref))
3145	return valid_none;
3146	}
3147
3148	return valid_none;
3149	}
3150
3151	/* Returns false if X is known to be invariant. */
3152	static bool
3153	equiv_init_varies_p (rtx x)
3154	{
3155	RTX_CODE code = GET_CODE (x);
3156	int i;
3157	const char *fmt;
3158
3159	switch (code)
3160	{
3161	case MEM:
3162	return !MEM_READONLY_P (x) || equiv_init_varies_p (XEXP (x, 0));
3163
3164	case CONST:
3165	CASE_CONST_ANY:
3166	case SYMBOL_REF:
3167	case LABEL_REF:
3168	return false;
3169
3170	case REG:
3171	return reg_equiv[REGNO (x)].replace == 0 && rtx_varies_p (x, 0);
3172
3173	case ASM_OPERANDS:
3174	if (MEM_VOLATILE_P (x))
3175	return true;
3176
3177	/* Fall through. */
3178
3179	default:
3180	break;
3181	}
3182
3183	fmt = GET_RTX_FORMAT (code);
3184	for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3185	if (fmt[i] == 'e')
3186	{
3187	if (equiv_init_varies_p (XEXP (x, i)))
3188	return true;
3189	}
3190	else if (fmt[i] == 'E')
3191	{
3192	int j;
3193	for (j = 0; j < XVECLEN (x, i); j++)
3194	if (equiv_init_varies_p (XVECEXP (x, i, j)))
3195	return true;
3196	}
3197
3198	return false;
3199	}
3200
3201	/* Returns true if X (used to initialize register REGNO) is movable.
3202	X is only movable if the registers it uses have equivalent initializations
3203	which appear to be within the same loop (or in an inner loop) and movable
3204	or if they are not candidates for local_alloc and don't vary. */
3205	static bool
3206	equiv_init_movable_p (rtx x, int regno)
3207	{
3208	int i, j;
3209	const char *fmt;
3210	enum rtx_code code = GET_CODE (x);
3211
3212	switch (code)
3213	{
3214	case SET:
3215	return equiv_init_movable_p (SET_SRC (x), regno);
3216
3217	case CLOBBER:
3218	return false;
3219
3220	case PRE_INC:
3221	case PRE_DEC:
3222	case POST_INC:
3223	case POST_DEC:
3224	case PRE_MODIFY:
3225	case POST_MODIFY:
3226	return false;
3227
3228	case REG:
3229	return ((reg_equiv[REGNO (x)].loop_depth >= reg_equiv[regno].loop_depth
3230	&& reg_equiv[REGNO (x)].replace)
3231	|| (REG_BASIC_BLOCK (REGNO (x)) < NUM_FIXED_BLOCKS
3232	&& ! rtx_varies_p (x, 0)));
3233
3234	case UNSPEC_VOLATILE:
3235	return false;
3236
3237	case ASM_OPERANDS:
3238	if (MEM_VOLATILE_P (x))
3239	return false;
3240
3241	/* Fall through. */
3242
3243	default:
3244	break;
3245	}
3246
3247	fmt = GET_RTX_FORMAT (code);
3248	for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3249	switch (fmt[i])
3250	{
3251	case 'e':
3252	if (! equiv_init_movable_p (XEXP (x, i), regno))
3253	return false;
3254	break;
3255	case 'E':
3256	for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3257	if (! equiv_init_movable_p (XVECEXP (x, i, j), regno))
3258	return false;
3259	break;
3260	}
3261
3262	return true;
3263	}
3264
3265	static bool memref_referenced_p (rtx memref, rtx x, bool read_p);
3266
3267	/* Auxiliary function for memref_referenced_p. Process setting X for
3268	MEMREF store. */
3269	static bool
3270	process_set_for_memref_referenced_p (rtx memref, rtx x)
3271	{
3272	/* If we are setting a MEM, it doesn't count (its address does), but any
3273	other SET_DEST that has a MEM in it is referencing the MEM. */
3274	if (MEM_P (x))
3275	{
3276	if (memref_referenced_p (memref, XEXP (x, 0), read_p: true))
3277	return true;
3278	}
3279	else if (memref_referenced_p (memref, x, read_p: false))
3280	return true;
3281
3282	return false;
3283	}
3284
3285	/* TRUE if X references a memory location (as a read if READ_P) that
3286	would be affected by a store to MEMREF. */
3287	static bool
3288	memref_referenced_p (rtx memref, rtx x, bool read_p)
3289	{
3290	int i, j;
3291	const char *fmt;
3292	enum rtx_code code = GET_CODE (x);
3293
3294	switch (code)
3295	{
3296	case CONST:
3297	case LABEL_REF:
3298	case SYMBOL_REF:
3299	CASE_CONST_ANY:
3300	case PC:
3301	case HIGH:
3302	case LO_SUM:
3303	return false;
3304
3305	case REG:
3306	return (reg_equiv[REGNO (x)].replacement
3307	&& memref_referenced_p (memref,
3308	x: reg_equiv[REGNO (x)].replacement, read_p));
3309
3310	case MEM:
3311	/* Memory X might have another effective type than MEMREF. */
3312	if (read_p || true_dependence (memref, VOIDmode, x))
3313	return true;
3314	break;
3315
3316	case SET:
3317	if (process_set_for_memref_referenced_p (memref, SET_DEST (x)))
3318	return true;
3319
3320	return memref_referenced_p (memref, SET_SRC (x), read_p: true);
3321
3322	case CLOBBER:
3323	if (process_set_for_memref_referenced_p (memref, XEXP (x, 0)))
3324	return true;
3325
3326	return false;
3327
3328	case PRE_DEC:
3329	case POST_DEC:
3330	case PRE_INC:
3331	case POST_INC:
3332	if (process_set_for_memref_referenced_p (memref, XEXP (x, 0)))
3333	return true;
3334
3335	return memref_referenced_p (memref, XEXP (x, 0), read_p: true);
3336
3337	case POST_MODIFY:
3338	case PRE_MODIFY:
3339	/* op0 = op0 + op1 */
3340	if (process_set_for_memref_referenced_p (memref, XEXP (x, 0)))
3341	return true;
3342
3343	if (memref_referenced_p (memref, XEXP (x, 0), read_p: true))
3344	return true;
3345
3346	return memref_referenced_p (memref, XEXP (x, 1), read_p: true);
3347
3348	default:
3349	break;
3350	}
3351
3352	fmt = GET_RTX_FORMAT (code);
3353	for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3354	switch (fmt[i])
3355	{
3356	case 'e':
3357	if (memref_referenced_p (memref, XEXP (x, i), read_p))
3358	return true;
3359	break;
3360	case 'E':
3361	for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3362	if (memref_referenced_p (memref, XVECEXP (x, i, j), read_p))
3363	return true;
3364	break;
3365	}
3366
3367	return false;
3368	}
3369
3370	/* TRUE if some insn in the range (START, END] references a memory location
3371	that would be affected by a store to MEMREF.
3372
3373	Callers should not call this routine if START is after END in the
3374	RTL chain. */
3375
3376	static bool
3377	memref_used_between_p (rtx memref, rtx_insn *start, rtx_insn *end)
3378	{
3379	rtx_insn *insn;
3380
3381	for (insn = NEXT_INSN (insn: start);
3382	insn && insn != NEXT_INSN (insn: end);
3383	insn = NEXT_INSN (insn))
3384	{
3385	if (!NONDEBUG_INSN_P (insn))
3386	continue;
3387
3388	if (memref_referenced_p (memref, x: PATTERN (insn), read_p: false))
3389	return true;
3390
3391	/* Nonconst functions may access memory. */
3392	if (CALL_P (insn) && (! RTL_CONST_CALL_P (insn)))
3393	return true;
3394	}
3395
3396	gcc_assert (insn == NEXT_INSN (end));
3397	return false;
3398	}
3399
3400	/* Mark REG as having no known equivalence.
3401	Some instructions might have been processed before and furnished
3402	with REG_EQUIV notes for this register; these notes will have to be
3403	removed.
3404	STORE is the piece of RTL that does the non-constant / conflicting
3405	assignment - a SET, CLOBBER or REG_INC note. It is currently not used,
3406	but needs to be there because this function is called from note_stores. */
3407	static void
3408	no_equiv (rtx reg, const_rtx store ATTRIBUTE_UNUSED,
3409	void *data ATTRIBUTE_UNUSED)
3410	{
3411	int regno;
3412	rtx_insn_list *list;
3413
3414	if (!REG_P (reg))
3415	return;
3416	regno = REGNO (reg);
3417	reg_equiv[regno].no_equiv = 1;
3418	list = reg_equiv[regno].init_insns;
3419	if (list && list->insn () == NULL)
3420	return;
3421	reg_equiv[regno].init_insns = gen_rtx_INSN_LIST (VOIDmode, NULL_RTX, NULL);
3422	reg_equiv[regno].replacement = NULL_RTX;
3423	/* This doesn't matter for equivalences made for argument registers, we
3424	should keep their initialization insns. */
3425	if (reg_equiv[regno].is_arg_equivalence)
3426	return;
3427	ira_reg_equiv[regno].defined_p = false;
3428	ira_reg_equiv[regno].caller_save_p = false;
3429	ira_reg_equiv[regno].init_insns = NULL;
3430	for (; list; list = list->next ())
3431	{
3432	rtx_insn *insn = list->insn ();
3433	remove_note (insn, find_reg_note (insn, REG_EQUIV, NULL_RTX));
3434	}
3435	}
3436
3437	/* Check whether the SUBREG is a paradoxical subreg and set the result
3438	in PDX_SUBREGS. */
3439
3440	static void
3441	set_paradoxical_subreg (rtx_insn *insn)
3442	{
3443	subrtx_iterator::array_type array;
3444	FOR_EACH_SUBRTX (iter, array, PATTERN (insn), NONCONST)
3445	{
3446	const_rtx subreg = *iter;
3447	if (GET_CODE (subreg) == SUBREG)
3448	{
3449	const_rtx reg = SUBREG_REG (subreg);
3450	if (REG_P (reg) && paradoxical_subreg_p (x: subreg))
3451	reg_equiv[REGNO (reg)].pdx_subregs = true;
3452	}
3453	}
3454	}
3455
3456	/* In DEBUG_INSN location adjust REGs from CLEARED_REGS bitmap to the
3457	equivalent replacement. */
3458
3459	static rtx
3460	adjust_cleared_regs (rtx loc, const_rtx old_rtx ATTRIBUTE_UNUSED, void *data)
3461	{
3462	if (REG_P (loc))
3463	{
3464	bitmap cleared_regs = (bitmap) data;
3465	if (bitmap_bit_p (cleared_regs, REGNO (loc)))
3466	return simplify_replace_fn_rtx (copy_rtx (*reg_equiv[REGNO (loc)].src_p),
3467	NULL_RTX, fn: adjust_cleared_regs, data);
3468	}
3469	return NULL_RTX;
3470	}
3471
3472	/* Given register REGNO is set only once, return true if the defining
3473	insn dominates all uses. */
3474
3475	static bool
3476	def_dominates_uses (int regno)
3477	{
3478	df_ref def = DF_REG_DEF_CHAIN (regno);
3479
3480	struct df_insn_info *def_info = DF_REF_INSN_INFO (def);
3481	/* If this is an artificial def (eh handler regs, hard frame pointer
3482	for non-local goto, regs defined on function entry) then def_info
3483	is NULL and the reg is always live before any use. We might
3484	reasonably return true in that case, but since the only call
3485	of this function is currently here in ira.cc when we are looking
3486	at a defining insn we can't have an artificial def as that would
3487	bump DF_REG_DEF_COUNT. */
3488	gcc_assert (DF_REG_DEF_COUNT (regno) == 1 && def_info != NULL);
3489
3490	rtx_insn *def_insn = DF_REF_INSN (def);
3491	basic_block def_bb = BLOCK_FOR_INSN (insn: def_insn);
3492
3493	for (df_ref use = DF_REG_USE_CHAIN (regno);
3494	use;
3495	use = DF_REF_NEXT_REG (use))
3496	{
3497	struct df_insn_info *use_info = DF_REF_INSN_INFO (use);
3498	/* Only check real uses, not artificial ones. */
3499	if (use_info)
3500	{
3501	rtx_insn *use_insn = DF_REF_INSN (use);
3502	if (!DEBUG_INSN_P (use_insn))
3503	{
3504	basic_block use_bb = BLOCK_FOR_INSN (insn: use_insn);
3505	if (use_bb != def_bb
3506	? !dominated_by_p (CDI_DOMINATORS, use_bb, def_bb)
3507	: DF_INSN_INFO_LUID (use_info) < DF_INSN_INFO_LUID (def_info))
3508	return false;
3509	}
3510	}
3511	}
3512	return true;
3513	}
3514
3515	/* Scan the instructions before update_equiv_regs. Record which registers
3516	are referenced as paradoxical subregs. Also check for cases in which
3517	the current function needs to save a register that one of its call
3518	instructions clobbers.
3519
3520	These things are logically unrelated, but it's more efficient to do
3521	them together. */
3522
3523	static void
3524	update_equiv_regs_prescan (void)
3525	{
3526	basic_block bb;
3527	rtx_insn *insn;
3528	function_abi_aggregator callee_abis;
3529
3530	FOR_EACH_BB_FN (bb, cfun)
3531	FOR_BB_INSNS (bb, insn)
3532	if (NONDEBUG_INSN_P (insn))
3533	{
3534	set_paradoxical_subreg (insn);
3535	if (CALL_P (insn))
3536	callee_abis.note_callee_abi (abi: insn_callee_abi (insn));
3537	}
3538
3539	HARD_REG_SET extra_caller_saves = callee_abis.caller_save_regs (*crtl->abi);
3540	if (!hard_reg_set_empty_p (x: extra_caller_saves))
3541	for (unsigned int regno = 0; regno < FIRST_PSEUDO_REGISTER; ++regno)
3542	if (TEST_HARD_REG_BIT (set: extra_caller_saves, bit: regno))
3543	df_set_regs_ever_live (regno, true);
3544	}
3545
3546	/* Find registers that are equivalent to a single value throughout the
3547	compilation (either because they can be referenced in memory or are
3548	set once from a single constant). Lower their priority for a
3549	register.
3550
3551	If such a register is only referenced once, try substituting its
3552	value into the using insn. If it succeeds, we can eliminate the
3553	register completely.
3554
3555	Initialize init_insns in ira_reg_equiv array. */
3556	static void
3557	update_equiv_regs (void)
3558	{
3559	rtx_insn *insn;
3560	basic_block bb;
3561
3562	/* Scan the insns and find which registers have equivalences. Do this
3563	in a separate scan of the insns because (due to -fcse-follow-jumps)
3564	a register can be set below its use. */
3565	bitmap setjmp_crosses = regstat_get_setjmp_crosses ();
3566	FOR_EACH_BB_FN (bb, cfun)
3567	{
3568	int loop_depth = bb_loop_depth (bb);
3569
3570	for (insn = BB_HEAD (bb);
3571	insn != NEXT_INSN (BB_END (bb));
3572	insn = NEXT_INSN (insn))
3573	{
3574	rtx note;
3575	rtx set;
3576	rtx dest, src;
3577	int regno;
3578
3579	if (! INSN_P (insn))
3580	continue;
3581
3582	for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
3583	if (REG_NOTE_KIND (note) == REG_INC)
3584	no_equiv (XEXP (note, 0), store: note, NULL);
3585
3586	set = single_set (insn);
3587
3588	/* If this insn contains more (or less) than a single SET,
3589	only mark all destinations as having no known equivalence. */
3590	if (set == NULL_RTX
3591	|| side_effects_p (SET_SRC (set)))
3592	{
3593	note_pattern_stores (PATTERN (insn), no_equiv, NULL);
3594	continue;
3595	}
3596	else if (GET_CODE (PATTERN (insn)) == PARALLEL)
3597	{
3598	int i;
3599
3600	for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
3601	{
3602	rtx part = XVECEXP (PATTERN (insn), 0, i);
3603	if (part != set)
3604	note_pattern_stores (part, no_equiv, NULL);
3605	}
3606	}
3607
3608	dest = SET_DEST (set);
3609	src = SET_SRC (set);
3610
3611	/* See if this is setting up the equivalence between an argument
3612	register and its stack slot. */
3613	note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
3614	if (note)
3615	{
3616	gcc_assert (REG_P (dest));
3617	regno = REGNO (dest);
3618
3619	/* Note that we don't want to clear init_insns in
3620	ira_reg_equiv even if there are multiple sets of this
3621	register. */
3622	reg_equiv[regno].is_arg_equivalence = 1;
3623
3624	/* The insn result can have equivalence memory although
3625	the equivalence is not set up by the insn. We add
3626	this insn to init insns as it is a flag for now that
3627	regno has an equivalence. We will remove the insn
3628	from init insn list later. */
3629	if (rtx_equal_p (src, XEXP (note, 0)) || MEM_P (XEXP (note, 0)))
3630	ira_reg_equiv[regno].init_insns
3631	= gen_rtx_INSN_LIST (VOIDmode, insn,
3632	ira_reg_equiv[regno].init_insns);
3633
3634	/* Continue normally in case this is a candidate for
3635	replacements. */
3636	}
3637
3638	if (!optimize)
3639	continue;
3640
3641	/* We only handle the case of a pseudo register being set
3642	once, or always to the same value. */
3643	/* ??? The mn10200 port breaks if we add equivalences for
3644	values that need an ADDRESS_REGS register and set them equivalent
3645	to a MEM of a pseudo. The actual problem is in the over-conservative
3646	handling of INPADDR_ADDRESS / INPUT_ADDRESS / INPUT triples in
3647	calculate_needs, but we traditionally work around this problem
3648	here by rejecting equivalences when the destination is in a register
3649	that's likely spilled. This is fragile, of course, since the
3650	preferred class of a pseudo depends on all instructions that set
3651	or use it. */
3652
3653	if (!REG_P (dest)
3654	|| (regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER
3655	|| (reg_equiv[regno].init_insns
3656	&& reg_equiv[regno].init_insns->insn () == NULL)
3657	|| (targetm.class_likely_spilled_p (reg_preferred_class (regno))
3658	&& MEM_P (src) && ! reg_equiv[regno].is_arg_equivalence))
3659	{
3660	/* This might be setting a SUBREG of a pseudo, a pseudo that is
3661	also set somewhere else to a constant. */
3662	note_pattern_stores (set, no_equiv, NULL);
3663	continue;
3664	}
3665
3666	/* Don't set reg mentioned in a paradoxical subreg
3667	equivalent to a mem. */
3668	if (MEM_P (src) && reg_equiv[regno].pdx_subregs)
3669	{
3670	note_pattern_stores (set, no_equiv, NULL);
3671	continue;
3672	}
3673
3674	note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
3675
3676	/* cse sometimes generates function invariants, but doesn't put a
3677	REG_EQUAL note on the insn. Since this note would be redundant,
3678	there's no point creating it earlier than here. */
3679	if (! note && ! rtx_varies_p (src, 0))
3680	note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
3681
3682	/* Don't bother considering a REG_EQUAL note containing an EXPR_LIST
3683	since it represents a function call. */
3684	if (note && GET_CODE (XEXP (note, 0)) == EXPR_LIST)
3685	note = NULL_RTX;
3686
3687	if (DF_REG_DEF_COUNT (regno) != 1)
3688	{
3689	bool equal_p = true;
3690	rtx_insn_list *list;
3691
3692	/* If we have already processed this pseudo and determined it
3693	cannot have an equivalence, then honor that decision. */
3694	if (reg_equiv[regno].no_equiv)
3695	continue;
3696
3697	if (! note
3698	|| rtx_varies_p (XEXP (note, 0), 0)
3699	|| (reg_equiv[regno].replacement
3700	&& ! rtx_equal_p (XEXP (note, 0),
3701	reg_equiv[regno].replacement)))
3702	{
3703	no_equiv (reg: dest, store: set, NULL);
3704	continue;
3705	}
3706
3707	list = reg_equiv[regno].init_insns;
3708	for (; list; list = list->next ())
3709	{
3710	rtx note_tmp;
3711	rtx_insn *insn_tmp;
3712
3713	insn_tmp = list->insn ();
3714	note_tmp = find_reg_note (insn_tmp, REG_EQUAL, NULL_RTX);
3715	gcc_assert (note_tmp);
3716	if (! rtx_equal_p (XEXP (note, 0), XEXP (note_tmp, 0)))
3717	{
3718	equal_p = false;
3719	break;
3720	}
3721	}
3722
3723	if (! equal_p)
3724	{
3725	no_equiv (reg: dest, store: set, NULL);
3726	continue;
3727	}
3728	}
3729
3730	/* Record this insn as initializing this register. */
3731	reg_equiv[regno].init_insns
3732	= gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv[regno].init_insns);
3733
3734	/* If this register is known to be equal to a constant, record that
3735	it is always equivalent to the constant.
3736	Note that it is possible to have a register use before
3737	the def in loops (see gcc.c-torture/execute/pr79286.c)
3738	where the reg is undefined on first use. If the def insn
3739	won't trap we can use it as an equivalence, effectively
3740	choosing the "undefined" value for the reg to be the
3741	same as the value set by the def. */
3742	if (DF_REG_DEF_COUNT (regno) == 1
3743	&& note
3744	&& !rtx_varies_p (XEXP (note, 0), 0)
3745	&& (!may_trap_or_fault_p (XEXP (note, 0))
3746	|| def_dominates_uses (regno)))
3747	{
3748	rtx note_value = XEXP (note, 0);
3749	remove_note (insn, note);
3750	set_unique_reg_note (insn, REG_EQUIV, note_value);
3751	}
3752
3753	/* If this insn introduces a "constant" register, decrease the priority
3754	of that register. Record this insn if the register is only used once
3755	more and the equivalence value is the same as our source.
3756
3757	The latter condition is checked for two reasons: First, it is an
3758	indication that it may be more efficient to actually emit the insn
3759	as written (if no registers are available, reload will substitute
3760	the equivalence). Secondly, it avoids problems with any registers
3761	dying in this insn whose death notes would be missed.
3762
3763	If we don't have a REG_EQUIV note, see if this insn is loading
3764	a register used only in one basic block from a MEM. If so, and the
3765	MEM remains unchanged for the life of the register, add a REG_EQUIV
3766	note. */
3767	note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
3768
3769	rtx replacement = NULL_RTX;
3770	if (note)
3771	replacement = XEXP (note, 0);
3772	else if (REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
3773	&& MEM_P (SET_SRC (set)))
3774	{
3775	enum valid_equiv validity;
3776	validity = validate_equiv_mem (start: insn, reg: dest, SET_SRC (set));
3777	if (validity != valid_none)
3778	{
3779	replacement = copy_rtx (SET_SRC (set));
3780	if (validity == valid_reload)
3781	{
3782	note = set_unique_reg_note (insn, REG_EQUIV, replacement);
3783	}
3784	else if (ira_use_lra_p)
3785	{
3786	/* We still can use this equivalence for caller save
3787	optimization in LRA. Mark this. */
3788	ira_reg_equiv[regno].caller_save_p = true;
3789	ira_reg_equiv[regno].init_insns
3790	= gen_rtx_INSN_LIST (VOIDmode, insn,
3791	ira_reg_equiv[regno].init_insns);
3792	}
3793	}
3794	}
3795
3796	/* If we haven't done so, record for reload that this is an
3797	equivalencing insn. */
3798	if (note && !reg_equiv[regno].is_arg_equivalence)
3799	ira_reg_equiv[regno].init_insns
3800	= gen_rtx_INSN_LIST (VOIDmode, insn,
3801	ira_reg_equiv[regno].init_insns);
3802
3803	if (replacement)
3804	{
3805	reg_equiv[regno].replacement = replacement;
3806	reg_equiv[regno].src_p = &SET_SRC (set);
3807	reg_equiv[regno].loop_depth = (short) loop_depth;
3808
3809	/* Don't mess with things live during setjmp. */
3810	if (optimize && !bitmap_bit_p (setjmp_crosses, regno))
3811	{
3812	/* If the register is referenced exactly twice, meaning it is
3813	set once and used once, indicate that the reference may be
3814	replaced by the equivalence we computed above. Do this
3815	even if the register is only used in one block so that
3816	dependencies can be handled where the last register is
3817	used in a different block (i.e. HIGH / LO_SUM sequences)
3818	and to reduce the number of registers alive across
3819	calls. */
3820
3821	if (REG_N_REFS (regno) == 2
3822	&& (rtx_equal_p (replacement, src)
3823	|| ! equiv_init_varies_p (x: src))
3824	&& NONJUMP_INSN_P (insn)
3825	&& equiv_init_movable_p (x: PATTERN (insn), regno))
3826	reg_equiv[regno].replace = 1;
3827	}
3828	}
3829	}
3830	}
3831	}
3832
3833	/* For insns that set a MEM to the contents of a REG that is only used
3834	in a single basic block, see if the register is always equivalent
3835	to that memory location and if moving the store from INSN to the
3836	insn that sets REG is safe. If so, put a REG_EQUIV note on the
3837	initializing insn. */
3838	static void
3839	add_store_equivs (void)
3840	{
3841	auto_bitmap seen_insns;
3842
3843	for (rtx_insn *insn = get_insns (); insn; insn = NEXT_INSN (insn))
3844	{
3845	rtx set, src, dest;
3846	unsigned regno;
3847	rtx_insn *init_insn;
3848
3849	bitmap_set_bit (seen_insns, INSN_UID (insn));
3850
3851	if (! INSN_P (insn))
3852	continue;
3853
3854	set = single_set (insn);
3855	if (! set)
3856	continue;
3857
3858	dest = SET_DEST (set);
3859	src = SET_SRC (set);
3860
3861	/* Don't add a REG_EQUIV note if the insn already has one. The existing
3862	REG_EQUIV is likely more useful than the one we are adding. */
3863	if (MEM_P (dest) && REG_P (src)
3864	&& (regno = REGNO (src)) >= FIRST_PSEUDO_REGISTER
3865	&& REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
3866	&& DF_REG_DEF_COUNT (regno) == 1
3867	&& ! reg_equiv[regno].pdx_subregs
3868	&& reg_equiv[regno].init_insns != NULL
3869	&& (init_insn = reg_equiv[regno].init_insns->insn ()) != 0
3870	&& bitmap_bit_p (seen_insns, INSN_UID (insn: init_insn))
3871	&& ! find_reg_note (init_insn, REG_EQUIV, NULL_RTX)
3872	&& validate_equiv_mem (start: init_insn, reg: src, memref: dest) == valid_reload
3873	&& ! memref_used_between_p (memref: dest, start: init_insn, end: insn)
3874	/* Attaching a REG_EQUIV note will fail if INIT_INSN has
3875	multiple sets. */
3876	&& set_unique_reg_note (init_insn, REG_EQUIV, copy_rtx (dest)))
3877	{
3878	/* This insn makes the equivalence, not the one initializing
3879	the register. */
3880	ira_reg_equiv[regno].init_insns
3881	= gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX);
3882	df_notes_rescan (init_insn);
3883	if (dump_file)
3884	fprintf (stream: dump_file,
3885	format: "Adding REG_EQUIV to insn %d for source of insn %d\n",
3886	INSN_UID (insn: init_insn),
3887	INSN_UID (insn));
3888	}
3889	}
3890	}
3891
3892	/* Scan all regs killed in an insn to see if any of them are registers
3893	only used that once. If so, see if we can replace the reference
3894	with the equivalent form. If we can, delete the initializing
3895	reference and this register will go away. If we can't replace the
3896	reference, and the initializing reference is within the same loop
3897	(or in an inner loop), then move the register initialization just
3898	before the use, so that they are in the same basic block. */
3899	static void
3900	combine_and_move_insns (void)
3901	{
3902	auto_bitmap cleared_regs;
3903	int max = max_reg_num ();
3904
3905	for (int regno = FIRST_PSEUDO_REGISTER; regno < max; regno++)
3906	{
3907	if (!reg_equiv[regno].replace)
3908	continue;
3909
3910	rtx_insn *use_insn = 0;
3911	for (df_ref use = DF_REG_USE_CHAIN (regno);
3912	use;
3913	use = DF_REF_NEXT_REG (use))
3914	if (DF_REF_INSN_INFO (use))
3915	{
3916	if (DEBUG_INSN_P (DF_REF_INSN (use)))
3917	continue;
3918	gcc_assert (!use_insn);
3919	use_insn = DF_REF_INSN (use);
3920	}
3921	gcc_assert (use_insn);
3922
3923	/* Don't substitute into jumps. indirect_jump_optimize does
3924	this for anything we are prepared to handle. */
3925	if (JUMP_P (use_insn))
3926	continue;
3927
3928	/* Also don't substitute into a conditional trap insn -- it can become
3929	an unconditional trap, and that is a flow control insn. */
3930	if (GET_CODE (PATTERN (use_insn)) == TRAP_IF)
3931	continue;
3932
3933	df_ref def = DF_REG_DEF_CHAIN (regno);
3934	gcc_assert (DF_REG_DEF_COUNT (regno) == 1 && DF_REF_INSN_INFO (def));
3935	rtx_insn *def_insn = DF_REF_INSN (def);
3936
3937	/* We may not move instructions that can throw, since that
3938	changes basic block boundaries and we are not prepared to
3939	adjust the CFG to match. */
3940	if (can_throw_internal (def_insn))
3941	continue;
3942
3943	/* Instructions with multiple sets can only be moved if DF analysis is
3944	performed for all of the registers set. See PR91052. */
3945	if (multiple_sets (def_insn))
3946	continue;
3947
3948	basic_block use_bb = BLOCK_FOR_INSN (insn: use_insn);
3949	basic_block def_bb = BLOCK_FOR_INSN (insn: def_insn);
3950	if (bb_loop_depth (use_bb) > bb_loop_depth (def_bb))
3951	continue;
3952
3953	if (asm_noperands (PATTERN (insn: def_insn)) < 0
3954	&& validate_replace_rtx (regno_reg_rtx[regno],
3955	*reg_equiv[regno].src_p, use_insn))
3956	{
3957	rtx link;
3958	/* Append the REG_DEAD notes from def_insn. */
3959	for (rtx *p = &REG_NOTES (def_insn); (link = *p) != 0; )
3960	{
3961	if (REG_NOTE_KIND (XEXP (link, 0)) == REG_DEAD)
3962	{
3963	*p = XEXP (link, 1);
3964	XEXP (link, 1) = REG_NOTES (use_insn);
3965	REG_NOTES (use_insn) = link;
3966	}
3967	else
3968	p = &XEXP (link, 1);
3969	}
3970
3971	remove_death (regno, use_insn);
3972	SET_REG_N_REFS (regno, 0);
3973	REG_FREQ (regno) = 0;
3974	df_ref use;
3975	FOR_EACH_INSN_USE (use, def_insn)
3976	{
3977	unsigned int use_regno = DF_REF_REGNO (use);
3978	if (!HARD_REGISTER_NUM_P (use_regno))
3979	reg_equiv[use_regno].replace = 0;
3980	}
3981
3982	delete_insn (def_insn);
3983
3984	reg_equiv[regno].init_insns = NULL;
3985	ira_reg_equiv[regno].init_insns = NULL;
3986	bitmap_set_bit (cleared_regs, regno);
3987	}
3988
3989	/* Move the initialization of the register to just before
3990	USE_INSN. Update the flow information. */
3991	else if (prev_nondebug_insn (use_insn) != def_insn)
3992	{
3993	rtx_insn *new_insn;
3994
3995	new_insn = emit_insn_before (PATTERN (insn: def_insn), use_insn);
3996	REG_NOTES (new_insn) = REG_NOTES (def_insn);
3997	REG_NOTES (def_insn) = 0;
3998	/* Rescan it to process the notes. */
3999	df_insn_rescan (new_insn);
4000
4001	/* Make sure this insn is recognized before reload begins,
4002	otherwise eliminate_regs_in_insn will die. */
4003	INSN_CODE (new_insn) = INSN_CODE (def_insn);
4004
4005	delete_insn (def_insn);
4006
4007	XEXP (reg_equiv[regno].init_insns, 0) = new_insn;
4008
4009	REG_BASIC_BLOCK (regno) = use_bb->index;
4010	REG_N_CALLS_CROSSED (regno) = 0;
4011
4012	if (use_insn == BB_HEAD (use_bb))
4013	BB_HEAD (use_bb) = new_insn;
4014
4015	/* We know regno dies in use_insn, but inside a loop
4016	REG_DEAD notes might be missing when def_insn was in
4017	another basic block. However, when we move def_insn into
4018	this bb we'll definitely get a REG_DEAD note and reload
4019	will see the death. It's possible that update_equiv_regs
4020	set up an equivalence referencing regno for a reg set by
4021	use_insn, when regno was seen as non-local. Now that
4022	regno is local to this block, and dies, such an
4023	equivalence is invalid. */
4024	if (find_reg_note (use_insn, REG_EQUIV, regno_reg_rtx[regno]))
4025	{
4026	rtx set = single_set (insn: use_insn);
4027	if (set && REG_P (SET_DEST (set)))
4028	no_equiv (SET_DEST (set), store: set, NULL);
4029	}
4030
4031	ira_reg_equiv[regno].init_insns
4032	= gen_rtx_INSN_LIST (VOIDmode, new_insn, NULL_RTX);
4033	bitmap_set_bit (cleared_regs, regno);
4034	}
4035	}
4036
4037	if (!bitmap_empty_p (map: cleared_regs))
4038	{
4039	basic_block bb;
4040
4041	FOR_EACH_BB_FN (bb, cfun)
4042	{
4043	bitmap_and_compl_into (DF_LR_IN (bb), cleared_regs);
4044	bitmap_and_compl_into (DF_LR_OUT (bb), cleared_regs);
4045	if (!df_live)
4046	continue;
4047	bitmap_and_compl_into (DF_LIVE_IN (bb), cleared_regs);
4048	bitmap_and_compl_into (DF_LIVE_OUT (bb), cleared_regs);
4049	}
4050
4051	/* Last pass - adjust debug insns referencing cleared regs. */
4052	if (MAY_HAVE_DEBUG_BIND_INSNS)
4053	for (rtx_insn *insn = get_insns (); insn; insn = NEXT_INSN (insn))
4054	if (DEBUG_BIND_INSN_P (insn))
4055	{
4056	rtx old_loc = INSN_VAR_LOCATION_LOC (insn);
4057	INSN_VAR_LOCATION_LOC (insn)
4058	= simplify_replace_fn_rtx (old_loc, NULL_RTX,
4059	fn: adjust_cleared_regs,
4060	(void *) cleared_regs);
4061	if (old_loc != INSN_VAR_LOCATION_LOC (insn))
4062	df_insn_rescan (insn);
4063	}
4064	}
4065	}
4066
4067	/* A pass over indirect jumps, converting simple cases to direct jumps.
4068	Combine does this optimization too, but only within a basic block. */
4069	static void
4070	indirect_jump_optimize (void)
4071	{
4072	basic_block bb;
4073	bool rebuild_p = false;
4074
4075	FOR_EACH_BB_REVERSE_FN (bb, cfun)
4076	{
4077	rtx_insn *insn = BB_END (bb);
4078	if (!JUMP_P (insn)
4079	|| find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
4080	continue;
4081
4082	rtx x = pc_set (insn);
4083	if (!x || !REG_P (SET_SRC (x)))
4084	continue;
4085
4086	int regno = REGNO (SET_SRC (x));
4087	if (DF_REG_DEF_COUNT (regno) == 1)
4088	{
4089	df_ref def = DF_REG_DEF_CHAIN (regno);
4090	if (!DF_REF_IS_ARTIFICIAL (def))
4091	{
4092	rtx_insn *def_insn = DF_REF_INSN (def);
4093	rtx lab = NULL_RTX;
4094	rtx set = single_set (insn: def_insn);
4095	if (set && GET_CODE (SET_SRC (set)) == LABEL_REF)
4096	lab = SET_SRC (set);
4097	else
4098	{
4099	rtx eqnote = find_reg_note (def_insn, REG_EQUAL, NULL_RTX);
4100	if (eqnote && GET_CODE (XEXP (eqnote, 0)) == LABEL_REF)
4101	lab = XEXP (eqnote, 0);
4102	}
4103	if (lab && validate_replace_rtx (SET_SRC (x), lab, insn))
4104	rebuild_p = true;
4105	}
4106	}
4107	}
4108
4109	if (rebuild_p)
4110	{
4111	timevar_push (tv: TV_JUMP);
4112	rebuild_jump_labels (get_insns ());
4113	if (purge_all_dead_edges ())
4114	delete_unreachable_blocks ();
4115	timevar_pop (tv: TV_JUMP);
4116	}
4117	}
4118
4119	/* Set up fields memory, constant, and invariant from init_insns in
4120	the structures of array ira_reg_equiv. */
4121	static void
4122	setup_reg_equiv (void)
4123	{
4124	int i;
4125	rtx_insn_list *elem, *prev_elem, *next_elem;
4126	rtx_insn *insn;
4127	rtx set, x;
4128
4129	for (i = FIRST_PSEUDO_REGISTER; i < ira_reg_equiv_len; i++)
4130	for (prev_elem = NULL, elem = ira_reg_equiv[i].init_insns;
4131	elem;
4132	prev_elem = elem, elem = next_elem)
4133	{
4134	next_elem = elem->next ();
4135	insn = elem->insn ();
4136	set = single_set (insn);
4137
4138	/* Init insns can set up equivalence when the reg is a destination or
4139	a source (in this case the destination is memory). */
4140	if (set != 0 && (REG_P (SET_DEST (set)) || REG_P (SET_SRC (set))))
4141	{
4142	if ((x = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != NULL)
4143	{
4144	x = XEXP (x, 0);
4145	if (REG_P (SET_DEST (set))
4146	&& REGNO (SET_DEST (set)) == (unsigned int) i
4147	&& ! rtx_equal_p (SET_SRC (set), x) && MEM_P (x))
4148	{
4149	/* This insn reporting the equivalence but
4150	actually not setting it. Remove it from the
4151	list. */
4152	if (prev_elem == NULL)
4153	ira_reg_equiv[i].init_insns = next_elem;
4154	else
4155	XEXP (prev_elem, 1) = next_elem;
4156	elem = prev_elem;
4157	}
4158	}
4159	else if (REG_P (SET_DEST (set))
4160	&& REGNO (SET_DEST (set)) == (unsigned int) i)
4161	x = SET_SRC (set);
4162	else
4163	{
4164	gcc_assert (REG_P (SET_SRC (set))
4165	&& REGNO (SET_SRC (set)) == (unsigned int) i);
4166	x = SET_DEST (set);
4167	}
4168	if (! function_invariant_p (x)
4169	|| ! flag_pic
4170	/* A function invariant is often CONSTANT_P but may
4171	include a register. We promise to only pass
4172	CONSTANT_P objects to LEGITIMATE_PIC_OPERAND_P. */
4173	|| (CONSTANT_P (x) && LEGITIMATE_PIC_OPERAND_P (x)))
4174	{
4175	/* It can happen that a REG_EQUIV note contains a MEM
4176	that is not a legitimate memory operand. As later
4177	stages of reload assume that all addresses found in
4178	the lra_regno_equiv_* arrays were originally
4179	legitimate, we ignore such REG_EQUIV notes. */
4180	if (memory_operand (x, VOIDmode))
4181	{
4182	ira_reg_equiv[i].defined_p = !ira_reg_equiv[i].caller_save_p;
4183	ira_reg_equiv[i].memory = x;
4184	continue;
4185	}
4186	else if (function_invariant_p (x))
4187	{
4188	machine_mode mode;
4189
4190	mode = GET_MODE (SET_DEST (set));
4191	if (GET_CODE (x) == PLUS
4192	|| x == frame_pointer_rtx || x == arg_pointer_rtx)
4193	/* This is PLUS of frame pointer and a constant,
4194	or fp, or argp. */
4195	ira_reg_equiv[i].invariant = x;
4196	else if (targetm.legitimate_constant_p (mode, x))
4197	ira_reg_equiv[i].constant = x;
4198	else
4199	{
4200	ira_reg_equiv[i].memory = force_const_mem (mode, x);
4201	if (ira_reg_equiv[i].memory == NULL_RTX)
4202	{
4203	ira_reg_equiv[i].defined_p = false;
4204	ira_reg_equiv[i].caller_save_p = false;
4205	ira_reg_equiv[i].init_insns = NULL;
4206	break;
4207	}
4208	}
4209	ira_reg_equiv[i].defined_p = true;
4210	continue;
4211	}
4212	}
4213	}
4214	ira_reg_equiv[i].defined_p = false;
4215	ira_reg_equiv[i].caller_save_p = false;
4216	ira_reg_equiv[i].init_insns = NULL;
4217	break;
4218	}
4219	}
4220
4221
4222
4223	/* Print chain C to FILE. */
4224	static void
4225	print_insn_chain (FILE *file, class insn_chain *c)
4226	{
4227	fprintf (stream: file, format: "insn=%d, ", INSN_UID (insn: c->insn));
4228	bitmap_print (file, &c->live_throughout, "live_throughout: ", ", ");
4229	bitmap_print (file, &c->dead_or_set, "dead_or_set: ", "\n");
4230	}
4231
4232
4233	/* Print all reload_insn_chains to FILE. */
4234	static void
4235	print_insn_chains (FILE *file)
4236	{
4237	class insn_chain *c;
4238	for (c = reload_insn_chain; c ; c = c->next)
4239	print_insn_chain (file, c);
4240	}
4241
4242	/* Return true if pseudo REGNO should be added to set live_throughout
4243	or dead_or_set of the insn chains for reload consideration. */
4244	static bool
4245	pseudo_for_reload_consideration_p (int regno)
4246	{
4247	/* Consider spilled pseudos too for IRA because they still have a
4248	chance to get hard-registers in the reload when IRA is used. */
4249	return (reg_renumber[regno] >= 0 || ira_conflicts_p);
4250	}
4251
4252	/* Return true if we can track the individual bytes of subreg X.
4253	When returning true, set *OUTER_SIZE to the number of bytes in
4254	X itself, *INNER_SIZE to the number of bytes in the inner register
4255	and *START to the offset of the first byte. */
4256	static bool
4257	get_subreg_tracking_sizes (rtx x, HOST_WIDE_INT *outer_size,
4258	HOST_WIDE_INT *inner_size, HOST_WIDE_INT *start)
4259	{
4260	rtx reg = regno_reg_rtx[REGNO (SUBREG_REG (x))];
4261	return (GET_MODE_SIZE (GET_MODE (x)).is_constant (const_value: outer_size)
4262	&& GET_MODE_SIZE (GET_MODE (reg)).is_constant (const_value: inner_size)
4263	&& SUBREG_BYTE (x).is_constant (const_value: start));
4264	}
4265
4266	/* Init LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM] for
4267	a register with SIZE bytes, making the register live if INIT_VALUE. */
4268	static void
4269	init_live_subregs (bool init_value, sbitmap *live_subregs,
4270	bitmap live_subregs_used, int allocnum, int size)
4271	{
4272	gcc_assert (size > 0);
4273
4274	/* Been there, done that. */
4275	if (bitmap_bit_p (live_subregs_used, allocnum))
4276	return;
4277
4278	/* Create a new one. */
4279	if (live_subregs[allocnum] == NULL)
4280	live_subregs[allocnum] = sbitmap_alloc (size);
4281
4282	/* If the entire reg was live before blasting into subregs, we need
4283	to init all of the subregs to ones else init to 0. */
4284	if (init_value)
4285	bitmap_ones (live_subregs[allocnum]);
4286	else
4287	bitmap_clear (live_subregs[allocnum]);
4288
4289	bitmap_set_bit (live_subregs_used, allocnum);
4290	}
4291
4292	/* Walk the insns of the current function and build reload_insn_chain,
4293	and record register life information. */
4294	static void
4295	build_insn_chain (void)
4296	{
4297	unsigned int i;
4298	class insn_chain **p = &reload_insn_chain;
4299	basic_block bb;
4300	class insn_chain *c = NULL;
4301	class insn_chain *next = NULL;
4302	auto_bitmap live_relevant_regs;
4303	auto_bitmap elim_regset;
4304	/* live_subregs is a vector used to keep accurate information about
4305	which hardregs are live in multiword pseudos. live_subregs and
4306	live_subregs_used are indexed by pseudo number. The live_subreg
4307	entry for a particular pseudo is only used if the corresponding
4308	element is non zero in live_subregs_used. The sbitmap size of
4309	live_subreg[allocno] is number of bytes that the pseudo can
4310	occupy. */
4311	sbitmap *live_subregs = XCNEWVEC (sbitmap, max_regno);
4312	auto_bitmap live_subregs_used;
4313
4314	for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
4315	if (TEST_HARD_REG_BIT (set: eliminable_regset, bit: i))
4316	bitmap_set_bit (elim_regset, i);
4317	FOR_EACH_BB_REVERSE_FN (bb, cfun)
4318	{
4319	bitmap_iterator bi;
4320	rtx_insn *insn;
4321
4322	CLEAR_REG_SET (live_relevant_regs);
4323	bitmap_clear (live_subregs_used);
4324
4325	EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb), 0, i, bi)
4326	{
4327	if (i >= FIRST_PSEUDO_REGISTER)
4328	break;
4329	bitmap_set_bit (live_relevant_regs, i);
4330	}
4331
4332	EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb),
4333	FIRST_PSEUDO_REGISTER, i, bi)
4334	{
4335	if (pseudo_for_reload_consideration_p (regno: i))
4336	bitmap_set_bit (live_relevant_regs, i);
4337	}
4338
4339	FOR_BB_INSNS_REVERSE (bb, insn)
4340	{
4341	if (!NOTE_P (insn) && !BARRIER_P (insn))
4342	{
4343	struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4344	df_ref def, use;
4345
4346	c = new_insn_chain ();
4347	c->next = next;
4348	next = c;
4349	*p = c;
4350	p = &c->prev;
4351
4352	c->insn = insn;
4353	c->block = bb->index;
4354
4355	if (NONDEBUG_INSN_P (insn))
4356	FOR_EACH_INSN_INFO_DEF (def, insn_info)
4357	{
4358	unsigned int regno = DF_REF_REGNO (def);
4359
4360	/* Ignore may clobbers because these are generated
4361	from calls. However, every other kind of def is
4362	added to dead_or_set. */
4363	if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
4364	{
4365	if (regno < FIRST_PSEUDO_REGISTER)
4366	{
4367	if (!fixed_regs[regno])
4368	bitmap_set_bit (&c->dead_or_set, regno);
4369	}
4370	else if (pseudo_for_reload_consideration_p (regno))
4371	bitmap_set_bit (&c->dead_or_set, regno);
4372	}
4373
4374	if ((regno < FIRST_PSEUDO_REGISTER
4375	|| reg_renumber[regno] >= 0
4376	|| ira_conflicts_p)
4377	&& (!DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)))
4378	{
4379	rtx reg = DF_REF_REG (def);
4380	HOST_WIDE_INT outer_size, inner_size, start;
4381
4382	/* We can usually track the liveness of individual
4383	bytes within a subreg. The only exceptions are
4384	subregs wrapped in ZERO_EXTRACTs and subregs whose
4385	size is not known; in those cases we need to be
4386	conservative and treat the definition as a partial
4387	definition of the full register rather than a full
4388	definition of a specific part of the register. */
4389	if (GET_CODE (reg) == SUBREG
4390	&& !DF_REF_FLAGS_IS_SET (def, DF_REF_ZERO_EXTRACT)
4391	&& get_subreg_tracking_sizes (x: reg, outer_size: &outer_size,
4392	inner_size: &inner_size, start: &start))
4393	{
4394	HOST_WIDE_INT last = start + outer_size;
4395
4396	init_live_subregs
4397	(init_value: bitmap_bit_p (live_relevant_regs, regno),
4398	live_subregs, live_subregs_used, allocnum: regno,
4399	size: inner_size);
4400
4401	if (!DF_REF_FLAGS_IS_SET
4402	(def, DF_REF_STRICT_LOW_PART))
4403	{
4404	/* Expand the range to cover entire words.
4405	Bytes added here are "don't care". */
4406	start
4407	= start / UNITS_PER_WORD * UNITS_PER_WORD;
4408	last = ((last + UNITS_PER_WORD - 1)
4409	/ UNITS_PER_WORD * UNITS_PER_WORD);
4410	}
4411
4412	/* Ignore the paradoxical bits. */
4413	if (last > SBITMAP_SIZE (live_subregs[regno]))
4414	last = SBITMAP_SIZE (live_subregs[regno]);
4415
4416	while (start < last)
4417	{
4418	bitmap_clear_bit (map: live_subregs[regno], bitno: start);
4419	start++;
4420	}
4421
4422	if (bitmap_empty_p (live_subregs[regno]))
4423	{
4424	bitmap_clear_bit (live_subregs_used, regno);
4425	bitmap_clear_bit (live_relevant_regs, regno);
4426	}
4427	else
4428	/* Set live_relevant_regs here because
4429	that bit has to be true to get us to
4430	look at the live_subregs fields. */
4431	bitmap_set_bit (live_relevant_regs, regno);
4432	}
4433	else
4434	{
4435	/* DF_REF_PARTIAL is generated for
4436	subregs, STRICT_LOW_PART, and
4437	ZERO_EXTRACT. We handle the subreg
4438	case above so here we have to keep from
4439	modeling the def as a killing def. */
4440	if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL))
4441	{
4442	bitmap_clear_bit (live_subregs_used, regno);
4443	bitmap_clear_bit (live_relevant_regs, regno);
4444	}
4445	}
4446	}
4447	}
4448
4449	bitmap_and_compl_into (live_relevant_regs, elim_regset);
4450	bitmap_copy (&c->live_throughout, live_relevant_regs);
4451
4452	if (NONDEBUG_INSN_P (insn))
4453	FOR_EACH_INSN_INFO_USE (use, insn_info)
4454	{
4455	unsigned int regno = DF_REF_REGNO (use);
4456	rtx reg = DF_REF_REG (use);
4457
4458	/* DF_REF_READ_WRITE on a use means that this use
4459	is fabricated from a def that is a partial set
4460	to a multiword reg. Here, we only model the
4461	subreg case that is not wrapped in ZERO_EXTRACT
4462	precisely so we do not need to look at the
4463	fabricated use. */
4464	if (DF_REF_FLAGS_IS_SET (use, DF_REF_READ_WRITE)
4465	&& !DF_REF_FLAGS_IS_SET (use, DF_REF_ZERO_EXTRACT)
4466	&& DF_REF_FLAGS_IS_SET (use, DF_REF_SUBREG))
4467	continue;
4468
4469	/* Add the last use of each var to dead_or_set. */
4470	if (!bitmap_bit_p (live_relevant_regs, regno))
4471	{
4472	if (regno < FIRST_PSEUDO_REGISTER)
4473	{
4474	if (!fixed_regs[regno])
4475	bitmap_set_bit (&c->dead_or_set, regno);
4476	}
4477	else if (pseudo_for_reload_consideration_p (regno))
4478	bitmap_set_bit (&c->dead_or_set, regno);
4479	}
4480
4481	if (regno < FIRST_PSEUDO_REGISTER
4482	|| pseudo_for_reload_consideration_p (regno))
4483	{
4484	HOST_WIDE_INT outer_size, inner_size, start;
4485	if (GET_CODE (reg) == SUBREG
4486	&& !DF_REF_FLAGS_IS_SET (use,
4487	DF_REF_SIGN_EXTRACT
4488	| DF_REF_ZERO_EXTRACT)
4489	&& get_subreg_tracking_sizes (x: reg, outer_size: &outer_size,
4490	inner_size: &inner_size, start: &start))
4491	{
4492	HOST_WIDE_INT last = start + outer_size;
4493
4494	init_live_subregs
4495	(init_value: bitmap_bit_p (live_relevant_regs, regno),
4496	live_subregs, live_subregs_used, allocnum: regno,
4497	size: inner_size);
4498
4499	/* Ignore the paradoxical bits. */
4500	if (last > SBITMAP_SIZE (live_subregs[regno]))
4501	last = SBITMAP_SIZE (live_subregs[regno]);
4502
4503	while (start < last)
4504	{
4505	bitmap_set_bit (map: live_subregs[regno], bitno: start);
4506	start++;
4507	}
4508	}
4509	else
4510	/* Resetting the live_subregs_used is
4511	effectively saying do not use the subregs
4512	because we are reading the whole
4513	pseudo. */
4514	bitmap_clear_bit (live_subregs_used, regno);
4515	bitmap_set_bit (live_relevant_regs, regno);
4516	}
4517	}
4518	}
4519	}
4520
4521	/* FIXME!! The following code is a disaster. Reload needs to see the
4522	labels and jump tables that are just hanging out in between
4523	the basic blocks. See pr33676. */
4524	insn = BB_HEAD (bb);
4525
4526	/* Skip over the barriers and cruft. */
4527	while (insn && (BARRIER_P (insn) || NOTE_P (insn)
4528	|| BLOCK_FOR_INSN (insn) == bb))
4529	insn = PREV_INSN (insn);
4530
4531	/* While we add anything except barriers and notes, the focus is
4532	to get the labels and jump tables into the
4533	reload_insn_chain. */
4534	while (insn)
4535	{
4536	if (!NOTE_P (insn) && !BARRIER_P (insn))
4537	{
4538	if (BLOCK_FOR_INSN (insn))
4539	break;
4540
4541	c = new_insn_chain ();
4542	c->next = next;
4543	next = c;
4544	*p = c;
4545	p = &c->prev;
4546
4547	/* The block makes no sense here, but it is what the old
4548	code did. */
4549	c->block = bb->index;
4550	c->insn = insn;
4551	bitmap_copy (&c->live_throughout, live_relevant_regs);
4552	}
4553	insn = PREV_INSN (insn);
4554	}
4555	}
4556
4557	reload_insn_chain = c;
4558	*p = NULL;
4559
4560	for (i = 0; i < (unsigned int) max_regno; i++)
4561	if (live_subregs[i] != NULL)
4562	sbitmap_free (map: live_subregs[i]);
4563	free (ptr: live_subregs);
4564
4565	if (dump_file)
4566	print_insn_chains (file: dump_file);
4567	}
4568
4569	/* Examine the rtx found in *LOC, which is read or written to as determined
4570	by TYPE. Return false if we find a reason why an insn containing this
4571	rtx should not be moved (such as accesses to non-constant memory), true
4572	otherwise. */
4573	static bool
4574	rtx_moveable_p (rtx *loc, enum op_type type)
4575	{
4576	const char *fmt;
4577	rtx x = *loc;
4578	int i, j;
4579
4580	enum rtx_code code = GET_CODE (x);
4581	switch (code)
4582	{
4583	case CONST:
4584	CASE_CONST_ANY:
4585	case SYMBOL_REF:
4586	case LABEL_REF:
4587	return true;
4588
4589	case PC:
4590	return type == OP_IN;
4591
4592	case REG:
4593	if (x == frame_pointer_rtx)
4594	return true;
4595	if (HARD_REGISTER_P (x))
4596	return false;
4597
4598	return true;
4599
4600	case MEM:
4601	if (type == OP_IN && MEM_READONLY_P (x))
4602	return rtx_moveable_p (loc: &XEXP (x, 0), type: OP_IN);
4603	return false;
4604
4605	case SET:
4606	return (rtx_moveable_p (loc: &SET_SRC (x), type: OP_IN)
4607	&& rtx_moveable_p (loc: &SET_DEST (x), type: OP_OUT));
4608
4609	case STRICT_LOW_PART:
4610	return rtx_moveable_p (loc: &XEXP (x, 0), type: OP_OUT);
4611
4612	case ZERO_EXTRACT:
4613	case SIGN_EXTRACT:
4614	return (rtx_moveable_p (loc: &XEXP (x, 0), type)
4615	&& rtx_moveable_p (loc: &XEXP (x, 1), type: OP_IN)
4616	&& rtx_moveable_p (loc: &XEXP (x, 2), type: OP_IN));
4617
4618	case CLOBBER:
4619	return rtx_moveable_p (loc: &SET_DEST (x), type: OP_OUT);
4620
4621	case UNSPEC_VOLATILE:
4622	/* It is a bad idea to consider insns with such rtl
4623	as moveable ones. The insn scheduler also considers them as barrier
4624	for a reason. */
4625	return false;
4626
4627	case ASM_OPERANDS:
4628	/* The same is true for volatile asm: it has unknown side effects, it
4629	cannot be moved at will. */
4630	if (MEM_VOLATILE_P (x))
4631	return false;
4632
4633	default:
4634	break;
4635	}
4636
4637	fmt = GET_RTX_FORMAT (code);
4638	for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4639	{
4640	if (fmt[i] == 'e')
4641	{
4642	if (!rtx_moveable_p (loc: &XEXP (x, i), type))
4643	return false;
4644	}
4645	else if (fmt[i] == 'E')
4646	for (j = XVECLEN (x, i) - 1; j >= 0; j--)
4647	{
4648	if (!rtx_moveable_p (loc: &XVECEXP (x, i, j), type))
4649	return false;
4650	}
4651	}
4652	return true;
4653	}
4654
4655	/* A wrapper around dominated_by_p, which uses the information in UID_LUID
4656	to give dominance relationships between two insns I1 and I2. */
4657	static bool
4658	insn_dominated_by_p (rtx i1, rtx i2, int *uid_luid)
4659	{
4660	basic_block bb1 = BLOCK_FOR_INSN (insn: i1);
4661	basic_block bb2 = BLOCK_FOR_INSN (insn: i2);
4662
4663	if (bb1 == bb2)
4664	return uid_luid[INSN_UID (insn: i2)] < uid_luid[INSN_UID (insn: i1)];
4665	return dominated_by_p (CDI_DOMINATORS, bb1, bb2);
4666	}
4667
4668	/* Record the range of register numbers added by find_moveable_pseudos. */
4669	int first_moveable_pseudo, last_moveable_pseudo;
4670
4671	/* These two vectors hold data for every register added by
4672	find_movable_pseudos, with index 0 holding data for the
4673	first_moveable_pseudo. */
4674	/* The original home register. */
4675	static vec<rtx> pseudo_replaced_reg;
4676
4677	/* Look for instances where we have an instruction that is known to increase
4678	register pressure, and whose result is not used immediately. If it is
4679	possible to move the instruction downwards to just before its first use,
4680	split its lifetime into two ranges. We create a new pseudo to compute the
4681	value, and emit a move instruction just before the first use. If, after
4682	register allocation, the new pseudo remains unallocated, the function
4683	move_unallocated_pseudos then deletes the move instruction and places
4684	the computation just before the first use.
4685
4686	Such a move is safe and profitable if all the input registers remain live
4687	and unchanged between the original computation and its first use. In such
4688	a situation, the computation is known to increase register pressure, and
4689	moving it is known to at least not worsen it.
4690
4691	We restrict moves to only those cases where a register remains unallocated,
4692	in order to avoid interfering too much with the instruction schedule. As
4693	an exception, we may move insns which only modify their input register
4694	(typically induction variables), as this increases the freedom for our
4695	intended transformation, and does not limit the second instruction
4696	scheduler pass. */
4697
4698	static void
4699	find_moveable_pseudos (void)
4700	{
4701	unsigned i;
4702	int max_regs = max_reg_num ();
4703	int max_uid = get_max_uid ();
4704	basic_block bb;
4705	int *uid_luid = XNEWVEC (int, max_uid);
4706	rtx_insn **closest_uses = XNEWVEC (rtx_insn *, max_regs);
4707	/* A set of registers which are live but not modified throughout a block. */
4708	bitmap_head *bb_transp_live = XNEWVEC (bitmap_head,
4709	last_basic_block_for_fn (cfun));
4710	/* A set of registers which only exist in a given basic block. */
4711	bitmap_head *bb_local = XNEWVEC (bitmap_head,
4712	last_basic_block_for_fn (cfun));
4713	/* A set of registers which are set once, in an instruction that can be
4714	moved freely downwards, but are otherwise transparent to a block. */
4715	bitmap_head *bb_moveable_reg_sets = XNEWVEC (bitmap_head,
4716	last_basic_block_for_fn (cfun));
4717	auto_bitmap live, used, set, interesting, unusable_as_input;
4718	bitmap_iterator bi;
4719
4720	first_moveable_pseudo = max_regs;
4721	pseudo_replaced_reg.release ();
4722	pseudo_replaced_reg.safe_grow_cleared (len: max_regs, exact: true);
4723
4724	df_analyze ();
4725	calculate_dominance_info (CDI_DOMINATORS);
4726
4727	i = 0;
4728	FOR_EACH_BB_FN (bb, cfun)
4729	{
4730	rtx_insn *insn;
4731	bitmap transp = bb_transp_live + bb->index;
4732	bitmap moveable = bb_moveable_reg_sets + bb->index;
4733	bitmap local = bb_local + bb->index;
4734
4735	bitmap_initialize (head: local, obstack: 0);
4736	bitmap_initialize (head: transp, obstack: 0);
4737	bitmap_initialize (head: moveable, obstack: 0);
4738	bitmap_copy (live, df_get_live_out (bb));
4739	bitmap_and_into (live, df_get_live_in (bb));
4740	bitmap_copy (transp, live);
4741	bitmap_clear (moveable);
4742	bitmap_clear (live);
4743	bitmap_clear (used);
4744	bitmap_clear (set);
4745	FOR_BB_INSNS (bb, insn)
4746	if (NONDEBUG_INSN_P (insn))
4747	{
4748	df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4749	df_ref def, use;
4750
4751	uid_luid[INSN_UID (insn)] = i++;
4752
4753	def = df_single_def (info: insn_info);
4754	use = df_single_use (info: insn_info);
4755	if (use
4756	&& def
4757	&& DF_REF_REGNO (use) == DF_REF_REGNO (def)
4758	&& !bitmap_bit_p (set, DF_REF_REGNO (use))
4759	&& rtx_moveable_p (loc: &PATTERN (insn), type: OP_IN))
4760	{
4761	unsigned regno = DF_REF_REGNO (use);
4762	bitmap_set_bit (moveable, regno);
4763	bitmap_set_bit (set, regno);
4764	bitmap_set_bit (used, regno);
4765	bitmap_clear_bit (transp, regno);
4766	continue;
4767	}
4768	FOR_EACH_INSN_INFO_USE (use, insn_info)
4769	{
4770	unsigned regno = DF_REF_REGNO (use);
4771	bitmap_set_bit (used, regno);
4772	if (bitmap_clear_bit (moveable, regno))
4773	bitmap_clear_bit (transp, regno);
4774	}
4775
4776	FOR_EACH_INSN_INFO_DEF (def, insn_info)
4777	{
4778	unsigned regno = DF_REF_REGNO (def);
4779	bitmap_set_bit (set, regno);
4780	bitmap_clear_bit (transp, regno);
4781	bitmap_clear_bit (moveable, regno);
4782	}
4783	}
4784	}
4785
4786	FOR_EACH_BB_FN (bb, cfun)
4787	{
4788	bitmap local = bb_local + bb->index;
4789	rtx_insn *insn;
4790
4791	FOR_BB_INSNS (bb, insn)
4792	if (NONDEBUG_INSN_P (insn))
4793	{
4794	df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
4795	rtx_insn *def_insn;
4796	rtx closest_use, note;
4797	df_ref def, use;
4798	unsigned regno;
4799	bool all_dominated, all_local;
4800	machine_mode mode;
4801
4802	def = df_single_def (info: insn_info);
4803	/* There must be exactly one def in this insn. */
4804	if (!def || !single_set (insn))
4805	continue;
4806	/* This must be the only definition of the reg. We also limit
4807	which modes we deal with so that we can assume we can generate
4808	move instructions. */
4809	regno = DF_REF_REGNO (def);
4810	mode = GET_MODE (DF_REF_REG (def));
4811	if (DF_REG_DEF_COUNT (regno) != 1
4812	|| !DF_REF_INSN_INFO (def)
4813	|| HARD_REGISTER_NUM_P (regno)
4814	|| DF_REG_EQ_USE_COUNT (regno) > 0
4815	|| (!INTEGRAL_MODE_P (mode)
4816	&& !FLOAT_MODE_P (mode)
4817	&& !OPAQUE_MODE_P (mode)))
4818	continue;
4819	def_insn = DF_REF_INSN (def);
4820
4821	for (note = REG_NOTES (def_insn); note; note = XEXP (note, 1))
4822	if (REG_NOTE_KIND (note) == REG_EQUIV && MEM_P (XEXP (note, 0)))
4823	break;
4824
4825	if (note)
4826	{
4827	if (dump_file)
4828	fprintf (stream: dump_file, format: "Ignoring reg %d, has equiv memory\n",
4829	regno);
4830	bitmap_set_bit (unusable_as_input, regno);
4831	continue;
4832	}
4833
4834	use = DF_REG_USE_CHAIN (regno);
4835	all_dominated = true;
4836	all_local = true;
4837	closest_use = NULL_RTX;
4838	for (; use; use = DF_REF_NEXT_REG (use))
4839	{
4840	rtx_insn *insn;
4841	if (!DF_REF_INSN_INFO (use))
4842	{
4843	all_dominated = false;
4844	all_local = false;
4845	break;
4846	}
4847	insn = DF_REF_INSN (use);
4848	if (DEBUG_INSN_P (insn))
4849	continue;
4850	if (BLOCK_FOR_INSN (insn) != BLOCK_FOR_INSN (insn: def_insn))
4851	all_local = false;
4852	if (!insn_dominated_by_p (i1: insn, i2: def_insn, uid_luid))
4853	all_dominated = false;
4854	if (closest_use != insn && closest_use != const0_rtx)
4855	{
4856	if (closest_use == NULL_RTX)
4857	closest_use = insn;
4858	else if (insn_dominated_by_p (i1: closest_use, i2: insn, uid_luid))
4859	closest_use = insn;
4860	else if (!insn_dominated_by_p (i1: insn, i2: closest_use, uid_luid))
4861	closest_use = const0_rtx;
4862	}
4863	}
4864	if (!all_dominated)
4865	{
4866	if (dump_file)
4867	fprintf (stream: dump_file, format: "Reg %d not all uses dominated by set\n",
4868	regno);
4869	continue;
4870	}
4871	if (all_local)
4872	bitmap_set_bit (local, regno);
4873	if (closest_use == const0_rtx || closest_use == NULL
4874	|| next_nonnote_nondebug_insn (def_insn) == closest_use)
4875	{
4876	if (dump_file)
4877	fprintf (stream: dump_file, format: "Reg %d uninteresting%s\n", regno,
4878	closest_use == const0_rtx || closest_use == NULL
4879	? " (no unique first use)" : "");
4880	continue;
4881	}
4882
4883	bitmap_set_bit (interesting, regno);
4884	/* If we get here, we know closest_use is a non-NULL insn
4885	(as opposed to const_0_rtx). */
4886	closest_uses[regno] = as_a <rtx_insn *> (p: closest_use);
4887
4888	if (dump_file && (all_local || all_dominated))
4889	{
4890	fprintf (stream: dump_file, format: "Reg %u:", regno);
4891	if (all_local)
4892	fprintf (stream: dump_file, format: " local to bb %d", bb->index);
4893	if (all_dominated)
4894	fprintf (stream: dump_file, format: " def dominates all uses");
4895	if (closest_use != const0_rtx)
4896	fprintf (stream: dump_file, format: " has unique first use");
4897	fputs (s: "\n", stream: dump_file);
4898	}
4899	}
4900	}
4901
4902	EXECUTE_IF_SET_IN_BITMAP (interesting, 0, i, bi)
4903	{
4904	df_ref def = DF_REG_DEF_CHAIN (i);
4905	rtx_insn *def_insn = DF_REF_INSN (def);
4906	basic_block def_block = BLOCK_FOR_INSN (insn: def_insn);
4907	bitmap def_bb_local = bb_local + def_block->index;
4908	bitmap def_bb_moveable = bb_moveable_reg_sets + def_block->index;
4909	bitmap def_bb_transp = bb_transp_live + def_block->index;
4910	bool local_to_bb_p = bitmap_bit_p (def_bb_local, i);
4911	rtx_insn *use_insn = closest_uses[i];
4912	df_ref use;
4913	bool all_ok = true;
4914	bool all_transp = true;
4915
4916	if (!REG_P (DF_REF_REG (def)))
4917	continue;
4918
4919	if (!local_to_bb_p)
4920	{
4921	if (dump_file)
4922	fprintf (stream: dump_file, format: "Reg %u not local to one basic block\n",
4923	i);
4924	continue;
4925	}
4926	if (reg_equiv_init (i) != NULL_RTX)
4927	{
4928	if (dump_file)
4929	fprintf (stream: dump_file, format: "Ignoring reg %u with equiv init insn\n",
4930	i);
4931	continue;
4932	}
4933	if (!rtx_moveable_p (loc: &PATTERN (insn: def_insn), type: OP_IN))
4934	{
4935	if (dump_file)
4936	fprintf (stream: dump_file, format: "Found def insn %d for %d to be not moveable\n",
4937	INSN_UID (insn: def_insn), i);
4938	continue;
4939	}
4940	if (dump_file)
4941	fprintf (stream: dump_file, format: "Examining insn %d, def for %d\n",
4942	INSN_UID (insn: def_insn), i);
4943	FOR_EACH_INSN_USE (use, def_insn)
4944	{
4945	unsigned regno = DF_REF_REGNO (use);
4946	if (bitmap_bit_p (unusable_as_input, regno))
4947	{
4948	all_ok = false;
4949	if (dump_file)
4950	fprintf (stream: dump_file, format: " found unusable input reg %u.\n", regno);
4951	break;
4952	}
4953	if (!bitmap_bit_p (def_bb_transp, regno))
4954	{
4955	if (bitmap_bit_p (def_bb_moveable, regno)
4956	&& !control_flow_insn_p (use_insn))
4957	{
4958	if (modified_between_p (DF_REF_REG (use), def_insn, use_insn))
4959	{
4960	rtx_insn *x = NEXT_INSN (insn: def_insn);
4961	while (!modified_in_p (DF_REF_REG (use), x))
4962	{
4963	gcc_assert (x != use_insn);
4964	x = NEXT_INSN (insn: x);
4965	}
4966	if (dump_file)
4967	fprintf (stream: dump_file, format: " input reg %u modified but insn %d moveable\n",
4968	regno, INSN_UID (insn: x));
4969	emit_insn_after (PATTERN (insn: x), use_insn);
4970	set_insn_deleted (x);
4971	}
4972	else
4973	{
4974	if (dump_file)
4975	fprintf (stream: dump_file, format: " input reg %u modified between def and use\n",
4976	regno);
4977	all_transp = false;
4978	}
4979	}
4980	else
4981	all_transp = false;
4982	}
4983	}
4984	if (!all_ok)
4985	continue;
4986	if (!dbg_cnt (index: ira_move))
4987	break;
4988	if (dump_file)
4989	fprintf (stream: dump_file, format: " all ok%s\n", all_transp ? " and transp" : "");
4990
4991	if (all_transp)
4992	{
4993	rtx def_reg = DF_REF_REG (def);
4994	rtx newreg = ira_create_new_reg (def_reg);
4995	if (validate_change (def_insn, DF_REF_REAL_LOC (def), newreg, 0))
4996	{
4997	unsigned nregno = REGNO (newreg);
4998	emit_insn_before (gen_move_insn (def_reg, newreg), use_insn);
4999	nregno -= max_regs;
5000	pseudo_replaced_reg[nregno] = def_reg;
5001	}
5002	}
5003	}
5004
5005	FOR_EACH_BB_FN (bb, cfun)
5006	{
5007	bitmap_clear (bb_local + bb->index);
5008	bitmap_clear (bb_transp_live + bb->index);
5009	bitmap_clear (bb_moveable_reg_sets + bb->index);
5010	}
5011	free (ptr: uid_luid);
5012	free (ptr: closest_uses);
5013	free (ptr: bb_local);
5014	free (ptr: bb_transp_live);
5015	free (ptr: bb_moveable_reg_sets);
5016
5017	last_moveable_pseudo = max_reg_num ();
5018
5019	fix_reg_equiv_init ();
5020	expand_reg_info ();
5021	regstat_free_n_sets_and_refs ();
5022	regstat_free_ri ();
5023	regstat_init_n_sets_and_refs ();
5024	regstat_compute_ri ();
5025	free_dominance_info (CDI_DOMINATORS);
5026	}
5027
5028	/* If SET pattern SET is an assignment from a hard register to a pseudo which
5029	is live at CALL_DOM (if non-NULL, otherwise this check is omitted), return
5030	the destination. Otherwise return NULL. */
5031
5032	static rtx
5033	interesting_dest_for_shprep_1 (rtx set, basic_block call_dom)
5034	{
5035	rtx src = SET_SRC (set);
5036	rtx dest = SET_DEST (set);
5037	if (!REG_P (src) || !HARD_REGISTER_P (src)
5038	|| !REG_P (dest) || HARD_REGISTER_P (dest)
5039	|| (call_dom && !bitmap_bit_p (df_get_live_in (bb: call_dom), REGNO (dest))))
5040	return NULL;
5041	return dest;
5042	}
5043
5044	/* If insn is interesting for parameter range-splitting shrink-wrapping
5045	preparation, i.e. it is a single set from a hard register to a pseudo, which
5046	is live at CALL_DOM (if non-NULL, otherwise this check is omitted), or a
5047	parallel statement with only one such statement, return the destination.
5048	Otherwise return NULL. */
5049
5050	static rtx
5051	interesting_dest_for_shprep (rtx_insn *insn, basic_block call_dom)
5052	{
5053	if (!INSN_P (insn))
5054	return NULL;
5055	rtx pat = PATTERN (insn);
5056	if (GET_CODE (pat) == SET)
5057	return interesting_dest_for_shprep_1 (set: pat, call_dom);
5058
5059	if (GET_CODE (pat) != PARALLEL)
5060	return NULL;
5061	rtx ret = NULL;
5062	for (int i = 0; i < XVECLEN (pat, 0); i++)
5063	{
5064	rtx sub = XVECEXP (pat, 0, i);
5065	if (GET_CODE (sub) == USE || GET_CODE (sub) == CLOBBER)
5066	continue;
5067	if (GET_CODE (sub) != SET
5068	|| side_effects_p (sub))
5069	return NULL;
5070	rtx dest = interesting_dest_for_shprep_1 (set: sub, call_dom);
5071	if (dest && ret)
5072	return NULL;
5073	if (dest)
5074	ret = dest;
5075	}
5076	return ret;
5077	}
5078
5079	/* Split live ranges of pseudos that are loaded from hard registers in the
5080	first BB in a BB that dominates all non-sibling call if such a BB can be
5081	found and is not in a loop. Return true if the function has made any
5082	changes. */
5083
5084	static bool
5085	split_live_ranges_for_shrink_wrap (void)
5086	{
5087	basic_block bb, call_dom = NULL;
5088	basic_block first = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
5089	rtx_insn *insn, *last_interesting_insn = NULL;
5090	auto_bitmap need_new, reachable;
5091	vec<basic_block> queue;
5092
5093	if (!SHRINK_WRAPPING_ENABLED)
5094	return false;
5095
5096	queue.create (n_basic_blocks_for_fn (cfun));
5097
5098	FOR_EACH_BB_FN (bb, cfun)
5099	FOR_BB_INSNS (bb, insn)
5100	if (CALL_P (insn) && !SIBLING_CALL_P (insn))
5101	{
5102	if (bb == first)
5103	{
5104	queue.release ();
5105	return false;
5106	}
5107
5108	bitmap_set_bit (need_new, bb->index);
5109	bitmap_set_bit (reachable, bb->index);
5110	queue.quick_push (obj: bb);
5111	break;
5112	}
5113
5114	if (queue.is_empty ())
5115	{
5116	queue.release ();
5117	return false;
5118	}
5119
5120	while (!queue.is_empty ())
5121	{
5122	edge e;
5123	edge_iterator ei;
5124
5125	bb = queue.pop ();
5126	FOR_EACH_EDGE (e, ei, bb->succs)
5127	if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
5128	&& bitmap_set_bit (reachable, e->dest->index))
5129	queue.quick_push (obj: e->dest);
5130	}
5131	queue.release ();
5132
5133	FOR_BB_INSNS (first, insn)
5134	{
5135	rtx dest = interesting_dest_for_shprep (insn, NULL);
5136	if (!dest)
5137	continue;
5138
5139	if (DF_REG_DEF_COUNT (REGNO (dest)) > 1)
5140	return false;
5141
5142	for (df_ref use = DF_REG_USE_CHAIN (REGNO(dest));
5143	use;
5144	use = DF_REF_NEXT_REG (use))
5145	{
5146	int ubbi = DF_REF_BB (use)->index;
5147	if (bitmap_bit_p (reachable, ubbi))
5148	bitmap_set_bit (need_new, ubbi);
5149	}
5150	last_interesting_insn = insn;
5151	}
5152
5153	if (!last_interesting_insn)
5154	return false;
5155
5156	call_dom = nearest_common_dominator_for_set (CDI_DOMINATORS, need_new);
5157	if (call_dom == first)
5158	return false;
5159
5160	loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
5161	while (bb_loop_depth (call_dom) > 0)
5162	call_dom = get_immediate_dominator (CDI_DOMINATORS, call_dom);
5163	loop_optimizer_finalize ();
5164
5165	if (call_dom == first)
5166	return false;
5167
5168	calculate_dominance_info (CDI_POST_DOMINATORS);
5169	if (dominated_by_p (CDI_POST_DOMINATORS, first, call_dom))
5170	{
5171	free_dominance_info (CDI_POST_DOMINATORS);
5172	return false;
5173	}
5174	free_dominance_info (CDI_POST_DOMINATORS);
5175
5176	if (dump_file)
5177	fprintf (stream: dump_file, format: "Will split live ranges of parameters at BB %i\n",
5178	call_dom->index);
5179
5180	bool ret = false;
5181	FOR_BB_INSNS (first, insn)
5182	{
5183	rtx dest = interesting_dest_for_shprep (insn, call_dom);
5184	if (!dest || dest == pic_offset_table_rtx)
5185	continue;
5186
5187	bool need_newreg = false;
5188	df_ref use, next;
5189	for (use = DF_REG_USE_CHAIN (REGNO (dest)); use; use = next)
5190	{
5191	rtx_insn *uin = DF_REF_INSN (use);
5192	next = DF_REF_NEXT_REG (use);
5193
5194	if (DEBUG_INSN_P (uin))
5195	continue;
5196
5197	basic_block ubb = BLOCK_FOR_INSN (insn: uin);
5198	if (ubb == call_dom
5199	|| dominated_by_p (CDI_DOMINATORS, ubb, call_dom))
5200	{
5201	need_newreg = true;
5202	break;
5203	}
5204	}
5205
5206	if (need_newreg)
5207	{
5208	rtx newreg = ira_create_new_reg (dest);
5209
5210	for (use = DF_REG_USE_CHAIN (REGNO (dest)); use; use = next)
5211	{
5212	rtx_insn *uin = DF_REF_INSN (use);
5213	next = DF_REF_NEXT_REG (use);
5214
5215	basic_block ubb = BLOCK_FOR_INSN (insn: uin);
5216	if (ubb == call_dom
5217	|| dominated_by_p (CDI_DOMINATORS, ubb, call_dom))
5218	validate_change (uin, DF_REF_REAL_LOC (use), newreg, true);
5219	}
5220
5221	rtx_insn *new_move = gen_move_insn (newreg, dest);
5222	emit_insn_after (new_move, bb_note (call_dom));
5223	if (dump_file)
5224	{
5225	fprintf (stream: dump_file, format: "Split live-range of register ");
5226	print_rtl_single (dump_file, dest);
5227	}
5228	ret = true;
5229	}
5230
5231	if (insn == last_interesting_insn)
5232	break;
5233	}
5234	apply_change_group ();
5235	return ret;
5236	}
5237
5238	/* Perform the second half of the transformation started in
5239	find_moveable_pseudos. We look for instances where the newly introduced
5240	pseudo remains unallocated, and remove it by moving the definition to
5241	just before its use, replacing the move instruction generated by
5242	find_moveable_pseudos. */
5243	static void
5244	move_unallocated_pseudos (void)
5245	{
5246	int i;
5247	for (i = first_moveable_pseudo; i < last_moveable_pseudo; i++)
5248	if (reg_renumber[i] < 0)
5249	{
5250	int idx = i - first_moveable_pseudo;
5251	rtx other_reg = pseudo_replaced_reg[idx];
5252	/* The iterating range [first_moveable_pseudo, last_moveable_pseudo)
5253	covers every new pseudo created in find_moveable_pseudos,
5254	regardless of the validation with it is successful or not.
5255	So we need to skip the pseudos which were used in those failed
5256	validations to avoid unexpected DF info and consequent ICE.
5257	We only set pseudo_replaced_reg[] when the validation is successful
5258	in find_moveable_pseudos, it's enough to check it here. */
5259	if (!other_reg)
5260	continue;
5261	rtx_insn *def_insn = DF_REF_INSN (DF_REG_DEF_CHAIN (i));
5262	/* The use must follow all definitions of OTHER_REG, so we can
5263	insert the new definition immediately after any of them. */
5264	df_ref other_def = DF_REG_DEF_CHAIN (REGNO (other_reg));
5265	rtx_insn *move_insn = DF_REF_INSN (other_def);
5266	rtx_insn *newinsn = emit_insn_after (PATTERN (insn: def_insn), move_insn);
5267	rtx set;
5268	int success;
5269
5270	if (dump_file)
5271	fprintf (stream: dump_file, format: "moving def of %d (insn %d now) ",
5272	REGNO (other_reg), INSN_UID (insn: def_insn));
5273
5274	delete_insn (move_insn);
5275	while ((other_def = DF_REG_DEF_CHAIN (REGNO (other_reg))))
5276	delete_insn (DF_REF_INSN (other_def));
5277	delete_insn (def_insn);
5278
5279	set = single_set (insn: newinsn);
5280	success = validate_change (newinsn, &SET_DEST (set), other_reg, 0);
5281	gcc_assert (success);
5282	if (dump_file)
5283	fprintf (stream: dump_file, format: " %d) rather than keep unallocated replacement %d\n",
5284	INSN_UID (insn: newinsn), i);
5285	SET_REG_N_REFS (i, 0);
5286	}
5287
5288	first_moveable_pseudo = last_moveable_pseudo = 0;
5289	}
5290
5291
5292
5293	/* Code dealing with scratches (changing them onto
5294	pseudos and restoring them from the pseudos).
5295
5296	We change scratches into pseudos at the beginning of IRA to
5297	simplify dealing with them (conflicts, hard register assignments).
5298
5299	If the pseudo denoting scratch was spilled it means that we do not
5300	need a hard register for it. Such pseudos are transformed back to
5301	scratches at the end of LRA. */
5302
5303	/* Description of location of a former scratch operand. */
5304	struct sloc
5305	{
5306	rtx_insn *insn; /* Insn where the scratch was. */
5307	int nop; /* Number of the operand which was a scratch. */
5308	unsigned regno; /* regno gnerated instead of scratch */
5309	int icode; /* Original icode from which scratch was removed. */
5310	};
5311
5312	typedef struct sloc *sloc_t;
5313
5314	/* Locations of the former scratches. */
5315	static vec<sloc_t> scratches;
5316
5317	/* Bitmap of scratch regnos. */
5318	static bitmap_head scratch_bitmap;
5319
5320	/* Bitmap of scratch operands. */
5321	static bitmap_head scratch_operand_bitmap;
5322
5323	/* Return true if pseudo REGNO is made of SCRATCH. */
5324	bool
5325	ira_former_scratch_p (int regno)
5326	{
5327	return bitmap_bit_p (&scratch_bitmap, regno);
5328	}
5329
5330	/* Return true if the operand NOP of INSN is a former scratch. */
5331	bool
5332	ira_former_scratch_operand_p (rtx_insn *insn, int nop)
5333	{
5334	return bitmap_bit_p (&scratch_operand_bitmap,
5335	INSN_UID (insn) * MAX_RECOG_OPERANDS + nop) != 0;
5336	}
5337
5338	/* Register operand NOP in INSN as a former scratch. It will be
5339	changed to scratch back, if it is necessary, at the LRA end. */
5340	void
5341	ira_register_new_scratch_op (rtx_insn *insn, int nop, int icode)
5342	{
5343	rtx op = *recog_data.operand_loc[nop];
5344	sloc_t loc = XNEW (struct sloc);
5345	ira_assert (REG_P (op));
5346	loc->insn = insn;
5347	loc->nop = nop;
5348	loc->regno = REGNO (op);
5349	loc->icode = icode;
5350	scratches.safe_push (obj: loc);
5351	bitmap_set_bit (&scratch_bitmap, REGNO (op));
5352	bitmap_set_bit (&scratch_operand_bitmap,
5353	INSN_UID (insn) * MAX_RECOG_OPERANDS + nop);
5354	add_reg_note (insn, REG_UNUSED, op);
5355	}
5356
5357	/* Return true if string STR contains constraint 'X'. */
5358	static bool
5359	contains_X_constraint_p (const char *str)
5360	{
5361	int c;
5362
5363	while ((c = *str))
5364	{
5365	str += CONSTRAINT_LEN (c, str);
5366	if (c == 'X') return true;
5367	}
5368	return false;
5369	}
5370
5371	/* Change INSN's scratches into pseudos and save their location.
5372	Return true if we changed any scratch. */
5373	bool
5374	ira_remove_insn_scratches (rtx_insn *insn, bool all_p, FILE *dump_file,
5375	rtx (*get_reg) (rtx original))
5376	{
5377	int i;
5378	bool insn_changed_p;
5379	rtx reg, *loc;
5380
5381	extract_insn (insn);
5382	insn_changed_p = false;
5383	for (i = 0; i < recog_data.n_operands; i++)
5384	{
5385	loc = recog_data.operand_loc[i];
5386	if (GET_CODE (*loc) == SCRATCH && GET_MODE (*loc) != VOIDmode)
5387	{
5388	if (! all_p && contains_X_constraint_p (str: recog_data.constraints[i]))
5389	continue;
5390	insn_changed_p = true;
5391	*loc = reg = get_reg (*loc);
5392	ira_register_new_scratch_op (insn, nop: i, INSN_CODE (insn));
5393	if (ira_dump_file != NULL)
5394	fprintf (stream: dump_file,
5395	format: "Removing SCRATCH to p%u in insn #%u (nop %d)\n",
5396	REGNO (reg), INSN_UID (insn), i);
5397	}
5398	}
5399	return insn_changed_p;
5400	}
5401
5402	/* Return new register of the same mode as ORIGINAL. Used in
5403	remove_scratches. */
5404	static rtx
5405	get_scratch_reg (rtx original)
5406	{
5407	return gen_reg_rtx (GET_MODE (original));
5408	}
5409
5410	/* Change scratches into pseudos and save their location. Return true
5411	if we changed any scratch. */
5412	static bool
5413	remove_scratches (void)
5414	{
5415	bool change_p = false;
5416	basic_block bb;
5417	rtx_insn *insn;
5418
5419	scratches.create (nelems: get_max_uid ());
5420	bitmap_initialize (head: &scratch_bitmap, obstack: &reg_obstack);
5421	bitmap_initialize (head: &scratch_operand_bitmap, obstack: &reg_obstack);
5422	FOR_EACH_BB_FN (bb, cfun)
5423	FOR_BB_INSNS (bb, insn)
5424	if (INSN_P (insn)
5425	&& ira_remove_insn_scratches (insn, all_p: false, dump_file: ira_dump_file, get_reg: get_scratch_reg))
5426	{
5427	/* Because we might use DF, we need to keep DF info up to date. */
5428	df_insn_rescan (insn);
5429	change_p = true;
5430	}
5431	return change_p;
5432	}
5433
5434	/* Changes pseudos created by function remove_scratches onto scratches. */
5435	void
5436	ira_restore_scratches (FILE *dump_file)
5437	{
5438	int regno, n;
5439	unsigned i;
5440	rtx *op_loc;
5441	sloc_t loc;
5442
5443	for (i = 0; scratches.iterate (ix: i, ptr: &loc); i++)
5444	{
5445	/* Ignore already deleted insns. */
5446	if (NOTE_P (loc->insn)
5447	&& NOTE_KIND (loc->insn) == NOTE_INSN_DELETED)
5448	continue;
5449	extract_insn (loc->insn);
5450	if (loc->icode != INSN_CODE (loc->insn))
5451	{
5452	/* The icode doesn't match, which means the insn has been modified
5453	(e.g. register elimination). The scratch cannot be restored. */
5454	continue;
5455	}
5456	op_loc = recog_data.operand_loc[loc->nop];
5457	if (REG_P (*op_loc)
5458	&& ((regno = REGNO (*op_loc)) >= FIRST_PSEUDO_REGISTER)
5459	&& reg_renumber[regno] < 0)
5460	{
5461	/* It should be only case when scratch register with chosen
5462	constraint 'X' did not get memory or hard register. */
5463	ira_assert (ira_former_scratch_p (regno));
5464	*op_loc = gen_rtx_SCRATCH (GET_MODE (*op_loc));
5465	for (n = 0; n < recog_data.n_dups; n++)
5466	*recog_data.dup_loc[n]
5467	= *recog_data.operand_loc[(int) recog_data.dup_num[n]];
5468	if (dump_file != NULL)
5469	fprintf (stream: dump_file, format: "Restoring SCRATCH in insn #%u(nop %d)\n",
5470	INSN_UID (insn: loc->insn), loc->nop);
5471	}
5472	}
5473	for (i = 0; scratches.iterate (ix: i, ptr: &loc); i++)
5474	free (ptr: loc);
5475	scratches.release ();
5476	bitmap_clear (&scratch_bitmap);
5477	bitmap_clear (&scratch_operand_bitmap);
5478	}
5479
5480
5481
5482	/* If the backend knows where to allocate pseudos for hard
5483	register initial values, register these allocations now. */
5484	static void
5485	allocate_initial_values (void)
5486	{
5487	if (targetm.allocate_initial_value)
5488	{
5489	rtx hreg, preg, x;
5490	int i, regno;
5491
5492	for (i = 0; HARD_REGISTER_NUM_P (i); i++)
5493	{
5494	if (! initial_value_entry (i, &hreg, &preg))
5495	break;
5496
5497	x = targetm.allocate_initial_value (hreg);
5498	regno = REGNO (preg);
5499	if (x && REG_N_SETS (regno) <= 1)
5500	{
5501	if (MEM_P (x))
5502	reg_equiv_memory_loc (regno) = x;
5503	else
5504	{
5505	basic_block bb;
5506	int new_regno;
5507
5508	gcc_assert (REG_P (x));
5509	new_regno = REGNO (x);
5510	reg_renumber[regno] = new_regno;
5511	/* Poke the regno right into regno_reg_rtx so that even
5512	fixed regs are accepted. */
5513	SET_REGNO (preg, new_regno);
5514	/* Update global register liveness information. */
5515	FOR_EACH_BB_FN (bb, cfun)
5516	{
5517	if (REGNO_REG_SET_P (df_get_live_in (bb), regno))
5518	SET_REGNO_REG_SET (df_get_live_in (bb), new_regno);
5519	if (REGNO_REG_SET_P (df_get_live_out (bb), regno))
5520	SET_REGNO_REG_SET (df_get_live_out (bb), new_regno);
5521	}
5522	}
5523	}
5524	}
5525
5526	gcc_checking_assert (! initial_value_entry (FIRST_PSEUDO_REGISTER,
5527	&hreg, &preg));
5528	}
5529	}
5530
5531
5532
5533
5534	/* True when we use LRA instead of reload pass for the current
5535	function. */
5536	bool ira_use_lra_p;
5537
5538	/* True if we have allocno conflicts. It is false for non-optimized
5539	mode or when the conflict table is too big. */
5540	bool ira_conflicts_p;
5541
5542	/* Saved between IRA and reload. */
5543	static int saved_flag_ira_share_spill_slots;
5544
5545	/* Set to true while in IRA. */
5546	bool ira_in_progress = false;
5547
5548	/* This is the main entry of IRA. */
5549	static void
5550	ira (FILE *f)
5551	{
5552	bool loops_p;
5553	int ira_max_point_before_emit;
5554	bool saved_flag_caller_saves = flag_caller_saves;
5555	enum ira_region saved_flag_ira_region = flag_ira_region;
5556	basic_block bb;
5557	edge_iterator ei;
5558	edge e;
5559	bool output_jump_reload_p = false;
5560
5561	if (ira_use_lra_p)
5562	{
5563	/* First put potential jump output reloads on the output edges
5564	as USE which will be removed at the end of LRA. The major
5565	goal is actually to create BBs for critical edges for LRA and
5566	populate them later by live info. In LRA it will be
5567	difficult to do this. */
5568	FOR_EACH_BB_FN (bb, cfun)
5569	{
5570	rtx_insn *end = BB_END (bb);
5571	if (!JUMP_P (end))
5572	continue;
5573	extract_insn (end);
5574	for (int i = 0; i < recog_data.n_operands; i++)
5575	if (recog_data.operand_type[i] != OP_IN)
5576	{
5577	bool skip_p = false;
5578	FOR_EACH_EDGE (e, ei, bb->succs)
5579	if (EDGE_CRITICAL_P (e)
5580	&& e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
5581	&& (e->flags & EDGE_ABNORMAL))
5582	{
5583	skip_p = true;
5584	break;
5585	}
5586	if (skip_p)
5587	break;
5588	output_jump_reload_p = true;
5589	FOR_EACH_EDGE (e, ei, bb->succs)
5590	if (EDGE_CRITICAL_P (e)
5591	&& e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
5592	{
5593	start_sequence ();
5594	/* We need to put some no-op insn here. We can
5595	not put a note as commit_edges insertion will
5596	fail. */
5597	emit_insn (gen_rtx_USE (VOIDmode, const1_rtx));
5598	rtx_insn *insns = get_insns ();
5599	end_sequence ();
5600	insert_insn_on_edge (insns, e);
5601	}
5602	break;
5603	}
5604	}
5605	if (output_jump_reload_p)
5606	commit_edge_insertions ();
5607	}
5608
5609	if (flag_ira_verbose < 10)
5610	{
5611	internal_flag_ira_verbose = flag_ira_verbose;
5612	ira_dump_file = f;
5613	}
5614	else
5615	{
5616	internal_flag_ira_verbose = flag_ira_verbose - 10;
5617	ira_dump_file = stderr;
5618	}
5619
5620	clear_bb_flags ();
5621
5622	/* Determine if the current function is a leaf before running IRA
5623	since this can impact optimizations done by the prologue and
5624	epilogue thus changing register elimination offsets.
5625	Other target callbacks may use crtl->is_leaf too, including
5626	SHRINK_WRAPPING_ENABLED, so initialize as early as possible. */
5627	crtl->is_leaf = leaf_function_p ();
5628
5629	/* Perform target specific PIC register initialization. */
5630	targetm.init_pic_reg ();
5631
5632	ira_conflicts_p = optimize > 0;
5633
5634	/* Determine the number of pseudos actually requiring coloring. */
5635	unsigned int num_used_regs = 0;
5636	for (unsigned int i = FIRST_PSEUDO_REGISTER; i < DF_REG_SIZE (df); i++)
5637	if (DF_REG_DEF_COUNT (i) || DF_REG_USE_COUNT (i))
5638	num_used_regs++;
5639
5640	/* If there are too many pseudos and/or basic blocks (e.g. 10K pseudos and
5641	10K blocks or 100K pseudos and 1K blocks) or we have too many function
5642	insns, we will use simplified and faster algorithms in LRA. */
5643	lra_simple_p
5644	= (ira_use_lra_p
5645	&& (num_used_regs >= (1U << 26) / last_basic_block_for_fn (cfun)
5646	/* max uid is a good evaluation of the number of insns as most
5647	optimizations are done on tree-SSA level. */
5648	|| ((uint64_t) get_max_uid ()
5649	> (uint64_t) param_ira_simple_lra_insn_threshold * 1000)));
5650
5651	if (lra_simple_p)
5652	{
5653	/* It permits to skip live range splitting in LRA. */
5654	flag_caller_saves = false;
5655	/* There is no sense to do regional allocation when we use
5656	simplified LRA. */
5657	flag_ira_region = IRA_REGION_ONE;
5658	ira_conflicts_p = false;
5659	}
5660
5661	#ifndef IRA_NO_OBSTACK
5662	gcc_obstack_init (&ira_obstack);
5663	#endif
5664	bitmap_obstack_initialize (&ira_bitmap_obstack);
5665
5666	/* LRA uses its own infrastructure to handle caller save registers. */
5667	if (flag_caller_saves && !ira_use_lra_p)
5668	init_caller_save ();
5669
5670	setup_prohibited_mode_move_regs ();
5671	decrease_live_ranges_number ();
5672	df_note_add_problem ();
5673
5674	/* DF_LIVE can't be used in the register allocator, too many other
5675	parts of the compiler depend on using the "classic" liveness
5676	interpretation of the DF_LR problem. See PR38711.
5677	Remove the problem, so that we don't spend time updating it in
5678	any of the df_analyze() calls during IRA/LRA. */
5679	if (optimize > 1)
5680	df_remove_problem (df_live);
5681	gcc_checking_assert (df_live == NULL);
5682
5683	if (flag_checking)
5684	df->changeable_flags |= DF_VERIFY_SCHEDULED;
5685
5686	df_analyze ();
5687
5688	init_reg_equiv ();
5689	if (ira_conflicts_p)
5690	{
5691	calculate_dominance_info (CDI_DOMINATORS);
5692
5693	if (split_live_ranges_for_shrink_wrap ())
5694	df_analyze ();
5695
5696	free_dominance_info (CDI_DOMINATORS);
5697	}
5698
5699	df_clear_flags (DF_NO_INSN_RESCAN);
5700
5701	indirect_jump_optimize ();
5702	if (delete_trivially_dead_insns (get_insns (), max_reg_num ()))
5703	df_analyze ();
5704
5705	regstat_init_n_sets_and_refs ();
5706	regstat_compute_ri ();
5707
5708	/* If we are not optimizing, then this is the only place before
5709	register allocation where dataflow is done. And that is needed
5710	to generate these warnings. */
5711	if (warn_clobbered)
5712	generate_setjmp_warnings ();
5713
5714	/* update_equiv_regs can use reg classes of pseudos and they are set up in
5715	register pressure sensitive scheduling and loop invariant motion and in
5716	live range shrinking. This info can become obsolete if we add new pseudos
5717	since the last set up. Recalculate it again if the new pseudos were
5718	added. */
5719	if (resize_reg_info () && (flag_sched_pressure || flag_live_range_shrinkage
5720	|| flag_ira_loop_pressure))
5721	ira_set_pseudo_classes (true, ira_dump_file);
5722
5723	init_alias_analysis ();
5724	loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
5725	reg_equiv = XCNEWVEC (struct equivalence, max_reg_num ());
5726	update_equiv_regs_prescan ();
5727	update_equiv_regs ();
5728
5729	/* Don't move insns if live range shrinkage or register
5730	pressure-sensitive scheduling were done because it will not
5731	improve allocation but likely worsen insn scheduling. */
5732	if (optimize
5733	&& !flag_live_range_shrinkage
5734	&& !(flag_sched_pressure && flag_schedule_insns))
5735	combine_and_move_insns ();
5736
5737	/* Gather additional equivalences with memory. */
5738	if (optimize)
5739	add_store_equivs ();
5740
5741	loop_optimizer_finalize ();
5742	free_dominance_info (CDI_DOMINATORS);
5743	end_alias_analysis ();
5744	free (ptr: reg_equiv);
5745
5746	/* Once max_regno changes, we need to free and re-init/re-compute
5747	some data structures like regstat_n_sets_and_refs and reg_info_p. */
5748	auto regstat_recompute_for_max_regno = []() {
5749	regstat_free_n_sets_and_refs ();
5750	regstat_free_ri ();
5751	regstat_init_n_sets_and_refs ();
5752	regstat_compute_ri ();
5753	resize_reg_info ();
5754	};
5755
5756	int max_regno_before_rm = max_reg_num ();
5757	if (ira_use_lra_p && remove_scratches ())
5758	{
5759	ira_expand_reg_equiv ();
5760	/* For now remove_scatches is supposed to create pseudos when it
5761	succeeds, assert this happens all the time. Once it doesn't
5762	hold, we should guard the regstat recompute for the case
5763	max_regno changes. */
5764	gcc_assert (max_regno_before_rm != max_reg_num ());
5765	regstat_recompute_for_max_regno ();
5766	}
5767
5768	setup_reg_equiv ();
5769	grow_reg_equivs ();
5770	setup_reg_equiv_init ();
5771
5772	allocated_reg_info_size = max_reg_num ();
5773
5774	/* It is not worth to do such improvement when we use a simple
5775	allocation because of -O0 usage or because the function is too
5776	big. */
5777	if (ira_conflicts_p)
5778	find_moveable_pseudos ();
5779
5780	max_regno_before_ira = max_reg_num ();
5781	ira_setup_eliminable_regset ();
5782
5783	ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
5784	ira_load_cost = ira_store_cost = ira_shuffle_cost = 0;
5785	ira_move_loops_num = ira_additional_jumps_num = 0;
5786
5787	ira_assert (current_loops == NULL);
5788	if (flag_ira_region == IRA_REGION_ALL || flag_ira_region == IRA_REGION_MIXED)
5789	loop_optimizer_init (AVOID_CFG_MODIFICATIONS | LOOPS_HAVE_RECORDED_EXITS);
5790
5791	if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
5792	fprintf (stream: ira_dump_file, format: "Building IRA IR\n");
5793	loops_p = ira_build ();
5794
5795	ira_assert (ira_conflicts_p || !loops_p);
5796
5797	saved_flag_ira_share_spill_slots = flag_ira_share_spill_slots;
5798	if (too_high_register_pressure_p () || cfun->calls_setjmp)
5799	/* It is just wasting compiler's time to pack spilled pseudos into
5800	stack slots in this case -- prohibit it. We also do this if
5801	there is setjmp call because a variable not modified between
5802	setjmp and longjmp the compiler is required to preserve its
5803	value and sharing slots does not guarantee it. */
5804	flag_ira_share_spill_slots = false;
5805
5806	ira_color ();
5807
5808	ira_max_point_before_emit = ira_max_point;
5809
5810	ira_initiate_emit_data ();
5811
5812	ira_emit (loops_p);
5813
5814	max_regno = max_reg_num ();
5815	if (ira_conflicts_p)
5816	{
5817	if (! loops_p)
5818	{
5819	if (! ira_use_lra_p)
5820	ira_initiate_assign ();
5821	}
5822	else
5823	{
5824	expand_reg_info ();
5825
5826	if (ira_use_lra_p)
5827	{
5828	ira_allocno_t a;
5829	ira_allocno_iterator ai;
5830
5831	FOR_EACH_ALLOCNO (a, ai)
5832	{
5833	int old_regno = ALLOCNO_REGNO (a);
5834	int new_regno = REGNO (ALLOCNO_EMIT_DATA (a)->reg);
5835
5836	ALLOCNO_REGNO (a) = new_regno;
5837
5838	if (old_regno != new_regno)
5839	setup_reg_classes (new_regno, reg_preferred_class (old_regno),
5840	reg_alternate_class (old_regno),
5841	reg_allocno_class (old_regno));
5842	}
5843	}
5844	else
5845	{
5846	if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
5847	fprintf (stream: ira_dump_file, format: "Flattening IR\n");
5848	ira_flattening (max_regno_before_ira, ira_max_point_before_emit);
5849	}
5850	/* New insns were generated: add notes and recalculate live
5851	info. */
5852	df_analyze ();
5853
5854	/* ??? Rebuild the loop tree, but why? Does the loop tree
5855	change if new insns were generated? Can that be handled
5856	by updating the loop tree incrementally? */
5857	loop_optimizer_finalize ();
5858	free_dominance_info (CDI_DOMINATORS);
5859	loop_optimizer_init (AVOID_CFG_MODIFICATIONS
5860	| LOOPS_HAVE_RECORDED_EXITS);
5861
5862	if (! ira_use_lra_p)
5863	{
5864	setup_allocno_assignment_flags ();
5865	ira_initiate_assign ();
5866	ira_reassign_conflict_allocnos (max_regno);
5867	}
5868	}
5869	}
5870
5871	ira_finish_emit_data ();
5872
5873	setup_reg_renumber ();
5874
5875	calculate_allocation_cost ();
5876
5877	#ifdef ENABLE_IRA_CHECKING
5878	if (ira_conflicts_p && ! ira_use_lra_p)
5879	/* Opposite to reload pass, LRA does not use any conflict info
5880	from IRA. We don't rebuild conflict info for LRA (through
5881	ira_flattening call) and cannot use the check here. We could
5882	rebuild this info for LRA in the check mode but there is a risk
5883	that code generated with the check and without it will be a bit
5884	different. Calling ira_flattening in any mode would be a
5885	wasting CPU time. So do not check the allocation for LRA. */
5886	check_allocation ();
5887	#endif
5888
5889	if (max_regno != max_regno_before_ira)
5890	regstat_recompute_for_max_regno ();
5891
5892	overall_cost_before = ira_overall_cost;
5893	if (! ira_conflicts_p)
5894	grow_reg_equivs ();
5895	else
5896	{
5897	fix_reg_equiv_init ();
5898
5899	#ifdef ENABLE_IRA_CHECKING
5900	print_redundant_copies ();
5901	#endif
5902	if (! ira_use_lra_p)
5903	{
5904	ira_spilled_reg_stack_slots_num = 0;
5905	ira_spilled_reg_stack_slots
5906	= ((class ira_spilled_reg_stack_slot *)
5907	ira_allocate (len: max_regno
5908	* sizeof (class ira_spilled_reg_stack_slot)));
5909	memset (s: (void *)ira_spilled_reg_stack_slots, c: 0,
5910	n: max_regno * sizeof (class ira_spilled_reg_stack_slot));
5911	}
5912	}
5913	allocate_initial_values ();
5914
5915	/* See comment for find_moveable_pseudos call. */
5916	if (ira_conflicts_p)
5917	move_unallocated_pseudos ();
5918
5919	/* Restore original values. */
5920	if (lra_simple_p)
5921	{
5922	flag_caller_saves = saved_flag_caller_saves;
5923	flag_ira_region = saved_flag_ira_region;
5924	}
5925	}
5926
5927	/* Modify asm goto to avoid further trouble with this insn. We can
5928	not replace the insn by USE as in other asm insns as we still
5929	need to keep CFG consistency. */
5930	void
5931	ira_nullify_asm_goto (rtx_insn *insn)
5932	{
5933	ira_assert (JUMP_P (insn) && INSN_CODE (insn) < 0);
5934	rtx tmp = extract_asm_operands (PATTERN (insn));
5935	PATTERN (insn) = gen_rtx_ASM_OPERANDS (VOIDmode, ggc_strdup (""), "", 0,
5936	rtvec_alloc (0),
5937	rtvec_alloc (0),
5938	ASM_OPERANDS_LABEL_VEC (tmp),
5939	ASM_OPERANDS_SOURCE_LOCATION(tmp));
5940	}
5941
5942	static void
5943	do_reload (void)
5944	{
5945	basic_block bb;
5946	bool need_dce;
5947	unsigned pic_offset_table_regno = INVALID_REGNUM;
5948
5949	if (flag_ira_verbose < 10)
5950	ira_dump_file = dump_file;
5951
5952	/* If pic_offset_table_rtx is a pseudo register, then keep it so
5953	after reload to avoid possible wrong usages of hard reg assigned
5954	to it. */
5955	if (pic_offset_table_rtx
5956	&& REGNO (pic_offset_table_rtx) >= FIRST_PSEUDO_REGISTER)
5957	pic_offset_table_regno = REGNO (pic_offset_table_rtx);
5958
5959	timevar_push (tv: TV_RELOAD);
5960	if (ira_use_lra_p)
5961	{
5962	if (current_loops != NULL)
5963	{
5964	loop_optimizer_finalize ();
5965	free_dominance_info (CDI_DOMINATORS);
5966	}
5967	FOR_ALL_BB_FN (bb, cfun)
5968	bb->loop_father = NULL;
5969	current_loops = NULL;
5970
5971	ira_destroy ();
5972
5973	lra (ira_dump_file);
5974	/* ???!!! Move it before lra () when we use ira_reg_equiv in
5975	LRA. */
5976	vec_free (v&: reg_equivs);
5977	reg_equivs = NULL;
5978	need_dce = false;
5979	}
5980	else
5981	{
5982	df_set_flags (DF_NO_INSN_RESCAN);
5983	build_insn_chain ();
5984
5985	need_dce = reload (get_insns (), ira_conflicts_p);
5986	}
5987
5988	timevar_pop (tv: TV_RELOAD);
5989
5990	timevar_push (tv: TV_IRA);
5991
5992	if (ira_conflicts_p && ! ira_use_lra_p)
5993	{
5994	ira_free (addr: ira_spilled_reg_stack_slots);
5995	ira_finish_assign ();
5996	}
5997
5998	if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL
5999	&& overall_cost_before != ira_overall_cost)
6000	fprintf (stream: ira_dump_file, format: "+++Overall after reload %" PRId64 "\n",
6001	ira_overall_cost);
6002
6003	flag_ira_share_spill_slots = saved_flag_ira_share_spill_slots;
6004
6005	if (! ira_use_lra_p)
6006	{
6007	ira_destroy ();
6008	if (current_loops != NULL)
6009	{
6010	loop_optimizer_finalize ();
6011	free_dominance_info (CDI_DOMINATORS);
6012	}
6013	FOR_ALL_BB_FN (bb, cfun)
6014	bb->loop_father = NULL;
6015	current_loops = NULL;
6016
6017	regstat_free_ri ();
6018	regstat_free_n_sets_and_refs ();
6019	}
6020
6021	if (optimize)
6022	cleanup_cfg (CLEANUP_EXPENSIVE);
6023
6024	finish_reg_equiv ();
6025
6026	bitmap_obstack_release (&ira_bitmap_obstack);
6027	#ifndef IRA_NO_OBSTACK
6028	obstack_free (&ira_obstack, NULL);
6029	#endif
6030
6031	/* The code after the reload has changed so much that at this point
6032	we might as well just rescan everything. Note that
6033	df_rescan_all_insns is not going to help here because it does not
6034	touch the artificial uses and defs. */
6035	df_finish_pass (true);
6036	df_scan_alloc (NULL);
6037	df_scan_blocks ();
6038
6039	if (optimize > 1)
6040	{
6041	df_live_add_problem ();
6042	df_live_set_all_dirty ();
6043	}
6044
6045	if (optimize)
6046	df_analyze ();
6047
6048	if (need_dce && optimize)
6049	run_fast_dce ();
6050
6051	/* Diagnose uses of the hard frame pointer when it is used as a global
6052	register. Often we can get away with letting the user appropriate
6053	the frame pointer, but we should let them know when code generation
6054	makes that impossible. */
6055	if (global_regs[HARD_FRAME_POINTER_REGNUM] && frame_pointer_needed)
6056	{
6057	tree decl = global_regs_decl[HARD_FRAME_POINTER_REGNUM];
6058	error_at (DECL_SOURCE_LOCATION (current_function_decl),
6059	"frame pointer required, but reserved");
6060	inform (DECL_SOURCE_LOCATION (decl), "for %qD", decl);
6061	}
6062
6063	/* If we are doing generic stack checking, give a warning if this
6064	function's frame size is larger than we expect. */
6065	if (flag_stack_check == GENERIC_STACK_CHECK)
6066	{
6067	poly_int64 size = get_frame_size () + STACK_CHECK_FIXED_FRAME_SIZE;
6068
6069	for (int i = 0; i < FIRST_PSEUDO_REGISTER; i++)
6070	if (df_regs_ever_live_p (i)
6071	&& !fixed_regs[i]
6072	&& !crtl->abi->clobbers_full_reg_p (regno: i))
6073	size += UNITS_PER_WORD;
6074
6075	if (constant_lower_bound (a: size) > STACK_CHECK_MAX_FRAME_SIZE)
6076	warning (0, "frame size too large for reliable stack checking");
6077	}
6078
6079	if (pic_offset_table_regno != INVALID_REGNUM)
6080	pic_offset_table_rtx = gen_rtx_REG (Pmode, pic_offset_table_regno);
6081
6082	timevar_pop (tv: TV_IRA);
6083	}
6084
6085	/* Run the integrated register allocator. */
6086
6087	namespace {
6088
6089	const pass_data pass_data_ira =
6090	{
6091	.type: RTL_PASS, /* type */
6092	.name: "ira", /* name */
6093	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
6094	.tv_id: TV_IRA, /* tv_id */
6095	.properties_required: 0, /* properties_required */
6096	.properties_provided: 0, /* properties_provided */
6097	.properties_destroyed: 0, /* properties_destroyed */
6098	.todo_flags_start: 0, /* todo_flags_start */
6099	TODO_do_not_ggc_collect, /* todo_flags_finish */
6100	};
6101
6102	class pass_ira : public rtl_opt_pass
6103	{
6104	public:
6105	pass_ira (gcc::context *ctxt)
6106	: rtl_opt_pass (pass_data_ira, ctxt)
6107	{}
6108
6109	/* opt_pass methods: */
6110	bool gate (function *) final override
6111	{
6112	return !targetm.no_register_allocation;
6113	}
6114	unsigned int execute (function *) final override
6115	{
6116	ira_in_progress = true;
6117	ira (f: dump_file);
6118	ira_in_progress = false;
6119	return 0;
6120	}
6121
6122	}; // class pass_ira
6123
6124	} // anon namespace
6125
6126	rtl_opt_pass *
6127	make_pass_ira (gcc::context *ctxt)
6128	{
6129	return new pass_ira (ctxt);
6130	}
6131
6132	namespace {
6133
6134	const pass_data pass_data_reload =
6135	{
6136	.type: RTL_PASS, /* type */
6137	.name: "reload", /* name */
6138	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
6139	.tv_id: TV_RELOAD, /* tv_id */
6140	.properties_required: 0, /* properties_required */
6141	.properties_provided: 0, /* properties_provided */
6142	.properties_destroyed: 0, /* properties_destroyed */
6143	.todo_flags_start: 0, /* todo_flags_start */
6144	.todo_flags_finish: 0, /* todo_flags_finish */
6145	};
6146
6147	class pass_reload : public rtl_opt_pass
6148	{
6149	public:
6150	pass_reload (gcc::context *ctxt)
6151	: rtl_opt_pass (pass_data_reload, ctxt)
6152	{}
6153
6154	/* opt_pass methods: */
6155	bool gate (function *) final override
6156	{
6157	return !targetm.no_register_allocation;
6158	}
6159	unsigned int execute (function *) final override
6160	{
6161	do_reload ();
6162	return 0;
6163	}
6164
6165	}; // class pass_reload
6166
6167	} // anon namespace
6168
6169	rtl_opt_pass *
6170	make_pass_reload (gcc::context *ctxt)
6171	{
6172	return new pass_reload (ctxt);
6173	}
6174