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_elems);
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_UPDATED_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_UPDATED_COVER_CLASS_COST (p1);
352 c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_UPDATED_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_UPDATED_COVER_CLASS_COST (a), i = 0;
434 costs[i] += a_costs[i];
435 full_costs[i] += a_costs[i];
440 full_costs[i] += cost;
442 /* Take preferences of conflicting allocnos into account. */
443 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
444 /* Reload can give another class so we need to check all
446 if (retry_p || bitmap_bit_p (consideration_allocno_bitmap,
447 ALLOCNO_NUM (conflict_allocno)))
449 ira_assert (cover_class == ALLOCNO_COVER_CLASS (conflict_allocno));
450 if (allocno_coalesced_p)
452 if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
453 ALLOCNO_NUM (conflict_allocno)))
455 bitmap_set_bit (processed_coalesced_allocno_bitmap,
456 ALLOCNO_NUM (conflict_allocno));
458 if (ALLOCNO_ASSIGNED_P (conflict_allocno))
460 if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno)) >= 0)
464 ira_reg_mode_hard_regset
465 [hard_regno][ALLOCNO_MODE (conflict_allocno)]);
466 if (hard_reg_set_subset_p (reg_class_contents[cover_class],
472 else if (! ALLOCNO_MAY_BE_SPILLED_P (conflict_allocno))
474 ira_allocate_and_copy_costs
475 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno),
477 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_allocno));
479 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno);
480 if (conflict_costs != NULL)
481 for (j = class_size - 1; j >= 0; j--)
482 full_costs[j] -= conflict_costs[j];
483 queue_update_cost (conflict_allocno, COST_HOP_DIVISOR);
489 /* Take into account preferences of allocnos connected by copies to
490 the conflict allocnos. */
491 update_conflict_hard_regno_costs (full_costs, true);
493 /* Take preferences of allocnos connected by copies into
495 start_update_cost ();
496 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
497 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
499 queue_update_cost (a, COST_HOP_DIVISOR);
503 update_conflict_hard_regno_costs (full_costs, false);
504 min_cost = min_full_cost = INT_MAX;
505 /* We don't care about giving callee saved registers to allocnos no
506 living through calls because call clobbered registers are
507 allocated first (it is usual practice to put them first in
509 for (i = 0; i < class_size; i++)
511 hard_regno = ira_class_hard_regs[cover_class][i];
514 && FIRST_STACK_REG <= hard_regno && hard_regno <= LAST_STACK_REG)
517 if (! ira_hard_reg_not_in_set_p (hard_regno, mode, conflicting_regs)
518 || TEST_HARD_REG_BIT (prohibited_class_mode_regs[cover_class][mode],
522 full_cost = full_costs[i];
523 if (! allocated_hardreg_p[hard_regno]
524 && ira_hard_reg_not_in_set_p (hard_regno, mode, call_used_reg_set))
525 /* We need to save/restore the hard register in
526 epilogue/prologue. Therefore we increase the cost. */
528 /* ??? If only part is call clobbered. */
529 rclass = REGNO_REG_CLASS (hard_regno);
530 add_cost = (ira_memory_move_cost[mode][rclass][0]
531 + ira_memory_move_cost[mode][rclass][1] - 1);
533 full_cost += add_cost;
537 if (min_full_cost > full_cost)
539 min_full_cost = full_cost;
540 best_hard_regno = hard_regno;
541 ira_assert (hard_regno >= 0);
544 if (min_full_cost > mem_cost)
546 if (! retry_p && internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
547 fprintf (ira_dump_file, "(memory is more profitable %d vs %d) ",
548 mem_cost, min_full_cost);
549 best_hard_regno = -1;
552 if (best_hard_regno < 0
553 && ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno) != allocno)
555 for (j = 0, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
556 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
558 sorted_allocnos[j++] = a;
562 qsort (sorted_allocnos, j, sizeof (ira_allocno_t),
563 allocno_cost_compare_func);
564 for (i = 0; i < j; i++)
566 a = sorted_allocnos[i];
567 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
568 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
569 VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, a);
570 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
572 fprintf (ira_dump_file, " Pushing");
573 print_coalesced_allocno (a);
574 fprintf (ira_dump_file, "\n");
579 if (best_hard_regno >= 0)
580 allocated_hardreg_p[best_hard_regno] = true;
581 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
582 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
584 ALLOCNO_HARD_REGNO (a) = best_hard_regno;
585 ALLOCNO_ASSIGNED_P (a) = true;
586 if (best_hard_regno >= 0)
587 update_copy_costs (a, true);
588 ira_assert (ALLOCNO_COVER_CLASS (a) == cover_class);
589 /* We don't need updated costs anymore: */
590 ira_free_allocno_updated_costs (a);
594 return best_hard_regno >= 0;
599 /* This page contains the allocator based on the Chaitin-Briggs algorithm. */
601 /* Bucket of allocnos that can colored currently without spilling. */
602 static ira_allocno_t colorable_allocno_bucket;
604 /* Bucket of allocnos that might be not colored currently without
606 static ira_allocno_t uncolorable_allocno_bucket;
608 /* Each element of the array contains the current number of allocnos
609 of given *cover* class in the uncolorable_bucket. */
610 static int uncolorable_allocnos_num[N_REG_CLASSES];
612 /* Add ALLOCNO to bucket *BUCKET_PTR. ALLOCNO should be not in a bucket
615 add_ira_allocno_to_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
617 ira_allocno_t first_allocno;
618 enum reg_class cover_class;
620 if (bucket_ptr == &uncolorable_allocno_bucket
621 && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
623 uncolorable_allocnos_num[cover_class]++;
624 ira_assert (uncolorable_allocnos_num[cover_class] > 0);
626 first_allocno = *bucket_ptr;
627 ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno) = first_allocno;
628 ALLOCNO_PREV_BUCKET_ALLOCNO (allocno) = NULL;
629 if (first_allocno != NULL)
630 ALLOCNO_PREV_BUCKET_ALLOCNO (first_allocno) = allocno;
631 *bucket_ptr = allocno;
634 /* The function returns frequency and number of available hard
635 registers for allocnos coalesced with ALLOCNO. */
637 get_coalesced_allocnos_attributes (ira_allocno_t allocno, int *freq, int *num)
643 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
644 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
646 *freq += ALLOCNO_FREQ (a);
647 *num += ALLOCNO_AVAILABLE_REGS_NUM (a);
653 /* Compare two allocnos to define which allocno should be pushed first
654 into the coloring stack. If the return is a negative number, the
655 allocno given by the first parameter will be pushed first. In this
656 case such allocno has less priority than the second one and the
657 hard register will be assigned to it after assignment to the second
658 one. As the result of such assignment order, the second allocno
659 has a better chance to get the best hard register. */
661 bucket_allocno_compare_func (const void *v1p, const void *v2p)
663 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
664 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
665 int diff, a1_freq, a2_freq, a1_num, a2_num;
667 if ((diff = (int) ALLOCNO_COVER_CLASS (a2) - ALLOCNO_COVER_CLASS (a1)) != 0)
669 get_coalesced_allocnos_attributes (a1, &a1_freq, &a1_num);
670 get_coalesced_allocnos_attributes (a2, &a2_freq, &a2_num);
671 if ((diff = a2_num - a1_num) != 0)
673 else if ((diff = a1_freq - a2_freq) != 0)
675 return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
678 /* Sort bucket *BUCKET_PTR and return the result through
681 sort_bucket (ira_allocno_t *bucket_ptr)
683 ira_allocno_t a, head;
686 for (n = 0, a = *bucket_ptr; a != NULL; a = ALLOCNO_NEXT_BUCKET_ALLOCNO (a))
687 sorted_allocnos[n++] = a;
690 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
691 bucket_allocno_compare_func);
693 for (n--; n >= 0; n--)
695 a = sorted_allocnos[n];
696 ALLOCNO_NEXT_BUCKET_ALLOCNO (a) = head;
697 ALLOCNO_PREV_BUCKET_ALLOCNO (a) = NULL;
699 ALLOCNO_PREV_BUCKET_ALLOCNO (head) = a;
705 /* Add ALLOCNO to bucket *BUCKET_PTR maintaining the order according
706 their priority. ALLOCNO should be not in a bucket before the
709 add_ira_allocno_to_ordered_bucket (ira_allocno_t allocno,
710 ira_allocno_t *bucket_ptr)
712 ira_allocno_t before, after;
713 enum reg_class cover_class;
715 if (bucket_ptr == &uncolorable_allocno_bucket
716 && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
718 uncolorable_allocnos_num[cover_class]++;
719 ira_assert (uncolorable_allocnos_num[cover_class] > 0);
721 for (before = *bucket_ptr, after = NULL;
723 after = before, before = ALLOCNO_NEXT_BUCKET_ALLOCNO (before))
724 if (bucket_allocno_compare_func (&allocno, &before) < 0)
726 ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno) = before;
727 ALLOCNO_PREV_BUCKET_ALLOCNO (allocno) = after;
729 *bucket_ptr = allocno;
731 ALLOCNO_NEXT_BUCKET_ALLOCNO (after) = allocno;
733 ALLOCNO_PREV_BUCKET_ALLOCNO (before) = allocno;
736 /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
739 delete_allocno_from_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
741 ira_allocno_t prev_allocno, next_allocno;
742 enum reg_class cover_class;
744 if (bucket_ptr == &uncolorable_allocno_bucket
745 && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
747 uncolorable_allocnos_num[cover_class]--;
748 ira_assert (uncolorable_allocnos_num[cover_class] >= 0);
750 prev_allocno = ALLOCNO_PREV_BUCKET_ALLOCNO (allocno);
751 next_allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno);
752 if (prev_allocno != NULL)
753 ALLOCNO_NEXT_BUCKET_ALLOCNO (prev_allocno) = next_allocno;
756 ira_assert (*bucket_ptr == allocno);
757 *bucket_ptr = next_allocno;
759 if (next_allocno != NULL)
760 ALLOCNO_PREV_BUCKET_ALLOCNO (next_allocno) = prev_allocno;
763 /* Splay tree for each cover class. The trees are indexed by the
764 corresponding cover classes. Splay trees contain uncolorable
766 static splay_tree uncolorable_allocnos_splay_tree[N_REG_CLASSES];
768 /* If the following macro is TRUE, splay tree is used to choose an
769 allocno of the corresponding cover class for spilling. When the
770 number uncolorable allocnos of given cover class decreases to some
771 threshold, linear array search is used to find the best allocno for
772 spilling. This threshold is actually pretty big because, although
773 splay trees asymptotically is much faster, each splay tree
774 operation is sufficiently costly especially taking cache locality
776 #define USE_SPLAY_P(CLASS) (uncolorable_allocnos_num[CLASS] > 4000)
778 /* Put ALLOCNO onto the coloring stack without removing it from its
779 bucket. Pushing allocno to the coloring stack can result in moving
780 conflicting allocnos from the uncolorable bucket to the colorable
783 push_ira_allocno_to_stack (ira_allocno_t allocno)
785 int conflicts_num, conflict_size, size;
786 ira_allocno_t a, conflict_allocno;
787 enum reg_class cover_class;
788 ira_allocno_conflict_iterator aci;
790 ALLOCNO_IN_GRAPH_P (allocno) = false;
791 VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, allocno);
792 cover_class = ALLOCNO_COVER_CLASS (allocno);
793 if (cover_class == NO_REGS)
795 size = ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)];
796 if (allocno_coalesced_p)
797 bitmap_clear (processed_coalesced_allocno_bitmap);
798 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
799 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
801 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
802 if (bitmap_bit_p (coloring_allocno_bitmap,
803 ALLOCNO_NUM (conflict_allocno)))
805 ira_assert (cover_class == ALLOCNO_COVER_CLASS (conflict_allocno));
806 if (allocno_coalesced_p)
808 if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
809 ALLOCNO_NUM (conflict_allocno)))
811 bitmap_set_bit (processed_coalesced_allocno_bitmap,
812 ALLOCNO_NUM (conflict_allocno));
814 if (ALLOCNO_IN_GRAPH_P (conflict_allocno)
815 && ! ALLOCNO_ASSIGNED_P (conflict_allocno))
817 conflicts_num = ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno);
819 = (ira_reg_class_nregs
820 [cover_class][ALLOCNO_MODE (conflict_allocno)]);
822 (ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) >= size);
823 if (conflicts_num + conflict_size
824 <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno))
826 ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) -= size;
830 = ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) - size;
831 if (uncolorable_allocnos_splay_tree[cover_class] != NULL
832 && !ALLOCNO_SPLAY_REMOVED_P (conflict_allocno)
833 && USE_SPLAY_P (cover_class))
837 (uncolorable_allocnos_splay_tree[cover_class],
838 (splay_tree_key) conflict_allocno) != NULL);
840 (uncolorable_allocnos_splay_tree[cover_class],
841 (splay_tree_key) conflict_allocno);
842 ALLOCNO_SPLAY_REMOVED_P (conflict_allocno) = true;
843 VEC_safe_push (ira_allocno_t, heap,
844 removed_splay_allocno_vec,
847 ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) = conflicts_num;
848 if (conflicts_num + conflict_size
849 <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno))
851 delete_allocno_from_bucket (conflict_allocno,
852 &uncolorable_allocno_bucket);
853 add_ira_allocno_to_ordered_bucket (conflict_allocno,
854 &colorable_allocno_bucket);
863 /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
864 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
866 remove_allocno_from_bucket_and_push (ira_allocno_t allocno, bool colorable_p)
868 enum reg_class cover_class;
871 delete_allocno_from_bucket (allocno, &colorable_allocno_bucket);
873 delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
874 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
876 fprintf (ira_dump_file, " Pushing");
877 print_coalesced_allocno (allocno);
878 fprintf (ira_dump_file, "%s\n", colorable_p ? "" : "(potential spill)");
880 cover_class = ALLOCNO_COVER_CLASS (allocno);
881 ira_assert ((colorable_p
882 && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
883 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)]
884 <= ALLOCNO_AVAILABLE_REGS_NUM (allocno)))
886 && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
887 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE
889 > ALLOCNO_AVAILABLE_REGS_NUM (allocno))));
891 ALLOCNO_MAY_BE_SPILLED_P (allocno) = true;
892 push_ira_allocno_to_stack (allocno);
895 /* Put all allocnos from colorable bucket onto the coloring stack. */
897 push_only_colorable (void)
899 sort_bucket (&colorable_allocno_bucket);
900 for (;colorable_allocno_bucket != NULL;)
901 remove_allocno_from_bucket_and_push (colorable_allocno_bucket, true);
904 /* Puts ALLOCNO chosen for potential spilling onto the coloring
907 push_ira_allocno_to_spill (ira_allocno_t allocno)
909 delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
910 ALLOCNO_MAY_BE_SPILLED_P (allocno) = true;
911 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
912 fprintf (ira_dump_file, " Pushing p%d(%d) (potential spill)\n",
913 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno));
914 push_ira_allocno_to_stack (allocno);
917 /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
918 loop given by its LOOP_NODE. */
920 ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p)
925 VEC (edge, heap) *edges;
927 ira_assert (loop_node->loop != NULL
928 && (regno < 0 || regno >= FIRST_PSEUDO_REGISTER));
932 FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
933 if (e->src != loop_node->loop->latch
935 || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
936 && bitmap_bit_p (DF_LR_IN (e->dest), regno))))
937 freq += EDGE_FREQUENCY (e);
941 edges = get_loop_exit_edges (loop_node->loop);
942 for (i = 0; VEC_iterate (edge, edges, i, e); i++)
944 || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
945 && bitmap_bit_p (DF_LR_IN (e->dest), regno)))
946 freq += EDGE_FREQUENCY (e);
947 VEC_free (edge, heap, edges);
950 return REG_FREQ_FROM_EDGE_FREQ (freq);
953 /* Calculate and return the cost of putting allocno A into memory. */
955 calculate_allocno_spill_cost (ira_allocno_t a)
958 enum machine_mode mode;
959 enum reg_class rclass;
960 ira_allocno_t parent_allocno;
961 ira_loop_tree_node_t parent_node, loop_node;
963 regno = ALLOCNO_REGNO (a);
964 cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_UPDATED_COVER_CLASS_COST (a);
965 if (ALLOCNO_CAP (a) != NULL)
967 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
968 if ((parent_node = loop_node->parent) == NULL)
970 if ((parent_allocno = parent_node->regno_allocno_map[regno]) == NULL)
972 mode = ALLOCNO_MODE (a);
973 rclass = ALLOCNO_COVER_CLASS (a);
974 if (ALLOCNO_HARD_REGNO (parent_allocno) < 0)
975 cost -= (ira_memory_move_cost[mode][rclass][0]
976 * ira_loop_edge_freq (loop_node, regno, true)
977 + ira_memory_move_cost[mode][rclass][1]
978 * ira_loop_edge_freq (loop_node, regno, false));
980 cost += ((ira_memory_move_cost[mode][rclass][1]
981 * ira_loop_edge_freq (loop_node, regno, true)
982 + ira_memory_move_cost[mode][rclass][0]
983 * ira_loop_edge_freq (loop_node, regno, false))
984 - (ira_register_move_cost[mode][rclass][rclass]
985 * (ira_loop_edge_freq (loop_node, regno, false)
986 + ira_loop_edge_freq (loop_node, regno, true))));
990 /* Compare keys in the splay tree used to choose best allocno for
991 spilling. The best allocno has the minimal key. */
993 allocno_spill_priority_compare (splay_tree_key k1, splay_tree_key k2)
995 int pri1, pri2, diff;
996 ira_allocno_t a1 = (ira_allocno_t) k1, a2 = (ira_allocno_t) k2;
998 pri1 = (ALLOCNO_TEMP (a1)
999 / (ALLOCNO_LEFT_CONFLICTS_NUM (a1)
1000 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a1)][ALLOCNO_MODE (a1)]
1002 pri2 = (ALLOCNO_TEMP (a2)
1003 / (ALLOCNO_LEFT_CONFLICTS_NUM (a2)
1004 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a2)][ALLOCNO_MODE (a2)]
1006 if ((diff = pri1 - pri2) != 0)
1008 if ((diff = ALLOCNO_TEMP (a1) - ALLOCNO_TEMP (a2)) != 0)
1010 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
1013 /* Allocate data of SIZE for the splay trees. We allocate only spay
1014 tree roots or splay tree nodes. If you change this, please rewrite
1017 splay_tree_allocate (int size, void *data ATTRIBUTE_UNUSED)
1019 if (size != sizeof (struct splay_tree_node_s))
1020 return ira_allocate (size);
1021 return pool_alloc (splay_tree_node_pool);
1024 /* Free data NODE for the splay trees. We allocate and free only spay
1025 tree roots or splay tree nodes. If you change this, please rewrite
1028 splay_tree_free (void *node, void *data ATTRIBUTE_UNUSED)
1031 enum reg_class cover_class;
1033 for (i = 0; i < ira_reg_class_cover_size; i++)
1035 cover_class = ira_reg_class_cover[i];
1036 if (node == uncolorable_allocnos_splay_tree[cover_class])
1042 pool_free (splay_tree_node_pool, node);
1045 /* Push allocnos to the coloring stack. The order of allocnos in the
1046 stack defines the order for the subsequent coloring. */
1048 push_allocnos_to_stack (void)
1050 ira_allocno_t allocno, a, i_allocno, *allocno_vec;
1051 enum reg_class cover_class, rclass;
1052 int allocno_pri, i_allocno_pri, allocno_cost, i_allocno_cost;
1053 int i, j, num, cover_class_allocnos_num[N_REG_CLASSES];
1054 ira_allocno_t *cover_class_allocnos[N_REG_CLASSES];
1058 VEC_truncate(ira_allocno_t, removed_splay_allocno_vec, 0);
1059 for (i = 0; i < ira_reg_class_cover_size; i++)
1061 cover_class = ira_reg_class_cover[i];
1062 cover_class_allocnos_num[cover_class] = 0;
1063 cover_class_allocnos[cover_class] = NULL;
1064 uncolorable_allocnos_splay_tree[cover_class] = NULL;
1066 /* Calculate uncolorable allocno spill costs. */
1067 for (allocno = uncolorable_allocno_bucket;
1069 allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno))
1070 if ((cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
1072 cover_class_allocnos_num[cover_class]++;
1074 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1075 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1077 cost += calculate_allocno_spill_cost (a);
1081 /* ??? Remove cost of copies between the coalesced
1083 ALLOCNO_TEMP (allocno) = cost;
1085 /* Define place where to put uncolorable allocnos of the same cover
1087 for (num = i = 0; i < ira_reg_class_cover_size; i++)
1089 cover_class = ira_reg_class_cover[i];
1090 ira_assert (cover_class_allocnos_num[cover_class]
1091 == uncolorable_allocnos_num[cover_class]);
1092 if (cover_class_allocnos_num[cover_class] != 0)
1094 cover_class_allocnos[cover_class] = allocnos_for_spilling + num;
1095 num += cover_class_allocnos_num[cover_class];
1096 cover_class_allocnos_num[cover_class] = 0;
1098 if (USE_SPLAY_P (cover_class))
1099 uncolorable_allocnos_splay_tree[cover_class]
1100 = splay_tree_new_with_allocator (allocno_spill_priority_compare,
1101 NULL, NULL, splay_tree_allocate,
1102 splay_tree_free, NULL);
1104 ira_assert (num <= ira_allocnos_num);
1105 /* Collect uncolorable allocnos of each cover class. */
1106 for (allocno = uncolorable_allocno_bucket;
1108 allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno))
1109 if ((cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
1111 cover_class_allocnos
1112 [cover_class][cover_class_allocnos_num[cover_class]++] = allocno;
1113 if (uncolorable_allocnos_splay_tree[cover_class] != NULL)
1114 splay_tree_insert (uncolorable_allocnos_splay_tree[cover_class],
1115 (splay_tree_key) allocno,
1116 (splay_tree_value) allocno);
1120 push_only_colorable ();
1121 allocno = uncolorable_allocno_bucket;
1122 if (allocno == NULL)
1124 cover_class = ALLOCNO_COVER_CLASS (allocno);
1125 if (cover_class == NO_REGS)
1127 push_ira_allocno_to_spill (allocno);
1130 /* Potential spilling. */
1132 (ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)] > 0);
1133 if (USE_SPLAY_P (cover_class))
1135 for (;VEC_length (ira_allocno_t, removed_splay_allocno_vec) != 0;)
1137 allocno = VEC_pop (ira_allocno_t, removed_splay_allocno_vec);
1138 ALLOCNO_SPLAY_REMOVED_P (allocno) = false;
1139 rclass = ALLOCNO_COVER_CLASS (allocno);
1140 if (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
1141 + ira_reg_class_nregs [rclass][ALLOCNO_MODE (allocno)]
1142 > ALLOCNO_AVAILABLE_REGS_NUM (allocno))
1144 (uncolorable_allocnos_splay_tree[rclass],
1145 (splay_tree_key) allocno, (splay_tree_value) allocno);
1147 allocno = ((ira_allocno_t)
1149 (uncolorable_allocnos_splay_tree[cover_class])->key);
1150 splay_tree_remove (uncolorable_allocnos_splay_tree[cover_class],
1151 (splay_tree_key) allocno);
1155 num = cover_class_allocnos_num[cover_class];
1156 ira_assert (num > 0);
1157 allocno_vec = cover_class_allocnos[cover_class];
1159 allocno_pri = allocno_cost = 0;
1160 /* Sort uncolorable allocno to find the one with the lowest
1162 for (i = 0, j = num - 1; i <= j;)
1164 i_allocno = allocno_vec[i];
1165 if (! ALLOCNO_IN_GRAPH_P (i_allocno)
1166 && ALLOCNO_IN_GRAPH_P (allocno_vec[j]))
1168 i_allocno = allocno_vec[j];
1169 allocno_vec[j] = allocno_vec[i];
1170 allocno_vec[i] = i_allocno;
1172 if (ALLOCNO_IN_GRAPH_P (i_allocno))
1175 if (ALLOCNO_TEMP (i_allocno) == INT_MAX)
1180 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (i_allocno);;
1181 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1183 cost += calculate_allocno_spill_cost (i_allocno);
1187 /* ??? Remove cost of copies between the coalesced
1189 ALLOCNO_TEMP (i_allocno) = cost;
1191 i_allocno_cost = ALLOCNO_TEMP (i_allocno);
1194 / (ALLOCNO_LEFT_CONFLICTS_NUM (i_allocno)
1195 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS
1197 [ALLOCNO_MODE (i_allocno)] + 1));
1198 if (allocno == NULL || allocno_pri > i_allocno_pri
1199 || (allocno_pri == i_allocno_pri
1200 && (allocno_cost > i_allocno_cost
1201 || (allocno_cost == i_allocno_cost
1202 && (ALLOCNO_NUM (allocno)
1203 > ALLOCNO_NUM (i_allocno))))))
1205 allocno = i_allocno;
1206 allocno_cost = i_allocno_cost;
1207 allocno_pri = i_allocno_pri;
1210 if (! ALLOCNO_IN_GRAPH_P (allocno_vec[j]))
1213 ira_assert (allocno != NULL && j >= 0);
1214 cover_class_allocnos_num[cover_class] = j + 1;
1216 ira_assert (ALLOCNO_IN_GRAPH_P (allocno)
1217 && ALLOCNO_COVER_CLASS (allocno) == cover_class
1218 && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
1219 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE
1221 > ALLOCNO_AVAILABLE_REGS_NUM (allocno)));
1222 remove_allocno_from_bucket_and_push (allocno, false);
1224 ira_assert (colorable_allocno_bucket == NULL
1225 && uncolorable_allocno_bucket == NULL);
1226 for (i = 0; i < ira_reg_class_cover_size; i++)
1228 cover_class = ira_reg_class_cover[i];
1229 ira_assert (uncolorable_allocnos_num[cover_class] == 0);
1230 if (uncolorable_allocnos_splay_tree[cover_class] != NULL)
1231 splay_tree_delete (uncolorable_allocnos_splay_tree[cover_class]);
1235 /* Pop the coloring stack and assign hard registers to the popped
1238 pop_allocnos_from_stack (void)
1240 ira_allocno_t allocno;
1241 enum reg_class cover_class;
1243 for (;VEC_length (ira_allocno_t, allocno_stack_vec) != 0;)
1245 allocno = VEC_pop (ira_allocno_t, allocno_stack_vec);
1246 cover_class = ALLOCNO_COVER_CLASS (allocno);
1247 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1249 fprintf (ira_dump_file, " Popping");
1250 print_coalesced_allocno (allocno);
1251 fprintf (ira_dump_file, " -- ");
1253 if (cover_class == NO_REGS)
1255 ALLOCNO_HARD_REGNO (allocno) = -1;
1256 ALLOCNO_ASSIGNED_P (allocno) = true;
1257 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno) == NULL);
1259 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno) == NULL);
1260 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1261 fprintf (ira_dump_file, "assign memory\n");
1263 else if (assign_hard_reg (allocno, false))
1265 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1266 fprintf (ira_dump_file, "assign reg %d\n",
1267 ALLOCNO_HARD_REGNO (allocno));
1269 else if (ALLOCNO_ASSIGNED_P (allocno))
1271 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1272 fprintf (ira_dump_file, "spill\n");
1274 ALLOCNO_IN_GRAPH_P (allocno) = true;
1278 /* Set up number of available hard registers for ALLOCNO. */
1280 setup_allocno_available_regs_num (ira_allocno_t allocno)
1282 int i, n, hard_regs_num;
1283 enum reg_class cover_class;
1285 HARD_REG_SET temp_set;
1287 cover_class = ALLOCNO_COVER_CLASS (allocno);
1288 ALLOCNO_AVAILABLE_REGS_NUM (allocno) = ira_available_class_regs[cover_class];
1289 if (cover_class == NO_REGS)
1291 CLEAR_HARD_REG_SET (temp_set);
1292 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) == allocno);
1293 hard_regs_num = ira_class_hard_regs_num[cover_class];
1294 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1295 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1297 IOR_HARD_REG_SET (temp_set, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1301 for (n = 0, i = hard_regs_num - 1; i >= 0; i--)
1302 if (TEST_HARD_REG_BIT (temp_set, ira_class_hard_regs[cover_class][i]))
1304 if (internal_flag_ira_verbose > 2 && n > 0 && ira_dump_file != NULL)
1305 fprintf (ira_dump_file, " Reg %d of %s has %d regs less\n",
1306 ALLOCNO_REGNO (allocno), reg_class_names[cover_class], n);
1307 ALLOCNO_AVAILABLE_REGS_NUM (allocno) -= n;
1310 /* Set up ALLOCNO_LEFT_CONFLICTS_NUM for ALLOCNO. */
1312 setup_allocno_left_conflicts_num (ira_allocno_t allocno)
1314 int i, hard_regs_num, hard_regno, conflict_allocnos_size;
1315 ira_allocno_t a, conflict_allocno;
1316 enum reg_class cover_class;
1317 HARD_REG_SET temp_set;
1318 ira_allocno_conflict_iterator aci;
1320 cover_class = ALLOCNO_COVER_CLASS (allocno);
1321 hard_regs_num = ira_class_hard_regs_num[cover_class];
1322 CLEAR_HARD_REG_SET (temp_set);
1323 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) == allocno);
1324 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1325 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1327 IOR_HARD_REG_SET (temp_set, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1331 AND_HARD_REG_SET (temp_set, reg_class_contents[cover_class]);
1332 AND_COMPL_HARD_REG_SET (temp_set, ira_no_alloc_regs);
1333 conflict_allocnos_size = 0;
1334 if (! hard_reg_set_empty_p (temp_set))
1335 for (i = 0; i < (int) hard_regs_num; i++)
1337 hard_regno = ira_class_hard_regs[cover_class][i];
1338 if (TEST_HARD_REG_BIT (temp_set, hard_regno))
1340 conflict_allocnos_size++;
1341 CLEAR_HARD_REG_BIT (temp_set, hard_regno);
1342 if (hard_reg_set_empty_p (temp_set))
1346 CLEAR_HARD_REG_SET (temp_set);
1347 if (allocno_coalesced_p)
1348 bitmap_clear (processed_coalesced_allocno_bitmap);
1349 if (cover_class != NO_REGS)
1350 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1351 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1353 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
1354 if (bitmap_bit_p (consideration_allocno_bitmap,
1355 ALLOCNO_NUM (conflict_allocno)))
1357 ira_assert (cover_class
1358 == ALLOCNO_COVER_CLASS (conflict_allocno));
1359 if (allocno_coalesced_p)
1361 if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
1362 ALLOCNO_NUM (conflict_allocno)))
1364 bitmap_set_bit (processed_coalesced_allocno_bitmap,
1365 ALLOCNO_NUM (conflict_allocno));
1367 if (! ALLOCNO_ASSIGNED_P (conflict_allocno))
1368 conflict_allocnos_size
1369 += (ira_reg_class_nregs
1370 [cover_class][ALLOCNO_MODE (conflict_allocno)]);
1371 else if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno))
1374 int last = (hard_regno
1376 [hard_regno][ALLOCNO_MODE (conflict_allocno)]);
1378 while (hard_regno < last)
1380 if (! TEST_HARD_REG_BIT (temp_set, hard_regno))
1382 conflict_allocnos_size++;
1383 SET_HARD_REG_BIT (temp_set, hard_regno);
1392 ALLOCNO_LEFT_CONFLICTS_NUM (allocno) = conflict_allocnos_size;
1395 /* Put ALLOCNO in a bucket corresponding to its number and size of its
1396 conflicting allocnos and hard registers. */
1398 put_allocno_into_bucket (ira_allocno_t allocno)
1401 enum reg_class cover_class;
1403 cover_class = ALLOCNO_COVER_CLASS (allocno);
1404 hard_regs_num = ira_class_hard_regs_num[cover_class];
1405 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
1407 ALLOCNO_IN_GRAPH_P (allocno) = true;
1408 setup_allocno_left_conflicts_num (allocno);
1409 setup_allocno_available_regs_num (allocno);
1410 if (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
1411 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)]
1412 <= ALLOCNO_AVAILABLE_REGS_NUM (allocno))
1413 add_ira_allocno_to_bucket (allocno, &colorable_allocno_bucket);
1415 add_ira_allocno_to_bucket (allocno, &uncolorable_allocno_bucket);
1418 /* The function is used to sort allocnos according to their execution
1421 copy_freq_compare_func (const void *v1p, const void *v2p)
1423 ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p;
1431 /* If freqencies are equal, sort by copies, so that the results of
1432 qsort leave nothing to chance. */
1433 return cp1->num - cp2->num;
1436 /* Merge two sets of coalesced allocnos given correspondingly by
1437 allocnos A1 and A2 (more accurately merging A2 set into A1
1440 merge_allocnos (ira_allocno_t a1, ira_allocno_t a2)
1442 ira_allocno_t a, first, last, next;
1444 first = ALLOCNO_FIRST_COALESCED_ALLOCNO (a1);
1445 if (first == ALLOCNO_FIRST_COALESCED_ALLOCNO (a2))
1447 for (last = a2, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
1448 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1450 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = first;
1455 next = ALLOCNO_NEXT_COALESCED_ALLOCNO (first);
1456 ALLOCNO_NEXT_COALESCED_ALLOCNO (first) = a2;
1457 ALLOCNO_NEXT_COALESCED_ALLOCNO (last) = next;
1460 /* Return TRUE if there are conflicting allocnos from two sets of
1461 coalesced allocnos given correspondingly by allocnos A1 and A2. If
1462 RELOAD_P is TRUE, we use live ranges to find conflicts because
1463 conflicts are represented only for allocnos of the same cover class
1464 and during the reload pass we coalesce allocnos for sharing stack
1467 coalesced_allocno_conflict_p (ira_allocno_t a1, ira_allocno_t a2,
1470 ira_allocno_t a, conflict_allocno;
1471 ira_allocno_conflict_iterator aci;
1473 if (allocno_coalesced_p)
1475 bitmap_clear (processed_coalesced_allocno_bitmap);
1476 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
1477 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1479 bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a));
1484 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
1485 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1489 for (conflict_allocno = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
1491 = ALLOCNO_NEXT_COALESCED_ALLOCNO (conflict_allocno))
1493 if (ira_allocno_live_ranges_intersect_p (a, conflict_allocno))
1495 if (conflict_allocno == a1)
1501 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
1502 if (conflict_allocno == a1
1503 || (allocno_coalesced_p
1504 && bitmap_bit_p (processed_coalesced_allocno_bitmap,
1505 ALLOCNO_NUM (conflict_allocno))))
1514 /* The major function for aggressive allocno coalescing. For the
1515 reload pass (RELOAD_P) we coalesce only spilled allocnos. If some
1516 allocnos have been coalesced, we set up flag
1517 allocno_coalesced_p. */
1519 coalesce_allocnos (bool reload_p)
1522 ira_copy_t cp, next_cp, *sorted_copies;
1523 enum reg_class cover_class;
1524 enum machine_mode mode;
1526 int i, n, cp_num, regno;
1529 sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num
1530 * sizeof (ira_copy_t));
1532 /* Collect copies. */
1533 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
1535 a = ira_allocnos[j];
1536 regno = ALLOCNO_REGNO (a);
1537 if ((! reload_p && ALLOCNO_ASSIGNED_P (a))
1539 && (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0
1540 || (regno < ira_reg_equiv_len
1541 && (ira_reg_equiv_const[regno] != NULL_RTX
1542 || ira_reg_equiv_invariant_p[regno])))))
1544 cover_class = ALLOCNO_COVER_CLASS (a);
1545 mode = ALLOCNO_MODE (a);
1546 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
1550 next_cp = cp->next_first_allocno_copy;
1551 regno = ALLOCNO_REGNO (cp->second);
1553 || (ALLOCNO_COVER_CLASS (cp->second) == cover_class
1554 && ALLOCNO_MODE (cp->second) == mode))
1556 && ((! reload_p && ! ALLOCNO_ASSIGNED_P (cp->second))
1558 && ALLOCNO_ASSIGNED_P (cp->second)
1559 && ALLOCNO_HARD_REGNO (cp->second) < 0
1560 && (regno >= ira_reg_equiv_len
1561 || (! ira_reg_equiv_invariant_p[regno]
1562 && ira_reg_equiv_const[regno] == NULL_RTX)))))
1563 sorted_copies[cp_num++] = cp;
1565 else if (cp->second == a)
1566 next_cp = cp->next_second_allocno_copy;
1571 qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
1572 /* Coalesced copies, most frequently executed first. */
1573 for (; cp_num != 0;)
1575 for (i = 0; i < cp_num; i++)
1577 cp = sorted_copies[i];
1578 if (! coalesced_allocno_conflict_p (cp->first, cp->second, reload_p))
1580 allocno_coalesced_p = true;
1581 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1584 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
1585 cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
1586 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
1588 merge_allocnos (cp->first, cp->second);
1593 /* Collect the rest of copies. */
1594 for (n = 0; i < cp_num; i++)
1596 cp = sorted_copies[i];
1597 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->first)
1598 != ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->second))
1599 sorted_copies[n++] = cp;
1603 ira_free (sorted_copies);
1606 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
1607 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
1609 color_allocnos (void)
1615 allocno_coalesced_p = false;
1616 processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
1617 if (flag_ira_coalesce)
1618 coalesce_allocnos (false);
1619 /* Put the allocnos into the corresponding buckets. */
1620 colorable_allocno_bucket = NULL;
1621 uncolorable_allocno_bucket = NULL;
1622 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1624 a = ira_allocnos[i];
1625 if (ALLOCNO_COVER_CLASS (a) == NO_REGS)
1627 ALLOCNO_HARD_REGNO (a) = -1;
1628 ALLOCNO_ASSIGNED_P (a) = true;
1629 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
1630 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
1631 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1633 fprintf (ira_dump_file, " Spill");
1634 print_coalesced_allocno (a);
1635 fprintf (ira_dump_file, "\n");
1639 put_allocno_into_bucket (a);
1641 push_allocnos_to_stack ();
1642 pop_allocnos_from_stack ();
1643 if (flag_ira_coalesce)
1644 /* We don't need coalesced allocnos for ira_reassign_pseudos. */
1645 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1647 a = ira_allocnos[i];
1648 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
1649 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
1651 ira_free_bitmap (processed_coalesced_allocno_bitmap);
1652 allocno_coalesced_p = false;
1657 /* Output information about the loop given by its LOOP_TREE_NODE. */
1659 print_loop_title (ira_loop_tree_node_t loop_tree_node)
1664 ira_assert (loop_tree_node->loop != NULL);
1665 fprintf (ira_dump_file,
1666 "\n Loop %d (parent %d, header bb%d, depth %d)\n all:",
1667 loop_tree_node->loop->num,
1668 (loop_tree_node->parent == NULL
1669 ? -1 : loop_tree_node->parent->loop->num),
1670 loop_tree_node->loop->header->index,
1671 loop_depth (loop_tree_node->loop));
1672 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
1673 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
1674 fprintf (ira_dump_file, "\n modified regnos:");
1675 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->modified_regnos, 0, j, bi)
1676 fprintf (ira_dump_file, " %d", j);
1677 fprintf (ira_dump_file, "\n border:");
1678 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->border_allocnos, 0, j, bi)
1679 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
1680 fprintf (ira_dump_file, "\n Pressure:");
1681 for (j = 0; (int) j < ira_reg_class_cover_size; j++)
1683 enum reg_class cover_class;
1685 cover_class = ira_reg_class_cover[j];
1686 if (loop_tree_node->reg_pressure[cover_class] == 0)
1688 fprintf (ira_dump_file, " %s=%d", reg_class_names[cover_class],
1689 loop_tree_node->reg_pressure[cover_class]);
1691 fprintf (ira_dump_file, "\n");
1694 /* Color the allocnos inside loop (in the extreme case it can be all
1695 of the function) given the corresponding LOOP_TREE_NODE. The
1696 function is called for each loop during top-down traverse of the
1699 color_pass (ira_loop_tree_node_t loop_tree_node)
1701 int regno, hard_regno, index = -1;
1702 int cost, exit_freq, enter_freq;
1705 enum machine_mode mode;
1706 enum reg_class rclass, cover_class;
1707 ira_allocno_t a, subloop_allocno;
1708 ira_loop_tree_node_t subloop_node;
1710 ira_assert (loop_tree_node->bb == NULL);
1711 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1712 print_loop_title (loop_tree_node);
1714 bitmap_copy (coloring_allocno_bitmap, loop_tree_node->all_allocnos);
1715 bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap);
1716 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
1718 a = ira_allocnos[j];
1719 if (! ALLOCNO_ASSIGNED_P (a))
1721 bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a));
1723 /* Color all mentioned allocnos including transparent ones. */
1725 /* Process caps. They are processed just once. */
1726 if (flag_ira_algorithm == IRA_ALGORITHM_MIXED
1727 || flag_ira_algorithm == IRA_ALGORITHM_REGIONAL)
1728 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
1730 a = ira_allocnos[j];
1731 if (ALLOCNO_CAP_MEMBER (a) == NULL)
1733 /* Remove from processing in the next loop. */
1734 bitmap_clear_bit (consideration_allocno_bitmap, j);
1735 rclass = ALLOCNO_COVER_CLASS (a);
1736 if ((flag_ira_algorithm == IRA_ALGORITHM_MIXED
1737 && loop_tree_node->reg_pressure[rclass]
1738 <= ira_available_class_regs[rclass]))
1740 mode = ALLOCNO_MODE (a);
1741 hard_regno = ALLOCNO_HARD_REGNO (a);
1742 if (hard_regno >= 0)
1744 index = ira_class_hard_reg_index[rclass][hard_regno];
1745 ira_assert (index >= 0);
1747 regno = ALLOCNO_REGNO (a);
1748 subloop_allocno = ALLOCNO_CAP_MEMBER (a);
1749 subloop_node = ALLOCNO_LOOP_TREE_NODE (subloop_allocno);
1750 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno));
1751 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
1752 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
1753 if (hard_regno >= 0)
1754 update_copy_costs (subloop_allocno, true);
1755 /* We don't need updated costs anymore: */
1756 ira_free_allocno_updated_costs (subloop_allocno);
1759 /* Update costs of the corresponding allocnos (not caps) in the
1761 for (subloop_node = loop_tree_node->subloops;
1762 subloop_node != NULL;
1763 subloop_node = subloop_node->subloop_next)
1765 ira_assert (subloop_node->bb == NULL);
1766 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
1768 a = ira_allocnos[j];
1769 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
1770 mode = ALLOCNO_MODE (a);
1771 rclass = ALLOCNO_COVER_CLASS (a);
1772 hard_regno = ALLOCNO_HARD_REGNO (a);
1773 if (hard_regno >= 0)
1775 index = ira_class_hard_reg_index[rclass][hard_regno];
1776 ira_assert (index >= 0);
1778 regno = ALLOCNO_REGNO (a);
1779 /* ??? conflict costs */
1780 subloop_allocno = subloop_node->regno_allocno_map[regno];
1781 if (subloop_allocno == NULL
1782 || ALLOCNO_CAP (subloop_allocno) != NULL)
1784 ira_assert (bitmap_bit_p (subloop_node->all_allocnos,
1785 ALLOCNO_NUM (subloop_allocno)));
1786 if (flag_ira_algorithm == IRA_ALGORITHM_MIXED
1787 && (loop_tree_node->reg_pressure[rclass]
1788 <= ira_available_class_regs[rclass]))
1790 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
1792 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
1793 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
1794 if (hard_regno >= 0)
1795 update_copy_costs (subloop_allocno, true);
1796 /* We don't need updated costs anymore: */
1797 ira_free_allocno_updated_costs (subloop_allocno);
1801 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
1802 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
1803 ira_assert (regno < ira_reg_equiv_len);
1804 if (ira_reg_equiv_invariant_p[regno]
1805 || ira_reg_equiv_const[regno] != NULL_RTX)
1807 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
1809 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
1810 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
1811 if (hard_regno >= 0)
1812 update_copy_costs (subloop_allocno, true);
1813 /* We don't need updated costs anymore: */
1814 ira_free_allocno_updated_costs (subloop_allocno);
1817 else if (hard_regno < 0)
1819 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
1820 -= ((ira_memory_move_cost[mode][rclass][1] * enter_freq)
1821 + (ira_memory_move_cost[mode][rclass][0] * exit_freq));
1825 cover_class = ALLOCNO_COVER_CLASS (subloop_allocno);
1826 cost = (ira_register_move_cost[mode][rclass][rclass]
1827 * (exit_freq + enter_freq));
1828 ira_allocate_and_set_or_copy_costs
1829 (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno), cover_class,
1830 ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno),
1831 ALLOCNO_HARD_REG_COSTS (subloop_allocno));
1832 ira_allocate_and_set_or_copy_costs
1833 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno),
1835 ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno));
1836 ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
1837 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
1839 if (ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno)
1840 > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index])
1841 ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno)
1842 = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index];
1843 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
1844 += (ira_memory_move_cost[mode][rclass][0] * enter_freq
1845 + ira_memory_move_cost[mode][rclass][1] * exit_freq);
1851 /* Initialize the common data for coloring and calls functions to do
1852 Chaitin-Briggs and regional coloring. */
1856 coloring_allocno_bitmap = ira_allocate_bitmap ();
1857 allocnos_for_spilling
1858 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
1859 * ira_allocnos_num);
1860 splay_tree_node_pool = create_alloc_pool ("splay tree nodes",
1861 sizeof (struct splay_tree_node_s),
1863 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
1864 fprintf (ira_dump_file, "\n**** Allocnos coloring:\n\n");
1866 ira_traverse_loop_tree (false, ira_loop_tree_root, color_pass, NULL);
1868 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1869 ira_print_disposition (ira_dump_file);
1871 free_alloc_pool (splay_tree_node_pool);
1872 ira_free_bitmap (coloring_allocno_bitmap);
1873 ira_free (allocnos_for_spilling);
1878 /* Move spill/restore code, which are to be generated in ira-emit.c,
1879 to less frequent points (if it is profitable) by reassigning some
1880 allocnos (in loop with subloops containing in another loop) to
1881 memory which results in longer live-range where the corresponding
1882 pseudo-registers will be in memory. */
1884 move_spill_restore (void)
1886 int cost, regno, hard_regno, hard_regno2, index;
1888 int enter_freq, exit_freq;
1889 enum machine_mode mode;
1890 enum reg_class rclass;
1891 ira_allocno_t a, parent_allocno, subloop_allocno;
1892 ira_loop_tree_node_t parent, loop_node, subloop_node;
1893 ira_allocno_iterator ai;
1898 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
1899 fprintf (ira_dump_file, "New iteration of spill/restore move\n");
1900 FOR_EACH_ALLOCNO (a, ai)
1902 regno = ALLOCNO_REGNO (a);
1903 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
1904 if (ALLOCNO_CAP_MEMBER (a) != NULL
1905 || ALLOCNO_CAP (a) != NULL
1906 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0
1907 || loop_node->children == NULL
1908 /* don't do the optimization because it can create
1909 copies and the reload pass can spill the allocno set
1910 by copy although the allocno will not get memory
1912 || ira_reg_equiv_invariant_p[regno]
1913 || ira_reg_equiv_const[regno] != NULL_RTX
1914 || !bitmap_bit_p (loop_node->border_allocnos, ALLOCNO_NUM (a)))
1916 mode = ALLOCNO_MODE (a);
1917 rclass = ALLOCNO_COVER_CLASS (a);
1918 index = ira_class_hard_reg_index[rclass][hard_regno];
1919 ira_assert (index >= 0);
1920 cost = (ALLOCNO_MEMORY_COST (a)
1921 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
1922 ? ALLOCNO_COVER_CLASS_COST (a)
1923 : ALLOCNO_HARD_REG_COSTS (a)[index]));
1924 for (subloop_node = loop_node->subloops;
1925 subloop_node != NULL;
1926 subloop_node = subloop_node->subloop_next)
1928 ira_assert (subloop_node->bb == NULL);
1929 subloop_allocno = subloop_node->regno_allocno_map[regno];
1930 if (subloop_allocno == NULL)
1932 /* We have accumulated cost. To get the real cost of
1933 allocno usage in the loop we should subtract costs of
1934 the subloop allocnos. */
1935 cost -= (ALLOCNO_MEMORY_COST (subloop_allocno)
1936 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno) == NULL
1937 ? ALLOCNO_COVER_CLASS_COST (subloop_allocno)
1938 : ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index]));
1939 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
1940 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
1941 if ((hard_regno2 = ALLOCNO_HARD_REGNO (subloop_allocno)) < 0)
1942 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
1943 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
1947 += (ira_memory_move_cost[mode][rclass][0] * exit_freq
1948 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
1949 if (hard_regno2 != hard_regno)
1950 cost -= (ira_register_move_cost[mode][rclass][rclass]
1951 * (exit_freq + enter_freq));
1954 if ((parent = loop_node->parent) != NULL
1955 && (parent_allocno = parent->regno_allocno_map[regno]) != NULL)
1957 exit_freq = ira_loop_edge_freq (loop_node, regno, true);
1958 enter_freq = ira_loop_edge_freq (loop_node, regno, false);
1959 if ((hard_regno2 = ALLOCNO_HARD_REGNO (parent_allocno)) < 0)
1960 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
1961 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
1965 += (ira_memory_move_cost[mode][rclass][1] * exit_freq
1966 + ira_memory_move_cost[mode][rclass][0] * enter_freq);
1967 if (hard_regno2 != hard_regno)
1968 cost -= (ira_register_move_cost[mode][rclass][rclass]
1969 * (exit_freq + enter_freq));
1974 ALLOCNO_HARD_REGNO (a) = -1;
1975 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1979 " Moving spill/restore for a%dr%d up from loop %d",
1980 ALLOCNO_NUM (a), regno, loop_node->loop->num);
1981 fprintf (ira_dump_file, " - profit %d\n", -cost);
1993 /* Update current hard reg costs and current conflict hard reg costs
1994 for allocno A. It is done by processing its copies containing
1995 other allocnos already assigned. */
1997 update_curr_costs (ira_allocno_t a)
1999 int i, hard_regno, cost;
2000 enum machine_mode mode;
2001 enum reg_class cover_class, rclass;
2002 ira_allocno_t another_a;
2003 ira_copy_t cp, next_cp;
2005 ira_assert (! ALLOCNO_ASSIGNED_P (a));
2006 cover_class = ALLOCNO_COVER_CLASS (a);
2007 if (cover_class == NO_REGS)
2009 mode = ALLOCNO_MODE (a);
2010 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2014 next_cp = cp->next_first_allocno_copy;
2015 another_a = cp->second;
2017 else if (cp->second == a)
2019 next_cp = cp->next_second_allocno_copy;
2020 another_a = cp->first;
2024 if (cover_class != ALLOCNO_COVER_CLASS (another_a)
2025 || ! ALLOCNO_ASSIGNED_P (another_a)
2026 || (hard_regno = ALLOCNO_HARD_REGNO (another_a)) < 0)
2028 rclass = REGNO_REG_CLASS (hard_regno);
2029 i = ira_class_hard_reg_index[cover_class][hard_regno];
2030 ira_assert (i >= 0);
2031 cost = (cp->first == a
2032 ? ira_register_move_cost[mode][rclass][cover_class]
2033 : ira_register_move_cost[mode][cover_class][rclass]);
2034 ira_allocate_and_set_or_copy_costs
2035 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
2036 cover_class, ALLOCNO_COVER_CLASS_COST (a),
2037 ALLOCNO_HARD_REG_COSTS (a));
2038 ira_allocate_and_set_or_copy_costs
2039 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
2040 cover_class, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
2041 ALLOCNO_UPDATED_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
2042 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
2046 /* Map: allocno number -> allocno priority. */
2047 static int *allocno_priorities;
2049 /* Set up priorities for N allocnos in array
2050 CONSIDERATION_ALLOCNOS. */
2052 setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
2054 int i, length, nrefs, priority, max_priority, mult;
2058 for (i = 0; i < n; i++)
2060 a = consideration_allocnos[i];
2061 nrefs = ALLOCNO_NREFS (a);
2062 ira_assert (nrefs >= 0);
2063 mult = floor_log2 (ALLOCNO_NREFS (a)) + 1;
2064 ira_assert (mult >= 0);
2065 allocno_priorities[ALLOCNO_NUM (a)]
2068 * (ALLOCNO_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a))
2069 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a)][ALLOCNO_MODE (a)]);
2071 priority = -priority;
2072 if (max_priority < priority)
2073 max_priority = priority;
2075 mult = max_priority == 0 ? 1 : INT_MAX / max_priority;
2076 for (i = 0; i < n; i++)
2078 a = consideration_allocnos[i];
2079 length = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2082 allocno_priorities[ALLOCNO_NUM (a)]
2083 = allocno_priorities[ALLOCNO_NUM (a)] * mult / length;
2087 /* Sort allocnos according to their priorities which are calculated
2088 analogous to ones in file `global.c'. */
2090 allocno_priority_compare_func (const void *v1p, const void *v2p)
2092 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2093 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2096 pri1 = allocno_priorities[ALLOCNO_NUM (a1)];
2097 pri2 = allocno_priorities[ALLOCNO_NUM (a2)];
2101 /* If regs are equally good, sort by allocnos, so that the results of
2102 qsort leave nothing to chance. */
2103 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2106 /* Try to assign hard registers to the unassigned allocnos and
2107 allocnos conflicting with them or conflicting with allocnos whose
2108 regno >= START_REGNO. The function is called after ira_flattening,
2109 so more allocnos (including ones created in ira-emit.c) will have a
2110 chance to get a hard register. We use simple assignment algorithm
2111 based on priorities. */
2113 ira_reassign_conflict_allocnos (int start_regno)
2115 int i, allocnos_to_color_num;
2116 ira_allocno_t a, conflict_a;
2117 ira_allocno_conflict_iterator aci;
2118 enum reg_class cover_class;
2119 bitmap allocnos_to_color;
2120 ira_allocno_iterator ai;
2122 allocnos_to_color = ira_allocate_bitmap ();
2123 allocnos_to_color_num = 0;
2124 FOR_EACH_ALLOCNO (a, ai)
2126 if (! ALLOCNO_ASSIGNED_P (a)
2127 && ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a)))
2129 if (ALLOCNO_COVER_CLASS (a) != NO_REGS)
2130 sorted_allocnos[allocnos_to_color_num++] = a;
2133 ALLOCNO_ASSIGNED_P (a) = true;
2134 ALLOCNO_HARD_REGNO (a) = -1;
2135 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2136 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2138 bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (a));
2140 if (ALLOCNO_REGNO (a) < start_regno
2141 || (cover_class = ALLOCNO_COVER_CLASS (a)) == NO_REGS)
2143 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
2145 ira_assert (cover_class == ALLOCNO_COVER_CLASS (conflict_a));
2146 if (bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (conflict_a)))
2148 bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a));
2149 sorted_allocnos[allocnos_to_color_num++] = conflict_a;
2152 ira_free_bitmap (allocnos_to_color);
2153 if (allocnos_to_color_num > 1)
2155 setup_allocno_priorities (sorted_allocnos, allocnos_to_color_num);
2156 qsort (sorted_allocnos, allocnos_to_color_num, sizeof (ira_allocno_t),
2157 allocno_priority_compare_func);
2159 for (i = 0; i < allocnos_to_color_num; i++)
2161 a = sorted_allocnos[i];
2162 ALLOCNO_ASSIGNED_P (a) = false;
2163 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2164 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2165 update_curr_costs (a);
2167 for (i = 0; i < allocnos_to_color_num; i++)
2169 a = sorted_allocnos[i];
2170 if (assign_hard_reg (a, true))
2172 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2175 " Secondary allocation: assign hard reg %d to reg %d\n",
2176 ALLOCNO_HARD_REGNO (a), ALLOCNO_REGNO (a));
2183 /* This page contains code to coalesce memory stack slots used by
2184 spilled allocnos. This results in smaller stack frame, better data
2185 locality, and in smaller code for some architectures like
2186 x86/x86_64 where insn size depends on address displacement value.
2187 On the other hand, it can worsen insn scheduling after the RA but
2188 in practice it is less important than smaller stack frames. */
2190 /* Usage cost and order number of coalesced allocno set to which
2191 given pseudo register belongs to. */
2192 static int *regno_coalesced_allocno_cost;
2193 static int *regno_coalesced_allocno_num;
2195 /* Sort pseudos according frequencies of coalesced allocno sets they
2196 belong to (putting most frequently ones first), and according to
2197 coalesced allocno set order numbers. */
2199 coalesced_pseudo_reg_freq_compare (const void *v1p, const void *v2p)
2201 const int regno1 = *(const int *) v1p;
2202 const int regno2 = *(const int *) v2p;
2205 if ((diff = (regno_coalesced_allocno_cost[regno2]
2206 - regno_coalesced_allocno_cost[regno1])) != 0)
2208 if ((diff = (regno_coalesced_allocno_num[regno1]
2209 - regno_coalesced_allocno_num[regno2])) != 0)
2211 return regno1 - regno2;
2214 /* Widest width in which each pseudo reg is referred to (via subreg).
2215 It is used for sorting pseudo registers. */
2216 static unsigned int *regno_max_ref_width;
2218 /* Redefine STACK_GROWS_DOWNWARD in terms of 0 or 1. */
2219 #ifdef STACK_GROWS_DOWNWARD
2220 # undef STACK_GROWS_DOWNWARD
2221 # define STACK_GROWS_DOWNWARD 1
2223 # define STACK_GROWS_DOWNWARD 0
2226 /* Sort pseudos according their slot numbers (putting ones with
2227 smaller numbers first, or last when the frame pointer is not
2230 coalesced_pseudo_reg_slot_compare (const void *v1p, const void *v2p)
2232 const int regno1 = *(const int *) v1p;
2233 const int regno2 = *(const int *) v2p;
2234 ira_allocno_t a1 = ira_regno_allocno_map[regno1];
2235 ira_allocno_t a2 = ira_regno_allocno_map[regno2];
2236 int diff, slot_num1, slot_num2;
2237 int total_size1, total_size2;
2239 if (a1 == NULL || ALLOCNO_HARD_REGNO (a1) >= 0)
2241 if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
2242 return regno1 - regno2;
2245 else if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
2247 slot_num1 = -ALLOCNO_HARD_REGNO (a1);
2248 slot_num2 = -ALLOCNO_HARD_REGNO (a2);
2249 if ((diff = slot_num1 - slot_num2) != 0)
2250 return (frame_pointer_needed
2251 || !FRAME_GROWS_DOWNWARD == STACK_GROWS_DOWNWARD ? diff : -diff);
2252 total_size1 = MAX (PSEUDO_REGNO_BYTES (regno1), regno_max_ref_width[regno1]);
2253 total_size2 = MAX (PSEUDO_REGNO_BYTES (regno2), regno_max_ref_width[regno2]);
2254 if ((diff = total_size2 - total_size1) != 0)
2256 return regno1 - regno2;
2259 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
2260 for coalesced allocno sets containing allocnos with their regnos
2261 given in array PSEUDO_REGNOS of length N. */
2263 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos, int n)
2265 int i, num, regno, cost;
2266 ira_allocno_t allocno, a;
2268 for (num = i = 0; i < n; i++)
2270 regno = pseudo_regnos[i];
2271 allocno = ira_regno_allocno_map[regno];
2272 if (allocno == NULL)
2274 regno_coalesced_allocno_cost[regno] = 0;
2275 regno_coalesced_allocno_num[regno] = ++num;
2278 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
2281 for (cost = 0, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2282 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2284 cost += ALLOCNO_FREQ (a);
2288 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2289 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2291 regno_coalesced_allocno_num[ALLOCNO_REGNO (a)] = num;
2292 regno_coalesced_allocno_cost[ALLOCNO_REGNO (a)] = cost;
2299 /* Collect spilled allocnos representing coalesced allocno sets (the
2300 first coalesced allocno). The collected allocnos are returned
2301 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
2302 number of the collected allocnos. The allocnos are given by their
2303 regnos in array PSEUDO_REGNOS of length N. */
2305 collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n,
2306 ira_allocno_t *spilled_coalesced_allocnos)
2309 ira_allocno_t allocno;
2311 for (num = i = 0; i < n; i++)
2313 regno = pseudo_regnos[i];
2314 allocno = ira_regno_allocno_map[regno];
2315 if (allocno == NULL || ALLOCNO_HARD_REGNO (allocno) >= 0
2316 || ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
2318 spilled_coalesced_allocnos[num++] = allocno;
2323 /* Array of bitmaps of size IRA_MAX_POINT. Bitmap for given point
2324 contains numbers of coalesced allocnos living at this point. */
2325 static regset_head *coalesced_allocnos_living_at_program_points;
2327 /* Return TRUE if coalesced allocnos represented by ALLOCNO live at
2328 program points of coalesced allocnos with number N. */
2330 coalesced_allocnos_live_at_points_p (ira_allocno_t allocno, int n)
2334 allocno_live_range_t r;
2336 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2337 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2339 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
2340 for (i = r->start; i <= r->finish; i++)
2341 if (bitmap_bit_p (&coalesced_allocnos_living_at_program_points[i], n))
2349 /* Mark program points where coalesced allocnos represented by ALLOCNO
2352 set_coalesced_allocnos_live_points (ira_allocno_t allocno)
2356 allocno_live_range_t r;
2358 n = ALLOCNO_TEMP (allocno);
2359 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2360 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2362 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
2363 for (i = r->start; i <= r->finish; i++)
2364 bitmap_set_bit (&coalesced_allocnos_living_at_program_points[i], n);
2370 /* We have coalesced allocnos involving in copies. Coalesce allocnos
2371 further in order to share the same memory stack slot. Allocnos
2372 representing sets of allocnos coalesced before the call are given
2373 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
2374 some allocnos were coalesced in the function. */
2376 coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num)
2378 int i, j, last_coalesced_allocno_num;
2379 ira_allocno_t allocno, a;
2380 bool merged_p = false;
2382 coalesced_allocnos_living_at_program_points
2383 = (regset_head *) ira_allocate (sizeof (regset_head) * ira_max_point);
2384 for (i = 0; i < ira_max_point; i++)
2385 INIT_REG_SET (&coalesced_allocnos_living_at_program_points[i]);
2386 last_coalesced_allocno_num = 0;
2387 /* Coalesce non-conflicting spilled allocnos preferring most
2389 for (i = 0; i < num; i++)
2391 allocno = spilled_coalesced_allocnos[i];
2392 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno
2393 || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
2394 && (ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)]
2395 || ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX)))
2397 for (j = 0; j < i; j++)
2399 a = spilled_coalesced_allocnos[j];
2400 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a
2401 && (ALLOCNO_REGNO (a) >= ira_reg_equiv_len
2402 || (! ira_reg_equiv_invariant_p[ALLOCNO_REGNO (a)]
2403 && ira_reg_equiv_const[ALLOCNO_REGNO (a)] == NULL_RTX))
2404 && ! coalesced_allocnos_live_at_points_p (allocno,
2410 /* No coalescing: set up number for coalesced allocnos
2411 represented by ALLOCNO. */
2412 ALLOCNO_TEMP (allocno) = last_coalesced_allocno_num++;
2413 set_coalesced_allocnos_live_points (allocno);
2417 allocno_coalesced_p = true;
2419 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2420 fprintf (ira_dump_file,
2421 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
2422 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno),
2423 ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2424 ALLOCNO_TEMP (allocno) = ALLOCNO_TEMP (a);
2425 set_coalesced_allocnos_live_points (allocno);
2426 merge_allocnos (a, allocno);
2427 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a);
2430 for (i = 0; i < ira_max_point; i++)
2431 CLEAR_REG_SET (&coalesced_allocnos_living_at_program_points[i]);
2432 ira_free (coalesced_allocnos_living_at_program_points);
2436 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
2437 subsequent assigning stack slots to them in the reload pass. To do
2438 this we coalesce spilled allocnos first to decrease the number of
2439 memory-memory move insns. This function is called by the
2442 ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n,
2443 unsigned int *reg_max_ref_width)
2445 int max_regno = max_reg_num ();
2446 int i, regno, num, slot_num;
2447 ira_allocno_t allocno, a;
2448 ira_allocno_iterator ai;
2449 ira_allocno_t *spilled_coalesced_allocnos;
2451 processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
2452 /* Set up allocnos can be coalesced. */
2453 coloring_allocno_bitmap = ira_allocate_bitmap ();
2454 for (i = 0; i < n; i++)
2456 regno = pseudo_regnos[i];
2457 allocno = ira_regno_allocno_map[regno];
2458 if (allocno != NULL)
2459 bitmap_set_bit (coloring_allocno_bitmap,
2460 ALLOCNO_NUM (allocno));
2462 allocno_coalesced_p = false;
2463 coalesce_allocnos (true);
2464 ira_free_bitmap (coloring_allocno_bitmap);
2465 regno_coalesced_allocno_cost
2466 = (int *) ira_allocate (max_regno * sizeof (int));
2467 regno_coalesced_allocno_num
2468 = (int *) ira_allocate (max_regno * sizeof (int));
2469 memset (regno_coalesced_allocno_num, 0, max_regno * sizeof (int));
2470 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
2471 /* Sort regnos according frequencies of the corresponding coalesced
2473 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_freq_compare);
2474 spilled_coalesced_allocnos
2475 = (ira_allocno_t *) ira_allocate (ira_allocnos_num
2476 * sizeof (ira_allocno_t));
2477 /* Collect allocnos representing the spilled coalesced allocno
2479 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
2480 spilled_coalesced_allocnos);
2481 if (flag_ira_share_spill_slots
2482 && coalesce_spill_slots (spilled_coalesced_allocnos, num))
2484 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
2485 qsort (pseudo_regnos, n, sizeof (int),
2486 coalesced_pseudo_reg_freq_compare);
2487 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
2488 spilled_coalesced_allocnos);
2490 ira_free_bitmap (processed_coalesced_allocno_bitmap);
2491 allocno_coalesced_p = false;
2492 /* Assign stack slot numbers to spilled allocno sets, use smaller
2493 numbers for most frequently used coalesced allocnos. -1 is
2494 reserved for dynamic search of stack slots for pseudos spilled by
2497 for (i = 0; i < num; i++)
2499 allocno = spilled_coalesced_allocnos[i];
2500 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno
2501 || ALLOCNO_HARD_REGNO (allocno) >= 0
2502 || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
2503 && (ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)]
2504 || ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX)))
2506 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2507 fprintf (ira_dump_file, " Slot %d (freq,size):", slot_num);
2509 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2510 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2512 ira_assert (ALLOCNO_HARD_REGNO (a) < 0);
2513 ALLOCNO_HARD_REGNO (a) = -slot_num;
2514 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2515 fprintf (ira_dump_file, " a%dr%d(%d,%d)",
2516 ALLOCNO_NUM (a), ALLOCNO_REGNO (a), ALLOCNO_FREQ (a),
2517 MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a)),
2518 reg_max_ref_width[ALLOCNO_REGNO (a)]));
2523 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2524 fprintf (ira_dump_file, "\n");
2526 ira_spilled_reg_stack_slots_num = slot_num - 1;
2527 ira_free (spilled_coalesced_allocnos);
2528 /* Sort regnos according the slot numbers. */
2529 regno_max_ref_width = reg_max_ref_width;
2530 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_slot_compare);
2531 /* Uncoalesce allocnos which is necessary for (re)assigning during
2533 FOR_EACH_ALLOCNO (a, ai)
2535 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
2536 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
2538 ira_free (regno_coalesced_allocno_num);
2539 ira_free (regno_coalesced_allocno_cost);
2544 /* This page contains code used by the reload pass to improve the
2547 /* The function is called from reload to mark changes in the
2548 allocation of REGNO made by the reload. Remember that reg_renumber
2549 reflects the change result. */
2551 ira_mark_allocation_change (int regno)
2553 ira_allocno_t a = ira_regno_allocno_map[regno];
2554 int old_hard_regno, hard_regno, cost;
2555 enum reg_class cover_class = ALLOCNO_COVER_CLASS (a);
2557 ira_assert (a != NULL);
2558 hard_regno = reg_renumber[regno];
2559 if ((old_hard_regno = ALLOCNO_HARD_REGNO (a)) == hard_regno)
2561 if (old_hard_regno < 0)
2562 cost = -ALLOCNO_MEMORY_COST (a);
2565 ira_assert (ira_class_hard_reg_index[cover_class][old_hard_regno] >= 0);
2566 cost = -(ALLOCNO_HARD_REG_COSTS (a) == NULL
2567 ? ALLOCNO_COVER_CLASS_COST (a)
2568 : ALLOCNO_HARD_REG_COSTS (a)
2569 [ira_class_hard_reg_index[cover_class][old_hard_regno]]);
2570 update_copy_costs (a, false);
2572 ira_overall_cost -= cost;
2573 ALLOCNO_HARD_REGNO (a) = hard_regno;
2576 ALLOCNO_HARD_REGNO (a) = -1;
2577 cost += ALLOCNO_MEMORY_COST (a);
2579 else if (ira_class_hard_reg_index[cover_class][hard_regno] >= 0)
2581 cost += (ALLOCNO_HARD_REG_COSTS (a) == NULL
2582 ? ALLOCNO_COVER_CLASS_COST (a)
2583 : ALLOCNO_HARD_REG_COSTS (a)
2584 [ira_class_hard_reg_index[cover_class][hard_regno]]);
2585 update_copy_costs (a, true);
2588 /* Reload changed class of the allocno. */
2590 ira_overall_cost += cost;
2593 /* This function is called when reload deletes memory-memory move. In
2594 this case we marks that the allocation of the corresponding
2595 allocnos should be not changed in future. Otherwise we risk to get
2598 ira_mark_memory_move_deletion (int dst_regno, int src_regno)
2600 ira_allocno_t dst = ira_regno_allocno_map[dst_regno];
2601 ira_allocno_t src = ira_regno_allocno_map[src_regno];
2603 ira_assert (dst != NULL && src != NULL
2604 && ALLOCNO_HARD_REGNO (dst) < 0
2605 && ALLOCNO_HARD_REGNO (src) < 0);
2606 ALLOCNO_DONT_REASSIGN_P (dst) = true;
2607 ALLOCNO_DONT_REASSIGN_P (src) = true;
2610 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
2611 allocno A and return TRUE in the case of success. That is an
2612 analog of retry_global_alloc for IRA. */
2614 allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs)
2617 enum reg_class cover_class;
2618 int regno = ALLOCNO_REGNO (a);
2620 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), forbidden_regs);
2621 if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
2622 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), call_used_reg_set);
2623 ALLOCNO_ASSIGNED_P (a) = false;
2624 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2625 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2626 cover_class = ALLOCNO_COVER_CLASS (a);
2627 update_curr_costs (a);
2628 assign_hard_reg (a, true);
2629 hard_regno = ALLOCNO_HARD_REGNO (a);
2630 reg_renumber[regno] = hard_regno;
2632 ALLOCNO_HARD_REGNO (a) = -1;
2635 ira_assert (ira_class_hard_reg_index[cover_class][hard_regno] >= 0);
2636 ira_overall_cost -= (ALLOCNO_MEMORY_COST (a)
2637 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
2638 ? ALLOCNO_COVER_CLASS_COST (a)
2639 : ALLOCNO_HARD_REG_COSTS (a)
2640 [ira_class_hard_reg_index
2641 [cover_class][hard_regno]]));
2642 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
2643 && ! ira_hard_reg_not_in_set_p (hard_regno, ALLOCNO_MODE (a),
2646 ira_assert (flag_caller_saves);
2647 caller_save_needed = 1;
2651 /* If we found a hard register, modify the RTL for the pseudo
2652 register to show the hard register, and mark the pseudo register
2654 if (reg_renumber[regno] >= 0)
2656 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2657 fprintf (ira_dump_file, ": reassign to %d\n", reg_renumber[regno]);
2658 SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
2659 mark_home_live (regno);
2661 else if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2662 fprintf (ira_dump_file, "\n");
2664 return reg_renumber[regno] >= 0;
2667 /* Sort pseudos according their usage frequencies (putting most
2668 frequently ones first). */
2670 pseudo_reg_compare (const void *v1p, const void *v2p)
2672 int regno1 = *(const int *) v1p;
2673 int regno2 = *(const int *) v2p;
2676 if ((diff = REG_FREQ (regno2) - REG_FREQ (regno1)) != 0)
2678 return regno1 - regno2;
2681 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
2682 NUM of them) or spilled pseudos conflicting with pseudos in
2683 SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
2684 allocation has been changed. The function doesn't use
2685 BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
2686 PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
2687 is called by the reload pass at the end of each reload
2690 ira_reassign_pseudos (int *spilled_pseudo_regs, int num,
2691 HARD_REG_SET bad_spill_regs,
2692 HARD_REG_SET *pseudo_forbidden_regs,
2693 HARD_REG_SET *pseudo_previous_regs, bitmap spilled)
2697 ira_allocno_t a, conflict_a;
2698 HARD_REG_SET forbidden_regs;
2699 ira_allocno_conflict_iterator aci;
2702 qsort (spilled_pseudo_regs, num, sizeof (int), pseudo_reg_compare);
2704 /* Try to assign hard registers to pseudos from
2705 SPILLED_PSEUDO_REGS. */
2706 for (m = i = 0; i < num; i++)
2708 regno = spilled_pseudo_regs[i];
2709 COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
2710 IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]);
2711 IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]);
2712 gcc_assert (reg_renumber[regno] < 0);
2713 a = ira_regno_allocno_map[regno];
2714 ira_mark_allocation_change (regno);
2715 ira_assert (reg_renumber[regno] < 0);
2716 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2717 fprintf (ira_dump_file,
2718 " Spill %d(a%d), cost=%d", regno, ALLOCNO_NUM (a),
2719 ALLOCNO_MEMORY_COST (a)
2720 - ALLOCNO_COVER_CLASS_COST (a));
2721 allocno_reload_assign (a, forbidden_regs);
2722 if (reg_renumber[regno] >= 0)
2724 CLEAR_REGNO_REG_SET (spilled, regno);
2728 spilled_pseudo_regs[m++] = regno;
2732 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2734 fprintf (ira_dump_file, " Spilled regs");
2735 for (i = 0; i < m; i++)
2736 fprintf (ira_dump_file, " %d", spilled_pseudo_regs[i]);
2737 fprintf (ira_dump_file, "\n");
2739 /* Try to assign hard registers to pseudos conflicting with ones
2740 from SPILLED_PSEUDO_REGS. */
2741 for (i = n = 0; i < m; i++)
2743 regno = spilled_pseudo_regs[i];
2744 a = ira_regno_allocno_map[regno];
2745 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
2746 if (ALLOCNO_HARD_REGNO (conflict_a) < 0
2747 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a)
2748 && ! bitmap_bit_p (consideration_allocno_bitmap,
2749 ALLOCNO_NUM (conflict_a)))
2751 sorted_allocnos[n++] = conflict_a;
2752 bitmap_set_bit (consideration_allocno_bitmap,
2753 ALLOCNO_NUM (conflict_a));
2758 setup_allocno_priorities (sorted_allocnos, n);
2759 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
2760 allocno_priority_compare_func);
2761 for (i = 0; i < n; i++)
2763 a = sorted_allocnos[i];
2764 regno = ALLOCNO_REGNO (a);
2765 COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
2766 IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]);
2767 IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]);
2768 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2769 fprintf (ira_dump_file,
2770 " Try assign %d(a%d), cost=%d",
2771 regno, ALLOCNO_NUM (a),
2772 ALLOCNO_MEMORY_COST (a)
2773 - ALLOCNO_COVER_CLASS_COST (a));
2774 if (allocno_reload_assign (a, forbidden_regs))
2777 bitmap_clear_bit (spilled, regno);
2784 /* The function is called by reload and returns already allocated
2785 stack slot (if any) for REGNO with given INHERENT_SIZE and
2786 TOTAL_SIZE. In the case of failure to find a slot which can be
2787 used for REGNO, the function returns NULL. */
2789 ira_reuse_stack_slot (int regno, unsigned int inherent_size,
2790 unsigned int total_size)
2793 int slot_num, best_slot_num;
2794 int cost, best_cost;
2795 ira_copy_t cp, next_cp;
2796 ira_allocno_t another_allocno, allocno = ira_regno_allocno_map[regno];
2799 struct ira_spilled_reg_stack_slot *slot = NULL;
2801 ira_assert (flag_ira && inherent_size == PSEUDO_REGNO_BYTES (regno)
2802 && inherent_size <= total_size
2803 && ALLOCNO_HARD_REGNO (allocno) < 0);
2804 if (! flag_ira_share_spill_slots)
2806 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
2809 slot = &ira_spilled_reg_stack_slots[slot_num];
2814 best_cost = best_slot_num = -1;
2816 /* It means that the pseudo was spilled in the reload pass, try
2819 slot_num < ira_spilled_reg_stack_slots_num;
2822 slot = &ira_spilled_reg_stack_slots[slot_num];
2823 if (slot->mem == NULL_RTX)
2825 if (slot->width < total_size
2826 || GET_MODE_SIZE (GET_MODE (slot->mem)) < inherent_size)
2829 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
2830 FIRST_PSEUDO_REGISTER, i, bi)
2832 another_allocno = ira_regno_allocno_map[i];
2833 if (ira_allocno_live_ranges_intersect_p (allocno,
2837 for (cost = 0, cp = ALLOCNO_COPIES (allocno);
2841 if (cp->first == allocno)
2843 next_cp = cp->next_first_allocno_copy;
2844 another_allocno = cp->second;
2846 else if (cp->second == allocno)
2848 next_cp = cp->next_second_allocno_copy;
2849 another_allocno = cp->first;
2853 if (cp->insn == NULL_RTX)
2855 if (bitmap_bit_p (&slot->spilled_regs,
2856 ALLOCNO_REGNO (another_allocno)))
2859 if (cost > best_cost)
2862 best_slot_num = slot_num;
2869 slot_num = best_slot_num;
2870 slot = &ira_spilled_reg_stack_slots[slot_num];
2871 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
2873 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
2878 ira_assert (slot->width >= total_size);
2879 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
2880 FIRST_PSEUDO_REGISTER, i, bi)
2882 ira_assert (! ira_pseudo_live_ranges_intersect_p (regno, i));
2884 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
2885 if (internal_flag_ira_verbose > 3 && ira_dump_file)
2887 fprintf (ira_dump_file, " Assigning %d(freq=%d) slot %d of",
2888 regno, REG_FREQ (regno), slot_num);
2889 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
2890 FIRST_PSEUDO_REGISTER, i, bi)
2892 if ((unsigned) regno != i)
2893 fprintf (ira_dump_file, " %d", i);
2895 fprintf (ira_dump_file, "\n");
2901 /* This is called by reload every time a new stack slot X with
2902 TOTAL_SIZE was allocated for REGNO. We store this info for
2903 subsequent ira_reuse_stack_slot calls. */
2905 ira_mark_new_stack_slot (rtx x, int regno, unsigned int total_size)
2907 struct ira_spilled_reg_stack_slot *slot;
2909 ira_allocno_t allocno;
2911 ira_assert (flag_ira && PSEUDO_REGNO_BYTES (regno) <= total_size);
2912 allocno = ira_regno_allocno_map[regno];
2913 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
2916 slot_num = ira_spilled_reg_stack_slots_num++;
2917 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
2919 slot = &ira_spilled_reg_stack_slots[slot_num];
2920 INIT_REG_SET (&slot->spilled_regs);
2921 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
2923 slot->width = total_size;
2924 if (internal_flag_ira_verbose > 3 && ira_dump_file)
2925 fprintf (ira_dump_file, " Assigning %d(freq=%d) a new slot %d\n",
2926 regno, REG_FREQ (regno), slot_num);
2930 /* Return spill cost for pseudo-registers whose numbers are in array
2931 REGNOS (with a negative number as an end marker) for reload with
2932 given IN and OUT for INSN. Return also number points (through
2933 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
2934 the register pressure is high, number of references of the
2935 pseudo-registers (through NREFS), number of callee-clobbered
2936 hard-registers occupied by the pseudo-registers (through
2937 CALL_USED_COUNT), and the first hard regno occupied by the
2938 pseudo-registers (through FIRST_HARD_REGNO). */
2940 calculate_spill_cost (int *regnos, rtx in, rtx out, rtx insn,
2941 int *excess_pressure_live_length,
2942 int *nrefs, int *call_used_count, int *first_hard_regno)
2944 int i, cost, regno, hard_regno, j, count, saved_cost, nregs;
2950 for (length = count = cost = i = 0;; i++)
2955 *nrefs += REG_N_REFS (regno);
2956 hard_regno = reg_renumber[regno];
2957 ira_assert (hard_regno >= 0);
2958 a = ira_regno_allocno_map[regno];
2959 length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2960 cost += ALLOCNO_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a);
2961 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
2962 for (j = 0; j < nregs; j++)
2963 if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j))
2967 in_p = in && REG_P (in) && (int) REGNO (in) == hard_regno;
2968 out_p = out && REG_P (out) && (int) REGNO (out) == hard_regno;
2970 && find_regno_note (insn, REG_DEAD, hard_regno) != NULL_RTX)
2974 saved_cost += ira_memory_move_cost
2975 [ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)][1];
2978 += ira_memory_move_cost
2979 [ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)][0];
2980 cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)) * saved_cost;
2983 *excess_pressure_live_length = length;
2984 *call_used_count = count;
2988 hard_regno = reg_renumber[regnos[0]];
2990 *first_hard_regno = hard_regno;
2994 /* Return TRUE if spilling pseudo-registers whose numbers are in array
2995 REGNOS is better than spilling pseudo-registers with numbers in
2996 OTHER_REGNOS for reload with given IN and OUT for INSN. The
2997 function used by the reload pass to make better register spilling
3000 ira_better_spill_reload_regno_p (int *regnos, int *other_regnos,
3001 rtx in, rtx out, rtx insn)
3003 int cost, other_cost;
3004 int length, other_length;
3005 int nrefs, other_nrefs;
3006 int call_used_count, other_call_used_count;
3007 int hard_regno, other_hard_regno;
3009 cost = calculate_spill_cost (regnos, in, out, insn,
3010 &length, &nrefs, &call_used_count, &hard_regno);
3011 other_cost = calculate_spill_cost (other_regnos, in, out, insn,
3012 &other_length, &other_nrefs,
3013 &other_call_used_count,
3015 if (nrefs == 0 && other_nrefs != 0)
3017 if (nrefs != 0 && other_nrefs == 0)
3019 if (cost != other_cost)
3020 return cost < other_cost;
3021 if (length != other_length)
3022 return length > other_length;
3023 #ifdef REG_ALLOC_ORDER
3024 if (hard_regno >= 0 && other_hard_regno >= 0)
3025 return (inv_reg_alloc_order[hard_regno]
3026 < inv_reg_alloc_order[other_hard_regno]);
3028 if (call_used_count != other_call_used_count)
3029 return call_used_count > other_call_used_count;
3036 /* Allocate and initialize data necessary for assign_hard_reg. */
3038 ira_initiate_assign (void)
3041 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
3042 * ira_allocnos_num);
3043 consideration_allocno_bitmap = ira_allocate_bitmap ();
3044 initiate_cost_update ();
3045 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
3048 /* Deallocate data used by assign_hard_reg. */
3050 ira_finish_assign (void)
3052 ira_free (sorted_allocnos);
3053 ira_free_bitmap (consideration_allocno_bitmap);
3054 finish_cost_update ();
3055 ira_free (allocno_priorities);
3060 /* Entry function doing color-based register allocation. */
3064 allocno_stack_vec = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
3065 removed_splay_allocno_vec
3066 = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
3067 memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p));
3068 ira_initiate_assign ();
3070 ira_finish_assign ();
3071 VEC_free (ira_allocno_t, heap, removed_splay_allocno_vec);
3072 VEC_free (ira_allocno_t, heap, allocno_stack_vec);
3073 move_spill_restore ();
3078 /* This page contains a simple register allocator without usage of
3079 allocno conflicts. This is used for fast allocation for -O0. */
3081 /* Do register allocation by not using allocno conflicts. It uses
3082 only allocno live ranges. The algorithm is close to Chow's
3083 priority coloring. */
3085 fast_allocation (void)
3087 int i, j, k, num, class_size, hard_regno;
3089 bool no_stack_reg_p;
3091 enum reg_class cover_class;
3092 enum machine_mode mode;
3094 ira_allocno_iterator ai;
3095 allocno_live_range_t r;
3096 HARD_REG_SET conflict_hard_regs, *used_hard_regs;
3098 sorted_allocnos = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
3099 * ira_allocnos_num);
3101 FOR_EACH_ALLOCNO (a, ai)
3102 sorted_allocnos[num++] = a;
3103 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
3104 setup_allocno_priorities (sorted_allocnos, num);
3105 used_hard_regs = (HARD_REG_SET *) ira_allocate (sizeof (HARD_REG_SET)
3107 for (i = 0; i < ira_max_point; i++)
3108 CLEAR_HARD_REG_SET (used_hard_regs[i]);
3109 qsort (sorted_allocnos, ira_allocnos_num, sizeof (ira_allocno_t),
3110 allocno_priority_compare_func);
3111 for (i = 0; i < num; i++)
3113 a = sorted_allocnos[i];
3114 COPY_HARD_REG_SET (conflict_hard_regs, ALLOCNO_CONFLICT_HARD_REGS (a));
3115 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
3116 for (j = r->start; j <= r->finish; j++)
3117 IOR_HARD_REG_SET (conflict_hard_regs, used_hard_regs[j]);
3118 cover_class = ALLOCNO_COVER_CLASS (a);
3119 ALLOCNO_ASSIGNED_P (a) = true;
3120 ALLOCNO_HARD_REGNO (a) = -1;
3121 if (hard_reg_set_subset_p (reg_class_contents[cover_class],
3122 conflict_hard_regs))
3124 mode = ALLOCNO_MODE (a);
3126 no_stack_reg_p = ALLOCNO_NO_STACK_REG_P (a);
3128 class_size = ira_class_hard_regs_num[cover_class];
3129 for (j = 0; j < class_size; j++)
3131 hard_regno = ira_class_hard_regs[cover_class][j];
3133 if (no_stack_reg_p && FIRST_STACK_REG <= hard_regno
3134 && hard_regno <= LAST_STACK_REG)
3137 if (!ira_hard_reg_not_in_set_p (hard_regno, mode, conflict_hard_regs)
3138 || (TEST_HARD_REG_BIT
3139 (prohibited_class_mode_regs[cover_class][mode], hard_regno)))
3141 ALLOCNO_HARD_REGNO (a) = hard_regno;
3142 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
3143 for (k = r->start; k <= r->finish; k++)
3144 IOR_HARD_REG_SET (used_hard_regs[k],
3145 ira_reg_mode_hard_regset[hard_regno][mode]);
3149 ira_free (sorted_allocnos);
3150 ira_free (used_hard_regs);
3151 ira_free (allocno_priorities);
3152 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
3153 ira_print_disposition (ira_dump_file);
3158 /* Entry function doing coloring. */
3163 ira_allocno_iterator ai;
3165 /* Setup updated costs. */
3166 FOR_EACH_ALLOCNO (a, ai)
3168 ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
3169 ALLOCNO_UPDATED_COVER_CLASS_COST (a) = ALLOCNO_COVER_CLASS_COST (a);