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 for (cost
= ALLOCNO_UPDATED_COVER_CLASS_COST (a
), i
= 0;
493 costs
[i
] += a_costs
[i
];
494 full_costs
[i
] += a_costs
[i
];
499 full_costs
[i
] += cost
;
501 /* Take preferences of conflicting allocnos into account. */
502 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_allocno
, aci
)
503 /* Reload can give another class so we need to check all
505 if (retry_p
|| bitmap_bit_p (consideration_allocno_bitmap
,
506 ALLOCNO_NUM (conflict_allocno
)))
508 conflict_cover_class
= ALLOCNO_COVER_CLASS (conflict_allocno
);
509 ira_assert (ira_reg_classes_intersect_p
510 [cover_class
][conflict_cover_class
]);
511 if (allocno_coalesced_p
)
513 if (bitmap_bit_p (processed_coalesced_allocno_bitmap
,
514 ALLOCNO_NUM (conflict_allocno
)))
516 bitmap_set_bit (processed_coalesced_allocno_bitmap
,
517 ALLOCNO_NUM (conflict_allocno
));
519 if (ALLOCNO_ASSIGNED_P (conflict_allocno
))
521 if ((hard_regno
= ALLOCNO_HARD_REGNO (conflict_allocno
)) >= 0
522 && ira_class_hard_reg_index
[cover_class
][hard_regno
] >= 0)
526 ira_reg_mode_hard_regset
527 [hard_regno
][ALLOCNO_MODE (conflict_allocno
)]);
528 if (hard_reg_set_subset_p (reg_class_contents
[cover_class
],
533 else if (! ALLOCNO_MAY_BE_SPILLED_P (ALLOCNO_FIRST_COALESCED_ALLOCNO
536 ira_allocate_and_copy_costs
537 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno
),
538 conflict_cover_class
,
539 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_allocno
));
541 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno
);
542 if (conflict_costs
!= NULL
)
543 for (j
= class_size
- 1; j
>= 0; j
--)
545 hard_regno
= ira_class_hard_regs
[cover_class
][j
];
546 ira_assert (hard_regno
>= 0);
547 k
= (ira_class_hard_reg_index
548 [conflict_cover_class
][hard_regno
]);
551 full_costs
[j
] -= conflict_costs
[k
];
553 queue_update_cost (conflict_allocno
, COST_HOP_DIVISOR
);
559 /* Take into account preferences of allocnos connected by copies to
560 the conflict allocnos. */
561 update_conflict_hard_regno_costs (full_costs
, cover_class
, true);
563 /* Take preferences of allocnos connected by copies into
565 start_update_cost ();
566 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
567 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
569 queue_update_cost (a
, COST_HOP_DIVISOR
);
573 update_conflict_hard_regno_costs (full_costs
, cover_class
, false);
574 min_cost
= min_full_cost
= INT_MAX
;
575 /* We don't care about giving callee saved registers to allocnos no
576 living through calls because call clobbered registers are
577 allocated first (it is usual practice to put them first in
579 for (i
= 0; i
< class_size
; i
++)
581 hard_regno
= ira_class_hard_regs
[cover_class
][i
];
584 && FIRST_STACK_REG
<= hard_regno
&& hard_regno
<= LAST_STACK_REG
)
587 if (! ira_hard_reg_not_in_set_p (hard_regno
, mode
, conflicting_regs
)
588 || TEST_HARD_REG_BIT (prohibited_class_mode_regs
[cover_class
][mode
],
592 full_cost
= full_costs
[i
];
593 #ifndef HONOR_REG_ALLOC_ORDER
594 if (! allocated_hardreg_p
[hard_regno
]
595 && ira_hard_reg_not_in_set_p (hard_regno
, mode
, call_used_reg_set
))
596 /* We need to save/restore the hard register in
597 epilogue/prologue. Therefore we increase the cost. */
599 /* ??? If only part is call clobbered. */
600 rclass
= REGNO_REG_CLASS (hard_regno
);
601 add_cost
= (ira_memory_move_cost
[mode
][rclass
][0]
602 + ira_memory_move_cost
[mode
][rclass
][1] - 1);
604 full_cost
+= add_cost
;
609 if (min_full_cost
> full_cost
)
611 min_full_cost
= full_cost
;
612 best_hard_regno
= hard_regno
;
613 ira_assert (hard_regno
>= 0);
616 if (min_full_cost
> mem_cost
)
618 if (! retry_p
&& internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
619 fprintf (ira_dump_file
, "(memory is more profitable %d vs %d) ",
620 mem_cost
, min_full_cost
);
621 best_hard_regno
= -1;
624 if (flag_ira_algorithm
!= IRA_ALGORITHM_PRIORITY
625 && best_hard_regno
< 0
626 && ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
) != allocno
)
628 for (j
= 0, a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
629 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
631 ira_assert (! ALLOCNO_IN_GRAPH_P (a
));
632 sorted_allocnos
[j
++] = a
;
636 qsort (sorted_allocnos
, j
, sizeof (ira_allocno_t
),
637 allocno_cost_compare_func
);
638 for (i
= 0; i
< j
; i
++)
640 a
= sorted_allocnos
[i
];
641 ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) = a
;
642 ALLOCNO_NEXT_COALESCED_ALLOCNO (a
) = a
;
643 VEC_safe_push (ira_allocno_t
, heap
, allocno_stack_vec
, a
);
644 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
646 fprintf (ira_dump_file
, " Pushing");
647 print_coalesced_allocno (a
);
648 fprintf (ira_dump_file
, "\n");
653 if (best_hard_regno
>= 0)
654 allocated_hardreg_p
[best_hard_regno
] = true;
655 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
656 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
658 ALLOCNO_HARD_REGNO (a
) = best_hard_regno
;
659 ALLOCNO_ASSIGNED_P (a
) = true;
660 if (best_hard_regno
>= 0)
661 update_copy_costs (a
, true);
662 ira_assert (ALLOCNO_COVER_CLASS (a
) == cover_class
);
663 /* We don't need updated costs anymore: */
664 ira_free_allocno_updated_costs (a
);
668 return best_hard_regno
>= 0;
673 /* This page contains the allocator based on the Chaitin-Briggs algorithm. */
675 /* Bucket of allocnos that can colored currently without spilling. */
676 static ira_allocno_t colorable_allocno_bucket
;
678 /* Bucket of allocnos that might be not colored currently without
680 static ira_allocno_t uncolorable_allocno_bucket
;
682 /* Each element of the array contains the current number of allocnos
683 of given *cover* class in the uncolorable_bucket. */
684 static int uncolorable_allocnos_num
[N_REG_CLASSES
];
686 /* Return the current spill priority of allocno A. The less the
687 number, the more preferable the allocno for spilling. */
689 allocno_spill_priority (ira_allocno_t a
)
691 return (ALLOCNO_TEMP (a
)
692 / (ALLOCNO_LEFT_CONFLICTS_SIZE (a
)
693 * ira_reg_class_nregs
[ALLOCNO_COVER_CLASS (a
)][ALLOCNO_MODE (a
)]
697 /* Add ALLOCNO to bucket *BUCKET_PTR. ALLOCNO should be not in a bucket
700 add_allocno_to_bucket (ira_allocno_t allocno
, ira_allocno_t
*bucket_ptr
)
702 ira_allocno_t first_allocno
;
703 enum reg_class cover_class
;
705 if (bucket_ptr
== &uncolorable_allocno_bucket
706 && (cover_class
= ALLOCNO_COVER_CLASS (allocno
)) != NO_REGS
)
708 uncolorable_allocnos_num
[cover_class
]++;
709 ira_assert (uncolorable_allocnos_num
[cover_class
] > 0);
711 first_allocno
= *bucket_ptr
;
712 ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno
) = first_allocno
;
713 ALLOCNO_PREV_BUCKET_ALLOCNO (allocno
) = NULL
;
714 if (first_allocno
!= NULL
)
715 ALLOCNO_PREV_BUCKET_ALLOCNO (first_allocno
) = allocno
;
716 *bucket_ptr
= allocno
;
719 /* The function returns frequency and number of available hard
720 registers for allocnos coalesced with ALLOCNO. */
722 get_coalesced_allocnos_attributes (ira_allocno_t allocno
, int *freq
, int *num
)
728 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
729 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
731 *freq
+= ALLOCNO_FREQ (a
);
732 *num
+= ALLOCNO_AVAILABLE_REGS_NUM (a
);
738 /* Compare two allocnos to define which allocno should be pushed first
739 into the coloring stack. If the return is a negative number, the
740 allocno given by the first parameter will be pushed first. In this
741 case such allocno has less priority than the second one and the
742 hard register will be assigned to it after assignment to the second
743 one. As the result of such assignment order, the second allocno
744 has a better chance to get the best hard register. */
746 bucket_allocno_compare_func (const void *v1p
, const void *v2p
)
748 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
749 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
750 int diff
, a1_freq
, a2_freq
, a1_num
, a2_num
;
752 if ((diff
= (int) ALLOCNO_COVER_CLASS (a2
) - ALLOCNO_COVER_CLASS (a1
)) != 0)
754 get_coalesced_allocnos_attributes (a1
, &a1_freq
, &a1_num
);
755 get_coalesced_allocnos_attributes (a2
, &a2_freq
, &a2_num
);
756 if ((diff
= a2_num
- a1_num
) != 0)
758 else if ((diff
= a1_freq
- a2_freq
) != 0)
760 return ALLOCNO_NUM (a2
) - ALLOCNO_NUM (a1
);
763 /* Sort bucket *BUCKET_PTR and return the result through
766 sort_bucket (ira_allocno_t
*bucket_ptr
)
768 ira_allocno_t a
, head
;
771 for (n
= 0, a
= *bucket_ptr
; a
!= NULL
; a
= ALLOCNO_NEXT_BUCKET_ALLOCNO (a
))
772 sorted_allocnos
[n
++] = a
;
775 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
),
776 bucket_allocno_compare_func
);
778 for (n
--; n
>= 0; n
--)
780 a
= sorted_allocnos
[n
];
781 ALLOCNO_NEXT_BUCKET_ALLOCNO (a
) = head
;
782 ALLOCNO_PREV_BUCKET_ALLOCNO (a
) = NULL
;
784 ALLOCNO_PREV_BUCKET_ALLOCNO (head
) = a
;
790 /* Add ALLOCNO to bucket *BUCKET_PTR maintaining the order according
791 their priority. ALLOCNO should be not in a bucket before the
794 add_allocno_to_ordered_bucket (ira_allocno_t allocno
,
795 ira_allocno_t
*bucket_ptr
)
797 ira_allocno_t before
, after
;
798 enum reg_class cover_class
;
800 if (bucket_ptr
== &uncolorable_allocno_bucket
801 && (cover_class
= ALLOCNO_COVER_CLASS (allocno
)) != NO_REGS
)
803 uncolorable_allocnos_num
[cover_class
]++;
804 ira_assert (uncolorable_allocnos_num
[cover_class
] > 0);
806 for (before
= *bucket_ptr
, after
= NULL
;
808 after
= before
, before
= ALLOCNO_NEXT_BUCKET_ALLOCNO (before
))
809 if (bucket_allocno_compare_func (&allocno
, &before
) < 0)
811 ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno
) = before
;
812 ALLOCNO_PREV_BUCKET_ALLOCNO (allocno
) = after
;
814 *bucket_ptr
= allocno
;
816 ALLOCNO_NEXT_BUCKET_ALLOCNO (after
) = allocno
;
818 ALLOCNO_PREV_BUCKET_ALLOCNO (before
) = allocno
;
821 /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
824 delete_allocno_from_bucket (ira_allocno_t allocno
, ira_allocno_t
*bucket_ptr
)
826 ira_allocno_t prev_allocno
, next_allocno
;
827 enum reg_class cover_class
;
829 if (bucket_ptr
== &uncolorable_allocno_bucket
830 && (cover_class
= ALLOCNO_COVER_CLASS (allocno
)) != NO_REGS
)
832 uncolorable_allocnos_num
[cover_class
]--;
833 ira_assert (uncolorable_allocnos_num
[cover_class
] >= 0);
835 prev_allocno
= ALLOCNO_PREV_BUCKET_ALLOCNO (allocno
);
836 next_allocno
= ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno
);
837 if (prev_allocno
!= NULL
)
838 ALLOCNO_NEXT_BUCKET_ALLOCNO (prev_allocno
) = next_allocno
;
841 ira_assert (*bucket_ptr
== allocno
);
842 *bucket_ptr
= next_allocno
;
844 if (next_allocno
!= NULL
)
845 ALLOCNO_PREV_BUCKET_ALLOCNO (next_allocno
) = prev_allocno
;
848 /* Splay tree for each cover class. The trees are indexed by the
849 corresponding cover classes. Splay trees contain uncolorable
851 static splay_tree uncolorable_allocnos_splay_tree
[N_REG_CLASSES
];
853 /* If the following macro is TRUE, splay tree is used to choose an
854 allocno of the corresponding cover class for spilling. When the
855 number uncolorable allocnos of given cover class decreases to some
856 threshold, linear array search is used to find the best allocno for
857 spilling. This threshold is actually pretty big because, although
858 splay trees asymptotically is much faster, each splay tree
859 operation is sufficiently costly especially taking cache locality
861 #define USE_SPLAY_P(CLASS) (uncolorable_allocnos_num[CLASS] > 4000)
863 /* Put ALLOCNO onto the coloring stack without removing it from its
864 bucket. Pushing allocno to the coloring stack can result in moving
865 conflicting allocnos from the uncolorable bucket to the colorable
868 push_allocno_to_stack (ira_allocno_t allocno
)
870 int left_conflicts_size
, conflict_size
, size
;
871 ira_allocno_t a
, conflict_allocno
;
872 enum reg_class cover_class
;
873 ira_allocno_conflict_iterator aci
;
875 ALLOCNO_IN_GRAPH_P (allocno
) = false;
876 VEC_safe_push (ira_allocno_t
, heap
, allocno_stack_vec
, allocno
);
877 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
878 if (cover_class
== NO_REGS
)
880 size
= ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE (allocno
)];
881 if (allocno_coalesced_p
)
882 bitmap_clear (processed_coalesced_allocno_bitmap
);
883 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
884 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
886 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_allocno
, aci
)
888 conflict_allocno
= ALLOCNO_FIRST_COALESCED_ALLOCNO (conflict_allocno
);
889 if (bitmap_bit_p (coloring_allocno_bitmap
,
890 ALLOCNO_NUM (conflict_allocno
)))
892 ira_assert (cover_class
893 == ALLOCNO_COVER_CLASS (conflict_allocno
));
894 if (allocno_coalesced_p
)
896 if (bitmap_bit_p (processed_coalesced_allocno_bitmap
,
897 ALLOCNO_NUM (conflict_allocno
)))
899 bitmap_set_bit (processed_coalesced_allocno_bitmap
,
900 ALLOCNO_NUM (conflict_allocno
));
902 if (ALLOCNO_IN_GRAPH_P (conflict_allocno
)
903 && ! ALLOCNO_ASSIGNED_P (conflict_allocno
))
906 = ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno
);
908 = (ira_reg_class_nregs
909 [cover_class
][ALLOCNO_MODE (conflict_allocno
)]);
911 (ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno
) >= size
);
912 if (left_conflicts_size
+ conflict_size
913 <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno
))
915 ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno
) -= size
;
919 = ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno
) - size
;
920 if (uncolorable_allocnos_splay_tree
[cover_class
] != NULL
921 && !ALLOCNO_SPLAY_REMOVED_P (conflict_allocno
)
922 && USE_SPLAY_P (cover_class
))
926 (uncolorable_allocnos_splay_tree
[cover_class
],
927 (splay_tree_key
) conflict_allocno
) != NULL
);
929 (uncolorable_allocnos_splay_tree
[cover_class
],
930 (splay_tree_key
) conflict_allocno
);
931 ALLOCNO_SPLAY_REMOVED_P (conflict_allocno
) = true;
932 VEC_safe_push (ira_allocno_t
, heap
,
933 removed_splay_allocno_vec
,
936 ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno
)
937 = left_conflicts_size
;
938 if (left_conflicts_size
+ conflict_size
939 <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno
))
941 delete_allocno_from_bucket
942 (conflict_allocno
, &uncolorable_allocno_bucket
);
943 add_allocno_to_ordered_bucket
944 (conflict_allocno
, &colorable_allocno_bucket
);
954 /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
955 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
957 remove_allocno_from_bucket_and_push (ira_allocno_t allocno
, bool colorable_p
)
959 enum reg_class cover_class
;
962 delete_allocno_from_bucket (allocno
, &colorable_allocno_bucket
);
964 delete_allocno_from_bucket (allocno
, &uncolorable_allocno_bucket
);
965 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
967 fprintf (ira_dump_file
, " Pushing");
968 print_coalesced_allocno (allocno
);
970 fprintf (ira_dump_file
, "\n");
972 fprintf (ira_dump_file
, "(potential spill: %spri=%d, cost=%d)\n",
973 ALLOCNO_BAD_SPILL_P (allocno
) ? "bad spill, " : "",
974 allocno_spill_priority (allocno
), ALLOCNO_TEMP (allocno
));
976 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
977 ira_assert ((colorable_p
978 && (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno
)
979 + ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE (allocno
)]
980 <= ALLOCNO_AVAILABLE_REGS_NUM (allocno
)))
982 && (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno
)
983 + ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE
985 > ALLOCNO_AVAILABLE_REGS_NUM (allocno
))));
987 ALLOCNO_MAY_BE_SPILLED_P (allocno
) = true;
988 push_allocno_to_stack (allocno
);
991 /* Put all allocnos from colorable bucket onto the coloring stack. */
993 push_only_colorable (void)
995 sort_bucket (&colorable_allocno_bucket
);
996 for (;colorable_allocno_bucket
!= NULL
;)
997 remove_allocno_from_bucket_and_push (colorable_allocno_bucket
, true);
1000 /* Puts ALLOCNO chosen for potential spilling onto the coloring
1003 push_allocno_to_spill (ira_allocno_t allocno
)
1005 delete_allocno_from_bucket (allocno
, &uncolorable_allocno_bucket
);
1006 ALLOCNO_MAY_BE_SPILLED_P (allocno
) = true;
1007 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1008 fprintf (ira_dump_file
, " Pushing p%d(%d) (spill for NO_REGS)\n",
1009 ALLOCNO_NUM (allocno
), ALLOCNO_REGNO (allocno
));
1010 push_allocno_to_stack (allocno
);
1013 /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
1014 loop given by its LOOP_NODE. */
1016 ira_loop_edge_freq (ira_loop_tree_node_t loop_node
, int regno
, bool exit_p
)
1021 VEC (edge
, heap
) *edges
;
1023 ira_assert (loop_node
->loop
!= NULL
1024 && (regno
< 0 || regno
>= FIRST_PSEUDO_REGISTER
));
1028 FOR_EACH_EDGE (e
, ei
, loop_node
->loop
->header
->preds
)
1029 if (e
->src
!= loop_node
->loop
->latch
1031 || (bitmap_bit_p (DF_LR_OUT (e
->src
), regno
)
1032 && bitmap_bit_p (DF_LR_IN (e
->dest
), regno
))))
1033 freq
+= EDGE_FREQUENCY (e
);
1037 edges
= get_loop_exit_edges (loop_node
->loop
);
1038 for (i
= 0; VEC_iterate (edge
, edges
, i
, e
); i
++)
1040 || (bitmap_bit_p (DF_LR_OUT (e
->src
), regno
)
1041 && bitmap_bit_p (DF_LR_IN (e
->dest
), regno
)))
1042 freq
+= EDGE_FREQUENCY (e
);
1043 VEC_free (edge
, heap
, edges
);
1046 return REG_FREQ_FROM_EDGE_FREQ (freq
);
1049 /* Calculate and return the cost of putting allocno A into memory. */
1051 calculate_allocno_spill_cost (ira_allocno_t a
)
1054 enum machine_mode mode
;
1055 enum reg_class rclass
;
1056 ira_allocno_t parent_allocno
;
1057 ira_loop_tree_node_t parent_node
, loop_node
;
1059 regno
= ALLOCNO_REGNO (a
);
1060 cost
= ALLOCNO_UPDATED_MEMORY_COST (a
) - ALLOCNO_UPDATED_COVER_CLASS_COST (a
);
1061 if (ALLOCNO_CAP (a
) != NULL
)
1063 loop_node
= ALLOCNO_LOOP_TREE_NODE (a
);
1064 if ((parent_node
= loop_node
->parent
) == NULL
)
1066 if ((parent_allocno
= parent_node
->regno_allocno_map
[regno
]) == NULL
)
1068 mode
= ALLOCNO_MODE (a
);
1069 rclass
= ALLOCNO_COVER_CLASS (a
);
1070 if (ALLOCNO_HARD_REGNO (parent_allocno
) < 0)
1071 cost
-= (ira_memory_move_cost
[mode
][rclass
][0]
1072 * ira_loop_edge_freq (loop_node
, regno
, true)
1073 + ira_memory_move_cost
[mode
][rclass
][1]
1074 * ira_loop_edge_freq (loop_node
, regno
, false));
1076 cost
+= ((ira_memory_move_cost
[mode
][rclass
][1]
1077 * ira_loop_edge_freq (loop_node
, regno
, true)
1078 + ira_memory_move_cost
[mode
][rclass
][0]
1079 * ira_loop_edge_freq (loop_node
, regno
, false))
1080 - (ira_get_register_move_cost (mode
, rclass
, rclass
)
1081 * (ira_loop_edge_freq (loop_node
, regno
, false)
1082 + ira_loop_edge_freq (loop_node
, regno
, true))));
1086 /* Compare keys in the splay tree used to choose best allocno for
1087 spilling. The best allocno has the minimal key. */
1089 allocno_spill_priority_compare (splay_tree_key k1
, splay_tree_key k2
)
1091 int pri1
, pri2
, diff
;
1092 ira_allocno_t a1
= (ira_allocno_t
) k1
, a2
= (ira_allocno_t
) k2
;
1094 pri1
= (ALLOCNO_TEMP (a1
)
1095 / (ALLOCNO_LEFT_CONFLICTS_SIZE (a1
)
1096 * ira_reg_class_nregs
[ALLOCNO_COVER_CLASS (a1
)][ALLOCNO_MODE (a1
)]
1098 pri2
= (ALLOCNO_TEMP (a2
)
1099 / (ALLOCNO_LEFT_CONFLICTS_SIZE (a2
)
1100 * ira_reg_class_nregs
[ALLOCNO_COVER_CLASS (a2
)][ALLOCNO_MODE (a2
)]
1102 if ((diff
= pri1
- pri2
) != 0)
1104 if ((diff
= ALLOCNO_TEMP (a1
) - ALLOCNO_TEMP (a2
)) != 0)
1106 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
1109 /* Allocate data of SIZE for the splay trees. We allocate only spay
1110 tree roots or splay tree nodes. If you change this, please rewrite
1113 splay_tree_allocate (int size
, void *data ATTRIBUTE_UNUSED
)
1115 if (size
!= sizeof (struct splay_tree_node_s
))
1116 return ira_allocate (size
);
1117 return pool_alloc (splay_tree_node_pool
);
1120 /* Free data NODE for the splay trees. We allocate and free only spay
1121 tree roots or splay tree nodes. If you change this, please rewrite
1124 splay_tree_free (void *node
, void *data ATTRIBUTE_UNUSED
)
1127 enum reg_class cover_class
;
1129 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1131 cover_class
= ira_reg_class_cover
[i
];
1132 if (node
== uncolorable_allocnos_splay_tree
[cover_class
])
1138 pool_free (splay_tree_node_pool
, node
);
1141 /* Push allocnos to the coloring stack. The order of allocnos in the
1142 stack defines the order for the subsequent coloring. */
1144 push_allocnos_to_stack (void)
1146 ira_allocno_t allocno
, a
, i_allocno
, *allocno_vec
;
1147 enum reg_class cover_class
, rclass
;
1148 int allocno_pri
, i_allocno_pri
, allocno_cost
, i_allocno_cost
;
1149 int i
, j
, num
, cover_class_allocnos_num
[N_REG_CLASSES
];
1150 ira_allocno_t
*cover_class_allocnos
[N_REG_CLASSES
];
1154 VEC_truncate(ira_allocno_t
, removed_splay_allocno_vec
, 0);
1155 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1157 cover_class
= ira_reg_class_cover
[i
];
1158 cover_class_allocnos_num
[cover_class
] = 0;
1159 cover_class_allocnos
[cover_class
] = NULL
;
1160 uncolorable_allocnos_splay_tree
[cover_class
] = NULL
;
1162 /* Calculate uncolorable allocno spill costs. */
1163 for (allocno
= uncolorable_allocno_bucket
;
1165 allocno
= ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno
))
1166 if ((cover_class
= ALLOCNO_COVER_CLASS (allocno
)) != NO_REGS
)
1168 cover_class_allocnos_num
[cover_class
]++;
1170 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
1171 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1173 cost
+= calculate_allocno_spill_cost (a
);
1177 /* ??? Remove cost of copies between the coalesced
1179 ALLOCNO_TEMP (allocno
) = cost
;
1181 /* Define place where to put uncolorable allocnos of the same cover
1183 for (num
= i
= 0; i
< ira_reg_class_cover_size
; i
++)
1185 cover_class
= ira_reg_class_cover
[i
];
1186 ira_assert (cover_class_allocnos_num
[cover_class
]
1187 == uncolorable_allocnos_num
[cover_class
]);
1188 if (cover_class_allocnos_num
[cover_class
] != 0)
1190 cover_class_allocnos
[cover_class
] = allocnos_for_spilling
+ num
;
1191 num
+= cover_class_allocnos_num
[cover_class
];
1192 cover_class_allocnos_num
[cover_class
] = 0;
1194 if (USE_SPLAY_P (cover_class
))
1195 uncolorable_allocnos_splay_tree
[cover_class
]
1196 = splay_tree_new_with_allocator (allocno_spill_priority_compare
,
1197 NULL
, NULL
, splay_tree_allocate
,
1198 splay_tree_free
, NULL
);
1200 ira_assert (num
<= ira_allocnos_num
);
1201 /* Collect uncolorable allocnos of each cover class. */
1202 for (allocno
= uncolorable_allocno_bucket
;
1204 allocno
= ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno
))
1205 if ((cover_class
= ALLOCNO_COVER_CLASS (allocno
)) != NO_REGS
)
1207 cover_class_allocnos
1208 [cover_class
][cover_class_allocnos_num
[cover_class
]++] = allocno
;
1209 if (uncolorable_allocnos_splay_tree
[cover_class
] != NULL
)
1210 splay_tree_insert (uncolorable_allocnos_splay_tree
[cover_class
],
1211 (splay_tree_key
) allocno
,
1212 (splay_tree_value
) allocno
);
1216 push_only_colorable ();
1217 allocno
= uncolorable_allocno_bucket
;
1218 if (allocno
== NULL
)
1220 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
1221 if (cover_class
== NO_REGS
)
1223 push_allocno_to_spill (allocno
);
1226 /* Potential spilling. */
1228 (ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE (allocno
)] > 0);
1229 if (USE_SPLAY_P (cover_class
))
1231 for (;VEC_length (ira_allocno_t
, removed_splay_allocno_vec
) != 0;)
1233 allocno
= VEC_pop (ira_allocno_t
, removed_splay_allocno_vec
);
1234 ALLOCNO_SPLAY_REMOVED_P (allocno
) = false;
1235 rclass
= ALLOCNO_COVER_CLASS (allocno
);
1236 if (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno
)
1237 + ira_reg_class_nregs
[rclass
][ALLOCNO_MODE (allocno
)]
1238 > ALLOCNO_AVAILABLE_REGS_NUM (allocno
))
1240 (uncolorable_allocnos_splay_tree
[rclass
],
1241 (splay_tree_key
) allocno
, (splay_tree_value
) allocno
);
1243 allocno
= ((ira_allocno_t
)
1245 (uncolorable_allocnos_splay_tree
[cover_class
])->key
);
1246 splay_tree_remove (uncolorable_allocnos_splay_tree
[cover_class
],
1247 (splay_tree_key
) allocno
);
1251 num
= cover_class_allocnos_num
[cover_class
];
1252 ira_assert (num
> 0);
1253 allocno_vec
= cover_class_allocnos
[cover_class
];
1255 allocno_pri
= allocno_cost
= 0;
1256 /* Sort uncolorable allocno to find the one with the lowest
1258 for (i
= 0, j
= num
- 1; i
<= j
;)
1260 i_allocno
= allocno_vec
[i
];
1261 if (! ALLOCNO_IN_GRAPH_P (i_allocno
)
1262 && ALLOCNO_IN_GRAPH_P (allocno_vec
[j
]))
1264 i_allocno
= allocno_vec
[j
];
1265 allocno_vec
[j
] = allocno_vec
[i
];
1266 allocno_vec
[i
] = i_allocno
;
1268 if (ALLOCNO_IN_GRAPH_P (i_allocno
))
1271 ira_assert (ALLOCNO_TEMP (i_allocno
) != INT_MAX
);
1272 i_allocno_cost
= ALLOCNO_TEMP (i_allocno
);
1273 i_allocno_pri
= allocno_spill_priority (i_allocno
);
1275 || (! ALLOCNO_BAD_SPILL_P (i_allocno
)
1276 && ALLOCNO_BAD_SPILL_P (allocno
))
1277 || (! (ALLOCNO_BAD_SPILL_P (i_allocno
)
1278 && ! ALLOCNO_BAD_SPILL_P (allocno
))
1279 && (allocno_pri
> i_allocno_pri
1280 || (allocno_pri
== i_allocno_pri
1281 && (allocno_cost
> i_allocno_cost
1282 || (allocno_cost
== i_allocno_cost
1283 && (ALLOCNO_NUM (allocno
)
1284 > ALLOCNO_NUM (i_allocno
))))))))
1286 allocno
= i_allocno
;
1287 allocno_cost
= i_allocno_cost
;
1288 allocno_pri
= i_allocno_pri
;
1291 if (! ALLOCNO_IN_GRAPH_P (allocno_vec
[j
]))
1294 ira_assert (allocno
!= NULL
&& j
>= 0);
1295 cover_class_allocnos_num
[cover_class
] = j
+ 1;
1297 ira_assert (ALLOCNO_IN_GRAPH_P (allocno
)
1298 && ALLOCNO_COVER_CLASS (allocno
) == cover_class
1299 && (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno
)
1300 + ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE
1302 > ALLOCNO_AVAILABLE_REGS_NUM (allocno
)));
1303 remove_allocno_from_bucket_and_push (allocno
, false);
1305 ira_assert (colorable_allocno_bucket
== NULL
1306 && uncolorable_allocno_bucket
== NULL
);
1307 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1309 cover_class
= ira_reg_class_cover
[i
];
1310 ira_assert (uncolorable_allocnos_num
[cover_class
] == 0);
1311 if (uncolorable_allocnos_splay_tree
[cover_class
] != NULL
)
1312 splay_tree_delete (uncolorable_allocnos_splay_tree
[cover_class
]);
1316 /* Pop the coloring stack and assign hard registers to the popped
1319 pop_allocnos_from_stack (void)
1321 ira_allocno_t allocno
;
1322 enum reg_class cover_class
;
1324 for (;VEC_length (ira_allocno_t
, allocno_stack_vec
) != 0;)
1326 allocno
= VEC_pop (ira_allocno_t
, allocno_stack_vec
);
1327 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
1328 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1330 fprintf (ira_dump_file
, " Popping");
1331 print_coalesced_allocno (allocno
);
1332 fprintf (ira_dump_file
, " -- ");
1334 if (cover_class
== NO_REGS
)
1336 ALLOCNO_HARD_REGNO (allocno
) = -1;
1337 ALLOCNO_ASSIGNED_P (allocno
) = true;
1338 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno
) == NULL
);
1340 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno
) == NULL
);
1341 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1342 fprintf (ira_dump_file
, "assign memory\n");
1344 else if (assign_hard_reg (allocno
, false))
1346 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1347 fprintf (ira_dump_file
, "assign reg %d\n",
1348 ALLOCNO_HARD_REGNO (allocno
));
1350 else if (ALLOCNO_ASSIGNED_P (allocno
))
1352 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1353 fprintf (ira_dump_file
, "spill\n");
1355 ALLOCNO_IN_GRAPH_P (allocno
) = true;
1359 /* Set up number of available hard registers for ALLOCNO. */
1361 setup_allocno_available_regs_num (ira_allocno_t allocno
)
1363 int i
, n
, hard_regs_num
, hard_regno
;
1364 enum machine_mode mode
;
1365 enum reg_class cover_class
;
1367 HARD_REG_SET temp_set
;
1369 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
1370 ALLOCNO_AVAILABLE_REGS_NUM (allocno
) = ira_available_class_regs
[cover_class
];
1371 if (cover_class
== NO_REGS
)
1373 CLEAR_HARD_REG_SET (temp_set
);
1374 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) == allocno
);
1375 hard_regs_num
= ira_class_hard_regs_num
[cover_class
];
1376 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
1377 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1379 IOR_HARD_REG_SET (temp_set
, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
1383 mode
= ALLOCNO_MODE (allocno
);
1384 for (n
= 0, i
= hard_regs_num
- 1; i
>= 0; i
--)
1386 hard_regno
= ira_class_hard_regs
[cover_class
][i
];
1387 if (TEST_HARD_REG_BIT (temp_set
, hard_regno
)
1388 || TEST_HARD_REG_BIT (prohibited_class_mode_regs
[cover_class
][mode
],
1392 if (internal_flag_ira_verbose
> 2 && n
> 0 && ira_dump_file
!= NULL
)
1393 fprintf (ira_dump_file
, " Reg %d of %s has %d regs less\n",
1394 ALLOCNO_REGNO (allocno
), reg_class_names
[cover_class
], n
);
1395 ALLOCNO_AVAILABLE_REGS_NUM (allocno
) -= n
;
1398 /* Set up ALLOCNO_LEFT_CONFLICTS_SIZE for ALLOCNO. */
1400 setup_allocno_left_conflicts_size (ira_allocno_t allocno
)
1402 int i
, hard_regs_num
, hard_regno
, conflict_allocnos_size
;
1403 ira_allocno_t a
, conflict_allocno
;
1404 enum reg_class cover_class
;
1405 HARD_REG_SET temp_set
;
1406 ira_allocno_conflict_iterator aci
;
1408 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
1409 hard_regs_num
= ira_class_hard_regs_num
[cover_class
];
1410 CLEAR_HARD_REG_SET (temp_set
);
1411 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) == allocno
);
1412 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
1413 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1415 IOR_HARD_REG_SET (temp_set
, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
1419 AND_HARD_REG_SET (temp_set
, reg_class_contents
[cover_class
]);
1420 AND_COMPL_HARD_REG_SET (temp_set
, ira_no_alloc_regs
);
1421 conflict_allocnos_size
= 0;
1422 if (! hard_reg_set_empty_p (temp_set
))
1423 for (i
= 0; i
< (int) hard_regs_num
; i
++)
1425 hard_regno
= ira_class_hard_regs
[cover_class
][i
];
1426 if (TEST_HARD_REG_BIT (temp_set
, hard_regno
))
1428 conflict_allocnos_size
++;
1429 CLEAR_HARD_REG_BIT (temp_set
, hard_regno
);
1430 if (hard_reg_set_empty_p (temp_set
))
1434 CLEAR_HARD_REG_SET (temp_set
);
1435 if (allocno_coalesced_p
)
1436 bitmap_clear (processed_coalesced_allocno_bitmap
);
1437 if (cover_class
!= NO_REGS
)
1438 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
1439 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1441 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_allocno
, aci
)
1444 = ALLOCNO_FIRST_COALESCED_ALLOCNO (conflict_allocno
);
1445 if (bitmap_bit_p (consideration_allocno_bitmap
,
1446 ALLOCNO_NUM (conflict_allocno
)))
1448 ira_assert (cover_class
1449 == ALLOCNO_COVER_CLASS (conflict_allocno
));
1450 if (allocno_coalesced_p
)
1452 if (bitmap_bit_p (processed_coalesced_allocno_bitmap
,
1453 ALLOCNO_NUM (conflict_allocno
)))
1455 bitmap_set_bit (processed_coalesced_allocno_bitmap
,
1456 ALLOCNO_NUM (conflict_allocno
));
1458 if (! ALLOCNO_ASSIGNED_P (conflict_allocno
))
1459 conflict_allocnos_size
1460 += (ira_reg_class_nregs
1461 [cover_class
][ALLOCNO_MODE (conflict_allocno
)]);
1462 else if ((hard_regno
= ALLOCNO_HARD_REGNO (conflict_allocno
))
1465 int last
= (hard_regno
1467 [hard_regno
][ALLOCNO_MODE (conflict_allocno
)]);
1469 while (hard_regno
< last
)
1471 if (! TEST_HARD_REG_BIT (temp_set
, hard_regno
))
1473 conflict_allocnos_size
++;
1474 SET_HARD_REG_BIT (temp_set
, hard_regno
);
1484 ALLOCNO_LEFT_CONFLICTS_SIZE (allocno
) = conflict_allocnos_size
;
1487 /* Put ALLOCNO in a bucket corresponding to its number and size of its
1488 conflicting allocnos and hard registers. */
1490 put_allocno_into_bucket (ira_allocno_t allocno
)
1492 enum reg_class cover_class
;
1494 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
1495 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) != allocno
)
1497 ALLOCNO_IN_GRAPH_P (allocno
) = true;
1498 setup_allocno_left_conflicts_size (allocno
);
1499 setup_allocno_available_regs_num (allocno
);
1500 if (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno
)
1501 + ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE (allocno
)]
1502 <= ALLOCNO_AVAILABLE_REGS_NUM (allocno
))
1503 add_allocno_to_bucket (allocno
, &colorable_allocno_bucket
);
1505 add_allocno_to_bucket (allocno
, &uncolorable_allocno_bucket
);
1508 /* The function is used to sort allocnos according to their execution
1511 copy_freq_compare_func (const void *v1p
, const void *v2p
)
1513 ira_copy_t cp1
= *(const ira_copy_t
*) v1p
, cp2
= *(const ira_copy_t
*) v2p
;
1521 /* If freqencies are equal, sort by copies, so that the results of
1522 qsort leave nothing to chance. */
1523 return cp1
->num
- cp2
->num
;
1526 /* Merge two sets of coalesced allocnos given correspondingly by
1527 allocnos A1 and A2 (more accurately merging A2 set into A1
1530 merge_allocnos (ira_allocno_t a1
, ira_allocno_t a2
)
1532 ira_allocno_t a
, first
, last
, next
;
1534 first
= ALLOCNO_FIRST_COALESCED_ALLOCNO (a1
);
1535 if (first
== ALLOCNO_FIRST_COALESCED_ALLOCNO (a2
))
1537 for (last
= a2
, a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a2
);;
1538 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1540 ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) = first
;
1545 next
= ALLOCNO_NEXT_COALESCED_ALLOCNO (first
);
1546 ALLOCNO_NEXT_COALESCED_ALLOCNO (first
) = a2
;
1547 ALLOCNO_NEXT_COALESCED_ALLOCNO (last
) = next
;
1550 /* Return TRUE if there are conflicting allocnos from two sets of
1551 coalesced allocnos given correspondingly by allocnos A1 and A2. If
1552 RELOAD_P is TRUE, we use live ranges to find conflicts because
1553 conflicts are represented only for allocnos of the same cover class
1554 and during the reload pass we coalesce allocnos for sharing stack
1557 coalesced_allocno_conflict_p (ira_allocno_t a1
, ira_allocno_t a2
,
1560 ira_allocno_t a
, conflict_allocno
;
1561 ira_allocno_conflict_iterator aci
;
1563 if (allocno_coalesced_p
)
1565 bitmap_clear (processed_coalesced_allocno_bitmap
);
1566 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a1
);;
1567 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1569 bitmap_set_bit (processed_coalesced_allocno_bitmap
, ALLOCNO_NUM (a
));
1574 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a2
);;
1575 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1579 for (conflict_allocno
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a1
);;
1581 = ALLOCNO_NEXT_COALESCED_ALLOCNO (conflict_allocno
))
1583 if (allocnos_have_intersected_live_ranges_p (a
,
1586 if (conflict_allocno
== a1
)
1592 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_allocno
, aci
)
1593 if (conflict_allocno
== a1
1594 || (allocno_coalesced_p
1595 && bitmap_bit_p (processed_coalesced_allocno_bitmap
,
1596 ALLOCNO_NUM (conflict_allocno
))))
1605 /* The major function for aggressive allocno coalescing. For the
1606 reload pass (RELOAD_P) we coalesce only spilled allocnos. If some
1607 allocnos have been coalesced, we set up flag
1608 allocno_coalesced_p. */
1610 coalesce_allocnos (bool reload_p
)
1613 ira_copy_t cp
, next_cp
, *sorted_copies
;
1614 enum reg_class cover_class
;
1615 enum machine_mode mode
;
1617 int i
, n
, cp_num
, regno
;
1620 sorted_copies
= (ira_copy_t
*) ira_allocate (ira_copies_num
1621 * sizeof (ira_copy_t
));
1623 /* Collect copies. */
1624 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, j
, bi
)
1626 a
= ira_allocnos
[j
];
1627 regno
= ALLOCNO_REGNO (a
);
1628 if ((! reload_p
&& ALLOCNO_ASSIGNED_P (a
))
1630 && (! ALLOCNO_ASSIGNED_P (a
) || ALLOCNO_HARD_REGNO (a
) >= 0
1631 || (regno
< ira_reg_equiv_len
1632 && (ira_reg_equiv_const
[regno
] != NULL_RTX
1633 || ira_reg_equiv_invariant_p
[regno
])))))
1635 cover_class
= ALLOCNO_COVER_CLASS (a
);
1636 mode
= ALLOCNO_MODE (a
);
1637 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
1641 next_cp
= cp
->next_first_allocno_copy
;
1642 regno
= ALLOCNO_REGNO (cp
->second
);
1643 /* For priority coloring we coalesce allocnos only with
1644 the same cover class not with intersected cover
1645 classes as it were possible. It is done for
1648 || (ALLOCNO_COVER_CLASS (cp
->second
) == cover_class
1649 && ALLOCNO_MODE (cp
->second
) == mode
))
1650 && (cp
->insn
!= NULL
|| cp
->constraint_p
)
1651 && ((! reload_p
&& ! ALLOCNO_ASSIGNED_P (cp
->second
))
1653 && ALLOCNO_ASSIGNED_P (cp
->second
)
1654 && ALLOCNO_HARD_REGNO (cp
->second
) < 0
1655 && (regno
>= ira_reg_equiv_len
1656 || (! ira_reg_equiv_invariant_p
[regno
]
1657 && ira_reg_equiv_const
[regno
] == NULL_RTX
)))))
1658 sorted_copies
[cp_num
++] = cp
;
1660 else if (cp
->second
== a
)
1661 next_cp
= cp
->next_second_allocno_copy
;
1666 qsort (sorted_copies
, cp_num
, sizeof (ira_copy_t
), copy_freq_compare_func
);
1667 /* Coalesced copies, most frequently executed first. */
1668 for (; cp_num
!= 0;)
1670 for (i
= 0; i
< cp_num
; i
++)
1672 cp
= sorted_copies
[i
];
1673 if (! coalesced_allocno_conflict_p (cp
->first
, cp
->second
, reload_p
))
1675 allocno_coalesced_p
= true;
1676 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1679 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
1680 cp
->num
, ALLOCNO_NUM (cp
->first
), ALLOCNO_REGNO (cp
->first
),
1681 ALLOCNO_NUM (cp
->second
), ALLOCNO_REGNO (cp
->second
),
1683 merge_allocnos (cp
->first
, cp
->second
);
1688 /* Collect the rest of copies. */
1689 for (n
= 0; i
< cp_num
; i
++)
1691 cp
= sorted_copies
[i
];
1692 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (cp
->first
)
1693 != ALLOCNO_FIRST_COALESCED_ALLOCNO (cp
->second
))
1694 sorted_copies
[n
++] = cp
;
1698 ira_free (sorted_copies
);
1701 /* Map: allocno number -> allocno priority. */
1702 static int *allocno_priorities
;
1704 /* Set up priorities for N allocnos in array
1705 CONSIDERATION_ALLOCNOS. */
1707 setup_allocno_priorities (ira_allocno_t
*consideration_allocnos
, int n
)
1709 int i
, length
, nrefs
, priority
, max_priority
, mult
;
1713 for (i
= 0; i
< n
; i
++)
1715 a
= consideration_allocnos
[i
];
1716 nrefs
= ALLOCNO_NREFS (a
);
1717 ira_assert (nrefs
>= 0);
1718 mult
= floor_log2 (ALLOCNO_NREFS (a
)) + 1;
1719 ira_assert (mult
>= 0);
1720 allocno_priorities
[ALLOCNO_NUM (a
)]
1723 * (ALLOCNO_MEMORY_COST (a
) - ALLOCNO_COVER_CLASS_COST (a
))
1724 * ira_reg_class_nregs
[ALLOCNO_COVER_CLASS (a
)][ALLOCNO_MODE (a
)]);
1726 priority
= -priority
;
1727 if (max_priority
< priority
)
1728 max_priority
= priority
;
1730 mult
= max_priority
== 0 ? 1 : INT_MAX
/ max_priority
;
1731 for (i
= 0; i
< n
; i
++)
1733 a
= consideration_allocnos
[i
];
1734 length
= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
1737 allocno_priorities
[ALLOCNO_NUM (a
)]
1738 = allocno_priorities
[ALLOCNO_NUM (a
)] * mult
/ length
;
1742 /* Sort allocnos according to their priorities which are calculated
1743 analogous to ones in file `global.c'. */
1745 allocno_priority_compare_func (const void *v1p
, const void *v2p
)
1747 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
1748 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
1751 pri1
= allocno_priorities
[ALLOCNO_NUM (a1
)];
1752 pri2
= allocno_priorities
[ALLOCNO_NUM (a2
)];
1756 /* If regs are equally good, sort by allocnos, so that the results of
1757 qsort leave nothing to chance. */
1758 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
1761 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
1762 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
1764 color_allocnos (void)
1770 allocno_coalesced_p
= false;
1771 processed_coalesced_allocno_bitmap
= ira_allocate_bitmap ();
1772 if (flag_ira_coalesce
)
1773 coalesce_allocnos (false);
1774 if (flag_ira_algorithm
== IRA_ALGORITHM_PRIORITY
)
1777 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
1779 a
= ira_allocnos
[i
];
1780 if (ALLOCNO_COVER_CLASS (a
) == NO_REGS
)
1782 ALLOCNO_HARD_REGNO (a
) = -1;
1783 ALLOCNO_ASSIGNED_P (a
) = true;
1784 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
1785 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
1786 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1788 fprintf (ira_dump_file
, " Spill");
1789 print_coalesced_allocno (a
);
1790 fprintf (ira_dump_file
, "\n");
1794 sorted_allocnos
[n
++] = a
;
1798 setup_allocno_priorities (sorted_allocnos
, n
);
1799 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
),
1800 allocno_priority_compare_func
);
1801 for (i
= 0; i
< n
; i
++)
1803 a
= sorted_allocnos
[i
];
1804 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1806 fprintf (ira_dump_file
, " ");
1807 print_coalesced_allocno (a
);
1808 fprintf (ira_dump_file
, " -- ");
1810 if (assign_hard_reg (a
, false))
1812 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1813 fprintf (ira_dump_file
, "assign hard reg %d\n",
1814 ALLOCNO_HARD_REGNO (a
));
1818 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1819 fprintf (ira_dump_file
, "assign memory\n");
1826 /* Put the allocnos into the corresponding buckets. */
1827 colorable_allocno_bucket
= NULL
;
1828 uncolorable_allocno_bucket
= NULL
;
1829 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
1831 a
= ira_allocnos
[i
];
1832 if (ALLOCNO_COVER_CLASS (a
) == NO_REGS
)
1834 ALLOCNO_HARD_REGNO (a
) = -1;
1835 ALLOCNO_ASSIGNED_P (a
) = true;
1836 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
1837 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
1838 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1840 fprintf (ira_dump_file
, " Spill");
1841 print_coalesced_allocno (a
);
1842 fprintf (ira_dump_file
, "\n");
1846 put_allocno_into_bucket (a
);
1848 push_allocnos_to_stack ();
1849 pop_allocnos_from_stack ();
1851 if (flag_ira_coalesce
)
1852 /* We don't need coalesced allocnos for ira_reassign_pseudos. */
1853 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
1855 a
= ira_allocnos
[i
];
1856 ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) = a
;
1857 ALLOCNO_NEXT_COALESCED_ALLOCNO (a
) = a
;
1859 ira_free_bitmap (processed_coalesced_allocno_bitmap
);
1860 allocno_coalesced_p
= false;
1865 /* Output information about the loop given by its LOOP_TREE_NODE. */
1867 print_loop_title (ira_loop_tree_node_t loop_tree_node
)
1871 ira_loop_tree_node_t subloop_node
, dest_loop_node
;
1875 ira_assert (loop_tree_node
->loop
!= NULL
);
1876 fprintf (ira_dump_file
,
1877 "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
1878 loop_tree_node
->loop
->num
,
1879 (loop_tree_node
->parent
== NULL
1880 ? -1 : loop_tree_node
->parent
->loop
->num
),
1881 loop_tree_node
->loop
->header
->index
,
1882 loop_depth (loop_tree_node
->loop
));
1883 for (subloop_node
= loop_tree_node
->children
;
1884 subloop_node
!= NULL
;
1885 subloop_node
= subloop_node
->next
)
1886 if (subloop_node
->bb
!= NULL
)
1888 fprintf (ira_dump_file
, " %d", subloop_node
->bb
->index
);
1889 FOR_EACH_EDGE (e
, ei
, subloop_node
->bb
->succs
)
1890 if (e
->dest
!= EXIT_BLOCK_PTR
1891 && ((dest_loop_node
= IRA_BB_NODE (e
->dest
)->parent
)
1893 fprintf (ira_dump_file
, "(->%d:l%d)",
1894 e
->dest
->index
, dest_loop_node
->loop
->num
);
1896 fprintf (ira_dump_file
, "\n all:");
1897 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->all_allocnos
, 0, j
, bi
)
1898 fprintf (ira_dump_file
, " %dr%d", j
, ALLOCNO_REGNO (ira_allocnos
[j
]));
1899 fprintf (ira_dump_file
, "\n modified regnos:");
1900 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->modified_regnos
, 0, j
, bi
)
1901 fprintf (ira_dump_file
, " %d", j
);
1902 fprintf (ira_dump_file
, "\n border:");
1903 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->border_allocnos
, 0, j
, bi
)
1904 fprintf (ira_dump_file
, " %dr%d", j
, ALLOCNO_REGNO (ira_allocnos
[j
]));
1905 fprintf (ira_dump_file
, "\n Pressure:");
1906 for (j
= 0; (int) j
< ira_reg_class_cover_size
; j
++)
1908 enum reg_class cover_class
;
1910 cover_class
= ira_reg_class_cover
[j
];
1911 if (loop_tree_node
->reg_pressure
[cover_class
] == 0)
1913 fprintf (ira_dump_file
, " %s=%d", reg_class_names
[cover_class
],
1914 loop_tree_node
->reg_pressure
[cover_class
]);
1916 fprintf (ira_dump_file
, "\n");
1919 /* Color the allocnos inside loop (in the extreme case it can be all
1920 of the function) given the corresponding LOOP_TREE_NODE. The
1921 function is called for each loop during top-down traverse of the
1924 color_pass (ira_loop_tree_node_t loop_tree_node
)
1926 int regno
, hard_regno
, index
= -1;
1927 int cost
, exit_freq
, enter_freq
;
1930 enum machine_mode mode
;
1931 enum reg_class rclass
, cover_class
;
1932 ira_allocno_t a
, subloop_allocno
;
1933 ira_loop_tree_node_t subloop_node
;
1935 ira_assert (loop_tree_node
->bb
== NULL
);
1936 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
1937 print_loop_title (loop_tree_node
);
1939 bitmap_copy (coloring_allocno_bitmap
, loop_tree_node
->all_allocnos
);
1940 bitmap_copy (consideration_allocno_bitmap
, coloring_allocno_bitmap
);
1941 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
1943 a
= ira_allocnos
[j
];
1944 if (! ALLOCNO_ASSIGNED_P (a
))
1946 bitmap_clear_bit (coloring_allocno_bitmap
, ALLOCNO_NUM (a
));
1948 /* Color all mentioned allocnos including transparent ones. */
1950 /* Process caps. They are processed just once. */
1951 if (flag_ira_region
== IRA_REGION_MIXED
1952 || flag_ira_region
== IRA_REGION_ALL
)
1953 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->all_allocnos
, 0, j
, bi
)
1955 a
= ira_allocnos
[j
];
1956 if (ALLOCNO_CAP_MEMBER (a
) == NULL
)
1958 /* Remove from processing in the next loop. */
1959 bitmap_clear_bit (consideration_allocno_bitmap
, j
);
1960 rclass
= ALLOCNO_COVER_CLASS (a
);
1961 if (flag_ira_region
== IRA_REGION_MIXED
1962 && (loop_tree_node
->reg_pressure
[rclass
]
1963 <= ira_available_class_regs
[rclass
]))
1965 mode
= ALLOCNO_MODE (a
);
1966 hard_regno
= ALLOCNO_HARD_REGNO (a
);
1967 if (hard_regno
>= 0)
1969 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
1970 ira_assert (index
>= 0);
1972 regno
= ALLOCNO_REGNO (a
);
1973 subloop_allocno
= ALLOCNO_CAP_MEMBER (a
);
1974 subloop_node
= ALLOCNO_LOOP_TREE_NODE (subloop_allocno
);
1975 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno
));
1976 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
1977 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
1978 if (hard_regno
>= 0)
1979 update_copy_costs (subloop_allocno
, true);
1980 /* We don't need updated costs anymore: */
1981 ira_free_allocno_updated_costs (subloop_allocno
);
1984 /* Update costs of the corresponding allocnos (not caps) in the
1986 for (subloop_node
= loop_tree_node
->subloops
;
1987 subloop_node
!= NULL
;
1988 subloop_node
= subloop_node
->subloop_next
)
1990 ira_assert (subloop_node
->bb
== NULL
);
1991 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
1993 a
= ira_allocnos
[j
];
1994 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
1995 mode
= ALLOCNO_MODE (a
);
1996 rclass
= ALLOCNO_COVER_CLASS (a
);
1997 hard_regno
= ALLOCNO_HARD_REGNO (a
);
1998 /* Use hard register class here. ??? */
1999 if (hard_regno
>= 0)
2001 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
2002 ira_assert (index
>= 0);
2004 regno
= ALLOCNO_REGNO (a
);
2005 /* ??? conflict costs */
2006 subloop_allocno
= subloop_node
->regno_allocno_map
[regno
];
2007 if (subloop_allocno
== NULL
2008 || ALLOCNO_CAP (subloop_allocno
) != NULL
)
2010 ira_assert (ALLOCNO_COVER_CLASS (subloop_allocno
) == rclass
);
2011 ira_assert (bitmap_bit_p (subloop_node
->all_allocnos
,
2012 ALLOCNO_NUM (subloop_allocno
)));
2013 if ((flag_ira_region
== IRA_REGION_MIXED
)
2014 && (loop_tree_node
->reg_pressure
[rclass
]
2015 <= ira_available_class_regs
[rclass
]))
2017 if (! ALLOCNO_ASSIGNED_P (subloop_allocno
))
2019 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
2020 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
2021 if (hard_regno
>= 0)
2022 update_copy_costs (subloop_allocno
, true);
2023 /* We don't need updated costs anymore: */
2024 ira_free_allocno_updated_costs (subloop_allocno
);
2028 exit_freq
= ira_loop_edge_freq (subloop_node
, regno
, true);
2029 enter_freq
= ira_loop_edge_freq (subloop_node
, regno
, false);
2030 ira_assert (regno
< ira_reg_equiv_len
);
2031 if (ira_reg_equiv_invariant_p
[regno
]
2032 || ira_reg_equiv_const
[regno
] != NULL_RTX
)
2034 if (! ALLOCNO_ASSIGNED_P (subloop_allocno
))
2036 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
2037 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
2038 if (hard_regno
>= 0)
2039 update_copy_costs (subloop_allocno
, true);
2040 /* We don't need updated costs anymore: */
2041 ira_free_allocno_updated_costs (subloop_allocno
);
2044 else if (hard_regno
< 0)
2046 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno
)
2047 -= ((ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
)
2048 + (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
));
2052 cover_class
= ALLOCNO_COVER_CLASS (subloop_allocno
);
2053 cost
= (ira_get_register_move_cost (mode
, rclass
, rclass
)
2054 * (exit_freq
+ enter_freq
));
2055 ira_allocate_and_set_or_copy_costs
2056 (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
), cover_class
,
2057 ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno
),
2058 ALLOCNO_HARD_REG_COSTS (subloop_allocno
));
2059 ira_allocate_and_set_or_copy_costs
2060 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno
),
2062 ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno
));
2063 ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
] -= cost
;
2064 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno
)[index
]
2066 if (ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno
)
2067 > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
])
2068 ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno
)
2069 = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
];
2070 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno
)
2071 += (ira_memory_move_cost
[mode
][rclass
][0] * enter_freq
2072 + ira_memory_move_cost
[mode
][rclass
][1] * exit_freq
);
2078 /* Initialize the common data for coloring and calls functions to do
2079 Chaitin-Briggs and regional coloring. */
2083 coloring_allocno_bitmap
= ira_allocate_bitmap ();
2084 allocnos_for_spilling
2085 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
2086 * ira_allocnos_num
);
2087 splay_tree_node_pool
= create_alloc_pool ("splay tree nodes",
2088 sizeof (struct splay_tree_node_s
),
2090 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
2091 fprintf (ira_dump_file
, "\n**** Allocnos coloring:\n\n");
2093 ira_traverse_loop_tree (false, ira_loop_tree_root
, color_pass
, NULL
);
2095 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
2096 ira_print_disposition (ira_dump_file
);
2098 free_alloc_pool (splay_tree_node_pool
);
2099 ira_free_bitmap (coloring_allocno_bitmap
);
2100 ira_free (allocnos_for_spilling
);
2105 /* Move spill/restore code, which are to be generated in ira-emit.c,
2106 to less frequent points (if it is profitable) by reassigning some
2107 allocnos (in loop with subloops containing in another loop) to
2108 memory which results in longer live-range where the corresponding
2109 pseudo-registers will be in memory. */
2111 move_spill_restore (void)
2113 int cost
, regno
, hard_regno
, hard_regno2
, index
;
2115 int enter_freq
, exit_freq
;
2116 enum machine_mode mode
;
2117 enum reg_class rclass
;
2118 ira_allocno_t a
, parent_allocno
, subloop_allocno
;
2119 ira_loop_tree_node_t parent
, loop_node
, subloop_node
;
2120 ira_allocno_iterator ai
;
2125 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
2126 fprintf (ira_dump_file
, "New iteration of spill/restore move\n");
2127 FOR_EACH_ALLOCNO (a
, ai
)
2129 regno
= ALLOCNO_REGNO (a
);
2130 loop_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2131 if (ALLOCNO_CAP_MEMBER (a
) != NULL
2132 || ALLOCNO_CAP (a
) != NULL
2133 || (hard_regno
= ALLOCNO_HARD_REGNO (a
)) < 0
2134 || loop_node
->children
== NULL
2135 /* don't do the optimization because it can create
2136 copies and the reload pass can spill the allocno set
2137 by copy although the allocno will not get memory
2139 || ira_reg_equiv_invariant_p
[regno
]
2140 || ira_reg_equiv_const
[regno
] != NULL_RTX
2141 || !bitmap_bit_p (loop_node
->border_allocnos
, ALLOCNO_NUM (a
)))
2143 mode
= ALLOCNO_MODE (a
);
2144 rclass
= ALLOCNO_COVER_CLASS (a
);
2145 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
2146 ira_assert (index
>= 0);
2147 cost
= (ALLOCNO_MEMORY_COST (a
)
2148 - (ALLOCNO_HARD_REG_COSTS (a
) == NULL
2149 ? ALLOCNO_COVER_CLASS_COST (a
)
2150 : ALLOCNO_HARD_REG_COSTS (a
)[index
]));
2151 for (subloop_node
= loop_node
->subloops
;
2152 subloop_node
!= NULL
;
2153 subloop_node
= subloop_node
->subloop_next
)
2155 ira_assert (subloop_node
->bb
== NULL
);
2156 subloop_allocno
= subloop_node
->regno_allocno_map
[regno
];
2157 if (subloop_allocno
== NULL
)
2159 ira_assert (rclass
== ALLOCNO_COVER_CLASS (subloop_allocno
));
2160 /* We have accumulated cost. To get the real cost of
2161 allocno usage in the loop we should subtract costs of
2162 the subloop allocnos. */
2163 cost
-= (ALLOCNO_MEMORY_COST (subloop_allocno
)
2164 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno
) == NULL
2165 ? ALLOCNO_COVER_CLASS_COST (subloop_allocno
)
2166 : ALLOCNO_HARD_REG_COSTS (subloop_allocno
)[index
]));
2167 exit_freq
= ira_loop_edge_freq (subloop_node
, regno
, true);
2168 enter_freq
= ira_loop_edge_freq (subloop_node
, regno
, false);
2169 if ((hard_regno2
= ALLOCNO_HARD_REGNO (subloop_allocno
)) < 0)
2170 cost
-= (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
2171 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
2175 += (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
2176 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
2177 if (hard_regno2
!= hard_regno
)
2178 cost
-= (ira_get_register_move_cost (mode
, rclass
, rclass
)
2179 * (exit_freq
+ enter_freq
));
2182 if ((parent
= loop_node
->parent
) != NULL
2183 && (parent_allocno
= parent
->regno_allocno_map
[regno
]) != NULL
)
2185 ira_assert (rclass
== ALLOCNO_COVER_CLASS (parent_allocno
));
2186 exit_freq
= ira_loop_edge_freq (loop_node
, regno
, true);
2187 enter_freq
= ira_loop_edge_freq (loop_node
, regno
, false);
2188 if ((hard_regno2
= ALLOCNO_HARD_REGNO (parent_allocno
)) < 0)
2189 cost
-= (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
2190 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
2194 += (ira_memory_move_cost
[mode
][rclass
][1] * exit_freq
2195 + ira_memory_move_cost
[mode
][rclass
][0] * enter_freq
);
2196 if (hard_regno2
!= hard_regno
)
2197 cost
-= (ira_get_register_move_cost (mode
, rclass
, rclass
)
2198 * (exit_freq
+ enter_freq
));
2203 ALLOCNO_HARD_REGNO (a
) = -1;
2204 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2208 " Moving spill/restore for a%dr%d up from loop %d",
2209 ALLOCNO_NUM (a
), regno
, loop_node
->loop
->num
);
2210 fprintf (ira_dump_file
, " - profit %d\n", -cost
);
2222 /* Update current hard reg costs and current conflict hard reg costs
2223 for allocno A. It is done by processing its copies containing
2224 other allocnos already assigned. */
2226 update_curr_costs (ira_allocno_t a
)
2228 int i
, hard_regno
, cost
;
2229 enum machine_mode mode
;
2230 enum reg_class cover_class
, rclass
;
2231 ira_allocno_t another_a
;
2232 ira_copy_t cp
, next_cp
;
2234 ira_free_allocno_updated_costs (a
);
2235 ira_assert (! ALLOCNO_ASSIGNED_P (a
));
2236 cover_class
= ALLOCNO_COVER_CLASS (a
);
2237 if (cover_class
== NO_REGS
)
2239 mode
= ALLOCNO_MODE (a
);
2240 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
2244 next_cp
= cp
->next_first_allocno_copy
;
2245 another_a
= cp
->second
;
2247 else if (cp
->second
== a
)
2249 next_cp
= cp
->next_second_allocno_copy
;
2250 another_a
= cp
->first
;
2254 if (! ira_reg_classes_intersect_p
[cover_class
][ALLOCNO_COVER_CLASS
2256 || ! ALLOCNO_ASSIGNED_P (another_a
)
2257 || (hard_regno
= ALLOCNO_HARD_REGNO (another_a
)) < 0)
2259 rclass
= REGNO_REG_CLASS (hard_regno
);
2260 i
= ira_class_hard_reg_index
[cover_class
][hard_regno
];
2263 cost
= (cp
->first
== a
2264 ? ira_get_register_move_cost (mode
, rclass
, cover_class
)
2265 : ira_get_register_move_cost (mode
, cover_class
, rclass
));
2266 ira_allocate_and_set_or_copy_costs
2267 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a
),
2268 cover_class
, ALLOCNO_COVER_CLASS_COST (a
),
2269 ALLOCNO_HARD_REG_COSTS (a
));
2270 ira_allocate_and_set_or_copy_costs
2271 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
),
2272 cover_class
, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a
));
2273 ALLOCNO_UPDATED_HARD_REG_COSTS (a
)[i
] -= cp
->freq
* cost
;
2274 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
)[i
] -= cp
->freq
* cost
;
2278 /* Try to assign hard registers to the unassigned allocnos and
2279 allocnos conflicting with them or conflicting with allocnos whose
2280 regno >= START_REGNO. The function is called after ira_flattening,
2281 so more allocnos (including ones created in ira-emit.c) will have a
2282 chance to get a hard register. We use simple assignment algorithm
2283 based on priorities. */
2285 ira_reassign_conflict_allocnos (int start_regno
)
2287 int i
, allocnos_to_color_num
;
2288 ira_allocno_t a
, conflict_a
;
2289 ira_allocno_conflict_iterator aci
;
2290 enum reg_class cover_class
;
2291 bitmap allocnos_to_color
;
2292 ira_allocno_iterator ai
;
2294 allocnos_to_color
= ira_allocate_bitmap ();
2295 allocnos_to_color_num
= 0;
2296 FOR_EACH_ALLOCNO (a
, ai
)
2298 if (! ALLOCNO_ASSIGNED_P (a
)
2299 && ! bitmap_bit_p (allocnos_to_color
, ALLOCNO_NUM (a
)))
2301 if (ALLOCNO_COVER_CLASS (a
) != NO_REGS
)
2302 sorted_allocnos
[allocnos_to_color_num
++] = a
;
2305 ALLOCNO_ASSIGNED_P (a
) = true;
2306 ALLOCNO_HARD_REGNO (a
) = -1;
2307 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
2308 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
2310 bitmap_set_bit (allocnos_to_color
, ALLOCNO_NUM (a
));
2312 if (ALLOCNO_REGNO (a
) < start_regno
2313 || (cover_class
= ALLOCNO_COVER_CLASS (a
)) == NO_REGS
)
2315 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_a
, aci
)
2317 ira_assert (ira_reg_classes_intersect_p
2318 [cover_class
][ALLOCNO_COVER_CLASS (conflict_a
)]);
2319 if (bitmap_bit_p (allocnos_to_color
, ALLOCNO_NUM (conflict_a
)))
2321 bitmap_set_bit (allocnos_to_color
, ALLOCNO_NUM (conflict_a
));
2322 sorted_allocnos
[allocnos_to_color_num
++] = conflict_a
;
2325 ira_free_bitmap (allocnos_to_color
);
2326 if (allocnos_to_color_num
> 1)
2328 setup_allocno_priorities (sorted_allocnos
, allocnos_to_color_num
);
2329 qsort (sorted_allocnos
, allocnos_to_color_num
, sizeof (ira_allocno_t
),
2330 allocno_priority_compare_func
);
2332 for (i
= 0; i
< allocnos_to_color_num
; i
++)
2334 a
= sorted_allocnos
[i
];
2335 ALLOCNO_ASSIGNED_P (a
) = false;
2336 update_curr_costs (a
);
2338 for (i
= 0; i
< allocnos_to_color_num
; i
++)
2340 a
= sorted_allocnos
[i
];
2341 if (assign_hard_reg (a
, true))
2343 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2346 " Secondary allocation: assign hard reg %d to reg %d\n",
2347 ALLOCNO_HARD_REGNO (a
), ALLOCNO_REGNO (a
));
2354 /* This page contains code to coalesce memory stack slots used by
2355 spilled allocnos. This results in smaller stack frame, better data
2356 locality, and in smaller code for some architectures like
2357 x86/x86_64 where insn size depends on address displacement value.
2358 On the other hand, it can worsen insn scheduling after the RA but
2359 in practice it is less important than smaller stack frames. */
2361 /* Usage cost and order number of coalesced allocno set to which
2362 given pseudo register belongs to. */
2363 static int *regno_coalesced_allocno_cost
;
2364 static int *regno_coalesced_allocno_num
;
2366 /* Sort pseudos according frequencies of coalesced allocno sets they
2367 belong to (putting most frequently ones first), and according to
2368 coalesced allocno set order numbers. */
2370 coalesced_pseudo_reg_freq_compare (const void *v1p
, const void *v2p
)
2372 const int regno1
= *(const int *) v1p
;
2373 const int regno2
= *(const int *) v2p
;
2376 if ((diff
= (regno_coalesced_allocno_cost
[regno2
]
2377 - regno_coalesced_allocno_cost
[regno1
])) != 0)
2379 if ((diff
= (regno_coalesced_allocno_num
[regno1
]
2380 - regno_coalesced_allocno_num
[regno2
])) != 0)
2382 return regno1
- regno2
;
2385 /* Widest width in which each pseudo reg is referred to (via subreg).
2386 It is used for sorting pseudo registers. */
2387 static unsigned int *regno_max_ref_width
;
2389 /* Redefine STACK_GROWS_DOWNWARD in terms of 0 or 1. */
2390 #ifdef STACK_GROWS_DOWNWARD
2391 # undef STACK_GROWS_DOWNWARD
2392 # define STACK_GROWS_DOWNWARD 1
2394 # define STACK_GROWS_DOWNWARD 0
2397 /* Sort pseudos according their slot numbers (putting ones with
2398 smaller numbers first, or last when the frame pointer is not
2401 coalesced_pseudo_reg_slot_compare (const void *v1p
, const void *v2p
)
2403 const int regno1
= *(const int *) v1p
;
2404 const int regno2
= *(const int *) v2p
;
2405 ira_allocno_t a1
= ira_regno_allocno_map
[regno1
];
2406 ira_allocno_t a2
= ira_regno_allocno_map
[regno2
];
2407 int diff
, slot_num1
, slot_num2
;
2408 int total_size1
, total_size2
;
2410 if (a1
== NULL
|| ALLOCNO_HARD_REGNO (a1
) >= 0)
2412 if (a2
== NULL
|| ALLOCNO_HARD_REGNO (a2
) >= 0)
2413 return regno1
- regno2
;
2416 else if (a2
== NULL
|| ALLOCNO_HARD_REGNO (a2
) >= 0)
2418 slot_num1
= -ALLOCNO_HARD_REGNO (a1
);
2419 slot_num2
= -ALLOCNO_HARD_REGNO (a2
);
2420 if ((diff
= slot_num1
- slot_num2
) != 0)
2421 return (frame_pointer_needed
2422 || !FRAME_GROWS_DOWNWARD
== STACK_GROWS_DOWNWARD
? diff
: -diff
);
2423 total_size1
= MAX (PSEUDO_REGNO_BYTES (regno1
), regno_max_ref_width
[regno1
]);
2424 total_size2
= MAX (PSEUDO_REGNO_BYTES (regno2
), regno_max_ref_width
[regno2
]);
2425 if ((diff
= total_size2
- total_size1
) != 0)
2427 return regno1
- regno2
;
2430 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
2431 for coalesced allocno sets containing allocnos with their regnos
2432 given in array PSEUDO_REGNOS of length N. */
2434 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos
, int n
)
2436 int i
, num
, regno
, cost
;
2437 ira_allocno_t allocno
, a
;
2439 for (num
= i
= 0; i
< n
; i
++)
2441 regno
= pseudo_regnos
[i
];
2442 allocno
= ira_regno_allocno_map
[regno
];
2443 if (allocno
== NULL
)
2445 regno_coalesced_allocno_cost
[regno
] = 0;
2446 regno_coalesced_allocno_num
[regno
] = ++num
;
2449 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) != allocno
)
2452 for (cost
= 0, a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
2453 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
2455 cost
+= ALLOCNO_FREQ (a
);
2459 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
2460 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
2462 regno_coalesced_allocno_num
[ALLOCNO_REGNO (a
)] = num
;
2463 regno_coalesced_allocno_cost
[ALLOCNO_REGNO (a
)] = cost
;
2470 /* Collect spilled allocnos representing coalesced allocno sets (the
2471 first coalesced allocno). The collected allocnos are returned
2472 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
2473 number of the collected allocnos. The allocnos are given by their
2474 regnos in array PSEUDO_REGNOS of length N. */
2476 collect_spilled_coalesced_allocnos (int *pseudo_regnos
, int n
,
2477 ira_allocno_t
*spilled_coalesced_allocnos
)
2480 ira_allocno_t allocno
;
2482 for (num
= i
= 0; i
< n
; i
++)
2484 regno
= pseudo_regnos
[i
];
2485 allocno
= ira_regno_allocno_map
[regno
];
2486 if (allocno
== NULL
|| ALLOCNO_HARD_REGNO (allocno
) >= 0
2487 || ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) != allocno
)
2489 spilled_coalesced_allocnos
[num
++] = allocno
;
2494 /* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
2495 given slot contains live ranges of coalesced allocnos assigned to
2497 static allocno_live_range_t
*slot_coalesced_allocnos_live_ranges
;
2499 /* Return TRUE if coalesced allocnos represented by ALLOCNO has live
2500 ranges intersected with live ranges of coalesced allocnos assigned
2501 to slot with number N. */
2503 slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno
, int n
)
2507 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
2508 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
2510 if (ira_allocno_live_ranges_intersect_p
2511 (slot_coalesced_allocnos_live_ranges
[n
], ALLOCNO_LIVE_RANGES (a
)))
2519 /* Update live ranges of slot to which coalesced allocnos represented
2520 by ALLOCNO were assigned. */
2522 setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno
)
2526 allocno_live_range_t r
;
2528 n
= ALLOCNO_TEMP (allocno
);
2529 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
2530 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
2532 r
= ira_copy_allocno_live_range_list (ALLOCNO_LIVE_RANGES (a
));
2533 slot_coalesced_allocnos_live_ranges
[n
]
2534 = ira_merge_allocno_live_ranges
2535 (slot_coalesced_allocnos_live_ranges
[n
], r
);
2541 /* We have coalesced allocnos involving in copies. Coalesce allocnos
2542 further in order to share the same memory stack slot. Allocnos
2543 representing sets of allocnos coalesced before the call are given
2544 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
2545 some allocnos were coalesced in the function. */
2547 coalesce_spill_slots (ira_allocno_t
*spilled_coalesced_allocnos
, int num
)
2549 int i
, j
, n
, last_coalesced_allocno_num
;
2550 ira_allocno_t allocno
, a
;
2551 bool merged_p
= false;
2552 bitmap set_jump_crosses
= regstat_get_setjmp_crosses ();
2554 slot_coalesced_allocnos_live_ranges
2555 = (allocno_live_range_t
*) ira_allocate (sizeof (allocno_live_range_t
)
2556 * ira_allocnos_num
);
2557 memset (slot_coalesced_allocnos_live_ranges
, 0,
2558 sizeof (allocno_live_range_t
) * ira_allocnos_num
);
2559 last_coalesced_allocno_num
= 0;
2560 /* Coalesce non-conflicting spilled allocnos preferring most
2562 for (i
= 0; i
< num
; i
++)
2564 allocno
= spilled_coalesced_allocnos
[i
];
2565 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) != allocno
2566 || bitmap_bit_p (set_jump_crosses
, ALLOCNO_REGNO (allocno
))
2567 || (ALLOCNO_REGNO (allocno
) < ira_reg_equiv_len
2568 && (ira_reg_equiv_const
[ALLOCNO_REGNO (allocno
)] != NULL_RTX
2569 || ira_reg_equiv_invariant_p
[ALLOCNO_REGNO (allocno
)])))
2571 for (j
= 0; j
< i
; j
++)
2573 a
= spilled_coalesced_allocnos
[j
];
2574 n
= ALLOCNO_TEMP (a
);
2575 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) == a
2576 && ! bitmap_bit_p (set_jump_crosses
, ALLOCNO_REGNO (a
))
2577 && (ALLOCNO_REGNO (a
) >= ira_reg_equiv_len
2578 || (! ira_reg_equiv_invariant_p
[ALLOCNO_REGNO (a
)]
2579 && ira_reg_equiv_const
[ALLOCNO_REGNO (a
)] == NULL_RTX
))
2580 && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno
, n
))
2585 /* No coalescing: set up number for coalesced allocnos
2586 represented by ALLOCNO. */
2587 ALLOCNO_TEMP (allocno
) = last_coalesced_allocno_num
++;
2588 setup_slot_coalesced_allocno_live_ranges (allocno
);
2592 allocno_coalesced_p
= true;
2594 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2595 fprintf (ira_dump_file
,
2596 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
2597 ALLOCNO_NUM (allocno
), ALLOCNO_REGNO (allocno
),
2598 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
2599 ALLOCNO_TEMP (allocno
) = ALLOCNO_TEMP (a
);
2600 setup_slot_coalesced_allocno_live_ranges (allocno
);
2601 merge_allocnos (a
, allocno
);
2602 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) == a
);
2605 for (i
= 0; i
< ira_allocnos_num
; i
++)
2606 ira_finish_allocno_live_range_list
2607 (slot_coalesced_allocnos_live_ranges
[i
]);
2608 ira_free (slot_coalesced_allocnos_live_ranges
);
2612 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
2613 subsequent assigning stack slots to them in the reload pass. To do
2614 this we coalesce spilled allocnos first to decrease the number of
2615 memory-memory move insns. This function is called by the
2618 ira_sort_regnos_for_alter_reg (int *pseudo_regnos
, int n
,
2619 unsigned int *reg_max_ref_width
)
2621 int max_regno
= max_reg_num ();
2622 int i
, regno
, num
, slot_num
;
2623 ira_allocno_t allocno
, a
;
2624 ira_allocno_iterator ai
;
2625 ira_allocno_t
*spilled_coalesced_allocnos
;
2627 processed_coalesced_allocno_bitmap
= ira_allocate_bitmap ();
2628 /* Set up allocnos can be coalesced. */
2629 coloring_allocno_bitmap
= ira_allocate_bitmap ();
2630 for (i
= 0; i
< n
; i
++)
2632 regno
= pseudo_regnos
[i
];
2633 allocno
= ira_regno_allocno_map
[regno
];
2634 if (allocno
!= NULL
)
2635 bitmap_set_bit (coloring_allocno_bitmap
,
2636 ALLOCNO_NUM (allocno
));
2638 allocno_coalesced_p
= false;
2639 coalesce_allocnos (true);
2640 ira_free_bitmap (coloring_allocno_bitmap
);
2641 regno_coalesced_allocno_cost
2642 = (int *) ira_allocate (max_regno
* sizeof (int));
2643 regno_coalesced_allocno_num
2644 = (int *) ira_allocate (max_regno
* sizeof (int));
2645 memset (regno_coalesced_allocno_num
, 0, max_regno
* sizeof (int));
2646 setup_coalesced_allocno_costs_and_nums (pseudo_regnos
, n
);
2647 /* Sort regnos according frequencies of the corresponding coalesced
2649 qsort (pseudo_regnos
, n
, sizeof (int), coalesced_pseudo_reg_freq_compare
);
2650 spilled_coalesced_allocnos
2651 = (ira_allocno_t
*) ira_allocate (ira_allocnos_num
2652 * sizeof (ira_allocno_t
));
2653 /* Collect allocnos representing the spilled coalesced allocno
2655 num
= collect_spilled_coalesced_allocnos (pseudo_regnos
, n
,
2656 spilled_coalesced_allocnos
);
2657 if (flag_ira_share_spill_slots
2658 && coalesce_spill_slots (spilled_coalesced_allocnos
, num
))
2660 setup_coalesced_allocno_costs_and_nums (pseudo_regnos
, n
);
2661 qsort (pseudo_regnos
, n
, sizeof (int),
2662 coalesced_pseudo_reg_freq_compare
);
2663 num
= collect_spilled_coalesced_allocnos (pseudo_regnos
, n
,
2664 spilled_coalesced_allocnos
);
2666 ira_free_bitmap (processed_coalesced_allocno_bitmap
);
2667 allocno_coalesced_p
= false;
2668 /* Assign stack slot numbers to spilled allocno sets, use smaller
2669 numbers for most frequently used coalesced allocnos. -1 is
2670 reserved for dynamic search of stack slots for pseudos spilled by
2673 for (i
= 0; i
< num
; i
++)
2675 allocno
= spilled_coalesced_allocnos
[i
];
2676 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) != allocno
2677 || ALLOCNO_HARD_REGNO (allocno
) >= 0
2678 || (ALLOCNO_REGNO (allocno
) < ira_reg_equiv_len
2679 && (ira_reg_equiv_const
[ALLOCNO_REGNO (allocno
)] != NULL_RTX
2680 || ira_reg_equiv_invariant_p
[ALLOCNO_REGNO (allocno
)])))
2682 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2683 fprintf (ira_dump_file
, " Slot %d (freq,size):", slot_num
);
2685 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
2686 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
2688 ira_assert (ALLOCNO_HARD_REGNO (a
) < 0);
2689 ALLOCNO_HARD_REGNO (a
) = -slot_num
;
2690 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2691 fprintf (ira_dump_file
, " a%dr%d(%d,%d)",
2692 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
), ALLOCNO_FREQ (a
),
2693 MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a
)),
2694 reg_max_ref_width
[ALLOCNO_REGNO (a
)]));
2699 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2700 fprintf (ira_dump_file
, "\n");
2702 ira_spilled_reg_stack_slots_num
= slot_num
- 1;
2703 ira_free (spilled_coalesced_allocnos
);
2704 /* Sort regnos according the slot numbers. */
2705 regno_max_ref_width
= reg_max_ref_width
;
2706 qsort (pseudo_regnos
, n
, sizeof (int), coalesced_pseudo_reg_slot_compare
);
2707 /* Uncoalesce allocnos which is necessary for (re)assigning during
2709 FOR_EACH_ALLOCNO (a
, ai
)
2711 ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) = a
;
2712 ALLOCNO_NEXT_COALESCED_ALLOCNO (a
) = a
;
2714 ira_free (regno_coalesced_allocno_num
);
2715 ira_free (regno_coalesced_allocno_cost
);
2720 /* This page contains code used by the reload pass to improve the
2723 /* The function is called from reload to mark changes in the
2724 allocation of REGNO made by the reload. Remember that reg_renumber
2725 reflects the change result. */
2727 ira_mark_allocation_change (int regno
)
2729 ira_allocno_t a
= ira_regno_allocno_map
[regno
];
2730 int old_hard_regno
, hard_regno
, cost
;
2731 enum reg_class cover_class
= ALLOCNO_COVER_CLASS (a
);
2733 ira_assert (a
!= NULL
);
2734 hard_regno
= reg_renumber
[regno
];
2735 if ((old_hard_regno
= ALLOCNO_HARD_REGNO (a
)) == hard_regno
)
2737 if (old_hard_regno
< 0)
2738 cost
= -ALLOCNO_MEMORY_COST (a
);
2741 ira_assert (ira_class_hard_reg_index
[cover_class
][old_hard_regno
] >= 0);
2742 cost
= -(ALLOCNO_HARD_REG_COSTS (a
) == NULL
2743 ? ALLOCNO_COVER_CLASS_COST (a
)
2744 : ALLOCNO_HARD_REG_COSTS (a
)
2745 [ira_class_hard_reg_index
[cover_class
][old_hard_regno
]]);
2746 update_copy_costs (a
, false);
2748 ira_overall_cost
-= cost
;
2749 ALLOCNO_HARD_REGNO (a
) = hard_regno
;
2752 ALLOCNO_HARD_REGNO (a
) = -1;
2753 cost
+= ALLOCNO_MEMORY_COST (a
);
2755 else if (ira_class_hard_reg_index
[cover_class
][hard_regno
] >= 0)
2757 cost
+= (ALLOCNO_HARD_REG_COSTS (a
) == NULL
2758 ? ALLOCNO_COVER_CLASS_COST (a
)
2759 : ALLOCNO_HARD_REG_COSTS (a
)
2760 [ira_class_hard_reg_index
[cover_class
][hard_regno
]]);
2761 update_copy_costs (a
, true);
2764 /* Reload changed class of the allocno. */
2766 ira_overall_cost
+= cost
;
2769 /* This function is called when reload deletes memory-memory move. In
2770 this case we marks that the allocation of the corresponding
2771 allocnos should be not changed in future. Otherwise we risk to get
2774 ira_mark_memory_move_deletion (int dst_regno
, int src_regno
)
2776 ira_allocno_t dst
= ira_regno_allocno_map
[dst_regno
];
2777 ira_allocno_t src
= ira_regno_allocno_map
[src_regno
];
2779 ira_assert (dst
!= NULL
&& src
!= NULL
2780 && ALLOCNO_HARD_REGNO (dst
) < 0
2781 && ALLOCNO_HARD_REGNO (src
) < 0);
2782 ALLOCNO_DONT_REASSIGN_P (dst
) = true;
2783 ALLOCNO_DONT_REASSIGN_P (src
) = true;
2786 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
2787 allocno A and return TRUE in the case of success. */
2789 allocno_reload_assign (ira_allocno_t a
, HARD_REG_SET forbidden_regs
)
2792 enum reg_class cover_class
;
2793 int regno
= ALLOCNO_REGNO (a
);
2796 COPY_HARD_REG_SET (saved
, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
2797 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
), forbidden_regs
);
2798 if (! flag_caller_saves
&& ALLOCNO_CALLS_CROSSED_NUM (a
) != 0)
2799 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
), call_used_reg_set
);
2800 ALLOCNO_ASSIGNED_P (a
) = false;
2801 cover_class
= ALLOCNO_COVER_CLASS (a
);
2802 update_curr_costs (a
);
2803 assign_hard_reg (a
, true);
2804 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2805 reg_renumber
[regno
] = hard_regno
;
2807 ALLOCNO_HARD_REGNO (a
) = -1;
2810 ira_assert (ira_class_hard_reg_index
[cover_class
][hard_regno
] >= 0);
2811 ira_overall_cost
-= (ALLOCNO_MEMORY_COST (a
)
2812 - (ALLOCNO_HARD_REG_COSTS (a
) == NULL
2813 ? ALLOCNO_COVER_CLASS_COST (a
)
2814 : ALLOCNO_HARD_REG_COSTS (a
)
2815 [ira_class_hard_reg_index
2816 [cover_class
][hard_regno
]]));
2817 if (ALLOCNO_CALLS_CROSSED_NUM (a
) != 0
2818 && ! ira_hard_reg_not_in_set_p (hard_regno
, ALLOCNO_MODE (a
),
2821 ira_assert (flag_caller_saves
);
2822 caller_save_needed
= 1;
2826 /* If we found a hard register, modify the RTL for the pseudo
2827 register to show the hard register, and mark the pseudo register
2829 if (reg_renumber
[regno
] >= 0)
2831 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2832 fprintf (ira_dump_file
, ": reassign to %d\n", reg_renumber
[regno
]);
2833 SET_REGNO (regno_reg_rtx
[regno
], reg_renumber
[regno
]);
2834 mark_home_live (regno
);
2836 else if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2837 fprintf (ira_dump_file
, "\n");
2838 COPY_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
), saved
);
2839 return reg_renumber
[regno
] >= 0;
2842 /* Sort pseudos according their usage frequencies (putting most
2843 frequently ones first). */
2845 pseudo_reg_compare (const void *v1p
, const void *v2p
)
2847 int regno1
= *(const int *) v1p
;
2848 int regno2
= *(const int *) v2p
;
2851 if ((diff
= REG_FREQ (regno2
) - REG_FREQ (regno1
)) != 0)
2853 return regno1
- regno2
;
2856 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
2857 NUM of them) or spilled pseudos conflicting with pseudos in
2858 SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
2859 allocation has been changed. The function doesn't use
2860 BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
2861 PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
2862 is called by the reload pass at the end of each reload
2865 ira_reassign_pseudos (int *spilled_pseudo_regs
, int num
,
2866 HARD_REG_SET bad_spill_regs
,
2867 HARD_REG_SET
*pseudo_forbidden_regs
,
2868 HARD_REG_SET
*pseudo_previous_regs
,
2873 ira_allocno_t a
, conflict_a
;
2874 HARD_REG_SET forbidden_regs
;
2875 ira_allocno_conflict_iterator aci
;
2876 bitmap temp
= BITMAP_ALLOC (NULL
);
2878 /* Add pseudos which conflict with pseudos already in
2879 SPILLED_PSEUDO_REGS to SPILLED_PSEUDO_REGS. This is preferable
2880 to allocating in two steps as some of the conflicts might have
2881 a higher priority than the pseudos passed in SPILLED_PSEUDO_REGS. */
2882 for (i
= 0; i
< num
; i
++)
2883 bitmap_set_bit (temp
, spilled_pseudo_regs
[i
]);
2885 for (i
= 0, n
= num
; i
< n
; i
++)
2887 int regno
= spilled_pseudo_regs
[i
];
2888 bitmap_set_bit (temp
, regno
);
2890 a
= ira_regno_allocno_map
[regno
];
2891 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_a
, aci
)
2892 if (ALLOCNO_HARD_REGNO (conflict_a
) < 0
2893 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a
)
2894 && ! bitmap_bit_p (temp
, ALLOCNO_REGNO (conflict_a
)))
2896 spilled_pseudo_regs
[num
++] = ALLOCNO_REGNO (conflict_a
);
2897 bitmap_set_bit (temp
, ALLOCNO_REGNO (conflict_a
));
2898 /* ?!? This seems wrong. */
2899 bitmap_set_bit (consideration_allocno_bitmap
,
2900 ALLOCNO_NUM (conflict_a
));
2905 qsort (spilled_pseudo_regs
, num
, sizeof (int), pseudo_reg_compare
);
2907 /* Try to assign hard registers to pseudos from
2908 SPILLED_PSEUDO_REGS. */
2909 for (i
= 0; i
< num
; i
++)
2911 regno
= spilled_pseudo_regs
[i
];
2912 COPY_HARD_REG_SET (forbidden_regs
, bad_spill_regs
);
2913 IOR_HARD_REG_SET (forbidden_regs
, pseudo_forbidden_regs
[regno
]);
2914 IOR_HARD_REG_SET (forbidden_regs
, pseudo_previous_regs
[regno
]);
2915 gcc_assert (reg_renumber
[regno
] < 0);
2916 a
= ira_regno_allocno_map
[regno
];
2917 ira_mark_allocation_change (regno
);
2918 ira_assert (reg_renumber
[regno
] < 0);
2919 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2920 fprintf (ira_dump_file
,
2921 " Try Assign %d(a%d), cost=%d", regno
, ALLOCNO_NUM (a
),
2922 ALLOCNO_MEMORY_COST (a
)
2923 - ALLOCNO_COVER_CLASS_COST (a
));
2924 allocno_reload_assign (a
, forbidden_regs
);
2925 if (reg_renumber
[regno
] >= 0)
2927 CLEAR_REGNO_REG_SET (spilled
, regno
);
2935 /* The function is called by reload and returns already allocated
2936 stack slot (if any) for REGNO with given INHERENT_SIZE and
2937 TOTAL_SIZE. In the case of failure to find a slot which can be
2938 used for REGNO, the function returns NULL. */
2940 ira_reuse_stack_slot (int regno
, unsigned int inherent_size
,
2941 unsigned int total_size
)
2944 int slot_num
, best_slot_num
;
2945 int cost
, best_cost
;
2946 ira_copy_t cp
, next_cp
;
2947 ira_allocno_t another_allocno
, allocno
= ira_regno_allocno_map
[regno
];
2950 struct ira_spilled_reg_stack_slot
*slot
= NULL
;
2952 ira_assert (inherent_size
== PSEUDO_REGNO_BYTES (regno
)
2953 && inherent_size
<= total_size
2954 && ALLOCNO_HARD_REGNO (allocno
) < 0);
2955 if (! flag_ira_share_spill_slots
)
2957 slot_num
= -ALLOCNO_HARD_REGNO (allocno
) - 2;
2960 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
2965 best_cost
= best_slot_num
= -1;
2967 /* It means that the pseudo was spilled in the reload pass, try
2970 slot_num
< ira_spilled_reg_stack_slots_num
;
2973 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
2974 if (slot
->mem
== NULL_RTX
)
2976 if (slot
->width
< total_size
2977 || GET_MODE_SIZE (GET_MODE (slot
->mem
)) < inherent_size
)
2980 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
2981 FIRST_PSEUDO_REGISTER
, i
, bi
)
2983 another_allocno
= ira_regno_allocno_map
[i
];
2984 if (allocnos_have_intersected_live_ranges_p (allocno
,
2988 for (cost
= 0, cp
= ALLOCNO_COPIES (allocno
);
2992 if (cp
->first
== allocno
)
2994 next_cp
= cp
->next_first_allocno_copy
;
2995 another_allocno
= cp
->second
;
2997 else if (cp
->second
== allocno
)
2999 next_cp
= cp
->next_second_allocno_copy
;
3000 another_allocno
= cp
->first
;
3004 if (cp
->insn
== NULL_RTX
)
3006 if (bitmap_bit_p (&slot
->spilled_regs
,
3007 ALLOCNO_REGNO (another_allocno
)))
3010 if (cost
> best_cost
)
3013 best_slot_num
= slot_num
;
3020 slot_num
= best_slot_num
;
3021 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
3022 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
3024 ALLOCNO_HARD_REGNO (allocno
) = -slot_num
- 2;
3029 ira_assert (slot
->width
>= total_size
);
3030 #ifdef ENABLE_IRA_CHECKING
3031 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
3032 FIRST_PSEUDO_REGISTER
, i
, bi
)
3034 ira_assert (! pseudos_have_intersected_live_ranges_p (regno
, i
));
3037 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
3038 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
3040 fprintf (ira_dump_file
, " Assigning %d(freq=%d) slot %d of",
3041 regno
, REG_FREQ (regno
), slot_num
);
3042 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
3043 FIRST_PSEUDO_REGISTER
, i
, bi
)
3045 if ((unsigned) regno
!= i
)
3046 fprintf (ira_dump_file
, " %d", i
);
3048 fprintf (ira_dump_file
, "\n");
3054 /* This is called by reload every time a new stack slot X with
3055 TOTAL_SIZE was allocated for REGNO. We store this info for
3056 subsequent ira_reuse_stack_slot calls. */
3058 ira_mark_new_stack_slot (rtx x
, int regno
, unsigned int total_size
)
3060 struct ira_spilled_reg_stack_slot
*slot
;
3062 ira_allocno_t allocno
;
3064 ira_assert (PSEUDO_REGNO_BYTES (regno
) <= total_size
);
3065 allocno
= ira_regno_allocno_map
[regno
];
3066 slot_num
= -ALLOCNO_HARD_REGNO (allocno
) - 2;
3069 slot_num
= ira_spilled_reg_stack_slots_num
++;
3070 ALLOCNO_HARD_REGNO (allocno
) = -slot_num
- 2;
3072 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
3073 INIT_REG_SET (&slot
->spilled_regs
);
3074 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
3076 slot
->width
= total_size
;
3077 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
3078 fprintf (ira_dump_file
, " Assigning %d(freq=%d) a new slot %d\n",
3079 regno
, REG_FREQ (regno
), slot_num
);
3083 /* Return spill cost for pseudo-registers whose numbers are in array
3084 REGNOS (with a negative number as an end marker) for reload with
3085 given IN and OUT for INSN. Return also number points (through
3086 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
3087 the register pressure is high, number of references of the
3088 pseudo-registers (through NREFS), number of callee-clobbered
3089 hard-registers occupied by the pseudo-registers (through
3090 CALL_USED_COUNT), and the first hard regno occupied by the
3091 pseudo-registers (through FIRST_HARD_REGNO). */
3093 calculate_spill_cost (int *regnos
, rtx in
, rtx out
, rtx insn
,
3094 int *excess_pressure_live_length
,
3095 int *nrefs
, int *call_used_count
, int *first_hard_regno
)
3097 int i
, cost
, regno
, hard_regno
, j
, count
, saved_cost
, nregs
;
3103 for (length
= count
= cost
= i
= 0;; i
++)
3108 *nrefs
+= REG_N_REFS (regno
);
3109 hard_regno
= reg_renumber
[regno
];
3110 ira_assert (hard_regno
>= 0);
3111 a
= ira_regno_allocno_map
[regno
];
3112 length
+= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
3113 cost
+= ALLOCNO_MEMORY_COST (a
) - ALLOCNO_COVER_CLASS_COST (a
);
3114 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (a
)];
3115 for (j
= 0; j
< nregs
; j
++)
3116 if (! TEST_HARD_REG_BIT (call_used_reg_set
, hard_regno
+ j
))
3120 in_p
= in
&& REG_P (in
) && (int) REGNO (in
) == hard_regno
;
3121 out_p
= out
&& REG_P (out
) && (int) REGNO (out
) == hard_regno
;
3123 && find_regno_note (insn
, REG_DEAD
, hard_regno
) != NULL_RTX
)
3127 saved_cost
+= ira_memory_move_cost
3128 [ALLOCNO_MODE (a
)][ALLOCNO_COVER_CLASS (a
)][1];
3131 += ira_memory_move_cost
3132 [ALLOCNO_MODE (a
)][ALLOCNO_COVER_CLASS (a
)][0];
3133 cost
-= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn
)) * saved_cost
;
3136 *excess_pressure_live_length
= length
;
3137 *call_used_count
= count
;
3141 hard_regno
= reg_renumber
[regnos
[0]];
3143 *first_hard_regno
= hard_regno
;
3147 /* Return TRUE if spilling pseudo-registers whose numbers are in array
3148 REGNOS is better than spilling pseudo-registers with numbers in
3149 OTHER_REGNOS for reload with given IN and OUT for INSN. The
3150 function used by the reload pass to make better register spilling
3153 ira_better_spill_reload_regno_p (int *regnos
, int *other_regnos
,
3154 rtx in
, rtx out
, rtx insn
)
3156 int cost
, other_cost
;
3157 int length
, other_length
;
3158 int nrefs
, other_nrefs
;
3159 int call_used_count
, other_call_used_count
;
3160 int hard_regno
, other_hard_regno
;
3162 cost
= calculate_spill_cost (regnos
, in
, out
, insn
,
3163 &length
, &nrefs
, &call_used_count
, &hard_regno
);
3164 other_cost
= calculate_spill_cost (other_regnos
, in
, out
, insn
,
3165 &other_length
, &other_nrefs
,
3166 &other_call_used_count
,
3168 if (nrefs
== 0 && other_nrefs
!= 0)
3170 if (nrefs
!= 0 && other_nrefs
== 0)
3172 if (cost
!= other_cost
)
3173 return cost
< other_cost
;
3174 if (length
!= other_length
)
3175 return length
> other_length
;
3176 #ifdef REG_ALLOC_ORDER
3177 if (hard_regno
>= 0 && other_hard_regno
>= 0)
3178 return (inv_reg_alloc_order
[hard_regno
]
3179 < inv_reg_alloc_order
[other_hard_regno
]);
3181 if (call_used_count
!= other_call_used_count
)
3182 return call_used_count
> other_call_used_count
;
3189 /* Allocate and initialize data necessary for assign_hard_reg. */
3191 ira_initiate_assign (void)
3194 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
3195 * ira_allocnos_num
);
3196 consideration_allocno_bitmap
= ira_allocate_bitmap ();
3197 initiate_cost_update ();
3198 allocno_priorities
= (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
3201 /* Deallocate data used by assign_hard_reg. */
3203 ira_finish_assign (void)
3205 ira_free (sorted_allocnos
);
3206 ira_free_bitmap (consideration_allocno_bitmap
);
3207 finish_cost_update ();
3208 ira_free (allocno_priorities
);
3213 /* Entry function doing color-based register allocation. */
3217 allocno_stack_vec
= VEC_alloc (ira_allocno_t
, heap
, ira_allocnos_num
);
3218 removed_splay_allocno_vec
3219 = VEC_alloc (ira_allocno_t
, heap
, ira_allocnos_num
);
3220 memset (allocated_hardreg_p
, 0, sizeof (allocated_hardreg_p
));
3221 ira_initiate_assign ();
3223 ira_finish_assign ();
3224 VEC_free (ira_allocno_t
, heap
, removed_splay_allocno_vec
);
3225 VEC_free (ira_allocno_t
, heap
, allocno_stack_vec
);
3226 move_spill_restore ();
3231 /* This page contains a simple register allocator without usage of
3232 allocno conflicts. This is used for fast allocation for -O0. */
3234 /* Do register allocation by not using allocno conflicts. It uses
3235 only allocno live ranges. The algorithm is close to Chow's
3236 priority coloring. */
3238 fast_allocation (void)
3240 int i
, j
, k
, num
, class_size
, hard_regno
;
3242 bool no_stack_reg_p
;
3244 enum reg_class cover_class
;
3245 enum machine_mode mode
;
3247 ira_allocno_iterator ai
;
3248 allocno_live_range_t r
;
3249 HARD_REG_SET conflict_hard_regs
, *used_hard_regs
;
3251 sorted_allocnos
= (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
3252 * ira_allocnos_num
);
3254 FOR_EACH_ALLOCNO (a
, ai
)
3255 sorted_allocnos
[num
++] = a
;
3256 allocno_priorities
= (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
3257 setup_allocno_priorities (sorted_allocnos
, num
);
3258 used_hard_regs
= (HARD_REG_SET
*) ira_allocate (sizeof (HARD_REG_SET
)
3260 for (i
= 0; i
< ira_max_point
; i
++)
3261 CLEAR_HARD_REG_SET (used_hard_regs
[i
]);
3262 qsort (sorted_allocnos
, num
, sizeof (ira_allocno_t
),
3263 allocno_priority_compare_func
);
3264 for (i
= 0; i
< num
; i
++)
3266 a
= sorted_allocnos
[i
];
3267 COPY_HARD_REG_SET (conflict_hard_regs
, ALLOCNO_CONFLICT_HARD_REGS (a
));
3268 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
3269 for (j
= r
->start
; j
<= r
->finish
; j
++)
3270 IOR_HARD_REG_SET (conflict_hard_regs
, used_hard_regs
[j
]);
3271 cover_class
= ALLOCNO_COVER_CLASS (a
);
3272 ALLOCNO_ASSIGNED_P (a
) = true;
3273 ALLOCNO_HARD_REGNO (a
) = -1;
3274 if (hard_reg_set_subset_p (reg_class_contents
[cover_class
],
3275 conflict_hard_regs
))
3277 mode
= ALLOCNO_MODE (a
);
3279 no_stack_reg_p
= ALLOCNO_NO_STACK_REG_P (a
);
3281 class_size
= ira_class_hard_regs_num
[cover_class
];
3282 for (j
= 0; j
< class_size
; j
++)
3284 hard_regno
= ira_class_hard_regs
[cover_class
][j
];
3286 if (no_stack_reg_p
&& FIRST_STACK_REG
<= hard_regno
3287 && hard_regno
<= LAST_STACK_REG
)
3290 if (!ira_hard_reg_not_in_set_p (hard_regno
, mode
, conflict_hard_regs
)
3291 || (TEST_HARD_REG_BIT
3292 (prohibited_class_mode_regs
[cover_class
][mode
], hard_regno
)))
3294 ALLOCNO_HARD_REGNO (a
) = hard_regno
;
3295 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
3296 for (k
= r
->start
; k
<= r
->finish
; k
++)
3297 IOR_HARD_REG_SET (used_hard_regs
[k
],
3298 ira_reg_mode_hard_regset
[hard_regno
][mode
]);
3302 ira_free (sorted_allocnos
);
3303 ira_free (used_hard_regs
);
3304 ira_free (allocno_priorities
);
3305 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
3306 ira_print_disposition (ira_dump_file
);
3311 /* Entry function doing coloring. */
3316 ira_allocno_iterator ai
;
3318 /* Setup updated costs. */
3319 FOR_EACH_ALLOCNO (a
, ai
)
3321 ALLOCNO_UPDATED_MEMORY_COST (a
) = ALLOCNO_MEMORY_COST (a
);
3322 ALLOCNO_UPDATED_COVER_CLASS_COST (a
) = ALLOCNO_COVER_CLASS_COST (a
);
3324 if (ira_conflicts_p
)