1 /* IRA allocation based on graph coloring.
2 Copyright (C) 2006, 2007, 2008, 2009
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
, add_cost
;
447 enum reg_class cover_class
, rclass
, 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
];
456 ira_assert (! ALLOCNO_ASSIGNED_P (allocno
));
457 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
458 class_size
= ira_class_hard_regs_num
[cover_class
];
459 mode
= ALLOCNO_MODE (allocno
);
460 CLEAR_HARD_REG_SET (conflicting_regs
);
461 best_hard_regno
= -1;
462 memset (full_costs
, 0, sizeof (int) * class_size
);
464 if (allocno_coalesced_p
)
465 bitmap_clear (processed_coalesced_allocno_bitmap
);
466 memset (costs
, 0, sizeof (int) * class_size
);
467 memset (full_costs
, 0, sizeof (int) * class_size
);
469 no_stack_reg_p
= false;
471 start_update_cost ();
472 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
473 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
475 mem_cost
+= ALLOCNO_UPDATED_MEMORY_COST (a
);
476 IOR_HARD_REG_SET (conflicting_regs
,
477 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
478 ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a
),
479 cover_class
, ALLOCNO_HARD_REG_COSTS (a
));
480 a_costs
= ALLOCNO_UPDATED_HARD_REG_COSTS (a
);
482 no_stack_reg_p
= no_stack_reg_p
|| ALLOCNO_TOTAL_NO_STACK_REG_P (a
);
484 for (cost
= ALLOCNO_UPDATED_COVER_CLASS_COST (a
), i
= 0;
489 costs
[i
] += a_costs
[i
];
490 full_costs
[i
] += a_costs
[i
];
495 full_costs
[i
] += cost
;
497 /* Take preferences of conflicting allocnos into account. */
498 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_allocno
, aci
)
499 /* Reload can give another class so we need to check all
501 if (retry_p
|| bitmap_bit_p (consideration_allocno_bitmap
,
502 ALLOCNO_NUM (conflict_allocno
)))
504 conflict_cover_class
= ALLOCNO_COVER_CLASS (conflict_allocno
);
505 ira_assert (ira_reg_classes_intersect_p
506 [cover_class
][conflict_cover_class
]);
507 if (allocno_coalesced_p
)
509 if (bitmap_bit_p (processed_coalesced_allocno_bitmap
,
510 ALLOCNO_NUM (conflict_allocno
)))
512 bitmap_set_bit (processed_coalesced_allocno_bitmap
,
513 ALLOCNO_NUM (conflict_allocno
));
515 if (ALLOCNO_ASSIGNED_P (conflict_allocno
))
517 if ((hard_regno
= ALLOCNO_HARD_REGNO (conflict_allocno
)) >= 0
518 && ira_class_hard_reg_index
[cover_class
][hard_regno
] >= 0)
522 ira_reg_mode_hard_regset
523 [hard_regno
][ALLOCNO_MODE (conflict_allocno
)]);
524 if (hard_reg_set_subset_p (reg_class_contents
[cover_class
],
529 else if (! ALLOCNO_MAY_BE_SPILLED_P (ALLOCNO_FIRST_COALESCED_ALLOCNO
532 ira_allocate_and_copy_costs
533 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno
),
534 conflict_cover_class
,
535 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_allocno
));
537 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno
);
538 if (conflict_costs
!= NULL
)
539 for (j
= class_size
- 1; j
>= 0; j
--)
541 hard_regno
= ira_class_hard_regs
[cover_class
][j
];
542 ira_assert (hard_regno
>= 0);
543 k
= (ira_class_hard_reg_index
544 [conflict_cover_class
][hard_regno
]);
547 full_costs
[j
] -= conflict_costs
[k
];
549 queue_update_cost (conflict_allocno
, COST_HOP_DIVISOR
);
555 /* Take into account preferences of allocnos connected by copies to
556 the conflict allocnos. */
557 update_conflict_hard_regno_costs (full_costs
, cover_class
, true);
559 /* Take preferences of allocnos connected by copies into
561 start_update_cost ();
562 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
563 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
565 queue_update_cost (a
, COST_HOP_DIVISOR
);
569 update_conflict_hard_regno_costs (full_costs
, cover_class
, false);
570 min_cost
= min_full_cost
= INT_MAX
;
571 /* We don't care about giving callee saved registers to allocnos no
572 living through calls because call clobbered registers are
573 allocated first (it is usual practice to put them first in
575 for (i
= 0; i
< class_size
; i
++)
577 hard_regno
= ira_class_hard_regs
[cover_class
][i
];
580 && FIRST_STACK_REG
<= hard_regno
&& hard_regno
<= LAST_STACK_REG
)
583 if (! ira_hard_reg_not_in_set_p (hard_regno
, mode
, conflicting_regs
)
584 || TEST_HARD_REG_BIT (prohibited_class_mode_regs
[cover_class
][mode
],
588 full_cost
= full_costs
[i
];
589 if (! allocated_hardreg_p
[hard_regno
]
590 && ira_hard_reg_not_in_set_p (hard_regno
, mode
, call_used_reg_set
))
591 /* We need to save/restore the hard register in
592 epilogue/prologue. Therefore we increase the cost. */
594 /* ??? If only part is call clobbered. */
595 rclass
= REGNO_REG_CLASS (hard_regno
);
596 add_cost
= (ira_memory_move_cost
[mode
][rclass
][0]
597 + ira_memory_move_cost
[mode
][rclass
][1] - 1);
599 full_cost
+= add_cost
;
603 if (min_full_cost
> full_cost
)
605 min_full_cost
= full_cost
;
606 best_hard_regno
= hard_regno
;
607 ira_assert (hard_regno
>= 0);
610 if (min_full_cost
> mem_cost
)
612 if (! retry_p
&& internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
613 fprintf (ira_dump_file
, "(memory is more profitable %d vs %d) ",
614 mem_cost
, min_full_cost
);
615 best_hard_regno
= -1;
618 if (flag_ira_algorithm
!= IRA_ALGORITHM_PRIORITY
619 && best_hard_regno
< 0
620 && ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
) != allocno
)
622 for (j
= 0, a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
623 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
625 ira_assert (! ALLOCNO_IN_GRAPH_P (a
));
626 sorted_allocnos
[j
++] = a
;
630 qsort (sorted_allocnos
, j
, sizeof (ira_allocno_t
),
631 allocno_cost_compare_func
);
632 for (i
= 0; i
< j
; i
++)
634 a
= sorted_allocnos
[i
];
635 ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) = a
;
636 ALLOCNO_NEXT_COALESCED_ALLOCNO (a
) = a
;
637 VEC_safe_push (ira_allocno_t
, heap
, allocno_stack_vec
, a
);
638 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
640 fprintf (ira_dump_file
, " Pushing");
641 print_coalesced_allocno (a
);
642 fprintf (ira_dump_file
, "\n");
647 if (best_hard_regno
>= 0)
648 allocated_hardreg_p
[best_hard_regno
] = true;
649 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
650 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
652 ALLOCNO_HARD_REGNO (a
) = best_hard_regno
;
653 ALLOCNO_ASSIGNED_P (a
) = true;
654 if (best_hard_regno
>= 0)
655 update_copy_costs (a
, true);
656 ira_assert (ALLOCNO_COVER_CLASS (a
) == cover_class
);
657 /* We don't need updated costs anymore: */
658 ira_free_allocno_updated_costs (a
);
662 return best_hard_regno
>= 0;
667 /* This page contains the allocator based on the Chaitin-Briggs algorithm. */
669 /* Bucket of allocnos that can colored currently without spilling. */
670 static ira_allocno_t colorable_allocno_bucket
;
672 /* Bucket of allocnos that might be not colored currently without
674 static ira_allocno_t uncolorable_allocno_bucket
;
676 /* Each element of the array contains the current number of allocnos
677 of given *cover* class in the uncolorable_bucket. */
678 static int uncolorable_allocnos_num
[N_REG_CLASSES
];
680 /* Return the current spill priority of allocno A. The less the
681 number, the more preferable the allocno for spilling. */
683 allocno_spill_priority (ira_allocno_t a
)
685 return (ALLOCNO_TEMP (a
)
686 / (ALLOCNO_LEFT_CONFLICTS_SIZE (a
)
687 * ira_reg_class_nregs
[ALLOCNO_COVER_CLASS (a
)][ALLOCNO_MODE (a
)]
691 /* Add ALLOCNO to bucket *BUCKET_PTR. ALLOCNO should be not in a bucket
694 add_allocno_to_bucket (ira_allocno_t allocno
, ira_allocno_t
*bucket_ptr
)
696 ira_allocno_t first_allocno
;
697 enum reg_class cover_class
;
699 if (bucket_ptr
== &uncolorable_allocno_bucket
700 && (cover_class
= ALLOCNO_COVER_CLASS (allocno
)) != NO_REGS
)
702 uncolorable_allocnos_num
[cover_class
]++;
703 ira_assert (uncolorable_allocnos_num
[cover_class
] > 0);
705 first_allocno
= *bucket_ptr
;
706 ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno
) = first_allocno
;
707 ALLOCNO_PREV_BUCKET_ALLOCNO (allocno
) = NULL
;
708 if (first_allocno
!= NULL
)
709 ALLOCNO_PREV_BUCKET_ALLOCNO (first_allocno
) = allocno
;
710 *bucket_ptr
= allocno
;
713 /* The function returns frequency and number of available hard
714 registers for allocnos coalesced with ALLOCNO. */
716 get_coalesced_allocnos_attributes (ira_allocno_t allocno
, int *freq
, int *num
)
722 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
723 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
725 *freq
+= ALLOCNO_FREQ (a
);
726 *num
+= ALLOCNO_AVAILABLE_REGS_NUM (a
);
732 /* Compare two allocnos to define which allocno should be pushed first
733 into the coloring stack. If the return is a negative number, the
734 allocno given by the first parameter will be pushed first. In this
735 case such allocno has less priority than the second one and the
736 hard register will be assigned to it after assignment to the second
737 one. As the result of such assignment order, the second allocno
738 has a better chance to get the best hard register. */
740 bucket_allocno_compare_func (const void *v1p
, const void *v2p
)
742 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
743 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
744 int diff
, a1_freq
, a2_freq
, a1_num
, a2_num
;
746 if ((diff
= (int) ALLOCNO_COVER_CLASS (a2
) - ALLOCNO_COVER_CLASS (a1
)) != 0)
748 get_coalesced_allocnos_attributes (a1
, &a1_freq
, &a1_num
);
749 get_coalesced_allocnos_attributes (a2
, &a2_freq
, &a2_num
);
750 if ((diff
= a2_num
- a1_num
) != 0)
752 else if ((diff
= a1_freq
- a2_freq
) != 0)
754 return ALLOCNO_NUM (a2
) - ALLOCNO_NUM (a1
);
757 /* Sort bucket *BUCKET_PTR and return the result through
760 sort_bucket (ira_allocno_t
*bucket_ptr
)
762 ira_allocno_t a
, head
;
765 for (n
= 0, a
= *bucket_ptr
; a
!= NULL
; a
= ALLOCNO_NEXT_BUCKET_ALLOCNO (a
))
766 sorted_allocnos
[n
++] = a
;
769 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
),
770 bucket_allocno_compare_func
);
772 for (n
--; n
>= 0; n
--)
774 a
= sorted_allocnos
[n
];
775 ALLOCNO_NEXT_BUCKET_ALLOCNO (a
) = head
;
776 ALLOCNO_PREV_BUCKET_ALLOCNO (a
) = NULL
;
778 ALLOCNO_PREV_BUCKET_ALLOCNO (head
) = a
;
784 /* Add ALLOCNO to bucket *BUCKET_PTR maintaining the order according
785 their priority. ALLOCNO should be not in a bucket before the
788 add_allocno_to_ordered_bucket (ira_allocno_t allocno
,
789 ira_allocno_t
*bucket_ptr
)
791 ira_allocno_t before
, after
;
792 enum reg_class cover_class
;
794 if (bucket_ptr
== &uncolorable_allocno_bucket
795 && (cover_class
= ALLOCNO_COVER_CLASS (allocno
)) != NO_REGS
)
797 uncolorable_allocnos_num
[cover_class
]++;
798 ira_assert (uncolorable_allocnos_num
[cover_class
] > 0);
800 for (before
= *bucket_ptr
, after
= NULL
;
802 after
= before
, before
= ALLOCNO_NEXT_BUCKET_ALLOCNO (before
))
803 if (bucket_allocno_compare_func (&allocno
, &before
) < 0)
805 ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno
) = before
;
806 ALLOCNO_PREV_BUCKET_ALLOCNO (allocno
) = after
;
808 *bucket_ptr
= allocno
;
810 ALLOCNO_NEXT_BUCKET_ALLOCNO (after
) = allocno
;
812 ALLOCNO_PREV_BUCKET_ALLOCNO (before
) = allocno
;
815 /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
818 delete_allocno_from_bucket (ira_allocno_t allocno
, ira_allocno_t
*bucket_ptr
)
820 ira_allocno_t prev_allocno
, next_allocno
;
821 enum reg_class cover_class
;
823 if (bucket_ptr
== &uncolorable_allocno_bucket
824 && (cover_class
= ALLOCNO_COVER_CLASS (allocno
)) != NO_REGS
)
826 uncolorable_allocnos_num
[cover_class
]--;
827 ira_assert (uncolorable_allocnos_num
[cover_class
] >= 0);
829 prev_allocno
= ALLOCNO_PREV_BUCKET_ALLOCNO (allocno
);
830 next_allocno
= ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno
);
831 if (prev_allocno
!= NULL
)
832 ALLOCNO_NEXT_BUCKET_ALLOCNO (prev_allocno
) = next_allocno
;
835 ira_assert (*bucket_ptr
== allocno
);
836 *bucket_ptr
= next_allocno
;
838 if (next_allocno
!= NULL
)
839 ALLOCNO_PREV_BUCKET_ALLOCNO (next_allocno
) = prev_allocno
;
842 /* Splay tree for each cover class. The trees are indexed by the
843 corresponding cover classes. Splay trees contain uncolorable
845 static splay_tree uncolorable_allocnos_splay_tree
[N_REG_CLASSES
];
847 /* If the following macro is TRUE, splay tree is used to choose an
848 allocno of the corresponding cover class for spilling. When the
849 number uncolorable allocnos of given cover class decreases to some
850 threshold, linear array search is used to find the best allocno for
851 spilling. This threshold is actually pretty big because, although
852 splay trees asymptotically is much faster, each splay tree
853 operation is sufficiently costly especially taking cache locality
855 #define USE_SPLAY_P(CLASS) (uncolorable_allocnos_num[CLASS] > 4000)
857 /* Put ALLOCNO onto the coloring stack without removing it from its
858 bucket. Pushing allocno to the coloring stack can result in moving
859 conflicting allocnos from the uncolorable bucket to the colorable
862 push_allocno_to_stack (ira_allocno_t allocno
)
864 int left_conflicts_size
, conflict_size
, size
;
865 ira_allocno_t a
, conflict_allocno
;
866 enum reg_class cover_class
;
867 ira_allocno_conflict_iterator aci
;
869 ALLOCNO_IN_GRAPH_P (allocno
) = false;
870 VEC_safe_push (ira_allocno_t
, heap
, allocno_stack_vec
, allocno
);
871 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
872 if (cover_class
== NO_REGS
)
874 size
= ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE (allocno
)];
875 if (allocno_coalesced_p
)
876 bitmap_clear (processed_coalesced_allocno_bitmap
);
877 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
878 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
880 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_allocno
, aci
)
882 conflict_allocno
= ALLOCNO_FIRST_COALESCED_ALLOCNO (conflict_allocno
);
883 if (bitmap_bit_p (coloring_allocno_bitmap
,
884 ALLOCNO_NUM (conflict_allocno
)))
886 ira_assert (cover_class
887 == ALLOCNO_COVER_CLASS (conflict_allocno
));
888 if (allocno_coalesced_p
)
890 if (bitmap_bit_p (processed_coalesced_allocno_bitmap
,
891 ALLOCNO_NUM (conflict_allocno
)))
893 bitmap_set_bit (processed_coalesced_allocno_bitmap
,
894 ALLOCNO_NUM (conflict_allocno
));
896 if (ALLOCNO_IN_GRAPH_P (conflict_allocno
)
897 && ! ALLOCNO_ASSIGNED_P (conflict_allocno
))
900 = ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno
);
902 = (ira_reg_class_nregs
903 [cover_class
][ALLOCNO_MODE (conflict_allocno
)]);
905 (ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno
) >= size
);
906 if (left_conflicts_size
+ conflict_size
907 <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno
))
909 ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno
) -= size
;
913 = ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno
) - size
;
914 if (uncolorable_allocnos_splay_tree
[cover_class
] != NULL
915 && !ALLOCNO_SPLAY_REMOVED_P (conflict_allocno
)
916 && USE_SPLAY_P (cover_class
))
920 (uncolorable_allocnos_splay_tree
[cover_class
],
921 (splay_tree_key
) conflict_allocno
) != NULL
);
923 (uncolorable_allocnos_splay_tree
[cover_class
],
924 (splay_tree_key
) conflict_allocno
);
925 ALLOCNO_SPLAY_REMOVED_P (conflict_allocno
) = true;
926 VEC_safe_push (ira_allocno_t
, heap
,
927 removed_splay_allocno_vec
,
930 ALLOCNO_LEFT_CONFLICTS_SIZE (conflict_allocno
)
931 = left_conflicts_size
;
932 if (left_conflicts_size
+ conflict_size
933 <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno
))
935 delete_allocno_from_bucket
936 (conflict_allocno
, &uncolorable_allocno_bucket
);
937 add_allocno_to_ordered_bucket
938 (conflict_allocno
, &colorable_allocno_bucket
);
948 /* Put ALLOCNO onto the coloring stack and remove it from its bucket.
949 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
951 remove_allocno_from_bucket_and_push (ira_allocno_t allocno
, bool colorable_p
)
953 enum reg_class cover_class
;
956 delete_allocno_from_bucket (allocno
, &colorable_allocno_bucket
);
958 delete_allocno_from_bucket (allocno
, &uncolorable_allocno_bucket
);
959 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
961 fprintf (ira_dump_file
, " Pushing");
962 print_coalesced_allocno (allocno
);
964 fprintf (ira_dump_file
, "\n");
966 fprintf (ira_dump_file
, "(potential spill: %spri=%d, cost=%d)\n",
967 ALLOCNO_BAD_SPILL_P (allocno
) ? "bad spill, " : "",
968 allocno_spill_priority (allocno
), ALLOCNO_TEMP (allocno
));
970 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
971 ira_assert ((colorable_p
972 && (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno
)
973 + ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE (allocno
)]
974 <= ALLOCNO_AVAILABLE_REGS_NUM (allocno
)))
976 && (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno
)
977 + ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE
979 > ALLOCNO_AVAILABLE_REGS_NUM (allocno
))));
981 ALLOCNO_MAY_BE_SPILLED_P (allocno
) = true;
982 push_allocno_to_stack (allocno
);
985 /* Put all allocnos from colorable bucket onto the coloring stack. */
987 push_only_colorable (void)
989 sort_bucket (&colorable_allocno_bucket
);
990 for (;colorable_allocno_bucket
!= NULL
;)
991 remove_allocno_from_bucket_and_push (colorable_allocno_bucket
, true);
994 /* Puts ALLOCNO chosen for potential spilling onto the coloring
997 push_allocno_to_spill (ira_allocno_t allocno
)
999 delete_allocno_from_bucket (allocno
, &uncolorable_allocno_bucket
);
1000 ALLOCNO_MAY_BE_SPILLED_P (allocno
) = true;
1001 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1002 fprintf (ira_dump_file
, " Pushing p%d(%d) (spill for NO_REGS)\n",
1003 ALLOCNO_NUM (allocno
), ALLOCNO_REGNO (allocno
));
1004 push_allocno_to_stack (allocno
);
1007 /* Return the frequency of exit edges (if EXIT_P) or entry from/to the
1008 loop given by its LOOP_NODE. */
1010 ira_loop_edge_freq (ira_loop_tree_node_t loop_node
, int regno
, bool exit_p
)
1015 VEC (edge
, heap
) *edges
;
1017 ira_assert (loop_node
->loop
!= NULL
1018 && (regno
< 0 || regno
>= FIRST_PSEUDO_REGISTER
));
1022 FOR_EACH_EDGE (e
, ei
, loop_node
->loop
->header
->preds
)
1023 if (e
->src
!= loop_node
->loop
->latch
1025 || (bitmap_bit_p (DF_LR_OUT (e
->src
), regno
)
1026 && bitmap_bit_p (DF_LR_IN (e
->dest
), regno
))))
1027 freq
+= EDGE_FREQUENCY (e
);
1031 edges
= get_loop_exit_edges (loop_node
->loop
);
1032 for (i
= 0; VEC_iterate (edge
, edges
, i
, e
); i
++)
1034 || (bitmap_bit_p (DF_LR_OUT (e
->src
), regno
)
1035 && bitmap_bit_p (DF_LR_IN (e
->dest
), regno
)))
1036 freq
+= EDGE_FREQUENCY (e
);
1037 VEC_free (edge
, heap
, edges
);
1040 return REG_FREQ_FROM_EDGE_FREQ (freq
);
1043 /* Calculate and return the cost of putting allocno A into memory. */
1045 calculate_allocno_spill_cost (ira_allocno_t a
)
1048 enum machine_mode mode
;
1049 enum reg_class rclass
;
1050 ira_allocno_t parent_allocno
;
1051 ira_loop_tree_node_t parent_node
, loop_node
;
1053 regno
= ALLOCNO_REGNO (a
);
1054 cost
= ALLOCNO_UPDATED_MEMORY_COST (a
) - ALLOCNO_UPDATED_COVER_CLASS_COST (a
);
1055 if (ALLOCNO_CAP (a
) != NULL
)
1057 loop_node
= ALLOCNO_LOOP_TREE_NODE (a
);
1058 if ((parent_node
= loop_node
->parent
) == NULL
)
1060 if ((parent_allocno
= parent_node
->regno_allocno_map
[regno
]) == NULL
)
1062 mode
= ALLOCNO_MODE (a
);
1063 rclass
= ALLOCNO_COVER_CLASS (a
);
1064 if (ALLOCNO_HARD_REGNO (parent_allocno
) < 0)
1065 cost
-= (ira_memory_move_cost
[mode
][rclass
][0]
1066 * ira_loop_edge_freq (loop_node
, regno
, true)
1067 + ira_memory_move_cost
[mode
][rclass
][1]
1068 * ira_loop_edge_freq (loop_node
, regno
, false));
1070 cost
+= ((ira_memory_move_cost
[mode
][rclass
][1]
1071 * ira_loop_edge_freq (loop_node
, regno
, true)
1072 + ira_memory_move_cost
[mode
][rclass
][0]
1073 * ira_loop_edge_freq (loop_node
, regno
, false))
1074 - (ira_get_register_move_cost (mode
, rclass
, rclass
)
1075 * (ira_loop_edge_freq (loop_node
, regno
, false)
1076 + ira_loop_edge_freq (loop_node
, regno
, true))));
1080 /* Compare keys in the splay tree used to choose best allocno for
1081 spilling. The best allocno has the minimal key. */
1083 allocno_spill_priority_compare (splay_tree_key k1
, splay_tree_key k2
)
1085 int pri1
, pri2
, diff
;
1086 ira_allocno_t a1
= (ira_allocno_t
) k1
, a2
= (ira_allocno_t
) k2
;
1088 pri1
= (ALLOCNO_TEMP (a1
)
1089 / (ALLOCNO_LEFT_CONFLICTS_SIZE (a1
)
1090 * ira_reg_class_nregs
[ALLOCNO_COVER_CLASS (a1
)][ALLOCNO_MODE (a1
)]
1092 pri2
= (ALLOCNO_TEMP (a2
)
1093 / (ALLOCNO_LEFT_CONFLICTS_SIZE (a2
)
1094 * ira_reg_class_nregs
[ALLOCNO_COVER_CLASS (a2
)][ALLOCNO_MODE (a2
)]
1096 if ((diff
= pri1
- pri2
) != 0)
1098 if ((diff
= ALLOCNO_TEMP (a1
) - ALLOCNO_TEMP (a2
)) != 0)
1100 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
1103 /* Allocate data of SIZE for the splay trees. We allocate only spay
1104 tree roots or splay tree nodes. If you change this, please rewrite
1107 splay_tree_allocate (int size
, void *data ATTRIBUTE_UNUSED
)
1109 if (size
!= sizeof (struct splay_tree_node_s
))
1110 return ira_allocate (size
);
1111 return pool_alloc (splay_tree_node_pool
);
1114 /* Free data NODE for the splay trees. We allocate and free only spay
1115 tree roots or splay tree nodes. If you change this, please rewrite
1118 splay_tree_free (void *node
, void *data ATTRIBUTE_UNUSED
)
1121 enum reg_class cover_class
;
1123 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1125 cover_class
= ira_reg_class_cover
[i
];
1126 if (node
== uncolorable_allocnos_splay_tree
[cover_class
])
1132 pool_free (splay_tree_node_pool
, node
);
1135 /* Push allocnos to the coloring stack. The order of allocnos in the
1136 stack defines the order for the subsequent coloring. */
1138 push_allocnos_to_stack (void)
1140 ira_allocno_t allocno
, a
, i_allocno
, *allocno_vec
;
1141 enum reg_class cover_class
, rclass
;
1142 int allocno_pri
, i_allocno_pri
, allocno_cost
, i_allocno_cost
;
1143 int i
, j
, num
, cover_class_allocnos_num
[N_REG_CLASSES
];
1144 ira_allocno_t
*cover_class_allocnos
[N_REG_CLASSES
];
1148 VEC_truncate(ira_allocno_t
, removed_splay_allocno_vec
, 0);
1149 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1151 cover_class
= ira_reg_class_cover
[i
];
1152 cover_class_allocnos_num
[cover_class
] = 0;
1153 cover_class_allocnos
[cover_class
] = NULL
;
1154 uncolorable_allocnos_splay_tree
[cover_class
] = NULL
;
1156 /* Calculate uncolorable allocno spill costs. */
1157 for (allocno
= uncolorable_allocno_bucket
;
1159 allocno
= ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno
))
1160 if ((cover_class
= ALLOCNO_COVER_CLASS (allocno
)) != NO_REGS
)
1162 cover_class_allocnos_num
[cover_class
]++;
1164 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
1165 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1167 cost
+= calculate_allocno_spill_cost (a
);
1171 /* ??? Remove cost of copies between the coalesced
1173 ALLOCNO_TEMP (allocno
) = cost
;
1175 /* Define place where to put uncolorable allocnos of the same cover
1177 for (num
= i
= 0; i
< ira_reg_class_cover_size
; i
++)
1179 cover_class
= ira_reg_class_cover
[i
];
1180 ira_assert (cover_class_allocnos_num
[cover_class
]
1181 == uncolorable_allocnos_num
[cover_class
]);
1182 if (cover_class_allocnos_num
[cover_class
] != 0)
1184 cover_class_allocnos
[cover_class
] = allocnos_for_spilling
+ num
;
1185 num
+= cover_class_allocnos_num
[cover_class
];
1186 cover_class_allocnos_num
[cover_class
] = 0;
1188 if (USE_SPLAY_P (cover_class
))
1189 uncolorable_allocnos_splay_tree
[cover_class
]
1190 = splay_tree_new_with_allocator (allocno_spill_priority_compare
,
1191 NULL
, NULL
, splay_tree_allocate
,
1192 splay_tree_free
, NULL
);
1194 ira_assert (num
<= ira_allocnos_num
);
1195 /* Collect uncolorable allocnos of each cover class. */
1196 for (allocno
= uncolorable_allocno_bucket
;
1198 allocno
= ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno
))
1199 if ((cover_class
= ALLOCNO_COVER_CLASS (allocno
)) != NO_REGS
)
1201 cover_class_allocnos
1202 [cover_class
][cover_class_allocnos_num
[cover_class
]++] = allocno
;
1203 if (uncolorable_allocnos_splay_tree
[cover_class
] != NULL
)
1204 splay_tree_insert (uncolorable_allocnos_splay_tree
[cover_class
],
1205 (splay_tree_key
) allocno
,
1206 (splay_tree_value
) allocno
);
1210 push_only_colorable ();
1211 allocno
= uncolorable_allocno_bucket
;
1212 if (allocno
== NULL
)
1214 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
1215 if (cover_class
== NO_REGS
)
1217 push_allocno_to_spill (allocno
);
1220 /* Potential spilling. */
1222 (ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE (allocno
)] > 0);
1223 if (USE_SPLAY_P (cover_class
))
1225 for (;VEC_length (ira_allocno_t
, removed_splay_allocno_vec
) != 0;)
1227 allocno
= VEC_pop (ira_allocno_t
, removed_splay_allocno_vec
);
1228 ALLOCNO_SPLAY_REMOVED_P (allocno
) = false;
1229 rclass
= ALLOCNO_COVER_CLASS (allocno
);
1230 if (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno
)
1231 + ira_reg_class_nregs
[rclass
][ALLOCNO_MODE (allocno
)]
1232 > ALLOCNO_AVAILABLE_REGS_NUM (allocno
))
1234 (uncolorable_allocnos_splay_tree
[rclass
],
1235 (splay_tree_key
) allocno
, (splay_tree_value
) allocno
);
1237 allocno
= ((ira_allocno_t
)
1239 (uncolorable_allocnos_splay_tree
[cover_class
])->key
);
1240 splay_tree_remove (uncolorable_allocnos_splay_tree
[cover_class
],
1241 (splay_tree_key
) allocno
);
1245 num
= cover_class_allocnos_num
[cover_class
];
1246 ira_assert (num
> 0);
1247 allocno_vec
= cover_class_allocnos
[cover_class
];
1249 allocno_pri
= allocno_cost
= 0;
1250 /* Sort uncolorable allocno to find the one with the lowest
1252 for (i
= 0, j
= num
- 1; i
<= j
;)
1254 i_allocno
= allocno_vec
[i
];
1255 if (! ALLOCNO_IN_GRAPH_P (i_allocno
)
1256 && ALLOCNO_IN_GRAPH_P (allocno_vec
[j
]))
1258 i_allocno
= allocno_vec
[j
];
1259 allocno_vec
[j
] = allocno_vec
[i
];
1260 allocno_vec
[i
] = i_allocno
;
1262 if (ALLOCNO_IN_GRAPH_P (i_allocno
))
1265 ira_assert (ALLOCNO_TEMP (i_allocno
) != INT_MAX
);
1266 i_allocno_cost
= ALLOCNO_TEMP (i_allocno
);
1267 i_allocno_pri
= allocno_spill_priority (i_allocno
);
1269 || (! ALLOCNO_BAD_SPILL_P (i_allocno
)
1270 && ALLOCNO_BAD_SPILL_P (allocno
))
1271 || (! (ALLOCNO_BAD_SPILL_P (i_allocno
)
1272 && ! ALLOCNO_BAD_SPILL_P (allocno
))
1273 && (allocno_pri
> i_allocno_pri
1274 || (allocno_pri
== i_allocno_pri
1275 && (allocno_cost
> i_allocno_cost
1276 || (allocno_cost
== i_allocno_cost
1277 && (ALLOCNO_NUM (allocno
)
1278 > ALLOCNO_NUM (i_allocno
))))))))
1280 allocno
= i_allocno
;
1281 allocno_cost
= i_allocno_cost
;
1282 allocno_pri
= i_allocno_pri
;
1285 if (! ALLOCNO_IN_GRAPH_P (allocno_vec
[j
]))
1288 ira_assert (allocno
!= NULL
&& j
>= 0);
1289 cover_class_allocnos_num
[cover_class
] = j
+ 1;
1291 ira_assert (ALLOCNO_IN_GRAPH_P (allocno
)
1292 && ALLOCNO_COVER_CLASS (allocno
) == cover_class
1293 && (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno
)
1294 + ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE
1296 > ALLOCNO_AVAILABLE_REGS_NUM (allocno
)));
1297 remove_allocno_from_bucket_and_push (allocno
, false);
1299 ira_assert (colorable_allocno_bucket
== NULL
1300 && uncolorable_allocno_bucket
== NULL
);
1301 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1303 cover_class
= ira_reg_class_cover
[i
];
1304 ira_assert (uncolorable_allocnos_num
[cover_class
] == 0);
1305 if (uncolorable_allocnos_splay_tree
[cover_class
] != NULL
)
1306 splay_tree_delete (uncolorable_allocnos_splay_tree
[cover_class
]);
1310 /* Pop the coloring stack and assign hard registers to the popped
1313 pop_allocnos_from_stack (void)
1315 ira_allocno_t allocno
;
1316 enum reg_class cover_class
;
1318 for (;VEC_length (ira_allocno_t
, allocno_stack_vec
) != 0;)
1320 allocno
= VEC_pop (ira_allocno_t
, allocno_stack_vec
);
1321 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
1322 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1324 fprintf (ira_dump_file
, " Popping");
1325 print_coalesced_allocno (allocno
);
1326 fprintf (ira_dump_file
, " -- ");
1328 if (cover_class
== NO_REGS
)
1330 ALLOCNO_HARD_REGNO (allocno
) = -1;
1331 ALLOCNO_ASSIGNED_P (allocno
) = true;
1332 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno
) == NULL
);
1334 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno
) == NULL
);
1335 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1336 fprintf (ira_dump_file
, "assign memory\n");
1338 else if (assign_hard_reg (allocno
, false))
1340 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1341 fprintf (ira_dump_file
, "assign reg %d\n",
1342 ALLOCNO_HARD_REGNO (allocno
));
1344 else if (ALLOCNO_ASSIGNED_P (allocno
))
1346 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1347 fprintf (ira_dump_file
, "spill\n");
1349 ALLOCNO_IN_GRAPH_P (allocno
) = true;
1353 /* Set up number of available hard registers for ALLOCNO. */
1355 setup_allocno_available_regs_num (ira_allocno_t allocno
)
1357 int i
, n
, hard_regs_num
;
1358 enum reg_class cover_class
;
1360 HARD_REG_SET temp_set
;
1362 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
1363 ALLOCNO_AVAILABLE_REGS_NUM (allocno
) = ira_available_class_regs
[cover_class
];
1364 if (cover_class
== NO_REGS
)
1366 CLEAR_HARD_REG_SET (temp_set
);
1367 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) == allocno
);
1368 hard_regs_num
= ira_class_hard_regs_num
[cover_class
];
1369 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
1370 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1372 IOR_HARD_REG_SET (temp_set
, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
1376 for (n
= 0, i
= hard_regs_num
- 1; i
>= 0; i
--)
1377 if (TEST_HARD_REG_BIT (temp_set
, ira_class_hard_regs
[cover_class
][i
]))
1379 if (internal_flag_ira_verbose
> 2 && n
> 0 && ira_dump_file
!= NULL
)
1380 fprintf (ira_dump_file
, " Reg %d of %s has %d regs less\n",
1381 ALLOCNO_REGNO (allocno
), reg_class_names
[cover_class
], n
);
1382 ALLOCNO_AVAILABLE_REGS_NUM (allocno
) -= n
;
1385 /* Set up ALLOCNO_LEFT_CONFLICTS_SIZE for ALLOCNO. */
1387 setup_allocno_left_conflicts_size (ira_allocno_t allocno
)
1389 int i
, hard_regs_num
, hard_regno
, conflict_allocnos_size
;
1390 ira_allocno_t a
, conflict_allocno
;
1391 enum reg_class cover_class
;
1392 HARD_REG_SET temp_set
;
1393 ira_allocno_conflict_iterator aci
;
1395 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
1396 hard_regs_num
= ira_class_hard_regs_num
[cover_class
];
1397 CLEAR_HARD_REG_SET (temp_set
);
1398 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) == allocno
);
1399 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
1400 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1402 IOR_HARD_REG_SET (temp_set
, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
1406 AND_HARD_REG_SET (temp_set
, reg_class_contents
[cover_class
]);
1407 AND_COMPL_HARD_REG_SET (temp_set
, ira_no_alloc_regs
);
1408 conflict_allocnos_size
= 0;
1409 if (! hard_reg_set_empty_p (temp_set
))
1410 for (i
= 0; i
< (int) hard_regs_num
; i
++)
1412 hard_regno
= ira_class_hard_regs
[cover_class
][i
];
1413 if (TEST_HARD_REG_BIT (temp_set
, hard_regno
))
1415 conflict_allocnos_size
++;
1416 CLEAR_HARD_REG_BIT (temp_set
, hard_regno
);
1417 if (hard_reg_set_empty_p (temp_set
))
1421 CLEAR_HARD_REG_SET (temp_set
);
1422 if (allocno_coalesced_p
)
1423 bitmap_clear (processed_coalesced_allocno_bitmap
);
1424 if (cover_class
!= NO_REGS
)
1425 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
1426 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1428 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_allocno
, aci
)
1431 = ALLOCNO_FIRST_COALESCED_ALLOCNO (conflict_allocno
);
1432 if (bitmap_bit_p (consideration_allocno_bitmap
,
1433 ALLOCNO_NUM (conflict_allocno
)))
1435 ira_assert (cover_class
1436 == ALLOCNO_COVER_CLASS (conflict_allocno
));
1437 if (allocno_coalesced_p
)
1439 if (bitmap_bit_p (processed_coalesced_allocno_bitmap
,
1440 ALLOCNO_NUM (conflict_allocno
)))
1442 bitmap_set_bit (processed_coalesced_allocno_bitmap
,
1443 ALLOCNO_NUM (conflict_allocno
));
1445 if (! ALLOCNO_ASSIGNED_P (conflict_allocno
))
1446 conflict_allocnos_size
1447 += (ira_reg_class_nregs
1448 [cover_class
][ALLOCNO_MODE (conflict_allocno
)]);
1449 else if ((hard_regno
= ALLOCNO_HARD_REGNO (conflict_allocno
))
1452 int last
= (hard_regno
1454 [hard_regno
][ALLOCNO_MODE (conflict_allocno
)]);
1456 while (hard_regno
< last
)
1458 if (! TEST_HARD_REG_BIT (temp_set
, hard_regno
))
1460 conflict_allocnos_size
++;
1461 SET_HARD_REG_BIT (temp_set
, hard_regno
);
1471 ALLOCNO_LEFT_CONFLICTS_SIZE (allocno
) = conflict_allocnos_size
;
1474 /* Put ALLOCNO in a bucket corresponding to its number and size of its
1475 conflicting allocnos and hard registers. */
1477 put_allocno_into_bucket (ira_allocno_t allocno
)
1479 enum reg_class cover_class
;
1481 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
1482 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) != allocno
)
1484 ALLOCNO_IN_GRAPH_P (allocno
) = true;
1485 setup_allocno_left_conflicts_size (allocno
);
1486 setup_allocno_available_regs_num (allocno
);
1487 if (ALLOCNO_LEFT_CONFLICTS_SIZE (allocno
)
1488 + ira_reg_class_nregs
[cover_class
][ALLOCNO_MODE (allocno
)]
1489 <= ALLOCNO_AVAILABLE_REGS_NUM (allocno
))
1490 add_allocno_to_bucket (allocno
, &colorable_allocno_bucket
);
1492 add_allocno_to_bucket (allocno
, &uncolorable_allocno_bucket
);
1495 /* The function is used to sort allocnos according to their execution
1498 copy_freq_compare_func (const void *v1p
, const void *v2p
)
1500 ira_copy_t cp1
= *(const ira_copy_t
*) v1p
, cp2
= *(const ira_copy_t
*) v2p
;
1508 /* If freqencies are equal, sort by copies, so that the results of
1509 qsort leave nothing to chance. */
1510 return cp1
->num
- cp2
->num
;
1513 /* Merge two sets of coalesced allocnos given correspondingly by
1514 allocnos A1 and A2 (more accurately merging A2 set into A1
1517 merge_allocnos (ira_allocno_t a1
, ira_allocno_t a2
)
1519 ira_allocno_t a
, first
, last
, next
;
1521 first
= ALLOCNO_FIRST_COALESCED_ALLOCNO (a1
);
1522 if (first
== ALLOCNO_FIRST_COALESCED_ALLOCNO (a2
))
1524 for (last
= a2
, a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a2
);;
1525 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1527 ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) = first
;
1532 next
= ALLOCNO_NEXT_COALESCED_ALLOCNO (first
);
1533 ALLOCNO_NEXT_COALESCED_ALLOCNO (first
) = a2
;
1534 ALLOCNO_NEXT_COALESCED_ALLOCNO (last
) = next
;
1537 /* Return TRUE if there are conflicting allocnos from two sets of
1538 coalesced allocnos given correspondingly by allocnos A1 and A2. If
1539 RELOAD_P is TRUE, we use live ranges to find conflicts because
1540 conflicts are represented only for allocnos of the same cover class
1541 and during the reload pass we coalesce allocnos for sharing stack
1544 coalesced_allocno_conflict_p (ira_allocno_t a1
, ira_allocno_t a2
,
1547 ira_allocno_t a
, conflict_allocno
;
1548 ira_allocno_conflict_iterator aci
;
1550 if (allocno_coalesced_p
)
1552 bitmap_clear (processed_coalesced_allocno_bitmap
);
1553 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a1
);;
1554 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1556 bitmap_set_bit (processed_coalesced_allocno_bitmap
, ALLOCNO_NUM (a
));
1561 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a2
);;
1562 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
1566 for (conflict_allocno
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a1
);;
1568 = ALLOCNO_NEXT_COALESCED_ALLOCNO (conflict_allocno
))
1570 if (allocnos_have_intersected_live_ranges_p (a
,
1573 if (conflict_allocno
== a1
)
1579 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_allocno
, aci
)
1580 if (conflict_allocno
== a1
1581 || (allocno_coalesced_p
1582 && bitmap_bit_p (processed_coalesced_allocno_bitmap
,
1583 ALLOCNO_NUM (conflict_allocno
))))
1592 /* The major function for aggressive allocno coalescing. For the
1593 reload pass (RELOAD_P) we coalesce only spilled allocnos. If some
1594 allocnos have been coalesced, we set up flag
1595 allocno_coalesced_p. */
1597 coalesce_allocnos (bool reload_p
)
1600 ira_copy_t cp
, next_cp
, *sorted_copies
;
1601 enum reg_class cover_class
;
1602 enum machine_mode mode
;
1604 int i
, n
, cp_num
, regno
;
1607 sorted_copies
= (ira_copy_t
*) ira_allocate (ira_copies_num
1608 * sizeof (ira_copy_t
));
1610 /* Collect copies. */
1611 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, j
, bi
)
1613 a
= ira_allocnos
[j
];
1614 regno
= ALLOCNO_REGNO (a
);
1615 if ((! reload_p
&& ALLOCNO_ASSIGNED_P (a
))
1617 && (! ALLOCNO_ASSIGNED_P (a
) || ALLOCNO_HARD_REGNO (a
) >= 0
1618 || (regno
< ira_reg_equiv_len
1619 && (ira_reg_equiv_const
[regno
] != NULL_RTX
1620 || ira_reg_equiv_invariant_p
[regno
])))))
1622 cover_class
= ALLOCNO_COVER_CLASS (a
);
1623 mode
= ALLOCNO_MODE (a
);
1624 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
1628 next_cp
= cp
->next_first_allocno_copy
;
1629 regno
= ALLOCNO_REGNO (cp
->second
);
1630 /* For priority coloring we coalesce allocnos only with
1631 the same cover class not with intersected cover
1632 classes as it were possible. It is done for
1635 || (ALLOCNO_COVER_CLASS (cp
->second
) == cover_class
1636 && ALLOCNO_MODE (cp
->second
) == mode
))
1637 && (cp
->insn
!= NULL
|| cp
->constraint_p
)
1638 && ((! reload_p
&& ! ALLOCNO_ASSIGNED_P (cp
->second
))
1640 && ALLOCNO_ASSIGNED_P (cp
->second
)
1641 && ALLOCNO_HARD_REGNO (cp
->second
) < 0
1642 && (regno
>= ira_reg_equiv_len
1643 || (! ira_reg_equiv_invariant_p
[regno
]
1644 && ira_reg_equiv_const
[regno
] == NULL_RTX
)))))
1645 sorted_copies
[cp_num
++] = cp
;
1647 else if (cp
->second
== a
)
1648 next_cp
= cp
->next_second_allocno_copy
;
1653 qsort (sorted_copies
, cp_num
, sizeof (ira_copy_t
), copy_freq_compare_func
);
1654 /* Coalesced copies, most frequently executed first. */
1655 for (; cp_num
!= 0;)
1657 for (i
= 0; i
< cp_num
; i
++)
1659 cp
= sorted_copies
[i
];
1660 if (! coalesced_allocno_conflict_p (cp
->first
, cp
->second
, reload_p
))
1662 allocno_coalesced_p
= true;
1663 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1666 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
1667 cp
->num
, ALLOCNO_NUM (cp
->first
), ALLOCNO_REGNO (cp
->first
),
1668 ALLOCNO_NUM (cp
->second
), ALLOCNO_REGNO (cp
->second
),
1670 merge_allocnos (cp
->first
, cp
->second
);
1675 /* Collect the rest of copies. */
1676 for (n
= 0; i
< cp_num
; i
++)
1678 cp
= sorted_copies
[i
];
1679 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (cp
->first
)
1680 != ALLOCNO_FIRST_COALESCED_ALLOCNO (cp
->second
))
1681 sorted_copies
[n
++] = cp
;
1685 ira_free (sorted_copies
);
1688 /* Map: allocno number -> allocno priority. */
1689 static int *allocno_priorities
;
1691 /* Set up priorities for N allocnos in array
1692 CONSIDERATION_ALLOCNOS. */
1694 setup_allocno_priorities (ira_allocno_t
*consideration_allocnos
, int n
)
1696 int i
, length
, nrefs
, priority
, max_priority
, mult
;
1700 for (i
= 0; i
< n
; i
++)
1702 a
= consideration_allocnos
[i
];
1703 nrefs
= ALLOCNO_NREFS (a
);
1704 ira_assert (nrefs
>= 0);
1705 mult
= floor_log2 (ALLOCNO_NREFS (a
)) + 1;
1706 ira_assert (mult
>= 0);
1707 allocno_priorities
[ALLOCNO_NUM (a
)]
1710 * (ALLOCNO_MEMORY_COST (a
) - ALLOCNO_COVER_CLASS_COST (a
))
1711 * ira_reg_class_nregs
[ALLOCNO_COVER_CLASS (a
)][ALLOCNO_MODE (a
)]);
1713 priority
= -priority
;
1714 if (max_priority
< priority
)
1715 max_priority
= priority
;
1717 mult
= max_priority
== 0 ? 1 : INT_MAX
/ max_priority
;
1718 for (i
= 0; i
< n
; i
++)
1720 a
= consideration_allocnos
[i
];
1721 length
= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
1724 allocno_priorities
[ALLOCNO_NUM (a
)]
1725 = allocno_priorities
[ALLOCNO_NUM (a
)] * mult
/ length
;
1729 /* Sort allocnos according to their priorities which are calculated
1730 analogous to ones in file `global.c'. */
1732 allocno_priority_compare_func (const void *v1p
, const void *v2p
)
1734 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
1735 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
1738 pri1
= allocno_priorities
[ALLOCNO_NUM (a1
)];
1739 pri2
= allocno_priorities
[ALLOCNO_NUM (a2
)];
1743 /* If regs are equally good, sort by allocnos, so that the results of
1744 qsort leave nothing to chance. */
1745 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
1748 /* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
1749 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
1751 color_allocnos (void)
1757 allocno_coalesced_p
= false;
1758 processed_coalesced_allocno_bitmap
= ira_allocate_bitmap ();
1759 if (flag_ira_coalesce
)
1760 coalesce_allocnos (false);
1761 if (flag_ira_algorithm
== IRA_ALGORITHM_PRIORITY
)
1764 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
1766 a
= ira_allocnos
[i
];
1767 if (ALLOCNO_COVER_CLASS (a
) == NO_REGS
)
1769 ALLOCNO_HARD_REGNO (a
) = -1;
1770 ALLOCNO_ASSIGNED_P (a
) = true;
1771 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
1772 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
1773 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1775 fprintf (ira_dump_file
, " Spill");
1776 print_coalesced_allocno (a
);
1777 fprintf (ira_dump_file
, "\n");
1781 sorted_allocnos
[n
++] = a
;
1785 setup_allocno_priorities (sorted_allocnos
, n
);
1786 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
),
1787 allocno_priority_compare_func
);
1788 for (i
= 0; i
< n
; i
++)
1790 a
= sorted_allocnos
[i
];
1791 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1793 fprintf (ira_dump_file
, " ");
1794 print_coalesced_allocno (a
);
1795 fprintf (ira_dump_file
, " -- ");
1797 if (assign_hard_reg (a
, false))
1799 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1800 fprintf (ira_dump_file
, "assign hard reg %d\n",
1801 ALLOCNO_HARD_REGNO (a
));
1805 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1806 fprintf (ira_dump_file
, "assign memory\n");
1813 /* Put the allocnos into the corresponding buckets. */
1814 colorable_allocno_bucket
= NULL
;
1815 uncolorable_allocno_bucket
= NULL
;
1816 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
1818 a
= ira_allocnos
[i
];
1819 if (ALLOCNO_COVER_CLASS (a
) == NO_REGS
)
1821 ALLOCNO_HARD_REGNO (a
) = -1;
1822 ALLOCNO_ASSIGNED_P (a
) = true;
1823 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
1824 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
1825 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
1827 fprintf (ira_dump_file
, " Spill");
1828 print_coalesced_allocno (a
);
1829 fprintf (ira_dump_file
, "\n");
1833 put_allocno_into_bucket (a
);
1835 push_allocnos_to_stack ();
1836 pop_allocnos_from_stack ();
1838 if (flag_ira_coalesce
)
1839 /* We don't need coalesced allocnos for ira_reassign_pseudos. */
1840 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap
, 0, i
, bi
)
1842 a
= ira_allocnos
[i
];
1843 ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) = a
;
1844 ALLOCNO_NEXT_COALESCED_ALLOCNO (a
) = a
;
1846 ira_free_bitmap (processed_coalesced_allocno_bitmap
);
1847 allocno_coalesced_p
= false;
1852 /* Output information about the loop given by its LOOP_TREE_NODE. */
1854 print_loop_title (ira_loop_tree_node_t loop_tree_node
)
1858 ira_loop_tree_node_t subloop_node
, dest_loop_node
;
1862 ira_assert (loop_tree_node
->loop
!= NULL
);
1863 fprintf (ira_dump_file
,
1864 "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
1865 loop_tree_node
->loop
->num
,
1866 (loop_tree_node
->parent
== NULL
1867 ? -1 : loop_tree_node
->parent
->loop
->num
),
1868 loop_tree_node
->loop
->header
->index
,
1869 loop_depth (loop_tree_node
->loop
));
1870 for (subloop_node
= loop_tree_node
->children
;
1871 subloop_node
!= NULL
;
1872 subloop_node
= subloop_node
->next
)
1873 if (subloop_node
->bb
!= NULL
)
1875 fprintf (ira_dump_file
, " %d", subloop_node
->bb
->index
);
1876 FOR_EACH_EDGE (e
, ei
, subloop_node
->bb
->succs
)
1877 if (e
->dest
!= EXIT_BLOCK_PTR
1878 && ((dest_loop_node
= IRA_BB_NODE (e
->dest
)->parent
)
1880 fprintf (ira_dump_file
, "(->%d:l%d)",
1881 e
->dest
->index
, dest_loop_node
->loop
->num
);
1883 fprintf (ira_dump_file
, "\n all:");
1884 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->all_allocnos
, 0, j
, bi
)
1885 fprintf (ira_dump_file
, " %dr%d", j
, ALLOCNO_REGNO (ira_allocnos
[j
]));
1886 fprintf (ira_dump_file
, "\n modified regnos:");
1887 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->modified_regnos
, 0, j
, bi
)
1888 fprintf (ira_dump_file
, " %d", j
);
1889 fprintf (ira_dump_file
, "\n border:");
1890 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->border_allocnos
, 0, j
, bi
)
1891 fprintf (ira_dump_file
, " %dr%d", j
, ALLOCNO_REGNO (ira_allocnos
[j
]));
1892 fprintf (ira_dump_file
, "\n Pressure:");
1893 for (j
= 0; (int) j
< ira_reg_class_cover_size
; j
++)
1895 enum reg_class cover_class
;
1897 cover_class
= ira_reg_class_cover
[j
];
1898 if (loop_tree_node
->reg_pressure
[cover_class
] == 0)
1900 fprintf (ira_dump_file
, " %s=%d", reg_class_names
[cover_class
],
1901 loop_tree_node
->reg_pressure
[cover_class
]);
1903 fprintf (ira_dump_file
, "\n");
1906 /* Color the allocnos inside loop (in the extreme case it can be all
1907 of the function) given the corresponding LOOP_TREE_NODE. The
1908 function is called for each loop during top-down traverse of the
1911 color_pass (ira_loop_tree_node_t loop_tree_node
)
1913 int regno
, hard_regno
, index
= -1;
1914 int cost
, exit_freq
, enter_freq
;
1917 enum machine_mode mode
;
1918 enum reg_class rclass
, cover_class
;
1919 ira_allocno_t a
, subloop_allocno
;
1920 ira_loop_tree_node_t subloop_node
;
1922 ira_assert (loop_tree_node
->bb
== NULL
);
1923 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
1924 print_loop_title (loop_tree_node
);
1926 bitmap_copy (coloring_allocno_bitmap
, loop_tree_node
->all_allocnos
);
1927 bitmap_copy (consideration_allocno_bitmap
, coloring_allocno_bitmap
);
1928 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
1930 a
= ira_allocnos
[j
];
1931 if (! ALLOCNO_ASSIGNED_P (a
))
1933 bitmap_clear_bit (coloring_allocno_bitmap
, ALLOCNO_NUM (a
));
1935 /* Color all mentioned allocnos including transparent ones. */
1937 /* Process caps. They are processed just once. */
1938 if (flag_ira_region
== IRA_REGION_MIXED
1939 || flag_ira_region
== IRA_REGION_ALL
)
1940 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node
->all_allocnos
, 0, j
, bi
)
1942 a
= ira_allocnos
[j
];
1943 if (ALLOCNO_CAP_MEMBER (a
) == NULL
)
1945 /* Remove from processing in the next loop. */
1946 bitmap_clear_bit (consideration_allocno_bitmap
, j
);
1947 rclass
= ALLOCNO_COVER_CLASS (a
);
1948 if (flag_ira_region
== IRA_REGION_MIXED
1949 && (loop_tree_node
->reg_pressure
[rclass
]
1950 <= ira_available_class_regs
[rclass
]))
1952 mode
= ALLOCNO_MODE (a
);
1953 hard_regno
= ALLOCNO_HARD_REGNO (a
);
1954 if (hard_regno
>= 0)
1956 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
1957 ira_assert (index
>= 0);
1959 regno
= ALLOCNO_REGNO (a
);
1960 subloop_allocno
= ALLOCNO_CAP_MEMBER (a
);
1961 subloop_node
= ALLOCNO_LOOP_TREE_NODE (subloop_allocno
);
1962 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno
));
1963 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
1964 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
1965 if (hard_regno
>= 0)
1966 update_copy_costs (subloop_allocno
, true);
1967 /* We don't need updated costs anymore: */
1968 ira_free_allocno_updated_costs (subloop_allocno
);
1971 /* Update costs of the corresponding allocnos (not caps) in the
1973 for (subloop_node
= loop_tree_node
->subloops
;
1974 subloop_node
!= NULL
;
1975 subloop_node
= subloop_node
->subloop_next
)
1977 ira_assert (subloop_node
->bb
== NULL
);
1978 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap
, 0, j
, bi
)
1980 a
= ira_allocnos
[j
];
1981 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
1982 mode
= ALLOCNO_MODE (a
);
1983 rclass
= ALLOCNO_COVER_CLASS (a
);
1984 hard_regno
= ALLOCNO_HARD_REGNO (a
);
1985 /* Use hard register class here. ??? */
1986 if (hard_regno
>= 0)
1988 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
1989 ira_assert (index
>= 0);
1991 regno
= ALLOCNO_REGNO (a
);
1992 /* ??? conflict costs */
1993 subloop_allocno
= subloop_node
->regno_allocno_map
[regno
];
1994 if (subloop_allocno
== NULL
1995 || ALLOCNO_CAP (subloop_allocno
) != NULL
)
1997 ira_assert (ALLOCNO_COVER_CLASS (subloop_allocno
) == rclass
);
1998 ira_assert (bitmap_bit_p (subloop_node
->all_allocnos
,
1999 ALLOCNO_NUM (subloop_allocno
)));
2000 if ((flag_ira_region
== IRA_REGION_MIXED
)
2001 && (loop_tree_node
->reg_pressure
[rclass
]
2002 <= ira_available_class_regs
[rclass
]))
2004 if (! ALLOCNO_ASSIGNED_P (subloop_allocno
))
2006 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
2007 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
2008 if (hard_regno
>= 0)
2009 update_copy_costs (subloop_allocno
, true);
2010 /* We don't need updated costs anymore: */
2011 ira_free_allocno_updated_costs (subloop_allocno
);
2015 exit_freq
= ira_loop_edge_freq (subloop_node
, regno
, true);
2016 enter_freq
= ira_loop_edge_freq (subloop_node
, regno
, false);
2017 ira_assert (regno
< ira_reg_equiv_len
);
2018 if (ira_reg_equiv_invariant_p
[regno
]
2019 || ira_reg_equiv_const
[regno
] != NULL_RTX
)
2021 if (! ALLOCNO_ASSIGNED_P (subloop_allocno
))
2023 ALLOCNO_HARD_REGNO (subloop_allocno
) = hard_regno
;
2024 ALLOCNO_ASSIGNED_P (subloop_allocno
) = true;
2025 if (hard_regno
>= 0)
2026 update_copy_costs (subloop_allocno
, true);
2027 /* We don't need updated costs anymore: */
2028 ira_free_allocno_updated_costs (subloop_allocno
);
2031 else if (hard_regno
< 0)
2033 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno
)
2034 -= ((ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
)
2035 + (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
));
2039 cover_class
= ALLOCNO_COVER_CLASS (subloop_allocno
);
2040 cost
= (ira_get_register_move_cost (mode
, rclass
, rclass
)
2041 * (exit_freq
+ enter_freq
));
2042 ira_allocate_and_set_or_copy_costs
2043 (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
), cover_class
,
2044 ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno
),
2045 ALLOCNO_HARD_REG_COSTS (subloop_allocno
));
2046 ira_allocate_and_set_or_copy_costs
2047 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno
),
2049 ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno
));
2050 ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
] -= cost
;
2051 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno
)[index
]
2053 if (ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno
)
2054 > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
])
2055 ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno
)
2056 = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno
)[index
];
2057 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno
)
2058 += (ira_memory_move_cost
[mode
][rclass
][0] * enter_freq
2059 + ira_memory_move_cost
[mode
][rclass
][1] * exit_freq
);
2065 /* Initialize the common data for coloring and calls functions to do
2066 Chaitin-Briggs and regional coloring. */
2070 coloring_allocno_bitmap
= ira_allocate_bitmap ();
2071 allocnos_for_spilling
2072 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
2073 * ira_allocnos_num
);
2074 splay_tree_node_pool
= create_alloc_pool ("splay tree nodes",
2075 sizeof (struct splay_tree_node_s
),
2077 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
2078 fprintf (ira_dump_file
, "\n**** Allocnos coloring:\n\n");
2080 ira_traverse_loop_tree (false, ira_loop_tree_root
, color_pass
, NULL
);
2082 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
2083 ira_print_disposition (ira_dump_file
);
2085 free_alloc_pool (splay_tree_node_pool
);
2086 ira_free_bitmap (coloring_allocno_bitmap
);
2087 ira_free (allocnos_for_spilling
);
2092 /* Move spill/restore code, which are to be generated in ira-emit.c,
2093 to less frequent points (if it is profitable) by reassigning some
2094 allocnos (in loop with subloops containing in another loop) to
2095 memory which results in longer live-range where the corresponding
2096 pseudo-registers will be in memory. */
2098 move_spill_restore (void)
2100 int cost
, regno
, hard_regno
, hard_regno2
, index
;
2102 int enter_freq
, exit_freq
;
2103 enum machine_mode mode
;
2104 enum reg_class rclass
;
2105 ira_allocno_t a
, parent_allocno
, subloop_allocno
;
2106 ira_loop_tree_node_t parent
, loop_node
, subloop_node
;
2107 ira_allocno_iterator ai
;
2112 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
2113 fprintf (ira_dump_file
, "New iteration of spill/restore move\n");
2114 FOR_EACH_ALLOCNO (a
, ai
)
2116 regno
= ALLOCNO_REGNO (a
);
2117 loop_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2118 if (ALLOCNO_CAP_MEMBER (a
) != NULL
2119 || ALLOCNO_CAP (a
) != NULL
2120 || (hard_regno
= ALLOCNO_HARD_REGNO (a
)) < 0
2121 || loop_node
->children
== NULL
2122 /* don't do the optimization because it can create
2123 copies and the reload pass can spill the allocno set
2124 by copy although the allocno will not get memory
2126 || ira_reg_equiv_invariant_p
[regno
]
2127 || ira_reg_equiv_const
[regno
] != NULL_RTX
2128 || !bitmap_bit_p (loop_node
->border_allocnos
, ALLOCNO_NUM (a
)))
2130 mode
= ALLOCNO_MODE (a
);
2131 rclass
= ALLOCNO_COVER_CLASS (a
);
2132 index
= ira_class_hard_reg_index
[rclass
][hard_regno
];
2133 ira_assert (index
>= 0);
2134 cost
= (ALLOCNO_MEMORY_COST (a
)
2135 - (ALLOCNO_HARD_REG_COSTS (a
) == NULL
2136 ? ALLOCNO_COVER_CLASS_COST (a
)
2137 : ALLOCNO_HARD_REG_COSTS (a
)[index
]));
2138 for (subloop_node
= loop_node
->subloops
;
2139 subloop_node
!= NULL
;
2140 subloop_node
= subloop_node
->subloop_next
)
2142 ira_assert (subloop_node
->bb
== NULL
);
2143 subloop_allocno
= subloop_node
->regno_allocno_map
[regno
];
2144 if (subloop_allocno
== NULL
)
2146 ira_assert (rclass
== ALLOCNO_COVER_CLASS (subloop_allocno
));
2147 /* We have accumulated cost. To get the real cost of
2148 allocno usage in the loop we should subtract costs of
2149 the subloop allocnos. */
2150 cost
-= (ALLOCNO_MEMORY_COST (subloop_allocno
)
2151 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno
) == NULL
2152 ? ALLOCNO_COVER_CLASS_COST (subloop_allocno
)
2153 : ALLOCNO_HARD_REG_COSTS (subloop_allocno
)[index
]));
2154 exit_freq
= ira_loop_edge_freq (subloop_node
, regno
, true);
2155 enter_freq
= ira_loop_edge_freq (subloop_node
, regno
, false);
2156 if ((hard_regno2
= ALLOCNO_HARD_REGNO (subloop_allocno
)) < 0)
2157 cost
-= (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
2158 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
2162 += (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
2163 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
2164 if (hard_regno2
!= hard_regno
)
2165 cost
-= (ira_get_register_move_cost (mode
, rclass
, rclass
)
2166 * (exit_freq
+ enter_freq
));
2169 if ((parent
= loop_node
->parent
) != NULL
2170 && (parent_allocno
= parent
->regno_allocno_map
[regno
]) != NULL
)
2172 ira_assert (rclass
== ALLOCNO_COVER_CLASS (parent_allocno
));
2173 exit_freq
= ira_loop_edge_freq (loop_node
, regno
, true);
2174 enter_freq
= ira_loop_edge_freq (loop_node
, regno
, false);
2175 if ((hard_regno2
= ALLOCNO_HARD_REGNO (parent_allocno
)) < 0)
2176 cost
-= (ira_memory_move_cost
[mode
][rclass
][0] * exit_freq
2177 + ira_memory_move_cost
[mode
][rclass
][1] * enter_freq
);
2181 += (ira_memory_move_cost
[mode
][rclass
][1] * exit_freq
2182 + ira_memory_move_cost
[mode
][rclass
][0] * enter_freq
);
2183 if (hard_regno2
!= hard_regno
)
2184 cost
-= (ira_get_register_move_cost (mode
, rclass
, rclass
)
2185 * (exit_freq
+ enter_freq
));
2190 ALLOCNO_HARD_REGNO (a
) = -1;
2191 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2195 " Moving spill/restore for a%dr%d up from loop %d",
2196 ALLOCNO_NUM (a
), regno
, loop_node
->loop
->num
);
2197 fprintf (ira_dump_file
, " - profit %d\n", -cost
);
2209 /* Update current hard reg costs and current conflict hard reg costs
2210 for allocno A. It is done by processing its copies containing
2211 other allocnos already assigned. */
2213 update_curr_costs (ira_allocno_t a
)
2215 int i
, hard_regno
, cost
;
2216 enum machine_mode mode
;
2217 enum reg_class cover_class
, rclass
;
2218 ira_allocno_t another_a
;
2219 ira_copy_t cp
, next_cp
;
2221 ira_assert (! ALLOCNO_ASSIGNED_P (a
));
2222 cover_class
= ALLOCNO_COVER_CLASS (a
);
2223 if (cover_class
== NO_REGS
)
2225 mode
= ALLOCNO_MODE (a
);
2226 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
2230 next_cp
= cp
->next_first_allocno_copy
;
2231 another_a
= cp
->second
;
2233 else if (cp
->second
== a
)
2235 next_cp
= cp
->next_second_allocno_copy
;
2236 another_a
= cp
->first
;
2240 if (! ira_reg_classes_intersect_p
[cover_class
][ALLOCNO_COVER_CLASS
2242 || ! ALLOCNO_ASSIGNED_P (another_a
)
2243 || (hard_regno
= ALLOCNO_HARD_REGNO (another_a
)) < 0)
2245 rclass
= REGNO_REG_CLASS (hard_regno
);
2246 i
= ira_class_hard_reg_index
[cover_class
][hard_regno
];
2249 cost
= (cp
->first
== a
2250 ? ira_get_register_move_cost (mode
, rclass
, cover_class
)
2251 : ira_get_register_move_cost (mode
, cover_class
, rclass
));
2252 ira_allocate_and_set_or_copy_costs
2253 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a
),
2254 cover_class
, ALLOCNO_COVER_CLASS_COST (a
),
2255 ALLOCNO_HARD_REG_COSTS (a
));
2256 ira_allocate_and_set_or_copy_costs
2257 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
),
2258 cover_class
, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a
));
2259 ALLOCNO_UPDATED_HARD_REG_COSTS (a
)[i
] -= cp
->freq
* cost
;
2260 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
)[i
] -= cp
->freq
* cost
;
2264 /* Try to assign hard registers to the unassigned allocnos and
2265 allocnos conflicting with them or conflicting with allocnos whose
2266 regno >= START_REGNO. The function is called after ira_flattening,
2267 so more allocnos (including ones created in ira-emit.c) will have a
2268 chance to get a hard register. We use simple assignment algorithm
2269 based on priorities. */
2271 ira_reassign_conflict_allocnos (int start_regno
)
2273 int i
, allocnos_to_color_num
;
2274 ira_allocno_t a
, conflict_a
;
2275 ira_allocno_conflict_iterator aci
;
2276 enum reg_class cover_class
;
2277 bitmap allocnos_to_color
;
2278 ira_allocno_iterator ai
;
2280 allocnos_to_color
= ira_allocate_bitmap ();
2281 allocnos_to_color_num
= 0;
2282 FOR_EACH_ALLOCNO (a
, ai
)
2284 if (! ALLOCNO_ASSIGNED_P (a
)
2285 && ! bitmap_bit_p (allocnos_to_color
, ALLOCNO_NUM (a
)))
2287 if (ALLOCNO_COVER_CLASS (a
) != NO_REGS
)
2288 sorted_allocnos
[allocnos_to_color_num
++] = a
;
2291 ALLOCNO_ASSIGNED_P (a
) = true;
2292 ALLOCNO_HARD_REGNO (a
) = -1;
2293 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
2294 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
2296 bitmap_set_bit (allocnos_to_color
, ALLOCNO_NUM (a
));
2298 if (ALLOCNO_REGNO (a
) < start_regno
2299 || (cover_class
= ALLOCNO_COVER_CLASS (a
)) == NO_REGS
)
2301 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_a
, aci
)
2303 ira_assert (ira_reg_classes_intersect_p
2304 [cover_class
][ALLOCNO_COVER_CLASS (conflict_a
)]);
2305 if (bitmap_bit_p (allocnos_to_color
, ALLOCNO_NUM (conflict_a
)))
2307 bitmap_set_bit (allocnos_to_color
, ALLOCNO_NUM (conflict_a
));
2308 sorted_allocnos
[allocnos_to_color_num
++] = conflict_a
;
2311 ira_free_bitmap (allocnos_to_color
);
2312 if (allocnos_to_color_num
> 1)
2314 setup_allocno_priorities (sorted_allocnos
, allocnos_to_color_num
);
2315 qsort (sorted_allocnos
, allocnos_to_color_num
, sizeof (ira_allocno_t
),
2316 allocno_priority_compare_func
);
2318 for (i
= 0; i
< allocnos_to_color_num
; i
++)
2320 a
= sorted_allocnos
[i
];
2321 ALLOCNO_ASSIGNED_P (a
) = false;
2322 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
2323 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
2324 update_curr_costs (a
);
2326 for (i
= 0; i
< allocnos_to_color_num
; i
++)
2328 a
= sorted_allocnos
[i
];
2329 if (assign_hard_reg (a
, true))
2331 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2334 " Secondary allocation: assign hard reg %d to reg %d\n",
2335 ALLOCNO_HARD_REGNO (a
), ALLOCNO_REGNO (a
));
2342 /* This page contains code to coalesce memory stack slots used by
2343 spilled allocnos. This results in smaller stack frame, better data
2344 locality, and in smaller code for some architectures like
2345 x86/x86_64 where insn size depends on address displacement value.
2346 On the other hand, it can worsen insn scheduling after the RA but
2347 in practice it is less important than smaller stack frames. */
2349 /* Usage cost and order number of coalesced allocno set to which
2350 given pseudo register belongs to. */
2351 static int *regno_coalesced_allocno_cost
;
2352 static int *regno_coalesced_allocno_num
;
2354 /* Sort pseudos according frequencies of coalesced allocno sets they
2355 belong to (putting most frequently ones first), and according to
2356 coalesced allocno set order numbers. */
2358 coalesced_pseudo_reg_freq_compare (const void *v1p
, const void *v2p
)
2360 const int regno1
= *(const int *) v1p
;
2361 const int regno2
= *(const int *) v2p
;
2364 if ((diff
= (regno_coalesced_allocno_cost
[regno2
]
2365 - regno_coalesced_allocno_cost
[regno1
])) != 0)
2367 if ((diff
= (regno_coalesced_allocno_num
[regno1
]
2368 - regno_coalesced_allocno_num
[regno2
])) != 0)
2370 return regno1
- regno2
;
2373 /* Widest width in which each pseudo reg is referred to (via subreg).
2374 It is used for sorting pseudo registers. */
2375 static unsigned int *regno_max_ref_width
;
2377 /* Redefine STACK_GROWS_DOWNWARD in terms of 0 or 1. */
2378 #ifdef STACK_GROWS_DOWNWARD
2379 # undef STACK_GROWS_DOWNWARD
2380 # define STACK_GROWS_DOWNWARD 1
2382 # define STACK_GROWS_DOWNWARD 0
2385 /* Sort pseudos according their slot numbers (putting ones with
2386 smaller numbers first, or last when the frame pointer is not
2389 coalesced_pseudo_reg_slot_compare (const void *v1p
, const void *v2p
)
2391 const int regno1
= *(const int *) v1p
;
2392 const int regno2
= *(const int *) v2p
;
2393 ira_allocno_t a1
= ira_regno_allocno_map
[regno1
];
2394 ira_allocno_t a2
= ira_regno_allocno_map
[regno2
];
2395 int diff
, slot_num1
, slot_num2
;
2396 int total_size1
, total_size2
;
2398 if (a1
== NULL
|| ALLOCNO_HARD_REGNO (a1
) >= 0)
2400 if (a2
== NULL
|| ALLOCNO_HARD_REGNO (a2
) >= 0)
2401 return regno1
- regno2
;
2404 else if (a2
== NULL
|| ALLOCNO_HARD_REGNO (a2
) >= 0)
2406 slot_num1
= -ALLOCNO_HARD_REGNO (a1
);
2407 slot_num2
= -ALLOCNO_HARD_REGNO (a2
);
2408 if ((diff
= slot_num1
- slot_num2
) != 0)
2409 return (frame_pointer_needed
2410 || !FRAME_GROWS_DOWNWARD
== STACK_GROWS_DOWNWARD
? diff
: -diff
);
2411 total_size1
= MAX (PSEUDO_REGNO_BYTES (regno1
), regno_max_ref_width
[regno1
]);
2412 total_size2
= MAX (PSEUDO_REGNO_BYTES (regno2
), regno_max_ref_width
[regno2
]);
2413 if ((diff
= total_size2
- total_size1
) != 0)
2415 return regno1
- regno2
;
2418 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
2419 for coalesced allocno sets containing allocnos with their regnos
2420 given in array PSEUDO_REGNOS of length N. */
2422 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos
, int n
)
2424 int i
, num
, regno
, cost
;
2425 ira_allocno_t allocno
, a
;
2427 for (num
= i
= 0; i
< n
; i
++)
2429 regno
= pseudo_regnos
[i
];
2430 allocno
= ira_regno_allocno_map
[regno
];
2431 if (allocno
== NULL
)
2433 regno_coalesced_allocno_cost
[regno
] = 0;
2434 regno_coalesced_allocno_num
[regno
] = ++num
;
2437 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) != allocno
)
2440 for (cost
= 0, a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
2441 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
2443 cost
+= ALLOCNO_FREQ (a
);
2447 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
2448 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
2450 regno_coalesced_allocno_num
[ALLOCNO_REGNO (a
)] = num
;
2451 regno_coalesced_allocno_cost
[ALLOCNO_REGNO (a
)] = cost
;
2458 /* Collect spilled allocnos representing coalesced allocno sets (the
2459 first coalesced allocno). The collected allocnos are returned
2460 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
2461 number of the collected allocnos. The allocnos are given by their
2462 regnos in array PSEUDO_REGNOS of length N. */
2464 collect_spilled_coalesced_allocnos (int *pseudo_regnos
, int n
,
2465 ira_allocno_t
*spilled_coalesced_allocnos
)
2468 ira_allocno_t allocno
;
2470 for (num
= i
= 0; i
< n
; i
++)
2472 regno
= pseudo_regnos
[i
];
2473 allocno
= ira_regno_allocno_map
[regno
];
2474 if (allocno
== NULL
|| ALLOCNO_HARD_REGNO (allocno
) >= 0
2475 || ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) != allocno
)
2477 spilled_coalesced_allocnos
[num
++] = allocno
;
2482 /* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
2483 given slot contains live ranges of coalesced allocnos assigned to
2485 static allocno_live_range_t
*slot_coalesced_allocnos_live_ranges
;
2487 /* Return TRUE if coalesced allocnos represented by ALLOCNO has live
2488 ranges intersected with live ranges of coalesced allocnos assigned
2489 to slot with number N. */
2491 slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno
, int n
)
2495 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
2496 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
2498 if (ira_allocno_live_ranges_intersect_p
2499 (slot_coalesced_allocnos_live_ranges
[n
], ALLOCNO_LIVE_RANGES (a
)))
2507 /* Update live ranges of slot to which coalesced allocnos represented
2508 by ALLOCNO were assigned. */
2510 setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno
)
2514 allocno_live_range_t r
;
2516 n
= ALLOCNO_TEMP (allocno
);
2517 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
2518 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
2520 r
= ira_copy_allocno_live_range_list (ALLOCNO_LIVE_RANGES (a
));
2521 slot_coalesced_allocnos_live_ranges
[n
]
2522 = ira_merge_allocno_live_ranges
2523 (slot_coalesced_allocnos_live_ranges
[n
], r
);
2529 /* We have coalesced allocnos involving in copies. Coalesce allocnos
2530 further in order to share the same memory stack slot. Allocnos
2531 representing sets of allocnos coalesced before the call are given
2532 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
2533 some allocnos were coalesced in the function. */
2535 coalesce_spill_slots (ira_allocno_t
*spilled_coalesced_allocnos
, int num
)
2537 int i
, j
, n
, last_coalesced_allocno_num
;
2538 ira_allocno_t allocno
, a
;
2539 bool merged_p
= false;
2540 bitmap set_jump_crosses
= regstat_get_setjmp_crosses ();
2542 slot_coalesced_allocnos_live_ranges
2543 = (allocno_live_range_t
*) ira_allocate (sizeof (allocno_live_range_t
)
2544 * ira_allocnos_num
);
2545 memset (slot_coalesced_allocnos_live_ranges
, 0,
2546 sizeof (allocno_live_range_t
) * ira_allocnos_num
);
2547 last_coalesced_allocno_num
= 0;
2548 /* Coalesce non-conflicting spilled allocnos preferring most
2550 for (i
= 0; i
< num
; i
++)
2552 allocno
= spilled_coalesced_allocnos
[i
];
2553 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) != allocno
2554 || bitmap_bit_p (set_jump_crosses
, ALLOCNO_REGNO (allocno
))
2555 || (ALLOCNO_REGNO (allocno
) < ira_reg_equiv_len
2556 && (ira_reg_equiv_const
[ALLOCNO_REGNO (allocno
)] != NULL_RTX
2557 || ira_reg_equiv_invariant_p
[ALLOCNO_REGNO (allocno
)])))
2559 for (j
= 0; j
< i
; j
++)
2561 a
= spilled_coalesced_allocnos
[j
];
2562 n
= ALLOCNO_TEMP (a
);
2563 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) == a
2564 && ! bitmap_bit_p (set_jump_crosses
, ALLOCNO_REGNO (a
))
2565 && (ALLOCNO_REGNO (a
) >= ira_reg_equiv_len
2566 || (! ira_reg_equiv_invariant_p
[ALLOCNO_REGNO (a
)]
2567 && ira_reg_equiv_const
[ALLOCNO_REGNO (a
)] == NULL_RTX
))
2568 && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno
, n
))
2573 /* No coalescing: set up number for coalesced allocnos
2574 represented by ALLOCNO. */
2575 ALLOCNO_TEMP (allocno
) = last_coalesced_allocno_num
++;
2576 setup_slot_coalesced_allocno_live_ranges (allocno
);
2580 allocno_coalesced_p
= true;
2582 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2583 fprintf (ira_dump_file
,
2584 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
2585 ALLOCNO_NUM (allocno
), ALLOCNO_REGNO (allocno
),
2586 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
2587 ALLOCNO_TEMP (allocno
) = ALLOCNO_TEMP (a
);
2588 setup_slot_coalesced_allocno_live_ranges (allocno
);
2589 merge_allocnos (a
, allocno
);
2590 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) == a
);
2593 for (i
= 0; i
< ira_allocnos_num
; i
++)
2594 ira_finish_allocno_live_range_list
2595 (slot_coalesced_allocnos_live_ranges
[i
]);
2596 ira_free (slot_coalesced_allocnos_live_ranges
);
2600 /* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
2601 subsequent assigning stack slots to them in the reload pass. To do
2602 this we coalesce spilled allocnos first to decrease the number of
2603 memory-memory move insns. This function is called by the
2606 ira_sort_regnos_for_alter_reg (int *pseudo_regnos
, int n
,
2607 unsigned int *reg_max_ref_width
)
2609 int max_regno
= max_reg_num ();
2610 int i
, regno
, num
, slot_num
;
2611 ira_allocno_t allocno
, a
;
2612 ira_allocno_iterator ai
;
2613 ira_allocno_t
*spilled_coalesced_allocnos
;
2615 processed_coalesced_allocno_bitmap
= ira_allocate_bitmap ();
2616 /* Set up allocnos can be coalesced. */
2617 coloring_allocno_bitmap
= ira_allocate_bitmap ();
2618 for (i
= 0; i
< n
; i
++)
2620 regno
= pseudo_regnos
[i
];
2621 allocno
= ira_regno_allocno_map
[regno
];
2622 if (allocno
!= NULL
)
2623 bitmap_set_bit (coloring_allocno_bitmap
,
2624 ALLOCNO_NUM (allocno
));
2626 allocno_coalesced_p
= false;
2627 coalesce_allocnos (true);
2628 ira_free_bitmap (coloring_allocno_bitmap
);
2629 regno_coalesced_allocno_cost
2630 = (int *) ira_allocate (max_regno
* sizeof (int));
2631 regno_coalesced_allocno_num
2632 = (int *) ira_allocate (max_regno
* sizeof (int));
2633 memset (regno_coalesced_allocno_num
, 0, max_regno
* sizeof (int));
2634 setup_coalesced_allocno_costs_and_nums (pseudo_regnos
, n
);
2635 /* Sort regnos according frequencies of the corresponding coalesced
2637 qsort (pseudo_regnos
, n
, sizeof (int), coalesced_pseudo_reg_freq_compare
);
2638 spilled_coalesced_allocnos
2639 = (ira_allocno_t
*) ira_allocate (ira_allocnos_num
2640 * sizeof (ira_allocno_t
));
2641 /* Collect allocnos representing the spilled coalesced allocno
2643 num
= collect_spilled_coalesced_allocnos (pseudo_regnos
, n
,
2644 spilled_coalesced_allocnos
);
2645 if (flag_ira_share_spill_slots
2646 && coalesce_spill_slots (spilled_coalesced_allocnos
, num
))
2648 setup_coalesced_allocno_costs_and_nums (pseudo_regnos
, n
);
2649 qsort (pseudo_regnos
, n
, sizeof (int),
2650 coalesced_pseudo_reg_freq_compare
);
2651 num
= collect_spilled_coalesced_allocnos (pseudo_regnos
, n
,
2652 spilled_coalesced_allocnos
);
2654 ira_free_bitmap (processed_coalesced_allocno_bitmap
);
2655 allocno_coalesced_p
= false;
2656 /* Assign stack slot numbers to spilled allocno sets, use smaller
2657 numbers for most frequently used coalesced allocnos. -1 is
2658 reserved for dynamic search of stack slots for pseudos spilled by
2661 for (i
= 0; i
< num
; i
++)
2663 allocno
= spilled_coalesced_allocnos
[i
];
2664 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno
) != allocno
2665 || ALLOCNO_HARD_REGNO (allocno
) >= 0
2666 || (ALLOCNO_REGNO (allocno
) < ira_reg_equiv_len
2667 && (ira_reg_equiv_const
[ALLOCNO_REGNO (allocno
)] != NULL_RTX
2668 || ira_reg_equiv_invariant_p
[ALLOCNO_REGNO (allocno
)])))
2670 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2671 fprintf (ira_dump_file
, " Slot %d (freq,size):", slot_num
);
2673 for (a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno
);;
2674 a
= ALLOCNO_NEXT_COALESCED_ALLOCNO (a
))
2676 ira_assert (ALLOCNO_HARD_REGNO (a
) < 0);
2677 ALLOCNO_HARD_REGNO (a
) = -slot_num
;
2678 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2679 fprintf (ira_dump_file
, " a%dr%d(%d,%d)",
2680 ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
), ALLOCNO_FREQ (a
),
2681 MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a
)),
2682 reg_max_ref_width
[ALLOCNO_REGNO (a
)]));
2687 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2688 fprintf (ira_dump_file
, "\n");
2690 ira_spilled_reg_stack_slots_num
= slot_num
- 1;
2691 ira_free (spilled_coalesced_allocnos
);
2692 /* Sort regnos according the slot numbers. */
2693 regno_max_ref_width
= reg_max_ref_width
;
2694 qsort (pseudo_regnos
, n
, sizeof (int), coalesced_pseudo_reg_slot_compare
);
2695 /* Uncoalesce allocnos which is necessary for (re)assigning during
2697 FOR_EACH_ALLOCNO (a
, ai
)
2699 ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) = a
;
2700 ALLOCNO_NEXT_COALESCED_ALLOCNO (a
) = a
;
2702 ira_free (regno_coalesced_allocno_num
);
2703 ira_free (regno_coalesced_allocno_cost
);
2708 /* This page contains code used by the reload pass to improve the
2711 /* The function is called from reload to mark changes in the
2712 allocation of REGNO made by the reload. Remember that reg_renumber
2713 reflects the change result. */
2715 ira_mark_allocation_change (int regno
)
2717 ira_allocno_t a
= ira_regno_allocno_map
[regno
];
2718 int old_hard_regno
, hard_regno
, cost
;
2719 enum reg_class cover_class
= ALLOCNO_COVER_CLASS (a
);
2721 ira_assert (a
!= NULL
);
2722 hard_regno
= reg_renumber
[regno
];
2723 if ((old_hard_regno
= ALLOCNO_HARD_REGNO (a
)) == hard_regno
)
2725 if (old_hard_regno
< 0)
2726 cost
= -ALLOCNO_MEMORY_COST (a
);
2729 ira_assert (ira_class_hard_reg_index
[cover_class
][old_hard_regno
] >= 0);
2730 cost
= -(ALLOCNO_HARD_REG_COSTS (a
) == NULL
2731 ? ALLOCNO_COVER_CLASS_COST (a
)
2732 : ALLOCNO_HARD_REG_COSTS (a
)
2733 [ira_class_hard_reg_index
[cover_class
][old_hard_regno
]]);
2734 update_copy_costs (a
, false);
2736 ira_overall_cost
-= cost
;
2737 ALLOCNO_HARD_REGNO (a
) = hard_regno
;
2740 ALLOCNO_HARD_REGNO (a
) = -1;
2741 cost
+= ALLOCNO_MEMORY_COST (a
);
2743 else if (ira_class_hard_reg_index
[cover_class
][hard_regno
] >= 0)
2745 cost
+= (ALLOCNO_HARD_REG_COSTS (a
) == NULL
2746 ? ALLOCNO_COVER_CLASS_COST (a
)
2747 : ALLOCNO_HARD_REG_COSTS (a
)
2748 [ira_class_hard_reg_index
[cover_class
][hard_regno
]]);
2749 update_copy_costs (a
, true);
2752 /* Reload changed class of the allocno. */
2754 ira_overall_cost
+= cost
;
2757 /* This function is called when reload deletes memory-memory move. In
2758 this case we marks that the allocation of the corresponding
2759 allocnos should be not changed in future. Otherwise we risk to get
2762 ira_mark_memory_move_deletion (int dst_regno
, int src_regno
)
2764 ira_allocno_t dst
= ira_regno_allocno_map
[dst_regno
];
2765 ira_allocno_t src
= ira_regno_allocno_map
[src_regno
];
2767 ira_assert (dst
!= NULL
&& src
!= NULL
2768 && ALLOCNO_HARD_REGNO (dst
) < 0
2769 && ALLOCNO_HARD_REGNO (src
) < 0);
2770 ALLOCNO_DONT_REASSIGN_P (dst
) = true;
2771 ALLOCNO_DONT_REASSIGN_P (src
) = true;
2774 /* Try to assign a hard register (except for FORBIDDEN_REGS) to
2775 allocno A and return TRUE in the case of success. */
2777 allocno_reload_assign (ira_allocno_t a
, HARD_REG_SET forbidden_regs
)
2780 enum reg_class cover_class
;
2781 int regno
= ALLOCNO_REGNO (a
);
2783 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
), forbidden_regs
);
2784 if (! flag_caller_saves
&& ALLOCNO_CALLS_CROSSED_NUM (a
) != 0)
2785 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
), call_used_reg_set
);
2786 ALLOCNO_ASSIGNED_P (a
) = false;
2787 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
2788 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
2789 cover_class
= ALLOCNO_COVER_CLASS (a
);
2790 update_curr_costs (a
);
2791 assign_hard_reg (a
, true);
2792 hard_regno
= ALLOCNO_HARD_REGNO (a
);
2793 reg_renumber
[regno
] = hard_regno
;
2795 ALLOCNO_HARD_REGNO (a
) = -1;
2798 ira_assert (ira_class_hard_reg_index
[cover_class
][hard_regno
] >= 0);
2799 ira_overall_cost
-= (ALLOCNO_MEMORY_COST (a
)
2800 - (ALLOCNO_HARD_REG_COSTS (a
) == NULL
2801 ? ALLOCNO_COVER_CLASS_COST (a
)
2802 : ALLOCNO_HARD_REG_COSTS (a
)
2803 [ira_class_hard_reg_index
2804 [cover_class
][hard_regno
]]));
2805 if (ALLOCNO_CALLS_CROSSED_NUM (a
) != 0
2806 && ! ira_hard_reg_not_in_set_p (hard_regno
, ALLOCNO_MODE (a
),
2809 ira_assert (flag_caller_saves
);
2810 caller_save_needed
= 1;
2814 /* If we found a hard register, modify the RTL for the pseudo
2815 register to show the hard register, and mark the pseudo register
2817 if (reg_renumber
[regno
] >= 0)
2819 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2820 fprintf (ira_dump_file
, ": reassign to %d\n", reg_renumber
[regno
]);
2821 SET_REGNO (regno_reg_rtx
[regno
], reg_renumber
[regno
]);
2822 mark_home_live (regno
);
2824 else if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2825 fprintf (ira_dump_file
, "\n");
2827 return reg_renumber
[regno
] >= 0;
2830 /* Sort pseudos according their usage frequencies (putting most
2831 frequently ones first). */
2833 pseudo_reg_compare (const void *v1p
, const void *v2p
)
2835 int regno1
= *(const int *) v1p
;
2836 int regno2
= *(const int *) v2p
;
2839 if ((diff
= REG_FREQ (regno2
) - REG_FREQ (regno1
)) != 0)
2841 return regno1
- regno2
;
2844 /* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
2845 NUM of them) or spilled pseudos conflicting with pseudos in
2846 SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
2847 allocation has been changed. The function doesn't use
2848 BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
2849 PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
2850 is called by the reload pass at the end of each reload
2853 ira_reassign_pseudos (int *spilled_pseudo_regs
, int num
,
2854 HARD_REG_SET bad_spill_regs
,
2855 HARD_REG_SET
*pseudo_forbidden_regs
,
2856 HARD_REG_SET
*pseudo_previous_regs
, bitmap spilled
)
2860 ira_allocno_t a
, conflict_a
;
2861 HARD_REG_SET forbidden_regs
;
2862 ira_allocno_conflict_iterator aci
;
2865 qsort (spilled_pseudo_regs
, num
, sizeof (int), pseudo_reg_compare
);
2867 /* Try to assign hard registers to pseudos from
2868 SPILLED_PSEUDO_REGS. */
2869 for (m
= i
= 0; i
< num
; i
++)
2871 regno
= spilled_pseudo_regs
[i
];
2872 COPY_HARD_REG_SET (forbidden_regs
, bad_spill_regs
);
2873 IOR_HARD_REG_SET (forbidden_regs
, pseudo_forbidden_regs
[regno
]);
2874 IOR_HARD_REG_SET (forbidden_regs
, pseudo_previous_regs
[regno
]);
2875 gcc_assert (reg_renumber
[regno
] < 0);
2876 a
= ira_regno_allocno_map
[regno
];
2877 ira_mark_allocation_change (regno
);
2878 ira_assert (reg_renumber
[regno
] < 0);
2879 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2880 fprintf (ira_dump_file
,
2881 " Spill %d(a%d), cost=%d", regno
, ALLOCNO_NUM (a
),
2882 ALLOCNO_MEMORY_COST (a
)
2883 - ALLOCNO_COVER_CLASS_COST (a
));
2884 allocno_reload_assign (a
, forbidden_regs
);
2885 if (reg_renumber
[regno
] >= 0)
2887 CLEAR_REGNO_REG_SET (spilled
, regno
);
2891 spilled_pseudo_regs
[m
++] = regno
;
2895 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2897 fprintf (ira_dump_file
, " Spilled regs");
2898 for (i
= 0; i
< m
; i
++)
2899 fprintf (ira_dump_file
, " %d", spilled_pseudo_regs
[i
]);
2900 fprintf (ira_dump_file
, "\n");
2902 /* Try to assign hard registers to pseudos conflicting with ones
2903 from SPILLED_PSEUDO_REGS. */
2904 for (i
= n
= 0; i
< m
; i
++)
2906 regno
= spilled_pseudo_regs
[i
];
2907 a
= ira_regno_allocno_map
[regno
];
2908 FOR_EACH_ALLOCNO_CONFLICT (a
, conflict_a
, aci
)
2909 if (ALLOCNO_HARD_REGNO (conflict_a
) < 0
2910 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a
)
2911 && ! bitmap_bit_p (consideration_allocno_bitmap
,
2912 ALLOCNO_NUM (conflict_a
)))
2914 sorted_allocnos
[n
++] = conflict_a
;
2915 bitmap_set_bit (consideration_allocno_bitmap
,
2916 ALLOCNO_NUM (conflict_a
));
2921 setup_allocno_priorities (sorted_allocnos
, n
);
2922 qsort (sorted_allocnos
, n
, sizeof (ira_allocno_t
),
2923 allocno_priority_compare_func
);
2924 for (i
= 0; i
< n
; i
++)
2926 a
= sorted_allocnos
[i
];
2927 regno
= ALLOCNO_REGNO (a
);
2928 COPY_HARD_REG_SET (forbidden_regs
, bad_spill_regs
);
2929 IOR_HARD_REG_SET (forbidden_regs
, pseudo_forbidden_regs
[regno
]);
2930 IOR_HARD_REG_SET (forbidden_regs
, pseudo_previous_regs
[regno
]);
2931 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
2932 fprintf (ira_dump_file
,
2933 " Try assign %d(a%d), cost=%d",
2934 regno
, ALLOCNO_NUM (a
),
2935 ALLOCNO_MEMORY_COST (a
)
2936 - ALLOCNO_COVER_CLASS_COST (a
));
2937 if (allocno_reload_assign (a
, forbidden_regs
))
2940 bitmap_clear_bit (spilled
, regno
);
2947 /* The function is called by reload and returns already allocated
2948 stack slot (if any) for REGNO with given INHERENT_SIZE and
2949 TOTAL_SIZE. In the case of failure to find a slot which can be
2950 used for REGNO, the function returns NULL. */
2952 ira_reuse_stack_slot (int regno
, unsigned int inherent_size
,
2953 unsigned int total_size
)
2956 int slot_num
, best_slot_num
;
2957 int cost
, best_cost
;
2958 ira_copy_t cp
, next_cp
;
2959 ira_allocno_t another_allocno
, allocno
= ira_regno_allocno_map
[regno
];
2962 struct ira_spilled_reg_stack_slot
*slot
= NULL
;
2964 ira_assert (inherent_size
== PSEUDO_REGNO_BYTES (regno
)
2965 && inherent_size
<= total_size
2966 && ALLOCNO_HARD_REGNO (allocno
) < 0);
2967 if (! flag_ira_share_spill_slots
)
2969 slot_num
= -ALLOCNO_HARD_REGNO (allocno
) - 2;
2972 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
2977 best_cost
= best_slot_num
= -1;
2979 /* It means that the pseudo was spilled in the reload pass, try
2982 slot_num
< ira_spilled_reg_stack_slots_num
;
2985 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
2986 if (slot
->mem
== NULL_RTX
)
2988 if (slot
->width
< total_size
2989 || GET_MODE_SIZE (GET_MODE (slot
->mem
)) < inherent_size
)
2992 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
2993 FIRST_PSEUDO_REGISTER
, i
, bi
)
2995 another_allocno
= ira_regno_allocno_map
[i
];
2996 if (allocnos_have_intersected_live_ranges_p (allocno
,
3000 for (cost
= 0, cp
= ALLOCNO_COPIES (allocno
);
3004 if (cp
->first
== allocno
)
3006 next_cp
= cp
->next_first_allocno_copy
;
3007 another_allocno
= cp
->second
;
3009 else if (cp
->second
== allocno
)
3011 next_cp
= cp
->next_second_allocno_copy
;
3012 another_allocno
= cp
->first
;
3016 if (cp
->insn
== NULL_RTX
)
3018 if (bitmap_bit_p (&slot
->spilled_regs
,
3019 ALLOCNO_REGNO (another_allocno
)))
3022 if (cost
> best_cost
)
3025 best_slot_num
= slot_num
;
3032 slot_num
= best_slot_num
;
3033 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
3034 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
3036 ALLOCNO_HARD_REGNO (allocno
) = -slot_num
- 2;
3041 ira_assert (slot
->width
>= total_size
);
3042 #ifdef ENABLE_IRA_CHECKING
3043 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
3044 FIRST_PSEUDO_REGISTER
, i
, bi
)
3046 ira_assert (! pseudos_have_intersected_live_ranges_p (regno
, i
));
3049 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
3050 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
3052 fprintf (ira_dump_file
, " Assigning %d(freq=%d) slot %d of",
3053 regno
, REG_FREQ (regno
), slot_num
);
3054 EXECUTE_IF_SET_IN_BITMAP (&slot
->spilled_regs
,
3055 FIRST_PSEUDO_REGISTER
, i
, bi
)
3057 if ((unsigned) regno
!= i
)
3058 fprintf (ira_dump_file
, " %d", i
);
3060 fprintf (ira_dump_file
, "\n");
3066 /* This is called by reload every time a new stack slot X with
3067 TOTAL_SIZE was allocated for REGNO. We store this info for
3068 subsequent ira_reuse_stack_slot calls. */
3070 ira_mark_new_stack_slot (rtx x
, int regno
, unsigned int total_size
)
3072 struct ira_spilled_reg_stack_slot
*slot
;
3074 ira_allocno_t allocno
;
3076 ira_assert (PSEUDO_REGNO_BYTES (regno
) <= total_size
);
3077 allocno
= ira_regno_allocno_map
[regno
];
3078 slot_num
= -ALLOCNO_HARD_REGNO (allocno
) - 2;
3081 slot_num
= ira_spilled_reg_stack_slots_num
++;
3082 ALLOCNO_HARD_REGNO (allocno
) = -slot_num
- 2;
3084 slot
= &ira_spilled_reg_stack_slots
[slot_num
];
3085 INIT_REG_SET (&slot
->spilled_regs
);
3086 SET_REGNO_REG_SET (&slot
->spilled_regs
, regno
);
3088 slot
->width
= total_size
;
3089 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
3090 fprintf (ira_dump_file
, " Assigning %d(freq=%d) a new slot %d\n",
3091 regno
, REG_FREQ (regno
), slot_num
);
3095 /* Return spill cost for pseudo-registers whose numbers are in array
3096 REGNOS (with a negative number as an end marker) for reload with
3097 given IN and OUT for INSN. Return also number points (through
3098 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
3099 the register pressure is high, number of references of the
3100 pseudo-registers (through NREFS), number of callee-clobbered
3101 hard-registers occupied by the pseudo-registers (through
3102 CALL_USED_COUNT), and the first hard regno occupied by the
3103 pseudo-registers (through FIRST_HARD_REGNO). */
3105 calculate_spill_cost (int *regnos
, rtx in
, rtx out
, rtx insn
,
3106 int *excess_pressure_live_length
,
3107 int *nrefs
, int *call_used_count
, int *first_hard_regno
)
3109 int i
, cost
, regno
, hard_regno
, j
, count
, saved_cost
, nregs
;
3115 for (length
= count
= cost
= i
= 0;; i
++)
3120 *nrefs
+= REG_N_REFS (regno
);
3121 hard_regno
= reg_renumber
[regno
];
3122 ira_assert (hard_regno
>= 0);
3123 a
= ira_regno_allocno_map
[regno
];
3124 length
+= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
3125 cost
+= ALLOCNO_MEMORY_COST (a
) - ALLOCNO_COVER_CLASS_COST (a
);
3126 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (a
)];
3127 for (j
= 0; j
< nregs
; j
++)
3128 if (! TEST_HARD_REG_BIT (call_used_reg_set
, hard_regno
+ j
))
3132 in_p
= in
&& REG_P (in
) && (int) REGNO (in
) == hard_regno
;
3133 out_p
= out
&& REG_P (out
) && (int) REGNO (out
) == hard_regno
;
3135 && find_regno_note (insn
, REG_DEAD
, hard_regno
) != NULL_RTX
)
3139 saved_cost
+= ira_memory_move_cost
3140 [ALLOCNO_MODE (a
)][ALLOCNO_COVER_CLASS (a
)][1];
3143 += ira_memory_move_cost
3144 [ALLOCNO_MODE (a
)][ALLOCNO_COVER_CLASS (a
)][0];
3145 cost
-= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn
)) * saved_cost
;
3148 *excess_pressure_live_length
= length
;
3149 *call_used_count
= count
;
3153 hard_regno
= reg_renumber
[regnos
[0]];
3155 *first_hard_regno
= hard_regno
;
3159 /* Return TRUE if spilling pseudo-registers whose numbers are in array
3160 REGNOS is better than spilling pseudo-registers with numbers in
3161 OTHER_REGNOS for reload with given IN and OUT for INSN. The
3162 function used by the reload pass to make better register spilling
3165 ira_better_spill_reload_regno_p (int *regnos
, int *other_regnos
,
3166 rtx in
, rtx out
, rtx insn
)
3168 int cost
, other_cost
;
3169 int length
, other_length
;
3170 int nrefs
, other_nrefs
;
3171 int call_used_count
, other_call_used_count
;
3172 int hard_regno
, other_hard_regno
;
3174 cost
= calculate_spill_cost (regnos
, in
, out
, insn
,
3175 &length
, &nrefs
, &call_used_count
, &hard_regno
);
3176 other_cost
= calculate_spill_cost (other_regnos
, in
, out
, insn
,
3177 &other_length
, &other_nrefs
,
3178 &other_call_used_count
,
3180 if (nrefs
== 0 && other_nrefs
!= 0)
3182 if (nrefs
!= 0 && other_nrefs
== 0)
3184 if (cost
!= other_cost
)
3185 return cost
< other_cost
;
3186 if (length
!= other_length
)
3187 return length
> other_length
;
3188 #ifdef REG_ALLOC_ORDER
3189 if (hard_regno
>= 0 && other_hard_regno
>= 0)
3190 return (inv_reg_alloc_order
[hard_regno
]
3191 < inv_reg_alloc_order
[other_hard_regno
]);
3193 if (call_used_count
!= other_call_used_count
)
3194 return call_used_count
> other_call_used_count
;
3201 /* Allocate and initialize data necessary for assign_hard_reg. */
3203 ira_initiate_assign (void)
3206 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
3207 * ira_allocnos_num
);
3208 consideration_allocno_bitmap
= ira_allocate_bitmap ();
3209 initiate_cost_update ();
3210 allocno_priorities
= (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
3213 /* Deallocate data used by assign_hard_reg. */
3215 ira_finish_assign (void)
3217 ira_free (sorted_allocnos
);
3218 ira_free_bitmap (consideration_allocno_bitmap
);
3219 finish_cost_update ();
3220 ira_free (allocno_priorities
);
3225 /* Entry function doing color-based register allocation. */
3229 allocno_stack_vec
= VEC_alloc (ira_allocno_t
, heap
, ira_allocnos_num
);
3230 removed_splay_allocno_vec
3231 = VEC_alloc (ira_allocno_t
, heap
, ira_allocnos_num
);
3232 memset (allocated_hardreg_p
, 0, sizeof (allocated_hardreg_p
));
3233 ira_initiate_assign ();
3235 ira_finish_assign ();
3236 VEC_free (ira_allocno_t
, heap
, removed_splay_allocno_vec
);
3237 VEC_free (ira_allocno_t
, heap
, allocno_stack_vec
);
3238 move_spill_restore ();
3243 /* This page contains a simple register allocator without usage of
3244 allocno conflicts. This is used for fast allocation for -O0. */
3246 /* Do register allocation by not using allocno conflicts. It uses
3247 only allocno live ranges. The algorithm is close to Chow's
3248 priority coloring. */
3250 fast_allocation (void)
3252 int i
, j
, k
, num
, class_size
, hard_regno
;
3254 bool no_stack_reg_p
;
3256 enum reg_class cover_class
;
3257 enum machine_mode mode
;
3259 ira_allocno_iterator ai
;
3260 allocno_live_range_t r
;
3261 HARD_REG_SET conflict_hard_regs
, *used_hard_regs
;
3263 sorted_allocnos
= (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
3264 * ira_allocnos_num
);
3266 FOR_EACH_ALLOCNO (a
, ai
)
3267 sorted_allocnos
[num
++] = a
;
3268 allocno_priorities
= (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
3269 setup_allocno_priorities (sorted_allocnos
, num
);
3270 used_hard_regs
= (HARD_REG_SET
*) ira_allocate (sizeof (HARD_REG_SET
)
3272 for (i
= 0; i
< ira_max_point
; i
++)
3273 CLEAR_HARD_REG_SET (used_hard_regs
[i
]);
3274 qsort (sorted_allocnos
, num
, sizeof (ira_allocno_t
),
3275 allocno_priority_compare_func
);
3276 for (i
= 0; i
< num
; i
++)
3278 a
= sorted_allocnos
[i
];
3279 COPY_HARD_REG_SET (conflict_hard_regs
, ALLOCNO_CONFLICT_HARD_REGS (a
));
3280 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
3281 for (j
= r
->start
; j
<= r
->finish
; j
++)
3282 IOR_HARD_REG_SET (conflict_hard_regs
, used_hard_regs
[j
]);
3283 cover_class
= ALLOCNO_COVER_CLASS (a
);
3284 ALLOCNO_ASSIGNED_P (a
) = true;
3285 ALLOCNO_HARD_REGNO (a
) = -1;
3286 if (hard_reg_set_subset_p (reg_class_contents
[cover_class
],
3287 conflict_hard_regs
))
3289 mode
= ALLOCNO_MODE (a
);
3291 no_stack_reg_p
= ALLOCNO_NO_STACK_REG_P (a
);
3293 class_size
= ira_class_hard_regs_num
[cover_class
];
3294 for (j
= 0; j
< class_size
; j
++)
3296 hard_regno
= ira_class_hard_regs
[cover_class
][j
];
3298 if (no_stack_reg_p
&& FIRST_STACK_REG
<= hard_regno
3299 && hard_regno
<= LAST_STACK_REG
)
3302 if (!ira_hard_reg_not_in_set_p (hard_regno
, mode
, conflict_hard_regs
)
3303 || (TEST_HARD_REG_BIT
3304 (prohibited_class_mode_regs
[cover_class
][mode
], hard_regno
)))
3306 ALLOCNO_HARD_REGNO (a
) = hard_regno
;
3307 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
3308 for (k
= r
->start
; k
<= r
->finish
; k
++)
3309 IOR_HARD_REG_SET (used_hard_regs
[k
],
3310 ira_reg_mode_hard_regset
[hard_regno
][mode
]);
3314 ira_free (sorted_allocnos
);
3315 ira_free (used_hard_regs
);
3316 ira_free (allocno_priorities
);
3317 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
3318 ira_print_disposition (ira_dump_file
);
3323 /* Entry function doing coloring. */
3328 ira_allocno_iterator ai
;
3330 /* Setup updated costs. */
3331 FOR_EACH_ALLOCNO (a
, ai
)
3333 ALLOCNO_UPDATED_MEMORY_COST (a
) = ALLOCNO_MEMORY_COST (a
);
3334 ALLOCNO_UPDATED_COVER_CLASS_COST (a
) = ALLOCNO_COVER_CLASS_COST (a
);
3336 if (ira_conflicts_p
)