1 /* Allocate registers for pseudo-registers that span basic blocks.
2 Copyright (C) 1987, 88, 91, 94, 96-98, 1999 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
26 #include "hard-reg-set.h"
30 #include "basic-block.h"
33 #include "insn-config.h"
38 /* This pass of the compiler performs global register allocation.
39 It assigns hard register numbers to all the pseudo registers
40 that were not handled in local_alloc. Assignments are recorded
41 in the vector reg_renumber, not by changing the rtl code.
42 (Such changes are made by final). The entry point is
43 the function global_alloc.
45 After allocation is complete, the reload pass is run as a subroutine
46 of this pass, so that when a pseudo reg loses its hard reg due to
47 spilling it is possible to make a second attempt to find a hard
48 reg for it. The reload pass is independent in other respects
49 and it is run even when stupid register allocation is in use.
51 1. Assign allocation-numbers (allocnos) to the pseudo-registers
52 still needing allocations and to the pseudo-registers currently
53 allocated by local-alloc which may be spilled by reload.
54 Set up tables reg_allocno and allocno_reg to map
55 reg numbers to allocnos and vice versa.
56 max_allocno gets the number of allocnos in use.
58 2. Allocate a max_allocno by max_allocno conflict bit matrix and clear it.
59 Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix
60 for conflicts between allocnos and explicit hard register use
61 (which includes use of pseudo-registers allocated by local_alloc).
63 3. For each basic block
64 walk forward through the block, recording which
65 pseudo-registers and which hardware registers are live.
66 Build the conflict matrix between the pseudo-registers
67 and another of pseudo-registers versus hardware registers.
68 Also record the preferred hardware registers
69 for each pseudo-register.
71 4. Sort a table of the allocnos into order of
72 desirability of the variables.
74 5. Allocate the variables in that order; each if possible into
75 a preferred register, else into another register. */
77 /* Number of pseudo-registers which are candidates for allocation. */
79 static int max_allocno;
81 /* Indexed by (pseudo) reg number, gives the allocno, or -1
82 for pseudo registers which are not to be allocated. */
84 static int *reg_allocno;
86 /* Indexed by allocno, gives the reg number. */
88 static int *allocno_reg;
90 /* A vector of the integers from 0 to max_allocno-1,
91 sorted in the order of first-to-be-allocated first. */
93 static int *allocno_order;
95 /* Indexed by an allocno, gives the number of consecutive
96 hard registers needed by that pseudo reg. */
98 static int *allocno_size;
100 /* Indexed by (pseudo) reg number, gives the number of another
101 lower-numbered pseudo reg which can share a hard reg with this pseudo
102 *even if the two pseudos would otherwise appear to conflict*. */
104 static int *reg_may_share;
106 /* Define the number of bits in each element of `conflicts' and what
107 type that element has. We use the largest integer format on the
110 #define INT_BITS HOST_BITS_PER_WIDE_INT
111 #define INT_TYPE HOST_WIDE_INT
113 /* max_allocno by max_allocno array of bits,
114 recording whether two allocno's conflict (can't go in the same
117 `conflicts' is symmetric after the call to mirror_conflicts. */
119 static INT_TYPE *conflicts;
121 /* Number of ints require to hold max_allocno bits.
122 This is the length of a row in `conflicts'. */
124 static int allocno_row_words;
126 /* Two macros to test or store 1 in an element of `conflicts'. */
128 #define CONFLICTP(I, J) \
129 (conflicts[(I) * allocno_row_words + (unsigned)(J) / INT_BITS] \
130 & ((INT_TYPE) 1 << ((unsigned)(J) % INT_BITS)))
132 #define SET_CONFLICT(I, J) \
133 (conflicts[(I) * allocno_row_words + (unsigned)(J) / INT_BITS] \
134 |= ((INT_TYPE) 1 << ((unsigned)(J) % INT_BITS)))
136 /* For any allocno set in ALLOCNO_SET, set ALLOCNO to that allocno,
138 #define EXECUTE_IF_SET_IN_ALLOCNO_SET(ALLOCNO_SET, ALLOCNO, CODE) \
142 INT_TYPE *p_ = (ALLOCNO_SET); \
144 for (i_ = allocno_row_words - 1, allocno_ = 0; i_ >= 0; \
145 i_--, allocno_ += INT_BITS) \
147 unsigned INT_TYPE word_ = (unsigned INT_TYPE) *p_++; \
149 for ((ALLOCNO) = allocno_; word_; word_ >>= 1, (ALLOCNO)++) \
157 /* This doesn't work for non-GNU C due to the way CODE is macro expanded. */
159 /* For any allocno that conflicts with IN_ALLOCNO, set OUT_ALLOCNO to
160 the conflicting allocno, and execute CODE. This macro assumes that
161 mirror_conflicts has been run. */
162 #define EXECUTE_IF_CONFLICT(IN_ALLOCNO, OUT_ALLOCNO, CODE)\
163 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + (IN_ALLOCNO) * allocno_row_words,\
167 /* Set of hard regs currently live (during scan of all insns). */
169 static HARD_REG_SET hard_regs_live;
171 /* Indexed by N, set of hard regs conflicting with allocno N. */
173 static HARD_REG_SET *hard_reg_conflicts;
175 /* Indexed by N, set of hard regs preferred by allocno N.
176 This is used to make allocnos go into regs that are copied to or from them,
177 when possible, to reduce register shuffling. */
179 static HARD_REG_SET *hard_reg_preferences;
181 /* Similar, but just counts register preferences made in simple copy
182 operations, rather than arithmetic. These are given priority because
183 we can always eliminate an insn by using these, but using a register
184 in the above list won't always eliminate an insn. */
186 static HARD_REG_SET *hard_reg_copy_preferences;
188 /* Similar to hard_reg_preferences, but includes bits for subsequent
189 registers when an allocno is multi-word. The above variable is used for
190 allocation while this is used to build reg_someone_prefers, below. */
192 static HARD_REG_SET *hard_reg_full_preferences;
194 /* Indexed by N, set of hard registers that some later allocno has a
197 static HARD_REG_SET *regs_someone_prefers;
199 /* Set of registers that global-alloc isn't supposed to use. */
201 static HARD_REG_SET no_global_alloc_regs;
203 /* Set of registers used so far. */
205 static HARD_REG_SET regs_used_so_far;
207 /* Number of calls crossed by each allocno. */
209 static int *allocno_calls_crossed;
211 /* Number of refs (weighted) to each allocno. */
213 static int *allocno_n_refs;
215 /* Guess at live length of each allocno.
216 This is actually the max of the live lengths of the regs. */
218 static int *allocno_live_length;
220 /* Number of refs (weighted) to each hard reg, as used by local alloc.
221 It is zero for a reg that contains global pseudos or is explicitly used. */
223 static int local_reg_n_refs[FIRST_PSEUDO_REGISTER];
225 /* Guess at live length of each hard reg, as used by local alloc.
226 This is actually the sum of the live lengths of the specific regs. */
228 static int local_reg_live_length[FIRST_PSEUDO_REGISTER];
230 /* Test a bit in TABLE, a vector of HARD_REG_SETs,
231 for vector element I, and hard register number J. */
233 #define REGBITP(TABLE, I, J) TEST_HARD_REG_BIT (TABLE[I], J)
235 /* Set to 1 a bit in a vector of HARD_REG_SETs. Works like REGBITP. */
237 #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (TABLE[I], J)
239 /* Bit mask for allocnos live at current point in the scan. */
241 static INT_TYPE *allocnos_live;
243 /* Test, set or clear bit number I in allocnos_live,
244 a bit vector indexed by allocno. */
246 #define ALLOCNO_LIVE_P(I) \
247 (allocnos_live[(unsigned)(I) / INT_BITS] \
248 & ((INT_TYPE) 1 << ((unsigned)(I) % INT_BITS)))
250 #define SET_ALLOCNO_LIVE(I) \
251 (allocnos_live[(unsigned)(I) / INT_BITS] \
252 |= ((INT_TYPE) 1 << ((unsigned)(I) % INT_BITS)))
254 #define CLEAR_ALLOCNO_LIVE(I) \
255 (allocnos_live[(unsigned)(I) / INT_BITS] \
256 &= ~((INT_TYPE) 1 << ((unsigned)(I) % INT_BITS)))
258 /* This is turned off because it doesn't work right for DImode.
259 (And it is only used for DImode, so the other cases are worthless.)
260 The problem is that it isn't true that there is NO possibility of conflict;
261 only that there is no conflict if the two pseudos get the exact same regs.
262 If they were allocated with a partial overlap, there would be a conflict.
263 We can't safely turn off the conflict unless we have another way to
264 prevent the partial overlap.
266 Idea: change hard_reg_conflicts so that instead of recording which
267 hard regs the allocno may not overlap, it records where the allocno
268 may not start. Change both where it is used and where it is updated.
269 Then there is a way to record that (reg:DI 108) may start at 10
270 but not at 9 or 11. There is still the question of how to record
271 this semi-conflict between two pseudos. */
273 /* Reg pairs for which conflict after the current insn
274 is inhibited by a REG_NO_CONFLICT note.
275 If the table gets full, we ignore any other notes--that is conservative. */
276 #define NUM_NO_CONFLICT_PAIRS 4
277 /* Number of pairs in use in this insn. */
278 int n_no_conflict_pairs;
279 static struct { int allocno1, allocno2;}
280 no_conflict_pairs[NUM_NO_CONFLICT_PAIRS];
283 /* Record all regs that are set in any one insn.
284 Communication from mark_reg_{store,clobber} and global_conflicts. */
286 static rtx *regs_set;
287 static int n_regs_set;
289 /* All registers that can be eliminated. */
291 static HARD_REG_SET eliminable_regset;
293 static int allocno_compare PROTO((const PTR, const PTR));
294 static void global_conflicts PROTO((void));
295 static void mirror_conflicts PROTO((void));
296 static void expand_preferences PROTO((void));
297 static void prune_preferences PROTO((void));
298 static void find_reg PROTO((int, HARD_REG_SET, int, int, int));
299 static void record_one_conflict PROTO((int));
300 static void record_conflicts PROTO((int *, int));
301 static void mark_reg_store PROTO((rtx, rtx, void *));
302 static void mark_reg_clobber PROTO((rtx, rtx, void *));
303 static void mark_reg_conflicts PROTO((rtx));
304 static void mark_reg_death PROTO((rtx));
305 static void mark_reg_live_nc PROTO((int, enum machine_mode));
306 static void set_preference PROTO((rtx, rtx));
307 static void dump_conflicts PROTO((FILE *));
308 static void reg_becomes_live PROTO((rtx, rtx, void *));
309 static void reg_dies PROTO((int, enum machine_mode));
310 static void build_insn_chain PROTO((rtx));
312 /* Perform allocation of pseudo-registers not allocated by local_alloc.
313 FILE is a file to output debugging information on,
314 or zero if such output is not desired.
316 Return value is nonzero if reload failed
317 and we must not do any more for this function. */
324 #ifdef ELIMINABLE_REGS
325 static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
328 = (! flag_omit_frame_pointer
329 #ifdef EXIT_IGNORE_STACK
330 || (current_function_calls_alloca && EXIT_IGNORE_STACK)
332 || FRAME_POINTER_REQUIRED);
339 /* A machine may have certain hard registers that
340 are safe to use only within a basic block. */
342 CLEAR_HARD_REG_SET (no_global_alloc_regs);
343 #ifdef OVERLAPPING_REGNO_P
344 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
345 if (OVERLAPPING_REGNO_P (i))
346 SET_HARD_REG_BIT (no_global_alloc_regs, i);
349 /* Build the regset of all eliminable registers and show we can't use those
350 that we already know won't be eliminated. */
351 #ifdef ELIMINABLE_REGS
352 for (i = 0; i < sizeof eliminables / sizeof eliminables[0]; i++)
354 SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from);
356 if (! CAN_ELIMINATE (eliminables[i].from, eliminables[i].to)
357 || (eliminables[i].to == STACK_POINTER_REGNUM && need_fp))
358 SET_HARD_REG_BIT (no_global_alloc_regs, eliminables[i].from);
360 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
361 SET_HARD_REG_BIT (eliminable_regset, HARD_FRAME_POINTER_REGNUM);
363 SET_HARD_REG_BIT (no_global_alloc_regs, HARD_FRAME_POINTER_REGNUM);
367 SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM);
369 SET_HARD_REG_BIT (no_global_alloc_regs, FRAME_POINTER_REGNUM);
372 /* Track which registers have already been used. Start with registers
373 explicitly in the rtl, then registers allocated by local register
376 CLEAR_HARD_REG_SET (regs_used_so_far);
377 #ifdef LEAF_REGISTERS
378 /* If we are doing the leaf function optimization, and this is a leaf
379 function, it means that the registers that take work to save are those
380 that need a register window. So prefer the ones that can be used in
384 static char leaf_regs[] = LEAF_REGISTERS;
386 if (only_leaf_regs_used () && leaf_function_p ())
387 cheap_regs = leaf_regs;
389 cheap_regs = call_used_regs;
390 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
391 if (regs_ever_live[i] || cheap_regs[i])
392 SET_HARD_REG_BIT (regs_used_so_far, i);
395 /* We consider registers that do not have to be saved over calls as if
396 they were already used since there is no cost in using them. */
397 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
398 if (regs_ever_live[i] || call_used_regs[i])
399 SET_HARD_REG_BIT (regs_used_so_far, i);
402 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
403 if (reg_renumber[i] >= 0)
404 SET_HARD_REG_BIT (regs_used_so_far, reg_renumber[i]);
406 /* Establish mappings from register number to allocation number
407 and vice versa. In the process, count the allocnos. */
409 reg_allocno = (int *) xmalloc (max_regno * sizeof (int));
411 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
414 /* Initialize the shared-hard-reg mapping
415 from the list of pairs that may share. */
416 reg_may_share = (int *) xcalloc (max_regno, sizeof (int));
417 for (x = regs_may_share; x; x = XEXP (XEXP (x, 1), 1))
419 int r1 = REGNO (XEXP (x, 0));
420 int r2 = REGNO (XEXP (XEXP (x, 1), 0));
422 reg_may_share[r1] = r2;
424 reg_may_share[r2] = r1;
427 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
428 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
429 that we are supposed to refrain from putting in a hard reg.
430 -2 means do make an allocno but don't allocate it. */
431 if (REG_N_REFS (i) != 0 && REG_LIVE_LENGTH (i) != -1
432 /* Don't allocate pseudos that cross calls,
433 if this function receives a nonlocal goto. */
434 && (! current_function_has_nonlocal_label
435 || REG_N_CALLS_CROSSED (i) == 0))
437 if (reg_renumber[i] < 0 && reg_may_share[i] && reg_allocno[reg_may_share[i]] >= 0)
438 reg_allocno[i] = reg_allocno[reg_may_share[i]];
440 reg_allocno[i] = max_allocno++;
441 if (REG_LIVE_LENGTH (i) == 0)
447 allocno_reg = (int *) xmalloc (max_allocno * sizeof (int));
448 allocno_size = (int *) xcalloc (max_allocno, sizeof (int));
449 allocno_calls_crossed = (int *) xcalloc (max_allocno, sizeof (int));
450 allocno_n_refs = (int *) xcalloc (max_allocno, sizeof (int));
451 allocno_live_length = (int *) xcalloc (max_allocno, sizeof (int));
453 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
454 if (reg_allocno[i] >= 0)
456 int allocno = reg_allocno[i];
457 allocno_reg[allocno] = i;
458 allocno_size[allocno] = PSEUDO_REGNO_SIZE (i);
459 allocno_calls_crossed[allocno] += REG_N_CALLS_CROSSED (i);
460 allocno_n_refs[allocno] += REG_N_REFS (i);
461 if (allocno_live_length[allocno] < REG_LIVE_LENGTH (i))
462 allocno_live_length[allocno] = REG_LIVE_LENGTH (i);
465 /* Calculate amount of usage of each hard reg by pseudos
466 allocated by local-alloc. This is to see if we want to
468 bzero ((char *) local_reg_live_length, sizeof local_reg_live_length);
469 bzero ((char *) local_reg_n_refs, sizeof local_reg_n_refs);
470 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
471 if (reg_renumber[i] >= 0)
473 int regno = reg_renumber[i];
474 int endregno = regno + HARD_REGNO_NREGS (regno, PSEUDO_REGNO_MODE (i));
477 for (j = regno; j < endregno; j++)
479 local_reg_n_refs[j] += REG_N_REFS (i);
480 local_reg_live_length[j] += REG_LIVE_LENGTH (i);
484 /* We can't override local-alloc for a reg used not just by local-alloc. */
485 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
486 if (regs_ever_live[i])
487 local_reg_n_refs[i] = 0;
489 /* Allocate the space for the conflict and preference tables and
493 = (HARD_REG_SET *) xcalloc (max_allocno, sizeof (HARD_REG_SET));
495 = (HARD_REG_SET *) xcalloc (max_allocno, sizeof (HARD_REG_SET));
496 hard_reg_copy_preferences
497 = (HARD_REG_SET *) xcalloc (max_allocno, sizeof (HARD_REG_SET));
498 hard_reg_full_preferences
499 = (HARD_REG_SET *) xcalloc (max_allocno, sizeof (HARD_REG_SET));
501 = (HARD_REG_SET *) xcalloc (max_allocno, sizeof (HARD_REG_SET));
503 allocno_row_words = (max_allocno + INT_BITS - 1) / INT_BITS;
505 /* We used to use alloca here, but the size of what it would try to
506 allocate would occasionally cause it to exceed the stack limit and
507 cause unpredictable core dumps. Some examples were > 2Mb in size. */
508 conflicts = (INT_TYPE *) xcalloc (max_allocno * allocno_row_words,
511 allocnos_live = (INT_TYPE *) xmalloc (allocno_row_words * sizeof (INT_TYPE));
513 /* If there is work to be done (at least one reg to allocate),
514 perform global conflict analysis and allocate the regs. */
518 /* Scan all the insns and compute the conflicts among allocnos
519 and between allocnos and hard regs. */
525 /* Eliminate conflicts between pseudos and eliminable registers. If
526 the register is not eliminated, the pseudo won't really be able to
527 live in the eliminable register, so the conflict doesn't matter.
528 If we do eliminate the register, the conflict will no longer exist.
529 So in either case, we can ignore the conflict. Likewise for
532 for (i = 0; i < (size_t) max_allocno; i++)
534 AND_COMPL_HARD_REG_SET (hard_reg_conflicts[i], eliminable_regset);
535 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[i],
537 AND_COMPL_HARD_REG_SET (hard_reg_preferences[i], eliminable_regset);
540 /* Try to expand the preferences by merging them between allocnos. */
542 expand_preferences ();
544 /* Determine the order to allocate the remaining pseudo registers. */
546 allocno_order = (int *) xmalloc (max_allocno * sizeof (int));
547 for (i = 0; i < (size_t) max_allocno; i++)
548 allocno_order[i] = i;
550 /* Default the size to 1, since allocno_compare uses it to divide by.
551 Also convert allocno_live_length of zero to -1. A length of zero
552 can occur when all the registers for that allocno have reg_live_length
553 equal to -2. In this case, we want to make an allocno, but not
554 allocate it. So avoid the divide-by-zero and set it to a low
557 for (i = 0; i < (size_t) max_allocno; i++)
559 if (allocno_size[i] == 0)
561 if (allocno_live_length[i] == 0)
562 allocno_live_length[i] = -1;
565 qsort (allocno_order, max_allocno, sizeof (int), allocno_compare);
567 prune_preferences ();
570 dump_conflicts (file);
572 /* Try allocating them, one by one, in that order,
573 except for parameters marked with reg_live_length[regno] == -2. */
575 for (i = 0; i < (size_t) max_allocno; i++)
576 if (reg_renumber[allocno_reg[allocno_order[i]]] < 0
577 && REG_LIVE_LENGTH (allocno_reg[allocno_order[i]]) >= 0)
579 /* If we have more than one register class,
580 first try allocating in the class that is cheapest
581 for this pseudo-reg. If that fails, try any reg. */
582 if (N_REG_CLASSES > 1)
584 find_reg (allocno_order[i], 0, 0, 0, 0);
585 if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
588 if (reg_alternate_class (allocno_reg[allocno_order[i]]) != NO_REGS)
589 find_reg (allocno_order[i], 0, 1, 0, 0);
592 free (allocno_order);
595 /* Do the reloads now while the allocno data still exist, so that we can
596 try to assign new hard regs to any pseudo regs that are spilled. */
598 #if 0 /* We need to eliminate regs even if there is no rtl code,
599 for the sake of debugging information. */
600 if (n_basic_blocks > 0)
603 build_insn_chain (get_insns ());
604 retval = reload (get_insns (), 1, file);
609 free (reg_may_share);
612 free (allocno_calls_crossed);
613 free (allocno_n_refs);
614 free (allocno_live_length);
615 free (hard_reg_conflicts);
616 free (hard_reg_preferences);
617 free (hard_reg_copy_preferences);
618 free (hard_reg_full_preferences);
619 free (regs_someone_prefers);
621 free (allocnos_live);
626 /* Sort predicate for ordering the allocnos.
627 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
630 allocno_compare (v1p, v2p)
634 int v1 = *(const int *)v1p, v2 = *(const int *)v2p;
635 /* Note that the quotient will never be bigger than
636 the value of floor_log2 times the maximum number of
637 times a register can occur in one insn (surely less than 100).
638 Multiplying this by 10000 can't overflow. */
640 = (((double) (floor_log2 (allocno_n_refs[v1]) * allocno_n_refs[v1])
641 / allocno_live_length[v1])
642 * 10000 * allocno_size[v1]);
644 = (((double) (floor_log2 (allocno_n_refs[v2]) * allocno_n_refs[v2])
645 / allocno_live_length[v2])
646 * 10000 * allocno_size[v2]);
650 /* If regs are equally good, sort by allocno,
651 so that the results of qsort leave nothing to chance. */
655 /* Scan the rtl code and record all conflicts and register preferences in the
656 conflict matrices and preference tables. */
663 int *block_start_allocnos;
665 /* Make a vector that mark_reg_{store,clobber} will store in. */
666 regs_set = (rtx *) xmalloc (max_parallel * sizeof (rtx) * 2);
668 block_start_allocnos = (int *) xmalloc (max_allocno * sizeof (int));
670 for (b = 0; b < n_basic_blocks; b++)
672 bzero ((char *) allocnos_live, allocno_row_words * sizeof (INT_TYPE));
674 /* Initialize table of registers currently live
675 to the state at the beginning of this basic block.
676 This also marks the conflicts among them.
678 For pseudo-regs, there is only one bit for each one
679 no matter how many hard regs it occupies.
680 This is ok; we know the size from PSEUDO_REGNO_SIZE.
681 For explicit hard regs, we cannot know the size that way
682 since one hard reg can be used with various sizes.
683 Therefore, we must require that all the hard regs
684 implicitly live as part of a multi-word hard reg
685 are explicitly marked in basic_block_live_at_start. */
688 register regset old = BASIC_BLOCK (b)->global_live_at_start;
691 REG_SET_TO_HARD_REG_SET (hard_regs_live, old);
692 EXECUTE_IF_SET_IN_REG_SET (old, FIRST_PSEUDO_REGISTER, i,
694 register int a = reg_allocno[i];
697 SET_ALLOCNO_LIVE (a);
698 block_start_allocnos[ax++] = a;
700 else if ((a = reg_renumber[i]) >= 0)
702 (a, PSEUDO_REGNO_MODE (i));
705 /* Record that each allocno now live conflicts with each other
706 allocno now live, and with each hard reg now live. */
708 record_conflicts (block_start_allocnos, ax);
712 /* Pseudos can't go in stack regs at the start of a basic block
713 that is reached by an abnormal edge. */
716 for (e = BASIC_BLOCK (b)->pred; e ; e = e->pred_next)
717 if (e->flags & EDGE_ABNORMAL)
720 for (ax = FIRST_STACK_REG; ax <= LAST_STACK_REG; ax++)
721 record_one_conflict (ax);
726 insn = BLOCK_HEAD (b);
728 /* Scan the code of this basic block, noting which allocnos
729 and hard regs are born or die. When one is born,
730 record a conflict with all others currently live. */
734 register RTX_CODE code = GET_CODE (insn);
737 /* Make regs_set an empty set. */
741 if (code == INSN || code == CALL_INSN || code == JUMP_INSN)
746 for (link = REG_NOTES (insn);
747 link && i < NUM_NO_CONFLICT_PAIRS;
748 link = XEXP (link, 1))
749 if (REG_NOTE_KIND (link) == REG_NO_CONFLICT)
751 no_conflict_pairs[i].allocno1
752 = reg_allocno[REGNO (SET_DEST (PATTERN (insn)))];
753 no_conflict_pairs[i].allocno2
754 = reg_allocno[REGNO (XEXP (link, 0))];
759 /* Mark any registers clobbered by INSN as live,
760 so they conflict with the inputs. */
762 note_stores (PATTERN (insn), mark_reg_clobber, NULL);
764 /* Mark any registers dead after INSN as dead now. */
766 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
767 if (REG_NOTE_KIND (link) == REG_DEAD)
768 mark_reg_death (XEXP (link, 0));
770 /* Mark any registers set in INSN as live,
771 and mark them as conflicting with all other live regs.
772 Clobbers are processed again, so they conflict with
773 the registers that are set. */
775 note_stores (PATTERN (insn), mark_reg_store, NULL);
778 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
779 if (REG_NOTE_KIND (link) == REG_INC)
780 mark_reg_store (XEXP (link, 0), NULL_RTX, NULL);
783 /* If INSN has multiple outputs, then any reg that dies here
784 and is used inside of an output
785 must conflict with the other outputs.
787 It is unsafe to use !single_set here since it will ignore an
788 unused output. Just because an output is unused does not mean
789 the compiler can assume the side effect will not occur.
790 Consider if REG appears in the address of an output and we
791 reload the output. If we allocate REG to the same hard
792 register as an unused output we could set the hard register
793 before the output reload insn. */
794 if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn))
795 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
796 if (REG_NOTE_KIND (link) == REG_DEAD)
798 int used_in_output = 0;
800 rtx reg = XEXP (link, 0);
802 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
804 rtx set = XVECEXP (PATTERN (insn), 0, i);
805 if (GET_CODE (set) == SET
806 && GET_CODE (SET_DEST (set)) != REG
807 && !rtx_equal_p (reg, SET_DEST (set))
808 && reg_overlap_mentioned_p (reg, SET_DEST (set)))
812 mark_reg_conflicts (reg);
815 /* Mark any registers set in INSN and then never used. */
817 while (n_regs_set > 0)
818 if (find_regno_note (insn, REG_UNUSED,
819 REGNO (regs_set[--n_regs_set])))
820 mark_reg_death (regs_set[n_regs_set]);
823 if (insn == BLOCK_END (b))
825 insn = NEXT_INSN (insn);
830 free (block_start_allocnos);
833 /* Expand the preference information by looking for cases where one allocno
834 dies in an insn that sets an allocno. If those two allocnos don't conflict,
835 merge any preferences between those allocnos. */
838 expand_preferences ()
844 /* We only try to handle the most common cases here. Most of the cases
845 where this wins are reg-reg copies. */
847 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
848 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
849 && (set = single_set (insn)) != 0
850 && GET_CODE (SET_DEST (set)) == REG
851 && reg_allocno[REGNO (SET_DEST (set))] >= 0)
852 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
853 if (REG_NOTE_KIND (link) == REG_DEAD
854 && GET_CODE (XEXP (link, 0)) == REG
855 && reg_allocno[REGNO (XEXP (link, 0))] >= 0
856 && ! CONFLICTP (reg_allocno[REGNO (SET_DEST (set))],
857 reg_allocno[REGNO (XEXP (link, 0))]))
859 int a1 = reg_allocno[REGNO (SET_DEST (set))];
860 int a2 = reg_allocno[REGNO (XEXP (link, 0))];
862 if (XEXP (link, 0) == SET_SRC (set))
864 IOR_HARD_REG_SET (hard_reg_copy_preferences[a1],
865 hard_reg_copy_preferences[a2]);
866 IOR_HARD_REG_SET (hard_reg_copy_preferences[a2],
867 hard_reg_copy_preferences[a1]);
870 IOR_HARD_REG_SET (hard_reg_preferences[a1],
871 hard_reg_preferences[a2]);
872 IOR_HARD_REG_SET (hard_reg_preferences[a2],
873 hard_reg_preferences[a1]);
874 IOR_HARD_REG_SET (hard_reg_full_preferences[a1],
875 hard_reg_full_preferences[a2]);
876 IOR_HARD_REG_SET (hard_reg_full_preferences[a2],
877 hard_reg_full_preferences[a1]);
881 /* Prune the preferences for global registers to exclude registers that cannot
884 Compute `regs_someone_prefers', which is a bitmask of the hard registers
885 that are preferred by conflicting registers of lower priority. If possible,
886 we will avoid using these registers. */
893 int *allocno_to_order = (int *) xmalloc (max_allocno * sizeof (int));
895 /* Scan least most important to most important.
896 For each allocno, remove from preferences registers that cannot be used,
897 either because of conflicts or register type. Then compute all registers
898 preferred by each lower-priority register that conflicts. */
900 for (i = max_allocno - 1; i >= 0; i--)
904 allocno = allocno_order[i];
905 allocno_to_order[allocno] = i;
906 COPY_HARD_REG_SET (temp, hard_reg_conflicts[allocno]);
908 if (allocno_calls_crossed[allocno] == 0)
909 IOR_HARD_REG_SET (temp, fixed_reg_set);
911 IOR_HARD_REG_SET (temp, call_used_reg_set);
913 IOR_COMPL_HARD_REG_SET
915 reg_class_contents[(int) reg_preferred_class (allocno_reg[allocno])]);
917 AND_COMPL_HARD_REG_SET (hard_reg_preferences[allocno], temp);
918 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[allocno], temp);
919 AND_COMPL_HARD_REG_SET (hard_reg_full_preferences[allocno], temp);
922 for (i = max_allocno - 1; i >= 0; i--)
924 /* Merge in the preferences of lower-priority registers (they have
925 already been pruned). If we also prefer some of those registers,
926 don't exclude them unless we are of a smaller size (in which case
927 we want to give the lower-priority allocno the first chance for
929 HARD_REG_SET temp, temp2;
932 allocno = allocno_order[i];
934 CLEAR_HARD_REG_SET (temp);
935 CLEAR_HARD_REG_SET (temp2);
937 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + allocno * allocno_row_words,
940 if (allocno_to_order[allocno2] > i)
942 if (allocno_size[allocno2] <= allocno_size[allocno])
943 IOR_HARD_REG_SET (temp, hard_reg_full_preferences[allocno2]);
945 IOR_HARD_REG_SET (temp2, hard_reg_full_preferences[allocno2]);
949 AND_COMPL_HARD_REG_SET (temp, hard_reg_full_preferences[allocno]);
950 IOR_HARD_REG_SET (temp, temp2);
951 COPY_HARD_REG_SET (regs_someone_prefers[allocno], temp);
953 free (allocno_to_order);
956 /* Assign a hard register to ALLOCNO; look for one that is the beginning
957 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
958 The registers marked in PREFREGS are tried first.
960 LOSERS, if non-zero, is a HARD_REG_SET indicating registers that cannot
961 be used for this allocation.
963 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
964 Otherwise ignore that preferred class and use the alternate class.
966 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
967 will have to be saved and restored at calls.
969 RETRYING is nonzero if this is called from retry_global_alloc.
971 If we find one, record it in reg_renumber.
972 If not, do nothing. */
975 find_reg (allocno, losers, alt_regs_p, accept_call_clobbered, retrying)
979 int accept_call_clobbered;
982 register int i, best_reg, pass;
984 register /* Declare it register if it's a scalar. */
986 HARD_REG_SET used, used1, used2;
988 enum reg_class class = (alt_regs_p
989 ? reg_alternate_class (allocno_reg[allocno])
990 : reg_preferred_class (allocno_reg[allocno]));
991 enum machine_mode mode = PSEUDO_REGNO_MODE (allocno_reg[allocno]);
993 if (accept_call_clobbered)
994 COPY_HARD_REG_SET (used1, call_fixed_reg_set);
995 else if (allocno_calls_crossed[allocno] == 0)
996 COPY_HARD_REG_SET (used1, fixed_reg_set);
998 COPY_HARD_REG_SET (used1, call_used_reg_set);
1000 /* Some registers should not be allocated in global-alloc. */
1001 IOR_HARD_REG_SET (used1, no_global_alloc_regs);
1003 IOR_HARD_REG_SET (used1, losers);
1005 IOR_COMPL_HARD_REG_SET (used1, reg_class_contents[(int) class]);
1006 COPY_HARD_REG_SET (used2, used1);
1008 IOR_HARD_REG_SET (used1, hard_reg_conflicts[allocno]);
1010 #ifdef CLASS_CANNOT_CHANGE_SIZE
1011 if (REG_CHANGES_SIZE (allocno_reg[allocno]))
1012 IOR_HARD_REG_SET (used1,
1013 reg_class_contents[(int) CLASS_CANNOT_CHANGE_SIZE]);
1016 /* Try each hard reg to see if it fits. Do this in two passes.
1017 In the first pass, skip registers that are preferred by some other pseudo
1018 to give it a better chance of getting one of those registers. Only if
1019 we can't get a register when excluding those do we take one of them.
1020 However, we never allocate a register for the first time in pass 0. */
1022 COPY_HARD_REG_SET (used, used1);
1023 IOR_COMPL_HARD_REG_SET (used, regs_used_so_far);
1024 IOR_HARD_REG_SET (used, regs_someone_prefers[allocno]);
1027 for (i = FIRST_PSEUDO_REGISTER, pass = 0;
1028 pass <= 1 && i >= FIRST_PSEUDO_REGISTER;
1032 COPY_HARD_REG_SET (used, used1);
1033 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1035 #ifdef REG_ALLOC_ORDER
1036 int regno = reg_alloc_order[i];
1040 if (! TEST_HARD_REG_BIT (used, regno)
1041 && HARD_REGNO_MODE_OK (regno, mode)
1042 && (allocno_calls_crossed[allocno] == 0
1043 || accept_call_clobbered
1044 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
1047 register int lim = regno + HARD_REGNO_NREGS (regno, mode);
1050 && ! TEST_HARD_REG_BIT (used, j));
1057 #ifndef REG_ALLOC_ORDER
1058 i = j; /* Skip starting points we know will lose */
1064 /* See if there is a preferred register with the same class as the register
1065 we allocated above. Making this restriction prevents register
1066 preferencing from creating worse register allocation.
1068 Remove from the preferred registers and conflicting registers. Note that
1069 additional conflicts may have been added after `prune_preferences' was
1072 First do this for those register with copy preferences, then all
1073 preferred registers. */
1075 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[allocno], used);
1076 GO_IF_HARD_REG_SUBSET (hard_reg_copy_preferences[allocno],
1077 reg_class_contents[(int) NO_REGS], no_copy_prefs);
1081 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1082 if (TEST_HARD_REG_BIT (hard_reg_copy_preferences[allocno], i)
1083 && HARD_REGNO_MODE_OK (i, mode)
1084 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1085 || reg_class_subset_p (REGNO_REG_CLASS (i),
1086 REGNO_REG_CLASS (best_reg))
1087 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1088 REGNO_REG_CLASS (i))))
1091 register int lim = i + HARD_REGNO_NREGS (i, mode);
1094 && ! TEST_HARD_REG_BIT (used, j)
1095 && (REGNO_REG_CLASS (j)
1096 == REGNO_REG_CLASS (best_reg + (j - i))
1097 || reg_class_subset_p (REGNO_REG_CLASS (j),
1098 REGNO_REG_CLASS (best_reg + (j - i)))
1099 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1100 REGNO_REG_CLASS (j))));
1111 AND_COMPL_HARD_REG_SET (hard_reg_preferences[allocno], used);
1112 GO_IF_HARD_REG_SUBSET (hard_reg_preferences[allocno],
1113 reg_class_contents[(int) NO_REGS], no_prefs);
1117 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1118 if (TEST_HARD_REG_BIT (hard_reg_preferences[allocno], i)
1119 && HARD_REGNO_MODE_OK (i, mode)
1120 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1121 || reg_class_subset_p (REGNO_REG_CLASS (i),
1122 REGNO_REG_CLASS (best_reg))
1123 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1124 REGNO_REG_CLASS (i))))
1127 register int lim = i + HARD_REGNO_NREGS (i, mode);
1130 && ! TEST_HARD_REG_BIT (used, j)
1131 && (REGNO_REG_CLASS (j)
1132 == REGNO_REG_CLASS (best_reg + (j - i))
1133 || reg_class_subset_p (REGNO_REG_CLASS (j),
1134 REGNO_REG_CLASS (best_reg + (j - i)))
1135 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1136 REGNO_REG_CLASS (j))));
1147 /* If we haven't succeeded yet, try with caller-saves.
1148 We need not check to see if the current function has nonlocal
1149 labels because we don't put any pseudos that are live over calls in
1150 registers in that case. */
1152 if (flag_caller_saves && best_reg < 0)
1154 /* Did not find a register. If it would be profitable to
1155 allocate a call-clobbered register and save and restore it
1156 around calls, do that. */
1157 if (! accept_call_clobbered
1158 && allocno_calls_crossed[allocno] != 0
1159 && CALLER_SAVE_PROFITABLE (allocno_n_refs[allocno],
1160 allocno_calls_crossed[allocno]))
1162 HARD_REG_SET new_losers;
1164 CLEAR_HARD_REG_SET (new_losers);
1166 COPY_HARD_REG_SET (new_losers, losers);
1168 IOR_HARD_REG_SET(new_losers, losing_caller_save_reg_set);
1169 find_reg (allocno, new_losers, alt_regs_p, 1, retrying);
1170 if (reg_renumber[allocno_reg[allocno]] >= 0)
1172 caller_save_needed = 1;
1178 /* If we haven't succeeded yet,
1179 see if some hard reg that conflicts with us
1180 was utilized poorly by local-alloc.
1181 If so, kick out the regs that were put there by local-alloc
1182 so we can use it instead. */
1183 if (best_reg < 0 && !retrying
1184 /* Let's not bother with multi-reg allocnos. */
1185 && allocno_size[allocno] == 1)
1187 /* Count from the end, to find the least-used ones first. */
1188 for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1190 #ifdef REG_ALLOC_ORDER
1191 int regno = reg_alloc_order[i];
1196 if (local_reg_n_refs[regno] != 0
1197 /* Don't use a reg no good for this pseudo. */
1198 && ! TEST_HARD_REG_BIT (used2, regno)
1199 && HARD_REGNO_MODE_OK (regno, mode)
1200 #ifdef CLASS_CANNOT_CHANGE_SIZE
1201 && ! (REG_CHANGES_SIZE (allocno_reg[allocno])
1202 && (TEST_HARD_REG_BIT
1203 (reg_class_contents[(int) CLASS_CANNOT_CHANGE_SIZE],
1208 /* We explicitly evaluate the divide results into temporary
1209 variables so as to avoid excess precision problems that occur
1210 on a i386-unknown-sysv4.2 (unixware) host. */
1212 double tmp1 = ((double) local_reg_n_refs[regno]
1213 / local_reg_live_length[regno]);
1214 double tmp2 = ((double) allocno_n_refs[allocno]
1215 / allocno_live_length[allocno]);
1219 /* Hard reg REGNO was used less in total by local regs
1220 than it would be used by this one allocno! */
1222 for (k = 0; k < max_regno; k++)
1223 if (reg_renumber[k] >= 0)
1225 int r = reg_renumber[k];
1227 = r + HARD_REGNO_NREGS (r, PSEUDO_REGNO_MODE (k));
1229 if (regno >= r && regno < endregno)
1230 reg_renumber[k] = -1;
1240 /* Did we find a register? */
1244 register int lim, j;
1245 HARD_REG_SET this_reg;
1247 /* Yes. Record it as the hard register of this pseudo-reg. */
1248 reg_renumber[allocno_reg[allocno]] = best_reg;
1249 /* Also of any pseudo-regs that share with it. */
1250 if (reg_may_share[allocno_reg[allocno]])
1251 for (j = FIRST_PSEUDO_REGISTER; j < max_regno; j++)
1252 if (reg_allocno[j] == allocno)
1253 reg_renumber[j] = best_reg;
1255 /* Make a set of the hard regs being allocated. */
1256 CLEAR_HARD_REG_SET (this_reg);
1257 lim = best_reg + HARD_REGNO_NREGS (best_reg, mode);
1258 for (j = best_reg; j < lim; j++)
1260 SET_HARD_REG_BIT (this_reg, j);
1261 SET_HARD_REG_BIT (regs_used_so_far, j);
1262 /* This is no longer a reg used just by local regs. */
1263 local_reg_n_refs[j] = 0;
1265 /* For each other pseudo-reg conflicting with this one,
1266 mark it as conflicting with the hard regs this one occupies. */
1268 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + lim * allocno_row_words, j,
1270 IOR_HARD_REG_SET (hard_reg_conflicts[j], this_reg);
1275 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1276 Perhaps it had previously seemed not worth a hard reg,
1277 or perhaps its old hard reg has been commandeered for reloads.
1278 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1279 they do not appear to be allocated.
1280 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1283 retry_global_alloc (regno, forbidden_regs)
1285 HARD_REG_SET forbidden_regs;
1287 int allocno = reg_allocno[regno];
1290 /* If we have more than one register class,
1291 first try allocating in the class that is cheapest
1292 for this pseudo-reg. If that fails, try any reg. */
1293 if (N_REG_CLASSES > 1)
1294 find_reg (allocno, forbidden_regs, 0, 0, 1);
1295 if (reg_renumber[regno] < 0
1296 && reg_alternate_class (regno) != NO_REGS)
1297 find_reg (allocno, forbidden_regs, 1, 0, 1);
1299 /* If we found a register, modify the RTL for the register to
1300 show the hard register, and mark that register live. */
1301 if (reg_renumber[regno] >= 0)
1303 REGNO (regno_reg_rtx[regno]) = reg_renumber[regno];
1304 mark_home_live (regno);
1309 /* Record a conflict between register REGNO
1310 and everything currently live.
1311 REGNO must not be a pseudo reg that was allocated
1312 by local_alloc; such numbers must be translated through
1313 reg_renumber before calling here. */
1316 record_one_conflict (regno)
1321 if (regno < FIRST_PSEUDO_REGISTER)
1322 /* When a hard register becomes live,
1323 record conflicts with live pseudo regs. */
1324 EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live, j,
1326 SET_HARD_REG_BIT (hard_reg_conflicts[j], regno);
1329 /* When a pseudo-register becomes live,
1330 record conflicts first with hard regs,
1331 then with other pseudo regs. */
1333 register int ialloc = reg_allocno[regno];
1334 register int ialloc_prod = ialloc * allocno_row_words;
1335 IOR_HARD_REG_SET (hard_reg_conflicts[ialloc], hard_regs_live);
1336 for (j = allocno_row_words - 1; j >= 0; j--)
1340 for (k = 0; k < n_no_conflict_pairs; k++)
1341 if (! ((j == no_conflict_pairs[k].allocno1
1342 && ialloc == no_conflict_pairs[k].allocno2)
1344 (j == no_conflict_pairs[k].allocno2
1345 && ialloc == no_conflict_pairs[k].allocno1)))
1347 conflicts[ialloc_prod + j] |= allocnos_live[j];
1352 /* Record all allocnos currently live as conflicting
1353 with each other and with all hard regs currently live.
1354 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1355 are currently live. Their bits are also flagged in allocnos_live. */
1358 record_conflicts (allocno_vec, len)
1359 register int *allocno_vec;
1362 register int allocno;
1364 register int ialloc_prod;
1368 allocno = allocno_vec[len];
1369 ialloc_prod = allocno * allocno_row_words;
1370 IOR_HARD_REG_SET (hard_reg_conflicts[allocno], hard_regs_live);
1371 for (j = allocno_row_words - 1; j >= 0; j--)
1372 conflicts[ialloc_prod + j] |= allocnos_live[j];
1376 /* If CONFLICTP (i, j) is true, make sure CONFLICTP (j, i) is also true. */
1381 int rw = allocno_row_words;
1382 int rwb = rw * INT_BITS;
1383 INT_TYPE *p = conflicts;
1384 INT_TYPE *q0 = conflicts, *q1, *q2;
1385 unsigned INT_TYPE mask;
1387 for (i = max_allocno - 1, mask = 1; i >= 0; i--, mask <<= 1)
1394 for (j = allocno_row_words - 1, q1 = q0; j >= 0; j--, q1 += rwb)
1396 unsigned INT_TYPE word;
1398 for (word = (unsigned INT_TYPE) *p++, q2 = q1; word;
1399 word >>= 1, q2 += rw)
1408 /* Handle the case where REG is set by the insn being scanned,
1409 during the forward scan to accumulate conflicts.
1410 Store a 1 in regs_live or allocnos_live for this register, record how many
1411 consecutive hardware registers it actually needs,
1412 and record a conflict with all other registers already live.
1414 Note that even if REG does not remain alive after this insn,
1415 we must mark it here as live, to ensure a conflict between
1416 REG and any other regs set in this insn that really do live.
1417 This is because those other regs could be considered after this.
1419 REG might actually be something other than a register;
1420 if so, we do nothing.
1422 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1423 a REG_INC note was found for it). */
1426 mark_reg_store (reg, setter, data)
1428 void *data ATTRIBUTE_UNUSED;
1432 /* WORD is which word of a multi-register group is being stored.
1433 For the case where the store is actually into a SUBREG of REG.
1434 Except we don't use it; I believe the entire REG needs to be
1438 if (GET_CODE (reg) == SUBREG)
1440 word = SUBREG_WORD (reg);
1441 reg = SUBREG_REG (reg);
1444 if (GET_CODE (reg) != REG)
1447 regs_set[n_regs_set++] = reg;
1449 if (setter && GET_CODE (setter) != CLOBBER)
1450 set_preference (reg, SET_SRC (setter));
1452 regno = REGNO (reg);
1454 /* Either this is one of the max_allocno pseudo regs not allocated,
1455 or it is or has a hardware reg. First handle the pseudo-regs. */
1456 if (regno >= FIRST_PSEUDO_REGISTER)
1458 if (reg_allocno[regno] >= 0)
1460 SET_ALLOCNO_LIVE (reg_allocno[regno]);
1461 record_one_conflict (regno);
1465 if (reg_renumber[regno] >= 0)
1466 regno = reg_renumber[regno] /* + word */;
1468 /* Handle hardware regs (and pseudos allocated to hard regs). */
1469 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1471 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1472 while (regno < last)
1474 record_one_conflict (regno);
1475 SET_HARD_REG_BIT (hard_regs_live, regno);
1481 /* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
1484 mark_reg_clobber (reg, setter, data)
1486 void *data ATTRIBUTE_UNUSED;
1488 if (GET_CODE (setter) == CLOBBER)
1489 mark_reg_store (reg, setter, data);
1492 /* Record that REG has conflicts with all the regs currently live.
1493 Do not mark REG itself as live. */
1496 mark_reg_conflicts (reg)
1501 if (GET_CODE (reg) == SUBREG)
1502 reg = SUBREG_REG (reg);
1504 if (GET_CODE (reg) != REG)
1507 regno = REGNO (reg);
1509 /* Either this is one of the max_allocno pseudo regs not allocated,
1510 or it is or has a hardware reg. First handle the pseudo-regs. */
1511 if (regno >= FIRST_PSEUDO_REGISTER)
1513 if (reg_allocno[regno] >= 0)
1514 record_one_conflict (regno);
1517 if (reg_renumber[regno] >= 0)
1518 regno = reg_renumber[regno];
1520 /* Handle hardware regs (and pseudos allocated to hard regs). */
1521 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1523 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1524 while (regno < last)
1526 record_one_conflict (regno);
1532 /* Mark REG as being dead (following the insn being scanned now).
1533 Store a 0 in regs_live or allocnos_live for this register. */
1536 mark_reg_death (reg)
1539 register int regno = REGNO (reg);
1541 /* Either this is one of the max_allocno pseudo regs not allocated,
1542 or it is a hardware reg. First handle the pseudo-regs. */
1543 if (regno >= FIRST_PSEUDO_REGISTER)
1545 if (reg_allocno[regno] >= 0)
1546 CLEAR_ALLOCNO_LIVE (reg_allocno[regno]);
1549 /* For pseudo reg, see if it has been assigned a hardware reg. */
1550 if (reg_renumber[regno] >= 0)
1551 regno = reg_renumber[regno];
1553 /* Handle hardware regs (and pseudos allocated to hard regs). */
1554 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1556 /* Pseudo regs already assigned hardware regs are treated
1557 almost the same as explicit hardware regs. */
1558 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1559 while (regno < last)
1561 CLEAR_HARD_REG_BIT (hard_regs_live, regno);
1567 /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1568 for the value stored in it. MODE determines how many consecutive
1569 registers are actually in use. Do not record conflicts;
1570 it is assumed that the caller will do that. */
1573 mark_reg_live_nc (regno, mode)
1575 enum machine_mode mode;
1577 register int last = regno + HARD_REGNO_NREGS (regno, mode);
1578 while (regno < last)
1580 SET_HARD_REG_BIT (hard_regs_live, regno);
1585 /* Try to set a preference for an allocno to a hard register.
1586 We are passed DEST and SRC which are the operands of a SET. It is known
1587 that SRC is a register. If SRC or the first operand of SRC is a register,
1588 try to set a preference. If one of the two is a hard register and the other
1589 is a pseudo-register, mark the preference.
1591 Note that we are not as aggressive as local-alloc in trying to tie a
1592 pseudo-register to a hard register. */
1595 set_preference (dest, src)
1598 int src_regno, dest_regno;
1599 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1600 to compensate for subregs in SRC or DEST. */
1605 if (GET_RTX_FORMAT (GET_CODE (src))[0] == 'e')
1606 src = XEXP (src, 0), copy = 0;
1608 /* Get the reg number for both SRC and DEST.
1609 If neither is a reg, give up. */
1611 if (GET_CODE (src) == REG)
1612 src_regno = REGNO (src);
1613 else if (GET_CODE (src) == SUBREG && GET_CODE (SUBREG_REG (src)) == REG)
1615 src_regno = REGNO (SUBREG_REG (src));
1616 offset += SUBREG_WORD (src);
1621 if (GET_CODE (dest) == REG)
1622 dest_regno = REGNO (dest);
1623 else if (GET_CODE (dest) == SUBREG && GET_CODE (SUBREG_REG (dest)) == REG)
1625 dest_regno = REGNO (SUBREG_REG (dest));
1626 offset -= SUBREG_WORD (dest);
1631 /* Convert either or both to hard reg numbers. */
1633 if (reg_renumber[src_regno] >= 0)
1634 src_regno = reg_renumber[src_regno];
1636 if (reg_renumber[dest_regno] >= 0)
1637 dest_regno = reg_renumber[dest_regno];
1639 /* Now if one is a hard reg and the other is a global pseudo
1640 then give the other a preference. */
1642 if (dest_regno < FIRST_PSEUDO_REGISTER && src_regno >= FIRST_PSEUDO_REGISTER
1643 && reg_allocno[src_regno] >= 0)
1645 dest_regno -= offset;
1646 if (dest_regno >= 0 && dest_regno < FIRST_PSEUDO_REGISTER)
1649 SET_REGBIT (hard_reg_copy_preferences,
1650 reg_allocno[src_regno], dest_regno);
1652 SET_REGBIT (hard_reg_preferences,
1653 reg_allocno[src_regno], dest_regno);
1654 for (i = dest_regno;
1655 i < dest_regno + HARD_REGNO_NREGS (dest_regno, GET_MODE (dest));
1657 SET_REGBIT (hard_reg_full_preferences, reg_allocno[src_regno], i);
1661 if (src_regno < FIRST_PSEUDO_REGISTER && dest_regno >= FIRST_PSEUDO_REGISTER
1662 && reg_allocno[dest_regno] >= 0)
1664 src_regno += offset;
1665 if (src_regno >= 0 && src_regno < FIRST_PSEUDO_REGISTER)
1668 SET_REGBIT (hard_reg_copy_preferences,
1669 reg_allocno[dest_regno], src_regno);
1671 SET_REGBIT (hard_reg_preferences,
1672 reg_allocno[dest_regno], src_regno);
1674 i < src_regno + HARD_REGNO_NREGS (src_regno, GET_MODE (src));
1676 SET_REGBIT (hard_reg_full_preferences, reg_allocno[dest_regno], i);
1681 /* Indicate that hard register number FROM was eliminated and replaced with
1682 an offset from hard register number TO. The status of hard registers live
1683 at the start of a basic block is updated by replacing a use of FROM with
1687 mark_elimination (from, to)
1692 for (i = 0; i < n_basic_blocks; i++)
1694 register regset r = BASIC_BLOCK (i)->global_live_at_start;
1695 if (REGNO_REG_SET_P (r, from))
1697 CLEAR_REGNO_REG_SET (r, from);
1698 SET_REGNO_REG_SET (r, to);
1703 /* Used for communication between the following functions. Holds the
1704 current life information. */
1705 static regset live_relevant_regs;
1707 /* Record in live_relevant_regs that register REG became live. This
1708 is called via note_stores. */
1710 reg_becomes_live (reg, setter, data)
1712 rtx setter ATTRIBUTE_UNUSED;
1713 void *data ATTRIBUTE_UNUSED;
1717 if (GET_CODE (reg) == SUBREG)
1718 reg = SUBREG_REG (reg);
1720 if (GET_CODE (reg) != REG)
1723 regno = REGNO (reg);
1724 if (regno < FIRST_PSEUDO_REGISTER)
1726 int nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg));
1728 SET_REGNO_REG_SET (live_relevant_regs, regno++);
1730 else if (reg_renumber[regno] >= 0)
1731 SET_REGNO_REG_SET (live_relevant_regs, regno);
1734 /* Record in live_relevant_regs that register REGNO died. */
1736 reg_dies (regno, mode)
1738 enum machine_mode mode;
1740 if (regno < FIRST_PSEUDO_REGISTER)
1742 int nregs = HARD_REGNO_NREGS (regno, mode);
1744 CLEAR_REGNO_REG_SET (live_relevant_regs, regno++);
1747 CLEAR_REGNO_REG_SET (live_relevant_regs, regno);
1750 /* Walk the insns of the current function and build reload_insn_chain,
1751 and record register life information. */
1753 build_insn_chain (first)
1756 struct insn_chain **p = &reload_insn_chain;
1757 struct insn_chain *prev = 0;
1760 live_relevant_regs = ALLOCA_REG_SET ();
1762 for (; first; first = NEXT_INSN (first))
1764 struct insn_chain *c;
1766 if (first == BLOCK_HEAD (b))
1770 CLEAR_REG_SET (live_relevant_regs);
1772 EXECUTE_IF_SET_IN_BITMAP
1773 (BASIC_BLOCK (b)->global_live_at_start, 0, i,
1775 if (i < FIRST_PSEUDO_REGISTER
1776 ? ! TEST_HARD_REG_BIT (eliminable_regset, i)
1777 : reg_renumber[i] >= 0)
1778 SET_REGNO_REG_SET (live_relevant_regs, i);
1782 if (GET_CODE (first) != NOTE && GET_CODE (first) != BARRIER)
1784 c = new_insn_chain ();
1792 COPY_REG_SET (c->live_before, live_relevant_regs);
1794 if (GET_RTX_CLASS (GET_CODE (first)) == 'i')
1798 /* Mark the death of everything that dies in this instruction. */
1800 for (link = REG_NOTES (first); link; link = XEXP (link, 1))
1801 if (REG_NOTE_KIND (link) == REG_DEAD
1802 && GET_CODE (XEXP (link, 0)) == REG)
1803 reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)));
1805 /* Mark everything born in this instruction as live. */
1807 note_stores (PATTERN (first), reg_becomes_live, NULL);
1810 /* Remember which registers are live at the end of the insn, before
1811 killing those with REG_UNUSED notes. */
1812 COPY_REG_SET (c->live_after, live_relevant_regs);
1814 if (GET_RTX_CLASS (GET_CODE (first)) == 'i')
1818 /* Mark anything that is set in this insn and then unused as dying. */
1820 for (link = REG_NOTES (first); link; link = XEXP (link, 1))
1821 if (REG_NOTE_KIND (link) == REG_UNUSED
1822 && GET_CODE (XEXP (link, 0)) == REG)
1823 reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)));
1827 if (first == BLOCK_END (b))
1830 /* Stop after we pass the end of the last basic block. Verify that
1831 no real insns are after the end of the last basic block.
1833 We may want to reorganize the loop somewhat since this test should
1834 always be the right exit test. */
1835 if (b == n_basic_blocks)
1837 for (first = NEXT_INSN (first) ; first; first = NEXT_INSN (first))
1838 if (GET_RTX_CLASS (GET_CODE (first)) == 'i'
1839 && GET_CODE (PATTERN (first)) != USE)
1844 FREE_REG_SET (live_relevant_regs);
1848 /* Print debugging trace information if -dg switch is given,
1849 showing the information on which the allocation decisions are based. */
1852 dump_conflicts (file)
1856 register int has_preferences;
1859 for (i = 0; i < max_allocno; i++)
1861 if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
1865 fprintf (file, ";; %d regs to allocate:", nregs);
1866 for (i = 0; i < max_allocno; i++)
1869 if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
1871 fprintf (file, " %d", allocno_reg[allocno_order[i]]);
1872 for (j = 0; j < max_regno; j++)
1873 if (reg_allocno[j] == allocno_order[i]
1874 && j != allocno_reg[allocno_order[i]])
1875 fprintf (file, "+%d", j);
1876 if (allocno_size[allocno_order[i]] != 1)
1877 fprintf (file, " (%d)", allocno_size[allocno_order[i]]);
1879 fprintf (file, "\n");
1881 for (i = 0; i < max_allocno; i++)
1884 fprintf (file, ";; %d conflicts:", allocno_reg[i]);
1885 for (j = 0; j < max_allocno; j++)
1886 if (CONFLICTP (j, i))
1887 fprintf (file, " %d", allocno_reg[j]);
1888 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1889 if (TEST_HARD_REG_BIT (hard_reg_conflicts[i], j))
1890 fprintf (file, " %d", j);
1891 fprintf (file, "\n");
1893 has_preferences = 0;
1894 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1895 if (TEST_HARD_REG_BIT (hard_reg_preferences[i], j))
1896 has_preferences = 1;
1898 if (! has_preferences)
1900 fprintf (file, ";; %d preferences:", allocno_reg[i]);
1901 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1902 if (TEST_HARD_REG_BIT (hard_reg_preferences[i], j))
1903 fprintf (file, " %d", j);
1904 fprintf (file, "\n");
1906 fprintf (file, "\n");
1910 dump_global_regs (file)
1915 fprintf (file, ";; Register dispositions:\n");
1916 for (i = FIRST_PSEUDO_REGISTER, j = 0; i < max_regno; i++)
1917 if (reg_renumber[i] >= 0)
1919 fprintf (file, "%d in %d ", i, reg_renumber[i]);
1921 fprintf (file, "\n");
1924 fprintf (file, "\n\n;; Hard regs used: ");
1925 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1926 if (regs_ever_live[i])
1927 fprintf (file, " %d", i);
1928 fprintf (file, "\n\n");