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 not symmetric; a conflict between allocno's i and j
118 is recorded either in element i,j or in element j,i. */
120 static INT_TYPE *conflicts;
122 /* Number of ints require to hold max_allocno bits.
123 This is the length of a row in `conflicts'. */
125 static int allocno_row_words;
127 /* Two macros to test or store 1 in an element of `conflicts'. */
129 #define CONFLICTP(I, J) \
130 (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
131 & ((INT_TYPE) 1 << ((J) % INT_BITS)))
133 #define SET_CONFLICT(I, J) \
134 (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
135 |= ((INT_TYPE) 1 << ((J) % INT_BITS)))
137 /* Set of hard regs currently live (during scan of all insns). */
139 static HARD_REG_SET hard_regs_live;
141 /* Indexed by N, set of hard regs conflicting with allocno N. */
143 static HARD_REG_SET *hard_reg_conflicts;
145 /* Indexed by N, set of hard regs preferred by allocno N.
146 This is used to make allocnos go into regs that are copied to or from them,
147 when possible, to reduce register shuffling. */
149 static HARD_REG_SET *hard_reg_preferences;
151 /* Similar, but just counts register preferences made in simple copy
152 operations, rather than arithmetic. These are given priority because
153 we can always eliminate an insn by using these, but using a register
154 in the above list won't always eliminate an insn. */
156 static HARD_REG_SET *hard_reg_copy_preferences;
158 /* Similar to hard_reg_preferences, but includes bits for subsequent
159 registers when an allocno is multi-word. The above variable is used for
160 allocation while this is used to build reg_someone_prefers, below. */
162 static HARD_REG_SET *hard_reg_full_preferences;
164 /* Indexed by N, set of hard registers that some later allocno has a
167 static HARD_REG_SET *regs_someone_prefers;
169 /* Set of registers that global-alloc isn't supposed to use. */
171 static HARD_REG_SET no_global_alloc_regs;
173 /* Set of registers used so far. */
175 static HARD_REG_SET regs_used_so_far;
177 /* Number of calls crossed by each allocno. */
179 static int *allocno_calls_crossed;
181 /* Number of refs (weighted) to each allocno. */
183 static int *allocno_n_refs;
185 /* Guess at live length of each allocno.
186 This is actually the max of the live lengths of the regs. */
188 static int *allocno_live_length;
190 /* Number of refs (weighted) to each hard reg, as used by local alloc.
191 It is zero for a reg that contains global pseudos or is explicitly used. */
193 static int local_reg_n_refs[FIRST_PSEUDO_REGISTER];
195 /* Guess at live length of each hard reg, as used by local alloc.
196 This is actually the sum of the live lengths of the specific regs. */
198 static int local_reg_live_length[FIRST_PSEUDO_REGISTER];
200 /* Test a bit in TABLE, a vector of HARD_REG_SETs,
201 for vector element I, and hard register number J. */
203 #define REGBITP(TABLE, I, J) TEST_HARD_REG_BIT (TABLE[I], J)
205 /* Set to 1 a bit in a vector of HARD_REG_SETs. Works like REGBITP. */
207 #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (TABLE[I], J)
209 /* Bit mask for allocnos live at current point in the scan. */
211 static INT_TYPE *allocnos_live;
213 /* Test, set or clear bit number I in allocnos_live,
214 a bit vector indexed by allocno. */
216 #define ALLOCNO_LIVE_P(I) \
217 (allocnos_live[(I) / INT_BITS] & ((INT_TYPE) 1 << ((I) % INT_BITS)))
219 #define SET_ALLOCNO_LIVE(I) \
220 (allocnos_live[(I) / INT_BITS] |= ((INT_TYPE) 1 << ((I) % INT_BITS)))
222 #define CLEAR_ALLOCNO_LIVE(I) \
223 (allocnos_live[(I) / INT_BITS] &= ~((INT_TYPE) 1 << ((I) % INT_BITS)))
225 /* This is turned off because it doesn't work right for DImode.
226 (And it is only used for DImode, so the other cases are worthless.)
227 The problem is that it isn't true that there is NO possibility of conflict;
228 only that there is no conflict if the two pseudos get the exact same regs.
229 If they were allocated with a partial overlap, there would be a conflict.
230 We can't safely turn off the conflict unless we have another way to
231 prevent the partial overlap.
233 Idea: change hard_reg_conflicts so that instead of recording which
234 hard regs the allocno may not overlap, it records where the allocno
235 may not start. Change both where it is used and where it is updated.
236 Then there is a way to record that (reg:DI 108) may start at 10
237 but not at 9 or 11. There is still the question of how to record
238 this semi-conflict between two pseudos. */
240 /* Reg pairs for which conflict after the current insn
241 is inhibited by a REG_NO_CONFLICT note.
242 If the table gets full, we ignore any other notes--that is conservative. */
243 #define NUM_NO_CONFLICT_PAIRS 4
244 /* Number of pairs in use in this insn. */
245 int n_no_conflict_pairs;
246 static struct { int allocno1, allocno2;}
247 no_conflict_pairs[NUM_NO_CONFLICT_PAIRS];
250 /* Record all regs that are set in any one insn.
251 Communication from mark_reg_{store,clobber} and global_conflicts. */
253 static rtx *regs_set;
254 static int n_regs_set;
256 /* All registers that can be eliminated. */
258 static HARD_REG_SET eliminable_regset;
260 static int allocno_compare PROTO((const PTR, const PTR));
261 static void global_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));
268 static void mark_reg_clobber PROTO((rtx, rtx));
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));
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 *) alloca (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 *) alloca (max_regno * sizeof (int));
383 bzero ((char *) reg_may_share, max_regno * sizeof (int));
384 for (x = regs_may_share; x; x = XEXP (XEXP (x, 1), 1))
386 int r1 = REGNO (XEXP (x, 0));
387 int r2 = REGNO (XEXP (XEXP (x, 1), 0));
389 reg_may_share[r1] = r2;
391 reg_may_share[r2] = r1;
394 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
395 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
396 that we are supposed to refrain from putting in a hard reg.
397 -2 means do make an allocno but don't allocate it. */
398 if (REG_N_REFS (i) != 0 && REG_LIVE_LENGTH (i) != -1
399 /* Don't allocate pseudos that cross calls,
400 if this function receives a nonlocal goto. */
401 && (! current_function_has_nonlocal_label
402 || REG_N_CALLS_CROSSED (i) == 0))
404 if (reg_renumber[i] < 0 && reg_may_share[i] && reg_allocno[reg_may_share[i]] >= 0)
405 reg_allocno[i] = reg_allocno[reg_may_share[i]];
407 reg_allocno[i] = max_allocno++;
408 if (REG_LIVE_LENGTH (i) == 0)
414 allocno_reg = (int *) alloca (max_allocno * sizeof (int));
415 allocno_size = (int *) alloca (max_allocno * sizeof (int));
416 allocno_calls_crossed = (int *) alloca (max_allocno * sizeof (int));
417 allocno_n_refs = (int *) alloca (max_allocno * sizeof (int));
418 allocno_live_length = (int *) alloca (max_allocno * sizeof (int));
419 bzero ((char *) allocno_size, max_allocno * sizeof (int));
420 bzero ((char *) allocno_calls_crossed, max_allocno * sizeof (int));
421 bzero ((char *) allocno_n_refs, max_allocno * sizeof (int));
422 bzero ((char *) allocno_live_length, max_allocno * sizeof (int));
424 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
425 if (reg_allocno[i] >= 0)
427 int allocno = reg_allocno[i];
428 allocno_reg[allocno] = i;
429 allocno_size[allocno] = PSEUDO_REGNO_SIZE (i);
430 allocno_calls_crossed[allocno] += REG_N_CALLS_CROSSED (i);
431 allocno_n_refs[allocno] += REG_N_REFS (i);
432 if (allocno_live_length[allocno] < REG_LIVE_LENGTH (i))
433 allocno_live_length[allocno] = REG_LIVE_LENGTH (i);
436 /* Calculate amount of usage of each hard reg by pseudos
437 allocated by local-alloc. This is to see if we want to
439 bzero ((char *) local_reg_live_length, sizeof local_reg_live_length);
440 bzero ((char *) local_reg_n_refs, sizeof local_reg_n_refs);
441 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
442 if (reg_renumber[i] >= 0)
444 int regno = reg_renumber[i];
445 int endregno = regno + HARD_REGNO_NREGS (regno, PSEUDO_REGNO_MODE (i));
448 for (j = regno; j < endregno; j++)
450 local_reg_n_refs[j] += REG_N_REFS (i);
451 local_reg_live_length[j] += REG_LIVE_LENGTH (i);
455 /* We can't override local-alloc for a reg used not just by local-alloc. */
456 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
457 if (regs_ever_live[i])
458 local_reg_n_refs[i] = 0;
460 /* Allocate the space for the conflict and preference tables and
464 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
465 bzero ((char *) hard_reg_conflicts, max_allocno * sizeof (HARD_REG_SET));
468 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
469 bzero ((char *) hard_reg_preferences, max_allocno * sizeof (HARD_REG_SET));
471 hard_reg_copy_preferences
472 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
473 bzero ((char *) hard_reg_copy_preferences,
474 max_allocno * sizeof (HARD_REG_SET));
476 hard_reg_full_preferences
477 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
478 bzero ((char *) hard_reg_full_preferences,
479 max_allocno * sizeof (HARD_REG_SET));
482 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
483 bzero ((char *) regs_someone_prefers, max_allocno * sizeof (HARD_REG_SET));
485 allocno_row_words = (max_allocno + INT_BITS - 1) / INT_BITS;
487 /* We used to use alloca here, but the size of what it would try to
488 allocate would occasionally cause it to exceed the stack limit and
489 cause unpredictable core dumps. Some examples were > 2Mb in size. */
490 conflicts = (INT_TYPE *) xcalloc (max_allocno * allocno_row_words,
493 allocnos_live = (INT_TYPE *) alloca (allocno_row_words * sizeof (INT_TYPE));
495 /* If there is work to be done (at least one reg to allocate),
496 perform global conflict analysis and allocate the regs. */
500 /* Scan all the insns and compute the conflicts among allocnos
501 and between allocnos and hard regs. */
505 /* Eliminate conflicts between pseudos and eliminable registers. If
506 the register is not eliminated, the pseudo won't really be able to
507 live in the eliminable register, so the conflict doesn't matter.
508 If we do eliminate the register, the conflict will no longer exist.
509 So in either case, we can ignore the conflict. Likewise for
512 for (i = 0; i < (size_t) max_allocno; i++)
514 AND_COMPL_HARD_REG_SET (hard_reg_conflicts[i], eliminable_regset);
515 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[i],
517 AND_COMPL_HARD_REG_SET (hard_reg_preferences[i], eliminable_regset);
520 /* Try to expand the preferences by merging them between allocnos. */
522 expand_preferences ();
524 /* Determine the order to allocate the remaining pseudo registers. */
526 allocno_order = (int *) alloca (max_allocno * sizeof (int));
527 for (i = 0; i < (size_t) max_allocno; i++)
528 allocno_order[i] = i;
530 /* Default the size to 1, since allocno_compare uses it to divide by.
531 Also convert allocno_live_length of zero to -1. A length of zero
532 can occur when all the registers for that allocno have reg_live_length
533 equal to -2. In this case, we want to make an allocno, but not
534 allocate it. So avoid the divide-by-zero and set it to a low
537 for (i = 0; i < (size_t) max_allocno; i++)
539 if (allocno_size[i] == 0)
541 if (allocno_live_length[i] == 0)
542 allocno_live_length[i] = -1;
545 qsort (allocno_order, max_allocno, sizeof (int), allocno_compare);
547 prune_preferences ();
550 dump_conflicts (file);
552 /* Try allocating them, one by one, in that order,
553 except for parameters marked with reg_live_length[regno] == -2. */
555 for (i = 0; i < (size_t) max_allocno; i++)
556 if (reg_renumber[allocno_reg[allocno_order[i]]] < 0
557 && REG_LIVE_LENGTH (allocno_reg[allocno_order[i]]) >= 0)
559 /* If we have more than one register class,
560 first try allocating in the class that is cheapest
561 for this pseudo-reg. If that fails, try any reg. */
562 if (N_REG_CLASSES > 1)
564 find_reg (allocno_order[i], 0, 0, 0, 0);
565 if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
568 if (reg_alternate_class (allocno_reg[allocno_order[i]]) != NO_REGS)
569 find_reg (allocno_order[i], 0, 1, 0, 0);
573 /* Do the reloads now while the allocno data still exist, so that we can
574 try to assign new hard regs to any pseudo regs that are spilled. */
576 #if 0 /* We need to eliminate regs even if there is no rtl code,
577 for the sake of debugging information. */
578 if (n_basic_blocks > 0)
581 build_insn_chain (get_insns ());
582 retval = reload (get_insns (), 1, file);
589 /* Sort predicate for ordering the allocnos.
590 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
593 allocno_compare (v1p, v2p)
597 int v1 = *(int *)v1p, v2 = *(int *)v2p;
598 /* Note that the quotient will never be bigger than
599 the value of floor_log2 times the maximum number of
600 times a register can occur in one insn (surely less than 100).
601 Multiplying this by 10000 can't overflow. */
603 = (((double) (floor_log2 (allocno_n_refs[v1]) * allocno_n_refs[v1])
604 / allocno_live_length[v1])
605 * 10000 * allocno_size[v1]);
607 = (((double) (floor_log2 (allocno_n_refs[v2]) * allocno_n_refs[v2])
608 / allocno_live_length[v2])
609 * 10000 * allocno_size[v2]);
613 /* If regs are equally good, sort by allocno,
614 so that the results of qsort leave nothing to chance. */
618 /* Scan the rtl code and record all conflicts and register preferences in the
619 conflict matrices and preference tables. */
626 int *block_start_allocnos;
628 /* Make a vector that mark_reg_{store,clobber} will store in. */
629 regs_set = (rtx *) alloca (max_parallel * sizeof (rtx) * 2);
631 block_start_allocnos = (int *) alloca (max_allocno * sizeof (int));
633 for (b = 0; b < n_basic_blocks; b++)
635 bzero ((char *) allocnos_live, allocno_row_words * sizeof (INT_TYPE));
637 /* Initialize table of registers currently live
638 to the state at the beginning of this basic block.
639 This also marks the conflicts among them.
641 For pseudo-regs, there is only one bit for each one
642 no matter how many hard regs it occupies.
643 This is ok; we know the size from PSEUDO_REGNO_SIZE.
644 For explicit hard regs, we cannot know the size that way
645 since one hard reg can be used with various sizes.
646 Therefore, we must require that all the hard regs
647 implicitly live as part of a multi-word hard reg
648 are explicitly marked in basic_block_live_at_start. */
651 register regset old = BASIC_BLOCK (b)->global_live_at_start;
654 REG_SET_TO_HARD_REG_SET (hard_regs_live, old);
655 EXECUTE_IF_SET_IN_REG_SET (old, FIRST_PSEUDO_REGISTER, i,
657 register int a = reg_allocno[i];
660 SET_ALLOCNO_LIVE (a);
661 block_start_allocnos[ax++] = a;
663 else if ((a = reg_renumber[i]) >= 0)
665 (a, PSEUDO_REGNO_MODE (i));
668 /* Record that each allocno now live conflicts with each other
669 allocno now live, and with each hard reg now live. */
671 record_conflicts (block_start_allocnos, ax);
675 /* Pseudos can't go in stack regs at the start of a basic block
676 that can be reached through a computed goto, since reg-stack
677 can't handle computed gotos. */
678 /* ??? Seems more likely that reg-stack can't handle any abnormal
679 edges, critical or not, computed goto or otherwise. */
682 for (e = BASIC_BLOCK (b)->pred; e ; e = e->pred_next)
683 if (e->flags & EDGE_ABNORMAL)
687 for (ax = FIRST_STACK_REG; ax <= LAST_STACK_REG; ax++)
688 record_one_conflict (ax);
693 insn = BLOCK_HEAD (b);
695 /* Scan the code of this basic block, noting which allocnos
696 and hard regs are born or die. When one is born,
697 record a conflict with all others currently live. */
701 register RTX_CODE code = GET_CODE (insn);
704 /* Make regs_set an empty set. */
708 if (code == INSN || code == CALL_INSN || code == JUMP_INSN)
713 for (link = REG_NOTES (insn);
714 link && i < NUM_NO_CONFLICT_PAIRS;
715 link = XEXP (link, 1))
716 if (REG_NOTE_KIND (link) == REG_NO_CONFLICT)
718 no_conflict_pairs[i].allocno1
719 = reg_allocno[REGNO (SET_DEST (PATTERN (insn)))];
720 no_conflict_pairs[i].allocno2
721 = reg_allocno[REGNO (XEXP (link, 0))];
726 /* Mark any registers clobbered by INSN as live,
727 so they conflict with the inputs. */
729 note_stores (PATTERN (insn), mark_reg_clobber);
731 /* Mark any registers dead after INSN as dead now. */
733 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
734 if (REG_NOTE_KIND (link) == REG_DEAD)
735 mark_reg_death (XEXP (link, 0));
737 /* Mark any registers set in INSN as live,
738 and mark them as conflicting with all other live regs.
739 Clobbers are processed again, so they conflict with
740 the registers that are set. */
742 note_stores (PATTERN (insn), mark_reg_store);
745 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
746 if (REG_NOTE_KIND (link) == REG_INC)
747 mark_reg_store (XEXP (link, 0), NULL_RTX);
750 /* If INSN has multiple outputs, then any reg that dies here
751 and is used inside of an output
752 must conflict with the other outputs.
754 It is unsafe to use !single_set here since it will ignore an
755 unused output. Just because an output is unused does not mean
756 the compiler can assume the side effect will not occur.
757 Consider if REG appears in the address of an output and we
758 reload the output. If we allocate REG to the same hard
759 register as an unused output we could set the hard register
760 before the output reload insn. */
761 if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn))
762 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
763 if (REG_NOTE_KIND (link) == REG_DEAD)
765 int used_in_output = 0;
767 rtx reg = XEXP (link, 0);
769 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
771 rtx set = XVECEXP (PATTERN (insn), 0, i);
772 if (GET_CODE (set) == SET
773 && GET_CODE (SET_DEST (set)) != REG
774 && !rtx_equal_p (reg, SET_DEST (set))
775 && reg_overlap_mentioned_p (reg, SET_DEST (set)))
779 mark_reg_conflicts (reg);
782 /* Mark any registers set in INSN and then never used. */
784 while (n_regs_set > 0)
785 if (find_regno_note (insn, REG_UNUSED,
786 REGNO (regs_set[--n_regs_set])))
787 mark_reg_death (regs_set[n_regs_set]);
790 if (insn == BLOCK_END (b))
792 insn = NEXT_INSN (insn);
796 /* Expand the preference information by looking for cases where one allocno
797 dies in an insn that sets an allocno. If those two allocnos don't conflict,
798 merge any preferences between those allocnos. */
801 expand_preferences ()
807 /* We only try to handle the most common cases here. Most of the cases
808 where this wins are reg-reg copies. */
810 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
811 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
812 && (set = single_set (insn)) != 0
813 && GET_CODE (SET_DEST (set)) == REG
814 && reg_allocno[REGNO (SET_DEST (set))] >= 0)
815 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
816 if (REG_NOTE_KIND (link) == REG_DEAD
817 && GET_CODE (XEXP (link, 0)) == REG
818 && reg_allocno[REGNO (XEXP (link, 0))] >= 0
819 && ! CONFLICTP (reg_allocno[REGNO (SET_DEST (set))],
820 reg_allocno[REGNO (XEXP (link, 0))])
821 && ! CONFLICTP (reg_allocno[REGNO (XEXP (link, 0))],
822 reg_allocno[REGNO (SET_DEST (set))]))
824 int a1 = reg_allocno[REGNO (SET_DEST (set))];
825 int a2 = reg_allocno[REGNO (XEXP (link, 0))];
827 if (XEXP (link, 0) == SET_SRC (set))
829 IOR_HARD_REG_SET (hard_reg_copy_preferences[a1],
830 hard_reg_copy_preferences[a2]);
831 IOR_HARD_REG_SET (hard_reg_copy_preferences[a2],
832 hard_reg_copy_preferences[a1]);
835 IOR_HARD_REG_SET (hard_reg_preferences[a1],
836 hard_reg_preferences[a2]);
837 IOR_HARD_REG_SET (hard_reg_preferences[a2],
838 hard_reg_preferences[a1]);
839 IOR_HARD_REG_SET (hard_reg_full_preferences[a1],
840 hard_reg_full_preferences[a2]);
841 IOR_HARD_REG_SET (hard_reg_full_preferences[a2],
842 hard_reg_full_preferences[a1]);
846 /* Prune the preferences for global registers to exclude registers that cannot
849 Compute `regs_someone_prefers', which is a bitmask of the hard registers
850 that are preferred by conflicting registers of lower priority. If possible,
851 we will avoid using these registers. */
859 /* Scan least most important to most important.
860 For each allocno, remove from preferences registers that cannot be used,
861 either because of conflicts or register type. Then compute all registers
862 preferred by each lower-priority register that conflicts. */
864 for (i = max_allocno - 1; i >= 0; i--)
866 HARD_REG_SET temp, temp2;
868 allocno = allocno_order[i];
869 COPY_HARD_REG_SET (temp, hard_reg_conflicts[allocno]);
871 if (allocno_calls_crossed[allocno] == 0)
872 IOR_HARD_REG_SET (temp, fixed_reg_set);
874 IOR_HARD_REG_SET (temp, call_used_reg_set);
876 IOR_COMPL_HARD_REG_SET
878 reg_class_contents[(int) reg_preferred_class (allocno_reg[allocno])]);
880 AND_COMPL_HARD_REG_SET (hard_reg_preferences[allocno], temp);
881 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[allocno], temp);
882 AND_COMPL_HARD_REG_SET (hard_reg_full_preferences[allocno], temp);
884 /* Merge in the preferences of lower-priority registers (they have
885 already been pruned). If we also prefer some of those registers,
886 don't exclude them unless we are of a smaller size (in which case
887 we want to give the lower-priority allocno the first chance for
889 CLEAR_HARD_REG_SET (temp);
890 CLEAR_HARD_REG_SET (temp2);
891 for (j = i + 1; j < max_allocno; j++)
892 if (CONFLICTP (allocno, allocno_order[j])
893 || CONFLICTP (allocno_order[j], allocno))
895 if (allocno_size[allocno_order[j]] <= allocno_size[allocno])
896 IOR_HARD_REG_SET (temp,
897 hard_reg_full_preferences[allocno_order[j]]);
899 IOR_HARD_REG_SET (temp2,
900 hard_reg_full_preferences[allocno_order[j]]);
902 AND_COMPL_HARD_REG_SET (temp, hard_reg_full_preferences[allocno]);
903 IOR_HARD_REG_SET (temp, temp2);
904 COPY_HARD_REG_SET (regs_someone_prefers[allocno], temp);
908 /* Assign a hard register to ALLOCNO; look for one that is the beginning
909 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
910 The registers marked in PREFREGS are tried first.
912 LOSERS, if non-zero, is a HARD_REG_SET indicating registers that cannot
913 be used for this allocation.
915 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
916 Otherwise ignore that preferred class and use the alternate class.
918 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
919 will have to be saved and restored at calls.
921 RETRYING is nonzero if this is called from retry_global_alloc.
923 If we find one, record it in reg_renumber.
924 If not, do nothing. */
927 find_reg (allocno, losers, alt_regs_p, accept_call_clobbered, retrying)
931 int accept_call_clobbered;
934 register int i, best_reg, pass;
936 register /* Declare it register if it's a scalar. */
938 HARD_REG_SET used, used1, used2;
940 enum reg_class class = (alt_regs_p
941 ? reg_alternate_class (allocno_reg[allocno])
942 : reg_preferred_class (allocno_reg[allocno]));
943 enum machine_mode mode = PSEUDO_REGNO_MODE (allocno_reg[allocno]);
945 if (accept_call_clobbered)
946 COPY_HARD_REG_SET (used1, call_fixed_reg_set);
947 else if (allocno_calls_crossed[allocno] == 0)
948 COPY_HARD_REG_SET (used1, fixed_reg_set);
950 COPY_HARD_REG_SET (used1, call_used_reg_set);
952 /* Some registers should not be allocated in global-alloc. */
953 IOR_HARD_REG_SET (used1, no_global_alloc_regs);
955 IOR_HARD_REG_SET (used1, losers);
957 IOR_COMPL_HARD_REG_SET (used1, reg_class_contents[(int) class]);
958 COPY_HARD_REG_SET (used2, used1);
960 IOR_HARD_REG_SET (used1, hard_reg_conflicts[allocno]);
962 #ifdef CLASS_CANNOT_CHANGE_SIZE
963 if (REG_CHANGES_SIZE (allocno_reg[allocno]))
964 IOR_HARD_REG_SET (used1,
965 reg_class_contents[(int) CLASS_CANNOT_CHANGE_SIZE]);
968 /* Try each hard reg to see if it fits. Do this in two passes.
969 In the first pass, skip registers that are preferred by some other pseudo
970 to give it a better chance of getting one of those registers. Only if
971 we can't get a register when excluding those do we take one of them.
972 However, we never allocate a register for the first time in pass 0. */
974 COPY_HARD_REG_SET (used, used1);
975 IOR_COMPL_HARD_REG_SET (used, regs_used_so_far);
976 IOR_HARD_REG_SET (used, regs_someone_prefers[allocno]);
979 for (i = FIRST_PSEUDO_REGISTER, pass = 0;
980 pass <= 1 && i >= FIRST_PSEUDO_REGISTER;
984 COPY_HARD_REG_SET (used, used1);
985 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
987 #ifdef REG_ALLOC_ORDER
988 int regno = reg_alloc_order[i];
992 if (! TEST_HARD_REG_BIT (used, regno)
993 && HARD_REGNO_MODE_OK (regno, mode)
994 && (allocno_calls_crossed[allocno] == 0
995 || accept_call_clobbered
996 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
999 register int lim = regno + HARD_REGNO_NREGS (regno, mode);
1002 && ! TEST_HARD_REG_BIT (used, j));
1009 #ifndef REG_ALLOC_ORDER
1010 i = j; /* Skip starting points we know will lose */
1016 /* See if there is a preferred register with the same class as the register
1017 we allocated above. Making this restriction prevents register
1018 preferencing from creating worse register allocation.
1020 Remove from the preferred registers and conflicting registers. Note that
1021 additional conflicts may have been added after `prune_preferences' was
1024 First do this for those register with copy preferences, then all
1025 preferred registers. */
1027 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[allocno], used);
1028 GO_IF_HARD_REG_SUBSET (hard_reg_copy_preferences[allocno],
1029 reg_class_contents[(int) NO_REGS], no_copy_prefs);
1033 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1034 if (TEST_HARD_REG_BIT (hard_reg_copy_preferences[allocno], i)
1035 && HARD_REGNO_MODE_OK (i, mode)
1036 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1037 || reg_class_subset_p (REGNO_REG_CLASS (i),
1038 REGNO_REG_CLASS (best_reg))
1039 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1040 REGNO_REG_CLASS (i))))
1043 register int lim = i + HARD_REGNO_NREGS (i, mode);
1046 && ! TEST_HARD_REG_BIT (used, j)
1047 && (REGNO_REG_CLASS (j)
1048 == REGNO_REG_CLASS (best_reg + (j - i))
1049 || reg_class_subset_p (REGNO_REG_CLASS (j),
1050 REGNO_REG_CLASS (best_reg + (j - i)))
1051 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1052 REGNO_REG_CLASS (j))));
1063 AND_COMPL_HARD_REG_SET (hard_reg_preferences[allocno], used);
1064 GO_IF_HARD_REG_SUBSET (hard_reg_preferences[allocno],
1065 reg_class_contents[(int) NO_REGS], no_prefs);
1069 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1070 if (TEST_HARD_REG_BIT (hard_reg_preferences[allocno], i)
1071 && HARD_REGNO_MODE_OK (i, mode)
1072 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1073 || reg_class_subset_p (REGNO_REG_CLASS (i),
1074 REGNO_REG_CLASS (best_reg))
1075 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1076 REGNO_REG_CLASS (i))))
1079 register int lim = i + HARD_REGNO_NREGS (i, mode);
1082 && ! TEST_HARD_REG_BIT (used, j)
1083 && (REGNO_REG_CLASS (j)
1084 == REGNO_REG_CLASS (best_reg + (j - i))
1085 || reg_class_subset_p (REGNO_REG_CLASS (j),
1086 REGNO_REG_CLASS (best_reg + (j - i)))
1087 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1088 REGNO_REG_CLASS (j))));
1099 /* If we haven't succeeded yet, try with caller-saves.
1100 We need not check to see if the current function has nonlocal
1101 labels because we don't put any pseudos that are live over calls in
1102 registers in that case. */
1104 if (flag_caller_saves && best_reg < 0)
1106 /* Did not find a register. If it would be profitable to
1107 allocate a call-clobbered register and save and restore it
1108 around calls, do that. */
1109 if (! accept_call_clobbered
1110 && allocno_calls_crossed[allocno] != 0
1111 && CALLER_SAVE_PROFITABLE (allocno_n_refs[allocno],
1112 allocno_calls_crossed[allocno]))
1114 HARD_REG_SET new_losers;
1116 CLEAR_HARD_REG_SET (new_losers);
1118 COPY_HARD_REG_SET (new_losers, losers);
1120 IOR_HARD_REG_SET(new_losers, losing_caller_save_reg_set);
1121 find_reg (allocno, new_losers, alt_regs_p, 1, retrying);
1122 if (reg_renumber[allocno_reg[allocno]] >= 0)
1124 caller_save_needed = 1;
1130 /* If we haven't succeeded yet,
1131 see if some hard reg that conflicts with us
1132 was utilized poorly by local-alloc.
1133 If so, kick out the regs that were put there by local-alloc
1134 so we can use it instead. */
1135 if (best_reg < 0 && !retrying
1136 /* Let's not bother with multi-reg allocnos. */
1137 && allocno_size[allocno] == 1)
1139 /* Count from the end, to find the least-used ones first. */
1140 for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1142 #ifdef REG_ALLOC_ORDER
1143 int regno = reg_alloc_order[i];
1148 if (local_reg_n_refs[regno] != 0
1149 /* Don't use a reg no good for this pseudo. */
1150 && ! TEST_HARD_REG_BIT (used2, regno)
1151 && HARD_REGNO_MODE_OK (regno, mode)
1152 #ifdef CLASS_CANNOT_CHANGE_SIZE
1153 && ! (REG_CHANGES_SIZE (allocno_reg[allocno])
1154 && (TEST_HARD_REG_BIT
1155 (reg_class_contents[(int) CLASS_CANNOT_CHANGE_SIZE],
1160 /* We explicitly evaluate the divide results into temporary
1161 variables so as to avoid excess precision problems that occur
1162 on a i386-unknown-sysv4.2 (unixware) host. */
1164 double tmp1 = ((double) local_reg_n_refs[regno]
1165 / local_reg_live_length[regno]);
1166 double tmp2 = ((double) allocno_n_refs[allocno]
1167 / allocno_live_length[allocno]);
1171 /* Hard reg REGNO was used less in total by local regs
1172 than it would be used by this one allocno! */
1174 for (k = 0; k < max_regno; k++)
1175 if (reg_renumber[k] >= 0)
1177 int r = reg_renumber[k];
1179 = r + HARD_REGNO_NREGS (r, PSEUDO_REGNO_MODE (k));
1181 if (regno >= r && regno < endregno)
1182 reg_renumber[k] = -1;
1192 /* Did we find a register? */
1196 register int lim, j;
1197 HARD_REG_SET this_reg;
1199 /* Yes. Record it as the hard register of this pseudo-reg. */
1200 reg_renumber[allocno_reg[allocno]] = best_reg;
1201 /* Also of any pseudo-regs that share with it. */
1202 if (reg_may_share[allocno_reg[allocno]])
1203 for (j = FIRST_PSEUDO_REGISTER; j < max_regno; j++)
1204 if (reg_allocno[j] == allocno)
1205 reg_renumber[j] = best_reg;
1207 /* Make a set of the hard regs being allocated. */
1208 CLEAR_HARD_REG_SET (this_reg);
1209 lim = best_reg + HARD_REGNO_NREGS (best_reg, mode);
1210 for (j = best_reg; j < lim; j++)
1212 SET_HARD_REG_BIT (this_reg, j);
1213 SET_HARD_REG_BIT (regs_used_so_far, j);
1214 /* This is no longer a reg used just by local regs. */
1215 local_reg_n_refs[j] = 0;
1217 /* For each other pseudo-reg conflicting with this one,
1218 mark it as conflicting with the hard regs this one occupies. */
1220 for (j = 0; j < max_allocno; j++)
1221 if (CONFLICTP (lim, j) || CONFLICTP (j, lim))
1223 IOR_HARD_REG_SET (hard_reg_conflicts[j], this_reg);
1228 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1229 Perhaps it had previously seemed not worth a hard reg,
1230 or perhaps its old hard reg has been commandeered for reloads.
1231 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1232 they do not appear to be allocated.
1233 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1236 retry_global_alloc (regno, forbidden_regs)
1238 HARD_REG_SET forbidden_regs;
1240 int allocno = reg_allocno[regno];
1243 /* If we have more than one register class,
1244 first try allocating in the class that is cheapest
1245 for this pseudo-reg. If that fails, try any reg. */
1246 if (N_REG_CLASSES > 1)
1247 find_reg (allocno, forbidden_regs, 0, 0, 1);
1248 if (reg_renumber[regno] < 0
1249 && reg_alternate_class (regno) != NO_REGS)
1250 find_reg (allocno, forbidden_regs, 1, 0, 1);
1252 /* If we found a register, modify the RTL for the register to
1253 show the hard register, and mark that register live. */
1254 if (reg_renumber[regno] >= 0)
1256 REGNO (regno_reg_rtx[regno]) = reg_renumber[regno];
1257 mark_home_live (regno);
1262 /* Record a conflict between register REGNO
1263 and everything currently live.
1264 REGNO must not be a pseudo reg that was allocated
1265 by local_alloc; such numbers must be translated through
1266 reg_renumber before calling here. */
1269 record_one_conflict (regno)
1274 if (regno < FIRST_PSEUDO_REGISTER)
1275 /* When a hard register becomes live,
1276 record conflicts with live pseudo regs. */
1277 for (j = 0; j < max_allocno; j++)
1279 if (ALLOCNO_LIVE_P (j))
1280 SET_HARD_REG_BIT (hard_reg_conflicts[j], regno);
1283 /* When a pseudo-register becomes live,
1284 record conflicts first with hard regs,
1285 then with other pseudo regs. */
1287 register int ialloc = reg_allocno[regno];
1288 register int ialloc_prod = ialloc * allocno_row_words;
1289 IOR_HARD_REG_SET (hard_reg_conflicts[ialloc], hard_regs_live);
1290 for (j = allocno_row_words - 1; j >= 0; j--)
1294 for (k = 0; k < n_no_conflict_pairs; k++)
1295 if (! ((j == no_conflict_pairs[k].allocno1
1296 && ialloc == no_conflict_pairs[k].allocno2)
1298 (j == no_conflict_pairs[k].allocno2
1299 && ialloc == no_conflict_pairs[k].allocno1)))
1301 conflicts[ialloc_prod + j] |= allocnos_live[j];
1306 /* Record all allocnos currently live as conflicting
1307 with each other and with all hard regs currently live.
1308 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1309 are currently live. Their bits are also flagged in allocnos_live. */
1312 record_conflicts (allocno_vec, len)
1313 register int *allocno_vec;
1316 register int allocno;
1318 register int ialloc_prod;
1322 allocno = allocno_vec[len];
1323 ialloc_prod = allocno * allocno_row_words;
1324 IOR_HARD_REG_SET (hard_reg_conflicts[allocno], hard_regs_live);
1325 for (j = allocno_row_words - 1; j >= 0; j--)
1326 conflicts[ialloc_prod + j] |= allocnos_live[j];
1330 /* Handle the case where REG is set by the insn being scanned,
1331 during the forward scan to accumulate conflicts.
1332 Store a 1 in regs_live or allocnos_live for this register, record how many
1333 consecutive hardware registers it actually needs,
1334 and record a conflict with all other registers already live.
1336 Note that even if REG does not remain alive after this insn,
1337 we must mark it here as live, to ensure a conflict between
1338 REG and any other regs set in this insn that really do live.
1339 This is because those other regs could be considered after this.
1341 REG might actually be something other than a register;
1342 if so, we do nothing.
1344 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1345 a REG_INC note was found for it). */
1348 mark_reg_store (reg, setter)
1353 /* WORD is which word of a multi-register group is being stored.
1354 For the case where the store is actually into a SUBREG of REG.
1355 Except we don't use it; I believe the entire REG needs to be
1359 if (GET_CODE (reg) == SUBREG)
1361 word = SUBREG_WORD (reg);
1362 reg = SUBREG_REG (reg);
1365 if (GET_CODE (reg) != REG)
1368 regs_set[n_regs_set++] = reg;
1370 if (setter && GET_CODE (setter) != CLOBBER)
1371 set_preference (reg, SET_SRC (setter));
1373 regno = REGNO (reg);
1375 /* Either this is one of the max_allocno pseudo regs not allocated,
1376 or it is or has a hardware reg. First handle the pseudo-regs. */
1377 if (regno >= FIRST_PSEUDO_REGISTER)
1379 if (reg_allocno[regno] >= 0)
1381 SET_ALLOCNO_LIVE (reg_allocno[regno]);
1382 record_one_conflict (regno);
1386 if (reg_renumber[regno] >= 0)
1387 regno = reg_renumber[regno] /* + word */;
1389 /* Handle hardware regs (and pseudos allocated to hard regs). */
1390 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1392 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1393 while (regno < last)
1395 record_one_conflict (regno);
1396 SET_HARD_REG_BIT (hard_regs_live, regno);
1402 /* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
1405 mark_reg_clobber (reg, setter)
1408 if (GET_CODE (setter) == CLOBBER)
1409 mark_reg_store (reg, setter);
1412 /* Record that REG has conflicts with all the regs currently live.
1413 Do not mark REG itself as live. */
1416 mark_reg_conflicts (reg)
1421 if (GET_CODE (reg) == SUBREG)
1422 reg = SUBREG_REG (reg);
1424 if (GET_CODE (reg) != REG)
1427 regno = REGNO (reg);
1429 /* Either this is one of the max_allocno pseudo regs not allocated,
1430 or it is or has a hardware reg. First handle the pseudo-regs. */
1431 if (regno >= FIRST_PSEUDO_REGISTER)
1433 if (reg_allocno[regno] >= 0)
1434 record_one_conflict (regno);
1437 if (reg_renumber[regno] >= 0)
1438 regno = reg_renumber[regno];
1440 /* Handle hardware regs (and pseudos allocated to hard regs). */
1441 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1443 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1444 while (regno < last)
1446 record_one_conflict (regno);
1452 /* Mark REG as being dead (following the insn being scanned now).
1453 Store a 0 in regs_live or allocnos_live for this register. */
1456 mark_reg_death (reg)
1459 register int regno = REGNO (reg);
1461 /* Either this is one of the max_allocno pseudo regs not allocated,
1462 or it is a hardware reg. First handle the pseudo-regs. */
1463 if (regno >= FIRST_PSEUDO_REGISTER)
1465 if (reg_allocno[regno] >= 0)
1466 CLEAR_ALLOCNO_LIVE (reg_allocno[regno]);
1469 /* For pseudo reg, see if it has been assigned a hardware reg. */
1470 if (reg_renumber[regno] >= 0)
1471 regno = reg_renumber[regno];
1473 /* Handle hardware regs (and pseudos allocated to hard regs). */
1474 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1476 /* Pseudo regs already assigned hardware regs are treated
1477 almost the same as explicit hardware regs. */
1478 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1479 while (regno < last)
1481 CLEAR_HARD_REG_BIT (hard_regs_live, regno);
1487 /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1488 for the value stored in it. MODE determines how many consecutive
1489 registers are actually in use. Do not record conflicts;
1490 it is assumed that the caller will do that. */
1493 mark_reg_live_nc (regno, mode)
1495 enum machine_mode mode;
1497 register int last = regno + HARD_REGNO_NREGS (regno, mode);
1498 while (regno < last)
1500 SET_HARD_REG_BIT (hard_regs_live, regno);
1505 /* Try to set a preference for an allocno to a hard register.
1506 We are passed DEST and SRC which are the operands of a SET. It is known
1507 that SRC is a register. If SRC or the first operand of SRC is a register,
1508 try to set a preference. If one of the two is a hard register and the other
1509 is a pseudo-register, mark the preference.
1511 Note that we are not as aggressive as local-alloc in trying to tie a
1512 pseudo-register to a hard register. */
1515 set_preference (dest, src)
1518 int src_regno, dest_regno;
1519 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1520 to compensate for subregs in SRC or DEST. */
1525 if (GET_RTX_FORMAT (GET_CODE (src))[0] == 'e')
1526 src = XEXP (src, 0), copy = 0;
1528 /* Get the reg number for both SRC and DEST.
1529 If neither is a reg, give up. */
1531 if (GET_CODE (src) == REG)
1532 src_regno = REGNO (src);
1533 else if (GET_CODE (src) == SUBREG && GET_CODE (SUBREG_REG (src)) == REG)
1535 src_regno = REGNO (SUBREG_REG (src));
1536 offset += SUBREG_WORD (src);
1541 if (GET_CODE (dest) == REG)
1542 dest_regno = REGNO (dest);
1543 else if (GET_CODE (dest) == SUBREG && GET_CODE (SUBREG_REG (dest)) == REG)
1545 dest_regno = REGNO (SUBREG_REG (dest));
1546 offset -= SUBREG_WORD (dest);
1551 /* Convert either or both to hard reg numbers. */
1553 if (reg_renumber[src_regno] >= 0)
1554 src_regno = reg_renumber[src_regno];
1556 if (reg_renumber[dest_regno] >= 0)
1557 dest_regno = reg_renumber[dest_regno];
1559 /* Now if one is a hard reg and the other is a global pseudo
1560 then give the other a preference. */
1562 if (dest_regno < FIRST_PSEUDO_REGISTER && src_regno >= FIRST_PSEUDO_REGISTER
1563 && reg_allocno[src_regno] >= 0)
1565 dest_regno -= offset;
1566 if (dest_regno >= 0 && dest_regno < FIRST_PSEUDO_REGISTER)
1569 SET_REGBIT (hard_reg_copy_preferences,
1570 reg_allocno[src_regno], dest_regno);
1572 SET_REGBIT (hard_reg_preferences,
1573 reg_allocno[src_regno], dest_regno);
1574 for (i = dest_regno;
1575 i < dest_regno + HARD_REGNO_NREGS (dest_regno, GET_MODE (dest));
1577 SET_REGBIT (hard_reg_full_preferences, reg_allocno[src_regno], i);
1581 if (src_regno < FIRST_PSEUDO_REGISTER && dest_regno >= FIRST_PSEUDO_REGISTER
1582 && reg_allocno[dest_regno] >= 0)
1584 src_regno += offset;
1585 if (src_regno >= 0 && src_regno < FIRST_PSEUDO_REGISTER)
1588 SET_REGBIT (hard_reg_copy_preferences,
1589 reg_allocno[dest_regno], src_regno);
1591 SET_REGBIT (hard_reg_preferences,
1592 reg_allocno[dest_regno], src_regno);
1594 i < src_regno + HARD_REGNO_NREGS (src_regno, GET_MODE (src));
1596 SET_REGBIT (hard_reg_full_preferences, reg_allocno[dest_regno], i);
1601 /* Indicate that hard register number FROM was eliminated and replaced with
1602 an offset from hard register number TO. The status of hard registers live
1603 at the start of a basic block is updated by replacing a use of FROM with
1607 mark_elimination (from, to)
1612 for (i = 0; i < n_basic_blocks; i++)
1614 register regset r = BASIC_BLOCK (i)->global_live_at_start;
1615 if (REGNO_REG_SET_P (r, from))
1617 CLEAR_REGNO_REG_SET (r, from);
1618 SET_REGNO_REG_SET (r, to);
1623 /* Used for communication between the following functions. Holds the
1624 current life information. */
1625 static regset live_relevant_regs;
1627 /* Record in live_relevant_regs that register REG became live. This
1628 is called via note_stores. */
1630 reg_becomes_live (reg, setter)
1632 rtx setter ATTRIBUTE_UNUSED;
1636 if (GET_CODE (reg) == SUBREG)
1637 reg = SUBREG_REG (reg);
1639 if (GET_CODE (reg) != REG)
1642 regno = REGNO (reg);
1643 if (regno < FIRST_PSEUDO_REGISTER)
1645 int nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg));
1647 SET_REGNO_REG_SET (live_relevant_regs, regno++);
1649 else if (reg_renumber[regno] >= 0)
1650 SET_REGNO_REG_SET (live_relevant_regs, regno);
1653 /* Record in live_relevant_regs that register REGNO died. */
1655 reg_dies (regno, mode)
1657 enum machine_mode mode;
1659 if (regno < FIRST_PSEUDO_REGISTER)
1661 int nregs = HARD_REGNO_NREGS (regno, mode);
1663 CLEAR_REGNO_REG_SET (live_relevant_regs, regno++);
1666 CLEAR_REGNO_REG_SET (live_relevant_regs, regno);
1669 /* Walk the insns of the current function and build reload_insn_chain,
1670 and record register life information. */
1672 build_insn_chain (first)
1675 struct insn_chain **p = &reload_insn_chain;
1676 struct insn_chain *prev = 0;
1679 live_relevant_regs = ALLOCA_REG_SET ();
1681 for (; first; first = NEXT_INSN (first))
1683 struct insn_chain *c;
1685 if (first == BLOCK_HEAD (b))
1688 CLEAR_REG_SET (live_relevant_regs);
1689 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1690 if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, i)
1691 && ! TEST_HARD_REG_BIT (eliminable_regset, i))
1692 SET_REGNO_REG_SET (live_relevant_regs, i);
1694 for (; i < max_regno; i++)
1695 if (reg_renumber[i] >= 0
1696 && REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, i))
1697 SET_REGNO_REG_SET (live_relevant_regs, i);
1700 if (GET_CODE (first) != NOTE && GET_CODE (first) != BARRIER)
1702 c = new_insn_chain ();
1710 COPY_REG_SET (c->live_before, live_relevant_regs);
1712 if (GET_RTX_CLASS (GET_CODE (first)) == 'i')
1716 /* Mark the death of everything that dies in this instruction. */
1718 for (link = REG_NOTES (first); link; link = XEXP (link, 1))
1719 if (REG_NOTE_KIND (link) == REG_DEAD
1720 && GET_CODE (XEXP (link, 0)) == REG)
1721 reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)));
1723 /* Mark everything born in this instruction as live. */
1725 note_stores (PATTERN (first), reg_becomes_live);
1728 /* Remember which registers are live at the end of the insn, before
1729 killing those with REG_UNUSED notes. */
1730 COPY_REG_SET (c->live_after, live_relevant_regs);
1732 if (GET_RTX_CLASS (GET_CODE (first)) == 'i')
1736 /* Mark anything that is set in this insn and then unused as dying. */
1738 for (link = REG_NOTES (first); link; link = XEXP (link, 1))
1739 if (REG_NOTE_KIND (link) == REG_UNUSED
1740 && GET_CODE (XEXP (link, 0)) == REG)
1741 reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)));
1745 if (first == BLOCK_END (b))
1748 /* Stop after we pass the end of the last basic block. Verify that
1749 no real insns are after the end of the last basic block.
1751 We may want to reorganize the loop somewhat since this test should
1752 always be the right exit test. */
1753 if (b == n_basic_blocks)
1755 for (first = NEXT_INSN (first) ; first; first = NEXT_INSN (first))
1756 if (GET_RTX_CLASS (GET_CODE (first)) == 'i'
1757 && GET_CODE (PATTERN (first)) != USE)
1762 FREE_REG_SET (live_relevant_regs);
1766 /* Print debugging trace information if -dg switch is given,
1767 showing the information on which the allocation decisions are based. */
1770 dump_conflicts (file)
1774 register int has_preferences;
1777 for (i = 0; i < max_allocno; i++)
1779 if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
1783 fprintf (file, ";; %d regs to allocate:", nregs);
1784 for (i = 0; i < max_allocno; i++)
1787 if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
1789 fprintf (file, " %d", allocno_reg[allocno_order[i]]);
1790 for (j = 0; j < max_regno; j++)
1791 if (reg_allocno[j] == allocno_order[i]
1792 && j != allocno_reg[allocno_order[i]])
1793 fprintf (file, "+%d", j);
1794 if (allocno_size[allocno_order[i]] != 1)
1795 fprintf (file, " (%d)", allocno_size[allocno_order[i]]);
1797 fprintf (file, "\n");
1799 for (i = 0; i < max_allocno; i++)
1802 fprintf (file, ";; %d conflicts:", allocno_reg[i]);
1803 for (j = 0; j < max_allocno; j++)
1804 if (CONFLICTP (i, j) || CONFLICTP (j, i))
1805 fprintf (file, " %d", allocno_reg[j]);
1806 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1807 if (TEST_HARD_REG_BIT (hard_reg_conflicts[i], j))
1808 fprintf (file, " %d", j);
1809 fprintf (file, "\n");
1811 has_preferences = 0;
1812 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1813 if (TEST_HARD_REG_BIT (hard_reg_preferences[i], j))
1814 has_preferences = 1;
1816 if (! has_preferences)
1818 fprintf (file, ";; %d preferences:", allocno_reg[i]);
1819 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1820 if (TEST_HARD_REG_BIT (hard_reg_preferences[i], j))
1821 fprintf (file, " %d", j);
1822 fprintf (file, "\n");
1824 fprintf (file, "\n");
1828 dump_global_regs (file)
1833 fprintf (file, ";; Register dispositions:\n");
1834 for (i = FIRST_PSEUDO_REGISTER, j = 0; i < max_regno; i++)
1835 if (reg_renumber[i] >= 0)
1837 fprintf (file, "%d in %d ", i, reg_renumber[i]);
1839 fprintf (file, "\n");
1842 fprintf (file, "\n\n;; Hard regs used: ");
1843 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1844 if (regs_ever_live[i])
1845 fprintf (file, " %d", i);
1846 fprintf (file, "\n\n");