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"
29 #include "basic-block.h"
32 #include "insn-config.h"
37 /* This pass of the compiler performs global register allocation.
38 It assigns hard register numbers to all the pseudo registers
39 that were not handled in local_alloc. Assignments are recorded
40 in the vector reg_renumber, not by changing the rtl code.
41 (Such changes are made by final). The entry point is
42 the function global_alloc.
44 After allocation is complete, the reload pass is run as a subroutine
45 of this pass, so that when a pseudo reg loses its hard reg due to
46 spilling it is possible to make a second attempt to find a hard
47 reg for it. The reload pass is independent in other respects
48 and it is run even when stupid register allocation is in use.
50 1. Assign allocation-numbers (allocnos) to the pseudo-registers
51 still needing allocations and to the pseudo-registers currently
52 allocated by local-alloc which may be spilled by reload.
53 Set up tables reg_allocno and allocno_reg to map
54 reg numbers to allocnos and vice versa.
55 max_allocno gets the number of allocnos in use.
57 2. Allocate a max_allocno by max_allocno conflict bit matrix and clear it.
58 Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix
59 for conflicts between allocnos and explicit hard register use
60 (which includes use of pseudo-registers allocated by local_alloc).
62 3. For each basic block
63 walk forward through the block, recording which
64 pseudo-registers and which hardware registers are live.
65 Build the conflict matrix between the pseudo-registers
66 and another of pseudo-registers versus hardware registers.
67 Also record the preferred hardware registers
68 for each pseudo-register.
70 4. Sort a table of the allocnos into order of
71 desirability of the variables.
73 5. Allocate the variables in that order; each if possible into
74 a preferred register, else into another register. */
76 /* Number of pseudo-registers which are candidates for allocation. */
78 static int max_allocno;
80 /* Indexed by (pseudo) reg number, gives the allocno, or -1
81 for pseudo registers which are not to be allocated. */
83 static int *reg_allocno;
85 /* Indexed by allocno, gives the reg number. */
87 static int *allocno_reg;
89 /* A vector of the integers from 0 to max_allocno-1,
90 sorted in the order of first-to-be-allocated first. */
92 static int *allocno_order;
94 /* Indexed by an allocno, gives the number of consecutive
95 hard registers needed by that pseudo reg. */
97 static int *allocno_size;
99 /* Indexed by (pseudo) reg number, gives the number of another
100 lower-numbered pseudo reg which can share a hard reg with this pseudo
101 *even if the two pseudos would otherwise appear to conflict*. */
103 static int *reg_may_share;
105 /* Define the number of bits in each element of `conflicts' and what
106 type that element has. We use the largest integer format on the
109 #define INT_BITS HOST_BITS_PER_WIDE_INT
110 #define INT_TYPE HOST_WIDE_INT
112 /* max_allocno by max_allocno array of bits,
113 recording whether two allocno's conflict (can't go in the same
116 `conflicts' is not symmetric; a conflict between allocno's i and j
117 is recorded either in element i,j or in element j,i. */
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 + (J) / INT_BITS] \
130 & ((INT_TYPE) 1 << ((J) % INT_BITS)))
132 #define SET_CONFLICT(I, J) \
133 (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
134 |= ((INT_TYPE) 1 << ((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 GENERIC_PTR, const GENERIC_PTR));
260 static void global_conflicts PROTO((void));
261 static void expand_preferences PROTO((void));
262 static void prune_preferences PROTO((void));
263 static void find_reg PROTO((int, HARD_REG_SET, int, int, int));
264 static void record_one_conflict PROTO((int));
265 static void record_conflicts PROTO((int *, int));
266 static void mark_reg_store PROTO((rtx, rtx));
267 static void mark_reg_clobber PROTO((rtx, rtx));
268 static void mark_reg_conflicts PROTO((rtx));
269 static void mark_reg_death PROTO((rtx));
270 static void mark_reg_live_nc PROTO((int, enum machine_mode));
271 static void set_preference PROTO((rtx, rtx));
272 static void dump_conflicts PROTO((FILE *));
273 static void reg_becomes_live PROTO((rtx, rtx));
274 static void reg_dies PROTO((int, enum machine_mode));
275 static void build_insn_chain PROTO((rtx));
277 /* Perform allocation of pseudo-registers not allocated by local_alloc.
278 FILE is a file to output debugging information on,
279 or zero if such output is not desired.
281 Return value is nonzero if reload failed
282 and we must not do any more for this function. */
289 #ifdef ELIMINABLE_REGS
290 static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
293 = (! flag_omit_frame_pointer
294 #ifdef EXIT_IGNORE_STACK
295 || (current_function_calls_alloca && EXIT_IGNORE_STACK)
297 || FRAME_POINTER_REQUIRED);
304 /* A machine may have certain hard registers that
305 are safe to use only within a basic block. */
307 CLEAR_HARD_REG_SET (no_global_alloc_regs);
308 #ifdef OVERLAPPING_REGNO_P
309 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
310 if (OVERLAPPING_REGNO_P (i))
311 SET_HARD_REG_BIT (no_global_alloc_regs, i);
314 /* Build the regset of all eliminable registers and show we can't use those
315 that we already know won't be eliminated. */
316 #ifdef ELIMINABLE_REGS
317 for (i = 0; i < sizeof eliminables / sizeof eliminables[0]; i++)
319 SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from);
321 if (! CAN_ELIMINATE (eliminables[i].from, eliminables[i].to)
322 || (eliminables[i].to == STACK_POINTER_REGNUM && need_fp))
323 SET_HARD_REG_BIT (no_global_alloc_regs, eliminables[i].from);
325 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
326 SET_HARD_REG_BIT (eliminable_regset, HARD_FRAME_POINTER_REGNUM);
328 SET_HARD_REG_BIT (no_global_alloc_regs, HARD_FRAME_POINTER_REGNUM);
332 SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM);
334 SET_HARD_REG_BIT (no_global_alloc_regs, FRAME_POINTER_REGNUM);
337 /* Track which registers have already been used. Start with registers
338 explicitly in the rtl, then registers allocated by local register
341 CLEAR_HARD_REG_SET (regs_used_so_far);
342 #ifdef LEAF_REGISTERS
343 /* If we are doing the leaf function optimization, and this is a leaf
344 function, it means that the registers that take work to save are those
345 that need a register window. So prefer the ones that can be used in
349 static char leaf_regs[] = LEAF_REGISTERS;
351 if (only_leaf_regs_used () && leaf_function_p ())
352 cheap_regs = leaf_regs;
354 cheap_regs = call_used_regs;
355 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
356 if (regs_ever_live[i] || cheap_regs[i])
357 SET_HARD_REG_BIT (regs_used_so_far, i);
360 /* We consider registers that do not have to be saved over calls as if
361 they were already used since there is no cost in using them. */
362 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
363 if (regs_ever_live[i] || call_used_regs[i])
364 SET_HARD_REG_BIT (regs_used_so_far, i);
367 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
368 if (reg_renumber[i] >= 0)
369 SET_HARD_REG_BIT (regs_used_so_far, reg_renumber[i]);
371 /* Establish mappings from register number to allocation number
372 and vice versa. In the process, count the allocnos. */
374 reg_allocno = (int *) alloca (max_regno * sizeof (int));
376 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
379 /* Initialize the shared-hard-reg mapping
380 from the list of pairs that may share. */
381 reg_may_share = (int *) alloca (max_regno * sizeof (int));
382 bzero ((char *) reg_may_share, 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 *) alloca (max_allocno * sizeof (int));
414 allocno_size = (int *) alloca (max_allocno * sizeof (int));
415 allocno_calls_crossed = (int *) alloca (max_allocno * sizeof (int));
416 allocno_n_refs = (int *) alloca (max_allocno * sizeof (int));
417 allocno_live_length = (int *) alloca (max_allocno * sizeof (int));
418 bzero ((char *) allocno_size, max_allocno * sizeof (int));
419 bzero ((char *) allocno_calls_crossed, max_allocno * sizeof (int));
420 bzero ((char *) allocno_n_refs, max_allocno * sizeof (int));
421 bzero ((char *) allocno_live_length, max_allocno * sizeof (int));
423 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
424 if (reg_allocno[i] >= 0)
426 int allocno = reg_allocno[i];
427 allocno_reg[allocno] = i;
428 allocno_size[allocno] = PSEUDO_REGNO_SIZE (i);
429 allocno_calls_crossed[allocno] += REG_N_CALLS_CROSSED (i);
430 allocno_n_refs[allocno] += REG_N_REFS (i);
431 if (allocno_live_length[allocno] < REG_LIVE_LENGTH (i))
432 allocno_live_length[allocno] = REG_LIVE_LENGTH (i);
435 /* Calculate amount of usage of each hard reg by pseudos
436 allocated by local-alloc. This is to see if we want to
438 bzero ((char *) local_reg_live_length, sizeof local_reg_live_length);
439 bzero ((char *) local_reg_n_refs, sizeof local_reg_n_refs);
440 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
441 if (reg_renumber[i] >= 0)
443 int regno = reg_renumber[i];
444 int endregno = regno + HARD_REGNO_NREGS (regno, PSEUDO_REGNO_MODE (i));
447 for (j = regno; j < endregno; j++)
449 local_reg_n_refs[j] += REG_N_REFS (i);
450 local_reg_live_length[j] += REG_LIVE_LENGTH (i);
454 /* We can't override local-alloc for a reg used not just by local-alloc. */
455 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
456 if (regs_ever_live[i])
457 local_reg_n_refs[i] = 0;
459 /* Allocate the space for the conflict and preference tables and
463 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
464 bzero ((char *) hard_reg_conflicts, max_allocno * sizeof (HARD_REG_SET));
467 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
468 bzero ((char *) hard_reg_preferences, max_allocno * sizeof (HARD_REG_SET));
470 hard_reg_copy_preferences
471 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
472 bzero ((char *) hard_reg_copy_preferences,
473 max_allocno * sizeof (HARD_REG_SET));
475 hard_reg_full_preferences
476 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
477 bzero ((char *) hard_reg_full_preferences,
478 max_allocno * sizeof (HARD_REG_SET));
481 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
482 bzero ((char *) regs_someone_prefers, max_allocno * sizeof (HARD_REG_SET));
484 allocno_row_words = (max_allocno + INT_BITS - 1) / INT_BITS;
486 /* We used to use alloca here, but the size of what it would try to
487 allocate would occasionally cause it to exceed the stack limit and
488 cause unpredictable core dumps. Some examples were > 2Mb in size. */
489 conflicts = (INT_TYPE *) xmalloc (max_allocno * allocno_row_words
490 * sizeof (INT_TYPE));
491 bzero ((char *) conflicts,
492 max_allocno * allocno_row_words * sizeof (INT_TYPE));
494 allocnos_live = (INT_TYPE *) alloca (allocno_row_words * sizeof (INT_TYPE));
496 /* If there is work to be done (at least one reg to allocate),
497 perform global conflict analysis and allocate the regs. */
501 /* Scan all the insns and compute the conflicts among allocnos
502 and between allocnos and hard regs. */
506 /* Eliminate conflicts between pseudos and eliminable registers. If
507 the register is not eliminated, the pseudo won't really be able to
508 live in the eliminable register, so the conflict doesn't matter.
509 If we do eliminate the register, the conflict will no longer exist.
510 So in either case, we can ignore the conflict. Likewise for
513 for (i = 0; i < (size_t) max_allocno; i++)
515 AND_COMPL_HARD_REG_SET (hard_reg_conflicts[i], eliminable_regset);
516 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[i],
518 AND_COMPL_HARD_REG_SET (hard_reg_preferences[i], eliminable_regset);
521 /* Try to expand the preferences by merging them between allocnos. */
523 expand_preferences ();
525 /* Determine the order to allocate the remaining pseudo registers. */
527 allocno_order = (int *) alloca (max_allocno * sizeof (int));
528 for (i = 0; i < (size_t) max_allocno; i++)
529 allocno_order[i] = i;
531 /* Default the size to 1, since allocno_compare uses it to divide by.
532 Also convert allocno_live_length of zero to -1. A length of zero
533 can occur when all the registers for that allocno have reg_live_length
534 equal to -2. In this case, we want to make an allocno, but not
535 allocate it. So avoid the divide-by-zero and set it to a low
538 for (i = 0; i < (size_t) max_allocno; i++)
540 if (allocno_size[i] == 0)
542 if (allocno_live_length[i] == 0)
543 allocno_live_length[i] = -1;
546 qsort (allocno_order, max_allocno, sizeof (int), allocno_compare);
548 prune_preferences ();
551 dump_conflicts (file);
553 /* Try allocating them, one by one, in that order,
554 except for parameters marked with reg_live_length[regno] == -2. */
556 for (i = 0; i < (size_t) max_allocno; i++)
557 if (reg_renumber[allocno_reg[allocno_order[i]]] < 0
558 && REG_LIVE_LENGTH (allocno_reg[allocno_order[i]]) >= 0)
560 /* If we have more than one register class,
561 first try allocating in the class that is cheapest
562 for this pseudo-reg. If that fails, try any reg. */
563 if (N_REG_CLASSES > 1)
565 find_reg (allocno_order[i], 0, 0, 0, 0);
566 if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
569 if (reg_alternate_class (allocno_reg[allocno_order[i]]) != NO_REGS)
570 find_reg (allocno_order[i], 0, 1, 0, 0);
574 /* Do the reloads now while the allocno data still exist, so that we can
575 try to assign new hard regs to any pseudo regs that are spilled. */
577 #if 0 /* We need to eliminate regs even if there is no rtl code,
578 for the sake of debugging information. */
579 if (n_basic_blocks > 0)
582 build_insn_chain (get_insns ());
583 retval = reload (get_insns (), 1, file);
590 /* Sort predicate for ordering the allocnos.
591 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
594 allocno_compare (v1p, v2p)
595 const GENERIC_PTR v1p;
596 const GENERIC_PTR v2p;
598 int v1 = *(int *)v1p, v2 = *(int *)v2p;
599 /* Note that the quotient will never be bigger than
600 the value of floor_log2 times the maximum number of
601 times a register can occur in one insn (surely less than 100).
602 Multiplying this by 10000 can't overflow. */
604 = (((double) (floor_log2 (allocno_n_refs[v1]) * allocno_n_refs[v1])
605 / allocno_live_length[v1])
606 * 10000 * allocno_size[v1]);
608 = (((double) (floor_log2 (allocno_n_refs[v2]) * allocno_n_refs[v2])
609 / allocno_live_length[v2])
610 * 10000 * allocno_size[v2]);
614 /* If regs are equally good, sort by allocno,
615 so that the results of qsort leave nothing to chance. */
619 /* Scan the rtl code and record all conflicts and register preferences in the
620 conflict matrices and preference tables. */
627 int *block_start_allocnos;
629 /* Make a vector that mark_reg_{store,clobber} will store in. */
630 regs_set = (rtx *) alloca (max_parallel * sizeof (rtx) * 2);
632 block_start_allocnos = (int *) alloca (max_allocno * sizeof (int));
634 for (b = 0; b < n_basic_blocks; b++)
636 bzero ((char *) allocnos_live, allocno_row_words * sizeof (INT_TYPE));
638 /* Initialize table of registers currently live
639 to the state at the beginning of this basic block.
640 This also marks the conflicts among them.
642 For pseudo-regs, there is only one bit for each one
643 no matter how many hard regs it occupies.
644 This is ok; we know the size from PSEUDO_REGNO_SIZE.
645 For explicit hard regs, we cannot know the size that way
646 since one hard reg can be used with various sizes.
647 Therefore, we must require that all the hard regs
648 implicitly live as part of a multi-word hard reg
649 are explicitly marked in basic_block_live_at_start. */
652 register regset old = BASIC_BLOCK (b)->global_live_at_start;
655 REG_SET_TO_HARD_REG_SET (hard_regs_live, old);
656 EXECUTE_IF_SET_IN_REG_SET (old, FIRST_PSEUDO_REGISTER, i,
658 register int a = reg_allocno[i];
661 SET_ALLOCNO_LIVE (a);
662 block_start_allocnos[ax++] = a;
664 else if ((a = reg_renumber[i]) >= 0)
666 (a, PSEUDO_REGNO_MODE (i));
669 /* Record that each allocno now live conflicts with each other
670 allocno now live, and with each hard reg now live. */
672 record_conflicts (block_start_allocnos, ax);
676 /* Pseudos can't go in stack regs at the start of a basic block
677 that can be reached through a computed goto, since reg-stack
678 can't handle computed gotos. */
679 /* ??? Seems more likely that reg-stack can't handle any abnormal
680 edges, critical or not, computed goto or otherwise. */
683 for (e = BASIC_BLOCK (b)->pred; e ; e = e->pred_next)
684 if (e->flags & EDGE_ABNORMAL)
688 for (ax = FIRST_STACK_REG; ax <= LAST_STACK_REG; ax++)
689 record_one_conflict (ax);
694 insn = BLOCK_HEAD (b);
696 /* Scan the code of this basic block, noting which allocnos
697 and hard regs are born or die. When one is born,
698 record a conflict with all others currently live. */
702 register RTX_CODE code = GET_CODE (insn);
705 /* Make regs_set an empty set. */
709 if (code == INSN || code == CALL_INSN || code == JUMP_INSN)
714 for (link = REG_NOTES (insn);
715 link && i < NUM_NO_CONFLICT_PAIRS;
716 link = XEXP (link, 1))
717 if (REG_NOTE_KIND (link) == REG_NO_CONFLICT)
719 no_conflict_pairs[i].allocno1
720 = reg_allocno[REGNO (SET_DEST (PATTERN (insn)))];
721 no_conflict_pairs[i].allocno2
722 = reg_allocno[REGNO (XEXP (link, 0))];
727 /* Mark any registers clobbered by INSN as live,
728 so they conflict with the inputs. */
730 note_stores (PATTERN (insn), mark_reg_clobber);
732 /* Mark any registers dead after INSN as dead now. */
734 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
735 if (REG_NOTE_KIND (link) == REG_DEAD)
736 mark_reg_death (XEXP (link, 0));
738 /* Mark any registers set in INSN as live,
739 and mark them as conflicting with all other live regs.
740 Clobbers are processed again, so they conflict with
741 the registers that are set. */
743 note_stores (PATTERN (insn), mark_reg_store);
746 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
747 if (REG_NOTE_KIND (link) == REG_INC)
748 mark_reg_store (XEXP (link, 0), NULL_RTX);
751 /* If INSN has multiple outputs, then any reg that dies here
752 and is used inside of an output
753 must conflict with the other outputs.
755 It is unsafe to use !single_set here since it will ignore an
756 unused output. Just because an output is unused does not mean
757 the compiler can assume the side effect will not occur.
758 Consider if REG appears in the address of an output and we
759 reload the output. If we allocate REG to the same hard
760 register as an unused output we could set the hard register
761 before the output reload insn. */
762 if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn))
763 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
764 if (REG_NOTE_KIND (link) == REG_DEAD)
766 int used_in_output = 0;
768 rtx reg = XEXP (link, 0);
770 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
772 rtx set = XVECEXP (PATTERN (insn), 0, i);
773 if (GET_CODE (set) == SET
774 && GET_CODE (SET_DEST (set)) != REG
775 && !rtx_equal_p (reg, SET_DEST (set))
776 && reg_overlap_mentioned_p (reg, SET_DEST (set)))
780 mark_reg_conflicts (reg);
783 /* Mark any registers set in INSN and then never used. */
785 while (n_regs_set > 0)
786 if (find_regno_note (insn, REG_UNUSED,
787 REGNO (regs_set[--n_regs_set])))
788 mark_reg_death (regs_set[n_regs_set]);
791 if (insn == BLOCK_END (b))
793 insn = NEXT_INSN (insn);
797 /* Expand the preference information by looking for cases where one allocno
798 dies in an insn that sets an allocno. If those two allocnos don't conflict,
799 merge any preferences between those allocnos. */
802 expand_preferences ()
808 /* We only try to handle the most common cases here. Most of the cases
809 where this wins are reg-reg copies. */
811 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
812 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
813 && (set = single_set (insn)) != 0
814 && GET_CODE (SET_DEST (set)) == REG
815 && reg_allocno[REGNO (SET_DEST (set))] >= 0)
816 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
817 if (REG_NOTE_KIND (link) == REG_DEAD
818 && GET_CODE (XEXP (link, 0)) == REG
819 && reg_allocno[REGNO (XEXP (link, 0))] >= 0
820 && ! CONFLICTP (reg_allocno[REGNO (SET_DEST (set))],
821 reg_allocno[REGNO (XEXP (link, 0))])
822 && ! CONFLICTP (reg_allocno[REGNO (XEXP (link, 0))],
823 reg_allocno[REGNO (SET_DEST (set))]))
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. */
860 /* Scan least most important to most important.
861 For each allocno, remove from preferences registers that cannot be used,
862 either because of conflicts or register type. Then compute all registers
863 preferred by each lower-priority register that conflicts. */
865 for (i = max_allocno - 1; i >= 0; i--)
869 allocno = allocno_order[i];
870 COPY_HARD_REG_SET (temp, hard_reg_conflicts[allocno]);
872 if (allocno_calls_crossed[allocno] == 0)
873 IOR_HARD_REG_SET (temp, fixed_reg_set);
875 IOR_HARD_REG_SET (temp, call_used_reg_set);
877 IOR_COMPL_HARD_REG_SET
879 reg_class_contents[(int) reg_preferred_class (allocno_reg[allocno])]);
881 AND_COMPL_HARD_REG_SET (hard_reg_preferences[allocno], temp);
882 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[allocno], temp);
883 AND_COMPL_HARD_REG_SET (hard_reg_full_preferences[allocno], temp);
885 CLEAR_HARD_REG_SET (regs_someone_prefers[allocno]);
887 /* Merge in the preferences of lower-priority registers (they have
888 already been pruned). If we also prefer some of those registers,
889 don't exclude them unless we are of a smaller size (in which case
890 we want to give the lower-priority allocno the first chance for
892 for (j = i + 1; j < max_allocno; j++)
893 if (CONFLICTP (allocno, allocno_order[j])
894 || CONFLICTP (allocno_order[j], allocno))
896 COPY_HARD_REG_SET (temp,
897 hard_reg_full_preferences[allocno_order[j]]);
898 if (allocno_size[allocno_order[j]] <= allocno_size[allocno])
899 AND_COMPL_HARD_REG_SET (temp,
900 hard_reg_full_preferences[allocno]);
902 IOR_HARD_REG_SET (regs_someone_prefers[allocno], temp);
907 /* Assign a hard register to ALLOCNO; look for one that is the beginning
908 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
909 The registers marked in PREFREGS are tried first.
911 LOSERS, if non-zero, is a HARD_REG_SET indicating registers that cannot
912 be used for this allocation.
914 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
915 Otherwise ignore that preferred class and use the alternate class.
917 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
918 will have to be saved and restored at calls.
920 RETRYING is nonzero if this is called from retry_global_alloc.
922 If we find one, record it in reg_renumber.
923 If not, do nothing. */
926 find_reg (allocno, losers, alt_regs_p, accept_call_clobbered, retrying)
930 int accept_call_clobbered;
933 register int i, best_reg, pass;
935 register /* Declare it register if it's a scalar. */
937 HARD_REG_SET used, used1, used2;
939 enum reg_class class = (alt_regs_p
940 ? reg_alternate_class (allocno_reg[allocno])
941 : reg_preferred_class (allocno_reg[allocno]));
942 enum machine_mode mode = PSEUDO_REGNO_MODE (allocno_reg[allocno]);
944 if (accept_call_clobbered)
945 COPY_HARD_REG_SET (used1, call_fixed_reg_set);
946 else if (allocno_calls_crossed[allocno] == 0)
947 COPY_HARD_REG_SET (used1, fixed_reg_set);
949 COPY_HARD_REG_SET (used1, call_used_reg_set);
951 /* Some registers should not be allocated in global-alloc. */
952 IOR_HARD_REG_SET (used1, no_global_alloc_regs);
954 IOR_HARD_REG_SET (used1, losers);
956 IOR_COMPL_HARD_REG_SET (used1, reg_class_contents[(int) class]);
957 COPY_HARD_REG_SET (used2, used1);
959 IOR_HARD_REG_SET (used1, hard_reg_conflicts[allocno]);
961 #ifdef CLASS_CANNOT_CHANGE_SIZE
962 if (REG_CHANGES_SIZE (allocno_reg[allocno]))
963 IOR_HARD_REG_SET (used1,
964 reg_class_contents[(int) CLASS_CANNOT_CHANGE_SIZE]);
967 /* Try each hard reg to see if it fits. Do this in two passes.
968 In the first pass, skip registers that are preferred by some other pseudo
969 to give it a better chance of getting one of those registers. Only if
970 we can't get a register when excluding those do we take one of them.
971 However, we never allocate a register for the first time in pass 0. */
973 COPY_HARD_REG_SET (used, used1);
974 IOR_COMPL_HARD_REG_SET (used, regs_used_so_far);
975 IOR_HARD_REG_SET (used, regs_someone_prefers[allocno]);
978 for (i = FIRST_PSEUDO_REGISTER, pass = 0;
979 pass <= 1 && i >= FIRST_PSEUDO_REGISTER;
983 COPY_HARD_REG_SET (used, used1);
984 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
986 #ifdef REG_ALLOC_ORDER
987 int regno = reg_alloc_order[i];
991 if (! TEST_HARD_REG_BIT (used, regno)
992 && HARD_REGNO_MODE_OK (regno, mode)
993 && (allocno_calls_crossed[allocno] == 0
994 || accept_call_clobbered
995 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
998 register int lim = regno + HARD_REGNO_NREGS (regno, mode);
1001 && ! TEST_HARD_REG_BIT (used, j));
1008 #ifndef REG_ALLOC_ORDER
1009 i = j; /* Skip starting points we know will lose */
1015 /* See if there is a preferred register with the same class as the register
1016 we allocated above. Making this restriction prevents register
1017 preferencing from creating worse register allocation.
1019 Remove from the preferred registers and conflicting registers. Note that
1020 additional conflicts may have been added after `prune_preferences' was
1023 First do this for those register with copy preferences, then all
1024 preferred registers. */
1026 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[allocno], used);
1027 GO_IF_HARD_REG_SUBSET (hard_reg_copy_preferences[allocno],
1028 reg_class_contents[(int) NO_REGS], no_copy_prefs);
1032 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1033 if (TEST_HARD_REG_BIT (hard_reg_copy_preferences[allocno], i)
1034 && HARD_REGNO_MODE_OK (i, mode)
1035 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1036 || reg_class_subset_p (REGNO_REG_CLASS (i),
1037 REGNO_REG_CLASS (best_reg))
1038 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1039 REGNO_REG_CLASS (i))))
1042 register int lim = i + HARD_REGNO_NREGS (i, mode);
1045 && ! TEST_HARD_REG_BIT (used, j)
1046 && (REGNO_REG_CLASS (j)
1047 == REGNO_REG_CLASS (best_reg + (j - i))
1048 || reg_class_subset_p (REGNO_REG_CLASS (j),
1049 REGNO_REG_CLASS (best_reg + (j - i)))
1050 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1051 REGNO_REG_CLASS (j))));
1062 AND_COMPL_HARD_REG_SET (hard_reg_preferences[allocno], used);
1063 GO_IF_HARD_REG_SUBSET (hard_reg_preferences[allocno],
1064 reg_class_contents[(int) NO_REGS], no_prefs);
1068 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1069 if (TEST_HARD_REG_BIT (hard_reg_preferences[allocno], i)
1070 && HARD_REGNO_MODE_OK (i, mode)
1071 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1072 || reg_class_subset_p (REGNO_REG_CLASS (i),
1073 REGNO_REG_CLASS (best_reg))
1074 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1075 REGNO_REG_CLASS (i))))
1078 register int lim = i + HARD_REGNO_NREGS (i, mode);
1081 && ! TEST_HARD_REG_BIT (used, j)
1082 && (REGNO_REG_CLASS (j)
1083 == REGNO_REG_CLASS (best_reg + (j - i))
1084 || reg_class_subset_p (REGNO_REG_CLASS (j),
1085 REGNO_REG_CLASS (best_reg + (j - i)))
1086 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1087 REGNO_REG_CLASS (j))));
1098 /* If we haven't succeeded yet, try with caller-saves.
1099 We need not check to see if the current function has nonlocal
1100 labels because we don't put any pseudos that are live over calls in
1101 registers in that case. */
1103 if (flag_caller_saves && best_reg < 0)
1105 /* Did not find a register. If it would be profitable to
1106 allocate a call-clobbered register and save and restore it
1107 around calls, do that. */
1108 if (! accept_call_clobbered
1109 && allocno_calls_crossed[allocno] != 0
1110 && CALLER_SAVE_PROFITABLE (allocno_n_refs[allocno],
1111 allocno_calls_crossed[allocno]))
1113 HARD_REG_SET new_losers;
1115 CLEAR_HARD_REG_SET (new_losers);
1117 COPY_HARD_REG_SET (new_losers, losers);
1119 IOR_HARD_REG_SET(new_losers, losing_caller_save_reg_set);
1120 find_reg (allocno, new_losers, alt_regs_p, 1, retrying);
1121 if (reg_renumber[allocno_reg[allocno]] >= 0)
1123 caller_save_needed = 1;
1129 /* If we haven't succeeded yet,
1130 see if some hard reg that conflicts with us
1131 was utilized poorly by local-alloc.
1132 If so, kick out the regs that were put there by local-alloc
1133 so we can use it instead. */
1134 if (best_reg < 0 && !retrying
1135 /* Let's not bother with multi-reg allocnos. */
1136 && allocno_size[allocno] == 1)
1138 /* Count from the end, to find the least-used ones first. */
1139 for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1141 #ifdef REG_ALLOC_ORDER
1142 int regno = reg_alloc_order[i];
1147 if (local_reg_n_refs[regno] != 0
1148 /* Don't use a reg no good for this pseudo. */
1149 && ! TEST_HARD_REG_BIT (used2, regno)
1150 && HARD_REGNO_MODE_OK (regno, mode)
1151 #ifdef CLASS_CANNOT_CHANGE_SIZE
1152 && ! (REG_CHANGES_SIZE (allocno_reg[allocno])
1153 && (TEST_HARD_REG_BIT
1154 (reg_class_contents[(int) CLASS_CANNOT_CHANGE_SIZE],
1159 /* We explicitly evaluate the divide results into temporary
1160 variables so as to avoid excess precision problems that occur
1161 on a i386-unknown-sysv4.2 (unixware) host. */
1163 double tmp1 = ((double) local_reg_n_refs[regno]
1164 / local_reg_live_length[regno]);
1165 double tmp2 = ((double) allocno_n_refs[allocno]
1166 / allocno_live_length[allocno]);
1170 /* Hard reg REGNO was used less in total by local regs
1171 than it would be used by this one allocno! */
1173 for (k = 0; k < max_regno; k++)
1174 if (reg_renumber[k] >= 0)
1176 int r = reg_renumber[k];
1178 = r + HARD_REGNO_NREGS (r, PSEUDO_REGNO_MODE (k));
1180 if (regno >= r && regno < endregno)
1181 reg_renumber[k] = -1;
1191 /* Did we find a register? */
1195 register int lim, j;
1196 HARD_REG_SET this_reg;
1198 /* Yes. Record it as the hard register of this pseudo-reg. */
1199 reg_renumber[allocno_reg[allocno]] = best_reg;
1200 /* Also of any pseudo-regs that share with it. */
1201 if (reg_may_share[allocno_reg[allocno]])
1202 for (j = FIRST_PSEUDO_REGISTER; j < max_regno; j++)
1203 if (reg_allocno[j] == allocno)
1204 reg_renumber[j] = best_reg;
1206 /* Make a set of the hard regs being allocated. */
1207 CLEAR_HARD_REG_SET (this_reg);
1208 lim = best_reg + HARD_REGNO_NREGS (best_reg, mode);
1209 for (j = best_reg; j < lim; j++)
1211 SET_HARD_REG_BIT (this_reg, j);
1212 SET_HARD_REG_BIT (regs_used_so_far, j);
1213 /* This is no longer a reg used just by local regs. */
1214 local_reg_n_refs[j] = 0;
1216 /* For each other pseudo-reg conflicting with this one,
1217 mark it as conflicting with the hard regs this one occupies. */
1219 for (j = 0; j < max_allocno; j++)
1220 if (CONFLICTP (lim, j) || CONFLICTP (j, lim))
1222 IOR_HARD_REG_SET (hard_reg_conflicts[j], this_reg);
1227 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1228 Perhaps it had previously seemed not worth a hard reg,
1229 or perhaps its old hard reg has been commandeered for reloads.
1230 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1231 they do not appear to be allocated.
1232 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1235 retry_global_alloc (regno, forbidden_regs)
1237 HARD_REG_SET forbidden_regs;
1239 int allocno = reg_allocno[regno];
1242 /* If we have more than one register class,
1243 first try allocating in the class that is cheapest
1244 for this pseudo-reg. If that fails, try any reg. */
1245 if (N_REG_CLASSES > 1)
1246 find_reg (allocno, forbidden_regs, 0, 0, 1);
1247 if (reg_renumber[regno] < 0
1248 && reg_alternate_class (regno) != NO_REGS)
1249 find_reg (allocno, forbidden_regs, 1, 0, 1);
1251 /* If we found a register, modify the RTL for the register to
1252 show the hard register, and mark that register live. */
1253 if (reg_renumber[regno] >= 0)
1255 REGNO (regno_reg_rtx[regno]) = reg_renumber[regno];
1256 mark_home_live (regno);
1261 /* Record a conflict between register REGNO
1262 and everything currently live.
1263 REGNO must not be a pseudo reg that was allocated
1264 by local_alloc; such numbers must be translated through
1265 reg_renumber before calling here. */
1268 record_one_conflict (regno)
1273 if (regno < FIRST_PSEUDO_REGISTER)
1274 /* When a hard register becomes live,
1275 record conflicts with live pseudo regs. */
1276 for (j = 0; j < max_allocno; j++)
1278 if (ALLOCNO_LIVE_P (j))
1279 SET_HARD_REG_BIT (hard_reg_conflicts[j], regno);
1282 /* When a pseudo-register becomes live,
1283 record conflicts first with hard regs,
1284 then with other pseudo regs. */
1286 register int ialloc = reg_allocno[regno];
1287 register int ialloc_prod = ialloc * allocno_row_words;
1288 IOR_HARD_REG_SET (hard_reg_conflicts[ialloc], hard_regs_live);
1289 for (j = allocno_row_words - 1; j >= 0; j--)
1293 for (k = 0; k < n_no_conflict_pairs; k++)
1294 if (! ((j == no_conflict_pairs[k].allocno1
1295 && ialloc == no_conflict_pairs[k].allocno2)
1297 (j == no_conflict_pairs[k].allocno2
1298 && ialloc == no_conflict_pairs[k].allocno1)))
1300 conflicts[ialloc_prod + j] |= allocnos_live[j];
1305 /* Record all allocnos currently live as conflicting
1306 with each other and with all hard regs currently live.
1307 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1308 are currently live. Their bits are also flagged in allocnos_live. */
1311 record_conflicts (allocno_vec, len)
1312 register int *allocno_vec;
1315 register int allocno;
1317 register int ialloc_prod;
1321 allocno = allocno_vec[len];
1322 ialloc_prod = allocno * allocno_row_words;
1323 IOR_HARD_REG_SET (hard_reg_conflicts[allocno], hard_regs_live);
1324 for (j = allocno_row_words - 1; j >= 0; j--)
1325 conflicts[ialloc_prod + j] |= allocnos_live[j];
1329 /* Handle the case where REG is set by the insn being scanned,
1330 during the forward scan to accumulate conflicts.
1331 Store a 1 in regs_live or allocnos_live for this register, record how many
1332 consecutive hardware registers it actually needs,
1333 and record a conflict with all other registers already live.
1335 Note that even if REG does not remain alive after this insn,
1336 we must mark it here as live, to ensure a conflict between
1337 REG and any other regs set in this insn that really do live.
1338 This is because those other regs could be considered after this.
1340 REG might actually be something other than a register;
1341 if so, we do nothing.
1343 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1344 a REG_INC note was found for it). */
1347 mark_reg_store (reg, setter)
1352 /* WORD is which word of a multi-register group is being stored.
1353 For the case where the store is actually into a SUBREG of REG.
1354 Except we don't use it; I believe the entire REG needs to be
1358 if (GET_CODE (reg) == SUBREG)
1360 word = SUBREG_WORD (reg);
1361 reg = SUBREG_REG (reg);
1364 if (GET_CODE (reg) != REG)
1367 regs_set[n_regs_set++] = reg;
1369 if (setter && GET_CODE (setter) != CLOBBER)
1370 set_preference (reg, SET_SRC (setter));
1372 regno = REGNO (reg);
1374 /* Either this is one of the max_allocno pseudo regs not allocated,
1375 or it is or has a hardware reg. First handle the pseudo-regs. */
1376 if (regno >= FIRST_PSEUDO_REGISTER)
1378 if (reg_allocno[regno] >= 0)
1380 SET_ALLOCNO_LIVE (reg_allocno[regno]);
1381 record_one_conflict (regno);
1385 if (reg_renumber[regno] >= 0)
1386 regno = reg_renumber[regno] /* + word */;
1388 /* Handle hardware regs (and pseudos allocated to hard regs). */
1389 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1391 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1392 while (regno < last)
1394 record_one_conflict (regno);
1395 SET_HARD_REG_BIT (hard_regs_live, regno);
1401 /* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
1404 mark_reg_clobber (reg, setter)
1407 if (GET_CODE (setter) == CLOBBER)
1408 mark_reg_store (reg, setter);
1411 /* Record that REG has conflicts with all the regs currently live.
1412 Do not mark REG itself as live. */
1415 mark_reg_conflicts (reg)
1420 if (GET_CODE (reg) == SUBREG)
1421 reg = SUBREG_REG (reg);
1423 if (GET_CODE (reg) != REG)
1426 regno = REGNO (reg);
1428 /* Either this is one of the max_allocno pseudo regs not allocated,
1429 or it is or has a hardware reg. First handle the pseudo-regs. */
1430 if (regno >= FIRST_PSEUDO_REGISTER)
1432 if (reg_allocno[regno] >= 0)
1433 record_one_conflict (regno);
1436 if (reg_renumber[regno] >= 0)
1437 regno = reg_renumber[regno];
1439 /* Handle hardware regs (and pseudos allocated to hard regs). */
1440 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1442 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1443 while (regno < last)
1445 record_one_conflict (regno);
1451 /* Mark REG as being dead (following the insn being scanned now).
1452 Store a 0 in regs_live or allocnos_live for this register. */
1455 mark_reg_death (reg)
1458 register int regno = REGNO (reg);
1460 /* Either this is one of the max_allocno pseudo regs not allocated,
1461 or it is a hardware reg. First handle the pseudo-regs. */
1462 if (regno >= FIRST_PSEUDO_REGISTER)
1464 if (reg_allocno[regno] >= 0)
1465 CLEAR_ALLOCNO_LIVE (reg_allocno[regno]);
1468 /* For pseudo reg, see if it has been assigned a hardware reg. */
1469 if (reg_renumber[regno] >= 0)
1470 regno = reg_renumber[regno];
1472 /* Handle hardware regs (and pseudos allocated to hard regs). */
1473 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1475 /* Pseudo regs already assigned hardware regs are treated
1476 almost the same as explicit hardware regs. */
1477 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1478 while (regno < last)
1480 CLEAR_HARD_REG_BIT (hard_regs_live, regno);
1486 /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1487 for the value stored in it. MODE determines how many consecutive
1488 registers are actually in use. Do not record conflicts;
1489 it is assumed that the caller will do that. */
1492 mark_reg_live_nc (regno, mode)
1494 enum machine_mode mode;
1496 register int last = regno + HARD_REGNO_NREGS (regno, mode);
1497 while (regno < last)
1499 SET_HARD_REG_BIT (hard_regs_live, regno);
1504 /* Try to set a preference for an allocno to a hard register.
1505 We are passed DEST and SRC which are the operands of a SET. It is known
1506 that SRC is a register. If SRC or the first operand of SRC is a register,
1507 try to set a preference. If one of the two is a hard register and the other
1508 is a pseudo-register, mark the preference.
1510 Note that we are not as aggressive as local-alloc in trying to tie a
1511 pseudo-register to a hard register. */
1514 set_preference (dest, src)
1517 int src_regno, dest_regno;
1518 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1519 to compensate for subregs in SRC or DEST. */
1524 if (GET_RTX_FORMAT (GET_CODE (src))[0] == 'e')
1525 src = XEXP (src, 0), copy = 0;
1527 /* Get the reg number for both SRC and DEST.
1528 If neither is a reg, give up. */
1530 if (GET_CODE (src) == REG)
1531 src_regno = REGNO (src);
1532 else if (GET_CODE (src) == SUBREG && GET_CODE (SUBREG_REG (src)) == REG)
1534 src_regno = REGNO (SUBREG_REG (src));
1535 offset += SUBREG_WORD (src);
1540 if (GET_CODE (dest) == REG)
1541 dest_regno = REGNO (dest);
1542 else if (GET_CODE (dest) == SUBREG && GET_CODE (SUBREG_REG (dest)) == REG)
1544 dest_regno = REGNO (SUBREG_REG (dest));
1545 offset -= SUBREG_WORD (dest);
1550 /* Convert either or both to hard reg numbers. */
1552 if (reg_renumber[src_regno] >= 0)
1553 src_regno = reg_renumber[src_regno];
1555 if (reg_renumber[dest_regno] >= 0)
1556 dest_regno = reg_renumber[dest_regno];
1558 /* Now if one is a hard reg and the other is a global pseudo
1559 then give the other a preference. */
1561 if (dest_regno < FIRST_PSEUDO_REGISTER && src_regno >= FIRST_PSEUDO_REGISTER
1562 && reg_allocno[src_regno] >= 0)
1564 dest_regno -= offset;
1565 if (dest_regno >= 0 && dest_regno < FIRST_PSEUDO_REGISTER)
1568 SET_REGBIT (hard_reg_copy_preferences,
1569 reg_allocno[src_regno], dest_regno);
1571 SET_REGBIT (hard_reg_preferences,
1572 reg_allocno[src_regno], dest_regno);
1573 for (i = dest_regno;
1574 i < dest_regno + HARD_REGNO_NREGS (dest_regno, GET_MODE (dest));
1576 SET_REGBIT (hard_reg_full_preferences, reg_allocno[src_regno], i);
1580 if (src_regno < FIRST_PSEUDO_REGISTER && dest_regno >= FIRST_PSEUDO_REGISTER
1581 && reg_allocno[dest_regno] >= 0)
1583 src_regno += offset;
1584 if (src_regno >= 0 && src_regno < FIRST_PSEUDO_REGISTER)
1587 SET_REGBIT (hard_reg_copy_preferences,
1588 reg_allocno[dest_regno], src_regno);
1590 SET_REGBIT (hard_reg_preferences,
1591 reg_allocno[dest_regno], src_regno);
1593 i < src_regno + HARD_REGNO_NREGS (src_regno, GET_MODE (src));
1595 SET_REGBIT (hard_reg_full_preferences, reg_allocno[dest_regno], i);
1600 /* Indicate that hard register number FROM was eliminated and replaced with
1601 an offset from hard register number TO. The status of hard registers live
1602 at the start of a basic block is updated by replacing a use of FROM with
1606 mark_elimination (from, to)
1611 for (i = 0; i < n_basic_blocks; i++)
1613 register regset r = BASIC_BLOCK (i)->global_live_at_start;
1614 if (REGNO_REG_SET_P (r, from))
1616 CLEAR_REGNO_REG_SET (r, from);
1617 SET_REGNO_REG_SET (r, to);
1622 /* Used for communication between the following functions. Holds the
1623 current life information. */
1624 static regset live_relevant_regs;
1626 /* Record in live_relevant_regs that register REG became live. This
1627 is called via note_stores. */
1629 reg_becomes_live (reg, setter)
1631 rtx setter ATTRIBUTE_UNUSED;
1635 if (GET_CODE (reg) == SUBREG)
1636 reg = SUBREG_REG (reg);
1638 if (GET_CODE (reg) != REG)
1641 regno = REGNO (reg);
1642 if (regno < FIRST_PSEUDO_REGISTER)
1644 int nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg));
1646 SET_REGNO_REG_SET (live_relevant_regs, regno++);
1648 else if (reg_renumber[regno] >= 0)
1649 SET_REGNO_REG_SET (live_relevant_regs, regno);
1652 /* Record in live_relevant_regs that register REGNO died. */
1654 reg_dies (regno, mode)
1656 enum machine_mode mode;
1658 if (regno < FIRST_PSEUDO_REGISTER)
1660 int nregs = HARD_REGNO_NREGS (regno, mode);
1662 CLEAR_REGNO_REG_SET (live_relevant_regs, regno++);
1665 CLEAR_REGNO_REG_SET (live_relevant_regs, regno);
1668 /* Walk the insns of the current function and build reload_insn_chain,
1669 and record register life information. */
1671 build_insn_chain (first)
1674 struct insn_chain **p = &reload_insn_chain;
1675 struct insn_chain *prev = 0;
1678 live_relevant_regs = ALLOCA_REG_SET ();
1680 for (; first; first = NEXT_INSN (first))
1682 struct insn_chain *c;
1684 if (first == BLOCK_HEAD (b))
1687 CLEAR_REG_SET (live_relevant_regs);
1688 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1689 if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, i)
1690 && ! TEST_HARD_REG_BIT (eliminable_regset, i))
1691 SET_REGNO_REG_SET (live_relevant_regs, i);
1693 for (; i < max_regno; i++)
1694 if (reg_renumber[i] >= 0
1695 && REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, i))
1696 SET_REGNO_REG_SET (live_relevant_regs, i);
1699 if (GET_CODE (first) != NOTE && GET_CODE (first) != BARRIER)
1701 c = new_insn_chain ();
1709 COPY_REG_SET (c->live_before, live_relevant_regs);
1711 if (GET_RTX_CLASS (GET_CODE (first)) == 'i')
1715 /* Mark the death of everything that dies in this instruction. */
1717 for (link = REG_NOTES (first); link; link = XEXP (link, 1))
1718 if (REG_NOTE_KIND (link) == REG_DEAD
1719 && GET_CODE (XEXP (link, 0)) == REG)
1720 reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)));
1722 /* Mark everything born in this instruction as live. */
1724 note_stores (PATTERN (first), reg_becomes_live);
1727 /* Remember which registers are live at the end of the insn, before
1728 killing those with REG_UNUSED notes. */
1729 COPY_REG_SET (c->live_after, live_relevant_regs);
1731 if (GET_RTX_CLASS (GET_CODE (first)) == 'i')
1735 /* Mark anything that is set in this insn and then unused as dying. */
1737 for (link = REG_NOTES (first); link; link = XEXP (link, 1))
1738 if (REG_NOTE_KIND (link) == REG_UNUSED
1739 && GET_CODE (XEXP (link, 0)) == REG)
1740 reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)));
1744 if (first == BLOCK_END (b))
1747 /* Stop after we pass the end of the last basic block. Verify that
1748 no real insns are after the end of the last basic block.
1750 We may want to reorganize the loop somewhat since this test should
1751 always be the right exit test. */
1752 if (b == n_basic_blocks)
1754 for (first = NEXT_INSN (first) ; first; first = NEXT_INSN (first))
1755 if (GET_RTX_CLASS (GET_CODE (first)) == 'i'
1756 && GET_CODE (PATTERN (first)) != USE)
1761 FREE_REG_SET (live_relevant_regs);
1765 /* Print debugging trace information if -dg switch is given,
1766 showing the information on which the allocation decisions are based. */
1769 dump_conflicts (file)
1773 register int has_preferences;
1776 for (i = 0; i < max_allocno; i++)
1778 if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
1782 fprintf (file, ";; %d regs to allocate:", nregs);
1783 for (i = 0; i < max_allocno; i++)
1786 if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
1788 fprintf (file, " %d", allocno_reg[allocno_order[i]]);
1789 for (j = 0; j < max_regno; j++)
1790 if (reg_allocno[j] == allocno_order[i]
1791 && j != allocno_reg[allocno_order[i]])
1792 fprintf (file, "+%d", j);
1793 if (allocno_size[allocno_order[i]] != 1)
1794 fprintf (file, " (%d)", allocno_size[allocno_order[i]]);
1796 fprintf (file, "\n");
1798 for (i = 0; i < max_allocno; i++)
1801 fprintf (file, ";; %d conflicts:", allocno_reg[i]);
1802 for (j = 0; j < max_allocno; j++)
1803 if (CONFLICTP (i, j) || CONFLICTP (j, i))
1804 fprintf (file, " %d", allocno_reg[j]);
1805 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1806 if (TEST_HARD_REG_BIT (hard_reg_conflicts[i], j))
1807 fprintf (file, " %d", j);
1808 fprintf (file, "\n");
1810 has_preferences = 0;
1811 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1812 if (TEST_HARD_REG_BIT (hard_reg_preferences[i], j))
1813 has_preferences = 1;
1815 if (! has_preferences)
1817 fprintf (file, ";; %d preferences:", allocno_reg[i]);
1818 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1819 if (TEST_HARD_REG_BIT (hard_reg_preferences[i], j))
1820 fprintf (file, " %d", j);
1821 fprintf (file, "\n");
1823 fprintf (file, "\n");
1827 dump_global_regs (file)
1832 fprintf (file, ";; Register dispositions:\n");
1833 for (i = FIRST_PSEUDO_REGISTER, j = 0; i < max_regno; i++)
1834 if (reg_renumber[i] >= 0)
1836 fprintf (file, "%d in %d ", i, reg_renumber[i]);
1838 fprintf (file, "\n");
1841 fprintf (file, "\n\n;; Hard regs used: ");
1842 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1843 if (regs_ever_live[i])
1844 fprintf (file, " %d", i);
1845 fprintf (file, "\n\n");