OSDN Git Service

* ltconfig (osf[345]): Append $major to soname_spec.
[pf3gnuchains/gcc-fork.git] / gcc / global.c
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.
4
5 This file is part of GCC.
6
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.
11
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.
16
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.  */
21
22
23 #include "config.h"
24 #include "system.h"
25
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"
38
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.
45
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.
51
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.
58
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).
63
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.
71
72    4. Sort a table of the allocnos into order of
73    desirability of the variables.
74
75    5. Allocate the variables in that order; each if possible into
76    a preferred register, else into another register.  */
77 \f
78 /* Number of pseudo-registers which are candidates for allocation.  */
79
80 static int max_allocno;
81
82 /* Indexed by (pseudo) reg number, gives the allocno, or -1
83    for pseudo registers which are not to be allocated.  */
84
85 static int *reg_allocno;
86
87 struct allocno
88 {
89   int reg;
90   /* Gives the number of consecutive hard registers needed by that
91      pseudo reg.  */
92   int size;
93
94   /* Number of calls crossed by each allocno.  */
95   int calls_crossed;
96
97   /* Number of refs to each allocno.  */
98   int n_refs;
99
100   /* Frequency of uses of each allocno.  */
101   int freq;
102
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;
106
107   /* Set of hard regs conflicting with allocno N.  */
108
109   HARD_REG_SET hard_reg_conflicts;
110
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.  */
114
115   HARD_REG_SET hard_reg_preferences;
116
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.  */
121
122   HARD_REG_SET hard_reg_copy_preferences;
123
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.  */
127
128   HARD_REG_SET hard_reg_full_preferences;
129
130   /* Set of hard registers that some later allocno has a preference for.  */
131
132   HARD_REG_SET regs_someone_prefers;
133 };
134
135 static struct allocno *allocno;
136
137 /* A vector of the integers from 0 to max_allocno-1,
138    sorted in the order of first-to-be-allocated first.  */
139
140 static int *allocno_order;
141
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*.  */
145
146 static int *reg_may_share;
147
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.  */
151
152 #define INT_BITS HOST_BITS_PER_WIDE_INT
153 #define INT_TYPE HOST_WIDE_INT
154
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).
158
159    `conflicts' is symmetric after the call to mirror_conflicts.  */
160
161 static INT_TYPE *conflicts;
162
163 /* Number of ints require to hold max_allocno bits.
164    This is the length of a row in `conflicts'.  */
165
166 static int allocno_row_words;
167
168 /* Two macros to test or store 1 in an element of `conflicts'.  */
169
170 #define CONFLICTP(I, J) \
171  (conflicts[(I) * allocno_row_words + (unsigned) (J) / INT_BITS]        \
172   & ((INT_TYPE) 1 << ((unsigned) (J) % INT_BITS)))
173
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);                                         \
181                                                                         \
182   for (i_ = allocno_row_words - 1, allocno_ = 0; i_ >= 0;               \
183        i_--, allocno_ += INT_BITS)                                      \
184     {                                                                   \
185       unsigned INT_TYPE word_ = (unsigned INT_TYPE) *p_++;              \
186                                                                         \
187       for ((ALLOCNO) = allocno_; word_; word_ >>= 1, (ALLOCNO)++)       \
188         {                                                               \
189           if (word_ & 1)                                                \
190             {CODE;}                                                     \
191         }                                                               \
192     }                                                                   \
193 } while (0)
194
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
204
205 /* Set of hard regs currently live (during scan of all insns).  */
206
207 static HARD_REG_SET hard_regs_live;
208
209 /* Set of registers that global-alloc isn't supposed to use.  */
210
211 static HARD_REG_SET no_global_alloc_regs;
212
213 /* Set of registers used so far.  */
214
215 static HARD_REG_SET regs_used_so_far;
216
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.  */
219
220 static int local_reg_n_refs[FIRST_PSEUDO_REGISTER];
221
222 /* Frequency of uses of given hard reg.  */
223 static int local_reg_freq[FIRST_PSEUDO_REGISTER];
224
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.  */
227
228 static int local_reg_live_length[FIRST_PSEUDO_REGISTER];
229
230 /* Set to 1 a bit in a vector TABLE of HARD_REG_SETs, for vector
231    element I, and hard register number J.  */
232
233 #define SET_REGBIT(TABLE, I, J)  SET_HARD_REG_BIT (allocno[I].TABLE, J)
234
235 /* Bit mask for allocnos live at current point in the scan.  */
236
237 static INT_TYPE *allocnos_live;
238
239 /* Test, set or clear bit number I in allocnos_live,
240    a bit vector indexed by allocno.  */
241
242 #define SET_ALLOCNO_LIVE(I)                             \
243   (allocnos_live[(unsigned) (I) / INT_BITS]             \
244      |= ((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS)))
245
246 #define CLEAR_ALLOCNO_LIVE(I)                           \
247   (allocnos_live[(unsigned) (I) / INT_BITS]             \
248      &= ~((INT_TYPE) 1 << ((unsigned) (I) % INT_BITS)))
249
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.
257
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 */
274
275 /* Record all regs that are set in any one insn.
276    Communication from mark_reg_{store,clobber} and global_conflicts.  */
277
278 static rtx *regs_set;
279 static int n_regs_set;
280
281 /* All registers that can be eliminated.  */
282
283 static HARD_REG_SET eliminable_regset;
284
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 *));
303 \f
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.
307
308    Return value is nonzero if reload failed
309    and we must not do any more for this function.  */
310
311 int
312 global_alloc (file)
313      FILE *file;
314 {
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);
325
326   size_t i;
327   rtx x;
328
329   max_allocno = 0;
330
331   /* A machine may have certain hard registers that
332      are safe to use only within a basic block.  */
333
334   CLEAR_HARD_REG_SET (no_global_alloc_regs);
335
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++)
340     {
341       SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from);
342
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);
346     }
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
352
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
358
359   /* Track which registers have already been used.  Start with registers
360      explicitly in the rtl, then registers allocated by local register
361      allocation.  */
362
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.  */
369   {
370     const char *cheap_regs;
371     const char *const leaf_regs = LEAF_REGISTERS;
372
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);
380   }
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
388
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]);
392
393   /* Establish mappings from register number to allocation number
394      and vice versa.  In the process, count the allocnos.  */
395
396   reg_allocno = (int *) xmalloc (max_regno * sizeof (int));
397
398   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
399     reg_allocno[i] = -1;
400
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))
405     {
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;
412     }
413
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))
423       {
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 ();
430       }
431     else
432       reg_allocno[i] = -1;
433
434   allocno = (struct allocno *) xcalloc (max_allocno, sizeof (struct allocno));
435
436   for (i = FIRST_PSEUDO_REGISTER; i < (size_t) max_regno; i++)
437     if (reg_allocno[i] >= 0)
438       {
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);
447       }
448
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)
457       {
458         int regno = reg_renumber[i];
459         int endregno = regno + HARD_REGNO_NREGS (regno, PSEUDO_REGNO_MODE (i));
460         int j;
461
462         for (j = regno; j < endregno; j++)
463           {
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);
467           }
468       }
469
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;
474
475   allocno_row_words = (max_allocno + INT_BITS - 1) / INT_BITS;
476
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));
482
483   allocnos_live = (INT_TYPE *) xmalloc (allocno_row_words * sizeof (INT_TYPE));
484
485   /* If there is work to be done (at least one reg to allocate),
486      perform global conflict analysis and allocate the regs.  */
487
488   if (max_allocno > 0)
489     {
490       /* Scan all the insns and compute the conflicts among allocnos
491          and between allocnos and hard regs.  */
492
493       global_conflicts ();
494
495       mirror_conflicts ();
496
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.  */
503
504       for (i = 0; i < (size_t) max_allocno; i++)
505         {
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);
512         }
513
514       /* Try to expand the preferences by merging them between allocnos.  */
515
516       expand_preferences ();
517
518       /* Determine the order to allocate the remaining pseudo registers.  */
519
520       allocno_order = (int *) xmalloc (max_allocno * sizeof (int));
521       for (i = 0; i < (size_t) max_allocno; i++)
522         allocno_order[i] = i;
523
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.  */
530
531       for (i = 0; i < (size_t) max_allocno; i++)
532         {
533           if (allocno[i].size == 0)
534             allocno[i].size = 1;
535           if (allocno[i].live_length == 0)
536             allocno[i].live_length = -1;
537         }
538
539       qsort (allocno_order, max_allocno, sizeof (int), allocno_compare);
540
541       prune_preferences ();
542
543       if (file)
544         dump_conflicts (file);
545
546       /* Try allocating them, one by one, in that order,
547          except for parameters marked with reg_live_length[regno] == -2.  */
548
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)
552           {
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)
557               {
558                 find_reg (allocno_order[i], 0, 0, 0, 0);
559                 if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
560                   continue;
561               }
562             if (reg_alternate_class (allocno[allocno_order[i]].reg) != NO_REGS)
563               find_reg (allocno_order[i], 0, 1, 0, 0);
564           }
565
566       free (allocno_order);
567     }
568
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.  */
571
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
576     {
577       build_insn_chain (get_insns ());
578       retval = reload (get_insns (), 1);
579     }
580
581   /* Clean up.  */
582   free (reg_allocno);
583   free (reg_may_share);
584   free (allocno);
585   free (conflicts);
586   free (allocnos_live);
587
588   return retval;
589 }
590
591 /* Sort predicate for ordering the allocnos.
592    Returns -1 (1) if *v1 should be allocated before (after) *v2.  */
593
594 static int
595 allocno_compare (v1p, v2p)
596      const PTR v1p;
597      const PTR v2p;
598 {
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;
615
616   /* If regs are equally good, sort by allocno,
617      so that the results of qsort leave nothing to chance.  */
618   return v1 - v2;
619 }
620 \f
621 /* Scan the rtl code and record all conflicts and register preferences in the
622    conflict matrices and preference tables.  */
623
624 static void
625 global_conflicts ()
626 {
627   int i;
628   basic_block b;
629   rtx insn;
630   int *block_start_allocnos;
631
632   /* Make a vector that mark_reg_{store,clobber} will store in.  */
633   regs_set = (rtx *) xmalloc (max_parallel * sizeof (rtx) * 2);
634
635   block_start_allocnos = (int *) xmalloc (max_allocno * sizeof (int));
636
637   FOR_EACH_BB (b)
638     {
639       memset ((char *) allocnos_live, 0, allocno_row_words * sizeof (INT_TYPE));
640
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.
645
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.  */
654
655       {
656         regset old = b->global_live_at_start;
657         int ax = 0;
658
659         REG_SET_TO_HARD_REG_SET (hard_regs_live, old);
660         EXECUTE_IF_SET_IN_REG_SET (old, FIRST_PSEUDO_REGISTER, i,
661                                    {
662                                      int a = reg_allocno[i];
663                                      if (a >= 0)
664                                        {
665                                          SET_ALLOCNO_LIVE (a);
666                                          block_start_allocnos[ax++] = a;
667                                        }
668                                      else if ((a = reg_renumber[i]) >= 0)
669                                        mark_reg_live_nc
670                                          (a, PSEUDO_REGNO_MODE (i));
671                                    });
672
673         /* Record that each allocno now live conflicts with each hard reg
674            now live.
675
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.
679
680              Given two pseudos X and Y and any point in the CFG P.
681
682              On any path to point P where X and Y are live one of the
683              following conditions must be true:
684
685                 1. X is live at some instruction on the path that
686                    evaluates Y.
687
688                 2. Y is live at some instruction on the path that
689                    evaluates X.
690
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.
694
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);
698
699 #ifdef STACK_REGS
700         {
701           /* Pseudos can't go in stack regs at the start of a basic block
702              that is reached by an abnormal edge.  */
703
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);
711         }
712 #endif
713       }
714
715       insn = b->head;
716
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.  */
720
721       while (1)
722         {
723           RTX_CODE code = GET_CODE (insn);
724           rtx link;
725
726           /* Make regs_set an empty set.  */
727
728           n_regs_set = 0;
729
730           if (code == INSN || code == CALL_INSN || code == JUMP_INSN)
731             {
732
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)
739                   {
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++;
745                   }
746 #endif /* 0 */
747
748               /* Mark any registers clobbered by INSN as live,
749                  so they conflict with the inputs.  */
750
751               note_stores (PATTERN (insn), mark_reg_clobber, NULL);
752
753               /* Mark any registers dead after INSN as dead now.  */
754
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));
758
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.  */
763
764               note_stores (PATTERN (insn), mark_reg_store, NULL);
765
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
771
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.
775
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)
786                     {
787                       int used_in_output = 0;
788                       int i;
789                       rtx reg = XEXP (link, 0);
790
791                       for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
792                         {
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;
799                         }
800                       if (used_in_output)
801                         mark_reg_conflicts (reg);
802                     }
803
804               /* Mark any registers set in INSN and then never used.  */
805
806               while (n_regs_set-- > 0)
807                 {
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));
812                 }
813             }
814
815           if (insn == b->end)
816             break;
817           insn = NEXT_INSN (insn);
818         }
819     }
820
821   /* Clean up.  */
822   free (block_start_allocnos);
823   free (regs_set);
824 }
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.  */
828
829 static void
830 expand_preferences ()
831 {
832   rtx insn;
833   rtx link;
834   rtx set;
835
836   /* We only try to handle the most common cases here.  Most of the cases
837      where this wins are reg-reg copies.  */
838
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))]))
850           {
851             int a1 = reg_allocno[REGNO (SET_DEST (set))];
852             int a2 = reg_allocno[REGNO (XEXP (link, 0))];
853
854             if (XEXP (link, 0) == SET_SRC (set))
855               {
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);
860               }
861
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);
870           }
871 }
872 \f
873 /* Prune the preferences for global registers to exclude registers that cannot
874    be used.
875
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.  */
879
880 static void
881 prune_preferences ()
882 {
883   int i;
884   int num;
885   int *allocno_to_order = (int *) xmalloc (max_allocno * sizeof (int));
886
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.  */
891
892   for (i = max_allocno - 1; i >= 0; i--)
893     {
894       HARD_REG_SET temp;
895
896       num = allocno_order[i];
897       allocno_to_order[num] = i;
898       COPY_HARD_REG_SET (temp, allocno[num].hard_reg_conflicts);
899
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);
904
905       IOR_COMPL_HARD_REG_SET
906         (temp,
907          reg_class_contents[(int) reg_preferred_class (allocno[num].reg)]);
908
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);
912     }
913
914   for (i = max_allocno - 1; i >= 0; i--)
915     {
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;
923
924       num = allocno_order[i];
925
926       CLEAR_HARD_REG_SET (temp);
927       CLEAR_HARD_REG_SET (temp2);
928
929       EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + num * allocno_row_words,
930                                      allocno2,
931         {
932           if (allocno_to_order[allocno2] > i)
933             {
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);
940             }
941         });
942
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);
946     }
947   free (allocno_to_order);
948 }
949 \f
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.
953
954    LOSERS, if nonzero, is a HARD_REG_SET indicating registers that cannot
955    be used for this allocation.
956
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.
959
960    If ACCEPT_CALL_CLOBBERED is nonzero, accept a call-clobbered hard reg that
961    will have to be saved and restored at calls.
962
963    RETRYING is nonzero if this is called from retry_global_alloc.
964
965    If we find one, record it in reg_renumber.
966    If not, do nothing.  */
967
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;
975 {
976   int i, best_reg, pass;
977   HARD_REG_SET used, used1, used2;
978
979   enum reg_class class = (alt_regs_p
980                           ? reg_alternate_class (allocno[num].reg)
981                           : reg_preferred_class (allocno[num].reg));
982   enum machine_mode mode = PSEUDO_REGNO_MODE (allocno[num].reg);
983
984   if (accept_call_clobbered)
985     COPY_HARD_REG_SET (used1, call_fixed_reg_set);
986   else if (allocno[num].calls_crossed == 0)
987     COPY_HARD_REG_SET (used1, fixed_reg_set);
988   else
989     COPY_HARD_REG_SET (used1, call_used_reg_set);
990
991   /* Some registers should not be allocated in global-alloc.  */
992   IOR_HARD_REG_SET (used1, no_global_alloc_regs);
993   if (losers)
994     IOR_HARD_REG_SET (used1, losers);
995
996   IOR_COMPL_HARD_REG_SET (used1, reg_class_contents[(int) class]);
997   COPY_HARD_REG_SET (used2, used1);
998
999   IOR_HARD_REG_SET (used1, allocno[num].hard_reg_conflicts);
1000
1001 #ifdef CANNOT_CHANGE_MODE_CLASS
1002   cannot_change_mode_set_regs (&used1, mode, allocno[num].reg);
1003 #endif
1004
1005   /* Try each hard reg to see if it fits.  Do this in two passes.
1006      In the first pass, skip registers that are preferred by some other pseudo
1007      to give it a better chance of getting one of those registers.  Only if
1008      we can't get a register when excluding those do we take one of them.
1009      However, we never allocate a register for the first time in pass 0.  */
1010
1011   COPY_HARD_REG_SET (used, used1);
1012   IOR_COMPL_HARD_REG_SET (used, regs_used_so_far);
1013   IOR_HARD_REG_SET (used, allocno[num].regs_someone_prefers);
1014
1015   best_reg = -1;
1016   for (i = FIRST_PSEUDO_REGISTER, pass = 0;
1017        pass <= 1 && i >= FIRST_PSEUDO_REGISTER;
1018        pass++)
1019     {
1020       if (pass == 1)
1021         COPY_HARD_REG_SET (used, used1);
1022       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1023         {
1024 #ifdef REG_ALLOC_ORDER
1025           int regno = reg_alloc_order[i];
1026 #else
1027           int regno = i;
1028 #endif
1029           if (! TEST_HARD_REG_BIT (used, regno)
1030               && HARD_REGNO_MODE_OK (regno, mode)
1031               && (allocno[num].calls_crossed == 0
1032                   || accept_call_clobbered
1033                   || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
1034             {
1035               int j;
1036               int lim = regno + HARD_REGNO_NREGS (regno, mode);
1037               for (j = regno + 1;
1038                    (j < lim
1039                     && ! TEST_HARD_REG_BIT (used, j));
1040                    j++);
1041               if (j == lim)
1042                 {
1043                   best_reg = regno;
1044                   break;
1045                 }
1046 #ifndef REG_ALLOC_ORDER
1047               i = j;                    /* Skip starting points we know will lose */
1048 #endif
1049             }
1050           }
1051       }
1052
1053   /* See if there is a preferred register with the same class as the register
1054      we allocated above.  Making this restriction prevents register
1055      preferencing from creating worse register allocation.
1056
1057      Remove from the preferred registers and conflicting registers.  Note that
1058      additional conflicts may have been added after `prune_preferences' was
1059      called.
1060
1061      First do this for those register with copy preferences, then all
1062      preferred registers.  */
1063
1064   AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_copy_preferences, used);
1065   GO_IF_HARD_REG_SUBSET (allocno[num].hard_reg_copy_preferences,
1066                          reg_class_contents[(int) NO_REGS], no_copy_prefs);
1067
1068   if (best_reg >= 0)
1069     {
1070       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1071         if (TEST_HARD_REG_BIT (allocno[num].hard_reg_copy_preferences, i)
1072             && HARD_REGNO_MODE_OK (i, mode)
1073             && (allocno[num].calls_crossed == 0
1074                 || accept_call_clobbered
1075                 || ! HARD_REGNO_CALL_PART_CLOBBERED (i, mode))
1076             && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1077                 || reg_class_subset_p (REGNO_REG_CLASS (i),
1078                                        REGNO_REG_CLASS (best_reg))
1079                 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1080                                        REGNO_REG_CLASS (i))))
1081             {
1082               int j;
1083               int lim = i + HARD_REGNO_NREGS (i, mode);
1084               for (j = i + 1;
1085                    (j < lim
1086                     && ! TEST_HARD_REG_BIT (used, j)
1087                     && (REGNO_REG_CLASS (j)
1088                         == REGNO_REG_CLASS (best_reg + (j - i))
1089                         || reg_class_subset_p (REGNO_REG_CLASS (j),
1090                                                REGNO_REG_CLASS (best_reg + (j - i)))
1091                         || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1092                                                REGNO_REG_CLASS (j))));
1093                    j++);
1094               if (j == lim)
1095                 {
1096                   best_reg = i;
1097                   goto no_prefs;
1098                 }
1099             }
1100     }
1101  no_copy_prefs:
1102
1103   AND_COMPL_HARD_REG_SET (allocno[num].hard_reg_preferences, used);
1104   GO_IF_HARD_REG_SUBSET (allocno[num].hard_reg_preferences,
1105                          reg_class_contents[(int) NO_REGS], no_prefs);
1106
1107   if (best_reg >= 0)
1108     {
1109       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1110         if (TEST_HARD_REG_BIT (allocno[num].hard_reg_preferences, i)
1111             && HARD_REGNO_MODE_OK (i, mode)
1112             && (allocno[num].calls_crossed == 0
1113                 || accept_call_clobbered
1114                 || ! HARD_REGNO_CALL_PART_CLOBBERED (i, mode))
1115             && (REGNO_REG_CLASS (i) == REGNO_REG_CLASS (best_reg)
1116                 || reg_class_subset_p (REGNO_REG_CLASS (i),
1117                                        REGNO_REG_CLASS (best_reg))
1118                 || reg_class_subset_p (REGNO_REG_CLASS (best_reg),
1119                                        REGNO_REG_CLASS (i))))
1120             {
1121               int j;
1122               int lim = i + HARD_REGNO_NREGS (i, mode);
1123               for (j = i + 1;
1124                    (j < lim
1125                     && ! TEST_HARD_REG_BIT (used, j)
1126                     && (REGNO_REG_CLASS (j)
1127                         == REGNO_REG_CLASS (best_reg + (j - i))
1128                         || reg_class_subset_p (REGNO_REG_CLASS (j),
1129                                                REGNO_REG_CLASS (best_reg + (j - i)))
1130                         || reg_class_subset_p (REGNO_REG_CLASS (best_reg + (j - i)),
1131                                                REGNO_REG_CLASS (j))));
1132                    j++);
1133               if (j == lim)
1134                 {
1135                   best_reg = i;
1136                   break;
1137                 }
1138             }
1139     }
1140  no_prefs:
1141
1142   /* If we haven't succeeded yet, try with caller-saves.
1143      We need not check to see if the current function has nonlocal
1144      labels because we don't put any pseudos that are live over calls in
1145      registers in that case.  */
1146
1147   if (flag_caller_saves && best_reg < 0)
1148     {
1149       /* Did not find a register.  If it would be profitable to
1150          allocate a call-clobbered register and save and restore it
1151          around calls, do that.  */
1152       if (! accept_call_clobbered
1153           && allocno[num].calls_crossed != 0
1154           && CALLER_SAVE_PROFITABLE (allocno[num].n_refs,
1155                                      allocno[num].calls_crossed))
1156         {
1157           HARD_REG_SET new_losers;
1158           if (! losers)
1159             CLEAR_HARD_REG_SET (new_losers);
1160           else
1161             COPY_HARD_REG_SET (new_losers, losers);
1162
1163           IOR_HARD_REG_SET(new_losers, losing_caller_save_reg_set);
1164           find_reg (num, new_losers, alt_regs_p, 1, retrying);
1165           if (reg_renumber[allocno[num].reg] >= 0)
1166             {
1167               caller_save_needed = 1;
1168               return;
1169             }
1170         }
1171     }
1172
1173   /* If we haven't succeeded yet,
1174      see if some hard reg that conflicts with us
1175      was utilized poorly by local-alloc.
1176      If so, kick out the regs that were put there by local-alloc
1177      so we can use it instead.  */
1178   if (best_reg < 0 && !retrying
1179       /* Let's not bother with multi-reg allocnos.  */
1180       && allocno[num].size == 1)
1181     {
1182       /* Count from the end, to find the least-used ones first.  */
1183       for (i = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1184         {
1185 #ifdef REG_ALLOC_ORDER
1186           int regno = reg_alloc_order[i];
1187 #else
1188           int regno = i;
1189 #endif
1190
1191           if (local_reg_n_refs[regno] != 0
1192               /* Don't use a reg no good for this pseudo.  */
1193               && ! TEST_HARD_REG_BIT (used2, regno)
1194               && HARD_REGNO_MODE_OK (regno, mode)
1195               /* The code below assumes that we need only a single
1196                  register, but the check of allocno[num].size above
1197                  was not enough.  Sometimes we need more than one
1198                  register for a single-word value.  */
1199               && HARD_REGNO_NREGS (regno, mode) == 1
1200               && (allocno[num].calls_crossed == 0
1201                   || accept_call_clobbered
1202                   || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode))
1203 #ifdef CANNOT_CHANGE_MODE_CLASS
1204               && ! invalid_mode_change_p (regno, REGNO_REG_CLASS (regno),
1205                                           mode)
1206 #endif
1207               )
1208             {
1209               /* We explicitly evaluate the divide results into temporary
1210                  variables so as to avoid excess precision problems that occur
1211                  on an i386-unknown-sysv4.2 (unixware) host.  */
1212
1213               double tmp1 = ((double) local_reg_freq[regno]
1214                             / local_reg_live_length[regno]);
1215               double tmp2 = ((double) allocno[num].freq
1216                              / allocno[num].live_length);
1217
1218               if (tmp1 < tmp2)
1219                 {
1220                   /* Hard reg REGNO was used less in total by local regs
1221                      than it would be used by this one allocno!  */
1222                   int k;
1223                   for (k = 0; k < max_regno; k++)
1224                     if (reg_renumber[k] >= 0)
1225                       {
1226                         int r = reg_renumber[k];
1227                         int endregno
1228                           = r + HARD_REGNO_NREGS (r, PSEUDO_REGNO_MODE (k));
1229
1230                         if (regno >= r && regno < endregno)
1231                           reg_renumber[k] = -1;
1232                       }
1233
1234                   best_reg = regno;
1235                   break;
1236                 }
1237             }
1238         }
1239     }
1240
1241   /* Did we find a register?  */
1242
1243   if (best_reg >= 0)
1244     {
1245       int lim, j;
1246       HARD_REG_SET this_reg;
1247
1248       /* Yes.  Record it as the hard register of this pseudo-reg.  */
1249       reg_renumber[allocno[num].reg] = best_reg;
1250       /* Also of any pseudo-regs that share with it.  */
1251       if (reg_may_share[allocno[num].reg])
1252         for (j = FIRST_PSEUDO_REGISTER; j < max_regno; j++)
1253           if (reg_allocno[j] == num)
1254             reg_renumber[j] = best_reg;
1255
1256       /* Make a set of the hard regs being allocated.  */
1257       CLEAR_HARD_REG_SET (this_reg);
1258       lim = best_reg + HARD_REGNO_NREGS (best_reg, mode);
1259       for (j = best_reg; j < lim; j++)
1260         {
1261           SET_HARD_REG_BIT (this_reg, j);
1262           SET_HARD_REG_BIT (regs_used_so_far, j);
1263           /* This is no longer a reg used just by local regs.  */
1264           local_reg_n_refs[j] = 0;
1265           local_reg_freq[j] = 0;
1266         }
1267       /* For each other pseudo-reg conflicting with this one,
1268          mark it as conflicting with the hard regs this one occupies.  */
1269       lim = num;
1270       EXECUTE_IF_SET_IN_ALLOCNO_SET (conflicts + lim * allocno_row_words, j,
1271         {
1272           IOR_HARD_REG_SET (allocno[j].hard_reg_conflicts, this_reg);
1273         });
1274     }
1275 }
1276 \f
1277 /* Called from `reload' to look for a hard reg to put pseudo reg REGNO in.
1278    Perhaps it had previously seemed not worth a hard reg,
1279    or perhaps its old hard reg has been commandeered for reloads.
1280    FORBIDDEN_REGS indicates certain hard regs that may not be used, even if
1281    they do not appear to be allocated.
1282    If FORBIDDEN_REGS is zero, no regs are forbidden.  */
1283
1284 void
1285 retry_global_alloc (regno, forbidden_regs)
1286      int regno;
1287      HARD_REG_SET forbidden_regs;
1288 {
1289   int alloc_no = reg_allocno[regno];
1290   if (alloc_no >= 0)
1291     {
1292       /* If we have more than one register class,
1293          first try allocating in the class that is cheapest
1294          for this pseudo-reg.  If that fails, try any reg.  */
1295       if (N_REG_CLASSES > 1)
1296         find_reg (alloc_no, forbidden_regs, 0, 0, 1);
1297       if (reg_renumber[regno] < 0
1298           && reg_alternate_class (regno) != NO_REGS)
1299         find_reg (alloc_no, forbidden_regs, 1, 0, 1);
1300
1301       /* If we found a register, modify the RTL for the register to
1302          show the hard register, and mark that register live.  */
1303       if (reg_renumber[regno] >= 0)
1304         {
1305           REGNO (regno_reg_rtx[regno]) = reg_renumber[regno];
1306           mark_home_live (regno);
1307         }
1308     }
1309 }
1310 \f
1311 /* Record a conflict between register REGNO
1312    and everything currently live.
1313    REGNO must not be a pseudo reg that was allocated
1314    by local_alloc; such numbers must be translated through
1315    reg_renumber before calling here.  */
1316
1317 static void
1318 record_one_conflict (regno)
1319      int regno;
1320 {
1321   int j;
1322
1323   if (regno < FIRST_PSEUDO_REGISTER)
1324     /* When a hard register becomes live,
1325        record conflicts with live pseudo regs.  */
1326     EXECUTE_IF_SET_IN_ALLOCNO_SET (allocnos_live, j,
1327       {
1328         SET_HARD_REG_BIT (allocno[j].hard_reg_conflicts, regno);
1329       });
1330   else
1331     /* When a pseudo-register becomes live,
1332        record conflicts first with hard regs,
1333        then with other pseudo regs.  */
1334     {
1335       int ialloc = reg_allocno[regno];
1336       int ialloc_prod = ialloc * allocno_row_words;
1337
1338       IOR_HARD_REG_SET (allocno[ialloc].hard_reg_conflicts, hard_regs_live);
1339       for (j = allocno_row_words - 1; j >= 0; j--)
1340         {
1341 #if 0
1342           int k;
1343           for (k = 0; k < n_no_conflict_pairs; k++)
1344             if (! ((j == no_conflict_pairs[k].allocno1
1345                     && ialloc == no_conflict_pairs[k].allocno2)
1346                    ||
1347                    (j == no_conflict_pairs[k].allocno2
1348                     && ialloc == no_conflict_pairs[k].allocno1)))
1349 #endif /* 0 */
1350               conflicts[ialloc_prod + j] |= allocnos_live[j];
1351         }
1352     }
1353 }
1354
1355 /* Record all allocnos currently live as conflicting
1356    with all hard regs currently live.
1357
1358    ALLOCNO_VEC is a vector of LEN allocnos, all allocnos that
1359    are currently live.  Their bits are also flagged in allocnos_live.  */
1360
1361 static void
1362 record_conflicts (allocno_vec, len)
1363      int *allocno_vec;
1364      int len;
1365 {
1366   int num;
1367   int ialloc_prod;
1368
1369   while (--len >= 0)
1370     {
1371       num = allocno_vec[len];
1372       ialloc_prod = num * allocno_row_words;
1373       IOR_HARD_REG_SET (allocno[num].hard_reg_conflicts, hard_regs_live);
1374     }
1375 }
1376
1377 /* If CONFLICTP (i, j) is true, make sure CONFLICTP (j, i) is also true.  */
1378 static void
1379 mirror_conflicts ()
1380 {
1381   int i, j;
1382   int rw = allocno_row_words;
1383   int rwb = rw * INT_BITS;
1384   INT_TYPE *p = conflicts;
1385   INT_TYPE *q0 = conflicts, *q1, *q2;
1386   unsigned INT_TYPE mask;
1387
1388   for (i = max_allocno - 1, mask = 1; i >= 0; i--, mask <<= 1)
1389     {
1390       if (! mask)
1391         {
1392           mask = 1;
1393           q0++;
1394         }
1395       for (j = allocno_row_words - 1, q1 = q0; j >= 0; j--, q1 += rwb)
1396         {
1397           unsigned INT_TYPE word;
1398
1399           for (word = (unsigned INT_TYPE) *p++, q2 = q1; word;
1400                word >>= 1, q2 += rw)
1401             {
1402               if (word & 1)
1403                 *q2 |= mask;
1404             }
1405         }
1406     }
1407 }
1408 \f
1409 /* Handle the case where REG is set by the insn being scanned,
1410    during the forward scan to accumulate conflicts.
1411    Store a 1 in regs_live or allocnos_live for this register, record how many
1412    consecutive hardware registers it actually needs,
1413    and record a conflict with all other registers already live.
1414
1415    Note that even if REG does not remain alive after this insn,
1416    we must mark it here as live, to ensure a conflict between
1417    REG and any other regs set in this insn that really do live.
1418    This is because those other regs could be considered after this.
1419
1420    REG might actually be something other than a register;
1421    if so, we do nothing.
1422
1423    SETTER is 0 if this register was modified by an auto-increment (i.e.,
1424    a REG_INC note was found for it).  */
1425
1426 static void
1427 mark_reg_store (reg, setter, data)
1428      rtx reg, setter;
1429      void *data ATTRIBUTE_UNUSED;
1430 {
1431   int regno;
1432
1433   if (GET_CODE (reg) == SUBREG)
1434     reg = SUBREG_REG (reg);
1435
1436   if (GET_CODE (reg) != REG)
1437     return;
1438
1439   regs_set[n_regs_set++] = reg;
1440
1441   if (setter && GET_CODE (setter) != CLOBBER)
1442     set_preference (reg, SET_SRC (setter));
1443
1444   regno = REGNO (reg);
1445
1446   /* Either this is one of the max_allocno pseudo regs not allocated,
1447      or it is or has a hardware reg.  First handle the pseudo-regs.  */
1448   if (regno >= FIRST_PSEUDO_REGISTER)
1449     {
1450       if (reg_allocno[regno] >= 0)
1451         {
1452           SET_ALLOCNO_LIVE (reg_allocno[regno]);
1453           record_one_conflict (regno);
1454         }
1455     }
1456
1457   if (reg_renumber[regno] >= 0)
1458     regno = reg_renumber[regno];
1459
1460   /* Handle hardware regs (and pseudos allocated to hard regs).  */
1461   if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1462     {
1463       int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1464       while (regno < last)
1465         {
1466           record_one_conflict (regno);
1467           SET_HARD_REG_BIT (hard_regs_live, regno);
1468           regno++;
1469         }
1470     }
1471 }
1472 \f
1473 /* Like mark_reg_set except notice just CLOBBERs; ignore SETs.  */
1474
1475 static void
1476 mark_reg_clobber (reg, setter, data)
1477      rtx reg, setter;
1478      void *data ATTRIBUTE_UNUSED;
1479 {
1480   if (GET_CODE (setter) == CLOBBER)
1481     mark_reg_store (reg, setter, data);
1482 }
1483
1484 /* Record that REG has conflicts with all the regs currently live.
1485    Do not mark REG itself as live.  */
1486
1487 static void
1488 mark_reg_conflicts (reg)
1489      rtx reg;
1490 {
1491   int regno;
1492
1493   if (GET_CODE (reg) == SUBREG)
1494     reg = SUBREG_REG (reg);
1495
1496   if (GET_CODE (reg) != REG)
1497     return;
1498
1499   regno = REGNO (reg);
1500
1501   /* Either this is one of the max_allocno pseudo regs not allocated,
1502      or it is or has a hardware reg.  First handle the pseudo-regs.  */
1503   if (regno >= FIRST_PSEUDO_REGISTER)
1504     {
1505       if (reg_allocno[regno] >= 0)
1506         record_one_conflict (regno);
1507     }
1508
1509   if (reg_renumber[regno] >= 0)
1510     regno = reg_renumber[regno];
1511
1512   /* Handle hardware regs (and pseudos allocated to hard regs).  */
1513   if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1514     {
1515       int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1516       while (regno < last)
1517         {
1518           record_one_conflict (regno);
1519           regno++;
1520         }
1521     }
1522 }
1523 \f
1524 /* Mark REG as being dead (following the insn being scanned now).
1525    Store a 0 in regs_live or allocnos_live for this register.  */
1526
1527 static void
1528 mark_reg_death (reg)
1529      rtx reg;
1530 {
1531   int regno = REGNO (reg);
1532
1533   /* Either this is one of the max_allocno pseudo regs not allocated,
1534      or it is a hardware reg.  First handle the pseudo-regs.  */
1535   if (regno >= FIRST_PSEUDO_REGISTER)
1536     {
1537       if (reg_allocno[regno] >= 0)
1538         CLEAR_ALLOCNO_LIVE (reg_allocno[regno]);
1539     }
1540
1541   /* For pseudo reg, see if it has been assigned a hardware reg.  */
1542   if (reg_renumber[regno] >= 0)
1543     regno = reg_renumber[regno];
1544
1545   /* Handle hardware regs (and pseudos allocated to hard regs).  */
1546   if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
1547     {
1548       /* Pseudo regs already assigned hardware regs are treated
1549          almost the same as explicit hardware regs.  */
1550       int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
1551       while (regno < last)
1552         {
1553           CLEAR_HARD_REG_BIT (hard_regs_live, regno);
1554           regno++;
1555         }
1556     }
1557 }
1558
1559 /* Mark hard reg REGNO as currently live, assuming machine mode MODE
1560    for the value stored in it.  MODE determines how many consecutive
1561    registers are actually in use.  Do not record conflicts;
1562    it is assumed that the caller will do that.  */
1563
1564 static void
1565 mark_reg_live_nc (regno, mode)
1566      int regno;
1567      enum machine_mode mode;
1568 {
1569   int last = regno + HARD_REGNO_NREGS (regno, mode);
1570   while (regno < last)
1571     {
1572       SET_HARD_REG_BIT (hard_regs_live, regno);
1573       regno++;
1574     }
1575 }
1576 \f
1577 /* Try to set a preference for an allocno to a hard register.
1578    We are passed DEST and SRC which are the operands of a SET.  It is known
1579    that SRC is a register.  If SRC or the first operand of SRC is a register,
1580    try to set a preference.  If one of the two is a hard register and the other
1581    is a pseudo-register, mark the preference.
1582
1583    Note that we are not as aggressive as local-alloc in trying to tie a
1584    pseudo-register to a hard register.  */
1585
1586 static void
1587 set_preference (dest, src)
1588      rtx dest, src;
1589 {
1590   unsigned int src_regno, dest_regno;
1591   /* Amount to add to the hard regno for SRC, or subtract from that for DEST,
1592      to compensate for subregs in SRC or DEST.  */
1593   int offset = 0;
1594   unsigned int i;
1595   int copy = 1;
1596
1597   if (GET_RTX_FORMAT (GET_CODE (src))[0] == 'e')
1598     src = XEXP (src, 0), copy = 0;
1599
1600   /* Get the reg number for both SRC and DEST.
1601      If neither is a reg, give up.  */
1602
1603   if (GET_CODE (src) == REG)
1604     src_regno = REGNO (src);
1605   else if (GET_CODE (src) == SUBREG && GET_CODE (SUBREG_REG (src)) == REG)
1606     {
1607       src_regno = REGNO (SUBREG_REG (src));
1608
1609       if (REGNO (SUBREG_REG (src)) < FIRST_PSEUDO_REGISTER)
1610         offset += subreg_regno_offset (REGNO (SUBREG_REG (src)),
1611                                        GET_MODE (SUBREG_REG (src)),
1612                                        SUBREG_BYTE (src),
1613                                        GET_MODE (src));
1614       else
1615         offset += (SUBREG_BYTE (src)
1616                    / REGMODE_NATURAL_SIZE (GET_MODE (src)));
1617     }
1618   else
1619     return;
1620
1621   if (GET_CODE (dest) == REG)
1622     dest_regno = REGNO (dest);
1623   else if (GET_CODE (dest) == SUBREG && GET_CODE (SUBREG_REG (dest)) == REG)
1624     {
1625       dest_regno = REGNO (SUBREG_REG (dest));
1626
1627       if (REGNO (SUBREG_REG (dest)) < FIRST_PSEUDO_REGISTER)
1628         offset -= subreg_regno_offset (REGNO (SUBREG_REG (dest)),
1629                                        GET_MODE (SUBREG_REG (dest)),
1630                                        SUBREG_BYTE (dest),
1631                                        GET_MODE (dest));
1632       else
1633         offset -= (SUBREG_BYTE (dest)
1634                    / REGMODE_NATURAL_SIZE (GET_MODE (dest)));
1635     }
1636   else
1637     return;
1638
1639   /* Convert either or both to hard reg numbers.  */
1640
1641   if (reg_renumber[src_regno] >= 0)
1642     src_regno = reg_renumber[src_regno];
1643
1644   if (reg_renumber[dest_regno] >= 0)
1645     dest_regno = reg_renumber[dest_regno];
1646
1647   /* Now if one is a hard reg and the other is a global pseudo
1648      then give the other a preference.  */
1649
1650   if (dest_regno < FIRST_PSEUDO_REGISTER && src_regno >= FIRST_PSEUDO_REGISTER
1651       && reg_allocno[src_regno] >= 0)
1652     {
1653       dest_regno -= offset;
1654       if (dest_regno < FIRST_PSEUDO_REGISTER)
1655         {
1656           if (copy)
1657             SET_REGBIT (hard_reg_copy_preferences,
1658                         reg_allocno[src_regno], dest_regno);
1659
1660           SET_REGBIT (hard_reg_preferences,
1661                       reg_allocno[src_regno], dest_regno);
1662           for (i = dest_regno;
1663                i < dest_regno + HARD_REGNO_NREGS (dest_regno, GET_MODE (dest));
1664                i++)
1665             SET_REGBIT (hard_reg_full_preferences, reg_allocno[src_regno], i);
1666         }
1667     }
1668
1669   if (src_regno < FIRST_PSEUDO_REGISTER && dest_regno >= FIRST_PSEUDO_REGISTER
1670       && reg_allocno[dest_regno] >= 0)
1671     {
1672       src_regno += offset;
1673       if (src_regno < FIRST_PSEUDO_REGISTER)
1674         {
1675           if (copy)
1676             SET_REGBIT (hard_reg_copy_preferences,
1677                         reg_allocno[dest_regno], src_regno);
1678
1679           SET_REGBIT (hard_reg_preferences,
1680                       reg_allocno[dest_regno], src_regno);
1681           for (i = src_regno;
1682                i < src_regno + HARD_REGNO_NREGS (src_regno, GET_MODE (src));
1683                i++)
1684             SET_REGBIT (hard_reg_full_preferences, reg_allocno[dest_regno], i);
1685         }
1686     }
1687 }
1688 \f
1689 /* Indicate that hard register number FROM was eliminated and replaced with
1690    an offset from hard register number TO.  The status of hard registers live
1691    at the start of a basic block is updated by replacing a use of FROM with
1692    a use of TO.  */
1693
1694 void
1695 mark_elimination (from, to)
1696      int from, to;
1697 {
1698   basic_block bb;
1699
1700   FOR_EACH_BB (bb)
1701     {
1702       regset r = bb->global_live_at_start;
1703       if (REGNO_REG_SET_P (r, from))
1704         {
1705           CLEAR_REGNO_REG_SET (r, from);
1706           SET_REGNO_REG_SET (r, to);
1707         }
1708     }
1709 }
1710 \f
1711 /* Used for communication between the following functions.  Holds the
1712    current life information.  */
1713 static regset live_relevant_regs;
1714
1715 /* Record in live_relevant_regs and REGS_SET that register REG became live.
1716    This is called via note_stores.  */
1717 static void
1718 reg_becomes_live (reg, setter, regs_set)
1719      rtx reg;
1720      rtx setter ATTRIBUTE_UNUSED;
1721      void *regs_set;
1722 {
1723   int regno;
1724
1725   if (GET_CODE (reg) == SUBREG)
1726     reg = SUBREG_REG (reg);
1727
1728   if (GET_CODE (reg) != REG)
1729     return;
1730
1731   regno = REGNO (reg);
1732   if (regno < FIRST_PSEUDO_REGISTER)
1733     {
1734       int nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg));
1735       while (nregs-- > 0)
1736         {
1737           SET_REGNO_REG_SET (live_relevant_regs, regno);
1738           if (! fixed_regs[regno])
1739             SET_REGNO_REG_SET ((regset) regs_set, regno);
1740           regno++;
1741         }
1742     }
1743   else if (reg_renumber[regno] >= 0)
1744     {
1745       SET_REGNO_REG_SET (live_relevant_regs, regno);
1746       SET_REGNO_REG_SET ((regset) regs_set, regno);
1747     }
1748 }
1749
1750 /* Record in live_relevant_regs that register REGNO died.  */
1751 static void
1752 reg_dies (regno, mode, chain)
1753      int regno;
1754      enum machine_mode mode;
1755      struct insn_chain *chain;
1756 {
1757   if (regno < FIRST_PSEUDO_REGISTER)
1758     {
1759       int nregs = HARD_REGNO_NREGS (regno, mode);
1760       while (nregs-- > 0)
1761         {
1762           CLEAR_REGNO_REG_SET (live_relevant_regs, regno);
1763           if (! fixed_regs[regno])
1764             SET_REGNO_REG_SET (&chain->dead_or_set, regno);
1765           regno++;
1766         }
1767     }
1768   else
1769     {
1770       CLEAR_REGNO_REG_SET (live_relevant_regs, regno);
1771       if (reg_renumber[regno] >= 0)
1772         SET_REGNO_REG_SET (&chain->dead_or_set, regno);
1773     }
1774 }
1775
1776 /* Walk the insns of the current function and build reload_insn_chain,
1777    and record register life information.  */
1778 void
1779 build_insn_chain (first)
1780      rtx first;
1781 {
1782   struct insn_chain **p = &reload_insn_chain;
1783   struct insn_chain *prev = 0;
1784   basic_block b = ENTRY_BLOCK_PTR->next_bb;
1785   regset_head live_relevant_regs_head;
1786
1787   live_relevant_regs = INITIALIZE_REG_SET (live_relevant_regs_head);
1788
1789   for (; first; first = NEXT_INSN (first))
1790     {
1791       struct insn_chain *c;
1792
1793       if (first == b->head)
1794         {
1795           int i;
1796
1797           CLEAR_REG_SET (live_relevant_regs);
1798
1799           EXECUTE_IF_SET_IN_BITMAP
1800             (b->global_live_at_start, 0, i,
1801              {
1802                if (i < FIRST_PSEUDO_REGISTER
1803                    ? ! TEST_HARD_REG_BIT (eliminable_regset, i)
1804                    : reg_renumber[i] >= 0)
1805                  SET_REGNO_REG_SET (live_relevant_regs, i);
1806              });
1807         }
1808
1809       if (GET_CODE (first) != NOTE && GET_CODE (first) != BARRIER)
1810         {
1811           c = new_insn_chain ();
1812           c->prev = prev;
1813           prev = c;
1814           *p = c;
1815           p = &c->next;
1816           c->insn = first;
1817           c->block = b->index;
1818
1819           if (INSN_P (first))
1820             {
1821               rtx link;
1822
1823               /* Mark the death of everything that dies in this instruction.  */
1824
1825               for (link = REG_NOTES (first); link; link = XEXP (link, 1))
1826                 if (REG_NOTE_KIND (link) == REG_DEAD
1827                     && GET_CODE (XEXP (link, 0)) == REG)
1828                   reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)),
1829                             c);
1830
1831               COPY_REG_SET (&c->live_throughout, live_relevant_regs);
1832
1833               /* Mark everything born in this instruction as live.  */
1834
1835               note_stores (PATTERN (first), reg_becomes_live,
1836                            &c->dead_or_set);
1837             }
1838           else
1839             COPY_REG_SET (&c->live_throughout, live_relevant_regs);
1840
1841           if (INSN_P (first))
1842             {
1843               rtx link;
1844
1845               /* Mark anything that is set in this insn and then unused as dying.  */
1846
1847               for (link = REG_NOTES (first); link; link = XEXP (link, 1))
1848                 if (REG_NOTE_KIND (link) == REG_UNUSED
1849                     && GET_CODE (XEXP (link, 0)) == REG)
1850                   reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)),
1851                             c);
1852             }
1853         }
1854
1855       if (first == b->end)
1856         b = b->next_bb;
1857
1858       /* Stop after we pass the end of the last basic block.  Verify that
1859          no real insns are after the end of the last basic block.
1860
1861          We may want to reorganize the loop somewhat since this test should
1862          always be the right exit test.  Allow an ADDR_VEC or ADDR_DIF_VEC if
1863          the previous real insn is a JUMP_INSN.  */
1864       if (b == EXIT_BLOCK_PTR)
1865         {
1866           for (first = NEXT_INSN (first) ; first; first = NEXT_INSN (first))
1867             if (INSN_P (first)
1868                 && GET_CODE (PATTERN (first)) != USE
1869                 && ! ((GET_CODE (PATTERN (first)) == ADDR_VEC
1870                        || GET_CODE (PATTERN (first)) == ADDR_DIFF_VEC)
1871                       && prev_real_insn (first) != 0
1872                       && GET_CODE (prev_real_insn (first)) == JUMP_INSN))
1873               abort ();
1874           break;
1875         }
1876     }
1877   FREE_REG_SET (live_relevant_regs);
1878   *p = 0;
1879 }
1880 \f
1881 /* Print debugging trace information if -dg switch is given,
1882    showing the information on which the allocation decisions are based.  */
1883
1884 static void
1885 dump_conflicts (file)
1886      FILE *file;
1887 {
1888   int i;
1889   int has_preferences;
1890   int nregs;
1891   nregs = 0;
1892   for (i = 0; i < max_allocno; i++)
1893     {
1894       if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
1895         continue;
1896       nregs++;
1897     }
1898   fprintf (file, ";; %d regs to allocate:", nregs);
1899   for (i = 0; i < max_allocno; i++)
1900     {
1901       int j;
1902       if (reg_renumber[allocno[allocno_order[i]].reg] >= 0)
1903         continue;
1904       fprintf (file, " %d", allocno[allocno_order[i]].reg);
1905       for (j = 0; j < max_regno; j++)
1906         if (reg_allocno[j] == allocno_order[i]
1907             && j != allocno[allocno_order[i]].reg)
1908           fprintf (file, "+%d", j);
1909       if (allocno[allocno_order[i]].size != 1)
1910         fprintf (file, " (%d)", allocno[allocno_order[i]].size);
1911     }
1912   fprintf (file, "\n");
1913
1914   for (i = 0; i < max_allocno; i++)
1915     {
1916       int j;
1917       fprintf (file, ";; %d conflicts:", allocno[i].reg);
1918       for (j = 0; j < max_allocno; j++)
1919         if (CONFLICTP (j, i))
1920           fprintf (file, " %d", allocno[j].reg);
1921       for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1922         if (TEST_HARD_REG_BIT (allocno[i].hard_reg_conflicts, j))
1923           fprintf (file, " %d", j);
1924       fprintf (file, "\n");
1925
1926       has_preferences = 0;
1927       for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1928         if (TEST_HARD_REG_BIT (allocno[i].hard_reg_preferences, j))
1929           has_preferences = 1;
1930
1931       if (! has_preferences)
1932         continue;
1933       fprintf (file, ";; %d preferences:", allocno[i].reg);
1934       for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1935         if (TEST_HARD_REG_BIT (allocno[i].hard_reg_preferences, j))
1936           fprintf (file, " %d", j);
1937       fprintf (file, "\n");
1938     }
1939   fprintf (file, "\n");
1940 }
1941
1942 void
1943 dump_global_regs (file)
1944      FILE *file;
1945 {
1946   int i, j;
1947
1948   fprintf (file, ";; Register dispositions:\n");
1949   for (i = FIRST_PSEUDO_REGISTER, j = 0; i < max_regno; i++)
1950     if (reg_renumber[i] >= 0)
1951       {
1952         fprintf (file, "%d in %d  ", i, reg_renumber[i]);
1953         if (++j % 6 == 0)
1954           fprintf (file, "\n");
1955       }
1956
1957   fprintf (file, "\n\n;; Hard regs used: ");
1958   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1959     if (regs_ever_live[i])
1960       fprintf (file, " %d", i);
1961   fprintf (file, "\n\n");
1962 }