1 /* IRA allocation based on graph coloring.
2 Copyright (C) 2006, 2007, 2008
3 Free Software Foundation, Inc.
4 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
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;
87 /* This page contains functions used to choose hard registers for
90 /* Array whose element value is TRUE if the corresponding hard
91 register was already allocated for an allocno. */
92 static bool allocated_hardreg_p[FIRST_PSEUDO_REGISTER];
94 /* Describes one element in a queue of allocnos whose costs need to be
95 updated. Each allocno in the queue is known to have a cover class. */
96 struct update_cost_queue_elem {
97 /* This element is in the queue iff CHECK == update_cost_check. */
100 /* COST_HOP_DIVISOR**N, where N is the length of the shortest path
101 connecting this allocno to the one being allocated. */
104 /* The next allocno in the queue, or null if this is the last element. */
108 /* The first element in a queue of allocnos whose copy costs need to be
109 updated. Null if the queue is empty. */
110 static ira_allocno_t update_cost_queue;
112 /* The last element in the queue described by update_cost_queue.
113 Not valid if update_cost_queue is null. */
114 static struct update_cost_queue_elem *update_cost_queue_tail;
116 /* A pool of elements in the queue described by update_cost_queue.
117 Elements are indexed by ALLOCNO_NUM. */
118 static struct update_cost_queue_elem *update_cost_queue_elems;
120 /* The current value of update_copy_cost call count. */
121 static int update_cost_check;
123 /* Allocate and initialize data necessary for function
124 update_copy_costs. */
126 initiate_cost_update (void)
130 size = ira_allocnos_num * sizeof (struct update_cost_queue_elem);
131 update_cost_queue_elems
132 = (struct update_cost_queue_elem *) ira_allocate (size);
133 memset (update_cost_queue_elems, 0, size);
134 update_cost_check = 0;
137 /* Deallocate data used by function update_copy_costs. */
139 finish_cost_update (void)
141 ira_free (update_cost_queue);
144 /* When we traverse allocnos to update hard register costs, the cost
145 divisor will be multiplied by the following macro value for each
146 hop from given allocno to directly connected allocnos. */
147 #define COST_HOP_DIVISOR 4
149 /* Start a new cost-updating pass. */
151 start_update_cost (void)
154 update_cost_queue = NULL;
157 /* Add (ALLOCNO, DIVISOR) to the end of update_cost_queue,
158 unless ALLOCNO is already in the queue, or has no cover class. */
160 queue_update_cost (ira_allocno_t allocno, int divisor)
162 struct update_cost_queue_elem *elem;
164 elem = &update_cost_queue_elems[ALLOCNO_NUM (allocno)];
165 if (elem->check != update_cost_check
166 && ALLOCNO_COVER_CLASS (allocno) != NO_REGS)
168 elem->check = update_cost_check;
169 elem->divisor = divisor;
171 if (update_cost_queue == NULL)
172 update_cost_queue = allocno;
174 update_cost_queue_tail->next = allocno;
175 update_cost_queue_tail = elem;
179 /* Try to remove the first element from update_cost_queue. Return false
180 if the queue was empty, otherwise make (*ALLOCNO, *DIVISOR) describe
181 the removed element. */
183 get_next_update_cost (ira_allocno_t *allocno, int *divisor)
185 struct update_cost_queue_elem *elem;
187 if (update_cost_queue == NULL)
190 *allocno = update_cost_queue;
191 elem = &update_cost_queue_elems[ALLOCNO_NUM (*allocno)];
192 *divisor = elem->divisor;
193 update_cost_queue = elem->next;
197 /* Update the cost of allocnos to increase chances to remove some
198 copies as the result of subsequent assignment. */
200 update_copy_costs (ira_allocno_t allocno, bool decr_p)
202 int i, cost, update_cost, hard_regno, divisor;
203 enum machine_mode mode;
204 enum reg_class rclass, cover_class;
205 ira_allocno_t another_allocno;
206 ira_copy_t cp, next_cp;
208 hard_regno = ALLOCNO_HARD_REGNO (allocno);
209 ira_assert (hard_regno >= 0);
211 cover_class = ALLOCNO_COVER_CLASS (allocno);
212 if (cover_class == NO_REGS)
214 i = ira_class_hard_reg_index[cover_class][hard_regno];
216 rclass = REGNO_REG_CLASS (hard_regno);
218 start_update_cost ();
222 mode = ALLOCNO_MODE (allocno);
223 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
225 if (cp->first == allocno)
227 next_cp = cp->next_first_allocno_copy;
228 another_allocno = cp->second;
230 else if (cp->second == allocno)
232 next_cp = cp->next_second_allocno_copy;
233 another_allocno = cp->first;
238 if (cover_class != ALLOCNO_COVER_CLASS (another_allocno)
239 || ALLOCNO_ASSIGNED_P (another_allocno))
242 cost = (cp->second == allocno
243 ? ira_register_move_cost[mode][rclass][cover_class]
244 : ira_register_move_cost[mode][cover_class][rclass]);
248 update_cost = cp->freq * cost / divisor;
249 if (update_cost == 0)
252 ira_allocate_and_set_or_copy_costs
253 (&ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno), cover_class,
254 ALLOCNO_COVER_CLASS_COST (another_allocno),
255 ALLOCNO_HARD_REG_COSTS (another_allocno));
256 ira_allocate_and_set_or_copy_costs
257 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
259 ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
260 ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno)[i] += update_cost;
261 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno)[i]
264 queue_update_cost (another_allocno, divisor * COST_HOP_DIVISOR);
267 while (get_next_update_cost (&allocno, &divisor));
270 /* This function updates COSTS (decrease if DECR_P) by conflict costs
271 of the unassigned allocnos connected by copies with allocnos in
272 update_cost_queue. This update increases chances to remove some
275 update_conflict_hard_regno_costs (int *costs, bool decr_p)
277 int i, cost, class_size, freq, mult, div, divisor;
280 enum reg_class cover_class;
281 ira_allocno_t allocno, another_allocno;
282 ira_copy_t cp, next_cp;
284 while (get_next_update_cost (&allocno, &divisor))
285 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
287 if (cp->first == allocno)
289 next_cp = cp->next_first_allocno_copy;
290 another_allocno = cp->second;
292 else if (cp->second == allocno)
294 next_cp = cp->next_second_allocno_copy;
295 another_allocno = cp->first;
299 cover_class = ALLOCNO_COVER_CLASS (allocno);
300 if (cover_class != ALLOCNO_COVER_CLASS (another_allocno)
301 || ALLOCNO_ASSIGNED_P (another_allocno)
302 || ALLOCNO_MAY_BE_SPILLED_P (another_allocno))
304 class_size = ira_class_hard_regs_num[cover_class];
305 ira_allocate_and_copy_costs
306 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
307 cover_class, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
309 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno);
310 if (conflict_costs == NULL)
315 freq = ALLOCNO_FREQ (another_allocno);
318 div = freq * divisor;
320 for (i = class_size - 1; i >= 0; i--)
322 cost = conflict_costs [i] * mult / div;
331 /* Probably 5 hops will be enough. */
333 && divisor <= (COST_HOP_DIVISOR
337 queue_update_cost (another_allocno, divisor * COST_HOP_DIVISOR);
341 /* Sort allocnos according to the profit of usage of a hard register
342 instead of memory for them. */
344 allocno_cost_compare_func (const void *v1p, const void *v2p)
346 ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
347 ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
350 c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_COVER_CLASS_COST (p1);
351 c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_COVER_CLASS_COST (p2);
355 /* If regs are equally good, sort by allocno numbers, so that the
356 results of qsort leave nothing to chance. */
357 return ALLOCNO_NUM (p1) - ALLOCNO_NUM (p2);
360 /* Print all allocnos coalesced with ALLOCNO. */
362 print_coalesced_allocno (ira_allocno_t allocno)
366 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
367 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
369 ira_print_expanded_allocno (a);
372 fprintf (ira_dump_file, "+");
376 /* Choose a hard register for ALLOCNO (or for all coalesced allocnos
377 represented by ALLOCNO). If RETRY_P is TRUE, it means that the
378 function called from function `ira_reassign_conflict_allocnos' and
379 `allocno_reload_assign'. This function implements the optimistic
380 coalescing too: if we failed to assign a hard register to set of
381 the coalesced allocnos, we put them onto the coloring stack for
382 subsequent separate assigning. */
384 assign_hard_reg (ira_allocno_t allocno, bool retry_p)
386 HARD_REG_SET conflicting_regs;
387 int i, j, hard_regno, best_hard_regno, class_size;
388 int cost, mem_cost, min_cost, full_cost, min_full_cost, add_cost;
391 enum reg_class cover_class, rclass;
392 enum machine_mode mode;
393 ira_allocno_t a, conflict_allocno;
394 ira_allocno_conflict_iterator aci;
395 static int costs[FIRST_PSEUDO_REGISTER], full_costs[FIRST_PSEUDO_REGISTER];
400 ira_assert (! ALLOCNO_ASSIGNED_P (allocno));
401 cover_class = ALLOCNO_COVER_CLASS (allocno);
402 class_size = ira_class_hard_regs_num[cover_class];
403 mode = ALLOCNO_MODE (allocno);
404 CLEAR_HARD_REG_SET (conflicting_regs);
405 best_hard_regno = -1;
406 memset (full_costs, 0, sizeof (int) * class_size);
408 if (allocno_coalesced_p)
409 bitmap_clear (processed_coalesced_allocno_bitmap);
410 memset (costs, 0, sizeof (int) * class_size);
411 memset (full_costs, 0, sizeof (int) * class_size);
413 no_stack_reg_p = false;
415 start_update_cost ();
416 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
417 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
419 mem_cost += ALLOCNO_UPDATED_MEMORY_COST (a);
420 IOR_HARD_REG_SET (conflicting_regs,
421 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
422 ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
423 cover_class, ALLOCNO_HARD_REG_COSTS (a));
424 a_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
426 no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a);
428 for (cost = ALLOCNO_COVER_CLASS_COST (a), i = 0; i < class_size; i++)
431 costs[i] += a_costs[i];
432 full_costs[i] += a_costs[i];
437 full_costs[i] += cost;
439 /* Take preferences of conflicting allocnos into account. */
440 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
441 /* Reload can give another class so we need to check all
443 if (retry_p || bitmap_bit_p (consideration_allocno_bitmap,
444 ALLOCNO_NUM (conflict_allocno)))
446 ira_assert (cover_class == ALLOCNO_COVER_CLASS (conflict_allocno));
447 if (allocno_coalesced_p)
449 if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
450 ALLOCNO_NUM (conflict_allocno)))
452 bitmap_set_bit (processed_coalesced_allocno_bitmap,
453 ALLOCNO_NUM (conflict_allocno));
455 if (ALLOCNO_ASSIGNED_P (conflict_allocno))
457 if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno)) >= 0)
461 ira_reg_mode_hard_regset
462 [hard_regno][ALLOCNO_MODE (conflict_allocno)]);
463 if (hard_reg_set_subset_p (reg_class_contents[cover_class],
469 else if (! ALLOCNO_MAY_BE_SPILLED_P (conflict_allocno))
471 ira_allocate_and_copy_costs
472 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno),
474 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_allocno));
476 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno);
477 if (conflict_costs != NULL)
478 for (j = class_size - 1; j >= 0; j--)
479 full_costs[j] -= conflict_costs[j];
480 queue_update_cost (conflict_allocno, COST_HOP_DIVISOR);
486 /* Take into account preferences of allocnos connected by copies to
487 the conflict allocnos. */
488 update_conflict_hard_regno_costs (full_costs, true);
490 /* Take preferences of allocnos connected by copies into
492 start_update_cost ();
493 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
494 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
496 queue_update_cost (a, COST_HOP_DIVISOR);
500 update_conflict_hard_regno_costs (full_costs, false);
501 min_cost = min_full_cost = INT_MAX;
502 /* We don't care about giving callee saved registers to allocnos no
503 living through calls because call clobbered registers are
504 allocated first (it is usual practice to put them first in
506 for (i = 0; i < class_size; i++)
508 hard_regno = ira_class_hard_regs[cover_class][i];
511 && FIRST_STACK_REG <= hard_regno && hard_regno <= LAST_STACK_REG)
514 if (! ira_hard_reg_not_in_set_p (hard_regno, mode, conflicting_regs)
515 || TEST_HARD_REG_BIT (prohibited_class_mode_regs[cover_class][mode],
519 full_cost = full_costs[i];
520 if (! allocated_hardreg_p[hard_regno]
521 && ira_hard_reg_not_in_set_p (hard_regno, mode, call_used_reg_set))
522 /* We need to save/restore the hard register in
523 epilogue/prologue. Therefore we increase the cost. */
525 /* ??? If only part is call clobbered. */
526 rclass = REGNO_REG_CLASS (hard_regno);
527 add_cost = (ira_memory_move_cost[mode][rclass][0]
528 + ira_memory_move_cost[mode][rclass][1] - 1);
530 full_cost += add_cost;
534 if (min_full_cost > full_cost)
536 min_full_cost = full_cost;
537 best_hard_regno = hard_regno;
538 ira_assert (hard_regno >= 0);
541 if (min_full_cost > mem_cost)
543 if (! retry_p && internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
544 fprintf (ira_dump_file, "(memory is more profitable %d vs %d) ",
545 mem_cost, min_full_cost);
546 best_hard_regno = -1;
549 if (best_hard_regno < 0
550 && ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno) != allocno)
552 for (j = 0, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
553 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
555 sorted_allocnos[j++] = a;
559 qsort (sorted_allocnos, j, sizeof (ira_allocno_t),
560 allocno_cost_compare_func);
561 for (i = 0; i < j; i++)
563 a = sorted_allocnos[i];
564 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
565 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
566 VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, a);
567 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
569 fprintf (ira_dump_file, " Pushing");
570 print_coalesced_allocno (a);
571 fprintf (ira_dump_file, "\n");
576 if (best_hard_regno >= 0)
577 allocated_hardreg_p[best_hard_regno] = true;
578 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
579 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
581 ALLOCNO_HARD_REGNO (a) = best_hard_regno;
582 ALLOCNO_ASSIGNED_P (a) = true;
583 if (best_hard_regno >= 0)
584 update_copy_costs (a, true);
585 ira_assert (ALLOCNO_COVER_CLASS (a) == cover_class);
586 /* We don't need updated costs anymore: */
587 ira_free_allocno_updated_costs (a);
591 return best_hard_regno >= 0;
596 /* This page contains the allocator based on the Chaitin-Briggs algorithm. */
598 /* Bucket of allocnos that can colored currently without spilling. */
599 static ira_allocno_t colorable_allocno_bucket;
601 /* Bucket of allocnos that might be not colored currently without
603 static ira_allocno_t uncolorable_allocno_bucket;
605 /* Each element of the array contains the current number of allocnos
606 of given *cover* class in the uncolorable_bucket. */
607 static int uncolorable_allocnos_num[N_REG_CLASSES];
609 /* Add ALLOCNO to bucket *BUCKET_PTR. ALLOCNO should be not in a bucket
612 add_ira_allocno_to_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
614 ira_allocno_t first_allocno;
615 enum reg_class cover_class;
617 if (bucket_ptr == &uncolorable_allocno_bucket
618 && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
620 uncolorable_allocnos_num[cover_class]++;
621 ira_assert (uncolorable_allocnos_num[cover_class] > 0);
623 first_allocno = *bucket_ptr;
624 ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno) = first_allocno;
625 ALLOCNO_PREV_BUCKET_ALLOCNO (allocno) = NULL;
626 if (first_allocno != NULL)
627 ALLOCNO_PREV_BUCKET_ALLOCNO (first_allocno) = allocno;
628 *bucket_ptr = allocno;
631 /* The function returns frequency and number of available hard
632 registers for allocnos coalesced with ALLOCNO. */
634 get_coalesced_allocnos_attributes (ira_allocno_t allocno, int *freq, int *num)
640 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
641 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
643 *freq += ALLOCNO_FREQ (a);
644 *num += ALLOCNO_AVAILABLE_REGS_NUM (a);
650 /* Compare two allocnos to define which allocno should be pushed first
651 into the coloring stack. If the return is a negative number, the
652 allocno given by the first parameter will be pushed first. In this
653 case such allocno has less priority than the second one and the
654 hard register will be assigned to it after assignment to the second
655 one. As the result of such assignment order, the second allocno
656 has a better chance to get the best hard register. */
658 bucket_allocno_compare_func (const void *v1p, const void *v2p)
660 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
661 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
662 int diff, a1_freq, a2_freq, a1_num, a2_num;
664 if ((diff = (int) ALLOCNO_COVER_CLASS (a2) - ALLOCNO_COVER_CLASS (a1)) != 0)
666 get_coalesced_allocnos_attributes (a1, &a1_freq, &a1_num);
667 get_coalesced_allocnos_attributes (a2, &a2_freq, &a2_num);
668 if ((diff = a2_num - a1_num) != 0)
670 else if ((diff = a1_freq - a2_freq) != 0)
672 return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
675 /* Sort bucket *BUCKET_PTR and return the result through
678 sort_bucket (ira_allocno_t *bucket_ptr)
680 ira_allocno_t a, head;
683 for (n = 0, a = *bucket_ptr; a != NULL; a = ALLOCNO_NEXT_BUCKET_ALLOCNO (a))
684 sorted_allocnos[n++] = a;
687 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
688 bucket_allocno_compare_func);
690 for (n--; n >= 0; n--)
692 a = sorted_allocnos[n];
693 ALLOCNO_NEXT_BUCKET_ALLOCNO (a) = head;
694 ALLOCNO_PREV_BUCKET_ALLOCNO (a) = NULL;
696 ALLOCNO_PREV_BUCKET_ALLOCNO (head) = a;
702 /* Add ALLOCNO to bucket *BUCKET_PTR maintaining the order according
703 their priority. ALLOCNO should be not in a bucket before the
706 add_ira_allocno_to_ordered_bucket (ira_allocno_t allocno,
707 ira_allocno_t *bucket_ptr)
709 ira_allocno_t before, after;
710 enum reg_class cover_class;
712 if (bucket_ptr == &uncolorable_allocno_bucket
713 && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
715 uncolorable_allocnos_num[cover_class]++;
716 ira_assert (uncolorable_allocnos_num[cover_class] > 0);
718 for (before = *bucket_ptr, after = NULL;
720 after = before, before = ALLOCNO_NEXT_BUCKET_ALLOCNO (before))
721 if (bucket_allocno_compare_func (&allocno, &before) < 0)
723 ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno) = before;
724 ALLOCNO_PREV_BUCKET_ALLOCNO (allocno) = after;
726 *bucket_ptr = allocno;
728 ALLOCNO_NEXT_BUCKET_ALLOCNO (after) = allocno;
730 ALLOCNO_PREV_BUCKET_ALLOCNO (before) = allocno;
733 /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
736 delete_allocno_from_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
738 ira_allocno_t prev_allocno, next_allocno;
739 enum reg_class cover_class;
741 if (bucket_ptr == &uncolorable_allocno_bucket
742 && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
744 uncolorable_allocnos_num[cover_class]--;
745 ira_assert (uncolorable_allocnos_num[cover_class] >= 0);
747 prev_allocno = ALLOCNO_PREV_BUCKET_ALLOCNO (allocno);
748 next_allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno);
749 if (prev_allocno != NULL)
750 ALLOCNO_NEXT_BUCKET_ALLOCNO (prev_allocno) = next_allocno;
753 ira_assert (*bucket_ptr == allocno);
754 *bucket_ptr = next_allocno;
756 if (next_allocno != NULL)
757 ALLOCNO_PREV_BUCKET_ALLOCNO (next_allocno) = prev_allocno;
760 /* Splay tree for each cover class. The trees are indexed by the
761 corresponding cover classes. Splay trees contain uncolorable
763 static splay_tree uncolorable_allocnos_splay_tree[N_REG_CLASSES];
765 /* If the following macro is TRUE, splay tree is used to choose an
766 allocno of the corresponding cover class for spilling. When the
767 number uncolorable allocnos of given cover class decreases to some
768 threshold, linear array search is used to find the best allocno for
769 spilling. This threshold is actually pretty big because, although
770 splay trees asymptotically is much faster, each splay tree
771 operation is sufficiently costly especially taking cache locality
773 #define USE_SPLAY_P(CLASS) (uncolorable_allocnos_num[CLASS] > 4000)
775 /* Put ALLOCNO onto the coloring stack without removing it from its
776 bucket. Pushing allocno to the coloring stack can result in moving
777 conflicting allocnos from the uncolorable bucket to the colorable
780 push_ira_allocno_to_stack (ira_allocno_t allocno)
782 int conflicts_num, conflict_size, size;
783 ira_allocno_t a, conflict_allocno;
784 enum reg_class cover_class;
785 ira_allocno_conflict_iterator aci;
787 ALLOCNO_IN_GRAPH_P (allocno) = false;
788 VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, allocno);
789 cover_class = ALLOCNO_COVER_CLASS (allocno);
790 if (cover_class == NO_REGS)
792 size = ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)];
793 if (allocno_coalesced_p)
794 bitmap_clear (processed_coalesced_allocno_bitmap);
795 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
796 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
798 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
799 if (bitmap_bit_p (coloring_allocno_bitmap,
800 ALLOCNO_NUM (conflict_allocno)))
802 ira_assert (cover_class == ALLOCNO_COVER_CLASS (conflict_allocno));
803 if (allocno_coalesced_p)
805 if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
806 ALLOCNO_NUM (conflict_allocno)))
808 bitmap_set_bit (processed_coalesced_allocno_bitmap,
809 ALLOCNO_NUM (conflict_allocno));
811 if (ALLOCNO_IN_GRAPH_P (conflict_allocno)
812 && ! ALLOCNO_ASSIGNED_P (conflict_allocno))
814 conflicts_num = ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno);
816 = (ira_reg_class_nregs
817 [cover_class][ALLOCNO_MODE (conflict_allocno)]);
819 (ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) >= size);
820 if (conflicts_num + conflict_size
821 <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno))
823 ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) -= size;
827 = ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) - size;
828 if (uncolorable_allocnos_splay_tree[cover_class] != NULL
829 && !ALLOCNO_SPLAY_REMOVED_P (conflict_allocno)
830 && USE_SPLAY_P (cover_class))
834 (uncolorable_allocnos_splay_tree[cover_class],
835 (splay_tree_key) conflict_allocno) != NULL);
837 (uncolorable_allocnos_splay_tree[cover_class],
838 (splay_tree_key) conflict_allocno);
839 ALLOCNO_SPLAY_REMOVED_P (conflict_allocno) = true;
840 VEC_safe_push (ira_allocno_t, heap,
841 removed_splay_allocno_vec,
844 ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) = conflicts_num;
845 if (conflicts_num + conflict_size
846 <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno))
848 delete_allocno_from_bucket (conflict_allocno,
849 &uncolorable_allocno_bucket);
850 add_ira_allocno_to_ordered_bucket (conflict_allocno,
851 &colorable_allocno_bucket);
860 /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
861 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
863 remove_allocno_from_bucket_and_push (ira_allocno_t allocno, bool colorable_p)
865 enum reg_class cover_class;
868 delete_allocno_from_bucket (allocno, &colorable_allocno_bucket);
870 delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
871 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
873 fprintf (ira_dump_file, " Pushing");
874 print_coalesced_allocno (allocno);
875 fprintf (ira_dump_file, "%s\n", colorable_p ? "" : "(potential spill)");
877 cover_class = ALLOCNO_COVER_CLASS (allocno);
878 ira_assert ((colorable_p
879 && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
880 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)]
881 <= ALLOCNO_AVAILABLE_REGS_NUM (allocno)))
883 && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
884 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE
886 > ALLOCNO_AVAILABLE_REGS_NUM (allocno))));
888 ALLOCNO_MAY_BE_SPILLED_P (allocno) = true;
889 push_ira_allocno_to_stack (allocno);
892 /* Put all allocnos from colorable bucket onto the coloring stack. */
894 push_only_colorable (void)
896 sort_bucket (&colorable_allocno_bucket);
897 for (;colorable_allocno_bucket != NULL;)
898 remove_allocno_from_bucket_and_push (colorable_allocno_bucket, true);
901 /* Puts ALLOCNO chosen for potential spilling onto the coloring
904 push_ira_allocno_to_spill (ira_allocno_t allocno)
906 delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
907 ALLOCNO_MAY_BE_SPILLED_P (allocno) = true;
908 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
909 fprintf (ira_dump_file, " Pushing p%d(%d) (potential spill)\n",
910 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno));
911 push_ira_allocno_to_stack (allocno);
914 /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
915 loop given by its LOOP_NODE. */
917 ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p)
922 VEC (edge, heap) *edges;
924 ira_assert (loop_node->loop != NULL
925 && (regno < 0 || regno >= FIRST_PSEUDO_REGISTER));
929 FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
930 if (e->src != loop_node->loop->latch
932 || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
933 && bitmap_bit_p (DF_LR_IN (e->dest), regno))))
934 freq += EDGE_FREQUENCY (e);
938 edges = get_loop_exit_edges (loop_node->loop);
939 for (i = 0; VEC_iterate (edge, edges, i, e); i++)
941 || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
942 && bitmap_bit_p (DF_LR_IN (e->dest), regno)))
943 freq += EDGE_FREQUENCY (e);
944 VEC_free (edge, heap, edges);
947 return REG_FREQ_FROM_EDGE_FREQ (freq);
950 /* Calculate and return the cost of putting allocno A into memory. */
952 calculate_allocno_spill_cost (ira_allocno_t a)
955 enum machine_mode mode;
956 enum reg_class rclass;
957 ira_allocno_t parent_allocno;
958 ira_loop_tree_node_t parent_node, loop_node;
960 regno = ALLOCNO_REGNO (a);
961 cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a);
962 if (ALLOCNO_CAP (a) != NULL)
964 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
965 if ((parent_node = loop_node->parent) == NULL)
967 if ((parent_allocno = parent_node->regno_allocno_map[regno]) == NULL)
969 mode = ALLOCNO_MODE (a);
970 rclass = ALLOCNO_COVER_CLASS (a);
971 if (ALLOCNO_HARD_REGNO (parent_allocno) < 0)
972 cost -= (ira_memory_move_cost[mode][rclass][0]
973 * ira_loop_edge_freq (loop_node, regno, true)
974 + ira_memory_move_cost[mode][rclass][1]
975 * ira_loop_edge_freq (loop_node, regno, false));
977 cost += ((ira_memory_move_cost[mode][rclass][1]
978 * ira_loop_edge_freq (loop_node, regno, true)
979 + ira_memory_move_cost[mode][rclass][0]
980 * ira_loop_edge_freq (loop_node, regno, false))
981 - (ira_register_move_cost[mode][rclass][rclass]
982 * (ira_loop_edge_freq (loop_node, regno, false)
983 + ira_loop_edge_freq (loop_node, regno, true))));
987 /* Compare keys in the splay tree used to choose best allocno for
988 spilling. The best allocno has the minimal key. */
990 allocno_spill_priority_compare (splay_tree_key k1, splay_tree_key k2)
992 int pri1, pri2, diff;
993 ira_allocno_t a1 = (ira_allocno_t) k1, a2 = (ira_allocno_t) k2;
995 pri1 = (IRA_ALLOCNO_TEMP (a1)
996 / (ALLOCNO_LEFT_CONFLICTS_NUM (a1)
997 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a1)][ALLOCNO_MODE (a1)]
999 pri2 = (IRA_ALLOCNO_TEMP (a2)
1000 / (ALLOCNO_LEFT_CONFLICTS_NUM (a2)
1001 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a2)][ALLOCNO_MODE (a2)]
1003 if ((diff = pri1 - pri2) != 0)
1005 if ((diff = IRA_ALLOCNO_TEMP (a1) - IRA_ALLOCNO_TEMP (a2)) != 0)
1007 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
1010 /* Allocate data of SIZE for the splay trees. We allocate only spay
1011 tree roots or splay tree nodes. If you change this, please rewrite
1014 splay_tree_allocate (int size, void *data ATTRIBUTE_UNUSED)
1016 if (size != sizeof (struct splay_tree_node_s))
1017 return ira_allocate (size);
1018 return pool_alloc (splay_tree_node_pool);
1021 /* Free data NODE for the splay trees. We allocate and free only spay
1022 tree roots or splay tree nodes. If you change this, please rewrite
1025 splay_tree_free (void *node, void *data ATTRIBUTE_UNUSED)
1028 enum reg_class cover_class;
1030 for (i = 0; i < ira_reg_class_cover_size; i++)
1032 cover_class = ira_reg_class_cover[i];
1033 if (node == uncolorable_allocnos_splay_tree[cover_class])
1039 pool_free (splay_tree_node_pool, node);
1042 /* Push allocnos to the coloring stack. The order of allocnos in the
1043 stack defines the order for the subsequent coloring. */
1045 push_allocnos_to_stack (void)
1047 ira_allocno_t allocno, a, i_allocno, *allocno_vec;
1048 enum reg_class cover_class, rclass;
1049 int allocno_pri, i_allocno_pri, allocno_cost, i_allocno_cost;
1050 int i, j, num, cover_class_allocnos_num[N_REG_CLASSES];
1051 ira_allocno_t *cover_class_allocnos[N_REG_CLASSES];
1055 VEC_truncate(ira_allocno_t, removed_splay_allocno_vec, 0);
1056 for (i = 0; i < ira_reg_class_cover_size; i++)
1058 cover_class = ira_reg_class_cover[i];
1059 cover_class_allocnos_num[cover_class] = 0;
1060 cover_class_allocnos[cover_class] = NULL;
1061 uncolorable_allocnos_splay_tree[cover_class] = NULL;
1063 /* Calculate uncolorable allocno spill costs. */
1064 for (allocno = uncolorable_allocno_bucket;
1066 allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno))
1067 if ((cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
1069 cover_class_allocnos_num[cover_class]++;
1071 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1072 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1074 cost += calculate_allocno_spill_cost (a);
1078 /* ??? Remove cost of copies between the coalesced
1080 IRA_ALLOCNO_TEMP (allocno) = cost;
1082 /* Define place where to put uncolorable allocnos of the same cover
1084 for (num = i = 0; i < ira_reg_class_cover_size; i++)
1086 cover_class = ira_reg_class_cover[i];
1087 ira_assert (cover_class_allocnos_num[cover_class]
1088 == uncolorable_allocnos_num[cover_class]);
1089 if (cover_class_allocnos_num[cover_class] != 0)
1091 cover_class_allocnos[cover_class] = allocnos_for_spilling + num;
1092 num += cover_class_allocnos_num[cover_class];
1093 cover_class_allocnos_num[cover_class] = 0;
1095 if (USE_SPLAY_P (cover_class))
1096 uncolorable_allocnos_splay_tree[cover_class]
1097 = splay_tree_new_with_allocator (allocno_spill_priority_compare,
1098 NULL, NULL, splay_tree_allocate,
1099 splay_tree_free, NULL);
1101 ira_assert (num <= ira_allocnos_num);
1102 /* Collect uncolorable allocnos of each cover class. */
1103 for (allocno = uncolorable_allocno_bucket;
1105 allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno))
1106 if ((cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
1108 cover_class_allocnos
1109 [cover_class][cover_class_allocnos_num[cover_class]++] = allocno;
1110 if (uncolorable_allocnos_splay_tree[cover_class] != NULL)
1111 splay_tree_insert (uncolorable_allocnos_splay_tree[cover_class],
1112 (splay_tree_key) allocno,
1113 (splay_tree_value) allocno);
1117 push_only_colorable ();
1118 allocno = uncolorable_allocno_bucket;
1119 if (allocno == NULL)
1121 cover_class = ALLOCNO_COVER_CLASS (allocno);
1122 if (cover_class == NO_REGS)
1124 push_ira_allocno_to_spill (allocno);
1127 /* Potential spilling. */
1129 (ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)] > 0);
1130 if (USE_SPLAY_P (cover_class))
1132 for (;VEC_length (ira_allocno_t, removed_splay_allocno_vec) != 0;)
1134 allocno = VEC_pop (ira_allocno_t, removed_splay_allocno_vec);
1135 ALLOCNO_SPLAY_REMOVED_P (allocno) = false;
1136 rclass = ALLOCNO_COVER_CLASS (allocno);
1137 if (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
1138 + ira_reg_class_nregs [rclass][ALLOCNO_MODE (allocno)]
1139 > ALLOCNO_AVAILABLE_REGS_NUM (allocno))
1141 (uncolorable_allocnos_splay_tree[rclass],
1142 (splay_tree_key) allocno, (splay_tree_value) allocno);
1144 allocno = ((ira_allocno_t)
1146 (uncolorable_allocnos_splay_tree[cover_class])->key);
1147 splay_tree_remove (uncolorable_allocnos_splay_tree[cover_class],
1148 (splay_tree_key) allocno);
1152 num = cover_class_allocnos_num[cover_class];
1153 ira_assert (num > 0);
1154 allocno_vec = cover_class_allocnos[cover_class];
1156 allocno_pri = allocno_cost = 0;
1157 /* Sort uncolorable allocno to find the one with the lowest
1159 for (i = 0, j = num - 1; i <= j;)
1161 i_allocno = allocno_vec[i];
1162 if (! ALLOCNO_IN_GRAPH_P (i_allocno)
1163 && ALLOCNO_IN_GRAPH_P (allocno_vec[j]))
1165 i_allocno = allocno_vec[j];
1166 allocno_vec[j] = allocno_vec[i];
1167 allocno_vec[i] = i_allocno;
1169 if (ALLOCNO_IN_GRAPH_P (i_allocno))
1172 if (IRA_ALLOCNO_TEMP (i_allocno) == INT_MAX)
1177 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (i_allocno);;
1178 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1180 cost += calculate_allocno_spill_cost (i_allocno);
1184 /* ??? Remove cost of copies between the coalesced
1186 IRA_ALLOCNO_TEMP (i_allocno) = cost;
1188 i_allocno_cost = IRA_ALLOCNO_TEMP (i_allocno);
1191 / (ALLOCNO_LEFT_CONFLICTS_NUM (i_allocno)
1192 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS
1194 [ALLOCNO_MODE (i_allocno)] + 1));
1195 if (allocno == NULL || allocno_pri > i_allocno_pri
1196 || (allocno_pri == i_allocno_pri
1197 && (allocno_cost > i_allocno_cost
1198 || (allocno_cost == i_allocno_cost
1199 && (ALLOCNO_NUM (allocno)
1200 > ALLOCNO_NUM (i_allocno))))))
1202 allocno = i_allocno;
1203 allocno_cost = i_allocno_cost;
1204 allocno_pri = i_allocno_pri;
1207 if (! ALLOCNO_IN_GRAPH_P (allocno_vec[j]))
1210 ira_assert (allocno != NULL && j >= 0);
1211 cover_class_allocnos_num[cover_class] = j + 1;
1213 ira_assert (ALLOCNO_IN_GRAPH_P (allocno)
1214 && ALLOCNO_COVER_CLASS (allocno) == cover_class
1215 && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
1216 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE
1218 > ALLOCNO_AVAILABLE_REGS_NUM (allocno)));
1219 remove_allocno_from_bucket_and_push (allocno, false);
1221 ira_assert (colorable_allocno_bucket == NULL
1222 && uncolorable_allocno_bucket == NULL);
1223 for (i = 0; i < ira_reg_class_cover_size; i++)
1225 cover_class = ira_reg_class_cover[i];
1226 ira_assert (uncolorable_allocnos_num[cover_class] == 0);
1227 if (uncolorable_allocnos_splay_tree[cover_class] != NULL)
1228 splay_tree_delete (uncolorable_allocnos_splay_tree[cover_class]);
1232 /* Pop the coloring stack and assign hard registers to the popped
1235 pop_allocnos_from_stack (void)
1237 ira_allocno_t allocno;
1238 enum reg_class cover_class;
1240 for (;VEC_length (ira_allocno_t, allocno_stack_vec) != 0;)
1242 allocno = VEC_pop (ira_allocno_t, allocno_stack_vec);
1243 cover_class = ALLOCNO_COVER_CLASS (allocno);
1244 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1246 fprintf (ira_dump_file, " Popping");
1247 print_coalesced_allocno (allocno);
1248 fprintf (ira_dump_file, " -- ");
1250 if (cover_class == NO_REGS)
1252 ALLOCNO_HARD_REGNO (allocno) = -1;
1253 ALLOCNO_ASSIGNED_P (allocno) = true;
1254 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno) == NULL);
1256 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno) == NULL);
1257 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1258 fprintf (ira_dump_file, "assign memory\n");
1260 else if (assign_hard_reg (allocno, false))
1262 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1263 fprintf (ira_dump_file, "assign reg %d\n",
1264 ALLOCNO_HARD_REGNO (allocno));
1266 else if (ALLOCNO_ASSIGNED_P (allocno))
1268 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1269 fprintf (ira_dump_file, "spill\n");
1271 ALLOCNO_IN_GRAPH_P (allocno) = true;
1275 /* Set up number of available hard registers for ALLOCNO. */
1277 setup_allocno_available_regs_num (ira_allocno_t allocno)
1279 int i, n, hard_regs_num;
1280 enum reg_class cover_class;
1282 HARD_REG_SET temp_set;
1284 cover_class = ALLOCNO_COVER_CLASS (allocno);
1285 ALLOCNO_AVAILABLE_REGS_NUM (allocno) = ira_available_class_regs[cover_class];
1286 if (cover_class == NO_REGS)
1288 CLEAR_HARD_REG_SET (temp_set);
1289 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) == allocno);
1290 hard_regs_num = ira_class_hard_regs_num[cover_class];
1291 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1292 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1294 IOR_HARD_REG_SET (temp_set, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1298 for (n = 0, i = hard_regs_num - 1; i >= 0; i--)
1299 if (TEST_HARD_REG_BIT (temp_set, ira_class_hard_regs[cover_class][i]))
1301 if (internal_flag_ira_verbose > 2 && n > 0 && ira_dump_file != NULL)
1302 fprintf (ira_dump_file, " Reg %d of %s has %d regs less\n",
1303 ALLOCNO_REGNO (allocno), reg_class_names[cover_class], n);
1304 ALLOCNO_AVAILABLE_REGS_NUM (allocno) -= n;
1307 /* Set up ALLOCNO_LEFT_CONFLICTS_NUM for ALLOCNO. */
1309 setup_allocno_left_conflicts_num (ira_allocno_t allocno)
1311 int i, hard_regs_num, hard_regno, conflict_allocnos_size;
1312 ira_allocno_t a, conflict_allocno;
1313 enum reg_class cover_class;
1314 HARD_REG_SET temp_set;
1315 ira_allocno_conflict_iterator aci;
1317 cover_class = ALLOCNO_COVER_CLASS (allocno);
1318 hard_regs_num = ira_class_hard_regs_num[cover_class];
1319 CLEAR_HARD_REG_SET (temp_set);
1320 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) == allocno);
1321 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1322 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1324 IOR_HARD_REG_SET (temp_set, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1328 AND_HARD_REG_SET (temp_set, reg_class_contents[cover_class]);
1329 AND_COMPL_HARD_REG_SET (temp_set, ira_no_alloc_regs);
1330 conflict_allocnos_size = 0;
1331 if (! hard_reg_set_empty_p (temp_set))
1332 for (i = 0; i < (int) hard_regs_num; i++)
1334 hard_regno = ira_class_hard_regs[cover_class][i];
1335 if (TEST_HARD_REG_BIT (temp_set, hard_regno))
1337 conflict_allocnos_size++;
1338 CLEAR_HARD_REG_BIT (temp_set, hard_regno);
1339 if (hard_reg_set_empty_p (temp_set))
1343 CLEAR_HARD_REG_SET (temp_set);
1344 if (allocno_coalesced_p)
1345 bitmap_clear (processed_coalesced_allocno_bitmap);
1346 if (cover_class != NO_REGS)
1347 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1348 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1350 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
1351 if (bitmap_bit_p (consideration_allocno_bitmap,
1352 ALLOCNO_NUM (conflict_allocno)))
1354 ira_assert (cover_class
1355 == ALLOCNO_COVER_CLASS (conflict_allocno));
1356 if (allocno_coalesced_p)
1358 if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
1359 ALLOCNO_NUM (conflict_allocno)))
1361 bitmap_set_bit (processed_coalesced_allocno_bitmap,
1362 ALLOCNO_NUM (conflict_allocno));
1364 if (! ALLOCNO_ASSIGNED_P (conflict_allocno))
1365 conflict_allocnos_size
1366 += (ira_reg_class_nregs
1367 [cover_class][ALLOCNO_MODE (conflict_allocno)]);
1368 else if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno))
1371 int last = (hard_regno
1373 [hard_regno][ALLOCNO_MODE (conflict_allocno)]);
1375 while (hard_regno < last)
1377 if (! TEST_HARD_REG_BIT (temp_set, hard_regno))
1379 conflict_allocnos_size++;
1380 SET_HARD_REG_BIT (temp_set, hard_regno);
1389 ALLOCNO_LEFT_CONFLICTS_NUM (allocno) = conflict_allocnos_size;
1392 /* Put ALLOCNO in a bucket corresponding to its number and size of its
1393 conflicting allocnos and hard registers. */
1395 put_allocno_into_bucket (ira_allocno_t allocno)
1398 enum reg_class cover_class;
1400 cover_class = ALLOCNO_COVER_CLASS (allocno);
1401 hard_regs_num = ira_class_hard_regs_num[cover_class];
1402 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
1404 ALLOCNO_IN_GRAPH_P (allocno) = true;
1405 setup_allocno_left_conflicts_num (allocno);
1406 setup_allocno_available_regs_num (allocno);
1407 if (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
1408 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)]
1409 <= ALLOCNO_AVAILABLE_REGS_NUM (allocno))
1410 add_ira_allocno_to_bucket (allocno, &colorable_allocno_bucket);
1412 add_ira_allocno_to_bucket (allocno, &uncolorable_allocno_bucket);
1415 /* The function is used to sort allocnos according to their execution
1418 copy_freq_compare_func (const void *v1p, const void *v2p)
1420 ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p;
1428 /* If freqencies are equal, sort by copies, so that the results of
1429 qsort leave nothing to chance. */
1430 return cp1->num - cp2->num;
1433 /* Merge two sets of coalesced allocnos given correspondingly by
1434 allocnos A1 and A2 (more accurately merging A2 set into A1
1437 merge_allocnos (ira_allocno_t a1, ira_allocno_t a2)
1439 ira_allocno_t a, first, last, next;
1441 first = ALLOCNO_FIRST_COALESCED_ALLOCNO (a1);
1442 if (first == ALLOCNO_FIRST_COALESCED_ALLOCNO (a2))
1444 for (last = a2, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
1445 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1447 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = first;
1452 next = ALLOCNO_NEXT_COALESCED_ALLOCNO (first);
1453 ALLOCNO_NEXT_COALESCED_ALLOCNO (first) = a2;
1454 ALLOCNO_NEXT_COALESCED_ALLOCNO (last) = next;
1457 /* Return TRUE if there are conflicting allocnos from two sets of
1458 coalesced allocnos given correspondingly by allocnos A1 and A2. If
1459 RELOAD_P is TRUE, we use live ranges to find conflicts because
1460 conflicts are represented only for allocnos of the same cover class
1461 and during the reload pass we coalesce allocnos for sharing stack
1464 coalesced_allocno_conflict_p (ira_allocno_t a1, ira_allocno_t a2,
1467 ira_allocno_t a, conflict_allocno;
1468 ira_allocno_conflict_iterator aci;
1470 if (allocno_coalesced_p)
1472 bitmap_clear (processed_coalesced_allocno_bitmap);
1473 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
1474 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1476 bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a));
1481 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
1482 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1486 for (conflict_allocno = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
1488 = ALLOCNO_NEXT_COALESCED_ALLOCNO (conflict_allocno))
1490 if (ira_allocno_live_ranges_intersect_p (a, conflict_allocno))
1492 if (conflict_allocno == a1)
1498 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
1499 if (conflict_allocno == a1
1500 || (allocno_coalesced_p
1501 && bitmap_bit_p (processed_coalesced_allocno_bitmap,
1502 ALLOCNO_NUM (conflict_allocno))))
1511 /* The major function for aggressive allocno coalescing. For the
1512 reload pass (RELOAD_P) we coalesce only spilled allocnos. If some
1513 allocnos have been coalesced, we set up flag
1514 allocno_coalesced_p. */
1516 coalesce_allocnos (bool reload_p)
1519 ira_copy_t cp, next_cp, *sorted_copies;
1520 enum reg_class cover_class;
1521 enum machine_mode mode;
1523 int i, n, cp_num, regno;
1526 sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num
1527 * sizeof (ira_copy_t));
1529 /* Collect copies. */
1530 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
1532 a = ira_allocnos[j];
1533 regno = ALLOCNO_REGNO (a);
1534 if ((! reload_p && ALLOCNO_ASSIGNED_P (a))
1536 && (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0
1537 || (regno < ira_reg_equiv_len
1538 && (ira_reg_equiv_const[regno] != NULL_RTX
1539 || ira_reg_equiv_invariant_p[regno])))))
1541 cover_class = ALLOCNO_COVER_CLASS (a);
1542 mode = ALLOCNO_MODE (a);
1543 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
1547 next_cp = cp->next_first_allocno_copy;
1548 regno = ALLOCNO_REGNO (cp->second);
1550 || (ALLOCNO_COVER_CLASS (cp->second) == cover_class
1551 && ALLOCNO_MODE (cp->second) == mode))
1553 && ((! reload_p && ! ALLOCNO_ASSIGNED_P (cp->second))
1555 && ALLOCNO_ASSIGNED_P (cp->second)
1556 && ALLOCNO_HARD_REGNO (cp->second) < 0
1557 && (regno >= ira_reg_equiv_len
1558 || (! ira_reg_equiv_invariant_p[regno]
1559 && ira_reg_equiv_const[regno] == NULL_RTX)))))
1560 sorted_copies[cp_num++] = cp;
1562 else if (cp->second == a)
1563 next_cp = cp->next_second_allocno_copy;
1568 qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
1569 /* Coalesced copies, most frequently executed first. */
1570 for (; cp_num != 0;)
1572 for (i = 0; i < cp_num; i++)
1574 cp = sorted_copies[i];
1575 if (! coalesced_allocno_conflict_p (cp->first, cp->second, reload_p))
1577 allocno_coalesced_p = true;
1578 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1581 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
1582 cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
1583 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
1585 merge_allocnos (cp->first, cp->second);
1590 /* Collect the rest of copies. */
1591 for (n = 0; i < cp_num; i++)
1593 cp = sorted_copies[i];
1594 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->first)
1595 != ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->second))
1596 sorted_copies[n++] = cp;
1600 ira_free (sorted_copies);
1603 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
1604 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
1606 color_allocnos (void)
1612 allocno_coalesced_p = false;
1613 processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
1614 if (flag_ira_coalesce)
1615 coalesce_allocnos (false);
1616 /* Put the allocnos into the corresponding buckets. */
1617 colorable_allocno_bucket = NULL;
1618 uncolorable_allocno_bucket = NULL;
1619 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1621 a = ira_allocnos[i];
1622 if (ALLOCNO_COVER_CLASS (a) == NO_REGS)
1624 ALLOCNO_HARD_REGNO (a) = -1;
1625 ALLOCNO_ASSIGNED_P (a) = true;
1626 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
1627 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
1628 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1630 fprintf (ira_dump_file, " Spill");
1631 print_coalesced_allocno (a);
1632 fprintf (ira_dump_file, "\n");
1636 put_allocno_into_bucket (a);
1638 push_allocnos_to_stack ();
1639 pop_allocnos_from_stack ();
1640 if (flag_ira_coalesce)
1641 /* We don't need coalesced allocnos for ira_reassign_pseudos. */
1642 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1644 a = ira_allocnos[i];
1645 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
1646 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
1648 ira_free_bitmap (processed_coalesced_allocno_bitmap);
1649 allocno_coalesced_p = false;
1654 /* Output information about the loop given by its LOOP_TREE_NODE. */
1656 print_loop_title (ira_loop_tree_node_t loop_tree_node)
1661 ira_assert (loop_tree_node->loop != NULL);
1662 fprintf (ira_dump_file,
1663 "\n Loop %d (parent %d, header bb%d, depth %d)\n all:",
1664 loop_tree_node->loop->num,
1665 (loop_tree_node->parent == NULL
1666 ? -1 : loop_tree_node->parent->loop->num),
1667 loop_tree_node->loop->header->index,
1668 loop_depth (loop_tree_node->loop));
1669 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
1670 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
1671 fprintf (ira_dump_file, "\n modified regnos:");
1672 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->modified_regnos, 0, j, bi)
1673 fprintf (ira_dump_file, " %d", j);
1674 fprintf (ira_dump_file, "\n border:");
1675 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->border_allocnos, 0, j, bi)
1676 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
1677 fprintf (ira_dump_file, "\n Pressure:");
1678 for (j = 0; (int) j < ira_reg_class_cover_size; j++)
1680 enum reg_class cover_class;
1682 cover_class = ira_reg_class_cover[j];
1683 if (loop_tree_node->reg_pressure[cover_class] == 0)
1685 fprintf (ira_dump_file, " %s=%d", reg_class_names[cover_class],
1686 loop_tree_node->reg_pressure[cover_class]);
1688 fprintf (ira_dump_file, "\n");
1691 /* Color the allocnos inside loop (in the extreme case it can be all
1692 of the function) given the corresponding LOOP_TREE_NODE. The
1693 function is called for each loop during top-down traverse of the
1696 color_pass (ira_loop_tree_node_t loop_tree_node)
1698 int regno, hard_regno, index = -1;
1699 int cost, exit_freq, enter_freq;
1702 enum machine_mode mode;
1703 enum reg_class rclass, cover_class;
1704 ira_allocno_t a, subloop_allocno;
1705 ira_loop_tree_node_t subloop_node;
1707 ira_assert (loop_tree_node->bb == NULL);
1708 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1709 print_loop_title (loop_tree_node);
1711 bitmap_copy (coloring_allocno_bitmap, loop_tree_node->all_allocnos);
1712 bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap);
1713 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
1715 a = ira_allocnos[j];
1716 if (! ALLOCNO_ASSIGNED_P (a))
1718 bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a));
1720 /* Color all mentioned allocnos including transparent ones. */
1722 /* Process caps. They are processed just once. */
1723 if (flag_ira_algorithm == IRA_ALGORITHM_MIXED
1724 || flag_ira_algorithm == IRA_ALGORITHM_REGIONAL)
1725 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
1727 a = ira_allocnos[j];
1728 if (ALLOCNO_CAP_MEMBER (a) == NULL)
1730 /* Remove from processing in the next loop. */
1731 bitmap_clear_bit (consideration_allocno_bitmap, j);
1732 rclass = ALLOCNO_COVER_CLASS (a);
1733 if ((flag_ira_algorithm == IRA_ALGORITHM_MIXED
1734 && loop_tree_node->reg_pressure[rclass]
1735 <= ira_available_class_regs[rclass]))
1737 mode = ALLOCNO_MODE (a);
1738 hard_regno = ALLOCNO_HARD_REGNO (a);
1739 if (hard_regno >= 0)
1741 index = ira_class_hard_reg_index[rclass][hard_regno];
1742 ira_assert (index >= 0);
1744 regno = ALLOCNO_REGNO (a);
1745 subloop_allocno = ALLOCNO_CAP_MEMBER (a);
1746 subloop_node = ALLOCNO_LOOP_TREE_NODE (subloop_allocno);
1747 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno));
1748 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
1749 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
1750 if (hard_regno >= 0)
1751 update_copy_costs (subloop_allocno, true);
1752 /* We don't need updated costs anymore: */
1753 ira_free_allocno_updated_costs (subloop_allocno);
1756 /* Update costs of the corresponding allocnos (not caps) in the
1758 for (subloop_node = loop_tree_node->subloops;
1759 subloop_node != NULL;
1760 subloop_node = subloop_node->subloop_next)
1762 ira_assert (subloop_node->bb == NULL);
1763 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
1765 a = ira_allocnos[j];
1766 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
1767 mode = ALLOCNO_MODE (a);
1768 rclass = ALLOCNO_COVER_CLASS (a);
1769 hard_regno = ALLOCNO_HARD_REGNO (a);
1770 if (hard_regno >= 0)
1772 index = ira_class_hard_reg_index[rclass][hard_regno];
1773 ira_assert (index >= 0);
1775 regno = ALLOCNO_REGNO (a);
1776 /* ??? conflict costs */
1777 subloop_allocno = subloop_node->regno_allocno_map[regno];
1778 if (subloop_allocno == NULL
1779 || ALLOCNO_CAP (subloop_allocno) != NULL)
1781 ira_assert (bitmap_bit_p (subloop_node->all_allocnos,
1782 ALLOCNO_NUM (subloop_allocno)));
1783 if (flag_ira_algorithm == IRA_ALGORITHM_MIXED
1784 && (loop_tree_node->reg_pressure[rclass]
1785 <= ira_available_class_regs[rclass]))
1787 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
1789 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
1790 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
1791 if (hard_regno >= 0)
1792 update_copy_costs (subloop_allocno, true);
1793 /* We don't need updated costs anymore: */
1794 ira_free_allocno_updated_costs (subloop_allocno);
1798 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
1799 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
1800 ira_assert (regno < ira_reg_equiv_len);
1801 if (ira_reg_equiv_invariant_p[regno]
1802 || ira_reg_equiv_const[regno] != NULL_RTX)
1804 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
1806 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
1807 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
1808 if (hard_regno >= 0)
1809 update_copy_costs (subloop_allocno, true);
1810 /* We don't need updated costs anymore: */
1811 ira_free_allocno_updated_costs (subloop_allocno);
1814 else if (hard_regno < 0)
1816 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
1817 -= ((ira_memory_move_cost[mode][rclass][1] * enter_freq)
1818 + (ira_memory_move_cost[mode][rclass][0] * exit_freq));
1822 cover_class = ALLOCNO_COVER_CLASS (subloop_allocno);
1823 ira_allocate_and_set_costs
1824 (&ALLOCNO_HARD_REG_COSTS (subloop_allocno), cover_class,
1825 ALLOCNO_COVER_CLASS_COST (subloop_allocno));
1826 ira_allocate_and_set_costs
1827 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno),
1829 cost = (ira_register_move_cost[mode][rclass][rclass]
1830 * (exit_freq + enter_freq));
1831 ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
1832 ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
1834 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
1835 += (ira_memory_move_cost[mode][rclass][0] * enter_freq
1836 + ira_memory_move_cost[mode][rclass][1] * exit_freq);
1837 if (ALLOCNO_COVER_CLASS_COST (subloop_allocno)
1838 > ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index])
1839 ALLOCNO_COVER_CLASS_COST (subloop_allocno)
1840 = ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index];
1846 /* Initialize the common data for coloring and calls functions to do
1847 Chaitin-Briggs and regional coloring. */
1851 coloring_allocno_bitmap = ira_allocate_bitmap ();
1852 allocnos_for_spilling
1853 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
1854 * ira_allocnos_num);
1855 splay_tree_node_pool = create_alloc_pool ("splay tree nodes",
1856 sizeof (struct splay_tree_node_s),
1858 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
1859 fprintf (ira_dump_file, "\n**** Allocnos coloring:\n\n");
1861 ira_traverse_loop_tree (false, ira_loop_tree_root, color_pass, NULL);
1863 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1864 ira_print_disposition (ira_dump_file);
1866 free_alloc_pool (splay_tree_node_pool);
1867 ira_free_bitmap (coloring_allocno_bitmap);
1868 ira_free (allocnos_for_spilling);
1873 /* Move spill/restore code, which are to be generated in ira-emit.c,
1874 to less frequent points (if it is profitable) by reassigning some
1875 allocnos (in loop with subloops containing in another loop) to
1876 memory which results in longer live-range where the corresponding
1877 pseudo-registers will be in memory. */
1879 move_spill_restore (void)
1881 int cost, regno, hard_regno, hard_regno2, index;
1883 int enter_freq, exit_freq;
1884 enum machine_mode mode;
1885 enum reg_class rclass;
1886 ira_allocno_t a, parent_allocno, subloop_allocno;
1887 ira_loop_tree_node_t parent, loop_node, subloop_node;
1888 ira_allocno_iterator ai;
1893 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
1894 fprintf (ira_dump_file, "New iteration of spill/restore move\n");
1895 FOR_EACH_ALLOCNO (a, ai)
1897 regno = ALLOCNO_REGNO (a);
1898 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
1899 if (ALLOCNO_CAP_MEMBER (a) != NULL
1900 || ALLOCNO_CAP (a) != NULL
1901 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0
1902 || loop_node->children == NULL
1903 /* don't do the optimization because it can create
1904 copies and the reload pass can spill the allocno set
1905 by copy although the allocno will not get memory
1907 || ira_reg_equiv_invariant_p[regno]
1908 || ira_reg_equiv_const[regno] != NULL_RTX
1909 || !bitmap_bit_p (loop_node->border_allocnos, ALLOCNO_NUM (a)))
1911 mode = ALLOCNO_MODE (a);
1912 rclass = ALLOCNO_COVER_CLASS (a);
1913 index = ira_class_hard_reg_index[rclass][hard_regno];
1914 ira_assert (index >= 0);
1915 cost = (ALLOCNO_MEMORY_COST (a)
1916 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
1917 ? ALLOCNO_COVER_CLASS_COST (a)
1918 : ALLOCNO_HARD_REG_COSTS (a)[index]));
1919 for (subloop_node = loop_node->subloops;
1920 subloop_node != NULL;
1921 subloop_node = subloop_node->subloop_next)
1923 ira_assert (subloop_node->bb == NULL);
1924 subloop_allocno = subloop_node->regno_allocno_map[regno];
1925 if (subloop_allocno == NULL)
1927 /* We have accumulated cost. To get the real cost of
1928 allocno usage in the loop we should subtract costs of
1929 the subloop allocnos. */
1930 cost -= (ALLOCNO_MEMORY_COST (subloop_allocno)
1931 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno) == NULL
1932 ? ALLOCNO_COVER_CLASS_COST (subloop_allocno)
1933 : ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index]));
1934 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
1935 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
1936 if ((hard_regno2 = ALLOCNO_HARD_REGNO (subloop_allocno)) < 0)
1937 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
1938 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
1942 += (ira_memory_move_cost[mode][rclass][0] * exit_freq
1943 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
1944 if (hard_regno2 != hard_regno)
1945 cost -= (ira_register_move_cost[mode][rclass][rclass]
1946 * (exit_freq + enter_freq));
1949 if ((parent = loop_node->parent) != NULL
1950 && (parent_allocno = parent->regno_allocno_map[regno]) != NULL)
1952 exit_freq = ira_loop_edge_freq (loop_node, regno, true);
1953 enter_freq = ira_loop_edge_freq (loop_node, regno, false);
1954 if ((hard_regno2 = ALLOCNO_HARD_REGNO (parent_allocno)) < 0)
1955 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
1956 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
1960 += (ira_memory_move_cost[mode][rclass][1] * exit_freq
1961 + ira_memory_move_cost[mode][rclass][0] * enter_freq);
1962 if (hard_regno2 != hard_regno)
1963 cost -= (ira_register_move_cost[mode][rclass][rclass]
1964 * (exit_freq + enter_freq));
1969 ALLOCNO_HARD_REGNO (a) = -1;
1970 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1974 " Moving spill/restore for a%dr%d up from loop %d",
1975 ALLOCNO_NUM (a), regno, loop_node->loop->num);
1976 fprintf (ira_dump_file, " - profit %d\n", -cost);
1988 /* Update current hard reg costs and current conflict hard reg costs
1989 for allocno A. It is done by processing its copies containing
1990 other allocnos already assigned. */
1992 update_curr_costs (ira_allocno_t a)
1994 int i, hard_regno, cost;
1995 enum machine_mode mode;
1996 enum reg_class cover_class, rclass;
1997 ira_allocno_t another_a;
1998 ira_copy_t cp, next_cp;
2000 ira_assert (! ALLOCNO_ASSIGNED_P (a));
2001 cover_class = ALLOCNO_COVER_CLASS (a);
2002 if (cover_class == NO_REGS)
2004 mode = ALLOCNO_MODE (a);
2005 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2009 next_cp = cp->next_first_allocno_copy;
2010 another_a = cp->second;
2012 else if (cp->second == a)
2014 next_cp = cp->next_second_allocno_copy;
2015 another_a = cp->first;
2019 if (cover_class != ALLOCNO_COVER_CLASS (another_a)
2020 || ! ALLOCNO_ASSIGNED_P (another_a)
2021 || (hard_regno = ALLOCNO_HARD_REGNO (another_a)) < 0)
2023 rclass = REGNO_REG_CLASS (hard_regno);
2024 i = ira_class_hard_reg_index[cover_class][hard_regno];
2025 ira_assert (i >= 0);
2026 cost = (cp->first == a
2027 ? ira_register_move_cost[mode][rclass][cover_class]
2028 : ira_register_move_cost[mode][cover_class][rclass]);
2029 ira_allocate_and_set_or_copy_costs
2030 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
2031 cover_class, ALLOCNO_COVER_CLASS_COST (a),
2032 ALLOCNO_HARD_REG_COSTS (a));
2033 ira_allocate_and_set_or_copy_costs
2034 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
2035 cover_class, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
2036 ALLOCNO_UPDATED_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
2037 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
2041 /* Map: allocno number -> allocno priority. */
2042 static int *allocno_priorities;
2044 /* Allocate array ALLOCNO_PRIORITIES and set up priorities for N allocnos in
2045 array CONSIDERATION_ALLOCNOS. */
2047 start_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
2051 allocno_live_range_t r;
2053 for (i = 0; i < n; i++)
2055 a = consideration_allocnos[i];
2056 for (length = 0, r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
2057 length += r->finish - r->start + 1;
2060 allocno_priorities[ALLOCNO_NUM (a)] = 0;
2063 ira_assert (length > 0 && ALLOCNO_NREFS (a) >= 0);
2064 allocno_priorities[ALLOCNO_NUM (a)]
2065 = (((double) (floor_log2 (ALLOCNO_NREFS (a)) * ALLOCNO_FREQ (a))
2067 * (10000 / REG_FREQ_MAX) * PSEUDO_REGNO_SIZE (ALLOCNO_REGNO (a)));
2071 /* Sort allocnos according to their priorities which are calculated
2072 analogous to ones in file `global.c'. */
2074 allocno_priority_compare_func (const void *v1p, const void *v2p)
2076 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2077 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2080 pri1 = allocno_priorities[ALLOCNO_NUM (a1)];
2081 pri2 = allocno_priorities[ALLOCNO_NUM (a2)];
2085 /* If regs are equally good, sort by allocnos, so that the results of
2086 qsort leave nothing to chance. */
2087 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2090 /* Try to assign hard registers to the unassigned allocnos and
2091 allocnos conflicting with them or conflicting with allocnos whose
2092 regno >= START_REGNO. The function is called after ira_flattening,
2093 so more allocnos (including ones created in ira-emit.c) will have a
2094 chance to get a hard register. We use simple assignment algorithm
2095 based on priorities. */
2097 ira_reassign_conflict_allocnos (int start_regno)
2099 int i, allocnos_to_color_num;
2100 ira_allocno_t a, conflict_a;
2101 ira_allocno_conflict_iterator aci;
2102 enum reg_class cover_class;
2103 bitmap allocnos_to_color;
2104 ira_allocno_iterator ai;
2106 allocnos_to_color = ira_allocate_bitmap ();
2107 allocnos_to_color_num = 0;
2108 FOR_EACH_ALLOCNO (a, ai)
2110 if (! ALLOCNO_ASSIGNED_P (a)
2111 && ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a)))
2113 if (ALLOCNO_COVER_CLASS (a) != NO_REGS)
2114 sorted_allocnos[allocnos_to_color_num++] = a;
2117 ALLOCNO_ASSIGNED_P (a) = true;
2118 ALLOCNO_HARD_REGNO (a) = -1;
2119 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2120 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2122 bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (a));
2124 if (ALLOCNO_REGNO (a) < start_regno
2125 || (cover_class = ALLOCNO_COVER_CLASS (a)) == NO_REGS)
2127 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
2129 ira_assert (cover_class == ALLOCNO_COVER_CLASS (conflict_a));
2130 if (bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (conflict_a)))
2132 bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a));
2133 sorted_allocnos[allocnos_to_color_num++] = conflict_a;
2136 ira_free_bitmap (allocnos_to_color);
2137 if (allocnos_to_color_num > 1)
2139 start_allocno_priorities (sorted_allocnos, allocnos_to_color_num);
2140 qsort (sorted_allocnos, allocnos_to_color_num, sizeof (ira_allocno_t),
2141 allocno_priority_compare_func);
2143 for (i = 0; i < allocnos_to_color_num; i++)
2145 a = sorted_allocnos[i];
2146 ALLOCNO_ASSIGNED_P (a) = false;
2147 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2148 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2149 update_curr_costs (a);
2151 for (i = 0; i < allocnos_to_color_num; i++)
2153 a = sorted_allocnos[i];
2154 if (assign_hard_reg (a, true))
2156 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2159 " Secondary allocation: assign hard reg %d to reg %d\n",
2160 ALLOCNO_HARD_REGNO (a), ALLOCNO_REGNO (a));
2167 /* This page contains code to coalesce memory stack slots used by
2168 spilled allocnos. This results in smaller stack frame, better data
2169 locality, and in smaller code for some architectures like
2170 x86/x86_64 where insn size depends on address displacement value.
2171 On the other hand, it can worsen insn scheduling after the RA but
2172 in practice it is less important than smaller stack frames. */
2174 /* Usage cost and order number of coalesced allocno set to which
2175 given pseudo register belongs to. */
2176 static int *regno_coalesced_allocno_cost;
2177 static int *regno_coalesced_allocno_num;
2179 /* Sort pseudos according frequencies of coalesced allocno sets they
2180 belong to (putting most frequently ones first), and according to
2181 coalesced allocno set order numbers. */
2183 coalesced_pseudo_reg_freq_compare (const void *v1p, const void *v2p)
2185 const int regno1 = *(const int *) v1p;
2186 const int regno2 = *(const int *) v2p;
2189 if ((diff = (regno_coalesced_allocno_cost[regno2]
2190 - regno_coalesced_allocno_cost[regno1])) != 0)
2192 if ((diff = (regno_coalesced_allocno_num[regno1]
2193 - regno_coalesced_allocno_num[regno2])) != 0)
2195 return regno1 - regno2;
2198 /* Widest width in which each pseudo reg is referred to (via subreg).
2199 It is used for sorting pseudo registers. */
2200 static unsigned int *regno_max_ref_width;
2202 /* Redefine STACK_GROWS_DOWNWARD in terms of 0 or 1. */
2203 #ifdef STACK_GROWS_DOWNWARD
2204 # undef STACK_GROWS_DOWNWARD
2205 # define STACK_GROWS_DOWNWARD 1
2207 # define STACK_GROWS_DOWNWARD 0
2210 /* Sort pseudos according their slot numbers (putting ones with
2211 smaller numbers first, or last when the frame pointer is not
2214 coalesced_pseudo_reg_slot_compare (const void *v1p, const void *v2p)
2216 const int regno1 = *(const int *) v1p;
2217 const int regno2 = *(const int *) v2p;
2218 ira_allocno_t a1 = ira_regno_allocno_map[regno1];
2219 ira_allocno_t a2 = ira_regno_allocno_map[regno2];
2220 int diff, slot_num1, slot_num2;
2221 int total_size1, total_size2;
2223 if (a1 == NULL || ALLOCNO_HARD_REGNO (a1) >= 0)
2225 if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
2226 return regno1 - regno2;
2229 else if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
2231 slot_num1 = -ALLOCNO_HARD_REGNO (a1);
2232 slot_num2 = -ALLOCNO_HARD_REGNO (a2);
2233 if ((diff = slot_num1 - slot_num2) != 0)
2234 return (frame_pointer_needed
2235 || !FRAME_GROWS_DOWNWARD == STACK_GROWS_DOWNWARD ? diff : -diff);
2236 total_size1 = MAX (PSEUDO_REGNO_BYTES (regno1), regno_max_ref_width[regno1]);
2237 total_size2 = MAX (PSEUDO_REGNO_BYTES (regno2), regno_max_ref_width[regno2]);
2238 if ((diff = total_size2 - total_size1) != 0)
2240 return regno1 - regno2;
2243 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
2244 for coalesced allocno sets containing allocnos with their regnos
2245 given in array PSEUDO_REGNOS of length N. */
2247 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos, int n)
2249 int i, num, regno, cost;
2250 ira_allocno_t allocno, a;
2252 for (num = i = 0; i < n; i++)
2254 regno = pseudo_regnos[i];
2255 allocno = ira_regno_allocno_map[regno];
2256 if (allocno == NULL)
2258 regno_coalesced_allocno_cost[regno] = 0;
2259 regno_coalesced_allocno_num[regno] = ++num;
2262 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
2265 for (cost = 0, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2266 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2268 cost += ALLOCNO_FREQ (a);
2272 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2273 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2275 regno_coalesced_allocno_num[ALLOCNO_REGNO (a)] = num;
2276 regno_coalesced_allocno_cost[ALLOCNO_REGNO (a)] = cost;
2283 /* Collect spilled allocnos representing coalesced allocno sets (the
2284 first coalesced allocno). The collected allocnos are returned
2285 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
2286 number of the collected allocnos. The allocnos are given by their
2287 regnos in array PSEUDO_REGNOS of length N. */
2289 collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n,
2290 ira_allocno_t *spilled_coalesced_allocnos)
2293 ira_allocno_t allocno;
2295 for (num = i = 0; i < n; i++)
2297 regno = pseudo_regnos[i];
2298 allocno = ira_regno_allocno_map[regno];
2299 if (allocno == NULL || ALLOCNO_HARD_REGNO (allocno) >= 0
2300 || ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
2302 spilled_coalesced_allocnos[num++] = allocno;
2307 /* We have coalesced allocnos involving in copies. Coalesce allocnos
2308 further in order to share the same memory stack slot. Allocnos
2309 representing sets of allocnos coalesced before the call are given
2310 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
2311 some allocnos were coalesced in the function. */
2313 coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num)
2316 ira_allocno_t allocno, a;
2317 bool merged_p = false;
2319 /* Coalesce non-conflicting spilled allocnos preferring most
2321 for (i = 0; i < num; i++)
2323 allocno = spilled_coalesced_allocnos[i];
2324 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno
2325 || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
2326 && (ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)]
2327 || ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX)))
2329 for (j = 0; j < i; j++)
2331 a = spilled_coalesced_allocnos[j];
2332 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) != a
2333 || (ALLOCNO_REGNO (a) < ira_reg_equiv_len
2334 && (ira_reg_equiv_invariant_p[ALLOCNO_REGNO (a)]
2335 || ira_reg_equiv_const[ALLOCNO_REGNO (a)] != NULL_RTX))
2336 || coalesced_allocno_conflict_p (allocno, a, true))
2338 allocno_coalesced_p = true;
2340 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2341 fprintf (ira_dump_file,
2342 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
2343 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno),
2344 ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2345 merge_allocnos (a, allocno);
2346 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a);
2352 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
2353 subsequent assigning stack slots to them in the reload pass. To do
2354 this we coalesce spilled allocnos first to decrease the number of
2355 memory-memory move insns. This function is called by the
2358 ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n,
2359 unsigned int *reg_max_ref_width)
2361 int max_regno = max_reg_num ();
2362 int i, regno, num, slot_num;
2363 ira_allocno_t allocno, a;
2364 ira_allocno_iterator ai;
2365 ira_allocno_t *spilled_coalesced_allocnos;
2367 processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
2368 /* Set up allocnos can be coalesced. */
2369 coloring_allocno_bitmap = ira_allocate_bitmap ();
2370 for (i = 0; i < n; i++)
2372 regno = pseudo_regnos[i];
2373 allocno = ira_regno_allocno_map[regno];
2374 if (allocno != NULL)
2375 bitmap_set_bit (coloring_allocno_bitmap,
2376 ALLOCNO_NUM (allocno));
2378 allocno_coalesced_p = false;
2379 coalesce_allocnos (true);
2380 ira_free_bitmap (coloring_allocno_bitmap);
2381 regno_coalesced_allocno_cost
2382 = (int *) ira_allocate (max_regno * sizeof (int));
2383 regno_coalesced_allocno_num
2384 = (int *) ira_allocate (max_regno * sizeof (int));
2385 memset (regno_coalesced_allocno_num, 0, max_regno * sizeof (int));
2386 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
2387 /* Sort regnos according frequencies of the corresponding coalesced
2389 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_freq_compare);
2390 spilled_coalesced_allocnos
2391 = (ira_allocno_t *) ira_allocate (ira_allocnos_num
2392 * sizeof (ira_allocno_t));
2393 /* Collect allocnos representing the spilled coalesced allocno
2395 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
2396 spilled_coalesced_allocnos);
2397 if (flag_ira_share_spill_slots
2398 && coalesce_spill_slots (spilled_coalesced_allocnos, num))
2400 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
2401 qsort (pseudo_regnos, n, sizeof (int),
2402 coalesced_pseudo_reg_freq_compare);
2403 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
2404 spilled_coalesced_allocnos);
2406 ira_free_bitmap (processed_coalesced_allocno_bitmap);
2407 allocno_coalesced_p = false;
2408 /* Assign stack slot numbers to spilled allocno sets, use smaller
2409 numbers for most frequently used coalesced allocnos. -1 is
2410 reserved for dynamic search of stack slots for pseudos spilled by
2413 for (i = 0; i < num; i++)
2415 allocno = spilled_coalesced_allocnos[i];
2416 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno
2417 || ALLOCNO_HARD_REGNO (allocno) >= 0
2418 || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
2419 && (ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)]
2420 || ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX)))
2422 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2423 fprintf (ira_dump_file, " Slot %d (freq,size):", slot_num);
2425 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2426 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2428 ira_assert (ALLOCNO_HARD_REGNO (a) < 0);
2429 ALLOCNO_HARD_REGNO (a) = -slot_num;
2430 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2431 fprintf (ira_dump_file, " a%dr%d(%d,%d)",
2432 ALLOCNO_NUM (a), ALLOCNO_REGNO (a), ALLOCNO_FREQ (a),
2433 MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a)),
2434 reg_max_ref_width[ALLOCNO_REGNO (a)]));
2439 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2440 fprintf (ira_dump_file, "\n");
2442 ira_spilled_reg_stack_slots_num = slot_num - 1;
2443 ira_free (spilled_coalesced_allocnos);
2444 /* Sort regnos according the slot numbers. */
2445 regno_max_ref_width = reg_max_ref_width;
2446 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_slot_compare);
2447 /* Uncoalesce allocnos which is necessary for (re)assigning during
2449 FOR_EACH_ALLOCNO (a, ai)
2451 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
2452 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
2454 ira_free (regno_coalesced_allocno_num);
2455 ira_free (regno_coalesced_allocno_cost);
2460 /* This page contains code used by the reload pass to improve the
2463 /* The function is called from reload to mark changes in the
2464 allocation of REGNO made by the reload. Remember that reg_renumber
2465 reflects the change result. */
2467 ira_mark_allocation_change (int regno)
2469 ira_allocno_t a = ira_regno_allocno_map[regno];
2470 int old_hard_regno, hard_regno, cost;
2471 enum reg_class cover_class = ALLOCNO_COVER_CLASS (a);
2473 ira_assert (a != NULL);
2474 hard_regno = reg_renumber[regno];
2475 if ((old_hard_regno = ALLOCNO_HARD_REGNO (a)) == hard_regno)
2477 if (old_hard_regno < 0)
2478 cost = -ALLOCNO_MEMORY_COST (a);
2481 ira_assert (ira_class_hard_reg_index[cover_class][old_hard_regno] >= 0);
2482 cost = -(ALLOCNO_HARD_REG_COSTS (a) == NULL
2483 ? ALLOCNO_COVER_CLASS_COST (a)
2484 : ALLOCNO_HARD_REG_COSTS (a)
2485 [ira_class_hard_reg_index[cover_class][old_hard_regno]]);
2486 update_copy_costs (a, false);
2488 ira_overall_cost -= cost;
2489 ALLOCNO_HARD_REGNO (a) = hard_regno;
2492 ALLOCNO_HARD_REGNO (a) = -1;
2493 cost += ALLOCNO_MEMORY_COST (a);
2495 else if (ira_class_hard_reg_index[cover_class][hard_regno] >= 0)
2497 cost += (ALLOCNO_HARD_REG_COSTS (a) == NULL
2498 ? ALLOCNO_COVER_CLASS_COST (a)
2499 : ALLOCNO_HARD_REG_COSTS (a)
2500 [ira_class_hard_reg_index[cover_class][hard_regno]]);
2501 update_copy_costs (a, true);
2504 /* Reload changed class of the allocno. */
2506 ira_overall_cost += cost;
2509 /* This function is called when reload deletes memory-memory move. In
2510 this case we marks that the allocation of the corresponding
2511 allocnos should be not changed in future. Otherwise we risk to get
2514 ira_mark_memory_move_deletion (int dst_regno, int src_regno)
2516 ira_allocno_t dst = ira_regno_allocno_map[dst_regno];
2517 ira_allocno_t src = ira_regno_allocno_map[src_regno];
2519 ira_assert (dst != NULL && src != NULL
2520 && ALLOCNO_HARD_REGNO (dst) < 0
2521 && ALLOCNO_HARD_REGNO (src) < 0);
2522 ALLOCNO_DONT_REASSIGN_P (dst) = true;
2523 ALLOCNO_DONT_REASSIGN_P (src) = true;
2526 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
2527 allocno A and return TRUE in the case of success. That is an
2528 analog of retry_global_alloc for IRA. */
2530 allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs)
2533 enum reg_class cover_class;
2534 int regno = ALLOCNO_REGNO (a);
2536 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), forbidden_regs);
2537 if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
2538 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), call_used_reg_set);
2539 ALLOCNO_ASSIGNED_P (a) = false;
2540 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2541 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2542 cover_class = ALLOCNO_COVER_CLASS (a);
2543 update_curr_costs (a);
2544 assign_hard_reg (a, true);
2545 hard_regno = ALLOCNO_HARD_REGNO (a);
2546 reg_renumber[regno] = hard_regno;
2548 ALLOCNO_HARD_REGNO (a) = -1;
2551 ira_assert (ira_class_hard_reg_index[cover_class][hard_regno] >= 0);
2552 ira_overall_cost -= (ALLOCNO_MEMORY_COST (a)
2553 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
2554 ? ALLOCNO_COVER_CLASS_COST (a)
2555 : ALLOCNO_HARD_REG_COSTS (a)
2556 [ira_class_hard_reg_index
2557 [cover_class][hard_regno]]));
2558 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
2559 && ! ira_hard_reg_not_in_set_p (hard_regno, ALLOCNO_MODE (a),
2562 ira_assert (flag_caller_saves);
2563 caller_save_needed = 1;
2567 /* If we found a hard register, modify the RTL for the pseudo
2568 register to show the hard register, and mark the pseudo register
2570 if (reg_renumber[regno] >= 0)
2572 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2573 fprintf (ira_dump_file, ": reassign to %d\n", reg_renumber[regno]);
2574 SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
2575 mark_home_live (regno);
2577 else if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2578 fprintf (ira_dump_file, "\n");
2580 return reg_renumber[regno] >= 0;
2583 /* Sort pseudos according their usage frequencies (putting most
2584 frequently ones first). */
2586 pseudo_reg_compare (const void *v1p, const void *v2p)
2588 int regno1 = *(const int *) v1p;
2589 int regno2 = *(const int *) v2p;
2592 if ((diff = REG_FREQ (regno2) - REG_FREQ (regno1)) != 0)
2594 return regno1 - regno2;
2597 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
2598 NUM of them) or spilled pseudos conflicting with pseudos in
2599 SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
2600 allocation has been changed. The function doesn't use
2601 BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
2602 PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
2603 is called by the reload pass at the end of each reload
2606 ira_reassign_pseudos (int *spilled_pseudo_regs, int num,
2607 HARD_REG_SET bad_spill_regs,
2608 HARD_REG_SET *pseudo_forbidden_regs,
2609 HARD_REG_SET *pseudo_previous_regs, bitmap spilled)
2613 ira_allocno_t a, conflict_a;
2614 HARD_REG_SET forbidden_regs;
2615 ira_allocno_conflict_iterator aci;
2618 qsort (spilled_pseudo_regs, num, sizeof (int), pseudo_reg_compare);
2620 /* Try to assign hard registers to pseudos from
2621 SPILLED_PSEUDO_REGS. */
2622 for (m = i = 0; i < num; i++)
2624 regno = spilled_pseudo_regs[i];
2625 COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
2626 IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]);
2627 IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]);
2628 gcc_assert (reg_renumber[regno] < 0);
2629 a = ira_regno_allocno_map[regno];
2630 ira_mark_allocation_change (regno);
2631 ira_assert (reg_renumber[regno] < 0);
2632 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2633 fprintf (ira_dump_file,
2634 " Spill %d(a%d), cost=%d", regno, ALLOCNO_NUM (a),
2635 ALLOCNO_MEMORY_COST (a)
2636 - ALLOCNO_COVER_CLASS_COST (a));
2637 allocno_reload_assign (a, forbidden_regs);
2638 if (reg_renumber[regno] >= 0)
2640 CLEAR_REGNO_REG_SET (spilled, regno);
2644 spilled_pseudo_regs[m++] = regno;
2648 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2650 fprintf (ira_dump_file, " Spilled regs");
2651 for (i = 0; i < m; i++)
2652 fprintf (ira_dump_file, " %d", spilled_pseudo_regs[i]);
2653 fprintf (ira_dump_file, "\n");
2655 /* Try to assign hard registers to pseudos conflicting with ones
2656 from SPILLED_PSEUDO_REGS. */
2657 for (i = n = 0; i < m; i++)
2659 regno = spilled_pseudo_regs[i];
2660 a = ira_regno_allocno_map[regno];
2661 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
2662 if (ALLOCNO_HARD_REGNO (conflict_a) < 0
2663 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a)
2664 && ! bitmap_bit_p (consideration_allocno_bitmap,
2665 ALLOCNO_NUM (conflict_a)))
2667 sorted_allocnos[n++] = conflict_a;
2668 bitmap_set_bit (consideration_allocno_bitmap,
2669 ALLOCNO_NUM (conflict_a));
2674 start_allocno_priorities (sorted_allocnos, n);
2675 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
2676 allocno_priority_compare_func);
2677 for (i = 0; i < n; i++)
2679 a = sorted_allocnos[i];
2680 regno = ALLOCNO_REGNO (a);
2681 COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
2682 IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]);
2683 IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]);
2684 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2685 fprintf (ira_dump_file,
2686 " Try assign %d(a%d), cost=%d",
2687 regno, ALLOCNO_NUM (a),
2688 ALLOCNO_MEMORY_COST (a)
2689 - ALLOCNO_COVER_CLASS_COST (a));
2690 if (allocno_reload_assign (a, forbidden_regs))
2693 bitmap_clear_bit (spilled, regno);
2700 /* The function is called by reload and returns already allocated
2701 stack slot (if any) for REGNO with given INHERENT_SIZE and
2702 TOTAL_SIZE. In the case of failure to find a slot which can be
2703 used for REGNO, the function returns NULL. */
2705 ira_reuse_stack_slot (int regno, unsigned int inherent_size,
2706 unsigned int total_size)
2709 int slot_num, best_slot_num;
2710 int cost, best_cost;
2711 ira_copy_t cp, next_cp;
2712 ira_allocno_t another_allocno, allocno = ira_regno_allocno_map[regno];
2715 struct ira_spilled_reg_stack_slot *slot = NULL;
2717 ira_assert (flag_ira && inherent_size == PSEUDO_REGNO_BYTES (regno)
2718 && inherent_size <= total_size
2719 && ALLOCNO_HARD_REGNO (allocno) < 0);
2720 if (! flag_ira_share_spill_slots)
2722 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
2725 slot = &ira_spilled_reg_stack_slots[slot_num];
2730 best_cost = best_slot_num = -1;
2732 /* It means that the pseudo was spilled in the reload pass, try
2735 slot_num < ira_spilled_reg_stack_slots_num;
2738 slot = &ira_spilled_reg_stack_slots[slot_num];
2739 if (slot->mem == NULL_RTX)
2741 if (slot->width < total_size
2742 || GET_MODE_SIZE (GET_MODE (slot->mem)) < inherent_size)
2745 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
2746 FIRST_PSEUDO_REGISTER, i, bi)
2748 another_allocno = ira_regno_allocno_map[i];
2749 if (ira_allocno_live_ranges_intersect_p (allocno,
2753 for (cost = 0, cp = ALLOCNO_COPIES (allocno);
2757 if (cp->first == allocno)
2759 next_cp = cp->next_first_allocno_copy;
2760 another_allocno = cp->second;
2762 else if (cp->second == allocno)
2764 next_cp = cp->next_second_allocno_copy;
2765 another_allocno = cp->first;
2769 if (cp->insn == NULL_RTX)
2771 if (bitmap_bit_p (&slot->spilled_regs,
2772 ALLOCNO_REGNO (another_allocno)))
2775 if (cost > best_cost)
2778 best_slot_num = slot_num;
2785 slot_num = best_slot_num;
2786 slot = &ira_spilled_reg_stack_slots[slot_num];
2787 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
2789 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
2794 ira_assert (slot->width >= total_size);
2795 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
2796 FIRST_PSEUDO_REGISTER, i, bi)
2798 ira_assert (! ira_pseudo_live_ranges_intersect_p (regno, i));
2800 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
2801 if (internal_flag_ira_verbose > 3 && ira_dump_file)
2803 fprintf (ira_dump_file, " Assigning %d(freq=%d) slot %d of",
2804 regno, REG_FREQ (regno), slot_num);
2805 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
2806 FIRST_PSEUDO_REGISTER, i, bi)
2808 if ((unsigned) regno != i)
2809 fprintf (ira_dump_file, " %d", i);
2811 fprintf (ira_dump_file, "\n");
2817 /* This is called by reload every time a new stack slot X with
2818 TOTAL_SIZE was allocated for REGNO. We store this info for
2819 subsequent ira_reuse_stack_slot calls. */
2821 ira_mark_new_stack_slot (rtx x, int regno, unsigned int total_size)
2823 struct ira_spilled_reg_stack_slot *slot;
2825 ira_allocno_t allocno;
2827 ira_assert (flag_ira && PSEUDO_REGNO_BYTES (regno) <= total_size);
2828 allocno = ira_regno_allocno_map[regno];
2829 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
2832 slot_num = ira_spilled_reg_stack_slots_num++;
2833 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
2835 slot = &ira_spilled_reg_stack_slots[slot_num];
2836 INIT_REG_SET (&slot->spilled_regs);
2837 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
2839 slot->width = total_size;
2840 if (internal_flag_ira_verbose > 3 && ira_dump_file)
2841 fprintf (ira_dump_file, " Assigning %d(freq=%d) a new slot %d\n",
2842 regno, REG_FREQ (regno), slot_num);
2846 /* Return spill cost for pseudo-registers whose numbers are in array
2847 REGNOS (with a negative number as an end marker) for reload with
2848 given IN and OUT for INSN. Return also number points (through
2849 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
2850 the register pressure is high, number of references of the
2851 pseudo-registers (through NREFS), number of callee-clobbered
2852 hard-registers occupied by the pseudo-registers (through
2853 CALL_USED_COUNT), and the first hard regno occupied by the
2854 pseudo-registers (through FIRST_HARD_REGNO). */
2856 calculate_spill_cost (int *regnos, rtx in, rtx out, rtx insn,
2857 int *excess_pressure_live_length,
2858 int *nrefs, int *call_used_count, int *first_hard_regno)
2860 int i, cost, regno, hard_regno, j, count, saved_cost, nregs;
2866 for (length = count = cost = i = 0;; i++)
2871 *nrefs += REG_N_REFS (regno);
2872 hard_regno = reg_renumber[regno];
2873 ira_assert (hard_regno >= 0);
2874 a = ira_regno_allocno_map[regno];
2875 length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2876 cost += ALLOCNO_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a);
2877 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
2878 for (j = 0; j < nregs; j++)
2879 if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j))
2883 in_p = in && REG_P (in) && (int) REGNO (in) == hard_regno;
2884 out_p = out && REG_P (out) && (int) REGNO (out) == hard_regno;
2886 && find_regno_note (insn, REG_DEAD, hard_regno) != NULL_RTX)
2890 saved_cost += ira_memory_move_cost
2891 [ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)][1];
2894 += ira_memory_move_cost
2895 [ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)][0];
2896 cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)) * saved_cost;
2899 *excess_pressure_live_length = length;
2900 *call_used_count = count;
2904 hard_regno = reg_renumber[regnos[0]];
2906 *first_hard_regno = hard_regno;
2910 /* Return TRUE if spilling pseudo-registers whose numbers are in array
2911 REGNOS is better than spilling pseudo-registers with numbers in
2912 OTHER_REGNOS for reload with given IN and OUT for INSN. The
2913 function used by the reload pass to make better register spilling
2916 ira_better_spill_reload_regno_p (int *regnos, int *other_regnos,
2917 rtx in, rtx out, rtx insn)
2919 int cost, other_cost;
2920 int length, other_length;
2921 int nrefs, other_nrefs;
2922 int call_used_count, other_call_used_count;
2923 int hard_regno, other_hard_regno;
2925 cost = calculate_spill_cost (regnos, in, out, insn,
2926 &length, &nrefs, &call_used_count, &hard_regno);
2927 other_cost = calculate_spill_cost (other_regnos, in, out, insn,
2928 &other_length, &other_nrefs,
2929 &other_call_used_count,
2931 if (nrefs == 0 && other_nrefs != 0)
2933 if (nrefs != 0 && other_nrefs == 0)
2935 if (cost != other_cost)
2936 return cost < other_cost;
2937 if (length != other_length)
2938 return length > other_length;
2939 #ifdef REG_ALLOC_ORDER
2940 if (hard_regno >= 0 && other_hard_regno >= 0)
2941 return (inv_reg_alloc_order[hard_regno]
2942 < inv_reg_alloc_order[other_hard_regno]);
2944 if (call_used_count != other_call_used_count)
2945 return call_used_count > other_call_used_count;
2952 /* Allocate and initialize data necessary for assign_hard_reg. */
2954 ira_initiate_assign (void)
2957 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
2958 * ira_allocnos_num);
2959 consideration_allocno_bitmap = ira_allocate_bitmap ();
2960 initiate_cost_update ();
2961 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
2964 /* Deallocate data used by assign_hard_reg. */
2966 ira_finish_assign (void)
2968 ira_free (sorted_allocnos);
2969 ira_free_bitmap (consideration_allocno_bitmap);
2970 finish_cost_update ();
2971 ira_free (allocno_priorities);
2976 /* Entry function doing color-based register allocation. */
2980 allocno_stack_vec = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
2981 removed_splay_allocno_vec
2982 = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
2983 memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p));
2984 ira_initiate_assign ();
2986 ira_finish_assign ();
2987 VEC_free (ira_allocno_t, heap, removed_splay_allocno_vec);
2988 VEC_free (ira_allocno_t, heap, allocno_stack_vec);
2989 move_spill_restore ();
2994 /* This page contains a simple register allocator without usage of
2995 allocno conflicts. This is used for fast allocation for -O0. */
2997 /* Do register allocation by not using allocno conflicts. It uses
2998 only allocno live ranges. The algorithm is close to Chow's
2999 priority coloring. */
3001 ira_fast_allocation (void)
3003 int i, j, k, l, num, class_size, hard_regno;
3005 bool no_stack_reg_p;
3007 enum reg_class cover_class;
3008 enum machine_mode mode;
3010 ira_allocno_iterator ai;
3011 allocno_live_range_t r;
3012 HARD_REG_SET conflict_hard_regs, *used_hard_regs;
3014 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
3015 FOR_EACH_ALLOCNO (a, ai)
3017 l = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
3020 allocno_priorities[ALLOCNO_NUM (a)]
3021 = (((double) (floor_log2 (ALLOCNO_NREFS (a))
3022 * (ALLOCNO_MEMORY_COST (a)
3023 - ALLOCNO_COVER_CLASS_COST (a))) / l)
3024 * (10000 / REG_FREQ_MAX)
3025 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a)][ALLOCNO_MODE (a)]);
3027 used_hard_regs = (HARD_REG_SET *) ira_allocate (sizeof (HARD_REG_SET)
3029 for (i = 0; i < ira_max_point; i++)
3030 CLEAR_HARD_REG_SET (used_hard_regs[i]);
3031 sorted_allocnos = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
3032 * ira_allocnos_num);
3034 FOR_EACH_ALLOCNO (a, ai)
3035 sorted_allocnos[num++] = a;
3036 qsort (sorted_allocnos, ira_allocnos_num, sizeof (ira_allocno_t),
3037 allocno_priority_compare_func);
3038 for (i = 0; i < num; i++)
3040 a = sorted_allocnos[i];
3041 COPY_HARD_REG_SET (conflict_hard_regs, ALLOCNO_CONFLICT_HARD_REGS (a));
3042 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
3043 for (j = r->start; j <= r->finish; j++)
3044 IOR_HARD_REG_SET (conflict_hard_regs, used_hard_regs[j]);
3045 cover_class = ALLOCNO_COVER_CLASS (a);
3046 ALLOCNO_ASSIGNED_P (a) = true;
3047 ALLOCNO_HARD_REGNO (a) = -1;
3048 if (hard_reg_set_subset_p (reg_class_contents[cover_class],
3049 conflict_hard_regs))
3051 mode = ALLOCNO_MODE (a);
3053 no_stack_reg_p = ALLOCNO_NO_STACK_REG_P (a);
3055 class_size = ira_class_hard_regs_num[cover_class];
3056 for (j = 0; j < class_size; j++)
3058 hard_regno = ira_class_hard_regs[cover_class][j];
3060 if (no_stack_reg_p && FIRST_STACK_REG <= hard_regno
3061 && hard_regno <= LAST_STACK_REG)
3064 if (!ira_hard_reg_not_in_set_p (hard_regno, mode, conflict_hard_regs)
3065 || (TEST_HARD_REG_BIT
3066 (prohibited_class_mode_regs[cover_class][mode], hard_regno)))
3068 ALLOCNO_HARD_REGNO (a) = hard_regno;
3069 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
3070 for (k = r->start; k <= r->finish; k++)
3071 IOR_HARD_REG_SET (used_hard_regs[k],
3072 ira_reg_mode_hard_regset[hard_regno][mode]);
3076 ira_free (sorted_allocnos);
3077 ira_free (used_hard_regs);
3078 ira_free (allocno_priorities);
3079 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
3080 ira_print_disposition (ira_dump_file);