1	/* IRA allocation based on graph coloring.
2	Copyright (C) 2006-2023 Free Software Foundation, Inc.
3	Contributed by Vladimir Makarov <vmakarov@redhat.com>.
4
5	This file is part of GCC.
6
7	GCC is free software; you can redistribute it and/or modify it under
8	the terms of the GNU General Public License as published by the Free
9	Software Foundation; either version 3, or (at your option) any later
10	version.
11
12	GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13	WARRANTY; without even the implied warranty of MERCHANTABILITY or
14	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15	for more details.
16
17	You should have received a copy of the GNU General Public License
18	along with GCC; see the file COPYING3. If not see
19	<http://www.gnu.org/licenses/>. */
20
21	#include "config.h"
22	#include "system.h"
23	#include "coretypes.h"
24	#include "backend.h"
25	#include "target.h"
26	#include "rtl.h"
27	#include "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	cost = costs[i];
2167	full_cost = full_costs[i];
2168	if (!HONOR_REG_ALLOC_ORDER)
2169	{
2170	if ((saved_nregs = calculate_saved_nregs (hard_regno, mode)) != 0)
2171	/* We need to save/restore the hard register in
2172	epilogue/prologue. Therefore we increase the cost. */
2173	{
2174	rclass = REGNO_REG_CLASS (hard_regno);
2175	add_cost = ((ira_memory_move_cost[mode][rclass][0]
2176	+ ira_memory_move_cost[mode][rclass][1])
2177	* saved_nregs / hard_regno_nregs (regno: hard_regno,
2178	mode) - 1);
2179	cost += add_cost;
2180	full_cost += add_cost;
2181	}
2182	}
2183	if (min_cost > cost)
2184	min_cost = cost;
2185	if (min_full_cost > full_cost)
2186	{
2187	min_full_cost = full_cost;
2188	best_hard_regno = hard_regno;
2189	ira_assert (hard_regno >= 0);
2190	}
2191	if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL)
2192	fprintf (stream: ira_dump_file, format: "(%d=%d,%d) ", hard_regno, cost, full_cost);
2193	}
2194	if (internal_flag_ira_verbose > 5 && ira_dump_file != NULL)
2195	fprintf (stream: ira_dump_file, format: "\n");
2196	if (min_full_cost > mem_cost
2197	/* Do not spill static chain pointer pseudo when non-local goto
2198	is used. */
2199	&& ! non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a)))
2200	{
2201	if (! retry_p && internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2202	fprintf (stream: ira_dump_file, format: "(memory is more profitable %d vs %d) ",
2203	mem_cost, min_full_cost);
2204	best_hard_regno = -1;
2205	}
2206	fail:
2207	if (best_hard_regno >= 0)
2208	{
2209	for (i = hard_regno_nregs (regno: best_hard_regno, mode) - 1; i >= 0; i--)
2210	allocated_hardreg_p[best_hard_regno + i] = true;
2211	spill_soft_conflicts (a, allocnos_to_spill, soft_conflict_regs,
2212	hregno: best_hard_regno);
2213	}
2214	if (! retry_p)
2215	restore_costs_from_copies (allocno: a);
2216	ALLOCNO_HARD_REGNO (a) = best_hard_regno;
2217	ALLOCNO_ASSIGNED_P (a) = true;
2218	if (best_hard_regno >= 0 && !retry_p)
2219	update_costs_from_copies (allocno: a, decr_p: true, record_p: true);
2220	ira_assert (ALLOCNO_CLASS (a) == aclass);
2221	/* We don't need updated costs anymore. */
2222	ira_free_allocno_updated_costs (a);
2223	return best_hard_regno >= 0;
2224	}
2225
2226
2227
2228	/* An array used to sort copies. */
2229	static ira_copy_t *sorted_copies;
2230
2231	/* If allocno A is a cap, return non-cap allocno from which A is
2232	created. Otherwise, return A. */
2233	static ira_allocno_t
2234	get_cap_member (ira_allocno_t a)
2235	{
2236	ira_allocno_t member;
2237
2238	while ((member = ALLOCNO_CAP_MEMBER (a)) != NULL)
2239	a = member;
2240	return a;
2241	}
2242
2243	/* Return TRUE if live ranges of allocnos A1 and A2 intersect. It is
2244	used to find a conflict for new allocnos or allocnos with the
2245	different allocno classes. */
2246	static bool
2247	allocnos_conflict_by_live_ranges_p (ira_allocno_t a1, ira_allocno_t a2)
2248	{
2249	rtx reg1, reg2;
2250	int i, j;
2251	int n1 = ALLOCNO_NUM_OBJECTS (a1);
2252	int n2 = ALLOCNO_NUM_OBJECTS (a2);
2253
2254	if (a1 == a2)
2255	return false;
2256	reg1 = regno_reg_rtx[ALLOCNO_REGNO (a1)];
2257	reg2 = regno_reg_rtx[ALLOCNO_REGNO (a2)];
2258	if (reg1 != NULL && reg2 != NULL
2259	&& ORIGINAL_REGNO (reg1) == ORIGINAL_REGNO (reg2))
2260	return false;
2261
2262	/* We don't keep live ranges for caps because they can be quite big.
2263	Use ranges of non-cap allocno from which caps are created. */
2264	a1 = get_cap_member (a: a1);
2265	a2 = get_cap_member (a: a2);
2266	for (i = 0; i < n1; i++)
2267	{
2268	ira_object_t c1 = ALLOCNO_OBJECT (a1, i);
2269
2270	for (j = 0; j < n2; j++)
2271	{
2272	ira_object_t c2 = ALLOCNO_OBJECT (a2, j);
2273
2274	if (ira_live_ranges_intersect_p (OBJECT_LIVE_RANGES (c1),
2275	OBJECT_LIVE_RANGES (c2)))
2276	return true;
2277	}
2278	}
2279	return false;
2280	}
2281
2282	/* The function is used to sort copies according to their execution
2283	frequencies. */
2284	static int
2285	copy_freq_compare_func (const void *v1p, const void *v2p)
2286	{
2287	ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p;
2288	int pri1, pri2;
2289
2290	pri1 = cp1->freq;
2291	pri2 = cp2->freq;
2292	if (pri2 - pri1)
2293	return pri2 - pri1;
2294
2295	/* If frequencies are equal, sort by copies, so that the results of
2296	qsort leave nothing to chance. */
2297	return cp1->num - cp2->num;
2298	}
2299
2300
2301
2302	/* Return true if any allocno from thread of A1 conflicts with any
2303	allocno from thread A2. */
2304	static bool
2305	allocno_thread_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
2306	{
2307	ira_allocno_t a, conflict_a;
2308
2309	for (a = ALLOCNO_COLOR_DATA (a2)->next_thread_allocno;;
2310	a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
2311	{
2312	for (conflict_a = ALLOCNO_COLOR_DATA (a1)->next_thread_allocno;;
2313	conflict_a = ALLOCNO_COLOR_DATA (conflict_a)->next_thread_allocno)
2314	{
2315	if (allocnos_conflict_by_live_ranges_p (a1: a, a2: conflict_a))
2316	return true;
2317	if (conflict_a == a1)
2318	break;
2319	}
2320	if (a == a2)
2321	break;
2322	}
2323	return false;
2324	}
2325
2326	/* Merge two threads given correspondingly by their first allocnos T1
2327	and T2 (more accurately merging T2 into T1). */
2328	static void
2329	merge_threads (ira_allocno_t t1, ira_allocno_t t2)
2330	{
2331	ira_allocno_t a, next, last;
2332
2333	gcc_assert (t1 != t2
2334	&& ALLOCNO_COLOR_DATA (t1)->first_thread_allocno == t1
2335	&& ALLOCNO_COLOR_DATA (t2)->first_thread_allocno == t2);
2336	for (last = t2, a = ALLOCNO_COLOR_DATA (t2)->next_thread_allocno;;
2337	a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
2338	{
2339	ALLOCNO_COLOR_DATA (a)->first_thread_allocno = t1;
2340	if (a == t2)
2341	break;
2342	last = a;
2343	}
2344	next = ALLOCNO_COLOR_DATA (t1)->next_thread_allocno;
2345	ALLOCNO_COLOR_DATA (t1)->next_thread_allocno = t2;
2346	ALLOCNO_COLOR_DATA (last)->next_thread_allocno = next;
2347	ALLOCNO_COLOR_DATA (t1)->thread_freq += ALLOCNO_COLOR_DATA (t2)->thread_freq;
2348	}
2349
2350	/* Create threads by processing CP_NUM copies from sorted copies. We
2351	process the most expensive copies first. */
2352	static void
2353	form_threads_from_copies (int cp_num)
2354	{
2355	ira_allocno_t a, thread1, thread2;
2356	ira_copy_t cp;
2357
2358	qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
2359	/* Form threads processing copies, most frequently executed
2360	first. */
2361	for (int i = 0; i < cp_num; i++)
2362	{
2363	cp = sorted_copies[i];
2364	thread1 = ALLOCNO_COLOR_DATA (cp->first)->first_thread_allocno;
2365	thread2 = ALLOCNO_COLOR_DATA (cp->second)->first_thread_allocno;
2366	if (thread1 == thread2)
2367	continue;
2368	if (! allocno_thread_conflict_p (a1: thread1, a2: thread2))
2369	{
2370	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2371	fprintf
2372	(stream: ira_dump_file,
2373	format: " Forming thread by copy %d:a%dr%d-a%dr%d (freq=%d):\n",
2374	cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
2375	ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
2376	cp->freq);
2377	merge_threads (t1: thread1, t2: thread2);
2378	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2379	{
2380	thread1 = ALLOCNO_COLOR_DATA (thread1)->first_thread_allocno;
2381	fprintf (stream: ira_dump_file, format: " Result (freq=%d): a%dr%d(%d)",
2382	ALLOCNO_COLOR_DATA (thread1)->thread_freq,
2383	ALLOCNO_NUM (thread1), ALLOCNO_REGNO (thread1),
2384	ALLOCNO_FREQ (thread1));
2385	for (a = ALLOCNO_COLOR_DATA (thread1)->next_thread_allocno;
2386	a != thread1;
2387	a = ALLOCNO_COLOR_DATA (a)->next_thread_allocno)
2388	fprintf (stream: ira_dump_file, format: " a%dr%d(%d)",
2389	ALLOCNO_NUM (a), ALLOCNO_REGNO (a),
2390	ALLOCNO_FREQ (a));
2391	fprintf (stream: ira_dump_file, format: "\n");
2392	}
2393	}
2394	}
2395	}
2396
2397	/* Create threads by processing copies of all alocnos from BUCKET. We
2398	process the most expensive copies first. */
2399	static void
2400	form_threads_from_bucket (ira_allocno_t bucket)
2401	{
2402	ira_allocno_t a;
2403	ira_copy_t cp, next_cp;
2404	int cp_num = 0;
2405
2406	for (a = bucket; a != NULL; a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2407	{
2408	for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2409	{
2410	if (cp->first == a)
2411	{
2412	next_cp = cp->next_first_allocno_copy;
2413	sorted_copies[cp_num++] = cp;
2414	}
2415	else if (cp->second == a)
2416	next_cp = cp->next_second_allocno_copy;
2417	else
2418	gcc_unreachable ();
2419	}
2420	}
2421	form_threads_from_copies (cp_num);
2422	}
2423
2424	/* Create threads by processing copies of colorable allocno A. We
2425	process most expensive copies first. */
2426	static void
2427	form_threads_from_colorable_allocno (ira_allocno_t a)
2428	{
2429	ira_allocno_t another_a;
2430	ira_copy_t cp, next_cp;
2431	int cp_num = 0;
2432
2433	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2434	fprintf (stream: ira_dump_file, format: " Forming thread from allocno a%dr%d:\n",
2435	ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2436	for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2437	{
2438	if (cp->first == a)
2439	{
2440	next_cp = cp->next_first_allocno_copy;
2441	another_a = cp->second;
2442	}
2443	else if (cp->second == a)
2444	{
2445	next_cp = cp->next_second_allocno_copy;
2446	another_a = cp->first;
2447	}
2448	else
2449	gcc_unreachable ();
2450	if ((! ALLOCNO_COLOR_DATA (another_a)->in_graph_p
2451	&& !ALLOCNO_COLOR_DATA (another_a)->may_be_spilled_p)
2452	|| ALLOCNO_COLOR_DATA (another_a)->colorable_p)
2453	sorted_copies[cp_num++] = cp;
2454	}
2455	form_threads_from_copies (cp_num);
2456	}
2457
2458	/* Form initial threads which contain only one allocno. */
2459	static void
2460	init_allocno_threads (void)
2461	{
2462	ira_allocno_t a;
2463	unsigned int j;
2464	bitmap_iterator bi;
2465	ira_pref_t pref;
2466
2467	EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
2468	{
2469	a = ira_allocnos[j];
2470	/* Set up initial thread data: */
2471	ALLOCNO_COLOR_DATA (a)->first_thread_allocno
2472	= ALLOCNO_COLOR_DATA (a)->next_thread_allocno = a;
2473	ALLOCNO_COLOR_DATA (a)->thread_freq = ALLOCNO_FREQ (a);
2474	ALLOCNO_COLOR_DATA (a)->hard_reg_prefs = 0;
2475	for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref)
2476	ALLOCNO_COLOR_DATA (a)->hard_reg_prefs += pref->freq;
2477	}
2478	}
2479
2480
2481
2482	/* This page contains the allocator based on the Chaitin-Briggs algorithm. */
2483
2484	/* Bucket of allocnos that can colored currently without spilling. */
2485	static ira_allocno_t colorable_allocno_bucket;
2486
2487	/* Bucket of allocnos that might be not colored currently without
2488	spilling. */
2489	static ira_allocno_t uncolorable_allocno_bucket;
2490
2491	/* The current number of allocnos in the uncolorable_bucket. */
2492	static int uncolorable_allocnos_num;
2493
2494	/* Return the current spill priority of allocno A. The less the
2495	number, the more preferable the allocno for spilling. */
2496	static inline int
2497	allocno_spill_priority (ira_allocno_t a)
2498	{
2499	allocno_color_data_t data = ALLOCNO_COLOR_DATA (a);
2500
2501	return (data->temp
2502	/ (ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a)
2503	* ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)]
2504	+ 1));
2505	}
2506
2507	/* Add allocno A to bucket *BUCKET_PTR. A should be not in a bucket
2508	before the call. */
2509	static void
2510	add_allocno_to_bucket (ira_allocno_t a, ira_allocno_t *bucket_ptr)
2511	{
2512	ira_allocno_t first_a;
2513	allocno_color_data_t data;
2514
2515	if (bucket_ptr == &uncolorable_allocno_bucket
2516	&& ALLOCNO_CLASS (a) != NO_REGS)
2517	{
2518	uncolorable_allocnos_num++;
2519	ira_assert (uncolorable_allocnos_num > 0);
2520	}
2521	first_a = *bucket_ptr;
2522	data = ALLOCNO_COLOR_DATA (a);
2523	data->next_bucket_allocno = first_a;
2524	data->prev_bucket_allocno = NULL;
2525	if (first_a != NULL)
2526	ALLOCNO_COLOR_DATA (first_a)->prev_bucket_allocno = a;
2527	*bucket_ptr = a;
2528	}
2529
2530	/* Compare two allocnos to define which allocno should be pushed first
2531	into the coloring stack. If the return is a negative number, the
2532	allocno given by the first parameter will be pushed first. In this
2533	case such allocno has less priority than the second one and the
2534	hard register will be assigned to it after assignment to the second
2535	one. As the result of such assignment order, the second allocno
2536	has a better chance to get the best hard register. */
2537	static int
2538	bucket_allocno_compare_func (const void *v1p, const void *v2p)
2539	{
2540	ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2541	ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2542	int diff, freq1, freq2, a1_num, a2_num, pref1, pref2;
2543	ira_allocno_t t1 = ALLOCNO_COLOR_DATA (a1)->first_thread_allocno;
2544	ira_allocno_t t2 = ALLOCNO_COLOR_DATA (a2)->first_thread_allocno;
2545	int cl1 = ALLOCNO_CLASS (a1), cl2 = ALLOCNO_CLASS (a2);
2546
2547	freq1 = ALLOCNO_COLOR_DATA (t1)->thread_freq;
2548	freq2 = ALLOCNO_COLOR_DATA (t2)->thread_freq;
2549	if ((diff = freq1 - freq2) != 0)
2550	return diff;
2551
2552	if ((diff = ALLOCNO_NUM (t2) - ALLOCNO_NUM (t1)) != 0)
2553	return diff;
2554
2555	/* Push pseudos requiring less hard registers first. It means that
2556	we will assign pseudos requiring more hard registers first
2557	avoiding creation small holes in free hard register file into
2558	which the pseudos requiring more hard registers cannot fit. */
2559	if ((diff = (ira_reg_class_max_nregs[cl1][ALLOCNO_MODE (a1)]
2560	- ira_reg_class_max_nregs[cl2][ALLOCNO_MODE (a2)])) != 0)
2561	return diff;
2562
2563	freq1 = ALLOCNO_FREQ (a1);
2564	freq2 = ALLOCNO_FREQ (a2);
2565	if ((diff = freq1 - freq2) != 0)
2566	return diff;
2567
2568	a1_num = ALLOCNO_COLOR_DATA (a1)->available_regs_num;
2569	a2_num = ALLOCNO_COLOR_DATA (a2)->available_regs_num;
2570	if ((diff = a2_num - a1_num) != 0)
2571	return diff;
2572	/* Push allocnos with minimal conflict_allocno_hard_prefs first. */
2573	pref1 = ALLOCNO_COLOR_DATA (a1)->conflict_allocno_hard_prefs;
2574	pref2 = ALLOCNO_COLOR_DATA (a2)->conflict_allocno_hard_prefs;
2575	if ((diff = pref1 - pref2) != 0)
2576	return diff;
2577	return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
2578	}
2579
2580	/* Sort bucket *BUCKET_PTR and return the result through
2581	BUCKET_PTR. */
2582	static void
2583	sort_bucket (ira_allocno_t *bucket_ptr,
2584	int (*compare_func) (const void *, const void *))
2585	{
2586	ira_allocno_t a, head;
2587	int n;
2588
2589	for (n = 0, a = *bucket_ptr;
2590	a != NULL;
2591	a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2592	sorted_allocnos[n++] = a;
2593	if (n <= 1)
2594	return;
2595	qsort (sorted_allocnos, n, sizeof (ira_allocno_t), compare_func);
2596	head = NULL;
2597	for (n--; n >= 0; n--)
2598	{
2599	a = sorted_allocnos[n];
2600	ALLOCNO_COLOR_DATA (a)->next_bucket_allocno = head;
2601	ALLOCNO_COLOR_DATA (a)->prev_bucket_allocno = NULL;
2602	if (head != NULL)
2603	ALLOCNO_COLOR_DATA (head)->prev_bucket_allocno = a;
2604	head = a;
2605	}
2606	*bucket_ptr = head;
2607	}
2608
2609	/* Add ALLOCNO to colorable bucket maintaining the order according
2610	their priority. ALLOCNO should be not in a bucket before the
2611	call. */
2612	static void
2613	add_allocno_to_ordered_colorable_bucket (ira_allocno_t allocno)
2614	{
2615	ira_allocno_t before, after;
2616
2617	form_threads_from_colorable_allocno (a: allocno);
2618	for (before = colorable_allocno_bucket, after = NULL;
2619	before != NULL;
2620	after = before,
2621	before = ALLOCNO_COLOR_DATA (before)->next_bucket_allocno)
2622	if (bucket_allocno_compare_func (v1p: &allocno, v2p: &before) < 0)
2623	break;
2624	ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno = before;
2625	ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno = after;
2626	if (after == NULL)
2627	colorable_allocno_bucket = allocno;
2628	else
2629	ALLOCNO_COLOR_DATA (after)->next_bucket_allocno = allocno;
2630	if (before != NULL)
2631	ALLOCNO_COLOR_DATA (before)->prev_bucket_allocno = allocno;
2632	}
2633
2634	/* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
2635	the call. */
2636	static void
2637	delete_allocno_from_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
2638	{
2639	ira_allocno_t prev_allocno, next_allocno;
2640
2641	if (bucket_ptr == &uncolorable_allocno_bucket
2642	&& ALLOCNO_CLASS (allocno) != NO_REGS)
2643	{
2644	uncolorable_allocnos_num--;
2645	ira_assert (uncolorable_allocnos_num >= 0);
2646	}
2647	prev_allocno = ALLOCNO_COLOR_DATA (allocno)->prev_bucket_allocno;
2648	next_allocno = ALLOCNO_COLOR_DATA (allocno)->next_bucket_allocno;
2649	if (prev_allocno != NULL)
2650	ALLOCNO_COLOR_DATA (prev_allocno)->next_bucket_allocno = next_allocno;
2651	else
2652	{
2653	ira_assert (*bucket_ptr == allocno);
2654	*bucket_ptr = next_allocno;
2655	}
2656	if (next_allocno != NULL)
2657	ALLOCNO_COLOR_DATA (next_allocno)->prev_bucket_allocno = prev_allocno;
2658	}
2659
2660	/* Put allocno A onto the coloring stack without removing it from its
2661	bucket. Pushing allocno to the coloring stack can result in moving
2662	conflicting allocnos from the uncolorable bucket to the colorable
2663	one. Update conflict_allocno_hard_prefs of the conflicting
2664	allocnos which are not on stack yet. */
2665	static void
2666	push_allocno_to_stack (ira_allocno_t a)
2667	{
2668	enum reg_class aclass;
2669	allocno_color_data_t data, conflict_data;
2670	int size, i, n = ALLOCNO_NUM_OBJECTS (a);
2671
2672	data = ALLOCNO_COLOR_DATA (a);
2673	data->in_graph_p = false;
2674	allocno_stack_vec.safe_push (obj: a);
2675	aclass = ALLOCNO_CLASS (a);
2676	if (aclass == NO_REGS)
2677	return;
2678	size = ira_reg_class_max_nregs[aclass][ALLOCNO_MODE (a)];
2679	if (n > 1)
2680	{
2681	/* We will deal with the subwords individually. */
2682	gcc_assert (size == ALLOCNO_NUM_OBJECTS (a));
2683	size = 1;
2684	}
2685	for (i = 0; i < n; i++)
2686	{
2687	ira_object_t obj = ALLOCNO_OBJECT (a, i);
2688	ira_object_t conflict_obj;
2689	ira_object_conflict_iterator oci;
2690
2691	FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2692	{
2693	ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2694	ira_pref_t pref;
2695
2696	conflict_data = ALLOCNO_COLOR_DATA (conflict_a);
2697	if (! conflict_data->in_graph_p
2698	|| ALLOCNO_ASSIGNED_P (conflict_a)
2699	|| !(hard_reg_set_intersect_p
2700	(ALLOCNO_COLOR_DATA (a)->profitable_hard_regs,
2701	y: conflict_data->profitable_hard_regs)))
2702	continue;
2703	for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref)
2704	conflict_data->conflict_allocno_hard_prefs -= pref->freq;
2705	if (conflict_data->colorable_p)
2706	continue;
2707	ira_assert (bitmap_bit_p (coloring_allocno_bitmap,
2708	ALLOCNO_NUM (conflict_a)));
2709	if (update_left_conflict_sizes_p (a: conflict_a, removed_a: a, size))
2710	{
2711	delete_allocno_from_bucket
2712	(allocno: conflict_a, bucket_ptr: &uncolorable_allocno_bucket);
2713	add_allocno_to_ordered_colorable_bucket (allocno: conflict_a);
2714	if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2715	{
2716	fprintf (stream: ira_dump_file, format: " Making");
2717	ira_print_expanded_allocno (conflict_a);
2718	fprintf (stream: ira_dump_file, format: " colorable\n");
2719	}
2720	}
2721
2722	}
2723	}
2724	}
2725
2726	/* Put ALLOCNO onto the coloring stack and remove it from its bucket.
2727	The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
2728	static void
2729	remove_allocno_from_bucket_and_push (ira_allocno_t allocno, bool colorable_p)
2730	{
2731	if (colorable_p)
2732	delete_allocno_from_bucket (allocno, bucket_ptr: &colorable_allocno_bucket);
2733	else
2734	delete_allocno_from_bucket (allocno, bucket_ptr: &uncolorable_allocno_bucket);
2735	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2736	{
2737	fprintf (stream: ira_dump_file, format: " Pushing");
2738	ira_print_expanded_allocno (allocno);
2739	if (colorable_p)
2740	fprintf (stream: ira_dump_file, format: "(cost %d)\n",
2741	ALLOCNO_COLOR_DATA (allocno)->temp);
2742	else
2743	fprintf (stream: ira_dump_file, format: "(potential spill: %spri=%d, cost=%d)\n",
2744	ALLOCNO_BAD_SPILL_P (allocno) ? "bad spill, " : "",
2745	allocno_spill_priority (a: allocno),
2746	ALLOCNO_COLOR_DATA (allocno)->temp);
2747	}
2748	if (! colorable_p)
2749	ALLOCNO_COLOR_DATA (allocno)->may_be_spilled_p = true;
2750	push_allocno_to_stack (a: allocno);
2751	}
2752
2753	/* Put all allocnos from colorable bucket onto the coloring stack. */
2754	static void
2755	push_only_colorable (void)
2756	{
2757	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2758	fprintf (stream: ira_dump_file, format: " Forming thread from colorable bucket:\n");
2759	form_threads_from_bucket (bucket: colorable_allocno_bucket);
2760	for (ira_allocno_t a = colorable_allocno_bucket;
2761	a != NULL;
2762	a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2763	update_costs_from_prefs (allocno: a);
2764	sort_bucket (bucket_ptr: &colorable_allocno_bucket, compare_func: bucket_allocno_compare_func);
2765	for (;colorable_allocno_bucket != NULL;)
2766	remove_allocno_from_bucket_and_push (allocno: colorable_allocno_bucket, colorable_p: true);
2767	}
2768
2769	/* Return the frequency of exit edges (if EXIT_P) or entry from/to the
2770	loop given by its LOOP_NODE. */
2771	int
2772	ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p)
2773	{
2774	int freq, i;
2775	edge_iterator ei;
2776	edge e;
2777
2778	ira_assert (current_loops != NULL && loop_node->loop != NULL
2779	&& (regno < 0 || regno >= FIRST_PSEUDO_REGISTER));
2780	freq = 0;
2781	if (! exit_p)
2782	{
2783	FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
2784	if (e->src != loop_node->loop->latch
2785	&& (regno < 0
2786	|| (bitmap_bit_p (df_get_live_out (bb: e->src), regno)
2787	&& bitmap_bit_p (df_get_live_in (bb: e->dest), regno))))
2788	freq += EDGE_FREQUENCY (e);
2789	}
2790	else
2791	{
2792	auto_vec<edge> edges = get_loop_exit_edges (loop_node->loop);
2793	FOR_EACH_VEC_ELT (edges, i, e)
2794	if (regno < 0
2795	|| (bitmap_bit_p (df_get_live_out (bb: e->src), regno)
2796	&& bitmap_bit_p (df_get_live_in (bb: e->dest), regno)))
2797	freq += EDGE_FREQUENCY (e);
2798	}
2799
2800	return REG_FREQ_FROM_EDGE_FREQ (freq);
2801	}
2802
2803	/* Construct an object that describes the boundary between A and its
2804	parent allocno. */
2805	ira_loop_border_costs::ira_loop_border_costs (ira_allocno_t a)
2806	: m_mode (ALLOCNO_MODE (a)),
2807	m_class (ALLOCNO_CLASS (a)),
2808	m_entry_freq (ira_loop_edge_freq (ALLOCNO_LOOP_TREE_NODE (a),
2809	ALLOCNO_REGNO (a), exit_p: false)),
2810	m_exit_freq (ira_loop_edge_freq (ALLOCNO_LOOP_TREE_NODE (a),
2811	ALLOCNO_REGNO (a), exit_p: true))
2812	{
2813	}
2814
2815	/* Calculate and return the cost of putting allocno A into memory. */
2816	static int
2817	calculate_allocno_spill_cost (ira_allocno_t a)
2818	{
2819	int regno, cost;
2820	ira_allocno_t parent_allocno;
2821	ira_loop_tree_node_t parent_node, loop_node;
2822
2823	regno = ALLOCNO_REGNO (a);
2824	cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_UPDATED_CLASS_COST (a);
2825	if (ALLOCNO_CAP (a) != NULL)
2826	return cost;
2827	loop_node = ALLOCNO_LOOP_TREE_NODE (a);
2828	if ((parent_node = loop_node->parent) == NULL)
2829	return cost;
2830	if ((parent_allocno = parent_node->regno_allocno_map[regno]) == NULL)
2831	return cost;
2832	ira_loop_border_costs border_costs (a);
2833	if (ALLOCNO_HARD_REGNO (parent_allocno) < 0)
2834	cost -= border_costs.spill_outside_loop_cost ();
2835	else
2836	cost += (border_costs.spill_inside_loop_cost ()
2837	- border_costs.move_between_loops_cost ());
2838	return cost;
2839	}
2840
2841	/* Used for sorting allocnos for spilling. */
2842	static inline int
2843	allocno_spill_priority_compare (ira_allocno_t a1, ira_allocno_t a2)
2844	{
2845	int pri1, pri2, diff;
2846
2847	/* Avoid spilling static chain pointer pseudo when non-local goto is
2848	used. */
2849	if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1)))
2850	return 1;
2851	else if (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2)))
2852	return -1;
2853	if (ALLOCNO_BAD_SPILL_P (a1) && ! ALLOCNO_BAD_SPILL_P (a2))
2854	return 1;
2855	if (ALLOCNO_BAD_SPILL_P (a2) && ! ALLOCNO_BAD_SPILL_P (a1))
2856	return -1;
2857	pri1 = allocno_spill_priority (a: a1);
2858	pri2 = allocno_spill_priority (a: a2);
2859	if ((diff = pri1 - pri2) != 0)
2860	return diff;
2861	if ((diff
2862	= ALLOCNO_COLOR_DATA (a1)->temp - ALLOCNO_COLOR_DATA (a2)->temp) != 0)
2863	return diff;
2864	return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2865	}
2866
2867	/* Used for sorting allocnos for spilling. */
2868	static int
2869	allocno_spill_sort_compare (const void *v1p, const void *v2p)
2870	{
2871	ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
2872	ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
2873
2874	return allocno_spill_priority_compare (a1: p1, a2: p2);
2875	}
2876
2877	/* Push allocnos to the coloring stack. The order of allocnos in the
2878	stack defines the order for the subsequent coloring. */
2879	static void
2880	push_allocnos_to_stack (void)
2881	{
2882	ira_allocno_t a;
2883	int cost;
2884
2885	/* Calculate uncolorable allocno spill costs. */
2886	for (a = uncolorable_allocno_bucket;
2887	a != NULL;
2888	a = ALLOCNO_COLOR_DATA (a)->next_bucket_allocno)
2889	if (ALLOCNO_CLASS (a) != NO_REGS)
2890	{
2891	cost = calculate_allocno_spill_cost (a);
2892	/* ??? Remove cost of copies between the coalesced
2893	allocnos. */
2894	ALLOCNO_COLOR_DATA (a)->temp = cost;
2895	}
2896	sort_bucket (bucket_ptr: &uncolorable_allocno_bucket, compare_func: allocno_spill_sort_compare);
2897	for (;;)
2898	{
2899	push_only_colorable ();
2900	a = uncolorable_allocno_bucket;
2901	if (a == NULL)
2902	break;
2903	remove_allocno_from_bucket_and_push (allocno: a, colorable_p: false);
2904	}
2905	ira_assert (colorable_allocno_bucket == NULL
2906	&& uncolorable_allocno_bucket == NULL);
2907	ira_assert (uncolorable_allocnos_num == 0);
2908	}
2909
2910	/* Pop the coloring stack and assign hard registers to the popped
2911	allocnos. */
2912	static void
2913	pop_allocnos_from_stack (void)
2914	{
2915	ira_allocno_t allocno;
2916	enum reg_class aclass;
2917
2918	for (;allocno_stack_vec.length () != 0;)
2919	{
2920	allocno = allocno_stack_vec.pop ();
2921	aclass = ALLOCNO_CLASS (allocno);
2922	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2923	{
2924	fprintf (stream: ira_dump_file, format: " Popping");
2925	ira_print_expanded_allocno (allocno);
2926	fprintf (stream: ira_dump_file, format: " -- ");
2927	}
2928	if (aclass == NO_REGS)
2929	{
2930	ALLOCNO_HARD_REGNO (allocno) = -1;
2931	ALLOCNO_ASSIGNED_P (allocno) = true;
2932	ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno) == NULL);
2933	ira_assert
2934	(ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno) == NULL);
2935	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2936	fprintf (stream: ira_dump_file, format: "assign memory\n");
2937	}
2938	else if (assign_hard_reg (a: allocno, retry_p: false))
2939	{
2940	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2941	fprintf (stream: ira_dump_file, format: " assign reg %d\n",
2942	ALLOCNO_HARD_REGNO (allocno));
2943	}
2944	else if (ALLOCNO_ASSIGNED_P (allocno))
2945	{
2946	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2947	fprintf (stream: ira_dump_file, format: "spill%s\n",
2948	ALLOCNO_COLOR_DATA (allocno)->may_be_spilled_p
2949	? "" : "!");
2950	}
2951	ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
2952	}
2953	}
2954
2955	/* Set up number of available hard registers for allocno A. */
2956	static void
2957	setup_allocno_available_regs_num (ira_allocno_t a)
2958	{
2959	int i, n, hard_regno, hard_regs_num, nwords;
2960	enum reg_class aclass;
2961	allocno_color_data_t data;
2962
2963	aclass = ALLOCNO_CLASS (a);
2964	data = ALLOCNO_COLOR_DATA (a);
2965	data->available_regs_num = 0;
2966	if (aclass == NO_REGS)
2967	return;
2968	hard_regs_num = ira_class_hard_regs_num[aclass];
2969	nwords = ALLOCNO_NUM_OBJECTS (a);
2970	for (n = 0, i = hard_regs_num - 1; i >= 0; i--)
2971	{
2972	hard_regno = ira_class_hard_regs[aclass][i];
2973	/* Checking only profitable hard regs. */
2974	if (TEST_HARD_REG_BIT (set: data->profitable_hard_regs, bit: hard_regno))
2975	n++;
2976	}
2977	data->available_regs_num = n;
2978	if (internal_flag_ira_verbose <= 2 || ira_dump_file == NULL)
2979	return;
2980	fprintf
2981	(stream: ira_dump_file,
2982	format: " Allocno a%dr%d of %s(%d) has %d avail. regs ",
2983	ALLOCNO_NUM (a), ALLOCNO_REGNO (a),
2984	reg_class_names[aclass], ira_class_hard_regs_num[aclass], n);
2985	print_hard_reg_set (f: ira_dump_file, set: data->profitable_hard_regs, new_line_p: false);
2986	fprintf (stream: ira_dump_file, format: ", %snode: ",
2987	data->profitable_hard_regs == data->hard_regs_node->hard_regs->set
2988	? "" : "^");
2989	print_hard_reg_set (f: ira_dump_file,
2990	set: data->hard_regs_node->hard_regs->set, new_line_p: false);
2991	for (i = 0; i < nwords; i++)
2992	{
2993	ira_object_t obj = ALLOCNO_OBJECT (a, i);
2994
2995	if (nwords != 1)
2996	{
2997	if (i != 0)
2998	fprintf (stream: ira_dump_file, format: ", ");
2999	fprintf (stream: ira_dump_file, format: " obj %d", i);
3000	}
3001	fprintf (stream: ira_dump_file, format: " (confl regs = ");
3002	print_hard_reg_set (f: ira_dump_file, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
3003	new_line_p: false);
3004	fprintf (stream: ira_dump_file, format: ")");
3005	}
3006	fprintf (stream: ira_dump_file, format: "\n");
3007	}
3008
3009	/* Put ALLOCNO in a bucket corresponding to its number and size of its
3010	conflicting allocnos and hard registers. */
3011	static void
3012	put_allocno_into_bucket (ira_allocno_t allocno)
3013	{
3014	ALLOCNO_COLOR_DATA (allocno)->in_graph_p = true;
3015	setup_allocno_available_regs_num (allocno);
3016	if (setup_left_conflict_sizes_p (allocno))
3017	add_allocno_to_bucket (a: allocno, bucket_ptr: &colorable_allocno_bucket);
3018	else
3019	add_allocno_to_bucket (a: allocno, bucket_ptr: &uncolorable_allocno_bucket);
3020	}
3021
3022	/* Map: allocno number -> allocno priority. */
3023	static int *allocno_priorities;
3024
3025	/* Set up priorities for N allocnos in array
3026	CONSIDERATION_ALLOCNOS. */
3027	static void
3028	setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
3029	{
3030	int i, length, nrefs, priority, max_priority, mult, diff;
3031	ira_allocno_t a;
3032
3033	max_priority = 0;
3034	for (i = 0; i < n; i++)
3035	{
3036	a = consideration_allocnos[i];
3037	nrefs = ALLOCNO_NREFS (a);
3038	ira_assert (nrefs >= 0);
3039	mult = floor_log2 (ALLOCNO_NREFS (a)) + 1;
3040	ira_assert (mult >= 0);
3041	mult *= ira_reg_class_max_nregs[ALLOCNO_CLASS (a)][ALLOCNO_MODE (a)];
3042	diff = ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a);
3043	#ifdef __has_builtin
3044	#if __has_builtin(__builtin_smul_overflow)
3045	#define HAS_SMUL_OVERFLOW
3046	#endif
3047	#endif
3048	/* Multiplication can overflow for very large functions.
3049	Check the overflow and constrain the result if necessary: */
3050	#ifdef HAS_SMUL_OVERFLOW
3051	if (__builtin_smul_overflow (mult, diff, &priority)
3052	|| priority < -INT_MAX)
3053	priority = diff >= 0 ? INT_MAX : -INT_MAX;
3054	#else
3055	static_assert
3056	(sizeof (long long) >= 2 * sizeof (int),
3057	"overflow code does not work for such int and long long sizes");
3058	long long priorityll = (long long) mult * diff;
3059	if (priorityll < -INT_MAX || priorityll > INT_MAX)
3060	priority = diff >= 0 ? INT_MAX : -INT_MAX;
3061	else
3062	priority = priorityll;
3063	#endif
3064	allocno_priorities[ALLOCNO_NUM (a)] = priority;
3065	if (priority < 0)
3066	priority = -priority;
3067	if (max_priority < priority)
3068	max_priority = priority;
3069	}
3070	mult = max_priority == 0 ? 1 : INT_MAX / max_priority;
3071	for (i = 0; i < n; i++)
3072	{
3073	a = consideration_allocnos[i];
3074	length = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
3075	if (ALLOCNO_NUM_OBJECTS (a) > 1)
3076	length /= ALLOCNO_NUM_OBJECTS (a);
3077	if (length <= 0)
3078	length = 1;
3079	allocno_priorities[ALLOCNO_NUM (a)]
3080	= allocno_priorities[ALLOCNO_NUM (a)] * mult / length;
3081	}
3082	}
3083
3084	/* Sort allocnos according to the profit of usage of a hard register
3085	instead of memory for them. */
3086	static int
3087	allocno_cost_compare_func (const void *v1p, const void *v2p)
3088	{
3089	ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
3090	ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
3091	int c1, c2;
3092
3093	c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_UPDATED_CLASS_COST (p1);
3094	c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_UPDATED_CLASS_COST (p2);
3095	if (c1 - c2)
3096	return c1 - c2;
3097
3098	/* If regs are equally good, sort by allocno numbers, so that the
3099	results of qsort leave nothing to chance. */
3100	return ALLOCNO_NUM (p1) - ALLOCNO_NUM (p2);
3101	}
3102
3103	/* Return savings on removed copies when ALLOCNO is assigned to
3104	HARD_REGNO. */
3105	static int
3106	allocno_copy_cost_saving (ira_allocno_t allocno, int hard_regno)
3107	{
3108	int cost = 0;
3109	machine_mode allocno_mode = ALLOCNO_MODE (allocno);
3110	enum reg_class rclass;
3111	ira_copy_t cp, next_cp;
3112
3113	rclass = REGNO_REG_CLASS (hard_regno);
3114	if (ira_reg_class_max_nregs[rclass][allocno_mode]
3115	> ira_class_hard_regs_num[rclass])
3116	/* For the above condition the cost can be wrong. Use the allocno
3117	class in this case. */
3118	rclass = ALLOCNO_CLASS (allocno);
3119	for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
3120	{
3121	if (cp->first == allocno)
3122	{
3123	next_cp = cp->next_first_allocno_copy;
3124	if (ALLOCNO_HARD_REGNO (cp->second) != hard_regno)
3125	continue;
3126	}
3127	else if (cp->second == allocno)
3128	{
3129	next_cp = cp->next_second_allocno_copy;
3130	if (ALLOCNO_HARD_REGNO (cp->first) != hard_regno)
3131	continue;
3132	}
3133	else
3134	gcc_unreachable ();
3135	ira_init_register_move_cost_if_necessary (mode: allocno_mode);
3136	cost += cp->freq * ira_register_move_cost[allocno_mode][rclass][rclass];
3137	}
3138	return cost;
3139	}
3140
3141	/* We used Chaitin-Briggs coloring to assign as many pseudos as
3142	possible to hard registers. Let us try to improve allocation with
3143	cost point of view. This function improves the allocation by
3144	spilling some allocnos and assigning the freed hard registers to
3145	other allocnos if it decreases the overall allocation cost. */
3146	static void
3147	improve_allocation (void)
3148	{
3149	unsigned int i;
3150	int j, k, n, hregno, conflict_hregno, base_cost, class_size, word, nwords;
3151	int check, spill_cost, min_cost, nregs, conflict_nregs, r, best;
3152	bool try_p;
3153	enum reg_class aclass, rclass;
3154	machine_mode mode;
3155	int *allocno_costs;
3156	int costs[FIRST_PSEUDO_REGISTER];
3157	HARD_REG_SET conflicting_regs[2], profitable_hard_regs;
3158	ira_allocno_t a;
3159	bitmap_iterator bi;
3160	int saved_nregs;
3161	int add_cost;
3162
3163	/* Don't bother to optimize the code with static chain pointer and
3164	non-local goto in order not to spill the chain pointer
3165	pseudo. */
3166	if (cfun->static_chain_decl && crtl->has_nonlocal_goto)
3167	return;
3168	/* Clear counts used to process conflicting allocnos only once for
3169	each allocno. */
3170	EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3171	ALLOCNO_COLOR_DATA (ira_allocnos[i])->temp = 0;
3172	check = n = 0;
3173	/* Process each allocno and try to assign a hard register to it by
3174	spilling some its conflicting allocnos. */
3175	EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3176	{
3177	a = ira_allocnos[i];
3178	ALLOCNO_COLOR_DATA (a)->temp = 0;
3179	if (empty_profitable_hard_regs (a))
3180	continue;
3181	check++;
3182	aclass = ALLOCNO_CLASS (a);
3183	allocno_costs = ALLOCNO_HARD_REG_COSTS (a);
3184	if ((hregno = ALLOCNO_HARD_REGNO (a)) < 0)
3185	base_cost = ALLOCNO_UPDATED_MEMORY_COST (a);
3186	else if (allocno_costs == NULL)
3187	/* It means that assigning a hard register is not profitable
3188	(we don't waste memory for hard register costs in this
3189	case). */
3190	continue;
3191	else
3192	base_cost = (allocno_costs[ira_class_hard_reg_index[aclass][hregno]]
3193	- allocno_copy_cost_saving (allocno: a, hard_regno: hregno));
3194	try_p = false;
3195	get_conflict_and_start_profitable_regs (a, retry_p: false,
3196	conflict_regs: conflicting_regs,
3197	start_profitable_regs: &profitable_hard_regs);
3198	class_size = ira_class_hard_regs_num[aclass];
3199	mode = ALLOCNO_MODE (a);
3200	/* Set up cost improvement for usage of each profitable hard
3201	register for allocno A. */
3202	for (j = 0; j < class_size; j++)
3203	{
3204	hregno = ira_class_hard_regs[aclass][j];
3205	if (! check_hard_reg_p (a, hard_regno: hregno,
3206	conflict_regs: conflicting_regs, profitable_regs: profitable_hard_regs))
3207	continue;
3208	ira_assert (ira_class_hard_reg_index[aclass][hregno] == j);
3209	k = allocno_costs == NULL ? 0 : j;
3210	costs[hregno] = (allocno_costs == NULL
3211	? ALLOCNO_UPDATED_CLASS_COST (a) : allocno_costs[k]);
3212	costs[hregno] -= allocno_copy_cost_saving (allocno: a, hard_regno: hregno);
3213
3214	if ((saved_nregs = calculate_saved_nregs (hard_regno: hregno, mode)) != 0)
3215	{
3216	/* We need to save/restore the hard register in
3217	epilogue/prologue. Therefore we increase the cost.
3218	Since the prolog is placed in the entry BB, the frequency
3219	of the entry BB is considered while computing the cost. */
3220	rclass = REGNO_REG_CLASS (hregno);
3221	add_cost = ((ira_memory_move_cost[mode][rclass][0]
3222	+ ira_memory_move_cost[mode][rclass][1])
3223	* saved_nregs / hard_regno_nregs (regno: hregno,
3224	mode) - 1)
3225	* REG_FREQ_FROM_BB (ENTRY_BLOCK_PTR_FOR_FN (cfun));
3226	costs[hregno] += add_cost;
3227	}
3228
3229	costs[hregno] -= base_cost;
3230	if (costs[hregno] < 0)
3231	try_p = true;
3232	}
3233	if (! try_p)
3234	/* There is no chance to improve the allocation cost by
3235	assigning hard register to allocno A even without spilling
3236	conflicting allocnos. */
3237	continue;
3238	auto_bitmap allocnos_to_spill;
3239	HARD_REG_SET soft_conflict_regs = {};
3240	mode = ALLOCNO_MODE (a);
3241	nwords = ALLOCNO_NUM_OBJECTS (a);
3242	/* Process each allocno conflicting with A and update the cost
3243	improvement for profitable hard registers of A. To use a
3244	hard register for A we need to spill some conflicting
3245	allocnos and that creates penalty for the cost
3246	improvement. */
3247	for (word = 0; word < nwords; word++)
3248	{
3249	ira_object_t conflict_obj;
3250	ira_object_t obj = ALLOCNO_OBJECT (a, word);
3251	ira_object_conflict_iterator oci;
3252
3253	FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
3254	{
3255	ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
3256
3257	if (ALLOCNO_COLOR_DATA (conflict_a)->temp == check)
3258	/* We already processed this conflicting allocno
3259	because we processed earlier another object of the
3260	conflicting allocno. */
3261	continue;
3262	ALLOCNO_COLOR_DATA (conflict_a)->temp = check;
3263	if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0)
3264	continue;
3265	auto spill_a = ira_soft_conflict (a1: a, a2: conflict_a);
3266	if (spill_a)
3267	{
3268	if (!bitmap_set_bit (allocnos_to_spill,
3269	ALLOCNO_NUM (spill_a)))
3270	continue;
3271	ira_loop_border_costs border_costs (spill_a);
3272	spill_cost = border_costs.spill_inside_loop_cost ();
3273	}
3274	else
3275	{
3276	spill_cost = ALLOCNO_UPDATED_MEMORY_COST (conflict_a);
3277	k = (ira_class_hard_reg_index
3278	[ALLOCNO_CLASS (conflict_a)][conflict_hregno]);
3279	ira_assert (k >= 0);
3280	if ((allocno_costs = ALLOCNO_HARD_REG_COSTS (conflict_a))
3281	!= NULL)
3282	spill_cost -= allocno_costs[k];
3283	else
3284	spill_cost -= ALLOCNO_UPDATED_CLASS_COST (conflict_a);
3285	spill_cost
3286	+= allocno_copy_cost_saving (allocno: conflict_a, hard_regno: conflict_hregno);
3287	}
3288	conflict_nregs = hard_regno_nregs (regno: conflict_hregno,
3289	ALLOCNO_MODE (conflict_a));
3290	auto note_conflict = [&](int r)
3291	{
3292	if (check_hard_reg_p (a, hard_regno: r,
3293	conflict_regs: conflicting_regs, profitable_regs: profitable_hard_regs))
3294	{
3295	if (spill_a)
3296	SET_HARD_REG_BIT (set&: soft_conflict_regs, bit: r);
3297	costs[r] += spill_cost;
3298	}
3299	};
3300	for (r = conflict_hregno;
3301	r >= 0 && (int) end_hard_regno (mode, regno: r) > conflict_hregno;
3302	r--)
3303	note_conflict (r);
3304	for (r = conflict_hregno + 1;
3305	r < conflict_hregno + conflict_nregs;
3306	r++)
3307	note_conflict (r);
3308	}
3309	}
3310	min_cost = INT_MAX;
3311	best = -1;
3312	/* Now we choose hard register for A which results in highest
3313	allocation cost improvement. */
3314	for (j = 0; j < class_size; j++)
3315	{
3316	hregno = ira_class_hard_regs[aclass][j];
3317	if (check_hard_reg_p (a, hard_regno: hregno,
3318	conflict_regs: conflicting_regs, profitable_regs: profitable_hard_regs)
3319	&& min_cost > costs[hregno])
3320	{
3321	best = hregno;
3322	min_cost = costs[hregno];
3323	}
3324	}
3325	if (min_cost >= 0)
3326	/* We are in a situation when assigning any hard register to A
3327	by spilling some conflicting allocnos does not improve the
3328	allocation cost. */
3329	continue;
3330	spill_soft_conflicts (a, allocnos_to_spill, soft_conflict_regs, hregno: best);
3331	nregs = hard_regno_nregs (regno: best, mode);
3332	/* Now spill conflicting allocnos which contain a hard register
3333	of A when we assign the best chosen hard register to it. */
3334	for (word = 0; word < nwords; word++)
3335	{
3336	ira_object_t conflict_obj;
3337	ira_object_t obj = ALLOCNO_OBJECT (a, word);
3338	ira_object_conflict_iterator oci;
3339
3340	FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
3341	{
3342	ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
3343
3344	if ((conflict_hregno = ALLOCNO_HARD_REGNO (conflict_a)) < 0)
3345	continue;
3346	conflict_nregs = hard_regno_nregs (regno: conflict_hregno,
3347	ALLOCNO_MODE (conflict_a));
3348	if (best + nregs <= conflict_hregno
3349	|| conflict_hregno + conflict_nregs <= best)
3350	/* No intersection. */
3351	continue;
3352	ALLOCNO_HARD_REGNO (conflict_a) = -1;
3353	sorted_allocnos[n++] = conflict_a;
3354	if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3355	fprintf (stream: ira_dump_file, format: "Spilling a%dr%d for a%dr%d\n",
3356	ALLOCNO_NUM (conflict_a), ALLOCNO_REGNO (conflict_a),
3357	ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
3358	}
3359	}
3360	/* Assign the best chosen hard register to A. */
3361	ALLOCNO_HARD_REGNO (a) = best;
3362
3363	for (j = nregs - 1; j >= 0; j--)
3364	allocated_hardreg_p[best + j] = true;
3365
3366	if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3367	fprintf (stream: ira_dump_file, format: "Assigning %d to a%dr%d\n",
3368	best, ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
3369	}
3370	if (n == 0)
3371	return;
3372	/* We spilled some allocnos to assign their hard registers to other
3373	allocnos. The spilled allocnos are now in array
3374	'sorted_allocnos'. There is still a possibility that some of the
3375	spilled allocnos can get hard registers. So let us try assign
3376	them hard registers again (just a reminder -- function
3377	'assign_hard_reg' assigns hard registers only if it is possible
3378	and profitable). We process the spilled allocnos with biggest
3379	benefit to get hard register first -- see function
3380	'allocno_cost_compare_func'. */
3381	qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
3382	allocno_cost_compare_func);
3383	for (j = 0; j < n; j++)
3384	{
3385	a = sorted_allocnos[j];
3386	ALLOCNO_ASSIGNED_P (a) = false;
3387	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3388	{
3389	fprintf (stream: ira_dump_file, format: " ");
3390	ira_print_expanded_allocno (a);
3391	fprintf (stream: ira_dump_file, format: " -- ");
3392	}
3393	if (assign_hard_reg (a, retry_p: false))
3394	{
3395	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3396	fprintf (stream: ira_dump_file, format: "assign hard reg %d\n",
3397	ALLOCNO_HARD_REGNO (a));
3398	}
3399	else
3400	{
3401	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3402	fprintf (stream: ira_dump_file, format: "assign memory\n");
3403	}
3404	}
3405	}
3406
3407	/* Sort allocnos according to their priorities. */
3408	static int
3409	allocno_priority_compare_func (const void *v1p, const void *v2p)
3410	{
3411	ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
3412	ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
3413	int pri1, pri2, diff;
3414
3415	/* Assign hard reg to static chain pointer pseudo first when
3416	non-local goto is used. */
3417	if ((diff = (non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a2))
3418	- non_spilled_static_chain_regno_p (ALLOCNO_REGNO (a1)))) != 0)
3419	return diff;
3420	pri1 = allocno_priorities[ALLOCNO_NUM (a1)];
3421	pri2 = allocno_priorities[ALLOCNO_NUM (a2)];
3422	if (pri2 != pri1)
3423	return SORTGT (pri2, pri1);
3424
3425	/* If regs are equally good, sort by allocnos, so that the results of
3426	qsort leave nothing to chance. */
3427	return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
3428	}
3429
3430	/* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
3431	taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
3432	static void
3433	color_allocnos (void)
3434	{
3435	unsigned int i, n;
3436	bitmap_iterator bi;
3437	ira_allocno_t a;
3438
3439	setup_profitable_hard_regs ();
3440	EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3441	{
3442	allocno_color_data_t data;
3443	ira_pref_t pref, next_pref;
3444
3445	a = ira_allocnos[i];
3446	data = ALLOCNO_COLOR_DATA (a);
3447	data->conflict_allocno_hard_prefs = 0;
3448	for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = next_pref)
3449	{
3450	next_pref = pref->next_pref;
3451	if (! ira_hard_reg_in_set_p (hard_regno: pref->hard_regno,
3452	ALLOCNO_MODE (a),
3453	hard_regset: data->profitable_hard_regs))
3454	ira_remove_pref (pref);
3455	}
3456	}
3457
3458	if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
3459	{
3460	n = 0;
3461	EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3462	{
3463	a = ira_allocnos[i];
3464	if (ALLOCNO_CLASS (a) == NO_REGS)
3465	{
3466	ALLOCNO_HARD_REGNO (a) = -1;
3467	ALLOCNO_ASSIGNED_P (a) = true;
3468	ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
3469	ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
3470	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3471	{
3472	fprintf (stream: ira_dump_file, format: " Spill");
3473	ira_print_expanded_allocno (a);
3474	fprintf (stream: ira_dump_file, format: "\n");
3475	}
3476	continue;
3477	}
3478	sorted_allocnos[n++] = a;
3479	}
3480	if (n != 0)
3481	{
3482	setup_allocno_priorities (consideration_allocnos: sorted_allocnos, n);
3483	qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
3484	allocno_priority_compare_func);
3485	for (i = 0; i < n; i++)
3486	{
3487	a = sorted_allocnos[i];
3488	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3489	{
3490	fprintf (stream: ira_dump_file, format: " ");
3491	ira_print_expanded_allocno (a);
3492	fprintf (stream: ira_dump_file, format: " -- ");
3493	}
3494	if (assign_hard_reg (a, retry_p: false))
3495	{
3496	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3497	fprintf (stream: ira_dump_file, format: "assign hard reg %d\n",
3498	ALLOCNO_HARD_REGNO (a));
3499	}
3500	else
3501	{
3502	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3503	fprintf (stream: ira_dump_file, format: "assign memory\n");
3504	}
3505	}
3506	}
3507	}
3508	else
3509	{
3510	form_allocno_hard_regs_nodes_forest ();
3511	if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3512	print_hard_regs_forest (f: ira_dump_file);
3513	EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3514	{
3515	a = ira_allocnos[i];
3516	if (ALLOCNO_CLASS (a) != NO_REGS && ! empty_profitable_hard_regs (a))
3517	{
3518	ALLOCNO_COLOR_DATA (a)->in_graph_p = true;
3519	update_conflict_allocno_hard_prefs (allocno: a);
3520	}
3521	else
3522	{
3523	ALLOCNO_HARD_REGNO (a) = -1;
3524	ALLOCNO_ASSIGNED_P (a) = true;
3525	/* We don't need updated costs anymore. */
3526	ira_free_allocno_updated_costs (a);
3527	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3528	{
3529	fprintf (stream: ira_dump_file, format: " Spill");
3530	ira_print_expanded_allocno (a);
3531	fprintf (stream: ira_dump_file, format: "\n");
3532	}
3533	}
3534	}
3535	/* Put the allocnos into the corresponding buckets. */
3536	colorable_allocno_bucket = NULL;
3537	uncolorable_allocno_bucket = NULL;
3538	EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
3539	{
3540	a = ira_allocnos[i];
3541	if (ALLOCNO_COLOR_DATA (a)->in_graph_p)
3542	put_allocno_into_bucket (allocno: a);
3543	}
3544	push_allocnos_to_stack ();
3545	pop_allocnos_from_stack ();
3546	finish_allocno_hard_regs_nodes_forest ();
3547	}
3548	improve_allocation ();
3549	}
3550
3551
3552
3553	/* Output information about the loop given by its LOOP_TREE_NODE. */
3554	static void
3555	print_loop_title (ira_loop_tree_node_t loop_tree_node)
3556	{
3557	unsigned int j;
3558	bitmap_iterator bi;
3559	ira_loop_tree_node_t subloop_node, dest_loop_node;
3560	edge e;
3561	edge_iterator ei;
3562
3563	if (loop_tree_node->parent == NULL)
3564	fprintf (stream: ira_dump_file,
3565	format: "\n Loop 0 (parent -1, header bb%d, depth 0)\n bbs:",
3566	NUM_FIXED_BLOCKS);
3567	else
3568	{
3569	ira_assert (current_loops != NULL && loop_tree_node->loop != NULL);
3570	fprintf (stream: ira_dump_file,
3571	format: "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
3572	loop_tree_node->loop_num, loop_tree_node->parent->loop_num,
3573	loop_tree_node->loop->header->index,
3574	loop_depth (loop: loop_tree_node->loop));
3575	}
3576	for (subloop_node = loop_tree_node->children;
3577	subloop_node != NULL;
3578	subloop_node = subloop_node->next)
3579	if (subloop_node->bb != NULL)
3580	{
3581	fprintf (stream: ira_dump_file, format: " %d", subloop_node->bb->index);
3582	FOR_EACH_EDGE (e, ei, subloop_node->bb->succs)
3583	if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
3584	&& ((dest_loop_node = IRA_BB_NODE (e->dest)->parent)
3585	!= loop_tree_node))
3586	fprintf (stream: ira_dump_file, format: "(->%d:l%d)",
3587	e->dest->index, dest_loop_node->loop_num);
3588	}
3589	fprintf (stream: ira_dump_file, format: "\n all:");
3590	EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
3591	fprintf (stream: ira_dump_file, format: " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
3592	fprintf (stream: ira_dump_file, format: "\n modified regnos:");
3593	EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->modified_regnos, 0, j, bi)
3594	fprintf (stream: ira_dump_file, format: " %d", j);
3595	fprintf (stream: ira_dump_file, format: "\n border:");
3596	EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->border_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 Pressure:");
3599	for (j = 0; (int) j < ira_pressure_classes_num; j++)
3600	{
3601	enum reg_class pclass;
3602
3603	pclass = ira_pressure_classes[j];
3604	if (loop_tree_node->reg_pressure[pclass] == 0)
3605	continue;
3606	fprintf (stream: ira_dump_file, format: " %s=%d", reg_class_names[pclass],
3607	loop_tree_node->reg_pressure[pclass]);
3608	}
3609	fprintf (stream: ira_dump_file, format: "\n");
3610	}
3611
3612	/* Color the allocnos inside loop (in the extreme case it can be all
3613	of the function) given the corresponding LOOP_TREE_NODE. The
3614	function is called for each loop during top-down traverse of the
3615	loop tree. */
3616	static void
3617	color_pass (ira_loop_tree_node_t loop_tree_node)
3618	{
3619	int regno, hard_regno, index = -1, n;
3620	int cost;
3621	unsigned int j;
3622	bitmap_iterator bi;
3623	machine_mode mode;
3624	enum reg_class rclass, aclass;
3625	ira_allocno_t a, subloop_allocno;
3626	ira_loop_tree_node_t subloop_node;
3627
3628	ira_assert (loop_tree_node->bb == NULL);
3629	if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
3630	print_loop_title (loop_tree_node);
3631
3632	bitmap_copy (coloring_allocno_bitmap, loop_tree_node->all_allocnos);
3633	bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap);
3634	n = 0;
3635	EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3636	{
3637	a = ira_allocnos[j];
3638	n++;
3639	if (! ALLOCNO_ASSIGNED_P (a))
3640	continue;
3641	bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a));
3642	}
3643	allocno_color_data
3644	= (allocno_color_data_t) ira_allocate (sizeof (struct allocno_color_data)
3645	* n);
3646	memset (s: allocno_color_data, c: 0, n: sizeof (struct allocno_color_data) * n);
3647	curr_allocno_process = 0;
3648	n = 0;
3649	EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3650	{
3651	a = ira_allocnos[j];
3652	ALLOCNO_ADD_DATA (a) = allocno_color_data + n;
3653	n++;
3654	}
3655	init_allocno_threads ();
3656	/* Color all mentioned allocnos including transparent ones. */
3657	color_allocnos ();
3658	/* Process caps. They are processed just once. */
3659	if (flag_ira_region == IRA_REGION_MIXED
3660	|| flag_ira_region == IRA_REGION_ALL)
3661	EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
3662	{
3663	a = ira_allocnos[j];
3664	if (ALLOCNO_CAP_MEMBER (a) == NULL)
3665	continue;
3666	/* Remove from processing in the next loop. */
3667	bitmap_clear_bit (consideration_allocno_bitmap, j);
3668	rclass = ALLOCNO_CLASS (a);
3669	subloop_allocno = ALLOCNO_CAP_MEMBER (a);
3670	subloop_node = ALLOCNO_LOOP_TREE_NODE (subloop_allocno);
3671	if (ira_single_region_allocno_p (a, subloop_a: subloop_allocno))
3672	{
3673	mode = ALLOCNO_MODE (a);
3674	hard_regno = ALLOCNO_HARD_REGNO (a);
3675	if (hard_regno >= 0)
3676	{
3677	index = ira_class_hard_reg_index[rclass][hard_regno];
3678	ira_assert (index >= 0);
3679	}
3680	regno = ALLOCNO_REGNO (a);
3681	ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno));
3682	ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
3683	ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
3684	if (hard_regno >= 0)
3685	update_costs_from_copies (allocno: subloop_allocno, decr_p: true, record_p: true);
3686	/* We don't need updated costs anymore. */
3687	ira_free_allocno_updated_costs (subloop_allocno);
3688	}
3689	}
3690	/* Update costs of the corresponding allocnos (not caps) in the
3691	subloops. */
3692	for (subloop_node = loop_tree_node->subloops;
3693	subloop_node != NULL;
3694	subloop_node = subloop_node->subloop_next)
3695	{
3696	ira_assert (subloop_node->bb == NULL);
3697	EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3698	{
3699	a = ira_allocnos[j];
3700	ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
3701	mode = ALLOCNO_MODE (a);
3702	rclass = ALLOCNO_CLASS (a);
3703	hard_regno = ALLOCNO_HARD_REGNO (a);
3704	/* Use hard register class here. ??? */
3705	if (hard_regno >= 0)
3706	{
3707	index = ira_class_hard_reg_index[rclass][hard_regno];
3708	ira_assert (index >= 0);
3709	}
3710	regno = ALLOCNO_REGNO (a);
3711	/* ??? conflict costs */
3712	subloop_allocno = subloop_node->regno_allocno_map[regno];
3713	if (subloop_allocno == NULL
3714	|| ALLOCNO_CAP (subloop_allocno) != NULL)
3715	continue;
3716	ira_assert (ALLOCNO_CLASS (subloop_allocno) == rclass);
3717	ira_assert (bitmap_bit_p (subloop_node->all_allocnos,
3718	ALLOCNO_NUM (subloop_allocno)));
3719	if (ira_single_region_allocno_p (a, subloop_a: subloop_allocno)
3720	|| !ira_subloop_allocnos_can_differ_p (a, allocated_p: hard_regno >= 0,
3721	exclude_old_reload: false))
3722	{
3723	gcc_assert (!ALLOCNO_MIGHT_CONFLICT_WITH_PARENT_P
3724	(subloop_allocno));
3725	if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
3726	{
3727	ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
3728	ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
3729	if (hard_regno >= 0)
3730	update_costs_from_copies (allocno: subloop_allocno, decr_p: true, record_p: true);
3731	/* We don't need updated costs anymore. */
3732	ira_free_allocno_updated_costs (subloop_allocno);
3733	}
3734	}
3735	else if (hard_regno < 0)
3736	{
3737	/* If we allocate a register to SUBLOOP_ALLOCNO, we'll need
3738	to load the register on entry to the subloop and store
3739	the register back on exit from the subloop. This incurs
3740	a fixed cost for all registers. Since UPDATED_MEMORY_COST
3741	is (and should only be) used relative to the register costs
3742	for the same allocno, we can subtract this shared register
3743	cost from the memory cost. */
3744	ira_loop_border_costs border_costs (subloop_allocno);
3745	ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
3746	-= border_costs.spill_outside_loop_cost ();
3747	}
3748	else
3749	{
3750	ira_loop_border_costs border_costs (subloop_allocno);
3751	aclass = ALLOCNO_CLASS (subloop_allocno);
3752	ira_init_register_move_cost_if_necessary (mode);
3753	cost = border_costs.move_between_loops_cost ();
3754	ira_allocate_and_set_or_copy_costs
3755	(vec: &ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno), aclass,
3756	ALLOCNO_UPDATED_CLASS_COST (subloop_allocno),
3757	ALLOCNO_HARD_REG_COSTS (subloop_allocno));
3758	ira_allocate_and_set_or_copy_costs
3759	(vec: &ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno),
3760	aclass, val: 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno));
3761	ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
3762	ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
3763	-= cost;
3764	if (ALLOCNO_UPDATED_CLASS_COST (subloop_allocno)
3765	> ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index])
3766	ALLOCNO_UPDATED_CLASS_COST (subloop_allocno)
3767	= ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index];
3768	/* If we spill SUBLOOP_ALLOCNO, we'll need to store HARD_REGNO
3769	on entry to the subloop and restore HARD_REGNO on exit from
3770	the subloop. */
3771	ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
3772	+= border_costs.spill_inside_loop_cost ();
3773	}
3774	}
3775	}
3776	ira_free (addr: allocno_color_data);
3777	EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
3778	{
3779	a = ira_allocnos[j];
3780	ALLOCNO_ADD_DATA (a) = NULL;
3781	}
3782	}
3783
3784	/* Initialize the common data for coloring and calls functions to do
3785	Chaitin-Briggs and regional coloring. */
3786	static void
3787	do_coloring (void)
3788	{
3789	coloring_allocno_bitmap = ira_allocate_bitmap ();
3790	if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3791	fprintf (stream: ira_dump_file, format: "\n**** Allocnos coloring:\n\n");
3792
3793	ira_traverse_loop_tree (false, ira_loop_tree_root, color_pass, NULL);
3794
3795	if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
3796	ira_print_disposition (ira_dump_file);
3797
3798	ira_free_bitmap (coloring_allocno_bitmap);
3799	}
3800
3801
3802
3803	/* Move spill/restore code, which are to be generated in ira-emit.cc,
3804	to less frequent points (if it is profitable) by reassigning some
3805	allocnos (in loop with subloops containing in another loop) to
3806	memory which results in longer live-range where the corresponding
3807	pseudo-registers will be in memory. */
3808	static void
3809	move_spill_restore (void)
3810	{
3811	int cost, regno, hard_regno, hard_regno2, index;
3812	bool changed_p;
3813	machine_mode mode;
3814	enum reg_class rclass;
3815	ira_allocno_t a, parent_allocno, subloop_allocno;
3816	ira_loop_tree_node_t parent, loop_node, subloop_node;
3817	ira_allocno_iterator ai;
3818
3819	for (;;)
3820	{
3821	changed_p = false;
3822	if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3823	fprintf (stream: ira_dump_file, format: "New iteration of spill/restore move\n");
3824	FOR_EACH_ALLOCNO (a, ai)
3825	{
3826	regno = ALLOCNO_REGNO (a);
3827	loop_node = ALLOCNO_LOOP_TREE_NODE (a);
3828	if (ALLOCNO_CAP_MEMBER (a) != NULL
3829	|| ALLOCNO_CAP (a) != NULL
3830	|| (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0
3831	|| loop_node->children == NULL
3832	/* don't do the optimization because it can create
3833	copies and the reload pass can spill the allocno set
3834	by copy although the allocno will not get memory
3835	slot. */
3836	|| ira_equiv_no_lvalue_p (regno)
3837	|| !bitmap_bit_p (loop_node->border_allocnos, ALLOCNO_NUM (a))
3838	/* Do not spill static chain pointer pseudo when
3839	non-local goto is used. */
3840	|| non_spilled_static_chain_regno_p (regno))
3841	continue;
3842	mode = ALLOCNO_MODE (a);
3843	rclass = ALLOCNO_CLASS (a);
3844	index = ira_class_hard_reg_index[rclass][hard_regno];
3845	ira_assert (index >= 0);
3846	cost = (ALLOCNO_MEMORY_COST (a)
3847	- (ALLOCNO_HARD_REG_COSTS (a) == NULL
3848	? ALLOCNO_CLASS_COST (a)
3849	: ALLOCNO_HARD_REG_COSTS (a)[index]));
3850	ira_init_register_move_cost_if_necessary (mode);
3851	for (subloop_node = loop_node->subloops;
3852	subloop_node != NULL;
3853	subloop_node = subloop_node->subloop_next)
3854	{
3855	ira_assert (subloop_node->bb == NULL);
3856	subloop_allocno = subloop_node->regno_allocno_map[regno];
3857	if (subloop_allocno == NULL)
3858	continue;
3859	ira_assert (rclass == ALLOCNO_CLASS (subloop_allocno));
3860	ira_loop_border_costs border_costs (subloop_allocno);
3861
3862	/* We have accumulated cost. To get the real cost of
3863	allocno usage in the loop we should subtract the costs
3864	added by propagate_allocno_info for the subloop allocnos. */
3865	int reg_cost
3866	= (ALLOCNO_HARD_REG_COSTS (subloop_allocno) == NULL
3867	? ALLOCNO_CLASS_COST (subloop_allocno)
3868	: ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index]);
3869
3870	int spill_cost
3871	= (border_costs.spill_inside_loop_cost ()
3872	+ ALLOCNO_MEMORY_COST (subloop_allocno));
3873
3874	/* If HARD_REGNO conflicts with SUBLOOP_A then
3875	propagate_allocno_info will have propagated
3876	the cost of spilling HARD_REGNO in SUBLOOP_NODE.
3877	(ira_subloop_allocnos_can_differ_p must be true
3878	in that case.) If HARD_REGNO is a caller-saved
3879	register, we might have modelled it in the same way.
3880
3881	Otherwise, SPILL_COST acted as a cap on the propagated
3882	register cost, in cases where the allocations can differ. */
3883	auto conflicts = ira_total_conflict_hard_regs (a: subloop_allocno);
3884	if (TEST_HARD_REG_BIT (set: conflicts, bit: hard_regno)
3885	|| (ira_need_caller_save_p (a: subloop_allocno, regno: hard_regno)
3886	&& ira_caller_save_loop_spill_p (a, subloop_a: subloop_allocno,
3887	spill_cost)))
3888	reg_cost = spill_cost;
3889	else if (ira_subloop_allocnos_can_differ_p (a))
3890	reg_cost = MIN (reg_cost, spill_cost);
3891
3892	cost -= ALLOCNO_MEMORY_COST (subloop_allocno) - reg_cost;
3893
3894	if ((hard_regno2 = ALLOCNO_HARD_REGNO (subloop_allocno)) < 0)
3895	/* The register was spilled in the subloop. If we spill
3896	it in the outer loop too then we'll no longer need to
3897	save the register on entry to the subloop and restore
3898	the register on exit from the subloop. */
3899	cost -= border_costs.spill_inside_loop_cost ();
3900	else
3901	{
3902	/* The register was also allocated in the subloop. If we
3903	spill it in the outer loop then we'll need to load the
3904	register on entry to the subloop and store the register
3905	back on exit from the subloop. */
3906	cost += border_costs.spill_outside_loop_cost ();
3907	if (hard_regno2 != hard_regno)
3908	cost -= border_costs.move_between_loops_cost ();
3909	}
3910	}
3911	if ((parent = loop_node->parent) != NULL
3912	&& (parent_allocno = parent->regno_allocno_map[regno]) != NULL)
3913	{
3914	ira_assert (rclass == ALLOCNO_CLASS (parent_allocno));
3915	ira_loop_border_costs border_costs (a);
3916	if ((hard_regno2 = ALLOCNO_HARD_REGNO (parent_allocno)) < 0)
3917	/* The register was spilled in the parent loop. If we spill
3918	it in this loop too then we'll no longer need to load the
3919	register on entry to this loop and save the register back
3920	on exit from this loop. */
3921	cost -= border_costs.spill_outside_loop_cost ();
3922	else
3923	{
3924	/* The register was also allocated in the parent loop.
3925	If we spill it in this loop then we'll need to save
3926	the register on entry to this loop and restore the
3927	register on exit from this loop. */
3928	cost += border_costs.spill_inside_loop_cost ();
3929	if (hard_regno2 != hard_regno)
3930	cost -= border_costs.move_between_loops_cost ();
3931	}
3932	}
3933	if (cost < 0)
3934	{
3935	ALLOCNO_HARD_REGNO (a) = -1;
3936	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
3937	{
3938	fprintf
3939	(stream: ira_dump_file,
3940	format: " Moving spill/restore for a%dr%d up from loop %d",
3941	ALLOCNO_NUM (a), regno, loop_node->loop_num);
3942	fprintf (stream: ira_dump_file, format: " - profit %d\n", -cost);
3943	}
3944	changed_p = true;
3945	}
3946	}
3947	if (! changed_p)
3948	break;
3949	}
3950	}
3951
3952
3953
3954	/* Update current hard reg costs and current conflict hard reg costs
3955	for allocno A. It is done by processing its copies containing
3956	other allocnos already assigned. */
3957	static void
3958	update_curr_costs (ira_allocno_t a)
3959	{
3960	int i, hard_regno, cost;
3961	machine_mode mode;
3962	enum reg_class aclass, rclass;
3963	ira_allocno_t another_a;
3964	ira_copy_t cp, next_cp;
3965
3966	ira_free_allocno_updated_costs (a);
3967	ira_assert (! ALLOCNO_ASSIGNED_P (a));
3968	aclass = ALLOCNO_CLASS (a);
3969	if (aclass == NO_REGS)
3970	return;
3971	mode = ALLOCNO_MODE (a);
3972	ira_init_register_move_cost_if_necessary (mode);
3973	for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
3974	{
3975	if (cp->first == a)
3976	{
3977	next_cp = cp->next_first_allocno_copy;
3978	another_a = cp->second;
3979	}
3980	else if (cp->second == a)
3981	{
3982	next_cp = cp->next_second_allocno_copy;
3983	another_a = cp->first;
3984	}
3985	else
3986	gcc_unreachable ();
3987	if (! ira_reg_classes_intersect_p[aclass][ALLOCNO_CLASS (another_a)]
3988	|| ! ALLOCNO_ASSIGNED_P (another_a)
3989	|| (hard_regno = ALLOCNO_HARD_REGNO (another_a)) < 0)
3990	continue;
3991	rclass = REGNO_REG_CLASS (hard_regno);
3992	i = ira_class_hard_reg_index[aclass][hard_regno];
3993	if (i < 0)
3994	continue;
3995	cost = (cp->first == a
3996	? ira_register_move_cost[mode][rclass][aclass]
3997	: ira_register_move_cost[mode][aclass][rclass]);
3998	ira_allocate_and_set_or_copy_costs
3999	(vec: &ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass, ALLOCNO_CLASS_COST (a),
4000	ALLOCNO_HARD_REG_COSTS (a));
4001	ira_allocate_and_set_or_copy_costs
4002	(vec: &ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
4003	aclass, val: 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
4004	ALLOCNO_UPDATED_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
4005	ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
4006	}
4007	}
4008
4009	/* Try to assign hard registers to the unassigned allocnos and
4010	allocnos conflicting with them or conflicting with allocnos whose
4011	regno >= START_REGNO. The function is called after ira_flattening,
4012	so more allocnos (including ones created in ira-emit.cc) will have a
4013	chance to get a hard register. We use simple assignment algorithm
4014	based on priorities. */
4015	void
4016	ira_reassign_conflict_allocnos (int start_regno)
4017	{
4018	int i, allocnos_to_color_num;
4019	ira_allocno_t a;
4020	enum reg_class aclass;
4021	bitmap allocnos_to_color;
4022	ira_allocno_iterator ai;
4023
4024	allocnos_to_color = ira_allocate_bitmap ();
4025	allocnos_to_color_num = 0;
4026	FOR_EACH_ALLOCNO (a, ai)
4027	{
4028	int n = ALLOCNO_NUM_OBJECTS (a);
4029
4030	if (! ALLOCNO_ASSIGNED_P (a)
4031	&& ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a)))
4032	{
4033	if (ALLOCNO_CLASS (a) != NO_REGS)
4034	sorted_allocnos[allocnos_to_color_num++] = a;
4035	else
4036	{
4037	ALLOCNO_ASSIGNED_P (a) = true;
4038	ALLOCNO_HARD_REGNO (a) = -1;
4039	ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
4040	ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
4041	}
4042	bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (a));
4043	}
4044	if (ALLOCNO_REGNO (a) < start_regno
4045	|| (aclass = ALLOCNO_CLASS (a)) == NO_REGS)
4046	continue;
4047	for (i = 0; i < n; i++)
4048	{
4049	ira_object_t obj = ALLOCNO_OBJECT (a, i);
4050	ira_object_t conflict_obj;
4051	ira_object_conflict_iterator oci;
4052
4053	FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
4054	{
4055	ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
4056
4057	ira_assert (ira_reg_classes_intersect_p
4058	[aclass][ALLOCNO_CLASS (conflict_a)]);
4059	if (!bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a)))
4060	continue;
4061	sorted_allocnos[allocnos_to_color_num++] = conflict_a;
4062	}
4063	}
4064	}
4065	ira_free_bitmap (allocnos_to_color);
4066	if (allocnos_to_color_num > 1)
4067	{
4068	setup_allocno_priorities (consideration_allocnos: sorted_allocnos, n: allocnos_to_color_num);
4069	qsort (sorted_allocnos, allocnos_to_color_num, sizeof (ira_allocno_t),
4070	allocno_priority_compare_func);
4071	}
4072	for (i = 0; i < allocnos_to_color_num; i++)
4073	{
4074	a = sorted_allocnos[i];
4075	ALLOCNO_ASSIGNED_P (a) = false;
4076	update_curr_costs (a);
4077	}
4078	for (i = 0; i < allocnos_to_color_num; i++)
4079	{
4080	a = sorted_allocnos[i];
4081	if (assign_hard_reg (a, retry_p: true))
4082	{
4083	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4084	fprintf
4085	(stream: ira_dump_file,
4086	format: " Secondary allocation: assign hard reg %d to reg %d\n",
4087	ALLOCNO_HARD_REGNO (a), ALLOCNO_REGNO (a));
4088	}
4089	}
4090	}
4091
4092
4093
4094	/* This page contains functions used to find conflicts using allocno
4095	live ranges. */
4096
4097	#ifdef ENABLE_IRA_CHECKING
4098
4099	/* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
4100	intersect. This should be used when there is only one region.
4101	Currently this is used during reload. */
4102	static bool
4103	conflict_by_live_ranges_p (int regno1, int regno2)
4104	{
4105	ira_allocno_t a1, a2;
4106
4107	ira_assert (regno1 >= FIRST_PSEUDO_REGISTER
4108	&& regno2 >= FIRST_PSEUDO_REGISTER);
4109	/* Reg info calculated by dataflow infrastructure can be different
4110	from one calculated by regclass. */
4111	if ((a1 = ira_loop_tree_root->regno_allocno_map[regno1]) == NULL
4112	|| (a2 = ira_loop_tree_root->regno_allocno_map[regno2]) == NULL)
4113	return false;
4114	return allocnos_conflict_by_live_ranges_p (a1, a2);
4115	}
4116
4117	#endif
4118
4119
4120
4121	/* This page contains code to coalesce memory stack slots used by
4122	spilled allocnos. This results in smaller stack frame, better data
4123	locality, and in smaller code for some architectures like
4124	x86/x86_64 where insn size depends on address displacement value.
4125	On the other hand, it can worsen insn scheduling after the RA but
4126	in practice it is less important than smaller stack frames. */
4127
4128	/* TRUE if we coalesced some allocnos. In other words, if we got
4129	loops formed by members first_coalesced_allocno and
4130	next_coalesced_allocno containing more one allocno. */
4131	static bool allocno_coalesced_p;
4132
4133	/* Bitmap used to prevent a repeated allocno processing because of
4134	coalescing. */
4135	static bitmap processed_coalesced_allocno_bitmap;
4136
4137	/* See below. */
4138	typedef struct coalesce_data *coalesce_data_t;
4139
4140	/* To decrease footprint of ira_allocno structure we store all data
4141	needed only for coalescing in the following structure. */
4142	struct coalesce_data
4143	{
4144	/* Coalesced allocnos form a cyclic list. One allocno given by
4145	FIRST represents all coalesced allocnos. The
4146	list is chained by NEXT. */
4147	ira_allocno_t first;
4148	ira_allocno_t next;
4149	int temp;
4150	};
4151
4152	/* Container for storing allocno data concerning coalescing. */
4153	static coalesce_data_t allocno_coalesce_data;
4154
4155	/* Macro to access the data concerning coalescing. */
4156	#define ALLOCNO_COALESCE_DATA(a) ((coalesce_data_t) ALLOCNO_ADD_DATA (a))
4157
4158	/* Merge two sets of coalesced allocnos given correspondingly by
4159	allocnos A1 and A2 (more accurately merging A2 set into A1
4160	set). */
4161	static void
4162	merge_allocnos (ira_allocno_t a1, ira_allocno_t a2)
4163	{
4164	ira_allocno_t a, first, last, next;
4165
4166	first = ALLOCNO_COALESCE_DATA (a1)->first;
4167	a = ALLOCNO_COALESCE_DATA (a2)->first;
4168	if (first == a)
4169	return;
4170	for (last = a2, a = ALLOCNO_COALESCE_DATA (a2)->next;;
4171	a = ALLOCNO_COALESCE_DATA (a)->next)
4172	{
4173	ALLOCNO_COALESCE_DATA (a)->first = first;
4174	if (a == a2)
4175	break;
4176	last = a;
4177	}
4178	next = allocno_coalesce_data[ALLOCNO_NUM (first)].next;
4179	allocno_coalesce_data[ALLOCNO_NUM (first)].next = a2;
4180	allocno_coalesce_data[ALLOCNO_NUM (last)].next = next;
4181	}
4182
4183	/* Return TRUE if there are conflicting allocnos from two sets of
4184	coalesced allocnos given correspondingly by allocnos A1 and A2. We
4185	use live ranges to find conflicts because conflicts are represented
4186	only for allocnos of the same allocno class and during the reload
4187	pass we coalesce allocnos for sharing stack memory slots. */
4188	static bool
4189	coalesced_allocno_conflict_p (ira_allocno_t a1, ira_allocno_t a2)
4190	{
4191	ira_allocno_t a, conflict_a;
4192
4193	if (allocno_coalesced_p)
4194	{
4195	bitmap_clear (processed_coalesced_allocno_bitmap);
4196	for (a = ALLOCNO_COALESCE_DATA (a1)->next;;
4197	a = ALLOCNO_COALESCE_DATA (a)->next)
4198	{
4199	bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a));
4200	if (a == a1)
4201	break;
4202	}
4203	}
4204	for (a = ALLOCNO_COALESCE_DATA (a2)->next;;
4205	a = ALLOCNO_COALESCE_DATA (a)->next)
4206	{
4207	for (conflict_a = ALLOCNO_COALESCE_DATA (a1)->next;;
4208	conflict_a = ALLOCNO_COALESCE_DATA (conflict_a)->next)
4209	{
4210	if (allocnos_conflict_by_live_ranges_p (a1: a, a2: conflict_a))
4211	return true;
4212	if (conflict_a == a1)
4213	break;
4214	}
4215	if (a == a2)
4216	break;
4217	}
4218	return false;
4219	}
4220
4221	/* The major function for aggressive allocno coalescing. We coalesce
4222	only spilled allocnos. If some allocnos have been coalesced, we
4223	set up flag allocno_coalesced_p. */
4224	static void
4225	coalesce_allocnos (void)
4226	{
4227	ira_allocno_t a;
4228	ira_copy_t cp, next_cp;
4229	unsigned int j;
4230	int i, n, cp_num, regno;
4231	bitmap_iterator bi;
4232
4233	cp_num = 0;
4234	/* Collect copies. */
4235	EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
4236	{
4237	a = ira_allocnos[j];
4238	regno = ALLOCNO_REGNO (a);
4239	if (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0
4240	|| ira_equiv_no_lvalue_p (regno))
4241	continue;
4242	for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
4243	{
4244	if (cp->first == a)
4245	{
4246	next_cp = cp->next_first_allocno_copy;
4247	regno = ALLOCNO_REGNO (cp->second);
4248	/* For priority coloring we coalesce allocnos only with
4249	the same allocno class not with intersected allocno
4250	classes as it were possible. It is done for
4251	simplicity. */
4252	if ((cp->insn != NULL || cp->constraint_p)
4253	&& ALLOCNO_ASSIGNED_P (cp->second)
4254	&& ALLOCNO_HARD_REGNO (cp->second) < 0
4255	&& ! ira_equiv_no_lvalue_p (regno))
4256	sorted_copies[cp_num++] = cp;
4257	}
4258	else if (cp->second == a)
4259	next_cp = cp->next_second_allocno_copy;
4260	else
4261	gcc_unreachable ();
4262	}
4263	}
4264	qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
4265	/* Coalesced copies, most frequently executed first. */
4266	for (; cp_num != 0;)
4267	{
4268	for (i = 0; i < cp_num; i++)
4269	{
4270	cp = sorted_copies[i];
4271	if (! coalesced_allocno_conflict_p (a1: cp->first, a2: cp->second))
4272	{
4273	allocno_coalesced_p = true;
4274	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4275	fprintf
4276	(stream: ira_dump_file,
4277	format: " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
4278	cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
4279	ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
4280	cp->freq);
4281	merge_allocnos (a1: cp->first, a2: cp->second);
4282	i++;
4283	break;
4284	}
4285	}
4286	/* Collect the rest of copies. */
4287	for (n = 0; i < cp_num; i++)
4288	{
4289	cp = sorted_copies[i];
4290	if (allocno_coalesce_data[ALLOCNO_NUM (cp->first)].first
4291	!= allocno_coalesce_data[ALLOCNO_NUM (cp->second)].first)
4292	sorted_copies[n++] = cp;
4293	}
4294	cp_num = n;
4295	}
4296	}
4297
4298	/* Usage cost and order number of coalesced allocno set to which
4299	given pseudo register belongs to. */
4300	static int *regno_coalesced_allocno_cost;
4301	static int *regno_coalesced_allocno_num;
4302
4303	/* Sort pseudos according frequencies of coalesced allocno sets they
4304	belong to (putting most frequently ones first), and according to
4305	coalesced allocno set order numbers. */
4306	static int
4307	coalesced_pseudo_reg_freq_compare (const void *v1p, const void *v2p)
4308	{
4309	const int regno1 = *(const int *) v1p;
4310	const int regno2 = *(const int *) v2p;
4311	int diff;
4312
4313	if ((diff = (regno_coalesced_allocno_cost[regno2]
4314	- regno_coalesced_allocno_cost[regno1])) != 0)
4315	return diff;
4316	if ((diff = (regno_coalesced_allocno_num[regno1]
4317	- regno_coalesced_allocno_num[regno2])) != 0)
4318	return diff;
4319	return regno1 - regno2;
4320	}
4321
4322	/* Widest width in which each pseudo reg is referred to (via subreg).
4323	It is used for sorting pseudo registers. */
4324	static machine_mode *regno_max_ref_mode;
4325
4326	/* Sort pseudos according their slot numbers (putting ones with
4327	smaller numbers first, or last when the frame pointer is not
4328	needed). */
4329	static int
4330	coalesced_pseudo_reg_slot_compare (const void *v1p, const void *v2p)
4331	{
4332	const int regno1 = *(const int *) v1p;
4333	const int regno2 = *(const int *) v2p;
4334	ira_allocno_t a1 = ira_regno_allocno_map[regno1];
4335	ira_allocno_t a2 = ira_regno_allocno_map[regno2];
4336	int diff, slot_num1, slot_num2;
4337	machine_mode mode1, mode2;
4338
4339	if (a1 == NULL || ALLOCNO_HARD_REGNO (a1) >= 0)
4340	{
4341	if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
4342	return regno1 - regno2;
4343	return 1;
4344	}
4345	else if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
4346	return -1;
4347	slot_num1 = -ALLOCNO_HARD_REGNO (a1);
4348	slot_num2 = -ALLOCNO_HARD_REGNO (a2);
4349	if ((diff = slot_num1 - slot_num2) != 0)
4350	return (frame_pointer_needed
4351	|| (!FRAME_GROWS_DOWNWARD) == STACK_GROWS_DOWNWARD ? diff : -diff);
4352	mode1 = wider_subreg_mode (PSEUDO_REGNO_MODE (regno1),
4353	innermode: regno_max_ref_mode[regno1]);
4354	mode2 = wider_subreg_mode (PSEUDO_REGNO_MODE (regno2),
4355	innermode: regno_max_ref_mode[regno2]);
4356	if ((diff = compare_sizes_for_sort (a: GET_MODE_SIZE (mode: mode2),
4357	b: GET_MODE_SIZE (mode: mode1))) != 0)
4358	return diff;
4359	return regno1 - regno2;
4360	}
4361
4362	/* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
4363	for coalesced allocno sets containing allocnos with their regnos
4364	given in array PSEUDO_REGNOS of length N. */
4365	static void
4366	setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos, int n)
4367	{
4368	int i, num, regno, cost;
4369	ira_allocno_t allocno, a;
4370
4371	for (num = i = 0; i < n; i++)
4372	{
4373	regno = pseudo_regnos[i];
4374	allocno = ira_regno_allocno_map[regno];
4375	if (allocno == NULL)
4376	{
4377	regno_coalesced_allocno_cost[regno] = 0;
4378	regno_coalesced_allocno_num[regno] = ++num;
4379	continue;
4380	}
4381	if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno)
4382	continue;
4383	num++;
4384	for (cost = 0, a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4385	a = ALLOCNO_COALESCE_DATA (a)->next)
4386	{
4387	cost += ALLOCNO_FREQ (a);
4388	if (a == allocno)
4389	break;
4390	}
4391	for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4392	a = ALLOCNO_COALESCE_DATA (a)->next)
4393	{
4394	regno_coalesced_allocno_num[ALLOCNO_REGNO (a)] = num;
4395	regno_coalesced_allocno_cost[ALLOCNO_REGNO (a)] = cost;
4396	if (a == allocno)
4397	break;
4398	}
4399	}
4400	}
4401
4402	/* Collect spilled allocnos representing coalesced allocno sets (the
4403	first coalesced allocno). The collected allocnos are returned
4404	through array SPILLED_COALESCED_ALLOCNOS. The function returns the
4405	number of the collected allocnos. The allocnos are given by their
4406	regnos in array PSEUDO_REGNOS of length N. */
4407	static int
4408	collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n,
4409	ira_allocno_t *spilled_coalesced_allocnos)
4410	{
4411	int i, num, regno;
4412	ira_allocno_t allocno;
4413
4414	for (num = i = 0; i < n; i++)
4415	{
4416	regno = pseudo_regnos[i];
4417	allocno = ira_regno_allocno_map[regno];
4418	if (allocno == NULL || ALLOCNO_HARD_REGNO (allocno) >= 0
4419	|| ALLOCNO_COALESCE_DATA (allocno)->first != allocno)
4420	continue;
4421	spilled_coalesced_allocnos[num++] = allocno;
4422	}
4423	return num;
4424	}
4425
4426	/* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
4427	given slot contains live ranges of coalesced allocnos assigned to
4428	given slot. */
4429	static live_range_t *slot_coalesced_allocnos_live_ranges;
4430
4431	/* Return TRUE if coalesced allocnos represented by ALLOCNO has live
4432	ranges intersected with live ranges of coalesced allocnos assigned
4433	to slot with number N. */
4434	static bool
4435	slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno, int n)
4436	{
4437	ira_allocno_t a;
4438
4439	for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4440	a = ALLOCNO_COALESCE_DATA (a)->next)
4441	{
4442	int i;
4443	int nr = ALLOCNO_NUM_OBJECTS (a);
4444	gcc_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
4445	for (i = 0; i < nr; i++)
4446	{
4447	ira_object_t obj = ALLOCNO_OBJECT (a, i);
4448
4449	if (ira_live_ranges_intersect_p
4450	(slot_coalesced_allocnos_live_ranges[n],
4451	OBJECT_LIVE_RANGES (obj)))
4452	return true;
4453	}
4454	if (a == allocno)
4455	break;
4456	}
4457	return false;
4458	}
4459
4460	/* Update live ranges of slot to which coalesced allocnos represented
4461	by ALLOCNO were assigned. */
4462	static void
4463	setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno)
4464	{
4465	int i, n;
4466	ira_allocno_t a;
4467	live_range_t r;
4468
4469	n = ALLOCNO_COALESCE_DATA (allocno)->temp;
4470	for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4471	a = ALLOCNO_COALESCE_DATA (a)->next)
4472	{
4473	int nr = ALLOCNO_NUM_OBJECTS (a);
4474	gcc_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
4475	for (i = 0; i < nr; i++)
4476	{
4477	ira_object_t obj = ALLOCNO_OBJECT (a, i);
4478
4479	r = ira_copy_live_range_list (OBJECT_LIVE_RANGES (obj));
4480	slot_coalesced_allocnos_live_ranges[n]
4481	= ira_merge_live_ranges
4482	(slot_coalesced_allocnos_live_ranges[n], r);
4483	}
4484	if (a == allocno)
4485	break;
4486	}
4487	}
4488
4489	/* We have coalesced allocnos involving in copies. Coalesce allocnos
4490	further in order to share the same memory stack slot. Allocnos
4491	representing sets of allocnos coalesced before the call are given
4492	in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
4493	some allocnos were coalesced in the function. */
4494	static bool
4495	coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num)
4496	{
4497	int i, j, n, last_coalesced_allocno_num;
4498	ira_allocno_t allocno, a;
4499	bool merged_p = false;
4500	bitmap set_jump_crosses = regstat_get_setjmp_crosses ();
4501
4502	slot_coalesced_allocnos_live_ranges
4503	= (live_range_t *) ira_allocate (sizeof (live_range_t) * ira_allocnos_num);
4504	memset (s: slot_coalesced_allocnos_live_ranges, c: 0,
4505	n: sizeof (live_range_t) * ira_allocnos_num);
4506	last_coalesced_allocno_num = 0;
4507	/* Coalesce non-conflicting spilled allocnos preferring most
4508	frequently used. */
4509	for (i = 0; i < num; i++)
4510	{
4511	allocno = spilled_coalesced_allocnos[i];
4512	if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno
4513	|| bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (allocno))
4514	|| ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno)))
4515	continue;
4516	for (j = 0; j < i; j++)
4517	{
4518	a = spilled_coalesced_allocnos[j];
4519	n = ALLOCNO_COALESCE_DATA (a)->temp;
4520	if (ALLOCNO_COALESCE_DATA (a)->first == a
4521	&& ! bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (a))
4522	&& ! ira_equiv_no_lvalue_p (ALLOCNO_REGNO (a))
4523	&& ! slot_coalesced_allocno_live_ranges_intersect_p (allocno, n))
4524	break;
4525	}
4526	if (j >= i)
4527	{
4528	/* No coalescing: set up number for coalesced allocnos
4529	represented by ALLOCNO. */
4530	ALLOCNO_COALESCE_DATA (allocno)->temp = last_coalesced_allocno_num++;
4531	setup_slot_coalesced_allocno_live_ranges (allocno);
4532	}
4533	else
4534	{
4535	allocno_coalesced_p = true;
4536	merged_p = true;
4537	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4538	fprintf (stream: ira_dump_file,
4539	format: " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
4540	ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno),
4541	ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
4542	ALLOCNO_COALESCE_DATA (allocno)->temp
4543	= ALLOCNO_COALESCE_DATA (a)->temp;
4544	setup_slot_coalesced_allocno_live_ranges (allocno);
4545	merge_allocnos (a1: a, a2: allocno);
4546	ira_assert (ALLOCNO_COALESCE_DATA (a)->first == a);
4547	}
4548	}
4549	for (i = 0; i < ira_allocnos_num; i++)
4550	ira_finish_live_range_list (slot_coalesced_allocnos_live_ranges[i]);
4551	ira_free (addr: slot_coalesced_allocnos_live_ranges);
4552	return merged_p;
4553	}
4554
4555	/* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
4556	subsequent assigning stack slots to them in the reload pass. To do
4557	this we coalesce spilled allocnos first to decrease the number of
4558	memory-memory move insns. This function is called by the
4559	reload. */
4560	void
4561	ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n,
4562	machine_mode *reg_max_ref_mode)
4563	{
4564	int max_regno = max_reg_num ();
4565	int i, regno, num, slot_num;
4566	ira_allocno_t allocno, a;
4567	ira_allocno_iterator ai;
4568	ira_allocno_t *spilled_coalesced_allocnos;
4569
4570	ira_assert (! ira_use_lra_p);
4571
4572	/* Set up allocnos can be coalesced. */
4573	coloring_allocno_bitmap = ira_allocate_bitmap ();
4574	for (i = 0; i < n; i++)
4575	{
4576	regno = pseudo_regnos[i];
4577	allocno = ira_regno_allocno_map[regno];
4578	if (allocno != NULL)
4579	bitmap_set_bit (coloring_allocno_bitmap, ALLOCNO_NUM (allocno));
4580	}
4581	allocno_coalesced_p = false;
4582	processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
4583	allocno_coalesce_data
4584	= (coalesce_data_t) ira_allocate (sizeof (struct coalesce_data)
4585	* ira_allocnos_num);
4586	/* Initialize coalesce data for allocnos. */
4587	FOR_EACH_ALLOCNO (a, ai)
4588	{
4589	ALLOCNO_ADD_DATA (a) = allocno_coalesce_data + ALLOCNO_NUM (a);
4590	ALLOCNO_COALESCE_DATA (a)->first = a;
4591	ALLOCNO_COALESCE_DATA (a)->next = a;
4592	}
4593	coalesce_allocnos ();
4594	ira_free_bitmap (coloring_allocno_bitmap);
4595	regno_coalesced_allocno_cost
4596	= (int *) ira_allocate (max_regno * sizeof (int));
4597	regno_coalesced_allocno_num
4598	= (int *) ira_allocate (max_regno * sizeof (int));
4599	memset (s: regno_coalesced_allocno_num, c: 0, n: max_regno * sizeof (int));
4600	setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
4601	/* Sort regnos according frequencies of the corresponding coalesced
4602	allocno sets. */
4603	qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_freq_compare);
4604	spilled_coalesced_allocnos
4605	= (ira_allocno_t *) ira_allocate (ira_allocnos_num
4606	* sizeof (ira_allocno_t));
4607	/* Collect allocnos representing the spilled coalesced allocno
4608	sets. */
4609	num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
4610	spilled_coalesced_allocnos);
4611	if (flag_ira_share_spill_slots
4612	&& coalesce_spill_slots (spilled_coalesced_allocnos, num))
4613	{
4614	setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
4615	qsort (pseudo_regnos, n, sizeof (int),
4616	coalesced_pseudo_reg_freq_compare);
4617	num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
4618	spilled_coalesced_allocnos);
4619	}
4620	ira_free_bitmap (processed_coalesced_allocno_bitmap);
4621	allocno_coalesced_p = false;
4622	/* Assign stack slot numbers to spilled allocno sets, use smaller
4623	numbers for most frequently used coalesced allocnos. -1 is
4624	reserved for dynamic search of stack slots for pseudos spilled by
4625	the reload. */
4626	slot_num = 1;
4627	for (i = 0; i < num; i++)
4628	{
4629	allocno = spilled_coalesced_allocnos[i];
4630	if (ALLOCNO_COALESCE_DATA (allocno)->first != allocno
4631	|| ALLOCNO_HARD_REGNO (allocno) >= 0
4632	|| ira_equiv_no_lvalue_p (ALLOCNO_REGNO (allocno)))
4633	continue;
4634	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4635	fprintf (stream: ira_dump_file, format: " Slot %d (freq,size):", slot_num);
4636	slot_num++;
4637	for (a = ALLOCNO_COALESCE_DATA (allocno)->next;;
4638	a = ALLOCNO_COALESCE_DATA (a)->next)
4639	{
4640	ira_assert (ALLOCNO_HARD_REGNO (a) < 0);
4641	ALLOCNO_HARD_REGNO (a) = -slot_num;
4642	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4643	{
4644	machine_mode mode = wider_subreg_mode
4645	(PSEUDO_REGNO_MODE (ALLOCNO_REGNO (a)),
4646	innermode: reg_max_ref_mode[ALLOCNO_REGNO (a)]);
4647	fprintf (stream: ira_dump_file, format: " a%dr%d(%d,",
4648	ALLOCNO_NUM (a), ALLOCNO_REGNO (a), ALLOCNO_FREQ (a));
4649	print_dec (value: GET_MODE_SIZE (mode), file: ira_dump_file, sgn: SIGNED);
4650	fprintf (stream: ira_dump_file, format: ")\n");
4651	}
4652
4653	if (a == allocno)
4654	break;
4655	}
4656	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4657	fprintf (stream: ira_dump_file, format: "\n");
4658	}
4659	ira_spilled_reg_stack_slots_num = slot_num - 1;
4660	ira_free (addr: spilled_coalesced_allocnos);
4661	/* Sort regnos according the slot numbers. */
4662	regno_max_ref_mode = reg_max_ref_mode;
4663	qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_slot_compare);
4664	FOR_EACH_ALLOCNO (a, ai)
4665	ALLOCNO_ADD_DATA (a) = NULL;
4666	ira_free (addr: allocno_coalesce_data);
4667	ira_free (addr: regno_coalesced_allocno_num);
4668	ira_free (addr: regno_coalesced_allocno_cost);
4669	}
4670
4671
4672
4673	/* This page contains code used by the reload pass to improve the
4674	final code. */
4675
4676	/* The function is called from reload to mark changes in the
4677	allocation of REGNO made by the reload. Remember that reg_renumber
4678	reflects the change result. */
4679	void
4680	ira_mark_allocation_change (int regno)
4681	{
4682	ira_allocno_t a = ira_regno_allocno_map[regno];
4683	int old_hard_regno, hard_regno, cost;
4684	enum reg_class aclass = ALLOCNO_CLASS (a);
4685
4686	ira_assert (a != NULL);
4687	hard_regno = reg_renumber[regno];
4688	if ((old_hard_regno = ALLOCNO_HARD_REGNO (a)) == hard_regno)
4689	return;
4690	if (old_hard_regno < 0)
4691	cost = -ALLOCNO_MEMORY_COST (a);
4692	else
4693	{
4694	ira_assert (ira_class_hard_reg_index[aclass][old_hard_regno] >= 0);
4695	cost = -(ALLOCNO_HARD_REG_COSTS (a) == NULL
4696	? ALLOCNO_CLASS_COST (a)
4697	: ALLOCNO_HARD_REG_COSTS (a)
4698	[ira_class_hard_reg_index[aclass][old_hard_regno]]);
4699	update_costs_from_copies (allocno: a, decr_p: false, record_p: false);
4700	}
4701	ira_overall_cost -= cost;
4702	ALLOCNO_HARD_REGNO (a) = hard_regno;
4703	if (hard_regno < 0)
4704	{
4705	ALLOCNO_HARD_REGNO (a) = -1;
4706	cost += ALLOCNO_MEMORY_COST (a);
4707	}
4708	else if (ira_class_hard_reg_index[aclass][hard_regno] >= 0)
4709	{
4710	cost += (ALLOCNO_HARD_REG_COSTS (a) == NULL
4711	? ALLOCNO_CLASS_COST (a)
4712	: ALLOCNO_HARD_REG_COSTS (a)
4713	[ira_class_hard_reg_index[aclass][hard_regno]]);
4714	update_costs_from_copies (allocno: a, decr_p: true, record_p: false);
4715	}
4716	else
4717	/* Reload changed class of the allocno. */
4718	cost = 0;
4719	ira_overall_cost += cost;
4720	}
4721
4722	/* This function is called when reload deletes memory-memory move. In
4723	this case we marks that the allocation of the corresponding
4724	allocnos should be not changed in future. Otherwise we risk to get
4725	a wrong code. */
4726	void
4727	ira_mark_memory_move_deletion (int dst_regno, int src_regno)
4728	{
4729	ira_allocno_t dst = ira_regno_allocno_map[dst_regno];
4730	ira_allocno_t src = ira_regno_allocno_map[src_regno];
4731
4732	ira_assert (dst != NULL && src != NULL
4733	&& ALLOCNO_HARD_REGNO (dst) < 0
4734	&& ALLOCNO_HARD_REGNO (src) < 0);
4735	ALLOCNO_DONT_REASSIGN_P (dst) = true;
4736	ALLOCNO_DONT_REASSIGN_P (src) = true;
4737	}
4738
4739	/* Try to assign a hard register (except for FORBIDDEN_REGS) to
4740	allocno A and return TRUE in the case of success. */
4741	static bool
4742	allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs)
4743	{
4744	int hard_regno;
4745	enum reg_class aclass;
4746	int regno = ALLOCNO_REGNO (a);
4747	HARD_REG_SET saved[2];
4748	int i, n;
4749
4750	n = ALLOCNO_NUM_OBJECTS (a);
4751	for (i = 0; i < n; i++)
4752	{
4753	ira_object_t obj = ALLOCNO_OBJECT (a, i);
4754	saved[i] = OBJECT_TOTAL_CONFLICT_HARD_REGS (obj);
4755	OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= forbidden_regs;
4756	if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
4757	OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= ira_need_caller_save_regs (a);
4758	}
4759	ALLOCNO_ASSIGNED_P (a) = false;
4760	aclass = ALLOCNO_CLASS (a);
4761	update_curr_costs (a);
4762	assign_hard_reg (a, retry_p: true);
4763	hard_regno = ALLOCNO_HARD_REGNO (a);
4764	reg_renumber[regno] = hard_regno;
4765	if (hard_regno < 0)
4766	ALLOCNO_HARD_REGNO (a) = -1;
4767	else
4768	{
4769	ira_assert (ira_class_hard_reg_index[aclass][hard_regno] >= 0);
4770	ira_overall_cost
4771	-= (ALLOCNO_MEMORY_COST (a)
4772	- (ALLOCNO_HARD_REG_COSTS (a) == NULL
4773	? ALLOCNO_CLASS_COST (a)
4774	: ALLOCNO_HARD_REG_COSTS (a)[ira_class_hard_reg_index
4775	[aclass][hard_regno]]));
4776	if (ira_need_caller_save_p (a, regno: hard_regno))
4777	{
4778	ira_assert (flag_caller_saves);
4779	caller_save_needed = 1;
4780	}
4781	}
4782
4783	/* If we found a hard register, modify the RTL for the pseudo
4784	register to show the hard register, and mark the pseudo register
4785	live. */
4786	if (reg_renumber[regno] >= 0)
4787	{
4788	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4789	fprintf (stream: ira_dump_file, format: ": reassign to %d\n", reg_renumber[regno]);
4790	SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
4791	mark_home_live (regno);
4792	}
4793	else if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4794	fprintf (stream: ira_dump_file, format: "\n");
4795	for (i = 0; i < n; i++)
4796	{
4797	ira_object_t obj = ALLOCNO_OBJECT (a, i);
4798	OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) = saved[i];
4799	}
4800	return reg_renumber[regno] >= 0;
4801	}
4802
4803	/* Sort pseudos according their usage frequencies (putting most
4804	frequently ones first). */
4805	static int
4806	pseudo_reg_compare (const void *v1p, const void *v2p)
4807	{
4808	int regno1 = *(const int *) v1p;
4809	int regno2 = *(const int *) v2p;
4810	int diff;
4811
4812	if ((diff = REG_FREQ (regno2) - REG_FREQ (regno1)) != 0)
4813	return diff;
4814	return regno1 - regno2;
4815	}
4816
4817	/* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
4818	NUM of them) or spilled pseudos conflicting with pseudos in
4819	SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
4820	allocation has been changed. The function doesn't use
4821	BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
4822	PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
4823	is called by the reload pass at the end of each reload
4824	iteration. */
4825	bool
4826	ira_reassign_pseudos (int *spilled_pseudo_regs, int num,
4827	HARD_REG_SET bad_spill_regs,
4828	HARD_REG_SET *pseudo_forbidden_regs,
4829	HARD_REG_SET *pseudo_previous_regs,
4830	bitmap spilled)
4831	{
4832	int i, n, regno;
4833	bool changed_p;
4834	ira_allocno_t a;
4835	HARD_REG_SET forbidden_regs;
4836	bitmap temp = BITMAP_ALLOC (NULL);
4837
4838	/* Add pseudos which conflict with pseudos already in
4839	SPILLED_PSEUDO_REGS to SPILLED_PSEUDO_REGS. This is preferable
4840	to allocating in two steps as some of the conflicts might have
4841	a higher priority than the pseudos passed in SPILLED_PSEUDO_REGS. */
4842	for (i = 0; i < num; i++)
4843	bitmap_set_bit (temp, spilled_pseudo_regs[i]);
4844
4845	for (i = 0, n = num; i < n; i++)
4846	{
4847	int nr, j;
4848	int regno = spilled_pseudo_regs[i];
4849	bitmap_set_bit (temp, regno);
4850
4851	a = ira_regno_allocno_map[regno];
4852	nr = ALLOCNO_NUM_OBJECTS (a);
4853	for (j = 0; j < nr; j++)
4854	{
4855	ira_object_t conflict_obj;
4856	ira_object_t obj = ALLOCNO_OBJECT (a, j);
4857	ira_object_conflict_iterator oci;
4858
4859	FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
4860	{
4861	ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
4862	if (ALLOCNO_HARD_REGNO (conflict_a) < 0
4863	&& ! ALLOCNO_DONT_REASSIGN_P (conflict_a)
4864	&& bitmap_set_bit (temp, ALLOCNO_REGNO (conflict_a)))
4865	{
4866	spilled_pseudo_regs[num++] = ALLOCNO_REGNO (conflict_a);
4867	/* ?!? This seems wrong. */
4868	bitmap_set_bit (consideration_allocno_bitmap,
4869	ALLOCNO_NUM (conflict_a));
4870	}
4871	}
4872	}
4873	}
4874
4875	if (num > 1)
4876	qsort (spilled_pseudo_regs, num, sizeof (int), pseudo_reg_compare);
4877	changed_p = false;
4878	/* Try to assign hard registers to pseudos from
4879	SPILLED_PSEUDO_REGS. */
4880	for (i = 0; i < num; i++)
4881	{
4882	regno = spilled_pseudo_regs[i];
4883	forbidden_regs = (bad_spill_regs
4884	| pseudo_forbidden_regs[regno]
4885	| pseudo_previous_regs[regno]);
4886	gcc_assert (reg_renumber[regno] < 0);
4887	a = ira_regno_allocno_map[regno];
4888	ira_mark_allocation_change (regno);
4889	ira_assert (reg_renumber[regno] < 0);
4890	if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
4891	fprintf (stream: ira_dump_file,
4892	format: " Try Assign %d(a%d), cost=%d", regno, ALLOCNO_NUM (a),
4893	ALLOCNO_MEMORY_COST (a)
4894	- ALLOCNO_CLASS_COST (a));
4895	allocno_reload_assign (a, forbidden_regs);
4896	if (reg_renumber[regno] >= 0)
4897	{
4898	CLEAR_REGNO_REG_SET (spilled, regno);
4899	changed_p = true;
4900	}
4901	}
4902	BITMAP_FREE (temp);
4903	return changed_p;
4904	}
4905
4906	/* The function is called by reload and returns already allocated
4907	stack slot (if any) for REGNO with given INHERENT_SIZE and
4908	TOTAL_SIZE. In the case of failure to find a slot which can be
4909	used for REGNO, the function returns NULL. */
4910	rtx
4911	ira_reuse_stack_slot (int regno, poly_uint64 inherent_size,
4912	poly_uint64 total_size)
4913	{
4914	unsigned int i;
4915	int slot_num, best_slot_num;
4916	int cost, best_cost;
4917	ira_copy_t cp, next_cp;
4918	ira_allocno_t another_allocno, allocno = ira_regno_allocno_map[regno];
4919	rtx x;
4920	bitmap_iterator bi;
4921	class ira_spilled_reg_stack_slot *slot = NULL;
4922
4923	ira_assert (! ira_use_lra_p);
4924
4925	ira_assert (known_eq (inherent_size, PSEUDO_REGNO_BYTES (regno))
4926	&& known_le (inherent_size, total_size)
4927	&& ALLOCNO_HARD_REGNO (allocno) < 0);
4928	if (! flag_ira_share_spill_slots)
4929	return NULL_RTX;
4930	slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
4931	if (slot_num != -1)
4932	{
4933	slot = &ira_spilled_reg_stack_slots[slot_num];
4934	x = slot->mem;
4935	}
4936	else
4937	{
4938	best_cost = best_slot_num = -1;
4939	x = NULL_RTX;
4940	/* It means that the pseudo was spilled in the reload pass, try
4941	to reuse a slot. */
4942	for (slot_num = 0;
4943	slot_num < ira_spilled_reg_stack_slots_num;
4944	slot_num++)
4945	{
4946	slot = &ira_spilled_reg_stack_slots[slot_num];
4947	if (slot->mem == NULL_RTX)
4948	continue;
4949	if (maybe_lt (a: slot->width, b: total_size)
4950	|| maybe_lt (a: GET_MODE_SIZE (GET_MODE (slot->mem)), b: inherent_size))
4951	continue;
4952
4953	EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
4954	FIRST_PSEUDO_REGISTER, i, bi)
4955	{
4956	another_allocno = ira_regno_allocno_map[i];
4957	if (allocnos_conflict_by_live_ranges_p (a1: allocno,
4958	a2: another_allocno))
4959	goto cont;
4960	}
4961	for (cost = 0, cp = ALLOCNO_COPIES (allocno);
4962	cp != NULL;
4963	cp = next_cp)
4964	{
4965	if (cp->first == allocno)
4966	{
4967	next_cp = cp->next_first_allocno_copy;
4968	another_allocno = cp->second;
4969	}
4970	else if (cp->second == allocno)
4971	{
4972	next_cp = cp->next_second_allocno_copy;
4973	another_allocno = cp->first;
4974	}
4975	else
4976	gcc_unreachable ();
4977	if (cp->insn == NULL_RTX)
4978	continue;
4979	if (bitmap_bit_p (&slot->spilled_regs,
4980	ALLOCNO_REGNO (another_allocno)))
4981	cost += cp->freq;
4982	}
4983	if (cost > best_cost)
4984	{
4985	best_cost = cost;
4986	best_slot_num = slot_num;
4987	}
4988	cont:
4989	;
4990	}
4991	if (best_cost >= 0)
4992	{
4993	slot_num = best_slot_num;
4994	slot = &ira_spilled_reg_stack_slots[slot_num];
4995	SET_REGNO_REG_SET (&slot->spilled_regs, regno);
4996	x = slot->mem;
4997	ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
4998	}
4999	}
5000	if (x != NULL_RTX)
5001	{
5002	ira_assert (known_ge (slot->width, total_size));
5003	#ifdef ENABLE_IRA_CHECKING
5004	EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
5005	FIRST_PSEUDO_REGISTER, i, bi)
5006	{
5007	ira_assert (! conflict_by_live_ranges_p (regno, i));
5008	}
5009	#endif
5010	SET_REGNO_REG_SET (&slot->spilled_regs, regno);
5011	if (internal_flag_ira_verbose > 3 && ira_dump_file)
5012	{
5013	fprintf (stream: ira_dump_file, format: " Assigning %d(freq=%d) slot %d of",
5014	regno, REG_FREQ (regno), slot_num);
5015	EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
5016	FIRST_PSEUDO_REGISTER, i, bi)
5017	{
5018	if ((unsigned) regno != i)
5019	fprintf (stream: ira_dump_file, format: " %d", i);
5020	}
5021	fprintf (stream: ira_dump_file, format: "\n");
5022	}
5023	}
5024	return x;
5025	}
5026
5027	/* This is called by reload every time a new stack slot X with
5028	TOTAL_SIZE was allocated for REGNO. We store this info for
5029	subsequent ira_reuse_stack_slot calls. */
5030	void
5031	ira_mark_new_stack_slot (rtx x, int regno, poly_uint64 total_size)
5032	{
5033	class ira_spilled_reg_stack_slot *slot;
5034	int slot_num;
5035	ira_allocno_t allocno;
5036
5037	ira_assert (! ira_use_lra_p);
5038
5039	ira_assert (known_le (PSEUDO_REGNO_BYTES (regno), total_size));
5040	allocno = ira_regno_allocno_map[regno];
5041	slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
5042	if (slot_num == -1)
5043	{
5044	slot_num = ira_spilled_reg_stack_slots_num++;
5045	ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
5046	}
5047	slot = &ira_spilled_reg_stack_slots[slot_num];
5048	INIT_REG_SET (&slot->spilled_regs);
5049	SET_REGNO_REG_SET (&slot->spilled_regs, regno);
5050	slot->mem = x;
5051	slot->width = total_size;
5052	if (internal_flag_ira_verbose > 3 && ira_dump_file)
5053	fprintf (stream: ira_dump_file, format: " Assigning %d(freq=%d) a new slot %d\n",
5054	regno, REG_FREQ (regno), slot_num);
5055	}
5056
5057
5058	/* Return spill cost for pseudo-registers whose numbers are in array
5059	REGNOS (with a negative number as an end marker) for reload with
5060	given IN and OUT for INSN. Return also number points (through
5061	EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
5062	the register pressure is high, number of references of the
5063	pseudo-registers (through NREFS), the number of psuedo registers
5064	whose allocated register wouldn't need saving in the prologue
5065	(through CALL_USED_COUNT), and the first hard regno occupied by the
5066	pseudo-registers (through FIRST_HARD_REGNO). */
5067	static int
5068	calculate_spill_cost (int *regnos, rtx in, rtx out, rtx_insn *insn,
5069	int *excess_pressure_live_length,
5070	int *nrefs, int *call_used_count, int *first_hard_regno)
5071	{
5072	int i, cost, regno, hard_regno, count, saved_cost;
5073	bool in_p, out_p;
5074	int length;
5075	ira_allocno_t a;
5076
5077	*nrefs = 0;
5078	for (length = count = cost = i = 0;; i++)
5079	{
5080	regno = regnos[i];
5081	if (regno < 0)
5082	break;
5083	*nrefs += REG_N_REFS (regno);
5084	hard_regno = reg_renumber[regno];
5085	ira_assert (hard_regno >= 0);
5086	a = ira_regno_allocno_map[regno];
5087	length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) / ALLOCNO_NUM_OBJECTS (a);
5088	cost += ALLOCNO_MEMORY_COST (a) - ALLOCNO_CLASS_COST (a);
5089	if (in_hard_reg_set_p (crtl->abi->full_reg_clobbers (),
5090	ALLOCNO_MODE (a), regno: hard_regno))
5091	count++;
5092	in_p = in && REG_P (in) && (int) REGNO (in) == hard_regno;
5093	out_p = out && REG_P (out) && (int) REGNO (out) == hard_regno;
5094	if ((in_p || out_p)
5095	&& find_regno_note (insn, REG_DEAD, hard_regno) != NULL_RTX)
5096	{
5097	saved_cost = 0;
5098	if (in_p)
5099	saved_cost += ira_memory_move_cost
5100	[ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)][1];
5101	if (out_p)
5102	saved_cost
5103	+= ira_memory_move_cost
5104	[ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)][0];
5105	cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)) * saved_cost;
5106	}
5107	}
5108	*excess_pressure_live_length = length;
5109	*call_used_count = count;
5110	hard_regno = -1;
5111	if (regnos[0] >= 0)
5112	{
5113	hard_regno = reg_renumber[regnos[0]];
5114	}
5115	*first_hard_regno = hard_regno;
5116	return cost;
5117	}
5118
5119	/* Return TRUE if spilling pseudo-registers whose numbers are in array
5120	REGNOS is better than spilling pseudo-registers with numbers in
5121	OTHER_REGNOS for reload with given IN and OUT for INSN. The
5122	function used by the reload pass to make better register spilling
5123	decisions. */
5124	bool
5125	ira_better_spill_reload_regno_p (int *regnos, int *other_regnos,
5126	rtx in, rtx out, rtx_insn *insn)
5127	{
5128	int cost, other_cost;
5129	int length, other_length;
5130	int nrefs, other_nrefs;
5131	int call_used_count, other_call_used_count;
5132	int hard_regno, other_hard_regno;
5133
5134	cost = calculate_spill_cost (regnos, in, out, insn,
5135	excess_pressure_live_length: &length, nrefs: &nrefs, call_used_count: &call_used_count, first_hard_regno: &hard_regno);
5136	other_cost = calculate_spill_cost (regnos: other_regnos, in, out, insn,
5137	excess_pressure_live_length: &other_length, nrefs: &other_nrefs,
5138	call_used_count: &other_call_used_count,
5139	first_hard_regno: &other_hard_regno);
5140	if (nrefs == 0 && other_nrefs != 0)
5141	return true;
5142	if (nrefs != 0 && other_nrefs == 0)
5143	return false;
5144	if (cost != other_cost)
5145	return cost < other_cost;
5146	if (length != other_length)
5147	return length > other_length;
5148	#ifdef REG_ALLOC_ORDER
5149	if (hard_regno >= 0 && other_hard_regno >= 0)
5150	return (inv_reg_alloc_order[hard_regno]
5151	< inv_reg_alloc_order[other_hard_regno]);
5152	#else
5153	if (call_used_count != other_call_used_count)
5154	return call_used_count > other_call_used_count;
5155	#endif
5156	return false;
5157	}
5158
5159
5160
5161	/* Allocate and initialize data necessary for assign_hard_reg. */
5162	void
5163	ira_initiate_assign (void)
5164	{
5165	sorted_allocnos
5166	= (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
5167	* ira_allocnos_num);
5168	consideration_allocno_bitmap = ira_allocate_bitmap ();
5169	initiate_cost_update ();
5170	allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
5171	sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num
5172	* sizeof (ira_copy_t));
5173	}
5174
5175	/* Deallocate data used by assign_hard_reg. */
5176	void
5177	ira_finish_assign (void)
5178	{
5179	ira_free (addr: sorted_allocnos);
5180	ira_free_bitmap (consideration_allocno_bitmap);
5181	finish_cost_update ();
5182	ira_free (addr: allocno_priorities);
5183	ira_free (addr: sorted_copies);
5184	}
5185
5186
5187
5188	/* Entry function doing color-based register allocation. */
5189	static void
5190	color (void)
5191	{
5192	allocno_stack_vec.create (nelems: ira_allocnos_num);
5193	memset (s: allocated_hardreg_p, c: 0, n: sizeof (allocated_hardreg_p));
5194	ira_initiate_assign ();
5195	do_coloring ();
5196	ira_finish_assign ();
5197	allocno_stack_vec.release ();
5198	move_spill_restore ();
5199	}
5200
5201
5202
5203	/* This page contains a simple register allocator without usage of
5204	allocno conflicts. This is used for fast allocation for -O0. */
5205
5206	/* Do register allocation by not using allocno conflicts. It uses
5207	only allocno live ranges. The algorithm is close to Chow's
5208	priority coloring. */
5209	static void
5210	fast_allocation (void)
5211	{
5212	int i, j, k, num, class_size, hard_regno, best_hard_regno, cost, min_cost;
5213	int *costs;
5214	#ifdef STACK_REGS
5215	bool no_stack_reg_p;
5216	#endif
5217	enum reg_class aclass;
5218	machine_mode mode;
5219	ira_allocno_t a;
5220	ira_allocno_iterator ai;
5221	live_range_t r;
5222	HARD_REG_SET conflict_hard_regs, *used_hard_regs;
5223
5224	sorted_allocnos = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
5225	* ira_allocnos_num);
5226	num = 0;
5227	FOR_EACH_ALLOCNO (a, ai)
5228	sorted_allocnos[num++] = a;
5229	allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
5230	setup_allocno_priorities (consideration_allocnos: sorted_allocnos, n: num);
5231	used_hard_regs = (HARD_REG_SET *) ira_allocate (sizeof (HARD_REG_SET)
5232	* ira_max_point);
5233	for (i = 0; i < ira_max_point; i++)
5234	CLEAR_HARD_REG_SET (set&: used_hard_regs[i]);
5235	qsort (sorted_allocnos, num, sizeof (ira_allocno_t),
5236	allocno_priority_compare_func);
5237	for (i = 0; i < num; i++)
5238	{
5239	int nr, l;
5240
5241	a = sorted_allocnos[i];
5242	nr = ALLOCNO_NUM_OBJECTS (a);
5243	CLEAR_HARD_REG_SET (set&: conflict_hard_regs);
5244	for (l = 0; l < nr; l++)
5245	{
5246	ira_object_t obj = ALLOCNO_OBJECT (a, l);
5247	conflict_hard_regs |= OBJECT_CONFLICT_HARD_REGS (obj);
5248	for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
5249	for (j = r->start; j <= r->finish; j++)
5250	conflict_hard_regs |= used_hard_regs[j];
5251	}
5252	aclass = ALLOCNO_CLASS (a);
5253	ALLOCNO_ASSIGNED_P (a) = true;
5254	ALLOCNO_HARD_REGNO (a) = -1;
5255	if (hard_reg_set_subset_p (reg_class_contents[aclass],
5256	y: conflict_hard_regs))
5257	continue;
5258	mode = ALLOCNO_MODE (a);
5259	#ifdef STACK_REGS
5260	no_stack_reg_p = ALLOCNO_NO_STACK_REG_P (a);
5261	#endif
5262	class_size = ira_class_hard_regs_num[aclass];
5263	costs = ALLOCNO_HARD_REG_COSTS (a);
5264	min_cost = INT_MAX;
5265	best_hard_regno = -1;
5266	for (j = 0; j < class_size; j++)
5267	{
5268	hard_regno = ira_class_hard_regs[aclass][j];
5269	#ifdef STACK_REGS
5270	if (no_stack_reg_p && FIRST_STACK_REG <= hard_regno
5271	&& hard_regno <= LAST_STACK_REG)
5272	continue;
5273	#endif
5274	if (ira_hard_reg_set_intersection_p (hard_regno, mode, hard_regset: conflict_hard_regs)
5275	|| (TEST_HARD_REG_BIT
5276	(ira_prohibited_class_mode_regs[aclass][mode], bit: hard_regno)))
5277	continue;
5278	if (costs == NULL)
5279	{
5280	best_hard_regno = hard_regno;
5281	break;
5282	}
5283	cost = costs[j];
5284	if (min_cost > cost)
5285	{
5286	min_cost = cost;
5287	best_hard_regno = hard_regno;
5288	}
5289	}
5290	if (best_hard_regno < 0)
5291	continue;
5292	ALLOCNO_HARD_REGNO (a) = hard_regno = best_hard_regno;
5293	for (l = 0; l < nr; l++)
5294	{
5295	ira_object_t obj = ALLOCNO_OBJECT (a, l);
5296	for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
5297	for (k = r->start; k <= r->finish; k++)
5298	used_hard_regs[k] |= ira_reg_mode_hard_regset[hard_regno][mode];
5299	}
5300	}
5301	ira_free (addr: sorted_allocnos);
5302	ira_free (addr: used_hard_regs);
5303	ira_free (addr: allocno_priorities);
5304	if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
5305	ira_print_disposition (ira_dump_file);
5306	}
5307
5308
5309
5310	/* Entry function doing coloring. */
5311	void
5312	ira_color (void)
5313	{
5314	ira_allocno_t a;
5315	ira_allocno_iterator ai;
5316
5317	/* Setup updated costs. */
5318	FOR_EACH_ALLOCNO (a, ai)
5319	{
5320	ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
5321	ALLOCNO_UPDATED_CLASS_COST (a) = ALLOCNO_CLASS_COST (a);
5322	}
5323	if (ira_conflicts_p)
5324	color ();
5325	else
5326	fast_allocation ();
5327	}
5328