Update to gcc-3.4.6
[dragonfly.git] / contrib / gcc-3.4 / gcc / global.c
CommitLineData
003757ed
MD
1/* Allocate registers for pseudo-registers that span basic blocks.
2 Copyright (C) 1987, 1988, 1991, 1994, 1996, 1997, 1998,
3 1999, 2000, 2002, 2003 Free Software Foundation, Inc.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 2, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING. If not, write to the Free
19Software Foundation, 59 Temple Place - Suite 330, Boston, MA
2002111-1307, USA. */
21
22
23#include "config.h"
24#include "system.h"
25#include "coretypes.h"
26#include "tm.h"
27
28#include "machmode.h"
29#include "hard-reg-set.h"
30#include "rtl.h"
31#include "tm_p.h"
32#include "flags.h"
33#include "basic-block.h"
34#include "regs.h"
35#include "function.h"
36#include "insn-config.h"
37#include "reload.h"
38#include "output.h"
39#include "toplev.h"
40
41/* This pass of the compiler performs global register allocation.
42 It assigns hard register numbers to all the pseudo registers
43 that were not handled in local_alloc. Assignments are recorded
44 in the vector reg_renumber, not by changing the rtl code.
45 (Such changes are made by final). The entry point is
46 the function global_alloc.
47
48 After allocation is complete, the reload pass is run as a subroutine
49 of this pass, so that when a pseudo reg loses its hard reg due to
50 spilling it is possible to make a second attempt to find a hard
51 reg for it. The reload pass is independent in other respects
52 and it is run even when stupid register allocation is in use.
53
54 1. Assign allocation-numbers (allocnos) to the pseudo-registers
55 still needing allocations and to the pseudo-registers currently
56 allocated by local-alloc which may be spilled by reload.
57 Set up tables reg_allocno and allocno_reg to map
58 reg numbers to allocnos and vice versa.
59 max_allocno gets the number of allocnos in use.
60
61 2. Allocate a max_allocno by max_allocno conflict bit matrix and clear it.
62 Allocate a max_allocno by FIRST_PSEUDO_REGISTER conflict matrix
63 for conflicts between allocnos and explicit hard register use
64 (which includes use of pseudo-registers allocated by local_alloc).
65
66 3. For each basic block
67 walk forward through the block, recording which
68 pseudo-registers and which hardware registers are live.
69 Build the conflict matrix between the pseudo-registers
70 and another of pseudo-registers versus hardware registers.
71 Also record the preferred hardware registers
72 for each pseudo-register.
73
74 4. Sort a table of the allocnos into order of
75 desirability of the variables.
76
77 5. Allocate the variables in that order; each if possible into
78 a preferred register, else into another register. */
79\f
80/* Number of pseudo-registers which are candidates for allocation. */
81
82static int max_allocno;
83
84/* Indexed by (pseudo) reg number, gives the allocno, or -1
85 for pseudo registers which are not to be allocated. */
86
87static int *reg_allocno;
88
89struct allocno
90{
91 int reg;
92 /* Gives the number of consecutive hard registers needed by that
93 pseudo reg. */
94 int size;
95
96 /* Number of calls crossed by each allocno. */
97 int calls_crossed;
98
1378ea41
SS
99 /* Number of calls that might throw crossed by each allocno. */
100 int throwing_calls_crossed;
101
003757ed
MD
102 /* Number of refs to each allocno. */
103 int n_refs;
104
105 /* Frequency of uses of each allocno. */
106 int freq;
107
108 /* Guess at live length of each allocno.
109 This is actually the max of the live lengths of the regs. */
110 int live_length;
111
112 /* Set of hard regs conflicting with allocno N. */
113
114 HARD_REG_SET hard_reg_conflicts;
115
116 /* Set of hard regs preferred by allocno N.
117 This is used to make allocnos go into regs that are copied to or from them,
118 when possible, to reduce register shuffling. */
119
120 HARD_REG_SET hard_reg_preferences;
121
122 /* Similar, but just counts register preferences made in simple copy
123 operations, rather than arithmetic. These are given priority because
124 we can always eliminate an insn by using these, but using a register
125 in the above list won't always eliminate an insn. */
126
127 HARD_REG_SET hard_reg_copy_preferences;
128
129 /* Similar to hard_reg_preferences, but includes bits for subsequent
130 registers when an allocno is multi-word. The above variable is used for
131 allocation while this is used to build reg_someone_prefers, below. */
132
133 HARD_REG_SET hard_reg_full_preferences;
134
135 /* Set of hard registers that some later allocno has a preference for. */
136
137 HARD_REG_SET regs_someone_prefers;
138
139#ifdef STACK_REGS
140 /* Set to true if allocno can't be allocated in the stack register. */
141 bool no_stack_reg;
142#endif
143};
144
145static struct allocno *allocno;
146
147/* A vector of the integers from 0 to max_allocno-1,
148 sorted in the order of first-to-be-allocated first. */
149
150static int *allocno_order;
151
152/* Indexed by (pseudo) reg number, gives the number of another
153 lower-numbered pseudo reg which can share a hard reg with this pseudo
154 *even if the two pseudos would otherwise appear to conflict*. */
155
156static int *reg_may_share;
157
158/* Define the number of bits in each element of `conflicts' and what
159 type that element has. We use the largest integer format on the
160 host machine. */
161
162#define INT_BITS HOST_BITS_PER_WIDE_INT
163#define INT_TYPE HOST_WIDE_INT
164
165/* max_allocno by max_allocno array of bits,
166 recording whether two allocno's conflict (can't go in the same
167 hardware register).
168
169 `conflicts' is symmetric after the call to mirror_conflicts. */
170
171static INT_TYPE *conflicts;
172
173/* Number of ints require to hold max_allocno bits.
174 This is the length of a row in `conflicts'. */
175
176static int allocno_row_words;
177
178/* Two macros to test or store 1 in an element of `conflicts'. */
179
180#define CONFLICTP(I, J) \
181 (conflicts[(I) * allocno_row_words + (unsigned) (J) / INT_BITS] \
182 & ((INT_TYPE) 1 << ((unsigned) (J) % INT_BITS)))
183
184/* For any allocno set in ALLOCNO_SET, set ALLOCNO to that allocno,
185 and execute CODE. */
186#define EXECUTE_IF_SET_IN_ALLOCNO_SET(ALLOCNO_SET, ALLOCNO, CODE) \
187do { \
188 int i_; \
189 int allocno_; \
190 INT_TYPE *p_ = (ALLOCNO_SET); \
191 \
192 for (i_ = allocno_row_words - 1, allocno_ = 0; i_ >= 0; \
193 i_--, allocno_ += INT_BITS) \
194 { \
195 unsigned INT_TYPE word_ = (unsigned INT_TYPE) *p_++; \
196 \
197 for ((ALLOCNO) = allocno_; word_; word_ >>= 1, (ALLOCNO)++) \
198 { \
199 if (word_ & 1) \
200 {CODE;} \
201 } \
202 } \
203} while (0)
204
205/* This doesn't work for non-GNU C due to the way CODE is macro expanded. */
206#if 0
207/* For any allocno that conflicts with IN_ALLOCNO, set OUT_ALLOCNO to
208 the conflicting allocno, and execute CODE. This macro assumes that
209 mirror_conflicts has been run. */
210#define EXECUTE_IF_CONFLICT(IN_ALLOCNO, OUT_ALLOCNO, CODE)\
211 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + (IN_ALLOCNO) * allocno_row_words,\
212 OUT_ALLOCNO, (CODE))
213#endif
214
215/* Set of hard regs currently live (during scan of all insns). */
216
217static HARD_REG_SET hard_regs_live;
218
219/* Set of registers that global-alloc isn't supposed to use. */
220
221static HARD_REG_SET no_global_alloc_regs;
222
223/* Set of registers used so far. */
224
225static HARD_REG_SET regs_used_so_far;
226
227/* Number of refs to each hard reg, as used by local alloc.
228 It is zero for a reg that contains global pseudos or is explicitly used. */
229
230static int local_reg_n_refs[FIRST_PSEUDO_REGISTER];
231
232/* Frequency of uses of given hard reg. */
233static int local_reg_freq[FIRST_PSEUDO_REGISTER];
234
235/* Guess at live length of each hard reg, as used by local alloc.
236 This is actually the sum of the live lengths of the specific regs. */
237
238static int local_reg_live_length[FIRST_PSEUDO_REGISTER];
239
240/* Set to 1 a bit in a vector TABLE of HARD_REG_SETs, for vector
241 element I, and hard register number J. */
242
243#define SET_REGBIT(TABLE, I, J) SET_HARD_REG_BIT (allocno[I].TABLE, J)
244
245/* Bit mask for allocnos live at current point in the scan. */
246
247static INT_TYPE *allocnos_live;
248
249/* Test, set or clear bit number I in allocnos_live,
250 a bit vector indexed by allocno. */
251
252#define SET_ALLOCNO_LIVE(I) \
253 (allocnos_live[(unsigned) (I) / INT_BITS] \
254 |= ((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS)))
255
256#define CLEAR_ALLOCNO_LIVE(I) \
257 (allocnos_live[(unsigned) (I) / INT_BITS] \
258 &= ~((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS)))
259
260/* This is turned off because it doesn't work right for DImode.
261 (And it is only used for DImode, so the other cases are worthless.)
262 The problem is that it isn't true that there is NO possibility of conflict;
263 only that there is no conflict if the two pseudos get the exact same regs.
264 If they were allocated with a partial overlap, there would be a conflict.
265 We can't safely turn off the conflict unless we have another way to
266 prevent the partial overlap.
267
268 Idea: change hard_reg_conflicts so that instead of recording which
269 hard regs the allocno may not overlap, it records where the allocno
270 may not start. Change both where it is used and where it is updated.
271 Then there is a way to record that (reg:DI 108) may start at 10
272 but not at 9 or 11. There is still the question of how to record
273 this semi-conflict between two pseudos. */
274#if 0
275/* Reg pairs for which conflict after the current insn
276 is inhibited by a REG_NO_CONFLICT note.
277 If the table gets full, we ignore any other notes--that is conservative. */
278#define NUM_NO_CONFLICT_PAIRS 4
279/* Number of pairs in use in this insn. */
280int n_no_conflict_pairs;
281static struct { int allocno1, allocno2;}
282 no_conflict_pairs[NUM_NO_CONFLICT_PAIRS];
283#endif /* 0 */
284
285/* Record all regs that are set in any one insn.
286 Communication from mark_reg_{store,clobber} and global_conflicts. */
287
288static rtx *regs_set;
289static int n_regs_set;
290
291/* All registers that can be eliminated. */
292
293static HARD_REG_SET eliminable_regset;
294
295static int allocno_compare (const void *, const void *);
296static void global_conflicts (void);
297static void mirror_conflicts (void);
298static void expand_preferences (void);
299static void prune_preferences (void);
300static void find_reg (int, HARD_REG_SET, int, int, int);
301static void record_one_conflict (int);
302static void record_conflicts (int *, int);
303static void mark_reg_store (rtx, rtx, void *);
304static void mark_reg_clobber (rtx, rtx, void *);
305static void mark_reg_conflicts (rtx);
306static void mark_reg_death (rtx);
307static void mark_reg_live_nc (int, enum machine_mode);
308static void set_preference (rtx, rtx);
309static void dump_conflicts (FILE *);
310static void reg_becomes_live (rtx, rtx, void *);
311static void reg_dies (int, enum machine_mode, struct insn_chain *);
312\f
313/* Perform allocation of pseudo-registers not allocated by local_alloc.
314 FILE is a file to output debugging information on,
315 or zero if such output is not desired.
316
317 Return value is nonzero if reload failed
318 and we must not do any more for this function. */
319
320int
321global_alloc (FILE *file)
322{
323 int retval;
324#ifdef ELIMINABLE_REGS
325 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
326#endif
327 int need_fp
328 = (! flag_omit_frame_pointer
329 || (current_function_calls_alloca && EXIT_IGNORE_STACK)
330 || FRAME_POINTER_REQUIRED);
331
332 size_t i;
333 rtx x;
334
335 max_allocno = 0;
336
337 /* A machine may have certain hard registers that
338 are safe to use only within a basic block. */
339
340 CLEAR_HARD_REG_SET (no_global_alloc_regs);
341
342 /* Build the regset of all eliminable registers and show we can't use those
343 that we already know won't be eliminated. */
344#ifdef ELIMINABLE_REGS
345 for (i = 0; i < ARRAY_SIZE (eliminables); i++)
346 {
347 bool cannot_elim
348 = (! CAN_ELIMINATE (eliminables[i].from, eliminables[i].to)
349 || (eliminables[i].to == STACK_POINTER_REGNUM && need_fp));
350
351 if (!regs_asm_clobbered[eliminables[i].from])
352 {
353 SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from);
354
355 if (cannot_elim)
356 SET_HARD_REG_BIT (no_global_alloc_regs, eliminables[i].from);
357 }
358 else if (cannot_elim)
359 error ("%s cannot be used in asm here",
360 reg_names[eliminables[i].from]);
361 else
362 regs_ever_live[eliminables[i].from] = 1;
363 }
364#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
365 if (!regs_asm_clobbered[HARD_FRAME_POINTER_REGNUM])
366 {
367 SET_HARD_REG_BIT (eliminable_regset, HARD_FRAME_POINTER_REGNUM);
368 if (need_fp)
369 SET_HARD_REG_BIT (no_global_alloc_regs, HARD_FRAME_POINTER_REGNUM);
370 }
371 else if (need_fp)
372 error ("%s cannot be used in asm here",
373 reg_names[HARD_FRAME_POINTER_REGNUM]);
374 else
375 regs_ever_live[HARD_FRAME_POINTER_REGNUM] = 1;
376#endif
377
378#else
379 if (!regs_asm_clobbered[FRAME_POINTER_REGNUM])
380 {
381 SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM);
382 if (need_fp)
383 SET_HARD_REG_BIT (no_global_alloc_regs, FRAME_POINTER_REGNUM);
384 }
385 else if (need_fp)
386 error ("%s cannot be used in asm here", reg_names[FRAME_POINTER_REGNUM]);
387 else
388 regs_ever_live[FRAME_POINTER_REGNUM] = 1;
389#endif
390
391 /* Track which registers have already been used. Start with registers
392 explicitly in the rtl, then registers allocated by local register
393 allocation. */
394
395 CLEAR_HARD_REG_SET (regs_used_so_far);
396#ifdef LEAF_REGISTERS
397 /* If we are doing the leaf function optimization, and this is a leaf
398 function, it means that the registers that take work to save are those
399 that need a register window. So prefer the ones that can be used in
400 a leaf function. */
401 {
402 const char *cheap_regs;
403 const char *const leaf_regs = LEAF_REGISTERS;
404
405 if (only_leaf_regs_used () && leaf_function_p ())
406 cheap_regs = leaf_regs;
407 else
408 cheap_regs = call_used_regs;
409 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
410 if (regs_ever_live[i] || cheap_regs[i])
411 SET_HARD_REG_BIT (regs_used_so_far, i);
412 }
413#else
414 /* We consider registers that do not have to be saved over calls as if
415 they were already used since there is no cost in using them. */
416 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
417 if (regs_ever_live[i] || call_used_regs[i])
418 SET_HARD_REG_BIT (regs_used_so_far, i);
419#endif
420
421 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
422 if (reg_renumber[i] >= 0)
423 SET_HARD_REG_BIT (regs_used_so_far, reg_renumber[i]);
424
425 /* Establish mappings from register number to allocation number
426 and vice versa. In the process, count the allocnos. */
427
428 reg_allocno = xmalloc (max_regno * sizeof (int));
429
430 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
431 reg_allocno[i] = -1;
432
433 /* Initialize the shared-hard-reg mapping
434 from the list of pairs that may share. */
435 reg_may_share = xcalloc (max_regno, sizeof (int));
436 for (x = regs_may_share; x; x = XEXP (XEXP (x, 1), 1))
437 {
438 int r1 = REGNO (XEXP (x, 0));
439 int r2 = REGNO (XEXP (XEXP (x, 1), 0));
440 if (r1 > r2)
441 reg_may_share[r1] = r2;
442 else
443 reg_may_share[r2] = r1;
444 }
445
446 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
447 /* Note that reg_live_length[i] < 0 indicates a "constant" reg
448 that we are supposed to refrain from putting in a hard reg.
449 -2 means do make an allocno but don't allocate it. */
450 if (REG_N_REFS (i) != 0 && REG_LIVE_LENGTH (i) != -1
451 /* Don't allocate pseudos that cross calls,
452 if this function receives a nonlocal goto. */
453 && (! current_function_has_nonlocal_label
454 || REG_N_CALLS_CROSSED (i) == 0))
455 {
456 if (reg_renumber[i] < 0 && reg_may_share[i] && reg_allocno[reg_may_share[i]] >= 0)
457 reg_allocno[i] = reg_allocno[reg_may_share[i]];
458 else
459 reg_allocno[i] = max_allocno++;
460 if (REG_LIVE_LENGTH (i) == 0)
461 abort ();
462 }
463 else
464 reg_allocno[i] = -1;
465
466 allocno = xcalloc (max_allocno, sizeof (struct allocno));
467
468 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
469 if (reg_allocno[i] >= 0)
470 {
471 int num = reg_allocno[i];
472 allocno[num].reg = i;
473 allocno[num].size = PSEUDO_REGNO_SIZE (i);
474 allocno[num].calls_crossed += REG_N_CALLS_CROSSED (i);
1378ea41
SS
475 allocno[num].throwing_calls_crossed
476 += REG_N_THROWING_CALLS_CROSSED (i);
003757ed
MD
477 allocno[num].n_refs += REG_N_REFS (i);
478 allocno[num].freq += REG_FREQ (i);
479 if (allocno[num].live_length < REG_LIVE_LENGTH (i))
480 allocno[num].live_length = REG_LIVE_LENGTH (i);
481 }
482
483 /* Calculate amount of usage of each hard reg by pseudos
484 allocated by local-alloc. This is to see if we want to
485 override it. */
486 memset (local_reg_live_length, 0, sizeof local_reg_live_length);
487 memset (local_reg_n_refs, 0, sizeof local_reg_n_refs);
488 memset (local_reg_freq, 0, sizeof local_reg_freq);
489 for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
490 if (reg_renumber[i] >= 0)
491 {
492 int regno = reg_renumber[i];
493 int endregno = regno + HARD_REGNO_NREGS (regno, PSEUDO_REGNO_MODE (i));
494 int j;
495
496 for (j = regno; j < endregno; j++)
497 {
498 local_reg_n_refs[j] += REG_N_REFS (i);
499 local_reg_freq[j] += REG_FREQ (i);
500 local_reg_live_length[j] += REG_LIVE_LENGTH (i);
501 }
502 }
503
504 /* We can't override local-alloc for a reg used not just by local-alloc. */
505 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
506 if (regs_ever_live[i])
507 local_reg_n_refs[i] = 0, local_reg_freq[i] = 0;
508
509 allocno_row_words = (max_allocno + INT_BITS - 1) / INT_BITS;
510
511 /* We used to use alloca here, but the size of what it would try to
512 allocate would occasionally cause it to exceed the stack limit and
513 cause unpredictable core dumps. Some examples were > 2Mb in size. */
514 conflicts = xcalloc (max_allocno * allocno_row_words, sizeof (INT_TYPE));
515
516 allocnos_live = xmalloc (allocno_row_words * sizeof (INT_TYPE));
517
518 /* If there is work to be done (at least one reg to allocate),
519 perform global conflict analysis and allocate the regs. */
520
521 if (max_allocno > 0)
522 {
523 /* Scan all the insns and compute the conflicts among allocnos
524 and between allocnos and hard regs. */
525
526 global_conflicts ();
527
528 mirror_conflicts ();
529
530 /* Eliminate conflicts between pseudos and eliminable registers. If
531 the register is not eliminated, the pseudo won't really be able to
532 live in the eliminable register, so the conflict doesn't matter.
533 If we do eliminate the register, the conflict will no longer exist.
534 So in either case, we can ignore the conflict. Likewise for
535 preferences. */
536
537 for (i = 0; i < (size_t) max_allocno; i++)
538 {
539 AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_conflicts,
540 eliminable_regset);
541 AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_copy_preferences,
542 eliminable_regset);
543 AND_COMPL_HARD_REG_SET (allocno[i].hard_reg_preferences,
544 eliminable_regset);
545 }
546
547 /* Try to expand the preferences by merging them between allocnos. */
548
549 expand_preferences ();
550
551 /* Determine the order to allocate the remaining pseudo registers. */
552
553 allocno_order = xmalloc (max_allocno * sizeof (int));
554 for (i = 0; i < (size_t) max_allocno; i++)
555 allocno_order[i] = i;
556
557 /* Default the size to 1, since allocno_compare uses it to divide by.
558 Also convert allocno_live_length of zero to -1. A length of zero
559 can occur when all the registers for that allocno have reg_live_length
560 equal to -2. In this case, we want to make an allocno, but not
561 allocate it. So avoid the divide-by-zero and set it to a low
562 priority. */
563
564 for (i = 0; i < (size_t) max_allocno; i++)
565 {
566 if (allocno[i].size == 0)
567 allocno[i].size = 1;
568 if (allocno[i].live_length == 0)
569 allocno[i].live_length = -1;
570 }
571
572 qsort (allocno_order, max_allocno, sizeof (int), allocno_compare);
573
574 prune_preferences ();
575
576 if (file)
577 dump_conflicts (file);
578
579 /* Try allocating them, one by one, in that order,
580 except for parameters marked with reg_live_length[regno] == -2. */
581
582 for (i = 0; i < (size_t) max_allocno; i++)
583 if (reg_renumber[allocno[allocno_order[i]].reg] < 0
584 && REG_LIVE_LENGTH (allocno[allocno_order[i]].reg) >= 0)
585 {
586 /* If we have more than one register class,
587 first try allocating in the class that is cheapest
588 for this pseudo-reg. If that fails, try any reg. */
589 if (N_REG_CLASSES > 1)
590 {
591 find_reg (allocno_order[i], 0, 0, 0, 0);
592 if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
593 continue;
594 }
595 if (reg_alternate_class (allocno[allocno_order[i]].reg) != NO_REGS)
596 find_reg (allocno_order[i], 0, 1, 0, 0);
597 }
598
599 free (allocno_order);
600 }
601
602 /* Do the reloads now while the allocno data still exist, so that we can
603 try to assign new hard regs to any pseudo regs that are spilled. */
604
605#if 0 /* We need to eliminate regs even if there is no rtl code,
606 for the sake of debugging information. */
607 if (n_basic_blocks > 0)
608#endif
609 {
610 build_insn_chain (get_insns ());
611 retval = reload (get_insns (), 1);
612 }
613
614 /* Clean up. */
615 free (reg_allocno);
616 free (reg_may_share);
617 free (allocno);
618 free (conflicts);
619 free (allocnos_live);
620
621 return retval;
622}
623
624/* Sort predicate for ordering the allocnos.
625 Returns -1 (1) if *v1 should be allocated before (after) *v2. */
626
627static int
628allocno_compare (const void *v1p, const void *v2p)
629{
630 int v1 = *(const int *)v1p, v2 = *(const int *)v2p;
631 /* Note that the quotient will never be bigger than
632 the value of floor_log2 times the maximum number of
633 times a register can occur in one insn (surely less than 100)
634 weighted by the frequency (maximally REG_FREQ_MAX).
635 Multiplying this by 10000/REG_FREQ_MAX can't overflow. */
636 int pri1
637 = (((double) (floor_log2 (allocno[v1].n_refs) * allocno[v1].freq)
638 / allocno[v1].live_length)
639 * (10000 / REG_FREQ_MAX) * allocno[v1].size);
640 int pri2
641 = (((double) (floor_log2 (allocno[v2].n_refs) * allocno[v2].freq)
642 / allocno[v2].live_length)
643 * (10000 / REG_FREQ_MAX) * allocno[v2].size);
644 if (pri2 - pri1)
645 return pri2 - pri1;
646
647 /* If regs are equally good, sort by allocno,
648 so that the results of qsort leave nothing to chance. */
649 return v1 - v2;
650}
651\f
652/* Scan the rtl code and record all conflicts and register preferences in the
653 conflict matrices and preference tables. */
654
655static void
656global_conflicts (void)
657{
658 int i;
659 basic_block b;
660 rtx insn;
661 int *block_start_allocnos;
662
663 /* Make a vector that mark_reg_{store,clobber} will store in. */
664 regs_set = xmalloc (max_parallel * sizeof (rtx) * 2);
665
666 block_start_allocnos = xmalloc (max_allocno * sizeof (int));
667
668 FOR_EACH_BB (b)
669 {
670 memset (allocnos_live, 0, allocno_row_words * sizeof (INT_TYPE));
671
672 /* Initialize table of registers currently live
673 to the state at the beginning of this basic block.
674 This also marks the conflicts among hard registers
675 and any allocnos that are live.
676
677 For pseudo-regs, there is only one bit for each one
678 no matter how many hard regs it occupies.
679 This is ok; we know the size from PSEUDO_REGNO_SIZE.
680 For explicit hard regs, we cannot know the size that way
681 since one hard reg can be used with various sizes.
682 Therefore, we must require that all the hard regs
683 implicitly live as part of a multi-word hard reg
684 are explicitly marked in basic_block_live_at_start. */
685
686 {
687 regset old = b->global_live_at_start;
688 int ax = 0;
689
690 REG_SET_TO_HARD_REG_SET (hard_regs_live, old);
691 EXECUTE_IF_SET_IN_REG_SET (old, FIRST_PSEUDO_REGISTER, i,
692 {
693 int a = reg_allocno[i];
694 if (a >= 0)
695 {
696 SET_ALLOCNO_LIVE (a);
697 block_start_allocnos[ax++] = a;
698 }
699 else if ((a = reg_renumber[i]) >= 0)
700 mark_reg_live_nc
701 (a, PSEUDO_REGNO_MODE (i));
702 });
703
704 /* Record that each allocno now live conflicts with each hard reg
705 now live.
706
707 It is not necessary to mark any conflicts between pseudos as
708 this point, even for pseudos which are live at the start of
709 the basic block.
710
711 Given two pseudos X and Y and any point in the CFG P.
712
713 On any path to point P where X and Y are live one of the
714 following conditions must be true:
715
716 1. X is live at some instruction on the path that
717 evaluates Y.
718
719 2. Y is live at some instruction on the path that
720 evaluates X.
721
722 3. Either X or Y is not evaluated on the path to P
723 (ie it is used uninitialized) and thus the
724 conflict can be ignored.
725
726 In cases #1 and #2 the conflict will be recorded when we
727 scan the instruction that makes either X or Y become live. */
728 record_conflicts (block_start_allocnos, ax);
729
730 /* Pseudos can't go in stack regs at the start of a basic block that
731 is reached by an abnormal edge. Likewise for call clobbered regs,
732 because because caller-save, fixup_abnormal_edges, and possibly
733 the table driven EH machinery are not quite ready to handle such
734 regs live across such edges. */
735 {
736 edge e;
737
738 for (e = b->pred; e ; e = e->pred_next)
739 if (e->flags & EDGE_ABNORMAL)
740 break;
741
742 if (e != NULL)
743 {
744#ifdef STACK_REGS
745 EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live, ax,
746 {
747 allocno[ax].no_stack_reg = 1;
748 });
749 for (ax = FIRST_STACK_REG; ax <= LAST_STACK_REG; ax++)
750 record_one_conflict (ax);
751#endif
752
753 /* No need to record conflicts for call clobbered regs if we have
754 nonlocal labels around, as we don't ever try to allocate such
755 regs in this case. */
756 if (! current_function_has_nonlocal_label)
757 for (ax = 0; ax < FIRST_PSEUDO_REGISTER; ax++)
758 if (call_used_regs [ax])
759 record_one_conflict (ax);
760 }
761 }
762 }
763
764 insn = BB_HEAD (b);
765
766 /* Scan the code of this basic block, noting which allocnos
767 and hard regs are born or die. When one is born,
768 record a conflict with all others currently live. */
769
770 while (1)
771 {
772 RTX_CODE code = GET_CODE (insn);
773 rtx link;
774
775 /* Make regs_set an empty set. */
776
777 n_regs_set = 0;
778
779 if (code == INSN || code == CALL_INSN || code == JUMP_INSN)
780 {
781
782#if 0
783 int i = 0;
784 for (link = REG_NOTES (insn);
785 link && i < NUM_NO_CONFLICT_PAIRS;
786 link = XEXP (link, 1))
787 if (REG_NOTE_KIND (link) == REG_NO_CONFLICT)
788 {
789 no_conflict_pairs[i].allocno1
790 = reg_allocno[REGNO (SET_DEST (PATTERN (insn)))];
791 no_conflict_pairs[i].allocno2
792 = reg_allocno[REGNO (XEXP (link, 0))];
793 i++;
794 }
795#endif /* 0 */
796
797 /* Mark any registers clobbered by INSN as live,
798 so they conflict with the inputs. */
799
800 note_stores (PATTERN (insn), mark_reg_clobber, NULL);
801
802 /* Mark any registers dead after INSN as dead now. */
803
804 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
805 if (REG_NOTE_KIND (link) == REG_DEAD)
806 mark_reg_death (XEXP (link, 0));
807
808 /* Mark any registers set in INSN as live,
809 and mark them as conflicting with all other live regs.
810 Clobbers are processed again, so they conflict with
811 the registers that are set. */
812
813 note_stores (PATTERN (insn), mark_reg_store, NULL);
814
815#ifdef AUTO_INC_DEC
816 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
817 if (REG_NOTE_KIND (link) == REG_INC)
818 mark_reg_store (XEXP (link, 0), NULL_RTX, NULL);
819#endif
820
821 /* If INSN has multiple outputs, then any reg that dies here
822 and is used inside of an output
823 must conflict with the other outputs.
824
825 It is unsafe to use !single_set here since it will ignore an
826 unused output. Just because an output is unused does not mean
827 the compiler can assume the side effect will not occur.
828 Consider if REG appears in the address of an output and we
829 reload the output. If we allocate REG to the same hard
830 register as an unused output we could set the hard register
831 before the output reload insn. */
832 if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn))
833 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
834 if (REG_NOTE_KIND (link) == REG_DEAD)
835 {
836 int used_in_output = 0;
837 int i;
838 rtx reg = XEXP (link, 0);
839
840 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
841 {
842 rtx set = XVECEXP (PATTERN (insn), 0, i);
843 if (GET_CODE (set) == SET
844 && GET_CODE (SET_DEST (set)) != REG
845 && !rtx_equal_p (reg, SET_DEST (set))
846 && reg_overlap_mentioned_p (reg, SET_DEST (set)))
847 used_in_output = 1;
848 }
849 if (used_in_output)
850 mark_reg_conflicts (reg);
851 }
852
853 /* Mark any registers set in INSN and then never used. */
854
855 while (n_regs_set-- > 0)
856 {
857 rtx note = find_regno_note (insn, REG_UNUSED,
858 REGNO (regs_set[n_regs_set]));
859 if (note)
860 mark_reg_death (XEXP (note, 0));
861 }
862 }
863
864 if (insn == BB_END (b))
865 break;
866 insn = NEXT_INSN (insn);
867 }
868 }
869
870 /* Clean up. */
871 free (block_start_allocnos);
872 free (regs_set);
873}
874/* Expand the preference information by looking for cases where one allocno
875 dies in an insn that sets an allocno. If those two allocnos don't conflict,
876 merge any preferences between those allocnos. */
877
878static void
879expand_preferences (void)
880{
881 rtx insn;
882 rtx link;
883 rtx set;
884
885 /* We only try to handle the most common cases here. Most of the cases
886 where this wins are reg-reg copies. */
887
888 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
889 if (INSN_P (insn)
890 && (set = single_set (insn)) != 0
891 && GET_CODE (SET_DEST (set)) == REG
892 && reg_allocno[REGNO (SET_DEST (set))] >= 0)
893 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
894 if (REG_NOTE_KIND (link) == REG_DEAD
895 && GET_CODE (XEXP (link, 0)) == REG
896 && reg_allocno[REGNO (XEXP (link, 0))] >= 0
897 && ! CONFLICTP (reg_allocno[REGNO (SET_DEST (set))],
898 reg_allocno[REGNO (XEXP (link, 0))]))
899 {
900 int a1 = reg_allocno[REGNO (SET_DEST (set))];
901 int a2 = reg_allocno[REGNO (XEXP (link, 0))];
902
903 if (XEXP (link, 0) == SET_SRC (set))
904 {
905 IOR_HARD_REG_SET (allocno[a1].hard_reg_copy_preferences,
906 allocno[a2].hard_reg_copy_preferences);
907 IOR_HARD_REG_SET (allocno[a2].hard_reg_copy_preferences,
908 allocno[a1].hard_reg_copy_preferences);
909 }
910
911 IOR_HARD_REG_SET (allocno[a1].hard_reg_preferences,
912 allocno[a2].hard_reg_preferences);
913 IOR_HARD_REG_SET (allocno[a2].hard_reg_preferences,
914 allocno[a1].hard_reg_preferences);
915 IOR_HARD_REG_SET (allocno[a1].hard_reg_full_preferences,
916 allocno[a2].hard_reg_full_preferences);
917 IOR_HARD_REG_SET (allocno[a2].hard_reg_full_preferences,
918 allocno[a1].hard_reg_full_preferences);
919 }
920}
921\f
922/* Prune the preferences for global registers to exclude registers that cannot
923 be used.
924
925 Compute `regs_someone_prefers', which is a bitmask of the hard registers
926 that are preferred by conflicting registers of lower priority. If possible,
927 we will avoid using these registers. */
928
929static void
930prune_preferences (void)
931{
932 int i;
933 int num;
934 int *allocno_to_order = xmalloc (max_allocno * sizeof (int));
935
936 /* Scan least most important to most important.
937 For each allocno, remove from preferences registers that cannot be used,
938 either because of conflicts or register type. Then compute all registers
939 preferred by each lower-priority register that conflicts. */
940
941 for (i = max_allocno - 1; i >= 0; i--)
942 {
943 HARD_REG_SET temp;
944
945 num = allocno_order[i];
946 allocno_to_order[num] = i;
947 COPY_HARD_REG_SET (temp, allocno[num].hard_reg_conflicts);
948
949 if (allocno[num].calls_crossed == 0)
950 IOR_HARD_REG_SET (temp, fixed_reg_set);
951 else
952 IOR_HARD_REG_SET (temp, call_used_reg_set);
953
954 IOR_COMPL_HARD_REG_SET
955 (temp,
956 reg_class_contents[(int) reg_preferred_class (allocno[num].reg)]);
957
958 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_preferences, temp);
959 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_copy_preferences, temp);
960 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_full_preferences, temp);
961 }
962
963 for (i = max_allocno - 1; i >= 0; i--)
964 {
965 /* Merge in the preferences of lower-priority registers (they have
966 already been pruned). If we also prefer some of those registers,
967 don't exclude them unless we are of a smaller size (in which case
968 we want to give the lower-priority allocno the first chance for
969 these registers). */
970 HARD_REG_SET temp, temp2;
971 int allocno2;
972
973 num = allocno_order[i];
974
975 CLEAR_HARD_REG_SET (temp);
976 CLEAR_HARD_REG_SET (temp2);
977
978 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + num * allocno_row_words,
979 allocno2,
980 {
981 if (allocno_to_order[allocno2] > i)
982 {
983 if (allocno[allocno2].size <= allocno[num].size)
984 IOR_HARD_REG_SET (temp,
985 allocno[allocno2].hard_reg_full_preferences);
986 else
987 IOR_HARD_REG_SET (temp2,
988 allocno[allocno2].hard_reg_full_preferences);
989 }
990 });
991
992 AND_COMPL_HARD_REG_SET (temp, allocno[num].hard_reg_full_preferences);
993 IOR_HARD_REG_SET (temp, temp2);
994 COPY_HARD_REG_SET (allocno[num].regs_someone_prefers, temp);
995 }
996 free (allocno_to_order);
997}
998\f
999/* Assign a hard register to allocno NUM; look for one that is the beginning
1000 of a long enough stretch of hard regs none of which conflicts with ALLOCNO.
1001 The registers marked in PREFREGS are tried first.
1002
1003 LOSERS, if nonzero, is a HARD_REG_SET indicating registers that cannot
1004 be used for this allocation.
1005
1006 If ALT_REGS_P is zero, consider only the preferred class of ALLOCNO's reg.
1007 Otherwise ignore that preferred class and use the alternate class.
1008
1009 If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
1010 will have to be saved and restored at calls.
1011
1012 RETRYING is nonzero if this is called from retry_global_alloc.
1013
1014 If we find one, record it in reg_renumber.
1015 If not, do nothing. */
1016
1017static void
1018find_reg (int num, HARD_REG_SET losers, int alt_regs_p, int accept_call_clobbered, int retrying)
1019{
1020 int i, best_reg, pass;
1021 HARD_REG_SET used, used1, used2;
1022
1023 enum reg_class class = (alt_regs_p
1024 ? reg_alternate_class (allocno[num].reg)
1025 : reg_preferred_class (allocno[num].reg));
1026 enum machine_mode mode = PSEUDO_REGNO_MODE (allocno[num].reg);
1027
1028 if (accept_call_clobbered)
1029 COPY_HARD_REG_SET (used1, call_fixed_reg_set);
1030 else if (allocno[num].calls_crossed == 0)
1031 COPY_HARD_REG_SET (used1, fixed_reg_set);
1032 else
1033 COPY_HARD_REG_SET (used1, call_used_reg_set);
1034
1035 /* Some registers should not be allocated in global-alloc. */
1036 IOR_HARD_REG_SET (used1, no_global_alloc_regs);
1037 if (losers)
1038 IOR_HARD_REG_SET (used1, losers);
1039
1040 IOR_COMPL_HARD_REG_SET (used1, reg_class_contents[(int) class]);
1041 COPY_HARD_REG_SET (used2, used1);
1042
1043 IOR_HARD_REG_SET (used1, allocno[num].hard_reg_conflicts);
1044
1045#ifdef CANNOT_CHANGE_MODE_CLASS
1046 cannot_change_mode_set_regs (&used1, mode, allocno[num].reg);
1047#endif
1048
1049 /* Try each hard reg to see if it fits. Do this in two passes.
1050 In the first pass, skip registers that are preferred by some other pseudo
1051 to give it a better chance of getting one of those registers. Only if
1052 we can't get a register when excluding those do we take one of them.
1053 However, we never allocate a register for the first time in pass 0. */
1054
1055 COPY_HARD_REG_SET (used, used1);
1056 IOR_COMPL_HARD_REG_SET (used, regs_used_so_far);
1057 IOR_HARD_REG_SET (used, allocno[num].regs_someone_prefers);
1058
1059 best_reg = -1;
1060 for (i = FIRST_PSEUDO_REGISTER, pass = 0;
1061 pass <= 1 && i >= FIRST_PSEUDO_REGISTER;
1062 pass++)
1063 {
1064 if (pass == 1)
1065 COPY_HARD_REG_SET (used, used1);
1066 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1067 {
1068#ifdef REG_ALLOC_ORDER
1069 int regno = reg_alloc_order[i];
1070#else
1071 int regno = i;
1072#endif
1073 if (! TEST_HARD_REG_BIT (used, regno)
1074 && HARD_REGNO_MODE_OK (regno, mode)
1075 && (allocno[num].calls_crossed == 0
1076 || accept_call_clobbered
1077 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
1078 {
1079 int j;
1080 int lim = regno + HARD_REGNO_NREGS (regno, mode);
1081 for (j = regno + 1;
1082 (j < lim
1083 && ! TEST_HARD_REG_BIT (used, j));
1084 j++);
1085 if (j == lim)
1086 {
1087 best_reg = regno;
1088 break;
1089 }
1090#ifndef REG_ALLOC_ORDER
1091 i = j; /* Skip starting points we know will lose */
1092#endif
1093 }
1094 }
1095 }
1096
1097 /* See if there is a preferred register with the same class as the register
1098 we allocated above. Making this restriction prevents register
1099 preferencing from creating worse register allocation.
1100
1101 Remove from the preferred registers and conflicting registers. Note that
1102 additional conflicts may have been added after `prune_preferences' was
1103 called.
1104
1105 First do this for those register with copy preferences, then all
1106 preferred registers. */
1107
1108 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_copy_preferences, used);
1109 GO_IF_HARD_REG_SUBSET (allocno[num].hard_reg_copy_preferences,
1110 reg_class_contents[(int) NO_REGS], no_copy_prefs);
1111
1112 if (best_reg >= 0)
1113 {
1114 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1115 if (TEST_HARD_REG_BIT (allocno[num].hard_reg_copy_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))))
1125 {
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)
1139 {
1140 best_reg = i;
1141 goto no_prefs;
1142 }
1143 }
1144 }
1145 no_copy_prefs:
1146
1147 AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_preferences, used);
1148 GO_IF_HARD_REG_SUBSET (allocno[num].hard_reg_preferences,
1149 reg_class_contents[(int) NO_REGS], no_prefs);
1150
1151 if (best_reg >= 0)
1152 {
1153 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1154 if (TEST_HARD_REG_BIT (allocno[num].hard_reg_preferences, i)
1155 && HARD_REGNO_MODE_OK (i, mode)
1156 && (allocno[num].calls_crossed == 0
1157 || accept_call_clobbered
1158 || ! HARD_REGNO_CALL_PART_CLOBBERED (i, mode))
1159 && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1160 || reg_class_subset_p (REGNO_REG_CLASS (i),
1161 REGNO_REG_CLASS (best_reg))
1162 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1163 REGNO_REG_CLASS (i))))
1164 {
1165 int j;
1166 int lim = i + HARD_REGNO_NREGS (i, mode);
1167 for (j = i + 1;
1168 (j < lim
1169 && ! TEST_HARD_REG_BIT (used, j)
1170 && (REGNO_REG_CLASS (j)
1171 == REGNO_REG_CLASS (best_reg + (j - i))
1172 || reg_class_subset_p (REGNO_REG_CLASS (j),
1173 REGNO_REG_CLASS (best_reg + (j - i)))
1174 || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1175 REGNO_REG_CLASS (j))));
1176 j++);
1177 if (j == lim)
1178 {
1179 best_reg = i;
1180 break;
1181 }
1182 }
1183 }
1184 no_prefs:
1185
1186 /* If we haven't succeeded yet, try with caller-saves.
1187 We need not check to see if the current function has nonlocal
1188 labels because we don't put any pseudos that are live over calls in
1189 registers in that case. */
1190
1191 if (flag_caller_saves && best_reg < 0)
1192 {
1193 /* Did not find a register. If it would be profitable to
1194 allocate a call-clobbered register and save and restore it
1378ea41
SS
1195 around calls, do that. Don't do this if it crosses any calls
1196 that might throw. */
003757ed
MD
1197 if (! accept_call_clobbered
1198 && allocno[num].calls_crossed != 0
1378ea41 1199 && allocno[num].throwing_calls_crossed == 0
003757ed
MD
1200 && CALLER_SAVE_PROFITABLE (allocno[num].n_refs,
1201 allocno[num].calls_crossed))
1202 {
1203 HARD_REG_SET new_losers;
1204 if (! losers)
1205 CLEAR_HARD_REG_SET (new_losers);
1206 else
1207 COPY_HARD_REG_SET (new_losers, losers);
1208
1209 IOR_HARD_REG_SET(new_losers, losing_caller_save_reg_set);
1210 find_reg (num, new_losers, alt_regs_p, 1, retrying);
1211 if (reg_renumber[allocno[num].reg] >= 0)
1212 {
1213 caller_save_needed = 1;
1214 return;
1215 }
1216 }
1217 }
1218
1219 /* If we haven't succeeded yet,
1220 see if some hard reg that conflicts with us
1221 was utilized poorly by local-alloc.
1222 If so, kick out the regs that were put there by local-alloc
1223 so we can use it instead. */
1224 if (best_reg < 0 && !retrying
1225 /* Let's not bother with multi-reg allocnos. */
1226 && allocno[num].size == 1)
1227 {
1228 /* Count from the end, to find the least-used ones first. */
1229 for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1230 {
1231#ifdef REG_ALLOC_ORDER
1232 int regno = reg_alloc_order[i];
1233#else
1234 int regno = i;
1235#endif
1236
1237 if (local_reg_n_refs[regno] != 0
1238 /* Don't use a reg no good for this pseudo. */
1239 && ! TEST_HARD_REG_BIT (used2, regno)
1240 && HARD_REGNO_MODE_OK (regno, mode)
1241 /* The code below assumes that we need only a single
1242 register, but the check of allocno[num].size above
1243 was not enough. Sometimes we need more than one
1244 register for a single-word value. */
1245 && HARD_REGNO_NREGS (regno, mode) == 1
1246 && (allocno[num].calls_crossed == 0
1247 || accept_call_clobbered
1248 || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode))
1249#ifdef CANNOT_CHANGE_MODE_CLASS
1250 && ! invalid_mode_change_p (regno, REGNO_REG_CLASS (regno),
1251 mode)
1252#endif
1253#ifdef STACK_REGS
1254 && (!allocno[num].no_stack_reg
1255 || regno < FIRST_STACK_REG || regno > LAST_STACK_REG)
1256#endif
1257 )
1258 {
1259 /* We explicitly evaluate the divide results into temporary
1260 variables so as to avoid excess precision problems that occur
1261 on an i386-unknown-sysv4.2 (unixware) host. */
1262
1263 double tmp1 = ((double) local_reg_freq[regno]
1264 / local_reg_live_length[regno]);
1265 double tmp2 = ((double) allocno[num].freq
1266 / allocno[num].live_length);
1267
1268 if (tmp1 < tmp2)
1269 {
1270 /* Hard reg REGNO was used less in total by local regs
1271 than it would be used by this one allocno! */
1272 int k;
1273 for (k = 0; k < max_regno; k++)
1274 if (reg_renumber[k] >= 0)
1275 {
1276 int r = reg_renumber[k];
1277 int endregno
1278 = r + HARD_REGNO_NREGS (r, PSEUDO_REGNO_MODE (k));
1279
1280 if (regno >= r && regno < endregno)
1281 reg_renumber[k] = -1;
1282 }
1283
1284 best_reg = regno;
1285 break;
1286 }
1287 }
1288 }
1289 }
1290
1291 /* Did we find a register? */
1292
1293 if (best_reg >= 0)
1294 {
1295 int lim, j;
1296 HARD_REG_SET this_reg;
1297
1298 /* Yes. Record it as the hard register of this pseudo-reg. */
1299 reg_renumber[allocno[num].reg] = best_reg;
1300 /* Also of any pseudo-regs that share with it. */
1301 if (reg_may_share[allocno[num].reg])
1302 for (j = FIRST_PSEUDO_REGISTER; j < max_regno; j++)
1303 if (reg_allocno[j] == num)
1304 reg_renumber[j] = best_reg;
1305
1306 /* Make a set of the hard regs being allocated. */
1307 CLEAR_HARD_REG_SET (this_reg);
1308 lim = best_reg + HARD_REGNO_NREGS (best_reg, mode);
1309 for (j = best_reg; j < lim; j++)
1310 {
1311 SET_HARD_REG_BIT (this_reg, j);
1312 SET_HARD_REG_BIT (regs_used_so_far, j);
1313 /* This is no longer a reg used just by local regs. */
1314 local_reg_n_refs[j] = 0;
1315 local_reg_freq[j] = 0;
1316 }
1317 /* For each other pseudo-reg conflicting with this one,
1318 mark it as conflicting with the hard regs this one occupies. */
1319 lim = num;
1320 EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + lim * allocno_row_words, j,
1321 {
1322 IOR_HARD_REG_SET (allocno[j].hard_reg_conflicts, this_reg);
1323 });
1324 }
1325}
1326\f
1327/* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1328 Perhaps it had previously seemed not worth a hard reg,
1329 or perhaps its old hard reg has been commandeered for reloads.
1330 FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1331 they do not appear to be allocated.
1332 If FORBIDDEN_REGS is zero, no regs are forbidden. */
1333
1334void
1335retry_global_alloc (int regno, HARD_REG_SET forbidden_regs)
1336{
1337 int alloc_no = reg_allocno[regno];
1338 if (alloc_no >= 0)
1339 {
1340 /* If we have more than one register class,
1341 first try allocating in the class that is cheapest
1342 for this pseudo-reg. If that fails, try any reg. */
1343 if (N_REG_CLASSES > 1)
1344 find_reg (alloc_no, forbidden_regs, 0, 0, 1);
1345 if (reg_renumber[regno] < 0
1346 && reg_alternate_class (regno) != NO_REGS)
1347 find_reg (alloc_no, forbidden_regs, 1, 0, 1);
1348
1349 /* If we found a register, modify the RTL for the register to
1350 show the hard register, and mark that register live. */
1351 if (reg_renumber[regno] >= 0)
1352 {
1353 REGNO (regno_reg_rtx[regno]) = reg_renumber[regno];
1354 mark_home_live (regno);
1355 }
1356 }
1357}
1358\f
1359/* Record a conflict between register REGNO
1360 and everything currently live.
1361 REGNO must not be a pseudo reg that was allocated
1362 by local_alloc; such numbers must be translated through
1363 reg_renumber before calling here. */
1364
1365static void
1366record_one_conflict (int regno)
1367{
1368 int j;
1369
1370 if (regno < FIRST_PSEUDO_REGISTER)
1371 /* When a hard register becomes live,
1372 record conflicts with live pseudo regs. */
1373 EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live, j,
1374 {
1375 SET_HARD_REG_BIT (allocno[j].hard_reg_conflicts, regno);
1376 });
1377 else
1378 /* When a pseudo-register becomes live,
1379 record conflicts first with hard regs,
1380 then with other pseudo regs. */
1381 {
1382 int ialloc = reg_allocno[regno];
1383 int ialloc_prod = ialloc * allocno_row_words;
1384
1385 IOR_HARD_REG_SET (allocno[ialloc].hard_reg_conflicts, hard_regs_live);
1386 for (j = allocno_row_words - 1; j >= 0; j--)
1387 {
1388#if 0
1389 int k;
1390 for (k = 0; k < n_no_conflict_pairs; k++)
1391 if (! ((j == no_conflict_pairs[k].allocno1
1392 && ialloc == no_conflict_pairs[k].allocno2)
1393 ||
1394 (j == no_conflict_pairs[k].allocno2
1395 && ialloc == no_conflict_pairs[k].allocno1)))
1396#endif /* 0 */
1397 conflicts[ialloc_prod + j] |= allocnos_live[j];
1398 }
1399 }
1400}
1401
1402/* Record all allocnos currently live as conflicting
1403 with all hard regs currently live.
1404
1405 ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1406 are currently live. Their bits are also flagged in allocnos_live. */
1407
1408static void
1409record_conflicts (int *allocno_vec, int len)
1410{
1411 while (--len >= 0)
1412 IOR_HARD_REG_SET (allocno[allocno_vec[len]].hard_reg_conflicts,
1413 hard_regs_live);
1414}
1415
1416/* If CONFLICTP (i, j) is true, make sure CONFLICTP (j, i) is also true. */
1417static void
1418mirror_conflicts (void)
1419{
1420 int i, j;
1421 int rw = allocno_row_words;
1422 int rwb = rw * INT_BITS;
1423 INT_TYPE *p = conflicts;
1424 INT_TYPE *q0 = conflicts, *q1, *q2;
1425 unsigned INT_TYPE mask;
1426
1427 for (i = max_allocno - 1, mask = 1; i >= 0; i--, mask <<= 1)
1428 {
1429 if (! mask)
1430 {
1431 mask = 1;
1432 q0++;
1433 }
1434 for (j = allocno_row_words - 1, q1 = q0; j >= 0; j--, q1 += rwb)
1435 {
1436 unsigned INT_TYPE word;
1437
1438 for (word = (unsigned INT_TYPE) *p++, q2 = q1; word;
1439 word >>= 1, q2 += rw)
1440 {
1441 if (word & 1)
1442 *q2 |= mask;
1443 }
1444 }
1445 }
1446}
1447\f
1448/* Handle the case where REG is set by the insn being scanned,
1449 during the forward scan to accumulate conflicts.
1450 Store a 1 in regs_live or allocnos_live for this register, record how many
1451 consecutive hardware registers it actually needs,
1452 and record a conflict with all other registers already live.
1453
1454 Note that even if REG does not remain alive after this insn,
1455 we must mark it here as live, to ensure a conflict between
1456 REG and any other regs set in this insn that really do live.
1457 This is because those other regs could be considered after this.
1458
1459 REG might actually be something other than a register;
1460 if so, we do nothing.
1461
1462 SETTER is 0 if this register was modified by an auto-increment (i.e.,
1463 a REG_INC note was found for it). */
1464
1465static void
1466mark_reg_store (rtx reg, rtx setter, void *data ATTRIBUTE_UNUSED)
1467{
1468 int regno;
1469
1470 if (GET_CODE (reg) == SUBREG)
1471 reg = SUBREG_REG (reg);
1472
1473 if (GET_CODE (reg) != REG)
1474 return;
1475
1476 regs_set[n_regs_set++] = reg;
1477
1478 if (setter && GET_CODE (setter) != CLOBBER)
1479 set_preference (reg, SET_SRC (setter));
1480
1481 regno = REGNO (reg);
1482
1483 /* Either this is one of the max_allocno pseudo regs not allocated,
1484 or it is or has a hardware reg. First handle the pseudo-regs. */
1485 if (regno >= FIRST_PSEUDO_REGISTER)
1486 {
1487 if (reg_allocno[regno] >= 0)
1488 {
1489 SET_ALLOCNO_LIVE (reg_allocno[regno]);
1490 record_one_conflict (regno);
1491 }
1492 }
1493
1494 if (reg_renumber[regno] >= 0)
1495 regno = reg_renumber[regno];
1496
1497 /* Handle hardware regs (and pseudos allocated to hard regs). */
1498 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1499 {
1500 int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1501 while (regno < last)
1502 {
1503 record_one_conflict (regno);
1504 SET_HARD_REG_BIT (hard_regs_live, regno);
1505 regno++;
1506 }
1507 }
1508}
1509\f
1510/* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
1511
1512static void
1513mark_reg_clobber (rtx reg, rtx setter, void *data ATTRIBUTE_UNUSED)
1514{
1515 if (GET_CODE (setter) == CLOBBER)
1516 mark_reg_store (reg, setter, data);
1517}
1518
1519/* Record that REG has conflicts with all the regs currently live.
1520 Do not mark REG itself as live. */
1521
1522static void
1523mark_reg_conflicts (rtx reg)
1524{
1525 int regno;
1526
1527 if (GET_CODE (reg) == SUBREG)
1528 reg = SUBREG_REG (reg);
1529
1530 if (GET_CODE (reg) != REG)
1531 return;
1532
1533 regno = REGNO (reg);
1534
1535 /* Either this is one of the max_allocno pseudo regs not allocated,
1536 or it is or has a hardware reg. First handle the pseudo-regs. */
1537 if (regno >= FIRST_PSEUDO_REGISTER)
1538 {
1539 if (reg_allocno[regno] >= 0)
1540 record_one_conflict (regno);
1541 }
1542
1543 if (reg_renumber[regno] >= 0)
1544 regno = reg_renumber[regno];
1545
1546 /* Handle hardware regs (and pseudos allocated to hard regs). */
1547 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1548 {
1549 int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1550 while (regno < last)
1551 {
1552 record_one_conflict (regno);
1553 regno++;
1554 }
1555 }
1556}
1557\f
1558/* Mark REG as being dead (following the insn being scanned now).
1559 Store a 0 in regs_live or allocnos_live for this register. */
1560
1561static void
1562mark_reg_death (rtx reg)
1563{
1564 int regno = REGNO (reg);
1565
1566 /* Either this is one of the max_allocno pseudo regs not allocated,
1567 or it is a hardware reg. First handle the pseudo-regs. */
1568 if (regno >= FIRST_PSEUDO_REGISTER)
1569 {
1570 if (reg_allocno[regno] >= 0)
1571 CLEAR_ALLOCNO_LIVE (reg_allocno[regno]);
1572 }
1573
1574 /* For pseudo reg, see if it has been assigned a hardware reg. */
1575 if (reg_renumber[regno] >= 0)
1576 regno = reg_renumber[regno];
1577
1578 /* Handle hardware regs (and pseudos allocated to hard regs). */
1579 if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1580 {
1581 /* Pseudo regs already assigned hardware regs are treated
1582 almost the same as explicit hardware regs. */
1583 int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1584 while (regno < last)
1585 {
1586 CLEAR_HARD_REG_BIT (hard_regs_live, regno);
1587 regno++;
1588 }
1589 }
1590}
1591
1592/* Mark hard reg REGNO as currently live, assuming machine mode MODE
1593 for the value stored in it. MODE determines how many consecutive
1594 registers are actually in use. Do not record conflicts;
1595 it is assumed that the caller will do that. */
1596
1597static void
1598mark_reg_live_nc (int regno, enum machine_mode mode)
1599{
1600 int last = regno + HARD_REGNO_NREGS (regno, mode);
1601 while (regno < last)
1602 {
1603 SET_HARD_REG_BIT (hard_regs_live, regno);
1604 regno++;
1605 }
1606}
1607\f
1608/* Try to set a preference for an allocno to a hard register.
1609 We are passed DEST and SRC which are the operands of a SET. It is known
1610 that SRC is a register. If SRC or the first operand of SRC is a register,
1611 try to set a preference. If one of the two is a hard register and the other
1612 is a pseudo-register, mark the preference.
1613
1614 Note that we are not as aggressive as local-alloc in trying to tie a
1615 pseudo-register to a hard register. */
1616
1617static void
1618set_preference (rtx dest, rtx src)
1619{
1620 unsigned int src_regno, dest_regno;
1621 /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1622 to compensate for subregs in SRC or DEST. */
1623 int offset = 0;
1624 unsigned int i;
1625 int copy = 1;
1626
1627 if (GET_RTX_FORMAT (GET_CODE (src))[0] == 'e')
1628 src = XEXP (src, 0), copy = 0;
1629
1630 /* Get the reg number for both SRC and DEST.
1631 If neither is a reg, give up. */
1632
1633 if (GET_CODE (src) == REG)
1634 src_regno = REGNO (src);
1635 else if (GET_CODE (src) == SUBREG && GET_CODE (SUBREG_REG (src)) == REG)
1636 {
1637 src_regno = REGNO (SUBREG_REG (src));
1638
1639 if (REGNO (SUBREG_REG (src)) < FIRST_PSEUDO_REGISTER)
1640 offset += subreg_regno_offset (REGNO (SUBREG_REG (src)),
1641 GET_MODE (SUBREG_REG (src)),
1642 SUBREG_BYTE (src),
1643 GET_MODE (src));
1644 else
1645 offset += (SUBREG_BYTE (src)
1646 / REGMODE_NATURAL_SIZE (GET_MODE (src)));
1647 }
1648 else
1649 return;
1650
1651 if (GET_CODE (dest) == REG)
1652 dest_regno = REGNO (dest);
1653 else if (GET_CODE (dest) == SUBREG && GET_CODE (SUBREG_REG (dest)) == REG)
1654 {
1655 dest_regno = REGNO (SUBREG_REG (dest));
1656
1657 if (REGNO (SUBREG_REG (dest)) < FIRST_PSEUDO_REGISTER)
1658 offset -= subreg_regno_offset (REGNO (SUBREG_REG (dest)),
1659 GET_MODE (SUBREG_REG (dest)),
1660 SUBREG_BYTE (dest),
1661 GET_MODE (dest));
1662 else
1663 offset -= (SUBREG_BYTE (dest)
1664 / REGMODE_NATURAL_SIZE (GET_MODE (dest)));
1665 }
1666 else
1667 return;
1668
1669 /* Convert either or both to hard reg numbers. */
1670
1671 if (reg_renumber[src_regno] >= 0)
1672 src_regno = reg_renumber[src_regno];
1673
1674 if (reg_renumber[dest_regno] >= 0)
1675 dest_regno = reg_renumber[dest_regno];
1676
1677 /* Now if one is a hard reg and the other is a global pseudo
1678 then give the other a preference. */
1679
1680 if (dest_regno < FIRST_PSEUDO_REGISTER && src_regno >= FIRST_PSEUDO_REGISTER
1681 && reg_allocno[src_regno] >= 0)
1682 {
1683 dest_regno -= offset;
1684 if (dest_regno < FIRST_PSEUDO_REGISTER)
1685 {
1686 if (copy)
1687 SET_REGBIT (hard_reg_copy_preferences,
1688 reg_allocno[src_regno], dest_regno);
1689
1690 SET_REGBIT (hard_reg_preferences,
1691 reg_allocno[src_regno], dest_regno);
1692 for (i = dest_regno;
1693 i < dest_regno + HARD_REGNO_NREGS (dest_regno, GET_MODE (dest));
1694 i++)
1695 SET_REGBIT (hard_reg_full_preferences, reg_allocno[src_regno], i);
1696 }
1697 }
1698
1699 if (src_regno < FIRST_PSEUDO_REGISTER && dest_regno >= FIRST_PSEUDO_REGISTER
1700 && reg_allocno[dest_regno] >= 0)
1701 {
1702 src_regno += offset;
1703 if (src_regno < FIRST_PSEUDO_REGISTER)
1704 {
1705 if (copy)
1706 SET_REGBIT (hard_reg_copy_preferences,
1707 reg_allocno[dest_regno], src_regno);
1708
1709 SET_REGBIT (hard_reg_preferences,
1710 reg_allocno[dest_regno], src_regno);
1711 for (i = src_regno;
1712 i < src_regno + HARD_REGNO_NREGS (src_regno, GET_MODE (src));
1713 i++)
1714 SET_REGBIT (hard_reg_full_preferences, reg_allocno[dest_regno], i);
1715 }
1716 }
1717}
1718\f
1719/* Indicate that hard register number FROM was eliminated and replaced with
1720 an offset from hard register number TO. The status of hard registers live
1721 at the start of a basic block is updated by replacing a use of FROM with
1722 a use of TO. */
1723
1724void
1725mark_elimination (int from, int to)
1726{
1727 basic_block bb;
1728
1729 FOR_EACH_BB (bb)
1730 {
1731 regset r = bb->global_live_at_start;
1732 if (REGNO_REG_SET_P (r, from))
1733 {
1734 CLEAR_REGNO_REG_SET (r, from);
1735 SET_REGNO_REG_SET (r, to);
1736 }
1737 }
1738}
1739\f
1740/* Used for communication between the following functions. Holds the
1741 current life information. */
1742static regset live_relevant_regs;
1743
1744/* Record in live_relevant_regs and REGS_SET that register REG became live.
1745 This is called via note_stores. */
1746static void
1747reg_becomes_live (rtx reg, rtx setter ATTRIBUTE_UNUSED, void *regs_set)
1748{
1749 int regno;
1750
1751 if (GET_CODE (reg) == SUBREG)
1752 reg = SUBREG_REG (reg);
1753
1754 if (GET_CODE (reg) != REG)
1755 return;
1756
1757 regno = REGNO (reg);
1758 if (regno < FIRST_PSEUDO_REGISTER)
1759 {
1760 int nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg));
1761 while (nregs-- > 0)
1762 {
1763 SET_REGNO_REG_SET (live_relevant_regs, regno);
1764 if (! fixed_regs[regno])
1765 SET_REGNO_REG_SET ((regset) regs_set, regno);
1766 regno++;
1767 }
1768 }
1769 else if (reg_renumber[regno] >= 0)
1770 {
1771 SET_REGNO_REG_SET (live_relevant_regs, regno);
1772 SET_REGNO_REG_SET ((regset) regs_set, regno);
1773 }
1774}
1775
1776/* Record in live_relevant_regs that register REGNO died. */
1777static void
1778reg_dies (int regno, enum machine_mode mode, struct insn_chain *chain)
1779{
1780 if (regno < FIRST_PSEUDO_REGISTER)
1781 {
1782 int nregs = HARD_REGNO_NREGS (regno, mode);
1783 while (nregs-- > 0)
1784 {
1785 CLEAR_REGNO_REG_SET (live_relevant_regs, regno);
1786 if (! fixed_regs[regno])
1787 SET_REGNO_REG_SET (&chain->dead_or_set, regno);
1788 regno++;
1789 }
1790 }
1791 else
1792 {
1793 CLEAR_REGNO_REG_SET (live_relevant_regs, regno);
1794 if (reg_renumber[regno] >= 0)
1795 SET_REGNO_REG_SET (&chain->dead_or_set, regno);
1796 }
1797}
1798
1799/* Walk the insns of the current function and build reload_insn_chain,
1800 and record register life information. */
1801void
1802build_insn_chain (rtx first)
1803{
1804 struct insn_chain **p = &reload_insn_chain;
1805 struct insn_chain *prev = 0;
1806 basic_block b = ENTRY_BLOCK_PTR->next_bb;
1807 regset_head live_relevant_regs_head;
1808
1809 live_relevant_regs = INITIALIZE_REG_SET (live_relevant_regs_head);
1810
1811 for (; first; first = NEXT_INSN (first))
1812 {
1813 struct insn_chain *c;
1814
1815 if (first == BB_HEAD (b))
1816 {
1817 int i;
1818
1819 CLEAR_REG_SET (live_relevant_regs);
1820
1821 EXECUTE_IF_SET_IN_BITMAP
1822 (b->global_live_at_start, 0, i,
1823 {
1824 if (i < FIRST_PSEUDO_REGISTER
1825 ? ! TEST_HARD_REG_BIT (eliminable_regset, i)
1826 : reg_renumber[i] >= 0)
1827 SET_REGNO_REG_SET (live_relevant_regs, i);
1828 });
1829 }
1830
1831 if (GET_CODE (first) != NOTE && GET_CODE (first) != BARRIER)
1832 {
1833 c = new_insn_chain ();
1834 c->prev = prev;
1835 prev = c;
1836 *p = c;
1837 p = &c->next;
1838 c->insn = first;
1839 c->block = b->index;
1840
1841 if (INSN_P (first))
1842 {
1843 rtx link;
1844
1845 /* Mark the death of everything that dies in this instruction. */
1846
1847 for (link = REG_NOTES (first); link; link = XEXP (link, 1))
1848 if (REG_NOTE_KIND (link) == REG_DEAD
1849 && GET_CODE (XEXP (link, 0)) == REG)
1850 reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)),
1851 c);
1852
1853 COPY_REG_SET (&c->live_throughout, live_relevant_regs);
1854
1855 /* Mark everything born in this instruction as live. */
1856
1857 note_stores (PATTERN (first), reg_becomes_live,
1858 &c->dead_or_set);
1859 }
1860 else
1861 COPY_REG_SET (&c->live_throughout, live_relevant_regs);
1862
1863 if (INSN_P (first))
1864 {
1865 rtx link;
1866
1867 /* Mark anything that is set in this insn and then unused as dying. */
1868
1869 for (link = REG_NOTES (first); link; link = XEXP (link, 1))
1870 if (REG_NOTE_KIND (link) == REG_UNUSED
1871 && GET_CODE (XEXP (link, 0)) == REG)
1872 reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)),
1873 c);
1874 }
1875 }
1876
1877 if (first == BB_END (b))
1878 b = b->next_bb;
1879
1880 /* Stop after we pass the end of the last basic block. Verify that
1881 no real insns are after the end of the last basic block.
1882
1883 We may want to reorganize the loop somewhat since this test should
1884 always be the right exit test. Allow an ADDR_VEC or ADDR_DIF_VEC if
1885 the previous real insn is a JUMP_INSN. */
1886 if (b == EXIT_BLOCK_PTR)
1887 {
1888 for (first = NEXT_INSN (first) ; first; first = NEXT_INSN (first))
1889 if (INSN_P (first)
1890 && GET_CODE (PATTERN (first)) != USE
1891 && ! ((GET_CODE (PATTERN (first)) == ADDR_VEC
1892 || GET_CODE (PATTERN (first)) == ADDR_DIFF_VEC)
1893 && prev_real_insn (first) != 0
1894 && GET_CODE (prev_real_insn (first)) == JUMP_INSN))
1895 abort ();
1896 break;
1897 }
1898 }
1899 FREE_REG_SET (live_relevant_regs);
1900 *p = 0;
1901}
1902\f
1903/* Print debugging trace information if -dg switch is given,
1904 showing the information on which the allocation decisions are based. */
1905
1906static void
1907dump_conflicts (FILE *file)
1908{
1909 int i;
1910 int has_preferences;
1911 int nregs;
1912 nregs = 0;
1913 for (i = 0; i < max_allocno; i++)
1914 {
1915 if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
1916 continue;
1917 nregs++;
1918 }
1919 fprintf (file, ";; %d regs to allocate:", nregs);
1920 for (i = 0; i < max_allocno; i++)
1921 {
1922 int j;
1923 if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
1924 continue;
1925 fprintf (file, " %d", allocno[allocno_order[i]].reg);
1926 for (j = 0; j < max_regno; j++)
1927 if (reg_allocno[j] == allocno_order[i]
1928 && j != allocno[allocno_order[i]].reg)
1929 fprintf (file, "+%d", j);
1930 if (allocno[allocno_order[i]].size != 1)
1931 fprintf (file, " (%d)", allocno[allocno_order[i]].size);
1932 }
1933 fprintf (file, "\n");
1934
1935 for (i = 0; i < max_allocno; i++)
1936 {
1937 int j;
1938 fprintf (file, ";; %d conflicts:", allocno[i].reg);
1939 for (j = 0; j < max_allocno; j++)
1940 if (CONFLICTP (j, i))
1941 fprintf (file, " %d", allocno[j].reg);
1942 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1943 if (TEST_HARD_REG_BIT (allocno[i].hard_reg_conflicts, j))
1944 fprintf (file, " %d", j);
1945 fprintf (file, "\n");
1946
1947 has_preferences = 0;
1948 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1949 if (TEST_HARD_REG_BIT (allocno[i].hard_reg_preferences, j))
1950 has_preferences = 1;
1951
1952 if (! has_preferences)
1953 continue;
1954 fprintf (file, ";; %d preferences:", allocno[i].reg);
1955 for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1956 if (TEST_HARD_REG_BIT (allocno[i].hard_reg_preferences, j))
1957 fprintf (file, " %d", j);
1958 fprintf (file, "\n");
1959 }
1960 fprintf (file, "\n");
1961}
1962
1963void
1964dump_global_regs (FILE *file)
1965{
1966 int i, j;
1967
1968 fprintf (file, ";; Register dispositions:\n");
1969 for (i = FIRST_PSEUDO_REGISTER, j = 0; i < max_regno; i++)
1970 if (reg_renumber[i] >= 0)
1971 {
1972 fprintf (file, "%d in %d ", i, reg_renumber[i]);
1973 if (++j % 6 == 0)
1974 fprintf (file, "\n");
1975 }
1976
1977 fprintf (file, "\n\n;; Hard regs used: ");
1978 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1979 if (regs_ever_live[i])
1980 fprintf (file, " %d", i);
1981 fprintf (file, "\n\n");
1982}