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 registers that can be eliminated. */
251 static HARD_REG_SET eliminable_regset;
253 static int allocno_compare PROTO((int *, int *));
254 static void global_conflicts PROTO((void));
255 static void expand_preferences PROTO((void));
256 static void prune_preferences PROTO((void));
257 static void find_reg PROTO((int, HARD_REG_SET, int, int, int));
258 static void record_one_conflict PROTO((int));
259 static void record_conflicts PROTO((short *, int));
260 static void mark_reg_store PROTO((rtx, rtx));
261 static void mark_reg_clobber PROTO((rtx, rtx));
262 static void mark_reg_conflicts PROTO((rtx));
263 static void mark_reg_death PROTO((rtx));
264 static void mark_reg_live_nc PROTO((int, enum machine_mode));
265 static void set_preference PROTO((rtx, rtx));
266 static void dump_conflicts PROTO((FILE *));
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;
283 = (! flag_omit_frame_pointer
284 #ifdef EXIT_IGNORE_STACK
285 || (current_function_calls_alloca && EXIT_IGNORE_STACK)
287 || FRAME_POINTER_REQUIRED);
294 /* A machine may have certain hard registers that
295 are safe to use only within a basic block. */
297 CLEAR_HARD_REG_SET (no_global_alloc_regs);
298 #ifdef OVERLAPPING_REGNO_P
299 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
300 if (OVERLAPPING_REGNO_P (i))
301 SET_HARD_REG_BIT (no_global_alloc_regs, i);
304 /* Build the regset of all eliminable registers and show we can't use those
305 that we already know won't be eliminated. */
306 #ifdef ELIMINABLE_REGS
307 for (i = 0; i < sizeof eliminables / sizeof eliminables[0]; i++)
309 SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from);
311 if (! CAN_ELIMINATE (eliminables[i].from, eliminables[i].to)
312 || (eliminables[i].to == STACK_POINTER_REGNUM && need_fp))
313 SET_HARD_REG_BIT (no_global_alloc_regs, eliminables[i].from);
315 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
316 SET_HARD_REG_BIT (eliminable_regset, HARD_FRAME_POINTER_REGNUM);
318 SET_HARD_REG_BIT (no_global_alloc_regs, HARD_FRAME_POINTER_REGNUM);
322 SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM);
324 SET_HARD_REG_BIT (no_global_alloc_regs, FRAME_POINTER_REGNUM);
327 /* Track which registers have already been used. Start with registers
328 explicitly in the rtl, then registers allocated by local register
331 CLEAR_HARD_REG_SET (regs_used_so_far);
332 #ifdef LEAF_REGISTERS
333 /* If we are doing the leaf function optimization, and this is a leaf
334 function, it means that the registers that take work to save are those
335 that need a register window. So prefer the ones that can be used in
339 static char leaf_regs[] = LEAF_REGISTERS;
341 if (only_leaf_regs_used () && leaf_function_p ())
342 cheap_regs = leaf_regs;
344 cheap_regs = call_used_regs;
345 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
346 if (regs_ever_live[i] || cheap_regs[i])
347 SET_HARD_REG_BIT (regs_used_so_far, i);
350 /* We consider registers that do not have to be saved over calls as if
351 they were already used since there is no cost in using them. */
352 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
353 if (regs_ever_live[i] || call_used_regs[i])
354 SET_HARD_REG_BIT (regs_used_so_far, i);
357 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
358 if (reg_renumber[i] >= 0)
359 SET_HARD_REG_BIT (regs_used_so_far, reg_renumber[i]);
361 /* Establish mappings from register number to allocation number
362 and vice versa. In the process, count the allocnos. */
364 reg_allocno = (int *) alloca (max_regno * sizeof (int));
366 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
369 /* Initialize the shared-hard-reg mapping
370 from the list of pairs that may share. */
371 reg_may_share = (int *) alloca (max_regno * sizeof (int));
372 bzero ((char *) reg_may_share, max_regno * sizeof (int));
373 for (x = regs_may_share; x; x = XEXP (XEXP (x, 1), 1))
375 int r1 = REGNO (XEXP (x, 0));
376 int r2 = REGNO (XEXP (XEXP (x, 1), 0));
378 reg_may_share[r1] = r2;
380 reg_may_share[r2] = r1;
383 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
384 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
385 that we are supposed to refrain from putting in a hard reg.
386 -2 means do make an allocno but don't allocate it. */
387 if (reg_n_refs[i] != 0 && reg_renumber[i] < 0 && reg_live_length[i] != -1
388 /* Don't allocate pseudos that cross calls,
389 if this function receives a nonlocal goto. */
390 && (! current_function_has_nonlocal_label
391 || reg_n_calls_crossed[i] == 0))
393 if (reg_may_share[i] && reg_allocno[reg_may_share[i]] >= 0)
394 reg_allocno[i] = reg_allocno[reg_may_share[i]];
396 reg_allocno[i] = max_allocno++;
397 if (reg_live_length[i] == 0)
403 allocno_reg = (int *) alloca (max_allocno * sizeof (int));
404 allocno_size = (int *) alloca (max_allocno * sizeof (int));
405 allocno_calls_crossed = (int *) alloca (max_allocno * sizeof (int));
406 allocno_n_refs = (int *) alloca (max_allocno * sizeof (int));
407 allocno_live_length = (int *) alloca (max_allocno * sizeof (int));
408 bzero ((char *) allocno_size, max_allocno * sizeof (int));
409 bzero ((char *) allocno_calls_crossed, max_allocno * sizeof (int));
410 bzero ((char *) allocno_n_refs, max_allocno * sizeof (int));
411 bzero ((char *) allocno_live_length, max_allocno * sizeof (int));
413 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
414 if (reg_allocno[i] >= 0)
416 int allocno = reg_allocno[i];
417 allocno_reg[allocno] = i;
418 allocno_size[allocno] = PSEUDO_REGNO_SIZE (i);
419 allocno_calls_crossed[allocno] += reg_n_calls_crossed[i];
420 allocno_n_refs[allocno] += reg_n_refs[i];
421 if (allocno_live_length[allocno] < reg_live_length[i])
422 allocno_live_length[allocno] = reg_live_length[i];
425 /* Calculate amount of usage of each hard reg by pseudos
426 allocated by local-alloc. This is to see if we want to
428 bzero ((char *) local_reg_live_length, sizeof local_reg_live_length);
429 bzero ((char *) local_reg_n_refs, sizeof local_reg_n_refs);
430 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
431 if (reg_allocno[i] < 0 && reg_renumber[i] >= 0)
433 int regno = reg_renumber[i];
434 int endregno = regno + HARD_REGNO_NREGS (regno, PSEUDO_REGNO_MODE (i));
437 for (j = regno; j < endregno; j++)
439 local_reg_n_refs[j] += reg_n_refs[i];
440 local_reg_live_length[j] += reg_live_length[i];
444 /* We can't override local-alloc for a reg used not just by local-alloc. */
445 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
446 if (regs_ever_live[i])
447 local_reg_n_refs[i] = 0;
449 /* Allocate the space for the conflict and preference tables and
453 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
454 bzero ((char *) hard_reg_conflicts, max_allocno * sizeof (HARD_REG_SET));
457 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
458 bzero ((char *) hard_reg_preferences, max_allocno * sizeof (HARD_REG_SET));
460 hard_reg_copy_preferences
461 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
462 bzero ((char *) hard_reg_copy_preferences,
463 max_allocno * sizeof (HARD_REG_SET));
465 hard_reg_full_preferences
466 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
467 bzero ((char *) hard_reg_full_preferences,
468 max_allocno * sizeof (HARD_REG_SET));
471 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
472 bzero ((char *) regs_someone_prefers, max_allocno * sizeof (HARD_REG_SET));
474 allocno_row_words = (max_allocno + INT_BITS - 1) / INT_BITS;
476 conflicts = (INT_TYPE *) alloca (max_allocno * allocno_row_words
477 * sizeof (INT_TYPE));
478 bzero ((char *) conflicts,
479 max_allocno * allocno_row_words * sizeof (INT_TYPE));
481 allocnos_live = (INT_TYPE *) alloca (allocno_row_words * sizeof (INT_TYPE));
483 /* If there is work to be done (at least one reg to allocate),
484 perform global conflict analysis and allocate the regs. */
488 /* Scan all the insns and compute the conflicts among allocnos
489 and between allocnos and hard regs. */
493 /* Eliminate conflicts between pseudos and eliminable registers. If
494 the register is not eliminated, the pseudo won't really be able to
495 live in the eliminable register, so the conflict doesn't matter.
496 If we do eliminate the register, the conflict will no longer exist.
497 So in either case, we can ignore the conflict. Likewise for
500 for (i = 0; i < max_allocno; i++)
502 AND_COMPL_HARD_REG_SET (hard_reg_conflicts[i], eliminable_regset);
503 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[i],
505 AND_COMPL_HARD_REG_SET (hard_reg_preferences[i], eliminable_regset);
508 /* Try to expand the preferences by merging them between allocnos. */
510 expand_preferences ();
512 /* Determine the order to allocate the remaining pseudo registers. */
514 allocno_order = (int *) alloca (max_allocno * sizeof (int));
515 for (i = 0; i < max_allocno; i++)
516 allocno_order[i] = i;
518 /* Default the size to 1, since allocno_compare uses it to divide by.
519 Also convert allocno_live_length of zero to -1. A length of zero
520 can occur when all the registers for that allocno have reg_live_length
521 equal to -2. In this case, we want to make an allocno, but not
522 allocate it. So avoid the divide-by-zero and set it to a low
525 for (i = 0; i < max_allocno; i++)
527 if (allocno_size[i] == 0)
529 if (allocno_live_length[i] == 0)
530 allocno_live_length[i] = -1;
533 qsort (allocno_order, max_allocno, sizeof (int), allocno_compare);
535 prune_preferences ();
538 dump_conflicts (file);
540 /* Try allocating them, one by one, in that order,
541 except for parameters marked with reg_live_length[regno] == -2. */
543 for (i = 0; i < max_allocno; i++)
544 if (reg_live_length[allocno_reg[allocno_order[i]]] >= 0)
546 /* If we have more than one register class,
547 first try allocating in the class that is cheapest
548 for this pseudo-reg. If that fails, try any reg. */
549 if (N_REG_CLASSES > 1)
551 find_reg (allocno_order[i], HARD_CONST (0), 0, 0, 0);
552 if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
555 if (reg_alternate_class (allocno_reg[allocno_order[i]]) != NO_REGS)
556 find_reg (allocno_order[i], HARD_CONST (0), 1, 0, 0);
560 /* Do the reloads now while the allocno data still exist, so that we can
561 try to assign new hard regs to any pseudo regs that are spilled. */
563 #if 0 /* We need to eliminate regs even if there is no rtl code,
564 for the sake of debugging information. */
565 if (n_basic_blocks > 0)
567 return reload (get_insns (), 1, file);
570 /* Sort predicate for ordering the allocnos.
571 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
574 allocno_compare (v1, v2)
577 /* Note that the quotient will never be bigger than
578 the value of floor_log2 times the maximum number of
579 times a register can occur in one insn (surely less than 100).
580 Multiplying this by 10000 can't overflow. */
582 = (((double) (floor_log2 (allocno_n_refs[*v1]) * allocno_n_refs[*v1])
583 / allocno_live_length[*v1])
584 * 10000 * allocno_size[*v1]);
586 = (((double) (floor_log2 (allocno_n_refs[*v2]) * allocno_n_refs[*v2])
587 / allocno_live_length[*v2])
588 * 10000 * allocno_size[*v2]);
592 /* If regs are equally good, sort by allocno,
593 so that the results of qsort leave nothing to chance. */
597 /* Scan the rtl code and record all conflicts and register preferences in the
598 conflict matrices and preference tables. */
605 short *block_start_allocnos;
607 /* Make a vector that mark_reg_{store,clobber} will store in. */
608 regs_set = (rtx *) alloca (max_parallel * sizeof (rtx) * 2);
610 block_start_allocnos = (short *) alloca (max_allocno * sizeof (short));
612 for (b = 0; b < n_basic_blocks; b++)
614 bzero ((char *) allocnos_live, allocno_row_words * sizeof (INT_TYPE));
616 /* Initialize table of registers currently live
617 to the state at the beginning of this basic block.
618 This also marks the conflicts among them.
620 For pseudo-regs, there is only one bit for each one
621 no matter how many hard regs it occupies.
622 This is ok; we know the size from PSEUDO_REGNO_SIZE.
623 For explicit hard regs, we cannot know the size that way
624 since one hard reg can be used with various sizes.
625 Therefore, we must require that all the hard regs
626 implicitly live as part of a multi-word hard reg
627 are explicitly marked in basic_block_live_at_start. */
632 register regset old = basic_block_live_at_start[b];
636 hard_regs_live = old[0];
638 COPY_HARD_REG_SET (hard_regs_live, old);
640 for (offset = 0, i = 0; offset < regset_size; offset++)
641 if (old[offset] == 0)
642 i += REGSET_ELT_BITS;
644 for (bit = 1; bit; bit <<= 1, i++)
648 if (old[offset] & bit)
650 register int a = reg_allocno[i];
653 SET_ALLOCNO_LIVE (a);
654 block_start_allocnos[ax++] = a;
656 else if ((a = reg_renumber[i]) >= 0)
657 mark_reg_live_nc (a, PSEUDO_REGNO_MODE (i));
661 /* Record that each allocno now live conflicts with each other
662 allocno now live, and with each hard reg now live. */
664 record_conflicts (block_start_allocnos, ax);
667 insn = basic_block_head[b];
669 /* Scan the code of this basic block, noting which allocnos
670 and hard regs are born or die. When one is born,
671 record a conflict with all others currently live. */
675 register RTX_CODE code = GET_CODE (insn);
678 /* Make regs_set an empty set. */
682 if (code == INSN || code == CALL_INSN || code == JUMP_INSN)
687 for (link = REG_NOTES (insn);
688 link && i < NUM_NO_CONFLICT_PAIRS;
689 link = XEXP (link, 1))
690 if (REG_NOTE_KIND (link) == REG_NO_CONFLICT)
692 no_conflict_pairs[i].allocno1
693 = reg_allocno[REGNO (SET_DEST (PATTERN (insn)))];
694 no_conflict_pairs[i].allocno2
695 = reg_allocno[REGNO (XEXP (link, 0))];
700 /* Mark any registers clobbered by INSN as live,
701 so they conflict with the inputs. */
703 note_stores (PATTERN (insn), mark_reg_clobber);
705 /* Mark any registers dead after INSN as dead now. */
707 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
708 if (REG_NOTE_KIND (link) == REG_DEAD)
709 mark_reg_death (XEXP (link, 0));
711 /* Mark any registers set in INSN as live,
712 and mark them as conflicting with all other live regs.
713 Clobbers are processed again, so they conflict with
714 the registers that are set. */
716 note_stores (PATTERN (insn), mark_reg_store);
719 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
720 if (REG_NOTE_KIND (link) == REG_INC)
721 mark_reg_store (XEXP (link, 0), NULL_RTX);
724 /* If INSN has multiple outputs, then any reg that dies here
725 and is used inside of an output
726 must conflict with the other outputs. */
728 if (GET_CODE (PATTERN (insn)) == PARALLEL && !single_set (insn))
729 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
730 if (REG_NOTE_KIND (link) == REG_DEAD)
732 int used_in_output = 0;
734 rtx reg = XEXP (link, 0);
736 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
738 rtx set = XVECEXP (PATTERN (insn), 0, i);
739 if (GET_CODE (set) == SET
740 && GET_CODE (SET_DEST (set)) != REG
741 && !rtx_equal_p (reg, SET_DEST (set))
742 && reg_overlap_mentioned_p (reg, SET_DEST (set)))
746 mark_reg_conflicts (reg);
749 /* Mark any registers set in INSN and then never used. */
751 while (n_regs_set > 0)
752 if (find_regno_note (insn, REG_UNUSED,
753 REGNO (regs_set[--n_regs_set])))
754 mark_reg_death (regs_set[n_regs_set]);
757 if (insn == basic_block_end[b])
759 insn = NEXT_INSN (insn);
763 /* Expand the preference information by looking for cases where one allocno
764 dies in an insn that sets an allocno. If those two allocnos don't conflict,
765 merge any preferences between those allocnos. */
768 expand_preferences ()
774 /* We only try to handle the most common cases here. Most of the cases
775 where this wins are reg-reg copies. */
777 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
778 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
779 && (set = single_set (insn)) != 0
780 && GET_CODE (SET_DEST (set)) == REG
781 && reg_allocno[REGNO (SET_DEST (set))] >= 0)
782 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
783 if (REG_NOTE_KIND (link) == REG_DEAD
784 && GET_CODE (XEXP (link, 0)) == REG
785 && reg_allocno[REGNO (XEXP (link, 0))] >= 0
786 && ! CONFLICTP (reg_allocno[REGNO (SET_DEST (set))],
787 reg_allocno[REGNO (XEXP (link, 0))])
788 && ! CONFLICTP (reg_allocno[REGNO (XEXP (link, 0))],
789 reg_allocno[REGNO (SET_DEST (set))]))
791 int a1 = reg_allocno[REGNO (SET_DEST (set))];
792 int a2 = reg_allocno[REGNO (XEXP (link, 0))];
794 if (XEXP (link, 0) == SET_SRC (set))
796 IOR_HARD_REG_SET (hard_reg_copy_preferences[a1],
797 hard_reg_copy_preferences[a2]);
798 IOR_HARD_REG_SET (hard_reg_copy_preferences[a2],
799 hard_reg_copy_preferences[a1]);
802 IOR_HARD_REG_SET (hard_reg_preferences[a1],
803 hard_reg_preferences[a2]);
804 IOR_HARD_REG_SET (hard_reg_preferences[a2],
805 hard_reg_preferences[a1]);
806 IOR_HARD_REG_SET (hard_reg_full_preferences[a1],
807 hard_reg_full_preferences[a2]);
808 IOR_HARD_REG_SET (hard_reg_full_preferences[a2],
809 hard_reg_full_preferences[a1]);
813 /* Prune the preferences for global registers to exclude registers that cannot
816 Compute `regs_someone_prefers', which is a bitmask of the hard registers
817 that are preferred by conflicting registers of lower priority. If possible,
818 we will avoid using these registers. */
826 /* Scan least most important to most important.
827 For each allocno, remove from preferences registers that cannot be used,
828 either because of conflicts or register type. Then compute all registers
829 preferred by each lower-priority register that conflicts. */
831 for (i = max_allocno - 1; i >= 0; i--)
835 allocno = allocno_order[i];
836 COPY_HARD_REG_SET (temp, hard_reg_conflicts[allocno]);
838 if (allocno_calls_crossed[allocno] == 0)
839 IOR_HARD_REG_SET (temp, fixed_reg_set);
841 IOR_HARD_REG_SET (temp, call_used_reg_set);
843 IOR_COMPL_HARD_REG_SET
845 reg_class_contents[(int) reg_preferred_class (allocno_reg[allocno])]);
847 AND_COMPL_HARD_REG_SET (hard_reg_preferences[allocno], temp);
848 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[allocno], temp);
849 AND_COMPL_HARD_REG_SET (hard_reg_full_preferences[allocno], temp);
851 CLEAR_HARD_REG_SET (regs_someone_prefers[allocno]);
853 /* Merge in the preferences of lower-priority registers (they have
854 already been pruned). If we also prefer some of those registers,
855 don't exclude them unless we are of a smaller size (in which case
856 we want to give the lower-priority allocno the first chance for
858 for (j = i + 1; j < max_allocno; j++)
859 if (CONFLICTP (allocno, allocno_order[j]))
861 COPY_HARD_REG_SET (temp,
862 hard_reg_full_preferences[allocno_order[j]]);
863 if (allocno_size[allocno_order[j]] <= allocno_size[allocno])
864 AND_COMPL_HARD_REG_SET (temp,
865 hard_reg_full_preferences[allocno]);
867 IOR_HARD_REG_SET (regs_someone_prefers[allocno], temp);
872 /* Assign a hard register to ALLOCNO; look for one that is the beginning
873 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
874 The registers marked in PREFREGS are tried first.
876 LOSERS, if non-zero, is a HARD_REG_SET indicating registers that cannot
877 be used for this allocation.
879 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
880 Otherwise ignore that preferred class and use the alternate class.
882 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
883 will have to be saved and restored at calls.
885 RETRYING is nonzero if this is called from retry_global_alloc.
887 If we find one, record it in reg_renumber.
888 If not, do nothing. */
891 find_reg (allocno, losers, alt_regs_p, accept_call_clobbered, retrying)
895 int accept_call_clobbered;
898 register int i, best_reg, pass;
900 register /* Declare it register if it's a scalar. */
902 HARD_REG_SET used, used1, used2;
904 enum reg_class class = (alt_regs_p
905 ? reg_alternate_class (allocno_reg[allocno])
906 : reg_preferred_class (allocno_reg[allocno]));
907 enum machine_mode mode = PSEUDO_REGNO_MODE (allocno_reg[allocno]);
909 if (accept_call_clobbered)
910 COPY_HARD_REG_SET (used1, call_fixed_reg_set);
911 else if (allocno_calls_crossed[allocno] == 0)
912 COPY_HARD_REG_SET (used1, fixed_reg_set);
914 COPY_HARD_REG_SET (used1, call_used_reg_set);
916 /* Some registers should not be allocated in global-alloc. */
917 IOR_HARD_REG_SET (used1, no_global_alloc_regs);
919 IOR_HARD_REG_SET (used1, losers);
921 IOR_COMPL_HARD_REG_SET (used1, reg_class_contents[(int) class]);
922 COPY_HARD_REG_SET (used2, used1);
924 IOR_HARD_REG_SET (used1, hard_reg_conflicts[allocno]);
926 /* Try each hard reg to see if it fits. Do this in two passes.
927 In the first pass, skip registers that are preferred by some other pseudo
928 to give it a better chance of getting one of those registers. Only if
929 we can't get a register when excluding those do we take one of them.
930 However, we never allocate a register for the first time in pass 0. */
932 COPY_HARD_REG_SET (used, used1);
933 IOR_COMPL_HARD_REG_SET (used, regs_used_so_far);
934 IOR_HARD_REG_SET (used, regs_someone_prefers[allocno]);
937 for (i = FIRST_PSEUDO_REGISTER, pass = 0;
938 pass <= 1 && i >= FIRST_PSEUDO_REGISTER;
942 COPY_HARD_REG_SET (used, used1);
943 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
945 #ifdef REG_ALLOC_ORDER
946 int regno = reg_alloc_order[i];
950 if (! TEST_HARD_REG_BIT (used, regno)
951 && HARD_REGNO_MODE_OK (regno, mode))
954 register int lim = regno + HARD_REGNO_NREGS (regno, mode);
957 && ! TEST_HARD_REG_BIT (used, j));
964 #ifndef REG_ALLOC_ORDER
965 i = j; /* Skip starting points we know will lose */
971 /* See if there is a preferred register with the same class as the register
972 we allocated above. Making this restriction prevents register
973 preferencing from creating worse register allocation.
975 Remove from the preferred registers and conflicting registers. Note that
976 additional conflicts may have been added after `prune_preferences' was
979 First do this for those register with copy preferences, then all
980 preferred registers. */
982 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[allocno], used);
983 GO_IF_HARD_REG_SUBSET (hard_reg_copy_preferences[allocno],
984 reg_class_contents[(int) NO_REGS], no_copy_prefs);
988 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
989 if (TEST_HARD_REG_BIT (hard_reg_copy_preferences[allocno], i)
990 && HARD_REGNO_MODE_OK (i, mode)
991 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
992 || reg_class_subset_p (REGNO_REG_CLASS (i),
993 REGNO_REG_CLASS (best_reg))
994 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
995 REGNO_REG_CLASS (i))))
998 register int lim = i + HARD_REGNO_NREGS (i, mode);
1001 && ! TEST_HARD_REG_BIT (used, j)
1002 && (REGNO_REG_CLASS (j)
1003 == REGNO_REG_CLASS (best_reg + (j - i))
1004 || reg_class_subset_p (REGNO_REG_CLASS (j),
1005 REGNO_REG_CLASS (best_reg + (j - i)))
1006 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1007 REGNO_REG_CLASS (j))));
1018 AND_COMPL_HARD_REG_SET (hard_reg_preferences[allocno], used);
1019 GO_IF_HARD_REG_SUBSET (hard_reg_preferences[allocno],
1020 reg_class_contents[(int) NO_REGS], no_prefs);
1024 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1025 if (TEST_HARD_REG_BIT (hard_reg_preferences[allocno], i)
1026 && HARD_REGNO_MODE_OK (i, mode)
1027 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1028 || reg_class_subset_p (REGNO_REG_CLASS (i),
1029 REGNO_REG_CLASS (best_reg))
1030 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1031 REGNO_REG_CLASS (i))))
1034 register int lim = i + HARD_REGNO_NREGS (i, mode);
1037 && ! TEST_HARD_REG_BIT (used, j)
1038 && (REGNO_REG_CLASS (j)
1039 == REGNO_REG_CLASS (best_reg + (j - i))
1040 || reg_class_subset_p (REGNO_REG_CLASS (j),
1041 REGNO_REG_CLASS (best_reg + (j - i)))
1042 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1043 REGNO_REG_CLASS (j))));
1054 /* If we haven't succeeded yet, try with caller-saves.
1055 We need not check to see if the current function has nonlocal
1056 labels because we don't put any pseudos that are live over calls in
1057 registers in that case. */
1059 if (flag_caller_saves && best_reg < 0)
1061 /* Did not find a register. If it would be profitable to
1062 allocate a call-clobbered register and save and restore it
1063 around calls, do that. */
1064 if (! accept_call_clobbered
1065 && allocno_calls_crossed[allocno] != 0
1066 && CALLER_SAVE_PROFITABLE (allocno_n_refs[allocno],
1067 allocno_calls_crossed[allocno]))
1069 find_reg (allocno, losers, alt_regs_p, 1, retrying);
1070 if (reg_renumber[allocno_reg[allocno]] >= 0)
1072 caller_save_needed = 1;
1078 /* If we haven't succeeded yet,
1079 see if some hard reg that conflicts with us
1080 was utilized poorly by local-alloc.
1081 If so, kick out the regs that were put there by local-alloc
1082 so we can use it instead. */
1083 if (best_reg < 0 && !retrying
1084 /* Let's not bother with multi-reg allocnos. */
1085 && allocno_size[allocno] == 1)
1087 /* Count from the end, to find the least-used ones first. */
1088 for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1090 #ifdef REG_ALLOC_ORDER
1091 int regno = reg_alloc_order[i];
1096 if (local_reg_n_refs[regno] != 0
1097 /* Don't use a reg no good for this pseudo. */
1098 && ! TEST_HARD_REG_BIT (used2, regno)
1099 && HARD_REGNO_MODE_OK (regno, mode)
1100 && (((double) local_reg_n_refs[regno]
1101 / local_reg_live_length[regno])
1102 < ((double) allocno_n_refs[allocno]
1103 / allocno_live_length[allocno])))
1105 /* Hard reg REGNO was used less in total by local regs
1106 than it would be used by this one allocno! */
1108 for (k = 0; k < max_regno; k++)
1109 if (reg_renumber[k] >= 0)
1111 int r = reg_renumber[k];
1113 = r + HARD_REGNO_NREGS (r, PSEUDO_REGNO_MODE (k));
1115 if (regno >= r && regno < endregno)
1116 reg_renumber[k] = -1;
1125 /* Did we find a register? */
1129 register int lim, j;
1130 HARD_REG_SET this_reg;
1132 /* Yes. Record it as the hard register of this pseudo-reg. */
1133 reg_renumber[allocno_reg[allocno]] = best_reg;
1134 /* Also of any pseudo-regs that share with it. */
1135 if (reg_may_share[allocno_reg[allocno]])
1136 for (j = FIRST_PSEUDO_REGISTER; j < max_regno; j++)
1137 if (reg_allocno[j] == allocno)
1138 reg_renumber[j] = best_reg;
1140 /* Make a set of the hard regs being allocated. */
1141 CLEAR_HARD_REG_SET (this_reg);
1142 lim = best_reg + HARD_REGNO_NREGS (best_reg, mode);
1143 for (j = best_reg; j < lim; j++)
1145 SET_HARD_REG_BIT (this_reg, j);
1146 SET_HARD_REG_BIT (regs_used_so_far, j);
1147 /* This is no longer a reg used just by local regs. */
1148 local_reg_n_refs[j] = 0;
1150 /* For each other pseudo-reg conflicting with this one,
1151 mark it as conflicting with the hard regs this one occupies. */
1153 for (j = 0; j < max_allocno; j++)
1154 if (CONFLICTP (lim, j) || CONFLICTP (j, lim))
1156 IOR_HARD_REG_SET (hard_reg_conflicts[j], this_reg);
1161 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1162 Perhaps it had previously seemed not worth a hard reg,
1163 or perhaps its old hard reg has been commandeered for reloads.
1164 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1165 they do not appear to be allocated.
1166 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1169 retry_global_alloc (regno, forbidden_regs)
1171 HARD_REG_SET forbidden_regs;
1173 int allocno = reg_allocno[regno];
1176 /* If we have more than one register class,
1177 first try allocating in the class that is cheapest
1178 for this pseudo-reg. If that fails, try any reg. */
1179 if (N_REG_CLASSES > 1)
1180 find_reg (allocno, forbidden_regs, 0, 0, 1);
1181 if (reg_renumber[regno] < 0
1182 && reg_alternate_class (regno) != NO_REGS)
1183 find_reg (allocno, forbidden_regs, 1, 0, 1);
1185 /* If we found a register, modify the RTL for the register to
1186 show the hard register, and mark that register live. */
1187 if (reg_renumber[regno] >= 0)
1189 REGNO (regno_reg_rtx[regno]) = reg_renumber[regno];
1190 mark_home_live (regno);
1195 /* Record a conflict between register REGNO
1196 and everything currently live.
1197 REGNO must not be a pseudo reg that was allocated
1198 by local_alloc; such numbers must be translated through
1199 reg_renumber before calling here. */
1202 record_one_conflict (regno)
1207 if (regno < FIRST_PSEUDO_REGISTER)
1208 /* When a hard register becomes live,
1209 record conflicts with live pseudo regs. */
1210 for (j = 0; j < max_allocno; j++)
1212 if (ALLOCNO_LIVE_P (j))
1213 SET_HARD_REG_BIT (hard_reg_conflicts[j], regno);
1216 /* When a pseudo-register becomes live,
1217 record conflicts first with hard regs,
1218 then with other pseudo regs. */
1220 register int ialloc = reg_allocno[regno];
1221 register int ialloc_prod = ialloc * allocno_row_words;
1222 IOR_HARD_REG_SET (hard_reg_conflicts[ialloc], hard_regs_live);
1223 for (j = allocno_row_words - 1; j >= 0; j--)
1227 for (k = 0; k < n_no_conflict_pairs; k++)
1228 if (! ((j == no_conflict_pairs[k].allocno1
1229 && ialloc == no_conflict_pairs[k].allocno2)
1231 (j == no_conflict_pairs[k].allocno2
1232 && ialloc == no_conflict_pairs[k].allocno1)))
1234 conflicts[ialloc_prod + j] |= allocnos_live[j];
1239 /* Record all allocnos currently live as conflicting
1240 with each other and with all hard regs currently live.
1241 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1242 are currently live. Their bits are also flagged in allocnos_live. */
1245 record_conflicts (allocno_vec, len)
1246 register short *allocno_vec;
1249 register int allocno;
1251 register int ialloc_prod;
1255 allocno = allocno_vec[len];
1256 ialloc_prod = allocno * allocno_row_words;
1257 IOR_HARD_REG_SET (hard_reg_conflicts[allocno], hard_regs_live);
1258 for (j = allocno_row_words - 1; j >= 0; j--)
1259 conflicts[ialloc_prod + j] |= allocnos_live[j];
1263 /* Handle the case where REG is set by the insn being scanned,
1264 during the forward scan to accumulate conflicts.
1265 Store a 1 in regs_live or allocnos_live for this register, record how many
1266 consecutive hardware registers it actually needs,
1267 and record a conflict with all other registers already live.
1269 Note that even if REG does not remain alive after this insn,
1270 we must mark it here as live, to ensure a conflict between
1271 REG and any other regs set in this insn that really do live.
1272 This is because those other regs could be considered after this.
1274 REG might actually be something other than a register;
1275 if so, we do nothing.
1277 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1278 a REG_INC note was found for it).
1280 CLOBBERs are processed here by calling mark_reg_clobber. */
1283 mark_reg_store (orig_reg, setter)
1284 rtx orig_reg, setter;
1287 register rtx reg = orig_reg;
1289 /* WORD is which word of a multi-register group is being stored.
1290 For the case where the store is actually into a SUBREG of REG.
1291 Except we don't use it; I believe the entire REG needs to be
1295 if (GET_CODE (reg) == SUBREG)
1297 word = SUBREG_WORD (reg);
1298 reg = SUBREG_REG (reg);
1301 if (GET_CODE (reg) != REG)
1304 if (setter && GET_CODE (setter) == CLOBBER)
1306 /* A clobber of a register should be processed here too. */
1307 mark_reg_clobber (orig_reg, setter);
1311 regs_set[n_regs_set++] = reg;
1314 set_preference (reg, SET_SRC (setter));
1316 regno = REGNO (reg);
1318 if (reg_renumber[regno] >= 0)
1319 regno = reg_renumber[regno] /* + word */;
1321 /* Either this is one of the max_allocno pseudo regs not allocated,
1322 or it is or has a hardware reg. First handle the pseudo-regs. */
1323 if (regno >= FIRST_PSEUDO_REGISTER)
1325 if (reg_allocno[regno] >= 0)
1327 SET_ALLOCNO_LIVE (reg_allocno[regno]);
1328 record_one_conflict (regno);
1331 /* Handle hardware regs (and pseudos allocated to hard regs). */
1332 else if (! fixed_regs[regno])
1334 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1335 while (regno < last)
1337 record_one_conflict (regno);
1338 SET_HARD_REG_BIT (hard_regs_live, regno);
1344 /* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
1347 mark_reg_clobber (reg, setter)
1352 /* WORD is which word of a multi-register group is being stored.
1353 For the case where the store is actually into a SUBREG of REG.
1354 Except we don't use it; I believe the entire REG needs to be
1358 if (GET_CODE (setter) != CLOBBER)
1361 if (GET_CODE (reg) == SUBREG)
1363 word = SUBREG_WORD (reg);
1364 reg = SUBREG_REG (reg);
1367 if (GET_CODE (reg) != REG)
1370 regs_set[n_regs_set++] = reg;
1372 regno = REGNO (reg);
1374 if (reg_renumber[regno] >= 0)
1375 regno = reg_renumber[regno] /* + word */;
1377 /* Either this is one of the max_allocno pseudo regs not allocated,
1378 or it is or has a hardware reg. First handle the pseudo-regs. */
1379 if (regno >= FIRST_PSEUDO_REGISTER)
1381 if (reg_allocno[regno] >= 0)
1383 SET_ALLOCNO_LIVE (reg_allocno[regno]);
1384 record_one_conflict (regno);
1387 /* Handle hardware regs (and pseudos allocated to hard regs). */
1388 else if (! fixed_regs[regno])
1390 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1391 while (regno < last)
1393 record_one_conflict (regno);
1394 SET_HARD_REG_BIT (hard_regs_live, regno);
1400 /* Record that REG has conflicts with all the regs currently live.
1401 Do not mark REG itself as live. */
1404 mark_reg_conflicts (reg)
1409 if (GET_CODE (reg) == SUBREG)
1410 reg = SUBREG_REG (reg);
1412 if (GET_CODE (reg) != REG)
1415 regno = REGNO (reg);
1417 if (reg_renumber[regno] >= 0)
1418 regno = reg_renumber[regno];
1420 /* Either this is one of the max_allocno pseudo regs not allocated,
1421 or it is or has a hardware reg. First handle the pseudo-regs. */
1422 if (regno >= FIRST_PSEUDO_REGISTER)
1424 if (reg_allocno[regno] >= 0)
1425 record_one_conflict (regno);
1427 /* Handle hardware regs (and pseudos allocated to hard regs). */
1428 else if (! fixed_regs[regno])
1430 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1431 while (regno < last)
1433 record_one_conflict (regno);
1439 /* Mark REG as being dead (following the insn being scanned now).
1440 Store a 0 in regs_live or allocnos_live for this register. */
1443 mark_reg_death (reg)
1446 register int regno = REGNO (reg);
1448 /* For pseudo reg, see if it has been assigned a hardware reg. */
1449 if (reg_renumber[regno] >= 0)
1450 regno = reg_renumber[regno];
1452 /* Either this is one of the max_allocno pseudo regs not allocated,
1453 or it is a hardware reg. First handle the pseudo-regs. */
1454 if (regno >= FIRST_PSEUDO_REGISTER)
1456 if (reg_allocno[regno] >= 0)
1457 CLEAR_ALLOCNO_LIVE (reg_allocno[regno]);
1459 /* Handle hardware regs (and pseudos allocated to hard regs). */
1460 else if (! fixed_regs[regno])
1462 /* Pseudo regs already assigned hardware regs are treated
1463 almost the same as explicit hardware regs. */
1464 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1465 while (regno < last)
1467 CLEAR_HARD_REG_BIT (hard_regs_live, regno);
1473 /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1474 for the value stored in it. MODE determines how many consecutive
1475 registers are actually in use. Do not record conflicts;
1476 it is assumed that the caller will do that. */
1479 mark_reg_live_nc (regno, mode)
1481 enum machine_mode mode;
1483 register int last = regno + HARD_REGNO_NREGS (regno, mode);
1484 while (regno < last)
1486 SET_HARD_REG_BIT (hard_regs_live, regno);
1491 /* Try to set a preference for an allocno to a hard register.
1492 We are passed DEST and SRC which are the operands of a SET. It is known
1493 that SRC is a register. If SRC or the first operand of SRC is a register,
1494 try to set a preference. If one of the two is a hard register and the other
1495 is a pseudo-register, mark the preference.
1497 Note that we are not as aggressive as local-alloc in trying to tie a
1498 pseudo-register to a hard register. */
1501 set_preference (dest, src)
1504 int src_regno, dest_regno;
1505 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1506 to compensate for subregs in SRC or DEST. */
1511 if (GET_RTX_FORMAT (GET_CODE (src))[0] == 'e')
1512 src = XEXP (src, 0), copy = 0;
1514 /* Get the reg number for both SRC and DEST.
1515 If neither is a reg, give up. */
1517 if (GET_CODE (src) == REG)
1518 src_regno = REGNO (src);
1519 else if (GET_CODE (src) == SUBREG && GET_CODE (SUBREG_REG (src)) == REG)
1521 src_regno = REGNO (SUBREG_REG (src));
1522 offset += SUBREG_WORD (src);
1527 if (GET_CODE (dest) == REG)
1528 dest_regno = REGNO (dest);
1529 else if (GET_CODE (dest) == SUBREG && GET_CODE (SUBREG_REG (dest)) == REG)
1531 dest_regno = REGNO (SUBREG_REG (dest));
1532 offset -= SUBREG_WORD (dest);
1537 /* Convert either or both to hard reg numbers. */
1539 if (reg_renumber[src_regno] >= 0)
1540 src_regno = reg_renumber[src_regno];
1542 if (reg_renumber[dest_regno] >= 0)
1543 dest_regno = reg_renumber[dest_regno];
1545 /* Now if one is a hard reg and the other is a global pseudo
1546 then give the other a preference. */
1548 if (dest_regno < FIRST_PSEUDO_REGISTER && src_regno >= FIRST_PSEUDO_REGISTER
1549 && reg_allocno[src_regno] >= 0)
1551 dest_regno -= offset;
1552 if (dest_regno >= 0 && dest_regno < FIRST_PSEUDO_REGISTER)
1555 SET_REGBIT (hard_reg_copy_preferences,
1556 reg_allocno[src_regno], dest_regno);
1558 SET_REGBIT (hard_reg_preferences,
1559 reg_allocno[src_regno], dest_regno);
1560 for (i = dest_regno;
1561 i < dest_regno + HARD_REGNO_NREGS (dest_regno, GET_MODE (dest));
1563 SET_REGBIT (hard_reg_full_preferences, reg_allocno[src_regno], i);
1567 if (src_regno < FIRST_PSEUDO_REGISTER && dest_regno >= FIRST_PSEUDO_REGISTER
1568 && reg_allocno[dest_regno] >= 0)
1570 src_regno += offset;
1571 if (src_regno >= 0 && src_regno < FIRST_PSEUDO_REGISTER)
1574 SET_REGBIT (hard_reg_copy_preferences,
1575 reg_allocno[dest_regno], src_regno);
1577 SET_REGBIT (hard_reg_preferences,
1578 reg_allocno[dest_regno], src_regno);
1580 i < src_regno + HARD_REGNO_NREGS (src_regno, GET_MODE (src));
1582 SET_REGBIT (hard_reg_full_preferences, reg_allocno[dest_regno], i);
1587 /* Indicate that hard register number FROM was eliminated and replaced with
1588 an offset from hard register number TO. The status of hard registers live
1589 at the start of a basic block is updated by replacing a use of FROM with
1593 mark_elimination (from, to)
1598 for (i = 0; i < n_basic_blocks; i++)
1599 if ((basic_block_live_at_start[i][from / REGSET_ELT_BITS]
1600 & ((REGSET_ELT_TYPE) 1 << (from % REGSET_ELT_BITS))) != 0)
1602 basic_block_live_at_start[i][from / REGSET_ELT_BITS]
1603 &= ~ ((REGSET_ELT_TYPE) 1 << (from % REGSET_ELT_BITS));
1604 basic_block_live_at_start[i][to / REGSET_ELT_BITS]
1605 |= ((REGSET_ELT_TYPE) 1 << (to % REGSET_ELT_BITS));
1609 /* Print debugging trace information if -greg switch is given,
1610 showing the information on which the allocation decisions are based. */
1613 dump_conflicts (file)
1617 register int has_preferences;
1618 fprintf (file, ";; %d regs to allocate:", max_allocno);
1619 for (i = 0; i < max_allocno; i++)
1622 fprintf (file, " %d", allocno_reg[allocno_order[i]]);
1623 for (j = 0; j < max_regno; j++)
1624 if (reg_allocno[j] == allocno_order[i]
1625 && j != allocno_reg[allocno_order[i]])
1626 fprintf (file, "+%d", j);
1627 if (allocno_size[allocno_order[i]] != 1)
1628 fprintf (file, " (%d)", allocno_size[allocno_order[i]]);
1630 fprintf (file, "\n");
1632 for (i = 0; i < max_allocno; i++)
1635 fprintf (file, ";; %d conflicts:", allocno_reg[i]);
1636 for (j = 0; j < max_allocno; j++)
1637 if (CONFLICTP (i, j) || CONFLICTP (j, i))
1638 fprintf (file, " %d", allocno_reg[j]);
1639 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1640 if (TEST_HARD_REG_BIT (hard_reg_conflicts[i], j))
1641 fprintf (file, " %d", j);
1642 fprintf (file, "\n");
1644 has_preferences = 0;
1645 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1646 if (TEST_HARD_REG_BIT (hard_reg_preferences[i], j))
1647 has_preferences = 1;
1649 if (! has_preferences)
1651 fprintf (file, ";; %d preferences:", allocno_reg[i]);
1652 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1653 if (TEST_HARD_REG_BIT (hard_reg_preferences[i], j))
1654 fprintf (file, " %d", j);
1655 fprintf (file, "\n");
1657 fprintf (file, "\n");
1661 dump_global_regs (file)
1666 fprintf (file, ";; Register dispositions:\n");
1667 for (i = FIRST_PSEUDO_REGISTER, j = 0; i < max_regno; i++)
1668 if (reg_renumber[i] >= 0)
1670 fprintf (file, "%d in %d ", i, reg_renumber[i]);
1672 fprintf (file, "\n");
1675 fprintf (file, "\n\n;; Hard regs used: ");
1676 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1677 if (regs_ever_live[i])
1678 fprintf (file, " %d", i);
1679 fprintf (file, "\n\n");