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 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
25 #include "coretypes.h"
29 #include "hard-reg-set.h"
33 #include "basic-block.h"
36 #include "insn-config.h"
41 /* This pass of the compiler performs global register allocation.
42 It assigns hard register numbers to all the pseudo registers
43 that were not handled in local_alloc. Assignments are recorded
44 in the vector reg_renumber, not by changing the rtl code.
45 (Such changes are made by final). The entry point is
46 the function global_alloc.
48 After allocation is complete, the reload pass is run as a subroutine
49 of this pass, so that when a pseudo reg loses its hard reg due to
50 spilling it is possible to make a second attempt to find a hard
51 reg for it. The reload pass is independent in other respects
52 and it is run even when stupid register allocation is in use.
54 1. Assign allocation-numbers (allocnos) to the pseudo-registers
55 still needing allocations and to the pseudo-registers currently
56 allocated by local-alloc which may be spilled by reload.
57 Set up tables reg_allocno and allocno_reg to map
58 reg numbers to allocnos and vice versa.
59 max_allocno gets the number of allocnos in use.
61 2. Allocate a max_allocno by max_allocno conflict bit matrix and clear it.
62 Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix
63 for conflicts between allocnos and explicit hard register use
64 (which includes use of pseudo-registers allocated by local_alloc).
66 3. For each basic block
67 walk forward through the block, recording which
68 pseudo-registers and which hardware registers are live.
69 Build the conflict matrix between the pseudo-registers
70 and another of pseudo-registers versus hardware registers.
71 Also record the preferred hardware registers
72 for each pseudo-register.
74 4. Sort a table of the allocnos into order of
75 desirability of the variables.
77 5. Allocate the variables in that order; each if possible into
78 a preferred register, else into another register. */
80 /* Number of pseudo-registers which are candidates for allocation. */
82 static int max_allocno;
84 /* Indexed by (pseudo) reg number, gives the allocno, or -1
85 for pseudo registers which are not to be allocated. */
87 static int *reg_allocno;
92 /* Gives the number of consecutive hard registers needed by that
96 /* Number of calls crossed by each allocno. */
99 /* Number of refs to each allocno. */
102 /* Frequency of uses of each allocno. */
105 /* Guess at live length of each allocno.
106 This is actually the max of the live lengths of the regs. */
109 /* Set of hard regs conflicting with allocno N. */
111 HARD_REG_SET hard_reg_conflicts;
113 /* Set of hard regs preferred by allocno N.
114 This is used to make allocnos go into regs that are copied to or from them,
115 when possible, to reduce register shuffling. */
117 HARD_REG_SET hard_reg_preferences;
119 /* Similar, but just counts register preferences made in simple copy
120 operations, rather than arithmetic. These are given priority because
121 we can always eliminate an insn by using these, but using a register
122 in the above list won't always eliminate an insn. */
124 HARD_REG_SET hard_reg_copy_preferences;
126 /* Similar to hard_reg_preferences, but includes bits for subsequent
127 registers when an allocno is multi-word. The above variable is used for
128 allocation while this is used to build reg_someone_prefers, below. */
130 HARD_REG_SET hard_reg_full_preferences;
132 /* Set of hard registers that some later allocno has a preference for. */
134 HARD_REG_SET regs_someone_prefers;
137 /* Set to true if allocno can't be allocated in the stack register. */
142 static struct allocno *allocno;
144 /* A vector of the integers from 0 to max_allocno-1,
145 sorted in the order of first-to-be-allocated first. */
147 static int *allocno_order;
149 /* Indexed by (pseudo) reg number, gives the number of another
150 lower-numbered pseudo reg which can share a hard reg with this pseudo
151 *even if the two pseudos would otherwise appear to conflict*. */
153 static int *reg_may_share;
155 /* Define the number of bits in each element of `conflicts' and what
156 type that element has. We use the largest integer format on the
159 #define INT_BITS HOST_BITS_PER_WIDE_INT
160 #define INT_TYPE HOST_WIDE_INT
162 /* max_allocno by max_allocno array of bits,
163 recording whether two allocno's conflict (can't go in the same
166 `conflicts' is symmetric after the call to mirror_conflicts. */
168 static INT_TYPE *conflicts;
170 /* Number of ints require to hold max_allocno bits.
171 This is the length of a row in `conflicts'. */
173 static int allocno_row_words;
175 /* Two macros to test or store 1 in an element of `conflicts'. */
177 #define CONFLICTP(I, J) \
178 (conflicts[(I) * allocno_row_words + (unsigned) (J) / INT_BITS] \
179 & ((INT_TYPE) 1 << ((unsigned) (J) % INT_BITS)))
181 /* For any allocno set in ALLOCNO_SET, set ALLOCNO to that allocno,
183 #define EXECUTE_IF_SET_IN_ALLOCNO_SET(ALLOCNO_SET, ALLOCNO, CODE) \
187 INT_TYPE *p_ = (ALLOCNO_SET); \
189 for (i_ = allocno_row_words - 1, allocno_ = 0; i_ >= 0; \
190 i_--, allocno_ += INT_BITS) \
192 unsigned INT_TYPE word_ = (unsigned INT_TYPE) *p_++; \
194 for ((ALLOCNO) = allocno_; word_; word_ >>= 1, (ALLOCNO)++) \
202 /* This doesn't work for non-GNU C due to the way CODE is macro expanded. */
204 /* For any allocno that conflicts with IN_ALLOCNO, set OUT_ALLOCNO to
205 the conflicting allocno, and execute CODE. This macro assumes that
206 mirror_conflicts has been run. */
207 #define EXECUTE_IF_CONFLICT(IN_ALLOCNO, OUT_ALLOCNO, CODE)\
208 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + (IN_ALLOCNO) * allocno_row_words,\
212 /* Set of hard regs currently live (during scan of all insns). */
214 static HARD_REG_SET hard_regs_live;
216 /* Set of registers that global-alloc isn't supposed to use. */
218 static HARD_REG_SET no_global_alloc_regs;
220 /* Set of registers used so far. */
222 static HARD_REG_SET regs_used_so_far;
224 /* Number of refs to each hard reg, as used by local alloc.
225 It is zero for a reg that contains global pseudos or is explicitly used. */
227 static int local_reg_n_refs[FIRST_PSEUDO_REGISTER];
229 /* Frequency of uses of given hard reg. */
230 static int local_reg_freq[FIRST_PSEUDO_REGISTER];
232 /* Guess at live length of each hard reg, as used by local alloc.
233 This is actually the sum of the live lengths of the specific regs. */
235 static int local_reg_live_length[FIRST_PSEUDO_REGISTER];
237 /* Set to 1 a bit in a vector TABLE of HARD_REG_SETs, for vector
238 element I, and hard register number J. */
240 #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (allocno[I].TABLE, J)
242 /* Bit mask for allocnos live at current point in the scan. */
244 static INT_TYPE *allocnos_live;
246 /* Test, set or clear bit number I in allocnos_live,
247 a bit vector indexed by allocno. */
249 #define SET_ALLOCNO_LIVE(I) \
250 (allocnos_live[(unsigned) (I) / INT_BITS] \
251 |= ((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS)))
253 #define CLEAR_ALLOCNO_LIVE(I) \
254 (allocnos_live[(unsigned) (I) / INT_BITS] \
255 &= ~((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS)))
257 /* This is turned off because it doesn't work right for DImode.
258 (And it is only used for DImode, so the other cases are worthless.)
259 The problem is that it isn't true that there is NO possibility of conflict;
260 only that there is no conflict if the two pseudos get the exact same regs.
261 If they were allocated with a partial overlap, there would be a conflict.
262 We can't safely turn off the conflict unless we have another way to
263 prevent the partial overlap.
265 Idea: change hard_reg_conflicts so that instead of recording which
266 hard regs the allocno may not overlap, it records where the allocno
267 may not start. Change both where it is used and where it is updated.
268 Then there is a way to record that (reg:DI 108) may start at 10
269 but not at 9 or 11. There is still the question of how to record
270 this semi-conflict between two pseudos. */
272 /* Reg pairs for which conflict after the current insn
273 is inhibited by a REG_NO_CONFLICT note.
274 If the table gets full, we ignore any other notes--that is conservative. */
275 #define NUM_NO_CONFLICT_PAIRS 4
276 /* Number of pairs in use in this insn. */
277 int n_no_conflict_pairs;
278 static struct { int allocno1, allocno2;}
279 no_conflict_pairs[NUM_NO_CONFLICT_PAIRS];
282 /* Record all regs that are set in any one insn.
283 Communication from mark_reg_{store,clobber} and global_conflicts. */
285 static rtx *regs_set;
286 static int n_regs_set;
288 /* All registers that can be eliminated. */
290 static HARD_REG_SET eliminable_regset;
292 static int allocno_compare (const void *, const void *);
293 static void global_conflicts (void);
294 static void mirror_conflicts (void);
295 static void expand_preferences (void);
296 static void prune_preferences (void);
297 static void find_reg (int, HARD_REG_SET, int, int, int);
298 static void record_one_conflict (int);
299 static void record_conflicts (int *, int);
300 static void mark_reg_store (rtx, rtx, void *);
301 static void mark_reg_clobber (rtx, rtx, void *);
302 static void mark_reg_conflicts (rtx);
303 static void mark_reg_death (rtx);
304 static void mark_reg_live_nc (int, enum machine_mode);
305 static void set_preference (rtx, rtx);
306 static void dump_conflicts (FILE *);
307 static void reg_becomes_live (rtx, rtx, void *);
308 static void reg_dies (int, enum machine_mode, struct insn_chain *);
310 /* Perform allocation of pseudo-registers not allocated by local_alloc.
311 FILE is a file to output debugging information on,
312 or zero if such output is not desired.
314 Return value is nonzero if reload failed
315 and we must not do any more for this function. */
318 global_alloc (FILE *file)
321 #ifdef ELIMINABLE_REGS
322 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
325 = (! flag_omit_frame_pointer
326 || (current_function_calls_alloca && EXIT_IGNORE_STACK)
327 || FRAME_POINTER_REQUIRED);
334 /* A machine may have certain hard registers that
335 are safe to use only within a basic block. */
337 CLEAR_HARD_REG_SET (no_global_alloc_regs);
339 /* Build the regset of all eliminable registers and show we can't use those
340 that we already know won't be eliminated. */
341 #ifdef ELIMINABLE_REGS
342 for (i = 0; i < ARRAY_SIZE (eliminables); i++)
345 = (! CAN_ELIMINATE (eliminables[i].from, eliminables[i].to)
346 || (eliminables[i].to == STACK_POINTER_REGNUM && need_fp));
348 if (!regs_asm_clobbered[eliminables[i].from])
350 SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from);
353 SET_HARD_REG_BIT (no_global_alloc_regs, eliminables[i].from);
355 else if (cannot_elim)
356 error ("%s cannot be used in asm here",
357 reg_names[eliminables[i].from]);
359 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
360 if (!regs_asm_clobbered[HARD_FRAME_POINTER_REGNUM])
362 SET_HARD_REG_BIT (eliminable_regset, HARD_FRAME_POINTER_REGNUM);
364 SET_HARD_REG_BIT (no_global_alloc_regs, HARD_FRAME_POINTER_REGNUM);
367 error ("%s cannot be used in asm here",
368 reg_names[HARD_FRAME_POINTER_REGNUM]);
372 if (!regs_asm_clobbered[FRAME_POINTER_REGNUM])
374 SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM);
376 SET_HARD_REG_BIT (no_global_alloc_regs, FRAME_POINTER_REGNUM);
379 error ("%s cannot be used in asm here", reg_names[FRAME_POINTER_REGNUM]);
382 /* Track which registers have already been used. Start with registers
383 explicitly in the rtl, then registers allocated by local register
386 CLEAR_HARD_REG_SET (regs_used_so_far);
387 #ifdef LEAF_REGISTERS
388 /* If we are doing the leaf function optimization, and this is a leaf
389 function, it means that the registers that take work to save are those
390 that need a register window. So prefer the ones that can be used in
393 const char *cheap_regs;
394 const char *const leaf_regs = LEAF_REGISTERS;
396 if (only_leaf_regs_used () && leaf_function_p ())
397 cheap_regs = leaf_regs;
399 cheap_regs = call_used_regs;
400 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
401 if (regs_ever_live[i] || cheap_regs[i])
402 SET_HARD_REG_BIT (regs_used_so_far, i);
405 /* We consider registers that do not have to be saved over calls as if
406 they were already used since there is no cost in using them. */
407 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
408 if (regs_ever_live[i] || call_used_regs[i])
409 SET_HARD_REG_BIT (regs_used_so_far, i);
412 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
413 if (reg_renumber[i] >= 0)
414 SET_HARD_REG_BIT (regs_used_so_far, reg_renumber[i]);
416 /* Establish mappings from register number to allocation number
417 and vice versa. In the process, count the allocnos. */
419 reg_allocno = xmalloc (max_regno * sizeof (int));
421 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
424 /* Initialize the shared-hard-reg mapping
425 from the list of pairs that may share. */
426 reg_may_share = xcalloc (max_regno, sizeof (int));
427 for (x = regs_may_share; x; x = XEXP (XEXP (x, 1), 1))
429 int r1 = REGNO (XEXP (x, 0));
430 int r2 = REGNO (XEXP (XEXP (x, 1), 0));
432 reg_may_share[r1] = r2;
434 reg_may_share[r2] = r1;
437 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
438 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
439 that we are supposed to refrain from putting in a hard reg.
440 -2 means do make an allocno but don't allocate it. */
441 if (REG_N_REFS (i) != 0 && REG_LIVE_LENGTH (i) != -1
442 /* Don't allocate pseudos that cross calls,
443 if this function receives a nonlocal goto. */
444 && (! current_function_has_nonlocal_label
445 || REG_N_CALLS_CROSSED (i) == 0))
447 if (reg_renumber[i] < 0 && reg_may_share[i] && reg_allocno[reg_may_share[i]] >= 0)
448 reg_allocno[i] = reg_allocno[reg_may_share[i]];
450 reg_allocno[i] = max_allocno++;
451 if (REG_LIVE_LENGTH (i) == 0)
457 allocno = xcalloc (max_allocno, sizeof (struct allocno));
459 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
460 if (reg_allocno[i] >= 0)
462 int num = reg_allocno[i];
463 allocno[num].reg = i;
464 allocno[num].size = PSEUDO_REGNO_SIZE (i);
465 allocno[num].calls_crossed += REG_N_CALLS_CROSSED (i);
466 allocno[num].n_refs += REG_N_REFS (i);
467 allocno[num].freq += REG_FREQ (i);
468 if (allocno[num].live_length < REG_LIVE_LENGTH (i))
469 allocno[num].live_length = REG_LIVE_LENGTH (i);
472 /* Calculate amount of usage of each hard reg by pseudos
473 allocated by local-alloc. This is to see if we want to
475 memset (local_reg_live_length, 0, sizeof local_reg_live_length);
476 memset (local_reg_n_refs, 0, sizeof local_reg_n_refs);
477 memset (local_reg_freq, 0, sizeof local_reg_freq);
478 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
479 if (reg_renumber[i] >= 0)
481 int regno = reg_renumber[i];
482 int endregno = regno + HARD_REGNO_NREGS (regno, PSEUDO_REGNO_MODE (i));
485 for (j = regno; j < endregno; j++)
487 local_reg_n_refs[j] += REG_N_REFS (i);
488 local_reg_freq[j] += REG_FREQ (i);
489 local_reg_live_length[j] += REG_LIVE_LENGTH (i);
493 /* We can't override local-alloc for a reg used not just by local-alloc. */
494 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
495 if (regs_ever_live[i])
496 local_reg_n_refs[i] = 0, local_reg_freq[i] = 0;
498 allocno_row_words = (max_allocno + INT_BITS - 1) / INT_BITS;
500 /* We used to use alloca here, but the size of what it would try to
501 allocate would occasionally cause it to exceed the stack limit and
502 cause unpredictable core dumps. Some examples were > 2Mb in size. */
503 conflicts = xcalloc (max_allocno * allocno_row_words, sizeof (INT_TYPE));
505 allocnos_live = xmalloc (allocno_row_words * sizeof (INT_TYPE));
507 /* If there is work to be done (at least one reg to allocate),
508 perform global conflict analysis and allocate the regs. */
512 /* Scan all the insns and compute the conflicts among allocnos
513 and between allocnos and hard regs. */
519 /* Eliminate conflicts between pseudos and eliminable registers. If
520 the register is not eliminated, the pseudo won't really be able to
521 live in the eliminable register, so the conflict doesn't matter.
522 If we do eliminate the register, the conflict will no longer exist.
523 So in either case, we can ignore the conflict. Likewise for
526 for (i = 0; i < (size_t) max_allocno; i++)
528 AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_conflicts,
530 AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_copy_preferences,
532 AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_preferences,
536 /* Try to expand the preferences by merging them between allocnos. */
538 expand_preferences ();
540 /* Determine the order to allocate the remaining pseudo registers. */
542 allocno_order = xmalloc (max_allocno * sizeof (int));
543 for (i = 0; i < (size_t) max_allocno; i++)
544 allocno_order[i] = i;
546 /* Default the size to 1, since allocno_compare uses it to divide by.
547 Also convert allocno_live_length of zero to -1. A length of zero
548 can occur when all the registers for that allocno have reg_live_length
549 equal to -2. In this case, we want to make an allocno, but not
550 allocate it. So avoid the divide-by-zero and set it to a low
553 for (i = 0; i < (size_t) max_allocno; i++)
555 if (allocno[i].size == 0)
557 if (allocno[i].live_length == 0)
558 allocno[i].live_length = -1;
561 qsort (allocno_order, max_allocno, sizeof (int), allocno_compare);
563 prune_preferences ();
566 dump_conflicts (file);
568 /* Try allocating them, one by one, in that order,
569 except for parameters marked with reg_live_length[regno] == -2. */
571 for (i = 0; i < (size_t) max_allocno; i++)
572 if (reg_renumber[allocno[allocno_order[i]].reg] < 0
573 && REG_LIVE_LENGTH (allocno[allocno_order[i]].reg) >= 0)
575 /* If we have more than one register class,
576 first try allocating in the class that is cheapest
577 for this pseudo-reg. If that fails, try any reg. */
578 if (N_REG_CLASSES > 1)
580 find_reg (allocno_order[i], 0, 0, 0, 0);
581 if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
584 if (reg_alternate_class (allocno[allocno_order[i]].reg) != NO_REGS)
585 find_reg (allocno_order[i], 0, 1, 0, 0);
588 free (allocno_order);
591 /* Do the reloads now while the allocno data still exist, so that we can
592 try to assign new hard regs to any pseudo regs that are spilled. */
594 #if 0 /* We need to eliminate regs even if there is no rtl code,
595 for the sake of debugging information. */
596 if (n_basic_blocks > 0)
599 build_insn_chain (get_insns ());
600 retval = reload (get_insns (), 1);
605 free (reg_may_share);
608 free (allocnos_live);
613 /* Sort predicate for ordering the allocnos.
614 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
617 allocno_compare (const void *v1p, const void *v2p)
619 int v1 = *(const int *)v1p, v2 = *(const int *)v2p;
620 /* Note that the quotient will never be bigger than
621 the value of floor_log2 times the maximum number of
622 times a register can occur in one insn (surely less than 100)
623 weighted by the frequency (maximally REG_FREQ_MAX).
624 Multiplying this by 10000/REG_FREQ_MAX can't overflow. */
626 = (((double) (floor_log2 (allocno[v1].n_refs) * allocno[v1].freq)
627 / allocno[v1].live_length)
628 * (10000 / REG_FREQ_MAX) * allocno[v1].size);
630 = (((double) (floor_log2 (allocno[v2].n_refs) * allocno[v2].freq)
631 / allocno[v2].live_length)
632 * (10000 / REG_FREQ_MAX) * allocno[v2].size);
636 /* If regs are equally good, sort by allocno,
637 so that the results of qsort leave nothing to chance. */
641 /* Scan the rtl code and record all conflicts and register preferences in the
642 conflict matrices and preference tables. */
645 global_conflicts (void)
650 int *block_start_allocnos;
652 /* Make a vector that mark_reg_{store,clobber} will store in. */
653 regs_set = xmalloc (max_parallel * sizeof (rtx) * 2);
655 block_start_allocnos = xmalloc (max_allocno * sizeof (int));
659 memset (allocnos_live, 0, allocno_row_words * sizeof (INT_TYPE));
661 /* Initialize table of registers currently live
662 to the state at the beginning of this basic block.
663 This also marks the conflicts among hard registers
664 and any allocnos that are live.
666 For pseudo-regs, there is only one bit for each one
667 no matter how many hard regs it occupies.
668 This is ok; we know the size from PSEUDO_REGNO_SIZE.
669 For explicit hard regs, we cannot know the size that way
670 since one hard reg can be used with various sizes.
671 Therefore, we must require that all the hard regs
672 implicitly live as part of a multi-word hard reg
673 are explicitly marked in basic_block_live_at_start. */
676 regset old = b->global_live_at_start;
679 REG_SET_TO_HARD_REG_SET (hard_regs_live, old);
680 EXECUTE_IF_SET_IN_REG_SET (old, FIRST_PSEUDO_REGISTER, i,
682 int a = reg_allocno[i];
685 SET_ALLOCNO_LIVE (a);
686 block_start_allocnos[ax++] = a;
688 else if ((a = reg_renumber[i]) >= 0)
690 (a, PSEUDO_REGNO_MODE (i));
693 /* Record that each allocno now live conflicts with each hard reg
696 It is not necessary to mark any conflicts between pseudos as
697 this point, even for pseudos which are live at the start of
700 Given two pseudos X and Y and any point in the CFG P.
702 On any path to point P where X and Y are live one of the
703 following conditions must be true:
705 1. X is live at some instruction on the path that
708 2. Y is live at some instruction on the path that
711 3. Either X or Y is not evaluated on the path to P
712 (ie it is used uninitialized) and thus the
713 conflict can be ignored.
715 In cases #1 and #2 the conflict will be recorded when we
716 scan the instruction that makes either X or Y become live. */
717 record_conflicts (block_start_allocnos, ax);
719 /* Pseudos can't go in stack regs at the start of a basic block that
720 is reached by an abnormal edge. Likewise for call clobbered regs,
721 because because caller-save, fixup_abnormal_edges, and possibly
722 the table driven EH machinery are not quite ready to handle such
723 regs live across such edges. */
727 for (e = b->pred; e ; e = e->pred_next)
728 if (e->flags & EDGE_ABNORMAL)
734 EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live, ax,
736 allocno[ax].no_stack_reg = 1;
738 for (ax = FIRST_STACK_REG; ax <= LAST_STACK_REG; ax++)
739 record_one_conflict (ax);
742 /* No need to record conflicts for call clobbered regs if we have
743 nonlocal labels around, as we don't ever try to allocate such
744 regs in this case. */
745 if (! current_function_has_nonlocal_label)
746 for (ax = 0; ax < FIRST_PSEUDO_REGISTER; ax++)
747 if (call_used_regs [ax])
748 record_one_conflict (ax);
755 /* Scan the code of this basic block, noting which allocnos
756 and hard regs are born or die. When one is born,
757 record a conflict with all others currently live. */
761 RTX_CODE code = GET_CODE (insn);
764 /* Make regs_set an empty set. */
768 if (code == INSN || code == CALL_INSN || code == JUMP_INSN)
773 for (link = REG_NOTES (insn);
774 link && i < NUM_NO_CONFLICT_PAIRS;
775 link = XEXP (link, 1))
776 if (REG_NOTE_KIND (link) == REG_NO_CONFLICT)
778 no_conflict_pairs[i].allocno1
779 = reg_allocno[REGNO (SET_DEST (PATTERN (insn)))];
780 no_conflict_pairs[i].allocno2
781 = reg_allocno[REGNO (XEXP (link, 0))];
786 /* Mark any registers clobbered by INSN as live,
787 so they conflict with the inputs. */
789 note_stores (PATTERN (insn), mark_reg_clobber, NULL);
791 /* Mark any registers dead after INSN as dead now. */
793 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
794 if (REG_NOTE_KIND (link) == REG_DEAD)
795 mark_reg_death (XEXP (link, 0));
797 /* Mark any registers set in INSN as live,
798 and mark them as conflicting with all other live regs.
799 Clobbers are processed again, so they conflict with
800 the registers that are set. */
802 note_stores (PATTERN (insn), mark_reg_store, NULL);
805 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
806 if (REG_NOTE_KIND (link) == REG_INC)
807 mark_reg_store (XEXP (link, 0), NULL_RTX, NULL);
810 /* If INSN has multiple outputs, then any reg that dies here
811 and is used inside of an output
812 must conflict with the other outputs.
814 It is unsafe to use !single_set here since it will ignore an
815 unused output. Just because an output is unused does not mean
816 the compiler can assume the side effect will not occur.
817 Consider if REG appears in the address of an output and we
818 reload the output. If we allocate REG to the same hard
819 register as an unused output we could set the hard register
820 before the output reload insn. */
821 if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn))
822 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
823 if (REG_NOTE_KIND (link) == REG_DEAD)
825 int used_in_output = 0;
827 rtx reg = XEXP (link, 0);
829 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
831 rtx set = XVECEXP (PATTERN (insn), 0, i);
832 if (GET_CODE (set) == SET
833 && GET_CODE (SET_DEST (set)) != REG
834 && !rtx_equal_p (reg, SET_DEST (set))
835 && reg_overlap_mentioned_p (reg, SET_DEST (set)))
839 mark_reg_conflicts (reg);
842 /* Mark any registers set in INSN and then never used. */
844 while (n_regs_set-- > 0)
846 rtx note = find_regno_note (insn, REG_UNUSED,
847 REGNO (regs_set[n_regs_set]));
849 mark_reg_death (XEXP (note, 0));
853 if (insn == BB_END (b))
855 insn = NEXT_INSN (insn);
860 free (block_start_allocnos);
863 /* Expand the preference information by looking for cases where one allocno
864 dies in an insn that sets an allocno. If those two allocnos don't conflict,
865 merge any preferences between those allocnos. */
868 expand_preferences (void)
874 /* We only try to handle the most common cases here. Most of the cases
875 where this wins are reg-reg copies. */
877 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
879 && (set = single_set (insn)) != 0
880 && GET_CODE (SET_DEST (set)) == REG
881 && reg_allocno[REGNO (SET_DEST (set))] >= 0)
882 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
883 if (REG_NOTE_KIND (link) == REG_DEAD
884 && GET_CODE (XEXP (link, 0)) == REG
885 && reg_allocno[REGNO (XEXP (link, 0))] >= 0
886 && ! CONFLICTP (reg_allocno[REGNO (SET_DEST (set))],
887 reg_allocno[REGNO (XEXP (link, 0))]))
889 int a1 = reg_allocno[REGNO (SET_DEST (set))];
890 int a2 = reg_allocno[REGNO (XEXP (link, 0))];
892 if (XEXP (link, 0) == SET_SRC (set))
894 IOR_HARD_REG_SET (allocno[a1].hard_reg_copy_preferences,
895 allocno[a2].hard_reg_copy_preferences);
896 IOR_HARD_REG_SET (allocno[a2].hard_reg_copy_preferences,
897 allocno[a1].hard_reg_copy_preferences);
900 IOR_HARD_REG_SET (allocno[a1].hard_reg_preferences,
901 allocno[a2].hard_reg_preferences);
902 IOR_HARD_REG_SET (allocno[a2].hard_reg_preferences,
903 allocno[a1].hard_reg_preferences);
904 IOR_HARD_REG_SET (allocno[a1].hard_reg_full_preferences,
905 allocno[a2].hard_reg_full_preferences);
906 IOR_HARD_REG_SET (allocno[a2].hard_reg_full_preferences,
907 allocno[a1].hard_reg_full_preferences);
911 /* Prune the preferences for global registers to exclude registers that cannot
914 Compute `regs_someone_prefers', which is a bitmask of the hard registers
915 that are preferred by conflicting registers of lower priority. If possible,
916 we will avoid using these registers. */
919 prune_preferences (void)
923 int *allocno_to_order = xmalloc (max_allocno * sizeof (int));
925 /* Scan least most important to most important.
926 For each allocno, remove from preferences registers that cannot be used,
927 either because of conflicts or register type. Then compute all registers
928 preferred by each lower-priority register that conflicts. */
930 for (i = max_allocno - 1; i >= 0; i--)
934 num = allocno_order[i];
935 allocno_to_order[num] = i;
936 COPY_HARD_REG_SET (temp, allocno[num].hard_reg_conflicts);
938 if (allocno[num].calls_crossed == 0)
939 IOR_HARD_REG_SET (temp, fixed_reg_set);
941 IOR_HARD_REG_SET (temp, call_used_reg_set);
943 IOR_COMPL_HARD_REG_SET
945 reg_class_contents[(int) reg_preferred_class (allocno[num].reg)]);
947 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_preferences, temp);
948 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_copy_preferences, temp);
949 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_full_preferences, temp);
952 for (i = max_allocno - 1; i >= 0; i--)
954 /* Merge in the preferences of lower-priority registers (they have
955 already been pruned). If we also prefer some of those registers,
956 don't exclude them unless we are of a smaller size (in which case
957 we want to give the lower-priority allocno the first chance for
959 HARD_REG_SET temp, temp2;
962 num = allocno_order[i];
964 CLEAR_HARD_REG_SET (temp);
965 CLEAR_HARD_REG_SET (temp2);
967 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + num * allocno_row_words,
970 if (allocno_to_order[allocno2] > i)
972 if (allocno[allocno2].size <= allocno[num].size)
973 IOR_HARD_REG_SET (temp,
974 allocno[allocno2].hard_reg_full_preferences);
976 IOR_HARD_REG_SET (temp2,
977 allocno[allocno2].hard_reg_full_preferences);
981 AND_COMPL_HARD_REG_SET (temp, allocno[num].hard_reg_full_preferences);
982 IOR_HARD_REG_SET (temp, temp2);
983 COPY_HARD_REG_SET (allocno[num].regs_someone_prefers, temp);
985 free (allocno_to_order);
988 /* Assign a hard register to allocno NUM; look for one that is the beginning
989 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
990 The registers marked in PREFREGS are tried first.
992 LOSERS, if nonzero, is a HARD_REG_SET indicating registers that cannot
993 be used for this allocation.
995 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
996 Otherwise ignore that preferred class and use the alternate class.
998 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
999 will have to be saved and restored at calls.
1001 RETRYING is nonzero if this is called from retry_global_alloc.
1003 If we find one, record it in reg_renumber.
1004 If not, do nothing. */
1007 find_reg (int num, HARD_REG_SET losers, int alt_regs_p, int accept_call_clobbered, int retrying)
1009 int i, best_reg, pass;
1010 HARD_REG_SET used, used1, used2;
1012 enum reg_class class = (alt_regs_p
1013 ? reg_alternate_class (allocno[num].reg)
1014 : reg_preferred_class (allocno[num].reg));
1015 enum machine_mode mode = PSEUDO_REGNO_MODE (allocno[num].reg);
1017 if (accept_call_clobbered)
1018 COPY_HARD_REG_SET (used1, call_fixed_reg_set);
1019 else if (allocno[num].calls_crossed == 0)
1020 COPY_HARD_REG_SET (used1, fixed_reg_set);
1022 COPY_HARD_REG_SET (used1, call_used_reg_set);
1024 /* Some registers should not be allocated in global-alloc. */
1025 IOR_HARD_REG_SET (used1, no_global_alloc_regs);
1027 IOR_HARD_REG_SET (used1, losers);
1029 IOR_COMPL_HARD_REG_SET (used1, reg_class_contents[(int) class]);
1030 COPY_HARD_REG_SET (used2, used1);
1032 IOR_HARD_REG_SET (used1, allocno[num].hard_reg_conflicts);
1034 #ifdef CANNOT_CHANGE_MODE_CLASS
1035 cannot_change_mode_set_regs (&used1, mode, allocno[num].reg);
1038 /* Try each hard reg to see if it fits. Do this in two passes.
1039 In the first pass, skip registers that are preferred by some other pseudo
1040 to give it a better chance of getting one of those registers. Only if
1041 we can't get a register when excluding those do we take one of them.
1042 However, we never allocate a register for the first time in pass 0. */
1044 COPY_HARD_REG_SET (used, used1);
1045 IOR_COMPL_HARD_REG_SET (used, regs_used_so_far);
1046 IOR_HARD_REG_SET (used, allocno[num].regs_someone_prefers);
1049 for (i = FIRST_PSEUDO_REGISTER, pass = 0;
1050 pass <= 1 && i >= FIRST_PSEUDO_REGISTER;
1054 COPY_HARD_REG_SET (used, used1);
1055 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1057 #ifdef REG_ALLOC_ORDER
1058 int regno = reg_alloc_order[i];
1062 if (! TEST_HARD_REG_BIT (used, regno)
1063 && HARD_REGNO_MODE_OK (regno, mode)
1064 && (allocno[num].calls_crossed == 0
1065 || accept_call_clobbered
1066 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
1069 int lim = regno + HARD_REGNO_NREGS (regno, mode);
1072 && ! TEST_HARD_REG_BIT (used, j));
1079 #ifndef REG_ALLOC_ORDER
1080 i = j; /* Skip starting points we know will lose */
1086 /* See if there is a preferred register with the same class as the register
1087 we allocated above. Making this restriction prevents register
1088 preferencing from creating worse register allocation.
1090 Remove from the preferred registers and conflicting registers. Note that
1091 additional conflicts may have been added after `prune_preferences' was
1094 First do this for those register with copy preferences, then all
1095 preferred registers. */
1097 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_copy_preferences, used);
1098 GO_IF_HARD_REG_SUBSET (allocno[num].hard_reg_copy_preferences,
1099 reg_class_contents[(int) NO_REGS], no_copy_prefs);
1103 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1104 if (TEST_HARD_REG_BIT (allocno[num].hard_reg_copy_preferences, i)
1105 && HARD_REGNO_MODE_OK (i, mode)
1106 && (allocno[num].calls_crossed == 0
1107 || accept_call_clobbered
1108 || ! HARD_REGNO_CALL_PART_CLOBBERED (i, mode))
1109 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1110 || reg_class_subset_p (REGNO_REG_CLASS (i),
1111 REGNO_REG_CLASS (best_reg))
1112 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1113 REGNO_REG_CLASS (i))))
1116 int lim = i + HARD_REGNO_NREGS (i, mode);
1119 && ! TEST_HARD_REG_BIT (used, j)
1120 && (REGNO_REG_CLASS (j)
1121 == REGNO_REG_CLASS (best_reg + (j - i))
1122 || reg_class_subset_p (REGNO_REG_CLASS (j),
1123 REGNO_REG_CLASS (best_reg + (j - i)))
1124 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1125 REGNO_REG_CLASS (j))));
1136 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_preferences, used);
1137 GO_IF_HARD_REG_SUBSET (allocno[num].hard_reg_preferences,
1138 reg_class_contents[(int) NO_REGS], no_prefs);
1142 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1143 if (TEST_HARD_REG_BIT (allocno[num].hard_reg_preferences, i)
1144 && HARD_REGNO_MODE_OK (i, mode)
1145 && (allocno[num].calls_crossed == 0
1146 || accept_call_clobbered
1147 || ! HARD_REGNO_CALL_PART_CLOBBERED (i, mode))
1148 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1149 || reg_class_subset_p (REGNO_REG_CLASS (i),
1150 REGNO_REG_CLASS (best_reg))
1151 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1152 REGNO_REG_CLASS (i))))
1155 int lim = i + HARD_REGNO_NREGS (i, mode);
1158 && ! TEST_HARD_REG_BIT (used, j)
1159 && (REGNO_REG_CLASS (j)
1160 == REGNO_REG_CLASS (best_reg + (j - i))
1161 || reg_class_subset_p (REGNO_REG_CLASS (j),
1162 REGNO_REG_CLASS (best_reg + (j - i)))
1163 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1164 REGNO_REG_CLASS (j))));
1175 /* If we haven't succeeded yet, try with caller-saves.
1176 We need not check to see if the current function has nonlocal
1177 labels because we don't put any pseudos that are live over calls in
1178 registers in that case. */
1180 if (flag_caller_saves && best_reg < 0)
1182 /* Did not find a register. If it would be profitable to
1183 allocate a call-clobbered register and save and restore it
1184 around calls, do that. */
1185 if (! accept_call_clobbered
1186 && allocno[num].calls_crossed != 0
1187 && CALLER_SAVE_PROFITABLE (allocno[num].n_refs,
1188 allocno[num].calls_crossed))
1190 HARD_REG_SET new_losers;
1192 CLEAR_HARD_REG_SET (new_losers);
1194 COPY_HARD_REG_SET (new_losers, losers);
1196 IOR_HARD_REG_SET(new_losers, losing_caller_save_reg_set);
1197 find_reg (num, new_losers, alt_regs_p, 1, retrying);
1198 if (reg_renumber[allocno[num].reg] >= 0)
1200 caller_save_needed = 1;
1206 /* If we haven't succeeded yet,
1207 see if some hard reg that conflicts with us
1208 was utilized poorly by local-alloc.
1209 If so, kick out the regs that were put there by local-alloc
1210 so we can use it instead. */
1211 if (best_reg < 0 && !retrying
1212 /* Let's not bother with multi-reg allocnos. */
1213 && allocno[num].size == 1)
1215 /* Count from the end, to find the least-used ones first. */
1216 for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1218 #ifdef REG_ALLOC_ORDER
1219 int regno = reg_alloc_order[i];
1224 if (local_reg_n_refs[regno] != 0
1225 /* Don't use a reg no good for this pseudo. */
1226 && ! TEST_HARD_REG_BIT (used2, regno)
1227 && HARD_REGNO_MODE_OK (regno, mode)
1228 /* The code below assumes that we need only a single
1229 register, but the check of allocno[num].size above
1230 was not enough. Sometimes we need more than one
1231 register for a single-word value. */
1232 && HARD_REGNO_NREGS (regno, mode) == 1
1233 && (allocno[num].calls_crossed == 0
1234 || accept_call_clobbered
1235 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode))
1236 #ifdef CANNOT_CHANGE_MODE_CLASS
1237 && ! invalid_mode_change_p (regno, REGNO_REG_CLASS (regno),
1241 && (!allocno[num].no_stack_reg
1242 || regno < FIRST_STACK_REG || regno > LAST_STACK_REG)
1246 /* We explicitly evaluate the divide results into temporary
1247 variables so as to avoid excess precision problems that occur
1248 on an i386-unknown-sysv4.2 (unixware) host. */
1250 double tmp1 = ((double) local_reg_freq[regno]
1251 / local_reg_live_length[regno]);
1252 double tmp2 = ((double) allocno[num].freq
1253 / allocno[num].live_length);
1257 /* Hard reg REGNO was used less in total by local regs
1258 than it would be used by this one allocno! */
1260 for (k = 0; k < max_regno; k++)
1261 if (reg_renumber[k] >= 0)
1263 int r = reg_renumber[k];
1265 = r + HARD_REGNO_NREGS (r, PSEUDO_REGNO_MODE (k));
1267 if (regno >= r && regno < endregno)
1268 reg_renumber[k] = -1;
1278 /* Did we find a register? */
1283 HARD_REG_SET this_reg;
1285 /* Yes. Record it as the hard register of this pseudo-reg. */
1286 reg_renumber[allocno[num].reg] = best_reg;
1287 /* Also of any pseudo-regs that share with it. */
1288 if (reg_may_share[allocno[num].reg])
1289 for (j = FIRST_PSEUDO_REGISTER; j < max_regno; j++)
1290 if (reg_allocno[j] == num)
1291 reg_renumber[j] = best_reg;
1293 /* Make a set of the hard regs being allocated. */
1294 CLEAR_HARD_REG_SET (this_reg);
1295 lim = best_reg + HARD_REGNO_NREGS (best_reg, mode);
1296 for (j = best_reg; j < lim; j++)
1298 SET_HARD_REG_BIT (this_reg, j);
1299 SET_HARD_REG_BIT (regs_used_so_far, j);
1300 /* This is no longer a reg used just by local regs. */
1301 local_reg_n_refs[j] = 0;
1302 local_reg_freq[j] = 0;
1304 /* For each other pseudo-reg conflicting with this one,
1305 mark it as conflicting with the hard regs this one occupies. */
1307 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + lim * allocno_row_words, j,
1309 IOR_HARD_REG_SET (allocno[j].hard_reg_conflicts, this_reg);
1314 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1315 Perhaps it had previously seemed not worth a hard reg,
1316 or perhaps its old hard reg has been commandeered for reloads.
1317 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1318 they do not appear to be allocated.
1319 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1322 retry_global_alloc (int regno, HARD_REG_SET forbidden_regs)
1324 int alloc_no = reg_allocno[regno];
1327 /* If we have more than one register class,
1328 first try allocating in the class that is cheapest
1329 for this pseudo-reg. If that fails, try any reg. */
1330 if (N_REG_CLASSES > 1)
1331 find_reg (alloc_no, forbidden_regs, 0, 0, 1);
1332 if (reg_renumber[regno] < 0
1333 && reg_alternate_class (regno) != NO_REGS)
1334 find_reg (alloc_no, forbidden_regs, 1, 0, 1);
1336 /* If we found a register, modify the RTL for the register to
1337 show the hard register, and mark that register live. */
1338 if (reg_renumber[regno] >= 0)
1340 REGNO (regno_reg_rtx[regno]) = reg_renumber[regno];
1341 mark_home_live (regno);
1346 /* Record a conflict between register REGNO
1347 and everything currently live.
1348 REGNO must not be a pseudo reg that was allocated
1349 by local_alloc; such numbers must be translated through
1350 reg_renumber before calling here. */
1353 record_one_conflict (int regno)
1357 if (regno < FIRST_PSEUDO_REGISTER)
1358 /* When a hard register becomes live,
1359 record conflicts with live pseudo regs. */
1360 EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live, j,
1362 SET_HARD_REG_BIT (allocno[j].hard_reg_conflicts, regno);
1365 /* When a pseudo-register becomes live,
1366 record conflicts first with hard regs,
1367 then with other pseudo regs. */
1369 int ialloc = reg_allocno[regno];
1370 int ialloc_prod = ialloc * allocno_row_words;
1372 IOR_HARD_REG_SET (allocno[ialloc].hard_reg_conflicts, hard_regs_live);
1373 for (j = allocno_row_words - 1; j >= 0; j--)
1377 for (k = 0; k < n_no_conflict_pairs; k++)
1378 if (! ((j == no_conflict_pairs[k].allocno1
1379 && ialloc == no_conflict_pairs[k].allocno2)
1381 (j == no_conflict_pairs[k].allocno2
1382 && ialloc == no_conflict_pairs[k].allocno1)))
1384 conflicts[ialloc_prod + j] |= allocnos_live[j];
1389 /* Record all allocnos currently live as conflicting
1390 with all hard regs currently live.
1392 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1393 are currently live. Their bits are also flagged in allocnos_live. */
1396 record_conflicts (int *allocno_vec, int len)
1399 IOR_HARD_REG_SET (allocno[allocno_vec[len]].hard_reg_conflicts,
1403 /* If CONFLICTP (i, j) is true, make sure CONFLICTP (j, i) is also true. */
1405 mirror_conflicts (void)
1408 int rw = allocno_row_words;
1409 int rwb = rw * INT_BITS;
1410 INT_TYPE *p = conflicts;
1411 INT_TYPE *q0 = conflicts, *q1, *q2;
1412 unsigned INT_TYPE mask;
1414 for (i = max_allocno - 1, mask = 1; i >= 0; i--, mask <<= 1)
1421 for (j = allocno_row_words - 1, q1 = q0; j >= 0; j--, q1 += rwb)
1423 unsigned INT_TYPE word;
1425 for (word = (unsigned INT_TYPE) *p++, q2 = q1; word;
1426 word >>= 1, q2 += rw)
1435 /* Handle the case where REG is set by the insn being scanned,
1436 during the forward scan to accumulate conflicts.
1437 Store a 1 in regs_live or allocnos_live for this register, record how many
1438 consecutive hardware registers it actually needs,
1439 and record a conflict with all other registers already live.
1441 Note that even if REG does not remain alive after this insn,
1442 we must mark it here as live, to ensure a conflict between
1443 REG and any other regs set in this insn that really do live.
1444 This is because those other regs could be considered after this.
1446 REG might actually be something other than a register;
1447 if so, we do nothing.
1449 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1450 a REG_INC note was found for it). */
1453 mark_reg_store (rtx reg, rtx setter, void *data ATTRIBUTE_UNUSED)
1457 if (GET_CODE (reg) == SUBREG)
1458 reg = SUBREG_REG (reg);
1460 if (GET_CODE (reg) != REG)
1463 regs_set[n_regs_set++] = reg;
1465 if (setter && GET_CODE (setter) != CLOBBER)
1466 set_preference (reg, SET_SRC (setter));
1468 regno = REGNO (reg);
1470 /* Either this is one of the max_allocno pseudo regs not allocated,
1471 or it is or has a hardware reg. First handle the pseudo-regs. */
1472 if (regno >= FIRST_PSEUDO_REGISTER)
1474 if (reg_allocno[regno] >= 0)
1476 SET_ALLOCNO_LIVE (reg_allocno[regno]);
1477 record_one_conflict (regno);
1481 if (reg_renumber[regno] >= 0)
1482 regno = reg_renumber[regno];
1484 /* Handle hardware regs (and pseudos allocated to hard regs). */
1485 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1487 int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1488 while (regno < last)
1490 record_one_conflict (regno);
1491 SET_HARD_REG_BIT (hard_regs_live, regno);
1497 /* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
1500 mark_reg_clobber (rtx reg, rtx setter, void *data ATTRIBUTE_UNUSED)
1502 if (GET_CODE (setter) == CLOBBER)
1503 mark_reg_store (reg, setter, data);
1506 /* Record that REG has conflicts with all the regs currently live.
1507 Do not mark REG itself as live. */
1510 mark_reg_conflicts (rtx reg)
1514 if (GET_CODE (reg) == SUBREG)
1515 reg = SUBREG_REG (reg);
1517 if (GET_CODE (reg) != REG)
1520 regno = REGNO (reg);
1522 /* Either this is one of the max_allocno pseudo regs not allocated,
1523 or it is or has a hardware reg. First handle the pseudo-regs. */
1524 if (regno >= FIRST_PSEUDO_REGISTER)
1526 if (reg_allocno[regno] >= 0)
1527 record_one_conflict (regno);
1530 if (reg_renumber[regno] >= 0)
1531 regno = reg_renumber[regno];
1533 /* Handle hardware regs (and pseudos allocated to hard regs). */
1534 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1536 int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1537 while (regno < last)
1539 record_one_conflict (regno);
1545 /* Mark REG as being dead (following the insn being scanned now).
1546 Store a 0 in regs_live or allocnos_live for this register. */
1549 mark_reg_death (rtx reg)
1551 int regno = REGNO (reg);
1553 /* Either this is one of the max_allocno pseudo regs not allocated,
1554 or it is a hardware reg. First handle the pseudo-regs. */
1555 if (regno >= FIRST_PSEUDO_REGISTER)
1557 if (reg_allocno[regno] >= 0)
1558 CLEAR_ALLOCNO_LIVE (reg_allocno[regno]);
1561 /* For pseudo reg, see if it has been assigned a hardware reg. */
1562 if (reg_renumber[regno] >= 0)
1563 regno = reg_renumber[regno];
1565 /* Handle hardware regs (and pseudos allocated to hard regs). */
1566 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1568 /* Pseudo regs already assigned hardware regs are treated
1569 almost the same as explicit hardware regs. */
1570 int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1571 while (regno < last)
1573 CLEAR_HARD_REG_BIT (hard_regs_live, regno);
1579 /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1580 for the value stored in it. MODE determines how many consecutive
1581 registers are actually in use. Do not record conflicts;
1582 it is assumed that the caller will do that. */
1585 mark_reg_live_nc (int regno, enum machine_mode mode)
1587 int last = regno + HARD_REGNO_NREGS (regno, mode);
1588 while (regno < last)
1590 SET_HARD_REG_BIT (hard_regs_live, regno);
1595 /* Try to set a preference for an allocno to a hard register.
1596 We are passed DEST and SRC which are the operands of a SET. It is known
1597 that SRC is a register. If SRC or the first operand of SRC is a register,
1598 try to set a preference. If one of the two is a hard register and the other
1599 is a pseudo-register, mark the preference.
1601 Note that we are not as aggressive as local-alloc in trying to tie a
1602 pseudo-register to a hard register. */
1605 set_preference (rtx dest, rtx src)
1607 unsigned int src_regno, dest_regno;
1608 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1609 to compensate for subregs in SRC or DEST. */
1614 if (GET_RTX_FORMAT (GET_CODE (src))[0] == 'e')
1615 src = XEXP (src, 0), copy = 0;
1617 /* Get the reg number for both SRC and DEST.
1618 If neither is a reg, give up. */
1620 if (GET_CODE (src) == REG)
1621 src_regno = REGNO (src);
1622 else if (GET_CODE (src) == SUBREG && GET_CODE (SUBREG_REG (src)) == REG)
1624 src_regno = REGNO (SUBREG_REG (src));
1626 if (REGNO (SUBREG_REG (src)) < FIRST_PSEUDO_REGISTER)
1627 offset += subreg_regno_offset (REGNO (SUBREG_REG (src)),
1628 GET_MODE (SUBREG_REG (src)),
1632 offset += (SUBREG_BYTE (src)
1633 / REGMODE_NATURAL_SIZE (GET_MODE (src)));
1638 if (GET_CODE (dest) == REG)
1639 dest_regno = REGNO (dest);
1640 else if (GET_CODE (dest) == SUBREG && GET_CODE (SUBREG_REG (dest)) == REG)
1642 dest_regno = REGNO (SUBREG_REG (dest));
1644 if (REGNO (SUBREG_REG (dest)) < FIRST_PSEUDO_REGISTER)
1645 offset -= subreg_regno_offset (REGNO (SUBREG_REG (dest)),
1646 GET_MODE (SUBREG_REG (dest)),
1650 offset -= (SUBREG_BYTE (dest)
1651 / REGMODE_NATURAL_SIZE (GET_MODE (dest)));
1656 /* Convert either or both to hard reg numbers. */
1658 if (reg_renumber[src_regno] >= 0)
1659 src_regno = reg_renumber[src_regno];
1661 if (reg_renumber[dest_regno] >= 0)
1662 dest_regno = reg_renumber[dest_regno];
1664 /* Now if one is a hard reg and the other is a global pseudo
1665 then give the other a preference. */
1667 if (dest_regno < FIRST_PSEUDO_REGISTER && src_regno >= FIRST_PSEUDO_REGISTER
1668 && reg_allocno[src_regno] >= 0)
1670 dest_regno -= offset;
1671 if (dest_regno < FIRST_PSEUDO_REGISTER)
1674 SET_REGBIT (hard_reg_copy_preferences,
1675 reg_allocno[src_regno], dest_regno);
1677 SET_REGBIT (hard_reg_preferences,
1678 reg_allocno[src_regno], dest_regno);
1679 for (i = dest_regno;
1680 i < dest_regno + HARD_REGNO_NREGS (dest_regno, GET_MODE (dest));
1682 SET_REGBIT (hard_reg_full_preferences, reg_allocno[src_regno], i);
1686 if (src_regno < FIRST_PSEUDO_REGISTER && dest_regno >= FIRST_PSEUDO_REGISTER
1687 && reg_allocno[dest_regno] >= 0)
1689 src_regno += offset;
1690 if (src_regno < FIRST_PSEUDO_REGISTER)
1693 SET_REGBIT (hard_reg_copy_preferences,
1694 reg_allocno[dest_regno], src_regno);
1696 SET_REGBIT (hard_reg_preferences,
1697 reg_allocno[dest_regno], src_regno);
1699 i < src_regno + HARD_REGNO_NREGS (src_regno, GET_MODE (src));
1701 SET_REGBIT (hard_reg_full_preferences, reg_allocno[dest_regno], i);
1706 /* Indicate that hard register number FROM was eliminated and replaced with
1707 an offset from hard register number TO. The status of hard registers live
1708 at the start of a basic block is updated by replacing a use of FROM with
1712 mark_elimination (int from, int to)
1718 regset r = bb->global_live_at_start;
1719 if (REGNO_REG_SET_P (r, from))
1721 CLEAR_REGNO_REG_SET (r, from);
1722 SET_REGNO_REG_SET (r, to);
1727 /* Used for communication between the following functions. Holds the
1728 current life information. */
1729 static regset live_relevant_regs;
1731 /* Record in live_relevant_regs and REGS_SET that register REG became live.
1732 This is called via note_stores. */
1734 reg_becomes_live (rtx reg, rtx setter ATTRIBUTE_UNUSED, void *regs_set)
1738 if (GET_CODE (reg) == SUBREG)
1739 reg = SUBREG_REG (reg);
1741 if (GET_CODE (reg) != REG)
1744 regno = REGNO (reg);
1745 if (regno < FIRST_PSEUDO_REGISTER)
1747 int nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg));
1750 SET_REGNO_REG_SET (live_relevant_regs, regno);
1751 if (! fixed_regs[regno])
1752 SET_REGNO_REG_SET ((regset) regs_set, regno);
1756 else if (reg_renumber[regno] >= 0)
1758 SET_REGNO_REG_SET (live_relevant_regs, regno);
1759 SET_REGNO_REG_SET ((regset) regs_set, regno);
1763 /* Record in live_relevant_regs that register REGNO died. */
1765 reg_dies (int regno, enum machine_mode mode, struct insn_chain *chain)
1767 if (regno < FIRST_PSEUDO_REGISTER)
1769 int nregs = HARD_REGNO_NREGS (regno, mode);
1772 CLEAR_REGNO_REG_SET (live_relevant_regs, regno);
1773 if (! fixed_regs[regno])
1774 SET_REGNO_REG_SET (&chain->dead_or_set, regno);
1780 CLEAR_REGNO_REG_SET (live_relevant_regs, regno);
1781 if (reg_renumber[regno] >= 0)
1782 SET_REGNO_REG_SET (&chain->dead_or_set, regno);
1786 /* Walk the insns of the current function and build reload_insn_chain,
1787 and record register life information. */
1789 build_insn_chain (rtx first)
1791 struct insn_chain **p = &reload_insn_chain;
1792 struct insn_chain *prev = 0;
1793 basic_block b = ENTRY_BLOCK_PTR->next_bb;
1794 regset_head live_relevant_regs_head;
1796 live_relevant_regs = INITIALIZE_REG_SET (live_relevant_regs_head);
1798 for (; first; first = NEXT_INSN (first))
1800 struct insn_chain *c;
1802 if (first == BB_HEAD (b))
1806 CLEAR_REG_SET (live_relevant_regs);
1808 EXECUTE_IF_SET_IN_BITMAP
1809 (b->global_live_at_start, 0, i,
1811 if (i < FIRST_PSEUDO_REGISTER
1812 ? ! TEST_HARD_REG_BIT (eliminable_regset, i)
1813 : reg_renumber[i] >= 0)
1814 SET_REGNO_REG_SET (live_relevant_regs, i);
1818 if (GET_CODE (first) != NOTE && GET_CODE (first) != BARRIER)
1820 c = new_insn_chain ();
1826 c->block = b->index;
1832 /* Mark the death of everything that dies in this instruction. */
1834 for (link = REG_NOTES (first); link; link = XEXP (link, 1))
1835 if (REG_NOTE_KIND (link) == REG_DEAD
1836 && GET_CODE (XEXP (link, 0)) == REG)
1837 reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)),
1840 COPY_REG_SET (&c->live_throughout, live_relevant_regs);
1842 /* Mark everything born in this instruction as live. */
1844 note_stores (PATTERN (first), reg_becomes_live,
1848 COPY_REG_SET (&c->live_throughout, live_relevant_regs);
1854 /* Mark anything that is set in this insn and then unused as dying. */
1856 for (link = REG_NOTES (first); link; link = XEXP (link, 1))
1857 if (REG_NOTE_KIND (link) == REG_UNUSED
1858 && GET_CODE (XEXP (link, 0)) == REG)
1859 reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)),
1864 if (first == BB_END (b))
1867 /* Stop after we pass the end of the last basic block. Verify that
1868 no real insns are after the end of the last basic block.
1870 We may want to reorganize the loop somewhat since this test should
1871 always be the right exit test. Allow an ADDR_VEC or ADDR_DIF_VEC if
1872 the previous real insn is a JUMP_INSN. */
1873 if (b == EXIT_BLOCK_PTR)
1875 for (first = NEXT_INSN (first) ; first; first = NEXT_INSN (first))
1877 && GET_CODE (PATTERN (first)) != USE
1878 && ! ((GET_CODE (PATTERN (first)) == ADDR_VEC
1879 || GET_CODE (PATTERN (first)) == ADDR_DIFF_VEC)
1880 && prev_real_insn (first) != 0
1881 && GET_CODE (prev_real_insn (first)) == JUMP_INSN))
1886 FREE_REG_SET (live_relevant_regs);
1890 /* Print debugging trace information if -dg switch is given,
1891 showing the information on which the allocation decisions are based. */
1894 dump_conflicts (FILE *file)
1897 int has_preferences;
1900 for (i = 0; i < max_allocno; i++)
1902 if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
1906 fprintf (file, ";; %d regs to allocate:", nregs);
1907 for (i = 0; i < max_allocno; i++)
1910 if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
1912 fprintf (file, " %d", allocno[allocno_order[i]].reg);
1913 for (j = 0; j < max_regno; j++)
1914 if (reg_allocno[j] == allocno_order[i]
1915 && j != allocno[allocno_order[i]].reg)
1916 fprintf (file, "+%d", j);
1917 if (allocno[allocno_order[i]].size != 1)
1918 fprintf (file, " (%d)", allocno[allocno_order[i]].size);
1920 fprintf (file, "\n");
1922 for (i = 0; i < max_allocno; i++)
1925 fprintf (file, ";; %d conflicts:", allocno[i].reg);
1926 for (j = 0; j < max_allocno; j++)
1927 if (CONFLICTP (j, i))
1928 fprintf (file, " %d", allocno[j].reg);
1929 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1930 if (TEST_HARD_REG_BIT (allocno[i].hard_reg_conflicts, j))
1931 fprintf (file, " %d", j);
1932 fprintf (file, "\n");
1934 has_preferences = 0;
1935 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1936 if (TEST_HARD_REG_BIT (allocno[i].hard_reg_preferences, j))
1937 has_preferences = 1;
1939 if (! has_preferences)
1941 fprintf (file, ";; %d preferences:", allocno[i].reg);
1942 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1943 if (TEST_HARD_REG_BIT (allocno[i].hard_reg_preferences, j))
1944 fprintf (file, " %d", j);
1945 fprintf (file, "\n");
1947 fprintf (file, "\n");
1951 dump_global_regs (FILE *file)
1955 fprintf (file, ";; Register dispositions:\n");
1956 for (i = FIRST_PSEUDO_REGISTER, j = 0; i < max_regno; i++)
1957 if (reg_renumber[i] >= 0)
1959 fprintf (file, "%d in %d ", i, reg_renumber[i]);
1961 fprintf (file, "\n");
1964 fprintf (file, "\n\n;; Hard regs used: ");
1965 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1966 if (regs_ever_live[i])
1967 fprintf (file, " %d", i);
1968 fprintf (file, "\n\n");