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