1	/* Building internal representation for IRA.
2	Copyright (C) 2006-2025 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	a = ira_create_allocno (regno, cap_p: false, loop_tree_node: ira_curr_loop_tree_node);
1855
1856	/* This used to only trigger at allocno creation which seems
1857	wrong. We care about the WMODE propery across all the uses. */
1858	if (outer != NULL && GET_CODE (outer) == SUBREG)
1859	{
1860	machine_mode wmode = GET_MODE (outer);
1861	if (partial_subreg_p (ALLOCNO_WMODE (a), innermode: wmode))
1862	ALLOCNO_WMODE (a) = wmode;
1863	}
1864
1865	ALLOCNO_NREFS (a)++;
1866	ALLOCNO_FREQ (a) += REG_FREQ_FROM_BB (curr_bb);
1867	if (output_p)
1868	bitmap_set_bit (ira_curr_loop_tree_node->modified_regnos, regno);
1869	}
1870	return;
1871	}
1872	else if (code == SET)
1873	{
1874	create_insn_allocnos (SET_DEST (x), NULL, output_p: true);
1875	create_insn_allocnos (SET_SRC (x), NULL, output_p: false);
1876	return;
1877	}
1878	else if (code == CLOBBER)
1879	{
1880	create_insn_allocnos (XEXP (x, 0), NULL, output_p: true);
1881	return;
1882	}
1883	else if (code == MEM)
1884	{
1885	create_insn_allocnos (XEXP (x, 0), NULL, output_p: false);
1886	return;
1887	}
1888	else if (code == PRE_DEC || code == POST_DEC || code == PRE_INC ||
1889	code == POST_INC || code == POST_MODIFY || code == PRE_MODIFY)
1890	{
1891	create_insn_allocnos (XEXP (x, 0), NULL, output_p: true);
1892	create_insn_allocnos (XEXP (x, 0), NULL, output_p: false);
1893	return;
1894	}
1895
1896	fmt = GET_RTX_FORMAT (code);
1897	for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1898	{
1899	if (fmt[i] == 'e')
1900	create_insn_allocnos (XEXP (x, i), outer: x, output_p);
1901	else if (fmt[i] == 'E')
1902	for (j = 0; j < XVECLEN (x, i); j++)
1903	create_insn_allocnos (XVECEXP (x, i, j), outer: x, output_p);
1904	}
1905	}
1906
1907	/* Create allocnos corresponding to pseudo-registers living in the
1908	basic block represented by the corresponding loop tree node
1909	BB_NODE. */
1910	static void
1911	create_bb_allocnos (ira_loop_tree_node_t bb_node)
1912	{
1913	basic_block bb;
1914	rtx_insn *insn;
1915	unsigned int i;
1916	bitmap_iterator bi;
1917
1918	curr_bb = bb = bb_node->bb;
1919	ira_assert (bb != NULL);
1920	FOR_BB_INSNS_REVERSE (bb, insn)
1921	if (NONDEBUG_INSN_P (insn))
1922	create_insn_allocnos (x: PATTERN (insn), NULL, output_p: false);
1923	/* It might be a allocno living through from one subloop to
1924	another. */
1925	EXECUTE_IF_SET_IN_REG_SET (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, i, bi)
1926	if (ira_curr_regno_allocno_map[i] == NULL)
1927	ira_create_allocno (regno: i, cap_p: false, loop_tree_node: ira_curr_loop_tree_node);
1928	}
1929
1930	/* Create allocnos corresponding to pseudo-registers living on edge E
1931	(a loop entry or exit). Also mark the allocnos as living on the
1932	loop border. */
1933	static void
1934	create_loop_allocnos (edge e)
1935	{
1936	unsigned int i;
1937	bitmap live_in_regs, border_allocnos;
1938	bitmap_iterator bi;
1939	ira_loop_tree_node_t parent;
1940
1941	live_in_regs = df_get_live_in (bb: e->dest);
1942	border_allocnos = ira_curr_loop_tree_node->border_allocnos;
1943	EXECUTE_IF_SET_IN_REG_SET (df_get_live_out (e->src),
1944	FIRST_PSEUDO_REGISTER, i, bi)
1945	if (bitmap_bit_p (live_in_regs, i))
1946	{
1947	if (ira_curr_regno_allocno_map[i] == NULL)
1948	{
1949	/* The order of creations is important for right
1950	ira_regno_allocno_map. */
1951	if ((parent = ira_curr_loop_tree_node->parent) != NULL
1952	&& parent->regno_allocno_map[i] == NULL)
1953	ira_create_allocno (regno: i, cap_p: false, loop_tree_node: parent);
1954	ira_create_allocno (regno: i, cap_p: false, loop_tree_node: ira_curr_loop_tree_node);
1955	}
1956	bitmap_set_bit (border_allocnos,
1957	ALLOCNO_NUM (ira_curr_regno_allocno_map[i]));
1958	}
1959	}
1960
1961	/* Create allocnos corresponding to pseudo-registers living in loop
1962	represented by the corresponding loop tree node LOOP_NODE. This
1963	function is called by ira_traverse_loop_tree. */
1964	static void
1965	create_loop_tree_node_allocnos (ira_loop_tree_node_t loop_node)
1966	{
1967	if (loop_node->bb != NULL)
1968	create_bb_allocnos (bb_node: loop_node);
1969	else if (loop_node != ira_loop_tree_root)
1970	{
1971	int i;
1972	edge_iterator ei;
1973	edge e;
1974
1975	ira_assert (current_loops != NULL);
1976	FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
1977	if (e->src != loop_node->loop->latch)
1978	create_loop_allocnos (e);
1979
1980	auto_vec<edge> edges = get_loop_exit_edges (loop_node->loop);
1981	FOR_EACH_VEC_ELT (edges, i, e)
1982	create_loop_allocnos (e);
1983	}
1984	}
1985
1986	/* Propagate information about allocnos modified inside the loop given
1987	by its LOOP_TREE_NODE to its parent. */
1988	static void
1989	propagate_modified_regnos (ira_loop_tree_node_t loop_tree_node)
1990	{
1991	if (loop_tree_node == ira_loop_tree_root)
1992	return;
1993	ira_assert (loop_tree_node->bb == NULL);
1994	bitmap_ior_into (loop_tree_node->parent->modified_regnos,
1995	loop_tree_node->modified_regnos);
1996	}
1997
1998	/* Propagate ALLOCNO_HARD_REG_COSTS from A to PARENT_A. Use SPILL_COST
1999	as the cost of spilling a register throughout A (which we have to do
2000	for PARENT_A allocations that conflict with A). */
2001	static void
2002	ira_propagate_hard_reg_costs (ira_allocno_t parent_a, ira_allocno_t a,
2003	int spill_cost)
2004	{
2005	HARD_REG_SET conflicts = ira_total_conflict_hard_regs (a);
2006	if (ira_caller_save_loop_spill_p (a: parent_a, subloop_a: a, spill_cost))
2007	conflicts |= ira_need_caller_save_regs (a);
2008	conflicts &= ~ira_total_conflict_hard_regs (a: parent_a);
2009
2010	auto costs = ALLOCNO_HARD_REG_COSTS (a);
2011	if (!hard_reg_set_empty_p (x: conflicts))
2012	ALLOCNO_MIGHT_CONFLICT_WITH_PARENT_P (a) = true;
2013	else if (!costs)
2014	return;
2015
2016	auto aclass = ALLOCNO_CLASS (a);
2017	ira_allocate_and_set_costs (vec: &ALLOCNO_HARD_REG_COSTS (parent_a),
2018	aclass, ALLOCNO_CLASS_COST (parent_a));
2019	auto parent_costs = ALLOCNO_HARD_REG_COSTS (parent_a);
2020	for (int i = 0; i < ira_class_hard_regs_num[aclass]; ++i)
2021	if (TEST_HARD_REG_BIT (set: conflicts, ira_class_hard_regs[aclass][i]))
2022	parent_costs[i] += spill_cost;
2023	else if (costs)
2024	/* The cost to A of allocating this register to PARENT_A can't
2025	be more than the cost of spilling the register throughout A. */
2026	parent_costs[i] += MIN (costs[i], spill_cost);
2027	}
2028
2029	/* Propagate new info about allocno A (see comments about accumulated
2030	info in allocno definition) to the corresponding allocno on upper
2031	loop tree level. So allocnos on upper levels accumulate
2032	information about the corresponding allocnos in nested regions.
2033	The new info means allocno info finally calculated in this
2034	file. */
2035	static void
2036	propagate_allocno_info (void)
2037	{
2038	int i;
2039	ira_allocno_t a, parent_a;
2040	ira_loop_tree_node_t parent;
2041	enum reg_class aclass;
2042
2043	if (flag_ira_region != IRA_REGION_ALL
2044	&& flag_ira_region != IRA_REGION_MIXED)
2045	return;
2046	for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
2047	for (a = ira_regno_allocno_map[i];
2048	a != NULL;
2049	a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2050	if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL
2051	&& (parent_a = parent->regno_allocno_map[i]) != NULL
2052	/* There are no caps yet at this point. So use
2053	border_allocnos to find allocnos for the propagation. */
2054	&& bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE (a)->border_allocnos,
2055	ALLOCNO_NUM (a)))
2056	{
2057	/* Calculate the cost of storing to memory on entry to A's loop,
2058	referencing as memory within A's loop, and restoring from
2059	memory on exit from A's loop. */
2060	ira_loop_border_costs border_costs (a);
2061	int spill_cost = INT_MAX;
2062	if (ira_subloop_allocnos_can_differ_p (a: parent_a))
2063	spill_cost = (border_costs.spill_inside_loop_cost ()
2064	+ ALLOCNO_MEMORY_COST (a));
2065
2066	if (! ALLOCNO_BAD_SPILL_P (a))
2067	ALLOCNO_BAD_SPILL_P (parent_a) = false;
2068	ALLOCNO_NREFS (parent_a) += ALLOCNO_NREFS (a);
2069	ALLOCNO_FREQ (parent_a) += ALLOCNO_FREQ (a);
2070	ALLOCNO_SET_REGISTER_FILTERS (parent_a,
2071	ALLOCNO_REGISTER_FILTERS (parent_a)
2072	| ALLOCNO_REGISTER_FILTERS (a));
2073
2074	/* If A's allocation can differ from PARENT_A's, we can if necessary
2075	spill PARENT_A on entry to A's loop and restore it afterwards.
2076	Doing that has cost SPILL_COST. */
2077	if (!ira_subloop_allocnos_can_differ_p (a: parent_a))
2078	merge_hard_reg_conflicts (from: a, to: parent_a, total_only: true);
2079
2080	if (!ira_caller_save_loop_spill_p (a: parent_a, subloop_a: a, spill_cost))
2081	{
2082	ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
2083	ALLOCNO_CALLS_CROSSED_NUM (parent_a)
2084	+= ALLOCNO_CALLS_CROSSED_NUM (a);
2085	ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
2086	+= ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
2087	ALLOCNO_CROSSED_CALLS_ABIS (parent_a)
2088	|= ALLOCNO_CROSSED_CALLS_ABIS (a);
2089	ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (parent_a)
2090	|= ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a);
2091	}
2092	ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
2093	+= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2094	aclass = ALLOCNO_CLASS (a);
2095	ira_assert (aclass == ALLOCNO_CLASS (parent_a));
2096	ira_propagate_hard_reg_costs (parent_a, a, spill_cost);
2097	ira_allocate_and_accumulate_costs
2098	(vec: &ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a),
2099	aclass,
2100	ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
2101	/* The cost to A of allocating a register to PARENT_A can't be
2102	more than the cost of spilling the register throughout A. */
2103	ALLOCNO_CLASS_COST (parent_a)
2104	+= MIN (ALLOCNO_CLASS_COST (a), spill_cost);
2105	ALLOCNO_MEMORY_COST (parent_a) += ALLOCNO_MEMORY_COST (a);
2106	}
2107	}
2108
2109	/* Create allocnos corresponding to pseudo-registers in the current
2110	function. Traverse the loop tree for this. */
2111	static void
2112	create_allocnos (void)
2113	{
2114	/* We need to process BB first to correctly link allocnos by member
2115	next_regno_allocno. */
2116	ira_traverse_loop_tree (bb_p: true, loop_node: ira_loop_tree_root,
2117	preorder_func: create_loop_tree_node_allocnos, NULL);
2118	if (optimize)
2119	ira_traverse_loop_tree (bb_p: false, loop_node: ira_loop_tree_root, NULL,
2120	postorder_func: propagate_modified_regnos);
2121	}
2122
2123
2124
2125	/* The page contains function to remove some regions from a separate
2126	register allocation. We remove regions whose separate allocation
2127	will hardly improve the result. As a result we speed up regional
2128	register allocation. */
2129
2130	/* The function changes the object in range list given by R to OBJ. */
2131	static void
2132	change_object_in_range_list (live_range_t r, ira_object_t obj)
2133	{
2134	for (; r != NULL; r = r->next)
2135	r->object = obj;
2136	}
2137
2138	/* Move all live ranges associated with allocno FROM to allocno TO. */
2139	static void
2140	move_allocno_live_ranges (ira_allocno_t from, ira_allocno_t to)
2141	{
2142	int i;
2143	int n = ALLOCNO_NUM_OBJECTS (from);
2144
2145	gcc_assert (n == ALLOCNO_NUM_OBJECTS (to));
2146
2147	for (i = 0; i < n; i++)
2148	{
2149	ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
2150	ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
2151	live_range_t lr = OBJECT_LIVE_RANGES (from_obj);
2152
2153	if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2154	{
2155	fprintf (stream: ira_dump_file,
2156	format: " Moving ranges of a%dr%d to a%dr%d: ",
2157	ALLOCNO_NUM (from), ALLOCNO_REGNO (from),
2158	ALLOCNO_NUM (to), ALLOCNO_REGNO (to));
2159	ira_print_live_range_list (ira_dump_file, lr);
2160	}
2161	change_object_in_range_list (r: lr, obj: to_obj);
2162	OBJECT_LIVE_RANGES (to_obj)
2163	= ira_merge_live_ranges (r1: lr, OBJECT_LIVE_RANGES (to_obj));
2164	OBJECT_LIVE_RANGES (from_obj) = NULL;
2165	}
2166	}
2167
2168	static void
2169	copy_allocno_live_ranges (ira_allocno_t from, ira_allocno_t to)
2170	{
2171	int i;
2172	int n = ALLOCNO_NUM_OBJECTS (from);
2173
2174	gcc_assert (n == ALLOCNO_NUM_OBJECTS (to));
2175
2176	for (i = 0; i < n; i++)
2177	{
2178	ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
2179	ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
2180	live_range_t lr = OBJECT_LIVE_RANGES (from_obj);
2181
2182	if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2183	{
2184	fprintf (stream: ira_dump_file, format: " Copying ranges of a%dr%d to a%dr%d: ",
2185	ALLOCNO_NUM (from), ALLOCNO_REGNO (from),
2186	ALLOCNO_NUM (to), ALLOCNO_REGNO (to));
2187	ira_print_live_range_list (ira_dump_file, lr);
2188	}
2189	lr = ira_copy_live_range_list (r: lr);
2190	change_object_in_range_list (r: lr, obj: to_obj);
2191	OBJECT_LIVE_RANGES (to_obj)
2192	= ira_merge_live_ranges (r1: lr, OBJECT_LIVE_RANGES (to_obj));
2193	}
2194	}
2195
2196	/* Return TRUE if NODE represents a loop with low register
2197	pressure. */
2198	static bool
2199	low_pressure_loop_node_p (ira_loop_tree_node_t node)
2200	{
2201	int i;
2202	enum reg_class pclass;
2203
2204	if (node->bb != NULL)
2205	return false;
2206
2207	for (i = 0; i < ira_pressure_classes_num; i++)
2208	{
2209	pclass = ira_pressure_classes[i];
2210	if (node->reg_pressure[pclass] > ira_class_hard_regs_num[pclass]
2211	&& ira_class_hard_regs_num[pclass] > 1)
2212	return false;
2213	}
2214	return true;
2215	}
2216
2217	#ifdef STACK_REGS
2218	/* Return TRUE if LOOP has a complex enter or exit edge. We don't
2219	form a region from such loop if the target use stack register
2220	because reg-stack.cc cannot deal with such edges. */
2221	static bool
2222	loop_with_complex_edge_p (class loop *loop)
2223	{
2224	int i;
2225	edge_iterator ei;
2226	edge e;
2227	bool res;
2228
2229	FOR_EACH_EDGE (e, ei, loop->header->preds)
2230	if (e->flags & EDGE_EH)
2231	return true;
2232	auto_vec<edge> edges = get_loop_exit_edges (loop);
2233	res = false;
2234	FOR_EACH_VEC_ELT (edges, i, e)
2235	if (e->flags & EDGE_COMPLEX)
2236	{
2237	res = true;
2238	break;
2239	}
2240	return res;
2241	}
2242	#endif
2243
2244	/* Sort loops for marking them for removal. We put already marked
2245	loops first, then less frequent loops next, and then outer loops
2246	next. */
2247	static int
2248	loop_compare_func (const void *v1p, const void *v2p)
2249	{
2250	int diff;
2251	ira_loop_tree_node_t l1 = *(const ira_loop_tree_node_t *) v1p;
2252	ira_loop_tree_node_t l2 = *(const ira_loop_tree_node_t *) v2p;
2253
2254	ira_assert (l1->parent != NULL && l2->parent != NULL);
2255	if (l1->to_remove_p && ! l2->to_remove_p)
2256	return -1;
2257	if (! l1->to_remove_p && l2->to_remove_p)
2258	return 1;
2259	if ((diff = l1->loop->header->count.to_frequency (cfun)
2260	- l2->loop->header->count.to_frequency (cfun)) != 0)
2261	return diff;
2262	if ((diff = (int) loop_depth (loop: l1->loop) - (int) loop_depth (loop: l2->loop)) != 0)
2263	return diff;
2264	/* Make sorting stable. */
2265	return l1->loop_num - l2->loop_num;
2266	}
2267
2268	/* Mark loops which should be removed from regional allocation. We
2269	remove a loop with low register pressure inside another loop with
2270	register pressure. In this case a separate allocation of the loop
2271	hardly helps (for irregular register file architecture it could
2272	help by choosing a better hard register in the loop but we prefer
2273	faster allocation even in this case). We also remove cheap loops
2274	if there are more than param_ira_max_loops_num of them. Loop with EH
2275	exit or enter edges are removed too because the allocation might
2276	require put pseudo moves on the EH edges (we could still do this
2277	for pseudos with caller saved hard registers in some cases but it
2278	is impossible to say here or during top-down allocation pass what
2279	hard register the pseudos get finally). */
2280	static void
2281	mark_loops_for_removal (void)
2282	{
2283	int i, n;
2284	ira_loop_tree_node_t *sorted_loops;
2285	loop_p loop;
2286
2287	ira_assert (current_loops != NULL);
2288	sorted_loops
2289	= (ira_loop_tree_node_t *) ira_allocate (sizeof (ira_loop_tree_node_t)
2290	* number_of_loops (cfun));
2291	for (n = i = 0; vec_safe_iterate (v: get_loops (cfun), ix: i, ptr: &loop); i++)
2292	if (ira_loop_nodes[i].regno_allocno_map != NULL)
2293	{
2294	if (ira_loop_nodes[i].parent == NULL)
2295	{
2296	/* Don't remove the root. */
2297	ira_loop_nodes[i].to_remove_p = false;
2298	continue;
2299	}
2300	sorted_loops[n++] = &ira_loop_nodes[i];
2301	ira_loop_nodes[i].to_remove_p
2302	= ((low_pressure_loop_node_p (node: ira_loop_nodes[i].parent)
2303	&& low_pressure_loop_node_p (node: &ira_loop_nodes[i]))
2304	#ifdef STACK_REGS
2305	|| loop_with_complex_edge_p (loop: ira_loop_nodes[i].loop)
2306	#endif
2307	);
2308	}
2309	qsort (sorted_loops, n, sizeof (ira_loop_tree_node_t), loop_compare_func);
2310	for (i = 0; i < n - param_ira_max_loops_num; i++)
2311	{
2312	sorted_loops[i]->to_remove_p = true;
2313	if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2314	fprintf
2315	(stream: ira_dump_file,
2316	format: " Mark loop %d (header %d, freq %d, depth %d) for removal (%s)\n",
2317	sorted_loops[i]->loop_num, sorted_loops[i]->loop->header->index,
2318	sorted_loops[i]->loop->header->count.to_frequency (cfun),
2319	loop_depth (loop: sorted_loops[i]->loop),
2320	low_pressure_loop_node_p (node: sorted_loops[i]->parent)
2321	&& low_pressure_loop_node_p (node: sorted_loops[i])
2322	? "low pressure" : "cheap loop");
2323	}
2324	ira_free (addr: sorted_loops);
2325	}
2326
2327	/* Mark all loops but root for removing. */
2328	static void
2329	mark_all_loops_for_removal (void)
2330	{
2331	int i;
2332	loop_p loop;
2333
2334	ira_assert (current_loops != NULL);
2335	FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
2336	if (ira_loop_nodes[i].regno_allocno_map != NULL)
2337	{
2338	if (ira_loop_nodes[i].parent == NULL)
2339	{
2340	/* Don't remove the root. */
2341	ira_loop_nodes[i].to_remove_p = false;
2342	continue;
2343	}
2344	ira_loop_nodes[i].to_remove_p = true;
2345	if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2346	fprintf
2347	(stream: ira_dump_file,
2348	format: " Mark loop %d (header %d, freq %d, depth %d) for removal\n",
2349	ira_loop_nodes[i].loop_num,
2350	ira_loop_nodes[i].loop->header->index,
2351	ira_loop_nodes[i].loop->header->count.to_frequency (cfun),
2352	loop_depth (loop: ira_loop_nodes[i].loop));
2353	}
2354	}
2355
2356	/* Definition of vector of loop tree nodes. */
2357
2358	/* Vec containing references to all removed loop tree nodes. */
2359	static vec<ira_loop_tree_node_t> removed_loop_vec;
2360
2361	/* Vec containing references to all children of loop tree nodes. */
2362	static vec<ira_loop_tree_node_t> children_vec;
2363
2364	/* Remove subregions of NODE if their separate allocation will not
2365	improve the result. */
2366	static void
2367	remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_node_t node)
2368	{
2369	unsigned int start;
2370	bool remove_p;
2371	ira_loop_tree_node_t subnode;
2372
2373	remove_p = node->to_remove_p;
2374	if (! remove_p)
2375	children_vec.safe_push (obj: node);
2376	start = children_vec.length ();
2377	for (subnode = node->children; subnode != NULL; subnode = subnode->next)
2378	if (subnode->bb == NULL)
2379	remove_uneccesary_loop_nodes_from_loop_tree (node: subnode);
2380	else
2381	children_vec.safe_push (obj: subnode);
2382	node->children = node->subloops = NULL;
2383	if (remove_p)
2384	{
2385	removed_loop_vec.safe_push (obj: node);
2386	return;
2387	}
2388	while (children_vec.length () > start)
2389	{
2390	subnode = children_vec.pop ();
2391	subnode->parent = node;
2392	subnode->next = node->children;
2393	node->children = subnode;
2394	if (subnode->bb == NULL)
2395	{
2396	subnode->subloop_next = node->subloops;
2397	node->subloops = subnode;
2398	}
2399	}
2400	}
2401
2402	/* Return TRUE if NODE is inside PARENT. */
2403	static bool
2404	loop_is_inside_p (ira_loop_tree_node_t node, ira_loop_tree_node_t parent)
2405	{
2406	for (node = node->parent; node != NULL; node = node->parent)
2407	if (node == parent)
2408	return true;
2409	return false;
2410	}
2411
2412	/* Sort allocnos according to their order in regno allocno list. */
2413	static int
2414	regno_allocno_order_compare_func (const void *v1p, const void *v2p)
2415	{
2416	ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2417	ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2418	ira_loop_tree_node_t n1 = ALLOCNO_LOOP_TREE_NODE (a1);
2419	ira_loop_tree_node_t n2 = ALLOCNO_LOOP_TREE_NODE (a2);
2420
2421	if (loop_is_inside_p (node: n1, parent: n2))
2422	return -1;
2423	else if (loop_is_inside_p (node: n2, parent: n1))
2424	return 1;
2425	/* If allocnos are equally good, sort by allocno numbers, so that
2426	the results of qsort leave nothing to chance. We put allocnos
2427	with higher number first in the list because it is the original
2428	order for allocnos from loops on the same levels. */
2429	return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
2430	}
2431
2432	/* This array is used to sort allocnos to restore allocno order in
2433	the regno allocno list. */
2434	static ira_allocno_t *regno_allocnos;
2435
2436	/* Restore allocno order for REGNO in the regno allocno list. */
2437	static void
2438	ira_rebuild_regno_allocno_list (int regno)
2439	{
2440	int i, n;
2441	ira_allocno_t a;
2442
2443	for (n = 0, a = ira_regno_allocno_map[regno];
2444	a != NULL;
2445	a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2446	regno_allocnos[n++] = a;
2447	ira_assert (n > 0);
2448	qsort (regno_allocnos, n, sizeof (ira_allocno_t),
2449	regno_allocno_order_compare_func);
2450	for (i = 1; i < n; i++)
2451	ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[i - 1]) = regno_allocnos[i];
2452	ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[n - 1]) = NULL;
2453	ira_regno_allocno_map[regno] = regno_allocnos[0];
2454	if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2455	fprintf (stream: ira_dump_file, format: " Rebuilding regno allocno list for %d\n", regno);
2456	}
2457
2458	/* Propagate info from allocno FROM_A to allocno A. */
2459	static void
2460	propagate_some_info_from_allocno (ira_allocno_t a, ira_allocno_t from_a)
2461	{
2462	enum reg_class aclass;
2463
2464	merge_hard_reg_conflicts (from: from_a, to: a, total_only: false);
2465	ALLOCNO_NREFS (a) += ALLOCNO_NREFS (from_a);
2466	ALLOCNO_FREQ (a) += ALLOCNO_FREQ (from_a);
2467	ALLOCNO_CALL_FREQ (a) += ALLOCNO_CALL_FREQ (from_a);
2468	ALLOCNO_CALLS_CROSSED_NUM (a) += ALLOCNO_CALLS_CROSSED_NUM (from_a);
2469	ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a)
2470	+= ALLOCNO_CHEAP_CALLS_CROSSED_NUM (from_a);
2471	ALLOCNO_CROSSED_CALLS_ABIS (a) |= ALLOCNO_CROSSED_CALLS_ABIS (from_a);
2472	ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a)
2473	|= ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (from_a);
2474	ALLOCNO_SET_REGISTER_FILTERS (a,
2475	ALLOCNO_REGISTER_FILTERS (from_a)
2476	| ALLOCNO_REGISTER_FILTERS (a));
2477
2478	ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a)
2479	+= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (from_a);
2480	if (! ALLOCNO_BAD_SPILL_P (from_a))
2481	ALLOCNO_BAD_SPILL_P (a) = false;
2482	aclass = ALLOCNO_CLASS (from_a);
2483	ira_assert (aclass == ALLOCNO_CLASS (a));
2484	ira_allocate_and_accumulate_costs (vec: &ALLOCNO_HARD_REG_COSTS (a), aclass,
2485	ALLOCNO_HARD_REG_COSTS (from_a));
2486	ira_allocate_and_accumulate_costs (vec: &ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
2487	aclass,
2488	ALLOCNO_CONFLICT_HARD_REG_COSTS (from_a));
2489	ALLOCNO_CLASS_COST (a) += ALLOCNO_CLASS_COST (from_a);
2490	ALLOCNO_MEMORY_COST (a) += ALLOCNO_MEMORY_COST (from_a);
2491	}
2492
2493	/* Remove allocnos from loops removed from the allocation
2494	consideration. */
2495	static void
2496	remove_unnecessary_allocnos (void)
2497	{
2498	int regno;
2499	bool merged_p, rebuild_p;
2500	ira_allocno_t a, prev_a, next_a, parent_a;
2501	ira_loop_tree_node_t a_node, parent;
2502
2503	merged_p = false;
2504	regno_allocnos = NULL;
2505	for (regno = max_reg_num () - 1; regno >= FIRST_PSEUDO_REGISTER; regno--)
2506	{
2507	rebuild_p = false;
2508	for (prev_a = NULL, a = ira_regno_allocno_map[regno];
2509	a != NULL;
2510	a = next_a)
2511	{
2512	next_a = ALLOCNO_NEXT_REGNO_ALLOCNO (a);
2513	a_node = ALLOCNO_LOOP_TREE_NODE (a);
2514	if (! a_node->to_remove_p)
2515	prev_a = a;
2516	else
2517	{
2518	for (parent = a_node->parent;
2519	(parent_a = parent->regno_allocno_map[regno]) == NULL
2520	&& parent->to_remove_p;
2521	parent = parent->parent)
2522	;
2523	if (parent_a == NULL)
2524	{
2525	/* There are no allocnos with the same regno in
2526	upper region -- just move the allocno to the
2527	upper region. */
2528	prev_a = a;
2529	ALLOCNO_LOOP_TREE_NODE (a) = parent;
2530	parent->regno_allocno_map[regno] = a;
2531	bitmap_set_bit (parent->all_allocnos, ALLOCNO_NUM (a));
2532	rebuild_p = true;
2533	}
2534	else
2535	{
2536	/* Remove the allocno and update info of allocno in
2537	the upper region. */
2538	if (prev_a == NULL)
2539	ira_regno_allocno_map[regno] = next_a;
2540	else
2541	ALLOCNO_NEXT_REGNO_ALLOCNO (prev_a) = next_a;
2542	move_allocno_live_ranges (from: a, to: parent_a);
2543	merged_p = true;
2544	propagate_some_info_from_allocno (a: parent_a, from_a: a);
2545	/* Remove it from the corresponding regno allocno
2546	map to avoid info propagation of subsequent
2547	allocno into this already removed allocno. */
2548	a_node->regno_allocno_map[regno] = NULL;
2549	ira_remove_allocno_prefs (a);
2550	finish_allocno (a);
2551	}
2552	}
2553	}
2554	if (rebuild_p)
2555	/* We need to restore the order in regno allocno list. */
2556	{
2557	if (regno_allocnos == NULL)
2558	regno_allocnos
2559	= (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
2560	* ira_allocnos_num);
2561	ira_rebuild_regno_allocno_list (regno);
2562	}
2563	}
2564	if (merged_p)
2565	ira_rebuild_start_finish_chains ();
2566	if (regno_allocnos != NULL)
2567	ira_free (addr: regno_allocnos);
2568	}
2569
2570	/* Remove allocnos from all loops but the root. */
2571	static void
2572	remove_low_level_allocnos (void)
2573	{
2574	int regno;
2575	bool merged_p, propagate_p;
2576	ira_allocno_t a, top_a;
2577	ira_loop_tree_node_t a_node, parent;
2578	ira_allocno_iterator ai;
2579
2580	merged_p = false;
2581	FOR_EACH_ALLOCNO (a, ai)
2582	{
2583	a_node = ALLOCNO_LOOP_TREE_NODE (a);
2584	if (a_node == ira_loop_tree_root || ALLOCNO_CAP_MEMBER (a) != NULL)
2585	continue;
2586	regno = ALLOCNO_REGNO (a);
2587	if ((top_a = ira_loop_tree_root->regno_allocno_map[regno]) == NULL)
2588	{
2589	ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
2590	ira_loop_tree_root->regno_allocno_map[regno] = a;
2591	continue;
2592	}
2593	propagate_p = a_node->parent->regno_allocno_map[regno] == NULL;
2594	/* Remove the allocno and update info of allocno in the upper
2595	region. */
2596	move_allocno_live_ranges (from: a, to: top_a);
2597	merged_p = true;
2598	if (propagate_p)
2599	propagate_some_info_from_allocno (a: top_a, from_a: a);
2600	}
2601	FOR_EACH_ALLOCNO (a, ai)
2602	{
2603	a_node = ALLOCNO_LOOP_TREE_NODE (a);
2604	if (a_node == ira_loop_tree_root)
2605	continue;
2606	parent = a_node->parent;
2607	regno = ALLOCNO_REGNO (a);
2608	if (ALLOCNO_CAP_MEMBER (a) != NULL)
2609	ira_assert (ALLOCNO_CAP (a) != NULL);
2610	else if (ALLOCNO_CAP (a) == NULL)
2611	ira_assert (parent->regno_allocno_map[regno] != NULL);
2612	}
2613	FOR_EACH_ALLOCNO (a, ai)
2614	{
2615	regno = ALLOCNO_REGNO (a);
2616	if (ira_loop_tree_root->regno_allocno_map[regno] == a)
2617	{
2618	ira_object_t obj;
2619	ira_allocno_object_iterator oi;
2620
2621	ira_regno_allocno_map[regno] = a;
2622	ALLOCNO_NEXT_REGNO_ALLOCNO (a) = NULL;
2623	ALLOCNO_CAP_MEMBER (a) = NULL;
2624	FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2625	OBJECT_CONFLICT_HARD_REGS (obj)
2626	= OBJECT_TOTAL_CONFLICT_HARD_REGS (obj);
2627	#ifdef STACK_REGS
2628	if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
2629	ALLOCNO_NO_STACK_REG_P (a) = true;
2630	#endif
2631	}
2632	else
2633	{
2634	ira_remove_allocno_prefs (a);
2635	finish_allocno (a);
2636	}
2637	}
2638	if (merged_p)
2639	ira_rebuild_start_finish_chains ();
2640	}
2641
2642	/* Remove loops from consideration. We remove all loops except for
2643	root if ALL_P or loops for which a separate allocation will not
2644	improve the result. We have to do this after allocno creation and
2645	their costs and allocno class evaluation because only after that
2646	the register pressure can be known and is calculated. */
2647	static void
2648	remove_unnecessary_regions (bool all_p)
2649	{
2650	if (current_loops == NULL)
2651	return;
2652	if (all_p)
2653	mark_all_loops_for_removal ();
2654	else
2655	mark_loops_for_removal ();
2656	children_vec.create (last_basic_block_for_fn (cfun)
2657	+ number_of_loops (cfun));
2658	removed_loop_vec.create (last_basic_block_for_fn (cfun)
2659	+ number_of_loops (cfun));
2660	remove_uneccesary_loop_nodes_from_loop_tree (node: ira_loop_tree_root);
2661	children_vec.release ();
2662	if (all_p)
2663	remove_low_level_allocnos ();
2664	else
2665	remove_unnecessary_allocnos ();
2666	while (removed_loop_vec.length () > 0)
2667	finish_loop_tree_node (loop: removed_loop_vec.pop ());
2668	removed_loop_vec.release ();
2669	}
2670
2671
2672
2673	/* At this point true value of allocno attribute bad_spill_p means
2674	that there is an insn where allocno occurs and where the allocno
2675	cannot be used as memory. The function updates the attribute, now
2676	it can be true only for allocnos which cannot be used as memory in
2677	an insn and in whose live ranges there is other allocno deaths.
2678	Spilling allocnos with true value will not improve the code because
2679	it will not make other allocnos colorable and additional reloads
2680	for the corresponding pseudo will be generated in reload pass for
2681	each insn it occurs.
2682
2683	This is a trick mentioned in one classic article of Chaitin etc
2684	which is frequently omitted in other implementations of RA based on
2685	graph coloring. */
2686	static void
2687	update_bad_spill_attribute (void)
2688	{
2689	int i;
2690	ira_allocno_t a;
2691	ira_allocno_iterator ai;
2692	ira_allocno_object_iterator aoi;
2693	ira_object_t obj;
2694	live_range_t r;
2695	enum reg_class aclass;
2696	bitmap_head dead_points[N_REG_CLASSES];
2697
2698	for (i = 0; i < ira_allocno_classes_num; i++)
2699	{
2700	aclass = ira_allocno_classes[i];
2701	bitmap_initialize (head: &dead_points[aclass], obstack: &reg_obstack);
2702	}
2703	FOR_EACH_ALLOCNO (a, ai)
2704	{
2705	aclass = ALLOCNO_CLASS (a);
2706	if (aclass == NO_REGS)
2707	continue;
2708	FOR_EACH_ALLOCNO_OBJECT (a, obj, aoi)
2709	for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
2710	bitmap_set_bit (&dead_points[aclass], r->finish);
2711	}
2712	FOR_EACH_ALLOCNO (a, ai)
2713	{
2714	aclass = ALLOCNO_CLASS (a);
2715	if (aclass == NO_REGS)
2716	continue;
2717	if (! ALLOCNO_BAD_SPILL_P (a))
2718	continue;
2719	FOR_EACH_ALLOCNO_OBJECT (a, obj, aoi)
2720	{
2721	for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
2722	{
2723	for (i = r->start + 1; i < r->finish; i++)
2724	if (bitmap_bit_p (&dead_points[aclass], i))
2725	break;
2726	if (i < r->finish)
2727	break;
2728	}
2729	if (r != NULL)
2730	{
2731	ALLOCNO_BAD_SPILL_P (a) = false;
2732	break;
2733	}
2734	}
2735	}
2736	for (i = 0; i < ira_allocno_classes_num; i++)
2737	{
2738	aclass = ira_allocno_classes[i];
2739	bitmap_clear (&dead_points[aclass]);
2740	}
2741	}
2742
2743
2744
2745	/* Set up minimal and maximal live range points for allocnos. */
2746	static void
2747	setup_min_max_allocno_live_range_point (void)
2748	{
2749	int i;
2750	ira_allocno_t a, parent_a, cap;
2751	ira_allocno_iterator ai;
2752	#ifdef ENABLE_IRA_CHECKING
2753	ira_object_iterator oi;
2754	ira_object_t obj;
2755	#endif
2756	live_range_t r;
2757	ira_loop_tree_node_t parent;
2758
2759	FOR_EACH_ALLOCNO (a, ai)
2760	{
2761	int n = ALLOCNO_NUM_OBJECTS (a);
2762
2763	for (i = 0; i < n; i++)
2764	{
2765	ira_object_t obj = ALLOCNO_OBJECT (a, i);
2766	r = OBJECT_LIVE_RANGES (obj);
2767	if (r == NULL)
2768	continue;
2769	OBJECT_MAX (obj) = r->finish;
2770	for (; r->next != NULL; r = r->next)
2771	;
2772	OBJECT_MIN (obj) = r->start;
2773	}
2774	}
2775	for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
2776	for (a = ira_regno_allocno_map[i];
2777	a != NULL;
2778	a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2779	{
2780	int j;
2781	int n = ALLOCNO_NUM_OBJECTS (a);
2782
2783	for (j = 0; j < n; j++)
2784	{
2785	ira_object_t obj = ALLOCNO_OBJECT (a, j);
2786	ira_object_t parent_obj;
2787
2788	if (OBJECT_MAX (obj) < 0)
2789	{
2790	/* The object is not used and hence does not live. */
2791	ira_assert (OBJECT_LIVE_RANGES (obj) == NULL);
2792	OBJECT_MAX (obj) = 0;
2793	OBJECT_MIN (obj) = 1;
2794	continue;
2795	}
2796	ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2797	/* Accumulation of range info. */
2798	if (ALLOCNO_CAP (a) != NULL)
2799	{
2800	for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
2801	{
2802	ira_object_t cap_obj = ALLOCNO_OBJECT (cap, j);
2803	if (OBJECT_MAX (cap_obj) < OBJECT_MAX (obj))
2804	OBJECT_MAX (cap_obj) = OBJECT_MAX (obj);
2805	if (OBJECT_MIN (cap_obj) > OBJECT_MIN (obj))
2806	OBJECT_MIN (cap_obj) = OBJECT_MIN (obj);
2807	}
2808	continue;
2809	}
2810	if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL)
2811	continue;
2812	parent_a = parent->regno_allocno_map[i];
2813	parent_obj = ALLOCNO_OBJECT (parent_a, j);
2814	if (OBJECT_MAX (parent_obj) < OBJECT_MAX (obj))
2815	OBJECT_MAX (parent_obj) = OBJECT_MAX (obj);
2816	if (OBJECT_MIN (parent_obj) > OBJECT_MIN (obj))
2817	OBJECT_MIN (parent_obj) = OBJECT_MIN (obj);
2818	}
2819	}
2820	#ifdef ENABLE_IRA_CHECKING
2821	FOR_EACH_OBJECT (obj, oi)
2822	{
2823	if ((OBJECT_MIN (obj) >= 0 && OBJECT_MIN (obj) <= ira_max_point)
2824	&& (OBJECT_MAX (obj) >= 0 && OBJECT_MAX (obj) <= ira_max_point))
2825	continue;
2826	gcc_unreachable ();
2827	}
2828	#endif
2829	}
2830
2831	/* Sort allocnos according to their live ranges. Allocnos with
2832	smaller allocno class are put first unless we use priority
2833	coloring. Allocnos with the same class are ordered according
2834	their start (min). Allocnos with the same start are ordered
2835	according their finish (max). */
2836	static int
2837	object_range_compare_func (const void *v1p, const void *v2p)
2838	{
2839	int diff;
2840	ira_object_t obj1 = *(const ira_object_t *) v1p;
2841	ira_object_t obj2 = *(const ira_object_t *) v2p;
2842	ira_allocno_t a1 = OBJECT_ALLOCNO (obj1);
2843	ira_allocno_t a2 = OBJECT_ALLOCNO (obj2);
2844
2845	if ((diff = OBJECT_MIN (obj1) - OBJECT_MIN (obj2)) != 0)
2846	return diff;
2847	if ((diff = OBJECT_MAX (obj1) - OBJECT_MAX (obj2)) != 0)
2848	return diff;
2849	return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2850	}
2851
2852	/* Sort ira_object_id_map and set up conflict id of allocnos. */
2853	static void
2854	sort_conflict_id_map (void)
2855	{
2856	int i, num;
2857	ira_allocno_t a;
2858	ira_allocno_iterator ai;
2859
2860	num = 0;
2861	FOR_EACH_ALLOCNO (a, ai)
2862	{
2863	ira_allocno_object_iterator oi;
2864	ira_object_t obj;
2865
2866	FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2867	ira_object_id_map[num++] = obj;
2868	}
2869	if (num > 1)
2870	qsort (ira_object_id_map, num, sizeof (ira_object_t),
2871	object_range_compare_func);
2872	for (i = 0; i < num; i++)
2873	{
2874	ira_object_t obj = ira_object_id_map[i];
2875
2876	gcc_assert (obj != NULL);
2877	OBJECT_CONFLICT_ID (obj) = i;
2878	}
2879	for (i = num; i < ira_objects_num; i++)
2880	ira_object_id_map[i] = NULL;
2881	}
2882
2883	/* Set up minimal and maximal conflict ids of allocnos with which
2884	given allocno can conflict. */
2885	static void
2886	setup_min_max_conflict_allocno_ids (void)
2887	{
2888	int aclass;
2889	int i, j, min, max, start, finish, first_not_finished, filled_area_start;
2890	int *live_range_min, *last_lived;
2891	int word0_min, word0_max;
2892	ira_allocno_t a;
2893	ira_allocno_iterator ai;
2894
2895	live_range_min = (int *) ira_allocate (sizeof (int) * ira_objects_num);
2896	aclass = -1;
2897	first_not_finished = -1;
2898	for (i = 0; i < ira_objects_num; i++)
2899	{
2900	ira_object_t obj = ira_object_id_map[i];
2901
2902	if (obj == NULL)
2903	continue;
2904
2905	a = OBJECT_ALLOCNO (obj);
2906
2907	if (aclass < 0)
2908	{
2909	aclass = ALLOCNO_CLASS (a);
2910	min = i;
2911	first_not_finished = i;
2912	}
2913	else
2914	{
2915	start = OBJECT_MIN (obj);
2916	/* If we skip an allocno, the allocno with smaller ids will
2917	be also skipped because of the secondary sorting the
2918	range finishes (see function
2919	object_range_compare_func). */
2920	while (first_not_finished < i
2921	&& start > OBJECT_MAX (ira_object_id_map
2922	[first_not_finished]))
2923	first_not_finished++;
2924	min = first_not_finished;
2925	}
2926	if (min == i)
2927	/* We could increase min further in this case but it is good
2928	enough. */
2929	min++;
2930	live_range_min[i] = OBJECT_MIN (obj);
2931	OBJECT_MIN (obj) = min;
2932	}
2933	last_lived = (int *) ira_allocate (sizeof (int) * ira_max_point);
2934	aclass = -1;
2935	filled_area_start = -1;
2936	for (i = ira_objects_num - 1; i >= 0; i--)
2937	{
2938	ira_object_t obj = ira_object_id_map[i];
2939
2940	if (obj == NULL)
2941	continue;
2942
2943	a = OBJECT_ALLOCNO (obj);
2944	if (aclass < 0)
2945	{
2946	aclass = ALLOCNO_CLASS (a);
2947	for (j = 0; j < ira_max_point; j++)
2948	last_lived[j] = -1;
2949	filled_area_start = ira_max_point;
2950	}
2951	min = live_range_min[i];
2952	finish = OBJECT_MAX (obj);
2953	max = last_lived[finish];
2954	if (max < 0)
2955	/* We could decrease max further in this case but it is good
2956	enough. */
2957	max = OBJECT_CONFLICT_ID (obj) - 1;
2958	OBJECT_MAX (obj) = max;
2959	/* In filling, we can go further A range finish to recognize
2960	intersection quickly because if the finish of subsequently
2961	processed allocno (it has smaller conflict id) range is
2962	further A range finish than they are definitely intersected
2963	(the reason for this is the allocnos with bigger conflict id
2964	have their range starts not smaller than allocnos with
2965	smaller ids. */
2966	for (j = min; j < filled_area_start; j++)
2967	last_lived[j] = i;
2968	filled_area_start = min;
2969	}
2970	ira_free (addr: last_lived);
2971	ira_free (addr: live_range_min);
2972
2973	/* For allocnos with more than one object, we may later record extra conflicts in
2974	subobject 0 that we cannot really know about here.
2975	For now, simply widen the min/max range of these subobjects. */
2976
2977	word0_min = INT_MAX;
2978	word0_max = INT_MIN;
2979
2980	FOR_EACH_ALLOCNO (a, ai)
2981	{
2982	int n = ALLOCNO_NUM_OBJECTS (a);
2983	ira_object_t obj0;
2984
2985	if (n < 2)
2986	continue;
2987	obj0 = ALLOCNO_OBJECT (a, 0);
2988	if (OBJECT_CONFLICT_ID (obj0) < word0_min)
2989	word0_min = OBJECT_CONFLICT_ID (obj0);
2990	if (OBJECT_CONFLICT_ID (obj0) > word0_max)
2991	word0_max = OBJECT_CONFLICT_ID (obj0);
2992	}
2993	FOR_EACH_ALLOCNO (a, ai)
2994	{
2995	int n = ALLOCNO_NUM_OBJECTS (a);
2996	ira_object_t obj0;
2997
2998	if (n < 2)
2999	continue;
3000	obj0 = ALLOCNO_OBJECT (a, 0);
3001	if (OBJECT_MIN (obj0) > word0_min)
3002	OBJECT_MIN (obj0) = word0_min;
3003	if (OBJECT_MAX (obj0) < word0_max)
3004	OBJECT_MAX (obj0) = word0_max;
3005	}
3006	}
3007
3008
3009
3010	static void
3011	create_caps (void)
3012	{
3013	ira_allocno_t a;
3014	ira_allocno_iterator ai;
3015	ira_loop_tree_node_t loop_tree_node;
3016
3017	FOR_EACH_ALLOCNO (a, ai)
3018	{
3019	if (ALLOCNO_LOOP_TREE_NODE (a) == ira_loop_tree_root)
3020	continue;
3021	if (ALLOCNO_CAP_MEMBER (a) != NULL)
3022	create_cap_allocno (a);
3023	else if (ALLOCNO_CAP (a) == NULL)
3024	{
3025	loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
3026	if (!bitmap_bit_p (loop_tree_node->border_allocnos, ALLOCNO_NUM (a)))
3027	create_cap_allocno (a);
3028	}
3029	}
3030	}
3031
3032
3033
3034	/* The page contains code transforming more one region internal
3035	representation (IR) to one region IR which is necessary for reload.
3036	This transformation is called IR flattening. We might just rebuild
3037	the IR for one region but we don't do it because it takes a lot of
3038	time. */
3039
3040	/* Map: regno -> allocnos which will finally represent the regno for
3041	IR with one region. */
3042	static ira_allocno_t *regno_top_level_allocno_map;
3043
3044	/* Find the allocno that corresponds to A at a level one higher up in the
3045	loop tree. Returns NULL if A is a cap, or if it has no parent. */
3046	ira_allocno_t
3047	ira_parent_allocno (ira_allocno_t a)
3048	{
3049	ira_loop_tree_node_t parent;
3050
3051	if (ALLOCNO_CAP (a) != NULL)
3052	return NULL;
3053
3054	parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
3055	if (parent == NULL)
3056	return NULL;
3057
3058	return parent->regno_allocno_map[ALLOCNO_REGNO (a)];
3059	}
3060
3061	/* Find the allocno that corresponds to A at a level one higher up in the
3062	loop tree. If ALLOCNO_CAP is set for A, return that. */
3063	ira_allocno_t
3064	ira_parent_or_cap_allocno (ira_allocno_t a)
3065	{
3066	if (ALLOCNO_CAP (a) != NULL)
3067	return ALLOCNO_CAP (a);
3068
3069	return ira_parent_allocno (a);
3070	}
3071
3072	/* Process all allocnos originated from pseudo REGNO and copy live
3073	ranges, hard reg conflicts, and allocno stack reg attributes from
3074	low level allocnos to final allocnos which are destinations of
3075	removed stores at a loop exit. Return true if we copied live
3076	ranges. */
3077	static bool
3078	copy_info_to_removed_store_destinations (int regno)
3079	{
3080	ira_allocno_t a;
3081	ira_allocno_t parent_a = NULL;
3082	ira_loop_tree_node_t parent;
3083	bool merged_p;
3084
3085	merged_p = false;
3086	for (a = ira_regno_allocno_map[regno];
3087	a != NULL;
3088	a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
3089	{
3090	if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))])
3091	/* This allocno will be removed. */
3092	continue;
3093
3094	/* Caps will be removed. */
3095	ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
3096	for (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
3097	parent != NULL;
3098	parent = parent->parent)
3099	if ((parent_a = parent->regno_allocno_map[regno]) == NULL
3100	|| (parent_a
3101	== regno_top_level_allocno_map[REGNO
3102	(allocno_emit_reg (parent_a))]
3103	&& ALLOCNO_EMIT_DATA (parent_a)->mem_optimized_dest_p))
3104	break;
3105	if (parent == NULL || parent_a == NULL)
3106	continue;
3107
3108	copy_allocno_live_ranges (from: a, to: parent_a);
3109	merge_hard_reg_conflicts (from: a, to: parent_a, total_only: true);
3110
3111	ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
3112	ALLOCNO_CALLS_CROSSED_NUM (parent_a)
3113	+= ALLOCNO_CALLS_CROSSED_NUM (a);
3114	ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
3115	+= ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
3116	ALLOCNO_CROSSED_CALLS_ABIS (parent_a)
3117	|= ALLOCNO_CROSSED_CALLS_ABIS (a);
3118	ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (parent_a)
3119	|= ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a);
3120	ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
3121	+= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
3122	merged_p = true;
3123	}
3124	return merged_p;
3125	}
3126
3127	/* Flatten the IR. In other words, this function transforms IR as if
3128	it were built with one region (without loops). We could make it
3129	much simpler by rebuilding IR with one region, but unfortunately it
3130	takes a lot of time. MAX_REGNO_BEFORE_EMIT and
3131	IRA_MAX_POINT_BEFORE_EMIT are correspondingly MAX_REG_NUM () and
3132	IRA_MAX_POINT before emitting insns on the loop borders. */
3133	void
3134	ira_flattening (int max_regno_before_emit, int ira_max_point_before_emit)
3135	{
3136	int i, j;
3137	bool keep_p;
3138	int hard_regs_num;
3139	bool new_pseudos_p, merged_p, mem_dest_p;
3140	unsigned int n;
3141	enum reg_class aclass;
3142	ira_allocno_t a, parent_a, first, second, node_first, node_second;
3143	ira_copy_t cp;
3144	ira_loop_tree_node_t node;
3145	live_range_t r;
3146	ira_allocno_iterator ai;
3147	ira_copy_iterator ci;
3148
3149	regno_top_level_allocno_map
3150	= (ira_allocno_t *) ira_allocate (max_reg_num ()
3151	* sizeof (ira_allocno_t));
3152	memset (s: regno_top_level_allocno_map, c: 0,
3153	n: max_reg_num () * sizeof (ira_allocno_t));
3154	new_pseudos_p = merged_p = false;
3155	FOR_EACH_ALLOCNO (a, ai)
3156	{
3157	ira_allocno_object_iterator oi;
3158	ira_object_t obj;
3159
3160	if (ALLOCNO_CAP_MEMBER (a) != NULL)
3161	/* Caps are not in the regno allocno maps and they are never
3162	will be transformed into allocnos existing after IR
3163	flattening. */
3164	continue;
3165	FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
3166	OBJECT_TOTAL_CONFLICT_HARD_REGS (obj)
3167	= OBJECT_CONFLICT_HARD_REGS (obj);
3168	#ifdef STACK_REGS
3169	ALLOCNO_TOTAL_NO_STACK_REG_P (a) = ALLOCNO_NO_STACK_REG_P (a);
3170	#endif
3171	}
3172	/* Fix final allocno attributes. */
3173	for (i = max_regno_before_emit - 1; i >= FIRST_PSEUDO_REGISTER; i--)
3174	{
3175	mem_dest_p = false;
3176	for (a = ira_regno_allocno_map[i];
3177	a != NULL;
3178	a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
3179	{
3180	ira_emit_data_t parent_data, data = ALLOCNO_EMIT_DATA (a);
3181
3182	ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
3183	if (data->somewhere_renamed_p)
3184	new_pseudos_p = true;
3185	parent_a = ira_parent_allocno (a);
3186	if (parent_a == NULL)
3187	{
3188	ALLOCNO_COPIES (a) = NULL;
3189	regno_top_level_allocno_map[REGNO (data->reg)] = a;
3190	continue;
3191	}
3192	ira_assert (ALLOCNO_CAP_MEMBER (parent_a) == NULL);
3193
3194	if (data->mem_optimized_dest != NULL)
3195	mem_dest_p = true;
3196	parent_data = ALLOCNO_EMIT_DATA (parent_a);
3197	if (REGNO (data->reg) == REGNO (parent_data->reg))
3198	{
3199	merge_hard_reg_conflicts (from: a, to: parent_a, total_only: true);
3200	move_allocno_live_ranges (from: a, to: parent_a);
3201	merged_p = true;
3202	parent_data->mem_optimized_dest_p
3203	= (parent_data->mem_optimized_dest_p
3204	|| data->mem_optimized_dest_p);
3205	continue;
3206	}
3207	new_pseudos_p = true;
3208	for (;;)
3209	{
3210	ALLOCNO_NREFS (parent_a) -= ALLOCNO_NREFS (a);
3211	ALLOCNO_FREQ (parent_a) -= ALLOCNO_FREQ (a);
3212	ALLOCNO_CALL_FREQ (parent_a) -= ALLOCNO_CALL_FREQ (a);
3213	ALLOCNO_CALLS_CROSSED_NUM (parent_a)
3214	-= ALLOCNO_CALLS_CROSSED_NUM (a);
3215	ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
3216	-= ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
3217	/* Assume that ALLOCNO_CROSSED_CALLS_ABIS and
3218	ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS stay the same.
3219	We'd need to rebuild the IR to do better. */
3220	ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
3221	-= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
3222	ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a) >= 0
3223	&& ALLOCNO_NREFS (parent_a) >= 0
3224	&& ALLOCNO_FREQ (parent_a) >= 0);
3225	aclass = ALLOCNO_CLASS (parent_a);
3226	hard_regs_num = ira_class_hard_regs_num[aclass];
3227	if (ALLOCNO_HARD_REG_COSTS (a) != NULL
3228	&& ALLOCNO_HARD_REG_COSTS (parent_a) != NULL)
3229	for (j = 0; j < hard_regs_num; j++)
3230	ALLOCNO_HARD_REG_COSTS (parent_a)[j]
3231	-= ALLOCNO_HARD_REG_COSTS (a)[j];
3232	if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL
3233	&& ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a) != NULL)
3234	for (j = 0; j < hard_regs_num; j++)
3235	ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a)[j]
3236	-= ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[j];
3237	ALLOCNO_CLASS_COST (parent_a)
3238	-= ALLOCNO_CLASS_COST (a);
3239	ALLOCNO_MEMORY_COST (parent_a) -= ALLOCNO_MEMORY_COST (a);
3240	parent_a = ira_parent_allocno (a: parent_a);
3241	if (parent_a == NULL)
3242	break;
3243	}
3244	ALLOCNO_COPIES (a) = NULL;
3245	regno_top_level_allocno_map[REGNO (data->reg)] = a;
3246	}
3247	if (mem_dest_p && copy_info_to_removed_store_destinations (regno: i))
3248	merged_p = true;
3249	}
3250	ira_assert (new_pseudos_p || ira_max_point_before_emit == ira_max_point);
3251	if (merged_p || ira_max_point_before_emit != ira_max_point)
3252	ira_rebuild_start_finish_chains ();
3253	if (new_pseudos_p)
3254	{
3255	sparseset objects_live;
3256
3257	/* Rebuild conflicts. */
3258	FOR_EACH_ALLOCNO (a, ai)
3259	{
3260	ira_allocno_object_iterator oi;
3261	ira_object_t obj;
3262
3263	if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
3264	|| ALLOCNO_CAP_MEMBER (a) != NULL)
3265	continue;
3266	FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
3267	{
3268	for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
3269	ira_assert (r->object == obj);
3270	clear_conflicts (obj);
3271	}
3272	}
3273	objects_live = sparseset_alloc (n_elms: ira_objects_num);
3274	for (i = 0; i < ira_max_point; i++)
3275	{
3276	for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next)
3277	{
3278	ira_object_t obj = r->object;
3279
3280	a = OBJECT_ALLOCNO (obj);
3281	if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
3282	|| ALLOCNO_CAP_MEMBER (a) != NULL)
3283	continue;
3284
3285	aclass = ALLOCNO_CLASS (a);
3286	EXECUTE_IF_SET_IN_SPARSESET (objects_live, n)
3287	{
3288	ira_object_t live_obj = ira_object_id_map[n];
3289	ira_allocno_t live_a = OBJECT_ALLOCNO (live_obj);
3290	enum reg_class live_aclass = ALLOCNO_CLASS (live_a);
3291
3292	if (ira_reg_classes_intersect_p[aclass][live_aclass]
3293	/* Don't set up conflict for the allocno with itself. */
3294	&& live_a != a)
3295	ira_add_conflict (obj1: obj, obj2: live_obj);
3296	}
3297	sparseset_set_bit (s: objects_live, OBJECT_CONFLICT_ID (obj));
3298	}
3299
3300	for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
3301	sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (r->object));
3302	}
3303	sparseset_free (objects_live);
3304	compress_conflict_vecs ();
3305	}
3306	/* Mark some copies for removing and change allocnos in the rest
3307	copies. */
3308	FOR_EACH_COPY (cp, ci)
3309	{
3310	if (ALLOCNO_CAP_MEMBER (cp->first) != NULL
3311	|| ALLOCNO_CAP_MEMBER (cp->second) != NULL)
3312	{
3313	if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
3314	fprintf
3315	(stream: ira_dump_file, format: " Remove cp%d:%c%dr%d-%c%dr%d\n",
3316	cp->num, ALLOCNO_CAP_MEMBER (cp->first) != NULL ? 'c' : 'a',
3317	ALLOCNO_NUM (cp->first),
3318	REGNO (allocno_emit_reg (cp->first)),
3319	ALLOCNO_CAP_MEMBER (cp->second) != NULL ? 'c' : 'a',
3320	ALLOCNO_NUM (cp->second),
3321	REGNO (allocno_emit_reg (cp->second)));
3322	cp->loop_tree_node = NULL;
3323	continue;
3324	}
3325	first
3326	= regno_top_level_allocno_map[REGNO (allocno_emit_reg (cp->first))];
3327	second
3328	= regno_top_level_allocno_map[REGNO (allocno_emit_reg (cp->second))];
3329	node = cp->loop_tree_node;
3330	if (node == NULL)
3331	keep_p = true; /* It copy generated in ira-emit.cc. */
3332	else
3333	{
3334	/* Check that the copy was not propagated from level on
3335	which we will have different pseudos. */
3336	node_first = node->regno_allocno_map[ALLOCNO_REGNO (cp->first)];
3337	node_second = node->regno_allocno_map[ALLOCNO_REGNO (cp->second)];
3338	keep_p = ((REGNO (allocno_emit_reg (first))
3339	== REGNO (allocno_emit_reg (node_first)))
3340	&& (REGNO (allocno_emit_reg (second))
3341	== REGNO (allocno_emit_reg (node_second))));
3342	}
3343	if (keep_p)
3344	{
3345	cp->loop_tree_node = ira_loop_tree_root;
3346	cp->first = first;
3347	cp->second = second;
3348	}
3349	else
3350	{
3351	cp->loop_tree_node = NULL;
3352	if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
3353	fprintf (stream: ira_dump_file, format: " Remove cp%d:a%dr%d-a%dr%d\n",
3354	cp->num, ALLOCNO_NUM (cp->first),
3355	REGNO (allocno_emit_reg (cp->first)),
3356	ALLOCNO_NUM (cp->second),
3357	REGNO (allocno_emit_reg (cp->second)));
3358	}
3359	}
3360	/* Remove unnecessary allocnos on lower levels of the loop tree. */
3361	FOR_EACH_ALLOCNO (a, ai)
3362	{
3363	if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
3364	|| ALLOCNO_CAP_MEMBER (a) != NULL)
3365	{
3366	if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
3367	fprintf (stream: ira_dump_file, format: " Remove a%dr%d\n",
3368	ALLOCNO_NUM (a), REGNO (allocno_emit_reg (a)));
3369	ira_remove_allocno_prefs (a);
3370	finish_allocno (a);
3371	continue;
3372	}
3373	ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
3374	ALLOCNO_REGNO (a) = REGNO (allocno_emit_reg (a));
3375	ALLOCNO_CAP (a) = NULL;
3376	/* Restore updated costs for assignments from reload. */
3377	ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
3378	ALLOCNO_UPDATED_CLASS_COST (a) = ALLOCNO_CLASS_COST (a);
3379	if (! ALLOCNO_ASSIGNED_P (a))
3380	ira_free_allocno_updated_costs (a);
3381	ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
3382	ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
3383	}
3384	/* Remove unnecessary copies. */
3385	FOR_EACH_COPY (cp, ci)
3386	{
3387	if (cp->loop_tree_node == NULL)
3388	{
3389	ira_copies[cp->num] = NULL;
3390	finish_copy (cp);
3391	continue;
3392	}
3393	ira_assert
3394	(ALLOCNO_LOOP_TREE_NODE (cp->first) == ira_loop_tree_root
3395	&& ALLOCNO_LOOP_TREE_NODE (cp->second) == ira_loop_tree_root);
3396	add_allocno_copy_to_list (cp);
3397	swap_allocno_copy_ends_if_necessary (cp);
3398	}
3399	rebuild_regno_allocno_maps ();
3400	if (ira_max_point != ira_max_point_before_emit)
3401	ira_compress_allocno_live_ranges ();
3402	ira_free (addr: regno_top_level_allocno_map);
3403	}
3404
3405
3406
3407	#ifdef ENABLE_IRA_CHECKING
3408	/* Check creation of all allocnos. Allocnos on lower levels should
3409	have allocnos or caps on all upper levels. */
3410	static void
3411	check_allocno_creation (void)
3412	{
3413	ira_allocno_t a;
3414	ira_allocno_iterator ai;
3415	ira_loop_tree_node_t loop_tree_node;
3416
3417	FOR_EACH_ALLOCNO (a, ai)
3418	{
3419	loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
3420	ira_assert (bitmap_bit_p (loop_tree_node->all_allocnos,
3421	ALLOCNO_NUM (a)));
3422	if (loop_tree_node == ira_loop_tree_root)
3423	continue;
3424	if (ALLOCNO_CAP_MEMBER (a) != NULL)
3425	ira_assert (ALLOCNO_CAP (a) != NULL);
3426	else if (ALLOCNO_CAP (a) == NULL)
3427	ira_assert (loop_tree_node->parent
3428	->regno_allocno_map[ALLOCNO_REGNO (a)] != NULL
3429	&& bitmap_bit_p (loop_tree_node->border_allocnos,
3430	ALLOCNO_NUM (a)));
3431	}
3432	}
3433	#endif
3434
3435	/* Identify allocnos which prefer a register class with a single hard register.
3436	Adjust ALLOCNO_CONFLICT_HARD_REG_COSTS so that conflicting allocnos are
3437	less likely to use the preferred singleton register. */
3438	static void
3439	update_conflict_hard_reg_costs (void)
3440	{
3441	ira_allocno_t a;
3442	ira_allocno_iterator ai;
3443	int i, index, min;
3444
3445	FOR_EACH_ALLOCNO (a, ai)
3446	{
3447	reg_class_t aclass = ALLOCNO_CLASS (a);
3448	reg_class_t pref = reg_preferred_class (ALLOCNO_REGNO (a));
3449	int singleton = ira_class_singleton[pref][ALLOCNO_MODE (a)];
3450	if (singleton < 0)
3451	continue;
3452	index = ira_class_hard_reg_index[(int) aclass][singleton];
3453	if (index < 0)
3454	continue;
3455	if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) == NULL
3456	|| ALLOCNO_HARD_REG_COSTS (a) == NULL)
3457	continue;
3458	min = INT_MAX;
3459	for (i = ira_class_hard_regs_num[(int) aclass] - 1; i >= 0; i--)
3460	if (ALLOCNO_HARD_REG_COSTS (a)[i] > ALLOCNO_CLASS_COST (a)
3461	&& min > ALLOCNO_HARD_REG_COSTS (a)[i])
3462	min = ALLOCNO_HARD_REG_COSTS (a)[i];
3463	if (min == INT_MAX)
3464	continue;
3465	ira_allocate_and_set_costs (vec: &ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
3466	aclass, val: 0);
3467	ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index]
3468	-= min - ALLOCNO_CLASS_COST (a);
3469	}
3470	}
3471
3472	/* Create a internal representation (IR) for IRA (allocnos, copies,
3473	loop tree nodes). The function returns TRUE if we generate loop
3474	structure (besides nodes representing all function and the basic
3475	blocks) for regional allocation. A true return means that we
3476	really need to flatten IR before the reload. */
3477	bool
3478	ira_build (void)
3479	{
3480	bool loops_p;
3481
3482	df_analyze ();
3483	initiate_cost_vectors ();
3484	initiate_allocnos ();
3485	initiate_prefs ();
3486	initiate_copies ();
3487	create_loop_tree_nodes ();
3488	form_loop_tree ();
3489	create_allocnos ();
3490	ira_costs ();
3491	create_allocno_objects ();
3492	ira_create_allocno_live_ranges ();
3493	remove_unnecessary_regions (all_p: false);
3494	ira_compress_allocno_live_ranges ();
3495	update_bad_spill_attribute ();
3496	loops_p = more_one_region_p ();
3497	if (loops_p)
3498	{
3499	propagate_allocno_info ();
3500	create_caps ();
3501	}
3502	ira_tune_allocno_costs ();
3503	#ifdef ENABLE_IRA_CHECKING
3504	check_allocno_creation ();
3505	#endif
3506	setup_min_max_allocno_live_range_point ();
3507	sort_conflict_id_map ();
3508	setup_min_max_conflict_allocno_ids ();
3509	ira_build_conflicts ();
3510	update_conflict_hard_reg_costs ();
3511	if (! ira_conflicts_p)
3512	{
3513	ira_allocno_t a;
3514	ira_allocno_iterator ai;
3515
3516	/* Remove all regions but root one. */
3517	if (loops_p)
3518	{
3519	remove_unnecessary_regions (all_p: true);
3520	loops_p = false;
3521	}
3522	/* We don't save hard registers around calls for fast allocation
3523	-- add caller clobbered registers as conflicting ones to
3524	allocno crossing calls. */
3525	FOR_EACH_ALLOCNO (a, ai)
3526	if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
3527	ior_hard_reg_conflicts (a, set: ira_need_caller_save_regs (a));
3528	}
3529	if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3530	print_copies (f: ira_dump_file);
3531	if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3532	print_prefs (f: ira_dump_file);
3533	if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3534	{
3535	int n, nr, nr_big;
3536	ira_allocno_t a;
3537	live_range_t r;
3538	ira_allocno_iterator ai;
3539
3540	n = 0;
3541	nr = 0;
3542	nr_big = 0;
3543	FOR_EACH_ALLOCNO (a, ai)
3544	{
3545	int j, nobj = ALLOCNO_NUM_OBJECTS (a);
3546
3547	if (nobj > 1)
3548	nr_big++;
3549	for (j = 0; j < nobj; j++)
3550	{
3551	ira_object_t obj = ALLOCNO_OBJECT (a, j);
3552	n += OBJECT_NUM_CONFLICTS (obj);
3553	for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
3554	nr++;
3555	}
3556	}
3557	fprintf (stream: ira_dump_file, format: " regions=%d, blocks=%d, points=%d\n",
3558	current_loops == NULL ? 1 : number_of_loops (cfun),
3559	n_basic_blocks_for_fn (cfun), ira_max_point);
3560	fprintf (stream: ira_dump_file,
3561	format: " allocnos=%d (big %d), copies=%d, conflicts=%d, ranges=%d\n",
3562	ira_allocnos_num, nr_big, ira_copies_num, n, nr);
3563	}
3564	return loops_p;
3565	}
3566
3567	/* Release the data created by function ira_build. */
3568	void
3569	ira_destroy (void)
3570	{
3571	finish_loop_tree_nodes ();
3572	finish_prefs ();
3573	finish_copies ();
3574	finish_allocnos ();
3575	finish_cost_vectors ();
3576	ira_finish_allocno_live_ranges ();
3577	}
3578