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