1	/* IRA allocation based on graph coloring.
2	Copyright (C) 2006-2024 Free Software Foundation, Inc.
3	Contributed by Vladimir Makarov <vmakarov@redhat.com>.
4
5	This file is part of GCC.
6
7	GCC is free software; you can redistribute it and/or modify it under
8	the terms of the GNU General Public License as published by the Free
9	Software Foundation; either version 3, or (at your option) any later
10	version.
11
12	GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13	WARRANTY; without even the implied warranty of MERCHANTABILITY or
14	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15	for more details.
16
17	You should have received a copy of the GNU General Public License
18	along with GCC; see the file COPYING3. If not see
19	<http://www.gnu.org/licenses/>. */
20
21	#include "config.h"
22	#include "system.h"
23	#include "coretypes.h"
24	#include "backend.h"
25	#include "target.h"
26	#include "rtl.h"
27	#include "tree.h"
28	#include "predict.h"
29	#include "df.h"
30	#include "memmodel.h"
31	#include "tm_p.h"
32	#include "insn-config.h"
33	#include "regs.h"
34	#include "ira.h"
35	#include "ira-int.h"
36	#include "reload.h"
37	#include "cfgloop.h"
38
39	/* To prevent soft conflict detection becoming quadratic in the
40	loop depth. Only for very pathological cases, so it hardly
41	seems worth a --param. */
42	const int max_soft_conflict_loop_depth = 64;
43
44	typedef struct allocno_hard_regs *allocno_hard_regs_t;
45
46	/* The structure contains information about hard registers can be
47	assigned to allocnos. Usually it is allocno profitable hard
48	registers but in some cases this set can be a bit different. Major
49	reason of the difference is a requirement to use hard register sets
50	that form a tree or a forest (set of trees), i.e. hard register set
51	of a node should contain hard register sets of its subnodes. */
52	struct allocno_hard_regs
53	{
54	/* Hard registers can be assigned to an allocno. */
55	HARD_REG_SET set;
56	/* Overall (spilling) cost of all allocnos with given register
57	set. */
58	int64_t cost;
59	};
60
61	typedef struct allocno_hard_regs_node *allocno_hard_regs_node_t;
62
63	/* A node representing allocno hard registers. Such nodes form a
64	forest (set of trees). Each subnode of given node in the forest
65	refers for hard register set (usually allocno profitable hard
66	register set) which is a subset of one referred from given
67	node. */
68	struct allocno_hard_regs_node
69	{
70	/* Set up number of the node in preorder traversing of the forest. */
71	int preorder_num;
72	/* Used for different calculation like finding conflict size of an
73	allocno. */
74	int check;
75	/* Used for calculation of conflict size of an allocno. The
76	conflict size of the allocno is maximal number of given allocno
77	hard registers needed for allocation of the conflicting allocnos.
78	Given allocno is trivially colored if this number plus the number
79	of hard registers needed for given allocno is not greater than
80	the number of given allocno hard register set. */
81	int conflict_size;
82	/* The number of hard registers given by member hard_regs. */
83	int hard_regs_num;
84	/* The following member is used to form the final forest. */
85	bool used_p;
86	/* Pointer to the corresponding profitable hard registers. */
87	allocno_hard_regs_t hard_regs;
88	/* Parent, first subnode, previous and next node with the same
89	parent in the forest. */
90	allocno_hard_regs_node_t parent, first, prev, next;
91	};
92
93	/* Info about changing hard reg costs of an allocno. */
94	struct update_cost_record
95	{
96	/* Hard regno for which we changed the cost. */
97	int hard_regno;
98	/* Divisor used when we changed the cost of HARD_REGNO. */
99	int divisor;
100	/* Next record for given allocno. */
101	struct update_cost_record *next;
102	};
103
104	/* To decrease footprint of ira_allocno structure we store all data
105	needed only for coloring in the following structure. */
106	struct allocno_color_data
107	{
108	/* TRUE value means that the allocno was not removed yet from the
109	conflicting graph during coloring. */
110	unsigned int in_graph_p : 1;
111	/* TRUE if it is put on the stack to make other allocnos
112	colorable. */
113	unsigned int may_be_spilled_p : 1;
114	/* TRUE if the allocno is trivially colorable. */
115	unsigned int colorable_p : 1;
116	/* Number of hard registers of the allocno class really
117	available for the allocno allocation. It is number of the
118	profitable hard regs. */
119	int available_regs_num;
120	/* Sum of frequencies of hard register preferences of all
121	conflicting allocnos which are not the coloring stack yet. */
122	int conflict_allocno_hard_prefs;
123	/* Allocnos in a bucket (used in coloring) chained by the following
124	two members. */
125	ira_allocno_t next_bucket_allocno;
126	ira_allocno_t prev_bucket_allocno;
127	/* Used for temporary purposes. */
128	int temp;
129	/* Used to exclude repeated processing. */
130	int last_process;
131	/* Profitable hard regs available for this pseudo allocation. It
132	means that the set excludes unavailable hard regs and hard regs
133	conflicting with given pseudo. They should be of the allocno
134	class. */
135	HARD_REG_SET profitable_hard_regs;
136	/* The allocno hard registers node. */
137	allocno_hard_regs_node_t hard_regs_node;
138	/* Array of structures allocno_hard_regs_subnode representing
139	given allocno hard registers node (the 1st element in the array)
140	and all its subnodes in the tree (forest) of allocno hard
141	register nodes (see comments above). */
142	int hard_regs_subnodes_start;
143	/* The length of the previous array. */
144	int hard_regs_subnodes_num;
145	/* Records about updating allocno hard reg costs from copies. If
146	the allocno did not get expected hard register, these records are
147	used to restore original hard reg costs of allocnos connected to
148	this allocno by copies. */
149	struct update_cost_record *update_cost_records;
150	/* Threads. We collect allocnos connected by copies into threads
151	and try to assign hard regs to allocnos by threads. */
152	/* Allocno representing all thread. */
153	ira_allocno_t first_thread_allocno;
154	/* Allocnos in thread forms a cycle list through the following
155	member. */
156	ira_allocno_t next_thread_allocno;
157	/* All thread frequency. Defined only for first thread allocno. */
158	int thread_freq;
159	/* Sum of frequencies of hard register preferences of the allocno. */
160	int hard_reg_prefs;
161	};
162
163	/* See above. */
164	typedef struct allocno_color_data *allocno_color_data_t;
165
166	/* Container for storing allocno data concerning coloring. */
167	static allocno_color_data_t allocno_color_data;
168
169	/* Macro to access the data concerning coloring. */
170	#define ALLOCNO_COLOR_DATA(a) ((allocno_color_data_t) ALLOCNO_ADD_DATA (a))
171
172	/* Used for finding allocno colorability to exclude repeated allocno
173	processing and for updating preferencing to exclude repeated
174	allocno processing during assignment. */
175	static int curr_allocno_process;
176
177	/* This file contains code for regional graph coloring, spill/restore
178	code placement optimization, and code helping the reload pass to do
179	a better job. */
180
181	/* Bitmap of allocnos which should be colored. */
182	static bitmap coloring_allocno_bitmap;
183
184	/* Bitmap of allocnos which should be taken into account during
185	coloring. In general case it contains allocnos from
186	coloring_allocno_bitmap plus other already colored conflicting
187	allocnos. */
188	static bitmap consideration_allocno_bitmap;
189
190	/* All allocnos sorted according their priorities. */
191	static ira_allocno_t *sorted_allocnos;
192
193	/* Vec representing the stack of allocnos used during coloring. */
194	static vec<ira_allocno_t> allocno_stack_vec;
195
196	/* Helper for qsort comparison callbacks - return a positive integer if
197	X > Y, or a negative value otherwise. Use a conditional expression
198	instead of a difference computation to insulate from possible overflow
199	issues, e.g. X - Y < 0 for some X > 0 and Y < 0. */
200	#define SORTGT(x,y) (((x) > (y)) ? 1 : -1)
201
202
203
204	/* Definition of vector of allocno hard registers. */
205
206	/* Vector of unique allocno hard registers. */
207	static vec<allocno_hard_regs_t> allocno_hard_regs_vec;
208
209	struct allocno_hard_regs_hasher : nofree_ptr_hash <allocno_hard_regs>
210	{
211	static inline hashval_t hash (const allocno_hard_regs *);
212	static inline bool equal (const allocno_hard_regs *,
213	const allocno_hard_regs *);
214	};
215
216	/* Returns hash value for allocno hard registers V. */
217	inline hashval_t
218	allocno_hard_regs_hasher::hash (const allocno_hard_regs *hv)
219	{
220	return iterative_hash (&hv->set, sizeof (HARD_REG_SET), 0);
221	}
222
223	/* Compares allocno hard registers V1 and V2. */
224	inline bool
225	allocno_hard_regs_hasher::equal (const allocno_hard_regs *hv1,
226	const allocno_hard_regs *hv2)
227	{
228	return hv1->set == hv2->set;
229	}
230
231	/* Hash table of unique allocno hard registers. */
232	static hash_table<allocno_hard_regs_hasher> *allocno_hard_regs_htab;
233
234	/* Return allocno hard registers in the hash table equal to HV. */
235	static allocno_hard_regs_t
236	find_hard_regs (allocno_hard_regs_t hv)
237	{
238	return allocno_hard_regs_htab->find (value: hv);
239	}
240
241	/* Insert allocno hard registers HV in the hash table (if it is not
242	there yet) and return the value which in the table. */
243	static allocno_hard_regs_t
244	insert_hard_regs (allocno_hard_regs_t hv)
245	{
246	allocno_hard_regs **slot = allocno_hard_regs_htab->find_slot (value: hv, insert: INSERT);
247
248	if (*slot == NULL)
249	*slot = hv;
250	return *slot;
251	}
252
253	/* Initialize data concerning allocno hard registers. */
254	static void
255	init_allocno_hard_regs (void)
256	{
257	allocno_hard_regs_vec.create (nelems: 200);
258	allocno_hard_regs_htab
259	= new hash_table<allocno_hard_regs_hasher> (200);
260	}
261
262	/* Add (or update info about) allocno hard registers with SET and
263	COST. */
264	static allocno_hard_regs_t
265	add_allocno_hard_regs (HARD_REG_SET set, int64_t cost)
266	{
267	struct allocno_hard_regs temp;
268	allocno_hard_regs_t hv;
269
270	gcc_assert (! hard_reg_set_empty_p (set));
271	temp.set = set;
272	if ((hv = find_hard_regs (hv: &temp)) != NULL)
273	hv->cost += cost;
274	else
275	{
276	hv = ((struct allocno_hard_regs *)
277	ira_allocate (sizeof (struct allocno_hard_regs)));
278	hv->set = set;
279	hv->cost = cost;
280	allocno_hard_regs_vec.safe_push (obj: hv);
281	insert_hard_regs (hv);
282	}
283	return hv;
284	}
285
286	/* Finalize data concerning allocno hard registers. */
287	static void
288	finish_allocno_hard_regs (void)
289	{
290	int i;
291	allocno_hard_regs_t hv;
292
293	for (i = 0;
294	allocno_hard_regs_vec.iterate (ix: i, ptr: &hv);
295	i++)
296	ira_free (addr: hv);
297	delete allocno_hard_regs_htab;
298	allocno_hard_regs_htab = NULL;
299	allocno_hard_regs_vec.release ();
300	}
301
302	/* Sort hard regs according to their frequency of usage. */
303	static int
304	allocno_hard_regs_compare (const void *v1p, const void *v2p)
305	{
306	allocno_hard_regs_t hv1 = *(const allocno_hard_regs_t *) v1p;
307	allocno_hard_regs_t hv2 = *(const allocno_hard_regs_t *) v2p;
308
309	if (hv2->cost > hv1->cost)
310	return 1;
311	else if (hv2->cost < hv1->cost)
312	return -1;
313	return SORTGT (allocno_hard_regs_hasher::hash(hv2), allocno_hard_regs_hasher::hash(hv1));
314	}
315
316
317
318	/* Used for finding a common ancestor of two allocno hard registers
319	nodes in the forest. We use the current value of
320	'node_check_tick' to mark all nodes from one node to the top and
321	then walking up from another node until we find a marked node.
322
323	It is also used to figure out allocno colorability as a mark that
324	we already reset value of member 'conflict_size' for the forest
325	node corresponding to the processed allocno. */
326	static int node_check_tick;
327
328	/* Roots of the forest containing hard register sets can be assigned
329	to allocnos. */
330	static allocno_hard_regs_node_t hard_regs_roots;
331
332	/* Definition of vector of allocno hard register nodes. */
333
334	/* Vector used to create the forest. */
335	static vec<allocno_hard_regs_node_t> hard_regs_node_vec;
336
337	/* Create and return allocno hard registers node containing allocno
338	hard registers HV. */
339	static allocno_hard_regs_node_t
340	create_new_allocno_hard_regs_node (allocno_hard_regs_t hv)
341	{
342	allocno_hard_regs_node_t new_node;
343
344	new_node = ((struct allocno_hard_regs_node *)
345	ira_allocate (sizeof (struct allocno_hard_regs_node)));
346	new_node->check = 0;
347	new_node->hard_regs = hv;
348	new_node->hard_regs_num = hard_reg_set_size (set: hv->set);
349	new_node->first = NULL;
350	new_node->used_p = false;
351	return new_node;
352	}
353
354	/* Add allocno hard registers node NEW_NODE to the forest on its level
355	given by ROOTS. */
356	static void
357	add_new_allocno_hard_regs_node_to_forest (allocno_hard_regs_node_t *roots,
358	allocno_hard_regs_node_t new_node)
359	{
360	new_node->next = *roots;
361	if (new_node->next != NULL)
362	new_node->next->prev = new_node;
363	new_node->prev = NULL;
364	*roots = new_node;
365	}
366
367	/* Add allocno hard registers HV (or its best approximation if it is
368	not possible) to the forest on its level given by ROOTS. */
369	static void
370	add_allocno_hard_regs_to_forest (allocno_hard_regs_node_t *roots,
371	allocno_hard_regs_t hv)
372	{
373	unsigned int i, start;
374	allocno_hard_regs_node_t node, prev, new_node;
375	HARD_REG_SET temp_set;
376	allocno_hard_regs_t hv2;
377
378	start = hard_regs_node_vec.length ();
379	for (node = *roots; node != NULL; node = node->next)
380	{
381	if (hv->set == node->hard_regs->set)
382	return;
383	if (hard_reg_set_subset_p (x: hv->set, y: node->hard_regs->set))
384	{
385	add_allocno_hard_regs_to_forest (roots: &node->first, hv);
386	return;
387	}
388	if (hard_reg_set_subset_p (x: node->hard_regs->set, y: hv->set))
389	hard_regs_node_vec.safe_push (obj: node);
390	else if (hard_reg_set_intersect_p (x: hv->set, y: node->hard_regs->set))
391	{
392	temp_set = hv->set & node->hard_regs->set;
393	hv2 = add_allocno_hard_regs (set: temp_set, cost: hv->cost);
394	add_allocno_hard_regs_to_forest (roots: &node->first, hv: hv2);
395	}
396	}
397	if (hard_regs_node_vec.length ()
398	> start + 1)
399	{
400	/* Create a new node which contains nodes in hard_regs_node_vec. */
401	CLEAR_HARD_REG_SET (set&: temp_set);
402	for (i = start;
403	i < hard_regs_node_vec.length ();
404	i++)
405	{
406	node = hard_regs_node_vec[i];
407	temp_set |= node->hard_regs->set;
408	}
409	hv = add_allocno_hard_regs (set: temp_set, cost: hv->cost);
410	new_node = create_new_allocno_hard_regs_node (hv);
411	prev = NULL;
412	for (i = start;
413	i < hard_regs_node_vec.length ();
414	i++)
415	{
416	node = hard_regs_node_vec[i];
417	if (node->prev == NULL)
418	*roots = node->next;
419	else
420	node->prev->next = node->next;
421	if (node->next != NULL)
422	node->next->prev = node->prev;
423	if (prev == NULL)
424	new_node->first = node;
425	else
426	prev->next = node;
427	node->prev = prev;
428	node->next = NULL;
429	prev = node;
430	}
431	add_new_allocno_hard_regs_node_to_forest (roots, new_node);
432	}
433	hard_regs_node_vec.truncate (size: start);
434	}
435
436	/* Add allocno hard registers nodes starting with the forest level
437	given by FIRST which contains biggest set inside SET. */
438	static void
439	collect_allocno_hard_regs_cover (allocno_hard_regs_node_t first,
440	HARD_REG_SET set)
441	{
442	allocno_hard_regs_node_t node;
443
444	ira_assert (first != NULL);
445	for (node = first; node != NULL; node = node->next)
446	if (hard_reg_set_subset_p (x: node->hard_regs->set, y: set))
447	hard_regs_node_vec.safe_push (obj: node);
448	else if (hard_reg_set_intersect_p (x: set, y: node->hard_regs->set))
449	collect_allocno_hard_regs_cover (first: node->first, set);
450	}
451
452	/* Set up field parent as PARENT in all allocno hard registers nodes
453	in forest given by FIRST. */
454	static void
455	setup_allocno_hard_regs_nodes_parent (allocno_hard_regs_node_t first,
456	allocno_hard_regs_node_t parent)
457	{
458	allocno_hard_regs_node_t node;
459
460	for (node = first; node != NULL; node = node->next)
461	{
462	node->parent = parent;
463	setup_allocno_hard_regs_nodes_parent (first: node->first, parent: node);
464	}
465	}
466
467	/* Return allocno hard registers node which is a first common ancestor
468	node of FIRST and SECOND in the forest. */
469	static allocno_hard_regs_node_t
470	first_common_ancestor_node (allocno_hard_regs_node_t first,
471	allocno_hard_regs_node_t second)
472	{
473	allocno_hard_regs_node_t node;
474
475	node_check_tick++;
476	for (node = first; node != NULL; node = node->parent)
477	node->check = node_check_tick;
478	for (node = second; node != NULL; node = node->parent)
479	if (node->check == node_check_tick)
480	return node;
481	return first_common_ancestor_node (first: second, second: first);
482	}
483
484	/* Print hard reg set SET to F. */
485	static void
486	print_hard_reg_set (FILE *f, HARD_REG_SET set, bool new_line_p)
487	{
488	int i, start, end;
489
490	for (start = end = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
491	{
492	bool reg_included = TEST_HARD_REG_BIT (set, bit: i);
493
494	if (reg_included)
495	{
496	if (start == -1)
497	start = i;
498	end = i;
499	}
500	if (start >= 0 && (!reg_included || i == FIRST_PSEUDO_REGISTER - 1))
501	{
502	if (start == end)
503	fprintf (stream: f, format: " %d", start);
504	else if (start == end + 1)
505	fprintf (stream: f, format: " %d %d", start, end);
506	else
507	fprintf (stream: f, format: " %d-%d", start, end);
508	start = -1;
509	}
510	}
511	if (new_line_p)
512	fprintf (stream: f, format: "\n");
513	}
514
515	/* Dump a hard reg set SET to stderr. */
516	DEBUG_FUNCTION void
517	debug_hard_reg_set (HARD_REG_SET set)
518	{
519	print_hard_reg_set (stderr, set, new_line_p: true);
520	}
521
522	/* Print allocno hard register subforest given by ROOTS and its LEVEL
523	to F. */
524	static void
525	print_hard_regs_subforest (FILE *f, allocno_hard_regs_node_t roots,
526	int level)
527	{
528	int i;
529	allocno_hard_regs_node_t node;
530
531	for (node = roots; node != NULL; node = node->next)
532	{
533	fprintf (stream: f, format: " ");
534	for (i = 0; i < level * 2; i++)
535	fprintf (stream: f, format: " ");
536	fprintf (stream: f, format: "%d:(", node->preorder_num);
537	print_hard_reg_set (f, set: node->hard_regs->set, new_line_p: false);
538	fprintf (stream: f, format: ")@%" PRId64"\n", node->hard_regs->cost);
539	print_hard_regs_subforest (f, roots: node->first, level: level + 1);
540	}
541	}
542
543	/* Print the allocno hard register forest to F. */
544	static void
545	print_hard_regs_forest (FILE *f)
546	{
547	fprintf (stream: f, format: " Hard reg set forest:\n");
548	print_hard_regs_subforest (f, roots: hard_regs_roots, level: 1);
549	}
550
551	/* Print the allocno hard register forest to stderr. */
552	void
553	ira_debug_hard_regs_forest (void)
554	{
555	print_hard_regs_forest (stderr);
556	}
557
558	/* Remove unused allocno hard registers nodes from forest given by its
559	*ROOTS. */
560	static void
561	remove_unused_allocno_hard_regs_nodes (allocno_hard_regs_node_t *roots)
562	{
563	allocno_hard_regs_node_t node, prev, next, last;
564
565	for (prev = NULL, node = *roots; node != NULL; node = next)
566	{
567	next = node->next;
568	if (node->used_p)
569	{
570	remove_unused_allocno_hard_regs_nodes (roots: &node->first);
571	prev = node;
572	}
573	else
574	{
575	for (last = node->first;
576	last != NULL && last->next != NULL;
577	last = last->next)
578	;
579	if (last != NULL)
580	{
581	if (prev == NULL)
582	*roots = node->first;
583	else
584	prev->next = node->first;
585	if (next != NULL)
586	next->prev = last;
587	last->next = next;
588	next = node->first;
589	}
590	else
591	{
592	if (prev == NULL)
593	*roots = next;
594	else
595	prev->next = next;
596	if (next != NULL)
597	next->prev = prev;
598	}
599	ira_free (addr: node);
600	}
601	}
602	}
603
604	/* Set up fields preorder_num starting with START_NUM in all allocno
605	hard registers nodes in forest given by FIRST. Return biggest set
606	PREORDER_NUM increased by 1. */
607	static int
608	enumerate_allocno_hard_regs_nodes (allocno_hard_regs_node_t first,
609	allocno_hard_regs_node_t parent,
610	int start_num)
611	{
612	allocno_hard_regs_node_t node;
613
614	for (node = first; node != NULL; node = node->next)
615	{
616	node->preorder_num = start_num++;
617	node->parent = parent;
618	start_num = enumerate_allocno_hard_regs_nodes (first: node->first, parent: node,
619	start_num);
620	}
621	return start_num;
622	}
623
624	/* Number of allocno hard registers nodes in the forest. */
625	static int allocno_hard_regs_nodes_num;
626
627	/* Table preorder number of allocno hard registers node in the forest
628	-> the allocno hard registers node. */
629	static allocno_hard_regs_node_t *allocno_hard_regs_nodes;
630
631	/* See below. */
632	typedef struct allocno_hard_regs_subnode *allocno_hard_regs_subnode_t;
633
634	/* The structure is used to describes all subnodes (not only immediate
635	ones) in the mentioned above tree for given allocno hard register
636	node. The usage of such data accelerates calculation of
637	colorability of given allocno. */
638	struct allocno_hard_regs_subnode
639	{
640	/* The conflict size of conflicting allocnos whose hard register
641	sets are equal sets (plus supersets if given node is given
642	allocno hard registers node) of one in the given node. */
643	int left_conflict_size;
644	/* The summary conflict size of conflicting allocnos whose hard
645	register sets are strict subsets of one in the given node.
646	Overall conflict size is
647	left_conflict_subnodes_size
648	+ MIN (max_node_impact - left_conflict_subnodes_size,
649	left_conflict_size)
650	*/
651	short left_conflict_subnodes_size;
652	short max_node_impact;
653	};
654
655	/* Container for hard regs subnodes of all allocnos. */
656	static allocno_hard_regs_subnode_t allocno_hard_regs_subnodes;
657
658	/* Table (preorder number of allocno hard registers node in the
659	forest, preorder number of allocno hard registers subnode) -> index
660	of the subnode relative to the node. -1 if it is not a
661	subnode. */
662	static int *allocno_hard_regs_subnode_index;
663
664	/* Setup arrays ALLOCNO_HARD_REGS_NODES and
665	ALLOCNO_HARD_REGS_SUBNODE_INDEX. */
666	static void
667	setup_allocno_hard_regs_subnode_index (allocno_hard_regs_node_t first)
668	{
669	allocno_hard_regs_node_t node, parent;
670	int index;
671
672	for (node = first; node != NULL; node = node->next)
673	{
674	allocno_hard_regs_nodes[node->preorder_num] = node;
675	for (parent = node; parent != NULL; parent = parent->parent)
676	{
677	index = parent->preorder_num * allocno_hard_regs_nodes_num;
678	allocno_hard_regs_subnode_index[index + node->preorder_num]
679	= node->preorder_num - parent->preorder_num;
680	}
681	setup_allocno_hard_regs_subnode_index (node->first);
682	}
683	}
684
685	/* Count all allocno hard registers nodes in tree ROOT. */
686	static int
687	get_allocno_hard_regs_subnodes_num (allocno_hard_regs_node_t root)
688	{
689	int len = 1;
690
691	for (root = root->first; root != NULL; root = root->next)
692	len += get_allocno_hard_regs_subnodes_num (root);
693	return len;
694	}
695
696	/* Build the forest of allocno hard registers nodes and assign each
697	allocno a node from the forest. */
698	static void
699	form_allocno_hard_regs_nodes_forest (void)
700	{
701	unsigned int i, j, size, len;
702	int start;
703	ira_allocno_t a;
704	allocno_hard_regs_t hv;
705	bitmap_iterator bi;
706	HARD_REG_SET temp;
707	allocno_hard_regs_node_t node, allocno_hard_regs_node;
708	allocno_color_data_t allocno_data;
709
710	node_check_tick = 0;
711	init_allocno_hard_regs ();
712	hard_regs_roots = NULL;
713	hard_regs_node_vec.create (nelems: 100);
714	for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
715	if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, bit: i))
716	{
717	CLEAR_HARD_REG_SET (set&: temp);
718	SET_HARD_REG_BIT (set&: temp, bit: i);
719	hv = add_allocno_hard_regs (set: temp, cost: 0);
720	node = create_new_allocno_hard_regs_node (hv);
721	add_new_allocno_hard_regs_node_to_forest (roots: &hard_regs_roots, new_node: node);
722	}
723	start = allocno_hard_regs_vec.length ();
724	EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
725	{
726	a = ira_allocnos[i];
727	allocno_data = ALLOCNO_COLOR_DATA (a);
728
729	if (hard_reg_set_empty_p (x: allocno_data->profitable_hard_regs))
730	continue;
731	hv = (add_allocno_hard_regs
732	(set: allocno_data->profitable_hard_regs,
733	ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a)));
734	}
735	temp = ~ira_no_alloc_regs;
736	add_allocno_hard_regs (set: temp, cost: 0);
737	qsort (allocno_hard_regs_vec.address () + start,
738	allocno_hard_regs_vec.length () - start,
739	sizeof (allocno_hard_regs_t), allocno_hard_regs_compare);
740	for (i = start;
741	allocno_hard_regs_vec.iterate (ix: i, ptr: &hv);
742	i++)
743	{
744	add_allocno_hard_regs_to_forest (roots: &hard_regs_roots, hv);
745	ira_assert (hard_regs_node_vec.length () == 0);
746	}
747	/* We need to set up parent fields for right work of
748	first_common_ancestor_node. */
749	setup_allocno_hard_regs_nodes_parent (first: hard_regs_roots, NULL);
750	EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
751	{
752	a = ira_allocnos[i];
753	allocno_data = ALLOCNO_COLOR_DATA (a);
754	if (hard_reg_set_empty_p (x: allocno_data->profitable_hard_regs))
755	continue;
756	hard_regs_node_vec.truncate (size: 0);
757	collect_allocno_hard_regs_cover (first: hard_regs_roots,
758	set: allocno_data->profitable_hard_regs);
759	allocno_hard_regs_node = NULL;
760	for (j = 0; hard_regs_node_vec.iterate (ix: j, ptr: &node); j++)
761	allocno_hard_regs_node
762	= (j == 0
763	? node
764	: first_common_ancestor_node (first: node, second: allocno_hard_regs_node));
765	/* That is a temporary storage. */
766	allocno_hard_regs_node->used_p = true;
767	allocno_data->hard_regs_node = allocno_hard_regs_node;
768	}
769	ira_assert (hard_regs_roots->next == NULL);
770	hard_regs_roots->used_p = true;
771	remove_unused_allocno_hard_regs_nodes (roots: &hard_regs_roots);
772	allocno_hard_regs_nodes_num
773	= enumerate_allocno_hard_regs_nodes (first: hard_regs_roots, NULL, start_num: 0);
774	allocno_hard_regs_nodes
775	= ((allocno_hard_regs_node_t *)
776	ira_allocate (allocno_hard_regs_nodes_num
777	* sizeof (allocno_hard_regs_node_t)));
778	size = allocno_hard_regs_nodes_num * allocno_hard_regs_nodes_num;
779	allocno_hard_regs_subnode_index
780	= (int *) ira_allocate (size * sizeof (int));
781	for (i = 0; i < size; i++)
782	allocno_hard_regs_subnode_index[i] = -1;
783	setup_allocno_hard_regs_subnode_index (hard_regs_roots);
784	start = 0;
785	EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
786	{
787	a = ira_allocnos[i];
788	allocno_data = ALLOCNO_COLOR_DATA (a);
789	if (hard_reg_set_empty_p (x: allocno_data->profitable_hard_regs))
790	continue;
791	len = get_allocno_hard_regs_subnodes_num (root: allocno_data->hard_regs_node);
792	allocno_data->hard_regs_subnodes_start = start;
793	allocno_data->hard_regs_subnodes_num = len;
794	start += len;
795	}
796	allocno_hard_regs_subnodes
797	= ((allocno_hard_regs_subnode_t)
798	ira_allocate (sizeof (struct allocno_hard_regs_subnode) * start));
799	hard_regs_node_vec.release ();
800	}
801
802	/* Free tree of allocno hard registers nodes given by its ROOT. */
803	static void
804	finish_allocno_hard_regs_nodes_tree (allocno_hard_regs_node_t root)
805	{
806	allocno_hard_regs_node_t child, next;
807
808	for (child = root->first; child != NULL; child = next)
809	{
810	next = child->next;
811	finish_allocno_hard_regs_nodes_tree (root: child);
812	}
813	ira_free (addr: root);
814	}
815
816	/* Finish work with the forest of allocno hard registers nodes. */
817	static void
818	finish_allocno_hard_regs_nodes_forest (void)
819	{
820	allocno_hard_regs_node_t node, next;
821
822	ira_free (addr: allocno_hard_regs_subnodes);
823	for (node = hard_regs_roots; node != NULL; node = next)
824	{
825	next = node->next;
826	finish_allocno_hard_regs_nodes_tree (root: node);
827	}
828	ira_free (addr: allocno_hard_regs_nodes);
829	ira_free (addr: allocno_hard_regs_subnode_index);
830	finish_allocno_hard_regs ();
831	}
832
833	/* Set up left conflict sizes and left conflict subnodes sizes of hard
834	registers subnodes of allocno A. Return TRUE if allocno A is
835	trivially colorable. */
836	static bool
837	setup_left_conflict_sizes_p (ira_allocno_t a)
838	{
839	int i, k, nobj, start;
840	int conflict_size, left_conflict_subnodes_size, node_preorder_num;
841	allocno_color_data_t data;
842	HARD_REG_SET profitable_hard_regs;
843	allocno_hard_regs_subnode_t subnodes;
844	allocno_hard_regs_node_t node;
845	HARD_REG_SET node_set;
846
847	nobj = ALLOCNO_NUM_OBJECTS (a);
848	data = ALLOCNO_COLOR_DATA (a);
849	subnodes = allocno_hard_regs_subnodes + data->hard_regs_subnodes_start;
850	profitable_hard_regs = data->profitable_hard_regs;
851	node = data->hard_regs_node;
852	node_preorder_num = node->preorder_num;
853	node_set = node->hard_regs->set;
854	node_check_tick++;
855	for (k = 0; k < nobj; k++)
856	{
857	ira_object_t obj = ALLOCNO_OBJECT (a, k);
858	ira_object_t conflict_obj;
859	ira_object_conflict_iterator oci;
860
861	FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
862	{
863	int size;
864	ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
865	allocno_hard_regs_node_t conflict_node, temp_node;
866	HARD_REG_SET conflict_node_set;
867	allocno_color_data_t conflict_data;
868
869	conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
870	if (! ALLOCNO_COLOR_DATA (conflict_a)->in_graph_p
871	|| ! hard_reg_set_intersect_p (x: profitable_hard_regs,
872	y: conflict_data
873	->profitable_hard_regs))
874	continue;
875	conflict_node = conflict_data->hard_regs_node;
876	conflict_node_set = conflict_node->hard_regs->set;
877	if (hard_reg_set_subset_p (x: node_set, y: conflict_node_set))
878	temp_node = node;
879	else
880	{
881	ira_assert (hard_reg_set_subset_p (conflict_node_set, node_set));
882	temp_node = conflict_node;
883	}
884	if (temp_node->check != node_check_tick)
885	{
886	temp_node->check = node_check_tick;
887	temp_node->conflict_size = 0;
888	}
889	size = (ira_reg_class_max_nregs
890	[ALLOCNO_CLASS (conflict_a)][ALLOCNO_MODE (conflict_a)]);
891	if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1)
892	/* We will deal with the subwords individually. */
893	size = 1;
894	temp_node->conflict_size += size;
895	}
896	}
897	for (i = 0; i < data->hard_regs_subnodes_num; i++)
898	{
899	allocno_hard_regs_node_t temp_node;
900
901	temp_node = allocno_hard_regs_nodes[i + node_preorder_num];
902	ira_assert (temp_node->preorder_num == i + node_preorder_num);
903	subnodes[i].left_conflict_size = (temp_node->check != node_check_tick
904	? 0 : temp_node->conflict_size);
905	if (hard_reg_set_subset_p (x: temp_node->hard_regs->set,
906	y: profitable_hard_regs))
907	subnodes[i].max_node_impact = temp_node->hard_regs_num;
908	else
909	{
910	HARD_REG_SET temp_set;
911	int j, n, hard_regno;
912	enum reg_class aclass;
913
914	temp_set = temp_node->hard_regs->set & profitable_hard_regs;
915	aclass = ALLOCNO_CLASS (a);
916	for (n = 0, j = ira_class_hard_regs_num[aclass] - 1; j >= 0; j--)
917	{
918	hard_regno = ira_class_hard_regs[aclass][j];
919	if (TEST_HARD_REG_BIT (set: temp_set, bit: hard_regno))
920	n++;
921	}
922	subnodes[i].max_node_impact = n;
923	}
924	subnodes[i].left_conflict_subnodes_size = 0;
925	}
926	start = node_preorder_num * allocno_hard_regs_nodes_num;
927	for (i = data->hard_regs_subnodes_num - 1; i > 0; i--)
928	{
929	int size, parent_i;
930	allocno_hard_regs_node_t parent;
931
932	size = (subnodes[i].left_conflict_subnodes_size
933	+ MIN (subnodes[i].max_node_impact
934	- subnodes[i].left_conflict_subnodes_size,
935	subnodes[i].left_conflict_size));
936	parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent;
937	gcc_checking_assert(parent);
938	parent_i
939	= allocno_hard_regs_subnode_index[start + parent->preorder_num];
940	gcc_checking_assert(parent_i >= 0);
941	subnodes[parent_i].left_conflict_subnodes_size += size;
942	}
943	left_conflict_subnodes_size = subnodes[0].left_conflict_subnodes_size;
944	conflict_size
945	= (left_conflict_subnodes_size
946	+ MIN (subnodes[0].max_node_impact - left_conflict_subnodes_size,
947	subnodes[0].left_conflict_size));
948	conflict_size += ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)];
949	data->colorable_p = conflict_size <= data->available_regs_num;
950	return data->colorable_p;
951	}
952
953	/* Update left conflict sizes of hard registers subnodes of allocno A
954	after removing allocno REMOVED_A with SIZE from the conflict graph.
955	Return TRUE if A is trivially colorable. */
956	static bool
957	update_left_conflict_sizes_p (ira_allocno_t a,
958	ira_allocno_t removed_a, int size)
959	{
960	int i, conflict_size, before_conflict_size, diff, start;
961	int node_preorder_num, parent_i;
962	allocno_hard_regs_node_t node, removed_node, parent;
963	allocno_hard_regs_subnode_t subnodes;
964	allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
965
966	ira_assert (! data->colorable_p);
967	node = data->hard_regs_node;
968	node_preorder_num = node->preorder_num;
969	removed_node = ALLOCNO_COLOR_DATA (removed_a)->hard_regs_node;
970	ira_assert (hard_reg_set_subset_p (removed_node->hard_regs->set,
971	node->hard_regs->set)
972	|| hard_reg_set_subset_p (node->hard_regs->set,
973	removed_node->hard_regs->set));
974	start = node_preorder_num * allocno_hard_regs_nodes_num;
975	i = allocno_hard_regs_subnode_index[start + removed_node->preorder_num];
976	if (i < 0)
977	i = 0;
978	subnodes = allocno_hard_regs_subnodes + data->hard_regs_subnodes_start;
979	before_conflict_size
980	= (subnodes[i].left_conflict_subnodes_size
981	+ MIN (subnodes[i].max_node_impact
982	- subnodes[i].left_conflict_subnodes_size,
983	subnodes[i].left_conflict_size));
984	subnodes[i].left_conflict_size -= size;
985	for (;;)
986	{
987	conflict_size
988	= (subnodes[i].left_conflict_subnodes_size
989	+ MIN (subnodes[i].max_node_impact
990	- subnodes[i].left_conflict_subnodes_size,
991	subnodes[i].left_conflict_size));
992	if ((diff = before_conflict_size - conflict_size) == 0)
993	break;
994	ira_assert (conflict_size < before_conflict_size);
995	parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent;
996	if (parent == NULL)
997	break;
998	parent_i
999	= allocno_hard_regs_subnode_index[start + parent->preorder_num];
1000	if (parent_i < 0)
1001	break;
1002	i = parent_i;
1003	before_conflict_size
1004	= (subnodes[i].left_conflict_subnodes_size
1005	+ MIN (subnodes[i].max_node_impact
1006	- subnodes[i].left_conflict_subnodes_size,
1007	subnodes[i].left_conflict_size));
1008	subnodes[i].left_conflict_subnodes_size -= diff;
1009	}
1010	if (i != 0
1011	|| (conflict_size
1012	+ ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]
1013	> data->available_regs_num))
1014	return false;
1015	data->colorable_p = true;
1016	return true;
1017	}
1018
1019	/* Return true if allocno A has empty profitable hard regs. */
1020	static bool
1021	empty_profitable_hard_regs (ira_allocno_t a)
1022	{
1023	allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
1024
1025	return hard_reg_set_empty_p (x: data->profitable_hard_regs);
1026	}
1027
1028	/* Set up profitable hard registers for each allocno being
1029	colored. */
1030	static void
1031	setup_profitable_hard_regs (void)
1032	{
1033	unsigned int i;
1034	int j, k, nobj, hard_regno, nregs, class_size;
1035	ira_allocno_t a;
1036	bitmap_iterator bi;
1037	enum reg_class aclass;
1038	machine_mode mode;
1039	allocno_color_data_t data;
1040
1041	/* Initial set up from allocno classes and explicitly conflicting
1042	hard regs. */
1043	EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1044	{
1045	a = ira_allocnos[i];
1046	if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS)
1047	continue;
1048	data = ALLOCNO_COLOR_DATA (a);
1049	if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL
1050	&& ALLOCNO_CLASS_COST (a) > ALLOCNO_MEMORY_COST (a)
1051	/* Do not empty profitable regs for static chain pointer
1052	pseudo when non-local goto is used. */
1053	&& ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
1054	CLEAR_HARD_REG_SET (set&: data->profitable_hard_regs);
1055	else
1056	{
1057	mode = ALLOCNO_MODE (a);
1058	data->profitable_hard_regs
1059	= ira_useful_class_mode_regs[aclass][mode];
1060	nobj = ALLOCNO_NUM_OBJECTS (a);
1061	for (k = 0; k < nobj; k++)
1062	{
1063	ira_object_t obj = ALLOCNO_OBJECT (a, k);
1064
1065	data->profitable_hard_regs
1066	&= ~OBJECT_TOTAL_CONFLICT_HARD_REGS (obj);
1067	}
1068	}
1069	}
1070	/* Exclude hard regs already assigned for conflicting objects. */
1071	EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, i, bi)
1072	{
1073	a = ira_allocnos[i];
1074	if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS
1075	|| ! ALLOCNO_ASSIGNED_P (a)
1076	|| (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0)
1077	continue;
1078	mode = ALLOCNO_MODE (a);
1079	nregs = hard_regno_nregs (regno: hard_regno, mode);
1080	nobj = ALLOCNO_NUM_OBJECTS (a);
1081	for (k = 0; k < nobj; k++)
1082	{
1083	ira_object_t obj = ALLOCNO_OBJECT (a, k);
1084	ira_object_t conflict_obj;
1085	ira_object_conflict_iterator oci;
1086
1087	FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1088	{
1089	ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1090
1091	/* We can process the conflict allocno repeatedly with
1092	the same result. */
1093	if (nregs == nobj && nregs > 1)
1094	{
1095	int num = OBJECT_SUBWORD (conflict_obj);
1096
1097	if (REG_WORDS_BIG_ENDIAN)
1098	CLEAR_HARD_REG_BIT
1099	(ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs,
1100	bit: hard_regno + nobj - num - 1);
1101	else
1102	CLEAR_HARD_REG_BIT
1103	(ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs,
1104	bit: hard_regno + num);
1105	}
1106	else
1107	ALLOCNO_COLOR_DATA (conflict_a)->profitable_hard_regs
1108	&= ~ira_reg_mode_hard_regset[hard_regno][mode];
1109	}
1110	}
1111	}
1112	/* Exclude too costly hard regs. */
1113	EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1114	{
1115	int min_cost = INT_MAX;
1116	int *costs;
1117
1118	a = ira_allocnos[i];
1119	if ((aclass = ALLOCNO_CLASS (a)) == NO_REGS
1120	|| empty_profitable_hard_regs (a))
1121	continue;
1122	data = ALLOCNO_COLOR_DATA (a);
1123	if ((costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a)) != NULL
1124	|| (costs = ALLOCNO_HARD_REG_COSTS (a)) != NULL)
1125	{
1126	class_size = ira_class_hard_regs_num[aclass];
1127	for (j = 0; j < class_size; j++)
1128	{
1129	hard_regno = ira_class_hard_regs[aclass][j];
1130	if (! TEST_HARD_REG_BIT (set: data->profitable_hard_regs,
1131	bit: hard_regno))
1132	continue;
1133	if (ALLOCNO_UPDATED_MEMORY_COST (a) < costs[j]
1134	/* Do not remove HARD_REGNO for static chain pointer
1135	pseudo when non-local goto is used. */
1136	&& ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
1137	CLEAR_HARD_REG_BIT (set&: data->profitable_hard_regs,
1138	bit: hard_regno);
1139	else if (min_cost > costs[j])
1140	min_cost = costs[j];
1141	}
1142	}
1143	else if (ALLOCNO_UPDATED_MEMORY_COST (a)
1144	< ALLOCNO_UPDATED_CLASS_COST (a)
1145	/* Do not empty profitable regs for static chain
1146	pointer pseudo when non-local goto is used. */
1147	&& ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
1148	CLEAR_HARD_REG_SET (set&: data->profitable_hard_regs);
1149	if (ALLOCNO_UPDATED_CLASS_COST (a) > min_cost)
1150	ALLOCNO_UPDATED_CLASS_COST (a) = min_cost;
1151	}
1152	}
1153
1154
1155
1156	/* This page contains functions used to choose hard registers for
1157	allocnos. */
1158
1159	/* Pool for update cost records. */
1160	static object_allocator<update_cost_record> update_cost_record_pool
1161	("update cost records");
1162
1163	/* Return new update cost record with given params. */
1164	static struct update_cost_record *
1165	get_update_cost_record (int hard_regno, int divisor,
1166	struct update_cost_record *next)
1167	{
1168	struct update_cost_record *record;
1169
1170	record = update_cost_record_pool.allocate ();
1171	record->hard_regno = hard_regno;
1172	record->divisor = divisor;
1173	record->next = next;
1174	return record;
1175	}
1176
1177	/* Free memory for all records in LIST. */
1178	static void
1179	free_update_cost_record_list (struct update_cost_record *list)
1180	{
1181	struct update_cost_record *next;
1182
1183	while (list != NULL)
1184	{
1185	next = list->next;
1186	update_cost_record_pool.remove (object: list);
1187	list = next;
1188	}
1189	}
1190
1191	/* Free memory allocated for all update cost records. */
1192	static void
1193	finish_update_cost_records (void)
1194	{
1195	update_cost_record_pool.release ();
1196	}
1197
1198	/* Array whose element value is TRUE if the corresponding hard
1199	register was already allocated for an allocno. */
1200	static bool allocated_hardreg_p[FIRST_PSEUDO_REGISTER];
1201
1202	/* Describes one element in a queue of allocnos whose costs need to be
1203	updated. Each allocno in the queue is known to have an allocno
1204	class. */
1205	struct update_cost_queue_elem
1206	{
1207	/* This element is in the queue iff CHECK == update_cost_check. */
1208	int check;
1209
1210	/* COST_HOP_DIVISOR**N, where N is the length of the shortest path
1211	connecting this allocno to the one being allocated. */
1212	int divisor;
1213
1214	/* Allocno from which we started chaining costs of connected
1215	allocnos. */
1216	ira_allocno_t start;
1217
1218	/* Allocno from which we are chaining costs of connected allocnos.
1219	It is used not go back in graph of allocnos connected by
1220	copies. */
1221	ira_allocno_t from;
1222
1223	/* The next allocno in the queue, or null if this is the last element. */
1224	ira_allocno_t next;
1225	};
1226
1227	/* The first element in a queue of allocnos whose copy costs need to be
1228	updated. Null if the queue is empty. */
1229	static ira_allocno_t update_cost_queue;
1230
1231	/* The last element in the queue described by update_cost_queue.
1232	Not valid if update_cost_queue is null. */
1233	static struct update_cost_queue_elem *update_cost_queue_tail;
1234
1235	/* A pool of elements in the queue described by update_cost_queue.
1236	Elements are indexed by ALLOCNO_NUM. */
1237	static struct update_cost_queue_elem *update_cost_queue_elems;
1238
1239	/* The current value of update_costs_from_copies call count. */
1240	static int update_cost_check;
1241
1242	/* Allocate and initialize data necessary for function
1243	update_costs_from_copies. */
1244	static void
1245	initiate_cost_update (void)
1246	{
1247	size_t size;
1248
1249	size = ira_allocnos_num * sizeof (struct update_cost_queue_elem);
1250	update_cost_queue_elems
1251	= (struct update_cost_queue_elem *) ira_allocate (size);
1252	memset (s: update_cost_queue_elems, c: 0, n: size);
1253	update_cost_check = 0;
1254	}
1255
1256	/* Deallocate data used by function update_costs_from_copies. */
1257	static void
1258	finish_cost_update (void)
1259	{
1260	ira_free (addr: update_cost_queue_elems);
1261	finish_update_cost_records ();
1262	}
1263
1264	/* When we traverse allocnos to update hard register costs, the cost
1265	divisor will be multiplied by the following macro value for each
1266	hop from given allocno to directly connected allocnos. */
1267	#define COST_HOP_DIVISOR 4
1268
1269	/* Start a new cost-updating pass. */
1270	static void
1271	start_update_cost (void)
1272	{
1273	update_cost_check++;
1274	update_cost_queue = NULL;
1275	}
1276
1277	/* Add (ALLOCNO, START, FROM, DIVISOR) to the end of update_cost_queue, unless
1278	ALLOCNO is already in the queue, or has NO_REGS class. */
1279	static inline void
1280	queue_update_cost (ira_allocno_t allocno, ira_allocno_t start,
1281	ira_allocno_t from, int divisor)
1282	{
1283	struct update_cost_queue_elem *elem;
1284
1285	elem = &update_cost_queue_elems[ALLOCNO_NUM (allocno)];
1286	if (elem->check != update_cost_check
1287	&& ALLOCNO_CLASS (allocno) != NO_REGS)
1288	{
1289	elem->check = update_cost_check;
1290	elem->start = start;
1291	elem->from = from;
1292	elem->divisor = divisor;
1293	elem->next = NULL;
1294	if (update_cost_queue == NULL)
1295	update_cost_queue = allocno;
1296	else
1297	update_cost_queue_tail->next = allocno;
1298	update_cost_queue_tail = elem;
1299	}
1300	}
1301
1302	/* Try to remove the first element from update_cost_queue. Return
1303	false if the queue was empty, otherwise make (*ALLOCNO, *START,
1304	*FROM, *DIVISOR) describe the removed element. */
1305	static inline bool
1306	get_next_update_cost (ira_allocno_t *allocno, ira_allocno_t *start,
1307	ira_allocno_t *from, int *divisor)
1308	{
1309	struct update_cost_queue_elem *elem;
1310
1311	if (update_cost_queue == NULL)
1312	return false;
1313
1314	*allocno = update_cost_queue;
1315	elem = &update_cost_queue_elems[ALLOCNO_NUM (*allocno)];
1316	*start = elem->start;
1317	*from = elem->from;
1318	*divisor = elem->divisor;
1319	update_cost_queue = elem->next;
1320	return true;
1321	}
1322
1323	/* Increase costs of HARD_REGNO by UPDATE_COST and conflict cost by
1324	UPDATE_CONFLICT_COST for ALLOCNO. Return true if we really
1325	modified the cost. */
1326	static bool
1327	update_allocno_cost (ira_allocno_t allocno, int hard_regno,
1328	int update_cost, int update_conflict_cost)
1329	{
1330	int i;
1331	enum reg_class aclass = ALLOCNO_CLASS (allocno);
1332
1333	i = ira_class_hard_reg_index[aclass][hard_regno];
1334	if (i < 0)
1335	return false;
1336	ira_allocate_and_set_or_copy_costs
1337	(vec: &ALLOCNO_UPDATED_HARD_REG_COSTS (allocno), aclass,
1338	ALLOCNO_UPDATED_CLASS_COST (allocno),
1339	ALLOCNO_HARD_REG_COSTS (allocno));
1340	ira_allocate_and_set_or_copy_costs
1341	(vec: &ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno),
1342	aclass, val: 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (allocno));
1343	ALLOCNO_UPDATED_HARD_REG_COSTS (allocno)[i] += update_cost;
1344	ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno)[i] += update_conflict_cost;
1345	return true;
1346	}
1347
1348	/* Return TRUE if the object OBJ conflicts with the allocno A. */
1349	static bool
1350	object_conflicts_with_allocno_p (ira_object_t obj, ira_allocno_t a)
1351	{
1352	if (!OBJECT_CONFLICT_VEC_P (obj))
1353	for (int word = 0; word < ALLOCNO_NUM_OBJECTS (a); word++)
1354	{
1355	ira_object_t another_obj = ALLOCNO_OBJECT (a, word);
1356	if (OBJECT_CONFLICT_ID (another_obj) >= OBJECT_MIN (obj)
1357	&& OBJECT_CONFLICT_ID (another_obj) <= OBJECT_MAX (obj)
1358	&& TEST_MINMAX_SET_BIT (OBJECT_CONFLICT_BITVEC (obj),
1359	OBJECT_CONFLICT_ID (another_obj),
1360	OBJECT_MIN (obj), OBJECT_MAX (obj)))
1361	return true;
1362	}
1363	else
1364	{
1365	/* If this linear walk ever becomes a bottleneck we could add a
1366	conflict_vec_sorted_p flag and if not set, sort the conflicts after
1367	their ID so we can use a binary search. That would also require
1368	tracking the actual number of conflicts in the vector to not rely
1369	on the NULL termination. */
1370	ira_object_conflict_iterator oci;
1371	ira_object_t conflict_obj;
1372	FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1373	if (OBJECT_ALLOCNO (conflict_obj) == a)
1374	return true;
1375	}
1376	return false;
1377	}
1378
1379	/* Return TRUE if allocnos A1 and A2 conflicts. Here we are
1380	interested only in conflicts of allocnos with intersecting allocno
1381	classes. */
1382	static bool
1383	allocnos_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
1384	{
1385	/* Compute the upper bound for the linear iteration when the object
1386	conflicts are represented as a sparse vector. In particular this
1387	will make sure we prefer O(1) bitvector testing. */
1388	int num_conflicts_in_vec1 = 0, num_conflicts_in_vec2 = 0;
1389	for (int word = 0; word < ALLOCNO_NUM_OBJECTS (a1); ++word)
1390	if (OBJECT_CONFLICT_VEC_P (ALLOCNO_OBJECT (a1, word)))
1391	num_conflicts_in_vec1 += OBJECT_NUM_CONFLICTS (ALLOCNO_OBJECT (a1, word));
1392	for (int word = 0; word < ALLOCNO_NUM_OBJECTS (a2); ++word)
1393	if (OBJECT_CONFLICT_VEC_P (ALLOCNO_OBJECT (a2, word)))
1394	num_conflicts_in_vec2 += OBJECT_NUM_CONFLICTS (ALLOCNO_OBJECT (a2, word));
1395	if (num_conflicts_in_vec2 < num_conflicts_in_vec1)
1396	std::swap (a&: a1, b&: a2);
1397
1398	for (int word = 0; word < ALLOCNO_NUM_OBJECTS (a1); word++)
1399	{
1400	ira_object_t obj = ALLOCNO_OBJECT (a1, word);
1401	/* Take preferences of conflicting allocnos into account. */
1402	if (object_conflicts_with_allocno_p (obj, a: a2))
1403	return true;
1404	}
1405	return false;
1406	}
1407
1408	/* Update (decrease if DECR_P) HARD_REGNO cost of allocnos connected
1409	by copies to ALLOCNO to increase chances to remove some copies as
1410	the result of subsequent assignment. Update conflict costs.
1411	Record cost updates if RECORD_P is true. */
1412	static void
1413	update_costs_from_allocno (ira_allocno_t allocno, int hard_regno,
1414	int divisor, bool decr_p, bool record_p)
1415	{
1416	int cost, update_cost, update_conflict_cost;
1417	machine_mode mode;
1418	enum reg_class rclass, aclass;
1419	ira_allocno_t another_allocno, start = allocno, from = NULL;
1420	ira_copy_t cp, next_cp;
1421
1422	rclass = REGNO_REG_CLASS (hard_regno);
1423	do
1424	{
1425	mode = ALLOCNO_MODE (allocno);
1426	ira_init_register_move_cost_if_necessary (mode);
1427	for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
1428	{
1429	if (cp->first == allocno)
1430	{
1431	next_cp = cp->next_first_allocno_copy;
1432	another_allocno = cp->second;
1433	}
1434	else if (cp->second == allocno)
1435	{
1436	next_cp = cp->next_second_allocno_copy;
1437	another_allocno = cp->first;
1438	}
1439	else
1440	gcc_unreachable ();
1441
1442	if (another_allocno == from
1443	|| (ALLOCNO_COLOR_DATA (another_allocno) != NULL
1444	&& (ALLOCNO_COLOR_DATA (allocno)->first_thread_allocno
1445	!= ALLOCNO_COLOR_DATA (another_allocno)->first_thread_allocno)))
1446	continue;
1447
1448	aclass = ALLOCNO_CLASS (another_allocno);
1449	if (! TEST_HARD_REG_BIT (reg_class_contents[aclass],
1450	bit: hard_regno)
1451	|| ALLOCNO_ASSIGNED_P (another_allocno))
1452	continue;
1453
1454	/* If we have different modes use the smallest one. It is
1455	a sub-register move. It is hard to predict what LRA
1456	will reload (the pseudo or its sub-register) but LRA
1457	will try to minimize the data movement. Also for some
1458	register classes bigger modes might be invalid,
1459	e.g. DImode for AREG on x86. For such cases the
1460	register move cost will be maximal. */
1461	mode = narrower_subreg_mode (ALLOCNO_MODE (cp->first),
1462	ALLOCNO_MODE (cp->second));
1463
1464	ira_init_register_move_cost_if_necessary (mode);
1465
1466	cost = (cp->second == allocno
1467	? ira_register_move_cost[mode][rclass][aclass]
1468	: ira_register_move_cost[mode][aclass][rclass]);
1469	if (decr_p)
1470	cost = -cost;
1471
1472	update_cost = cp->freq * cost / divisor;
1473	update_conflict_cost = update_cost;
1474
1475	if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL)
1476	fprintf (stream: ira_dump_file,
1477	format: " a%dr%d (hr%d): update cost by %d, conflict cost by %d\n",
1478	ALLOCNO_NUM (another_allocno), ALLOCNO_REGNO (another_allocno),
1479	hard_regno, update_cost, update_conflict_cost);
1480	if (update_cost == 0)
1481	continue;
1482
1483	if (! update_allocno_cost (allocno: another_allocno, hard_regno,
1484	update_cost, update_conflict_cost))
1485	continue;
1486	queue_update_cost (allocno: another_allocno, start, from: allocno,
1487	divisor: divisor * COST_HOP_DIVISOR);
1488	if (record_p && ALLOCNO_COLOR_DATA (another_allocno) != NULL)
1489	ALLOCNO_COLOR_DATA (another_allocno)->update_cost_records
1490	= get_update_cost_record (hard_regno, divisor,
1491	ALLOCNO_COLOR_DATA (another_allocno)
1492	->update_cost_records);
1493	}
1494	}
1495	while (get_next_update_cost (allocno: &allocno, start: &start, from: &from, divisor: &divisor));
1496	}
1497
1498	/* Decrease preferred ALLOCNO hard register costs and costs of
1499	allocnos connected to ALLOCNO through copy. */
1500	static void
1501	update_costs_from_prefs (ira_allocno_t allocno)
1502	{
1503	ira_pref_t pref;
1504
1505	start_update_cost ();
1506	for (pref = ALLOCNO_PREFS (allocno); pref != NULL; pref = pref->next_pref)
1507	{
1508	if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL)
1509	fprintf (stream: ira_dump_file, format: " Start updating from pref of hr%d for a%dr%d:\n",
1510	pref->hard_regno, ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno));
1511	update_costs_from_allocno (allocno, hard_regno: pref->hard_regno,
1512	COST_HOP_DIVISOR, decr_p: true, record_p: true);
1513	}
1514	}
1515
1516	/* Update (decrease if DECR_P) the cost of allocnos connected to
1517	ALLOCNO through copies to increase chances to remove some copies as
1518	the result of subsequent assignment. ALLOCNO was just assigned to
1519	a hard register. Record cost updates if RECORD_P is true. */
1520	static void
1521	update_costs_from_copies (ira_allocno_t allocno, bool decr_p, bool record_p)
1522	{
1523	int hard_regno;
1524
1525	hard_regno = ALLOCNO_HARD_REGNO (allocno);
1526	ira_assert (hard_regno >= 0 && ALLOCNO_CLASS (allocno) != NO_REGS);
1527	start_update_cost ();
1528	if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL)
1529	fprintf (stream: ira_dump_file, format: " Start updating from a%dr%d by copies:\n",
1530	ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno));
1531	update_costs_from_allocno (allocno, hard_regno, divisor: 1, decr_p, record_p);
1532	}
1533
1534	/* Update conflict_allocno_hard_prefs of allocnos conflicting with
1535	ALLOCNO. */
1536	static void
1537	update_conflict_allocno_hard_prefs (ira_allocno_t allocno)
1538	{
1539	int l, nr = ALLOCNO_NUM_OBJECTS (allocno);
1540
1541	for (l = 0; l < nr; l++)
1542	{
1543	ira_object_t conflict_obj, obj = ALLOCNO_OBJECT (allocno, l);
1544	ira_object_conflict_iterator oci;
1545
1546	FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
1547	{
1548	ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
1549	allocno_color_data_t conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
1550	ira_pref_t pref;
1551
1552	if (!(hard_reg_set_intersect_p
1553	(ALLOCNO_COLOR_DATA (allocno)->profitable_hard_regs,
1554	y: conflict_data->profitable_hard_regs)))
1555	continue;
1556	for (pref = ALLOCNO_PREFS (allocno);
1557	pref != NULL;
1558	pref = pref->next_pref)
1559	conflict_data->conflict_allocno_hard_prefs += pref->freq;
1560	}
1561	}
1562	}
1563
1564	/* Restore costs of allocnos connected to ALLOCNO by copies as it was
1565	before updating costs of these allocnos from given allocno. This
1566	is a wise thing to do as if given allocno did not get an expected
1567	hard reg, using smaller cost of the hard reg for allocnos connected
1568	by copies to given allocno becomes actually misleading. Free all
1569	update cost records for ALLOCNO as we don't need them anymore. */
1570	static void
1571	restore_costs_from_copies (ira_allocno_t allocno)
1572	{
1573	struct update_cost_record *records, *curr;
1574
1575	if (ALLOCNO_COLOR_DATA (allocno) == NULL)
1576	return;
1577	records = ALLOCNO_COLOR_DATA (allocno)->update_cost_records;
1578	start_update_cost ();
1579	if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL)
1580	fprintf (stream: ira_dump_file, format: " Start restoring from a%dr%d:\n",
1581	ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno));
1582	for (curr = records; curr != NULL; curr = curr->next)
1583	update_costs_from_allocno (allocno, hard_regno: curr->hard_regno,
1584	divisor: curr->divisor, decr_p: true, record_p: false);
1585	free_update_cost_record_list (list: records);
1586	ALLOCNO_COLOR_DATA (allocno)->update_cost_records = NULL;
1587	}
1588
1589	/* This function updates COSTS (decrease if DECR_P) for hard_registers
1590	of ACLASS by conflict costs of the unassigned allocnos
1591	connected by copies with allocnos in update_cost_queue. This
1592	update increases chances to remove some copies. */
1593	static void
1594	update_conflict_hard_regno_costs (int *costs, enum reg_class aclass,
1595	bool decr_p)
1596	{
1597	int i, cost, class_size, freq, mult, div, divisor;
1598	int index, hard_regno;
1599	int *conflict_costs;
1600	bool cont_p;
1601	enum reg_class another_aclass;
1602	ira_allocno_t allocno, another_allocno, start, from;
1603	ira_copy_t cp, next_cp;
1604
1605	while (get_next_update_cost (allocno: &allocno, start: &start, from: &from, divisor: &divisor))
1606	for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
1607	{
1608	if (cp->first == allocno)
1609	{
1610	next_cp = cp->next_first_allocno_copy;
1611	another_allocno = cp->second;
1612	}
1613	else if (cp->second == allocno)
1614	{
1615	next_cp = cp->next_second_allocno_copy;
1616	another_allocno = cp->first;
1617	}
1618	else
1619	gcc_unreachable ();
1620
1621	another_aclass = ALLOCNO_CLASS (another_allocno);
1622	if (another_allocno == from
1623	|| ALLOCNO_ASSIGNED_P (another_allocno)
1624	|| ALLOCNO_COLOR_DATA (another_allocno)->may_be_spilled_p
1625	|| ! ira_reg_classes_intersect_p[aclass][another_aclass])
1626	continue;
1627	if (allocnos_conflict_p (a1: another_allocno, a2: start))
1628	continue;
1629
1630	class_size = ira_class_hard_regs_num[another_aclass];
1631	ira_allocate_and_copy_costs
1632	(vec: &ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
1633	aclass: another_aclass, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
1634	conflict_costs
1635	= ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno);
1636	if (conflict_costs == NULL)
1637	cont_p = true;
1638	else
1639	{
1640	mult = cp->freq;
1641	freq = ALLOCNO_FREQ (another_allocno);
1642	if (freq == 0)
1643	freq = 1;
1644	div = freq * divisor;
1645	cont_p = false;
1646	for (i = class_size - 1; i >= 0; i--)
1647	{
1648	hard_regno = ira_class_hard_regs[another_aclass][i];
1649	ira_assert (hard_regno >= 0);
1650	index = ira_class_hard_reg_index[aclass][hard_regno];
1651	if (index < 0)
1652	continue;
1653	cost = (int) (((int64_t) conflict_costs [i] * mult) / div);
1654	if (cost == 0)
1655	continue;
1656	cont_p = true;
1657	if (decr_p)
1658	cost = -cost;
1659	costs[index] += cost;
1660	}
1661	}
1662	/* Probably 5 hops will be enough. */
1663	if (cont_p
1664	&& divisor <= (COST_HOP_DIVISOR
1665	* COST_HOP_DIVISOR
1666	* COST_HOP_DIVISOR
1667	* COST_HOP_DIVISOR))
1668	queue_update_cost (allocno: another_allocno, start, from, divisor: divisor * COST_HOP_DIVISOR);
1669	}
1670	}
1671
1672	/* Set up conflicting (through CONFLICT_REGS) for each object of
1673	allocno A and the start allocno profitable regs (through
1674	START_PROFITABLE_REGS). Remember that the start profitable regs
1675	exclude hard regs which cannot hold value of mode of allocno A.
1676	This covers mostly cases when multi-register value should be
1677	aligned. */
1678	static inline void
1679	get_conflict_and_start_profitable_regs (ira_allocno_t a, bool retry_p,
1680	HARD_REG_SET *conflict_regs,
1681	HARD_REG_SET *start_profitable_regs)
1682	{
1683	int i, nwords;
1684	ira_object_t obj;
1685
1686	nwords = ALLOCNO_NUM_OBJECTS (a);
1687	for (i = 0; i < nwords; i++)
1688	{
1689	obj = ALLOCNO_OBJECT (a, i);
1690	conflict_regs[i] = OBJECT_TOTAL_CONFLICT_HARD_REGS (obj);
1691	}
1692	if (retry_p)
1693	*start_profitable_regs
1694	= (reg_class_contents[ALLOCNO_CLASS (a)]
1695	&~ (ira_prohibited_class_mode_regs
1696	[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]));
1697	else
1698	*start_profitable_regs = ALLOCNO_COLOR_DATA (a)->profitable_hard_regs;
1699	}
1700
1701	/* Return true if HARD_REGNO is ok for assigning to allocno A with
1702	PROFITABLE_REGS and whose objects have CONFLICT_REGS. */
1703	static inline bool
1704	check_hard_reg_p (ira_allocno_t a, int hard_regno,
1705	HARD_REG_SET *conflict_regs, HARD_REG_SET profitable_regs)
1706	{
1707	int j, nwords, nregs;
1708	enum reg_class aclass;
1709	machine_mode mode;
1710
1711	aclass = ALLOCNO_CLASS (a);
1712	mode = ALLOCNO_MODE (a);
1713	if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[aclass][mode],
1714	bit: hard_regno))
1715	return false;
1716	/* Checking only profitable hard regs. */
1717	if (! TEST_HARD_REG_BIT (set: profitable_regs, bit: hard_regno))
1718	return false;
1719	nregs = hard_regno_nregs (regno: hard_regno, mode);
1720	nwords = ALLOCNO_NUM_OBJECTS (a);
1721	for (j = 0; j < nregs; j++)
1722	{
1723	int k;
1724	int set_to_test_start = 0, set_to_test_end = nwords;
1725
1726	if (nregs == nwords)
1727	{
1728	if (REG_WORDS_BIG_ENDIAN)
1729	set_to_test_start = nwords - j - 1;
1730	else
1731	set_to_test_start = j;
1732	set_to_test_end = set_to_test_start + 1;
1733	}
1734	for (k = set_to_test_start; k < set_to_test_end; k++)
1735	if (TEST_HARD_REG_BIT (set: conflict_regs[k], bit: hard_regno + j))
1736	break;
1737	if (k != set_to_test_end)
1738	break;
1739	}
1740	return j == nregs;
1741	}
1742
1743	/* Return number of registers needed to be saved and restored at
1744	function prologue/epilogue if we allocate HARD_REGNO to hold value
1745	of MODE. */
1746	static int
1747	calculate_saved_nregs (int hard_regno, machine_mode mode)
1748	{
1749	int i;
1750	int nregs = 0;
1751
1752	ira_assert (hard_regno >= 0);
1753	for (i = hard_regno_nregs (regno: hard_regno, mode) - 1; i >= 0; i--)
1754	if (!allocated_hardreg_p[hard_regno + i]
1755	&& !crtl->abi->clobbers_full_reg_p (regno: hard_regno + i)
1756	&& !LOCAL_REGNO (hard_regno + i))
1757	nregs++;
1758	return nregs;
1759	}
1760
1761	/* Allocnos A1 and A2 are known to conflict. Check whether, in some loop L
1762	that is either the current loop or a nested subloop, the conflict is of
1763	the following form:
1764
1765	- One allocno (X) is a cap allocno for some non-cap allocno X2.
1766
1767	- X2 belongs to some loop L2.
1768
1769	- The other allocno (Y) is a non-cap allocno.
1770
1771	- Y is an ancestor of some allocno Y2 in L2. (Note that such a Y2
1772	must exist, given that X and Y conflict.)
1773
1774	- Y2 is not referenced in L2 (that is, ALLOCNO_NREFS (Y2) == 0).
1775
1776	- Y can use a different allocation from Y2.
1777
1778	In this case, Y's register is live across L2 but is not used within it,
1779	whereas X's register is used only within L2. The conflict is therefore
1780	only "soft", in that it can easily be avoided by spilling Y2 inside L2
1781	without affecting any insn references.
1782
1783	If the conflict does have this form, return the Y2 that would need to be
1784	spilled in order to allow X and Y (and thus A1 and A2) to use the same
1785	register. Return null otherwise. Returning null is conservatively correct;
1786	any nonnnull return value is an optimization. */
1787	ira_allocno_t
1788	ira_soft_conflict (ira_allocno_t a1, ira_allocno_t a2)
1789	{
1790	/* Search for the loop L and its associated allocnos X and Y. */
1791	int search_depth = 0;
1792	while (ALLOCNO_CAP_MEMBER (a1) && ALLOCNO_CAP_MEMBER (a2))
1793	{
1794	a1 = ALLOCNO_CAP_MEMBER (a1);
1795	a2 = ALLOCNO_CAP_MEMBER (a2);
1796	if (search_depth++ > max_soft_conflict_loop_depth)
1797	return nullptr;
1798	}
1799	/* This must be true if A1 and A2 conflict. */
1800	ira_assert (ALLOCNO_LOOP_TREE_NODE (a1) == ALLOCNO_LOOP_TREE_NODE (a2));
1801
1802	/* Make A1 the cap allocno (X in the comment above) and A2 the
1803	non-cap allocno (Y in the comment above). */
1804	if (ALLOCNO_CAP_MEMBER (a2))
1805	std::swap (a&: a1, b&: a2);
1806	if (!ALLOCNO_CAP_MEMBER (a1))
1807	return nullptr;
1808
1809	/* Search for the real allocno that A1 caps (X2 in the comment above). */
1810	do
1811	{
1812	a1 = ALLOCNO_CAP_MEMBER (a1);
1813	if (search_depth++ > max_soft_conflict_loop_depth)
1814	return nullptr;
1815	}
1816	while (ALLOCNO_CAP_MEMBER (a1));
1817
1818	/* Find the associated allocno for A2 (Y2 in the comment above). */
1819	auto node = ALLOCNO_LOOP_TREE_NODE (a1);
1820	auto local_a2 = node->regno_allocno_map[ALLOCNO_REGNO (a2)];
1821
1822	/* Find the parent of LOCAL_A2/Y2. LOCAL_A2 must be a descendant of A2
1823	for the conflict query to make sense, so this parent lookup must succeed.
1824
1825	If the parent allocno has no references, it is usually cheaper to
1826	spill at that loop level instead. Keep searching until we find
1827	a parent allocno that does have references (but don't look past
1828	the starting allocno). */
1829	ira_allocno_t local_parent_a2;
1830	for (;;)
1831	{
1832	local_parent_a2 = ira_parent_allocno (local_a2);
1833	if (local_parent_a2 == a2 || ALLOCNO_NREFS (local_parent_a2) != 0)
1834	break;
1835	local_a2 = local_parent_a2;
1836	}
1837	if (CHECKING_P)
1838	{
1839	/* Sanity check to make sure that the conflict we've been given
1840	makes sense. */
1841	auto test_a2 = local_parent_a2;
1842	while (test_a2 != a2)
1843	{
1844	test_a2 = ira_parent_allocno (test_a2);
1845	ira_assert (test_a2);
1846	}
1847	}
1848	if (local_a2
1849	&& ALLOCNO_NREFS (local_a2) == 0
1850	&& ira_subloop_allocnos_can_differ_p (a: local_parent_a2))
1851	return local_a2;
1852	return nullptr;
1853	}
1854
1855	/* The caller has decided to allocate HREGNO to A and has proved that
1856	this is safe. However, the allocation might require the kind of
1857	spilling described in the comment above ira_soft_conflict.
1858	The caller has recorded that:
1859
1860	- The allocnos in ALLOCNOS_TO_SPILL are the ones that would need
1861	to be spilled to satisfy soft conflicts for at least one allocation
1862	(not necessarily HREGNO).
1863
1864	- The soft conflicts apply only to A allocations that overlap
1865	SOFT_CONFLICT_REGS.
1866
1867	If allocating HREGNO is subject to any soft conflicts, record the
1868	subloop allocnos that need to be spilled. */
1869	static void
1870	spill_soft_conflicts (ira_allocno_t a, bitmap allocnos_to_spill,
1871	HARD_REG_SET soft_conflict_regs, int hregno)
1872	{
1873	auto nregs = hard_regno_nregs (regno: hregno, ALLOCNO_MODE (a));
1874	bitmap_iterator bi;
1875	unsigned int i;
1876	EXECUTE_IF_SET_IN_BITMAP (allocnos_to_spill, 0, i, bi)
1877	{
1878	/* SPILL_A needs to be spilled for at least one allocation
1879	(not necessarily this one). */
1880	auto spill_a = ira_allocnos[i];
1881
1882	/* Find the corresponding allocno for this loop. */
1883	auto conflict_a = spill_a;
1884	do
1885	{
1886	conflict_a = ira_parent_or_cap_allocno (conflict_a);
1887	ira_assert (conflict_a);
1888	}
1889	while (ALLOCNO_LOOP_TREE_NODE (conflict_a)->level
1890	> ALLOCNO_LOOP_TREE_NODE (a)->level);
1891
1892	ira_assert (ALLOCNO_LOOP_TREE_NODE (conflict_a)
1893	== ALLOCNO_LOOP_TREE_NODE (a));
1894
1895	if (conflict_a == a)
1896	{
1897	/* SPILL_A is a descendant of A. We don't know (and don't need
1898	to know) which cap allocnos have a soft conflict with A.
1899	All we need to do is test whether the soft conflict applies
1900	to the chosen allocation. */
1901	if (ira_hard_reg_set_intersection_p (hard_regno: hregno, ALLOCNO_MODE (a),
1902	hard_regset: soft_conflict_regs))
1903	ALLOCNO_MIGHT_CONFLICT_WITH_PARENT_P (spill_a) = true;
1904	}
1905	else
1906	{
1907	/* SPILL_A is a descendant of CONFLICT_A, which has a soft conflict
1908	with A. Test whether the soft conflict applies to the current
1909	allocation. */
1910	ira_assert (ira_soft_conflict (a, conflict_a) == spill_a);
1911	auto conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a);
1912	ira_assert (conflict_hregno >= 0);
1913	auto conflict_nregs = hard_regno_nregs (regno: conflict_hregno,
1914	ALLOCNO_MODE (conflict_a));
1915	if (hregno + nregs > conflict_hregno
1916	&& conflict_hregno + conflict_nregs > hregno)
1917	ALLOCNO_MIGHT_CONFLICT_WITH_PARENT_P (spill_a) = true;
1918	}
1919	}
1920	}
1921
1922	/* Choose a hard register for allocno A. If RETRY_P is TRUE, it means
1923	that the function called from function
1924	`ira_reassign_conflict_allocnos' and `allocno_reload_assign'. In
1925	this case some allocno data are not defined or updated and we
1926	should not touch these data. The function returns true if we
1927	managed to assign a hard register to the allocno.
1928
1929	To assign a hard register, first of all we calculate all conflict
1930	hard registers which can come from conflicting allocnos with
1931	already assigned hard registers. After that we find first free
1932	hard register with the minimal cost. During hard register cost
1933	calculation we take conflict hard register costs into account to
1934	give a chance for conflicting allocnos to get a better hard
1935	register in the future.
1936
1937	If the best hard register cost is bigger than cost of memory usage
1938	for the allocno, we don't assign a hard register to given allocno
1939	at all.
1940
1941	If we assign a hard register to the allocno, we update costs of the
1942	hard register for allocnos connected by copies to improve a chance
1943	to coalesce insns represented by the copies when we assign hard
1944	registers to the allocnos connected by the copies. */
1945	static bool
1946	assign_hard_reg (ira_allocno_t a, bool retry_p)
1947	{
1948	HARD_REG_SET conflicting_regs[2], profitable_hard_regs;
1949	int i, j, hard_regno, best_hard_regno, class_size;
1950	int cost, mem_cost, min_cost, full_cost, min_full_cost, nwords, word;
1951	int *a_costs;
1952	enum reg_class aclass;
1953	machine_mode mode;
1954	static int costs[FIRST_PSEUDO_REGISTER], full_costs[FIRST_PSEUDO_REGISTER];
1955	int saved_nregs;
1956	enum reg_class rclass;
1957	int add_cost;
1958	#ifdef STACK_REGS
1959	bool no_stack_reg_p;
1960	#endif
1961	auto_bitmap allocnos_to_spill;
1962	HARD_REG_SET soft_conflict_regs = {};
1963
1964	ira_assert (! ALLOCNO_ASSIGNED_P (a));
1965	get_conflict_and_start_profitable_regs (a, retry_p,
1966	conflict_regs: conflicting_regs,
1967	start_profitable_regs: &profitable_hard_regs);
1968	aclass = ALLOCNO_CLASS (a);
1969	class_size = ira_class_hard_regs_num[aclass];
1970	best_hard_regno = -1;
1971	mem_cost = 0;
1972	memset (s: costs, c: 0, n: sizeof (int) * class_size);
1973	memset (s: full_costs, c: 0, n: sizeof (int) * class_size);
1974	#ifdef STACK_REGS
1975	no_stack_reg_p = false;
1976	#endif
1977	if (! retry_p)
1978	start_update_cost ();
1979	mem_cost += ALLOCNO_UPDATED_MEMORY_COST (a);
1980
1981	ira_allocate_and_copy_costs (vec: &ALLOCNO_UPDATED_HARD_REG_COSTS (a),
1982	aclass, ALLOCNO_HARD_REG_COSTS (a));
1983	a_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
1984	#ifdef STACK_REGS
1985	no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a);
1986	#endif
1987	cost = ALLOCNO_UPDATED_CLASS_COST (a);
1988	for (i = 0; i < class_size; i++)
1989	if (a_costs != NULL)
1990	{
1991	costs[i] += a_costs[i];
1992	full_costs[i] += a_costs[i];
1993	}
1994	else
1995	{
1996	costs[i] += cost;
1997	full_costs[i] += cost;
1998	}
1999	nwords = ALLOCNO_NUM_OBJECTS (a);
2000	curr_allocno_process++;
2001	for (word = 0; word < nwords; word++)
2002	{
2003	ira_object_t conflict_obj;
2004	ira_object_t obj = ALLOCNO_OBJECT (a, word);
2005	ira_object_conflict_iterator oci;
2006
2007	/* Take preferences of conflicting allocnos into account. */
2008	FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2009	{
2010	ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2011	enum reg_class conflict_aclass;
2012	allocno_color_data_t data = ALLOCNO_COLOR_DATA (conflict_a);
2013
2014	/* Reload can give another class so we need to check all
2015	allocnos. */
2016	if (!retry_p
2017	&& ((!ALLOCNO_ASSIGNED_P (conflict_a)
2018	|| ALLOCNO_HARD_REGNO (conflict_a) < 0)
2019	&& !(hard_reg_set_intersect_p
2020	(x: profitable_hard_regs,
2021	ALLOCNO_COLOR_DATA
2022	(conflict_a)->profitable_hard_regs))))
2023	{
2024	/* All conflict allocnos are in consideration bitmap
2025	when retry_p is false. It might change in future and
2026	if it happens the assert will be broken. It means
2027	the code should be modified for the new
2028	assumptions. */
2029	ira_assert (bitmap_bit_p (consideration_allocno_bitmap,
2030	ALLOCNO_NUM (conflict_a)));
2031	continue;
2032	}
2033	conflict_aclass = ALLOCNO_CLASS (conflict_a);
2034	ira_assert (ira_reg_classes_intersect_p
2035	[aclass][conflict_aclass]);
2036	if (ALLOCNO_ASSIGNED_P (conflict_a))
2037	{
2038	hard_regno = ALLOCNO_HARD_REGNO (conflict_a);
2039	if (hard_regno >= 0
2040	&& (ira_hard_reg_set_intersection_p
2041	(hard_regno, ALLOCNO_MODE (conflict_a),
2042	reg_class_contents[aclass])))
2043	{
2044	int n_objects = ALLOCNO_NUM_OBJECTS (conflict_a);
2045	int conflict_nregs;
2046
2047	mode = ALLOCNO_MODE (conflict_a);
2048	conflict_nregs = hard_regno_nregs (regno: hard_regno, mode);
2049	auto spill_a = (retry_p
2050	? nullptr
2051	: ira_soft_conflict (a1: a, a2: conflict_a));
2052	if (spill_a)
2053	{
2054	if (bitmap_set_bit (allocnos_to_spill,
2055	ALLOCNO_NUM (spill_a)))
2056	{
2057	ira_loop_border_costs border_costs (spill_a);
2058	auto cost = border_costs.spill_inside_loop_cost ();
2059	auto note_conflict = [&](int r)
2060	{
2061	SET_HARD_REG_BIT (set&: soft_conflict_regs, bit: r);
2062	auto hri = ira_class_hard_reg_index[aclass][r];
2063	if (hri >= 0)
2064	{
2065	costs[hri] += cost;
2066	full_costs[hri] += cost;
2067	}
2068	};
2069	for (int r = hard_regno;
2070	r >= 0 && (int) end_hard_regno (mode, regno: r) > hard_regno;
2071	r--)
2072	note_conflict (r);
2073	for (int r = hard_regno + 1;
2074	r < hard_regno + conflict_nregs;
2075	r++)
2076	note_conflict (r);
2077	}
2078	}
2079	else
2080	{
2081	if (conflict_nregs == n_objects && conflict_nregs > 1)
2082	{
2083	int num = OBJECT_SUBWORD (conflict_obj);
2084
2085	if (REG_WORDS_BIG_ENDIAN)
2086	SET_HARD_REG_BIT (set&: conflicting_regs[word],
2087	bit: hard_regno + n_objects - num - 1);
2088	else
2089	SET_HARD_REG_BIT (set&: conflicting_regs[word],
2090	bit: hard_regno + num);
2091	}
2092	else
2093	conflicting_regs[word]
2094	|= ira_reg_mode_hard_regset[hard_regno][mode];
2095	if (hard_reg_set_subset_p (x: profitable_hard_regs,
2096	y: conflicting_regs[word]))
2097	goto fail;
2098	}
2099	}
2100	}
2101	else if (! retry_p
2102	&& ! ALLOCNO_COLOR_DATA (conflict_a)->may_be_spilled_p
2103	/* Don't process the conflict allocno twice. */
2104	&& (ALLOCNO_COLOR_DATA (conflict_a)->last_process
2105	!= curr_allocno_process))
2106	{
2107	int k, *conflict_costs;
2108
2109	ALLOCNO_COLOR_DATA (conflict_a)->last_process
2110	= curr_allocno_process;
2111	ira_allocate_and_copy_costs
2112	(vec: &ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a),
2113	aclass: conflict_aclass,
2114	ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_a));
2115	conflict_costs
2116	= ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_a);
2117	if (conflict_costs != NULL)
2118	for (j = class_size - 1; j >= 0; j--)
2119	{
2120	hard_regno = ira_class_hard_regs[aclass][j];
2121	ira_assert (hard_regno >= 0);
2122	k = ira_class_hard_reg_index[conflict_aclass][hard_regno];
2123	if (k < 0
2124	/* If HARD_REGNO is not available for CONFLICT_A,
2125	the conflict would be ignored, since HARD_REGNO
2126	will never be assigned to CONFLICT_A. */
2127	|| !TEST_HARD_REG_BIT (set: data->profitable_hard_regs,
2128	bit: hard_regno))
2129	continue;
2130	full_costs[j] -= conflict_costs[k];
2131	}
2132	queue_update_cost (allocno: conflict_a, start: conflict_a, NULL, COST_HOP_DIVISOR);
2133	}
2134	}
2135	}
2136	if (! retry_p)
2137	/* Take into account preferences of allocnos connected by copies to
2138	the conflict allocnos. */
2139	update_conflict_hard_regno_costs (costs: full_costs, aclass, decr_p: true);
2140
2141	/* Take preferences of allocnos connected by copies into
2142	account. */
2143	if (! retry_p)
2144	{
2145	start_update_cost ();
2146	queue_update_cost (allocno: a, start: a, NULL, COST_HOP_DIVISOR);
2147	update_conflict_hard_regno_costs (costs: full_costs, aclass, decr_p: false);
2148	}
2149	min_cost = min_full_cost = INT_MAX;
2150	/* We don't care about giving callee saved registers to allocnos no
2151	living through calls because call clobbered registers are
2152	allocated first (it is usual practice to put them first in
2153	REG_ALLOC_ORDER). */
2154	mode = ALLOCNO_MODE (a);
2155	for (i = 0; i < class_size; i++)
2156	{
2157	hard_regno = ira_class_hard_regs[aclass][i];
2158	#ifdef STACK_REGS
2159	if (no_stack_reg_p
2160	&& FIRST_STACK_REG <= hard_regno && hard_regno <= LAST_STACK_REG)
2161	continue;
2162	#endif
2163	if (! check_hard_reg_p (a, hard_regno,
2164	conflict_regs: conflicting_regs, profitable_regs: profitable_hard_regs))
2165	continue;
2166	if (NUM_REGISTER_FILTERS
2167	&& !test_register_filters (ALLOCNO_REGISTER_FILTERS (a), hard_regno))
2168	continue;
2169	cost = costs[i];
2170	full_cost = full_costs[i];
2171	if (!HONOR_REG_ALLOC_ORDER)
2172	{
2173	if ((saved_nregs = calculate_saved_nregs (hard_regno, mode)) != 0)
2174	/* We need to save/restore the hard register in
2175	epilogue/prologue. Therefore we increase the cost. */
2176	{
2177	rclass = REGNO_REG_CLASS (hard_regno);
2178	add_cost = ((ira_memory_move_cost[mode][rclass][0]
2179	+ ira_memory_move_cost[mode][rclass][1])
2180	* saved_nregs / hard_regno_nregs (regno: hard_regno,
2181	mode) - 1);
2182	cost += add_cost;
2183	full_cost += add_cost;
2184	}
2185	}
2186	if (min_cost > cost)
2187	min_cost = cost;
2188	if (min_full_cost > full_cost)
2189	{
2190	min_full_cost = full_cost;
2191	best_hard_regno = hard_regno;
2192	ira_assert (hard_regno >= 0);
2193	}
2194	if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL)
2195	fprintf (stream: ira_dump_file, format: "(%d=%d,%d) ", hard_regno, cost, full_cost);
2196	}
2197	if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL)
2198	fprintf (stream: ira_dump_file, format: "\n");
2199	if (min_full_cost > mem_cost
2200	/* Do not spill static chain pointer pseudo when non-local goto
2201	is used. */
2202	&& ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
2203	{
2204	if (! retry_p && internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2205	fprintf (stream: ira_dump_file, format: "(memory is more profitable %d vs %d) ",
2206	mem_cost, min_full_cost);
2207	best_hard_regno = -1;
2208	}
2209	fail:
2210	if (best_hard_regno >= 0)
2211	{
2212	for (i = hard_regno_nregs (regno: best_hard_regno, mode) - 1; i >= 0; i--)
2213	allocated_hardreg_p[best_hard_regno + i] = true;
2214	spill_soft_conflicts (a, allocnos_to_spill, soft_conflict_regs,
2215	hregno: best_hard_regno);
2216	}
2217	if (! retry_p)
2218	restore_costs_from_copies (allocno: a);
2219	ALLOCNO_HARD_REGNO (a) = best_hard_regno;
2220	ALLOCNO_ASSIGNED_P (a) = true;
2221	if (best_hard_regno >= 0 && !retry_p)
2222	update_costs_from_copies (allocno: a, decr_p: true, record_p: true);
2223	ira_assert (ALLOCNO_CLASS (a) == aclass);
2224	/* We don't need updated costs anymore. */
2225	ira_free_allocno_updated_costs (a);
2226	return best_hard_regno >= 0;
2227	}
2228
2229
2230
2231	/* An array used to sort copies. */
2232	static ira_copy_t *sorted_copies;
2233
2234	/* If allocno A is a cap, return non-cap allocno from which A is
2235	created. Otherwise, return A. */
2236	static ira_allocno_t
2237	get_cap_member (ira_allocno_t a)
2238	{
2239	ira_allocno_t member;
2240
2241	while ((member = ALLOCNO_CAP_MEMBER (a)) != NULL)
2242	a = member;
2243	return a;
2244	}
2245
2246	/* Return TRUE if live ranges of allocnos A1 and A2 intersect. It is
2247	used to find a conflict for new allocnos or allocnos with the
2248	different allocno classes. */
2249	static bool
2250	allocnos_conflict_by_live_ranges_p (ira_allocno_t a1, ira_allocno_t a2)
2251	{
2252	rtx reg1, reg2;
2253	int i, j;
2254	int n1 = ALLOCNO_NUM_OBJECTS (a1);
2255	int n2 = ALLOCNO_NUM_OBJECTS (a2);
2256
2257	if (a1 == a2)
2258	return false;
2259	reg1 = regno_reg_rtx[ALLOCNO_REGNO (a1)];
2260	reg2 = regno_reg_rtx[ALLOCNO_REGNO (a2)];
2261	if (reg1 != NULL && reg2 != NULL
2262	&& ORIGINAL_REGNO (reg1) == ORIGINAL_REGNO (reg2))
2263	return false;
2264
2265	/* We don't keep live ranges for caps because they can be quite big.
2266	Use ranges of non-cap allocno from which caps are created. */
2267	a1 = get_cap_member (a: a1);
2268	a2 = get_cap_member (a: a2);
2269	for (i = 0; i < n1; i++)
2270	{
2271	ira_object_t c1 = ALLOCNO_OBJECT (a1, i);
2272
2273	for (j = 0; j < n2; j++)
2274	{
2275	ira_object_t c2 = ALLOCNO_OBJECT (a2, j);
2276
2277	if (ira_live_ranges_intersect_p (OBJECT_LIVE_RANGES (c1),
2278	OBJECT_LIVE_RANGES (c2)))
2279	return true;
2280	}
2281	}
2282	return false;
2283	}
2284
2285	/* The function is used to sort copies according to their execution
2286	frequencies. */
2287	static int
2288	copy_freq_compare_func (const void *v1p, const void *v2p)
2289	{
2290	ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p;
2291	int pri1, pri2;
2292
2293	pri1 = cp1->freq;
2294	pri2 = cp2->freq;
2295	if (pri2 - pri1)
2296	return pri2 - pri1;
2297
2298	/* If frequencies are equal, sort by copies, so that the results of
2299	qsort leave nothing to chance. */
2300	return cp1->num - cp2->num;
2301	}
2302
2303
2304
2305	/* Return true if any allocno from thread of A1 conflicts with any
2306	allocno from thread A2. */
2307	static bool
2308	allocno_thread_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
2309	{
2310	ira_allocno_t a, conflict_a;
2311
2312	for (a = ALLOCNO_COLOR_DATA (a2)->next_thread_allocno;;
2313	a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
2314	{
2315	for (conflict_a = ALLOCNO_COLOR_DATA (a1)->next_thread_allocno;;
2316	conflict_a = ALLOCNO_COLOR_DATA (conflict_a)->next_thread_allocno)
2317	{
2318	if (allocnos_conflict_by_live_ranges_p (a1: a, a2: conflict_a))
2319	return true;
2320	if (conflict_a == a1)
2321	break;
2322	}
2323	if (a == a2)
2324	break;
2325	}
2326	return false;
2327	}
2328
2329	/* Merge two threads given correspondingly by their first allocnos T1
2330	and T2 (more accurately merging T2 into T1). */
2331	static void
2332	merge_threads (ira_allocno_t t1, ira_allocno_t t2)
2333	{
2334	ira_allocno_t a, next, last;
2335
2336	gcc_assert (t1 != t2
2337	&& ALLOCNO_COLOR_DATA (t1)->first_thread_allocno == t1
2338	&& ALLOCNO_COLOR_DATA (t2)->first_thread_allocno == t2);
2339	for (last = t2, a = ALLOCNO_COLOR_DATA (t2)->next_thread_allocno;;
2340	a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
2341	{
2342	ALLOCNO_COLOR_DATA (a)->first_thread_allocno = t1;
2343	if (a == t2)
2344	break;
2345	last = a;
2346	}
2347	next = ALLOCNO_COLOR_DATA (t1)->next_thread_allocno;
2348	ALLOCNO_COLOR_DATA (t1)->next_thread_allocno = t2;
2349	ALLOCNO_COLOR_DATA (last)->next_thread_allocno = next;
2350	ALLOCNO_COLOR_DATA (t1)->thread_freq += ALLOCNO_COLOR_DATA (t2)->thread_freq;
2351	}
2352
2353	/* Create threads by processing CP_NUM copies from sorted copies. We
2354	process the most expensive copies first. */
2355	static void
2356	form_threads_from_copies (int cp_num)
2357	{
2358	ira_allocno_t a, thread1, thread2;
2359	ira_copy_t cp;
2360
2361	qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
2362	/* Form threads processing copies, most frequently executed
2363	first. */
2364	for (int i = 0; i < cp_num; i++)
2365	{
2366	cp = sorted_copies[i];
2367	thread1 = ALLOCNO_COLOR_DATA (cp->first)->first_thread_allocno;
2368	thread2 = ALLOCNO_COLOR_DATA (cp->second)->first_thread_allocno;
2369	if (thread1 == thread2)
2370	continue;
2371	if (! allocno_thread_conflict_p (a1: thread1, a2: thread2))
2372	{
2373	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2374	fprintf
2375	(stream: ira_dump_file,
2376	format: " Forming thread by copy %d:a%dr%d-a%dr%d (freq=%d):\n",
2377	cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
2378	ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
2379	cp->freq);
2380	merge_threads (t1: thread1, t2: thread2);
2381	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2382	{
2383	thread1 = ALLOCNO_COLOR_DATA (thread1)->first_thread_allocno;
2384	fprintf (stream: ira_dump_file, format: " Result (freq=%d): a%dr%d(%d)",
2385	ALLOCNO_COLOR_DATA (thread1)->thread_freq,
2386	ALLOCNO_NUM (thread1), ALLOCNO_REGNO (thread1),
2387	ALLOCNO_FREQ (thread1));
2388	for (a = ALLOCNO_COLOR_DATA (thread1)->next_thread_allocno;
2389	a != thread1;
2390	a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
2391	fprintf (stream: ira_dump_file, format: " a%dr%d(%d)",
2392	ALLOCNO_NUM (a), ALLOCNO_REGNO (a),
2393	ALLOCNO_FREQ (a));
2394	fprintf (stream: ira_dump_file, format: "\n");
2395	}
2396	}
2397	}
2398	}
2399
2400	/* Create threads by processing copies of all alocnos from BUCKET. We
2401	process the most expensive copies first. */
2402	static void
2403	form_threads_from_bucket (ira_allocno_t bucket)
2404	{
2405	ira_allocno_t a;
2406	ira_copy_t cp, next_cp;
2407	int cp_num = 0;
2408
2409	for (a = bucket; a != NULL; a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2410	{
2411	for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2412	{
2413	if (cp->first == a)
2414	{
2415	next_cp = cp->next_first_allocno_copy;
2416	sorted_copies[cp_num++] = cp;
2417	}
2418	else if (cp->second == a)
2419	next_cp = cp->next_second_allocno_copy;
2420	else
2421	gcc_unreachable ();
2422	}
2423	}
2424	form_threads_from_copies (cp_num);
2425	}
2426
2427	/* Create threads by processing copies of colorable allocno A. We
2428	process most expensive copies first. */
2429	static void
2430	form_threads_from_colorable_allocno (ira_allocno_t a)
2431	{
2432	ira_allocno_t another_a;
2433	ira_copy_t cp, next_cp;
2434	int cp_num = 0;
2435
2436	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2437	fprintf (stream: ira_dump_file, format: " Forming thread from allocno a%dr%d:\n",
2438	ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2439	for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2440	{
2441	if (cp->first == a)
2442	{
2443	next_cp = cp->next_first_allocno_copy;
2444	another_a = cp->second;
2445	}
2446	else if (cp->second == a)
2447	{
2448	next_cp = cp->next_second_allocno_copy;
2449	another_a = cp->first;
2450	}
2451	else
2452	gcc_unreachable ();
2453	if ((! ALLOCNO_COLOR_DATA (another_a)->in_graph_p
2454	&& !ALLOCNO_COLOR_DATA (another_a)->may_be_spilled_p)
2455	|| ALLOCNO_COLOR_DATA (another_a)->colorable_p)
2456	sorted_copies[cp_num++] = cp;
2457	}
2458	form_threads_from_copies (cp_num);
2459	}
2460
2461	/* Form initial threads which contain only one allocno. */
2462	static void
2463	init_allocno_threads (void)
2464	{
2465	ira_allocno_t a;
2466	unsigned int j;
2467	bitmap_iterator bi;
2468	ira_pref_t pref;
2469
2470	EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
2471	{
2472	a = ira_allocnos[j];
2473	/* Set up initial thread data: */
2474	ALLOCNO_COLOR_DATA (a)->first_thread_allocno
2475	= ALLOCNO_COLOR_DATA (a)->next_thread_allocno = a;
2476	ALLOCNO_COLOR_DATA (a)->thread_freq = ALLOCNO_FREQ (a);
2477	ALLOCNO_COLOR_DATA (a)->hard_reg_prefs = 0;
2478	for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref)
2479	ALLOCNO_COLOR_DATA (a)->hard_reg_prefs += pref->freq;
2480	}
2481	}
2482
2483
2484
2485	/* This page contains the allocator based on the Chaitin-Briggs algorithm. */
2486
2487	/* Bucket of allocnos that can colored currently without spilling. */
2488	static ira_allocno_t colorable_allocno_bucket;
2489
2490	/* Bucket of allocnos that might be not colored currently without
2491	spilling. */
2492	static ira_allocno_t uncolorable_allocno_bucket;
2493
2494	/* The current number of allocnos in the uncolorable_bucket. */
2495	static int uncolorable_allocnos_num;
2496
2497	/* Return the current spill priority of allocno A. The less the
2498	number, the more preferable the allocno for spilling. */
2499	static inline int
2500	allocno_spill_priority (ira_allocno_t a)
2501	{
2502	allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
2503
2504	return (data->temp
2505	/ (ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a)
2506	* ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]
2507	+ 1));
2508	}
2509
2510	/* Add allocno A to bucket *BUCKET_PTR. A should be not in a bucket
2511	before the call. */
2512	static void
2513	add_allocno_to_bucket (ira_allocno_t a, ira_allocno_t *bucket_ptr)
2514	{
2515	ira_allocno_t first_a;
2516	allocno_color_data_t data;
2517
2518	if (bucket_ptr == &uncolorable_allocno_bucket
2519	&& ALLOCNO_CLASS (a) != NO_REGS)
2520	{
2521	uncolorable_allocnos_num++;
2522	ira_assert (uncolorable_allocnos_num > 0);
2523	}
2524	first_a = *bucket_ptr;
2525	data = ALLOCNO_COLOR_DATA (a);
2526	data->next_bucket_allocno = first_a;
2527	data->prev_bucket_allocno = NULL;
2528	if (first_a != NULL)
2529	ALLOCNO_COLOR_DATA (first_a)->prev_bucket_allocno = a;
2530	*bucket_ptr = a;
2531	}
2532
2533	/* Compare two allocnos to define which allocno should be pushed first
2534	into the coloring stack. If the return is a negative number, the
2535	allocno given by the first parameter will be pushed first. In this
2536	case such allocno has less priority than the second one and the
2537	hard register will be assigned to it after assignment to the second
2538	one. As the result of such assignment order, the second allocno
2539	has a better chance to get the best hard register. */
2540	static int
2541	bucket_allocno_compare_func (const void *v1p, const void *v2p)
2542	{
2543	ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2544	ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2545	int diff, freq1, freq2, a1_num, a2_num, pref1, pref2;
2546	ira_allocno_t t1 = ALLOCNO_COLOR_DATA (a1)->first_thread_allocno;
2547	ira_allocno_t t2 = ALLOCNO_COLOR_DATA (a2)->first_thread_allocno;
2548	int cl1 = ALLOCNO_CLASS (a1), cl2 = ALLOCNO_CLASS (a2);
2549
2550	freq1 = ALLOCNO_COLOR_DATA (t1)->thread_freq;
2551	freq2 = ALLOCNO_COLOR_DATA (t2)->thread_freq;
2552	if ((diff = freq1 - freq2) != 0)
2553	return diff;
2554
2555	if ((diff = ALLOCNO_NUM (t2) - ALLOCNO_NUM (t1)) != 0)
2556	return diff;
2557
2558	/* Push pseudos requiring less hard registers first. It means that
2559	we will assign pseudos requiring more hard registers first
2560	avoiding creation small holes in free hard register file into
2561	which the pseudos requiring more hard registers cannot fit. */
2562	if ((diff = (ira_reg_class_max_nregs[cl1][ALLOCNO_MODE (a1)]
2563	- ira_reg_class_max_nregs[cl2][ALLOCNO_MODE (a2)])) != 0)
2564	return diff;
2565
2566	freq1 = ALLOCNO_FREQ (a1);
2567	freq2 = ALLOCNO_FREQ (a2);
2568	if ((diff = freq1 - freq2) != 0)
2569	return diff;
2570
2571	a1_num = ALLOCNO_COLOR_DATA (a1)->available_regs_num;
2572	a2_num = ALLOCNO_COLOR_DATA (a2)->available_regs_num;
2573	if ((diff = a2_num - a1_num) != 0)
2574	return diff;
2575	/* Push allocnos with minimal conflict_allocno_hard_prefs first. */
2576	pref1 = ALLOCNO_COLOR_DATA (a1)->conflict_allocno_hard_prefs;
2577	pref2 = ALLOCNO_COLOR_DATA (a2)->conflict_allocno_hard_prefs;
2578	if ((diff = pref1 - pref2) != 0)
2579	return diff;
2580	return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
2581	}
2582
2583	/* Sort bucket *BUCKET_PTR and return the result through
2584	BUCKET_PTR. */
2585	static void
2586	sort_bucket (ira_allocno_t *bucket_ptr,
2587	int (*compare_func) (const void *, const void *))
2588	{
2589	ira_allocno_t a, head;
2590	int n;
2591
2592	for (n = 0, a = *bucket_ptr;
2593	a != NULL;
2594	a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2595	sorted_allocnos[n++] = a;
2596	if (n <= 1)
2597	return;
2598	qsort (sorted_allocnos, n, sizeof (ira_allocno_t), compare_func);
2599	head = NULL;
2600	for (n--; n >= 0; n--)
2601	{
2602	a = sorted_allocnos[n];
2603	ALLOCNO_COLOR_DATA (a)->next_bucket_allocno = head;
2604	ALLOCNO_COLOR_DATA (a)->prev_bucket_allocno = NULL;
2605	if (head != NULL)
2606	ALLOCNO_COLOR_DATA (head)->prev_bucket_allocno = a;
2607	head = a;
2608	}
2609	*bucket_ptr = head;
2610	}
2611
2612	/* Add ALLOCNO to colorable bucket maintaining the order according
2613	their priority. ALLOCNO should be not in a bucket before the
2614	call. */
2615	static void
2616	add_allocno_to_ordered_colorable_bucket (ira_allocno_t allocno)
2617	{
2618	ira_allocno_t before, after;
2619
2620	form_threads_from_colorable_allocno (a: allocno);
2621	for (before = colorable_allocno_bucket, after = NULL;
2622	before != NULL;
2623	after = before,
2624	before = ALLOCNO_COLOR_DATA (before)->next_bucket_allocno)
2625	if (bucket_allocno_compare_func (v1p: &allocno, v2p: &before) < 0)
2626	break;
2627	ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno = before;
2628	ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno = after;
2629	if (after == NULL)
2630	colorable_allocno_bucket = allocno;
2631	else
2632	ALLOCNO_COLOR_DATA (after)->next_bucket_allocno = allocno;
2633	if (before != NULL)
2634	ALLOCNO_COLOR_DATA (before)->prev_bucket_allocno = allocno;
2635	}
2636
2637	/* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
2638	the call. */
2639	static void
2640	delete_allocno_from_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
2641	{
2642	ira_allocno_t prev_allocno, next_allocno;
2643
2644	if (bucket_ptr == &uncolorable_allocno_bucket
2645	&& ALLOCNO_CLASS (allocno) != NO_REGS)
2646	{
2647	uncolorable_allocnos_num--;
2648	ira_assert (uncolorable_allocnos_num >= 0);
2649	}
2650	prev_allocno = ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno;
2651	next_allocno = ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno;
2652	if (prev_allocno != NULL)
2653	ALLOCNO_COLOR_DATA (prev_allocno)->next_bucket_allocno = next_allocno;
2654	else
2655	{
2656	ira_assert (*bucket_ptr == allocno);
2657	*bucket_ptr = next_allocno;
2658	}
2659	if (next_allocno != NULL)
2660	ALLOCNO_COLOR_DATA (next_allocno)->prev_bucket_allocno = prev_allocno;
2661	}
2662
2663	/* Put allocno A onto the coloring stack without removing it from its
2664	bucket. Pushing allocno to the coloring stack can result in moving
2665	conflicting allocnos from the uncolorable bucket to the colorable
2666	one. Update conflict_allocno_hard_prefs of the conflicting
2667	allocnos which are not on stack yet. */
2668	static void
2669	push_allocno_to_stack (ira_allocno_t a)
2670	{
2671	enum reg_class aclass;
2672	allocno_color_data_t data, conflict_data;
2673	int size, i, n = ALLOCNO_NUM_OBJECTS (a);
2674
2675	data = ALLOCNO_COLOR_DATA (a);
2676	data->in_graph_p = false;
2677	allocno_stack_vec.safe_push (obj: a);
2678	aclass = ALLOCNO_CLASS (a);
2679	if (aclass == NO_REGS)
2680	return;
2681	size = ira_reg_class_max_nregs[aclass][ALLOCNO_MODE (a)];
2682	if (n > 1)
2683	{
2684	/* We will deal with the subwords individually. */
2685	gcc_assert (size == ALLOCNO_NUM_OBJECTS (a));
2686	size = 1;
2687	}
2688	for (i = 0; i < n; i++)
2689	{
2690	ira_object_t obj = ALLOCNO_OBJECT (a, i);
2691	ira_object_t conflict_obj;
2692	ira_object_conflict_iterator oci;
2693
2694	FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2695	{
2696	ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2697	ira_pref_t pref;
2698
2699	conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
2700	if (! conflict_data->in_graph_p
2701	|| ALLOCNO_ASSIGNED_P (conflict_a)
2702	|| !(hard_reg_set_intersect_p
2703	(ALLOCNO_COLOR_DATA (a)->profitable_hard_regs,
2704	y: conflict_data->profitable_hard_regs)))
2705	continue;
2706	for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref)
2707	conflict_data->conflict_allocno_hard_prefs -= pref->freq;
2708	if (conflict_data->colorable_p)
2709	continue;
2710	ira_assert (bitmap_bit_p (coloring_allocno_bitmap,
2711	ALLOCNO_NUM (conflict_a)));
2712	if (update_left_conflict_sizes_p (a: conflict_a, removed_a: a, size))
2713	{
2714	delete_allocno_from_bucket
2715	(allocno: conflict_a, bucket_ptr: &uncolorable_allocno_bucket);
2716	add_allocno_to_ordered_colorable_bucket (allocno: conflict_a);
2717	if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2718	{
2719	fprintf (stream: ira_dump_file, format: " Making");
2720	ira_print_expanded_allocno (conflict_a);
2721	fprintf (stream: ira_dump_file, format: " colorable\n");
2722	}
2723	}
2724
2725	}
2726	}
2727	}
2728
2729	/* Put ALLOCNO onto the coloring stack and remove it from its bucket.
2730	The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
2731	static void
2732	remove_allocno_from_bucket_and_push (ira_allocno_t allocno, bool colorable_p)
2733	{
2734	if (colorable_p)
2735	delete_allocno_from_bucket (allocno, bucket_ptr: &colorable_allocno_bucket);
2736	else
2737	delete_allocno_from_bucket (allocno, bucket_ptr: &uncolorable_allocno_bucket);
2738	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2739	{
2740	fprintf (stream: ira_dump_file, format: " Pushing");
2741	ira_print_expanded_allocno (allocno);
2742	if (colorable_p)
2743	fprintf (stream: ira_dump_file, format: "(cost %d)\n",
2744	ALLOCNO_COLOR_DATA (allocno)->temp);
2745	else
2746	fprintf (stream: ira_dump_file, format: "(potential spill: %spri=%d, cost=%d)\n",
2747	ALLOCNO_BAD_SPILL_P (allocno) ? "bad spill, " : "",
2748	allocno_spill_priority (a: allocno),
2749	ALLOCNO_COLOR_DATA (allocno)->temp);
2750	}
2751	if (! colorable_p)
2752	ALLOCNO_COLOR_DATA (allocno)->may_be_spilled_p = true;
2753	push_allocno_to_stack (a: allocno);
2754	}
2755
2756	/* Put all allocnos from colorable bucket onto the coloring stack. */
2757	static void
2758	push_only_colorable (void)
2759	{
2760	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2761	fprintf (stream: ira_dump_file, format: " Forming thread from colorable bucket:\n");
2762	form_threads_from_bucket (bucket: colorable_allocno_bucket);
2763	for (ira_allocno_t a = colorable_allocno_bucket;
2764	a != NULL;
2765	a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2766	update_costs_from_prefs (allocno: a);
2767	sort_bucket (bucket_ptr: &colorable_allocno_bucket, compare_func: bucket_allocno_compare_func);
2768	for (;colorable_allocno_bucket != NULL;)
2769	remove_allocno_from_bucket_and_push (allocno: colorable_allocno_bucket, colorable_p: true);
2770	}
2771
2772	/* Return the frequency of exit edges (if EXIT_P) or entry from/to the
2773	loop given by its LOOP_NODE. */
2774	int
2775	ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p)
2776	{
2777	int freq, i;
2778	edge_iterator ei;
2779	edge e;
2780
2781	ira_assert (current_loops != NULL && loop_node->loop != NULL
2782	&& (regno < 0 || regno >= FIRST_PSEUDO_REGISTER));
2783	freq = 0;
2784	if (! exit_p)
2785	{
2786	FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
2787	if (e->src != loop_node->loop->latch
2788	&& (regno < 0
2789	|| (bitmap_bit_p (df_get_live_out (bb: e->src), regno)
2790	&& bitmap_bit_p (df_get_live_in (bb: e->dest), regno))))
2791	freq += EDGE_FREQUENCY (e);
2792	}
2793	else
2794	{
2795	auto_vec<edge> edges = get_loop_exit_edges (loop_node->loop);
2796	FOR_EACH_VEC_ELT (edges, i, e)
2797	if (regno < 0
2798	|| (bitmap_bit_p (df_get_live_out (bb: e->src), regno)
2799	&& bitmap_bit_p (df_get_live_in (bb: e->dest), regno)))
2800	freq += EDGE_FREQUENCY (e);
2801	}
2802
2803	return REG_FREQ_FROM_EDGE_FREQ (freq);
2804	}
2805
2806	/* Construct an object that describes the boundary between A and its
2807	parent allocno. */
2808	ira_loop_border_costs::ira_loop_border_costs (ira_allocno_t a)
2809	: m_mode (ALLOCNO_MODE (a)),
2810	m_class (ALLOCNO_CLASS (a)),
2811	m_entry_freq (ira_loop_edge_freq (ALLOCNO_LOOP_TREE_NODE (a),
2812	ALLOCNO_REGNO (a), exit_p: false)),
2813	m_exit_freq (ira_loop_edge_freq (ALLOCNO_LOOP_TREE_NODE (a),
2814	ALLOCNO_REGNO (a), exit_p: true))
2815	{
2816	}
2817
2818	/* Calculate and return the cost of putting allocno A into memory. */
2819	static int
2820	calculate_allocno_spill_cost (ira_allocno_t a)
2821	{
2822	int regno, cost;
2823	ira_allocno_t parent_allocno;
2824	ira_loop_tree_node_t parent_node, loop_node;
2825
2826	regno = ALLOCNO_REGNO (a);
2827	cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_UPDATED_CLASS_COST (a);
2828	if (ALLOCNO_CAP (a) != NULL)
2829	return cost;
2830	loop_node = ALLOCNO_LOOP_TREE_NODE (a);
2831	if ((parent_node = loop_node->parent) == NULL)
2832	return cost;
2833	if ((parent_allocno = parent_node->regno_allocno_map[regno]) == NULL)
2834	return cost;
2835	ira_loop_border_costs border_costs (a);
2836	if (ALLOCNO_HARD_REGNO (parent_allocno) < 0)
2837	cost -= border_costs.spill_outside_loop_cost ();
2838	else
2839	cost += (border_costs.spill_inside_loop_cost ()
2840	- border_costs.move_between_loops_cost ());
2841	return cost;
2842	}
2843
2844	/* Used for sorting allocnos for spilling. */
2845	static inline int
2846	allocno_spill_priority_compare (ira_allocno_t a1, ira_allocno_t a2)
2847	{
2848	int pri1, pri2, diff;
2849
2850	/* Avoid spilling static chain pointer pseudo when non-local goto is
2851	used. */
2852	if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1)))
2853	return 1;
2854	else if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2)))
2855	return -1;
2856	if (ALLOCNO_BAD_SPILL_P (a1) && ! ALLOCNO_BAD_SPILL_P (a2))
2857	return 1;
2858	if (ALLOCNO_BAD_SPILL_P (a2) && ! ALLOCNO_BAD_SPILL_P (a1))
2859	return -1;
2860	pri1 = allocno_spill_priority (a: a1);
2861	pri2 = allocno_spill_priority (a: a2);
2862	if ((diff = pri1 - pri2) != 0)
2863	return diff;
2864	if ((diff
2865	= ALLOCNO_COLOR_DATA (a1)->temp - ALLOCNO_COLOR_DATA (a2)->temp) != 0)
2866	return diff;
2867	return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2868	}
2869
2870	/* Used for sorting allocnos for spilling. */
2871	static int
2872	allocno_spill_sort_compare (const void *v1p, const void *v2p)
2873	{
2874	ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
2875	ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
2876
2877	return allocno_spill_priority_compare (a1: p1, a2: p2);
2878	}
2879
2880	/* Push allocnos to the coloring stack. The order of allocnos in the
2881	stack defines the order for the subsequent coloring. */
2882	static void
2883	push_allocnos_to_stack (void)
2884	{
2885	ira_allocno_t a;
2886	int cost;
2887
2888	/* Calculate uncolorable allocno spill costs. */
2889	for (a = uncolorable_allocno_bucket;
2890	a != NULL;
2891	a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2892	if (ALLOCNO_CLASS (a) != NO_REGS)
2893	{
2894	cost = calculate_allocno_spill_cost (a);
2895	/* ??? Remove cost of copies between the coalesced
2896	allocnos. */
2897	ALLOCNO_COLOR_DATA (a)->temp = cost;
2898	}
2899	sort_bucket (bucket_ptr: &uncolorable_allocno_bucket, compare_func: allocno_spill_sort_compare);
2900	for (;;)
2901	{
2902	push_only_colorable ();
2903	a = uncolorable_allocno_bucket;
2904	if (a == NULL)
2905	break;
2906	remove_allocno_from_bucket_and_push (allocno: a, colorable_p: false);
2907	}
2908	ira_assert (colorable_allocno_bucket == NULL
2909	&& uncolorable_allocno_bucket == NULL);
2910	ira_assert (uncolorable_allocnos_num == 0);
2911	}
2912
2913	/* Pop the coloring stack and assign hard registers to the popped
2914	allocnos. */
2915	static void
2916	pop_allocnos_from_stack (void)
2917	{
2918	ira_allocno_t allocno;
2919	enum reg_class aclass;
2920
2921	for (;allocno_stack_vec.length () != 0;)
2922	{
2923	allocno = allocno_stack_vec.pop ();
2924	aclass = ALLOCNO_CLASS (allocno);
2925	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2926	{
2927	fprintf (stream: ira_dump_file, format: " Popping");
2928	ira_print_expanded_allocno (allocno);
2929	fprintf (stream: ira_dump_file, format: " -- ");
2930	}
2931	if (aclass == NO_REGS)
2932	{
2933	ALLOCNO_HARD_REGNO (allocno) = -1;
2934	ALLOCNO_ASSIGNED_P (allocno) = true;
2935	ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno) == NULL);
2936	ira_assert
2937	(ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno) == NULL);
2938	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2939	fprintf (stream: ira_dump_file, format: "assign memory\n");
2940	}
2941	else if (assign_hard_reg (a: allocno, retry_p: false))
2942	{
2943	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2944	fprintf (stream: ira_dump_file, format: " assign reg %d\n",
2945	ALLOCNO_HARD_REGNO (allocno));
2946	}
2947	else if (ALLOCNO_ASSIGNED_P (allocno))
2948	{
2949	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2950	fprintf (stream: ira_dump_file, format: "spill%s\n",
2951	ALLOCNO_COLOR_DATA (allocno)->may_be_spilled_p
2952	? "" : "!");
2953	}
2954	ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
2955	}
2956	}
2957
2958	/* Set up number of available hard registers for allocno A. */
2959	static void
2960	setup_allocno_available_regs_num (ira_allocno_t a)
2961	{
2962	int i, n, hard_regno, hard_regs_num, nwords;
2963	enum reg_class aclass;
2964	allocno_color_data_t data;
2965
2966	aclass = ALLOCNO_CLASS (a);
2967	data = ALLOCNO_COLOR_DATA (a);
2968	data->available_regs_num = 0;
2969	if (aclass == NO_REGS)
2970	return;
2971	hard_regs_num = ira_class_hard_regs_num[aclass];
2972	nwords = ALLOCNO_NUM_OBJECTS (a);
2973	for (n = 0, i = hard_regs_num - 1; i >= 0; i--)
2974	{
2975	hard_regno = ira_class_hard_regs[aclass][i];
2976	/* Checking only profitable hard regs. */
2977	if (TEST_HARD_REG_BIT (set: data->profitable_hard_regs, bit: hard_regno))
2978	n++;
2979	}
2980	data->available_regs_num = n;
2981	if (internal_flag_ira_verbose <= 2 || ira_dump_file == NULL)
2982	return;
2983	fprintf
2984	(stream: ira_dump_file,
2985	format: " Allocno a%dr%d of %s(%d) has %d avail. regs ",
2986	ALLOCNO_NUM (a), ALLOCNO_REGNO (a),
2987	reg_class_names[aclass], ira_class_hard_regs_num[aclass], n);
2988	print_hard_reg_set (f: ira_dump_file, set: data->profitable_hard_regs, new_line_p: false);
2989	fprintf (stream: ira_dump_file, format: ", %snode: ",
2990	data->profitable_hard_regs == data->hard_regs_node->hard_regs->set
2991	? "" : "^");
2992	print_hard_reg_set (f: ira_dump_file,
2993	set: data->hard_regs_node->hard_regs->set, new_line_p: false);
2994	for (i = 0; i < nwords; i++)
2995	{
2996	ira_object_t obj = ALLOCNO_OBJECT (a, i);
2997
2998	if (nwords != 1)
2999	{
3000	if (i != 0)
3001	fprintf (stream: ira_dump_file, format: ", ");
3002	fprintf (stream: ira_dump_file, format: " obj %d", i);
3003	}
3004	fprintf (stream: ira_dump_file, format: " (confl regs = ");
3005	print_hard_reg_set (f: ira_dump_file, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
3006	new_line_p: false);
3007	fprintf (stream: ira_dump_file, format: ")");
3008	}
3009	fprintf (stream: ira_dump_file, format: "\n");
3010	}
3011
3012	/* Put ALLOCNO in a bucket corresponding to its number and size of its
3013	conflicting allocnos and hard registers. */
3014	static void
3015	put_allocno_into_bucket (ira_allocno_t allocno)
3016	{
3017	ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
3018	setup_allocno_available_regs_num (allocno);
3019	if (setup_left_conflict_sizes_p (allocno))
3020	add_allocno_to_bucket (a: allocno, bucket_ptr: &colorable_allocno_bucket);
3021	else
3022	add_allocno_to_bucket (a: allocno, bucket_ptr: &uncolorable_allocno_bucket);
3023	}
3024
3025	/* Map: allocno number -> allocno priority. */
3026	static int *allocno_priorities;
3027
3028	/* Set up priorities for N allocnos in array
3029	CONSIDERATION_ALLOCNOS. */
3030	static void
3031	setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
3032	{
3033	int i, length, nrefs, priority, max_priority, mult, diff;
3034	ira_allocno_t a;
3035
3036	max_priority = 0;
3037	for (i = 0; i < n; i++)
3038	{
3039	a = consideration_allocnos[i];
3040	nrefs = ALLOCNO_NREFS (a);
3041	ira_assert (nrefs >= 0);
3042	mult = floor_log2 (ALLOCNO_NREFS (a)) + 1;
3043	ira_assert (mult >= 0);
3044	mult *= ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)];
3045	diff = ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a);
3046	#ifdef __has_builtin
3047	#if __has_builtin(__builtin_smul_overflow)
3048	#define HAS_SMUL_OVERFLOW
3049	#endif
3050	#endif
3051	/* Multiplication can overflow for very large functions.
3052	Check the overflow and constrain the result if necessary: */
3053	#ifdef HAS_SMUL_OVERFLOW
3054	if (__builtin_smul_overflow (mult, diff, &priority)
3055	|| priority < -INT_MAX)
3056	priority = diff >= 0 ? INT_MAX : -INT_MAX;
3057	#else
3058	static_assert
3059	(sizeof (long long) >= 2 * sizeof (int),
3060	"overflow code does not work for such int and long long sizes");
3061	long long priorityll = (long long) mult * diff;
3062	if (priorityll < -INT_MAX || priorityll > INT_MAX)
3063	priority = diff >= 0 ? INT_MAX : -INT_MAX;
3064	else
3065	priority = priorityll;
3066	#endif
3067	allocno_priorities[ALLOCNO_NUM (a)] = priority;
3068	if (priority < 0)
3069	priority = -priority;
3070	if (max_priority < priority)
3071	max_priority = priority;
3072	}
3073	mult = max_priority == 0 ? 1 : INT_MAX / max_priority;
3074	for (i = 0; i < n; i++)
3075	{
3076	a = consideration_allocnos[i];
3077	length = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
3078	if (ALLOCNO_NUM_OBJECTS (a) > 1)
3079	length /= ALLOCNO_NUM_OBJECTS (a);
3080	if (length <= 0)
3081	length = 1;
3082	allocno_priorities[ALLOCNO_NUM (a)]
3083	= allocno_priorities[ALLOCNO_NUM (a)] * mult / length;
3084	}
3085	}
3086
3087	/* Sort allocnos according to the profit of usage of a hard register
3088	instead of memory for them. */
3089	static int
3090	allocno_cost_compare_func (const void *v1p, const void *v2p)
3091	{
3092	ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
3093	ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
3094	int c1, c2;
3095
3096	c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_UPDATED_CLASS_COST (p1);
3097	c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_UPDATED_CLASS_COST (p2);
3098	if (c1 - c2)
3099	return c1 - c2;
3100
3101	/* If regs are equally good, sort by allocno numbers, so that the
3102	results of qsort leave nothing to chance. */
3103	return ALLOCNO_NUM (p1) - ALLOCNO_NUM (p2);
3104	}
3105
3106	/* Return savings on removed copies when ALLOCNO is assigned to
3107	HARD_REGNO. */
3108	static int
3109	allocno_copy_cost_saving (ira_allocno_t allocno, int hard_regno)
3110	{
3111	int cost = 0;
3112	machine_mode allocno_mode = ALLOCNO_MODE (allocno);
3113	enum reg_class rclass;
3114	ira_copy_t cp, next_cp;
3115
3116	rclass = REGNO_REG_CLASS (hard_regno);
3117	if (ira_reg_class_max_nregs[rclass][allocno_mode]
3118	> ira_class_hard_regs_num[rclass])
3119	/* For the above condition the cost can be wrong. Use the allocno
3120	class in this case. */
3121	rclass = ALLOCNO_CLASS (allocno);
3122	for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
3123	{
3124	if (cp->first == allocno)
3125	{
3126	next_cp = cp->next_first_allocno_copy;
3127	if (ALLOCNO_HARD_REGNO (cp->second) != hard_regno)
3128	continue;
3129	}
3130	else if (cp->second == allocno)
3131	{
3132	next_cp = cp->next_second_allocno_copy;
3133	if (ALLOCNO_HARD_REGNO (cp->first) != hard_regno)
3134	continue;
3135	}
3136	else
3137	gcc_unreachable ();
3138	ira_init_register_move_cost_if_necessary (mode: allocno_mode);
3139	cost += cp->freq * ira_register_move_cost[allocno_mode][rclass][rclass];
3140	}
3141	return cost;
3142	}
3143
3144	/* We used Chaitin-Briggs coloring to assign as many pseudos as
3145	possible to hard registers. Let us try to improve allocation with
3146	cost point of view. This function improves the allocation by
3147	spilling some allocnos and assigning the freed hard registers to
3148	other allocnos if it decreases the overall allocation cost. */
3149	static void
3150	improve_allocation (void)
3151	{
3152	unsigned int i;
3153	int j, k, n, hregno, conflict_hregno, base_cost, class_size, word, nwords;
3154	int check, spill_cost, min_cost, nregs, conflict_nregs, r, best;
3155	bool try_p;
3156	enum reg_class aclass, rclass;
3157	machine_mode mode;
3158	int *allocno_costs;
3159	int costs[FIRST_PSEUDO_REGISTER];
3160	HARD_REG_SET conflicting_regs[2], profitable_hard_regs;
3161	ira_allocno_t a;
3162	bitmap_iterator bi;
3163	int saved_nregs;
3164	int add_cost;
3165
3166	/* Don't bother to optimize the code with static chain pointer and
3167	non-local goto in order not to spill the chain pointer
3168	pseudo. */
3169	if (cfun->static_chain_decl && crtl->has_nonlocal_goto)
3170	return;
3171	/* Clear counts used to process conflicting allocnos only once for
3172	each allocno. */
3173	EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3174	ALLOCNO_COLOR_DATA (ira_allocnos[i])->temp = 0;
3175	check = n = 0;
3176	/* Process each allocno and try to assign a hard register to it by
3177	spilling some its conflicting allocnos. */
3178	EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3179	{
3180	a = ira_allocnos[i];
3181	ALLOCNO_COLOR_DATA (a)->temp = 0;
3182	if (empty_profitable_hard_regs (a))
3183	continue;
3184	check++;
3185	aclass = ALLOCNO_CLASS (a);
3186	allocno_costs = ALLOCNO_HARD_REG_COSTS (a);
3187	if ((hregno = ALLOCNO_HARD_REGNO (a)) < 0)
3188	base_cost = ALLOCNO_UPDATED_MEMORY_COST (a);
3189	else if (allocno_costs == NULL)
3190	/* It means that assigning a hard register is not profitable
3191	(we don't waste memory for hard register costs in this
3192	case). */
3193	continue;
3194	else
3195	base_cost = (allocno_costs[ira_class_hard_reg_index[aclass][hregno]]
3196	- allocno_copy_cost_saving (allocno: a, hard_regno: hregno));
3197	try_p = false;
3198	get_conflict_and_start_profitable_regs (a, retry_p: false,
3199	conflict_regs: conflicting_regs,
3200	start_profitable_regs: &profitable_hard_regs);
3201	class_size = ira_class_hard_regs_num[aclass];
3202	mode = ALLOCNO_MODE (a);
3203	/* Set up cost improvement for usage of each profitable hard
3204	register for allocno A. */
3205	for (j = 0; j < class_size; j++)
3206	{
3207	hregno = ira_class_hard_regs[aclass][j];
3208	if (! check_hard_reg_p (a, hard_regno: hregno,
3209	conflict_regs: conflicting_regs, profitable_regs: profitable_hard_regs))
3210	continue;
3211	if (NUM_REGISTER_FILTERS
3212	&& !test_register_filters (ALLOCNO_REGISTER_FILTERS (a), hregno))
3213	continue;
3214	ira_assert (ira_class_hard_reg_index[aclass][hregno] == j);
3215	k = allocno_costs == NULL ? 0 : j;
3216	costs[hregno] = (allocno_costs == NULL
3217	? ALLOCNO_UPDATED_CLASS_COST (a) : allocno_costs[k]);
3218	costs[hregno] -= allocno_copy_cost_saving (allocno: a, hard_regno: hregno);
3219
3220	if ((saved_nregs = calculate_saved_nregs (hard_regno: hregno, mode)) != 0)
3221	{
3222	/* We need to save/restore the hard register in
3223	epilogue/prologue. Therefore we increase the cost.
3224	Since the prolog is placed in the entry BB, the frequency
3225	of the entry BB is considered while computing the cost. */
3226	rclass = REGNO_REG_CLASS (hregno);
3227	add_cost = ((ira_memory_move_cost[mode][rclass][0]
3228	+ ira_memory_move_cost[mode][rclass][1])
3229	* saved_nregs / hard_regno_nregs (regno: hregno,
3230	mode) - 1)
3231	* REG_FREQ_FROM_BB (ENTRY_BLOCK_PTR_FOR_FN (cfun));
3232	costs[hregno] += add_cost;
3233	}
3234
3235	costs[hregno] -= base_cost;
3236	if (costs[hregno] < 0)
3237	try_p = true;
3238	}
3239	if (! try_p)
3240	/* There is no chance to improve the allocation cost by
3241	assigning hard register to allocno A even without spilling
3242	conflicting allocnos. */
3243	continue;
3244	auto_bitmap allocnos_to_spill;
3245	HARD_REG_SET soft_conflict_regs = {};
3246	mode = ALLOCNO_MODE (a);
3247	nwords = ALLOCNO_NUM_OBJECTS (a);
3248	/* Process each allocno conflicting with A and update the cost
3249	improvement for profitable hard registers of A. To use a
3250	hard register for A we need to spill some conflicting
3251	allocnos and that creates penalty for the cost
3252	improvement. */
3253	for (word = 0; word < nwords; word++)
3254	{
3255	ira_object_t conflict_obj;
3256	ira_object_t obj = ALLOCNO_OBJECT (a, word);
3257	ira_object_conflict_iterator oci;
3258
3259	FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
3260	{
3261	ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
3262
3263	if (ALLOCNO_COLOR_DATA (conflict_a)->temp == check)
3264	/* We already processed this conflicting allocno
3265	because we processed earlier another object of the
3266	conflicting allocno. */
3267	continue;
3268	ALLOCNO_COLOR_DATA (conflict_a)->temp = check;
3269	if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0)
3270	continue;
3271	auto spill_a = ira_soft_conflict (a1: a, a2: conflict_a);
3272	if (spill_a)
3273	{
3274	if (!bitmap_set_bit (allocnos_to_spill,
3275	ALLOCNO_NUM (spill_a)))
3276	continue;
3277	ira_loop_border_costs border_costs (spill_a);
3278	spill_cost = border_costs.spill_inside_loop_cost ();
3279	}
3280	else
3281	{
3282	spill_cost = ALLOCNO_UPDATED_MEMORY_COST (conflict_a);
3283	k = (ira_class_hard_reg_index
3284	[ALLOCNO_CLASS (conflict_a)][conflict_hregno]);
3285	ira_assert (k >= 0);
3286	if ((allocno_costs = ALLOCNO_HARD_REG_COSTS (conflict_a))
3287	!= NULL)
3288	spill_cost -= allocno_costs[k];
3289	else
3290	spill_cost -= ALLOCNO_UPDATED_CLASS_COST (conflict_a);
3291	spill_cost
3292	+= allocno_copy_cost_saving (allocno: conflict_a, hard_regno: conflict_hregno);
3293	}
3294	conflict_nregs = hard_regno_nregs (regno: conflict_hregno,
3295	ALLOCNO_MODE (conflict_a));
3296	auto note_conflict = [&](int r)
3297	{
3298	if (check_hard_reg_p (a, hard_regno: r,
3299	conflict_regs: conflicting_regs, profitable_regs: profitable_hard_regs))
3300	{
3301	if (spill_a)
3302	SET_HARD_REG_BIT (set&: soft_conflict_regs, bit: r);
3303	costs[r] += spill_cost;
3304	}
3305	};
3306	for (r = conflict_hregno;
3307	r >= 0 && (int) end_hard_regno (mode, regno: r) > conflict_hregno;
3308	r--)
3309	note_conflict (r);
3310	for (r = conflict_hregno + 1;
3311	r < conflict_hregno + conflict_nregs;
3312	r++)
3313	note_conflict (r);
3314	}
3315	}
3316	min_cost = INT_MAX;
3317	best = -1;
3318	/* Now we choose hard register for A which results in highest
3319	allocation cost improvement. */
3320	for (j = 0; j < class_size; j++)
3321	{
3322	hregno = ira_class_hard_regs[aclass][j];
3323	if (check_hard_reg_p (a, hard_regno: hregno,
3324	conflict_regs: conflicting_regs, profitable_regs: profitable_hard_regs)
3325	&& min_cost > costs[hregno])
3326	{
3327	best = hregno;
3328	min_cost = costs[hregno];
3329	}
3330	}
3331	if (min_cost >= 0)
3332	/* We are in a situation when assigning any hard register to A
3333	by spilling some conflicting allocnos does not improve the
3334	allocation cost. */
3335	continue;
3336	spill_soft_conflicts (a, allocnos_to_spill, soft_conflict_regs, hregno: best);
3337	nregs = hard_regno_nregs (regno: best, mode);
3338	/* Now spill conflicting allocnos which contain a hard register
3339	of A when we assign the best chosen hard register to it. */
3340	for (word = 0; word < nwords; word++)
3341	{
3342	ira_object_t conflict_obj;
3343	ira_object_t obj = ALLOCNO_OBJECT (a, word);
3344	ira_object_conflict_iterator oci;
3345
3346	FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
3347	{
3348	ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
3349
3350	if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0)
3351	continue;
3352	conflict_nregs = hard_regno_nregs (regno: conflict_hregno,
3353	ALLOCNO_MODE (conflict_a));
3354	if (best + nregs <= conflict_hregno
3355	|| conflict_hregno + conflict_nregs <= best)
3356	/* No intersection. */
3357	continue;
3358	ALLOCNO_HARD_REGNO (conflict_a) = -1;
3359	sorted_allocnos[n++] = conflict_a;
3360	if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3361	fprintf (stream: ira_dump_file, format: "Spilling a%dr%d for a%dr%d\n",
3362	ALLOCNO_NUM (conflict_a), ALLOCNO_REGNO (conflict_a),
3363	ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
3364	}
3365	}
3366	/* Assign the best chosen hard register to A. */
3367	ALLOCNO_HARD_REGNO (a) = best;
3368
3369	for (j = nregs - 1; j >= 0; j--)
3370	allocated_hardreg_p[best + j] = true;
3371
3372	if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3373	fprintf (stream: ira_dump_file, format: "Assigning %d to a%dr%d\n",
3374	best, ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
3375	}
3376	if (n == 0)
3377	return;
3378	/* We spilled some allocnos to assign their hard registers to other
3379	allocnos. The spilled allocnos are now in array
3380	'sorted_allocnos'. There is still a possibility that some of the
3381	spilled allocnos can get hard registers. So let us try assign
3382	them hard registers again (just a reminder -- function
3383	'assign_hard_reg' assigns hard registers only if it is possible
3384	and profitable). We process the spilled allocnos with biggest
3385	benefit to get hard register first -- see function
3386	'allocno_cost_compare_func'. */
3387	qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
3388	allocno_cost_compare_func);
3389	for (j = 0; j < n; j++)
3390	{
3391	a = sorted_allocnos[j];
3392	ALLOCNO_ASSIGNED_P (a) = false;
3393	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3394	{
3395	fprintf (stream: ira_dump_file, format: " ");
3396	ira_print_expanded_allocno (a);
3397	fprintf (stream: ira_dump_file, format: " -- ");
3398	}
3399	if (assign_hard_reg (a, retry_p: false))
3400	{
3401	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3402	fprintf (stream: ira_dump_file, format: "assign hard reg %d\n",
3403	ALLOCNO_HARD_REGNO (a));
3404	}
3405	else
3406	{
3407	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3408	fprintf (stream: ira_dump_file, format: "assign memory\n");
3409	}
3410	}
3411	}
3412
3413	/* Sort allocnos according to their priorities. */
3414	static int
3415	allocno_priority_compare_func (const void *v1p, const void *v2p)
3416	{
3417	ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
3418	ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
3419	int pri1, pri2, diff;
3420
3421	/* Assign hard reg to static chain pointer pseudo first when
3422	non-local goto is used. */
3423	if ((diff = (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2))
3424	- non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1)))) != 0)
3425	return diff;
3426	pri1 = allocno_priorities[ALLOCNO_NUM (a1)];
3427	pri2 = allocno_priorities[ALLOCNO_NUM (a2)];
3428	if (pri2 != pri1)
3429	return SORTGT (pri2, pri1);
3430
3431	/* If regs are equally good, sort by allocnos, so that the results of
3432	qsort leave nothing to chance. */
3433	return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
3434	}
3435
3436	/* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
3437	taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
3438	static void
3439	color_allocnos (void)
3440	{
3441	unsigned int i, n;
3442	bitmap_iterator bi;
3443	ira_allocno_t a;
3444
3445	setup_profitable_hard_regs ();
3446	EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3447	{
3448	allocno_color_data_t data;
3449	ira_pref_t pref, next_pref;
3450
3451	a = ira_allocnos[i];
3452	data = ALLOCNO_COLOR_DATA (a);
3453	data->conflict_allocno_hard_prefs = 0;
3454	for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = next_pref)
3455	{
3456	next_pref = pref->next_pref;
3457	if (! ira_hard_reg_in_set_p (hard_regno: pref->hard_regno,
3458	ALLOCNO_MODE (a),
3459	hard_regset: data->profitable_hard_regs))
3460	ira_remove_pref (pref);
3461	}
3462	}
3463
3464	if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
3465	{
3466	n = 0;
3467	EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3468	{
3469	a = ira_allocnos[i];
3470	if (ALLOCNO_CLASS (a) == NO_REGS)
3471	{
3472	ALLOCNO_HARD_REGNO (a) = -1;
3473	ALLOCNO_ASSIGNED_P (a) = true;
3474	ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
3475	ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
3476	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3477	{
3478	fprintf (stream: ira_dump_file, format: " Spill");
3479	ira_print_expanded_allocno (a);
3480	fprintf (stream: ira_dump_file, format: "\n");
3481	}
3482	continue;
3483	}
3484	sorted_allocnos[n++] = a;
3485	}
3486	if (n != 0)
3487	{
3488	setup_allocno_priorities (consideration_allocnos: sorted_allocnos, n);
3489	qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
3490	allocno_priority_compare_func);
3491	for (i = 0; i < n; i++)
3492	{
3493	a = sorted_allocnos[i];
3494	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3495	{
3496	fprintf (stream: ira_dump_file, format: " ");
3497	ira_print_expanded_allocno (a);
3498	fprintf (stream: ira_dump_file, format: " -- ");
3499	}
3500	if (assign_hard_reg (a, retry_p: false))
3501	{
3502	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3503	fprintf (stream: ira_dump_file, format: "assign hard reg %d\n",
3504	ALLOCNO_HARD_REGNO (a));
3505	}
3506	else
3507	{
3508	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3509	fprintf (stream: ira_dump_file, format: "assign memory\n");
3510	}
3511	}
3512	}
3513	}
3514	else
3515	{
3516	form_allocno_hard_regs_nodes_forest ();
3517	if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3518	print_hard_regs_forest (f: ira_dump_file);
3519	EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3520	{
3521	a = ira_allocnos[i];
3522	if (ALLOCNO_CLASS (a) != NO_REGS && ! empty_profitable_hard_regs (a))
3523	{
3524	ALLOCNO_COLOR_DATA (a)->in_graph_p = true;
3525	update_conflict_allocno_hard_prefs (allocno: a);
3526	}
3527	else
3528	{
3529	ALLOCNO_HARD_REGNO (a) = -1;
3530	ALLOCNO_ASSIGNED_P (a) = true;
3531	/* We don't need updated costs anymore. */
3532	ira_free_allocno_updated_costs (a);
3533	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3534	{
3535	fprintf (stream: ira_dump_file, format: " Spill");
3536	ira_print_expanded_allocno (a);
3537	fprintf (stream: ira_dump_file, format: "\n");
3538	}
3539	}
3540	}
3541	/* Put the allocnos into the corresponding buckets. */
3542	colorable_allocno_bucket = NULL;
3543	uncolorable_allocno_bucket = NULL;
3544	EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3545	{
3546	a = ira_allocnos[i];
3547	if (ALLOCNO_COLOR_DATA (a)->in_graph_p)
3548	put_allocno_into_bucket (allocno: a);
3549	}
3550	push_allocnos_to_stack ();
3551	pop_allocnos_from_stack ();
3552	finish_allocno_hard_regs_nodes_forest ();
3553	}
3554	improve_allocation ();
3555	}
3556
3557
3558
3559	/* Output information about the loop given by its LOOP_TREE_NODE. */
3560	static void
3561	print_loop_title (ira_loop_tree_node_t loop_tree_node)
3562	{
3563	unsigned int j;
3564	bitmap_iterator bi;
3565	ira_loop_tree_node_t subloop_node, dest_loop_node;
3566	edge e;
3567	edge_iterator ei;
3568
3569	if (loop_tree_node->parent == NULL)
3570	fprintf (stream: ira_dump_file,
3571	format: "\n Loop 0 (parent -1, header bb%d, depth 0)\n bbs:",
3572	NUM_FIXED_BLOCKS);
3573	else
3574	{
3575	ira_assert (current_loops != NULL && loop_tree_node->loop != NULL);
3576	fprintf (stream: ira_dump_file,
3577	format: "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
3578	loop_tree_node->loop_num, loop_tree_node->parent->loop_num,
3579	loop_tree_node->loop->header->index,
3580	loop_depth (loop: loop_tree_node->loop));
3581	}
3582	for (subloop_node = loop_tree_node->children;
3583	subloop_node != NULL;
3584	subloop_node = subloop_node->next)
3585	if (subloop_node->bb != NULL)
3586	{
3587	fprintf (stream: ira_dump_file, format: " %d", subloop_node->bb->index);
3588	FOR_EACH_EDGE (e, ei, subloop_node->bb->succs)
3589	if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
3590	&& ((dest_loop_node = IRA_BB_NODE (e->dest)->parent)
3591	!= loop_tree_node))
3592	fprintf (stream: ira_dump_file, format: "(->%d:l%d)",
3593	e->dest->index, dest_loop_node->loop_num);
3594	}
3595	fprintf (stream: ira_dump_file, format: "\n all:");
3596	EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
3597	fprintf (stream: ira_dump_file, format: " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
3598	fprintf (stream: ira_dump_file, format: "\n modified regnos:");
3599	EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->modified_regnos, 0, j, bi)
3600	fprintf (stream: ira_dump_file, format: " %d", j);
3601	fprintf (stream: ira_dump_file, format: "\n border:");
3602	EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->border_allocnos, 0, j, bi)
3603	fprintf (stream: ira_dump_file, format: " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
3604	fprintf (stream: ira_dump_file, format: "\n Pressure:");
3605	for (j = 0; (int) j < ira_pressure_classes_num; j++)
3606	{
3607	enum reg_class pclass;
3608
3609	pclass = ira_pressure_classes[j];
3610	if (loop_tree_node->reg_pressure[pclass] == 0)
3611	continue;
3612	fprintf (stream: ira_dump_file, format: " %s=%d", reg_class_names[pclass],
3613	loop_tree_node->reg_pressure[pclass]);
3614	}
3615	fprintf (stream: ira_dump_file, format: "\n");
3616	}
3617
3618	/* Color the allocnos inside loop (in the extreme case it can be all
3619	of the function) given the corresponding LOOP_TREE_NODE. The
3620	function is called for each loop during top-down traverse of the
3621	loop tree. */
3622	static void
3623	color_pass (ira_loop_tree_node_t loop_tree_node)
3624	{
3625	int regno, hard_regno, index = -1, n;
3626	int cost;
3627	unsigned int j;
3628	bitmap_iterator bi;
3629	machine_mode mode;
3630	enum reg_class rclass, aclass;
3631	ira_allocno_t a, subloop_allocno;
3632	ira_loop_tree_node_t subloop_node;
3633
3634	ira_assert (loop_tree_node->bb == NULL);
3635	if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
3636	print_loop_title (loop_tree_node);
3637
3638	bitmap_copy (coloring_allocno_bitmap, loop_tree_node->all_allocnos);
3639	bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap);
3640	n = 0;
3641	EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3642	{
3643	a = ira_allocnos[j];
3644	n++;
3645	if (! ALLOCNO_ASSIGNED_P (a))
3646	continue;
3647	bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a));
3648	}
3649	allocno_color_data
3650	= (allocno_color_data_t) ira_allocate (sizeof (struct allocno_color_data)
3651	* n);
3652	memset (s: allocno_color_data, c: 0, n: sizeof (struct allocno_color_data) * n);
3653	curr_allocno_process = 0;
3654	n = 0;
3655	EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3656	{
3657	a = ira_allocnos[j];
3658	ALLOCNO_ADD_DATA (a) = allocno_color_data + n;
3659	n++;
3660	}
3661	init_allocno_threads ();
3662	/* Color all mentioned allocnos including transparent ones. */
3663	color_allocnos ();
3664	/* Process caps. They are processed just once. */
3665	if (flag_ira_region == IRA_REGION_MIXED
3666	|| flag_ira_region == IRA_REGION_ALL)
3667	EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
3668	{
3669	a = ira_allocnos[j];
3670	if (ALLOCNO_CAP_MEMBER (a) == NULL)
3671	continue;
3672	/* Remove from processing in the next loop. */
3673	bitmap_clear_bit (consideration_allocno_bitmap, j);
3674	rclass = ALLOCNO_CLASS (a);
3675	subloop_allocno = ALLOCNO_CAP_MEMBER (a);
3676	subloop_node = ALLOCNO_LOOP_TREE_NODE (subloop_allocno);
3677	if (ira_single_region_allocno_p (a, subloop_a: subloop_allocno))
3678	{
3679	mode = ALLOCNO_MODE (a);
3680	hard_regno = ALLOCNO_HARD_REGNO (a);
3681	if (hard_regno >= 0)
3682	{
3683	index = ira_class_hard_reg_index[rclass][hard_regno];
3684	ira_assert (index >= 0);
3685	}
3686	regno = ALLOCNO_REGNO (a);
3687	ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno));
3688	ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
3689	ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
3690	if (hard_regno >= 0)
3691	update_costs_from_copies (allocno: subloop_allocno, decr_p: true, record_p: true);
3692	/* We don't need updated costs anymore. */
3693	ira_free_allocno_updated_costs (subloop_allocno);
3694	}
3695	}
3696	/* Update costs of the corresponding allocnos (not caps) in the
3697	subloops. */
3698	for (subloop_node = loop_tree_node->subloops;
3699	subloop_node != NULL;
3700	subloop_node = subloop_node->subloop_next)
3701	{
3702	ira_assert (subloop_node->bb == NULL);
3703	EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3704	{
3705	a = ira_allocnos[j];
3706	ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
3707	mode = ALLOCNO_MODE (a);
3708	rclass = ALLOCNO_CLASS (a);
3709	hard_regno = ALLOCNO_HARD_REGNO (a);
3710	/* Use hard register class here. ??? */
3711	if (hard_regno >= 0)
3712	{
3713	index = ira_class_hard_reg_index[rclass][hard_regno];
3714	ira_assert (index >= 0);
3715	}
3716	regno = ALLOCNO_REGNO (a);
3717	/* ??? conflict costs */
3718	subloop_allocno = subloop_node->regno_allocno_map[regno];
3719	if (subloop_allocno == NULL
3720	|| ALLOCNO_CAP (subloop_allocno) != NULL)
3721	continue;
3722	ira_assert (ALLOCNO_CLASS (subloop_allocno) == rclass);
3723	ira_assert (bitmap_bit_p (subloop_node->all_allocnos,
3724	ALLOCNO_NUM (subloop_allocno)));
3725	if (ira_single_region_allocno_p (a, subloop_a: subloop_allocno)
3726	|| !ira_subloop_allocnos_can_differ_p (a, allocated_p: hard_regno >= 0,
3727	exclude_old_reload: false))
3728	{
3729	gcc_assert (!ALLOCNO_MIGHT_CONFLICT_WITH_PARENT_P
3730	(subloop_allocno));
3731	if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
3732	{
3733	ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
3734	ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
3735	if (hard_regno >= 0)
3736	update_costs_from_copies (allocno: subloop_allocno, decr_p: true, record_p: true);
3737	/* We don't need updated costs anymore. */
3738	ira_free_allocno_updated_costs (subloop_allocno);
3739	}
3740	}
3741	else if (hard_regno < 0)
3742	{
3743	/* If we allocate a register to SUBLOOP_ALLOCNO, we'll need
3744	to load the register on entry to the subloop and store
3745	the register back on exit from the subloop. This incurs
3746	a fixed cost for all registers. Since UPDATED_MEMORY_COST
3747	is (and should only be) used relative to the register costs
3748	for the same allocno, we can subtract this shared register
3749	cost from the memory cost. */
3750	ira_loop_border_costs border_costs (subloop_allocno);
3751	ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
3752	-= border_costs.spill_outside_loop_cost ();
3753	}
3754	else
3755	{
3756	ira_loop_border_costs border_costs (subloop_allocno);
3757	aclass = ALLOCNO_CLASS (subloop_allocno);
3758	ira_init_register_move_cost_if_necessary (mode);
3759	cost = border_costs.move_between_loops_cost ();
3760	ira_allocate_and_set_or_copy_costs
3761	(vec: &ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno), aclass,
3762	ALLOCNO_UPDATED_CLASS_COST (subloop_allocno),
3763	ALLOCNO_HARD_REG_COSTS (subloop_allocno));
3764	ira_allocate_and_set_or_copy_costs
3765	(vec: &ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno),
3766	aclass, val: 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno));
3767	ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
3768	ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
3769	-= cost;
3770	if (ALLOCNO_UPDATED_CLASS_COST (subloop_allocno)
3771	> ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index])
3772	ALLOCNO_UPDATED_CLASS_COST (subloop_allocno)
3773	= ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index];
3774	/* If we spill SUBLOOP_ALLOCNO, we'll need to store HARD_REGNO
3775	on entry to the subloop and restore HARD_REGNO on exit from
3776	the subloop. */
3777	ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
3778	+= border_costs.spill_inside_loop_cost ();
3779	}
3780	}
3781	}
3782	ira_free (addr: allocno_color_data);
3783	EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3784	{
3785	a = ira_allocnos[j];
3786	ALLOCNO_ADD_DATA (a) = NULL;
3787	}
3788	}
3789
3790	/* Initialize the common data for coloring and calls functions to do
3791	Chaitin-Briggs and regional coloring. */
3792	static void
3793	do_coloring (void)
3794	{
3795	coloring_allocno_bitmap = ira_allocate_bitmap ();
3796	if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3797	fprintf (stream: ira_dump_file, format: "\n**** Allocnos coloring:\n\n");
3798
3799	ira_traverse_loop_tree (false, ira_loop_tree_root, color_pass, NULL);
3800
3801	if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
3802	ira_print_disposition (ira_dump_file);
3803
3804	ira_free_bitmap (coloring_allocno_bitmap);
3805	}
3806
3807
3808
3809	/* Move spill/restore code, which are to be generated in ira-emit.cc,
3810	to less frequent points (if it is profitable) by reassigning some
3811	allocnos (in loop with subloops containing in another loop) to
3812	memory which results in longer live-range where the corresponding
3813	pseudo-registers will be in memory. */
3814	static void
3815	move_spill_restore (void)
3816	{
3817	int cost, regno, hard_regno, hard_regno2, index;
3818	bool changed_p;
3819	machine_mode mode;
3820	enum reg_class rclass;
3821	ira_allocno_t a, parent_allocno, subloop_allocno;
3822	ira_loop_tree_node_t parent, loop_node, subloop_node;
3823	ira_allocno_iterator ai;
3824
3825	for (;;)
3826	{
3827	changed_p = false;
3828	if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3829	fprintf (stream: ira_dump_file, format: "New iteration of spill/restore move\n");
3830	FOR_EACH_ALLOCNO (a, ai)
3831	{
3832	regno = ALLOCNO_REGNO (a);
3833	loop_node = ALLOCNO_LOOP_TREE_NODE (a);
3834	if (ALLOCNO_CAP_MEMBER (a) != NULL
3835	|| ALLOCNO_CAP (a) != NULL
3836	|| (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0
3837	|| loop_node->children == NULL
3838	/* don't do the optimization because it can create
3839	copies and the reload pass can spill the allocno set
3840	by copy although the allocno will not get memory
3841	slot. */
3842	|| ira_equiv_no_lvalue_p (regno)
3843	|| !bitmap_bit_p (loop_node->border_allocnos, ALLOCNO_NUM (a))
3844	/* Do not spill static chain pointer pseudo when
3845	non-local goto is used. */
3846	|| non_spilled_static_chain_regno_p (regno))
3847	continue;
3848	mode = ALLOCNO_MODE (a);
3849	rclass = ALLOCNO_CLASS (a);
3850	index = ira_class_hard_reg_index[rclass][hard_regno];
3851	ira_assert (index >= 0);
3852	cost = (ALLOCNO_MEMORY_COST (a)
3853	- (ALLOCNO_HARD_REG_COSTS (a) == NULL
3854	? ALLOCNO_CLASS_COST (a)
3855	: ALLOCNO_HARD_REG_COSTS (a)[index]));
3856	ira_init_register_move_cost_if_necessary (mode);
3857	for (subloop_node = loop_node->subloops;
3858	subloop_node != NULL;
3859	subloop_node = subloop_node->subloop_next)
3860	{
3861	ira_assert (subloop_node->bb == NULL);
3862	subloop_allocno = subloop_node->regno_allocno_map[regno];
3863	if (subloop_allocno == NULL)
3864	continue;
3865	ira_assert (rclass == ALLOCNO_CLASS (subloop_allocno));
3866	ira_loop_border_costs border_costs (subloop_allocno);
3867
3868	/* We have accumulated cost. To get the real cost of
3869	allocno usage in the loop we should subtract the costs
3870	added by propagate_allocno_info for the subloop allocnos. */
3871	int reg_cost
3872	= (ALLOCNO_HARD_REG_COSTS (subloop_allocno) == NULL
3873	? ALLOCNO_CLASS_COST (subloop_allocno)
3874	: ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index]);
3875
3876	int spill_cost
3877	= (border_costs.spill_inside_loop_cost ()
3878	+ ALLOCNO_MEMORY_COST (subloop_allocno));
3879
3880	/* If HARD_REGNO conflicts with SUBLOOP_A then
3881	propagate_allocno_info will have propagated
3882	the cost of spilling HARD_REGNO in SUBLOOP_NODE.
3883	(ira_subloop_allocnos_can_differ_p must be true
3884	in that case.) If HARD_REGNO is a caller-saved
3885	register, we might have modelled it in the same way.
3886
3887	Otherwise, SPILL_COST acted as a cap on the propagated
3888	register cost, in cases where the allocations can differ. */
3889	auto conflicts = ira_total_conflict_hard_regs (a: subloop_allocno);
3890	if (TEST_HARD_REG_BIT (set: conflicts, bit: hard_regno)
3891	|| (ira_need_caller_save_p (a: subloop_allocno, regno: hard_regno)
3892	&& ira_caller_save_loop_spill_p (a, subloop_a: subloop_allocno,
3893	spill_cost)))
3894	reg_cost = spill_cost;
3895	else if (ira_subloop_allocnos_can_differ_p (a))
3896	reg_cost = MIN (reg_cost, spill_cost);
3897
3898	cost -= ALLOCNO_MEMORY_COST (subloop_allocno) - reg_cost;
3899
3900	if ((hard_regno2 = ALLOCNO_HARD_REGNO (subloop_allocno)) < 0)
3901	/* The register was spilled in the subloop. If we spill
3902	it in the outer loop too then we'll no longer need to
3903	save the register on entry to the subloop and restore
3904	the register on exit from the subloop. */
3905	cost -= border_costs.spill_inside_loop_cost ();
3906	else
3907	{
3908	/* The register was also allocated in the subloop. If we
3909	spill it in the outer loop then we'll need to load the
3910	register on entry to the subloop and store the register
3911	back on exit from the subloop. */
3912	cost += border_costs.spill_outside_loop_cost ();
3913	if (hard_regno2 != hard_regno)
3914	cost -= border_costs.move_between_loops_cost ();
3915	}
3916	}
3917	if ((parent = loop_node->parent) != NULL
3918	&& (parent_allocno = parent->regno_allocno_map[regno]) != NULL)
3919	{
3920	ira_assert (rclass == ALLOCNO_CLASS (parent_allocno));
3921	ira_loop_border_costs border_costs (a);
3922	if ((hard_regno2 = ALLOCNO_HARD_REGNO (parent_allocno)) < 0)
3923	/* The register was spilled in the parent loop. If we spill
3924	it in this loop too then we'll no longer need to load the
3925	register on entry to this loop and save the register back
3926	on exit from this loop. */
3927	cost -= border_costs.spill_outside_loop_cost ();
3928	else
3929	{
3930	/* The register was also allocated in the parent loop.
3931	If we spill it in this loop then we'll need to save
3932	the register on entry to this loop and restore the
3933	register on exit from this loop. */
3934	cost += border_costs.spill_inside_loop_cost ();
3935	if (hard_regno2 != hard_regno)
3936	cost -= border_costs.move_between_loops_cost ();
3937	}
3938	}
3939	if (cost < 0)
3940	{
3941	ALLOCNO_HARD_REGNO (a) = -1;
3942	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3943	{
3944	fprintf
3945	(stream: ira_dump_file,
3946	format: " Moving spill/restore for a%dr%d up from loop %d",
3947	ALLOCNO_NUM (a), regno, loop_node->loop_num);
3948	fprintf (stream: ira_dump_file, format: " - profit %d\n", -cost);
3949	}
3950	changed_p = true;
3951	}
3952	}
3953	if (! changed_p)
3954	break;
3955	}
3956	}
3957
3958
3959
3960	/* Update current hard reg costs and current conflict hard reg costs
3961	for allocno A. It is done by processing its copies containing
3962	other allocnos already assigned. */
3963	static void
3964	update_curr_costs (ira_allocno_t a)
3965	{
3966	int i, hard_regno, cost;
3967	machine_mode mode;
3968	enum reg_class aclass, rclass;
3969	ira_allocno_t another_a;
3970	ira_copy_t cp, next_cp;
3971
3972	ira_free_allocno_updated_costs (a);
3973	ira_assert (! ALLOCNO_ASSIGNED_P (a));
3974	aclass = ALLOCNO_CLASS (a);
3975	if (aclass == NO_REGS)
3976	return;
3977	mode = ALLOCNO_MODE (a);
3978	ira_init_register_move_cost_if_necessary (mode);
3979	for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
3980	{
3981	if (cp->first == a)
3982	{
3983	next_cp = cp->next_first_allocno_copy;
3984	another_a = cp->second;
3985	}
3986	else if (cp->second == a)
3987	{
3988	next_cp = cp->next_second_allocno_copy;
3989	another_a = cp->first;
3990	}
3991	else
3992	gcc_unreachable ();
3993	if (! ira_reg_classes_intersect_p[aclass][ALLOCNO_CLASS (another_a)]
3994	|| ! ALLOCNO_ASSIGNED_P (another_a)
3995	|| (hard_regno = ALLOCNO_HARD_REGNO (another_a)) < 0)
3996	continue;
3997	rclass = REGNO_REG_CLASS (hard_regno);
3998	i = ira_class_hard_reg_index[aclass][hard_regno];
3999	if (i < 0)
4000	continue;
4001	cost = (cp->first == a
4002	? ira_register_move_cost[mode][rclass][aclass]
4003	: ira_register_move_cost[mode][aclass][rclass]);
4004	ira_allocate_and_set_or_copy_costs
4005	(vec: &ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass, ALLOCNO_CLASS_COST (a),
4006	ALLOCNO_HARD_REG_COSTS (a));
4007	ira_allocate_and_set_or_copy_costs
4008	(vec: &ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
4009	aclass, val: 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
4010	ALLOCNO_UPDATED_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
4011	ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
4012	}
4013	}
4014
4015	/* Try to assign hard registers to the unassigned allocnos and
4016	allocnos conflicting with them or conflicting with allocnos whose
4017	regno >= START_REGNO. The function is called after ira_flattening,
4018	so more allocnos (including ones created in ira-emit.cc) will have a
4019	chance to get a hard register. We use simple assignment algorithm
4020	based on priorities. */
4021	void
4022	ira_reassign_conflict_allocnos (int start_regno)
4023	{
4024	int i, allocnos_to_color_num;
4025	ira_allocno_t a;
4026	enum reg_class aclass;
4027	bitmap allocnos_to_color;
4028	ira_allocno_iterator ai;
4029
4030	allocnos_to_color = ira_allocate_bitmap ();
4031	allocnos_to_color_num = 0;
4032	FOR_EACH_ALLOCNO (a, ai)
4033	{
4034	int n = ALLOCNO_NUM_OBJECTS (a);
4035
4036	if (! ALLOCNO_ASSIGNED_P (a)
4037	&& ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a)))
4038	{
4039	if (ALLOCNO_CLASS (a) != NO_REGS)
4040	sorted_allocnos[allocnos_to_color_num++] = a;
4041	else
4042	{
4043	ALLOCNO_ASSIGNED_P (a) = true;
4044	ALLOCNO_HARD_REGNO (a) = -1;
4045	ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
4046	ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
4047	}
4048	bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (a));
4049	}
4050	if (ALLOCNO_REGNO (a) < start_regno
4051	|| (aclass = ALLOCNO_CLASS (a)) == NO_REGS)
4052	continue;
4053	for (i = 0; i < n; i++)
4054	{
4055	ira_object_t obj = ALLOCNO_OBJECT (a, i);
4056	ira_object_t conflict_obj;
4057	ira_object_conflict_iterator oci;
4058
4059	FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
4060	{
4061	ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
4062
4063	ira_assert (ira_reg_classes_intersect_p
4064	[aclass][ALLOCNO_CLASS (conflict_a)]);
4065	if (!bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a)))
4066	continue;
4067	sorted_allocnos[allocnos_to_color_num++] = conflict_a;
4068	}
4069	}
4070	}
4071	ira_free_bitmap (allocnos_to_color);
4072	if (allocnos_to_color_num > 1)
4073	{
4074	setup_allocno_priorities (consideration_allocnos: sorted_allocnos, n: allocnos_to_color_num);
4075	qsort (sorted_allocnos, allocnos_to_color_num, sizeof (ira_allocno_t),
4076	allocno_priority_compare_func);
4077	}
4078	for (i = 0; i < allocnos_to_color_num; i++)
4079	{
4080	a = sorted_allocnos[i];
4081	ALLOCNO_ASSIGNED_P (a) = false;
4082	update_curr_costs (a);
4083	}
4084	for (i = 0; i < allocnos_to_color_num; i++)
4085	{
4086	a = sorted_allocnos[i];
4087	if (assign_hard_reg (a, retry_p: true))
4088	{
4089	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4090	fprintf
4091	(stream: ira_dump_file,
4092	format: " Secondary allocation: assign hard reg %d to reg %d\n",
4093	ALLOCNO_HARD_REGNO (a), ALLOCNO_REGNO (a));
4094	}
4095	}
4096	}
4097
4098
4099
4100	/* This page contains functions used to find conflicts using allocno
4101	live ranges. */
4102
4103	#ifdef ENABLE_IRA_CHECKING
4104
4105	/* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
4106	intersect. This should be used when there is only one region.
4107	Currently this is used during reload. */
4108	static bool
4109	conflict_by_live_ranges_p (int regno1, int regno2)
4110	{
4111	ira_allocno_t a1, a2;
4112
4113	ira_assert (regno1 >= FIRST_PSEUDO_REGISTER
4114	&& regno2 >= FIRST_PSEUDO_REGISTER);
4115	/* Reg info calculated by dataflow infrastructure can be different
4116	from one calculated by regclass. */
4117	if ((a1 = ira_loop_tree_root->regno_allocno_map[regno1]) == NULL
4118	|| (a2 = ira_loop_tree_root->regno_allocno_map[regno2]) == NULL)
4119	return false;
4120	return allocnos_conflict_by_live_ranges_p (a1, a2);
4121	}
4122
4123	#endif
4124
4125
4126
4127	/* This page contains code to coalesce memory stack slots used by
4128	spilled allocnos. This results in smaller stack frame, better data
4129	locality, and in smaller code for some architectures like
4130	x86/x86_64 where insn size depends on address displacement value.
4131	On the other hand, it can worsen insn scheduling after the RA but
4132	in practice it is less important than smaller stack frames. */
4133
4134	/* TRUE if we coalesced some allocnos. In other words, if we got
4135	loops formed by members first_coalesced_allocno and
4136	next_coalesced_allocno containing more one allocno. */
4137	static bool allocno_coalesced_p;
4138
4139	/* Bitmap used to prevent a repeated allocno processing because of
4140	coalescing. */
4141	static bitmap processed_coalesced_allocno_bitmap;
4142
4143	/* See below. */
4144	typedef struct coalesce_data *coalesce_data_t;
4145
4146	/* To decrease footprint of ira_allocno structure we store all data
4147	needed only for coalescing in the following structure. */
4148	struct coalesce_data
4149	{
4150	/* Coalesced allocnos form a cyclic list. One allocno given by
4151	FIRST represents all coalesced allocnos. The
4152	list is chained by NEXT. */
4153	ira_allocno_t first;
4154	ira_allocno_t next;
4155	int temp;
4156	};
4157
4158	/* Container for storing allocno data concerning coalescing. */
4159	static coalesce_data_t allocno_coalesce_data;
4160
4161	/* Macro to access the data concerning coalescing. */
4162	#define ALLOCNO_COALESCE_DATA(a) ((coalesce_data_t) ALLOCNO_ADD_DATA (a))
4163
4164	/* Merge two sets of coalesced allocnos given correspondingly by
4165	allocnos A1 and A2 (more accurately merging A2 set into A1
4166	set). */
4167	static void
4168	merge_allocnos (ira_allocno_t a1, ira_allocno_t a2)
4169	{
4170	ira_allocno_t a, first, last, next;
4171
4172	first = ALLOCNO_COALESCE_DATA (a1)->first;
4173	a = ALLOCNO_COALESCE_DATA (a2)->first;
4174	if (first == a)
4175	return;
4176	for (last = a2, a = ALLOCNO_COALESCE_DATA (a2)->next;;
4177	a = ALLOCNO_COALESCE_DATA (a)->next)
4178	{
4179	ALLOCNO_COALESCE_DATA (a)->first = first;
4180	if (a == a2)
4181	break;
4182	last = a;
4183	}
4184	next = allocno_coalesce_data[ALLOCNO_NUM (first)].next;
4185	allocno_coalesce_data[ALLOCNO_NUM (first)].next = a2;
4186	allocno_coalesce_data[ALLOCNO_NUM (last)].next = next;
4187	}
4188
4189	/* Return TRUE if there are conflicting allocnos from two sets of
4190	coalesced allocnos given correspondingly by allocnos A1 and A2. We
4191	use live ranges to find conflicts because conflicts are represented
4192	only for allocnos of the same allocno class and during the reload
4193	pass we coalesce allocnos for sharing stack memory slots. */
4194	static bool
4195	coalesced_allocno_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
4196	{
4197	ira_allocno_t a, conflict_a;
4198
4199	if (allocno_coalesced_p)
4200	{
4201	bitmap_clear (processed_coalesced_allocno_bitmap);
4202	for (a = ALLOCNO_COALESCE_DATA (a1)->next;;
4203	a = ALLOCNO_COALESCE_DATA (a)->next)
4204	{
4205	bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a));
4206	if (a == a1)
4207	break;
4208	}
4209	}
4210	for (a = ALLOCNO_COALESCE_DATA (a2)->next;;
4211	a = ALLOCNO_COALESCE_DATA (a)->next)
4212	{
4213	for (conflict_a = ALLOCNO_COALESCE_DATA (a1)->next;;
4214	conflict_a = ALLOCNO_COALESCE_DATA (conflict_a)->next)
4215	{
4216	if (allocnos_conflict_by_live_ranges_p (a1: a, a2: conflict_a))
4217	return true;
4218	if (conflict_a == a1)
4219	break;
4220	}
4221	if (a == a2)
4222	break;
4223	}
4224	return false;
4225	}
4226
4227	/* The major function for aggressive allocno coalescing. We coalesce
4228	only spilled allocnos. If some allocnos have been coalesced, we
4229	set up flag allocno_coalesced_p. */
4230	static void
4231	coalesce_allocnos (void)
4232	{
4233	ira_allocno_t a;
4234	ira_copy_t cp, next_cp;
4235	unsigned int j;
4236	int i, n, cp_num, regno;
4237	bitmap_iterator bi;
4238
4239	cp_num = 0;
4240	/* Collect copies. */
4241	EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
4242	{
4243	a = ira_allocnos[j];
4244	regno = ALLOCNO_REGNO (a);
4245	if (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0
4246	|| ira_equiv_no_lvalue_p (regno))
4247	continue;
4248	for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
4249	{
4250	if (cp->first == a)
4251	{
4252	next_cp = cp->next_first_allocno_copy;
4253	regno = ALLOCNO_REGNO (cp->second);
4254	/* For priority coloring we coalesce allocnos only with
4255	the same allocno class not with intersected allocno
4256	classes as it were possible. It is done for
4257	simplicity. */
4258	if ((cp->insn != NULL || cp->constraint_p)
4259	&& ALLOCNO_ASSIGNED_P (cp->second)
4260	&& ALLOCNO_HARD_REGNO (cp->second) < 0
4261	&& ! ira_equiv_no_lvalue_p (regno))
4262	sorted_copies[cp_num++] = cp;
4263	}
4264	else if (cp->second == a)
4265	next_cp = cp->next_second_allocno_copy;
4266	else
4267	gcc_unreachable ();
4268	}
4269	}
4270	qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
4271	/* Coalesced copies, most frequently executed first. */
4272	for (; cp_num != 0;)
4273	{
4274	for (i = 0; i < cp_num; i++)
4275	{
4276	cp = sorted_copies[i];
4277	if (! coalesced_allocno_conflict_p (a1: cp->first, a2: cp->second))
4278	{
4279	allocno_coalesced_p = true;
4280	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4281	fprintf
4282	(stream: ira_dump_file,
4283	format: " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
4284	cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
4285	ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
4286	cp->freq);
4287	merge_allocnos (a1: cp->first, a2: cp->second);
4288	i++;
4289	break;
4290	}
4291	}
4292	/* Collect the rest of copies. */
4293	for (n = 0; i < cp_num; i++)
4294	{
4295	cp = sorted_copies[i];
4296	if (allocno_coalesce_data[ALLOCNO_NUM (cp->first)].first
4297	!= allocno_coalesce_data[ALLOCNO_NUM (cp->second)].first)
4298	sorted_copies[n++] = cp;
4299	}
4300	cp_num = n;
4301	}
4302	}
4303
4304	/* Usage cost and order number of coalesced allocno set to which
4305	given pseudo register belongs to. */
4306	static int *regno_coalesced_allocno_cost;
4307	static int *regno_coalesced_allocno_num;
4308
4309	/* Sort pseudos according frequencies of coalesced allocno sets they
4310	belong to (putting most frequently ones first), and according to
4311	coalesced allocno set order numbers. */
4312	static int
4313	coalesced_pseudo_reg_freq_compare (const void *v1p, const void *v2p)
4314	{
4315	const int regno1 = *(const int *) v1p;
4316	const int regno2 = *(const int *) v2p;
4317	int diff;
4318
4319	if ((diff = (regno_coalesced_allocno_cost[regno2]
4320	- regno_coalesced_allocno_cost[regno1])) != 0)
4321	return diff;
4322	if ((diff = (regno_coalesced_allocno_num[regno1]
4323	- regno_coalesced_allocno_num[regno2])) != 0)
4324	return diff;
4325	return regno1 - regno2;
4326	}
4327
4328	/* Widest width in which each pseudo reg is referred to (via subreg).
4329	It is used for sorting pseudo registers. */
4330	static machine_mode *regno_max_ref_mode;
4331
4332	/* Sort pseudos according their slot numbers (putting ones with
4333	smaller numbers first, or last when the frame pointer is not
4334	needed). */
4335	static int
4336	coalesced_pseudo_reg_slot_compare (const void *v1p, const void *v2p)
4337	{
4338	const int regno1 = *(const int *) v1p;
4339	const int regno2 = *(const int *) v2p;
4340	ira_allocno_t a1 = ira_regno_allocno_map[regno1];
4341	ira_allocno_t a2 = ira_regno_allocno_map[regno2];
4342	int diff, slot_num1, slot_num2;
4343	machine_mode mode1, mode2;
4344
4345	if (a1 == NULL || ALLOCNO_HARD_REGNO (a1) >= 0)
4346	{
4347	if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
4348	return regno1 - regno2;
4349	return 1;
4350	}
4351	else if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
4352	return -1;
4353	slot_num1 = -ALLOCNO_HARD_REGNO (a1);
4354	slot_num2 = -ALLOCNO_HARD_REGNO (a2);
4355	if ((diff = slot_num1 - slot_num2) != 0)
4356	return (frame_pointer_needed
4357	|| (!FRAME_GROWS_DOWNWARD) == STACK_GROWS_DOWNWARD ? diff : -diff);
4358	mode1 = wider_subreg_mode (PSEUDO_REGNO_MODE (regno1),
4359	innermode: regno_max_ref_mode[regno1]);
4360	mode2 = wider_subreg_mode (PSEUDO_REGNO_MODE (regno2),
4361	innermode: regno_max_ref_mode[regno2]);
4362	if ((diff = compare_sizes_for_sort (a: GET_MODE_SIZE (mode: mode2),
4363	b: GET_MODE_SIZE (mode: mode1))) != 0)
4364	return diff;
4365	return regno1 - regno2;
4366	}
4367
4368	/* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
4369	for coalesced allocno sets containing allocnos with their regnos
4370	given in array PSEUDO_REGNOS of length N. */
4371	static void
4372	setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos, int n)
4373	{
4374	int i, num, regno, cost;
4375	ira_allocno_t allocno, a;
4376
4377	for (num = i = 0; i < n; i++)
4378	{
4379	regno = pseudo_regnos[i];
4380	allocno = ira_regno_allocno_map[regno];
4381	if (allocno == NULL)
4382	{
4383	regno_coalesced_allocno_cost[regno] = 0;
4384	regno_coalesced_allocno_num[regno] = ++num;
4385	continue;
4386	}
4387	if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno)
4388	continue;
4389	num++;
4390	for (cost = 0, a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4391	a = ALLOCNO_COALESCE_DATA (a)->next)
4392	{
4393	cost += ALLOCNO_FREQ (a);
4394	if (a == allocno)
4395	break;
4396	}
4397	for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4398	a = ALLOCNO_COALESCE_DATA (a)->next)
4399	{
4400	regno_coalesced_allocno_num[ALLOCNO_REGNO (a)] = num;
4401	regno_coalesced_allocno_cost[ALLOCNO_REGNO (a)] = cost;
4402	if (a == allocno)
4403	break;
4404	}
4405	}
4406	}
4407
4408	/* Collect spilled allocnos representing coalesced allocno sets (the
4409	first coalesced allocno). The collected allocnos are returned
4410	through array SPILLED_COALESCED_ALLOCNOS. The function returns the
4411	number of the collected allocnos. The allocnos are given by their
4412	regnos in array PSEUDO_REGNOS of length N. */
4413	static int
4414	collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n,
4415	ira_allocno_t *spilled_coalesced_allocnos)
4416	{
4417	int i, num, regno;
4418	ira_allocno_t allocno;
4419
4420	for (num = i = 0; i < n; i++)
4421	{
4422	regno = pseudo_regnos[i];
4423	allocno = ira_regno_allocno_map[regno];
4424	if (allocno == NULL || ALLOCNO_HARD_REGNO (allocno) >= 0
4425	|| ALLOCNO_COALESCE_DATA (allocno)->first != allocno)
4426	continue;
4427	spilled_coalesced_allocnos[num++] = allocno;
4428	}
4429	return num;
4430	}
4431
4432	/* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
4433	given slot contains live ranges of coalesced allocnos assigned to
4434	given slot. */
4435	static live_range_t *slot_coalesced_allocnos_live_ranges;
4436
4437	/* Return TRUE if coalesced allocnos represented by ALLOCNO has live
4438	ranges intersected with live ranges of coalesced allocnos assigned
4439	to slot with number N. */
4440	static bool
4441	slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno, int n)
4442	{
4443	ira_allocno_t a;
4444
4445	for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4446	a = ALLOCNO_COALESCE_DATA (a)->next)
4447	{
4448	int i;
4449	int nr = ALLOCNO_NUM_OBJECTS (a);
4450	gcc_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
4451	for (i = 0; i < nr; i++)
4452	{
4453	ira_object_t obj = ALLOCNO_OBJECT (a, i);
4454
4455	if (ira_live_ranges_intersect_p
4456	(slot_coalesced_allocnos_live_ranges[n],
4457	OBJECT_LIVE_RANGES (obj)))
4458	return true;
4459	}
4460	if (a == allocno)
4461	break;
4462	}
4463	return false;
4464	}
4465
4466	/* Update live ranges of slot to which coalesced allocnos represented
4467	by ALLOCNO were assigned. */
4468	static void
4469	setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno)
4470	{
4471	int i, n;
4472	ira_allocno_t a;
4473	live_range_t r;
4474
4475	n = ALLOCNO_COALESCE_DATA (allocno)->temp;
4476	for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4477	a = ALLOCNO_COALESCE_DATA (a)->next)
4478	{
4479	int nr = ALLOCNO_NUM_OBJECTS (a);
4480	gcc_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
4481	for (i = 0; i < nr; i++)
4482	{
4483	ira_object_t obj = ALLOCNO_OBJECT (a, i);
4484
4485	r = ira_copy_live_range_list (OBJECT_LIVE_RANGES (obj));
4486	slot_coalesced_allocnos_live_ranges[n]
4487	= ira_merge_live_ranges
4488	(slot_coalesced_allocnos_live_ranges[n], r);
4489	}
4490	if (a == allocno)
4491	break;
4492	}
4493	}
4494
4495	/* We have coalesced allocnos involving in copies. Coalesce allocnos
4496	further in order to share the same memory stack slot. Allocnos
4497	representing sets of allocnos coalesced before the call are given
4498	in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
4499	some allocnos were coalesced in the function. */
4500	static bool
4501	coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num)
4502	{
4503	int i, j, n, last_coalesced_allocno_num;
4504	ira_allocno_t allocno, a;
4505	bool merged_p = false;
4506	bitmap set_jump_crosses = regstat_get_setjmp_crosses ();
4507
4508	slot_coalesced_allocnos_live_ranges
4509	= (live_range_t *) ira_allocate (sizeof (live_range_t) * ira_allocnos_num);
4510	memset (s: slot_coalesced_allocnos_live_ranges, c: 0,
4511	n: sizeof (live_range_t) * ira_allocnos_num);
4512	last_coalesced_allocno_num = 0;
4513	/* Coalesce non-conflicting spilled allocnos preferring most
4514	frequently used. */
4515	for (i = 0; i < num; i++)
4516	{
4517	allocno = spilled_coalesced_allocnos[i];
4518	if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno
4519	|| bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (allocno))
4520	|| ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno)))
4521	continue;
4522	for (j = 0; j < i; j++)
4523	{
4524	a = spilled_coalesced_allocnos[j];
4525	n = ALLOCNO_COALESCE_DATA (a)->temp;
4526	if (ALLOCNO_COALESCE_DATA (a)->first == a
4527	&& ! bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (a))
4528	&& ! ira_equiv_no_lvalue_p (ALLOCNO_REGNO (a))
4529	&& ! slot_coalesced_allocno_live_ranges_intersect_p (allocno, n))
4530	break;
4531	}
4532	if (j >= i)
4533	{
4534	/* No coalescing: set up number for coalesced allocnos
4535	represented by ALLOCNO. */
4536	ALLOCNO_COALESCE_DATA (allocno)->temp = last_coalesced_allocno_num++;
4537	setup_slot_coalesced_allocno_live_ranges (allocno);
4538	}
4539	else
4540	{
4541	allocno_coalesced_p = true;
4542	merged_p = true;
4543	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4544	fprintf (stream: ira_dump_file,
4545	format: " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
4546	ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno),
4547	ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
4548	ALLOCNO_COALESCE_DATA (allocno)->temp
4549	= ALLOCNO_COALESCE_DATA (a)->temp;
4550	setup_slot_coalesced_allocno_live_ranges (allocno);
4551	merge_allocnos (a1: a, a2: allocno);
4552	ira_assert (ALLOCNO_COALESCE_DATA (a)->first == a);
4553	}
4554	}
4555	for (i = 0; i < ira_allocnos_num; i++)
4556	ira_finish_live_range_list (slot_coalesced_allocnos_live_ranges[i]);
4557	ira_free (addr: slot_coalesced_allocnos_live_ranges);
4558	return merged_p;
4559	}
4560
4561	/* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
4562	subsequent assigning stack slots to them in the reload pass. To do
4563	this we coalesce spilled allocnos first to decrease the number of
4564	memory-memory move insns. This function is called by the
4565	reload. */
4566	void
4567	ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n,
4568	machine_mode *reg_max_ref_mode)
4569	{
4570	int max_regno = max_reg_num ();
4571	int i, regno, num, slot_num;
4572	ira_allocno_t allocno, a;
4573	ira_allocno_iterator ai;
4574	ira_allocno_t *spilled_coalesced_allocnos;
4575
4576	ira_assert (! ira_use_lra_p);
4577
4578	/* Set up allocnos can be coalesced. */
4579	coloring_allocno_bitmap = ira_allocate_bitmap ();
4580	for (i = 0; i < n; i++)
4581	{
4582	regno = pseudo_regnos[i];
4583	allocno = ira_regno_allocno_map[regno];
4584	if (allocno != NULL)
4585	bitmap_set_bit (coloring_allocno_bitmap, ALLOCNO_NUM (allocno));
4586	}
4587	allocno_coalesced_p = false;
4588	processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
4589	allocno_coalesce_data
4590	= (coalesce_data_t) ira_allocate (sizeof (struct coalesce_data)
4591	* ira_allocnos_num);
4592	/* Initialize coalesce data for allocnos. */
4593	FOR_EACH_ALLOCNO (a, ai)
4594	{
4595	ALLOCNO_ADD_DATA (a) = allocno_coalesce_data + ALLOCNO_NUM (a);
4596	ALLOCNO_COALESCE_DATA (a)->first = a;
4597	ALLOCNO_COALESCE_DATA (a)->next = a;
4598	}
4599	coalesce_allocnos ();
4600	ira_free_bitmap (coloring_allocno_bitmap);
4601	regno_coalesced_allocno_cost
4602	= (int *) ira_allocate (max_regno * sizeof (int));
4603	regno_coalesced_allocno_num
4604	= (int *) ira_allocate (max_regno * sizeof (int));
4605	memset (s: regno_coalesced_allocno_num, c: 0, n: max_regno * sizeof (int));
4606	setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
4607	/* Sort regnos according frequencies of the corresponding coalesced
4608	allocno sets. */
4609	qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_freq_compare);
4610	spilled_coalesced_allocnos
4611	= (ira_allocno_t *) ira_allocate (ira_allocnos_num
4612	* sizeof (ira_allocno_t));
4613	/* Collect allocnos representing the spilled coalesced allocno
4614	sets. */
4615	num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
4616	spilled_coalesced_allocnos);
4617	if (flag_ira_share_spill_slots
4618	&& coalesce_spill_slots (spilled_coalesced_allocnos, num))
4619	{
4620	setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
4621	qsort (pseudo_regnos, n, sizeof (int),
4622	coalesced_pseudo_reg_freq_compare);
4623	num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
4624	spilled_coalesced_allocnos);
4625	}
4626	ira_free_bitmap (processed_coalesced_allocno_bitmap);
4627	allocno_coalesced_p = false;
4628	/* Assign stack slot numbers to spilled allocno sets, use smaller
4629	numbers for most frequently used coalesced allocnos. -1 is
4630	reserved for dynamic search of stack slots for pseudos spilled by
4631	the reload. */
4632	slot_num = 1;
4633	for (i = 0; i < num; i++)
4634	{
4635	allocno = spilled_coalesced_allocnos[i];
4636	if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno
4637	|| ALLOCNO_HARD_REGNO (allocno) >= 0
4638	|| ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno)))
4639	continue;
4640	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4641	fprintf (stream: ira_dump_file, format: " Slot %d (freq,size):", slot_num);
4642	slot_num++;
4643	for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4644	a = ALLOCNO_COALESCE_DATA (a)->next)
4645	{
4646	ira_assert (ALLOCNO_HARD_REGNO (a) < 0);
4647	ALLOCNO_HARD_REGNO (a) = -slot_num;
4648	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4649	{
4650	machine_mode mode = wider_subreg_mode
4651	(PSEUDO_REGNO_MODE (ALLOCNO_REGNO (a)),
4652	innermode: reg_max_ref_mode[ALLOCNO_REGNO (a)]);
4653	fprintf (stream: ira_dump_file, format: " a%dr%d(%d,",
4654	ALLOCNO_NUM (a), ALLOCNO_REGNO (a), ALLOCNO_FREQ (a));
4655	print_dec (value: GET_MODE_SIZE (mode), file: ira_dump_file, sgn: SIGNED);
4656	fprintf (stream: ira_dump_file, format: ")\n");
4657	}
4658
4659	if (a == allocno)
4660	break;
4661	}
4662	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4663	fprintf (stream: ira_dump_file, format: "\n");
4664	}
4665	ira_spilled_reg_stack_slots_num = slot_num - 1;
4666	ira_free (addr: spilled_coalesced_allocnos);
4667	/* Sort regnos according the slot numbers. */
4668	regno_max_ref_mode = reg_max_ref_mode;
4669	qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_slot_compare);
4670	FOR_EACH_ALLOCNO (a, ai)
4671	ALLOCNO_ADD_DATA (a) = NULL;
4672	ira_free (addr: allocno_coalesce_data);
4673	ira_free (addr: regno_coalesced_allocno_num);
4674	ira_free (addr: regno_coalesced_allocno_cost);
4675	}
4676
4677
4678
4679	/* This page contains code used by the reload pass to improve the
4680	final code. */
4681
4682	/* The function is called from reload to mark changes in the
4683	allocation of REGNO made by the reload. Remember that reg_renumber
4684	reflects the change result. */
4685	void
4686	ira_mark_allocation_change (int regno)
4687	{
4688	ira_allocno_t a = ira_regno_allocno_map[regno];
4689	int old_hard_regno, hard_regno, cost;
4690	enum reg_class aclass = ALLOCNO_CLASS (a);
4691
4692	ira_assert (a != NULL);
4693	hard_regno = reg_renumber[regno];
4694	if ((old_hard_regno = ALLOCNO_HARD_REGNO (a)) == hard_regno)
4695	return;
4696	if (old_hard_regno < 0)
4697	cost = -ALLOCNO_MEMORY_COST (a);
4698	else
4699	{
4700	ira_assert (ira_class_hard_reg_index[aclass][old_hard_regno] >= 0);
4701	cost = -(ALLOCNO_HARD_REG_COSTS (a) == NULL
4702	? ALLOCNO_CLASS_COST (a)
4703	: ALLOCNO_HARD_REG_COSTS (a)
4704	[ira_class_hard_reg_index[aclass][old_hard_regno]]);
4705	update_costs_from_copies (allocno: a, decr_p: false, record_p: false);
4706	}
4707	ira_overall_cost -= cost;
4708	ALLOCNO_HARD_REGNO (a) = hard_regno;
4709	if (hard_regno < 0)
4710	{
4711	ALLOCNO_HARD_REGNO (a) = -1;
4712	cost += ALLOCNO_MEMORY_COST (a);
4713	}
4714	else if (ira_class_hard_reg_index[aclass][hard_regno] >= 0)
4715	{
4716	cost += (ALLOCNO_HARD_REG_COSTS (a) == NULL
4717	? ALLOCNO_CLASS_COST (a)
4718	: ALLOCNO_HARD_REG_COSTS (a)
4719	[ira_class_hard_reg_index[aclass][hard_regno]]);
4720	update_costs_from_copies (allocno: a, decr_p: true, record_p: false);
4721	}
4722	else
4723	/* Reload changed class of the allocno. */
4724	cost = 0;
4725	ira_overall_cost += cost;
4726	}
4727
4728	/* This function is called when reload deletes memory-memory move. In
4729	this case we marks that the allocation of the corresponding
4730	allocnos should be not changed in future. Otherwise we risk to get
4731	a wrong code. */
4732	void
4733	ira_mark_memory_move_deletion (int dst_regno, int src_regno)
4734	{
4735	ira_allocno_t dst = ira_regno_allocno_map[dst_regno];
4736	ira_allocno_t src = ira_regno_allocno_map[src_regno];
4737
4738	ira_assert (dst != NULL && src != NULL
4739	&& ALLOCNO_HARD_REGNO (dst) < 0
4740	&& ALLOCNO_HARD_REGNO (src) < 0);
4741	ALLOCNO_DONT_REASSIGN_P (dst) = true;
4742	ALLOCNO_DONT_REASSIGN_P (src) = true;
4743	}
4744
4745	/* Try to assign a hard register (except for FORBIDDEN_REGS) to
4746	allocno A and return TRUE in the case of success. */
4747	static bool
4748	allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs)
4749	{
4750	int hard_regno;
4751	enum reg_class aclass;
4752	int regno = ALLOCNO_REGNO (a);
4753	HARD_REG_SET saved[2];
4754	int i, n;
4755
4756	n = ALLOCNO_NUM_OBJECTS (a);
4757	for (i = 0; i < n; i++)
4758	{
4759	ira_object_t obj = ALLOCNO_OBJECT (a, i);
4760	saved[i] = OBJECT_TOTAL_CONFLICT_HARD_REGS (obj);
4761	OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= forbidden_regs;
4762	if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
4763	OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= ira_need_caller_save_regs (a);
4764	}
4765	ALLOCNO_ASSIGNED_P (a) = false;
4766	aclass = ALLOCNO_CLASS (a);
4767	update_curr_costs (a);
4768	assign_hard_reg (a, retry_p: true);
4769	hard_regno = ALLOCNO_HARD_REGNO (a);
4770	reg_renumber[regno] = hard_regno;
4771	if (hard_regno < 0)
4772	ALLOCNO_HARD_REGNO (a) = -1;
4773	else
4774	{
4775	ira_assert (ira_class_hard_reg_index[aclass][hard_regno] >= 0);
4776	ira_overall_cost
4777	-= (ALLOCNO_MEMORY_COST (a)
4778	- (ALLOCNO_HARD_REG_COSTS (a) == NULL
4779	? ALLOCNO_CLASS_COST (a)
4780	: ALLOCNO_HARD_REG_COSTS (a)[ira_class_hard_reg_index
4781	[aclass][hard_regno]]));
4782	if (ira_need_caller_save_p (a, regno: hard_regno))
4783	{
4784	ira_assert (flag_caller_saves);
4785	caller_save_needed = 1;
4786	}
4787	}
4788
4789	/* If we found a hard register, modify the RTL for the pseudo
4790	register to show the hard register, and mark the pseudo register
4791	live. */
4792	if (reg_renumber[regno] >= 0)
4793	{
4794	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4795	fprintf (stream: ira_dump_file, format: ": reassign to %d\n", reg_renumber[regno]);
4796	SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
4797	mark_home_live (regno);
4798	}
4799	else if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4800	fprintf (stream: ira_dump_file, format: "\n");
4801	for (i = 0; i < n; i++)
4802	{
4803	ira_object_t obj = ALLOCNO_OBJECT (a, i);
4804	OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) = saved[i];
4805	}
4806	return reg_renumber[regno] >= 0;
4807	}
4808
4809	/* Sort pseudos according their usage frequencies (putting most
4810	frequently ones first). */
4811	static int
4812	pseudo_reg_compare (const void *v1p, const void *v2p)
4813	{
4814	int regno1 = *(const int *) v1p;
4815	int regno2 = *(const int *) v2p;
4816	int diff;
4817
4818	if ((diff = REG_FREQ (regno2) - REG_FREQ (regno1)) != 0)
4819	return diff;
4820	return regno1 - regno2;
4821	}
4822
4823	/* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
4824	NUM of them) or spilled pseudos conflicting with pseudos in
4825	SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
4826	allocation has been changed. The function doesn't use
4827	BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
4828	PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
4829	is called by the reload pass at the end of each reload
4830	iteration. */
4831	bool
4832	ira_reassign_pseudos (int *spilled_pseudo_regs, int num,
4833	HARD_REG_SET bad_spill_regs,
4834	HARD_REG_SET *pseudo_forbidden_regs,
4835	HARD_REG_SET *pseudo_previous_regs,
4836	bitmap spilled)
4837	{
4838	int i, n, regno;
4839	bool changed_p;
4840	ira_allocno_t a;
4841	HARD_REG_SET forbidden_regs;
4842	bitmap temp = BITMAP_ALLOC (NULL);
4843
4844	/* Add pseudos which conflict with pseudos already in
4845	SPILLED_PSEUDO_REGS to SPILLED_PSEUDO_REGS. This is preferable
4846	to allocating in two steps as some of the conflicts might have
4847	a higher priority than the pseudos passed in SPILLED_PSEUDO_REGS. */
4848	for (i = 0; i < num; i++)
4849	bitmap_set_bit (temp, spilled_pseudo_regs[i]);
4850
4851	for (i = 0, n = num; i < n; i++)
4852	{
4853	int nr, j;
4854	int regno = spilled_pseudo_regs[i];
4855	bitmap_set_bit (temp, regno);
4856
4857	a = ira_regno_allocno_map[regno];
4858	nr = ALLOCNO_NUM_OBJECTS (a);
4859	for (j = 0; j < nr; j++)
4860	{
4861	ira_object_t conflict_obj;
4862	ira_object_t obj = ALLOCNO_OBJECT (a, j);
4863	ira_object_conflict_iterator oci;
4864
4865	FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
4866	{
4867	ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
4868	if (ALLOCNO_HARD_REGNO (conflict_a) < 0
4869	&& ! ALLOCNO_DONT_REASSIGN_P (conflict_a)
4870	&& bitmap_set_bit (temp, ALLOCNO_REGNO (conflict_a)))
4871	{
4872	spilled_pseudo_regs[num++] = ALLOCNO_REGNO (conflict_a);
4873	/* ?!? This seems wrong. */
4874	bitmap_set_bit (consideration_allocno_bitmap,
4875	ALLOCNO_NUM (conflict_a));
4876	}
4877	}
4878	}
4879	}
4880
4881	if (num > 1)
4882	qsort (spilled_pseudo_regs, num, sizeof (int), pseudo_reg_compare);
4883	changed_p = false;
4884	/* Try to assign hard registers to pseudos from
4885	SPILLED_PSEUDO_REGS. */
4886	for (i = 0; i < num; i++)
4887	{
4888	regno = spilled_pseudo_regs[i];
4889	forbidden_regs = (bad_spill_regs
4890	| pseudo_forbidden_regs[regno]
4891	| pseudo_previous_regs[regno]);
4892	gcc_assert (reg_renumber[regno] < 0);
4893	a = ira_regno_allocno_map[regno];
4894	ira_mark_allocation_change (regno);
4895	ira_assert (reg_renumber[regno] < 0);
4896	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4897	fprintf (stream: ira_dump_file,
4898	format: " Try Assign %d(a%d), cost=%d", regno, ALLOCNO_NUM (a),
4899	ALLOCNO_MEMORY_COST (a)
4900	- ALLOCNO_CLASS_COST (a));
4901	allocno_reload_assign (a, forbidden_regs);
4902	if (reg_renumber[regno] >= 0)
4903	{
4904	CLEAR_REGNO_REG_SET (spilled, regno);
4905	changed_p = true;
4906	}
4907	}
4908	BITMAP_FREE (temp);
4909	return changed_p;
4910	}
4911
4912	/* The function is called by reload and returns already allocated
4913	stack slot (if any) for REGNO with given INHERENT_SIZE and
4914	TOTAL_SIZE. In the case of failure to find a slot which can be
4915	used for REGNO, the function returns NULL. */
4916	rtx
4917	ira_reuse_stack_slot (int regno, poly_uint64 inherent_size,
4918	poly_uint64 total_size)
4919	{
4920	unsigned int i;
4921	int slot_num, best_slot_num;
4922	int cost, best_cost;
4923	ira_copy_t cp, next_cp;
4924	ira_allocno_t another_allocno, allocno = ira_regno_allocno_map[regno];
4925	rtx x;
4926	bitmap_iterator bi;
4927	class ira_spilled_reg_stack_slot *slot = NULL;
4928
4929	ira_assert (! ira_use_lra_p);
4930
4931	ira_assert (known_eq (inherent_size, PSEUDO_REGNO_BYTES (regno))
4932	&& known_le (inherent_size, total_size)
4933	&& ALLOCNO_HARD_REGNO (allocno) < 0);
4934	if (! flag_ira_share_spill_slots)
4935	return NULL_RTX;
4936	slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
4937	if (slot_num != -1)
4938	{
4939	slot = &ira_spilled_reg_stack_slots[slot_num];
4940	x = slot->mem;
4941	}
4942	else
4943	{
4944	best_cost = best_slot_num = -1;
4945	x = NULL_RTX;
4946	/* It means that the pseudo was spilled in the reload pass, try
4947	to reuse a slot. */
4948	for (slot_num = 0;
4949	slot_num < ira_spilled_reg_stack_slots_num;
4950	slot_num++)
4951	{
4952	slot = &ira_spilled_reg_stack_slots[slot_num];
4953	if (slot->mem == NULL_RTX)
4954	continue;
4955	if (maybe_lt (a: slot->width, b: total_size)
4956	|| maybe_lt (a: GET_MODE_SIZE (GET_MODE (slot->mem)), b: inherent_size))
4957	continue;
4958
4959	EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4960	FIRST_PSEUDO_REGISTER, i, bi)
4961	{
4962	another_allocno = ira_regno_allocno_map[i];
4963	if (allocnos_conflict_by_live_ranges_p (a1: allocno,
4964	a2: another_allocno))
4965	goto cont;
4966	}
4967	for (cost = 0, cp = ALLOCNO_COPIES (allocno);
4968	cp != NULL;
4969	cp = next_cp)
4970	{
4971	if (cp->first == allocno)
4972	{
4973	next_cp = cp->next_first_allocno_copy;
4974	another_allocno = cp->second;
4975	}
4976	else if (cp->second == allocno)
4977	{
4978	next_cp = cp->next_second_allocno_copy;
4979	another_allocno = cp->first;
4980	}
4981	else
4982	gcc_unreachable ();
4983	if (cp->insn == NULL_RTX)
4984	continue;
4985	if (bitmap_bit_p (&slot->spilled_regs,
4986	ALLOCNO_REGNO (another_allocno)))
4987	cost += cp->freq;
4988	}
4989	if (cost > best_cost)
4990	{
4991	best_cost = cost;
4992	best_slot_num = slot_num;
4993	}
4994	cont:
4995	;
4996	}
4997	if (best_cost >= 0)
4998	{
4999	slot_num = best_slot_num;
5000	slot = &ira_spilled_reg_stack_slots[slot_num];
5001	SET_REGNO_REG_SET (&slot->spilled_regs, regno);
5002	x = slot->mem;
5003	ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
5004	}
5005	}
5006	if (x != NULL_RTX)
5007	{
5008	ira_assert (known_ge (slot->width, total_size));
5009	#ifdef ENABLE_IRA_CHECKING
5010	EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
5011	FIRST_PSEUDO_REGISTER, i, bi)
5012	{
5013	ira_assert (! conflict_by_live_ranges_p (regno, i));
5014	}
5015	#endif
5016	SET_REGNO_REG_SET (&slot->spilled_regs, regno);
5017	if (internal_flag_ira_verbose > 3 && ira_dump_file)
5018	{
5019	fprintf (stream: ira_dump_file, format: " Assigning %d(freq=%d) slot %d of",
5020	regno, REG_FREQ (regno), slot_num);
5021	EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
5022	FIRST_PSEUDO_REGISTER, i, bi)
5023	{
5024	if ((unsigned) regno != i)
5025	fprintf (stream: ira_dump_file, format: " %d", i);
5026	}
5027	fprintf (stream: ira_dump_file, format: "\n");
5028	}
5029	}
5030	return x;
5031	}
5032
5033	/* This is called by reload every time a new stack slot X with
5034	TOTAL_SIZE was allocated for REGNO. We store this info for
5035	subsequent ira_reuse_stack_slot calls. */
5036	void
5037	ira_mark_new_stack_slot (rtx x, int regno, poly_uint64 total_size)
5038	{
5039	class ira_spilled_reg_stack_slot *slot;
5040	int slot_num;
5041	ira_allocno_t allocno;
5042
5043	ira_assert (! ira_use_lra_p);
5044
5045	ira_assert (known_le (PSEUDO_REGNO_BYTES (regno), total_size));
5046	allocno = ira_regno_allocno_map[regno];
5047	slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
5048	if (slot_num == -1)
5049	{
5050	slot_num = ira_spilled_reg_stack_slots_num++;
5051	ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
5052	}
5053	slot = &ira_spilled_reg_stack_slots[slot_num];
5054	INIT_REG_SET (&slot->spilled_regs);
5055	SET_REGNO_REG_SET (&slot->spilled_regs, regno);
5056	slot->mem = x;
5057	slot->width = total_size;
5058	if (internal_flag_ira_verbose > 3 && ira_dump_file)
5059	fprintf (stream: ira_dump_file, format: " Assigning %d(freq=%d) a new slot %d\n",
5060	regno, REG_FREQ (regno), slot_num);
5061	}
5062
5063
5064	/* Return spill cost for pseudo-registers whose numbers are in array
5065	REGNOS (with a negative number as an end marker) for reload with
5066	given IN and OUT for INSN. Return also number points (through
5067	EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
5068	the register pressure is high, number of references of the
5069	pseudo-registers (through NREFS), the number of psuedo registers
5070	whose allocated register wouldn't need saving in the prologue
5071	(through CALL_USED_COUNT), and the first hard regno occupied by the
5072	pseudo-registers (through FIRST_HARD_REGNO). */
5073	static int
5074	calculate_spill_cost (int *regnos, rtx in, rtx out, rtx_insn *insn,
5075	int *excess_pressure_live_length,
5076	int *nrefs, int *call_used_count, int *first_hard_regno)
5077	{
5078	int i, cost, regno, hard_regno, count, saved_cost;
5079	bool in_p, out_p;
5080	int length;
5081	ira_allocno_t a;
5082
5083	*nrefs = 0;
5084	for (length = count = cost = i = 0;; i++)
5085	{
5086	regno = regnos[i];
5087	if (regno < 0)
5088	break;
5089	*nrefs += REG_N_REFS (regno);
5090	hard_regno = reg_renumber[regno];
5091	ira_assert (hard_regno >= 0);
5092	a = ira_regno_allocno_map[regno];
5093	length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) / ALLOCNO_NUM_OBJECTS (a);
5094	cost += ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a);
5095	if (in_hard_reg_set_p (crtl->abi->full_reg_clobbers (),
5096	ALLOCNO_MODE (a), regno: hard_regno))
5097	count++;
5098	in_p = in && REG_P (in) && (int) REGNO (in) == hard_regno;
5099	out_p = out && REG_P (out) && (int) REGNO (out) == hard_regno;
5100	if ((in_p || out_p)
5101	&& find_regno_note (insn, REG_DEAD, hard_regno) != NULL_RTX)
5102	{
5103	saved_cost = 0;
5104	if (in_p)
5105	saved_cost += ira_memory_move_cost
5106	[ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)][1];
5107	if (out_p)
5108	saved_cost
5109	+= ira_memory_move_cost
5110	[ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)][0];
5111	cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)) * saved_cost;
5112	}
5113	}
5114	*excess_pressure_live_length = length;
5115	*call_used_count = count;
5116	hard_regno = -1;
5117	if (regnos[0] >= 0)
5118	{
5119	hard_regno = reg_renumber[regnos[0]];
5120	}
5121	*first_hard_regno = hard_regno;
5122	return cost;
5123	}
5124
5125	/* Return TRUE if spilling pseudo-registers whose numbers are in array
5126	REGNOS is better than spilling pseudo-registers with numbers in
5127	OTHER_REGNOS for reload with given IN and OUT for INSN. The
5128	function used by the reload pass to make better register spilling
5129	decisions. */
5130	bool
5131	ira_better_spill_reload_regno_p (int *regnos, int *other_regnos,
5132	rtx in, rtx out, rtx_insn *insn)
5133	{
5134	int cost, other_cost;
5135	int length, other_length;
5136	int nrefs, other_nrefs;
5137	int call_used_count, other_call_used_count;
5138	int hard_regno, other_hard_regno;
5139
5140	cost = calculate_spill_cost (regnos, in, out, insn,
5141	excess_pressure_live_length: &length, nrefs: &nrefs, call_used_count: &call_used_count, first_hard_regno: &hard_regno);
5142	other_cost = calculate_spill_cost (regnos: other_regnos, in, out, insn,
5143	excess_pressure_live_length: &other_length, nrefs: &other_nrefs,
5144	call_used_count: &other_call_used_count,
5145	first_hard_regno: &other_hard_regno);
5146	if (nrefs == 0 && other_nrefs != 0)
5147	return true;
5148	if (nrefs != 0 && other_nrefs == 0)
5149	return false;
5150	if (cost != other_cost)
5151	return cost < other_cost;
5152	if (length != other_length)
5153	return length > other_length;
5154	#ifdef REG_ALLOC_ORDER
5155	if (hard_regno >= 0 && other_hard_regno >= 0)
5156	return (inv_reg_alloc_order[hard_regno]
5157	< inv_reg_alloc_order[other_hard_regno]);
5158	#else
5159	if (call_used_count != other_call_used_count)
5160	return call_used_count > other_call_used_count;
5161	#endif
5162	return false;
5163	}
5164
5165
5166
5167	/* Allocate and initialize data necessary for assign_hard_reg. */
5168	void
5169	ira_initiate_assign (void)
5170	{
5171	sorted_allocnos
5172	= (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
5173	* ira_allocnos_num);
5174	consideration_allocno_bitmap = ira_allocate_bitmap ();
5175	initiate_cost_update ();
5176	allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
5177	sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num
5178	* sizeof (ira_copy_t));
5179	}
5180
5181	/* Deallocate data used by assign_hard_reg. */
5182	void
5183	ira_finish_assign (void)
5184	{
5185	ira_free (addr: sorted_allocnos);
5186	ira_free_bitmap (consideration_allocno_bitmap);
5187	finish_cost_update ();
5188	ira_free (addr: allocno_priorities);
5189	ira_free (addr: sorted_copies);
5190	}
5191
5192
5193
5194	/* Entry function doing color-based register allocation. */
5195	static void
5196	color (void)
5197	{
5198	allocno_stack_vec.create (nelems: ira_allocnos_num);
5199	memset (s: allocated_hardreg_p, c: 0, n: sizeof (allocated_hardreg_p));
5200	ira_initiate_assign ();
5201	do_coloring ();
5202	ira_finish_assign ();
5203	allocno_stack_vec.release ();
5204	move_spill_restore ();
5205	}
5206
5207
5208
5209	/* This page contains a simple register allocator without usage of
5210	allocno conflicts. This is used for fast allocation for -O0. */
5211
5212	/* Do register allocation by not using allocno conflicts. It uses
5213	only allocno live ranges. The algorithm is close to Chow's
5214	priority coloring. */
5215	static void
5216	fast_allocation (void)
5217	{
5218	int i, j, k, num, class_size, hard_regno, best_hard_regno, cost, min_cost;
5219	int *costs;
5220	#ifdef STACK_REGS
5221	bool no_stack_reg_p;
5222	#endif
5223	enum reg_class aclass;
5224	machine_mode mode;
5225	ira_allocno_t a;
5226	ira_allocno_iterator ai;
5227	live_range_t r;
5228	HARD_REG_SET conflict_hard_regs, *used_hard_regs;
5229
5230	sorted_allocnos = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
5231	* ira_allocnos_num);
5232	num = 0;
5233	FOR_EACH_ALLOCNO (a, ai)
5234	sorted_allocnos[num++] = a;
5235	allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
5236	setup_allocno_priorities (consideration_allocnos: sorted_allocnos, n: num);
5237	used_hard_regs = (HARD_REG_SET *) ira_allocate (sizeof (HARD_REG_SET)
5238	* ira_max_point);
5239	for (i = 0; i < ira_max_point; i++)
5240	CLEAR_HARD_REG_SET (set&: used_hard_regs[i]);
5241	qsort (sorted_allocnos, num, sizeof (ira_allocno_t),
5242	allocno_priority_compare_func);
5243	for (i = 0; i < num; i++)
5244	{
5245	int nr, l;
5246
5247	a = sorted_allocnos[i];
5248	nr = ALLOCNO_NUM_OBJECTS (a);
5249	CLEAR_HARD_REG_SET (set&: conflict_hard_regs);
5250	for (l = 0; l < nr; l++)
5251	{
5252	ira_object_t obj = ALLOCNO_OBJECT (a, l);
5253	conflict_hard_regs |= OBJECT_CONFLICT_HARD_REGS (obj);
5254	for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
5255	for (j = r->start; j <= r->finish; j++)
5256	conflict_hard_regs |= used_hard_regs[j];
5257	}
5258	aclass = ALLOCNO_CLASS (a);
5259	ALLOCNO_ASSIGNED_P (a) = true;
5260	ALLOCNO_HARD_REGNO (a) = -1;
5261	if (hard_reg_set_subset_p (reg_class_contents[aclass],
5262	y: conflict_hard_regs))
5263	continue;
5264	mode = ALLOCNO_MODE (a);
5265	#ifdef STACK_REGS
5266	no_stack_reg_p = ALLOCNO_NO_STACK_REG_P (a);
5267	#endif
5268	class_size = ira_class_hard_regs_num[aclass];
5269	costs = ALLOCNO_HARD_REG_COSTS (a);
5270	min_cost = INT_MAX;
5271	best_hard_regno = -1;
5272	for (j = 0; j < class_size; j++)
5273	{
5274	hard_regno = ira_class_hard_regs[aclass][j];
5275	#ifdef STACK_REGS
5276	if (no_stack_reg_p && FIRST_STACK_REG <= hard_regno
5277	&& hard_regno <= LAST_STACK_REG)
5278	continue;
5279	#endif
5280	if (ira_hard_reg_set_intersection_p (hard_regno, mode, hard_regset: conflict_hard_regs)
5281	|| (TEST_HARD_REG_BIT
5282	(ira_prohibited_class_mode_regs[aclass][mode], bit: hard_regno)))
5283	continue;
5284	if (NUM_REGISTER_FILTERS
5285	&& !test_register_filters (ALLOCNO_REGISTER_FILTERS (a),
5286	hard_regno))
5287	continue;
5288	if (costs == NULL)
5289	{
5290	best_hard_regno = hard_regno;
5291	break;
5292	}
5293	cost = costs[j];
5294	if (min_cost > cost)
5295	{
5296	min_cost = cost;
5297	best_hard_regno = hard_regno;
5298	}
5299	}
5300	if (best_hard_regno < 0)
5301	continue;
5302	ALLOCNO_HARD_REGNO (a) = hard_regno = best_hard_regno;
5303	for (l = 0; l < nr; l++)
5304	{
5305	ira_object_t obj = ALLOCNO_OBJECT (a, l);
5306	for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
5307	for (k = r->start; k <= r->finish; k++)
5308	used_hard_regs[k] |= ira_reg_mode_hard_regset[hard_regno][mode];
5309	}
5310	}
5311	ira_free (addr: sorted_allocnos);
5312	ira_free (addr: used_hard_regs);
5313	ira_free (addr: allocno_priorities);
5314	if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
5315	ira_print_disposition (ira_dump_file);
5316	}
5317
5318
5319
5320	/* Entry function doing coloring. */
5321	void
5322	ira_color (void)
5323	{
5324	ira_allocno_t a;
5325	ira_allocno_iterator ai;
5326
5327	/* Setup updated costs. */
5328	FOR_EACH_ALLOCNO (a, ai)
5329	{
5330	ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
5331	ALLOCNO_UPDATED_CLASS_COST (a) = ALLOCNO_CLASS_COST (a);
5332	}
5333	if (ira_conflicts_p)
5334	color ();
5335	else
5336	fast_allocation ();
5337	}
5338