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 2, 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 COPYING. If not, write to the Free
20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
26 #include "coretypes.h"
29 #include "hard-reg-set.h"
35 #include "insn-config.h"
40 #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 conflict bit matrix and clear it.
67 Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix
68 for conflicts between allocnos and explicit hard register use
69 (which includes use of pseudo-registers allocated by local_alloc).
71 3. For each basic block
72 walk forward through the block, recording which
73 pseudo-registers and which hardware registers are live.
74 Build the conflict matrix between the pseudo-registers
75 and another of pseudo-registers versus hardware registers.
76 Also record the preferred hardware registers
77 for each pseudo-register.
79 4. Sort a table of the allocnos into order of
80 desirability of the variables.
82 5. Allocate the variables in that order; each if possible into
83 a preferred register, else into another register. */
85 /* Number of pseudo-registers which are candidates for allocation. */
87 static int max_allocno;
89 /* Indexed by (pseudo) reg number, gives the allocno, or -1
90 for pseudo registers which are not to be allocated. */
92 static int *reg_allocno;
97 /* Gives the number of consecutive hard registers needed by that
101 /* Number of calls crossed by each allocno. */
104 /* Number of calls that might throw crossed by each allocno. */
105 int throwing_calls_crossed;
107 /* Number of refs to each allocno. */
110 /* Frequency of uses of each allocno. */
113 /* Guess at live length of each allocno.
114 This is actually the max of the live lengths of the regs. */
117 /* Set of hard regs conflicting with allocno N. */
119 HARD_REG_SET hard_reg_conflicts;
121 /* Set of hard regs preferred by allocno N.
122 This is used to make allocnos go into regs that are copied to or from them,
123 when possible, to reduce register shuffling. */
125 HARD_REG_SET hard_reg_preferences;
127 /* Similar, but just counts register preferences made in simple copy
128 operations, rather than arithmetic. These are given priority because
129 we can always eliminate an insn by using these, but using a register
130 in the above list won't always eliminate an insn. */
132 HARD_REG_SET hard_reg_copy_preferences;
134 /* Similar to hard_reg_preferences, but includes bits for subsequent
135 registers when an allocno is multi-word. The above variable is used for
136 allocation while this is used to build reg_someone_prefers, below. */
138 HARD_REG_SET hard_reg_full_preferences;
140 /* Set of hard registers that some later allocno has a preference for. */
142 HARD_REG_SET regs_someone_prefers;
145 /* Set to true if allocno can't be allocated in the stack register. */
150 static struct allocno *allocno;
152 /* A vector of the integers from 0 to max_allocno-1,
153 sorted in the order of first-to-be-allocated first. */
155 static int *allocno_order;
157 /* Define the number of bits in each element of `conflicts' and what
158 type that element has. We use the largest integer format on the
161 #define INT_BITS HOST_BITS_PER_WIDE_INT
162 #define INT_TYPE HOST_WIDE_INT
164 /* max_allocno by max_allocno array of bits,
165 recording whether two allocno's conflict (can't go in the same
168 `conflicts' is symmetric after the call to mirror_conflicts. */
170 static INT_TYPE *conflicts;
172 /* Number of ints required to hold max_allocno bits.
173 This is the length of a row in `conflicts'. */
175 static int allocno_row_words;
177 /* Two macros to test or store 1 in an element of `conflicts'. */
179 #define CONFLICTP(I, J) \
180 (conflicts[(I) * allocno_row_words + (unsigned) (J) / INT_BITS] \
181 & ((INT_TYPE) 1 << ((unsigned) (J) % INT_BITS)))
183 /* For any allocno set in ALLOCNO_SET, set ALLOCNO to that allocno,
185 #define EXECUTE_IF_SET_IN_ALLOCNO_SET(ALLOCNO_SET, ALLOCNO, CODE) \
189 INT_TYPE *p_ = (ALLOCNO_SET); \
191 for (i_ = allocno_row_words - 1, allocno_ = 0; i_ >= 0; \
192 i_--, allocno_ += INT_BITS) \
194 unsigned INT_TYPE word_ = (unsigned INT_TYPE) *p_++; \
196 for ((ALLOCNO) = allocno_; word_; word_ >>= 1, (ALLOCNO)++) \
204 /* Set of hard regs currently live (during scan of all insns). */
206 static HARD_REG_SET hard_regs_live;
208 /* Set of registers that global-alloc isn't supposed to use. */
210 static HARD_REG_SET no_global_alloc_regs;
212 /* Set of registers used so far. */
214 static HARD_REG_SET regs_used_so_far;
216 /* Number of refs to each hard reg, as used by local alloc.
217 It is zero for a reg that contains global pseudos or is explicitly used. */
219 static int local_reg_n_refs[FIRST_PSEUDO_REGISTER];
221 /* Frequency of uses of given hard reg. */
222 static int local_reg_freq[FIRST_PSEUDO_REGISTER];
224 /* Guess at live length of each hard reg, as used by local alloc.
225 This is actually the sum of the live lengths of the specific regs. */
227 static int local_reg_live_length[FIRST_PSEUDO_REGISTER];
229 /* Set to 1 a bit in a vector TABLE of HARD_REG_SETs, for vector
230 element I, and hard register number J. */
232 #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (allocno[I].TABLE, J)
234 /* Bit mask for allocnos live at current point in the scan. */
236 static INT_TYPE *allocnos_live;
238 /* Test, set or clear bit number I in allocnos_live,
239 a bit vector indexed by allocno. */
241 #define SET_ALLOCNO_LIVE(I) \
242 (allocnos_live[(unsigned) (I) / INT_BITS] \
243 |= ((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS)))
245 #define CLEAR_ALLOCNO_LIVE(I) \
246 (allocnos_live[(unsigned) (I) / INT_BITS] \
247 &= ~((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS)))
249 /* This is turned off because it doesn't work right for DImode.
250 (And it is only used for DImode, so the other cases are worthless.)
251 The problem is that it isn't true that there is NO possibility of conflict;
252 only that there is no conflict if the two pseudos get the exact same regs.
253 If they were allocated with a partial overlap, there would be a conflict.
254 We can't safely turn off the conflict unless we have another way to
255 prevent the partial overlap.
257 Idea: change hard_reg_conflicts so that instead of recording which
258 hard regs the allocno may not overlap, it records where the allocno
259 may not start. Change both where it is used and where it is updated.
260 Then there is a way to record that (reg:DI 108) may start at 10
261 but not at 9 or 11. There is still the question of how to record
262 this semi-conflict between two pseudos. */
264 /* Reg pairs for which conflict after the current insn
265 is inhibited by a REG_NO_CONFLICT note.
266 If the table gets full, we ignore any other notes--that is conservative. */
267 #define NUM_NO_CONFLICT_PAIRS 4
268 /* Number of pairs in use in this insn. */
269 int n_no_conflict_pairs;
270 static struct { int allocno1, allocno2;}
271 no_conflict_pairs[NUM_NO_CONFLICT_PAIRS];
274 /* Record all regs that are set in any one insn.
275 Communication from mark_reg_{store,clobber} and global_conflicts. */
277 static VEC(rtx, heap) *regs_set;
280 /* Return true if *LOC contains an asm. */
283 insn_contains_asm_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
287 if (GET_CODE (*loc) == ASM_OPERANDS)
293 /* Return true if INSN contains an ASM. */
296 insn_contains_asm (rtx insn)
298 return for_each_rtx (&insn, insn_contains_asm_1, NULL);
303 compute_regs_asm_clobbered (char *regs_asm_clobbered)
307 memset (regs_asm_clobbered, 0, sizeof (char) * FIRST_PSEUDO_REGISTER);
312 FOR_BB_INSNS_REVERSE (bb, insn)
314 struct df_ref **def_rec;
315 if (insn_contains_asm (insn))
316 for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
318 struct df_ref *def = *def_rec;
319 unsigned int dregno = DF_REF_REGNO (def);
320 if (dregno < FIRST_PSEUDO_REGISTER)
323 enum machine_mode mode = GET_MODE (DF_REF_REAL_REG (def));
324 unsigned int end = dregno
325 + hard_regno_nregs[dregno][mode] - 1;
326 for (i = dregno; i <= end; ++i)
327 regs_asm_clobbered[i] = 1;
335 /* All registers that can be eliminated. */
337 static HARD_REG_SET eliminable_regset;
339 static int allocno_compare (const void *, const void *);
340 static void global_conflicts (void);
341 static void mirror_conflicts (void);
342 static void expand_preferences (void);
343 static void prune_preferences (void);
344 static void find_reg (int, HARD_REG_SET, int, int, int);
345 static void record_one_conflict (int);
346 static void record_conflicts (int *, int);
347 static void mark_reg_store (rtx, rtx, void *);
348 static void mark_reg_clobber (rtx, rtx, void *);
349 static void mark_reg_conflicts (rtx);
350 static void mark_reg_death (rtx);
351 static void set_preference (rtx, rtx);
352 static void dump_conflicts (FILE *);
353 static void reg_becomes_live (rtx, rtx, void *);
354 static void reg_dies (int, enum machine_mode, struct insn_chain *);
359 /* Look through the list of eliminable registers. Set ELIM_SET to the
360 set of registers which may be eliminated. Set NO_GLOBAL_SET to the
361 set of registers which may not be used across blocks.
363 This will normally be called with ELIM_SET as the file static
364 variable eliminable_regset, and NO_GLOBAL_SET as the file static
365 variable NO_GLOBAL_ALLOC_REGS. */
368 compute_regsets (HARD_REG_SET *elim_set,
369 HARD_REG_SET *no_global_set)
372 /* Like regs_ever_live, but 1 if a reg is set or clobbered from an asm.
373 Unlike regs_ever_live, elements of this array corresponding to
374 eliminable regs like the frame pointer are set if an asm sets them. */
375 char *regs_asm_clobbered = alloca (FIRST_PSEUDO_REGISTER * sizeof (char));
377 #ifdef ELIMINABLE_REGS
378 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
382 = (! flag_omit_frame_pointer
383 || (current_function_calls_alloca && EXIT_IGNORE_STACK)
384 || FRAME_POINTER_REQUIRED);
386 max_regno = max_reg_num ();
391 /* A machine may have certain hard registers that
392 are safe to use only within a basic block. */
394 CLEAR_HARD_REG_SET (*no_global_set);
395 CLEAR_HARD_REG_SET (*elim_set);
397 compute_regs_asm_clobbered (regs_asm_clobbered);
398 /* Build the regset of all eliminable registers and show we can't use those
399 that we already know won't be eliminated. */
400 #ifdef ELIMINABLE_REGS
401 for (i = 0; i < ARRAY_SIZE (eliminables); i++)
404 = (! CAN_ELIMINATE (eliminables[i].from, eliminables[i].to)
405 || (eliminables[i].to == STACK_POINTER_REGNUM && need_fp));
407 if (!regs_asm_clobbered[eliminables[i].from])
409 SET_HARD_REG_BIT (*elim_set, eliminables[i].from);
412 SET_HARD_REG_BIT (*no_global_set, eliminables[i].from);
414 else if (cannot_elim)
415 error ("%s cannot be used in asm here",
416 reg_names[eliminables[i].from]);
418 df_set_regs_ever_live (eliminables[i].from, true);
420 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
421 if (!regs_asm_clobbered[HARD_FRAME_POINTER_REGNUM])
423 SET_HARD_REG_BIT (*elim_set, HARD_FRAME_POINTER_REGNUM);
425 SET_HARD_REG_BIT (*no_global_set, HARD_FRAME_POINTER_REGNUM);
428 error ("%s cannot be used in asm here",
429 reg_names[HARD_FRAME_POINTER_REGNUM]);
431 df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM, true);
435 if (!regs_asm_clobbered[FRAME_POINTER_REGNUM])
437 SET_HARD_REG_BIT (*elim_set, FRAME_POINTER_REGNUM);
439 SET_HARD_REG_BIT (*no_global_set, FRAME_POINTER_REGNUM);
442 error ("%s cannot be used in asm here", reg_names[FRAME_POINTER_REGNUM]);
444 df_set_regs_ever_live (FRAME_POINTER_REGNUM, true);
448 /* Perform allocation of pseudo-registers not allocated by local_alloc.
450 Return value is nonzero if reload failed
451 and we must not do any more for this function. */
459 compute_regsets (&eliminable_regset, &no_global_alloc_regs);
461 /* Track which registers have already been used. Start with registers
462 explicitly in the rtl, then registers allocated by local register
465 CLEAR_HARD_REG_SET (regs_used_so_far);
466 #ifdef LEAF_REGISTERS
467 /* If we are doing the leaf function optimization, and this is a leaf
468 function, it means that the registers that take work to save are those
469 that need a register window. So prefer the ones that can be used in
472 const char *cheap_regs;
473 const char *const leaf_regs = LEAF_REGISTERS;
475 if (only_leaf_regs_used () && leaf_function_p ())
476 cheap_regs = leaf_regs;
478 cheap_regs = call_used_regs;
479 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
480 if (df_regs_ever_live_p (i) || cheap_regs[i])
481 SET_HARD_REG_BIT (regs_used_so_far, i);
484 /* We consider registers that do not have to be saved over calls as if
485 they were already used since there is no cost in using them. */
486 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
487 if (df_regs_ever_live_p (i) || call_used_regs[i])
488 SET_HARD_REG_BIT (regs_used_so_far, i);
491 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
492 if (reg_renumber[i] >= 0)
493 SET_HARD_REG_BIT (regs_used_so_far, reg_renumber[i]);
495 /* Establish mappings from register number to allocation number
496 and vice versa. In the process, count the allocnos. */
498 reg_allocno = XNEWVEC (int, max_regno);
500 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
504 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
505 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
506 that we are supposed to refrain from putting in a hard reg.
507 -2 means do make an allocno but don't allocate it. */
508 if (REG_N_REFS (i) != 0 && REG_LIVE_LENGTH (i) != -1
509 /* Don't allocate pseudos that cross calls,
510 if this function receives a nonlocal goto. */
511 && (! current_function_has_nonlocal_label
512 || REG_N_CALLS_CROSSED (i) == 0))
514 reg_allocno[i] = max_allocno++;
515 gcc_assert (REG_LIVE_LENGTH (i));
520 allocno = XCNEWVEC (struct allocno, max_allocno);
522 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
523 if (reg_allocno[i] >= 0)
525 int num = reg_allocno[i];
526 allocno[num].reg = i;
527 allocno[num].size = PSEUDO_REGNO_SIZE (i);
528 allocno[num].calls_crossed += REG_N_CALLS_CROSSED (i);
529 allocno[num].throwing_calls_crossed
530 += REG_N_THROWING_CALLS_CROSSED (i);
531 allocno[num].n_refs += REG_N_REFS (i);
532 allocno[num].freq += REG_FREQ (i);
533 if (allocno[num].live_length < REG_LIVE_LENGTH (i))
534 allocno[num].live_length = REG_LIVE_LENGTH (i);
537 /* Calculate amount of usage of each hard reg by pseudos
538 allocated by local-alloc. This is to see if we want to
540 memset (local_reg_live_length, 0, sizeof local_reg_live_length);
541 memset (local_reg_n_refs, 0, sizeof local_reg_n_refs);
542 memset (local_reg_freq, 0, sizeof local_reg_freq);
543 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
544 if (reg_renumber[i] >= 0)
546 int regno = reg_renumber[i];
547 int endregno = end_hard_regno (PSEUDO_REGNO_MODE (i), regno);
550 for (j = regno; j < endregno; j++)
552 local_reg_n_refs[j] += REG_N_REFS (i);
553 local_reg_freq[j] += REG_FREQ (i);
554 local_reg_live_length[j] += REG_LIVE_LENGTH (i);
558 /* We can't override local-alloc for a reg used not just by local-alloc. */
559 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
560 if (df_regs_ever_live_p (i))
561 local_reg_n_refs[i] = 0, local_reg_freq[i] = 0;
565 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
567 fprintf (dump_file, "%d REG_N_REFS=%d, REG_FREQ=%d, REG_LIVE_LENGTH=%d\n",
568 (int)i, REG_N_REFS (i), REG_FREQ (i), REG_LIVE_LENGTH (i));
570 fprintf (dump_file, "regs_ever_live =");
571 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
572 if (df_regs_ever_live_p (i))
573 fprintf (dump_file, " %d", (int)i);
574 fprintf (dump_file, "\n");
576 allocno_row_words = (max_allocno + INT_BITS - 1) / INT_BITS;
578 /* We used to use alloca here, but the size of what it would try to
579 allocate would occasionally cause it to exceed the stack limit and
580 cause unpredictable core dumps. Some examples were > 2Mb in size. */
581 conflicts = XCNEWVEC (INT_TYPE, max_allocno * allocno_row_words);
583 allocnos_live = XNEWVEC (INT_TYPE, allocno_row_words);
585 /* If there is work to be done (at least one reg to allocate),
586 perform global conflict analysis and allocate the regs. */
590 /* Make a vector that mark_reg_{store,clobber} will store in. */
592 regs_set = VEC_alloc (rtx, heap, 10);
594 /* Scan all the insns and compute the conflicts among allocnos
595 and between allocnos and hard regs. */
601 /* Eliminate conflicts between pseudos and eliminable registers. If
602 the register is not eliminated, the pseudo won't really be able to
603 live in the eliminable register, so the conflict doesn't matter.
604 If we do eliminate the register, the conflict will no longer exist.
605 So in either case, we can ignore the conflict. Likewise for
608 for (i = 0; i < (size_t) max_allocno; i++)
610 AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_conflicts,
612 AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_copy_preferences,
614 AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_preferences,
618 /* Try to expand the preferences by merging them between allocnos. */
620 expand_preferences ();
622 /* Determine the order to allocate the remaining pseudo registers. */
624 allocno_order = XNEWVEC (int, max_allocno);
625 for (i = 0; i < (size_t) max_allocno; i++)
626 allocno_order[i] = i;
628 /* Default the size to 1, since allocno_compare uses it to divide by.
629 Also convert allocno_live_length of zero to -1. A length of zero
630 can occur when all the registers for that allocno have reg_live_length
631 equal to -2. In this case, we want to make an allocno, but not
632 allocate it. So avoid the divide-by-zero and set it to a low
635 for (i = 0; i < (size_t) max_allocno; i++)
637 if (allocno[i].size == 0)
639 if (allocno[i].live_length == 0)
640 allocno[i].live_length = -1;
643 qsort (allocno_order, max_allocno, sizeof (int), allocno_compare);
645 prune_preferences ();
648 dump_conflicts (dump_file);
650 /* Try allocating them, one by one, in that order,
651 except for parameters marked with reg_live_length[regno] == -2. */
653 for (i = 0; i < (size_t) max_allocno; i++)
654 if (reg_renumber[allocno[allocno_order[i]].reg] < 0
655 && REG_LIVE_LENGTH (allocno[allocno_order[i]].reg) >= 0)
657 if (!dbg_cnt (global_alloc_at_reg))
659 /* If we have more than one register class,
660 first try allocating in the class that is cheapest
661 for this pseudo-reg. If that fails, try any reg. */
662 if (N_REG_CLASSES > 1)
664 find_reg (allocno_order[i], 0, 0, 0, 0);
665 if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
668 if (reg_alternate_class (allocno[allocno_order[i]].reg) != NO_REGS)
669 find_reg (allocno_order[i], 0, 1, 0, 0);
672 free (allocno_order);
675 /* Do the reloads now while the allocno data still exists, so that we can
676 try to assign new hard regs to any pseudo regs that are spilled. */
678 #if 0 /* We need to eliminate regs even if there is no rtl code,
679 for the sake of debugging information. */
680 if (n_basic_blocks > NUM_FIXED_BLOCKS)
683 build_insn_chain (get_insns ());
684 retval = reload (get_insns (), 1);
691 free (allocnos_live);
696 /* Sort predicate for ordering the allocnos.
697 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
700 allocno_compare (const void *v1p, const void *v2p)
702 int v1 = *(const int *)v1p, v2 = *(const int *)v2p;
703 /* Note that the quotient will never be bigger than
704 the value of floor_log2 times the maximum number of
705 times a register can occur in one insn (surely less than 100)
706 weighted by the frequency (maximally REG_FREQ_MAX).
707 Multiplying this by 10000/REG_FREQ_MAX can't overflow. */
709 = (((double) (floor_log2 (allocno[v1].n_refs) * allocno[v1].freq)
710 / allocno[v1].live_length)
711 * (10000 / REG_FREQ_MAX) * allocno[v1].size);
713 = (((double) (floor_log2 (allocno[v2].n_refs) * allocno[v2].freq)
714 / allocno[v2].live_length)
715 * (10000 / REG_FREQ_MAX) * allocno[v2].size);
719 /* If regs are equally good, sort by allocno,
720 so that the results of qsort leave nothing to chance. */
724 /* Scan the rtl code and record all conflicts and register preferences in the
725 conflict matrices and preference tables. */
728 global_conflicts (void)
733 int *block_start_allocnos;
735 block_start_allocnos = XNEWVEC (int, max_allocno);
739 memset (allocnos_live, 0, allocno_row_words * sizeof (INT_TYPE));
741 /* Initialize table of registers currently live
742 to the state at the beginning of this basic block.
743 This also marks the conflicts among hard registers
744 and any allocnos that are live.
746 For pseudo-regs, there is only one bit for each one
747 no matter how many hard regs it occupies.
748 This is ok; we know the size from PSEUDO_REGNO_SIZE.
749 For explicit hard regs, we cannot know the size that way
750 since one hard reg can be used with various sizes.
751 Therefore, we must require that all the hard regs
752 implicitly live as part of a multi-word hard reg
753 be explicitly marked in basic_block_live_at_start. */
757 reg_set_iterator rsi;
759 REG_SET_TO_HARD_REG_SET (hard_regs_live, DF_RA_LIVE_TOP (b));
760 EXECUTE_IF_SET_IN_REG_SET (DF_RA_LIVE_TOP (b), FIRST_PSEUDO_REGISTER, i, rsi)
762 int a = reg_allocno[i];
765 SET_ALLOCNO_LIVE (a);
766 block_start_allocnos[ax++] = a;
768 else if ((a = reg_renumber[i]) >= 0)
769 add_to_hard_reg_set (&hard_regs_live, PSEUDO_REGNO_MODE (i), a);
772 /* Record that each allocno now live conflicts with each hard reg
775 It is not necessary to mark any conflicts between pseudos at
776 this point, even for pseudos which are live at the start of
779 Given two pseudos X and Y and any point in the CFG P.
781 On any path to point P where X and Y are live one of the
782 following conditions must be true:
784 1. X is live at some instruction on the path that
787 2. Y is live at some instruction on the path that
790 3. Either X or Y is not evaluated on the path to P
791 (i.e. it is used uninitialized) and thus the
792 conflict can be ignored.
794 In cases #1 and #2 the conflict will be recorded when we
795 scan the instruction that makes either X or Y become live. */
796 record_conflicts (block_start_allocnos, ax);
798 #ifdef EH_RETURN_DATA_REGNO
799 if (bb_has_eh_pred (b))
805 unsigned int regno = EH_RETURN_DATA_REGNO (i);
806 if (regno == INVALID_REGNUM)
808 record_one_conflict (regno);
813 /* Pseudos can't go in stack regs at the start of a basic block that
814 is reached by an abnormal edge. Likewise for call clobbered regs,
815 because caller-save, fixup_abnormal_edges and possibly the table
816 driven EH machinery are not quite ready to handle such regs live
817 across such edges. */
822 FOR_EACH_EDGE (e, ei, b->preds)
823 if (e->flags & EDGE_ABNORMAL)
829 EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live, ax,
831 allocno[ax].no_stack_reg = 1;
833 for (ax = FIRST_STACK_REG; ax <= LAST_STACK_REG; ax++)
834 record_one_conflict (ax);
837 /* No need to record conflicts for call clobbered regs if we have
838 nonlocal labels around, as we don't ever try to allocate such
839 regs in this case. */
840 if (! current_function_has_nonlocal_label)
841 for (ax = 0; ax < FIRST_PSEUDO_REGISTER; ax++)
842 if (call_used_regs [ax])
843 record_one_conflict (ax);
850 /* Scan the code of this basic block, noting which allocnos
851 and hard regs are born or die. When one is born,
852 record a conflict with all others currently live. */
856 RTX_CODE code = GET_CODE (insn);
859 gcc_assert (VEC_empty (rtx, regs_set));
860 if (code == INSN || code == CALL_INSN || code == JUMP_INSN)
864 for (link = REG_NOTES (insn);
865 link && i < NUM_NO_CONFLICT_PAIRS;
866 link = XEXP (link, 1))
867 if (REG_NOTE_KIND (link) == REG_NO_CONFLICT)
869 no_conflict_pairs[i].allocno1
870 = reg_allocno[REGNO (SET_DEST (PATTERN (insn)))];
871 no_conflict_pairs[i].allocno2
872 = reg_allocno[REGNO (XEXP (link, 0))];
877 /* Mark any registers clobbered by INSN as live,
878 so they conflict with the inputs. */
880 note_stores (PATTERN (insn), mark_reg_clobber, NULL);
883 /* Auto-increment instructions clobber the base
885 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
886 if (REG_NOTE_KIND (link) == REG_INC)
887 mark_reg_store (XEXP (link, 0), NULL_RTX, NULL);
889 /* Mark any registers dead after INSN as dead now. */
891 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
892 if (REG_NOTE_KIND (link) == REG_DEAD)
893 mark_reg_death (XEXP (link, 0));
895 /* Mark any registers set in INSN as live,
896 and mark them as conflicting with all other live regs.
897 Clobbers are processed again, so they conflict with
898 the registers that are set. */
900 note_stores (PATTERN (insn), mark_reg_store, NULL);
902 /* If INSN has multiple outputs, then any reg that dies here
903 and is used inside of an output
904 must conflict with the other outputs.
906 It is unsafe to use !single_set here since it will ignore an
907 unused output. Just because an output is unused does not mean
908 the compiler can assume the side effect will not occur.
909 Consider if REG appears in the address of an output and we
910 reload the output. If we allocate REG to the same hard
911 register as an unused output we could set the hard register
912 before the output reload insn. */
913 if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn))
914 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
915 if (REG_NOTE_KIND (link) == REG_DEAD)
917 int used_in_output = 0;
919 rtx reg = XEXP (link, 0);
921 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
923 rtx set = XVECEXP (PATTERN (insn), 0, i);
924 if (GET_CODE (set) == SET
925 && !REG_P (SET_DEST (set))
926 && !rtx_equal_p (reg, SET_DEST (set))
927 && reg_overlap_mentioned_p (reg, SET_DEST (set)))
931 mark_reg_conflicts (reg);
934 /* Mark any registers set in INSN and then never used. */
936 while (!VEC_empty (rtx, regs_set))
938 rtx reg = VEC_pop (rtx, regs_set);
939 rtx note = find_regno_note (insn, REG_UNUSED,
942 mark_reg_death (XEXP (note, 0));
946 if (insn == BB_END (b))
948 insn = NEXT_INSN (insn);
953 free (block_start_allocnos);
956 /* Expand the preference information by looking for cases where one allocno
957 dies in an insn that sets an allocno. If those two allocnos don't conflict,
958 merge any preferences between those allocnos. */
961 expand_preferences (void)
967 /* We only try to handle the most common cases here. Most of the cases
968 where this wins are reg-reg copies. */
970 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
972 && (set = single_set (insn)) != 0
973 && REG_P (SET_DEST (set))
974 && reg_allocno[REGNO (SET_DEST (set))] >= 0)
975 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
976 if (REG_NOTE_KIND (link) == REG_DEAD
977 && REG_P (XEXP (link, 0))
978 && reg_allocno[REGNO (XEXP (link, 0))] >= 0
979 && ! CONFLICTP (reg_allocno[REGNO (SET_DEST (set))],
980 reg_allocno[REGNO (XEXP (link, 0))]))
982 int a1 = reg_allocno[REGNO (SET_DEST (set))];
983 int a2 = reg_allocno[REGNO (XEXP (link, 0))];
985 if (XEXP (link, 0) == SET_SRC (set))
987 IOR_HARD_REG_SET (allocno[a1].hard_reg_copy_preferences,
988 allocno[a2].hard_reg_copy_preferences);
989 IOR_HARD_REG_SET (allocno[a2].hard_reg_copy_preferences,
990 allocno[a1].hard_reg_copy_preferences);
993 IOR_HARD_REG_SET (allocno[a1].hard_reg_preferences,
994 allocno[a2].hard_reg_preferences);
995 IOR_HARD_REG_SET (allocno[a2].hard_reg_preferences,
996 allocno[a1].hard_reg_preferences);
997 IOR_HARD_REG_SET (allocno[a1].hard_reg_full_preferences,
998 allocno[a2].hard_reg_full_preferences);
999 IOR_HARD_REG_SET (allocno[a2].hard_reg_full_preferences,
1000 allocno[a1].hard_reg_full_preferences);
1004 /* Prune the preferences for global registers to exclude registers that cannot
1007 Compute `regs_someone_prefers', which is a bitmask of the hard registers
1008 that are preferred by conflicting registers of lower priority. If possible,
1009 we will avoid using these registers. */
1012 prune_preferences (void)
1016 int *allocno_to_order = XNEWVEC (int, max_allocno);
1018 /* Scan least most important to most important.
1019 For each allocno, remove from preferences registers that cannot be used,
1020 either because of conflicts or register type. Then compute all registers
1021 preferred by each lower-priority register that conflicts. */
1023 for (i = max_allocno - 1; i >= 0; i--)
1027 num = allocno_order[i];
1028 allocno_to_order[num] = i;
1029 COPY_HARD_REG_SET (temp, allocno[num].hard_reg_conflicts);
1031 if (allocno[num].calls_crossed == 0)
1032 IOR_HARD_REG_SET (temp, fixed_reg_set);
1034 IOR_HARD_REG_SET (temp, call_used_reg_set);
1036 IOR_COMPL_HARD_REG_SET
1038 reg_class_contents[(int) reg_preferred_class (allocno[num].reg)]);
1040 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_preferences, temp);
1041 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_copy_preferences, temp);
1042 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_full_preferences, temp);
1045 for (i = max_allocno - 1; i >= 0; i--)
1047 /* Merge in the preferences of lower-priority registers (they have
1048 already been pruned). If we also prefer some of those registers,
1049 don't exclude them unless we are of a smaller size (in which case
1050 we want to give the lower-priority allocno the first chance for
1051 these registers). */
1052 HARD_REG_SET temp, temp2;
1055 num = allocno_order[i];
1057 CLEAR_HARD_REG_SET (temp);
1058 CLEAR_HARD_REG_SET (temp2);
1060 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + num * allocno_row_words,
1063 if (allocno_to_order[allocno2] > i)
1065 if (allocno[allocno2].size <= allocno[num].size)
1066 IOR_HARD_REG_SET (temp,
1067 allocno[allocno2].hard_reg_full_preferences);
1069 IOR_HARD_REG_SET (temp2,
1070 allocno[allocno2].hard_reg_full_preferences);
1074 AND_COMPL_HARD_REG_SET (temp, allocno[num].hard_reg_full_preferences);
1075 IOR_HARD_REG_SET (temp, temp2);
1076 COPY_HARD_REG_SET (allocno[num].regs_someone_prefers, temp);
1078 free (allocno_to_order);
1081 /* Assign a hard register to allocno NUM; look for one that is the beginning
1082 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
1083 The registers marked in PREFREGS are tried first.
1085 LOSERS, if nonzero, is a HARD_REG_SET indicating registers that cannot
1086 be used for this allocation.
1088 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
1089 Otherwise ignore that preferred class and use the alternate class.
1091 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
1092 will have to be saved and restored at calls.
1094 RETRYING is nonzero if this is called from retry_global_alloc.
1096 If we find one, record it in reg_renumber.
1097 If not, do nothing. */
1100 find_reg (int num, HARD_REG_SET losers, int alt_regs_p, int accept_call_clobbered, int retrying)
1102 int i, best_reg, pass;
1103 HARD_REG_SET used, used1, used2;
1105 enum reg_class class = (alt_regs_p
1106 ? reg_alternate_class (allocno[num].reg)
1107 : reg_preferred_class (allocno[num].reg));
1108 enum machine_mode mode = PSEUDO_REGNO_MODE (allocno[num].reg);
1110 if (accept_call_clobbered)
1111 COPY_HARD_REG_SET (used1, call_fixed_reg_set);
1112 else if (allocno[num].calls_crossed == 0)
1113 COPY_HARD_REG_SET (used1, fixed_reg_set);
1115 COPY_HARD_REG_SET (used1, call_used_reg_set);
1117 /* Some registers should not be allocated in global-alloc. */
1118 IOR_HARD_REG_SET (used1, no_global_alloc_regs);
1120 IOR_HARD_REG_SET (used1, losers);
1122 IOR_COMPL_HARD_REG_SET (used1, reg_class_contents[(int) class]);
1123 COPY_HARD_REG_SET (used2, used1);
1125 IOR_HARD_REG_SET (used1, allocno[num].hard_reg_conflicts);
1127 #ifdef CANNOT_CHANGE_MODE_CLASS
1128 cannot_change_mode_set_regs (&used1, mode, allocno[num].reg);
1131 /* Try each hard reg to see if it fits. Do this in two passes.
1132 In the first pass, skip registers that are preferred by some other pseudo
1133 to give it a better chance of getting one of those registers. Only if
1134 we can't get a register when excluding those do we take one of them.
1135 However, we never allocate a register for the first time in pass 0. */
1137 COPY_HARD_REG_SET (used, used1);
1138 IOR_COMPL_HARD_REG_SET (used, regs_used_so_far);
1139 IOR_HARD_REG_SET (used, allocno[num].regs_someone_prefers);
1142 for (i = FIRST_PSEUDO_REGISTER, pass = 0;
1143 pass <= 1 && i >= FIRST_PSEUDO_REGISTER;
1147 COPY_HARD_REG_SET (used, used1);
1148 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1150 #ifdef REG_ALLOC_ORDER
1151 int regno = reg_alloc_order[i];
1155 if (! TEST_HARD_REG_BIT (used, regno)
1156 && HARD_REGNO_MODE_OK (regno, mode)
1157 && (allocno[num].calls_crossed == 0
1158 || accept_call_clobbered
1159 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
1162 int lim = end_hard_regno (mode, regno);
1165 && ! TEST_HARD_REG_BIT (used, j));
1172 #ifndef REG_ALLOC_ORDER
1173 i = j; /* Skip starting points we know will lose */
1179 /* See if there is a preferred register with the same class as the register
1180 we allocated above. Making this restriction prevents register
1181 preferencing from creating worse register allocation.
1183 Remove from the preferred registers and conflicting registers. Note that
1184 additional conflicts may have been added after `prune_preferences' was
1187 First do this for those register with copy preferences, then all
1188 preferred registers. */
1190 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_copy_preferences, used);
1191 if (!hard_reg_set_empty_p (allocno[num].hard_reg_copy_preferences)
1194 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1195 if (TEST_HARD_REG_BIT (allocno[num].hard_reg_copy_preferences, i)
1196 && HARD_REGNO_MODE_OK (i, mode)
1197 && (allocno[num].calls_crossed == 0
1198 || accept_call_clobbered
1199 || ! HARD_REGNO_CALL_PART_CLOBBERED (i, mode))
1200 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1201 || reg_class_subset_p (REGNO_REG_CLASS (i),
1202 REGNO_REG_CLASS (best_reg))
1203 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1204 REGNO_REG_CLASS (i))))
1207 int lim = end_hard_regno (mode, i);
1210 && ! TEST_HARD_REG_BIT (used, j)
1211 && (REGNO_REG_CLASS (j)
1212 == REGNO_REG_CLASS (best_reg + (j - i))
1213 || reg_class_subset_p (REGNO_REG_CLASS (j),
1214 REGNO_REG_CLASS (best_reg + (j - i)))
1215 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1216 REGNO_REG_CLASS (j))));
1226 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_preferences, used);
1227 if (!hard_reg_set_empty_p (allocno[num].hard_reg_preferences)
1230 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1231 if (TEST_HARD_REG_BIT (allocno[num].hard_reg_preferences, i)
1232 && HARD_REGNO_MODE_OK (i, mode)
1233 && (allocno[num].calls_crossed == 0
1234 || accept_call_clobbered
1235 || ! HARD_REGNO_CALL_PART_CLOBBERED (i, mode))
1236 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1237 || reg_class_subset_p (REGNO_REG_CLASS (i),
1238 REGNO_REG_CLASS (best_reg))
1239 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1240 REGNO_REG_CLASS (i))))
1243 int lim = end_hard_regno (mode, i);
1246 && ! TEST_HARD_REG_BIT (used, j)
1247 && (REGNO_REG_CLASS (j)
1248 == REGNO_REG_CLASS (best_reg + (j - i))
1249 || reg_class_subset_p (REGNO_REG_CLASS (j),
1250 REGNO_REG_CLASS (best_reg + (j - i)))
1251 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1252 REGNO_REG_CLASS (j))));
1263 /* If we haven't succeeded yet, try with caller-saves.
1264 We need not check to see if the current function has nonlocal
1265 labels because we don't put any pseudos that are live over calls in
1266 registers in that case. */
1268 if (flag_caller_saves && best_reg < 0)
1270 /* Did not find a register. If it would be profitable to
1271 allocate a call-clobbered register and save and restore it
1272 around calls, do that. Don't do this if it crosses any calls
1273 that might throw. */
1274 if (! accept_call_clobbered
1275 && allocno[num].calls_crossed != 0
1276 && allocno[num].throwing_calls_crossed == 0
1277 && CALLER_SAVE_PROFITABLE (allocno[num].n_refs,
1278 allocno[num].calls_crossed))
1280 HARD_REG_SET new_losers;
1282 CLEAR_HARD_REG_SET (new_losers);
1284 COPY_HARD_REG_SET (new_losers, losers);
1286 IOR_HARD_REG_SET(new_losers, losing_caller_save_reg_set);
1287 find_reg (num, new_losers, alt_regs_p, 1, retrying);
1288 if (reg_renumber[allocno[num].reg] >= 0)
1290 caller_save_needed = 1;
1296 /* If we haven't succeeded yet,
1297 see if some hard reg that conflicts with us
1298 was utilized poorly by local-alloc.
1299 If so, kick out the regs that were put there by local-alloc
1300 so we can use it instead. */
1301 if (best_reg < 0 && !retrying
1302 /* Let's not bother with multi-reg allocnos. */
1303 && allocno[num].size == 1
1304 && REG_BASIC_BLOCK (allocno[num].reg) == REG_BLOCK_GLOBAL)
1306 /* Count from the end, to find the least-used ones first. */
1307 for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1309 #ifdef REG_ALLOC_ORDER
1310 int regno = reg_alloc_order[i];
1315 if (local_reg_n_refs[regno] != 0
1316 /* Don't use a reg no good for this pseudo. */
1317 && ! TEST_HARD_REG_BIT (used2, regno)
1318 && HARD_REGNO_MODE_OK (regno, mode)
1319 /* The code below assumes that we need only a single
1320 register, but the check of allocno[num].size above
1321 was not enough. Sometimes we need more than one
1322 register for a single-word value. */
1323 && hard_regno_nregs[regno][mode] == 1
1324 && (allocno[num].calls_crossed == 0
1325 || accept_call_clobbered
1326 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode))
1327 #ifdef CANNOT_CHANGE_MODE_CLASS
1328 && ! invalid_mode_change_p (regno, REGNO_REG_CLASS (regno),
1332 && (!allocno[num].no_stack_reg
1333 || regno < FIRST_STACK_REG || regno > LAST_STACK_REG)
1337 /* We explicitly evaluate the divide results into temporary
1338 variables so as to avoid excess precision problems that occur
1339 on an i386-unknown-sysv4.2 (unixware) host. */
1341 double tmp1 = ((double) local_reg_freq[regno] * local_reg_n_refs[regno]
1342 / local_reg_live_length[regno]);
1343 double tmp2 = ((double) allocno[num].freq * allocno[num].n_refs
1344 / allocno[num].live_length);
1348 /* Hard reg REGNO was used less in total by local regs
1349 than it would be used by this one allocno! */
1353 fprintf (dump_file, "Regno %d better for global %d, ",
1354 regno, allocno[num].reg);
1355 fprintf (dump_file, "fr:%d, ll:%d, nr:%d ",
1356 allocno[num].freq, allocno[num].live_length,
1357 allocno[num].n_refs);
1358 fprintf (dump_file, "(was: fr:%d, ll:%d, nr:%d)\n",
1359 local_reg_freq[regno],
1360 local_reg_live_length[regno],
1361 local_reg_n_refs[regno]);
1364 for (k = 0; k < max_regno; k++)
1365 if (reg_renumber[k] >= 0)
1367 int r = reg_renumber[k];
1369 = end_hard_regno (PSEUDO_REGNO_MODE (k), r);
1371 if (regno >= r && regno < endregno)
1375 "Local Reg %d now on stack\n", k);
1376 reg_renumber[k] = -1;
1387 /* Did we find a register? */
1392 HARD_REG_SET this_reg;
1394 /* Yes. Record it as the hard register of this pseudo-reg. */
1395 reg_renumber[allocno[num].reg] = best_reg;
1397 /* Make a set of the hard regs being allocated. */
1398 CLEAR_HARD_REG_SET (this_reg);
1399 lim = end_hard_regno (mode, best_reg);
1400 for (j = best_reg; j < lim; j++)
1402 SET_HARD_REG_BIT (this_reg, j);
1403 SET_HARD_REG_BIT (regs_used_so_far, j);
1404 /* This is no longer a reg used just by local regs. */
1405 local_reg_n_refs[j] = 0;
1406 local_reg_freq[j] = 0;
1408 /* For each other pseudo-reg conflicting with this one,
1409 mark it as conflicting with the hard regs this one occupies. */
1411 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + lim * allocno_row_words, j,
1413 IOR_HARD_REG_SET (allocno[j].hard_reg_conflicts, this_reg);
1418 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1419 Perhaps it had previously seemed not worth a hard reg,
1420 or perhaps its old hard reg has been commandeered for reloads.
1421 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1422 they do not appear to be allocated.
1423 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1426 retry_global_alloc (int regno, HARD_REG_SET forbidden_regs)
1428 int alloc_no = reg_allocno[regno];
1431 /* If we have more than one register class,
1432 first try allocating in the class that is cheapest
1433 for this pseudo-reg. If that fails, try any reg. */
1434 if (N_REG_CLASSES > 1)
1435 find_reg (alloc_no, forbidden_regs, 0, 0, 1);
1436 if (reg_renumber[regno] < 0
1437 && reg_alternate_class (regno) != NO_REGS)
1438 find_reg (alloc_no, forbidden_regs, 1, 0, 1);
1440 /* If we found a register, modify the RTL for the register to
1441 show the hard register, and mark that register live. */
1442 if (reg_renumber[regno] >= 0)
1444 SET_REGNO (regno_reg_rtx[regno], reg_renumber[regno]);
1445 mark_home_live (regno);
1450 /* Record a conflict between register REGNO
1451 and everything currently live.
1452 REGNO must not be a pseudo reg that was allocated
1453 by local_alloc; such numbers must be translated through
1454 reg_renumber before calling here. */
1457 record_one_conflict (int regno)
1461 if (regno < FIRST_PSEUDO_REGISTER)
1462 /* When a hard register becomes live,
1463 record conflicts with live pseudo regs. */
1464 EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live, j,
1466 SET_HARD_REG_BIT (allocno[j].hard_reg_conflicts, regno);
1469 /* When a pseudo-register becomes live,
1470 record conflicts first with hard regs,
1471 then with other pseudo regs. */
1473 int ialloc = reg_allocno[regno];
1474 int ialloc_prod = ialloc * allocno_row_words;
1476 IOR_HARD_REG_SET (allocno[ialloc].hard_reg_conflicts, hard_regs_live);
1477 for (j = allocno_row_words - 1; j >= 0; j--)
1478 conflicts[ialloc_prod + j] |= allocnos_live[j];
1482 /* Record all allocnos currently live as conflicting
1483 with all hard regs currently live.
1485 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1486 are currently live. Their bits are also flagged in allocnos_live. */
1489 record_conflicts (int *allocno_vec, int len)
1492 IOR_HARD_REG_SET (allocno[allocno_vec[len]].hard_reg_conflicts,
1496 /* If CONFLICTP (i, j) is true, make sure CONFLICTP (j, i) is also true. */
1498 mirror_conflicts (void)
1501 int rw = allocno_row_words;
1502 int rwb = rw * INT_BITS;
1503 INT_TYPE *p = conflicts;
1504 INT_TYPE *q0 = conflicts, *q1, *q2;
1505 unsigned INT_TYPE mask;
1507 for (i = max_allocno - 1, mask = 1; i >= 0; i--, mask <<= 1)
1514 for (j = allocno_row_words - 1, q1 = q0; j >= 0; j--, q1 += rwb)
1516 unsigned INT_TYPE word;
1518 for (word = (unsigned INT_TYPE) *p++, q2 = q1; word;
1519 word >>= 1, q2 += rw)
1528 /* Handle the case where REG is set by the insn being scanned,
1529 during the forward scan to accumulate conflicts.
1530 Store a 1 in regs_live or allocnos_live for this register, record how many
1531 consecutive hardware registers it actually needs,
1532 and record a conflict with all other registers already live.
1534 Note that even if REG does not remain alive after this insn,
1535 we must mark it here as live, to ensure a conflict between
1536 REG and any other regs set in this insn that really do live.
1537 This is because those other regs could be considered after this.
1539 REG might actually be something other than a register;
1540 if so, we do nothing.
1542 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1543 a REG_INC note was found for it). */
1546 mark_reg_store (rtx reg, rtx setter, void *data ATTRIBUTE_UNUSED)
1550 if (GET_CODE (reg) == SUBREG)
1551 reg = SUBREG_REG (reg);
1556 VEC_safe_push (rtx, heap, regs_set, reg);
1558 if (setter && GET_CODE (setter) != CLOBBER)
1559 set_preference (reg, SET_SRC (setter));
1561 regno = REGNO (reg);
1563 /* Either this is one of the max_allocno pseudo regs not allocated,
1564 or it is or has a hardware reg. First handle the pseudo-regs. */
1565 if (regno >= FIRST_PSEUDO_REGISTER)
1567 if (reg_allocno[regno] >= 0)
1569 SET_ALLOCNO_LIVE (reg_allocno[regno]);
1570 record_one_conflict (regno);
1574 if (reg_renumber[regno] >= 0)
1575 regno = reg_renumber[regno];
1577 /* Handle hardware regs (and pseudos allocated to hard regs). */
1578 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1580 int last = end_hard_regno (GET_MODE (reg), regno);
1581 while (regno < last)
1583 record_one_conflict (regno);
1584 SET_HARD_REG_BIT (hard_regs_live, regno);
1590 /* Like mark_reg_store except notice just CLOBBERs; ignore SETs. */
1593 mark_reg_clobber (rtx reg, rtx setter, void *data)
1595 if (GET_CODE (setter) == CLOBBER)
1596 mark_reg_store (reg, setter, data);
1599 /* Record that REG has conflicts with all the regs currently live.
1600 Do not mark REG itself as live. */
1603 mark_reg_conflicts (rtx reg)
1607 if (GET_CODE (reg) == SUBREG)
1608 reg = SUBREG_REG (reg);
1613 regno = REGNO (reg);
1615 /* Either this is one of the max_allocno pseudo regs not allocated,
1616 or it is or has a hardware reg. First handle the pseudo-regs. */
1617 if (regno >= FIRST_PSEUDO_REGISTER)
1619 if (reg_allocno[regno] >= 0)
1620 record_one_conflict (regno);
1623 if (reg_renumber[regno] >= 0)
1624 regno = reg_renumber[regno];
1626 /* Handle hardware regs (and pseudos allocated to hard regs). */
1627 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1629 int last = end_hard_regno (GET_MODE (reg), regno);
1630 while (regno < last)
1632 record_one_conflict (regno);
1638 /* Mark REG as being dead (following the insn being scanned now).
1639 Store a 0 in regs_live or allocnos_live for this register. */
1642 mark_reg_death (rtx reg)
1644 int regno = REGNO (reg);
1646 /* Either this is one of the max_allocno pseudo regs not allocated,
1647 or it is a hardware reg. First handle the pseudo-regs. */
1648 if (regno >= FIRST_PSEUDO_REGISTER)
1650 if (reg_allocno[regno] >= 0)
1651 CLEAR_ALLOCNO_LIVE (reg_allocno[regno]);
1654 /* For pseudo reg, see if it has been assigned a hardware reg. */
1655 if (reg_renumber[regno] >= 0)
1656 regno = reg_renumber[regno];
1658 /* Handle hardware regs (and pseudos allocated to hard regs). */
1659 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1660 /* Pseudo regs already assigned hardware regs are treated
1661 almost the same as explicit hardware regs. */
1662 remove_from_hard_reg_set (&hard_regs_live, GET_MODE (reg), regno);
1665 /* Try to set a preference for an allocno to a hard register.
1666 We are passed DEST and SRC which are the operands of a SET. It is known
1667 that SRC is a register. If SRC or the first operand of SRC is a register,
1668 try to set a preference. If one of the two is a hard register and the other
1669 is a pseudo-register, mark the preference.
1671 Note that we are not as aggressive as local-alloc in trying to tie a
1672 pseudo-register to a hard register. */
1675 set_preference (rtx dest, rtx src)
1677 unsigned int src_regno, dest_regno, end_regno;
1678 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1679 to compensate for subregs in SRC or DEST. */
1684 if (GET_RTX_FORMAT (GET_CODE (src))[0] == 'e')
1685 src = XEXP (src, 0), copy = 0;
1687 /* Get the reg number for both SRC and DEST.
1688 If neither is a reg, give up. */
1691 src_regno = REGNO (src);
1692 else if (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src)))
1694 src_regno = REGNO (SUBREG_REG (src));
1696 if (REGNO (SUBREG_REG (src)) < FIRST_PSEUDO_REGISTER)
1697 offset += subreg_regno_offset (REGNO (SUBREG_REG (src)),
1698 GET_MODE (SUBREG_REG (src)),
1702 offset += (SUBREG_BYTE (src)
1703 / REGMODE_NATURAL_SIZE (GET_MODE (src)));
1709 dest_regno = REGNO (dest);
1710 else if (GET_CODE (dest) == SUBREG && REG_P (SUBREG_REG (dest)))
1712 dest_regno = REGNO (SUBREG_REG (dest));
1714 if (REGNO (SUBREG_REG (dest)) < FIRST_PSEUDO_REGISTER)
1715 offset -= subreg_regno_offset (REGNO (SUBREG_REG (dest)),
1716 GET_MODE (SUBREG_REG (dest)),
1720 offset -= (SUBREG_BYTE (dest)
1721 / REGMODE_NATURAL_SIZE (GET_MODE (dest)));
1726 /* Convert either or both to hard reg numbers. */
1728 if (reg_renumber[src_regno] >= 0)
1729 src_regno = reg_renumber[src_regno];
1731 if (reg_renumber[dest_regno] >= 0)
1732 dest_regno = reg_renumber[dest_regno];
1734 /* Now if one is a hard reg and the other is a global pseudo
1735 then give the other a preference. */
1737 if (dest_regno < FIRST_PSEUDO_REGISTER && src_regno >= FIRST_PSEUDO_REGISTER
1738 && reg_allocno[src_regno] >= 0)
1740 dest_regno -= offset;
1741 if (dest_regno < FIRST_PSEUDO_REGISTER)
1744 SET_REGBIT (hard_reg_copy_preferences,
1745 reg_allocno[src_regno], dest_regno);
1747 SET_REGBIT (hard_reg_preferences,
1748 reg_allocno[src_regno], dest_regno);
1749 end_regno = end_hard_regno (GET_MODE (dest), dest_regno);
1750 for (i = dest_regno; i < end_regno; i++)
1751 SET_REGBIT (hard_reg_full_preferences, reg_allocno[src_regno], i);
1755 if (src_regno < FIRST_PSEUDO_REGISTER && dest_regno >= FIRST_PSEUDO_REGISTER
1756 && reg_allocno[dest_regno] >= 0)
1758 src_regno += offset;
1759 if (src_regno < FIRST_PSEUDO_REGISTER)
1762 SET_REGBIT (hard_reg_copy_preferences,
1763 reg_allocno[dest_regno], src_regno);
1765 SET_REGBIT (hard_reg_preferences,
1766 reg_allocno[dest_regno], src_regno);
1767 end_regno = end_hard_regno (GET_MODE (src), src_regno);
1768 for (i = src_regno; i < end_regno; i++)
1769 SET_REGBIT (hard_reg_full_preferences, reg_allocno[dest_regno], i);
1774 /* Indicate that hard register number FROM was eliminated and replaced with
1775 an offset from hard register number TO. The status of hard registers live
1776 at the start of a basic block is updated by replacing a use of FROM with
1780 mark_elimination (int from, int to)
1786 regset r = DF_RA_LIVE_IN (bb);
1787 if (REGNO_REG_SET_P (r, from))
1789 CLEAR_REGNO_REG_SET (r, from);
1790 SET_REGNO_REG_SET (r, to);
1795 /* Used for communication between the following functions. Holds the
1796 current life information. */
1797 static regset live_relevant_regs;
1799 /* Record in live_relevant_regs and REGS_SET that register REG became live.
1800 This is called via note_stores. */
1802 reg_becomes_live (rtx reg, rtx setter ATTRIBUTE_UNUSED, void *regs_set)
1806 if (GET_CODE (reg) == SUBREG)
1807 reg = SUBREG_REG (reg);
1812 regno = REGNO (reg);
1813 if (regno < FIRST_PSEUDO_REGISTER)
1815 int nregs = hard_regno_nregs[regno][GET_MODE (reg)];
1818 if (GET_CODE (setter) == CLOBBER)
1819 CLEAR_REGNO_REG_SET (live_relevant_regs, regno);
1821 SET_REGNO_REG_SET (live_relevant_regs, regno);
1823 if (!fixed_regs[regno])
1824 SET_REGNO_REG_SET ((regset) regs_set, regno);
1828 else if (reg_renumber[regno] >= 0)
1830 if (GET_CODE (setter) == CLOBBER)
1831 CLEAR_REGNO_REG_SET (live_relevant_regs, regno);
1833 SET_REGNO_REG_SET (live_relevant_regs, regno);
1834 SET_REGNO_REG_SET ((regset) regs_set, regno);
1838 /* Record in live_relevant_regs that register REGNO died. */
1840 reg_dies (int regno, enum machine_mode mode, struct insn_chain *chain)
1842 if (regno < FIRST_PSEUDO_REGISTER)
1844 int nregs = hard_regno_nregs[regno][mode];
1847 CLEAR_REGNO_REG_SET (live_relevant_regs, regno);
1848 if (! fixed_regs[regno])
1849 SET_REGNO_REG_SET (&chain->dead_or_set, regno);
1855 CLEAR_REGNO_REG_SET (live_relevant_regs, regno);
1856 if (reg_renumber[regno] >= 0)
1857 SET_REGNO_REG_SET (&chain->dead_or_set, regno);
1861 /* Walk the insns of the current function and build reload_insn_chain,
1862 and record register life information. */
1864 build_insn_chain (rtx first)
1866 struct insn_chain **p = &reload_insn_chain;
1867 struct insn_chain *prev = 0;
1868 basic_block b = ENTRY_BLOCK_PTR->next_bb;
1870 live_relevant_regs = ALLOC_REG_SET (®_obstack);
1872 for (; first; first = NEXT_INSN (first))
1874 struct insn_chain *c;
1876 if (first == BB_HEAD (b))
1881 CLEAR_REG_SET (live_relevant_regs);
1883 EXECUTE_IF_SET_IN_BITMAP (df_get_live_top (b), 0, i, bi)
1885 if (i < FIRST_PSEUDO_REGISTER
1886 ? ! TEST_HARD_REG_BIT (eliminable_regset, i)
1887 : reg_renumber[i] >= 0)
1888 SET_REGNO_REG_SET (live_relevant_regs, i);
1892 if (!NOTE_P (first) && !BARRIER_P (first))
1894 c = new_insn_chain ();
1900 c->block = b->index;
1906 /* Mark the death of everything that dies in this instruction. */
1908 for (link = REG_NOTES (first); link; link = XEXP (link, 1))
1909 if (REG_NOTE_KIND (link) == REG_DEAD
1910 && REG_P (XEXP (link, 0)))
1911 reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)),
1914 COPY_REG_SET (&c->live_throughout, live_relevant_regs);
1916 /* Mark everything born in this instruction as live. */
1918 note_stores (PATTERN (first), reg_becomes_live,
1922 COPY_REG_SET (&c->live_throughout, live_relevant_regs);
1928 /* Mark anything that is set in this insn and then unused as dying. */
1930 for (link = REG_NOTES (first); link; link = XEXP (link, 1))
1931 if (REG_NOTE_KIND (link) == REG_UNUSED
1932 && REG_P (XEXP (link, 0)))
1933 reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)),
1938 if (first == BB_END (b))
1941 /* Stop after we pass the end of the last basic block. Verify that
1942 no real insns are after the end of the last basic block.
1944 We may want to reorganize the loop somewhat since this test should
1945 always be the right exit test. Allow an ADDR_VEC or ADDR_DIF_VEC if
1946 the previous real insn is a JUMP_INSN. */
1947 if (b == EXIT_BLOCK_PTR)
1949 #ifdef ENABLE_CHECKING
1950 for (first = NEXT_INSN (first); first; first = NEXT_INSN (first))
1951 gcc_assert (!INSN_P (first)
1952 || GET_CODE (PATTERN (first)) == USE
1953 || ((GET_CODE (PATTERN (first)) == ADDR_VEC
1954 || GET_CODE (PATTERN (first)) == ADDR_DIFF_VEC)
1955 && prev_real_insn (first) != 0
1956 && JUMP_P (prev_real_insn (first))));
1961 FREE_REG_SET (live_relevant_regs);
1965 /* Print debugging trace information if -dg switch is given,
1966 showing the information on which the allocation decisions are based. */
1969 dump_conflicts (FILE *file)
1972 int has_preferences;
1975 for (i = 0; i < max_allocno; i++)
1977 if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
1981 fprintf (file, ";; %d regs to allocate:", nregs);
1982 for (i = 0; i < max_allocno; i++)
1985 if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
1987 fprintf (file, " %d", allocno[allocno_order[i]].reg);
1988 for (j = 0; j < max_regno; j++)
1989 if (reg_allocno[j] == allocno_order[i]
1990 && j != allocno[allocno_order[i]].reg)
1991 fprintf (file, "+%d", j);
1992 if (allocno[allocno_order[i]].size != 1)
1993 fprintf (file, " (%d)", allocno[allocno_order[i]].size);
1995 fprintf (file, "\n");
1997 for (i = 0; i < max_allocno; i++)
2000 fprintf (file, ";; %d conflicts:", allocno[i].reg);
2001 for (j = 0; j < max_allocno; j++)
2002 if (CONFLICTP (j, i))
2003 fprintf (file, " %d", allocno[j].reg);
2004 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
2005 if (TEST_HARD_REG_BIT (allocno[i].hard_reg_conflicts, j))
2006 fprintf (file, " %d", j);
2007 fprintf (file, "\n");
2009 has_preferences = 0;
2010 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
2011 if (TEST_HARD_REG_BIT (allocno[i].hard_reg_preferences, j))
2012 has_preferences = 1;
2014 if (! has_preferences)
2016 fprintf (file, ";; %d preferences:", allocno[i].reg);
2017 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
2018 if (TEST_HARD_REG_BIT (allocno[i].hard_reg_preferences, j))
2019 fprintf (file, " %d", j);
2020 fprintf (file, "\n");
2022 fprintf (file, "\n");
2026 dump_global_regs (FILE *file)
2030 fprintf (file, ";; Register dispositions:\n");
2031 for (i = FIRST_PSEUDO_REGISTER, j = 0; i < max_regno; i++)
2032 if (reg_renumber[i] >= 0)
2034 fprintf (file, "%d in %d ", i, reg_renumber[i]);
2036 fprintf (file, "\n");
2039 fprintf (file, "\n\n;; Hard regs used: ");
2040 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2041 if (df_regs_ever_live_p (i))
2042 fprintf (file, " %d", i);
2043 fprintf (file, "\n\n");
2046 /* Run old register allocator. Return TRUE if we must exit
2047 rest_of_compilation upon return. */
2049 rest_of_handle_global_alloc (void)
2053 /* If optimizing, allocate remaining pseudo-regs. Do the reload
2054 pass fixing up any insns that are invalid. */
2055 if (optimize && dbg_cnt (global_alloc_at_func))
2056 failure = global_alloc ();
2059 compute_regsets (&eliminable_regset, &no_global_alloc_regs);
2060 build_insn_chain (get_insns ());
2061 df_set_flags (DF_NO_INSN_RESCAN);
2062 failure = reload (get_insns (), 0);
2065 if (dump_enabled_p (pass_global_alloc.static_pass_number))
2067 timevar_push (TV_DUMP);
2068 dump_global_regs (dump_file);
2069 timevar_pop (TV_DUMP);
2072 /* FIXME: This appears on the surface to be wrong thing to be doing.
2073 So much of the compiler is designed to check reload_completed to
2074 see if it is running after reload that seems doomed to failure.
2075 We should be returning a value that says that we have found
2076 errors so that nothing but the cleanup passes are run
2078 gcc_assert (reload_completed || failure);
2079 reload_completed = !failure;
2081 /* The world has changed so much that at this point we might as well
2082 just rescan everything. Not that df_rescan_all_insns is not
2083 going to help here because it does not touch the artificial uses
2087 df_live_add_problem ();
2088 df_scan_alloc (NULL);
2094 regstat_free_n_sets_and_refs ();
2099 struct tree_opt_pass pass_global_alloc =
2103 rest_of_handle_global_alloc, /* execute */
2106 0, /* static_pass_number */
2107 TV_GLOBAL_ALLOC, /* tv_id */
2108 0, /* properties_required */
2109 0, /* properties_provided */
2110 0, /* properties_destroyed */
2111 0, /* todo_flags_start */
2113 TODO_ggc_collect, /* todo_flags_finish */