2002-08-22 Paolo Carlini <pcarlini@unitus.it>
[official-gcc.git] / gcc / global.c
blobd7950fa9aa29112d485f03ab0730fcfadf4efba6
1 /* Allocate registers for pseudo-registers that span basic blocks.
2 Copyright (C) 1987, 1988, 1991, 1994, 1996, 1997, 1998,
3 1999, 2000, 2002 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, USA. */
23 #include "config.h"
24 #include "system.h"
26 #include "machmode.h"
27 #include "hard-reg-set.h"
28 #include "rtl.h"
29 #include "tm_p.h"
30 #include "flags.h"
31 #include "basic-block.h"
32 #include "regs.h"
33 #include "function.h"
34 #include "insn-config.h"
35 #include "reload.h"
36 #include "output.h"
37 #include "toplev.h"
39 /* This pass of the compiler performs global register allocation.
40 It assigns hard register numbers to all the pseudo registers
41 that were not handled in local_alloc. Assignments are recorded
42 in the vector reg_renumber, not by changing the rtl code.
43 (Such changes are made by final). The entry point is
44 the function global_alloc.
46 After allocation is complete, the reload pass is run as a subroutine
47 of this pass, so that when a pseudo reg loses its hard reg due to
48 spilling it is possible to make a second attempt to find a hard
49 reg for it. The reload pass is independent in other respects
50 and it is run even when stupid register allocation is in use.
52 1. Assign allocation-numbers (allocnos) to the pseudo-registers
53 still needing allocations and to the pseudo-registers currently
54 allocated by local-alloc which may be spilled by reload.
55 Set up tables reg_allocno and allocno_reg to map
56 reg numbers to allocnos and vice versa.
57 max_allocno gets the number of allocnos in use.
59 2. Allocate a max_allocno by max_allocno conflict bit matrix and clear it.
60 Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix
61 for conflicts between allocnos and explicit hard register use
62 (which includes use of pseudo-registers allocated by local_alloc).
64 3. For each basic block
65 walk forward through the block, recording which
66 pseudo-registers and which hardware registers are live.
67 Build the conflict matrix between the pseudo-registers
68 and another of pseudo-registers versus hardware registers.
69 Also record the preferred hardware registers
70 for each pseudo-register.
72 4. Sort a table of the allocnos into order of
73 desirability of the variables.
75 5. Allocate the variables in that order; each if possible into
76 a preferred register, else into another register. */
78 /* Number of pseudo-registers which are candidates for allocation. */
80 static int max_allocno;
82 /* Indexed by (pseudo) reg number, gives the allocno, or -1
83 for pseudo registers which are not to be allocated. */
85 static int *reg_allocno;
87 struct allocno
89 int reg;
90 /* Gives the number of consecutive hard registers needed by that
91 pseudo reg. */
92 int size;
94 /* Number of calls crossed by each allocno. */
95 int calls_crossed;
97 /* Number of refs to each allocno. */
98 int n_refs;
100 /* Frequency of uses of each allocno. */
101 int freq;
103 /* Guess at live length of each allocno.
104 This is actually the max of the live lengths of the regs. */
105 int live_length;
107 /* Set of hard regs conflicting with allocno N. */
109 HARD_REG_SET hard_reg_conflicts;
111 /* Set of hard regs preferred by allocno N.
112 This is used to make allocnos go into regs that are copied to or from them,
113 when possible, to reduce register shuffling. */
115 HARD_REG_SET hard_reg_preferences;
117 /* Similar, but just counts register preferences made in simple copy
118 operations, rather than arithmetic. These are given priority because
119 we can always eliminate an insn by using these, but using a register
120 in the above list won't always eliminate an insn. */
122 HARD_REG_SET hard_reg_copy_preferences;
124 /* Similar to hard_reg_preferences, but includes bits for subsequent
125 registers when an allocno is multi-word. The above variable is used for
126 allocation while this is used to build reg_someone_prefers, below. */
128 HARD_REG_SET hard_reg_full_preferences;
130 /* Set of hard registers that some later allocno has a preference for. */
132 HARD_REG_SET regs_someone_prefers;
135 static struct allocno *allocno;
137 /* A vector of the integers from 0 to max_allocno-1,
138 sorted in the order of first-to-be-allocated first. */
140 static int *allocno_order;
142 /* Indexed by (pseudo) reg number, gives the number of another
143 lower-numbered pseudo reg which can share a hard reg with this pseudo
144 *even if the two pseudos would otherwise appear to conflict*. */
146 static int *reg_may_share;
148 /* Define the number of bits in each element of `conflicts' and what
149 type that element has. We use the largest integer format on the
150 host machine. */
152 #define INT_BITS HOST_BITS_PER_WIDE_INT
153 #define INT_TYPE HOST_WIDE_INT
155 /* max_allocno by max_allocno array of bits,
156 recording whether two allocno's conflict (can't go in the same
157 hardware register).
159 `conflicts' is symmetric after the call to mirror_conflicts. */
161 static INT_TYPE *conflicts;
163 /* Number of ints require to hold max_allocno bits.
164 This is the length of a row in `conflicts'. */
166 static int allocno_row_words;
168 /* Two macros to test or store 1 in an element of `conflicts'. */
170 #define CONFLICTP(I, J) \
171 (conflicts[(I) * allocno_row_words + (unsigned) (J) / INT_BITS] \
172 & ((INT_TYPE) 1 << ((unsigned) (J) % INT_BITS)))
174 /* For any allocno set in ALLOCNO_SET, set ALLOCNO to that allocno,
175 and execute CODE. */
176 #define EXECUTE_IF_SET_IN_ALLOCNO_SET(ALLOCNO_SET, ALLOCNO, CODE) \
177 do { \
178 int i_; \
179 int allocno_; \
180 INT_TYPE *p_ = (ALLOCNO_SET); \
182 for (i_ = allocno_row_words - 1, allocno_ = 0; i_ >= 0; \
183 i_--, allocno_ += INT_BITS) \
185 unsigned INT_TYPE word_ = (unsigned INT_TYPE) *p_++; \
187 for ((ALLOCNO) = allocno_; word_; word_ >>= 1, (ALLOCNO)++) \
189 if (word_ & 1) \
190 {CODE;} \
193 } while (0)
195 /* This doesn't work for non-GNU C due to the way CODE is macro expanded. */
196 #if 0
197 /* For any allocno that conflicts with IN_ALLOCNO, set OUT_ALLOCNO to
198 the conflicting allocno, and execute CODE. This macro assumes that
199 mirror_conflicts has been run. */
200 #define EXECUTE_IF_CONFLICT(IN_ALLOCNO, OUT_ALLOCNO, CODE)\
201 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + (IN_ALLOCNO) * allocno_row_words,\
202 OUT_ALLOCNO, (CODE))
203 #endif
205 /* Set of hard regs currently live (during scan of all insns). */
207 static HARD_REG_SET hard_regs_live;
209 /* Set of registers that global-alloc isn't supposed to use. */
211 static HARD_REG_SET no_global_alloc_regs;
213 /* Set of registers used so far. */
215 static HARD_REG_SET regs_used_so_far;
217 /* Number of refs to each hard reg, as used by local alloc.
218 It is zero for a reg that contains global pseudos or is explicitly used. */
220 static int local_reg_n_refs[FIRST_PSEUDO_REGISTER];
222 /* Frequency of uses of given hard reg. */
223 static int local_reg_freq[FIRST_PSEUDO_REGISTER];
225 /* Guess at live length of each hard reg, as used by local alloc.
226 This is actually the sum of the live lengths of the specific regs. */
228 static int local_reg_live_length[FIRST_PSEUDO_REGISTER];
230 /* Set to 1 a bit in a vector TABLE of HARD_REG_SETs, for vector
231 element I, and hard register number J. */
233 #define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (allocno[I].TABLE, J)
235 /* Bit mask for allocnos live at current point in the scan. */
237 static INT_TYPE *allocnos_live;
239 /* Test, set or clear bit number I in allocnos_live,
240 a bit vector indexed by allocno. */
242 #define SET_ALLOCNO_LIVE(I) \
243 (allocnos_live[(unsigned) (I) / INT_BITS] \
244 |= ((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS)))
246 #define CLEAR_ALLOCNO_LIVE(I) \
247 (allocnos_live[(unsigned) (I) / INT_BITS] \
248 &= ~((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS)))
250 /* This is turned off because it doesn't work right for DImode.
251 (And it is only used for DImode, so the other cases are worthless.)
252 The problem is that it isn't true that there is NO possibility of conflict;
253 only that there is no conflict if the two pseudos get the exact same regs.
254 If they were allocated with a partial overlap, there would be a conflict.
255 We can't safely turn off the conflict unless we have another way to
256 prevent the partial overlap.
258 Idea: change hard_reg_conflicts so that instead of recording which
259 hard regs the allocno may not overlap, it records where the allocno
260 may not start. Change both where it is used and where it is updated.
261 Then there is a way to record that (reg:DI 108) may start at 10
262 but not at 9 or 11. There is still the question of how to record
263 this semi-conflict between two pseudos. */
264 #if 0
265 /* Reg pairs for which conflict after the current insn
266 is inhibited by a REG_NO_CONFLICT note.
267 If the table gets full, we ignore any other notes--that is conservative. */
268 #define NUM_NO_CONFLICT_PAIRS 4
269 /* Number of pairs in use in this insn. */
270 int n_no_conflict_pairs;
271 static struct { int allocno1, allocno2;}
272 no_conflict_pairs[NUM_NO_CONFLICT_PAIRS];
273 #endif /* 0 */
275 /* Record all regs that are set in any one insn.
276 Communication from mark_reg_{store,clobber} and global_conflicts. */
278 static rtx *regs_set;
279 static int n_regs_set;
281 /* All registers that can be eliminated. */
283 static HARD_REG_SET eliminable_regset;
285 static int allocno_compare PARAMS ((const PTR, const PTR));
286 static void global_conflicts PARAMS ((void));
287 static void mirror_conflicts PARAMS ((void));
288 static void expand_preferences PARAMS ((void));
289 static void prune_preferences PARAMS ((void));
290 static void find_reg PARAMS ((int, HARD_REG_SET, int, int, int));
291 static void record_one_conflict PARAMS ((int));
292 static void record_conflicts PARAMS ((int *, int));
293 static void mark_reg_store PARAMS ((rtx, rtx, void *));
294 static void mark_reg_clobber PARAMS ((rtx, rtx, void *));
295 static void mark_reg_conflicts PARAMS ((rtx));
296 static void mark_reg_death PARAMS ((rtx));
297 static void mark_reg_live_nc PARAMS ((int, enum machine_mode));
298 static void set_preference PARAMS ((rtx, rtx));
299 static void dump_conflicts PARAMS ((FILE *));
300 static void reg_becomes_live PARAMS ((rtx, rtx, void *));
301 static void reg_dies PARAMS ((int, enum machine_mode,
302 struct insn_chain *));
304 /* Perform allocation of pseudo-registers not allocated by local_alloc.
305 FILE is a file to output debugging information on,
306 or zero if such output is not desired.
308 Return value is nonzero if reload failed
309 and we must not do any more for this function. */
312 global_alloc (file)
313 FILE *file;
315 int retval;
316 #ifdef ELIMINABLE_REGS
317 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
318 #endif
319 int need_fp
320 = (! flag_omit_frame_pointer
321 #ifdef EXIT_IGNORE_STACK
322 || (current_function_calls_alloca && EXIT_IGNORE_STACK)
323 #endif
324 || FRAME_POINTER_REQUIRED);
326 size_t i;
327 rtx x;
329 max_allocno = 0;
331 /* A machine may have certain hard registers that
332 are safe to use only within a basic block. */
334 CLEAR_HARD_REG_SET (no_global_alloc_regs);
336 /* Build the regset of all eliminable registers and show we can't use those
337 that we already know won't be eliminated. */
338 #ifdef ELIMINABLE_REGS
339 for (i = 0; i < ARRAY_SIZE (eliminables); i++)
341 SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from);
343 if (! CAN_ELIMINATE (eliminables[i].from, eliminables[i].to)
344 || (eliminables[i].to == STACK_POINTER_REGNUM && need_fp))
345 SET_HARD_REG_BIT (no_global_alloc_regs, eliminables[i].from);
347 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
348 SET_HARD_REG_BIT (eliminable_regset, HARD_FRAME_POINTER_REGNUM);
349 if (need_fp)
350 SET_HARD_REG_BIT (no_global_alloc_regs, HARD_FRAME_POINTER_REGNUM);
351 #endif
353 #else
354 SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM);
355 if (need_fp)
356 SET_HARD_REG_BIT (no_global_alloc_regs, FRAME_POINTER_REGNUM);
357 #endif
359 /* Track which registers have already been used. Start with registers
360 explicitly in the rtl, then registers allocated by local register
361 allocation. */
363 CLEAR_HARD_REG_SET (regs_used_so_far);
364 #ifdef LEAF_REGISTERS
365 /* If we are doing the leaf function optimization, and this is a leaf
366 function, it means that the registers that take work to save are those
367 that need a register window. So prefer the ones that can be used in
368 a leaf function. */
370 const char *cheap_regs;
371 const char *const leaf_regs = LEAF_REGISTERS;
373 if (only_leaf_regs_used () && leaf_function_p ())
374 cheap_regs = leaf_regs;
375 else
376 cheap_regs = call_used_regs;
377 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
378 if (regs_ever_live[i] || cheap_regs[i])
379 SET_HARD_REG_BIT (regs_used_so_far, i);
381 #else
382 /* We consider registers that do not have to be saved over calls as if
383 they were already used since there is no cost in using them. */
384 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
385 if (regs_ever_live[i] || call_used_regs[i])
386 SET_HARD_REG_BIT (regs_used_so_far, i);
387 #endif
389 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
390 if (reg_renumber[i] >= 0)
391 SET_HARD_REG_BIT (regs_used_so_far, reg_renumber[i]);
393 /* Establish mappings from register number to allocation number
394 and vice versa. In the process, count the allocnos. */
396 reg_allocno = (int *) xmalloc (max_regno * sizeof (int));
398 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
399 reg_allocno[i] = -1;
401 /* Initialize the shared-hard-reg mapping
402 from the list of pairs that may share. */
403 reg_may_share = (int *) xcalloc (max_regno, sizeof (int));
404 for (x = regs_may_share; x; x = XEXP (XEXP (x, 1), 1))
406 int r1 = REGNO (XEXP (x, 0));
407 int r2 = REGNO (XEXP (XEXP (x, 1), 0));
408 if (r1 > r2)
409 reg_may_share[r1] = r2;
410 else
411 reg_may_share[r2] = r1;
414 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
415 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
416 that we are supposed to refrain from putting in a hard reg.
417 -2 means do make an allocno but don't allocate it. */
418 if (REG_N_REFS (i) != 0 && REG_LIVE_LENGTH (i) != -1
419 /* Don't allocate pseudos that cross calls,
420 if this function receives a nonlocal goto. */
421 && (! current_function_has_nonlocal_label
422 || REG_N_CALLS_CROSSED (i) == 0))
424 if (reg_renumber[i] < 0 && reg_may_share[i] && reg_allocno[reg_may_share[i]] >= 0)
425 reg_allocno[i] = reg_allocno[reg_may_share[i]];
426 else
427 reg_allocno[i] = max_allocno++;
428 if (REG_LIVE_LENGTH (i) == 0)
429 abort ();
431 else
432 reg_allocno[i] = -1;
434 allocno = (struct allocno *) xcalloc (max_allocno, sizeof (struct allocno));
436 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
437 if (reg_allocno[i] >= 0)
439 int num = reg_allocno[i];
440 allocno[num].reg = i;
441 allocno[num].size = PSEUDO_REGNO_SIZE (i);
442 allocno[num].calls_crossed += REG_N_CALLS_CROSSED (i);
443 allocno[num].n_refs += REG_N_REFS (i);
444 allocno[num].freq += REG_FREQ (i);
445 if (allocno[num].live_length < REG_LIVE_LENGTH (i))
446 allocno[num].live_length = REG_LIVE_LENGTH (i);
449 /* Calculate amount of usage of each hard reg by pseudos
450 allocated by local-alloc. This is to see if we want to
451 override it. */
452 memset ((char *) local_reg_live_length, 0, sizeof local_reg_live_length);
453 memset ((char *) local_reg_n_refs, 0, sizeof local_reg_n_refs);
454 memset ((char *) local_reg_freq, 0, sizeof local_reg_freq);
455 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
456 if (reg_renumber[i] >= 0)
458 int regno = reg_renumber[i];
459 int endregno = regno + HARD_REGNO_NREGS (regno, PSEUDO_REGNO_MODE (i));
460 int j;
462 for (j = regno; j < endregno; j++)
464 local_reg_n_refs[j] += REG_N_REFS (i);
465 local_reg_freq[j] += REG_FREQ (i);
466 local_reg_live_length[j] += REG_LIVE_LENGTH (i);
470 /* We can't override local-alloc for a reg used not just by local-alloc. */
471 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
472 if (regs_ever_live[i])
473 local_reg_n_refs[i] = 0, local_reg_freq[i] = 0;
475 allocno_row_words = (max_allocno + INT_BITS - 1) / INT_BITS;
477 /* We used to use alloca here, but the size of what it would try to
478 allocate would occasionally cause it to exceed the stack limit and
479 cause unpredictable core dumps. Some examples were > 2Mb in size. */
480 conflicts = (INT_TYPE *) xcalloc (max_allocno * allocno_row_words,
481 sizeof (INT_TYPE));
483 allocnos_live = (INT_TYPE *) xmalloc (allocno_row_words * sizeof (INT_TYPE));
485 /* If there is work to be done (at least one reg to allocate),
486 perform global conflict analysis and allocate the regs. */
488 if (max_allocno > 0)
490 /* Scan all the insns and compute the conflicts among allocnos
491 and between allocnos and hard regs. */
493 global_conflicts ();
495 mirror_conflicts ();
497 /* Eliminate conflicts between pseudos and eliminable registers. If
498 the register is not eliminated, the pseudo won't really be able to
499 live in the eliminable register, so the conflict doesn't matter.
500 If we do eliminate the register, the conflict will no longer exist.
501 So in either case, we can ignore the conflict. Likewise for
502 preferences. */
504 for (i = 0; i < (size_t) max_allocno; i++)
506 AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_conflicts,
507 eliminable_regset);
508 AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_copy_preferences,
509 eliminable_regset);
510 AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_preferences,
511 eliminable_regset);
514 /* Try to expand the preferences by merging them between allocnos. */
516 expand_preferences ();
518 /* Determine the order to allocate the remaining pseudo registers. */
520 allocno_order = (int *) xmalloc (max_allocno * sizeof (int));
521 for (i = 0; i < (size_t) max_allocno; i++)
522 allocno_order[i] = i;
524 /* Default the size to 1, since allocno_compare uses it to divide by.
525 Also convert allocno_live_length of zero to -1. A length of zero
526 can occur when all the registers for that allocno have reg_live_length
527 equal to -2. In this case, we want to make an allocno, but not
528 allocate it. So avoid the divide-by-zero and set it to a low
529 priority. */
531 for (i = 0; i < (size_t) max_allocno; i++)
533 if (allocno[i].size == 0)
534 allocno[i].size = 1;
535 if (allocno[i].live_length == 0)
536 allocno[i].live_length = -1;
539 qsort (allocno_order, max_allocno, sizeof (int), allocno_compare);
541 prune_preferences ();
543 if (file)
544 dump_conflicts (file);
546 /* Try allocating them, one by one, in that order,
547 except for parameters marked with reg_live_length[regno] == -2. */
549 for (i = 0; i < (size_t) max_allocno; i++)
550 if (reg_renumber[allocno[allocno_order[i]].reg] < 0
551 && REG_LIVE_LENGTH (allocno[allocno_order[i]].reg) >= 0)
553 /* If we have more than one register class,
554 first try allocating in the class that is cheapest
555 for this pseudo-reg. If that fails, try any reg. */
556 if (N_REG_CLASSES > 1)
558 find_reg (allocno_order[i], 0, 0, 0, 0);
559 if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
560 continue;
562 if (reg_alternate_class (allocno[allocno_order[i]].reg) != NO_REGS)
563 find_reg (allocno_order[i], 0, 1, 0, 0);
566 free (allocno_order);
569 /* Do the reloads now while the allocno data still exist, so that we can
570 try to assign new hard regs to any pseudo regs that are spilled. */
572 #if 0 /* We need to eliminate regs even if there is no rtl code,
573 for the sake of debugging information. */
574 if (n_basic_blocks > 0)
575 #endif
577 build_insn_chain (get_insns ());
578 retval = reload (get_insns (), 1);
581 /* Clean up. */
582 free (reg_allocno);
583 free (reg_may_share);
584 free (allocno);
585 free (conflicts);
586 free (allocnos_live);
588 return retval;
591 /* Sort predicate for ordering the allocnos.
592 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
594 static int
595 allocno_compare (v1p, v2p)
596 const PTR v1p;
597 const PTR v2p;
599 int v1 = *(const int *)v1p, v2 = *(const int *)v2p;
600 /* Note that the quotient will never be bigger than
601 the value of floor_log2 times the maximum number of
602 times a register can occur in one insn (surely less than 100)
603 weighted by the frequency (maximally REG_FREQ_MAX).
604 Multiplying this by 10000/REG_FREQ_MAX can't overflow. */
605 int pri1
606 = (((double) (floor_log2 (allocno[v1].n_refs) * allocno[v1].freq)
607 / allocno[v1].live_length)
608 * (10000 / REG_FREQ_MAX) * allocno[v1].size);
609 int pri2
610 = (((double) (floor_log2 (allocno[v2].n_refs) * allocno[v2].freq)
611 / allocno[v2].live_length)
612 * (10000 / REG_FREQ_MAX) * allocno[v2].size);
613 if (pri2 - pri1)
614 return pri2 - pri1;
616 /* If regs are equally good, sort by allocno,
617 so that the results of qsort leave nothing to chance. */
618 return v1 - v2;
621 /* Scan the rtl code and record all conflicts and register preferences in the
622 conflict matrices and preference tables. */
624 static void
625 global_conflicts ()
627 int i;
628 basic_block b;
629 rtx insn;
630 int *block_start_allocnos;
632 /* Make a vector that mark_reg_{store,clobber} will store in. */
633 regs_set = (rtx *) xmalloc (max_parallel * sizeof (rtx) * 2);
635 block_start_allocnos = (int *) xmalloc (max_allocno * sizeof (int));
637 FOR_EACH_BB (b)
639 memset ((char *) allocnos_live, 0, allocno_row_words * sizeof (INT_TYPE));
641 /* Initialize table of registers currently live
642 to the state at the beginning of this basic block.
643 This also marks the conflicts among hard registers
644 and any allocnos that are live.
646 For pseudo-regs, there is only one bit for each one
647 no matter how many hard regs it occupies.
648 This is ok; we know the size from PSEUDO_REGNO_SIZE.
649 For explicit hard regs, we cannot know the size that way
650 since one hard reg can be used with various sizes.
651 Therefore, we must require that all the hard regs
652 implicitly live as part of a multi-word hard reg
653 are explicitly marked in basic_block_live_at_start. */
656 regset old = b->global_live_at_start;
657 int ax = 0;
659 REG_SET_TO_HARD_REG_SET (hard_regs_live, old);
660 EXECUTE_IF_SET_IN_REG_SET (old, FIRST_PSEUDO_REGISTER, i,
662 int a = reg_allocno[i];
663 if (a >= 0)
665 SET_ALLOCNO_LIVE (a);
666 block_start_allocnos[ax++] = a;
668 else if ((a = reg_renumber[i]) >= 0)
669 mark_reg_live_nc
670 (a, PSEUDO_REGNO_MODE (i));
673 /* Record that each allocno now live conflicts with each hard reg
674 now live.
676 It is not necessary to mark any conflicts between pseudos as
677 this point, even for pseudos which are live at the start of
678 the basic block.
680 Given two pseudos X and Y and any point in the CFG P.
682 On any path to point P where X and Y are live one of the
683 following conditions must be true:
685 1. X is live at some instruction on the path that
686 evaluates Y.
688 2. Y is live at some instruction on the path that
689 evaluates X.
691 3. Either X or Y is not evaluted on the path to P
692 (ie it is used uninitialized) and thus the
693 conflict can be ignored.
695 In cases #1 and #2 the conflict will be recorded when we
696 scan the instruction that makes either X or Y become live. */
697 record_conflicts (block_start_allocnos, ax);
699 #ifdef STACK_REGS
701 /* Pseudos can't go in stack regs at the start of a basic block
702 that is reached by an abnormal edge. */
704 edge e;
705 for (e = b->pred; e ; e = e->pred_next)
706 if (e->flags & EDGE_ABNORMAL)
707 break;
708 if (e != NULL)
709 for (ax = FIRST_STACK_REG; ax <= LAST_STACK_REG; ax++)
710 record_one_conflict (ax);
712 #endif
715 insn = b->head;
717 /* Scan the code of this basic block, noting which allocnos
718 and hard regs are born or die. When one is born,
719 record a conflict with all others currently live. */
721 while (1)
723 RTX_CODE code = GET_CODE (insn);
724 rtx link;
726 /* Make regs_set an empty set. */
728 n_regs_set = 0;
730 if (code == INSN || code == CALL_INSN || code == JUMP_INSN)
733 #if 0
734 int i = 0;
735 for (link = REG_NOTES (insn);
736 link && i < NUM_NO_CONFLICT_PAIRS;
737 link = XEXP (link, 1))
738 if (REG_NOTE_KIND (link) == REG_NO_CONFLICT)
740 no_conflict_pairs[i].allocno1
741 = reg_allocno[REGNO (SET_DEST (PATTERN (insn)))];
742 no_conflict_pairs[i].allocno2
743 = reg_allocno[REGNO (XEXP (link, 0))];
744 i++;
746 #endif /* 0 */
748 /* Mark any registers clobbered by INSN as live,
749 so they conflict with the inputs. */
751 note_stores (PATTERN (insn), mark_reg_clobber, NULL);
753 /* Mark any registers dead after INSN as dead now. */
755 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
756 if (REG_NOTE_KIND (link) == REG_DEAD)
757 mark_reg_death (XEXP (link, 0));
759 /* Mark any registers set in INSN as live,
760 and mark them as conflicting with all other live regs.
761 Clobbers are processed again, so they conflict with
762 the registers that are set. */
764 note_stores (PATTERN (insn), mark_reg_store, NULL);
766 #ifdef AUTO_INC_DEC
767 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
768 if (REG_NOTE_KIND (link) == REG_INC)
769 mark_reg_store (XEXP (link, 0), NULL_RTX, NULL);
770 #endif
772 /* If INSN has multiple outputs, then any reg that dies here
773 and is used inside of an output
774 must conflict with the other outputs.
776 It is unsafe to use !single_set here since it will ignore an
777 unused output. Just because an output is unused does not mean
778 the compiler can assume the side effect will not occur.
779 Consider if REG appears in the address of an output and we
780 reload the output. If we allocate REG to the same hard
781 register as an unused output we could set the hard register
782 before the output reload insn. */
783 if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn))
784 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
785 if (REG_NOTE_KIND (link) == REG_DEAD)
787 int used_in_output = 0;
788 int i;
789 rtx reg = XEXP (link, 0);
791 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
793 rtx set = XVECEXP (PATTERN (insn), 0, i);
794 if (GET_CODE (set) == SET
795 && GET_CODE (SET_DEST (set)) != REG
796 && !rtx_equal_p (reg, SET_DEST (set))
797 && reg_overlap_mentioned_p (reg, SET_DEST (set)))
798 used_in_output = 1;
800 if (used_in_output)
801 mark_reg_conflicts (reg);
804 /* Mark any registers set in INSN and then never used. */
806 while (n_regs_set-- > 0)
808 rtx note = find_regno_note (insn, REG_UNUSED,
809 REGNO (regs_set[n_regs_set]));
810 if (note)
811 mark_reg_death (XEXP (note, 0));
815 if (insn == b->end)
816 break;
817 insn = NEXT_INSN (insn);
821 /* Clean up. */
822 free (block_start_allocnos);
823 free (regs_set);
825 /* Expand the preference information by looking for cases where one allocno
826 dies in an insn that sets an allocno. If those two allocnos don't conflict,
827 merge any preferences between those allocnos. */
829 static void
830 expand_preferences ()
832 rtx insn;
833 rtx link;
834 rtx set;
836 /* We only try to handle the most common cases here. Most of the cases
837 where this wins are reg-reg copies. */
839 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
840 if (INSN_P (insn)
841 && (set = single_set (insn)) != 0
842 && GET_CODE (SET_DEST (set)) == REG
843 && reg_allocno[REGNO (SET_DEST (set))] >= 0)
844 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
845 if (REG_NOTE_KIND (link) == REG_DEAD
846 && GET_CODE (XEXP (link, 0)) == REG
847 && reg_allocno[REGNO (XEXP (link, 0))] >= 0
848 && ! CONFLICTP (reg_allocno[REGNO (SET_DEST (set))],
849 reg_allocno[REGNO (XEXP (link, 0))]))
851 int a1 = reg_allocno[REGNO (SET_DEST (set))];
852 int a2 = reg_allocno[REGNO (XEXP (link, 0))];
854 if (XEXP (link, 0) == SET_SRC (set))
856 IOR_HARD_REG_SET (allocno[a1].hard_reg_copy_preferences,
857 allocno[a2].hard_reg_copy_preferences);
858 IOR_HARD_REG_SET (allocno[a2].hard_reg_copy_preferences,
859 allocno[a1].hard_reg_copy_preferences);
862 IOR_HARD_REG_SET (allocno[a1].hard_reg_preferences,
863 allocno[a2].hard_reg_preferences);
864 IOR_HARD_REG_SET (allocno[a2].hard_reg_preferences,
865 allocno[a1].hard_reg_preferences);
866 IOR_HARD_REG_SET (allocno[a1].hard_reg_full_preferences,
867 allocno[a2].hard_reg_full_preferences);
868 IOR_HARD_REG_SET (allocno[a2].hard_reg_full_preferences,
869 allocno[a1].hard_reg_full_preferences);
873 /* Prune the preferences for global registers to exclude registers that cannot
874 be used.
876 Compute `regs_someone_prefers', which is a bitmask of the hard registers
877 that are preferred by conflicting registers of lower priority. If possible,
878 we will avoid using these registers. */
880 static void
881 prune_preferences ()
883 int i;
884 int num;
885 int *allocno_to_order = (int *) xmalloc (max_allocno * sizeof (int));
887 /* Scan least most important to most important.
888 For each allocno, remove from preferences registers that cannot be used,
889 either because of conflicts or register type. Then compute all registers
890 preferred by each lower-priority register that conflicts. */
892 for (i = max_allocno - 1; i >= 0; i--)
894 HARD_REG_SET temp;
896 num = allocno_order[i];
897 allocno_to_order[num] = i;
898 COPY_HARD_REG_SET (temp, allocno[num].hard_reg_conflicts);
900 if (allocno[num].calls_crossed == 0)
901 IOR_HARD_REG_SET (temp, fixed_reg_set);
902 else
903 IOR_HARD_REG_SET (temp, call_used_reg_set);
905 IOR_COMPL_HARD_REG_SET
906 (temp,
907 reg_class_contents[(int) reg_preferred_class (allocno[num].reg)]);
909 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_preferences, temp);
910 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_copy_preferences, temp);
911 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_full_preferences, temp);
914 for (i = max_allocno - 1; i >= 0; i--)
916 /* Merge in the preferences of lower-priority registers (they have
917 already been pruned). If we also prefer some of those registers,
918 don't exclude them unless we are of a smaller size (in which case
919 we want to give the lower-priority allocno the first chance for
920 these registers). */
921 HARD_REG_SET temp, temp2;
922 int allocno2;
924 num = allocno_order[i];
926 CLEAR_HARD_REG_SET (temp);
927 CLEAR_HARD_REG_SET (temp2);
929 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + num * allocno_row_words,
930 allocno2,
932 if (allocno_to_order[allocno2] > i)
934 if (allocno[allocno2].size <= allocno[num].size)
935 IOR_HARD_REG_SET (temp,
936 allocno[allocno2].hard_reg_full_preferences);
937 else
938 IOR_HARD_REG_SET (temp2,
939 allocno[allocno2].hard_reg_full_preferences);
943 AND_COMPL_HARD_REG_SET (temp, allocno[num].hard_reg_full_preferences);
944 IOR_HARD_REG_SET (temp, temp2);
945 COPY_HARD_REG_SET (allocno[num].regs_someone_prefers, temp);
947 free (allocno_to_order);
950 /* Assign a hard register to allocno NUM; look for one that is the beginning
951 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
952 The registers marked in PREFREGS are tried first.
954 LOSERS, if non-zero, is a HARD_REG_SET indicating registers that cannot
955 be used for this allocation.
957 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
958 Otherwise ignore that preferred class and use the alternate class.
960 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
961 will have to be saved and restored at calls.
963 RETRYING is nonzero if this is called from retry_global_alloc.
965 If we find one, record it in reg_renumber.
966 If not, do nothing. */
968 static void
969 find_reg (num, losers, alt_regs_p, accept_call_clobbered, retrying)
970 int num;
971 HARD_REG_SET losers;
972 int alt_regs_p;
973 int accept_call_clobbered;
974 int retrying;
976 int i, best_reg, pass;
977 #ifdef HARD_REG_SET
978 register /* Declare it register if it's a scalar. */
979 #endif
980 HARD_REG_SET used, used1, used2;
982 enum reg_class class = (alt_regs_p
983 ? reg_alternate_class (allocno[num].reg)
984 : reg_preferred_class (allocno[num].reg));
985 enum machine_mode mode = PSEUDO_REGNO_MODE (allocno[num].reg);
987 if (accept_call_clobbered)
988 COPY_HARD_REG_SET (used1, call_fixed_reg_set);
989 else if (allocno[num].calls_crossed == 0)
990 COPY_HARD_REG_SET (used1, fixed_reg_set);
991 else
992 COPY_HARD_REG_SET (used1, call_used_reg_set);
994 /* Some registers should not be allocated in global-alloc. */
995 IOR_HARD_REG_SET (used1, no_global_alloc_regs);
996 if (losers)
997 IOR_HARD_REG_SET (used1, losers);
999 IOR_COMPL_HARD_REG_SET (used1, reg_class_contents[(int) class]);
1000 COPY_HARD_REG_SET (used2, used1);
1002 IOR_HARD_REG_SET (used1, allocno[num].hard_reg_conflicts);
1004 #ifdef CLASS_CANNOT_CHANGE_MODE
1005 if (REG_CHANGES_MODE (allocno[num].reg))
1006 IOR_HARD_REG_SET (used1,
1007 reg_class_contents[(int) CLASS_CANNOT_CHANGE_MODE]);
1008 #endif
1010 /* Try each hard reg to see if it fits. Do this in two passes.
1011 In the first pass, skip registers that are preferred by some other pseudo
1012 to give it a better chance of getting one of those registers. Only if
1013 we can't get a register when excluding those do we take one of them.
1014 However, we never allocate a register for the first time in pass 0. */
1016 COPY_HARD_REG_SET (used, used1);
1017 IOR_COMPL_HARD_REG_SET (used, regs_used_so_far);
1018 IOR_HARD_REG_SET (used, allocno[num].regs_someone_prefers);
1020 best_reg = -1;
1021 for (i = FIRST_PSEUDO_REGISTER, pass = 0;
1022 pass <= 1 && i >= FIRST_PSEUDO_REGISTER;
1023 pass++)
1025 if (pass == 1)
1026 COPY_HARD_REG_SET (used, used1);
1027 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1029 #ifdef REG_ALLOC_ORDER
1030 int regno = reg_alloc_order[i];
1031 #else
1032 int regno = i;
1033 #endif
1034 if (! TEST_HARD_REG_BIT (used, regno)
1035 && HARD_REGNO_MODE_OK (regno, mode)
1036 && (allocno[num].calls_crossed == 0
1037 || accept_call_clobbered
1038 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
1040 int j;
1041 int lim = regno + HARD_REGNO_NREGS (regno, mode);
1042 for (j = regno + 1;
1043 (j < lim
1044 && ! TEST_HARD_REG_BIT (used, j));
1045 j++);
1046 if (j == lim)
1048 best_reg = regno;
1049 break;
1051 #ifndef REG_ALLOC_ORDER
1052 i = j; /* Skip starting points we know will lose */
1053 #endif
1058 /* See if there is a preferred register with the same class as the register
1059 we allocated above. Making this restriction prevents register
1060 preferencing from creating worse register allocation.
1062 Remove from the preferred registers and conflicting registers. Note that
1063 additional conflicts may have been added after `prune_preferences' was
1064 called.
1066 First do this for those register with copy preferences, then all
1067 preferred registers. */
1069 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_copy_preferences, used);
1070 GO_IF_HARD_REG_SUBSET (allocno[num].hard_reg_copy_preferences,
1071 reg_class_contents[(int) NO_REGS], no_copy_prefs);
1073 if (best_reg >= 0)
1075 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1076 if (TEST_HARD_REG_BIT (allocno[num].hard_reg_copy_preferences, i)
1077 && HARD_REGNO_MODE_OK (i, mode)
1078 && (allocno[num].calls_crossed == 0
1079 || accept_call_clobbered
1080 || ! HARD_REGNO_CALL_PART_CLOBBERED (i, mode))
1081 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1082 || reg_class_subset_p (REGNO_REG_CLASS (i),
1083 REGNO_REG_CLASS (best_reg))
1084 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1085 REGNO_REG_CLASS (i))))
1087 int j;
1088 int lim = i + HARD_REGNO_NREGS (i, mode);
1089 for (j = i + 1;
1090 (j < lim
1091 && ! TEST_HARD_REG_BIT (used, j)
1092 && (REGNO_REG_CLASS (j)
1093 == REGNO_REG_CLASS (best_reg + (j - i))
1094 || reg_class_subset_p (REGNO_REG_CLASS (j),
1095 REGNO_REG_CLASS (best_reg + (j - i)))
1096 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1097 REGNO_REG_CLASS (j))));
1098 j++);
1099 if (j == lim)
1101 best_reg = i;
1102 goto no_prefs;
1106 no_copy_prefs:
1108 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_preferences, used);
1109 GO_IF_HARD_REG_SUBSET (allocno[num].hard_reg_preferences,
1110 reg_class_contents[(int) NO_REGS], no_prefs);
1112 if (best_reg >= 0)
1114 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1115 if (TEST_HARD_REG_BIT (allocno[num].hard_reg_preferences, i)
1116 && HARD_REGNO_MODE_OK (i, mode)
1117 && (allocno[num].calls_crossed == 0
1118 || accept_call_clobbered
1119 || ! HARD_REGNO_CALL_PART_CLOBBERED (i, mode))
1120 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1121 || reg_class_subset_p (REGNO_REG_CLASS (i),
1122 REGNO_REG_CLASS (best_reg))
1123 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1124 REGNO_REG_CLASS (i))))
1126 int j;
1127 int lim = i + HARD_REGNO_NREGS (i, mode);
1128 for (j = i + 1;
1129 (j < lim
1130 && ! TEST_HARD_REG_BIT (used, j)
1131 && (REGNO_REG_CLASS (j)
1132 == REGNO_REG_CLASS (best_reg + (j - i))
1133 || reg_class_subset_p (REGNO_REG_CLASS (j),
1134 REGNO_REG_CLASS (best_reg + (j - i)))
1135 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1136 REGNO_REG_CLASS (j))));
1137 j++);
1138 if (j == lim)
1140 best_reg = i;
1141 break;
1145 no_prefs:
1147 /* If we haven't succeeded yet, try with caller-saves.
1148 We need not check to see if the current function has nonlocal
1149 labels because we don't put any pseudos that are live over calls in
1150 registers in that case. */
1152 if (flag_caller_saves && best_reg < 0)
1154 /* Did not find a register. If it would be profitable to
1155 allocate a call-clobbered register and save and restore it
1156 around calls, do that. */
1157 if (! accept_call_clobbered
1158 && allocno[num].calls_crossed != 0
1159 && CALLER_SAVE_PROFITABLE (allocno[num].n_refs,
1160 allocno[num].calls_crossed))
1162 HARD_REG_SET new_losers;
1163 if (! losers)
1164 CLEAR_HARD_REG_SET (new_losers);
1165 else
1166 COPY_HARD_REG_SET (new_losers, losers);
1168 IOR_HARD_REG_SET(new_losers, losing_caller_save_reg_set);
1169 find_reg (num, new_losers, alt_regs_p, 1, retrying);
1170 if (reg_renumber[allocno[num].reg] >= 0)
1172 caller_save_needed = 1;
1173 return;
1178 /* If we haven't succeeded yet,
1179 see if some hard reg that conflicts with us
1180 was utilized poorly by local-alloc.
1181 If so, kick out the regs that were put there by local-alloc
1182 so we can use it instead. */
1183 if (best_reg < 0 && !retrying
1184 /* Let's not bother with multi-reg allocnos. */
1185 && allocno[num].size == 1)
1187 /* Count from the end, to find the least-used ones first. */
1188 for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1190 #ifdef REG_ALLOC_ORDER
1191 int regno = reg_alloc_order[i];
1192 #else
1193 int regno = i;
1194 #endif
1196 if (local_reg_n_refs[regno] != 0
1197 /* Don't use a reg no good for this pseudo. */
1198 && ! TEST_HARD_REG_BIT (used2, regno)
1199 && HARD_REGNO_MODE_OK (regno, mode)
1200 && (allocno[num].calls_crossed == 0
1201 || accept_call_clobbered
1202 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode))
1203 #ifdef CLASS_CANNOT_CHANGE_MODE
1204 && ! (REG_CHANGES_MODE (allocno[num].reg)
1205 && (TEST_HARD_REG_BIT
1206 (reg_class_contents[(int) CLASS_CANNOT_CHANGE_MODE],
1207 regno)))
1208 #endif
1211 /* We explicitly evaluate the divide results into temporary
1212 variables so as to avoid excess precision problems that occur
1213 on an i386-unknown-sysv4.2 (unixware) host. */
1215 double tmp1 = ((double) local_reg_freq[regno]
1216 / local_reg_live_length[regno]);
1217 double tmp2 = ((double) allocno[num].freq
1218 / allocno[num].live_length);
1220 if (tmp1 < tmp2)
1222 /* Hard reg REGNO was used less in total by local regs
1223 than it would be used by this one allocno! */
1224 int k;
1225 for (k = 0; k < max_regno; k++)
1226 if (reg_renumber[k] >= 0)
1228 int r = reg_renumber[k];
1229 int endregno
1230 = r + HARD_REGNO_NREGS (r, PSEUDO_REGNO_MODE (k));
1232 if (regno >= r && regno < endregno)
1233 reg_renumber[k] = -1;
1236 best_reg = regno;
1237 break;
1243 /* Did we find a register? */
1245 if (best_reg >= 0)
1247 int lim, j;
1248 HARD_REG_SET this_reg;
1250 /* Yes. Record it as the hard register of this pseudo-reg. */
1251 reg_renumber[allocno[num].reg] = best_reg;
1252 /* Also of any pseudo-regs that share with it. */
1253 if (reg_may_share[allocno[num].reg])
1254 for (j = FIRST_PSEUDO_REGISTER; j < max_regno; j++)
1255 if (reg_allocno[j] == num)
1256 reg_renumber[j] = best_reg;
1258 /* Make a set of the hard regs being allocated. */
1259 CLEAR_HARD_REG_SET (this_reg);
1260 lim = best_reg + HARD_REGNO_NREGS (best_reg, mode);
1261 for (j = best_reg; j < lim; j++)
1263 SET_HARD_REG_BIT (this_reg, j);
1264 SET_HARD_REG_BIT (regs_used_so_far, j);
1265 /* This is no longer a reg used just by local regs. */
1266 local_reg_n_refs[j] = 0;
1267 local_reg_freq[j] = 0;
1269 /* For each other pseudo-reg conflicting with this one,
1270 mark it as conflicting with the hard regs this one occupies. */
1271 lim = num;
1272 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + lim * allocno_row_words, j,
1274 IOR_HARD_REG_SET (allocno[j].hard_reg_conflicts, this_reg);
1279 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1280 Perhaps it had previously seemed not worth a hard reg,
1281 or perhaps its old hard reg has been commandeered for reloads.
1282 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1283 they do not appear to be allocated.
1284 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1286 void
1287 retry_global_alloc (regno, forbidden_regs)
1288 int regno;
1289 HARD_REG_SET forbidden_regs;
1291 int alloc_no = reg_allocno[regno];
1292 if (alloc_no >= 0)
1294 /* If we have more than one register class,
1295 first try allocating in the class that is cheapest
1296 for this pseudo-reg. If that fails, try any reg. */
1297 if (N_REG_CLASSES > 1)
1298 find_reg (alloc_no, forbidden_regs, 0, 0, 1);
1299 if (reg_renumber[regno] < 0
1300 && reg_alternate_class (regno) != NO_REGS)
1301 find_reg (alloc_no, forbidden_regs, 1, 0, 1);
1303 /* If we found a register, modify the RTL for the register to
1304 show the hard register, and mark that register live. */
1305 if (reg_renumber[regno] >= 0)
1307 REGNO (regno_reg_rtx[regno]) = reg_renumber[regno];
1308 mark_home_live (regno);
1313 /* Record a conflict between register REGNO
1314 and everything currently live.
1315 REGNO must not be a pseudo reg that was allocated
1316 by local_alloc; such numbers must be translated through
1317 reg_renumber before calling here. */
1319 static void
1320 record_one_conflict (regno)
1321 int regno;
1323 int j;
1325 if (regno < FIRST_PSEUDO_REGISTER)
1326 /* When a hard register becomes live,
1327 record conflicts with live pseudo regs. */
1328 EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live, j,
1330 SET_HARD_REG_BIT (allocno[j].hard_reg_conflicts, regno);
1332 else
1333 /* When a pseudo-register becomes live,
1334 record conflicts first with hard regs,
1335 then with other pseudo regs. */
1337 int ialloc = reg_allocno[regno];
1338 int ialloc_prod = ialloc * allocno_row_words;
1340 IOR_HARD_REG_SET (allocno[ialloc].hard_reg_conflicts, hard_regs_live);
1341 for (j = allocno_row_words - 1; j >= 0; j--)
1343 #if 0
1344 int k;
1345 for (k = 0; k < n_no_conflict_pairs; k++)
1346 if (! ((j == no_conflict_pairs[k].allocno1
1347 && ialloc == no_conflict_pairs[k].allocno2)
1349 (j == no_conflict_pairs[k].allocno2
1350 && ialloc == no_conflict_pairs[k].allocno1)))
1351 #endif /* 0 */
1352 conflicts[ialloc_prod + j] |= allocnos_live[j];
1357 /* Record all allocnos currently live as conflicting
1358 with all hard regs currently live.
1360 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1361 are currently live. Their bits are also flagged in allocnos_live. */
1363 static void
1364 record_conflicts (allocno_vec, len)
1365 int *allocno_vec;
1366 int len;
1368 int num;
1369 int ialloc_prod;
1371 while (--len >= 0)
1373 num = allocno_vec[len];
1374 ialloc_prod = num * allocno_row_words;
1375 IOR_HARD_REG_SET (allocno[num].hard_reg_conflicts, hard_regs_live);
1379 /* If CONFLICTP (i, j) is true, make sure CONFLICTP (j, i) is also true. */
1380 static void
1381 mirror_conflicts ()
1383 int i, j;
1384 int rw = allocno_row_words;
1385 int rwb = rw * INT_BITS;
1386 INT_TYPE *p = conflicts;
1387 INT_TYPE *q0 = conflicts, *q1, *q2;
1388 unsigned INT_TYPE mask;
1390 for (i = max_allocno - 1, mask = 1; i >= 0; i--, mask <<= 1)
1392 if (! mask)
1394 mask = 1;
1395 q0++;
1397 for (j = allocno_row_words - 1, q1 = q0; j >= 0; j--, q1 += rwb)
1399 unsigned INT_TYPE word;
1401 for (word = (unsigned INT_TYPE) *p++, q2 = q1; word;
1402 word >>= 1, q2 += rw)
1404 if (word & 1)
1405 *q2 |= mask;
1411 /* Handle the case where REG is set by the insn being scanned,
1412 during the forward scan to accumulate conflicts.
1413 Store a 1 in regs_live or allocnos_live for this register, record how many
1414 consecutive hardware registers it actually needs,
1415 and record a conflict with all other registers already live.
1417 Note that even if REG does not remain alive after this insn,
1418 we must mark it here as live, to ensure a conflict between
1419 REG and any other regs set in this insn that really do live.
1420 This is because those other regs could be considered after this.
1422 REG might actually be something other than a register;
1423 if so, we do nothing.
1425 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1426 a REG_INC note was found for it). */
1428 static void
1429 mark_reg_store (reg, setter, data)
1430 rtx reg, setter;
1431 void *data ATTRIBUTE_UNUSED;
1433 int regno;
1435 if (GET_CODE (reg) == SUBREG)
1436 reg = SUBREG_REG (reg);
1438 if (GET_CODE (reg) != REG)
1439 return;
1441 regs_set[n_regs_set++] = reg;
1443 if (setter && GET_CODE (setter) != CLOBBER)
1444 set_preference (reg, SET_SRC (setter));
1446 regno = REGNO (reg);
1448 /* Either this is one of the max_allocno pseudo regs not allocated,
1449 or it is or has a hardware reg. First handle the pseudo-regs. */
1450 if (regno >= FIRST_PSEUDO_REGISTER)
1452 if (reg_allocno[regno] >= 0)
1454 SET_ALLOCNO_LIVE (reg_allocno[regno]);
1455 record_one_conflict (regno);
1459 if (reg_renumber[regno] >= 0)
1460 regno = reg_renumber[regno];
1462 /* Handle hardware regs (and pseudos allocated to hard regs). */
1463 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1465 int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1466 while (regno < last)
1468 record_one_conflict (regno);
1469 SET_HARD_REG_BIT (hard_regs_live, regno);
1470 regno++;
1475 /* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
1477 static void
1478 mark_reg_clobber (reg, setter, data)
1479 rtx reg, setter;
1480 void *data ATTRIBUTE_UNUSED;
1482 if (GET_CODE (setter) == CLOBBER)
1483 mark_reg_store (reg, setter, data);
1486 /* Record that REG has conflicts with all the regs currently live.
1487 Do not mark REG itself as live. */
1489 static void
1490 mark_reg_conflicts (reg)
1491 rtx reg;
1493 int regno;
1495 if (GET_CODE (reg) == SUBREG)
1496 reg = SUBREG_REG (reg);
1498 if (GET_CODE (reg) != REG)
1499 return;
1501 regno = REGNO (reg);
1503 /* Either this is one of the max_allocno pseudo regs not allocated,
1504 or it is or has a hardware reg. First handle the pseudo-regs. */
1505 if (regno >= FIRST_PSEUDO_REGISTER)
1507 if (reg_allocno[regno] >= 0)
1508 record_one_conflict (regno);
1511 if (reg_renumber[regno] >= 0)
1512 regno = reg_renumber[regno];
1514 /* Handle hardware regs (and pseudos allocated to hard regs). */
1515 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1517 int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1518 while (regno < last)
1520 record_one_conflict (regno);
1521 regno++;
1526 /* Mark REG as being dead (following the insn being scanned now).
1527 Store a 0 in regs_live or allocnos_live for this register. */
1529 static void
1530 mark_reg_death (reg)
1531 rtx reg;
1533 int regno = REGNO (reg);
1535 /* Either this is one of the max_allocno pseudo regs not allocated,
1536 or it is a hardware reg. First handle the pseudo-regs. */
1537 if (regno >= FIRST_PSEUDO_REGISTER)
1539 if (reg_allocno[regno] >= 0)
1540 CLEAR_ALLOCNO_LIVE (reg_allocno[regno]);
1543 /* For pseudo reg, see if it has been assigned a hardware reg. */
1544 if (reg_renumber[regno] >= 0)
1545 regno = reg_renumber[regno];
1547 /* Handle hardware regs (and pseudos allocated to hard regs). */
1548 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1550 /* Pseudo regs already assigned hardware regs are treated
1551 almost the same as explicit hardware regs. */
1552 int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1553 while (regno < last)
1555 CLEAR_HARD_REG_BIT (hard_regs_live, regno);
1556 regno++;
1561 /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1562 for the value stored in it. MODE determines how many consecutive
1563 registers are actually in use. Do not record conflicts;
1564 it is assumed that the caller will do that. */
1566 static void
1567 mark_reg_live_nc (regno, mode)
1568 int regno;
1569 enum machine_mode mode;
1571 int last = regno + HARD_REGNO_NREGS (regno, mode);
1572 while (regno < last)
1574 SET_HARD_REG_BIT (hard_regs_live, regno);
1575 regno++;
1579 /* Try to set a preference for an allocno to a hard register.
1580 We are passed DEST and SRC which are the operands of a SET. It is known
1581 that SRC is a register. If SRC or the first operand of SRC is a register,
1582 try to set a preference. If one of the two is a hard register and the other
1583 is a pseudo-register, mark the preference.
1585 Note that we are not as aggressive as local-alloc in trying to tie a
1586 pseudo-register to a hard register. */
1588 static void
1589 set_preference (dest, src)
1590 rtx dest, src;
1592 unsigned int src_regno, dest_regno;
1593 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1594 to compensate for subregs in SRC or DEST. */
1595 int offset = 0;
1596 unsigned int i;
1597 int copy = 1;
1599 if (GET_RTX_FORMAT (GET_CODE (src))[0] == 'e')
1600 src = XEXP (src, 0), copy = 0;
1602 /* Get the reg number for both SRC and DEST.
1603 If neither is a reg, give up. */
1605 if (GET_CODE (src) == REG)
1606 src_regno = REGNO (src);
1607 else if (GET_CODE (src) == SUBREG && GET_CODE (SUBREG_REG (src)) == REG)
1609 src_regno = REGNO (SUBREG_REG (src));
1611 if (REGNO (SUBREG_REG (src)) < FIRST_PSEUDO_REGISTER)
1612 offset += subreg_regno_offset (REGNO (SUBREG_REG (src)),
1613 GET_MODE (SUBREG_REG (src)),
1614 SUBREG_BYTE (src),
1615 GET_MODE (src));
1616 else
1617 offset += (SUBREG_BYTE (src)
1618 / REGMODE_NATURAL_SIZE (GET_MODE (src)));
1620 else
1621 return;
1623 if (GET_CODE (dest) == REG)
1624 dest_regno = REGNO (dest);
1625 else if (GET_CODE (dest) == SUBREG && GET_CODE (SUBREG_REG (dest)) == REG)
1627 dest_regno = REGNO (SUBREG_REG (dest));
1629 if (REGNO (SUBREG_REG (dest)) < FIRST_PSEUDO_REGISTER)
1630 offset -= subreg_regno_offset (REGNO (SUBREG_REG (dest)),
1631 GET_MODE (SUBREG_REG (dest)),
1632 SUBREG_BYTE (dest),
1633 GET_MODE (dest));
1634 else
1635 offset -= (SUBREG_BYTE (dest)
1636 / REGMODE_NATURAL_SIZE (GET_MODE (dest)));
1638 else
1639 return;
1641 /* Convert either or both to hard reg numbers. */
1643 if (reg_renumber[src_regno] >= 0)
1644 src_regno = reg_renumber[src_regno];
1646 if (reg_renumber[dest_regno] >= 0)
1647 dest_regno = reg_renumber[dest_regno];
1649 /* Now if one is a hard reg and the other is a global pseudo
1650 then give the other a preference. */
1652 if (dest_regno < FIRST_PSEUDO_REGISTER && src_regno >= FIRST_PSEUDO_REGISTER
1653 && reg_allocno[src_regno] >= 0)
1655 dest_regno -= offset;
1656 if (dest_regno < FIRST_PSEUDO_REGISTER)
1658 if (copy)
1659 SET_REGBIT (hard_reg_copy_preferences,
1660 reg_allocno[src_regno], dest_regno);
1662 SET_REGBIT (hard_reg_preferences,
1663 reg_allocno[src_regno], dest_regno);
1664 for (i = dest_regno;
1665 i < dest_regno + HARD_REGNO_NREGS (dest_regno, GET_MODE (dest));
1666 i++)
1667 SET_REGBIT (hard_reg_full_preferences, reg_allocno[src_regno], i);
1671 if (src_regno < FIRST_PSEUDO_REGISTER && dest_regno >= FIRST_PSEUDO_REGISTER
1672 && reg_allocno[dest_regno] >= 0)
1674 src_regno += offset;
1675 if (src_regno < FIRST_PSEUDO_REGISTER)
1677 if (copy)
1678 SET_REGBIT (hard_reg_copy_preferences,
1679 reg_allocno[dest_regno], src_regno);
1681 SET_REGBIT (hard_reg_preferences,
1682 reg_allocno[dest_regno], src_regno);
1683 for (i = src_regno;
1684 i < src_regno + HARD_REGNO_NREGS (src_regno, GET_MODE (src));
1685 i++)
1686 SET_REGBIT (hard_reg_full_preferences, reg_allocno[dest_regno], i);
1691 /* Indicate that hard register number FROM was eliminated and replaced with
1692 an offset from hard register number TO. The status of hard registers live
1693 at the start of a basic block is updated by replacing a use of FROM with
1694 a use of TO. */
1696 void
1697 mark_elimination (from, to)
1698 int from, to;
1700 basic_block bb;
1702 FOR_EACH_BB (bb)
1704 regset r = bb->global_live_at_start;
1705 if (REGNO_REG_SET_P (r, from))
1707 CLEAR_REGNO_REG_SET (r, from);
1708 SET_REGNO_REG_SET (r, to);
1713 /* Used for communication between the following functions. Holds the
1714 current life information. */
1715 static regset live_relevant_regs;
1717 /* Record in live_relevant_regs and REGS_SET that register REG became live.
1718 This is called via note_stores. */
1719 static void
1720 reg_becomes_live (reg, setter, regs_set)
1721 rtx reg;
1722 rtx setter ATTRIBUTE_UNUSED;
1723 void *regs_set;
1725 int regno;
1727 if (GET_CODE (reg) == SUBREG)
1728 reg = SUBREG_REG (reg);
1730 if (GET_CODE (reg) != REG)
1731 return;
1733 regno = REGNO (reg);
1734 if (regno < FIRST_PSEUDO_REGISTER)
1736 int nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg));
1737 while (nregs-- > 0)
1739 SET_REGNO_REG_SET (live_relevant_regs, regno);
1740 if (! fixed_regs[regno])
1741 SET_REGNO_REG_SET ((regset) regs_set, regno);
1742 regno++;
1745 else if (reg_renumber[regno] >= 0)
1747 SET_REGNO_REG_SET (live_relevant_regs, regno);
1748 SET_REGNO_REG_SET ((regset) regs_set, regno);
1752 /* Record in live_relevant_regs that register REGNO died. */
1753 static void
1754 reg_dies (regno, mode, chain)
1755 int regno;
1756 enum machine_mode mode;
1757 struct insn_chain *chain;
1759 if (regno < FIRST_PSEUDO_REGISTER)
1761 int nregs = HARD_REGNO_NREGS (regno, mode);
1762 while (nregs-- > 0)
1764 CLEAR_REGNO_REG_SET (live_relevant_regs, regno);
1765 if (! fixed_regs[regno])
1766 SET_REGNO_REG_SET (&chain->dead_or_set, regno);
1767 regno++;
1770 else
1772 CLEAR_REGNO_REG_SET (live_relevant_regs, regno);
1773 if (reg_renumber[regno] >= 0)
1774 SET_REGNO_REG_SET (&chain->dead_or_set, regno);
1778 /* Walk the insns of the current function and build reload_insn_chain,
1779 and record register life information. */
1780 void
1781 build_insn_chain (first)
1782 rtx first;
1784 struct insn_chain **p = &reload_insn_chain;
1785 struct insn_chain *prev = 0;
1786 basic_block b = ENTRY_BLOCK_PTR->next_bb;
1787 regset_head live_relevant_regs_head;
1789 live_relevant_regs = INITIALIZE_REG_SET (live_relevant_regs_head);
1791 for (; first; first = NEXT_INSN (first))
1793 struct insn_chain *c;
1795 if (first == b->head)
1797 int i;
1799 CLEAR_REG_SET (live_relevant_regs);
1801 EXECUTE_IF_SET_IN_BITMAP
1802 (b->global_live_at_start, 0, i,
1804 if (i < FIRST_PSEUDO_REGISTER
1805 ? ! TEST_HARD_REG_BIT (eliminable_regset, i)
1806 : reg_renumber[i] >= 0)
1807 SET_REGNO_REG_SET (live_relevant_regs, i);
1811 if (GET_CODE (first) != NOTE && GET_CODE (first) != BARRIER)
1813 c = new_insn_chain ();
1814 c->prev = prev;
1815 prev = c;
1816 *p = c;
1817 p = &c->next;
1818 c->insn = first;
1819 c->block = b->index;
1821 if (INSN_P (first))
1823 rtx link;
1825 /* Mark the death of everything that dies in this instruction. */
1827 for (link = REG_NOTES (first); link; link = XEXP (link, 1))
1828 if (REG_NOTE_KIND (link) == REG_DEAD
1829 && GET_CODE (XEXP (link, 0)) == REG)
1830 reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)),
1833 COPY_REG_SET (&c->live_throughout, live_relevant_regs);
1835 /* Mark everything born in this instruction as live. */
1837 note_stores (PATTERN (first), reg_becomes_live,
1838 &c->dead_or_set);
1840 else
1841 COPY_REG_SET (&c->live_throughout, live_relevant_regs);
1843 if (INSN_P (first))
1845 rtx link;
1847 /* Mark anything that is set in this insn and then unused as dying. */
1849 for (link = REG_NOTES (first); link; link = XEXP (link, 1))
1850 if (REG_NOTE_KIND (link) == REG_UNUSED
1851 && GET_CODE (XEXP (link, 0)) == REG)
1852 reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)),
1857 if (first == b->end)
1858 b = b->next_bb;
1860 /* Stop after we pass the end of the last basic block. Verify that
1861 no real insns are after the end of the last basic block.
1863 We may want to reorganize the loop somewhat since this test should
1864 always be the right exit test. Allow an ADDR_VEC or ADDR_DIF_VEC if
1865 the previous real insn is a JUMP_INSN. */
1866 if (b == EXIT_BLOCK_PTR)
1868 for (first = NEXT_INSN (first) ; first; first = NEXT_INSN (first))
1869 if (INSN_P (first)
1870 && GET_CODE (PATTERN (first)) != USE
1871 && ! ((GET_CODE (PATTERN (first)) == ADDR_VEC
1872 || GET_CODE (PATTERN (first)) == ADDR_DIFF_VEC)
1873 && prev_real_insn (first) != 0
1874 && GET_CODE (prev_real_insn (first)) == JUMP_INSN))
1875 abort ();
1876 break;
1879 FREE_REG_SET (live_relevant_regs);
1880 *p = 0;
1883 /* Print debugging trace information if -dg switch is given,
1884 showing the information on which the allocation decisions are based. */
1886 static void
1887 dump_conflicts (file)
1888 FILE *file;
1890 int i;
1891 int has_preferences;
1892 int nregs;
1893 nregs = 0;
1894 for (i = 0; i < max_allocno; i++)
1896 if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
1897 continue;
1898 nregs++;
1900 fprintf (file, ";; %d regs to allocate:", nregs);
1901 for (i = 0; i < max_allocno; i++)
1903 int j;
1904 if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
1905 continue;
1906 fprintf (file, " %d", allocno[allocno_order[i]].reg);
1907 for (j = 0; j < max_regno; j++)
1908 if (reg_allocno[j] == allocno_order[i]
1909 && j != allocno[allocno_order[i]].reg)
1910 fprintf (file, "+%d", j);
1911 if (allocno[allocno_order[i]].size != 1)
1912 fprintf (file, " (%d)", allocno[allocno_order[i]].size);
1914 fprintf (file, "\n");
1916 for (i = 0; i < max_allocno; i++)
1918 int j;
1919 fprintf (file, ";; %d conflicts:", allocno[i].reg);
1920 for (j = 0; j < max_allocno; j++)
1921 if (CONFLICTP (j, i))
1922 fprintf (file, " %d", allocno[j].reg);
1923 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1924 if (TEST_HARD_REG_BIT (allocno[i].hard_reg_conflicts, j))
1925 fprintf (file, " %d", j);
1926 fprintf (file, "\n");
1928 has_preferences = 0;
1929 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1930 if (TEST_HARD_REG_BIT (allocno[i].hard_reg_preferences, j))
1931 has_preferences = 1;
1933 if (! has_preferences)
1934 continue;
1935 fprintf (file, ";; %d preferences:", allocno[i].reg);
1936 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1937 if (TEST_HARD_REG_BIT (allocno[i].hard_reg_preferences, j))
1938 fprintf (file, " %d", j);
1939 fprintf (file, "\n");
1941 fprintf (file, "\n");
1944 void
1945 dump_global_regs (file)
1946 FILE *file;
1948 int i, j;
1950 fprintf (file, ";; Register dispositions:\n");
1951 for (i = FIRST_PSEUDO_REGISTER, j = 0; i < max_regno; i++)
1952 if (reg_renumber[i] >= 0)
1954 fprintf (file, "%d in %d ", i, reg_renumber[i]);
1955 if (++j % 6 == 0)
1956 fprintf (file, "\n");
1959 fprintf (file, "\n\n;; Hard regs used: ");
1960 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1961 if (regs_ever_live[i])
1962 fprintf (file, " %d", i);
1963 fprintf (file, "\n\n");