1 /* Allocate registers for pseudo-registers that span basic blocks.
2 Copyright (C) 1987, 1988, 1991, 1994, 1996, 1997, 1998,
3 1999, 2000, 2002, 2003, 2004, 2005, 2006, 2007
4 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
25 #include "coretypes.h"
28 #include "hard-reg-set.h"
34 #include "insn-config.h"
39 #include "tree-pass.h"
46 /* This pass of the compiler performs global register allocation.
47 It assigns hard register numbers to all the pseudo registers
48 that were not handled in local_alloc. Assignments are recorded
49 in the vector reg_renumber, not by changing the rtl code.
50 (Such changes are made by final). The entry point is
51 the function global_alloc.
53 After allocation is complete, the reload pass is run as a subroutine
54 of this pass, so that when a pseudo reg loses its hard reg due to
55 spilling it is possible to make a second attempt to find a hard
56 reg for it. The reload pass is independent in other respects
57 and it is run even when stupid register allocation is in use.
59 1. Assign allocation-numbers (allocnos) to the pseudo-registers
60 still needing allocations and to the pseudo-registers currently
61 allocated by local-alloc which may be spilled by reload.
62 Set up tables reg_allocno and allocno_reg to map
63 reg numbers to allocnos and vice versa.
64 max_allocno gets the number of allocnos in use.
66 2. Allocate a max_allocno by max_allocno compressed triangular conflict
67 bit matrix (a triangular bit matrix with portions removed for which we
68 can guarantee there are no conflicts, example: two local pseudos that
69 live in different basic blocks) and clear it. This is called "conflict".
70 Note that for triangular bit matrices, there are two possible equations
71 for computing the bit number for two allocnos: LOW and HIGH (LOW < HIGH):
73 1) BITNUM = f(HIGH) + LOW, where
74 f(HIGH) = (HIGH * (HIGH - 1)) / 2
76 2) BITNUM = f(LOW) + HIGH, where
77 f(LOW) = LOW * (max_allocno - LOW) + (LOW * (LOW - 1)) / 2 - LOW - 1
79 We use the second (and less common) equation as this gives us better
80 cache locality for local allocnos that are live within the same basic
81 block. Also note that f(HIGH) and f(LOW) can be precalculated for all
82 values of HIGH and LOW, so all that is necessary to compute the bit
83 number for two allocnos LOW and HIGH is a load followed by an addition.
85 Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix for
86 conflicts between allocnos and explicit hard register use (which
87 includes use of pseudo-registers allocated by local_alloc). This
88 is the hard_reg_conflicts inside each allocno.
90 3. For each basic block, walk backward through the block, recording
91 which pseudo-registers and which hardware registers are live.
92 Build the conflict matrix between the pseudo-registers and another of
93 pseudo-registers versus hardware registers.
95 4. For each basic block, walk backward through the block, recording
96 the preferred hardware registers for each pseudo-register.
98 5. Sort a table of the allocnos into order of desirability of the variables.
100 6. Allocate the variables in that order; each if possible into
101 a preferred register, else into another register. */
103 /* A vector of the integers from 0 to max_allocno-1,
104 sorted in the order of first-to-be-allocated first. */
106 static int *allocno_order;
108 /* Set of registers that global-alloc isn't supposed to use. */
110 static HARD_REG_SET no_global_alloc_regs;
112 /* Set of registers used so far. */
114 static HARD_REG_SET regs_used_so_far;
116 /* Number of refs to each hard reg, as used by local alloc.
117 It is zero for a reg that contains global pseudos or is explicitly used. */
119 static int local_reg_n_refs[FIRST_PSEUDO_REGISTER];
121 /* Frequency of uses of given hard reg. */
122 static int local_reg_freq[FIRST_PSEUDO_REGISTER];
124 /* Guess at live length of each hard reg, as used by local alloc.
125 This is actually the sum of the live lengths of the specific regs. */
127 static int local_reg_live_length[FIRST_PSEUDO_REGISTER];
129 /* Set to 1 a bit in a vector TABLE of HARD_REG_SETs, for vector
130 element I, and hard register number J. */
132 #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (allocno[I].TABLE, J)
134 /* This is turned off because it doesn't work right for DImode.
135 (And it is only used for DImode, so the other cases are worthless.)
136 The problem is that it isn't true that there is NO possibility of conflict;
137 only that there is no conflict if the two pseudos get the exact same regs.
138 If they were allocated with a partial overlap, there would be a conflict.
139 We can't safely turn off the conflict unless we have another way to
140 prevent the partial overlap.
142 Idea: change hard_reg_conflicts so that instead of recording which
143 hard regs the allocno may not overlap, it records where the allocno
144 may not start. Change both where it is used and where it is updated.
145 Then there is a way to record that (reg:DI 108) may start at 10
146 but not at 9 or 11. There is still the question of how to record
147 this semi-conflict between two pseudos. */
149 /* Reg pairs for which conflict after the current insn
150 is inhibited by a REG_NO_CONFLICT note.
151 If the table gets full, we ignore any other notes--that is conservative. */
152 #define NUM_NO_CONFLICT_PAIRS 4
153 /* Number of pairs in use in this insn. */
154 int n_no_conflict_pairs;
155 static struct { int allocno1, allocno2;}
156 no_conflict_pairs[NUM_NO_CONFLICT_PAIRS];
159 /* Return true if *LOC contains an asm. */
162 insn_contains_asm_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
166 if (GET_CODE (*loc) == ASM_OPERANDS)
172 /* Return true if INSN contains an ASM. */
175 insn_contains_asm (rtx insn)
177 return for_each_rtx (&insn, insn_contains_asm_1, NULL);
182 compute_regs_asm_clobbered (char *regs_asm_clobbered)
186 memset (regs_asm_clobbered, 0, sizeof (char) * FIRST_PSEUDO_REGISTER);
191 FOR_BB_INSNS_REVERSE (bb, insn)
193 struct df_ref **def_rec;
194 if (insn_contains_asm (insn))
195 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
197 struct df_ref *def = *def_rec;
198 unsigned int dregno = DF_REF_REGNO (def);
199 if (dregno < FIRST_PSEUDO_REGISTER)
202 enum machine_mode mode = GET_MODE (DF_REF_REAL_REG (def));
203 unsigned int end = dregno
204 + hard_regno_nregs[dregno][mode] - 1;
205 for (i = dregno; i <= end; ++i)
206 regs_asm_clobbered[i] = 1;
214 /* All registers that can be eliminated. */
216 static HARD_REG_SET eliminable_regset;
218 static int regno_compare (const void *, const void *);
219 static int allocno_compare (const void *, const void *);
220 static void expand_preferences (void);
221 static void prune_preferences (void);
222 static void set_preferences (void);
223 static void find_reg (int, HARD_REG_SET, int, int, int);
224 static void dump_conflicts (FILE *);
225 static void build_insn_chain (void);
228 /* Look through the list of eliminable registers. Set ELIM_SET to the
229 set of registers which may be eliminated. Set NO_GLOBAL_SET to the
230 set of registers which may not be used across blocks.
232 This will normally be called with ELIM_SET as the file static
233 variable eliminable_regset, and NO_GLOBAL_SET as the file static
234 variable NO_GLOBAL_ALLOC_REGS. */
237 compute_regsets (HARD_REG_SET *elim_set,
238 HARD_REG_SET *no_global_set)
241 /* Like regs_ever_live, but 1 if a reg is set or clobbered from an asm.
242 Unlike regs_ever_live, elements of this array corresponding to
243 eliminable regs like the frame pointer are set if an asm sets them. */
244 char *regs_asm_clobbered = alloca (FIRST_PSEUDO_REGISTER * sizeof (char));
246 #ifdef ELIMINABLE_REGS
247 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
251 = (! flag_omit_frame_pointer
252 || (current_function_calls_alloca && EXIT_IGNORE_STACK)
253 || FRAME_POINTER_REQUIRED);
255 max_regno = max_reg_num ();
260 /* A machine may have certain hard registers that
261 are safe to use only within a basic block. */
263 CLEAR_HARD_REG_SET (*no_global_set);
264 CLEAR_HARD_REG_SET (*elim_set);
266 compute_regs_asm_clobbered (regs_asm_clobbered);
267 /* Build the regset of all eliminable registers and show we can't use those
268 that we already know won't be eliminated. */
269 #ifdef ELIMINABLE_REGS
270 for (i = 0; i < ARRAY_SIZE (eliminables); i++)
273 = (! CAN_ELIMINATE (eliminables[i].from, eliminables[i].to)
274 || (eliminables[i].to == STACK_POINTER_REGNUM && need_fp));
276 if (!regs_asm_clobbered[eliminables[i].from])
278 SET_HARD_REG_BIT (*elim_set, eliminables[i].from);
281 SET_HARD_REG_BIT (*no_global_set, eliminables[i].from);
283 else if (cannot_elim)
284 error ("%s cannot be used in asm here",
285 reg_names[eliminables[i].from]);
287 df_set_regs_ever_live (eliminables[i].from, true);
289 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
290 if (!regs_asm_clobbered[HARD_FRAME_POINTER_REGNUM])
292 SET_HARD_REG_BIT (*elim_set, HARD_FRAME_POINTER_REGNUM);
294 SET_HARD_REG_BIT (*no_global_set, HARD_FRAME_POINTER_REGNUM);
297 error ("%s cannot be used in asm here",
298 reg_names[HARD_FRAME_POINTER_REGNUM]);
300 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM, true);
304 if (!regs_asm_clobbered[FRAME_POINTER_REGNUM])
306 SET_HARD_REG_BIT (*elim_set, FRAME_POINTER_REGNUM);
308 SET_HARD_REG_BIT (*no_global_set, FRAME_POINTER_REGNUM);
311 error ("%s cannot be used in asm here", reg_names[FRAME_POINTER_REGNUM]);
313 df_set_regs_ever_live (FRAME_POINTER_REGNUM, true);
317 /* Perform allocation of pseudo-registers not allocated by local_alloc.
319 Return value is nonzero if reload failed
320 and we must not do any more for this function. */
328 int *num_allocnos_per_blk;
330 compute_regsets (&eliminable_regset, &no_global_alloc_regs);
332 /* Track which registers have already been used. Start with registers
333 explicitly in the rtl, then registers allocated by local register
336 CLEAR_HARD_REG_SET (regs_used_so_far);
337 #ifdef LEAF_REGISTERS
338 /* If we are doing the leaf function optimization, and this is a leaf
339 function, it means that the registers that take work to save are those
340 that need a register window. So prefer the ones that can be used in
343 const char *cheap_regs;
344 const char *const leaf_regs = LEAF_REGISTERS;
346 if (only_leaf_regs_used () && leaf_function_p ())
347 cheap_regs = leaf_regs;
349 cheap_regs = call_used_regs;
350 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
351 if (df_regs_ever_live_p (i) || cheap_regs[i])
352 SET_HARD_REG_BIT (regs_used_so_far, i);
355 /* We consider registers that do not have to be saved over calls as if
356 they were already used since there is no cost in using them. */
357 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
358 if (df_regs_ever_live_p (i) || call_used_regs[i])
359 SET_HARD_REG_BIT (regs_used_so_far, i);
362 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
363 if (reg_renumber[i] >= 0)
364 SET_HARD_REG_BIT (regs_used_so_far, reg_renumber[i]);
366 /* Establish mappings from register number to allocation number
367 and vice versa. In the process, count the allocnos. */
369 reg_allocno = XNEWVEC (int, max_regno);
371 /* Initially fill the reg_allocno array with regno's... */
374 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
375 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
376 that we are supposed to refrain from putting in a hard reg.
377 -2 means do make an allocno but don't allocate it. */
378 if (REG_N_REFS (i) != 0 && REG_LIVE_LENGTH (i) != -1
379 /* Don't allocate pseudos that cross calls,
380 if this function receives a nonlocal goto. */
381 && (! current_function_has_nonlocal_label
382 || REG_N_CALLS_CROSSED (i) == 0))
384 int blk = regno_basic_block (i);
385 reg_allocno[max_allocno++] = i;
388 gcc_assert (REG_LIVE_LENGTH (i));
391 allocno = XCNEWVEC (struct allocno, max_allocno);
392 partial_bitnum = XNEWVEC (HOST_WIDE_INT, max_allocno);
393 num_allocnos_per_blk = XCNEWVEC (int, max_blk + 1);
395 /* ...so we can sort them in the order we want them to receive
397 qsort (reg_allocno, max_allocno, sizeof (int), regno_compare);
399 for (i = 0; i < (size_t) max_allocno; i++)
401 int regno = reg_allocno[i];
402 int blk = regno_basic_block (regno);
403 num_allocnos_per_blk[blk]++;
404 allocno[i].reg = regno;
405 allocno[i].size = PSEUDO_REGNO_SIZE (regno);
406 allocno[i].calls_crossed += REG_N_CALLS_CROSSED (regno);
407 allocno[i].freq_calls_crossed += REG_FREQ_CALLS_CROSSED (regno);
408 allocno[i].throwing_calls_crossed
409 += REG_N_THROWING_CALLS_CROSSED (regno);
410 allocno[i].n_refs += REG_N_REFS (regno);
411 allocno[i].freq += REG_FREQ (regno);
412 if (allocno[i].live_length < REG_LIVE_LENGTH (regno))
413 allocno[i].live_length = REG_LIVE_LENGTH (regno);
416 /* The "global" block must contain all allocnos. */
417 num_allocnos_per_blk[0] = max_allocno;
419 /* Now reinitialize the reg_allocno array in terms of the
420 optimized regno to allocno mapping we created above. */
421 for (i = 0; i < (size_t) max_regno; i++)
425 for (i = 0; i < (size_t) max_allocno; i++)
427 int regno = allocno[i].reg;
428 int blk = regno_basic_block (regno);
429 int row_size = --num_allocnos_per_blk[blk];
430 reg_allocno[regno] = (int) i;
431 partial_bitnum[i] = (row_size > 0) ? max_bitnum - ((int) i + 1) : -1;
432 max_bitnum += row_size;
435 #ifdef ENABLE_CHECKING
436 gcc_assert (max_bitnum <=
437 (((HOST_WIDE_INT) max_allocno *
438 ((HOST_WIDE_INT) max_allocno - 1)) / 2));
443 HOST_WIDE_INT num_bits, num_bytes, actual_bytes;
445 fprintf (dump_file, "## max_blk: %d\n", max_blk);
446 fprintf (dump_file, "## max_regno: %d\n", max_regno);
447 fprintf (dump_file, "## max_allocno: %d\n", max_allocno);
449 num_bits = max_bitnum;
450 num_bytes = CEIL (num_bits, 8);
451 actual_bytes = num_bytes;
452 fprintf (dump_file, "## Compressed triangular bitmatrix size: ");
453 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC " bits, ", num_bits);
454 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC " bytes\n", num_bytes);
456 num_bits = ((HOST_WIDE_INT) max_allocno *
457 ((HOST_WIDE_INT) max_allocno - 1)) / 2;
458 num_bytes = CEIL (num_bits, 8);
459 fprintf (dump_file, "## Standard triangular bitmatrix size: ");
460 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC " bits, ", num_bits);
461 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC " bytes [%.2f%%]\n",
462 num_bytes, 100.0 * ((double) actual_bytes / (double) num_bytes));
464 num_bits = (HOST_WIDE_INT) max_allocno * (HOST_WIDE_INT) max_allocno;
465 num_bytes = CEIL (num_bits, 8);
466 fprintf (dump_file, "## Square bitmatrix size: ");
467 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC " bits, ", num_bits);
468 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC " bytes [%.2f%%]\n",
469 num_bytes, 100.0 * ((double) actual_bytes / (double) num_bytes));
472 /* Calculate amount of usage of each hard reg by pseudos
473 allocated by local-alloc. This is to see if we want to
475 memset (local_reg_live_length, 0, sizeof local_reg_live_length);
476 memset (local_reg_n_refs, 0, sizeof local_reg_n_refs);
477 memset (local_reg_freq, 0, sizeof local_reg_freq);
478 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
479 if (reg_renumber[i] >= 0)
481 int regno = reg_renumber[i];
482 int endregno = end_hard_regno (PSEUDO_REGNO_MODE (i), regno);
485 for (j = regno; j < endregno; j++)
487 local_reg_n_refs[j] += REG_N_REFS (i);
488 local_reg_freq[j] += REG_FREQ (i);
489 local_reg_live_length[j] += REG_LIVE_LENGTH (i);
493 /* We can't override local-alloc for a reg used not just by local-alloc. */
494 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
495 if (df_regs_ever_live_p (i))
496 local_reg_n_refs[i] = 0, local_reg_freq[i] = 0;
500 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
502 fprintf (dump_file, "%d REG_N_REFS=%d, REG_FREQ=%d, REG_LIVE_LENGTH=%d\n",
503 (int)i, REG_N_REFS (i), REG_FREQ (i), REG_LIVE_LENGTH (i));
505 fprintf (dump_file, "regs_ever_live =");
506 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
507 if (df_regs_ever_live_p (i))
508 fprintf (dump_file, " %d", (int)i);
509 fprintf (dump_file, "\n");
514 adjacency_pool = NULL;
516 /* If there is work to be done (at least one reg to allocate),
517 perform global conflict analysis and allocate the regs. */
521 /* We used to use alloca here, but the size of what it would try to
522 allocate would occasionally cause it to exceed the stack limit and
523 cause unpredictable core dumps. Some examples were > 2Mb in size. */
524 conflicts = XCNEWVEC (HOST_WIDEST_FAST_INT,
525 CEIL(max_bitnum, HOST_BITS_PER_WIDEST_FAST_INT));
527 adjacency = XCNEWVEC (adjacency_t *, max_allocno);
528 adjacency_pool = create_alloc_pool ("global_alloc adjacency list pool",
529 sizeof (adjacency_t), 1024);
531 /* Scan all the insns and compute the conflicts among allocnos
532 and between allocnos and hard regs. */
536 /* There is just too much going on in the register allocators to
537 keep things up to date. At the end we have to rescan anyway
538 because things change when the reload_completed flag is set.
539 So we just turn off scanning and we will rescan by hand.
541 However, we needed to do the rescanning before this point to
542 get the new insns scanned inserted by local_alloc scanned for
544 df_set_flags (DF_NO_INSN_RESCAN);
546 /* Eliminate conflicts between pseudos and eliminable registers. If
547 the register is not eliminated, the pseudo won't really be able to
548 live in the eliminable register, so the conflict doesn't matter.
549 If we do eliminate the register, the conflict will no longer exist.
550 So in either case, we can ignore the conflict. Likewise for
555 for (i = 0; i < (size_t) max_allocno; i++)
557 AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_conflicts,
559 AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_copy_preferences,
561 AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_preferences,
565 /* Try to expand the preferences by merging them between allocnos. */
567 expand_preferences ();
569 /* Determine the order to allocate the remaining pseudo registers. */
571 allocno_order = XNEWVEC (int, max_allocno);
572 for (i = 0; i < (size_t) max_allocno; i++)
573 allocno_order[i] = i;
575 /* Default the size to 1, since allocno_compare uses it to divide by.
576 Also convert allocno_live_length of zero to -1. A length of zero
577 can occur when all the registers for that allocno have reg_live_length
578 equal to -2. In this case, we want to make an allocno, but not
579 allocate it. So avoid the divide-by-zero and set it to a low
582 for (i = 0; i < (size_t) max_allocno; i++)
584 if (allocno[i].size == 0)
586 if (allocno[i].live_length == 0)
587 allocno[i].live_length = -1;
590 qsort (allocno_order, max_allocno, sizeof (int), allocno_compare);
592 prune_preferences ();
595 dump_conflicts (dump_file);
597 /* Try allocating them, one by one, in that order,
598 except for parameters marked with reg_live_length[regno] == -2. */
600 for (i = 0; i < (size_t) max_allocno; i++)
601 if (reg_renumber[allocno[allocno_order[i]].reg] < 0
602 && REG_LIVE_LENGTH (allocno[allocno_order[i]].reg) >= 0)
604 if (!dbg_cnt (global_alloc_at_reg))
606 /* If we have more than one register class,
607 first try allocating in the class that is cheapest
608 for this pseudo-reg. If that fails, try any reg. */
609 if (N_REG_CLASSES > 1)
611 find_reg (allocno_order[i], 0, 0, 0, 0);
612 if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
615 if (reg_alternate_class (allocno[allocno_order[i]].reg) != NO_REGS)
616 find_reg (allocno_order[i], 0, 1, 0, 0);
619 free (allocno_order);
623 /* Do the reloads now while the allocno data still exists, so that we can
624 try to assign new hard regs to any pseudo regs that are spilled. */
626 #if 0 /* We need to eliminate regs even if there is no rtl code,
627 for the sake of debugging information. */
628 if (n_basic_blocks > NUM_FIXED_BLOCKS)
632 retval = reload (get_insns (), 1);
637 free (num_allocnos_per_blk);
638 free (partial_bitnum);
640 if (adjacency != NULL)
642 free_alloc_pool (adjacency_pool);
649 /* Sort predicate for ordering the regnos. We want the regno to allocno
650 mapping to have the property that all "global" regnos (ie, regnos that
651 are referenced in more than one basic block) have smaller allocno values
652 than "local" regnos (ie, regnos referenced in only one basic block).
653 In addition, for two basic blocks "i" and "j" with i < j, all regnos
654 local to basic block i should have smaller allocno values than regnos
655 local to basic block j.
656 Returns -1 (1) if *v1p should be allocated before (after) *v2p. */
659 regno_compare (const void *v1p, const void *v2p)
661 int regno1 = *(const int *)v1p;
662 int regno2 = *(const int *)v2p;
663 int blk1 = REG_BASIC_BLOCK (regno1);
664 int blk2 = REG_BASIC_BLOCK (regno2);
666 /* Prefer lower numbered basic blocks. Note that global and unknown
667 blocks have negative values, giving them high precedence. */
671 /* If both regs are referenced from the same block, sort by regno. */
672 return regno1 - regno2;
675 /* Sort predicate for ordering the allocnos.
676 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
679 allocno_compare (const void *v1p, const void *v2p)
681 int v1 = *(const int *)v1p, v2 = *(const int *)v2p;
682 /* Note that the quotient will never be bigger than
683 the value of floor_log2 times the maximum number of
684 times a register can occur in one insn (surely less than 100)
685 weighted by the frequency (maximally REG_FREQ_MAX).
686 Multiplying this by 10000/REG_FREQ_MAX can't overflow. */
688 = (((double) (floor_log2 (allocno[v1].n_refs) * allocno[v1].freq)
689 / allocno[v1].live_length)
690 * (10000 / REG_FREQ_MAX) * allocno[v1].size);
692 = (((double) (floor_log2 (allocno[v2].n_refs) * allocno[v2].freq)
693 / allocno[v2].live_length)
694 * (10000 / REG_FREQ_MAX) * allocno[v2].size);
698 /* If regs are equally good, sort by allocno,
699 so that the results of qsort leave nothing to chance. */
703 /* Expand the preference information by looking for cases where one allocno
704 dies in an insn that sets an allocno. If those two allocnos don't conflict,
705 merge any preferences between those allocnos. */
708 expand_preferences (void)
714 /* We only try to handle the most common cases here. Most of the cases
715 where this wins are reg-reg copies. */
717 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
719 && (set = single_set (insn)) != 0
720 && REG_P (SET_DEST (set))
721 && reg_allocno[REGNO (SET_DEST (set))] >= 0)
722 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
723 if (REG_NOTE_KIND (link) == REG_DEAD
724 && REG_P (XEXP (link, 0))
725 && reg_allocno[REGNO (XEXP (link, 0))] >= 0
726 && ! conflict_p (reg_allocno[REGNO (SET_DEST (set))],
727 reg_allocno[REGNO (XEXP (link, 0))]))
729 int a1 = reg_allocno[REGNO (SET_DEST (set))];
730 int a2 = reg_allocno[REGNO (XEXP (link, 0))];
732 if (XEXP (link, 0) == SET_SRC (set))
734 IOR_HARD_REG_SET (allocno[a1].hard_reg_copy_preferences,
735 allocno[a2].hard_reg_copy_preferences);
736 IOR_HARD_REG_SET (allocno[a2].hard_reg_copy_preferences,
737 allocno[a1].hard_reg_copy_preferences);
740 IOR_HARD_REG_SET (allocno[a1].hard_reg_preferences,
741 allocno[a2].hard_reg_preferences);
742 IOR_HARD_REG_SET (allocno[a2].hard_reg_preferences,
743 allocno[a1].hard_reg_preferences);
744 IOR_HARD_REG_SET (allocno[a1].hard_reg_full_preferences,
745 allocno[a2].hard_reg_full_preferences);
746 IOR_HARD_REG_SET (allocno[a2].hard_reg_full_preferences,
747 allocno[a1].hard_reg_full_preferences);
752 /* Try to set a preference for an allocno to a hard register.
753 We are passed DEST and SRC which are the operands of a SET. It is known
754 that SRC is a register. If SRC or the first operand of SRC is a register,
755 try to set a preference. If one of the two is a hard register and the other
756 is a pseudo-register, mark the preference.
758 Note that we are not as aggressive as local-alloc in trying to tie a
759 pseudo-register to a hard register. */
762 set_preference (rtx dest, rtx src)
764 unsigned int src_regno, dest_regno, end_regno;
765 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
766 to compensate for subregs in SRC or DEST. */
771 if (GET_RTX_FORMAT (GET_CODE (src))[0] == 'e')
772 src = XEXP (src, 0), copy = 0;
774 /* Get the reg number for both SRC and DEST.
775 If neither is a reg, give up. */
778 src_regno = REGNO (src);
779 else if (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src)))
781 src_regno = REGNO (SUBREG_REG (src));
783 if (REGNO (SUBREG_REG (src)) < FIRST_PSEUDO_REGISTER)
784 offset += subreg_regno_offset (REGNO (SUBREG_REG (src)),
785 GET_MODE (SUBREG_REG (src)),
789 offset += (SUBREG_BYTE (src)
790 / REGMODE_NATURAL_SIZE (GET_MODE (src)));
796 dest_regno = REGNO (dest);
797 else if (GET_CODE (dest) == SUBREG && REG_P (SUBREG_REG (dest)))
799 dest_regno = REGNO (SUBREG_REG (dest));
801 if (REGNO (SUBREG_REG (dest)) < FIRST_PSEUDO_REGISTER)
802 offset -= subreg_regno_offset (REGNO (SUBREG_REG (dest)),
803 GET_MODE (SUBREG_REG (dest)),
807 offset -= (SUBREG_BYTE (dest)
808 / REGMODE_NATURAL_SIZE (GET_MODE (dest)));
813 /* Convert either or both to hard reg numbers. */
815 if (reg_renumber[src_regno] >= 0)
816 src_regno = reg_renumber[src_regno];
818 if (reg_renumber[dest_regno] >= 0)
819 dest_regno = reg_renumber[dest_regno];
821 /* Now if one is a hard reg and the other is a global pseudo
822 then give the other a preference. */
824 if (dest_regno < FIRST_PSEUDO_REGISTER && src_regno >= FIRST_PSEUDO_REGISTER
825 && reg_allocno[src_regno] >= 0)
827 dest_regno -= offset;
828 if (dest_regno < FIRST_PSEUDO_REGISTER)
831 SET_REGBIT (hard_reg_copy_preferences,
832 reg_allocno[src_regno], dest_regno);
834 SET_REGBIT (hard_reg_preferences,
835 reg_allocno[src_regno], dest_regno);
836 end_regno = end_hard_regno (GET_MODE (dest), dest_regno);
837 for (i = dest_regno; i < end_regno; i++)
838 SET_REGBIT (hard_reg_full_preferences, reg_allocno[src_regno], i);
842 if (src_regno < FIRST_PSEUDO_REGISTER && dest_regno >= FIRST_PSEUDO_REGISTER
843 && reg_allocno[dest_regno] >= 0)
846 if (src_regno < FIRST_PSEUDO_REGISTER)
849 SET_REGBIT (hard_reg_copy_preferences,
850 reg_allocno[dest_regno], src_regno);
852 SET_REGBIT (hard_reg_preferences,
853 reg_allocno[dest_regno], src_regno);
854 end_regno = end_hard_regno (GET_MODE (src), src_regno);
855 for (i = src_regno; i < end_regno; i++)
856 SET_REGBIT (hard_reg_full_preferences, reg_allocno[dest_regno], i);
861 /* Helper function for set_preferences. */
863 set_preferences_1 (rtx reg, const_rtx setter, void *data ATTRIBUTE_UNUSED)
865 if (GET_CODE (reg) == SUBREG)
866 reg = SUBREG_REG (reg);
872 if (GET_CODE (setter) != CLOBBER)
873 set_preference (reg, SET_SRC (setter));
876 /* Scan all of the insns and initialize the preferences. */
879 set_preferences (void)
884 FOR_BB_INSNS_REVERSE (bb, insn)
889 note_stores (PATTERN (insn), set_preferences_1, NULL);
895 /* Prune the preferences for global registers to exclude registers that cannot
898 Compute `regs_someone_prefers', which is a bitmask of the hard registers
899 that are preferred by conflicting registers of lower priority. If possible,
900 we will avoid using these registers. */
903 prune_preferences (void)
907 int *allocno_to_order = XNEWVEC (int, max_allocno);
909 /* Scan least most important to most important.
910 For each allocno, remove from preferences registers that cannot be used,
911 either because of conflicts or register type. Then compute all registers
912 preferred by each lower-priority register that conflicts. */
914 for (i = max_allocno - 1; i >= 0; i--)
918 num = allocno_order[i];
919 allocno_to_order[num] = i;
920 COPY_HARD_REG_SET (temp, allocno[num].hard_reg_conflicts);
922 if (allocno[num].calls_crossed == 0)
923 IOR_HARD_REG_SET (temp, fixed_reg_set);
925 IOR_HARD_REG_SET (temp, call_used_reg_set);
927 IOR_COMPL_HARD_REG_SET
929 reg_class_contents[(int) reg_preferred_class (allocno[num].reg)]);
931 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_preferences, temp);
932 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_copy_preferences, temp);
933 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_full_preferences, temp);
936 for (i = max_allocno - 1; i >= 0; i--)
938 /* Merge in the preferences of lower-priority registers (they have
939 already been pruned). If we also prefer some of those registers,
940 don't exclude them unless we are of a smaller size (in which case
941 we want to give the lower-priority allocno the first chance for
943 HARD_REG_SET temp, temp2;
947 num = allocno_order[i];
949 CLEAR_HARD_REG_SET (temp);
950 CLEAR_HARD_REG_SET (temp2);
952 FOR_EACH_CONFLICT (num, allocno2, ai)
954 if (allocno_to_order[allocno2] > i)
956 if (allocno[allocno2].size <= allocno[num].size)
957 IOR_HARD_REG_SET (temp,
958 allocno[allocno2].hard_reg_full_preferences);
960 IOR_HARD_REG_SET (temp2,
961 allocno[allocno2].hard_reg_full_preferences);
965 AND_COMPL_HARD_REG_SET (temp, allocno[num].hard_reg_full_preferences);
966 IOR_HARD_REG_SET (temp, temp2);
967 COPY_HARD_REG_SET (allocno[num].regs_someone_prefers, temp);
969 free (allocno_to_order);
972 /* Assign a hard register to allocno NUM; look for one that is the beginning
973 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
974 The registers marked in PREFREGS are tried first.
976 LOSERS, if nonzero, is a HARD_REG_SET indicating registers that cannot
977 be used for this allocation.
979 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
980 Otherwise ignore that preferred class and use the alternate class.
982 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
983 will have to be saved and restored at calls.
985 RETRYING is nonzero if this is called from retry_global_alloc.
987 If we find one, record it in reg_renumber.
988 If not, do nothing. */
991 find_reg (int num, HARD_REG_SET losers, int alt_regs_p, int accept_call_clobbered, int retrying)
993 int i, best_reg, pass;
994 HARD_REG_SET used, used1, used2;
996 enum reg_class class = (alt_regs_p
997 ? reg_alternate_class (allocno[num].reg)
998 : reg_preferred_class (allocno[num].reg));
999 enum machine_mode mode = PSEUDO_REGNO_MODE (allocno[num].reg);
1001 if (accept_call_clobbered)
1002 COPY_HARD_REG_SET (used1, call_fixed_reg_set);
1003 else if (allocno[num].calls_crossed == 0)
1004 COPY_HARD_REG_SET (used1, fixed_reg_set);
1006 COPY_HARD_REG_SET (used1, call_used_reg_set);
1008 /* Some registers should not be allocated in global-alloc. */
1009 IOR_HARD_REG_SET (used1, no_global_alloc_regs);
1011 IOR_HARD_REG_SET (used1, losers);
1013 IOR_COMPL_HARD_REG_SET (used1, reg_class_contents[(int) class]);
1014 COPY_HARD_REG_SET (used2, used1);
1016 IOR_HARD_REG_SET (used1, allocno[num].hard_reg_conflicts);
1018 #ifdef CANNOT_CHANGE_MODE_CLASS
1019 cannot_change_mode_set_regs (&used1, mode, allocno[num].reg);
1022 /* Try each hard reg to see if it fits. Do this in two passes.
1023 In the first pass, skip registers that are preferred by some other pseudo
1024 to give it a better chance of getting one of those registers. Only if
1025 we can't get a register when excluding those do we take one of them.
1026 However, we never allocate a register for the first time in pass 0. */
1028 COPY_HARD_REG_SET (used, used1);
1029 IOR_COMPL_HARD_REG_SET (used, regs_used_so_far);
1030 IOR_HARD_REG_SET (used, allocno[num].regs_someone_prefers);
1033 for (i = FIRST_PSEUDO_REGISTER, pass = 0;
1034 pass <= 1 && i >= FIRST_PSEUDO_REGISTER;
1038 COPY_HARD_REG_SET (used, used1);
1039 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1041 #ifdef REG_ALLOC_ORDER
1042 int regno = reg_alloc_order[i];
1046 if (! TEST_HARD_REG_BIT (used, regno)
1047 && HARD_REGNO_MODE_OK (regno, mode)
1048 && (allocno[num].calls_crossed == 0
1049 || accept_call_clobbered
1050 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
1053 int lim = end_hard_regno (mode, regno);
1056 && ! TEST_HARD_REG_BIT (used, j));
1063 #ifndef REG_ALLOC_ORDER
1064 i = j; /* Skip starting points we know will lose */
1070 /* See if there is a preferred register with the same class as the register
1071 we allocated above. Making this restriction prevents register
1072 preferencing from creating worse register allocation.
1074 Remove from the preferred registers and conflicting registers. Note that
1075 additional conflicts may have been added after `prune_preferences' was
1078 First do this for those register with copy preferences, then all
1079 preferred registers. */
1081 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_copy_preferences, used);
1082 if (!hard_reg_set_empty_p (allocno[num].hard_reg_copy_preferences)
1085 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1086 if (TEST_HARD_REG_BIT (allocno[num].hard_reg_copy_preferences, i)
1087 && HARD_REGNO_MODE_OK (i, mode)
1088 && (allocno[num].calls_crossed == 0
1089 || accept_call_clobbered
1090 || ! HARD_REGNO_CALL_PART_CLOBBERED (i, mode))
1091 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1092 || reg_class_subset_p (REGNO_REG_CLASS (i),
1093 REGNO_REG_CLASS (best_reg))
1094 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1095 REGNO_REG_CLASS (i))))
1098 int lim = end_hard_regno (mode, i);
1101 && ! TEST_HARD_REG_BIT (used, j)
1102 && (REGNO_REG_CLASS (j)
1103 == REGNO_REG_CLASS (best_reg + (j - i))
1104 || reg_class_subset_p (REGNO_REG_CLASS (j),
1105 REGNO_REG_CLASS (best_reg + (j - i)))
1106 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1107 REGNO_REG_CLASS (j))));
1117 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_preferences, used);
1118 if (!hard_reg_set_empty_p (allocno[num].hard_reg_preferences)
1121 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1122 if (TEST_HARD_REG_BIT (allocno[num].hard_reg_preferences, i)
1123 && HARD_REGNO_MODE_OK (i, mode)
1124 && (allocno[num].calls_crossed == 0
1125 || accept_call_clobbered
1126 || ! HARD_REGNO_CALL_PART_CLOBBERED (i, mode))
1127 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1128 || reg_class_subset_p (REGNO_REG_CLASS (i),
1129 REGNO_REG_CLASS (best_reg))
1130 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1131 REGNO_REG_CLASS (i))))
1134 int lim = end_hard_regno (mode, i);
1137 && ! TEST_HARD_REG_BIT (used, j)
1138 && (REGNO_REG_CLASS (j)
1139 == REGNO_REG_CLASS (best_reg + (j - i))
1140 || reg_class_subset_p (REGNO_REG_CLASS (j),
1141 REGNO_REG_CLASS (best_reg + (j - i)))
1142 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1143 REGNO_REG_CLASS (j))));
1154 /* If we haven't succeeded yet, try with caller-saves.
1155 We need not check to see if the current function has nonlocal
1156 labels because we don't put any pseudos that are live over calls in
1157 registers in that case. */
1159 if (flag_caller_saves && best_reg < 0)
1161 /* Did not find a register. If it would be profitable to
1162 allocate a call-clobbered register and save and restore it
1163 around calls, do that. Don't do this if it crosses any calls
1164 that might throw. */
1165 if (! accept_call_clobbered
1166 && allocno[num].calls_crossed != 0
1167 && allocno[num].throwing_calls_crossed == 0
1168 && CALLER_SAVE_PROFITABLE (optimize_size ? allocno[num].n_refs : allocno[num].freq,
1169 optimize_size ? allocno[num].calls_crossed
1170 : allocno[num].freq_calls_crossed))
1172 HARD_REG_SET new_losers;
1174 CLEAR_HARD_REG_SET (new_losers);
1176 COPY_HARD_REG_SET (new_losers, losers);
1178 IOR_HARD_REG_SET(new_losers, losing_caller_save_reg_set);
1179 find_reg (num, new_losers, alt_regs_p, 1, retrying);
1180 if (reg_renumber[allocno[num].reg] >= 0)
1182 caller_save_needed = 1;
1188 /* If we haven't succeeded yet,
1189 see if some hard reg that conflicts with us
1190 was utilized poorly by local-alloc.
1191 If so, kick out the regs that were put there by local-alloc
1192 so we can use it instead. */
1193 if (best_reg < 0 && !retrying
1194 /* Let's not bother with multi-reg allocnos. */
1195 && allocno[num].size == 1
1196 && REG_BASIC_BLOCK (allocno[num].reg) == REG_BLOCK_GLOBAL)
1198 /* Count from the end, to find the least-used ones first. */
1199 for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1201 #ifdef REG_ALLOC_ORDER
1202 int regno = reg_alloc_order[i];
1207 if (local_reg_n_refs[regno] != 0
1208 /* Don't use a reg no good for this pseudo. */
1209 && ! TEST_HARD_REG_BIT (used2, regno)
1210 && HARD_REGNO_MODE_OK (regno, mode)
1211 /* The code below assumes that we need only a single
1212 register, but the check of allocno[num].size above
1213 was not enough. Sometimes we need more than one
1214 register for a single-word value. */
1215 && hard_regno_nregs[regno][mode] == 1
1216 && (allocno[num].calls_crossed == 0
1217 || accept_call_clobbered
1218 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode))
1219 #ifdef CANNOT_CHANGE_MODE_CLASS
1220 && ! invalid_mode_change_p (regno, REGNO_REG_CLASS (regno),
1224 && (!allocno[num].no_stack_reg
1225 || regno < FIRST_STACK_REG || regno > LAST_STACK_REG)
1229 /* We explicitly evaluate the divide results into temporary
1230 variables so as to avoid excess precision problems that occur
1231 on an i386-unknown-sysv4.2 (unixware) host. */
1233 double tmp1 = ((double) local_reg_freq[regno] * local_reg_n_refs[regno]
1234 / local_reg_live_length[regno]);
1235 double tmp2 = ((double) allocno[num].freq * allocno[num].n_refs
1236 / allocno[num].live_length);
1240 /* Hard reg REGNO was used less in total by local regs
1241 than it would be used by this one allocno! */
1245 fprintf (dump_file, "Regno %d better for global %d, ",
1246 regno, allocno[num].reg);
1247 fprintf (dump_file, "fr:%d, ll:%d, nr:%d ",
1248 allocno[num].freq, allocno[num].live_length,
1249 allocno[num].n_refs);
1250 fprintf (dump_file, "(was: fr:%d, ll:%d, nr:%d)\n",
1251 local_reg_freq[regno],
1252 local_reg_live_length[regno],
1253 local_reg_n_refs[regno]);
1256 for (k = 0; k < max_regno; k++)
1257 if (reg_renumber[k] >= 0)
1259 int r = reg_renumber[k];
1261 = end_hard_regno (PSEUDO_REGNO_MODE (k), r);
1263 if (regno >= r && regno < endregno)
1267 "Local Reg %d now on stack\n", k);
1268 reg_renumber[k] = -1;
1279 /* Did we find a register? */
1284 HARD_REG_SET this_reg;
1287 /* Yes. Record it as the hard register of this pseudo-reg. */
1288 reg_renumber[allocno[num].reg] = best_reg;
1290 /* Make a set of the hard regs being allocated. */
1291 CLEAR_HARD_REG_SET (this_reg);
1292 lim = end_hard_regno (mode, best_reg);
1293 for (j = best_reg; j < lim; j++)
1295 SET_HARD_REG_BIT (this_reg, j);
1296 SET_HARD_REG_BIT (regs_used_so_far, j);
1297 /* This is no longer a reg used just by local regs. */
1298 local_reg_n_refs[j] = 0;
1299 local_reg_freq[j] = 0;
1301 /* For each other pseudo-reg conflicting with this one,
1302 mark it as conflicting with the hard regs this one occupies. */
1303 FOR_EACH_CONFLICT (num, j, ai)
1305 IOR_HARD_REG_SET (allocno[j].hard_reg_conflicts, this_reg);
1310 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1311 Perhaps it had previously seemed not worth a hard reg,
1312 or perhaps its old hard reg has been commandeered for reloads.
1313 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1314 they do not appear to be allocated.
1315 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1318 retry_global_alloc (int regno, HARD_REG_SET forbidden_regs)
1320 int alloc_no = reg_allocno[regno];
1323 /* If we have more than one register class,
1324 first try allocating in the class that is cheapest
1325 for this pseudo-reg. If that fails, try any reg. */
1326 if (N_REG_CLASSES > 1)
1327 find_reg (alloc_no, forbidden_regs, 0, 0, 1);
1328 if (reg_renumber[regno] < 0
1329 && reg_alternate_class (regno) != NO_REGS)
1330 find_reg (alloc_no, forbidden_regs, 1, 0, 1);
1332 /* If we found a register, modify the RTL for the register to
1333 show the hard register, and mark that register live. */
1334 if (reg_renumber[regno] >= 0)
1336 SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
1337 mark_home_live (regno);
1342 /* Indicate that hard register number FROM was eliminated and replaced with
1343 an offset from hard register number TO. The status of hard registers live
1344 at the start of a basic block is updated by replacing a use of FROM with
1348 mark_elimination (int from, int to)
1354 regset r = DF_LIVE_IN (bb);
1355 if (REGNO_REG_SET_P (r, from))
1357 CLEAR_REGNO_REG_SET (r, from);
1358 SET_REGNO_REG_SET (r, to);
1363 /* Print chain C to FILE. */
1366 print_insn_chain (FILE *file, struct insn_chain *c)
1368 fprintf (file, "insn=%d, ", INSN_UID(c->insn));
1369 bitmap_print (file, &c->live_throughout, "live_throughout: ", ", ");
1370 bitmap_print (file, &c->dead_or_set, "dead_or_set: ", "\n");
1374 /* Print all reload_insn_chains to FILE. */
1377 print_insn_chains (FILE *file)
1379 struct insn_chain *c;
1380 for (c = reload_insn_chain; c ; c = c->next)
1381 print_insn_chain (file, c);
1385 /* Walk the insns of the current function and build reload_insn_chain,
1386 and record register life information. */
1389 build_insn_chain (void)
1392 struct insn_chain **p = &reload_insn_chain;
1394 struct insn_chain *c = NULL;
1395 struct insn_chain *next = NULL;
1396 bitmap live_relevant_regs = BITMAP_ALLOC (NULL);
1397 bitmap elim_regset = BITMAP_ALLOC (NULL);
1398 /* live_subregs is a vector used to keep accurate information about
1399 which hardregs are live in multiword pseudos. live_subregs and
1400 live_subregs_used are indexed by pseudo number. The live_subreg
1401 entry for a particular pseudo is only used if the corresponding
1402 element is non zero in live_subregs_used. The value in
1403 live_subregs_used is number of bytes that the pseudo can
1405 sbitmap *live_subregs = XCNEWVEC (sbitmap, max_regno);
1406 int *live_subregs_used = XNEWVEC (int, max_regno);
1408 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1409 if (TEST_HARD_REG_BIT (eliminable_regset, i))
1410 bitmap_set_bit (elim_regset, i);
1412 FOR_EACH_BB_REVERSE (bb)
1417 CLEAR_REG_SET (live_relevant_regs);
1418 memset (live_subregs_used, 0, max_regno * sizeof (int));
1420 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb), 0, i, bi)
1422 if (i >= FIRST_PSEUDO_REGISTER)
1424 bitmap_set_bit (live_relevant_regs, i);
1427 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb), FIRST_PSEUDO_REGISTER, i, bi)
1429 if (reg_renumber[i] >= 0)
1430 bitmap_set_bit (live_relevant_regs, i);
1433 FOR_BB_INSNS_REVERSE (bb, insn)
1435 if (!NOTE_P (insn) && !BARRIER_P (insn))
1437 unsigned int uid = INSN_UID (insn);
1438 struct df_ref **def_rec;
1439 struct df_ref **use_rec;
1441 c = new_insn_chain ();
1448 c->block = bb->index;
1451 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1453 struct df_ref *def = *def_rec;
1454 unsigned int regno = DF_REF_REGNO (def);
1456 /* Ignore may clobbers because these are generated
1457 from calls. However, every other kind of def is
1458 added to dead_or_set. */
1459 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1461 if (regno < FIRST_PSEUDO_REGISTER)
1463 if (!fixed_regs[regno])
1464 bitmap_set_bit (&c->dead_or_set, regno);
1466 else if (reg_renumber[regno] >= 0)
1467 bitmap_set_bit (&c->dead_or_set, regno);
1470 if ((regno < FIRST_PSEUDO_REGISTER || reg_renumber[regno] >= 0)
1471 && (!DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)))
1473 rtx reg = DF_REF_REG (def);
1475 /* We can model subregs, but not if they are
1476 wrapped in ZERO_EXTRACTS. */
1477 if (GET_CODE (reg) == SUBREG
1478 && !DF_REF_FLAGS_IS_SET (def, DF_REF_EXTRACT))
1480 unsigned int start = SUBREG_BYTE (reg);
1481 unsigned int last = start
1482 + GET_MODE_SIZE (GET_MODE (reg));
1484 ra_init_live_subregs (bitmap_bit_p (live_relevant_regs,
1489 /* Ignore the paradoxical bits. */
1490 if ((int)last > live_subregs_used[regno])
1491 last = live_subregs_used[regno];
1493 while (start < last)
1495 RESET_BIT (live_subregs[regno], start);
1499 if (sbitmap_empty_p (live_subregs[regno]))
1501 live_subregs_used[regno] = 0;
1502 bitmap_clear_bit (live_relevant_regs, regno);
1505 /* Set live_relevant_regs here because
1506 that bit has to be true to get us to
1507 look at the live_subregs fields. */
1508 bitmap_set_bit (live_relevant_regs, regno);
1512 /* DF_REF_PARTIAL is generated for
1513 subregs, STRICT_LOW_PART, and
1514 ZERO_EXTRACT. We handle the subreg
1515 case above so here we have to keep from
1516 modeling the def as a killing def. */
1517 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL))
1519 bitmap_clear_bit (live_relevant_regs, regno);
1520 live_subregs_used[regno] = 0;
1526 bitmap_and_compl_into (live_relevant_regs, elim_regset);
1527 bitmap_copy (&c->live_throughout, live_relevant_regs);
1530 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
1532 struct df_ref *use = *use_rec;
1533 unsigned int regno = DF_REF_REGNO (use);
1534 rtx reg = DF_REF_REG (use);
1536 /* DF_REF_READ_WRITE on a use means that this use
1537 is fabricated from a def that is a partial set
1538 to a multiword reg. Here, we only model the
1539 subreg case that is not wrapped in ZERO_EXTRACT
1540 precisely so we do not need to look at the
1542 if (DF_REF_FLAGS_IS_SET (use, DF_REF_READ_WRITE)
1543 && !DF_REF_FLAGS_IS_SET (use, DF_REF_EXTRACT)
1544 && DF_REF_FLAGS_IS_SET (use, DF_REF_SUBREG))
1547 /* Add the last use of each var to dead_or_set. */
1548 if (!bitmap_bit_p (live_relevant_regs, regno))
1550 if (regno < FIRST_PSEUDO_REGISTER)
1552 if (!fixed_regs[regno])
1553 bitmap_set_bit (&c->dead_or_set, regno);
1555 else if (reg_renumber[regno] >= 0)
1556 bitmap_set_bit (&c->dead_or_set, regno);
1559 if (regno < FIRST_PSEUDO_REGISTER || reg_renumber[regno] >= 0)
1561 if (GET_CODE (reg) == SUBREG
1562 && !DF_REF_FLAGS_IS_SET (use, DF_REF_EXTRACT))
1564 unsigned int start = SUBREG_BYTE (reg);
1565 unsigned int last = start
1566 + GET_MODE_SIZE (GET_MODE (reg));
1568 ra_init_live_subregs (bitmap_bit_p (live_relevant_regs,
1574 /* Ignore the paradoxical bits. */
1575 if ((int)last > live_subregs_used[regno])
1576 last = live_subregs_used[regno];
1578 while (start < last)
1580 SET_BIT (live_subregs[regno], start);
1585 /* Resetting the live_subregs_used is
1586 effectively saying do not use the subregs
1587 because we are reading the whole
1589 live_subregs_used[regno] = 0;
1590 bitmap_set_bit (live_relevant_regs, regno);
1596 /* FIXME!! The following code is a disaster. Reload needs to see the
1597 labels and jump tables that are just hanging out in between
1598 the basic blocks. See pr33676. */
1599 insn = BB_HEAD (bb);
1601 /* Skip over the barriers and cruft. */
1602 while (insn && (BARRIER_P (insn) || NOTE_P (insn)
1603 || BLOCK_FOR_INSN (insn) == bb))
1604 insn = PREV_INSN (insn);
1606 /* While we add anything except barriers and notes, the focus is
1607 to get the labels and jump tables into the
1608 reload_insn_chain. */
1611 if (!NOTE_P (insn) && !BARRIER_P (insn))
1613 if (BLOCK_FOR_INSN (insn))
1616 c = new_insn_chain ();
1622 /* The block makes no sense here, but it is what the old
1624 c->block = bb->index;
1626 bitmap_copy (&c->live_throughout, live_relevant_regs);
1628 insn = PREV_INSN (insn);
1632 for (i = 0; i < (unsigned int) max_regno; i++)
1633 if (live_subregs[i])
1634 free (live_subregs[i]);
1636 reload_insn_chain = c;
1639 free (live_subregs);
1640 free (live_subregs_used);
1641 BITMAP_FREE (live_relevant_regs);
1642 BITMAP_FREE (elim_regset);
1645 print_insn_chains (dump_file);
1648 /* Print debugging trace information if -dg switch is given,
1649 showing the information on which the allocation decisions are based. */
1652 dump_conflicts (FILE *file)
1656 int has_preferences;
1659 for (i = 0; i < max_allocno; i++)
1661 if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
1665 fprintf (file, ";; %d regs to allocate:", nregs);
1666 for (regno = 0; regno < max_regno; regno++)
1667 if ((i = reg_allocno[regno]) >= 0)
1670 if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
1672 fprintf (file, " %d", allocno[allocno_order[i]].reg);
1673 for (j = 0; j < max_regno; j++)
1674 if (reg_allocno[j] == allocno_order[i]
1675 && j != allocno[allocno_order[i]].reg)
1676 fprintf (file, "+%d", j);
1677 if (allocno[allocno_order[i]].size != 1)
1678 fprintf (file, " (%d)", allocno[allocno_order[i]].size);
1680 fprintf (file, "\n");
1682 for (regno = 0; regno < max_regno; regno++)
1683 if ((i = reg_allocno[regno]) >= 0)
1687 fprintf (file, ";; %d conflicts:", allocno[i].reg);
1688 FOR_EACH_CONFLICT (i, j, ai)
1690 fprintf (file, " %d", allocno[j].reg);
1692 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1693 if (TEST_HARD_REG_BIT (allocno[i].hard_reg_conflicts, j)
1695 fprintf (file, " %d", j);
1696 fprintf (file, "\n");
1698 has_preferences = 0;
1699 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1700 if (TEST_HARD_REG_BIT (allocno[i].hard_reg_preferences, j))
1701 has_preferences = 1;
1703 if (!has_preferences)
1705 fprintf (file, ";; %d preferences:", allocno[i].reg);
1706 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1707 if (TEST_HARD_REG_BIT (allocno[i].hard_reg_preferences, j))
1708 fprintf (file, " %d", j);
1709 fprintf (file, "\n");
1711 fprintf (file, "\n");
1715 dump_global_regs (FILE *file)
1719 fprintf (file, ";; Register dispositions:\n");
1720 for (i = FIRST_PSEUDO_REGISTER, j = 0; i < max_regno; i++)
1721 if (reg_renumber[i] >= 0)
1723 fprintf (file, "%d in %d ", i, reg_renumber[i]);
1725 fprintf (file, "\n");
1728 fprintf (file, "\n\n;; Hard regs used: ");
1729 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1730 if (df_regs_ever_live_p (i))
1731 fprintf (file, " %d", i);
1732 fprintf (file, "\n\n");
1735 /* Run old register allocator. Return TRUE if we must exit
1736 rest_of_compilation upon return. */
1738 rest_of_handle_global_alloc (void)
1742 /* If optimizing, allocate remaining pseudo-regs. Do the reload
1743 pass fixing up any insns that are invalid. */
1744 if (optimize && dbg_cnt (global_alloc_at_func))
1745 failure = global_alloc ();
1748 /* There is just too much going on in the register allocators to
1749 keep things up to date. At the end we have to rescan anyway
1750 because things change when the reload_completed flag is set.
1751 So we just turn off scanning and we will rescan by hand. */
1752 df_set_flags (DF_NO_INSN_RESCAN);
1753 compute_regsets (&eliminable_regset, &no_global_alloc_regs);
1754 build_insn_chain ();
1755 df_set_flags (DF_NO_INSN_RESCAN);
1756 failure = reload (get_insns (), 0);
1759 if (dump_enabled_p (pass_global_alloc.static_pass_number))
1761 timevar_push (TV_DUMP);
1762 dump_global_regs (dump_file);
1763 timevar_pop (TV_DUMP);
1766 /* FIXME: This appears on the surface to be wrong thing to be doing.
1767 So much of the compiler is designed to check reload_completed to
1768 see if it is running after reload that seems doomed to failure.
1769 We should be returning a value that says that we have found
1770 errors so that nothing but the cleanup passes are run
1772 gcc_assert (reload_completed || failure);
1773 reload_completed = !failure;
1775 /* The world has changed so much that at this point we might as well
1776 just rescan everything. Note that df_rescan_all_insns is not
1777 going to help here because it does not touch the artificial uses
1779 df_finish_pass (true);
1781 df_live_add_problem ();
1782 df_scan_alloc (NULL);
1788 regstat_free_n_sets_and_refs ();
1793 struct tree_opt_pass pass_global_alloc =
1797 rest_of_handle_global_alloc, /* execute */
1800 0, /* static_pass_number */
1801 TV_GLOBAL_ALLOC, /* tv_id */
1802 0, /* properties_required */
1803 0, /* properties_provided */
1804 0, /* properties_destroyed */
1805 0, /* todo_flags_start */
1806 TODO_dump_func | TODO_verify_rtl_sharing
1807 | TODO_ggc_collect, /* todo_flags_finish */