1 /* IRA allocation based on graph coloring.
2 Copyright (C) 2006, 2007, 2008, 2009
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"
33 #include "hard-reg-set.h"
34 #include "basic-block.h"
40 #include "splay-tree.h"
43 /* This file contains code for regional graph coloring, spill/restore
44 code placement optimization, and code helping the reload pass to do
47 /* Bitmap of allocnos which should be colored. */
48 static bitmap coloring_allocno_bitmap;
50 /* Bitmap of allocnos which should be taken into account during
51 coloring. In general case it contains allocnos from
52 coloring_allocno_bitmap plus other already colored conflicting
54 static bitmap consideration_allocno_bitmap;
56 /* TRUE if we coalesced some allocnos. In other words, if we got
57 loops formed by members first_coalesced_allocno and
58 next_coalesced_allocno containing more one allocno. */
59 static bool allocno_coalesced_p;
61 /* Bitmap used to prevent a repeated allocno processing because of
63 static bitmap processed_coalesced_allocno_bitmap;
65 /* All allocnos sorted according their priorities. */
66 static ira_allocno_t *sorted_allocnos;
68 /* Vec representing the stack of allocnos used during coloring. */
69 static VEC(ira_allocno_t,heap) *allocno_stack_vec;
71 /* Array used to choose an allocno for spilling. */
72 static ira_allocno_t *allocnos_for_spilling;
74 /* Pool for splay tree nodes. */
75 static alloc_pool splay_tree_node_pool;
77 /* When an allocno is removed from the splay tree, it is put in the
78 following vector for subsequent inserting it into the splay tree
79 after putting all colorable allocnos onto the stack. The allocno
80 could be removed from and inserted to the splay tree every time
81 when its spilling priority is changed but such solution would be
82 more costly although simpler. */
83 static VEC(ira_allocno_t,heap) *removed_splay_allocno_vec;
85 /* Helper for qsort comparison callbacks - return a positive integer if
86 X > Y, or a negative value otherwise. Use a conditional expression
87 instead of a difference computation to insulate from possible overflow
88 issues, e.g. X - Y < 0 for some X > 0 and Y < 0. */
89 #define SORTGT(x,y) (((x) > (y)) ? 1 : -1)
93 /* This page contains functions used to find conflicts using allocno
96 /* Return TRUE if live ranges of allocnos A1 and A2 intersect. It is
97 used to find a conflict for new allocnos or allocnos with the
98 different cover classes. */
100 allocnos_have_intersected_live_ranges_p (ira_allocno_t a1, ira_allocno_t a2)
104 if (ALLOCNO_REG (a1) != NULL && ALLOCNO_REG (a2) != NULL
105 && (ORIGINAL_REGNO (ALLOCNO_REG (a1))
106 == ORIGINAL_REGNO (ALLOCNO_REG (a2))))
108 return ira_allocno_live_ranges_intersect_p (ALLOCNO_LIVE_RANGES (a1),
109 ALLOCNO_LIVE_RANGES (a2));
112 #ifdef ENABLE_IRA_CHECKING
114 /* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
115 intersect. This should be used when there is only one region.
116 Currently this is used during reload. */
118 pseudos_have_intersected_live_ranges_p (int regno1, int regno2)
120 ira_allocno_t a1, a2;
122 ira_assert (regno1 >= FIRST_PSEUDO_REGISTER
123 && regno2 >= FIRST_PSEUDO_REGISTER);
124 /* Reg info caclulated by dataflow infrastructure can be different
125 from one calculated by regclass. */
126 if ((a1 = ira_loop_tree_root->regno_allocno_map[regno1]) == NULL
127 || (a2 = ira_loop_tree_root->regno_allocno_map[regno2]) == NULL)
129 return allocnos_have_intersected_live_ranges_p (a1, a2);
136 /* This page contains functions used to choose hard registers for
139 /* Array whose element value is TRUE if the corresponding hard
140 register was already allocated for an allocno. */
141 static bool allocated_hardreg_p[FIRST_PSEUDO_REGISTER];
143 /* Describes one element in a queue of allocnos whose costs need to be
144 updated. Each allocno in the queue is known to have a cover class. */
145 struct update_cost_queue_elem
147 /* This element is in the queue iff CHECK == update_cost_check. */
150 /* COST_HOP_DIVISOR**N, where N is the length of the shortest path
151 connecting this allocno to the one being allocated. */
154 /* The next allocno in the queue, or null if this is the last element. */
158 /* The first element in a queue of allocnos whose copy costs need to be
159 updated. Null if the queue is empty. */
160 static ira_allocno_t update_cost_queue;
162 /* The last element in the queue described by update_cost_queue.
163 Not valid if update_cost_queue is null. */
164 static struct update_cost_queue_elem *update_cost_queue_tail;
166 /* A pool of elements in the queue described by update_cost_queue.
167 Elements are indexed by ALLOCNO_NUM. */
168 static struct update_cost_queue_elem *update_cost_queue_elems;
170 /* The current value of update_copy_cost call count. */
171 static int update_cost_check;
173 /* Allocate and initialize data necessary for function
174 update_copy_costs. */
176 initiate_cost_update (void)
180 size = ira_allocnos_num * sizeof (struct update_cost_queue_elem);
181 update_cost_queue_elems
182 = (struct update_cost_queue_elem *) ira_allocate (size);
183 memset (update_cost_queue_elems, 0, size);
184 update_cost_check = 0;
187 /* Deallocate data used by function update_copy_costs. */
189 finish_cost_update (void)
191 ira_free (update_cost_queue_elems);
194 /* When we traverse allocnos to update hard register costs, the cost
195 divisor will be multiplied by the following macro value for each
196 hop from given allocno to directly connected allocnos. */
197 #define COST_HOP_DIVISOR 4
199 /* Start a new cost-updating pass. */
201 start_update_cost (void)
204 update_cost_queue = NULL;
207 /* Add (ALLOCNO, DIVISOR) to the end of update_cost_queue,
208 unless ALLOCNO is already in the queue, or has no cover class. */
210 queue_update_cost (ira_allocno_t allocno, int divisor)
212 struct update_cost_queue_elem *elem;
214 elem = &update_cost_queue_elems[ALLOCNO_NUM (allocno)];
215 if (elem->check != update_cost_check
216 && ALLOCNO_COVER_CLASS (allocno) != NO_REGS)
218 elem->check = update_cost_check;
219 elem->divisor = divisor;
221 if (update_cost_queue == NULL)
222 update_cost_queue = allocno;
224 update_cost_queue_tail->next = allocno;
225 update_cost_queue_tail = elem;
229 /* Try to remove the first element from update_cost_queue. Return false
230 if the queue was empty, otherwise make (*ALLOCNO, *DIVISOR) describe
231 the removed element. */
233 get_next_update_cost (ira_allocno_t *allocno, int *divisor)
235 struct update_cost_queue_elem *elem;
237 if (update_cost_queue == NULL)
240 *allocno = update_cost_queue;
241 elem = &update_cost_queue_elems[ALLOCNO_NUM (*allocno)];
242 *divisor = elem->divisor;
243 update_cost_queue = elem->next;
247 /* Update the cost of allocnos to increase chances to remove some
248 copies as the result of subsequent assignment. */
250 update_copy_costs (ira_allocno_t allocno, bool decr_p)
252 int i, cost, update_cost, hard_regno, divisor;
253 enum machine_mode mode;
254 enum reg_class rclass, cover_class;
255 ira_allocno_t another_allocno;
256 ira_copy_t cp, next_cp;
258 hard_regno = ALLOCNO_HARD_REGNO (allocno);
259 ira_assert (hard_regno >= 0);
261 cover_class = ALLOCNO_COVER_CLASS (allocno);
262 if (cover_class == NO_REGS)
264 i = ira_class_hard_reg_index[cover_class][hard_regno];
266 rclass = REGNO_REG_CLASS (hard_regno);
268 start_update_cost ();
272 mode = ALLOCNO_MODE (allocno);
273 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
275 if (cp->first == allocno)
277 next_cp = cp->next_first_allocno_copy;
278 another_allocno = cp->second;
280 else if (cp->second == allocno)
282 next_cp = cp->next_second_allocno_copy;
283 another_allocno = cp->first;
288 cover_class = ALLOCNO_COVER_CLASS (another_allocno);
289 if (! ira_reg_classes_intersect_p[rclass][cover_class]
290 || ALLOCNO_ASSIGNED_P (another_allocno))
293 cost = (cp->second == allocno
294 ? ira_get_register_move_cost (mode, rclass, cover_class)
295 : ira_get_register_move_cost (mode, cover_class, rclass));
299 update_cost = cp->freq * cost / divisor;
300 if (update_cost == 0)
303 ira_allocate_and_set_or_copy_costs
304 (&ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno), cover_class,
305 ALLOCNO_UPDATED_COVER_CLASS_COST (another_allocno),
306 ALLOCNO_HARD_REG_COSTS (another_allocno));
307 ira_allocate_and_set_or_copy_costs
308 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
310 ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
311 i = ira_class_hard_reg_index[cover_class][hard_regno];
313 ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno)[i] += update_cost;
314 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno)[i]
317 queue_update_cost (another_allocno, divisor * COST_HOP_DIVISOR);
320 while (get_next_update_cost (&allocno, &divisor));
323 /* This function updates COSTS (decrease if DECR_P) for hard_registers
324 of COVER_CLASS by conflict costs of the unassigned allocnos
325 connected by copies with allocnos in update_cost_queue. This
326 update increases chances to remove some copies. */
328 update_conflict_hard_regno_costs (int *costs, enum reg_class cover_class,
331 int i, cost, class_size, freq, mult, div, divisor;
332 int index, hard_regno;
335 enum reg_class another_cover_class;
336 ira_allocno_t allocno, another_allocno;
337 ira_copy_t cp, next_cp;
339 while (get_next_update_cost (&allocno, &divisor))
340 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
342 if (cp->first == allocno)
344 next_cp = cp->next_first_allocno_copy;
345 another_allocno = cp->second;
347 else if (cp->second == allocno)
349 next_cp = cp->next_second_allocno_copy;
350 another_allocno = cp->first;
354 another_cover_class = ALLOCNO_COVER_CLASS (another_allocno);
355 if (! ira_reg_classes_intersect_p[cover_class][another_cover_class]
356 || ALLOCNO_ASSIGNED_P (another_allocno)
357 || ALLOCNO_MAY_BE_SPILLED_P (ALLOCNO_FIRST_COALESCED_ALLOCNO
360 class_size = ira_class_hard_regs_num[another_cover_class];
361 ira_allocate_and_copy_costs
362 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
364 ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
366 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno);
367 if (conflict_costs == NULL)
372 freq = ALLOCNO_FREQ (another_allocno);
375 div = freq * divisor;
377 for (i = class_size - 1; i >= 0; i--)
379 hard_regno = ira_class_hard_regs[another_cover_class][i];
380 ira_assert (hard_regno >= 0);
381 index = ira_class_hard_reg_index[cover_class][hard_regno];
384 cost = conflict_costs [i] * mult / div;
390 costs[index] += cost;
393 /* Probably 5 hops will be enough. */
395 && divisor <= (COST_HOP_DIVISOR
399 queue_update_cost (another_allocno, divisor * COST_HOP_DIVISOR);
403 /* Sort allocnos according to the profit of usage of a hard register
404 instead of memory for them. */
406 allocno_cost_compare_func (const void *v1p, const void *v2p)
408 ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
409 ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
412 c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_UPDATED_COVER_CLASS_COST (p1);
413 c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_UPDATED_COVER_CLASS_COST (p2);
417 /* If regs are equally good, sort by allocno numbers, so that the
418 results of qsort leave nothing to chance. */
419 return ALLOCNO_NUM (p1) - ALLOCNO_NUM (p2);
422 /* Print all allocnos coalesced with ALLOCNO. */
424 print_coalesced_allocno (ira_allocno_t allocno)
428 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
429 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
431 ira_print_expanded_allocno (a);
434 fprintf (ira_dump_file, "+");
438 /* Choose a hard register for ALLOCNO (or for all coalesced allocnos
439 represented by ALLOCNO). If RETRY_P is TRUE, it means that the
440 function called from function `ira_reassign_conflict_allocnos' and
441 `allocno_reload_assign'. This function implements the optimistic
442 coalescing too: if we failed to assign a hard register to set of
443 the coalesced allocnos, we put them onto the coloring stack for
444 subsequent separate assigning. */
446 assign_hard_reg (ira_allocno_t allocno, bool retry_p)
448 HARD_REG_SET conflicting_regs;
449 int i, j, k, hard_regno, best_hard_regno, class_size;
450 int cost, mem_cost, min_cost, full_cost, min_full_cost, add_cost;
453 enum reg_class cover_class, rclass, conflict_cover_class;
454 enum machine_mode mode;
455 ira_allocno_t a, conflict_allocno;
456 ira_allocno_conflict_iterator aci;
457 static int costs[FIRST_PSEUDO_REGISTER], full_costs[FIRST_PSEUDO_REGISTER];
462 ira_assert (! ALLOCNO_ASSIGNED_P (allocno));
463 cover_class = ALLOCNO_COVER_CLASS (allocno);
464 class_size = ira_class_hard_regs_num[cover_class];
465 mode = ALLOCNO_MODE (allocno);
466 CLEAR_HARD_REG_SET (conflicting_regs);
467 best_hard_regno = -1;
468 memset (full_costs, 0, sizeof (int) * class_size);
470 if (allocno_coalesced_p)
471 bitmap_clear (processed_coalesced_allocno_bitmap);
472 memset (costs, 0, sizeof (int) * class_size);
473 memset (full_costs, 0, sizeof (int) * class_size);
475 no_stack_reg_p = false;
477 start_update_cost ();
478 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
479 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
481 mem_cost += ALLOCNO_UPDATED_MEMORY_COST (a);
482 IOR_HARD_REG_SET (conflicting_regs,
483 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
484 ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
485 cover_class, ALLOCNO_HARD_REG_COSTS (a));
486 a_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
488 no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a);
490 for (cost = ALLOCNO_UPDATED_COVER_CLASS_COST (a), i = 0;
495 costs[i] += a_costs[i];
496 full_costs[i] += a_costs[i];
501 full_costs[i] += cost;
503 /* Take preferences of conflicting allocnos into account. */
504 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
505 /* Reload can give another class so we need to check all
507 if (retry_p || bitmap_bit_p (consideration_allocno_bitmap,
508 ALLOCNO_NUM (conflict_allocno)))
510 conflict_cover_class = ALLOCNO_COVER_CLASS (conflict_allocno);
511 ira_assert (ira_reg_classes_intersect_p
512 [cover_class][conflict_cover_class]);
513 if (allocno_coalesced_p)
515 if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
516 ALLOCNO_NUM (conflict_allocno)))
518 bitmap_set_bit (processed_coalesced_allocno_bitmap,
519 ALLOCNO_NUM (conflict_allocno));
521 if (ALLOCNO_ASSIGNED_P (conflict_allocno))
523 if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno)) >= 0
524 && ira_class_hard_reg_index[cover_class][hard_regno] >= 0)
528 ira_reg_mode_hard_regset
529 [hard_regno][ALLOCNO_MODE (conflict_allocno)]);
530 if (hard_reg_set_subset_p (reg_class_contents[cover_class],
535 else if (! ALLOCNO_MAY_BE_SPILLED_P (ALLOCNO_FIRST_COALESCED_ALLOCNO
538 ira_allocate_and_copy_costs
539 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno),
540 conflict_cover_class,
541 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_allocno));
543 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno);
544 if (conflict_costs != NULL)
545 for (j = class_size - 1; j >= 0; j--)
547 hard_regno = ira_class_hard_regs[cover_class][j];
548 ira_assert (hard_regno >= 0);
549 k = (ira_class_hard_reg_index
550 [conflict_cover_class][hard_regno]);
553 full_costs[j] -= conflict_costs[k];
555 queue_update_cost (conflict_allocno, COST_HOP_DIVISOR);
561 /* Take into account preferences of allocnos connected by copies to
562 the conflict allocnos. */
563 update_conflict_hard_regno_costs (full_costs, cover_class, true);
565 /* Take preferences of allocnos connected by copies into
567 start_update_cost ();
568 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
569 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
571 queue_update_cost (a, COST_HOP_DIVISOR);
575 update_conflict_hard_regno_costs (full_costs, cover_class, false);
576 min_cost = min_full_cost = INT_MAX;
577 /* We don't care about giving callee saved registers to allocnos no
578 living through calls because call clobbered registers are
579 allocated first (it is usual practice to put them first in
581 for (i = 0; i < class_size; i++)
583 hard_regno = ira_class_hard_regs[cover_class][i];
586 && FIRST_STACK_REG <= hard_regno && hard_regno <= LAST_STACK_REG)
589 if (! ira_hard_reg_not_in_set_p (hard_regno, mode, conflicting_regs)
590 || TEST_HARD_REG_BIT (prohibited_class_mode_regs[cover_class][mode],
594 full_cost = full_costs[i];
595 if (! allocated_hardreg_p[hard_regno]
596 && ira_hard_reg_not_in_set_p (hard_regno, mode, call_used_reg_set))
597 /* We need to save/restore the hard register in
598 epilogue/prologue. Therefore we increase the cost. */
600 /* ??? If only part is call clobbered. */
601 rclass = REGNO_REG_CLASS (hard_regno);
602 add_cost = (ira_memory_move_cost[mode][rclass][0]
603 + ira_memory_move_cost[mode][rclass][1] - 1);
605 full_cost += add_cost;
609 if (min_full_cost > full_cost)
611 min_full_cost = full_cost;
612 best_hard_regno = hard_regno;
613 ira_assert (hard_regno >= 0);
616 if (min_full_cost > mem_cost)
618 if (! retry_p && internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
619 fprintf (ira_dump_file, "(memory is more profitable %d vs %d) ",
620 mem_cost, min_full_cost);
621 best_hard_regno = -1;
624 if (flag_ira_algorithm != IRA_ALGORITHM_PRIORITY
625 && best_hard_regno < 0
626 && ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno) != allocno)
628 for (j = 0, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
629 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
631 ira_assert (! ALLOCNO_IN_GRAPH_P (a));
632 sorted_allocnos[j++] = a;
636 qsort (sorted_allocnos, j, sizeof (ira_allocno_t),
637 allocno_cost_compare_func);
638 for (i = 0; i < j; i++)
640 a = sorted_allocnos[i];
641 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
642 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
643 VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, a);
644 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
646 fprintf (ira_dump_file, " Pushing");
647 print_coalesced_allocno (a);
648 fprintf (ira_dump_file, "\n");
653 if (best_hard_regno >= 0)
654 allocated_hardreg_p[best_hard_regno] = true;
655 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
656 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
658 ALLOCNO_HARD_REGNO (a) = best_hard_regno;
659 ALLOCNO_ASSIGNED_P (a) = true;
660 if (best_hard_regno >= 0)
661 update_copy_costs (a, true);
662 ira_assert (ALLOCNO_COVER_CLASS (a) == cover_class);
663 /* We don't need updated costs anymore: */
664 ira_free_allocno_updated_costs (a);
668 return best_hard_regno >= 0;
673 /* This page contains the allocator based on the Chaitin-Briggs algorithm. */
675 /* Bucket of allocnos that can colored currently without spilling. */
676 static ira_allocno_t colorable_allocno_bucket;
678 /* Bucket of allocnos that might be not colored currently without
680 static ira_allocno_t uncolorable_allocno_bucket;
682 /* Each element of the array contains the current number of allocnos
683 of given *cover* class in the uncolorable_bucket. */
684 static int uncolorable_allocnos_num[N_REG_CLASSES];
686 /* Return the current spill priority of allocno A. The less the
687 number, the more preferable the allocno for spilling. */
689 allocno_spill_priority (ira_allocno_t a)
691 return (ALLOCNO_TEMP (a)
692 / (ALLOCNO_LEFT_CONFLICTS_NUM (a)
693 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a)][ALLOCNO_MODE (a)]
697 /* Add ALLOCNO to bucket *BUCKET_PTR. ALLOCNO should be not in a bucket
700 add_allocno_to_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
702 ira_allocno_t first_allocno;
703 enum reg_class cover_class;
705 if (bucket_ptr == &uncolorable_allocno_bucket
706 && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
708 uncolorable_allocnos_num[cover_class]++;
709 ira_assert (uncolorable_allocnos_num[cover_class] > 0);
711 first_allocno = *bucket_ptr;
712 ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno) = first_allocno;
713 ALLOCNO_PREV_BUCKET_ALLOCNO (allocno) = NULL;
714 if (first_allocno != NULL)
715 ALLOCNO_PREV_BUCKET_ALLOCNO (first_allocno) = allocno;
716 *bucket_ptr = allocno;
719 /* The function returns frequency and number of available hard
720 registers for allocnos coalesced with ALLOCNO. */
722 get_coalesced_allocnos_attributes (ira_allocno_t allocno, int *freq, int *num)
728 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
729 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
731 *freq += ALLOCNO_FREQ (a);
732 *num += ALLOCNO_AVAILABLE_REGS_NUM (a);
738 /* Compare two allocnos to define which allocno should be pushed first
739 into the coloring stack. If the return is a negative number, the
740 allocno given by the first parameter will be pushed first. In this
741 case such allocno has less priority than the second one and the
742 hard register will be assigned to it after assignment to the second
743 one. As the result of such assignment order, the second allocno
744 has a better chance to get the best hard register. */
746 bucket_allocno_compare_func (const void *v1p, const void *v2p)
748 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
749 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
750 int diff, a1_freq, a2_freq, a1_num, a2_num;
752 if ((diff = (int) ALLOCNO_COVER_CLASS (a2) - ALLOCNO_COVER_CLASS (a1)) != 0)
754 get_coalesced_allocnos_attributes (a1, &a1_freq, &a1_num);
755 get_coalesced_allocnos_attributes (a2, &a2_freq, &a2_num);
756 if ((diff = a2_num - a1_num) != 0)
758 else if ((diff = a1_freq - a2_freq) != 0)
760 return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
763 /* Sort bucket *BUCKET_PTR and return the result through
766 sort_bucket (ira_allocno_t *bucket_ptr)
768 ira_allocno_t a, head;
771 for (n = 0, a = *bucket_ptr; a != NULL; a = ALLOCNO_NEXT_BUCKET_ALLOCNO (a))
772 sorted_allocnos[n++] = a;
775 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
776 bucket_allocno_compare_func);
778 for (n--; n >= 0; n--)
780 a = sorted_allocnos[n];
781 ALLOCNO_NEXT_BUCKET_ALLOCNO (a) = head;
782 ALLOCNO_PREV_BUCKET_ALLOCNO (a) = NULL;
784 ALLOCNO_PREV_BUCKET_ALLOCNO (head) = a;
790 /* Add ALLOCNO to bucket *BUCKET_PTR maintaining the order according
791 their priority. ALLOCNO should be not in a bucket before the
794 add_allocno_to_ordered_bucket (ira_allocno_t allocno,
795 ira_allocno_t *bucket_ptr)
797 ira_allocno_t before, after;
798 enum reg_class cover_class;
800 if (bucket_ptr == &uncolorable_allocno_bucket
801 && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
803 uncolorable_allocnos_num[cover_class]++;
804 ira_assert (uncolorable_allocnos_num[cover_class] > 0);
806 for (before = *bucket_ptr, after = NULL;
808 after = before, before = ALLOCNO_NEXT_BUCKET_ALLOCNO (before))
809 if (bucket_allocno_compare_func (&allocno, &before) < 0)
811 ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno) = before;
812 ALLOCNO_PREV_BUCKET_ALLOCNO (allocno) = after;
814 *bucket_ptr = allocno;
816 ALLOCNO_NEXT_BUCKET_ALLOCNO (after) = allocno;
818 ALLOCNO_PREV_BUCKET_ALLOCNO (before) = allocno;
821 /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
824 delete_allocno_from_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
826 ira_allocno_t prev_allocno, next_allocno;
827 enum reg_class cover_class;
829 if (bucket_ptr == &uncolorable_allocno_bucket
830 && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
832 uncolorable_allocnos_num[cover_class]--;
833 ira_assert (uncolorable_allocnos_num[cover_class] >= 0);
835 prev_allocno = ALLOCNO_PREV_BUCKET_ALLOCNO (allocno);
836 next_allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno);
837 if (prev_allocno != NULL)
838 ALLOCNO_NEXT_BUCKET_ALLOCNO (prev_allocno) = next_allocno;
841 ira_assert (*bucket_ptr == allocno);
842 *bucket_ptr = next_allocno;
844 if (next_allocno != NULL)
845 ALLOCNO_PREV_BUCKET_ALLOCNO (next_allocno) = prev_allocno;
848 /* Splay tree for each cover class. The trees are indexed by the
849 corresponding cover classes. Splay trees contain uncolorable
851 static splay_tree uncolorable_allocnos_splay_tree[N_REG_CLASSES];
853 /* If the following macro is TRUE, splay tree is used to choose an
854 allocno of the corresponding cover class for spilling. When the
855 number uncolorable allocnos of given cover class decreases to some
856 threshold, linear array search is used to find the best allocno for
857 spilling. This threshold is actually pretty big because, although
858 splay trees asymptotically is much faster, each splay tree
859 operation is sufficiently costly especially taking cache locality
861 #define USE_SPLAY_P(CLASS) (uncolorable_allocnos_num[CLASS] > 4000)
863 /* Put ALLOCNO onto the coloring stack without removing it from its
864 bucket. Pushing allocno to the coloring stack can result in moving
865 conflicting allocnos from the uncolorable bucket to the colorable
868 push_allocno_to_stack (ira_allocno_t allocno)
870 int conflicts_num, conflict_size, size;
871 ira_allocno_t a, conflict_allocno;
872 enum reg_class cover_class;
873 ira_allocno_conflict_iterator aci;
875 ALLOCNO_IN_GRAPH_P (allocno) = false;
876 VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, allocno);
877 cover_class = ALLOCNO_COVER_CLASS (allocno);
878 if (cover_class == NO_REGS)
880 size = ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)];
881 if (allocno_coalesced_p)
882 bitmap_clear (processed_coalesced_allocno_bitmap);
883 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
884 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
886 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
888 conflict_allocno = ALLOCNO_FIRST_COALESCED_ALLOCNO (conflict_allocno);
889 if (bitmap_bit_p (coloring_allocno_bitmap,
890 ALLOCNO_NUM (conflict_allocno)))
892 ira_assert (cover_class
893 == ALLOCNO_COVER_CLASS (conflict_allocno));
894 if (allocno_coalesced_p)
896 if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
897 ALLOCNO_NUM (conflict_allocno)))
899 bitmap_set_bit (processed_coalesced_allocno_bitmap,
900 ALLOCNO_NUM (conflict_allocno));
902 if (ALLOCNO_IN_GRAPH_P (conflict_allocno)
903 && ! ALLOCNO_ASSIGNED_P (conflict_allocno))
905 conflicts_num = ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno);
907 = (ira_reg_class_nregs
908 [cover_class][ALLOCNO_MODE (conflict_allocno)]);
910 (ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) >= size);
911 if (conflicts_num + conflict_size
912 <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno))
914 ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) -= size;
918 = ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) - size;
919 if (uncolorable_allocnos_splay_tree[cover_class] != NULL
920 && !ALLOCNO_SPLAY_REMOVED_P (conflict_allocno)
921 && USE_SPLAY_P (cover_class))
925 (uncolorable_allocnos_splay_tree[cover_class],
926 (splay_tree_key) conflict_allocno) != NULL);
928 (uncolorable_allocnos_splay_tree[cover_class],
929 (splay_tree_key) conflict_allocno);
930 ALLOCNO_SPLAY_REMOVED_P (conflict_allocno) = true;
931 VEC_safe_push (ira_allocno_t, heap,
932 removed_splay_allocno_vec,
935 ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) = conflicts_num;
936 if (conflicts_num + conflict_size
937 <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno))
939 delete_allocno_from_bucket
940 (conflict_allocno, &uncolorable_allocno_bucket);
941 add_allocno_to_ordered_bucket
942 (conflict_allocno, &colorable_allocno_bucket);
952 /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
953 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
955 remove_allocno_from_bucket_and_push (ira_allocno_t allocno, bool colorable_p)
957 enum reg_class cover_class;
960 delete_allocno_from_bucket (allocno, &colorable_allocno_bucket);
962 delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
963 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
965 fprintf (ira_dump_file, " Pushing");
966 print_coalesced_allocno (allocno);
968 fprintf (ira_dump_file, "\n");
970 fprintf (ira_dump_file, "(potential spill: %spri=%d, cost=%d)\n",
971 ALLOCNO_BAD_SPILL_P (allocno) ? "bad spill, " : "",
972 allocno_spill_priority (allocno), ALLOCNO_TEMP (allocno));
974 cover_class = ALLOCNO_COVER_CLASS (allocno);
975 ira_assert ((colorable_p
976 && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
977 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)]
978 <= ALLOCNO_AVAILABLE_REGS_NUM (allocno)))
980 && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
981 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE
983 > ALLOCNO_AVAILABLE_REGS_NUM (allocno))));
985 ALLOCNO_MAY_BE_SPILLED_P (allocno) = true;
986 push_allocno_to_stack (allocno);
989 /* Put all allocnos from colorable bucket onto the coloring stack. */
991 push_only_colorable (void)
993 sort_bucket (&colorable_allocno_bucket);
994 for (;colorable_allocno_bucket != NULL;)
995 remove_allocno_from_bucket_and_push (colorable_allocno_bucket, true);
998 /* Puts ALLOCNO chosen for potential spilling onto the coloring
1001 push_allocno_to_spill (ira_allocno_t allocno)
1003 delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
1004 ALLOCNO_MAY_BE_SPILLED_P (allocno) = true;
1005 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1006 fprintf (ira_dump_file, " Pushing p%d(%d) (spill for NO_REGS)\n",
1007 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno));
1008 push_allocno_to_stack (allocno);
1011 /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
1012 loop given by its LOOP_NODE. */
1014 ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p)
1019 VEC (edge, heap) *edges;
1021 ira_assert (loop_node->loop != NULL
1022 && (regno < 0 || regno >= FIRST_PSEUDO_REGISTER));
1026 FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
1027 if (e->src != loop_node->loop->latch
1029 || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
1030 && bitmap_bit_p (DF_LR_IN (e->dest), regno))))
1031 freq += EDGE_FREQUENCY (e);
1035 edges = get_loop_exit_edges (loop_node->loop);
1036 for (i = 0; VEC_iterate (edge, edges, i, e); i++)
1038 || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
1039 && bitmap_bit_p (DF_LR_IN (e->dest), regno)))
1040 freq += EDGE_FREQUENCY (e);
1041 VEC_free (edge, heap, edges);
1044 return REG_FREQ_FROM_EDGE_FREQ (freq);
1047 /* Calculate and return the cost of putting allocno A into memory. */
1049 calculate_allocno_spill_cost (ira_allocno_t a)
1052 enum machine_mode mode;
1053 enum reg_class rclass;
1054 ira_allocno_t parent_allocno;
1055 ira_loop_tree_node_t parent_node, loop_node;
1057 regno = ALLOCNO_REGNO (a);
1058 cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_UPDATED_COVER_CLASS_COST (a);
1059 if (ALLOCNO_CAP (a) != NULL)
1061 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
1062 if ((parent_node = loop_node->parent) == NULL)
1064 if ((parent_allocno = parent_node->regno_allocno_map[regno]) == NULL)
1066 mode = ALLOCNO_MODE (a);
1067 rclass = ALLOCNO_COVER_CLASS (a);
1068 if (ALLOCNO_HARD_REGNO (parent_allocno) < 0)
1069 cost -= (ira_memory_move_cost[mode][rclass][0]
1070 * ira_loop_edge_freq (loop_node, regno, true)
1071 + ira_memory_move_cost[mode][rclass][1]
1072 * ira_loop_edge_freq (loop_node, regno, false));
1074 cost += ((ira_memory_move_cost[mode][rclass][1]
1075 * ira_loop_edge_freq (loop_node, regno, true)
1076 + ira_memory_move_cost[mode][rclass][0]
1077 * ira_loop_edge_freq (loop_node, regno, false))
1078 - (ira_get_register_move_cost (mode, rclass, rclass)
1079 * (ira_loop_edge_freq (loop_node, regno, false)
1080 + ira_loop_edge_freq (loop_node, regno, true))));
1084 /* Compare keys in the splay tree used to choose best allocno for
1085 spilling. The best allocno has the minimal key. */
1087 allocno_spill_priority_compare (splay_tree_key k1, splay_tree_key k2)
1089 int pri1, pri2, diff;
1090 ira_allocno_t a1 = (ira_allocno_t) k1, a2 = (ira_allocno_t) k2;
1092 pri1 = (ALLOCNO_TEMP (a1)
1093 / (ALLOCNO_LEFT_CONFLICTS_NUM (a1)
1094 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a1)][ALLOCNO_MODE (a1)]
1096 pri2 = (ALLOCNO_TEMP (a2)
1097 / (ALLOCNO_LEFT_CONFLICTS_NUM (a2)
1098 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a2)][ALLOCNO_MODE (a2)]
1100 if ((diff = pri1 - pri2) != 0)
1102 if ((diff = ALLOCNO_TEMP (a1) - ALLOCNO_TEMP (a2)) != 0)
1104 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
1107 /* Allocate data of SIZE for the splay trees. We allocate only spay
1108 tree roots or splay tree nodes. If you change this, please rewrite
1111 splay_tree_allocate (int size, void *data ATTRIBUTE_UNUSED)
1113 if (size != sizeof (struct splay_tree_node_s))
1114 return ira_allocate (size);
1115 return pool_alloc (splay_tree_node_pool);
1118 /* Free data NODE for the splay trees. We allocate and free only spay
1119 tree roots or splay tree nodes. If you change this, please rewrite
1122 splay_tree_free (void *node, void *data ATTRIBUTE_UNUSED)
1125 enum reg_class cover_class;
1127 for (i = 0; i < ira_reg_class_cover_size; i++)
1129 cover_class = ira_reg_class_cover[i];
1130 if (node == uncolorable_allocnos_splay_tree[cover_class])
1136 pool_free (splay_tree_node_pool, node);
1139 /* Push allocnos to the coloring stack. The order of allocnos in the
1140 stack defines the order for the subsequent coloring. */
1142 push_allocnos_to_stack (void)
1144 ira_allocno_t allocno, a, i_allocno, *allocno_vec;
1145 enum reg_class cover_class, rclass;
1146 int allocno_pri, i_allocno_pri, allocno_cost, i_allocno_cost;
1147 int i, j, num, cover_class_allocnos_num[N_REG_CLASSES];
1148 ira_allocno_t *cover_class_allocnos[N_REG_CLASSES];
1152 VEC_truncate(ira_allocno_t, removed_splay_allocno_vec, 0);
1153 for (i = 0; i < ira_reg_class_cover_size; i++)
1155 cover_class = ira_reg_class_cover[i];
1156 cover_class_allocnos_num[cover_class] = 0;
1157 cover_class_allocnos[cover_class] = NULL;
1158 uncolorable_allocnos_splay_tree[cover_class] = NULL;
1160 /* Calculate uncolorable allocno spill costs. */
1161 for (allocno = uncolorable_allocno_bucket;
1163 allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno))
1164 if ((cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
1166 cover_class_allocnos_num[cover_class]++;
1168 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1169 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1171 cost += calculate_allocno_spill_cost (a);
1175 /* ??? Remove cost of copies between the coalesced
1177 ALLOCNO_TEMP (allocno) = cost;
1179 /* Define place where to put uncolorable allocnos of the same cover
1181 for (num = i = 0; i < ira_reg_class_cover_size; i++)
1183 cover_class = ira_reg_class_cover[i];
1184 ira_assert (cover_class_allocnos_num[cover_class]
1185 == uncolorable_allocnos_num[cover_class]);
1186 if (cover_class_allocnos_num[cover_class] != 0)
1188 cover_class_allocnos[cover_class] = allocnos_for_spilling + num;
1189 num += cover_class_allocnos_num[cover_class];
1190 cover_class_allocnos_num[cover_class] = 0;
1192 if (USE_SPLAY_P (cover_class))
1193 uncolorable_allocnos_splay_tree[cover_class]
1194 = splay_tree_new_with_allocator (allocno_spill_priority_compare,
1195 NULL, NULL, splay_tree_allocate,
1196 splay_tree_free, NULL);
1198 ira_assert (num <= ira_allocnos_num);
1199 /* Collect uncolorable allocnos of each cover class. */
1200 for (allocno = uncolorable_allocno_bucket;
1202 allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno))
1203 if ((cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
1205 cover_class_allocnos
1206 [cover_class][cover_class_allocnos_num[cover_class]++] = allocno;
1207 if (uncolorable_allocnos_splay_tree[cover_class] != NULL)
1208 splay_tree_insert (uncolorable_allocnos_splay_tree[cover_class],
1209 (splay_tree_key) allocno,
1210 (splay_tree_value) allocno);
1214 push_only_colorable ();
1215 allocno = uncolorable_allocno_bucket;
1216 if (allocno == NULL)
1218 cover_class = ALLOCNO_COVER_CLASS (allocno);
1219 if (cover_class == NO_REGS)
1221 push_allocno_to_spill (allocno);
1224 /* Potential spilling. */
1226 (ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)] > 0);
1227 if (USE_SPLAY_P (cover_class))
1229 for (;VEC_length (ira_allocno_t, removed_splay_allocno_vec) != 0;)
1231 allocno = VEC_pop (ira_allocno_t, removed_splay_allocno_vec);
1232 ALLOCNO_SPLAY_REMOVED_P (allocno) = false;
1233 rclass = ALLOCNO_COVER_CLASS (allocno);
1234 if (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
1235 + ira_reg_class_nregs [rclass][ALLOCNO_MODE (allocno)]
1236 > ALLOCNO_AVAILABLE_REGS_NUM (allocno))
1238 (uncolorable_allocnos_splay_tree[rclass],
1239 (splay_tree_key) allocno, (splay_tree_value) allocno);
1241 allocno = ((ira_allocno_t)
1243 (uncolorable_allocnos_splay_tree[cover_class])->key);
1244 splay_tree_remove (uncolorable_allocnos_splay_tree[cover_class],
1245 (splay_tree_key) allocno);
1249 num = cover_class_allocnos_num[cover_class];
1250 ira_assert (num > 0);
1251 allocno_vec = cover_class_allocnos[cover_class];
1253 allocno_pri = allocno_cost = 0;
1254 /* Sort uncolorable allocno to find the one with the lowest
1256 for (i = 0, j = num - 1; i <= j;)
1258 i_allocno = allocno_vec[i];
1259 if (! ALLOCNO_IN_GRAPH_P (i_allocno)
1260 && ALLOCNO_IN_GRAPH_P (allocno_vec[j]))
1262 i_allocno = allocno_vec[j];
1263 allocno_vec[j] = allocno_vec[i];
1264 allocno_vec[i] = i_allocno;
1266 if (ALLOCNO_IN_GRAPH_P (i_allocno))
1269 ira_assert (ALLOCNO_TEMP (i_allocno) != INT_MAX);
1270 i_allocno_cost = ALLOCNO_TEMP (i_allocno);
1271 i_allocno_pri = allocno_spill_priority (i_allocno);
1273 || (! ALLOCNO_BAD_SPILL_P (i_allocno)
1274 && ALLOCNO_BAD_SPILL_P (allocno))
1275 || (! (ALLOCNO_BAD_SPILL_P (i_allocno)
1276 && ! ALLOCNO_BAD_SPILL_P (allocno))
1277 && (allocno_pri > i_allocno_pri
1278 || (allocno_pri == i_allocno_pri
1279 && (allocno_cost > i_allocno_cost
1280 || (allocno_cost == i_allocno_cost
1281 && (ALLOCNO_NUM (allocno)
1282 > ALLOCNO_NUM (i_allocno))))))))
1284 allocno = i_allocno;
1285 allocno_cost = i_allocno_cost;
1286 allocno_pri = i_allocno_pri;
1289 if (! ALLOCNO_IN_GRAPH_P (allocno_vec[j]))
1292 ira_assert (allocno != NULL && j >= 0);
1293 cover_class_allocnos_num[cover_class] = j + 1;
1295 ira_assert (ALLOCNO_IN_GRAPH_P (allocno)
1296 && ALLOCNO_COVER_CLASS (allocno) == cover_class
1297 && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
1298 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE
1300 > ALLOCNO_AVAILABLE_REGS_NUM (allocno)));
1301 remove_allocno_from_bucket_and_push (allocno, false);
1303 ira_assert (colorable_allocno_bucket == NULL
1304 && uncolorable_allocno_bucket == NULL);
1305 for (i = 0; i < ira_reg_class_cover_size; i++)
1307 cover_class = ira_reg_class_cover[i];
1308 ira_assert (uncolorable_allocnos_num[cover_class] == 0);
1309 if (uncolorable_allocnos_splay_tree[cover_class] != NULL)
1310 splay_tree_delete (uncolorable_allocnos_splay_tree[cover_class]);
1314 /* Pop the coloring stack and assign hard registers to the popped
1317 pop_allocnos_from_stack (void)
1319 ira_allocno_t allocno;
1320 enum reg_class cover_class;
1322 for (;VEC_length (ira_allocno_t, allocno_stack_vec) != 0;)
1324 allocno = VEC_pop (ira_allocno_t, allocno_stack_vec);
1325 cover_class = ALLOCNO_COVER_CLASS (allocno);
1326 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1328 fprintf (ira_dump_file, " Popping");
1329 print_coalesced_allocno (allocno);
1330 fprintf (ira_dump_file, " -- ");
1332 if (cover_class == NO_REGS)
1334 ALLOCNO_HARD_REGNO (allocno) = -1;
1335 ALLOCNO_ASSIGNED_P (allocno) = true;
1336 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno) == NULL);
1338 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno) == NULL);
1339 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1340 fprintf (ira_dump_file, "assign memory\n");
1342 else if (assign_hard_reg (allocno, false))
1344 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1345 fprintf (ira_dump_file, "assign reg %d\n",
1346 ALLOCNO_HARD_REGNO (allocno));
1348 else if (ALLOCNO_ASSIGNED_P (allocno))
1350 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1351 fprintf (ira_dump_file, "spill\n");
1353 ALLOCNO_IN_GRAPH_P (allocno) = true;
1357 /* Set up number of available hard registers for ALLOCNO. */
1359 setup_allocno_available_regs_num (ira_allocno_t allocno)
1361 int i, n, hard_regs_num;
1362 enum reg_class cover_class;
1364 HARD_REG_SET temp_set;
1366 cover_class = ALLOCNO_COVER_CLASS (allocno);
1367 ALLOCNO_AVAILABLE_REGS_NUM (allocno) = ira_available_class_regs[cover_class];
1368 if (cover_class == NO_REGS)
1370 CLEAR_HARD_REG_SET (temp_set);
1371 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) == allocno);
1372 hard_regs_num = ira_class_hard_regs_num[cover_class];
1373 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1374 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1376 IOR_HARD_REG_SET (temp_set, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1380 for (n = 0, i = hard_regs_num - 1; i >= 0; i--)
1381 if (TEST_HARD_REG_BIT (temp_set, ira_class_hard_regs[cover_class][i]))
1383 if (internal_flag_ira_verbose > 2 && n > 0 && ira_dump_file != NULL)
1384 fprintf (ira_dump_file, " Reg %d of %s has %d regs less\n",
1385 ALLOCNO_REGNO (allocno), reg_class_names[cover_class], n);
1386 ALLOCNO_AVAILABLE_REGS_NUM (allocno) -= n;
1389 /* Set up ALLOCNO_LEFT_CONFLICTS_NUM for ALLOCNO. */
1391 setup_allocno_left_conflicts_num (ira_allocno_t allocno)
1393 int i, hard_regs_num, hard_regno, conflict_allocnos_size;
1394 ira_allocno_t a, conflict_allocno;
1395 enum reg_class cover_class;
1396 HARD_REG_SET temp_set;
1397 ira_allocno_conflict_iterator aci;
1399 cover_class = ALLOCNO_COVER_CLASS (allocno);
1400 hard_regs_num = ira_class_hard_regs_num[cover_class];
1401 CLEAR_HARD_REG_SET (temp_set);
1402 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) == allocno);
1403 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1404 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1406 IOR_HARD_REG_SET (temp_set, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1410 AND_HARD_REG_SET (temp_set, reg_class_contents[cover_class]);
1411 AND_COMPL_HARD_REG_SET (temp_set, ira_no_alloc_regs);
1412 conflict_allocnos_size = 0;
1413 if (! hard_reg_set_empty_p (temp_set))
1414 for (i = 0; i < (int) hard_regs_num; i++)
1416 hard_regno = ira_class_hard_regs[cover_class][i];
1417 if (TEST_HARD_REG_BIT (temp_set, hard_regno))
1419 conflict_allocnos_size++;
1420 CLEAR_HARD_REG_BIT (temp_set, hard_regno);
1421 if (hard_reg_set_empty_p (temp_set))
1425 CLEAR_HARD_REG_SET (temp_set);
1426 if (allocno_coalesced_p)
1427 bitmap_clear (processed_coalesced_allocno_bitmap);
1428 if (cover_class != NO_REGS)
1429 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1430 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1432 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
1435 = ALLOCNO_FIRST_COALESCED_ALLOCNO (conflict_allocno);
1436 if (bitmap_bit_p (consideration_allocno_bitmap,
1437 ALLOCNO_NUM (conflict_allocno)))
1439 ira_assert (cover_class
1440 == ALLOCNO_COVER_CLASS (conflict_allocno));
1441 if (allocno_coalesced_p)
1443 if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
1444 ALLOCNO_NUM (conflict_allocno)))
1446 bitmap_set_bit (processed_coalesced_allocno_bitmap,
1447 ALLOCNO_NUM (conflict_allocno));
1449 if (! ALLOCNO_ASSIGNED_P (conflict_allocno))
1450 conflict_allocnos_size
1451 += (ira_reg_class_nregs
1452 [cover_class][ALLOCNO_MODE (conflict_allocno)]);
1453 else if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno))
1456 int last = (hard_regno
1458 [hard_regno][ALLOCNO_MODE (conflict_allocno)]);
1460 while (hard_regno < last)
1462 if (! TEST_HARD_REG_BIT (temp_set, hard_regno))
1464 conflict_allocnos_size++;
1465 SET_HARD_REG_BIT (temp_set, hard_regno);
1475 ALLOCNO_LEFT_CONFLICTS_NUM (allocno) = conflict_allocnos_size;
1478 /* Put ALLOCNO in a bucket corresponding to its number and size of its
1479 conflicting allocnos and hard registers. */
1481 put_allocno_into_bucket (ira_allocno_t allocno)
1484 enum reg_class cover_class;
1486 cover_class = ALLOCNO_COVER_CLASS (allocno);
1487 hard_regs_num = ira_class_hard_regs_num[cover_class];
1488 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
1490 ALLOCNO_IN_GRAPH_P (allocno) = true;
1491 setup_allocno_left_conflicts_num (allocno);
1492 setup_allocno_available_regs_num (allocno);
1493 if (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
1494 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)]
1495 <= ALLOCNO_AVAILABLE_REGS_NUM (allocno))
1496 add_allocno_to_bucket (allocno, &colorable_allocno_bucket);
1498 add_allocno_to_bucket (allocno, &uncolorable_allocno_bucket);
1501 /* The function is used to sort allocnos according to their execution
1504 copy_freq_compare_func (const void *v1p, const void *v2p)
1506 ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p;
1514 /* If freqencies are equal, sort by copies, so that the results of
1515 qsort leave nothing to chance. */
1516 return cp1->num - cp2->num;
1519 /* Merge two sets of coalesced allocnos given correspondingly by
1520 allocnos A1 and A2 (more accurately merging A2 set into A1
1523 merge_allocnos (ira_allocno_t a1, ira_allocno_t a2)
1525 ira_allocno_t a, first, last, next;
1527 first = ALLOCNO_FIRST_COALESCED_ALLOCNO (a1);
1528 if (first == ALLOCNO_FIRST_COALESCED_ALLOCNO (a2))
1530 for (last = a2, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
1531 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1533 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = first;
1538 next = ALLOCNO_NEXT_COALESCED_ALLOCNO (first);
1539 ALLOCNO_NEXT_COALESCED_ALLOCNO (first) = a2;
1540 ALLOCNO_NEXT_COALESCED_ALLOCNO (last) = next;
1543 /* Return TRUE if there are conflicting allocnos from two sets of
1544 coalesced allocnos given correspondingly by allocnos A1 and A2. If
1545 RELOAD_P is TRUE, we use live ranges to find conflicts because
1546 conflicts are represented only for allocnos of the same cover class
1547 and during the reload pass we coalesce allocnos for sharing stack
1550 coalesced_allocno_conflict_p (ira_allocno_t a1, ira_allocno_t a2,
1553 ira_allocno_t a, conflict_allocno;
1554 ira_allocno_conflict_iterator aci;
1556 if (allocno_coalesced_p)
1558 bitmap_clear (processed_coalesced_allocno_bitmap);
1559 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
1560 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1562 bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a));
1567 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
1568 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1572 for (conflict_allocno = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
1574 = ALLOCNO_NEXT_COALESCED_ALLOCNO (conflict_allocno))
1576 if (allocnos_have_intersected_live_ranges_p (a,
1579 if (conflict_allocno == a1)
1585 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
1586 if (conflict_allocno == a1
1587 || (allocno_coalesced_p
1588 && bitmap_bit_p (processed_coalesced_allocno_bitmap,
1589 ALLOCNO_NUM (conflict_allocno))))
1598 /* The major function for aggressive allocno coalescing. For the
1599 reload pass (RELOAD_P) we coalesce only spilled allocnos. If some
1600 allocnos have been coalesced, we set up flag
1601 allocno_coalesced_p. */
1603 coalesce_allocnos (bool reload_p)
1606 ira_copy_t cp, next_cp, *sorted_copies;
1607 enum reg_class cover_class;
1608 enum machine_mode mode;
1610 int i, n, cp_num, regno;
1613 sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num
1614 * sizeof (ira_copy_t));
1616 /* Collect copies. */
1617 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
1619 a = ira_allocnos[j];
1620 regno = ALLOCNO_REGNO (a);
1621 if ((! reload_p && ALLOCNO_ASSIGNED_P (a))
1623 && (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0
1624 || (regno < ira_reg_equiv_len
1625 && (ira_reg_equiv_const[regno] != NULL_RTX
1626 || ira_reg_equiv_invariant_p[regno])))))
1628 cover_class = ALLOCNO_COVER_CLASS (a);
1629 mode = ALLOCNO_MODE (a);
1630 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
1634 next_cp = cp->next_first_allocno_copy;
1635 regno = ALLOCNO_REGNO (cp->second);
1636 /* For priority coloring we coalesce allocnos only with
1637 the same cover class not with intersected cover
1638 classes as it were possible. It is done for
1641 || (ALLOCNO_COVER_CLASS (cp->second) == cover_class
1642 && ALLOCNO_MODE (cp->second) == mode))
1643 && (cp->insn != NULL || cp->constraint_p)
1644 && ((! reload_p && ! ALLOCNO_ASSIGNED_P (cp->second))
1646 && ALLOCNO_ASSIGNED_P (cp->second)
1647 && ALLOCNO_HARD_REGNO (cp->second) < 0
1648 && (regno >= ira_reg_equiv_len
1649 || (! ira_reg_equiv_invariant_p[regno]
1650 && ira_reg_equiv_const[regno] == NULL_RTX)))))
1651 sorted_copies[cp_num++] = cp;
1653 else if (cp->second == a)
1654 next_cp = cp->next_second_allocno_copy;
1659 qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
1660 /* Coalesced copies, most frequently executed first. */
1661 for (; cp_num != 0;)
1663 for (i = 0; i < cp_num; i++)
1665 cp = sorted_copies[i];
1666 if (! coalesced_allocno_conflict_p (cp->first, cp->second, reload_p))
1668 allocno_coalesced_p = true;
1669 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1672 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
1673 cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
1674 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
1676 merge_allocnos (cp->first, cp->second);
1681 /* Collect the rest of copies. */
1682 for (n = 0; i < cp_num; i++)
1684 cp = sorted_copies[i];
1685 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->first)
1686 != ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->second))
1687 sorted_copies[n++] = cp;
1691 ira_free (sorted_copies);
1694 /* Map: allocno number -> allocno priority. */
1695 static int *allocno_priorities;
1697 /* Set up priorities for N allocnos in array
1698 CONSIDERATION_ALLOCNOS. */
1700 setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
1702 int i, length, nrefs, priority, max_priority, mult;
1706 for (i = 0; i < n; i++)
1708 a = consideration_allocnos[i];
1709 nrefs = ALLOCNO_NREFS (a);
1710 ira_assert (nrefs >= 0);
1711 mult = floor_log2 (ALLOCNO_NREFS (a)) + 1;
1712 ira_assert (mult >= 0);
1713 allocno_priorities[ALLOCNO_NUM (a)]
1716 * (ALLOCNO_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a))
1717 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a)][ALLOCNO_MODE (a)]);
1719 priority = -priority;
1720 if (max_priority < priority)
1721 max_priority = priority;
1723 mult = max_priority == 0 ? 1 : INT_MAX / max_priority;
1724 for (i = 0; i < n; i++)
1726 a = consideration_allocnos[i];
1727 length = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
1730 allocno_priorities[ALLOCNO_NUM (a)]
1731 = allocno_priorities[ALLOCNO_NUM (a)] * mult / length;
1735 /* Sort allocnos according to their priorities which are calculated
1736 analogous to ones in file `global.c'. */
1738 allocno_priority_compare_func (const void *v1p, const void *v2p)
1740 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
1741 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
1744 pri1 = allocno_priorities[ALLOCNO_NUM (a1)];
1745 pri2 = allocno_priorities[ALLOCNO_NUM (a2)];
1747 return SORTGT (pri2, pri1);
1749 /* If regs are equally good, sort by allocnos, so that the results of
1750 qsort leave nothing to chance. */
1751 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
1754 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
1755 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
1757 color_allocnos (void)
1763 allocno_coalesced_p = false;
1764 processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
1765 if (flag_ira_coalesce)
1766 coalesce_allocnos (false);
1767 if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
1770 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1772 a = ira_allocnos[i];
1773 if (ALLOCNO_COVER_CLASS (a) == NO_REGS)
1775 ALLOCNO_HARD_REGNO (a) = -1;
1776 ALLOCNO_ASSIGNED_P (a) = true;
1777 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
1778 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
1779 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1781 fprintf (ira_dump_file, " Spill");
1782 print_coalesced_allocno (a);
1783 fprintf (ira_dump_file, "\n");
1787 sorted_allocnos[n++] = a;
1791 setup_allocno_priorities (sorted_allocnos, n);
1792 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
1793 allocno_priority_compare_func);
1794 for (i = 0; i < n; i++)
1796 a = sorted_allocnos[i];
1797 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1799 fprintf (ira_dump_file, " ");
1800 print_coalesced_allocno (a);
1801 fprintf (ira_dump_file, " -- ");
1803 if (assign_hard_reg (a, false))
1805 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1806 fprintf (ira_dump_file, "assign hard reg %d\n",
1807 ALLOCNO_HARD_REGNO (a));
1811 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1812 fprintf (ira_dump_file, "assign memory\n");
1819 /* Put the allocnos into the corresponding buckets. */
1820 colorable_allocno_bucket = NULL;
1821 uncolorable_allocno_bucket = NULL;
1822 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1824 a = ira_allocnos[i];
1825 if (ALLOCNO_COVER_CLASS (a) == NO_REGS)
1827 ALLOCNO_HARD_REGNO (a) = -1;
1828 ALLOCNO_ASSIGNED_P (a) = true;
1829 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
1830 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
1831 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1833 fprintf (ira_dump_file, " Spill");
1834 print_coalesced_allocno (a);
1835 fprintf (ira_dump_file, "\n");
1839 put_allocno_into_bucket (a);
1841 push_allocnos_to_stack ();
1842 pop_allocnos_from_stack ();
1844 if (flag_ira_coalesce)
1845 /* We don't need coalesced allocnos for ira_reassign_pseudos. */
1846 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1848 a = ira_allocnos[i];
1849 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
1850 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
1852 ira_free_bitmap (processed_coalesced_allocno_bitmap);
1853 allocno_coalesced_p = false;
1858 /* Output information about the loop given by its LOOP_TREE_NODE. */
1860 print_loop_title (ira_loop_tree_node_t loop_tree_node)
1864 ira_loop_tree_node_t subloop_node, dest_loop_node;
1868 ira_assert (loop_tree_node->loop != NULL);
1869 fprintf (ira_dump_file,
1870 "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
1871 loop_tree_node->loop->num,
1872 (loop_tree_node->parent == NULL
1873 ? -1 : loop_tree_node->parent->loop->num),
1874 loop_tree_node->loop->header->index,
1875 loop_depth (loop_tree_node->loop));
1876 for (subloop_node = loop_tree_node->children;
1877 subloop_node != NULL;
1878 subloop_node = subloop_node->next)
1879 if (subloop_node->bb != NULL)
1881 fprintf (ira_dump_file, " %d", subloop_node->bb->index);
1882 FOR_EACH_EDGE (e, ei, subloop_node->bb->succs)
1883 if (e->dest != EXIT_BLOCK_PTR
1884 && ((dest_loop_node = IRA_BB_NODE (e->dest)->parent)
1886 fprintf (ira_dump_file, "(->%d:l%d)",
1887 e->dest->index, dest_loop_node->loop->num);
1889 fprintf (ira_dump_file, "\n all:");
1890 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
1891 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
1892 fprintf (ira_dump_file, "\n modified regnos:");
1893 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->modified_regnos, 0, j, bi)
1894 fprintf (ira_dump_file, " %d", j);
1895 fprintf (ira_dump_file, "\n border:");
1896 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->border_allocnos, 0, j, bi)
1897 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
1898 fprintf (ira_dump_file, "\n Pressure:");
1899 for (j = 0; (int) j < ira_reg_class_cover_size; j++)
1901 enum reg_class cover_class;
1903 cover_class = ira_reg_class_cover[j];
1904 if (loop_tree_node->reg_pressure[cover_class] == 0)
1906 fprintf (ira_dump_file, " %s=%d", reg_class_names[cover_class],
1907 loop_tree_node->reg_pressure[cover_class]);
1909 fprintf (ira_dump_file, "\n");
1912 /* Color the allocnos inside loop (in the extreme case it can be all
1913 of the function) given the corresponding LOOP_TREE_NODE. The
1914 function is called for each loop during top-down traverse of the
1917 color_pass (ira_loop_tree_node_t loop_tree_node)
1919 int regno, hard_regno, index = -1;
1920 int cost, exit_freq, enter_freq;
1923 enum machine_mode mode;
1924 enum reg_class rclass, cover_class;
1925 ira_allocno_t a, subloop_allocno;
1926 ira_loop_tree_node_t subloop_node;
1928 ira_assert (loop_tree_node->bb == NULL);
1929 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1930 print_loop_title (loop_tree_node);
1932 bitmap_copy (coloring_allocno_bitmap, loop_tree_node->all_allocnos);
1933 bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap);
1934 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
1936 a = ira_allocnos[j];
1937 if (! ALLOCNO_ASSIGNED_P (a))
1939 bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a));
1941 /* Color all mentioned allocnos including transparent ones. */
1943 /* Process caps. They are processed just once. */
1944 if (flag_ira_region == IRA_REGION_MIXED
1945 || flag_ira_region == IRA_REGION_ALL)
1946 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
1948 a = ira_allocnos[j];
1949 if (ALLOCNO_CAP_MEMBER (a) == NULL)
1951 /* Remove from processing in the next loop. */
1952 bitmap_clear_bit (consideration_allocno_bitmap, j);
1953 rclass = ALLOCNO_COVER_CLASS (a);
1954 if (flag_ira_region == IRA_REGION_MIXED
1955 && (loop_tree_node->reg_pressure[rclass]
1956 <= ira_available_class_regs[rclass]))
1958 mode = ALLOCNO_MODE (a);
1959 hard_regno = ALLOCNO_HARD_REGNO (a);
1960 if (hard_regno >= 0)
1962 index = ira_class_hard_reg_index[rclass][hard_regno];
1963 ira_assert (index >= 0);
1965 regno = ALLOCNO_REGNO (a);
1966 subloop_allocno = ALLOCNO_CAP_MEMBER (a);
1967 subloop_node = ALLOCNO_LOOP_TREE_NODE (subloop_allocno);
1968 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno));
1969 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
1970 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
1971 if (hard_regno >= 0)
1972 update_copy_costs (subloop_allocno, true);
1973 /* We don't need updated costs anymore: */
1974 ira_free_allocno_updated_costs (subloop_allocno);
1977 /* Update costs of the corresponding allocnos (not caps) in the
1979 for (subloop_node = loop_tree_node->subloops;
1980 subloop_node != NULL;
1981 subloop_node = subloop_node->subloop_next)
1983 ira_assert (subloop_node->bb == NULL);
1984 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
1986 a = ira_allocnos[j];
1987 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
1988 mode = ALLOCNO_MODE (a);
1989 rclass = ALLOCNO_COVER_CLASS (a);
1990 hard_regno = ALLOCNO_HARD_REGNO (a);
1991 /* Use hard register class here. ??? */
1992 if (hard_regno >= 0)
1994 index = ira_class_hard_reg_index[rclass][hard_regno];
1995 ira_assert (index >= 0);
1997 regno = ALLOCNO_REGNO (a);
1998 /* ??? conflict costs */
1999 subloop_allocno = subloop_node->regno_allocno_map[regno];
2000 if (subloop_allocno == NULL
2001 || ALLOCNO_CAP (subloop_allocno) != NULL)
2003 ira_assert (ALLOCNO_COVER_CLASS (subloop_allocno) == rclass);
2004 ira_assert (bitmap_bit_p (subloop_node->all_allocnos,
2005 ALLOCNO_NUM (subloop_allocno)));
2006 if ((flag_ira_region == IRA_REGION_MIXED)
2007 && (loop_tree_node->reg_pressure[rclass]
2008 <= ira_available_class_regs[rclass]))
2010 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
2012 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
2013 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
2014 if (hard_regno >= 0)
2015 update_copy_costs (subloop_allocno, true);
2016 /* We don't need updated costs anymore: */
2017 ira_free_allocno_updated_costs (subloop_allocno);
2021 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
2022 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
2023 ira_assert (regno < ira_reg_equiv_len);
2024 if (ira_reg_equiv_invariant_p[regno]
2025 || ira_reg_equiv_const[regno] != NULL_RTX)
2027 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
2029 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
2030 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
2031 if (hard_regno >= 0)
2032 update_copy_costs (subloop_allocno, true);
2033 /* We don't need updated costs anymore: */
2034 ira_free_allocno_updated_costs (subloop_allocno);
2037 else if (hard_regno < 0)
2039 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
2040 -= ((ira_memory_move_cost[mode][rclass][1] * enter_freq)
2041 + (ira_memory_move_cost[mode][rclass][0] * exit_freq));
2045 cover_class = ALLOCNO_COVER_CLASS (subloop_allocno);
2046 cost = (ira_get_register_move_cost (mode, rclass, rclass)
2047 * (exit_freq + enter_freq));
2048 ira_allocate_and_set_or_copy_costs
2049 (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno), cover_class,
2050 ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno),
2051 ALLOCNO_HARD_REG_COSTS (subloop_allocno));
2052 ira_allocate_and_set_or_copy_costs
2053 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno),
2055 ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno));
2056 ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
2057 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
2059 if (ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno)
2060 > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index])
2061 ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno)
2062 = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index];
2063 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
2064 += (ira_memory_move_cost[mode][rclass][0] * enter_freq
2065 + ira_memory_move_cost[mode][rclass][1] * exit_freq);
2071 /* Initialize the common data for coloring and calls functions to do
2072 Chaitin-Briggs and regional coloring. */
2076 coloring_allocno_bitmap = ira_allocate_bitmap ();
2077 allocnos_for_spilling
2078 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
2079 * ira_allocnos_num);
2080 splay_tree_node_pool = create_alloc_pool ("splay tree nodes",
2081 sizeof (struct splay_tree_node_s),
2083 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2084 fprintf (ira_dump_file, "\n**** Allocnos coloring:\n\n");
2086 ira_traverse_loop_tree (false, ira_loop_tree_root, color_pass, NULL);
2088 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2089 ira_print_disposition (ira_dump_file);
2091 free_alloc_pool (splay_tree_node_pool);
2092 ira_free_bitmap (coloring_allocno_bitmap);
2093 ira_free (allocnos_for_spilling);
2098 /* Move spill/restore code, which are to be generated in ira-emit.c,
2099 to less frequent points (if it is profitable) by reassigning some
2100 allocnos (in loop with subloops containing in another loop) to
2101 memory which results in longer live-range where the corresponding
2102 pseudo-registers will be in memory. */
2104 move_spill_restore (void)
2106 int cost, regno, hard_regno, hard_regno2, index;
2108 int enter_freq, exit_freq;
2109 enum machine_mode mode;
2110 enum reg_class rclass;
2111 ira_allocno_t a, parent_allocno, subloop_allocno;
2112 ira_loop_tree_node_t parent, loop_node, subloop_node;
2113 ira_allocno_iterator ai;
2118 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2119 fprintf (ira_dump_file, "New iteration of spill/restore move\n");
2120 FOR_EACH_ALLOCNO (a, ai)
2122 regno = ALLOCNO_REGNO (a);
2123 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
2124 if (ALLOCNO_CAP_MEMBER (a) != NULL
2125 || ALLOCNO_CAP (a) != NULL
2126 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0
2127 || loop_node->children == NULL
2128 /* don't do the optimization because it can create
2129 copies and the reload pass can spill the allocno set
2130 by copy although the allocno will not get memory
2132 || ira_reg_equiv_invariant_p[regno]
2133 || ira_reg_equiv_const[regno] != NULL_RTX
2134 || !bitmap_bit_p (loop_node->border_allocnos, ALLOCNO_NUM (a)))
2136 mode = ALLOCNO_MODE (a);
2137 rclass = ALLOCNO_COVER_CLASS (a);
2138 index = ira_class_hard_reg_index[rclass][hard_regno];
2139 ira_assert (index >= 0);
2140 cost = (ALLOCNO_MEMORY_COST (a)
2141 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
2142 ? ALLOCNO_COVER_CLASS_COST (a)
2143 : ALLOCNO_HARD_REG_COSTS (a)[index]));
2144 for (subloop_node = loop_node->subloops;
2145 subloop_node != NULL;
2146 subloop_node = subloop_node->subloop_next)
2148 ira_assert (subloop_node->bb == NULL);
2149 subloop_allocno = subloop_node->regno_allocno_map[regno];
2150 if (subloop_allocno == NULL)
2152 ira_assert (rclass == ALLOCNO_COVER_CLASS (subloop_allocno));
2153 /* We have accumulated cost. To get the real cost of
2154 allocno usage in the loop we should subtract costs of
2155 the subloop allocnos. */
2156 cost -= (ALLOCNO_MEMORY_COST (subloop_allocno)
2157 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno) == NULL
2158 ? ALLOCNO_COVER_CLASS_COST (subloop_allocno)
2159 : ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index]));
2160 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
2161 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
2162 if ((hard_regno2 = ALLOCNO_HARD_REGNO (subloop_allocno)) < 0)
2163 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
2164 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
2168 += (ira_memory_move_cost[mode][rclass][0] * exit_freq
2169 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
2170 if (hard_regno2 != hard_regno)
2171 cost -= (ira_get_register_move_cost (mode, rclass, rclass)
2172 * (exit_freq + enter_freq));
2175 if ((parent = loop_node->parent) != NULL
2176 && (parent_allocno = parent->regno_allocno_map[regno]) != NULL)
2178 ira_assert (rclass == ALLOCNO_COVER_CLASS (parent_allocno));
2179 exit_freq = ira_loop_edge_freq (loop_node, regno, true);
2180 enter_freq = ira_loop_edge_freq (loop_node, regno, false);
2181 if ((hard_regno2 = ALLOCNO_HARD_REGNO (parent_allocno)) < 0)
2182 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
2183 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
2187 += (ira_memory_move_cost[mode][rclass][1] * exit_freq
2188 + ira_memory_move_cost[mode][rclass][0] * enter_freq);
2189 if (hard_regno2 != hard_regno)
2190 cost -= (ira_get_register_move_cost (mode, rclass, rclass)
2191 * (exit_freq + enter_freq));
2196 ALLOCNO_HARD_REGNO (a) = -1;
2197 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2201 " Moving spill/restore for a%dr%d up from loop %d",
2202 ALLOCNO_NUM (a), regno, loop_node->loop->num);
2203 fprintf (ira_dump_file, " - profit %d\n", -cost);
2215 /* Update current hard reg costs and current conflict hard reg costs
2216 for allocno A. It is done by processing its copies containing
2217 other allocnos already assigned. */
2219 update_curr_costs (ira_allocno_t a)
2221 int i, hard_regno, cost;
2222 enum machine_mode mode;
2223 enum reg_class cover_class, rclass;
2224 ira_allocno_t another_a;
2225 ira_copy_t cp, next_cp;
2227 ira_assert (! ALLOCNO_ASSIGNED_P (a));
2228 cover_class = ALLOCNO_COVER_CLASS (a);
2229 if (cover_class == NO_REGS)
2231 mode = ALLOCNO_MODE (a);
2232 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2236 next_cp = cp->next_first_allocno_copy;
2237 another_a = cp->second;
2239 else if (cp->second == a)
2241 next_cp = cp->next_second_allocno_copy;
2242 another_a = cp->first;
2246 if (! ira_reg_classes_intersect_p[cover_class][ALLOCNO_COVER_CLASS
2248 || ! ALLOCNO_ASSIGNED_P (another_a)
2249 || (hard_regno = ALLOCNO_HARD_REGNO (another_a)) < 0)
2251 rclass = REGNO_REG_CLASS (hard_regno);
2252 i = ira_class_hard_reg_index[cover_class][hard_regno];
2255 cost = (cp->first == a
2256 ? ira_get_register_move_cost (mode, rclass, cover_class)
2257 : ira_get_register_move_cost (mode, cover_class, rclass));
2258 ira_allocate_and_set_or_copy_costs
2259 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
2260 cover_class, ALLOCNO_COVER_CLASS_COST (a),
2261 ALLOCNO_HARD_REG_COSTS (a));
2262 ira_allocate_and_set_or_copy_costs
2263 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
2264 cover_class, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
2265 ALLOCNO_UPDATED_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
2266 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
2270 /* Try to assign hard registers to the unassigned allocnos and
2271 allocnos conflicting with them or conflicting with allocnos whose
2272 regno >= START_REGNO. The function is called after ira_flattening,
2273 so more allocnos (including ones created in ira-emit.c) will have a
2274 chance to get a hard register. We use simple assignment algorithm
2275 based on priorities. */
2277 ira_reassign_conflict_allocnos (int start_regno)
2279 int i, allocnos_to_color_num;
2280 ira_allocno_t a, conflict_a;
2281 ira_allocno_conflict_iterator aci;
2282 enum reg_class cover_class;
2283 bitmap allocnos_to_color;
2284 ira_allocno_iterator ai;
2286 allocnos_to_color = ira_allocate_bitmap ();
2287 allocnos_to_color_num = 0;
2288 FOR_EACH_ALLOCNO (a, ai)
2290 if (! ALLOCNO_ASSIGNED_P (a)
2291 && ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a)))
2293 if (ALLOCNO_COVER_CLASS (a) != NO_REGS)
2294 sorted_allocnos[allocnos_to_color_num++] = a;
2297 ALLOCNO_ASSIGNED_P (a) = true;
2298 ALLOCNO_HARD_REGNO (a) = -1;
2299 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2300 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2302 bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (a));
2304 if (ALLOCNO_REGNO (a) < start_regno
2305 || (cover_class = ALLOCNO_COVER_CLASS (a)) == NO_REGS)
2307 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
2309 ira_assert (ira_reg_classes_intersect_p
2310 [cover_class][ALLOCNO_COVER_CLASS (conflict_a)]);
2311 if (bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (conflict_a)))
2313 bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a));
2314 sorted_allocnos[allocnos_to_color_num++] = conflict_a;
2317 ira_free_bitmap (allocnos_to_color);
2318 if (allocnos_to_color_num > 1)
2320 setup_allocno_priorities (sorted_allocnos, allocnos_to_color_num);
2321 qsort (sorted_allocnos, allocnos_to_color_num, sizeof (ira_allocno_t),
2322 allocno_priority_compare_func);
2324 for (i = 0; i < allocnos_to_color_num; i++)
2326 a = sorted_allocnos[i];
2327 ALLOCNO_ASSIGNED_P (a) = false;
2328 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2329 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2330 update_curr_costs (a);
2332 for (i = 0; i < allocnos_to_color_num; i++)
2334 a = sorted_allocnos[i];
2335 if (assign_hard_reg (a, true))
2337 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2340 " Secondary allocation: assign hard reg %d to reg %d\n",
2341 ALLOCNO_HARD_REGNO (a), ALLOCNO_REGNO (a));
2348 /* This page contains code to coalesce memory stack slots used by
2349 spilled allocnos. This results in smaller stack frame, better data
2350 locality, and in smaller code for some architectures like
2351 x86/x86_64 where insn size depends on address displacement value.
2352 On the other hand, it can worsen insn scheduling after the RA but
2353 in practice it is less important than smaller stack frames. */
2355 /* Usage cost and order number of coalesced allocno set to which
2356 given pseudo register belongs to. */
2357 static int *regno_coalesced_allocno_cost;
2358 static int *regno_coalesced_allocno_num;
2360 /* Sort pseudos according frequencies of coalesced allocno sets they
2361 belong to (putting most frequently ones first), and according to
2362 coalesced allocno set order numbers. */
2364 coalesced_pseudo_reg_freq_compare (const void *v1p, const void *v2p)
2366 const int regno1 = *(const int *) v1p;
2367 const int regno2 = *(const int *) v2p;
2370 if ((diff = (regno_coalesced_allocno_cost[regno2]
2371 - regno_coalesced_allocno_cost[regno1])) != 0)
2373 if ((diff = (regno_coalesced_allocno_num[regno1]
2374 - regno_coalesced_allocno_num[regno2])) != 0)
2376 return regno1 - regno2;
2379 /* Widest width in which each pseudo reg is referred to (via subreg).
2380 It is used for sorting pseudo registers. */
2381 static unsigned int *regno_max_ref_width;
2383 /* Redefine STACK_GROWS_DOWNWARD in terms of 0 or 1. */
2384 #ifdef STACK_GROWS_DOWNWARD
2385 # undef STACK_GROWS_DOWNWARD
2386 # define STACK_GROWS_DOWNWARD 1
2388 # define STACK_GROWS_DOWNWARD 0
2391 /* Sort pseudos according their slot numbers (putting ones with
2392 smaller numbers first, or last when the frame pointer is not
2395 coalesced_pseudo_reg_slot_compare (const void *v1p, const void *v2p)
2397 const int regno1 = *(const int *) v1p;
2398 const int regno2 = *(const int *) v2p;
2399 ira_allocno_t a1 = ira_regno_allocno_map[regno1];
2400 ira_allocno_t a2 = ira_regno_allocno_map[regno2];
2401 int diff, slot_num1, slot_num2;
2402 int total_size1, total_size2;
2404 if (a1 == NULL || ALLOCNO_HARD_REGNO (a1) >= 0)
2406 if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
2407 return regno1 - regno2;
2410 else if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
2412 slot_num1 = -ALLOCNO_HARD_REGNO (a1);
2413 slot_num2 = -ALLOCNO_HARD_REGNO (a2);
2414 if ((diff = slot_num1 - slot_num2) != 0)
2415 return (frame_pointer_needed
2416 || !FRAME_GROWS_DOWNWARD == STACK_GROWS_DOWNWARD ? diff : -diff);
2417 total_size1 = MAX (PSEUDO_REGNO_BYTES (regno1), regno_max_ref_width[regno1]);
2418 total_size2 = MAX (PSEUDO_REGNO_BYTES (regno2), regno_max_ref_width[regno2]);
2419 if ((diff = total_size2 - total_size1) != 0)
2421 return regno1 - regno2;
2424 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
2425 for coalesced allocno sets containing allocnos with their regnos
2426 given in array PSEUDO_REGNOS of length N. */
2428 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos, int n)
2430 int i, num, regno, cost;
2431 ira_allocno_t allocno, a;
2433 for (num = i = 0; i < n; i++)
2435 regno = pseudo_regnos[i];
2436 allocno = ira_regno_allocno_map[regno];
2437 if (allocno == NULL)
2439 regno_coalesced_allocno_cost[regno] = 0;
2440 regno_coalesced_allocno_num[regno] = ++num;
2443 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
2446 for (cost = 0, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2447 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2449 cost += ALLOCNO_FREQ (a);
2453 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2454 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2456 regno_coalesced_allocno_num[ALLOCNO_REGNO (a)] = num;
2457 regno_coalesced_allocno_cost[ALLOCNO_REGNO (a)] = cost;
2464 /* Collect spilled allocnos representing coalesced allocno sets (the
2465 first coalesced allocno). The collected allocnos are returned
2466 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
2467 number of the collected allocnos. The allocnos are given by their
2468 regnos in array PSEUDO_REGNOS of length N. */
2470 collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n,
2471 ira_allocno_t *spilled_coalesced_allocnos)
2474 ira_allocno_t allocno;
2476 for (num = i = 0; i < n; i++)
2478 regno = pseudo_regnos[i];
2479 allocno = ira_regno_allocno_map[regno];
2480 if (allocno == NULL || ALLOCNO_HARD_REGNO (allocno) >= 0
2481 || ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
2483 spilled_coalesced_allocnos[num++] = allocno;
2488 /* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
2489 given slot contains live ranges of coalesced allocnos assigned to
2491 static allocno_live_range_t *slot_coalesced_allocnos_live_ranges;
2493 /* Return TRUE if coalesced allocnos represented by ALLOCNO has live
2494 ranges intersected with live ranges of coalesced allocnos assigned
2495 to slot with number N. */
2497 slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno, int n)
2501 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2502 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2504 if (ira_allocno_live_ranges_intersect_p
2505 (slot_coalesced_allocnos_live_ranges[n], ALLOCNO_LIVE_RANGES (a)))
2513 /* Update live ranges of slot to which coalesced allocnos represented
2514 by ALLOCNO were assigned. */
2516 setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno)
2520 allocno_live_range_t r;
2522 n = ALLOCNO_TEMP (allocno);
2523 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2524 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2526 r = ira_copy_allocno_live_range_list (ALLOCNO_LIVE_RANGES (a));
2527 slot_coalesced_allocnos_live_ranges[n]
2528 = ira_merge_allocno_live_ranges
2529 (slot_coalesced_allocnos_live_ranges[n], r);
2535 /* We have coalesced allocnos involving in copies. Coalesce allocnos
2536 further in order to share the same memory stack slot. Allocnos
2537 representing sets of allocnos coalesced before the call are given
2538 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
2539 some allocnos were coalesced in the function. */
2541 coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num)
2543 int i, j, n, last_coalesced_allocno_num;
2544 ira_allocno_t allocno, a;
2545 bool merged_p = false;
2546 bitmap set_jump_crosses = regstat_get_setjmp_crosses ();
2548 slot_coalesced_allocnos_live_ranges
2549 = (allocno_live_range_t *) ira_allocate (sizeof (allocno_live_range_t)
2550 * ira_allocnos_num);
2551 memset (slot_coalesced_allocnos_live_ranges, 0,
2552 sizeof (allocno_live_range_t) * ira_allocnos_num);
2553 last_coalesced_allocno_num = 0;
2554 /* Coalesce non-conflicting spilled allocnos preferring most
2556 for (i = 0; i < num; i++)
2558 allocno = spilled_coalesced_allocnos[i];
2559 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno
2560 || bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (allocno))
2561 || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
2562 && (ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX
2563 || ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)])))
2565 for (j = 0; j < i; j++)
2567 a = spilled_coalesced_allocnos[j];
2568 n = ALLOCNO_TEMP (a);
2569 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a
2570 && ! bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (a))
2571 && (ALLOCNO_REGNO (a) >= ira_reg_equiv_len
2572 || (! ira_reg_equiv_invariant_p[ALLOCNO_REGNO (a)]
2573 && ira_reg_equiv_const[ALLOCNO_REGNO (a)] == NULL_RTX))
2574 && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno, n))
2579 /* No coalescing: set up number for coalesced allocnos
2580 represented by ALLOCNO. */
2581 ALLOCNO_TEMP (allocno) = last_coalesced_allocno_num++;
2582 setup_slot_coalesced_allocno_live_ranges (allocno);
2586 allocno_coalesced_p = true;
2588 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2589 fprintf (ira_dump_file,
2590 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
2591 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno),
2592 ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2593 ALLOCNO_TEMP (allocno) = ALLOCNO_TEMP (a);
2594 setup_slot_coalesced_allocno_live_ranges (allocno);
2595 merge_allocnos (a, allocno);
2596 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a);
2599 for (i = 0; i < ira_allocnos_num; i++)
2600 ira_finish_allocno_live_range_list
2601 (slot_coalesced_allocnos_live_ranges[i]);
2602 ira_free (slot_coalesced_allocnos_live_ranges);
2606 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
2607 subsequent assigning stack slots to them in the reload pass. To do
2608 this we coalesce spilled allocnos first to decrease the number of
2609 memory-memory move insns. This function is called by the
2612 ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n,
2613 unsigned int *reg_max_ref_width)
2615 int max_regno = max_reg_num ();
2616 int i, regno, num, slot_num;
2617 ira_allocno_t allocno, a;
2618 ira_allocno_iterator ai;
2619 ira_allocno_t *spilled_coalesced_allocnos;
2621 processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
2622 /* Set up allocnos can be coalesced. */
2623 coloring_allocno_bitmap = ira_allocate_bitmap ();
2624 for (i = 0; i < n; i++)
2626 regno = pseudo_regnos[i];
2627 allocno = ira_regno_allocno_map[regno];
2628 if (allocno != NULL)
2629 bitmap_set_bit (coloring_allocno_bitmap,
2630 ALLOCNO_NUM (allocno));
2632 allocno_coalesced_p = false;
2633 coalesce_allocnos (true);
2634 ira_free_bitmap (coloring_allocno_bitmap);
2635 regno_coalesced_allocno_cost
2636 = (int *) ira_allocate (max_regno * sizeof (int));
2637 regno_coalesced_allocno_num
2638 = (int *) ira_allocate (max_regno * sizeof (int));
2639 memset (regno_coalesced_allocno_num, 0, max_regno * sizeof (int));
2640 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
2641 /* Sort regnos according frequencies of the corresponding coalesced
2643 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_freq_compare);
2644 spilled_coalesced_allocnos
2645 = (ira_allocno_t *) ira_allocate (ira_allocnos_num
2646 * sizeof (ira_allocno_t));
2647 /* Collect allocnos representing the spilled coalesced allocno
2649 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
2650 spilled_coalesced_allocnos);
2651 if (flag_ira_share_spill_slots
2652 && coalesce_spill_slots (spilled_coalesced_allocnos, num))
2654 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
2655 qsort (pseudo_regnos, n, sizeof (int),
2656 coalesced_pseudo_reg_freq_compare);
2657 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
2658 spilled_coalesced_allocnos);
2660 ira_free_bitmap (processed_coalesced_allocno_bitmap);
2661 allocno_coalesced_p = false;
2662 /* Assign stack slot numbers to spilled allocno sets, use smaller
2663 numbers for most frequently used coalesced allocnos. -1 is
2664 reserved for dynamic search of stack slots for pseudos spilled by
2667 for (i = 0; i < num; i++)
2669 allocno = spilled_coalesced_allocnos[i];
2670 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno
2671 || ALLOCNO_HARD_REGNO (allocno) >= 0
2672 || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
2673 && (ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX
2674 || ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)])))
2676 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2677 fprintf (ira_dump_file, " Slot %d (freq,size):", slot_num);
2679 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2680 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2682 ira_assert (ALLOCNO_HARD_REGNO (a) < 0);
2683 ALLOCNO_HARD_REGNO (a) = -slot_num;
2684 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2685 fprintf (ira_dump_file, " a%dr%d(%d,%d)",
2686 ALLOCNO_NUM (a), ALLOCNO_REGNO (a), ALLOCNO_FREQ (a),
2687 MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a)),
2688 reg_max_ref_width[ALLOCNO_REGNO (a)]));
2693 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2694 fprintf (ira_dump_file, "\n");
2696 ira_spilled_reg_stack_slots_num = slot_num - 1;
2697 ira_free (spilled_coalesced_allocnos);
2698 /* Sort regnos according the slot numbers. */
2699 regno_max_ref_width = reg_max_ref_width;
2700 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_slot_compare);
2701 /* Uncoalesce allocnos which is necessary for (re)assigning during
2703 FOR_EACH_ALLOCNO (a, ai)
2705 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
2706 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
2708 ira_free (regno_coalesced_allocno_num);
2709 ira_free (regno_coalesced_allocno_cost);
2714 /* This page contains code used by the reload pass to improve the
2717 /* The function is called from reload to mark changes in the
2718 allocation of REGNO made by the reload. Remember that reg_renumber
2719 reflects the change result. */
2721 ira_mark_allocation_change (int regno)
2723 ira_allocno_t a = ira_regno_allocno_map[regno];
2724 int old_hard_regno, hard_regno, cost;
2725 enum reg_class cover_class = ALLOCNO_COVER_CLASS (a);
2727 ira_assert (a != NULL);
2728 hard_regno = reg_renumber[regno];
2729 if ((old_hard_regno = ALLOCNO_HARD_REGNO (a)) == hard_regno)
2731 if (old_hard_regno < 0)
2732 cost = -ALLOCNO_MEMORY_COST (a);
2735 ira_assert (ira_class_hard_reg_index[cover_class][old_hard_regno] >= 0);
2736 cost = -(ALLOCNO_HARD_REG_COSTS (a) == NULL
2737 ? ALLOCNO_COVER_CLASS_COST (a)
2738 : ALLOCNO_HARD_REG_COSTS (a)
2739 [ira_class_hard_reg_index[cover_class][old_hard_regno]]);
2740 update_copy_costs (a, false);
2742 ira_overall_cost -= cost;
2743 ALLOCNO_HARD_REGNO (a) = hard_regno;
2746 ALLOCNO_HARD_REGNO (a) = -1;
2747 cost += ALLOCNO_MEMORY_COST (a);
2749 else if (ira_class_hard_reg_index[cover_class][hard_regno] >= 0)
2751 cost += (ALLOCNO_HARD_REG_COSTS (a) == NULL
2752 ? ALLOCNO_COVER_CLASS_COST (a)
2753 : ALLOCNO_HARD_REG_COSTS (a)
2754 [ira_class_hard_reg_index[cover_class][hard_regno]]);
2755 update_copy_costs (a, true);
2758 /* Reload changed class of the allocno. */
2760 ira_overall_cost += cost;
2763 /* This function is called when reload deletes memory-memory move. In
2764 this case we marks that the allocation of the corresponding
2765 allocnos should be not changed in future. Otherwise we risk to get
2768 ira_mark_memory_move_deletion (int dst_regno, int src_regno)
2770 ira_allocno_t dst = ira_regno_allocno_map[dst_regno];
2771 ira_allocno_t src = ira_regno_allocno_map[src_regno];
2773 ira_assert (dst != NULL && src != NULL
2774 && ALLOCNO_HARD_REGNO (dst) < 0
2775 && ALLOCNO_HARD_REGNO (src) < 0);
2776 ALLOCNO_DONT_REASSIGN_P (dst) = true;
2777 ALLOCNO_DONT_REASSIGN_P (src) = true;
2780 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
2781 allocno A and return TRUE in the case of success. */
2783 allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs)
2786 enum reg_class cover_class;
2787 int regno = ALLOCNO_REGNO (a);
2789 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), forbidden_regs);
2790 if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
2791 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), call_used_reg_set);
2792 ALLOCNO_ASSIGNED_P (a) = false;
2793 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2794 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2795 cover_class = ALLOCNO_COVER_CLASS (a);
2796 update_curr_costs (a);
2797 assign_hard_reg (a, true);
2798 hard_regno = ALLOCNO_HARD_REGNO (a);
2799 reg_renumber[regno] = hard_regno;
2801 ALLOCNO_HARD_REGNO (a) = -1;
2804 ira_assert (ira_class_hard_reg_index[cover_class][hard_regno] >= 0);
2805 ira_overall_cost -= (ALLOCNO_MEMORY_COST (a)
2806 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
2807 ? ALLOCNO_COVER_CLASS_COST (a)
2808 : ALLOCNO_HARD_REG_COSTS (a)
2809 [ira_class_hard_reg_index
2810 [cover_class][hard_regno]]));
2811 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
2812 && ! ira_hard_reg_not_in_set_p (hard_regno, ALLOCNO_MODE (a),
2815 ira_assert (flag_caller_saves);
2816 caller_save_needed = 1;
2820 /* If we found a hard register, modify the RTL for the pseudo
2821 register to show the hard register, and mark the pseudo register
2823 if (reg_renumber[regno] >= 0)
2825 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2826 fprintf (ira_dump_file, ": reassign to %d\n", reg_renumber[regno]);
2827 SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
2828 mark_home_live (regno);
2830 else if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2831 fprintf (ira_dump_file, "\n");
2833 return reg_renumber[regno] >= 0;
2836 /* Sort pseudos according their usage frequencies (putting most
2837 frequently ones first). */
2839 pseudo_reg_compare (const void *v1p, const void *v2p)
2841 int regno1 = *(const int *) v1p;
2842 int regno2 = *(const int *) v2p;
2845 if ((diff = REG_FREQ (regno2) - REG_FREQ (regno1)) != 0)
2847 return regno1 - regno2;
2850 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
2851 NUM of them) or spilled pseudos conflicting with pseudos in
2852 SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
2853 allocation has been changed. The function doesn't use
2854 BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
2855 PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
2856 is called by the reload pass at the end of each reload
2859 ira_reassign_pseudos (int *spilled_pseudo_regs, int num,
2860 HARD_REG_SET bad_spill_regs,
2861 HARD_REG_SET *pseudo_forbidden_regs,
2862 HARD_REG_SET *pseudo_previous_regs, bitmap spilled)
2866 ira_allocno_t a, conflict_a;
2867 HARD_REG_SET forbidden_regs;
2868 ira_allocno_conflict_iterator aci;
2871 qsort (spilled_pseudo_regs, num, sizeof (int), pseudo_reg_compare);
2873 /* Try to assign hard registers to pseudos from
2874 SPILLED_PSEUDO_REGS. */
2875 for (m = i = 0; i < num; i++)
2877 regno = spilled_pseudo_regs[i];
2878 COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
2879 IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]);
2880 IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]);
2881 gcc_assert (reg_renumber[regno] < 0);
2882 a = ira_regno_allocno_map[regno];
2883 ira_mark_allocation_change (regno);
2884 ira_assert (reg_renumber[regno] < 0);
2885 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2886 fprintf (ira_dump_file,
2887 " Spill %d(a%d), cost=%d", regno, ALLOCNO_NUM (a),
2888 ALLOCNO_MEMORY_COST (a)
2889 - ALLOCNO_COVER_CLASS_COST (a));
2890 allocno_reload_assign (a, forbidden_regs);
2891 if (reg_renumber[regno] >= 0)
2893 CLEAR_REGNO_REG_SET (spilled, regno);
2897 spilled_pseudo_regs[m++] = regno;
2901 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2903 fprintf (ira_dump_file, " Spilled regs");
2904 for (i = 0; i < m; i++)
2905 fprintf (ira_dump_file, " %d", spilled_pseudo_regs[i]);
2906 fprintf (ira_dump_file, "\n");
2908 /* Try to assign hard registers to pseudos conflicting with ones
2909 from SPILLED_PSEUDO_REGS. */
2910 for (i = n = 0; i < m; i++)
2912 regno = spilled_pseudo_regs[i];
2913 a = ira_regno_allocno_map[regno];
2914 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
2915 if (ALLOCNO_HARD_REGNO (conflict_a) < 0
2916 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a)
2917 && ! bitmap_bit_p (consideration_allocno_bitmap,
2918 ALLOCNO_NUM (conflict_a)))
2920 sorted_allocnos[n++] = conflict_a;
2921 bitmap_set_bit (consideration_allocno_bitmap,
2922 ALLOCNO_NUM (conflict_a));
2927 setup_allocno_priorities (sorted_allocnos, n);
2928 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
2929 allocno_priority_compare_func);
2930 for (i = 0; i < n; i++)
2932 a = sorted_allocnos[i];
2933 regno = ALLOCNO_REGNO (a);
2934 COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
2935 IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]);
2936 IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]);
2937 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2938 fprintf (ira_dump_file,
2939 " Try assign %d(a%d), cost=%d",
2940 regno, ALLOCNO_NUM (a),
2941 ALLOCNO_MEMORY_COST (a)
2942 - ALLOCNO_COVER_CLASS_COST (a));
2943 if (allocno_reload_assign (a, forbidden_regs))
2946 bitmap_clear_bit (spilled, regno);
2953 /* The function is called by reload and returns already allocated
2954 stack slot (if any) for REGNO with given INHERENT_SIZE and
2955 TOTAL_SIZE. In the case of failure to find a slot which can be
2956 used for REGNO, the function returns NULL. */
2958 ira_reuse_stack_slot (int regno, unsigned int inherent_size,
2959 unsigned int total_size)
2962 int slot_num, best_slot_num;
2963 int cost, best_cost;
2964 ira_copy_t cp, next_cp;
2965 ira_allocno_t another_allocno, allocno = ira_regno_allocno_map[regno];
2968 struct ira_spilled_reg_stack_slot *slot = NULL;
2970 ira_assert (inherent_size == PSEUDO_REGNO_BYTES (regno)
2971 && inherent_size <= total_size
2972 && ALLOCNO_HARD_REGNO (allocno) < 0);
2973 if (! flag_ira_share_spill_slots)
2975 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
2978 slot = &ira_spilled_reg_stack_slots[slot_num];
2983 best_cost = best_slot_num = -1;
2985 /* It means that the pseudo was spilled in the reload pass, try
2988 slot_num < ira_spilled_reg_stack_slots_num;
2991 slot = &ira_spilled_reg_stack_slots[slot_num];
2992 if (slot->mem == NULL_RTX)
2994 if (slot->width < total_size
2995 || GET_MODE_SIZE (GET_MODE (slot->mem)) < inherent_size)
2998 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
2999 FIRST_PSEUDO_REGISTER, i, bi)
3001 another_allocno = ira_regno_allocno_map[i];
3002 if (allocnos_have_intersected_live_ranges_p (allocno,
3006 for (cost = 0, cp = ALLOCNO_COPIES (allocno);
3010 if (cp->first == allocno)
3012 next_cp = cp->next_first_allocno_copy;
3013 another_allocno = cp->second;
3015 else if (cp->second == allocno)
3017 next_cp = cp->next_second_allocno_copy;
3018 another_allocno = cp->first;
3022 if (cp->insn == NULL_RTX)
3024 if (bitmap_bit_p (&slot->spilled_regs,
3025 ALLOCNO_REGNO (another_allocno)))
3028 if (cost > best_cost)
3031 best_slot_num = slot_num;
3038 slot_num = best_slot_num;
3039 slot = &ira_spilled_reg_stack_slots[slot_num];
3040 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
3042 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
3047 ira_assert (slot->width >= total_size);
3048 #ifdef ENABLE_IRA_CHECKING
3049 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
3050 FIRST_PSEUDO_REGISTER, i, bi)
3052 ira_assert (! pseudos_have_intersected_live_ranges_p (regno, i));
3055 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
3056 if (internal_flag_ira_verbose > 3 && ira_dump_file)
3058 fprintf (ira_dump_file, " Assigning %d(freq=%d) slot %d of",
3059 regno, REG_FREQ (regno), slot_num);
3060 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
3061 FIRST_PSEUDO_REGISTER, i, bi)
3063 if ((unsigned) regno != i)
3064 fprintf (ira_dump_file, " %d", i);
3066 fprintf (ira_dump_file, "\n");
3072 /* This is called by reload every time a new stack slot X with
3073 TOTAL_SIZE was allocated for REGNO. We store this info for
3074 subsequent ira_reuse_stack_slot calls. */
3076 ira_mark_new_stack_slot (rtx x, int regno, unsigned int total_size)
3078 struct ira_spilled_reg_stack_slot *slot;
3080 ira_allocno_t allocno;
3082 ira_assert (PSEUDO_REGNO_BYTES (regno) <= total_size);
3083 allocno = ira_regno_allocno_map[regno];
3084 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
3087 slot_num = ira_spilled_reg_stack_slots_num++;
3088 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
3090 slot = &ira_spilled_reg_stack_slots[slot_num];
3091 INIT_REG_SET (&slot->spilled_regs);
3092 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
3094 slot->width = total_size;
3095 if (internal_flag_ira_verbose > 3 && ira_dump_file)
3096 fprintf (ira_dump_file, " Assigning %d(freq=%d) a new slot %d\n",
3097 regno, REG_FREQ (regno), slot_num);
3101 /* Return spill cost for pseudo-registers whose numbers are in array
3102 REGNOS (with a negative number as an end marker) for reload with
3103 given IN and OUT for INSN. Return also number points (through
3104 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
3105 the register pressure is high, number of references of the
3106 pseudo-registers (through NREFS), number of callee-clobbered
3107 hard-registers occupied by the pseudo-registers (through
3108 CALL_USED_COUNT), and the first hard regno occupied by the
3109 pseudo-registers (through FIRST_HARD_REGNO). */
3111 calculate_spill_cost (int *regnos, rtx in, rtx out, rtx insn,
3112 int *excess_pressure_live_length,
3113 int *nrefs, int *call_used_count, int *first_hard_regno)
3115 int i, cost, regno, hard_regno, j, count, saved_cost, nregs;
3121 for (length = count = cost = i = 0;; i++)
3126 *nrefs += REG_N_REFS (regno);
3127 hard_regno = reg_renumber[regno];
3128 ira_assert (hard_regno >= 0);
3129 a = ira_regno_allocno_map[regno];
3130 length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
3131 cost += ALLOCNO_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a);
3132 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
3133 for (j = 0; j < nregs; j++)
3134 if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j))
3138 in_p = in && REG_P (in) && (int) REGNO (in) == hard_regno;
3139 out_p = out && REG_P (out) && (int) REGNO (out) == hard_regno;
3141 && find_regno_note (insn, REG_DEAD, hard_regno) != NULL_RTX)
3145 saved_cost += ira_memory_move_cost
3146 [ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)][1];
3149 += ira_memory_move_cost
3150 [ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)][0];
3151 cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)) * saved_cost;
3154 *excess_pressure_live_length = length;
3155 *call_used_count = count;
3159 hard_regno = reg_renumber[regnos[0]];
3161 *first_hard_regno = hard_regno;
3165 /* Return TRUE if spilling pseudo-registers whose numbers are in array
3166 REGNOS is better than spilling pseudo-registers with numbers in
3167 OTHER_REGNOS for reload with given IN and OUT for INSN. The
3168 function used by the reload pass to make better register spilling
3171 ira_better_spill_reload_regno_p (int *regnos, int *other_regnos,
3172 rtx in, rtx out, rtx insn)
3174 int cost, other_cost;
3175 int length, other_length;
3176 int nrefs, other_nrefs;
3177 int call_used_count, other_call_used_count;
3178 int hard_regno, other_hard_regno;
3180 cost = calculate_spill_cost (regnos, in, out, insn,
3181 &length, &nrefs, &call_used_count, &hard_regno);
3182 other_cost = calculate_spill_cost (other_regnos, in, out, insn,
3183 &other_length, &other_nrefs,
3184 &other_call_used_count,
3186 if (nrefs == 0 && other_nrefs != 0)
3188 if (nrefs != 0 && other_nrefs == 0)
3190 if (cost != other_cost)
3191 return cost < other_cost;
3192 if (length != other_length)
3193 return length > other_length;
3194 #ifdef REG_ALLOC_ORDER
3195 if (hard_regno >= 0 && other_hard_regno >= 0)
3196 return (inv_reg_alloc_order[hard_regno]
3197 < inv_reg_alloc_order[other_hard_regno]);
3199 if (call_used_count != other_call_used_count)
3200 return call_used_count > other_call_used_count;
3207 /* Allocate and initialize data necessary for assign_hard_reg. */
3209 ira_initiate_assign (void)
3212 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
3213 * ira_allocnos_num);
3214 consideration_allocno_bitmap = ira_allocate_bitmap ();
3215 initiate_cost_update ();
3216 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
3219 /* Deallocate data used by assign_hard_reg. */
3221 ira_finish_assign (void)
3223 ira_free (sorted_allocnos);
3224 ira_free_bitmap (consideration_allocno_bitmap);
3225 finish_cost_update ();
3226 ira_free (allocno_priorities);
3231 /* Entry function doing color-based register allocation. */
3235 allocno_stack_vec = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
3236 removed_splay_allocno_vec
3237 = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
3238 memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p));
3239 ira_initiate_assign ();
3241 ira_finish_assign ();
3242 VEC_free (ira_allocno_t, heap, removed_splay_allocno_vec);
3243 VEC_free (ira_allocno_t, heap, allocno_stack_vec);
3244 move_spill_restore ();
3249 /* This page contains a simple register allocator without usage of
3250 allocno conflicts. This is used for fast allocation for -O0. */
3252 /* Do register allocation by not using allocno conflicts. It uses
3253 only allocno live ranges. The algorithm is close to Chow's
3254 priority coloring. */
3256 fast_allocation (void)
3258 int i, j, k, num, class_size, hard_regno;
3260 bool no_stack_reg_p;
3262 enum reg_class cover_class;
3263 enum machine_mode mode;
3265 ira_allocno_iterator ai;
3266 allocno_live_range_t r;
3267 HARD_REG_SET conflict_hard_regs, *used_hard_regs;
3269 sorted_allocnos = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
3270 * ira_allocnos_num);
3272 FOR_EACH_ALLOCNO (a, ai)
3273 sorted_allocnos[num++] = a;
3274 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
3275 setup_allocno_priorities (sorted_allocnos, num);
3276 used_hard_regs = (HARD_REG_SET *) ira_allocate (sizeof (HARD_REG_SET)
3278 for (i = 0; i < ira_max_point; i++)
3279 CLEAR_HARD_REG_SET (used_hard_regs[i]);
3280 qsort (sorted_allocnos, num, sizeof (ira_allocno_t),
3281 allocno_priority_compare_func);
3282 for (i = 0; i < num; i++)
3284 a = sorted_allocnos[i];
3285 COPY_HARD_REG_SET (conflict_hard_regs, ALLOCNO_CONFLICT_HARD_REGS (a));
3286 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
3287 for (j = r->start; j <= r->finish; j++)
3288 IOR_HARD_REG_SET (conflict_hard_regs, used_hard_regs[j]);
3289 cover_class = ALLOCNO_COVER_CLASS (a);
3290 ALLOCNO_ASSIGNED_P (a) = true;
3291 ALLOCNO_HARD_REGNO (a) = -1;
3292 if (hard_reg_set_subset_p (reg_class_contents[cover_class],
3293 conflict_hard_regs))
3295 mode = ALLOCNO_MODE (a);
3297 no_stack_reg_p = ALLOCNO_NO_STACK_REG_P (a);
3299 class_size = ira_class_hard_regs_num[cover_class];
3300 for (j = 0; j < class_size; j++)
3302 hard_regno = ira_class_hard_regs[cover_class][j];
3304 if (no_stack_reg_p && FIRST_STACK_REG <= hard_regno
3305 && hard_regno <= LAST_STACK_REG)
3308 if (!ira_hard_reg_not_in_set_p (hard_regno, mode, conflict_hard_regs)
3309 || (TEST_HARD_REG_BIT
3310 (prohibited_class_mode_regs[cover_class][mode], hard_regno)))
3312 ALLOCNO_HARD_REGNO (a) = hard_regno;
3313 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
3314 for (k = r->start; k <= r->finish; k++)
3315 IOR_HARD_REG_SET (used_hard_regs[k],
3316 ira_reg_mode_hard_regset[hard_regno][mode]);
3320 ira_free (sorted_allocnos);
3321 ira_free (used_hard_regs);
3322 ira_free (allocno_priorities);
3323 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
3324 ira_print_disposition (ira_dump_file);
3329 /* Entry function doing coloring. */
3334 ira_allocno_iterator ai;
3336 /* Setup updated costs. */
3337 FOR_EACH_ALLOCNO (a, ai)
3339 ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
3340 ALLOCNO_UPDATED_COVER_CLASS_COST (a) = ALLOCNO_COVER_CLASS_COST (a);
3342 if (ira_conflicts_p)