Merge branch 'vendor/GCC44'
[dragonfly.git] / contrib / gcc-4.4 / gcc / ira-color.c
CommitLineData
c251ad9e
SS
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>.
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify it under
9the terms of the GNU General Public License as published by the Free
10Software Foundation; either version 3, or (at your option) any later
11version.
12
13GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14WARRANTY; without even the implied warranty of MERCHANTABILITY or
15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16for more details.
17
18You should have received a copy of the GNU General Public License
19along with GCC; see the file COPYING3. If not see
20<http://www.gnu.org/licenses/>. */
21
22#include "config.h"
23#include "system.h"
24#include "coretypes.h"
25#include "tm.h"
26#include "rtl.h"
27#include "tm_p.h"
28#include "target.h"
29#include "regs.h"
30#include "flags.h"
31#include "sbitmap.h"
32#include "bitmap.h"
33#include "hard-reg-set.h"
34#include "basic-block.h"
35#include "expr.h"
36#include "toplev.h"
37#include "reload.h"
38#include "params.h"
39#include "df.h"
40#include "splay-tree.h"
41#include "ira-int.h"
42
43/* This file contains code for regional graph coloring, spill/restore
44 code placement optimization, and code helping the reload pass to do
45 a better job. */
46
47/* Bitmap of allocnos which should be colored. */
48static bitmap coloring_allocno_bitmap;
49
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
53 allocnos. */
54static bitmap consideration_allocno_bitmap;
55
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. */
59static bool allocno_coalesced_p;
60
61/* Bitmap used to prevent a repeated allocno processing because of
62 coalescing. */
63static bitmap processed_coalesced_allocno_bitmap;
64
65/* All allocnos sorted according their priorities. */
66static ira_allocno_t *sorted_allocnos;
67
68/* Vec representing the stack of allocnos used during coloring. */
69static VEC(ira_allocno_t,heap) *allocno_stack_vec;
70
71/* Array used to choose an allocno for spilling. */
72static ira_allocno_t *allocnos_for_spilling;
73
74/* Pool for splay tree nodes. */
75static alloc_pool splay_tree_node_pool;
76
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. */
83static VEC(ira_allocno_t,heap) *removed_splay_allocno_vec;
84
4b1e227d
SW
85/* Helper for qsort comparison callbacks - return a positive integer if
86 X > Y, or a negative value otherwise. Use a conditional expression
87 instead of a difference computation to insulate from possible overflow
88 issues, e.g. X - Y < 0 for some X > 0 and Y < 0. */
89#define SORTGT(x,y) (((x) > (y)) ? 1 : -1)
90
c251ad9e
SS
91\f
92
93/* This page contains functions used to find conflicts using allocno
94 live ranges. */
95
96/* Return TRUE if live ranges of allocnos A1 and A2 intersect. It is
97 used to find a conflict for new allocnos or allocnos with the
98 different cover classes. */
99static bool
100allocnos_have_intersected_live_ranges_p (ira_allocno_t a1, ira_allocno_t a2)
101{
102 if (a1 == a2)
103 return false;
104 if (ALLOCNO_REG (a1) != NULL && ALLOCNO_REG (a2) != NULL
105 && (ORIGINAL_REGNO (ALLOCNO_REG (a1))
106 == ORIGINAL_REGNO (ALLOCNO_REG (a2))))
107 return false;
108 return ira_allocno_live_ranges_intersect_p (ALLOCNO_LIVE_RANGES (a1),
109 ALLOCNO_LIVE_RANGES (a2));
110}
111
112#ifdef ENABLE_IRA_CHECKING
113
114/* Return TRUE if live ranges of pseudo-registers REGNO1 and REGNO2
115 intersect. This should be used when there is only one region.
116 Currently this is used during reload. */
117static bool
118pseudos_have_intersected_live_ranges_p (int regno1, int regno2)
119{
120 ira_allocno_t a1, a2;
121
122 ira_assert (regno1 >= FIRST_PSEUDO_REGISTER
123 && regno2 >= FIRST_PSEUDO_REGISTER);
124 /* Reg info caclulated by dataflow infrastructure can be different
125 from one calculated by regclass. */
126 if ((a1 = ira_loop_tree_root->regno_allocno_map[regno1]) == NULL
127 || (a2 = ira_loop_tree_root->regno_allocno_map[regno2]) == NULL)
128 return false;
129 return allocnos_have_intersected_live_ranges_p (a1, a2);
130}
131
132#endif
133
134\f
135
136/* This page contains functions used to choose hard registers for
137 allocnos. */
138
139/* Array whose element value is TRUE if the corresponding hard
140 register was already allocated for an allocno. */
141static bool allocated_hardreg_p[FIRST_PSEUDO_REGISTER];
142
143/* Describes one element in a queue of allocnos whose costs need to be
144 updated. Each allocno in the queue is known to have a cover class. */
145struct update_cost_queue_elem
146{
147 /* This element is in the queue iff CHECK == update_cost_check. */
148 int check;
149
150 /* COST_HOP_DIVISOR**N, where N is the length of the shortest path
151 connecting this allocno to the one being allocated. */
152 int divisor;
153
154 /* The next allocno in the queue, or null if this is the last element. */
155 ira_allocno_t next;
156};
157
158/* The first element in a queue of allocnos whose copy costs need to be
159 updated. Null if the queue is empty. */
160static ira_allocno_t update_cost_queue;
161
162/* The last element in the queue described by update_cost_queue.
163 Not valid if update_cost_queue is null. */
164static struct update_cost_queue_elem *update_cost_queue_tail;
165
166/* A pool of elements in the queue described by update_cost_queue.
167 Elements are indexed by ALLOCNO_NUM. */
168static struct update_cost_queue_elem *update_cost_queue_elems;
169
170/* The current value of update_copy_cost call count. */
171static int update_cost_check;
172
173/* Allocate and initialize data necessary for function
174 update_copy_costs. */
175static void
176initiate_cost_update (void)
177{
178 size_t size;
179
180 size = ira_allocnos_num * sizeof (struct update_cost_queue_elem);
181 update_cost_queue_elems
182 = (struct update_cost_queue_elem *) ira_allocate (size);
183 memset (update_cost_queue_elems, 0, size);
184 update_cost_check = 0;
185}
186
187/* Deallocate data used by function update_copy_costs. */
188static void
189finish_cost_update (void)
190{
191 ira_free (update_cost_queue_elems);
192}
193
194/* When we traverse allocnos to update hard register costs, the cost
195 divisor will be multiplied by the following macro value for each
196 hop from given allocno to directly connected allocnos. */
197#define COST_HOP_DIVISOR 4
198
199/* Start a new cost-updating pass. */
200static void
201start_update_cost (void)
202{
203 update_cost_check++;
204 update_cost_queue = NULL;
205}
206
207/* Add (ALLOCNO, DIVISOR) to the end of update_cost_queue,
208 unless ALLOCNO is already in the queue, or has no cover class. */
209static inline void
210queue_update_cost (ira_allocno_t allocno, int divisor)
211{
212 struct update_cost_queue_elem *elem;
213
214 elem = &update_cost_queue_elems[ALLOCNO_NUM (allocno)];
215 if (elem->check != update_cost_check
216 && ALLOCNO_COVER_CLASS (allocno) != NO_REGS)
217 {
218 elem->check = update_cost_check;
219 elem->divisor = divisor;
220 elem->next = NULL;
221 if (update_cost_queue == NULL)
222 update_cost_queue = allocno;
223 else
224 update_cost_queue_tail->next = allocno;
225 update_cost_queue_tail = elem;
226 }
227}
228
229/* Try to remove the first element from update_cost_queue. Return false
230 if the queue was empty, otherwise make (*ALLOCNO, *DIVISOR) describe
231 the removed element. */
232static inline bool
233get_next_update_cost (ira_allocno_t *allocno, int *divisor)
234{
235 struct update_cost_queue_elem *elem;
236
237 if (update_cost_queue == NULL)
238 return false;
239
240 *allocno = update_cost_queue;
241 elem = &update_cost_queue_elems[ALLOCNO_NUM (*allocno)];
242 *divisor = elem->divisor;
243 update_cost_queue = elem->next;
244 return true;
245}
246
247/* Update the cost of allocnos to increase chances to remove some
248 copies as the result of subsequent assignment. */
249static void
250update_copy_costs (ira_allocno_t allocno, bool decr_p)
251{
252 int i, cost, update_cost, hard_regno, divisor;
253 enum machine_mode mode;
254 enum reg_class rclass, cover_class;
255 ira_allocno_t another_allocno;
256 ira_copy_t cp, next_cp;
257
258 hard_regno = ALLOCNO_HARD_REGNO (allocno);
259 ira_assert (hard_regno >= 0);
260
261 cover_class = ALLOCNO_COVER_CLASS (allocno);
262 if (cover_class == NO_REGS)
263 return;
264 i = ira_class_hard_reg_index[cover_class][hard_regno];
265 ira_assert (i >= 0);
266 rclass = REGNO_REG_CLASS (hard_regno);
267
268 start_update_cost ();
269 divisor = 1;
270 do
271 {
272 mode = ALLOCNO_MODE (allocno);
273 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
274 {
275 if (cp->first == allocno)
276 {
277 next_cp = cp->next_first_allocno_copy;
278 another_allocno = cp->second;
279 }
280 else if (cp->second == allocno)
281 {
282 next_cp = cp->next_second_allocno_copy;
283 another_allocno = cp->first;
284 }
285 else
286 gcc_unreachable ();
287
288 cover_class = ALLOCNO_COVER_CLASS (another_allocno);
289 if (! ira_reg_classes_intersect_p[rclass][cover_class]
290 || ALLOCNO_ASSIGNED_P (another_allocno))
291 continue;
292
293 cost = (cp->second == allocno
294 ? ira_get_register_move_cost (mode, rclass, cover_class)
295 : ira_get_register_move_cost (mode, cover_class, rclass));
296 if (decr_p)
297 cost = -cost;
298
299 update_cost = cp->freq * cost / divisor;
300 if (update_cost == 0)
301 continue;
302
303 ira_allocate_and_set_or_copy_costs
304 (&ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno), cover_class,
305 ALLOCNO_UPDATED_COVER_CLASS_COST (another_allocno),
306 ALLOCNO_HARD_REG_COSTS (another_allocno));
307 ira_allocate_and_set_or_copy_costs
308 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
309 cover_class, 0,
310 ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
311 i = ira_class_hard_reg_index[cover_class][hard_regno];
312 ira_assert (i >= 0);
313 ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno)[i] += update_cost;
314 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno)[i]
315 += update_cost;
316
317 queue_update_cost (another_allocno, divisor * COST_HOP_DIVISOR);
318 }
319 }
320 while (get_next_update_cost (&allocno, &divisor));
321}
322
323/* This function updates COSTS (decrease if DECR_P) for hard_registers
324 of COVER_CLASS by conflict costs of the unassigned allocnos
325 connected by copies with allocnos in update_cost_queue. This
326 update increases chances to remove some copies. */
327static void
328update_conflict_hard_regno_costs (int *costs, enum reg_class cover_class,
329 bool decr_p)
330{
331 int i, cost, class_size, freq, mult, div, divisor;
332 int index, hard_regno;
333 int *conflict_costs;
334 bool cont_p;
335 enum reg_class another_cover_class;
336 ira_allocno_t allocno, another_allocno;
337 ira_copy_t cp, next_cp;
338
339 while (get_next_update_cost (&allocno, &divisor))
340 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
341 {
342 if (cp->first == allocno)
343 {
344 next_cp = cp->next_first_allocno_copy;
345 another_allocno = cp->second;
346 }
347 else if (cp->second == allocno)
348 {
349 next_cp = cp->next_second_allocno_copy;
350 another_allocno = cp->first;
351 }
352 else
353 gcc_unreachable ();
354 another_cover_class = ALLOCNO_COVER_CLASS (another_allocno);
355 if (! ira_reg_classes_intersect_p[cover_class][another_cover_class]
356 || ALLOCNO_ASSIGNED_P (another_allocno)
357 || ALLOCNO_MAY_BE_SPILLED_P (ALLOCNO_FIRST_COALESCED_ALLOCNO
358 (another_allocno)))
359 continue;
360 class_size = ira_class_hard_regs_num[another_cover_class];
361 ira_allocate_and_copy_costs
362 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
363 another_cover_class,
364 ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
365 conflict_costs
366 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno);
367 if (conflict_costs == NULL)
368 cont_p = true;
369 else
370 {
371 mult = cp->freq;
372 freq = ALLOCNO_FREQ (another_allocno);
373 if (freq == 0)
374 freq = 1;
375 div = freq * divisor;
376 cont_p = false;
377 for (i = class_size - 1; i >= 0; i--)
378 {
379 hard_regno = ira_class_hard_regs[another_cover_class][i];
380 ira_assert (hard_regno >= 0);
381 index = ira_class_hard_reg_index[cover_class][hard_regno];
382 if (index < 0)
383 continue;
384 cost = conflict_costs [i] * mult / div;
385 if (cost == 0)
386 continue;
387 cont_p = true;
388 if (decr_p)
389 cost = -cost;
390 costs[index] += cost;
391 }
392 }
393 /* Probably 5 hops will be enough. */
394 if (cont_p
395 && divisor <= (COST_HOP_DIVISOR
396 * COST_HOP_DIVISOR
397 * COST_HOP_DIVISOR
398 * COST_HOP_DIVISOR))
399 queue_update_cost (another_allocno, divisor * COST_HOP_DIVISOR);
400 }
401}
402
403/* Sort allocnos according to the profit of usage of a hard register
404 instead of memory for them. */
405static int
406allocno_cost_compare_func (const void *v1p, const void *v2p)
407{
408 ira_allocno_t p1 = *(const ira_allocno_t *) v1p;
409 ira_allocno_t p2 = *(const ira_allocno_t *) v2p;
410 int c1, c2;
411
412 c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_UPDATED_COVER_CLASS_COST (p1);
413 c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_UPDATED_COVER_CLASS_COST (p2);
414 if (c1 - c2)
415 return c1 - c2;
416
417 /* If regs are equally good, sort by allocno numbers, so that the
418 results of qsort leave nothing to chance. */
419 return ALLOCNO_NUM (p1) - ALLOCNO_NUM (p2);
420}
421
422/* Print all allocnos coalesced with ALLOCNO. */
423static void
424print_coalesced_allocno (ira_allocno_t allocno)
425{
426 ira_allocno_t a;
427
428 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
429 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
430 {
431 ira_print_expanded_allocno (a);
432 if (a == allocno)
433 break;
434 fprintf (ira_dump_file, "+");
435 }
436}
437
438/* Choose a hard register for ALLOCNO (or for all coalesced allocnos
439 represented by ALLOCNO). If RETRY_P is TRUE, it means that the
440 function called from function `ira_reassign_conflict_allocnos' and
441 `allocno_reload_assign'. This function implements the optimistic
442 coalescing too: if we failed to assign a hard register to set of
443 the coalesced allocnos, we put them onto the coloring stack for
444 subsequent separate assigning. */
445static bool
446assign_hard_reg (ira_allocno_t allocno, bool retry_p)
447{
448 HARD_REG_SET conflicting_regs;
449 int i, j, k, hard_regno, best_hard_regno, class_size;
450 int cost, mem_cost, min_cost, full_cost, min_full_cost, add_cost;
451 int *a_costs;
452 int *conflict_costs;
453 enum reg_class cover_class, rclass, conflict_cover_class;
454 enum machine_mode mode;
455 ira_allocno_t a, conflict_allocno;
456 ira_allocno_conflict_iterator aci;
457 static int costs[FIRST_PSEUDO_REGISTER], full_costs[FIRST_PSEUDO_REGISTER];
458#ifdef STACK_REGS
459 bool no_stack_reg_p;
460#endif
461
462 ira_assert (! ALLOCNO_ASSIGNED_P (allocno));
463 cover_class = ALLOCNO_COVER_CLASS (allocno);
464 class_size = ira_class_hard_regs_num[cover_class];
465 mode = ALLOCNO_MODE (allocno);
466 CLEAR_HARD_REG_SET (conflicting_regs);
467 best_hard_regno = -1;
468 memset (full_costs, 0, sizeof (int) * class_size);
469 mem_cost = 0;
470 if (allocno_coalesced_p)
471 bitmap_clear (processed_coalesced_allocno_bitmap);
472 memset (costs, 0, sizeof (int) * class_size);
473 memset (full_costs, 0, sizeof (int) * class_size);
474#ifdef STACK_REGS
475 no_stack_reg_p = false;
476#endif
477 start_update_cost ();
478 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
479 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
480 {
481 mem_cost += ALLOCNO_UPDATED_MEMORY_COST (a);
482 IOR_HARD_REG_SET (conflicting_regs,
483 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
484 ira_allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
485 cover_class, ALLOCNO_HARD_REG_COSTS (a));
486 a_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
487#ifdef STACK_REGS
488 no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a);
489#endif
490 for (cost = ALLOCNO_UPDATED_COVER_CLASS_COST (a), i = 0;
491 i < class_size;
492 i++)
493 if (a_costs != NULL)
494 {
495 costs[i] += a_costs[i];
496 full_costs[i] += a_costs[i];
497 }
498 else
499 {
500 costs[i] += cost;
501 full_costs[i] += cost;
502 }
503 /* Take preferences of conflicting allocnos into account. */
504 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
505 /* Reload can give another class so we need to check all
506 allocnos. */
507 if (retry_p || bitmap_bit_p (consideration_allocno_bitmap,
508 ALLOCNO_NUM (conflict_allocno)))
509 {
510 conflict_cover_class = ALLOCNO_COVER_CLASS (conflict_allocno);
511 ira_assert (ira_reg_classes_intersect_p
512 [cover_class][conflict_cover_class]);
513 if (allocno_coalesced_p)
514 {
515 if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
516 ALLOCNO_NUM (conflict_allocno)))
517 continue;
518 bitmap_set_bit (processed_coalesced_allocno_bitmap,
519 ALLOCNO_NUM (conflict_allocno));
520 }
521 if (ALLOCNO_ASSIGNED_P (conflict_allocno))
522 {
523 if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno)) >= 0
524 && ira_class_hard_reg_index[cover_class][hard_regno] >= 0)
525 {
526 IOR_HARD_REG_SET
527 (conflicting_regs,
528 ira_reg_mode_hard_regset
529 [hard_regno][ALLOCNO_MODE (conflict_allocno)]);
530 if (hard_reg_set_subset_p (reg_class_contents[cover_class],
531 conflicting_regs))
532 goto fail;
533 }
534 }
535 else if (! ALLOCNO_MAY_BE_SPILLED_P (ALLOCNO_FIRST_COALESCED_ALLOCNO
536 (conflict_allocno)))
537 {
538 ira_allocate_and_copy_costs
539 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno),
540 conflict_cover_class,
541 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_allocno));
542 conflict_costs
543 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno);
544 if (conflict_costs != NULL)
545 for (j = class_size - 1; j >= 0; j--)
546 {
547 hard_regno = ira_class_hard_regs[cover_class][j];
548 ira_assert (hard_regno >= 0);
549 k = (ira_class_hard_reg_index
550 [conflict_cover_class][hard_regno]);
551 if (k < 0)
552 continue;
553 full_costs[j] -= conflict_costs[k];
554 }
555 queue_update_cost (conflict_allocno, COST_HOP_DIVISOR);
556 }
557 }
558 if (a == allocno)
559 break;
560 }
561 /* Take into account preferences of allocnos connected by copies to
562 the conflict allocnos. */
563 update_conflict_hard_regno_costs (full_costs, cover_class, true);
564
565 /* Take preferences of allocnos connected by copies into
566 account. */
567 start_update_cost ();
568 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
569 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
570 {
571 queue_update_cost (a, COST_HOP_DIVISOR);
572 if (a == allocno)
573 break;
574 }
575 update_conflict_hard_regno_costs (full_costs, cover_class, false);
576 min_cost = min_full_cost = INT_MAX;
577 /* We don't care about giving callee saved registers to allocnos no
578 living through calls because call clobbered registers are
579 allocated first (it is usual practice to put them first in
580 REG_ALLOC_ORDER). */
581 for (i = 0; i < class_size; i++)
582 {
583 hard_regno = ira_class_hard_regs[cover_class][i];
584#ifdef STACK_REGS
585 if (no_stack_reg_p
586 && FIRST_STACK_REG <= hard_regno && hard_regno <= LAST_STACK_REG)
587 continue;
588#endif
589 if (! ira_hard_reg_not_in_set_p (hard_regno, mode, conflicting_regs)
590 || TEST_HARD_REG_BIT (prohibited_class_mode_regs[cover_class][mode],
591 hard_regno))
592 continue;
593 cost = costs[i];
594 full_cost = full_costs[i];
595 if (! allocated_hardreg_p[hard_regno]
596 && ira_hard_reg_not_in_set_p (hard_regno, mode, call_used_reg_set))
597 /* We need to save/restore the hard register in
598 epilogue/prologue. Therefore we increase the cost. */
599 {
600 /* ??? If only part is call clobbered. */
601 rclass = REGNO_REG_CLASS (hard_regno);
602 add_cost = (ira_memory_move_cost[mode][rclass][0]
603 + ira_memory_move_cost[mode][rclass][1] - 1);
604 cost += add_cost;
605 full_cost += add_cost;
606 }
607 if (min_cost > cost)
608 min_cost = cost;
609 if (min_full_cost > full_cost)
610 {
611 min_full_cost = full_cost;
612 best_hard_regno = hard_regno;
613 ira_assert (hard_regno >= 0);
614 }
615 }
616 if (min_full_cost > mem_cost)
617 {
618 if (! retry_p && internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
619 fprintf (ira_dump_file, "(memory is more profitable %d vs %d) ",
620 mem_cost, min_full_cost);
621 best_hard_regno = -1;
622 }
623 fail:
624 if (flag_ira_algorithm != IRA_ALGORITHM_PRIORITY
625 && best_hard_regno < 0
626 && ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno) != allocno)
627 {
628 for (j = 0, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
629 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
630 {
631 ira_assert (! ALLOCNO_IN_GRAPH_P (a));
632 sorted_allocnos[j++] = a;
633 if (a == allocno)
634 break;
635 }
636 qsort (sorted_allocnos, j, sizeof (ira_allocno_t),
637 allocno_cost_compare_func);
638 for (i = 0; i < j; i++)
639 {
640 a = sorted_allocnos[i];
641 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
642 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
643 VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, a);
644 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
645 {
646 fprintf (ira_dump_file, " Pushing");
647 print_coalesced_allocno (a);
648 fprintf (ira_dump_file, "\n");
649 }
650 }
651 return false;
652 }
653 if (best_hard_regno >= 0)
654 allocated_hardreg_p[best_hard_regno] = true;
655 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
656 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
657 {
658 ALLOCNO_HARD_REGNO (a) = best_hard_regno;
659 ALLOCNO_ASSIGNED_P (a) = true;
660 if (best_hard_regno >= 0)
661 update_copy_costs (a, true);
662 ira_assert (ALLOCNO_COVER_CLASS (a) == cover_class);
663 /* We don't need updated costs anymore: */
664 ira_free_allocno_updated_costs (a);
665 if (a == allocno)
666 break;
667 }
668 return best_hard_regno >= 0;
669}
670
671\f
672
673/* This page contains the allocator based on the Chaitin-Briggs algorithm. */
674
675/* Bucket of allocnos that can colored currently without spilling. */
676static ira_allocno_t colorable_allocno_bucket;
677
678/* Bucket of allocnos that might be not colored currently without
679 spilling. */
680static ira_allocno_t uncolorable_allocno_bucket;
681
682/* Each element of the array contains the current number of allocnos
683 of given *cover* class in the uncolorable_bucket. */
684static int uncolorable_allocnos_num[N_REG_CLASSES];
685
686/* Return the current spill priority of allocno A. The less the
687 number, the more preferable the allocno for spilling. */
688static int
689allocno_spill_priority (ira_allocno_t a)
690{
691 return (ALLOCNO_TEMP (a)
692 / (ALLOCNO_LEFT_CONFLICTS_NUM (a)
693 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a)][ALLOCNO_MODE (a)]
694 + 1));
695}
696
697/* Add ALLOCNO to bucket *BUCKET_PTR. ALLOCNO should be not in a bucket
698 before the call. */
699static void
700add_allocno_to_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
701{
702 ira_allocno_t first_allocno;
703 enum reg_class cover_class;
704
705 if (bucket_ptr == &uncolorable_allocno_bucket
706 && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
707 {
708 uncolorable_allocnos_num[cover_class]++;
709 ira_assert (uncolorable_allocnos_num[cover_class] > 0);
710 }
711 first_allocno = *bucket_ptr;
712 ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno) = first_allocno;
713 ALLOCNO_PREV_BUCKET_ALLOCNO (allocno) = NULL;
714 if (first_allocno != NULL)
715 ALLOCNO_PREV_BUCKET_ALLOCNO (first_allocno) = allocno;
716 *bucket_ptr = allocno;
717}
718
719/* The function returns frequency and number of available hard
720 registers for allocnos coalesced with ALLOCNO. */
721static void
722get_coalesced_allocnos_attributes (ira_allocno_t allocno, int *freq, int *num)
723{
724 ira_allocno_t a;
725
726 *freq = 0;
727 *num = 0;
728 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
729 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
730 {
731 *freq += ALLOCNO_FREQ (a);
732 *num += ALLOCNO_AVAILABLE_REGS_NUM (a);
733 if (a == allocno)
734 break;
735 }
736}
737
738/* Compare two allocnos to define which allocno should be pushed first
739 into the coloring stack. If the return is a negative number, the
740 allocno given by the first parameter will be pushed first. In this
741 case such allocno has less priority than the second one and the
742 hard register will be assigned to it after assignment to the second
743 one. As the result of such assignment order, the second allocno
744 has a better chance to get the best hard register. */
745static int
746bucket_allocno_compare_func (const void *v1p, const void *v2p)
747{
748 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
749 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
750 int diff, a1_freq, a2_freq, a1_num, a2_num;
751
752 if ((diff = (int) ALLOCNO_COVER_CLASS (a2) - ALLOCNO_COVER_CLASS (a1)) != 0)
753 return diff;
754 get_coalesced_allocnos_attributes (a1, &a1_freq, &a1_num);
755 get_coalesced_allocnos_attributes (a2, &a2_freq, &a2_num);
756 if ((diff = a2_num - a1_num) != 0)
757 return diff;
758 else if ((diff = a1_freq - a2_freq) != 0)
759 return diff;
760 return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
761}
762
763/* Sort bucket *BUCKET_PTR and return the result through
764 BUCKET_PTR. */
765static void
766sort_bucket (ira_allocno_t *bucket_ptr)
767{
768 ira_allocno_t a, head;
769 int n;
770
771 for (n = 0, a = *bucket_ptr; a != NULL; a = ALLOCNO_NEXT_BUCKET_ALLOCNO (a))
772 sorted_allocnos[n++] = a;
773 if (n <= 1)
774 return;
775 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
776 bucket_allocno_compare_func);
777 head = NULL;
778 for (n--; n >= 0; n--)
779 {
780 a = sorted_allocnos[n];
781 ALLOCNO_NEXT_BUCKET_ALLOCNO (a) = head;
782 ALLOCNO_PREV_BUCKET_ALLOCNO (a) = NULL;
783 if (head != NULL)
784 ALLOCNO_PREV_BUCKET_ALLOCNO (head) = a;
785 head = a;
786 }
787 *bucket_ptr = head;
788}
789
790/* Add ALLOCNO to bucket *BUCKET_PTR maintaining the order according
791 their priority. ALLOCNO should be not in a bucket before the
792 call. */
793static void
794add_allocno_to_ordered_bucket (ira_allocno_t allocno,
795 ira_allocno_t *bucket_ptr)
796{
797 ira_allocno_t before, after;
798 enum reg_class cover_class;
799
800 if (bucket_ptr == &uncolorable_allocno_bucket
801 && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
802 {
803 uncolorable_allocnos_num[cover_class]++;
804 ira_assert (uncolorable_allocnos_num[cover_class] > 0);
805 }
806 for (before = *bucket_ptr, after = NULL;
807 before != NULL;
808 after = before, before = ALLOCNO_NEXT_BUCKET_ALLOCNO (before))
809 if (bucket_allocno_compare_func (&allocno, &before) < 0)
810 break;
811 ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno) = before;
812 ALLOCNO_PREV_BUCKET_ALLOCNO (allocno) = after;
813 if (after == NULL)
814 *bucket_ptr = allocno;
815 else
816 ALLOCNO_NEXT_BUCKET_ALLOCNO (after) = allocno;
817 if (before != NULL)
818 ALLOCNO_PREV_BUCKET_ALLOCNO (before) = allocno;
819}
820
821/* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
822 the call. */
823static void
824delete_allocno_from_bucket (ira_allocno_t allocno, ira_allocno_t *bucket_ptr)
825{
826 ira_allocno_t prev_allocno, next_allocno;
827 enum reg_class cover_class;
828
829 if (bucket_ptr == &uncolorable_allocno_bucket
830 && (cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
831 {
832 uncolorable_allocnos_num[cover_class]--;
833 ira_assert (uncolorable_allocnos_num[cover_class] >= 0);
834 }
835 prev_allocno = ALLOCNO_PREV_BUCKET_ALLOCNO (allocno);
836 next_allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno);
837 if (prev_allocno != NULL)
838 ALLOCNO_NEXT_BUCKET_ALLOCNO (prev_allocno) = next_allocno;
839 else
840 {
841 ira_assert (*bucket_ptr == allocno);
842 *bucket_ptr = next_allocno;
843 }
844 if (next_allocno != NULL)
845 ALLOCNO_PREV_BUCKET_ALLOCNO (next_allocno) = prev_allocno;
846}
847
848/* Splay tree for each cover class. The trees are indexed by the
849 corresponding cover classes. Splay trees contain uncolorable
850 allocnos. */
851static splay_tree uncolorable_allocnos_splay_tree[N_REG_CLASSES];
852
853/* If the following macro is TRUE, splay tree is used to choose an
854 allocno of the corresponding cover class for spilling. When the
855 number uncolorable allocnos of given cover class decreases to some
856 threshold, linear array search is used to find the best allocno for
857 spilling. This threshold is actually pretty big because, although
858 splay trees asymptotically is much faster, each splay tree
859 operation is sufficiently costly especially taking cache locality
860 into account. */
861#define USE_SPLAY_P(CLASS) (uncolorable_allocnos_num[CLASS] > 4000)
862
863/* Put ALLOCNO onto the coloring stack without removing it from its
864 bucket. Pushing allocno to the coloring stack can result in moving
865 conflicting allocnos from the uncolorable bucket to the colorable
866 one. */
867static void
868push_allocno_to_stack (ira_allocno_t allocno)
869{
870 int conflicts_num, conflict_size, size;
871 ira_allocno_t a, conflict_allocno;
872 enum reg_class cover_class;
873 ira_allocno_conflict_iterator aci;
874
875 ALLOCNO_IN_GRAPH_P (allocno) = false;
876 VEC_safe_push (ira_allocno_t, heap, allocno_stack_vec, allocno);
877 cover_class = ALLOCNO_COVER_CLASS (allocno);
878 if (cover_class == NO_REGS)
879 return;
880 size = ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)];
881 if (allocno_coalesced_p)
882 bitmap_clear (processed_coalesced_allocno_bitmap);
883 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
884 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
885 {
886 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
887 {
888 conflict_allocno = ALLOCNO_FIRST_COALESCED_ALLOCNO (conflict_allocno);
889 if (bitmap_bit_p (coloring_allocno_bitmap,
890 ALLOCNO_NUM (conflict_allocno)))
891 {
892 ira_assert (cover_class
893 == ALLOCNO_COVER_CLASS (conflict_allocno));
894 if (allocno_coalesced_p)
895 {
896 if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
897 ALLOCNO_NUM (conflict_allocno)))
898 continue;
899 bitmap_set_bit (processed_coalesced_allocno_bitmap,
900 ALLOCNO_NUM (conflict_allocno));
901 }
902 if (ALLOCNO_IN_GRAPH_P (conflict_allocno)
903 && ! ALLOCNO_ASSIGNED_P (conflict_allocno))
904 {
905 conflicts_num = ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno);
906 conflict_size
907 = (ira_reg_class_nregs
908 [cover_class][ALLOCNO_MODE (conflict_allocno)]);
909 ira_assert
910 (ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) >= size);
911 if (conflicts_num + conflict_size
912 <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno))
913 {
914 ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) -= size;
915 continue;
916 }
917 conflicts_num
918 = ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) - size;
919 if (uncolorable_allocnos_splay_tree[cover_class] != NULL
920 && !ALLOCNO_SPLAY_REMOVED_P (conflict_allocno)
921 && USE_SPLAY_P (cover_class))
922 {
923 ira_assert
924 (splay_tree_lookup
925 (uncolorable_allocnos_splay_tree[cover_class],
926 (splay_tree_key) conflict_allocno) != NULL);
927 splay_tree_remove
928 (uncolorable_allocnos_splay_tree[cover_class],
929 (splay_tree_key) conflict_allocno);
930 ALLOCNO_SPLAY_REMOVED_P (conflict_allocno) = true;
931 VEC_safe_push (ira_allocno_t, heap,
932 removed_splay_allocno_vec,
933 conflict_allocno);
934 }
935 ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) = conflicts_num;
936 if (conflicts_num + conflict_size
937 <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno))
938 {
939 delete_allocno_from_bucket
940 (conflict_allocno, &uncolorable_allocno_bucket);
941 add_allocno_to_ordered_bucket
942 (conflict_allocno, &colorable_allocno_bucket);
943 }
944 }
945 }
946 }
947 if (a == allocno)
948 break;
949 }
950}
951
952/* Put ALLOCNO onto the coloring stack and remove it from its bucket.
953 The allocno is in the colorable bucket if COLORABLE_P is TRUE. */
954static void
955remove_allocno_from_bucket_and_push (ira_allocno_t allocno, bool colorable_p)
956{
957 enum reg_class cover_class;
958
959 if (colorable_p)
960 delete_allocno_from_bucket (allocno, &colorable_allocno_bucket);
961 else
962 delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
963 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
964 {
965 fprintf (ira_dump_file, " Pushing");
966 print_coalesced_allocno (allocno);
967 if (colorable_p)
968 fprintf (ira_dump_file, "\n");
969 else
970 fprintf (ira_dump_file, "(potential spill: %spri=%d, cost=%d)\n",
971 ALLOCNO_BAD_SPILL_P (allocno) ? "bad spill, " : "",
972 allocno_spill_priority (allocno), ALLOCNO_TEMP (allocno));
973 }
974 cover_class = ALLOCNO_COVER_CLASS (allocno);
975 ira_assert ((colorable_p
976 && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
977 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)]
978 <= ALLOCNO_AVAILABLE_REGS_NUM (allocno)))
979 || (! colorable_p
980 && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
981 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE
982 (allocno)]
983 > ALLOCNO_AVAILABLE_REGS_NUM (allocno))));
984 if (! colorable_p)
985 ALLOCNO_MAY_BE_SPILLED_P (allocno) = true;
986 push_allocno_to_stack (allocno);
987}
988
989/* Put all allocnos from colorable bucket onto the coloring stack. */
990static void
991push_only_colorable (void)
992{
993 sort_bucket (&colorable_allocno_bucket);
994 for (;colorable_allocno_bucket != NULL;)
995 remove_allocno_from_bucket_and_push (colorable_allocno_bucket, true);
996}
997
998/* Puts ALLOCNO chosen for potential spilling onto the coloring
999 stack. */
1000static void
1001push_allocno_to_spill (ira_allocno_t allocno)
1002{
1003 delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
1004 ALLOCNO_MAY_BE_SPILLED_P (allocno) = true;
1005 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1006 fprintf (ira_dump_file, " Pushing p%d(%d) (spill for NO_REGS)\n",
1007 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno));
1008 push_allocno_to_stack (allocno);
1009}
1010
1011/* Return the frequency of exit edges (if EXIT_P) or entry from/to the
1012 loop given by its LOOP_NODE. */
1013int
1014ira_loop_edge_freq (ira_loop_tree_node_t loop_node, int regno, bool exit_p)
1015{
1016 int freq, i;
1017 edge_iterator ei;
1018 edge e;
1019 VEC (edge, heap) *edges;
1020
1021 ira_assert (loop_node->loop != NULL
1022 && (regno < 0 || regno >= FIRST_PSEUDO_REGISTER));
1023 freq = 0;
1024 if (! exit_p)
1025 {
1026 FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
1027 if (e->src != loop_node->loop->latch
1028 && (regno < 0
1029 || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
1030 && bitmap_bit_p (DF_LR_IN (e->dest), regno))))
1031 freq += EDGE_FREQUENCY (e);
1032 }
1033 else
1034 {
1035 edges = get_loop_exit_edges (loop_node->loop);
1036 for (i = 0; VEC_iterate (edge, edges, i, e); i++)
1037 if (regno < 0
1038 || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
1039 && bitmap_bit_p (DF_LR_IN (e->dest), regno)))
1040 freq += EDGE_FREQUENCY (e);
1041 VEC_free (edge, heap, edges);
1042 }
1043
1044 return REG_FREQ_FROM_EDGE_FREQ (freq);
1045}
1046
1047/* Calculate and return the cost of putting allocno A into memory. */
1048static int
1049calculate_allocno_spill_cost (ira_allocno_t a)
1050{
1051 int regno, cost;
1052 enum machine_mode mode;
1053 enum reg_class rclass;
1054 ira_allocno_t parent_allocno;
1055 ira_loop_tree_node_t parent_node, loop_node;
1056
1057 regno = ALLOCNO_REGNO (a);
1058 cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_UPDATED_COVER_CLASS_COST (a);
1059 if (ALLOCNO_CAP (a) != NULL)
1060 return cost;
1061 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
1062 if ((parent_node = loop_node->parent) == NULL)
1063 return cost;
1064 if ((parent_allocno = parent_node->regno_allocno_map[regno]) == NULL)
1065 return cost;
1066 mode = ALLOCNO_MODE (a);
1067 rclass = ALLOCNO_COVER_CLASS (a);
1068 if (ALLOCNO_HARD_REGNO (parent_allocno) < 0)
1069 cost -= (ira_memory_move_cost[mode][rclass][0]
1070 * ira_loop_edge_freq (loop_node, regno, true)
1071 + ira_memory_move_cost[mode][rclass][1]
1072 * ira_loop_edge_freq (loop_node, regno, false));
1073 else
1074 cost += ((ira_memory_move_cost[mode][rclass][1]
1075 * ira_loop_edge_freq (loop_node, regno, true)
1076 + ira_memory_move_cost[mode][rclass][0]
1077 * ira_loop_edge_freq (loop_node, regno, false))
1078 - (ira_get_register_move_cost (mode, rclass, rclass)
1079 * (ira_loop_edge_freq (loop_node, regno, false)
1080 + ira_loop_edge_freq (loop_node, regno, true))));
1081 return cost;
1082}
1083
1084/* Compare keys in the splay tree used to choose best allocno for
1085 spilling. The best allocno has the minimal key. */
1086static int
1087allocno_spill_priority_compare (splay_tree_key k1, splay_tree_key k2)
1088{
1089 int pri1, pri2, diff;
1090 ira_allocno_t a1 = (ira_allocno_t) k1, a2 = (ira_allocno_t) k2;
1091
1092 pri1 = (ALLOCNO_TEMP (a1)
1093 / (ALLOCNO_LEFT_CONFLICTS_NUM (a1)
1094 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a1)][ALLOCNO_MODE (a1)]
1095 + 1));
1096 pri2 = (ALLOCNO_TEMP (a2)
1097 / (ALLOCNO_LEFT_CONFLICTS_NUM (a2)
1098 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a2)][ALLOCNO_MODE (a2)]
1099 + 1));
1100 if ((diff = pri1 - pri2) != 0)
1101 return diff;
1102 if ((diff = ALLOCNO_TEMP (a1) - ALLOCNO_TEMP (a2)) != 0)
1103 return diff;
1104 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
1105}
1106
1107/* Allocate data of SIZE for the splay trees. We allocate only spay
1108 tree roots or splay tree nodes. If you change this, please rewrite
1109 the function. */
1110static void *
1111splay_tree_allocate (int size, void *data ATTRIBUTE_UNUSED)
1112{
1113 if (size != sizeof (struct splay_tree_node_s))
1114 return ira_allocate (size);
1115 return pool_alloc (splay_tree_node_pool);
1116}
1117
1118/* Free data NODE for the splay trees. We allocate and free only spay
1119 tree roots or splay tree nodes. If you change this, please rewrite
1120 the function. */
1121static void
1122splay_tree_free (void *node, void *data ATTRIBUTE_UNUSED)
1123{
1124 int i;
1125 enum reg_class cover_class;
1126
1127 for (i = 0; i < ira_reg_class_cover_size; i++)
1128 {
1129 cover_class = ira_reg_class_cover[i];
1130 if (node == uncolorable_allocnos_splay_tree[cover_class])
1131 {
1132 ira_free (node);
1133 return;
1134 }
1135 }
1136 pool_free (splay_tree_node_pool, node);
1137}
1138
1139/* Push allocnos to the coloring stack. The order of allocnos in the
1140 stack defines the order for the subsequent coloring. */
1141static void
1142push_allocnos_to_stack (void)
1143{
1144 ira_allocno_t allocno, a, i_allocno, *allocno_vec;
1145 enum reg_class cover_class, rclass;
1146 int allocno_pri, i_allocno_pri, allocno_cost, i_allocno_cost;
1147 int i, j, num, cover_class_allocnos_num[N_REG_CLASSES];
1148 ira_allocno_t *cover_class_allocnos[N_REG_CLASSES];
1149 int cost;
1150
1151 /* Initialize. */
1152 VEC_truncate(ira_allocno_t, removed_splay_allocno_vec, 0);
1153 for (i = 0; i < ira_reg_class_cover_size; i++)
1154 {
1155 cover_class = ira_reg_class_cover[i];
1156 cover_class_allocnos_num[cover_class] = 0;
1157 cover_class_allocnos[cover_class] = NULL;
1158 uncolorable_allocnos_splay_tree[cover_class] = NULL;
1159 }
1160 /* Calculate uncolorable allocno spill costs. */
1161 for (allocno = uncolorable_allocno_bucket;
1162 allocno != NULL;
1163 allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno))
1164 if ((cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
1165 {
1166 cover_class_allocnos_num[cover_class]++;
1167 cost = 0;
1168 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1169 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1170 {
1171 cost += calculate_allocno_spill_cost (a);
1172 if (a == allocno)
1173 break;
1174 }
1175 /* ??? Remove cost of copies between the coalesced
1176 allocnos. */
1177 ALLOCNO_TEMP (allocno) = cost;
1178 }
1179 /* Define place where to put uncolorable allocnos of the same cover
1180 class. */
1181 for (num = i = 0; i < ira_reg_class_cover_size; i++)
1182 {
1183 cover_class = ira_reg_class_cover[i];
1184 ira_assert (cover_class_allocnos_num[cover_class]
1185 == uncolorable_allocnos_num[cover_class]);
1186 if (cover_class_allocnos_num[cover_class] != 0)
1187 {
1188 cover_class_allocnos[cover_class] = allocnos_for_spilling + num;
1189 num += cover_class_allocnos_num[cover_class];
1190 cover_class_allocnos_num[cover_class] = 0;
1191 }
1192 if (USE_SPLAY_P (cover_class))
1193 uncolorable_allocnos_splay_tree[cover_class]
1194 = splay_tree_new_with_allocator (allocno_spill_priority_compare,
1195 NULL, NULL, splay_tree_allocate,
1196 splay_tree_free, NULL);
1197 }
1198 ira_assert (num <= ira_allocnos_num);
1199 /* Collect uncolorable allocnos of each cover class. */
1200 for (allocno = uncolorable_allocno_bucket;
1201 allocno != NULL;
1202 allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno))
1203 if ((cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
1204 {
1205 cover_class_allocnos
1206 [cover_class][cover_class_allocnos_num[cover_class]++] = allocno;
1207 if (uncolorable_allocnos_splay_tree[cover_class] != NULL)
1208 splay_tree_insert (uncolorable_allocnos_splay_tree[cover_class],
1209 (splay_tree_key) allocno,
1210 (splay_tree_value) allocno);
1211 }
1212 for (;;)
1213 {
1214 push_only_colorable ();
1215 allocno = uncolorable_allocno_bucket;
1216 if (allocno == NULL)
1217 break;
1218 cover_class = ALLOCNO_COVER_CLASS (allocno);
1219 if (cover_class == NO_REGS)
1220 {
1221 push_allocno_to_spill (allocno);
1222 continue;
1223 }
1224 /* Potential spilling. */
1225 ira_assert
1226 (ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)] > 0);
1227 if (USE_SPLAY_P (cover_class))
1228 {
1229 for (;VEC_length (ira_allocno_t, removed_splay_allocno_vec) != 0;)
1230 {
1231 allocno = VEC_pop (ira_allocno_t, removed_splay_allocno_vec);
1232 ALLOCNO_SPLAY_REMOVED_P (allocno) = false;
1233 rclass = ALLOCNO_COVER_CLASS (allocno);
1234 if (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
1235 + ira_reg_class_nregs [rclass][ALLOCNO_MODE (allocno)]
1236 > ALLOCNO_AVAILABLE_REGS_NUM (allocno))
1237 splay_tree_insert
1238 (uncolorable_allocnos_splay_tree[rclass],
1239 (splay_tree_key) allocno, (splay_tree_value) allocno);
1240 }
1241 allocno = ((ira_allocno_t)
1242 splay_tree_min
1243 (uncolorable_allocnos_splay_tree[cover_class])->key);
1244 splay_tree_remove (uncolorable_allocnos_splay_tree[cover_class],
1245 (splay_tree_key) allocno);
1246 }
1247 else
1248 {
1249 num = cover_class_allocnos_num[cover_class];
1250 ira_assert (num > 0);
1251 allocno_vec = cover_class_allocnos[cover_class];
1252 allocno = NULL;
1253 allocno_pri = allocno_cost = 0;
1254 /* Sort uncolorable allocno to find the one with the lowest
1255 spill cost. */
1256 for (i = 0, j = num - 1; i <= j;)
1257 {
1258 i_allocno = allocno_vec[i];
1259 if (! ALLOCNO_IN_GRAPH_P (i_allocno)
1260 && ALLOCNO_IN_GRAPH_P (allocno_vec[j]))
1261 {
1262 i_allocno = allocno_vec[j];
1263 allocno_vec[j] = allocno_vec[i];
1264 allocno_vec[i] = i_allocno;
1265 }
1266 if (ALLOCNO_IN_GRAPH_P (i_allocno))
1267 {
1268 i++;
1269 ira_assert (ALLOCNO_TEMP (i_allocno) != INT_MAX);
1270 i_allocno_cost = ALLOCNO_TEMP (i_allocno);
1271 i_allocno_pri = allocno_spill_priority (i_allocno);
1272 if (allocno == NULL
1273 || (! ALLOCNO_BAD_SPILL_P (i_allocno)
1274 && ALLOCNO_BAD_SPILL_P (allocno))
1275 || (! (ALLOCNO_BAD_SPILL_P (i_allocno)
1276 && ! ALLOCNO_BAD_SPILL_P (allocno))
1277 && (allocno_pri > i_allocno_pri
1278 || (allocno_pri == i_allocno_pri
1279 && (allocno_cost > i_allocno_cost
1280 || (allocno_cost == i_allocno_cost
1281 && (ALLOCNO_NUM (allocno)
1282 > ALLOCNO_NUM (i_allocno))))))))
1283 {
1284 allocno = i_allocno;
1285 allocno_cost = i_allocno_cost;
1286 allocno_pri = i_allocno_pri;
1287 }
1288 }
1289 if (! ALLOCNO_IN_GRAPH_P (allocno_vec[j]))
1290 j--;
1291 }
1292 ira_assert (allocno != NULL && j >= 0);
1293 cover_class_allocnos_num[cover_class] = j + 1;
1294 }
1295 ira_assert (ALLOCNO_IN_GRAPH_P (allocno)
1296 && ALLOCNO_COVER_CLASS (allocno) == cover_class
1297 && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
1298 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE
1299 (allocno)]
1300 > ALLOCNO_AVAILABLE_REGS_NUM (allocno)));
1301 remove_allocno_from_bucket_and_push (allocno, false);
1302 }
1303 ira_assert (colorable_allocno_bucket == NULL
1304 && uncolorable_allocno_bucket == NULL);
1305 for (i = 0; i < ira_reg_class_cover_size; i++)
1306 {
1307 cover_class = ira_reg_class_cover[i];
1308 ira_assert (uncolorable_allocnos_num[cover_class] == 0);
1309 if (uncolorable_allocnos_splay_tree[cover_class] != NULL)
1310 splay_tree_delete (uncolorable_allocnos_splay_tree[cover_class]);
1311 }
1312}
1313
1314/* Pop the coloring stack and assign hard registers to the popped
1315 allocnos. */
1316static void
1317pop_allocnos_from_stack (void)
1318{
1319 ira_allocno_t allocno;
1320 enum reg_class cover_class;
1321
1322 for (;VEC_length (ira_allocno_t, allocno_stack_vec) != 0;)
1323 {
1324 allocno = VEC_pop (ira_allocno_t, allocno_stack_vec);
1325 cover_class = ALLOCNO_COVER_CLASS (allocno);
1326 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1327 {
1328 fprintf (ira_dump_file, " Popping");
1329 print_coalesced_allocno (allocno);
1330 fprintf (ira_dump_file, " -- ");
1331 }
1332 if (cover_class == NO_REGS)
1333 {
1334 ALLOCNO_HARD_REGNO (allocno) = -1;
1335 ALLOCNO_ASSIGNED_P (allocno) = true;
1336 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno) == NULL);
1337 ira_assert
1338 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno) == NULL);
1339 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1340 fprintf (ira_dump_file, "assign memory\n");
1341 }
1342 else if (assign_hard_reg (allocno, false))
1343 {
1344 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1345 fprintf (ira_dump_file, "assign reg %d\n",
1346 ALLOCNO_HARD_REGNO (allocno));
1347 }
1348 else if (ALLOCNO_ASSIGNED_P (allocno))
1349 {
1350 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1351 fprintf (ira_dump_file, "spill\n");
1352 }
1353 ALLOCNO_IN_GRAPH_P (allocno) = true;
1354 }
1355}
1356
1357/* Set up number of available hard registers for ALLOCNO. */
1358static void
1359setup_allocno_available_regs_num (ira_allocno_t allocno)
1360{
1361 int i, n, hard_regs_num;
1362 enum reg_class cover_class;
1363 ira_allocno_t a;
1364 HARD_REG_SET temp_set;
1365
1366 cover_class = ALLOCNO_COVER_CLASS (allocno);
1367 ALLOCNO_AVAILABLE_REGS_NUM (allocno) = ira_available_class_regs[cover_class];
1368 if (cover_class == NO_REGS)
1369 return;
1370 CLEAR_HARD_REG_SET (temp_set);
1371 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) == allocno);
1372 hard_regs_num = ira_class_hard_regs_num[cover_class];
1373 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1374 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1375 {
1376 IOR_HARD_REG_SET (temp_set, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1377 if (a == allocno)
1378 break;
1379 }
1380 for (n = 0, i = hard_regs_num - 1; i >= 0; i--)
1381 if (TEST_HARD_REG_BIT (temp_set, ira_class_hard_regs[cover_class][i]))
1382 n++;
1383 if (internal_flag_ira_verbose > 2 && n > 0 && ira_dump_file != NULL)
1384 fprintf (ira_dump_file, " Reg %d of %s has %d regs less\n",
1385 ALLOCNO_REGNO (allocno), reg_class_names[cover_class], n);
1386 ALLOCNO_AVAILABLE_REGS_NUM (allocno) -= n;
1387}
1388
1389/* Set up ALLOCNO_LEFT_CONFLICTS_NUM for ALLOCNO. */
1390static void
1391setup_allocno_left_conflicts_num (ira_allocno_t allocno)
1392{
1393 int i, hard_regs_num, hard_regno, conflict_allocnos_size;
1394 ira_allocno_t a, conflict_allocno;
1395 enum reg_class cover_class;
1396 HARD_REG_SET temp_set;
1397 ira_allocno_conflict_iterator aci;
1398
1399 cover_class = ALLOCNO_COVER_CLASS (allocno);
1400 hard_regs_num = ira_class_hard_regs_num[cover_class];
1401 CLEAR_HARD_REG_SET (temp_set);
1402 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) == allocno);
1403 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1404 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1405 {
1406 IOR_HARD_REG_SET (temp_set, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1407 if (a == allocno)
1408 break;
1409 }
1410 AND_HARD_REG_SET (temp_set, reg_class_contents[cover_class]);
1411 AND_COMPL_HARD_REG_SET (temp_set, ira_no_alloc_regs);
1412 conflict_allocnos_size = 0;
1413 if (! hard_reg_set_empty_p (temp_set))
1414 for (i = 0; i < (int) hard_regs_num; i++)
1415 {
1416 hard_regno = ira_class_hard_regs[cover_class][i];
1417 if (TEST_HARD_REG_BIT (temp_set, hard_regno))
1418 {
1419 conflict_allocnos_size++;
1420 CLEAR_HARD_REG_BIT (temp_set, hard_regno);
1421 if (hard_reg_set_empty_p (temp_set))
1422 break;
1423 }
1424 }
1425 CLEAR_HARD_REG_SET (temp_set);
1426 if (allocno_coalesced_p)
1427 bitmap_clear (processed_coalesced_allocno_bitmap);
1428 if (cover_class != NO_REGS)
1429 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1430 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1431 {
1432 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
1433 {
1434 conflict_allocno
1435 = ALLOCNO_FIRST_COALESCED_ALLOCNO (conflict_allocno);
1436 if (bitmap_bit_p (consideration_allocno_bitmap,
1437 ALLOCNO_NUM (conflict_allocno)))
1438 {
1439 ira_assert (cover_class
1440 == ALLOCNO_COVER_CLASS (conflict_allocno));
1441 if (allocno_coalesced_p)
1442 {
1443 if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
1444 ALLOCNO_NUM (conflict_allocno)))
1445 continue;
1446 bitmap_set_bit (processed_coalesced_allocno_bitmap,
1447 ALLOCNO_NUM (conflict_allocno));
1448 }
1449 if (! ALLOCNO_ASSIGNED_P (conflict_allocno))
1450 conflict_allocnos_size
1451 += (ira_reg_class_nregs
1452 [cover_class][ALLOCNO_MODE (conflict_allocno)]);
1453 else if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno))
1454 >= 0)
1455 {
1456 int last = (hard_regno
1457 + hard_regno_nregs
1458 [hard_regno][ALLOCNO_MODE (conflict_allocno)]);
1459
1460 while (hard_regno < last)
1461 {
1462 if (! TEST_HARD_REG_BIT (temp_set, hard_regno))
1463 {
1464 conflict_allocnos_size++;
1465 SET_HARD_REG_BIT (temp_set, hard_regno);
1466 }
1467 hard_regno++;
1468 }
1469 }
1470 }
1471 }
1472 if (a == allocno)
1473 break;
1474 }
1475 ALLOCNO_LEFT_CONFLICTS_NUM (allocno) = conflict_allocnos_size;
1476}
1477
1478/* Put ALLOCNO in a bucket corresponding to its number and size of its
1479 conflicting allocnos and hard registers. */
1480static void
1481put_allocno_into_bucket (ira_allocno_t allocno)
1482{
1483 int hard_regs_num;
1484 enum reg_class cover_class;
1485
1486 cover_class = ALLOCNO_COVER_CLASS (allocno);
1487 hard_regs_num = ira_class_hard_regs_num[cover_class];
1488 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
1489 return;
1490 ALLOCNO_IN_GRAPH_P (allocno) = true;
1491 setup_allocno_left_conflicts_num (allocno);
1492 setup_allocno_available_regs_num (allocno);
1493 if (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
1494 + ira_reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)]
1495 <= ALLOCNO_AVAILABLE_REGS_NUM (allocno))
1496 add_allocno_to_bucket (allocno, &colorable_allocno_bucket);
1497 else
1498 add_allocno_to_bucket (allocno, &uncolorable_allocno_bucket);
1499}
1500
1501/* The function is used to sort allocnos according to their execution
1502 frequencies. */
1503static int
1504copy_freq_compare_func (const void *v1p, const void *v2p)
1505{
1506 ira_copy_t cp1 = *(const ira_copy_t *) v1p, cp2 = *(const ira_copy_t *) v2p;
1507 int pri1, pri2;
1508
1509 pri1 = cp1->freq;
1510 pri2 = cp2->freq;
1511 if (pri2 - pri1)
1512 return pri2 - pri1;
1513
1514 /* If freqencies are equal, sort by copies, so that the results of
1515 qsort leave nothing to chance. */
1516 return cp1->num - cp2->num;
1517}
1518
1519/* Merge two sets of coalesced allocnos given correspondingly by
1520 allocnos A1 and A2 (more accurately merging A2 set into A1
1521 set). */
1522static void
1523merge_allocnos (ira_allocno_t a1, ira_allocno_t a2)
1524{
1525 ira_allocno_t a, first, last, next;
1526
1527 first = ALLOCNO_FIRST_COALESCED_ALLOCNO (a1);
1528 if (first == ALLOCNO_FIRST_COALESCED_ALLOCNO (a2))
1529 return;
1530 for (last = a2, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
1531 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1532 {
1533 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = first;
1534 if (a == a2)
1535 break;
1536 last = a;
1537 }
1538 next = ALLOCNO_NEXT_COALESCED_ALLOCNO (first);
1539 ALLOCNO_NEXT_COALESCED_ALLOCNO (first) = a2;
1540 ALLOCNO_NEXT_COALESCED_ALLOCNO (last) = next;
1541}
1542
1543/* Return TRUE if there are conflicting allocnos from two sets of
1544 coalesced allocnos given correspondingly by allocnos A1 and A2. If
1545 RELOAD_P is TRUE, we use live ranges to find conflicts because
1546 conflicts are represented only for allocnos of the same cover class
1547 and during the reload pass we coalesce allocnos for sharing stack
1548 memory slots. */
1549static bool
1550coalesced_allocno_conflict_p (ira_allocno_t a1, ira_allocno_t a2,
1551 bool reload_p)
1552{
1553 ira_allocno_t a, conflict_allocno;
1554 ira_allocno_conflict_iterator aci;
1555
1556 if (allocno_coalesced_p)
1557 {
1558 bitmap_clear (processed_coalesced_allocno_bitmap);
1559 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
1560 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1561 {
1562 bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a));
1563 if (a == a1)
1564 break;
1565 }
1566 }
1567 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
1568 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1569 {
1570 if (reload_p)
1571 {
1572 for (conflict_allocno = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
1573 conflict_allocno
1574 = ALLOCNO_NEXT_COALESCED_ALLOCNO (conflict_allocno))
1575 {
1576 if (allocnos_have_intersected_live_ranges_p (a,
1577 conflict_allocno))
1578 return true;
1579 if (conflict_allocno == a1)
1580 break;
1581 }
1582 }
1583 else
1584 {
1585 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
1586 if (conflict_allocno == a1
1587 || (allocno_coalesced_p
1588 && bitmap_bit_p (processed_coalesced_allocno_bitmap,
1589 ALLOCNO_NUM (conflict_allocno))))
1590 return true;
1591 }
1592 if (a == a2)
1593 break;
1594 }
1595 return false;
1596}
1597
1598/* The major function for aggressive allocno coalescing. For the
1599 reload pass (RELOAD_P) we coalesce only spilled allocnos. If some
1600 allocnos have been coalesced, we set up flag
1601 allocno_coalesced_p. */
1602static void
1603coalesce_allocnos (bool reload_p)
1604{
1605 ira_allocno_t a;
1606 ira_copy_t cp, next_cp, *sorted_copies;
1607 enum reg_class cover_class;
1608 enum machine_mode mode;
1609 unsigned int j;
1610 int i, n, cp_num, regno;
1611 bitmap_iterator bi;
1612
1613 sorted_copies = (ira_copy_t *) ira_allocate (ira_copies_num
1614 * sizeof (ira_copy_t));
1615 cp_num = 0;
1616 /* Collect copies. */
1617 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
1618 {
1619 a = ira_allocnos[j];
1620 regno = ALLOCNO_REGNO (a);
1621 if ((! reload_p && ALLOCNO_ASSIGNED_P (a))
1622 || (reload_p
1623 && (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0
1624 || (regno < ira_reg_equiv_len
1625 && (ira_reg_equiv_const[regno] != NULL_RTX
1626 || ira_reg_equiv_invariant_p[regno])))))
1627 continue;
1628 cover_class = ALLOCNO_COVER_CLASS (a);
1629 mode = ALLOCNO_MODE (a);
1630 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
1631 {
1632 if (cp->first == a)
1633 {
1634 next_cp = cp->next_first_allocno_copy;
1635 regno = ALLOCNO_REGNO (cp->second);
1636 /* For priority coloring we coalesce allocnos only with
1637 the same cover class not with intersected cover
1638 classes as it were possible. It is done for
1639 simplicity. */
1640 if ((reload_p
1641 || (ALLOCNO_COVER_CLASS (cp->second) == cover_class
1642 && ALLOCNO_MODE (cp->second) == mode))
1643 && (cp->insn != NULL || cp->constraint_p)
1644 && ((! reload_p && ! ALLOCNO_ASSIGNED_P (cp->second))
1645 || (reload_p
1646 && ALLOCNO_ASSIGNED_P (cp->second)
1647 && ALLOCNO_HARD_REGNO (cp->second) < 0
1648 && (regno >= ira_reg_equiv_len
1649 || (! ira_reg_equiv_invariant_p[regno]
1650 && ira_reg_equiv_const[regno] == NULL_RTX)))))
1651 sorted_copies[cp_num++] = cp;
1652 }
1653 else if (cp->second == a)
1654 next_cp = cp->next_second_allocno_copy;
1655 else
1656 gcc_unreachable ();
1657 }
1658 }
1659 qsort (sorted_copies, cp_num, sizeof (ira_copy_t), copy_freq_compare_func);
1660 /* Coalesced copies, most frequently executed first. */
1661 for (; cp_num != 0;)
1662 {
1663 for (i = 0; i < cp_num; i++)
1664 {
1665 cp = sorted_copies[i];
1666 if (! coalesced_allocno_conflict_p (cp->first, cp->second, reload_p))
1667 {
1668 allocno_coalesced_p = true;
1669 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1670 fprintf
1671 (ira_dump_file,
1672 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
1673 cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
1674 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
1675 cp->freq);
1676 merge_allocnos (cp->first, cp->second);
1677 i++;
1678 break;
1679 }
1680 }
1681 /* Collect the rest of copies. */
1682 for (n = 0; i < cp_num; i++)
1683 {
1684 cp = sorted_copies[i];
1685 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->first)
1686 != ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->second))
1687 sorted_copies[n++] = cp;
1688 }
1689 cp_num = n;
1690 }
1691 ira_free (sorted_copies);
1692}
1693
1694/* Map: allocno number -> allocno priority. */
1695static int *allocno_priorities;
1696
1697/* Set up priorities for N allocnos in array
1698 CONSIDERATION_ALLOCNOS. */
1699static void
1700setup_allocno_priorities (ira_allocno_t *consideration_allocnos, int n)
1701{
1702 int i, length, nrefs, priority, max_priority, mult;
1703 ira_allocno_t a;
1704
1705 max_priority = 0;
1706 for (i = 0; i < n; i++)
1707 {
1708 a = consideration_allocnos[i];
1709 nrefs = ALLOCNO_NREFS (a);
1710 ira_assert (nrefs >= 0);
1711 mult = floor_log2 (ALLOCNO_NREFS (a)) + 1;
1712 ira_assert (mult >= 0);
1713 allocno_priorities[ALLOCNO_NUM (a)]
1714 = priority
1715 = (mult
1716 * (ALLOCNO_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a))
1717 * ira_reg_class_nregs[ALLOCNO_COVER_CLASS (a)][ALLOCNO_MODE (a)]);
1718 if (priority < 0)
1719 priority = -priority;
1720 if (max_priority < priority)
1721 max_priority = priority;
1722 }
1723 mult = max_priority == 0 ? 1 : INT_MAX / max_priority;
1724 for (i = 0; i < n; i++)
1725 {
1726 a = consideration_allocnos[i];
1727 length = ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
1728 if (length <= 0)
1729 length = 1;
1730 allocno_priorities[ALLOCNO_NUM (a)]
1731 = allocno_priorities[ALLOCNO_NUM (a)] * mult / length;
1732 }
1733}
1734
1735/* Sort allocnos according to their priorities which are calculated
1736 analogous to ones in file `global.c'. */
1737static int
1738allocno_priority_compare_func (const void *v1p, const void *v2p)
1739{
1740 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
1741 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
1742 int pri1, pri2;
1743
1744 pri1 = allocno_priorities[ALLOCNO_NUM (a1)];
1745 pri2 = allocno_priorities[ALLOCNO_NUM (a2)];
4b1e227d
SW
1746 if (pri2 != pri1)
1747 return SORTGT (pri2, pri1);
c251ad9e
SS
1748
1749 /* If regs are equally good, sort by allocnos, so that the results of
1750 qsort leave nothing to chance. */
1751 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
1752}
1753
1754/* Chaitin-Briggs coloring for allocnos in COLORING_ALLOCNO_BITMAP
1755 taking into account allocnos in CONSIDERATION_ALLOCNO_BITMAP. */
1756static void
1757color_allocnos (void)
1758{
1759 unsigned int i, n;
1760 bitmap_iterator bi;
1761 ira_allocno_t a;
1762
1763 allocno_coalesced_p = false;
1764 processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
1765 if (flag_ira_coalesce)
1766 coalesce_allocnos (false);
1767 if (flag_ira_algorithm == IRA_ALGORITHM_PRIORITY)
1768 {
1769 n = 0;
1770 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1771 {
1772 a = ira_allocnos[i];
1773 if (ALLOCNO_COVER_CLASS (a) == NO_REGS)
1774 {
1775 ALLOCNO_HARD_REGNO (a) = -1;
1776 ALLOCNO_ASSIGNED_P (a) = true;
1777 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
1778 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
1779 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1780 {
1781 fprintf (ira_dump_file, " Spill");
1782 print_coalesced_allocno (a);
1783 fprintf (ira_dump_file, "\n");
1784 }
1785 continue;
1786 }
1787 sorted_allocnos[n++] = a;
1788 }
1789 if (n != 0)
1790 {
1791 setup_allocno_priorities (sorted_allocnos, n);
1792 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
1793 allocno_priority_compare_func);
1794 for (i = 0; i < n; i++)
1795 {
1796 a = sorted_allocnos[i];
1797 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1798 {
1799 fprintf (ira_dump_file, " ");
1800 print_coalesced_allocno (a);
1801 fprintf (ira_dump_file, " -- ");
1802 }
1803 if (assign_hard_reg (a, false))
1804 {
1805 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1806 fprintf (ira_dump_file, "assign hard reg %d\n",
1807 ALLOCNO_HARD_REGNO (a));
1808 }
1809 else
1810 {
1811 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1812 fprintf (ira_dump_file, "assign memory\n");
1813 }
1814 }
1815 }
1816 }
1817 else
1818 {
1819 /* Put the allocnos into the corresponding buckets. */
1820 colorable_allocno_bucket = NULL;
1821 uncolorable_allocno_bucket = NULL;
1822 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1823 {
1824 a = ira_allocnos[i];
1825 if (ALLOCNO_COVER_CLASS (a) == NO_REGS)
1826 {
1827 ALLOCNO_HARD_REGNO (a) = -1;
1828 ALLOCNO_ASSIGNED_P (a) = true;
1829 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
1830 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
1831 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1832 {
1833 fprintf (ira_dump_file, " Spill");
1834 print_coalesced_allocno (a);
1835 fprintf (ira_dump_file, "\n");
1836 }
1837 continue;
1838 }
1839 put_allocno_into_bucket (a);
1840 }
1841 push_allocnos_to_stack ();
1842 pop_allocnos_from_stack ();
1843 }
1844 if (flag_ira_coalesce)
1845 /* We don't need coalesced allocnos for ira_reassign_pseudos. */
1846 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1847 {
1848 a = ira_allocnos[i];
1849 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
1850 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
1851 }
1852 ira_free_bitmap (processed_coalesced_allocno_bitmap);
1853 allocno_coalesced_p = false;
1854}
1855
1856\f
1857
1858/* Output information about the loop given by its LOOP_TREE_NODE. */
1859static void
1860print_loop_title (ira_loop_tree_node_t loop_tree_node)
1861{
1862 unsigned int j;
1863 bitmap_iterator bi;
1864 ira_loop_tree_node_t subloop_node, dest_loop_node;
1865 edge e;
1866 edge_iterator ei;
1867
1868 ira_assert (loop_tree_node->loop != NULL);
1869 fprintf (ira_dump_file,
1870 "\n Loop %d (parent %d, header bb%d, depth %d)\n bbs:",
1871 loop_tree_node->loop->num,
1872 (loop_tree_node->parent == NULL
1873 ? -1 : loop_tree_node->parent->loop->num),
1874 loop_tree_node->loop->header->index,
1875 loop_depth (loop_tree_node->loop));
1876 for (subloop_node = loop_tree_node->children;
1877 subloop_node != NULL;
1878 subloop_node = subloop_node->next)
1879 if (subloop_node->bb != NULL)
1880 {
1881 fprintf (ira_dump_file, " %d", subloop_node->bb->index);
1882 FOR_EACH_EDGE (e, ei, subloop_node->bb->succs)
1883 if (e->dest != EXIT_BLOCK_PTR
1884 && ((dest_loop_node = IRA_BB_NODE (e->dest)->parent)
1885 != loop_tree_node))
1886 fprintf (ira_dump_file, "(->%d:l%d)",
1887 e->dest->index, dest_loop_node->loop->num);
1888 }
1889 fprintf (ira_dump_file, "\n all:");
1890 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
1891 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
1892 fprintf (ira_dump_file, "\n modified regnos:");
1893 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->modified_regnos, 0, j, bi)
1894 fprintf (ira_dump_file, " %d", j);
1895 fprintf (ira_dump_file, "\n border:");
1896 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->border_allocnos, 0, j, bi)
1897 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (ira_allocnos[j]));
1898 fprintf (ira_dump_file, "\n Pressure:");
1899 for (j = 0; (int) j < ira_reg_class_cover_size; j++)
1900 {
1901 enum reg_class cover_class;
1902
1903 cover_class = ira_reg_class_cover[j];
1904 if (loop_tree_node->reg_pressure[cover_class] == 0)
1905 continue;
1906 fprintf (ira_dump_file, " %s=%d", reg_class_names[cover_class],
1907 loop_tree_node->reg_pressure[cover_class]);
1908 }
1909 fprintf (ira_dump_file, "\n");
1910}
1911
1912/* Color the allocnos inside loop (in the extreme case it can be all
1913 of the function) given the corresponding LOOP_TREE_NODE. The
1914 function is called for each loop during top-down traverse of the
1915 loop tree. */
1916static void
1917color_pass (ira_loop_tree_node_t loop_tree_node)
1918{
1919 int regno, hard_regno, index = -1;
1920 int cost, exit_freq, enter_freq;
1921 unsigned int j;
1922 bitmap_iterator bi;
1923 enum machine_mode mode;
1924 enum reg_class rclass, cover_class;
1925 ira_allocno_t a, subloop_allocno;
1926 ira_loop_tree_node_t subloop_node;
1927
1928 ira_assert (loop_tree_node->bb == NULL);
1929 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1930 print_loop_title (loop_tree_node);
1931
1932 bitmap_copy (coloring_allocno_bitmap, loop_tree_node->all_allocnos);
1933 bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap);
1934 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
1935 {
1936 a = ira_allocnos[j];
1937 if (! ALLOCNO_ASSIGNED_P (a))
1938 continue;
1939 bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a));
1940 }
1941 /* Color all mentioned allocnos including transparent ones. */
1942 color_allocnos ();
1943 /* Process caps. They are processed just once. */
1944 if (flag_ira_region == IRA_REGION_MIXED
1945 || flag_ira_region == IRA_REGION_ALL)
1946 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->all_allocnos, 0, j, bi)
1947 {
1948 a = ira_allocnos[j];
1949 if (ALLOCNO_CAP_MEMBER (a) == NULL)
1950 continue;
1951 /* Remove from processing in the next loop. */
1952 bitmap_clear_bit (consideration_allocno_bitmap, j);
1953 rclass = ALLOCNO_COVER_CLASS (a);
1954 if (flag_ira_region == IRA_REGION_MIXED
1955 && (loop_tree_node->reg_pressure[rclass]
1956 <= ira_available_class_regs[rclass]))
1957 {
1958 mode = ALLOCNO_MODE (a);
1959 hard_regno = ALLOCNO_HARD_REGNO (a);
1960 if (hard_regno >= 0)
1961 {
1962 index = ira_class_hard_reg_index[rclass][hard_regno];
1963 ira_assert (index >= 0);
1964 }
1965 regno = ALLOCNO_REGNO (a);
1966 subloop_allocno = ALLOCNO_CAP_MEMBER (a);
1967 subloop_node = ALLOCNO_LOOP_TREE_NODE (subloop_allocno);
1968 ira_assert (!ALLOCNO_ASSIGNED_P (subloop_allocno));
1969 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
1970 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
1971 if (hard_regno >= 0)
1972 update_copy_costs (subloop_allocno, true);
1973 /* We don't need updated costs anymore: */
1974 ira_free_allocno_updated_costs (subloop_allocno);
1975 }
1976 }
1977 /* Update costs of the corresponding allocnos (not caps) in the
1978 subloops. */
1979 for (subloop_node = loop_tree_node->subloops;
1980 subloop_node != NULL;
1981 subloop_node = subloop_node->subloop_next)
1982 {
1983 ira_assert (subloop_node->bb == NULL);
1984 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
1985 {
1986 a = ira_allocnos[j];
1987 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
1988 mode = ALLOCNO_MODE (a);
1989 rclass = ALLOCNO_COVER_CLASS (a);
1990 hard_regno = ALLOCNO_HARD_REGNO (a);
1991 /* Use hard register class here. ??? */
1992 if (hard_regno >= 0)
1993 {
1994 index = ira_class_hard_reg_index[rclass][hard_regno];
1995 ira_assert (index >= 0);
1996 }
1997 regno = ALLOCNO_REGNO (a);
1998 /* ??? conflict costs */
1999 subloop_allocno = subloop_node->regno_allocno_map[regno];
2000 if (subloop_allocno == NULL
2001 || ALLOCNO_CAP (subloop_allocno) != NULL)
2002 continue;
2003 ira_assert (ALLOCNO_COVER_CLASS (subloop_allocno) == rclass);
2004 ira_assert (bitmap_bit_p (subloop_node->all_allocnos,
2005 ALLOCNO_NUM (subloop_allocno)));
2006 if ((flag_ira_region == IRA_REGION_MIXED)
2007 && (loop_tree_node->reg_pressure[rclass]
2008 <= ira_available_class_regs[rclass]))
2009 {
2010 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
2011 {
2012 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
2013 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
2014 if (hard_regno >= 0)
2015 update_copy_costs (subloop_allocno, true);
2016 /* We don't need updated costs anymore: */
2017 ira_free_allocno_updated_costs (subloop_allocno);
2018 }
2019 continue;
2020 }
2021 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
2022 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
2023 ira_assert (regno < ira_reg_equiv_len);
2024 if (ira_reg_equiv_invariant_p[regno]
2025 || ira_reg_equiv_const[regno] != NULL_RTX)
2026 {
2027 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
2028 {
2029 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
2030 ALLOCNO_ASSIGNED_P (subloop_allocno) = true;
2031 if (hard_regno >= 0)
2032 update_copy_costs (subloop_allocno, true);
2033 /* We don't need updated costs anymore: */
2034 ira_free_allocno_updated_costs (subloop_allocno);
2035 }
2036 }
2037 else if (hard_regno < 0)
2038 {
2039 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
2040 -= ((ira_memory_move_cost[mode][rclass][1] * enter_freq)
2041 + (ira_memory_move_cost[mode][rclass][0] * exit_freq));
2042 }
2043 else
2044 {
2045 cover_class = ALLOCNO_COVER_CLASS (subloop_allocno);
2046 cost = (ira_get_register_move_cost (mode, rclass, rclass)
2047 * (exit_freq + enter_freq));
2048 ira_allocate_and_set_or_copy_costs
2049 (&ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno), cover_class,
2050 ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno),
2051 ALLOCNO_HARD_REG_COSTS (subloop_allocno));
2052 ira_allocate_and_set_or_copy_costs
2053 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno),
2054 cover_class, 0,
2055 ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno));
2056 ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
2057 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
2058 -= cost;
2059 if (ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno)
2060 > ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index])
2061 ALLOCNO_UPDATED_COVER_CLASS_COST (subloop_allocno)
2062 = ALLOCNO_UPDATED_HARD_REG_COSTS (subloop_allocno)[index];
2063 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
2064 += (ira_memory_move_cost[mode][rclass][0] * enter_freq
2065 + ira_memory_move_cost[mode][rclass][1] * exit_freq);
2066 }
2067 }
2068 }
2069}
2070
2071/* Initialize the common data for coloring and calls functions to do
2072 Chaitin-Briggs and regional coloring. */
2073static void
2074do_coloring (void)
2075{
2076 coloring_allocno_bitmap = ira_allocate_bitmap ();
2077 allocnos_for_spilling
2078 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
2079 * ira_allocnos_num);
2080 splay_tree_node_pool = create_alloc_pool ("splay tree nodes",
2081 sizeof (struct splay_tree_node_s),
2082 100);
2083 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2084 fprintf (ira_dump_file, "\n**** Allocnos coloring:\n\n");
2085
2086 ira_traverse_loop_tree (false, ira_loop_tree_root, color_pass, NULL);
2087
2088 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2089 ira_print_disposition (ira_dump_file);
2090
2091 free_alloc_pool (splay_tree_node_pool);
2092 ira_free_bitmap (coloring_allocno_bitmap);
2093 ira_free (allocnos_for_spilling);
2094}
2095
2096\f
2097
2098/* Move spill/restore code, which are to be generated in ira-emit.c,
2099 to less frequent points (if it is profitable) by reassigning some
2100 allocnos (in loop with subloops containing in another loop) to
2101 memory which results in longer live-range where the corresponding
2102 pseudo-registers will be in memory. */
2103static void
2104move_spill_restore (void)
2105{
2106 int cost, regno, hard_regno, hard_regno2, index;
2107 bool changed_p;
2108 int enter_freq, exit_freq;
2109 enum machine_mode mode;
2110 enum reg_class rclass;
2111 ira_allocno_t a, parent_allocno, subloop_allocno;
2112 ira_loop_tree_node_t parent, loop_node, subloop_node;
2113 ira_allocno_iterator ai;
2114
2115 for (;;)
2116 {
2117 changed_p = false;
2118 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2119 fprintf (ira_dump_file, "New iteration of spill/restore move\n");
2120 FOR_EACH_ALLOCNO (a, ai)
2121 {
2122 regno = ALLOCNO_REGNO (a);
2123 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
2124 if (ALLOCNO_CAP_MEMBER (a) != NULL
2125 || ALLOCNO_CAP (a) != NULL
2126 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0
2127 || loop_node->children == NULL
2128 /* don't do the optimization because it can create
2129 copies and the reload pass can spill the allocno set
2130 by copy although the allocno will not get memory
2131 slot. */
2132 || ira_reg_equiv_invariant_p[regno]
2133 || ira_reg_equiv_const[regno] != NULL_RTX
2134 || !bitmap_bit_p (loop_node->border_allocnos, ALLOCNO_NUM (a)))
2135 continue;
2136 mode = ALLOCNO_MODE (a);
2137 rclass = ALLOCNO_COVER_CLASS (a);
2138 index = ira_class_hard_reg_index[rclass][hard_regno];
2139 ira_assert (index >= 0);
2140 cost = (ALLOCNO_MEMORY_COST (a)
2141 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
2142 ? ALLOCNO_COVER_CLASS_COST (a)
2143 : ALLOCNO_HARD_REG_COSTS (a)[index]));
2144 for (subloop_node = loop_node->subloops;
2145 subloop_node != NULL;
2146 subloop_node = subloop_node->subloop_next)
2147 {
2148 ira_assert (subloop_node->bb == NULL);
2149 subloop_allocno = subloop_node->regno_allocno_map[regno];
2150 if (subloop_allocno == NULL)
2151 continue;
2152 ira_assert (rclass == ALLOCNO_COVER_CLASS (subloop_allocno));
2153 /* We have accumulated cost. To get the real cost of
2154 allocno usage in the loop we should subtract costs of
2155 the subloop allocnos. */
2156 cost -= (ALLOCNO_MEMORY_COST (subloop_allocno)
2157 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno) == NULL
2158 ? ALLOCNO_COVER_CLASS_COST (subloop_allocno)
2159 : ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index]));
2160 exit_freq = ira_loop_edge_freq (subloop_node, regno, true);
2161 enter_freq = ira_loop_edge_freq (subloop_node, regno, false);
2162 if ((hard_regno2 = ALLOCNO_HARD_REGNO (subloop_allocno)) < 0)
2163 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
2164 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
2165 else
2166 {
2167 cost
2168 += (ira_memory_move_cost[mode][rclass][0] * exit_freq
2169 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
2170 if (hard_regno2 != hard_regno)
2171 cost -= (ira_get_register_move_cost (mode, rclass, rclass)
2172 * (exit_freq + enter_freq));
2173 }
2174 }
2175 if ((parent = loop_node->parent) != NULL
2176 && (parent_allocno = parent->regno_allocno_map[regno]) != NULL)
2177 {
2178 ira_assert (rclass == ALLOCNO_COVER_CLASS (parent_allocno));
2179 exit_freq = ira_loop_edge_freq (loop_node, regno, true);
2180 enter_freq = ira_loop_edge_freq (loop_node, regno, false);
2181 if ((hard_regno2 = ALLOCNO_HARD_REGNO (parent_allocno)) < 0)
2182 cost -= (ira_memory_move_cost[mode][rclass][0] * exit_freq
2183 + ira_memory_move_cost[mode][rclass][1] * enter_freq);
2184 else
2185 {
2186 cost
2187 += (ira_memory_move_cost[mode][rclass][1] * exit_freq
2188 + ira_memory_move_cost[mode][rclass][0] * enter_freq);
2189 if (hard_regno2 != hard_regno)
2190 cost -= (ira_get_register_move_cost (mode, rclass, rclass)
2191 * (exit_freq + enter_freq));
2192 }
2193 }
2194 if (cost < 0)
2195 {
2196 ALLOCNO_HARD_REGNO (a) = -1;
2197 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2198 {
2199 fprintf
2200 (ira_dump_file,
2201 " Moving spill/restore for a%dr%d up from loop %d",
2202 ALLOCNO_NUM (a), regno, loop_node->loop->num);
2203 fprintf (ira_dump_file, " - profit %d\n", -cost);
2204 }
2205 changed_p = true;
2206 }
2207 }
2208 if (! changed_p)
2209 break;
2210 }
2211}
2212
2213\f
2214
2215/* Update current hard reg costs and current conflict hard reg costs
2216 for allocno A. It is done by processing its copies containing
2217 other allocnos already assigned. */
2218static void
2219update_curr_costs (ira_allocno_t a)
2220{
2221 int i, hard_regno, cost;
2222 enum machine_mode mode;
2223 enum reg_class cover_class, rclass;
2224 ira_allocno_t another_a;
2225 ira_copy_t cp, next_cp;
2226
2227 ira_assert (! ALLOCNO_ASSIGNED_P (a));
2228 cover_class = ALLOCNO_COVER_CLASS (a);
2229 if (cover_class == NO_REGS)
2230 return;
2231 mode = ALLOCNO_MODE (a);
2232 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2233 {
2234 if (cp->first == a)
2235 {
2236 next_cp = cp->next_first_allocno_copy;
2237 another_a = cp->second;
2238 }
2239 else if (cp->second == a)
2240 {
2241 next_cp = cp->next_second_allocno_copy;
2242 another_a = cp->first;
2243 }
2244 else
2245 gcc_unreachable ();
2246 if (! ira_reg_classes_intersect_p[cover_class][ALLOCNO_COVER_CLASS
2247 (another_a)]
2248 || ! ALLOCNO_ASSIGNED_P (another_a)
2249 || (hard_regno = ALLOCNO_HARD_REGNO (another_a)) < 0)
2250 continue;
2251 rclass = REGNO_REG_CLASS (hard_regno);
2252 i = ira_class_hard_reg_index[cover_class][hard_regno];
2253 if (i < 0)
2254 continue;
2255 cost = (cp->first == a
2256 ? ira_get_register_move_cost (mode, rclass, cover_class)
2257 : ira_get_register_move_cost (mode, cover_class, rclass));
2258 ira_allocate_and_set_or_copy_costs
2259 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
2260 cover_class, ALLOCNO_COVER_CLASS_COST (a),
2261 ALLOCNO_HARD_REG_COSTS (a));
2262 ira_allocate_and_set_or_copy_costs
2263 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
2264 cover_class, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
2265 ALLOCNO_UPDATED_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
2266 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
2267 }
2268}
2269
2270/* Try to assign hard registers to the unassigned allocnos and
2271 allocnos conflicting with them or conflicting with allocnos whose
2272 regno >= START_REGNO. The function is called after ira_flattening,
2273 so more allocnos (including ones created in ira-emit.c) will have a
2274 chance to get a hard register. We use simple assignment algorithm
2275 based on priorities. */
2276void
2277ira_reassign_conflict_allocnos (int start_regno)
2278{
2279 int i, allocnos_to_color_num;
2280 ira_allocno_t a, conflict_a;
2281 ira_allocno_conflict_iterator aci;
2282 enum reg_class cover_class;
2283 bitmap allocnos_to_color;
2284 ira_allocno_iterator ai;
2285
2286 allocnos_to_color = ira_allocate_bitmap ();
2287 allocnos_to_color_num = 0;
2288 FOR_EACH_ALLOCNO (a, ai)
2289 {
2290 if (! ALLOCNO_ASSIGNED_P (a)
2291 && ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a)))
2292 {
2293 if (ALLOCNO_COVER_CLASS (a) != NO_REGS)
2294 sorted_allocnos[allocnos_to_color_num++] = a;
2295 else
2296 {
2297 ALLOCNO_ASSIGNED_P (a) = true;
2298 ALLOCNO_HARD_REGNO (a) = -1;
2299 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2300 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2301 }
2302 bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (a));
2303 }
2304 if (ALLOCNO_REGNO (a) < start_regno
2305 || (cover_class = ALLOCNO_COVER_CLASS (a)) == NO_REGS)
2306 continue;
2307 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
2308 {
2309 ira_assert (ira_reg_classes_intersect_p
2310 [cover_class][ALLOCNO_COVER_CLASS (conflict_a)]);
2311 if (bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (conflict_a)))
2312 continue;
2313 bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a));
2314 sorted_allocnos[allocnos_to_color_num++] = conflict_a;
2315 }
2316 }
2317 ira_free_bitmap (allocnos_to_color);
2318 if (allocnos_to_color_num > 1)
2319 {
2320 setup_allocno_priorities (sorted_allocnos, allocnos_to_color_num);
2321 qsort (sorted_allocnos, allocnos_to_color_num, sizeof (ira_allocno_t),
2322 allocno_priority_compare_func);
2323 }
2324 for (i = 0; i < allocnos_to_color_num; i++)
2325 {
2326 a = sorted_allocnos[i];
2327 ALLOCNO_ASSIGNED_P (a) = false;
2328 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2329 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2330 update_curr_costs (a);
2331 }
2332 for (i = 0; i < allocnos_to_color_num; i++)
2333 {
2334 a = sorted_allocnos[i];
2335 if (assign_hard_reg (a, true))
2336 {
2337 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2338 fprintf
2339 (ira_dump_file,
2340 " Secondary allocation: assign hard reg %d to reg %d\n",
2341 ALLOCNO_HARD_REGNO (a), ALLOCNO_REGNO (a));
2342 }
2343 }
2344}
2345
2346\f
2347
2348/* This page contains code to coalesce memory stack slots used by
2349 spilled allocnos. This results in smaller stack frame, better data
2350 locality, and in smaller code for some architectures like
2351 x86/x86_64 where insn size depends on address displacement value.
2352 On the other hand, it can worsen insn scheduling after the RA but
2353 in practice it is less important than smaller stack frames. */
2354
2355/* Usage cost and order number of coalesced allocno set to which
2356 given pseudo register belongs to. */
2357static int *regno_coalesced_allocno_cost;
2358static int *regno_coalesced_allocno_num;
2359
2360/* Sort pseudos according frequencies of coalesced allocno sets they
2361 belong to (putting most frequently ones first), and according to
2362 coalesced allocno set order numbers. */
2363static int
2364coalesced_pseudo_reg_freq_compare (const void *v1p, const void *v2p)
2365{
2366 const int regno1 = *(const int *) v1p;
2367 const int regno2 = *(const int *) v2p;
2368 int diff;
2369
2370 if ((diff = (regno_coalesced_allocno_cost[regno2]
2371 - regno_coalesced_allocno_cost[regno1])) != 0)
2372 return diff;
2373 if ((diff = (regno_coalesced_allocno_num[regno1]
2374 - regno_coalesced_allocno_num[regno2])) != 0)
2375 return diff;
2376 return regno1 - regno2;
2377}
2378
2379/* Widest width in which each pseudo reg is referred to (via subreg).
2380 It is used for sorting pseudo registers. */
2381static unsigned int *regno_max_ref_width;
2382
2383/* Redefine STACK_GROWS_DOWNWARD in terms of 0 or 1. */
2384#ifdef STACK_GROWS_DOWNWARD
2385# undef STACK_GROWS_DOWNWARD
2386# define STACK_GROWS_DOWNWARD 1
2387#else
2388# define STACK_GROWS_DOWNWARD 0
2389#endif
2390
2391/* Sort pseudos according their slot numbers (putting ones with
2392 smaller numbers first, or last when the frame pointer is not
2393 needed). */
2394static int
2395coalesced_pseudo_reg_slot_compare (const void *v1p, const void *v2p)
2396{
2397 const int regno1 = *(const int *) v1p;
2398 const int regno2 = *(const int *) v2p;
2399 ira_allocno_t a1 = ira_regno_allocno_map[regno1];
2400 ira_allocno_t a2 = ira_regno_allocno_map[regno2];
2401 int diff, slot_num1, slot_num2;
2402 int total_size1, total_size2;
2403
2404 if (a1 == NULL || ALLOCNO_HARD_REGNO (a1) >= 0)
2405 {
2406 if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
2407 return regno1 - regno2;
2408 return 1;
2409 }
2410 else if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
2411 return -1;
2412 slot_num1 = -ALLOCNO_HARD_REGNO (a1);
2413 slot_num2 = -ALLOCNO_HARD_REGNO (a2);
2414 if ((diff = slot_num1 - slot_num2) != 0)
2415 return (frame_pointer_needed
2416 || !FRAME_GROWS_DOWNWARD == STACK_GROWS_DOWNWARD ? diff : -diff);
2417 total_size1 = MAX (PSEUDO_REGNO_BYTES (regno1), regno_max_ref_width[regno1]);
2418 total_size2 = MAX (PSEUDO_REGNO_BYTES (regno2), regno_max_ref_width[regno2]);
2419 if ((diff = total_size2 - total_size1) != 0)
2420 return diff;
2421 return regno1 - regno2;
2422}
2423
2424/* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
2425 for coalesced allocno sets containing allocnos with their regnos
2426 given in array PSEUDO_REGNOS of length N. */
2427static void
2428setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos, int n)
2429{
2430 int i, num, regno, cost;
2431 ira_allocno_t allocno, a;
2432
2433 for (num = i = 0; i < n; i++)
2434 {
2435 regno = pseudo_regnos[i];
2436 allocno = ira_regno_allocno_map[regno];
2437 if (allocno == NULL)
2438 {
2439 regno_coalesced_allocno_cost[regno] = 0;
2440 regno_coalesced_allocno_num[regno] = ++num;
2441 continue;
2442 }
2443 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
2444 continue;
2445 num++;
2446 for (cost = 0, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2447 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2448 {
2449 cost += ALLOCNO_FREQ (a);
2450 if (a == allocno)
2451 break;
2452 }
2453 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2454 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2455 {
2456 regno_coalesced_allocno_num[ALLOCNO_REGNO (a)] = num;
2457 regno_coalesced_allocno_cost[ALLOCNO_REGNO (a)] = cost;
2458 if (a == allocno)
2459 break;
2460 }
2461 }
2462}
2463
2464/* Collect spilled allocnos representing coalesced allocno sets (the
2465 first coalesced allocno). The collected allocnos are returned
2466 through array SPILLED_COALESCED_ALLOCNOS. The function returns the
2467 number of the collected allocnos. The allocnos are given by their
2468 regnos in array PSEUDO_REGNOS of length N. */
2469static int
2470collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n,
2471 ira_allocno_t *spilled_coalesced_allocnos)
2472{
2473 int i, num, regno;
2474 ira_allocno_t allocno;
2475
2476 for (num = i = 0; i < n; i++)
2477 {
2478 regno = pseudo_regnos[i];
2479 allocno = ira_regno_allocno_map[regno];
2480 if (allocno == NULL || ALLOCNO_HARD_REGNO (allocno) >= 0
2481 || ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
2482 continue;
2483 spilled_coalesced_allocnos[num++] = allocno;
2484 }
2485 return num;
2486}
2487
2488/* Array of live ranges of size IRA_ALLOCNOS_NUM. Live range for
2489 given slot contains live ranges of coalesced allocnos assigned to
2490 given slot. */
2491static allocno_live_range_t *slot_coalesced_allocnos_live_ranges;
2492
2493/* Return TRUE if coalesced allocnos represented by ALLOCNO has live
2494 ranges intersected with live ranges of coalesced allocnos assigned
2495 to slot with number N. */
2496static bool
2497slot_coalesced_allocno_live_ranges_intersect_p (ira_allocno_t allocno, int n)
2498{
2499 ira_allocno_t a;
2500
2501 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2502 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2503 {
2504 if (ira_allocno_live_ranges_intersect_p
2505 (slot_coalesced_allocnos_live_ranges[n], ALLOCNO_LIVE_RANGES (a)))
2506 return true;
2507 if (a == allocno)
2508 break;
2509 }
2510 return false;
2511}
2512
2513/* Update live ranges of slot to which coalesced allocnos represented
2514 by ALLOCNO were assigned. */
2515static void
2516setup_slot_coalesced_allocno_live_ranges (ira_allocno_t allocno)
2517{
2518 int n;
2519 ira_allocno_t a;
2520 allocno_live_range_t r;
2521
2522 n = ALLOCNO_TEMP (allocno);
2523 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2524 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2525 {
2526 r = ira_copy_allocno_live_range_list (ALLOCNO_LIVE_RANGES (a));
2527 slot_coalesced_allocnos_live_ranges[n]
2528 = ira_merge_allocno_live_ranges
2529 (slot_coalesced_allocnos_live_ranges[n], r);
2530 if (a == allocno)
2531 break;
2532 }
2533}
2534
2535/* We have coalesced allocnos involving in copies. Coalesce allocnos
2536 further in order to share the same memory stack slot. Allocnos
2537 representing sets of allocnos coalesced before the call are given
2538 in array SPILLED_COALESCED_ALLOCNOS of length NUM. Return TRUE if
2539 some allocnos were coalesced in the function. */
2540static bool
2541coalesce_spill_slots (ira_allocno_t *spilled_coalesced_allocnos, int num)
2542{
2543 int i, j, n, last_coalesced_allocno_num;
2544 ira_allocno_t allocno, a;
2545 bool merged_p = false;
2546 bitmap set_jump_crosses = regstat_get_setjmp_crosses ();
2547
2548 slot_coalesced_allocnos_live_ranges
2549 = (allocno_live_range_t *) ira_allocate (sizeof (allocno_live_range_t)
2550 * ira_allocnos_num);
2551 memset (slot_coalesced_allocnos_live_ranges, 0,
2552 sizeof (allocno_live_range_t) * ira_allocnos_num);
2553 last_coalesced_allocno_num = 0;
2554 /* Coalesce non-conflicting spilled allocnos preferring most
2555 frequently used. */
2556 for (i = 0; i < num; i++)
2557 {
2558 allocno = spilled_coalesced_allocnos[i];
2559 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno
2560 || bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (allocno))
2561 || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
2562 && (ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX
2563 || ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)])))
2564 continue;
2565 for (j = 0; j < i; j++)
2566 {
2567 a = spilled_coalesced_allocnos[j];
2568 n = ALLOCNO_TEMP (a);
2569 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a
2570 && ! bitmap_bit_p (set_jump_crosses, ALLOCNO_REGNO (a))
2571 && (ALLOCNO_REGNO (a) >= ira_reg_equiv_len
2572 || (! ira_reg_equiv_invariant_p[ALLOCNO_REGNO (a)]
2573 && ira_reg_equiv_const[ALLOCNO_REGNO (a)] == NULL_RTX))
2574 && ! slot_coalesced_allocno_live_ranges_intersect_p (allocno, n))
2575 break;
2576 }
2577 if (j >= i)
2578 {
2579 /* No coalescing: set up number for coalesced allocnos
2580 represented by ALLOCNO. */
2581 ALLOCNO_TEMP (allocno) = last_coalesced_allocno_num++;
2582 setup_slot_coalesced_allocno_live_ranges (allocno);
2583 }
2584 else
2585 {
2586 allocno_coalesced_p = true;
2587 merged_p = true;
2588 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2589 fprintf (ira_dump_file,
2590 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
2591 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno),
2592 ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2593 ALLOCNO_TEMP (allocno) = ALLOCNO_TEMP (a);
2594 setup_slot_coalesced_allocno_live_ranges (allocno);
2595 merge_allocnos (a, allocno);
2596 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a);
2597 }
2598 }
2599 for (i = 0; i < ira_allocnos_num; i++)
2600 ira_finish_allocno_live_range_list
2601 (slot_coalesced_allocnos_live_ranges[i]);
2602 ira_free (slot_coalesced_allocnos_live_ranges);
2603 return merged_p;
2604}
2605
2606/* Sort pseudo-register numbers in array PSEUDO_REGNOS of length N for
2607 subsequent assigning stack slots to them in the reload pass. To do
2608 this we coalesce spilled allocnos first to decrease the number of
2609 memory-memory move insns. This function is called by the
2610 reload. */
2611void
2612ira_sort_regnos_for_alter_reg (int *pseudo_regnos, int n,
2613 unsigned int *reg_max_ref_width)
2614{
2615 int max_regno = max_reg_num ();
2616 int i, regno, num, slot_num;
2617 ira_allocno_t allocno, a;
2618 ira_allocno_iterator ai;
2619 ira_allocno_t *spilled_coalesced_allocnos;
2620
2621 processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
2622 /* Set up allocnos can be coalesced. */
2623 coloring_allocno_bitmap = ira_allocate_bitmap ();
2624 for (i = 0; i < n; i++)
2625 {
2626 regno = pseudo_regnos[i];
2627 allocno = ira_regno_allocno_map[regno];
2628 if (allocno != NULL)
2629 bitmap_set_bit (coloring_allocno_bitmap,
2630 ALLOCNO_NUM (allocno));
2631 }
2632 allocno_coalesced_p = false;
2633 coalesce_allocnos (true);
2634 ira_free_bitmap (coloring_allocno_bitmap);
2635 regno_coalesced_allocno_cost
2636 = (int *) ira_allocate (max_regno * sizeof (int));
2637 regno_coalesced_allocno_num
2638 = (int *) ira_allocate (max_regno * sizeof (int));
2639 memset (regno_coalesced_allocno_num, 0, max_regno * sizeof (int));
2640 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
2641 /* Sort regnos according frequencies of the corresponding coalesced
2642 allocno sets. */
2643 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_freq_compare);
2644 spilled_coalesced_allocnos
2645 = (ira_allocno_t *) ira_allocate (ira_allocnos_num
2646 * sizeof (ira_allocno_t));
2647 /* Collect allocnos representing the spilled coalesced allocno
2648 sets. */
2649 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
2650 spilled_coalesced_allocnos);
2651 if (flag_ira_share_spill_slots
2652 && coalesce_spill_slots (spilled_coalesced_allocnos, num))
2653 {
2654 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
2655 qsort (pseudo_regnos, n, sizeof (int),
2656 coalesced_pseudo_reg_freq_compare);
2657 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
2658 spilled_coalesced_allocnos);
2659 }
2660 ira_free_bitmap (processed_coalesced_allocno_bitmap);
2661 allocno_coalesced_p = false;
2662 /* Assign stack slot numbers to spilled allocno sets, use smaller
2663 numbers for most frequently used coalesced allocnos. -1 is
2664 reserved for dynamic search of stack slots for pseudos spilled by
2665 the reload. */
2666 slot_num = 1;
2667 for (i = 0; i < num; i++)
2668 {
2669 allocno = spilled_coalesced_allocnos[i];
2670 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno
2671 || ALLOCNO_HARD_REGNO (allocno) >= 0
2672 || (ALLOCNO_REGNO (allocno) < ira_reg_equiv_len
2673 && (ira_reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX
2674 || ira_reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)])))
2675 continue;
2676 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2677 fprintf (ira_dump_file, " Slot %d (freq,size):", slot_num);
2678 slot_num++;
2679 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2680 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2681 {
2682 ira_assert (ALLOCNO_HARD_REGNO (a) < 0);
2683 ALLOCNO_HARD_REGNO (a) = -slot_num;
2684 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2685 fprintf (ira_dump_file, " a%dr%d(%d,%d)",
2686 ALLOCNO_NUM (a), ALLOCNO_REGNO (a), ALLOCNO_FREQ (a),
2687 MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a)),
2688 reg_max_ref_width[ALLOCNO_REGNO (a)]));
2689
2690 if (a == allocno)
2691 break;
2692 }
2693 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2694 fprintf (ira_dump_file, "\n");
2695 }
2696 ira_spilled_reg_stack_slots_num = slot_num - 1;
2697 ira_free (spilled_coalesced_allocnos);
2698 /* Sort regnos according the slot numbers. */
2699 regno_max_ref_width = reg_max_ref_width;
2700 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_slot_compare);
2701 /* Uncoalesce allocnos which is necessary for (re)assigning during
2702 the reload pass. */
2703 FOR_EACH_ALLOCNO (a, ai)
2704 {
2705 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
2706 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
2707 }
2708 ira_free (regno_coalesced_allocno_num);
2709 ira_free (regno_coalesced_allocno_cost);
2710}
2711
2712\f
2713
2714/* This page contains code used by the reload pass to improve the
2715 final code. */
2716
2717/* The function is called from reload to mark changes in the
2718 allocation of REGNO made by the reload. Remember that reg_renumber
2719 reflects the change result. */
2720void
2721ira_mark_allocation_change (int regno)
2722{
2723 ira_allocno_t a = ira_regno_allocno_map[regno];
2724 int old_hard_regno, hard_regno, cost;
2725 enum reg_class cover_class = ALLOCNO_COVER_CLASS (a);
2726
2727 ira_assert (a != NULL);
2728 hard_regno = reg_renumber[regno];
2729 if ((old_hard_regno = ALLOCNO_HARD_REGNO (a)) == hard_regno)
2730 return;
2731 if (old_hard_regno < 0)
2732 cost = -ALLOCNO_MEMORY_COST (a);
2733 else
2734 {
2735 ira_assert (ira_class_hard_reg_index[cover_class][old_hard_regno] >= 0);
2736 cost = -(ALLOCNO_HARD_REG_COSTS (a) == NULL
2737 ? ALLOCNO_COVER_CLASS_COST (a)
2738 : ALLOCNO_HARD_REG_COSTS (a)
2739 [ira_class_hard_reg_index[cover_class][old_hard_regno]]);
2740 update_copy_costs (a, false);
2741 }
2742 ira_overall_cost -= cost;
2743 ALLOCNO_HARD_REGNO (a) = hard_regno;
2744 if (hard_regno < 0)
2745 {
2746 ALLOCNO_HARD_REGNO (a) = -1;
2747 cost += ALLOCNO_MEMORY_COST (a);
2748 }
2749 else if (ira_class_hard_reg_index[cover_class][hard_regno] >= 0)
2750 {
2751 cost += (ALLOCNO_HARD_REG_COSTS (a) == NULL
2752 ? ALLOCNO_COVER_CLASS_COST (a)
2753 : ALLOCNO_HARD_REG_COSTS (a)
2754 [ira_class_hard_reg_index[cover_class][hard_regno]]);
2755 update_copy_costs (a, true);
2756 }
2757 else
2758 /* Reload changed class of the allocno. */
2759 cost = 0;
2760 ira_overall_cost += cost;
2761}
2762
2763/* This function is called when reload deletes memory-memory move. In
2764 this case we marks that the allocation of the corresponding
2765 allocnos should be not changed in future. Otherwise we risk to get
2766 a wrong code. */
2767void
2768ira_mark_memory_move_deletion (int dst_regno, int src_regno)
2769{
2770 ira_allocno_t dst = ira_regno_allocno_map[dst_regno];
2771 ira_allocno_t src = ira_regno_allocno_map[src_regno];
2772
2773 ira_assert (dst != NULL && src != NULL
2774 && ALLOCNO_HARD_REGNO (dst) < 0
2775 && ALLOCNO_HARD_REGNO (src) < 0);
2776 ALLOCNO_DONT_REASSIGN_P (dst) = true;
2777 ALLOCNO_DONT_REASSIGN_P (src) = true;
2778}
2779
2780/* Try to assign a hard register (except for FORBIDDEN_REGS) to
2781 allocno A and return TRUE in the case of success. */
2782static bool
2783allocno_reload_assign (ira_allocno_t a, HARD_REG_SET forbidden_regs)
2784{
2785 int hard_regno;
2786 enum reg_class cover_class;
2787 int regno = ALLOCNO_REGNO (a);
2788
2789 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), forbidden_regs);
2790 if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
2791 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), call_used_reg_set);
2792 ALLOCNO_ASSIGNED_P (a) = false;
2793 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2794 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2795 cover_class = ALLOCNO_COVER_CLASS (a);
2796 update_curr_costs (a);
2797 assign_hard_reg (a, true);
2798 hard_regno = ALLOCNO_HARD_REGNO (a);
2799 reg_renumber[regno] = hard_regno;
2800 if (hard_regno < 0)
2801 ALLOCNO_HARD_REGNO (a) = -1;
2802 else
2803 {
2804 ira_assert (ira_class_hard_reg_index[cover_class][hard_regno] >= 0);
2805 ira_overall_cost -= (ALLOCNO_MEMORY_COST (a)
2806 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
2807 ? ALLOCNO_COVER_CLASS_COST (a)
2808 : ALLOCNO_HARD_REG_COSTS (a)
2809 [ira_class_hard_reg_index
2810 [cover_class][hard_regno]]));
2811 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
2812 && ! ira_hard_reg_not_in_set_p (hard_regno, ALLOCNO_MODE (a),
2813 call_used_reg_set))
2814 {
2815 ira_assert (flag_caller_saves);
2816 caller_save_needed = 1;
2817 }
2818 }
2819
2820 /* If we found a hard register, modify the RTL for the pseudo
2821 register to show the hard register, and mark the pseudo register
2822 live. */
2823 if (reg_renumber[regno] >= 0)
2824 {
2825 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2826 fprintf (ira_dump_file, ": reassign to %d\n", reg_renumber[regno]);
2827 SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
2828 mark_home_live (regno);
2829 }
2830 else if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2831 fprintf (ira_dump_file, "\n");
2832
2833 return reg_renumber[regno] >= 0;
2834}
2835
2836/* Sort pseudos according their usage frequencies (putting most
2837 frequently ones first). */
2838static int
2839pseudo_reg_compare (const void *v1p, const void *v2p)
2840{
2841 int regno1 = *(const int *) v1p;
2842 int regno2 = *(const int *) v2p;
2843 int diff;
2844
2845 if ((diff = REG_FREQ (regno2) - REG_FREQ (regno1)) != 0)
2846 return diff;
2847 return regno1 - regno2;
2848}
2849
2850/* Try to allocate hard registers to SPILLED_PSEUDO_REGS (there are
2851 NUM of them) or spilled pseudos conflicting with pseudos in
2852 SPILLED_PSEUDO_REGS. Return TRUE and update SPILLED, if the
2853 allocation has been changed. The function doesn't use
2854 BAD_SPILL_REGS and hard registers in PSEUDO_FORBIDDEN_REGS and
2855 PSEUDO_PREVIOUS_REGS for the corresponding pseudos. The function
2856 is called by the reload pass at the end of each reload
2857 iteration. */
2858bool
2859ira_reassign_pseudos (int *spilled_pseudo_regs, int num,
2860 HARD_REG_SET bad_spill_regs,
2861 HARD_REG_SET *pseudo_forbidden_regs,
2862 HARD_REG_SET *pseudo_previous_regs, bitmap spilled)
2863{
2864 int i, m, n, regno;
2865 bool changed_p;
2866 ira_allocno_t a, conflict_a;
2867 HARD_REG_SET forbidden_regs;
2868 ira_allocno_conflict_iterator aci;
2869
2870 if (num > 1)
2871 qsort (spilled_pseudo_regs, num, sizeof (int), pseudo_reg_compare);
2872 changed_p = false;
2873 /* Try to assign hard registers to pseudos from
2874 SPILLED_PSEUDO_REGS. */
2875 for (m = i = 0; i < num; i++)
2876 {
2877 regno = spilled_pseudo_regs[i];
2878 COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
2879 IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]);
2880 IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]);
2881 gcc_assert (reg_renumber[regno] < 0);
2882 a = ira_regno_allocno_map[regno];
2883 ira_mark_allocation_change (regno);
2884 ira_assert (reg_renumber[regno] < 0);
2885 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2886 fprintf (ira_dump_file,
2887 " Spill %d(a%d), cost=%d", regno, ALLOCNO_NUM (a),
2888 ALLOCNO_MEMORY_COST (a)
2889 - ALLOCNO_COVER_CLASS_COST (a));
2890 allocno_reload_assign (a, forbidden_regs);
2891 if (reg_renumber[regno] >= 0)
2892 {
2893 CLEAR_REGNO_REG_SET (spilled, regno);
2894 changed_p = true;
2895 }
2896 else
2897 spilled_pseudo_regs[m++] = regno;
2898 }
2899 if (m == 0)
2900 return changed_p;
2901 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2902 {
2903 fprintf (ira_dump_file, " Spilled regs");
2904 for (i = 0; i < m; i++)
2905 fprintf (ira_dump_file, " %d", spilled_pseudo_regs[i]);
2906 fprintf (ira_dump_file, "\n");
2907 }
2908 /* Try to assign hard registers to pseudos conflicting with ones
2909 from SPILLED_PSEUDO_REGS. */
2910 for (i = n = 0; i < m; i++)
2911 {
2912 regno = spilled_pseudo_regs[i];
2913 a = ira_regno_allocno_map[regno];
2914 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
2915 if (ALLOCNO_HARD_REGNO (conflict_a) < 0
2916 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a)
2917 && ! bitmap_bit_p (consideration_allocno_bitmap,
2918 ALLOCNO_NUM (conflict_a)))
2919 {
2920 sorted_allocnos[n++] = conflict_a;
2921 bitmap_set_bit (consideration_allocno_bitmap,
2922 ALLOCNO_NUM (conflict_a));
2923 }
2924 }
2925 if (n != 0)
2926 {
2927 setup_allocno_priorities (sorted_allocnos, n);
2928 qsort (sorted_allocnos, n, sizeof (ira_allocno_t),
2929 allocno_priority_compare_func);
2930 for (i = 0; i < n; i++)
2931 {
2932 a = sorted_allocnos[i];
2933 regno = ALLOCNO_REGNO (a);
2934 COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
2935 IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]);
2936 IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]);
2937 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2938 fprintf (ira_dump_file,
2939 " Try assign %d(a%d), cost=%d",
2940 regno, ALLOCNO_NUM (a),
2941 ALLOCNO_MEMORY_COST (a)
2942 - ALLOCNO_COVER_CLASS_COST (a));
2943 if (allocno_reload_assign (a, forbidden_regs))
2944 {
2945 changed_p = true;
2946 bitmap_clear_bit (spilled, regno);
2947 }
2948 }
2949 }
2950 return changed_p;
2951}
2952
2953/* The function is called by reload and returns already allocated
2954 stack slot (if any) for REGNO with given INHERENT_SIZE and
2955 TOTAL_SIZE. In the case of failure to find a slot which can be
2956 used for REGNO, the function returns NULL. */
2957rtx
2958ira_reuse_stack_slot (int regno, unsigned int inherent_size,
2959 unsigned int total_size)
2960{
2961 unsigned int i;
2962 int slot_num, best_slot_num;
2963 int cost, best_cost;
2964 ira_copy_t cp, next_cp;
2965 ira_allocno_t another_allocno, allocno = ira_regno_allocno_map[regno];
2966 rtx x;
2967 bitmap_iterator bi;
2968 struct ira_spilled_reg_stack_slot *slot = NULL;
2969
2970 ira_assert (inherent_size == PSEUDO_REGNO_BYTES (regno)
2971 && inherent_size <= total_size
2972 && ALLOCNO_HARD_REGNO (allocno) < 0);
2973 if (! flag_ira_share_spill_slots)
2974 return NULL_RTX;
2975 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
2976 if (slot_num != -1)
2977 {
2978 slot = &ira_spilled_reg_stack_slots[slot_num];
2979 x = slot->mem;
2980 }
2981 else
2982 {
2983 best_cost = best_slot_num = -1;
2984 x = NULL_RTX;
2985 /* It means that the pseudo was spilled in the reload pass, try
2986 to reuse a slot. */
2987 for (slot_num = 0;
2988 slot_num < ira_spilled_reg_stack_slots_num;
2989 slot_num++)
2990 {
2991 slot = &ira_spilled_reg_stack_slots[slot_num];
2992 if (slot->mem == NULL_RTX)
2993 continue;
2994 if (slot->width < total_size
2995 || GET_MODE_SIZE (GET_MODE (slot->mem)) < inherent_size)
2996 continue;
2997
2998 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
2999 FIRST_PSEUDO_REGISTER, i, bi)
3000 {
3001 another_allocno = ira_regno_allocno_map[i];
3002 if (allocnos_have_intersected_live_ranges_p (allocno,
3003 another_allocno))
3004 goto cont;
3005 }
3006 for (cost = 0, cp = ALLOCNO_COPIES (allocno);
3007 cp != NULL;
3008 cp = next_cp)
3009 {
3010 if (cp->first == allocno)
3011 {
3012 next_cp = cp->next_first_allocno_copy;
3013 another_allocno = cp->second;
3014 }
3015 else if (cp->second == allocno)
3016 {
3017 next_cp = cp->next_second_allocno_copy;
3018 another_allocno = cp->first;
3019 }
3020 else
3021 gcc_unreachable ();
3022 if (cp->insn == NULL_RTX)
3023 continue;
3024 if (bitmap_bit_p (&slot->spilled_regs,
3025 ALLOCNO_REGNO (another_allocno)))
3026 cost += cp->freq;
3027 }
3028 if (cost > best_cost)
3029 {
3030 best_cost = cost;
3031 best_slot_num = slot_num;
3032 }
3033 cont:
3034 ;
3035 }
3036 if (best_cost >= 0)
3037 {
3038 slot_num = best_slot_num;
3039 slot = &ira_spilled_reg_stack_slots[slot_num];
3040 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
3041 x = slot->mem;
3042 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
3043 }
3044 }
3045 if (x != NULL_RTX)
3046 {
3047 ira_assert (slot->width >= total_size);
3048#ifdef ENABLE_IRA_CHECKING
3049 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
3050 FIRST_PSEUDO_REGISTER, i, bi)
3051 {
3052 ira_assert (! pseudos_have_intersected_live_ranges_p (regno, i));
3053 }
3054#endif
3055 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
3056 if (internal_flag_ira_verbose > 3 && ira_dump_file)
3057 {
3058 fprintf (ira_dump_file, " Assigning %d(freq=%d) slot %d of",
3059 regno, REG_FREQ (regno), slot_num);
3060 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
3061 FIRST_PSEUDO_REGISTER, i, bi)
3062 {
3063 if ((unsigned) regno != i)
3064 fprintf (ira_dump_file, " %d", i);
3065 }
3066 fprintf (ira_dump_file, "\n");
3067 }
3068 }
3069 return x;
3070}
3071
3072/* This is called by reload every time a new stack slot X with
3073 TOTAL_SIZE was allocated for REGNO. We store this info for
3074 subsequent ira_reuse_stack_slot calls. */
3075void
3076ira_mark_new_stack_slot (rtx x, int regno, unsigned int total_size)
3077{
3078 struct ira_spilled_reg_stack_slot *slot;
3079 int slot_num;
3080 ira_allocno_t allocno;
3081
3082 ira_assert (PSEUDO_REGNO_BYTES (regno) <= total_size);
3083 allocno = ira_regno_allocno_map[regno];
3084 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
3085 if (slot_num == -1)
3086 {
3087 slot_num = ira_spilled_reg_stack_slots_num++;
3088 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
3089 }
3090 slot = &ira_spilled_reg_stack_slots[slot_num];
3091 INIT_REG_SET (&slot->spilled_regs);
3092 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
3093 slot->mem = x;
3094 slot->width = total_size;
3095 if (internal_flag_ira_verbose > 3 && ira_dump_file)
3096 fprintf (ira_dump_file, " Assigning %d(freq=%d) a new slot %d\n",
3097 regno, REG_FREQ (regno), slot_num);
3098}
3099
3100
3101/* Return spill cost for pseudo-registers whose numbers are in array
3102 REGNOS (with a negative number as an end marker) for reload with
3103 given IN and OUT for INSN. Return also number points (through
3104 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
3105 the register pressure is high, number of references of the
3106 pseudo-registers (through NREFS), number of callee-clobbered
3107 hard-registers occupied by the pseudo-registers (through
3108 CALL_USED_COUNT), and the first hard regno occupied by the
3109 pseudo-registers (through FIRST_HARD_REGNO). */
3110static int
3111calculate_spill_cost (int *regnos, rtx in, rtx out, rtx insn,
3112 int *excess_pressure_live_length,
3113 int *nrefs, int *call_used_count, int *first_hard_regno)
3114{
3115 int i, cost, regno, hard_regno, j, count, saved_cost, nregs;
3116 bool in_p, out_p;
3117 int length;
3118 ira_allocno_t a;
3119
3120 *nrefs = 0;
3121 for (length = count = cost = i = 0;; i++)
3122 {
3123 regno = regnos[i];
3124 if (regno < 0)
3125 break;
3126 *nrefs += REG_N_REFS (regno);
3127 hard_regno = reg_renumber[regno];
3128 ira_assert (hard_regno >= 0);
3129 a = ira_regno_allocno_map[regno];
3130 length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
3131 cost += ALLOCNO_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a);
3132 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
3133 for (j = 0; j < nregs; j++)
3134 if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j))
3135 break;
3136 if (j == nregs)
3137 count++;
3138 in_p = in && REG_P (in) && (int) REGNO (in) == hard_regno;
3139 out_p = out && REG_P (out) && (int) REGNO (out) == hard_regno;
3140 if ((in_p || out_p)
3141 && find_regno_note (insn, REG_DEAD, hard_regno) != NULL_RTX)
3142 {
3143 saved_cost = 0;
3144 if (in_p)
3145 saved_cost += ira_memory_move_cost
3146 [ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)][1];
3147 if (out_p)
3148 saved_cost
3149 += ira_memory_move_cost
3150 [ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)][0];
3151 cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)) * saved_cost;
3152 }
3153 }
3154 *excess_pressure_live_length = length;
3155 *call_used_count = count;
3156 hard_regno = -1;
3157 if (regnos[0] >= 0)
3158 {
3159 hard_regno = reg_renumber[regnos[0]];
3160 }
3161 *first_hard_regno = hard_regno;
3162 return cost;
3163}
3164
3165/* Return TRUE if spilling pseudo-registers whose numbers are in array
3166 REGNOS is better than spilling pseudo-registers with numbers in
3167 OTHER_REGNOS for reload with given IN and OUT for INSN. The
3168 function used by the reload pass to make better register spilling
3169 decisions. */
3170bool
3171ira_better_spill_reload_regno_p (int *regnos, int *other_regnos,
3172 rtx in, rtx out, rtx insn)
3173{
3174 int cost, other_cost;
3175 int length, other_length;
3176 int nrefs, other_nrefs;
3177 int call_used_count, other_call_used_count;
3178 int hard_regno, other_hard_regno;
3179
3180 cost = calculate_spill_cost (regnos, in, out, insn,
3181 &length, &nrefs, &call_used_count, &hard_regno);
3182 other_cost = calculate_spill_cost (other_regnos, in, out, insn,
3183 &other_length, &other_nrefs,
3184 &other_call_used_count,
3185 &other_hard_regno);
3186 if (nrefs == 0 && other_nrefs != 0)
3187 return true;
3188 if (nrefs != 0 && other_nrefs == 0)
3189 return false;
3190 if (cost != other_cost)
3191 return cost < other_cost;
3192 if (length != other_length)
3193 return length > other_length;
3194#ifdef REG_ALLOC_ORDER
3195 if (hard_regno >= 0 && other_hard_regno >= 0)
3196 return (inv_reg_alloc_order[hard_regno]
3197 < inv_reg_alloc_order[other_hard_regno]);
3198#else
3199 if (call_used_count != other_call_used_count)
3200 return call_used_count > other_call_used_count;
3201#endif
3202 return false;
3203}
3204
3205\f
3206
3207/* Allocate and initialize data necessary for assign_hard_reg. */
3208void
3209ira_initiate_assign (void)
3210{
3211 sorted_allocnos
3212 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
3213 * ira_allocnos_num);
3214 consideration_allocno_bitmap = ira_allocate_bitmap ();
3215 initiate_cost_update ();
3216 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
3217}
3218
3219/* Deallocate data used by assign_hard_reg. */
3220void
3221ira_finish_assign (void)
3222{
3223 ira_free (sorted_allocnos);
3224 ira_free_bitmap (consideration_allocno_bitmap);
3225 finish_cost_update ();
3226 ira_free (allocno_priorities);
3227}
3228
3229\f
3230
3231/* Entry function doing color-based register allocation. */
3232static void
3233color (void)
3234{
3235 allocno_stack_vec = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
3236 removed_splay_allocno_vec
3237 = VEC_alloc (ira_allocno_t, heap, ira_allocnos_num);
3238 memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p));
3239 ira_initiate_assign ();
3240 do_coloring ();
3241 ira_finish_assign ();
3242 VEC_free (ira_allocno_t, heap, removed_splay_allocno_vec);
3243 VEC_free (ira_allocno_t, heap, allocno_stack_vec);
3244 move_spill_restore ();
3245}
3246
3247\f
3248
3249/* This page contains a simple register allocator without usage of
3250 allocno conflicts. This is used for fast allocation for -O0. */
3251
3252/* Do register allocation by not using allocno conflicts. It uses
3253 only allocno live ranges. The algorithm is close to Chow's
3254 priority coloring. */
3255static void
3256fast_allocation (void)
3257{
3258 int i, j, k, num, class_size, hard_regno;
3259#ifdef STACK_REGS
3260 bool no_stack_reg_p;
3261#endif
3262 enum reg_class cover_class;
3263 enum machine_mode mode;
3264 ira_allocno_t a;
3265 ira_allocno_iterator ai;
3266 allocno_live_range_t r;
3267 HARD_REG_SET conflict_hard_regs, *used_hard_regs;
3268
3269 sorted_allocnos = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
3270 * ira_allocnos_num);
3271 num = 0;
3272 FOR_EACH_ALLOCNO (a, ai)
3273 sorted_allocnos[num++] = a;
3274 allocno_priorities = (int *) ira_allocate (sizeof (int) * ira_allocnos_num);
3275 setup_allocno_priorities (sorted_allocnos, num);
3276 used_hard_regs = (HARD_REG_SET *) ira_allocate (sizeof (HARD_REG_SET)
3277 * ira_max_point);
3278 for (i = 0; i < ira_max_point; i++)
3279 CLEAR_HARD_REG_SET (used_hard_regs[i]);
3280 qsort (sorted_allocnos, num, sizeof (ira_allocno_t),
3281 allocno_priority_compare_func);
3282 for (i = 0; i < num; i++)
3283 {
3284 a = sorted_allocnos[i];
3285 COPY_HARD_REG_SET (conflict_hard_regs, ALLOCNO_CONFLICT_HARD_REGS (a));
3286 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
3287 for (j = r->start; j <= r->finish; j++)
3288 IOR_HARD_REG_SET (conflict_hard_regs, used_hard_regs[j]);
3289 cover_class = ALLOCNO_COVER_CLASS (a);
3290 ALLOCNO_ASSIGNED_P (a) = true;
3291 ALLOCNO_HARD_REGNO (a) = -1;
3292 if (hard_reg_set_subset_p (reg_class_contents[cover_class],
3293 conflict_hard_regs))
3294 continue;
3295 mode = ALLOCNO_MODE (a);
3296#ifdef STACK_REGS
3297 no_stack_reg_p = ALLOCNO_NO_STACK_REG_P (a);
3298#endif
3299 class_size = ira_class_hard_regs_num[cover_class];
3300 for (j = 0; j < class_size; j++)
3301 {
3302 hard_regno = ira_class_hard_regs[cover_class][j];
3303#ifdef STACK_REGS
3304 if (no_stack_reg_p && FIRST_STACK_REG <= hard_regno
3305 && hard_regno <= LAST_STACK_REG)
3306 continue;
3307#endif
3308 if (!ira_hard_reg_not_in_set_p (hard_regno, mode, conflict_hard_regs)
3309 || (TEST_HARD_REG_BIT
3310 (prohibited_class_mode_regs[cover_class][mode], hard_regno)))
3311 continue;
3312 ALLOCNO_HARD_REGNO (a) = hard_regno;
3313 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
3314 for (k = r->start; k <= r->finish; k++)
3315 IOR_HARD_REG_SET (used_hard_regs[k],
3316 ira_reg_mode_hard_regset[hard_regno][mode]);
3317 break;
3318 }
3319 }
3320 ira_free (sorted_allocnos);
3321 ira_free (used_hard_regs);
3322 ira_free (allocno_priorities);
3323 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
3324 ira_print_disposition (ira_dump_file);
3325}
3326
3327\f
3328
3329/* Entry function doing coloring. */
3330void
3331ira_color (void)
3332{
3333 ira_allocno_t a;
3334 ira_allocno_iterator ai;
3335
3336 /* Setup updated costs. */
3337 FOR_EACH_ALLOCNO (a, ai)
3338 {
3339 ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
3340 ALLOCNO_UPDATED_COVER_CLASS_COST (a) = ALLOCNO_COVER_CLASS_COST (a);
3341 }
3342 if (ira_conflicts_p)
3343 color ();
3344 else
3345 fast_allocation ();
3346}