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 /* For any allocno that conflicts with IN_ALLOCNO, set OUT_ALLOCNO to
158 the conflicting allocno, and execute CODE. This macro assumes that
159 mirror_conflicts has been run. */
160 #define EXECUTE_IF_CONFLICT(IN_ALLOCNO, OUT_ALLOCNO, CODE)\
161 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + (IN_ALLOCNO) * allocno_row_words,\
164 /* Set of hard regs currently live (during scan of all insns). */
166 static HARD_REG_SET hard_regs_live;
168 /* Indexed by N, set of hard regs conflicting with allocno N. */
170 static HARD_REG_SET *hard_reg_conflicts;
172 /* Indexed by N, set of hard regs preferred by allocno N.
173 This is used to make allocnos go into regs that are copied to or from them,
174 when possible, to reduce register shuffling. */
176 static HARD_REG_SET *hard_reg_preferences;
178 /* Similar, but just counts register preferences made in simple copy
179 operations, rather than arithmetic. These are given priority because
180 we can always eliminate an insn by using these, but using a register
181 in the above list won't always eliminate an insn. */
183 static HARD_REG_SET *hard_reg_copy_preferences;
185 /* Similar to hard_reg_preferences, but includes bits for subsequent
186 registers when an allocno is multi-word. The above variable is used for
187 allocation while this is used to build reg_someone_prefers, below. */
189 static HARD_REG_SET *hard_reg_full_preferences;
191 /* Indexed by N, set of hard registers that some later allocno has a
194 static HARD_REG_SET *regs_someone_prefers;
196 /* Set of registers that global-alloc isn't supposed to use. */
198 static HARD_REG_SET no_global_alloc_regs;
200 /* Set of registers used so far. */
202 static HARD_REG_SET regs_used_so_far;
204 /* Number of calls crossed by each allocno. */
206 static int *allocno_calls_crossed;
208 /* Number of refs (weighted) to each allocno. */
210 static int *allocno_n_refs;
212 /* Guess at live length of each allocno.
213 This is actually the max of the live lengths of the regs. */
215 static int *allocno_live_length;
217 /* Number of refs (weighted) to each hard reg, as used by local alloc.
218 It is zero for a reg that contains global pseudos or is explicitly used. */
220 static int local_reg_n_refs[FIRST_PSEUDO_REGISTER];
222 /* Guess at live length of each hard reg, as used by local alloc.
223 This is actually the sum of the live lengths of the specific regs. */
225 static int local_reg_live_length[FIRST_PSEUDO_REGISTER];
227 /* Test a bit in TABLE, a vector of HARD_REG_SETs,
228 for vector element I, and hard register number J. */
230 #define REGBITP(TABLE, I, J) TEST_HARD_REG_BIT (TABLE[I], J)
232 /* Set to 1 a bit in a vector of HARD_REG_SETs. Works like REGBITP. */
234 #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (TABLE[I], J)
236 /* Bit mask for allocnos live at current point in the scan. */
238 static INT_TYPE *allocnos_live;
240 /* Test, set or clear bit number I in allocnos_live,
241 a bit vector indexed by allocno. */
243 #define ALLOCNO_LIVE_P(I) \
244 (allocnos_live[(unsigned)(I) / INT_BITS] \
245 & ((INT_TYPE) 1 << ((unsigned)(I) % INT_BITS)))
247 #define SET_ALLOCNO_LIVE(I) \
248 (allocnos_live[(unsigned)(I) / INT_BITS] \
249 |= ((INT_TYPE) 1 << ((unsigned)(I) % INT_BITS)))
251 #define CLEAR_ALLOCNO_LIVE(I) \
252 (allocnos_live[(unsigned)(I) / INT_BITS] \
253 &= ~((INT_TYPE) 1 << ((unsigned)(I) % INT_BITS)))
255 /* This is turned off because it doesn't work right for DImode.
256 (And it is only used for DImode, so the other cases are worthless.)
257 The problem is that it isn't true that there is NO possibility of conflict;
258 only that there is no conflict if the two pseudos get the exact same regs.
259 If they were allocated with a partial overlap, there would be a conflict.
260 We can't safely turn off the conflict unless we have another way to
261 prevent the partial overlap.
263 Idea: change hard_reg_conflicts so that instead of recording which
264 hard regs the allocno may not overlap, it records where the allocno
265 may not start. Change both where it is used and where it is updated.
266 Then there is a way to record that (reg:DI 108) may start at 10
267 but not at 9 or 11. There is still the question of how to record
268 this semi-conflict between two pseudos. */
270 /* Reg pairs for which conflict after the current insn
271 is inhibited by a REG_NO_CONFLICT note.
272 If the table gets full, we ignore any other notes--that is conservative. */
273 #define NUM_NO_CONFLICT_PAIRS 4
274 /* Number of pairs in use in this insn. */
275 int n_no_conflict_pairs;
276 static struct { int allocno1, allocno2;}
277 no_conflict_pairs[NUM_NO_CONFLICT_PAIRS];
280 /* Record all regs that are set in any one insn.
281 Communication from mark_reg_{store,clobber} and global_conflicts. */
283 static rtx *regs_set;
284 static int n_regs_set;
286 /* All registers that can be eliminated. */
288 static HARD_REG_SET eliminable_regset;
290 static int allocno_compare PROTO((const PTR, const PTR));
291 static void global_conflicts PROTO((void));
292 static void mirror_conflicts PROTO((void));
293 static void expand_preferences PROTO((void));
294 static void prune_preferences PROTO((void));
295 static void find_reg PROTO((int, HARD_REG_SET, int, int, int));
296 static void record_one_conflict PROTO((int));
297 static void record_conflicts PROTO((int *, int));
298 static void mark_reg_store PROTO((rtx, rtx, void *));
299 static void mark_reg_clobber PROTO((rtx, rtx, void *));
300 static void mark_reg_conflicts PROTO((rtx));
301 static void mark_reg_death PROTO((rtx));
302 static void mark_reg_live_nc PROTO((int, enum machine_mode));
303 static void set_preference PROTO((rtx, rtx));
304 static void dump_conflicts PROTO((FILE *));
305 static void reg_becomes_live PROTO((rtx, rtx, void *));
306 static void reg_dies PROTO((int, enum machine_mode));
307 static void build_insn_chain PROTO((rtx));
309 /* Perform allocation of pseudo-registers not allocated by local_alloc.
310 FILE is a file to output debugging information on,
311 or zero if such output is not desired.
313 Return value is nonzero if reload failed
314 and we must not do any more for this function. */
321 #ifdef ELIMINABLE_REGS
322 static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
325 = (! flag_omit_frame_pointer
326 #ifdef EXIT_IGNORE_STACK
327 || (current_function_calls_alloca && EXIT_IGNORE_STACK)
329 || FRAME_POINTER_REQUIRED);
336 /* A machine may have certain hard registers that
337 are safe to use only within a basic block. */
339 CLEAR_HARD_REG_SET (no_global_alloc_regs);
340 #ifdef OVERLAPPING_REGNO_P
341 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
342 if (OVERLAPPING_REGNO_P (i))
343 SET_HARD_REG_BIT (no_global_alloc_regs, i);
346 /* Build the regset of all eliminable registers and show we can't use those
347 that we already know won't be eliminated. */
348 #ifdef ELIMINABLE_REGS
349 for (i = 0; i < sizeof eliminables / sizeof eliminables[0]; i++)
351 SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from);
353 if (! CAN_ELIMINATE (eliminables[i].from, eliminables[i].to)
354 || (eliminables[i].to == STACK_POINTER_REGNUM && need_fp))
355 SET_HARD_REG_BIT (no_global_alloc_regs, eliminables[i].from);
357 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
358 SET_HARD_REG_BIT (eliminable_regset, HARD_FRAME_POINTER_REGNUM);
360 SET_HARD_REG_BIT (no_global_alloc_regs, HARD_FRAME_POINTER_REGNUM);
364 SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM);
366 SET_HARD_REG_BIT (no_global_alloc_regs, FRAME_POINTER_REGNUM);
369 /* Track which registers have already been used. Start with registers
370 explicitly in the rtl, then registers allocated by local register
373 CLEAR_HARD_REG_SET (regs_used_so_far);
374 #ifdef LEAF_REGISTERS
375 /* If we are doing the leaf function optimization, and this is a leaf
376 function, it means that the registers that take work to save are those
377 that need a register window. So prefer the ones that can be used in
381 static char leaf_regs[] = LEAF_REGISTERS;
383 if (only_leaf_regs_used () && leaf_function_p ())
384 cheap_regs = leaf_regs;
386 cheap_regs = call_used_regs;
387 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
388 if (regs_ever_live[i] || cheap_regs[i])
389 SET_HARD_REG_BIT (regs_used_so_far, i);
392 /* We consider registers that do not have to be saved over calls as if
393 they were already used since there is no cost in using them. */
394 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
395 if (regs_ever_live[i] || call_used_regs[i])
396 SET_HARD_REG_BIT (regs_used_so_far, i);
399 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
400 if (reg_renumber[i] >= 0)
401 SET_HARD_REG_BIT (regs_used_so_far, reg_renumber[i]);
403 /* Establish mappings from register number to allocation number
404 and vice versa. In the process, count the allocnos. */
406 reg_allocno = (int *) xmalloc (max_regno * sizeof (int));
408 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
411 /* Initialize the shared-hard-reg mapping
412 from the list of pairs that may share. */
413 reg_may_share = (int *) xcalloc (max_regno, sizeof (int));
414 for (x = regs_may_share; x; x = XEXP (XEXP (x, 1), 1))
416 int r1 = REGNO (XEXP (x, 0));
417 int r2 = REGNO (XEXP (XEXP (x, 1), 0));
419 reg_may_share[r1] = r2;
421 reg_may_share[r2] = r1;
424 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
425 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
426 that we are supposed to refrain from putting in a hard reg.
427 -2 means do make an allocno but don't allocate it. */
428 if (REG_N_REFS (i) != 0 && REG_LIVE_LENGTH (i) != -1
429 /* Don't allocate pseudos that cross calls,
430 if this function receives a nonlocal goto. */
431 && (! current_function_has_nonlocal_label
432 || REG_N_CALLS_CROSSED (i) == 0))
434 if (reg_renumber[i] < 0 && reg_may_share[i] && reg_allocno[reg_may_share[i]] >= 0)
435 reg_allocno[i] = reg_allocno[reg_may_share[i]];
437 reg_allocno[i] = max_allocno++;
438 if (REG_LIVE_LENGTH (i) == 0)
444 allocno_reg = (int *) xmalloc (max_allocno * sizeof (int));
445 allocno_size = (int *) xcalloc (max_allocno, sizeof (int));
446 allocno_calls_crossed = (int *) xcalloc (max_allocno, sizeof (int));
447 allocno_n_refs = (int *) xcalloc (max_allocno, sizeof (int));
448 allocno_live_length = (int *) xcalloc (max_allocno, sizeof (int));
450 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
451 if (reg_allocno[i] >= 0)
453 int allocno = reg_allocno[i];
454 allocno_reg[allocno] = i;
455 allocno_size[allocno] = PSEUDO_REGNO_SIZE (i);
456 allocno_calls_crossed[allocno] += REG_N_CALLS_CROSSED (i);
457 allocno_n_refs[allocno] += REG_N_REFS (i);
458 if (allocno_live_length[allocno] < REG_LIVE_LENGTH (i))
459 allocno_live_length[allocno] = REG_LIVE_LENGTH (i);
462 /* Calculate amount of usage of each hard reg by pseudos
463 allocated by local-alloc. This is to see if we want to
465 bzero ((char *) local_reg_live_length, sizeof local_reg_live_length);
466 bzero ((char *) local_reg_n_refs, sizeof local_reg_n_refs);
467 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
468 if (reg_renumber[i] >= 0)
470 int regno = reg_renumber[i];
471 int endregno = regno + HARD_REGNO_NREGS (regno, PSEUDO_REGNO_MODE (i));
474 for (j = regno; j < endregno; j++)
476 local_reg_n_refs[j] += REG_N_REFS (i);
477 local_reg_live_length[j] += REG_LIVE_LENGTH (i);
481 /* We can't override local-alloc for a reg used not just by local-alloc. */
482 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
483 if (regs_ever_live[i])
484 local_reg_n_refs[i] = 0;
486 /* Allocate the space for the conflict and preference tables and
490 = (HARD_REG_SET *) xcalloc (max_allocno, sizeof (HARD_REG_SET));
492 = (HARD_REG_SET *) xcalloc (max_allocno, sizeof (HARD_REG_SET));
493 hard_reg_copy_preferences
494 = (HARD_REG_SET *) xcalloc (max_allocno, sizeof (HARD_REG_SET));
495 hard_reg_full_preferences
496 = (HARD_REG_SET *) xcalloc (max_allocno, sizeof (HARD_REG_SET));
498 = (HARD_REG_SET *) xcalloc (max_allocno, sizeof (HARD_REG_SET));
500 allocno_row_words = (max_allocno + INT_BITS - 1) / INT_BITS;
502 /* We used to use alloca here, but the size of what it would try to
503 allocate would occasionally cause it to exceed the stack limit and
504 cause unpredictable core dumps. Some examples were > 2Mb in size. */
505 conflicts = (INT_TYPE *) xcalloc (max_allocno * allocno_row_words,
508 allocnos_live = (INT_TYPE *) xmalloc (allocno_row_words * sizeof (INT_TYPE));
510 /* If there is work to be done (at least one reg to allocate),
511 perform global conflict analysis and allocate the regs. */
515 /* Scan all the insns and compute the conflicts among allocnos
516 and between allocnos and hard regs. */
522 /* Eliminate conflicts between pseudos and eliminable registers. If
523 the register is not eliminated, the pseudo won't really be able to
524 live in the eliminable register, so the conflict doesn't matter.
525 If we do eliminate the register, the conflict will no longer exist.
526 So in either case, we can ignore the conflict. Likewise for
529 for (i = 0; i < (size_t) max_allocno; i++)
531 AND_COMPL_HARD_REG_SET (hard_reg_conflicts[i], eliminable_regset);
532 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[i],
534 AND_COMPL_HARD_REG_SET (hard_reg_preferences[i], eliminable_regset);
537 /* Try to expand the preferences by merging them between allocnos. */
539 expand_preferences ();
541 /* Determine the order to allocate the remaining pseudo registers. */
543 allocno_order = (int *) xmalloc (max_allocno * sizeof (int));
544 for (i = 0; i < (size_t) max_allocno; i++)
545 allocno_order[i] = i;
547 /* Default the size to 1, since allocno_compare uses it to divide by.
548 Also convert allocno_live_length of zero to -1. A length of zero
549 can occur when all the registers for that allocno have reg_live_length
550 equal to -2. In this case, we want to make an allocno, but not
551 allocate it. So avoid the divide-by-zero and set it to a low
554 for (i = 0; i < (size_t) max_allocno; i++)
556 if (allocno_size[i] == 0)
558 if (allocno_live_length[i] == 0)
559 allocno_live_length[i] = -1;
562 qsort (allocno_order, max_allocno, sizeof (int), allocno_compare);
564 prune_preferences ();
567 dump_conflicts (file);
569 /* Try allocating them, one by one, in that order,
570 except for parameters marked with reg_live_length[regno] == -2. */
572 for (i = 0; i < (size_t) max_allocno; i++)
573 if (reg_renumber[allocno_reg[allocno_order[i]]] < 0
574 && REG_LIVE_LENGTH (allocno_reg[allocno_order[i]]) >= 0)
576 /* If we have more than one register class,
577 first try allocating in the class that is cheapest
578 for this pseudo-reg. If that fails, try any reg. */
579 if (N_REG_CLASSES > 1)
581 find_reg (allocno_order[i], 0, 0, 0, 0);
582 if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
585 if (reg_alternate_class (allocno_reg[allocno_order[i]]) != NO_REGS)
586 find_reg (allocno_order[i], 0, 1, 0, 0);
589 free (allocno_order);
592 /* Do the reloads now while the allocno data still exist, so that we can
593 try to assign new hard regs to any pseudo regs that are spilled. */
595 #if 0 /* We need to eliminate regs even if there is no rtl code,
596 for the sake of debugging information. */
597 if (n_basic_blocks > 0)
600 build_insn_chain (get_insns ());
601 retval = reload (get_insns (), 1, file);
606 free (reg_may_share);
609 free (allocno_calls_crossed);
610 free (allocno_n_refs);
611 free (allocno_live_length);
612 free (hard_reg_conflicts);
613 free (hard_reg_preferences);
614 free (hard_reg_copy_preferences);
615 free (hard_reg_full_preferences);
616 free (regs_someone_prefers);
618 free (allocnos_live);
623 /* Sort predicate for ordering the allocnos.
624 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
627 allocno_compare (v1p, v2p)
631 int v1 = *(const int *)v1p, v2 = *(const int *)v2p;
632 /* Note that the quotient will never be bigger than
633 the value of floor_log2 times the maximum number of
634 times a register can occur in one insn (surely less than 100).
635 Multiplying this by 10000 can't overflow. */
637 = (((double) (floor_log2 (allocno_n_refs[v1]) * allocno_n_refs[v1])
638 / allocno_live_length[v1])
639 * 10000 * allocno_size[v1]);
641 = (((double) (floor_log2 (allocno_n_refs[v2]) * allocno_n_refs[v2])
642 / allocno_live_length[v2])
643 * 10000 * allocno_size[v2]);
647 /* If regs are equally good, sort by allocno,
648 so that the results of qsort leave nothing to chance. */
652 /* Scan the rtl code and record all conflicts and register preferences in the
653 conflict matrices and preference tables. */
660 int *block_start_allocnos;
662 /* Make a vector that mark_reg_{store,clobber} will store in. */
663 regs_set = (rtx *) xmalloc (max_parallel * sizeof (rtx) * 2);
665 block_start_allocnos = (int *) xmalloc (max_allocno * sizeof (int));
667 for (b = 0; b < n_basic_blocks; b++)
669 bzero ((char *) allocnos_live, allocno_row_words * sizeof (INT_TYPE));
671 /* Initialize table of registers currently live
672 to the state at the beginning of this basic block.
673 This also marks the conflicts among them.
675 For pseudo-regs, there is only one bit for each one
676 no matter how many hard regs it occupies.
677 This is ok; we know the size from PSEUDO_REGNO_SIZE.
678 For explicit hard regs, we cannot know the size that way
679 since one hard reg can be used with various sizes.
680 Therefore, we must require that all the hard regs
681 implicitly live as part of a multi-word hard reg
682 are explicitly marked in basic_block_live_at_start. */
685 register regset old = BASIC_BLOCK (b)->global_live_at_start;
688 REG_SET_TO_HARD_REG_SET (hard_regs_live, old);
689 EXECUTE_IF_SET_IN_REG_SET (old, FIRST_PSEUDO_REGISTER, i,
691 register int a = reg_allocno[i];
694 SET_ALLOCNO_LIVE (a);
695 block_start_allocnos[ax++] = a;
697 else if ((a = reg_renumber[i]) >= 0)
699 (a, PSEUDO_REGNO_MODE (i));
702 /* Record that each allocno now live conflicts with each other
703 allocno now live, and with each hard reg now live. */
705 record_conflicts (block_start_allocnos, ax);
709 /* Pseudos can't go in stack regs at the start of a basic block
710 that is reached by an abnormal edge. */
713 for (e = BASIC_BLOCK (b)->pred; e ; e = e->pred_next)
714 if (e->flags & EDGE_ABNORMAL)
717 for (ax = FIRST_STACK_REG; ax <= LAST_STACK_REG; ax++)
718 record_one_conflict (ax);
723 insn = BLOCK_HEAD (b);
725 /* Scan the code of this basic block, noting which allocnos
726 and hard regs are born or die. When one is born,
727 record a conflict with all others currently live. */
731 register RTX_CODE code = GET_CODE (insn);
734 /* Make regs_set an empty set. */
738 if (code == INSN || code == CALL_INSN || code == JUMP_INSN)
743 for (link = REG_NOTES (insn);
744 link && i < NUM_NO_CONFLICT_PAIRS;
745 link = XEXP (link, 1))
746 if (REG_NOTE_KIND (link) == REG_NO_CONFLICT)
748 no_conflict_pairs[i].allocno1
749 = reg_allocno[REGNO (SET_DEST (PATTERN (insn)))];
750 no_conflict_pairs[i].allocno2
751 = reg_allocno[REGNO (XEXP (link, 0))];
756 /* Mark any registers clobbered by INSN as live,
757 so they conflict with the inputs. */
759 note_stores (PATTERN (insn), mark_reg_clobber, NULL);
761 /* Mark any registers dead after INSN as dead now. */
763 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
764 if (REG_NOTE_KIND (link) == REG_DEAD)
765 mark_reg_death (XEXP (link, 0));
767 /* Mark any registers set in INSN as live,
768 and mark them as conflicting with all other live regs.
769 Clobbers are processed again, so they conflict with
770 the registers that are set. */
772 note_stores (PATTERN (insn), mark_reg_store, NULL);
775 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
776 if (REG_NOTE_KIND (link) == REG_INC)
777 mark_reg_store (XEXP (link, 0), NULL_RTX, NULL);
780 /* If INSN has multiple outputs, then any reg that dies here
781 and is used inside of an output
782 must conflict with the other outputs.
784 It is unsafe to use !single_set here since it will ignore an
785 unused output. Just because an output is unused does not mean
786 the compiler can assume the side effect will not occur.
787 Consider if REG appears in the address of an output and we
788 reload the output. If we allocate REG to the same hard
789 register as an unused output we could set the hard register
790 before the output reload insn. */
791 if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn))
792 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
793 if (REG_NOTE_KIND (link) == REG_DEAD)
795 int used_in_output = 0;
797 rtx reg = XEXP (link, 0);
799 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
801 rtx set = XVECEXP (PATTERN (insn), 0, i);
802 if (GET_CODE (set) == SET
803 && GET_CODE (SET_DEST (set)) != REG
804 && !rtx_equal_p (reg, SET_DEST (set))
805 && reg_overlap_mentioned_p (reg, SET_DEST (set)))
809 mark_reg_conflicts (reg);
812 /* Mark any registers set in INSN and then never used. */
814 while (n_regs_set > 0)
815 if (find_regno_note (insn, REG_UNUSED,
816 REGNO (regs_set[--n_regs_set])))
817 mark_reg_death (regs_set[n_regs_set]);
820 if (insn == BLOCK_END (b))
822 insn = NEXT_INSN (insn);
827 free (block_start_allocnos);
830 /* Expand the preference information by looking for cases where one allocno
831 dies in an insn that sets an allocno. If those two allocnos don't conflict,
832 merge any preferences between those allocnos. */
835 expand_preferences ()
841 /* We only try to handle the most common cases here. Most of the cases
842 where this wins are reg-reg copies. */
844 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
845 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
846 && (set = single_set (insn)) != 0
847 && GET_CODE (SET_DEST (set)) == REG
848 && reg_allocno[REGNO (SET_DEST (set))] >= 0)
849 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
850 if (REG_NOTE_KIND (link) == REG_DEAD
851 && GET_CODE (XEXP (link, 0)) == REG
852 && reg_allocno[REGNO (XEXP (link, 0))] >= 0
853 && ! CONFLICTP (reg_allocno[REGNO (SET_DEST (set))],
854 reg_allocno[REGNO (XEXP (link, 0))]))
856 int a1 = reg_allocno[REGNO (SET_DEST (set))];
857 int a2 = reg_allocno[REGNO (XEXP (link, 0))];
859 if (XEXP (link, 0) == SET_SRC (set))
861 IOR_HARD_REG_SET (hard_reg_copy_preferences[a1],
862 hard_reg_copy_preferences[a2]);
863 IOR_HARD_REG_SET (hard_reg_copy_preferences[a2],
864 hard_reg_copy_preferences[a1]);
867 IOR_HARD_REG_SET (hard_reg_preferences[a1],
868 hard_reg_preferences[a2]);
869 IOR_HARD_REG_SET (hard_reg_preferences[a2],
870 hard_reg_preferences[a1]);
871 IOR_HARD_REG_SET (hard_reg_full_preferences[a1],
872 hard_reg_full_preferences[a2]);
873 IOR_HARD_REG_SET (hard_reg_full_preferences[a2],
874 hard_reg_full_preferences[a1]);
878 /* Prune the preferences for global registers to exclude registers that cannot
881 Compute `regs_someone_prefers', which is a bitmask of the hard registers
882 that are preferred by conflicting registers of lower priority. If possible,
883 we will avoid using these registers. */
890 int *allocno_to_order = (int *) xmalloc (max_allocno * sizeof (int));
892 /* Scan least most important to most important.
893 For each allocno, remove from preferences registers that cannot be used,
894 either because of conflicts or register type. Then compute all registers
895 preferred by each lower-priority register that conflicts. */
897 for (i = max_allocno - 1; i >= 0; i--)
901 allocno = allocno_order[i];
902 allocno_to_order[allocno] = i;
903 COPY_HARD_REG_SET (temp, hard_reg_conflicts[allocno]);
905 if (allocno_calls_crossed[allocno] == 0)
906 IOR_HARD_REG_SET (temp, fixed_reg_set);
908 IOR_HARD_REG_SET (temp, call_used_reg_set);
910 IOR_COMPL_HARD_REG_SET
912 reg_class_contents[(int) reg_preferred_class (allocno_reg[allocno])]);
914 AND_COMPL_HARD_REG_SET (hard_reg_preferences[allocno], temp);
915 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[allocno], temp);
916 AND_COMPL_HARD_REG_SET (hard_reg_full_preferences[allocno], temp);
919 for (i = max_allocno - 1; i >= 0; i--)
921 /* Merge in the preferences of lower-priority registers (they have
922 already been pruned). If we also prefer some of those registers,
923 don't exclude them unless we are of a smaller size (in which case
924 we want to give the lower-priority allocno the first chance for
926 HARD_REG_SET temp, temp2;
929 allocno = allocno_order[i];
931 CLEAR_HARD_REG_SET (temp);
932 CLEAR_HARD_REG_SET (temp2);
934 EXECUTE_IF_CONFLICT (allocno, allocno2,
936 if (allocno_to_order[allocno2] > i)
938 if (allocno_size[allocno2] <= allocno_size[allocno])
939 IOR_HARD_REG_SET (temp, hard_reg_full_preferences[allocno2]);
941 IOR_HARD_REG_SET (temp2, hard_reg_full_preferences[allocno2]);
945 AND_COMPL_HARD_REG_SET (temp, hard_reg_full_preferences[allocno]);
946 IOR_HARD_REG_SET (temp, temp2);
947 COPY_HARD_REG_SET (regs_someone_prefers[allocno], temp);
949 free (allocno_to_order);
952 /* Assign a hard register to ALLOCNO; look for one that is the beginning
953 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
954 The registers marked in PREFREGS are tried first.
956 LOSERS, if non-zero, is a HARD_REG_SET indicating registers that cannot
957 be used for this allocation.
959 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
960 Otherwise ignore that preferred class and use the alternate class.
962 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
963 will have to be saved and restored at calls.
965 RETRYING is nonzero if this is called from retry_global_alloc.
967 If we find one, record it in reg_renumber.
968 If not, do nothing. */
971 find_reg (allocno, losers, alt_regs_p, accept_call_clobbered, retrying)
975 int accept_call_clobbered;
978 register int i, best_reg, pass;
980 register /* Declare it register if it's a scalar. */
982 HARD_REG_SET used, used1, used2;
984 enum reg_class class = (alt_regs_p
985 ? reg_alternate_class (allocno_reg[allocno])
986 : reg_preferred_class (allocno_reg[allocno]));
987 enum machine_mode mode = PSEUDO_REGNO_MODE (allocno_reg[allocno]);
989 if (accept_call_clobbered)
990 COPY_HARD_REG_SET (used1, call_fixed_reg_set);
991 else if (allocno_calls_crossed[allocno] == 0)
992 COPY_HARD_REG_SET (used1, fixed_reg_set);
994 COPY_HARD_REG_SET (used1, call_used_reg_set);
996 /* Some registers should not be allocated in global-alloc. */
997 IOR_HARD_REG_SET (used1, no_global_alloc_regs);
999 IOR_HARD_REG_SET (used1, losers);
1001 IOR_COMPL_HARD_REG_SET (used1, reg_class_contents[(int) class]);
1002 COPY_HARD_REG_SET (used2, used1);
1004 IOR_HARD_REG_SET (used1, hard_reg_conflicts[allocno]);
1006 #ifdef CLASS_CANNOT_CHANGE_SIZE
1007 if (REG_CHANGES_SIZE (allocno_reg[allocno]))
1008 IOR_HARD_REG_SET (used1,
1009 reg_class_contents[(int) CLASS_CANNOT_CHANGE_SIZE]);
1012 /* Try each hard reg to see if it fits. Do this in two passes.
1013 In the first pass, skip registers that are preferred by some other pseudo
1014 to give it a better chance of getting one of those registers. Only if
1015 we can't get a register when excluding those do we take one of them.
1016 However, we never allocate a register for the first time in pass 0. */
1018 COPY_HARD_REG_SET (used, used1);
1019 IOR_COMPL_HARD_REG_SET (used, regs_used_so_far);
1020 IOR_HARD_REG_SET (used, regs_someone_prefers[allocno]);
1023 for (i = FIRST_PSEUDO_REGISTER, pass = 0;
1024 pass <= 1 && i >= FIRST_PSEUDO_REGISTER;
1028 COPY_HARD_REG_SET (used, used1);
1029 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1031 #ifdef REG_ALLOC_ORDER
1032 int regno = reg_alloc_order[i];
1036 if (! TEST_HARD_REG_BIT (used, regno)
1037 && HARD_REGNO_MODE_OK (regno, mode)
1038 && (allocno_calls_crossed[allocno] == 0
1039 || accept_call_clobbered
1040 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
1043 register int lim = regno + HARD_REGNO_NREGS (regno, mode);
1046 && ! TEST_HARD_REG_BIT (used, j));
1053 #ifndef REG_ALLOC_ORDER
1054 i = j; /* Skip starting points we know will lose */
1060 /* See if there is a preferred register with the same class as the register
1061 we allocated above. Making this restriction prevents register
1062 preferencing from creating worse register allocation.
1064 Remove from the preferred registers and conflicting registers. Note that
1065 additional conflicts may have been added after `prune_preferences' was
1068 First do this for those register with copy preferences, then all
1069 preferred registers. */
1071 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[allocno], used);
1072 GO_IF_HARD_REG_SUBSET (hard_reg_copy_preferences[allocno],
1073 reg_class_contents[(int) NO_REGS], no_copy_prefs);
1077 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1078 if (TEST_HARD_REG_BIT (hard_reg_copy_preferences[allocno], i)
1079 && HARD_REGNO_MODE_OK (i, mode)
1080 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1081 || reg_class_subset_p (REGNO_REG_CLASS (i),
1082 REGNO_REG_CLASS (best_reg))
1083 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1084 REGNO_REG_CLASS (i))))
1087 register int lim = i + HARD_REGNO_NREGS (i, mode);
1090 && ! TEST_HARD_REG_BIT (used, j)
1091 && (REGNO_REG_CLASS (j)
1092 == REGNO_REG_CLASS (best_reg + (j - i))
1093 || reg_class_subset_p (REGNO_REG_CLASS (j),
1094 REGNO_REG_CLASS (best_reg + (j - i)))
1095 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1096 REGNO_REG_CLASS (j))));
1107 AND_COMPL_HARD_REG_SET (hard_reg_preferences[allocno], used);
1108 GO_IF_HARD_REG_SUBSET (hard_reg_preferences[allocno],
1109 reg_class_contents[(int) NO_REGS], no_prefs);
1113 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1114 if (TEST_HARD_REG_BIT (hard_reg_preferences[allocno], i)
1115 && HARD_REGNO_MODE_OK (i, mode)
1116 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1117 || reg_class_subset_p (REGNO_REG_CLASS (i),
1118 REGNO_REG_CLASS (best_reg))
1119 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1120 REGNO_REG_CLASS (i))))
1123 register int lim = i + HARD_REGNO_NREGS (i, mode);
1126 && ! TEST_HARD_REG_BIT (used, j)
1127 && (REGNO_REG_CLASS (j)
1128 == REGNO_REG_CLASS (best_reg + (j - i))
1129 || reg_class_subset_p (REGNO_REG_CLASS (j),
1130 REGNO_REG_CLASS (best_reg + (j - i)))
1131 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1132 REGNO_REG_CLASS (j))));
1143 /* If we haven't succeeded yet, try with caller-saves.
1144 We need not check to see if the current function has nonlocal
1145 labels because we don't put any pseudos that are live over calls in
1146 registers in that case. */
1148 if (flag_caller_saves && best_reg < 0)
1150 /* Did not find a register. If it would be profitable to
1151 allocate a call-clobbered register and save and restore it
1152 around calls, do that. */
1153 if (! accept_call_clobbered
1154 && allocno_calls_crossed[allocno] != 0
1155 && CALLER_SAVE_PROFITABLE (allocno_n_refs[allocno],
1156 allocno_calls_crossed[allocno]))
1158 HARD_REG_SET new_losers;
1160 CLEAR_HARD_REG_SET (new_losers);
1162 COPY_HARD_REG_SET (new_losers, losers);
1164 IOR_HARD_REG_SET(new_losers, losing_caller_save_reg_set);
1165 find_reg (allocno, new_losers, alt_regs_p, 1, retrying);
1166 if (reg_renumber[allocno_reg[allocno]] >= 0)
1168 caller_save_needed = 1;
1174 /* If we haven't succeeded yet,
1175 see if some hard reg that conflicts with us
1176 was utilized poorly by local-alloc.
1177 If so, kick out the regs that were put there by local-alloc
1178 so we can use it instead. */
1179 if (best_reg < 0 && !retrying
1180 /* Let's not bother with multi-reg allocnos. */
1181 && allocno_size[allocno] == 1)
1183 /* Count from the end, to find the least-used ones first. */
1184 for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1186 #ifdef REG_ALLOC_ORDER
1187 int regno = reg_alloc_order[i];
1192 if (local_reg_n_refs[regno] != 0
1193 /* Don't use a reg no good for this pseudo. */
1194 && ! TEST_HARD_REG_BIT (used2, regno)
1195 && HARD_REGNO_MODE_OK (regno, mode)
1196 #ifdef CLASS_CANNOT_CHANGE_SIZE
1197 && ! (REG_CHANGES_SIZE (allocno_reg[allocno])
1198 && (TEST_HARD_REG_BIT
1199 (reg_class_contents[(int) CLASS_CANNOT_CHANGE_SIZE],
1204 /* We explicitly evaluate the divide results into temporary
1205 variables so as to avoid excess precision problems that occur
1206 on a i386-unknown-sysv4.2 (unixware) host. */
1208 double tmp1 = ((double) local_reg_n_refs[regno]
1209 / local_reg_live_length[regno]);
1210 double tmp2 = ((double) allocno_n_refs[allocno]
1211 / allocno_live_length[allocno]);
1215 /* Hard reg REGNO was used less in total by local regs
1216 than it would be used by this one allocno! */
1218 for (k = 0; k < max_regno; k++)
1219 if (reg_renumber[k] >= 0)
1221 int r = reg_renumber[k];
1223 = r + HARD_REGNO_NREGS (r, PSEUDO_REGNO_MODE (k));
1225 if (regno >= r && regno < endregno)
1226 reg_renumber[k] = -1;
1236 /* Did we find a register? */
1240 register int lim, j;
1241 HARD_REG_SET this_reg;
1243 /* Yes. Record it as the hard register of this pseudo-reg. */
1244 reg_renumber[allocno_reg[allocno]] = best_reg;
1245 /* Also of any pseudo-regs that share with it. */
1246 if (reg_may_share[allocno_reg[allocno]])
1247 for (j = FIRST_PSEUDO_REGISTER; j < max_regno; j++)
1248 if (reg_allocno[j] == allocno)
1249 reg_renumber[j] = best_reg;
1251 /* Make a set of the hard regs being allocated. */
1252 CLEAR_HARD_REG_SET (this_reg);
1253 lim = best_reg + HARD_REGNO_NREGS (best_reg, mode);
1254 for (j = best_reg; j < lim; j++)
1256 SET_HARD_REG_BIT (this_reg, j);
1257 SET_HARD_REG_BIT (regs_used_so_far, j);
1258 /* This is no longer a reg used just by local regs. */
1259 local_reg_n_refs[j] = 0;
1261 /* For each other pseudo-reg conflicting with this one,
1262 mark it as conflicting with the hard regs this one occupies. */
1264 EXECUTE_IF_CONFLICT (lim, j,
1266 IOR_HARD_REG_SET (hard_reg_conflicts[j], this_reg);
1271 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1272 Perhaps it had previously seemed not worth a hard reg,
1273 or perhaps its old hard reg has been commandeered for reloads.
1274 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1275 they do not appear to be allocated.
1276 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1279 retry_global_alloc (regno, forbidden_regs)
1281 HARD_REG_SET forbidden_regs;
1283 int allocno = reg_allocno[regno];
1286 /* If we have more than one register class,
1287 first try allocating in the class that is cheapest
1288 for this pseudo-reg. If that fails, try any reg. */
1289 if (N_REG_CLASSES > 1)
1290 find_reg (allocno, forbidden_regs, 0, 0, 1);
1291 if (reg_renumber[regno] < 0
1292 && reg_alternate_class (regno) != NO_REGS)
1293 find_reg (allocno, forbidden_regs, 1, 0, 1);
1295 /* If we found a register, modify the RTL for the register to
1296 show the hard register, and mark that register live. */
1297 if (reg_renumber[regno] >= 0)
1299 REGNO (regno_reg_rtx[regno]) = reg_renumber[regno];
1300 mark_home_live (regno);
1305 /* Record a conflict between register REGNO
1306 and everything currently live.
1307 REGNO must not be a pseudo reg that was allocated
1308 by local_alloc; such numbers must be translated through
1309 reg_renumber before calling here. */
1312 record_one_conflict (regno)
1317 if (regno < FIRST_PSEUDO_REGISTER)
1318 /* When a hard register becomes live,
1319 record conflicts with live pseudo regs. */
1320 EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live, j,
1322 SET_HARD_REG_BIT (hard_reg_conflicts[j], regno);
1325 /* When a pseudo-register becomes live,
1326 record conflicts first with hard regs,
1327 then with other pseudo regs. */
1329 register int ialloc = reg_allocno[regno];
1330 register int ialloc_prod = ialloc * allocno_row_words;
1331 IOR_HARD_REG_SET (hard_reg_conflicts[ialloc], hard_regs_live);
1332 for (j = allocno_row_words - 1; j >= 0; j--)
1336 for (k = 0; k < n_no_conflict_pairs; k++)
1337 if (! ((j == no_conflict_pairs[k].allocno1
1338 && ialloc == no_conflict_pairs[k].allocno2)
1340 (j == no_conflict_pairs[k].allocno2
1341 && ialloc == no_conflict_pairs[k].allocno1)))
1343 conflicts[ialloc_prod + j] |= allocnos_live[j];
1348 /* Record all allocnos currently live as conflicting
1349 with each other and with all hard regs currently live.
1350 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1351 are currently live. Their bits are also flagged in allocnos_live. */
1354 record_conflicts (allocno_vec, len)
1355 register int *allocno_vec;
1358 register int allocno;
1360 register int ialloc_prod;
1364 allocno = allocno_vec[len];
1365 ialloc_prod = allocno * allocno_row_words;
1366 IOR_HARD_REG_SET (hard_reg_conflicts[allocno], hard_regs_live);
1367 for (j = allocno_row_words - 1; j >= 0; j--)
1368 conflicts[ialloc_prod + j] |= allocnos_live[j];
1372 /* If CONFLICTP (i, j) is true, make sure CONFLICTP (j, i) is also true. */
1377 int rw = allocno_row_words;
1378 int rwb = rw * INT_BITS;
1379 INT_TYPE *p = conflicts;
1380 INT_TYPE *q0 = conflicts, *q1, *q2;
1381 unsigned INT_TYPE mask;
1383 for (i = max_allocno - 1, mask = 1; i >= 0; i--, mask <<= 1)
1390 for (j = allocno_row_words - 1, q1 = q0; j >= 0; j--, q1 += rwb)
1392 unsigned INT_TYPE word;
1394 for (word = (unsigned INT_TYPE) *p++, q2 = q1; word;
1395 word >>= 1, q2 += rw)
1404 /* Handle the case where REG is set by the insn being scanned,
1405 during the forward scan to accumulate conflicts.
1406 Store a 1 in regs_live or allocnos_live for this register, record how many
1407 consecutive hardware registers it actually needs,
1408 and record a conflict with all other registers already live.
1410 Note that even if REG does not remain alive after this insn,
1411 we must mark it here as live, to ensure a conflict between
1412 REG and any other regs set in this insn that really do live.
1413 This is because those other regs could be considered after this.
1415 REG might actually be something other than a register;
1416 if so, we do nothing.
1418 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1419 a REG_INC note was found for it). */
1422 mark_reg_store (reg, setter, data)
1424 void *data ATTRIBUTE_UNUSED;
1428 /* WORD is which word of a multi-register group is being stored.
1429 For the case where the store is actually into a SUBREG of REG.
1430 Except we don't use it; I believe the entire REG needs to be
1434 if (GET_CODE (reg) == SUBREG)
1436 word = SUBREG_WORD (reg);
1437 reg = SUBREG_REG (reg);
1440 if (GET_CODE (reg) != REG)
1443 regs_set[n_regs_set++] = reg;
1445 if (setter && GET_CODE (setter) != CLOBBER)
1446 set_preference (reg, SET_SRC (setter));
1448 regno = REGNO (reg);
1450 /* Either this is one of the max_allocno pseudo regs not allocated,
1451 or it is or has a hardware reg. First handle the pseudo-regs. */
1452 if (regno >= FIRST_PSEUDO_REGISTER)
1454 if (reg_allocno[regno] >= 0)
1456 SET_ALLOCNO_LIVE (reg_allocno[regno]);
1457 record_one_conflict (regno);
1461 if (reg_renumber[regno] >= 0)
1462 regno = reg_renumber[regno] /* + word */;
1464 /* Handle hardware regs (and pseudos allocated to hard regs). */
1465 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1467 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1468 while (regno < last)
1470 record_one_conflict (regno);
1471 SET_HARD_REG_BIT (hard_regs_live, regno);
1477 /* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
1480 mark_reg_clobber (reg, setter, data)
1482 void *data ATTRIBUTE_UNUSED;
1484 if (GET_CODE (setter) == CLOBBER)
1485 mark_reg_store (reg, setter, data);
1488 /* Record that REG has conflicts with all the regs currently live.
1489 Do not mark REG itself as live. */
1492 mark_reg_conflicts (reg)
1497 if (GET_CODE (reg) == SUBREG)
1498 reg = SUBREG_REG (reg);
1500 if (GET_CODE (reg) != REG)
1503 regno = REGNO (reg);
1505 /* Either this is one of the max_allocno pseudo regs not allocated,
1506 or it is or has a hardware reg. First handle the pseudo-regs. */
1507 if (regno >= FIRST_PSEUDO_REGISTER)
1509 if (reg_allocno[regno] >= 0)
1510 record_one_conflict (regno);
1513 if (reg_renumber[regno] >= 0)
1514 regno = reg_renumber[regno];
1516 /* Handle hardware regs (and pseudos allocated to hard regs). */
1517 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1519 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1520 while (regno < last)
1522 record_one_conflict (regno);
1528 /* Mark REG as being dead (following the insn being scanned now).
1529 Store a 0 in regs_live or allocnos_live for this register. */
1532 mark_reg_death (reg)
1535 register int regno = REGNO (reg);
1537 /* Either this is one of the max_allocno pseudo regs not allocated,
1538 or it is a hardware reg. First handle the pseudo-regs. */
1539 if (regno >= FIRST_PSEUDO_REGISTER)
1541 if (reg_allocno[regno] >= 0)
1542 CLEAR_ALLOCNO_LIVE (reg_allocno[regno]);
1545 /* For pseudo reg, see if it has been assigned a hardware reg. */
1546 if (reg_renumber[regno] >= 0)
1547 regno = reg_renumber[regno];
1549 /* Handle hardware regs (and pseudos allocated to hard regs). */
1550 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1552 /* Pseudo regs already assigned hardware regs are treated
1553 almost the same as explicit hardware regs. */
1554 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1555 while (regno < last)
1557 CLEAR_HARD_REG_BIT (hard_regs_live, regno);
1563 /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1564 for the value stored in it. MODE determines how many consecutive
1565 registers are actually in use. Do not record conflicts;
1566 it is assumed that the caller will do that. */
1569 mark_reg_live_nc (regno, mode)
1571 enum machine_mode mode;
1573 register int last = regno + HARD_REGNO_NREGS (regno, mode);
1574 while (regno < last)
1576 SET_HARD_REG_BIT (hard_regs_live, regno);
1581 /* Try to set a preference for an allocno to a hard register.
1582 We are passed DEST and SRC which are the operands of a SET. It is known
1583 that SRC is a register. If SRC or the first operand of SRC is a register,
1584 try to set a preference. If one of the two is a hard register and the other
1585 is a pseudo-register, mark the preference.
1587 Note that we are not as aggressive as local-alloc in trying to tie a
1588 pseudo-register to a hard register. */
1591 set_preference (dest, src)
1594 int src_regno, dest_regno;
1595 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1596 to compensate for subregs in SRC or DEST. */
1601 if (GET_RTX_FORMAT (GET_CODE (src))[0] == 'e')
1602 src = XEXP (src, 0), copy = 0;
1604 /* Get the reg number for both SRC and DEST.
1605 If neither is a reg, give up. */
1607 if (GET_CODE (src) == REG)
1608 src_regno = REGNO (src);
1609 else if (GET_CODE (src) == SUBREG && GET_CODE (SUBREG_REG (src)) == REG)
1611 src_regno = REGNO (SUBREG_REG (src));
1612 offset += SUBREG_WORD (src);
1617 if (GET_CODE (dest) == REG)
1618 dest_regno = REGNO (dest);
1619 else if (GET_CODE (dest) == SUBREG && GET_CODE (SUBREG_REG (dest)) == REG)
1621 dest_regno = REGNO (SUBREG_REG (dest));
1622 offset -= SUBREG_WORD (dest);
1627 /* Convert either or both to hard reg numbers. */
1629 if (reg_renumber[src_regno] >= 0)
1630 src_regno = reg_renumber[src_regno];
1632 if (reg_renumber[dest_regno] >= 0)
1633 dest_regno = reg_renumber[dest_regno];
1635 /* Now if one is a hard reg and the other is a global pseudo
1636 then give the other a preference. */
1638 if (dest_regno < FIRST_PSEUDO_REGISTER && src_regno >= FIRST_PSEUDO_REGISTER
1639 && reg_allocno[src_regno] >= 0)
1641 dest_regno -= offset;
1642 if (dest_regno >= 0 && dest_regno < FIRST_PSEUDO_REGISTER)
1645 SET_REGBIT (hard_reg_copy_preferences,
1646 reg_allocno[src_regno], dest_regno);
1648 SET_REGBIT (hard_reg_preferences,
1649 reg_allocno[src_regno], dest_regno);
1650 for (i = dest_regno;
1651 i < dest_regno + HARD_REGNO_NREGS (dest_regno, GET_MODE (dest));
1653 SET_REGBIT (hard_reg_full_preferences, reg_allocno[src_regno], i);
1657 if (src_regno < FIRST_PSEUDO_REGISTER && dest_regno >= FIRST_PSEUDO_REGISTER
1658 && reg_allocno[dest_regno] >= 0)
1660 src_regno += offset;
1661 if (src_regno >= 0 && src_regno < FIRST_PSEUDO_REGISTER)
1664 SET_REGBIT (hard_reg_copy_preferences,
1665 reg_allocno[dest_regno], src_regno);
1667 SET_REGBIT (hard_reg_preferences,
1668 reg_allocno[dest_regno], src_regno);
1670 i < src_regno + HARD_REGNO_NREGS (src_regno, GET_MODE (src));
1672 SET_REGBIT (hard_reg_full_preferences, reg_allocno[dest_regno], i);
1677 /* Indicate that hard register number FROM was eliminated and replaced with
1678 an offset from hard register number TO. The status of hard registers live
1679 at the start of a basic block is updated by replacing a use of FROM with
1683 mark_elimination (from, to)
1688 for (i = 0; i < n_basic_blocks; i++)
1690 register regset r = BASIC_BLOCK (i)->global_live_at_start;
1691 if (REGNO_REG_SET_P (r, from))
1693 CLEAR_REGNO_REG_SET (r, from);
1694 SET_REGNO_REG_SET (r, to);
1699 /* Used for communication between the following functions. Holds the
1700 current life information. */
1701 static regset live_relevant_regs;
1703 /* Record in live_relevant_regs that register REG became live. This
1704 is called via note_stores. */
1706 reg_becomes_live (reg, setter, data)
1708 rtx setter ATTRIBUTE_UNUSED;
1709 void *data ATTRIBUTE_UNUSED;
1713 if (GET_CODE (reg) == SUBREG)
1714 reg = SUBREG_REG (reg);
1716 if (GET_CODE (reg) != REG)
1719 regno = REGNO (reg);
1720 if (regno < FIRST_PSEUDO_REGISTER)
1722 int nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg));
1724 SET_REGNO_REG_SET (live_relevant_regs, regno++);
1726 else if (reg_renumber[regno] >= 0)
1727 SET_REGNO_REG_SET (live_relevant_regs, regno);
1730 /* Record in live_relevant_regs that register REGNO died. */
1732 reg_dies (regno, mode)
1734 enum machine_mode mode;
1736 if (regno < FIRST_PSEUDO_REGISTER)
1738 int nregs = HARD_REGNO_NREGS (regno, mode);
1740 CLEAR_REGNO_REG_SET (live_relevant_regs, regno++);
1743 CLEAR_REGNO_REG_SET (live_relevant_regs, regno);
1746 /* Walk the insns of the current function and build reload_insn_chain,
1747 and record register life information. */
1749 build_insn_chain (first)
1752 struct insn_chain **p = &reload_insn_chain;
1753 struct insn_chain *prev = 0;
1756 live_relevant_regs = ALLOCA_REG_SET ();
1758 for (; first; first = NEXT_INSN (first))
1760 struct insn_chain *c;
1762 if (first == BLOCK_HEAD (b))
1766 CLEAR_REG_SET (live_relevant_regs);
1768 EXECUTE_IF_SET_IN_BITMAP
1769 (BASIC_BLOCK (b)->global_live_at_start, 0, i,
1771 if (i < FIRST_PSEUDO_REGISTER
1772 ? ! TEST_HARD_REG_BIT (eliminable_regset, i)
1773 : reg_renumber[i] >= 0)
1774 SET_REGNO_REG_SET (live_relevant_regs, i);
1778 if (GET_CODE (first) != NOTE && GET_CODE (first) != BARRIER)
1780 c = new_insn_chain ();
1788 COPY_REG_SET (c->live_before, live_relevant_regs);
1790 if (GET_RTX_CLASS (GET_CODE (first)) == 'i')
1794 /* Mark the death of everything that dies in this instruction. */
1796 for (link = REG_NOTES (first); link; link = XEXP (link, 1))
1797 if (REG_NOTE_KIND (link) == REG_DEAD
1798 && GET_CODE (XEXP (link, 0)) == REG)
1799 reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)));
1801 /* Mark everything born in this instruction as live. */
1803 note_stores (PATTERN (first), reg_becomes_live, NULL);
1806 /* Remember which registers are live at the end of the insn, before
1807 killing those with REG_UNUSED notes. */
1808 COPY_REG_SET (c->live_after, live_relevant_regs);
1810 if (GET_RTX_CLASS (GET_CODE (first)) == 'i')
1814 /* Mark anything that is set in this insn and then unused as dying. */
1816 for (link = REG_NOTES (first); link; link = XEXP (link, 1))
1817 if (REG_NOTE_KIND (link) == REG_UNUSED
1818 && GET_CODE (XEXP (link, 0)) == REG)
1819 reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)));
1823 if (first == BLOCK_END (b))
1826 /* Stop after we pass the end of the last basic block. Verify that
1827 no real insns are after the end of the last basic block.
1829 We may want to reorganize the loop somewhat since this test should
1830 always be the right exit test. */
1831 if (b == n_basic_blocks)
1833 for (first = NEXT_INSN (first) ; first; first = NEXT_INSN (first))
1834 if (GET_RTX_CLASS (GET_CODE (first)) == 'i'
1835 && GET_CODE (PATTERN (first)) != USE)
1840 FREE_REG_SET (live_relevant_regs);
1844 /* Print debugging trace information if -dg switch is given,
1845 showing the information on which the allocation decisions are based. */
1848 dump_conflicts (file)
1852 register int has_preferences;
1855 for (i = 0; i < max_allocno; i++)
1857 if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
1861 fprintf (file, ";; %d regs to allocate:", nregs);
1862 for (i = 0; i < max_allocno; i++)
1865 if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
1867 fprintf (file, " %d", allocno_reg[allocno_order[i]]);
1868 for (j = 0; j < max_regno; j++)
1869 if (reg_allocno[j] == allocno_order[i]
1870 && j != allocno_reg[allocno_order[i]])
1871 fprintf (file, "+%d", j);
1872 if (allocno_size[allocno_order[i]] != 1)
1873 fprintf (file, " (%d)", allocno_size[allocno_order[i]]);
1875 fprintf (file, "\n");
1877 for (i = 0; i < max_allocno; i++)
1880 fprintf (file, ";; %d conflicts:", allocno_reg[i]);
1881 for (j = 0; j < max_allocno; j++)
1882 if (CONFLICTP (j, i))
1883 fprintf (file, " %d", allocno_reg[j]);
1884 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1885 if (TEST_HARD_REG_BIT (hard_reg_conflicts[i], j))
1886 fprintf (file, " %d", j);
1887 fprintf (file, "\n");
1889 has_preferences = 0;
1890 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1891 if (TEST_HARD_REG_BIT (hard_reg_preferences[i], j))
1892 has_preferences = 1;
1894 if (! has_preferences)
1896 fprintf (file, ";; %d preferences:", allocno_reg[i]);
1897 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1898 if (TEST_HARD_REG_BIT (hard_reg_preferences[i], j))
1899 fprintf (file, " %d", j);
1900 fprintf (file, "\n");
1902 fprintf (file, "\n");
1906 dump_global_regs (file)
1911 fprintf (file, ";; Register dispositions:\n");
1912 for (i = FIRST_PSEUDO_REGISTER, j = 0; i < max_regno; i++)
1913 if (reg_renumber[i] >= 0)
1915 fprintf (file, "%d in %d ", i, reg_renumber[i]);
1917 fprintf (file, "\n");
1920 fprintf (file, "\n\n;; Hard regs used: ");
1921 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1922 if (regs_ever_live[i])
1923 fprintf (file, " %d", i);
1924 fprintf (file, "\n\n");