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 (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].throwing_calls_crossed
408 += REG_N_THROWING_CALLS_CROSSED (regno);
409 allocno[i].n_refs += REG_N_REFS (regno);
410 allocno[i].freq += REG_FREQ (regno);
411 if (allocno[i].live_length < REG_LIVE_LENGTH (regno))
412 allocno[i].live_length = REG_LIVE_LENGTH (regno);
415 /* The "global" block must contain all allocnos. */
416 num_allocnos_per_blk[0] = max_allocno;
418 /* Now reinitialize the reg_allocno array in terms of the
419 optimized regno to allocno mapping we created above. */
420 for (i = 0; i < (size_t) max_regno; i++)
424 for (i = 0; i < (size_t) max_allocno; i++)
426 int regno = allocno[i].reg;
427 int blk = regno_basic_block (regno);
428 int row_size = --num_allocnos_per_blk[blk];
429 reg_allocno[regno] = (int) i;
430 partial_bitnum[i] = (row_size > 0) ? max_bitnum - ((int) i + 1) : -1;
431 max_bitnum += row_size;
434 #ifdef ENABLE_CHECKING
435 gcc_assert (max_bitnum <= ((max_allocno * (max_allocno - 1)) / 2));
440 int num_bits, num_bytes, actual_bytes;
442 fprintf (dump_file, "## max_blk: %d\n", max_blk);
443 fprintf (dump_file, "## max_regno: %d\n", max_regno);
444 fprintf (dump_file, "## max_allocno: %d\n", max_allocno);
446 num_bits = max_bitnum;
447 num_bytes = CEIL (num_bits, 8);
448 actual_bytes = num_bytes;
449 fprintf (dump_file, "## Compressed triangular bitmatrix size: ");
450 fprintf (dump_file, "%d bits, %d bytes\n", num_bits, num_bytes);
452 num_bits = (max_allocno * (max_allocno - 1)) / 2;
453 num_bytes = CEIL (num_bits, 8);
454 fprintf (dump_file, "## Standard triangular bitmatrix size: ");
455 fprintf (dump_file, "%d bits, %d bytes [%.2f%%]\n",
457 100.0 * ((double) actual_bytes / (double) num_bytes));
459 num_bits = max_allocno * max_allocno;
460 num_bytes = CEIL (num_bits, 8);
461 fprintf (dump_file, "## Square bitmatrix size: ");
462 fprintf (dump_file, "%d bits, %d bytes [%.2f%%]\n",
464 100.0 * ((double) actual_bytes / (double) num_bytes));
467 /* Calculate amount of usage of each hard reg by pseudos
468 allocated by local-alloc. This is to see if we want to
470 memset (local_reg_live_length, 0, sizeof local_reg_live_length);
471 memset (local_reg_n_refs, 0, sizeof local_reg_n_refs);
472 memset (local_reg_freq, 0, sizeof local_reg_freq);
473 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
474 if (reg_renumber[i] >= 0)
476 int regno = reg_renumber[i];
477 int endregno = end_hard_regno (PSEUDO_REGNO_MODE (i), regno);
480 for (j = regno; j < endregno; j++)
482 local_reg_n_refs[j] += REG_N_REFS (i);
483 local_reg_freq[j] += REG_FREQ (i);
484 local_reg_live_length[j] += REG_LIVE_LENGTH (i);
488 /* We can't override local-alloc for a reg used not just by local-alloc. */
489 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
490 if (df_regs_ever_live_p (i))
491 local_reg_n_refs[i] = 0, local_reg_freq[i] = 0;
495 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
497 fprintf (dump_file, "%d REG_N_REFS=%d, REG_FREQ=%d, REG_LIVE_LENGTH=%d\n",
498 (int)i, REG_N_REFS (i), REG_FREQ (i), REG_LIVE_LENGTH (i));
500 fprintf (dump_file, "regs_ever_live =");
501 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
502 if (df_regs_ever_live_p (i))
503 fprintf (dump_file, " %d", (int)i);
504 fprintf (dump_file, "\n");
509 adjacency_pool = NULL;
511 /* If there is work to be done (at least one reg to allocate),
512 perform global conflict analysis and allocate the regs. */
516 /* We used to use alloca here, but the size of what it would try to
517 allocate would occasionally cause it to exceed the stack limit and
518 cause unpredictable core dumps. Some examples were > 2Mb in size. */
519 conflicts = XCNEWVEC (HOST_WIDEST_FAST_INT,
520 CEIL(max_bitnum, HOST_BITS_PER_WIDEST_FAST_INT));
522 adjacency = XCNEWVEC (adjacency_t *, max_allocno);
523 adjacency_pool = create_alloc_pool ("global_alloc adjacency list pool",
524 sizeof (adjacency_t), 1024);
526 /* Scan all the insns and compute the conflicts among allocnos
527 and between allocnos and hard regs. */
531 /* There is just too much going on in the register allocators to
532 keep things up to date. At the end we have to rescan anyway
533 because things change when the reload_completed flag is set.
534 So we just turn off scanning and we will rescan by hand.
536 However, we needed to do the rescanning before this point to
537 get the new insns scanned inserted by local_alloc scanned for
539 df_set_flags (DF_NO_INSN_RESCAN);
541 /* Eliminate conflicts between pseudos and eliminable registers. If
542 the register is not eliminated, the pseudo won't really be able to
543 live in the eliminable register, so the conflict doesn't matter.
544 If we do eliminate the register, the conflict will no longer exist.
545 So in either case, we can ignore the conflict. Likewise for
550 for (i = 0; i < (size_t) max_allocno; i++)
552 AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_conflicts,
554 AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_copy_preferences,
556 AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_preferences,
560 /* Try to expand the preferences by merging them between allocnos. */
562 expand_preferences ();
564 /* Determine the order to allocate the remaining pseudo registers. */
566 allocno_order = XNEWVEC (int, max_allocno);
567 for (i = 0; i < (size_t) max_allocno; i++)
568 allocno_order[i] = i;
570 /* Default the size to 1, since allocno_compare uses it to divide by.
571 Also convert allocno_live_length of zero to -1. A length of zero
572 can occur when all the registers for that allocno have reg_live_length
573 equal to -2. In this case, we want to make an allocno, but not
574 allocate it. So avoid the divide-by-zero and set it to a low
577 for (i = 0; i < (size_t) max_allocno; i++)
579 if (allocno[i].size == 0)
581 if (allocno[i].live_length == 0)
582 allocno[i].live_length = -1;
585 qsort (allocno_order, max_allocno, sizeof (int), allocno_compare);
587 prune_preferences ();
590 dump_conflicts (dump_file);
592 /* Try allocating them, one by one, in that order,
593 except for parameters marked with reg_live_length[regno] == -2. */
595 for (i = 0; i < (size_t) max_allocno; i++)
596 if (reg_renumber[allocno[allocno_order[i]].reg] < 0
597 && REG_LIVE_LENGTH (allocno[allocno_order[i]].reg) >= 0)
599 if (!dbg_cnt (global_alloc_at_reg))
601 /* If we have more than one register class,
602 first try allocating in the class that is cheapest
603 for this pseudo-reg. If that fails, try any reg. */
604 if (N_REG_CLASSES > 1)
606 find_reg (allocno_order[i], 0, 0, 0, 0);
607 if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
610 if (reg_alternate_class (allocno[allocno_order[i]].reg) != NO_REGS)
611 find_reg (allocno_order[i], 0, 1, 0, 0);
614 free (allocno_order);
618 /* Do the reloads now while the allocno data still exists, so that we can
619 try to assign new hard regs to any pseudo regs that are spilled. */
621 #if 0 /* We need to eliminate regs even if there is no rtl code,
622 for the sake of debugging information. */
623 if (n_basic_blocks > NUM_FIXED_BLOCKS)
627 retval = reload (get_insns (), 1);
632 free (num_allocnos_per_blk);
633 free (partial_bitnum);
635 if (adjacency != NULL)
637 free_alloc_pool (adjacency_pool);
644 /* Sort predicate for ordering the regnos. We want the regno to allocno
645 mapping to have the property that all "global" regnos (ie, regnos that
646 are referenced in more than one basic block) have smaller allocno values
647 than "local" regnos (ie, regnos referenced in only one basic block).
648 In addition, for two basic blocks "i" and "j" with i < j, all regnos
649 local to basic block i should have smaller allocno values than regnos
650 local to basic block j.
651 Returns -1 (1) if *v1p should be allocated before (after) *v2p. */
654 regno_compare (const void *v1p, const void *v2p)
656 int regno1 = *(const int *)v1p;
657 int regno2 = *(const int *)v2p;
658 int blk1 = REG_BASIC_BLOCK (regno1);
659 int blk2 = REG_BASIC_BLOCK (regno2);
661 /* Prefer lower numbered basic blocks. Note that global and unknown
662 blocks have negative values, giving them high precedence. */
666 /* If both regs are referenced from the same block, sort by regno. */
667 return regno1 - regno2;
670 /* Sort predicate for ordering the allocnos.
671 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
674 allocno_compare (const void *v1p, const void *v2p)
676 int v1 = *(const int *)v1p, v2 = *(const int *)v2p;
677 /* Note that the quotient will never be bigger than
678 the value of floor_log2 times the maximum number of
679 times a register can occur in one insn (surely less than 100)
680 weighted by the frequency (maximally REG_FREQ_MAX).
681 Multiplying this by 10000/REG_FREQ_MAX can't overflow. */
683 = (((double) (floor_log2 (allocno[v1].n_refs) * allocno[v1].freq)
684 / allocno[v1].live_length)
685 * (10000 / REG_FREQ_MAX) * allocno[v1].size);
687 = (((double) (floor_log2 (allocno[v2].n_refs) * allocno[v2].freq)
688 / allocno[v2].live_length)
689 * (10000 / REG_FREQ_MAX) * allocno[v2].size);
693 /* If regs are equally good, sort by allocno,
694 so that the results of qsort leave nothing to chance. */
698 /* Expand the preference information by looking for cases where one allocno
699 dies in an insn that sets an allocno. If those two allocnos don't conflict,
700 merge any preferences between those allocnos. */
703 expand_preferences (void)
709 /* We only try to handle the most common cases here. Most of the cases
710 where this wins are reg-reg copies. */
712 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
714 && (set = single_set (insn)) != 0
715 && REG_P (SET_DEST (set))
716 && reg_allocno[REGNO (SET_DEST (set))] >= 0)
717 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
718 if (REG_NOTE_KIND (link) == REG_DEAD
719 && REG_P (XEXP (link, 0))
720 && reg_allocno[REGNO (XEXP (link, 0))] >= 0
721 && ! conflict_p (reg_allocno[REGNO (SET_DEST (set))],
722 reg_allocno[REGNO (XEXP (link, 0))]))
724 int a1 = reg_allocno[REGNO (SET_DEST (set))];
725 int a2 = reg_allocno[REGNO (XEXP (link, 0))];
727 if (XEXP (link, 0) == SET_SRC (set))
729 IOR_HARD_REG_SET (allocno[a1].hard_reg_copy_preferences,
730 allocno[a2].hard_reg_copy_preferences);
731 IOR_HARD_REG_SET (allocno[a2].hard_reg_copy_preferences,
732 allocno[a1].hard_reg_copy_preferences);
735 IOR_HARD_REG_SET (allocno[a1].hard_reg_preferences,
736 allocno[a2].hard_reg_preferences);
737 IOR_HARD_REG_SET (allocno[a2].hard_reg_preferences,
738 allocno[a1].hard_reg_preferences);
739 IOR_HARD_REG_SET (allocno[a1].hard_reg_full_preferences,
740 allocno[a2].hard_reg_full_preferences);
741 IOR_HARD_REG_SET (allocno[a2].hard_reg_full_preferences,
742 allocno[a1].hard_reg_full_preferences);
747 /* Try to set a preference for an allocno to a hard register.
748 We are passed DEST and SRC which are the operands of a SET. It is known
749 that SRC is a register. If SRC or the first operand of SRC is a register,
750 try to set a preference. If one of the two is a hard register and the other
751 is a pseudo-register, mark the preference.
753 Note that we are not as aggressive as local-alloc in trying to tie a
754 pseudo-register to a hard register. */
757 set_preference (rtx dest, rtx src)
759 unsigned int src_regno, dest_regno, end_regno;
760 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
761 to compensate for subregs in SRC or DEST. */
766 if (GET_RTX_FORMAT (GET_CODE (src))[0] == 'e')
767 src = XEXP (src, 0), copy = 0;
769 /* Get the reg number for both SRC and DEST.
770 If neither is a reg, give up. */
773 src_regno = REGNO (src);
774 else if (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src)))
776 src_regno = REGNO (SUBREG_REG (src));
778 if (REGNO (SUBREG_REG (src)) < FIRST_PSEUDO_REGISTER)
779 offset += subreg_regno_offset (REGNO (SUBREG_REG (src)),
780 GET_MODE (SUBREG_REG (src)),
784 offset += (SUBREG_BYTE (src)
785 / REGMODE_NATURAL_SIZE (GET_MODE (src)));
791 dest_regno = REGNO (dest);
792 else if (GET_CODE (dest) == SUBREG && REG_P (SUBREG_REG (dest)))
794 dest_regno = REGNO (SUBREG_REG (dest));
796 if (REGNO (SUBREG_REG (dest)) < FIRST_PSEUDO_REGISTER)
797 offset -= subreg_regno_offset (REGNO (SUBREG_REG (dest)),
798 GET_MODE (SUBREG_REG (dest)),
802 offset -= (SUBREG_BYTE (dest)
803 / REGMODE_NATURAL_SIZE (GET_MODE (dest)));
808 /* Convert either or both to hard reg numbers. */
810 if (reg_renumber[src_regno] >= 0)
811 src_regno = reg_renumber[src_regno];
813 if (reg_renumber[dest_regno] >= 0)
814 dest_regno = reg_renumber[dest_regno];
816 /* Now if one is a hard reg and the other is a global pseudo
817 then give the other a preference. */
819 if (dest_regno < FIRST_PSEUDO_REGISTER && src_regno >= FIRST_PSEUDO_REGISTER
820 && reg_allocno[src_regno] >= 0)
822 dest_regno -= offset;
823 if (dest_regno < FIRST_PSEUDO_REGISTER)
826 SET_REGBIT (hard_reg_copy_preferences,
827 reg_allocno[src_regno], dest_regno);
829 SET_REGBIT (hard_reg_preferences,
830 reg_allocno[src_regno], dest_regno);
831 end_regno = end_hard_regno (GET_MODE (dest), dest_regno);
832 for (i = dest_regno; i < end_regno; i++)
833 SET_REGBIT (hard_reg_full_preferences, reg_allocno[src_regno], i);
837 if (src_regno < FIRST_PSEUDO_REGISTER && dest_regno >= FIRST_PSEUDO_REGISTER
838 && reg_allocno[dest_regno] >= 0)
841 if (src_regno < FIRST_PSEUDO_REGISTER)
844 SET_REGBIT (hard_reg_copy_preferences,
845 reg_allocno[dest_regno], src_regno);
847 SET_REGBIT (hard_reg_preferences,
848 reg_allocno[dest_regno], src_regno);
849 end_regno = end_hard_regno (GET_MODE (src), src_regno);
850 for (i = src_regno; i < end_regno; i++)
851 SET_REGBIT (hard_reg_full_preferences, reg_allocno[dest_regno], i);
856 /* Helper function for set_preferences. */
858 set_preferences_1 (rtx reg, const_rtx setter, void *data ATTRIBUTE_UNUSED)
860 if (GET_CODE (reg) == SUBREG)
861 reg = SUBREG_REG (reg);
867 if (GET_CODE (setter) != CLOBBER)
868 set_preference (reg, SET_SRC (setter));
871 /* Scan all of the insns and initialize the preferences. */
874 set_preferences (void)
879 FOR_BB_INSNS_REVERSE (bb, insn)
884 note_stores (PATTERN (insn), set_preferences_1, NULL);
890 /* Prune the preferences for global registers to exclude registers that cannot
893 Compute `regs_someone_prefers', which is a bitmask of the hard registers
894 that are preferred by conflicting registers of lower priority. If possible,
895 we will avoid using these registers. */
898 prune_preferences (void)
902 int *allocno_to_order = XNEWVEC (int, max_allocno);
904 /* Scan least most important to most important.
905 For each allocno, remove from preferences registers that cannot be used,
906 either because of conflicts or register type. Then compute all registers
907 preferred by each lower-priority register that conflicts. */
909 for (i = max_allocno - 1; i >= 0; i--)
913 num = allocno_order[i];
914 allocno_to_order[num] = i;
915 COPY_HARD_REG_SET (temp, allocno[num].hard_reg_conflicts);
917 if (allocno[num].calls_crossed == 0)
918 IOR_HARD_REG_SET (temp, fixed_reg_set);
920 IOR_HARD_REG_SET (temp, call_used_reg_set);
922 IOR_COMPL_HARD_REG_SET
924 reg_class_contents[(int) reg_preferred_class (allocno[num].reg)]);
926 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_preferences, temp);
927 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_copy_preferences, temp);
928 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_full_preferences, temp);
931 for (i = max_allocno - 1; i >= 0; i--)
933 /* Merge in the preferences of lower-priority registers (they have
934 already been pruned). If we also prefer some of those registers,
935 don't exclude them unless we are of a smaller size (in which case
936 we want to give the lower-priority allocno the first chance for
938 HARD_REG_SET temp, temp2;
942 num = allocno_order[i];
944 CLEAR_HARD_REG_SET (temp);
945 CLEAR_HARD_REG_SET (temp2);
947 FOR_EACH_CONFLICT (num, allocno2, ai)
949 if (allocno_to_order[allocno2] > i)
951 if (allocno[allocno2].size <= allocno[num].size)
952 IOR_HARD_REG_SET (temp,
953 allocno[allocno2].hard_reg_full_preferences);
955 IOR_HARD_REG_SET (temp2,
956 allocno[allocno2].hard_reg_full_preferences);
960 AND_COMPL_HARD_REG_SET (temp, allocno[num].hard_reg_full_preferences);
961 IOR_HARD_REG_SET (temp, temp2);
962 COPY_HARD_REG_SET (allocno[num].regs_someone_prefers, temp);
964 free (allocno_to_order);
967 /* Assign a hard register to allocno NUM; look for one that is the beginning
968 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
969 The registers marked in PREFREGS are tried first.
971 LOSERS, if nonzero, is a HARD_REG_SET indicating registers that cannot
972 be used for this allocation.
974 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
975 Otherwise ignore that preferred class and use the alternate class.
977 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
978 will have to be saved and restored at calls.
980 RETRYING is nonzero if this is called from retry_global_alloc.
982 If we find one, record it in reg_renumber.
983 If not, do nothing. */
986 find_reg (int num, HARD_REG_SET losers, int alt_regs_p, int accept_call_clobbered, int retrying)
988 int i, best_reg, pass;
989 HARD_REG_SET used, used1, used2;
991 enum reg_class class = (alt_regs_p
992 ? reg_alternate_class (allocno[num].reg)
993 : reg_preferred_class (allocno[num].reg));
994 enum machine_mode mode = PSEUDO_REGNO_MODE (allocno[num].reg);
996 if (accept_call_clobbered)
997 COPY_HARD_REG_SET (used1, call_fixed_reg_set);
998 else if (allocno[num].calls_crossed == 0)
999 COPY_HARD_REG_SET (used1, fixed_reg_set);
1001 COPY_HARD_REG_SET (used1, call_used_reg_set);
1003 /* Some registers should not be allocated in global-alloc. */
1004 IOR_HARD_REG_SET (used1, no_global_alloc_regs);
1006 IOR_HARD_REG_SET (used1, losers);
1008 IOR_COMPL_HARD_REG_SET (used1, reg_class_contents[(int) class]);
1009 COPY_HARD_REG_SET (used2, used1);
1011 IOR_HARD_REG_SET (used1, allocno[num].hard_reg_conflicts);
1013 #ifdef CANNOT_CHANGE_MODE_CLASS
1014 cannot_change_mode_set_regs (&used1, mode, allocno[num].reg);
1017 /* Try each hard reg to see if it fits. Do this in two passes.
1018 In the first pass, skip registers that are preferred by some other pseudo
1019 to give it a better chance of getting one of those registers. Only if
1020 we can't get a register when excluding those do we take one of them.
1021 However, we never allocate a register for the first time in pass 0. */
1023 COPY_HARD_REG_SET (used, used1);
1024 IOR_COMPL_HARD_REG_SET (used, regs_used_so_far);
1025 IOR_HARD_REG_SET (used, allocno[num].regs_someone_prefers);
1028 for (i = FIRST_PSEUDO_REGISTER, pass = 0;
1029 pass <= 1 && i >= FIRST_PSEUDO_REGISTER;
1033 COPY_HARD_REG_SET (used, used1);
1034 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1036 #ifdef REG_ALLOC_ORDER
1037 int regno = reg_alloc_order[i];
1041 if (! TEST_HARD_REG_BIT (used, regno)
1042 && HARD_REGNO_MODE_OK (regno, mode)
1043 && (allocno[num].calls_crossed == 0
1044 || accept_call_clobbered
1045 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
1048 int lim = end_hard_regno (mode, regno);
1051 && ! TEST_HARD_REG_BIT (used, j));
1058 #ifndef REG_ALLOC_ORDER
1059 i = j; /* Skip starting points we know will lose */
1065 /* See if there is a preferred register with the same class as the register
1066 we allocated above. Making this restriction prevents register
1067 preferencing from creating worse register allocation.
1069 Remove from the preferred registers and conflicting registers. Note that
1070 additional conflicts may have been added after `prune_preferences' was
1073 First do this for those register with copy preferences, then all
1074 preferred registers. */
1076 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_copy_preferences, used);
1077 if (!hard_reg_set_empty_p (allocno[num].hard_reg_copy_preferences)
1080 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1081 if (TEST_HARD_REG_BIT (allocno[num].hard_reg_copy_preferences, i)
1082 && HARD_REGNO_MODE_OK (i, mode)
1083 && (allocno[num].calls_crossed == 0
1084 || accept_call_clobbered
1085 || ! HARD_REGNO_CALL_PART_CLOBBERED (i, mode))
1086 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1087 || reg_class_subset_p (REGNO_REG_CLASS (i),
1088 REGNO_REG_CLASS (best_reg))
1089 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1090 REGNO_REG_CLASS (i))))
1093 int lim = end_hard_regno (mode, i);
1096 && ! TEST_HARD_REG_BIT (used, j)
1097 && (REGNO_REG_CLASS (j)
1098 == REGNO_REG_CLASS (best_reg + (j - i))
1099 || reg_class_subset_p (REGNO_REG_CLASS (j),
1100 REGNO_REG_CLASS (best_reg + (j - i)))
1101 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1102 REGNO_REG_CLASS (j))));
1112 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_preferences, used);
1113 if (!hard_reg_set_empty_p (allocno[num].hard_reg_preferences)
1116 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1117 if (TEST_HARD_REG_BIT (allocno[num].hard_reg_preferences, i)
1118 && HARD_REGNO_MODE_OK (i, mode)
1119 && (allocno[num].calls_crossed == 0
1120 || accept_call_clobbered
1121 || ! HARD_REGNO_CALL_PART_CLOBBERED (i, mode))
1122 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1123 || reg_class_subset_p (REGNO_REG_CLASS (i),
1124 REGNO_REG_CLASS (best_reg))
1125 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1126 REGNO_REG_CLASS (i))))
1129 int lim = end_hard_regno (mode, i);
1132 && ! TEST_HARD_REG_BIT (used, j)
1133 && (REGNO_REG_CLASS (j)
1134 == REGNO_REG_CLASS (best_reg + (j - i))
1135 || reg_class_subset_p (REGNO_REG_CLASS (j),
1136 REGNO_REG_CLASS (best_reg + (j - i)))
1137 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1138 REGNO_REG_CLASS (j))));
1149 /* If we haven't succeeded yet, try with caller-saves.
1150 We need not check to see if the current function has nonlocal
1151 labels because we don't put any pseudos that are live over calls in
1152 registers in that case. */
1154 if (flag_caller_saves && best_reg < 0)
1156 /* Did not find a register. If it would be profitable to
1157 allocate a call-clobbered register and save and restore it
1158 around calls, do that. Don't do this if it crosses any calls
1159 that might throw. */
1160 if (! accept_call_clobbered
1161 && allocno[num].calls_crossed != 0
1162 && allocno[num].throwing_calls_crossed == 0
1163 && CALLER_SAVE_PROFITABLE (allocno[num].n_refs,
1164 allocno[num].calls_crossed))
1166 HARD_REG_SET new_losers;
1168 CLEAR_HARD_REG_SET (new_losers);
1170 COPY_HARD_REG_SET (new_losers, losers);
1172 IOR_HARD_REG_SET(new_losers, losing_caller_save_reg_set);
1173 find_reg (num, new_losers, alt_regs_p, 1, retrying);
1174 if (reg_renumber[allocno[num].reg] >= 0)
1176 caller_save_needed = 1;
1182 /* If we haven't succeeded yet,
1183 see if some hard reg that conflicts with us
1184 was utilized poorly by local-alloc.
1185 If so, kick out the regs that were put there by local-alloc
1186 so we can use it instead. */
1187 if (best_reg < 0 && !retrying
1188 /* Let's not bother with multi-reg allocnos. */
1189 && allocno[num].size == 1
1190 && REG_BASIC_BLOCK (allocno[num].reg) == REG_BLOCK_GLOBAL)
1192 /* Count from the end, to find the least-used ones first. */
1193 for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1195 #ifdef REG_ALLOC_ORDER
1196 int regno = reg_alloc_order[i];
1201 if (local_reg_n_refs[regno] != 0
1202 /* Don't use a reg no good for this pseudo. */
1203 && ! TEST_HARD_REG_BIT (used2, regno)
1204 && HARD_REGNO_MODE_OK (regno, mode)
1205 /* The code below assumes that we need only a single
1206 register, but the check of allocno[num].size above
1207 was not enough. Sometimes we need more than one
1208 register for a single-word value. */
1209 && hard_regno_nregs[regno][mode] == 1
1210 && (allocno[num].calls_crossed == 0
1211 || accept_call_clobbered
1212 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode))
1213 #ifdef CANNOT_CHANGE_MODE_CLASS
1214 && ! invalid_mode_change_p (regno, REGNO_REG_CLASS (regno),
1218 && (!allocno[num].no_stack_reg
1219 || regno < FIRST_STACK_REG || regno > LAST_STACK_REG)
1223 /* We explicitly evaluate the divide results into temporary
1224 variables so as to avoid excess precision problems that occur
1225 on an i386-unknown-sysv4.2 (unixware) host. */
1227 double tmp1 = ((double) local_reg_freq[regno] * local_reg_n_refs[regno]
1228 / local_reg_live_length[regno]);
1229 double tmp2 = ((double) allocno[num].freq * allocno[num].n_refs
1230 / allocno[num].live_length);
1234 /* Hard reg REGNO was used less in total by local regs
1235 than it would be used by this one allocno! */
1239 fprintf (dump_file, "Regno %d better for global %d, ",
1240 regno, allocno[num].reg);
1241 fprintf (dump_file, "fr:%d, ll:%d, nr:%d ",
1242 allocno[num].freq, allocno[num].live_length,
1243 allocno[num].n_refs);
1244 fprintf (dump_file, "(was: fr:%d, ll:%d, nr:%d)\n",
1245 local_reg_freq[regno],
1246 local_reg_live_length[regno],
1247 local_reg_n_refs[regno]);
1250 for (k = 0; k < max_regno; k++)
1251 if (reg_renumber[k] >= 0)
1253 int r = reg_renumber[k];
1255 = end_hard_regno (PSEUDO_REGNO_MODE (k), r);
1257 if (regno >= r && regno < endregno)
1261 "Local Reg %d now on stack\n", k);
1262 reg_renumber[k] = -1;
1273 /* Did we find a register? */
1278 HARD_REG_SET this_reg;
1281 /* Yes. Record it as the hard register of this pseudo-reg. */
1282 reg_renumber[allocno[num].reg] = best_reg;
1284 /* Make a set of the hard regs being allocated. */
1285 CLEAR_HARD_REG_SET (this_reg);
1286 lim = end_hard_regno (mode, best_reg);
1287 for (j = best_reg; j < lim; j++)
1289 SET_HARD_REG_BIT (this_reg, j);
1290 SET_HARD_REG_BIT (regs_used_so_far, j);
1291 /* This is no longer a reg used just by local regs. */
1292 local_reg_n_refs[j] = 0;
1293 local_reg_freq[j] = 0;
1295 /* For each other pseudo-reg conflicting with this one,
1296 mark it as conflicting with the hard regs this one occupies. */
1297 FOR_EACH_CONFLICT (num, j, ai)
1299 IOR_HARD_REG_SET (allocno[j].hard_reg_conflicts, this_reg);
1304 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1305 Perhaps it had previously seemed not worth a hard reg,
1306 or perhaps its old hard reg has been commandeered for reloads.
1307 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1308 they do not appear to be allocated.
1309 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1312 retry_global_alloc (int regno, HARD_REG_SET forbidden_regs)
1314 int alloc_no = reg_allocno[regno];
1317 /* If we have more than one register class,
1318 first try allocating in the class that is cheapest
1319 for this pseudo-reg. If that fails, try any reg. */
1320 if (N_REG_CLASSES > 1)
1321 find_reg (alloc_no, forbidden_regs, 0, 0, 1);
1322 if (reg_renumber[regno] < 0
1323 && reg_alternate_class (regno) != NO_REGS)
1324 find_reg (alloc_no, forbidden_regs, 1, 0, 1);
1326 /* If we found a register, modify the RTL for the register to
1327 show the hard register, and mark that register live. */
1328 if (reg_renumber[regno] >= 0)
1330 SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
1331 mark_home_live (regno);
1336 /* Indicate that hard register number FROM was eliminated and replaced with
1337 an offset from hard register number TO. The status of hard registers live
1338 at the start of a basic block is updated by replacing a use of FROM with
1342 mark_elimination (int from, int to)
1348 regset r = DF_LIVE_IN (bb);
1349 if (REGNO_REG_SET_P (r, from))
1351 CLEAR_REGNO_REG_SET (r, from);
1352 SET_REGNO_REG_SET (r, to);
1358 print_insn_chain (FILE *file, struct insn_chain *c)
1360 fprintf (file, "insn=%d, ", INSN_UID(c->insn));
1361 bitmap_print (file, &c->live_throughout, "live_throughout: ", ", ");
1362 bitmap_print (file, &c->dead_or_set, "dead_or_set: ", "\n");
1366 print_insn_chains (FILE *file)
1368 struct insn_chain *c;
1369 for (c = reload_insn_chain; c ; c = c->next)
1370 print_insn_chain (file, c);
1372 /* Walk the insns of the current function and build reload_insn_chain,
1373 and record register life information. */
1375 build_insn_chain (void)
1378 struct insn_chain **p = &reload_insn_chain;
1380 struct insn_chain *c = NULL;
1381 struct insn_chain *next = NULL;
1382 bitmap live_relevant_regs = BITMAP_ALLOC (NULL);
1383 bitmap elim_regset = BITMAP_ALLOC (NULL);
1384 /* live_subregs is a vector used to keep accurate information about
1385 which hardregs are live in multiword pseudos. live_subregs and
1386 live_subregs_used are indexed by pseudo number. The live_subreg
1387 entry for a particular pseudo is only used if the corresponding
1388 element is non zero in live_subregs_used. The value in
1389 live_subregs_used is number of bytes that the pseudo can
1391 sbitmap *live_subregs = XCNEWVEC (sbitmap, max_regno);
1392 int *live_subregs_used = XNEWVEC (int, max_regno);
1394 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1395 if (TEST_HARD_REG_BIT (eliminable_regset, i))
1396 bitmap_set_bit (elim_regset, i);
1398 FOR_EACH_BB_REVERSE (bb)
1403 CLEAR_REG_SET (live_relevant_regs);
1404 memset (live_subregs_used, 0, max_regno * sizeof (int));
1406 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb), 0, i, bi)
1408 if (i >= FIRST_PSEUDO_REGISTER)
1410 bitmap_set_bit (live_relevant_regs, i);
1413 EXECUTE_IF_SET_IN_BITMAP (df_get_live_out (bb), FIRST_PSEUDO_REGISTER, i, bi)
1415 if (reg_renumber[i] >= 0)
1416 bitmap_set_bit (live_relevant_regs, i);
1419 FOR_BB_INSNS_REVERSE (bb, insn)
1421 if (!NOTE_P (insn) && !BARRIER_P (insn))
1423 unsigned int uid = INSN_UID (insn);
1424 struct df_ref **def_rec;
1425 struct df_ref **use_rec;
1427 c = new_insn_chain ();
1434 c->block = bb->index;
1437 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
1439 struct df_ref *def = *def_rec;
1440 unsigned int regno = DF_REF_REGNO (def);
1442 /* Ignore may clobbers because these are generated
1443 from calls. However, every other kind of def is
1444 added to dead_or_set. */
1445 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1447 if (regno < FIRST_PSEUDO_REGISTER)
1449 if (! fixed_regs[regno])
1450 bitmap_set_bit (&c->dead_or_set, regno);
1452 else if (reg_renumber[regno] >= 0)
1453 bitmap_set_bit (&c->dead_or_set, regno);
1456 if ((regno < FIRST_PSEUDO_REGISTER || reg_renumber[regno] >= 0)
1457 && (!DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)))
1459 rtx reg = DF_REF_REG (def);
1460 /* We can model subregs, but not if they are
1461 wrapped in ZERO_EXTRACTS. */
1462 if (GET_CODE (reg) == SUBREG
1463 && !DF_REF_FLAGS_IS_SET (def, DF_REF_EXTRACT))
1465 unsigned int start = SUBREG_BYTE (reg);
1466 unsigned int last = start + GET_MODE_SIZE (GET_MODE (reg));
1468 ra_init_live_subregs (bitmap_bit_p (live_relevant_regs, regno),
1469 live_subregs, live_subregs_used,
1471 /* Ignore the paradoxical bits. */
1472 if ((int)last > live_subregs_used[regno])
1473 last = live_subregs_used[regno];
1475 while (start < last)
1477 RESET_BIT (live_subregs[regno], start);
1481 if (sbitmap_empty_p (live_subregs[regno]))
1483 live_subregs_used[regno] = 0;
1484 bitmap_clear_bit (live_relevant_regs, regno);
1487 /* Set live_relevant_regs here because
1488 that bit has to be true to get us to
1489 look at the live_subregs fields. */
1490 bitmap_set_bit (live_relevant_regs, regno);
1494 /* DF_REF_PARTIAL is generated for
1495 subregs, STRICT_LOW_PART, and
1496 ZERO_EXTRACT. We handle the subreg
1497 case above so here we have to keep from
1498 modeling the def as a killing def. */
1499 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL))
1501 bitmap_clear_bit (live_relevant_regs, regno);
1502 live_subregs_used[regno] = 0;
1508 bitmap_and_compl_into (live_relevant_regs, elim_regset);
1509 bitmap_copy (&c->live_throughout, live_relevant_regs);
1512 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
1514 struct df_ref *use = *use_rec;
1515 unsigned int regno = DF_REF_REGNO (use);
1516 rtx reg = DF_REF_REG (use);
1518 /* DF_REF_READ_WRITE on a use means that this use
1519 is fabricated from a def that is a partial set
1520 to a multiword reg. Here, we only model the
1521 subreg case that is not wrapped in ZERO_EXTRACT
1522 precisely so we do not need to look at the
1524 if (DF_REF_FLAGS_IS_SET (use, DF_REF_READ_WRITE)
1525 && !DF_REF_FLAGS_IS_SET (use, DF_REF_EXTRACT)
1526 && DF_REF_FLAGS_IS_SET (use, DF_REF_SUBREG))
1529 /* Add the last use of each var to dead_or_set. */
1530 if (!bitmap_bit_p (live_relevant_regs, regno))
1532 if (regno < FIRST_PSEUDO_REGISTER)
1534 if (! fixed_regs[regno])
1535 bitmap_set_bit (&c->dead_or_set, regno);
1537 else if (reg_renumber[regno] >= 0)
1538 bitmap_set_bit (&c->dead_or_set, regno);
1541 if (regno < FIRST_PSEUDO_REGISTER || reg_renumber[regno] >= 0)
1543 if (GET_CODE (reg) == SUBREG
1544 && !DF_REF_FLAGS_IS_SET (use, DF_REF_EXTRACT))
1546 unsigned int start = SUBREG_BYTE (reg);
1547 unsigned int last = start + GET_MODE_SIZE (GET_MODE (reg));
1549 ra_init_live_subregs (bitmap_bit_p (live_relevant_regs, regno),
1550 live_subregs, live_subregs_used,
1553 /* Ignore the paradoxical bits. */
1554 if ((int)last > live_subregs_used[regno])
1555 last = live_subregs_used[regno];
1557 while (start < last)
1559 SET_BIT (live_subregs[regno], start);
1564 /* Resetting the live_subregs_used is
1565 effectively saying do not use the subregs
1566 because we are reading the whole
1568 live_subregs_used[regno] = 0;
1569 bitmap_set_bit (live_relevant_regs, regno);
1576 for (i = 0; i < (unsigned int)max_regno; i++)
1577 if (live_subregs[i])
1578 free (live_subregs[i]);
1580 reload_insn_chain = c;
1583 free (live_subregs);
1584 free (live_subregs_used);
1585 BITMAP_FREE (live_relevant_regs);
1586 BITMAP_FREE (elim_regset);
1589 print_insn_chains (dump_file);
1592 /* Print debugging trace information if -dg switch is given,
1593 showing the information on which the allocation decisions are based. */
1596 dump_conflicts (FILE *file)
1600 int has_preferences;
1603 for (i = 0; i < max_allocno; i++)
1605 if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
1609 fprintf (file, ";; %d regs to allocate:", nregs);
1610 for (regno = 0; regno < max_regno; regno++)
1611 if ((i = reg_allocno[regno]) >= 0)
1614 if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
1616 fprintf (file, " %d", allocno[allocno_order[i]].reg);
1617 for (j = 0; j < max_regno; j++)
1618 if (reg_allocno[j] == allocno_order[i]
1619 && j != allocno[allocno_order[i]].reg)
1620 fprintf (file, "+%d", j);
1621 if (allocno[allocno_order[i]].size != 1)
1622 fprintf (file, " (%d)", allocno[allocno_order[i]].size);
1624 fprintf (file, "\n");
1626 for (regno = 0; regno < max_regno; regno++)
1627 if ((i = reg_allocno[regno]) >= 0)
1631 fprintf (file, ";; %d conflicts:", allocno[i].reg);
1632 FOR_EACH_CONFLICT (i, j, ai)
1634 fprintf (file, " %d", allocno[j].reg);
1636 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1637 if (TEST_HARD_REG_BIT (allocno[i].hard_reg_conflicts, j)
1639 fprintf (file, " %d", j);
1640 fprintf (file, "\n");
1642 has_preferences = 0;
1643 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1644 if (TEST_HARD_REG_BIT (allocno[i].hard_reg_preferences, j))
1645 has_preferences = 1;
1647 if (!has_preferences)
1649 fprintf (file, ";; %d preferences:", allocno[i].reg);
1650 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1651 if (TEST_HARD_REG_BIT (allocno[i].hard_reg_preferences, j))
1652 fprintf (file, " %d", j);
1653 fprintf (file, "\n");
1655 fprintf (file, "\n");
1659 dump_global_regs (FILE *file)
1663 fprintf (file, ";; Register dispositions:\n");
1664 for (i = FIRST_PSEUDO_REGISTER, j = 0; i < max_regno; i++)
1665 if (reg_renumber[i] >= 0)
1667 fprintf (file, "%d in %d ", i, reg_renumber[i]);
1669 fprintf (file, "\n");
1672 fprintf (file, "\n\n;; Hard regs used: ");
1673 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1674 if (df_regs_ever_live_p (i))
1675 fprintf (file, " %d", i);
1676 fprintf (file, "\n\n");
1679 /* Run old register allocator. Return TRUE if we must exit
1680 rest_of_compilation upon return. */
1682 rest_of_handle_global_alloc (void)
1686 /* If optimizing, allocate remaining pseudo-regs. Do the reload
1687 pass fixing up any insns that are invalid. */
1688 if (optimize && dbg_cnt (global_alloc_at_func))
1689 failure = global_alloc ();
1692 /* There is just too much going on in the register allocators to
1693 keep things up to date. At the end we have to rescan anyway
1694 because things change when the reload_completed flag is set.
1695 So we just turn off scanning and we will rescan by hand. */
1696 df_set_flags (DF_NO_INSN_RESCAN);
1697 compute_regsets (&eliminable_regset, &no_global_alloc_regs);
1698 build_insn_chain ();
1699 df_set_flags (DF_NO_INSN_RESCAN);
1700 failure = reload (get_insns (), 0);
1703 if (dump_enabled_p (pass_global_alloc.static_pass_number))
1705 timevar_push (TV_DUMP);
1706 dump_global_regs (dump_file);
1707 timevar_pop (TV_DUMP);
1710 /* FIXME: This appears on the surface to be wrong thing to be doing.
1711 So much of the compiler is designed to check reload_completed to
1712 see if it is running after reload that seems doomed to failure.
1713 We should be returning a value that says that we have found
1714 errors so that nothing but the cleanup passes are run
1716 gcc_assert (reload_completed || failure);
1717 reload_completed = !failure;
1719 /* The world has changed so much that at this point we might as well
1720 just rescan everything. Not that df_rescan_all_insns is not
1721 going to help here because it does not touch the artificial uses
1723 df_finish_pass (true);
1725 df_live_add_problem ();
1726 df_scan_alloc (NULL);
1732 regstat_free_n_sets_and_refs ();
1737 struct tree_opt_pass pass_global_alloc =
1741 rest_of_handle_global_alloc, /* execute */
1744 0, /* static_pass_number */
1745 TV_GLOBAL_ALLOC, /* tv_id */
1746 0, /* properties_required */
1747 0, /* properties_provided */
1748 0, /* properties_destroyed */
1749 0, /* todo_flags_start */
1750 TODO_dump_func | TODO_verify_rtl_sharing
1751 | TODO_ggc_collect, /* todo_flags_finish */