1 /* Building internal representation for IRA.
2 Copyright (C) 2006, 2007, 2008
3 Free Software Foundation, Inc.
4 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
33 #include "insn-config.h"
40 #include "sparseset.h"
43 static ira_copy_t find_allocno_copy (ira_allocno_t, ira_allocno_t, rtx,
44 ira_loop_tree_node_t);
46 /* The root of the loop tree corresponding to the all function. */
47 ira_loop_tree_node_t ira_loop_tree_root;
49 /* Height of the loop tree. */
50 int ira_loop_tree_height;
52 /* All nodes representing basic blocks are referred through the
53 following array. We can not use basic block member `aux' for this
54 because it is used for insertion of insns on edges. */
55 ira_loop_tree_node_t ira_bb_nodes;
57 /* All nodes representing loops are referred through the following
59 ira_loop_tree_node_t ira_loop_nodes;
61 /* Map regno -> allocnos with given regno (see comments for
62 allocno member `next_regno_allocno'). */
63 ira_allocno_t *ira_regno_allocno_map;
65 /* Array of references to all allocnos. The order number of the
66 allocno corresponds to the index in the array. Removed allocnos
67 have NULL element value. */
68 ira_allocno_t *ira_allocnos;
70 /* Sizes of the previous array. */
73 /* Map conflict id -> allocno with given conflict id (see comments for
74 allocno member `conflict_id'). */
75 ira_allocno_t *ira_conflict_id_allocno_map;
77 /* Array of references to all copies. The order number of the copy
78 corresponds to the index in the array. Removed copies have NULL
80 ira_copy_t *ira_copies;
82 /* Size of the previous array. */
87 /* LAST_BASIC_BLOCK before generating additional insns because of live
88 range splitting. Emitting insns on a critical edge creates a new
90 static int last_basic_block_before_change;
92 /* The following function allocates the loop tree nodes. If LOOPS_P
93 is FALSE, the nodes corresponding to the loops (except the root
94 which corresponds the all function) will be not allocated but nodes
95 will still be allocated for basic blocks. */
97 create_loop_tree_nodes (bool loops_p)
104 VEC (edge, heap) *edges;
108 = ((struct ira_loop_tree_node *)
109 ira_allocate (sizeof (struct ira_loop_tree_node) * last_basic_block));
110 last_basic_block_before_change = last_basic_block;
111 for (i = 0; i < (unsigned int) last_basic_block; i++)
113 ira_bb_nodes[i].regno_allocno_map = NULL;
114 memset (ira_bb_nodes[i].reg_pressure, 0,
115 sizeof (ira_bb_nodes[i].reg_pressure));
116 ira_bb_nodes[i].all_allocnos = NULL;
117 ira_bb_nodes[i].modified_regnos = NULL;
118 ira_bb_nodes[i].border_allocnos = NULL;
119 ira_bb_nodes[i].local_copies = NULL;
121 ira_loop_nodes = ((struct ira_loop_tree_node *)
122 ira_allocate (sizeof (struct ira_loop_tree_node)
123 * VEC_length (loop_p, ira_loops.larray)));
124 max_regno = max_reg_num ();
125 for (i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
127 if (loop != ira_loops.tree_root)
129 ira_loop_nodes[i].regno_allocno_map = NULL;
133 FOR_EACH_EDGE (e, ei, loop->header->preds)
134 if (e->src != loop->latch
135 && (e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
142 edges = get_loop_exit_edges (loop);
143 for (j = 0; VEC_iterate (edge, edges, j, e); j++)
144 if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
149 VEC_free (edge, heap, edges);
153 ira_loop_nodes[i].regno_allocno_map
154 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t) * max_regno);
155 memset (ira_loop_nodes[i].regno_allocno_map, 0,
156 sizeof (ira_allocno_t) * max_regno);
157 memset (ira_loop_nodes[i].reg_pressure, 0,
158 sizeof (ira_loop_nodes[i].reg_pressure));
159 ira_loop_nodes[i].all_allocnos = ira_allocate_bitmap ();
160 ira_loop_nodes[i].modified_regnos = ira_allocate_bitmap ();
161 ira_loop_nodes[i].border_allocnos = ira_allocate_bitmap ();
162 ira_loop_nodes[i].local_copies = ira_allocate_bitmap ();
166 /* The function returns TRUE if there are more one allocation
169 more_one_region_p (void)
174 for (i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
175 if (ira_loop_nodes[i].regno_allocno_map != NULL
176 && ira_loop_tree_root != &ira_loop_nodes[i])
181 /* Free the loop tree node of a loop. */
183 finish_loop_tree_node (ira_loop_tree_node_t loop)
185 if (loop->regno_allocno_map != NULL)
187 ira_assert (loop->bb == NULL);
188 ira_free_bitmap (loop->local_copies);
189 ira_free_bitmap (loop->border_allocnos);
190 ira_free_bitmap (loop->modified_regnos);
191 ira_free_bitmap (loop->all_allocnos);
192 ira_free (loop->regno_allocno_map);
193 loop->regno_allocno_map = NULL;
197 /* Free the loop tree nodes. */
199 finish_loop_tree_nodes (void)
204 for (i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
205 finish_loop_tree_node (&ira_loop_nodes[i]);
206 ira_free (ira_loop_nodes);
207 for (i = 0; i < (unsigned int) last_basic_block_before_change; i++)
209 if (ira_bb_nodes[i].local_copies != NULL)
210 ira_free_bitmap (ira_bb_nodes[i].local_copies);
211 if (ira_bb_nodes[i].border_allocnos != NULL)
212 ira_free_bitmap (ira_bb_nodes[i].border_allocnos);
213 if (ira_bb_nodes[i].modified_regnos != NULL)
214 ira_free_bitmap (ira_bb_nodes[i].modified_regnos);
215 if (ira_bb_nodes[i].all_allocnos != NULL)
216 ira_free_bitmap (ira_bb_nodes[i].all_allocnos);
217 if (ira_bb_nodes[i].regno_allocno_map != NULL)
218 ira_free (ira_bb_nodes[i].regno_allocno_map);
220 ira_free (ira_bb_nodes);
225 /* The following recursive function adds LOOP to the loop tree
226 hierarchy. LOOP is added only once. */
228 add_loop_to_tree (struct loop *loop)
231 ira_loop_tree_node_t loop_node, parent_node;
233 /* We can not use loop node access macros here because of potential
234 checking and because the nodes are not initialized enough
236 if (loop_outer (loop) != NULL)
237 add_loop_to_tree (loop_outer (loop));
238 if (ira_loop_nodes[loop->num].regno_allocno_map != NULL
239 && ira_loop_nodes[loop->num].children == NULL)
241 /* We have not added loop node to the tree yet. */
242 loop_node = &ira_loop_nodes[loop->num];
243 loop_node->loop = loop;
244 loop_node->bb = NULL;
245 for (parent = loop_outer (loop);
247 parent = loop_outer (parent))
248 if (ira_loop_nodes[parent->num].regno_allocno_map != NULL)
252 loop_node->next = NULL;
253 loop_node->subloop_next = NULL;
254 loop_node->parent = NULL;
258 parent_node = &ira_loop_nodes[parent->num];
259 loop_node->next = parent_node->children;
260 parent_node->children = loop_node;
261 loop_node->subloop_next = parent_node->subloops;
262 parent_node->subloops = loop_node;
263 loop_node->parent = parent_node;
268 /* The following recursive function sets up levels of nodes of the
269 tree given its root LOOP_NODE. The enumeration starts with LEVEL.
270 The function returns maximal value of level in the tree + 1. */
272 setup_loop_tree_level (ira_loop_tree_node_t loop_node, int level)
274 int height, max_height;
275 ira_loop_tree_node_t subloop_node;
277 ira_assert (loop_node->bb == NULL);
278 loop_node->level = level;
279 max_height = level + 1;
280 for (subloop_node = loop_node->subloops;
281 subloop_node != NULL;
282 subloop_node = subloop_node->subloop_next)
284 ira_assert (subloop_node->bb == NULL);
285 height = setup_loop_tree_level (subloop_node, level + 1);
286 if (height > max_height)
292 /* Create the loop tree. The algorithm is designed to provide correct
293 order of loops (they are ordered by their last loop BB) and basic
294 blocks in the chain formed by member next. */
296 form_loop_tree (void)
301 ira_loop_tree_node_t bb_node, loop_node;
304 /* We can not use loop/bb node access macros because of potential
305 checking and because the nodes are not initialized enough
307 for (i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
308 if (ira_loop_nodes[i].regno_allocno_map != NULL)
310 ira_loop_nodes[i].children = NULL;
311 ira_loop_nodes[i].subloops = NULL;
315 bb_node = &ira_bb_nodes[bb->index];
317 bb_node->loop = NULL;
318 bb_node->subloops = NULL;
319 bb_node->children = NULL;
320 bb_node->subloop_next = NULL;
321 bb_node->next = NULL;
322 for (parent = bb->loop_father;
324 parent = loop_outer (parent))
325 if (ira_loop_nodes[parent->num].regno_allocno_map != NULL)
327 add_loop_to_tree (parent);
328 loop_node = &ira_loop_nodes[parent->num];
329 bb_node->next = loop_node->children;
330 bb_node->parent = loop_node;
331 loop_node->children = bb_node;
333 ira_loop_tree_root = IRA_LOOP_NODE_BY_INDEX (ira_loops.tree_root->num);
334 ira_loop_tree_height = setup_loop_tree_level (ira_loop_tree_root, 0);
335 ira_assert (ira_loop_tree_root->regno_allocno_map != NULL);
340 /* Rebuild IRA_REGNO_ALLOCNO_MAP and REGNO_ALLOCNO_MAPs of the loop
343 rebuild_regno_allocno_maps (void)
346 int max_regno, regno;
348 ira_loop_tree_node_t loop_tree_node;
350 ira_allocno_iterator ai;
352 max_regno = max_reg_num ();
353 for (l = 0; VEC_iterate (loop_p, ira_loops.larray, l, loop); l++)
354 if (ira_loop_nodes[l].regno_allocno_map != NULL)
356 ira_free (ira_loop_nodes[l].regno_allocno_map);
357 ira_loop_nodes[l].regno_allocno_map
358 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
360 memset (ira_loop_nodes[l].regno_allocno_map, 0,
361 sizeof (ira_allocno_t) * max_regno);
363 ira_free (ira_regno_allocno_map);
364 ira_regno_allocno_map
365 = (ira_allocno_t *) ira_allocate (max_regno * sizeof (ira_allocno_t));
366 memset (ira_regno_allocno_map, 0, max_regno * sizeof (ira_allocno_t));
367 FOR_EACH_ALLOCNO (a, ai)
369 if (ALLOCNO_CAP_MEMBER (a) != NULL)
370 /* Caps are not in the regno allocno maps. */
372 regno = ALLOCNO_REGNO (a);
373 loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
374 ALLOCNO_NEXT_REGNO_ALLOCNO (a) = ira_regno_allocno_map[regno];
375 ira_regno_allocno_map[regno] = a;
376 if (loop_tree_node->regno_allocno_map[regno] == NULL)
377 /* Remember that we can create temporary allocnos to break
378 cycles in register shuffle. */
379 loop_tree_node->regno_allocno_map[regno] = a;
385 /* Pools for allocnos and allocno live ranges. */
386 static alloc_pool allocno_pool, allocno_live_range_pool;
388 /* Vec containing references to all created allocnos. It is a
389 container of array allocnos. */
390 static VEC(ira_allocno_t,heap) *allocno_vec;
392 /* Vec containing references to all created allocnos. It is a
393 container of ira_conflict_id_allocno_map. */
394 static VEC(ira_allocno_t,heap) *ira_conflict_id_allocno_map_vec;
396 /* Initialize data concerning allocnos. */
398 initiate_allocnos (void)
400 allocno_live_range_pool
401 = create_alloc_pool ("allocno live ranges",
402 sizeof (struct ira_allocno_live_range), 100);
404 = create_alloc_pool ("allocnos", sizeof (struct ira_allocno), 100);
405 allocno_vec = VEC_alloc (ira_allocno_t, heap, max_reg_num () * 2);
407 ira_allocnos_num = 0;
408 ira_conflict_id_allocno_map_vec
409 = VEC_alloc (ira_allocno_t, heap, max_reg_num () * 2);
410 ira_conflict_id_allocno_map = NULL;
411 ira_regno_allocno_map
412 = (ira_allocno_t *) ira_allocate (max_reg_num () * sizeof (ira_allocno_t));
413 memset (ira_regno_allocno_map, 0, max_reg_num () * sizeof (ira_allocno_t));
416 /* Create and return the allocno corresponding to REGNO in
417 LOOP_TREE_NODE. Add the allocno to the list of allocnos with the
418 same regno if CAP_P is FALSE. */
420 ira_create_allocno (int regno, bool cap_p, ira_loop_tree_node_t loop_tree_node)
424 a = (ira_allocno_t) pool_alloc (allocno_pool);
425 ALLOCNO_REGNO (a) = regno;
426 ALLOCNO_LOOP_TREE_NODE (a) = loop_tree_node;
429 ALLOCNO_NEXT_REGNO_ALLOCNO (a) = ira_regno_allocno_map[regno];
430 ira_regno_allocno_map[regno] = a;
431 if (loop_tree_node->regno_allocno_map[regno] == NULL)
432 /* Remember that we can create temporary allocnos to break
433 cycles in register shuffle on region borders (see
435 loop_tree_node->regno_allocno_map[regno] = a;
437 ALLOCNO_CAP (a) = NULL;
438 ALLOCNO_CAP_MEMBER (a) = NULL;
439 ALLOCNO_NUM (a) = ira_allocnos_num;
440 bitmap_set_bit (loop_tree_node->all_allocnos, ALLOCNO_NUM (a));
441 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) = NULL;
442 ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = 0;
443 COPY_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a), ira_no_alloc_regs);
444 COPY_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), ira_no_alloc_regs);
445 ALLOCNO_NREFS (a) = 0;
446 ALLOCNO_FREQ (a) = 0;
447 ALLOCNO_HARD_REGNO (a) = -1;
448 ALLOCNO_CALL_FREQ (a) = 0;
449 ALLOCNO_CALLS_CROSSED_NUM (a) = 0;
451 ALLOCNO_NO_STACK_REG_P (a) = false;
452 ALLOCNO_TOTAL_NO_STACK_REG_P (a) = false;
454 ALLOCNO_MEM_OPTIMIZED_DEST (a) = NULL;
455 ALLOCNO_MEM_OPTIMIZED_DEST_P (a) = false;
456 ALLOCNO_SOMEWHERE_RENAMED_P (a) = false;
457 ALLOCNO_CHILD_RENAMED_P (a) = false;
458 ALLOCNO_DONT_REASSIGN_P (a) = false;
459 ALLOCNO_BAD_SPILL_P (a) = false;
460 ALLOCNO_IN_GRAPH_P (a) = false;
461 ALLOCNO_ASSIGNED_P (a) = false;
462 ALLOCNO_MAY_BE_SPILLED_P (a) = false;
463 ALLOCNO_SPLAY_REMOVED_P (a) = false;
464 ALLOCNO_CONFLICT_VEC_P (a) = false;
465 ALLOCNO_MODE (a) = (regno < 0 ? VOIDmode : PSEUDO_REGNO_MODE (regno));
466 ALLOCNO_COPIES (a) = NULL;
467 ALLOCNO_HARD_REG_COSTS (a) = NULL;
468 ALLOCNO_CONFLICT_HARD_REG_COSTS (a) = NULL;
469 ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
470 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
471 ALLOCNO_LEFT_CONFLICTS_NUM (a) = -1;
472 ALLOCNO_COVER_CLASS (a) = NO_REGS;
473 ALLOCNO_UPDATED_COVER_CLASS_COST (a) = 0;
474 ALLOCNO_COVER_CLASS_COST (a) = 0;
475 ALLOCNO_MEMORY_COST (a) = 0;
476 ALLOCNO_UPDATED_MEMORY_COST (a) = 0;
477 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) = 0;
478 ALLOCNO_NEXT_BUCKET_ALLOCNO (a) = NULL;
479 ALLOCNO_PREV_BUCKET_ALLOCNO (a) = NULL;
480 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
481 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
482 ALLOCNO_LIVE_RANGES (a) = NULL;
483 ALLOCNO_MIN (a) = INT_MAX;
484 ALLOCNO_MAX (a) = -1;
485 ALLOCNO_CONFLICT_ID (a) = ira_allocnos_num;
486 VEC_safe_push (ira_allocno_t, heap, allocno_vec, a);
487 ira_allocnos = VEC_address (ira_allocno_t, allocno_vec);
488 ira_allocnos_num = VEC_length (ira_allocno_t, allocno_vec);
489 VEC_safe_push (ira_allocno_t, heap, ira_conflict_id_allocno_map_vec, a);
490 ira_conflict_id_allocno_map
491 = VEC_address (ira_allocno_t, ira_conflict_id_allocno_map_vec);
495 /* Set up cover class for A and update its conflict hard registers. */
497 ira_set_allocno_cover_class (ira_allocno_t a, enum reg_class cover_class)
499 ALLOCNO_COVER_CLASS (a) = cover_class;
500 IOR_COMPL_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
501 reg_class_contents[cover_class]);
502 IOR_COMPL_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
503 reg_class_contents[cover_class]);
506 /* Return TRUE if the conflict vector with NUM elements is more
507 profitable than conflict bit vector for A. */
509 ira_conflict_vector_profitable_p (ira_allocno_t a, int num)
513 if (ALLOCNO_MAX (a) < ALLOCNO_MIN (a))
514 /* We prefer bit vector in such case because it does not result in
518 nw = (ALLOCNO_MAX (a) - ALLOCNO_MIN (a) + IRA_INT_BITS) / IRA_INT_BITS;
519 return (2 * sizeof (ira_allocno_t) * (num + 1)
520 < 3 * nw * sizeof (IRA_INT_TYPE));
523 /* Allocates and initialize the conflict vector of A for NUM
524 conflicting allocnos. */
526 ira_allocate_allocno_conflict_vec (ira_allocno_t a, int num)
531 ira_assert (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) == NULL);
532 num++; /* for NULL end marker */
533 size = sizeof (ira_allocno_t) * num;
534 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) = ira_allocate (size);
535 vec = (ira_allocno_t *) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a);
537 ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = 0;
538 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a) = size;
539 ALLOCNO_CONFLICT_VEC_P (a) = true;
542 /* Allocate and initialize the conflict bit vector of A. */
544 allocate_allocno_conflict_bit_vec (ira_allocno_t a)
548 ira_assert (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) == NULL);
549 size = ((ALLOCNO_MAX (a) - ALLOCNO_MIN (a) + IRA_INT_BITS)
550 / IRA_INT_BITS * sizeof (IRA_INT_TYPE));
551 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) = ira_allocate (size);
552 memset (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a), 0, size);
553 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a) = size;
554 ALLOCNO_CONFLICT_VEC_P (a) = false;
557 /* Allocate and initialize the conflict vector or conflict bit vector
558 of A for NUM conflicting allocnos whatever is more profitable. */
560 ira_allocate_allocno_conflicts (ira_allocno_t a, int num)
562 if (ira_conflict_vector_profitable_p (a, num))
563 ira_allocate_allocno_conflict_vec (a, num);
565 allocate_allocno_conflict_bit_vec (a);
568 /* Add A2 to the conflicts of A1. */
570 add_to_allocno_conflicts (ira_allocno_t a1, ira_allocno_t a2)
575 if (ALLOCNO_CONFLICT_VEC_P (a1))
579 num = ALLOCNO_CONFLICT_ALLOCNOS_NUM (a1) + 2;
580 if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1)
581 >= num * sizeof (ira_allocno_t))
582 vec = (ira_allocno_t *) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1);
585 size = (3 * num / 2 + 1) * sizeof (ira_allocno_t);
586 vec = (ira_allocno_t *) ira_allocate (size);
587 memcpy (vec, ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1),
588 sizeof (ira_allocno_t) * ALLOCNO_CONFLICT_ALLOCNOS_NUM (a1));
589 ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1));
590 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1) = vec;
591 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1) = size;
595 ALLOCNO_CONFLICT_ALLOCNOS_NUM (a1)++;
599 int nw, added_head_nw, id;
602 id = ALLOCNO_CONFLICT_ID (a2);
603 vec = (IRA_INT_TYPE *) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1);
604 if (ALLOCNO_MIN (a1) > id)
606 /* Expand head of the bit vector. */
607 added_head_nw = (ALLOCNO_MIN (a1) - id - 1) / IRA_INT_BITS + 1;
608 nw = (ALLOCNO_MAX (a1) - ALLOCNO_MIN (a1)) / IRA_INT_BITS + 1;
609 size = (nw + added_head_nw) * sizeof (IRA_INT_TYPE);
610 if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1) >= size)
612 memmove ((char *) vec + added_head_nw * sizeof (IRA_INT_TYPE),
613 vec, nw * sizeof (IRA_INT_TYPE));
614 memset (vec, 0, added_head_nw * sizeof (IRA_INT_TYPE));
619 = (3 * (nw + added_head_nw) / 2 + 1) * sizeof (IRA_INT_TYPE);
620 vec = (IRA_INT_TYPE *) ira_allocate (size);
621 memcpy ((char *) vec + added_head_nw * sizeof (IRA_INT_TYPE),
622 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1),
623 nw * sizeof (IRA_INT_TYPE));
624 memset (vec, 0, added_head_nw * sizeof (IRA_INT_TYPE));
626 + (nw + added_head_nw) * sizeof (IRA_INT_TYPE),
627 0, size - (nw + added_head_nw) * sizeof (IRA_INT_TYPE));
628 ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1));
629 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1) = vec;
630 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1) = size;
632 ALLOCNO_MIN (a1) -= added_head_nw * IRA_INT_BITS;
634 else if (ALLOCNO_MAX (a1) < id)
636 nw = (id - ALLOCNO_MIN (a1)) / IRA_INT_BITS + 1;
637 size = nw * sizeof (IRA_INT_TYPE);
638 if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1) < size)
640 /* Expand tail of the bit vector. */
641 size = (3 * nw / 2 + 1) * sizeof (IRA_INT_TYPE);
642 vec = (IRA_INT_TYPE *) ira_allocate (size);
643 memcpy (vec, ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1),
644 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1));
645 memset ((char *) vec + ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1),
646 0, size - ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1));
647 ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1));
648 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1) = vec;
649 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1) = size;
651 ALLOCNO_MAX (a1) = id;
653 SET_ALLOCNO_SET_BIT (vec, id, ALLOCNO_MIN (a1), ALLOCNO_MAX (a1));
657 /* Add A1 to the conflicts of A2 and vise versa. */
659 ira_add_allocno_conflict (ira_allocno_t a1, ira_allocno_t a2)
661 add_to_allocno_conflicts (a1, a2);
662 add_to_allocno_conflicts (a2, a1);
665 /* Clear all conflicts of allocno A. */
667 clear_allocno_conflicts (ira_allocno_t a)
669 if (ALLOCNO_CONFLICT_VEC_P (a))
671 ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = 0;
672 ((ira_allocno_t *) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a))[0] = NULL;
674 else if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a) != 0)
678 nw = (ALLOCNO_MAX (a) - ALLOCNO_MIN (a)) / IRA_INT_BITS + 1;
679 memset (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a), 0,
680 nw * sizeof (IRA_INT_TYPE));
684 /* The array used to find duplications in conflict vectors of
686 static int *allocno_conflict_check;
688 /* The value used to mark allocation presence in conflict vector of
689 the current allocno. */
690 static int curr_allocno_conflict_check_tick;
692 /* Remove duplications in conflict vector of A. */
694 compress_allocno_conflict_vec (ira_allocno_t a)
696 ira_allocno_t *vec, conflict_a;
699 ira_assert (ALLOCNO_CONFLICT_VEC_P (a));
700 vec = (ira_allocno_t *) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a);
701 curr_allocno_conflict_check_tick++;
702 for (i = j = 0; (conflict_a = vec[i]) != NULL; i++)
704 if (allocno_conflict_check[ALLOCNO_NUM (conflict_a)]
705 != curr_allocno_conflict_check_tick)
707 allocno_conflict_check[ALLOCNO_NUM (conflict_a)]
708 = curr_allocno_conflict_check_tick;
709 vec[j++] = conflict_a;
712 ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = j;
716 /* Remove duplications in conflict vectors of all allocnos. */
718 compress_conflict_vecs (void)
721 ira_allocno_iterator ai;
723 allocno_conflict_check
724 = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
725 memset (allocno_conflict_check, 0, sizeof (int) * ira_allocnos_num);
726 curr_allocno_conflict_check_tick = 0;
727 FOR_EACH_ALLOCNO (a, ai)
728 if (ALLOCNO_CONFLICT_VEC_P (a))
729 compress_allocno_conflict_vec (a);
730 ira_free (allocno_conflict_check);
733 /* This recursive function outputs allocno A and if it is a cap the
734 function outputs its members. */
736 ira_print_expanded_allocno (ira_allocno_t a)
740 fprintf (ira_dump_file, " a%d(r%d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
741 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
742 fprintf (ira_dump_file, ",b%d", bb->index);
744 fprintf (ira_dump_file, ",l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop->num);
745 if (ALLOCNO_CAP_MEMBER (a) != NULL)
747 fprintf (ira_dump_file, ":");
748 ira_print_expanded_allocno (ALLOCNO_CAP_MEMBER (a));
750 fprintf (ira_dump_file, ")");
753 /* Create and return the cap representing allocno A in the
756 create_cap_allocno (ira_allocno_t a)
759 ira_loop_tree_node_t parent;
760 enum reg_class cover_class;
762 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a
763 && ALLOCNO_NEXT_COALESCED_ALLOCNO (a) == a);
764 parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
765 cap = ira_create_allocno (ALLOCNO_REGNO (a), true, parent);
766 ALLOCNO_MODE (cap) = ALLOCNO_MODE (a);
767 cover_class = ALLOCNO_COVER_CLASS (a);
768 ira_set_allocno_cover_class (cap, cover_class);
769 ALLOCNO_AVAILABLE_REGS_NUM (cap) = ALLOCNO_AVAILABLE_REGS_NUM (a);
770 ALLOCNO_CAP_MEMBER (cap) = a;
771 ALLOCNO_CAP (a) = cap;
772 ALLOCNO_COVER_CLASS_COST (cap) = ALLOCNO_COVER_CLASS_COST (a);
773 ALLOCNO_MEMORY_COST (cap) = ALLOCNO_MEMORY_COST (a);
774 ira_allocate_and_copy_costs
775 (&ALLOCNO_HARD_REG_COSTS (cap), cover_class, ALLOCNO_HARD_REG_COSTS (a));
776 ira_allocate_and_copy_costs
777 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (cap), cover_class,
778 ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
779 ALLOCNO_BAD_SPILL_P (cap) = ALLOCNO_BAD_SPILL_P (a);
780 ALLOCNO_NREFS (cap) = ALLOCNO_NREFS (a);
781 ALLOCNO_FREQ (cap) = ALLOCNO_FREQ (a);
782 ALLOCNO_CALL_FREQ (cap) = ALLOCNO_CALL_FREQ (a);
783 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (cap),
784 ALLOCNO_CONFLICT_HARD_REGS (a));
785 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (cap),
786 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
787 ALLOCNO_CALLS_CROSSED_NUM (cap) = ALLOCNO_CALLS_CROSSED_NUM (a);
789 ALLOCNO_NO_STACK_REG_P (cap) = ALLOCNO_NO_STACK_REG_P (a);
790 ALLOCNO_TOTAL_NO_STACK_REG_P (cap) = ALLOCNO_TOTAL_NO_STACK_REG_P (a);
792 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
794 fprintf (ira_dump_file, " Creating cap ");
795 ira_print_expanded_allocno (cap);
796 fprintf (ira_dump_file, "\n");
801 /* Create and return allocno live range with given attributes. */
803 ira_create_allocno_live_range (ira_allocno_t a, int start, int finish,
804 allocno_live_range_t next)
806 allocno_live_range_t p;
808 p = (allocno_live_range_t) pool_alloc (allocno_live_range_pool);
816 /* Copy allocno live range R and return the result. */
817 static allocno_live_range_t
818 copy_allocno_live_range (allocno_live_range_t r)
820 allocno_live_range_t p;
822 p = (allocno_live_range_t) pool_alloc (allocno_live_range_pool);
827 /* Copy allocno live range list given by its head R and return the
830 ira_copy_allocno_live_range_list (allocno_live_range_t r)
832 allocno_live_range_t p, first, last;
836 for (first = last = NULL; r != NULL; r = r->next)
838 p = copy_allocno_live_range (r);
848 /* Merge ranges R1 and R2 and returns the result. The function
849 maintains the order of ranges and tries to minimize number of the
852 ira_merge_allocno_live_ranges (allocno_live_range_t r1,
853 allocno_live_range_t r2)
855 allocno_live_range_t first, last, temp;
861 for (first = last = NULL; r1 != NULL && r2 != NULL;)
863 if (r1->start < r2->start)
869 if (r1->start <= r2->finish + 1)
871 /* Intersected ranges: merge r1 and r2 into r1. */
872 r1->start = r2->start;
873 if (r1->finish < r2->finish)
874 r1->finish = r2->finish;
877 ira_finish_allocno_live_range (temp);
880 /* To try to merge with subsequent ranges in r1. */
887 /* Add r1 to the result. */
898 /* To try to merge with subsequent ranges in r2. */
910 ira_assert (r1->next == NULL);
918 ira_assert (r2->next == NULL);
922 ira_assert (last->next == NULL);
927 /* Return TRUE if live ranges R1 and R2 intersect. */
929 ira_allocno_live_ranges_intersect_p (allocno_live_range_t r1,
930 allocno_live_range_t r2)
932 /* Remember the live ranges are always kept ordered. */
933 while (r1 != NULL && r2 != NULL)
935 if (r1->start > r2->finish)
937 else if (r2->start > r1->finish)
945 /* Free allocno live range R. */
947 ira_finish_allocno_live_range (allocno_live_range_t r)
949 pool_free (allocno_live_range_pool, r);
952 /* Free list of allocno live ranges starting with R. */
954 ira_finish_allocno_live_range_list (allocno_live_range_t r)
956 allocno_live_range_t next_r;
958 for (; r != NULL; r = next_r)
961 ira_finish_allocno_live_range (r);
965 /* Free updated register costs of allocno A. */
967 ira_free_allocno_updated_costs (ira_allocno_t a)
969 enum reg_class cover_class;
971 cover_class = ALLOCNO_COVER_CLASS (a);
972 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL)
973 ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), cover_class);
974 ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
975 if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
976 ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
978 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
981 /* Free the memory allocated for allocno A. */
983 finish_allocno (ira_allocno_t a)
985 enum reg_class cover_class = ALLOCNO_COVER_CLASS (a);
987 ira_allocnos[ALLOCNO_NUM (a)] = NULL;
988 ira_conflict_id_allocno_map[ALLOCNO_CONFLICT_ID (a)] = NULL;
989 if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) != NULL)
990 ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a));
991 if (ALLOCNO_HARD_REG_COSTS (a) != NULL)
992 ira_free_cost_vector (ALLOCNO_HARD_REG_COSTS (a), cover_class);
993 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL)
994 ira_free_cost_vector (ALLOCNO_CONFLICT_HARD_REG_COSTS (a), cover_class);
995 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL)
996 ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), cover_class);
997 if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
998 ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
1000 ira_finish_allocno_live_range_list (ALLOCNO_LIVE_RANGES (a));
1001 pool_free (allocno_pool, a);
1004 /* Free the memory allocated for all allocnos. */
1006 finish_allocnos (void)
1009 ira_allocno_iterator ai;
1011 FOR_EACH_ALLOCNO (a, ai)
1013 ira_free (ira_regno_allocno_map);
1014 VEC_free (ira_allocno_t, heap, ira_conflict_id_allocno_map_vec);
1015 VEC_free (ira_allocno_t, heap, allocno_vec);
1016 free_alloc_pool (allocno_pool);
1017 free_alloc_pool (allocno_live_range_pool);
1022 /* Pools for copies. */
1023 static alloc_pool copy_pool;
1025 /* Vec containing references to all created copies. It is a
1026 container of array ira_copies. */
1027 static VEC(ira_copy_t,heap) *copy_vec;
1029 /* The function initializes data concerning allocno copies. */
1031 initiate_copies (void)
1034 = create_alloc_pool ("copies", sizeof (struct ira_allocno_copy), 100);
1035 copy_vec = VEC_alloc (ira_copy_t, heap, get_max_uid ());
1040 /* Return copy connecting A1 and A2 and originated from INSN of
1041 LOOP_TREE_NODE if any. */
1043 find_allocno_copy (ira_allocno_t a1, ira_allocno_t a2, rtx insn,
1044 ira_loop_tree_node_t loop_tree_node)
1046 ira_copy_t cp, next_cp;
1047 ira_allocno_t another_a;
1049 for (cp = ALLOCNO_COPIES (a1); cp != NULL; cp = next_cp)
1051 if (cp->first == a1)
1053 next_cp = cp->next_first_allocno_copy;
1054 another_a = cp->second;
1056 else if (cp->second == a1)
1058 next_cp = cp->next_second_allocno_copy;
1059 another_a = cp->first;
1063 if (another_a == a2 && cp->insn == insn
1064 && cp->loop_tree_node == loop_tree_node)
1070 /* Create and return copy with given attributes LOOP_TREE_NODE, FIRST,
1071 SECOND, FREQ, CONSTRAINT_P, and INSN. */
1073 ira_create_copy (ira_allocno_t first, ira_allocno_t second, int freq,
1074 bool constraint_p, rtx insn,
1075 ira_loop_tree_node_t loop_tree_node)
1079 cp = (ira_copy_t) pool_alloc (copy_pool);
1080 cp->num = ira_copies_num;
1082 cp->second = second;
1084 cp->constraint_p = constraint_p;
1086 cp->loop_tree_node = loop_tree_node;
1087 VEC_safe_push (ira_copy_t, heap, copy_vec, cp);
1088 ira_copies = VEC_address (ira_copy_t, copy_vec);
1089 ira_copies_num = VEC_length (ira_copy_t, copy_vec);
1093 /* Attach a copy CP to allocnos involved into the copy. */
1095 ira_add_allocno_copy_to_list (ira_copy_t cp)
1097 ira_allocno_t first = cp->first, second = cp->second;
1099 cp->prev_first_allocno_copy = NULL;
1100 cp->prev_second_allocno_copy = NULL;
1101 cp->next_first_allocno_copy = ALLOCNO_COPIES (first);
1102 if (cp->next_first_allocno_copy != NULL)
1104 if (cp->next_first_allocno_copy->first == first)
1105 cp->next_first_allocno_copy->prev_first_allocno_copy = cp;
1107 cp->next_first_allocno_copy->prev_second_allocno_copy = cp;
1109 cp->next_second_allocno_copy = ALLOCNO_COPIES (second);
1110 if (cp->next_second_allocno_copy != NULL)
1112 if (cp->next_second_allocno_copy->second == second)
1113 cp->next_second_allocno_copy->prev_second_allocno_copy = cp;
1115 cp->next_second_allocno_copy->prev_first_allocno_copy = cp;
1117 ALLOCNO_COPIES (first) = cp;
1118 ALLOCNO_COPIES (second) = cp;
1121 /* Detach a copy CP from allocnos involved into the copy. */
1123 ira_remove_allocno_copy_from_list (ira_copy_t cp)
1125 ira_allocno_t first = cp->first, second = cp->second;
1126 ira_copy_t prev, next;
1128 next = cp->next_first_allocno_copy;
1129 prev = cp->prev_first_allocno_copy;
1131 ALLOCNO_COPIES (first) = next;
1132 else if (prev->first == first)
1133 prev->next_first_allocno_copy = next;
1135 prev->next_second_allocno_copy = next;
1138 if (next->first == first)
1139 next->prev_first_allocno_copy = prev;
1141 next->prev_second_allocno_copy = prev;
1143 cp->prev_first_allocno_copy = cp->next_first_allocno_copy = NULL;
1145 next = cp->next_second_allocno_copy;
1146 prev = cp->prev_second_allocno_copy;
1148 ALLOCNO_COPIES (second) = next;
1149 else if (prev->second == second)
1150 prev->next_second_allocno_copy = next;
1152 prev->next_first_allocno_copy = next;
1155 if (next->second == second)
1156 next->prev_second_allocno_copy = prev;
1158 next->prev_first_allocno_copy = prev;
1160 cp->prev_second_allocno_copy = cp->next_second_allocno_copy = NULL;
1163 /* Make a copy CP a canonical copy where number of the
1164 first allocno is less than the second one. */
1166 ira_swap_allocno_copy_ends_if_necessary (ira_copy_t cp)
1171 if (ALLOCNO_NUM (cp->first) <= ALLOCNO_NUM (cp->second))
1175 cp->first = cp->second;
1178 temp_cp = cp->prev_first_allocno_copy;
1179 cp->prev_first_allocno_copy = cp->prev_second_allocno_copy;
1180 cp->prev_second_allocno_copy = temp_cp;
1182 temp_cp = cp->next_first_allocno_copy;
1183 cp->next_first_allocno_copy = cp->next_second_allocno_copy;
1184 cp->next_second_allocno_copy = temp_cp;
1187 /* Create (or update frequency if the copy already exists) and return
1188 the copy of allocnos FIRST and SECOND with frequency FREQ
1189 corresponding to move insn INSN (if any) and originated from
1192 ira_add_allocno_copy (ira_allocno_t first, ira_allocno_t second, int freq,
1193 bool constraint_p, rtx insn,
1194 ira_loop_tree_node_t loop_tree_node)
1198 if ((cp = find_allocno_copy (first, second, insn, loop_tree_node)) != NULL)
1203 cp = ira_create_copy (first, second, freq, constraint_p, insn,
1205 ira_assert (first != NULL && second != NULL);
1206 ira_add_allocno_copy_to_list (cp);
1207 ira_swap_allocno_copy_ends_if_necessary (cp);
1211 /* Print info about copy CP into file F. */
1213 print_copy (FILE *f, ira_copy_t cp)
1215 fprintf (f, " cp%d:a%d(r%d)<->a%d(r%d)@%d:%s\n", cp->num,
1216 ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
1217 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second), cp->freq,
1219 ? "move" : cp->constraint_p ? "constraint" : "shuffle");
1222 /* Print info about copy CP into stderr. */
1224 ira_debug_copy (ira_copy_t cp)
1226 print_copy (stderr, cp);
1229 /* Print info about all copies into file F. */
1231 print_copies (FILE *f)
1234 ira_copy_iterator ci;
1236 FOR_EACH_COPY (cp, ci)
1240 /* Print info about all copies into stderr. */
1242 ira_debug_copies (void)
1244 print_copies (stderr);
1247 /* Print info about copies involving allocno A into file F. */
1249 print_allocno_copies (FILE *f, ira_allocno_t a)
1251 ira_allocno_t another_a;
1252 ira_copy_t cp, next_cp;
1254 fprintf (f, " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
1255 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
1259 next_cp = cp->next_first_allocno_copy;
1260 another_a = cp->second;
1262 else if (cp->second == a)
1264 next_cp = cp->next_second_allocno_copy;
1265 another_a = cp->first;
1269 fprintf (f, " cp%d:a%d(r%d)@%d", cp->num,
1270 ALLOCNO_NUM (another_a), ALLOCNO_REGNO (another_a), cp->freq);
1275 /* Print info about copies involving allocno A into stderr. */
1277 ira_debug_allocno_copies (ira_allocno_t a)
1279 print_allocno_copies (stderr, a);
1282 /* The function frees memory allocated for copy CP. */
1284 finish_copy (ira_copy_t cp)
1286 pool_free (copy_pool, cp);
1290 /* Free memory allocated for all copies. */
1292 finish_copies (void)
1295 ira_copy_iterator ci;
1297 FOR_EACH_COPY (cp, ci)
1299 VEC_free (ira_copy_t, heap, copy_vec);
1300 free_alloc_pool (copy_pool);
1305 /* Pools for cost vectors. It is defined only for cover classes. */
1306 static alloc_pool cost_vector_pool[N_REG_CLASSES];
1308 /* The function initiates work with hard register cost vectors. It
1309 creates allocation pool for each cover class. */
1311 initiate_cost_vectors (void)
1314 enum reg_class cover_class;
1316 for (i = 0; i < ira_reg_class_cover_size; i++)
1318 cover_class = ira_reg_class_cover[i];
1319 cost_vector_pool[cover_class]
1320 = create_alloc_pool ("cost vectors",
1322 * ira_class_hard_regs_num[cover_class],
1327 /* Allocate and return a cost vector VEC for COVER_CLASS. */
1329 ira_allocate_cost_vector (enum reg_class cover_class)
1331 return (int *) pool_alloc (cost_vector_pool[cover_class]);
1334 /* Free a cost vector VEC for COVER_CLASS. */
1336 ira_free_cost_vector (int *vec, enum reg_class cover_class)
1338 ira_assert (vec != NULL);
1339 pool_free (cost_vector_pool[cover_class], vec);
1342 /* Finish work with hard register cost vectors. Release allocation
1343 pool for each cover class. */
1345 finish_cost_vectors (void)
1348 enum reg_class cover_class;
1350 for (i = 0; i < ira_reg_class_cover_size; i++)
1352 cover_class = ira_reg_class_cover[i];
1353 free_alloc_pool (cost_vector_pool[cover_class]);
1359 /* The current loop tree node and its regno allocno map. */
1360 ira_loop_tree_node_t ira_curr_loop_tree_node;
1361 ira_allocno_t *ira_curr_regno_allocno_map;
1363 /* This recursive function traverses loop tree with root LOOP_NODE
1364 calling non-null functions PREORDER_FUNC and POSTORDER_FUNC
1365 correspondingly in preorder and postorder. The function sets up
1366 IRA_CURR_LOOP_TREE_NODE and IRA_CURR_REGNO_ALLOCNO_MAP. If BB_P,
1367 basic block nodes of LOOP_NODE is also processed (before its
1370 ira_traverse_loop_tree (bool bb_p, ira_loop_tree_node_t loop_node,
1371 void (*preorder_func) (ira_loop_tree_node_t),
1372 void (*postorder_func) (ira_loop_tree_node_t))
1374 ira_loop_tree_node_t subloop_node;
1376 ira_assert (loop_node->bb == NULL);
1377 ira_curr_loop_tree_node = loop_node;
1378 ira_curr_regno_allocno_map = ira_curr_loop_tree_node->regno_allocno_map;
1380 if (preorder_func != NULL)
1381 (*preorder_func) (loop_node);
1384 for (subloop_node = loop_node->children;
1385 subloop_node != NULL;
1386 subloop_node = subloop_node->next)
1387 if (subloop_node->bb != NULL)
1389 if (preorder_func != NULL)
1390 (*preorder_func) (subloop_node);
1392 if (postorder_func != NULL)
1393 (*postorder_func) (subloop_node);
1396 for (subloop_node = loop_node->subloops;
1397 subloop_node != NULL;
1398 subloop_node = subloop_node->subloop_next)
1400 ira_assert (subloop_node->bb == NULL);
1401 ira_traverse_loop_tree (bb_p, subloop_node,
1402 preorder_func, postorder_func);
1405 ira_curr_loop_tree_node = loop_node;
1406 ira_curr_regno_allocno_map = ira_curr_loop_tree_node->regno_allocno_map;
1408 if (postorder_func != NULL)
1409 (*postorder_func) (loop_node);
1414 /* The basic block currently being processed. */
1415 static basic_block curr_bb;
1417 /* This recursive function creates allocnos corresponding to
1418 pseudo-registers containing in X. True OUTPUT_P means that X is
1421 create_insn_allocnos (rtx x, bool output_p)
1425 enum rtx_code code = GET_CODE (x);
1431 if ((regno = REGNO (x)) >= FIRST_PSEUDO_REGISTER)
1435 if ((a = ira_curr_regno_allocno_map[regno]) == NULL)
1436 a = ira_create_allocno (regno, false, ira_curr_loop_tree_node);
1438 ALLOCNO_NREFS (a)++;
1439 ALLOCNO_FREQ (a) += REG_FREQ_FROM_BB (curr_bb);
1441 bitmap_set_bit (ira_curr_loop_tree_node->modified_regnos, regno);
1445 else if (code == SET)
1447 create_insn_allocnos (SET_DEST (x), true);
1448 create_insn_allocnos (SET_SRC (x), false);
1451 else if (code == CLOBBER)
1453 create_insn_allocnos (XEXP (x, 0), true);
1456 else if (code == MEM)
1458 create_insn_allocnos (XEXP (x, 0), false);
1461 else if (code == PRE_DEC || code == POST_DEC || code == PRE_INC ||
1462 code == POST_INC || code == POST_MODIFY || code == PRE_MODIFY)
1464 create_insn_allocnos (XEXP (x, 0), true);
1465 create_insn_allocnos (XEXP (x, 0), false);
1469 fmt = GET_RTX_FORMAT (code);
1470 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1473 create_insn_allocnos (XEXP (x, i), output_p);
1474 else if (fmt[i] == 'E')
1475 for (j = 0; j < XVECLEN (x, i); j++)
1476 create_insn_allocnos (XVECEXP (x, i, j), output_p);
1480 /* Create allocnos corresponding to pseudo-registers living in the
1481 basic block represented by the corresponding loop tree node
1484 create_bb_allocnos (ira_loop_tree_node_t bb_node)
1491 curr_bb = bb = bb_node->bb;
1492 ira_assert (bb != NULL);
1493 FOR_BB_INSNS_REVERSE (bb, insn)
1495 create_insn_allocnos (PATTERN (insn), false);
1496 /* It might be a allocno living through from one subloop to
1498 EXECUTE_IF_SET_IN_REG_SET (DF_LR_IN (bb), FIRST_PSEUDO_REGISTER, i, bi)
1499 if (ira_curr_regno_allocno_map[i] == NULL)
1500 ira_create_allocno (i, false, ira_curr_loop_tree_node);
1503 /* Create allocnos corresponding to pseudo-registers living on edge E
1504 (a loop entry or exit). Also mark the allocnos as living on the
1507 create_loop_allocnos (edge e)
1510 bitmap live_in_regs, border_allocnos;
1512 ira_loop_tree_node_t parent;
1514 live_in_regs = DF_LR_IN (e->dest);
1515 border_allocnos = ira_curr_loop_tree_node->border_allocnos;
1516 EXECUTE_IF_SET_IN_REG_SET (DF_LR_OUT (e->src),
1517 FIRST_PSEUDO_REGISTER, i, bi)
1518 if (bitmap_bit_p (live_in_regs, i))
1520 if (ira_curr_regno_allocno_map[i] == NULL)
1522 /* The order of creations is important for right
1523 ira_regno_allocno_map. */
1524 if ((parent = ira_curr_loop_tree_node->parent) != NULL
1525 && parent->regno_allocno_map[i] == NULL)
1526 ira_create_allocno (i, false, parent);
1527 ira_create_allocno (i, false, ira_curr_loop_tree_node);
1529 bitmap_set_bit (border_allocnos,
1530 ALLOCNO_NUM (ira_curr_regno_allocno_map[i]));
1534 /* Create allocnos corresponding to pseudo-registers living in loop
1535 represented by the corresponding loop tree node LOOP_NODE. This
1536 function is called by ira_traverse_loop_tree. */
1538 create_loop_tree_node_allocnos (ira_loop_tree_node_t loop_node)
1540 if (loop_node->bb != NULL)
1541 create_bb_allocnos (loop_node);
1542 else if (loop_node != ira_loop_tree_root)
1547 VEC (edge, heap) *edges;
1549 FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
1550 if (e->src != loop_node->loop->latch)
1551 create_loop_allocnos (e);
1553 edges = get_loop_exit_edges (loop_node->loop);
1554 for (i = 0; VEC_iterate (edge, edges, i, e); i++)
1555 create_loop_allocnos (e);
1556 VEC_free (edge, heap, edges);
1560 /* Propagate information about allocnos modified inside the loop given
1561 by its LOOP_TREE_NODE to its parent. */
1563 propagate_modified_regnos (ira_loop_tree_node_t loop_tree_node)
1565 if (loop_tree_node == ira_loop_tree_root)
1567 ira_assert (loop_tree_node->bb == NULL);
1568 bitmap_ior_into (loop_tree_node->parent->modified_regnos,
1569 loop_tree_node->modified_regnos);
1572 /* Propagate new info about allocno A (see comments about accumulated
1573 info in allocno definition) to the corresponding allocno on upper
1574 loop tree level. So allocnos on upper levels accumulate
1575 information about the corresponding allocnos in nested regions.
1576 The new info means allocno info finally calculated in this
1579 propagate_allocno_info (void)
1582 ira_allocno_t a, parent_a;
1583 ira_loop_tree_node_t parent;
1584 enum reg_class cover_class;
1586 if (flag_ira_region != IRA_REGION_ALL
1587 && flag_ira_region != IRA_REGION_MIXED)
1589 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1590 for (a = ira_regno_allocno_map[i];
1592 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1593 if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL
1594 && (parent_a = parent->regno_allocno_map[i]) != NULL
1595 /* There are no caps yet at this point. So use
1596 border_allocnos to find allocnos for the propagation. */
1597 && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE (a)->border_allocnos,
1600 if (! ALLOCNO_BAD_SPILL_P (a))
1601 ALLOCNO_BAD_SPILL_P (parent_a) = false;
1602 ALLOCNO_NREFS (parent_a) += ALLOCNO_NREFS (a);
1603 ALLOCNO_FREQ (parent_a) += ALLOCNO_FREQ (a);
1604 ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
1606 if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
1607 ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a) = true;
1609 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a),
1610 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1611 ALLOCNO_CALLS_CROSSED_NUM (parent_a)
1612 += ALLOCNO_CALLS_CROSSED_NUM (a);
1613 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
1614 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
1615 cover_class = ALLOCNO_COVER_CLASS (a);
1616 ira_assert (cover_class == ALLOCNO_COVER_CLASS (parent_a));
1617 ira_allocate_and_accumulate_costs
1618 (&ALLOCNO_HARD_REG_COSTS (parent_a), cover_class,
1619 ALLOCNO_HARD_REG_COSTS (a));
1620 ira_allocate_and_accumulate_costs
1621 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a),
1623 ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
1624 ALLOCNO_COVER_CLASS_COST (parent_a)
1625 += ALLOCNO_COVER_CLASS_COST (a);
1626 ALLOCNO_MEMORY_COST (parent_a) += ALLOCNO_MEMORY_COST (a);
1630 /* Create allocnos corresponding to pseudo-registers in the current
1631 function. Traverse the loop tree for this. */
1633 create_allocnos (void)
1635 /* We need to process BB first to correctly link allocnos by member
1636 next_regno_allocno. */
1637 ira_traverse_loop_tree (true, ira_loop_tree_root,
1638 create_loop_tree_node_allocnos, NULL);
1640 ira_traverse_loop_tree (false, ira_loop_tree_root, NULL,
1641 propagate_modified_regnos);
1646 /* The page contains function to remove some regions from a separate
1647 register allocation. We remove regions whose separate allocation
1648 will hardly improve the result. As a result we speed up regional
1649 register allocation. */
1651 /* The function changes allocno in range list given by R onto A. */
1653 change_allocno_in_range_list (allocno_live_range_t r, ira_allocno_t a)
1655 for (; r != NULL; r = r->next)
1659 /* Return TRUE if NODE represents a loop with low register
1662 low_pressure_loop_node_p (ira_loop_tree_node_t node)
1665 enum reg_class cover_class;
1667 if (node->bb != NULL)
1670 for (i = 0; i < ira_reg_class_cover_size; i++)
1672 cover_class = ira_reg_class_cover[i];
1673 if (node->reg_pressure[cover_class]
1674 > ira_available_class_regs[cover_class])
1680 /* Sort loops for marking them for removal. We put already marked
1681 loops first, then less frequent loops next, and then outer loops
1684 loop_compare_func (const void *v1p, const void *v2p)
1687 ira_loop_tree_node_t l1 = *(const ira_loop_tree_node_t *) v1p;
1688 ira_loop_tree_node_t l2 = *(const ira_loop_tree_node_t *) v2p;
1690 ira_assert (l1->parent != NULL && l2->parent != NULL);
1691 if (l1->to_remove_p && ! l2->to_remove_p)
1693 if (! l1->to_remove_p && l2->to_remove_p)
1695 if ((diff = l1->loop->header->frequency - l2->loop->header->frequency) != 0)
1697 if ((diff = (int) loop_depth (l1->loop) - (int) loop_depth (l2->loop)) != 0)
1699 /* Make sorting stable. */
1700 return l1->loop->num - l2->loop->num;
1704 /* Mark loops which should be removed from regional allocation. We
1705 remove a loop with low register pressure inside another loop with
1706 register pressure. In this case a separate allocation of the loop
1707 hardly helps (for irregular register file architecture it could
1708 help by choosing a better hard register in the loop but we prefer
1709 faster allocation even in this case). We also remove cheap loops
1710 if there are more than IRA_MAX_LOOPS_NUM of them. */
1712 mark_loops_for_removal (void)
1715 ira_loop_tree_node_t *sorted_loops;
1719 = (ira_loop_tree_node_t *) ira_allocate (sizeof (ira_loop_tree_node_t)
1720 * VEC_length (loop_p,
1722 for (n = i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
1723 if (ira_loop_nodes[i].regno_allocno_map != NULL)
1725 if (ira_loop_nodes[i].parent == NULL)
1727 /* Don't remove the root. */
1728 ira_loop_nodes[i].to_remove_p = false;
1731 sorted_loops[n++] = &ira_loop_nodes[i];
1732 ira_loop_nodes[i].to_remove_p
1733 = (low_pressure_loop_node_p (ira_loop_nodes[i].parent)
1734 && low_pressure_loop_node_p (&ira_loop_nodes[i]));
1736 qsort (sorted_loops, n, sizeof (ira_loop_tree_node_t), loop_compare_func);
1737 for (i = 0; n - i + 1 > IRA_MAX_LOOPS_NUM; i++)
1739 sorted_loops[i]->to_remove_p = true;
1740 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1743 " Mark loop %d (header %d, freq %d, depth %d) for removal (%s)\n",
1744 sorted_loops[i]->loop->num, sorted_loops[i]->loop->header->index,
1745 sorted_loops[i]->loop->header->frequency,
1746 loop_depth (sorted_loops[i]->loop),
1747 low_pressure_loop_node_p (sorted_loops[i]->parent)
1748 && low_pressure_loop_node_p (sorted_loops[i])
1749 ? "low pressure" : "cheap loop");
1751 ira_free (sorted_loops);
1755 /* Definition of vector of loop tree nodes. */
1756 DEF_VEC_P(ira_loop_tree_node_t);
1757 DEF_VEC_ALLOC_P(ira_loop_tree_node_t, heap);
1759 /* Vec containing references to all removed loop tree nodes. */
1760 static VEC(ira_loop_tree_node_t,heap) *removed_loop_vec;
1762 /* Vec containing references to all children of loop tree nodes. */
1763 static VEC(ira_loop_tree_node_t,heap) *children_vec;
1765 /* Remove subregions of NODE if their separate allocation will not
1766 improve the result. */
1768 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_node_t node)
1772 ira_loop_tree_node_t subnode;
1774 remove_p = node->to_remove_p;
1776 VEC_safe_push (ira_loop_tree_node_t, heap, children_vec, node);
1777 start = VEC_length (ira_loop_tree_node_t, children_vec);
1778 for (subnode = node->children; subnode != NULL; subnode = subnode->next)
1779 if (subnode->bb == NULL)
1780 remove_uneccesary_loop_nodes_from_loop_tree (subnode);
1782 VEC_safe_push (ira_loop_tree_node_t, heap, children_vec, subnode);
1783 node->children = node->subloops = NULL;
1786 VEC_safe_push (ira_loop_tree_node_t, heap, removed_loop_vec, node);
1789 while (VEC_length (ira_loop_tree_node_t, children_vec) > start)
1791 subnode = VEC_pop (ira_loop_tree_node_t, children_vec);
1792 subnode->parent = node;
1793 subnode->next = node->children;
1794 node->children = subnode;
1795 if (subnode->bb == NULL)
1797 subnode->subloop_next = node->subloops;
1798 node->subloops = subnode;
1803 /* Return TRUE if NODE is inside PARENT. */
1805 loop_is_inside_p (ira_loop_tree_node_t node, ira_loop_tree_node_t parent)
1807 for (node = node->parent; node != NULL; node = node->parent)
1813 /* Sort allocnos according to their order in regno allocno list. */
1815 regno_allocno_order_compare_func (const void *v1p, const void *v2p)
1817 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
1818 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
1819 ira_loop_tree_node_t n1 = ALLOCNO_LOOP_TREE_NODE (a1);
1820 ira_loop_tree_node_t n2 = ALLOCNO_LOOP_TREE_NODE (a2);
1822 if (loop_is_inside_p (n1, n2))
1824 else if (loop_is_inside_p (n2, n1))
1826 /* If allocnos are equally good, sort by allocno numbers, so that
1827 the results of qsort leave nothing to chance. We put allocnos
1828 with higher number first in the list because it is the original
1829 order for allocnos from loops on the same levels. */
1830 return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
1833 /* This array is used to sort allocnos to restore allocno order in
1834 the regno allocno list. */
1835 static ira_allocno_t *regno_allocnos;
1837 /* Restore allocno order for REGNO in the regno allocno list. */
1839 ira_rebuild_regno_allocno_list (int regno)
1844 for (n = 0, a = ira_regno_allocno_map[regno];
1846 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1847 regno_allocnos[n++] = a;
1849 qsort (regno_allocnos, n, sizeof (ira_allocno_t),
1850 regno_allocno_order_compare_func);
1851 for (i = 1; i < n; i++)
1852 ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[i - 1]) = regno_allocnos[i];
1853 ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[n - 1]) = NULL;
1854 ira_regno_allocno_map[regno] = regno_allocnos[0];
1855 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1856 fprintf (ira_dump_file, " Rebuilding regno allocno list for %d\n", regno);
1859 /* Remove allocnos from loops removed from the allocation
1862 remove_unnecessary_allocnos (void)
1865 bool merged_p, rebuild_p;
1866 enum reg_class cover_class;
1867 ira_allocno_t a, prev_a, next_a, parent_a;
1868 ira_loop_tree_node_t a_node, parent;
1869 allocno_live_range_t r;
1872 regno_allocnos = NULL;
1873 for (regno = max_reg_num () - 1; regno >= FIRST_PSEUDO_REGISTER; regno--)
1876 for (prev_a = NULL, a = ira_regno_allocno_map[regno];
1880 next_a = ALLOCNO_NEXT_REGNO_ALLOCNO (a);
1881 a_node = ALLOCNO_LOOP_TREE_NODE (a);
1882 if (! a_node->to_remove_p)
1886 for (parent = a_node->parent;
1887 (parent_a = parent->regno_allocno_map[regno]) == NULL
1888 && parent->to_remove_p;
1889 parent = parent->parent)
1891 if (parent_a == NULL)
1893 /* There are no allocnos with the same regno in upper
1894 region -- just move the allocno to the upper
1897 ALLOCNO_LOOP_TREE_NODE (a) = parent;
1898 parent->regno_allocno_map[regno] = a;
1899 bitmap_set_bit (parent->all_allocnos, ALLOCNO_NUM (a));
1904 /* Remove the allocno and update info of allocno in
1905 the upper region. */
1907 ira_regno_allocno_map[regno] = next_a;
1909 ALLOCNO_NEXT_REGNO_ALLOCNO (prev_a) = next_a;
1910 r = ALLOCNO_LIVE_RANGES (a);
1911 change_allocno_in_range_list (r, parent_a);
1912 ALLOCNO_LIVE_RANGES (parent_a)
1913 = ira_merge_allocno_live_ranges
1914 (r, ALLOCNO_LIVE_RANGES (parent_a));
1916 ALLOCNO_LIVE_RANGES (a) = NULL;
1917 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (parent_a),
1918 ALLOCNO_CONFLICT_HARD_REGS (a));
1920 if (ALLOCNO_NO_STACK_REG_P (a))
1921 ALLOCNO_NO_STACK_REG_P (parent_a) = true;
1923 ALLOCNO_NREFS (parent_a) += ALLOCNO_NREFS (a);
1924 ALLOCNO_FREQ (parent_a) += ALLOCNO_FREQ (a);
1925 ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
1927 (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a),
1928 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1929 ALLOCNO_CALLS_CROSSED_NUM (parent_a)
1930 += ALLOCNO_CALLS_CROSSED_NUM (a);
1931 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
1932 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
1933 if (! ALLOCNO_BAD_SPILL_P (a))
1934 ALLOCNO_BAD_SPILL_P (parent_a) = false;
1936 if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
1937 ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a) = true;
1939 cover_class = ALLOCNO_COVER_CLASS (a);
1940 ira_assert (cover_class == ALLOCNO_COVER_CLASS (parent_a));
1941 ira_allocate_and_accumulate_costs
1942 (&ALLOCNO_HARD_REG_COSTS (parent_a), cover_class,
1943 ALLOCNO_HARD_REG_COSTS (a));
1944 ira_allocate_and_accumulate_costs
1945 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a),
1947 ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
1948 ALLOCNO_COVER_CLASS_COST (parent_a)
1949 += ALLOCNO_COVER_CLASS_COST (a);
1950 ALLOCNO_MEMORY_COST (parent_a) += ALLOCNO_MEMORY_COST (a);
1956 /* We need to restore the order in regno allocno list. */
1958 if (regno_allocnos == NULL)
1960 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
1961 * ira_allocnos_num);
1962 ira_rebuild_regno_allocno_list (regno);
1966 ira_rebuild_start_finish_chains ();
1967 if (regno_allocnos != NULL)
1968 ira_free (regno_allocnos);
1971 /* Remove loops from consideration. We remove loops for which a
1972 separate allocation will not improve the result. We have to do
1973 this after allocno creation and their costs and cover class
1974 evaluation because only after that the register pressure can be
1975 known and is calculated. */
1977 remove_unnecessary_regions (void)
1979 mark_loops_for_removal ();
1981 = VEC_alloc (ira_loop_tree_node_t, heap,
1982 last_basic_block + VEC_length (loop_p, ira_loops.larray));
1984 = VEC_alloc (ira_loop_tree_node_t, heap,
1985 last_basic_block + VEC_length (loop_p, ira_loops.larray));
1986 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_root) ;
1987 VEC_free (ira_loop_tree_node_t, heap, children_vec);
1988 remove_unnecessary_allocnos ();
1989 while (VEC_length (ira_loop_tree_node_t, removed_loop_vec) > 0)
1990 finish_loop_tree_node (VEC_pop (ira_loop_tree_node_t, removed_loop_vec));
1991 VEC_free (ira_loop_tree_node_t, heap, removed_loop_vec);
1996 /* At this point true value of allocno attribute bad_spill_p means
1997 that there is an insn where allocno occurs and where the allocno
1998 can not be used as memory. The function updates the attribute, now
1999 it can be true only for allocnos which can not be used as memory in
2000 an insn and in whose live ranges there is other allocno deaths.
2001 Spilling allocnos with true value will not improve the code because
2002 it will not make other allocnos colorable and additional reloads
2003 for the corresponding pseudo will be generated in reload pass for
2004 each insn it occurs.
2006 This is a trick mentioned in one classic article of Chaitin etc
2007 which is frequently omitted in other implementations of RA based on
2010 update_bad_spill_attribute (void)
2014 ira_allocno_iterator ai;
2015 allocno_live_range_t r;
2016 enum reg_class cover_class;
2017 bitmap_head dead_points[N_REG_CLASSES];
2019 for (i = 0; i < ira_reg_class_cover_size; i++)
2021 cover_class = ira_reg_class_cover[i];
2022 bitmap_initialize (&dead_points[cover_class], ®_obstack);
2024 FOR_EACH_ALLOCNO (a, ai)
2026 cover_class = ALLOCNO_COVER_CLASS (a);
2027 if (cover_class == NO_REGS)
2029 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
2030 bitmap_set_bit (&dead_points[cover_class], r->finish);
2032 FOR_EACH_ALLOCNO (a, ai)
2034 cover_class = ALLOCNO_COVER_CLASS (a);
2035 if (cover_class == NO_REGS)
2037 if (! ALLOCNO_BAD_SPILL_P (a))
2039 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
2041 for (i = r->start + 1; i < r->finish; i++)
2042 if (bitmap_bit_p (&dead_points[cover_class], i))
2048 ALLOCNO_BAD_SPILL_P (a) = false;
2050 for (i = 0; i < ira_reg_class_cover_size; i++)
2052 cover_class = ira_reg_class_cover[i];
2053 bitmap_clear (&dead_points[cover_class]);
2059 /* Set up minimal and maximal live range points for allocnos. */
2061 setup_min_max_allocno_live_range_point (void)
2064 ira_allocno_t a, parent_a, cap;
2065 ira_allocno_iterator ai;
2066 allocno_live_range_t r;
2067 ira_loop_tree_node_t parent;
2069 FOR_EACH_ALLOCNO (a, ai)
2071 r = ALLOCNO_LIVE_RANGES (a);
2074 ALLOCNO_MAX (a) = r->finish;
2075 for (; r->next != NULL; r = r->next)
2077 ALLOCNO_MIN (a) = r->start;
2079 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
2080 for (a = ira_regno_allocno_map[i];
2082 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2084 if (ALLOCNO_MAX (a) < 0)
2086 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2087 /* Accumulation of range info. */
2088 if (ALLOCNO_CAP (a) != NULL)
2090 for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
2092 if (ALLOCNO_MAX (cap) < ALLOCNO_MAX (a))
2093 ALLOCNO_MAX (cap) = ALLOCNO_MAX (a);
2094 if (ALLOCNO_MIN (cap) > ALLOCNO_MIN (a))
2095 ALLOCNO_MIN (cap) = ALLOCNO_MIN (a);
2099 if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL)
2101 parent_a = parent->regno_allocno_map[i];
2102 if (ALLOCNO_MAX (parent_a) < ALLOCNO_MAX (a))
2103 ALLOCNO_MAX (parent_a) = ALLOCNO_MAX (a);
2104 if (ALLOCNO_MIN (parent_a) > ALLOCNO_MIN (a))
2105 ALLOCNO_MIN (parent_a) = ALLOCNO_MIN (a);
2107 #ifdef ENABLE_IRA_CHECKING
2108 FOR_EACH_ALLOCNO (a, ai)
2110 if ((0 <= ALLOCNO_MIN (a) && ALLOCNO_MIN (a) <= ira_max_point)
2111 && (0 <= ALLOCNO_MAX (a) && ALLOCNO_MAX (a) <= ira_max_point))
2118 /* Sort allocnos according to their live ranges. Allocnos with
2119 smaller cover class are put first unless we use priority coloring.
2120 Allocnos with the same cove class are ordered according their start
2121 (min). Allocnos with the same start are ordered according their
2124 allocno_range_compare_func (const void *v1p, const void *v2p)
2127 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2128 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2130 if (flag_ira_algorithm != IRA_ALGORITHM_PRIORITY
2131 && (diff = ALLOCNO_COVER_CLASS (a1) - ALLOCNO_COVER_CLASS (a2)) != 0)
2133 if ((diff = ALLOCNO_MIN (a1) - ALLOCNO_MIN (a2)) != 0)
2135 if ((diff = ALLOCNO_MAX (a1) - ALLOCNO_MAX (a2)) != 0)
2137 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2140 /* Sort ira_conflict_id_allocno_map and set up conflict id of
2143 sort_conflict_id_allocno_map (void)
2147 ira_allocno_iterator ai;
2150 FOR_EACH_ALLOCNO (a, ai)
2151 ira_conflict_id_allocno_map[num++] = a;
2152 qsort (ira_conflict_id_allocno_map, num, sizeof (ira_allocno_t),
2153 allocno_range_compare_func);
2154 for (i = 0; i < num; i++)
2155 if ((a = ira_conflict_id_allocno_map[i]) != NULL)
2156 ALLOCNO_CONFLICT_ID (a) = i;
2157 for (i = num; i < ira_allocnos_num; i++)
2158 ira_conflict_id_allocno_map[i] = NULL;
2161 /* Set up minimal and maximal conflict ids of allocnos with which
2162 given allocno can conflict. */
2164 setup_min_max_conflict_allocno_ids (void)
2167 int i, j, min, max, start, finish, first_not_finished, filled_area_start;
2168 int *live_range_min, *last_lived;
2171 live_range_min = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
2173 first_not_finished = -1;
2174 for (i = 0; i < ira_allocnos_num; i++)
2176 a = ira_conflict_id_allocno_map[i];
2180 || (flag_ira_algorithm != IRA_ALGORITHM_PRIORITY
2181 && cover_class != (int) ALLOCNO_COVER_CLASS (a)))
2183 cover_class = ALLOCNO_COVER_CLASS (a);
2185 first_not_finished = i;
2189 start = ALLOCNO_MIN (a);
2190 /* If we skip an allocno, the allocno with smaller ids will
2191 be also skipped because of the secondary sorting the
2192 range finishes (see function
2193 allocno_range_compare_func). */
2194 while (first_not_finished < i
2195 && start > ALLOCNO_MAX (ira_conflict_id_allocno_map
2196 [first_not_finished]))
2197 first_not_finished++;
2198 min = first_not_finished;
2201 /* We could increase min further in this case but it is good
2204 live_range_min[i] = ALLOCNO_MIN (a);
2205 ALLOCNO_MIN (a) = min;
2207 last_lived = (int *) ira_allocate (sizeof (int) * ira_max_point);
2209 filled_area_start = -1;
2210 for (i = ira_allocnos_num - 1; i >= 0; i--)
2212 a = ira_conflict_id_allocno_map[i];
2216 || (flag_ira_algorithm != IRA_ALGORITHM_PRIORITY
2217 && cover_class != (int) ALLOCNO_COVER_CLASS (a)))
2219 cover_class = ALLOCNO_COVER_CLASS (a);
2220 for (j = 0; j < ira_max_point; j++)
2222 filled_area_start = ira_max_point;
2224 min = live_range_min[i];
2225 finish = ALLOCNO_MAX (a);
2226 max = last_lived[finish];
2228 /* We could decrease max further in this case but it is good
2230 max = ALLOCNO_CONFLICT_ID (a) - 1;
2231 ALLOCNO_MAX (a) = max;
2232 /* In filling, we can go further A range finish to recognize
2233 intersection quickly because if the finish of subsequently
2234 processed allocno (it has smaller conflict id) range is
2235 further A range finish than they are definitely intersected
2236 (the reason for this is the allocnos with bigger conflict id
2237 have their range starts not smaller than allocnos with
2239 for (j = min; j < filled_area_start; j++)
2241 filled_area_start = min;
2243 ira_free (last_lived);
2244 ira_free (live_range_min);
2253 ira_allocno_iterator ai;
2254 ira_loop_tree_node_t loop_tree_node;
2256 FOR_EACH_ALLOCNO (a, ai)
2258 if (ALLOCNO_LOOP_TREE_NODE (a) == ira_loop_tree_root)
2260 if (ALLOCNO_CAP_MEMBER (a) != NULL)
2261 create_cap_allocno (a);
2262 else if (ALLOCNO_CAP (a) == NULL)
2264 loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
2265 if (!bitmap_bit_p (loop_tree_node->border_allocnos, ALLOCNO_NUM (a)))
2266 create_cap_allocno (a);
2273 /* The page contains code transforming more one region internal
2274 representation (IR) to one region IR which is necessary for reload.
2275 This transformation is called IR flattening. We might just rebuild
2276 the IR for one region but we don't do it because it takes a lot of
2279 /* Map: regno -> allocnos which will finally represent the regno for
2280 IR with one region. */
2281 static ira_allocno_t *regno_top_level_allocno_map;
2283 /* Process all allocnos originated from pseudo REGNO and copy live
2284 ranges, hard reg conflicts, and allocno stack reg attributes from
2285 low level allocnos to final allocnos which are destinations of
2286 removed stores at a loop exit. Return true if we copied live
2289 copy_info_to_removed_store_destinations (int regno)
2291 ira_allocno_t a, parent_a;
2292 ira_loop_tree_node_t parent;
2293 allocno_live_range_t r;
2297 for (a = ira_regno_allocno_map[regno];
2299 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2301 if (a != regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))])
2302 /* This allocno will be removed. */
2304 /* Caps will be removed. */
2305 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2306 for (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
2308 parent = parent->parent)
2309 if ((parent_a = parent->regno_allocno_map[regno]) == NULL
2310 || (parent_a == regno_top_level_allocno_map[REGNO (ALLOCNO_REG
2312 && ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a)))
2314 if (parent == NULL || parent_a == NULL)
2316 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2320 " Coping ranges of a%dr%d to a%dr%d: ",
2321 ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)),
2322 ALLOCNO_NUM (parent_a), REGNO (ALLOCNO_REG (parent_a)));
2323 ira_print_live_range_list (ira_dump_file,
2324 ALLOCNO_LIVE_RANGES (a));
2326 r = ira_copy_allocno_live_range_list (ALLOCNO_LIVE_RANGES (a));
2327 change_allocno_in_range_list (r, parent_a);
2328 ALLOCNO_LIVE_RANGES (parent_a)
2329 = ira_merge_allocno_live_ranges (r, ALLOCNO_LIVE_RANGES (parent_a));
2330 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a),
2331 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
2333 if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
2334 ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a) = true;
2336 ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
2337 ALLOCNO_CALLS_CROSSED_NUM (parent_a)
2338 += ALLOCNO_CALLS_CROSSED_NUM (a);
2339 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
2340 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2346 /* Flatten the IR. In other words, this function transforms IR as if
2347 it were built with one region (without loops). We could make it
2348 much simpler by rebuilding IR with one region, but unfortunately it
2349 takes a lot of time. MAX_REGNO_BEFORE_EMIT and
2350 IRA_MAX_POINT_BEFORE_EMIT are correspondingly MAX_REG_NUM () and
2351 IRA_MAX_POINT before emitting insns on the loop borders. */
2353 ira_flattening (int max_regno_before_emit, int ira_max_point_before_emit)
2358 bool new_pseudos_p, merged_p, mem_dest_p;
2360 enum reg_class cover_class;
2361 ira_allocno_t a, parent_a, first, second, node_first, node_second;
2363 ira_loop_tree_node_t parent, node;
2364 allocno_live_range_t r;
2365 ira_allocno_iterator ai;
2366 ira_copy_iterator ci;
2367 sparseset allocnos_live;
2369 regno_top_level_allocno_map
2370 = (ira_allocno_t *) ira_allocate (max_reg_num () * sizeof (ira_allocno_t));
2371 memset (regno_top_level_allocno_map, 0,
2372 max_reg_num () * sizeof (ira_allocno_t));
2373 new_pseudos_p = merged_p = false;
2374 FOR_EACH_ALLOCNO (a, ai)
2376 if (ALLOCNO_CAP_MEMBER (a) != NULL)
2377 /* Caps are not in the regno allocno maps and they are never
2378 will be transformed into allocnos existing after IR
2381 COPY_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
2382 ALLOCNO_CONFLICT_HARD_REGS (a));
2384 ALLOCNO_TOTAL_NO_STACK_REG_P (a) = ALLOCNO_NO_STACK_REG_P (a);
2387 /* Fix final allocno attributes. */
2388 for (i = max_regno_before_emit - 1; i >= FIRST_PSEUDO_REGISTER; i--)
2391 for (a = ira_regno_allocno_map[i];
2393 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2395 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2396 if (ALLOCNO_SOMEWHERE_RENAMED_P (a))
2397 new_pseudos_p = true;
2398 if (ALLOCNO_CAP (a) != NULL
2399 || (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
2400 || ((parent_a = parent->regno_allocno_map[ALLOCNO_REGNO (a)])
2403 ALLOCNO_COPIES (a) = NULL;
2404 regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))] = a;
2407 ira_assert (ALLOCNO_CAP_MEMBER (parent_a) == NULL);
2409 if (ALLOCNO_MEM_OPTIMIZED_DEST (a) != NULL)
2411 if (REGNO (ALLOCNO_REG (a)) == REGNO (ALLOCNO_REG (parent_a)))
2413 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a),
2414 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
2416 if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
2417 ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a) = true;
2419 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2421 fprintf (ira_dump_file,
2422 " Moving ranges of a%dr%d to a%dr%d: ",
2423 ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)),
2424 ALLOCNO_NUM (parent_a),
2425 REGNO (ALLOCNO_REG (parent_a)));
2426 ira_print_live_range_list (ira_dump_file,
2427 ALLOCNO_LIVE_RANGES (a));
2429 change_allocno_in_range_list (ALLOCNO_LIVE_RANGES (a), parent_a);
2430 ALLOCNO_LIVE_RANGES (parent_a)
2431 = ira_merge_allocno_live_ranges
2432 (ALLOCNO_LIVE_RANGES (a), ALLOCNO_LIVE_RANGES (parent_a));
2434 ALLOCNO_LIVE_RANGES (a) = NULL;
2435 ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a)
2436 = (ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a)
2437 || ALLOCNO_MEM_OPTIMIZED_DEST_P (a));
2440 new_pseudos_p = true;
2443 ALLOCNO_NREFS (parent_a) -= ALLOCNO_NREFS (a);
2444 ALLOCNO_FREQ (parent_a) -= ALLOCNO_FREQ (a);
2445 ALLOCNO_CALL_FREQ (parent_a) -= ALLOCNO_CALL_FREQ (a);
2446 ALLOCNO_CALLS_CROSSED_NUM (parent_a)
2447 -= ALLOCNO_CALLS_CROSSED_NUM (a);
2448 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
2449 -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2450 ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a) >= 0
2451 && ALLOCNO_NREFS (parent_a) >= 0
2452 && ALLOCNO_FREQ (parent_a) >= 0);
2453 cover_class = ALLOCNO_COVER_CLASS (parent_a);
2454 hard_regs_num = ira_class_hard_regs_num[cover_class];
2455 if (ALLOCNO_HARD_REG_COSTS (a) != NULL
2456 && ALLOCNO_HARD_REG_COSTS (parent_a) != NULL)
2457 for (j = 0; j < hard_regs_num; j++)
2458 ALLOCNO_HARD_REG_COSTS (parent_a)[j]
2459 -= ALLOCNO_HARD_REG_COSTS (a)[j];
2460 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL
2461 && ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a) != NULL)
2462 for (j = 0; j < hard_regs_num; j++)
2463 ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a)[j]
2464 -= ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[j];
2465 ALLOCNO_COVER_CLASS_COST (parent_a)
2466 -= ALLOCNO_COVER_CLASS_COST (a);
2467 ALLOCNO_MEMORY_COST (parent_a) -= ALLOCNO_MEMORY_COST (a);
2468 if (ALLOCNO_CAP (parent_a) != NULL
2470 = ALLOCNO_LOOP_TREE_NODE (parent_a)->parent) == NULL
2471 || (parent_a = (parent->regno_allocno_map
2472 [ALLOCNO_REGNO (parent_a)])) == NULL)
2475 ALLOCNO_COPIES (a) = NULL;
2476 regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))] = a;
2478 if (mem_dest_p && copy_info_to_removed_store_destinations (i))
2481 ira_assert (new_pseudos_p || ira_max_point_before_emit == ira_max_point);
2482 if (merged_p || ira_max_point_before_emit != ira_max_point)
2483 ira_rebuild_start_finish_chains ();
2486 /* Rebuild conflicts. */
2487 FOR_EACH_ALLOCNO (a, ai)
2489 if (a != regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))]
2490 || ALLOCNO_CAP_MEMBER (a) != NULL)
2492 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
2493 ira_assert (r->allocno == a);
2494 clear_allocno_conflicts (a);
2496 allocnos_live = sparseset_alloc (ira_allocnos_num);
2497 for (i = 0; i < ira_max_point; i++)
2499 for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next)
2502 if (a != regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))]
2503 || ALLOCNO_CAP_MEMBER (a) != NULL)
2505 num = ALLOCNO_NUM (a);
2506 cover_class = ALLOCNO_COVER_CLASS (a);
2507 sparseset_set_bit (allocnos_live, num);
2508 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, n)
2510 ira_allocno_t live_a = ira_allocnos[n];
2512 if (ira_reg_classes_intersect_p
2513 [cover_class][ALLOCNO_COVER_CLASS (live_a)]
2514 /* Don't set up conflict for the allocno with itself. */
2516 ira_add_allocno_conflict (a, live_a);
2520 for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
2521 sparseset_clear_bit (allocnos_live, ALLOCNO_NUM (r->allocno));
2523 sparseset_free (allocnos_live);
2524 compress_conflict_vecs ();
2526 /* Mark some copies for removing and change allocnos in the rest
2528 FOR_EACH_COPY (cp, ci)
2530 if (ALLOCNO_CAP_MEMBER (cp->first) != NULL
2531 || ALLOCNO_CAP_MEMBER (cp->second) != NULL)
2533 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2535 (ira_dump_file, " Remove cp%d:%c%dr%d-%c%dr%d\n",
2536 cp->num, ALLOCNO_CAP_MEMBER (cp->first) != NULL ? 'c' : 'a',
2537 ALLOCNO_NUM (cp->first), REGNO (ALLOCNO_REG (cp->first)),
2538 ALLOCNO_CAP_MEMBER (cp->second) != NULL ? 'c' : 'a',
2539 ALLOCNO_NUM (cp->second), REGNO (ALLOCNO_REG (cp->second)));
2540 cp->loop_tree_node = NULL;
2543 first = regno_top_level_allocno_map[REGNO (ALLOCNO_REG (cp->first))];
2544 second = regno_top_level_allocno_map[REGNO (ALLOCNO_REG (cp->second))];
2545 node = cp->loop_tree_node;
2547 keep_p = true; /* It copy generated in ira-emit.c. */
2550 /* Check that the copy was not propagated from level on
2551 which we will have different pseudos. */
2552 node_first = node->regno_allocno_map[ALLOCNO_REGNO (cp->first)];
2553 node_second = node->regno_allocno_map[ALLOCNO_REGNO (cp->second)];
2554 keep_p = ((REGNO (ALLOCNO_REG (first))
2555 == REGNO (ALLOCNO_REG (node_first)))
2556 && (REGNO (ALLOCNO_REG (second))
2557 == REGNO (ALLOCNO_REG (node_second))));
2561 cp->loop_tree_node = ira_loop_tree_root;
2563 cp->second = second;
2567 cp->loop_tree_node = NULL;
2568 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2569 fprintf (ira_dump_file, " Remove cp%d:a%dr%d-a%dr%d\n",
2570 cp->num, ALLOCNO_NUM (cp->first),
2571 REGNO (ALLOCNO_REG (cp->first)), ALLOCNO_NUM (cp->second),
2572 REGNO (ALLOCNO_REG (cp->second)));
2575 /* Remove unnecessary allocnos on lower levels of the loop tree. */
2576 FOR_EACH_ALLOCNO (a, ai)
2578 if (a != regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))]
2579 || ALLOCNO_CAP_MEMBER (a) != NULL)
2581 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2582 fprintf (ira_dump_file, " Remove a%dr%d\n",
2583 ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)));
2587 ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
2588 ALLOCNO_REGNO (a) = REGNO (ALLOCNO_REG (a));
2589 ALLOCNO_CAP (a) = NULL;
2590 /* Restore updated costs for assignments from reload. */
2591 ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
2592 ALLOCNO_UPDATED_COVER_CLASS_COST (a) = ALLOCNO_COVER_CLASS_COST (a);
2593 if (! ALLOCNO_ASSIGNED_P (a))
2594 ira_free_allocno_updated_costs (a);
2595 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2596 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2598 /* Remove unnecessary copies. */
2599 FOR_EACH_COPY (cp, ci)
2601 if (cp->loop_tree_node == NULL)
2603 ira_copies[cp->num] = NULL;
2608 (ALLOCNO_LOOP_TREE_NODE (cp->first) == ira_loop_tree_root
2609 && ALLOCNO_LOOP_TREE_NODE (cp->second) == ira_loop_tree_root);
2610 ira_add_allocno_copy_to_list (cp);
2611 ira_swap_allocno_copy_ends_if_necessary (cp);
2613 rebuild_regno_allocno_maps ();
2614 if (ira_max_point != ira_max_point_before_emit)
2615 ira_compress_allocno_live_ranges ();
2616 ira_free (regno_top_level_allocno_map);
2621 #ifdef ENABLE_IRA_CHECKING
2622 /* Check creation of all allocnos. Allocnos on lower levels should
2623 have allocnos or caps on all upper levels. */
2625 check_allocno_creation (void)
2628 ira_allocno_iterator ai;
2629 ira_loop_tree_node_t loop_tree_node;
2631 FOR_EACH_ALLOCNO (a, ai)
2633 loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
2634 ira_assert (bitmap_bit_p (loop_tree_node->all_allocnos,
2636 if (loop_tree_node == ira_loop_tree_root)
2638 if (ALLOCNO_CAP_MEMBER (a) != NULL)
2639 ira_assert (ALLOCNO_CAP (a) != NULL);
2640 else if (ALLOCNO_CAP (a) == NULL)
2641 ira_assert (loop_tree_node->parent
2642 ->regno_allocno_map[ALLOCNO_REGNO (a)] != NULL
2643 && bitmap_bit_p (loop_tree_node->border_allocnos,
2649 /* Create a internal representation (IR) for IRA (allocnos, copies,
2650 loop tree nodes). If LOOPS_P is FALSE the nodes corresponding to
2651 the loops (except the root which corresponds the all function) and
2652 correspondingly allocnos for the loops will be not created. Such
2653 parameter value is used for Chaitin-Briggs coloring. The function
2654 returns TRUE if we generate loop structure (besides nodes
2655 representing all function and the basic blocks) for regional
2656 allocation. A true return means that we really need to flatten IR
2657 before the reload. */
2659 ira_build (bool loops_p)
2663 initiate_cost_vectors ();
2664 initiate_allocnos ();
2666 create_loop_tree_nodes (loops_p);
2670 ira_create_allocno_live_ranges ();
2671 remove_unnecessary_regions ();
2672 ira_compress_allocno_live_ranges ();
2673 update_bad_spill_attribute ();
2674 loops_p = more_one_region_p ();
2677 propagate_allocno_info ();
2680 ira_tune_allocno_costs_and_cover_classes ();
2681 #ifdef ENABLE_IRA_CHECKING
2682 check_allocno_creation ();
2684 setup_min_max_allocno_live_range_point ();
2685 sort_conflict_id_allocno_map ();
2686 setup_min_max_conflict_allocno_ids ();
2687 ira_build_conflicts ();
2688 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2689 print_copies (ira_dump_file);
2690 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2694 allocno_live_range_t r;
2695 ira_allocno_iterator ai;
2698 FOR_EACH_ALLOCNO (a, ai)
2699 n += ALLOCNO_CONFLICT_ALLOCNOS_NUM (a);
2701 FOR_EACH_ALLOCNO (a, ai)
2702 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
2704 fprintf (ira_dump_file, " regions=%d, blocks=%d, points=%d\n",
2705 VEC_length (loop_p, ira_loops.larray), n_basic_blocks,
2707 fprintf (ira_dump_file,
2708 " allocnos=%d, copies=%d, conflicts=%d, ranges=%d\n",
2709 ira_allocnos_num, ira_copies_num, n, nr);
2714 /* Release the data created by function ira_build. */
2718 finish_loop_tree_nodes ();
2721 finish_cost_vectors ();
2722 ira_finish_allocno_live_ranges ();