1 /* IRA allocation based on graph coloring.
2 Copyright (C) 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
33 #include "hard-reg-set.h"
34 #include "basic-block.h"
40 #include "splay-tree.h"
43 /* This file contains code for regional graph coloring, spill/restore
44 code placement optimization, and code helping the reload pass to do
47 /* Bitmap of allocnos which should be colored. */
48 static bitmap coloring_allocno_bitmap
;
50 /* Bitmap of allocnos which should be taken into account during
51 coloring. In general case it contains allocnos from
52 coloring_allocno_bitmap plus other already colored conflicting
54 static bitmap consideration_allocno_bitmap
;
56 /* TRUE if we coalesced some allocnos. In other words, if we got
57 loops formed by members first_coalesced_allocno and
58 next_coalesced_allocno containing more one allocno. */
59 static bool allocno_coalesced_p
;
61 /* Bitmap used to prevent a repeated allocno processing because of
63 static bitmap processed_coalesced_allocno_bitmap
;
65 /* All allocnos sorted according their priorities. */
66 static ira_allocno_t
*sorted_allocnos
;
68 /* Vec representing the stack of allocnos used during coloring. */
69 static VEC(ira_allocno_t
,heap
) *allocno_stack_vec
;
71 /* Array used to choose an allocno for spilling. */
72 static ira_allocno_t
*allocnos_for_spilling
;
74 /* Pool for splay tree nodes. */
75 static alloc_pool splay_tree_node_pool
;
77 /* When an allocno is removed from the splay tree, it is put in the
78 following vector for subsequent inserting it into the splay tree
79 after putting all colorable allocnos onto the stack. The allocno
80 could be removed from and inserted to the splay tree every time
81 when its spilling priority is changed but such solution would be
82 more costly although simpler. */
83 static VEC(ira_allocno_t
,heap
) *removed_splay_allocno_vec
;
87 /* This page contains functions used to find conflicts using allocno
90 /* Return TRUE if live ranges of allocnos A1 and A2 intersect. It is
91 used to find a conflict for new allocnos or allocnos with the
92 different cover classes. */
94 allocnos_have_intersected_live_ranges_p (ira_allocno_t a1
, ira_allocno_t a2
)
98 if (ALLOCNO_REG (a1
) != NULL
&& ALLOCNO_REG (a2
) != NULL
99 && (ORIGINAL_REGNO (ALLOCNO_REG (a1
))
100 == ORIGINAL_REGNO (ALLOCNO_REG (a2
))))
102 return ira_allocno_live_ranges_intersect_p (ALLOCNO_LIVE_RANGES (a1
),
103 ALLOCNO_LIVE_RANGES (a2
));
106 #ifdef ENABLE_IRA_CHECKING
108 /* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
109 intersect. This should be used when there is only one region.
110 Currently this is used during reload. */
112 pseudos_have_intersected_live_ranges_p (int regno1
, int regno2
)
114 ira_allocno_t a1
, a2
;
116 ira_assert (regno1
>= FIRST_PSEUDO_REGISTER
117 && regno2
>= FIRST_PSEUDO_REGISTER
);
118 /* Reg info caclulated by dataflow infrastructure can be different
119 from one calculated by regclass. */
120 if ((a1
= ira_loop_tree_root
->regno_allocno_map
[regno1
]) == NULL
121 || (a2
= ira_loop_tree_root
->regno_allocno_map
[regno2
]) == NULL
)
123 return allocnos_have_intersected_live_ranges_p (a1
, a2
);
130 /* This page contains functions used to choose hard registers for
133 /* Array whose element value is TRUE if the corresponding hard
134 register was already allocated for an allocno. */
135 static bool allocated_hardreg_p
[FIRST_PSEUDO_REGISTER
];
137 /* Describes one element in a queue of allocnos whose costs need to be
138 updated. Each allocno in the queue is known to have a cover class. */
139 struct update_cost_queue_elem
141 /* This element is in the queue iff CHECK == update_cost_check. */
144 /* COST_HOP_DIVISOR**N, where N is the length of the shortest path
145 connecting this allocno to the one being allocated. */
148 /* The next allocno in the queue, or null if this is the last element. */
152 /* The first element in a queue of allocnos whose copy costs need to be
153 updated. Null if the queue is empty. */
154 static ira_allocno_t update_cost_queue
;
156 /* The last element in the queue described by update_cost_queue.
157 Not valid if update_cost_queue is null. */
158 static struct update_cost_queue_elem
*update_cost_queue_tail
;
160 /* A pool of elements in the queue described by update_cost_queue.
161 Elements are indexed by ALLOCNO_NUM. */
162 static struct update_cost_queue_elem
*update_cost_queue_elems
;
164 /* The current value of update_copy_cost call count. */
165 static int update_cost_check
;
167 /* Allocate and initialize data necessary for function
168 update_copy_costs. */
170 initiate_cost_update (void)
174 size
= ira_allocnos_num
* sizeof (struct update_cost_queue_elem
);
175 update_cost_queue_elems
176 = (struct update_cost_queue_elem
*) ira_allocate (size
);
177 memset (update_cost_queue_elems
, 0, size
);
178 update_cost_check
= 0;
181 /* Deallocate data used by function update_copy_costs. */
183 finish_cost_update (void)
185 ira_free (update_cost_queue_elems
);
188 /* When we traverse allocnos to update hard register costs, the cost
189 divisor will be multiplied by the following macro value for each
190 hop from given allocno to directly connected allocnos. */
191 #define COST_HOP_DIVISOR 4
193 /* Start a new cost-updating pass. */
195 start_update_cost (void)
198 update_cost_queue
= NULL
;
201 /* Add (ALLOCNO, DIVISOR) to the end of update_cost_queue,
202 unless ALLOCNO is already in the queue, or has no cover class. */
204 queue_update_cost (ira_allocno_t allocno
, int divisor
)
206 struct update_cost_queue_elem
*elem
;
208 elem
= &update_cost_queue_elems
[ALLOCNO_NUM (allocno
)];
209 if (elem
->check
!= update_cost_check
210 && ALLOCNO_COVER_CLASS (allocno
) != NO_REGS
)
212 elem
->check
= update_cost_check
;
213 elem
->divisor
= divisor
;
215 if (update_cost_queue
== NULL
)
216 update_cost_queue
= allocno
;
218 update_cost_queue_tail
->next
= allocno
;
219 update_cost_queue_tail
= elem
;
223 /* Try to remove the first element from update_cost_queue. Return false
224 if the queue was empty, otherwise make (*ALLOCNO, *DIVISOR) describe
225 the removed element. */
227 get_next_update_cost (ira_allocno_t
*allocno
, int *divisor
)
229 struct update_cost_queue_elem
*elem
;
231 if (update_cost_queue
== NULL
)
234 *allocno
= update_cost_queue
;
235 elem
= &update_cost_queue_elems
[ALLOCNO_NUM (*allocno
)];
236 *divisor
= elem
->divisor
;
237 update_cost_queue
= elem
->next
;
241 /* Update the cost of allocnos to increase chances to remove some
242 copies as the result of subsequent assignment. */
244 update_copy_costs (ira_allocno_t allocno
, bool decr_p
)
246 int i
, cost
, update_cost
, hard_regno
, divisor
;
247 enum machine_mode mode
;
248 enum reg_class rclass
, cover_class
;
249 ira_allocno_t another_allocno
;
250 ira_copy_t cp
, next_cp
;
252 hard_regno
= ALLOCNO_HARD_REGNO (allocno
);
253 ira_assert (hard_regno
>= 0);
255 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
256 if (cover_class
== NO_REGS
)
258 i
= ira_class_hard_reg_index
[cover_class
][hard_regno
];
260 rclass
= REGNO_REG_CLASS (hard_regno
);
262 start_update_cost ();
266 mode
= ALLOCNO_MODE (allocno
);
267 for (cp
= ALLOCNO_COPIES (allocno
); cp
!= NULL
; cp
= next_cp
)
269 if (cp
->first
== allocno
)
271 next_cp
= cp
->next_first_allocno_copy
;
272 another_allocno
= cp
->second
;
274 else if (cp
->second
== allocno
)
276 next_cp
= cp
->next_second_allocno_copy
;
277 another_allocno
= cp
->first
;
282 cover_class
= ALLOCNO_COVER_CLASS (another_allocno
);
283 if (! ira_reg_classes_intersect_p
[rclass
][cover_class
]
284 || ALLOCNO_ASSIGNED_P (another_allocno
))
287 cost
= (cp
->second
== allocno
288 ? ira_get_register_move_cost (mode
, rclass
, cover_class
)
289 : ira_get_register_move_cost (mode
, cover_class
, rclass
));
293 update_cost
= cp
->freq
* cost
/ divisor
;
294 if (update_cost
== 0)
297 ira_allocate_and_set_or_copy_costs
298 (&ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno
), cover_class
,
299 ALLOCNO_UPDATED_COVER_CLASS_COST (another_allocno
),
300 ALLOCNO_HARD_REG_COSTS (another_allocno
));
301 ira_allocate_and_set_or_copy_costs
302 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno
),
304 ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno
));
305 i
= ira_class_hard_reg_index
[cover_class
][hard_regno
];
307 ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno
)[i
] += update_cost
;
308 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno
)[i
]
311 queue_update_cost (another_allocno
, divisor
* COST_HOP_DIVISOR
);
314 while (get_next_update_cost (&allocno
, &divisor
));
317 /* This function updates COSTS (decrease if DECR_P) for hard_registers
318 of COVER_CLASS by conflict costs of the unassigned allocnos
319 connected by copies with allocnos in update_cost_queue. This
320 update increases chances to remove some copies. */
322 update_conflict_hard_regno_costs (int *costs
, enum reg_class cover_class
,
325 int i
, cost
, class_size
, freq
, mult
, div
, divisor
;
326 int index
, hard_regno
;
329 enum reg_class another_cover_class
;
330 ira_allocno_t allocno
, another_allocno
;
331 ira_copy_t cp
, next_cp
;
333 while (get_next_update_cost (&allocno
, &divisor
))
334 for (cp
= ALLOCNO_COPIES (allocno
); cp
!= NULL
; cp
= next_cp
)
336 if (cp
->first
== allocno
)
338 next_cp
= cp
->next_first_allocno_copy
;
339 another_allocno
= cp
->second
;
341 else if (cp
->second
== allocno
)
343 next_cp
= cp
->next_second_allocno_copy
;
344 another_allocno
= cp
->first
;
348 another_cover_class
= ALLOCNO_COVER_CLASS (another_allocno
);
349 if (! ira_reg_classes_intersect_p
[cover_class
][another_cover_class
]
350 || ALLOCNO_ASSIGNED_P (another_allocno
)
351 || ALLOCNO_MAY_BE_SPILLED_P (ALLOCNO_FIRST_COALESCED_ALLOCNO
354 class_size
= ira_class_hard_regs_num
[another_cover_class
];
355 ira_allocate_and_copy_costs
356 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno
),
358 ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno
));
360 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno
);
361 if (conflict_costs
== NULL
)
366 freq
= ALLOCNO_FREQ (another_allocno
);
369 div
= freq
* divisor
;
371 for (i
= class_size
- 1; i
>= 0; i
--)
373 hard_regno
= ira_class_hard_regs
[another_cover_class
][i
];
374 ira_assert (hard_regno
>= 0);
375 index
= ira_class_hard_reg_index
[cover_class
][hard_regno
];
378 cost
= conflict_costs
[i
] * mult
/ div
;
384 costs
[index
] += cost
;
387 /* Probably 5 hops will be enough. */
389 && divisor
<= (COST_HOP_DIVISOR
393 queue_update_cost (another_allocno
, divisor
* COST_HOP_DIVISOR
);
397 /* Sort allocnos according to the profit of usage of a hard register
398 instead of memory for them. */
400 allocno_cost_compare_func (const void *v1p
, const void *v2p
)
402 ira_allocno_t p1
= *(const ira_allocno_t
*) v1p
;
403 ira_allocno_t p2
= *(const ira_allocno_t
*) v2p
;
406 c1
= ALLOCNO_UPDATED_MEMORY_COST (p1
) - ALLOCNO_UPDATED_COVER_CLASS_COST (p1
);
407 c2
= ALLOCNO_UPDATED_MEMORY_COST (p2
) - ALLOCNO_UPDATED_COVER_CLASS_COST (p2
);
411 /* If regs are equally good, sort by allocno numbers, so that the
412 results of qsort leave nothing to chance. */
413 return ALLOCNO_NUM (p1
) - ALLOCNO_NUM (p2
);
416 /* Print all allocnos coalesced with ALLOCNO. */
418 print_coalesced_allocno (ira_allocno_t allocno
)
422 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
423 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
425 ira_print_expanded_allocno (a
);
428 fprintf (ira_dump_file
, "+");
432 /* Choose a hard register for ALLOCNO (or for all coalesced allocnos
433 represented by ALLOCNO). If RETRY_P is TRUE, it means that the
434 function called from function `ira_reassign_conflict_allocnos' and
435 `allocno_reload_assign'. This function implements the optimistic
436 coalescing too: if we failed to assign a hard register to set of
437 the coalesced allocnos, we put them onto the coloring stack for
438 subsequent separate assigning. */
440 assign_hard_reg (ira_allocno_t allocno
, bool retry_p
)
442 HARD_REG_SET conflicting_regs
;
443 int i
, j
, k
, hard_regno
, best_hard_regno
, class_size
;
444 int cost
, mem_cost
, min_cost
, full_cost
, min_full_cost
;
447 enum reg_class cover_class
, conflict_cover_class
;
448 enum machine_mode mode
;
449 ira_allocno_t a
, conflict_allocno
;
450 ira_allocno_conflict_iterator aci
;
451 static int costs
[FIRST_PSEUDO_REGISTER
], full_costs
[FIRST_PSEUDO_REGISTER
];
452 #ifndef HONOR_REG_ALLOC_ORDER
453 enum reg_class rclass
;
460 ira_assert (! ALLOCNO_ASSIGNED_P (allocno
));
461 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
462 class_size
= ira_class_hard_regs_num
[cover_class
];
463 mode
= ALLOCNO_MODE (allocno
);
464 CLEAR_HARD_REG_SET (conflicting_regs
);
465 best_hard_regno
= -1;
466 memset (full_costs
, 0, sizeof (int) * class_size
);
468 if (allocno_coalesced_p
)
469 bitmap_clear (processed_coalesced_allocno_bitmap
);
470 memset (costs
, 0, sizeof (int) * class_size
);
471 memset (full_costs
, 0, sizeof (int) * class_size
);
473 no_stack_reg_p
= false;
475 start_update_cost ();
476 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
477 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
479 mem_cost
+= ALLOCNO_UPDATED_MEMORY_COST (a
);
480 IOR_HARD_REG_SET (conflicting_regs
,
481 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
482 ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a
),
483 cover_class
, ALLOCNO_HARD_REG_COSTS (a
));
484 a_costs
= ALLOCNO_UPDATED_HARD_REG_COSTS (a
);
486 no_stack_reg_p
= no_stack_reg_p
|| ALLOCNO_TOTAL_NO_STACK_REG_P (a
);
488 cost
= ALLOCNO_UPDATED_COVER_CLASS_COST (a
);
489 for (i
= 0; i
< class_size
; i
++)
492 costs
[i
] += a_costs
[i
];
493 full_costs
[i
] += a_costs
[i
];
498 full_costs
[i
] += cost
;
500 /* Take preferences of conflicting allocnos into account. */
501 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_allocno
, aci
)
502 /* Reload can give another class so we need to check all
504 if (retry_p
|| bitmap_bit_p (consideration_allocno_bitmap
,
505 ALLOCNO_NUM (conflict_allocno
)))
507 conflict_cover_class
= ALLOCNO_COVER_CLASS (conflict_allocno
);
508 ira_assert (ira_reg_classes_intersect_p
509 [cover_class
][conflict_cover_class
]);
510 if (allocno_coalesced_p
)
512 if (bitmap_bit_p (processed_coalesced_allocno_bitmap
,
513 ALLOCNO_NUM (conflict_allocno
)))
515 bitmap_set_bit (processed_coalesced_allocno_bitmap
,
516 ALLOCNO_NUM (conflict_allocno
));
518 if (ALLOCNO_ASSIGNED_P (conflict_allocno
))
520 if ((hard_regno
= ALLOCNO_HARD_REGNO (conflict_allocno
)) >= 0
521 && ira_class_hard_reg_index
[cover_class
][hard_regno
] >= 0)
525 ira_reg_mode_hard_regset
526 [hard_regno
][ALLOCNO_MODE (conflict_allocno
)]);
527 if (hard_reg_set_subset_p (reg_class_contents
[cover_class
],
532 else if (! ALLOCNO_MAY_BE_SPILLED_P (ALLOCNO_FIRST_COALESCED_ALLOCNO
535 ira_allocate_and_copy_costs
536 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno
),
537 conflict_cover_class
,
538 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_allocno
));
540 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno
);
541 if (conflict_costs
!= NULL
)
542 for (j
= class_size
- 1; j
>= 0; j
--)
544 hard_regno
= ira_class_hard_regs
[cover_class
][j
];
545 ira_assert (hard_regno
>= 0);
546 k
= (ira_class_hard_reg_index
547 [conflict_cover_class
][hard_regno
]);
550 full_costs
[j
] -= conflict_costs
[k
];
552 queue_update_cost (conflict_allocno
, COST_HOP_DIVISOR
);
558 /* Take into account preferences of allocnos connected by copies to
559 the conflict allocnos. */
560 update_conflict_hard_regno_costs (full_costs
, cover_class
, true);
562 /* Take preferences of allocnos connected by copies into
564 start_update_cost ();
565 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
566 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
568 queue_update_cost (a
, COST_HOP_DIVISOR
);
572 update_conflict_hard_regno_costs (full_costs
, cover_class
, false);
573 min_cost
= min_full_cost
= INT_MAX
;
574 /* We don't care about giving callee saved registers to allocnos no
575 living through calls because call clobbered registers are
576 allocated first (it is usual practice to put them first in
578 for (i
= 0; i
< class_size
; i
++)
580 hard_regno
= ira_class_hard_regs
[cover_class
][i
];
583 && FIRST_STACK_REG
<= hard_regno
&& hard_regno
<= LAST_STACK_REG
)
586 if (! ira_hard_reg_not_in_set_p (hard_regno
, mode
, conflicting_regs
)
587 || TEST_HARD_REG_BIT (prohibited_class_mode_regs
[cover_class
][mode
],
591 full_cost
= full_costs
[i
];
592 #ifndef HONOR_REG_ALLOC_ORDER
593 if (! allocated_hardreg_p
[hard_regno
]
594 && ira_hard_reg_not_in_set_p (hard_regno
, mode
, call_used_reg_set
))
595 /* We need to save/restore the hard register in
596 epilogue/prologue. Therefore we increase the cost. */
598 /* ??? If only part is call clobbered. */
599 rclass
= REGNO_REG_CLASS (hard_regno
);
600 add_cost
= (ira_memory_move_cost
[mode
][rclass
][0]
601 + ira_memory_move_cost
[mode
][rclass
][1] - 1);
603 full_cost
+= add_cost
;
608 if (min_full_cost
> full_cost
)
610 min_full_cost
= full_cost
;
611 best_hard_regno
= hard_regno
;
612 ira_assert (hard_regno
>= 0);
615 if (min_full_cost
> mem_cost
)
617 if (! retry_p
&& internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
618 fprintf (ira_dump_file
, "(memory is more profitable %d vs %d) ",
619 mem_cost
, min_full_cost
);
620 best_hard_regno
= -1;
623 if (flag_ira_algorithm
!= IRA_ALGORITHM_PRIORITY
624 && best_hard_regno
< 0
625 && ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
) != allocno
)
627 for (j
= 0, a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
628 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
630 ira_assert (! ALLOCNO_IN_GRAPH_P (a
));
631 sorted_allocnos
[j
++] = a
;
635 qsort (sorted_allocnos
, j
, sizeof (ira_allocno_t
),
636 allocno_cost_compare_func
);
637 for (i
= 0; i
< j
; i
++)
639 a
= sorted_allocnos
[i
];
640 ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) = a
;
641 ALLOCNO_NEXT_COALESCED_ALLOCNO (a
) = a
;
642 VEC_safe_push (ira_allocno_t
, heap
, allocno_stack_vec
, a
);
643 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
645 fprintf (ira_dump_file
, " Pushing");
646 print_coalesced_allocno (a
);
647 fprintf (ira_dump_file
, "\n");
652 if (best_hard_regno
>= 0)
653 allocated_hardreg_p
[best_hard_regno
] = true;
654 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
655 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
657 ALLOCNO_HARD_REGNO (a
) = best_hard_regno
;
658 ALLOCNO_ASSIGNED_P (a
) = true;
659 if (best_hard_regno
>= 0)
660 update_copy_costs (a
, true);
661 ira_assert (ALLOCNO_COVER_CLASS (a
) == cover_class
);
662 /* We don't need updated costs anymore: */
663 ira_free_allocno_updated_costs (a
);
667 return best_hard_regno
>= 0;
672 /* This page contains the allocator based on the Chaitin-Briggs algorithm. */
674 /* Bucket of allocnos that can colored currently without spilling. */
675 static ira_allocno_t colorable_allocno_bucket
;
677 /* Bucket of allocnos that might be not colored currently without
679 static ira_allocno_t uncolorable_allocno_bucket
;
681 /* Each element of the array contains the current number of allocnos
682 of given *cover* class in the uncolorable_bucket. */
683 static int uncolorable_allocnos_num
[N_REG_CLASSES
];
685 /* Return the current spill priority of allocno A. The less the
686 number, the more preferable the allocno for spilling. */
688 allocno_spill_priority (ira_allocno_t a
)
690 return (ALLOCNO_TEMP (a
)
691 / (ALLOCNO_LEFT_CONFLICTS_SIZE (a
)
692 * ira_reg_class_nregs
[ALLOCNO_COVER_CLASS (a
)][ALLOCNO_MODE (a
)]
696 /* Add ALLOCNO to bucket *BUCKET_PTR. ALLOCNO should be not in a bucket
699 add_allocno_to_bucket (ira_allocno_t allocno
, ira_allocno_t
*bucket_ptr
)
701 ira_allocno_t first_allocno
;
702 enum reg_class cover_class
;
704 if (bucket_ptr
== &uncolorable_allocno_bucket
705 && (cover_class
= ALLOCNO_COVER_CLASS (allocno
)) != NO_REGS
)
707 uncolorable_allocnos_num
[cover_class
]++;
708 ira_assert (uncolorable_allocnos_num
[cover_class
] > 0);
710 first_allocno
= *bucket_ptr
;
711 ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno
) = first_allocno
;
712 ALLOCNO_PREV_BUCKET_ALLOCNO (allocno
) = NULL
;
713 if (first_allocno
!= NULL
)
714 ALLOCNO_PREV_BUCKET_ALLOCNO (first_allocno
) = allocno
;
715 *bucket_ptr
= allocno
;
718 /* The function returns frequency and number of available hard
719 registers for allocnos coalesced with ALLOCNO. */
721 get_coalesced_allocnos_attributes (ira_allocno_t allocno
, int *freq
, int *num
)
727 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
728 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
730 *freq
+= ALLOCNO_FREQ (a
);
731 *num
+= ALLOCNO_AVAILABLE_REGS_NUM (a
);
737 /* Compare two allocnos to define which allocno should be pushed first
738 into the coloring stack. If the return is a negative number, the
739 allocno given by the first parameter will be pushed first. In this
740 case such allocno has less priority than the second one and the
741 hard register will be assigned to it after assignment to the second
742 one. As the result of such assignment order, the second allocno
743 has a better chance to get the best hard register. */
745 bucket_allocno_compare_func (const void *v1p
, const void *v2p
)
747 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
748 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
749 int diff
, a1_freq
, a2_freq
, a1_num
, a2_num
;
751 if ((diff
= (int) ALLOCNO_COVER_CLASS (a2
) - ALLOCNO_COVER_CLASS (a1
)) != 0)
753 get_coalesced_allocnos_attributes (a1
, &a1_freq
, &a1_num
);
754 get_coalesced_allocnos_attributes (a2
, &a2_freq
, &a2_num
);
755 if ((diff
= a2_num
- a1_num
) != 0)
757 else if ((diff
= a1_freq
- a2_freq
) != 0)
759 return ALLOCNO_NUM (a2
) - ALLOCNO_NUM (a1
);
762 /* Sort bucket *BUCKET_PTR and return the result through
765 sort_bucket (ira_allocno_t
*bucket_ptr
)
767 ira_allocno_t a
, head
;
770 for (n
= 0, a
= *bucket_ptr
; a
!= NULL
; a
= ALLOCNO_NEXT_BUCKET_ALLOCNO (a
))
771 sorted_allocnos
[n
++] = a
;
774 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
),
775 bucket_allocno_compare_func
);
777 for (n
--; n
>= 0; n
--)
779 a
= sorted_allocnos
[n
];
780 ALLOCNO_NEXT_BUCKET_ALLOCNO (a
) = head
;
781 ALLOCNO_PREV_BUCKET_ALLOCNO (a
) = NULL
;
783 ALLOCNO_PREV_BUCKET_ALLOCNO (head
) = a
;
789 /* Add ALLOCNO to bucket *BUCKET_PTR maintaining the order according
790 their priority. ALLOCNO should be not in a bucket before the
793 add_allocno_to_ordered_bucket (ira_allocno_t allocno
,
794 ira_allocno_t
*bucket_ptr
)
796 ira_allocno_t before
, after
;
797 enum reg_class cover_class
;
799 if (bucket_ptr
== &uncolorable_allocno_bucket
800 && (cover_class
= ALLOCNO_COVER_CLASS (allocno
)) != NO_REGS
)
802 uncolorable_allocnos_num
[cover_class
]++;
803 ira_assert (uncolorable_allocnos_num
[cover_class
] > 0);
805 for (before
= *bucket_ptr
, after
= NULL
;
807 after
= before
, before
= ALLOCNO_NEXT_BUCKET_ALLOCNO (before
))
808 if (bucket_allocno_compare_func (&allocno
, &before
) < 0)
810 ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno
) = before
;
811 ALLOCNO_PREV_BUCKET_ALLOCNO (allocno
) = after
;
813 *bucket_ptr
= allocno
;
815 ALLOCNO_NEXT_BUCKET_ALLOCNO (after
) = allocno
;
817 ALLOCNO_PREV_BUCKET_ALLOCNO (before
) = allocno
;
820 /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
823 delete_allocno_from_bucket (ira_allocno_t allocno
, ira_allocno_t
*bucket_ptr
)
825 ira_allocno_t prev_allocno
, next_allocno
;
826 enum reg_class cover_class
;
828 if (bucket_ptr
== &uncolorable_allocno_bucket
829 && (cover_class
= ALLOCNO_COVER_CLASS (allocno
)) != NO_REGS
)
831 uncolorable_allocnos_num
[cover_class
]--;
832 ira_assert (uncolorable_allocnos_num
[cover_class
] >= 0);
834 prev_allocno
= ALLOCNO_PREV_BUCKET_ALLOCNO (allocno
);
835 next_allocno
= ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno
);
836 if (prev_allocno
!= NULL
)
837 ALLOCNO_NEXT_BUCKET_ALLOCNO (prev_allocno
) = next_allocno
;
840 ira_assert (*bucket_ptr
== allocno
);
841 *bucket_ptr
= next_allocno
;
843 if (next_allocno
!= NULL
)
844 ALLOCNO_PREV_BUCKET_ALLOCNO (next_allocno
) = prev_allocno
;
847 /* Splay tree for each cover class. The trees are indexed by the
848 corresponding cover classes. Splay trees contain uncolorable
850 static splay_tree uncolorable_allocnos_splay_tree
[N_REG_CLASSES
];
852 /* If the following macro is TRUE, splay tree is used to choose an
853 allocno of the corresponding cover class for spilling. When the
854 number uncolorable allocnos of given cover class decreases to some
855 threshold, linear array search is used to find the best allocno for
856 spilling. This threshold is actually pretty big because, although
857 splay trees asymptotically is much faster, each splay tree
858 operation is sufficiently costly especially taking cache locality
860 #define USE_SPLAY_P(CLASS) (uncolorable_allocnos_num[CLASS] > 4000)
862 /* Put ALLOCNO onto the coloring stack without removing it from its
863 bucket. Pushing allocno to the coloring stack can result in moving
864 conflicting allocnos from the uncolorable bucket to the colorable
867 push_allocno_to_stack (ira_allocno_t allocno
)
869 int left_conflicts_size
, conflict_size
, size
;
870 ira_allocno_t a
, conflict_allocno
;
871 enum reg_class cover_class
;
872 ira_allocno_conflict_iterator aci
;
874 ALLOCNO_IN_GRAPH_P (allocno
) = false;
875 VEC_safe_push (ira_allocno_t
, heap
, allocno_stack_vec
, allocno
);
876 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
877 if (cover_class
== NO_REGS
)
879 size
= ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE (allocno
)];
880 if (allocno_coalesced_p
)
881 bitmap_clear (processed_coalesced_allocno_bitmap
);
882 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
883 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
885 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_allocno
, aci
)
887 conflict_allocno
= ALLOCNO_FIRST_COALESCED_ALLOCNO (conflict_allocno
);
888 if (bitmap_bit_p (coloring_allocno_bitmap
,
889 ALLOCNO_NUM (conflict_allocno
)))
891 ira_assert (cover_class
892 == ALLOCNO_COVER_CLASS (conflict_allocno
));
893 if (allocno_coalesced_p
)
895 if (bitmap_bit_p (processed_coalesced_allocno_bitmap
,
896 ALLOCNO_NUM (conflict_allocno
)))
898 bitmap_set_bit (processed_coalesced_allocno_bitmap
,
899 ALLOCNO_NUM (conflict_allocno
));
901 if (ALLOCNO_IN_GRAPH_P (conflict_allocno
)
902 && ! ALLOCNO_ASSIGNED_P (conflict_allocno
))
905 = ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno
);
907 = (ira_reg_class_nregs
908 [cover_class
][ALLOCNO_MODE (conflict_allocno
)]);
910 (ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno
) >= size
);
911 if (left_conflicts_size
+ conflict_size
912 <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno
))
914 ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno
) -= size
;
918 = ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno
) - size
;
919 if (uncolorable_allocnos_splay_tree
[cover_class
] != NULL
920 && !ALLOCNO_SPLAY_REMOVED_P (conflict_allocno
)
921 && USE_SPLAY_P (cover_class
))
925 (uncolorable_allocnos_splay_tree
[cover_class
],
926 (splay_tree_key
) conflict_allocno
) != NULL
);
928 (uncolorable_allocnos_splay_tree
[cover_class
],
929 (splay_tree_key
) conflict_allocno
);
930 ALLOCNO_SPLAY_REMOVED_P (conflict_allocno
) = true;
931 VEC_safe_push (ira_allocno_t
, heap
,
932 removed_splay_allocno_vec
,
935 ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno
)
936 = left_conflicts_size
;
937 if (left_conflicts_size
+ conflict_size
938 <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno
))
940 delete_allocno_from_bucket
941 (conflict_allocno
, &uncolorable_allocno_bucket
);
942 add_allocno_to_ordered_bucket
943 (conflict_allocno
, &colorable_allocno_bucket
);
953 /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
954 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
956 remove_allocno_from_bucket_and_push (ira_allocno_t allocno
, bool colorable_p
)
958 enum reg_class cover_class
;
961 delete_allocno_from_bucket (allocno
, &colorable_allocno_bucket
);
963 delete_allocno_from_bucket (allocno
, &uncolorable_allocno_bucket
);
964 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
966 fprintf (ira_dump_file
, " Pushing");
967 print_coalesced_allocno (allocno
);
969 fprintf (ira_dump_file
, "\n");
971 fprintf (ira_dump_file
, "(potential spill: %spri=%d, cost=%d)\n",
972 ALLOCNO_BAD_SPILL_P (allocno
) ? "bad spill, " : "",
973 allocno_spill_priority (allocno
), ALLOCNO_TEMP (allocno
));
975 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
976 ira_assert ((colorable_p
977 && (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno
)
978 + ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE (allocno
)]
979 <= ALLOCNO_AVAILABLE_REGS_NUM (allocno
)))
981 && (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno
)
982 + ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE
984 > ALLOCNO_AVAILABLE_REGS_NUM (allocno
))));
986 ALLOCNO_MAY_BE_SPILLED_P (allocno
) = true;
987 push_allocno_to_stack (allocno
);
990 /* Put all allocnos from colorable bucket onto the coloring stack. */
992 push_only_colorable (void)
994 sort_bucket (&colorable_allocno_bucket
);
995 for (;colorable_allocno_bucket
!= NULL
;)
996 remove_allocno_from_bucket_and_push (colorable_allocno_bucket
, true);
999 /* Puts ALLOCNO chosen for potential spilling onto the coloring
1002 push_allocno_to_spill (ira_allocno_t allocno
)
1004 delete_allocno_from_bucket (allocno
, &uncolorable_allocno_bucket
);
1005 ALLOCNO_MAY_BE_SPILLED_P (allocno
) = true;
1006 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1007 fprintf (ira_dump_file
, " Pushing p%d(%d) (spill for NO_REGS)\n",
1008 ALLOCNO_NUM (allocno
), ALLOCNO_REGNO (allocno
));
1009 push_allocno_to_stack (allocno
);
1012 /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
1013 loop given by its LOOP_NODE. */
1015 ira_loop_edge_freq (ira_loop_tree_node_t loop_node
, int regno
, bool exit_p
)
1020 VEC (edge
, heap
) *edges
;
1022 ira_assert (loop_node
->loop
!= NULL
1023 && (regno
< 0 || regno
>= FIRST_PSEUDO_REGISTER
));
1027 FOR_EACH_EDGE (e
, ei
, loop_node
->loop
->header
->preds
)
1028 if (e
->src
!= loop_node
->loop
->latch
1030 || (bitmap_bit_p (DF_LR_OUT (e
->src
), regno
)
1031 && bitmap_bit_p (DF_LR_IN (e
->dest
), regno
))))
1032 freq
+= EDGE_FREQUENCY (e
);
1036 edges
= get_loop_exit_edges (loop_node
->loop
);
1037 for (i
= 0; VEC_iterate (edge
, edges
, i
, e
); i
++)
1039 || (bitmap_bit_p (DF_LR_OUT (e
->src
), regno
)
1040 && bitmap_bit_p (DF_LR_IN (e
->dest
), regno
)))
1041 freq
+= EDGE_FREQUENCY (e
);
1042 VEC_free (edge
, heap
, edges
);
1045 return REG_FREQ_FROM_EDGE_FREQ (freq
);
1048 /* Calculate and return the cost of putting allocno A into memory. */
1050 calculate_allocno_spill_cost (ira_allocno_t a
)
1053 enum machine_mode mode
;
1054 enum reg_class rclass
;
1055 ira_allocno_t parent_allocno
;
1056 ira_loop_tree_node_t parent_node
, loop_node
;
1058 regno
= ALLOCNO_REGNO (a
);
1059 cost
= ALLOCNO_UPDATED_MEMORY_COST (a
) - ALLOCNO_UPDATED_COVER_CLASS_COST (a
);
1060 if (ALLOCNO_CAP (a
) != NULL
)
1062 loop_node
= ALLOCNO_LOOP_TREE_NODE (a
);
1063 if ((parent_node
= loop_node
->parent
) == NULL
)
1065 if ((parent_allocno
= parent_node
->regno_allocno_map
[regno
]) == NULL
)
1067 mode
= ALLOCNO_MODE (a
);
1068 rclass
= ALLOCNO_COVER_CLASS (a
);
1069 if (ALLOCNO_HARD_REGNO (parent_allocno
) < 0)
1070 cost
-= (ira_memory_move_cost
[mode
][rclass
][0]
1071 * ira_loop_edge_freq (loop_node
, regno
, true)
1072 + ira_memory_move_cost
[mode
][rclass
][1]
1073 * ira_loop_edge_freq (loop_node
, regno
, false));
1075 cost
+= ((ira_memory_move_cost
[mode
][rclass
][1]
1076 * ira_loop_edge_freq (loop_node
, regno
, true)
1077 + ira_memory_move_cost
[mode
][rclass
][0]
1078 * ira_loop_edge_freq (loop_node
, regno
, false))
1079 - (ira_get_register_move_cost (mode
, rclass
, rclass
)
1080 * (ira_loop_edge_freq (loop_node
, regno
, false)
1081 + ira_loop_edge_freq (loop_node
, regno
, true))));
1085 /* Compare keys in the splay tree used to choose best allocno for
1086 spilling. The best allocno has the minimal key. */
1088 allocno_spill_priority_compare (splay_tree_key k1
, splay_tree_key k2
)
1090 int pri1
, pri2
, diff
;
1091 ira_allocno_t a1
= (ira_allocno_t
) k1
, a2
= (ira_allocno_t
) k2
;
1093 pri1
= (ALLOCNO_TEMP (a1
)
1094 / (ALLOCNO_LEFT_CONFLICTS_SIZE (a1
)
1095 * ira_reg_class_nregs
[ALLOCNO_COVER_CLASS (a1
)][ALLOCNO_MODE (a1
)]
1097 pri2
= (ALLOCNO_TEMP (a2
)
1098 / (ALLOCNO_LEFT_CONFLICTS_SIZE (a2
)
1099 * ira_reg_class_nregs
[ALLOCNO_COVER_CLASS (a2
)][ALLOCNO_MODE (a2
)]
1101 if ((diff
= pri1
- pri2
) != 0)
1103 if ((diff
= ALLOCNO_TEMP (a1
) - ALLOCNO_TEMP (a2
)) != 0)
1105 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
1108 /* Allocate data of SIZE for the splay trees. We allocate only spay
1109 tree roots or splay tree nodes. If you change this, please rewrite
1112 splay_tree_allocate (int size
, void *data ATTRIBUTE_UNUSED
)
1114 if (size
!= sizeof (struct splay_tree_node_s
))
1115 return ira_allocate (size
);
1116 return pool_alloc (splay_tree_node_pool
);
1119 /* Free data NODE for the splay trees. We allocate and free only spay
1120 tree roots or splay tree nodes. If you change this, please rewrite
1123 splay_tree_free (void *node
, void *data ATTRIBUTE_UNUSED
)
1126 enum reg_class cover_class
;
1128 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1130 cover_class
= ira_reg_class_cover
[i
];
1131 if (node
== uncolorable_allocnos_splay_tree
[cover_class
])
1137 pool_free (splay_tree_node_pool
, node
);
1140 /* Push allocnos to the coloring stack. The order of allocnos in the
1141 stack defines the order for the subsequent coloring. */
1143 push_allocnos_to_stack (void)
1145 ira_allocno_t allocno
, a
, i_allocno
, *allocno_vec
;
1146 enum reg_class cover_class
, rclass
;
1147 int allocno_pri
, i_allocno_pri
, allocno_cost
, i_allocno_cost
;
1148 int i
, j
, num
, cover_class_allocnos_num
[N_REG_CLASSES
];
1149 ira_allocno_t
*cover_class_allocnos
[N_REG_CLASSES
];
1153 VEC_truncate(ira_allocno_t
, removed_splay_allocno_vec
, 0);
1154 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1156 cover_class
= ira_reg_class_cover
[i
];
1157 cover_class_allocnos_num
[cover_class
] = 0;
1158 cover_class_allocnos
[cover_class
] = NULL
;
1159 uncolorable_allocnos_splay_tree
[cover_class
] = NULL
;
1161 /* Calculate uncolorable allocno spill costs. */
1162 for (allocno
= uncolorable_allocno_bucket
;
1164 allocno
= ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno
))
1165 if ((cover_class
= ALLOCNO_COVER_CLASS (allocno
)) != NO_REGS
)
1167 cover_class_allocnos_num
[cover_class
]++;
1169 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
1170 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1172 cost
+= calculate_allocno_spill_cost (a
);
1176 /* ??? Remove cost of copies between the coalesced
1178 ALLOCNO_TEMP (allocno
) = cost
;
1180 /* Define place where to put uncolorable allocnos of the same cover
1182 for (num
= i
= 0; i
< ira_reg_class_cover_size
; i
++)
1184 cover_class
= ira_reg_class_cover
[i
];
1185 ira_assert (cover_class_allocnos_num
[cover_class
]
1186 == uncolorable_allocnos_num
[cover_class
]);
1187 if (cover_class_allocnos_num
[cover_class
] != 0)
1189 cover_class_allocnos
[cover_class
] = allocnos_for_spilling
+ num
;
1190 num
+= cover_class_allocnos_num
[cover_class
];
1191 cover_class_allocnos_num
[cover_class
] = 0;
1193 if (USE_SPLAY_P (cover_class
))
1194 uncolorable_allocnos_splay_tree
[cover_class
]
1195 = splay_tree_new_with_allocator (allocno_spill_priority_compare
,
1196 NULL
, NULL
, splay_tree_allocate
,
1197 splay_tree_free
, NULL
);
1199 ira_assert (num
<= ira_allocnos_num
);
1200 /* Collect uncolorable allocnos of each cover class. */
1201 for (allocno
= uncolorable_allocno_bucket
;
1203 allocno
= ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno
))
1204 if ((cover_class
= ALLOCNO_COVER_CLASS (allocno
)) != NO_REGS
)
1206 cover_class_allocnos
1207 [cover_class
][cover_class_allocnos_num
[cover_class
]++] = allocno
;
1208 if (uncolorable_allocnos_splay_tree
[cover_class
] != NULL
)
1209 splay_tree_insert (uncolorable_allocnos_splay_tree
[cover_class
],
1210 (splay_tree_key
) allocno
,
1211 (splay_tree_value
) allocno
);
1215 push_only_colorable ();
1216 allocno
= uncolorable_allocno_bucket
;
1217 if (allocno
== NULL
)
1219 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
1220 if (cover_class
== NO_REGS
)
1222 push_allocno_to_spill (allocno
);
1225 /* Potential spilling. */
1227 (ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE (allocno
)] > 0);
1228 if (USE_SPLAY_P (cover_class
))
1230 for (;VEC_length (ira_allocno_t
, removed_splay_allocno_vec
) != 0;)
1232 allocno
= VEC_pop (ira_allocno_t
, removed_splay_allocno_vec
);
1233 ALLOCNO_SPLAY_REMOVED_P (allocno
) = false;
1234 rclass
= ALLOCNO_COVER_CLASS (allocno
);
1235 if (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno
)
1236 + ira_reg_class_nregs
[rclass
][ALLOCNO_MODE (allocno
)]
1237 > ALLOCNO_AVAILABLE_REGS_NUM (allocno
))
1239 (uncolorable_allocnos_splay_tree
[rclass
],
1240 (splay_tree_key
) allocno
, (splay_tree_value
) allocno
);
1242 allocno
= ((ira_allocno_t
)
1244 (uncolorable_allocnos_splay_tree
[cover_class
])->key
);
1245 splay_tree_remove (uncolorable_allocnos_splay_tree
[cover_class
],
1246 (splay_tree_key
) allocno
);
1250 num
= cover_class_allocnos_num
[cover_class
];
1251 ira_assert (num
> 0);
1252 allocno_vec
= cover_class_allocnos
[cover_class
];
1254 allocno_pri
= allocno_cost
= 0;
1255 /* Sort uncolorable allocno to find the one with the lowest
1257 for (i
= 0, j
= num
- 1; i
<= j
;)
1259 i_allocno
= allocno_vec
[i
];
1260 if (! ALLOCNO_IN_GRAPH_P (i_allocno
)
1261 && ALLOCNO_IN_GRAPH_P (allocno_vec
[j
]))
1263 i_allocno
= allocno_vec
[j
];
1264 allocno_vec
[j
] = allocno_vec
[i
];
1265 allocno_vec
[i
] = i_allocno
;
1267 if (ALLOCNO_IN_GRAPH_P (i_allocno
))
1270 ira_assert (ALLOCNO_TEMP (i_allocno
) != INT_MAX
);
1271 i_allocno_cost
= ALLOCNO_TEMP (i_allocno
);
1272 i_allocno_pri
= allocno_spill_priority (i_allocno
);
1274 || (! ALLOCNO_BAD_SPILL_P (i_allocno
)
1275 && ALLOCNO_BAD_SPILL_P (allocno
))
1276 || (! (ALLOCNO_BAD_SPILL_P (i_allocno
)
1277 && ! ALLOCNO_BAD_SPILL_P (allocno
))
1278 && (allocno_pri
> i_allocno_pri
1279 || (allocno_pri
== i_allocno_pri
1280 && (allocno_cost
> i_allocno_cost
1281 || (allocno_cost
== i_allocno_cost
1282 && (ALLOCNO_NUM (allocno
)
1283 > ALLOCNO_NUM (i_allocno
))))))))
1285 allocno
= i_allocno
;
1286 allocno_cost
= i_allocno_cost
;
1287 allocno_pri
= i_allocno_pri
;
1290 if (! ALLOCNO_IN_GRAPH_P (allocno_vec
[j
]))
1293 ira_assert (allocno
!= NULL
&& j
>= 0);
1294 cover_class_allocnos_num
[cover_class
] = j
+ 1;
1296 ira_assert (ALLOCNO_IN_GRAPH_P (allocno
)
1297 && ALLOCNO_COVER_CLASS (allocno
) == cover_class
1298 && (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno
)
1299 + ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE
1301 > ALLOCNO_AVAILABLE_REGS_NUM (allocno
)));
1302 remove_allocno_from_bucket_and_push (allocno
, false);
1304 ira_assert (colorable_allocno_bucket
== NULL
1305 && uncolorable_allocno_bucket
== NULL
);
1306 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1308 cover_class
= ira_reg_class_cover
[i
];
1309 ira_assert (uncolorable_allocnos_num
[cover_class
] == 0);
1310 if (uncolorable_allocnos_splay_tree
[cover_class
] != NULL
)
1311 splay_tree_delete (uncolorable_allocnos_splay_tree
[cover_class
]);
1315 /* Pop the coloring stack and assign hard registers to the popped
1318 pop_allocnos_from_stack (void)
1320 ira_allocno_t allocno
;
1321 enum reg_class cover_class
;
1323 for (;VEC_length (ira_allocno_t
, allocno_stack_vec
) != 0;)
1325 allocno
= VEC_pop (ira_allocno_t
, allocno_stack_vec
);
1326 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
1327 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1329 fprintf (ira_dump_file
, " Popping");
1330 print_coalesced_allocno (allocno
);
1331 fprintf (ira_dump_file
, " -- ");
1333 if (cover_class
== NO_REGS
)
1335 ALLOCNO_HARD_REGNO (allocno
) = -1;
1336 ALLOCNO_ASSIGNED_P (allocno
) = true;
1337 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno
) == NULL
);
1339 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno
) == NULL
);
1340 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1341 fprintf (ira_dump_file
, "assign memory\n");
1343 else if (assign_hard_reg (allocno
, false))
1345 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1346 fprintf (ira_dump_file
, "assign reg %d\n",
1347 ALLOCNO_HARD_REGNO (allocno
));
1349 else if (ALLOCNO_ASSIGNED_P (allocno
))
1351 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1352 fprintf (ira_dump_file
, "spill\n");
1354 ALLOCNO_IN_GRAPH_P (allocno
) = true;
1358 /* Set up number of available hard registers for ALLOCNO. */
1360 setup_allocno_available_regs_num (ira_allocno_t allocno
)
1362 int i
, n
, hard_regs_num
, hard_regno
;
1363 enum machine_mode mode
;
1364 enum reg_class cover_class
;
1366 HARD_REG_SET temp_set
;
1368 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
1369 ALLOCNO_AVAILABLE_REGS_NUM (allocno
) = ira_available_class_regs
[cover_class
];
1370 if (cover_class
== NO_REGS
)
1372 CLEAR_HARD_REG_SET (temp_set
);
1373 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) == allocno
);
1374 hard_regs_num
= ira_class_hard_regs_num
[cover_class
];
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 mode
= ALLOCNO_MODE (allocno
);
1383 for (n
= 0, i
= hard_regs_num
- 1; i
>= 0; i
--)
1385 hard_regno
= ira_class_hard_regs
[cover_class
][i
];
1386 if (TEST_HARD_REG_BIT (temp_set
, hard_regno
)
1387 || TEST_HARD_REG_BIT (prohibited_class_mode_regs
[cover_class
][mode
],
1391 if (internal_flag_ira_verbose
> 2 && n
> 0 && ira_dump_file
!= NULL
)
1392 fprintf (ira_dump_file
, " Reg %d of %s has %d regs less\n",
1393 ALLOCNO_REGNO (allocno
), reg_class_names
[cover_class
], n
);
1394 ALLOCNO_AVAILABLE_REGS_NUM (allocno
) -= n
;
1397 /* Set up ALLOCNO_LEFT_CONFLICTS_SIZE for ALLOCNO. */
1399 setup_allocno_left_conflicts_size (ira_allocno_t allocno
)
1401 int i
, hard_regs_num
, hard_regno
, conflict_allocnos_size
;
1402 ira_allocno_t a
, conflict_allocno
;
1403 enum reg_class cover_class
;
1404 HARD_REG_SET temp_set
;
1405 ira_allocno_conflict_iterator aci
;
1407 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
1408 hard_regs_num
= ira_class_hard_regs_num
[cover_class
];
1409 CLEAR_HARD_REG_SET (temp_set
);
1410 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) == allocno
);
1411 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
1412 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1414 IOR_HARD_REG_SET (temp_set
, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
1418 AND_HARD_REG_SET (temp_set
, reg_class_contents
[cover_class
]);
1419 AND_COMPL_HARD_REG_SET (temp_set
, ira_no_alloc_regs
);
1420 conflict_allocnos_size
= 0;
1421 if (! hard_reg_set_empty_p (temp_set
))
1422 for (i
= 0; i
< (int) hard_regs_num
; i
++)
1424 hard_regno
= ira_class_hard_regs
[cover_class
][i
];
1425 if (TEST_HARD_REG_BIT (temp_set
, hard_regno
))
1427 conflict_allocnos_size
++;
1428 CLEAR_HARD_REG_BIT (temp_set
, hard_regno
);
1429 if (hard_reg_set_empty_p (temp_set
))
1433 CLEAR_HARD_REG_SET (temp_set
);
1434 if (allocno_coalesced_p
)
1435 bitmap_clear (processed_coalesced_allocno_bitmap
);
1436 if (cover_class
!= NO_REGS
)
1437 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
1438 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1440 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_allocno
, aci
)
1443 = ALLOCNO_FIRST_COALESCED_ALLOCNO (conflict_allocno
);
1444 if (bitmap_bit_p (consideration_allocno_bitmap
,
1445 ALLOCNO_NUM (conflict_allocno
)))
1447 ira_assert (cover_class
1448 == ALLOCNO_COVER_CLASS (conflict_allocno
));
1449 if (allocno_coalesced_p
)
1451 if (bitmap_bit_p (processed_coalesced_allocno_bitmap
,
1452 ALLOCNO_NUM (conflict_allocno
)))
1454 bitmap_set_bit (processed_coalesced_allocno_bitmap
,
1455 ALLOCNO_NUM (conflict_allocno
));
1457 if (! ALLOCNO_ASSIGNED_P (conflict_allocno
))
1458 conflict_allocnos_size
1459 += (ira_reg_class_nregs
1460 [cover_class
][ALLOCNO_MODE (conflict_allocno
)]);
1461 else if ((hard_regno
= ALLOCNO_HARD_REGNO (conflict_allocno
))
1464 int last
= (hard_regno
1466 [hard_regno
][ALLOCNO_MODE (conflict_allocno
)]);
1468 while (hard_regno
< last
)
1470 if (! TEST_HARD_REG_BIT (temp_set
, hard_regno
))
1472 conflict_allocnos_size
++;
1473 SET_HARD_REG_BIT (temp_set
, hard_regno
);
1483 ALLOCNO_LEFT_CONFLICTS_SIZE (allocno
) = conflict_allocnos_size
;
1486 /* Put ALLOCNO in a bucket corresponding to its number and size of its
1487 conflicting allocnos and hard registers. */
1489 put_allocno_into_bucket (ira_allocno_t allocno
)
1491 enum reg_class cover_class
;
1493 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
1494 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) != allocno
)
1496 ALLOCNO_IN_GRAPH_P (allocno
) = true;
1497 setup_allocno_left_conflicts_size (allocno
);
1498 setup_allocno_available_regs_num (allocno
);
1499 if (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno
)
1500 + ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE (allocno
)]
1501 <= ALLOCNO_AVAILABLE_REGS_NUM (allocno
))
1502 add_allocno_to_bucket (allocno
, &colorable_allocno_bucket
);
1504 add_allocno_to_bucket (allocno
, &uncolorable_allocno_bucket
);
1507 /* The function is used to sort allocnos according to their execution
1510 copy_freq_compare_func (const void *v1p
, const void *v2p
)
1512 ira_copy_t cp1
= *(const ira_copy_t
*) v1p
, cp2
= *(const ira_copy_t
*) v2p
;
1520 /* If freqencies are equal, sort by copies, so that the results of
1521 qsort leave nothing to chance. */
1522 return cp1
->num
- cp2
->num
;
1525 /* Merge two sets of coalesced allocnos given correspondingly by
1526 allocnos A1 and A2 (more accurately merging A2 set into A1
1529 merge_allocnos (ira_allocno_t a1
, ira_allocno_t a2
)
1531 ira_allocno_t a
, first
, last
, next
;
1533 first
= ALLOCNO_FIRST_COALESCED_ALLOCNO (a1
);
1534 if (first
== ALLOCNO_FIRST_COALESCED_ALLOCNO (a2
))
1536 for (last
= a2
, a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a2
);;
1537 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1539 ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) = first
;
1544 next
= ALLOCNO_NEXT_COALESCED_ALLOCNO (first
);
1545 ALLOCNO_NEXT_COALESCED_ALLOCNO (first
) = a2
;
1546 ALLOCNO_NEXT_COALESCED_ALLOCNO (last
) = next
;
1549 /* Return TRUE if there are conflicting allocnos from two sets of
1550 coalesced allocnos given correspondingly by allocnos A1 and A2. If
1551 RELOAD_P is TRUE, we use live ranges to find conflicts because
1552 conflicts are represented only for allocnos of the same cover class
1553 and during the reload pass we coalesce allocnos for sharing stack
1556 coalesced_allocno_conflict_p (ira_allocno_t a1
, ira_allocno_t a2
,
1559 ira_allocno_t a
, conflict_allocno
;
1560 ira_allocno_conflict_iterator aci
;
1562 if (allocno_coalesced_p
)
1564 bitmap_clear (processed_coalesced_allocno_bitmap
);
1565 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a1
);;
1566 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1568 bitmap_set_bit (processed_coalesced_allocno_bitmap
, ALLOCNO_NUM (a
));
1573 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a2
);;
1574 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1578 for (conflict_allocno
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a1
);;
1580 = ALLOCNO_NEXT_COALESCED_ALLOCNO (conflict_allocno
))
1582 if (allocnos_have_intersected_live_ranges_p (a
,
1585 if (conflict_allocno
== a1
)
1591 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_allocno
, aci
)
1592 if (conflict_allocno
== a1
1593 || (allocno_coalesced_p
1594 && bitmap_bit_p (processed_coalesced_allocno_bitmap
,
1595 ALLOCNO_NUM (conflict_allocno
))))
1604 /* The major function for aggressive allocno coalescing. For the
1605 reload pass (RELOAD_P) we coalesce only spilled allocnos. If some
1606 allocnos have been coalesced, we set up flag
1607 allocno_coalesced_p. */
1609 coalesce_allocnos (bool reload_p
)
1612 ira_copy_t cp
, next_cp
, *sorted_copies
;
1613 enum reg_class cover_class
;
1614 enum machine_mode mode
;
1616 int i
, n
, cp_num
, regno
;
1619 sorted_copies
= (ira_copy_t
*) ira_allocate (ira_copies_num
1620 * sizeof (ira_copy_t
));
1622 /* Collect copies. */
1623 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, j
, bi
)
1625 a
= ira_allocnos
[j
];
1626 regno
= ALLOCNO_REGNO (a
);
1627 if ((! reload_p
&& ALLOCNO_ASSIGNED_P (a
))
1629 && (! ALLOCNO_ASSIGNED_P (a
) || ALLOCNO_HARD_REGNO (a
) >= 0
1630 || (regno
< ira_reg_equiv_len
1631 && (ira_reg_equiv_const
[regno
] != NULL_RTX
1632 || ira_reg_equiv_invariant_p
[regno
])))))
1634 cover_class
= ALLOCNO_COVER_CLASS (a
);
1635 mode
= ALLOCNO_MODE (a
);
1636 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
1640 next_cp
= cp
->next_first_allocno_copy
;
1641 regno
= ALLOCNO_REGNO (cp
->second
);
1642 /* For priority coloring we coalesce allocnos only with
1643 the same cover class not with intersected cover
1644 classes as it were possible. It is done for
1647 || (ALLOCNO_COVER_CLASS (cp
->second
) == cover_class
1648 && ALLOCNO_MODE (cp
->second
) == mode
))
1649 && (cp
->insn
!= NULL
|| cp
->constraint_p
)
1650 && ((! reload_p
&& ! ALLOCNO_ASSIGNED_P (cp
->second
))
1652 && ALLOCNO_ASSIGNED_P (cp
->second
)
1653 && ALLOCNO_HARD_REGNO (cp
->second
) < 0
1654 && (regno
>= ira_reg_equiv_len
1655 || (! ira_reg_equiv_invariant_p
[regno
]
1656 && ira_reg_equiv_const
[regno
] == NULL_RTX
)))))
1657 sorted_copies
[cp_num
++] = cp
;
1659 else if (cp
->second
== a
)
1660 next_cp
= cp
->next_second_allocno_copy
;
1665 qsort (sorted_copies
, cp_num
, sizeof (ira_copy_t
), copy_freq_compare_func
);
1666 /* Coalesced copies, most frequently executed first. */
1667 for (; cp_num
!= 0;)
1669 for (i
= 0; i
< cp_num
; i
++)
1671 cp
= sorted_copies
[i
];
1672 if (! coalesced_allocno_conflict_p (cp
->first
, cp
->second
, reload_p
))
1674 allocno_coalesced_p
= true;
1675 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1678 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
1679 cp
->num
, ALLOCNO_NUM (cp
->first
), ALLOCNO_REGNO (cp
->first
),
1680 ALLOCNO_NUM (cp
->second
), ALLOCNO_REGNO (cp
->second
),
1682 merge_allocnos (cp
->first
, cp
->second
);
1687 /* Collect the rest of copies. */
1688 for (n
= 0; i
< cp_num
; i
++)
1690 cp
= sorted_copies
[i
];
1691 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (cp
->first
)
1692 != ALLOCNO_FIRST_COALESCED_ALLOCNO (cp
->second
))
1693 sorted_copies
[n
++] = cp
;
1697 ira_free (sorted_copies
);
1700 /* Map: allocno number -> allocno priority. */
1701 static int *allocno_priorities
;
1703 /* Set up priorities for N allocnos in array
1704 CONSIDERATION_ALLOCNOS. */
1706 setup_allocno_priorities (ira_allocno_t
*consideration_allocnos
, int n
)
1708 int i
, length
, nrefs
, priority
, max_priority
, mult
;
1712 for (i
= 0; i
< n
; i
++)
1714 a
= consideration_allocnos
[i
];
1715 nrefs
= ALLOCNO_NREFS (a
);
1716 ira_assert (nrefs
>= 0);
1717 mult
= floor_log2 (ALLOCNO_NREFS (a
)) + 1;
1718 ira_assert (mult
>= 0);
1719 allocno_priorities
[ALLOCNO_NUM (a
)]
1722 * (ALLOCNO_MEMORY_COST (a
) - ALLOCNO_COVER_CLASS_COST (a
))
1723 * ira_reg_class_nregs
[ALLOCNO_COVER_CLASS (a
)][ALLOCNO_MODE (a
)]);
1725 priority
= -priority
;
1726 if (max_priority
< priority
)
1727 max_priority
= priority
;
1729 mult
= max_priority
== 0 ? 1 : INT_MAX
/ max_priority
;
1730 for (i
= 0; i
< n
; i
++)
1732 a
= consideration_allocnos
[i
];
1733 length
= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
1736 allocno_priorities
[ALLOCNO_NUM (a
)]
1737 = allocno_priorities
[ALLOCNO_NUM (a
)] * mult
/ length
;
1741 /* Sort allocnos according to their priorities which are calculated
1742 analogous to ones in file `global.c'. */
1744 allocno_priority_compare_func (const void *v1p
, const void *v2p
)
1746 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
1747 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
1750 pri1
= allocno_priorities
[ALLOCNO_NUM (a1
)];
1751 pri2
= allocno_priorities
[ALLOCNO_NUM (a2
)];
1755 /* If regs are equally good, sort by allocnos, so that the results of
1756 qsort leave nothing to chance. */
1757 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
1760 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
1761 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
1763 color_allocnos (void)
1769 allocno_coalesced_p
= false;
1770 processed_coalesced_allocno_bitmap
= ira_allocate_bitmap ();
1771 if (flag_ira_coalesce
)
1772 coalesce_allocnos (false);
1773 if (flag_ira_algorithm
== IRA_ALGORITHM_PRIORITY
)
1776 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
1778 a
= ira_allocnos
[i
];
1779 if (ALLOCNO_COVER_CLASS (a
) == NO_REGS
)
1781 ALLOCNO_HARD_REGNO (a
) = -1;
1782 ALLOCNO_ASSIGNED_P (a
) = true;
1783 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
1784 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
1785 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1787 fprintf (ira_dump_file
, " Spill");
1788 print_coalesced_allocno (a
);
1789 fprintf (ira_dump_file
, "\n");
1793 sorted_allocnos
[n
++] = a
;
1797 setup_allocno_priorities (sorted_allocnos
, n
);
1798 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
),
1799 allocno_priority_compare_func
);
1800 for (i
= 0; i
< n
; i
++)
1802 a
= sorted_allocnos
[i
];
1803 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1805 fprintf (ira_dump_file
, " ");
1806 print_coalesced_allocno (a
);
1807 fprintf (ira_dump_file
, " -- ");
1809 if (assign_hard_reg (a
, false))
1811 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1812 fprintf (ira_dump_file
, "assign hard reg %d\n",
1813 ALLOCNO_HARD_REGNO (a
));
1817 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1818 fprintf (ira_dump_file
, "assign memory\n");
1825 /* Put the allocnos into the corresponding buckets. */
1826 colorable_allocno_bucket
= NULL
;
1827 uncolorable_allocno_bucket
= NULL
;
1828 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
1830 a
= ira_allocnos
[i
];
1831 if (ALLOCNO_COVER_CLASS (a
) == NO_REGS
)
1833 ALLOCNO_HARD_REGNO (a
) = -1;
1834 ALLOCNO_ASSIGNED_P (a
) = true;
1835 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
1836 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
1837 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1839 fprintf (ira_dump_file
, " Spill");
1840 print_coalesced_allocno (a
);
1841 fprintf (ira_dump_file
, "\n");
1845 put_allocno_into_bucket (a
);
1847 push_allocnos_to_stack ();
1848 pop_allocnos_from_stack ();
1850 if (flag_ira_coalesce
)
1851 /* We don't need coalesced allocnos for ira_reassign_pseudos. */
1852 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
1854 a
= ira_allocnos
[i
];
1855 ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) = a
;
1856 ALLOCNO_NEXT_COALESCED_ALLOCNO (a
) = a
;
1858 ira_free_bitmap (processed_coalesced_allocno_bitmap
);
1859 allocno_coalesced_p
= false;
1864 /* Output information about the loop given by its LOOP_TREE_NODE. */
1866 print_loop_title (ira_loop_tree_node_t loop_tree_node
)
1870 ira_loop_tree_node_t subloop_node
, dest_loop_node
;
1874 ira_assert (loop_tree_node
->loop
!= NULL
);
1875 fprintf (ira_dump_file
,
1876 "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
1877 loop_tree_node
->loop
->num
,
1878 (loop_tree_node
->parent
== NULL
1879 ? -1 : loop_tree_node
->parent
->loop
->num
),
1880 loop_tree_node
->loop
->header
->index
,
1881 loop_depth (loop_tree_node
->loop
));
1882 for (subloop_node
= loop_tree_node
->children
;
1883 subloop_node
!= NULL
;
1884 subloop_node
= subloop_node
->next
)
1885 if (subloop_node
->bb
!= NULL
)
1887 fprintf (ira_dump_file
, " %d", subloop_node
->bb
->index
);
1888 FOR_EACH_EDGE (e
, ei
, subloop_node
->bb
->succs
)
1889 if (e
->dest
!= EXIT_BLOCK_PTR
1890 && ((dest_loop_node
= IRA_BB_NODE (e
->dest
)->parent
)
1892 fprintf (ira_dump_file
, "(->%d:l%d)",
1893 e
->dest
->index
, dest_loop_node
->loop
->num
);
1895 fprintf (ira_dump_file
, "\n all:");
1896 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->all_allocnos
, 0, j
, bi
)
1897 fprintf (ira_dump_file
, " %dr%d", j
, ALLOCNO_REGNO (ira_allocnos
[j
]));
1898 fprintf (ira_dump_file
, "\n modified regnos:");
1899 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->modified_regnos
, 0, j
, bi
)
1900 fprintf (ira_dump_file
, " %d", j
);
1901 fprintf (ira_dump_file
, "\n border:");
1902 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->border_allocnos
, 0, j
, bi
)
1903 fprintf (ira_dump_file
, " %dr%d", j
, ALLOCNO_REGNO (ira_allocnos
[j
]));
1904 fprintf (ira_dump_file
, "\n Pressure:");
1905 for (j
= 0; (int) j
< ira_reg_class_cover_size
; j
++)
1907 enum reg_class cover_class
;
1909 cover_class
= ira_reg_class_cover
[j
];
1910 if (loop_tree_node
->reg_pressure
[cover_class
] == 0)
1912 fprintf (ira_dump_file
, " %s=%d", reg_class_names
[cover_class
],
1913 loop_tree_node
->reg_pressure
[cover_class
]);
1915 fprintf (ira_dump_file
, "\n");
1918 /* Color the allocnos inside loop (in the extreme case it can be all
1919 of the function) given the corresponding LOOP_TREE_NODE. The
1920 function is called for each loop during top-down traverse of the
1923 color_pass (ira_loop_tree_node_t loop_tree_node
)
1925 int regno
, hard_regno
, index
= -1;
1926 int cost
, exit_freq
, enter_freq
;
1929 enum machine_mode mode
;
1930 enum reg_class rclass
, cover_class
;
1931 ira_allocno_t a
, subloop_allocno
;
1932 ira_loop_tree_node_t subloop_node
;
1934 ira_assert (loop_tree_node
->bb
== NULL
);
1935 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
1936 print_loop_title (loop_tree_node
);
1938 bitmap_copy (coloring_allocno_bitmap
, loop_tree_node
->all_allocnos
);
1939 bitmap_copy (consideration_allocno_bitmap
, coloring_allocno_bitmap
);
1940 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
1942 a
= ira_allocnos
[j
];
1943 if (! ALLOCNO_ASSIGNED_P (a
))
1945 bitmap_clear_bit (coloring_allocno_bitmap
, ALLOCNO_NUM (a
));
1947 /* Color all mentioned allocnos including transparent ones. */
1949 /* Process caps. They are processed just once. */
1950 if (flag_ira_region
== IRA_REGION_MIXED
1951 || flag_ira_region
== IRA_REGION_ALL
)
1952 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->all_allocnos
, 0, j
, bi
)
1954 a
= ira_allocnos
[j
];
1955 if (ALLOCNO_CAP_MEMBER (a
) == NULL
)
1957 /* Remove from processing in the next loop. */
1958 bitmap_clear_bit (consideration_allocno_bitmap
, j
);
1959 rclass
= ALLOCNO_COVER_CLASS (a
);
1960 if (flag_ira_region
== IRA_REGION_MIXED
1961 && (loop_tree_node
->reg_pressure
[rclass
]
1962 <= ira_available_class_regs
[rclass
]))
1964 mode
= ALLOCNO_MODE (a
);
1965 hard_regno
= ALLOCNO_HARD_REGNO (a
);
1966 if (hard_regno
>= 0)
1968 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
1969 ira_assert (index
>= 0);
1971 regno
= ALLOCNO_REGNO (a
);
1972 subloop_allocno
= ALLOCNO_CAP_MEMBER (a
);
1973 subloop_node
= ALLOCNO_LOOP_TREE_NODE (subloop_allocno
);
1974 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno
));
1975 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
1976 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
1977 if (hard_regno
>= 0)
1978 update_copy_costs (subloop_allocno
, true);
1979 /* We don't need updated costs anymore: */
1980 ira_free_allocno_updated_costs (subloop_allocno
);
1983 /* Update costs of the corresponding allocnos (not caps) in the
1985 for (subloop_node
= loop_tree_node
->subloops
;
1986 subloop_node
!= NULL
;
1987 subloop_node
= subloop_node
->subloop_next
)
1989 ira_assert (subloop_node
->bb
== NULL
);
1990 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
1992 a
= ira_allocnos
[j
];
1993 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
1994 mode
= ALLOCNO_MODE (a
);
1995 rclass
= ALLOCNO_COVER_CLASS (a
);
1996 hard_regno
= ALLOCNO_HARD_REGNO (a
);
1997 /* Use hard register class here. ??? */
1998 if (hard_regno
>= 0)
2000 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
2001 ira_assert (index
>= 0);
2003 regno
= ALLOCNO_REGNO (a
);
2004 /* ??? conflict costs */
2005 subloop_allocno
= subloop_node
->regno_allocno_map
[regno
];
2006 if (subloop_allocno
== NULL
2007 || ALLOCNO_CAP (subloop_allocno
) != NULL
)
2009 ira_assert (ALLOCNO_COVER_CLASS (subloop_allocno
) == rclass
);
2010 ira_assert (bitmap_bit_p (subloop_node
->all_allocnos
,
2011 ALLOCNO_NUM (subloop_allocno
)));
2012 if ((flag_ira_region
== IRA_REGION_MIXED
)
2013 && (loop_tree_node
->reg_pressure
[rclass
]
2014 <= ira_available_class_regs
[rclass
]))
2016 if (! ALLOCNO_ASSIGNED_P (subloop_allocno
))
2018 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
2019 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
2020 if (hard_regno
>= 0)
2021 update_copy_costs (subloop_allocno
, true);
2022 /* We don't need updated costs anymore: */
2023 ira_free_allocno_updated_costs (subloop_allocno
);
2027 exit_freq
= ira_loop_edge_freq (subloop_node
, regno
, true);
2028 enter_freq
= ira_loop_edge_freq (subloop_node
, regno
, false);
2029 ira_assert (regno
< ira_reg_equiv_len
);
2030 if (ira_reg_equiv_invariant_p
[regno
]
2031 || ira_reg_equiv_const
[regno
] != NULL_RTX
)
2033 if (! ALLOCNO_ASSIGNED_P (subloop_allocno
))
2035 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
2036 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
2037 if (hard_regno
>= 0)
2038 update_copy_costs (subloop_allocno
, true);
2039 /* We don't need updated costs anymore: */
2040 ira_free_allocno_updated_costs (subloop_allocno
);
2043 else if (hard_regno
< 0)
2045 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno
)
2046 -= ((ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
)
2047 + (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
));
2051 cover_class
= ALLOCNO_COVER_CLASS (subloop_allocno
);
2052 cost
= (ira_get_register_move_cost (mode
, rclass
, rclass
)
2053 * (exit_freq
+ enter_freq
));
2054 ira_allocate_and_set_or_copy_costs
2055 (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
), cover_class
,
2056 ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno
),
2057 ALLOCNO_HARD_REG_COSTS (subloop_allocno
));
2058 ira_allocate_and_set_or_copy_costs
2059 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno
),
2061 ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno
));
2062 ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
] -= cost
;
2063 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno
)[index
]
2065 if (ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno
)
2066 > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
])
2067 ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno
)
2068 = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
];
2069 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno
)
2070 += (ira_memory_move_cost
[mode
][rclass
][0] * enter_freq
2071 + ira_memory_move_cost
[mode
][rclass
][1] * exit_freq
);
2077 /* Initialize the common data for coloring and calls functions to do
2078 Chaitin-Briggs and regional coloring. */
2082 coloring_allocno_bitmap
= ira_allocate_bitmap ();
2083 allocnos_for_spilling
2084 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
2085 * ira_allocnos_num
);
2086 splay_tree_node_pool
= create_alloc_pool ("splay tree nodes",
2087 sizeof (struct splay_tree_node_s
),
2089 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
2090 fprintf (ira_dump_file
, "\n**** Allocnos coloring:\n\n");
2092 ira_traverse_loop_tree (false, ira_loop_tree_root
, color_pass
, NULL
);
2094 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
2095 ira_print_disposition (ira_dump_file
);
2097 free_alloc_pool (splay_tree_node_pool
);
2098 ira_free_bitmap (coloring_allocno_bitmap
);
2099 ira_free (allocnos_for_spilling
);
2104 /* Move spill/restore code, which are to be generated in ira-emit.c,
2105 to less frequent points (if it is profitable) by reassigning some
2106 allocnos (in loop with subloops containing in another loop) to
2107 memory which results in longer live-range where the corresponding
2108 pseudo-registers will be in memory. */
2110 move_spill_restore (void)
2112 int cost
, regno
, hard_regno
, hard_regno2
, index
;
2114 int enter_freq
, exit_freq
;
2115 enum machine_mode mode
;
2116 enum reg_class rclass
;
2117 ira_allocno_t a
, parent_allocno
, subloop_allocno
;
2118 ira_loop_tree_node_t parent
, loop_node
, subloop_node
;
2119 ira_allocno_iterator ai
;
2124 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
2125 fprintf (ira_dump_file
, "New iteration of spill/restore move\n");
2126 FOR_EACH_ALLOCNO (a
, ai
)
2128 regno
= ALLOCNO_REGNO (a
);
2129 loop_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2130 if (ALLOCNO_CAP_MEMBER (a
) != NULL
2131 || ALLOCNO_CAP (a
) != NULL
2132 || (hard_regno
= ALLOCNO_HARD_REGNO (a
)) < 0
2133 || loop_node
->children
== NULL
2134 /* don't do the optimization because it can create
2135 copies and the reload pass can spill the allocno set
2136 by copy although the allocno will not get memory
2138 || ira_reg_equiv_invariant_p
[regno
]
2139 || ira_reg_equiv_const
[regno
] != NULL_RTX
2140 || !bitmap_bit_p (loop_node
->border_allocnos
, ALLOCNO_NUM (a
)))
2142 mode
= ALLOCNO_MODE (a
);
2143 rclass
= ALLOCNO_COVER_CLASS (a
);
2144 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
2145 ira_assert (index
>= 0);
2146 cost
= (ALLOCNO_MEMORY_COST (a
)
2147 - (ALLOCNO_HARD_REG_COSTS (a
) == NULL
2148 ? ALLOCNO_COVER_CLASS_COST (a
)
2149 : ALLOCNO_HARD_REG_COSTS (a
)[index
]));
2150 for (subloop_node
= loop_node
->subloops
;
2151 subloop_node
!= NULL
;
2152 subloop_node
= subloop_node
->subloop_next
)
2154 ira_assert (subloop_node
->bb
== NULL
);
2155 subloop_allocno
= subloop_node
->regno_allocno_map
[regno
];
2156 if (subloop_allocno
== NULL
)
2158 ira_assert (rclass
== ALLOCNO_COVER_CLASS (subloop_allocno
));
2159 /* We have accumulated cost. To get the real cost of
2160 allocno usage in the loop we should subtract costs of
2161 the subloop allocnos. */
2162 cost
-= (ALLOCNO_MEMORY_COST (subloop_allocno
)
2163 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno
) == NULL
2164 ? ALLOCNO_COVER_CLASS_COST (subloop_allocno
)
2165 : ALLOCNO_HARD_REG_COSTS (subloop_allocno
)[index
]));
2166 exit_freq
= ira_loop_edge_freq (subloop_node
, regno
, true);
2167 enter_freq
= ira_loop_edge_freq (subloop_node
, regno
, false);
2168 if ((hard_regno2
= ALLOCNO_HARD_REGNO (subloop_allocno
)) < 0)
2169 cost
-= (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
2170 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
2174 += (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
2175 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
2176 if (hard_regno2
!= hard_regno
)
2177 cost
-= (ira_get_register_move_cost (mode
, rclass
, rclass
)
2178 * (exit_freq
+ enter_freq
));
2181 if ((parent
= loop_node
->parent
) != NULL
2182 && (parent_allocno
= parent
->regno_allocno_map
[regno
]) != NULL
)
2184 ira_assert (rclass
== ALLOCNO_COVER_CLASS (parent_allocno
));
2185 exit_freq
= ira_loop_edge_freq (loop_node
, regno
, true);
2186 enter_freq
= ira_loop_edge_freq (loop_node
, regno
, false);
2187 if ((hard_regno2
= ALLOCNO_HARD_REGNO (parent_allocno
)) < 0)
2188 cost
-= (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
2189 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
2193 += (ira_memory_move_cost
[mode
][rclass
][1] * exit_freq
2194 + ira_memory_move_cost
[mode
][rclass
][0] * enter_freq
);
2195 if (hard_regno2
!= hard_regno
)
2196 cost
-= (ira_get_register_move_cost (mode
, rclass
, rclass
)
2197 * (exit_freq
+ enter_freq
));
2202 ALLOCNO_HARD_REGNO (a
) = -1;
2203 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2207 " Moving spill/restore for a%dr%d up from loop %d",
2208 ALLOCNO_NUM (a
), regno
, loop_node
->loop
->num
);
2209 fprintf (ira_dump_file
, " - profit %d\n", -cost
);
2221 /* Update current hard reg costs and current conflict hard reg costs
2222 for allocno A. It is done by processing its copies containing
2223 other allocnos already assigned. */
2225 update_curr_costs (ira_allocno_t a
)
2227 int i
, hard_regno
, cost
;
2228 enum machine_mode mode
;
2229 enum reg_class cover_class
, rclass
;
2230 ira_allocno_t another_a
;
2231 ira_copy_t cp
, next_cp
;
2233 ira_free_allocno_updated_costs (a
);
2234 ira_assert (! ALLOCNO_ASSIGNED_P (a
));
2235 cover_class
= ALLOCNO_COVER_CLASS (a
);
2236 if (cover_class
== NO_REGS
)
2238 mode
= ALLOCNO_MODE (a
);
2239 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
2243 next_cp
= cp
->next_first_allocno_copy
;
2244 another_a
= cp
->second
;
2246 else if (cp
->second
== a
)
2248 next_cp
= cp
->next_second_allocno_copy
;
2249 another_a
= cp
->first
;
2253 if (! ira_reg_classes_intersect_p
[cover_class
][ALLOCNO_COVER_CLASS
2255 || ! ALLOCNO_ASSIGNED_P (another_a
)
2256 || (hard_regno
= ALLOCNO_HARD_REGNO (another_a
)) < 0)
2258 rclass
= REGNO_REG_CLASS (hard_regno
);
2259 i
= ira_class_hard_reg_index
[cover_class
][hard_regno
];
2262 cost
= (cp
->first
== a
2263 ? ira_get_register_move_cost (mode
, rclass
, cover_class
)
2264 : ira_get_register_move_cost (mode
, cover_class
, rclass
));
2265 ira_allocate_and_set_or_copy_costs
2266 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a
),
2267 cover_class
, ALLOCNO_COVER_CLASS_COST (a
),
2268 ALLOCNO_HARD_REG_COSTS (a
));
2269 ira_allocate_and_set_or_copy_costs
2270 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
),
2271 cover_class
, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a
));
2272 ALLOCNO_UPDATED_HARD_REG_COSTS (a
)[i
] -= cp
->freq
* cost
;
2273 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
)[i
] -= cp
->freq
* cost
;
2277 /* Try to assign hard registers to the unassigned allocnos and
2278 allocnos conflicting with them or conflicting with allocnos whose
2279 regno >= START_REGNO. The function is called after ira_flattening,
2280 so more allocnos (including ones created in ira-emit.c) will have a
2281 chance to get a hard register. We use simple assignment algorithm
2282 based on priorities. */
2284 ira_reassign_conflict_allocnos (int start_regno
)
2286 int i
, allocnos_to_color_num
;
2287 ira_allocno_t a
, conflict_a
;
2288 ira_allocno_conflict_iterator aci
;
2289 enum reg_class cover_class
;
2290 bitmap allocnos_to_color
;
2291 ira_allocno_iterator ai
;
2293 allocnos_to_color
= ira_allocate_bitmap ();
2294 allocnos_to_color_num
= 0;
2295 FOR_EACH_ALLOCNO (a
, ai
)
2297 if (! ALLOCNO_ASSIGNED_P (a
)
2298 && ! bitmap_bit_p (allocnos_to_color
, ALLOCNO_NUM (a
)))
2300 if (ALLOCNO_COVER_CLASS (a
) != NO_REGS
)
2301 sorted_allocnos
[allocnos_to_color_num
++] = a
;
2304 ALLOCNO_ASSIGNED_P (a
) = true;
2305 ALLOCNO_HARD_REGNO (a
) = -1;
2306 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
2307 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
2309 bitmap_set_bit (allocnos_to_color
, ALLOCNO_NUM (a
));
2311 if (ALLOCNO_REGNO (a
) < start_regno
2312 || (cover_class
= ALLOCNO_COVER_CLASS (a
)) == NO_REGS
)
2314 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_a
, aci
)
2316 ira_assert (ira_reg_classes_intersect_p
2317 [cover_class
][ALLOCNO_COVER_CLASS (conflict_a
)]);
2318 if (bitmap_bit_p (allocnos_to_color
, ALLOCNO_NUM (conflict_a
)))
2320 bitmap_set_bit (allocnos_to_color
, ALLOCNO_NUM (conflict_a
));
2321 sorted_allocnos
[allocnos_to_color_num
++] = conflict_a
;
2324 ira_free_bitmap (allocnos_to_color
);
2325 if (allocnos_to_color_num
> 1)
2327 setup_allocno_priorities (sorted_allocnos
, allocnos_to_color_num
);
2328 qsort (sorted_allocnos
, allocnos_to_color_num
, sizeof (ira_allocno_t
),
2329 allocno_priority_compare_func
);
2331 for (i
= 0; i
< allocnos_to_color_num
; i
++)
2333 a
= sorted_allocnos
[i
];
2334 ALLOCNO_ASSIGNED_P (a
) = false;
2335 update_curr_costs (a
);
2337 for (i
= 0; i
< allocnos_to_color_num
; i
++)
2339 a
= sorted_allocnos
[i
];
2340 if (assign_hard_reg (a
, true))
2342 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2345 " Secondary allocation: assign hard reg %d to reg %d\n",
2346 ALLOCNO_HARD_REGNO (a
), ALLOCNO_REGNO (a
));
2353 /* This page contains code to coalesce memory stack slots used by
2354 spilled allocnos. This results in smaller stack frame, better data
2355 locality, and in smaller code for some architectures like
2356 x86/x86_64 where insn size depends on address displacement value.
2357 On the other hand, it can worsen insn scheduling after the RA but
2358 in practice it is less important than smaller stack frames. */
2360 /* Usage cost and order number of coalesced allocno set to which
2361 given pseudo register belongs to. */
2362 static int *regno_coalesced_allocno_cost
;
2363 static int *regno_coalesced_allocno_num
;
2365 /* Sort pseudos according frequencies of coalesced allocno sets they
2366 belong to (putting most frequently ones first), and according to
2367 coalesced allocno set order numbers. */
2369 coalesced_pseudo_reg_freq_compare (const void *v1p
, const void *v2p
)
2371 const int regno1
= *(const int *) v1p
;
2372 const int regno2
= *(const int *) v2p
;
2375 if ((diff
= (regno_coalesced_allocno_cost
[regno2
]
2376 - regno_coalesced_allocno_cost
[regno1
])) != 0)
2378 if ((diff
= (regno_coalesced_allocno_num
[regno1
]
2379 - regno_coalesced_allocno_num
[regno2
])) != 0)
2381 return regno1
- regno2
;
2384 /* Widest width in which each pseudo reg is referred to (via subreg).
2385 It is used for sorting pseudo registers. */
2386 static unsigned int *regno_max_ref_width
;
2388 /* Redefine STACK_GROWS_DOWNWARD in terms of 0 or 1. */
2389 #ifdef STACK_GROWS_DOWNWARD
2390 # undef STACK_GROWS_DOWNWARD
2391 # define STACK_GROWS_DOWNWARD 1
2393 # define STACK_GROWS_DOWNWARD 0
2396 /* Sort pseudos according their slot numbers (putting ones with
2397 smaller numbers first, or last when the frame pointer is not
2400 coalesced_pseudo_reg_slot_compare (const void *v1p
, const void *v2p
)
2402 const int regno1
= *(const int *) v1p
;
2403 const int regno2
= *(const int *) v2p
;
2404 ira_allocno_t a1
= ira_regno_allocno_map
[regno1
];
2405 ira_allocno_t a2
= ira_regno_allocno_map
[regno2
];
2406 int diff
, slot_num1
, slot_num2
;
2407 int total_size1
, total_size2
;
2409 if (a1
== NULL
|| ALLOCNO_HARD_REGNO (a1
) >= 0)
2411 if (a2
== NULL
|| ALLOCNO_HARD_REGNO (a2
) >= 0)
2412 return regno1
- regno2
;
2415 else if (a2
== NULL
|| ALLOCNO_HARD_REGNO (a2
) >= 0)
2417 slot_num1
= -ALLOCNO_HARD_REGNO (a1
);
2418 slot_num2
= -ALLOCNO_HARD_REGNO (a2
);
2419 if ((diff
= slot_num1
- slot_num2
) != 0)
2420 return (frame_pointer_needed
2421 || !FRAME_GROWS_DOWNWARD
== STACK_GROWS_DOWNWARD
? diff
: -diff
);
2422 total_size1
= MAX (PSEUDO_REGNO_BYTES (regno1
), regno_max_ref_width
[regno1
]);
2423 total_size2
= MAX (PSEUDO_REGNO_BYTES (regno2
), regno_max_ref_width
[regno2
]);
2424 if ((diff
= total_size2
- total_size1
) != 0)
2426 return regno1
- regno2
;
2429 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
2430 for coalesced allocno sets containing allocnos with their regnos
2431 given in array PSEUDO_REGNOS of length N. */
2433 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos
, int n
)
2435 int i
, num
, regno
, cost
;
2436 ira_allocno_t allocno
, a
;
2438 for (num
= i
= 0; i
< n
; i
++)
2440 regno
= pseudo_regnos
[i
];
2441 allocno
= ira_regno_allocno_map
[regno
];
2442 if (allocno
== NULL
)
2444 regno_coalesced_allocno_cost
[regno
] = 0;
2445 regno_coalesced_allocno_num
[regno
] = ++num
;
2448 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) != allocno
)
2451 for (cost
= 0, a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
2452 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
2454 cost
+= ALLOCNO_FREQ (a
);
2458 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
2459 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
2461 regno_coalesced_allocno_num
[ALLOCNO_REGNO (a
)] = num
;
2462 regno_coalesced_allocno_cost
[ALLOCNO_REGNO (a
)] = cost
;
2469 /* Collect spilled allocnos representing coalesced allocno sets (the
2470 first coalesced allocno). The collected allocnos are returned
2471 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
2472 number of the collected allocnos. The allocnos are given by their
2473 regnos in array PSEUDO_REGNOS of length N. */
2475 collect_spilled_coalesced_allocnos (int *pseudo_regnos
, int n
,
2476 ira_allocno_t
*spilled_coalesced_allocnos
)
2479 ira_allocno_t allocno
;
2481 for (num
= i
= 0; i
< n
; i
++)
2483 regno
= pseudo_regnos
[i
];
2484 allocno
= ira_regno_allocno_map
[regno
];
2485 if (allocno
== NULL
|| ALLOCNO_HARD_REGNO (allocno
) >= 0
2486 || ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) != allocno
)
2488 spilled_coalesced_allocnos
[num
++] = allocno
;
2493 /* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
2494 given slot contains live ranges of coalesced allocnos assigned to
2496 static live_range_t
*slot_coalesced_allocnos_live_ranges
;
2498 /* Return TRUE if coalesced allocnos represented by ALLOCNO has live
2499 ranges intersected with live ranges of coalesced allocnos assigned
2500 to slot with number N. */
2502 slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno
, int n
)
2506 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
2507 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
2509 if (ira_allocno_live_ranges_intersect_p
2510 (slot_coalesced_allocnos_live_ranges
[n
], ALLOCNO_LIVE_RANGES (a
)))
2518 /* Update live ranges of slot to which coalesced allocnos represented
2519 by ALLOCNO were assigned. */
2521 setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno
)
2527 n
= ALLOCNO_TEMP (allocno
);
2528 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
2529 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
2531 r
= ira_copy_allocno_live_range_list (ALLOCNO_LIVE_RANGES (a
));
2532 slot_coalesced_allocnos_live_ranges
[n
]
2533 = ira_merge_allocno_live_ranges
2534 (slot_coalesced_allocnos_live_ranges
[n
], r
);
2540 /* We have coalesced allocnos involving in copies. Coalesce allocnos
2541 further in order to share the same memory stack slot. Allocnos
2542 representing sets of allocnos coalesced before the call are given
2543 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
2544 some allocnos were coalesced in the function. */
2546 coalesce_spill_slots (ira_allocno_t
*spilled_coalesced_allocnos
, int num
)
2548 int i
, j
, n
, last_coalesced_allocno_num
;
2549 ira_allocno_t allocno
, a
;
2550 bool merged_p
= false;
2551 bitmap set_jump_crosses
= regstat_get_setjmp_crosses ();
2553 slot_coalesced_allocnos_live_ranges
2554 = (live_range_t
*) ira_allocate (sizeof (live_range_t
) * ira_allocnos_num
);
2555 memset (slot_coalesced_allocnos_live_ranges
, 0,
2556 sizeof (live_range_t
) * ira_allocnos_num
);
2557 last_coalesced_allocno_num
= 0;
2558 /* Coalesce non-conflicting spilled allocnos preferring most
2560 for (i
= 0; i
< num
; i
++)
2562 allocno
= spilled_coalesced_allocnos
[i
];
2563 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) != allocno
2564 || bitmap_bit_p (set_jump_crosses
, ALLOCNO_REGNO (allocno
))
2565 || (ALLOCNO_REGNO (allocno
) < ira_reg_equiv_len
2566 && (ira_reg_equiv_const
[ALLOCNO_REGNO (allocno
)] != NULL_RTX
2567 || ira_reg_equiv_invariant_p
[ALLOCNO_REGNO (allocno
)])))
2569 for (j
= 0; j
< i
; j
++)
2571 a
= spilled_coalesced_allocnos
[j
];
2572 n
= ALLOCNO_TEMP (a
);
2573 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) == a
2574 && ! bitmap_bit_p (set_jump_crosses
, ALLOCNO_REGNO (a
))
2575 && (ALLOCNO_REGNO (a
) >= ira_reg_equiv_len
2576 || (! ira_reg_equiv_invariant_p
[ALLOCNO_REGNO (a
)]
2577 && ira_reg_equiv_const
[ALLOCNO_REGNO (a
)] == NULL_RTX
))
2578 && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno
, n
))
2583 /* No coalescing: set up number for coalesced allocnos
2584 represented by ALLOCNO. */
2585 ALLOCNO_TEMP (allocno
) = last_coalesced_allocno_num
++;
2586 setup_slot_coalesced_allocno_live_ranges (allocno
);
2590 allocno_coalesced_p
= true;
2592 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2593 fprintf (ira_dump_file
,
2594 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
2595 ALLOCNO_NUM (allocno
), ALLOCNO_REGNO (allocno
),
2596 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
2597 ALLOCNO_TEMP (allocno
) = ALLOCNO_TEMP (a
);
2598 setup_slot_coalesced_allocno_live_ranges (allocno
);
2599 merge_allocnos (a
, allocno
);
2600 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) == a
);
2603 for (i
= 0; i
< ira_allocnos_num
; i
++)
2604 ira_finish_allocno_live_range_list
2605 (slot_coalesced_allocnos_live_ranges
[i
]);
2606 ira_free (slot_coalesced_allocnos_live_ranges
);
2610 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
2611 subsequent assigning stack slots to them in the reload pass. To do
2612 this we coalesce spilled allocnos first to decrease the number of
2613 memory-memory move insns. This function is called by the
2616 ira_sort_regnos_for_alter_reg (int *pseudo_regnos
, int n
,
2617 unsigned int *reg_max_ref_width
)
2619 int max_regno
= max_reg_num ();
2620 int i
, regno
, num
, slot_num
;
2621 ira_allocno_t allocno
, a
;
2622 ira_allocno_iterator ai
;
2623 ira_allocno_t
*spilled_coalesced_allocnos
;
2625 processed_coalesced_allocno_bitmap
= ira_allocate_bitmap ();
2626 /* Set up allocnos can be coalesced. */
2627 coloring_allocno_bitmap
= ira_allocate_bitmap ();
2628 for (i
= 0; i
< n
; i
++)
2630 regno
= pseudo_regnos
[i
];
2631 allocno
= ira_regno_allocno_map
[regno
];
2632 if (allocno
!= NULL
)
2633 bitmap_set_bit (coloring_allocno_bitmap
,
2634 ALLOCNO_NUM (allocno
));
2636 allocno_coalesced_p
= false;
2637 coalesce_allocnos (true);
2638 ira_free_bitmap (coloring_allocno_bitmap
);
2639 regno_coalesced_allocno_cost
2640 = (int *) ira_allocate (max_regno
* sizeof (int));
2641 regno_coalesced_allocno_num
2642 = (int *) ira_allocate (max_regno
* sizeof (int));
2643 memset (regno_coalesced_allocno_num
, 0, max_regno
* sizeof (int));
2644 setup_coalesced_allocno_costs_and_nums (pseudo_regnos
, n
);
2645 /* Sort regnos according frequencies of the corresponding coalesced
2647 qsort (pseudo_regnos
, n
, sizeof (int), coalesced_pseudo_reg_freq_compare
);
2648 spilled_coalesced_allocnos
2649 = (ira_allocno_t
*) ira_allocate (ira_allocnos_num
2650 * sizeof (ira_allocno_t
));
2651 /* Collect allocnos representing the spilled coalesced allocno
2653 num
= collect_spilled_coalesced_allocnos (pseudo_regnos
, n
,
2654 spilled_coalesced_allocnos
);
2655 if (flag_ira_share_spill_slots
2656 && coalesce_spill_slots (spilled_coalesced_allocnos
, num
))
2658 setup_coalesced_allocno_costs_and_nums (pseudo_regnos
, n
);
2659 qsort (pseudo_regnos
, n
, sizeof (int),
2660 coalesced_pseudo_reg_freq_compare
);
2661 num
= collect_spilled_coalesced_allocnos (pseudo_regnos
, n
,
2662 spilled_coalesced_allocnos
);
2664 ira_free_bitmap (processed_coalesced_allocno_bitmap
);
2665 allocno_coalesced_p
= false;
2666 /* Assign stack slot numbers to spilled allocno sets, use smaller
2667 numbers for most frequently used coalesced allocnos. -1 is
2668 reserved for dynamic search of stack slots for pseudos spilled by
2671 for (i
= 0; i
< num
; i
++)
2673 allocno
= spilled_coalesced_allocnos
[i
];
2674 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) != allocno
2675 || ALLOCNO_HARD_REGNO (allocno
) >= 0
2676 || (ALLOCNO_REGNO (allocno
) < ira_reg_equiv_len
2677 && (ira_reg_equiv_const
[ALLOCNO_REGNO (allocno
)] != NULL_RTX
2678 || ira_reg_equiv_invariant_p
[ALLOCNO_REGNO (allocno
)])))
2680 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2681 fprintf (ira_dump_file
, " Slot %d (freq,size):", slot_num
);
2683 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
2684 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
2686 ira_assert (ALLOCNO_HARD_REGNO (a
) < 0);
2687 ALLOCNO_HARD_REGNO (a
) = -slot_num
;
2688 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2689 fprintf (ira_dump_file
, " a%dr%d(%d,%d)",
2690 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
), ALLOCNO_FREQ (a
),
2691 MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a
)),
2692 reg_max_ref_width
[ALLOCNO_REGNO (a
)]));
2697 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2698 fprintf (ira_dump_file
, "\n");
2700 ira_spilled_reg_stack_slots_num
= slot_num
- 1;
2701 ira_free (spilled_coalesced_allocnos
);
2702 /* Sort regnos according the slot numbers. */
2703 regno_max_ref_width
= reg_max_ref_width
;
2704 qsort (pseudo_regnos
, n
, sizeof (int), coalesced_pseudo_reg_slot_compare
);
2705 /* Uncoalesce allocnos which is necessary for (re)assigning during
2707 FOR_EACH_ALLOCNO (a
, ai
)
2709 ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) = a
;
2710 ALLOCNO_NEXT_COALESCED_ALLOCNO (a
) = a
;
2712 ira_free (regno_coalesced_allocno_num
);
2713 ira_free (regno_coalesced_allocno_cost
);
2718 /* This page contains code used by the reload pass to improve the
2721 /* The function is called from reload to mark changes in the
2722 allocation of REGNO made by the reload. Remember that reg_renumber
2723 reflects the change result. */
2725 ira_mark_allocation_change (int regno
)
2727 ira_allocno_t a
= ira_regno_allocno_map
[regno
];
2728 int old_hard_regno
, hard_regno
, cost
;
2729 enum reg_class cover_class
= ALLOCNO_COVER_CLASS (a
);
2731 ira_assert (a
!= NULL
);
2732 hard_regno
= reg_renumber
[regno
];
2733 if ((old_hard_regno
= ALLOCNO_HARD_REGNO (a
)) == hard_regno
)
2735 if (old_hard_regno
< 0)
2736 cost
= -ALLOCNO_MEMORY_COST (a
);
2739 ira_assert (ira_class_hard_reg_index
[cover_class
][old_hard_regno
] >= 0);
2740 cost
= -(ALLOCNO_HARD_REG_COSTS (a
) == NULL
2741 ? ALLOCNO_COVER_CLASS_COST (a
)
2742 : ALLOCNO_HARD_REG_COSTS (a
)
2743 [ira_class_hard_reg_index
[cover_class
][old_hard_regno
]]);
2744 update_copy_costs (a
, false);
2746 ira_overall_cost
-= cost
;
2747 ALLOCNO_HARD_REGNO (a
) = hard_regno
;
2750 ALLOCNO_HARD_REGNO (a
) = -1;
2751 cost
+= ALLOCNO_MEMORY_COST (a
);
2753 else if (ira_class_hard_reg_index
[cover_class
][hard_regno
] >= 0)
2755 cost
+= (ALLOCNO_HARD_REG_COSTS (a
) == NULL
2756 ? ALLOCNO_COVER_CLASS_COST (a
)
2757 : ALLOCNO_HARD_REG_COSTS (a
)
2758 [ira_class_hard_reg_index
[cover_class
][hard_regno
]]);
2759 update_copy_costs (a
, true);
2762 /* Reload changed class of the allocno. */
2764 ira_overall_cost
+= cost
;
2767 /* This function is called when reload deletes memory-memory move. In
2768 this case we marks that the allocation of the corresponding
2769 allocnos should be not changed in future. Otherwise we risk to get
2772 ira_mark_memory_move_deletion (int dst_regno
, int src_regno
)
2774 ira_allocno_t dst
= ira_regno_allocno_map
[dst_regno
];
2775 ira_allocno_t src
= ira_regno_allocno_map
[src_regno
];
2777 ira_assert (dst
!= NULL
&& src
!= NULL
2778 && ALLOCNO_HARD_REGNO (dst
) < 0
2779 && ALLOCNO_HARD_REGNO (src
) < 0);
2780 ALLOCNO_DONT_REASSIGN_P (dst
) = true;
2781 ALLOCNO_DONT_REASSIGN_P (src
) = true;
2784 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
2785 allocno A and return TRUE in the case of success. */
2787 allocno_reload_assign (ira_allocno_t a
, HARD_REG_SET forbidden_regs
)
2790 enum reg_class cover_class
;
2791 int regno
= ALLOCNO_REGNO (a
);
2794 COPY_HARD_REG_SET (saved
, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
2795 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
), forbidden_regs
);
2796 if (! flag_caller_saves
&& ALLOCNO_CALLS_CROSSED_NUM (a
) != 0)
2797 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
), call_used_reg_set
);
2798 ALLOCNO_ASSIGNED_P (a
) = false;
2799 cover_class
= ALLOCNO_COVER_CLASS (a
);
2800 update_curr_costs (a
);
2801 assign_hard_reg (a
, true);
2802 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2803 reg_renumber
[regno
] = hard_regno
;
2805 ALLOCNO_HARD_REGNO (a
) = -1;
2808 ira_assert (ira_class_hard_reg_index
[cover_class
][hard_regno
] >= 0);
2809 ira_overall_cost
-= (ALLOCNO_MEMORY_COST (a
)
2810 - (ALLOCNO_HARD_REG_COSTS (a
) == NULL
2811 ? ALLOCNO_COVER_CLASS_COST (a
)
2812 : ALLOCNO_HARD_REG_COSTS (a
)
2813 [ira_class_hard_reg_index
2814 [cover_class
][hard_regno
]]));
2815 if (ALLOCNO_CALLS_CROSSED_NUM (a
) != 0
2816 && ! ira_hard_reg_not_in_set_p (hard_regno
, ALLOCNO_MODE (a
),
2819 ira_assert (flag_caller_saves
);
2820 caller_save_needed
= 1;
2824 /* If we found a hard register, modify the RTL for the pseudo
2825 register to show the hard register, and mark the pseudo register
2827 if (reg_renumber
[regno
] >= 0)
2829 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2830 fprintf (ira_dump_file
, ": reassign to %d\n", reg_renumber
[regno
]);
2831 SET_REGNO (regno_reg_rtx
[regno
], reg_renumber
[regno
]);
2832 mark_home_live (regno
);
2834 else if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2835 fprintf (ira_dump_file
, "\n");
2836 COPY_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
), saved
);
2837 return reg_renumber
[regno
] >= 0;
2840 /* Sort pseudos according their usage frequencies (putting most
2841 frequently ones first). */
2843 pseudo_reg_compare (const void *v1p
, const void *v2p
)
2845 int regno1
= *(const int *) v1p
;
2846 int regno2
= *(const int *) v2p
;
2849 if ((diff
= REG_FREQ (regno2
) - REG_FREQ (regno1
)) != 0)
2851 return regno1
- regno2
;
2854 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
2855 NUM of them) or spilled pseudos conflicting with pseudos in
2856 SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
2857 allocation has been changed. The function doesn't use
2858 BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
2859 PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
2860 is called by the reload pass at the end of each reload
2863 ira_reassign_pseudos (int *spilled_pseudo_regs
, int num
,
2864 HARD_REG_SET bad_spill_regs
,
2865 HARD_REG_SET
*pseudo_forbidden_regs
,
2866 HARD_REG_SET
*pseudo_previous_regs
,
2871 ira_allocno_t a
, conflict_a
;
2872 HARD_REG_SET forbidden_regs
;
2873 ira_allocno_conflict_iterator aci
;
2874 bitmap temp
= BITMAP_ALLOC (NULL
);
2876 /* Add pseudos which conflict with pseudos already in
2877 SPILLED_PSEUDO_REGS to SPILLED_PSEUDO_REGS. This is preferable
2878 to allocating in two steps as some of the conflicts might have
2879 a higher priority than the pseudos passed in SPILLED_PSEUDO_REGS. */
2880 for (i
= 0; i
< num
; i
++)
2881 bitmap_set_bit (temp
, spilled_pseudo_regs
[i
]);
2883 for (i
= 0, n
= num
; i
< n
; i
++)
2885 int regno
= spilled_pseudo_regs
[i
];
2886 bitmap_set_bit (temp
, regno
);
2888 a
= ira_regno_allocno_map
[regno
];
2889 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_a
, aci
)
2890 if (ALLOCNO_HARD_REGNO (conflict_a
) < 0
2891 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a
)
2892 && ! bitmap_bit_p (temp
, ALLOCNO_REGNO (conflict_a
)))
2894 spilled_pseudo_regs
[num
++] = ALLOCNO_REGNO (conflict_a
);
2895 bitmap_set_bit (temp
, ALLOCNO_REGNO (conflict_a
));
2896 /* ?!? This seems wrong. */
2897 bitmap_set_bit (consideration_allocno_bitmap
,
2898 ALLOCNO_NUM (conflict_a
));
2903 qsort (spilled_pseudo_regs
, num
, sizeof (int), pseudo_reg_compare
);
2905 /* Try to assign hard registers to pseudos from
2906 SPILLED_PSEUDO_REGS. */
2907 for (i
= 0; i
< num
; i
++)
2909 regno
= spilled_pseudo_regs
[i
];
2910 COPY_HARD_REG_SET (forbidden_regs
, bad_spill_regs
);
2911 IOR_HARD_REG_SET (forbidden_regs
, pseudo_forbidden_regs
[regno
]);
2912 IOR_HARD_REG_SET (forbidden_regs
, pseudo_previous_regs
[regno
]);
2913 gcc_assert (reg_renumber
[regno
] < 0);
2914 a
= ira_regno_allocno_map
[regno
];
2915 ira_mark_allocation_change (regno
);
2916 ira_assert (reg_renumber
[regno
] < 0);
2917 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2918 fprintf (ira_dump_file
,
2919 " Try Assign %d(a%d), cost=%d", regno
, ALLOCNO_NUM (a
),
2920 ALLOCNO_MEMORY_COST (a
)
2921 - ALLOCNO_COVER_CLASS_COST (a
));
2922 allocno_reload_assign (a
, forbidden_regs
);
2923 if (reg_renumber
[regno
] >= 0)
2925 CLEAR_REGNO_REG_SET (spilled
, regno
);
2933 /* The function is called by reload and returns already allocated
2934 stack slot (if any) for REGNO with given INHERENT_SIZE and
2935 TOTAL_SIZE. In the case of failure to find a slot which can be
2936 used for REGNO, the function returns NULL. */
2938 ira_reuse_stack_slot (int regno
, unsigned int inherent_size
,
2939 unsigned int total_size
)
2942 int slot_num
, best_slot_num
;
2943 int cost
, best_cost
;
2944 ira_copy_t cp
, next_cp
;
2945 ira_allocno_t another_allocno
, allocno
= ira_regno_allocno_map
[regno
];
2948 struct ira_spilled_reg_stack_slot
*slot
= NULL
;
2950 ira_assert (inherent_size
== PSEUDO_REGNO_BYTES (regno
)
2951 && inherent_size
<= total_size
2952 && ALLOCNO_HARD_REGNO (allocno
) < 0);
2953 if (! flag_ira_share_spill_slots
)
2955 slot_num
= -ALLOCNO_HARD_REGNO (allocno
) - 2;
2958 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
2963 best_cost
= best_slot_num
= -1;
2965 /* It means that the pseudo was spilled in the reload pass, try
2968 slot_num
< ira_spilled_reg_stack_slots_num
;
2971 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
2972 if (slot
->mem
== NULL_RTX
)
2974 if (slot
->width
< total_size
2975 || GET_MODE_SIZE (GET_MODE (slot
->mem
)) < inherent_size
)
2978 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
2979 FIRST_PSEUDO_REGISTER
, i
, bi
)
2981 another_allocno
= ira_regno_allocno_map
[i
];
2982 if (allocnos_have_intersected_live_ranges_p (allocno
,
2986 for (cost
= 0, cp
= ALLOCNO_COPIES (allocno
);
2990 if (cp
->first
== allocno
)
2992 next_cp
= cp
->next_first_allocno_copy
;
2993 another_allocno
= cp
->second
;
2995 else if (cp
->second
== allocno
)
2997 next_cp
= cp
->next_second_allocno_copy
;
2998 another_allocno
= cp
->first
;
3002 if (cp
->insn
== NULL_RTX
)
3004 if (bitmap_bit_p (&slot
->spilled_regs
,
3005 ALLOCNO_REGNO (another_allocno
)))
3008 if (cost
> best_cost
)
3011 best_slot_num
= slot_num
;
3018 slot_num
= best_slot_num
;
3019 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
3020 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
3022 ALLOCNO_HARD_REGNO (allocno
) = -slot_num
- 2;
3027 ira_assert (slot
->width
>= total_size
);
3028 #ifdef ENABLE_IRA_CHECKING
3029 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
3030 FIRST_PSEUDO_REGISTER
, i
, bi
)
3032 ira_assert (! pseudos_have_intersected_live_ranges_p (regno
, i
));
3035 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
3036 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
3038 fprintf (ira_dump_file
, " Assigning %d(freq=%d) slot %d of",
3039 regno
, REG_FREQ (regno
), slot_num
);
3040 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
3041 FIRST_PSEUDO_REGISTER
, i
, bi
)
3043 if ((unsigned) regno
!= i
)
3044 fprintf (ira_dump_file
, " %d", i
);
3046 fprintf (ira_dump_file
, "\n");
3052 /* This is called by reload every time a new stack slot X with
3053 TOTAL_SIZE was allocated for REGNO. We store this info for
3054 subsequent ira_reuse_stack_slot calls. */
3056 ira_mark_new_stack_slot (rtx x
, int regno
, unsigned int total_size
)
3058 struct ira_spilled_reg_stack_slot
*slot
;
3060 ira_allocno_t allocno
;
3062 ira_assert (PSEUDO_REGNO_BYTES (regno
) <= total_size
);
3063 allocno
= ira_regno_allocno_map
[regno
];
3064 slot_num
= -ALLOCNO_HARD_REGNO (allocno
) - 2;
3067 slot_num
= ira_spilled_reg_stack_slots_num
++;
3068 ALLOCNO_HARD_REGNO (allocno
) = -slot_num
- 2;
3070 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
3071 INIT_REG_SET (&slot
->spilled_regs
);
3072 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
3074 slot
->width
= total_size
;
3075 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
3076 fprintf (ira_dump_file
, " Assigning %d(freq=%d) a new slot %d\n",
3077 regno
, REG_FREQ (regno
), slot_num
);
3081 /* Return spill cost for pseudo-registers whose numbers are in array
3082 REGNOS (with a negative number as an end marker) for reload with
3083 given IN and OUT for INSN. Return also number points (through
3084 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
3085 the register pressure is high, number of references of the
3086 pseudo-registers (through NREFS), number of callee-clobbered
3087 hard-registers occupied by the pseudo-registers (through
3088 CALL_USED_COUNT), and the first hard regno occupied by the
3089 pseudo-registers (through FIRST_HARD_REGNO). */
3091 calculate_spill_cost (int *regnos
, rtx in
, rtx out
, rtx insn
,
3092 int *excess_pressure_live_length
,
3093 int *nrefs
, int *call_used_count
, int *first_hard_regno
)
3095 int i
, cost
, regno
, hard_regno
, j
, count
, saved_cost
, nregs
;
3101 for (length
= count
= cost
= i
= 0;; i
++)
3106 *nrefs
+= REG_N_REFS (regno
);
3107 hard_regno
= reg_renumber
[regno
];
3108 ira_assert (hard_regno
>= 0);
3109 a
= ira_regno_allocno_map
[regno
];
3110 length
+= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
3111 cost
+= ALLOCNO_MEMORY_COST (a
) - ALLOCNO_COVER_CLASS_COST (a
);
3112 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (a
)];
3113 for (j
= 0; j
< nregs
; j
++)
3114 if (! TEST_HARD_REG_BIT (call_used_reg_set
, hard_regno
+ j
))
3118 in_p
= in
&& REG_P (in
) && (int) REGNO (in
) == hard_regno
;
3119 out_p
= out
&& REG_P (out
) && (int) REGNO (out
) == hard_regno
;
3121 && find_regno_note (insn
, REG_DEAD
, hard_regno
) != NULL_RTX
)
3125 saved_cost
+= ira_memory_move_cost
3126 [ALLOCNO_MODE (a
)][ALLOCNO_COVER_CLASS (a
)][1];
3129 += ira_memory_move_cost
3130 [ALLOCNO_MODE (a
)][ALLOCNO_COVER_CLASS (a
)][0];
3131 cost
-= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn
)) * saved_cost
;
3134 *excess_pressure_live_length
= length
;
3135 *call_used_count
= count
;
3139 hard_regno
= reg_renumber
[regnos
[0]];
3141 *first_hard_regno
= hard_regno
;
3145 /* Return TRUE if spilling pseudo-registers whose numbers are in array
3146 REGNOS is better than spilling pseudo-registers with numbers in
3147 OTHER_REGNOS for reload with given IN and OUT for INSN. The
3148 function used by the reload pass to make better register spilling
3151 ira_better_spill_reload_regno_p (int *regnos
, int *other_regnos
,
3152 rtx in
, rtx out
, rtx insn
)
3154 int cost
, other_cost
;
3155 int length
, other_length
;
3156 int nrefs
, other_nrefs
;
3157 int call_used_count
, other_call_used_count
;
3158 int hard_regno
, other_hard_regno
;
3160 cost
= calculate_spill_cost (regnos
, in
, out
, insn
,
3161 &length
, &nrefs
, &call_used_count
, &hard_regno
);
3162 other_cost
= calculate_spill_cost (other_regnos
, in
, out
, insn
,
3163 &other_length
, &other_nrefs
,
3164 &other_call_used_count
,
3166 if (nrefs
== 0 && other_nrefs
!= 0)
3168 if (nrefs
!= 0 && other_nrefs
== 0)
3170 if (cost
!= other_cost
)
3171 return cost
< other_cost
;
3172 if (length
!= other_length
)
3173 return length
> other_length
;
3174 #ifdef REG_ALLOC_ORDER
3175 if (hard_regno
>= 0 && other_hard_regno
>= 0)
3176 return (inv_reg_alloc_order
[hard_regno
]
3177 < inv_reg_alloc_order
[other_hard_regno
]);
3179 if (call_used_count
!= other_call_used_count
)
3180 return call_used_count
> other_call_used_count
;
3187 /* Allocate and initialize data necessary for assign_hard_reg. */
3189 ira_initiate_assign (void)
3192 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
3193 * ira_allocnos_num
);
3194 consideration_allocno_bitmap
= ira_allocate_bitmap ();
3195 initiate_cost_update ();
3196 allocno_priorities
= (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
3199 /* Deallocate data used by assign_hard_reg. */
3201 ira_finish_assign (void)
3203 ira_free (sorted_allocnos
);
3204 ira_free_bitmap (consideration_allocno_bitmap
);
3205 finish_cost_update ();
3206 ira_free (allocno_priorities
);
3211 /* Entry function doing color-based register allocation. */
3215 allocno_stack_vec
= VEC_alloc (ira_allocno_t
, heap
, ira_allocnos_num
);
3216 removed_splay_allocno_vec
3217 = VEC_alloc (ira_allocno_t
, heap
, ira_allocnos_num
);
3218 memset (allocated_hardreg_p
, 0, sizeof (allocated_hardreg_p
));
3219 ira_initiate_assign ();
3221 ira_finish_assign ();
3222 VEC_free (ira_allocno_t
, heap
, removed_splay_allocno_vec
);
3223 VEC_free (ira_allocno_t
, heap
, allocno_stack_vec
);
3224 move_spill_restore ();
3229 /* This page contains a simple register allocator without usage of
3230 allocno conflicts. This is used for fast allocation for -O0. */
3232 /* Do register allocation by not using allocno conflicts. It uses
3233 only allocno live ranges. The algorithm is close to Chow's
3234 priority coloring. */
3236 fast_allocation (void)
3238 int i
, j
, k
, num
, class_size
, hard_regno
;
3240 bool no_stack_reg_p
;
3242 enum reg_class cover_class
;
3243 enum machine_mode mode
;
3245 ira_allocno_iterator ai
;
3247 HARD_REG_SET conflict_hard_regs
, *used_hard_regs
;
3249 sorted_allocnos
= (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
3250 * ira_allocnos_num
);
3252 FOR_EACH_ALLOCNO (a
, ai
)
3253 sorted_allocnos
[num
++] = a
;
3254 allocno_priorities
= (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
3255 setup_allocno_priorities (sorted_allocnos
, num
);
3256 used_hard_regs
= (HARD_REG_SET
*) ira_allocate (sizeof (HARD_REG_SET
)
3258 for (i
= 0; i
< ira_max_point
; i
++)
3259 CLEAR_HARD_REG_SET (used_hard_regs
[i
]);
3260 qsort (sorted_allocnos
, num
, sizeof (ira_allocno_t
),
3261 allocno_priority_compare_func
);
3262 for (i
= 0; i
< num
; i
++)
3264 a
= sorted_allocnos
[i
];
3265 COPY_HARD_REG_SET (conflict_hard_regs
, ALLOCNO_CONFLICT_HARD_REGS (a
));
3266 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
3267 for (j
= r
->start
; j
<= r
->finish
; j
++)
3268 IOR_HARD_REG_SET (conflict_hard_regs
, used_hard_regs
[j
]);
3269 cover_class
= ALLOCNO_COVER_CLASS (a
);
3270 ALLOCNO_ASSIGNED_P (a
) = true;
3271 ALLOCNO_HARD_REGNO (a
) = -1;
3272 if (hard_reg_set_subset_p (reg_class_contents
[cover_class
],
3273 conflict_hard_regs
))
3275 mode
= ALLOCNO_MODE (a
);
3277 no_stack_reg_p
= ALLOCNO_NO_STACK_REG_P (a
);
3279 class_size
= ira_class_hard_regs_num
[cover_class
];
3280 for (j
= 0; j
< class_size
; j
++)
3282 hard_regno
= ira_class_hard_regs
[cover_class
][j
];
3284 if (no_stack_reg_p
&& FIRST_STACK_REG
<= hard_regno
3285 && hard_regno
<= LAST_STACK_REG
)
3288 if (!ira_hard_reg_not_in_set_p (hard_regno
, mode
, conflict_hard_regs
)
3289 || (TEST_HARD_REG_BIT
3290 (prohibited_class_mode_regs
[cover_class
][mode
], hard_regno
)))
3292 ALLOCNO_HARD_REGNO (a
) = hard_regno
;
3293 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
3294 for (k
= r
->start
; k
<= r
->finish
; k
++)
3295 IOR_HARD_REG_SET (used_hard_regs
[k
],
3296 ira_reg_mode_hard_regset
[hard_regno
][mode
]);
3300 ira_free (sorted_allocnos
);
3301 ira_free (used_hard_regs
);
3302 ira_free (allocno_priorities
);
3303 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
3304 ira_print_disposition (ira_dump_file
);
3309 /* Entry function doing coloring. */
3314 ira_allocno_iterator ai
;
3316 /* Setup updated costs. */
3317 FOR_EACH_ALLOCNO (a
, ai
)
3319 ALLOCNO_UPDATED_MEMORY_COST (a
) = ALLOCNO_MEMORY_COST (a
);
3320 ALLOCNO_UPDATED_COVER_CLASS_COST (a
) = ALLOCNO_COVER_CLASS_COST (a
);
3322 if (ira_conflicts_p
)