1 /* IRA allocation based on graph coloring.
2 Copyright (C) 2006, 2007, 2008
3 Free Software Foundation, Inc.
4 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
33 #include "hard-reg-set.h"
34 #include "basic-block.h"
40 #include "splay-tree.h"
43 /* This file contains code for regional graph coloring, spill/restore
44 code placement optimization, and code helping the reload pass to do
47 /* Bitmap of allocnos which should be colored. */
48 static bitmap coloring_allocno_bitmap
;
50 /* Bitmap of allocnos which should be taken into account during
51 coloring. In general case it contains allocnos from
52 coloring_allocno_bitmap plus other already colored conflicting
54 static bitmap consideration_allocno_bitmap
;
56 /* TRUE if we coalesced some allocnos. In other words, if we got
57 loops formed by members first_coalesced_allocno and
58 next_coalesced_allocno containing more one allocno. */
59 static bool allocno_coalesced_p
;
61 /* Bitmap used to prevent a repeated allocno processing because of
63 static bitmap processed_coalesced_allocno_bitmap
;
65 /* All allocnos sorted according their priorities. */
66 static ira_allocno_t
*sorted_allocnos
;
68 /* Vec representing the stack of allocnos used during coloring. */
69 static VEC(ira_allocno_t
,heap
) *allocno_stack_vec
;
71 /* Array used to choose an allocno for spilling. */
72 static ira_allocno_t
*allocnos_for_spilling
;
74 /* Pool for splay tree nodes. */
75 static alloc_pool splay_tree_node_pool
;
77 /* When an allocno is removed from the splay tree, it is put in the
78 following vector for subsequent inserting it into the splay tree
79 after putting all colorable allocnos onto the stack. The allocno
80 could be removed from and inserted to the splay tree every time
81 when its spilling priority is changed but such solution would be
82 more costly although simpler. */
83 static VEC(ira_allocno_t
,heap
) *removed_splay_allocno_vec
;
87 /* This page contains functions used to find conflicts using allocno
90 /* Return TRUE if live ranges of allocnos A1 and A2 intersect. It is
91 used to find a conflict for new allocnos or allocnos with the
92 different cover classes. */
94 allocnos_have_intersected_live_ranges_p (ira_allocno_t a1
, ira_allocno_t a2
)
98 if (ALLOCNO_REG (a1
) != NULL
&& ALLOCNO_REG (a2
) != NULL
99 && (ORIGINAL_REGNO (ALLOCNO_REG (a1
))
100 == ORIGINAL_REGNO (ALLOCNO_REG (a2
))))
102 return ira_allocno_live_ranges_intersect_p (ALLOCNO_LIVE_RANGES (a1
),
103 ALLOCNO_LIVE_RANGES (a2
));
106 #ifdef ENABLE_IRA_CHECKING
108 /* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
109 intersect. This should be used when there is only one region.
110 Currently this is used during reload. */
112 pseudos_have_intersected_live_ranges_p (int regno1
, int regno2
)
114 ira_allocno_t a1
, a2
;
116 ira_assert (regno1
>= FIRST_PSEUDO_REGISTER
117 && regno2
>= FIRST_PSEUDO_REGISTER
);
118 /* Reg info caclulated by dataflow infrastructure can be different
119 from one calculated by regclass. */
120 if ((a1
= ira_loop_tree_root
->regno_allocno_map
[regno1
]) == NULL
121 || (a2
= ira_loop_tree_root
->regno_allocno_map
[regno2
]) == NULL
)
123 return allocnos_have_intersected_live_ranges_p (a1
, a2
);
130 /* This page contains functions used to choose hard registers for
133 /* Array whose element value is TRUE if the corresponding hard
134 register was already allocated for an allocno. */
135 static bool allocated_hardreg_p
[FIRST_PSEUDO_REGISTER
];
137 /* Describes one element in a queue of allocnos whose costs need to be
138 updated. Each allocno in the queue is known to have a cover class. */
139 struct update_cost_queue_elem
141 /* This element is in the queue iff CHECK == update_cost_check. */
144 /* COST_HOP_DIVISOR**N, where N is the length of the shortest path
145 connecting this allocno to the one being allocated. */
148 /* The next allocno in the queue, or null if this is the last element. */
152 /* The first element in a queue of allocnos whose copy costs need to be
153 updated. Null if the queue is empty. */
154 static ira_allocno_t update_cost_queue
;
156 /* The last element in the queue described by update_cost_queue.
157 Not valid if update_cost_queue is null. */
158 static struct update_cost_queue_elem
*update_cost_queue_tail
;
160 /* A pool of elements in the queue described by update_cost_queue.
161 Elements are indexed by ALLOCNO_NUM. */
162 static struct update_cost_queue_elem
*update_cost_queue_elems
;
164 /* The current value of update_copy_cost call count. */
165 static int update_cost_check
;
167 /* Allocate and initialize data necessary for function
168 update_copy_costs. */
170 initiate_cost_update (void)
174 size
= ira_allocnos_num
* sizeof (struct update_cost_queue_elem
);
175 update_cost_queue_elems
176 = (struct update_cost_queue_elem
*) ira_allocate (size
);
177 memset (update_cost_queue_elems
, 0, size
);
178 update_cost_check
= 0;
181 /* Deallocate data used by function update_copy_costs. */
183 finish_cost_update (void)
185 ira_free (update_cost_queue_elems
);
188 /* When we traverse allocnos to update hard register costs, the cost
189 divisor will be multiplied by the following macro value for each
190 hop from given allocno to directly connected allocnos. */
191 #define COST_HOP_DIVISOR 4
193 /* Start a new cost-updating pass. */
195 start_update_cost (void)
198 update_cost_queue
= NULL
;
201 /* Add (ALLOCNO, DIVISOR) to the end of update_cost_queue,
202 unless ALLOCNO is already in the queue, or has no cover class. */
204 queue_update_cost (ira_allocno_t allocno
, int divisor
)
206 struct update_cost_queue_elem
*elem
;
208 elem
= &update_cost_queue_elems
[ALLOCNO_NUM (allocno
)];
209 if (elem
->check
!= update_cost_check
210 && ALLOCNO_COVER_CLASS (allocno
) != NO_REGS
)
212 elem
->check
= update_cost_check
;
213 elem
->divisor
= divisor
;
215 if (update_cost_queue
== NULL
)
216 update_cost_queue
= allocno
;
218 update_cost_queue_tail
->next
= allocno
;
219 update_cost_queue_tail
= elem
;
223 /* Try to remove the first element from update_cost_queue. Return false
224 if the queue was empty, otherwise make (*ALLOCNO, *DIVISOR) describe
225 the removed element. */
227 get_next_update_cost (ira_allocno_t
*allocno
, int *divisor
)
229 struct update_cost_queue_elem
*elem
;
231 if (update_cost_queue
== NULL
)
234 *allocno
= update_cost_queue
;
235 elem
= &update_cost_queue_elems
[ALLOCNO_NUM (*allocno
)];
236 *divisor
= elem
->divisor
;
237 update_cost_queue
= elem
->next
;
241 /* Update the cost of allocnos to increase chances to remove some
242 copies as the result of subsequent assignment. */
244 update_copy_costs (ira_allocno_t allocno
, bool decr_p
)
246 int i
, cost
, update_cost
, hard_regno
, divisor
;
247 enum machine_mode mode
;
248 enum reg_class rclass
, cover_class
;
249 ira_allocno_t another_allocno
;
250 ira_copy_t cp
, next_cp
;
252 hard_regno
= ALLOCNO_HARD_REGNO (allocno
);
253 ira_assert (hard_regno
>= 0);
255 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
256 if (cover_class
== NO_REGS
)
258 i
= ira_class_hard_reg_index
[cover_class
][hard_regno
];
260 rclass
= REGNO_REG_CLASS (hard_regno
);
262 start_update_cost ();
266 mode
= ALLOCNO_MODE (allocno
);
267 for (cp
= ALLOCNO_COPIES (allocno
); cp
!= NULL
; cp
= next_cp
)
269 if (cp
->first
== allocno
)
271 next_cp
= cp
->next_first_allocno_copy
;
272 another_allocno
= cp
->second
;
274 else if (cp
->second
== allocno
)
276 next_cp
= cp
->next_second_allocno_copy
;
277 another_allocno
= cp
->first
;
282 if (cover_class
!= ALLOCNO_COVER_CLASS (another_allocno
)
283 || ALLOCNO_ASSIGNED_P (another_allocno
))
286 cost
= (cp
->second
== allocno
287 ? ira_register_move_cost
[mode
][rclass
][cover_class
]
288 : ira_register_move_cost
[mode
][cover_class
][rclass
]);
292 update_cost
= cp
->freq
* cost
/ divisor
;
293 if (update_cost
== 0)
296 ira_allocate_and_set_or_copy_costs
297 (&ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno
), cover_class
,
298 ALLOCNO_UPDATED_COVER_CLASS_COST (another_allocno
),
299 ALLOCNO_HARD_REG_COSTS (another_allocno
));
300 ira_allocate_and_set_or_copy_costs
301 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno
),
303 ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno
));
304 ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno
)[i
] += update_cost
;
305 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno
)[i
]
308 queue_update_cost (another_allocno
, divisor
* COST_HOP_DIVISOR
);
311 while (get_next_update_cost (&allocno
, &divisor
));
314 /* This function updates COSTS (decrease if DECR_P) by conflict costs
315 of the unassigned allocnos connected by copies with allocnos in
316 update_cost_queue. This update increases chances to remove some
319 update_conflict_hard_regno_costs (int *costs
, bool decr_p
)
321 int i
, cost
, class_size
, freq
, mult
, div
, divisor
;
324 enum reg_class cover_class
;
325 ira_allocno_t allocno
, another_allocno
;
326 ira_copy_t cp
, next_cp
;
328 while (get_next_update_cost (&allocno
, &divisor
))
329 for (cp
= ALLOCNO_COPIES (allocno
); cp
!= NULL
; cp
= next_cp
)
331 if (cp
->first
== allocno
)
333 next_cp
= cp
->next_first_allocno_copy
;
334 another_allocno
= cp
->second
;
336 else if (cp
->second
== allocno
)
338 next_cp
= cp
->next_second_allocno_copy
;
339 another_allocno
= cp
->first
;
343 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
344 if (cover_class
!= ALLOCNO_COVER_CLASS (another_allocno
)
345 || ALLOCNO_ASSIGNED_P (another_allocno
)
346 || ALLOCNO_MAY_BE_SPILLED_P (ALLOCNO_FIRST_COALESCED_ALLOCNO
349 class_size
= ira_class_hard_regs_num
[cover_class
];
350 ira_allocate_and_copy_costs
351 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno
),
352 cover_class
, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno
));
354 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno
);
355 if (conflict_costs
== NULL
)
360 freq
= ALLOCNO_FREQ (another_allocno
);
363 div
= freq
* divisor
;
365 for (i
= class_size
- 1; i
>= 0; i
--)
367 cost
= conflict_costs
[i
] * mult
/ div
;
376 /* Probably 5 hops will be enough. */
378 && divisor
<= (COST_HOP_DIVISOR
382 queue_update_cost (another_allocno
, divisor
* COST_HOP_DIVISOR
);
386 /* Sort allocnos according to the profit of usage of a hard register
387 instead of memory for them. */
389 allocno_cost_compare_func (const void *v1p
, const void *v2p
)
391 ira_allocno_t p1
= *(const ira_allocno_t
*) v1p
;
392 ira_allocno_t p2
= *(const ira_allocno_t
*) v2p
;
395 c1
= ALLOCNO_UPDATED_MEMORY_COST (p1
) - ALLOCNO_UPDATED_COVER_CLASS_COST (p1
);
396 c2
= ALLOCNO_UPDATED_MEMORY_COST (p2
) - ALLOCNO_UPDATED_COVER_CLASS_COST (p2
);
400 /* If regs are equally good, sort by allocno numbers, so that the
401 results of qsort leave nothing to chance. */
402 return ALLOCNO_NUM (p1
) - ALLOCNO_NUM (p2
);
405 /* Print all allocnos coalesced with ALLOCNO. */
407 print_coalesced_allocno (ira_allocno_t allocno
)
411 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
412 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
414 ira_print_expanded_allocno (a
);
417 fprintf (ira_dump_file
, "+");
421 /* Choose a hard register for ALLOCNO (or for all coalesced allocnos
422 represented by ALLOCNO). If RETRY_P is TRUE, it means that the
423 function called from function `ira_reassign_conflict_allocnos' and
424 `allocno_reload_assign'. This function implements the optimistic
425 coalescing too: if we failed to assign a hard register to set of
426 the coalesced allocnos, we put them onto the coloring stack for
427 subsequent separate assigning. */
429 assign_hard_reg (ira_allocno_t allocno
, bool retry_p
)
431 HARD_REG_SET conflicting_regs
;
432 int i
, j
, hard_regno
, best_hard_regno
, class_size
;
433 int cost
, mem_cost
, min_cost
, full_cost
, min_full_cost
, add_cost
;
436 enum reg_class cover_class
, rclass
;
437 enum machine_mode mode
;
438 ira_allocno_t a
, conflict_allocno
;
439 ira_allocno_conflict_iterator aci
;
440 static int costs
[FIRST_PSEUDO_REGISTER
], full_costs
[FIRST_PSEUDO_REGISTER
];
445 ira_assert (! ALLOCNO_ASSIGNED_P (allocno
));
446 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
447 class_size
= ira_class_hard_regs_num
[cover_class
];
448 mode
= ALLOCNO_MODE (allocno
);
449 CLEAR_HARD_REG_SET (conflicting_regs
);
450 best_hard_regno
= -1;
451 memset (full_costs
, 0, sizeof (int) * class_size
);
453 if (allocno_coalesced_p
)
454 bitmap_clear (processed_coalesced_allocno_bitmap
);
455 memset (costs
, 0, sizeof (int) * class_size
);
456 memset (full_costs
, 0, sizeof (int) * class_size
);
458 no_stack_reg_p
= false;
460 start_update_cost ();
461 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
462 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
464 mem_cost
+= ALLOCNO_UPDATED_MEMORY_COST (a
);
465 IOR_HARD_REG_SET (conflicting_regs
,
466 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
467 ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a
),
468 cover_class
, ALLOCNO_HARD_REG_COSTS (a
));
469 a_costs
= ALLOCNO_UPDATED_HARD_REG_COSTS (a
);
471 no_stack_reg_p
= no_stack_reg_p
|| ALLOCNO_TOTAL_NO_STACK_REG_P (a
);
473 for (cost
= ALLOCNO_UPDATED_COVER_CLASS_COST (a
), i
= 0;
478 costs
[i
] += a_costs
[i
];
479 full_costs
[i
] += a_costs
[i
];
484 full_costs
[i
] += cost
;
486 /* Take preferences of conflicting allocnos into account. */
487 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_allocno
, aci
)
488 /* Reload can give another class so we need to check all
490 if (retry_p
|| bitmap_bit_p (consideration_allocno_bitmap
,
491 ALLOCNO_NUM (conflict_allocno
)))
493 ira_assert (cover_class
== ALLOCNO_COVER_CLASS (conflict_allocno
));
494 if (allocno_coalesced_p
)
496 if (bitmap_bit_p (processed_coalesced_allocno_bitmap
,
497 ALLOCNO_NUM (conflict_allocno
)))
499 bitmap_set_bit (processed_coalesced_allocno_bitmap
,
500 ALLOCNO_NUM (conflict_allocno
));
502 if (ALLOCNO_ASSIGNED_P (conflict_allocno
))
504 if ((hard_regno
= ALLOCNO_HARD_REGNO (conflict_allocno
)) >= 0)
508 ira_reg_mode_hard_regset
509 [hard_regno
][ALLOCNO_MODE (conflict_allocno
)]);
510 if (hard_reg_set_subset_p (reg_class_contents
[cover_class
],
516 else if (! ALLOCNO_MAY_BE_SPILLED_P (ALLOCNO_FIRST_COALESCED_ALLOCNO
519 ira_allocate_and_copy_costs
520 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno
),
522 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_allocno
));
524 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno
);
525 if (conflict_costs
!= NULL
)
526 for (j
= class_size
- 1; j
>= 0; j
--)
527 full_costs
[j
] -= conflict_costs
[j
];
528 queue_update_cost (conflict_allocno
, COST_HOP_DIVISOR
);
534 /* Take into account preferences of allocnos connected by copies to
535 the conflict allocnos. */
536 update_conflict_hard_regno_costs (full_costs
, true);
538 /* Take preferences of allocnos connected by copies into
540 start_update_cost ();
541 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
542 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
544 queue_update_cost (a
, COST_HOP_DIVISOR
);
548 update_conflict_hard_regno_costs (full_costs
, false);
549 min_cost
= min_full_cost
= INT_MAX
;
550 /* We don't care about giving callee saved registers to allocnos no
551 living through calls because call clobbered registers are
552 allocated first (it is usual practice to put them first in
554 for (i
= 0; i
< class_size
; i
++)
556 hard_regno
= ira_class_hard_regs
[cover_class
][i
];
559 && FIRST_STACK_REG
<= hard_regno
&& hard_regno
<= LAST_STACK_REG
)
562 if (! ira_hard_reg_not_in_set_p (hard_regno
, mode
, conflicting_regs
)
563 || TEST_HARD_REG_BIT (prohibited_class_mode_regs
[cover_class
][mode
],
567 full_cost
= full_costs
[i
];
568 if (! allocated_hardreg_p
[hard_regno
]
569 && ira_hard_reg_not_in_set_p (hard_regno
, mode
, call_used_reg_set
))
570 /* We need to save/restore the hard register in
571 epilogue/prologue. Therefore we increase the cost. */
573 /* ??? If only part is call clobbered. */
574 rclass
= REGNO_REG_CLASS (hard_regno
);
575 add_cost
= (ira_memory_move_cost
[mode
][rclass
][0]
576 + ira_memory_move_cost
[mode
][rclass
][1] - 1);
578 full_cost
+= add_cost
;
582 if (min_full_cost
> full_cost
)
584 min_full_cost
= full_cost
;
585 best_hard_regno
= hard_regno
;
586 ira_assert (hard_regno
>= 0);
589 if (min_full_cost
> mem_cost
)
591 if (! retry_p
&& internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
592 fprintf (ira_dump_file
, "(memory is more profitable %d vs %d) ",
593 mem_cost
, min_full_cost
);
594 best_hard_regno
= -1;
597 if (best_hard_regno
< 0
598 && ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
) != allocno
)
600 for (j
= 0, a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
601 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
603 ira_assert (! ALLOCNO_IN_GRAPH_P (a
));
604 sorted_allocnos
[j
++] = a
;
608 qsort (sorted_allocnos
, j
, sizeof (ira_allocno_t
),
609 allocno_cost_compare_func
);
610 for (i
= 0; i
< j
; i
++)
612 a
= sorted_allocnos
[i
];
613 ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) = a
;
614 ALLOCNO_NEXT_COALESCED_ALLOCNO (a
) = a
;
615 VEC_safe_push (ira_allocno_t
, heap
, allocno_stack_vec
, a
);
616 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
618 fprintf (ira_dump_file
, " Pushing");
619 print_coalesced_allocno (a
);
620 fprintf (ira_dump_file
, "\n");
625 if (best_hard_regno
>= 0)
626 allocated_hardreg_p
[best_hard_regno
] = true;
627 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
628 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
630 ALLOCNO_HARD_REGNO (a
) = best_hard_regno
;
631 ALLOCNO_ASSIGNED_P (a
) = true;
632 if (best_hard_regno
>= 0)
633 update_copy_costs (a
, true);
634 ira_assert (ALLOCNO_COVER_CLASS (a
) == cover_class
);
635 /* We don't need updated costs anymore: */
636 ira_free_allocno_updated_costs (a
);
640 return best_hard_regno
>= 0;
645 /* This page contains the allocator based on the Chaitin-Briggs algorithm. */
647 /* Bucket of allocnos that can colored currently without spilling. */
648 static ira_allocno_t colorable_allocno_bucket
;
650 /* Bucket of allocnos that might be not colored currently without
652 static ira_allocno_t uncolorable_allocno_bucket
;
654 /* Each element of the array contains the current number of allocnos
655 of given *cover* class in the uncolorable_bucket. */
656 static int uncolorable_allocnos_num
[N_REG_CLASSES
];
658 /* Add ALLOCNO to bucket *BUCKET_PTR. ALLOCNO should be not in a bucket
661 add_allocno_to_bucket (ira_allocno_t allocno
, ira_allocno_t
*bucket_ptr
)
663 ira_allocno_t first_allocno
;
664 enum reg_class cover_class
;
666 if (bucket_ptr
== &uncolorable_allocno_bucket
667 && (cover_class
= ALLOCNO_COVER_CLASS (allocno
)) != NO_REGS
)
669 uncolorable_allocnos_num
[cover_class
]++;
670 ira_assert (uncolorable_allocnos_num
[cover_class
] > 0);
672 first_allocno
= *bucket_ptr
;
673 ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno
) = first_allocno
;
674 ALLOCNO_PREV_BUCKET_ALLOCNO (allocno
) = NULL
;
675 if (first_allocno
!= NULL
)
676 ALLOCNO_PREV_BUCKET_ALLOCNO (first_allocno
) = allocno
;
677 *bucket_ptr
= allocno
;
680 /* The function returns frequency and number of available hard
681 registers for allocnos coalesced with ALLOCNO. */
683 get_coalesced_allocnos_attributes (ira_allocno_t allocno
, int *freq
, int *num
)
689 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
690 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
692 *freq
+= ALLOCNO_FREQ (a
);
693 *num
+= ALLOCNO_AVAILABLE_REGS_NUM (a
);
699 /* Compare two allocnos to define which allocno should be pushed first
700 into the coloring stack. If the return is a negative number, the
701 allocno given by the first parameter will be pushed first. In this
702 case such allocno has less priority than the second one and the
703 hard register will be assigned to it after assignment to the second
704 one. As the result of such assignment order, the second allocno
705 has a better chance to get the best hard register. */
707 bucket_allocno_compare_func (const void *v1p
, const void *v2p
)
709 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
710 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
711 int diff
, a1_freq
, a2_freq
, a1_num
, a2_num
;
713 if ((diff
= (int) ALLOCNO_COVER_CLASS (a2
) - ALLOCNO_COVER_CLASS (a1
)) != 0)
715 get_coalesced_allocnos_attributes (a1
, &a1_freq
, &a1_num
);
716 get_coalesced_allocnos_attributes (a2
, &a2_freq
, &a2_num
);
717 if ((diff
= a2_num
- a1_num
) != 0)
719 else if ((diff
= a1_freq
- a2_freq
) != 0)
721 return ALLOCNO_NUM (a2
) - ALLOCNO_NUM (a1
);
724 /* Sort bucket *BUCKET_PTR and return the result through
727 sort_bucket (ira_allocno_t
*bucket_ptr
)
729 ira_allocno_t a
, head
;
732 for (n
= 0, a
= *bucket_ptr
; a
!= NULL
; a
= ALLOCNO_NEXT_BUCKET_ALLOCNO (a
))
733 sorted_allocnos
[n
++] = a
;
736 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
),
737 bucket_allocno_compare_func
);
739 for (n
--; n
>= 0; n
--)
741 a
= sorted_allocnos
[n
];
742 ALLOCNO_NEXT_BUCKET_ALLOCNO (a
) = head
;
743 ALLOCNO_PREV_BUCKET_ALLOCNO (a
) = NULL
;
745 ALLOCNO_PREV_BUCKET_ALLOCNO (head
) = a
;
751 /* Add ALLOCNO to bucket *BUCKET_PTR maintaining the order according
752 their priority. ALLOCNO should be not in a bucket before the
755 add_allocno_to_ordered_bucket (ira_allocno_t allocno
,
756 ira_allocno_t
*bucket_ptr
)
758 ira_allocno_t before
, after
;
759 enum reg_class cover_class
;
761 if (bucket_ptr
== &uncolorable_allocno_bucket
762 && (cover_class
= ALLOCNO_COVER_CLASS (allocno
)) != NO_REGS
)
764 uncolorable_allocnos_num
[cover_class
]++;
765 ira_assert (uncolorable_allocnos_num
[cover_class
] > 0);
767 for (before
= *bucket_ptr
, after
= NULL
;
769 after
= before
, before
= ALLOCNO_NEXT_BUCKET_ALLOCNO (before
))
770 if (bucket_allocno_compare_func (&allocno
, &before
) < 0)
772 ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno
) = before
;
773 ALLOCNO_PREV_BUCKET_ALLOCNO (allocno
) = after
;
775 *bucket_ptr
= allocno
;
777 ALLOCNO_NEXT_BUCKET_ALLOCNO (after
) = allocno
;
779 ALLOCNO_PREV_BUCKET_ALLOCNO (before
) = allocno
;
782 /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
785 delete_allocno_from_bucket (ira_allocno_t allocno
, ira_allocno_t
*bucket_ptr
)
787 ira_allocno_t prev_allocno
, next_allocno
;
788 enum reg_class cover_class
;
790 if (bucket_ptr
== &uncolorable_allocno_bucket
791 && (cover_class
= ALLOCNO_COVER_CLASS (allocno
)) != NO_REGS
)
793 uncolorable_allocnos_num
[cover_class
]--;
794 ira_assert (uncolorable_allocnos_num
[cover_class
] >= 0);
796 prev_allocno
= ALLOCNO_PREV_BUCKET_ALLOCNO (allocno
);
797 next_allocno
= ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno
);
798 if (prev_allocno
!= NULL
)
799 ALLOCNO_NEXT_BUCKET_ALLOCNO (prev_allocno
) = next_allocno
;
802 ira_assert (*bucket_ptr
== allocno
);
803 *bucket_ptr
= next_allocno
;
805 if (next_allocno
!= NULL
)
806 ALLOCNO_PREV_BUCKET_ALLOCNO (next_allocno
) = prev_allocno
;
809 /* Splay tree for each cover class. The trees are indexed by the
810 corresponding cover classes. Splay trees contain uncolorable
812 static splay_tree uncolorable_allocnos_splay_tree
[N_REG_CLASSES
];
814 /* If the following macro is TRUE, splay tree is used to choose an
815 allocno of the corresponding cover class for spilling. When the
816 number uncolorable allocnos of given cover class decreases to some
817 threshold, linear array search is used to find the best allocno for
818 spilling. This threshold is actually pretty big because, although
819 splay trees asymptotically is much faster, each splay tree
820 operation is sufficiently costly especially taking cache locality
822 #define USE_SPLAY_P(CLASS) (uncolorable_allocnos_num[CLASS] > 4000)
824 /* Put ALLOCNO onto the coloring stack without removing it from its
825 bucket. Pushing allocno to the coloring stack can result in moving
826 conflicting allocnos from the uncolorable bucket to the colorable
829 push_allocno_to_stack (ira_allocno_t allocno
)
831 int conflicts_num
, conflict_size
, size
;
832 ira_allocno_t a
, conflict_allocno
;
833 enum reg_class cover_class
;
834 ira_allocno_conflict_iterator aci
;
836 ALLOCNO_IN_GRAPH_P (allocno
) = false;
837 VEC_safe_push (ira_allocno_t
, heap
, allocno_stack_vec
, allocno
);
838 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
839 if (cover_class
== NO_REGS
)
841 size
= ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE (allocno
)];
842 if (allocno_coalesced_p
)
843 bitmap_clear (processed_coalesced_allocno_bitmap
);
844 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
845 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
847 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_allocno
, aci
)
849 conflict_allocno
= ALLOCNO_FIRST_COALESCED_ALLOCNO (conflict_allocno
);
850 if (bitmap_bit_p (coloring_allocno_bitmap
,
851 ALLOCNO_NUM (conflict_allocno
)))
853 ira_assert (cover_class
854 == ALLOCNO_COVER_CLASS (conflict_allocno
));
855 if (allocno_coalesced_p
)
857 if (bitmap_bit_p (processed_coalesced_allocno_bitmap
,
858 ALLOCNO_NUM (conflict_allocno
)))
860 bitmap_set_bit (processed_coalesced_allocno_bitmap
,
861 ALLOCNO_NUM (conflict_allocno
));
863 if (ALLOCNO_IN_GRAPH_P (conflict_allocno
)
864 && ! ALLOCNO_ASSIGNED_P (conflict_allocno
))
866 conflicts_num
= ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno
);
868 = (ira_reg_class_nregs
869 [cover_class
][ALLOCNO_MODE (conflict_allocno
)]);
871 (ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno
) >= size
);
872 if (conflicts_num
+ conflict_size
873 <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno
))
875 ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno
) -= size
;
879 = ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno
) - size
;
880 if (uncolorable_allocnos_splay_tree
[cover_class
] != NULL
881 && !ALLOCNO_SPLAY_REMOVED_P (conflict_allocno
)
882 && USE_SPLAY_P (cover_class
))
886 (uncolorable_allocnos_splay_tree
[cover_class
],
887 (splay_tree_key
) conflict_allocno
) != NULL
);
889 (uncolorable_allocnos_splay_tree
[cover_class
],
890 (splay_tree_key
) conflict_allocno
);
891 ALLOCNO_SPLAY_REMOVED_P (conflict_allocno
) = true;
892 VEC_safe_push (ira_allocno_t
, heap
,
893 removed_splay_allocno_vec
,
896 ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno
) = conflicts_num
;
897 if (conflicts_num
+ conflict_size
898 <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno
))
900 delete_allocno_from_bucket
901 (conflict_allocno
, &uncolorable_allocno_bucket
);
902 add_allocno_to_ordered_bucket
903 (conflict_allocno
, &colorable_allocno_bucket
);
913 /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
914 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
916 remove_allocno_from_bucket_and_push (ira_allocno_t allocno
, bool colorable_p
)
918 enum reg_class cover_class
;
921 delete_allocno_from_bucket (allocno
, &colorable_allocno_bucket
);
923 delete_allocno_from_bucket (allocno
, &uncolorable_allocno_bucket
);
924 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
926 fprintf (ira_dump_file
, " Pushing");
927 print_coalesced_allocno (allocno
);
928 fprintf (ira_dump_file
, "%s\n", colorable_p
? "" : "(potential spill)");
930 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
931 ira_assert ((colorable_p
932 && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno
)
933 + ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE (allocno
)]
934 <= ALLOCNO_AVAILABLE_REGS_NUM (allocno
)))
936 && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno
)
937 + ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE
939 > ALLOCNO_AVAILABLE_REGS_NUM (allocno
))));
941 ALLOCNO_MAY_BE_SPILLED_P (allocno
) = true;
942 push_allocno_to_stack (allocno
);
945 /* Put all allocnos from colorable bucket onto the coloring stack. */
947 push_only_colorable (void)
949 sort_bucket (&colorable_allocno_bucket
);
950 for (;colorable_allocno_bucket
!= NULL
;)
951 remove_allocno_from_bucket_and_push (colorable_allocno_bucket
, true);
954 /* Puts ALLOCNO chosen for potential spilling onto the coloring
957 push_allocno_to_spill (ira_allocno_t allocno
)
959 delete_allocno_from_bucket (allocno
, &uncolorable_allocno_bucket
);
960 ALLOCNO_MAY_BE_SPILLED_P (allocno
) = true;
961 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
962 fprintf (ira_dump_file
, " Pushing p%d(%d) (potential spill)\n",
963 ALLOCNO_NUM (allocno
), ALLOCNO_REGNO (allocno
));
964 push_allocno_to_stack (allocno
);
967 /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
968 loop given by its LOOP_NODE. */
970 ira_loop_edge_freq (ira_loop_tree_node_t loop_node
, int regno
, bool exit_p
)
975 VEC (edge
, heap
) *edges
;
977 ira_assert (loop_node
->loop
!= NULL
978 && (regno
< 0 || regno
>= FIRST_PSEUDO_REGISTER
));
982 FOR_EACH_EDGE (e
, ei
, loop_node
->loop
->header
->preds
)
983 if (e
->src
!= loop_node
->loop
->latch
985 || (bitmap_bit_p (DF_LR_OUT (e
->src
), regno
)
986 && bitmap_bit_p (DF_LR_IN (e
->dest
), regno
))))
987 freq
+= EDGE_FREQUENCY (e
);
991 edges
= get_loop_exit_edges (loop_node
->loop
);
992 for (i
= 0; VEC_iterate (edge
, edges
, i
, e
); i
++)
994 || (bitmap_bit_p (DF_LR_OUT (e
->src
), regno
)
995 && bitmap_bit_p (DF_LR_IN (e
->dest
), regno
)))
996 freq
+= EDGE_FREQUENCY (e
);
997 VEC_free (edge
, heap
, edges
);
1000 return REG_FREQ_FROM_EDGE_FREQ (freq
);
1003 /* Calculate and return the cost of putting allocno A into memory. */
1005 calculate_allocno_spill_cost (ira_allocno_t a
)
1008 enum machine_mode mode
;
1009 enum reg_class rclass
;
1010 ira_allocno_t parent_allocno
;
1011 ira_loop_tree_node_t parent_node
, loop_node
;
1013 regno
= ALLOCNO_REGNO (a
);
1014 cost
= ALLOCNO_UPDATED_MEMORY_COST (a
) - ALLOCNO_UPDATED_COVER_CLASS_COST (a
);
1015 if (ALLOCNO_CAP (a
) != NULL
)
1017 loop_node
= ALLOCNO_LOOP_TREE_NODE (a
);
1018 if ((parent_node
= loop_node
->parent
) == NULL
)
1020 if ((parent_allocno
= parent_node
->regno_allocno_map
[regno
]) == NULL
)
1022 mode
= ALLOCNO_MODE (a
);
1023 rclass
= ALLOCNO_COVER_CLASS (a
);
1024 if (ALLOCNO_HARD_REGNO (parent_allocno
) < 0)
1025 cost
-= (ira_memory_move_cost
[mode
][rclass
][0]
1026 * ira_loop_edge_freq (loop_node
, regno
, true)
1027 + ira_memory_move_cost
[mode
][rclass
][1]
1028 * ira_loop_edge_freq (loop_node
, regno
, false));
1030 cost
+= ((ira_memory_move_cost
[mode
][rclass
][1]
1031 * ira_loop_edge_freq (loop_node
, regno
, true)
1032 + ira_memory_move_cost
[mode
][rclass
][0]
1033 * ira_loop_edge_freq (loop_node
, regno
, false))
1034 - (ira_register_move_cost
[mode
][rclass
][rclass
]
1035 * (ira_loop_edge_freq (loop_node
, regno
, false)
1036 + ira_loop_edge_freq (loop_node
, regno
, true))));
1040 /* Compare keys in the splay tree used to choose best allocno for
1041 spilling. The best allocno has the minimal key. */
1043 allocno_spill_priority_compare (splay_tree_key k1
, splay_tree_key k2
)
1045 int pri1
, pri2
, diff
;
1046 ira_allocno_t a1
= (ira_allocno_t
) k1
, a2
= (ira_allocno_t
) k2
;
1048 pri1
= (ALLOCNO_TEMP (a1
)
1049 / (ALLOCNO_LEFT_CONFLICTS_NUM (a1
)
1050 * ira_reg_class_nregs
[ALLOCNO_COVER_CLASS (a1
)][ALLOCNO_MODE (a1
)]
1052 pri2
= (ALLOCNO_TEMP (a2
)
1053 / (ALLOCNO_LEFT_CONFLICTS_NUM (a2
)
1054 * ira_reg_class_nregs
[ALLOCNO_COVER_CLASS (a2
)][ALLOCNO_MODE (a2
)]
1056 if ((diff
= pri1
- pri2
) != 0)
1058 if ((diff
= ALLOCNO_TEMP (a1
) - ALLOCNO_TEMP (a2
)) != 0)
1060 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
1063 /* Allocate data of SIZE for the splay trees. We allocate only spay
1064 tree roots or splay tree nodes. If you change this, please rewrite
1067 splay_tree_allocate (int size
, void *data ATTRIBUTE_UNUSED
)
1069 if (size
!= sizeof (struct splay_tree_node_s
))
1070 return ira_allocate (size
);
1071 return pool_alloc (splay_tree_node_pool
);
1074 /* Free data NODE for the splay trees. We allocate and free only spay
1075 tree roots or splay tree nodes. If you change this, please rewrite
1078 splay_tree_free (void *node
, void *data ATTRIBUTE_UNUSED
)
1081 enum reg_class cover_class
;
1083 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1085 cover_class
= ira_reg_class_cover
[i
];
1086 if (node
== uncolorable_allocnos_splay_tree
[cover_class
])
1092 pool_free (splay_tree_node_pool
, node
);
1095 /* Push allocnos to the coloring stack. The order of allocnos in the
1096 stack defines the order for the subsequent coloring. */
1098 push_allocnos_to_stack (void)
1100 ira_allocno_t allocno
, a
, i_allocno
, *allocno_vec
;
1101 enum reg_class cover_class
, rclass
;
1102 int allocno_pri
, i_allocno_pri
, allocno_cost
, i_allocno_cost
;
1103 int i
, j
, num
, cover_class_allocnos_num
[N_REG_CLASSES
];
1104 ira_allocno_t
*cover_class_allocnos
[N_REG_CLASSES
];
1108 VEC_truncate(ira_allocno_t
, removed_splay_allocno_vec
, 0);
1109 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1111 cover_class
= ira_reg_class_cover
[i
];
1112 cover_class_allocnos_num
[cover_class
] = 0;
1113 cover_class_allocnos
[cover_class
] = NULL
;
1114 uncolorable_allocnos_splay_tree
[cover_class
] = NULL
;
1116 /* Calculate uncolorable allocno spill costs. */
1117 for (allocno
= uncolorable_allocno_bucket
;
1119 allocno
= ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno
))
1120 if ((cover_class
= ALLOCNO_COVER_CLASS (allocno
)) != NO_REGS
)
1122 cover_class_allocnos_num
[cover_class
]++;
1124 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
1125 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1127 cost
+= calculate_allocno_spill_cost (a
);
1131 /* ??? Remove cost of copies between the coalesced
1133 ALLOCNO_TEMP (allocno
) = cost
;
1135 /* Define place where to put uncolorable allocnos of the same cover
1137 for (num
= i
= 0; i
< ira_reg_class_cover_size
; i
++)
1139 cover_class
= ira_reg_class_cover
[i
];
1140 ira_assert (cover_class_allocnos_num
[cover_class
]
1141 == uncolorable_allocnos_num
[cover_class
]);
1142 if (cover_class_allocnos_num
[cover_class
] != 0)
1144 cover_class_allocnos
[cover_class
] = allocnos_for_spilling
+ num
;
1145 num
+= cover_class_allocnos_num
[cover_class
];
1146 cover_class_allocnos_num
[cover_class
] = 0;
1148 if (USE_SPLAY_P (cover_class
))
1149 uncolorable_allocnos_splay_tree
[cover_class
]
1150 = splay_tree_new_with_allocator (allocno_spill_priority_compare
,
1151 NULL
, NULL
, splay_tree_allocate
,
1152 splay_tree_free
, NULL
);
1154 ira_assert (num
<= ira_allocnos_num
);
1155 /* Collect uncolorable allocnos of each cover class. */
1156 for (allocno
= uncolorable_allocno_bucket
;
1158 allocno
= ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno
))
1159 if ((cover_class
= ALLOCNO_COVER_CLASS (allocno
)) != NO_REGS
)
1161 cover_class_allocnos
1162 [cover_class
][cover_class_allocnos_num
[cover_class
]++] = allocno
;
1163 if (uncolorable_allocnos_splay_tree
[cover_class
] != NULL
)
1164 splay_tree_insert (uncolorable_allocnos_splay_tree
[cover_class
],
1165 (splay_tree_key
) allocno
,
1166 (splay_tree_value
) allocno
);
1170 push_only_colorable ();
1171 allocno
= uncolorable_allocno_bucket
;
1172 if (allocno
== NULL
)
1174 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
1175 if (cover_class
== NO_REGS
)
1177 push_allocno_to_spill (allocno
);
1180 /* Potential spilling. */
1182 (ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE (allocno
)] > 0);
1183 if (USE_SPLAY_P (cover_class
))
1185 for (;VEC_length (ira_allocno_t
, removed_splay_allocno_vec
) != 0;)
1187 allocno
= VEC_pop (ira_allocno_t
, removed_splay_allocno_vec
);
1188 ALLOCNO_SPLAY_REMOVED_P (allocno
) = false;
1189 rclass
= ALLOCNO_COVER_CLASS (allocno
);
1190 if (ALLOCNO_LEFT_CONFLICTS_NUM (allocno
)
1191 + ira_reg_class_nregs
[rclass
][ALLOCNO_MODE (allocno
)]
1192 > ALLOCNO_AVAILABLE_REGS_NUM (allocno
))
1194 (uncolorable_allocnos_splay_tree
[rclass
],
1195 (splay_tree_key
) allocno
, (splay_tree_value
) allocno
);
1197 allocno
= ((ira_allocno_t
)
1199 (uncolorable_allocnos_splay_tree
[cover_class
])->key
);
1200 splay_tree_remove (uncolorable_allocnos_splay_tree
[cover_class
],
1201 (splay_tree_key
) allocno
);
1205 num
= cover_class_allocnos_num
[cover_class
];
1206 ira_assert (num
> 0);
1207 allocno_vec
= cover_class_allocnos
[cover_class
];
1209 allocno_pri
= allocno_cost
= 0;
1210 /* Sort uncolorable allocno to find the one with the lowest
1212 for (i
= 0, j
= num
- 1; i
<= j
;)
1214 i_allocno
= allocno_vec
[i
];
1215 if (! ALLOCNO_IN_GRAPH_P (i_allocno
)
1216 && ALLOCNO_IN_GRAPH_P (allocno_vec
[j
]))
1218 i_allocno
= allocno_vec
[j
];
1219 allocno_vec
[j
] = allocno_vec
[i
];
1220 allocno_vec
[i
] = i_allocno
;
1222 if (ALLOCNO_IN_GRAPH_P (i_allocno
))
1225 ira_assert (ALLOCNO_TEMP (i_allocno
) != INT_MAX
);
1226 i_allocno_cost
= ALLOCNO_TEMP (i_allocno
);
1229 / (ALLOCNO_LEFT_CONFLICTS_NUM (i_allocno
)
1230 * ira_reg_class_nregs
[ALLOCNO_COVER_CLASS
1232 [ALLOCNO_MODE (i_allocno
)] + 1));
1234 || (! ALLOCNO_BAD_SPILL_P (i_allocno
)
1235 && ALLOCNO_BAD_SPILL_P (allocno
))
1236 || allocno_pri
> i_allocno_pri
1237 || (allocno_pri
== i_allocno_pri
1238 && (allocno_cost
> i_allocno_cost
1239 || (allocno_cost
== i_allocno_cost
1240 && (ALLOCNO_NUM (allocno
)
1241 > ALLOCNO_NUM (i_allocno
))))))
1243 allocno
= i_allocno
;
1244 allocno_cost
= i_allocno_cost
;
1245 allocno_pri
= i_allocno_pri
;
1248 if (! ALLOCNO_IN_GRAPH_P (allocno_vec
[j
]))
1251 ira_assert (allocno
!= NULL
&& j
>= 0);
1252 cover_class_allocnos_num
[cover_class
] = j
+ 1;
1254 ira_assert (ALLOCNO_IN_GRAPH_P (allocno
)
1255 && ALLOCNO_COVER_CLASS (allocno
) == cover_class
1256 && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno
)
1257 + ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE
1259 > ALLOCNO_AVAILABLE_REGS_NUM (allocno
)));
1260 remove_allocno_from_bucket_and_push (allocno
, false);
1262 ira_assert (colorable_allocno_bucket
== NULL
1263 && uncolorable_allocno_bucket
== NULL
);
1264 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1266 cover_class
= ira_reg_class_cover
[i
];
1267 ira_assert (uncolorable_allocnos_num
[cover_class
] == 0);
1268 if (uncolorable_allocnos_splay_tree
[cover_class
] != NULL
)
1269 splay_tree_delete (uncolorable_allocnos_splay_tree
[cover_class
]);
1273 /* Pop the coloring stack and assign hard registers to the popped
1276 pop_allocnos_from_stack (void)
1278 ira_allocno_t allocno
;
1279 enum reg_class cover_class
;
1281 for (;VEC_length (ira_allocno_t
, allocno_stack_vec
) != 0;)
1283 allocno
= VEC_pop (ira_allocno_t
, allocno_stack_vec
);
1284 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
1285 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1287 fprintf (ira_dump_file
, " Popping");
1288 print_coalesced_allocno (allocno
);
1289 fprintf (ira_dump_file
, " -- ");
1291 if (cover_class
== NO_REGS
)
1293 ALLOCNO_HARD_REGNO (allocno
) = -1;
1294 ALLOCNO_ASSIGNED_P (allocno
) = true;
1295 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno
) == NULL
);
1297 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno
) == NULL
);
1298 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1299 fprintf (ira_dump_file
, "assign memory\n");
1301 else if (assign_hard_reg (allocno
, false))
1303 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1304 fprintf (ira_dump_file
, "assign reg %d\n",
1305 ALLOCNO_HARD_REGNO (allocno
));
1307 else if (ALLOCNO_ASSIGNED_P (allocno
))
1309 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1310 fprintf (ira_dump_file
, "spill\n");
1312 ALLOCNO_IN_GRAPH_P (allocno
) = true;
1316 /* Set up number of available hard registers for ALLOCNO. */
1318 setup_allocno_available_regs_num (ira_allocno_t allocno
)
1320 int i
, n
, hard_regs_num
;
1321 enum reg_class cover_class
;
1323 HARD_REG_SET temp_set
;
1325 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
1326 ALLOCNO_AVAILABLE_REGS_NUM (allocno
) = ira_available_class_regs
[cover_class
];
1327 if (cover_class
== NO_REGS
)
1329 CLEAR_HARD_REG_SET (temp_set
);
1330 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) == allocno
);
1331 hard_regs_num
= ira_class_hard_regs_num
[cover_class
];
1332 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
1333 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1335 IOR_HARD_REG_SET (temp_set
, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
1339 for (n
= 0, i
= hard_regs_num
- 1; i
>= 0; i
--)
1340 if (TEST_HARD_REG_BIT (temp_set
, ira_class_hard_regs
[cover_class
][i
]))
1342 if (internal_flag_ira_verbose
> 2 && n
> 0 && ira_dump_file
!= NULL
)
1343 fprintf (ira_dump_file
, " Reg %d of %s has %d regs less\n",
1344 ALLOCNO_REGNO (allocno
), reg_class_names
[cover_class
], n
);
1345 ALLOCNO_AVAILABLE_REGS_NUM (allocno
) -= n
;
1348 /* Set up ALLOCNO_LEFT_CONFLICTS_NUM for ALLOCNO. */
1350 setup_allocno_left_conflicts_num (ira_allocno_t allocno
)
1352 int i
, hard_regs_num
, hard_regno
, conflict_allocnos_size
;
1353 ira_allocno_t a
, conflict_allocno
;
1354 enum reg_class cover_class
;
1355 HARD_REG_SET temp_set
;
1356 ira_allocno_conflict_iterator aci
;
1358 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
1359 hard_regs_num
= ira_class_hard_regs_num
[cover_class
];
1360 CLEAR_HARD_REG_SET (temp_set
);
1361 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) == allocno
);
1362 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
1363 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1365 IOR_HARD_REG_SET (temp_set
, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
1369 AND_HARD_REG_SET (temp_set
, reg_class_contents
[cover_class
]);
1370 AND_COMPL_HARD_REG_SET (temp_set
, ira_no_alloc_regs
);
1371 conflict_allocnos_size
= 0;
1372 if (! hard_reg_set_empty_p (temp_set
))
1373 for (i
= 0; i
< (int) hard_regs_num
; i
++)
1375 hard_regno
= ira_class_hard_regs
[cover_class
][i
];
1376 if (TEST_HARD_REG_BIT (temp_set
, hard_regno
))
1378 conflict_allocnos_size
++;
1379 CLEAR_HARD_REG_BIT (temp_set
, hard_regno
);
1380 if (hard_reg_set_empty_p (temp_set
))
1384 CLEAR_HARD_REG_SET (temp_set
);
1385 if (allocno_coalesced_p
)
1386 bitmap_clear (processed_coalesced_allocno_bitmap
);
1387 if (cover_class
!= NO_REGS
)
1388 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
1389 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1391 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_allocno
, aci
)
1394 = ALLOCNO_FIRST_COALESCED_ALLOCNO (conflict_allocno
);
1395 if (bitmap_bit_p (consideration_allocno_bitmap
,
1396 ALLOCNO_NUM (conflict_allocno
)))
1398 ira_assert (cover_class
1399 == ALLOCNO_COVER_CLASS (conflict_allocno
));
1400 if (allocno_coalesced_p
)
1402 if (bitmap_bit_p (processed_coalesced_allocno_bitmap
,
1403 ALLOCNO_NUM (conflict_allocno
)))
1405 bitmap_set_bit (processed_coalesced_allocno_bitmap
,
1406 ALLOCNO_NUM (conflict_allocno
));
1408 if (! ALLOCNO_ASSIGNED_P (conflict_allocno
))
1409 conflict_allocnos_size
1410 += (ira_reg_class_nregs
1411 [cover_class
][ALLOCNO_MODE (conflict_allocno
)]);
1412 else if ((hard_regno
= ALLOCNO_HARD_REGNO (conflict_allocno
))
1415 int last
= (hard_regno
1417 [hard_regno
][ALLOCNO_MODE (conflict_allocno
)]);
1419 while (hard_regno
< last
)
1421 if (! TEST_HARD_REG_BIT (temp_set
, hard_regno
))
1423 conflict_allocnos_size
++;
1424 SET_HARD_REG_BIT (temp_set
, hard_regno
);
1434 ALLOCNO_LEFT_CONFLICTS_NUM (allocno
) = conflict_allocnos_size
;
1437 /* Put ALLOCNO in a bucket corresponding to its number and size of its
1438 conflicting allocnos and hard registers. */
1440 put_allocno_into_bucket (ira_allocno_t allocno
)
1443 enum reg_class cover_class
;
1445 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
1446 hard_regs_num
= ira_class_hard_regs_num
[cover_class
];
1447 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) != allocno
)
1449 ALLOCNO_IN_GRAPH_P (allocno
) = true;
1450 setup_allocno_left_conflicts_num (allocno
);
1451 setup_allocno_available_regs_num (allocno
);
1452 if (ALLOCNO_LEFT_CONFLICTS_NUM (allocno
)
1453 + ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE (allocno
)]
1454 <= ALLOCNO_AVAILABLE_REGS_NUM (allocno
))
1455 add_allocno_to_bucket (allocno
, &colorable_allocno_bucket
);
1457 add_allocno_to_bucket (allocno
, &uncolorable_allocno_bucket
);
1460 /* The function is used to sort allocnos according to their execution
1463 copy_freq_compare_func (const void *v1p
, const void *v2p
)
1465 ira_copy_t cp1
= *(const ira_copy_t
*) v1p
, cp2
= *(const ira_copy_t
*) v2p
;
1473 /* If freqencies are equal, sort by copies, so that the results of
1474 qsort leave nothing to chance. */
1475 return cp1
->num
- cp2
->num
;
1478 /* Merge two sets of coalesced allocnos given correspondingly by
1479 allocnos A1 and A2 (more accurately merging A2 set into A1
1482 merge_allocnos (ira_allocno_t a1
, ira_allocno_t a2
)
1484 ira_allocno_t a
, first
, last
, next
;
1486 first
= ALLOCNO_FIRST_COALESCED_ALLOCNO (a1
);
1487 if (first
== ALLOCNO_FIRST_COALESCED_ALLOCNO (a2
))
1489 for (last
= a2
, a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a2
);;
1490 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1492 ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) = first
;
1497 next
= ALLOCNO_NEXT_COALESCED_ALLOCNO (first
);
1498 ALLOCNO_NEXT_COALESCED_ALLOCNO (first
) = a2
;
1499 ALLOCNO_NEXT_COALESCED_ALLOCNO (last
) = next
;
1502 /* Return TRUE if there are conflicting allocnos from two sets of
1503 coalesced allocnos given correspondingly by allocnos A1 and A2. If
1504 RELOAD_P is TRUE, we use live ranges to find conflicts because
1505 conflicts are represented only for allocnos of the same cover class
1506 and during the reload pass we coalesce allocnos for sharing stack
1509 coalesced_allocno_conflict_p (ira_allocno_t a1
, ira_allocno_t a2
,
1512 ira_allocno_t a
, conflict_allocno
;
1513 ira_allocno_conflict_iterator aci
;
1515 if (allocno_coalesced_p
)
1517 bitmap_clear (processed_coalesced_allocno_bitmap
);
1518 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a1
);;
1519 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1521 bitmap_set_bit (processed_coalesced_allocno_bitmap
, ALLOCNO_NUM (a
));
1526 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a2
);;
1527 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1531 for (conflict_allocno
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a1
);;
1533 = ALLOCNO_NEXT_COALESCED_ALLOCNO (conflict_allocno
))
1535 if (allocnos_have_intersected_live_ranges_p (a
,
1538 if (conflict_allocno
== a1
)
1544 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_allocno
, aci
)
1545 if (conflict_allocno
== a1
1546 || (allocno_coalesced_p
1547 && bitmap_bit_p (processed_coalesced_allocno_bitmap
,
1548 ALLOCNO_NUM (conflict_allocno
))))
1557 /* The major function for aggressive allocno coalescing. For the
1558 reload pass (RELOAD_P) we coalesce only spilled allocnos. If some
1559 allocnos have been coalesced, we set up flag
1560 allocno_coalesced_p. */
1562 coalesce_allocnos (bool reload_p
)
1565 ira_copy_t cp
, next_cp
, *sorted_copies
;
1566 enum reg_class cover_class
;
1567 enum machine_mode mode
;
1569 int i
, n
, cp_num
, regno
;
1572 sorted_copies
= (ira_copy_t
*) ira_allocate (ira_copies_num
1573 * sizeof (ira_copy_t
));
1575 /* Collect copies. */
1576 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, j
, bi
)
1578 a
= ira_allocnos
[j
];
1579 regno
= ALLOCNO_REGNO (a
);
1580 if ((! reload_p
&& ALLOCNO_ASSIGNED_P (a
))
1582 && (! ALLOCNO_ASSIGNED_P (a
) || ALLOCNO_HARD_REGNO (a
) >= 0
1583 || (regno
< ira_reg_equiv_len
1584 && (ira_reg_equiv_const
[regno
] != NULL_RTX
1585 || ira_reg_equiv_invariant_p
[regno
])))))
1587 cover_class
= ALLOCNO_COVER_CLASS (a
);
1588 mode
= ALLOCNO_MODE (a
);
1589 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
1593 next_cp
= cp
->next_first_allocno_copy
;
1594 regno
= ALLOCNO_REGNO (cp
->second
);
1596 || (ALLOCNO_COVER_CLASS (cp
->second
) == cover_class
1597 && ALLOCNO_MODE (cp
->second
) == mode
))
1598 && (cp
->insn
!= NULL
|| cp
->constraint_p
)
1599 && ((! reload_p
&& ! ALLOCNO_ASSIGNED_P (cp
->second
))
1601 && ALLOCNO_ASSIGNED_P (cp
->second
)
1602 && ALLOCNO_HARD_REGNO (cp
->second
) < 0
1603 && (regno
>= ira_reg_equiv_len
1604 || (! ira_reg_equiv_invariant_p
[regno
]
1605 && ira_reg_equiv_const
[regno
] == NULL_RTX
)))))
1606 sorted_copies
[cp_num
++] = cp
;
1608 else if (cp
->second
== a
)
1609 next_cp
= cp
->next_second_allocno_copy
;
1614 qsort (sorted_copies
, cp_num
, sizeof (ira_copy_t
), copy_freq_compare_func
);
1615 /* Coalesced copies, most frequently executed first. */
1616 for (; cp_num
!= 0;)
1618 for (i
= 0; i
< cp_num
; i
++)
1620 cp
= sorted_copies
[i
];
1621 if (! coalesced_allocno_conflict_p (cp
->first
, cp
->second
, reload_p
))
1623 allocno_coalesced_p
= true;
1624 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1627 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
1628 cp
->num
, ALLOCNO_NUM (cp
->first
), ALLOCNO_REGNO (cp
->first
),
1629 ALLOCNO_NUM (cp
->second
), ALLOCNO_REGNO (cp
->second
),
1631 merge_allocnos (cp
->first
, cp
->second
);
1636 /* Collect the rest of copies. */
1637 for (n
= 0; i
< cp_num
; i
++)
1639 cp
= sorted_copies
[i
];
1640 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (cp
->first
)
1641 != ALLOCNO_FIRST_COALESCED_ALLOCNO (cp
->second
))
1642 sorted_copies
[n
++] = cp
;
1646 ira_free (sorted_copies
);
1649 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
1650 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
1652 color_allocnos (void)
1658 allocno_coalesced_p
= false;
1659 processed_coalesced_allocno_bitmap
= ira_allocate_bitmap ();
1660 if (flag_ira_coalesce
)
1661 coalesce_allocnos (false);
1662 /* Put the allocnos into the corresponding buckets. */
1663 colorable_allocno_bucket
= NULL
;
1664 uncolorable_allocno_bucket
= NULL
;
1665 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
1667 a
= ira_allocnos
[i
];
1668 if (ALLOCNO_COVER_CLASS (a
) == NO_REGS
)
1670 ALLOCNO_HARD_REGNO (a
) = -1;
1671 ALLOCNO_ASSIGNED_P (a
) = true;
1672 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
1673 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
1674 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1676 fprintf (ira_dump_file
, " Spill");
1677 print_coalesced_allocno (a
);
1678 fprintf (ira_dump_file
, "\n");
1682 put_allocno_into_bucket (a
);
1684 push_allocnos_to_stack ();
1685 pop_allocnos_from_stack ();
1686 if (flag_ira_coalesce
)
1687 /* We don't need coalesced allocnos for ira_reassign_pseudos. */
1688 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
1690 a
= ira_allocnos
[i
];
1691 ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) = a
;
1692 ALLOCNO_NEXT_COALESCED_ALLOCNO (a
) = a
;
1694 ira_free_bitmap (processed_coalesced_allocno_bitmap
);
1695 allocno_coalesced_p
= false;
1700 /* Output information about the loop given by its LOOP_TREE_NODE. */
1702 print_loop_title (ira_loop_tree_node_t loop_tree_node
)
1706 ira_loop_tree_node_t subloop_node
, dest_loop_node
;
1710 ira_assert (loop_tree_node
->loop
!= NULL
);
1711 fprintf (ira_dump_file
,
1712 "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
1713 loop_tree_node
->loop
->num
,
1714 (loop_tree_node
->parent
== NULL
1715 ? -1 : loop_tree_node
->parent
->loop
->num
),
1716 loop_tree_node
->loop
->header
->index
,
1717 loop_depth (loop_tree_node
->loop
));
1718 for (subloop_node
= loop_tree_node
->children
;
1719 subloop_node
!= NULL
;
1720 subloop_node
= subloop_node
->next
)
1721 if (subloop_node
->bb
!= NULL
)
1723 fprintf (ira_dump_file
, " %d", subloop_node
->bb
->index
);
1724 FOR_EACH_EDGE (e
, ei
, subloop_node
->bb
->succs
)
1725 if (e
->dest
!= EXIT_BLOCK_PTR
1726 && ((dest_loop_node
= IRA_BB_NODE (e
->dest
)->parent
)
1728 fprintf (ira_dump_file
, "(->%d:l%d)",
1729 e
->dest
->index
, dest_loop_node
->loop
->num
);
1731 fprintf (ira_dump_file
, "\n all:");
1732 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->all_allocnos
, 0, j
, bi
)
1733 fprintf (ira_dump_file
, " %dr%d", j
, ALLOCNO_REGNO (ira_allocnos
[j
]));
1734 fprintf (ira_dump_file
, "\n modified regnos:");
1735 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->modified_regnos
, 0, j
, bi
)
1736 fprintf (ira_dump_file
, " %d", j
);
1737 fprintf (ira_dump_file
, "\n border:");
1738 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->border_allocnos
, 0, j
, bi
)
1739 fprintf (ira_dump_file
, " %dr%d", j
, ALLOCNO_REGNO (ira_allocnos
[j
]));
1740 fprintf (ira_dump_file
, "\n Pressure:");
1741 for (j
= 0; (int) j
< ira_reg_class_cover_size
; j
++)
1743 enum reg_class cover_class
;
1745 cover_class
= ira_reg_class_cover
[j
];
1746 if (loop_tree_node
->reg_pressure
[cover_class
] == 0)
1748 fprintf (ira_dump_file
, " %s=%d", reg_class_names
[cover_class
],
1749 loop_tree_node
->reg_pressure
[cover_class
]);
1751 fprintf (ira_dump_file
, "\n");
1754 /* Color the allocnos inside loop (in the extreme case it can be all
1755 of the function) given the corresponding LOOP_TREE_NODE. The
1756 function is called for each loop during top-down traverse of the
1759 color_pass (ira_loop_tree_node_t loop_tree_node
)
1761 int regno
, hard_regno
, index
= -1;
1762 int cost
, exit_freq
, enter_freq
;
1765 enum machine_mode mode
;
1766 enum reg_class rclass
, cover_class
;
1767 ira_allocno_t a
, subloop_allocno
;
1768 ira_loop_tree_node_t subloop_node
;
1770 ira_assert (loop_tree_node
->bb
== NULL
);
1771 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
1772 print_loop_title (loop_tree_node
);
1774 bitmap_copy (coloring_allocno_bitmap
, loop_tree_node
->all_allocnos
);
1775 bitmap_copy (consideration_allocno_bitmap
, coloring_allocno_bitmap
);
1776 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
1778 a
= ira_allocnos
[j
];
1779 if (! ALLOCNO_ASSIGNED_P (a
))
1781 bitmap_clear_bit (coloring_allocno_bitmap
, ALLOCNO_NUM (a
));
1783 /* Color all mentioned allocnos including transparent ones. */
1785 /* Process caps. They are processed just once. */
1786 if (flag_ira_algorithm
== IRA_ALGORITHM_MIXED
1787 || flag_ira_algorithm
== IRA_ALGORITHM_REGIONAL
)
1788 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->all_allocnos
, 0, j
, bi
)
1790 a
= ira_allocnos
[j
];
1791 if (ALLOCNO_CAP_MEMBER (a
) == NULL
)
1793 /* Remove from processing in the next loop. */
1794 bitmap_clear_bit (consideration_allocno_bitmap
, j
);
1795 rclass
= ALLOCNO_COVER_CLASS (a
);
1796 if ((flag_ira_algorithm
== IRA_ALGORITHM_MIXED
1797 && loop_tree_node
->reg_pressure
[rclass
]
1798 <= ira_available_class_regs
[rclass
]))
1800 mode
= ALLOCNO_MODE (a
);
1801 hard_regno
= ALLOCNO_HARD_REGNO (a
);
1802 if (hard_regno
>= 0)
1804 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
1805 ira_assert (index
>= 0);
1807 regno
= ALLOCNO_REGNO (a
);
1808 subloop_allocno
= ALLOCNO_CAP_MEMBER (a
);
1809 subloop_node
= ALLOCNO_LOOP_TREE_NODE (subloop_allocno
);
1810 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno
));
1811 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
1812 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
1813 if (hard_regno
>= 0)
1814 update_copy_costs (subloop_allocno
, true);
1815 /* We don't need updated costs anymore: */
1816 ira_free_allocno_updated_costs (subloop_allocno
);
1819 /* Update costs of the corresponding allocnos (not caps) in the
1821 for (subloop_node
= loop_tree_node
->subloops
;
1822 subloop_node
!= NULL
;
1823 subloop_node
= subloop_node
->subloop_next
)
1825 ira_assert (subloop_node
->bb
== NULL
);
1826 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
1828 a
= ira_allocnos
[j
];
1829 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
1830 mode
= ALLOCNO_MODE (a
);
1831 rclass
= ALLOCNO_COVER_CLASS (a
);
1832 hard_regno
= ALLOCNO_HARD_REGNO (a
);
1833 if (hard_regno
>= 0)
1835 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
1836 ira_assert (index
>= 0);
1838 regno
= ALLOCNO_REGNO (a
);
1839 /* ??? conflict costs */
1840 subloop_allocno
= subloop_node
->regno_allocno_map
[regno
];
1841 if (subloop_allocno
== NULL
1842 || ALLOCNO_CAP (subloop_allocno
) != NULL
)
1844 ira_assert (bitmap_bit_p (subloop_node
->all_allocnos
,
1845 ALLOCNO_NUM (subloop_allocno
)));
1846 if (flag_ira_algorithm
== IRA_ALGORITHM_MIXED
1847 && (loop_tree_node
->reg_pressure
[rclass
]
1848 <= ira_available_class_regs
[rclass
]))
1850 if (! ALLOCNO_ASSIGNED_P (subloop_allocno
))
1852 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
1853 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
1854 if (hard_regno
>= 0)
1855 update_copy_costs (subloop_allocno
, true);
1856 /* We don't need updated costs anymore: */
1857 ira_free_allocno_updated_costs (subloop_allocno
);
1861 exit_freq
= ira_loop_edge_freq (subloop_node
, regno
, true);
1862 enter_freq
= ira_loop_edge_freq (subloop_node
, regno
, false);
1863 ira_assert (regno
< ira_reg_equiv_len
);
1864 if (ira_reg_equiv_invariant_p
[regno
]
1865 || ira_reg_equiv_const
[regno
] != NULL_RTX
)
1867 if (! ALLOCNO_ASSIGNED_P (subloop_allocno
))
1869 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
1870 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
1871 if (hard_regno
>= 0)
1872 update_copy_costs (subloop_allocno
, true);
1873 /* We don't need updated costs anymore: */
1874 ira_free_allocno_updated_costs (subloop_allocno
);
1877 else if (hard_regno
< 0)
1879 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno
)
1880 -= ((ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
)
1881 + (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
));
1885 cover_class
= ALLOCNO_COVER_CLASS (subloop_allocno
);
1886 cost
= (ira_register_move_cost
[mode
][rclass
][rclass
]
1887 * (exit_freq
+ enter_freq
));
1888 ira_allocate_and_set_or_copy_costs
1889 (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
), cover_class
,
1890 ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno
),
1891 ALLOCNO_HARD_REG_COSTS (subloop_allocno
));
1892 ira_allocate_and_set_or_copy_costs
1893 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno
),
1895 ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno
));
1896 ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
] -= cost
;
1897 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno
)[index
]
1899 if (ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno
)
1900 > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
])
1901 ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno
)
1902 = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
];
1903 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno
)
1904 += (ira_memory_move_cost
[mode
][rclass
][0] * enter_freq
1905 + ira_memory_move_cost
[mode
][rclass
][1] * exit_freq
);
1911 /* Initialize the common data for coloring and calls functions to do
1912 Chaitin-Briggs and regional coloring. */
1916 coloring_allocno_bitmap
= ira_allocate_bitmap ();
1917 allocnos_for_spilling
1918 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
1919 * ira_allocnos_num
);
1920 splay_tree_node_pool
= create_alloc_pool ("splay tree nodes",
1921 sizeof (struct splay_tree_node_s
),
1923 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
1924 fprintf (ira_dump_file
, "\n**** Allocnos coloring:\n\n");
1926 ira_traverse_loop_tree (false, ira_loop_tree_root
, color_pass
, NULL
);
1928 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
1929 ira_print_disposition (ira_dump_file
);
1931 free_alloc_pool (splay_tree_node_pool
);
1932 ira_free_bitmap (coloring_allocno_bitmap
);
1933 ira_free (allocnos_for_spilling
);
1938 /* Move spill/restore code, which are to be generated in ira-emit.c,
1939 to less frequent points (if it is profitable) by reassigning some
1940 allocnos (in loop with subloops containing in another loop) to
1941 memory which results in longer live-range where the corresponding
1942 pseudo-registers will be in memory. */
1944 move_spill_restore (void)
1946 int cost
, regno
, hard_regno
, hard_regno2
, index
;
1948 int enter_freq
, exit_freq
;
1949 enum machine_mode mode
;
1950 enum reg_class rclass
;
1951 ira_allocno_t a
, parent_allocno
, subloop_allocno
;
1952 ira_loop_tree_node_t parent
, loop_node
, subloop_node
;
1953 ira_allocno_iterator ai
;
1958 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
1959 fprintf (ira_dump_file
, "New iteration of spill/restore move\n");
1960 FOR_EACH_ALLOCNO (a
, ai
)
1962 regno
= ALLOCNO_REGNO (a
);
1963 loop_node
= ALLOCNO_LOOP_TREE_NODE (a
);
1964 if (ALLOCNO_CAP_MEMBER (a
) != NULL
1965 || ALLOCNO_CAP (a
) != NULL
1966 || (hard_regno
= ALLOCNO_HARD_REGNO (a
)) < 0
1967 || loop_node
->children
== NULL
1968 /* don't do the optimization because it can create
1969 copies and the reload pass can spill the allocno set
1970 by copy although the allocno will not get memory
1972 || ira_reg_equiv_invariant_p
[regno
]
1973 || ira_reg_equiv_const
[regno
] != NULL_RTX
1974 || !bitmap_bit_p (loop_node
->border_allocnos
, ALLOCNO_NUM (a
)))
1976 mode
= ALLOCNO_MODE (a
);
1977 rclass
= ALLOCNO_COVER_CLASS (a
);
1978 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
1979 ira_assert (index
>= 0);
1980 cost
= (ALLOCNO_MEMORY_COST (a
)
1981 - (ALLOCNO_HARD_REG_COSTS (a
) == NULL
1982 ? ALLOCNO_COVER_CLASS_COST (a
)
1983 : ALLOCNO_HARD_REG_COSTS (a
)[index
]));
1984 for (subloop_node
= loop_node
->subloops
;
1985 subloop_node
!= NULL
;
1986 subloop_node
= subloop_node
->subloop_next
)
1988 ira_assert (subloop_node
->bb
== NULL
);
1989 subloop_allocno
= subloop_node
->regno_allocno_map
[regno
];
1990 if (subloop_allocno
== NULL
)
1992 /* We have accumulated cost. To get the real cost of
1993 allocno usage in the loop we should subtract costs of
1994 the subloop allocnos. */
1995 cost
-= (ALLOCNO_MEMORY_COST (subloop_allocno
)
1996 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno
) == NULL
1997 ? ALLOCNO_COVER_CLASS_COST (subloop_allocno
)
1998 : ALLOCNO_HARD_REG_COSTS (subloop_allocno
)[index
]));
1999 exit_freq
= ira_loop_edge_freq (subloop_node
, regno
, true);
2000 enter_freq
= ira_loop_edge_freq (subloop_node
, regno
, false);
2001 if ((hard_regno2
= ALLOCNO_HARD_REGNO (subloop_allocno
)) < 0)
2002 cost
-= (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
2003 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
2007 += (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
2008 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
2009 if (hard_regno2
!= hard_regno
)
2010 cost
-= (ira_register_move_cost
[mode
][rclass
][rclass
]
2011 * (exit_freq
+ enter_freq
));
2014 if ((parent
= loop_node
->parent
) != NULL
2015 && (parent_allocno
= parent
->regno_allocno_map
[regno
]) != NULL
)
2017 exit_freq
= ira_loop_edge_freq (loop_node
, regno
, true);
2018 enter_freq
= ira_loop_edge_freq (loop_node
, regno
, false);
2019 if ((hard_regno2
= ALLOCNO_HARD_REGNO (parent_allocno
)) < 0)
2020 cost
-= (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
2021 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
2025 += (ira_memory_move_cost
[mode
][rclass
][1] * exit_freq
2026 + ira_memory_move_cost
[mode
][rclass
][0] * enter_freq
);
2027 if (hard_regno2
!= hard_regno
)
2028 cost
-= (ira_register_move_cost
[mode
][rclass
][rclass
]
2029 * (exit_freq
+ enter_freq
));
2034 ALLOCNO_HARD_REGNO (a
) = -1;
2035 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2039 " Moving spill/restore for a%dr%d up from loop %d",
2040 ALLOCNO_NUM (a
), regno
, loop_node
->loop
->num
);
2041 fprintf (ira_dump_file
, " - profit %d\n", -cost
);
2053 /* Update current hard reg costs and current conflict hard reg costs
2054 for allocno A. It is done by processing its copies containing
2055 other allocnos already assigned. */
2057 update_curr_costs (ira_allocno_t a
)
2059 int i
, hard_regno
, cost
;
2060 enum machine_mode mode
;
2061 enum reg_class cover_class
, rclass
;
2062 ira_allocno_t another_a
;
2063 ira_copy_t cp
, next_cp
;
2065 ira_assert (! ALLOCNO_ASSIGNED_P (a
));
2066 cover_class
= ALLOCNO_COVER_CLASS (a
);
2067 if (cover_class
== NO_REGS
)
2069 mode
= ALLOCNO_MODE (a
);
2070 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
2074 next_cp
= cp
->next_first_allocno_copy
;
2075 another_a
= cp
->second
;
2077 else if (cp
->second
== a
)
2079 next_cp
= cp
->next_second_allocno_copy
;
2080 another_a
= cp
->first
;
2084 if (cover_class
!= ALLOCNO_COVER_CLASS (another_a
)
2085 || ! ALLOCNO_ASSIGNED_P (another_a
)
2086 || (hard_regno
= ALLOCNO_HARD_REGNO (another_a
)) < 0)
2088 rclass
= REGNO_REG_CLASS (hard_regno
);
2089 i
= ira_class_hard_reg_index
[cover_class
][hard_regno
];
2090 ira_assert (i
>= 0);
2091 cost
= (cp
->first
== a
2092 ? ira_register_move_cost
[mode
][rclass
][cover_class
]
2093 : ira_register_move_cost
[mode
][cover_class
][rclass
]);
2094 ira_allocate_and_set_or_copy_costs
2095 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a
),
2096 cover_class
, ALLOCNO_COVER_CLASS_COST (a
),
2097 ALLOCNO_HARD_REG_COSTS (a
));
2098 ira_allocate_and_set_or_copy_costs
2099 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
),
2100 cover_class
, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a
));
2101 ALLOCNO_UPDATED_HARD_REG_COSTS (a
)[i
] -= cp
->freq
* cost
;
2102 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
)[i
] -= cp
->freq
* cost
;
2106 /* Map: allocno number -> allocno priority. */
2107 static int *allocno_priorities
;
2109 /* Set up priorities for N allocnos in array
2110 CONSIDERATION_ALLOCNOS. */
2112 setup_allocno_priorities (ira_allocno_t
*consideration_allocnos
, int n
)
2114 int i
, length
, nrefs
, priority
, max_priority
, mult
;
2118 for (i
= 0; i
< n
; i
++)
2120 a
= consideration_allocnos
[i
];
2121 nrefs
= ALLOCNO_NREFS (a
);
2122 ira_assert (nrefs
>= 0);
2123 mult
= floor_log2 (ALLOCNO_NREFS (a
)) + 1;
2124 ira_assert (mult
>= 0);
2125 allocno_priorities
[ALLOCNO_NUM (a
)]
2128 * (ALLOCNO_MEMORY_COST (a
) - ALLOCNO_COVER_CLASS_COST (a
))
2129 * ira_reg_class_nregs
[ALLOCNO_COVER_CLASS (a
)][ALLOCNO_MODE (a
)]);
2131 priority
= -priority
;
2132 if (max_priority
< priority
)
2133 max_priority
= priority
;
2135 mult
= max_priority
== 0 ? 1 : INT_MAX
/ max_priority
;
2136 for (i
= 0; i
< n
; i
++)
2138 a
= consideration_allocnos
[i
];
2139 length
= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
2142 allocno_priorities
[ALLOCNO_NUM (a
)]
2143 = allocno_priorities
[ALLOCNO_NUM (a
)] * mult
/ length
;
2147 /* Sort allocnos according to their priorities which are calculated
2148 analogous to ones in file `global.c'. */
2150 allocno_priority_compare_func (const void *v1p
, const void *v2p
)
2152 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
2153 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
2156 pri1
= allocno_priorities
[ALLOCNO_NUM (a1
)];
2157 pri2
= allocno_priorities
[ALLOCNO_NUM (a2
)];
2161 /* If regs are equally good, sort by allocnos, so that the results of
2162 qsort leave nothing to chance. */
2163 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
2166 /* Try to assign hard registers to the unassigned allocnos and
2167 allocnos conflicting with them or conflicting with allocnos whose
2168 regno >= START_REGNO. The function is called after ira_flattening,
2169 so more allocnos (including ones created in ira-emit.c) will have a
2170 chance to get a hard register. We use simple assignment algorithm
2171 based on priorities. */
2173 ira_reassign_conflict_allocnos (int start_regno
)
2175 int i
, allocnos_to_color_num
;
2176 ira_allocno_t a
, conflict_a
;
2177 ira_allocno_conflict_iterator aci
;
2178 enum reg_class cover_class
;
2179 bitmap allocnos_to_color
;
2180 ira_allocno_iterator ai
;
2182 allocnos_to_color
= ira_allocate_bitmap ();
2183 allocnos_to_color_num
= 0;
2184 FOR_EACH_ALLOCNO (a
, ai
)
2186 if (! ALLOCNO_ASSIGNED_P (a
)
2187 && ! bitmap_bit_p (allocnos_to_color
, ALLOCNO_NUM (a
)))
2189 if (ALLOCNO_COVER_CLASS (a
) != NO_REGS
)
2190 sorted_allocnos
[allocnos_to_color_num
++] = a
;
2193 ALLOCNO_ASSIGNED_P (a
) = true;
2194 ALLOCNO_HARD_REGNO (a
) = -1;
2195 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
2196 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
2198 bitmap_set_bit (allocnos_to_color
, ALLOCNO_NUM (a
));
2200 if (ALLOCNO_REGNO (a
) < start_regno
2201 || (cover_class
= ALLOCNO_COVER_CLASS (a
)) == NO_REGS
)
2203 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_a
, aci
)
2205 ira_assert (cover_class
== ALLOCNO_COVER_CLASS (conflict_a
));
2206 if (bitmap_bit_p (allocnos_to_color
, ALLOCNO_NUM (conflict_a
)))
2208 bitmap_set_bit (allocnos_to_color
, ALLOCNO_NUM (conflict_a
));
2209 sorted_allocnos
[allocnos_to_color_num
++] = conflict_a
;
2212 ira_free_bitmap (allocnos_to_color
);
2213 if (allocnos_to_color_num
> 1)
2215 setup_allocno_priorities (sorted_allocnos
, allocnos_to_color_num
);
2216 qsort (sorted_allocnos
, allocnos_to_color_num
, sizeof (ira_allocno_t
),
2217 allocno_priority_compare_func
);
2219 for (i
= 0; i
< allocnos_to_color_num
; i
++)
2221 a
= sorted_allocnos
[i
];
2222 ALLOCNO_ASSIGNED_P (a
) = false;
2223 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
2224 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
2225 update_curr_costs (a
);
2227 for (i
= 0; i
< allocnos_to_color_num
; i
++)
2229 a
= sorted_allocnos
[i
];
2230 if (assign_hard_reg (a
, true))
2232 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2235 " Secondary allocation: assign hard reg %d to reg %d\n",
2236 ALLOCNO_HARD_REGNO (a
), ALLOCNO_REGNO (a
));
2243 /* This page contains code to coalesce memory stack slots used by
2244 spilled allocnos. This results in smaller stack frame, better data
2245 locality, and in smaller code for some architectures like
2246 x86/x86_64 where insn size depends on address displacement value.
2247 On the other hand, it can worsen insn scheduling after the RA but
2248 in practice it is less important than smaller stack frames. */
2250 /* Usage cost and order number of coalesced allocno set to which
2251 given pseudo register belongs to. */
2252 static int *regno_coalesced_allocno_cost
;
2253 static int *regno_coalesced_allocno_num
;
2255 /* Sort pseudos according frequencies of coalesced allocno sets they
2256 belong to (putting most frequently ones first), and according to
2257 coalesced allocno set order numbers. */
2259 coalesced_pseudo_reg_freq_compare (const void *v1p
, const void *v2p
)
2261 const int regno1
= *(const int *) v1p
;
2262 const int regno2
= *(const int *) v2p
;
2265 if ((diff
= (regno_coalesced_allocno_cost
[regno2
]
2266 - regno_coalesced_allocno_cost
[regno1
])) != 0)
2268 if ((diff
= (regno_coalesced_allocno_num
[regno1
]
2269 - regno_coalesced_allocno_num
[regno2
])) != 0)
2271 return regno1
- regno2
;
2274 /* Widest width in which each pseudo reg is referred to (via subreg).
2275 It is used for sorting pseudo registers. */
2276 static unsigned int *regno_max_ref_width
;
2278 /* Redefine STACK_GROWS_DOWNWARD in terms of 0 or 1. */
2279 #ifdef STACK_GROWS_DOWNWARD
2280 # undef STACK_GROWS_DOWNWARD
2281 # define STACK_GROWS_DOWNWARD 1
2283 # define STACK_GROWS_DOWNWARD 0
2286 /* Sort pseudos according their slot numbers (putting ones with
2287 smaller numbers first, or last when the frame pointer is not
2290 coalesced_pseudo_reg_slot_compare (const void *v1p
, const void *v2p
)
2292 const int regno1
= *(const int *) v1p
;
2293 const int regno2
= *(const int *) v2p
;
2294 ira_allocno_t a1
= ira_regno_allocno_map
[regno1
];
2295 ira_allocno_t a2
= ira_regno_allocno_map
[regno2
];
2296 int diff
, slot_num1
, slot_num2
;
2297 int total_size1
, total_size2
;
2299 if (a1
== NULL
|| ALLOCNO_HARD_REGNO (a1
) >= 0)
2301 if (a2
== NULL
|| ALLOCNO_HARD_REGNO (a2
) >= 0)
2302 return regno1
- regno2
;
2305 else if (a2
== NULL
|| ALLOCNO_HARD_REGNO (a2
) >= 0)
2307 slot_num1
= -ALLOCNO_HARD_REGNO (a1
);
2308 slot_num2
= -ALLOCNO_HARD_REGNO (a2
);
2309 if ((diff
= slot_num1
- slot_num2
) != 0)
2310 return (frame_pointer_needed
2311 || !FRAME_GROWS_DOWNWARD
== STACK_GROWS_DOWNWARD
? diff
: -diff
);
2312 total_size1
= MAX (PSEUDO_REGNO_BYTES (regno1
), regno_max_ref_width
[regno1
]);
2313 total_size2
= MAX (PSEUDO_REGNO_BYTES (regno2
), regno_max_ref_width
[regno2
]);
2314 if ((diff
= total_size2
- total_size1
) != 0)
2316 return regno1
- regno2
;
2319 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
2320 for coalesced allocno sets containing allocnos with their regnos
2321 given in array PSEUDO_REGNOS of length N. */
2323 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos
, int n
)
2325 int i
, num
, regno
, cost
;
2326 ira_allocno_t allocno
, a
;
2328 for (num
= i
= 0; i
< n
; i
++)
2330 regno
= pseudo_regnos
[i
];
2331 allocno
= ira_regno_allocno_map
[regno
];
2332 if (allocno
== NULL
)
2334 regno_coalesced_allocno_cost
[regno
] = 0;
2335 regno_coalesced_allocno_num
[regno
] = ++num
;
2338 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) != allocno
)
2341 for (cost
= 0, a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
2342 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
2344 cost
+= ALLOCNO_FREQ (a
);
2348 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
2349 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
2351 regno_coalesced_allocno_num
[ALLOCNO_REGNO (a
)] = num
;
2352 regno_coalesced_allocno_cost
[ALLOCNO_REGNO (a
)] = cost
;
2359 /* Collect spilled allocnos representing coalesced allocno sets (the
2360 first coalesced allocno). The collected allocnos are returned
2361 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
2362 number of the collected allocnos. The allocnos are given by their
2363 regnos in array PSEUDO_REGNOS of length N. */
2365 collect_spilled_coalesced_allocnos (int *pseudo_regnos
, int n
,
2366 ira_allocno_t
*spilled_coalesced_allocnos
)
2369 ira_allocno_t allocno
;
2371 for (num
= i
= 0; i
< n
; i
++)
2373 regno
= pseudo_regnos
[i
];
2374 allocno
= ira_regno_allocno_map
[regno
];
2375 if (allocno
== NULL
|| ALLOCNO_HARD_REGNO (allocno
) >= 0
2376 || ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) != allocno
)
2378 spilled_coalesced_allocnos
[num
++] = allocno
;
2383 /* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
2384 given slot contains live ranges of coalesced allocnos assigned to
2386 static allocno_live_range_t
*slot_coalesced_allocnos_live_ranges
;
2388 /* Return TRUE if coalesced allocnos represented by ALLOCNO has live
2389 ranges intersected with live ranges of coalesced allocnos assigned
2390 to slot with number N. */
2392 slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno
, int n
)
2396 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
2397 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
2399 if (ira_allocno_live_ranges_intersect_p
2400 (slot_coalesced_allocnos_live_ranges
[n
], ALLOCNO_LIVE_RANGES (a
)))
2408 /* Update live ranges of slot to which coalesced allocnos represented
2409 by ALLOCNO were assigned. */
2411 setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno
)
2415 allocno_live_range_t r
;
2417 n
= ALLOCNO_TEMP (allocno
);
2418 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
2419 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
2421 r
= ira_copy_allocno_live_range_list (ALLOCNO_LIVE_RANGES (a
));
2422 slot_coalesced_allocnos_live_ranges
[n
]
2423 = ira_merge_allocno_live_ranges
2424 (slot_coalesced_allocnos_live_ranges
[n
], r
);
2430 /* We have coalesced allocnos involving in copies. Coalesce allocnos
2431 further in order to share the same memory stack slot. Allocnos
2432 representing sets of allocnos coalesced before the call are given
2433 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
2434 some allocnos were coalesced in the function. */
2436 coalesce_spill_slots (ira_allocno_t
*spilled_coalesced_allocnos
, int num
)
2438 int i
, j
, n
, last_coalesced_allocno_num
;
2439 ira_allocno_t allocno
, a
;
2440 bool merged_p
= false;
2442 slot_coalesced_allocnos_live_ranges
2443 = (allocno_live_range_t
*) ira_allocate (sizeof (allocno_live_range_t
)
2444 * ira_allocnos_num
);
2445 memset (slot_coalesced_allocnos_live_ranges
, 0,
2446 sizeof (allocno_live_range_t
) * ira_allocnos_num
);
2447 last_coalesced_allocno_num
= 0;
2448 /* Coalesce non-conflicting spilled allocnos preferring most
2450 for (i
= 0; i
< num
; i
++)
2452 allocno
= spilled_coalesced_allocnos
[i
];
2453 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) != allocno
2454 || (ALLOCNO_REGNO (allocno
) < ira_reg_equiv_len
2455 && (ira_reg_equiv_const
[ALLOCNO_REGNO (allocno
)] != NULL_RTX
2456 || ira_reg_equiv_invariant_p
[ALLOCNO_REGNO (allocno
)])))
2458 for (j
= 0; j
< i
; j
++)
2460 a
= spilled_coalesced_allocnos
[j
];
2461 n
= ALLOCNO_TEMP (a
);
2462 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) == a
2463 && (ALLOCNO_REGNO (a
) >= ira_reg_equiv_len
2464 || (! ira_reg_equiv_invariant_p
[ALLOCNO_REGNO (a
)]
2465 && ira_reg_equiv_const
[ALLOCNO_REGNO (a
)] == NULL_RTX
))
2466 && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno
, n
))
2471 /* No coalescing: set up number for coalesced allocnos
2472 represented by ALLOCNO. */
2473 ALLOCNO_TEMP (allocno
) = last_coalesced_allocno_num
++;
2474 setup_slot_coalesced_allocno_live_ranges (allocno
);
2478 allocno_coalesced_p
= true;
2480 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2481 fprintf (ira_dump_file
,
2482 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
2483 ALLOCNO_NUM (allocno
), ALLOCNO_REGNO (allocno
),
2484 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
2485 ALLOCNO_TEMP (allocno
) = ALLOCNO_TEMP (a
);
2486 setup_slot_coalesced_allocno_live_ranges (allocno
);
2487 merge_allocnos (a
, allocno
);
2488 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) == a
);
2491 for (i
= 0; i
< ira_allocnos_num
; i
++)
2492 ira_finish_allocno_live_range_list
2493 (slot_coalesced_allocnos_live_ranges
[i
]);
2494 ira_free (slot_coalesced_allocnos_live_ranges
);
2498 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
2499 subsequent assigning stack slots to them in the reload pass. To do
2500 this we coalesce spilled allocnos first to decrease the number of
2501 memory-memory move insns. This function is called by the
2504 ira_sort_regnos_for_alter_reg (int *pseudo_regnos
, int n
,
2505 unsigned int *reg_max_ref_width
)
2507 int max_regno
= max_reg_num ();
2508 int i
, regno
, num
, slot_num
;
2509 ira_allocno_t allocno
, a
;
2510 ira_allocno_iterator ai
;
2511 ira_allocno_t
*spilled_coalesced_allocnos
;
2513 processed_coalesced_allocno_bitmap
= ira_allocate_bitmap ();
2514 /* Set up allocnos can be coalesced. */
2515 coloring_allocno_bitmap
= ira_allocate_bitmap ();
2516 for (i
= 0; i
< n
; i
++)
2518 regno
= pseudo_regnos
[i
];
2519 allocno
= ira_regno_allocno_map
[regno
];
2520 if (allocno
!= NULL
)
2521 bitmap_set_bit (coloring_allocno_bitmap
,
2522 ALLOCNO_NUM (allocno
));
2524 allocno_coalesced_p
= false;
2525 coalesce_allocnos (true);
2526 ira_free_bitmap (coloring_allocno_bitmap
);
2527 regno_coalesced_allocno_cost
2528 = (int *) ira_allocate (max_regno
* sizeof (int));
2529 regno_coalesced_allocno_num
2530 = (int *) ira_allocate (max_regno
* sizeof (int));
2531 memset (regno_coalesced_allocno_num
, 0, max_regno
* sizeof (int));
2532 setup_coalesced_allocno_costs_and_nums (pseudo_regnos
, n
);
2533 /* Sort regnos according frequencies of the corresponding coalesced
2535 qsort (pseudo_regnos
, n
, sizeof (int), coalesced_pseudo_reg_freq_compare
);
2536 spilled_coalesced_allocnos
2537 = (ira_allocno_t
*) ira_allocate (ira_allocnos_num
2538 * sizeof (ira_allocno_t
));
2539 /* Collect allocnos representing the spilled coalesced allocno
2541 num
= collect_spilled_coalesced_allocnos (pseudo_regnos
, n
,
2542 spilled_coalesced_allocnos
);
2543 if (flag_ira_share_spill_slots
2544 && coalesce_spill_slots (spilled_coalesced_allocnos
, num
))
2546 setup_coalesced_allocno_costs_and_nums (pseudo_regnos
, n
);
2547 qsort (pseudo_regnos
, n
, sizeof (int),
2548 coalesced_pseudo_reg_freq_compare
);
2549 num
= collect_spilled_coalesced_allocnos (pseudo_regnos
, n
,
2550 spilled_coalesced_allocnos
);
2552 ira_free_bitmap (processed_coalesced_allocno_bitmap
);
2553 allocno_coalesced_p
= false;
2554 /* Assign stack slot numbers to spilled allocno sets, use smaller
2555 numbers for most frequently used coalesced allocnos. -1 is
2556 reserved for dynamic search of stack slots for pseudos spilled by
2559 for (i
= 0; i
< num
; i
++)
2561 allocno
= spilled_coalesced_allocnos
[i
];
2562 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) != allocno
2563 || ALLOCNO_HARD_REGNO (allocno
) >= 0
2564 || (ALLOCNO_REGNO (allocno
) < ira_reg_equiv_len
2565 && (ira_reg_equiv_const
[ALLOCNO_REGNO (allocno
)] != NULL_RTX
2566 || ira_reg_equiv_invariant_p
[ALLOCNO_REGNO (allocno
)])))
2568 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2569 fprintf (ira_dump_file
, " Slot %d (freq,size):", slot_num
);
2571 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
2572 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
2574 ira_assert (ALLOCNO_HARD_REGNO (a
) < 0);
2575 ALLOCNO_HARD_REGNO (a
) = -slot_num
;
2576 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2577 fprintf (ira_dump_file
, " a%dr%d(%d,%d)",
2578 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
), ALLOCNO_FREQ (a
),
2579 MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a
)),
2580 reg_max_ref_width
[ALLOCNO_REGNO (a
)]));
2585 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2586 fprintf (ira_dump_file
, "\n");
2588 ira_spilled_reg_stack_slots_num
= slot_num
- 1;
2589 ira_free (spilled_coalesced_allocnos
);
2590 /* Sort regnos according the slot numbers. */
2591 regno_max_ref_width
= reg_max_ref_width
;
2592 qsort (pseudo_regnos
, n
, sizeof (int), coalesced_pseudo_reg_slot_compare
);
2593 /* Uncoalesce allocnos which is necessary for (re)assigning during
2595 FOR_EACH_ALLOCNO (a
, ai
)
2597 ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) = a
;
2598 ALLOCNO_NEXT_COALESCED_ALLOCNO (a
) = a
;
2600 ira_free (regno_coalesced_allocno_num
);
2601 ira_free (regno_coalesced_allocno_cost
);
2606 /* This page contains code used by the reload pass to improve the
2609 /* The function is called from reload to mark changes in the
2610 allocation of REGNO made by the reload. Remember that reg_renumber
2611 reflects the change result. */
2613 ira_mark_allocation_change (int regno
)
2615 ira_allocno_t a
= ira_regno_allocno_map
[regno
];
2616 int old_hard_regno
, hard_regno
, cost
;
2617 enum reg_class cover_class
= ALLOCNO_COVER_CLASS (a
);
2619 ira_assert (a
!= NULL
);
2620 hard_regno
= reg_renumber
[regno
];
2621 if ((old_hard_regno
= ALLOCNO_HARD_REGNO (a
)) == hard_regno
)
2623 if (old_hard_regno
< 0)
2624 cost
= -ALLOCNO_MEMORY_COST (a
);
2627 ira_assert (ira_class_hard_reg_index
[cover_class
][old_hard_regno
] >= 0);
2628 cost
= -(ALLOCNO_HARD_REG_COSTS (a
) == NULL
2629 ? ALLOCNO_COVER_CLASS_COST (a
)
2630 : ALLOCNO_HARD_REG_COSTS (a
)
2631 [ira_class_hard_reg_index
[cover_class
][old_hard_regno
]]);
2632 update_copy_costs (a
, false);
2634 ira_overall_cost
-= cost
;
2635 ALLOCNO_HARD_REGNO (a
) = hard_regno
;
2638 ALLOCNO_HARD_REGNO (a
) = -1;
2639 cost
+= ALLOCNO_MEMORY_COST (a
);
2641 else if (ira_class_hard_reg_index
[cover_class
][hard_regno
] >= 0)
2643 cost
+= (ALLOCNO_HARD_REG_COSTS (a
) == NULL
2644 ? ALLOCNO_COVER_CLASS_COST (a
)
2645 : ALLOCNO_HARD_REG_COSTS (a
)
2646 [ira_class_hard_reg_index
[cover_class
][hard_regno
]]);
2647 update_copy_costs (a
, true);
2650 /* Reload changed class of the allocno. */
2652 ira_overall_cost
+= cost
;
2655 /* This function is called when reload deletes memory-memory move. In
2656 this case we marks that the allocation of the corresponding
2657 allocnos should be not changed in future. Otherwise we risk to get
2660 ira_mark_memory_move_deletion (int dst_regno
, int src_regno
)
2662 ira_allocno_t dst
= ira_regno_allocno_map
[dst_regno
];
2663 ira_allocno_t src
= ira_regno_allocno_map
[src_regno
];
2665 ira_assert (dst
!= NULL
&& src
!= NULL
2666 && ALLOCNO_HARD_REGNO (dst
) < 0
2667 && ALLOCNO_HARD_REGNO (src
) < 0);
2668 ALLOCNO_DONT_REASSIGN_P (dst
) = true;
2669 ALLOCNO_DONT_REASSIGN_P (src
) = true;
2672 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
2673 allocno A and return TRUE in the case of success. That is an
2674 analog of retry_global_alloc for IRA. */
2676 allocno_reload_assign (ira_allocno_t a
, HARD_REG_SET forbidden_regs
)
2679 enum reg_class cover_class
;
2680 int regno
= ALLOCNO_REGNO (a
);
2682 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
), forbidden_regs
);
2683 if (! flag_caller_saves
&& ALLOCNO_CALLS_CROSSED_NUM (a
) != 0)
2684 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
), call_used_reg_set
);
2685 ALLOCNO_ASSIGNED_P (a
) = false;
2686 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
2687 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
2688 cover_class
= ALLOCNO_COVER_CLASS (a
);
2689 update_curr_costs (a
);
2690 assign_hard_reg (a
, true);
2691 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2692 reg_renumber
[regno
] = hard_regno
;
2694 ALLOCNO_HARD_REGNO (a
) = -1;
2697 ira_assert (ira_class_hard_reg_index
[cover_class
][hard_regno
] >= 0);
2698 ira_overall_cost
-= (ALLOCNO_MEMORY_COST (a
)
2699 - (ALLOCNO_HARD_REG_COSTS (a
) == NULL
2700 ? ALLOCNO_COVER_CLASS_COST (a
)
2701 : ALLOCNO_HARD_REG_COSTS (a
)
2702 [ira_class_hard_reg_index
2703 [cover_class
][hard_regno
]]));
2704 if (ALLOCNO_CALLS_CROSSED_NUM (a
) != 0
2705 && ! ira_hard_reg_not_in_set_p (hard_regno
, ALLOCNO_MODE (a
),
2708 ira_assert (flag_caller_saves
);
2709 caller_save_needed
= 1;
2713 /* If we found a hard register, modify the RTL for the pseudo
2714 register to show the hard register, and mark the pseudo register
2716 if (reg_renumber
[regno
] >= 0)
2718 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2719 fprintf (ira_dump_file
, ": reassign to %d\n", reg_renumber
[regno
]);
2720 SET_REGNO (regno_reg_rtx
[regno
], reg_renumber
[regno
]);
2721 mark_home_live (regno
);
2723 else if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2724 fprintf (ira_dump_file
, "\n");
2726 return reg_renumber
[regno
] >= 0;
2729 /* Sort pseudos according their usage frequencies (putting most
2730 frequently ones first). */
2732 pseudo_reg_compare (const void *v1p
, const void *v2p
)
2734 int regno1
= *(const int *) v1p
;
2735 int regno2
= *(const int *) v2p
;
2738 if ((diff
= REG_FREQ (regno2
) - REG_FREQ (regno1
)) != 0)
2740 return regno1
- regno2
;
2743 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
2744 NUM of them) or spilled pseudos conflicting with pseudos in
2745 SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
2746 allocation has been changed. The function doesn't use
2747 BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
2748 PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
2749 is called by the reload pass at the end of each reload
2752 ira_reassign_pseudos (int *spilled_pseudo_regs
, int num
,
2753 HARD_REG_SET bad_spill_regs
,
2754 HARD_REG_SET
*pseudo_forbidden_regs
,
2755 HARD_REG_SET
*pseudo_previous_regs
, bitmap spilled
)
2759 ira_allocno_t a
, conflict_a
;
2760 HARD_REG_SET forbidden_regs
;
2761 ira_allocno_conflict_iterator aci
;
2764 qsort (spilled_pseudo_regs
, num
, sizeof (int), pseudo_reg_compare
);
2766 /* Try to assign hard registers to pseudos from
2767 SPILLED_PSEUDO_REGS. */
2768 for (m
= i
= 0; i
< num
; i
++)
2770 regno
= spilled_pseudo_regs
[i
];
2771 COPY_HARD_REG_SET (forbidden_regs
, bad_spill_regs
);
2772 IOR_HARD_REG_SET (forbidden_regs
, pseudo_forbidden_regs
[regno
]);
2773 IOR_HARD_REG_SET (forbidden_regs
, pseudo_previous_regs
[regno
]);
2774 gcc_assert (reg_renumber
[regno
] < 0);
2775 a
= ira_regno_allocno_map
[regno
];
2776 ira_mark_allocation_change (regno
);
2777 ira_assert (reg_renumber
[regno
] < 0);
2778 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2779 fprintf (ira_dump_file
,
2780 " Spill %d(a%d), cost=%d", regno
, ALLOCNO_NUM (a
),
2781 ALLOCNO_MEMORY_COST (a
)
2782 - ALLOCNO_COVER_CLASS_COST (a
));
2783 allocno_reload_assign (a
, forbidden_regs
);
2784 if (reg_renumber
[regno
] >= 0)
2786 CLEAR_REGNO_REG_SET (spilled
, regno
);
2790 spilled_pseudo_regs
[m
++] = regno
;
2794 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2796 fprintf (ira_dump_file
, " Spilled regs");
2797 for (i
= 0; i
< m
; i
++)
2798 fprintf (ira_dump_file
, " %d", spilled_pseudo_regs
[i
]);
2799 fprintf (ira_dump_file
, "\n");
2801 /* Try to assign hard registers to pseudos conflicting with ones
2802 from SPILLED_PSEUDO_REGS. */
2803 for (i
= n
= 0; i
< m
; i
++)
2805 regno
= spilled_pseudo_regs
[i
];
2806 a
= ira_regno_allocno_map
[regno
];
2807 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_a
, aci
)
2808 if (ALLOCNO_HARD_REGNO (conflict_a
) < 0
2809 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a
)
2810 && ! bitmap_bit_p (consideration_allocno_bitmap
,
2811 ALLOCNO_NUM (conflict_a
)))
2813 sorted_allocnos
[n
++] = conflict_a
;
2814 bitmap_set_bit (consideration_allocno_bitmap
,
2815 ALLOCNO_NUM (conflict_a
));
2820 setup_allocno_priorities (sorted_allocnos
, n
);
2821 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
),
2822 allocno_priority_compare_func
);
2823 for (i
= 0; i
< n
; i
++)
2825 a
= sorted_allocnos
[i
];
2826 regno
= ALLOCNO_REGNO (a
);
2827 COPY_HARD_REG_SET (forbidden_regs
, bad_spill_regs
);
2828 IOR_HARD_REG_SET (forbidden_regs
, pseudo_forbidden_regs
[regno
]);
2829 IOR_HARD_REG_SET (forbidden_regs
, pseudo_previous_regs
[regno
]);
2830 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2831 fprintf (ira_dump_file
,
2832 " Try assign %d(a%d), cost=%d",
2833 regno
, ALLOCNO_NUM (a
),
2834 ALLOCNO_MEMORY_COST (a
)
2835 - ALLOCNO_COVER_CLASS_COST (a
));
2836 if (allocno_reload_assign (a
, forbidden_regs
))
2839 bitmap_clear_bit (spilled
, regno
);
2846 /* The function is called by reload and returns already allocated
2847 stack slot (if any) for REGNO with given INHERENT_SIZE and
2848 TOTAL_SIZE. In the case of failure to find a slot which can be
2849 used for REGNO, the function returns NULL. */
2851 ira_reuse_stack_slot (int regno
, unsigned int inherent_size
,
2852 unsigned int total_size
)
2855 int slot_num
, best_slot_num
;
2856 int cost
, best_cost
;
2857 ira_copy_t cp
, next_cp
;
2858 ira_allocno_t another_allocno
, allocno
= ira_regno_allocno_map
[regno
];
2861 struct ira_spilled_reg_stack_slot
*slot
= NULL
;
2863 ira_assert (flag_ira
&& inherent_size
== PSEUDO_REGNO_BYTES (regno
)
2864 && inherent_size
<= total_size
2865 && ALLOCNO_HARD_REGNO (allocno
) < 0);
2866 if (! flag_ira_share_spill_slots
)
2868 slot_num
= -ALLOCNO_HARD_REGNO (allocno
) - 2;
2871 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
2876 best_cost
= best_slot_num
= -1;
2878 /* It means that the pseudo was spilled in the reload pass, try
2881 slot_num
< ira_spilled_reg_stack_slots_num
;
2884 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
2885 if (slot
->mem
== NULL_RTX
)
2887 if (slot
->width
< total_size
2888 || GET_MODE_SIZE (GET_MODE (slot
->mem
)) < inherent_size
)
2891 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
2892 FIRST_PSEUDO_REGISTER
, i
, bi
)
2894 another_allocno
= ira_regno_allocno_map
[i
];
2895 if (allocnos_have_intersected_live_ranges_p (allocno
,
2899 for (cost
= 0, cp
= ALLOCNO_COPIES (allocno
);
2903 if (cp
->first
== allocno
)
2905 next_cp
= cp
->next_first_allocno_copy
;
2906 another_allocno
= cp
->second
;
2908 else if (cp
->second
== allocno
)
2910 next_cp
= cp
->next_second_allocno_copy
;
2911 another_allocno
= cp
->first
;
2915 if (cp
->insn
== NULL_RTX
)
2917 if (bitmap_bit_p (&slot
->spilled_regs
,
2918 ALLOCNO_REGNO (another_allocno
)))
2921 if (cost
> best_cost
)
2924 best_slot_num
= slot_num
;
2931 slot_num
= best_slot_num
;
2932 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
2933 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
2935 ALLOCNO_HARD_REGNO (allocno
) = -slot_num
- 2;
2940 ira_assert (slot
->width
>= total_size
);
2941 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
2942 FIRST_PSEUDO_REGISTER
, i
, bi
)
2944 ira_assert (! pseudos_have_intersected_live_ranges_p (regno
, i
));
2946 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
2947 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
2949 fprintf (ira_dump_file
, " Assigning %d(freq=%d) slot %d of",
2950 regno
, REG_FREQ (regno
), slot_num
);
2951 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
2952 FIRST_PSEUDO_REGISTER
, i
, bi
)
2954 if ((unsigned) regno
!= i
)
2955 fprintf (ira_dump_file
, " %d", i
);
2957 fprintf (ira_dump_file
, "\n");
2963 /* This is called by reload every time a new stack slot X with
2964 TOTAL_SIZE was allocated for REGNO. We store this info for
2965 subsequent ira_reuse_stack_slot calls. */
2967 ira_mark_new_stack_slot (rtx x
, int regno
, unsigned int total_size
)
2969 struct ira_spilled_reg_stack_slot
*slot
;
2971 ira_allocno_t allocno
;
2973 ira_assert (flag_ira
&& PSEUDO_REGNO_BYTES (regno
) <= total_size
);
2974 allocno
= ira_regno_allocno_map
[regno
];
2975 slot_num
= -ALLOCNO_HARD_REGNO (allocno
) - 2;
2978 slot_num
= ira_spilled_reg_stack_slots_num
++;
2979 ALLOCNO_HARD_REGNO (allocno
) = -slot_num
- 2;
2981 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
2982 INIT_REG_SET (&slot
->spilled_regs
);
2983 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
2985 slot
->width
= total_size
;
2986 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
2987 fprintf (ira_dump_file
, " Assigning %d(freq=%d) a new slot %d\n",
2988 regno
, REG_FREQ (regno
), slot_num
);
2992 /* Return spill cost for pseudo-registers whose numbers are in array
2993 REGNOS (with a negative number as an end marker) for reload with
2994 given IN and OUT for INSN. Return also number points (through
2995 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
2996 the register pressure is high, number of references of the
2997 pseudo-registers (through NREFS), number of callee-clobbered
2998 hard-registers occupied by the pseudo-registers (through
2999 CALL_USED_COUNT), and the first hard regno occupied by the
3000 pseudo-registers (through FIRST_HARD_REGNO). */
3002 calculate_spill_cost (int *regnos
, rtx in
, rtx out
, rtx insn
,
3003 int *excess_pressure_live_length
,
3004 int *nrefs
, int *call_used_count
, int *first_hard_regno
)
3006 int i
, cost
, regno
, hard_regno
, j
, count
, saved_cost
, nregs
;
3012 for (length
= count
= cost
= i
= 0;; i
++)
3017 *nrefs
+= REG_N_REFS (regno
);
3018 hard_regno
= reg_renumber
[regno
];
3019 ira_assert (hard_regno
>= 0);
3020 a
= ira_regno_allocno_map
[regno
];
3021 length
+= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
3022 cost
+= ALLOCNO_MEMORY_COST (a
) - ALLOCNO_COVER_CLASS_COST (a
);
3023 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (a
)];
3024 for (j
= 0; j
< nregs
; j
++)
3025 if (! TEST_HARD_REG_BIT (call_used_reg_set
, hard_regno
+ j
))
3029 in_p
= in
&& REG_P (in
) && (int) REGNO (in
) == hard_regno
;
3030 out_p
= out
&& REG_P (out
) && (int) REGNO (out
) == hard_regno
;
3032 && find_regno_note (insn
, REG_DEAD
, hard_regno
) != NULL_RTX
)
3036 saved_cost
+= ira_memory_move_cost
3037 [ALLOCNO_MODE (a
)][ALLOCNO_COVER_CLASS (a
)][1];
3040 += ira_memory_move_cost
3041 [ALLOCNO_MODE (a
)][ALLOCNO_COVER_CLASS (a
)][0];
3042 cost
-= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn
)) * saved_cost
;
3045 *excess_pressure_live_length
= length
;
3046 *call_used_count
= count
;
3050 hard_regno
= reg_renumber
[regnos
[0]];
3052 *first_hard_regno
= hard_regno
;
3056 /* Return TRUE if spilling pseudo-registers whose numbers are in array
3057 REGNOS is better than spilling pseudo-registers with numbers in
3058 OTHER_REGNOS for reload with given IN and OUT for INSN. The
3059 function used by the reload pass to make better register spilling
3062 ira_better_spill_reload_regno_p (int *regnos
, int *other_regnos
,
3063 rtx in
, rtx out
, rtx insn
)
3065 int cost
, other_cost
;
3066 int length
, other_length
;
3067 int nrefs
, other_nrefs
;
3068 int call_used_count
, other_call_used_count
;
3069 int hard_regno
, other_hard_regno
;
3071 cost
= calculate_spill_cost (regnos
, in
, out
, insn
,
3072 &length
, &nrefs
, &call_used_count
, &hard_regno
);
3073 other_cost
= calculate_spill_cost (other_regnos
, in
, out
, insn
,
3074 &other_length
, &other_nrefs
,
3075 &other_call_used_count
,
3077 if (nrefs
== 0 && other_nrefs
!= 0)
3079 if (nrefs
!= 0 && other_nrefs
== 0)
3081 if (cost
!= other_cost
)
3082 return cost
< other_cost
;
3083 if (length
!= other_length
)
3084 return length
> other_length
;
3085 #ifdef REG_ALLOC_ORDER
3086 if (hard_regno
>= 0 && other_hard_regno
>= 0)
3087 return (inv_reg_alloc_order
[hard_regno
]
3088 < inv_reg_alloc_order
[other_hard_regno
]);
3090 if (call_used_count
!= other_call_used_count
)
3091 return call_used_count
> other_call_used_count
;
3098 /* Allocate and initialize data necessary for assign_hard_reg. */
3100 ira_initiate_assign (void)
3103 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
3104 * ira_allocnos_num
);
3105 consideration_allocno_bitmap
= ira_allocate_bitmap ();
3106 initiate_cost_update ();
3107 allocno_priorities
= (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
3110 /* Deallocate data used by assign_hard_reg. */
3112 ira_finish_assign (void)
3114 ira_free (sorted_allocnos
);
3115 ira_free_bitmap (consideration_allocno_bitmap
);
3116 finish_cost_update ();
3117 ira_free (allocno_priorities
);
3122 /* Entry function doing color-based register allocation. */
3126 allocno_stack_vec
= VEC_alloc (ira_allocno_t
, heap
, ira_allocnos_num
);
3127 removed_splay_allocno_vec
3128 = VEC_alloc (ira_allocno_t
, heap
, ira_allocnos_num
);
3129 memset (allocated_hardreg_p
, 0, sizeof (allocated_hardreg_p
));
3130 ira_initiate_assign ();
3132 ira_finish_assign ();
3133 VEC_free (ira_allocno_t
, heap
, removed_splay_allocno_vec
);
3134 VEC_free (ira_allocno_t
, heap
, allocno_stack_vec
);
3135 move_spill_restore ();
3140 /* This page contains a simple register allocator without usage of
3141 allocno conflicts. This is used for fast allocation for -O0. */
3143 /* Do register allocation by not using allocno conflicts. It uses
3144 only allocno live ranges. The algorithm is close to Chow's
3145 priority coloring. */
3147 fast_allocation (void)
3149 int i
, j
, k
, num
, class_size
, hard_regno
;
3151 bool no_stack_reg_p
;
3153 enum reg_class cover_class
;
3154 enum machine_mode mode
;
3156 ira_allocno_iterator ai
;
3157 allocno_live_range_t r
;
3158 HARD_REG_SET conflict_hard_regs
, *used_hard_regs
;
3160 sorted_allocnos
= (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
3161 * ira_allocnos_num
);
3163 FOR_EACH_ALLOCNO (a
, ai
)
3164 sorted_allocnos
[num
++] = a
;
3165 allocno_priorities
= (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
3166 setup_allocno_priorities (sorted_allocnos
, num
);
3167 used_hard_regs
= (HARD_REG_SET
*) ira_allocate (sizeof (HARD_REG_SET
)
3169 for (i
= 0; i
< ira_max_point
; i
++)
3170 CLEAR_HARD_REG_SET (used_hard_regs
[i
]);
3171 qsort (sorted_allocnos
, ira_allocnos_num
, sizeof (ira_allocno_t
),
3172 allocno_priority_compare_func
);
3173 for (i
= 0; i
< num
; i
++)
3175 a
= sorted_allocnos
[i
];
3176 COPY_HARD_REG_SET (conflict_hard_regs
, ALLOCNO_CONFLICT_HARD_REGS (a
));
3177 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
3178 for (j
= r
->start
; j
<= r
->finish
; j
++)
3179 IOR_HARD_REG_SET (conflict_hard_regs
, used_hard_regs
[j
]);
3180 cover_class
= ALLOCNO_COVER_CLASS (a
);
3181 ALLOCNO_ASSIGNED_P (a
) = true;
3182 ALLOCNO_HARD_REGNO (a
) = -1;
3183 if (hard_reg_set_subset_p (reg_class_contents
[cover_class
],
3184 conflict_hard_regs
))
3186 mode
= ALLOCNO_MODE (a
);
3188 no_stack_reg_p
= ALLOCNO_NO_STACK_REG_P (a
);
3190 class_size
= ira_class_hard_regs_num
[cover_class
];
3191 for (j
= 0; j
< class_size
; j
++)
3193 hard_regno
= ira_class_hard_regs
[cover_class
][j
];
3195 if (no_stack_reg_p
&& FIRST_STACK_REG
<= hard_regno
3196 && hard_regno
<= LAST_STACK_REG
)
3199 if (!ira_hard_reg_not_in_set_p (hard_regno
, mode
, conflict_hard_regs
)
3200 || (TEST_HARD_REG_BIT
3201 (prohibited_class_mode_regs
[cover_class
][mode
], hard_regno
)))
3203 ALLOCNO_HARD_REGNO (a
) = hard_regno
;
3204 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
3205 for (k
= r
->start
; k
<= r
->finish
; k
++)
3206 IOR_HARD_REG_SET (used_hard_regs
[k
],
3207 ira_reg_mode_hard_regset
[hard_regno
][mode
]);
3211 ira_free (sorted_allocnos
);
3212 ira_free (used_hard_regs
);
3213 ira_free (allocno_priorities
);
3214 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
3215 ira_print_disposition (ira_dump_file
);
3220 /* Entry function doing coloring. */
3225 ira_allocno_iterator ai
;
3227 /* Setup updated costs. */
3228 FOR_EACH_ALLOCNO (a
, ai
)
3230 ALLOCNO_UPDATED_MEMORY_COST (a
) = ALLOCNO_MEMORY_COST (a
);
3231 ALLOCNO_UPDATED_COVER_CLASS_COST (a
) = ALLOCNO_COVER_CLASS_COST (a
);