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"
36 #include "diagnostic-core.h"
41 #include "splay-tree.h"
44 /* This file contains code for regional graph coloring, spill/restore
45 code placement optimization, and code helping the reload pass to do
48 /* Bitmap of allocnos which should be colored. */
49 static bitmap coloring_allocno_bitmap;
51 /* Bitmap of allocnos which should be taken into account during
52 coloring. In general case it contains allocnos from
53 coloring_allocno_bitmap plus other already colored conflicting
55 static bitmap consideration_allocno_bitmap;
57 /* TRUE if we coalesced some allocnos. In other words, if we got
58 loops formed by members first_coalesced_allocno and
59 next_coalesced_allocno containing more one allocno. */
60 static bool allocno_coalesced_p;
62 /* Bitmap used to prevent a repeated allocno processing because of
64 static bitmap processed_coalesced_allocno_bitmap;
66 /* All allocnos sorted according their priorities. */
67 static ira_allocno_t *sorted_allocnos;
69 /* Vec representing the stack of allocnos used during coloring. */
70 static VEC(ira_allocno_t,heap) *allocno_stack_vec;
72 /* Array used to choose an allocno for spilling. */
73 static ira_allocno_t *allocnos_for_spilling;
75 /* Pool for splay tree nodes. */
76 static alloc_pool splay_tree_node_pool;
78 /* When an allocno is removed from the splay tree, it is put in the
79 following vector for subsequent inserting it into the splay tree
80 after putting all colorable allocnos onto the stack. The allocno
81 could be removed from and inserted to the splay tree every time
82 when its spilling priority is changed but such solution would be
83 more costly although simpler. */
84 static VEC(ira_allocno_t,heap) *removed_splay_allocno_vec;
88 /* This page contains functions used to find conflicts using allocno
91 /* Return TRUE if live ranges of allocnos A1 and A2 intersect. It is
92 used to find a conflict for new allocnos or allocnos with the
93 different cover classes. */
95 allocnos_have_intersected_live_ranges_p (ira_allocno_t a1, ira_allocno_t a2)
99 if (ALLOCNO_REG (a1) != NULL && ALLOCNO_REG (a2) != NULL
100 && (ORIGINAL_REGNO (ALLOCNO_REG (a1))
101 == ORIGINAL_REGNO (ALLOCNO_REG (a2))))
103 return ira_allocno_live_ranges_intersect_p (ALLOCNO_LIVE_RANGES (a1),
104 ALLOCNO_LIVE_RANGES (a2));
107 #ifdef ENABLE_IRA_CHECKING
109 /* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
110 intersect. This should be used when there is only one region.
111 Currently this is used during reload. */
113 pseudos_have_intersected_live_ranges_p (int regno1, int regno2)
115 ira_allocno_t a1, a2;
117 ira_assert (regno1 >= FIRST_PSEUDO_REGISTER
118 && regno2 >= FIRST_PSEUDO_REGISTER);
119 /* Reg info caclulated by dataflow infrastructure can be different
120 from one calculated by regclass. */
121 if ((a1 = ira_loop_tree_root->regno_allocno_map[regno1]) == NULL
122 || (a2 = ira_loop_tree_root->regno_allocno_map[regno2]) == NULL)
124 return allocnos_have_intersected_live_ranges_p (a1, a2);
131 /* This page contains functions used to choose hard registers for
134 /* Array whose element value is TRUE if the corresponding hard
135 register was already allocated for an allocno. */
136 static bool allocated_hardreg_p[FIRST_PSEUDO_REGISTER];
138 /* Describes one element in a queue of allocnos whose costs need to be
139 updated. Each allocno in the queue is known to have a cover class. */
140 struct update_cost_queue_elem
142 /* This element is in the queue iff CHECK == update_cost_check. */
145 /* COST_HOP_DIVISOR**N, where N is the length of the shortest path
146 connecting this allocno to the one being allocated. */
149 /* The next allocno in the queue, or null if this is the last element. */
153 /* The first element in a queue of allocnos whose copy costs need to be
154 updated. Null if the queue is empty. */
155 static ira_allocno_t update_cost_queue;
157 /* The last element in the queue described by update_cost_queue.
158 Not valid if update_cost_queue is null. */
159 static struct update_cost_queue_elem *update_cost_queue_tail;
161 /* A pool of elements in the queue described by update_cost_queue.
162 Elements are indexed by ALLOCNO_NUM. */
163 static struct update_cost_queue_elem *update_cost_queue_elems;
165 /* The current value of update_copy_cost call count. */
166 static int update_cost_check;
168 /* Allocate and initialize data necessary for function
169 update_copy_costs. */
171 initiate_cost_update (void)
175 size = ira_allocnos_num * sizeof (struct update_cost_queue_elem);
176 update_cost_queue_elems
177 = (struct update_cost_queue_elem *) ira_allocate (size);
178 memset (update_cost_queue_elems, 0, size);
179 update_cost_check = 0;
182 /* Deallocate data used by function update_copy_costs. */
184 finish_cost_update (void)
186 ira_free (update_cost_queue_elems);
189 /* When we traverse allocnos to update hard register costs, the cost
190 divisor will be multiplied by the following macro value for each
191 hop from given allocno to directly connected allocnos. */
192 #define COST_HOP_DIVISOR 4
194 /* Start a new cost-updating pass. */
196 start_update_cost (void)
199 update_cost_queue = NULL;
202 /* Add (ALLOCNO, DIVISOR) to the end of update_cost_queue,
203 unless ALLOCNO is already in the queue, or has no cover class. */
205 queue_update_cost (ira_allocno_t allocno, int divisor)
207 struct update_cost_queue_elem *elem;
209 elem = &update_cost_queue_elems[ALLOCNO_NUM (allocno)];
210 if (elem->check != update_cost_check
211 && ALLOCNO_COVER_CLASS (allocno) != NO_REGS)
213 elem->check = update_cost_check;
214 elem->divisor = divisor;
216 if (update_cost_queue == NULL)
217 update_cost_queue = allocno;
219 update_cost_queue_tail->next = allocno;
220 update_cost_queue_tail = elem;
224 /* Try to remove the first element from update_cost_queue. Return false
225 if the queue was empty, otherwise make (*ALLOCNO, *DIVISOR) describe
226 the removed element. */
228 get_next_update_cost (ira_allocno_t *allocno, int *divisor)
230 struct update_cost_queue_elem *elem;
232 if (update_cost_queue == NULL)
235 *allocno = update_cost_queue;
236 elem = &update_cost_queue_elems[ALLOCNO_NUM (*allocno)];
237 *divisor = elem->divisor;
238 update_cost_queue = elem->next;
242 /* Update the cost of allocnos to increase chances to remove some
243 copies as the result of subsequent assignment. */
245 update_copy_costs (ira_allocno_t allocno, bool decr_p)
247 int i, cost, update_cost, hard_regno, divisor;
248 enum machine_mode mode;
249 enum reg_class rclass, cover_class;
250 ira_allocno_t another_allocno;
251 ira_copy_t cp, next_cp;
253 hard_regno = ALLOCNO_HARD_REGNO (allocno);
254 ira_assert (hard_regno >= 0);
256 cover_class = ALLOCNO_COVER_CLASS (allocno);
257 if (cover_class == NO_REGS)
259 i = ira_class_hard_reg_index[cover_class][hard_regno];
261 rclass = REGNO_REG_CLASS (hard_regno);
263 start_update_cost ();
267 mode = ALLOCNO_MODE (allocno);
268 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
270 if (cp->first == allocno)
272 next_cp = cp->next_first_allocno_copy;
273 another_allocno = cp->second;
275 else if (cp->second == allocno)
277 next_cp = cp->next_second_allocno_copy;
278 another_allocno = cp->first;
283 cover_class = ALLOCNO_COVER_CLASS (another_allocno);
284 if (! ira_reg_classes_intersect_p[rclass][cover_class]
285 || ALLOCNO_ASSIGNED_P (another_allocno))
288 cost = (cp->second == allocno
289 ? ira_get_register_move_cost (mode, rclass, cover_class)
290 : ira_get_register_move_cost (mode, cover_class, rclass));
294 update_cost = cp->freq * cost / divisor;
295 if (update_cost == 0)
298 ira_allocate_and_set_or_copy_costs
299 (&ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno), cover_class,
300 ALLOCNO_UPDATED_COVER_CLASS_COST (another_allocno),
301 ALLOCNO_HARD_REG_COSTS (another_allocno));
302 ira_allocate_and_set_or_copy_costs
303 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
305 ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
306 i = ira_class_hard_reg_index[cover_class][hard_regno];
308 ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno)[i] += update_cost;
309 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno)[i]
312 queue_update_cost (another_allocno, divisor * COST_HOP_DIVISOR);
315 while (get_next_update_cost (&allocno, &divisor));
318 /* This function updates COSTS (decrease if DECR_P) for hard_registers
319 of COVER_CLASS by conflict costs of the unassigned allocnos
320 connected by copies with allocnos in update_cost_queue. This
321 update increases chances to remove some copies. */
323 update_conflict_hard_regno_costs (int *costs, enum reg_class cover_class,
326 int i, cost, class_size, freq, mult, div, divisor;
327 int index, hard_regno;
330 enum reg_class another_cover_class;
331 ira_allocno_t allocno, another_allocno;
332 ira_copy_t cp, next_cp;
334 while (get_next_update_cost (&allocno, &divisor))
335 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
337 if (cp->first == allocno)
339 next_cp = cp->next_first_allocno_copy;
340 another_allocno = cp->second;
342 else if (cp->second == allocno)
344 next_cp = cp->next_second_allocno_copy;
345 another_allocno = cp->first;
349 another_cover_class = ALLOCNO_COVER_CLASS (another_allocno);
350 if (! ira_reg_classes_intersect_p[cover_class][another_cover_class]
351 || ALLOCNO_ASSIGNED_P (another_allocno)
352 || ALLOCNO_MAY_BE_SPILLED_P (ALLOCNO_FIRST_COALESCED_ALLOCNO
355 class_size = ira_class_hard_regs_num[another_cover_class];
356 ira_allocate_and_copy_costs
357 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
359 ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
361 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno);
362 if (conflict_costs == NULL)
367 freq = ALLOCNO_FREQ (another_allocno);
370 div = freq * divisor;
372 for (i = class_size - 1; i >= 0; i--)
374 hard_regno = ira_class_hard_regs[another_cover_class][i];
375 ira_assert (hard_regno >= 0);
376 index = ira_class_hard_reg_index[cover_class][hard_regno];
379 cost = conflict_costs [i] * mult / div;
385 costs[index] += cost;
388 /* Probably 5 hops will be enough. */
390 && divisor <= (COST_HOP_DIVISOR
394 queue_update_cost (another_allocno, divisor * COST_HOP_DIVISOR);
398 /* Sort allocnos according to the profit of usage of a hard register
399 instead of memory for them. */
401 allocno_cost_compare_func (const void *v1p, const void *v2p)
403 ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
404 ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
407 c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_UPDATED_COVER_CLASS_COST (p1);
408 c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_UPDATED_COVER_CLASS_COST (p2);
412 /* If regs are equally good, sort by allocno numbers, so that the
413 results of qsort leave nothing to chance. */
414 return ALLOCNO_NUM (p1) - ALLOCNO_NUM (p2);
417 /* Print all allocnos coalesced with ALLOCNO. */
419 print_coalesced_allocno (ira_allocno_t allocno)
423 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
424 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
426 ira_print_expanded_allocno (a);
429 fprintf (ira_dump_file, "+");
433 /* Choose a hard register for ALLOCNO (or for all coalesced allocnos
434 represented by ALLOCNO). If RETRY_P is TRUE, it means that the
435 function called from function `ira_reassign_conflict_allocnos' and
436 `allocno_reload_assign'. This function implements the optimistic
437 coalescing too: if we failed to assign a hard register to set of
438 the coalesced allocnos, we put them onto the coloring stack for
439 subsequent separate assigning. */
441 assign_hard_reg (ira_allocno_t allocno, bool retry_p)
443 HARD_REG_SET conflicting_regs;
444 int i, j, k, hard_regno, best_hard_regno, class_size;
445 int cost, mem_cost, min_cost, full_cost, min_full_cost;
448 enum reg_class cover_class, conflict_cover_class;
449 enum machine_mode mode;
450 ira_allocno_t a, conflict_allocno;
451 ira_allocno_conflict_iterator aci;
452 static int costs[FIRST_PSEUDO_REGISTER], full_costs[FIRST_PSEUDO_REGISTER];
453 #ifndef HONOR_REG_ALLOC_ORDER
454 enum reg_class rclass;
461 ira_assert (! ALLOCNO_ASSIGNED_P (allocno));
462 cover_class = ALLOCNO_COVER_CLASS (allocno);
463 class_size = ira_class_hard_regs_num[cover_class];
464 mode = ALLOCNO_MODE (allocno);
465 CLEAR_HARD_REG_SET (conflicting_regs);
466 best_hard_regno = -1;
467 memset (full_costs, 0, sizeof (int) * class_size);
469 if (allocno_coalesced_p)
470 bitmap_clear (processed_coalesced_allocno_bitmap);
471 memset (costs, 0, sizeof (int) * class_size);
472 memset (full_costs, 0, sizeof (int) * class_size);
474 no_stack_reg_p = false;
476 start_update_cost ();
477 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
478 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
480 mem_cost += ALLOCNO_UPDATED_MEMORY_COST (a);
481 IOR_HARD_REG_SET (conflicting_regs,
482 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
483 ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
484 cover_class, ALLOCNO_HARD_REG_COSTS (a));
485 a_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
487 no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a);
489 cost = ALLOCNO_UPDATED_COVER_CLASS_COST (a);
490 for (i = 0; i < class_size; i++)
493 costs[i] += a_costs[i];
494 full_costs[i] += a_costs[i];
499 full_costs[i] += cost;
501 /* Take preferences of conflicting allocnos into account. */
502 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
503 /* Reload can give another class so we need to check all
505 if (retry_p || bitmap_bit_p (consideration_allocno_bitmap,
506 ALLOCNO_NUM (conflict_allocno)))
508 conflict_cover_class = ALLOCNO_COVER_CLASS (conflict_allocno);
509 ira_assert (ira_reg_classes_intersect_p
510 [cover_class][conflict_cover_class]);
511 if (allocno_coalesced_p)
513 if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
514 ALLOCNO_NUM (conflict_allocno)))
516 bitmap_set_bit (processed_coalesced_allocno_bitmap,
517 ALLOCNO_NUM (conflict_allocno));
519 if (ALLOCNO_ASSIGNED_P (conflict_allocno))
521 if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno)) >= 0
522 && ira_class_hard_reg_index[cover_class][hard_regno] >= 0)
526 ira_reg_mode_hard_regset
527 [hard_regno][ALLOCNO_MODE (conflict_allocno)]);
528 if (hard_reg_set_subset_p (reg_class_contents[cover_class],
533 else if (! ALLOCNO_MAY_BE_SPILLED_P (ALLOCNO_FIRST_COALESCED_ALLOCNO
536 ira_allocate_and_copy_costs
537 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno),
538 conflict_cover_class,
539 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_allocno));
541 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno);
542 if (conflict_costs != NULL)
543 for (j = class_size - 1; j >= 0; j--)
545 hard_regno = ira_class_hard_regs[cover_class][j];
546 ira_assert (hard_regno >= 0);
547 k = (ira_class_hard_reg_index
548 [conflict_cover_class][hard_regno]);
551 full_costs[j] -= conflict_costs[k];
553 queue_update_cost (conflict_allocno, COST_HOP_DIVISOR);
559 /* Take into account preferences of allocnos connected by copies to
560 the conflict allocnos. */
561 update_conflict_hard_regno_costs (full_costs, cover_class, true);
563 /* Take preferences of allocnos connected by copies into
565 start_update_cost ();
566 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
567 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
569 queue_update_cost (a, COST_HOP_DIVISOR);
573 update_conflict_hard_regno_costs (full_costs, cover_class, false);
574 min_cost = min_full_cost = INT_MAX;
575 /* We don't care about giving callee saved registers to allocnos no
576 living through calls because call clobbered registers are
577 allocated first (it is usual practice to put them first in
579 for (i = 0; i < class_size; i++)
581 hard_regno = ira_class_hard_regs[cover_class][i];
584 && FIRST_STACK_REG <= hard_regno && hard_regno <= LAST_STACK_REG)
587 if (! ira_hard_reg_not_in_set_p (hard_regno, mode, conflicting_regs)
588 || TEST_HARD_REG_BIT (prohibited_class_mode_regs[cover_class][mode],
592 full_cost = full_costs[i];
593 #ifndef HONOR_REG_ALLOC_ORDER
594 if (! allocated_hardreg_p[hard_regno]
595 && ira_hard_reg_not_in_set_p (hard_regno, mode, call_used_reg_set))
596 /* We need to save/restore the hard register in
597 epilogue/prologue. Therefore we increase the cost. */
599 /* ??? If only part is call clobbered. */
600 rclass = REGNO_REG_CLASS (hard_regno);
601 add_cost = (ira_memory_move_cost[mode][rclass][0]
602 + ira_memory_move_cost[mode][rclass][1] - 1);
604 full_cost += add_cost;
609 if (min_full_cost > full_cost)
611 min_full_cost = full_cost;
612 best_hard_regno = hard_regno;
613 ira_assert (hard_regno >= 0);
616 if (min_full_cost > mem_cost)
618 if (! retry_p && internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
619 fprintf (ira_dump_file, "(memory is more profitable %d vs %d) ",
620 mem_cost, min_full_cost);
621 best_hard_regno = -1;
624 if (flag_ira_algorithm != IRA_ALGORITHM_PRIORITY
625 && best_hard_regno < 0
626 && ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno) != allocno)
628 for (j = 0, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
629 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
631 ira_assert (! ALLOCNO_IN_GRAPH_P (a));
632 sorted_allocnos[j++] = a;
636 qsort (sorted_allocnos, j, sizeof (ira_allocno_t),
637 allocno_cost_compare_func);
638 for (i = 0; i < j; i++)
640 a = sorted_allocnos[i];
641 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
642 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
643 VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, a);
644 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
646 fprintf (ira_dump_file, " Pushing");
647 print_coalesced_allocno (a);
648 fprintf (ira_dump_file, "\n");
653 if (best_hard_regno >= 0)
654 allocated_hardreg_p[best_hard_regno] = true;
655 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
656 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
658 ALLOCNO_HARD_REGNO (a) = best_hard_regno;
659 ALLOCNO_ASSIGNED_P (a) = true;
660 if (best_hard_regno >= 0)
661 update_copy_costs (a, true);
662 ira_assert (ALLOCNO_COVER_CLASS (a) == cover_class);
663 /* We don't need updated costs anymore: */
664 ira_free_allocno_updated_costs (a);
668 return best_hard_regno >= 0;
673 /* This page contains the allocator based on the Chaitin-Briggs algorithm. */
675 /* Bucket of allocnos that can colored currently without spilling. */
676 static ira_allocno_t colorable_allocno_bucket;
678 /* Bucket of allocnos that might be not colored currently without
680 static ira_allocno_t uncolorable_allocno_bucket;
682 /* Each element of the array contains the current number of allocnos
683 of given *cover* class in the uncolorable_bucket. */
684 static int uncolorable_allocnos_num[N_REG_CLASSES];
686 /* Return the current spill priority of allocno A. The less the
687 number, the more preferable the allocno for spilling. */
689 allocno_spill_priority (ira_allocno_t a)
691 return (ALLOCNO_TEMP (a)
692 / (ALLOCNO_LEFT_CONFLICTS_SIZE (a)
693 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a)][ALLOCNO_MODE (a)]
697 /* Add ALLOCNO to bucket *BUCKET_PTR. ALLOCNO should be not in a bucket
700 add_allocno_to_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
702 ira_allocno_t first_allocno;
703 enum reg_class cover_class;
705 if (bucket_ptr == &uncolorable_allocno_bucket
706 && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
708 uncolorable_allocnos_num[cover_class]++;
709 ira_assert (uncolorable_allocnos_num[cover_class] > 0);
711 first_allocno = *bucket_ptr;
712 ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno) = first_allocno;
713 ALLOCNO_PREV_BUCKET_ALLOCNO (allocno) = NULL;
714 if (first_allocno != NULL)
715 ALLOCNO_PREV_BUCKET_ALLOCNO (first_allocno) = allocno;
716 *bucket_ptr = allocno;
719 /* The function returns frequency and number of available hard
720 registers for allocnos coalesced with ALLOCNO. */
722 get_coalesced_allocnos_attributes (ira_allocno_t allocno, int *freq, int *num)
728 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
729 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
731 *freq += ALLOCNO_FREQ (a);
732 *num += ALLOCNO_AVAILABLE_REGS_NUM (a);
738 /* Compare two allocnos to define which allocno should be pushed first
739 into the coloring stack. If the return is a negative number, the
740 allocno given by the first parameter will be pushed first. In this
741 case such allocno has less priority than the second one and the
742 hard register will be assigned to it after assignment to the second
743 one. As the result of such assignment order, the second allocno
744 has a better chance to get the best hard register. */
746 bucket_allocno_compare_func (const void *v1p, const void *v2p)
748 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
749 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
750 int diff, a1_freq, a2_freq, a1_num, a2_num;
752 if ((diff = (int) ALLOCNO_COVER_CLASS (a2) - ALLOCNO_COVER_CLASS (a1)) != 0)
754 get_coalesced_allocnos_attributes (a1, &a1_freq, &a1_num);
755 get_coalesced_allocnos_attributes (a2, &a2_freq, &a2_num);
756 if ((diff = a2_num - a1_num) != 0)
758 else if ((diff = a1_freq - a2_freq) != 0)
760 return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
763 /* Sort bucket *BUCKET_PTR and return the result through
766 sort_bucket (ira_allocno_t *bucket_ptr)
768 ira_allocno_t a, head;
771 for (n = 0, a = *bucket_ptr; a != NULL; a = ALLOCNO_NEXT_BUCKET_ALLOCNO (a))
772 sorted_allocnos[n++] = a;
775 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
776 bucket_allocno_compare_func);
778 for (n--; n >= 0; n--)
780 a = sorted_allocnos[n];
781 ALLOCNO_NEXT_BUCKET_ALLOCNO (a) = head;
782 ALLOCNO_PREV_BUCKET_ALLOCNO (a) = NULL;
784 ALLOCNO_PREV_BUCKET_ALLOCNO (head) = a;
790 /* Add ALLOCNO to bucket *BUCKET_PTR maintaining the order according
791 their priority. ALLOCNO should be not in a bucket before the
794 add_allocno_to_ordered_bucket (ira_allocno_t allocno,
795 ira_allocno_t *bucket_ptr)
797 ira_allocno_t before, after;
798 enum reg_class cover_class;
800 if (bucket_ptr == &uncolorable_allocno_bucket
801 && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
803 uncolorable_allocnos_num[cover_class]++;
804 ira_assert (uncolorable_allocnos_num[cover_class] > 0);
806 for (before = *bucket_ptr, after = NULL;
808 after = before, before = ALLOCNO_NEXT_BUCKET_ALLOCNO (before))
809 if (bucket_allocno_compare_func (&allocno, &before) < 0)
811 ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno) = before;
812 ALLOCNO_PREV_BUCKET_ALLOCNO (allocno) = after;
814 *bucket_ptr = allocno;
816 ALLOCNO_NEXT_BUCKET_ALLOCNO (after) = allocno;
818 ALLOCNO_PREV_BUCKET_ALLOCNO (before) = allocno;
821 /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
824 delete_allocno_from_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
826 ira_allocno_t prev_allocno, next_allocno;
827 enum reg_class cover_class;
829 if (bucket_ptr == &uncolorable_allocno_bucket
830 && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
832 uncolorable_allocnos_num[cover_class]--;
833 ira_assert (uncolorable_allocnos_num[cover_class] >= 0);
835 prev_allocno = ALLOCNO_PREV_BUCKET_ALLOCNO (allocno);
836 next_allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno);
837 if (prev_allocno != NULL)
838 ALLOCNO_NEXT_BUCKET_ALLOCNO (prev_allocno) = next_allocno;
841 ira_assert (*bucket_ptr == allocno);
842 *bucket_ptr = next_allocno;
844 if (next_allocno != NULL)
845 ALLOCNO_PREV_BUCKET_ALLOCNO (next_allocno) = prev_allocno;
848 /* Splay tree for each cover class. The trees are indexed by the
849 corresponding cover classes. Splay trees contain uncolorable
851 static splay_tree uncolorable_allocnos_splay_tree[N_REG_CLASSES];
853 /* If the following macro is TRUE, splay tree is used to choose an
854 allocno of the corresponding cover class for spilling. When the
855 number uncolorable allocnos of given cover class decreases to some
856 threshold, linear array search is used to find the best allocno for
857 spilling. This threshold is actually pretty big because, although
858 splay trees asymptotically is much faster, each splay tree
859 operation is sufficiently costly especially taking cache locality
861 #define USE_SPLAY_P(CLASS) (uncolorable_allocnos_num[CLASS] > 4000)
863 /* Put ALLOCNO onto the coloring stack without removing it from its
864 bucket. Pushing allocno to the coloring stack can result in moving
865 conflicting allocnos from the uncolorable bucket to the colorable
868 push_allocno_to_stack (ira_allocno_t allocno)
870 int left_conflicts_size, conflict_size, size;
871 ira_allocno_t a, conflict_allocno;
872 enum reg_class cover_class;
873 ira_allocno_conflict_iterator aci;
875 ALLOCNO_IN_GRAPH_P (allocno) = false;
876 VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, allocno);
877 cover_class = ALLOCNO_COVER_CLASS (allocno);
878 if (cover_class == NO_REGS)
880 size = ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)];
881 if (allocno_coalesced_p)
882 bitmap_clear (processed_coalesced_allocno_bitmap);
883 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
884 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
886 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
888 conflict_allocno = ALLOCNO_FIRST_COALESCED_ALLOCNO (conflict_allocno);
889 if (bitmap_bit_p (coloring_allocno_bitmap,
890 ALLOCNO_NUM (conflict_allocno)))
892 ira_assert (cover_class
893 == ALLOCNO_COVER_CLASS (conflict_allocno));
894 if (allocno_coalesced_p)
896 if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
897 ALLOCNO_NUM (conflict_allocno)))
899 bitmap_set_bit (processed_coalesced_allocno_bitmap,
900 ALLOCNO_NUM (conflict_allocno));
902 if (ALLOCNO_IN_GRAPH_P (conflict_allocno)
903 && ! ALLOCNO_ASSIGNED_P (conflict_allocno))
906 = ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno);
908 = (ira_reg_class_nregs
909 [cover_class][ALLOCNO_MODE (conflict_allocno)]);
911 (ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno) >= size);
912 if (left_conflicts_size + conflict_size
913 <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno))
915 ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno) -= size;
919 = ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno) - size;
920 if (uncolorable_allocnos_splay_tree[cover_class] != NULL
921 && !ALLOCNO_SPLAY_REMOVED_P (conflict_allocno)
922 && USE_SPLAY_P (cover_class))
926 (uncolorable_allocnos_splay_tree[cover_class],
927 (splay_tree_key) conflict_allocno) != NULL);
929 (uncolorable_allocnos_splay_tree[cover_class],
930 (splay_tree_key) conflict_allocno);
931 ALLOCNO_SPLAY_REMOVED_P (conflict_allocno) = true;
932 VEC_safe_push (ira_allocno_t, heap,
933 removed_splay_allocno_vec,
936 ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno)
937 = left_conflicts_size;
938 if (left_conflicts_size + conflict_size
939 <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno))
941 delete_allocno_from_bucket
942 (conflict_allocno, &uncolorable_allocno_bucket);
943 add_allocno_to_ordered_bucket
944 (conflict_allocno, &colorable_allocno_bucket);
954 /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
955 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
957 remove_allocno_from_bucket_and_push (ira_allocno_t allocno, bool colorable_p)
959 enum reg_class cover_class;
962 delete_allocno_from_bucket (allocno, &colorable_allocno_bucket);
964 delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
965 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
967 fprintf (ira_dump_file, " Pushing");
968 print_coalesced_allocno (allocno);
970 fprintf (ira_dump_file, "\n");
972 fprintf (ira_dump_file, "(potential spill: %spri=%d, cost=%d)\n",
973 ALLOCNO_BAD_SPILL_P (allocno) ? "bad spill, " : "",
974 allocno_spill_priority (allocno), ALLOCNO_TEMP (allocno));
976 cover_class = ALLOCNO_COVER_CLASS (allocno);
977 ira_assert ((colorable_p
978 && (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno)
979 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)]
980 <= ALLOCNO_AVAILABLE_REGS_NUM (allocno)))
982 && (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno)
983 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE
985 > ALLOCNO_AVAILABLE_REGS_NUM (allocno))));
987 ALLOCNO_MAY_BE_SPILLED_P (allocno) = true;
988 push_allocno_to_stack (allocno);
991 /* Put all allocnos from colorable bucket onto the coloring stack. */
993 push_only_colorable (void)
995 sort_bucket (&colorable_allocno_bucket);
996 for (;colorable_allocno_bucket != NULL;)
997 remove_allocno_from_bucket_and_push (colorable_allocno_bucket, true);
1000 /* Puts ALLOCNO chosen for potential spilling onto the coloring
1003 push_allocno_to_spill (ira_allocno_t allocno)
1005 delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
1006 ALLOCNO_MAY_BE_SPILLED_P (allocno) = true;
1007 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1008 fprintf (ira_dump_file, " Pushing p%d(%d) (spill for NO_REGS)\n",
1009 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno));
1010 push_allocno_to_stack (allocno);
1013 /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
1014 loop given by its LOOP_NODE. */
1016 ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p)
1021 VEC (edge, heap) *edges;
1023 ira_assert (loop_node->loop != NULL
1024 && (regno < 0 || regno >= FIRST_PSEUDO_REGISTER));
1028 FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
1029 if (e->src != loop_node->loop->latch
1031 || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
1032 && bitmap_bit_p (DF_LR_IN (e->dest), regno))))
1033 freq += EDGE_FREQUENCY (e);
1037 edges = get_loop_exit_edges (loop_node->loop);
1038 for (i = 0; VEC_iterate (edge, edges, i, e); i++)
1040 || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
1041 && bitmap_bit_p (DF_LR_IN (e->dest), regno)))
1042 freq += EDGE_FREQUENCY (e);
1043 VEC_free (edge, heap, edges);
1046 return REG_FREQ_FROM_EDGE_FREQ (freq);
1049 /* Calculate and return the cost of putting allocno A into memory. */
1051 calculate_allocno_spill_cost (ira_allocno_t a)
1054 enum machine_mode mode;
1055 enum reg_class rclass;
1056 ira_allocno_t parent_allocno;
1057 ira_loop_tree_node_t parent_node, loop_node;
1059 regno = ALLOCNO_REGNO (a);
1060 cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_UPDATED_COVER_CLASS_COST (a);
1061 if (ALLOCNO_CAP (a) != NULL)
1063 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
1064 if ((parent_node = loop_node->parent) == NULL)
1066 if ((parent_allocno = parent_node->regno_allocno_map[regno]) == NULL)
1068 mode = ALLOCNO_MODE (a);
1069 rclass = ALLOCNO_COVER_CLASS (a);
1070 if (ALLOCNO_HARD_REGNO (parent_allocno) < 0)
1071 cost -= (ira_memory_move_cost[mode][rclass][0]
1072 * ira_loop_edge_freq (loop_node, regno, true)
1073 + ira_memory_move_cost[mode][rclass][1]
1074 * ira_loop_edge_freq (loop_node, regno, false));
1076 cost += ((ira_memory_move_cost[mode][rclass][1]
1077 * ira_loop_edge_freq (loop_node, regno, true)
1078 + ira_memory_move_cost[mode][rclass][0]
1079 * ira_loop_edge_freq (loop_node, regno, false))
1080 - (ira_get_register_move_cost (mode, rclass, rclass)
1081 * (ira_loop_edge_freq (loop_node, regno, false)
1082 + ira_loop_edge_freq (loop_node, regno, true))));
1086 /* Compare keys in the splay tree used to choose best allocno for
1087 spilling. The best allocno has the minimal key. */
1089 allocno_spill_priority_compare (splay_tree_key k1, splay_tree_key k2)
1091 int pri1, pri2, diff;
1092 ira_allocno_t a1 = (ira_allocno_t) k1, a2 = (ira_allocno_t) k2;
1094 pri1 = (ALLOCNO_TEMP (a1)
1095 / (ALLOCNO_LEFT_CONFLICTS_SIZE (a1)
1096 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a1)][ALLOCNO_MODE (a1)]
1098 pri2 = (ALLOCNO_TEMP (a2)
1099 / (ALLOCNO_LEFT_CONFLICTS_SIZE (a2)
1100 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a2)][ALLOCNO_MODE (a2)]
1102 if ((diff = pri1 - pri2) != 0)
1104 if ((diff = ALLOCNO_TEMP (a1) - ALLOCNO_TEMP (a2)) != 0)
1106 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
1109 /* Allocate data of SIZE for the splay trees. We allocate only spay
1110 tree roots or splay tree nodes. If you change this, please rewrite
1113 splay_tree_allocate (int size, void *data ATTRIBUTE_UNUSED)
1115 if (size != sizeof (struct splay_tree_node_s))
1116 return ira_allocate (size);
1117 return pool_alloc (splay_tree_node_pool);
1120 /* Free data NODE for the splay trees. We allocate and free only spay
1121 tree roots or splay tree nodes. If you change this, please rewrite
1124 splay_tree_free (void *node, void *data ATTRIBUTE_UNUSED)
1127 enum reg_class cover_class;
1129 for (i = 0; i < ira_reg_class_cover_size; i++)
1131 cover_class = ira_reg_class_cover[i];
1132 if (node == uncolorable_allocnos_splay_tree[cover_class])
1138 pool_free (splay_tree_node_pool, node);
1141 /* Push allocnos to the coloring stack. The order of allocnos in the
1142 stack defines the order for the subsequent coloring. */
1144 push_allocnos_to_stack (void)
1146 ira_allocno_t allocno, a, i_allocno, *allocno_vec;
1147 enum reg_class cover_class, rclass;
1148 int allocno_pri, i_allocno_pri, allocno_cost, i_allocno_cost;
1149 int i, j, num, cover_class_allocnos_num[N_REG_CLASSES];
1150 ira_allocno_t *cover_class_allocnos[N_REG_CLASSES];
1154 VEC_truncate(ira_allocno_t, removed_splay_allocno_vec, 0);
1155 for (i = 0; i < ira_reg_class_cover_size; i++)
1157 cover_class = ira_reg_class_cover[i];
1158 cover_class_allocnos_num[cover_class] = 0;
1159 cover_class_allocnos[cover_class] = NULL;
1160 uncolorable_allocnos_splay_tree[cover_class] = NULL;
1162 /* Calculate uncolorable allocno spill costs. */
1163 for (allocno = uncolorable_allocno_bucket;
1165 allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno))
1166 if ((cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
1168 cover_class_allocnos_num[cover_class]++;
1170 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1171 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1173 cost += calculate_allocno_spill_cost (a);
1177 /* ??? Remove cost of copies between the coalesced
1179 ALLOCNO_TEMP (allocno) = cost;
1181 /* Define place where to put uncolorable allocnos of the same cover
1183 for (num = i = 0; i < ira_reg_class_cover_size; i++)
1185 cover_class = ira_reg_class_cover[i];
1186 ira_assert (cover_class_allocnos_num[cover_class]
1187 == uncolorable_allocnos_num[cover_class]);
1188 if (cover_class_allocnos_num[cover_class] != 0)
1190 cover_class_allocnos[cover_class] = allocnos_for_spilling + num;
1191 num += cover_class_allocnos_num[cover_class];
1192 cover_class_allocnos_num[cover_class] = 0;
1194 if (USE_SPLAY_P (cover_class))
1195 uncolorable_allocnos_splay_tree[cover_class]
1196 = splay_tree_new_with_allocator (allocno_spill_priority_compare,
1197 NULL, NULL, splay_tree_allocate,
1198 splay_tree_free, NULL);
1200 ira_assert (num <= ira_allocnos_num);
1201 /* Collect uncolorable allocnos of each cover class. */
1202 for (allocno = uncolorable_allocno_bucket;
1204 allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno))
1205 if ((cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
1207 cover_class_allocnos
1208 [cover_class][cover_class_allocnos_num[cover_class]++] = allocno;
1209 if (uncolorable_allocnos_splay_tree[cover_class] != NULL)
1210 splay_tree_insert (uncolorable_allocnos_splay_tree[cover_class],
1211 (splay_tree_key) allocno,
1212 (splay_tree_value) allocno);
1216 push_only_colorable ();
1217 allocno = uncolorable_allocno_bucket;
1218 if (allocno == NULL)
1220 cover_class = ALLOCNO_COVER_CLASS (allocno);
1221 if (cover_class == NO_REGS)
1223 push_allocno_to_spill (allocno);
1226 /* Potential spilling. */
1228 (ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)] > 0);
1229 if (USE_SPLAY_P (cover_class))
1231 for (;VEC_length (ira_allocno_t, removed_splay_allocno_vec) != 0;)
1233 allocno = VEC_pop (ira_allocno_t, removed_splay_allocno_vec);
1234 ALLOCNO_SPLAY_REMOVED_P (allocno) = false;
1235 rclass = ALLOCNO_COVER_CLASS (allocno);
1236 if (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno)
1237 + ira_reg_class_nregs [rclass][ALLOCNO_MODE (allocno)]
1238 > ALLOCNO_AVAILABLE_REGS_NUM (allocno))
1240 (uncolorable_allocnos_splay_tree[rclass],
1241 (splay_tree_key) allocno, (splay_tree_value) allocno);
1243 allocno = ((ira_allocno_t)
1245 (uncolorable_allocnos_splay_tree[cover_class])->key);
1246 splay_tree_remove (uncolorable_allocnos_splay_tree[cover_class],
1247 (splay_tree_key) allocno);
1251 num = cover_class_allocnos_num[cover_class];
1252 ira_assert (num > 0);
1253 allocno_vec = cover_class_allocnos[cover_class];
1255 allocno_pri = allocno_cost = 0;
1256 /* Sort uncolorable allocno to find the one with the lowest
1258 for (i = 0, j = num - 1; i <= j;)
1260 i_allocno = allocno_vec[i];
1261 if (! ALLOCNO_IN_GRAPH_P (i_allocno)
1262 && ALLOCNO_IN_GRAPH_P (allocno_vec[j]))
1264 i_allocno = allocno_vec[j];
1265 allocno_vec[j] = allocno_vec[i];
1266 allocno_vec[i] = i_allocno;
1268 if (ALLOCNO_IN_GRAPH_P (i_allocno))
1271 ira_assert (ALLOCNO_TEMP (i_allocno) != INT_MAX);
1272 i_allocno_cost = ALLOCNO_TEMP (i_allocno);
1273 i_allocno_pri = allocno_spill_priority (i_allocno);
1275 || (! ALLOCNO_BAD_SPILL_P (i_allocno)
1276 && ALLOCNO_BAD_SPILL_P (allocno))
1277 || (! (ALLOCNO_BAD_SPILL_P (i_allocno)
1278 && ! ALLOCNO_BAD_SPILL_P (allocno))
1279 && (allocno_pri > i_allocno_pri
1280 || (allocno_pri == i_allocno_pri
1281 && (allocno_cost > i_allocno_cost
1282 || (allocno_cost == i_allocno_cost
1283 && (ALLOCNO_NUM (allocno)
1284 > ALLOCNO_NUM (i_allocno))))))))
1286 allocno = i_allocno;
1287 allocno_cost = i_allocno_cost;
1288 allocno_pri = i_allocno_pri;
1291 if (! ALLOCNO_IN_GRAPH_P (allocno_vec[j]))
1294 ira_assert (allocno != NULL && j >= 0);
1295 cover_class_allocnos_num[cover_class] = j + 1;
1297 ira_assert (ALLOCNO_IN_GRAPH_P (allocno)
1298 && ALLOCNO_COVER_CLASS (allocno) == cover_class
1299 && (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno)
1300 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE
1302 > ALLOCNO_AVAILABLE_REGS_NUM (allocno)));
1303 remove_allocno_from_bucket_and_push (allocno, false);
1305 ira_assert (colorable_allocno_bucket == NULL
1306 && uncolorable_allocno_bucket == NULL);
1307 for (i = 0; i < ira_reg_class_cover_size; i++)
1309 cover_class = ira_reg_class_cover[i];
1310 ira_assert (uncolorable_allocnos_num[cover_class] == 0);
1311 if (uncolorable_allocnos_splay_tree[cover_class] != NULL)
1312 splay_tree_delete (uncolorable_allocnos_splay_tree[cover_class]);
1316 /* Pop the coloring stack and assign hard registers to the popped
1319 pop_allocnos_from_stack (void)
1321 ira_allocno_t allocno;
1322 enum reg_class cover_class;
1324 for (;VEC_length (ira_allocno_t, allocno_stack_vec) != 0;)
1326 allocno = VEC_pop (ira_allocno_t, allocno_stack_vec);
1327 cover_class = ALLOCNO_COVER_CLASS (allocno);
1328 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1330 fprintf (ira_dump_file, " Popping");
1331 print_coalesced_allocno (allocno);
1332 fprintf (ira_dump_file, " -- ");
1334 if (cover_class == NO_REGS)
1336 ALLOCNO_HARD_REGNO (allocno) = -1;
1337 ALLOCNO_ASSIGNED_P (allocno) = true;
1338 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno) == NULL);
1340 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno) == NULL);
1341 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1342 fprintf (ira_dump_file, "assign memory\n");
1344 else if (assign_hard_reg (allocno, false))
1346 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1347 fprintf (ira_dump_file, "assign reg %d\n",
1348 ALLOCNO_HARD_REGNO (allocno));
1350 else if (ALLOCNO_ASSIGNED_P (allocno))
1352 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1353 fprintf (ira_dump_file, "spill\n");
1355 ALLOCNO_IN_GRAPH_P (allocno) = true;
1359 /* Set up number of available hard registers for ALLOCNO. */
1361 setup_allocno_available_regs_num (ira_allocno_t allocno)
1363 int i, n, hard_regs_num, hard_regno;
1364 enum machine_mode mode;
1365 enum reg_class cover_class;
1367 HARD_REG_SET temp_set;
1369 cover_class = ALLOCNO_COVER_CLASS (allocno);
1370 ALLOCNO_AVAILABLE_REGS_NUM (allocno) = ira_available_class_regs[cover_class];
1371 if (cover_class == NO_REGS)
1373 CLEAR_HARD_REG_SET (temp_set);
1374 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) == allocno);
1375 hard_regs_num = ira_class_hard_regs_num[cover_class];
1376 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1377 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1379 IOR_HARD_REG_SET (temp_set, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1383 mode = ALLOCNO_MODE (allocno);
1384 for (n = 0, i = hard_regs_num - 1; i >= 0; i--)
1386 hard_regno = ira_class_hard_regs[cover_class][i];
1387 if (TEST_HARD_REG_BIT (temp_set, hard_regno)
1388 || TEST_HARD_REG_BIT (prohibited_class_mode_regs[cover_class][mode],
1392 if (internal_flag_ira_verbose > 2 && n > 0 && ira_dump_file != NULL)
1393 fprintf (ira_dump_file, " Reg %d of %s has %d regs less\n",
1394 ALLOCNO_REGNO (allocno), reg_class_names[cover_class], n);
1395 ALLOCNO_AVAILABLE_REGS_NUM (allocno) -= n;
1398 /* Set up ALLOCNO_LEFT_CONFLICTS_SIZE for ALLOCNO. */
1400 setup_allocno_left_conflicts_size (ira_allocno_t allocno)
1402 int i, hard_regs_num, hard_regno, conflict_allocnos_size;
1403 ira_allocno_t a, conflict_allocno;
1404 enum reg_class cover_class;
1405 HARD_REG_SET temp_set;
1406 ira_allocno_conflict_iterator aci;
1408 cover_class = ALLOCNO_COVER_CLASS (allocno);
1409 hard_regs_num = ira_class_hard_regs_num[cover_class];
1410 CLEAR_HARD_REG_SET (temp_set);
1411 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) == allocno);
1412 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1413 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1415 IOR_HARD_REG_SET (temp_set, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1419 AND_HARD_REG_SET (temp_set, reg_class_contents[cover_class]);
1420 AND_COMPL_HARD_REG_SET (temp_set, ira_no_alloc_regs);
1421 conflict_allocnos_size = 0;
1422 if (! hard_reg_set_empty_p (temp_set))
1423 for (i = 0; i < (int) hard_regs_num; i++)
1425 hard_regno = ira_class_hard_regs[cover_class][i];
1426 if (TEST_HARD_REG_BIT (temp_set, hard_regno))
1428 conflict_allocnos_size++;
1429 CLEAR_HARD_REG_BIT (temp_set, hard_regno);
1430 if (hard_reg_set_empty_p (temp_set))
1434 CLEAR_HARD_REG_SET (temp_set);
1435 if (allocno_coalesced_p)
1436 bitmap_clear (processed_coalesced_allocno_bitmap);
1437 if (cover_class != NO_REGS)
1438 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1439 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1441 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
1444 = ALLOCNO_FIRST_COALESCED_ALLOCNO (conflict_allocno);
1445 if (bitmap_bit_p (consideration_allocno_bitmap,
1446 ALLOCNO_NUM (conflict_allocno)))
1448 ira_assert (cover_class
1449 == ALLOCNO_COVER_CLASS (conflict_allocno));
1450 if (allocno_coalesced_p)
1452 if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
1453 ALLOCNO_NUM (conflict_allocno)))
1455 bitmap_set_bit (processed_coalesced_allocno_bitmap,
1456 ALLOCNO_NUM (conflict_allocno));
1458 if (! ALLOCNO_ASSIGNED_P (conflict_allocno))
1459 conflict_allocnos_size
1460 += (ira_reg_class_nregs
1461 [cover_class][ALLOCNO_MODE (conflict_allocno)]);
1462 else if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno))
1465 int last = (hard_regno
1467 [hard_regno][ALLOCNO_MODE (conflict_allocno)]);
1469 while (hard_regno < last)
1471 if (! TEST_HARD_REG_BIT (temp_set, hard_regno))
1473 conflict_allocnos_size++;
1474 SET_HARD_REG_BIT (temp_set, hard_regno);
1484 ALLOCNO_LEFT_CONFLICTS_SIZE (allocno) = conflict_allocnos_size;
1487 /* Put ALLOCNO in a bucket corresponding to its number and size of its
1488 conflicting allocnos and hard registers. */
1490 put_allocno_into_bucket (ira_allocno_t allocno)
1492 enum reg_class cover_class;
1494 cover_class = ALLOCNO_COVER_CLASS (allocno);
1495 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
1497 ALLOCNO_IN_GRAPH_P (allocno) = true;
1498 setup_allocno_left_conflicts_size (allocno);
1499 setup_allocno_available_regs_num (allocno);
1500 if (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno)
1501 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)]
1502 <= ALLOCNO_AVAILABLE_REGS_NUM (allocno))
1503 add_allocno_to_bucket (allocno, &colorable_allocno_bucket);
1505 add_allocno_to_bucket (allocno, &uncolorable_allocno_bucket);
1508 /* The function is used to sort allocnos according to their execution
1511 copy_freq_compare_func (const void *v1p, const void *v2p)
1513 ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p;
1521 /* If freqencies are equal, sort by copies, so that the results of
1522 qsort leave nothing to chance. */
1523 return cp1->num - cp2->num;
1526 /* Merge two sets of coalesced allocnos given correspondingly by
1527 allocnos A1 and A2 (more accurately merging A2 set into A1
1530 merge_allocnos (ira_allocno_t a1, ira_allocno_t a2)
1532 ira_allocno_t a, first, last, next;
1534 first = ALLOCNO_FIRST_COALESCED_ALLOCNO (a1);
1535 if (first == ALLOCNO_FIRST_COALESCED_ALLOCNO (a2))
1537 for (last = a2, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
1538 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1540 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = first;
1545 next = ALLOCNO_NEXT_COALESCED_ALLOCNO (first);
1546 ALLOCNO_NEXT_COALESCED_ALLOCNO (first) = a2;
1547 ALLOCNO_NEXT_COALESCED_ALLOCNO (last) = next;
1550 /* Return TRUE if there are conflicting allocnos from two sets of
1551 coalesced allocnos given correspondingly by allocnos A1 and A2. If
1552 RELOAD_P is TRUE, we use live ranges to find conflicts because
1553 conflicts are represented only for allocnos of the same cover class
1554 and during the reload pass we coalesce allocnos for sharing stack
1557 coalesced_allocno_conflict_p (ira_allocno_t a1, ira_allocno_t a2,
1560 ira_allocno_t a, conflict_allocno;
1561 ira_allocno_conflict_iterator aci;
1563 if (allocno_coalesced_p)
1565 bitmap_clear (processed_coalesced_allocno_bitmap);
1566 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
1567 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1569 bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a));
1574 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
1575 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1579 for (conflict_allocno = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
1581 = ALLOCNO_NEXT_COALESCED_ALLOCNO (conflict_allocno))
1583 if (allocnos_have_intersected_live_ranges_p (a,
1586 if (conflict_allocno == a1)
1592 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
1593 if (conflict_allocno == a1
1594 || (allocno_coalesced_p
1595 && bitmap_bit_p (processed_coalesced_allocno_bitmap,
1596 ALLOCNO_NUM (conflict_allocno))))
1605 /* The major function for aggressive allocno coalescing. For the
1606 reload pass (RELOAD_P) we coalesce only spilled allocnos. If some
1607 allocnos have been coalesced, we set up flag
1608 allocno_coalesced_p. */
1610 coalesce_allocnos (bool reload_p)
1613 ira_copy_t cp, next_cp, *sorted_copies;
1614 enum reg_class cover_class;
1615 enum machine_mode mode;
1617 int i, n, cp_num, regno;
1620 sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num
1621 * sizeof (ira_copy_t));
1623 /* Collect copies. */
1624 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
1626 a = ira_allocnos[j];
1627 regno = ALLOCNO_REGNO (a);
1628 if ((! reload_p && ALLOCNO_ASSIGNED_P (a))
1630 && (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0
1631 || (regno < ira_reg_equiv_len
1632 && (ira_reg_equiv_const[regno] != NULL_RTX
1633 || ira_reg_equiv_invariant_p[regno])))))
1635 cover_class = ALLOCNO_COVER_CLASS (a);
1636 mode = ALLOCNO_MODE (a);
1637 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
1641 next_cp = cp->next_first_allocno_copy;
1642 regno = ALLOCNO_REGNO (cp->second);
1643 /* For priority coloring we coalesce allocnos only with
1644 the same cover class not with intersected cover
1645 classes as it were possible. It is done for
1648 || (ALLOCNO_COVER_CLASS (cp->second) == cover_class
1649 && ALLOCNO_MODE (cp->second) == mode))
1650 && (cp->insn != NULL || cp->constraint_p)
1651 && ((! reload_p && ! ALLOCNO_ASSIGNED_P (cp->second))
1653 && ALLOCNO_ASSIGNED_P (cp->second)
1654 && ALLOCNO_HARD_REGNO (cp->second) < 0
1655 && (regno >= ira_reg_equiv_len
1656 || (! ira_reg_equiv_invariant_p[regno]
1657 && ira_reg_equiv_const[regno] == NULL_RTX)))))
1658 sorted_copies[cp_num++] = cp;
1660 else if (cp->second == a)
1661 next_cp = cp->next_second_allocno_copy;
1666 qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
1667 /* Coalesced copies, most frequently executed first. */
1668 for (; cp_num != 0;)
1670 for (i = 0; i < cp_num; i++)
1672 cp = sorted_copies[i];
1673 if (! coalesced_allocno_conflict_p (cp->first, cp->second, reload_p))
1675 allocno_coalesced_p = true;
1676 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1679 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
1680 cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
1681 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
1683 merge_allocnos (cp->first, cp->second);
1688 /* Collect the rest of copies. */
1689 for (n = 0; i < cp_num; i++)
1691 cp = sorted_copies[i];
1692 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->first)
1693 != ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->second))
1694 sorted_copies[n++] = cp;
1698 ira_free (sorted_copies);
1701 /* Map: allocno number -> allocno priority. */
1702 static int *allocno_priorities;
1704 /* Set up priorities for N allocnos in array
1705 CONSIDERATION_ALLOCNOS. */
1707 setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
1709 int i, length, nrefs, priority, max_priority, mult;
1713 for (i = 0; i < n; i++)
1715 a = consideration_allocnos[i];
1716 nrefs = ALLOCNO_NREFS (a);
1717 ira_assert (nrefs >= 0);
1718 mult = floor_log2 (ALLOCNO_NREFS (a)) + 1;
1719 ira_assert (mult >= 0);
1720 allocno_priorities[ALLOCNO_NUM (a)]
1723 * (ALLOCNO_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a))
1724 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a)][ALLOCNO_MODE (a)]);
1726 priority = -priority;
1727 if (max_priority < priority)
1728 max_priority = priority;
1730 mult = max_priority == 0 ? 1 : INT_MAX / max_priority;
1731 for (i = 0; i < n; i++)
1733 a = consideration_allocnos[i];
1734 length = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
1737 allocno_priorities[ALLOCNO_NUM (a)]
1738 = allocno_priorities[ALLOCNO_NUM (a)] * mult / length;
1742 /* Sort allocnos according to their priorities which are calculated
1743 analogous to ones in file `global.c'. */
1745 allocno_priority_compare_func (const void *v1p, const void *v2p)
1747 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
1748 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
1751 pri1 = allocno_priorities[ALLOCNO_NUM (a1)];
1752 pri2 = allocno_priorities[ALLOCNO_NUM (a2)];
1756 /* If regs are equally good, sort by allocnos, so that the results of
1757 qsort leave nothing to chance. */
1758 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
1761 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
1762 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
1764 color_allocnos (void)
1770 allocno_coalesced_p = false;
1771 processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
1772 if (flag_ira_coalesce)
1773 coalesce_allocnos (false);
1774 if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
1777 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1779 a = ira_allocnos[i];
1780 if (ALLOCNO_COVER_CLASS (a) == NO_REGS)
1782 ALLOCNO_HARD_REGNO (a) = -1;
1783 ALLOCNO_ASSIGNED_P (a) = true;
1784 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
1785 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
1786 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1788 fprintf (ira_dump_file, " Spill");
1789 print_coalesced_allocno (a);
1790 fprintf (ira_dump_file, "\n");
1794 sorted_allocnos[n++] = a;
1798 setup_allocno_priorities (sorted_allocnos, n);
1799 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
1800 allocno_priority_compare_func);
1801 for (i = 0; i < n; i++)
1803 a = sorted_allocnos[i];
1804 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1806 fprintf (ira_dump_file, " ");
1807 print_coalesced_allocno (a);
1808 fprintf (ira_dump_file, " -- ");
1810 if (assign_hard_reg (a, false))
1812 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1813 fprintf (ira_dump_file, "assign hard reg %d\n",
1814 ALLOCNO_HARD_REGNO (a));
1818 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1819 fprintf (ira_dump_file, "assign memory\n");
1826 /* Put the allocnos into the corresponding buckets. */
1827 colorable_allocno_bucket = NULL;
1828 uncolorable_allocno_bucket = NULL;
1829 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1831 a = ira_allocnos[i];
1832 if (ALLOCNO_COVER_CLASS (a) == NO_REGS)
1834 ALLOCNO_HARD_REGNO (a) = -1;
1835 ALLOCNO_ASSIGNED_P (a) = true;
1836 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
1837 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
1838 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1840 fprintf (ira_dump_file, " Spill");
1841 print_coalesced_allocno (a);
1842 fprintf (ira_dump_file, "\n");
1846 put_allocno_into_bucket (a);
1848 push_allocnos_to_stack ();
1849 pop_allocnos_from_stack ();
1851 if (flag_ira_coalesce)
1852 /* We don't need coalesced allocnos for ira_reassign_pseudos. */
1853 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1855 a = ira_allocnos[i];
1856 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
1857 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
1859 ira_free_bitmap (processed_coalesced_allocno_bitmap);
1860 allocno_coalesced_p = false;
1865 /* Output information about the loop given by its LOOP_TREE_NODE. */
1867 print_loop_title (ira_loop_tree_node_t loop_tree_node)
1871 ira_loop_tree_node_t subloop_node, dest_loop_node;
1875 ira_assert (loop_tree_node->loop != NULL);
1876 fprintf (ira_dump_file,
1877 "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
1878 loop_tree_node->loop->num,
1879 (loop_tree_node->parent == NULL
1880 ? -1 : loop_tree_node->parent->loop->num),
1881 loop_tree_node->loop->header->index,
1882 loop_depth (loop_tree_node->loop));
1883 for (subloop_node = loop_tree_node->children;
1884 subloop_node != NULL;
1885 subloop_node = subloop_node->next)
1886 if (subloop_node->bb != NULL)
1888 fprintf (ira_dump_file, " %d", subloop_node->bb->index);
1889 FOR_EACH_EDGE (e, ei, subloop_node->bb->succs)
1890 if (e->dest != EXIT_BLOCK_PTR
1891 && ((dest_loop_node = IRA_BB_NODE (e->dest)->parent)
1893 fprintf (ira_dump_file, "(->%d:l%d)",
1894 e->dest->index, dest_loop_node->loop->num);
1896 fprintf (ira_dump_file, "\n all:");
1897 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
1898 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
1899 fprintf (ira_dump_file, "\n modified regnos:");
1900 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->modified_regnos, 0, j, bi)
1901 fprintf (ira_dump_file, " %d", j);
1902 fprintf (ira_dump_file, "\n border:");
1903 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->border_allocnos, 0, j, bi)
1904 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
1905 fprintf (ira_dump_file, "\n Pressure:");
1906 for (j = 0; (int) j < ira_reg_class_cover_size; j++)
1908 enum reg_class cover_class;
1910 cover_class = ira_reg_class_cover[j];
1911 if (loop_tree_node->reg_pressure[cover_class] == 0)
1913 fprintf (ira_dump_file, " %s=%d", reg_class_names[cover_class],
1914 loop_tree_node->reg_pressure[cover_class]);
1916 fprintf (ira_dump_file, "\n");
1919 /* Color the allocnos inside loop (in the extreme case it can be all
1920 of the function) given the corresponding LOOP_TREE_NODE. The
1921 function is called for each loop during top-down traverse of the
1924 color_pass (ira_loop_tree_node_t loop_tree_node)
1926 int regno, hard_regno, index = -1;
1927 int cost, exit_freq, enter_freq;
1930 enum machine_mode mode;
1931 enum reg_class rclass, cover_class;
1932 ira_allocno_t a, subloop_allocno;
1933 ira_loop_tree_node_t subloop_node;
1935 ira_assert (loop_tree_node->bb == NULL);
1936 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1937 print_loop_title (loop_tree_node);
1939 bitmap_copy (coloring_allocno_bitmap, loop_tree_node->all_allocnos);
1940 bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap);
1941 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
1943 a = ira_allocnos[j];
1944 if (! ALLOCNO_ASSIGNED_P (a))
1946 bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a));
1948 /* Color all mentioned allocnos including transparent ones. */
1950 /* Process caps. They are processed just once. */
1951 if (flag_ira_region == IRA_REGION_MIXED
1952 || flag_ira_region == IRA_REGION_ALL)
1953 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
1955 a = ira_allocnos[j];
1956 if (ALLOCNO_CAP_MEMBER (a) == NULL)
1958 /* Remove from processing in the next loop. */
1959 bitmap_clear_bit (consideration_allocno_bitmap, j);
1960 rclass = ALLOCNO_COVER_CLASS (a);
1961 if (flag_ira_region == IRA_REGION_MIXED
1962 && (loop_tree_node->reg_pressure[rclass]
1963 <= ira_available_class_regs[rclass]))
1965 mode = ALLOCNO_MODE (a);
1966 hard_regno = ALLOCNO_HARD_REGNO (a);
1967 if (hard_regno >= 0)
1969 index = ira_class_hard_reg_index[rclass][hard_regno];
1970 ira_assert (index >= 0);
1972 regno = ALLOCNO_REGNO (a);
1973 subloop_allocno = ALLOCNO_CAP_MEMBER (a);
1974 subloop_node = ALLOCNO_LOOP_TREE_NODE (subloop_allocno);
1975 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno));
1976 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
1977 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
1978 if (hard_regno >= 0)
1979 update_copy_costs (subloop_allocno, true);
1980 /* We don't need updated costs anymore: */
1981 ira_free_allocno_updated_costs (subloop_allocno);
1984 /* Update costs of the corresponding allocnos (not caps) in the
1986 for (subloop_node = loop_tree_node->subloops;
1987 subloop_node != NULL;
1988 subloop_node = subloop_node->subloop_next)
1990 ira_assert (subloop_node->bb == NULL);
1991 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
1993 a = ira_allocnos[j];
1994 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
1995 mode = ALLOCNO_MODE (a);
1996 rclass = ALLOCNO_COVER_CLASS (a);
1997 hard_regno = ALLOCNO_HARD_REGNO (a);
1998 /* Use hard register class here. ??? */
1999 if (hard_regno >= 0)
2001 index = ira_class_hard_reg_index[rclass][hard_regno];
2002 ira_assert (index >= 0);
2004 regno = ALLOCNO_REGNO (a);
2005 /* ??? conflict costs */
2006 subloop_allocno = subloop_node->regno_allocno_map[regno];
2007 if (subloop_allocno == NULL
2008 || ALLOCNO_CAP (subloop_allocno) != NULL)
2010 ira_assert (ALLOCNO_COVER_CLASS (subloop_allocno) == rclass);
2011 ira_assert (bitmap_bit_p (subloop_node->all_allocnos,
2012 ALLOCNO_NUM (subloop_allocno)));
2013 if ((flag_ira_region == IRA_REGION_MIXED)
2014 && (loop_tree_node->reg_pressure[rclass]
2015 <= ira_available_class_regs[rclass]))
2017 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
2019 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
2020 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
2021 if (hard_regno >= 0)
2022 update_copy_costs (subloop_allocno, true);
2023 /* We don't need updated costs anymore: */
2024 ira_free_allocno_updated_costs (subloop_allocno);
2028 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
2029 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
2030 ira_assert (regno < ira_reg_equiv_len);
2031 if (ira_reg_equiv_invariant_p[regno]
2032 || ira_reg_equiv_const[regno] != NULL_RTX)
2034 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
2036 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
2037 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
2038 if (hard_regno >= 0)
2039 update_copy_costs (subloop_allocno, true);
2040 /* We don't need updated costs anymore: */
2041 ira_free_allocno_updated_costs (subloop_allocno);
2044 else if (hard_regno < 0)
2046 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
2047 -= ((ira_memory_move_cost[mode][rclass][1] * enter_freq)
2048 + (ira_memory_move_cost[mode][rclass][0] * exit_freq));
2052 cover_class = ALLOCNO_COVER_CLASS (subloop_allocno);
2053 cost = (ira_get_register_move_cost (mode, rclass, rclass)
2054 * (exit_freq + enter_freq));
2055 ira_allocate_and_set_or_copy_costs
2056 (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno), cover_class,
2057 ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno),
2058 ALLOCNO_HARD_REG_COSTS (subloop_allocno));
2059 ira_allocate_and_set_or_copy_costs
2060 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno),
2062 ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno));
2063 ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
2064 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
2066 if (ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno)
2067 > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index])
2068 ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno)
2069 = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index];
2070 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
2071 += (ira_memory_move_cost[mode][rclass][0] * enter_freq
2072 + ira_memory_move_cost[mode][rclass][1] * exit_freq);
2078 /* Initialize the common data for coloring and calls functions to do
2079 Chaitin-Briggs and regional coloring. */
2083 coloring_allocno_bitmap = ira_allocate_bitmap ();
2084 allocnos_for_spilling
2085 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
2086 * ira_allocnos_num);
2087 splay_tree_node_pool = create_alloc_pool ("splay tree nodes",
2088 sizeof (struct splay_tree_node_s),
2090 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2091 fprintf (ira_dump_file, "\n**** Allocnos coloring:\n\n");
2093 ira_traverse_loop_tree (false, ira_loop_tree_root, color_pass, NULL);
2095 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2096 ira_print_disposition (ira_dump_file);
2098 free_alloc_pool (splay_tree_node_pool);
2099 ira_free_bitmap (coloring_allocno_bitmap);
2100 ira_free (allocnos_for_spilling);
2105 /* Move spill/restore code, which are to be generated in ira-emit.c,
2106 to less frequent points (if it is profitable) by reassigning some
2107 allocnos (in loop with subloops containing in another loop) to
2108 memory which results in longer live-range where the corresponding
2109 pseudo-registers will be in memory. */
2111 move_spill_restore (void)
2113 int cost, regno, hard_regno, hard_regno2, index;
2115 int enter_freq, exit_freq;
2116 enum machine_mode mode;
2117 enum reg_class rclass;
2118 ira_allocno_t a, parent_allocno, subloop_allocno;
2119 ira_loop_tree_node_t parent, loop_node, subloop_node;
2120 ira_allocno_iterator ai;
2125 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2126 fprintf (ira_dump_file, "New iteration of spill/restore move\n");
2127 FOR_EACH_ALLOCNO (a, ai)
2129 regno = ALLOCNO_REGNO (a);
2130 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
2131 if (ALLOCNO_CAP_MEMBER (a) != NULL
2132 || ALLOCNO_CAP (a) != NULL
2133 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0
2134 || loop_node->children == NULL
2135 /* don't do the optimization because it can create
2136 copies and the reload pass can spill the allocno set
2137 by copy although the allocno will not get memory
2139 || ira_reg_equiv_invariant_p[regno]
2140 || ira_reg_equiv_const[regno] != NULL_RTX
2141 || !bitmap_bit_p (loop_node->border_allocnos, ALLOCNO_NUM (a)))
2143 mode = ALLOCNO_MODE (a);
2144 rclass = ALLOCNO_COVER_CLASS (a);
2145 index = ira_class_hard_reg_index[rclass][hard_regno];
2146 ira_assert (index >= 0);
2147 cost = (ALLOCNO_MEMORY_COST (a)
2148 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
2149 ? ALLOCNO_COVER_CLASS_COST (a)
2150 : ALLOCNO_HARD_REG_COSTS (a)[index]));
2151 for (subloop_node = loop_node->subloops;
2152 subloop_node != NULL;
2153 subloop_node = subloop_node->subloop_next)
2155 ira_assert (subloop_node->bb == NULL);
2156 subloop_allocno = subloop_node->regno_allocno_map[regno];
2157 if (subloop_allocno == NULL)
2159 ira_assert (rclass == ALLOCNO_COVER_CLASS (subloop_allocno));
2160 /* We have accumulated cost. To get the real cost of
2161 allocno usage in the loop we should subtract costs of
2162 the subloop allocnos. */
2163 cost -= (ALLOCNO_MEMORY_COST (subloop_allocno)
2164 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno) == NULL
2165 ? ALLOCNO_COVER_CLASS_COST (subloop_allocno)
2166 : ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index]));
2167 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
2168 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
2169 if ((hard_regno2 = ALLOCNO_HARD_REGNO (subloop_allocno)) < 0)
2170 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
2171 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
2175 += (ira_memory_move_cost[mode][rclass][0] * exit_freq
2176 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
2177 if (hard_regno2 != hard_regno)
2178 cost -= (ira_get_register_move_cost (mode, rclass, rclass)
2179 * (exit_freq + enter_freq));
2182 if ((parent = loop_node->parent) != NULL
2183 && (parent_allocno = parent->regno_allocno_map[regno]) != NULL)
2185 ira_assert (rclass == ALLOCNO_COVER_CLASS (parent_allocno));
2186 exit_freq = ira_loop_edge_freq (loop_node, regno, true);
2187 enter_freq = ira_loop_edge_freq (loop_node, regno, false);
2188 if ((hard_regno2 = ALLOCNO_HARD_REGNO (parent_allocno)) < 0)
2189 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
2190 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
2194 += (ira_memory_move_cost[mode][rclass][1] * exit_freq
2195 + ira_memory_move_cost[mode][rclass][0] * enter_freq);
2196 if (hard_regno2 != hard_regno)
2197 cost -= (ira_get_register_move_cost (mode, rclass, rclass)
2198 * (exit_freq + enter_freq));
2203 ALLOCNO_HARD_REGNO (a) = -1;
2204 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2208 " Moving spill/restore for a%dr%d up from loop %d",
2209 ALLOCNO_NUM (a), regno, loop_node->loop->num);
2210 fprintf (ira_dump_file, " - profit %d\n", -cost);
2222 /* Update current hard reg costs and current conflict hard reg costs
2223 for allocno A. It is done by processing its copies containing
2224 other allocnos already assigned. */
2226 update_curr_costs (ira_allocno_t a)
2228 int i, hard_regno, cost;
2229 enum machine_mode mode;
2230 enum reg_class cover_class, rclass;
2231 ira_allocno_t another_a;
2232 ira_copy_t cp, next_cp;
2234 ira_free_allocno_updated_costs (a);
2235 ira_assert (! ALLOCNO_ASSIGNED_P (a));
2236 cover_class = ALLOCNO_COVER_CLASS (a);
2237 if (cover_class == NO_REGS)
2239 mode = ALLOCNO_MODE (a);
2240 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2244 next_cp = cp->next_first_allocno_copy;
2245 another_a = cp->second;
2247 else if (cp->second == a)
2249 next_cp = cp->next_second_allocno_copy;
2250 another_a = cp->first;
2254 if (! ira_reg_classes_intersect_p[cover_class][ALLOCNO_COVER_CLASS
2256 || ! ALLOCNO_ASSIGNED_P (another_a)
2257 || (hard_regno = ALLOCNO_HARD_REGNO (another_a)) < 0)
2259 rclass = REGNO_REG_CLASS (hard_regno);
2260 i = ira_class_hard_reg_index[cover_class][hard_regno];
2263 cost = (cp->first == a
2264 ? ira_get_register_move_cost (mode, rclass, cover_class)
2265 : ira_get_register_move_cost (mode, cover_class, rclass));
2266 ira_allocate_and_set_or_copy_costs
2267 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
2268 cover_class, ALLOCNO_COVER_CLASS_COST (a),
2269 ALLOCNO_HARD_REG_COSTS (a));
2270 ira_allocate_and_set_or_copy_costs
2271 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
2272 cover_class, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
2273 ALLOCNO_UPDATED_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
2274 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
2278 /* Try to assign hard registers to the unassigned allocnos and
2279 allocnos conflicting with them or conflicting with allocnos whose
2280 regno >= START_REGNO. The function is called after ira_flattening,
2281 so more allocnos (including ones created in ira-emit.c) will have a
2282 chance to get a hard register. We use simple assignment algorithm
2283 based on priorities. */
2285 ira_reassign_conflict_allocnos (int start_regno)
2287 int i, allocnos_to_color_num;
2288 ira_allocno_t a, conflict_a;
2289 ira_allocno_conflict_iterator aci;
2290 enum reg_class cover_class;
2291 bitmap allocnos_to_color;
2292 ira_allocno_iterator ai;
2294 allocnos_to_color = ira_allocate_bitmap ();
2295 allocnos_to_color_num = 0;
2296 FOR_EACH_ALLOCNO (a, ai)
2298 if (! ALLOCNO_ASSIGNED_P (a)
2299 && ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a)))
2301 if (ALLOCNO_COVER_CLASS (a) != NO_REGS)
2302 sorted_allocnos[allocnos_to_color_num++] = a;
2305 ALLOCNO_ASSIGNED_P (a) = true;
2306 ALLOCNO_HARD_REGNO (a) = -1;
2307 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2308 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2310 bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (a));
2312 if (ALLOCNO_REGNO (a) < start_regno
2313 || (cover_class = ALLOCNO_COVER_CLASS (a)) == NO_REGS)
2315 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
2317 ira_assert (ira_reg_classes_intersect_p
2318 [cover_class][ALLOCNO_COVER_CLASS (conflict_a)]);
2319 if (bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (conflict_a)))
2321 bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a));
2322 sorted_allocnos[allocnos_to_color_num++] = conflict_a;
2325 ira_free_bitmap (allocnos_to_color);
2326 if (allocnos_to_color_num > 1)
2328 setup_allocno_priorities (sorted_allocnos, allocnos_to_color_num);
2329 qsort (sorted_allocnos, allocnos_to_color_num, sizeof (ira_allocno_t),
2330 allocno_priority_compare_func);
2332 for (i = 0; i < allocnos_to_color_num; i++)
2334 a = sorted_allocnos[i];
2335 ALLOCNO_ASSIGNED_P (a) = false;
2336 update_curr_costs (a);
2338 for (i = 0; i < allocnos_to_color_num; i++)
2340 a = sorted_allocnos[i];
2341 if (assign_hard_reg (a, true))
2343 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2346 " Secondary allocation: assign hard reg %d to reg %d\n",
2347 ALLOCNO_HARD_REGNO (a), ALLOCNO_REGNO (a));
2354 /* This page contains code to coalesce memory stack slots used by
2355 spilled allocnos. This results in smaller stack frame, better data
2356 locality, and in smaller code for some architectures like
2357 x86/x86_64 where insn size depends on address displacement value.
2358 On the other hand, it can worsen insn scheduling after the RA but
2359 in practice it is less important than smaller stack frames. */
2361 /* Usage cost and order number of coalesced allocno set to which
2362 given pseudo register belongs to. */
2363 static int *regno_coalesced_allocno_cost;
2364 static int *regno_coalesced_allocno_num;
2366 /* Sort pseudos according frequencies of coalesced allocno sets they
2367 belong to (putting most frequently ones first), and according to
2368 coalesced allocno set order numbers. */
2370 coalesced_pseudo_reg_freq_compare (const void *v1p, const void *v2p)
2372 const int regno1 = *(const int *) v1p;
2373 const int regno2 = *(const int *) v2p;
2376 if ((diff = (regno_coalesced_allocno_cost[regno2]
2377 - regno_coalesced_allocno_cost[regno1])) != 0)
2379 if ((diff = (regno_coalesced_allocno_num[regno1]
2380 - regno_coalesced_allocno_num[regno2])) != 0)
2382 return regno1 - regno2;
2385 /* Widest width in which each pseudo reg is referred to (via subreg).
2386 It is used for sorting pseudo registers. */
2387 static unsigned int *regno_max_ref_width;
2389 /* Redefine STACK_GROWS_DOWNWARD in terms of 0 or 1. */
2390 #ifdef STACK_GROWS_DOWNWARD
2391 # undef STACK_GROWS_DOWNWARD
2392 # define STACK_GROWS_DOWNWARD 1
2394 # define STACK_GROWS_DOWNWARD 0
2397 /* Sort pseudos according their slot numbers (putting ones with
2398 smaller numbers first, or last when the frame pointer is not
2401 coalesced_pseudo_reg_slot_compare (const void *v1p, const void *v2p)
2403 const int regno1 = *(const int *) v1p;
2404 const int regno2 = *(const int *) v2p;
2405 ira_allocno_t a1 = ira_regno_allocno_map[regno1];
2406 ira_allocno_t a2 = ira_regno_allocno_map[regno2];
2407 int diff, slot_num1, slot_num2;
2408 int total_size1, total_size2;
2410 if (a1 == NULL || ALLOCNO_HARD_REGNO (a1) >= 0)
2412 if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
2413 return regno1 - regno2;
2416 else if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
2418 slot_num1 = -ALLOCNO_HARD_REGNO (a1);
2419 slot_num2 = -ALLOCNO_HARD_REGNO (a2);
2420 if ((diff = slot_num1 - slot_num2) != 0)
2421 return (frame_pointer_needed
2422 || !FRAME_GROWS_DOWNWARD == STACK_GROWS_DOWNWARD ? diff : -diff);
2423 total_size1 = MAX (PSEUDO_REGNO_BYTES (regno1), regno_max_ref_width[regno1]);
2424 total_size2 = MAX (PSEUDO_REGNO_BYTES (regno2), regno_max_ref_width[regno2]);
2425 if ((diff = total_size2 - total_size1) != 0)
2427 return regno1 - regno2;
2430 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
2431 for coalesced allocno sets containing allocnos with their regnos
2432 given in array PSEUDO_REGNOS of length N. */
2434 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos, int n)
2436 int i, num, regno, cost;
2437 ira_allocno_t allocno, a;
2439 for (num = i = 0; i < n; i++)
2441 regno = pseudo_regnos[i];
2442 allocno = ira_regno_allocno_map[regno];
2443 if (allocno == NULL)
2445 regno_coalesced_allocno_cost[regno] = 0;
2446 regno_coalesced_allocno_num[regno] = ++num;
2449 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
2452 for (cost = 0, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2453 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2455 cost += ALLOCNO_FREQ (a);
2459 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2460 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2462 regno_coalesced_allocno_num[ALLOCNO_REGNO (a)] = num;
2463 regno_coalesced_allocno_cost[ALLOCNO_REGNO (a)] = cost;
2470 /* Collect spilled allocnos representing coalesced allocno sets (the
2471 first coalesced allocno). The collected allocnos are returned
2472 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
2473 number of the collected allocnos. The allocnos are given by their
2474 regnos in array PSEUDO_REGNOS of length N. */
2476 collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n,
2477 ira_allocno_t *spilled_coalesced_allocnos)
2480 ira_allocno_t allocno;
2482 for (num = i = 0; i < n; i++)
2484 regno = pseudo_regnos[i];
2485 allocno = ira_regno_allocno_map[regno];
2486 if (allocno == NULL || ALLOCNO_HARD_REGNO (allocno) >= 0
2487 || ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
2489 spilled_coalesced_allocnos[num++] = allocno;
2494 /* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
2495 given slot contains live ranges of coalesced allocnos assigned to
2497 static live_range_t *slot_coalesced_allocnos_live_ranges;
2499 /* Return TRUE if coalesced allocnos represented by ALLOCNO has live
2500 ranges intersected with live ranges of coalesced allocnos assigned
2501 to slot with number N. */
2503 slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno, int n)
2507 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2508 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2510 if (ira_allocno_live_ranges_intersect_p
2511 (slot_coalesced_allocnos_live_ranges[n], ALLOCNO_LIVE_RANGES (a)))
2519 /* Update live ranges of slot to which coalesced allocnos represented
2520 by ALLOCNO were assigned. */
2522 setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno)
2528 n = ALLOCNO_TEMP (allocno);
2529 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2530 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2532 r = ira_copy_allocno_live_range_list (ALLOCNO_LIVE_RANGES (a));
2533 slot_coalesced_allocnos_live_ranges[n]
2534 = ira_merge_allocno_live_ranges
2535 (slot_coalesced_allocnos_live_ranges[n], r);
2541 /* We have coalesced allocnos involving in copies. Coalesce allocnos
2542 further in order to share the same memory stack slot. Allocnos
2543 representing sets of allocnos coalesced before the call are given
2544 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
2545 some allocnos were coalesced in the function. */
2547 coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num)
2549 int i, j, n, last_coalesced_allocno_num;
2550 ira_allocno_t allocno, a;
2551 bool merged_p = false;
2552 bitmap set_jump_crosses = regstat_get_setjmp_crosses ();
2554 slot_coalesced_allocnos_live_ranges
2555 = (live_range_t *) ira_allocate (sizeof (live_range_t) * ira_allocnos_num);
2556 memset (slot_coalesced_allocnos_live_ranges, 0,
2557 sizeof (live_range_t) * ira_allocnos_num);
2558 last_coalesced_allocno_num = 0;
2559 /* Coalesce non-conflicting spilled allocnos preferring most
2561 for (i = 0; i < num; i++)
2563 allocno = spilled_coalesced_allocnos[i];
2564 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno
2565 || bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (allocno))
2566 || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
2567 && (ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX
2568 || ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)])))
2570 for (j = 0; j < i; j++)
2572 a = spilled_coalesced_allocnos[j];
2573 n = ALLOCNO_TEMP (a);
2574 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a
2575 && ! bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (a))
2576 && (ALLOCNO_REGNO (a) >= ira_reg_equiv_len
2577 || (! ira_reg_equiv_invariant_p[ALLOCNO_REGNO (a)]
2578 && ira_reg_equiv_const[ALLOCNO_REGNO (a)] == NULL_RTX))
2579 && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno, n))
2584 /* No coalescing: set up number for coalesced allocnos
2585 represented by ALLOCNO. */
2586 ALLOCNO_TEMP (allocno) = last_coalesced_allocno_num++;
2587 setup_slot_coalesced_allocno_live_ranges (allocno);
2591 allocno_coalesced_p = true;
2593 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2594 fprintf (ira_dump_file,
2595 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
2596 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno),
2597 ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2598 ALLOCNO_TEMP (allocno) = ALLOCNO_TEMP (a);
2599 setup_slot_coalesced_allocno_live_ranges (allocno);
2600 merge_allocnos (a, allocno);
2601 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a);
2604 for (i = 0; i < ira_allocnos_num; i++)
2605 ira_finish_allocno_live_range_list
2606 (slot_coalesced_allocnos_live_ranges[i]);
2607 ira_free (slot_coalesced_allocnos_live_ranges);
2611 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
2612 subsequent assigning stack slots to them in the reload pass. To do
2613 this we coalesce spilled allocnos first to decrease the number of
2614 memory-memory move insns. This function is called by the
2617 ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n,
2618 unsigned int *reg_max_ref_width)
2620 int max_regno = max_reg_num ();
2621 int i, regno, num, slot_num;
2622 ira_allocno_t allocno, a;
2623 ira_allocno_iterator ai;
2624 ira_allocno_t *spilled_coalesced_allocnos;
2626 processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
2627 /* Set up allocnos can be coalesced. */
2628 coloring_allocno_bitmap = ira_allocate_bitmap ();
2629 for (i = 0; i < n; i++)
2631 regno = pseudo_regnos[i];
2632 allocno = ira_regno_allocno_map[regno];
2633 if (allocno != NULL)
2634 bitmap_set_bit (coloring_allocno_bitmap,
2635 ALLOCNO_NUM (allocno));
2637 allocno_coalesced_p = false;
2638 coalesce_allocnos (true);
2639 ira_free_bitmap (coloring_allocno_bitmap);
2640 regno_coalesced_allocno_cost
2641 = (int *) ira_allocate (max_regno * sizeof (int));
2642 regno_coalesced_allocno_num
2643 = (int *) ira_allocate (max_regno * sizeof (int));
2644 memset (regno_coalesced_allocno_num, 0, max_regno * sizeof (int));
2645 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
2646 /* Sort regnos according frequencies of the corresponding coalesced
2648 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_freq_compare);
2649 spilled_coalesced_allocnos
2650 = (ira_allocno_t *) ira_allocate (ira_allocnos_num
2651 * sizeof (ira_allocno_t));
2652 /* Collect allocnos representing the spilled coalesced allocno
2654 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
2655 spilled_coalesced_allocnos);
2656 if (flag_ira_share_spill_slots
2657 && coalesce_spill_slots (spilled_coalesced_allocnos, num))
2659 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
2660 qsort (pseudo_regnos, n, sizeof (int),
2661 coalesced_pseudo_reg_freq_compare);
2662 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
2663 spilled_coalesced_allocnos);
2665 ira_free_bitmap (processed_coalesced_allocno_bitmap);
2666 allocno_coalesced_p = false;
2667 /* Assign stack slot numbers to spilled allocno sets, use smaller
2668 numbers for most frequently used coalesced allocnos. -1 is
2669 reserved for dynamic search of stack slots for pseudos spilled by
2672 for (i = 0; i < num; i++)
2674 allocno = spilled_coalesced_allocnos[i];
2675 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno
2676 || ALLOCNO_HARD_REGNO (allocno) >= 0
2677 || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
2678 && (ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX
2679 || ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)])))
2681 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2682 fprintf (ira_dump_file, " Slot %d (freq,size):", slot_num);
2684 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2685 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2687 ira_assert (ALLOCNO_HARD_REGNO (a) < 0);
2688 ALLOCNO_HARD_REGNO (a) = -slot_num;
2689 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2690 fprintf (ira_dump_file, " a%dr%d(%d,%d)",
2691 ALLOCNO_NUM (a), ALLOCNO_REGNO (a), ALLOCNO_FREQ (a),
2692 MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a)),
2693 reg_max_ref_width[ALLOCNO_REGNO (a)]));
2698 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2699 fprintf (ira_dump_file, "\n");
2701 ira_spilled_reg_stack_slots_num = slot_num - 1;
2702 ira_free (spilled_coalesced_allocnos);
2703 /* Sort regnos according the slot numbers. */
2704 regno_max_ref_width = reg_max_ref_width;
2705 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_slot_compare);
2706 /* Uncoalesce allocnos which is necessary for (re)assigning during
2708 FOR_EACH_ALLOCNO (a, ai)
2710 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
2711 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
2713 ira_free (regno_coalesced_allocno_num);
2714 ira_free (regno_coalesced_allocno_cost);
2719 /* This page contains code used by the reload pass to improve the
2722 /* The function is called from reload to mark changes in the
2723 allocation of REGNO made by the reload. Remember that reg_renumber
2724 reflects the change result. */
2726 ira_mark_allocation_change (int regno)
2728 ira_allocno_t a = ira_regno_allocno_map[regno];
2729 int old_hard_regno, hard_regno, cost;
2730 enum reg_class cover_class = ALLOCNO_COVER_CLASS (a);
2732 ira_assert (a != NULL);
2733 hard_regno = reg_renumber[regno];
2734 if ((old_hard_regno = ALLOCNO_HARD_REGNO (a)) == hard_regno)
2736 if (old_hard_regno < 0)
2737 cost = -ALLOCNO_MEMORY_COST (a);
2740 ira_assert (ira_class_hard_reg_index[cover_class][old_hard_regno] >= 0);
2741 cost = -(ALLOCNO_HARD_REG_COSTS (a) == NULL
2742 ? ALLOCNO_COVER_CLASS_COST (a)
2743 : ALLOCNO_HARD_REG_COSTS (a)
2744 [ira_class_hard_reg_index[cover_class][old_hard_regno]]);
2745 update_copy_costs (a, false);
2747 ira_overall_cost -= cost;
2748 ALLOCNO_HARD_REGNO (a) = hard_regno;
2751 ALLOCNO_HARD_REGNO (a) = -1;
2752 cost += ALLOCNO_MEMORY_COST (a);
2754 else if (ira_class_hard_reg_index[cover_class][hard_regno] >= 0)
2756 cost += (ALLOCNO_HARD_REG_COSTS (a) == NULL
2757 ? ALLOCNO_COVER_CLASS_COST (a)
2758 : ALLOCNO_HARD_REG_COSTS (a)
2759 [ira_class_hard_reg_index[cover_class][hard_regno]]);
2760 update_copy_costs (a, true);
2763 /* Reload changed class of the allocno. */
2765 ira_overall_cost += cost;
2768 /* This function is called when reload deletes memory-memory move. In
2769 this case we marks that the allocation of the corresponding
2770 allocnos should be not changed in future. Otherwise we risk to get
2773 ira_mark_memory_move_deletion (int dst_regno, int src_regno)
2775 ira_allocno_t dst = ira_regno_allocno_map[dst_regno];
2776 ira_allocno_t src = ira_regno_allocno_map[src_regno];
2778 ira_assert (dst != NULL && src != NULL
2779 && ALLOCNO_HARD_REGNO (dst) < 0
2780 && ALLOCNO_HARD_REGNO (src) < 0);
2781 ALLOCNO_DONT_REASSIGN_P (dst) = true;
2782 ALLOCNO_DONT_REASSIGN_P (src) = true;
2785 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
2786 allocno A and return TRUE in the case of success. */
2788 allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs)
2791 enum reg_class cover_class;
2792 int regno = ALLOCNO_REGNO (a);
2795 COPY_HARD_REG_SET (saved, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
2796 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), forbidden_regs);
2797 if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
2798 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), call_used_reg_set);
2799 ALLOCNO_ASSIGNED_P (a) = false;
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;
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)