1 /* Allocate registers for pseudo-registers that span basic blocks.
2 Copyright (C) 1987, 88, 91, 94, 96-98, 1999 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
26 #include "hard-reg-set.h"
30 #include "basic-block.h"
33 #include "insn-config.h"
38 /* This pass of the compiler performs global register allocation.
39 It assigns hard register numbers to all the pseudo registers
40 that were not handled in local_alloc. Assignments are recorded
41 in the vector reg_renumber, not by changing the rtl code.
42 (Such changes are made by final). The entry point is
43 the function global_alloc.
45 After allocation is complete, the reload pass is run as a subroutine
46 of this pass, so that when a pseudo reg loses its hard reg due to
47 spilling it is possible to make a second attempt to find a hard
48 reg for it. The reload pass is independent in other respects
49 and it is run even when stupid register allocation is in use.
51 1. Assign allocation-numbers (allocnos) to the pseudo-registers
52 still needing allocations and to the pseudo-registers currently
53 allocated by local-alloc which may be spilled by reload.
54 Set up tables reg_allocno and allocno_reg to map
55 reg numbers to allocnos and vice versa.
56 max_allocno gets the number of allocnos in use.
58 2. Allocate a max_allocno by max_allocno conflict bit matrix and clear it.
59 Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix
60 for conflicts between allocnos and explicit hard register use
61 (which includes use of pseudo-registers allocated by local_alloc).
63 3. For each basic block
64 walk forward through the block, recording which
65 pseudo-registers and which hardware registers are live.
66 Build the conflict matrix between the pseudo-registers
67 and another of pseudo-registers versus hardware registers.
68 Also record the preferred hardware registers
69 for each pseudo-register.
71 4. Sort a table of the allocnos into order of
72 desirability of the variables.
74 5. Allocate the variables in that order; each if possible into
75 a preferred register, else into another register. */
77 /* Number of pseudo-registers which are candidates for allocation. */
79 static int max_allocno;
81 /* Indexed by (pseudo) reg number, gives the allocno, or -1
82 for pseudo registers which are not to be allocated. */
84 static int *reg_allocno;
86 /* Indexed by allocno, gives the reg number. */
88 static int *allocno_reg;
90 /* A vector of the integers from 0 to max_allocno-1,
91 sorted in the order of first-to-be-allocated first. */
93 static int *allocno_order;
95 /* Indexed by an allocno, gives the number of consecutive
96 hard registers needed by that pseudo reg. */
98 static int *allocno_size;
100 /* Indexed by (pseudo) reg number, gives the number of another
101 lower-numbered pseudo reg which can share a hard reg with this pseudo
102 *even if the two pseudos would otherwise appear to conflict*. */
104 static int *reg_may_share;
106 /* Define the number of bits in each element of `conflicts' and what
107 type that element has. We use the largest integer format on the
110 #define INT_BITS HOST_BITS_PER_WIDE_INT
111 #define INT_TYPE HOST_WIDE_INT
113 /* max_allocno by max_allocno array of bits,
114 recording whether two allocno's conflict (can't go in the same
117 `conflicts' is symmetric after the call to mirror_conflicts. */
119 static INT_TYPE *conflicts;
121 /* Number of ints require to hold max_allocno bits.
122 This is the length of a row in `conflicts'. */
124 static int allocno_row_words;
126 /* Two macros to test or store 1 in an element of `conflicts'. */
128 #define CONFLICTP(I, J) \
129 (conflicts[(I) * allocno_row_words + (unsigned)(J) / INT_BITS] \
130 & ((INT_TYPE) 1 << ((unsigned)(J) % INT_BITS)))
132 #define SET_CONFLICT(I, J) \
133 (conflicts[(I) * allocno_row_words + (unsigned)(J) / INT_BITS] \
134 |= ((INT_TYPE) 1 << ((unsigned)(J) % INT_BITS)))
136 /* Set of hard regs currently live (during scan of all insns). */
138 static HARD_REG_SET hard_regs_live;
140 /* Indexed by N, set of hard regs conflicting with allocno N. */
142 static HARD_REG_SET *hard_reg_conflicts;
144 /* Indexed by N, set of hard regs preferred by allocno N.
145 This is used to make allocnos go into regs that are copied to or from them,
146 when possible, to reduce register shuffling. */
148 static HARD_REG_SET *hard_reg_preferences;
150 /* Similar, but just counts register preferences made in simple copy
151 operations, rather than arithmetic. These are given priority because
152 we can always eliminate an insn by using these, but using a register
153 in the above list won't always eliminate an insn. */
155 static HARD_REG_SET *hard_reg_copy_preferences;
157 /* Similar to hard_reg_preferences, but includes bits for subsequent
158 registers when an allocno is multi-word. The above variable is used for
159 allocation while this is used to build reg_someone_prefers, below. */
161 static HARD_REG_SET *hard_reg_full_preferences;
163 /* Indexed by N, set of hard registers that some later allocno has a
166 static HARD_REG_SET *regs_someone_prefers;
168 /* Set of registers that global-alloc isn't supposed to use. */
170 static HARD_REG_SET no_global_alloc_regs;
172 /* Set of registers used so far. */
174 static HARD_REG_SET regs_used_so_far;
176 /* Number of calls crossed by each allocno. */
178 static int *allocno_calls_crossed;
180 /* Number of refs (weighted) to each allocno. */
182 static int *allocno_n_refs;
184 /* Guess at live length of each allocno.
185 This is actually the max of the live lengths of the regs. */
187 static int *allocno_live_length;
189 /* Number of refs (weighted) to each hard reg, as used by local alloc.
190 It is zero for a reg that contains global pseudos or is explicitly used. */
192 static int local_reg_n_refs[FIRST_PSEUDO_REGISTER];
194 /* Guess at live length of each hard reg, as used by local alloc.
195 This is actually the sum of the live lengths of the specific regs. */
197 static int local_reg_live_length[FIRST_PSEUDO_REGISTER];
199 /* Test a bit in TABLE, a vector of HARD_REG_SETs,
200 for vector element I, and hard register number J. */
202 #define REGBITP(TABLE, I, J) TEST_HARD_REG_BIT (TABLE[I], J)
204 /* Set to 1 a bit in a vector of HARD_REG_SETs. Works like REGBITP. */
206 #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (TABLE[I], J)
208 /* Bit mask for allocnos live at current point in the scan. */
210 static INT_TYPE *allocnos_live;
212 /* Test, set or clear bit number I in allocnos_live,
213 a bit vector indexed by allocno. */
215 #define ALLOCNO_LIVE_P(I) \
216 (allocnos_live[(I) / INT_BITS] & ((INT_TYPE) 1 << ((I) % INT_BITS)))
218 #define SET_ALLOCNO_LIVE(I) \
219 (allocnos_live[(I) / INT_BITS] |= ((INT_TYPE) 1 << ((I) % INT_BITS)))
221 #define CLEAR_ALLOCNO_LIVE(I) \
222 (allocnos_live[(I) / INT_BITS] &= ~((INT_TYPE) 1 << ((I) % INT_BITS)))
224 /* This is turned off because it doesn't work right for DImode.
225 (And it is only used for DImode, so the other cases are worthless.)
226 The problem is that it isn't true that there is NO possibility of conflict;
227 only that there is no conflict if the two pseudos get the exact same regs.
228 If they were allocated with a partial overlap, there would be a conflict.
229 We can't safely turn off the conflict unless we have another way to
230 prevent the partial overlap.
232 Idea: change hard_reg_conflicts so that instead of recording which
233 hard regs the allocno may not overlap, it records where the allocno
234 may not start. Change both where it is used and where it is updated.
235 Then there is a way to record that (reg:DI 108) may start at 10
236 but not at 9 or 11. There is still the question of how to record
237 this semi-conflict between two pseudos. */
239 /* Reg pairs for which conflict after the current insn
240 is inhibited by a REG_NO_CONFLICT note.
241 If the table gets full, we ignore any other notes--that is conservative. */
242 #define NUM_NO_CONFLICT_PAIRS 4
243 /* Number of pairs in use in this insn. */
244 int n_no_conflict_pairs;
245 static struct { int allocno1, allocno2;}
246 no_conflict_pairs[NUM_NO_CONFLICT_PAIRS];
249 /* Record all regs that are set in any one insn.
250 Communication from mark_reg_{store,clobber} and global_conflicts. */
252 static rtx *regs_set;
253 static int n_regs_set;
255 /* All registers that can be eliminated. */
257 static HARD_REG_SET eliminable_regset;
259 static int allocno_compare PROTO((const PTR, const PTR));
260 static void global_conflicts PROTO((void));
261 static void mirror_conflicts PROTO((void));
262 static void expand_preferences PROTO((void));
263 static void prune_preferences PROTO((void));
264 static void find_reg PROTO((int, HARD_REG_SET, int, int, int));
265 static void record_one_conflict PROTO((int));
266 static void record_conflicts PROTO((int *, int));
267 static void mark_reg_store PROTO((rtx, rtx, void *));
268 static void mark_reg_clobber PROTO((rtx, rtx, void *));
269 static void mark_reg_conflicts PROTO((rtx));
270 static void mark_reg_death PROTO((rtx));
271 static void mark_reg_live_nc PROTO((int, enum machine_mode));
272 static void set_preference PROTO((rtx, rtx));
273 static void dump_conflicts PROTO((FILE *));
274 static void reg_becomes_live PROTO((rtx, rtx, void *));
275 static void reg_dies PROTO((int, enum machine_mode));
276 static void build_insn_chain PROTO((rtx));
278 /* Perform allocation of pseudo-registers not allocated by local_alloc.
279 FILE is a file to output debugging information on,
280 or zero if such output is not desired.
282 Return value is nonzero if reload failed
283 and we must not do any more for this function. */
290 #ifdef ELIMINABLE_REGS
291 static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
294 = (! flag_omit_frame_pointer
295 #ifdef EXIT_IGNORE_STACK
296 || (current_function_calls_alloca && EXIT_IGNORE_STACK)
298 || FRAME_POINTER_REQUIRED);
305 /* A machine may have certain hard registers that
306 are safe to use only within a basic block. */
308 CLEAR_HARD_REG_SET (no_global_alloc_regs);
309 #ifdef OVERLAPPING_REGNO_P
310 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
311 if (OVERLAPPING_REGNO_P (i))
312 SET_HARD_REG_BIT (no_global_alloc_regs, i);
315 /* Build the regset of all eliminable registers and show we can't use those
316 that we already know won't be eliminated. */
317 #ifdef ELIMINABLE_REGS
318 for (i = 0; i < sizeof eliminables / sizeof eliminables[0]; i++)
320 SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from);
322 if (! CAN_ELIMINATE (eliminables[i].from, eliminables[i].to)
323 || (eliminables[i].to == STACK_POINTER_REGNUM && need_fp))
324 SET_HARD_REG_BIT (no_global_alloc_regs, eliminables[i].from);
326 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
327 SET_HARD_REG_BIT (eliminable_regset, HARD_FRAME_POINTER_REGNUM);
329 SET_HARD_REG_BIT (no_global_alloc_regs, HARD_FRAME_POINTER_REGNUM);
333 SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM);
335 SET_HARD_REG_BIT (no_global_alloc_regs, FRAME_POINTER_REGNUM);
338 /* Track which registers have already been used. Start with registers
339 explicitly in the rtl, then registers allocated by local register
342 CLEAR_HARD_REG_SET (regs_used_so_far);
343 #ifdef LEAF_REGISTERS
344 /* If we are doing the leaf function optimization, and this is a leaf
345 function, it means that the registers that take work to save are those
346 that need a register window. So prefer the ones that can be used in
350 static char leaf_regs[] = LEAF_REGISTERS;
352 if (only_leaf_regs_used () && leaf_function_p ())
353 cheap_regs = leaf_regs;
355 cheap_regs = call_used_regs;
356 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
357 if (regs_ever_live[i] || cheap_regs[i])
358 SET_HARD_REG_BIT (regs_used_so_far, i);
361 /* We consider registers that do not have to be saved over calls as if
362 they were already used since there is no cost in using them. */
363 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
364 if (regs_ever_live[i] || call_used_regs[i])
365 SET_HARD_REG_BIT (regs_used_so_far, i);
368 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
369 if (reg_renumber[i] >= 0)
370 SET_HARD_REG_BIT (regs_used_so_far, reg_renumber[i]);
372 /* Establish mappings from register number to allocation number
373 and vice versa. In the process, count the allocnos. */
375 reg_allocno = (int *) xmalloc (max_regno * sizeof (int));
377 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
380 /* Initialize the shared-hard-reg mapping
381 from the list of pairs that may share. */
382 reg_may_share = (int *) xcalloc (max_regno, sizeof (int));
383 for (x = regs_may_share; x; x = XEXP (XEXP (x, 1), 1))
385 int r1 = REGNO (XEXP (x, 0));
386 int r2 = REGNO (XEXP (XEXP (x, 1), 0));
388 reg_may_share[r1] = r2;
390 reg_may_share[r2] = r1;
393 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
394 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
395 that we are supposed to refrain from putting in a hard reg.
396 -2 means do make an allocno but don't allocate it. */
397 if (REG_N_REFS (i) != 0 && REG_LIVE_LENGTH (i) != -1
398 /* Don't allocate pseudos that cross calls,
399 if this function receives a nonlocal goto. */
400 && (! current_function_has_nonlocal_label
401 || REG_N_CALLS_CROSSED (i) == 0))
403 if (reg_renumber[i] < 0 && reg_may_share[i] && reg_allocno[reg_may_share[i]] >= 0)
404 reg_allocno[i] = reg_allocno[reg_may_share[i]];
406 reg_allocno[i] = max_allocno++;
407 if (REG_LIVE_LENGTH (i) == 0)
413 allocno_reg = (int *) xmalloc (max_allocno * sizeof (int));
414 allocno_size = (int *) xcalloc (max_allocno, sizeof (int));
415 allocno_calls_crossed = (int *) xcalloc (max_allocno, sizeof (int));
416 allocno_n_refs = (int *) xcalloc (max_allocno, sizeof (int));
417 allocno_live_length = (int *) xcalloc (max_allocno, sizeof (int));
419 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
420 if (reg_allocno[i] >= 0)
422 int allocno = reg_allocno[i];
423 allocno_reg[allocno] = i;
424 allocno_size[allocno] = PSEUDO_REGNO_SIZE (i);
425 allocno_calls_crossed[allocno] += REG_N_CALLS_CROSSED (i);
426 allocno_n_refs[allocno] += REG_N_REFS (i);
427 if (allocno_live_length[allocno] < REG_LIVE_LENGTH (i))
428 allocno_live_length[allocno] = REG_LIVE_LENGTH (i);
431 /* Calculate amount of usage of each hard reg by pseudos
432 allocated by local-alloc. This is to see if we want to
434 bzero ((char *) local_reg_live_length, sizeof local_reg_live_length);
435 bzero ((char *) local_reg_n_refs, sizeof local_reg_n_refs);
436 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
437 if (reg_renumber[i] >= 0)
439 int regno = reg_renumber[i];
440 int endregno = regno + HARD_REGNO_NREGS (regno, PSEUDO_REGNO_MODE (i));
443 for (j = regno; j < endregno; j++)
445 local_reg_n_refs[j] += REG_N_REFS (i);
446 local_reg_live_length[j] += REG_LIVE_LENGTH (i);
450 /* We can't override local-alloc for a reg used not just by local-alloc. */
451 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
452 if (regs_ever_live[i])
453 local_reg_n_refs[i] = 0;
455 /* Allocate the space for the conflict and preference tables and
459 = (HARD_REG_SET *) xcalloc (max_allocno, sizeof (HARD_REG_SET));
461 = (HARD_REG_SET *) xcalloc (max_allocno, sizeof (HARD_REG_SET));
462 hard_reg_copy_preferences
463 = (HARD_REG_SET *) xcalloc (max_allocno, sizeof (HARD_REG_SET));
464 hard_reg_full_preferences
465 = (HARD_REG_SET *) xcalloc (max_allocno, sizeof (HARD_REG_SET));
467 = (HARD_REG_SET *) xcalloc (max_allocno, sizeof (HARD_REG_SET));
469 allocno_row_words = (max_allocno + INT_BITS - 1) / INT_BITS;
471 /* We used to use alloca here, but the size of what it would try to
472 allocate would occasionally cause it to exceed the stack limit and
473 cause unpredictable core dumps. Some examples were > 2Mb in size. */
474 conflicts = (INT_TYPE *) xcalloc (max_allocno * allocno_row_words,
477 allocnos_live = (INT_TYPE *) xmalloc (allocno_row_words * sizeof (INT_TYPE));
479 /* If there is work to be done (at least one reg to allocate),
480 perform global conflict analysis and allocate the regs. */
484 /* Scan all the insns and compute the conflicts among allocnos
485 and between allocnos and hard regs. */
491 /* Eliminate conflicts between pseudos and eliminable registers. If
492 the register is not eliminated, the pseudo won't really be able to
493 live in the eliminable register, so the conflict doesn't matter.
494 If we do eliminate the register, the conflict will no longer exist.
495 So in either case, we can ignore the conflict. Likewise for
498 for (i = 0; i < (size_t) max_allocno; i++)
500 AND_COMPL_HARD_REG_SET (hard_reg_conflicts[i], eliminable_regset);
501 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[i],
503 AND_COMPL_HARD_REG_SET (hard_reg_preferences[i], eliminable_regset);
506 /* Try to expand the preferences by merging them between allocnos. */
508 expand_preferences ();
510 /* Determine the order to allocate the remaining pseudo registers. */
512 allocno_order = (int *) xmalloc (max_allocno * sizeof (int));
513 for (i = 0; i < (size_t) max_allocno; i++)
514 allocno_order[i] = i;
516 /* Default the size to 1, since allocno_compare uses it to divide by.
517 Also convert allocno_live_length of zero to -1. A length of zero
518 can occur when all the registers for that allocno have reg_live_length
519 equal to -2. In this case, we want to make an allocno, but not
520 allocate it. So avoid the divide-by-zero and set it to a low
523 for (i = 0; i < (size_t) max_allocno; i++)
525 if (allocno_size[i] == 0)
527 if (allocno_live_length[i] == 0)
528 allocno_live_length[i] = -1;
531 qsort (allocno_order, max_allocno, sizeof (int), allocno_compare);
533 prune_preferences ();
536 dump_conflicts (file);
538 /* Try allocating them, one by one, in that order,
539 except for parameters marked with reg_live_length[regno] == -2. */
541 for (i = 0; i < (size_t) max_allocno; i++)
542 if (reg_renumber[allocno_reg[allocno_order[i]]] < 0
543 && REG_LIVE_LENGTH (allocno_reg[allocno_order[i]]) >= 0)
545 /* If we have more than one register class,
546 first try allocating in the class that is cheapest
547 for this pseudo-reg. If that fails, try any reg. */
548 if (N_REG_CLASSES > 1)
550 find_reg (allocno_order[i], 0, 0, 0, 0);
551 if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
554 if (reg_alternate_class (allocno_reg[allocno_order[i]]) != NO_REGS)
555 find_reg (allocno_order[i], 0, 1, 0, 0);
558 free (allocno_order);
561 /* Do the reloads now while the allocno data still exist, so that we can
562 try to assign new hard regs to any pseudo regs that are spilled. */
564 #if 0 /* We need to eliminate regs even if there is no rtl code,
565 for the sake of debugging information. */
566 if (n_basic_blocks > 0)
569 build_insn_chain (get_insns ());
570 retval = reload (get_insns (), 1, file);
575 free (reg_may_share);
578 free (allocno_calls_crossed);
579 free (allocno_n_refs);
580 free (allocno_live_length);
581 free (hard_reg_conflicts);
582 free (hard_reg_preferences);
583 free (hard_reg_copy_preferences);
584 free (hard_reg_full_preferences);
585 free (regs_someone_prefers);
587 free (allocnos_live);
592 /* Sort predicate for ordering the allocnos.
593 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
596 allocno_compare (v1p, v2p)
600 int v1 = *(const int *)v1p, v2 = *(const int *)v2p;
601 /* Note that the quotient will never be bigger than
602 the value of floor_log2 times the maximum number of
603 times a register can occur in one insn (surely less than 100).
604 Multiplying this by 10000 can't overflow. */
606 = (((double) (floor_log2 (allocno_n_refs[v1]) * allocno_n_refs[v1])
607 / allocno_live_length[v1])
608 * 10000 * allocno_size[v1]);
610 = (((double) (floor_log2 (allocno_n_refs[v2]) * allocno_n_refs[v2])
611 / allocno_live_length[v2])
612 * 10000 * allocno_size[v2]);
616 /* If regs are equally good, sort by allocno,
617 so that the results of qsort leave nothing to chance. */
621 /* Scan the rtl code and record all conflicts and register preferences in the
622 conflict matrices and preference tables. */
629 int *block_start_allocnos;
631 /* Make a vector that mark_reg_{store,clobber} will store in. */
632 regs_set = (rtx *) xmalloc (max_parallel * sizeof (rtx) * 2);
634 block_start_allocnos = (int *) xmalloc (max_allocno * sizeof (int));
636 for (b = 0; b < n_basic_blocks; b++)
638 bzero ((char *) allocnos_live, allocno_row_words * sizeof (INT_TYPE));
640 /* Initialize table of registers currently live
641 to the state at the beginning of this basic block.
642 This also marks the conflicts among them.
644 For pseudo-regs, there is only one bit for each one
645 no matter how many hard regs it occupies.
646 This is ok; we know the size from PSEUDO_REGNO_SIZE.
647 For explicit hard regs, we cannot know the size that way
648 since one hard reg can be used with various sizes.
649 Therefore, we must require that all the hard regs
650 implicitly live as part of a multi-word hard reg
651 are explicitly marked in basic_block_live_at_start. */
654 register regset old = BASIC_BLOCK (b)->global_live_at_start;
657 REG_SET_TO_HARD_REG_SET (hard_regs_live, old);
658 EXECUTE_IF_SET_IN_REG_SET (old, FIRST_PSEUDO_REGISTER, i,
660 register int a = reg_allocno[i];
663 SET_ALLOCNO_LIVE (a);
664 block_start_allocnos[ax++] = a;
666 else if ((a = reg_renumber[i]) >= 0)
668 (a, PSEUDO_REGNO_MODE (i));
671 /* Record that each allocno now live conflicts with each other
672 allocno now live, and with each hard reg now live. */
674 record_conflicts (block_start_allocnos, ax);
678 /* Pseudos can't go in stack regs at the start of a basic block
679 that is reached by an abnormal edge. */
682 for (e = BASIC_BLOCK (b)->pred; e ; e = e->pred_next)
683 if (e->flags & EDGE_ABNORMAL)
686 for (ax = FIRST_STACK_REG; ax <= LAST_STACK_REG; ax++)
687 record_one_conflict (ax);
692 insn = BLOCK_HEAD (b);
694 /* Scan the code of this basic block, noting which allocnos
695 and hard regs are born or die. When one is born,
696 record a conflict with all others currently live. */
700 register RTX_CODE code = GET_CODE (insn);
703 /* Make regs_set an empty set. */
707 if (code == INSN || code == CALL_INSN || code == JUMP_INSN)
712 for (link = REG_NOTES (insn);
713 link && i < NUM_NO_CONFLICT_PAIRS;
714 link = XEXP (link, 1))
715 if (REG_NOTE_KIND (link) == REG_NO_CONFLICT)
717 no_conflict_pairs[i].allocno1
718 = reg_allocno[REGNO (SET_DEST (PATTERN (insn)))];
719 no_conflict_pairs[i].allocno2
720 = reg_allocno[REGNO (XEXP (link, 0))];
725 /* Mark any registers clobbered by INSN as live,
726 so they conflict with the inputs. */
728 note_stores (PATTERN (insn), mark_reg_clobber, NULL);
730 /* Mark any registers dead after INSN as dead now. */
732 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
733 if (REG_NOTE_KIND (link) == REG_DEAD)
734 mark_reg_death (XEXP (link, 0));
736 /* Mark any registers set in INSN as live,
737 and mark them as conflicting with all other live regs.
738 Clobbers are processed again, so they conflict with
739 the registers that are set. */
741 note_stores (PATTERN (insn), mark_reg_store, NULL);
744 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
745 if (REG_NOTE_KIND (link) == REG_INC)
746 mark_reg_store (XEXP (link, 0), NULL_RTX, NULL);
749 /* If INSN has multiple outputs, then any reg that dies here
750 and is used inside of an output
751 must conflict with the other outputs.
753 It is unsafe to use !single_set here since it will ignore an
754 unused output. Just because an output is unused does not mean
755 the compiler can assume the side effect will not occur.
756 Consider if REG appears in the address of an output and we
757 reload the output. If we allocate REG to the same hard
758 register as an unused output we could set the hard register
759 before the output reload insn. */
760 if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn))
761 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
762 if (REG_NOTE_KIND (link) == REG_DEAD)
764 int used_in_output = 0;
766 rtx reg = XEXP (link, 0);
768 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
770 rtx set = XVECEXP (PATTERN (insn), 0, i);
771 if (GET_CODE (set) == SET
772 && GET_CODE (SET_DEST (set)) != REG
773 && !rtx_equal_p (reg, SET_DEST (set))
774 && reg_overlap_mentioned_p (reg, SET_DEST (set)))
778 mark_reg_conflicts (reg);
781 /* Mark any registers set in INSN and then never used. */
783 while (n_regs_set > 0)
784 if (find_regno_note (insn, REG_UNUSED,
785 REGNO (regs_set[--n_regs_set])))
786 mark_reg_death (regs_set[n_regs_set]);
789 if (insn == BLOCK_END (b))
791 insn = NEXT_INSN (insn);
796 free (block_start_allocnos);
799 /* Expand the preference information by looking for cases where one allocno
800 dies in an insn that sets an allocno. If those two allocnos don't conflict,
801 merge any preferences between those allocnos. */
804 expand_preferences ()
810 /* We only try to handle the most common cases here. Most of the cases
811 where this wins are reg-reg copies. */
813 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
814 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
815 && (set = single_set (insn)) != 0
816 && GET_CODE (SET_DEST (set)) == REG
817 && reg_allocno[REGNO (SET_DEST (set))] >= 0)
818 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
819 if (REG_NOTE_KIND (link) == REG_DEAD
820 && GET_CODE (XEXP (link, 0)) == REG
821 && reg_allocno[REGNO (XEXP (link, 0))] >= 0
822 && ! CONFLICTP (reg_allocno[REGNO (SET_DEST (set))],
823 reg_allocno[REGNO (XEXP (link, 0))]))
825 int a1 = reg_allocno[REGNO (SET_DEST (set))];
826 int a2 = reg_allocno[REGNO (XEXP (link, 0))];
828 if (XEXP (link, 0) == SET_SRC (set))
830 IOR_HARD_REG_SET (hard_reg_copy_preferences[a1],
831 hard_reg_copy_preferences[a2]);
832 IOR_HARD_REG_SET (hard_reg_copy_preferences[a2],
833 hard_reg_copy_preferences[a1]);
836 IOR_HARD_REG_SET (hard_reg_preferences[a1],
837 hard_reg_preferences[a2]);
838 IOR_HARD_REG_SET (hard_reg_preferences[a2],
839 hard_reg_preferences[a1]);
840 IOR_HARD_REG_SET (hard_reg_full_preferences[a1],
841 hard_reg_full_preferences[a2]);
842 IOR_HARD_REG_SET (hard_reg_full_preferences[a2],
843 hard_reg_full_preferences[a1]);
847 /* Prune the preferences for global registers to exclude registers that cannot
850 Compute `regs_someone_prefers', which is a bitmask of the hard registers
851 that are preferred by conflicting registers of lower priority. If possible,
852 we will avoid using these registers. */
859 int *allocno_to_order = (int *) xmalloc (max_allocno * sizeof (int));
861 /* Scan least most important to most important.
862 For each allocno, remove from preferences registers that cannot be used,
863 either because of conflicts or register type. Then compute all registers
864 preferred by each lower-priority register that conflicts. */
866 for (i = max_allocno - 1; i >= 0; i--)
870 allocno = allocno_order[i];
871 allocno_to_order[allocno] = i;
872 COPY_HARD_REG_SET (temp, hard_reg_conflicts[allocno]);
874 if (allocno_calls_crossed[allocno] == 0)
875 IOR_HARD_REG_SET (temp, fixed_reg_set);
877 IOR_HARD_REG_SET (temp, call_used_reg_set);
879 IOR_COMPL_HARD_REG_SET
881 reg_class_contents[(int) reg_preferred_class (allocno_reg[allocno])]);
883 AND_COMPL_HARD_REG_SET (hard_reg_preferences[allocno], temp);
884 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[allocno], temp);
885 AND_COMPL_HARD_REG_SET (hard_reg_full_preferences[allocno], temp);
888 for (i = max_allocno - 1; i >= 0; i--)
890 /* Merge in the preferences of lower-priority registers (they have
891 already been pruned). If we also prefer some of those registers,
892 don't exclude them unless we are of a smaller size (in which case
893 we want to give the lower-priority allocno the first chance for
895 HARD_REG_SET temp, temp2;
897 int allocno2, allocno3;
899 allocno = allocno_order[i];
900 p = conflicts + allocno * allocno_row_words;
902 CLEAR_HARD_REG_SET (temp);
903 CLEAR_HARD_REG_SET (temp2);
905 for (j = allocno_row_words - 1, allocno2 = 0; j >= 0;
906 j--, allocno2 += INT_BITS)
908 unsigned INT_TYPE word = (unsigned INT_TYPE) *p++;
910 for (allocno3 = allocno2; word; word >>= 1, allocno3++)
912 if ((word & 1) && allocno_to_order[allocno3] > i)
914 if (allocno_size[allocno3] <= allocno_size[allocno])
915 IOR_HARD_REG_SET (temp,
916 hard_reg_full_preferences[allocno3]);
918 IOR_HARD_REG_SET (temp2,
919 hard_reg_full_preferences[allocno3]);
924 AND_COMPL_HARD_REG_SET (temp, hard_reg_full_preferences[allocno]);
925 IOR_HARD_REG_SET (temp, temp2);
926 COPY_HARD_REG_SET (regs_someone_prefers[allocno], temp);
928 free (allocno_to_order);
931 /* Assign a hard register to ALLOCNO; look for one that is the beginning
932 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
933 The registers marked in PREFREGS are tried first.
935 LOSERS, if non-zero, is a HARD_REG_SET indicating registers that cannot
936 be used for this allocation.
938 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
939 Otherwise ignore that preferred class and use the alternate class.
941 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
942 will have to be saved and restored at calls.
944 RETRYING is nonzero if this is called from retry_global_alloc.
946 If we find one, record it in reg_renumber.
947 If not, do nothing. */
950 find_reg (allocno, losers, alt_regs_p, accept_call_clobbered, retrying)
954 int accept_call_clobbered;
957 register int i, best_reg, pass;
959 register /* Declare it register if it's a scalar. */
961 HARD_REG_SET used, used1, used2;
963 enum reg_class class = (alt_regs_p
964 ? reg_alternate_class (allocno_reg[allocno])
965 : reg_preferred_class (allocno_reg[allocno]));
966 enum machine_mode mode = PSEUDO_REGNO_MODE (allocno_reg[allocno]);
968 if (accept_call_clobbered)
969 COPY_HARD_REG_SET (used1, call_fixed_reg_set);
970 else if (allocno_calls_crossed[allocno] == 0)
971 COPY_HARD_REG_SET (used1, fixed_reg_set);
973 COPY_HARD_REG_SET (used1, call_used_reg_set);
975 /* Some registers should not be allocated in global-alloc. */
976 IOR_HARD_REG_SET (used1, no_global_alloc_regs);
978 IOR_HARD_REG_SET (used1, losers);
980 IOR_COMPL_HARD_REG_SET (used1, reg_class_contents[(int) class]);
981 COPY_HARD_REG_SET (used2, used1);
983 IOR_HARD_REG_SET (used1, hard_reg_conflicts[allocno]);
985 #ifdef CLASS_CANNOT_CHANGE_SIZE
986 if (REG_CHANGES_SIZE (allocno_reg[allocno]))
987 IOR_HARD_REG_SET (used1,
988 reg_class_contents[(int) CLASS_CANNOT_CHANGE_SIZE]);
991 /* Try each hard reg to see if it fits. Do this in two passes.
992 In the first pass, skip registers that are preferred by some other pseudo
993 to give it a better chance of getting one of those registers. Only if
994 we can't get a register when excluding those do we take one of them.
995 However, we never allocate a register for the first time in pass 0. */
997 COPY_HARD_REG_SET (used, used1);
998 IOR_COMPL_HARD_REG_SET (used, regs_used_so_far);
999 IOR_HARD_REG_SET (used, regs_someone_prefers[allocno]);
1002 for (i = FIRST_PSEUDO_REGISTER, pass = 0;
1003 pass <= 1 && i >= FIRST_PSEUDO_REGISTER;
1007 COPY_HARD_REG_SET (used, used1);
1008 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1010 #ifdef REG_ALLOC_ORDER
1011 int regno = reg_alloc_order[i];
1015 if (! TEST_HARD_REG_BIT (used, regno)
1016 && HARD_REGNO_MODE_OK (regno, mode)
1017 && (allocno_calls_crossed[allocno] == 0
1018 || accept_call_clobbered
1019 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
1022 register int lim = regno + HARD_REGNO_NREGS (regno, mode);
1025 && ! TEST_HARD_REG_BIT (used, j));
1032 #ifndef REG_ALLOC_ORDER
1033 i = j; /* Skip starting points we know will lose */
1039 /* See if there is a preferred register with the same class as the register
1040 we allocated above. Making this restriction prevents register
1041 preferencing from creating worse register allocation.
1043 Remove from the preferred registers and conflicting registers. Note that
1044 additional conflicts may have been added after `prune_preferences' was
1047 First do this for those register with copy preferences, then all
1048 preferred registers. */
1050 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[allocno], used);
1051 GO_IF_HARD_REG_SUBSET (hard_reg_copy_preferences[allocno],
1052 reg_class_contents[(int) NO_REGS], no_copy_prefs);
1056 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1057 if (TEST_HARD_REG_BIT (hard_reg_copy_preferences[allocno], i)
1058 && HARD_REGNO_MODE_OK (i, mode)
1059 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1060 || reg_class_subset_p (REGNO_REG_CLASS (i),
1061 REGNO_REG_CLASS (best_reg))
1062 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1063 REGNO_REG_CLASS (i))))
1066 register int lim = i + HARD_REGNO_NREGS (i, mode);
1069 && ! TEST_HARD_REG_BIT (used, j)
1070 && (REGNO_REG_CLASS (j)
1071 == REGNO_REG_CLASS (best_reg + (j - i))
1072 || reg_class_subset_p (REGNO_REG_CLASS (j),
1073 REGNO_REG_CLASS (best_reg + (j - i)))
1074 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1075 REGNO_REG_CLASS (j))));
1086 AND_COMPL_HARD_REG_SET (hard_reg_preferences[allocno], used);
1087 GO_IF_HARD_REG_SUBSET (hard_reg_preferences[allocno],
1088 reg_class_contents[(int) NO_REGS], no_prefs);
1092 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1093 if (TEST_HARD_REG_BIT (hard_reg_preferences[allocno], i)
1094 && HARD_REGNO_MODE_OK (i, mode)
1095 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1096 || reg_class_subset_p (REGNO_REG_CLASS (i),
1097 REGNO_REG_CLASS (best_reg))
1098 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1099 REGNO_REG_CLASS (i))))
1102 register int lim = i + HARD_REGNO_NREGS (i, mode);
1105 && ! TEST_HARD_REG_BIT (used, j)
1106 && (REGNO_REG_CLASS (j)
1107 == REGNO_REG_CLASS (best_reg + (j - i))
1108 || reg_class_subset_p (REGNO_REG_CLASS (j),
1109 REGNO_REG_CLASS (best_reg + (j - i)))
1110 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1111 REGNO_REG_CLASS (j))));
1122 /* If we haven't succeeded yet, try with caller-saves.
1123 We need not check to see if the current function has nonlocal
1124 labels because we don't put any pseudos that are live over calls in
1125 registers in that case. */
1127 if (flag_caller_saves && best_reg < 0)
1129 /* Did not find a register. If it would be profitable to
1130 allocate a call-clobbered register and save and restore it
1131 around calls, do that. */
1132 if (! accept_call_clobbered
1133 && allocno_calls_crossed[allocno] != 0
1134 && CALLER_SAVE_PROFITABLE (allocno_n_refs[allocno],
1135 allocno_calls_crossed[allocno]))
1137 HARD_REG_SET new_losers;
1139 CLEAR_HARD_REG_SET (new_losers);
1141 COPY_HARD_REG_SET (new_losers, losers);
1143 IOR_HARD_REG_SET(new_losers, losing_caller_save_reg_set);
1144 find_reg (allocno, new_losers, alt_regs_p, 1, retrying);
1145 if (reg_renumber[allocno_reg[allocno]] >= 0)
1147 caller_save_needed = 1;
1153 /* If we haven't succeeded yet,
1154 see if some hard reg that conflicts with us
1155 was utilized poorly by local-alloc.
1156 If so, kick out the regs that were put there by local-alloc
1157 so we can use it instead. */
1158 if (best_reg < 0 && !retrying
1159 /* Let's not bother with multi-reg allocnos. */
1160 && allocno_size[allocno] == 1)
1162 /* Count from the end, to find the least-used ones first. */
1163 for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1165 #ifdef REG_ALLOC_ORDER
1166 int regno = reg_alloc_order[i];
1171 if (local_reg_n_refs[regno] != 0
1172 /* Don't use a reg no good for this pseudo. */
1173 && ! TEST_HARD_REG_BIT (used2, regno)
1174 && HARD_REGNO_MODE_OK (regno, mode)
1175 #ifdef CLASS_CANNOT_CHANGE_SIZE
1176 && ! (REG_CHANGES_SIZE (allocno_reg[allocno])
1177 && (TEST_HARD_REG_BIT
1178 (reg_class_contents[(int) CLASS_CANNOT_CHANGE_SIZE],
1183 /* We explicitly evaluate the divide results into temporary
1184 variables so as to avoid excess precision problems that occur
1185 on a i386-unknown-sysv4.2 (unixware) host. */
1187 double tmp1 = ((double) local_reg_n_refs[regno]
1188 / local_reg_live_length[regno]);
1189 double tmp2 = ((double) allocno_n_refs[allocno]
1190 / allocno_live_length[allocno]);
1194 /* Hard reg REGNO was used less in total by local regs
1195 than it would be used by this one allocno! */
1197 for (k = 0; k < max_regno; k++)
1198 if (reg_renumber[k] >= 0)
1200 int r = reg_renumber[k];
1202 = r + HARD_REGNO_NREGS (r, PSEUDO_REGNO_MODE (k));
1204 if (regno >= r && regno < endregno)
1205 reg_renumber[k] = -1;
1215 /* Did we find a register? */
1219 register int lim, j;
1220 HARD_REG_SET this_reg;
1222 /* Yes. Record it as the hard register of this pseudo-reg. */
1223 reg_renumber[allocno_reg[allocno]] = best_reg;
1224 /* Also of any pseudo-regs that share with it. */
1225 if (reg_may_share[allocno_reg[allocno]])
1226 for (j = FIRST_PSEUDO_REGISTER; j < max_regno; j++)
1227 if (reg_allocno[j] == allocno)
1228 reg_renumber[j] = best_reg;
1230 /* Make a set of the hard regs being allocated. */
1231 CLEAR_HARD_REG_SET (this_reg);
1232 lim = best_reg + HARD_REGNO_NREGS (best_reg, mode);
1233 for (j = best_reg; j < lim; j++)
1235 SET_HARD_REG_BIT (this_reg, j);
1236 SET_HARD_REG_BIT (regs_used_so_far, j);
1237 /* This is no longer a reg used just by local regs. */
1238 local_reg_n_refs[j] = 0;
1240 /* For each other pseudo-reg conflicting with this one,
1241 mark it as conflicting with the hard regs this one occupies. */
1243 for (j = 0; j < max_allocno; j++)
1244 if (CONFLICTP (j, lim))
1246 IOR_HARD_REG_SET (hard_reg_conflicts[j], this_reg);
1251 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1252 Perhaps it had previously seemed not worth a hard reg,
1253 or perhaps its old hard reg has been commandeered for reloads.
1254 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1255 they do not appear to be allocated.
1256 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1259 retry_global_alloc (regno, forbidden_regs)
1261 HARD_REG_SET forbidden_regs;
1263 int allocno = reg_allocno[regno];
1266 /* If we have more than one register class,
1267 first try allocating in the class that is cheapest
1268 for this pseudo-reg. If that fails, try any reg. */
1269 if (N_REG_CLASSES > 1)
1270 find_reg (allocno, forbidden_regs, 0, 0, 1);
1271 if (reg_renumber[regno] < 0
1272 && reg_alternate_class (regno) != NO_REGS)
1273 find_reg (allocno, forbidden_regs, 1, 0, 1);
1275 /* If we found a register, modify the RTL for the register to
1276 show the hard register, and mark that register live. */
1277 if (reg_renumber[regno] >= 0)
1279 REGNO (regno_reg_rtx[regno]) = reg_renumber[regno];
1280 mark_home_live (regno);
1285 /* Record a conflict between register REGNO
1286 and everything currently live.
1287 REGNO must not be a pseudo reg that was allocated
1288 by local_alloc; such numbers must be translated through
1289 reg_renumber before calling here. */
1292 record_one_conflict (regno)
1297 if (regno < FIRST_PSEUDO_REGISTER)
1298 /* When a hard register becomes live,
1299 record conflicts with live pseudo regs. */
1300 for (j = 0; j < max_allocno; j++)
1302 if (ALLOCNO_LIVE_P (j))
1303 SET_HARD_REG_BIT (hard_reg_conflicts[j], regno);
1306 /* When a pseudo-register becomes live,
1307 record conflicts first with hard regs,
1308 then with other pseudo regs. */
1310 register int ialloc = reg_allocno[regno];
1311 register int ialloc_prod = ialloc * allocno_row_words;
1312 IOR_HARD_REG_SET (hard_reg_conflicts[ialloc], hard_regs_live);
1313 for (j = allocno_row_words - 1; j >= 0; j--)
1317 for (k = 0; k < n_no_conflict_pairs; k++)
1318 if (! ((j == no_conflict_pairs[k].allocno1
1319 && ialloc == no_conflict_pairs[k].allocno2)
1321 (j == no_conflict_pairs[k].allocno2
1322 && ialloc == no_conflict_pairs[k].allocno1)))
1324 conflicts[ialloc_prod + j] |= allocnos_live[j];
1329 /* Record all allocnos currently live as conflicting
1330 with each other and with all hard regs currently live.
1331 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1332 are currently live. Their bits are also flagged in allocnos_live. */
1335 record_conflicts (allocno_vec, len)
1336 register int *allocno_vec;
1339 register int allocno;
1341 register int ialloc_prod;
1345 allocno = allocno_vec[len];
1346 ialloc_prod = allocno * allocno_row_words;
1347 IOR_HARD_REG_SET (hard_reg_conflicts[allocno], hard_regs_live);
1348 for (j = allocno_row_words - 1; j >= 0; j--)
1349 conflicts[ialloc_prod + j] |= allocnos_live[j];
1353 /* If CONFLICTP (i, j) is true, make sure CONFLICTP (j, i) is also true. */
1358 int rw = allocno_row_words;
1359 int rwb = rw * INT_BITS;
1360 INT_TYPE *p = conflicts;
1361 INT_TYPE *q0 = conflicts, *q1, *q2;
1362 unsigned INT_TYPE mask;
1364 for (i = max_allocno - 1, mask = 1; i >= 0; i--, mask <<= 1)
1371 for (j = allocno_row_words - 1, q1 = q0; j >= 0; j--, q1 += rwb)
1373 unsigned INT_TYPE word;
1375 for (word = (unsigned INT_TYPE) *p++, q2 = q1; word;
1376 word >>= 1, q2 += rw)
1385 /* Handle the case where REG is set by the insn being scanned,
1386 during the forward scan to accumulate conflicts.
1387 Store a 1 in regs_live or allocnos_live for this register, record how many
1388 consecutive hardware registers it actually needs,
1389 and record a conflict with all other registers already live.
1391 Note that even if REG does not remain alive after this insn,
1392 we must mark it here as live, to ensure a conflict between
1393 REG and any other regs set in this insn that really do live.
1394 This is because those other regs could be considered after this.
1396 REG might actually be something other than a register;
1397 if so, we do nothing.
1399 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1400 a REG_INC note was found for it). */
1403 mark_reg_store (reg, setter, data)
1405 void *data ATTRIBUTE_UNUSED;
1409 /* WORD is which word of a multi-register group is being stored.
1410 For the case where the store is actually into a SUBREG of REG.
1411 Except we don't use it; I believe the entire REG needs to be
1415 if (GET_CODE (reg) == SUBREG)
1417 word = SUBREG_WORD (reg);
1418 reg = SUBREG_REG (reg);
1421 if (GET_CODE (reg) != REG)
1424 regs_set[n_regs_set++] = reg;
1426 if (setter && GET_CODE (setter) != CLOBBER)
1427 set_preference (reg, SET_SRC (setter));
1429 regno = REGNO (reg);
1431 /* Either this is one of the max_allocno pseudo regs not allocated,
1432 or it is or has a hardware reg. First handle the pseudo-regs. */
1433 if (regno >= FIRST_PSEUDO_REGISTER)
1435 if (reg_allocno[regno] >= 0)
1437 SET_ALLOCNO_LIVE (reg_allocno[regno]);
1438 record_one_conflict (regno);
1442 if (reg_renumber[regno] >= 0)
1443 regno = reg_renumber[regno] /* + word */;
1445 /* Handle hardware regs (and pseudos allocated to hard regs). */
1446 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1448 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1449 while (regno < last)
1451 record_one_conflict (regno);
1452 SET_HARD_REG_BIT (hard_regs_live, regno);
1458 /* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
1461 mark_reg_clobber (reg, setter, data)
1463 void *data ATTRIBUTE_UNUSED;
1465 if (GET_CODE (setter) == CLOBBER)
1466 mark_reg_store (reg, setter, data);
1469 /* Record that REG has conflicts with all the regs currently live.
1470 Do not mark REG itself as live. */
1473 mark_reg_conflicts (reg)
1478 if (GET_CODE (reg) == SUBREG)
1479 reg = SUBREG_REG (reg);
1481 if (GET_CODE (reg) != REG)
1484 regno = REGNO (reg);
1486 /* Either this is one of the max_allocno pseudo regs not allocated,
1487 or it is or has a hardware reg. First handle the pseudo-regs. */
1488 if (regno >= FIRST_PSEUDO_REGISTER)
1490 if (reg_allocno[regno] >= 0)
1491 record_one_conflict (regno);
1494 if (reg_renumber[regno] >= 0)
1495 regno = reg_renumber[regno];
1497 /* Handle hardware regs (and pseudos allocated to hard regs). */
1498 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1500 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1501 while (regno < last)
1503 record_one_conflict (regno);
1509 /* Mark REG as being dead (following the insn being scanned now).
1510 Store a 0 in regs_live or allocnos_live for this register. */
1513 mark_reg_death (reg)
1516 register int regno = REGNO (reg);
1518 /* Either this is one of the max_allocno pseudo regs not allocated,
1519 or it is a hardware reg. First handle the pseudo-regs. */
1520 if (regno >= FIRST_PSEUDO_REGISTER)
1522 if (reg_allocno[regno] >= 0)
1523 CLEAR_ALLOCNO_LIVE (reg_allocno[regno]);
1526 /* For pseudo reg, see if it has been assigned a hardware reg. */
1527 if (reg_renumber[regno] >= 0)
1528 regno = reg_renumber[regno];
1530 /* Handle hardware regs (and pseudos allocated to hard regs). */
1531 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1533 /* Pseudo regs already assigned hardware regs are treated
1534 almost the same as explicit hardware regs. */
1535 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1536 while (regno < last)
1538 CLEAR_HARD_REG_BIT (hard_regs_live, regno);
1544 /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1545 for the value stored in it. MODE determines how many consecutive
1546 registers are actually in use. Do not record conflicts;
1547 it is assumed that the caller will do that. */
1550 mark_reg_live_nc (regno, mode)
1552 enum machine_mode mode;
1554 register int last = regno + HARD_REGNO_NREGS (regno, mode);
1555 while (regno < last)
1557 SET_HARD_REG_BIT (hard_regs_live, regno);
1562 /* Try to set a preference for an allocno to a hard register.
1563 We are passed DEST and SRC which are the operands of a SET. It is known
1564 that SRC is a register. If SRC or the first operand of SRC is a register,
1565 try to set a preference. If one of the two is a hard register and the other
1566 is a pseudo-register, mark the preference.
1568 Note that we are not as aggressive as local-alloc in trying to tie a
1569 pseudo-register to a hard register. */
1572 set_preference (dest, src)
1575 int src_regno, dest_regno;
1576 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1577 to compensate for subregs in SRC or DEST. */
1582 if (GET_RTX_FORMAT (GET_CODE (src))[0] == 'e')
1583 src = XEXP (src, 0), copy = 0;
1585 /* Get the reg number for both SRC and DEST.
1586 If neither is a reg, give up. */
1588 if (GET_CODE (src) == REG)
1589 src_regno = REGNO (src);
1590 else if (GET_CODE (src) == SUBREG && GET_CODE (SUBREG_REG (src)) == REG)
1592 src_regno = REGNO (SUBREG_REG (src));
1593 offset += SUBREG_WORD (src);
1598 if (GET_CODE (dest) == REG)
1599 dest_regno = REGNO (dest);
1600 else if (GET_CODE (dest) == SUBREG && GET_CODE (SUBREG_REG (dest)) == REG)
1602 dest_regno = REGNO (SUBREG_REG (dest));
1603 offset -= SUBREG_WORD (dest);
1608 /* Convert either or both to hard reg numbers. */
1610 if (reg_renumber[src_regno] >= 0)
1611 src_regno = reg_renumber[src_regno];
1613 if (reg_renumber[dest_regno] >= 0)
1614 dest_regno = reg_renumber[dest_regno];
1616 /* Now if one is a hard reg and the other is a global pseudo
1617 then give the other a preference. */
1619 if (dest_regno < FIRST_PSEUDO_REGISTER && src_regno >= FIRST_PSEUDO_REGISTER
1620 && reg_allocno[src_regno] >= 0)
1622 dest_regno -= offset;
1623 if (dest_regno >= 0 && dest_regno < FIRST_PSEUDO_REGISTER)
1626 SET_REGBIT (hard_reg_copy_preferences,
1627 reg_allocno[src_regno], dest_regno);
1629 SET_REGBIT (hard_reg_preferences,
1630 reg_allocno[src_regno], dest_regno);
1631 for (i = dest_regno;
1632 i < dest_regno + HARD_REGNO_NREGS (dest_regno, GET_MODE (dest));
1634 SET_REGBIT (hard_reg_full_preferences, reg_allocno[src_regno], i);
1638 if (src_regno < FIRST_PSEUDO_REGISTER && dest_regno >= FIRST_PSEUDO_REGISTER
1639 && reg_allocno[dest_regno] >= 0)
1641 src_regno += offset;
1642 if (src_regno >= 0 && src_regno < FIRST_PSEUDO_REGISTER)
1645 SET_REGBIT (hard_reg_copy_preferences,
1646 reg_allocno[dest_regno], src_regno);
1648 SET_REGBIT (hard_reg_preferences,
1649 reg_allocno[dest_regno], src_regno);
1651 i < src_regno + HARD_REGNO_NREGS (src_regno, GET_MODE (src));
1653 SET_REGBIT (hard_reg_full_preferences, reg_allocno[dest_regno], i);
1658 /* Indicate that hard register number FROM was eliminated and replaced with
1659 an offset from hard register number TO. The status of hard registers live
1660 at the start of a basic block is updated by replacing a use of FROM with
1664 mark_elimination (from, to)
1669 for (i = 0; i < n_basic_blocks; i++)
1671 register regset r = BASIC_BLOCK (i)->global_live_at_start;
1672 if (REGNO_REG_SET_P (r, from))
1674 CLEAR_REGNO_REG_SET (r, from);
1675 SET_REGNO_REG_SET (r, to);
1680 /* Used for communication between the following functions. Holds the
1681 current life information. */
1682 static regset live_relevant_regs;
1684 /* Record in live_relevant_regs that register REG became live. This
1685 is called via note_stores. */
1687 reg_becomes_live (reg, setter, data)
1689 rtx setter ATTRIBUTE_UNUSED;
1690 void *data ATTRIBUTE_UNUSED;
1694 if (GET_CODE (reg) == SUBREG)
1695 reg = SUBREG_REG (reg);
1697 if (GET_CODE (reg) != REG)
1700 regno = REGNO (reg);
1701 if (regno < FIRST_PSEUDO_REGISTER)
1703 int nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg));
1705 SET_REGNO_REG_SET (live_relevant_regs, regno++);
1707 else if (reg_renumber[regno] >= 0)
1708 SET_REGNO_REG_SET (live_relevant_regs, regno);
1711 /* Record in live_relevant_regs that register REGNO died. */
1713 reg_dies (regno, mode)
1715 enum machine_mode mode;
1717 if (regno < FIRST_PSEUDO_REGISTER)
1719 int nregs = HARD_REGNO_NREGS (regno, mode);
1721 CLEAR_REGNO_REG_SET (live_relevant_regs, regno++);
1724 CLEAR_REGNO_REG_SET (live_relevant_regs, regno);
1727 /* Walk the insns of the current function and build reload_insn_chain,
1728 and record register life information. */
1730 build_insn_chain (first)
1733 struct insn_chain **p = &reload_insn_chain;
1734 struct insn_chain *prev = 0;
1737 live_relevant_regs = ALLOCA_REG_SET ();
1739 for (; first; first = NEXT_INSN (first))
1741 struct insn_chain *c;
1743 if (first == BLOCK_HEAD (b))
1747 CLEAR_REG_SET (live_relevant_regs);
1749 EXECUTE_IF_SET_IN_BITMAP
1750 (BASIC_BLOCK (b)->global_live_at_start, 0, i,
1752 if (i < FIRST_PSEUDO_REGISTER
1753 ? ! TEST_HARD_REG_BIT (eliminable_regset, i)
1754 : reg_renumber[i] >= 0)
1755 SET_REGNO_REG_SET (live_relevant_regs, i);
1759 if (GET_CODE (first) != NOTE && GET_CODE (first) != BARRIER)
1761 c = new_insn_chain ();
1769 COPY_REG_SET (c->live_before, live_relevant_regs);
1771 if (GET_RTX_CLASS (GET_CODE (first)) == 'i')
1775 /* Mark the death of everything that dies in this instruction. */
1777 for (link = REG_NOTES (first); link; link = XEXP (link, 1))
1778 if (REG_NOTE_KIND (link) == REG_DEAD
1779 && GET_CODE (XEXP (link, 0)) == REG)
1780 reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)));
1782 /* Mark everything born in this instruction as live. */
1784 note_stores (PATTERN (first), reg_becomes_live, NULL);
1787 /* Remember which registers are live at the end of the insn, before
1788 killing those with REG_UNUSED notes. */
1789 COPY_REG_SET (c->live_after, live_relevant_regs);
1791 if (GET_RTX_CLASS (GET_CODE (first)) == 'i')
1795 /* Mark anything that is set in this insn and then unused as dying. */
1797 for (link = REG_NOTES (first); link; link = XEXP (link, 1))
1798 if (REG_NOTE_KIND (link) == REG_UNUSED
1799 && GET_CODE (XEXP (link, 0)) == REG)
1800 reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)));
1804 if (first == BLOCK_END (b))
1807 /* Stop after we pass the end of the last basic block. Verify that
1808 no real insns are after the end of the last basic block.
1810 We may want to reorganize the loop somewhat since this test should
1811 always be the right exit test. */
1812 if (b == n_basic_blocks)
1814 for (first = NEXT_INSN (first) ; first; first = NEXT_INSN (first))
1815 if (GET_RTX_CLASS (GET_CODE (first)) == 'i'
1816 && GET_CODE (PATTERN (first)) != USE)
1821 FREE_REG_SET (live_relevant_regs);
1825 /* Print debugging trace information if -dg switch is given,
1826 showing the information on which the allocation decisions are based. */
1829 dump_conflicts (file)
1833 register int has_preferences;
1836 for (i = 0; i < max_allocno; i++)
1838 if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
1842 fprintf (file, ";; %d regs to allocate:", nregs);
1843 for (i = 0; i < max_allocno; i++)
1846 if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
1848 fprintf (file, " %d", allocno_reg[allocno_order[i]]);
1849 for (j = 0; j < max_regno; j++)
1850 if (reg_allocno[j] == allocno_order[i]
1851 && j != allocno_reg[allocno_order[i]])
1852 fprintf (file, "+%d", j);
1853 if (allocno_size[allocno_order[i]] != 1)
1854 fprintf (file, " (%d)", allocno_size[allocno_order[i]]);
1856 fprintf (file, "\n");
1858 for (i = 0; i < max_allocno; i++)
1861 fprintf (file, ";; %d conflicts:", allocno_reg[i]);
1862 for (j = 0; j < max_allocno; j++)
1863 if (CONFLICTP (j, i))
1864 fprintf (file, " %d", allocno_reg[j]);
1865 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1866 if (TEST_HARD_REG_BIT (hard_reg_conflicts[i], j))
1867 fprintf (file, " %d", j);
1868 fprintf (file, "\n");
1870 has_preferences = 0;
1871 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1872 if (TEST_HARD_REG_BIT (hard_reg_preferences[i], j))
1873 has_preferences = 1;
1875 if (! has_preferences)
1877 fprintf (file, ";; %d preferences:", allocno_reg[i]);
1878 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1879 if (TEST_HARD_REG_BIT (hard_reg_preferences[i], j))
1880 fprintf (file, " %d", j);
1881 fprintf (file, "\n");
1883 fprintf (file, "\n");
1887 dump_global_regs (file)
1892 fprintf (file, ";; Register dispositions:\n");
1893 for (i = FIRST_PSEUDO_REGISTER, j = 0; i < max_regno; i++)
1894 if (reg_renumber[i] >= 0)
1896 fprintf (file, "%d in %d ", i, reg_renumber[i]);
1898 fprintf (file, "\n");
1901 fprintf (file, "\n\n;; Hard regs used: ");
1902 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1903 if (regs_ever_live[i])
1904 fprintf (file, " %d", i);
1905 fprintf (file, "\n\n");