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 /* Return true if *LOC contains an asm. */
137 insn_contains_asm_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
141 if (GET_CODE (*loc) == ASM_OPERANDS)
147 /* Return true if INSN contains an ASM. */
150 insn_contains_asm (rtx insn)
152 return for_each_rtx (&insn, insn_contains_asm_1, NULL);
157 compute_regs_asm_clobbered (char *regs_asm_clobbered)
161 memset (regs_asm_clobbered, 0, sizeof (char) * FIRST_PSEUDO_REGISTER);
166 FOR_BB_INSNS_REVERSE (bb, insn)
168 struct df_ref **def_rec;
169 if (insn_contains_asm (insn))
170 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
172 struct df_ref *def = *def_rec;
173 unsigned int dregno = DF_REF_REGNO (def);
174 if (dregno < FIRST_PSEUDO_REGISTER)
177 enum machine_mode mode = GET_MODE (DF_REF_REAL_REG (def));
178 unsigned int end = dregno
179 + hard_regno_nregs[dregno][mode] - 1;
180 for (i = dregno; i <= end; ++i)
181 regs_asm_clobbered[i] = 1;
189 /* All registers that can be eliminated. */
191 static HARD_REG_SET eliminable_regset;
193 static int regno_compare (const void *, const void *);
194 static int allocno_compare (const void *, const void *);
195 static void expand_preferences (void);
196 static void prune_preferences (void);
197 static void set_preferences (void);
198 static void find_reg (int, HARD_REG_SET, int, int, int);
199 static void dump_conflicts (FILE *);
200 static void build_insn_chain (void);
203 /* Look through the list of eliminable registers. Set ELIM_SET to the
204 set of registers which may be eliminated. Set NO_GLOBAL_SET to the
205 set of registers which may not be used across blocks.
207 This will normally be called with ELIM_SET as the file static
208 variable eliminable_regset, and NO_GLOBAL_SET as the file static
209 variable NO_GLOBAL_ALLOC_REGS.
211 It also initializes global flag frame_pointer_needed. */
214 compute_regsets (HARD_REG_SET *elim_set,
215 HARD_REG_SET *no_global_set)
218 /* Like regs_ever_live, but 1 if a reg is set or clobbered from an asm.
219 Unlike regs_ever_live, elements of this array corresponding to
220 eliminable regs like the frame pointer are set if an asm sets them. */
221 char *regs_asm_clobbered = XALLOCAVEC (char, FIRST_PSEUDO_REGISTER);
223 #ifdef ELIMINABLE_REGS
224 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
228 /* FIXME: If EXIT_IGNORE_STACK is set, we will not save and restore
229 sp for alloca. So we can't eliminate the frame pointer in that
230 case. At some point, we should improve this by emitting the
231 sp-adjusting insns for this case. */
233 = (! flag_omit_frame_pointer
234 || (cfun->calls_alloca && EXIT_IGNORE_STACK)
235 || crtl->accesses_prior_frames
236 || FRAME_POINTER_REQUIRED);
238 frame_pointer_needed = need_fp;
240 max_regno = max_reg_num ();
245 /* A machine may have certain hard registers that
246 are safe to use only within a basic block. */
248 CLEAR_HARD_REG_SET (*no_global_set);
249 CLEAR_HARD_REG_SET (*elim_set);
251 compute_regs_asm_clobbered (regs_asm_clobbered);
252 /* Build the regset of all eliminable registers and show we can't use those
253 that we already know won't be eliminated. */
254 #ifdef ELIMINABLE_REGS
255 for (i = 0; i < ARRAY_SIZE (eliminables); i++)
258 = (! CAN_ELIMINATE (eliminables[i].from, eliminables[i].to)
259 || (eliminables[i].to == STACK_POINTER_REGNUM && need_fp));
261 if (!regs_asm_clobbered[eliminables[i].from])
263 SET_HARD_REG_BIT (*elim_set, eliminables[i].from);
266 SET_HARD_REG_BIT (*no_global_set, eliminables[i].from);
268 else if (cannot_elim)
269 error ("%s cannot be used in asm here",
270 reg_names[eliminables[i].from]);
272 df_set_regs_ever_live (eliminables[i].from, true);
274 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
275 if (!regs_asm_clobbered[HARD_FRAME_POINTER_REGNUM])
277 SET_HARD_REG_BIT (*elim_set, HARD_FRAME_POINTER_REGNUM);
279 SET_HARD_REG_BIT (*no_global_set, HARD_FRAME_POINTER_REGNUM);
282 error ("%s cannot be used in asm here",
283 reg_names[HARD_FRAME_POINTER_REGNUM]);
285 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM, true);
289 if (!regs_asm_clobbered[FRAME_POINTER_REGNUM])
291 SET_HARD_REG_BIT (*elim_set, FRAME_POINTER_REGNUM);
293 SET_HARD_REG_BIT (*no_global_set, FRAME_POINTER_REGNUM);
296 error ("%s cannot be used in asm here", reg_names[FRAME_POINTER_REGNUM]);
298 df_set_regs_ever_live (FRAME_POINTER_REGNUM, true);
302 /* Perform allocation of pseudo-registers not allocated by local_alloc.
304 Return value is nonzero if reload failed
305 and we must not do any more for this function. */
313 int *num_allocnos_per_blk;
315 compute_regsets (&eliminable_regset, &no_global_alloc_regs);
317 /* Track which registers have already been used. Start with registers
318 explicitly in the rtl, then registers allocated by local register
321 CLEAR_HARD_REG_SET (regs_used_so_far);
322 #ifdef LEAF_REGISTERS
323 /* If we are doing the leaf function optimization, and this is a leaf
324 function, it means that the registers that take work to save are those
325 that need a register window. So prefer the ones that can be used in
328 const char *cheap_regs;
329 const char *const leaf_regs = LEAF_REGISTERS;
331 if (only_leaf_regs_used () && leaf_function_p ())
332 cheap_regs = leaf_regs;
334 cheap_regs = call_used_regs;
335 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
336 if (df_regs_ever_live_p (i) || cheap_regs[i])
337 SET_HARD_REG_BIT (regs_used_so_far, i);
340 /* We consider registers that do not have to be saved over calls as if
341 they were already used since there is no cost in using them. */
342 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
343 if (df_regs_ever_live_p (i) || call_used_regs[i])
344 SET_HARD_REG_BIT (regs_used_so_far, i);
347 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
348 if (reg_renumber[i] >= 0)
349 SET_HARD_REG_BIT (regs_used_so_far, reg_renumber[i]);
351 /* Establish mappings from register number to allocation number
352 and vice versa. In the process, count the allocnos. */
354 reg_allocno = XNEWVEC (int, max_regno);
356 /* Initially fill the reg_allocno array with regno's... */
359 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
360 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
361 that we are supposed to refrain from putting in a hard reg.
362 -2 means do make an allocno but don't allocate it. */
363 if (REG_N_REFS (i) != 0 && REG_LIVE_LENGTH (i) != -1
364 /* Don't allocate pseudos that cross calls,
365 if this function receives a nonlocal goto. */
366 && (! cfun->has_nonlocal_label
367 || REG_N_CALLS_CROSSED (i) == 0))
369 int blk = regno_basic_block (i);
370 reg_allocno[max_allocno++] = i;
373 gcc_assert (REG_LIVE_LENGTH (i));
376 allocno = XCNEWVEC (struct allocno, max_allocno);
377 partial_bitnum = XNEWVEC (HOST_WIDE_INT, max_allocno);
378 num_allocnos_per_blk = XCNEWVEC (int, max_blk + 1);
380 /* ...so we can sort them in the order we want them to receive
382 qsort (reg_allocno, max_allocno, sizeof (int), regno_compare);
384 for (i = 0; i < (size_t) max_allocno; i++)
386 int regno = reg_allocno[i];
387 int blk = regno_basic_block (regno);
388 num_allocnos_per_blk[blk]++;
389 allocno[i].reg = regno;
390 allocno[i].size = PSEUDO_REGNO_SIZE (regno);
391 allocno[i].calls_crossed += REG_N_CALLS_CROSSED (regno);
392 allocno[i].freq_calls_crossed += REG_FREQ_CALLS_CROSSED (regno);
393 allocno[i].throwing_calls_crossed
394 += REG_N_THROWING_CALLS_CROSSED (regno);
395 allocno[i].n_refs += REG_N_REFS (regno);
396 allocno[i].freq += REG_FREQ (regno);
397 if (allocno[i].live_length < REG_LIVE_LENGTH (regno))
398 allocno[i].live_length = REG_LIVE_LENGTH (regno);
401 /* The "global" block must contain all allocnos. */
402 num_allocnos_per_blk[0] = max_allocno;
404 /* Now reinitialize the reg_allocno array in terms of the
405 optimized regno to allocno mapping we created above. */
406 for (i = 0; i < (size_t) max_regno; i++)
410 for (i = 0; i < (size_t) max_allocno; i++)
412 int regno = allocno[i].reg;
413 int blk = regno_basic_block (regno);
414 int row_size = --num_allocnos_per_blk[blk];
415 reg_allocno[regno] = (int) i;
416 partial_bitnum[i] = (row_size > 0) ? max_bitnum - ((int) i + 1) : -1;
417 max_bitnum += row_size;
420 #ifdef ENABLE_CHECKING
421 gcc_assert (max_bitnum <=
422 (((HOST_WIDE_INT) max_allocno *
423 ((HOST_WIDE_INT) max_allocno - 1)) / 2));
428 HOST_WIDE_INT num_bits, num_bytes, actual_bytes;
430 fprintf (dump_file, "## max_blk: %d\n", max_blk);
431 fprintf (dump_file, "## max_regno: %d\n", max_regno);
432 fprintf (dump_file, "## max_allocno: %d\n", max_allocno);
434 num_bits = max_bitnum;
435 num_bytes = CEIL (num_bits, 8);
436 actual_bytes = num_bytes;
437 fprintf (dump_file, "## Compressed triangular bitmatrix size: ");
438 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC " bits, ", num_bits);
439 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC " bytes\n", num_bytes);
441 num_bits = ((HOST_WIDE_INT) max_allocno *
442 ((HOST_WIDE_INT) max_allocno - 1)) / 2;
443 num_bytes = CEIL (num_bits, 8);
444 fprintf (dump_file, "## Standard triangular bitmatrix size: ");
445 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC " bits, ", num_bits);
446 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC " bytes [%.2f%%]\n",
447 num_bytes, 100.0 * ((double) actual_bytes / (double) num_bytes));
449 num_bits = (HOST_WIDE_INT) max_allocno * (HOST_WIDE_INT) max_allocno;
450 num_bytes = CEIL (num_bits, 8);
451 fprintf (dump_file, "## Square bitmatrix size: ");
452 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC " bits, ", num_bits);
453 fprintf (dump_file, HOST_WIDE_INT_PRINT_DEC " bytes [%.2f%%]\n",
454 num_bytes, 100.0 * ((double) actual_bytes / (double) num_bytes));
457 /* Calculate amount of usage of each hard reg by pseudos
458 allocated by local-alloc. This is to see if we want to
460 memset (local_reg_live_length, 0, sizeof local_reg_live_length);
461 memset (local_reg_n_refs, 0, sizeof local_reg_n_refs);
462 memset (local_reg_freq, 0, sizeof local_reg_freq);
463 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
464 if (reg_renumber[i] >= 0)
466 int regno = reg_renumber[i];
467 int endregno = end_hard_regno (PSEUDO_REGNO_MODE (i), regno);
470 for (j = regno; j < endregno; j++)
472 local_reg_n_refs[j] += REG_N_REFS (i);
473 local_reg_freq[j] += REG_FREQ (i);
474 local_reg_live_length[j] += REG_LIVE_LENGTH (i);
478 /* We can't override local-alloc for a reg used not just by local-alloc. */
479 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
480 if (df_regs_ever_live_p (i))
481 local_reg_n_refs[i] = 0, local_reg_freq[i] = 0;
485 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
487 fprintf (dump_file, "%d REG_N_REFS=%d, REG_FREQ=%d, REG_LIVE_LENGTH=%d\n",
488 (int)i, REG_N_REFS (i), REG_FREQ (i), REG_LIVE_LENGTH (i));
490 fprintf (dump_file, "regs_ever_live =");
491 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
492 if (df_regs_ever_live_p (i))
493 fprintf (dump_file, " %d", (int)i);
494 fprintf (dump_file, "\n");
499 adjacency_pool = NULL;
501 /* If there is work to be done (at least one reg to allocate),
502 perform global conflict analysis and allocate the regs. */
506 /* We used to use alloca here, but the size of what it would try to
507 allocate would occasionally cause it to exceed the stack limit and
508 cause unpredictable core dumps. Some examples were > 2Mb in size. */
509 conflicts = XCNEWVEC (HOST_WIDEST_FAST_INT,
510 CEIL(max_bitnum, HOST_BITS_PER_WIDEST_FAST_INT));
512 adjacency = XCNEWVEC (adjacency_t *, max_allocno);
513 adjacency_pool = create_alloc_pool ("global_alloc adjacency list pool",
514 sizeof (adjacency_t), 1024);
516 /* Scan all the insns and compute the conflicts among allocnos
517 and between allocnos and hard regs. */
521 /* There is just too much going on in the register allocators to
522 keep things up to date. At the end we have to rescan anyway
523 because things change when the reload_completed flag is set.
524 So we just turn off scanning and we will rescan by hand.
526 However, we needed to do the rescanning before this point to
527 get the new insns scanned inserted by local_alloc scanned for
529 df_set_flags (DF_NO_INSN_RESCAN);
531 /* Eliminate conflicts between pseudos and eliminable registers. If
532 the register is not eliminated, the pseudo won't really be able to
533 live in the eliminable register, so the conflict doesn't matter.
534 If we do eliminate the register, the conflict will no longer exist.
535 So in either case, we can ignore the conflict. Likewise for
540 for (i = 0; i < (size_t) max_allocno; i++)
542 AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_conflicts,
544 AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_copy_preferences,
546 AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_preferences,
550 /* Try to expand the preferences by merging them between allocnos. */
552 expand_preferences ();
554 /* Determine the order to allocate the remaining pseudo registers. */
556 allocno_order = XNEWVEC (int, max_allocno);
557 for (i = 0; i < (size_t) max_allocno; i++)
558 allocno_order[i] = i;
560 /* Default the size to 1, since allocno_compare uses it to divide by.
561 Also convert allocno_live_length of zero to -1. A length of zero
562 can occur when all the registers for that allocno have reg_live_length
563 equal to -2. In this case, we want to make an allocno, but not
564 allocate it. So avoid the divide-by-zero and set it to a low
567 for (i = 0; i < (size_t) max_allocno; i++)
569 if (allocno[i].size == 0)
571 if (allocno[i].live_length == 0)
572 allocno[i].live_length = -1;
575 qsort (allocno_order, max_allocno, sizeof (int), allocno_compare);
577 prune_preferences ();
580 dump_conflicts (dump_file);
582 /* Try allocating them, one by one, in that order,
583 except for parameters marked with reg_live_length[regno] == -2. */
585 for (i = 0; i < (size_t) max_allocno; i++)
586 if (reg_renumber[allocno[allocno_order[i]].reg] < 0
587 && REG_LIVE_LENGTH (allocno[allocno_order[i]].reg) >= 0)
589 if (!dbg_cnt (global_alloc_at_reg))
591 /* If we have more than one register class,
592 first try allocating in the class that is cheapest
593 for this pseudo-reg. If that fails, try any reg. */
594 if (N_REG_CLASSES > 1)
596 find_reg (allocno_order[i], 0, 0, 0, 0);
597 if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
600 if (reg_alternate_class (allocno[allocno_order[i]].reg) != NO_REGS)
601 find_reg (allocno_order[i], 0, 1, 0, 0);
604 free (allocno_order);
608 /* Do the reloads now while the allocno data still exists, so that we can
609 try to assign new hard regs to any pseudo regs that are spilled. */
611 #if 0 /* We need to eliminate regs even if there is no rtl code,
612 for the sake of debugging information. */
613 if (n_basic_blocks > NUM_FIXED_BLOCKS)
617 retval = reload (get_insns (), 1);
622 free (num_allocnos_per_blk);
623 free (partial_bitnum);
625 if (adjacency != NULL)
627 free_alloc_pool (adjacency_pool);
634 /* Sort predicate for ordering the regnos. We want the regno to allocno
635 mapping to have the property that all "global" regnos (ie, regnos that
636 are referenced in more than one basic block) have smaller allocno values
637 than "local" regnos (ie, regnos referenced in only one basic block).
638 In addition, for two basic blocks "i" and "j" with i < j, all regnos
639 local to basic block i should have smaller allocno values than regnos
640 local to basic block j.
641 Returns -1 (1) if *v1p should be allocated before (after) *v2p. */
644 regno_compare (const void *v1p, const void *v2p)
646 int regno1 = *(const int *)v1p;
647 int regno2 = *(const int *)v2p;
648 int blk1 = REG_BASIC_BLOCK (regno1);
649 int blk2 = REG_BASIC_BLOCK (regno2);
651 /* Prefer lower numbered basic blocks. Note that global and unknown
652 blocks have negative values, giving them high precedence. */
656 /* If both regs are referenced from the same block, sort by regno. */
657 return regno1 - regno2;
660 /* Sort predicate for ordering the allocnos.
661 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
664 allocno_compare (const void *v1p, const void *v2p)
666 int v1 = *(const int *)v1p, v2 = *(const int *)v2p;
667 /* Note that the quotient will never be bigger than
668 the value of floor_log2 times the maximum number of
669 times a register can occur in one insn (surely less than 100)
670 weighted by the frequency (maximally REG_FREQ_MAX).
671 Multiplying this by 10000/REG_FREQ_MAX can't overflow. */
673 = (((double) (floor_log2 (allocno[v1].n_refs) * allocno[v1].freq)
674 / allocno[v1].live_length)
675 * (10000 / REG_FREQ_MAX) * allocno[v1].size);
677 = (((double) (floor_log2 (allocno[v2].n_refs) * allocno[v2].freq)
678 / allocno[v2].live_length)
679 * (10000 / REG_FREQ_MAX) * allocno[v2].size);
683 /* If regs are equally good, sort by allocno,
684 so that the results of qsort leave nothing to chance. */
688 /* Expand the preference information by looking for cases where one allocno
689 dies in an insn that sets an allocno. If those two allocnos don't conflict,
690 merge any preferences between those allocnos. */
693 expand_preferences (void)
699 /* We only try to handle the most common cases here. Most of the cases
700 where this wins are reg-reg copies. */
702 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
704 && (set = single_set (insn)) != 0
705 && REG_P (SET_DEST (set))
706 && reg_allocno[REGNO (SET_DEST (set))] >= 0)
707 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
708 if (REG_NOTE_KIND (link) == REG_DEAD
709 && REG_P (XEXP (link, 0))
710 && reg_allocno[REGNO (XEXP (link, 0))] >= 0
711 && ! conflict_p (reg_allocno[REGNO (SET_DEST (set))],
712 reg_allocno[REGNO (XEXP (link, 0))]))
714 int a1 = reg_allocno[REGNO (SET_DEST (set))];
715 int a2 = reg_allocno[REGNO (XEXP (link, 0))];
717 if (XEXP (link, 0) == SET_SRC (set))
719 IOR_HARD_REG_SET (allocno[a1].hard_reg_copy_preferences,
720 allocno[a2].hard_reg_copy_preferences);
721 IOR_HARD_REG_SET (allocno[a2].hard_reg_copy_preferences,
722 allocno[a1].hard_reg_copy_preferences);
725 IOR_HARD_REG_SET (allocno[a1].hard_reg_preferences,
726 allocno[a2].hard_reg_preferences);
727 IOR_HARD_REG_SET (allocno[a2].hard_reg_preferences,
728 allocno[a1].hard_reg_preferences);
729 IOR_HARD_REG_SET (allocno[a1].hard_reg_full_preferences,
730 allocno[a2].hard_reg_full_preferences);
731 IOR_HARD_REG_SET (allocno[a2].hard_reg_full_preferences,
732 allocno[a1].hard_reg_full_preferences);
737 /* Try to set a preference for an allocno to a hard register.
738 We are passed DEST and SRC which are the operands of a SET. It is known
739 that SRC is a register. If SRC or the first operand of SRC is a register,
740 try to set a preference. If one of the two is a hard register and the other
741 is a pseudo-register, mark the preference.
743 Note that we are not as aggressive as local-alloc in trying to tie a
744 pseudo-register to a hard register. */
747 set_preference (rtx dest, rtx src)
749 unsigned int src_regno, dest_regno, end_regno;
750 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
751 to compensate for subregs in SRC or DEST. */
756 if (GET_RTX_FORMAT (GET_CODE (src))[0] == 'e')
757 src = XEXP (src, 0), copy = 0;
759 /* Get the reg number for both SRC and DEST.
760 If neither is a reg, give up. */
763 src_regno = REGNO (src);
764 else if (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src)))
766 src_regno = REGNO (SUBREG_REG (src));
768 if (REGNO (SUBREG_REG (src)) < FIRST_PSEUDO_REGISTER)
769 offset += subreg_regno_offset (REGNO (SUBREG_REG (src)),
770 GET_MODE (SUBREG_REG (src)),
774 offset += (SUBREG_BYTE (src)
775 / REGMODE_NATURAL_SIZE (GET_MODE (src)));
781 dest_regno = REGNO (dest);
782 else if (GET_CODE (dest) == SUBREG && REG_P (SUBREG_REG (dest)))
784 dest_regno = REGNO (SUBREG_REG (dest));
786 if (REGNO (SUBREG_REG (dest)) < FIRST_PSEUDO_REGISTER)
787 offset -= subreg_regno_offset (REGNO (SUBREG_REG (dest)),
788 GET_MODE (SUBREG_REG (dest)),
792 offset -= (SUBREG_BYTE (dest)
793 / REGMODE_NATURAL_SIZE (GET_MODE (dest)));
798 /* Convert either or both to hard reg numbers. */
800 if (reg_renumber[src_regno] >= 0)
801 src_regno = reg_renumber[src_regno];
803 if (reg_renumber[dest_regno] >= 0)
804 dest_regno = reg_renumber[dest_regno];
806 /* Now if one is a hard reg and the other is a global pseudo
807 then give the other a preference. */
809 if (dest_regno < FIRST_PSEUDO_REGISTER && src_regno >= FIRST_PSEUDO_REGISTER
810 && reg_allocno[src_regno] >= 0)
812 dest_regno -= offset;
813 if (dest_regno < FIRST_PSEUDO_REGISTER)
816 SET_REGBIT (hard_reg_copy_preferences,
817 reg_allocno[src_regno], dest_regno);
819 SET_REGBIT (hard_reg_preferences,
820 reg_allocno[src_regno], dest_regno);
821 end_regno = end_hard_regno (GET_MODE (dest), dest_regno);
822 for (i = dest_regno; i < end_regno; i++)
823 SET_REGBIT (hard_reg_full_preferences, reg_allocno[src_regno], i);
827 if (src_regno < FIRST_PSEUDO_REGISTER && dest_regno >= FIRST_PSEUDO_REGISTER
828 && reg_allocno[dest_regno] >= 0)
831 if (src_regno < FIRST_PSEUDO_REGISTER)
834 SET_REGBIT (hard_reg_copy_preferences,
835 reg_allocno[dest_regno], src_regno);
837 SET_REGBIT (hard_reg_preferences,
838 reg_allocno[dest_regno], src_regno);
839 end_regno = end_hard_regno (GET_MODE (src), src_regno);
840 for (i = src_regno; i < end_regno; i++)
841 SET_REGBIT (hard_reg_full_preferences, reg_allocno[dest_regno], i);
846 /* Helper function for set_preferences. */
848 set_preferences_1 (rtx reg, const_rtx setter, void *data ATTRIBUTE_UNUSED)
850 if (GET_CODE (reg) == SUBREG)
851 reg = SUBREG_REG (reg);
857 if (GET_CODE (setter) != CLOBBER)
858 set_preference (reg, SET_SRC (setter));
861 /* Scan all of the insns and initialize the preferences. */
864 set_preferences (void)
869 FOR_BB_INSNS_REVERSE (bb, insn)
874 note_stores (PATTERN (insn), set_preferences_1, NULL);
880 /* Prune the preferences for global registers to exclude registers that cannot
883 Compute `regs_someone_prefers', which is a bitmask of the hard registers
884 that are preferred by conflicting registers of lower priority. If possible,
885 we will avoid using these registers. */
888 prune_preferences (void)
892 int *allocno_to_order = XNEWVEC (int, max_allocno);
894 /* Scan least most important to most important.
895 For each allocno, remove from preferences registers that cannot be used,
896 either because of conflicts or register type. Then compute all registers
897 preferred by each lower-priority register that conflicts. */
899 for (i = max_allocno - 1; i >= 0; i--)
903 num = allocno_order[i];
904 allocno_to_order[num] = i;
905 COPY_HARD_REG_SET (temp, allocno[num].hard_reg_conflicts);
907 if (allocno[num].calls_crossed == 0)
908 IOR_HARD_REG_SET (temp, fixed_reg_set);
910 IOR_HARD_REG_SET (temp, call_used_reg_set);
912 IOR_COMPL_HARD_REG_SET
914 reg_class_contents[(int) reg_preferred_class (allocno[num].reg)]);
916 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_preferences, temp);
917 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_copy_preferences, temp);
918 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_full_preferences, temp);
921 for (i = max_allocno - 1; i >= 0; i--)
923 /* Merge in the preferences of lower-priority registers (they have
924 already been pruned). If we also prefer some of those registers,
925 don't exclude them unless we are of a smaller size (in which case
926 we want to give the lower-priority allocno the first chance for
928 HARD_REG_SET temp, temp2;
932 num = allocno_order[i];
934 CLEAR_HARD_REG_SET (temp);
935 CLEAR_HARD_REG_SET (temp2);
937 FOR_EACH_CONFLICT (num, allocno2, ai)
939 if (allocno_to_order[allocno2] > i)
941 if (allocno[allocno2].size <= allocno[num].size)
942 IOR_HARD_REG_SET (temp,
943 allocno[allocno2].hard_reg_full_preferences);
945 IOR_HARD_REG_SET (temp2,
946 allocno[allocno2].hard_reg_full_preferences);
950 AND_COMPL_HARD_REG_SET (temp, allocno[num].hard_reg_full_preferences);
951 IOR_HARD_REG_SET (temp, temp2);
952 COPY_HARD_REG_SET (allocno[num].regs_someone_prefers, temp);
954 free (allocno_to_order);
957 /* Assign a hard register to allocno NUM; look for one that is the beginning
958 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
959 The registers marked in PREFREGS are tried first.
961 LOSERS, if nonzero, is a HARD_REG_SET indicating registers that cannot
962 be used for this allocation.
964 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
965 Otherwise ignore that preferred class and use the alternate class.
967 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
968 will have to be saved and restored at calls.
970 RETRYING is nonzero if this is called from retry_global_alloc.
972 If we find one, record it in reg_renumber.
973 If not, do nothing. */
976 find_reg (int num, HARD_REG_SET losers, int alt_regs_p, int accept_call_clobbered, int retrying)
978 int i, best_reg, pass;
979 HARD_REG_SET used, used1, used2;
981 enum reg_class class = (alt_regs_p
982 ? reg_alternate_class (allocno[num].reg)
983 : reg_preferred_class (allocno[num].reg));
984 enum machine_mode mode = PSEUDO_REGNO_MODE (allocno[num].reg);
986 if (accept_call_clobbered)
987 COPY_HARD_REG_SET (used1, call_fixed_reg_set);
988 else if (allocno[num].calls_crossed == 0)
989 COPY_HARD_REG_SET (used1, fixed_reg_set);
991 COPY_HARD_REG_SET (used1, call_used_reg_set);
993 /* Some registers should not be allocated in global-alloc. */
994 IOR_HARD_REG_SET (used1, no_global_alloc_regs);
996 IOR_HARD_REG_SET (used1, losers);
998 IOR_COMPL_HARD_REG_SET (used1, reg_class_contents[(int) class]);
1000 #ifdef EH_RETURN_DATA_REGNO
1001 if (allocno[num].no_eh_reg)
1006 unsigned int regno = EH_RETURN_DATA_REGNO (j);
1007 if (regno == INVALID_REGNUM)
1009 SET_HARD_REG_BIT (used1, regno);
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_ZERO_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,
1490 if (!DF_REF_FLAGS_IS_SET
1491 (def, DF_REF_STRICT_LOW_PART))
1493 /* Expand the range to cover entire words.
1494 Bytes added here are "don't care". */
1495 start = start / UNITS_PER_WORD * UNITS_PER_WORD;
1496 last = ((last + UNITS_PER_WORD - 1)
1497 / UNITS_PER_WORD * UNITS_PER_WORD);
1500 /* Ignore the paradoxical bits. */
1501 if ((int)last > live_subregs_used[regno])
1502 last = live_subregs_used[regno];
1504 while (start < last)
1506 RESET_BIT (live_subregs[regno], start);
1510 if (sbitmap_empty_p (live_subregs[regno]))
1512 live_subregs_used[regno] = 0;
1513 bitmap_clear_bit (live_relevant_regs, regno);
1516 /* Set live_relevant_regs here because
1517 that bit has to be true to get us to
1518 look at the live_subregs fields. */
1519 bitmap_set_bit (live_relevant_regs, regno);
1523 /* DF_REF_PARTIAL is generated for
1524 subregs, STRICT_LOW_PART, and
1525 ZERO_EXTRACT. We handle the subreg
1526 case above so here we have to keep from
1527 modeling the def as a killing def. */
1528 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL))
1530 bitmap_clear_bit (live_relevant_regs, regno);
1531 live_subregs_used[regno] = 0;
1537 bitmap_and_compl_into (live_relevant_regs, elim_regset);
1538 bitmap_copy (&c->live_throughout, live_relevant_regs);
1541 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
1543 struct df_ref *use = *use_rec;
1544 unsigned int regno = DF_REF_REGNO (use);
1545 rtx reg = DF_REF_REG (use);
1547 /* DF_REF_READ_WRITE on a use means that this use
1548 is fabricated from a def that is a partial set
1549 to a multiword reg. Here, we only model the
1550 subreg case that is not wrapped in ZERO_EXTRACT
1551 precisely so we do not need to look at the
1553 if (DF_REF_FLAGS_IS_SET (use, DF_REF_READ_WRITE)
1554 && !DF_REF_FLAGS_IS_SET (use, DF_REF_ZERO_EXTRACT)
1555 && DF_REF_FLAGS_IS_SET (use, DF_REF_SUBREG))
1558 /* Add the last use of each var to dead_or_set. */
1559 if (!bitmap_bit_p (live_relevant_regs, regno))
1561 if (regno < FIRST_PSEUDO_REGISTER)
1563 if (!fixed_regs[regno])
1564 bitmap_set_bit (&c->dead_or_set, regno);
1566 else if (reg_renumber[regno] >= 0)
1567 bitmap_set_bit (&c->dead_or_set, regno);
1570 if (regno < FIRST_PSEUDO_REGISTER || reg_renumber[regno] >= 0)
1572 if (GET_CODE (reg) == SUBREG
1573 && !DF_REF_FLAGS_IS_SET (use,
1574 DF_REF_SIGN_EXTRACT | DF_REF_ZERO_EXTRACT))
1576 unsigned int start = SUBREG_BYTE (reg);
1577 unsigned int last = start
1578 + GET_MODE_SIZE (GET_MODE (reg));
1580 ra_init_live_subregs (bitmap_bit_p (live_relevant_regs,
1586 /* Ignore the paradoxical bits. */
1587 if ((int)last > live_subregs_used[regno])
1588 last = live_subregs_used[regno];
1590 while (start < last)
1592 SET_BIT (live_subregs[regno], start);
1597 /* Resetting the live_subregs_used is
1598 effectively saying do not use the subregs
1599 because we are reading the whole
1601 live_subregs_used[regno] = 0;
1602 bitmap_set_bit (live_relevant_regs, regno);
1608 /* FIXME!! The following code is a disaster. Reload needs to see the
1609 labels and jump tables that are just hanging out in between
1610 the basic blocks. See pr33676. */
1611 insn = BB_HEAD (bb);
1613 /* Skip over the barriers and cruft. */
1614 while (insn && (BARRIER_P (insn) || NOTE_P (insn)
1615 || BLOCK_FOR_INSN (insn) == bb))
1616 insn = PREV_INSN (insn);
1618 /* While we add anything except barriers and notes, the focus is
1619 to get the labels and jump tables into the
1620 reload_insn_chain. */
1623 if (!NOTE_P (insn) && !BARRIER_P (insn))
1625 if (BLOCK_FOR_INSN (insn))
1628 c = new_insn_chain ();
1634 /* The block makes no sense here, but it is what the old
1636 c->block = bb->index;
1638 bitmap_copy (&c->live_throughout, live_relevant_regs);
1640 insn = PREV_INSN (insn);
1644 for (i = 0; i < (unsigned int) max_regno; i++)
1645 if (live_subregs[i])
1646 free (live_subregs[i]);
1648 reload_insn_chain = c;
1651 free (live_subregs);
1652 free (live_subregs_used);
1653 BITMAP_FREE (live_relevant_regs);
1654 BITMAP_FREE (elim_regset);
1657 print_insn_chains (dump_file);
1660 /* Print debugging trace information if -dg switch is given,
1661 showing the information on which the allocation decisions are based. */
1664 dump_conflicts (FILE *file)
1668 int has_preferences;
1671 for (i = 0; i < max_allocno; i++)
1673 if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
1677 fprintf (file, ";; %d regs to allocate:", nregs);
1678 for (regno = 0; regno < max_regno; regno++)
1679 if ((i = reg_allocno[regno]) >= 0)
1682 if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
1684 fprintf (file, " %d", allocno[allocno_order[i]].reg);
1685 for (j = 0; j < max_regno; j++)
1686 if (reg_allocno[j] == allocno_order[i]
1687 && j != allocno[allocno_order[i]].reg)
1688 fprintf (file, "+%d", j);
1689 if (allocno[allocno_order[i]].size != 1)
1690 fprintf (file, " (%d)", allocno[allocno_order[i]].size);
1692 fprintf (file, "\n");
1694 for (regno = 0; regno < max_regno; regno++)
1695 if ((i = reg_allocno[regno]) >= 0)
1699 fprintf (file, ";; %d conflicts:", allocno[i].reg);
1700 FOR_EACH_CONFLICT (i, j, ai)
1702 fprintf (file, " %d", allocno[j].reg);
1704 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1705 if (TEST_HARD_REG_BIT (allocno[i].hard_reg_conflicts, j)
1707 fprintf (file, " %d", j);
1708 fprintf (file, "\n");
1710 has_preferences = 0;
1711 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1712 if (TEST_HARD_REG_BIT (allocno[i].hard_reg_preferences, j))
1713 has_preferences = 1;
1715 if (!has_preferences)
1717 fprintf (file, ";; %d preferences:", allocno[i].reg);
1718 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1719 if (TEST_HARD_REG_BIT (allocno[i].hard_reg_preferences, j))
1720 fprintf (file, " %d", j);
1721 fprintf (file, "\n");
1723 fprintf (file, "\n");
1727 dump_global_regs (FILE *file)
1731 fprintf (file, ";; Register dispositions:\n");
1732 for (i = FIRST_PSEUDO_REGISTER, j = 0; i < max_regno; i++)
1733 if (reg_renumber[i] >= 0)
1735 fprintf (file, "%d in %d ", i, reg_renumber[i]);
1737 fprintf (file, "\n");
1740 fprintf (file, "\n\n;; Hard regs used: ");
1741 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1742 if (df_regs_ever_live_p (i))
1743 fprintf (file, " %d", i);
1744 fprintf (file, "\n\n");
1747 /* Run old register allocator. Return TRUE if we must exit
1748 rest_of_compilation upon return. */
1750 rest_of_handle_global_alloc (void)
1754 /* If optimizing, allocate remaining pseudo-regs. Do the reload
1755 pass fixing up any insns that are invalid. */
1756 if (optimize && dbg_cnt (global_alloc_at_func))
1757 failure = global_alloc ();
1760 /* There is just too much going on in the register allocators to
1761 keep things up to date. At the end we have to rescan anyway
1762 because things change when the reload_completed flag is set.
1763 So we just turn off scanning and we will rescan by hand. */
1764 df_set_flags (DF_NO_INSN_RESCAN);
1765 compute_regsets (&eliminable_regset, &no_global_alloc_regs);
1766 build_insn_chain ();
1767 df_set_flags (DF_NO_INSN_RESCAN);
1768 failure = reload (get_insns (), 0);
1771 if (dump_enabled_p (pass_global_alloc.pass.static_pass_number))
1773 timevar_push (TV_DUMP);
1774 dump_global_regs (dump_file);
1775 timevar_pop (TV_DUMP);
1778 /* FIXME: This appears on the surface to be wrong thing to be doing.
1779 So much of the compiler is designed to check reload_completed to
1780 see if it is running after reload that seems doomed to failure.
1781 We should be returning a value that says that we have found
1782 errors so that nothing but the cleanup passes are run
1784 gcc_assert (reload_completed || failure);
1785 reload_completed = !failure;
1787 /* The world has changed so much that at this point we might as well
1788 just rescan everything. Note that df_rescan_all_insns is not
1789 going to help here because it does not touch the artificial uses
1791 df_finish_pass (true);
1793 df_live_add_problem ();
1794 df_scan_alloc (NULL);
1800 regstat_free_n_sets_and_refs ();
1805 struct rtl_opt_pass pass_global_alloc =
1811 rest_of_handle_global_alloc, /* execute */
1814 0, /* static_pass_number */
1815 TV_GLOBAL_ALLOC, /* tv_id */
1816 0, /* properties_required */
1817 0, /* properties_provided */
1818 0, /* properties_destroyed */
1819 0, /* todo_flags_start */
1820 TODO_dump_func | TODO_verify_rtl_sharing
1821 | TODO_ggc_collect /* todo_flags_finish */