1 /* Building internal representation for IRA.
2 Copyright (C) 2006-2016 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5 This file is part of GCC.
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
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
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/>. */
23 #include "coretypes.h"
29 #include "insn-config.h"
34 #include "sparseset.h"
37 static ira_copy_t find_allocno_copy (ira_allocno_t, ira_allocno_t, rtx_insn *,
38 ira_loop_tree_node_t);
40 /* The root of the loop tree corresponding to the all function. */
41 ira_loop_tree_node_t ira_loop_tree_root;
43 /* Height of the loop tree. */
44 int ira_loop_tree_height;
46 /* All nodes representing basic blocks are referred through the
47 following array. We can not 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;
51 /* All nodes representing loops are referred through the following
53 ira_loop_tree_node_t ira_loop_nodes;
55 /* And size of the ira_loop_nodes array. */
56 unsigned int ira_loop_nodes_count;
58 /* Map regno -> allocnos with given regno (see comments for
59 allocno member `next_regno_allocno'). */
60 ira_allocno_t *ira_regno_allocno_map;
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;
67 /* Sizes of the previous array. */
70 /* Count of conflict record structures we've created, used when creating
74 /* Map a conflict id to its conflict record. */
75 ira_object_t *ira_object_id_map;
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;
81 /* Size of the previous array. */
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
87 ira_copy_t *ira_copies;
89 /* Size of the previous array. */
94 /* LAST_BASIC_BLOCK before generating additional insns because of live
95 range splitting. Emitting insns on a critical edge creates a new
97 static int last_basic_block_before_change;
99 /* Initialize some members in loop tree node NODE. Use LOOP_NUM for
100 the member loop_num. */
102 init_loop_tree_node (struct ira_loop_tree_node *node, int loop_num)
104 int max_regno = max_reg_num ();
106 node->regno_allocno_map
107 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t) * max_regno);
108 memset (node->regno_allocno_map, 0, sizeof (ira_allocno_t) * max_regno);
109 memset (node->reg_pressure, 0, sizeof (node->reg_pressure));
110 node->all_allocnos = ira_allocate_bitmap ();
111 node->modified_regnos = ira_allocate_bitmap ();
112 node->border_allocnos = ira_allocate_bitmap ();
113 node->local_copies = ira_allocate_bitmap ();
114 node->loop_num = loop_num;
115 node->children = NULL;
116 node->subloops = NULL;
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. */
125 create_loop_tree_nodes (void)
135 = ((struct ira_loop_tree_node *)
136 ira_allocate (sizeof (struct ira_loop_tree_node)
137 * last_basic_block_for_fn (cfun)));
138 last_basic_block_before_change = last_basic_block_for_fn (cfun);
139 for (i = 0; i < (unsigned int) last_basic_block_for_fn (cfun); i++)
141 ira_bb_nodes[i].regno_allocno_map = NULL;
142 memset (ira_bb_nodes[i].reg_pressure, 0,
143 sizeof (ira_bb_nodes[i].reg_pressure));
144 ira_bb_nodes[i].all_allocnos = NULL;
145 ira_bb_nodes[i].modified_regnos = NULL;
146 ira_bb_nodes[i].border_allocnos = NULL;
147 ira_bb_nodes[i].local_copies = NULL;
149 if (current_loops == NULL)
151 ira_loop_nodes_count = 1;
152 ira_loop_nodes = ((struct ira_loop_tree_node *)
153 ira_allocate (sizeof (struct ira_loop_tree_node)));
154 init_loop_tree_node (ira_loop_nodes, 0);
157 ira_loop_nodes_count = number_of_loops (cfun);
158 ira_loop_nodes = ((struct ira_loop_tree_node *)
159 ira_allocate (sizeof (struct ira_loop_tree_node)
160 * ira_loop_nodes_count));
161 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
163 if (loop_outer (loop) != NULL)
165 ira_loop_nodes[i].regno_allocno_map = NULL;
167 FOR_EACH_EDGE (e, ei, loop->header->preds)
168 if (e->src != loop->latch
169 && (e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
176 edges = get_loop_exit_edges (loop);
177 FOR_EACH_VEC_ELT (edges, j, e)
178 if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
187 init_loop_tree_node (&ira_loop_nodes[i], loop->num);
191 /* The function returns TRUE if there are more one allocation
194 more_one_region_p (void)
199 if (current_loops != NULL)
200 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
201 if (ira_loop_nodes[i].regno_allocno_map != NULL
202 && ira_loop_tree_root != &ira_loop_nodes[i])
207 /* Free the loop tree node of a loop. */
209 finish_loop_tree_node (ira_loop_tree_node_t loop)
211 if (loop->regno_allocno_map != NULL)
213 ira_assert (loop->bb == NULL);
214 ira_free_bitmap (loop->local_copies);
215 ira_free_bitmap (loop->border_allocnos);
216 ira_free_bitmap (loop->modified_regnos);
217 ira_free_bitmap (loop->all_allocnos);
218 ira_free (loop->regno_allocno_map);
219 loop->regno_allocno_map = NULL;
223 /* Free the loop tree nodes. */
225 finish_loop_tree_nodes (void)
229 for (i = 0; i < ira_loop_nodes_count; i++)
230 finish_loop_tree_node (&ira_loop_nodes[i]);
231 ira_free (ira_loop_nodes);
232 for (i = 0; i < (unsigned int) last_basic_block_before_change; i++)
234 if (ira_bb_nodes[i].local_copies != NULL)
235 ira_free_bitmap (ira_bb_nodes[i].local_copies);
236 if (ira_bb_nodes[i].border_allocnos != NULL)
237 ira_free_bitmap (ira_bb_nodes[i].border_allocnos);
238 if (ira_bb_nodes[i].modified_regnos != NULL)
239 ira_free_bitmap (ira_bb_nodes[i].modified_regnos);
240 if (ira_bb_nodes[i].all_allocnos != NULL)
241 ira_free_bitmap (ira_bb_nodes[i].all_allocnos);
242 if (ira_bb_nodes[i].regno_allocno_map != NULL)
243 ira_free (ira_bb_nodes[i].regno_allocno_map);
245 ira_free (ira_bb_nodes);
250 /* The following recursive function adds LOOP to the loop tree
251 hierarchy. LOOP is added only once. If LOOP is NULL we adding
252 loop designating the whole function when CFG loops are not
255 add_loop_to_tree (struct loop *loop)
259 ira_loop_tree_node_t loop_node, parent_node;
261 /* We can not use loop node access macros here because of potential
262 checking and because the nodes are not initialized enough
264 if (loop != NULL && loop_outer (loop) != NULL)
265 add_loop_to_tree (loop_outer (loop));
266 loop_num = loop != NULL ? loop->num : 0;
267 if (ira_loop_nodes[loop_num].regno_allocno_map != NULL
268 && ira_loop_nodes[loop_num].children == NULL)
270 /* We have not added loop node to the tree yet. */
271 loop_node = &ira_loop_nodes[loop_num];
272 loop_node->loop = loop;
273 loop_node->bb = NULL;
278 for (parent = loop_outer (loop);
280 parent = loop_outer (parent))
281 if (ira_loop_nodes[parent->num].regno_allocno_map != NULL)
286 loop_node->next = NULL;
287 loop_node->subloop_next = NULL;
288 loop_node->parent = NULL;
292 parent_node = &ira_loop_nodes[parent->num];
293 loop_node->next = parent_node->children;
294 parent_node->children = loop_node;
295 loop_node->subloop_next = parent_node->subloops;
296 parent_node->subloops = loop_node;
297 loop_node->parent = parent_node;
302 /* The following recursive function sets up levels of nodes of the
303 tree given its root LOOP_NODE. The enumeration starts with LEVEL.
304 The function returns maximal value of level in the tree + 1. */
306 setup_loop_tree_level (ira_loop_tree_node_t loop_node, int level)
308 int height, max_height;
309 ira_loop_tree_node_t subloop_node;
311 ira_assert (loop_node->bb == NULL);
312 loop_node->level = level;
313 max_height = level + 1;
314 for (subloop_node = loop_node->subloops;
315 subloop_node != NULL;
316 subloop_node = subloop_node->subloop_next)
318 ira_assert (subloop_node->bb == NULL);
319 height = setup_loop_tree_level (subloop_node, level + 1);
320 if (height > max_height)
326 /* Create the loop tree. The algorithm is designed to provide correct
327 order of loops (they are ordered by their last loop BB) and basic
328 blocks in the chain formed by member next. */
330 form_loop_tree (void)
334 ira_loop_tree_node_t bb_node, loop_node;
336 /* We can not use loop/bb node access macros because of potential
337 checking and because the nodes are not initialized enough
339 FOR_EACH_BB_FN (bb, cfun)
341 bb_node = &ira_bb_nodes[bb->index];
343 bb_node->loop = NULL;
344 bb_node->subloops = NULL;
345 bb_node->children = NULL;
346 bb_node->subloop_next = NULL;
347 bb_node->next = NULL;
348 if (current_loops == NULL)
352 for (parent = bb->loop_father;
354 parent = loop_outer (parent))
355 if (ira_loop_nodes[parent->num].regno_allocno_map != NULL)
358 add_loop_to_tree (parent);
359 loop_node = &ira_loop_nodes[parent == NULL ? 0 : parent->num];
360 bb_node->next = loop_node->children;
361 bb_node->parent = loop_node;
362 loop_node->children = bb_node;
364 ira_loop_tree_root = IRA_LOOP_NODE_BY_INDEX (0);
365 ira_loop_tree_height = setup_loop_tree_level (ira_loop_tree_root, 0);
366 ira_assert (ira_loop_tree_root->regno_allocno_map != NULL);
371 /* Rebuild IRA_REGNO_ALLOCNO_MAP and REGNO_ALLOCNO_MAPs of the loop
374 rebuild_regno_allocno_maps (void)
377 int max_regno, regno;
379 ira_loop_tree_node_t loop_tree_node;
381 ira_allocno_iterator ai;
383 ira_assert (current_loops != NULL);
384 max_regno = max_reg_num ();
385 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), l, loop)
386 if (ira_loop_nodes[l].regno_allocno_map != NULL)
388 ira_free (ira_loop_nodes[l].regno_allocno_map);
389 ira_loop_nodes[l].regno_allocno_map
390 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
392 memset (ira_loop_nodes[l].regno_allocno_map, 0,
393 sizeof (ira_allocno_t) * max_regno);
395 ira_free (ira_regno_allocno_map);
396 ira_regno_allocno_map
397 = (ira_allocno_t *) ira_allocate (max_regno * sizeof (ira_allocno_t));
398 memset (ira_regno_allocno_map, 0, max_regno * sizeof (ira_allocno_t));
399 FOR_EACH_ALLOCNO (a, ai)
401 if (ALLOCNO_CAP_MEMBER (a) != NULL)
402 /* Caps are not in the regno allocno maps. */
404 regno = ALLOCNO_REGNO (a);
405 loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
406 ALLOCNO_NEXT_REGNO_ALLOCNO (a) = ira_regno_allocno_map[regno];
407 ira_regno_allocno_map[regno] = a;
408 if (loop_tree_node->regno_allocno_map[regno] == NULL)
409 /* Remember that we can create temporary allocnos to break
410 cycles in register shuffle. */
411 loop_tree_node->regno_allocno_map[regno] = a;
416 /* Pools for allocnos, allocno live ranges and objects. */
417 static object_allocator<live_range> live_range_pool ("live ranges");
418 static object_allocator<ira_allocno> allocno_pool ("allocnos");
419 static object_allocator<ira_object> object_pool ("objects");
421 /* Vec containing references to all created allocnos. It is a
422 container of array allocnos. */
423 static vec<ira_allocno_t> allocno_vec;
425 /* Vec containing references to all created ira_objects. It is a
426 container of ira_object_id_map. */
427 static vec<ira_object_t> ira_object_id_map_vec;
429 /* Initialize data concerning allocnos. */
431 initiate_allocnos (void)
433 allocno_vec.create (max_reg_num () * 2);
435 ira_allocnos_num = 0;
437 ira_object_id_map_vec.create (max_reg_num () * 2);
438 ira_object_id_map = NULL;
439 ira_regno_allocno_map
440 = (ira_allocno_t *) ira_allocate (max_reg_num ()
441 * sizeof (ira_allocno_t));
442 memset (ira_regno_allocno_map, 0, max_reg_num () * sizeof (ira_allocno_t));
445 /* Create and return an object corresponding to a new allocno A. */
447 ira_create_object (ira_allocno_t a, int subword)
449 enum reg_class aclass = ALLOCNO_CLASS (a);
450 ira_object_t obj = object_pool.allocate ();
452 OBJECT_ALLOCNO (obj) = a;
453 OBJECT_SUBWORD (obj) = subword;
454 OBJECT_CONFLICT_ID (obj) = ira_objects_num;
455 OBJECT_CONFLICT_VEC_P (obj) = false;
456 OBJECT_CONFLICT_ARRAY (obj) = NULL;
457 OBJECT_NUM_CONFLICTS (obj) = 0;
458 COPY_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), ira_no_alloc_regs);
459 COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), ira_no_alloc_regs);
460 IOR_COMPL_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
461 reg_class_contents[aclass]);
462 IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
463 reg_class_contents[aclass]);
464 OBJECT_MIN (obj) = INT_MAX;
465 OBJECT_MAX (obj) = -1;
466 OBJECT_LIVE_RANGES (obj) = NULL;
468 ira_object_id_map_vec.safe_push (obj);
470 = ira_object_id_map_vec.address ();
471 ira_objects_num = ira_object_id_map_vec.length ();
476 /* Create and return the allocno corresponding to REGNO in
477 LOOP_TREE_NODE. Add the allocno to the list of allocnos with the
478 same regno if CAP_P is FALSE. */
480 ira_create_allocno (int regno, bool cap_p,
481 ira_loop_tree_node_t loop_tree_node)
485 a = allocno_pool.allocate ();
486 ALLOCNO_REGNO (a) = regno;
487 ALLOCNO_LOOP_TREE_NODE (a) = loop_tree_node;
490 ALLOCNO_NEXT_REGNO_ALLOCNO (a) = ira_regno_allocno_map[regno];
491 ira_regno_allocno_map[regno] = a;
492 if (loop_tree_node->regno_allocno_map[regno] == NULL)
493 /* Remember that we can create temporary allocnos to break
494 cycles in register shuffle on region borders (see
496 loop_tree_node->regno_allocno_map[regno] = a;
498 ALLOCNO_CAP (a) = NULL;
499 ALLOCNO_CAP_MEMBER (a) = NULL;
500 ALLOCNO_NUM (a) = ira_allocnos_num;
501 bitmap_set_bit (loop_tree_node->all_allocnos, ALLOCNO_NUM (a));
502 ALLOCNO_NREFS (a) = 0;
503 ALLOCNO_FREQ (a) = 0;
504 ALLOCNO_HARD_REGNO (a) = -1;
505 ALLOCNO_CALL_FREQ (a) = 0;
506 ALLOCNO_CALLS_CROSSED_NUM (a) = 0;
507 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a) = 0;
508 CLEAR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a));
510 ALLOCNO_NO_STACK_REG_P (a) = false;
511 ALLOCNO_TOTAL_NO_STACK_REG_P (a) = false;
513 ALLOCNO_DONT_REASSIGN_P (a) = false;
514 ALLOCNO_BAD_SPILL_P (a) = false;
515 ALLOCNO_ASSIGNED_P (a) = false;
516 ALLOCNO_MODE (a) = (regno < 0 ? VOIDmode : PSEUDO_REGNO_MODE (regno));
517 ALLOCNO_WMODE (a) = ALLOCNO_MODE (a);
518 ALLOCNO_PREFS (a) = NULL;
519 ALLOCNO_COPIES (a) = NULL;
520 ALLOCNO_HARD_REG_COSTS (a) = NULL;
521 ALLOCNO_CONFLICT_HARD_REG_COSTS (a) = NULL;
522 ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
523 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
524 ALLOCNO_CLASS (a) = NO_REGS;
525 ALLOCNO_UPDATED_CLASS_COST (a) = 0;
526 ALLOCNO_CLASS_COST (a) = 0;
527 ALLOCNO_MEMORY_COST (a) = 0;
528 ALLOCNO_UPDATED_MEMORY_COST (a) = 0;
529 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) = 0;
530 ALLOCNO_NUM_OBJECTS (a) = 0;
532 ALLOCNO_ADD_DATA (a) = NULL;
533 allocno_vec.safe_push (a);
534 ira_allocnos = allocno_vec.address ();
535 ira_allocnos_num = allocno_vec.length ();
540 /* Set up register class for A and update its conflict hard
543 ira_set_allocno_class (ira_allocno_t a, enum reg_class aclass)
545 ira_allocno_object_iterator oi;
548 ALLOCNO_CLASS (a) = aclass;
549 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
551 IOR_COMPL_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
552 reg_class_contents[aclass]);
553 IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
554 reg_class_contents[aclass]);
558 /* Determine the number of objects we should associate with allocno A
559 and allocate them. */
561 ira_create_allocno_objects (ira_allocno_t a)
563 machine_mode mode = ALLOCNO_MODE (a);
564 enum reg_class aclass = ALLOCNO_CLASS (a);
565 int n = ira_reg_class_max_nregs[aclass][mode];
568 if (GET_MODE_SIZE (mode) != 2 * UNITS_PER_WORD || n != 2)
571 ALLOCNO_NUM_OBJECTS (a) = n;
572 for (i = 0; i < n; i++)
573 ALLOCNO_OBJECT (a, i) = ira_create_object (a, i);
576 /* For each allocno, set ALLOCNO_NUM_OBJECTS and create the
577 ALLOCNO_OBJECT structures. This must be called after the allocno
578 classes are known. */
580 create_allocno_objects (void)
583 ira_allocno_iterator ai;
585 FOR_EACH_ALLOCNO (a, ai)
586 ira_create_allocno_objects (a);
589 /* Merge hard register conflict information for all objects associated with
590 allocno TO into the corresponding objects associated with FROM.
591 If TOTAL_ONLY is true, we only merge OBJECT_TOTAL_CONFLICT_HARD_REGS. */
593 merge_hard_reg_conflicts (ira_allocno_t from, ira_allocno_t to,
597 gcc_assert (ALLOCNO_NUM_OBJECTS (to) == ALLOCNO_NUM_OBJECTS (from));
598 for (i = 0; i < ALLOCNO_NUM_OBJECTS (to); i++)
600 ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
601 ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
604 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (to_obj),
605 OBJECT_CONFLICT_HARD_REGS (from_obj));
606 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (to_obj),
607 OBJECT_TOTAL_CONFLICT_HARD_REGS (from_obj));
610 if (!total_only && ALLOCNO_NO_STACK_REG_P (from))
611 ALLOCNO_NO_STACK_REG_P (to) = true;
612 if (ALLOCNO_TOTAL_NO_STACK_REG_P (from))
613 ALLOCNO_TOTAL_NO_STACK_REG_P (to) = true;
617 /* Update hard register conflict information for all objects associated with
618 A to include the regs in SET. */
620 ior_hard_reg_conflicts (ira_allocno_t a, HARD_REG_SET *set)
622 ira_allocno_object_iterator i;
625 FOR_EACH_ALLOCNO_OBJECT (a, obj, i)
627 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), *set);
628 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), *set);
632 /* Return TRUE if a conflict vector with NUM elements is more
633 profitable than a conflict bit vector for OBJ. */
635 ira_conflict_vector_profitable_p (ira_object_t obj, int num)
638 int max = OBJECT_MAX (obj);
639 int min = OBJECT_MIN (obj);
642 /* We prefer a bit vector in such case because it does not result
646 nw = (max - min + IRA_INT_BITS) / IRA_INT_BITS;
647 return (2 * sizeof (ira_object_t) * (num + 1)
648 < 3 * nw * sizeof (IRA_INT_TYPE));
651 /* Allocates and initialize the conflict vector of OBJ for NUM
652 conflicting objects. */
654 ira_allocate_conflict_vec (ira_object_t obj, int num)
659 ira_assert (OBJECT_CONFLICT_ARRAY (obj) == NULL);
660 num++; /* for NULL end marker */
661 size = sizeof (ira_object_t) * num;
662 OBJECT_CONFLICT_ARRAY (obj) = ira_allocate (size);
663 vec = (ira_object_t *) OBJECT_CONFLICT_ARRAY (obj);
665 OBJECT_NUM_CONFLICTS (obj) = 0;
666 OBJECT_CONFLICT_ARRAY_SIZE (obj) = size;
667 OBJECT_CONFLICT_VEC_P (obj) = true;
670 /* Allocate and initialize the conflict bit vector of OBJ. */
672 allocate_conflict_bit_vec (ira_object_t obj)
676 ira_assert (OBJECT_CONFLICT_ARRAY (obj) == NULL);
677 size = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
678 / IRA_INT_BITS * sizeof (IRA_INT_TYPE));
679 OBJECT_CONFLICT_ARRAY (obj) = ira_allocate (size);
680 memset (OBJECT_CONFLICT_ARRAY (obj), 0, size);
681 OBJECT_CONFLICT_ARRAY_SIZE (obj) = size;
682 OBJECT_CONFLICT_VEC_P (obj) = false;
685 /* Allocate and initialize the conflict vector or conflict bit vector
686 of OBJ for NUM conflicting allocnos whatever is more profitable. */
688 ira_allocate_object_conflicts (ira_object_t obj, int num)
690 if (ira_conflict_vector_profitable_p (obj, num))
691 ira_allocate_conflict_vec (obj, num);
693 allocate_conflict_bit_vec (obj);
696 /* Add OBJ2 to the conflicts of OBJ1. */
698 add_to_conflicts (ira_object_t obj1, ira_object_t obj2)
703 if (OBJECT_CONFLICT_VEC_P (obj1))
705 ira_object_t *vec = OBJECT_CONFLICT_VEC (obj1);
706 int curr_num = OBJECT_NUM_CONFLICTS (obj1);
708 if (OBJECT_CONFLICT_ARRAY_SIZE (obj1) < num * sizeof (ira_object_t))
710 ira_object_t *newvec;
711 size = (3 * num / 2 + 1) * sizeof (ira_allocno_t);
712 newvec = (ira_object_t *) ira_allocate (size);
713 memcpy (newvec, vec, curr_num * sizeof (ira_object_t));
716 OBJECT_CONFLICT_ARRAY (obj1) = vec;
717 OBJECT_CONFLICT_ARRAY_SIZE (obj1) = size;
721 OBJECT_NUM_CONFLICTS (obj1)++;
725 int nw, added_head_nw, id;
726 IRA_INT_TYPE *vec = OBJECT_CONFLICT_BITVEC (obj1);
728 id = OBJECT_CONFLICT_ID (obj2);
729 if (OBJECT_MIN (obj1) > id)
731 /* Expand head of the bit vector. */
732 added_head_nw = (OBJECT_MIN (obj1) - id - 1) / IRA_INT_BITS + 1;
733 nw = (OBJECT_MAX (obj1) - OBJECT_MIN (obj1)) / IRA_INT_BITS + 1;
734 size = (nw + added_head_nw) * sizeof (IRA_INT_TYPE);
735 if (OBJECT_CONFLICT_ARRAY_SIZE (obj1) >= size)
737 memmove ((char *) vec + added_head_nw * sizeof (IRA_INT_TYPE),
738 vec, nw * sizeof (IRA_INT_TYPE));
739 memset (vec, 0, added_head_nw * sizeof (IRA_INT_TYPE));
744 = (3 * (nw + added_head_nw) / 2 + 1) * sizeof (IRA_INT_TYPE);
745 vec = (IRA_INT_TYPE *) ira_allocate (size);
746 memcpy ((char *) vec + added_head_nw * sizeof (IRA_INT_TYPE),
747 OBJECT_CONFLICT_ARRAY (obj1), nw * sizeof (IRA_INT_TYPE));
748 memset (vec, 0, added_head_nw * sizeof (IRA_INT_TYPE));
750 + (nw + added_head_nw) * sizeof (IRA_INT_TYPE),
751 0, size - (nw + added_head_nw) * sizeof (IRA_INT_TYPE));
752 ira_free (OBJECT_CONFLICT_ARRAY (obj1));
753 OBJECT_CONFLICT_ARRAY (obj1) = vec;
754 OBJECT_CONFLICT_ARRAY_SIZE (obj1) = size;
756 OBJECT_MIN (obj1) -= added_head_nw * IRA_INT_BITS;
758 else if (OBJECT_MAX (obj1) < id)
760 nw = (id - OBJECT_MIN (obj1)) / IRA_INT_BITS + 1;
761 size = nw * sizeof (IRA_INT_TYPE);
762 if (OBJECT_CONFLICT_ARRAY_SIZE (obj1) < size)
764 /* Expand tail of the bit vector. */
765 size = (3 * nw / 2 + 1) * sizeof (IRA_INT_TYPE);
766 vec = (IRA_INT_TYPE *) ira_allocate (size);
767 memcpy (vec, OBJECT_CONFLICT_ARRAY (obj1), OBJECT_CONFLICT_ARRAY_SIZE (obj1));
768 memset ((char *) vec + OBJECT_CONFLICT_ARRAY_SIZE (obj1),
769 0, size - OBJECT_CONFLICT_ARRAY_SIZE (obj1));
770 ira_free (OBJECT_CONFLICT_ARRAY (obj1));
771 OBJECT_CONFLICT_ARRAY (obj1) = vec;
772 OBJECT_CONFLICT_ARRAY_SIZE (obj1) = size;
774 OBJECT_MAX (obj1) = id;
776 SET_MINMAX_SET_BIT (vec, id, OBJECT_MIN (obj1), OBJECT_MAX (obj1));
780 /* Add OBJ1 to the conflicts of OBJ2 and vice versa. */
782 ira_add_conflict (ira_object_t obj1, ira_object_t obj2)
784 add_to_conflicts (obj1, obj2);
785 add_to_conflicts (obj2, obj1);
788 /* Clear all conflicts of OBJ. */
790 clear_conflicts (ira_object_t obj)
792 if (OBJECT_CONFLICT_VEC_P (obj))
794 OBJECT_NUM_CONFLICTS (obj) = 0;
795 OBJECT_CONFLICT_VEC (obj)[0] = NULL;
797 else if (OBJECT_CONFLICT_ARRAY_SIZE (obj) != 0)
801 nw = (OBJECT_MAX (obj) - OBJECT_MIN (obj)) / IRA_INT_BITS + 1;
802 memset (OBJECT_CONFLICT_BITVEC (obj), 0, nw * sizeof (IRA_INT_TYPE));
806 /* The array used to find duplications in conflict vectors of
808 static int *conflict_check;
810 /* The value used to mark allocation presence in conflict vector of
811 the current allocno. */
812 static int curr_conflict_check_tick;
814 /* Remove duplications in conflict vector of OBJ. */
816 compress_conflict_vec (ira_object_t obj)
818 ira_object_t *vec, conflict_obj;
821 ira_assert (OBJECT_CONFLICT_VEC_P (obj));
822 vec = OBJECT_CONFLICT_VEC (obj);
823 curr_conflict_check_tick++;
824 for (i = j = 0; (conflict_obj = vec[i]) != NULL; i++)
826 int id = OBJECT_CONFLICT_ID (conflict_obj);
827 if (conflict_check[id] != curr_conflict_check_tick)
829 conflict_check[id] = curr_conflict_check_tick;
830 vec[j++] = conflict_obj;
833 OBJECT_NUM_CONFLICTS (obj) = j;
837 /* Remove duplications in conflict vectors of all allocnos. */
839 compress_conflict_vecs (void)
842 ira_object_iterator oi;
844 conflict_check = (int *) ira_allocate (sizeof (int) * ira_objects_num);
845 memset (conflict_check, 0, sizeof (int) * ira_objects_num);
846 curr_conflict_check_tick = 0;
847 FOR_EACH_OBJECT (obj, oi)
849 if (OBJECT_CONFLICT_VEC_P (obj))
850 compress_conflict_vec (obj);
852 ira_free (conflict_check);
855 /* This recursive function outputs allocno A and if it is a cap the
856 function outputs its members. */
858 ira_print_expanded_allocno (ira_allocno_t a)
862 fprintf (ira_dump_file, " a%d(r%d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
863 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
864 fprintf (ira_dump_file, ",b%d", bb->index);
866 fprintf (ira_dump_file, ",l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
867 if (ALLOCNO_CAP_MEMBER (a) != NULL)
869 fprintf (ira_dump_file, ":");
870 ira_print_expanded_allocno (ALLOCNO_CAP_MEMBER (a));
872 fprintf (ira_dump_file, ")");
875 /* Create and return the cap representing allocno A in the
878 create_cap_allocno (ira_allocno_t a)
881 ira_loop_tree_node_t parent;
882 enum reg_class aclass;
884 parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
885 cap = ira_create_allocno (ALLOCNO_REGNO (a), true, parent);
886 ALLOCNO_MODE (cap) = ALLOCNO_MODE (a);
887 ALLOCNO_WMODE (cap) = ALLOCNO_WMODE (a);
888 aclass = ALLOCNO_CLASS (a);
889 ira_set_allocno_class (cap, aclass);
890 ira_create_allocno_objects (cap);
891 ALLOCNO_CAP_MEMBER (cap) = a;
892 ALLOCNO_CAP (a) = cap;
893 ALLOCNO_CLASS_COST (cap) = ALLOCNO_CLASS_COST (a);
894 ALLOCNO_MEMORY_COST (cap) = ALLOCNO_MEMORY_COST (a);
895 ira_allocate_and_copy_costs
896 (&ALLOCNO_HARD_REG_COSTS (cap), aclass, ALLOCNO_HARD_REG_COSTS (a));
897 ira_allocate_and_copy_costs
898 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (cap), aclass,
899 ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
900 ALLOCNO_BAD_SPILL_P (cap) = ALLOCNO_BAD_SPILL_P (a);
901 ALLOCNO_NREFS (cap) = ALLOCNO_NREFS (a);
902 ALLOCNO_FREQ (cap) = ALLOCNO_FREQ (a);
903 ALLOCNO_CALL_FREQ (cap) = ALLOCNO_CALL_FREQ (a);
905 merge_hard_reg_conflicts (a, cap, false);
907 ALLOCNO_CALLS_CROSSED_NUM (cap) = ALLOCNO_CALLS_CROSSED_NUM (a);
908 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (cap) = ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
909 IOR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (cap),
910 ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a));
911 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
913 fprintf (ira_dump_file, " Creating cap ");
914 ira_print_expanded_allocno (cap);
915 fprintf (ira_dump_file, "\n");
920 /* Create and return a live range for OBJECT with given attributes. */
922 ira_create_live_range (ira_object_t obj, int start, int finish,
927 p = live_range_pool.allocate ();
935 /* Create a new live range for OBJECT and queue it at the head of its
938 ira_add_live_range_to_object (ira_object_t object, int start, int finish)
941 p = ira_create_live_range (object, start, finish,
942 OBJECT_LIVE_RANGES (object));
943 OBJECT_LIVE_RANGES (object) = p;
946 /* Copy allocno live range R and return the result. */
948 copy_live_range (live_range_t r)
952 p = live_range_pool.allocate ();
957 /* Copy allocno live range list given by its head R and return the
960 ira_copy_live_range_list (live_range_t r)
962 live_range_t p, first, last;
966 for (first = last = NULL; r != NULL; r = r->next)
968 p = copy_live_range (r);
978 /* Merge ranges R1 and R2 and returns the result. The function
979 maintains the order of ranges and tries to minimize number of the
982 ira_merge_live_ranges (live_range_t r1, live_range_t r2)
984 live_range_t first, last;
990 for (first = last = NULL; r1 != NULL && r2 != NULL;)
992 if (r1->start < r2->start)
994 if (r1->start <= r2->finish + 1)
996 /* Intersected ranges: merge r1 and r2 into r1. */
997 r1->start = r2->start;
998 if (r1->finish < r2->finish)
999 r1->finish = r2->finish;
1000 live_range_t temp = r2;
1002 ira_finish_live_range (temp);
1005 /* To try to merge with subsequent ranges in r1. */
1012 /* Add r1 to the result. */
1023 /* To try to merge with subsequent ranges in r2. */
1035 ira_assert (r1->next == NULL);
1037 else if (r2 != NULL)
1043 ira_assert (r2->next == NULL);
1047 ira_assert (last->next == NULL);
1052 /* Return TRUE if live ranges R1 and R2 intersect. */
1054 ira_live_ranges_intersect_p (live_range_t r1, live_range_t r2)
1056 /* Remember the live ranges are always kept ordered. */
1057 while (r1 != NULL && r2 != NULL)
1059 if (r1->start > r2->finish)
1061 else if (r2->start > r1->finish)
1069 /* Free allocno live range R. */
1071 ira_finish_live_range (live_range_t r)
1073 live_range_pool.remove (r);
1076 /* Free list of allocno live ranges starting with R. */
1078 ira_finish_live_range_list (live_range_t r)
1080 live_range_t next_r;
1082 for (; r != NULL; r = next_r)
1085 ira_finish_live_range (r);
1089 /* Free updated register costs of allocno A. */
1091 ira_free_allocno_updated_costs (ira_allocno_t a)
1093 enum reg_class aclass;
1095 aclass = ALLOCNO_CLASS (a);
1096 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL)
1097 ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass);
1098 ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
1099 if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
1100 ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
1102 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
1105 /* Free and nullify all cost vectors allocated earlier for allocno
1108 ira_free_allocno_costs (ira_allocno_t a)
1110 enum reg_class aclass = ALLOCNO_CLASS (a);
1112 ira_allocno_object_iterator oi;
1114 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
1116 ira_finish_live_range_list (OBJECT_LIVE_RANGES (obj));
1117 ira_object_id_map[OBJECT_CONFLICT_ID (obj)] = NULL;
1118 if (OBJECT_CONFLICT_ARRAY (obj) != NULL)
1119 ira_free (OBJECT_CONFLICT_ARRAY (obj));
1120 object_pool.remove (obj);
1123 ira_allocnos[ALLOCNO_NUM (a)] = NULL;
1124 if (ALLOCNO_HARD_REG_COSTS (a) != NULL)
1125 ira_free_cost_vector (ALLOCNO_HARD_REG_COSTS (a), aclass);
1126 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL)
1127 ira_free_cost_vector (ALLOCNO_CONFLICT_HARD_REG_COSTS (a), aclass);
1128 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL)
1129 ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass);
1130 if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
1131 ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
1133 ALLOCNO_HARD_REG_COSTS (a) = NULL;
1134 ALLOCNO_CONFLICT_HARD_REG_COSTS (a) = NULL;
1135 ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
1136 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
1139 /* Free the memory allocated for allocno A. */
1141 finish_allocno (ira_allocno_t a)
1143 ira_free_allocno_costs (a);
1144 allocno_pool.remove (a);
1147 /* Free the memory allocated for all allocnos. */
1149 finish_allocnos (void)
1152 ira_allocno_iterator ai;
1154 FOR_EACH_ALLOCNO (a, ai)
1156 ira_free (ira_regno_allocno_map);
1157 ira_object_id_map_vec.release ();
1158 allocno_vec.release ();
1159 allocno_pool.release ();
1160 object_pool.release ();
1161 live_range_pool.release ();
1166 /* Pools for allocno preferences. */
1167 static object_allocator <ira_allocno_pref> pref_pool ("prefs");
1169 /* Vec containing references to all created preferences. It is a
1170 container of array ira_prefs. */
1171 static vec<ira_pref_t> pref_vec;
1173 /* The function initializes data concerning allocno prefs. */
1175 initiate_prefs (void)
1177 pref_vec.create (get_max_uid ());
1182 /* Return pref for A and HARD_REGNO if any. */
1184 find_allocno_pref (ira_allocno_t a, int hard_regno)
1188 for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref)
1189 if (pref->allocno == a && pref->hard_regno == hard_regno)
1194 /* Create and return pref with given attributes A, HARD_REGNO, and FREQ. */
1196 ira_create_pref (ira_allocno_t a, int hard_regno, int freq)
1200 pref = pref_pool.allocate ();
1201 pref->num = ira_prefs_num;
1203 pref->hard_regno = hard_regno;
1205 pref_vec.safe_push (pref);
1206 ira_prefs = pref_vec.address ();
1207 ira_prefs_num = pref_vec.length ();
1211 /* Attach a pref PREF to the corresponding allocno. */
1213 add_allocno_pref_to_list (ira_pref_t pref)
1215 ira_allocno_t a = pref->allocno;
1217 pref->next_pref = ALLOCNO_PREFS (a);
1218 ALLOCNO_PREFS (a) = pref;
1221 /* Create (or update frequency if the pref already exists) the pref of
1222 allocnos A preferring HARD_REGNO with frequency FREQ. */
1224 ira_add_allocno_pref (ira_allocno_t a, int hard_regno, int freq)
1230 if ((pref = find_allocno_pref (a, hard_regno)) != NULL)
1235 pref = ira_create_pref (a, hard_regno, freq);
1236 ira_assert (a != NULL);
1237 add_allocno_pref_to_list (pref);
1240 /* Print info about PREF into file F. */
1242 print_pref (FILE *f, ira_pref_t pref)
1244 fprintf (f, " pref%d:a%d(r%d)<-hr%d@%d\n", pref->num,
1245 ALLOCNO_NUM (pref->allocno), ALLOCNO_REGNO (pref->allocno),
1246 pref->hard_regno, pref->freq);
1249 /* Print info about PREF into stderr. */
1251 ira_debug_pref (ira_pref_t pref)
1253 print_pref (stderr, pref);
1256 /* Print info about all prefs into file F. */
1258 print_prefs (FILE *f)
1261 ira_pref_iterator pi;
1263 FOR_EACH_PREF (pref, pi)
1264 print_pref (f, pref);
1267 /* Print info about all prefs into stderr. */
1269 ira_debug_prefs (void)
1271 print_prefs (stderr);
1274 /* Print info about prefs involving allocno A into file F. */
1276 print_allocno_prefs (FILE *f, ira_allocno_t a)
1280 fprintf (f, " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
1281 for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref)
1282 fprintf (f, " pref%d:hr%d@%d", pref->num, pref->hard_regno, pref->freq);
1286 /* Print info about prefs involving allocno A into stderr. */
1288 ira_debug_allocno_prefs (ira_allocno_t a)
1290 print_allocno_prefs (stderr, a);
1293 /* The function frees memory allocated for PREF. */
1295 finish_pref (ira_pref_t pref)
1297 ira_prefs[pref->num] = NULL;
1298 pref_pool.remove (pref);
1301 /* Remove PREF from the list of allocno prefs and free memory for
1304 ira_remove_pref (ira_pref_t pref)
1306 ira_pref_t cpref, prev;
1308 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1309 fprintf (ira_dump_file, " Removing pref%d:hr%d@%d\n",
1310 pref->num, pref->hard_regno, pref->freq);
1311 for (prev = NULL, cpref = ALLOCNO_PREFS (pref->allocno);
1313 prev = cpref, cpref = cpref->next_pref)
1316 ira_assert (cpref != NULL);
1318 ALLOCNO_PREFS (pref->allocno) = pref->next_pref;
1320 prev->next_pref = pref->next_pref;
1324 /* Remove all prefs of allocno A. */
1326 ira_remove_allocno_prefs (ira_allocno_t a)
1328 ira_pref_t pref, next_pref;
1330 for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = next_pref)
1332 next_pref = pref->next_pref;
1335 ALLOCNO_PREFS (a) = NULL;
1338 /* Free memory allocated for all prefs. */
1343 ira_pref_iterator pi;
1345 FOR_EACH_PREF (pref, pi)
1347 pref_vec.release ();
1348 pref_pool.release ();
1353 /* Pools for copies. */
1354 static object_allocator<ira_allocno_copy> copy_pool ("copies");
1356 /* Vec containing references to all created copies. It is a
1357 container of array ira_copies. */
1358 static vec<ira_copy_t> copy_vec;
1360 /* The function initializes data concerning allocno copies. */
1362 initiate_copies (void)
1364 copy_vec.create (get_max_uid ());
1369 /* Return copy connecting A1 and A2 and originated from INSN of
1370 LOOP_TREE_NODE if any. */
1372 find_allocno_copy (ira_allocno_t a1, ira_allocno_t a2, rtx_insn *insn,
1373 ira_loop_tree_node_t loop_tree_node)
1375 ira_copy_t cp, next_cp;
1376 ira_allocno_t another_a;
1378 for (cp = ALLOCNO_COPIES (a1); cp != NULL; cp = next_cp)
1380 if (cp->first == a1)
1382 next_cp = cp->next_first_allocno_copy;
1383 another_a = cp->second;
1385 else if (cp->second == a1)
1387 next_cp = cp->next_second_allocno_copy;
1388 another_a = cp->first;
1392 if (another_a == a2 && cp->insn == insn
1393 && cp->loop_tree_node == loop_tree_node)
1399 /* Create and return copy with given attributes LOOP_TREE_NODE, FIRST,
1400 SECOND, FREQ, CONSTRAINT_P, and INSN. */
1402 ira_create_copy (ira_allocno_t first, ira_allocno_t second, int freq,
1403 bool constraint_p, rtx_insn *insn,
1404 ira_loop_tree_node_t loop_tree_node)
1408 cp = copy_pool.allocate ();
1409 cp->num = ira_copies_num;
1411 cp->second = second;
1413 cp->constraint_p = constraint_p;
1415 cp->loop_tree_node = loop_tree_node;
1416 copy_vec.safe_push (cp);
1417 ira_copies = copy_vec.address ();
1418 ira_copies_num = copy_vec.length ();
1422 /* Attach a copy CP to allocnos involved into the copy. */
1424 add_allocno_copy_to_list (ira_copy_t cp)
1426 ira_allocno_t first = cp->first, second = cp->second;
1428 cp->prev_first_allocno_copy = NULL;
1429 cp->prev_second_allocno_copy = NULL;
1430 cp->next_first_allocno_copy = ALLOCNO_COPIES (first);
1431 if (cp->next_first_allocno_copy != NULL)
1433 if (cp->next_first_allocno_copy->first == first)
1434 cp->next_first_allocno_copy->prev_first_allocno_copy = cp;
1436 cp->next_first_allocno_copy->prev_second_allocno_copy = cp;
1438 cp->next_second_allocno_copy = ALLOCNO_COPIES (second);
1439 if (cp->next_second_allocno_copy != NULL)
1441 if (cp->next_second_allocno_copy->second == second)
1442 cp->next_second_allocno_copy->prev_second_allocno_copy = cp;
1444 cp->next_second_allocno_copy->prev_first_allocno_copy = cp;
1446 ALLOCNO_COPIES (first) = cp;
1447 ALLOCNO_COPIES (second) = cp;
1450 /* Make a copy CP a canonical copy where number of the
1451 first allocno is less than the second one. */
1453 swap_allocno_copy_ends_if_necessary (ira_copy_t cp)
1455 if (ALLOCNO_NUM (cp->first) <= ALLOCNO_NUM (cp->second))
1458 std::swap (cp->first, cp->second);
1459 std::swap (cp->prev_first_allocno_copy, cp->prev_second_allocno_copy);
1460 std::swap (cp->next_first_allocno_copy, cp->next_second_allocno_copy);
1463 /* Create (or update frequency if the copy already exists) and return
1464 the copy of allocnos FIRST and SECOND with frequency FREQ
1465 corresponding to move insn INSN (if any) and originated from
1468 ira_add_allocno_copy (ira_allocno_t first, ira_allocno_t second, int freq,
1469 bool constraint_p, rtx_insn *insn,
1470 ira_loop_tree_node_t loop_tree_node)
1474 if ((cp = find_allocno_copy (first, second, insn, loop_tree_node)) != NULL)
1479 cp = ira_create_copy (first, second, freq, constraint_p, insn,
1481 ira_assert (first != NULL && second != NULL);
1482 add_allocno_copy_to_list (cp);
1483 swap_allocno_copy_ends_if_necessary (cp);
1487 /* Print info about copy CP into file F. */
1489 print_copy (FILE *f, ira_copy_t cp)
1491 fprintf (f, " cp%d:a%d(r%d)<->a%d(r%d)@%d:%s\n", cp->num,
1492 ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
1493 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second), cp->freq,
1495 ? "move" : cp->constraint_p ? "constraint" : "shuffle");
1499 debug (ira_allocno_copy &ref)
1501 print_copy (stderr, &ref);
1505 debug (ira_allocno_copy *ptr)
1510 fprintf (stderr, "<nil>\n");
1513 /* Print info about copy CP into stderr. */
1515 ira_debug_copy (ira_copy_t cp)
1517 print_copy (stderr, cp);
1520 /* Print info about all copies into file F. */
1522 print_copies (FILE *f)
1525 ira_copy_iterator ci;
1527 FOR_EACH_COPY (cp, ci)
1531 /* Print info about all copies into stderr. */
1533 ira_debug_copies (void)
1535 print_copies (stderr);
1538 /* Print info about copies involving allocno A into file F. */
1540 print_allocno_copies (FILE *f, ira_allocno_t a)
1542 ira_allocno_t another_a;
1543 ira_copy_t cp, next_cp;
1545 fprintf (f, " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
1546 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
1550 next_cp = cp->next_first_allocno_copy;
1551 another_a = cp->second;
1553 else if (cp->second == a)
1555 next_cp = cp->next_second_allocno_copy;
1556 another_a = cp->first;
1560 fprintf (f, " cp%d:a%d(r%d)@%d", cp->num,
1561 ALLOCNO_NUM (another_a), ALLOCNO_REGNO (another_a), cp->freq);
1567 debug (ira_allocno &ref)
1569 print_allocno_copies (stderr, &ref);
1573 debug (ira_allocno *ptr)
1578 fprintf (stderr, "<nil>\n");
1582 /* Print info about copies involving allocno A into stderr. */
1584 ira_debug_allocno_copies (ira_allocno_t a)
1586 print_allocno_copies (stderr, a);
1589 /* The function frees memory allocated for copy CP. */
1591 finish_copy (ira_copy_t cp)
1593 copy_pool.remove (cp);
1597 /* Free memory allocated for all copies. */
1599 finish_copies (void)
1602 ira_copy_iterator ci;
1604 FOR_EACH_COPY (cp, ci)
1606 copy_vec.release ();
1607 copy_pool.release ();
1612 /* Pools for cost vectors. It is defined only for allocno classes. */
1613 static pool_allocator *cost_vector_pool[N_REG_CLASSES];
1615 /* The function initiates work with hard register cost vectors. It
1616 creates allocation pool for each allocno class. */
1618 initiate_cost_vectors (void)
1621 enum reg_class aclass;
1623 for (i = 0; i < ira_allocno_classes_num; i++)
1625 aclass = ira_allocno_classes[i];
1626 cost_vector_pool[aclass] = new pool_allocator
1627 ("cost vectors", sizeof (int) * (ira_class_hard_regs_num[aclass]));
1631 /* Allocate and return a cost vector VEC for ACLASS. */
1633 ira_allocate_cost_vector (reg_class_t aclass)
1635 return (int*) cost_vector_pool[(int) aclass]->allocate ();
1638 /* Free a cost vector VEC for ACLASS. */
1640 ira_free_cost_vector (int *vec, reg_class_t aclass)
1642 ira_assert (vec != NULL);
1643 cost_vector_pool[(int) aclass]->remove (vec);
1646 /* Finish work with hard register cost vectors. Release allocation
1647 pool for each allocno class. */
1649 finish_cost_vectors (void)
1652 enum reg_class aclass;
1654 for (i = 0; i < ira_allocno_classes_num; i++)
1656 aclass = ira_allocno_classes[i];
1657 delete cost_vector_pool[aclass];
1663 /* Compute a post-ordering of the reverse control flow of the loop body
1664 designated by the children nodes of LOOP_NODE, whose body nodes in
1665 pre-order are input as LOOP_PREORDER. Return a VEC with a post-order
1666 of the reverse loop body.
1668 For the post-order of the reverse CFG, we visit the basic blocks in
1669 LOOP_PREORDER array in the reverse order of where they appear.
1670 This is important: We do not just want to compute a post-order of
1671 the reverse CFG, we want to make a best-guess for a visiting order that
1672 minimizes the number of chain elements per allocno live range. If the
1673 blocks would be visited in a different order, we would still compute a
1674 correct post-ordering but it would be less likely that two nodes
1675 connected by an edge in the CFG are neighbors in the topsort. */
1677 static vec<ira_loop_tree_node_t>
1678 ira_loop_tree_body_rev_postorder (ira_loop_tree_node_t loop_node ATTRIBUTE_UNUSED,
1679 vec<ira_loop_tree_node_t> loop_preorder)
1681 vec<ira_loop_tree_node_t> topsort_nodes = vNULL;
1682 unsigned int n_loop_preorder;
1684 n_loop_preorder = loop_preorder.length ();
1685 if (n_loop_preorder != 0)
1687 ira_loop_tree_node_t subloop_node;
1689 auto_vec<ira_loop_tree_node_t> dfs_stack;
1691 /* This is a bit of strange abuse of the BB_VISITED flag: We use
1692 the flag to mark blocks we still have to visit to add them to
1693 our post-order. Define an alias to avoid confusion. */
1694 #define BB_TO_VISIT BB_VISITED
1696 FOR_EACH_VEC_ELT (loop_preorder, i, subloop_node)
1698 gcc_checking_assert (! (subloop_node->bb->flags & BB_TO_VISIT));
1699 subloop_node->bb->flags |= BB_TO_VISIT;
1702 topsort_nodes.create (n_loop_preorder);
1703 dfs_stack.create (n_loop_preorder);
1705 FOR_EACH_VEC_ELT_REVERSE (loop_preorder, i, subloop_node)
1707 if (! (subloop_node->bb->flags & BB_TO_VISIT))
1710 subloop_node->bb->flags &= ~BB_TO_VISIT;
1711 dfs_stack.quick_push (subloop_node);
1712 while (! dfs_stack.is_empty ())
1717 ira_loop_tree_node_t n = dfs_stack.last ();
1718 FOR_EACH_EDGE (e, ei, n->bb->preds)
1720 ira_loop_tree_node_t pred_node;
1721 basic_block pred_bb = e->src;
1723 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1726 pred_node = IRA_BB_NODE_BY_INDEX (pred_bb->index);
1728 && (pred_node->bb->flags & BB_TO_VISIT))
1730 pred_node->bb->flags &= ~BB_TO_VISIT;
1731 dfs_stack.quick_push (pred_node);
1734 if (n == dfs_stack.last ())
1737 topsort_nodes.quick_push (n);
1745 gcc_assert (topsort_nodes.length () == n_loop_preorder);
1746 return topsort_nodes;
1749 /* The current loop tree node and its regno allocno map. */
1750 ira_loop_tree_node_t ira_curr_loop_tree_node;
1751 ira_allocno_t *ira_curr_regno_allocno_map;
1753 /* This recursive function traverses loop tree with root LOOP_NODE
1754 calling non-null functions PREORDER_FUNC and POSTORDER_FUNC
1755 correspondingly in preorder and postorder. The function sets up
1756 IRA_CURR_LOOP_TREE_NODE and IRA_CURR_REGNO_ALLOCNO_MAP. If BB_P,
1757 basic block nodes of LOOP_NODE is also processed (before its
1760 If BB_P is set and POSTORDER_FUNC is given, the basic blocks in
1761 the loop are passed in the *reverse* post-order of the *reverse*
1762 CFG. This is only used by ira_create_allocno_live_ranges, which
1763 wants to visit basic blocks in this order to minimize the number
1764 of elements per live range chain.
1765 Note that the loop tree nodes are still visited in the normal,
1766 forward post-order of the loop tree. */
1769 ira_traverse_loop_tree (bool bb_p, ira_loop_tree_node_t loop_node,
1770 void (*preorder_func) (ira_loop_tree_node_t),
1771 void (*postorder_func) (ira_loop_tree_node_t))
1773 ira_loop_tree_node_t subloop_node;
1775 ira_assert (loop_node->bb == NULL);
1776 ira_curr_loop_tree_node = loop_node;
1777 ira_curr_regno_allocno_map = ira_curr_loop_tree_node->regno_allocno_map;
1779 if (preorder_func != NULL)
1780 (*preorder_func) (loop_node);
1784 auto_vec<ira_loop_tree_node_t> loop_preorder;
1787 /* Add all nodes to the set of nodes to visit. The IRA loop tree
1788 is set up such that nodes in the loop body appear in a pre-order
1789 of their place in the CFG. */
1790 for (subloop_node = loop_node->children;
1791 subloop_node != NULL;
1792 subloop_node = subloop_node->next)
1793 if (subloop_node->bb != NULL)
1794 loop_preorder.safe_push (subloop_node);
1796 if (preorder_func != NULL)
1797 FOR_EACH_VEC_ELT (loop_preorder, i, subloop_node)
1798 (*preorder_func) (subloop_node);
1800 if (postorder_func != NULL)
1802 vec<ira_loop_tree_node_t> loop_rev_postorder =
1803 ira_loop_tree_body_rev_postorder (loop_node, loop_preorder);
1804 FOR_EACH_VEC_ELT_REVERSE (loop_rev_postorder, i, subloop_node)
1805 (*postorder_func) (subloop_node);
1806 loop_rev_postorder.release ();
1810 for (subloop_node = loop_node->subloops;
1811 subloop_node != NULL;
1812 subloop_node = subloop_node->subloop_next)
1814 ira_assert (subloop_node->bb == NULL);
1815 ira_traverse_loop_tree (bb_p, subloop_node,
1816 preorder_func, postorder_func);
1819 ira_curr_loop_tree_node = loop_node;
1820 ira_curr_regno_allocno_map = ira_curr_loop_tree_node->regno_allocno_map;
1822 if (postorder_func != NULL)
1823 (*postorder_func) (loop_node);
1828 /* The basic block currently being processed. */
1829 static basic_block curr_bb;
1831 /* This recursive function creates allocnos corresponding to
1832 pseudo-registers containing in X. True OUTPUT_P means that X is
1833 an lvalue. PARENT corresponds to the parent expression of X. */
1835 create_insn_allocnos (rtx x, rtx outer, bool output_p)
1839 enum rtx_code code = GET_CODE (x);
1845 if ((regno = REGNO (x)) >= FIRST_PSEUDO_REGISTER)
1849 if ((a = ira_curr_regno_allocno_map[regno]) == NULL)
1851 a = ira_create_allocno (regno, false, ira_curr_loop_tree_node);
1852 if (outer != NULL && GET_CODE (outer) == SUBREG)
1854 machine_mode wmode = GET_MODE (outer);
1855 if (GET_MODE_SIZE (wmode) > GET_MODE_SIZE (ALLOCNO_WMODE (a)))
1856 ALLOCNO_WMODE (a) = wmode;
1860 ALLOCNO_NREFS (a)++;
1861 ALLOCNO_FREQ (a) += REG_FREQ_FROM_BB (curr_bb);
1863 bitmap_set_bit (ira_curr_loop_tree_node->modified_regnos, regno);
1867 else if (code == SET)
1869 create_insn_allocnos (SET_DEST (x), NULL, true);
1870 create_insn_allocnos (SET_SRC (x), NULL, false);
1873 else if (code == CLOBBER)
1875 create_insn_allocnos (XEXP (x, 0), NULL, true);
1878 else if (code == MEM)
1880 create_insn_allocnos (XEXP (x, 0), NULL, false);
1883 else if (code == PRE_DEC || code == POST_DEC || code == PRE_INC ||
1884 code == POST_INC || code == POST_MODIFY || code == PRE_MODIFY)
1886 create_insn_allocnos (XEXP (x, 0), NULL, true);
1887 create_insn_allocnos (XEXP (x, 0), NULL, false);
1891 fmt = GET_RTX_FORMAT (code);
1892 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1895 create_insn_allocnos (XEXP (x, i), x, output_p);
1896 else if (fmt[i] == 'E')
1897 for (j = 0; j < XVECLEN (x, i); j++)
1898 create_insn_allocnos (XVECEXP (x, i, j), x, output_p);
1902 /* Create allocnos corresponding to pseudo-registers living in the
1903 basic block represented by the corresponding loop tree node
1906 create_bb_allocnos (ira_loop_tree_node_t bb_node)
1913 curr_bb = bb = bb_node->bb;
1914 ira_assert (bb != NULL);
1915 FOR_BB_INSNS_REVERSE (bb, insn)
1916 if (NONDEBUG_INSN_P (insn))
1917 create_insn_allocnos (PATTERN (insn), NULL, false);
1918 /* It might be a allocno living through from one subloop to
1920 EXECUTE_IF_SET_IN_REG_SET (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, i, bi)
1921 if (ira_curr_regno_allocno_map[i] == NULL)
1922 ira_create_allocno (i, false, ira_curr_loop_tree_node);
1925 /* Create allocnos corresponding to pseudo-registers living on edge E
1926 (a loop entry or exit). Also mark the allocnos as living on the
1929 create_loop_allocnos (edge e)
1932 bitmap live_in_regs, border_allocnos;
1934 ira_loop_tree_node_t parent;
1936 live_in_regs = df_get_live_in (e->dest);
1937 border_allocnos = ira_curr_loop_tree_node->border_allocnos;
1938 EXECUTE_IF_SET_IN_REG_SET (df_get_live_out (e->src),
1939 FIRST_PSEUDO_REGISTER, i, bi)
1940 if (bitmap_bit_p (live_in_regs, i))
1942 if (ira_curr_regno_allocno_map[i] == NULL)
1944 /* The order of creations is important for right
1945 ira_regno_allocno_map. */
1946 if ((parent = ira_curr_loop_tree_node->parent) != NULL
1947 && parent->regno_allocno_map[i] == NULL)
1948 ira_create_allocno (i, false, parent);
1949 ira_create_allocno (i, false, ira_curr_loop_tree_node);
1951 bitmap_set_bit (border_allocnos,
1952 ALLOCNO_NUM (ira_curr_regno_allocno_map[i]));
1956 /* Create allocnos corresponding to pseudo-registers living in loop
1957 represented by the corresponding loop tree node LOOP_NODE. This
1958 function is called by ira_traverse_loop_tree. */
1960 create_loop_tree_node_allocnos (ira_loop_tree_node_t loop_node)
1962 if (loop_node->bb != NULL)
1963 create_bb_allocnos (loop_node);
1964 else if (loop_node != ira_loop_tree_root)
1971 ira_assert (current_loops != NULL);
1972 FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
1973 if (e->src != loop_node->loop->latch)
1974 create_loop_allocnos (e);
1976 edges = get_loop_exit_edges (loop_node->loop);
1977 FOR_EACH_VEC_ELT (edges, i, e)
1978 create_loop_allocnos (e);
1983 /* Propagate information about allocnos modified inside the loop given
1984 by its LOOP_TREE_NODE to its parent. */
1986 propagate_modified_regnos (ira_loop_tree_node_t loop_tree_node)
1988 if (loop_tree_node == ira_loop_tree_root)
1990 ira_assert (loop_tree_node->bb == NULL);
1991 bitmap_ior_into (loop_tree_node->parent->modified_regnos,
1992 loop_tree_node->modified_regnos);
1995 /* Propagate new info about allocno A (see comments about accumulated
1996 info in allocno definition) to the corresponding allocno on upper
1997 loop tree level. So allocnos on upper levels accumulate
1998 information about the corresponding allocnos in nested regions.
1999 The new info means allocno info finally calculated in this
2002 propagate_allocno_info (void)
2005 ira_allocno_t a, parent_a;
2006 ira_loop_tree_node_t parent;
2007 enum reg_class aclass;
2009 if (flag_ira_region != IRA_REGION_ALL
2010 && flag_ira_region != IRA_REGION_MIXED)
2012 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
2013 for (a = ira_regno_allocno_map[i];
2015 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2016 if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL
2017 && (parent_a = parent->regno_allocno_map[i]) != NULL
2018 /* There are no caps yet at this point. So use
2019 border_allocnos to find allocnos for the propagation. */
2020 && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE (a)->border_allocnos,
2023 if (! ALLOCNO_BAD_SPILL_P (a))
2024 ALLOCNO_BAD_SPILL_P (parent_a) = false;
2025 ALLOCNO_NREFS (parent_a) += ALLOCNO_NREFS (a);
2026 ALLOCNO_FREQ (parent_a) += ALLOCNO_FREQ (a);
2027 ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
2028 merge_hard_reg_conflicts (a, parent_a, true);
2029 ALLOCNO_CALLS_CROSSED_NUM (parent_a)
2030 += ALLOCNO_CALLS_CROSSED_NUM (a);
2031 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
2032 += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
2033 IOR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (parent_a),
2034 ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a));
2035 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
2036 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2037 aclass = ALLOCNO_CLASS (a);
2038 ira_assert (aclass == ALLOCNO_CLASS (parent_a));
2039 ira_allocate_and_accumulate_costs
2040 (&ALLOCNO_HARD_REG_COSTS (parent_a), aclass,
2041 ALLOCNO_HARD_REG_COSTS (a));
2042 ira_allocate_and_accumulate_costs
2043 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a),
2045 ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
2046 ALLOCNO_CLASS_COST (parent_a)
2047 += ALLOCNO_CLASS_COST (a);
2048 ALLOCNO_MEMORY_COST (parent_a) += ALLOCNO_MEMORY_COST (a);
2052 /* Create allocnos corresponding to pseudo-registers in the current
2053 function. Traverse the loop tree for this. */
2055 create_allocnos (void)
2057 /* We need to process BB first to correctly link allocnos by member
2058 next_regno_allocno. */
2059 ira_traverse_loop_tree (true, ira_loop_tree_root,
2060 create_loop_tree_node_allocnos, NULL);
2062 ira_traverse_loop_tree (false, ira_loop_tree_root, NULL,
2063 propagate_modified_regnos);
2068 /* The page contains function to remove some regions from a separate
2069 register allocation. We remove regions whose separate allocation
2070 will hardly improve the result. As a result we speed up regional
2071 register allocation. */
2073 /* The function changes the object in range list given by R to OBJ. */
2075 change_object_in_range_list (live_range_t r, ira_object_t obj)
2077 for (; r != NULL; r = r->next)
2081 /* Move all live ranges associated with allocno FROM to allocno TO. */
2083 move_allocno_live_ranges (ira_allocno_t from, ira_allocno_t to)
2086 int n = ALLOCNO_NUM_OBJECTS (from);
2088 gcc_assert (n == ALLOCNO_NUM_OBJECTS (to));
2090 for (i = 0; i < n; i++)
2092 ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
2093 ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
2094 live_range_t lr = OBJECT_LIVE_RANGES (from_obj);
2096 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2098 fprintf (ira_dump_file,
2099 " Moving ranges of a%dr%d to a%dr%d: ",
2100 ALLOCNO_NUM (from), ALLOCNO_REGNO (from),
2101 ALLOCNO_NUM (to), ALLOCNO_REGNO (to));
2102 ira_print_live_range_list (ira_dump_file, lr);
2104 change_object_in_range_list (lr, to_obj);
2105 OBJECT_LIVE_RANGES (to_obj)
2106 = ira_merge_live_ranges (lr, OBJECT_LIVE_RANGES (to_obj));
2107 OBJECT_LIVE_RANGES (from_obj) = NULL;
2112 copy_allocno_live_ranges (ira_allocno_t from, ira_allocno_t to)
2115 int n = ALLOCNO_NUM_OBJECTS (from);
2117 gcc_assert (n == ALLOCNO_NUM_OBJECTS (to));
2119 for (i = 0; i < n; i++)
2121 ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
2122 ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
2123 live_range_t lr = OBJECT_LIVE_RANGES (from_obj);
2125 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2127 fprintf (ira_dump_file, " Copying ranges of a%dr%d to a%dr%d: ",
2128 ALLOCNO_NUM (from), ALLOCNO_REGNO (from),
2129 ALLOCNO_NUM (to), ALLOCNO_REGNO (to));
2130 ira_print_live_range_list (ira_dump_file, lr);
2132 lr = ira_copy_live_range_list (lr);
2133 change_object_in_range_list (lr, to_obj);
2134 OBJECT_LIVE_RANGES (to_obj)
2135 = ira_merge_live_ranges (lr, OBJECT_LIVE_RANGES (to_obj));
2139 /* Return TRUE if NODE represents a loop with low register
2142 low_pressure_loop_node_p (ira_loop_tree_node_t node)
2145 enum reg_class pclass;
2147 if (node->bb != NULL)
2150 for (i = 0; i < ira_pressure_classes_num; i++)
2152 pclass = ira_pressure_classes[i];
2153 if (node->reg_pressure[pclass] > ira_class_hard_regs_num[pclass]
2154 && ira_class_hard_regs_num[pclass] > 1)
2161 /* Return TRUE if LOOP has a complex enter or exit edge. We don't
2162 form a region from such loop if the target use stack register
2163 because reg-stack.c can not deal with such edges. */
2165 loop_with_complex_edge_p (struct loop *loop)
2173 FOR_EACH_EDGE (e, ei, loop->header->preds)
2174 if (e->flags & EDGE_EH)
2176 edges = get_loop_exit_edges (loop);
2178 FOR_EACH_VEC_ELT (edges, i, e)
2179 if (e->flags & EDGE_COMPLEX)
2189 /* Sort loops for marking them for removal. We put already marked
2190 loops first, then less frequent loops next, and then outer loops
2193 loop_compare_func (const void *v1p, const void *v2p)
2196 ira_loop_tree_node_t l1 = *(const ira_loop_tree_node_t *) v1p;
2197 ira_loop_tree_node_t l2 = *(const ira_loop_tree_node_t *) v2p;
2199 ira_assert (l1->parent != NULL && l2->parent != NULL);
2200 if (l1->to_remove_p && ! l2->to_remove_p)
2202 if (! l1->to_remove_p && l2->to_remove_p)
2204 if ((diff = l1->loop->header->frequency - l2->loop->header->frequency) != 0)
2206 if ((diff = (int) loop_depth (l1->loop) - (int) loop_depth (l2->loop)) != 0)
2208 /* Make sorting stable. */
2209 return l1->loop_num - l2->loop_num;
2212 /* Mark loops which should be removed from regional allocation. We
2213 remove a loop with low register pressure inside another loop with
2214 register pressure. In this case a separate allocation of the loop
2215 hardly helps (for irregular register file architecture it could
2216 help by choosing a better hard register in the loop but we prefer
2217 faster allocation even in this case). We also remove cheap loops
2218 if there are more than IRA_MAX_LOOPS_NUM of them. Loop with EH
2219 exit or enter edges are removed too because the allocation might
2220 require put pseudo moves on the EH edges (we could still do this
2221 for pseudos with caller saved hard registers in some cases but it
2222 is impossible to say here or during top-down allocation pass what
2223 hard register the pseudos get finally). */
2225 mark_loops_for_removal (void)
2228 ira_loop_tree_node_t *sorted_loops;
2231 ira_assert (current_loops != NULL);
2233 = (ira_loop_tree_node_t *) ira_allocate (sizeof (ira_loop_tree_node_t)
2234 * number_of_loops (cfun));
2235 for (n = i = 0; vec_safe_iterate (get_loops (cfun), i, &loop); i++)
2236 if (ira_loop_nodes[i].regno_allocno_map != NULL)
2238 if (ira_loop_nodes[i].parent == NULL)
2240 /* Don't remove the root. */
2241 ira_loop_nodes[i].to_remove_p = false;
2244 sorted_loops[n++] = &ira_loop_nodes[i];
2245 ira_loop_nodes[i].to_remove_p
2246 = ((low_pressure_loop_node_p (ira_loop_nodes[i].parent)
2247 && low_pressure_loop_node_p (&ira_loop_nodes[i]))
2249 || loop_with_complex_edge_p (ira_loop_nodes[i].loop)
2253 qsort (sorted_loops, n, sizeof (ira_loop_tree_node_t), loop_compare_func);
2254 for (i = 0; i < n - IRA_MAX_LOOPS_NUM; i++)
2256 sorted_loops[i]->to_remove_p = true;
2257 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2260 " Mark loop %d (header %d, freq %d, depth %d) for removal (%s)\n",
2261 sorted_loops[i]->loop_num, sorted_loops[i]->loop->header->index,
2262 sorted_loops[i]->loop->header->frequency,
2263 loop_depth (sorted_loops[i]->loop),
2264 low_pressure_loop_node_p (sorted_loops[i]->parent)
2265 && low_pressure_loop_node_p (sorted_loops[i])
2266 ? "low pressure" : "cheap loop");
2268 ira_free (sorted_loops);
2271 /* Mark all loops but root for removing. */
2273 mark_all_loops_for_removal (void)
2278 ira_assert (current_loops != NULL);
2279 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
2280 if (ira_loop_nodes[i].regno_allocno_map != NULL)
2282 if (ira_loop_nodes[i].parent == NULL)
2284 /* Don't remove the root. */
2285 ira_loop_nodes[i].to_remove_p = false;
2288 ira_loop_nodes[i].to_remove_p = true;
2289 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2292 " Mark loop %d (header %d, freq %d, depth %d) for removal\n",
2293 ira_loop_nodes[i].loop_num,
2294 ira_loop_nodes[i].loop->header->index,
2295 ira_loop_nodes[i].loop->header->frequency,
2296 loop_depth (ira_loop_nodes[i].loop));
2300 /* Definition of vector of loop tree nodes. */
2302 /* Vec containing references to all removed loop tree nodes. */
2303 static vec<ira_loop_tree_node_t> removed_loop_vec;
2305 /* Vec containing references to all children of loop tree nodes. */
2306 static vec<ira_loop_tree_node_t> children_vec;
2308 /* Remove subregions of NODE if their separate allocation will not
2309 improve the result. */
2311 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_node_t node)
2315 ira_loop_tree_node_t subnode;
2317 remove_p = node->to_remove_p;
2319 children_vec.safe_push (node);
2320 start = children_vec.length ();
2321 for (subnode = node->children; subnode != NULL; subnode = subnode->next)
2322 if (subnode->bb == NULL)
2323 remove_uneccesary_loop_nodes_from_loop_tree (subnode);
2325 children_vec.safe_push (subnode);
2326 node->children = node->subloops = NULL;
2329 removed_loop_vec.safe_push (node);
2332 while (children_vec.length () > start)
2334 subnode = children_vec.pop ();
2335 subnode->parent = node;
2336 subnode->next = node->children;
2337 node->children = subnode;
2338 if (subnode->bb == NULL)
2340 subnode->subloop_next = node->subloops;
2341 node->subloops = subnode;
2346 /* Return TRUE if NODE is inside PARENT. */
2348 loop_is_inside_p (ira_loop_tree_node_t node, ira_loop_tree_node_t parent)
2350 for (node = node->parent; node != NULL; node = node->parent)
2356 /* Sort allocnos according to their order in regno allocno list. */
2358 regno_allocno_order_compare_func (const void *v1p, const void *v2p)
2360 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2361 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2362 ira_loop_tree_node_t n1 = ALLOCNO_LOOP_TREE_NODE (a1);
2363 ira_loop_tree_node_t n2 = ALLOCNO_LOOP_TREE_NODE (a2);
2365 if (loop_is_inside_p (n1, n2))
2367 else if (loop_is_inside_p (n2, n1))
2369 /* If allocnos are equally good, sort by allocno numbers, so that
2370 the results of qsort leave nothing to chance. We put allocnos
2371 with higher number first in the list because it is the original
2372 order for allocnos from loops on the same levels. */
2373 return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
2376 /* This array is used to sort allocnos to restore allocno order in
2377 the regno allocno list. */
2378 static ira_allocno_t *regno_allocnos;
2380 /* Restore allocno order for REGNO in the regno allocno list. */
2382 ira_rebuild_regno_allocno_list (int regno)
2387 for (n = 0, a = ira_regno_allocno_map[regno];
2389 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2390 regno_allocnos[n++] = a;
2392 qsort (regno_allocnos, n, sizeof (ira_allocno_t),
2393 regno_allocno_order_compare_func);
2394 for (i = 1; i < n; i++)
2395 ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[i - 1]) = regno_allocnos[i];
2396 ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[n - 1]) = NULL;
2397 ira_regno_allocno_map[regno] = regno_allocnos[0];
2398 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2399 fprintf (ira_dump_file, " Rebuilding regno allocno list for %d\n", regno);
2402 /* Propagate info from allocno FROM_A to allocno A. */
2404 propagate_some_info_from_allocno (ira_allocno_t a, ira_allocno_t from_a)
2406 enum reg_class aclass;
2408 merge_hard_reg_conflicts (from_a, a, false);
2409 ALLOCNO_NREFS (a) += ALLOCNO_NREFS (from_a);
2410 ALLOCNO_FREQ (a) += ALLOCNO_FREQ (from_a);
2411 ALLOCNO_CALL_FREQ (a) += ALLOCNO_CALL_FREQ (from_a);
2412 ALLOCNO_CALLS_CROSSED_NUM (a) += ALLOCNO_CALLS_CROSSED_NUM (from_a);
2413 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a)
2414 += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (from_a);
2415 IOR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a),
2416 ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (from_a));
2418 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a)
2419 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (from_a);
2420 if (! ALLOCNO_BAD_SPILL_P (from_a))
2421 ALLOCNO_BAD_SPILL_P (a) = false;
2422 aclass = ALLOCNO_CLASS (from_a);
2423 ira_assert (aclass == ALLOCNO_CLASS (a));
2424 ira_allocate_and_accumulate_costs (&ALLOCNO_HARD_REG_COSTS (a), aclass,
2425 ALLOCNO_HARD_REG_COSTS (from_a));
2426 ira_allocate_and_accumulate_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
2428 ALLOCNO_CONFLICT_HARD_REG_COSTS (from_a));
2429 ALLOCNO_CLASS_COST (a) += ALLOCNO_CLASS_COST (from_a);
2430 ALLOCNO_MEMORY_COST (a) += ALLOCNO_MEMORY_COST (from_a);
2433 /* Remove allocnos from loops removed from the allocation
2436 remove_unnecessary_allocnos (void)
2439 bool merged_p, rebuild_p;
2440 ira_allocno_t a, prev_a, next_a, parent_a;
2441 ira_loop_tree_node_t a_node, parent;
2444 regno_allocnos = NULL;
2445 for (regno = max_reg_num () - 1; regno >= FIRST_PSEUDO_REGISTER; regno--)
2448 for (prev_a = NULL, a = ira_regno_allocno_map[regno];
2452 next_a = ALLOCNO_NEXT_REGNO_ALLOCNO (a);
2453 a_node = ALLOCNO_LOOP_TREE_NODE (a);
2454 if (! a_node->to_remove_p)
2458 for (parent = a_node->parent;
2459 (parent_a = parent->regno_allocno_map[regno]) == NULL
2460 && parent->to_remove_p;
2461 parent = parent->parent)
2463 if (parent_a == NULL)
2465 /* There are no allocnos with the same regno in
2466 upper region -- just move the allocno to the
2469 ALLOCNO_LOOP_TREE_NODE (a) = parent;
2470 parent->regno_allocno_map[regno] = a;
2471 bitmap_set_bit (parent->all_allocnos, ALLOCNO_NUM (a));
2476 /* Remove the allocno and update info of allocno in
2477 the upper region. */
2479 ira_regno_allocno_map[regno] = next_a;
2481 ALLOCNO_NEXT_REGNO_ALLOCNO (prev_a) = next_a;
2482 move_allocno_live_ranges (a, parent_a);
2484 propagate_some_info_from_allocno (parent_a, a);
2485 /* Remove it from the corresponding regno allocno
2486 map to avoid info propagation of subsequent
2487 allocno into this already removed allocno. */
2488 a_node->regno_allocno_map[regno] = NULL;
2489 ira_remove_allocno_prefs (a);
2495 /* We need to restore the order in regno allocno list. */
2497 if (regno_allocnos == NULL)
2499 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
2500 * ira_allocnos_num);
2501 ira_rebuild_regno_allocno_list (regno);
2505 ira_rebuild_start_finish_chains ();
2506 if (regno_allocnos != NULL)
2507 ira_free (regno_allocnos);
2510 /* Remove allocnos from all loops but the root. */
2512 remove_low_level_allocnos (void)
2515 bool merged_p, propagate_p;
2516 ira_allocno_t a, top_a;
2517 ira_loop_tree_node_t a_node, parent;
2518 ira_allocno_iterator ai;
2521 FOR_EACH_ALLOCNO (a, ai)
2523 a_node = ALLOCNO_LOOP_TREE_NODE (a);
2524 if (a_node == ira_loop_tree_root || ALLOCNO_CAP_MEMBER (a) != NULL)
2526 regno = ALLOCNO_REGNO (a);
2527 if ((top_a = ira_loop_tree_root->regno_allocno_map[regno]) == NULL)
2529 ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
2530 ira_loop_tree_root->regno_allocno_map[regno] = a;
2533 propagate_p = a_node->parent->regno_allocno_map[regno] == NULL;
2534 /* Remove the allocno and update info of allocno in the upper
2536 move_allocno_live_ranges (a, top_a);
2539 propagate_some_info_from_allocno (top_a, a);
2541 FOR_EACH_ALLOCNO (a, ai)
2543 a_node = ALLOCNO_LOOP_TREE_NODE (a);
2544 if (a_node == ira_loop_tree_root)
2546 parent = a_node->parent;
2547 regno = ALLOCNO_REGNO (a);
2548 if (ALLOCNO_CAP_MEMBER (a) != NULL)
2549 ira_assert (ALLOCNO_CAP (a) != NULL);
2550 else if (ALLOCNO_CAP (a) == NULL)
2551 ira_assert (parent->regno_allocno_map[regno] != NULL);
2553 FOR_EACH_ALLOCNO (a, ai)
2555 regno = ALLOCNO_REGNO (a);
2556 if (ira_loop_tree_root->regno_allocno_map[regno] == a)
2559 ira_allocno_object_iterator oi;
2561 ira_regno_allocno_map[regno] = a;
2562 ALLOCNO_NEXT_REGNO_ALLOCNO (a) = NULL;
2563 ALLOCNO_CAP_MEMBER (a) = NULL;
2564 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2565 COPY_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
2566 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
2568 if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
2569 ALLOCNO_NO_STACK_REG_P (a) = true;
2574 ira_remove_allocno_prefs (a);
2579 ira_rebuild_start_finish_chains ();
2582 /* Remove loops from consideration. We remove all loops except for
2583 root if ALL_P or loops for which a separate allocation will not
2584 improve the result. We have to do this after allocno creation and
2585 their costs and allocno class evaluation because only after that
2586 the register pressure can be known and is calculated. */
2588 remove_unnecessary_regions (bool all_p)
2590 if (current_loops == NULL)
2593 mark_all_loops_for_removal ();
2595 mark_loops_for_removal ();
2596 children_vec.create (last_basic_block_for_fn (cfun)
2597 + number_of_loops (cfun));
2598 removed_loop_vec.create (last_basic_block_for_fn (cfun)
2599 + number_of_loops (cfun));
2600 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_root);
2601 children_vec.release ();
2603 remove_low_level_allocnos ();
2605 remove_unnecessary_allocnos ();
2606 while (removed_loop_vec.length () > 0)
2607 finish_loop_tree_node (removed_loop_vec.pop ());
2608 removed_loop_vec.release ();
2613 /* At this point true value of allocno attribute bad_spill_p means
2614 that there is an insn where allocno occurs and where the allocno
2615 can not be used as memory. The function updates the attribute, now
2616 it can be true only for allocnos which can not be used as memory in
2617 an insn and in whose live ranges there is other allocno deaths.
2618 Spilling allocnos with true value will not improve the code because
2619 it will not make other allocnos colorable and additional reloads
2620 for the corresponding pseudo will be generated in reload pass for
2621 each insn it occurs.
2623 This is a trick mentioned in one classic article of Chaitin etc
2624 which is frequently omitted in other implementations of RA based on
2627 update_bad_spill_attribute (void)
2631 ira_allocno_iterator ai;
2632 ira_allocno_object_iterator aoi;
2635 enum reg_class aclass;
2636 bitmap_head dead_points[N_REG_CLASSES];
2638 for (i = 0; i < ira_allocno_classes_num; i++)
2640 aclass = ira_allocno_classes[i];
2641 bitmap_initialize (&dead_points[aclass], ®_obstack);
2643 FOR_EACH_ALLOCNO (a, ai)
2645 aclass = ALLOCNO_CLASS (a);
2646 if (aclass == NO_REGS)
2648 FOR_EACH_ALLOCNO_OBJECT (a, obj, aoi)
2649 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
2650 bitmap_set_bit (&dead_points[aclass], r->finish);
2652 FOR_EACH_ALLOCNO (a, ai)
2654 aclass = ALLOCNO_CLASS (a);
2655 if (aclass == NO_REGS)
2657 if (! ALLOCNO_BAD_SPILL_P (a))
2659 FOR_EACH_ALLOCNO_OBJECT (a, obj, aoi)
2661 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
2663 for (i = r->start + 1; i < r->finish; i++)
2664 if (bitmap_bit_p (&dead_points[aclass], i))
2671 ALLOCNO_BAD_SPILL_P (a) = false;
2676 for (i = 0; i < ira_allocno_classes_num; i++)
2678 aclass = ira_allocno_classes[i];
2679 bitmap_clear (&dead_points[aclass]);
2685 /* Set up minimal and maximal live range points for allocnos. */
2687 setup_min_max_allocno_live_range_point (void)
2690 ira_allocno_t a, parent_a, cap;
2691 ira_allocno_iterator ai;
2692 #ifdef ENABLE_IRA_CHECKING
2693 ira_object_iterator oi;
2697 ira_loop_tree_node_t parent;
2699 FOR_EACH_ALLOCNO (a, ai)
2701 int n = ALLOCNO_NUM_OBJECTS (a);
2703 for (i = 0; i < n; i++)
2705 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2706 r = OBJECT_LIVE_RANGES (obj);
2709 OBJECT_MAX (obj) = r->finish;
2710 for (; r->next != NULL; r = r->next)
2712 OBJECT_MIN (obj) = r->start;
2715 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
2716 for (a = ira_regno_allocno_map[i];
2718 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2721 int n = ALLOCNO_NUM_OBJECTS (a);
2723 for (j = 0; j < n; j++)
2725 ira_object_t obj = ALLOCNO_OBJECT (a, j);
2726 ira_object_t parent_obj;
2728 if (OBJECT_MAX (obj) < 0)
2730 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2731 /* Accumulation of range info. */
2732 if (ALLOCNO_CAP (a) != NULL)
2734 for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
2736 ira_object_t cap_obj = ALLOCNO_OBJECT (cap, j);
2737 if (OBJECT_MAX (cap_obj) < OBJECT_MAX (obj))
2738 OBJECT_MAX (cap_obj) = OBJECT_MAX (obj);
2739 if (OBJECT_MIN (cap_obj) > OBJECT_MIN (obj))
2740 OBJECT_MIN (cap_obj) = OBJECT_MIN (obj);
2744 if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL)
2746 parent_a = parent->regno_allocno_map[i];
2747 parent_obj = ALLOCNO_OBJECT (parent_a, j);
2748 if (OBJECT_MAX (parent_obj) < OBJECT_MAX (obj))
2749 OBJECT_MAX (parent_obj) = OBJECT_MAX (obj);
2750 if (OBJECT_MIN (parent_obj) > OBJECT_MIN (obj))
2751 OBJECT_MIN (parent_obj) = OBJECT_MIN (obj);
2754 #ifdef ENABLE_IRA_CHECKING
2755 FOR_EACH_OBJECT (obj, oi)
2757 if ((0 <= OBJECT_MIN (obj) && OBJECT_MIN (obj) <= ira_max_point)
2758 && (0 <= OBJECT_MAX (obj) && OBJECT_MAX (obj) <= ira_max_point))
2765 /* Sort allocnos according to their live ranges. Allocnos with
2766 smaller allocno class are put first unless we use priority
2767 coloring. Allocnos with the same class are ordered according
2768 their start (min). Allocnos with the same start are ordered
2769 according their finish (max). */
2771 object_range_compare_func (const void *v1p, const void *v2p)
2774 ira_object_t obj1 = *(const ira_object_t *) v1p;
2775 ira_object_t obj2 = *(const ira_object_t *) v2p;
2776 ira_allocno_t a1 = OBJECT_ALLOCNO (obj1);
2777 ira_allocno_t a2 = OBJECT_ALLOCNO (obj2);
2779 if ((diff = OBJECT_MIN (obj1) - OBJECT_MIN (obj2)) != 0)
2781 if ((diff = OBJECT_MAX (obj1) - OBJECT_MAX (obj2)) != 0)
2783 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2786 /* Sort ira_object_id_map and set up conflict id of allocnos. */
2788 sort_conflict_id_map (void)
2792 ira_allocno_iterator ai;
2795 FOR_EACH_ALLOCNO (a, ai)
2797 ira_allocno_object_iterator oi;
2800 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2801 ira_object_id_map[num++] = obj;
2804 qsort (ira_object_id_map, num, sizeof (ira_object_t),
2805 object_range_compare_func);
2806 for (i = 0; i < num; i++)
2808 ira_object_t obj = ira_object_id_map[i];
2810 gcc_assert (obj != NULL);
2811 OBJECT_CONFLICT_ID (obj) = i;
2813 for (i = num; i < ira_objects_num; i++)
2814 ira_object_id_map[i] = NULL;
2817 /* Set up minimal and maximal conflict ids of allocnos with which
2818 given allocno can conflict. */
2820 setup_min_max_conflict_allocno_ids (void)
2823 int i, j, min, max, start, finish, first_not_finished, filled_area_start;
2824 int *live_range_min, *last_lived;
2825 int word0_min, word0_max;
2827 ira_allocno_iterator ai;
2829 live_range_min = (int *) ira_allocate (sizeof (int) * ira_objects_num);
2831 first_not_finished = -1;
2832 for (i = 0; i < ira_objects_num; i++)
2834 ira_object_t obj = ira_object_id_map[i];
2839 a = OBJECT_ALLOCNO (obj);
2843 aclass = ALLOCNO_CLASS (a);
2845 first_not_finished = i;
2849 start = OBJECT_MIN (obj);
2850 /* If we skip an allocno, the allocno with smaller ids will
2851 be also skipped because of the secondary sorting the
2852 range finishes (see function
2853 object_range_compare_func). */
2854 while (first_not_finished < i
2855 && start > OBJECT_MAX (ira_object_id_map
2856 [first_not_finished]))
2857 first_not_finished++;
2858 min = first_not_finished;
2861 /* We could increase min further in this case but it is good
2864 live_range_min[i] = OBJECT_MIN (obj);
2865 OBJECT_MIN (obj) = min;
2867 last_lived = (int *) ira_allocate (sizeof (int) * ira_max_point);
2869 filled_area_start = -1;
2870 for (i = ira_objects_num - 1; i >= 0; i--)
2872 ira_object_t obj = ira_object_id_map[i];
2877 a = OBJECT_ALLOCNO (obj);
2880 aclass = ALLOCNO_CLASS (a);
2881 for (j = 0; j < ira_max_point; j++)
2883 filled_area_start = ira_max_point;
2885 min = live_range_min[i];
2886 finish = OBJECT_MAX (obj);
2887 max = last_lived[finish];
2889 /* We could decrease max further in this case but it is good
2891 max = OBJECT_CONFLICT_ID (obj) - 1;
2892 OBJECT_MAX (obj) = max;
2893 /* In filling, we can go further A range finish to recognize
2894 intersection quickly because if the finish of subsequently
2895 processed allocno (it has smaller conflict id) range is
2896 further A range finish than they are definitely intersected
2897 (the reason for this is the allocnos with bigger conflict id
2898 have their range starts not smaller than allocnos with
2900 for (j = min; j < filled_area_start; j++)
2902 filled_area_start = min;
2904 ira_free (last_lived);
2905 ira_free (live_range_min);
2907 /* For allocnos with more than one object, we may later record extra conflicts in
2908 subobject 0 that we cannot really know about here.
2909 For now, simply widen the min/max range of these subobjects. */
2911 word0_min = INT_MAX;
2912 word0_max = INT_MIN;
2914 FOR_EACH_ALLOCNO (a, ai)
2916 int n = ALLOCNO_NUM_OBJECTS (a);
2921 obj0 = ALLOCNO_OBJECT (a, 0);
2922 if (OBJECT_CONFLICT_ID (obj0) < word0_min)
2923 word0_min = OBJECT_CONFLICT_ID (obj0);
2924 if (OBJECT_CONFLICT_ID (obj0) > word0_max)
2925 word0_max = OBJECT_CONFLICT_ID (obj0);
2927 FOR_EACH_ALLOCNO (a, ai)
2929 int n = ALLOCNO_NUM_OBJECTS (a);
2934 obj0 = ALLOCNO_OBJECT (a, 0);
2935 if (OBJECT_MIN (obj0) > word0_min)
2936 OBJECT_MIN (obj0) = word0_min;
2937 if (OBJECT_MAX (obj0) < word0_max)
2938 OBJECT_MAX (obj0) = word0_max;
2948 ira_allocno_iterator ai;
2949 ira_loop_tree_node_t loop_tree_node;
2951 FOR_EACH_ALLOCNO (a, ai)
2953 if (ALLOCNO_LOOP_TREE_NODE (a) == ira_loop_tree_root)
2955 if (ALLOCNO_CAP_MEMBER (a) != NULL)
2956 create_cap_allocno (a);
2957 else if (ALLOCNO_CAP (a) == NULL)
2959 loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
2960 if (!bitmap_bit_p (loop_tree_node->border_allocnos, ALLOCNO_NUM (a)))
2961 create_cap_allocno (a);
2968 /* The page contains code transforming more one region internal
2969 representation (IR) to one region IR which is necessary for reload.
2970 This transformation is called IR flattening. We might just rebuild
2971 the IR for one region but we don't do it because it takes a lot of
2974 /* Map: regno -> allocnos which will finally represent the regno for
2975 IR with one region. */
2976 static ira_allocno_t *regno_top_level_allocno_map;
2978 /* Find the allocno that corresponds to A at a level one higher up in the
2979 loop tree. Returns NULL if A is a cap, or if it has no parent. */
2981 ira_parent_allocno (ira_allocno_t a)
2983 ira_loop_tree_node_t parent;
2985 if (ALLOCNO_CAP (a) != NULL)
2988 parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
2992 return parent->regno_allocno_map[ALLOCNO_REGNO (a)];
2995 /* Find the allocno that corresponds to A at a level one higher up in the
2996 loop tree. If ALLOCNO_CAP is set for A, return that. */
2998 ira_parent_or_cap_allocno (ira_allocno_t a)
3000 if (ALLOCNO_CAP (a) != NULL)
3001 return ALLOCNO_CAP (a);
3003 return ira_parent_allocno (a);
3006 /* Process all allocnos originated from pseudo REGNO and copy live
3007 ranges, hard reg conflicts, and allocno stack reg attributes from
3008 low level allocnos to final allocnos which are destinations of
3009 removed stores at a loop exit. Return true if we copied live
3012 copy_info_to_removed_store_destinations (int regno)
3015 ira_allocno_t parent_a = NULL;
3016 ira_loop_tree_node_t parent;
3020 for (a = ira_regno_allocno_map[regno];
3022 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
3024 if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))])
3025 /* This allocno will be removed. */
3028 /* Caps will be removed. */
3029 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
3030 for (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
3032 parent = parent->parent)
3033 if ((parent_a = parent->regno_allocno_map[regno]) == NULL
3035 == regno_top_level_allocno_map[REGNO
3036 (allocno_emit_reg (parent_a))]
3037 && ALLOCNO_EMIT_DATA (parent_a)->mem_optimized_dest_p))
3039 if (parent == NULL || parent_a == NULL)
3042 copy_allocno_live_ranges (a, parent_a);
3043 merge_hard_reg_conflicts (a, parent_a, true);
3045 ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
3046 ALLOCNO_CALLS_CROSSED_NUM (parent_a)
3047 += ALLOCNO_CALLS_CROSSED_NUM (a);
3048 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
3049 += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
3050 IOR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (parent_a),
3051 ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a));
3052 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
3053 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
3059 /* Flatten the IR. In other words, this function transforms IR as if
3060 it were built with one region (without loops). We could make it
3061 much simpler by rebuilding IR with one region, but unfortunately it
3062 takes a lot of time. MAX_REGNO_BEFORE_EMIT and
3063 IRA_MAX_POINT_BEFORE_EMIT are correspondingly MAX_REG_NUM () and
3064 IRA_MAX_POINT before emitting insns on the loop borders. */
3066 ira_flattening (int max_regno_before_emit, int ira_max_point_before_emit)
3071 bool new_pseudos_p, merged_p, mem_dest_p;
3073 enum reg_class aclass;
3074 ira_allocno_t a, parent_a, first, second, node_first, node_second;
3076 ira_loop_tree_node_t node;
3078 ira_allocno_iterator ai;
3079 ira_copy_iterator ci;
3081 regno_top_level_allocno_map
3082 = (ira_allocno_t *) ira_allocate (max_reg_num ()
3083 * sizeof (ira_allocno_t));
3084 memset (regno_top_level_allocno_map, 0,
3085 max_reg_num () * sizeof (ira_allocno_t));
3086 new_pseudos_p = merged_p = false;
3087 FOR_EACH_ALLOCNO (a, ai)
3089 ira_allocno_object_iterator oi;
3092 if (ALLOCNO_CAP_MEMBER (a) != NULL)
3093 /* Caps are not in the regno allocno maps and they are never
3094 will be transformed into allocnos existing after IR
3097 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
3098 COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
3099 OBJECT_CONFLICT_HARD_REGS (obj));
3101 ALLOCNO_TOTAL_NO_STACK_REG_P (a) = ALLOCNO_NO_STACK_REG_P (a);
3104 /* Fix final allocno attributes. */
3105 for (i = max_regno_before_emit - 1; i >= FIRST_PSEUDO_REGISTER; i--)
3108 for (a = ira_regno_allocno_map[i];
3110 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
3112 ira_emit_data_t parent_data, data = ALLOCNO_EMIT_DATA (a);
3114 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
3115 if (data->somewhere_renamed_p)
3116 new_pseudos_p = true;
3117 parent_a = ira_parent_allocno (a);
3118 if (parent_a == NULL)
3120 ALLOCNO_COPIES (a) = NULL;
3121 regno_top_level_allocno_map[REGNO (data->reg)] = a;
3124 ira_assert (ALLOCNO_CAP_MEMBER (parent_a) == NULL);
3126 if (data->mem_optimized_dest != NULL)
3128 parent_data = ALLOCNO_EMIT_DATA (parent_a);
3129 if (REGNO (data->reg) == REGNO (parent_data->reg))
3131 merge_hard_reg_conflicts (a, parent_a, true);
3132 move_allocno_live_ranges (a, parent_a);
3134 parent_data->mem_optimized_dest_p
3135 = (parent_data->mem_optimized_dest_p
3136 || data->mem_optimized_dest_p);
3139 new_pseudos_p = true;
3142 ALLOCNO_NREFS (parent_a) -= ALLOCNO_NREFS (a);
3143 ALLOCNO_FREQ (parent_a) -= ALLOCNO_FREQ (a);
3144 ALLOCNO_CALL_FREQ (parent_a) -= ALLOCNO_CALL_FREQ (a);
3145 ALLOCNO_CALLS_CROSSED_NUM (parent_a)
3146 -= ALLOCNO_CALLS_CROSSED_NUM (a);
3147 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
3148 -= ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
3149 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
3150 -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
3151 ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a) >= 0
3152 && ALLOCNO_NREFS (parent_a) >= 0
3153 && ALLOCNO_FREQ (parent_a) >= 0);
3154 aclass = ALLOCNO_CLASS (parent_a);
3155 hard_regs_num = ira_class_hard_regs_num[aclass];
3156 if (ALLOCNO_HARD_REG_COSTS (a) != NULL
3157 && ALLOCNO_HARD_REG_COSTS (parent_a) != NULL)
3158 for (j = 0; j < hard_regs_num; j++)
3159 ALLOCNO_HARD_REG_COSTS (parent_a)[j]
3160 -= ALLOCNO_HARD_REG_COSTS (a)[j];
3161 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL
3162 && ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a) != NULL)
3163 for (j = 0; j < hard_regs_num; j++)
3164 ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a)[j]
3165 -= ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[j];
3166 ALLOCNO_CLASS_COST (parent_a)
3167 -= ALLOCNO_CLASS_COST (a);
3168 ALLOCNO_MEMORY_COST (parent_a) -= ALLOCNO_MEMORY_COST (a);
3169 parent_a = ira_parent_allocno (parent_a);
3170 if (parent_a == NULL)
3173 ALLOCNO_COPIES (a) = NULL;
3174 regno_top_level_allocno_map[REGNO (data->reg)] = a;
3176 if (mem_dest_p && copy_info_to_removed_store_destinations (i))
3179 ira_assert (new_pseudos_p || ira_max_point_before_emit == ira_max_point);
3180 if (merged_p || ira_max_point_before_emit != ira_max_point)
3181 ira_rebuild_start_finish_chains ();
3184 sparseset objects_live;
3186 /* Rebuild conflicts. */
3187 FOR_EACH_ALLOCNO (a, ai)
3189 ira_allocno_object_iterator oi;
3192 if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
3193 || ALLOCNO_CAP_MEMBER (a) != NULL)
3195 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
3197 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
3198 ira_assert (r->object == obj);
3199 clear_conflicts (obj);
3202 objects_live = sparseset_alloc (ira_objects_num);
3203 for (i = 0; i < ira_max_point; i++)
3205 for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next)
3207 ira_object_t obj = r->object;
3209 a = OBJECT_ALLOCNO (obj);
3210 if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
3211 || ALLOCNO_CAP_MEMBER (a) != NULL)
3214 aclass = ALLOCNO_CLASS (a);
3215 EXECUTE_IF_SET_IN_SPARSESET (objects_live, n)
3217 ira_object_t live_obj = ira_object_id_map[n];
3218 ira_allocno_t live_a = OBJECT_ALLOCNO (live_obj);
3219 enum reg_class live_aclass = ALLOCNO_CLASS (live_a);
3221 if (ira_reg_classes_intersect_p[aclass][live_aclass]
3222 /* Don't set up conflict for the allocno with itself. */
3224 ira_add_conflict (obj, live_obj);
3226 sparseset_set_bit (objects_live, OBJECT_CONFLICT_ID (obj));
3229 for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
3230 sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (r->object));
3232 sparseset_free (objects_live);
3233 compress_conflict_vecs ();
3235 /* Mark some copies for removing and change allocnos in the rest
3237 FOR_EACH_COPY (cp, ci)
3239 if (ALLOCNO_CAP_MEMBER (cp->first) != NULL
3240 || ALLOCNO_CAP_MEMBER (cp->second) != NULL)
3242 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
3244 (ira_dump_file, " Remove cp%d:%c%dr%d-%c%dr%d\n",
3245 cp->num, ALLOCNO_CAP_MEMBER (cp->first) != NULL ? 'c' : 'a',
3246 ALLOCNO_NUM (cp->first),
3247 REGNO (allocno_emit_reg (cp->first)),
3248 ALLOCNO_CAP_MEMBER (cp->second) != NULL ? 'c' : 'a',
3249 ALLOCNO_NUM (cp->second),
3250 REGNO (allocno_emit_reg (cp->second)));
3251 cp->loop_tree_node = NULL;
3255 = regno_top_level_allocno_map[REGNO (allocno_emit_reg (cp->first))];
3257 = regno_top_level_allocno_map[REGNO (allocno_emit_reg (cp->second))];
3258 node = cp->loop_tree_node;
3260 keep_p = true; /* It copy generated in ira-emit.c. */
3263 /* Check that the copy was not propagated from level on
3264 which we will have different pseudos. */
3265 node_first = node->regno_allocno_map[ALLOCNO_REGNO (cp->first)];
3266 node_second = node->regno_allocno_map[ALLOCNO_REGNO (cp->second)];
3267 keep_p = ((REGNO (allocno_emit_reg (first))
3268 == REGNO (allocno_emit_reg (node_first)))
3269 && (REGNO (allocno_emit_reg (second))
3270 == REGNO (allocno_emit_reg (node_second))));
3274 cp->loop_tree_node = ira_loop_tree_root;
3276 cp->second = second;
3280 cp->loop_tree_node = NULL;
3281 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
3282 fprintf (ira_dump_file, " Remove cp%d:a%dr%d-a%dr%d\n",
3283 cp->num, ALLOCNO_NUM (cp->first),
3284 REGNO (allocno_emit_reg (cp->first)),
3285 ALLOCNO_NUM (cp->second),
3286 REGNO (allocno_emit_reg (cp->second)));
3289 /* Remove unnecessary allocnos on lower levels of the loop tree. */
3290 FOR_EACH_ALLOCNO (a, ai)
3292 if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
3293 || ALLOCNO_CAP_MEMBER (a) != NULL)
3295 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
3296 fprintf (ira_dump_file, " Remove a%dr%d\n",
3297 ALLOCNO_NUM (a), REGNO (allocno_emit_reg (a)));
3298 ira_remove_allocno_prefs (a);
3302 ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
3303 ALLOCNO_REGNO (a) = REGNO (allocno_emit_reg (a));
3304 ALLOCNO_CAP (a) = NULL;
3305 /* Restore updated costs for assignments from reload. */
3306 ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
3307 ALLOCNO_UPDATED_CLASS_COST (a) = ALLOCNO_CLASS_COST (a);
3308 if (! ALLOCNO_ASSIGNED_P (a))
3309 ira_free_allocno_updated_costs (a);
3310 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
3311 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
3313 /* Remove unnecessary copies. */
3314 FOR_EACH_COPY (cp, ci)
3316 if (cp->loop_tree_node == NULL)
3318 ira_copies[cp->num] = NULL;
3323 (ALLOCNO_LOOP_TREE_NODE (cp->first) == ira_loop_tree_root
3324 && ALLOCNO_LOOP_TREE_NODE (cp->second) == ira_loop_tree_root);
3325 add_allocno_copy_to_list (cp);
3326 swap_allocno_copy_ends_if_necessary (cp);
3328 rebuild_regno_allocno_maps ();
3329 if (ira_max_point != ira_max_point_before_emit)
3330 ira_compress_allocno_live_ranges ();
3331 ira_free (regno_top_level_allocno_map);
3336 #ifdef ENABLE_IRA_CHECKING
3337 /* Check creation of all allocnos. Allocnos on lower levels should
3338 have allocnos or caps on all upper levels. */
3340 check_allocno_creation (void)
3343 ira_allocno_iterator ai;
3344 ira_loop_tree_node_t loop_tree_node;
3346 FOR_EACH_ALLOCNO (a, ai)
3348 loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
3349 ira_assert (bitmap_bit_p (loop_tree_node->all_allocnos,
3351 if (loop_tree_node == ira_loop_tree_root)
3353 if (ALLOCNO_CAP_MEMBER (a) != NULL)
3354 ira_assert (ALLOCNO_CAP (a) != NULL);
3355 else if (ALLOCNO_CAP (a) == NULL)
3356 ira_assert (loop_tree_node->parent
3357 ->regno_allocno_map[ALLOCNO_REGNO (a)] != NULL
3358 && bitmap_bit_p (loop_tree_node->border_allocnos,
3364 /* Identify allocnos which prefer a register class with a single hard register.
3365 Adjust ALLOCNO_CONFLICT_HARD_REG_COSTS so that conflicting allocnos are
3366 less likely to use the preferred singleton register. */
3368 update_conflict_hard_reg_costs (void)
3371 ira_allocno_iterator ai;
3374 FOR_EACH_ALLOCNO (a, ai)
3376 reg_class_t aclass = ALLOCNO_CLASS (a);
3377 reg_class_t pref = reg_preferred_class (ALLOCNO_REGNO (a));
3378 int singleton = ira_class_singleton[pref][ALLOCNO_MODE (a)];
3381 index = ira_class_hard_reg_index[(int) aclass][singleton];
3384 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) == NULL
3385 || ALLOCNO_HARD_REG_COSTS (a) == NULL)
3388 for (i = ira_class_hard_regs_num[(int) aclass] - 1; i >= 0; i--)
3389 if (ALLOCNO_HARD_REG_COSTS (a)[i] > ALLOCNO_CLASS_COST (a)
3390 && min > ALLOCNO_HARD_REG_COSTS (a)[i])
3391 min = ALLOCNO_HARD_REG_COSTS (a)[i];
3394 ira_allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
3396 ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index]
3397 -= min - ALLOCNO_CLASS_COST (a);
3401 /* Create a internal representation (IR) for IRA (allocnos, copies,
3402 loop tree nodes). The function returns TRUE if we generate loop
3403 structure (besides nodes representing all function and the basic
3404 blocks) for regional allocation. A true return means that we
3405 really need to flatten IR before the reload. */
3412 initiate_cost_vectors ();
3413 initiate_allocnos ();
3416 create_loop_tree_nodes ();
3420 create_allocno_objects ();
3421 ira_create_allocno_live_ranges ();
3422 remove_unnecessary_regions (false);
3423 ira_compress_allocno_live_ranges ();
3424 update_bad_spill_attribute ();
3425 loops_p = more_one_region_p ();
3428 propagate_allocno_info ();
3431 ira_tune_allocno_costs ();
3432 #ifdef ENABLE_IRA_CHECKING
3433 check_allocno_creation ();
3435 setup_min_max_allocno_live_range_point ();
3436 sort_conflict_id_map ();
3437 setup_min_max_conflict_allocno_ids ();
3438 ira_build_conflicts ();
3439 update_conflict_hard_reg_costs ();
3440 if (! ira_conflicts_p)
3443 ira_allocno_iterator ai;
3445 /* Remove all regions but root one. */
3448 remove_unnecessary_regions (true);
3451 /* We don't save hard registers around calls for fast allocation
3452 -- add caller clobbered registers as conflicting ones to
3453 allocno crossing calls. */
3454 FOR_EACH_ALLOCNO (a, ai)
3455 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
3456 ior_hard_reg_conflicts (a, &call_used_reg_set);
3458 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3459 print_copies (ira_dump_file);
3460 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3461 print_prefs (ira_dump_file);
3462 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3467 ira_allocno_iterator ai;
3472 FOR_EACH_ALLOCNO (a, ai)
3474 int j, nobj = ALLOCNO_NUM_OBJECTS (a);
3478 for (j = 0; j < nobj; j++)
3480 ira_object_t obj = ALLOCNO_OBJECT (a, j);
3481 n += OBJECT_NUM_CONFLICTS (obj);
3482 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
3486 fprintf (ira_dump_file, " regions=%d, blocks=%d, points=%d\n",
3487 current_loops == NULL ? 1 : number_of_loops (cfun),
3488 n_basic_blocks_for_fn (cfun), ira_max_point);
3489 fprintf (ira_dump_file,
3490 " allocnos=%d (big %d), copies=%d, conflicts=%d, ranges=%d\n",
3491 ira_allocnos_num, nr_big, ira_copies_num, n, nr);
3496 /* Release the data created by function ira_build. */
3500 finish_loop_tree_nodes ();
3504 finish_cost_vectors ();
3505 ira_finish_allocno_live_ranges ();