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_algorithm != IRA_ALGORITHM_REGIONAL
1587 && flag_ira_algorithm != IRA_ALGORITHM_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 /* Return TRUE if NODE represents a loop with should be removed from
1681 regional allocation. We remove a loop with low register pressure
1682 inside another loop with register pressure. In this case a
1683 separate allocation of the loop hardly helps (for irregular
1684 register file architecture it could help by choosing a better hard
1685 register in the loop but we prefer faster allocation even in this
1688 loop_node_to_be_removed_p (ira_loop_tree_node_t node)
1690 return (node->parent != NULL && low_pressure_loop_node_p (node->parent)
1691 && low_pressure_loop_node_p (node));
1694 /* Definition of vector of loop tree nodes. */
1695 DEF_VEC_P(ira_loop_tree_node_t);
1696 DEF_VEC_ALLOC_P(ira_loop_tree_node_t, heap);
1698 /* Vec containing references to all removed loop tree nodes. */
1699 static VEC(ira_loop_tree_node_t,heap) *removed_loop_vec;
1701 /* Vec containing references to all children of loop tree nodes. */
1702 static VEC(ira_loop_tree_node_t,heap) *children_vec;
1704 /* Remove subregions of NODE if their separate allocation will not
1705 improve the result. */
1707 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_node_t node)
1711 ira_loop_tree_node_t subnode;
1713 remove_p = loop_node_to_be_removed_p (node);
1715 VEC_safe_push (ira_loop_tree_node_t, heap, children_vec, node);
1716 start = VEC_length (ira_loop_tree_node_t, children_vec);
1717 for (subnode = node->children; subnode != NULL; subnode = subnode->next)
1718 if (subnode->bb == NULL)
1719 remove_uneccesary_loop_nodes_from_loop_tree (subnode);
1721 VEC_safe_push (ira_loop_tree_node_t, heap, children_vec, subnode);
1722 node->children = node->subloops = NULL;
1725 VEC_safe_push (ira_loop_tree_node_t, heap, removed_loop_vec, node);
1728 while (VEC_length (ira_loop_tree_node_t, children_vec) > start)
1730 subnode = VEC_pop (ira_loop_tree_node_t, children_vec);
1731 subnode->parent = node;
1732 subnode->next = node->children;
1733 node->children = subnode;
1734 if (subnode->bb == NULL)
1736 subnode->subloop_next = node->subloops;
1737 node->subloops = subnode;
1742 /* Remove allocnos from loops removed from the allocation
1745 remove_unnecessary_allocnos (void)
1749 enum reg_class cover_class;
1750 ira_allocno_t a, prev_a, next_a, parent_a;
1751 ira_loop_tree_node_t a_node, parent;
1752 allocno_live_range_t r;
1755 for (regno = max_reg_num () - 1; regno >= FIRST_PSEUDO_REGISTER; regno--)
1756 for (prev_a = NULL, a = ira_regno_allocno_map[regno];
1760 next_a = ALLOCNO_NEXT_REGNO_ALLOCNO (a);
1761 a_node = ALLOCNO_LOOP_TREE_NODE (a);
1762 if (! loop_node_to_be_removed_p (a_node))
1766 for (parent = a_node->parent;
1767 (parent_a = parent->regno_allocno_map[regno]) == NULL
1768 && loop_node_to_be_removed_p (parent);
1769 parent = parent->parent)
1771 if (parent_a == NULL)
1773 /* There are no allocnos with the same regno in upper
1774 region -- just move the allocno to the upper
1777 ALLOCNO_LOOP_TREE_NODE (a) = parent;
1778 parent->regno_allocno_map[regno] = a;
1779 bitmap_set_bit (parent->all_allocnos, ALLOCNO_NUM (a));
1783 /* Remove the allocno and update info of allocno in
1784 the upper region. */
1786 ira_regno_allocno_map[regno] = next_a;
1788 ALLOCNO_NEXT_REGNO_ALLOCNO (prev_a) = next_a;
1789 r = ALLOCNO_LIVE_RANGES (a);
1790 change_allocno_in_range_list (r, parent_a);
1791 ALLOCNO_LIVE_RANGES (parent_a)
1792 = ira_merge_allocno_live_ranges
1793 (r, ALLOCNO_LIVE_RANGES (parent_a));
1795 ALLOCNO_LIVE_RANGES (a) = NULL;
1796 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (parent_a),
1797 ALLOCNO_CONFLICT_HARD_REGS (a));
1799 if (ALLOCNO_NO_STACK_REG_P (a))
1800 ALLOCNO_NO_STACK_REG_P (parent_a) = true;
1802 ALLOCNO_NREFS (parent_a) += ALLOCNO_NREFS (a);
1803 ALLOCNO_FREQ (parent_a) += ALLOCNO_FREQ (a);
1804 ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
1806 (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a),
1807 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1808 ALLOCNO_CALLS_CROSSED_NUM (parent_a)
1809 += ALLOCNO_CALLS_CROSSED_NUM (a);
1810 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
1811 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
1812 if (! ALLOCNO_BAD_SPILL_P (a))
1813 ALLOCNO_BAD_SPILL_P (parent_a) = false;
1815 if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
1816 ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a) = true;
1818 cover_class = ALLOCNO_COVER_CLASS (a);
1819 ira_assert (cover_class == ALLOCNO_COVER_CLASS (parent_a));
1820 ira_allocate_and_accumulate_costs
1821 (&ALLOCNO_HARD_REG_COSTS (parent_a), cover_class,
1822 ALLOCNO_HARD_REG_COSTS (a));
1823 ira_allocate_and_accumulate_costs
1824 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a),
1826 ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
1827 ALLOCNO_COVER_CLASS_COST (parent_a)
1828 += ALLOCNO_COVER_CLASS_COST (a);
1829 ALLOCNO_MEMORY_COST (parent_a) += ALLOCNO_MEMORY_COST (a);
1835 ira_rebuild_start_finish_chains ();
1838 /* Remove loops from consideration. We remove loops for which a
1839 separate allocation will not improve the result. We have to do
1840 this after allocno creation and their costs and cover class
1841 evaluation because only after that the register pressure can be
1842 known and is calculated. */
1844 remove_unnecessary_regions (void)
1847 = VEC_alloc (ira_loop_tree_node_t, heap,
1848 last_basic_block + VEC_length (loop_p, ira_loops.larray));
1850 = VEC_alloc (ira_loop_tree_node_t, heap,
1851 last_basic_block + VEC_length (loop_p, ira_loops.larray));
1852 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_root) ;
1853 VEC_free (ira_loop_tree_node_t, heap, children_vec);
1854 remove_unnecessary_allocnos ();
1855 while (VEC_length (ira_loop_tree_node_t, removed_loop_vec) > 0)
1856 finish_loop_tree_node (VEC_pop (ira_loop_tree_node_t, removed_loop_vec));
1857 VEC_free (ira_loop_tree_node_t, heap, removed_loop_vec);
1862 /* At this point true value of allocno attribute bad_spill_p means
1863 that there is an insn where allocno occurs and where the allocno
1864 can not be used as memory. The function updates the attribute, now
1865 it can be true only for allocnos which can not be used as memory in
1866 an insn and in whose live ranges there is other allocno deaths.
1867 Spilling allocnos with true value will not improve the code because
1868 it will not make other allocnos colorable and additional reloads
1869 for the corresponding pseudo will be generated in reload pass for
1870 each insn it occurs.
1872 This is a trick mentioned in one classic article of Chaitin etc
1873 which is frequently omitted in other implementations of RA based on
1876 update_bad_spill_attribute (void)
1880 ira_allocno_iterator ai;
1881 allocno_live_range_t r;
1882 enum reg_class cover_class;
1883 bitmap_head dead_points[N_REG_CLASSES];
1885 for (i = 0; i < ira_reg_class_cover_size; i++)
1887 cover_class = ira_reg_class_cover[i];
1888 bitmap_initialize (&dead_points[cover_class], ®_obstack);
1890 FOR_EACH_ALLOCNO (a, ai)
1892 cover_class = ALLOCNO_COVER_CLASS (a);
1893 if (cover_class == NO_REGS)
1895 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
1896 bitmap_set_bit (&dead_points[cover_class], r->finish);
1898 FOR_EACH_ALLOCNO (a, ai)
1900 cover_class = ALLOCNO_COVER_CLASS (a);
1901 if (cover_class == NO_REGS)
1903 if (! ALLOCNO_BAD_SPILL_P (a))
1905 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
1907 for (i = r->start + 1; i < r->finish; i++)
1908 if (bitmap_bit_p (&dead_points[cover_class], i))
1914 ALLOCNO_BAD_SPILL_P (a) = false;
1916 for (i = 0; i < ira_reg_class_cover_size; i++)
1918 cover_class = ira_reg_class_cover[i];
1919 bitmap_clear (&dead_points[cover_class]);
1925 /* Set up minimal and maximal live range points for allocnos. */
1927 setup_min_max_allocno_live_range_point (void)
1930 ira_allocno_t a, parent_a, cap;
1931 ira_allocno_iterator ai;
1932 allocno_live_range_t r;
1933 ira_loop_tree_node_t parent;
1935 FOR_EACH_ALLOCNO (a, ai)
1937 r = ALLOCNO_LIVE_RANGES (a);
1940 ALLOCNO_MAX (a) = r->finish;
1941 for (; r->next != NULL; r = r->next)
1943 ALLOCNO_MIN (a) = r->start;
1945 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1946 for (a = ira_regno_allocno_map[i];
1948 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1950 if (ALLOCNO_MAX (a) < 0)
1952 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
1953 /* Accumulation of range info. */
1954 if (ALLOCNO_CAP (a) != NULL)
1956 for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
1958 if (ALLOCNO_MAX (cap) < ALLOCNO_MAX (a))
1959 ALLOCNO_MAX (cap) = ALLOCNO_MAX (a);
1960 if (ALLOCNO_MIN (cap) > ALLOCNO_MIN (a))
1961 ALLOCNO_MIN (cap) = ALLOCNO_MIN (a);
1965 if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL)
1967 parent_a = parent->regno_allocno_map[i];
1968 if (ALLOCNO_MAX (parent_a) < ALLOCNO_MAX (a))
1969 ALLOCNO_MAX (parent_a) = ALLOCNO_MAX (a);
1970 if (ALLOCNO_MIN (parent_a) > ALLOCNO_MIN (a))
1971 ALLOCNO_MIN (parent_a) = ALLOCNO_MIN (a);
1973 #ifdef ENABLE_IRA_CHECKING
1974 FOR_EACH_ALLOCNO (a, ai)
1976 if ((0 <= ALLOCNO_MIN (a) && ALLOCNO_MIN (a) <= ira_max_point)
1977 && (0 <= ALLOCNO_MAX (a) && ALLOCNO_MAX (a) <= ira_max_point))
1984 /* Sort allocnos according to their live ranges. Allocnos with
1985 smaller cover class are put first. Allocnos with the same cove
1986 class are ordered according their start (min). Allocnos with the
1987 same start are ordered according their finish (max). */
1989 allocno_range_compare_func (const void *v1p, const void *v2p)
1992 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
1993 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
1995 if ((diff = ALLOCNO_COVER_CLASS (a1) - ALLOCNO_COVER_CLASS (a2)) != 0)
1997 if ((diff = ALLOCNO_MIN (a1) - ALLOCNO_MIN (a2)) != 0)
1999 if ((diff = ALLOCNO_MAX (a1) - ALLOCNO_MAX (a2)) != 0)
2001 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2004 /* Sort ira_conflict_id_allocno_map and set up conflict id of
2007 sort_conflict_id_allocno_map (void)
2011 ira_allocno_iterator ai;
2014 FOR_EACH_ALLOCNO (a, ai)
2015 ira_conflict_id_allocno_map[num++] = a;
2016 qsort (ira_conflict_id_allocno_map, num, sizeof (ira_allocno_t),
2017 allocno_range_compare_func);
2018 for (i = 0; i < num; i++)
2019 if ((a = ira_conflict_id_allocno_map[i]) != NULL)
2020 ALLOCNO_CONFLICT_ID (a) = i;
2021 for (i = num; i < ira_allocnos_num; i++)
2022 ira_conflict_id_allocno_map[i] = NULL;
2025 /* Set up minimal and maximal conflict ids of allocnos with which
2026 given allocno can conflict. */
2028 setup_min_max_conflict_allocno_ids (void)
2030 enum reg_class cover_class;
2031 int i, j, min, max, start, finish, first_not_finished, filled_area_start;
2032 int *live_range_min, *last_lived;
2035 live_range_min = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
2037 first_not_finished = -1;
2038 for (i = 0; i < ira_allocnos_num; i++)
2040 a = ira_conflict_id_allocno_map[i];
2043 if (cover_class != ALLOCNO_COVER_CLASS (a))
2045 cover_class = ALLOCNO_COVER_CLASS (a);
2047 first_not_finished = i;
2051 start = ALLOCNO_MIN (a);
2052 /* If we skip an allocno, the allocno with smaller ids will
2053 be also skipped because of the secondary sorting the
2054 range finishes (see function
2055 allocno_range_compare_func). */
2056 while (first_not_finished < i
2057 && start > ALLOCNO_MAX (ira_conflict_id_allocno_map
2058 [first_not_finished]))
2059 first_not_finished++;
2060 min = first_not_finished;
2063 /* We could increase min further in this case but it is good
2066 live_range_min[i] = ALLOCNO_MIN (a);
2067 ALLOCNO_MIN (a) = min;
2069 last_lived = (int *) ira_allocate (sizeof (int) * ira_max_point);
2071 filled_area_start = -1;
2072 for (i = ira_allocnos_num - 1; i >= 0; i--)
2074 a = ira_conflict_id_allocno_map[i];
2077 if (cover_class != ALLOCNO_COVER_CLASS (a))
2079 cover_class = ALLOCNO_COVER_CLASS (a);
2080 for (j = 0; j < ira_max_point; j++)
2082 filled_area_start = ira_max_point;
2084 min = live_range_min[i];
2085 finish = ALLOCNO_MAX (a);
2086 max = last_lived[finish];
2088 /* We could decrease max further in this case but it is good
2090 max = ALLOCNO_CONFLICT_ID (a) - 1;
2091 ALLOCNO_MAX (a) = max;
2092 /* In filling, we can go further A range finish to recognize
2093 intersection quickly because if the finish of subsequently
2094 processed allocno (it has smaller conflict id) range is
2095 further A range finish than they are definitely intersected
2096 (the reason for this is the allocnos with bigger conflict id
2097 have their range starts not smaller than allocnos with
2099 for (j = min; j < filled_area_start; j++)
2101 filled_area_start = min;
2103 ira_free (last_lived);
2104 ira_free (live_range_min);
2113 ira_allocno_iterator ai;
2114 ira_loop_tree_node_t loop_tree_node;
2116 FOR_EACH_ALLOCNO (a, ai)
2118 if (ALLOCNO_LOOP_TREE_NODE (a) == ira_loop_tree_root)
2120 if (ALLOCNO_CAP_MEMBER (a) != NULL)
2121 create_cap_allocno (a);
2122 else if (ALLOCNO_CAP (a) == NULL)
2124 loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
2125 if (!bitmap_bit_p (loop_tree_node->border_allocnos, ALLOCNO_NUM (a)))
2126 create_cap_allocno (a);
2133 /* The page contains code transforming more one region internal
2134 representation (IR) to one region IR which is necessary for reload.
2135 This transformation is called IR flattening. We might just rebuild
2136 the IR for one region but we don't do it because it takes a lot of
2139 /* Map: regno -> allocnos which will finally represent the regno for
2140 IR with one region. */
2141 static ira_allocno_t *regno_top_level_allocno_map;
2143 /* Process all allocnos originated from pseudo REGNO and copy live
2144 ranges, hard reg conflicts, and allocno stack reg attributes from
2145 low level allocnos to final allocnos which are destinations of
2146 removed stores at a loop exit. Return true if we copied live
2149 copy_info_to_removed_store_destinations (int regno)
2151 ira_allocno_t a, parent_a;
2152 ira_loop_tree_node_t parent;
2153 allocno_live_range_t r;
2157 for (a = ira_regno_allocno_map[regno];
2159 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2161 if (a != regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))])
2162 /* This allocno will be removed. */
2164 /* Caps will be removed. */
2165 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2166 for (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
2168 parent = parent->parent)
2169 if ((parent_a = parent->regno_allocno_map[regno]) == NULL
2170 || (parent_a == regno_top_level_allocno_map[REGNO (ALLOCNO_REG
2172 && ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a)))
2174 if (parent == NULL || parent_a == NULL)
2176 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2180 " Coping ranges of a%dr%d to a%dr%d: ",
2181 ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)),
2182 ALLOCNO_NUM (parent_a), REGNO (ALLOCNO_REG (parent_a)));
2183 ira_print_live_range_list (ira_dump_file,
2184 ALLOCNO_LIVE_RANGES (a));
2186 r = ira_copy_allocno_live_range_list (ALLOCNO_LIVE_RANGES (a));
2187 change_allocno_in_range_list (r, parent_a);
2188 ALLOCNO_LIVE_RANGES (parent_a)
2189 = ira_merge_allocno_live_ranges (r, ALLOCNO_LIVE_RANGES (parent_a));
2190 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a),
2191 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
2193 if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
2194 ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a) = true;
2196 ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
2197 ALLOCNO_CALLS_CROSSED_NUM (parent_a)
2198 += ALLOCNO_CALLS_CROSSED_NUM (a);
2199 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
2200 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2206 /* Flatten the IR. In other words, this function transforms IR as if
2207 it were built with one region (without loops). We could make it
2208 much simpler by rebuilding IR with one region, but unfortunately it
2209 takes a lot of time. MAX_REGNO_BEFORE_EMIT and
2210 IRA_MAX_POINT_BEFORE_EMIT are correspondingly MAX_REG_NUM () and
2211 IRA_MAX_POINT before emitting insns on the loop borders. */
2213 ira_flattening (int max_regno_before_emit, int ira_max_point_before_emit)
2218 bool new_pseudos_p, merged_p, mem_dest_p;
2220 enum reg_class cover_class;
2221 ira_allocno_t a, parent_a, first, second, node_first, node_second;
2223 ira_loop_tree_node_t parent, node;
2224 allocno_live_range_t r;
2225 ira_allocno_iterator ai;
2226 ira_copy_iterator ci;
2227 sparseset allocnos_live;
2229 regno_top_level_allocno_map
2230 = (ira_allocno_t *) ira_allocate (max_reg_num () * sizeof (ira_allocno_t));
2231 memset (regno_top_level_allocno_map, 0,
2232 max_reg_num () * sizeof (ira_allocno_t));
2233 new_pseudos_p = merged_p = false;
2234 FOR_EACH_ALLOCNO (a, ai)
2236 if (ALLOCNO_CAP_MEMBER (a) != NULL)
2237 /* Caps are not in the regno allocno maps and they are never
2238 will be transformed into allocnos existing after IR
2241 COPY_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
2242 ALLOCNO_CONFLICT_HARD_REGS (a));
2244 ALLOCNO_TOTAL_NO_STACK_REG_P (a) = ALLOCNO_NO_STACK_REG_P (a);
2247 /* Fix final allocno attributes. */
2248 for (i = max_regno_before_emit - 1; i >= FIRST_PSEUDO_REGISTER; i--)
2251 for (a = ira_regno_allocno_map[i];
2253 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2255 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2256 if (ALLOCNO_SOMEWHERE_RENAMED_P (a))
2257 new_pseudos_p = true;
2258 if (ALLOCNO_CAP (a) != NULL
2259 || (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
2260 || ((parent_a = parent->regno_allocno_map[ALLOCNO_REGNO (a)])
2263 ALLOCNO_COPIES (a) = NULL;
2264 regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))] = a;
2267 ira_assert (ALLOCNO_CAP_MEMBER (parent_a) == NULL);
2269 if (ALLOCNO_MEM_OPTIMIZED_DEST (a) != NULL)
2271 if (REGNO (ALLOCNO_REG (a)) == REGNO (ALLOCNO_REG (parent_a)))
2273 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a),
2274 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
2276 if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
2277 ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a) = true;
2279 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2281 fprintf (ira_dump_file,
2282 " Moving ranges of a%dr%d to a%dr%d: ",
2283 ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)),
2284 ALLOCNO_NUM (parent_a),
2285 REGNO (ALLOCNO_REG (parent_a)));
2286 ira_print_live_range_list (ira_dump_file,
2287 ALLOCNO_LIVE_RANGES (a));
2289 change_allocno_in_range_list (ALLOCNO_LIVE_RANGES (a), parent_a);
2290 ALLOCNO_LIVE_RANGES (parent_a)
2291 = ira_merge_allocno_live_ranges
2292 (ALLOCNO_LIVE_RANGES (a), ALLOCNO_LIVE_RANGES (parent_a));
2294 ALLOCNO_LIVE_RANGES (a) = NULL;
2295 ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a)
2296 = (ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a)
2297 || ALLOCNO_MEM_OPTIMIZED_DEST_P (a));
2300 new_pseudos_p = true;
2303 ALLOCNO_NREFS (parent_a) -= ALLOCNO_NREFS (a);
2304 ALLOCNO_FREQ (parent_a) -= ALLOCNO_FREQ (a);
2305 ALLOCNO_CALL_FREQ (parent_a) -= ALLOCNO_CALL_FREQ (a);
2306 ALLOCNO_CALLS_CROSSED_NUM (parent_a)
2307 -= ALLOCNO_CALLS_CROSSED_NUM (a);
2308 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
2309 -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2310 ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a) >= 0
2311 && ALLOCNO_NREFS (parent_a) >= 0
2312 && ALLOCNO_FREQ (parent_a) >= 0);
2313 cover_class = ALLOCNO_COVER_CLASS (parent_a);
2314 hard_regs_num = ira_class_hard_regs_num[cover_class];
2315 if (ALLOCNO_HARD_REG_COSTS (a) != NULL
2316 && ALLOCNO_HARD_REG_COSTS (parent_a) != NULL)
2317 for (j = 0; j < hard_regs_num; j++)
2318 ALLOCNO_HARD_REG_COSTS (parent_a)[j]
2319 -= ALLOCNO_HARD_REG_COSTS (a)[j];
2320 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL
2321 && ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a) != NULL)
2322 for (j = 0; j < hard_regs_num; j++)
2323 ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a)[j]
2324 -= ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[j];
2325 ALLOCNO_COVER_CLASS_COST (parent_a)
2326 -= ALLOCNO_COVER_CLASS_COST (a);
2327 ALLOCNO_MEMORY_COST (parent_a) -= ALLOCNO_MEMORY_COST (a);
2328 if (ALLOCNO_CAP (parent_a) != NULL
2330 = ALLOCNO_LOOP_TREE_NODE (parent_a)->parent) == NULL
2331 || (parent_a = (parent->regno_allocno_map
2332 [ALLOCNO_REGNO (parent_a)])) == NULL)
2335 ALLOCNO_COPIES (a) = NULL;
2336 regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))] = a;
2338 if (mem_dest_p && copy_info_to_removed_store_destinations (i))
2341 ira_assert (new_pseudos_p || ira_max_point_before_emit == ira_max_point);
2342 if (merged_p || ira_max_point_before_emit != ira_max_point)
2343 ira_rebuild_start_finish_chains ();
2346 /* Rebuild conflicts. */
2347 FOR_EACH_ALLOCNO (a, ai)
2349 if (a != regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))]
2350 || ALLOCNO_CAP_MEMBER (a) != NULL)
2352 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
2353 ira_assert (r->allocno == a);
2354 clear_allocno_conflicts (a);
2356 allocnos_live = sparseset_alloc (ira_allocnos_num);
2357 for (i = 0; i < ira_max_point; i++)
2359 for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next)
2362 if (a != regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))]
2363 || ALLOCNO_CAP_MEMBER (a) != NULL)
2365 num = ALLOCNO_NUM (a);
2366 cover_class = ALLOCNO_COVER_CLASS (a);
2367 sparseset_set_bit (allocnos_live, num);
2368 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, n)
2370 ira_allocno_t live_a = ira_allocnos[n];
2372 if (cover_class == ALLOCNO_COVER_CLASS (live_a)
2373 /* Don't set up conflict for the allocno with itself. */
2375 ira_add_allocno_conflict (a, live_a);
2379 for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
2380 sparseset_clear_bit (allocnos_live, ALLOCNO_NUM (r->allocno));
2382 sparseset_free (allocnos_live);
2383 compress_conflict_vecs ();
2385 /* Mark some copies for removing and change allocnos in the rest
2387 FOR_EACH_COPY (cp, ci)
2389 if (ALLOCNO_CAP_MEMBER (cp->first) != NULL
2390 || ALLOCNO_CAP_MEMBER (cp->second) != NULL)
2392 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2394 (ira_dump_file, " Remove cp%d:%c%dr%d-%c%dr%d\n",
2395 cp->num, ALLOCNO_CAP_MEMBER (cp->first) != NULL ? 'c' : 'a',
2396 ALLOCNO_NUM (cp->first), REGNO (ALLOCNO_REG (cp->first)),
2397 ALLOCNO_CAP_MEMBER (cp->second) != NULL ? 'c' : 'a',
2398 ALLOCNO_NUM (cp->second), REGNO (ALLOCNO_REG (cp->second)));
2399 cp->loop_tree_node = NULL;
2402 first = regno_top_level_allocno_map[REGNO (ALLOCNO_REG (cp->first))];
2403 second = regno_top_level_allocno_map[REGNO (ALLOCNO_REG (cp->second))];
2404 node = cp->loop_tree_node;
2406 keep_p = true; /* It copy generated in ira-emit.c. */
2409 /* Check that the copy was not propagated from level on
2410 which we will have different pseudos. */
2411 node_first = node->regno_allocno_map[ALLOCNO_REGNO (cp->first)];
2412 node_second = node->regno_allocno_map[ALLOCNO_REGNO (cp->second)];
2413 keep_p = ((REGNO (ALLOCNO_REG (first))
2414 == REGNO (ALLOCNO_REG (node_first)))
2415 && (REGNO (ALLOCNO_REG (second))
2416 == REGNO (ALLOCNO_REG (node_second))));
2420 cp->loop_tree_node = ira_loop_tree_root;
2422 cp->second = second;
2426 cp->loop_tree_node = NULL;
2427 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2428 fprintf (ira_dump_file, " Remove cp%d:a%dr%d-a%dr%d\n",
2429 cp->num, ALLOCNO_NUM (cp->first),
2430 REGNO (ALLOCNO_REG (cp->first)), ALLOCNO_NUM (cp->second),
2431 REGNO (ALLOCNO_REG (cp->second)));
2434 /* Remove unnecessary allocnos on lower levels of the loop tree. */
2435 FOR_EACH_ALLOCNO (a, ai)
2437 if (a != regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))]
2438 || ALLOCNO_CAP_MEMBER (a) != NULL)
2440 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2441 fprintf (ira_dump_file, " Remove a%dr%d\n",
2442 ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)));
2446 ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
2447 ALLOCNO_REGNO (a) = REGNO (ALLOCNO_REG (a));
2448 ALLOCNO_CAP (a) = NULL;
2449 /* Restore updated costs for assignments from reload. */
2450 ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
2451 ALLOCNO_UPDATED_COVER_CLASS_COST (a) = ALLOCNO_COVER_CLASS_COST (a);
2452 if (! ALLOCNO_ASSIGNED_P (a))
2453 ira_free_allocno_updated_costs (a);
2454 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2455 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2457 /* Remove unnecessary copies. */
2458 FOR_EACH_COPY (cp, ci)
2460 if (cp->loop_tree_node == NULL)
2462 ira_copies[cp->num] = NULL;
2467 (ALLOCNO_LOOP_TREE_NODE (cp->first) == ira_loop_tree_root
2468 && ALLOCNO_LOOP_TREE_NODE (cp->second) == ira_loop_tree_root);
2469 ira_add_allocno_copy_to_list (cp);
2470 ira_swap_allocno_copy_ends_if_necessary (cp);
2472 rebuild_regno_allocno_maps ();
2473 if (ira_max_point != ira_max_point_before_emit)
2474 ira_compress_allocno_live_ranges ();
2475 ira_free (regno_top_level_allocno_map);
2480 #ifdef ENABLE_IRA_CHECKING
2481 /* Check creation of all allocnos. Allocnos on lower levels should
2482 have allocnos or caps on all upper levels. */
2484 check_allocno_creation (void)
2487 ira_allocno_iterator ai;
2488 ira_loop_tree_node_t loop_tree_node;
2490 FOR_EACH_ALLOCNO (a, ai)
2492 loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
2493 ira_assert (bitmap_bit_p (loop_tree_node->all_allocnos,
2495 if (loop_tree_node == ira_loop_tree_root)
2497 if (ALLOCNO_CAP_MEMBER (a) != NULL)
2498 ira_assert (ALLOCNO_CAP (a) != NULL);
2499 else if (ALLOCNO_CAP (a) == NULL)
2500 ira_assert (loop_tree_node->parent
2501 ->regno_allocno_map[ALLOCNO_REGNO (a)] != NULL
2502 && bitmap_bit_p (loop_tree_node->border_allocnos,
2508 /* Create a internal representation (IR) for IRA (allocnos, copies,
2509 loop tree nodes). If LOOPS_P is FALSE the nodes corresponding to
2510 the loops (except the root which corresponds the all function) and
2511 correspondingly allocnos for the loops will be not created. Such
2512 parameter value is used for Chaitin-Briggs coloring. The function
2513 returns TRUE if we generate loop structure (besides nodes
2514 representing all function and the basic blocks) for regional
2515 allocation. A true return means that we really need to flatten IR
2516 before the reload. */
2518 ira_build (bool loops_p)
2522 initiate_cost_vectors ();
2523 initiate_allocnos ();
2525 create_loop_tree_nodes (loops_p);
2529 ira_create_allocno_live_ranges ();
2530 remove_unnecessary_regions ();
2531 ira_compress_allocno_live_ranges ();
2532 update_bad_spill_attribute ();
2533 loops_p = more_one_region_p ();
2536 propagate_allocno_info ();
2539 ira_tune_allocno_costs_and_cover_classes ();
2540 #ifdef ENABLE_IRA_CHECKING
2541 check_allocno_creation ();
2543 setup_min_max_allocno_live_range_point ();
2544 sort_conflict_id_allocno_map ();
2545 setup_min_max_conflict_allocno_ids ();
2546 ira_build_conflicts ();
2547 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2548 print_copies (ira_dump_file);
2549 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2553 allocno_live_range_t r;
2554 ira_allocno_iterator ai;
2557 FOR_EACH_ALLOCNO (a, ai)
2558 n += ALLOCNO_CONFLICT_ALLOCNOS_NUM (a);
2560 FOR_EACH_ALLOCNO (a, ai)
2561 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
2563 fprintf (ira_dump_file, " regions=%d, blocks=%d, points=%d\n",
2564 VEC_length (loop_p, ira_loops.larray), n_basic_blocks,
2566 fprintf (ira_dump_file,
2567 " allocnos=%d, copies=%d, conflicts=%d, ranges=%d\n",
2568 ira_allocnos_num, ira_copies_num, n, nr);
2573 /* Release the data created by function ira_build. */
2577 finish_loop_tree_nodes ();
2580 finish_cost_vectors ();
2581 ira_finish_allocno_live_ranges ();