?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
2008-04-08 Vladimir Makarov <vmakarov@redhat.com>
[official-gcc.git] / gcc / ira-color.c
blobbd54e87ae8e03c92d0982a55bc4726192ce1f002
1 /* IRA allocation based on graph coloring.
2 Copyright (C) 2006, 2007, 2008
3 Free Software Foundation, Inc.
4 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
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 "varray.h"
30 #include "regs.h"
31 #include "flags.h"
32 #include "sbitmap.h"
33 #include "bitmap.h"
34 #include "hard-reg-set.h"
35 #include "basic-block.h"
36 #include "expr.h"
37 #include "toplev.h"
38 #include "reload.h"
39 #include "params.h"
40 #include "df.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 static void initiate_cost_update (void);
48 static void finish_cost_update (void);
49 static void update_copy_costs_1 (allocno_t, int, int, int);
50 static void update_copy_costs (allocno_t, int);
51 static int allocno_cost_compare_func (const void *, const void *);
52 static void print_coalesced_allocno (allocno_t);
53 static int assign_hard_reg (allocno_t, int);
54
55 static void add_allocno_to_bucket (allocno_t, allocno_t *);
56 static void get_coalesced_allocnos_attributes (allocno_t, int *, int *);
57 static int bucket_allocno_compare_func (const void *, const void *);
58 static void sort_bucket (allocno_t *);
59 static void add_allocno_to_ordered_bucket (allocno_t, allocno_t *);
60 static void delete_allocno_from_bucket (allocno_t, allocno_t *);
61 static void push_allocno_to_stack (allocno_t);
62 static void remove_allocno_from_bucket_and_push (allocno_t, int);
63 static void push_only_colorable (void);
64 static void push_allocno_to_spill (allocno_t);
65 static int calculate_allocno_spill_cost (allocno_t);
66 static void push_allocnos_to_stack (void);
67 static void pop_allocnos_from_stack (void);
68 static void setup_allocno_available_regs_num (allocno_t);
69 static void setup_allocno_left_conflicts_num (allocno_t);
70 static void put_allocno_into_bucket (allocno_t);
71 static int copy_freq_compare_func (const void *, const void *);
72 static void merge_allocnos (allocno_t, allocno_t);
73 static int coalesced_allocno_conflict_p (allocno_t, allocno_t, int);
74 static void coalesce_allocnos (int);
75 static void color_allocnos (void);
76
77 static void print_loop_title (loop_tree_node_t);
78 static void color_pass (loop_tree_node_t);
79 static void do_coloring (void);
80
81 static void move_spill_restore (void);
82
83 static void update_curr_costs (allocno_t);
84 static void start_allocno_priorities (allocno_t *, int);
85 static int allocno_priority_compare_func (const void *, const void *);
86
87 static int coalesced_pseudo_reg_freq_compare (const void *, const void *);
88 static int coalesced_pseudo_reg_slot_compare (const void *, const void *);
89 static void setup_coalesced_allocno_costs_and_nums (int *, int);
90 static int collect_spilled_coalesced_allocnos (int *, int, allocno_t *);
91 static int coalesce_spill_slots (allocno_t *, int);
92
93 static int allocno_reload_assign (allocno_t, HARD_REG_SET);
94 static int pseudo_reg_compare (const void *, const void *);
95
96 static int calculate_spill_cost (int *, rtx, rtx, rtx,
97 int *, int *, int *, int*);
98
99 /* Bitmap of allocnos which should be colored. */
100 static bitmap coloring_allocno_bitmap;
101
102 /* Bitmap of allocnos which should be taken into account during
103 coloring. In general case it contains allocnos from
104 coloring_allocno_bitmap plus other already colored conflicting
105 allocnos. */
106 static bitmap consideration_allocno_bitmap;
107
108 /* TRUE if we coalesced some allocnos. In other words, if we got
109 loops formed by members first_coalesced_allocno and
110 next_coalesced_allocno containing more one allocno. */
111 static int allocno_coalesced_p;
112
113 /* Bitmap used to prevent a repeated allocno processing because of
114 coalescing. */
115 static bitmap processed_coalesced_allocno_bitmap;
116
117 /* All allocnos sorted according their priorities. */
118 static allocno_t *sorted_allocnos;
119
120 /* Array used to sort allocnos to choose an allocno for spilling. */
121 static allocno_t *sorted_allocnos_for_spilling;
122
123 /* Varray representing the stack of allocnos used during coloring. */
124 static varray_type allocno_stack_varray;
125
126 \f
127
128 /* This page contains functions used to choose hard registers for
129 allocnos. */
130
131 /* Array whose element value is TRUE if the corresponding hard
132 register was already allocated for an allocno. */
133 static int allocated_hardreg_p[FIRST_PSEUDO_REGISTER];
134
135 /* Array used to check already processed allocnos during the current
136 update_copy_costs call. */
137 static int *allocno_update_cost_check;
138
139 /* The current value of update_copy_cost call count. */
140 static int update_cost_check;
141
142 /* Allocate and initialize data necessary for function
143 update_copy_costs. */
144 static void
145 initiate_cost_update (void)
146 {
147 allocno_update_cost_check = ira_allocate (allocnos_num * sizeof (int));
148 memset (allocno_update_cost_check, 0, allocnos_num * sizeof (int));
149 update_cost_check = 0;
150 }
151
152 /* Deallocate data used by function update_copy_costs. */
153 static void
154 finish_cost_update (void)
155 {
156 ira_free (allocno_update_cost_check);
157 }
158
159 /* This recursive function updates costs (decrease if DECR_P) of the
160 unassigned allocnos connected by copies with ALLOCNO. This update
161 increases chances to remove some copies. Copy cost is proportional
162 the copy frequency divided by DIVISOR. */
163 static void
164 update_copy_costs_1 (allocno_t allocno, int hard_regno,
165 int decr_p, int divisor)
166 {
167 int i, cost, update_cost;
168 enum machine_mode mode;
169 enum reg_class class, cover_class;
170 allocno_t another_allocno;
171 copy_t cp, next_cp;
172
173 cover_class = ALLOCNO_COVER_CLASS (allocno);
174 if (cover_class == NO_REGS)
175 return;
176 if (allocno_update_cost_check[ALLOCNO_NUM (allocno)] == update_cost_check)
177 return;
178 allocno_update_cost_check[ALLOCNO_NUM (allocno)] = update_cost_check;
179 ira_assert (hard_regno >= 0);
180 i = class_hard_reg_index[cover_class][hard_regno];
181 ira_assert (i >= 0);
182 class = REGNO_REG_CLASS (hard_regno);
183 mode = ALLOCNO_MODE (allocno);
184 for (cp = ALLOCNO_COPIES (allocno); cp != NULL; cp = next_cp)
185 {
186 if (cp->first == allocno)
187 {
188 next_cp = cp->next_first_allocno_copy;
189 another_allocno = cp->second;
190 }
191 else if (cp->second == allocno)
192 {
193 next_cp = cp->next_second_allocno_copy;
194 another_allocno = cp->first;
195 }
196 else
197 gcc_unreachable ();
198 if (cover_class
199 != ALLOCNO_COVER_CLASS (another_allocno)
200 || ALLOCNO_ASSIGNED_P (another_allocno))
201 continue;
202 cost = (cp->second == allocno
203 ? register_move_cost[mode][class]
204 [ALLOCNO_COVER_CLASS (another_allocno)]
205 : register_move_cost[mode]
206 [ALLOCNO_COVER_CLASS (another_allocno)][class]);
207 if (decr_p)
208 cost = -cost;
209 allocate_and_set_or_copy_costs
210 (&ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno), cover_class,
211 ALLOCNO_COVER_CLASS_COST (another_allocno),
212 ALLOCNO_HARD_REG_COSTS (another_allocno));
213 allocate_and_set_or_copy_costs
214 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
215 cover_class, 0,
216 ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
217 update_cost = cp->freq * cost / divisor;
218 ALLOCNO_UPDATED_HARD_REG_COSTS (another_allocno)[i] += update_cost;
219 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno)[i]
220 += update_cost;
221 if (update_cost != 0)
222 update_copy_costs_1 (another_allocno, hard_regno,
223 decr_p, divisor * 4);
224 }
225 }
226
227 /* Entry function to update costs of allocnos to increase chances to
228 remove some copies as the result of subsequent assignment. */
229 static void
230 update_copy_costs (allocno_t allocno, int decr_p)
231 {
232 update_cost_check++;
233 update_copy_costs_1 (allocno, ALLOCNO_HARD_REGNO (allocno), decr_p, 1);
234 }
235
236 /* The function is used to sort allocnos according to the profit of
237 usage of a hard register instead of memory for them. */
238 static int
239 allocno_cost_compare_func (const void *v1p, const void *v2p)
240 {
241 allocno_t p1 = *(const allocno_t *) v1p, p2 = *(const allocno_t *) v2p;
242 int c1, c2;
243
244 c1 = ALLOCNO_UPDATED_MEMORY_COST (p1) - ALLOCNO_COVER_CLASS_COST (p1);
245 c2 = ALLOCNO_UPDATED_MEMORY_COST (p2) - ALLOCNO_COVER_CLASS_COST (p2);
246 if (c1 - c2)
247 return c1 - c2;
248
249 /* If regs are equally good, sort by allocno numbers, so that the
250 results of qsort leave nothing to chance. */
251 return ALLOCNO_NUM (p1) - ALLOCNO_NUM (p2);
252 }
253
254 /* Print all allocnos coalesced with ALLOCNO. */
255 static void
256 print_coalesced_allocno (allocno_t allocno)
257 {
258 allocno_t a;
259
260 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
261 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
262 {
263 print_expanded_allocno (a);
264 if (a == allocno)
265 break;
266 fprintf (ira_dump_file, "+");
267 }
268 }
269
270 /* Function choosing a hard register for ALLOCNO (or for all coalesced
271 allocnos represented by ALLOCNO). If RETRY_P is TRUE, it means
272 that the function called from function `reassign_conflict_allocnos'
273 and `allocno_reload_assign'. The function implements the
274 optimistic coalescing too: if we failed to assign a hard register
275 to set of the coalesced allocnos, we put them onto the coloring
276 stack for subsequent separate assigning. */
277 static int
278 assign_hard_reg (allocno_t allocno, int retry_p)
279 {
280 HARD_REG_SET conflicting_regs;
281 int i, j, hard_regno, best_hard_regno, class_size;
282 int cost, mem_cost, min_cost, full_cost, min_full_cost, add_cost;
283 int *a_costs;
284 int *conflict_costs;
285 enum reg_class cover_class, class;
286 enum machine_mode mode;
287 allocno_t a, conflict_allocno;
288 allocno_t another_allocno;
289 allocno_conflict_iterator aci;
290 copy_t cp, next_cp;
291 static int costs[FIRST_PSEUDO_REGISTER], full_costs[FIRST_PSEUDO_REGISTER];
292 #ifdef STACK_REGS
293 int no_stack_reg_p;
294 #endif
295
296 ira_assert (! ALLOCNO_ASSIGNED_P (allocno));
297 cover_class = ALLOCNO_COVER_CLASS (allocno);
298 class_size = class_hard_regs_num[cover_class];
299 mode = ALLOCNO_MODE (allocno);
300 COPY_HARD_REG_SET (conflicting_regs, no_alloc_regs);
301 IOR_COMPL_HARD_REG_SET (conflicting_regs, reg_class_contents[cover_class]);
302 best_hard_regno = -1;
303 memset (full_costs, 0, sizeof (int) * class_size);
304 mem_cost = 0;
305 if (allocno_coalesced_p)
306 bitmap_clear (processed_coalesced_allocno_bitmap);
307 memset (costs, 0, sizeof (int) * class_size);
308 memset (full_costs, 0, sizeof (int) * class_size);
309 #ifdef STACK_REGS
310 no_stack_reg_p = FALSE;
311 #endif
312 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
313 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
314 {
315 mem_cost += ALLOCNO_UPDATED_MEMORY_COST (a);
316 IOR_HARD_REG_SET (conflicting_regs,
317 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
318 allocate_and_copy_costs (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
319 cover_class, ALLOCNO_HARD_REG_COSTS (a));
320 a_costs = ALLOCNO_UPDATED_HARD_REG_COSTS (a);
321 #ifdef STACK_REGS
322 no_stack_reg_p = no_stack_reg_p || ALLOCNO_TOTAL_NO_STACK_REG_P (a);
323 #endif
324 for (cost = ALLOCNO_COVER_CLASS_COST (a), i = 0; i < class_size; i++)
325 if (a_costs != NULL)
326 {
327 costs[i] += a_costs[i];
328 full_costs[i] += a_costs[i];
329 }
330 else
331 {
332 costs[i] += cost;
333 full_costs[i] += cost;
334 }
335 /* Take preferences of conflicting allocnos into account. */
336 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
337 /* Reload can give another class so we need to check all
338 allocnos. */
339 if (retry_p || bitmap_bit_p (consideration_allocno_bitmap,
340 ALLOCNO_NUM (conflict_allocno)))
341 {
342 ira_assert (cover_class == ALLOCNO_COVER_CLASS (conflict_allocno));
343 if (allocno_coalesced_p)
344 {
345 if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
346 ALLOCNO_NUM (conflict_allocno)))
347 continue;
348 bitmap_set_bit (processed_coalesced_allocno_bitmap,
349 ALLOCNO_NUM (conflict_allocno));
350 }
351 if (ALLOCNO_ASSIGNED_P (conflict_allocno))
352 {
353 if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno)) >= 0)
354 {
355 IOR_HARD_REG_SET
356 (conflicting_regs,
357 reg_mode_hard_regset
358 [hard_regno][ALLOCNO_MODE (conflict_allocno)]);
359 if (hard_reg_set_subset_p (reg_class_contents[cover_class],
360 conflicting_regs))
361 goto fail;
362 }
363 continue;
364 }
365 else if (! ALLOCNO_MAY_BE_SPILLED_P (conflict_allocno))
366 {
367 allocate_and_copy_costs
368 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno),
369 cover_class,
370 ALLOCNO_CONFLICT_HARD_REG_COSTS (conflict_allocno));
371 conflict_costs
372 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (conflict_allocno);
373 if (conflict_costs != NULL)
374 for (j = class_size - 1; j >= 0; j--)
375 full_costs[j] -= conflict_costs[j];
376 }
377 }
378 if (a == allocno)
379 break;
380 }
381 /* Take copies into account. */
382 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
383 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
384 {
385 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
386 {
387 if (cp->first == a)
388 {
389 next_cp = cp->next_first_allocno_copy;
390 another_allocno = cp->second;
391 }
392 else if (cp->second == a)
393 {
394 next_cp = cp->next_second_allocno_copy;
395 another_allocno = cp->first;
396 }
397 else
398 gcc_unreachable ();
399 if (cover_class != ALLOCNO_COVER_CLASS (another_allocno)
400 || ALLOCNO_ASSIGNED_P (another_allocno))
401 continue;
402 allocate_and_copy_costs
403 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno),
404 cover_class, ALLOCNO_CONFLICT_HARD_REG_COSTS (another_allocno));
405 conflict_costs
406 = ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (another_allocno);
407 if (conflict_costs != NULL
408 && ! ALLOCNO_MAY_BE_SPILLED_P (another_allocno))
409 for (j = class_size - 1; j >= 0; j--)
410 full_costs[j] += conflict_costs[j];
411 }
412 if (a == allocno)
413 break;
414 }
415 min_cost = min_full_cost = INT_MAX;
416 /* We don't care about giving callee saved registers to allocnos no
417 living through calls because call clobbered registers are
418 allocated first (it is usual practice to put them first in
419 REG_ALLOC_ORDER). */
420 for (i = 0; i < class_size; i++)
421 {
422 hard_regno = class_hard_regs[cover_class][i];
423 #ifdef STACK_REGS
424 if (no_stack_reg_p
425 && FIRST_STACK_REG <= hard_regno && hard_regno <= LAST_STACK_REG)
426 continue;
427 #endif
428 if (! hard_reg_not_in_set_p (hard_regno, mode, conflicting_regs)
429 || TEST_HARD_REG_BIT (prohibited_class_mode_regs[cover_class][mode],
430 hard_regno))
431 continue;
432 cost = costs[i];
433 full_cost = full_costs[i];
434 if (! allocated_hardreg_p[hard_regno]
435 && hard_reg_not_in_set_p (hard_regno, mode, call_used_reg_set))
436 /* We need to save/restore the hard register in
437 epilogue/prologue. Therefore we increase the cost. */
438 {
439 /* ??? If only part is call clobbered. */
440 class = REGNO_REG_CLASS (hard_regno);
441 add_cost = (memory_move_cost[mode][class][0]
442 + memory_move_cost[mode][class][1] - 1);
443 cost += add_cost;
444 full_cost += add_cost;
445 }
446 if (min_cost > cost)
447 min_cost = cost;
448 if (min_full_cost > full_cost)
449 {
450 min_full_cost = full_cost;
451 best_hard_regno = hard_regno;
452 ira_assert (hard_regno >= 0);
453 }
454 }
455 if (min_full_cost > mem_cost)
456 {
457 if (! retry_p && internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
458 fprintf (ira_dump_file, "(memory is more profitable %d vs %d) ",
459 mem_cost, min_full_cost);
460 best_hard_regno = -1;
461 }
462 fail:
463 if (best_hard_regno < 0
464 && ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno) != allocno)
465 {
466 for (j = 0, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
467 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
468 {
469 sorted_allocnos[j++] = a;
470 if (a == allocno)
471 break;
472 }
473 qsort (sorted_allocnos, j, sizeof (allocno_t),
474 allocno_cost_compare_func);
475 for (i = 0; i < j; i++)
476 {
477 a = sorted_allocnos[i];
478 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
479 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
480 VARRAY_PUSH_GENERIC_PTR (allocno_stack_varray, a);
481 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
482 {
483 fprintf (ira_dump_file, " Pushing");
484 print_coalesced_allocno (a);
485 fprintf (ira_dump_file, "\n");
486 }
487 }
488 return FALSE;
489 }
490 if (best_hard_regno >= 0)
491 allocated_hardreg_p[best_hard_regno] = TRUE;
492 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
493 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
494 {
495 ALLOCNO_HARD_REGNO (a) = best_hard_regno;
496 ALLOCNO_ASSIGNED_P (a) = TRUE;
497 if (best_hard_regno >= 0)
498 update_copy_costs (a, TRUE);
499 ira_assert (ALLOCNO_COVER_CLASS (a) == cover_class);
500 /* We don't need updated costs anymore: */
501 free_allocno_updated_costs (a);
502 if (a == allocno)
503 break;
504 }
505 return best_hard_regno >= 0;
506 }
507
508 \f
509
510 /* This page contains allocator based on Chaitin-Briggs algorithm. */
511
512 /* Bucket of allocnos that can colored currently without spilling. */
513 static allocno_t colorable_allocno_bucket;
514
515 /* Bucket of allocnos that might be not colored currently without
516 spilling. */
517 static allocno_t uncolorable_allocno_bucket;
518
519 /* Add ALLOCNO to bucket *BUCKET_PTR. ALLOCNO should be not in a bucket
520 before the call. */
521 static void
522 add_allocno_to_bucket (allocno_t allocno, allocno_t *bucket_ptr)
523 {
524 allocno_t first_allocno;
525
526 first_allocno = *bucket_ptr;
527 ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno) = first_allocno;
528 ALLOCNO_PREV_BUCKET_ALLOCNO (allocno) = NULL;
529 if (first_allocno != NULL)
530 ALLOCNO_PREV_BUCKET_ALLOCNO (first_allocno) = allocno;
531 *bucket_ptr = allocno;
532 }
533
534 /* The function returns frequency and number of available hard
535 registers for allocnos coalesced with ALLOCNO. */
536 static void
537 get_coalesced_allocnos_attributes (allocno_t allocno, int *freq, int *num)
538 {
539 allocno_t a;
540
541 *freq = 0;
542 *num = 0;
543 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
544 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
545 {
546 *freq += ALLOCNO_FREQ (a);
547 *num += ALLOCNO_AVAILABLE_REGS_NUM (a);
548 if (a == allocno)
549 break;
550 }
551 }
552
553 /* The function compares two allocnos to define what allocno should be
554 pushed first into the coloring stack. If the function returns a
555 negative number, the allocno given by the first parameter will be
556 pushed first. In this case such allocno has less priority than the
557 second one and the hard register will be assigned to it after
558 assignment to the second one. As the result of such assignment
559 order, the second allocno has a better chance to get the best hard
560 register. */
561 static int
562 bucket_allocno_compare_func (const void *v1p, const void *v2p)
563 {
564 allocno_t a1 = *(const allocno_t *) v1p, a2 = *(const allocno_t *) v2p;
565 int diff, a1_freq, a2_freq, a1_num, a2_num;
566
567 if ((diff = (int) ALLOCNO_COVER_CLASS (a2) - ALLOCNO_COVER_CLASS (a1)) != 0)
568 return diff;
569 get_coalesced_allocnos_attributes (a1, &a1_freq, &a1_num);
570 get_coalesced_allocnos_attributes (a2, &a2_freq, &a2_num);
571 if ((diff = a2_num - a1_num) != 0)
572 return diff;
573 else if ((diff = a1_freq - a2_freq) != 0)
574 return diff;
575 return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
576 }
577
578 /* Function sorts bucket *BUCKET_PTR and returns the result through
579 BUCKET_PTR. */
580 static void
581 sort_bucket (allocno_t *bucket_ptr)
582 {
583 allocno_t a, head;
584 int n;
585
586 for (n = 0, a = *bucket_ptr; a != NULL; a = ALLOCNO_NEXT_BUCKET_ALLOCNO (a))
587 sorted_allocnos[n++] = a;
588 if (n <= 1)
589 return;
590 qsort (sorted_allocnos, n, sizeof (allocno_t), bucket_allocno_compare_func);
591 head = NULL;
592 for (n--; n >= 0; n--)
593 {
594 a = sorted_allocnos[n];
595 ALLOCNO_NEXT_BUCKET_ALLOCNO (a) = head;
596 ALLOCNO_PREV_BUCKET_ALLOCNO (a) = NULL;
597 if (head != NULL)
598 ALLOCNO_PREV_BUCKET_ALLOCNO (head) = a;
599 head = a;
600 }
601 *bucket_ptr = head;
602 }
603
604 /* Add ALLOCNO to bucket *BUCKET_PTR maintaining the order according
605 their priority. ALLOCNO should be not in a bucket before the
606 call. */
607 static void
608 add_allocno_to_ordered_bucket (allocno_t allocno, allocno_t *bucket_ptr)
609 {
610 allocno_t before, after;
611
612 for (before = *bucket_ptr, after = NULL;
613 before != NULL;
614 after = before, before = ALLOCNO_NEXT_BUCKET_ALLOCNO (before))
615 if (bucket_allocno_compare_func (&allocno, &before) < 0)
616 break;
617 ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno) = before;
618 ALLOCNO_PREV_BUCKET_ALLOCNO (allocno) = after;
619 if (after == NULL)
620 *bucket_ptr = allocno;
621 else
622 ALLOCNO_NEXT_BUCKET_ALLOCNO (after) = allocno;
623 if (before != NULL)
624 ALLOCNO_PREV_BUCKET_ALLOCNO (before) = allocno;
625 }
626
627 /* Delete ALLOCNO from bucket *BUCKET_PTR. It should be there before
628 the call. */
629 static void
630 delete_allocno_from_bucket (allocno_t allocno, allocno_t *bucket_ptr)
631 {
632 allocno_t prev_allocno, next_allocno;
633
634 prev_allocno = ALLOCNO_PREV_BUCKET_ALLOCNO (allocno);
635 next_allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno);
636 if (prev_allocno != NULL)
637 ALLOCNO_NEXT_BUCKET_ALLOCNO (prev_allocno) = next_allocno;
638 else
639 {
640 ira_assert (*bucket_ptr == allocno);
641 *bucket_ptr = next_allocno;
642 }
643 if (next_allocno != NULL)
644 ALLOCNO_PREV_BUCKET_ALLOCNO (next_allocno) = prev_allocno;
645 }
646
647 /* The function puts ALLOCNO onto the coloring stack without removing
648 it from its bucket. Pushing allocno to the coloring stack can
649 result in moving conflicting allocnos from the uncolorable bucket
650 to the colorable one. */
651 static void
652 push_allocno_to_stack (allocno_t allocno)
653 {
654 int conflicts_num, conflict_size, size;
655 allocno_t a, conflict_allocno;
656 enum reg_class cover_class;
657 allocno_conflict_iterator aci;
658
659 ALLOCNO_IN_GRAPH_P (allocno) = FALSE;
660 VARRAY_PUSH_GENERIC_PTR (allocno_stack_varray, allocno);
661 cover_class = ALLOCNO_COVER_CLASS (allocno);
662 if (cover_class == NO_REGS)
663 return;
664 size = reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)];
665 if (allocno_coalesced_p)
666 bitmap_clear (processed_coalesced_allocno_bitmap);
667 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
668 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
669 {
670 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
671 if (bitmap_bit_p (coloring_allocno_bitmap,
672 ALLOCNO_NUM (conflict_allocno)))
673 {
674 ira_assert (cover_class == ALLOCNO_COVER_CLASS (conflict_allocno));
675 if (allocno_coalesced_p)
676 {
677 if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
678 ALLOCNO_NUM (conflict_allocno)))
679 continue;
680 bitmap_set_bit (processed_coalesced_allocno_bitmap,
681 ALLOCNO_NUM (conflict_allocno));
682 }
683 if (ALLOCNO_IN_GRAPH_P (conflict_allocno)
684 && ! ALLOCNO_ASSIGNED_P (conflict_allocno))
685 {
686 conflicts_num = ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno);
687 conflict_size
688 = (reg_class_nregs
689 [cover_class][ALLOCNO_MODE (conflict_allocno)]);
690 ira_assert
691 (ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) >= size);
692 ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno) -= size;
693 if (conflicts_num + conflict_size
694 <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno))
695 continue;
696 conflicts_num = ALLOCNO_LEFT_CONFLICTS_NUM (conflict_allocno);
697 if (conflicts_num + conflict_size
698 <= ALLOCNO_AVAILABLE_REGS_NUM (conflict_allocno))
699 {
700 delete_allocno_from_bucket
701 (conflict_allocno, &uncolorable_allocno_bucket);
702 add_allocno_to_ordered_bucket (conflict_allocno,
703 &colorable_allocno_bucket);
704 }
705 }
706 }
707 if (a == allocno)
708 break;
709 }
710 }
711
712 /* The function puts ALLOCNO onto the coloring stack and removes it
713 from its bucket. The allocno is in the colorable bucket if
714 COLORABLE_P is TRUE. */
715 static void
716 remove_allocno_from_bucket_and_push (allocno_t allocno, int colorable_p)
717 {
718 enum reg_class cover_class;
719 allocno_t *bucket_ptr;
720
721 bucket_ptr = (colorable_p
722 ? &colorable_allocno_bucket : &uncolorable_allocno_bucket);
723 delete_allocno_from_bucket (allocno, bucket_ptr);
724 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
725 {
726 fprintf (ira_dump_file, " Pushing");
727 print_coalesced_allocno (allocno);
728 fprintf (ira_dump_file, "%s\n", colorable_p ? "" : "(potential spill)");
729 }
730 cover_class = ALLOCNO_COVER_CLASS (allocno);
731 ira_assert ((colorable_p
732 && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
733 + reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)]
734 <= ALLOCNO_AVAILABLE_REGS_NUM (allocno)))
735 || (! colorable_p
736 && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
737 + reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)]
738 > ALLOCNO_AVAILABLE_REGS_NUM (allocno))));
739 if (! colorable_p)
740 ALLOCNO_MAY_BE_SPILLED_P (allocno) = TRUE;
741 push_allocno_to_stack (allocno);
742 }
743
744 /* The function puts all allocnos from colorable bucket onto the
745 coloring stack. */
746 static void
747 push_only_colorable (void)
748 {
749 sort_bucket (&colorable_allocno_bucket);
750 for (;colorable_allocno_bucket != NULL;)
751 remove_allocno_from_bucket_and_push (colorable_allocno_bucket, TRUE);
752 }
753
754 /* The function puts ALLOCNO chosen for potential spilling onto the
755 coloring stack. */
756 static void
757 push_allocno_to_spill (allocno_t allocno)
758 {
759 delete_allocno_from_bucket (allocno, &uncolorable_allocno_bucket);
760 ALLOCNO_MAY_BE_SPILLED_P (allocno) = TRUE;
761 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
762 fprintf (ira_dump_file, " Pushing p%d(%d) (potential spill)\n",
763 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno));
764 push_allocno_to_stack (allocno);
765 }
766
767 /* The function returns frequency of exit edges (if EXIT_P) or entry
768 from/to the loop given by its LOOP_NODE. */
769 int
770 loop_edge_freq (loop_tree_node_t loop_node, int regno, int exit_p)
771 {
772 int freq, i;
773 edge_iterator ei;
774 edge e;
775 VEC (edge, heap) *edges;
776
777 ira_assert (loop_node->loop != NULL
778 && (regno < 0 || regno >= FIRST_PSEUDO_REGISTER));
779 freq = 0;
780 if (! exit_p)
781 {
782 FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
783 if (e->src != loop_node->loop->latch
784 && (regno < 0
785 || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
786 && bitmap_bit_p (DF_LR_IN (e->dest), regno))))
787 freq += EDGE_FREQUENCY (e);
788 }
789 else
790 {
791 edges = get_loop_exit_edges (loop_node->loop);
792 for (i = 0; VEC_iterate (edge, edges, i, e); i++)
793 if (regno < 0
794 || (bitmap_bit_p (DF_LR_OUT (e->src), regno)
795 && bitmap_bit_p (DF_LR_IN (e->dest), regno)))
796 freq += EDGE_FREQUENCY (e);
797 VEC_free (edge, heap, edges);
798 }
799
800 return REG_FREQ_FROM_EDGE_FREQ (freq);
801 }
802
803 /* The function calculates and returns cost of putting allocno A into
804 memory. */
805 static int
806 calculate_allocno_spill_cost (allocno_t a)
807 {
808 int regno, cost;
809 enum machine_mode mode;
810 enum reg_class class;
811 allocno_t father_allocno;
812 loop_tree_node_t father_node, loop_node;
813
814 regno = ALLOCNO_REGNO (a);
815 cost = ALLOCNO_UPDATED_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a);
816 if (ALLOCNO_CAP (a) != NULL)
817 return cost;
818 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
819 if ((father_node = loop_node->father) == NULL)
820 return cost;
821 if ((father_allocno = father_node->regno_allocno_map[regno]) == NULL)
822 return cost;
823 mode = ALLOCNO_MODE (a);
824 class = ALLOCNO_COVER_CLASS (a);
825 if (ALLOCNO_HARD_REGNO (father_allocno) < 0)
826 cost -= (memory_move_cost[mode][class][0]
827 * loop_edge_freq (loop_node, regno, TRUE)
828 + memory_move_cost[mode][class][1]
829 * loop_edge_freq (loop_node, regno, FALSE));
830 else
831 cost += ((memory_move_cost[mode][class][1]
832 * loop_edge_freq (loop_node, regno, TRUE)
833 + memory_move_cost[mode][class][0]
834 * loop_edge_freq (loop_node, regno, FALSE))
835 - (register_move_cost[mode][class][class]
836 * (loop_edge_freq (loop_node, regno, FALSE)
837 + loop_edge_freq (loop_node, regno, TRUE))));
838 return cost;
839 }
840
841 /* Push allocnos to the coloring stack. The order of allocnos in the
842 stack defines the order for the subsequent coloring. */
843 static void
844 push_allocnos_to_stack (void)
845 {
846 int i, j;
847 int allocno_pri, i_allocno_pri;
848 int allocno_cost, i_allocno_cost;
849 allocno_t allocno, i_allocno;
850 allocno_t *allocno_vec;
851 enum reg_class cover_class;
852 int num, cover_class_allocnos_num[N_REG_CLASSES];
853 allocno_t *cover_class_allocnos[N_REG_CLASSES];
854
855 /* Initialize. */
856 for (i = 0; i < reg_class_cover_size; i++)
857 {
858 cover_class = reg_class_cover[i];
859 cover_class_allocnos_num[cover_class] = 0;
860 cover_class_allocnos[cover_class] = NULL;
861 }
862 /* Calculate uncolorable allocnos of each cover class. */
863 for (allocno = uncolorable_allocno_bucket;
864 allocno != NULL;
865 allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno))
866 if ((cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
867 {
868 cover_class_allocnos_num[cover_class]++;
869 ALLOCNO_TEMP (allocno) = INT_MAX;
870 }
871 /* Define place where to put uncolorable allocnos of the same cover
872 class. */
873 for (num = i = 0; i < reg_class_cover_size; i++)
874 {
875 cover_class = reg_class_cover[i];
876 if (cover_class_allocnos_num[cover_class] != 0)
877 {
878 cover_class_allocnos[cover_class]
879 = sorted_allocnos_for_spilling + num;
880 num += cover_class_allocnos_num[cover_class];
881 cover_class_allocnos_num[cover_class] = 0;
882 }
883 }
884 ira_assert (num <= allocnos_num);
885 /* Put uncolorable allocnos of the same cover class together. */
886 for (allocno = uncolorable_allocno_bucket;
887 allocno != NULL;
888 allocno = ALLOCNO_NEXT_BUCKET_ALLOCNO (allocno))
889 if ((cover_class = ALLOCNO_COVER_CLASS (allocno)) != NO_REGS)
890 cover_class_allocnos
891 [cover_class][cover_class_allocnos_num[cover_class]++] = allocno;
892 for (;;)
893 {
894 push_only_colorable ();
895 allocno = uncolorable_allocno_bucket;
896 if (allocno == NULL)
897 break;
898 cover_class = ALLOCNO_COVER_CLASS (allocno);
899 if (cover_class == NO_REGS)
900 {
901 push_allocno_to_spill (allocno);
902 continue;
903 }
904 /* Potential spilling. */
905 ira_assert (reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)] > 0);
906 num = cover_class_allocnos_num[cover_class];
907 ira_assert (num > 0);
908 allocno_vec = cover_class_allocnos[cover_class];
909 allocno = NULL;
910 allocno_pri = allocno_cost = 0;
911 /* Sort uncolorable allocno to find the one with the lowest spill
912 cost. */
913 for (i = 0, j = num - 1; i <= j;)
914 {
915 i_allocno = allocno_vec[i];
916 if (! ALLOCNO_IN_GRAPH_P (i_allocno)
917 && ALLOCNO_IN_GRAPH_P (allocno_vec[j]))
918 {
919 i_allocno = allocno_vec[j];
920 allocno_vec[j] = allocno_vec[i];
921 allocno_vec[i] = i_allocno;
922 }
923 if (ALLOCNO_IN_GRAPH_P (i_allocno))
924 {
925 i++;
926 if (ALLOCNO_TEMP (i_allocno) == INT_MAX)
927 {
928 allocno_t a;
929 int cost = 0;
930
931 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (i_allocno);;
932 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
933 {
934 cost += calculate_allocno_spill_cost (i_allocno);
935 if (a == i_allocno)
936 break;
937 }
938 /* ??? Remove cost of copies between the coalesced
939 allocnos. */
940 ALLOCNO_TEMP (i_allocno) = cost;
941 }
942 i_allocno_cost = ALLOCNO_TEMP (i_allocno);
943 i_allocno_pri
944 = (i_allocno_cost
945 / (ALLOCNO_LEFT_CONFLICTS_NUM (i_allocno)
946 * reg_class_nregs[ALLOCNO_COVER_CLASS (i_allocno)]
947 [ALLOCNO_MODE (i_allocno)] + 1));
948 if (allocno == NULL || allocno_pri > i_allocno_pri
949 || (allocno_pri == i_allocno_pri
950 && (allocno_cost > i_allocno_cost
951 || (allocno_cost == i_allocno_cost
952 && (ALLOCNO_NUM (allocno)
953 > ALLOCNO_NUM (i_allocno))))))
954 {
955 allocno = i_allocno;
956 allocno_cost = i_allocno_cost;
957 allocno_pri = i_allocno_pri;
958 }
959 }
960 if (! ALLOCNO_IN_GRAPH_P (allocno_vec[j]))
961 j--;
962 }
963 ira_assert (allocno != NULL && j >= 0);
964 cover_class_allocnos_num[cover_class] = j + 1;
965 ira_assert (ALLOCNO_IN_GRAPH_P (allocno)
966 && ALLOCNO_COVER_CLASS (allocno) == cover_class
967 && (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
968 + reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)]
969 > ALLOCNO_AVAILABLE_REGS_NUM (allocno)));
970 remove_allocno_from_bucket_and_push (allocno, FALSE);
971 }
972 }
973
974 /* Pop the coloring stack and assign hard registers to the popped
975 allocnos. */
976 static void
977 pop_allocnos_from_stack (void)
978 {
979 allocno_t allocno;
980 enum reg_class cover_class;
981
982 for (;VARRAY_ACTIVE_SIZE (allocno_stack_varray) != 0;)
983 {
984 allocno = VARRAY_TOP_GENERIC_PTR (allocno_stack_varray);
985 VARRAY_POP (allocno_stack_varray);
986 cover_class = ALLOCNO_COVER_CLASS (allocno);
987 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
988 {
989 fprintf (ira_dump_file, " Popping");
990 print_coalesced_allocno (allocno);
991 fprintf (ira_dump_file, " -- ");
992 }
993 if (cover_class == NO_REGS)
994 {
995 ALLOCNO_HARD_REGNO (allocno) = -1;
996 ALLOCNO_ASSIGNED_P (allocno) = TRUE;
997 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (allocno) == NULL);
998 ira_assert
999 (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (allocno) == NULL);
1000 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1001 fprintf (ira_dump_file, "assign memory\n");
1002 }
1003 else if (assign_hard_reg (allocno, FALSE))
1004 {
1005 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1006 fprintf (ira_dump_file, "assign reg %d\n",
1007 ALLOCNO_HARD_REGNO (allocno));
1008 }
1009 else if (ALLOCNO_ASSIGNED_P (allocno))
1010 {
1011 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1012 fprintf (ira_dump_file, "spill\n");
1013 }
1014 ALLOCNO_IN_GRAPH_P (allocno) = TRUE;
1015 }
1016 }
1017
1018 /* Set up number of available hard registers for ALLOCNO. */
1019 static void
1020 setup_allocno_available_regs_num (allocno_t allocno)
1021 {
1022 int i, n, hard_regs_num;
1023 enum reg_class cover_class;
1024 allocno_t a;
1025 HARD_REG_SET temp_set;
1026
1027 cover_class = ALLOCNO_COVER_CLASS (allocno);
1028 ALLOCNO_AVAILABLE_REGS_NUM (allocno) = available_class_regs[cover_class];
1029 if (cover_class == NO_REGS)
1030 return;
1031 CLEAR_HARD_REG_SET (temp_set);
1032 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) == allocno);
1033 hard_regs_num = class_hard_regs_num[cover_class];
1034 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1035 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1036 {
1037 IOR_HARD_REG_SET (temp_set, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1038 if (a == allocno)
1039 break;
1040 }
1041 for (n = 0, i = hard_regs_num - 1; i >= 0; i--)
1042 if (TEST_HARD_REG_BIT (temp_set, class_hard_regs[cover_class][i]))
1043 n++;
1044 if (internal_flag_ira_verbose > 2 && n > 0 && ira_dump_file != NULL)
1045 fprintf (ira_dump_file, " Reg %d of %s has %d regs less\n",
1046 ALLOCNO_REGNO (allocno), reg_class_names[cover_class], n);
1047 ALLOCNO_AVAILABLE_REGS_NUM (allocno) -= n;
1048 }
1049
1050 /* Set up ALLOCNO_LEFT_CONFLICTS_NUM for ALLOCNO. */
1051 static void
1052 setup_allocno_left_conflicts_num (allocno_t allocno)
1053 {
1054 int i, hard_regs_num, hard_regno, conflict_allocnos_size;
1055 allocno_t a, conflict_allocno;
1056 enum reg_class cover_class;
1057 HARD_REG_SET temp_set;
1058 allocno_conflict_iterator aci;
1059
1060 cover_class = ALLOCNO_COVER_CLASS (allocno);
1061 hard_regs_num = class_hard_regs_num[cover_class];
1062 CLEAR_HARD_REG_SET (temp_set);
1063 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) == allocno);
1064 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1065 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1066 {
1067 IOR_HARD_REG_SET (temp_set, ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1068 if (a == allocno)
1069 break;
1070 }
1071 AND_HARD_REG_SET (temp_set, reg_class_contents[cover_class]);
1072 AND_COMPL_HARD_REG_SET (temp_set, no_alloc_regs);
1073 conflict_allocnos_size = 0;
1074 if (! hard_reg_set_equal_p (temp_set, zero_hard_reg_set))
1075 for (i = 0; i < (int) hard_regs_num; i++)
1076 {
1077 hard_regno = class_hard_regs[cover_class][i];
1078 if (TEST_HARD_REG_BIT (temp_set, hard_regno))
1079 {
1080 conflict_allocnos_size++;
1081 CLEAR_HARD_REG_BIT (temp_set, hard_regno);
1082 if (hard_reg_set_equal_p (temp_set, zero_hard_reg_set))
1083 break;
1084 }
1085 }
1086 CLEAR_HARD_REG_SET (temp_set);
1087 if (allocno_coalesced_p)
1088 bitmap_clear (processed_coalesced_allocno_bitmap);
1089 if (cover_class != NO_REGS)
1090 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
1091 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1092 {
1093 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
1094 if (bitmap_bit_p (consideration_allocno_bitmap,
1095 ALLOCNO_NUM (conflict_allocno)))
1096 {
1097 ira_assert (cover_class
1098 == ALLOCNO_COVER_CLASS (conflict_allocno));
1099 if (allocno_coalesced_p)
1100 {
1101 if (bitmap_bit_p (processed_coalesced_allocno_bitmap,
1102 ALLOCNO_NUM (conflict_allocno)))
1103 continue;
1104 bitmap_set_bit (processed_coalesced_allocno_bitmap,
1105 ALLOCNO_NUM (conflict_allocno));
1106 }
1107 if (! ALLOCNO_ASSIGNED_P (conflict_allocno))
1108 conflict_allocnos_size
1109 += (reg_class_nregs
1110 [cover_class][ALLOCNO_MODE (conflict_allocno)]);
1111 else if ((hard_regno = ALLOCNO_HARD_REGNO (conflict_allocno))
1112 >= 0)
1113 {
1114 int last = (hard_regno
1115 + hard_regno_nregs
1116 [hard_regno][ALLOCNO_MODE (conflict_allocno)]);
1117
1118 while (hard_regno < last)
1119 {
1120 if (! TEST_HARD_REG_BIT (temp_set, hard_regno))
1121 {
1122 conflict_allocnos_size++;
1123 SET_HARD_REG_BIT (temp_set, hard_regno);
1124 }
1125 hard_regno++;
1126 }
1127 }
1128 }
1129 if (a == allocno)
1130 break;
1131 }
1132 ALLOCNO_LEFT_CONFLICTS_NUM (allocno) = conflict_allocnos_size;
1133 }
1134
1135 /* The function put ALLOCNO in a bucket corresponding to its number and
1136 size of its conflicting allocnos and hard registers. */
1137 static void
1138 put_allocno_into_bucket (allocno_t allocno)
1139 {
1140 int hard_regs_num;
1141 enum reg_class cover_class;
1142
1143 cover_class = ALLOCNO_COVER_CLASS (allocno);
1144 hard_regs_num = class_hard_regs_num[cover_class];
1145 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
1146 return;
1147 ALLOCNO_IN_GRAPH_P (allocno) = TRUE;
1148 setup_allocno_left_conflicts_num (allocno);
1149 setup_allocno_available_regs_num (allocno);
1150 if (ALLOCNO_LEFT_CONFLICTS_NUM (allocno)
1151 + reg_class_nregs[cover_class][ALLOCNO_MODE (allocno)]
1152 <= ALLOCNO_AVAILABLE_REGS_NUM (allocno))
1153 add_allocno_to_bucket (allocno, &colorable_allocno_bucket);
1154 else
1155 add_allocno_to_bucket (allocno, &uncolorable_allocno_bucket);
1156 }
1157
1158 /* The function is used to sort allocnos according to their execution
1159 frequencies. */
1160 static int
1161 copy_freq_compare_func (const void *v1p, const void *v2p)
1162 {
1163 copy_t cp1 = *(const copy_t *) v1p, cp2 = *(const copy_t *) v2p;
1164 int pri1, pri2;
1165
1166 pri1 = cp1->freq;
1167 pri2 = cp2->freq;
1168 if (pri2 - pri1)
1169 return pri2 - pri1;
1170
1171 /* If freqencies are equal, sort by copies, so that the results of
1172 qsort leave nothing to chance. */
1173 return cp1->num - cp2->num;
1174 }
1175
1176 /* The function merges two sets of coalesced allocnos given
1177 correspondingly by allocnos A1 and A2 (more accurately merging A2
1178 set into A1 set). */
1179 static void
1180 merge_allocnos (allocno_t a1, allocno_t a2)
1181 {
1182 allocno_t a, first, last, next;
1183
1184 first = ALLOCNO_FIRST_COALESCED_ALLOCNO (a1);
1185 if (first == ALLOCNO_FIRST_COALESCED_ALLOCNO (a2))
1186 return;
1187 for (last = a2, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
1188 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1189 {
1190 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = first;
1191 if (a == a2)
1192 break;
1193 last = a;
1194 }
1195 next = ALLOCNO_NEXT_COALESCED_ALLOCNO (first);
1196 ALLOCNO_NEXT_COALESCED_ALLOCNO (first) = a2;
1197 ALLOCNO_NEXT_COALESCED_ALLOCNO (last) = next;
1198 }
1199
1200 /* The function returns TRUE if there are conflicting allocnos from
1201 two sets of coalesced allocnos given correspondingly by allocnos
1202 A1 and A2. If RELOAD_P is TRUE, we use live ranges to find
1203 conflicts because conflicts are represented only for allocnos of
1204 the same cover class and during the reload pass we coalesce
1205 allocnos for sharing stack memory slots. */
1206 static int
1207 coalesced_allocno_conflict_p (allocno_t a1, allocno_t a2, int reload_p)
1208 {
1209 allocno_t a, conflict_allocno;
1210 allocno_conflict_iterator aci;
1211
1212 if (allocno_coalesced_p)
1213 {
1214 bitmap_clear (processed_coalesced_allocno_bitmap);
1215 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
1216 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1217 {
1218 bitmap_set_bit (processed_coalesced_allocno_bitmap, ALLOCNO_NUM (a));
1219 if (a == a1)
1220 break;
1221 }
1222 }
1223 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a2);;
1224 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
1225 {
1226 if (reload_p)
1227 {
1228 for (conflict_allocno = ALLOCNO_NEXT_COALESCED_ALLOCNO (a1);;
1229 conflict_allocno
1230 = ALLOCNO_NEXT_COALESCED_ALLOCNO (conflict_allocno))
1231 {
1232 if (allocno_live_ranges_intersect_p (a, conflict_allocno))
1233 return TRUE;
1234 if (conflict_allocno == a1)
1235 break;
1236 }
1237 }
1238 else
1239 {
1240 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
1241 if (conflict_allocno == a1
1242 || (allocno_coalesced_p
1243 && bitmap_bit_p (processed_coalesced_allocno_bitmap,
1244 ALLOCNO_NUM (conflict_allocno))))
1245 return TRUE;
1246 }
1247 if (a == a2)
1248 break;
1249 }
1250 return FALSE;
1251 }
1252
1253 /* The major function for aggressive allocno coalescing. For the
1254 reload pass (RELOAD_P) we coalesce only spilled allocnos. If some
1255 allocnos have been coalesced, we set up flag
1256 allocno_coalesced_p. */
1257 static void
1258 coalesce_allocnos (int reload_p)
1259 {
1260 allocno_t a;
1261 copy_t cp, next_cp, *sorted_copies;
1262 enum reg_class cover_class;
1263 enum machine_mode mode;
1264 unsigned int j;
1265 int i, n, cp_num, regno;
1266 bitmap_iterator bi;
1267
1268 sorted_copies = ira_allocate (copies_num * sizeof (copy_t));
1269 cp_num = 0;
1270 /* Collect copies. */
1271 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, j, bi)
1272 {
1273 a = allocnos[j];
1274 regno = ALLOCNO_REGNO (a);
1275 if ((! reload_p && ALLOCNO_ASSIGNED_P (a))
1276 || (reload_p
1277 && (! ALLOCNO_ASSIGNED_P (a) || ALLOCNO_HARD_REGNO (a) >= 0
1278 || (regno < reg_equiv_len
1279 && (reg_equiv_const[regno] != NULL_RTX
1280 || reg_equiv_invariant_p[regno])))))
1281 continue;
1282 cover_class = ALLOCNO_COVER_CLASS (a);
1283 mode = ALLOCNO_MODE (a);
1284 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
1285 {
1286 if (cp->first == a)
1287 {
1288 next_cp = cp->next_first_allocno_copy;
1289 regno = ALLOCNO_REGNO (cp->second);
1290 if ((reload_p
1291 || (ALLOCNO_COVER_CLASS (cp->second) == cover_class
1292 && ALLOCNO_MODE (cp->second) == mode))
1293 && cp->insn != NULL
1294 && ((! reload_p && ! ALLOCNO_ASSIGNED_P (cp->second))
1295 || (reload_p
1296 && ALLOCNO_ASSIGNED_P (cp->second)
1297 && ALLOCNO_HARD_REGNO (cp->second) < 0
1298 && (regno >= reg_equiv_len
1299 || (! reg_equiv_invariant_p[regno]
1300 && reg_equiv_const[regno] == NULL_RTX)))))
1301 sorted_copies[cp_num++] = cp;
1302 }
1303 else if (cp->second == a)
1304 next_cp = cp->next_second_allocno_copy;
1305 else
1306 gcc_unreachable ();
1307 }
1308 }
1309 qsort (sorted_copies, cp_num, sizeof (copy_t), copy_freq_compare_func);
1310 /* Coalesced copies, most frequently executed first. */
1311 for (; cp_num != 0;)
1312 {
1313 for (i = 0; i < cp_num; i++)
1314 {
1315 cp = sorted_copies[i];
1316 if (! coalesced_allocno_conflict_p (cp->first, cp->second, reload_p))
1317 {
1318 allocno_coalesced_p = TRUE;
1319 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1320 fprintf
1321 (ira_dump_file,
1322 " Coalescing copy %d:a%dr%d-a%dr%d (freq=%d)\n",
1323 cp->num, ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
1324 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second),
1325 cp->freq);
1326 merge_allocnos (cp->first, cp->second);
1327 i++;
1328 break;
1329 }
1330 }
1331 /* Collect the rest of copies. */
1332 for (n = 0; i < cp_num; i++)
1333 {
1334 cp = sorted_copies[i];
1335 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->first)
1336 != ALLOCNO_FIRST_COALESCED_ALLOCNO (cp->second))
1337 sorted_copies[n++] = cp;
1338 }
1339 cp_num = n;
1340 }
1341 ira_free (sorted_copies);
1342 }
1343
1344 /* Function implements Chaitin-Briggs coloring for allocnos in
1345 COLORING_ALLOCNO_BITMAP taking into account allocnos in
1346 CONSIDERATION_ALLOCNO_BITMAP. */
1347 static void
1348 color_allocnos (void)
1349 {
1350 unsigned int i;
1351 bitmap_iterator bi;
1352 allocno_t a;
1353
1354 allocno_coalesced_p = FALSE;
1355 processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
1356 if (flag_ira_coalesce)
1357 coalesce_allocnos (FALSE);
1358 /* Put the allocnos into the corresponding buckets. */
1359 colorable_allocno_bucket = NULL;
1360 uncolorable_allocno_bucket = NULL;
1361 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1362 {
1363 a = allocnos[i];
1364 if (ALLOCNO_COVER_CLASS (a) == NO_REGS)
1365 {
1366 ALLOCNO_HARD_REGNO (a) = -1;
1367 ALLOCNO_ASSIGNED_P (a) = TRUE;
1368 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
1369 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
1370 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1371 {
1372 fprintf (ira_dump_file, " Spill");
1373 print_coalesced_allocno (a);
1374 fprintf (ira_dump_file, "\n");
1375 }
1376 continue;
1377 }
1378 put_allocno_into_bucket (a);
1379 }
1380 push_allocnos_to_stack ();
1381 pop_allocnos_from_stack ();
1382 if (flag_ira_coalesce)
1383 /* We don't need coalesced allocnos for reassign_pseudos. */
1384 EXECUTE_IF_SET_IN_BITMAP (coloring_allocno_bitmap, 0, i, bi)
1385 {
1386 a = allocnos[i];
1387 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
1388 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
1389 }
1390 ira_free_bitmap (processed_coalesced_allocno_bitmap);
1391 allocno_coalesced_p = FALSE;
1392 }
1393
1394 \f
1395
1396 /* The function outputs information about the loop given by its
1397 LOOP_TREE_NODE. */
1398 static void
1399 print_loop_title (loop_tree_node_t loop_tree_node)
1400 {
1401 unsigned int j;
1402 bitmap_iterator bi;
1403
1404 ira_assert (loop_tree_node->loop != NULL);
1405 fprintf (ira_dump_file,
1406 "\n Loop %d (father %d, header bb%d, depth %d)\n ref:",
1407 loop_tree_node->loop->num,
1408 (loop_tree_node->father == NULL
1409 ? -1 : loop_tree_node->father->loop->num),
1410 loop_tree_node->loop->header->index,
1411 loop_depth (loop_tree_node->loop));
1412 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->mentioned_allocnos, 0, j, bi)
1413 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (allocnos[j]));
1414 fprintf (ira_dump_file, "\n modified regnos:");
1415 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->modified_regnos, 0, j, bi)
1416 fprintf (ira_dump_file, " %d", j);
1417 fprintf (ira_dump_file, "\n border:");
1418 EXECUTE_IF_SET_IN_BITMAP (loop_tree_node->border_allocnos, 0, j, bi)
1419 fprintf (ira_dump_file, " %dr%d", j, ALLOCNO_REGNO (allocnos[j]));
1420 fprintf (ira_dump_file, "\n Pressure:");
1421 for (j = 0; (int) j < reg_class_cover_size; j++)
1422 {
1423 enum reg_class cover_class;
1424
1425 cover_class = reg_class_cover[j];
1426 if (loop_tree_node->reg_pressure[cover_class] == 0)
1427 continue;
1428 fprintf (ira_dump_file, " %s=%d", reg_class_names[cover_class],
1429 loop_tree_node->reg_pressure[cover_class]);
1430 }
1431 fprintf (ira_dump_file, "\n");
1432 }
1433
1434 /* The function does coloring for allocnos inside loop (in extreme
1435 case it can be all function) given by the corresponding
1436 LOOP_TREE_NODE. The function is called for each loop during
1437 top-down traverse of the loop tree. */
1438 static void
1439 color_pass (loop_tree_node_t loop_tree_node)
1440 {
1441 int regno, hard_regno, index = -1;
1442 int cost, exit_freq, enter_freq;
1443 unsigned int j;
1444 bitmap_iterator bi;
1445 enum machine_mode mode;
1446 enum reg_class class, cover_class;
1447 allocno_t a, subloop_allocno;
1448 loop_tree_node_t subloop_node;
1449
1450 if (loop_tree_node->loop == NULL)
1451 return;
1452 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1453 print_loop_title (loop_tree_node);
1454
1455 bitmap_copy (coloring_allocno_bitmap, loop_tree_node->mentioned_allocnos);
1456 bitmap_ior_into (coloring_allocno_bitmap, loop_tree_node->border_allocnos);
1457 bitmap_copy (consideration_allocno_bitmap, coloring_allocno_bitmap);
1458 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
1459 {
1460 a = allocnos[j];
1461 if (! ALLOCNO_ASSIGNED_P (a))
1462 continue;
1463 bitmap_clear_bit (coloring_allocno_bitmap, ALLOCNO_NUM (a));
1464 }
1465 /* Color all mentioned allocnos including transparent ones. */
1466 color_allocnos ();
1467 /* Update costs of the corresponding allocnos in the subloops. */
1468 for (subloop_node = loop_tree_node->children;
1469 subloop_node != NULL;
1470 subloop_node = subloop_node->next)
1471 if (subloop_node->bb == NULL)
1472 EXECUTE_IF_SET_IN_BITMAP (consideration_allocno_bitmap, 0, j, bi)
1473 {
1474 a = allocnos[j];
1475 mode = ALLOCNO_MODE (a);
1476 class = ALLOCNO_COVER_CLASS (a);
1477 hard_regno = ALLOCNO_HARD_REGNO (a);
1478 if (hard_regno >= 0)
1479 {
1480 index = class_hard_reg_index[class][hard_regno];
1481 ira_assert (index >= 0);
1482 }
1483 regno = ALLOCNO_REGNO (a);
1484 /* ??? conflict costs */
1485 if (ALLOCNO_CAP_MEMBER (a) == NULL)
1486 {
1487 subloop_allocno = subloop_node->regno_allocno_map[regno];
1488 if (subloop_allocno == NULL)
1489 continue;
1490 if ((flag_ira_algorithm == IRA_ALGORITHM_MIXED
1491 && (loop_tree_node->reg_pressure[class]
1492 <= available_class_regs[class]))
1493 || (hard_regno < 0
1494 && ! bitmap_bit_p (subloop_node->mentioned_allocnos,
1495 ALLOCNO_NUM (subloop_allocno))))
1496 {
1497 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
1498 {
1499 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
1500 ALLOCNO_ASSIGNED_P (subloop_allocno) = TRUE;
1501 if (hard_regno >= 0)
1502 update_copy_costs (subloop_allocno, TRUE);
1503 /* We don't need updated costs anymore: */
1504 free_allocno_updated_costs (subloop_allocno);
1505 }
1506 continue;
1507 }
1508 exit_freq = loop_edge_freq (subloop_node, regno, TRUE);
1509 enter_freq = loop_edge_freq (subloop_node, regno, FALSE);
1510 ira_assert (regno < reg_equiv_len);
1511 if (reg_equiv_invariant_p[regno]
1512 || reg_equiv_const[regno] != NULL_RTX)
1513 {
1514 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
1515 {
1516 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
1517 ALLOCNO_ASSIGNED_P (subloop_allocno) = TRUE;
1518 if (hard_regno >= 0)
1519 update_copy_costs (subloop_allocno, TRUE);
1520 /* We don't need updated costs anymore: */
1521 free_allocno_updated_costs (subloop_allocno);
1522 }
1523 }
1524 else if (hard_regno < 0)
1525 {
1526 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
1527 -= ((memory_move_cost[mode][class][1] * enter_freq)
1528 + (memory_move_cost[mode][class][0] * exit_freq));
1529 }
1530 else
1531 {
1532 cover_class = ALLOCNO_COVER_CLASS (subloop_allocno);
1533 allocate_and_set_costs
1534 (&ALLOCNO_HARD_REG_COSTS (subloop_allocno), cover_class,
1535 ALLOCNO_COVER_CLASS_COST (subloop_allocno));
1536 allocate_and_set_costs
1537 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno),
1538 cover_class, 0);
1539 cost = (register_move_cost[mode][class][class]
1540 * (exit_freq + enter_freq));
1541 ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
1542 ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
1543 -= cost;
1544 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
1545 += (memory_move_cost[mode][class][0] * enter_freq
1546 + memory_move_cost[mode][class][1] * exit_freq);
1547 if (ALLOCNO_COVER_CLASS_COST (subloop_allocno)
1548 > ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index])
1549 ALLOCNO_COVER_CLASS_COST (subloop_allocno)
1550 = ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index];
1551 }
1552 }
1553 else
1554 {
1555 subloop_allocno = ALLOCNO_CAP_MEMBER (a);
1556 if (ALLOCNO_LOOP_TREE_NODE (subloop_allocno) != subloop_node)
1557 continue;
1558 if ((flag_ira_algorithm == IRA_ALGORITHM_MIXED
1559 && loop_tree_node->reg_pressure[class]
1560 <= available_class_regs[class])
1561 || (hard_regno < 0
1562 && ! bitmap_bit_p (subloop_node->mentioned_allocnos,
1563 ALLOCNO_NUM (subloop_allocno))))
1564 {
1565 if (! ALLOCNO_ASSIGNED_P (subloop_allocno))
1566 {
1567 ALLOCNO_HARD_REGNO (subloop_allocno) = hard_regno;
1568 ALLOCNO_ASSIGNED_P (subloop_allocno) = TRUE;
1569 if (hard_regno >= 0)
1570 update_copy_costs (subloop_allocno, TRUE);
1571 /* We don't need updated costs anymore: */
1572 free_allocno_updated_costs (subloop_allocno);
1573 }
1574 }
1575 else if (flag_ira_propagate_cost && hard_regno >= 0)
1576 {
1577 exit_freq = loop_edge_freq (subloop_node, -1, TRUE);
1578 enter_freq = loop_edge_freq (subloop_node, -1, FALSE);
1579 cost = (register_move_cost[mode][class][class]
1580 * (exit_freq + enter_freq));
1581 cover_class = ALLOCNO_COVER_CLASS (subloop_allocno);
1582 allocate_and_set_costs
1583 (&ALLOCNO_HARD_REG_COSTS (subloop_allocno), cover_class,
1584 ALLOCNO_COVER_CLASS_COST (subloop_allocno));
1585 allocate_and_set_costs
1586 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno),
1587 cover_class, 0);
1588 ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index] -= cost;
1589 ALLOCNO_CONFLICT_HARD_REG_COSTS (subloop_allocno)[index]
1590 -= cost;
1591 ALLOCNO_UPDATED_MEMORY_COST (subloop_allocno)
1592 += (memory_move_cost[mode][class][0] * enter_freq
1593 + memory_move_cost[mode][class][1] * exit_freq);
1594 if (ALLOCNO_COVER_CLASS_COST (subloop_allocno)
1595 > ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index])
1596 ALLOCNO_COVER_CLASS_COST (subloop_allocno)
1597 = ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index];
1598 }
1599 }
1600 }
1601 }
1602
1603 /* The function initialized common data for coloring and calls
1604 functions to do Chaitin-Briggs and regional coloring. */
1605 static void
1606 do_coloring (void)
1607 {
1608 coloring_allocno_bitmap = ira_allocate_bitmap ();
1609
1610 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
1611 fprintf (ira_dump_file, "\n**** Allocnos coloring:\n\n");
1612
1613 traverse_loop_tree (FALSE, ira_loop_tree_root, color_pass, NULL);
1614
1615 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1616 print_disposition (ira_dump_file);
1617
1618 ira_free_bitmap (coloring_allocno_bitmap);
1619 }
1620
1621 \f
1622
1623 /* The functions moves spill/restore code, which are to be generated
1624 in ira-emit.c, to less frequent points (if it is profitable) by
1625 reassigning some allocnos (in loop with subloops containing in
1626 another loop) to memory which results in longer live-range where
1627 the corresponding pseudo-registers will be in memory. */
1628 static void
1629 move_spill_restore (void)
1630 {
1631 int cost, changed_p, regno, hard_regno, hard_regno2, index;
1632 int enter_freq, exit_freq;
1633 enum machine_mode mode;
1634 enum reg_class class;
1635 allocno_t a, father_allocno, subloop_allocno;
1636 loop_tree_node_t father, loop_node, subloop_node;
1637 allocno_iterator ai;
1638
1639 for (;;)
1640 {
1641 changed_p = FALSE;
1642 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
1643 fprintf (ira_dump_file, "New iteration of spill/restore move\n");
1644 FOR_EACH_ALLOCNO (a, ai)
1645 {
1646 regno = ALLOCNO_REGNO (a);
1647 loop_node = ALLOCNO_LOOP_TREE_NODE (a);
1648 if (ALLOCNO_CAP_MEMBER (a) != NULL
1649 || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0
1650 || loop_node->children == NULL
1651 /* don't do the optimization because it can create
1652 copies and the reload pass can spill the allocno set
1653 by copy although the allocno will not get memory
1654 slot. */
1655 || reg_equiv_invariant_p[regno]
1656 || reg_equiv_const[regno] != NULL_RTX)
1657 continue;
1658 mode = ALLOCNO_MODE (a);
1659 class = ALLOCNO_COVER_CLASS (a);
1660 index = class_hard_reg_index[class][hard_regno];
1661 ira_assert (index >= 0);
1662 cost = (ALLOCNO_MEMORY_COST (a)
1663 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
1664 ? ALLOCNO_COVER_CLASS_COST (a)
1665 : ALLOCNO_HARD_REG_COSTS (a)[index]));
1666 for (subloop_node = loop_node->children;
1667 subloop_node != NULL;
1668 subloop_node = subloop_node->next)
1669 {
1670 if (subloop_node->bb != NULL)
1671 continue;
1672 subloop_allocno = subloop_node->regno_allocno_map[regno];
1673 if (subloop_allocno == NULL)
1674 continue;
1675 /* We have accumulated cost. To get the real cost of
1676 allocno usage in the loop we should subtract costs of
1677 the subloop allocnos. */
1678 cost -= (ALLOCNO_MEMORY_COST (subloop_allocno)
1679 - (ALLOCNO_HARD_REG_COSTS (subloop_allocno) == NULL
1680 ? ALLOCNO_COVER_CLASS_COST (subloop_allocno)
1681 : ALLOCNO_HARD_REG_COSTS (subloop_allocno)[index]));
1682 exit_freq = loop_edge_freq (subloop_node, regno, TRUE);
1683 enter_freq = loop_edge_freq (subloop_node, regno, FALSE);
1684 if ((hard_regno2 = ALLOCNO_HARD_REGNO (subloop_allocno)) < 0)
1685 cost -= (memory_move_cost[mode][class][0] * exit_freq
1686 + memory_move_cost[mode][class][1] * enter_freq);
1687 else
1688 {
1689 cost += (memory_move_cost[mode][class][0] * exit_freq
1690 + memory_move_cost[mode][class][1] * enter_freq);
1691 if (hard_regno2 != hard_regno)
1692 cost -= (register_move_cost[mode][class][class]
1693 * (exit_freq + enter_freq));
1694 }
1695 }
1696 if ((father = loop_node->father) != NULL
1697 && (father_allocno = father->regno_allocno_map[regno]) != NULL)
1698 {
1699 exit_freq = loop_edge_freq (loop_node, regno, TRUE);
1700 enter_freq = loop_edge_freq (loop_node, regno, FALSE);
1701 if ((hard_regno2 = ALLOCNO_HARD_REGNO (father_allocno)) < 0)
1702 cost -= (memory_move_cost[mode][class][0] * exit_freq
1703 + memory_move_cost[mode][class][1] * enter_freq);
1704 else
1705 {
1706 cost += (memory_move_cost[mode][class][1] * exit_freq
1707 + memory_move_cost[mode][class][0] * enter_freq);
1708 if (hard_regno2 != hard_regno)
1709 cost -= (register_move_cost[mode][class][class]
1710 * (exit_freq + enter_freq));
1711 }
1712 }
1713 if (cost < 0)
1714 {
1715 ALLOCNO_HARD_REGNO (a) = -1;
1716 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1717 {
1718 fprintf
1719 (ira_dump_file,
1720 " Moving spill/restore for a%dr%d up from loop %d",
1721 ALLOCNO_NUM (a), regno, loop_node->loop->num);
1722 fprintf (ira_dump_file, " - profit %d\n", -cost);
1723 }
1724 changed_p = TRUE;
1725 }
1726 }
1727 if (! changed_p)
1728 break;
1729 }
1730 }
1731
1732 \f
1733
1734 /* Update current hard reg costs and current conflict hard reg costs
1735 for allocno A. It is done by processing its copies containing
1736 other allocnos already assigned. */
1737 static void
1738 update_curr_costs (allocno_t a)
1739 {
1740 int i, hard_regno, cost;
1741 enum machine_mode mode;
1742 enum reg_class cover_class, class;
1743 allocno_t another_a;
1744 copy_t cp, next_cp;
1745
1746 ira_assert (! ALLOCNO_ASSIGNED_P (a));
1747 cover_class = ALLOCNO_COVER_CLASS (a);
1748 if (cover_class == NO_REGS)
1749 return;
1750 mode = ALLOCNO_MODE (a);
1751 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
1752 {
1753 if (cp->first == a)
1754 {
1755 next_cp = cp->next_first_allocno_copy;
1756 another_a = cp->second;
1757 }
1758 else if (cp->second == a)
1759 {
1760 next_cp = cp->next_second_allocno_copy;
1761 another_a = cp->first;
1762 }
1763 else
1764 gcc_unreachable ();
1765 if (cover_class != ALLOCNO_COVER_CLASS (another_a)
1766 || ! ALLOCNO_ASSIGNED_P (another_a)
1767 || (hard_regno = ALLOCNO_HARD_REGNO (another_a)) < 0)
1768 continue;
1769 class = REGNO_REG_CLASS (hard_regno);
1770 i = class_hard_reg_index[cover_class][hard_regno];
1771 ira_assert (i >= 0);
1772 cost = (cp->first == a
1773 ? register_move_cost[mode][class][cover_class]
1774 : register_move_cost[mode][cover_class][class]);
1775 allocate_and_set_or_copy_costs
1776 (&ALLOCNO_UPDATED_HARD_REG_COSTS (a),
1777 cover_class, ALLOCNO_COVER_CLASS_COST (a),
1778 ALLOCNO_HARD_REG_COSTS (a));
1779 allocate_and_set_or_copy_costs
1780 (&ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
1781 cover_class, 0, ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
1782 ALLOCNO_UPDATED_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
1783 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a)[i] -= cp->freq * cost;
1784 }
1785 }
1786
1787 /* Map: allocno number -> allocno priority. */
1788 static int *allocno_priorities;
1789
1790 /* Allocate array ALLOCNO_PRIORITIES and set up priorities for N allocnos in
1791 array CONSIDERATION_ALLOCNOS. */
1792 static void
1793 start_allocno_priorities (allocno_t *consideration_allocnos, int n)
1794 {
1795 int i, length;
1796 allocno_t a;
1797 allocno_live_range_t r;
1798
1799 for (i = 0; i < n; i++)
1800 {
1801 a = consideration_allocnos[i];
1802 for (length = 0, r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
1803 length += r->finish - r->start + 1;
1804 if (length == 0)
1805 {
1806 allocno_priorities[ALLOCNO_NUM (a)] = 0;
1807 continue;
1808 }
1809 ira_assert (length > 0 && ALLOCNO_NREFS (a) >= 0);
1810 allocno_priorities[ALLOCNO_NUM (a)]
1811 = (((double) (floor_log2 (ALLOCNO_NREFS (a)) * ALLOCNO_FREQ (a))
1812 / length)
1813 * (10000 / REG_FREQ_MAX) * PSEUDO_REGNO_SIZE (ALLOCNO_REGNO (a)));
1814 }
1815 }
1816
1817 /* The function is used to sort allocnos according to their priorities
1818 which are calculated analogous to ones in file `global.c'. */
1819 static int
1820 allocno_priority_compare_func (const void *v1p, const void *v2p)
1821 {
1822 allocno_t a1 = *(const allocno_t *) v1p, a2 = *(const allocno_t *) v2p;
1823 int pri1, pri2;
1824
1825 pri1 = allocno_priorities[ALLOCNO_NUM (a1)];
1826 pri2 = allocno_priorities[ALLOCNO_NUM (a2)];
1827 if (pri2 - pri1)
1828 return pri2 - pri1;
1829
1830 /* If regs are equally good, sort by allocnos, so that the results of
1831 qsort leave nothing to chance. */
1832 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
1833 }
1834
1835 /* Try to assign hard registers to the unassigned allocnos and
1836 allocnos conflicting with them or conflicting with allocnos whose
1837 regno >= START_REGNO. The function is called after spill/restore
1838 placement optimization and ira_flattening, so more allocnos
1839 (including ones created in ira-emit.c) will have a chance to get a
1840 hard register. We use simple assignment algorithm based on
1841 priorities. */
1842 void
1843 reassign_conflict_allocnos (int start_regno)
1844 {
1845 int i, allocnos_to_color_num;
1846 allocno_t a, conflict_a;
1847 allocno_conflict_iterator aci;
1848 enum reg_class cover_class;
1849 bitmap allocnos_to_color;
1850 allocno_iterator ai;
1851
1852 allocnos_to_color = ira_allocate_bitmap ();
1853 allocnos_to_color_num = 0;
1854 FOR_EACH_ALLOCNO (a, ai)
1855 {
1856 if (! ALLOCNO_ASSIGNED_P (a)
1857 && ! bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (a)))
1858 {
1859 if (ALLOCNO_COVER_CLASS (a) != NO_REGS)
1860 sorted_allocnos[allocnos_to_color_num++] = a;
1861 else
1862 {
1863 ALLOCNO_ASSIGNED_P (a) = TRUE;
1864 ALLOCNO_HARD_REGNO (a) = -1;
1865 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
1866 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
1867 }
1868 bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (a));
1869 }
1870 if (ALLOCNO_REGNO (a) < start_regno
1871 || (cover_class = ALLOCNO_COVER_CLASS (a)) == NO_REGS)
1872 continue;
1873 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
1874 {
1875 ira_assert (cover_class == ALLOCNO_COVER_CLASS (conflict_a));
1876 if (bitmap_bit_p (allocnos_to_color, ALLOCNO_NUM (conflict_a)))
1877 continue;
1878 bitmap_set_bit (allocnos_to_color, ALLOCNO_NUM (conflict_a));
1879 sorted_allocnos[allocnos_to_color_num++] = conflict_a;
1880 }
1881 }
1882 ira_free_bitmap (allocnos_to_color);
1883 if (allocnos_to_color_num > 1)
1884 {
1885 start_allocno_priorities (sorted_allocnos, allocnos_to_color_num);
1886 qsort (sorted_allocnos, allocnos_to_color_num, sizeof (allocno_t),
1887 allocno_priority_compare_func);
1888 }
1889 for (i = 0; i < allocnos_to_color_num; i++)
1890 {
1891 a = sorted_allocnos[i];
1892 ALLOCNO_ASSIGNED_P (a) = FALSE;
1893 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
1894 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
1895 update_curr_costs (a);
1896 }
1897 for (i = 0; i < allocnos_to_color_num; i++)
1898 {
1899 a = sorted_allocnos[i];
1900 if (assign_hard_reg (a, TRUE))
1901 {
1902 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
1903 fprintf
1904 (ira_dump_file,
1905 " Secondary allocation: assign hard reg %d to reg %d\n",
1906 ALLOCNO_HARD_REGNO (a), ALLOCNO_REGNO (a));
1907 }
1908 }
1909 }
1910
1911 \f
1912
1913 /* This page contains code to coalesce memory stack slots used by
1914 spilled allocnos. This results in smaller stack frame, better data
1915 locality, and in smaller code for some architectures like
1916 x86/x86_64 where insn size depends on address displacement value.
1917 On the other hand, it can worsen insn scheduling after the RA but
1918 in practice it is less important than smaller stack frames. */
1919
1920 /* Usage cost and order number of coalesced allocno set to which
1921 given pseudo register belongs to. */
1922 static int *regno_coalesced_allocno_cost;
1923 static int *regno_coalesced_allocno_num;
1924
1925 /* The function is used to sort pseudos according frequencies of
1926 coalesced allocno sets they belong to (putting most frequently ones
1927 first), and according to coalesced allocno set order numbers. */
1928 static int
1929 coalesced_pseudo_reg_freq_compare (const void *v1p, const void *v2p)
1930 {
1931 int regno1 = *(int *) v1p;
1932 int regno2 = *(int *) v2p;
1933 int diff;
1934
1935 if ((diff = (regno_coalesced_allocno_cost[regno2]
1936 - regno_coalesced_allocno_cost[regno1])) != 0)
1937 return diff;
1938 if ((diff = (regno_coalesced_allocno_num[regno1]
1939 - regno_coalesced_allocno_num[regno2])) != 0)
1940 return diff;
1941 return regno1 - regno2;
1942 }
1943
1944 /* Widest width in which each pseudo reg is referred to (via subreg).
1945 It is used for sorting pseudo registers. */
1946 static unsigned int *regno_max_ref_width;
1947
1948 /* The function is used to sort pseudos according their slot numbers
1949 (putting ones with smaller numbers first, or last when the frame
1950 pointer is not needed). */
1951 static int
1952 coalesced_pseudo_reg_slot_compare (const void *v1p, const void *v2p)
1953 {
1954 int regno1 = *(int *) v1p;
1955 int regno2 = *(int *) v2p;
1956 allocno_t a1 = regno_allocno_map[regno1];
1957 allocno_t a2 = regno_allocno_map[regno2];
1958 int diff, slot_num1, slot_num2;
1959 int total_size1, total_size2;
1960
1961 if (a1 == NULL || ALLOCNO_HARD_REGNO (a1) >= 0)
1962 {
1963 if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
1964 return (int *) v1p - (int *) v2p; /* Save the order. */
1965 return 1;
1966 }
1967 else if (a2 == NULL || ALLOCNO_HARD_REGNO (a2) >= 0)
1968 return -1;
1969 slot_num1 = -ALLOCNO_HARD_REGNO (a1);
1970 slot_num2 = -ALLOCNO_HARD_REGNO (a2);
1971 if ((diff = slot_num1 - slot_num2) != 0)
1972 return frame_pointer_needed ? diff : -diff;
1973 total_size1 = MAX (PSEUDO_REGNO_BYTES (regno1), regno_max_ref_width[regno1]);
1974 total_size2 = MAX (PSEUDO_REGNO_BYTES (regno2), regno_max_ref_width[regno2]);
1975 if ((diff = total_size2 - total_size1) != 0)
1976 return diff;
1977 return (int *) v1p - (int *) v2p; /* Save the order. */
1978 }
1979
1980 /* Setup REGNO_COALESCED_ALLOCNO_COST and REGNO_COALESCED_ALLOCNO_NUM
1981 for coalesced allocno sets containing allocnos with their regnos
1982 given in array PSEUDO_REGNOS of length N. */
1983 static void
1984 setup_coalesced_allocno_costs_and_nums (int *pseudo_regnos, int n)
1985 {
1986 int i, num, regno, cost;
1987 allocno_t allocno, a;
1988
1989 for (num = i = 0; i < n; i++)
1990 {
1991 regno = pseudo_regnos[i];
1992 allocno = regno_allocno_map[regno];
1993 if (allocno == NULL)
1994 {
1995 regno_coalesced_allocno_cost[regno] = 0;
1996 regno_coalesced_allocno_num[regno] = ++num;
1997 continue;
1998 }
1999 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
2000 continue;
2001 num++;
2002 for (cost = 0, a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2003 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2004 {
2005 cost += ALLOCNO_FREQ (a);
2006 if (a == allocno)
2007 break;
2008 }
2009 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2010 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2011 {
2012 regno_coalesced_allocno_num[ALLOCNO_REGNO (a)] = num;
2013 regno_coalesced_allocno_cost[ALLOCNO_REGNO (a)] = cost;
2014 if (a == allocno)
2015 break;
2016 }
2017 }
2018 }
2019
2020 /* The function collects spilled allocnos representing coalesced
2021 allocno sets (the first coalesced allocno). The collected allocnos
2022 are returned through array SPILLED_COALESCED_ALLOCNOS. The
2023 function returns the number of the collected allocnos. The
2024 allocnos are given by their regnos in array PSEUDO_REGNOS of length
2025 N. */
2026 static int
2027 collect_spilled_coalesced_allocnos (int *pseudo_regnos, int n,
2028 allocno_t *spilled_coalesced_allocnos)
2029 {
2030 int i, num, regno;
2031 allocno_t allocno;
2032
2033 for (num = i = 0; i < n; i++)
2034 {
2035 regno = pseudo_regnos[i];
2036 allocno = regno_allocno_map[regno];
2037 if (allocno == NULL || ALLOCNO_HARD_REGNO (allocno) >= 0
2038 || ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno)
2039 continue;
2040 spilled_coalesced_allocnos[num++] = allocno;
2041 }
2042 return num;
2043 }
2044
2045 /* We have coalesced allocnos involving in copies. This function
2046 coalesces allocnos further in order to share the same memory stack
2047 slot. Allocnos representing sets of allocnos coalesced before the
2048 call are given in array SPILLED_COALESCED_ALLOCNOS of length NUM.
2049 Return TRUE if some allocnos were coalesced in the function. */
2050 static int
2051 coalesce_spill_slots (allocno_t *spilled_coalesced_allocnos, int num)
2052 {
2053 int i, j;
2054 allocno_t allocno, a;
2055 int merged_p = FALSE;
2056
2057 /* Coalesce non-conflicting spilled allocnos preferring most
2058 frequently used. */
2059 for (i = 0; i < num; i++)
2060 {
2061 allocno = spilled_coalesced_allocnos[i];
2062 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno
2063 || (ALLOCNO_REGNO (allocno) < reg_equiv_len
2064 && (reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)]
2065 || reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX)))
2066 continue;
2067 for (j = 0; j < i; j++)
2068 {
2069 a = spilled_coalesced_allocnos[j];
2070 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) != a
2071 || (ALLOCNO_REGNO (a) < reg_equiv_len
2072 && (reg_equiv_invariant_p[ALLOCNO_REGNO (a)]
2073 || reg_equiv_const[ALLOCNO_REGNO (a)] != NULL_RTX))
2074 || coalesced_allocno_conflict_p (allocno, a, TRUE))
2075 continue;
2076 allocno_coalesced_p = TRUE;
2077 merged_p = TRUE;
2078 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2079 fprintf (ira_dump_file,
2080 " Coalescing spilled allocnos a%dr%d->a%dr%d\n",
2081 ALLOCNO_NUM (allocno), ALLOCNO_REGNO (allocno),
2082 ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
2083 merge_allocnos (a, allocno);
2084 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a);
2085 }
2086 }
2087 return merged_p;
2088 }
2089
2090 /* The function sorts pseudo-register numbers in array PSEUDO_REGNOS
2091 of length N for subsequent assigning stack slots to them in the
2092 reload pass. To do this we coalesce spilled allocnos first to
2093 decrease the number of memory-memory move insns. This function is
2094 called by the reload. */
2095 void
2096 sort_regnos_for_alter_reg (int *pseudo_regnos, int n,
2097 unsigned int *reg_max_ref_width)
2098 {
2099 int max_regno = max_reg_num ();
2100 int i, regno, num, slot_num;
2101 allocno_t allocno, a;
2102 allocno_iterator ai;
2103 allocno_t *spilled_coalesced_allocnos;
2104
2105 processed_coalesced_allocno_bitmap = ira_allocate_bitmap ();
2106 /* Set up allocnos can be coalesced. */
2107 coloring_allocno_bitmap = ira_allocate_bitmap ();
2108 for (i = 0; i < n; i++)
2109 {
2110 regno = pseudo_regnos[i];
2111 allocno = regno_allocno_map[regno];
2112 if (allocno != NULL)
2113 bitmap_set_bit (coloring_allocno_bitmap,
2114 ALLOCNO_NUM (allocno));
2115 }
2116 allocno_coalesced_p = FALSE;
2117 coalesce_allocnos (TRUE);
2118 ira_free_bitmap (coloring_allocno_bitmap);
2119 regno_coalesced_allocno_cost = ira_allocate (max_regno * sizeof (int));
2120 regno_coalesced_allocno_num = ira_allocate (max_regno * sizeof (int));
2121 memset (regno_coalesced_allocno_num, 0, max_regno * sizeof (int));
2122 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
2123 /* Sort regnos according frequencies of the corresponding coalesced
2124 allocno sets. */
2125 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_freq_compare);
2126 spilled_coalesced_allocnos
2127 = ira_allocate (allocnos_num * sizeof (allocno_t));
2128 /* Collect allocnos representing the spilled coalesced allocno
2129 sets. */
2130 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
2131 spilled_coalesced_allocnos);
2132 if (flag_ira_share_spill_slots
2133 && coalesce_spill_slots (spilled_coalesced_allocnos, num))
2134 {
2135 setup_coalesced_allocno_costs_and_nums (pseudo_regnos, n);
2136 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_freq_compare);
2137 num = collect_spilled_coalesced_allocnos (pseudo_regnos, n,
2138 spilled_coalesced_allocnos);
2139 }
2140 ira_free_bitmap (processed_coalesced_allocno_bitmap);
2141 allocno_coalesced_p = FALSE;
2142 /* Assign stack slot numbers to spilled allocno sets, use smaller
2143 numbers for most frequently used coalesced allocnos. -1 is
2144 reserved for dynamic search of stack slots for pseudos spilled by
2145 the reload. */
2146 slot_num = 1;
2147 for (i = 0; i < num; i++)
2148 {
2149 allocno = spilled_coalesced_allocnos[i];
2150 if (ALLOCNO_FIRST_COALESCED_ALLOCNO (allocno) != allocno
2151 || ALLOCNO_HARD_REGNO (allocno) >= 0
2152 || (ALLOCNO_REGNO (allocno) < reg_equiv_len
2153 && (reg_equiv_invariant_p[ALLOCNO_REGNO (allocno)]
2154 || reg_equiv_const[ALLOCNO_REGNO (allocno)] != NULL_RTX)))
2155 continue;
2156 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2157 fprintf (ira_dump_file, " Slot %d (freq,size):", slot_num);
2158 slot_num++;
2159 for (a = ALLOCNO_NEXT_COALESCED_ALLOCNO (allocno);;
2160 a = ALLOCNO_NEXT_COALESCED_ALLOCNO (a))
2161 {
2162 ira_assert (ALLOCNO_HARD_REGNO (a) < 0);
2163 ALLOCNO_HARD_REGNO (a) = -slot_num;
2164 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2165 fprintf (ira_dump_file, " a%dr%d(%d,%d)",
2166 ALLOCNO_NUM (a), ALLOCNO_REGNO (a), ALLOCNO_FREQ (a),
2167 MAX (PSEUDO_REGNO_BYTES (ALLOCNO_REGNO (a)),
2168 reg_max_ref_width[ALLOCNO_REGNO (a)]));
2169
2170 if (a == allocno)
2171 break;
2172 }
2173 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2174 fprintf (ira_dump_file, "\n");
2175 }
2176 spilled_reg_stack_slots_num = slot_num - 1;
2177 ira_free (spilled_coalesced_allocnos);
2178 /* Sort regnos according the slot numbers. */
2179 regno_max_ref_width = reg_max_ref_width;
2180 qsort (pseudo_regnos, n, sizeof (int), coalesced_pseudo_reg_slot_compare);
2181 /* Uncoalesce allocnos which is necessary for (re)assigning during
2182 the reload pass. */
2183 FOR_EACH_ALLOCNO (a, ai)
2184 {
2185 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
2186 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
2187 }
2188 ira_free (regno_coalesced_allocno_num);
2189 ira_free (regno_coalesced_allocno_cost);
2190 }
2191
2192 \f
2193
2194 /* This page contains code used by the reload pass to improve the
2195 final code. */
2196
2197 /* The function is called from the reload pass to mark changes in the
2198 allocation of REGNO made by the reload. Remember that reg_renumber
2199 reflects the change result. */
2200 void
2201 mark_allocation_change (int regno)
2202 {
2203 allocno_t a = regno_allocno_map[regno];
2204 int old_hard_regno, hard_regno, cost;
2205 enum reg_class cover_class = ALLOCNO_COVER_CLASS (a);
2206
2207 ira_assert (a != NULL);
2208 hard_regno = reg_renumber[regno];
2209 if ((old_hard_regno = ALLOCNO_HARD_REGNO (a)) == hard_regno)
2210 return;
2211 if (old_hard_regno < 0)
2212 cost = -ALLOCNO_MEMORY_COST (a);
2213 else
2214 {
2215 ira_assert (class_hard_reg_index[cover_class][old_hard_regno] >= 0);
2216 cost = -(ALLOCNO_HARD_REG_COSTS (a) == NULL
2217 ? ALLOCNO_COVER_CLASS_COST (a)
2218 : ALLOCNO_HARD_REG_COSTS (a)
2219 [class_hard_reg_index[cover_class][old_hard_regno]]);
2220 update_copy_costs (a, FALSE);
2221 }
2222 overall_cost -= cost;
2223 ALLOCNO_HARD_REGNO (a) = hard_regno;
2224 if (hard_regno < 0)
2225 {
2226 ALLOCNO_HARD_REGNO (a) = -1;
2227 cost += ALLOCNO_MEMORY_COST (a);
2228 }
2229 else if (class_hard_reg_index[cover_class][hard_regno] >= 0)
2230 {
2231 cost += (ALLOCNO_HARD_REG_COSTS (a) == NULL
2232 ? ALLOCNO_COVER_CLASS_COST (a)
2233 : ALLOCNO_HARD_REG_COSTS (a)
2234 [class_hard_reg_index[cover_class][hard_regno]]);
2235 update_copy_costs (a, TRUE);
2236 }
2237 else
2238 /* Reload changed class of the allocno. */
2239 cost = 0;
2240 overall_cost += cost;
2241 }
2242
2243 /* This function is called when the reload deletes memory-memory move.
2244 In this case we marks that the allocation of the corresponding
2245 allocnos should be not changed in future. Otherwise we risk to get
2246 a wrong code. */
2247 void
2248 mark_memory_move_deletion (int dst_regno, int src_regno)
2249 {
2250 allocno_t dst = regno_allocno_map[dst_regno];
2251 allocno_t src = regno_allocno_map[src_regno];
2252
2253 ira_assert (dst != NULL && src != NULL
2254 && ALLOCNO_HARD_REGNO (dst) < 0
2255 && ALLOCNO_HARD_REGNO (src) < 0);
2256 ALLOCNO_DONT_REASSIGN_P (dst) = TRUE;
2257 ALLOCNO_DONT_REASSIGN_P (src) = TRUE;
2258 }
2259
2260 /* The function tries to assign a hard register (except for
2261 FORBIDDEN_REGS) to allocno A and return TRUE in the case of
2262 success. That is an analog of retry_global_alloc for IRA. */
2263 static int
2264 allocno_reload_assign (allocno_t a, HARD_REG_SET forbidden_regs)
2265 {
2266 int hard_regno;
2267 enum reg_class cover_class;
2268 int regno = ALLOCNO_REGNO (a);
2269
2270 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), forbidden_regs);
2271 if (! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
2272 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), call_used_reg_set);
2273 ALLOCNO_ASSIGNED_P (a) = FALSE;
2274 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2275 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2276 cover_class = ALLOCNO_COVER_CLASS (a);
2277 update_curr_costs (a);
2278 assign_hard_reg (a, TRUE);
2279 hard_regno = ALLOCNO_HARD_REGNO (a);
2280 reg_renumber[regno] = hard_regno;
2281 if (hard_regno < 0)
2282 ALLOCNO_HARD_REGNO (a) = -1;
2283 else
2284 {
2285 ira_assert (class_hard_reg_index[cover_class][hard_regno] >= 0);
2286 overall_cost -= (ALLOCNO_MEMORY_COST (a)
2287 - (ALLOCNO_HARD_REG_COSTS (a) == NULL
2288 ? ALLOCNO_COVER_CLASS_COST (a)
2289 : ALLOCNO_HARD_REG_COSTS (a)
2290 [class_hard_reg_index[cover_class][hard_regno]]));
2291 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
2292 && ! hard_reg_not_in_set_p (hard_regno, ALLOCNO_MODE (a),
2293 call_used_reg_set))
2294 {
2295 ira_assert (flag_caller_saves);
2296 caller_save_needed = 1;
2297 }
2298 }
2299
2300 /* If we found a hard register, modify the RTL for the pseudo
2301 register to show the hard register, and mark the pseudo register
2302 live. */
2303 if (reg_renumber[regno] >= 0)
2304 {
2305 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2306 fprintf (ira_dump_file, ": reassign to %d\n", reg_renumber[regno]);
2307 SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
2308 mark_home_live (regno);
2309 }
2310 else if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2311 fprintf (ira_dump_file, "\n");
2312
2313 return reg_renumber[regno] >= 0;
2314 }
2315
2316 /* The function is used to sort pseudos according their usage
2317 frequencies (putting most frequently ones first). */
2318 static int
2319 pseudo_reg_compare (const void *v1p, const void *v2p)
2320 {
2321 int regno1 = *(int *) v1p;
2322 int regno2 = *(int *) v2p;
2323 int diff;
2324
2325 if ((diff = REG_FREQ (regno2) - REG_FREQ (regno1)) != 0)
2326 return diff;
2327 return regno1 - regno2;
2328 }
2329
2330 /* The function tries to allocate hard registers to
2331 SPILLED_PSEUDO_REGS (there are NUM of them) or spilled pseudos
2332 conflicting with pseudos in SPILLED_PSEUDO_REGS. It returns TRUE
2333 and update SPILLED, if the allocation has been changed. The
2334 function doesn't use BAD_SPILL_REGS and hard registers in
2335 PSEUDO_FORBIDDEN_REGS and PSEUDO_PREVIOUS_REGS for the
2336 corresponding pseudos. The function is called by the reload pass
2337 at the end of each reload iteration. */
2338 int
2339 reassign_pseudos (int *spilled_pseudo_regs, int num,
2340 HARD_REG_SET bad_spill_regs,
2341 HARD_REG_SET *pseudo_forbidden_regs,
2342 HARD_REG_SET *pseudo_previous_regs, bitmap spilled)
2343 {
2344 int i, m, n, regno, changed_p;
2345 allocno_t a, conflict_a;
2346 HARD_REG_SET forbidden_regs;
2347 allocno_conflict_iterator aci;
2348
2349 if (num > 1)
2350 qsort (spilled_pseudo_regs, num, sizeof (int), pseudo_reg_compare);
2351 changed_p = FALSE;
2352 /* Try to assign hard registers to pseudos from
2353 SPILLED_PSEUDO_REGS. */
2354 for (m = i = 0; i < num; i++)
2355 {
2356 regno = spilled_pseudo_regs[i];
2357 COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
2358 IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]);
2359 IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]);
2360 gcc_assert (reg_renumber[regno] < 0);
2361 a = regno_allocno_map[regno];
2362 mark_allocation_change (regno);
2363 ira_assert (reg_renumber[regno] < 0);
2364 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2365 fprintf (ira_dump_file,
2366 " Spill %d(a%d), cost=%d", regno, ALLOCNO_NUM (a),
2367 ALLOCNO_MEMORY_COST (a)
2368 - ALLOCNO_COVER_CLASS_COST (a));
2369 allocno_reload_assign (a, forbidden_regs);
2370 if (reg_renumber[regno] >= 0)
2371 {
2372 CLEAR_REGNO_REG_SET (spilled, regno);
2373 changed_p = TRUE;
2374 }
2375 else
2376 spilled_pseudo_regs[m++] = regno;
2377 }
2378 if (m == 0)
2379 return changed_p;
2380 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2381 {
2382 fprintf (ira_dump_file, " Spilled regs");
2383 for (i = 0; i < m; i++)
2384 fprintf (ira_dump_file, " %d", spilled_pseudo_regs[i]);
2385 fprintf (ira_dump_file, "\n");
2386 }
2387 /* Try to assign hard registers to pseudos conflicting with ones
2388 from SPILLED_PSEUDO_REGS. */
2389 for (i = n = 0; i < m; i++)
2390 {
2391 regno = spilled_pseudo_regs[i];
2392 a = regno_allocno_map[regno];
2393 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
2394 if (ALLOCNO_HARD_REGNO (conflict_a) < 0
2395 && ! ALLOCNO_DONT_REASSIGN_P (conflict_a)
2396 && ! bitmap_bit_p (consideration_allocno_bitmap,
2397 ALLOCNO_NUM (conflict_a)))
2398 {
2399 sorted_allocnos[n++] = conflict_a;
2400 bitmap_set_bit (consideration_allocno_bitmap,
2401 ALLOCNO_NUM (conflict_a));
2402 }
2403 }
2404 if (n != 0)
2405 {
2406 start_allocno_priorities (sorted_allocnos, n);
2407 qsort (sorted_allocnos, n, sizeof (allocno_t),
2408 allocno_priority_compare_func);
2409 for (i = 0; i < n; i++)
2410 {
2411 a = sorted_allocnos[i];
2412 regno = ALLOCNO_REGNO (a);
2413 COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
2414 IOR_HARD_REG_SET (forbidden_regs, pseudo_forbidden_regs[regno]);
2415 IOR_HARD_REG_SET (forbidden_regs, pseudo_previous_regs[regno]);
2416 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
2417 fprintf (ira_dump_file,
2418 " Try assign %d(a%d), cost=%d",
2419 regno, ALLOCNO_NUM (a),
2420 ALLOCNO_MEMORY_COST (a)
2421 - ALLOCNO_COVER_CLASS_COST (a));
2422 if (allocno_reload_assign (a, forbidden_regs))
2423 {
2424 changed_p = TRUE;
2425 bitmap_clear_bit (spilled, regno);
2426 }
2427 }
2428 }
2429 return changed_p;
2430 }
2431
2432 /* The function is called by the reload pass and returns already
2433 allocated stack slot (if any) for REGNO with given INHERENT_SIZE
2434 and TOTAL_SIZE. In the case of failure to find a slot which can be
2435 used for REGNO, the function returns NULL. */
2436 rtx
2437 reuse_stack_slot (int regno, unsigned int inherent_size,
2438 unsigned int total_size)
2439 {
2440 unsigned int i;
2441 int slot_num, best_slot_num;
2442 int cost, best_cost;
2443 copy_t cp, next_cp;
2444 allocno_t another_allocno, allocno = regno_allocno_map[regno];
2445 rtx x;
2446 bitmap_iterator bi;
2447 struct spilled_reg_stack_slot *slot = NULL;
2448
2449 ira_assert (flag_ira && inherent_size == PSEUDO_REGNO_BYTES (regno)
2450 && inherent_size <= total_size
2451 && ALLOCNO_HARD_REGNO (allocno) < 0);
2452 if (! flag_ira_share_spill_slots)
2453 return NULL_RTX;
2454 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
2455 if (slot_num != -1)
2456 {
2457 slot = &spilled_reg_stack_slots[slot_num];
2458 x = slot->mem;
2459 }
2460 else
2461 {
2462 best_cost = best_slot_num = -1;
2463 x = NULL_RTX;
2464 /* It means that the pseudo was spilled in the reload pass, try
2465 to reuse a slot. */
2466 for (slot_num = 0; slot_num < spilled_reg_stack_slots_num; slot_num++)
2467 {
2468 slot = &spilled_reg_stack_slots[slot_num];
2469 if (slot->mem == NULL_RTX)
2470 continue;
2471 if (slot->width < total_size
2472 || GET_MODE_SIZE (GET_MODE (slot->mem)) < inherent_size)
2473 continue;
2474
2475 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
2476 FIRST_PSEUDO_REGISTER, i, bi)
2477 {
2478 another_allocno = regno_allocno_map[i];
2479 if (allocno_live_ranges_intersect_p (allocno, another_allocno))
2480 goto cont;
2481 }
2482 for (cost = 0, cp = ALLOCNO_COPIES (allocno);
2483 cp != NULL;
2484 cp = next_cp)
2485 {
2486 if (cp->first == allocno)
2487 {
2488 next_cp = cp->next_first_allocno_copy;
2489 another_allocno = cp->second;
2490 }
2491 else if (cp->second == allocno)
2492 {
2493 next_cp = cp->next_second_allocno_copy;
2494 another_allocno = cp->first;
2495 }
2496 else
2497 gcc_unreachable ();
2498 if (cp->insn == NULL_RTX)
2499 continue;
2500 if (bitmap_bit_p (&slot->spilled_regs,
2501 ALLOCNO_REGNO (another_allocno)))
2502 cost += cp->freq;
2503 }
2504 if (cost > best_cost)
2505 {
2506 best_cost = cost;
2507 best_slot_num = slot_num;
2508 }
2509 cont:
2510 ;
2511 }
2512 if (best_cost >= 0)
2513 {
2514 slot = &spilled_reg_stack_slots[best_slot_num];
2515 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
2516 x = slot->mem;
2517 ALLOCNO_HARD_REGNO (allocno) = -best_slot_num - 2;
2518 }
2519 }
2520 if (x != NULL_RTX)
2521 {
2522 ira_assert (slot->width >= total_size);
2523 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
2524 FIRST_PSEUDO_REGISTER, i, bi)
2525 {
2526 ira_assert (! pseudo_live_ranges_intersect_p (regno, i));
2527 }
2528 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
2529 if (internal_flag_ira_verbose > 3 && ira_dump_file)
2530 {
2531 fprintf (ira_dump_file, " Assigning %d(freq=%d) slot %d of",
2532 regno, REG_FREQ (regno), slot_num);
2533 EXECUTE_IF_SET_IN_BITMAP (&slot->spilled_regs,
2534 FIRST_PSEUDO_REGISTER, i, bi)
2535 {
2536 if ((unsigned) regno != i)
2537 fprintf (ira_dump_file, " %d", i);
2538 }
2539 fprintf (ira_dump_file, "\n");
2540 }
2541 }
2542 return x;
2543 }
2544
2545 /* The function is called by the reload pass every time when a new
2546 stack slot X with TOTAL_SIZE was allocated for REGNO. We store
2547 this info for subsequent reuse_stack_slot calls. */
2548 void
2549 mark_new_stack_slot (rtx x, int regno, unsigned int total_size)
2550 {
2551 struct spilled_reg_stack_slot *slot;
2552 int slot_num;
2553 allocno_t allocno;
2554
2555 ira_assert (flag_ira && PSEUDO_REGNO_BYTES (regno) <= total_size);
2556 allocno = regno_allocno_map[regno];
2557 slot_num = -ALLOCNO_HARD_REGNO (allocno) - 2;
2558 if (slot_num == -1)
2559 {
2560 slot_num = spilled_reg_stack_slots_num++;
2561 ALLOCNO_HARD_REGNO (allocno) = -slot_num - 2;
2562 }
2563 slot = &spilled_reg_stack_slots[slot_num];
2564 INIT_REG_SET (&slot->spilled_regs);
2565 SET_REGNO_REG_SET (&slot->spilled_regs, regno);
2566 slot->mem = x;
2567 slot->width = total_size;
2568 if (internal_flag_ira_verbose > 3 && ira_dump_file)
2569 fprintf (ira_dump_file, " Assigning %d(freq=%d) a new slot %d\n",
2570 regno, REG_FREQ (regno), slot_num);
2571 }
2572
2573
2574 /* Return spill cost for pseudo-registers whose numbers are in array
2575 REGNOS (with a negative number as an end marker) for reload with
2576 given IN and OUT for INSN. Return also number points (through
2577 EXCESS_PRESSURE_LIVE_LENGTH) where the pseudo-register lives and
2578 the register pressure is high, number of references of the
2579 pseudo-registers (through NREFS), number of callee-clobbered
2580 hard-registers occupied by the pseudo-registers (through
2581 CALL_USED_COUNT), and the first hard regno occupied by the
2582 pseudo-registers (through FIRST_HARD_REGNO). */
2583 static int
2584 calculate_spill_cost (int *regnos, rtx in, rtx out, rtx insn,
2585 int *excess_pressure_live_length,
2586 int *nrefs, int *call_used_count, int *first_hard_regno)
2587 {
2588 int i, cost, regno, hard_regno, j, count, saved_cost, nregs, in_p, out_p;
2589 int length;
2590 allocno_t a;
2591
2592 *nrefs = 0;
2593 for (length = count = cost = i = 0;; i++)
2594 {
2595 regno = regnos[i];
2596 if (regno < 0)
2597 break;
2598 *nrefs += REG_N_REFS (regno);
2599 hard_regno = reg_renumber[regno];
2600 ira_assert (hard_regno >= 0);
2601 a = regno_allocno_map[regno];
2602 length += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2603 cost += ALLOCNO_MEMORY_COST (a) - ALLOCNO_COVER_CLASS_COST (a);
2604 nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
2605 for (j = 0; j < nregs; j++)
2606 if (! TEST_HARD_REG_BIT (call_used_reg_set, hard_regno + j))
2607 break;
2608 if (j == nregs)
2609 count++;
2610 in_p = in && REG_P (in) && (int) REGNO (in) == hard_regno;
2611 out_p = out && REG_P (out) && (int) REGNO (out) == hard_regno;
2612 if ((in_p || out_p)
2613 && find_regno_note (insn, REG_DEAD, hard_regno) != NULL_RTX)
2614 {
2615 saved_cost = 0;
2616 if (in_p)
2617 saved_cost += memory_move_cost
2618 [ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)][1];
2619 if (out_p)
2620 saved_cost
2621 += memory_move_cost
2622 [ALLOCNO_MODE (a)][ALLOCNO_COVER_CLASS (a)][0];
2623 cost -= REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)) * saved_cost;
2624 }
2625 }
2626 *excess_pressure_live_length = length;
2627 *call_used_count = count;
2628 hard_regno = -1;
2629 if (regnos[0] >= 0)
2630 {
2631 hard_regno = reg_renumber[regnos[0]];
2632 }
2633 *first_hard_regno = hard_regno;
2634 return cost;
2635 }
2636
2637 /* Return TRUE if spilling pseudo-registers whose numbers are in array
2638 REGNOS is better than spilling pseudo-registers with numbers in
2639 OTHER_REGNOS for reload with given IN and OUT for INSN. The
2640 function used by the reload pass to make better register spilling
2641 decisions. */
2642 int
2643 better_spill_reload_regno_p (int *regnos, int *other_regnos,
2644 rtx in, rtx out, rtx insn)
2645 {
2646 int cost, other_cost;
2647 int length, other_length;
2648 int nrefs, other_nrefs;
2649 int call_used_count, other_call_used_count;
2650 int hard_regno, other_hard_regno;
2651
2652 cost = calculate_spill_cost (regnos, in, out, insn,
2653 &length, &nrefs, &call_used_count, &hard_regno);
2654 other_cost = calculate_spill_cost (other_regnos, in, out, insn,
2655 &other_length, &other_nrefs,
2656 &other_call_used_count,
2657 &other_hard_regno);
2658 if (cost != other_cost)
2659 return cost < other_cost;
2660 if (length != other_length)
2661 return length > other_length;
2662 #ifdef REG_ALLOC_ORDER
2663 if (hard_regno >= 0 && other_hard_regno >= 0)
2664 return (inv_reg_alloc_order[hard_regno]
2665 < inv_reg_alloc_order[other_hard_regno]);
2666 #else
2667 if (call_used_count != other_call_used_count)
2668 return call_used_count > other_call_used_count;
2669 #endif
2670 return FALSE;
2671 }
2672
2673 \f
2674
2675 /* The function returns (through CALL_CLOBBERED_REGS) hard registers
2676 changed by all function calls inside REGNO live range. The
2677 function is used to improve code for saving/restore callee-clobbered
2678 hard registers around calls (see caller-saves.c). */
2679 void
2680 collect_pseudo_call_clobbered_regs (int regno,
2681 HARD_REG_SET (*call_clobbered_regs))
2682 {
2683 int i;
2684 allocno_t a;
2685 HARD_REG_SET clobbered_regs;
2686 rtx call, *allocno_calls;
2687
2688 a = regno_allocno_map[regno];
2689 CLEAR_HARD_REG_SET (*call_clobbered_regs);
2690 allocno_calls = (VEC_address (rtx, regno_calls[regno])
2691 + ALLOCNO_CALLS_CROSSED_START (a));
2692 for (i = ALLOCNO_CALLS_CROSSED_NUM (a) - 1; i >= 0; i--)
2693 {
2694 call = allocno_calls[i];
2695 get_call_invalidated_used_regs (call, &clobbered_regs, FALSE);
2696 IOR_HARD_REG_SET (*call_clobbered_regs, clobbered_regs);
2697 }
2698 }
2699
2700 \f
2701
2702 /* Allocate and initialize data necessary for assign_hard_reg. */
2703 void
2704 initiate_ira_assign (void)
2705 {
2706 sorted_allocnos = ira_allocate (sizeof (allocno_t) * allocnos_num);
2707 sorted_allocnos_for_spilling
2708 = ira_allocate (sizeof (allocno_t) * allocnos_num);
2709 consideration_allocno_bitmap = ira_allocate_bitmap ();
2710 initiate_cost_update ();
2711 allocno_priorities = ira_allocate (sizeof (int) * allocnos_num);
2712 }
2713
2714 /* Deallocate data used by assign_hard_reg. */
2715 void
2716 finish_ira_assign (void)
2717 {
2718 ira_free (sorted_allocnos_for_spilling);
2719 ira_free (sorted_allocnos);
2720 ira_free_bitmap (consideration_allocno_bitmap);
2721 finish_cost_update ();
2722 ira_free (allocno_priorities);
2723 }
2724
2725 \f
2726
2727 /* Entry function doing color-based register allocation. */
2728 void
2729 ira_color (void)
2730 {
2731 VARRAY_GENERIC_PTR_NOGC_INIT (allocno_stack_varray, allocnos_num,
2732 "stack of allocnos");
2733 memset (allocated_hardreg_p, 0, sizeof (allocated_hardreg_p));
2734 initiate_ira_assign ();
2735 do_coloring ();
2736 finish_ira_assign ();
2737 VARRAY_FREE (allocno_stack_varray);
2738 move_spill_restore ();
2739 }
Mirror of the offical gcc git repository hosted at gcc.gnu.org