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
98 /* This element is in the queue iff CHECK == update_cost_check. */
101 /* COST_HOP_DIVISOR**N, where N is the length of the shortest path
102 connecting this allocno to the one being allocated. */
105 /* The next allocno in the queue, or null if this is the last element. */
109 /* The first element in a queue of allocnos whose copy costs need to be
110 updated. Null if the queue is empty. */
111 static ira_allocno_t update_cost_queue;
113 /* The last element in the queue described by update_cost_queue.
114 Not valid if update_cost_queue is null. */
115 static struct update_cost_queue_elem *update_cost_queue_tail;
117 /* A pool of elements in the queue described by update_cost_queue.
118 Elements are indexed by ALLOCNO_NUM. */
119 static struct update_cost_queue_elem *update_cost_queue_elems;
121 /* The current value of update_copy_cost call count. */
122 static int update_cost_check;
124 /* Allocate and initialize data necessary for function
125 update_copy_costs. */
127 initiate_cost_update (void)
131 size = ira_allocnos_num * sizeof (struct update_cost_queue_elem);
132 update_cost_queue_elems
133 = (struct update_cost_queue_elem *) ira_allocate (size);
134 memset (update_cost_queue_elems, 0, size);
135 update_cost_check = 0;
138 /* Deallocate data used by function update_copy_costs. */
140 finish_cost_update (void)
142 ira_free (update_cost_queue);
145 /* When we traverse allocnos to update hard register costs, the cost
146 divisor will be multiplied by the following macro value for each
147 hop from given allocno to directly connected allocnos. */
148 #define COST_HOP_DIVISOR 4
150 /* Start a new cost-updating pass. */
152 start_update_cost (void)
155 update_cost_queue = NULL;
158 /* Add (ALLOCNO, DIVISOR) to the end of update_cost_queue,
159 unless ALLOCNO is already in the queue, or has no cover class. */
161 queue_update_cost (ira_allocno_t allocno, int divisor)
163 struct update_cost_queue_elem *elem;
165 elem = &update_cost_queue_elems[ALLOCNO_NUM (allocno)];
166 if (elem->check != update_cost_check
167 && ALLOCNO_COVER_CLASS (allocno) != NO_REGS)
169 elem->check = update_cost_check;
170 elem->divisor = divisor;
172 if (update_cost_queue == NULL)
173 update_cost_queue = allocno;
175 update_cost_queue_tail->next = allocno;
176 update_cost_queue_tail = elem;
180 /* Try to remove the first element from update_cost_queue. Return false
181 if the queue was empty, otherwise make (*ALLOCNO, *DIVISOR) describe
182 the removed element. */
184 get_next_update_cost (ira_allocno_t *allocno, int *divisor)
186 struct update_cost_queue_elem *elem;
188 if (update_cost_queue == NULL)
191 *allocno = update_cost_queue;
192 elem = &update_cost_queue_elems[ALLOCNO_NUM (*allocno)];
193 *divisor = elem->divisor;
194 update_cost_queue = elem->next;
198 /* Update the cost of allocnos to increase chances to remove some
199 copies as the result of subsequent assignment. */
201 update_copy_costs (ira_allocno_t allocno, bool decr_p)
203 int i, cost, update_cost, hard_regno, divisor;
204 enum machine_mode mode;
205 enum reg_class rclass, cover_class;
206 ira_allocno_t another_allocno;
207 ira_copy_t cp, next_cp;
209 hard_regno = ALLOCNO_HARD_REGNO (allocno);
210 ira_assert (hard_regno >= 0);
212 cover_class = ALLOCNO_COVER_CLASS (allocno);
213 if (cover_class == NO_REGS)
215 i = ira_class_hard_reg_index[cover_class][hard_regno];
217 rclass = REGNO_REG_CLASS (hard_regno);
219 start_update_cost ();
223 mode = ALLOCNO_MODE (allocno);
224 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
226 if (cp->first == allocno)
228 next_cp = cp->next_first_allocno_copy;
229 another_allocno = cp->second;
231 else if (cp->second == allocno)
233 next_cp = cp->next_second_allocno_copy;
234 another_allocno = cp->first;
239 if (cover_class != ALLOCNO_COVER_CLASS (another_allocno)
240 || ALLOCNO_ASSIGNED_P (another_allocno))
243 cost = (cp->second == allocno
244 ? ira_register_move_cost[mode][rclass][cover_class]
245 : ira_register_move_cost[mode][cover_class][rclass]);
249 update_cost = cp->freq * cost / divisor;
250 if (update_cost == 0)
253 ira_allocate_and_set_or_copy_costs
254 (&ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno), cover_class,
255 ALLOCNO_COVER_CLASS_COST (another_allocno),
256 ALLOCNO_HARD_REG_COSTS (another_allocno));
257 ira_allocate_and_set_or_copy_costs
258 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
260 ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
261 ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno)[i] += update_cost;
262 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno)[i]
265 queue_update_cost (another_allocno, divisor * COST_HOP_DIVISOR);
268 while (get_next_update_cost (&allocno, &divisor));
271 /* This function updates COSTS (decrease if DECR_P) by conflict costs
272 of the unassigned allocnos connected by copies with allocnos in
273 update_cost_queue. This update increases chances to remove some
276 update_conflict_hard_regno_costs (int *costs, bool decr_p)
278 int i, cost, class_size, freq, mult, div, divisor;
281 enum reg_class cover_class;
282 ira_allocno_t allocno, another_allocno;
283 ira_copy_t cp, next_cp;
285 while (get_next_update_cost (&allocno, &divisor))
286 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
288 if (cp->first == allocno)
290 next_cp = cp->next_first_allocno_copy;
291 another_allocno = cp->second;
293 else if (cp->second == allocno)
295 next_cp = cp->next_second_allocno_copy;
296 another_allocno = cp->first;
300 cover_class = ALLOCNO_COVER_CLASS (allocno);
301 if (cover_class != ALLOCNO_COVER_CLASS (another_allocno)
302 || ALLOCNO_ASSIGNED_P (another_allocno)
303 || ALLOCNO_MAY_BE_SPILLED_P (another_allocno))
305 class_size = ira_class_hard_regs_num[cover_class];
306 ira_allocate_and_copy_costs
307 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
308 cover_class, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
310 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno);
311 if (conflict_costs == NULL)
316 freq = ALLOCNO_FREQ (another_allocno);
319 div = freq * divisor;
321 for (i = class_size - 1; i >= 0; i--)
323 cost = conflict_costs [i] * mult / div;
332 /* Probably 5 hops will be enough. */
334 && divisor <= (COST_HOP_DIVISOR
338 queue_update_cost (another_allocno, divisor * COST_HOP_DIVISOR);
342 /* Sort allocnos according to the profit of usage of a hard register
343 instead of memory for them. */
345 allocno_cost_compare_func (const void *v1p, const void *v2p)
347 ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
348 ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
351 c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_COVER_CLASS_COST (p1);
352 c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_COVER_CLASS_COST (p2);
356 /* If regs are equally good, sort by allocno numbers, so that the
357 results of qsort leave nothing to chance. */
358 return ALLOCNO_NUM (p1) - ALLOCNO_NUM (p2);
361 /* Print all allocnos coalesced with ALLOCNO. */
363 print_coalesced_allocno (ira_allocno_t allocno)
367 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
368 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
370 ira_print_expanded_allocno (a);
373 fprintf (ira_dump_file, "+");
377 /* Choose a hard register for ALLOCNO (or for all coalesced allocnos
378 represented by ALLOCNO). If RETRY_P is TRUE, it means that the
379 function called from function `ira_reassign_conflict_allocnos' and
380 `allocno_reload_assign'. This function implements the optimistic
381 coalescing too: if we failed to assign a hard register to set of
382 the coalesced allocnos, we put them onto the coloring stack for
383 subsequent separate assigning. */
385 assign_hard_reg (ira_allocno_t allocno, bool retry_p)
387 HARD_REG_SET conflicting_regs;
388 int i, j, hard_regno, best_hard_regno, class_size;
389 int cost, mem_cost, min_cost, full_cost, min_full_cost, add_cost;
392 enum reg_class cover_class, rclass;
393 enum machine_mode mode;
394 ira_allocno_t a, conflict_allocno;
395 ira_allocno_conflict_iterator aci;
396 static int costs[FIRST_PSEUDO_REGISTER], full_costs[FIRST_PSEUDO_REGISTER];
401 ira_assert (! ALLOCNO_ASSIGNED_P (allocno));
402 cover_class = ALLOCNO_COVER_CLASS (allocno);
403 class_size = ira_class_hard_regs_num[cover_class];
404 mode = ALLOCNO_MODE (allocno);
405 CLEAR_HARD_REG_SET (conflicting_regs);
406 best_hard_regno = -1;
407 memset (full_costs, 0, sizeof (int) * class_size);
409 if (allocno_coalesced_p)
410 bitmap_clear (processed_coalesced_allocno_bitmap);
411 memset (costs, 0, sizeof (int) * class_size);
412 memset (full_costs, 0, sizeof (int) * class_size);
414 no_stack_reg_p = false;
416 start_update_cost ();
417 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
418 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
420 mem_cost += ALLOCNO_UPDATED_MEMORY_COST (a);
421 IOR_HARD_REG_SET (conflicting_regs,
422 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
423 ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
424 cover_class, ALLOCNO_HARD_REG_COSTS (a));
425 a_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
427 no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a);
429 for (cost = ALLOCNO_COVER_CLASS_COST (a), i = 0; i < class_size; i++)
432 costs[i] += a_costs[i];
433 full_costs[i] += a_costs[i];
438 full_costs[i] += cost;
440 /* Take preferences of conflicting allocnos into account. */
441 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
442 /* Reload can give another class so we need to check all
444 if (retry_p || bitmap_bit_p (consideration_allocno_bitmap,
445 ALLOCNO_NUM (conflict_allocno)))
447 ira_assert (cover_class == ALLOCNO_COVER_CLASS (conflict_allocno));
448 if (allocno_coalesced_p)
450 if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
451 ALLOCNO_NUM (conflict_allocno)))
453 bitmap_set_bit (processed_coalesced_allocno_bitmap,
454 ALLOCNO_NUM (conflict_allocno));
456 if (ALLOCNO_ASSIGNED_P (conflict_allocno))
458 if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno)) >= 0)
462 ira_reg_mode_hard_regset
463 [hard_regno][ALLOCNO_MODE (conflict_allocno)]);
464 if (hard_reg_set_subset_p (reg_class_contents[cover_class],
470 else if (! ALLOCNO_MAY_BE_SPILLED_P (conflict_allocno))
472 ira_allocate_and_copy_costs
473 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno),
475 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_allocno));
477 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno);
478 if (conflict_costs != NULL)
479 for (j = class_size - 1; j >= 0; j--)
480 full_costs[j] -= conflict_costs[j];
481 queue_update_cost (conflict_allocno, COST_HOP_DIVISOR);
487 /* Take into account preferences of allocnos connected by copies to
488 the conflict allocnos. */
489 update_conflict_hard_regno_costs (full_costs, true);
491 /* Take preferences of allocnos connected by copies into
493 start_update_cost ();
494 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
495 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
497 queue_update_cost (a, COST_HOP_DIVISOR);
501 update_conflict_hard_regno_costs (full_costs, false);
502 min_cost = min_full_cost = INT_MAX;
503 /* We don't care about giving callee saved registers to allocnos no
504 living through calls because call clobbered registers are
505 allocated first (it is usual practice to put them first in
507 for (i = 0; i < class_size; i++)
509 hard_regno = ira_class_hard_regs[cover_class][i];
512 && FIRST_STACK_REG <= hard_regno && hard_regno <= LAST_STACK_REG)
515 if (! ira_hard_reg_not_in_set_p (hard_regno, mode, conflicting_regs)
516 || TEST_HARD_REG_BIT (prohibited_class_mode_regs[cover_class][mode],
520 full_cost = full_costs[i];
521 if (! allocated_hardreg_p[hard_regno]
522 && ira_hard_reg_not_in_set_p (hard_regno, mode, call_used_reg_set))
523 /* We need to save/restore the hard register in
524 epilogue/prologue. Therefore we increase the cost. */
526 /* ??? If only part is call clobbered. */
527 rclass = REGNO_REG_CLASS (hard_regno);
528 add_cost = (ira_memory_move_cost[mode][rclass][0]
529 + ira_memory_move_cost[mode][rclass][1] - 1);
531 full_cost += add_cost;
535 if (min_full_cost > full_cost)
537 min_full_cost = full_cost;
538 best_hard_regno = hard_regno;
539 ira_assert (hard_regno >= 0);
542 if (min_full_cost > mem_cost)
544 if (! retry_p && internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
545 fprintf (ira_dump_file, "(memory is more profitable %d vs %d) ",
546 mem_cost, min_full_cost);
547 best_hard_regno = -1;
550 if (best_hard_regno < 0
551 && ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno) != allocno)
553 for (j = 0, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
554 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
556 sorted_allocnos[j++] = a;
560 qsort (sorted_allocnos, j, sizeof (ira_allocno_t),
561 allocno_cost_compare_func);
562 for (i = 0; i < j; i++)
564 a = sorted_allocnos[i];
565 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
566 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
567 VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, a);
568 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
570 fprintf (ira_dump_file, " Pushing");
571 print_coalesced_allocno (a);
572 fprintf (ira_dump_file, "\n");
577 if (best_hard_regno >= 0)
578 allocated_hardreg_p[best_hard_regno] = true;
579 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
580 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
582 ALLOCNO_HARD_REGNO (a) = best_hard_regno;
583 ALLOCNO_ASSIGNED_P (a) = true;
584 if (best_hard_regno >= 0)
585 update_copy_costs (a, true);
586 ira_assert (ALLOCNO_COVER_CLASS (a) == cover_class);
587 /* We don't need updated costs anymore: */
588 ira_free_allocno_updated_costs (a);
592 return best_hard_regno >= 0;
597 /* This page contains the allocator based on the Chaitin-Briggs algorithm. */
599 /* Bucket of allocnos that can colored currently without spilling. */
600 static ira_allocno_t colorable_allocno_bucket;
602 /* Bucket of allocnos that might be not colored currently without
604 static ira_allocno_t uncolorable_allocno_bucket;
606 /* Each element of the array contains the current number of allocnos
607 of given *cover* class in the uncolorable_bucket. */
608 static int uncolorable_allocnos_num[N_REG_CLASSES];
610 /* Add ALLOCNO to bucket *BUCKET_PTR. ALLOCNO should be not in a bucket
613 add_ira_allocno_to_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
615 ira_allocno_t first_allocno;
616 enum reg_class cover_class;
618 if (bucket_ptr == &uncolorable_allocno_bucket
619 && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
621 uncolorable_allocnos_num[cover_class]++;
622 ira_assert (uncolorable_allocnos_num[cover_class] > 0);
624 first_allocno = *bucket_ptr;
625 ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno) = first_allocno;
626 ALLOCNO_PREV_BUCKET_ALLOCNO (allocno) = NULL;
627 if (first_allocno != NULL)
628 ALLOCNO_PREV_BUCKET_ALLOCNO (first_allocno) = allocno;
629 *bucket_ptr = allocno;
632 /* The function returns frequency and number of available hard
633 registers for allocnos coalesced with ALLOCNO. */
635 get_coalesced_allocnos_attributes (ira_allocno_t allocno, int *freq, int *num)
641 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
642 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
644 *freq += ALLOCNO_FREQ (a);
645 *num += ALLOCNO_AVAILABLE_REGS_NUM (a);
651 /* Compare two allocnos to define which allocno should be pushed first
652 into the coloring stack. If the return is a negative number, the
653 allocno given by the first parameter will be pushed first. In this
654 case such allocno has less priority than the second one and the
655 hard register will be assigned to it after assignment to the second
656 one. As the result of such assignment order, the second allocno
657 has a better chance to get the best hard register. */
659 bucket_allocno_compare_func (const void *v1p, const void *v2p)
661 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
662 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
663 int diff, a1_freq, a2_freq, a1_num, a2_num;
665 if ((diff = (int) ALLOCNO_COVER_CLASS (a2) - ALLOCNO_COVER_CLASS (a1)) != 0)
667 get_coalesced_allocnos_attributes (a1, &a1_freq, &a1_num);
668 get_coalesced_allocnos_attributes (a2, &a2_freq, &a2_num);
669 if ((diff = a2_num - a1_num) != 0)
671 else if ((diff = a1_freq - a2_freq) != 0)
673 return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
676 /* Sort bucket *BUCKET_PTR and return the result through
679 sort_bucket (ira_allocno_t *bucket_ptr)
681 ira_allocno_t a, head;
684 for (n = 0, a = *bucket_ptr; a != NULL; a = ALLOCNO_NEXT_BUCKET_ALLOCNO (a))
685 sorted_allocnos[n++] = a;
688 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
689 bucket_allocno_compare_func);
691 for (n--; n >= 0; n--)
693 a = sorted_allocnos[n];
694 ALLOCNO_NEXT_BUCKET_ALLOCNO (a) = head;
695 ALLOCNO_PREV_BUCKET_ALLOCNO (a) = NULL;
697 ALLOCNO_PREV_BUCKET_ALLOCNO (head) = a;
703 /* Add ALLOCNO to bucket *BUCKET_PTR maintaining the order according
704 their priority. ALLOCNO should be not in a bucket before the
707 add_ira_allocno_to_ordered_bucket (ira_allocno_t allocno,
708 ira_allocno_t *bucket_ptr)
710 ira_allocno_t before, after;
711 enum reg_class cover_class;
713 if (bucket_ptr == &uncolorable_allocno_bucket
714 && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
716 uncolorable_allocnos_num[cover_class]++;
717 ira_assert (uncolorable_allocnos_num[cover_class] > 0);
719 for (before = *bucket_ptr, after = NULL;
721 after = before, before = ALLOCNO_NEXT_BUCKET_ALLOCNO (before))
722 if (bucket_allocno_compare_func (&allocno, &before) < 0)
724 ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno) = before;
725 ALLOCNO_PREV_BUCKET_ALLOCNO (allocno) = after;
727 *bucket_ptr = allocno;
729 ALLOCNO_NEXT_BUCKET_ALLOCNO (after) = allocno;
731 ALLOCNO_PREV_BUCKET_ALLOCNO (before) = allocno;
734 /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
737 delete_allocno_from_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
739 ira_allocno_t prev_allocno, next_allocno;
740 enum reg_class cover_class;
742 if (bucket_ptr == &uncolorable_allocno_bucket
743 && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
745 uncolorable_allocnos_num[cover_class]--;
746 ira_assert (uncolorable_allocnos_num[cover_class] >= 0);
748 prev_allocno = ALLOCNO_PREV_BUCKET_ALLOCNO (allocno);
749 next_allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno);
750 if (prev_allocno != NULL)
751 ALLOCNO_NEXT_BUCKET_ALLOCNO (prev_allocno) = next_allocno;
754 ira_assert (*bucket_ptr == allocno);
755 *bucket_ptr = next_allocno;
757 if (next_allocno != NULL)
758 ALLOCNO_PREV_BUCKET_ALLOCNO (next_allocno) = prev_allocno;
761 /* Splay tree for each cover class. The trees are indexed by the
762 corresponding cover classes. Splay trees contain uncolorable
764 static splay_tree uncolorable_allocnos_splay_tree[N_REG_CLASSES];
766 /* If the following macro is TRUE, splay tree is used to choose an
767 allocno of the corresponding cover class for spilling. When the
768 number uncolorable allocnos of given cover class decreases to some
769 threshold, linear array search is used to find the best allocno for
770 spilling. This threshold is actually pretty big because, although
771 splay trees asymptotically is much faster, each splay tree
772 operation is sufficiently costly especially taking cache locality
774 #define USE_SPLAY_P(CLASS) (uncolorable_allocnos_num[CLASS] > 4000)
776 /* Put ALLOCNO onto the coloring stack without removing it from its
777 bucket. Pushing allocno to the coloring stack can result in moving
778 conflicting allocnos from the uncolorable bucket to the colorable
781 push_ira_allocno_to_stack (ira_allocno_t allocno)
783 int conflicts_num, conflict_size, size;
784 ira_allocno_t a, conflict_allocno;
785 enum reg_class cover_class;
786 ira_allocno_conflict_iterator aci;
788 ALLOCNO_IN_GRAPH_P (allocno) = false;
789 VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, allocno);
790 cover_class = ALLOCNO_COVER_CLASS (allocno);
791 if (cover_class == NO_REGS)
793 size = ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)];
794 if (allocno_coalesced_p)
795 bitmap_clear (processed_coalesced_allocno_bitmap);
796 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
797 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
799 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
800 if (bitmap_bit_p (coloring_allocno_bitmap,
801 ALLOCNO_NUM (conflict_allocno)))
803 ira_assert (cover_class == ALLOCNO_COVER_CLASS (conflict_allocno));
804 if (allocno_coalesced_p)
806 if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
807 ALLOCNO_NUM (conflict_allocno)))
809 bitmap_set_bit (processed_coalesced_allocno_bitmap,
810 ALLOCNO_NUM (conflict_allocno));
812 if (ALLOCNO_IN_GRAPH_P (conflict_allocno)
813 && ! ALLOCNO_ASSIGNED_P (conflict_allocno))
815 conflicts_num = ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno);
817 = (ira_reg_class_nregs
818 [cover_class][ALLOCNO_MODE (conflict_allocno)]);
820 (ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) >= size);
821 if (conflicts_num + conflict_size
822 <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno))
824 ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) -= size;
828 = ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) - size;
829 if (uncolorable_allocnos_splay_tree[cover_class] != NULL
830 && !ALLOCNO_SPLAY_REMOVED_P (conflict_allocno)
831 && USE_SPLAY_P (cover_class))
835 (uncolorable_allocnos_splay_tree[cover_class],
836 (splay_tree_key) conflict_allocno) != NULL);
838 (uncolorable_allocnos_splay_tree[cover_class],
839 (splay_tree_key) conflict_allocno);
840 ALLOCNO_SPLAY_REMOVED_P (conflict_allocno) = true;
841 VEC_safe_push (ira_allocno_t, heap,
842 removed_splay_allocno_vec,
845 ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) = conflicts_num;
846 if (conflicts_num + conflict_size
847 <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno))
849 delete_allocno_from_bucket (conflict_allocno,
850 &uncolorable_allocno_bucket);
851 add_ira_allocno_to_ordered_bucket (conflict_allocno,
852 &colorable_allocno_bucket);
861 /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
862 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
864 remove_allocno_from_bucket_and_push (ira_allocno_t allocno, bool colorable_p)
866 enum reg_class cover_class;
869 delete_allocno_from_bucket (allocno, &colorable_allocno_bucket);
871 delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
872 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
874 fprintf (ira_dump_file, " Pushing");
875 print_coalesced_allocno (allocno);
876 fprintf (ira_dump_file, "%s\n", colorable_p ? "" : "(potential spill)");
878 cover_class = ALLOCNO_COVER_CLASS (allocno);
879 ira_assert ((colorable_p
880 && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
881 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)]
882 <= ALLOCNO_AVAILABLE_REGS_NUM (allocno)))
884 && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
885 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE
887 > ALLOCNO_AVAILABLE_REGS_NUM (allocno))));
889 ALLOCNO_MAY_BE_SPILLED_P (allocno) = true;
890 push_ira_allocno_to_stack (allocno);
893 /* Put all allocnos from colorable bucket onto the coloring stack. */
895 push_only_colorable (void)
897 sort_bucket (&colorable_allocno_bucket);
898 for (;colorable_allocno_bucket != NULL;)
899 remove_allocno_from_bucket_and_push (colorable_allocno_bucket, true);
902 /* Puts ALLOCNO chosen for potential spilling onto the coloring
905 push_ira_allocno_to_spill (ira_allocno_t allocno)
907 delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
908 ALLOCNO_MAY_BE_SPILLED_P (allocno) = true;
909 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
910 fprintf (ira_dump_file, " Pushing p%d(%d) (potential spill)\n",
911 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno));
912 push_ira_allocno_to_stack (allocno);
915 /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
916 loop given by its LOOP_NODE. */
918 ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p)
923 VEC (edge, heap) *edges;
925 ira_assert (loop_node->loop != NULL
926 && (regno < 0 || regno >= FIRST_PSEUDO_REGISTER));
930 FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
931 if (e->src != loop_node->loop->latch
933 || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
934 && bitmap_bit_p (DF_LR_IN (e->dest), regno))))
935 freq += EDGE_FREQUENCY (e);
939 edges = get_loop_exit_edges (loop_node->loop);
940 for (i = 0; VEC_iterate (edge, edges, i, e); i++)
942 || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
943 && bitmap_bit_p (DF_LR_IN (e->dest), regno)))
944 freq += EDGE_FREQUENCY (e);
945 VEC_free (edge, heap, edges);
948 return REG_FREQ_FROM_EDGE_FREQ (freq);
951 /* Calculate and return the cost of putting allocno A into memory. */
953 calculate_allocno_spill_cost (ira_allocno_t a)
956 enum machine_mode mode;
957 enum reg_class rclass;
958 ira_allocno_t parent_allocno;
959 ira_loop_tree_node_t parent_node, loop_node;
961 regno = ALLOCNO_REGNO (a);
962 cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a);
963 if (ALLOCNO_CAP (a) != NULL)
965 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
966 if ((parent_node = loop_node->parent) == NULL)
968 if ((parent_allocno = parent_node->regno_allocno_map[regno]) == NULL)
970 mode = ALLOCNO_MODE (a);
971 rclass = ALLOCNO_COVER_CLASS (a);
972 if (ALLOCNO_HARD_REGNO (parent_allocno) < 0)
973 cost -= (ira_memory_move_cost[mode][rclass][0]
974 * ira_loop_edge_freq (loop_node, regno, true)
975 + ira_memory_move_cost[mode][rclass][1]
976 * ira_loop_edge_freq (loop_node, regno, false));
978 cost += ((ira_memory_move_cost[mode][rclass][1]
979 * ira_loop_edge_freq (loop_node, regno, true)
980 + ira_memory_move_cost[mode][rclass][0]
981 * ira_loop_edge_freq (loop_node, regno, false))
982 - (ira_register_move_cost[mode][rclass][rclass]
983 * (ira_loop_edge_freq (loop_node, regno, false)
984 + ira_loop_edge_freq (loop_node, regno, true))));
988 /* Compare keys in the splay tree used to choose best allocno for
989 spilling. The best allocno has the minimal key. */
991 allocno_spill_priority_compare (splay_tree_key k1, splay_tree_key k2)
993 int pri1, pri2, diff;
994 ira_allocno_t a1 = (ira_allocno_t) k1, a2 = (ira_allocno_t) k2;
996 pri1 = (IRA_ALLOCNO_TEMP (a1)
997 / (ALLOCNO_LEFT_CONFLICTS_NUM (a1)
998 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a1)][ALLOCNO_MODE (a1)]
1000 pri2 = (IRA_ALLOCNO_TEMP (a2)
1001 / (ALLOCNO_LEFT_CONFLICTS_NUM (a2)
1002 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a2)][ALLOCNO_MODE (a2)]
1004 if ((diff = pri1 - pri2) != 0)
1006 if ((diff = IRA_ALLOCNO_TEMP (a1) - IRA_ALLOCNO_TEMP (a2)) != 0)
1008 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
1011 /* Allocate data of SIZE for the splay trees. We allocate only spay
1012 tree roots or splay tree nodes. If you change this, please rewrite
1015 splay_tree_allocate (int size, void *data ATTRIBUTE_UNUSED)
1017 if (size != sizeof (struct splay_tree_node_s))
1018 return ira_allocate (size);
1019 return pool_alloc (splay_tree_node_pool);
1022 /* Free data NODE for the splay trees. We allocate and free only spay
1023 tree roots or splay tree nodes. If you change this, please rewrite
1026 splay_tree_free (void *node, void *data ATTRIBUTE_UNUSED)
1029 enum reg_class cover_class;
1031 for (i = 0; i < ira_reg_class_cover_size; i++)
1033 cover_class = ira_reg_class_cover[i];
1034 if (node == uncolorable_allocnos_splay_tree[cover_class])
1040 pool_free (splay_tree_node_pool, node);
1043 /* Push allocnos to the coloring stack. The order of allocnos in the
1044 stack defines the order for the subsequent coloring. */
1046 push_allocnos_to_stack (void)
1048 ira_allocno_t allocno, a, i_allocno, *allocno_vec;
1049 enum reg_class cover_class, rclass;
1050 int allocno_pri, i_allocno_pri, allocno_cost, i_allocno_cost;
1051 int i, j, num, cover_class_allocnos_num[N_REG_CLASSES];
1052 ira_allocno_t *cover_class_allocnos[N_REG_CLASSES];
1056 VEC_truncate(ira_allocno_t, removed_splay_allocno_vec, 0);
1057 for (i = 0; i < ira_reg_class_cover_size; i++)
1059 cover_class = ira_reg_class_cover[i];
1060 cover_class_allocnos_num[cover_class] = 0;
1061 cover_class_allocnos[cover_class] = NULL;
1062 uncolorable_allocnos_splay_tree[cover_class] = NULL;
1064 /* Calculate uncolorable allocno spill costs. */
1065 for (allocno = uncolorable_allocno_bucket;
1067 allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno))
1068 if ((cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
1070 cover_class_allocnos_num[cover_class]++;
1072 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1073 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1075 cost += calculate_allocno_spill_cost (a);
1079 /* ??? Remove cost of copies between the coalesced
1081 IRA_ALLOCNO_TEMP (allocno) = cost;
1083 /* Define place where to put uncolorable allocnos of the same cover
1085 for (num = i = 0; i < ira_reg_class_cover_size; i++)
1087 cover_class = ira_reg_class_cover[i];
1088 ira_assert (cover_class_allocnos_num[cover_class]
1089 == uncolorable_allocnos_num[cover_class]);
1090 if (cover_class_allocnos_num[cover_class] != 0)
1092 cover_class_allocnos[cover_class] = allocnos_for_spilling + num;
1093 num += cover_class_allocnos_num[cover_class];
1094 cover_class_allocnos_num[cover_class] = 0;
1096 if (USE_SPLAY_P (cover_class))
1097 uncolorable_allocnos_splay_tree[cover_class]
1098 = splay_tree_new_with_allocator (allocno_spill_priority_compare,
1099 NULL, NULL, splay_tree_allocate,
1100 splay_tree_free, NULL);
1102 ira_assert (num <= ira_allocnos_num);
1103 /* Collect uncolorable allocnos of each cover class. */
1104 for (allocno = uncolorable_allocno_bucket;
1106 allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno))
1107 if ((cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
1109 cover_class_allocnos
1110 [cover_class][cover_class_allocnos_num[cover_class]++] = allocno;
1111 if (uncolorable_allocnos_splay_tree[cover_class] != NULL)
1112 splay_tree_insert (uncolorable_allocnos_splay_tree[cover_class],
1113 (splay_tree_key) allocno,
1114 (splay_tree_value) allocno);
1118 push_only_colorable ();
1119 allocno = uncolorable_allocno_bucket;
1120 if (allocno == NULL)
1122 cover_class = ALLOCNO_COVER_CLASS (allocno);
1123 if (cover_class == NO_REGS)
1125 push_ira_allocno_to_spill (allocno);
1128 /* Potential spilling. */
1130 (ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)] > 0);
1131 if (USE_SPLAY_P (cover_class))
1133 for (;VEC_length (ira_allocno_t, removed_splay_allocno_vec) != 0;)
1135 allocno = VEC_pop (ira_allocno_t, removed_splay_allocno_vec);
1136 ALLOCNO_SPLAY_REMOVED_P (allocno) = false;
1137 rclass = ALLOCNO_COVER_CLASS (allocno);
1138 if (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
1139 + ira_reg_class_nregs [rclass][ALLOCNO_MODE (allocno)]
1140 > ALLOCNO_AVAILABLE_REGS_NUM (allocno))
1142 (uncolorable_allocnos_splay_tree[rclass],
1143 (splay_tree_key) allocno, (splay_tree_value) allocno);
1145 allocno = ((ira_allocno_t)
1147 (uncolorable_allocnos_splay_tree[cover_class])->key);
1148 splay_tree_remove (uncolorable_allocnos_splay_tree[cover_class],
1149 (splay_tree_key) allocno);
1153 num = cover_class_allocnos_num[cover_class];
1154 ira_assert (num > 0);
1155 allocno_vec = cover_class_allocnos[cover_class];
1157 allocno_pri = allocno_cost = 0;
1158 /* Sort uncolorable allocno to find the one with the lowest
1160 for (i = 0, j = num - 1; i <= j;)
1162 i_allocno = allocno_vec[i];
1163 if (! ALLOCNO_IN_GRAPH_P (i_allocno)
1164 && ALLOCNO_IN_GRAPH_P (allocno_vec[j]))
1166 i_allocno = allocno_vec[j];
1167 allocno_vec[j] = allocno_vec[i];
1168 allocno_vec[i] = i_allocno;
1170 if (ALLOCNO_IN_GRAPH_P (i_allocno))
1173 if (IRA_ALLOCNO_TEMP (i_allocno) == INT_MAX)
1178 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (i_allocno);;
1179 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1181 cost += calculate_allocno_spill_cost (i_allocno);
1185 /* ??? Remove cost of copies between the coalesced
1187 IRA_ALLOCNO_TEMP (i_allocno) = cost;
1189 i_allocno_cost = IRA_ALLOCNO_TEMP (i_allocno);
1192 / (ALLOCNO_LEFT_CONFLICTS_NUM (i_allocno)
1193 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS
1195 [ALLOCNO_MODE (i_allocno)] + 1));
1196 if (allocno == NULL || allocno_pri > i_allocno_pri
1197 || (allocno_pri == i_allocno_pri
1198 && (allocno_cost > i_allocno_cost
1199 || (allocno_cost == i_allocno_cost
1200 && (ALLOCNO_NUM (allocno)
1201 > ALLOCNO_NUM (i_allocno))))))
1203 allocno = i_allocno;
1204 allocno_cost = i_allocno_cost;
1205 allocno_pri = i_allocno_pri;
1208 if (! ALLOCNO_IN_GRAPH_P (allocno_vec[j]))
1211 ira_assert (allocno != NULL && j >= 0);
1212 cover_class_allocnos_num[cover_class] = j + 1;
1214 ira_assert (ALLOCNO_IN_GRAPH_P (allocno)
1215 && ALLOCNO_COVER_CLASS (allocno) == cover_class
1216 && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
1217 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE
1219 > ALLOCNO_AVAILABLE_REGS_NUM (allocno)));
1220 remove_allocno_from_bucket_and_push (allocno, false);
1222 ira_assert (colorable_allocno_bucket == NULL
1223 && uncolorable_allocno_bucket == NULL);
1224 for (i = 0; i < ira_reg_class_cover_size; i++)
1226 cover_class = ira_reg_class_cover[i];
1227 ira_assert (uncolorable_allocnos_num[cover_class] == 0);
1228 if (uncolorable_allocnos_splay_tree[cover_class] != NULL)
1229 splay_tree_delete (uncolorable_allocnos_splay_tree[cover_class]);
1233 /* Pop the coloring stack and assign hard registers to the popped
1236 pop_allocnos_from_stack (void)
1238 ira_allocno_t allocno;
1239 enum reg_class cover_class;
1241 for (;VEC_length (ira_allocno_t, allocno_stack_vec) != 0;)
1243 allocno = VEC_pop (ira_allocno_t, allocno_stack_vec);
1244 cover_class = ALLOCNO_COVER_CLASS (allocno);
1245 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1247 fprintf (ira_dump_file, " Popping");
1248 print_coalesced_allocno (allocno);
1249 fprintf (ira_dump_file, " -- ");
1251 if (cover_class == NO_REGS)
1253 ALLOCNO_HARD_REGNO (allocno) = -1;
1254 ALLOCNO_ASSIGNED_P (allocno) = true;
1255 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno) == NULL);
1257 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno) == NULL);
1258 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1259 fprintf (ira_dump_file, "assign memory\n");
1261 else if (assign_hard_reg (allocno, false))
1263 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1264 fprintf (ira_dump_file, "assign reg %d\n",
1265 ALLOCNO_HARD_REGNO (allocno));
1267 else if (ALLOCNO_ASSIGNED_P (allocno))
1269 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1270 fprintf (ira_dump_file, "spill\n");
1272 ALLOCNO_IN_GRAPH_P (allocno) = true;
1276 /* Set up number of available hard registers for ALLOCNO. */
1278 setup_allocno_available_regs_num (ira_allocno_t allocno)
1280 int i, n, hard_regs_num;
1281 enum reg_class cover_class;
1283 HARD_REG_SET temp_set;
1285 cover_class = ALLOCNO_COVER_CLASS (allocno);
1286 ALLOCNO_AVAILABLE_REGS_NUM (allocno) = ira_available_class_regs[cover_class];
1287 if (cover_class == NO_REGS)
1289 CLEAR_HARD_REG_SET (temp_set);
1290 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) == allocno);
1291 hard_regs_num = ira_class_hard_regs_num[cover_class];
1292 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1293 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1295 IOR_HARD_REG_SET (temp_set, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1299 for (n = 0, i = hard_regs_num - 1; i >= 0; i--)
1300 if (TEST_HARD_REG_BIT (temp_set, ira_class_hard_regs[cover_class][i]))
1302 if (internal_flag_ira_verbose > 2 && n > 0 && ira_dump_file != NULL)
1303 fprintf (ira_dump_file, " Reg %d of %s has %d regs less\n",
1304 ALLOCNO_REGNO (allocno), reg_class_names[cover_class], n);
1305 ALLOCNO_AVAILABLE_REGS_NUM (allocno) -= n;
1308 /* Set up ALLOCNO_LEFT_CONFLICTS_NUM for ALLOCNO. */
1310 setup_allocno_left_conflicts_num (ira_allocno_t allocno)
1312 int i, hard_regs_num, hard_regno, conflict_allocnos_size;
1313 ira_allocno_t a, conflict_allocno;
1314 enum reg_class cover_class;
1315 HARD_REG_SET temp_set;
1316 ira_allocno_conflict_iterator aci;
1318 cover_class = ALLOCNO_COVER_CLASS (allocno);
1319 hard_regs_num = ira_class_hard_regs_num[cover_class];
1320 CLEAR_HARD_REG_SET (temp_set);
1321 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) == allocno);
1322 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1323 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1325 IOR_HARD_REG_SET (temp_set, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1329 AND_HARD_REG_SET (temp_set, reg_class_contents[cover_class]);
1330 AND_COMPL_HARD_REG_SET (temp_set, ira_no_alloc_regs);
1331 conflict_allocnos_size = 0;
1332 if (! hard_reg_set_empty_p (temp_set))
1333 for (i = 0; i < (int) hard_regs_num; i++)
1335 hard_regno = ira_class_hard_regs[cover_class][i];
1336 if (TEST_HARD_REG_BIT (temp_set, hard_regno))
1338 conflict_allocnos_size++;
1339 CLEAR_HARD_REG_BIT (temp_set, hard_regno);
1340 if (hard_reg_set_empty_p (temp_set))
1344 CLEAR_HARD_REG_SET (temp_set);
1345 if (allocno_coalesced_p)
1346 bitmap_clear (processed_coalesced_allocno_bitmap);
1347 if (cover_class != NO_REGS)
1348 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1349 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1351 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
1352 if (bitmap_bit_p (consideration_allocno_bitmap,
1353 ALLOCNO_NUM (conflict_allocno)))
1355 ira_assert (cover_class
1356 == ALLOCNO_COVER_CLASS (conflict_allocno));
1357 if (allocno_coalesced_p)
1359 if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
1360 ALLOCNO_NUM (conflict_allocno)))
1362 bitmap_set_bit (processed_coalesced_allocno_bitmap,
1363 ALLOCNO_NUM (conflict_allocno));
1365 if (! ALLOCNO_ASSIGNED_P (conflict_allocno))
1366 conflict_allocnos_size
1367 += (ira_reg_class_nregs
1368 [cover_class][ALLOCNO_MODE (conflict_allocno)]);
1369 else if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno))
1372 int last = (hard_regno
1374 [hard_regno][ALLOCNO_MODE (conflict_allocno)]);
1376 while (hard_regno < last)
1378 if (! TEST_HARD_REG_BIT (temp_set, hard_regno))
1380 conflict_allocnos_size++;
1381 SET_HARD_REG_BIT (temp_set, hard_regno);
1390 ALLOCNO_LEFT_CONFLICTS_NUM (allocno) = conflict_allocnos_size;
1393 /* Put ALLOCNO in a bucket corresponding to its number and size of its
1394 conflicting allocnos and hard registers. */
1396 put_allocno_into_bucket (ira_allocno_t allocno)
1399 enum reg_class cover_class;
1401 cover_class = ALLOCNO_COVER_CLASS (allocno);
1402 hard_regs_num = ira_class_hard_regs_num[cover_class];
1403 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
1405 ALLOCNO_IN_GRAPH_P (allocno) = true;
1406 setup_allocno_left_conflicts_num (allocno);
1407 setup_allocno_available_regs_num (allocno);
1408 if (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
1409 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)]
1410 <= ALLOCNO_AVAILABLE_REGS_NUM (allocno))
1411 add_ira_allocno_to_bucket (allocno, &colorable_allocno_bucket);
1413 add_ira_allocno_to_bucket (allocno, &uncolorable_allocno_bucket);
1416 /* The function is used to sort allocnos according to their execution
1419 copy_freq_compare_func (const void *v1p, const void *v2p)
1421 ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p;
1429 /* If freqencies are equal, sort by copies, so that the results of
1430 qsort leave nothing to chance. */
1431 return cp1->num - cp2->num;
1434 /* Merge two sets of coalesced allocnos given correspondingly by
1435 allocnos A1 and A2 (more accurately merging A2 set into A1
1438 merge_allocnos (ira_allocno_t a1, ira_allocno_t a2)
1440 ira_allocno_t a, first, last, next;
1442 first = ALLOCNO_FIRST_COALESCED_ALLOCNO (a1);
1443 if (first == ALLOCNO_FIRST_COALESCED_ALLOCNO (a2))
1445 for (last = a2, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
1446 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1448 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = first;
1453 next = ALLOCNO_NEXT_COALESCED_ALLOCNO (first);
1454 ALLOCNO_NEXT_COALESCED_ALLOCNO (first) = a2;
1455 ALLOCNO_NEXT_COALESCED_ALLOCNO (last) = next;
1458 /* Return TRUE if there are conflicting allocnos from two sets of
1459 coalesced allocnos given correspondingly by allocnos A1 and A2. If
1460 RELOAD_P is TRUE, we use live ranges to find conflicts because
1461 conflicts are represented only for allocnos of the same cover class
1462 and during the reload pass we coalesce allocnos for sharing stack
1465 coalesced_allocno_conflict_p (ira_allocno_t a1, ira_allocno_t a2,
1468 ira_allocno_t a, conflict_allocno;
1469 ira_allocno_conflict_iterator aci;
1471 if (allocno_coalesced_p)
1473 bitmap_clear (processed_coalesced_allocno_bitmap);
1474 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
1475 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1477 bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a));
1482 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
1483 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1487 for (conflict_allocno = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
1489 = ALLOCNO_NEXT_COALESCED_ALLOCNO (conflict_allocno))
1491 if (ira_allocno_live_ranges_intersect_p (a, conflict_allocno))
1493 if (conflict_allocno == a1)
1499 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
1500 if (conflict_allocno == a1
1501 || (allocno_coalesced_p
1502 && bitmap_bit_p (processed_coalesced_allocno_bitmap,
1503 ALLOCNO_NUM (conflict_allocno))))
1512 /* The major function for aggressive allocno coalescing. For the
1513 reload pass (RELOAD_P) we coalesce only spilled allocnos. If some
1514 allocnos have been coalesced, we set up flag
1515 allocno_coalesced_p. */
1517 coalesce_allocnos (bool reload_p)
1520 ira_copy_t cp, next_cp, *sorted_copies;
1521 enum reg_class cover_class;
1522 enum machine_mode mode;
1524 int i, n, cp_num, regno;
1527 sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num
1528 * sizeof (ira_copy_t));
1530 /* Collect copies. */
1531 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
1533 a = ira_allocnos[j];
1534 regno = ALLOCNO_REGNO (a);
1535 if ((! reload_p && ALLOCNO_ASSIGNED_P (a))
1537 && (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0
1538 || (regno < ira_reg_equiv_len
1539 && (ira_reg_equiv_const[regno] != NULL_RTX
1540 || ira_reg_equiv_invariant_p[regno])))))
1542 cover_class = ALLOCNO_COVER_CLASS (a);
1543 mode = ALLOCNO_MODE (a);
1544 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
1548 next_cp = cp->next_first_allocno_copy;
1549 regno = ALLOCNO_REGNO (cp->second);
1551 || (ALLOCNO_COVER_CLASS (cp->second) == cover_class
1552 && ALLOCNO_MODE (cp->second) == mode))
1554 && ((! reload_p && ! ALLOCNO_ASSIGNED_P (cp->second))
1556 && ALLOCNO_ASSIGNED_P (cp->second)
1557 && ALLOCNO_HARD_REGNO (cp->second) < 0
1558 && (regno >= ira_reg_equiv_len
1559 || (! ira_reg_equiv_invariant_p[regno]
1560 && ira_reg_equiv_const[regno] == NULL_RTX)))))
1561 sorted_copies[cp_num++] = cp;
1563 else if (cp->second == a)
1564 next_cp = cp->next_second_allocno_copy;
1569 qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
1570 /* Coalesced copies, most frequently executed first. */
1571 for (; cp_num != 0;)
1573 for (i = 0; i < cp_num; i++)
1575 cp = sorted_copies[i];
1576 if (! coalesced_allocno_conflict_p (cp->first, cp->second, reload_p))
1578 allocno_coalesced_p = true;
1579 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1582 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
1583 cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
1584 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
1586 merge_allocnos (cp->first, cp->second);
1591 /* Collect the rest of copies. */
1592 for (n = 0; i < cp_num; i++)
1594 cp = sorted_copies[i];
1595 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->first)
1596 != ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->second))
1597 sorted_copies[n++] = cp;
1601 ira_free (sorted_copies);
1604 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
1605 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
1607 color_allocnos (void)
1613 allocno_coalesced_p = false;
1614 processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
1615 if (flag_ira_coalesce)
1616 coalesce_allocnos (false);
1617 /* Put the allocnos into the corresponding buckets. */
1618 colorable_allocno_bucket = NULL;
1619 uncolorable_allocno_bucket = NULL;
1620 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1622 a = ira_allocnos[i];
1623 if (ALLOCNO_COVER_CLASS (a) == NO_REGS)
1625 ALLOCNO_HARD_REGNO (a) = -1;
1626 ALLOCNO_ASSIGNED_P (a) = true;
1627 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
1628 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
1629 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1631 fprintf (ira_dump_file, " Spill");
1632 print_coalesced_allocno (a);
1633 fprintf (ira_dump_file, "\n");
1637 put_allocno_into_bucket (a);
1639 push_allocnos_to_stack ();
1640 pop_allocnos_from_stack ();
1641 if (flag_ira_coalesce)
1642 /* We don't need coalesced allocnos for ira_reassign_pseudos. */
1643 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1645 a = ira_allocnos[i];
1646 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
1647 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
1649 ira_free_bitmap (processed_coalesced_allocno_bitmap);
1650 allocno_coalesced_p = false;
1655 /* Output information about the loop given by its LOOP_TREE_NODE. */
1657 print_loop_title (ira_loop_tree_node_t loop_tree_node)
1662 ira_assert (loop_tree_node->loop != NULL);
1663 fprintf (ira_dump_file,
1664 "\n Loop %d (parent %d, header bb%d, depth %d)\n all:",
1665 loop_tree_node->loop->num,
1666 (loop_tree_node->parent == NULL
1667 ? -1 : loop_tree_node->parent->loop->num),
1668 loop_tree_node->loop->header->index,
1669 loop_depth (loop_tree_node->loop));
1670 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
1671 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
1672 fprintf (ira_dump_file, "\n modified regnos:");
1673 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->modified_regnos, 0, j, bi)
1674 fprintf (ira_dump_file, " %d", j);
1675 fprintf (ira_dump_file, "\n border:");
1676 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->border_allocnos, 0, j, bi)
1677 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
1678 fprintf (ira_dump_file, "\n Pressure:");
1679 for (j = 0; (int) j < ira_reg_class_cover_size; j++)
1681 enum reg_class cover_class;
1683 cover_class = ira_reg_class_cover[j];
1684 if (loop_tree_node->reg_pressure[cover_class] == 0)
1686 fprintf (ira_dump_file, " %s=%d", reg_class_names[cover_class],
1687 loop_tree_node->reg_pressure[cover_class]);
1689 fprintf (ira_dump_file, "\n");
1692 /* Color the allocnos inside loop (in the extreme case it can be all
1693 of the function) given the corresponding LOOP_TREE_NODE. The
1694 function is called for each loop during top-down traverse of the
1697 color_pass (ira_loop_tree_node_t loop_tree_node)
1699 int regno, hard_regno, index = -1;
1700 int cost, exit_freq, enter_freq;
1703 enum machine_mode mode;
1704 enum reg_class rclass, cover_class;
1705 ira_allocno_t a, subloop_allocno;
1706 ira_loop_tree_node_t subloop_node;
1708 ira_assert (loop_tree_node->bb == NULL);
1709 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1710 print_loop_title (loop_tree_node);
1712 bitmap_copy (coloring_allocno_bitmap, loop_tree_node->all_allocnos);
1713 bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap);
1714 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
1716 a = ira_allocnos[j];
1717 if (! ALLOCNO_ASSIGNED_P (a))
1719 bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a));
1721 /* Color all mentioned allocnos including transparent ones. */
1723 /* Process caps. They are processed just once. */
1724 if (flag_ira_algorithm == IRA_ALGORITHM_MIXED
1725 || flag_ira_algorithm == IRA_ALGORITHM_REGIONAL)
1726 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
1728 a = ira_allocnos[j];
1729 if (ALLOCNO_CAP_MEMBER (a) == NULL)
1731 /* Remove from processing in the next loop. */
1732 bitmap_clear_bit (consideration_allocno_bitmap, j);
1733 rclass = ALLOCNO_COVER_CLASS (a);
1734 if ((flag_ira_algorithm == IRA_ALGORITHM_MIXED
1735 && loop_tree_node->reg_pressure[rclass]
1736 <= ira_available_class_regs[rclass]))
1738 mode = ALLOCNO_MODE (a);
1739 hard_regno = ALLOCNO_HARD_REGNO (a);
1740 if (hard_regno >= 0)
1742 index = ira_class_hard_reg_index[rclass][hard_regno];
1743 ira_assert (index >= 0);
1745 regno = ALLOCNO_REGNO (a);
1746 subloop_allocno = ALLOCNO_CAP_MEMBER (a);
1747 subloop_node = ALLOCNO_LOOP_TREE_NODE (subloop_allocno);
1748 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno));
1749 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
1750 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
1751 if (hard_regno >= 0)
1752 update_copy_costs (subloop_allocno, true);
1753 /* We don't need updated costs anymore: */
1754 ira_free_allocno_updated_costs (subloop_allocno);
1757 /* Update costs of the corresponding allocnos (not caps) in the
1759 for (subloop_node = loop_tree_node->subloops;
1760 subloop_node != NULL;
1761 subloop_node = subloop_node->subloop_next)
1763 ira_assert (subloop_node->bb == NULL);
1764 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
1766 a = ira_allocnos[j];
1767 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
1768 mode = ALLOCNO_MODE (a);
1769 rclass = ALLOCNO_COVER_CLASS (a);
1770 hard_regno = ALLOCNO_HARD_REGNO (a);
1771 if (hard_regno >= 0)
1773 index = ira_class_hard_reg_index[rclass][hard_regno];
1774 ira_assert (index >= 0);
1776 regno = ALLOCNO_REGNO (a);
1777 /* ??? conflict costs */
1778 subloop_allocno = subloop_node->regno_allocno_map[regno];
1779 if (subloop_allocno == NULL
1780 || ALLOCNO_CAP (subloop_allocno) != NULL)
1782 ira_assert (bitmap_bit_p (subloop_node->all_allocnos,
1783 ALLOCNO_NUM (subloop_allocno)));
1784 if (flag_ira_algorithm == IRA_ALGORITHM_MIXED
1785 && (loop_tree_node->reg_pressure[rclass]
1786 <= ira_available_class_regs[rclass]))
1788 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
1790 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
1791 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
1792 if (hard_regno >= 0)
1793 update_copy_costs (subloop_allocno, true);
1794 /* We don't need updated costs anymore: */
1795 ira_free_allocno_updated_costs (subloop_allocno);
1799 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
1800 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
1801 ira_assert (regno < ira_reg_equiv_len);
1802 if (ira_reg_equiv_invariant_p[regno]
1803 || ira_reg_equiv_const[regno] != NULL_RTX)
1805 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
1807 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
1808 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
1809 if (hard_regno >= 0)
1810 update_copy_costs (subloop_allocno, true);
1811 /* We don't need updated costs anymore: */
1812 ira_free_allocno_updated_costs (subloop_allocno);
1815 else if (hard_regno < 0)
1817 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
1818 -= ((ira_memory_move_cost[mode][rclass][1] * enter_freq)
1819 + (ira_memory_move_cost[mode][rclass][0] * exit_freq));
1823 cover_class = ALLOCNO_COVER_CLASS (subloop_allocno);
1824 ira_allocate_and_set_costs
1825 (&ALLOCNO_HARD_REG_COSTS (subloop_allocno), cover_class,
1826 ALLOCNO_COVER_CLASS_COST (subloop_allocno));
1827 ira_allocate_and_set_costs
1828 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno),
1830 cost = (ira_register_move_cost[mode][rclass][rclass]
1831 * (exit_freq + enter_freq));
1832 ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
1833 ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
1835 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
1836 += (ira_memory_move_cost[mode][rclass][0] * enter_freq
1837 + ira_memory_move_cost[mode][rclass][1] * exit_freq);
1838 if (ALLOCNO_COVER_CLASS_COST (subloop_allocno)
1839 > ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index])
1840 ALLOCNO_COVER_CLASS_COST (subloop_allocno)
1841 = ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index];
1847 /* Initialize the common data for coloring and calls functions to do
1848 Chaitin-Briggs and regional coloring. */
1852 coloring_allocno_bitmap = ira_allocate_bitmap ();
1853 allocnos_for_spilling
1854 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
1855 * ira_allocnos_num);
1856 splay_tree_node_pool = create_alloc_pool ("splay tree nodes",
1857 sizeof (struct splay_tree_node_s),
1859 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
1860 fprintf (ira_dump_file, "\n**** Allocnos coloring:\n\n");
1862 ira_traverse_loop_tree (false, ira_loop_tree_root, color_pass, NULL);
1864 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1865 ira_print_disposition (ira_dump_file);
1867 free_alloc_pool (splay_tree_node_pool);
1868 ira_free_bitmap (coloring_allocno_bitmap);
1869 ira_free (allocnos_for_spilling);
1874 /* Move spill/restore code, which are to be generated in ira-emit.c,
1875 to less frequent points (if it is profitable) by reassigning some
1876 allocnos (in loop with subloops containing in another loop) to
1877 memory which results in longer live-range where the corresponding
1878 pseudo-registers will be in memory. */
1880 move_spill_restore (void)
1882 int cost, regno, hard_regno, hard_regno2, index;
1884 int enter_freq, exit_freq;
1885 enum machine_mode mode;
1886 enum reg_class rclass;
1887 ira_allocno_t a, parent_allocno, subloop_allocno;
1888 ira_loop_tree_node_t parent, loop_node, subloop_node;
1889 ira_allocno_iterator ai;
1894 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
1895 fprintf (ira_dump_file, "New iteration of spill/restore move\n");
1896 FOR_EACH_ALLOCNO (a, ai)
1898 regno = ALLOCNO_REGNO (a);
1899 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
1900 if (ALLOCNO_CAP_MEMBER (a) != NULL
1901 || ALLOCNO_CAP (a) != NULL
1902 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0
1903 || loop_node->children == NULL
1904 /* don't do the optimization because it can create
1905 copies and the reload pass can spill the allocno set
1906 by copy although the allocno will not get memory
1908 || ira_reg_equiv_invariant_p[regno]
1909 || ira_reg_equiv_const[regno] != NULL_RTX
1910 || !bitmap_bit_p (loop_node->border_allocnos, ALLOCNO_NUM (a)))
1912 mode = ALLOCNO_MODE (a);
1913 rclass = ALLOCNO_COVER_CLASS (a);
1914 index = ira_class_hard_reg_index[rclass][hard_regno];
1915 ira_assert (index >= 0);
1916 cost = (ALLOCNO_MEMORY_COST (a)
1917 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
1918 ? ALLOCNO_COVER_CLASS_COST (a)
1919 : ALLOCNO_HARD_REG_COSTS (a)[index]));
1920 for (subloop_node = loop_node->subloops;
1921 subloop_node != NULL;
1922 subloop_node = subloop_node->subloop_next)
1924 ira_assert (subloop_node->bb == NULL);
1925 subloop_allocno = subloop_node->regno_allocno_map[regno];
1926 if (subloop_allocno == NULL)
1928 /* We have accumulated cost. To get the real cost of
1929 allocno usage in the loop we should subtract costs of
1930 the subloop allocnos. */
1931 cost -= (ALLOCNO_MEMORY_COST (subloop_allocno)
1932 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno) == NULL
1933 ? ALLOCNO_COVER_CLASS_COST (subloop_allocno)
1934 : ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index]));
1935 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
1936 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
1937 if ((hard_regno2 = ALLOCNO_HARD_REGNO (subloop_allocno)) < 0)
1938 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
1939 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
1943 += (ira_memory_move_cost[mode][rclass][0] * exit_freq
1944 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
1945 if (hard_regno2 != hard_regno)
1946 cost -= (ira_register_move_cost[mode][rclass][rclass]
1947 * (exit_freq + enter_freq));
1950 if ((parent = loop_node->parent) != NULL
1951 && (parent_allocno = parent->regno_allocno_map[regno]) != NULL)
1953 exit_freq = ira_loop_edge_freq (loop_node, regno, true);
1954 enter_freq = ira_loop_edge_freq (loop_node, regno, false);
1955 if ((hard_regno2 = ALLOCNO_HARD_REGNO (parent_allocno)) < 0)
1956 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
1957 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
1961 += (ira_memory_move_cost[mode][rclass][1] * exit_freq
1962 + ira_memory_move_cost[mode][rclass][0] * enter_freq);
1963 if (hard_regno2 != hard_regno)
1964 cost -= (ira_register_move_cost[mode][rclass][rclass]
1965 * (exit_freq + enter_freq));
1970 ALLOCNO_HARD_REGNO (a) = -1;
1971 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1975 " Moving spill/restore for a%dr%d up from loop %d",
1976 ALLOCNO_NUM (a), regno, loop_node->loop->num);
1977 fprintf (ira_dump_file, " - profit %d\n", -cost);
1989 /* Update current hard reg costs and current conflict hard reg costs
1990 for allocno A. It is done by processing its copies containing
1991 other allocnos already assigned. */
1993 update_curr_costs (ira_allocno_t a)
1995 int i, hard_regno, cost;
1996 enum machine_mode mode;
1997 enum reg_class cover_class, rclass;
1998 ira_allocno_t another_a;
1999 ira_copy_t cp, next_cp;
2001 ira_assert (! ALLOCNO_ASSIGNED_P (a));
2002 cover_class = ALLOCNO_COVER_CLASS (a);
2003 if (cover_class == NO_REGS)
2005 mode = ALLOCNO_MODE (a);
2006 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2010 next_cp = cp->next_first_allocno_copy;
2011 another_a = cp->second;
2013 else if (cp->second == a)
2015 next_cp = cp->next_second_allocno_copy;
2016 another_a = cp->first;
2020 if (cover_class != ALLOCNO_COVER_CLASS (another_a)
2021 || ! ALLOCNO_ASSIGNED_P (another_a)
2022 || (hard_regno = ALLOCNO_HARD_REGNO (another_a)) < 0)
2024 rclass = REGNO_REG_CLASS (hard_regno);
2025 i = ira_class_hard_reg_index[cover_class][hard_regno];
2026 ira_assert (i >= 0);
2027 cost = (cp->first == a
2028 ? ira_register_move_cost[mode][rclass][cover_class]
2029 : ira_register_move_cost[mode][cover_class][rclass]);
2030 ira_allocate_and_set_or_copy_costs
2031 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
2032 cover_class, ALLOCNO_COVER_CLASS_COST (a),
2033 ALLOCNO_HARD_REG_COSTS (a));
2034 ira_allocate_and_set_or_copy_costs
2035 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
2036 cover_class, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
2037 ALLOCNO_UPDATED_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
2038 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
2042 /* Map: allocno number -> allocno priority. */
2043 static int *allocno_priorities;
2045 /* Allocate array ALLOCNO_PRIORITIES and set up priorities for N allocnos in
2046 array CONSIDERATION_ALLOCNOS. */
2048 start_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
2052 allocno_live_range_t r;
2054 for (i = 0; i < n; i++)
2056 a = consideration_allocnos[i];
2057 for (length = 0, r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
2058 length += r->finish - r->start + 1;
2061 allocno_priorities[ALLOCNO_NUM (a)] = 0;
2064 ira_assert (length > 0 && ALLOCNO_NREFS (a) >= 0);
2065 allocno_priorities[ALLOCNO_NUM (a)]
2066 = (((double) (floor_log2 (ALLOCNO_NREFS (a)) * ALLOCNO_FREQ (a))
2068 * (10000 / REG_FREQ_MAX) * PSEUDO_REGNO_SIZE (ALLOCNO_REGNO (a)));
2072 /* Sort allocnos according to their priorities which are calculated
2073 analogous to ones in file `global.c'. */
2075 allocno_priority_compare_func (const void *v1p, const void *v2p)
2077 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2078 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2081 pri1 = allocno_priorities[ALLOCNO_NUM (a1)];
2082 pri2 = allocno_priorities[ALLOCNO_NUM (a2)];
2086 /* If regs are equally good, sort by allocnos, so that the results of
2087 qsort leave nothing to chance. */
2088 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2091 /* Try to assign hard registers to the unassigned allocnos and
2092 allocnos conflicting with them or conflicting with allocnos whose
2093 regno >= START_REGNO. The function is called after ira_flattening,
2094 so more allocnos (including ones created in ira-emit.c) will have a
2095 chance to get a hard register. We use simple assignment algorithm
2096 based on priorities. */
2098 ira_reassign_conflict_allocnos (int start_regno)
2100 int i, allocnos_to_color_num;
2101 ira_allocno_t a, conflict_a;
2102 ira_allocno_conflict_iterator aci;
2103 enum reg_class cover_class;
2104 bitmap allocnos_to_color;
2105 ira_allocno_iterator ai;
2107 allocnos_to_color = ira_allocate_bitmap ();
2108 allocnos_to_color_num = 0;
2109 FOR_EACH_ALLOCNO (a, ai)
2111 if (! ALLOCNO_ASSIGNED_P (a)
2112 && ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a)))
2114 if (ALLOCNO_COVER_CLASS (a) != NO_REGS)
2115 sorted_allocnos[allocnos_to_color_num++] = a;
2118 ALLOCNO_ASSIGNED_P (a) = true;
2119 ALLOCNO_HARD_REGNO (a) = -1;
2120 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2121 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2123 bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (a));
2125 if (ALLOCNO_REGNO (a) < start_regno
2126 || (cover_class = ALLOCNO_COVER_CLASS (a)) == NO_REGS)
2128 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
2130 ira_assert (cover_class == ALLOCNO_COVER_CLASS (conflict_a));
2131 if (bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (conflict_a)))
2133 bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a));
2134 sorted_allocnos[allocnos_to_color_num++] = conflict_a;
2137 ira_free_bitmap (allocnos_to_color);
2138 if (allocnos_to_color_num > 1)
2140 start_allocno_priorities (sorted_allocnos, allocnos_to_color_num);
2141 qsort (sorted_allocnos, allocnos_to_color_num, sizeof (ira_allocno_t),
2142 allocno_priority_compare_func);
2144 for (i = 0; i < allocnos_to_color_num; i++)
2146 a = sorted_allocnos[i];
2147 ALLOCNO_ASSIGNED_P (a) = false;
2148 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2149 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2150 update_curr_costs (a);
2152 for (i = 0; i < allocnos_to_color_num; i++)
2154 a = sorted_allocnos[i];
2155 if (assign_hard_reg (a, true))
2157 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2160 " Secondary allocation: assign hard reg %d to reg %d\n",
2161 ALLOCNO_HARD_REGNO (a), ALLOCNO_REGNO (a));
2168 /* This page contains code to coalesce memory stack slots used by
2169 spilled allocnos. This results in smaller stack frame, better data
2170 locality, and in smaller code for some architectures like
2171 x86/x86_64 where insn size depends on address displacement value.
2172 On the other hand, it can worsen insn scheduling after the RA but
2173 in practice it is less important than smaller stack frames. */
2175 /* Usage cost and order number of coalesced allocno set to which
2176 given pseudo register belongs to. */
2177 static int *regno_coalesced_allocno_cost;
2178 static int *regno_coalesced_allocno_num;
2180 /* Sort pseudos according frequencies of coalesced allocno sets they
2181 belong to (putting most frequently ones first), and according to
2182 coalesced allocno set order numbers. */
2184 coalesced_pseudo_reg_freq_compare (const void *v1p, const void *v2p)
2186 const int regno1 = *(const int *) v1p;
2187 const int regno2 = *(const int *) v2p;
2190 if ((diff = (regno_coalesced_allocno_cost[regno2]
2191 - regno_coalesced_allocno_cost[regno1])) != 0)
2193 if ((diff = (regno_coalesced_allocno_num[regno1]
2194 - regno_coalesced_allocno_num[regno2])) != 0)
2196 return regno1 - regno2;
2199 /* Widest width in which each pseudo reg is referred to (via subreg).
2200 It is used for sorting pseudo registers. */
2201 static unsigned int *regno_max_ref_width;
2203 /* Redefine STACK_GROWS_DOWNWARD in terms of 0 or 1. */
2204 #ifdef STACK_GROWS_DOWNWARD
2205 # undef STACK_GROWS_DOWNWARD
2206 # define STACK_GROWS_DOWNWARD 1
2208 # define STACK_GROWS_DOWNWARD 0
2211 /* Sort pseudos according their slot numbers (putting ones with
2212 smaller numbers first, or last when the frame pointer is not
2215 coalesced_pseudo_reg_slot_compare (const void *v1p, const void *v2p)
2217 const int regno1 = *(const int *) v1p;
2218 const int regno2 = *(const int *) v2p;
2219 ira_allocno_t a1 = ira_regno_allocno_map[regno1];
2220 ira_allocno_t a2 = ira_regno_allocno_map[regno2];
2221 int diff, slot_num1, slot_num2;
2222 int total_size1, total_size2;
2224 if (a1 == NULL || ALLOCNO_HARD_REGNO (a1) >= 0)
2226 if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
2227 return regno1 - regno2;
2230 else if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
2232 slot_num1 = -ALLOCNO_HARD_REGNO (a1);
2233 slot_num2 = -ALLOCNO_HARD_REGNO (a2);
2234 if ((diff = slot_num1 - slot_num2) != 0)
2235 return (frame_pointer_needed
2236 || !FRAME_GROWS_DOWNWARD == STACK_GROWS_DOWNWARD ? diff : -diff);
2237 total_size1 = MAX (PSEUDO_REGNO_BYTES (regno1), regno_max_ref_width[regno1]);
2238 total_size2 = MAX (PSEUDO_REGNO_BYTES (regno2), regno_max_ref_width[regno2]);
2239 if ((diff = total_size2 - total_size1) != 0)
2241 return regno1 - regno2;
2244 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
2245 for coalesced allocno sets containing allocnos with their regnos
2246 given in array PSEUDO_REGNOS of length N. */
2248 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos, int n)
2250 int i, num, regno, cost;
2251 ira_allocno_t allocno, a;
2253 for (num = i = 0; i < n; i++)
2255 regno = pseudo_regnos[i];
2256 allocno = ira_regno_allocno_map[regno];
2257 if (allocno == NULL)
2259 regno_coalesced_allocno_cost[regno] = 0;
2260 regno_coalesced_allocno_num[regno] = ++num;
2263 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
2266 for (cost = 0, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2267 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2269 cost += ALLOCNO_FREQ (a);
2273 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2274 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2276 regno_coalesced_allocno_num[ALLOCNO_REGNO (a)] = num;
2277 regno_coalesced_allocno_cost[ALLOCNO_REGNO (a)] = cost;
2284 /* Collect spilled allocnos representing coalesced allocno sets (the
2285 first coalesced allocno). The collected allocnos are returned
2286 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
2287 number of the collected allocnos. The allocnos are given by their
2288 regnos in array PSEUDO_REGNOS of length N. */
2290 collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n,
2291 ira_allocno_t *spilled_coalesced_allocnos)
2294 ira_allocno_t allocno;
2296 for (num = i = 0; i < n; i++)
2298 regno = pseudo_regnos[i];
2299 allocno = ira_regno_allocno_map[regno];
2300 if (allocno == NULL || ALLOCNO_HARD_REGNO (allocno) >= 0
2301 || ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
2303 spilled_coalesced_allocnos[num++] = allocno;
2308 /* We have coalesced allocnos involving in copies. Coalesce allocnos
2309 further in order to share the same memory stack slot. Allocnos
2310 representing sets of allocnos coalesced before the call are given
2311 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
2312 some allocnos were coalesced in the function. */
2314 coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num)
2317 ira_allocno_t allocno, a;
2318 bool merged_p = false;
2320 /* Coalesce non-conflicting spilled allocnos preferring most
2322 for (i = 0; i < num; i++)
2324 allocno = spilled_coalesced_allocnos[i];
2325 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno
2326 || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
2327 && (ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)]
2328 || ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX)))
2330 for (j = 0; j < i; j++)
2332 a = spilled_coalesced_allocnos[j];
2333 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) != a
2334 || (ALLOCNO_REGNO (a) < ira_reg_equiv_len
2335 && (ira_reg_equiv_invariant_p[ALLOCNO_REGNO (a)]
2336 || ira_reg_equiv_const[ALLOCNO_REGNO (a)] != NULL_RTX))
2337 || coalesced_allocno_conflict_p (allocno, a, true))
2339 allocno_coalesced_p = true;
2341 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2342 fprintf (ira_dump_file,
2343 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
2344 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno),
2345 ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2346 merge_allocnos (a, allocno);
2347 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a);
2353 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
2354 subsequent assigning stack slots to them in the reload pass. To do
2355 this we coalesce spilled allocnos first to decrease the number of
2356 memory-memory move insns. This function is called by the
2359 ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n,
2360 unsigned int *reg_max_ref_width)
2362 int max_regno = max_reg_num ();
2363 int i, regno, num, slot_num;
2364 ira_allocno_t allocno, a;
2365 ira_allocno_iterator ai;
2366 ira_allocno_t *spilled_coalesced_allocnos;
2368 processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
2369 /* Set up allocnos can be coalesced. */
2370 coloring_allocno_bitmap = ira_allocate_bitmap ();
2371 for (i = 0; i < n; i++)
2373 regno = pseudo_regnos[i];
2374 allocno = ira_regno_allocno_map[regno];
2375 if (allocno != NULL)
2376 bitmap_set_bit (coloring_allocno_bitmap,
2377 ALLOCNO_NUM (allocno));
2379 allocno_coalesced_p = false;
2380 coalesce_allocnos (true);
2381 ira_free_bitmap (coloring_allocno_bitmap);
2382 regno_coalesced_allocno_cost
2383 = (int *) ira_allocate (max_regno * sizeof (int));
2384 regno_coalesced_allocno_num
2385 = (int *) ira_allocate (max_regno * sizeof (int));
2386 memset (regno_coalesced_allocno_num, 0, max_regno * sizeof (int));
2387 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
2388 /* Sort regnos according frequencies of the corresponding coalesced
2390 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_freq_compare);
2391 spilled_coalesced_allocnos
2392 = (ira_allocno_t *) ira_allocate (ira_allocnos_num
2393 * sizeof (ira_allocno_t));
2394 /* Collect allocnos representing the spilled coalesced allocno
2396 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
2397 spilled_coalesced_allocnos);
2398 if (flag_ira_share_spill_slots
2399 && coalesce_spill_slots (spilled_coalesced_allocnos, num))
2401 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
2402 qsort (pseudo_regnos, n, sizeof (int),
2403 coalesced_pseudo_reg_freq_compare);
2404 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
2405 spilled_coalesced_allocnos);
2407 ira_free_bitmap (processed_coalesced_allocno_bitmap);
2408 allocno_coalesced_p = false;
2409 /* Assign stack slot numbers to spilled allocno sets, use smaller
2410 numbers for most frequently used coalesced allocnos. -1 is
2411 reserved for dynamic search of stack slots for pseudos spilled by
2414 for (i = 0; i < num; i++)
2416 allocno = spilled_coalesced_allocnos[i];
2417 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno
2418 || ALLOCNO_HARD_REGNO (allocno) >= 0
2419 || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
2420 && (ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)]
2421 || ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX)))
2423 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2424 fprintf (ira_dump_file, " Slot %d (freq,size):", slot_num);
2426 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2427 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2429 ira_assert (ALLOCNO_HARD_REGNO (a) < 0);
2430 ALLOCNO_HARD_REGNO (a) = -slot_num;
2431 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2432 fprintf (ira_dump_file, " a%dr%d(%d,%d)",
2433 ALLOCNO_NUM (a), ALLOCNO_REGNO (a), ALLOCNO_FREQ (a),
2434 MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a)),
2435 reg_max_ref_width[ALLOCNO_REGNO (a)]));
2440 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2441 fprintf (ira_dump_file, "\n");
2443 ira_spilled_reg_stack_slots_num = slot_num - 1;
2444 ira_free (spilled_coalesced_allocnos);
2445 /* Sort regnos according the slot numbers. */
2446 regno_max_ref_width = reg_max_ref_width;
2447 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_slot_compare);
2448 /* Uncoalesce allocnos which is necessary for (re)assigning during
2450 FOR_EACH_ALLOCNO (a, ai)
2452 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
2453 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
2455 ira_free (regno_coalesced_allocno_num);
2456 ira_free (regno_coalesced_allocno_cost);
2461 /* This page contains code used by the reload pass to improve the
2464 /* The function is called from reload to mark changes in the
2465 allocation of REGNO made by the reload. Remember that reg_renumber
2466 reflects the change result. */
2468 ira_mark_allocation_change (int regno)
2470 ira_allocno_t a = ira_regno_allocno_map[regno];
2471 int old_hard_regno, hard_regno, cost;
2472 enum reg_class cover_class = ALLOCNO_COVER_CLASS (a);
2474 ira_assert (a != NULL);
2475 hard_regno = reg_renumber[regno];
2476 if ((old_hard_regno = ALLOCNO_HARD_REGNO (a)) == hard_regno)
2478 if (old_hard_regno < 0)
2479 cost = -ALLOCNO_MEMORY_COST (a);
2482 ira_assert (ira_class_hard_reg_index[cover_class][old_hard_regno] >= 0);
2483 cost = -(ALLOCNO_HARD_REG_COSTS (a) == NULL
2484 ? ALLOCNO_COVER_CLASS_COST (a)
2485 : ALLOCNO_HARD_REG_COSTS (a)
2486 [ira_class_hard_reg_index[cover_class][old_hard_regno]]);
2487 update_copy_costs (a, false);
2489 ira_overall_cost -= cost;
2490 ALLOCNO_HARD_REGNO (a) = hard_regno;
2493 ALLOCNO_HARD_REGNO (a) = -1;
2494 cost += ALLOCNO_MEMORY_COST (a);
2496 else if (ira_class_hard_reg_index[cover_class][hard_regno] >= 0)
2498 cost += (ALLOCNO_HARD_REG_COSTS (a) == NULL
2499 ? ALLOCNO_COVER_CLASS_COST (a)
2500 : ALLOCNO_HARD_REG_COSTS (a)
2501 [ira_class_hard_reg_index[cover_class][hard_regno]]);
2502 update_copy_costs (a, true);
2505 /* Reload changed class of the allocno. */
2507 ira_overall_cost += cost;
2510 /* This function is called when reload deletes memory-memory move. In
2511 this case we marks that the allocation of the corresponding
2512 allocnos should be not changed in future. Otherwise we risk to get
2515 ira_mark_memory_move_deletion (int dst_regno, int src_regno)
2517 ira_allocno_t dst = ira_regno_allocno_map[dst_regno];
2518 ira_allocno_t src = ira_regno_allocno_map[src_regno];
2520 ira_assert (dst != NULL && src != NULL
2521 && ALLOCNO_HARD_REGNO (dst) < 0
2522 && ALLOCNO_HARD_REGNO (src) < 0);
2523 ALLOCNO_DONT_REASSIGN_P (dst) = true;
2524 ALLOCNO_DONT_REASSIGN_P (src) = true;
2527 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
2528 allocno A and return TRUE in the case of success. That is an
2529 analog of retry_global_alloc for IRA. */
2531 allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs)
2534 enum reg_class cover_class;
2535 int regno = ALLOCNO_REGNO (a);
2537 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), forbidden_regs);
2538 if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
2539 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), call_used_reg_set);
2540 ALLOCNO_ASSIGNED_P (a) = false;
2541 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2542 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2543 cover_class = ALLOCNO_COVER_CLASS (a);
2544 update_curr_costs (a);
2545 assign_hard_reg (a, true);
2546 hard_regno = ALLOCNO_HARD_REGNO (a);
2547 reg_renumber[regno] = hard_regno;
2549 ALLOCNO_HARD_REGNO (a) = -1;
2552 ira_assert (ira_class_hard_reg_index[cover_class][hard_regno] >= 0);
2553 ira_overall_cost -= (ALLOCNO_MEMORY_COST (a)
2554 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
2555 ? ALLOCNO_COVER_CLASS_COST (a)
2556 : ALLOCNO_HARD_REG_COSTS (a)
2557 [ira_class_hard_reg_index
2558 [cover_class][hard_regno]]));
2559 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
2560 && ! ira_hard_reg_not_in_set_p (hard_regno, ALLOCNO_MODE (a),
2563 ira_assert (flag_caller_saves);
2564 caller_save_needed = 1;
2568 /* If we found a hard register, modify the RTL for the pseudo
2569 register to show the hard register, and mark the pseudo register
2571 if (reg_renumber[regno] >= 0)
2573 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2574 fprintf (ira_dump_file, ": reassign to %d\n", reg_renumber[regno]);
2575 SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
2576 mark_home_live (regno);
2578 else if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2579 fprintf (ira_dump_file, "\n");
2581 return reg_renumber[regno] >= 0;
2584 /* Sort pseudos according their usage frequencies (putting most
2585 frequently ones first). */
2587 pseudo_reg_compare (const void *v1p, const void *v2p)
2589 int regno1 = *(const int *) v1p;
2590 int regno2 = *(const int *) v2p;
2593 if ((diff = REG_FREQ (regno2) - REG_FREQ (regno1)) != 0)
2595 return regno1 - regno2;
2598 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
2599 NUM of them) or spilled pseudos conflicting with pseudos in
2600 SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
2601 allocation has been changed. The function doesn't use
2602 BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
2603 PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
2604 is called by the reload pass at the end of each reload
2607 ira_reassign_pseudos (int *spilled_pseudo_regs, int num,
2608 HARD_REG_SET bad_spill_regs,
2609 HARD_REG_SET *pseudo_forbidden_regs,
2610 HARD_REG_SET *pseudo_previous_regs, bitmap spilled)
2614 ira_allocno_t a, conflict_a;
2615 HARD_REG_SET forbidden_regs;
2616 ira_allocno_conflict_iterator aci;
2619 qsort (spilled_pseudo_regs, num, sizeof (int), pseudo_reg_compare);
2621 /* Try to assign hard registers to pseudos from
2622 SPILLED_PSEUDO_REGS. */
2623 for (m = i = 0; i < num; i++)
2625 regno = spilled_pseudo_regs[i];
2626 COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
2627 IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]);
2628 IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]);
2629 gcc_assert (reg_renumber[regno] < 0);
2630 a = ira_regno_allocno_map[regno];
2631 ira_mark_allocation_change (regno);
2632 ira_assert (reg_renumber[regno] < 0);
2633 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2634 fprintf (ira_dump_file,
2635 " Spill %d(a%d), cost=%d", regno, ALLOCNO_NUM (a),
2636 ALLOCNO_MEMORY_COST (a)
2637 - ALLOCNO_COVER_CLASS_COST (a));
2638 allocno_reload_assign (a, forbidden_regs);
2639 if (reg_renumber[regno] >= 0)
2641 CLEAR_REGNO_REG_SET (spilled, regno);
2645 spilled_pseudo_regs[m++] = regno;
2649 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2651 fprintf (ira_dump_file, " Spilled regs");
2652 for (i = 0; i < m; i++)
2653 fprintf (ira_dump_file, " %d", spilled_pseudo_regs[i]);
2654 fprintf (ira_dump_file, "\n");
2656 /* Try to assign hard registers to pseudos conflicting with ones
2657 from SPILLED_PSEUDO_REGS. */
2658 for (i = n = 0; i < m; i++)
2660 regno = spilled_pseudo_regs[i];
2661 a = ira_regno_allocno_map[regno];
2662 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
2663 if (ALLOCNO_HARD_REGNO (conflict_a) < 0
2664 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a)
2665 && ! bitmap_bit_p (consideration_allocno_bitmap,
2666 ALLOCNO_NUM (conflict_a)))
2668 sorted_allocnos[n++] = conflict_a;
2669 bitmap_set_bit (consideration_allocno_bitmap,
2670 ALLOCNO_NUM (conflict_a));
2675 start_allocno_priorities (sorted_allocnos, n);
2676 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
2677 allocno_priority_compare_func);
2678 for (i = 0; i < n; i++)
2680 a = sorted_allocnos[i];
2681 regno = ALLOCNO_REGNO (a);
2682 COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
2683 IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]);
2684 IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]);
2685 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2686 fprintf (ira_dump_file,
2687 " Try assign %d(a%d), cost=%d",
2688 regno, ALLOCNO_NUM (a),
2689 ALLOCNO_MEMORY_COST (a)
2690 - ALLOCNO_COVER_CLASS_COST (a));
2691 if (allocno_reload_assign (a, forbidden_regs))
2694 bitmap_clear_bit (spilled, regno);
2701 /* The function is called by reload and returns already allocated
2702 stack slot (if any) for REGNO with given INHERENT_SIZE and
2703 TOTAL_SIZE. In the case of failure to find a slot which can be
2704 used for REGNO, the function returns NULL. */
2706 ira_reuse_stack_slot (int regno, unsigned int inherent_size,
2707 unsigned int total_size)
2710 int slot_num, best_slot_num;
2711 int cost, best_cost;
2712 ira_copy_t cp, next_cp;
2713 ira_allocno_t another_allocno, allocno = ira_regno_allocno_map[regno];
2716 struct ira_spilled_reg_stack_slot *slot = NULL;
2718 ira_assert (flag_ira && inherent_size == PSEUDO_REGNO_BYTES (regno)
2719 && inherent_size <= total_size
2720 && ALLOCNO_HARD_REGNO (allocno) < 0);
2721 if (! flag_ira_share_spill_slots)
2723 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
2726 slot = &ira_spilled_reg_stack_slots[slot_num];
2731 best_cost = best_slot_num = -1;
2733 /* It means that the pseudo was spilled in the reload pass, try
2736 slot_num < ira_spilled_reg_stack_slots_num;
2739 slot = &ira_spilled_reg_stack_slots[slot_num];
2740 if (slot->mem == NULL_RTX)
2742 if (slot->width < total_size
2743 || GET_MODE_SIZE (GET_MODE (slot->mem)) < inherent_size)
2746 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
2747 FIRST_PSEUDO_REGISTER, i, bi)
2749 another_allocno = ira_regno_allocno_map[i];
2750 if (ira_allocno_live_ranges_intersect_p (allocno,
2754 for (cost = 0, cp = ALLOCNO_COPIES (allocno);
2758 if (cp->first == allocno)
2760 next_cp = cp->next_first_allocno_copy;
2761 another_allocno = cp->second;
2763 else if (cp->second == allocno)
2765 next_cp = cp->next_second_allocno_copy;
2766 another_allocno = cp->first;
2770 if (cp->insn == NULL_RTX)
2772 if (bitmap_bit_p (&slot->spilled_regs,
2773 ALLOCNO_REGNO (another_allocno)))
2776 if (cost > best_cost)
2779 best_slot_num = slot_num;
2786 slot_num = best_slot_num;
2787 slot = &ira_spilled_reg_stack_slots[slot_num];
2788 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
2790 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
2795 ira_assert (slot->width >= total_size);
2796 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
2797 FIRST_PSEUDO_REGISTER, i, bi)
2799 ira_assert (! ira_pseudo_live_ranges_intersect_p (regno, i));
2801 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
2802 if (internal_flag_ira_verbose > 3 && ira_dump_file)
2804 fprintf (ira_dump_file, " Assigning %d(freq=%d) slot %d of",
2805 regno, REG_FREQ (regno), slot_num);
2806 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
2807 FIRST_PSEUDO_REGISTER, i, bi)
2809 if ((unsigned) regno != i)
2810 fprintf (ira_dump_file, " %d", i);
2812 fprintf (ira_dump_file, "\n");
2818 /* This is called by reload every time a new stack slot X with
2819 TOTAL_SIZE was allocated for REGNO. We store this info for
2820 subsequent ira_reuse_stack_slot calls. */
2822 ira_mark_new_stack_slot (rtx x, int regno, unsigned int total_size)
2824 struct ira_spilled_reg_stack_slot *slot;
2826 ira_allocno_t allocno;
2828 ira_assert (flag_ira && PSEUDO_REGNO_BYTES (regno) <= total_size);
2829 allocno = ira_regno_allocno_map[regno];
2830 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
2833 slot_num = ira_spilled_reg_stack_slots_num++;
2834 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
2836 slot = &ira_spilled_reg_stack_slots[slot_num];
2837 INIT_REG_SET (&slot->spilled_regs);
2838 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
2840 slot->width = total_size;
2841 if (internal_flag_ira_verbose > 3 && ira_dump_file)
2842 fprintf (ira_dump_file, " Assigning %d(freq=%d) a new slot %d\n",
2843 regno, REG_FREQ (regno), slot_num);
2847 /* Return spill cost for pseudo-registers whose numbers are in array
2848 REGNOS (with a negative number as an end marker) for reload with
2849 given IN and OUT for INSN. Return also number points (through
2850 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
2851 the register pressure is high, number of references of the
2852 pseudo-registers (through NREFS), number of callee-clobbered
2853 hard-registers occupied by the pseudo-registers (through
2854 CALL_USED_COUNT), and the first hard regno occupied by the
2855 pseudo-registers (through FIRST_HARD_REGNO). */
2857 calculate_spill_cost (int *regnos, rtx in, rtx out, rtx insn,
2858 int *excess_pressure_live_length,
2859 int *nrefs, int *call_used_count, int *first_hard_regno)
2861 int i, cost, regno, hard_regno, j, count, saved_cost, nregs;
2867 for (length = count = cost = i = 0;; i++)
2872 *nrefs += REG_N_REFS (regno);
2873 hard_regno = reg_renumber[regno];
2874 ira_assert (hard_regno >= 0);
2875 a = ira_regno_allocno_map[regno];
2876 length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2877 cost += ALLOCNO_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a);
2878 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
2879 for (j = 0; j < nregs; j++)
2880 if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j))
2884 in_p = in && REG_P (in) && (int) REGNO (in) == hard_regno;
2885 out_p = out && REG_P (out) && (int) REGNO (out) == hard_regno;
2887 && find_regno_note (insn, REG_DEAD, hard_regno) != NULL_RTX)
2891 saved_cost += ira_memory_move_cost
2892 [ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)][1];
2895 += ira_memory_move_cost
2896 [ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)][0];
2897 cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)) * saved_cost;
2900 *excess_pressure_live_length = length;
2901 *call_used_count = count;
2905 hard_regno = reg_renumber[regnos[0]];
2907 *first_hard_regno = hard_regno;
2911 /* Return TRUE if spilling pseudo-registers whose numbers are in array
2912 REGNOS is better than spilling pseudo-registers with numbers in
2913 OTHER_REGNOS for reload with given IN and OUT for INSN. The
2914 function used by the reload pass to make better register spilling
2917 ira_better_spill_reload_regno_p (int *regnos, int *other_regnos,
2918 rtx in, rtx out, rtx insn)
2920 int cost, other_cost;
2921 int length, other_length;
2922 int nrefs, other_nrefs;
2923 int call_used_count, other_call_used_count;
2924 int hard_regno, other_hard_regno;
2926 cost = calculate_spill_cost (regnos, in, out, insn,
2927 &length, &nrefs, &call_used_count, &hard_regno);
2928 other_cost = calculate_spill_cost (other_regnos, in, out, insn,
2929 &other_length, &other_nrefs,
2930 &other_call_used_count,
2932 if (nrefs == 0 && other_nrefs != 0)
2934 if (nrefs != 0 && other_nrefs == 0)
2936 if (cost != other_cost)
2937 return cost < other_cost;
2938 if (length != other_length)
2939 return length > other_length;
2940 #ifdef REG_ALLOC_ORDER
2941 if (hard_regno >= 0 && other_hard_regno >= 0)
2942 return (inv_reg_alloc_order[hard_regno]
2943 < inv_reg_alloc_order[other_hard_regno]);
2945 if (call_used_count != other_call_used_count)
2946 return call_used_count > other_call_used_count;
2953 /* Allocate and initialize data necessary for assign_hard_reg. */
2955 ira_initiate_assign (void)
2958 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
2959 * ira_allocnos_num);
2960 consideration_allocno_bitmap = ira_allocate_bitmap ();
2961 initiate_cost_update ();
2962 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
2965 /* Deallocate data used by assign_hard_reg. */
2967 ira_finish_assign (void)
2969 ira_free (sorted_allocnos);
2970 ira_free_bitmap (consideration_allocno_bitmap);
2971 finish_cost_update ();
2972 ira_free (allocno_priorities);
2977 /* Entry function doing color-based register allocation. */
2981 allocno_stack_vec = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
2982 removed_splay_allocno_vec
2983 = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
2984 memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p));
2985 ira_initiate_assign ();
2987 ira_finish_assign ();
2988 VEC_free (ira_allocno_t, heap, removed_splay_allocno_vec);
2989 VEC_free (ira_allocno_t, heap, allocno_stack_vec);
2990 move_spill_restore ();
2995 /* This page contains a simple register allocator without usage of
2996 allocno conflicts. This is used for fast allocation for -O0. */
2998 /* Do register allocation by not using allocno conflicts. It uses
2999 only allocno live ranges. The algorithm is close to Chow's
3000 priority coloring. */
3002 ira_fast_allocation (void)
3004 int i, j, k, l, num, class_size, hard_regno;
3006 bool no_stack_reg_p;
3008 enum reg_class cover_class;
3009 enum machine_mode mode;
3011 ira_allocno_iterator ai;
3012 allocno_live_range_t r;
3013 HARD_REG_SET conflict_hard_regs, *used_hard_regs;
3015 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
3016 FOR_EACH_ALLOCNO (a, ai)
3018 l = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
3021 allocno_priorities[ALLOCNO_NUM (a)]
3022 = (((double) (floor_log2 (ALLOCNO_NREFS (a))
3023 * (ALLOCNO_MEMORY_COST (a)
3024 - ALLOCNO_COVER_CLASS_COST (a))) / l)
3025 * (10000 / REG_FREQ_MAX)
3026 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a)][ALLOCNO_MODE (a)]);
3028 used_hard_regs = (HARD_REG_SET *) ira_allocate (sizeof (HARD_REG_SET)
3030 for (i = 0; i < ira_max_point; i++)
3031 CLEAR_HARD_REG_SET (used_hard_regs[i]);
3032 sorted_allocnos = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
3033 * ira_allocnos_num);
3035 FOR_EACH_ALLOCNO (a, ai)
3036 sorted_allocnos[num++] = a;
3037 qsort (sorted_allocnos, ira_allocnos_num, sizeof (ira_allocno_t),
3038 allocno_priority_compare_func);
3039 for (i = 0; i < num; i++)
3041 a = sorted_allocnos[i];
3042 COPY_HARD_REG_SET (conflict_hard_regs, ALLOCNO_CONFLICT_HARD_REGS (a));
3043 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
3044 for (j = r->start; j <= r->finish; j++)
3045 IOR_HARD_REG_SET (conflict_hard_regs, used_hard_regs[j]);
3046 cover_class = ALLOCNO_COVER_CLASS (a);
3047 ALLOCNO_ASSIGNED_P (a) = true;
3048 ALLOCNO_HARD_REGNO (a) = -1;
3049 if (hard_reg_set_subset_p (reg_class_contents[cover_class],
3050 conflict_hard_regs))
3052 mode = ALLOCNO_MODE (a);
3054 no_stack_reg_p = ALLOCNO_NO_STACK_REG_P (a);
3056 class_size = ira_class_hard_regs_num[cover_class];
3057 for (j = 0; j < class_size; j++)
3059 hard_regno = ira_class_hard_regs[cover_class][j];
3061 if (no_stack_reg_p && FIRST_STACK_REG <= hard_regno
3062 && hard_regno <= LAST_STACK_REG)
3065 if (!ira_hard_reg_not_in_set_p (hard_regno, mode, conflict_hard_regs)
3066 || (TEST_HARD_REG_BIT
3067 (prohibited_class_mode_regs[cover_class][mode], hard_regno)))
3069 ALLOCNO_HARD_REGNO (a) = hard_regno;
3070 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
3071 for (k = r->start; k <= r->finish; k++)
3072 IOR_HARD_REG_SET (used_hard_regs[k],
3073 ira_reg_mode_hard_regset[hard_regno][mode]);
3077 ira_free (sorted_allocnos);
3078 ira_free (used_hard_regs);
3079 ira_free (allocno_priorities);
3080 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
3081 ira_print_disposition (ira_dump_file);