1 /* Allocate registers for pseudo-registers that span basic blocks.
2 Copyright (C) 1987, 1988, 1991, 1994 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, 675 Mass Ave, Cambridge, MA 02139, USA. */
25 #include "basic-block.h"
26 #include "hard-reg-set.h"
28 #include "insn-config.h"
31 /* This pass of the compiler performs global register allocation.
32 It assigns hard register numbers to all the pseudo registers
33 that were not handled in local_alloc. Assignments are recorded
34 in the vector reg_renumber, not by changing the rtl code.
35 (Such changes are made by final). The entry point is
36 the function global_alloc.
38 After allocation is complete, the reload pass is run as a subroutine
39 of this pass, so that when a pseudo reg loses its hard reg due to
40 spilling it is possible to make a second attempt to find a hard
41 reg for it. The reload pass is independent in other respects
42 and it is run even when stupid register allocation is in use.
44 1. count the pseudo-registers still needing allocation
45 and assign allocation-numbers (allocnos) to them.
46 Set up tables reg_allocno and allocno_reg to map
47 reg numbers to allocnos and vice versa.
48 max_allocno gets the number of allocnos in use.
50 2. Allocate a max_allocno by max_allocno conflict bit matrix and clear it.
51 Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix
52 for conflicts between allocnos and explicit hard register use
53 (which includes use of pseudo-registers allocated by local_alloc).
55 3. for each basic block
56 walk forward through the block, recording which
57 unallocated registers and which hardware registers are live.
58 Build the conflict matrix between the unallocated registers
59 and another of unallocated registers versus hardware registers.
60 Also record the preferred hardware registers
61 for each unallocated one.
63 4. Sort a table of the allocnos into order of
64 desirability of the variables.
66 5. Allocate the variables in that order; each if possible into
67 a preferred register, else into another register. */
69 /* Number of pseudo-registers still requiring allocation
70 (not allocated by local_allocate). */
72 static int max_allocno;
74 /* Indexed by (pseudo) reg number, gives the allocno, or -1
75 for pseudo registers already allocated by local_allocate. */
77 static int *reg_allocno;
79 /* Indexed by allocno, gives the reg number. */
81 static int *allocno_reg;
83 /* A vector of the integers from 0 to max_allocno-1,
84 sorted in the order of first-to-be-allocated first. */
86 static int *allocno_order;
88 /* Indexed by an allocno, gives the number of consecutive
89 hard registers needed by that pseudo reg. */
91 static int *allocno_size;
93 /* Indexed by (pseudo) reg number, gives the number of another
94 lower-numbered pseudo reg which can share a hard reg with this pseudo
95 *even if the two pseudos would otherwise appear to conflict*. */
97 static int *reg_may_share;
99 /* Define the number of bits in each element of `conflicts' and what
100 type that element has. We use the largest integer format on the
103 #define INT_BITS HOST_BITS_PER_WIDE_INT
104 #define INT_TYPE HOST_WIDE_INT
106 /* max_allocno by max_allocno array of bits,
107 recording whether two allocno's conflict (can't go in the same
110 `conflicts' is not symmetric; a conflict between allocno's i and j
111 is recorded either in element i,j or in element j,i. */
113 static INT_TYPE *conflicts;
115 /* Number of ints require to hold max_allocno bits.
116 This is the length of a row in `conflicts'. */
118 static int allocno_row_words;
120 /* Two macros to test or store 1 in an element of `conflicts'. */
122 #define CONFLICTP(I, J) \
123 (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
124 & ((INT_TYPE) 1 << ((J) % INT_BITS)))
126 #define SET_CONFLICT(I, J) \
127 (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
128 |= ((INT_TYPE) 1 << ((J) % INT_BITS)))
130 /* Set of hard regs currently live (during scan of all insns). */
132 static HARD_REG_SET hard_regs_live;
134 /* Indexed by N, set of hard regs conflicting with allocno N. */
136 static HARD_REG_SET *hard_reg_conflicts;
138 /* Indexed by N, set of hard regs preferred by allocno N.
139 This is used to make allocnos go into regs that are copied to or from them,
140 when possible, to reduce register shuffling. */
142 static HARD_REG_SET *hard_reg_preferences;
144 /* Similar, but just counts register preferences made in simple copy
145 operations, rather than arithmetic. These are given priority because
146 we can always eliminate an insn by using these, but using a register
147 in the above list won't always eliminate an insn. */
149 static HARD_REG_SET *hard_reg_copy_preferences;
151 /* Similar to hard_reg_preferences, but includes bits for subsequent
152 registers when an allocno is multi-word. The above variable is used for
153 allocation while this is used to build reg_someone_prefers, below. */
155 static HARD_REG_SET *hard_reg_full_preferences;
157 /* Indexed by N, set of hard registers that some later allocno has a
160 static HARD_REG_SET *regs_someone_prefers;
162 /* Set of registers that global-alloc isn't supposed to use. */
164 static HARD_REG_SET no_global_alloc_regs;
166 /* Set of registers used so far. */
168 static HARD_REG_SET regs_used_so_far;
170 /* Number of calls crossed by each allocno. */
172 static int *allocno_calls_crossed;
174 /* Number of refs (weighted) to each allocno. */
176 static int *allocno_n_refs;
178 /* Guess at live length of each allocno.
179 This is actually the max of the live lengths of the regs. */
181 static int *allocno_live_length;
183 /* Number of refs (weighted) to each hard reg, as used by local alloc.
184 It is zero for a reg that contains global pseudos or is explicitly used. */
186 static int local_reg_n_refs[FIRST_PSEUDO_REGISTER];
188 /* Guess at live length of each hard reg, as used by local alloc.
189 This is actually the sum of the live lengths of the specific regs. */
191 static int local_reg_live_length[FIRST_PSEUDO_REGISTER];
193 /* Test a bit in TABLE, a vector of HARD_REG_SETs,
194 for vector element I, and hard register number J. */
196 #define REGBITP(TABLE, I, J) TEST_HARD_REG_BIT (TABLE[I], J)
198 /* Set to 1 a bit in a vector of HARD_REG_SETs. Works like REGBITP. */
200 #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (TABLE[I], J)
202 /* Bit mask for allocnos live at current point in the scan. */
204 static INT_TYPE *allocnos_live;
206 /* Test, set or clear bit number I in allocnos_live,
207 a bit vector indexed by allocno. */
209 #define ALLOCNO_LIVE_P(I) \
210 (allocnos_live[(I) / INT_BITS] & ((INT_TYPE) 1 << ((I) % INT_BITS)))
212 #define SET_ALLOCNO_LIVE(I) \
213 (allocnos_live[(I) / INT_BITS] |= ((INT_TYPE) 1 << ((I) % INT_BITS)))
215 #define CLEAR_ALLOCNO_LIVE(I) \
216 (allocnos_live[(I) / INT_BITS] &= ~((INT_TYPE) 1 << ((I) % INT_BITS)))
218 /* This is turned off because it doesn't work right for DImode.
219 (And it is only used for DImode, so the other cases are worthless.)
220 The problem is that it isn't true that there is NO possibility of conflict;
221 only that there is no conflict if the two pseudos get the exact same regs.
222 If they were allocated with a partial overlap, there would be a conflict.
223 We can't safely turn off the conflict unless we have another way to
224 prevent the partial overlap.
226 Idea: change hard_reg_conflicts so that instead of recording which
227 hard regs the allocno may not overlap, it records where the allocno
228 may not start. Change both where it is used and where it is updated.
229 Then there is a way to record that (reg:DI 108) may start at 10
230 but not at 9 or 11. There is still the question of how to record
231 this semi-conflict between two pseudos. */
233 /* Reg pairs for which conflict after the current insn
234 is inhibited by a REG_NO_CONFLICT note.
235 If the table gets full, we ignore any other notes--that is conservative. */
236 #define NUM_NO_CONFLICT_PAIRS 4
237 /* Number of pairs in use in this insn. */
238 int n_no_conflict_pairs;
239 static struct { int allocno1, allocno2;}
240 no_conflict_pairs[NUM_NO_CONFLICT_PAIRS];
243 /* Record all regs that are set in any one insn.
244 Communication from mark_reg_{store,clobber} and global_conflicts. */
246 static rtx *regs_set;
247 static int n_regs_set;
249 /* All register that can be eliminated. */
251 static HARD_REG_SET eliminable_regset;
253 static int allocno_compare ();
254 static void mark_reg_store ();
255 static void mark_reg_clobber ();
256 static void mark_reg_conflicts ();
257 static void mark_reg_live_nc ();
258 static void mark_reg_death ();
259 static void dump_conflicts ();
260 void dump_global_regs ();
261 static void find_reg ();
262 static void global_conflicts ();
263 static void expand_preferences ();
264 static void prune_preferences ();
265 static void record_conflicts ();
266 static void set_preference ();
268 /* Perform allocation of pseudo-registers not allocated by local_alloc.
269 FILE is a file to output debugging information on,
270 or zero if such output is not desired.
272 Return value is nonzero if reload failed
273 and we must not do any more for this function. */
279 #ifdef ELIMINABLE_REGS
280 static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
287 /* A machine may have certain hard registers that
288 are safe to use only within a basic block. */
290 CLEAR_HARD_REG_SET (no_global_alloc_regs);
291 #ifdef OVERLAPPING_REGNO_P
292 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
293 if (OVERLAPPING_REGNO_P (i))
294 SET_HARD_REG_BIT (no_global_alloc_regs, i);
297 /* Build the regset of all eliminable registers and show we can't use those
298 that we already know won't be eliminated. */
299 #ifdef ELIMINABLE_REGS
300 for (i = 0; i < sizeof eliminables / sizeof eliminables[0]; i++)
302 SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from);
304 if (! CAN_ELIMINATE (eliminables[i].from, eliminables[i].to)
305 || (eliminables[i].from == HARD_FRAME_POINTER_REGNUM
306 && (! flag_omit_frame_pointer || FRAME_POINTER_REQUIRED)))
307 SET_HARD_REG_BIT (no_global_alloc_regs, eliminables[i].from);
309 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
310 if (!flag_omit_frame_pointer || FRAME_POINTER_REQUIRED)
311 SET_HARD_REG_BIT (no_global_alloc_regs, HARD_FRAME_POINTER_REGNUM);
314 SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM);
316 /* If we know we will definitely not be eliminating the frame pointer,
317 don't allocate it. */
318 if (! flag_omit_frame_pointer || FRAME_POINTER_REQUIRED)
319 SET_HARD_REG_BIT (no_global_alloc_regs, FRAME_POINTER_REGNUM);
322 /* Track which registers have already been used. Start with registers
323 explicitly in the rtl, then registers allocated by local register
326 CLEAR_HARD_REG_SET (regs_used_so_far);
327 #ifdef LEAF_REGISTERS
328 /* If we are doing the leaf function optimization, and this is a leaf
329 function, it means that the registers that take work to save are those
330 that need a register window. So prefer the ones that can be used in
334 static char leaf_regs[] = LEAF_REGISTERS;
336 if (only_leaf_regs_used () && leaf_function_p ())
337 cheap_regs = leaf_regs;
339 cheap_regs = call_used_regs;
340 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
341 if (regs_ever_live[i] || cheap_regs[i])
342 SET_HARD_REG_BIT (regs_used_so_far, i);
345 /* We consider registers that do not have to be saved over calls as if
346 they were already used since there is no cost in using them. */
347 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
348 if (regs_ever_live[i] || call_used_regs[i])
349 SET_HARD_REG_BIT (regs_used_so_far, i);
352 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
353 if (reg_renumber[i] >= 0)
354 SET_HARD_REG_BIT (regs_used_so_far, reg_renumber[i]);
356 /* Establish mappings from register number to allocation number
357 and vice versa. In the process, count the allocnos. */
359 reg_allocno = (int *) alloca (max_regno * sizeof (int));
361 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
364 /* Initialize the shared-hard-reg mapping
365 from the list of pairs that may share. */
366 reg_may_share = (int *) alloca (max_regno * sizeof (int));
367 bzero (reg_may_share, max_regno * sizeof (int));
368 for (x = regs_may_share; x; x = XEXP (XEXP (x, 1), 1))
370 int r1 = REGNO (XEXP (x, 0));
371 int r2 = REGNO (XEXP (XEXP (x, 1), 0));
373 reg_may_share[r1] = r2;
375 reg_may_share[r2] = r1;
378 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
379 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
380 that we are supposed to refrain from putting in a hard reg.
381 -2 means do make an allocno but don't allocate it. */
382 if (reg_n_refs[i] != 0 && reg_renumber[i] < 0 && reg_live_length[i] != -1
383 /* Don't allocate pseudos that cross calls,
384 if this function receives a nonlocal goto. */
385 && (! current_function_has_nonlocal_label
386 || reg_n_calls_crossed[i] == 0))
388 if (reg_may_share[i] && reg_allocno[reg_may_share[i]] >= 0)
389 reg_allocno[i] = reg_allocno[reg_may_share[i]];
391 reg_allocno[i] = max_allocno++;
392 if (reg_live_length[i] == 0)
398 allocno_reg = (int *) alloca (max_allocno * sizeof (int));
399 allocno_size = (int *) alloca (max_allocno * sizeof (int));
400 allocno_calls_crossed = (int *) alloca (max_allocno * sizeof (int));
401 allocno_n_refs = (int *) alloca (max_allocno * sizeof (int));
402 allocno_live_length = (int *) alloca (max_allocno * sizeof (int));
403 bzero (allocno_size, max_allocno * sizeof (int));
404 bzero (allocno_calls_crossed, max_allocno * sizeof (int));
405 bzero (allocno_n_refs, max_allocno * sizeof (int));
406 bzero (allocno_live_length, max_allocno * sizeof (int));
408 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
409 if (reg_allocno[i] >= 0)
411 int allocno = reg_allocno[i];
412 allocno_reg[allocno] = i;
413 allocno_size[allocno] = PSEUDO_REGNO_SIZE (i);
414 allocno_calls_crossed[allocno] += reg_n_calls_crossed[i];
415 allocno_n_refs[allocno] += reg_n_refs[i];
416 if (allocno_live_length[allocno] < reg_live_length[i])
417 allocno_live_length[allocno] = reg_live_length[i];
420 /* Calculate amount of usage of each hard reg by pseudos
421 allocated by local-alloc. This is to see if we want to
423 bzero (local_reg_live_length, sizeof local_reg_live_length);
424 bzero (local_reg_n_refs, sizeof local_reg_n_refs);
425 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
426 if (reg_allocno[i] < 0 && reg_renumber[i] >= 0)
428 int regno = reg_renumber[i];
429 int endregno = regno + HARD_REGNO_NREGS (regno, PSEUDO_REGNO_MODE (i));
432 for (j = regno; j < endregno; j++)
434 local_reg_n_refs[j] += reg_n_refs[i];
435 local_reg_live_length[j] += reg_live_length[i];
439 /* We can't override local-alloc for a reg used not just by local-alloc. */
440 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
441 if (regs_ever_live[i])
442 local_reg_n_refs[i] = 0;
444 /* Allocate the space for the conflict and preference tables and
448 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
449 bzero (hard_reg_conflicts, max_allocno * sizeof (HARD_REG_SET));
452 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
453 bzero (hard_reg_preferences, max_allocno * sizeof (HARD_REG_SET));
455 hard_reg_copy_preferences
456 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
457 bzero (hard_reg_copy_preferences, max_allocno * sizeof (HARD_REG_SET));
459 hard_reg_full_preferences
460 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
461 bzero (hard_reg_full_preferences, max_allocno * sizeof (HARD_REG_SET));
464 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
465 bzero (regs_someone_prefers, max_allocno * sizeof (HARD_REG_SET));
467 allocno_row_words = (max_allocno + INT_BITS - 1) / INT_BITS;
469 conflicts = (INT_TYPE *) alloca (max_allocno * allocno_row_words
470 * sizeof (INT_TYPE));
471 bzero (conflicts, max_allocno * allocno_row_words
472 * sizeof (INT_TYPE));
474 allocnos_live = (INT_TYPE *) alloca (allocno_row_words * sizeof (INT_TYPE));
476 /* If there is work to be done (at least one reg to allocate),
477 perform global conflict analysis and allocate the regs. */
481 /* Scan all the insns and compute the conflicts among allocnos
482 and between allocnos and hard regs. */
486 /* Eliminate conflicts between pseudos and eliminable registers. If
487 the register is not eliminated, the pseudo won't really be able to
488 live in the eliminable register, so the conflict doesn't matter.
489 If we do eliminate the register, the conflict will no longer exist.
490 So in either case, we can ignore the conflict. Likewise for
493 for (i = 0; i < max_allocno; i++)
495 AND_COMPL_HARD_REG_SET (hard_reg_conflicts[i], eliminable_regset);
496 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[i],
498 AND_COMPL_HARD_REG_SET (hard_reg_preferences[i], eliminable_regset);
501 /* Try to expand the preferences by merging them between allocnos. */
503 expand_preferences ();
505 /* Determine the order to allocate the remaining pseudo registers. */
507 allocno_order = (int *) alloca (max_allocno * sizeof (int));
508 for (i = 0; i < max_allocno; i++)
509 allocno_order[i] = i;
511 /* Default the size to 1, since allocno_compare uses it to divide by.
512 Also convert allocno_live_length of zero to -1. A length of zero
513 can occur when all the registers for that allocno have reg_live_length
514 equal to -2. In this case, we want to make an allocno, but not
515 allocate it. So avoid the divide-by-zero and set it to a low
518 for (i = 0; i < max_allocno; i++)
520 if (allocno_size[i] == 0)
522 if (allocno_live_length[i] == 0)
523 allocno_live_length[i] = -1;
526 qsort (allocno_order, max_allocno, sizeof (int), allocno_compare);
528 prune_preferences ();
531 dump_conflicts (file);
533 /* Try allocating them, one by one, in that order,
534 except for parameters marked with reg_live_length[regno] == -2. */
536 for (i = 0; i < max_allocno; i++)
537 if (reg_live_length[allocno_reg[allocno_order[i]]] >= 0)
539 /* If we have more than one register class,
540 first try allocating in the class that is cheapest
541 for this pseudo-reg. If that fails, try any reg. */
542 if (N_REG_CLASSES > 1)
544 find_reg (allocno_order[i], HARD_CONST (0), 0, 0, 0);
545 if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
548 if (reg_alternate_class (allocno_reg[allocno_order[i]]) != NO_REGS)
549 find_reg (allocno_order[i], HARD_CONST (0), 1, 0, 0);
553 /* Do the reloads now while the allocno data still exist, so that we can
554 try to assign new hard regs to any pseudo regs that are spilled. */
556 #if 0 /* We need to eliminate regs even if there is no rtl code,
557 for the sake of debugging information. */
558 if (n_basic_blocks > 0)
560 return reload (get_insns (), 1, file);
563 /* Sort predicate for ordering the allocnos.
564 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
567 allocno_compare (v1, v2)
570 /* Note that the quotient will never be bigger than
571 the value of floor_log2 times the maximum number of
572 times a register can occur in one insn (surely less than 100).
573 Multiplying this by 10000 can't overflow. */
575 = (((double) (floor_log2 (allocno_n_refs[*v1]) * allocno_n_refs[*v1])
576 / allocno_live_length[*v1])
577 * 10000 * allocno_size[*v1]);
579 = (((double) (floor_log2 (allocno_n_refs[*v2]) * allocno_n_refs[*v2])
580 / allocno_live_length[*v2])
581 * 10000 * allocno_size[*v2]);
585 /* If regs are equally good, sort by allocno,
586 so that the results of qsort leave nothing to chance. */
590 /* Scan the rtl code and record all conflicts and register preferences in the
591 conflict matrices and preference tables. */
598 short *block_start_allocnos;
600 /* Make a vector that mark_reg_{store,clobber} will store in. */
601 regs_set = (rtx *) alloca (max_parallel * sizeof (rtx) * 2);
603 block_start_allocnos = (short *) alloca (max_allocno * sizeof (short));
605 for (b = 0; b < n_basic_blocks; b++)
607 bzero (allocnos_live, allocno_row_words * sizeof (INT_TYPE));
609 /* Initialize table of registers currently live
610 to the state at the beginning of this basic block.
611 This also marks the conflicts among them.
613 For pseudo-regs, there is only one bit for each one
614 no matter how many hard regs it occupies.
615 This is ok; we know the size from PSEUDO_REGNO_SIZE.
616 For explicit hard regs, we cannot know the size that way
617 since one hard reg can be used with various sizes.
618 Therefore, we must require that all the hard regs
619 implicitly live as part of a multi-word hard reg
620 are explicitly marked in basic_block_live_at_start. */
625 register regset old = basic_block_live_at_start[b];
628 COPY_HARD_REG_SET (hard_regs_live, old[0]);
630 for (offset = 0, i = 0; offset < regset_size; offset++)
631 if (old[offset] == 0)
632 i += REGSET_ELT_BITS;
634 for (bit = 1; bit; bit <<= 1, i++)
638 if (old[offset] & bit)
640 register int a = reg_allocno[i];
643 SET_ALLOCNO_LIVE (a);
644 block_start_allocnos[ax++] = a;
646 else if ((a = reg_renumber[i]) >= 0)
647 mark_reg_live_nc (a, PSEUDO_REGNO_MODE (i));
651 /* Record that each allocno now live conflicts with each other
652 allocno now live, and with each hard reg now live. */
654 record_conflicts (block_start_allocnos, ax);
657 insn = basic_block_head[b];
659 /* Scan the code of this basic block, noting which allocnos
660 and hard regs are born or die. When one is born,
661 record a conflict with all others currently live. */
665 register RTX_CODE code = GET_CODE (insn);
668 /* Make regs_set an empty set. */
672 if (code == INSN || code == CALL_INSN || code == JUMP_INSN)
677 for (link = REG_NOTES (insn);
678 link && i < NUM_NO_CONFLICT_PAIRS;
679 link = XEXP (link, 1))
680 if (REG_NOTE_KIND (link) == REG_NO_CONFLICT)
682 no_conflict_pairs[i].allocno1
683 = reg_allocno[REGNO (SET_DEST (PATTERN (insn)))];
684 no_conflict_pairs[i].allocno2
685 = reg_allocno[REGNO (XEXP (link, 0))];
690 /* Mark any registers clobbered by INSN as live,
691 so they conflict with the inputs. */
693 note_stores (PATTERN (insn), mark_reg_clobber);
695 /* Mark any registers dead after INSN as dead now. */
697 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
698 if (REG_NOTE_KIND (link) == REG_DEAD)
699 mark_reg_death (XEXP (link, 0));
701 /* Mark any registers set in INSN as live,
702 and mark them as conflicting with all other live regs.
703 Clobbers are processed again, so they conflict with
704 the registers that are set. */
706 note_stores (PATTERN (insn), mark_reg_store);
709 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
710 if (REG_NOTE_KIND (link) == REG_INC)
711 mark_reg_store (XEXP (link, 0), NULL_RTX);
714 /* If INSN has multiple outputs, then any reg that dies here
715 and is used inside of an output
716 must conflict with the other outputs. */
718 if (GET_CODE (PATTERN (insn)) == PARALLEL && !single_set (insn))
719 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
720 if (REG_NOTE_KIND (link) == REG_DEAD)
722 int used_in_output = 0;
724 rtx reg = XEXP (link, 0);
726 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
728 rtx set = XVECEXP (PATTERN (insn), 0, i);
729 if (GET_CODE (set) == SET
730 && GET_CODE (SET_DEST (set)) != REG
731 && !rtx_equal_p (reg, SET_DEST (set))
732 && reg_overlap_mentioned_p (reg, SET_DEST (set)))
736 mark_reg_conflicts (reg);
739 /* Mark any registers set in INSN and then never used. */
741 while (n_regs_set > 0)
742 if (find_regno_note (insn, REG_UNUSED,
743 REGNO (regs_set[--n_regs_set])))
744 mark_reg_death (regs_set[n_regs_set]);
747 if (insn == basic_block_end[b])
749 insn = NEXT_INSN (insn);
753 /* Expand the preference information by looking for cases where one allocno
754 dies in an insn that sets an allocno. If those two allocnos don't conflict,
755 merge any preferences between those allocnos. */
758 expand_preferences ()
764 /* We only try to handle the most common cases here. Most of the cases
765 where this wins are reg-reg copies. */
767 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
768 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
769 && (set = single_set (insn)) != 0
770 && GET_CODE (SET_DEST (set)) == REG
771 && reg_allocno[REGNO (SET_DEST (set))] >= 0)
772 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
773 if (REG_NOTE_KIND (link) == REG_DEAD
774 && GET_CODE (XEXP (link, 0)) == REG
775 && reg_allocno[REGNO (XEXP (link, 0))] >= 0
776 && ! CONFLICTP (reg_allocno[REGNO (SET_DEST (set))],
777 reg_allocno[REGNO (XEXP (link, 0))])
778 && ! CONFLICTP (reg_allocno[REGNO (XEXP (link, 0))],
779 reg_allocno[REGNO (SET_DEST (set))]))
781 int a1 = reg_allocno[REGNO (SET_DEST (set))];
782 int a2 = reg_allocno[REGNO (XEXP (link, 0))];
784 if (XEXP (link, 0) == SET_SRC (set))
786 IOR_HARD_REG_SET (hard_reg_copy_preferences[a1],
787 hard_reg_copy_preferences[a2]);
788 IOR_HARD_REG_SET (hard_reg_copy_preferences[a2],
789 hard_reg_copy_preferences[a1]);
792 IOR_HARD_REG_SET (hard_reg_preferences[a1],
793 hard_reg_preferences[a2]);
794 IOR_HARD_REG_SET (hard_reg_preferences[a2],
795 hard_reg_preferences[a1]);
796 IOR_HARD_REG_SET (hard_reg_full_preferences[a1],
797 hard_reg_full_preferences[a2]);
798 IOR_HARD_REG_SET (hard_reg_full_preferences[a2],
799 hard_reg_full_preferences[a1]);
803 /* Prune the preferences for global registers to exclude registers that cannot
806 Compute `regs_someone_prefers', which is a bitmask of the hard registers
807 that are preferred by conflicting registers of lower priority. If possible,
808 we will avoid using these registers. */
816 /* Scan least most important to most important.
817 For each allocno, remove from preferences registers that cannot be used,
818 either because of conflicts or register type. Then compute all registers
819 preferred by each lower-priority register that conflicts. */
821 for (i = max_allocno - 1; i >= 0; i--)
825 allocno = allocno_order[i];
826 COPY_HARD_REG_SET (temp, hard_reg_conflicts[allocno]);
828 if (allocno_calls_crossed[allocno] == 0)
829 IOR_HARD_REG_SET (temp, fixed_reg_set);
831 IOR_HARD_REG_SET (temp, call_used_reg_set);
833 IOR_COMPL_HARD_REG_SET
835 reg_class_contents[(int) reg_preferred_class (allocno_reg[allocno])]);
837 AND_COMPL_HARD_REG_SET (hard_reg_preferences[allocno], temp);
838 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[allocno], temp);
839 AND_COMPL_HARD_REG_SET (hard_reg_full_preferences[allocno], temp);
841 CLEAR_HARD_REG_SET (regs_someone_prefers[allocno]);
843 /* Merge in the preferences of lower-priority registers (they have
844 already been pruned). If we also prefer some of those registers,
845 don't exclude them unless we are of a smaller size (in which case
846 we want to give the lower-priority allocno the first chance for
848 for (j = i + 1; j < max_allocno; j++)
849 if (CONFLICTP (allocno, allocno_order[j]))
851 COPY_HARD_REG_SET (temp,
852 hard_reg_full_preferences[allocno_order[j]]);
853 if (allocno_size[allocno_order[j]] <= allocno_size[allocno])
854 AND_COMPL_HARD_REG_SET (temp,
855 hard_reg_full_preferences[allocno]);
857 IOR_HARD_REG_SET (regs_someone_prefers[allocno], temp);
862 /* Assign a hard register to ALLOCNO; look for one that is the beginning
863 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
864 The registers marked in PREFREGS are tried first.
866 LOSERS, if non-zero, is a HARD_REG_SET indicating registers that cannot
867 be used for this allocation.
869 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
870 Otherwise ignore that preferred class and use the alternate class.
872 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
873 will have to be saved and restored at calls.
875 RETRYING is nonzero if this is called from retry_global_alloc.
877 If we find one, record it in reg_renumber.
878 If not, do nothing. */
881 find_reg (allocno, losers, alt_regs_p, accept_call_clobbered, retrying)
885 int accept_call_clobbered;
888 register int i, best_reg, pass;
890 register /* Declare it register if it's a scalar. */
892 HARD_REG_SET used, used1, used2;
894 enum reg_class class = (alt_regs_p
895 ? reg_alternate_class (allocno_reg[allocno])
896 : reg_preferred_class (allocno_reg[allocno]));
897 enum machine_mode mode = PSEUDO_REGNO_MODE (allocno_reg[allocno]);
899 if (accept_call_clobbered)
900 COPY_HARD_REG_SET (used1, call_fixed_reg_set);
901 else if (allocno_calls_crossed[allocno] == 0)
902 COPY_HARD_REG_SET (used1, fixed_reg_set);
904 COPY_HARD_REG_SET (used1, call_used_reg_set);
906 /* Some registers should not be allocated in global-alloc. */
907 IOR_HARD_REG_SET (used1, no_global_alloc_regs);
909 IOR_HARD_REG_SET (used1, losers);
911 IOR_COMPL_HARD_REG_SET (used1, reg_class_contents[(int) class]);
912 COPY_HARD_REG_SET (used2, used1);
914 IOR_HARD_REG_SET (used1, hard_reg_conflicts[allocno]);
916 /* Try each hard reg to see if it fits. Do this in two passes.
917 In the first pass, skip registers that are preferred by some other pseudo
918 to give it a better chance of getting one of those registers. Only if
919 we can't get a register when excluding those do we take one of them.
920 However, we never allocate a register for the first time in pass 0. */
922 COPY_HARD_REG_SET (used, used1);
923 IOR_COMPL_HARD_REG_SET (used, regs_used_so_far);
924 IOR_HARD_REG_SET (used, regs_someone_prefers[allocno]);
927 for (i = FIRST_PSEUDO_REGISTER, pass = 0;
928 pass <= 1 && i >= FIRST_PSEUDO_REGISTER;
932 COPY_HARD_REG_SET (used, used1);
933 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
935 #ifdef REG_ALLOC_ORDER
936 int regno = reg_alloc_order[i];
940 if (! TEST_HARD_REG_BIT (used, regno)
941 && HARD_REGNO_MODE_OK (regno, mode))
944 register int lim = regno + HARD_REGNO_NREGS (regno, mode);
947 && ! TEST_HARD_REG_BIT (used, j));
954 #ifndef REG_ALLOC_ORDER
955 i = j; /* Skip starting points we know will lose */
961 /* See if there is a preferred register with the same class as the register
962 we allocated above. Making this restriction prevents register
963 preferencing from creating worse register allocation.
965 Remove from the preferred registers and conflicting registers. Note that
966 additional conflicts may have been added after `prune_preferences' was
969 First do this for those register with copy preferences, then all
970 preferred registers. */
972 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[allocno], used);
973 GO_IF_HARD_REG_SUBSET (hard_reg_copy_preferences[allocno],
974 reg_class_contents[(int) NO_REGS], no_copy_prefs);
978 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
979 if (TEST_HARD_REG_BIT (hard_reg_copy_preferences[allocno], i)
980 && HARD_REGNO_MODE_OK (i, mode)
981 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
982 || reg_class_subset_p (REGNO_REG_CLASS (i),
983 REGNO_REG_CLASS (best_reg))
984 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
985 REGNO_REG_CLASS (i))))
988 register int lim = i + HARD_REGNO_NREGS (i, mode);
991 && ! TEST_HARD_REG_BIT (used, j)
992 && (REGNO_REG_CLASS (j)
993 == REGNO_REG_CLASS (best_reg + (j - i))
994 || reg_class_subset_p (REGNO_REG_CLASS (j),
995 REGNO_REG_CLASS (best_reg + (j - i)))
996 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
997 REGNO_REG_CLASS (j))));
1008 AND_COMPL_HARD_REG_SET (hard_reg_preferences[allocno], used);
1009 GO_IF_HARD_REG_SUBSET (hard_reg_preferences[allocno],
1010 reg_class_contents[(int) NO_REGS], no_prefs);
1014 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1015 if (TEST_HARD_REG_BIT (hard_reg_preferences[allocno], i)
1016 && HARD_REGNO_MODE_OK (i, mode)
1017 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1018 || reg_class_subset_p (REGNO_REG_CLASS (i),
1019 REGNO_REG_CLASS (best_reg))
1020 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1021 REGNO_REG_CLASS (i))))
1024 register int lim = i + HARD_REGNO_NREGS (i, mode);
1027 && ! TEST_HARD_REG_BIT (used, j)
1028 && (REGNO_REG_CLASS (j)
1029 == REGNO_REG_CLASS (best_reg + (j - i))
1030 || reg_class_subset_p (REGNO_REG_CLASS (j),
1031 REGNO_REG_CLASS (best_reg + (j - i)))
1032 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1033 REGNO_REG_CLASS (j))));
1044 /* If we haven't succeeded yet, try with caller-saves.
1045 We need not check to see if the current function has nonlocal
1046 labels because we don't put any pseudos that are live over calls in
1047 registers in that case. */
1049 if (flag_caller_saves && best_reg < 0)
1051 /* Did not find a register. If it would be profitable to
1052 allocate a call-clobbered register and save and restore it
1053 around calls, do that. */
1054 if (! accept_call_clobbered
1055 && allocno_calls_crossed[allocno] != 0
1056 && CALLER_SAVE_PROFITABLE (allocno_n_refs[allocno],
1057 allocno_calls_crossed[allocno]))
1059 find_reg (allocno, losers, alt_regs_p, 1, retrying);
1060 if (reg_renumber[allocno_reg[allocno]] >= 0)
1062 caller_save_needed = 1;
1068 /* If we haven't succeeded yet,
1069 see if some hard reg that conflicts with us
1070 was utilized poorly by local-alloc.
1071 If so, kick out the regs that were put there by local-alloc
1072 so we can use it instead. */
1073 if (best_reg < 0 && !retrying
1074 /* Let's not bother with multi-reg allocnos. */
1075 && allocno_size[allocno] == 1)
1077 /* Count from the end, to find the least-used ones first. */
1078 for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1079 if (local_reg_n_refs[i] != 0
1080 /* Don't use a reg no good for this pseudo. */
1081 && ! TEST_HARD_REG_BIT (used2, i)
1082 && HARD_REGNO_MODE_OK (i, mode)
1083 && ((double) local_reg_n_refs[i] / local_reg_live_length[i]
1084 < ((double) allocno_n_refs[allocno]
1085 / allocno_live_length[allocno])))
1087 /* Hard reg I was used less in total by local regs
1088 than it would be used by this one allocno! */
1090 for (k = 0; k < max_regno; k++)
1091 if (reg_renumber[k] >= 0)
1093 int regno = reg_renumber[k];
1095 = regno + HARD_REGNO_NREGS (regno, PSEUDO_REGNO_MODE (k));
1097 if (i >= regno && i < endregno)
1098 reg_renumber[k] = -1;
1106 /* Did we find a register? */
1110 register int lim, j;
1111 HARD_REG_SET this_reg;
1113 /* Yes. Record it as the hard register of this pseudo-reg. */
1114 reg_renumber[allocno_reg[allocno]] = best_reg;
1115 /* Also of any pseudo-regs that share with it. */
1116 if (reg_may_share[allocno_reg[allocno]])
1117 for (j = FIRST_PSEUDO_REGISTER; j < max_regno; j++)
1118 if (reg_allocno[j] == allocno)
1119 reg_renumber[j] = best_reg;
1121 /* Make a set of the hard regs being allocated. */
1122 CLEAR_HARD_REG_SET (this_reg);
1123 lim = best_reg + HARD_REGNO_NREGS (best_reg, mode);
1124 for (j = best_reg; j < lim; j++)
1126 SET_HARD_REG_BIT (this_reg, j);
1127 SET_HARD_REG_BIT (regs_used_so_far, j);
1128 /* This is no longer a reg used just by local regs. */
1129 local_reg_n_refs[j] = 0;
1131 /* For each other pseudo-reg conflicting with this one,
1132 mark it as conflicting with the hard regs this one occupies. */
1134 for (j = 0; j < max_allocno; j++)
1135 if (CONFLICTP (lim, j) || CONFLICTP (j, lim))
1137 IOR_HARD_REG_SET (hard_reg_conflicts[j], this_reg);
1142 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1143 Perhaps it had previously seemed not worth a hard reg,
1144 or perhaps its old hard reg has been commandeered for reloads.
1145 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1146 they do not appear to be allocated.
1147 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1150 retry_global_alloc (regno, forbidden_regs)
1152 HARD_REG_SET forbidden_regs;
1154 int allocno = reg_allocno[regno];
1157 /* If we have more than one register class,
1158 first try allocating in the class that is cheapest
1159 for this pseudo-reg. If that fails, try any reg. */
1160 if (N_REG_CLASSES > 1)
1161 find_reg (allocno, forbidden_regs, 0, 0, 1);
1162 if (reg_renumber[regno] < 0
1163 && reg_alternate_class (regno) != NO_REGS)
1164 find_reg (allocno, forbidden_regs, 1, 0, 1);
1166 /* If we found a register, modify the RTL for the register to
1167 show the hard register, and mark that register live. */
1168 if (reg_renumber[regno] >= 0)
1170 REGNO (regno_reg_rtx[regno]) = reg_renumber[regno];
1171 mark_home_live (regno);
1176 /* Record a conflict between register REGNO
1177 and everything currently live.
1178 REGNO must not be a pseudo reg that was allocated
1179 by local_alloc; such numbers must be translated through
1180 reg_renumber before calling here. */
1183 record_one_conflict (regno)
1188 if (regno < FIRST_PSEUDO_REGISTER)
1189 /* When a hard register becomes live,
1190 record conflicts with live pseudo regs. */
1191 for (j = 0; j < max_allocno; j++)
1193 if (ALLOCNO_LIVE_P (j))
1194 SET_HARD_REG_BIT (hard_reg_conflicts[j], regno);
1197 /* When a pseudo-register becomes live,
1198 record conflicts first with hard regs,
1199 then with other pseudo regs. */
1201 register int ialloc = reg_allocno[regno];
1202 register int ialloc_prod = ialloc * allocno_row_words;
1203 IOR_HARD_REG_SET (hard_reg_conflicts[ialloc], hard_regs_live);
1204 for (j = allocno_row_words - 1; j >= 0; j--)
1208 for (k = 0; k < n_no_conflict_pairs; k++)
1209 if (! ((j == no_conflict_pairs[k].allocno1
1210 && ialloc == no_conflict_pairs[k].allocno2)
1212 (j == no_conflict_pairs[k].allocno2
1213 && ialloc == no_conflict_pairs[k].allocno1)))
1215 conflicts[ialloc_prod + j] |= allocnos_live[j];
1220 /* Record all allocnos currently live as conflicting
1221 with each other and with all hard regs currently live.
1222 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1223 are currently live. Their bits are also flagged in allocnos_live. */
1226 record_conflicts (allocno_vec, len)
1227 register short *allocno_vec;
1230 register int allocno;
1232 register int ialloc_prod;
1236 allocno = allocno_vec[len];
1237 ialloc_prod = allocno * allocno_row_words;
1238 IOR_HARD_REG_SET (hard_reg_conflicts[allocno], hard_regs_live);
1239 for (j = allocno_row_words - 1; j >= 0; j--)
1240 conflicts[ialloc_prod + j] |= allocnos_live[j];
1244 /* Handle the case where REG is set by the insn being scanned,
1245 during the forward scan to accumulate conflicts.
1246 Store a 1 in regs_live or allocnos_live for this register, record how many
1247 consecutive hardware registers it actually needs,
1248 and record a conflict with all other registers already live.
1250 Note that even if REG does not remain alive after this insn,
1251 we must mark it here as live, to ensure a conflict between
1252 REG and any other regs set in this insn that really do live.
1253 This is because those other regs could be considered after this.
1255 REG might actually be something other than a register;
1256 if so, we do nothing.
1258 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1259 a REG_INC note was found for it).
1261 CLOBBERs are processed here by calling mark_reg_clobber. */
1264 mark_reg_store (orig_reg, setter)
1265 rtx orig_reg, setter;
1268 register rtx reg = orig_reg;
1270 /* WORD is which word of a multi-register group is being stored.
1271 For the case where the store is actually into a SUBREG of REG.
1272 Except we don't use it; I believe the entire REG needs to be
1276 if (GET_CODE (reg) == SUBREG)
1278 word = SUBREG_WORD (reg);
1279 reg = SUBREG_REG (reg);
1282 if (GET_CODE (reg) != REG)
1285 if (setter && GET_CODE (setter) == CLOBBER)
1287 /* A clobber of a register should be processed here too. */
1288 mark_reg_clobber (orig_reg, setter);
1292 regs_set[n_regs_set++] = reg;
1295 set_preference (reg, SET_SRC (setter));
1297 regno = REGNO (reg);
1299 if (reg_renumber[regno] >= 0)
1300 regno = reg_renumber[regno] /* + word */;
1302 /* Either this is one of the max_allocno pseudo regs not allocated,
1303 or it is or has a hardware reg. First handle the pseudo-regs. */
1304 if (regno >= FIRST_PSEUDO_REGISTER)
1306 if (reg_allocno[regno] >= 0)
1308 SET_ALLOCNO_LIVE (reg_allocno[regno]);
1309 record_one_conflict (regno);
1312 /* Handle hardware regs (and pseudos allocated to hard regs). */
1313 else if (! fixed_regs[regno])
1315 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1316 while (regno < last)
1318 record_one_conflict (regno);
1319 SET_HARD_REG_BIT (hard_regs_live, regno);
1325 /* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
1328 mark_reg_clobber (reg, setter)
1333 /* WORD is which word of a multi-register group is being stored.
1334 For the case where the store is actually into a SUBREG of REG.
1335 Except we don't use it; I believe the entire REG needs to be
1339 if (GET_CODE (setter) != CLOBBER)
1342 if (GET_CODE (reg) == SUBREG)
1344 word = SUBREG_WORD (reg);
1345 reg = SUBREG_REG (reg);
1348 if (GET_CODE (reg) != REG)
1351 regs_set[n_regs_set++] = reg;
1353 regno = REGNO (reg);
1355 if (reg_renumber[regno] >= 0)
1356 regno = reg_renumber[regno] /* + word */;
1358 /* Either this is one of the max_allocno pseudo regs not allocated,
1359 or it is or has a hardware reg. First handle the pseudo-regs. */
1360 if (regno >= FIRST_PSEUDO_REGISTER)
1362 if (reg_allocno[regno] >= 0)
1364 SET_ALLOCNO_LIVE (reg_allocno[regno]);
1365 record_one_conflict (regno);
1368 /* Handle hardware regs (and pseudos allocated to hard regs). */
1369 else if (! fixed_regs[regno])
1371 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1372 while (regno < last)
1374 record_one_conflict (regno);
1375 SET_HARD_REG_BIT (hard_regs_live, regno);
1381 /* Record that REG has conflicts with all the regs currently live.
1382 Do not mark REG itself as live. */
1385 mark_reg_conflicts (reg)
1390 if (GET_CODE (reg) == SUBREG)
1391 reg = SUBREG_REG (reg);
1393 if (GET_CODE (reg) != REG)
1396 regno = REGNO (reg);
1398 if (reg_renumber[regno] >= 0)
1399 regno = reg_renumber[regno];
1401 /* Either this is one of the max_allocno pseudo regs not allocated,
1402 or it is or has a hardware reg. First handle the pseudo-regs. */
1403 if (regno >= FIRST_PSEUDO_REGISTER)
1405 if (reg_allocno[regno] >= 0)
1406 record_one_conflict (regno);
1408 /* Handle hardware regs (and pseudos allocated to hard regs). */
1409 else if (! fixed_regs[regno])
1411 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1412 while (regno < last)
1414 record_one_conflict (regno);
1420 /* Mark REG as being dead (following the insn being scanned now).
1421 Store a 0 in regs_live or allocnos_live for this register. */
1424 mark_reg_death (reg)
1427 register int regno = REGNO (reg);
1429 /* For pseudo reg, see if it has been assigned a hardware reg. */
1430 if (reg_renumber[regno] >= 0)
1431 regno = reg_renumber[regno];
1433 /* Either this is one of the max_allocno pseudo regs not allocated,
1434 or it is a hardware reg. First handle the pseudo-regs. */
1435 if (regno >= FIRST_PSEUDO_REGISTER)
1437 if (reg_allocno[regno] >= 0)
1438 CLEAR_ALLOCNO_LIVE (reg_allocno[regno]);
1440 /* Handle hardware regs (and pseudos allocated to hard regs). */
1441 else if (! fixed_regs[regno])
1443 /* Pseudo regs already assigned hardware regs are treated
1444 almost the same as explicit hardware regs. */
1445 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1446 while (regno < last)
1448 CLEAR_HARD_REG_BIT (hard_regs_live, regno);
1454 /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1455 for the value stored in it. MODE determines how many consecutive
1456 registers are actually in use. Do not record conflicts;
1457 it is assumed that the caller will do that. */
1460 mark_reg_live_nc (regno, mode)
1462 enum machine_mode mode;
1464 register int last = regno + HARD_REGNO_NREGS (regno, mode);
1465 while (regno < last)
1467 SET_HARD_REG_BIT (hard_regs_live, regno);
1472 /* Try to set a preference for an allocno to a hard register.
1473 We are passed DEST and SRC which are the operands of a SET. It is known
1474 that SRC is a register. If SRC or the first operand of SRC is a register,
1475 try to set a preference. If one of the two is a hard register and the other
1476 is a pseudo-register, mark the preference.
1478 Note that we are not as aggressive as local-alloc in trying to tie a
1479 pseudo-register to a hard register. */
1482 set_preference (dest, src)
1485 int src_regno, dest_regno;
1486 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1487 to compensate for subregs in SRC or DEST. */
1492 if (GET_RTX_FORMAT (GET_CODE (src))[0] == 'e')
1493 src = XEXP (src, 0), copy = 0;
1495 /* Get the reg number for both SRC and DEST.
1496 If neither is a reg, give up. */
1498 if (GET_CODE (src) == REG)
1499 src_regno = REGNO (src);
1500 else if (GET_CODE (src) == SUBREG && GET_CODE (SUBREG_REG (src)) == REG)
1502 src_regno = REGNO (SUBREG_REG (src));
1503 offset += SUBREG_WORD (src);
1508 if (GET_CODE (dest) == REG)
1509 dest_regno = REGNO (dest);
1510 else if (GET_CODE (dest) == SUBREG && GET_CODE (SUBREG_REG (dest)) == REG)
1512 dest_regno = REGNO (SUBREG_REG (dest));
1513 offset -= SUBREG_WORD (dest);
1518 /* Convert either or both to hard reg numbers. */
1520 if (reg_renumber[src_regno] >= 0)
1521 src_regno = reg_renumber[src_regno];
1523 if (reg_renumber[dest_regno] >= 0)
1524 dest_regno = reg_renumber[dest_regno];
1526 /* Now if one is a hard reg and the other is a global pseudo
1527 then give the other a preference. */
1529 if (dest_regno < FIRST_PSEUDO_REGISTER && src_regno >= FIRST_PSEUDO_REGISTER
1530 && reg_allocno[src_regno] >= 0)
1532 dest_regno -= offset;
1533 if (dest_regno >= 0 && dest_regno < FIRST_PSEUDO_REGISTER)
1536 SET_REGBIT (hard_reg_copy_preferences,
1537 reg_allocno[src_regno], dest_regno);
1539 SET_REGBIT (hard_reg_preferences,
1540 reg_allocno[src_regno], dest_regno);
1541 for (i = dest_regno;
1542 i < dest_regno + HARD_REGNO_NREGS (dest_regno, GET_MODE (dest));
1544 SET_REGBIT (hard_reg_full_preferences, reg_allocno[src_regno], i);
1548 if (src_regno < FIRST_PSEUDO_REGISTER && dest_regno >= FIRST_PSEUDO_REGISTER
1549 && reg_allocno[dest_regno] >= 0)
1551 src_regno += offset;
1552 if (src_regno >= 0 && src_regno < FIRST_PSEUDO_REGISTER)
1555 SET_REGBIT (hard_reg_copy_preferences,
1556 reg_allocno[dest_regno], src_regno);
1558 SET_REGBIT (hard_reg_preferences,
1559 reg_allocno[dest_regno], src_regno);
1561 i < src_regno + HARD_REGNO_NREGS (src_regno, GET_MODE (src));
1563 SET_REGBIT (hard_reg_full_preferences, reg_allocno[dest_regno], i);
1568 /* Indicate that hard register number FROM was eliminated and replaced with
1569 an offset from hard register number TO. The status of hard registers live
1570 at the start of a basic block is updated by replacing a use of FROM with
1574 mark_elimination (from, to)
1579 for (i = 0; i < n_basic_blocks; i++)
1580 if ((basic_block_live_at_start[i][from / REGSET_ELT_BITS]
1581 & ((REGSET_ELT_TYPE) 1 << (from % REGSET_ELT_BITS))) != 0)
1583 basic_block_live_at_start[i][from / REGSET_ELT_BITS]
1584 &= ~ ((REGSET_ELT_TYPE) 1 << (from % REGSET_ELT_BITS));
1585 basic_block_live_at_start[i][to / REGSET_ELT_BITS]
1586 |= ((REGSET_ELT_TYPE) 1 << (to % REGSET_ELT_BITS));
1590 /* Print debugging trace information if -greg switch is given,
1591 showing the information on which the allocation decisions are based. */
1594 dump_conflicts (file)
1598 register int has_preferences;
1599 fprintf (file, ";; %d regs to allocate:", max_allocno);
1600 for (i = 0; i < max_allocno; i++)
1603 fprintf (file, " %d", allocno_reg[allocno_order[i]]);
1604 for (j = 0; j < max_regno; j++)
1605 if (reg_allocno[j] == allocno_order[i]
1606 && j != allocno_reg[allocno_order[i]])
1607 fprintf (file, "+%d", j);
1608 if (allocno_size[allocno_order[i]] != 1)
1609 fprintf (file, " (%d)", allocno_size[allocno_order[i]]);
1611 fprintf (file, "\n");
1613 for (i = 0; i < max_allocno; i++)
1616 fprintf (file, ";; %d conflicts:", allocno_reg[i]);
1617 for (j = 0; j < max_allocno; j++)
1618 if (CONFLICTP (i, j) || CONFLICTP (j, i))
1619 fprintf (file, " %d", allocno_reg[j]);
1620 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1621 if (TEST_HARD_REG_BIT (hard_reg_conflicts[i], j))
1622 fprintf (file, " %d", j);
1623 fprintf (file, "\n");
1625 has_preferences = 0;
1626 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1627 if (TEST_HARD_REG_BIT (hard_reg_preferences[i], j))
1628 has_preferences = 1;
1630 if (! has_preferences)
1632 fprintf (file, ";; %d preferences:", allocno_reg[i]);
1633 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1634 if (TEST_HARD_REG_BIT (hard_reg_preferences[i], j))
1635 fprintf (file, " %d", j);
1636 fprintf (file, "\n");
1638 fprintf (file, "\n");
1642 dump_global_regs (file)
1647 fprintf (file, ";; Register dispositions:\n");
1648 for (i = FIRST_PSEUDO_REGISTER, j = 0; i < max_regno; i++)
1649 if (reg_renumber[i] >= 0)
1651 fprintf (file, "%d in %d ", i, reg_renumber[i]);
1653 fprintf (file, "\n");
1656 fprintf (file, "\n\n;; Hard regs used: ");
1657 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1658 if (regs_ever_live[i])
1659 fprintf (file, " %d", i);
1660 fprintf (file, "\n\n");