1	/* Building internal representation for IRA.
2	Copyright (C) 2006-2024 Free Software Foundation, Inc.
3	Contributed by Vladimir Makarov <vmakarov@redhat.com>.
4
5	This file is part of GCC.
6
7	GCC is free software; you can redistribute it and/or modify it under
8	the terms of the GNU General Public License as published by the Free
9	Software Foundation; either version 3, or (at your option) any later
10	version.
11
12	GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13	WARRANTY; without even the implied warranty of MERCHANTABILITY or
14	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15	for more details.
16
17	You should have received a copy of the GNU General Public License
18	along with GCC; see the file COPYING3. If not see
19	<http://www.gnu.org/licenses/>. */
20
21	#include "config.h"
22	#include "system.h"
23	#include "coretypes.h"
24	#include "backend.h"
25	#include "target.h"
26	#include "rtl.h"
27	#include "predict.h"
28	#include "df.h"
29	#include "insn-config.h"
30	#include "regs.h"
31	#include "memmodel.h"
32	#include "ira.h"
33	#include "ira-int.h"
34	#include "sparseset.h"
35	#include "cfgloop.h"
36
37	static ira_copy_t find_allocno_copy (ira_allocno_t, ira_allocno_t, rtx_insn *,
38	ira_loop_tree_node_t);
39
40	/* The root of the loop tree corresponding to the all function. */
41	ira_loop_tree_node_t ira_loop_tree_root;
42
43	/* Height of the loop tree. */
44	int ira_loop_tree_height;
45
46	/* All nodes representing basic blocks are referred through the
47	following array. We cannot use basic block member `aux' for this
48	because it is used for insertion of insns on edges. */
49	ira_loop_tree_node_t ira_bb_nodes;
50
51	/* All nodes representing loops are referred through the following
52	array. */
53	ira_loop_tree_node_t ira_loop_nodes;
54
55	/* And size of the ira_loop_nodes array. */
56	unsigned int ira_loop_nodes_count;
57
58	/* Map regno -> allocnos with given regno (see comments for
59	allocno member `next_regno_allocno'). */
60	ira_allocno_t *ira_regno_allocno_map;
61
62	/* Array of references to all allocnos. The order number of the
63	allocno corresponds to the index in the array. Removed allocnos
64	have NULL element value. */
65	ira_allocno_t *ira_allocnos;
66
67	/* Sizes of the previous array. */
68	int ira_allocnos_num;
69
70	/* Count of conflict record structures we've created, used when creating
71	a new conflict id. */
72	int ira_objects_num;
73
74	/* Map a conflict id to its conflict record. */
75	ira_object_t *ira_object_id_map;
76
77	/* Array of references to all allocno preferences. The order number
78	of the preference corresponds to the index in the array. */
79	ira_pref_t *ira_prefs;
80
81	/* Size of the previous array. */
82	int ira_prefs_num;
83
84	/* Array of references to all copies. The order number of the copy
85	corresponds to the index in the array. Removed copies have NULL
86	element value. */
87	ira_copy_t *ira_copies;
88
89	/* Size of the previous array. */
90	int ira_copies_num;
91
92
93
94	/* LAST_BASIC_BLOCK before generating additional insns because of live
95	range splitting. Emitting insns on a critical edge creates a new
96	basic block. */
97	static int last_basic_block_before_change;
98
99	/* Initialize some members in loop tree node NODE. Use LOOP_NUM for
100	the member loop_num. */
101	static void
102	init_loop_tree_node (struct ira_loop_tree_node *node, int loop_num)
103	{
104	int max_regno = max_reg_num ();
105
106	node->regno_allocno_map
107	= (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t) * max_regno);
108	memset (s: node->regno_allocno_map, c: 0, n: sizeof (ira_allocno_t) * max_regno);
109	memset (s: node->reg_pressure, c: 0, n: sizeof (node->reg_pressure));
110	node->all_allocnos = ira_allocate_bitmap ();
111	node->modified_regnos = ira_allocate_bitmap ();
112	node->border_allocnos = ira_allocate_bitmap ();
113	node->local_copies = ira_allocate_bitmap ();
114	node->loop_num = loop_num;
115	node->children = NULL;
116	node->subloops = NULL;
117	}
118
119
120	/* The following function allocates the loop tree nodes. If
121	CURRENT_LOOPS is NULL, the nodes corresponding to the loops (except
122	the root which corresponds the all function) will be not allocated
123	but nodes will still be allocated for basic blocks. */
124	static void
125	create_loop_tree_nodes (void)
126	{
127	unsigned int i, j;
128	bool skip_p;
129	edge_iterator ei;
130	edge e;
131	loop_p loop;
132
133	ira_bb_nodes
134	= ((struct ira_loop_tree_node *)
135	ira_allocate (sizeof (struct ira_loop_tree_node)
136	* last_basic_block_for_fn (cfun)));
137	last_basic_block_before_change = last_basic_block_for_fn (cfun);
138	for (i = 0; i < (unsigned int) last_basic_block_for_fn (cfun); i++)
139	{
140	ira_bb_nodes[i].regno_allocno_map = NULL;
141	memset (s: ira_bb_nodes[i].reg_pressure, c: 0,
142	n: sizeof (ira_bb_nodes[i].reg_pressure));
143	ira_bb_nodes[i].all_allocnos = NULL;
144	ira_bb_nodes[i].modified_regnos = NULL;
145	ira_bb_nodes[i].border_allocnos = NULL;
146	ira_bb_nodes[i].local_copies = NULL;
147	}
148	if (current_loops == NULL)
149	{
150	ira_loop_nodes_count = 1;
151	ira_loop_nodes = ((struct ira_loop_tree_node *)
152	ira_allocate (sizeof (struct ira_loop_tree_node)));
153	init_loop_tree_node (node: ira_loop_nodes, loop_num: 0);
154	return;
155	}
156	ira_loop_nodes_count = number_of_loops (cfun);
157	ira_loop_nodes = ((struct ira_loop_tree_node *)
158	ira_allocate (sizeof (struct ira_loop_tree_node)
159	* ira_loop_nodes_count));
160	FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
161	{
162	if (loop_outer (loop) != NULL)
163	{
164	ira_loop_nodes[i].regno_allocno_map = NULL;
165	skip_p = false;
166	FOR_EACH_EDGE (e, ei, loop->header->preds)
167	if (e->src != loop->latch
168	&& (e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
169	{
170	skip_p = true;
171	break;
172	}
173	if (skip_p)
174	continue;
175	auto_vec<edge> edges = get_loop_exit_edges (loop);
176	FOR_EACH_VEC_ELT (edges, j, e)
177	if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
178	{
179	skip_p = true;
180	break;
181	}
182	if (skip_p)
183	continue;
184	}
185	init_loop_tree_node (node: &ira_loop_nodes[i], loop_num: loop->num);
186	}
187	}
188
189	/* The function returns TRUE if there are more one allocation
190	region. */
191	static bool
192	more_one_region_p (void)
193	{
194	unsigned int i;
195	loop_p loop;
196
197	if (current_loops != NULL)
198	FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
199	if (ira_loop_nodes[i].regno_allocno_map != NULL
200	&& ira_loop_tree_root != &ira_loop_nodes[i])
201	return true;
202	return false;
203	}
204
205	/* Free the loop tree node of a loop. */
206	static void
207	finish_loop_tree_node (ira_loop_tree_node_t loop)
208	{
209	if (loop->regno_allocno_map != NULL)
210	{
211	ira_assert (loop->bb == NULL);
212	ira_free_bitmap (loop->local_copies);
213	ira_free_bitmap (loop->border_allocnos);
214	ira_free_bitmap (loop->modified_regnos);
215	ira_free_bitmap (loop->all_allocnos);
216	ira_free (addr: loop->regno_allocno_map);
217	loop->regno_allocno_map = NULL;
218	}
219	}
220
221	/* Free the loop tree nodes. */
222	static void
223	finish_loop_tree_nodes (void)
224	{
225	unsigned int i;
226
227	for (i = 0; i < ira_loop_nodes_count; i++)
228	finish_loop_tree_node (loop: &ira_loop_nodes[i]);
229	ira_free (addr: ira_loop_nodes);
230	for (i = 0; i < (unsigned int) last_basic_block_before_change; i++)
231	{
232	if (ira_bb_nodes[i].local_copies != NULL)
233	ira_free_bitmap (ira_bb_nodes[i].local_copies);
234	if (ira_bb_nodes[i].border_allocnos != NULL)
235	ira_free_bitmap (ira_bb_nodes[i].border_allocnos);
236	if (ira_bb_nodes[i].modified_regnos != NULL)
237	ira_free_bitmap (ira_bb_nodes[i].modified_regnos);
238	if (ira_bb_nodes[i].all_allocnos != NULL)
239	ira_free_bitmap (ira_bb_nodes[i].all_allocnos);
240	if (ira_bb_nodes[i].regno_allocno_map != NULL)
241	ira_free (addr: ira_bb_nodes[i].regno_allocno_map);
242	}
243	ira_free (addr: ira_bb_nodes);
244	}
245
246
247
248	/* The following recursive function adds LOOP to the loop tree
249	hierarchy. LOOP is added only once. If LOOP is NULL we adding
250	loop designating the whole function when CFG loops are not
251	built. */
252	static void
253	add_loop_to_tree (class loop *loop)
254	{
255	int loop_num;
256	class loop *parent;
257	ira_loop_tree_node_t loop_node, parent_node;
258
259	/* We cannot use loop node access macros here because of potential
260	checking and because the nodes are not initialized enough
261	yet. */
262	if (loop != NULL && loop_outer (loop) != NULL)
263	add_loop_to_tree (loop: loop_outer (loop));
264	loop_num = loop != NULL ? loop->num : 0;
265	if (ira_loop_nodes[loop_num].regno_allocno_map != NULL
266	&& ira_loop_nodes[loop_num].children == NULL)
267	{
268	/* We have not added loop node to the tree yet. */
269	loop_node = &ira_loop_nodes[loop_num];
270	loop_node->loop = loop;
271	loop_node->bb = NULL;
272	if (loop == NULL)
273	parent = NULL;
274	else
275	{
276	for (parent = loop_outer (loop);
277	parent != NULL;
278	parent = loop_outer (loop: parent))
279	if (ira_loop_nodes[parent->num].regno_allocno_map != NULL)
280	break;
281	}
282	if (parent == NULL)
283	{
284	loop_node->next = NULL;
285	loop_node->subloop_next = NULL;
286	loop_node->parent = NULL;
287	}
288	else
289	{
290	parent_node = &ira_loop_nodes[parent->num];
291	loop_node->next = parent_node->children;
292	parent_node->children = loop_node;
293	loop_node->subloop_next = parent_node->subloops;
294	parent_node->subloops = loop_node;
295	loop_node->parent = parent_node;
296	}
297	}
298	}
299
300	/* The following recursive function sets up levels of nodes of the
301	tree given its root LOOP_NODE. The enumeration starts with LEVEL.
302	The function returns maximal value of level in the tree + 1. */
303	static int
304	setup_loop_tree_level (ira_loop_tree_node_t loop_node, int level)
305	{
306	int height, max_height;
307	ira_loop_tree_node_t subloop_node;
308
309	ira_assert (loop_node->bb == NULL);
310	loop_node->level = level;
311	max_height = level + 1;
312	for (subloop_node = loop_node->subloops;
313	subloop_node != NULL;
314	subloop_node = subloop_node->subloop_next)
315	{
316	ira_assert (subloop_node->bb == NULL);
317	height = setup_loop_tree_level (loop_node: subloop_node, level: level + 1);
318	if (height > max_height)
319	max_height = height;
320	}
321	return max_height;
322	}
323
324	/* Create the loop tree. The algorithm is designed to provide correct
325	order of loops (they are ordered by their last loop BB) and basic
326	blocks in the chain formed by member next. */
327	static void
328	form_loop_tree (void)
329	{
330	basic_block bb;
331	class loop *parent;
332	ira_loop_tree_node_t bb_node, loop_node;
333
334	/* We cannot use loop/bb node access macros because of potential
335	checking and because the nodes are not initialized enough
336	yet. */
337	FOR_EACH_BB_FN (bb, cfun)
338	{
339	bb_node = &ira_bb_nodes[bb->index];
340	bb_node->bb = bb;
341	bb_node->loop = NULL;
342	bb_node->subloops = NULL;
343	bb_node->children = NULL;
344	bb_node->subloop_next = NULL;
345	bb_node->next = NULL;
346	if (current_loops == NULL)
347	parent = NULL;
348	else
349	{
350	for (parent = bb->loop_father;
351	parent != NULL;
352	parent = loop_outer (loop: parent))
353	if (ira_loop_nodes[parent->num].regno_allocno_map != NULL)
354	break;
355	}
356	add_loop_to_tree (loop: parent);
357	loop_node = &ira_loop_nodes[parent == NULL ? 0 : parent->num];
358	bb_node->next = loop_node->children;
359	bb_node->parent = loop_node;
360	loop_node->children = bb_node;
361	}
362	ira_loop_tree_root = IRA_LOOP_NODE_BY_INDEX (0);
363	ira_loop_tree_height = setup_loop_tree_level (loop_node: ira_loop_tree_root, level: 0);
364	ira_assert (ira_loop_tree_root->regno_allocno_map != NULL);
365	}
366
367
368
369	/* Rebuild IRA_REGNO_ALLOCNO_MAP and REGNO_ALLOCNO_MAPs of the loop
370	tree nodes. */
371	static void
372	rebuild_regno_allocno_maps (void)
373	{
374	unsigned int l;
375	int max_regno, regno;
376	ira_allocno_t a;
377	ira_loop_tree_node_t loop_tree_node;
378	loop_p loop;
379	ira_allocno_iterator ai;
380
381	ira_assert (current_loops != NULL);
382	max_regno = max_reg_num ();
383	FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), l, loop)
384	if (ira_loop_nodes[l].regno_allocno_map != NULL)
385	{
386	ira_free (addr: ira_loop_nodes[l].regno_allocno_map);
387	ira_loop_nodes[l].regno_allocno_map
388	= (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
389	* max_regno);
390	memset (s: ira_loop_nodes[l].regno_allocno_map, c: 0,
391	n: sizeof (ira_allocno_t) * max_regno);
392	}
393	ira_free (addr: ira_regno_allocno_map);
394	ira_regno_allocno_map
395	= (ira_allocno_t *) ira_allocate (max_regno * sizeof (ira_allocno_t));
396	memset (s: ira_regno_allocno_map, c: 0, n: max_regno * sizeof (ira_allocno_t));
397	FOR_EACH_ALLOCNO (a, ai)
398	{
399	if (ALLOCNO_CAP_MEMBER (a) != NULL)
400	/* Caps are not in the regno allocno maps. */
401	continue;
402	regno = ALLOCNO_REGNO (a);
403	loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
404	ALLOCNO_NEXT_REGNO_ALLOCNO (a) = ira_regno_allocno_map[regno];
405	ira_regno_allocno_map[regno] = a;
406	if (loop_tree_node->regno_allocno_map[regno] == NULL)
407	/* Remember that we can create temporary allocnos to break
408	cycles in register shuffle. */
409	loop_tree_node->regno_allocno_map[regno] = a;
410	}
411	}
412
413
414	/* Pools for allocnos, allocno live ranges and objects. */
415	static object_allocator<live_range> live_range_pool ("live ranges");
416	static object_allocator<ira_allocno> allocno_pool ("allocnos");
417	static object_allocator<ira_object> object_pool ("objects");
418
419	/* Vec containing references to all created allocnos. It is a
420	container of array allocnos. */
421	static vec<ira_allocno_t> allocno_vec;
422
423	/* Vec containing references to all created ira_objects. It is a
424	container of ira_object_id_map. */
425	static vec<ira_object_t> ira_object_id_map_vec;
426
427	/* Initialize data concerning allocnos. */
428	static void
429	initiate_allocnos (void)
430	{
431	allocno_vec.create (nelems: max_reg_num () * 2);
432	ira_allocnos = NULL;
433	ira_allocnos_num = 0;
434	ira_objects_num = 0;
435	ira_object_id_map_vec.create (nelems: max_reg_num () * 2);
436	ira_object_id_map = NULL;
437	ira_regno_allocno_map
438	= (ira_allocno_t *) ira_allocate (max_reg_num ()
439	* sizeof (ira_allocno_t));
440	memset (s: ira_regno_allocno_map, c: 0, n: max_reg_num () * sizeof (ira_allocno_t));
441	}
442
443	/* Create and return an object corresponding to a new allocno A. */
444	static ira_object_t
445	ira_create_object (ira_allocno_t a, int subword)
446	{
447	enum reg_class aclass = ALLOCNO_CLASS (a);
448	ira_object_t obj = object_pool.allocate ();
449
450	OBJECT_ALLOCNO (obj) = a;
451	OBJECT_SUBWORD (obj) = subword;
452	OBJECT_CONFLICT_ID (obj) = ira_objects_num;
453	OBJECT_CONFLICT_VEC_P (obj) = false;
454	OBJECT_CONFLICT_ARRAY (obj) = NULL;
455	OBJECT_NUM_CONFLICTS (obj) = 0;
456	OBJECT_CONFLICT_HARD_REGS (obj) = ira_no_alloc_regs;
457	OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) = ira_no_alloc_regs;
458	OBJECT_CONFLICT_HARD_REGS (obj) |= ~reg_class_contents[aclass];
459	OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= ~reg_class_contents[aclass];
460	OBJECT_MIN (obj) = INT_MAX;
461	OBJECT_MAX (obj) = -1;
462	OBJECT_LIVE_RANGES (obj) = NULL;
463
464	ira_object_id_map_vec.safe_push (obj);
465	ira_object_id_map
466	= ira_object_id_map_vec.address ();
467	ira_objects_num = ira_object_id_map_vec.length ();
468
469	return obj;
470	}
471
472	/* Create and return the allocno corresponding to REGNO in
473	LOOP_TREE_NODE. Add the allocno to the list of allocnos with the
474	same regno if CAP_P is FALSE. */
475	ira_allocno_t
476	ira_create_allocno (int regno, bool cap_p,
477	ira_loop_tree_node_t loop_tree_node)
478	{
479	ira_allocno_t a;
480
481	a = allocno_pool.allocate ();
482	ALLOCNO_REGNO (a) = regno;
483	ALLOCNO_LOOP_TREE_NODE (a) = loop_tree_node;
484	if (! cap_p)
485	{
486	ALLOCNO_NEXT_REGNO_ALLOCNO (a) = ira_regno_allocno_map[regno];
487	ira_regno_allocno_map[regno] = a;
488	if (loop_tree_node->regno_allocno_map[regno] == NULL)
489	/* Remember that we can create temporary allocnos to break
490	cycles in register shuffle on region borders (see
491	ira-emit.cc). */
492	loop_tree_node->regno_allocno_map[regno] = a;
493	}
494	ALLOCNO_CAP (a) = NULL;
495	ALLOCNO_CAP_MEMBER (a) = NULL;
496	ALLOCNO_NUM (a) = ira_allocnos_num;
497	bitmap_set_bit (loop_tree_node->all_allocnos, ALLOCNO_NUM (a));
498	ALLOCNO_NREFS (a) = 0;
499	ALLOCNO_FREQ (a) = 0;
500	ALLOCNO_MIGHT_CONFLICT_WITH_PARENT_P (a) = false;
501	ALLOCNO_SET_REGISTER_FILTERS (a, 0);
502	ALLOCNO_HARD_REGNO (a) = -1;
503	ALLOCNO_CALL_FREQ (a) = 0;
504	ALLOCNO_CALLS_CROSSED_NUM (a) = 0;
505	ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a) = 0;
506	ALLOCNO_CROSSED_CALLS_ABIS (a) = 0;
507	CLEAR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a));
508	#ifdef STACK_REGS
509	ALLOCNO_NO_STACK_REG_P (a) = false;
510	ALLOCNO_TOTAL_NO_STACK_REG_P (a) = false;
511	#endif
512	ALLOCNO_DONT_REASSIGN_P (a) = false;
513	ALLOCNO_BAD_SPILL_P (a) = false;
514	ALLOCNO_ASSIGNED_P (a) = false;
515	ALLOCNO_MODE (a) = (regno < 0 ? VOIDmode : PSEUDO_REGNO_MODE (regno));
516	ALLOCNO_WMODE (a) = ALLOCNO_MODE (a);
517	ALLOCNO_PREFS (a) = NULL;
518	ALLOCNO_COPIES (a) = NULL;
519	ALLOCNO_HARD_REG_COSTS (a) = NULL;
520	ALLOCNO_CONFLICT_HARD_REG_COSTS (a) = NULL;
521	ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
522	ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
523	ALLOCNO_CLASS (a) = NO_REGS;
524	ALLOCNO_UPDATED_CLASS_COST (a) = 0;
525	ALLOCNO_CLASS_COST (a) = 0;
526	ALLOCNO_MEMORY_COST (a) = 0;
527	ALLOCNO_UPDATED_MEMORY_COST (a) = 0;
528	ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) = 0;
529	ALLOCNO_NUM_OBJECTS (a) = 0;
530
531	ALLOCNO_ADD_DATA (a) = NULL;
532	allocno_vec.safe_push (obj: a);
533	ira_allocnos = allocno_vec.address ();
534	ira_allocnos_num = allocno_vec.length ();
535
536	return a;
537	}
538
539	/* Set up register class for A and update its conflict hard
540	registers. */
541	void
542	ira_set_allocno_class (ira_allocno_t a, enum reg_class aclass)
543	{
544	ira_allocno_object_iterator oi;
545	ira_object_t obj;
546
547	ALLOCNO_CLASS (a) = aclass;
548	FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
549	{
550	OBJECT_CONFLICT_HARD_REGS (obj) |= ~reg_class_contents[aclass];
551	OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= ~reg_class_contents[aclass];
552	}
553	}
554
555	/* Determine the number of objects we should associate with allocno A
556	and allocate them. */
557	void
558	ira_create_allocno_objects (ira_allocno_t a)
559	{
560	machine_mode mode = ALLOCNO_MODE (a);
561	enum reg_class aclass = ALLOCNO_CLASS (a);
562	int n = ira_reg_class_max_nregs[aclass][mode];
563	int i;
564
565	if (n != 2 || maybe_ne (a: GET_MODE_SIZE (mode), b: n * UNITS_PER_WORD))
566	n = 1;
567
568	ALLOCNO_NUM_OBJECTS (a) = n;
569	for (i = 0; i < n; i++)
570	ALLOCNO_OBJECT (a, i) = ira_create_object (a, subword: i);
571	}
572
573	/* For each allocno, set ALLOCNO_NUM_OBJECTS and create the
574	ALLOCNO_OBJECT structures. This must be called after the allocno
575	classes are known. */
576	static void
577	create_allocno_objects (void)
578	{
579	ira_allocno_t a;
580	ira_allocno_iterator ai;
581
582	FOR_EACH_ALLOCNO (a, ai)
583	ira_create_allocno_objects (a);
584	}
585
586	/* Merge hard register conflict information for all objects associated with
587	allocno TO into the corresponding objects associated with FROM.
588	If TOTAL_ONLY is true, we only merge OBJECT_TOTAL_CONFLICT_HARD_REGS. */
589	static void
590	merge_hard_reg_conflicts (ira_allocno_t from, ira_allocno_t to,
591	bool total_only)
592	{
593	int i;
594	gcc_assert (ALLOCNO_NUM_OBJECTS (to) == ALLOCNO_NUM_OBJECTS (from));
595	for (i = 0; i < ALLOCNO_NUM_OBJECTS (to); i++)
596	{
597	ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
598	ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
599
600	if (!total_only)
601	OBJECT_CONFLICT_HARD_REGS (to_obj)
602	|= OBJECT_CONFLICT_HARD_REGS (from_obj);
603	OBJECT_TOTAL_CONFLICT_HARD_REGS (to_obj)
604	|= OBJECT_TOTAL_CONFLICT_HARD_REGS (from_obj);
605	}
606	#ifdef STACK_REGS
607	if (!total_only && ALLOCNO_NO_STACK_REG_P (from))
608	ALLOCNO_NO_STACK_REG_P (to) = true;
609	if (ALLOCNO_TOTAL_NO_STACK_REG_P (from))
610	ALLOCNO_TOTAL_NO_STACK_REG_P (to) = true;
611	#endif
612	}
613
614	/* Update hard register conflict information for all objects associated with
615	A to include the regs in SET. */
616	void
617	ior_hard_reg_conflicts (ira_allocno_t a, const_hard_reg_set set)
618	{
619	ira_allocno_object_iterator i;
620	ira_object_t obj;
621
622	FOR_EACH_ALLOCNO_OBJECT (a, obj, i)
623	{
624	OBJECT_CONFLICT_HARD_REGS (obj) |= set;
625	OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= set;
626	}
627	}
628
629	/* Return TRUE if a conflict vector with NUM elements is more
630	profitable than a conflict bit vector for OBJ. */
631	bool
632	ira_conflict_vector_profitable_p (ira_object_t obj, int num)
633	{
634	int nbytes;
635	int max = OBJECT_MAX (obj);
636	int min = OBJECT_MIN (obj);
637
638	if (max < min)
639	/* We prefer a bit vector in such case because it does not result
640	in allocation. */
641	return false;
642
643	nbytes = (max - min) / 8 + 1;
644	STATIC_ASSERT (sizeof (ira_object_t) <= 8);
645	/* Don't use sizeof (ira_object_t), use constant 8. Size of ira_object_t (a
646	pointer) is different on 32-bit and 64-bit targets. Usage sizeof
647	(ira_object_t) can result in different code generation by GCC built as 32-
648	and 64-bit program. In any case the profitability is just an estimation
649	and border cases are rare. */
650	return (2 * 8 /* sizeof (ira_object_t) */ * (num + 1) < 3 * nbytes);
651	}
652
653	/* Allocates and initialize the conflict vector of OBJ for NUM
654	conflicting objects. */
655	void
656	ira_allocate_conflict_vec (ira_object_t obj, int num)
657	{
658	int size;
659	ira_object_t *vec;
660
661	ira_assert (OBJECT_CONFLICT_ARRAY (obj) == NULL);
662	num++; /* for NULL end marker */
663	size = sizeof (ira_object_t) * num;
664	OBJECT_CONFLICT_ARRAY (obj) = ira_allocate (size);
665	vec = (ira_object_t *) OBJECT_CONFLICT_ARRAY (obj);
666	vec[0] = NULL;
667	OBJECT_NUM_CONFLICTS (obj) = 0;
668	OBJECT_CONFLICT_ARRAY_SIZE (obj) = size;
669	OBJECT_CONFLICT_VEC_P (obj) = true;
670	}
671
672	/* Allocate and initialize the conflict bit vector of OBJ. */
673	static void
674	allocate_conflict_bit_vec (ira_object_t obj)
675	{
676	unsigned int size;
677
678	ira_assert (OBJECT_CONFLICT_ARRAY (obj) == NULL);
679	size = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
680	/ IRA_INT_BITS * sizeof (IRA_INT_TYPE));
681	OBJECT_CONFLICT_ARRAY (obj) = ira_allocate (size);
682	memset (OBJECT_CONFLICT_ARRAY (obj), c: 0, n: size);
683	OBJECT_CONFLICT_ARRAY_SIZE (obj) = size;
684	OBJECT_CONFLICT_VEC_P (obj) = false;
685	}
686
687	/* Allocate and initialize the conflict vector or conflict bit vector
688	of OBJ for NUM conflicting allocnos whatever is more profitable. */
689	void
690	ira_allocate_object_conflicts (ira_object_t obj, int num)
691	{
692	if (ira_conflict_vector_profitable_p (obj, num))
693	ira_allocate_conflict_vec (obj, num);
694	else
695	allocate_conflict_bit_vec (obj);
696	}
697
698	/* Add OBJ2 to the conflicts of OBJ1. */
699	static void
700	add_to_conflicts (ira_object_t obj1, ira_object_t obj2)
701	{
702	int num;
703	unsigned int size;
704
705	if (OBJECT_CONFLICT_VEC_P (obj1))
706	{
707	ira_object_t *vec = OBJECT_CONFLICT_VEC (obj1);
708	int curr_num = OBJECT_NUM_CONFLICTS (obj1);
709	num = curr_num + 2;
710	if (OBJECT_CONFLICT_ARRAY_SIZE (obj1) < num * sizeof (ira_object_t))
711	{
712	ira_object_t *newvec;
713	size = (3 * num / 2 + 1) * sizeof (ira_allocno_t);
714	newvec = (ira_object_t *) ira_allocate (size);
715	memcpy (dest: newvec, src: vec, n: curr_num * sizeof (ira_object_t));
716	ira_free (addr: vec);
717	vec = newvec;
718	OBJECT_CONFLICT_ARRAY (obj1) = vec;
719	OBJECT_CONFLICT_ARRAY_SIZE (obj1) = size;
720	}
721	vec[num - 2] = obj2;
722	vec[num - 1] = NULL;
723	OBJECT_NUM_CONFLICTS (obj1)++;
724	}
725	else
726	{
727	int nw, added_head_nw, id;
728	IRA_INT_TYPE *vec = OBJECT_CONFLICT_BITVEC (obj1);
729
730	id = OBJECT_CONFLICT_ID (obj2);
731	if (OBJECT_MIN (obj1) > id)
732	{
733	/* Expand head of the bit vector. */
734	added_head_nw = (OBJECT_MIN (obj1) - id - 1) / IRA_INT_BITS + 1;
735	nw = (OBJECT_MAX (obj1) - OBJECT_MIN (obj1)) / IRA_INT_BITS + 1;
736	size = (nw + added_head_nw) * sizeof (IRA_INT_TYPE);
737	if (OBJECT_CONFLICT_ARRAY_SIZE (obj1) >= size)
738	{
739	memmove (dest: (char *) vec + added_head_nw * sizeof (IRA_INT_TYPE),
740	src: vec, n: nw * sizeof (IRA_INT_TYPE));
741	memset (s: vec, c: 0, n: added_head_nw * sizeof (IRA_INT_TYPE));
742	}
743	else
744	{
745	size
746	= (3 * (nw + added_head_nw) / 2 + 1) * sizeof (IRA_INT_TYPE);
747	vec = (IRA_INT_TYPE *) ira_allocate (size);
748	memcpy (dest: (char *) vec + added_head_nw * sizeof (IRA_INT_TYPE),
749	OBJECT_CONFLICT_ARRAY (obj1), n: nw * sizeof (IRA_INT_TYPE));
750	memset (s: vec, c: 0, n: added_head_nw * sizeof (IRA_INT_TYPE));
751	memset (s: (char *) vec
752	+ (nw + added_head_nw) * sizeof (IRA_INT_TYPE),
753	c: 0, n: size - (nw + added_head_nw) * sizeof (IRA_INT_TYPE));
754	ira_free (OBJECT_CONFLICT_ARRAY (obj1));
755	OBJECT_CONFLICT_ARRAY (obj1) = vec;
756	OBJECT_CONFLICT_ARRAY_SIZE (obj1) = size;
757	}
758	OBJECT_MIN (obj1) -= added_head_nw * IRA_INT_BITS;
759	}
760	else if (OBJECT_MAX (obj1) < id)
761	{
762	nw = (id - OBJECT_MIN (obj1)) / IRA_INT_BITS + 1;
763	size = nw * sizeof (IRA_INT_TYPE);
764	if (OBJECT_CONFLICT_ARRAY_SIZE (obj1) < size)
765	{
766	/* Expand tail of the bit vector. */
767	size = (3 * nw / 2 + 1) * sizeof (IRA_INT_TYPE);
768	vec = (IRA_INT_TYPE *) ira_allocate (size);
769	memcpy (dest: vec, OBJECT_CONFLICT_ARRAY (obj1), OBJECT_CONFLICT_ARRAY_SIZE (obj1));
770	memset (s: (char *) vec + OBJECT_CONFLICT_ARRAY_SIZE (obj1),
771	c: 0, n: size - OBJECT_CONFLICT_ARRAY_SIZE (obj1));
772	ira_free (OBJECT_CONFLICT_ARRAY (obj1));
773	OBJECT_CONFLICT_ARRAY (obj1) = vec;
774	OBJECT_CONFLICT_ARRAY_SIZE (obj1) = size;
775	}
776	OBJECT_MAX (obj1) = id;
777	}
778	SET_MINMAX_SET_BIT (vec, id, OBJECT_MIN (obj1), OBJECT_MAX (obj1));
779	}
780	}
781
782	/* Add OBJ1 to the conflicts of OBJ2 and vice versa. */
783	static void
784	ira_add_conflict (ira_object_t obj1, ira_object_t obj2)
785	{
786	add_to_conflicts (obj1, obj2);
787	add_to_conflicts (obj1: obj2, obj2: obj1);
788	}
789
790	/* Clear all conflicts of OBJ. */
791	static void
792	clear_conflicts (ira_object_t obj)
793	{
794	if (OBJECT_CONFLICT_VEC_P (obj))
795	{
796	OBJECT_NUM_CONFLICTS (obj) = 0;
797	OBJECT_CONFLICT_VEC (obj)[0] = NULL;
798	}
799	else if (OBJECT_CONFLICT_ARRAY_SIZE (obj) != 0)
800	{
801	int nw;
802
803	nw = (OBJECT_MAX (obj) - OBJECT_MIN (obj)) / IRA_INT_BITS + 1;
804	memset (OBJECT_CONFLICT_BITVEC (obj), c: 0, n: nw * sizeof (IRA_INT_TYPE));
805	}
806	}
807
808	/* The array used to find duplications in conflict vectors of
809	allocnos. */
810	static int *conflict_check;
811
812	/* The value used to mark allocation presence in conflict vector of
813	the current allocno. */
814	static int curr_conflict_check_tick;
815
816	/* Remove duplications in conflict vector of OBJ. */
817	static void
818	compress_conflict_vec (ira_object_t obj)
819	{
820	ira_object_t *vec, conflict_obj;
821	int i, j;
822
823	ira_assert (OBJECT_CONFLICT_VEC_P (obj));
824	vec = OBJECT_CONFLICT_VEC (obj);
825	curr_conflict_check_tick++;
826	for (i = j = 0; (conflict_obj = vec[i]) != NULL; i++)
827	{
828	int id = OBJECT_CONFLICT_ID (conflict_obj);
829	if (conflict_check[id] != curr_conflict_check_tick)
830	{
831	conflict_check[id] = curr_conflict_check_tick;
832	vec[j++] = conflict_obj;
833	}
834	}
835	OBJECT_NUM_CONFLICTS (obj) = j;
836	vec[j] = NULL;
837	}
838
839	/* Remove duplications in conflict vectors of all allocnos. */
840	static void
841	compress_conflict_vecs (void)
842	{
843	ira_object_t obj;
844	ira_object_iterator oi;
845
846	conflict_check = (int *) ira_allocate (sizeof (int) * ira_objects_num);
847	memset (s: conflict_check, c: 0, n: sizeof (int) * ira_objects_num);
848	curr_conflict_check_tick = 0;
849	FOR_EACH_OBJECT (obj, oi)
850	{
851	if (OBJECT_CONFLICT_VEC_P (obj))
852	compress_conflict_vec (obj);
853	}
854	ira_free (addr: conflict_check);
855	}
856
857	/* This recursive function outputs allocno A and if it is a cap the
858	function outputs its members. */
859	void
860	ira_print_expanded_allocno (ira_allocno_t a)
861	{
862	basic_block bb;
863
864	fprintf (stream: ira_dump_file, format: " a%d(r%d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
865	if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
866	fprintf (stream: ira_dump_file, format: ",b%d", bb->index);
867	else
868	fprintf (stream: ira_dump_file, format: ",l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
869	if (ALLOCNO_CAP_MEMBER (a) != NULL)
870	{
871	fprintf (stream: ira_dump_file, format: ":");
872	ira_print_expanded_allocno (ALLOCNO_CAP_MEMBER (a));
873	}
874	fprintf (stream: ira_dump_file, format: ")");
875	}
876
877	/* Create and return the cap representing allocno A in the
878	parent loop. */
879	static ira_allocno_t
880	create_cap_allocno (ira_allocno_t a)
881	{
882	ira_allocno_t cap;
883	ira_loop_tree_node_t parent;
884	enum reg_class aclass;
885
886	parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
887	cap = ira_create_allocno (ALLOCNO_REGNO (a), cap_p: true, loop_tree_node: parent);
888	ALLOCNO_MODE (cap) = ALLOCNO_MODE (a);
889	ALLOCNO_WMODE (cap) = ALLOCNO_WMODE (a);
890	aclass = ALLOCNO_CLASS (a);
891	ira_set_allocno_class (a: cap, aclass);
892	ira_create_allocno_objects (a: cap);
893	ALLOCNO_CAP_MEMBER (cap) = a;
894	ALLOCNO_CAP (a) = cap;
895	ALLOCNO_CLASS_COST (cap) = ALLOCNO_CLASS_COST (a);
896	ALLOCNO_MEMORY_COST (cap) = ALLOCNO_MEMORY_COST (a);
897	ira_allocate_and_copy_costs
898	(vec: &ALLOCNO_HARD_REG_COSTS (cap), aclass, ALLOCNO_HARD_REG_COSTS (a));
899	ira_allocate_and_copy_costs
900	(vec: &ALLOCNO_CONFLICT_HARD_REG_COSTS (cap), aclass,
901	ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
902	ALLOCNO_BAD_SPILL_P (cap) = ALLOCNO_BAD_SPILL_P (a);
903	ALLOCNO_NREFS (cap) = ALLOCNO_NREFS (a);
904	ALLOCNO_FREQ (cap) = ALLOCNO_FREQ (a);
905	ALLOCNO_CALL_FREQ (cap) = ALLOCNO_CALL_FREQ (a);
906	ALLOCNO_SET_REGISTER_FILTERS (cap, ALLOCNO_REGISTER_FILTERS (a));
907
908	merge_hard_reg_conflicts (from: a, to: cap, total_only: false);
909
910	ALLOCNO_CALLS_CROSSED_NUM (cap) = ALLOCNO_CALLS_CROSSED_NUM (a);
911	ALLOCNO_CHEAP_CALLS_CROSSED_NUM (cap) = ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
912	ALLOCNO_CROSSED_CALLS_ABIS (cap) = ALLOCNO_CROSSED_CALLS_ABIS (a);
913	ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (cap)
914	= ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a);
915	if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
916	{
917	fprintf (stream: ira_dump_file, format: " Creating cap ");
918	ira_print_expanded_allocno (a: cap);
919	fprintf (stream: ira_dump_file, format: "\n");
920	}
921	return cap;
922	}
923
924	/* Create and return a live range for OBJECT with given attributes. */
925	live_range_t
926	ira_create_live_range (ira_object_t obj, int start, int finish,
927	live_range_t next)
928	{
929	live_range_t p;
930
931	p = live_range_pool.allocate ();
932	p->object = obj;
933	p->start = start;
934	p->finish = finish;
935	p->next = next;
936	return p;
937	}
938
939	/* Create a new live range for OBJECT and queue it at the head of its
940	live range list. */
941	void
942	ira_add_live_range_to_object (ira_object_t object, int start, int finish)
943	{
944	live_range_t p;
945	p = ira_create_live_range (obj: object, start, finish,
946	OBJECT_LIVE_RANGES (object));
947	OBJECT_LIVE_RANGES (object) = p;
948	}
949
950	/* Copy allocno live range R and return the result. */
951	static live_range_t
952	copy_live_range (live_range_t r)
953	{
954	live_range_t p;
955
956	p = live_range_pool.allocate ();
957	*p = *r;
958	return p;
959	}
960
961	/* Copy allocno live range list given by its head R and return the
962	result. */
963	live_range_t
964	ira_copy_live_range_list (live_range_t r)
965	{
966	live_range_t p, first, last;
967
968	if (r == NULL)
969	return NULL;
970	for (first = last = NULL; r != NULL; r = r->next)
971	{
972	p = copy_live_range (r);
973	if (first == NULL)
974	first = p;
975	else
976	last->next = p;
977	last = p;
978	}
979	return first;
980	}
981
982	/* Merge ranges R1 and R2 and returns the result. The function
983	maintains the order of ranges and tries to minimize number of the
984	result ranges. */
985	live_range_t
986	ira_merge_live_ranges (live_range_t r1, live_range_t r2)
987	{
988	live_range_t first, last;
989
990	if (r1 == NULL)
991	return r2;
992	if (r2 == NULL)
993	return r1;
994	for (first = last = NULL; r1 != NULL && r2 != NULL;)
995	{
996	if (r1->start < r2->start)
997	std::swap (a&: r1, b&: r2);
998	if (r1->start <= r2->finish + 1)
999	{
1000	/* Intersected ranges: merge r1 and r2 into r1. */
1001	r1->start = r2->start;
1002	if (r1->finish < r2->finish)
1003	r1->finish = r2->finish;
1004	live_range_t temp = r2;
1005	r2 = r2->next;
1006	ira_finish_live_range (temp);
1007	if (r2 == NULL)
1008	{
1009	/* To try to merge with subsequent ranges in r1. */
1010	r2 = r1->next;
1011	r1->next = NULL;
1012	}
1013	}
1014	else
1015	{
1016	/* Add r1 to the result. */
1017	if (first == NULL)
1018	first = last = r1;
1019	else
1020	{
1021	last->next = r1;
1022	last = r1;
1023	}
1024	r1 = r1->next;
1025	if (r1 == NULL)
1026	{
1027	/* To try to merge with subsequent ranges in r2. */
1028	r1 = r2->next;
1029	r2->next = NULL;
1030	}
1031	}
1032	}
1033	if (r1 != NULL)
1034	{
1035	if (first == NULL)
1036	first = r1;
1037	else
1038	last->next = r1;
1039	ira_assert (r1->next == NULL);
1040	}
1041	else if (r2 != NULL)
1042	{
1043	if (first == NULL)
1044	first = r2;
1045	else
1046	last->next = r2;
1047	ira_assert (r2->next == NULL);
1048	}
1049	else
1050	{
1051	ira_assert (last->next == NULL);
1052	}
1053	return first;
1054	}
1055
1056	/* Return TRUE if live ranges R1 and R2 intersect. */
1057	bool
1058	ira_live_ranges_intersect_p (live_range_t r1, live_range_t r2)
1059	{
1060	/* Remember the live ranges are always kept ordered. */
1061	while (r1 != NULL && r2 != NULL)
1062	{
1063	if (r1->start > r2->finish)
1064	r1 = r1->next;
1065	else if (r2->start > r1->finish)
1066	r2 = r2->next;
1067	else
1068	return true;
1069	}
1070	return false;
1071	}
1072
1073	/* Free allocno live range R. */
1074	void
1075	ira_finish_live_range (live_range_t r)
1076	{
1077	live_range_pool.remove (object: r);
1078	}
1079
1080	/* Free list of allocno live ranges starting with R. */
1081	void
1082	ira_finish_live_range_list (live_range_t r)
1083	{
1084	live_range_t next_r;
1085
1086	for (; r != NULL; r = next_r)
1087	{
1088	next_r = r->next;
1089	ira_finish_live_range (r);
1090	}
1091	}
1092
1093	/* Free updated register costs of allocno A. */
1094	void
1095	ira_free_allocno_updated_costs (ira_allocno_t a)
1096	{
1097	enum reg_class aclass;
1098
1099	aclass = ALLOCNO_CLASS (a);
1100	if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL)
1101	ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass);
1102	ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
1103	if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
1104	ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
1105	aclass);
1106	ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
1107	}
1108
1109	/* Free and nullify all cost vectors allocated earlier for allocno
1110	A. */
1111	static void
1112	ira_free_allocno_costs (ira_allocno_t a)
1113	{
1114	enum reg_class aclass = ALLOCNO_CLASS (a);
1115	ira_object_t obj;
1116	ira_allocno_object_iterator oi;
1117
1118	FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
1119	{
1120	ira_finish_live_range_list (OBJECT_LIVE_RANGES (obj));
1121	ira_object_id_map[OBJECT_CONFLICT_ID (obj)] = NULL;
1122	if (OBJECT_CONFLICT_ARRAY (obj) != NULL)
1123	ira_free (OBJECT_CONFLICT_ARRAY (obj));
1124	object_pool.remove (object: obj);
1125	}
1126
1127	ira_allocnos[ALLOCNO_NUM (a)] = NULL;
1128	if (ALLOCNO_HARD_REG_COSTS (a) != NULL)
1129	ira_free_cost_vector (ALLOCNO_HARD_REG_COSTS (a), aclass);
1130	if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL)
1131	ira_free_cost_vector (ALLOCNO_CONFLICT_HARD_REG_COSTS (a), aclass);
1132	if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL)
1133	ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass);
1134	if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
1135	ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
1136	aclass);
1137	ALLOCNO_HARD_REG_COSTS (a) = NULL;
1138	ALLOCNO_CONFLICT_HARD_REG_COSTS (a) = NULL;
1139	ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
1140	ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
1141	}
1142
1143	/* Free the memory allocated for allocno A. */
1144	static void
1145	finish_allocno (ira_allocno_t a)
1146	{
1147	ira_free_allocno_costs (a);
1148	allocno_pool.remove (object: a);
1149	}
1150
1151	/* Free the memory allocated for all allocnos. */
1152	static void
1153	finish_allocnos (void)
1154	{
1155	ira_allocno_t a;
1156	ira_allocno_iterator ai;
1157
1158	FOR_EACH_ALLOCNO (a, ai)
1159	finish_allocno (a);
1160	ira_free (addr: ira_regno_allocno_map);
1161	ira_object_id_map_vec.release ();
1162	allocno_vec.release ();
1163	allocno_pool.release ();
1164	object_pool.release ();
1165	live_range_pool.release ();
1166	}
1167
1168
1169
1170	/* Pools for allocno preferences. */
1171	static object_allocator <ira_allocno_pref> pref_pool ("prefs");
1172
1173	/* Vec containing references to all created preferences. It is a
1174	container of array ira_prefs. */
1175	static vec<ira_pref_t> pref_vec;
1176
1177	/* The function initializes data concerning allocno prefs. */
1178	static void
1179	initiate_prefs (void)
1180	{
1181	pref_vec.create (nelems: get_max_uid ());
1182	ira_prefs = NULL;
1183	ira_prefs_num = 0;
1184	}
1185
1186	/* Return pref for A and HARD_REGNO if any. */
1187	static ira_pref_t
1188	find_allocno_pref (ira_allocno_t a, int hard_regno)
1189	{
1190	ira_pref_t pref;
1191
1192	for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref)
1193	if (pref->allocno == a && pref->hard_regno == hard_regno)
1194	return pref;
1195	return NULL;
1196	}
1197
1198	/* Create and return pref with given attributes A, HARD_REGNO, and FREQ. */
1199	ira_pref_t
1200	ira_create_pref (ira_allocno_t a, int hard_regno, int freq)
1201	{
1202	ira_pref_t pref;
1203
1204	pref = pref_pool.allocate ();
1205	pref->num = ira_prefs_num;
1206	pref->allocno = a;
1207	pref->hard_regno = hard_regno;
1208	pref->freq = freq;
1209	pref_vec.safe_push (obj: pref);
1210	ira_prefs = pref_vec.address ();
1211	ira_prefs_num = pref_vec.length ();
1212	return pref;
1213	}
1214
1215	/* Attach a pref PREF to the corresponding allocno. */
1216	static void
1217	add_allocno_pref_to_list (ira_pref_t pref)
1218	{
1219	ira_allocno_t a = pref->allocno;
1220
1221	pref->next_pref = ALLOCNO_PREFS (a);
1222	ALLOCNO_PREFS (a) = pref;
1223	}
1224
1225	/* Create (or update frequency if the pref already exists) the pref of
1226	allocnos A preferring HARD_REGNO with frequency FREQ. */
1227	void
1228	ira_add_allocno_pref (ira_allocno_t a, int hard_regno, int freq)
1229	{
1230	ira_pref_t pref;
1231
1232	if (freq <= 0)
1233	return;
1234	if ((pref = find_allocno_pref (a, hard_regno)) != NULL)
1235	{
1236	pref->freq += freq;
1237	return;
1238	}
1239	pref = ira_create_pref (a, hard_regno, freq);
1240	ira_assert (a != NULL);
1241	add_allocno_pref_to_list (pref);
1242	}
1243
1244	/* Print info about PREF into file F. */
1245	static void
1246	print_pref (FILE *f, ira_pref_t pref)
1247	{
1248	fprintf (stream: f, format: " pref%d:a%d(r%d)<-hr%d@%d\n", pref->num,
1249	ALLOCNO_NUM (pref->allocno), ALLOCNO_REGNO (pref->allocno),
1250	pref->hard_regno, pref->freq);
1251	}
1252
1253	/* Print info about PREF into stderr. */
1254	void
1255	ira_debug_pref (ira_pref_t pref)
1256	{
1257	print_pref (stderr, pref);
1258	}
1259
1260	/* Print info about all prefs into file F. */
1261	static void
1262	print_prefs (FILE *f)
1263	{
1264	ira_pref_t pref;
1265	ira_pref_iterator pi;
1266
1267	FOR_EACH_PREF (pref, pi)
1268	print_pref (f, pref);
1269	}
1270
1271	/* Print info about all prefs into stderr. */
1272	void
1273	ira_debug_prefs (void)
1274	{
1275	print_prefs (stderr);
1276	}
1277
1278	/* Print info about prefs involving allocno A into file F. */
1279	static void
1280	print_allocno_prefs (FILE *f, ira_allocno_t a)
1281	{
1282	ira_pref_t pref;
1283
1284	fprintf (stream: f, format: " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
1285	for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref)
1286	fprintf (stream: f, format: " pref%d:hr%d@%d", pref->num, pref->hard_regno, pref->freq);
1287	fprintf (stream: f, format: "\n");
1288	}
1289
1290	/* Print info about prefs involving allocno A into stderr. */
1291	void
1292	ira_debug_allocno_prefs (ira_allocno_t a)
1293	{
1294	print_allocno_prefs (stderr, a);
1295	}
1296
1297	/* The function frees memory allocated for PREF. */
1298	static void
1299	finish_pref (ira_pref_t pref)
1300	{
1301	ira_prefs[pref->num] = NULL;
1302	pref_pool.remove (object: pref);
1303	}
1304
1305	/* Remove PREF from the list of allocno prefs and free memory for
1306	it. */
1307	void
1308	ira_remove_pref (ira_pref_t pref)
1309	{
1310	ira_pref_t cpref, prev;
1311
1312	if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1313	fprintf (stream: ira_dump_file, format: " Removing pref%d:hr%d@%d\n",
1314	pref->num, pref->hard_regno, pref->freq);
1315	for (prev = NULL, cpref = ALLOCNO_PREFS (pref->allocno);
1316	cpref != NULL;
1317	prev = cpref, cpref = cpref->next_pref)
1318	if (cpref == pref)
1319	break;
1320	ira_assert (cpref != NULL);
1321	if (prev == NULL)
1322	ALLOCNO_PREFS (pref->allocno) = pref->next_pref;
1323	else
1324	prev->next_pref = pref->next_pref;
1325	finish_pref (pref);
1326	}
1327
1328	/* Remove all prefs of allocno A. */
1329	void
1330	ira_remove_allocno_prefs (ira_allocno_t a)
1331	{
1332	ira_pref_t pref, next_pref;
1333
1334	for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = next_pref)
1335	{
1336	next_pref = pref->next_pref;
1337	finish_pref (pref);
1338	}
1339	ALLOCNO_PREFS (a) = NULL;
1340	}
1341
1342	/* Free memory allocated for all prefs. */
1343	static void
1344	finish_prefs (void)
1345	{
1346	ira_pref_t pref;
1347	ira_pref_iterator pi;
1348
1349	FOR_EACH_PREF (pref, pi)
1350	finish_pref (pref);
1351	pref_vec.release ();
1352	pref_pool.release ();
1353	}
1354
1355
1356
1357	/* Pools for copies. */
1358	static object_allocator<ira_allocno_copy> copy_pool ("copies");
1359
1360	/* Vec containing references to all created copies. It is a
1361	container of array ira_copies. */
1362	static vec<ira_copy_t> copy_vec;
1363
1364	/* The function initializes data concerning allocno copies. */
1365	static void
1366	initiate_copies (void)
1367	{
1368	copy_vec.create (nelems: get_max_uid ());
1369	ira_copies = NULL;
1370	ira_copies_num = 0;
1371	}
1372
1373	/* Return copy connecting A1 and A2 and originated from INSN of
1374	LOOP_TREE_NODE if any. */
1375	static ira_copy_t
1376	find_allocno_copy (ira_allocno_t a1, ira_allocno_t a2, rtx_insn *insn,
1377	ira_loop_tree_node_t loop_tree_node)
1378	{
1379	ira_copy_t cp, next_cp;
1380	ira_allocno_t another_a;
1381
1382	for (cp = ALLOCNO_COPIES (a1); cp != NULL; cp = next_cp)
1383	{
1384	if (cp->first == a1)
1385	{
1386	next_cp = cp->next_first_allocno_copy;
1387	another_a = cp->second;
1388	}
1389	else if (cp->second == a1)
1390	{
1391	next_cp = cp->next_second_allocno_copy;
1392	another_a = cp->first;
1393	}
1394	else
1395	gcc_unreachable ();
1396	if (another_a == a2 && cp->insn == insn
1397	&& cp->loop_tree_node == loop_tree_node)
1398	return cp;
1399	}
1400	return NULL;
1401	}
1402
1403	/* Create and return copy with given attributes LOOP_TREE_NODE, FIRST,
1404	SECOND, FREQ, CONSTRAINT_P, and INSN. */
1405	ira_copy_t
1406	ira_create_copy (ira_allocno_t first, ira_allocno_t second, int freq,
1407	bool constraint_p, rtx_insn *insn,
1408	ira_loop_tree_node_t loop_tree_node)
1409	{
1410	ira_copy_t cp;
1411
1412	cp = copy_pool.allocate ();
1413	cp->num = ira_copies_num;
1414	cp->first = first;
1415	cp->second = second;
1416	cp->freq = freq;
1417	cp->constraint_p = constraint_p;
1418	cp->insn = insn;
1419	cp->loop_tree_node = loop_tree_node;
1420	copy_vec.safe_push (obj: cp);
1421	ira_copies = copy_vec.address ();
1422	ira_copies_num = copy_vec.length ();
1423	return cp;
1424	}
1425
1426	/* Attach a copy CP to allocnos involved into the copy. */
1427	static void
1428	add_allocno_copy_to_list (ira_copy_t cp)
1429	{
1430	ira_allocno_t first = cp->first, second = cp->second;
1431
1432	cp->prev_first_allocno_copy = NULL;
1433	cp->prev_second_allocno_copy = NULL;
1434	cp->next_first_allocno_copy = ALLOCNO_COPIES (first);
1435	if (cp->next_first_allocno_copy != NULL)
1436	{
1437	if (cp->next_first_allocno_copy->first == first)
1438	cp->next_first_allocno_copy->prev_first_allocno_copy = cp;
1439	else
1440	cp->next_first_allocno_copy->prev_second_allocno_copy = cp;
1441	}
1442	cp->next_second_allocno_copy = ALLOCNO_COPIES (second);
1443	if (cp->next_second_allocno_copy != NULL)
1444	{
1445	if (cp->next_second_allocno_copy->second == second)
1446	cp->next_second_allocno_copy->prev_second_allocno_copy = cp;
1447	else
1448	cp->next_second_allocno_copy->prev_first_allocno_copy = cp;
1449	}
1450	ALLOCNO_COPIES (first) = cp;
1451	ALLOCNO_COPIES (second) = cp;
1452	}
1453
1454	/* Make a copy CP a canonical copy where number of the
1455	first allocno is less than the second one. */
1456	static void
1457	swap_allocno_copy_ends_if_necessary (ira_copy_t cp)
1458	{
1459	if (ALLOCNO_NUM (cp->first) <= ALLOCNO_NUM (cp->second))
1460	return;
1461
1462	std::swap (a&: cp->first, b&: cp->second);
1463	std::swap (a&: cp->prev_first_allocno_copy, b&: cp->prev_second_allocno_copy);
1464	std::swap (a&: cp->next_first_allocno_copy, b&: cp->next_second_allocno_copy);
1465	}
1466
1467	/* Create (or update frequency if the copy already exists) and return
1468	the copy of allocnos FIRST and SECOND with frequency FREQ
1469	corresponding to move insn INSN (if any) and originated from
1470	LOOP_TREE_NODE. */
1471	ira_copy_t
1472	ira_add_allocno_copy (ira_allocno_t first, ira_allocno_t second, int freq,
1473	bool constraint_p, rtx_insn *insn,
1474	ira_loop_tree_node_t loop_tree_node)
1475	{
1476	ira_copy_t cp;
1477
1478	if ((cp = find_allocno_copy (a1: first, a2: second, insn, loop_tree_node)) != NULL)
1479	{
1480	cp->freq += freq;
1481	return cp;
1482	}
1483	cp = ira_create_copy (first, second, freq, constraint_p, insn,
1484	loop_tree_node);
1485	ira_assert (first != NULL && second != NULL);
1486	add_allocno_copy_to_list (cp);
1487	swap_allocno_copy_ends_if_necessary (cp);
1488	return cp;
1489	}
1490
1491	/* Print info about copy CP into file F. */
1492	static void
1493	print_copy (FILE *f, ira_copy_t cp)
1494	{
1495	fprintf (stream: f, format: " cp%d:a%d(r%d)<->a%d(r%d)@%d:%s\n", cp->num,
1496	ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
1497	ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second), cp->freq,
1498	cp->insn != NULL
1499	? "move" : cp->constraint_p ? "constraint" : "shuffle");
1500	}
1501
1502	DEBUG_FUNCTION void
1503	debug (ira_allocno_copy &ref)
1504	{
1505	print_copy (stderr, cp: &ref);
1506	}
1507
1508	DEBUG_FUNCTION void
1509	debug (ira_allocno_copy *ptr)
1510	{
1511	if (ptr)
1512	debug (ref&: *ptr);
1513	else
1514	fprintf (stderr, format: "<nil>\n");
1515	}
1516
1517	/* Print info about copy CP into stderr. */
1518	void
1519	ira_debug_copy (ira_copy_t cp)
1520	{
1521	print_copy (stderr, cp);
1522	}
1523
1524	/* Print info about all copies into file F. */
1525	static void
1526	print_copies (FILE *f)
1527	{
1528	ira_copy_t cp;
1529	ira_copy_iterator ci;
1530
1531	FOR_EACH_COPY (cp, ci)
1532	print_copy (f, cp);
1533	}
1534
1535	/* Print info about all copies into stderr. */
1536	void
1537	ira_debug_copies (void)
1538	{
1539	print_copies (stderr);
1540	}
1541
1542	/* Print info about copies involving allocno A into file F. */
1543	static void
1544	print_allocno_copies (FILE *f, ira_allocno_t a)
1545	{
1546	ira_allocno_t another_a;
1547	ira_copy_t cp, next_cp;
1548
1549	fprintf (stream: f, format: " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
1550	for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
1551	{
1552	if (cp->first == a)
1553	{
1554	next_cp = cp->next_first_allocno_copy;
1555	another_a = cp->second;
1556	}
1557	else if (cp->second == a)
1558	{
1559	next_cp = cp->next_second_allocno_copy;
1560	another_a = cp->first;
1561	}
1562	else
1563	gcc_unreachable ();
1564	fprintf (stream: f, format: " cp%d:a%d(r%d)@%d", cp->num,
1565	ALLOCNO_NUM (another_a), ALLOCNO_REGNO (another_a), cp->freq);
1566	}
1567	fprintf (stream: f, format: "\n");
1568	}
1569
1570	DEBUG_FUNCTION void
1571	debug (ira_allocno &ref)
1572	{
1573	print_allocno_copies (stderr, a: &ref);
1574	}
1575
1576	DEBUG_FUNCTION void
1577	debug (ira_allocno *ptr)
1578	{
1579	if (ptr)
1580	debug (ref&: *ptr);
1581	else
1582	fprintf (stderr, format: "<nil>\n");
1583	}
1584
1585
1586	/* Print info about copies involving allocno A into stderr. */
1587	void
1588	ira_debug_allocno_copies (ira_allocno_t a)
1589	{
1590	print_allocno_copies (stderr, a);
1591	}
1592
1593	/* The function frees memory allocated for copy CP. */
1594	static void
1595	finish_copy (ira_copy_t cp)
1596	{
1597	copy_pool.remove (object: cp);
1598	}
1599
1600
1601	/* Free memory allocated for all copies. */
1602	static void
1603	finish_copies (void)
1604	{
1605	ira_copy_t cp;
1606	ira_copy_iterator ci;
1607
1608	FOR_EACH_COPY (cp, ci)
1609	finish_copy (cp);
1610	copy_vec.release ();
1611	copy_pool.release ();
1612	}
1613
1614
1615
1616	/* Pools for cost vectors. It is defined only for allocno classes. */
1617	static pool_allocator *cost_vector_pool[N_REG_CLASSES];
1618
1619	/* The function initiates work with hard register cost vectors. It
1620	creates allocation pool for each allocno class. */
1621	static void
1622	initiate_cost_vectors (void)
1623	{
1624	int i;
1625	enum reg_class aclass;
1626
1627	for (i = 0; i < ira_allocno_classes_num; i++)
1628	{
1629	aclass = ira_allocno_classes[i];
1630	cost_vector_pool[aclass] = new pool_allocator
1631	("cost vectors", sizeof (int) * (ira_class_hard_regs_num[aclass]));
1632	}
1633	}
1634
1635	/* Allocate and return a cost vector VEC for ACLASS. */
1636	int *
1637	ira_allocate_cost_vector (reg_class_t aclass)
1638	{
1639	return (int*) cost_vector_pool[(int) aclass]->allocate ();
1640	}
1641
1642	/* Free a cost vector VEC for ACLASS. */
1643	void
1644	ira_free_cost_vector (int *vec, reg_class_t aclass)
1645	{
1646	ira_assert (vec != NULL);
1647	cost_vector_pool[(int) aclass]->remove (object: vec);
1648	}
1649
1650	/* Finish work with hard register cost vectors. Release allocation
1651	pool for each allocno class. */
1652	static void
1653	finish_cost_vectors (void)
1654	{
1655	int i;
1656	enum reg_class aclass;
1657
1658	for (i = 0; i < ira_allocno_classes_num; i++)
1659	{
1660	aclass = ira_allocno_classes[i];
1661	delete cost_vector_pool[aclass];
1662	}
1663	}
1664
1665
1666
1667	/* Compute a post-ordering of the reverse control flow of the loop body
1668	designated by the children nodes of LOOP_NODE, whose body nodes in
1669	pre-order are input as LOOP_PREORDER. Return a VEC with a post-order
1670	of the reverse loop body.
1671
1672	For the post-order of the reverse CFG, we visit the basic blocks in
1673	LOOP_PREORDER array in the reverse order of where they appear.
1674	This is important: We do not just want to compute a post-order of
1675	the reverse CFG, we want to make a best-guess for a visiting order that
1676	minimizes the number of chain elements per allocno live range. If the
1677	blocks would be visited in a different order, we would still compute a
1678	correct post-ordering but it would be less likely that two nodes
1679	connected by an edge in the CFG are neighbors in the topsort. */
1680
1681	static vec<ira_loop_tree_node_t>
1682	ira_loop_tree_body_rev_postorder (ira_loop_tree_node_t loop_node ATTRIBUTE_UNUSED,
1683	const vec<ira_loop_tree_node_t> &loop_preorder)
1684	{
1685	vec<ira_loop_tree_node_t> topsort_nodes = vNULL;
1686	unsigned int n_loop_preorder;
1687
1688	n_loop_preorder = loop_preorder.length ();
1689	if (n_loop_preorder != 0)
1690	{
1691	ira_loop_tree_node_t subloop_node;
1692	unsigned int i;
1693	auto_vec<ira_loop_tree_node_t> dfs_stack;
1694
1695	/* This is a bit of strange abuse of the BB_VISITED flag: We use
1696	the flag to mark blocks we still have to visit to add them to
1697	our post-order. Define an alias to avoid confusion. */
1698	#define BB_TO_VISIT BB_VISITED
1699
1700	FOR_EACH_VEC_ELT (loop_preorder, i, subloop_node)
1701	{
1702	gcc_checking_assert (! (subloop_node->bb->flags & BB_TO_VISIT));
1703	subloop_node->bb->flags |= BB_TO_VISIT;
1704	}
1705
1706	topsort_nodes.create (nelems: n_loop_preorder);
1707	dfs_stack.create (nelems: n_loop_preorder);
1708
1709	FOR_EACH_VEC_ELT_REVERSE (loop_preorder, i, subloop_node)
1710	{
1711	if (! (subloop_node->bb->flags & BB_TO_VISIT))
1712	continue;
1713
1714	subloop_node->bb->flags &= ~BB_TO_VISIT;
1715	dfs_stack.quick_push (obj: subloop_node);
1716	while (! dfs_stack.is_empty ())
1717	{
1718	edge e;
1719	edge_iterator ei;
1720
1721	ira_loop_tree_node_t n = dfs_stack.last ();
1722	FOR_EACH_EDGE (e, ei, n->bb->preds)
1723	{
1724	ira_loop_tree_node_t pred_node;
1725	basic_block pred_bb = e->src;
1726
1727	if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1728	continue;
1729
1730	pred_node = IRA_BB_NODE_BY_INDEX (pred_bb->index);
1731	if (pred_node != n
1732	&& (pred_node->bb->flags & BB_TO_VISIT))
1733	{
1734	pred_node->bb->flags &= ~BB_TO_VISIT;
1735	dfs_stack.quick_push (obj: pred_node);
1736	}
1737	}
1738	if (n == dfs_stack.last ())
1739	{
1740	dfs_stack.pop ();
1741	topsort_nodes.quick_push (obj: n);
1742	}
1743	}
1744	}
1745
1746	#undef BB_TO_VISIT
1747	}
1748
1749	gcc_assert (topsort_nodes.length () == n_loop_preorder);
1750	return topsort_nodes;
1751	}
1752
1753	/* The current loop tree node and its regno allocno map. */
1754	ira_loop_tree_node_t ira_curr_loop_tree_node;
1755	ira_allocno_t *ira_curr_regno_allocno_map;
1756
1757	/* This recursive function traverses loop tree with root LOOP_NODE
1758	calling non-null functions PREORDER_FUNC and POSTORDER_FUNC
1759	correspondingly in preorder and postorder. The function sets up
1760	IRA_CURR_LOOP_TREE_NODE and IRA_CURR_REGNO_ALLOCNO_MAP. If BB_P,
1761	basic block nodes of LOOP_NODE is also processed (before its
1762	subloop nodes).
1763
1764	If BB_P is set and POSTORDER_FUNC is given, the basic blocks in
1765	the loop are passed in the *reverse* post-order of the *reverse*
1766	CFG. This is only used by ira_create_allocno_live_ranges, which
1767	wants to visit basic blocks in this order to minimize the number
1768	of elements per live range chain.
1769	Note that the loop tree nodes are still visited in the normal,
1770	forward post-order of the loop tree. */
1771
1772	void
1773	ira_traverse_loop_tree (bool bb_p, ira_loop_tree_node_t loop_node,
1774	void (*preorder_func) (ira_loop_tree_node_t),
1775	void (*postorder_func) (ira_loop_tree_node_t))
1776	{
1777	ira_loop_tree_node_t subloop_node;
1778
1779	ira_assert (loop_node->bb == NULL);
1780	ira_curr_loop_tree_node = loop_node;
1781	ira_curr_regno_allocno_map = ira_curr_loop_tree_node->regno_allocno_map;
1782
1783	if (preorder_func != NULL)
1784	(*preorder_func) (loop_node);
1785
1786	if (bb_p)
1787	{
1788	auto_vec<ira_loop_tree_node_t> loop_preorder;
1789	unsigned int i;
1790
1791	/* Add all nodes to the set of nodes to visit. The IRA loop tree
1792	is set up such that nodes in the loop body appear in a pre-order
1793	of their place in the CFG. */
1794	for (subloop_node = loop_node->children;
1795	subloop_node != NULL;
1796	subloop_node = subloop_node->next)
1797	if (subloop_node->bb != NULL)
1798	loop_preorder.safe_push (obj: subloop_node);
1799
1800	if (preorder_func != NULL)
1801	FOR_EACH_VEC_ELT (loop_preorder, i, subloop_node)
1802	(*preorder_func) (subloop_node);
1803
1804	if (postorder_func != NULL)
1805	{
1806	vec<ira_loop_tree_node_t> loop_rev_postorder =
1807	ira_loop_tree_body_rev_postorder (loop_node, loop_preorder);
1808	FOR_EACH_VEC_ELT_REVERSE (loop_rev_postorder, i, subloop_node)
1809	(*postorder_func) (subloop_node);
1810	loop_rev_postorder.release ();
1811	}
1812	}
1813
1814	for (subloop_node = loop_node->subloops;
1815	subloop_node != NULL;
1816	subloop_node = subloop_node->subloop_next)
1817	{
1818	ira_assert (subloop_node->bb == NULL);
1819	ira_traverse_loop_tree (bb_p, loop_node: subloop_node,
1820	preorder_func, postorder_func);
1821	}
1822
1823	ira_curr_loop_tree_node = loop_node;
1824	ira_curr_regno_allocno_map = ira_curr_loop_tree_node->regno_allocno_map;
1825
1826	if (postorder_func != NULL)
1827	(*postorder_func) (loop_node);
1828	}
1829
1830
1831
1832	/* The basic block currently being processed. */
1833	static basic_block curr_bb;
1834
1835	/* This recursive function creates allocnos corresponding to
1836	pseudo-registers containing in X. True OUTPUT_P means that X is
1837	an lvalue. OUTER corresponds to the parent expression of X. */
1838	static void
1839	create_insn_allocnos (rtx x, rtx outer, bool output_p)
1840	{
1841	int i, j;
1842	const char *fmt;
1843	enum rtx_code code = GET_CODE (x);
1844
1845	if (code == REG)
1846	{
1847	int regno;
1848
1849	if ((regno = REGNO (x)) >= FIRST_PSEUDO_REGISTER)
1850	{
1851	ira_allocno_t a;
1852
1853	if ((a = ira_curr_regno_allocno_map[regno]) == NULL)
1854	{
1855	a = ira_create_allocno (regno, cap_p: false, loop_tree_node: ira_curr_loop_tree_node);
1856	if (outer != NULL && GET_CODE (outer) == SUBREG)
1857	{
1858	machine_mode wmode = GET_MODE (outer);
1859	if (partial_subreg_p (ALLOCNO_WMODE (a), innermode: wmode))
1860	ALLOCNO_WMODE (a) = wmode;
1861	}
1862	}
1863
1864	ALLOCNO_NREFS (a)++;
1865	ALLOCNO_FREQ (a) += REG_FREQ_FROM_BB (curr_bb);
1866	if (output_p)
1867	bitmap_set_bit (ira_curr_loop_tree_node->modified_regnos, regno);
1868	}
1869	return;
1870	}
1871	else if (code == SET)
1872	{
1873	create_insn_allocnos (SET_DEST (x), NULL, output_p: true);
1874	create_insn_allocnos (SET_SRC (x), NULL, output_p: false);
1875	return;
1876	}
1877	else if (code == CLOBBER)
1878	{
1879	create_insn_allocnos (XEXP (x, 0), NULL, output_p: true);
1880	return;
1881	}
1882	else if (code == MEM)
1883	{
1884	create_insn_allocnos (XEXP (x, 0), NULL, output_p: false);
1885	return;
1886	}
1887	else if (code == PRE_DEC || code == POST_DEC || code == PRE_INC ||
1888	code == POST_INC || code == POST_MODIFY || code == PRE_MODIFY)
1889	{
1890	create_insn_allocnos (XEXP (x, 0), NULL, output_p: true);
1891	create_insn_allocnos (XEXP (x, 0), NULL, output_p: false);
1892	return;
1893	}
1894
1895	fmt = GET_RTX_FORMAT (code);
1896	for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1897	{
1898	if (fmt[i] == 'e')
1899	create_insn_allocnos (XEXP (x, i), outer: x, output_p);
1900	else if (fmt[i] == 'E')
1901	for (j = 0; j < XVECLEN (x, i); j++)
1902	create_insn_allocnos (XVECEXP (x, i, j), outer: x, output_p);
1903	}
1904	}
1905
1906	/* Create allocnos corresponding to pseudo-registers living in the
1907	basic block represented by the corresponding loop tree node
1908	BB_NODE. */
1909	static void
1910	create_bb_allocnos (ira_loop_tree_node_t bb_node)
1911	{
1912	basic_block bb;
1913	rtx_insn *insn;
1914	unsigned int i;
1915	bitmap_iterator bi;
1916
1917	curr_bb = bb = bb_node->bb;
1918	ira_assert (bb != NULL);
1919	FOR_BB_INSNS_REVERSE (bb, insn)
1920	if (NONDEBUG_INSN_P (insn))
1921	create_insn_allocnos (x: PATTERN (insn), NULL, output_p: false);
1922	/* It might be a allocno living through from one subloop to
1923	another. */
1924	EXECUTE_IF_SET_IN_REG_SET (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, i, bi)
1925	if (ira_curr_regno_allocno_map[i] == NULL)
1926	ira_create_allocno (regno: i, cap_p: false, loop_tree_node: ira_curr_loop_tree_node);
1927	}
1928
1929	/* Create allocnos corresponding to pseudo-registers living on edge E
1930	(a loop entry or exit). Also mark the allocnos as living on the
1931	loop border. */
1932	static void
1933	create_loop_allocnos (edge e)
1934	{
1935	unsigned int i;
1936	bitmap live_in_regs, border_allocnos;
1937	bitmap_iterator bi;
1938	ira_loop_tree_node_t parent;
1939
1940	live_in_regs = df_get_live_in (bb: e->dest);
1941	border_allocnos = ira_curr_loop_tree_node->border_allocnos;
1942	EXECUTE_IF_SET_IN_REG_SET (df_get_live_out (e->src),
1943	FIRST_PSEUDO_REGISTER, i, bi)
1944	if (bitmap_bit_p (live_in_regs, i))
1945	{
1946	if (ira_curr_regno_allocno_map[i] == NULL)
1947	{
1948	/* The order of creations is important for right
1949	ira_regno_allocno_map. */
1950	if ((parent = ira_curr_loop_tree_node->parent) != NULL
1951	&& parent->regno_allocno_map[i] == NULL)
1952	ira_create_allocno (regno: i, cap_p: false, loop_tree_node: parent);
1953	ira_create_allocno (regno: i, cap_p: false, loop_tree_node: ira_curr_loop_tree_node);
1954	}
1955	bitmap_set_bit (border_allocnos,
1956	ALLOCNO_NUM (ira_curr_regno_allocno_map[i]));
1957	}
1958	}
1959
1960	/* Create allocnos corresponding to pseudo-registers living in loop
1961	represented by the corresponding loop tree node LOOP_NODE. This
1962	function is called by ira_traverse_loop_tree. */
1963	static void
1964	create_loop_tree_node_allocnos (ira_loop_tree_node_t loop_node)
1965	{
1966	if (loop_node->bb != NULL)
1967	create_bb_allocnos (bb_node: loop_node);
1968	else if (loop_node != ira_loop_tree_root)
1969	{
1970	int i;
1971	edge_iterator ei;
1972	edge e;
1973
1974	ira_assert (current_loops != NULL);
1975	FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
1976	if (e->src != loop_node->loop->latch)
1977	create_loop_allocnos (e);
1978
1979	auto_vec<edge> edges = get_loop_exit_edges (loop_node->loop);
1980	FOR_EACH_VEC_ELT (edges, i, e)
1981	create_loop_allocnos (e);
1982	}
1983	}
1984
1985	/* Propagate information about allocnos modified inside the loop given
1986	by its LOOP_TREE_NODE to its parent. */
1987	static void
1988	propagate_modified_regnos (ira_loop_tree_node_t loop_tree_node)
1989	{
1990	if (loop_tree_node == ira_loop_tree_root)
1991	return;
1992	ira_assert (loop_tree_node->bb == NULL);
1993	bitmap_ior_into (loop_tree_node->parent->modified_regnos,
1994	loop_tree_node->modified_regnos);
1995	}
1996
1997	/* Propagate ALLOCNO_HARD_REG_COSTS from A to PARENT_A. Use SPILL_COST
1998	as the cost of spilling a register throughout A (which we have to do
1999	for PARENT_A allocations that conflict with A). */
2000	static void
2001	ira_propagate_hard_reg_costs (ira_allocno_t parent_a, ira_allocno_t a,
2002	int spill_cost)
2003	{
2004	HARD_REG_SET conflicts = ira_total_conflict_hard_regs (a);
2005	if (ira_caller_save_loop_spill_p (a: parent_a, subloop_a: a, spill_cost))
2006	conflicts |= ira_need_caller_save_regs (a);
2007	conflicts &= ~ira_total_conflict_hard_regs (a: parent_a);
2008
2009	auto costs = ALLOCNO_HARD_REG_COSTS (a);
2010	if (!hard_reg_set_empty_p (x: conflicts))
2011	ALLOCNO_MIGHT_CONFLICT_WITH_PARENT_P (a) = true;
2012	else if (!costs)
2013	return;
2014
2015	auto aclass = ALLOCNO_CLASS (a);
2016	ira_allocate_and_set_costs (vec: &ALLOCNO_HARD_REG_COSTS (parent_a),
2017	aclass, ALLOCNO_CLASS_COST (parent_a));
2018	auto parent_costs = ALLOCNO_HARD_REG_COSTS (parent_a);
2019	for (int i = 0; i < ira_class_hard_regs_num[aclass]; ++i)
2020	if (TEST_HARD_REG_BIT (set: conflicts, ira_class_hard_regs[aclass][i]))
2021	parent_costs[i] += spill_cost;
2022	else if (costs)
2023	/* The cost to A of allocating this register to PARENT_A can't
2024	be more than the cost of spilling the register throughout A. */
2025	parent_costs[i] += MIN (costs[i], spill_cost);
2026	}
2027
2028	/* Propagate new info about allocno A (see comments about accumulated
2029	info in allocno definition) to the corresponding allocno on upper
2030	loop tree level. So allocnos on upper levels accumulate
2031	information about the corresponding allocnos in nested regions.
2032	The new info means allocno info finally calculated in this
2033	file. */
2034	static void
2035	propagate_allocno_info (void)
2036	{
2037	int i;
2038	ira_allocno_t a, parent_a;
2039	ira_loop_tree_node_t parent;
2040	enum reg_class aclass;
2041
2042	if (flag_ira_region != IRA_REGION_ALL
2043	&& flag_ira_region != IRA_REGION_MIXED)
2044	return;
2045	for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
2046	for (a = ira_regno_allocno_map[i];
2047	a != NULL;
2048	a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2049	if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL
2050	&& (parent_a = parent->regno_allocno_map[i]) != NULL
2051	/* There are no caps yet at this point. So use
2052	border_allocnos to find allocnos for the propagation. */
2053	&& bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE (a)->border_allocnos,
2054	ALLOCNO_NUM (a)))
2055	{
2056	/* Calculate the cost of storing to memory on entry to A's loop,
2057	referencing as memory within A's loop, and restoring from
2058	memory on exit from A's loop. */
2059	ira_loop_border_costs border_costs (a);
2060	int spill_cost = INT_MAX;
2061	if (ira_subloop_allocnos_can_differ_p (a: parent_a))
2062	spill_cost = (border_costs.spill_inside_loop_cost ()
2063	+ ALLOCNO_MEMORY_COST (a));
2064
2065	if (! ALLOCNO_BAD_SPILL_P (a))
2066	ALLOCNO_BAD_SPILL_P (parent_a) = false;
2067	ALLOCNO_NREFS (parent_a) += ALLOCNO_NREFS (a);
2068	ALLOCNO_FREQ (parent_a) += ALLOCNO_FREQ (a);
2069	ALLOCNO_SET_REGISTER_FILTERS (parent_a,
2070	ALLOCNO_REGISTER_FILTERS (parent_a)
2071	| ALLOCNO_REGISTER_FILTERS (a));
2072
2073	/* If A's allocation can differ from PARENT_A's, we can if necessary
2074	spill PARENT_A on entry to A's loop and restore it afterwards.
2075	Doing that has cost SPILL_COST. */
2076	if (!ira_subloop_allocnos_can_differ_p (a: parent_a))
2077	merge_hard_reg_conflicts (from: a, to: parent_a, total_only: true);
2078
2079	if (!ira_caller_save_loop_spill_p (a: parent_a, subloop_a: a, spill_cost))
2080	{
2081	ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
2082	ALLOCNO_CALLS_CROSSED_NUM (parent_a)
2083	+= ALLOCNO_CALLS_CROSSED_NUM (a);
2084	ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
2085	+= ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
2086	ALLOCNO_CROSSED_CALLS_ABIS (parent_a)
2087	|= ALLOCNO_CROSSED_CALLS_ABIS (a);
2088	ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (parent_a)
2089	|= ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a);
2090	}
2091	ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
2092	+= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2093	aclass = ALLOCNO_CLASS (a);
2094	ira_assert (aclass == ALLOCNO_CLASS (parent_a));
2095	ira_propagate_hard_reg_costs (parent_a, a, spill_cost);
2096	ira_allocate_and_accumulate_costs
2097	(vec: &ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a),
2098	aclass,
2099	ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
2100	/* The cost to A of allocating a register to PARENT_A can't be
2101	more than the cost of spilling the register throughout A. */
2102	ALLOCNO_CLASS_COST (parent_a)
2103	+= MIN (ALLOCNO_CLASS_COST (a), spill_cost);
2104	ALLOCNO_MEMORY_COST (parent_a) += ALLOCNO_MEMORY_COST (a);
2105	}
2106	}
2107
2108	/* Create allocnos corresponding to pseudo-registers in the current
2109	function. Traverse the loop tree for this. */
2110	static void
2111	create_allocnos (void)
2112	{
2113	/* We need to process BB first to correctly link allocnos by member
2114	next_regno_allocno. */
2115	ira_traverse_loop_tree (bb_p: true, loop_node: ira_loop_tree_root,
2116	preorder_func: create_loop_tree_node_allocnos, NULL);
2117	if (optimize)
2118	ira_traverse_loop_tree (bb_p: false, loop_node: ira_loop_tree_root, NULL,
2119	postorder_func: propagate_modified_regnos);
2120	}
2121
2122
2123
2124	/* The page contains function to remove some regions from a separate
2125	register allocation. We remove regions whose separate allocation
2126	will hardly improve the result. As a result we speed up regional
2127	register allocation. */
2128
2129	/* The function changes the object in range list given by R to OBJ. */
2130	static void
2131	change_object_in_range_list (live_range_t r, ira_object_t obj)
2132	{
2133	for (; r != NULL; r = r->next)
2134	r->object = obj;
2135	}
2136
2137	/* Move all live ranges associated with allocno FROM to allocno TO. */
2138	static void
2139	move_allocno_live_ranges (ira_allocno_t from, ira_allocno_t to)
2140	{
2141	int i;
2142	int n = ALLOCNO_NUM_OBJECTS (from);
2143
2144	gcc_assert (n == ALLOCNO_NUM_OBJECTS (to));
2145
2146	for (i = 0; i < n; i++)
2147	{
2148	ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
2149	ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
2150	live_range_t lr = OBJECT_LIVE_RANGES (from_obj);
2151
2152	if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2153	{
2154	fprintf (stream: ira_dump_file,
2155	format: " Moving ranges of a%dr%d to a%dr%d: ",
2156	ALLOCNO_NUM (from), ALLOCNO_REGNO (from),
2157	ALLOCNO_NUM (to), ALLOCNO_REGNO (to));
2158	ira_print_live_range_list (ira_dump_file, lr);
2159	}
2160	change_object_in_range_list (r: lr, obj: to_obj);
2161	OBJECT_LIVE_RANGES (to_obj)
2162	= ira_merge_live_ranges (r1: lr, OBJECT_LIVE_RANGES (to_obj));
2163	OBJECT_LIVE_RANGES (from_obj) = NULL;
2164	}
2165	}
2166
2167	static void
2168	copy_allocno_live_ranges (ira_allocno_t from, ira_allocno_t to)
2169	{
2170	int i;
2171	int n = ALLOCNO_NUM_OBJECTS (from);
2172
2173	gcc_assert (n == ALLOCNO_NUM_OBJECTS (to));
2174
2175	for (i = 0; i < n; i++)
2176	{
2177	ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
2178	ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
2179	live_range_t lr = OBJECT_LIVE_RANGES (from_obj);
2180
2181	if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2182	{
2183	fprintf (stream: ira_dump_file, format: " Copying ranges of a%dr%d to a%dr%d: ",
2184	ALLOCNO_NUM (from), ALLOCNO_REGNO (from),
2185	ALLOCNO_NUM (to), ALLOCNO_REGNO (to));
2186	ira_print_live_range_list (ira_dump_file, lr);
2187	}
2188	lr = ira_copy_live_range_list (r: lr);
2189	change_object_in_range_list (r: lr, obj: to_obj);
2190	OBJECT_LIVE_RANGES (to_obj)
2191	= ira_merge_live_ranges (r1: lr, OBJECT_LIVE_RANGES (to_obj));
2192	}
2193	}
2194
2195	/* Return TRUE if NODE represents a loop with low register
2196	pressure. */
2197	static bool
2198	low_pressure_loop_node_p (ira_loop_tree_node_t node)
2199	{
2200	int i;
2201	enum reg_class pclass;
2202
2203	if (node->bb != NULL)
2204	return false;
2205
2206	for (i = 0; i < ira_pressure_classes_num; i++)
2207	{
2208	pclass = ira_pressure_classes[i];
2209	if (node->reg_pressure[pclass] > ira_class_hard_regs_num[pclass]
2210	&& ira_class_hard_regs_num[pclass] > 1)
2211	return false;
2212	}
2213	return true;
2214	}
2215
2216	#ifdef STACK_REGS
2217	/* Return TRUE if LOOP has a complex enter or exit edge. We don't
2218	form a region from such loop if the target use stack register
2219	because reg-stack.cc cannot deal with such edges. */
2220	static bool
2221	loop_with_complex_edge_p (class loop *loop)
2222	{
2223	int i;
2224	edge_iterator ei;
2225	edge e;
2226	bool res;
2227
2228	FOR_EACH_EDGE (e, ei, loop->header->preds)
2229	if (e->flags & EDGE_EH)
2230	return true;
2231	auto_vec<edge> edges = get_loop_exit_edges (loop);
2232	res = false;
2233	FOR_EACH_VEC_ELT (edges, i, e)
2234	if (e->flags & EDGE_COMPLEX)
2235	{
2236	res = true;
2237	break;
2238	}
2239	return res;
2240	}
2241	#endif
2242
2243	/* Sort loops for marking them for removal. We put already marked
2244	loops first, then less frequent loops next, and then outer loops
2245	next. */
2246	static int
2247	loop_compare_func (const void *v1p, const void *v2p)
2248	{
2249	int diff;
2250	ira_loop_tree_node_t l1 = *(const ira_loop_tree_node_t *) v1p;
2251	ira_loop_tree_node_t l2 = *(const ira_loop_tree_node_t *) v2p;
2252
2253	ira_assert (l1->parent != NULL && l2->parent != NULL);
2254	if (l1->to_remove_p && ! l2->to_remove_p)
2255	return -1;
2256	if (! l1->to_remove_p && l2->to_remove_p)
2257	return 1;
2258	if ((diff = l1->loop->header->count.to_frequency (cfun)
2259	- l2->loop->header->count.to_frequency (cfun)) != 0)
2260	return diff;
2261	if ((diff = (int) loop_depth (loop: l1->loop) - (int) loop_depth (loop: l2->loop)) != 0)
2262	return diff;
2263	/* Make sorting stable. */
2264	return l1->loop_num - l2->loop_num;
2265	}
2266
2267	/* Mark loops which should be removed from regional allocation. We
2268	remove a loop with low register pressure inside another loop with
2269	register pressure. In this case a separate allocation of the loop
2270	hardly helps (for irregular register file architecture it could
2271	help by choosing a better hard register in the loop but we prefer
2272	faster allocation even in this case). We also remove cheap loops
2273	if there are more than param_ira_max_loops_num of them. Loop with EH
2274	exit or enter edges are removed too because the allocation might
2275	require put pseudo moves on the EH edges (we could still do this
2276	for pseudos with caller saved hard registers in some cases but it
2277	is impossible to say here or during top-down allocation pass what
2278	hard register the pseudos get finally). */
2279	static void
2280	mark_loops_for_removal (void)
2281	{
2282	int i, n;
2283	ira_loop_tree_node_t *sorted_loops;
2284	loop_p loop;
2285
2286	ira_assert (current_loops != NULL);
2287	sorted_loops
2288	= (ira_loop_tree_node_t *) ira_allocate (sizeof (ira_loop_tree_node_t)
2289	* number_of_loops (cfun));
2290	for (n = i = 0; vec_safe_iterate (v: get_loops (cfun), ix: i, ptr: &loop); i++)
2291	if (ira_loop_nodes[i].regno_allocno_map != NULL)
2292	{
2293	if (ira_loop_nodes[i].parent == NULL)
2294	{
2295	/* Don't remove the root. */
2296	ira_loop_nodes[i].to_remove_p = false;
2297	continue;
2298	}
2299	sorted_loops[n++] = &ira_loop_nodes[i];
2300	ira_loop_nodes[i].to_remove_p
2301	= ((low_pressure_loop_node_p (node: ira_loop_nodes[i].parent)
2302	&& low_pressure_loop_node_p (node: &ira_loop_nodes[i]))
2303	#ifdef STACK_REGS
2304	|| loop_with_complex_edge_p (loop: ira_loop_nodes[i].loop)
2305	#endif
2306	);
2307	}
2308	qsort (sorted_loops, n, sizeof (ira_loop_tree_node_t), loop_compare_func);
2309	for (i = 0; i < n - param_ira_max_loops_num; i++)
2310	{
2311	sorted_loops[i]->to_remove_p = true;
2312	if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2313	fprintf
2314	(stream: ira_dump_file,
2315	format: " Mark loop %d (header %d, freq %d, depth %d) for removal (%s)\n",
2316	sorted_loops[i]->loop_num, sorted_loops[i]->loop->header->index,
2317	sorted_loops[i]->loop->header->count.to_frequency (cfun),
2318	loop_depth (loop: sorted_loops[i]->loop),
2319	low_pressure_loop_node_p (node: sorted_loops[i]->parent)
2320	&& low_pressure_loop_node_p (node: sorted_loops[i])
2321	? "low pressure" : "cheap loop");
2322	}
2323	ira_free (addr: sorted_loops);
2324	}
2325
2326	/* Mark all loops but root for removing. */
2327	static void
2328	mark_all_loops_for_removal (void)
2329	{
2330	int i;
2331	loop_p loop;
2332
2333	ira_assert (current_loops != NULL);
2334	FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
2335	if (ira_loop_nodes[i].regno_allocno_map != NULL)
2336	{
2337	if (ira_loop_nodes[i].parent == NULL)
2338	{
2339	/* Don't remove the root. */
2340	ira_loop_nodes[i].to_remove_p = false;
2341	continue;
2342	}
2343	ira_loop_nodes[i].to_remove_p = true;
2344	if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2345	fprintf
2346	(stream: ira_dump_file,
2347	format: " Mark loop %d (header %d, freq %d, depth %d) for removal\n",
2348	ira_loop_nodes[i].loop_num,
2349	ira_loop_nodes[i].loop->header->index,
2350	ira_loop_nodes[i].loop->header->count.to_frequency (cfun),
2351	loop_depth (loop: ira_loop_nodes[i].loop));
2352	}
2353	}
2354
2355	/* Definition of vector of loop tree nodes. */
2356
2357	/* Vec containing references to all removed loop tree nodes. */
2358	static vec<ira_loop_tree_node_t> removed_loop_vec;
2359
2360	/* Vec containing references to all children of loop tree nodes. */
2361	static vec<ira_loop_tree_node_t> children_vec;
2362
2363	/* Remove subregions of NODE if their separate allocation will not
2364	improve the result. */
2365	static void
2366	remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_node_t node)
2367	{
2368	unsigned int start;
2369	bool remove_p;
2370	ira_loop_tree_node_t subnode;
2371
2372	remove_p = node->to_remove_p;
2373	if (! remove_p)
2374	children_vec.safe_push (obj: node);
2375	start = children_vec.length ();
2376	for (subnode = node->children; subnode != NULL; subnode = subnode->next)
2377	if (subnode->bb == NULL)
2378	remove_uneccesary_loop_nodes_from_loop_tree (node: subnode);
2379	else
2380	children_vec.safe_push (obj: subnode);
2381	node->children = node->subloops = NULL;
2382	if (remove_p)
2383	{
2384	removed_loop_vec.safe_push (obj: node);
2385	return;
2386	}
2387	while (children_vec.length () > start)
2388	{
2389	subnode = children_vec.pop ();
2390	subnode->parent = node;
2391	subnode->next = node->children;
2392	node->children = subnode;
2393	if (subnode->bb == NULL)
2394	{
2395	subnode->subloop_next = node->subloops;
2396	node->subloops = subnode;
2397	}
2398	}
2399	}
2400
2401	/* Return TRUE if NODE is inside PARENT. */
2402	static bool
2403	loop_is_inside_p (ira_loop_tree_node_t node, ira_loop_tree_node_t parent)
2404	{
2405	for (node = node->parent; node != NULL; node = node->parent)
2406	if (node == parent)
2407	return true;
2408	return false;
2409	}
2410
2411	/* Sort allocnos according to their order in regno allocno list. */
2412	static int
2413	regno_allocno_order_compare_func (const void *v1p, const void *v2p)
2414	{
2415	ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2416	ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2417	ira_loop_tree_node_t n1 = ALLOCNO_LOOP_TREE_NODE (a1);
2418	ira_loop_tree_node_t n2 = ALLOCNO_LOOP_TREE_NODE (a2);
2419
2420	if (loop_is_inside_p (node: n1, parent: n2))
2421	return -1;
2422	else if (loop_is_inside_p (node: n2, parent: n1))
2423	return 1;
2424	/* If allocnos are equally good, sort by allocno numbers, so that
2425	the results of qsort leave nothing to chance. We put allocnos
2426	with higher number first in the list because it is the original
2427	order for allocnos from loops on the same levels. */
2428	return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
2429	}
2430
2431	/* This array is used to sort allocnos to restore allocno order in
2432	the regno allocno list. */
2433	static ira_allocno_t *regno_allocnos;
2434
2435	/* Restore allocno order for REGNO in the regno allocno list. */
2436	static void
2437	ira_rebuild_regno_allocno_list (int regno)
2438	{
2439	int i, n;
2440	ira_allocno_t a;
2441
2442	for (n = 0, a = ira_regno_allocno_map[regno];
2443	a != NULL;
2444	a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2445	regno_allocnos[n++] = a;
2446	ira_assert (n > 0);
2447	qsort (regno_allocnos, n, sizeof (ira_allocno_t),
2448	regno_allocno_order_compare_func);
2449	for (i = 1; i < n; i++)
2450	ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[i - 1]) = regno_allocnos[i];
2451	ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[n - 1]) = NULL;
2452	ira_regno_allocno_map[regno] = regno_allocnos[0];
2453	if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2454	fprintf (stream: ira_dump_file, format: " Rebuilding regno allocno list for %d\n", regno);
2455	}
2456
2457	/* Propagate info from allocno FROM_A to allocno A. */
2458	static void
2459	propagate_some_info_from_allocno (ira_allocno_t a, ira_allocno_t from_a)
2460	{
2461	enum reg_class aclass;
2462
2463	merge_hard_reg_conflicts (from: from_a, to: a, total_only: false);
2464	ALLOCNO_NREFS (a) += ALLOCNO_NREFS (from_a);
2465	ALLOCNO_FREQ (a) += ALLOCNO_FREQ (from_a);
2466	ALLOCNO_CALL_FREQ (a) += ALLOCNO_CALL_FREQ (from_a);
2467	ALLOCNO_CALLS_CROSSED_NUM (a) += ALLOCNO_CALLS_CROSSED_NUM (from_a);
2468	ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a)
2469	+= ALLOCNO_CHEAP_CALLS_CROSSED_NUM (from_a);
2470	ALLOCNO_CROSSED_CALLS_ABIS (a) |= ALLOCNO_CROSSED_CALLS_ABIS (from_a);
2471	ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a)
2472	|= ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (from_a);
2473	ALLOCNO_SET_REGISTER_FILTERS (a,
2474	ALLOCNO_REGISTER_FILTERS (from_a)
2475	| ALLOCNO_REGISTER_FILTERS (a));
2476
2477	ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a)
2478	+= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (from_a);
2479	if (! ALLOCNO_BAD_SPILL_P (from_a))
2480	ALLOCNO_BAD_SPILL_P (a) = false;
2481	aclass = ALLOCNO_CLASS (from_a);
2482	ira_assert (aclass == ALLOCNO_CLASS (a));
2483	ira_allocate_and_accumulate_costs (vec: &ALLOCNO_HARD_REG_COSTS (a), aclass,
2484	ALLOCNO_HARD_REG_COSTS (from_a));
2485	ira_allocate_and_accumulate_costs (vec: &ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
2486	aclass,
2487	ALLOCNO_CONFLICT_HARD_REG_COSTS (from_a));
2488	ALLOCNO_CLASS_COST (a) += ALLOCNO_CLASS_COST (from_a);
2489	ALLOCNO_MEMORY_COST (a) += ALLOCNO_MEMORY_COST (from_a);
2490	}
2491
2492	/* Remove allocnos from loops removed from the allocation
2493	consideration. */
2494	static void
2495	remove_unnecessary_allocnos (void)
2496	{
2497	int regno;
2498	bool merged_p, rebuild_p;
2499	ira_allocno_t a, prev_a, next_a, parent_a;
2500	ira_loop_tree_node_t a_node, parent;
2501
2502	merged_p = false;
2503	regno_allocnos = NULL;
2504	for (regno = max_reg_num () - 1; regno >= FIRST_PSEUDO_REGISTER; regno--)
2505	{
2506	rebuild_p = false;
2507	for (prev_a = NULL, a = ira_regno_allocno_map[regno];
2508	a != NULL;
2509	a = next_a)
2510	{
2511	next_a = ALLOCNO_NEXT_REGNO_ALLOCNO (a);
2512	a_node = ALLOCNO_LOOP_TREE_NODE (a);
2513	if (! a_node->to_remove_p)
2514	prev_a = a;
2515	else
2516	{
2517	for (parent = a_node->parent;
2518	(parent_a = parent->regno_allocno_map[regno]) == NULL
2519	&& parent->to_remove_p;
2520	parent = parent->parent)
2521	;
2522	if (parent_a == NULL)
2523	{
2524	/* There are no allocnos with the same regno in
2525	upper region -- just move the allocno to the
2526	upper region. */
2527	prev_a = a;
2528	ALLOCNO_LOOP_TREE_NODE (a) = parent;
2529	parent->regno_allocno_map[regno] = a;
2530	bitmap_set_bit (parent->all_allocnos, ALLOCNO_NUM (a));
2531	rebuild_p = true;
2532	}
2533	else
2534	{
2535	/* Remove the allocno and update info of allocno in
2536	the upper region. */
2537	if (prev_a == NULL)
2538	ira_regno_allocno_map[regno] = next_a;
2539	else
2540	ALLOCNO_NEXT_REGNO_ALLOCNO (prev_a) = next_a;
2541	move_allocno_live_ranges (from: a, to: parent_a);
2542	merged_p = true;
2543	propagate_some_info_from_allocno (a: parent_a, from_a: a);
2544	/* Remove it from the corresponding regno allocno
2545	map to avoid info propagation of subsequent
2546	allocno into this already removed allocno. */
2547	a_node->regno_allocno_map[regno] = NULL;
2548	ira_remove_allocno_prefs (a);
2549	finish_allocno (a);
2550	}
2551	}
2552	}
2553	if (rebuild_p)
2554	/* We need to restore the order in regno allocno list. */
2555	{
2556	if (regno_allocnos == NULL)
2557	regno_allocnos
2558	= (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
2559	* ira_allocnos_num);
2560	ira_rebuild_regno_allocno_list (regno);
2561	}
2562	}
2563	if (merged_p)
2564	ira_rebuild_start_finish_chains ();
2565	if (regno_allocnos != NULL)
2566	ira_free (addr: regno_allocnos);
2567	}
2568
2569	/* Remove allocnos from all loops but the root. */
2570	static void
2571	remove_low_level_allocnos (void)
2572	{
2573	int regno;
2574	bool merged_p, propagate_p;
2575	ira_allocno_t a, top_a;
2576	ira_loop_tree_node_t a_node, parent;
2577	ira_allocno_iterator ai;
2578
2579	merged_p = false;
2580	FOR_EACH_ALLOCNO (a, ai)
2581	{
2582	a_node = ALLOCNO_LOOP_TREE_NODE (a);
2583	if (a_node == ira_loop_tree_root || ALLOCNO_CAP_MEMBER (a) != NULL)
2584	continue;
2585	regno = ALLOCNO_REGNO (a);
2586	if ((top_a = ira_loop_tree_root->regno_allocno_map[regno]) == NULL)
2587	{
2588	ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
2589	ira_loop_tree_root->regno_allocno_map[regno] = a;
2590	continue;
2591	}
2592	propagate_p = a_node->parent->regno_allocno_map[regno] == NULL;
2593	/* Remove the allocno and update info of allocno in the upper
2594	region. */
2595	move_allocno_live_ranges (from: a, to: top_a);
2596	merged_p = true;
2597	if (propagate_p)
2598	propagate_some_info_from_allocno (a: top_a, from_a: a);
2599	}
2600	FOR_EACH_ALLOCNO (a, ai)
2601	{
2602	a_node = ALLOCNO_LOOP_TREE_NODE (a);
2603	if (a_node == ira_loop_tree_root)
2604	continue;
2605	parent = a_node->parent;
2606	regno = ALLOCNO_REGNO (a);
2607	if (ALLOCNO_CAP_MEMBER (a) != NULL)
2608	ira_assert (ALLOCNO_CAP (a) != NULL);
2609	else if (ALLOCNO_CAP (a) == NULL)
2610	ira_assert (parent->regno_allocno_map[regno] != NULL);
2611	}
2612	FOR_EACH_ALLOCNO (a, ai)
2613	{
2614	regno = ALLOCNO_REGNO (a);
2615	if (ira_loop_tree_root->regno_allocno_map[regno] == a)
2616	{
2617	ira_object_t obj;
2618	ira_allocno_object_iterator oi;
2619
2620	ira_regno_allocno_map[regno] = a;
2621	ALLOCNO_NEXT_REGNO_ALLOCNO (a) = NULL;
2622	ALLOCNO_CAP_MEMBER (a) = NULL;
2623	FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2624	OBJECT_CONFLICT_HARD_REGS (obj)
2625	= OBJECT_TOTAL_CONFLICT_HARD_REGS (obj);
2626	#ifdef STACK_REGS
2627	if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
2628	ALLOCNO_NO_STACK_REG_P (a) = true;
2629	#endif
2630	}
2631	else
2632	{
2633	ira_remove_allocno_prefs (a);
2634	finish_allocno (a);
2635	}
2636	}
2637	if (merged_p)
2638	ira_rebuild_start_finish_chains ();
2639	}
2640
2641	/* Remove loops from consideration. We remove all loops except for
2642	root if ALL_P or loops for which a separate allocation will not
2643	improve the result. We have to do this after allocno creation and
2644	their costs and allocno class evaluation because only after that
2645	the register pressure can be known and is calculated. */
2646	static void
2647	remove_unnecessary_regions (bool all_p)
2648	{
2649	if (current_loops == NULL)
2650	return;
2651	if (all_p)
2652	mark_all_loops_for_removal ();
2653	else
2654	mark_loops_for_removal ();
2655	children_vec.create (last_basic_block_for_fn (cfun)
2656	+ number_of_loops (cfun));
2657	removed_loop_vec.create (last_basic_block_for_fn (cfun)
2658	+ number_of_loops (cfun));
2659	remove_uneccesary_loop_nodes_from_loop_tree (node: ira_loop_tree_root);
2660	children_vec.release ();
2661	if (all_p)
2662	remove_low_level_allocnos ();
2663	else
2664	remove_unnecessary_allocnos ();
2665	while (removed_loop_vec.length () > 0)
2666	finish_loop_tree_node (loop: removed_loop_vec.pop ());
2667	removed_loop_vec.release ();
2668	}
2669
2670
2671
2672	/* At this point true value of allocno attribute bad_spill_p means
2673	that there is an insn where allocno occurs and where the allocno
2674	cannot be used as memory. The function updates the attribute, now
2675	it can be true only for allocnos which cannot be used as memory in
2676	an insn and in whose live ranges there is other allocno deaths.
2677	Spilling allocnos with true value will not improve the code because
2678	it will not make other allocnos colorable and additional reloads
2679	for the corresponding pseudo will be generated in reload pass for
2680	each insn it occurs.
2681
2682	This is a trick mentioned in one classic article of Chaitin etc
2683	which is frequently omitted in other implementations of RA based on
2684	graph coloring. */
2685	static void
2686	update_bad_spill_attribute (void)
2687	{
2688	int i;
2689	ira_allocno_t a;
2690	ira_allocno_iterator ai;
2691	ira_allocno_object_iterator aoi;
2692	ira_object_t obj;
2693	live_range_t r;
2694	enum reg_class aclass;
2695	bitmap_head dead_points[N_REG_CLASSES];
2696
2697	for (i = 0; i < ira_allocno_classes_num; i++)
2698	{
2699	aclass = ira_allocno_classes[i];
2700	bitmap_initialize (head: &dead_points[aclass], obstack: &reg_obstack);
2701	}
2702	FOR_EACH_ALLOCNO (a, ai)
2703	{
2704	aclass = ALLOCNO_CLASS (a);
2705	if (aclass == NO_REGS)
2706	continue;
2707	FOR_EACH_ALLOCNO_OBJECT (a, obj, aoi)
2708	for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
2709	bitmap_set_bit (&dead_points[aclass], r->finish);
2710	}
2711	FOR_EACH_ALLOCNO (a, ai)
2712	{
2713	aclass = ALLOCNO_CLASS (a);
2714	if (aclass == NO_REGS)
2715	continue;
2716	if (! ALLOCNO_BAD_SPILL_P (a))
2717	continue;
2718	FOR_EACH_ALLOCNO_OBJECT (a, obj, aoi)
2719	{
2720	for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
2721	{
2722	for (i = r->start + 1; i < r->finish; i++)
2723	if (bitmap_bit_p (&dead_points[aclass], i))
2724	break;
2725	if (i < r->finish)
2726	break;
2727	}
2728	if (r != NULL)
2729	{
2730	ALLOCNO_BAD_SPILL_P (a) = false;
2731	break;
2732	}
2733	}
2734	}
2735	for (i = 0; i < ira_allocno_classes_num; i++)
2736	{
2737	aclass = ira_allocno_classes[i];
2738	bitmap_clear (&dead_points[aclass]);
2739	}
2740	}
2741
2742
2743
2744	/* Set up minimal and maximal live range points for allocnos. */
2745	static void
2746	setup_min_max_allocno_live_range_point (void)
2747	{
2748	int i;
2749	ira_allocno_t a, parent_a, cap;
2750	ira_allocno_iterator ai;
2751	#ifdef ENABLE_IRA_CHECKING
2752	ira_object_iterator oi;
2753	ira_object_t obj;
2754	#endif
2755	live_range_t r;
2756	ira_loop_tree_node_t parent;
2757
2758	FOR_EACH_ALLOCNO (a, ai)
2759	{
2760	int n = ALLOCNO_NUM_OBJECTS (a);
2761
2762	for (i = 0; i < n; i++)
2763	{
2764	ira_object_t obj = ALLOCNO_OBJECT (a, i);
2765	r = OBJECT_LIVE_RANGES (obj);
2766	if (r == NULL)
2767	continue;
2768	OBJECT_MAX (obj) = r->finish;
2769	for (; r->next != NULL; r = r->next)
2770	;
2771	OBJECT_MIN (obj) = r->start;
2772	}
2773	}
2774	for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
2775	for (a = ira_regno_allocno_map[i];
2776	a != NULL;
2777	a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2778	{
2779	int j;
2780	int n = ALLOCNO_NUM_OBJECTS (a);
2781
2782	for (j = 0; j < n; j++)
2783	{
2784	ira_object_t obj = ALLOCNO_OBJECT (a, j);
2785	ira_object_t parent_obj;
2786
2787	if (OBJECT_MAX (obj) < 0)
2788	{
2789	/* The object is not used and hence does not live. */
2790	ira_assert (OBJECT_LIVE_RANGES (obj) == NULL);
2791	OBJECT_MAX (obj) = 0;
2792	OBJECT_MIN (obj) = 1;
2793	continue;
2794	}
2795	ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2796	/* Accumulation of range info. */
2797	if (ALLOCNO_CAP (a) != NULL)
2798	{
2799	for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
2800	{
2801	ira_object_t cap_obj = ALLOCNO_OBJECT (cap, j);
2802	if (OBJECT_MAX (cap_obj) < OBJECT_MAX (obj))
2803	OBJECT_MAX (cap_obj) = OBJECT_MAX (obj);
2804	if (OBJECT_MIN (cap_obj) > OBJECT_MIN (obj))
2805	OBJECT_MIN (cap_obj) = OBJECT_MIN (obj);
2806	}
2807	continue;
2808	}
2809	if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL)
2810	continue;
2811	parent_a = parent->regno_allocno_map[i];
2812	parent_obj = ALLOCNO_OBJECT (parent_a, j);
2813	if (OBJECT_MAX (parent_obj) < OBJECT_MAX (obj))
2814	OBJECT_MAX (parent_obj) = OBJECT_MAX (obj);
2815	if (OBJECT_MIN (parent_obj) > OBJECT_MIN (obj))
2816	OBJECT_MIN (parent_obj) = OBJECT_MIN (obj);
2817	}
2818	}
2819	#ifdef ENABLE_IRA_CHECKING
2820	FOR_EACH_OBJECT (obj, oi)
2821	{
2822	if ((OBJECT_MIN (obj) >= 0 && OBJECT_MIN (obj) <= ira_max_point)
2823	&& (OBJECT_MAX (obj) >= 0 && OBJECT_MAX (obj) <= ira_max_point))
2824	continue;
2825	gcc_unreachable ();
2826	}
2827	#endif
2828	}
2829
2830	/* Sort allocnos according to their live ranges. Allocnos with
2831	smaller allocno class are put first unless we use priority
2832	coloring. Allocnos with the same class are ordered according
2833	their start (min). Allocnos with the same start are ordered
2834	according their finish (max). */
2835	static int
2836	object_range_compare_func (const void *v1p, const void *v2p)
2837	{
2838	int diff;
2839	ira_object_t obj1 = *(const ira_object_t *) v1p;
2840	ira_object_t obj2 = *(const ira_object_t *) v2p;
2841	ira_allocno_t a1 = OBJECT_ALLOCNO (obj1);
2842	ira_allocno_t a2 = OBJECT_ALLOCNO (obj2);
2843
2844	if ((diff = OBJECT_MIN (obj1) - OBJECT_MIN (obj2)) != 0)
2845	return diff;
2846	if ((diff = OBJECT_MAX (obj1) - OBJECT_MAX (obj2)) != 0)
2847	return diff;
2848	return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2849	}
2850
2851	/* Sort ira_object_id_map and set up conflict id of allocnos. */
2852	static void
2853	sort_conflict_id_map (void)
2854	{
2855	int i, num;
2856	ira_allocno_t a;
2857	ira_allocno_iterator ai;
2858
2859	num = 0;
2860	FOR_EACH_ALLOCNO (a, ai)
2861	{
2862	ira_allocno_object_iterator oi;
2863	ira_object_t obj;
2864
2865	FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2866	ira_object_id_map[num++] = obj;
2867	}
2868	if (num > 1)
2869	qsort (ira_object_id_map, num, sizeof (ira_object_t),
2870	object_range_compare_func);
2871	for (i = 0; i < num; i++)
2872	{
2873	ira_object_t obj = ira_object_id_map[i];
2874
2875	gcc_assert (obj != NULL);
2876	OBJECT_CONFLICT_ID (obj) = i;
2877	}
2878	for (i = num; i < ira_objects_num; i++)
2879	ira_object_id_map[i] = NULL;
2880	}
2881
2882	/* Set up minimal and maximal conflict ids of allocnos with which
2883	given allocno can conflict. */
2884	static void
2885	setup_min_max_conflict_allocno_ids (void)
2886	{
2887	int aclass;
2888	int i, j, min, max, start, finish, first_not_finished, filled_area_start;
2889	int *live_range_min, *last_lived;
2890	int word0_min, word0_max;
2891	ira_allocno_t a;
2892	ira_allocno_iterator ai;
2893
2894	live_range_min = (int *) ira_allocate (sizeof (int) * ira_objects_num);
2895	aclass = -1;
2896	first_not_finished = -1;
2897	for (i = 0; i < ira_objects_num; i++)
2898	{
2899	ira_object_t obj = ira_object_id_map[i];
2900
2901	if (obj == NULL)
2902	continue;
2903
2904	a = OBJECT_ALLOCNO (obj);
2905
2906	if (aclass < 0)
2907	{
2908	aclass = ALLOCNO_CLASS (a);
2909	min = i;
2910	first_not_finished = i;
2911	}
2912	else
2913	{
2914	start = OBJECT_MIN (obj);
2915	/* If we skip an allocno, the allocno with smaller ids will
2916	be also skipped because of the secondary sorting the
2917	range finishes (see function
2918	object_range_compare_func). */
2919	while (first_not_finished < i
2920	&& start > OBJECT_MAX (ira_object_id_map
2921	[first_not_finished]))
2922	first_not_finished++;
2923	min = first_not_finished;
2924	}
2925	if (min == i)
2926	/* We could increase min further in this case but it is good
2927	enough. */
2928	min++;
2929	live_range_min[i] = OBJECT_MIN (obj);
2930	OBJECT_MIN (obj) = min;
2931	}
2932	last_lived = (int *) ira_allocate (sizeof (int) * ira_max_point);
2933	aclass = -1;
2934	filled_area_start = -1;
2935	for (i = ira_objects_num - 1; i >= 0; i--)
2936	{
2937	ira_object_t obj = ira_object_id_map[i];
2938
2939	if (obj == NULL)
2940	continue;
2941
2942	a = OBJECT_ALLOCNO (obj);
2943	if (aclass < 0)
2944	{
2945	aclass = ALLOCNO_CLASS (a);
2946	for (j = 0; j < ira_max_point; j++)
2947	last_lived[j] = -1;
2948	filled_area_start = ira_max_point;
2949	}
2950	min = live_range_min[i];
2951	finish = OBJECT_MAX (obj);
2952	max = last_lived[finish];
2953	if (max < 0)
2954	/* We could decrease max further in this case but it is good
2955	enough. */
2956	max = OBJECT_CONFLICT_ID (obj) - 1;
2957	OBJECT_MAX (obj) = max;
2958	/* In filling, we can go further A range finish to recognize
2959	intersection quickly because if the finish of subsequently
2960	processed allocno (it has smaller conflict id) range is
2961	further A range finish than they are definitely intersected
2962	(the reason for this is the allocnos with bigger conflict id
2963	have their range starts not smaller than allocnos with
2964	smaller ids. */
2965	for (j = min; j < filled_area_start; j++)
2966	last_lived[j] = i;
2967	filled_area_start = min;
2968	}
2969	ira_free (addr: last_lived);
2970	ira_free (addr: live_range_min);
2971
2972	/* For allocnos with more than one object, we may later record extra conflicts in
2973	subobject 0 that we cannot really know about here.
2974	For now, simply widen the min/max range of these subobjects. */
2975
2976	word0_min = INT_MAX;
2977	word0_max = INT_MIN;
2978
2979	FOR_EACH_ALLOCNO (a, ai)
2980	{
2981	int n = ALLOCNO_NUM_OBJECTS (a);
2982	ira_object_t obj0;
2983
2984	if (n < 2)
2985	continue;
2986	obj0 = ALLOCNO_OBJECT (a, 0);
2987	if (OBJECT_CONFLICT_ID (obj0) < word0_min)
2988	word0_min = OBJECT_CONFLICT_ID (obj0);
2989	if (OBJECT_CONFLICT_ID (obj0) > word0_max)
2990	word0_max = OBJECT_CONFLICT_ID (obj0);
2991	}
2992	FOR_EACH_ALLOCNO (a, ai)
2993	{
2994	int n = ALLOCNO_NUM_OBJECTS (a);
2995	ira_object_t obj0;
2996
2997	if (n < 2)
2998	continue;
2999	obj0 = ALLOCNO_OBJECT (a, 0);
3000	if (OBJECT_MIN (obj0) > word0_min)
3001	OBJECT_MIN (obj0) = word0_min;
3002	if (OBJECT_MAX (obj0) < word0_max)
3003	OBJECT_MAX (obj0) = word0_max;
3004	}
3005	}
3006
3007
3008
3009	static void
3010	create_caps (void)
3011	{
3012	ira_allocno_t a;
3013	ira_allocno_iterator ai;
3014	ira_loop_tree_node_t loop_tree_node;
3015
3016	FOR_EACH_ALLOCNO (a, ai)
3017	{
3018	if (ALLOCNO_LOOP_TREE_NODE (a) == ira_loop_tree_root)
3019	continue;
3020	if (ALLOCNO_CAP_MEMBER (a) != NULL)
3021	create_cap_allocno (a);
3022	else if (ALLOCNO_CAP (a) == NULL)
3023	{
3024	loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
3025	if (!bitmap_bit_p (loop_tree_node->border_allocnos, ALLOCNO_NUM (a)))
3026	create_cap_allocno (a);
3027	}
3028	}
3029	}
3030
3031
3032
3033	/* The page contains code transforming more one region internal
3034	representation (IR) to one region IR which is necessary for reload.
3035	This transformation is called IR flattening. We might just rebuild
3036	the IR for one region but we don't do it because it takes a lot of
3037	time. */
3038
3039	/* Map: regno -> allocnos which will finally represent the regno for
3040	IR with one region. */
3041	static ira_allocno_t *regno_top_level_allocno_map;
3042
3043	/* Find the allocno that corresponds to A at a level one higher up in the
3044	loop tree. Returns NULL if A is a cap, or if it has no parent. */
3045	ira_allocno_t
3046	ira_parent_allocno (ira_allocno_t a)
3047	{
3048	ira_loop_tree_node_t parent;
3049
3050	if (ALLOCNO_CAP (a) != NULL)
3051	return NULL;
3052
3053	parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
3054	if (parent == NULL)
3055	return NULL;
3056
3057	return parent->regno_allocno_map[ALLOCNO_REGNO (a)];
3058	}
3059
3060	/* Find the allocno that corresponds to A at a level one higher up in the
3061	loop tree. If ALLOCNO_CAP is set for A, return that. */
3062	ira_allocno_t
3063	ira_parent_or_cap_allocno (ira_allocno_t a)
3064	{
3065	if (ALLOCNO_CAP (a) != NULL)
3066	return ALLOCNO_CAP (a);
3067
3068	return ira_parent_allocno (a);
3069	}
3070
3071	/* Process all allocnos originated from pseudo REGNO and copy live
3072	ranges, hard reg conflicts, and allocno stack reg attributes from
3073	low level allocnos to final allocnos which are destinations of
3074	removed stores at a loop exit. Return true if we copied live
3075	ranges. */
3076	static bool
3077	copy_info_to_removed_store_destinations (int regno)
3078	{
3079	ira_allocno_t a;
3080	ira_allocno_t parent_a = NULL;
3081	ira_loop_tree_node_t parent;
3082	bool merged_p;
3083
3084	merged_p = false;
3085	for (a = ira_regno_allocno_map[regno];
3086	a != NULL;
3087	a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
3088	{
3089	if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))])
3090	/* This allocno will be removed. */
3091	continue;
3092
3093	/* Caps will be removed. */
3094	ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
3095	for (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
3096	parent != NULL;
3097	parent = parent->parent)
3098	if ((parent_a = parent->regno_allocno_map[regno]) == NULL
3099	|| (parent_a
3100	== regno_top_level_allocno_map[REGNO
3101	(allocno_emit_reg (parent_a))]
3102	&& ALLOCNO_EMIT_DATA (parent_a)->mem_optimized_dest_p))
3103	break;
3104	if (parent == NULL || parent_a == NULL)
3105	continue;
3106
3107	copy_allocno_live_ranges (from: a, to: parent_a);
3108	merge_hard_reg_conflicts (from: a, to: parent_a, total_only: true);
3109
3110	ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
3111	ALLOCNO_CALLS_CROSSED_NUM (parent_a)
3112	+= ALLOCNO_CALLS_CROSSED_NUM (a);
3113	ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
3114	+= ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
3115	ALLOCNO_CROSSED_CALLS_ABIS (parent_a)
3116	|= ALLOCNO_CROSSED_CALLS_ABIS (a);
3117	ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (parent_a)
3118	|= ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a);
3119	ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
3120	+= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
3121	merged_p = true;
3122	}
3123	return merged_p;
3124	}
3125
3126	/* Flatten the IR. In other words, this function transforms IR as if
3127	it were built with one region (without loops). We could make it
3128	much simpler by rebuilding IR with one region, but unfortunately it
3129	takes a lot of time. MAX_REGNO_BEFORE_EMIT and
3130	IRA_MAX_POINT_BEFORE_EMIT are correspondingly MAX_REG_NUM () and
3131	IRA_MAX_POINT before emitting insns on the loop borders. */
3132	void
3133	ira_flattening (int max_regno_before_emit, int ira_max_point_before_emit)
3134	{
3135	int i, j;
3136	bool keep_p;
3137	int hard_regs_num;
3138	bool new_pseudos_p, merged_p, mem_dest_p;
3139	unsigned int n;
3140	enum reg_class aclass;
3141	ira_allocno_t a, parent_a, first, second, node_first, node_second;
3142	ira_copy_t cp;
3143	ira_loop_tree_node_t node;
3144	live_range_t r;
3145	ira_allocno_iterator ai;
3146	ira_copy_iterator ci;
3147
3148	regno_top_level_allocno_map
3149	= (ira_allocno_t *) ira_allocate (max_reg_num ()
3150	* sizeof (ira_allocno_t));
3151	memset (s: regno_top_level_allocno_map, c: 0,
3152	n: max_reg_num () * sizeof (ira_allocno_t));
3153	new_pseudos_p = merged_p = false;
3154	FOR_EACH_ALLOCNO (a, ai)
3155	{
3156	ira_allocno_object_iterator oi;
3157	ira_object_t obj;
3158
3159	if (ALLOCNO_CAP_MEMBER (a) != NULL)
3160	/* Caps are not in the regno allocno maps and they are never
3161	will be transformed into allocnos existing after IR
3162	flattening. */
3163	continue;
3164	FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
3165	OBJECT_TOTAL_CONFLICT_HARD_REGS (obj)
3166	= OBJECT_CONFLICT_HARD_REGS (obj);
3167	#ifdef STACK_REGS
3168	ALLOCNO_TOTAL_NO_STACK_REG_P (a) = ALLOCNO_NO_STACK_REG_P (a);
3169	#endif
3170	}
3171	/* Fix final allocno attributes. */
3172	for (i = max_regno_before_emit - 1; i >= FIRST_PSEUDO_REGISTER; i--)
3173	{
3174	mem_dest_p = false;
3175	for (a = ira_regno_allocno_map[i];
3176	a != NULL;
3177	a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
3178	{
3179	ira_emit_data_t parent_data, data = ALLOCNO_EMIT_DATA (a);
3180
3181	ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
3182	if (data->somewhere_renamed_p)
3183	new_pseudos_p = true;
3184	parent_a = ira_parent_allocno (a);
3185	if (parent_a == NULL)
3186	{
3187	ALLOCNO_COPIES (a) = NULL;
3188	regno_top_level_allocno_map[REGNO (data->reg)] = a;
3189	continue;
3190	}
3191	ira_assert (ALLOCNO_CAP_MEMBER (parent_a) == NULL);
3192
3193	if (data->mem_optimized_dest != NULL)
3194	mem_dest_p = true;
3195	parent_data = ALLOCNO_EMIT_DATA (parent_a);
3196	if (REGNO (data->reg) == REGNO (parent_data->reg))
3197	{
3198	merge_hard_reg_conflicts (from: a, to: parent_a, total_only: true);
3199	move_allocno_live_ranges (from: a, to: parent_a);
3200	merged_p = true;
3201	parent_data->mem_optimized_dest_p
3202	= (parent_data->mem_optimized_dest_p
3203	|| data->mem_optimized_dest_p);
3204	continue;
3205	}
3206	new_pseudos_p = true;
3207	for (;;)
3208	{
3209	ALLOCNO_NREFS (parent_a) -= ALLOCNO_NREFS (a);
3210	ALLOCNO_FREQ (parent_a) -= ALLOCNO_FREQ (a);
3211	ALLOCNO_CALL_FREQ (parent_a) -= ALLOCNO_CALL_FREQ (a);
3212	ALLOCNO_CALLS_CROSSED_NUM (parent_a)
3213	-= ALLOCNO_CALLS_CROSSED_NUM (a);
3214	ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
3215	-= ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
3216	/* Assume that ALLOCNO_CROSSED_CALLS_ABIS and
3217	ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS stay the same.
3218	We'd need to rebuild the IR to do better. */
3219	ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
3220	-= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
3221	ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a) >= 0
3222	&& ALLOCNO_NREFS (parent_a) >= 0
3223	&& ALLOCNO_FREQ (parent_a) >= 0);
3224	aclass = ALLOCNO_CLASS (parent_a);
3225	hard_regs_num = ira_class_hard_regs_num[aclass];
3226	if (ALLOCNO_HARD_REG_COSTS (a) != NULL
3227	&& ALLOCNO_HARD_REG_COSTS (parent_a) != NULL)
3228	for (j = 0; j < hard_regs_num; j++)
3229	ALLOCNO_HARD_REG_COSTS (parent_a)[j]
3230	-= ALLOCNO_HARD_REG_COSTS (a)[j];
3231	if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL
3232	&& ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a) != NULL)
3233	for (j = 0; j < hard_regs_num; j++)
3234	ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a)[j]
3235	-= ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[j];
3236	ALLOCNO_CLASS_COST (parent_a)
3237	-= ALLOCNO_CLASS_COST (a);
3238	ALLOCNO_MEMORY_COST (parent_a) -= ALLOCNO_MEMORY_COST (a);
3239	parent_a = ira_parent_allocno (a: parent_a);
3240	if (parent_a == NULL)
3241	break;
3242	}
3243	ALLOCNO_COPIES (a) = NULL;
3244	regno_top_level_allocno_map[REGNO (data->reg)] = a;
3245	}
3246	if (mem_dest_p && copy_info_to_removed_store_destinations (regno: i))
3247	merged_p = true;
3248	}
3249	ira_assert (new_pseudos_p || ira_max_point_before_emit == ira_max_point);
3250	if (merged_p || ira_max_point_before_emit != ira_max_point)
3251	ira_rebuild_start_finish_chains ();
3252	if (new_pseudos_p)
3253	{
3254	sparseset objects_live;
3255
3256	/* Rebuild conflicts. */
3257	FOR_EACH_ALLOCNO (a, ai)
3258	{
3259	ira_allocno_object_iterator oi;
3260	ira_object_t obj;
3261
3262	if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
3263	|| ALLOCNO_CAP_MEMBER (a) != NULL)
3264	continue;
3265	FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
3266	{
3267	for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
3268	ira_assert (r->object == obj);
3269	clear_conflicts (obj);
3270	}
3271	}
3272	objects_live = sparseset_alloc (n_elms: ira_objects_num);
3273	for (i = 0; i < ira_max_point; i++)
3274	{
3275	for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next)
3276	{
3277	ira_object_t obj = r->object;
3278
3279	a = OBJECT_ALLOCNO (obj);
3280	if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
3281	|| ALLOCNO_CAP_MEMBER (a) != NULL)
3282	continue;
3283
3284	aclass = ALLOCNO_CLASS (a);
3285	EXECUTE_IF_SET_IN_SPARSESET (objects_live, n)
3286	{
3287	ira_object_t live_obj = ira_object_id_map[n];
3288	ira_allocno_t live_a = OBJECT_ALLOCNO (live_obj);
3289	enum reg_class live_aclass = ALLOCNO_CLASS (live_a);
3290
3291	if (ira_reg_classes_intersect_p[aclass][live_aclass]
3292	/* Don't set up conflict for the allocno with itself. */
3293	&& live_a != a)
3294	ira_add_conflict (obj1: obj, obj2: live_obj);
3295	}
3296	sparseset_set_bit (s: objects_live, OBJECT_CONFLICT_ID (obj));
3297	}
3298
3299	for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
3300	sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (r->object));
3301	}
3302	sparseset_free (objects_live);
3303	compress_conflict_vecs ();
3304	}
3305	/* Mark some copies for removing and change allocnos in the rest
3306	copies. */
3307	FOR_EACH_COPY (cp, ci)
3308	{
3309	if (ALLOCNO_CAP_MEMBER (cp->first) != NULL
3310	|| ALLOCNO_CAP_MEMBER (cp->second) != NULL)
3311	{
3312	if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
3313	fprintf
3314	(stream: ira_dump_file, format: " Remove cp%d:%c%dr%d-%c%dr%d\n",
3315	cp->num, ALLOCNO_CAP_MEMBER (cp->first) != NULL ? 'c' : 'a',
3316	ALLOCNO_NUM (cp->first),
3317	REGNO (allocno_emit_reg (cp->first)),
3318	ALLOCNO_CAP_MEMBER (cp->second) != NULL ? 'c' : 'a',
3319	ALLOCNO_NUM (cp->second),
3320	REGNO (allocno_emit_reg (cp->second)));
3321	cp->loop_tree_node = NULL;
3322	continue;
3323	}
3324	first
3325	= regno_top_level_allocno_map[REGNO (allocno_emit_reg (cp->first))];
3326	second
3327	= regno_top_level_allocno_map[REGNO (allocno_emit_reg (cp->second))];
3328	node = cp->loop_tree_node;
3329	if (node == NULL)
3330	keep_p = true; /* It copy generated in ira-emit.cc. */
3331	else
3332	{
3333	/* Check that the copy was not propagated from level on
3334	which we will have different pseudos. */
3335	node_first = node->regno_allocno_map[ALLOCNO_REGNO (cp->first)];
3336	node_second = node->regno_allocno_map[ALLOCNO_REGNO (cp->second)];
3337	keep_p = ((REGNO (allocno_emit_reg (first))
3338	== REGNO (allocno_emit_reg (node_first)))
3339	&& (REGNO (allocno_emit_reg (second))
3340	== REGNO (allocno_emit_reg (node_second))));
3341	}
3342	if (keep_p)
3343	{
3344	cp->loop_tree_node = ira_loop_tree_root;
3345	cp->first = first;
3346	cp->second = second;
3347	}
3348	else
3349	{
3350	cp->loop_tree_node = NULL;
3351	if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
3352	fprintf (stream: ira_dump_file, format: " Remove cp%d:a%dr%d-a%dr%d\n",
3353	cp->num, ALLOCNO_NUM (cp->first),
3354	REGNO (allocno_emit_reg (cp->first)),
3355	ALLOCNO_NUM (cp->second),
3356	REGNO (allocno_emit_reg (cp->second)));
3357	}
3358	}
3359	/* Remove unnecessary allocnos on lower levels of the loop tree. */
3360	FOR_EACH_ALLOCNO (a, ai)
3361	{
3362	if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
3363	|| ALLOCNO_CAP_MEMBER (a) != NULL)
3364	{
3365	if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
3366	fprintf (stream: ira_dump_file, format: " Remove a%dr%d\n",
3367	ALLOCNO_NUM (a), REGNO (allocno_emit_reg (a)));
3368	ira_remove_allocno_prefs (a);
3369	finish_allocno (a);
3370	continue;
3371	}
3372	ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
3373	ALLOCNO_REGNO (a) = REGNO (allocno_emit_reg (a));
3374	ALLOCNO_CAP (a) = NULL;
3375	/* Restore updated costs for assignments from reload. */
3376	ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
3377	ALLOCNO_UPDATED_CLASS_COST (a) = ALLOCNO_CLASS_COST (a);
3378	if (! ALLOCNO_ASSIGNED_P (a))
3379	ira_free_allocno_updated_costs (a);
3380	ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
3381	ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
3382	}
3383	/* Remove unnecessary copies. */
3384	FOR_EACH_COPY (cp, ci)
3385	{
3386	if (cp->loop_tree_node == NULL)
3387	{
3388	ira_copies[cp->num] = NULL;
3389	finish_copy (cp);
3390	continue;
3391	}
3392	ira_assert
3393	(ALLOCNO_LOOP_TREE_NODE (cp->first) == ira_loop_tree_root
3394	&& ALLOCNO_LOOP_TREE_NODE (cp->second) == ira_loop_tree_root);
3395	add_allocno_copy_to_list (cp);
3396	swap_allocno_copy_ends_if_necessary (cp);
3397	}
3398	rebuild_regno_allocno_maps ();
3399	if (ira_max_point != ira_max_point_before_emit)
3400	ira_compress_allocno_live_ranges ();
3401	ira_free (addr: regno_top_level_allocno_map);
3402	}
3403
3404
3405
3406	#ifdef ENABLE_IRA_CHECKING
3407	/* Check creation of all allocnos. Allocnos on lower levels should
3408	have allocnos or caps on all upper levels. */
3409	static void
3410	check_allocno_creation (void)
3411	{
3412	ira_allocno_t a;
3413	ira_allocno_iterator ai;
3414	ira_loop_tree_node_t loop_tree_node;
3415
3416	FOR_EACH_ALLOCNO (a, ai)
3417	{
3418	loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
3419	ira_assert (bitmap_bit_p (loop_tree_node->all_allocnos,
3420	ALLOCNO_NUM (a)));
3421	if (loop_tree_node == ira_loop_tree_root)
3422	continue;
3423	if (ALLOCNO_CAP_MEMBER (a) != NULL)
3424	ira_assert (ALLOCNO_CAP (a) != NULL);
3425	else if (ALLOCNO_CAP (a) == NULL)
3426	ira_assert (loop_tree_node->parent
3427	->regno_allocno_map[ALLOCNO_REGNO (a)] != NULL
3428	&& bitmap_bit_p (loop_tree_node->border_allocnos,
3429	ALLOCNO_NUM (a)));
3430	}
3431	}
3432	#endif
3433
3434	/* Identify allocnos which prefer a register class with a single hard register.
3435	Adjust ALLOCNO_CONFLICT_HARD_REG_COSTS so that conflicting allocnos are
3436	less likely to use the preferred singleton register. */
3437	static void
3438	update_conflict_hard_reg_costs (void)
3439	{
3440	ira_allocno_t a;
3441	ira_allocno_iterator ai;
3442	int i, index, min;
3443
3444	FOR_EACH_ALLOCNO (a, ai)
3445	{
3446	reg_class_t aclass = ALLOCNO_CLASS (a);
3447	reg_class_t pref = reg_preferred_class (ALLOCNO_REGNO (a));
3448	int singleton = ira_class_singleton[pref][ALLOCNO_MODE (a)];
3449	if (singleton < 0)
3450	continue;
3451	index = ira_class_hard_reg_index[(int) aclass][singleton];
3452	if (index < 0)
3453	continue;
3454	if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) == NULL
3455	|| ALLOCNO_HARD_REG_COSTS (a) == NULL)
3456	continue;
3457	min = INT_MAX;
3458	for (i = ira_class_hard_regs_num[(int) aclass] - 1; i >= 0; i--)
3459	if (ALLOCNO_HARD_REG_COSTS (a)[i] > ALLOCNO_CLASS_COST (a)
3460	&& min > ALLOCNO_HARD_REG_COSTS (a)[i])
3461	min = ALLOCNO_HARD_REG_COSTS (a)[i];
3462	if (min == INT_MAX)
3463	continue;
3464	ira_allocate_and_set_costs (vec: &ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
3465	aclass, val: 0);
3466	ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index]
3467	-= min - ALLOCNO_CLASS_COST (a);
3468	}
3469	}
3470
3471	/* Create a internal representation (IR) for IRA (allocnos, copies,
3472	loop tree nodes). The function returns TRUE if we generate loop
3473	structure (besides nodes representing all function and the basic
3474	blocks) for regional allocation. A true return means that we
3475	really need to flatten IR before the reload. */
3476	bool
3477	ira_build (void)
3478	{
3479	bool loops_p;
3480
3481	df_analyze ();
3482	initiate_cost_vectors ();
3483	initiate_allocnos ();
3484	initiate_prefs ();
3485	initiate_copies ();
3486	create_loop_tree_nodes ();
3487	form_loop_tree ();
3488	create_allocnos ();
3489	ira_costs ();
3490	create_allocno_objects ();
3491	ira_create_allocno_live_ranges ();
3492	remove_unnecessary_regions (all_p: false);
3493	ira_compress_allocno_live_ranges ();
3494	update_bad_spill_attribute ();
3495	loops_p = more_one_region_p ();
3496	if (loops_p)
3497	{
3498	propagate_allocno_info ();
3499	create_caps ();
3500	}
3501	ira_tune_allocno_costs ();
3502	#ifdef ENABLE_IRA_CHECKING
3503	check_allocno_creation ();
3504	#endif
3505	setup_min_max_allocno_live_range_point ();
3506	sort_conflict_id_map ();
3507	setup_min_max_conflict_allocno_ids ();
3508	ira_build_conflicts ();
3509	update_conflict_hard_reg_costs ();
3510	if (! ira_conflicts_p)
3511	{
3512	ira_allocno_t a;
3513	ira_allocno_iterator ai;
3514
3515	/* Remove all regions but root one. */
3516	if (loops_p)
3517	{
3518	remove_unnecessary_regions (all_p: true);
3519	loops_p = false;
3520	}
3521	/* We don't save hard registers around calls for fast allocation
3522	-- add caller clobbered registers as conflicting ones to
3523	allocno crossing calls. */
3524	FOR_EACH_ALLOCNO (a, ai)
3525	if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
3526	ior_hard_reg_conflicts (a, set: ira_need_caller_save_regs (a));
3527	}
3528	if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3529	print_copies (f: ira_dump_file);
3530	if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3531	print_prefs (f: ira_dump_file);
3532	if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3533	{
3534	int n, nr, nr_big;
3535	ira_allocno_t a;
3536	live_range_t r;
3537	ira_allocno_iterator ai;
3538
3539	n = 0;
3540	nr = 0;
3541	nr_big = 0;
3542	FOR_EACH_ALLOCNO (a, ai)
3543	{
3544	int j, nobj = ALLOCNO_NUM_OBJECTS (a);
3545
3546	if (nobj > 1)
3547	nr_big++;
3548	for (j = 0; j < nobj; j++)
3549	{
3550	ira_object_t obj = ALLOCNO_OBJECT (a, j);
3551	n += OBJECT_NUM_CONFLICTS (obj);
3552	for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
3553	nr++;
3554	}
3555	}
3556	fprintf (stream: ira_dump_file, format: " regions=%d, blocks=%d, points=%d\n",
3557	current_loops == NULL ? 1 : number_of_loops (cfun),
3558	n_basic_blocks_for_fn (cfun), ira_max_point);
3559	fprintf (stream: ira_dump_file,
3560	format: " allocnos=%d (big %d), copies=%d, conflicts=%d, ranges=%d\n",
3561	ira_allocnos_num, nr_big, ira_copies_num, n, nr);
3562	}
3563	return loops_p;
3564	}
3565
3566	/* Release the data created by function ira_build. */
3567	void
3568	ira_destroy (void)
3569	{
3570	finish_loop_tree_nodes ();
3571	finish_prefs ();
3572	finish_copies ();
3573	finish_allocnos ();
3574	finish_cost_vectors ();
3575	ira_finish_allocno_live_ranges ();
3576	}
3577