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 /* Return the current spill priority of allocno A. The less the
659 number, the more preferable the allocno for spilling. */
661 allocno_spill_priority (ira_allocno_t a
)
663 return (ALLOCNO_TEMP (a
)
664 / (ALLOCNO_LEFT_CONFLICTS_NUM (a
)
665 * ira_reg_class_nregs
[ALLOCNO_COVER_CLASS (a
)][ALLOCNO_MODE (a
)]
669 /* Add ALLOCNO to bucket *BUCKET_PTR. ALLOCNO should be not in a bucket
672 add_allocno_to_bucket (ira_allocno_t allocno
, ira_allocno_t
*bucket_ptr
)
674 ira_allocno_t first_allocno
;
675 enum reg_class cover_class
;
677 if (bucket_ptr
== &uncolorable_allocno_bucket
678 && (cover_class
= ALLOCNO_COVER_CLASS (allocno
)) != NO_REGS
)
680 uncolorable_allocnos_num
[cover_class
]++;
681 ira_assert (uncolorable_allocnos_num
[cover_class
] > 0);
683 first_allocno
= *bucket_ptr
;
684 ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno
) = first_allocno
;
685 ALLOCNO_PREV_BUCKET_ALLOCNO (allocno
) = NULL
;
686 if (first_allocno
!= NULL
)
687 ALLOCNO_PREV_BUCKET_ALLOCNO (first_allocno
) = allocno
;
688 *bucket_ptr
= allocno
;
691 /* The function returns frequency and number of available hard
692 registers for allocnos coalesced with ALLOCNO. */
694 get_coalesced_allocnos_attributes (ira_allocno_t allocno
, int *freq
, int *num
)
700 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
701 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
703 *freq
+= ALLOCNO_FREQ (a
);
704 *num
+= ALLOCNO_AVAILABLE_REGS_NUM (a
);
710 /* Compare two allocnos to define which allocno should be pushed first
711 into the coloring stack. If the return is a negative number, the
712 allocno given by the first parameter will be pushed first. In this
713 case such allocno has less priority than the second one and the
714 hard register will be assigned to it after assignment to the second
715 one. As the result of such assignment order, the second allocno
716 has a better chance to get the best hard register. */
718 bucket_allocno_compare_func (const void *v1p
, const void *v2p
)
720 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
721 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
722 int diff
, a1_freq
, a2_freq
, a1_num
, a2_num
;
724 if ((diff
= (int) ALLOCNO_COVER_CLASS (a2
) - ALLOCNO_COVER_CLASS (a1
)) != 0)
726 get_coalesced_allocnos_attributes (a1
, &a1_freq
, &a1_num
);
727 get_coalesced_allocnos_attributes (a2
, &a2_freq
, &a2_num
);
728 if ((diff
= a2_num
- a1_num
) != 0)
730 else if ((diff
= a1_freq
- a2_freq
) != 0)
732 return ALLOCNO_NUM (a2
) - ALLOCNO_NUM (a1
);
735 /* Sort bucket *BUCKET_PTR and return the result through
738 sort_bucket (ira_allocno_t
*bucket_ptr
)
740 ira_allocno_t a
, head
;
743 for (n
= 0, a
= *bucket_ptr
; a
!= NULL
; a
= ALLOCNO_NEXT_BUCKET_ALLOCNO (a
))
744 sorted_allocnos
[n
++] = a
;
747 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
),
748 bucket_allocno_compare_func
);
750 for (n
--; n
>= 0; n
--)
752 a
= sorted_allocnos
[n
];
753 ALLOCNO_NEXT_BUCKET_ALLOCNO (a
) = head
;
754 ALLOCNO_PREV_BUCKET_ALLOCNO (a
) = NULL
;
756 ALLOCNO_PREV_BUCKET_ALLOCNO (head
) = a
;
762 /* Add ALLOCNO to bucket *BUCKET_PTR maintaining the order according
763 their priority. ALLOCNO should be not in a bucket before the
766 add_allocno_to_ordered_bucket (ira_allocno_t allocno
,
767 ira_allocno_t
*bucket_ptr
)
769 ira_allocno_t before
, after
;
770 enum reg_class cover_class
;
772 if (bucket_ptr
== &uncolorable_allocno_bucket
773 && (cover_class
= ALLOCNO_COVER_CLASS (allocno
)) != NO_REGS
)
775 uncolorable_allocnos_num
[cover_class
]++;
776 ira_assert (uncolorable_allocnos_num
[cover_class
] > 0);
778 for (before
= *bucket_ptr
, after
= NULL
;
780 after
= before
, before
= ALLOCNO_NEXT_BUCKET_ALLOCNO (before
))
781 if (bucket_allocno_compare_func (&allocno
, &before
) < 0)
783 ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno
) = before
;
784 ALLOCNO_PREV_BUCKET_ALLOCNO (allocno
) = after
;
786 *bucket_ptr
= allocno
;
788 ALLOCNO_NEXT_BUCKET_ALLOCNO (after
) = allocno
;
790 ALLOCNO_PREV_BUCKET_ALLOCNO (before
) = allocno
;
793 /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
796 delete_allocno_from_bucket (ira_allocno_t allocno
, ira_allocno_t
*bucket_ptr
)
798 ira_allocno_t prev_allocno
, next_allocno
;
799 enum reg_class cover_class
;
801 if (bucket_ptr
== &uncolorable_allocno_bucket
802 && (cover_class
= ALLOCNO_COVER_CLASS (allocno
)) != NO_REGS
)
804 uncolorable_allocnos_num
[cover_class
]--;
805 ira_assert (uncolorable_allocnos_num
[cover_class
] >= 0);
807 prev_allocno
= ALLOCNO_PREV_BUCKET_ALLOCNO (allocno
);
808 next_allocno
= ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno
);
809 if (prev_allocno
!= NULL
)
810 ALLOCNO_NEXT_BUCKET_ALLOCNO (prev_allocno
) = next_allocno
;
813 ira_assert (*bucket_ptr
== allocno
);
814 *bucket_ptr
= next_allocno
;
816 if (next_allocno
!= NULL
)
817 ALLOCNO_PREV_BUCKET_ALLOCNO (next_allocno
) = prev_allocno
;
820 /* Splay tree for each cover class. The trees are indexed by the
821 corresponding cover classes. Splay trees contain uncolorable
823 static splay_tree uncolorable_allocnos_splay_tree
[N_REG_CLASSES
];
825 /* If the following macro is TRUE, splay tree is used to choose an
826 allocno of the corresponding cover class for spilling. When the
827 number uncolorable allocnos of given cover class decreases to some
828 threshold, linear array search is used to find the best allocno for
829 spilling. This threshold is actually pretty big because, although
830 splay trees asymptotically is much faster, each splay tree
831 operation is sufficiently costly especially taking cache locality
833 #define USE_SPLAY_P(CLASS) (uncolorable_allocnos_num[CLASS] > 4000)
835 /* Put ALLOCNO onto the coloring stack without removing it from its
836 bucket. Pushing allocno to the coloring stack can result in moving
837 conflicting allocnos from the uncolorable bucket to the colorable
840 push_allocno_to_stack (ira_allocno_t allocno
)
842 int conflicts_num
, conflict_size
, size
;
843 ira_allocno_t a
, conflict_allocno
;
844 enum reg_class cover_class
;
845 ira_allocno_conflict_iterator aci
;
847 ALLOCNO_IN_GRAPH_P (allocno
) = false;
848 VEC_safe_push (ira_allocno_t
, heap
, allocno_stack_vec
, allocno
);
849 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
850 if (cover_class
== NO_REGS
)
852 size
= ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE (allocno
)];
853 if (allocno_coalesced_p
)
854 bitmap_clear (processed_coalesced_allocno_bitmap
);
855 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
856 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
858 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_allocno
, aci
)
860 conflict_allocno
= ALLOCNO_FIRST_COALESCED_ALLOCNO (conflict_allocno
);
861 if (bitmap_bit_p (coloring_allocno_bitmap
,
862 ALLOCNO_NUM (conflict_allocno
)))
864 ira_assert (cover_class
865 == ALLOCNO_COVER_CLASS (conflict_allocno
));
866 if (allocno_coalesced_p
)
868 if (bitmap_bit_p (processed_coalesced_allocno_bitmap
,
869 ALLOCNO_NUM (conflict_allocno
)))
871 bitmap_set_bit (processed_coalesced_allocno_bitmap
,
872 ALLOCNO_NUM (conflict_allocno
));
874 if (ALLOCNO_IN_GRAPH_P (conflict_allocno
)
875 && ! ALLOCNO_ASSIGNED_P (conflict_allocno
))
877 conflicts_num
= ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno
);
879 = (ira_reg_class_nregs
880 [cover_class
][ALLOCNO_MODE (conflict_allocno
)]);
882 (ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno
) >= size
);
883 if (conflicts_num
+ conflict_size
884 <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno
))
886 ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno
) -= size
;
890 = ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno
) - size
;
891 if (uncolorable_allocnos_splay_tree
[cover_class
] != NULL
892 && !ALLOCNO_SPLAY_REMOVED_P (conflict_allocno
)
893 && USE_SPLAY_P (cover_class
))
897 (uncolorable_allocnos_splay_tree
[cover_class
],
898 (splay_tree_key
) conflict_allocno
) != NULL
);
900 (uncolorable_allocnos_splay_tree
[cover_class
],
901 (splay_tree_key
) conflict_allocno
);
902 ALLOCNO_SPLAY_REMOVED_P (conflict_allocno
) = true;
903 VEC_safe_push (ira_allocno_t
, heap
,
904 removed_splay_allocno_vec
,
907 ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno
) = conflicts_num
;
908 if (conflicts_num
+ conflict_size
909 <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno
))
911 delete_allocno_from_bucket
912 (conflict_allocno
, &uncolorable_allocno_bucket
);
913 add_allocno_to_ordered_bucket
914 (conflict_allocno
, &colorable_allocno_bucket
);
924 /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
925 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
927 remove_allocno_from_bucket_and_push (ira_allocno_t allocno
, bool colorable_p
)
929 enum reg_class cover_class
;
932 delete_allocno_from_bucket (allocno
, &colorable_allocno_bucket
);
934 delete_allocno_from_bucket (allocno
, &uncolorable_allocno_bucket
);
935 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
937 fprintf (ira_dump_file
, " Pushing");
938 print_coalesced_allocno (allocno
);
940 fprintf (ira_dump_file
, "\n");
942 fprintf (ira_dump_file
, "(potential spill: %spri=%d, cost=%d)\n",
943 ALLOCNO_BAD_SPILL_P (allocno
) ? "bad spill, " : "",
944 allocno_spill_priority (allocno
), ALLOCNO_TEMP (allocno
));
946 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
947 ira_assert ((colorable_p
948 && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno
)
949 + ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE (allocno
)]
950 <= ALLOCNO_AVAILABLE_REGS_NUM (allocno
)))
952 && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno
)
953 + ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE
955 > ALLOCNO_AVAILABLE_REGS_NUM (allocno
))));
957 ALLOCNO_MAY_BE_SPILLED_P (allocno
) = true;
958 push_allocno_to_stack (allocno
);
961 /* Put all allocnos from colorable bucket onto the coloring stack. */
963 push_only_colorable (void)
965 sort_bucket (&colorable_allocno_bucket
);
966 for (;colorable_allocno_bucket
!= NULL
;)
967 remove_allocno_from_bucket_and_push (colorable_allocno_bucket
, true);
970 /* Puts ALLOCNO chosen for potential spilling onto the coloring
973 push_allocno_to_spill (ira_allocno_t allocno
)
975 delete_allocno_from_bucket (allocno
, &uncolorable_allocno_bucket
);
976 ALLOCNO_MAY_BE_SPILLED_P (allocno
) = true;
977 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
978 fprintf (ira_dump_file
, " Pushing p%d(%d) (spill for NO_REGS)\n",
979 ALLOCNO_NUM (allocno
), ALLOCNO_REGNO (allocno
));
980 push_allocno_to_stack (allocno
);
983 /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
984 loop given by its LOOP_NODE. */
986 ira_loop_edge_freq (ira_loop_tree_node_t loop_node
, int regno
, bool exit_p
)
991 VEC (edge
, heap
) *edges
;
993 ira_assert (loop_node
->loop
!= NULL
994 && (regno
< 0 || regno
>= FIRST_PSEUDO_REGISTER
));
998 FOR_EACH_EDGE (e
, ei
, loop_node
->loop
->header
->preds
)
999 if (e
->src
!= loop_node
->loop
->latch
1001 || (bitmap_bit_p (DF_LR_OUT (e
->src
), regno
)
1002 && bitmap_bit_p (DF_LR_IN (e
->dest
), regno
))))
1003 freq
+= EDGE_FREQUENCY (e
);
1007 edges
= get_loop_exit_edges (loop_node
->loop
);
1008 for (i
= 0; VEC_iterate (edge
, edges
, i
, e
); i
++)
1010 || (bitmap_bit_p (DF_LR_OUT (e
->src
), regno
)
1011 && bitmap_bit_p (DF_LR_IN (e
->dest
), regno
)))
1012 freq
+= EDGE_FREQUENCY (e
);
1013 VEC_free (edge
, heap
, edges
);
1016 return REG_FREQ_FROM_EDGE_FREQ (freq
);
1019 /* Calculate and return the cost of putting allocno A into memory. */
1021 calculate_allocno_spill_cost (ira_allocno_t a
)
1024 enum machine_mode mode
;
1025 enum reg_class rclass
;
1026 ira_allocno_t parent_allocno
;
1027 ira_loop_tree_node_t parent_node
, loop_node
;
1029 regno
= ALLOCNO_REGNO (a
);
1030 cost
= ALLOCNO_UPDATED_MEMORY_COST (a
) - ALLOCNO_UPDATED_COVER_CLASS_COST (a
);
1031 if (ALLOCNO_CAP (a
) != NULL
)
1033 loop_node
= ALLOCNO_LOOP_TREE_NODE (a
);
1034 if ((parent_node
= loop_node
->parent
) == NULL
)
1036 if ((parent_allocno
= parent_node
->regno_allocno_map
[regno
]) == NULL
)
1038 mode
= ALLOCNO_MODE (a
);
1039 rclass
= ALLOCNO_COVER_CLASS (a
);
1040 if (ALLOCNO_HARD_REGNO (parent_allocno
) < 0)
1041 cost
-= (ira_memory_move_cost
[mode
][rclass
][0]
1042 * ira_loop_edge_freq (loop_node
, regno
, true)
1043 + ira_memory_move_cost
[mode
][rclass
][1]
1044 * ira_loop_edge_freq (loop_node
, regno
, false));
1046 cost
+= ((ira_memory_move_cost
[mode
][rclass
][1]
1047 * ira_loop_edge_freq (loop_node
, regno
, true)
1048 + ira_memory_move_cost
[mode
][rclass
][0]
1049 * ira_loop_edge_freq (loop_node
, regno
, false))
1050 - (ira_register_move_cost
[mode
][rclass
][rclass
]
1051 * (ira_loop_edge_freq (loop_node
, regno
, false)
1052 + ira_loop_edge_freq (loop_node
, regno
, true))));
1056 /* Compare keys in the splay tree used to choose best allocno for
1057 spilling. The best allocno has the minimal key. */
1059 allocno_spill_priority_compare (splay_tree_key k1
, splay_tree_key k2
)
1061 int pri1
, pri2
, diff
;
1062 ira_allocno_t a1
= (ira_allocno_t
) k1
, a2
= (ira_allocno_t
) k2
;
1064 pri1
= (ALLOCNO_TEMP (a1
)
1065 / (ALLOCNO_LEFT_CONFLICTS_NUM (a1
)
1066 * ira_reg_class_nregs
[ALLOCNO_COVER_CLASS (a1
)][ALLOCNO_MODE (a1
)]
1068 pri2
= (ALLOCNO_TEMP (a2
)
1069 / (ALLOCNO_LEFT_CONFLICTS_NUM (a2
)
1070 * ira_reg_class_nregs
[ALLOCNO_COVER_CLASS (a2
)][ALLOCNO_MODE (a2
)]
1072 if ((diff
= pri1
- pri2
) != 0)
1074 if ((diff
= ALLOCNO_TEMP (a1
) - ALLOCNO_TEMP (a2
)) != 0)
1076 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
1079 /* Allocate data of SIZE for the splay trees. We allocate only spay
1080 tree roots or splay tree nodes. If you change this, please rewrite
1083 splay_tree_allocate (int size
, void *data ATTRIBUTE_UNUSED
)
1085 if (size
!= sizeof (struct splay_tree_node_s
))
1086 return ira_allocate (size
);
1087 return pool_alloc (splay_tree_node_pool
);
1090 /* Free data NODE for the splay trees. We allocate and free only spay
1091 tree roots or splay tree nodes. If you change this, please rewrite
1094 splay_tree_free (void *node
, void *data ATTRIBUTE_UNUSED
)
1097 enum reg_class cover_class
;
1099 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1101 cover_class
= ira_reg_class_cover
[i
];
1102 if (node
== uncolorable_allocnos_splay_tree
[cover_class
])
1108 pool_free (splay_tree_node_pool
, node
);
1111 /* Push allocnos to the coloring stack. The order of allocnos in the
1112 stack defines the order for the subsequent coloring. */
1114 push_allocnos_to_stack (void)
1116 ira_allocno_t allocno
, a
, i_allocno
, *allocno_vec
;
1117 enum reg_class cover_class
, rclass
;
1118 int allocno_pri
, i_allocno_pri
, allocno_cost
, i_allocno_cost
;
1119 int i
, j
, num
, cover_class_allocnos_num
[N_REG_CLASSES
];
1120 ira_allocno_t
*cover_class_allocnos
[N_REG_CLASSES
];
1124 VEC_truncate(ira_allocno_t
, removed_splay_allocno_vec
, 0);
1125 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1127 cover_class
= ira_reg_class_cover
[i
];
1128 cover_class_allocnos_num
[cover_class
] = 0;
1129 cover_class_allocnos
[cover_class
] = NULL
;
1130 uncolorable_allocnos_splay_tree
[cover_class
] = NULL
;
1132 /* Calculate uncolorable allocno spill costs. */
1133 for (allocno
= uncolorable_allocno_bucket
;
1135 allocno
= ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno
))
1136 if ((cover_class
= ALLOCNO_COVER_CLASS (allocno
)) != NO_REGS
)
1138 cover_class_allocnos_num
[cover_class
]++;
1140 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
1141 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1143 cost
+= calculate_allocno_spill_cost (a
);
1147 /* ??? Remove cost of copies between the coalesced
1149 ALLOCNO_TEMP (allocno
) = cost
;
1151 /* Define place where to put uncolorable allocnos of the same cover
1153 for (num
= i
= 0; i
< ira_reg_class_cover_size
; i
++)
1155 cover_class
= ira_reg_class_cover
[i
];
1156 ira_assert (cover_class_allocnos_num
[cover_class
]
1157 == uncolorable_allocnos_num
[cover_class
]);
1158 if (cover_class_allocnos_num
[cover_class
] != 0)
1160 cover_class_allocnos
[cover_class
] = allocnos_for_spilling
+ num
;
1161 num
+= cover_class_allocnos_num
[cover_class
];
1162 cover_class_allocnos_num
[cover_class
] = 0;
1164 if (USE_SPLAY_P (cover_class
))
1165 uncolorable_allocnos_splay_tree
[cover_class
]
1166 = splay_tree_new_with_allocator (allocno_spill_priority_compare
,
1167 NULL
, NULL
, splay_tree_allocate
,
1168 splay_tree_free
, NULL
);
1170 ira_assert (num
<= ira_allocnos_num
);
1171 /* Collect uncolorable allocnos of each cover class. */
1172 for (allocno
= uncolorable_allocno_bucket
;
1174 allocno
= ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno
))
1175 if ((cover_class
= ALLOCNO_COVER_CLASS (allocno
)) != NO_REGS
)
1177 cover_class_allocnos
1178 [cover_class
][cover_class_allocnos_num
[cover_class
]++] = allocno
;
1179 if (uncolorable_allocnos_splay_tree
[cover_class
] != NULL
)
1180 splay_tree_insert (uncolorable_allocnos_splay_tree
[cover_class
],
1181 (splay_tree_key
) allocno
,
1182 (splay_tree_value
) allocno
);
1186 push_only_colorable ();
1187 allocno
= uncolorable_allocno_bucket
;
1188 if (allocno
== NULL
)
1190 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
1191 if (cover_class
== NO_REGS
)
1193 push_allocno_to_spill (allocno
);
1196 /* Potential spilling. */
1198 (ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE (allocno
)] > 0);
1199 if (USE_SPLAY_P (cover_class
))
1201 for (;VEC_length (ira_allocno_t
, removed_splay_allocno_vec
) != 0;)
1203 allocno
= VEC_pop (ira_allocno_t
, removed_splay_allocno_vec
);
1204 ALLOCNO_SPLAY_REMOVED_P (allocno
) = false;
1205 rclass
= ALLOCNO_COVER_CLASS (allocno
);
1206 if (ALLOCNO_LEFT_CONFLICTS_NUM (allocno
)
1207 + ira_reg_class_nregs
[rclass
][ALLOCNO_MODE (allocno
)]
1208 > ALLOCNO_AVAILABLE_REGS_NUM (allocno
))
1210 (uncolorable_allocnos_splay_tree
[rclass
],
1211 (splay_tree_key
) allocno
, (splay_tree_value
) allocno
);
1213 allocno
= ((ira_allocno_t
)
1215 (uncolorable_allocnos_splay_tree
[cover_class
])->key
);
1216 splay_tree_remove (uncolorable_allocnos_splay_tree
[cover_class
],
1217 (splay_tree_key
) allocno
);
1221 num
= cover_class_allocnos_num
[cover_class
];
1222 ira_assert (num
> 0);
1223 allocno_vec
= cover_class_allocnos
[cover_class
];
1225 allocno_pri
= allocno_cost
= 0;
1226 /* Sort uncolorable allocno to find the one with the lowest
1228 for (i
= 0, j
= num
- 1; i
<= j
;)
1230 i_allocno
= allocno_vec
[i
];
1231 if (! ALLOCNO_IN_GRAPH_P (i_allocno
)
1232 && ALLOCNO_IN_GRAPH_P (allocno_vec
[j
]))
1234 i_allocno
= allocno_vec
[j
];
1235 allocno_vec
[j
] = allocno_vec
[i
];
1236 allocno_vec
[i
] = i_allocno
;
1238 if (ALLOCNO_IN_GRAPH_P (i_allocno
))
1241 ira_assert (ALLOCNO_TEMP (i_allocno
) != INT_MAX
);
1242 i_allocno_cost
= ALLOCNO_TEMP (i_allocno
);
1243 i_allocno_pri
= allocno_spill_priority (i_allocno
);
1245 || (! ALLOCNO_BAD_SPILL_P (i_allocno
)
1246 && ALLOCNO_BAD_SPILL_P (allocno
))
1247 || (! (ALLOCNO_BAD_SPILL_P (i_allocno
)
1248 && ! ALLOCNO_BAD_SPILL_P (allocno
))
1249 && (allocno_pri
> i_allocno_pri
1250 || (allocno_pri
== i_allocno_pri
1251 && (allocno_cost
> i_allocno_cost
1252 || (allocno_cost
== i_allocno_cost
1253 && (ALLOCNO_NUM (allocno
)
1254 > ALLOCNO_NUM (i_allocno
))))))))
1256 allocno
= i_allocno
;
1257 allocno_cost
= i_allocno_cost
;
1258 allocno_pri
= i_allocno_pri
;
1261 if (! ALLOCNO_IN_GRAPH_P (allocno_vec
[j
]))
1264 ira_assert (allocno
!= NULL
&& j
>= 0);
1265 cover_class_allocnos_num
[cover_class
] = j
+ 1;
1267 ira_assert (ALLOCNO_IN_GRAPH_P (allocno
)
1268 && ALLOCNO_COVER_CLASS (allocno
) == cover_class
1269 && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno
)
1270 + ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE
1272 > ALLOCNO_AVAILABLE_REGS_NUM (allocno
)));
1273 remove_allocno_from_bucket_and_push (allocno
, false);
1275 ira_assert (colorable_allocno_bucket
== NULL
1276 && uncolorable_allocno_bucket
== NULL
);
1277 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1279 cover_class
= ira_reg_class_cover
[i
];
1280 ira_assert (uncolorable_allocnos_num
[cover_class
] == 0);
1281 if (uncolorable_allocnos_splay_tree
[cover_class
] != NULL
)
1282 splay_tree_delete (uncolorable_allocnos_splay_tree
[cover_class
]);
1286 /* Pop the coloring stack and assign hard registers to the popped
1289 pop_allocnos_from_stack (void)
1291 ira_allocno_t allocno
;
1292 enum reg_class cover_class
;
1294 for (;VEC_length (ira_allocno_t
, allocno_stack_vec
) != 0;)
1296 allocno
= VEC_pop (ira_allocno_t
, allocno_stack_vec
);
1297 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
1298 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1300 fprintf (ira_dump_file
, " Popping");
1301 print_coalesced_allocno (allocno
);
1302 fprintf (ira_dump_file
, " -- ");
1304 if (cover_class
== NO_REGS
)
1306 ALLOCNO_HARD_REGNO (allocno
) = -1;
1307 ALLOCNO_ASSIGNED_P (allocno
) = true;
1308 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno
) == NULL
);
1310 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno
) == NULL
);
1311 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1312 fprintf (ira_dump_file
, "assign memory\n");
1314 else if (assign_hard_reg (allocno
, false))
1316 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1317 fprintf (ira_dump_file
, "assign reg %d\n",
1318 ALLOCNO_HARD_REGNO (allocno
));
1320 else if (ALLOCNO_ASSIGNED_P (allocno
))
1322 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1323 fprintf (ira_dump_file
, "spill\n");
1325 ALLOCNO_IN_GRAPH_P (allocno
) = true;
1329 /* Set up number of available hard registers for ALLOCNO. */
1331 setup_allocno_available_regs_num (ira_allocno_t allocno
)
1333 int i
, n
, hard_regs_num
;
1334 enum reg_class cover_class
;
1336 HARD_REG_SET temp_set
;
1338 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
1339 ALLOCNO_AVAILABLE_REGS_NUM (allocno
) = ira_available_class_regs
[cover_class
];
1340 if (cover_class
== NO_REGS
)
1342 CLEAR_HARD_REG_SET (temp_set
);
1343 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) == allocno
);
1344 hard_regs_num
= ira_class_hard_regs_num
[cover_class
];
1345 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
1346 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1348 IOR_HARD_REG_SET (temp_set
, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
1352 for (n
= 0, i
= hard_regs_num
- 1; i
>= 0; i
--)
1353 if (TEST_HARD_REG_BIT (temp_set
, ira_class_hard_regs
[cover_class
][i
]))
1355 if (internal_flag_ira_verbose
> 2 && n
> 0 && ira_dump_file
!= NULL
)
1356 fprintf (ira_dump_file
, " Reg %d of %s has %d regs less\n",
1357 ALLOCNO_REGNO (allocno
), reg_class_names
[cover_class
], n
);
1358 ALLOCNO_AVAILABLE_REGS_NUM (allocno
) -= n
;
1361 /* Set up ALLOCNO_LEFT_CONFLICTS_NUM for ALLOCNO. */
1363 setup_allocno_left_conflicts_num (ira_allocno_t allocno
)
1365 int i
, hard_regs_num
, hard_regno
, conflict_allocnos_size
;
1366 ira_allocno_t a
, conflict_allocno
;
1367 enum reg_class cover_class
;
1368 HARD_REG_SET temp_set
;
1369 ira_allocno_conflict_iterator aci
;
1371 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
1372 hard_regs_num
= ira_class_hard_regs_num
[cover_class
];
1373 CLEAR_HARD_REG_SET (temp_set
);
1374 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) == allocno
);
1375 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
1376 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1378 IOR_HARD_REG_SET (temp_set
, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
1382 AND_HARD_REG_SET (temp_set
, reg_class_contents
[cover_class
]);
1383 AND_COMPL_HARD_REG_SET (temp_set
, ira_no_alloc_regs
);
1384 conflict_allocnos_size
= 0;
1385 if (! hard_reg_set_empty_p (temp_set
))
1386 for (i
= 0; i
< (int) hard_regs_num
; i
++)
1388 hard_regno
= ira_class_hard_regs
[cover_class
][i
];
1389 if (TEST_HARD_REG_BIT (temp_set
, hard_regno
))
1391 conflict_allocnos_size
++;
1392 CLEAR_HARD_REG_BIT (temp_set
, hard_regno
);
1393 if (hard_reg_set_empty_p (temp_set
))
1397 CLEAR_HARD_REG_SET (temp_set
);
1398 if (allocno_coalesced_p
)
1399 bitmap_clear (processed_coalesced_allocno_bitmap
);
1400 if (cover_class
!= NO_REGS
)
1401 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
1402 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1404 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_allocno
, aci
)
1407 = ALLOCNO_FIRST_COALESCED_ALLOCNO (conflict_allocno
);
1408 if (bitmap_bit_p (consideration_allocno_bitmap
,
1409 ALLOCNO_NUM (conflict_allocno
)))
1411 ira_assert (cover_class
1412 == ALLOCNO_COVER_CLASS (conflict_allocno
));
1413 if (allocno_coalesced_p
)
1415 if (bitmap_bit_p (processed_coalesced_allocno_bitmap
,
1416 ALLOCNO_NUM (conflict_allocno
)))
1418 bitmap_set_bit (processed_coalesced_allocno_bitmap
,
1419 ALLOCNO_NUM (conflict_allocno
));
1421 if (! ALLOCNO_ASSIGNED_P (conflict_allocno
))
1422 conflict_allocnos_size
1423 += (ira_reg_class_nregs
1424 [cover_class
][ALLOCNO_MODE (conflict_allocno
)]);
1425 else if ((hard_regno
= ALLOCNO_HARD_REGNO (conflict_allocno
))
1428 int last
= (hard_regno
1430 [hard_regno
][ALLOCNO_MODE (conflict_allocno
)]);
1432 while (hard_regno
< last
)
1434 if (! TEST_HARD_REG_BIT (temp_set
, hard_regno
))
1436 conflict_allocnos_size
++;
1437 SET_HARD_REG_BIT (temp_set
, hard_regno
);
1447 ALLOCNO_LEFT_CONFLICTS_NUM (allocno
) = conflict_allocnos_size
;
1450 /* Put ALLOCNO in a bucket corresponding to its number and size of its
1451 conflicting allocnos and hard registers. */
1453 put_allocno_into_bucket (ira_allocno_t allocno
)
1456 enum reg_class cover_class
;
1458 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
1459 hard_regs_num
= ira_class_hard_regs_num
[cover_class
];
1460 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) != allocno
)
1462 ALLOCNO_IN_GRAPH_P (allocno
) = true;
1463 setup_allocno_left_conflicts_num (allocno
);
1464 setup_allocno_available_regs_num (allocno
);
1465 if (ALLOCNO_LEFT_CONFLICTS_NUM (allocno
)
1466 + ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE (allocno
)]
1467 <= ALLOCNO_AVAILABLE_REGS_NUM (allocno
))
1468 add_allocno_to_bucket (allocno
, &colorable_allocno_bucket
);
1470 add_allocno_to_bucket (allocno
, &uncolorable_allocno_bucket
);
1473 /* The function is used to sort allocnos according to their execution
1476 copy_freq_compare_func (const void *v1p
, const void *v2p
)
1478 ira_copy_t cp1
= *(const ira_copy_t
*) v1p
, cp2
= *(const ira_copy_t
*) v2p
;
1486 /* If freqencies are equal, sort by copies, so that the results of
1487 qsort leave nothing to chance. */
1488 return cp1
->num
- cp2
->num
;
1491 /* Merge two sets of coalesced allocnos given correspondingly by
1492 allocnos A1 and A2 (more accurately merging A2 set into A1
1495 merge_allocnos (ira_allocno_t a1
, ira_allocno_t a2
)
1497 ira_allocno_t a
, first
, last
, next
;
1499 first
= ALLOCNO_FIRST_COALESCED_ALLOCNO (a1
);
1500 if (first
== ALLOCNO_FIRST_COALESCED_ALLOCNO (a2
))
1502 for (last
= a2
, a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a2
);;
1503 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1505 ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) = first
;
1510 next
= ALLOCNO_NEXT_COALESCED_ALLOCNO (first
);
1511 ALLOCNO_NEXT_COALESCED_ALLOCNO (first
) = a2
;
1512 ALLOCNO_NEXT_COALESCED_ALLOCNO (last
) = next
;
1515 /* Return TRUE if there are conflicting allocnos from two sets of
1516 coalesced allocnos given correspondingly by allocnos A1 and A2. If
1517 RELOAD_P is TRUE, we use live ranges to find conflicts because
1518 conflicts are represented only for allocnos of the same cover class
1519 and during the reload pass we coalesce allocnos for sharing stack
1522 coalesced_allocno_conflict_p (ira_allocno_t a1
, ira_allocno_t a2
,
1525 ira_allocno_t a
, conflict_allocno
;
1526 ira_allocno_conflict_iterator aci
;
1528 if (allocno_coalesced_p
)
1530 bitmap_clear (processed_coalesced_allocno_bitmap
);
1531 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a1
);;
1532 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1534 bitmap_set_bit (processed_coalesced_allocno_bitmap
, ALLOCNO_NUM (a
));
1539 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a2
);;
1540 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1544 for (conflict_allocno
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a1
);;
1546 = ALLOCNO_NEXT_COALESCED_ALLOCNO (conflict_allocno
))
1548 if (allocnos_have_intersected_live_ranges_p (a
,
1551 if (conflict_allocno
== a1
)
1557 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_allocno
, aci
)
1558 if (conflict_allocno
== a1
1559 || (allocno_coalesced_p
1560 && bitmap_bit_p (processed_coalesced_allocno_bitmap
,
1561 ALLOCNO_NUM (conflict_allocno
))))
1570 /* The major function for aggressive allocno coalescing. For the
1571 reload pass (RELOAD_P) we coalesce only spilled allocnos. If some
1572 allocnos have been coalesced, we set up flag
1573 allocno_coalesced_p. */
1575 coalesce_allocnos (bool reload_p
)
1578 ira_copy_t cp
, next_cp
, *sorted_copies
;
1579 enum reg_class cover_class
;
1580 enum machine_mode mode
;
1582 int i
, n
, cp_num
, regno
;
1585 sorted_copies
= (ira_copy_t
*) ira_allocate (ira_copies_num
1586 * sizeof (ira_copy_t
));
1588 /* Collect copies. */
1589 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, j
, bi
)
1591 a
= ira_allocnos
[j
];
1592 regno
= ALLOCNO_REGNO (a
);
1593 if ((! reload_p
&& ALLOCNO_ASSIGNED_P (a
))
1595 && (! ALLOCNO_ASSIGNED_P (a
) || ALLOCNO_HARD_REGNO (a
) >= 0
1596 || (regno
< ira_reg_equiv_len
1597 && (ira_reg_equiv_const
[regno
] != NULL_RTX
1598 || ira_reg_equiv_invariant_p
[regno
])))))
1600 cover_class
= ALLOCNO_COVER_CLASS (a
);
1601 mode
= ALLOCNO_MODE (a
);
1602 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
1606 next_cp
= cp
->next_first_allocno_copy
;
1607 regno
= ALLOCNO_REGNO (cp
->second
);
1609 || (ALLOCNO_COVER_CLASS (cp
->second
) == cover_class
1610 && ALLOCNO_MODE (cp
->second
) == mode
))
1611 && (cp
->insn
!= NULL
|| cp
->constraint_p
)
1612 && ((! reload_p
&& ! ALLOCNO_ASSIGNED_P (cp
->second
))
1614 && ALLOCNO_ASSIGNED_P (cp
->second
)
1615 && ALLOCNO_HARD_REGNO (cp
->second
) < 0
1616 && (regno
>= ira_reg_equiv_len
1617 || (! ira_reg_equiv_invariant_p
[regno
]
1618 && ira_reg_equiv_const
[regno
] == NULL_RTX
)))))
1619 sorted_copies
[cp_num
++] = cp
;
1621 else if (cp
->second
== a
)
1622 next_cp
= cp
->next_second_allocno_copy
;
1627 qsort (sorted_copies
, cp_num
, sizeof (ira_copy_t
), copy_freq_compare_func
);
1628 /* Coalesced copies, most frequently executed first. */
1629 for (; cp_num
!= 0;)
1631 for (i
= 0; i
< cp_num
; i
++)
1633 cp
= sorted_copies
[i
];
1634 if (! coalesced_allocno_conflict_p (cp
->first
, cp
->second
, reload_p
))
1636 allocno_coalesced_p
= true;
1637 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1640 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
1641 cp
->num
, ALLOCNO_NUM (cp
->first
), ALLOCNO_REGNO (cp
->first
),
1642 ALLOCNO_NUM (cp
->second
), ALLOCNO_REGNO (cp
->second
),
1644 merge_allocnos (cp
->first
, cp
->second
);
1649 /* Collect the rest of copies. */
1650 for (n
= 0; i
< cp_num
; i
++)
1652 cp
= sorted_copies
[i
];
1653 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (cp
->first
)
1654 != ALLOCNO_FIRST_COALESCED_ALLOCNO (cp
->second
))
1655 sorted_copies
[n
++] = cp
;
1659 ira_free (sorted_copies
);
1662 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
1663 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
1665 color_allocnos (void)
1671 allocno_coalesced_p
= false;
1672 processed_coalesced_allocno_bitmap
= ira_allocate_bitmap ();
1673 if (flag_ira_coalesce
)
1674 coalesce_allocnos (false);
1675 /* Put the allocnos into the corresponding buckets. */
1676 colorable_allocno_bucket
= NULL
;
1677 uncolorable_allocno_bucket
= NULL
;
1678 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
1680 a
= ira_allocnos
[i
];
1681 if (ALLOCNO_COVER_CLASS (a
) == NO_REGS
)
1683 ALLOCNO_HARD_REGNO (a
) = -1;
1684 ALLOCNO_ASSIGNED_P (a
) = true;
1685 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
1686 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
1687 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1689 fprintf (ira_dump_file
, " Spill");
1690 print_coalesced_allocno (a
);
1691 fprintf (ira_dump_file
, "\n");
1695 put_allocno_into_bucket (a
);
1697 push_allocnos_to_stack ();
1698 pop_allocnos_from_stack ();
1699 if (flag_ira_coalesce
)
1700 /* We don't need coalesced allocnos for ira_reassign_pseudos. */
1701 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
1703 a
= ira_allocnos
[i
];
1704 ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) = a
;
1705 ALLOCNO_NEXT_COALESCED_ALLOCNO (a
) = a
;
1707 ira_free_bitmap (processed_coalesced_allocno_bitmap
);
1708 allocno_coalesced_p
= false;
1713 /* Output information about the loop given by its LOOP_TREE_NODE. */
1715 print_loop_title (ira_loop_tree_node_t loop_tree_node
)
1719 ira_loop_tree_node_t subloop_node
, dest_loop_node
;
1723 ira_assert (loop_tree_node
->loop
!= NULL
);
1724 fprintf (ira_dump_file
,
1725 "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
1726 loop_tree_node
->loop
->num
,
1727 (loop_tree_node
->parent
== NULL
1728 ? -1 : loop_tree_node
->parent
->loop
->num
),
1729 loop_tree_node
->loop
->header
->index
,
1730 loop_depth (loop_tree_node
->loop
));
1731 for (subloop_node
= loop_tree_node
->children
;
1732 subloop_node
!= NULL
;
1733 subloop_node
= subloop_node
->next
)
1734 if (subloop_node
->bb
!= NULL
)
1736 fprintf (ira_dump_file
, " %d", subloop_node
->bb
->index
);
1737 FOR_EACH_EDGE (e
, ei
, subloop_node
->bb
->succs
)
1738 if (e
->dest
!= EXIT_BLOCK_PTR
1739 && ((dest_loop_node
= IRA_BB_NODE (e
->dest
)->parent
)
1741 fprintf (ira_dump_file
, "(->%d:l%d)",
1742 e
->dest
->index
, dest_loop_node
->loop
->num
);
1744 fprintf (ira_dump_file
, "\n all:");
1745 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->all_allocnos
, 0, j
, bi
)
1746 fprintf (ira_dump_file
, " %dr%d", j
, ALLOCNO_REGNO (ira_allocnos
[j
]));
1747 fprintf (ira_dump_file
, "\n modified regnos:");
1748 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->modified_regnos
, 0, j
, bi
)
1749 fprintf (ira_dump_file
, " %d", j
);
1750 fprintf (ira_dump_file
, "\n border:");
1751 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->border_allocnos
, 0, j
, bi
)
1752 fprintf (ira_dump_file
, " %dr%d", j
, ALLOCNO_REGNO (ira_allocnos
[j
]));
1753 fprintf (ira_dump_file
, "\n Pressure:");
1754 for (j
= 0; (int) j
< ira_reg_class_cover_size
; j
++)
1756 enum reg_class cover_class
;
1758 cover_class
= ira_reg_class_cover
[j
];
1759 if (loop_tree_node
->reg_pressure
[cover_class
] == 0)
1761 fprintf (ira_dump_file
, " %s=%d", reg_class_names
[cover_class
],
1762 loop_tree_node
->reg_pressure
[cover_class
]);
1764 fprintf (ira_dump_file
, "\n");
1767 /* Color the allocnos inside loop (in the extreme case it can be all
1768 of the function) given the corresponding LOOP_TREE_NODE. The
1769 function is called for each loop during top-down traverse of the
1772 color_pass (ira_loop_tree_node_t loop_tree_node
)
1774 int regno
, hard_regno
, index
= -1;
1775 int cost
, exit_freq
, enter_freq
;
1778 enum machine_mode mode
;
1779 enum reg_class rclass
, cover_class
;
1780 ira_allocno_t a
, subloop_allocno
;
1781 ira_loop_tree_node_t subloop_node
;
1783 ira_assert (loop_tree_node
->bb
== NULL
);
1784 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
1785 print_loop_title (loop_tree_node
);
1787 bitmap_copy (coloring_allocno_bitmap
, loop_tree_node
->all_allocnos
);
1788 bitmap_copy (consideration_allocno_bitmap
, coloring_allocno_bitmap
);
1789 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
1791 a
= ira_allocnos
[j
];
1792 if (! ALLOCNO_ASSIGNED_P (a
))
1794 bitmap_clear_bit (coloring_allocno_bitmap
, ALLOCNO_NUM (a
));
1796 /* Color all mentioned allocnos including transparent ones. */
1798 /* Process caps. They are processed just once. */
1799 if (flag_ira_algorithm
== IRA_ALGORITHM_MIXED
1800 || flag_ira_algorithm
== IRA_ALGORITHM_REGIONAL
)
1801 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->all_allocnos
, 0, j
, bi
)
1803 a
= ira_allocnos
[j
];
1804 if (ALLOCNO_CAP_MEMBER (a
) == NULL
)
1806 /* Remove from processing in the next loop. */
1807 bitmap_clear_bit (consideration_allocno_bitmap
, j
);
1808 rclass
= ALLOCNO_COVER_CLASS (a
);
1809 if ((flag_ira_algorithm
== IRA_ALGORITHM_MIXED
1810 && loop_tree_node
->reg_pressure
[rclass
]
1811 <= ira_available_class_regs
[rclass
]))
1813 mode
= ALLOCNO_MODE (a
);
1814 hard_regno
= ALLOCNO_HARD_REGNO (a
);
1815 if (hard_regno
>= 0)
1817 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
1818 ira_assert (index
>= 0);
1820 regno
= ALLOCNO_REGNO (a
);
1821 subloop_allocno
= ALLOCNO_CAP_MEMBER (a
);
1822 subloop_node
= ALLOCNO_LOOP_TREE_NODE (subloop_allocno
);
1823 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno
));
1824 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
1825 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
1826 if (hard_regno
>= 0)
1827 update_copy_costs (subloop_allocno
, true);
1828 /* We don't need updated costs anymore: */
1829 ira_free_allocno_updated_costs (subloop_allocno
);
1832 /* Update costs of the corresponding allocnos (not caps) in the
1834 for (subloop_node
= loop_tree_node
->subloops
;
1835 subloop_node
!= NULL
;
1836 subloop_node
= subloop_node
->subloop_next
)
1838 ira_assert (subloop_node
->bb
== NULL
);
1839 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
1841 a
= ira_allocnos
[j
];
1842 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
1843 mode
= ALLOCNO_MODE (a
);
1844 rclass
= ALLOCNO_COVER_CLASS (a
);
1845 hard_regno
= ALLOCNO_HARD_REGNO (a
);
1846 if (hard_regno
>= 0)
1848 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
1849 ira_assert (index
>= 0);
1851 regno
= ALLOCNO_REGNO (a
);
1852 /* ??? conflict costs */
1853 subloop_allocno
= subloop_node
->regno_allocno_map
[regno
];
1854 if (subloop_allocno
== NULL
1855 || ALLOCNO_CAP (subloop_allocno
) != NULL
)
1857 ira_assert (bitmap_bit_p (subloop_node
->all_allocnos
,
1858 ALLOCNO_NUM (subloop_allocno
)));
1859 if (flag_ira_algorithm
== IRA_ALGORITHM_MIXED
1860 && (loop_tree_node
->reg_pressure
[rclass
]
1861 <= ira_available_class_regs
[rclass
]))
1863 if (! ALLOCNO_ASSIGNED_P (subloop_allocno
))
1865 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
1866 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
1867 if (hard_regno
>= 0)
1868 update_copy_costs (subloop_allocno
, true);
1869 /* We don't need updated costs anymore: */
1870 ira_free_allocno_updated_costs (subloop_allocno
);
1874 exit_freq
= ira_loop_edge_freq (subloop_node
, regno
, true);
1875 enter_freq
= ira_loop_edge_freq (subloop_node
, regno
, false);
1876 ira_assert (regno
< ira_reg_equiv_len
);
1877 if (ira_reg_equiv_invariant_p
[regno
]
1878 || ira_reg_equiv_const
[regno
] != NULL_RTX
)
1880 if (! ALLOCNO_ASSIGNED_P (subloop_allocno
))
1882 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
1883 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
1884 if (hard_regno
>= 0)
1885 update_copy_costs (subloop_allocno
, true);
1886 /* We don't need updated costs anymore: */
1887 ira_free_allocno_updated_costs (subloop_allocno
);
1890 else if (hard_regno
< 0)
1892 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno
)
1893 -= ((ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
)
1894 + (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
));
1898 cover_class
= ALLOCNO_COVER_CLASS (subloop_allocno
);
1899 cost
= (ira_register_move_cost
[mode
][rclass
][rclass
]
1900 * (exit_freq
+ enter_freq
));
1901 ira_allocate_and_set_or_copy_costs
1902 (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
), cover_class
,
1903 ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno
),
1904 ALLOCNO_HARD_REG_COSTS (subloop_allocno
));
1905 ira_allocate_and_set_or_copy_costs
1906 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno
),
1908 ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno
));
1909 ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
] -= cost
;
1910 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno
)[index
]
1912 if (ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno
)
1913 > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
])
1914 ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno
)
1915 = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
];
1916 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno
)
1917 += (ira_memory_move_cost
[mode
][rclass
][0] * enter_freq
1918 + ira_memory_move_cost
[mode
][rclass
][1] * exit_freq
);
1924 /* Initialize the common data for coloring and calls functions to do
1925 Chaitin-Briggs and regional coloring. */
1929 coloring_allocno_bitmap
= ira_allocate_bitmap ();
1930 allocnos_for_spilling
1931 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
1932 * ira_allocnos_num
);
1933 splay_tree_node_pool
= create_alloc_pool ("splay tree nodes",
1934 sizeof (struct splay_tree_node_s
),
1936 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
1937 fprintf (ira_dump_file
, "\n**** Allocnos coloring:\n\n");
1939 ira_traverse_loop_tree (false, ira_loop_tree_root
, color_pass
, NULL
);
1941 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
1942 ira_print_disposition (ira_dump_file
);
1944 free_alloc_pool (splay_tree_node_pool
);
1945 ira_free_bitmap (coloring_allocno_bitmap
);
1946 ira_free (allocnos_for_spilling
);
1951 /* Move spill/restore code, which are to be generated in ira-emit.c,
1952 to less frequent points (if it is profitable) by reassigning some
1953 allocnos (in loop with subloops containing in another loop) to
1954 memory which results in longer live-range where the corresponding
1955 pseudo-registers will be in memory. */
1957 move_spill_restore (void)
1959 int cost
, regno
, hard_regno
, hard_regno2
, index
;
1961 int enter_freq
, exit_freq
;
1962 enum machine_mode mode
;
1963 enum reg_class rclass
;
1964 ira_allocno_t a
, parent_allocno
, subloop_allocno
;
1965 ira_loop_tree_node_t parent
, loop_node
, subloop_node
;
1966 ira_allocno_iterator ai
;
1971 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
1972 fprintf (ira_dump_file
, "New iteration of spill/restore move\n");
1973 FOR_EACH_ALLOCNO (a
, ai
)
1975 regno
= ALLOCNO_REGNO (a
);
1976 loop_node
= ALLOCNO_LOOP_TREE_NODE (a
);
1977 if (ALLOCNO_CAP_MEMBER (a
) != NULL
1978 || ALLOCNO_CAP (a
) != NULL
1979 || (hard_regno
= ALLOCNO_HARD_REGNO (a
)) < 0
1980 || loop_node
->children
== NULL
1981 /* don't do the optimization because it can create
1982 copies and the reload pass can spill the allocno set
1983 by copy although the allocno will not get memory
1985 || ira_reg_equiv_invariant_p
[regno
]
1986 || ira_reg_equiv_const
[regno
] != NULL_RTX
1987 || !bitmap_bit_p (loop_node
->border_allocnos
, ALLOCNO_NUM (a
)))
1989 mode
= ALLOCNO_MODE (a
);
1990 rclass
= ALLOCNO_COVER_CLASS (a
);
1991 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
1992 ira_assert (index
>= 0);
1993 cost
= (ALLOCNO_MEMORY_COST (a
)
1994 - (ALLOCNO_HARD_REG_COSTS (a
) == NULL
1995 ? ALLOCNO_COVER_CLASS_COST (a
)
1996 : ALLOCNO_HARD_REG_COSTS (a
)[index
]));
1997 for (subloop_node
= loop_node
->subloops
;
1998 subloop_node
!= NULL
;
1999 subloop_node
= subloop_node
->subloop_next
)
2001 ira_assert (subloop_node
->bb
== NULL
);
2002 subloop_allocno
= subloop_node
->regno_allocno_map
[regno
];
2003 if (subloop_allocno
== NULL
)
2005 /* We have accumulated cost. To get the real cost of
2006 allocno usage in the loop we should subtract costs of
2007 the subloop allocnos. */
2008 cost
-= (ALLOCNO_MEMORY_COST (subloop_allocno
)
2009 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno
) == NULL
2010 ? ALLOCNO_COVER_CLASS_COST (subloop_allocno
)
2011 : ALLOCNO_HARD_REG_COSTS (subloop_allocno
)[index
]));
2012 exit_freq
= ira_loop_edge_freq (subloop_node
, regno
, true);
2013 enter_freq
= ira_loop_edge_freq (subloop_node
, regno
, false);
2014 if ((hard_regno2
= ALLOCNO_HARD_REGNO (subloop_allocno
)) < 0)
2015 cost
-= (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
2016 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
2020 += (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
2021 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
2022 if (hard_regno2
!= hard_regno
)
2023 cost
-= (ira_register_move_cost
[mode
][rclass
][rclass
]
2024 * (exit_freq
+ enter_freq
));
2027 if ((parent
= loop_node
->parent
) != NULL
2028 && (parent_allocno
= parent
->regno_allocno_map
[regno
]) != NULL
)
2030 exit_freq
= ira_loop_edge_freq (loop_node
, regno
, true);
2031 enter_freq
= ira_loop_edge_freq (loop_node
, regno
, false);
2032 if ((hard_regno2
= ALLOCNO_HARD_REGNO (parent_allocno
)) < 0)
2033 cost
-= (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
2034 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
2038 += (ira_memory_move_cost
[mode
][rclass
][1] * exit_freq
2039 + ira_memory_move_cost
[mode
][rclass
][0] * enter_freq
);
2040 if (hard_regno2
!= hard_regno
)
2041 cost
-= (ira_register_move_cost
[mode
][rclass
][rclass
]
2042 * (exit_freq
+ enter_freq
));
2047 ALLOCNO_HARD_REGNO (a
) = -1;
2048 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2052 " Moving spill/restore for a%dr%d up from loop %d",
2053 ALLOCNO_NUM (a
), regno
, loop_node
->loop
->num
);
2054 fprintf (ira_dump_file
, " - profit %d\n", -cost
);
2066 /* Update current hard reg costs and current conflict hard reg costs
2067 for allocno A. It is done by processing its copies containing
2068 other allocnos already assigned. */
2070 update_curr_costs (ira_allocno_t a
)
2072 int i
, hard_regno
, cost
;
2073 enum machine_mode mode
;
2074 enum reg_class cover_class
, rclass
;
2075 ira_allocno_t another_a
;
2076 ira_copy_t cp
, next_cp
;
2078 ira_assert (! ALLOCNO_ASSIGNED_P (a
));
2079 cover_class
= ALLOCNO_COVER_CLASS (a
);
2080 if (cover_class
== NO_REGS
)
2082 mode
= ALLOCNO_MODE (a
);
2083 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
2087 next_cp
= cp
->next_first_allocno_copy
;
2088 another_a
= cp
->second
;
2090 else if (cp
->second
== a
)
2092 next_cp
= cp
->next_second_allocno_copy
;
2093 another_a
= cp
->first
;
2097 if (cover_class
!= ALLOCNO_COVER_CLASS (another_a
)
2098 || ! ALLOCNO_ASSIGNED_P (another_a
)
2099 || (hard_regno
= ALLOCNO_HARD_REGNO (another_a
)) < 0)
2101 rclass
= REGNO_REG_CLASS (hard_regno
);
2102 i
= ira_class_hard_reg_index
[cover_class
][hard_regno
];
2103 ira_assert (i
>= 0);
2104 cost
= (cp
->first
== a
2105 ? ira_register_move_cost
[mode
][rclass
][cover_class
]
2106 : ira_register_move_cost
[mode
][cover_class
][rclass
]);
2107 ira_allocate_and_set_or_copy_costs
2108 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a
),
2109 cover_class
, ALLOCNO_COVER_CLASS_COST (a
),
2110 ALLOCNO_HARD_REG_COSTS (a
));
2111 ira_allocate_and_set_or_copy_costs
2112 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
),
2113 cover_class
, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a
));
2114 ALLOCNO_UPDATED_HARD_REG_COSTS (a
)[i
] -= cp
->freq
* cost
;
2115 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
)[i
] -= cp
->freq
* cost
;
2119 /* Map: allocno number -> allocno priority. */
2120 static int *allocno_priorities
;
2122 /* Set up priorities for N allocnos in array
2123 CONSIDERATION_ALLOCNOS. */
2125 setup_allocno_priorities (ira_allocno_t
*consideration_allocnos
, int n
)
2127 int i
, length
, nrefs
, priority
, max_priority
, mult
;
2131 for (i
= 0; i
< n
; i
++)
2133 a
= consideration_allocnos
[i
];
2134 nrefs
= ALLOCNO_NREFS (a
);
2135 ira_assert (nrefs
>= 0);
2136 mult
= floor_log2 (ALLOCNO_NREFS (a
)) + 1;
2137 ira_assert (mult
>= 0);
2138 allocno_priorities
[ALLOCNO_NUM (a
)]
2141 * (ALLOCNO_MEMORY_COST (a
) - ALLOCNO_COVER_CLASS_COST (a
))
2142 * ira_reg_class_nregs
[ALLOCNO_COVER_CLASS (a
)][ALLOCNO_MODE (a
)]);
2144 priority
= -priority
;
2145 if (max_priority
< priority
)
2146 max_priority
= priority
;
2148 mult
= max_priority
== 0 ? 1 : INT_MAX
/ max_priority
;
2149 for (i
= 0; i
< n
; i
++)
2151 a
= consideration_allocnos
[i
];
2152 length
= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
2155 allocno_priorities
[ALLOCNO_NUM (a
)]
2156 = allocno_priorities
[ALLOCNO_NUM (a
)] * mult
/ length
;
2160 /* Sort allocnos according to their priorities which are calculated
2161 analogous to ones in file `global.c'. */
2163 allocno_priority_compare_func (const void *v1p
, const void *v2p
)
2165 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
2166 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
2169 pri1
= allocno_priorities
[ALLOCNO_NUM (a1
)];
2170 pri2
= allocno_priorities
[ALLOCNO_NUM (a2
)];
2174 /* If regs are equally good, sort by allocnos, so that the results of
2175 qsort leave nothing to chance. */
2176 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
2179 /* Try to assign hard registers to the unassigned allocnos and
2180 allocnos conflicting with them or conflicting with allocnos whose
2181 regno >= START_REGNO. The function is called after ira_flattening,
2182 so more allocnos (including ones created in ira-emit.c) will have a
2183 chance to get a hard register. We use simple assignment algorithm
2184 based on priorities. */
2186 ira_reassign_conflict_allocnos (int start_regno
)
2188 int i
, allocnos_to_color_num
;
2189 ira_allocno_t a
, conflict_a
;
2190 ira_allocno_conflict_iterator aci
;
2191 enum reg_class cover_class
;
2192 bitmap allocnos_to_color
;
2193 ira_allocno_iterator ai
;
2195 allocnos_to_color
= ira_allocate_bitmap ();
2196 allocnos_to_color_num
= 0;
2197 FOR_EACH_ALLOCNO (a
, ai
)
2199 if (! ALLOCNO_ASSIGNED_P (a
)
2200 && ! bitmap_bit_p (allocnos_to_color
, ALLOCNO_NUM (a
)))
2202 if (ALLOCNO_COVER_CLASS (a
) != NO_REGS
)
2203 sorted_allocnos
[allocnos_to_color_num
++] = a
;
2206 ALLOCNO_ASSIGNED_P (a
) = true;
2207 ALLOCNO_HARD_REGNO (a
) = -1;
2208 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
2209 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
2211 bitmap_set_bit (allocnos_to_color
, ALLOCNO_NUM (a
));
2213 if (ALLOCNO_REGNO (a
) < start_regno
2214 || (cover_class
= ALLOCNO_COVER_CLASS (a
)) == NO_REGS
)
2216 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_a
, aci
)
2218 ira_assert (cover_class
== ALLOCNO_COVER_CLASS (conflict_a
));
2219 if (bitmap_bit_p (allocnos_to_color
, ALLOCNO_NUM (conflict_a
)))
2221 bitmap_set_bit (allocnos_to_color
, ALLOCNO_NUM (conflict_a
));
2222 sorted_allocnos
[allocnos_to_color_num
++] = conflict_a
;
2225 ira_free_bitmap (allocnos_to_color
);
2226 if (allocnos_to_color_num
> 1)
2228 setup_allocno_priorities (sorted_allocnos
, allocnos_to_color_num
);
2229 qsort (sorted_allocnos
, allocnos_to_color_num
, sizeof (ira_allocno_t
),
2230 allocno_priority_compare_func
);
2232 for (i
= 0; i
< allocnos_to_color_num
; i
++)
2234 a
= sorted_allocnos
[i
];
2235 ALLOCNO_ASSIGNED_P (a
) = false;
2236 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
2237 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
2238 update_curr_costs (a
);
2240 for (i
= 0; i
< allocnos_to_color_num
; i
++)
2242 a
= sorted_allocnos
[i
];
2243 if (assign_hard_reg (a
, true))
2245 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2248 " Secondary allocation: assign hard reg %d to reg %d\n",
2249 ALLOCNO_HARD_REGNO (a
), ALLOCNO_REGNO (a
));
2256 /* This page contains code to coalesce memory stack slots used by
2257 spilled allocnos. This results in smaller stack frame, better data
2258 locality, and in smaller code for some architectures like
2259 x86/x86_64 where insn size depends on address displacement value.
2260 On the other hand, it can worsen insn scheduling after the RA but
2261 in practice it is less important than smaller stack frames. */
2263 /* Usage cost and order number of coalesced allocno set to which
2264 given pseudo register belongs to. */
2265 static int *regno_coalesced_allocno_cost
;
2266 static int *regno_coalesced_allocno_num
;
2268 /* Sort pseudos according frequencies of coalesced allocno sets they
2269 belong to (putting most frequently ones first), and according to
2270 coalesced allocno set order numbers. */
2272 coalesced_pseudo_reg_freq_compare (const void *v1p
, const void *v2p
)
2274 const int regno1
= *(const int *) v1p
;
2275 const int regno2
= *(const int *) v2p
;
2278 if ((diff
= (regno_coalesced_allocno_cost
[regno2
]
2279 - regno_coalesced_allocno_cost
[regno1
])) != 0)
2281 if ((diff
= (regno_coalesced_allocno_num
[regno1
]
2282 - regno_coalesced_allocno_num
[regno2
])) != 0)
2284 return regno1
- regno2
;
2287 /* Widest width in which each pseudo reg is referred to (via subreg).
2288 It is used for sorting pseudo registers. */
2289 static unsigned int *regno_max_ref_width
;
2291 /* Redefine STACK_GROWS_DOWNWARD in terms of 0 or 1. */
2292 #ifdef STACK_GROWS_DOWNWARD
2293 # undef STACK_GROWS_DOWNWARD
2294 # define STACK_GROWS_DOWNWARD 1
2296 # define STACK_GROWS_DOWNWARD 0
2299 /* Sort pseudos according their slot numbers (putting ones with
2300 smaller numbers first, or last when the frame pointer is not
2303 coalesced_pseudo_reg_slot_compare (const void *v1p
, const void *v2p
)
2305 const int regno1
= *(const int *) v1p
;
2306 const int regno2
= *(const int *) v2p
;
2307 ira_allocno_t a1
= ira_regno_allocno_map
[regno1
];
2308 ira_allocno_t a2
= ira_regno_allocno_map
[regno2
];
2309 int diff
, slot_num1
, slot_num2
;
2310 int total_size1
, total_size2
;
2312 if (a1
== NULL
|| ALLOCNO_HARD_REGNO (a1
) >= 0)
2314 if (a2
== NULL
|| ALLOCNO_HARD_REGNO (a2
) >= 0)
2315 return regno1
- regno2
;
2318 else if (a2
== NULL
|| ALLOCNO_HARD_REGNO (a2
) >= 0)
2320 slot_num1
= -ALLOCNO_HARD_REGNO (a1
);
2321 slot_num2
= -ALLOCNO_HARD_REGNO (a2
);
2322 if ((diff
= slot_num1
- slot_num2
) != 0)
2323 return (frame_pointer_needed
2324 || !FRAME_GROWS_DOWNWARD
== STACK_GROWS_DOWNWARD
? diff
: -diff
);
2325 total_size1
= MAX (PSEUDO_REGNO_BYTES (regno1
), regno_max_ref_width
[regno1
]);
2326 total_size2
= MAX (PSEUDO_REGNO_BYTES (regno2
), regno_max_ref_width
[regno2
]);
2327 if ((diff
= total_size2
- total_size1
) != 0)
2329 return regno1
- regno2
;
2332 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
2333 for coalesced allocno sets containing allocnos with their regnos
2334 given in array PSEUDO_REGNOS of length N. */
2336 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos
, int n
)
2338 int i
, num
, regno
, cost
;
2339 ira_allocno_t allocno
, a
;
2341 for (num
= i
= 0; i
< n
; i
++)
2343 regno
= pseudo_regnos
[i
];
2344 allocno
= ira_regno_allocno_map
[regno
];
2345 if (allocno
== NULL
)
2347 regno_coalesced_allocno_cost
[regno
] = 0;
2348 regno_coalesced_allocno_num
[regno
] = ++num
;
2351 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) != allocno
)
2354 for (cost
= 0, a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
2355 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
2357 cost
+= ALLOCNO_FREQ (a
);
2361 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
2362 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
2364 regno_coalesced_allocno_num
[ALLOCNO_REGNO (a
)] = num
;
2365 regno_coalesced_allocno_cost
[ALLOCNO_REGNO (a
)] = cost
;
2372 /* Collect spilled allocnos representing coalesced allocno sets (the
2373 first coalesced allocno). The collected allocnos are returned
2374 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
2375 number of the collected allocnos. The allocnos are given by their
2376 regnos in array PSEUDO_REGNOS of length N. */
2378 collect_spilled_coalesced_allocnos (int *pseudo_regnos
, int n
,
2379 ira_allocno_t
*spilled_coalesced_allocnos
)
2382 ira_allocno_t allocno
;
2384 for (num
= i
= 0; i
< n
; i
++)
2386 regno
= pseudo_regnos
[i
];
2387 allocno
= ira_regno_allocno_map
[regno
];
2388 if (allocno
== NULL
|| ALLOCNO_HARD_REGNO (allocno
) >= 0
2389 || ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) != allocno
)
2391 spilled_coalesced_allocnos
[num
++] = allocno
;
2396 /* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
2397 given slot contains live ranges of coalesced allocnos assigned to
2399 static allocno_live_range_t
*slot_coalesced_allocnos_live_ranges
;
2401 /* Return TRUE if coalesced allocnos represented by ALLOCNO has live
2402 ranges intersected with live ranges of coalesced allocnos assigned
2403 to slot with number N. */
2405 slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno
, int n
)
2409 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
2410 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
2412 if (ira_allocno_live_ranges_intersect_p
2413 (slot_coalesced_allocnos_live_ranges
[n
], ALLOCNO_LIVE_RANGES (a
)))
2421 /* Update live ranges of slot to which coalesced allocnos represented
2422 by ALLOCNO were assigned. */
2424 setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno
)
2428 allocno_live_range_t r
;
2430 n
= ALLOCNO_TEMP (allocno
);
2431 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
2432 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
2434 r
= ira_copy_allocno_live_range_list (ALLOCNO_LIVE_RANGES (a
));
2435 slot_coalesced_allocnos_live_ranges
[n
]
2436 = ira_merge_allocno_live_ranges
2437 (slot_coalesced_allocnos_live_ranges
[n
], r
);
2443 /* We have coalesced allocnos involving in copies. Coalesce allocnos
2444 further in order to share the same memory stack slot. Allocnos
2445 representing sets of allocnos coalesced before the call are given
2446 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
2447 some allocnos were coalesced in the function. */
2449 coalesce_spill_slots (ira_allocno_t
*spilled_coalesced_allocnos
, int num
)
2451 int i
, j
, n
, last_coalesced_allocno_num
;
2452 ira_allocno_t allocno
, a
;
2453 bool merged_p
= false;
2455 slot_coalesced_allocnos_live_ranges
2456 = (allocno_live_range_t
*) ira_allocate (sizeof (allocno_live_range_t
)
2457 * ira_allocnos_num
);
2458 memset (slot_coalesced_allocnos_live_ranges
, 0,
2459 sizeof (allocno_live_range_t
) * ira_allocnos_num
);
2460 last_coalesced_allocno_num
= 0;
2461 /* Coalesce non-conflicting spilled allocnos preferring most
2463 for (i
= 0; i
< num
; i
++)
2465 allocno
= spilled_coalesced_allocnos
[i
];
2466 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) != allocno
2467 || (ALLOCNO_REGNO (allocno
) < ira_reg_equiv_len
2468 && (ira_reg_equiv_const
[ALLOCNO_REGNO (allocno
)] != NULL_RTX
2469 || ira_reg_equiv_invariant_p
[ALLOCNO_REGNO (allocno
)])))
2471 for (j
= 0; j
< i
; j
++)
2473 a
= spilled_coalesced_allocnos
[j
];
2474 n
= ALLOCNO_TEMP (a
);
2475 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) == a
2476 && (ALLOCNO_REGNO (a
) >= ira_reg_equiv_len
2477 || (! ira_reg_equiv_invariant_p
[ALLOCNO_REGNO (a
)]
2478 && ira_reg_equiv_const
[ALLOCNO_REGNO (a
)] == NULL_RTX
))
2479 && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno
, n
))
2484 /* No coalescing: set up number for coalesced allocnos
2485 represented by ALLOCNO. */
2486 ALLOCNO_TEMP (allocno
) = last_coalesced_allocno_num
++;
2487 setup_slot_coalesced_allocno_live_ranges (allocno
);
2491 allocno_coalesced_p
= true;
2493 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2494 fprintf (ira_dump_file
,
2495 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
2496 ALLOCNO_NUM (allocno
), ALLOCNO_REGNO (allocno
),
2497 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
2498 ALLOCNO_TEMP (allocno
) = ALLOCNO_TEMP (a
);
2499 setup_slot_coalesced_allocno_live_ranges (allocno
);
2500 merge_allocnos (a
, allocno
);
2501 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) == a
);
2504 for (i
= 0; i
< ira_allocnos_num
; i
++)
2505 ira_finish_allocno_live_range_list
2506 (slot_coalesced_allocnos_live_ranges
[i
]);
2507 ira_free (slot_coalesced_allocnos_live_ranges
);
2511 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
2512 subsequent assigning stack slots to them in the reload pass. To do
2513 this we coalesce spilled allocnos first to decrease the number of
2514 memory-memory move insns. This function is called by the
2517 ira_sort_regnos_for_alter_reg (int *pseudo_regnos
, int n
,
2518 unsigned int *reg_max_ref_width
)
2520 int max_regno
= max_reg_num ();
2521 int i
, regno
, num
, slot_num
;
2522 ira_allocno_t allocno
, a
;
2523 ira_allocno_iterator ai
;
2524 ira_allocno_t
*spilled_coalesced_allocnos
;
2526 processed_coalesced_allocno_bitmap
= ira_allocate_bitmap ();
2527 /* Set up allocnos can be coalesced. */
2528 coloring_allocno_bitmap
= ira_allocate_bitmap ();
2529 for (i
= 0; i
< n
; i
++)
2531 regno
= pseudo_regnos
[i
];
2532 allocno
= ira_regno_allocno_map
[regno
];
2533 if (allocno
!= NULL
)
2534 bitmap_set_bit (coloring_allocno_bitmap
,
2535 ALLOCNO_NUM (allocno
));
2537 allocno_coalesced_p
= false;
2538 coalesce_allocnos (true);
2539 ira_free_bitmap (coloring_allocno_bitmap
);
2540 regno_coalesced_allocno_cost
2541 = (int *) ira_allocate (max_regno
* sizeof (int));
2542 regno_coalesced_allocno_num
2543 = (int *) ira_allocate (max_regno
* sizeof (int));
2544 memset (regno_coalesced_allocno_num
, 0, max_regno
* sizeof (int));
2545 setup_coalesced_allocno_costs_and_nums (pseudo_regnos
, n
);
2546 /* Sort regnos according frequencies of the corresponding coalesced
2548 qsort (pseudo_regnos
, n
, sizeof (int), coalesced_pseudo_reg_freq_compare
);
2549 spilled_coalesced_allocnos
2550 = (ira_allocno_t
*) ira_allocate (ira_allocnos_num
2551 * sizeof (ira_allocno_t
));
2552 /* Collect allocnos representing the spilled coalesced allocno
2554 num
= collect_spilled_coalesced_allocnos (pseudo_regnos
, n
,
2555 spilled_coalesced_allocnos
);
2556 if (flag_ira_share_spill_slots
2557 && coalesce_spill_slots (spilled_coalesced_allocnos
, num
))
2559 setup_coalesced_allocno_costs_and_nums (pseudo_regnos
, n
);
2560 qsort (pseudo_regnos
, n
, sizeof (int),
2561 coalesced_pseudo_reg_freq_compare
);
2562 num
= collect_spilled_coalesced_allocnos (pseudo_regnos
, n
,
2563 spilled_coalesced_allocnos
);
2565 ira_free_bitmap (processed_coalesced_allocno_bitmap
);
2566 allocno_coalesced_p
= false;
2567 /* Assign stack slot numbers to spilled allocno sets, use smaller
2568 numbers for most frequently used coalesced allocnos. -1 is
2569 reserved for dynamic search of stack slots for pseudos spilled by
2572 for (i
= 0; i
< num
; i
++)
2574 allocno
= spilled_coalesced_allocnos
[i
];
2575 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) != allocno
2576 || ALLOCNO_HARD_REGNO (allocno
) >= 0
2577 || (ALLOCNO_REGNO (allocno
) < ira_reg_equiv_len
2578 && (ira_reg_equiv_const
[ALLOCNO_REGNO (allocno
)] != NULL_RTX
2579 || ira_reg_equiv_invariant_p
[ALLOCNO_REGNO (allocno
)])))
2581 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2582 fprintf (ira_dump_file
, " Slot %d (freq,size):", slot_num
);
2584 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
2585 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
2587 ira_assert (ALLOCNO_HARD_REGNO (a
) < 0);
2588 ALLOCNO_HARD_REGNO (a
) = -slot_num
;
2589 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2590 fprintf (ira_dump_file
, " a%dr%d(%d,%d)",
2591 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
), ALLOCNO_FREQ (a
),
2592 MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a
)),
2593 reg_max_ref_width
[ALLOCNO_REGNO (a
)]));
2598 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2599 fprintf (ira_dump_file
, "\n");
2601 ira_spilled_reg_stack_slots_num
= slot_num
- 1;
2602 ira_free (spilled_coalesced_allocnos
);
2603 /* Sort regnos according the slot numbers. */
2604 regno_max_ref_width
= reg_max_ref_width
;
2605 qsort (pseudo_regnos
, n
, sizeof (int), coalesced_pseudo_reg_slot_compare
);
2606 /* Uncoalesce allocnos which is necessary for (re)assigning during
2608 FOR_EACH_ALLOCNO (a
, ai
)
2610 ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) = a
;
2611 ALLOCNO_NEXT_COALESCED_ALLOCNO (a
) = a
;
2613 ira_free (regno_coalesced_allocno_num
);
2614 ira_free (regno_coalesced_allocno_cost
);
2619 /* This page contains code used by the reload pass to improve the
2622 /* The function is called from reload to mark changes in the
2623 allocation of REGNO made by the reload. Remember that reg_renumber
2624 reflects the change result. */
2626 ira_mark_allocation_change (int regno
)
2628 ira_allocno_t a
= ira_regno_allocno_map
[regno
];
2629 int old_hard_regno
, hard_regno
, cost
;
2630 enum reg_class cover_class
= ALLOCNO_COVER_CLASS (a
);
2632 ira_assert (a
!= NULL
);
2633 hard_regno
= reg_renumber
[regno
];
2634 if ((old_hard_regno
= ALLOCNO_HARD_REGNO (a
)) == hard_regno
)
2636 if (old_hard_regno
< 0)
2637 cost
= -ALLOCNO_MEMORY_COST (a
);
2640 ira_assert (ira_class_hard_reg_index
[cover_class
][old_hard_regno
] >= 0);
2641 cost
= -(ALLOCNO_HARD_REG_COSTS (a
) == NULL
2642 ? ALLOCNO_COVER_CLASS_COST (a
)
2643 : ALLOCNO_HARD_REG_COSTS (a
)
2644 [ira_class_hard_reg_index
[cover_class
][old_hard_regno
]]);
2645 update_copy_costs (a
, false);
2647 ira_overall_cost
-= cost
;
2648 ALLOCNO_HARD_REGNO (a
) = hard_regno
;
2651 ALLOCNO_HARD_REGNO (a
) = -1;
2652 cost
+= ALLOCNO_MEMORY_COST (a
);
2654 else if (ira_class_hard_reg_index
[cover_class
][hard_regno
] >= 0)
2656 cost
+= (ALLOCNO_HARD_REG_COSTS (a
) == NULL
2657 ? ALLOCNO_COVER_CLASS_COST (a
)
2658 : ALLOCNO_HARD_REG_COSTS (a
)
2659 [ira_class_hard_reg_index
[cover_class
][hard_regno
]]);
2660 update_copy_costs (a
, true);
2663 /* Reload changed class of the allocno. */
2665 ira_overall_cost
+= cost
;
2668 /* This function is called when reload deletes memory-memory move. In
2669 this case we marks that the allocation of the corresponding
2670 allocnos should be not changed in future. Otherwise we risk to get
2673 ira_mark_memory_move_deletion (int dst_regno
, int src_regno
)
2675 ira_allocno_t dst
= ira_regno_allocno_map
[dst_regno
];
2676 ira_allocno_t src
= ira_regno_allocno_map
[src_regno
];
2678 ira_assert (dst
!= NULL
&& src
!= NULL
2679 && ALLOCNO_HARD_REGNO (dst
) < 0
2680 && ALLOCNO_HARD_REGNO (src
) < 0);
2681 ALLOCNO_DONT_REASSIGN_P (dst
) = true;
2682 ALLOCNO_DONT_REASSIGN_P (src
) = true;
2685 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
2686 allocno A and return TRUE in the case of success. That is an
2687 analog of retry_global_alloc for IRA. */
2689 allocno_reload_assign (ira_allocno_t a
, HARD_REG_SET forbidden_regs
)
2692 enum reg_class cover_class
;
2693 int regno
= ALLOCNO_REGNO (a
);
2695 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
), forbidden_regs
);
2696 if (! flag_caller_saves
&& ALLOCNO_CALLS_CROSSED_NUM (a
) != 0)
2697 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
), call_used_reg_set
);
2698 ALLOCNO_ASSIGNED_P (a
) = false;
2699 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
2700 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
2701 cover_class
= ALLOCNO_COVER_CLASS (a
);
2702 update_curr_costs (a
);
2703 assign_hard_reg (a
, true);
2704 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2705 reg_renumber
[regno
] = hard_regno
;
2707 ALLOCNO_HARD_REGNO (a
) = -1;
2710 ira_assert (ira_class_hard_reg_index
[cover_class
][hard_regno
] >= 0);
2711 ira_overall_cost
-= (ALLOCNO_MEMORY_COST (a
)
2712 - (ALLOCNO_HARD_REG_COSTS (a
) == NULL
2713 ? ALLOCNO_COVER_CLASS_COST (a
)
2714 : ALLOCNO_HARD_REG_COSTS (a
)
2715 [ira_class_hard_reg_index
2716 [cover_class
][hard_regno
]]));
2717 if (ALLOCNO_CALLS_CROSSED_NUM (a
) != 0
2718 && ! ira_hard_reg_not_in_set_p (hard_regno
, ALLOCNO_MODE (a
),
2721 ira_assert (flag_caller_saves
);
2722 caller_save_needed
= 1;
2726 /* If we found a hard register, modify the RTL for the pseudo
2727 register to show the hard register, and mark the pseudo register
2729 if (reg_renumber
[regno
] >= 0)
2731 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2732 fprintf (ira_dump_file
, ": reassign to %d\n", reg_renumber
[regno
]);
2733 SET_REGNO (regno_reg_rtx
[regno
], reg_renumber
[regno
]);
2734 mark_home_live (regno
);
2736 else if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2737 fprintf (ira_dump_file
, "\n");
2739 return reg_renumber
[regno
] >= 0;
2742 /* Sort pseudos according their usage frequencies (putting most
2743 frequently ones first). */
2745 pseudo_reg_compare (const void *v1p
, const void *v2p
)
2747 int regno1
= *(const int *) v1p
;
2748 int regno2
= *(const int *) v2p
;
2751 if ((diff
= REG_FREQ (regno2
) - REG_FREQ (regno1
)) != 0)
2753 return regno1
- regno2
;
2756 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
2757 NUM of them) or spilled pseudos conflicting with pseudos in
2758 SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
2759 allocation has been changed. The function doesn't use
2760 BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
2761 PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
2762 is called by the reload pass at the end of each reload
2765 ira_reassign_pseudos (int *spilled_pseudo_regs
, int num
,
2766 HARD_REG_SET bad_spill_regs
,
2767 HARD_REG_SET
*pseudo_forbidden_regs
,
2768 HARD_REG_SET
*pseudo_previous_regs
, bitmap spilled
)
2772 ira_allocno_t a
, conflict_a
;
2773 HARD_REG_SET forbidden_regs
;
2774 ira_allocno_conflict_iterator aci
;
2777 qsort (spilled_pseudo_regs
, num
, sizeof (int), pseudo_reg_compare
);
2779 /* Try to assign hard registers to pseudos from
2780 SPILLED_PSEUDO_REGS. */
2781 for (m
= i
= 0; i
< num
; i
++)
2783 regno
= spilled_pseudo_regs
[i
];
2784 COPY_HARD_REG_SET (forbidden_regs
, bad_spill_regs
);
2785 IOR_HARD_REG_SET (forbidden_regs
, pseudo_forbidden_regs
[regno
]);
2786 IOR_HARD_REG_SET (forbidden_regs
, pseudo_previous_regs
[regno
]);
2787 gcc_assert (reg_renumber
[regno
] < 0);
2788 a
= ira_regno_allocno_map
[regno
];
2789 ira_mark_allocation_change (regno
);
2790 ira_assert (reg_renumber
[regno
] < 0);
2791 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2792 fprintf (ira_dump_file
,
2793 " Spill %d(a%d), cost=%d", regno
, ALLOCNO_NUM (a
),
2794 ALLOCNO_MEMORY_COST (a
)
2795 - ALLOCNO_COVER_CLASS_COST (a
));
2796 allocno_reload_assign (a
, forbidden_regs
);
2797 if (reg_renumber
[regno
] >= 0)
2799 CLEAR_REGNO_REG_SET (spilled
, regno
);
2803 spilled_pseudo_regs
[m
++] = regno
;
2807 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2809 fprintf (ira_dump_file
, " Spilled regs");
2810 for (i
= 0; i
< m
; i
++)
2811 fprintf (ira_dump_file
, " %d", spilled_pseudo_regs
[i
]);
2812 fprintf (ira_dump_file
, "\n");
2814 /* Try to assign hard registers to pseudos conflicting with ones
2815 from SPILLED_PSEUDO_REGS. */
2816 for (i
= n
= 0; i
< m
; i
++)
2818 regno
= spilled_pseudo_regs
[i
];
2819 a
= ira_regno_allocno_map
[regno
];
2820 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_a
, aci
)
2821 if (ALLOCNO_HARD_REGNO (conflict_a
) < 0
2822 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a
)
2823 && ! bitmap_bit_p (consideration_allocno_bitmap
,
2824 ALLOCNO_NUM (conflict_a
)))
2826 sorted_allocnos
[n
++] = conflict_a
;
2827 bitmap_set_bit (consideration_allocno_bitmap
,
2828 ALLOCNO_NUM (conflict_a
));
2833 setup_allocno_priorities (sorted_allocnos
, n
);
2834 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
),
2835 allocno_priority_compare_func
);
2836 for (i
= 0; i
< n
; i
++)
2838 a
= sorted_allocnos
[i
];
2839 regno
= ALLOCNO_REGNO (a
);
2840 COPY_HARD_REG_SET (forbidden_regs
, bad_spill_regs
);
2841 IOR_HARD_REG_SET (forbidden_regs
, pseudo_forbidden_regs
[regno
]);
2842 IOR_HARD_REG_SET (forbidden_regs
, pseudo_previous_regs
[regno
]);
2843 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2844 fprintf (ira_dump_file
,
2845 " Try assign %d(a%d), cost=%d",
2846 regno
, ALLOCNO_NUM (a
),
2847 ALLOCNO_MEMORY_COST (a
)
2848 - ALLOCNO_COVER_CLASS_COST (a
));
2849 if (allocno_reload_assign (a
, forbidden_regs
))
2852 bitmap_clear_bit (spilled
, regno
);
2859 /* The function is called by reload and returns already allocated
2860 stack slot (if any) for REGNO with given INHERENT_SIZE and
2861 TOTAL_SIZE. In the case of failure to find a slot which can be
2862 used for REGNO, the function returns NULL. */
2864 ira_reuse_stack_slot (int regno
, unsigned int inherent_size
,
2865 unsigned int total_size
)
2868 int slot_num
, best_slot_num
;
2869 int cost
, best_cost
;
2870 ira_copy_t cp
, next_cp
;
2871 ira_allocno_t another_allocno
, allocno
= ira_regno_allocno_map
[regno
];
2874 struct ira_spilled_reg_stack_slot
*slot
= NULL
;
2876 ira_assert (flag_ira
&& inherent_size
== PSEUDO_REGNO_BYTES (regno
)
2877 && inherent_size
<= total_size
2878 && ALLOCNO_HARD_REGNO (allocno
) < 0);
2879 if (! flag_ira_share_spill_slots
)
2881 slot_num
= -ALLOCNO_HARD_REGNO (allocno
) - 2;
2884 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
2889 best_cost
= best_slot_num
= -1;
2891 /* It means that the pseudo was spilled in the reload pass, try
2894 slot_num
< ira_spilled_reg_stack_slots_num
;
2897 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
2898 if (slot
->mem
== NULL_RTX
)
2900 if (slot
->width
< total_size
2901 || GET_MODE_SIZE (GET_MODE (slot
->mem
)) < inherent_size
)
2904 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
2905 FIRST_PSEUDO_REGISTER
, i
, bi
)
2907 another_allocno
= ira_regno_allocno_map
[i
];
2908 if (allocnos_have_intersected_live_ranges_p (allocno
,
2912 for (cost
= 0, cp
= ALLOCNO_COPIES (allocno
);
2916 if (cp
->first
== allocno
)
2918 next_cp
= cp
->next_first_allocno_copy
;
2919 another_allocno
= cp
->second
;
2921 else if (cp
->second
== allocno
)
2923 next_cp
= cp
->next_second_allocno_copy
;
2924 another_allocno
= cp
->first
;
2928 if (cp
->insn
== NULL_RTX
)
2930 if (bitmap_bit_p (&slot
->spilled_regs
,
2931 ALLOCNO_REGNO (another_allocno
)))
2934 if (cost
> best_cost
)
2937 best_slot_num
= slot_num
;
2944 slot_num
= best_slot_num
;
2945 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
2946 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
2948 ALLOCNO_HARD_REGNO (allocno
) = -slot_num
- 2;
2953 ira_assert (slot
->width
>= total_size
);
2954 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
2955 FIRST_PSEUDO_REGISTER
, i
, bi
)
2957 ira_assert (! pseudos_have_intersected_live_ranges_p (regno
, i
));
2959 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
2960 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
2962 fprintf (ira_dump_file
, " Assigning %d(freq=%d) slot %d of",
2963 regno
, REG_FREQ (regno
), slot_num
);
2964 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
2965 FIRST_PSEUDO_REGISTER
, i
, bi
)
2967 if ((unsigned) regno
!= i
)
2968 fprintf (ira_dump_file
, " %d", i
);
2970 fprintf (ira_dump_file
, "\n");
2976 /* This is called by reload every time a new stack slot X with
2977 TOTAL_SIZE was allocated for REGNO. We store this info for
2978 subsequent ira_reuse_stack_slot calls. */
2980 ira_mark_new_stack_slot (rtx x
, int regno
, unsigned int total_size
)
2982 struct ira_spilled_reg_stack_slot
*slot
;
2984 ira_allocno_t allocno
;
2986 ira_assert (flag_ira
&& PSEUDO_REGNO_BYTES (regno
) <= total_size
);
2987 allocno
= ira_regno_allocno_map
[regno
];
2988 slot_num
= -ALLOCNO_HARD_REGNO (allocno
) - 2;
2991 slot_num
= ira_spilled_reg_stack_slots_num
++;
2992 ALLOCNO_HARD_REGNO (allocno
) = -slot_num
- 2;
2994 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
2995 INIT_REG_SET (&slot
->spilled_regs
);
2996 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
2998 slot
->width
= total_size
;
2999 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
3000 fprintf (ira_dump_file
, " Assigning %d(freq=%d) a new slot %d\n",
3001 regno
, REG_FREQ (regno
), slot_num
);
3005 /* Return spill cost for pseudo-registers whose numbers are in array
3006 REGNOS (with a negative number as an end marker) for reload with
3007 given IN and OUT for INSN. Return also number points (through
3008 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
3009 the register pressure is high, number of references of the
3010 pseudo-registers (through NREFS), number of callee-clobbered
3011 hard-registers occupied by the pseudo-registers (through
3012 CALL_USED_COUNT), and the first hard regno occupied by the
3013 pseudo-registers (through FIRST_HARD_REGNO). */
3015 calculate_spill_cost (int *regnos
, rtx in
, rtx out
, rtx insn
,
3016 int *excess_pressure_live_length
,
3017 int *nrefs
, int *call_used_count
, int *first_hard_regno
)
3019 int i
, cost
, regno
, hard_regno
, j
, count
, saved_cost
, nregs
;
3025 for (length
= count
= cost
= i
= 0;; i
++)
3030 *nrefs
+= REG_N_REFS (regno
);
3031 hard_regno
= reg_renumber
[regno
];
3032 ira_assert (hard_regno
>= 0);
3033 a
= ira_regno_allocno_map
[regno
];
3034 length
+= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
3035 cost
+= ALLOCNO_MEMORY_COST (a
) - ALLOCNO_COVER_CLASS_COST (a
);
3036 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (a
)];
3037 for (j
= 0; j
< nregs
; j
++)
3038 if (! TEST_HARD_REG_BIT (call_used_reg_set
, hard_regno
+ j
))
3042 in_p
= in
&& REG_P (in
) && (int) REGNO (in
) == hard_regno
;
3043 out_p
= out
&& REG_P (out
) && (int) REGNO (out
) == hard_regno
;
3045 && find_regno_note (insn
, REG_DEAD
, hard_regno
) != NULL_RTX
)
3049 saved_cost
+= ira_memory_move_cost
3050 [ALLOCNO_MODE (a
)][ALLOCNO_COVER_CLASS (a
)][1];
3053 += ira_memory_move_cost
3054 [ALLOCNO_MODE (a
)][ALLOCNO_COVER_CLASS (a
)][0];
3055 cost
-= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn
)) * saved_cost
;
3058 *excess_pressure_live_length
= length
;
3059 *call_used_count
= count
;
3063 hard_regno
= reg_renumber
[regnos
[0]];
3065 *first_hard_regno
= hard_regno
;
3069 /* Return TRUE if spilling pseudo-registers whose numbers are in array
3070 REGNOS is better than spilling pseudo-registers with numbers in
3071 OTHER_REGNOS for reload with given IN and OUT for INSN. The
3072 function used by the reload pass to make better register spilling
3075 ira_better_spill_reload_regno_p (int *regnos
, int *other_regnos
,
3076 rtx in
, rtx out
, rtx insn
)
3078 int cost
, other_cost
;
3079 int length
, other_length
;
3080 int nrefs
, other_nrefs
;
3081 int call_used_count
, other_call_used_count
;
3082 int hard_regno
, other_hard_regno
;
3084 cost
= calculate_spill_cost (regnos
, in
, out
, insn
,
3085 &length
, &nrefs
, &call_used_count
, &hard_regno
);
3086 other_cost
= calculate_spill_cost (other_regnos
, in
, out
, insn
,
3087 &other_length
, &other_nrefs
,
3088 &other_call_used_count
,
3090 if (nrefs
== 0 && other_nrefs
!= 0)
3092 if (nrefs
!= 0 && other_nrefs
== 0)
3094 if (cost
!= other_cost
)
3095 return cost
< other_cost
;
3096 if (length
!= other_length
)
3097 return length
> other_length
;
3098 #ifdef REG_ALLOC_ORDER
3099 if (hard_regno
>= 0 && other_hard_regno
>= 0)
3100 return (inv_reg_alloc_order
[hard_regno
]
3101 < inv_reg_alloc_order
[other_hard_regno
]);
3103 if (call_used_count
!= other_call_used_count
)
3104 return call_used_count
> other_call_used_count
;
3111 /* Allocate and initialize data necessary for assign_hard_reg. */
3113 ira_initiate_assign (void)
3116 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
3117 * ira_allocnos_num
);
3118 consideration_allocno_bitmap
= ira_allocate_bitmap ();
3119 initiate_cost_update ();
3120 allocno_priorities
= (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
3123 /* Deallocate data used by assign_hard_reg. */
3125 ira_finish_assign (void)
3127 ira_free (sorted_allocnos
);
3128 ira_free_bitmap (consideration_allocno_bitmap
);
3129 finish_cost_update ();
3130 ira_free (allocno_priorities
);
3135 /* Entry function doing color-based register allocation. */
3139 allocno_stack_vec
= VEC_alloc (ira_allocno_t
, heap
, ira_allocnos_num
);
3140 removed_splay_allocno_vec
3141 = VEC_alloc (ira_allocno_t
, heap
, ira_allocnos_num
);
3142 memset (allocated_hardreg_p
, 0, sizeof (allocated_hardreg_p
));
3143 ira_initiate_assign ();
3145 ira_finish_assign ();
3146 VEC_free (ira_allocno_t
, heap
, removed_splay_allocno_vec
);
3147 VEC_free (ira_allocno_t
, heap
, allocno_stack_vec
);
3148 move_spill_restore ();
3153 /* This page contains a simple register allocator without usage of
3154 allocno conflicts. This is used for fast allocation for -O0. */
3156 /* Do register allocation by not using allocno conflicts. It uses
3157 only allocno live ranges. The algorithm is close to Chow's
3158 priority coloring. */
3160 fast_allocation (void)
3162 int i
, j
, k
, num
, class_size
, hard_regno
;
3164 bool no_stack_reg_p
;
3166 enum reg_class cover_class
;
3167 enum machine_mode mode
;
3169 ira_allocno_iterator ai
;
3170 allocno_live_range_t r
;
3171 HARD_REG_SET conflict_hard_regs
, *used_hard_regs
;
3173 sorted_allocnos
= (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
3174 * ira_allocnos_num
);
3176 FOR_EACH_ALLOCNO (a
, ai
)
3177 sorted_allocnos
[num
++] = a
;
3178 allocno_priorities
= (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
3179 setup_allocno_priorities (sorted_allocnos
, num
);
3180 used_hard_regs
= (HARD_REG_SET
*) ira_allocate (sizeof (HARD_REG_SET
)
3182 for (i
= 0; i
< ira_max_point
; i
++)
3183 CLEAR_HARD_REG_SET (used_hard_regs
[i
]);
3184 qsort (sorted_allocnos
, ira_allocnos_num
, sizeof (ira_allocno_t
),
3185 allocno_priority_compare_func
);
3186 for (i
= 0; i
< num
; i
++)
3188 a
= sorted_allocnos
[i
];
3189 COPY_HARD_REG_SET (conflict_hard_regs
, ALLOCNO_CONFLICT_HARD_REGS (a
));
3190 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
3191 for (j
= r
->start
; j
<= r
->finish
; j
++)
3192 IOR_HARD_REG_SET (conflict_hard_regs
, used_hard_regs
[j
]);
3193 cover_class
= ALLOCNO_COVER_CLASS (a
);
3194 ALLOCNO_ASSIGNED_P (a
) = true;
3195 ALLOCNO_HARD_REGNO (a
) = -1;
3196 if (hard_reg_set_subset_p (reg_class_contents
[cover_class
],
3197 conflict_hard_regs
))
3199 mode
= ALLOCNO_MODE (a
);
3201 no_stack_reg_p
= ALLOCNO_NO_STACK_REG_P (a
);
3203 class_size
= ira_class_hard_regs_num
[cover_class
];
3204 for (j
= 0; j
< class_size
; j
++)
3206 hard_regno
= ira_class_hard_regs
[cover_class
][j
];
3208 if (no_stack_reg_p
&& FIRST_STACK_REG
<= hard_regno
3209 && hard_regno
<= LAST_STACK_REG
)
3212 if (!ira_hard_reg_not_in_set_p (hard_regno
, mode
, conflict_hard_regs
)
3213 || (TEST_HARD_REG_BIT
3214 (prohibited_class_mode_regs
[cover_class
][mode
], hard_regno
)))
3216 ALLOCNO_HARD_REGNO (a
) = hard_regno
;
3217 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
3218 for (k
= r
->start
; k
<= r
->finish
; k
++)
3219 IOR_HARD_REG_SET (used_hard_regs
[k
],
3220 ira_reg_mode_hard_regset
[hard_regno
][mode
]);
3224 ira_free (sorted_allocnos
);
3225 ira_free (used_hard_regs
);
3226 ira_free (allocno_priorities
);
3227 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
3228 ira_print_disposition (ira_dump_file
);
3233 /* Entry function doing coloring. */
3238 ira_allocno_iterator ai
;
3240 /* Setup updated costs. */
3241 FOR_EACH_ALLOCNO (a
, ai
)
3243 ALLOCNO_UPDATED_MEMORY_COST (a
) = ALLOCNO_MEMORY_COST (a
);
3244 ALLOCNO_UPDATED_COVER_CLASS_COST (a
) = ALLOCNO_COVER_CLASS_COST (a
);