1 /* Allocate registers for pseudo-registers that span basic blocks.
2 Copyright (C) 1987, 1988, 1991 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 /* max_allocno by max_allocno array of bits,
100 recording whether two allocno's conflict (can't go in the same
103 `conflicts' is not symmetric; a conflict between allocno's i and j
104 is recorded either in element i,j or in element j,i. */
106 static int *conflicts;
108 /* Number of ints require to hold max_allocno bits.
109 This is the length of a row in `conflicts'. */
111 static int allocno_row_words;
113 /* Two macros to test or store 1 in an element of `conflicts'. */
115 #define CONFLICTP(I, J) \
116 (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
117 & (1 << ((J) % INT_BITS)))
119 #define SET_CONFLICT(I, J) \
120 (conflicts[(I) * allocno_row_words + (J) / INT_BITS] \
121 |= (1 << ((J) % INT_BITS)))
123 /* Set of hard regs currently live (during scan of all insns). */
125 static HARD_REG_SET hard_regs_live;
127 /* Indexed by N, set of hard regs conflicting with allocno N. */
129 static HARD_REG_SET *hard_reg_conflicts;
131 /* Indexed by N, set of hard regs preferred by allocno N.
132 This is used to make allocnos go into regs that are copied to or from them,
133 when possible, to reduce register shuffling. */
135 static HARD_REG_SET *hard_reg_preferences;
137 /* Similar, but just counts register preferences made in simple copy
138 operations, rather than arithmetic. These are given priority because
139 we can always eliminate an insn by using these, but using a register
140 in the above list won't always eliminate an insn. */
142 static HARD_REG_SET *hard_reg_copy_preferences;
144 /* Similar to hard_reg_preferences, but includes bits for subsequent
145 registers when an allocno is multi-word. The above variable is used for
146 allocation while this is used to build reg_someone_prefers, below. */
148 static HARD_REG_SET *hard_reg_full_preferences;
150 /* Indexed by N, set of hard registers that some later allocno has a
153 static HARD_REG_SET *regs_someone_prefers;
155 /* Set of registers that global-alloc isn't supposed to use. */
157 static HARD_REG_SET no_global_alloc_regs;
159 /* Set of registers used so far. */
161 static HARD_REG_SET regs_used_so_far;
163 /* Number of calls crossed by each allocno. */
165 static int *allocno_calls_crossed;
167 /* Number of refs (weighted) to each allocno. */
169 static int *allocno_n_refs;
171 /* Guess at live length of each allocno.
172 This is actually the max of the live lengths of the regs. */
174 static int *allocno_live_length;
176 /* Number of refs (weighted) to each hard reg, as used by local alloc.
177 It is zero for a reg that contains global pseudos or is explicitly used. */
179 static int local_reg_n_refs[FIRST_PSEUDO_REGISTER];
181 /* Guess at live length of each hard reg, as used by local alloc.
182 This is actually the sum of the live lengths of the specific regs. */
184 static int local_reg_live_length[FIRST_PSEUDO_REGISTER];
186 /* Test a bit in TABLE, a vector of HARD_REG_SETs,
187 for vector element I, and hard register number J. */
189 #define REGBITP(TABLE, I, J) TEST_HARD_REG_BIT (TABLE[I], J)
191 /* Set to 1 a bit in a vector of HARD_REG_SETs. Works like REGBITP. */
193 #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (TABLE[I], J)
195 /* Bit mask for allocnos live at current point in the scan. */
197 static int *allocnos_live;
199 #define INT_BITS HOST_BITS_PER_INT
201 /* Test, set or clear bit number I in allocnos_live,
202 a bit vector indexed by allocno. */
204 #define ALLOCNO_LIVE_P(I) \
205 (allocnos_live[(I) / INT_BITS] & (1 << ((I) % INT_BITS)))
207 #define SET_ALLOCNO_LIVE(I) \
208 (allocnos_live[(I) / INT_BITS] |= (1 << ((I) % INT_BITS)))
210 #define CLEAR_ALLOCNO_LIVE(I) \
211 (allocnos_live[(I) / INT_BITS] &= ~(1 << ((I) % INT_BITS)))
213 /* This is turned off because it doesn't work right for DImode.
214 (And it is only used for DImode, so the other cases are worthless.)
215 The problem is that it isn't true that there is NO possibility of conflict;
216 only that there is no conflict if the two pseudos get the exact same regs.
217 If they were allocated with a partial overlap, there would be a conflict.
218 We can't safely turn off the conflict unless we have another way to
219 prevent the partial overlap.
221 Idea: change hard_reg_conflicts so that instead of recording which
222 hard regs the allocno may not overlap, it records where the allocno
223 may not start. Change both where it is used and where it is updated.
224 Then there is a way to record that (reg:DI 108) may start at 10
225 but not at 9 or 11. There is still the question of how to record
226 this semi-conflict between two pseudos. */
228 /* Reg pairs for which conflict after the current insn
229 is inhibited by a REG_NO_CONFLICT note.
230 If the table gets full, we ignore any other notes--that is conservative. */
231 #define NUM_NO_CONFLICT_PAIRS 4
232 /* Number of pairs in use in this insn. */
233 int n_no_conflict_pairs;
234 static struct { int allocno1, allocno2;}
235 no_conflict_pairs[NUM_NO_CONFLICT_PAIRS];
238 /* Record all regs that are set in any one insn.
239 Communication from mark_reg_{store,clobber} and global_conflicts. */
241 static rtx *regs_set;
242 static int n_regs_set;
244 /* All register that can be eliminated. */
246 static HARD_REG_SET eliminable_regset;
248 static int allocno_compare ();
249 static void mark_reg_store ();
250 static void mark_reg_clobber ();
251 static void mark_reg_conflicts ();
252 static void mark_reg_live_nc ();
253 static void mark_reg_death ();
254 static void dump_conflicts ();
255 void dump_global_regs ();
256 static void find_reg ();
257 static void global_conflicts ();
258 static void expand_preferences ();
259 static void prune_preferences ();
260 static void record_conflicts ();
261 static void set_preference ();
263 /* Perform allocation of pseudo-registers not allocated by local_alloc.
264 FILE is a file to output debugging information on,
265 or zero if such output is not desired.
267 Return value is nonzero if reload failed
268 and we must not do any more for this function. */
274 #ifdef ELIMINABLE_REGS
275 static struct {int from, to; } eliminables[] = ELIMINABLE_REGS;
282 /* A machine may have certain hard registers that
283 are safe to use only within a basic block. */
285 CLEAR_HARD_REG_SET (no_global_alloc_regs);
286 #ifdef OVERLAPPING_REGNO_P
287 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
288 if (OVERLAPPING_REGNO_P (i))
289 SET_HARD_REG_BIT (no_global_alloc_regs, i);
292 /* Build the regset of all eliminable registers and show we can't use those
293 that we already know won't be eliminated. */
294 #ifdef ELIMINABLE_REGS
295 for (i = 0; i < sizeof eliminables / sizeof eliminables[0]; i++)
297 SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from);
299 if (! CAN_ELIMINATE (eliminables[i].from, eliminables[i].to)
300 || (eliminables[i].from == FRAME_POINTER_REGNUM
301 && (! flag_omit_frame_pointer || FRAME_POINTER_REQUIRED)))
302 SET_HARD_REG_BIT (no_global_alloc_regs, eliminables[i].from);
305 SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM);
307 /* If we know we will definitely not be eliminating the frame pointer,
308 don't allocate it. */
309 if (! flag_omit_frame_pointer || FRAME_POINTER_REQUIRED)
310 SET_HARD_REG_BIT (no_global_alloc_regs, FRAME_POINTER_REGNUM);
313 /* Track which registers have already been used. Start with registers
314 explicitly in the rtl, then registers allocated by local register
317 CLEAR_HARD_REG_SET (regs_used_so_far);
318 #ifdef LEAF_REGISTERS
319 /* If we are doing the leaf function optimization, and this is a leaf
320 function, it means that the registers that take work to save are those
321 that need a register window. So prefer the ones that can be used in
325 static char leaf_regs[] = LEAF_REGISTERS;
327 if (only_leaf_regs_used () && leaf_function_p ())
328 cheap_regs = leaf_regs;
330 cheap_regs = call_used_regs;
331 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
332 if (regs_ever_live[i] || cheap_regs[i])
333 SET_HARD_REG_BIT (regs_used_so_far, i);
336 /* We consider registers that do not have to be saved over calls as if
337 they were already used since there is no cost in using them. */
338 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
339 if (regs_ever_live[i] || call_used_regs[i])
340 SET_HARD_REG_BIT (regs_used_so_far, i);
343 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
344 if (reg_renumber[i] >= 0)
345 SET_HARD_REG_BIT (regs_used_so_far, reg_renumber[i]);
347 /* Establish mappings from register number to allocation number
348 and vice versa. In the process, count the allocnos. */
350 reg_allocno = (int *) alloca (max_regno * sizeof (int));
352 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
355 /* Initialize the shared-hard-reg mapping
356 from the list of pairs that may share. */
357 reg_may_share = (int *) alloca (max_regno * sizeof (int));
358 bzero (reg_may_share, max_regno * sizeof (int));
359 for (x = regs_may_share; x; x = XEXP (XEXP (x, 1), 1))
361 int r1 = REGNO (XEXP (x, 0));
362 int r2 = REGNO (XEXP (XEXP (x, 1), 0));
364 reg_may_share[r1] = r2;
366 reg_may_share[r2] = r1;
369 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
370 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
371 that we are supposed to refrain from putting in a hard reg.
372 -2 means do make an allocno but don't allocate it. */
373 if (reg_n_refs[i] != 0 && reg_renumber[i] < 0 && reg_live_length[i] != -1
374 /* Don't allocate pseudos that cross calls,
375 if this function receives a nonlocal goto. */
376 && (! current_function_has_nonlocal_label
377 || reg_n_calls_crossed[i] == 0))
379 if (reg_may_share[i] && reg_allocno[reg_may_share[i]] >= 0)
380 reg_allocno[i] = reg_allocno[reg_may_share[i]];
382 reg_allocno[i] = max_allocno++;
383 if (reg_live_length[i] == 0)
389 allocno_reg = (int *) alloca (max_allocno * sizeof (int));
390 allocno_size = (int *) alloca (max_allocno * sizeof (int));
391 allocno_calls_crossed = (int *) alloca (max_allocno * sizeof (int));
392 allocno_n_refs = (int *) alloca (max_allocno * sizeof (int));
393 allocno_live_length = (int *) alloca (max_allocno * sizeof (int));
394 bzero (allocno_size, max_allocno * sizeof (int));
395 bzero (allocno_calls_crossed, max_allocno * sizeof (int));
396 bzero (allocno_n_refs, max_allocno * sizeof (int));
397 bzero (allocno_live_length, max_allocno * sizeof (int));
399 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
400 if (reg_allocno[i] >= 0)
402 int allocno = reg_allocno[i];
403 allocno_reg[allocno] = i;
404 allocno_size[allocno] = PSEUDO_REGNO_SIZE (i);
405 allocno_calls_crossed[allocno] += reg_n_calls_crossed[i];
406 allocno_n_refs[allocno] += reg_n_refs[i];
407 if (allocno_live_length[allocno] < reg_live_length[i])
408 allocno_live_length[allocno] = reg_live_length[i];
411 /* Calculate amount of usage of each hard reg by pseudos
412 allocated by local-alloc. This is to see if we want to
414 bzero (local_reg_live_length, sizeof local_reg_live_length);
415 bzero (local_reg_n_refs, sizeof local_reg_n_refs);
416 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
417 if (reg_allocno[i] < 0 && reg_renumber[i] >= 0)
419 int regno = reg_renumber[i];
420 int endregno = regno + HARD_REGNO_NREGS (regno, PSEUDO_REGNO_MODE (i));
423 for (j = regno; j < endregno; j++)
425 local_reg_n_refs[j] += reg_n_refs[i];
426 local_reg_live_length[j] += reg_live_length[i];
430 /* We can't override local-alloc for a reg used not just by local-alloc. */
431 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
432 if (regs_ever_live[i])
433 local_reg_n_refs[i] = 0;
435 /* Allocate the space for the conflict and preference tables and
439 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
440 bzero (hard_reg_conflicts, max_allocno * sizeof (HARD_REG_SET));
443 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
444 bzero (hard_reg_preferences, max_allocno * sizeof (HARD_REG_SET));
446 hard_reg_copy_preferences
447 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
448 bzero (hard_reg_copy_preferences, max_allocno * sizeof (HARD_REG_SET));
450 hard_reg_full_preferences
451 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
452 bzero (hard_reg_full_preferences, max_allocno * sizeof (HARD_REG_SET));
455 = (HARD_REG_SET *) alloca (max_allocno * sizeof (HARD_REG_SET));
456 bzero (regs_someone_prefers, max_allocno * sizeof (HARD_REG_SET));
458 allocno_row_words = (max_allocno + INT_BITS - 1) / INT_BITS;
460 conflicts = (int *) alloca (max_allocno * allocno_row_words * sizeof (int));
461 bzero (conflicts, max_allocno * allocno_row_words * sizeof (int));
463 allocnos_live = (int *) alloca (allocno_row_words * sizeof (int));
465 /* If there is work to be done (at least one reg to allocate),
466 perform global conflict analysis and allocate the regs. */
470 /* Scan all the insns and compute the conflicts among allocnos
471 and between allocnos and hard regs. */
475 /* Eliminate conflicts between pseudos and eliminable registers. If
476 the register is not eliminated, the pseudo won't really be able to
477 live in the eliminable register, so the conflict doesn't matter.
478 If we do eliminate the register, the conflict will no longer exist.
479 So in either case, we can ignore the conflict. Likewise for
482 for (i = 0; i < max_allocno; i++)
484 AND_COMPL_HARD_REG_SET (hard_reg_conflicts[i], eliminable_regset);
485 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[i],
487 AND_COMPL_HARD_REG_SET (hard_reg_preferences[i], eliminable_regset);
490 /* Try to expand the preferences by merging them between allocnos. */
492 expand_preferences ();
494 /* Determine the order to allocate the remaining pseudo registers. */
496 allocno_order = (int *) alloca (max_allocno * sizeof (int));
497 for (i = 0; i < max_allocno; i++)
498 allocno_order[i] = i;
500 /* Default the size to 1, since allocno_compare uses it to divide by.
501 Also convert allocno_live_length of zero to -1. A length of zero
502 can occur when all the registers for that allocno have reg_live_length
503 equal to -2. In this case, we want to make an allocno, but not
504 allocate it. So avoid the divide-by-zero and set it to a low
507 for (i = 0; i < max_allocno; i++)
509 if (allocno_size[i] == 0)
511 if (allocno_live_length[i] == 0)
512 allocno_live_length[i] = -1;
515 qsort (allocno_order, max_allocno, sizeof (int), allocno_compare);
517 prune_preferences ();
520 dump_conflicts (file);
522 /* Try allocating them, one by one, in that order,
523 except for parameters marked with reg_live_length[regno] == -2. */
525 for (i = 0; i < max_allocno; i++)
526 if (reg_live_length[allocno_reg[allocno_order[i]]] >= 0)
528 /* If we have more than one register class,
529 first try allocating in the class that is cheapest
530 for this pseudo-reg. If that fails, try any reg. */
531 if (N_REG_CLASSES > 1)
533 find_reg (allocno_order[i], HARD_CONST (0), 0, 0, 0);
534 if (reg_renumber[allocno_reg[allocno_order[i]]] >= 0)
537 if (!reg_preferred_or_nothing (allocno_reg[allocno_order[i]]))
538 find_reg (allocno_order[i], HARD_CONST (0), 1, 0, 0);
542 /* Do the reloads now while the allocno data still exist, so that we can
543 try to assign new hard regs to any pseudo regs that are spilled. */
545 #if 0 /* We need to eliminate regs even if there is no rtl code,
546 for the sake of debugging information. */
547 if (n_basic_blocks > 0)
549 return reload (get_insns (), 1, file);
552 /* Sort predicate for ordering the allocnos.
553 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
556 allocno_compare (v1, v2)
559 /* Note that the quotient will never be bigger than
560 the value of floor_log2 times the maximum number of
561 times a register can occur in one insn (surely less than 100).
562 Multiplying this by 10000 can't overflow. */
564 = (((double) (floor_log2 (allocno_n_refs[*v1]) * allocno_n_refs[*v1])
565 / (allocno_live_length[*v1] * allocno_size[*v1]))
568 = (((double) (floor_log2 (allocno_n_refs[*v2]) * allocno_n_refs[*v2])
569 / (allocno_live_length[*v2] * allocno_size[*v2]))
574 /* If regs are equally good, sort by allocno,
575 so that the results of qsort leave nothing to chance. */
579 /* Scan the rtl code and record all conflicts and register preferences in the
580 conflict matrices and preference tables. */
587 short *block_start_allocnos;
589 /* Make a vector that mark_reg_{store,clobber} will store in. */
590 regs_set = (rtx *) alloca (max_parallel * sizeof (rtx) * 2);
592 block_start_allocnos = (short *) alloca (max_allocno * sizeof (short));
594 for (b = 0; b < n_basic_blocks; b++)
596 bzero (allocnos_live, allocno_row_words * sizeof (int));
598 /* Initialize table of registers currently live
599 to the state at the beginning of this basic block.
600 This also marks the conflicts among them.
602 For pseudo-regs, there is only one bit for each one
603 no matter how many hard regs it occupies.
604 This is ok; we know the size from PSEUDO_REGNO_SIZE.
605 For explicit hard regs, we cannot know the size that way
606 since one hard reg can be used with various sizes.
607 Therefore, we must require that all the hard regs
608 implicitly live as part of a multi-word hard reg
609 are explicitly marked in basic_block_live_at_start. */
612 register int offset, bit;
613 register regset old = basic_block_live_at_start[b];
617 hard_regs_live = old[0];
619 COPY_HARD_REG_SET (hard_regs_live, old);
621 for (offset = 0, i = 0; offset < regset_size; offset++)
622 if (old[offset] == 0)
623 i += HOST_BITS_PER_INT;
625 for (bit = 1; bit; bit <<= 1, i++)
629 if (old[offset] & bit)
631 register int a = reg_allocno[i];
634 SET_ALLOCNO_LIVE (a);
635 block_start_allocnos[ax++] = a;
637 else if ((a = reg_renumber[i]) >= 0)
638 mark_reg_live_nc (a, PSEUDO_REGNO_MODE (i));
642 /* Record that each allocno now live conflicts with each other
643 allocno now live, and with each hard reg now live. */
645 record_conflicts (block_start_allocnos, ax);
648 insn = basic_block_head[b];
650 /* Scan the code of this basic block, noting which allocnos
651 and hard regs are born or die. When one is born,
652 record a conflict with all others currently live. */
656 register RTX_CODE code = GET_CODE (insn);
659 /* Make regs_set an empty set. */
663 if (code == INSN || code == CALL_INSN || code == JUMP_INSN)
668 for (link = REG_NOTES (insn);
669 link && i < NUM_NO_CONFLICT_PAIRS;
670 link = XEXP (link, 1))
671 if (REG_NOTE_KIND (link) == REG_NO_CONFLICT)
673 no_conflict_pairs[i].allocno1
674 = reg_allocno[REGNO (SET_DEST (PATTERN (insn)))];
675 no_conflict_pairs[i].allocno2
676 = reg_allocno[REGNO (XEXP (link, 0))];
681 /* Mark any registers clobbered by INSN as live,
682 so they conflict with the inputs. */
684 note_stores (PATTERN (insn), mark_reg_clobber);
686 /* Mark any registers dead after INSN as dead now. */
688 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
689 if (REG_NOTE_KIND (link) == REG_DEAD)
690 mark_reg_death (XEXP (link, 0));
692 /* Mark any registers set in INSN as live,
693 and mark them as conflicting with all other live regs.
694 Clobbers are processed again, so they conflict with
695 the registers that are set. */
697 note_stores (PATTERN (insn), mark_reg_store);
700 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
701 if (REG_NOTE_KIND (link) == REG_INC)
702 mark_reg_store (XEXP (link, 0), 0);
705 /* If INSN has multiple outputs, then any reg that dies here
706 and is used inside of an output
707 must conflict with the other outputs. */
709 if (GET_CODE (PATTERN (insn)) == PARALLEL && !single_set (insn))
710 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
711 if (REG_NOTE_KIND (link) == REG_DEAD)
713 int used_in_output = 0;
715 rtx reg = XEXP (link, 0);
717 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
719 rtx set = XVECEXP (PATTERN (insn), 0, i);
720 if (GET_CODE (set) == SET
721 && GET_CODE (SET_DEST (set)) != REG
722 && !rtx_equal_p (reg, SET_DEST (set))
723 && reg_overlap_mentioned_p (reg, SET_DEST (set)))
727 mark_reg_conflicts (reg);
730 /* Mark any registers set in INSN and then never used. */
732 while (n_regs_set > 0)
733 if (find_regno_note (insn, REG_UNUSED,
734 REGNO (regs_set[--n_regs_set])))
735 mark_reg_death (regs_set[n_regs_set]);
738 if (insn == basic_block_end[b])
740 insn = NEXT_INSN (insn);
744 /* Expand the preference information by looking for cases where one allocno
745 dies in an insn that sets an allocno. If those two allocnos don't conflict,
746 merge any preferences between those allocnos. */
749 expand_preferences ()
755 /* We only try to handle the most common cases here. Most of the cases
756 where this wins are reg-reg copies. */
758 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
759 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
760 && (set = single_set (insn)) != 0
761 && GET_CODE (SET_DEST (set)) == REG
762 && reg_allocno[REGNO (SET_DEST (set))] >= 0)
763 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
764 if (REG_NOTE_KIND (link) == REG_DEAD
765 && GET_CODE (XEXP (link, 0)) == REG
766 && reg_allocno[REGNO (XEXP (link, 0))] >= 0
767 && ! CONFLICTP (reg_allocno[REGNO (SET_DEST (set))],
768 reg_allocno[REGNO (XEXP (link, 0))])
769 && ! CONFLICTP (reg_allocno[REGNO (XEXP (link, 0))],
770 reg_allocno[REGNO (SET_DEST (set))]))
772 int a1 = reg_allocno[REGNO (SET_DEST (set))];
773 int a2 = reg_allocno[REGNO (XEXP (link, 0))];
775 if (XEXP (link, 0) == SET_SRC (set))
777 IOR_HARD_REG_SET (hard_reg_copy_preferences[a1],
778 hard_reg_copy_preferences[a2]);
779 IOR_HARD_REG_SET (hard_reg_copy_preferences[a2],
780 hard_reg_copy_preferences[a1]);
783 IOR_HARD_REG_SET (hard_reg_preferences[a1],
784 hard_reg_preferences[a2]);
785 IOR_HARD_REG_SET (hard_reg_preferences[a2],
786 hard_reg_preferences[a1]);
787 IOR_HARD_REG_SET (hard_reg_full_preferences[a1],
788 hard_reg_full_preferences[a2]);
789 IOR_HARD_REG_SET (hard_reg_full_preferences[a2],
790 hard_reg_full_preferences[a1]);
794 /* Prune the preferences for global registers to exclude registers that cannot
797 Compute `regs_someone_prefers', which is a bitmask of the hard registers
798 that are preferred by conflicting registers of lower priority. If possible,
799 we will avoid using these registers. */
807 /* Scan least most important to most important.
808 For each allocno, remove from preferences registers that cannot be used,
809 either because of conflicts or register type. Then compute all registers
810 preferred by each lower-priority register that conflicts. */
812 for (i = max_allocno - 1; i >= 0; i--)
816 allocno = allocno_order[i];
817 COPY_HARD_REG_SET (temp, hard_reg_conflicts[allocno]);
819 if (allocno_calls_crossed[allocno] == 0)
820 IOR_HARD_REG_SET (temp, fixed_reg_set);
822 IOR_HARD_REG_SET (temp, call_used_reg_set);
824 IOR_COMPL_HARD_REG_SET
826 reg_class_contents[(int) reg_preferred_class (allocno_reg[allocno])]);
828 AND_COMPL_HARD_REG_SET (hard_reg_preferences[allocno], temp);
829 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[allocno], temp);
830 AND_COMPL_HARD_REG_SET (hard_reg_full_preferences[allocno], temp);
832 CLEAR_HARD_REG_SET (regs_someone_prefers[allocno]);
834 /* Merge in the preferences of lower-priority registers (they have
835 already been pruned). If we also prefer some of those registers,
836 don't exclude them unless we are of a smaller size (in which case
837 we want to give the lower-priority allocno the first chance for
839 for (j = i + 1; j < max_allocno; j++)
840 if (CONFLICTP (allocno, allocno_order[j]))
842 COPY_HARD_REG_SET (temp,
843 hard_reg_full_preferences[allocno_order[j]]);
844 if (allocno_size[allocno_order[j]] <= allocno_size[allocno])
845 AND_COMPL_HARD_REG_SET (temp,
846 hard_reg_full_preferences[allocno]);
848 IOR_HARD_REG_SET (regs_someone_prefers[allocno], temp);
853 /* Assign a hard register to ALLOCNO; look for one that is the beginning
854 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
855 The registers marked in PREFREGS are tried first.
857 LOSERS, if non-zero, is a HARD_REG_SET indicating registers that cannot
858 be used for this allocation.
860 If ALL_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
861 Otherwise ignore that preferred class.
863 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
864 will have to be saved and restored at calls.
866 RETRYING is nonzero if this is called from retry_global_alloc.
868 If we find one, record it in reg_renumber.
869 If not, do nothing. */
872 find_reg (allocno, losers, all_regs_p, accept_call_clobbered, retrying)
876 int accept_call_clobbered;
879 register int i, best_reg, pass;
881 register /* Declare it register if it's a scalar. */
883 HARD_REG_SET used, used1, used2;
886 = all_regs_p ? ALL_REGS : reg_preferred_class (allocno_reg[allocno]);
887 enum machine_mode mode = PSEUDO_REGNO_MODE (allocno_reg[allocno]);
889 if (accept_call_clobbered)
890 COPY_HARD_REG_SET (used1, call_fixed_reg_set);
891 else if (allocno_calls_crossed[allocno] == 0)
892 COPY_HARD_REG_SET (used1, fixed_reg_set);
894 COPY_HARD_REG_SET (used1, call_used_reg_set);
896 /* Some registers should not be allocated in global-alloc. */
897 IOR_HARD_REG_SET (used1, no_global_alloc_regs);
899 IOR_HARD_REG_SET (used1, losers);
901 IOR_COMPL_HARD_REG_SET (used1, reg_class_contents[(int) class]);
902 COPY_HARD_REG_SET (used2, used1);
904 IOR_HARD_REG_SET (used1, hard_reg_conflicts[allocno]);
906 /* Try each hard reg to see if it fits. Do this in two passes.
907 In the first pass, skip registers that are preferred by some other pseudo
908 to give it a better chance of getting one of those registers. Only if
909 we can't get a register when excluding those do we take one of them.
910 However, we never allocate a register for the first time in pass 0. */
912 COPY_HARD_REG_SET (used, used1);
913 IOR_COMPL_HARD_REG_SET (used, regs_used_so_far);
914 IOR_HARD_REG_SET (used, regs_someone_prefers[allocno]);
917 for (i = FIRST_PSEUDO_REGISTER, pass = 0;
918 pass <= 1 && i >= FIRST_PSEUDO_REGISTER;
922 COPY_HARD_REG_SET (used, used1);
923 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
925 #ifdef REG_ALLOC_ORDER
926 int regno = reg_alloc_order[i];
930 if (! TEST_HARD_REG_BIT (used, regno)
931 && HARD_REGNO_MODE_OK (regno, mode))
934 register int lim = regno + HARD_REGNO_NREGS (regno, mode);
937 && ! TEST_HARD_REG_BIT (used, j));
944 #ifndef REG_ALLOC_ORDER
945 i = j; /* Skip starting points we know will lose */
951 /* See if there is a preferred register with the same class as the register
952 we allocated above. Making this restriction prevents register
953 preferencing from creating worse register allocation.
955 Remove from the preferred registers and conflicting registers. Note that
956 additional conflicts may have been added after `prune_preferences' was
959 First do this for those register with copy preferences, then all
960 preferred registers. */
962 AND_COMPL_HARD_REG_SET (hard_reg_copy_preferences[allocno], used);
963 GO_IF_HARD_REG_SUBSET (hard_reg_copy_preferences[allocno],
964 reg_class_contents[(int) NO_REGS], no_copy_prefs);
968 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
969 if (TEST_HARD_REG_BIT (hard_reg_copy_preferences[allocno], i)
970 && HARD_REGNO_MODE_OK (i, mode)
971 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
972 || reg_class_subset_p (REGNO_REG_CLASS (i),
973 REGNO_REG_CLASS (best_reg))
974 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
975 REGNO_REG_CLASS (i))))
978 register int lim = i + HARD_REGNO_NREGS (i, mode);
981 && ! TEST_HARD_REG_BIT (used, j)
982 && (REGNO_REG_CLASS (j)
983 == REGNO_REG_CLASS (best_reg + (j - i))
984 || reg_class_subset_p (REGNO_REG_CLASS (j),
985 REGNO_REG_CLASS (best_reg + (j - i)))
986 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
987 REGNO_REG_CLASS (j))));
998 AND_COMPL_HARD_REG_SET (hard_reg_preferences[allocno], used);
999 GO_IF_HARD_REG_SUBSET (hard_reg_preferences[allocno],
1000 reg_class_contents[(int) NO_REGS], no_prefs);
1004 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1005 if (TEST_HARD_REG_BIT (hard_reg_preferences[allocno], i)
1006 && HARD_REGNO_MODE_OK (i, mode)
1007 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1008 || reg_class_subset_p (REGNO_REG_CLASS (i),
1009 REGNO_REG_CLASS (best_reg))
1010 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1011 REGNO_REG_CLASS (i))))
1014 register int lim = i + HARD_REGNO_NREGS (i, mode);
1017 && ! TEST_HARD_REG_BIT (used, j)
1018 && (REGNO_REG_CLASS (j)
1019 == REGNO_REG_CLASS (best_reg + (j - i))
1020 || reg_class_subset_p (REGNO_REG_CLASS (j),
1021 REGNO_REG_CLASS (best_reg + (j - i)))
1022 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1023 REGNO_REG_CLASS (j))));
1034 /* If we haven't succeeded yet, try with caller-saves. */
1035 if (flag_caller_saves && best_reg < 0)
1037 /* Did not find a register. If it would be profitable to
1038 allocate a call-clobbered register and save and restore it
1039 around calls, do that. */
1040 if (! accept_call_clobbered
1041 && allocno_calls_crossed[allocno] != 0
1042 && CALLER_SAVE_PROFITABLE (allocno_n_refs[allocno],
1043 allocno_calls_crossed[allocno]))
1045 find_reg (allocno, losers, all_regs_p, 1, retrying);
1046 if (reg_renumber[allocno_reg[allocno]] >= 0)
1048 caller_save_needed = 1;
1054 /* If we haven't succeeded yet,
1055 see if some hard reg that conflicts with us
1056 was utilized poorly by local-alloc.
1057 If so, kick out the regs that were put there by local-alloc
1058 so we can use it instead. */
1059 if (best_reg < 0 && !retrying
1060 /* Let's not bother with multi-reg allocnos. */
1061 && allocno_size[allocno] == 1)
1063 /* Count from the end, to find the least-used ones first. */
1064 for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1065 if (local_reg_n_refs[i] != 0
1066 /* Don't use a reg no good for this pseudo. */
1067 && ! TEST_HARD_REG_BIT (used2, i)
1068 && HARD_REGNO_MODE_OK (i, mode)
1069 && ((double) local_reg_n_refs[i] / local_reg_live_length[i]
1070 < ((double) allocno_n_refs[allocno]
1071 / allocno_live_length[allocno])))
1073 /* Hard reg I was used less in total by local regs
1074 than it would be used by this one allocno! */
1076 for (k = 0; k < max_regno; k++)
1077 if (reg_renumber[k] >= 0)
1079 int regno = reg_renumber[k];
1081 = regno + HARD_REGNO_NREGS (regno, PSEUDO_REGNO_MODE (k));
1083 if (i >= regno && i < endregno)
1084 reg_renumber[k] = -1;
1092 /* Did we find a register? */
1096 register int lim, j;
1097 HARD_REG_SET this_reg;
1099 /* Yes. Record it as the hard register of this pseudo-reg. */
1100 reg_renumber[allocno_reg[allocno]] = best_reg;
1101 /* Also of any pseudo-regs that share with it. */
1102 if (reg_may_share[allocno_reg[allocno]])
1103 for (j = FIRST_PSEUDO_REGISTER; j < max_regno; j++)
1104 if (reg_allocno[j] == allocno)
1105 reg_renumber[j] = best_reg;
1107 /* Make a set of the hard regs being allocated. */
1108 CLEAR_HARD_REG_SET (this_reg);
1109 lim = best_reg + HARD_REGNO_NREGS (best_reg, mode);
1110 for (j = best_reg; j < lim; j++)
1112 SET_HARD_REG_BIT (this_reg, j);
1113 SET_HARD_REG_BIT (regs_used_so_far, j);
1114 /* This is no longer a reg used just by local regs. */
1115 local_reg_n_refs[j] = 0;
1117 /* For each other pseudo-reg conflicting with this one,
1118 mark it as conflicting with the hard regs this one occupies. */
1120 for (j = 0; j < max_allocno; j++)
1121 if (CONFLICTP (lim, j) || CONFLICTP (j, lim))
1123 IOR_HARD_REG_SET (hard_reg_conflicts[j], this_reg);
1128 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1129 Perhaps it had previously seemed not worth a hard reg,
1130 or perhaps its old hard reg has been commandeered for reloads.
1131 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1132 they do not appear to be allocated.
1133 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1136 retry_global_alloc (regno, forbidden_regs)
1138 HARD_REG_SET forbidden_regs;
1140 int allocno = reg_allocno[regno];
1143 /* If we have more than one register class,
1144 first try allocating in the class that is cheapest
1145 for this pseudo-reg. If that fails, try any reg. */
1146 if (N_REG_CLASSES > 1)
1147 find_reg (allocno, forbidden_regs, 0, 0, 1);
1148 if (reg_renumber[regno] < 0
1149 && !reg_preferred_or_nothing (regno))
1150 find_reg (allocno, forbidden_regs, 1, 0, 1);
1152 /* If we found a register, modify the RTL for the register to
1153 show the hard register, and mark that register live. */
1154 if (reg_renumber[regno] >= 0)
1156 REGNO (regno_reg_rtx[regno]) = reg_renumber[regno];
1157 mark_home_live (regno);
1162 /* Record a conflict between register REGNO
1163 and everything currently live.
1164 REGNO must not be a pseudo reg that was allocated
1165 by local_alloc; such numbers must be translated through
1166 reg_renumber before calling here. */
1169 record_one_conflict (regno)
1174 if (regno < FIRST_PSEUDO_REGISTER)
1175 /* When a hard register becomes live,
1176 record conflicts with live pseudo regs. */
1177 for (j = 0; j < max_allocno; j++)
1179 if (ALLOCNO_LIVE_P (j))
1180 SET_HARD_REG_BIT (hard_reg_conflicts[j], regno);
1183 /* When a pseudo-register becomes live,
1184 record conflicts first with hard regs,
1185 then with other pseudo regs. */
1187 register int ialloc = reg_allocno[regno];
1188 register int ialloc_prod = ialloc * allocno_row_words;
1189 IOR_HARD_REG_SET (hard_reg_conflicts[ialloc], hard_regs_live);
1190 for (j = allocno_row_words - 1; j >= 0; j--)
1194 for (k = 0; k < n_no_conflict_pairs; k++)
1195 if (! ((j == no_conflict_pairs[k].allocno1
1196 && ialloc == no_conflict_pairs[k].allocno2)
1198 (j == no_conflict_pairs[k].allocno2
1199 && ialloc == no_conflict_pairs[k].allocno1)))
1201 conflicts[ialloc_prod + j] |= allocnos_live[j];
1206 /* Record all allocnos currently live as conflicting
1207 with each other and with all hard regs currently live.
1208 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1209 are currently live. Their bits are also flagged in allocnos_live. */
1212 record_conflicts (allocno_vec, len)
1213 register short *allocno_vec;
1216 register int allocno;
1218 register int ialloc_prod;
1222 allocno = allocno_vec[len];
1223 ialloc_prod = allocno * allocno_row_words;
1224 IOR_HARD_REG_SET (hard_reg_conflicts[allocno], hard_regs_live);
1225 for (j = allocno_row_words - 1; j >= 0; j--)
1226 conflicts[ialloc_prod + j] |= allocnos_live[j];
1230 /* Handle the case where REG is set by the insn being scanned,
1231 during the forward scan to accumulate conflicts.
1232 Store a 1 in regs_live or allocnos_live for this register, record how many
1233 consecutive hardware registers it actually needs,
1234 and record a conflict with all other registers already live.
1236 Note that even if REG does not remain alive after this insn,
1237 we must mark it here as live, to ensure a conflict between
1238 REG and any other regs set in this insn that really do live.
1239 This is because those other regs could be considered after this.
1241 REG might actually be something other than a register;
1242 if so, we do nothing.
1244 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1245 a REG_INC note was found for it).
1247 CLOBBERs are processed here by calling mark_reg_clobber. */
1250 mark_reg_store (orig_reg, setter)
1251 rtx orig_reg, setter;
1254 register rtx reg = orig_reg;
1256 /* WORD is which word of a multi-register group is being stored.
1257 For the case where the store is actually into a SUBREG of REG.
1258 Except we don't use it; I believe the entire REG needs to be
1262 if (GET_CODE (reg) == SUBREG)
1264 word = SUBREG_WORD (reg);
1265 reg = SUBREG_REG (reg);
1268 if (GET_CODE (reg) != REG)
1271 if (setter && GET_CODE (setter) == CLOBBER)
1273 /* A clobber of a register should be processed here too. */
1274 mark_reg_clobber (orig_reg, setter);
1278 regs_set[n_regs_set++] = reg;
1281 set_preference (reg, SET_SRC (setter));
1283 regno = REGNO (reg);
1285 if (reg_renumber[regno] >= 0)
1286 regno = reg_renumber[regno] /* + word */;
1288 /* Either this is one of the max_allocno pseudo regs not allocated,
1289 or it is or has a hardware reg. First handle the pseudo-regs. */
1290 if (regno >= FIRST_PSEUDO_REGISTER)
1292 if (reg_allocno[regno] >= 0)
1294 SET_ALLOCNO_LIVE (reg_allocno[regno]);
1295 record_one_conflict (regno);
1298 /* Handle hardware regs (and pseudos allocated to hard regs). */
1299 else if (! fixed_regs[regno])
1301 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1302 while (regno < last)
1304 record_one_conflict (regno);
1305 SET_HARD_REG_BIT (hard_regs_live, regno);
1311 /* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
1314 mark_reg_clobber (reg, setter)
1319 /* WORD is which word of a multi-register group is being stored.
1320 For the case where the store is actually into a SUBREG of REG.
1321 Except we don't use it; I believe the entire REG needs to be
1325 if (GET_CODE (setter) != CLOBBER)
1328 if (GET_CODE (reg) == SUBREG)
1330 word = SUBREG_WORD (reg);
1331 reg = SUBREG_REG (reg);
1334 if (GET_CODE (reg) != REG)
1337 regs_set[n_regs_set++] = reg;
1339 regno = REGNO (reg);
1341 if (reg_renumber[regno] >= 0)
1342 regno = reg_renumber[regno] /* + word */;
1344 /* Either this is one of the max_allocno pseudo regs not allocated,
1345 or it is or has a hardware reg. First handle the pseudo-regs. */
1346 if (regno >= FIRST_PSEUDO_REGISTER)
1348 if (reg_allocno[regno] >= 0)
1350 SET_ALLOCNO_LIVE (reg_allocno[regno]);
1351 record_one_conflict (regno);
1354 /* Handle hardware regs (and pseudos allocated to hard regs). */
1355 else if (! fixed_regs[regno])
1357 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1358 while (regno < last)
1360 record_one_conflict (regno);
1361 SET_HARD_REG_BIT (hard_regs_live, regno);
1367 /* Record that REG has conflicts with all the regs currently live.
1368 Do not mark REG itself as live. */
1371 mark_reg_conflicts (reg)
1376 if (GET_CODE (reg) == SUBREG)
1377 reg = SUBREG_REG (reg);
1379 if (GET_CODE (reg) != REG)
1382 regno = REGNO (reg);
1384 if (reg_renumber[regno] >= 0)
1385 regno = reg_renumber[regno];
1387 /* Either this is one of the max_allocno pseudo regs not allocated,
1388 or it is or has a hardware reg. First handle the pseudo-regs. */
1389 if (regno >= FIRST_PSEUDO_REGISTER)
1391 if (reg_allocno[regno] >= 0)
1392 record_one_conflict (regno);
1394 /* Handle hardware regs (and pseudos allocated to hard regs). */
1395 else if (! fixed_regs[regno])
1397 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1398 while (regno < last)
1400 record_one_conflict (regno);
1406 /* Mark REG as being dead (following the insn being scanned now).
1407 Store a 0 in regs_live or allocnos_live for this register. */
1410 mark_reg_death (reg)
1413 register int regno = REGNO (reg);
1415 /* For pseudo reg, see if it has been assigned a hardware reg. */
1416 if (reg_renumber[regno] >= 0)
1417 regno = reg_renumber[regno];
1419 /* Either this is one of the max_allocno pseudo regs not allocated,
1420 or it is a hardware reg. First handle the pseudo-regs. */
1421 if (regno >= FIRST_PSEUDO_REGISTER)
1423 if (reg_allocno[regno] >= 0)
1424 CLEAR_ALLOCNO_LIVE (reg_allocno[regno]);
1426 /* Handle hardware regs (and pseudos allocated to hard regs). */
1427 else if (! fixed_regs[regno])
1429 /* Pseudo regs already assigned hardware regs are treated
1430 almost the same as explicit hardware regs. */
1431 register int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1432 while (regno < last)
1434 CLEAR_HARD_REG_BIT (hard_regs_live, regno);
1440 /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1441 for the value stored in it. MODE determines how many consecutive
1442 registers are actually in use. Do not record conflicts;
1443 it is assumed that the caller will do that. */
1446 mark_reg_live_nc (regno, mode)
1448 enum machine_mode mode;
1450 register int last = regno + HARD_REGNO_NREGS (regno, mode);
1451 while (regno < last)
1453 SET_HARD_REG_BIT (hard_regs_live, regno);
1458 /* Try to set a preference for an allocno to a hard register.
1459 We are passed DEST and SRC which are the operands of a SET. It is known
1460 that SRC is a register. If SRC or the first operand of SRC is a register,
1461 try to set a preference. If one of the two is a hard register and the other
1462 is a pseudo-register, mark the preference.
1464 Note that we are not as aggressive as local-alloc in trying to tie a
1465 pseudo-register to a hard register. */
1468 set_preference (dest, src)
1471 int src_regno, dest_regno;
1472 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1473 to compensate for subregs in SRC or DEST. */
1478 if (GET_RTX_FORMAT (GET_CODE (src))[0] == 'e')
1479 src = XEXP (src, 0), copy = 0;
1481 /* Get the reg number for both SRC and DEST.
1482 If neither is a reg, give up. */
1484 if (GET_CODE (src) == REG)
1485 src_regno = REGNO (src);
1486 else if (GET_CODE (src) == SUBREG && GET_CODE (SUBREG_REG (src)) == REG)
1488 src_regno = REGNO (SUBREG_REG (src));
1489 offset += SUBREG_WORD (src);
1494 if (GET_CODE (dest) == REG)
1495 dest_regno = REGNO (dest);
1496 else if (GET_CODE (dest) == SUBREG && GET_CODE (SUBREG_REG (dest)) == REG)
1498 dest_regno = REGNO (SUBREG_REG (dest));
1499 offset -= SUBREG_WORD (dest);
1504 /* Convert either or both to hard reg numbers. */
1506 if (reg_renumber[src_regno] >= 0)
1507 src_regno = reg_renumber[src_regno];
1509 if (reg_renumber[dest_regno] >= 0)
1510 dest_regno = reg_renumber[dest_regno];
1512 /* Now if one is a hard reg and the other is a global pseudo
1513 then give the other a preference. */
1515 if (dest_regno < FIRST_PSEUDO_REGISTER && src_regno >= FIRST_PSEUDO_REGISTER
1516 && reg_allocno[src_regno] >= 0)
1518 dest_regno -= offset;
1519 if (dest_regno >= 0 && dest_regno < FIRST_PSEUDO_REGISTER)
1522 SET_REGBIT (hard_reg_copy_preferences,
1523 reg_allocno[src_regno], dest_regno);
1525 SET_REGBIT (hard_reg_preferences,
1526 reg_allocno[src_regno], dest_regno);
1527 for (i = dest_regno;
1528 i < dest_regno + HARD_REGNO_NREGS (dest_regno, GET_MODE (dest));
1530 SET_REGBIT (hard_reg_full_preferences, reg_allocno[src_regno], i);
1534 if (src_regno < FIRST_PSEUDO_REGISTER && dest_regno >= FIRST_PSEUDO_REGISTER
1535 && reg_allocno[dest_regno] >= 0)
1537 src_regno += offset;
1538 if (src_regno >= 0 && src_regno < FIRST_PSEUDO_REGISTER)
1541 SET_REGBIT (hard_reg_copy_preferences,
1542 reg_allocno[dest_regno], src_regno);
1544 SET_REGBIT (hard_reg_preferences,
1545 reg_allocno[dest_regno], src_regno);
1547 i < src_regno + HARD_REGNO_NREGS (src_regno, GET_MODE (src));
1549 SET_REGBIT (hard_reg_full_preferences, reg_allocno[dest_regno], i);
1554 /* Indicate that hard register number FROM was eliminated and replaced with
1555 an offset from hard register number TO. The status of hard registers live
1556 at the start of a basic block is updated by replacing a use of FROM with
1560 mark_elimination (from, to)
1565 for (i = 0; i < n_basic_blocks; i++)
1566 if ((basic_block_live_at_start[i][from / HOST_BITS_PER_INT]
1567 & (1 << (from % HOST_BITS_PER_INT))) != 0)
1569 basic_block_live_at_start[i][from / HOST_BITS_PER_INT]
1570 &= ~ (1 << (from % HOST_BITS_PER_INT));
1571 basic_block_live_at_start[i][to / HOST_BITS_PER_INT]
1572 |= (1 << (to % HOST_BITS_PER_INT));
1576 /* Print debugging trace information if -greg switch is given,
1577 showing the information on which the allocation decisions are based. */
1580 dump_conflicts (file)
1584 register int has_preferences;
1585 fprintf (file, ";; %d regs to allocate:", max_allocno);
1586 for (i = 0; i < max_allocno; i++)
1589 fprintf (file, " %d", allocno_reg[allocno_order[i]]);
1590 for (j = 0; j < max_regno; j++)
1591 if (reg_allocno[j] == allocno_order[i]
1592 && j != allocno_reg[allocno_order[i]])
1593 fprintf (file, "+%d", j);
1594 if (allocno_size[allocno_order[i]] != 1)
1595 fprintf (file, " (%d)", allocno_size[allocno_order[i]]);
1597 fprintf (file, "\n");
1599 for (i = 0; i < max_allocno; i++)
1602 fprintf (file, ";; %d conflicts:", allocno_reg[i]);
1603 for (j = 0; j < max_allocno; j++)
1604 if (CONFLICTP (i, j) || CONFLICTP (j, i))
1605 fprintf (file, " %d", allocno_reg[j]);
1606 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1607 if (TEST_HARD_REG_BIT (hard_reg_conflicts[i], j))
1608 fprintf (file, " %d", j);
1609 fprintf (file, "\n");
1611 has_preferences = 0;
1612 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1613 if (TEST_HARD_REG_BIT (hard_reg_preferences[i], j))
1614 has_preferences = 1;
1616 if (! has_preferences)
1618 fprintf (file, ";; %d preferences:", allocno_reg[i]);
1619 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1620 if (TEST_HARD_REG_BIT (hard_reg_preferences[i], j))
1621 fprintf (file, " %d", j);
1622 fprintf (file, "\n");
1624 fprintf (file, "\n");
1628 dump_global_regs (file)
1633 fprintf (file, ";; Register dispositions:\n");
1634 for (i = FIRST_PSEUDO_REGISTER, j = 0; i < max_regno; i++)
1635 if (reg_renumber[i] >= 0)
1637 fprintf (file, "%d in %d ", i, reg_renumber[i]);
1639 fprintf (file, "\n");
1642 fprintf (file, "\n\n;; Hard regs used: ");
1643 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1644 if (regs_ever_live[i])
1645 fprintf (file, " %d", i);
1646 fprintf (file, "\n\n");