1 /* IRA allocation based on graph coloring.
2 Copyright (C) 2006, 2007, 2008, 2009, 2010
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 find conflicts using allocno
90 /* Return TRUE if live ranges of allocnos A1 and A2 intersect. It is
91 used to find a conflict for new allocnos or allocnos with the
92 different cover classes. */
94 allocnos_have_intersected_live_ranges_p (ira_allocno_t a1, ira_allocno_t a2)
98 if (ALLOCNO_REG (a1) != NULL && ALLOCNO_REG (a2) != NULL
99 && (ORIGINAL_REGNO (ALLOCNO_REG (a1))
100 == ORIGINAL_REGNO (ALLOCNO_REG (a2))))
102 return ira_allocno_live_ranges_intersect_p (ALLOCNO_LIVE_RANGES (a1),
103 ALLOCNO_LIVE_RANGES (a2));
106 #ifdef ENABLE_IRA_CHECKING
108 /* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
109 intersect. This should be used when there is only one region.
110 Currently this is used during reload. */
112 pseudos_have_intersected_live_ranges_p (int regno1, int regno2)
114 ira_allocno_t a1, a2;
116 ira_assert (regno1 >= FIRST_PSEUDO_REGISTER
117 && regno2 >= FIRST_PSEUDO_REGISTER);
118 /* Reg info caclulated by dataflow infrastructure can be different
119 from one calculated by regclass. */
120 if ((a1 = ira_loop_tree_root->regno_allocno_map[regno1]) == NULL
121 || (a2 = ira_loop_tree_root->regno_allocno_map[regno2]) == NULL)
123 return allocnos_have_intersected_live_ranges_p (a1, a2);
130 /* This page contains functions used to choose hard registers for
133 /* Array whose element value is TRUE if the corresponding hard
134 register was already allocated for an allocno. */
135 static bool allocated_hardreg_p[FIRST_PSEUDO_REGISTER];
137 /* Describes one element in a queue of allocnos whose costs need to be
138 updated. Each allocno in the queue is known to have a cover class. */
139 struct update_cost_queue_elem
141 /* This element is in the queue iff CHECK == update_cost_check. */
144 /* COST_HOP_DIVISOR**N, where N is the length of the shortest path
145 connecting this allocno to the one being allocated. */
148 /* The next allocno in the queue, or null if this is the last element. */
152 /* The first element in a queue of allocnos whose copy costs need to be
153 updated. Null if the queue is empty. */
154 static ira_allocno_t update_cost_queue;
156 /* The last element in the queue described by update_cost_queue.
157 Not valid if update_cost_queue is null. */
158 static struct update_cost_queue_elem *update_cost_queue_tail;
160 /* A pool of elements in the queue described by update_cost_queue.
161 Elements are indexed by ALLOCNO_NUM. */
162 static struct update_cost_queue_elem *update_cost_queue_elems;
164 /* The current value of update_copy_cost call count. */
165 static int update_cost_check;
167 /* Allocate and initialize data necessary for function
168 update_copy_costs. */
170 initiate_cost_update (void)
174 size = ira_allocnos_num * sizeof (struct update_cost_queue_elem);
175 update_cost_queue_elems
176 = (struct update_cost_queue_elem *) ira_allocate (size);
177 memset (update_cost_queue_elems, 0, size);
178 update_cost_check = 0;
181 /* Deallocate data used by function update_copy_costs. */
183 finish_cost_update (void)
185 ira_free (update_cost_queue_elems);
188 /* When we traverse allocnos to update hard register costs, the cost
189 divisor will be multiplied by the following macro value for each
190 hop from given allocno to directly connected allocnos. */
191 #define COST_HOP_DIVISOR 4
193 /* Start a new cost-updating pass. */
195 start_update_cost (void)
198 update_cost_queue = NULL;
201 /* Add (ALLOCNO, DIVISOR) to the end of update_cost_queue,
202 unless ALLOCNO is already in the queue, or has no cover class. */
204 queue_update_cost (ira_allocno_t allocno, int divisor)
206 struct update_cost_queue_elem *elem;
208 elem = &update_cost_queue_elems[ALLOCNO_NUM (allocno)];
209 if (elem->check != update_cost_check
210 && ALLOCNO_COVER_CLASS (allocno) != NO_REGS)
212 elem->check = update_cost_check;
213 elem->divisor = divisor;
215 if (update_cost_queue == NULL)
216 update_cost_queue = allocno;
218 update_cost_queue_tail->next = allocno;
219 update_cost_queue_tail = elem;
223 /* Try to remove the first element from update_cost_queue. Return false
224 if the queue was empty, otherwise make (*ALLOCNO, *DIVISOR) describe
225 the removed element. */
227 get_next_update_cost (ira_allocno_t *allocno, int *divisor)
229 struct update_cost_queue_elem *elem;
231 if (update_cost_queue == NULL)
234 *allocno = update_cost_queue;
235 elem = &update_cost_queue_elems[ALLOCNO_NUM (*allocno)];
236 *divisor = elem->divisor;
237 update_cost_queue = elem->next;
241 /* Update the cost of allocnos to increase chances to remove some
242 copies as the result of subsequent assignment. */
244 update_copy_costs (ira_allocno_t allocno, bool decr_p)
246 int i, cost, update_cost, hard_regno, divisor;
247 enum machine_mode mode;
248 enum reg_class rclass, cover_class;
249 ira_allocno_t another_allocno;
250 ira_copy_t cp, next_cp;
252 hard_regno = ALLOCNO_HARD_REGNO (allocno);
253 ira_assert (hard_regno >= 0);
255 cover_class = ALLOCNO_COVER_CLASS (allocno);
256 if (cover_class == NO_REGS)
258 i = ira_class_hard_reg_index[cover_class][hard_regno];
260 rclass = REGNO_REG_CLASS (hard_regno);
262 start_update_cost ();
266 mode = ALLOCNO_MODE (allocno);
267 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
269 if (cp->first == allocno)
271 next_cp = cp->next_first_allocno_copy;
272 another_allocno = cp->second;
274 else if (cp->second == allocno)
276 next_cp = cp->next_second_allocno_copy;
277 another_allocno = cp->first;
282 cover_class = ALLOCNO_COVER_CLASS (another_allocno);
283 if (! ira_reg_classes_intersect_p[rclass][cover_class]
284 || ALLOCNO_ASSIGNED_P (another_allocno))
287 cost = (cp->second == allocno
288 ? ira_get_register_move_cost (mode, rclass, cover_class)
289 : ira_get_register_move_cost (mode, cover_class, rclass));
293 update_cost = cp->freq * cost / divisor;
294 if (update_cost == 0)
297 ira_allocate_and_set_or_copy_costs
298 (&ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno), cover_class,
299 ALLOCNO_UPDATED_COVER_CLASS_COST (another_allocno),
300 ALLOCNO_HARD_REG_COSTS (another_allocno));
301 ira_allocate_and_set_or_copy_costs
302 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
304 ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
305 i = ira_class_hard_reg_index[cover_class][hard_regno];
307 ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno)[i] += update_cost;
308 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno)[i]
311 queue_update_cost (another_allocno, divisor * COST_HOP_DIVISOR);
314 while (get_next_update_cost (&allocno, &divisor));
317 /* This function updates COSTS (decrease if DECR_P) for hard_registers
318 of COVER_CLASS by conflict costs of the unassigned allocnos
319 connected by copies with allocnos in update_cost_queue. This
320 update increases chances to remove some copies. */
322 update_conflict_hard_regno_costs (int *costs, enum reg_class cover_class,
325 int i, cost, class_size, freq, mult, div, divisor;
326 int index, hard_regno;
329 enum reg_class another_cover_class;
330 ira_allocno_t allocno, another_allocno;
331 ira_copy_t cp, next_cp;
333 while (get_next_update_cost (&allocno, &divisor))
334 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
336 if (cp->first == allocno)
338 next_cp = cp->next_first_allocno_copy;
339 another_allocno = cp->second;
341 else if (cp->second == allocno)
343 next_cp = cp->next_second_allocno_copy;
344 another_allocno = cp->first;
348 another_cover_class = ALLOCNO_COVER_CLASS (another_allocno);
349 if (! ira_reg_classes_intersect_p[cover_class][another_cover_class]
350 || ALLOCNO_ASSIGNED_P (another_allocno)
351 || ALLOCNO_MAY_BE_SPILLED_P (ALLOCNO_FIRST_COALESCED_ALLOCNO
354 class_size = ira_class_hard_regs_num[another_cover_class];
355 ira_allocate_and_copy_costs
356 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
358 ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
360 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno);
361 if (conflict_costs == NULL)
366 freq = ALLOCNO_FREQ (another_allocno);
369 div = freq * divisor;
371 for (i = class_size - 1; i >= 0; i--)
373 hard_regno = ira_class_hard_regs[another_cover_class][i];
374 ira_assert (hard_regno >= 0);
375 index = ira_class_hard_reg_index[cover_class][hard_regno];
378 cost = conflict_costs [i] * mult / div;
384 costs[index] += cost;
387 /* Probably 5 hops will be enough. */
389 && divisor <= (COST_HOP_DIVISOR
393 queue_update_cost (another_allocno, divisor * COST_HOP_DIVISOR);
397 /* Sort allocnos according to the profit of usage of a hard register
398 instead of memory for them. */
400 allocno_cost_compare_func (const void *v1p, const void *v2p)
402 ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
403 ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
406 c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_UPDATED_COVER_CLASS_COST (p1);
407 c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_UPDATED_COVER_CLASS_COST (p2);
411 /* If regs are equally good, sort by allocno numbers, so that the
412 results of qsort leave nothing to chance. */
413 return ALLOCNO_NUM (p1) - ALLOCNO_NUM (p2);
416 /* Print all allocnos coalesced with ALLOCNO. */
418 print_coalesced_allocno (ira_allocno_t allocno)
422 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
423 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
425 ira_print_expanded_allocno (a);
428 fprintf (ira_dump_file, "+");
432 /* Choose a hard register for ALLOCNO (or for all coalesced allocnos
433 represented by ALLOCNO). If RETRY_P is TRUE, it means that the
434 function called from function `ira_reassign_conflict_allocnos' and
435 `allocno_reload_assign'. This function implements the optimistic
436 coalescing too: if we failed to assign a hard register to set of
437 the coalesced allocnos, we put them onto the coloring stack for
438 subsequent separate assigning. */
440 assign_hard_reg (ira_allocno_t allocno, bool retry_p)
442 HARD_REG_SET conflicting_regs;
443 int i, j, k, hard_regno, best_hard_regno, class_size;
444 int cost, mem_cost, min_cost, full_cost, min_full_cost, add_cost;
447 enum reg_class cover_class, rclass, conflict_cover_class;
448 enum machine_mode mode;
449 ira_allocno_t a, conflict_allocno;
450 ira_allocno_conflict_iterator aci;
451 static int costs[FIRST_PSEUDO_REGISTER], full_costs[FIRST_PSEUDO_REGISTER];
456 ira_assert (! ALLOCNO_ASSIGNED_P (allocno));
457 cover_class = ALLOCNO_COVER_CLASS (allocno);
458 class_size = ira_class_hard_regs_num[cover_class];
459 mode = ALLOCNO_MODE (allocno);
460 CLEAR_HARD_REG_SET (conflicting_regs);
461 best_hard_regno = -1;
462 memset (full_costs, 0, sizeof (int) * class_size);
464 if (allocno_coalesced_p)
465 bitmap_clear (processed_coalesced_allocno_bitmap);
466 memset (costs, 0, sizeof (int) * class_size);
467 memset (full_costs, 0, sizeof (int) * class_size);
469 no_stack_reg_p = false;
471 start_update_cost ();
472 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
473 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
475 mem_cost += ALLOCNO_UPDATED_MEMORY_COST (a);
476 IOR_HARD_REG_SET (conflicting_regs,
477 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
478 ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
479 cover_class, ALLOCNO_HARD_REG_COSTS (a));
480 a_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
482 no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a);
484 for (cost = ALLOCNO_UPDATED_COVER_CLASS_COST (a), i = 0;
489 costs[i] += a_costs[i];
490 full_costs[i] += a_costs[i];
495 full_costs[i] += cost;
497 /* Take preferences of conflicting allocnos into account. */
498 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
499 /* Reload can give another class so we need to check all
501 if (retry_p || bitmap_bit_p (consideration_allocno_bitmap,
502 ALLOCNO_NUM (conflict_allocno)))
504 conflict_cover_class = ALLOCNO_COVER_CLASS (conflict_allocno);
505 ira_assert (ira_reg_classes_intersect_p
506 [cover_class][conflict_cover_class]);
507 if (allocno_coalesced_p)
509 if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
510 ALLOCNO_NUM (conflict_allocno)))
512 bitmap_set_bit (processed_coalesced_allocno_bitmap,
513 ALLOCNO_NUM (conflict_allocno));
515 if (ALLOCNO_ASSIGNED_P (conflict_allocno))
517 if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno)) >= 0
518 && ira_class_hard_reg_index[cover_class][hard_regno] >= 0)
522 ira_reg_mode_hard_regset
523 [hard_regno][ALLOCNO_MODE (conflict_allocno)]);
524 if (hard_reg_set_subset_p (reg_class_contents[cover_class],
529 else if (! ALLOCNO_MAY_BE_SPILLED_P (ALLOCNO_FIRST_COALESCED_ALLOCNO
532 ira_allocate_and_copy_costs
533 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno),
534 conflict_cover_class,
535 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_allocno));
537 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno);
538 if (conflict_costs != NULL)
539 for (j = class_size - 1; j >= 0; j--)
541 hard_regno = ira_class_hard_regs[cover_class][j];
542 ira_assert (hard_regno >= 0);
543 k = (ira_class_hard_reg_index
544 [conflict_cover_class][hard_regno]);
547 full_costs[j] -= conflict_costs[k];
549 queue_update_cost (conflict_allocno, COST_HOP_DIVISOR);
555 /* Take into account preferences of allocnos connected by copies to
556 the conflict allocnos. */
557 update_conflict_hard_regno_costs (full_costs, cover_class, true);
559 /* Take preferences of allocnos connected by copies into
561 start_update_cost ();
562 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
563 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
565 queue_update_cost (a, COST_HOP_DIVISOR);
569 update_conflict_hard_regno_costs (full_costs, cover_class, false);
570 min_cost = min_full_cost = INT_MAX;
571 /* We don't care about giving callee saved registers to allocnos no
572 living through calls because call clobbered registers are
573 allocated first (it is usual practice to put them first in
575 for (i = 0; i < class_size; i++)
577 hard_regno = ira_class_hard_regs[cover_class][i];
580 && FIRST_STACK_REG <= hard_regno && hard_regno <= LAST_STACK_REG)
583 if (! ira_hard_reg_not_in_set_p (hard_regno, mode, conflicting_regs)
584 || TEST_HARD_REG_BIT (prohibited_class_mode_regs[cover_class][mode],
588 full_cost = full_costs[i];
589 #ifndef HONOR_REG_ALLOC_ORDER
590 if (! allocated_hardreg_p[hard_regno]
591 && ira_hard_reg_not_in_set_p (hard_regno, mode, call_used_reg_set))
592 /* We need to save/restore the hard register in
593 epilogue/prologue. Therefore we increase the cost. */
595 /* ??? If only part is call clobbered. */
596 rclass = REGNO_REG_CLASS (hard_regno);
597 add_cost = (ira_memory_move_cost[mode][rclass][0]
598 + ira_memory_move_cost[mode][rclass][1] - 1);
600 full_cost += add_cost;
605 if (min_full_cost > full_cost)
607 min_full_cost = full_cost;
608 best_hard_regno = hard_regno;
609 ira_assert (hard_regno >= 0);
612 if (min_full_cost > mem_cost)
614 if (! retry_p && internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
615 fprintf (ira_dump_file, "(memory is more profitable %d vs %d) ",
616 mem_cost, min_full_cost);
617 best_hard_regno = -1;
620 if (flag_ira_algorithm != IRA_ALGORITHM_PRIORITY
621 && best_hard_regno < 0
622 && ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno) != allocno)
624 for (j = 0, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
625 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
627 ira_assert (! ALLOCNO_IN_GRAPH_P (a));
628 sorted_allocnos[j++] = a;
632 qsort (sorted_allocnos, j, sizeof (ira_allocno_t),
633 allocno_cost_compare_func);
634 for (i = 0; i < j; i++)
636 a = sorted_allocnos[i];
637 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
638 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
639 VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, a);
640 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
642 fprintf (ira_dump_file, " Pushing");
643 print_coalesced_allocno (a);
644 fprintf (ira_dump_file, "\n");
649 if (best_hard_regno >= 0)
650 allocated_hardreg_p[best_hard_regno] = true;
651 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
652 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
654 ALLOCNO_HARD_REGNO (a) = best_hard_regno;
655 ALLOCNO_ASSIGNED_P (a) = true;
656 if (best_hard_regno >= 0)
657 update_copy_costs (a, true);
658 ira_assert (ALLOCNO_COVER_CLASS (a) == cover_class);
659 /* We don't need updated costs anymore: */
660 ira_free_allocno_updated_costs (a);
664 return best_hard_regno >= 0;
669 /* This page contains the allocator based on the Chaitin-Briggs algorithm. */
671 /* Bucket of allocnos that can colored currently without spilling. */
672 static ira_allocno_t colorable_allocno_bucket;
674 /* Bucket of allocnos that might be not colored currently without
676 static ira_allocno_t uncolorable_allocno_bucket;
678 /* Each element of the array contains the current number of allocnos
679 of given *cover* class in the uncolorable_bucket. */
680 static int uncolorable_allocnos_num[N_REG_CLASSES];
682 /* Return the current spill priority of allocno A. The less the
683 number, the more preferable the allocno for spilling. */
685 allocno_spill_priority (ira_allocno_t a)
687 return (ALLOCNO_TEMP (a)
688 / (ALLOCNO_LEFT_CONFLICTS_SIZE (a)
689 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a)][ALLOCNO_MODE (a)]
693 /* Add ALLOCNO to bucket *BUCKET_PTR. ALLOCNO should be not in a bucket
696 add_allocno_to_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
698 ira_allocno_t first_allocno;
699 enum reg_class cover_class;
701 if (bucket_ptr == &uncolorable_allocno_bucket
702 && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
704 uncolorable_allocnos_num[cover_class]++;
705 ira_assert (uncolorable_allocnos_num[cover_class] > 0);
707 first_allocno = *bucket_ptr;
708 ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno) = first_allocno;
709 ALLOCNO_PREV_BUCKET_ALLOCNO (allocno) = NULL;
710 if (first_allocno != NULL)
711 ALLOCNO_PREV_BUCKET_ALLOCNO (first_allocno) = allocno;
712 *bucket_ptr = allocno;
715 /* The function returns frequency and number of available hard
716 registers for allocnos coalesced with ALLOCNO. */
718 get_coalesced_allocnos_attributes (ira_allocno_t allocno, int *freq, int *num)
724 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
725 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
727 *freq += ALLOCNO_FREQ (a);
728 *num += ALLOCNO_AVAILABLE_REGS_NUM (a);
734 /* Compare two allocnos to define which allocno should be pushed first
735 into the coloring stack. If the return is a negative number, the
736 allocno given by the first parameter will be pushed first. In this
737 case such allocno has less priority than the second one and the
738 hard register will be assigned to it after assignment to the second
739 one. As the result of such assignment order, the second allocno
740 has a better chance to get the best hard register. */
742 bucket_allocno_compare_func (const void *v1p, const void *v2p)
744 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
745 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
746 int diff, a1_freq, a2_freq, a1_num, a2_num;
748 if ((diff = (int) ALLOCNO_COVER_CLASS (a2) - ALLOCNO_COVER_CLASS (a1)) != 0)
750 get_coalesced_allocnos_attributes (a1, &a1_freq, &a1_num);
751 get_coalesced_allocnos_attributes (a2, &a2_freq, &a2_num);
752 if ((diff = a2_num - a1_num) != 0)
754 else if ((diff = a1_freq - a2_freq) != 0)
756 return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
759 /* Sort bucket *BUCKET_PTR and return the result through
762 sort_bucket (ira_allocno_t *bucket_ptr)
764 ira_allocno_t a, head;
767 for (n = 0, a = *bucket_ptr; a != NULL; a = ALLOCNO_NEXT_BUCKET_ALLOCNO (a))
768 sorted_allocnos[n++] = a;
771 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
772 bucket_allocno_compare_func);
774 for (n--; n >= 0; n--)
776 a = sorted_allocnos[n];
777 ALLOCNO_NEXT_BUCKET_ALLOCNO (a) = head;
778 ALLOCNO_PREV_BUCKET_ALLOCNO (a) = NULL;
780 ALLOCNO_PREV_BUCKET_ALLOCNO (head) = a;
786 /* Add ALLOCNO to bucket *BUCKET_PTR maintaining the order according
787 their priority. ALLOCNO should be not in a bucket before the
790 add_allocno_to_ordered_bucket (ira_allocno_t allocno,
791 ira_allocno_t *bucket_ptr)
793 ira_allocno_t before, after;
794 enum reg_class cover_class;
796 if (bucket_ptr == &uncolorable_allocno_bucket
797 && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
799 uncolorable_allocnos_num[cover_class]++;
800 ira_assert (uncolorable_allocnos_num[cover_class] > 0);
802 for (before = *bucket_ptr, after = NULL;
804 after = before, before = ALLOCNO_NEXT_BUCKET_ALLOCNO (before))
805 if (bucket_allocno_compare_func (&allocno, &before) < 0)
807 ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno) = before;
808 ALLOCNO_PREV_BUCKET_ALLOCNO (allocno) = after;
810 *bucket_ptr = allocno;
812 ALLOCNO_NEXT_BUCKET_ALLOCNO (after) = allocno;
814 ALLOCNO_PREV_BUCKET_ALLOCNO (before) = allocno;
817 /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
820 delete_allocno_from_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
822 ira_allocno_t prev_allocno, next_allocno;
823 enum reg_class cover_class;
825 if (bucket_ptr == &uncolorable_allocno_bucket
826 && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
828 uncolorable_allocnos_num[cover_class]--;
829 ira_assert (uncolorable_allocnos_num[cover_class] >= 0);
831 prev_allocno = ALLOCNO_PREV_BUCKET_ALLOCNO (allocno);
832 next_allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno);
833 if (prev_allocno != NULL)
834 ALLOCNO_NEXT_BUCKET_ALLOCNO (prev_allocno) = next_allocno;
837 ira_assert (*bucket_ptr == allocno);
838 *bucket_ptr = next_allocno;
840 if (next_allocno != NULL)
841 ALLOCNO_PREV_BUCKET_ALLOCNO (next_allocno) = prev_allocno;
844 /* Splay tree for each cover class. The trees are indexed by the
845 corresponding cover classes. Splay trees contain uncolorable
847 static splay_tree uncolorable_allocnos_splay_tree[N_REG_CLASSES];
849 /* If the following macro is TRUE, splay tree is used to choose an
850 allocno of the corresponding cover class for spilling. When the
851 number uncolorable allocnos of given cover class decreases to some
852 threshold, linear array search is used to find the best allocno for
853 spilling. This threshold is actually pretty big because, although
854 splay trees asymptotically is much faster, each splay tree
855 operation is sufficiently costly especially taking cache locality
857 #define USE_SPLAY_P(CLASS) (uncolorable_allocnos_num[CLASS] > 4000)
859 /* Put ALLOCNO onto the coloring stack without removing it from its
860 bucket. Pushing allocno to the coloring stack can result in moving
861 conflicting allocnos from the uncolorable bucket to the colorable
864 push_allocno_to_stack (ira_allocno_t allocno)
866 int left_conflicts_size, conflict_size, size;
867 ira_allocno_t a, conflict_allocno;
868 enum reg_class cover_class;
869 ira_allocno_conflict_iterator aci;
871 ALLOCNO_IN_GRAPH_P (allocno) = false;
872 VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, allocno);
873 cover_class = ALLOCNO_COVER_CLASS (allocno);
874 if (cover_class == NO_REGS)
876 size = ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)];
877 if (allocno_coalesced_p)
878 bitmap_clear (processed_coalesced_allocno_bitmap);
879 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
880 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
882 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
884 conflict_allocno = ALLOCNO_FIRST_COALESCED_ALLOCNO (conflict_allocno);
885 if (bitmap_bit_p (coloring_allocno_bitmap,
886 ALLOCNO_NUM (conflict_allocno)))
888 ira_assert (cover_class
889 == ALLOCNO_COVER_CLASS (conflict_allocno));
890 if (allocno_coalesced_p)
892 if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
893 ALLOCNO_NUM (conflict_allocno)))
895 bitmap_set_bit (processed_coalesced_allocno_bitmap,
896 ALLOCNO_NUM (conflict_allocno));
898 if (ALLOCNO_IN_GRAPH_P (conflict_allocno)
899 && ! ALLOCNO_ASSIGNED_P (conflict_allocno))
902 = ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno);
904 = (ira_reg_class_nregs
905 [cover_class][ALLOCNO_MODE (conflict_allocno)]);
907 (ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno) >= size);
908 if (left_conflicts_size + conflict_size
909 <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno))
911 ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno) -= size;
915 = ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno) - size;
916 if (uncolorable_allocnos_splay_tree[cover_class] != NULL
917 && !ALLOCNO_SPLAY_REMOVED_P (conflict_allocno)
918 && USE_SPLAY_P (cover_class))
922 (uncolorable_allocnos_splay_tree[cover_class],
923 (splay_tree_key) conflict_allocno) != NULL);
925 (uncolorable_allocnos_splay_tree[cover_class],
926 (splay_tree_key) conflict_allocno);
927 ALLOCNO_SPLAY_REMOVED_P (conflict_allocno) = true;
928 VEC_safe_push (ira_allocno_t, heap,
929 removed_splay_allocno_vec,
932 ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno)
933 = left_conflicts_size;
934 if (left_conflicts_size + conflict_size
935 <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno))
937 delete_allocno_from_bucket
938 (conflict_allocno, &uncolorable_allocno_bucket);
939 add_allocno_to_ordered_bucket
940 (conflict_allocno, &colorable_allocno_bucket);
950 /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
951 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
953 remove_allocno_from_bucket_and_push (ira_allocno_t allocno, bool colorable_p)
955 enum reg_class cover_class;
958 delete_allocno_from_bucket (allocno, &colorable_allocno_bucket);
960 delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
961 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
963 fprintf (ira_dump_file, " Pushing");
964 print_coalesced_allocno (allocno);
966 fprintf (ira_dump_file, "\n");
968 fprintf (ira_dump_file, "(potential spill: %spri=%d, cost=%d)\n",
969 ALLOCNO_BAD_SPILL_P (allocno) ? "bad spill, " : "",
970 allocno_spill_priority (allocno), ALLOCNO_TEMP (allocno));
972 cover_class = ALLOCNO_COVER_CLASS (allocno);
973 ira_assert ((colorable_p
974 && (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno)
975 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)]
976 <= ALLOCNO_AVAILABLE_REGS_NUM (allocno)))
978 && (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno)
979 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE
981 > ALLOCNO_AVAILABLE_REGS_NUM (allocno))));
983 ALLOCNO_MAY_BE_SPILLED_P (allocno) = true;
984 push_allocno_to_stack (allocno);
987 /* Put all allocnos from colorable bucket onto the coloring stack. */
989 push_only_colorable (void)
991 sort_bucket (&colorable_allocno_bucket);
992 for (;colorable_allocno_bucket != NULL;)
993 remove_allocno_from_bucket_and_push (colorable_allocno_bucket, true);
996 /* Puts ALLOCNO chosen for potential spilling onto the coloring
999 push_allocno_to_spill (ira_allocno_t allocno)
1001 delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
1002 ALLOCNO_MAY_BE_SPILLED_P (allocno) = true;
1003 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1004 fprintf (ira_dump_file, " Pushing p%d(%d) (spill for NO_REGS)\n",
1005 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno));
1006 push_allocno_to_stack (allocno);
1009 /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
1010 loop given by its LOOP_NODE. */
1012 ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p)
1017 VEC (edge, heap) *edges;
1019 ira_assert (loop_node->loop != NULL
1020 && (regno < 0 || regno >= FIRST_PSEUDO_REGISTER));
1024 FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
1025 if (e->src != loop_node->loop->latch
1027 || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
1028 && bitmap_bit_p (DF_LR_IN (e->dest), regno))))
1029 freq += EDGE_FREQUENCY (e);
1033 edges = get_loop_exit_edges (loop_node->loop);
1034 for (i = 0; VEC_iterate (edge, edges, i, e); i++)
1036 || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
1037 && bitmap_bit_p (DF_LR_IN (e->dest), regno)))
1038 freq += EDGE_FREQUENCY (e);
1039 VEC_free (edge, heap, edges);
1042 return REG_FREQ_FROM_EDGE_FREQ (freq);
1045 /* Calculate and return the cost of putting allocno A into memory. */
1047 calculate_allocno_spill_cost (ira_allocno_t a)
1050 enum machine_mode mode;
1051 enum reg_class rclass;
1052 ira_allocno_t parent_allocno;
1053 ira_loop_tree_node_t parent_node, loop_node;
1055 regno = ALLOCNO_REGNO (a);
1056 cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_UPDATED_COVER_CLASS_COST (a);
1057 if (ALLOCNO_CAP (a) != NULL)
1059 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
1060 if ((parent_node = loop_node->parent) == NULL)
1062 if ((parent_allocno = parent_node->regno_allocno_map[regno]) == NULL)
1064 mode = ALLOCNO_MODE (a);
1065 rclass = ALLOCNO_COVER_CLASS (a);
1066 if (ALLOCNO_HARD_REGNO (parent_allocno) < 0)
1067 cost -= (ira_memory_move_cost[mode][rclass][0]
1068 * ira_loop_edge_freq (loop_node, regno, true)
1069 + ira_memory_move_cost[mode][rclass][1]
1070 * ira_loop_edge_freq (loop_node, regno, false));
1072 cost += ((ira_memory_move_cost[mode][rclass][1]
1073 * ira_loop_edge_freq (loop_node, regno, true)
1074 + ira_memory_move_cost[mode][rclass][0]
1075 * ira_loop_edge_freq (loop_node, regno, false))
1076 - (ira_get_register_move_cost (mode, rclass, rclass)
1077 * (ira_loop_edge_freq (loop_node, regno, false)
1078 + ira_loop_edge_freq (loop_node, regno, true))));
1082 /* Compare keys in the splay tree used to choose best allocno for
1083 spilling. The best allocno has the minimal key. */
1085 allocno_spill_priority_compare (splay_tree_key k1, splay_tree_key k2)
1087 int pri1, pri2, diff;
1088 ira_allocno_t a1 = (ira_allocno_t) k1, a2 = (ira_allocno_t) k2;
1090 pri1 = (ALLOCNO_TEMP (a1)
1091 / (ALLOCNO_LEFT_CONFLICTS_SIZE (a1)
1092 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a1)][ALLOCNO_MODE (a1)]
1094 pri2 = (ALLOCNO_TEMP (a2)
1095 / (ALLOCNO_LEFT_CONFLICTS_SIZE (a2)
1096 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a2)][ALLOCNO_MODE (a2)]
1098 if ((diff = pri1 - pri2) != 0)
1100 if ((diff = ALLOCNO_TEMP (a1) - ALLOCNO_TEMP (a2)) != 0)
1102 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
1105 /* Allocate data of SIZE for the splay trees. We allocate only spay
1106 tree roots or splay tree nodes. If you change this, please rewrite
1109 splay_tree_allocate (int size, void *data ATTRIBUTE_UNUSED)
1111 if (size != sizeof (struct splay_tree_node_s))
1112 return ira_allocate (size);
1113 return pool_alloc (splay_tree_node_pool);
1116 /* Free data NODE for the splay trees. We allocate and free only spay
1117 tree roots or splay tree nodes. If you change this, please rewrite
1120 splay_tree_free (void *node, void *data ATTRIBUTE_UNUSED)
1123 enum reg_class cover_class;
1125 for (i = 0; i < ira_reg_class_cover_size; i++)
1127 cover_class = ira_reg_class_cover[i];
1128 if (node == uncolorable_allocnos_splay_tree[cover_class])
1134 pool_free (splay_tree_node_pool, node);
1137 /* Push allocnos to the coloring stack. The order of allocnos in the
1138 stack defines the order for the subsequent coloring. */
1140 push_allocnos_to_stack (void)
1142 ira_allocno_t allocno, a, i_allocno, *allocno_vec;
1143 enum reg_class cover_class, rclass;
1144 int allocno_pri, i_allocno_pri, allocno_cost, i_allocno_cost;
1145 int i, j, num, cover_class_allocnos_num[N_REG_CLASSES];
1146 ira_allocno_t *cover_class_allocnos[N_REG_CLASSES];
1150 VEC_truncate(ira_allocno_t, removed_splay_allocno_vec, 0);
1151 for (i = 0; i < ira_reg_class_cover_size; i++)
1153 cover_class = ira_reg_class_cover[i];
1154 cover_class_allocnos_num[cover_class] = 0;
1155 cover_class_allocnos[cover_class] = NULL;
1156 uncolorable_allocnos_splay_tree[cover_class] = NULL;
1158 /* Calculate uncolorable allocno spill costs. */
1159 for (allocno = uncolorable_allocno_bucket;
1161 allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno))
1162 if ((cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
1164 cover_class_allocnos_num[cover_class]++;
1166 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1167 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1169 cost += calculate_allocno_spill_cost (a);
1173 /* ??? Remove cost of copies between the coalesced
1175 ALLOCNO_TEMP (allocno) = cost;
1177 /* Define place where to put uncolorable allocnos of the same cover
1179 for (num = i = 0; i < ira_reg_class_cover_size; i++)
1181 cover_class = ira_reg_class_cover[i];
1182 ira_assert (cover_class_allocnos_num[cover_class]
1183 == uncolorable_allocnos_num[cover_class]);
1184 if (cover_class_allocnos_num[cover_class] != 0)
1186 cover_class_allocnos[cover_class] = allocnos_for_spilling + num;
1187 num += cover_class_allocnos_num[cover_class];
1188 cover_class_allocnos_num[cover_class] = 0;
1190 if (USE_SPLAY_P (cover_class))
1191 uncolorable_allocnos_splay_tree[cover_class]
1192 = splay_tree_new_with_allocator (allocno_spill_priority_compare,
1193 NULL, NULL, splay_tree_allocate,
1194 splay_tree_free, NULL);
1196 ira_assert (num <= ira_allocnos_num);
1197 /* Collect uncolorable allocnos of each cover class. */
1198 for (allocno = uncolorable_allocno_bucket;
1200 allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno))
1201 if ((cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
1203 cover_class_allocnos
1204 [cover_class][cover_class_allocnos_num[cover_class]++] = allocno;
1205 if (uncolorable_allocnos_splay_tree[cover_class] != NULL)
1206 splay_tree_insert (uncolorable_allocnos_splay_tree[cover_class],
1207 (splay_tree_key) allocno,
1208 (splay_tree_value) allocno);
1212 push_only_colorable ();
1213 allocno = uncolorable_allocno_bucket;
1214 if (allocno == NULL)
1216 cover_class = ALLOCNO_COVER_CLASS (allocno);
1217 if (cover_class == NO_REGS)
1219 push_allocno_to_spill (allocno);
1222 /* Potential spilling. */
1224 (ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)] > 0);
1225 if (USE_SPLAY_P (cover_class))
1227 for (;VEC_length (ira_allocno_t, removed_splay_allocno_vec) != 0;)
1229 allocno = VEC_pop (ira_allocno_t, removed_splay_allocno_vec);
1230 ALLOCNO_SPLAY_REMOVED_P (allocno) = false;
1231 rclass = ALLOCNO_COVER_CLASS (allocno);
1232 if (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno)
1233 + ira_reg_class_nregs [rclass][ALLOCNO_MODE (allocno)]
1234 > ALLOCNO_AVAILABLE_REGS_NUM (allocno))
1236 (uncolorable_allocnos_splay_tree[rclass],
1237 (splay_tree_key) allocno, (splay_tree_value) allocno);
1239 allocno = ((ira_allocno_t)
1241 (uncolorable_allocnos_splay_tree[cover_class])->key);
1242 splay_tree_remove (uncolorable_allocnos_splay_tree[cover_class],
1243 (splay_tree_key) allocno);
1247 num = cover_class_allocnos_num[cover_class];
1248 ira_assert (num > 0);
1249 allocno_vec = cover_class_allocnos[cover_class];
1251 allocno_pri = allocno_cost = 0;
1252 /* Sort uncolorable allocno to find the one with the lowest
1254 for (i = 0, j = num - 1; i <= j;)
1256 i_allocno = allocno_vec[i];
1257 if (! ALLOCNO_IN_GRAPH_P (i_allocno)
1258 && ALLOCNO_IN_GRAPH_P (allocno_vec[j]))
1260 i_allocno = allocno_vec[j];
1261 allocno_vec[j] = allocno_vec[i];
1262 allocno_vec[i] = i_allocno;
1264 if (ALLOCNO_IN_GRAPH_P (i_allocno))
1267 ira_assert (ALLOCNO_TEMP (i_allocno) != INT_MAX);
1268 i_allocno_cost = ALLOCNO_TEMP (i_allocno);
1269 i_allocno_pri = allocno_spill_priority (i_allocno);
1271 || (! ALLOCNO_BAD_SPILL_P (i_allocno)
1272 && ALLOCNO_BAD_SPILL_P (allocno))
1273 || (! (ALLOCNO_BAD_SPILL_P (i_allocno)
1274 && ! ALLOCNO_BAD_SPILL_P (allocno))
1275 && (allocno_pri > i_allocno_pri
1276 || (allocno_pri == i_allocno_pri
1277 && (allocno_cost > i_allocno_cost
1278 || (allocno_cost == i_allocno_cost
1279 && (ALLOCNO_NUM (allocno)
1280 > ALLOCNO_NUM (i_allocno))))))))
1282 allocno = i_allocno;
1283 allocno_cost = i_allocno_cost;
1284 allocno_pri = i_allocno_pri;
1287 if (! ALLOCNO_IN_GRAPH_P (allocno_vec[j]))
1290 ira_assert (allocno != NULL && j >= 0);
1291 cover_class_allocnos_num[cover_class] = j + 1;
1293 ira_assert (ALLOCNO_IN_GRAPH_P (allocno)
1294 && ALLOCNO_COVER_CLASS (allocno) == cover_class
1295 && (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno)
1296 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE
1298 > ALLOCNO_AVAILABLE_REGS_NUM (allocno)));
1299 remove_allocno_from_bucket_and_push (allocno, false);
1301 ira_assert (colorable_allocno_bucket == NULL
1302 && uncolorable_allocno_bucket == NULL);
1303 for (i = 0; i < ira_reg_class_cover_size; i++)
1305 cover_class = ira_reg_class_cover[i];
1306 ira_assert (uncolorable_allocnos_num[cover_class] == 0);
1307 if (uncolorable_allocnos_splay_tree[cover_class] != NULL)
1308 splay_tree_delete (uncolorable_allocnos_splay_tree[cover_class]);
1312 /* Pop the coloring stack and assign hard registers to the popped
1315 pop_allocnos_from_stack (void)
1317 ira_allocno_t allocno;
1318 enum reg_class cover_class;
1320 for (;VEC_length (ira_allocno_t, allocno_stack_vec) != 0;)
1322 allocno = VEC_pop (ira_allocno_t, allocno_stack_vec);
1323 cover_class = ALLOCNO_COVER_CLASS (allocno);
1324 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1326 fprintf (ira_dump_file, " Popping");
1327 print_coalesced_allocno (allocno);
1328 fprintf (ira_dump_file, " -- ");
1330 if (cover_class == NO_REGS)
1332 ALLOCNO_HARD_REGNO (allocno) = -1;
1333 ALLOCNO_ASSIGNED_P (allocno) = true;
1334 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno) == NULL);
1336 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno) == NULL);
1337 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1338 fprintf (ira_dump_file, "assign memory\n");
1340 else if (assign_hard_reg (allocno, false))
1342 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1343 fprintf (ira_dump_file, "assign reg %d\n",
1344 ALLOCNO_HARD_REGNO (allocno));
1346 else if (ALLOCNO_ASSIGNED_P (allocno))
1348 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1349 fprintf (ira_dump_file, "spill\n");
1351 ALLOCNO_IN_GRAPH_P (allocno) = true;
1355 /* Set up number of available hard registers for ALLOCNO. */
1357 setup_allocno_available_regs_num (ira_allocno_t allocno)
1359 int i, n, hard_regs_num, hard_regno;
1360 enum machine_mode mode;
1361 enum reg_class cover_class;
1363 HARD_REG_SET temp_set;
1365 cover_class = ALLOCNO_COVER_CLASS (allocno);
1366 ALLOCNO_AVAILABLE_REGS_NUM (allocno) = ira_available_class_regs[cover_class];
1367 if (cover_class == NO_REGS)
1369 CLEAR_HARD_REG_SET (temp_set);
1370 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) == allocno);
1371 hard_regs_num = ira_class_hard_regs_num[cover_class];
1372 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1373 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1375 IOR_HARD_REG_SET (temp_set, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1379 mode = ALLOCNO_MODE (allocno);
1380 for (n = 0, i = hard_regs_num - 1; i >= 0; i--)
1382 hard_regno = ira_class_hard_regs[cover_class][i];
1383 if (TEST_HARD_REG_BIT (temp_set, hard_regno)
1384 || TEST_HARD_REG_BIT (prohibited_class_mode_regs[cover_class][mode],
1388 if (internal_flag_ira_verbose > 2 && n > 0 && ira_dump_file != NULL)
1389 fprintf (ira_dump_file, " Reg %d of %s has %d regs less\n",
1390 ALLOCNO_REGNO (allocno), reg_class_names[cover_class], n);
1391 ALLOCNO_AVAILABLE_REGS_NUM (allocno) -= n;
1394 /* Set up ALLOCNO_LEFT_CONFLICTS_SIZE for ALLOCNO. */
1396 setup_allocno_left_conflicts_size (ira_allocno_t allocno)
1398 int i, hard_regs_num, hard_regno, conflict_allocnos_size;
1399 ira_allocno_t a, conflict_allocno;
1400 enum reg_class cover_class;
1401 HARD_REG_SET temp_set;
1402 ira_allocno_conflict_iterator aci;
1404 cover_class = ALLOCNO_COVER_CLASS (allocno);
1405 hard_regs_num = ira_class_hard_regs_num[cover_class];
1406 CLEAR_HARD_REG_SET (temp_set);
1407 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) == allocno);
1408 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1409 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1411 IOR_HARD_REG_SET (temp_set, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1415 AND_HARD_REG_SET (temp_set, reg_class_contents[cover_class]);
1416 AND_COMPL_HARD_REG_SET (temp_set, ira_no_alloc_regs);
1417 conflict_allocnos_size = 0;
1418 if (! hard_reg_set_empty_p (temp_set))
1419 for (i = 0; i < (int) hard_regs_num; i++)
1421 hard_regno = ira_class_hard_regs[cover_class][i];
1422 if (TEST_HARD_REG_BIT (temp_set, hard_regno))
1424 conflict_allocnos_size++;
1425 CLEAR_HARD_REG_BIT (temp_set, hard_regno);
1426 if (hard_reg_set_empty_p (temp_set))
1430 CLEAR_HARD_REG_SET (temp_set);
1431 if (allocno_coalesced_p)
1432 bitmap_clear (processed_coalesced_allocno_bitmap);
1433 if (cover_class != NO_REGS)
1434 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1435 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1437 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
1440 = ALLOCNO_FIRST_COALESCED_ALLOCNO (conflict_allocno);
1441 if (bitmap_bit_p (consideration_allocno_bitmap,
1442 ALLOCNO_NUM (conflict_allocno)))
1444 ira_assert (cover_class
1445 == ALLOCNO_COVER_CLASS (conflict_allocno));
1446 if (allocno_coalesced_p)
1448 if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
1449 ALLOCNO_NUM (conflict_allocno)))
1451 bitmap_set_bit (processed_coalesced_allocno_bitmap,
1452 ALLOCNO_NUM (conflict_allocno));
1454 if (! ALLOCNO_ASSIGNED_P (conflict_allocno))
1455 conflict_allocnos_size
1456 += (ira_reg_class_nregs
1457 [cover_class][ALLOCNO_MODE (conflict_allocno)]);
1458 else if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno))
1461 int last = (hard_regno
1463 [hard_regno][ALLOCNO_MODE (conflict_allocno)]);
1465 while (hard_regno < last)
1467 if (! TEST_HARD_REG_BIT (temp_set, hard_regno))
1469 conflict_allocnos_size++;
1470 SET_HARD_REG_BIT (temp_set, hard_regno);
1480 ALLOCNO_LEFT_CONFLICTS_SIZE (allocno) = conflict_allocnos_size;
1483 /* Put ALLOCNO in a bucket corresponding to its number and size of its
1484 conflicting allocnos and hard registers. */
1486 put_allocno_into_bucket (ira_allocno_t allocno)
1488 enum reg_class cover_class;
1490 cover_class = ALLOCNO_COVER_CLASS (allocno);
1491 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
1493 ALLOCNO_IN_GRAPH_P (allocno) = true;
1494 setup_allocno_left_conflicts_size (allocno);
1495 setup_allocno_available_regs_num (allocno);
1496 if (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno)
1497 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)]
1498 <= ALLOCNO_AVAILABLE_REGS_NUM (allocno))
1499 add_allocno_to_bucket (allocno, &colorable_allocno_bucket);
1501 add_allocno_to_bucket (allocno, &uncolorable_allocno_bucket);
1504 /* The function is used to sort allocnos according to their execution
1507 copy_freq_compare_func (const void *v1p, const void *v2p)
1509 ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p;
1517 /* If freqencies are equal, sort by copies, so that the results of
1518 qsort leave nothing to chance. */
1519 return cp1->num - cp2->num;
1522 /* Merge two sets of coalesced allocnos given correspondingly by
1523 allocnos A1 and A2 (more accurately merging A2 set into A1
1526 merge_allocnos (ira_allocno_t a1, ira_allocno_t a2)
1528 ira_allocno_t a, first, last, next;
1530 first = ALLOCNO_FIRST_COALESCED_ALLOCNO (a1);
1531 if (first == ALLOCNO_FIRST_COALESCED_ALLOCNO (a2))
1533 for (last = a2, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
1534 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1536 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = first;
1541 next = ALLOCNO_NEXT_COALESCED_ALLOCNO (first);
1542 ALLOCNO_NEXT_COALESCED_ALLOCNO (first) = a2;
1543 ALLOCNO_NEXT_COALESCED_ALLOCNO (last) = next;
1546 /* Return TRUE if there are conflicting allocnos from two sets of
1547 coalesced allocnos given correspondingly by allocnos A1 and A2. If
1548 RELOAD_P is TRUE, we use live ranges to find conflicts because
1549 conflicts are represented only for allocnos of the same cover class
1550 and during the reload pass we coalesce allocnos for sharing stack
1553 coalesced_allocno_conflict_p (ira_allocno_t a1, ira_allocno_t a2,
1556 ira_allocno_t a, conflict_allocno;
1557 ira_allocno_conflict_iterator aci;
1559 if (allocno_coalesced_p)
1561 bitmap_clear (processed_coalesced_allocno_bitmap);
1562 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
1563 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1565 bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a));
1570 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
1571 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1575 for (conflict_allocno = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
1577 = ALLOCNO_NEXT_COALESCED_ALLOCNO (conflict_allocno))
1579 if (allocnos_have_intersected_live_ranges_p (a,
1582 if (conflict_allocno == a1)
1588 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
1589 if (conflict_allocno == a1
1590 || (allocno_coalesced_p
1591 && bitmap_bit_p (processed_coalesced_allocno_bitmap,
1592 ALLOCNO_NUM (conflict_allocno))))
1601 /* The major function for aggressive allocno coalescing. For the
1602 reload pass (RELOAD_P) we coalesce only spilled allocnos. If some
1603 allocnos have been coalesced, we set up flag
1604 allocno_coalesced_p. */
1606 coalesce_allocnos (bool reload_p)
1609 ira_copy_t cp, next_cp, *sorted_copies;
1610 enum reg_class cover_class;
1611 enum machine_mode mode;
1613 int i, n, cp_num, regno;
1616 sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num
1617 * sizeof (ira_copy_t));
1619 /* Collect copies. */
1620 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
1622 a = ira_allocnos[j];
1623 regno = ALLOCNO_REGNO (a);
1624 if ((! reload_p && ALLOCNO_ASSIGNED_P (a))
1626 && (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0
1627 || (regno < ira_reg_equiv_len
1628 && (ira_reg_equiv_const[regno] != NULL_RTX
1629 || ira_reg_equiv_invariant_p[regno])))))
1631 cover_class = ALLOCNO_COVER_CLASS (a);
1632 mode = ALLOCNO_MODE (a);
1633 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
1637 next_cp = cp->next_first_allocno_copy;
1638 regno = ALLOCNO_REGNO (cp->second);
1639 /* For priority coloring we coalesce allocnos only with
1640 the same cover class not with intersected cover
1641 classes as it were possible. It is done for
1644 || (ALLOCNO_COVER_CLASS (cp->second) == cover_class
1645 && ALLOCNO_MODE (cp->second) == mode))
1646 && (cp->insn != NULL || cp->constraint_p)
1647 && ((! reload_p && ! ALLOCNO_ASSIGNED_P (cp->second))
1649 && ALLOCNO_ASSIGNED_P (cp->second)
1650 && ALLOCNO_HARD_REGNO (cp->second) < 0
1651 && (regno >= ira_reg_equiv_len
1652 || (! ira_reg_equiv_invariant_p[regno]
1653 && ira_reg_equiv_const[regno] == NULL_RTX)))))
1654 sorted_copies[cp_num++] = cp;
1656 else if (cp->second == a)
1657 next_cp = cp->next_second_allocno_copy;
1662 qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
1663 /* Coalesced copies, most frequently executed first. */
1664 for (; cp_num != 0;)
1666 for (i = 0; i < cp_num; i++)
1668 cp = sorted_copies[i];
1669 if (! coalesced_allocno_conflict_p (cp->first, cp->second, reload_p))
1671 allocno_coalesced_p = true;
1672 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1675 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
1676 cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
1677 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
1679 merge_allocnos (cp->first, cp->second);
1684 /* Collect the rest of copies. */
1685 for (n = 0; i < cp_num; i++)
1687 cp = sorted_copies[i];
1688 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->first)
1689 != ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->second))
1690 sorted_copies[n++] = cp;
1694 ira_free (sorted_copies);
1697 /* Map: allocno number -> allocno priority. */
1698 static int *allocno_priorities;
1700 /* Set up priorities for N allocnos in array
1701 CONSIDERATION_ALLOCNOS. */
1703 setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
1705 int i, length, nrefs, priority, max_priority, mult;
1709 for (i = 0; i < n; i++)
1711 a = consideration_allocnos[i];
1712 nrefs = ALLOCNO_NREFS (a);
1713 ira_assert (nrefs >= 0);
1714 mult = floor_log2 (ALLOCNO_NREFS (a)) + 1;
1715 ira_assert (mult >= 0);
1716 allocno_priorities[ALLOCNO_NUM (a)]
1719 * (ALLOCNO_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a))
1720 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a)][ALLOCNO_MODE (a)]);
1722 priority = -priority;
1723 if (max_priority < priority)
1724 max_priority = priority;
1726 mult = max_priority == 0 ? 1 : INT_MAX / max_priority;
1727 for (i = 0; i < n; i++)
1729 a = consideration_allocnos[i];
1730 length = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
1733 allocno_priorities[ALLOCNO_NUM (a)]
1734 = allocno_priorities[ALLOCNO_NUM (a)] * mult / length;
1738 /* Sort allocnos according to their priorities which are calculated
1739 analogous to ones in file `global.c'. */
1741 allocno_priority_compare_func (const void *v1p, const void *v2p)
1743 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
1744 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
1747 pri1 = allocno_priorities[ALLOCNO_NUM (a1)];
1748 pri2 = allocno_priorities[ALLOCNO_NUM (a2)];
1752 /* If regs are equally good, sort by allocnos, so that the results of
1753 qsort leave nothing to chance. */
1754 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
1757 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
1758 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
1760 color_allocnos (void)
1766 allocno_coalesced_p = false;
1767 processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
1768 if (flag_ira_coalesce)
1769 coalesce_allocnos (false);
1770 if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
1773 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1775 a = ira_allocnos[i];
1776 if (ALLOCNO_COVER_CLASS (a) == NO_REGS)
1778 ALLOCNO_HARD_REGNO (a) = -1;
1779 ALLOCNO_ASSIGNED_P (a) = true;
1780 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
1781 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
1782 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1784 fprintf (ira_dump_file, " Spill");
1785 print_coalesced_allocno (a);
1786 fprintf (ira_dump_file, "\n");
1790 sorted_allocnos[n++] = a;
1794 setup_allocno_priorities (sorted_allocnos, n);
1795 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
1796 allocno_priority_compare_func);
1797 for (i = 0; i < n; i++)
1799 a = sorted_allocnos[i];
1800 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1802 fprintf (ira_dump_file, " ");
1803 print_coalesced_allocno (a);
1804 fprintf (ira_dump_file, " -- ");
1806 if (assign_hard_reg (a, false))
1808 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1809 fprintf (ira_dump_file, "assign hard reg %d\n",
1810 ALLOCNO_HARD_REGNO (a));
1814 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1815 fprintf (ira_dump_file, "assign memory\n");
1822 /* Put the allocnos into the corresponding buckets. */
1823 colorable_allocno_bucket = NULL;
1824 uncolorable_allocno_bucket = NULL;
1825 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1827 a = ira_allocnos[i];
1828 if (ALLOCNO_COVER_CLASS (a) == NO_REGS)
1830 ALLOCNO_HARD_REGNO (a) = -1;
1831 ALLOCNO_ASSIGNED_P (a) = true;
1832 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
1833 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
1834 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1836 fprintf (ira_dump_file, " Spill");
1837 print_coalesced_allocno (a);
1838 fprintf (ira_dump_file, "\n");
1842 put_allocno_into_bucket (a);
1844 push_allocnos_to_stack ();
1845 pop_allocnos_from_stack ();
1847 if (flag_ira_coalesce)
1848 /* We don't need coalesced allocnos for ira_reassign_pseudos. */
1849 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1851 a = ira_allocnos[i];
1852 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
1853 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
1855 ira_free_bitmap (processed_coalesced_allocno_bitmap);
1856 allocno_coalesced_p = false;
1861 /* Output information about the loop given by its LOOP_TREE_NODE. */
1863 print_loop_title (ira_loop_tree_node_t loop_tree_node)
1867 ira_loop_tree_node_t subloop_node, dest_loop_node;
1871 ira_assert (loop_tree_node->loop != NULL);
1872 fprintf (ira_dump_file,
1873 "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
1874 loop_tree_node->loop->num,
1875 (loop_tree_node->parent == NULL
1876 ? -1 : loop_tree_node->parent->loop->num),
1877 loop_tree_node->loop->header->index,
1878 loop_depth (loop_tree_node->loop));
1879 for (subloop_node = loop_tree_node->children;
1880 subloop_node != NULL;
1881 subloop_node = subloop_node->next)
1882 if (subloop_node->bb != NULL)
1884 fprintf (ira_dump_file, " %d", subloop_node->bb->index);
1885 FOR_EACH_EDGE (e, ei, subloop_node->bb->succs)
1886 if (e->dest != EXIT_BLOCK_PTR
1887 && ((dest_loop_node = IRA_BB_NODE (e->dest)->parent)
1889 fprintf (ira_dump_file, "(->%d:l%d)",
1890 e->dest->index, dest_loop_node->loop->num);
1892 fprintf (ira_dump_file, "\n all:");
1893 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
1894 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
1895 fprintf (ira_dump_file, "\n modified regnos:");
1896 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->modified_regnos, 0, j, bi)
1897 fprintf (ira_dump_file, " %d", j);
1898 fprintf (ira_dump_file, "\n border:");
1899 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->border_allocnos, 0, j, bi)
1900 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
1901 fprintf (ira_dump_file, "\n Pressure:");
1902 for (j = 0; (int) j < ira_reg_class_cover_size; j++)
1904 enum reg_class cover_class;
1906 cover_class = ira_reg_class_cover[j];
1907 if (loop_tree_node->reg_pressure[cover_class] == 0)
1909 fprintf (ira_dump_file, " %s=%d", reg_class_names[cover_class],
1910 loop_tree_node->reg_pressure[cover_class]);
1912 fprintf (ira_dump_file, "\n");
1915 /* Color the allocnos inside loop (in the extreme case it can be all
1916 of the function) given the corresponding LOOP_TREE_NODE. The
1917 function is called for each loop during top-down traverse of the
1920 color_pass (ira_loop_tree_node_t loop_tree_node)
1922 int regno, hard_regno, index = -1;
1923 int cost, exit_freq, enter_freq;
1926 enum machine_mode mode;
1927 enum reg_class rclass, cover_class;
1928 ira_allocno_t a, subloop_allocno;
1929 ira_loop_tree_node_t subloop_node;
1931 ira_assert (loop_tree_node->bb == NULL);
1932 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1933 print_loop_title (loop_tree_node);
1935 bitmap_copy (coloring_allocno_bitmap, loop_tree_node->all_allocnos);
1936 bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap);
1937 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
1939 a = ira_allocnos[j];
1940 if (! ALLOCNO_ASSIGNED_P (a))
1942 bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a));
1944 /* Color all mentioned allocnos including transparent ones. */
1946 /* Process caps. They are processed just once. */
1947 if (flag_ira_region == IRA_REGION_MIXED
1948 || flag_ira_region == IRA_REGION_ALL)
1949 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
1951 a = ira_allocnos[j];
1952 if (ALLOCNO_CAP_MEMBER (a) == NULL)
1954 /* Remove from processing in the next loop. */
1955 bitmap_clear_bit (consideration_allocno_bitmap, j);
1956 rclass = ALLOCNO_COVER_CLASS (a);
1957 if (flag_ira_region == IRA_REGION_MIXED
1958 && (loop_tree_node->reg_pressure[rclass]
1959 <= ira_available_class_regs[rclass]))
1961 mode = ALLOCNO_MODE (a);
1962 hard_regno = ALLOCNO_HARD_REGNO (a);
1963 if (hard_regno >= 0)
1965 index = ira_class_hard_reg_index[rclass][hard_regno];
1966 ira_assert (index >= 0);
1968 regno = ALLOCNO_REGNO (a);
1969 subloop_allocno = ALLOCNO_CAP_MEMBER (a);
1970 subloop_node = ALLOCNO_LOOP_TREE_NODE (subloop_allocno);
1971 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno));
1972 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
1973 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
1974 if (hard_regno >= 0)
1975 update_copy_costs (subloop_allocno, true);
1976 /* We don't need updated costs anymore: */
1977 ira_free_allocno_updated_costs (subloop_allocno);
1980 /* Update costs of the corresponding allocnos (not caps) in the
1982 for (subloop_node = loop_tree_node->subloops;
1983 subloop_node != NULL;
1984 subloop_node = subloop_node->subloop_next)
1986 ira_assert (subloop_node->bb == NULL);
1987 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
1989 a = ira_allocnos[j];
1990 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
1991 mode = ALLOCNO_MODE (a);
1992 rclass = ALLOCNO_COVER_CLASS (a);
1993 hard_regno = ALLOCNO_HARD_REGNO (a);
1994 /* Use hard register class here. ??? */
1995 if (hard_regno >= 0)
1997 index = ira_class_hard_reg_index[rclass][hard_regno];
1998 ira_assert (index >= 0);
2000 regno = ALLOCNO_REGNO (a);
2001 /* ??? conflict costs */
2002 subloop_allocno = subloop_node->regno_allocno_map[regno];
2003 if (subloop_allocno == NULL
2004 || ALLOCNO_CAP (subloop_allocno) != NULL)
2006 ira_assert (ALLOCNO_COVER_CLASS (subloop_allocno) == rclass);
2007 ira_assert (bitmap_bit_p (subloop_node->all_allocnos,
2008 ALLOCNO_NUM (subloop_allocno)));
2009 if ((flag_ira_region == IRA_REGION_MIXED)
2010 && (loop_tree_node->reg_pressure[rclass]
2011 <= ira_available_class_regs[rclass]))
2013 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
2015 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
2016 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
2017 if (hard_regno >= 0)
2018 update_copy_costs (subloop_allocno, true);
2019 /* We don't need updated costs anymore: */
2020 ira_free_allocno_updated_costs (subloop_allocno);
2024 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
2025 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
2026 ira_assert (regno < ira_reg_equiv_len);
2027 if (ira_reg_equiv_invariant_p[regno]
2028 || ira_reg_equiv_const[regno] != NULL_RTX)
2030 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
2032 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
2033 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
2034 if (hard_regno >= 0)
2035 update_copy_costs (subloop_allocno, true);
2036 /* We don't need updated costs anymore: */
2037 ira_free_allocno_updated_costs (subloop_allocno);
2040 else if (hard_regno < 0)
2042 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
2043 -= ((ira_memory_move_cost[mode][rclass][1] * enter_freq)
2044 + (ira_memory_move_cost[mode][rclass][0] * exit_freq));
2048 cover_class = ALLOCNO_COVER_CLASS (subloop_allocno);
2049 cost = (ira_get_register_move_cost (mode, rclass, rclass)
2050 * (exit_freq + enter_freq));
2051 ira_allocate_and_set_or_copy_costs
2052 (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno), cover_class,
2053 ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno),
2054 ALLOCNO_HARD_REG_COSTS (subloop_allocno));
2055 ira_allocate_and_set_or_copy_costs
2056 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno),
2058 ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno));
2059 ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
2060 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
2062 if (ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno)
2063 > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index])
2064 ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno)
2065 = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index];
2066 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
2067 += (ira_memory_move_cost[mode][rclass][0] * enter_freq
2068 + ira_memory_move_cost[mode][rclass][1] * exit_freq);
2074 /* Initialize the common data for coloring and calls functions to do
2075 Chaitin-Briggs and regional coloring. */
2079 coloring_allocno_bitmap = ira_allocate_bitmap ();
2080 allocnos_for_spilling
2081 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
2082 * ira_allocnos_num);
2083 splay_tree_node_pool = create_alloc_pool ("splay tree nodes",
2084 sizeof (struct splay_tree_node_s),
2086 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2087 fprintf (ira_dump_file, "\n**** Allocnos coloring:\n\n");
2089 ira_traverse_loop_tree (false, ira_loop_tree_root, color_pass, NULL);
2091 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2092 ira_print_disposition (ira_dump_file);
2094 free_alloc_pool (splay_tree_node_pool);
2095 ira_free_bitmap (coloring_allocno_bitmap);
2096 ira_free (allocnos_for_spilling);
2101 /* Move spill/restore code, which are to be generated in ira-emit.c,
2102 to less frequent points (if it is profitable) by reassigning some
2103 allocnos (in loop with subloops containing in another loop) to
2104 memory which results in longer live-range where the corresponding
2105 pseudo-registers will be in memory. */
2107 move_spill_restore (void)
2109 int cost, regno, hard_regno, hard_regno2, index;
2111 int enter_freq, exit_freq;
2112 enum machine_mode mode;
2113 enum reg_class rclass;
2114 ira_allocno_t a, parent_allocno, subloop_allocno;
2115 ira_loop_tree_node_t parent, loop_node, subloop_node;
2116 ira_allocno_iterator ai;
2121 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2122 fprintf (ira_dump_file, "New iteration of spill/restore move\n");
2123 FOR_EACH_ALLOCNO (a, ai)
2125 regno = ALLOCNO_REGNO (a);
2126 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
2127 if (ALLOCNO_CAP_MEMBER (a) != NULL
2128 || ALLOCNO_CAP (a) != NULL
2129 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0
2130 || loop_node->children == NULL
2131 /* don't do the optimization because it can create
2132 copies and the reload pass can spill the allocno set
2133 by copy although the allocno will not get memory
2135 || ira_reg_equiv_invariant_p[regno]
2136 || ira_reg_equiv_const[regno] != NULL_RTX
2137 || !bitmap_bit_p (loop_node->border_allocnos, ALLOCNO_NUM (a)))
2139 mode = ALLOCNO_MODE (a);
2140 rclass = ALLOCNO_COVER_CLASS (a);
2141 index = ira_class_hard_reg_index[rclass][hard_regno];
2142 ira_assert (index >= 0);
2143 cost = (ALLOCNO_MEMORY_COST (a)
2144 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
2145 ? ALLOCNO_COVER_CLASS_COST (a)
2146 : ALLOCNO_HARD_REG_COSTS (a)[index]));
2147 for (subloop_node = loop_node->subloops;
2148 subloop_node != NULL;
2149 subloop_node = subloop_node->subloop_next)
2151 ira_assert (subloop_node->bb == NULL);
2152 subloop_allocno = subloop_node->regno_allocno_map[regno];
2153 if (subloop_allocno == NULL)
2155 ira_assert (rclass == ALLOCNO_COVER_CLASS (subloop_allocno));
2156 /* We have accumulated cost. To get the real cost of
2157 allocno usage in the loop we should subtract costs of
2158 the subloop allocnos. */
2159 cost -= (ALLOCNO_MEMORY_COST (subloop_allocno)
2160 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno) == NULL
2161 ? ALLOCNO_COVER_CLASS_COST (subloop_allocno)
2162 : ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index]));
2163 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
2164 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
2165 if ((hard_regno2 = ALLOCNO_HARD_REGNO (subloop_allocno)) < 0)
2166 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
2167 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
2171 += (ira_memory_move_cost[mode][rclass][0] * exit_freq
2172 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
2173 if (hard_regno2 != hard_regno)
2174 cost -= (ira_get_register_move_cost (mode, rclass, rclass)
2175 * (exit_freq + enter_freq));
2178 if ((parent = loop_node->parent) != NULL
2179 && (parent_allocno = parent->regno_allocno_map[regno]) != NULL)
2181 ira_assert (rclass == ALLOCNO_COVER_CLASS (parent_allocno));
2182 exit_freq = ira_loop_edge_freq (loop_node, regno, true);
2183 enter_freq = ira_loop_edge_freq (loop_node, regno, false);
2184 if ((hard_regno2 = ALLOCNO_HARD_REGNO (parent_allocno)) < 0)
2185 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
2186 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
2190 += (ira_memory_move_cost[mode][rclass][1] * exit_freq
2191 + ira_memory_move_cost[mode][rclass][0] * enter_freq);
2192 if (hard_regno2 != hard_regno)
2193 cost -= (ira_get_register_move_cost (mode, rclass, rclass)
2194 * (exit_freq + enter_freq));
2199 ALLOCNO_HARD_REGNO (a) = -1;
2200 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2204 " Moving spill/restore for a%dr%d up from loop %d",
2205 ALLOCNO_NUM (a), regno, loop_node->loop->num);
2206 fprintf (ira_dump_file, " - profit %d\n", -cost);
2218 /* Update current hard reg costs and current conflict hard reg costs
2219 for allocno A. It is done by processing its copies containing
2220 other allocnos already assigned. */
2222 update_curr_costs (ira_allocno_t a)
2224 int i, hard_regno, cost;
2225 enum machine_mode mode;
2226 enum reg_class cover_class, rclass;
2227 ira_allocno_t another_a;
2228 ira_copy_t cp, next_cp;
2230 ira_assert (! ALLOCNO_ASSIGNED_P (a));
2231 cover_class = ALLOCNO_COVER_CLASS (a);
2232 if (cover_class == NO_REGS)
2234 mode = ALLOCNO_MODE (a);
2235 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2239 next_cp = cp->next_first_allocno_copy;
2240 another_a = cp->second;
2242 else if (cp->second == a)
2244 next_cp = cp->next_second_allocno_copy;
2245 another_a = cp->first;
2249 if (! ira_reg_classes_intersect_p[cover_class][ALLOCNO_COVER_CLASS
2251 || ! ALLOCNO_ASSIGNED_P (another_a)
2252 || (hard_regno = ALLOCNO_HARD_REGNO (another_a)) < 0)
2254 rclass = REGNO_REG_CLASS (hard_regno);
2255 i = ira_class_hard_reg_index[cover_class][hard_regno];
2258 cost = (cp->first == a
2259 ? ira_get_register_move_cost (mode, rclass, cover_class)
2260 : ira_get_register_move_cost (mode, cover_class, rclass));
2261 ira_allocate_and_set_or_copy_costs
2262 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
2263 cover_class, ALLOCNO_COVER_CLASS_COST (a),
2264 ALLOCNO_HARD_REG_COSTS (a));
2265 ira_allocate_and_set_or_copy_costs
2266 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
2267 cover_class, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
2268 ALLOCNO_UPDATED_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
2269 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
2273 /* Try to assign hard registers to the unassigned allocnos and
2274 allocnos conflicting with them or conflicting with allocnos whose
2275 regno >= START_REGNO. The function is called after ira_flattening,
2276 so more allocnos (including ones created in ira-emit.c) will have a
2277 chance to get a hard register. We use simple assignment algorithm
2278 based on priorities. */
2280 ira_reassign_conflict_allocnos (int start_regno)
2282 int i, allocnos_to_color_num;
2283 ira_allocno_t a, conflict_a;
2284 ira_allocno_conflict_iterator aci;
2285 enum reg_class cover_class;
2286 bitmap allocnos_to_color;
2287 ira_allocno_iterator ai;
2289 allocnos_to_color = ira_allocate_bitmap ();
2290 allocnos_to_color_num = 0;
2291 FOR_EACH_ALLOCNO (a, ai)
2293 if (! ALLOCNO_ASSIGNED_P (a)
2294 && ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a)))
2296 if (ALLOCNO_COVER_CLASS (a) != NO_REGS)
2297 sorted_allocnos[allocnos_to_color_num++] = a;
2300 ALLOCNO_ASSIGNED_P (a) = true;
2301 ALLOCNO_HARD_REGNO (a) = -1;
2302 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2303 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2305 bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (a));
2307 if (ALLOCNO_REGNO (a) < start_regno
2308 || (cover_class = ALLOCNO_COVER_CLASS (a)) == NO_REGS)
2310 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
2312 ira_assert (ira_reg_classes_intersect_p
2313 [cover_class][ALLOCNO_COVER_CLASS (conflict_a)]);
2314 if (bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (conflict_a)))
2316 bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a));
2317 sorted_allocnos[allocnos_to_color_num++] = conflict_a;
2320 ira_free_bitmap (allocnos_to_color);
2321 if (allocnos_to_color_num > 1)
2323 setup_allocno_priorities (sorted_allocnos, allocnos_to_color_num);
2324 qsort (sorted_allocnos, allocnos_to_color_num, sizeof (ira_allocno_t),
2325 allocno_priority_compare_func);
2327 for (i = 0; i < allocnos_to_color_num; i++)
2329 a = sorted_allocnos[i];
2330 ALLOCNO_ASSIGNED_P (a) = false;
2331 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2332 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2333 update_curr_costs (a);
2335 for (i = 0; i < allocnos_to_color_num; i++)
2337 a = sorted_allocnos[i];
2338 if (assign_hard_reg (a, true))
2340 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2343 " Secondary allocation: assign hard reg %d to reg %d\n",
2344 ALLOCNO_HARD_REGNO (a), ALLOCNO_REGNO (a));
2351 /* This page contains code to coalesce memory stack slots used by
2352 spilled allocnos. This results in smaller stack frame, better data
2353 locality, and in smaller code for some architectures like
2354 x86/x86_64 where insn size depends on address displacement value.
2355 On the other hand, it can worsen insn scheduling after the RA but
2356 in practice it is less important than smaller stack frames. */
2358 /* Usage cost and order number of coalesced allocno set to which
2359 given pseudo register belongs to. */
2360 static int *regno_coalesced_allocno_cost;
2361 static int *regno_coalesced_allocno_num;
2363 /* Sort pseudos according frequencies of coalesced allocno sets they
2364 belong to (putting most frequently ones first), and according to
2365 coalesced allocno set order numbers. */
2367 coalesced_pseudo_reg_freq_compare (const void *v1p, const void *v2p)
2369 const int regno1 = *(const int *) v1p;
2370 const int regno2 = *(const int *) v2p;
2373 if ((diff = (regno_coalesced_allocno_cost[regno2]
2374 - regno_coalesced_allocno_cost[regno1])) != 0)
2376 if ((diff = (regno_coalesced_allocno_num[regno1]
2377 - regno_coalesced_allocno_num[regno2])) != 0)
2379 return regno1 - regno2;
2382 /* Widest width in which each pseudo reg is referred to (via subreg).
2383 It is used for sorting pseudo registers. */
2384 static unsigned int *regno_max_ref_width;
2386 /* Redefine STACK_GROWS_DOWNWARD in terms of 0 or 1. */
2387 #ifdef STACK_GROWS_DOWNWARD
2388 # undef STACK_GROWS_DOWNWARD
2389 # define STACK_GROWS_DOWNWARD 1
2391 # define STACK_GROWS_DOWNWARD 0
2394 /* Sort pseudos according their slot numbers (putting ones with
2395 smaller numbers first, or last when the frame pointer is not
2398 coalesced_pseudo_reg_slot_compare (const void *v1p, const void *v2p)
2400 const int regno1 = *(const int *) v1p;
2401 const int regno2 = *(const int *) v2p;
2402 ira_allocno_t a1 = ira_regno_allocno_map[regno1];
2403 ira_allocno_t a2 = ira_regno_allocno_map[regno2];
2404 int diff, slot_num1, slot_num2;
2405 int total_size1, total_size2;
2407 if (a1 == NULL || ALLOCNO_HARD_REGNO (a1) >= 0)
2409 if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
2410 return regno1 - regno2;
2413 else if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
2415 slot_num1 = -ALLOCNO_HARD_REGNO (a1);
2416 slot_num2 = -ALLOCNO_HARD_REGNO (a2);
2417 if ((diff = slot_num1 - slot_num2) != 0)
2418 return (frame_pointer_needed
2419 || !FRAME_GROWS_DOWNWARD == STACK_GROWS_DOWNWARD ? diff : -diff);
2420 total_size1 = MAX (PSEUDO_REGNO_BYTES (regno1), regno_max_ref_width[regno1]);
2421 total_size2 = MAX (PSEUDO_REGNO_BYTES (regno2), regno_max_ref_width[regno2]);
2422 if ((diff = total_size2 - total_size1) != 0)
2424 return regno1 - regno2;
2427 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
2428 for coalesced allocno sets containing allocnos with their regnos
2429 given in array PSEUDO_REGNOS of length N. */
2431 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos, int n)
2433 int i, num, regno, cost;
2434 ira_allocno_t allocno, a;
2436 for (num = i = 0; i < n; i++)
2438 regno = pseudo_regnos[i];
2439 allocno = ira_regno_allocno_map[regno];
2440 if (allocno == NULL)
2442 regno_coalesced_allocno_cost[regno] = 0;
2443 regno_coalesced_allocno_num[regno] = ++num;
2446 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
2449 for (cost = 0, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2450 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2452 cost += ALLOCNO_FREQ (a);
2456 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2457 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2459 regno_coalesced_allocno_num[ALLOCNO_REGNO (a)] = num;
2460 regno_coalesced_allocno_cost[ALLOCNO_REGNO (a)] = cost;
2467 /* Collect spilled allocnos representing coalesced allocno sets (the
2468 first coalesced allocno). The collected allocnos are returned
2469 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
2470 number of the collected allocnos. The allocnos are given by their
2471 regnos in array PSEUDO_REGNOS of length N. */
2473 collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n,
2474 ira_allocno_t *spilled_coalesced_allocnos)
2477 ira_allocno_t allocno;
2479 for (num = i = 0; i < n; i++)
2481 regno = pseudo_regnos[i];
2482 allocno = ira_regno_allocno_map[regno];
2483 if (allocno == NULL || ALLOCNO_HARD_REGNO (allocno) >= 0
2484 || ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
2486 spilled_coalesced_allocnos[num++] = allocno;
2491 /* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
2492 given slot contains live ranges of coalesced allocnos assigned to
2494 static allocno_live_range_t *slot_coalesced_allocnos_live_ranges;
2496 /* Return TRUE if coalesced allocnos represented by ALLOCNO has live
2497 ranges intersected with live ranges of coalesced allocnos assigned
2498 to slot with number N. */
2500 slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno, int n)
2504 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2505 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2507 if (ira_allocno_live_ranges_intersect_p
2508 (slot_coalesced_allocnos_live_ranges[n], ALLOCNO_LIVE_RANGES (a)))
2516 /* Update live ranges of slot to which coalesced allocnos represented
2517 by ALLOCNO were assigned. */
2519 setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno)
2523 allocno_live_range_t r;
2525 n = ALLOCNO_TEMP (allocno);
2526 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2527 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2529 r = ira_copy_allocno_live_range_list (ALLOCNO_LIVE_RANGES (a));
2530 slot_coalesced_allocnos_live_ranges[n]
2531 = ira_merge_allocno_live_ranges
2532 (slot_coalesced_allocnos_live_ranges[n], r);
2538 /* We have coalesced allocnos involving in copies. Coalesce allocnos
2539 further in order to share the same memory stack slot. Allocnos
2540 representing sets of allocnos coalesced before the call are given
2541 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
2542 some allocnos were coalesced in the function. */
2544 coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num)
2546 int i, j, n, last_coalesced_allocno_num;
2547 ira_allocno_t allocno, a;
2548 bool merged_p = false;
2549 bitmap set_jump_crosses = regstat_get_setjmp_crosses ();
2551 slot_coalesced_allocnos_live_ranges
2552 = (allocno_live_range_t *) ira_allocate (sizeof (allocno_live_range_t)
2553 * ira_allocnos_num);
2554 memset (slot_coalesced_allocnos_live_ranges, 0,
2555 sizeof (allocno_live_range_t) * ira_allocnos_num);
2556 last_coalesced_allocno_num = 0;
2557 /* Coalesce non-conflicting spilled allocnos preferring most
2559 for (i = 0; i < num; i++)
2561 allocno = spilled_coalesced_allocnos[i];
2562 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno
2563 || bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (allocno))
2564 || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
2565 && (ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX
2566 || ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)])))
2568 for (j = 0; j < i; j++)
2570 a = spilled_coalesced_allocnos[j];
2571 n = ALLOCNO_TEMP (a);
2572 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a
2573 && ! bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (a))
2574 && (ALLOCNO_REGNO (a) >= ira_reg_equiv_len
2575 || (! ira_reg_equiv_invariant_p[ALLOCNO_REGNO (a)]
2576 && ira_reg_equiv_const[ALLOCNO_REGNO (a)] == NULL_RTX))
2577 && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno, n))
2582 /* No coalescing: set up number for coalesced allocnos
2583 represented by ALLOCNO. */
2584 ALLOCNO_TEMP (allocno) = last_coalesced_allocno_num++;
2585 setup_slot_coalesced_allocno_live_ranges (allocno);
2589 allocno_coalesced_p = true;
2591 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2592 fprintf (ira_dump_file,
2593 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
2594 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno),
2595 ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2596 ALLOCNO_TEMP (allocno) = ALLOCNO_TEMP (a);
2597 setup_slot_coalesced_allocno_live_ranges (allocno);
2598 merge_allocnos (a, allocno);
2599 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a);
2602 for (i = 0; i < ira_allocnos_num; i++)
2603 ira_finish_allocno_live_range_list
2604 (slot_coalesced_allocnos_live_ranges[i]);
2605 ira_free (slot_coalesced_allocnos_live_ranges);
2609 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
2610 subsequent assigning stack slots to them in the reload pass. To do
2611 this we coalesce spilled allocnos first to decrease the number of
2612 memory-memory move insns. This function is called by the
2615 ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n,
2616 unsigned int *reg_max_ref_width)
2618 int max_regno = max_reg_num ();
2619 int i, regno, num, slot_num;
2620 ira_allocno_t allocno, a;
2621 ira_allocno_iterator ai;
2622 ira_allocno_t *spilled_coalesced_allocnos;
2624 processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
2625 /* Set up allocnos can be coalesced. */
2626 coloring_allocno_bitmap = ira_allocate_bitmap ();
2627 for (i = 0; i < n; i++)
2629 regno = pseudo_regnos[i];
2630 allocno = ira_regno_allocno_map[regno];
2631 if (allocno != NULL)
2632 bitmap_set_bit (coloring_allocno_bitmap,
2633 ALLOCNO_NUM (allocno));
2635 allocno_coalesced_p = false;
2636 coalesce_allocnos (true);
2637 ira_free_bitmap (coloring_allocno_bitmap);
2638 regno_coalesced_allocno_cost
2639 = (int *) ira_allocate (max_regno * sizeof (int));
2640 regno_coalesced_allocno_num
2641 = (int *) ira_allocate (max_regno * sizeof (int));
2642 memset (regno_coalesced_allocno_num, 0, max_regno * sizeof (int));
2643 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
2644 /* Sort regnos according frequencies of the corresponding coalesced
2646 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_freq_compare);
2647 spilled_coalesced_allocnos
2648 = (ira_allocno_t *) ira_allocate (ira_allocnos_num
2649 * sizeof (ira_allocno_t));
2650 /* Collect allocnos representing the spilled coalesced allocno
2652 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
2653 spilled_coalesced_allocnos);
2654 if (flag_ira_share_spill_slots
2655 && coalesce_spill_slots (spilled_coalesced_allocnos, num))
2657 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
2658 qsort (pseudo_regnos, n, sizeof (int),
2659 coalesced_pseudo_reg_freq_compare);
2660 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
2661 spilled_coalesced_allocnos);
2663 ira_free_bitmap (processed_coalesced_allocno_bitmap);
2664 allocno_coalesced_p = false;
2665 /* Assign stack slot numbers to spilled allocno sets, use smaller
2666 numbers for most frequently used coalesced allocnos. -1 is
2667 reserved for dynamic search of stack slots for pseudos spilled by
2670 for (i = 0; i < num; i++)
2672 allocno = spilled_coalesced_allocnos[i];
2673 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno
2674 || ALLOCNO_HARD_REGNO (allocno) >= 0
2675 || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
2676 && (ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX
2677 || ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)])))
2679 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2680 fprintf (ira_dump_file, " Slot %d (freq,size):", slot_num);
2682 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2683 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2685 ira_assert (ALLOCNO_HARD_REGNO (a) < 0);
2686 ALLOCNO_HARD_REGNO (a) = -slot_num;
2687 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2688 fprintf (ira_dump_file, " a%dr%d(%d,%d)",
2689 ALLOCNO_NUM (a), ALLOCNO_REGNO (a), ALLOCNO_FREQ (a),
2690 MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a)),
2691 reg_max_ref_width[ALLOCNO_REGNO (a)]));
2696 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2697 fprintf (ira_dump_file, "\n");
2699 ira_spilled_reg_stack_slots_num = slot_num - 1;
2700 ira_free (spilled_coalesced_allocnos);
2701 /* Sort regnos according the slot numbers. */
2702 regno_max_ref_width = reg_max_ref_width;
2703 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_slot_compare);
2704 /* Uncoalesce allocnos which is necessary for (re)assigning during
2706 FOR_EACH_ALLOCNO (a, ai)
2708 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
2709 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
2711 ira_free (regno_coalesced_allocno_num);
2712 ira_free (regno_coalesced_allocno_cost);
2717 /* This page contains code used by the reload pass to improve the
2720 /* The function is called from reload to mark changes in the
2721 allocation of REGNO made by the reload. Remember that reg_renumber
2722 reflects the change result. */
2724 ira_mark_allocation_change (int regno)
2726 ira_allocno_t a = ira_regno_allocno_map[regno];
2727 int old_hard_regno, hard_regno, cost;
2728 enum reg_class cover_class = ALLOCNO_COVER_CLASS (a);
2730 ira_assert (a != NULL);
2731 hard_regno = reg_renumber[regno];
2732 if ((old_hard_regno = ALLOCNO_HARD_REGNO (a)) == hard_regno)
2734 if (old_hard_regno < 0)
2735 cost = -ALLOCNO_MEMORY_COST (a);
2738 ira_assert (ira_class_hard_reg_index[cover_class][old_hard_regno] >= 0);
2739 cost = -(ALLOCNO_HARD_REG_COSTS (a) == NULL
2740 ? ALLOCNO_COVER_CLASS_COST (a)
2741 : ALLOCNO_HARD_REG_COSTS (a)
2742 [ira_class_hard_reg_index[cover_class][old_hard_regno]]);
2743 update_copy_costs (a, false);
2745 ira_overall_cost -= cost;
2746 ALLOCNO_HARD_REGNO (a) = hard_regno;
2749 ALLOCNO_HARD_REGNO (a) = -1;
2750 cost += ALLOCNO_MEMORY_COST (a);
2752 else if (ira_class_hard_reg_index[cover_class][hard_regno] >= 0)
2754 cost += (ALLOCNO_HARD_REG_COSTS (a) == NULL
2755 ? ALLOCNO_COVER_CLASS_COST (a)
2756 : ALLOCNO_HARD_REG_COSTS (a)
2757 [ira_class_hard_reg_index[cover_class][hard_regno]]);
2758 update_copy_costs (a, true);
2761 /* Reload changed class of the allocno. */
2763 ira_overall_cost += cost;
2766 /* This function is called when reload deletes memory-memory move. In
2767 this case we marks that the allocation of the corresponding
2768 allocnos should be not changed in future. Otherwise we risk to get
2771 ira_mark_memory_move_deletion (int dst_regno, int src_regno)
2773 ira_allocno_t dst = ira_regno_allocno_map[dst_regno];
2774 ira_allocno_t src = ira_regno_allocno_map[src_regno];
2776 ira_assert (dst != NULL && src != NULL
2777 && ALLOCNO_HARD_REGNO (dst) < 0
2778 && ALLOCNO_HARD_REGNO (src) < 0);
2779 ALLOCNO_DONT_REASSIGN_P (dst) = true;
2780 ALLOCNO_DONT_REASSIGN_P (src) = true;
2783 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
2784 allocno A and return TRUE in the case of success. */
2786 allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs)
2789 enum reg_class cover_class;
2790 int regno = ALLOCNO_REGNO (a);
2793 COPY_HARD_REG_SET (saved, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
2794 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), forbidden_regs);
2795 if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
2796 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), call_used_reg_set);
2797 ALLOCNO_ASSIGNED_P (a) = false;
2798 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2799 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2800 cover_class = ALLOCNO_COVER_CLASS (a);
2801 update_curr_costs (a);
2802 assign_hard_reg (a, true);
2803 hard_regno = ALLOCNO_HARD_REGNO (a);
2804 reg_renumber[regno] = hard_regno;
2806 ALLOCNO_HARD_REGNO (a) = -1;
2809 ira_assert (ira_class_hard_reg_index[cover_class][hard_regno] >= 0);
2810 ira_overall_cost -= (ALLOCNO_MEMORY_COST (a)
2811 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
2812 ? ALLOCNO_COVER_CLASS_COST (a)
2813 : ALLOCNO_HARD_REG_COSTS (a)
2814 [ira_class_hard_reg_index
2815 [cover_class][hard_regno]]));
2816 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
2817 && ! ira_hard_reg_not_in_set_p (hard_regno, ALLOCNO_MODE (a),
2820 ira_assert (flag_caller_saves);
2821 caller_save_needed = 1;
2825 /* If we found a hard register, modify the RTL for the pseudo
2826 register to show the hard register, and mark the pseudo register
2828 if (reg_renumber[regno] >= 0)
2830 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2831 fprintf (ira_dump_file, ": reassign to %d\n", reg_renumber[regno]);
2832 SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
2833 mark_home_live (regno);
2835 else if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2836 fprintf (ira_dump_file, "\n");
2837 COPY_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), saved);
2838 return reg_renumber[regno] >= 0;
2841 /* Sort pseudos according their usage frequencies (putting most
2842 frequently ones first). */
2844 pseudo_reg_compare (const void *v1p, const void *v2p)
2846 int regno1 = *(const int *) v1p;
2847 int regno2 = *(const int *) v2p;
2850 if ((diff = REG_FREQ (regno2) - REG_FREQ (regno1)) != 0)
2852 return regno1 - regno2;
2855 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
2856 NUM of them) or spilled pseudos conflicting with pseudos in
2857 SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
2858 allocation has been changed. The function doesn't use
2859 BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
2860 PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
2861 is called by the reload pass at the end of each reload
2864 ira_reassign_pseudos (int *spilled_pseudo_regs, int num,
2865 HARD_REG_SET bad_spill_regs,
2866 HARD_REG_SET *pseudo_forbidden_regs,
2867 HARD_REG_SET *pseudo_previous_regs,
2872 ira_allocno_t a, conflict_a;
2873 HARD_REG_SET forbidden_regs;
2874 ira_allocno_conflict_iterator aci;
2875 bitmap temp = BITMAP_ALLOC (NULL);
2877 /* Add pseudos which conflict with pseudos already in
2878 SPILLED_PSEUDO_REGS to SPILLED_PSEUDO_REGS. This is preferable
2879 to allocating in two steps as some of the conflicts might have
2880 a higher priority than the pseudos passed in SPILLED_PSEUDO_REGS. */
2881 for (i = 0; i < num; i++)
2882 bitmap_set_bit (temp, spilled_pseudo_regs[i]);
2884 for (i = 0, n = num; i < n; i++)
2886 int regno = spilled_pseudo_regs[i];
2887 bitmap_set_bit (temp, regno);
2889 a = ira_regno_allocno_map[regno];
2890 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
2891 if (ALLOCNO_HARD_REGNO (conflict_a) < 0
2892 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a)
2893 && ! bitmap_bit_p (temp, ALLOCNO_REGNO (conflict_a)))
2895 spilled_pseudo_regs[num++] = ALLOCNO_REGNO (conflict_a);
2896 bitmap_set_bit (temp, ALLOCNO_REGNO (conflict_a));
2897 /* ?!? This seems wrong. */
2898 bitmap_set_bit (consideration_allocno_bitmap,
2899 ALLOCNO_NUM (conflict_a));
2904 qsort (spilled_pseudo_regs, num, sizeof (int), pseudo_reg_compare);
2906 /* Try to assign hard registers to pseudos from
2907 SPILLED_PSEUDO_REGS. */
2908 for (i = 0; i < num; i++)
2910 regno = spilled_pseudo_regs[i];
2911 COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
2912 IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]);
2913 IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]);
2914 gcc_assert (reg_renumber[regno] < 0);
2915 a = ira_regno_allocno_map[regno];
2916 ira_mark_allocation_change (regno);
2917 ira_assert (reg_renumber[regno] < 0);
2918 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2919 fprintf (ira_dump_file,
2920 " Try Assign %d(a%d), cost=%d", regno, ALLOCNO_NUM (a),
2921 ALLOCNO_MEMORY_COST (a)
2922 - ALLOCNO_COVER_CLASS_COST (a));
2923 allocno_reload_assign (a, forbidden_regs);
2924 if (reg_renumber[regno] >= 0)
2926 CLEAR_REGNO_REG_SET (spilled, regno);
2934 /* The function is called by reload and returns already allocated
2935 stack slot (if any) for REGNO with given INHERENT_SIZE and
2936 TOTAL_SIZE. In the case of failure to find a slot which can be
2937 used for REGNO, the function returns NULL. */
2939 ira_reuse_stack_slot (int regno, unsigned int inherent_size,
2940 unsigned int total_size)
2943 int slot_num, best_slot_num;
2944 int cost, best_cost;
2945 ira_copy_t cp, next_cp;
2946 ira_allocno_t another_allocno, allocno = ira_regno_allocno_map[regno];
2949 struct ira_spilled_reg_stack_slot *slot = NULL;
2951 ira_assert (inherent_size == PSEUDO_REGNO_BYTES (regno)
2952 && inherent_size <= total_size
2953 && ALLOCNO_HARD_REGNO (allocno) < 0);
2954 if (! flag_ira_share_spill_slots)
2956 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
2959 slot = &ira_spilled_reg_stack_slots[slot_num];
2964 best_cost = best_slot_num = -1;
2966 /* It means that the pseudo was spilled in the reload pass, try
2969 slot_num < ira_spilled_reg_stack_slots_num;
2972 slot = &ira_spilled_reg_stack_slots[slot_num];
2973 if (slot->mem == NULL_RTX)
2975 if (slot->width < total_size
2976 || GET_MODE_SIZE (GET_MODE (slot->mem)) < inherent_size)
2979 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
2980 FIRST_PSEUDO_REGISTER, i, bi)
2982 another_allocno = ira_regno_allocno_map[i];
2983 if (allocnos_have_intersected_live_ranges_p (allocno,
2987 for (cost = 0, cp = ALLOCNO_COPIES (allocno);
2991 if (cp->first == allocno)
2993 next_cp = cp->next_first_allocno_copy;
2994 another_allocno = cp->second;
2996 else if (cp->second == allocno)
2998 next_cp = cp->next_second_allocno_copy;
2999 another_allocno = cp->first;
3003 if (cp->insn == NULL_RTX)
3005 if (bitmap_bit_p (&slot->spilled_regs,
3006 ALLOCNO_REGNO (another_allocno)))
3009 if (cost > best_cost)
3012 best_slot_num = slot_num;
3019 slot_num = best_slot_num;
3020 slot = &ira_spilled_reg_stack_slots[slot_num];
3021 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
3023 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
3028 ira_assert (slot->width >= total_size);
3029 #ifdef ENABLE_IRA_CHECKING
3030 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
3031 FIRST_PSEUDO_REGISTER, i, bi)
3033 ira_assert (! pseudos_have_intersected_live_ranges_p (regno, i));
3036 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
3037 if (internal_flag_ira_verbose > 3 && ira_dump_file)
3039 fprintf (ira_dump_file, " Assigning %d(freq=%d) slot %d of",
3040 regno, REG_FREQ (regno), slot_num);
3041 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
3042 FIRST_PSEUDO_REGISTER, i, bi)
3044 if ((unsigned) regno != i)
3045 fprintf (ira_dump_file, " %d", i);
3047 fprintf (ira_dump_file, "\n");
3053 /* This is called by reload every time a new stack slot X with
3054 TOTAL_SIZE was allocated for REGNO. We store this info for
3055 subsequent ira_reuse_stack_slot calls. */
3057 ira_mark_new_stack_slot (rtx x, int regno, unsigned int total_size)
3059 struct ira_spilled_reg_stack_slot *slot;
3061 ira_allocno_t allocno;
3063 ira_assert (PSEUDO_REGNO_BYTES (regno) <= total_size);
3064 allocno = ira_regno_allocno_map[regno];
3065 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
3068 slot_num = ira_spilled_reg_stack_slots_num++;
3069 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
3071 slot = &ira_spilled_reg_stack_slots[slot_num];
3072 INIT_REG_SET (&slot->spilled_regs);
3073 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
3075 slot->width = total_size;
3076 if (internal_flag_ira_verbose > 3 && ira_dump_file)
3077 fprintf (ira_dump_file, " Assigning %d(freq=%d) a new slot %d\n",
3078 regno, REG_FREQ (regno), slot_num);
3082 /* Return spill cost for pseudo-registers whose numbers are in array
3083 REGNOS (with a negative number as an end marker) for reload with
3084 given IN and OUT for INSN. Return also number points (through
3085 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
3086 the register pressure is high, number of references of the
3087 pseudo-registers (through NREFS), number of callee-clobbered
3088 hard-registers occupied by the pseudo-registers (through
3089 CALL_USED_COUNT), and the first hard regno occupied by the
3090 pseudo-registers (through FIRST_HARD_REGNO). */
3092 calculate_spill_cost (int *regnos, rtx in, rtx out, rtx insn,
3093 int *excess_pressure_live_length,
3094 int *nrefs, int *call_used_count, int *first_hard_regno)
3096 int i, cost, regno, hard_regno, j, count, saved_cost, nregs;
3102 for (length = count = cost = i = 0;; i++)
3107 *nrefs += REG_N_REFS (regno);
3108 hard_regno = reg_renumber[regno];
3109 ira_assert (hard_regno >= 0);
3110 a = ira_regno_allocno_map[regno];
3111 length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
3112 cost += ALLOCNO_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a);
3113 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
3114 for (j = 0; j < nregs; j++)
3115 if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j))
3119 in_p = in && REG_P (in) && (int) REGNO (in) == hard_regno;
3120 out_p = out && REG_P (out) && (int) REGNO (out) == hard_regno;
3122 && find_regno_note (insn, REG_DEAD, hard_regno) != NULL_RTX)
3126 saved_cost += ira_memory_move_cost
3127 [ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)][1];
3130 += ira_memory_move_cost
3131 [ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)][0];
3132 cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)) * saved_cost;
3135 *excess_pressure_live_length = length;
3136 *call_used_count = count;
3140 hard_regno = reg_renumber[regnos[0]];
3142 *first_hard_regno = hard_regno;
3146 /* Return TRUE if spilling pseudo-registers whose numbers are in array
3147 REGNOS is better than spilling pseudo-registers with numbers in
3148 OTHER_REGNOS for reload with given IN and OUT for INSN. The
3149 function used by the reload pass to make better register spilling
3152 ira_better_spill_reload_regno_p (int *regnos, int *other_regnos,
3153 rtx in, rtx out, rtx insn)
3155 int cost, other_cost;
3156 int length, other_length;
3157 int nrefs, other_nrefs;
3158 int call_used_count, other_call_used_count;
3159 int hard_regno, other_hard_regno;
3161 cost = calculate_spill_cost (regnos, in, out, insn,
3162 &length, &nrefs, &call_used_count, &hard_regno);
3163 other_cost = calculate_spill_cost (other_regnos, in, out, insn,
3164 &other_length, &other_nrefs,
3165 &other_call_used_count,
3167 if (nrefs == 0 && other_nrefs != 0)
3169 if (nrefs != 0 && other_nrefs == 0)
3171 if (cost != other_cost)
3172 return cost < other_cost;
3173 if (length != other_length)
3174 return length > other_length;
3175 #ifdef REG_ALLOC_ORDER
3176 if (hard_regno >= 0 && other_hard_regno >= 0)
3177 return (inv_reg_alloc_order[hard_regno]
3178 < inv_reg_alloc_order[other_hard_regno]);
3180 if (call_used_count != other_call_used_count)
3181 return call_used_count > other_call_used_count;
3188 /* Allocate and initialize data necessary for assign_hard_reg. */
3190 ira_initiate_assign (void)
3193 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
3194 * ira_allocnos_num);
3195 consideration_allocno_bitmap = ira_allocate_bitmap ();
3196 initiate_cost_update ();
3197 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
3200 /* Deallocate data used by assign_hard_reg. */
3202 ira_finish_assign (void)
3204 ira_free (sorted_allocnos);
3205 ira_free_bitmap (consideration_allocno_bitmap);
3206 finish_cost_update ();
3207 ira_free (allocno_priorities);
3212 /* Entry function doing color-based register allocation. */
3216 allocno_stack_vec = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
3217 removed_splay_allocno_vec
3218 = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
3219 memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p));
3220 ira_initiate_assign ();
3222 ira_finish_assign ();
3223 VEC_free (ira_allocno_t, heap, removed_splay_allocno_vec);
3224 VEC_free (ira_allocno_t, heap, allocno_stack_vec);
3225 move_spill_restore ();
3230 /* This page contains a simple register allocator without usage of
3231 allocno conflicts. This is used for fast allocation for -O0. */
3233 /* Do register allocation by not using allocno conflicts. It uses
3234 only allocno live ranges. The algorithm is close to Chow's
3235 priority coloring. */
3237 fast_allocation (void)
3239 int i, j, k, num, class_size, hard_regno;
3241 bool no_stack_reg_p;
3243 enum reg_class cover_class;
3244 enum machine_mode mode;
3246 ira_allocno_iterator ai;
3247 allocno_live_range_t r;
3248 HARD_REG_SET conflict_hard_regs, *used_hard_regs;
3250 sorted_allocnos = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
3251 * ira_allocnos_num);
3253 FOR_EACH_ALLOCNO (a, ai)
3254 sorted_allocnos[num++] = a;
3255 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
3256 setup_allocno_priorities (sorted_allocnos, num);
3257 used_hard_regs = (HARD_REG_SET *) ira_allocate (sizeof (HARD_REG_SET)
3259 for (i = 0; i < ira_max_point; i++)
3260 CLEAR_HARD_REG_SET (used_hard_regs[i]);
3261 qsort (sorted_allocnos, num, sizeof (ira_allocno_t),
3262 allocno_priority_compare_func);
3263 for (i = 0; i < num; i++)
3265 a = sorted_allocnos[i];
3266 COPY_HARD_REG_SET (conflict_hard_regs, ALLOCNO_CONFLICT_HARD_REGS (a));
3267 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
3268 for (j = r->start; j <= r->finish; j++)
3269 IOR_HARD_REG_SET (conflict_hard_regs, used_hard_regs[j]);
3270 cover_class = ALLOCNO_COVER_CLASS (a);
3271 ALLOCNO_ASSIGNED_P (a) = true;
3272 ALLOCNO_HARD_REGNO (a) = -1;
3273 if (hard_reg_set_subset_p (reg_class_contents[cover_class],
3274 conflict_hard_regs))
3276 mode = ALLOCNO_MODE (a);
3278 no_stack_reg_p = ALLOCNO_NO_STACK_REG_P (a);
3280 class_size = ira_class_hard_regs_num[cover_class];
3281 for (j = 0; j < class_size; j++)
3283 hard_regno = ira_class_hard_regs[cover_class][j];
3285 if (no_stack_reg_p && FIRST_STACK_REG <= hard_regno
3286 && hard_regno <= LAST_STACK_REG)
3289 if (!ira_hard_reg_not_in_set_p (hard_regno, mode, conflict_hard_regs)
3290 || (TEST_HARD_REG_BIT
3291 (prohibited_class_mode_regs[cover_class][mode], hard_regno)))
3293 ALLOCNO_HARD_REGNO (a) = hard_regno;
3294 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
3295 for (k = r->start; k <= r->finish; k++)
3296 IOR_HARD_REG_SET (used_hard_regs[k],
3297 ira_reg_mode_hard_regset[hard_regno][mode]);
3301 ira_free (sorted_allocnos);
3302 ira_free (used_hard_regs);
3303 ira_free (allocno_priorities);
3304 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
3305 ira_print_disposition (ira_dump_file);
3310 /* Entry function doing coloring. */
3315 ira_allocno_iterator ai;
3317 /* Setup updated costs. */
3318 FOR_EACH_ALLOCNO (a, ai)
3320 ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
3321 ALLOCNO_UPDATED_COVER_CLASS_COST (a) = ALLOCNO_COVER_CLASS_COST (a);
3323 if (ira_conflicts_p)