OSDN Git Service

Don't assume a SUBREG can not conflict with a MEM
[pf3gnuchains/gcc-fork.git] / gcc / reload1.c
1 /* Reload pseudo regs into hard regs for insns that require hard regs.
2    Copyright (C) 1987, 88, 89, 92-6, 1997 Free Software Foundation, Inc.
3
4 This file is part of GNU CC.
5
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
9 any later version.
10
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING.  If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA.  */
20
21
22 #include <stdio.h>
23 #include "config.h"
24 #include "rtl.h"
25 #include "obstack.h"
26 #include "insn-config.h"
27 #include "insn-flags.h"
28 #include "insn-codes.h"
29 #include "flags.h"
30 #include "expr.h"
31 #include "regs.h"
32 #include "hard-reg-set.h"
33 #include "reload.h"
34 #include "recog.h"
35 #include "basic-block.h"
36 #include "output.h"
37 #include "real.h"
38
39 /* This file contains the reload pass of the compiler, which is
40    run after register allocation has been done.  It checks that
41    each insn is valid (operands required to be in registers really
42    are in registers of the proper class) and fixes up invalid ones
43    by copying values temporarily into registers for the insns
44    that need them.
45
46    The results of register allocation are described by the vector
47    reg_renumber; the insns still contain pseudo regs, but reg_renumber
48    can be used to find which hard reg, if any, a pseudo reg is in.
49
50    The technique we always use is to free up a few hard regs that are
51    called ``reload regs'', and for each place where a pseudo reg
52    must be in a hard reg, copy it temporarily into one of the reload regs.
53
54    All the pseudos that were formerly allocated to the hard regs that
55    are now in use as reload regs must be ``spilled''.  This means
56    that they go to other hard regs, or to stack slots if no other
57    available hard regs can be found.  Spilling can invalidate more
58    insns, requiring additional need for reloads, so we must keep checking
59    until the process stabilizes.
60
61    For machines with different classes of registers, we must keep track
62    of the register class needed for each reload, and make sure that
63    we allocate enough reload registers of each class.
64
65    The file reload.c contains the code that checks one insn for
66    validity and reports the reloads that it needs.  This file
67    is in charge of scanning the entire rtl code, accumulating the
68    reload needs, spilling, assigning reload registers to use for
69    fixing up each insn, and generating the new insns to copy values
70    into the reload registers.  */
71
72
73 #ifndef REGISTER_MOVE_COST
74 #define REGISTER_MOVE_COST(x, y) 2
75 #endif
76
77 #ifndef MEMORY_MOVE_COST
78 #define MEMORY_MOVE_COST(x) 4
79 #endif
80 \f
81 /* During reload_as_needed, element N contains a REG rtx for the hard reg
82    into which reg N has been reloaded (perhaps for a previous insn).  */
83 static rtx *reg_last_reload_reg;
84
85 /* Elt N nonzero if reg_last_reload_reg[N] has been set in this insn
86    for an output reload that stores into reg N.  */
87 static char *reg_has_output_reload;
88
89 /* Indicates which hard regs are reload-registers for an output reload
90    in the current insn.  */
91 static HARD_REG_SET reg_is_output_reload;
92
93 /* Element N is the constant value to which pseudo reg N is equivalent,
94    or zero if pseudo reg N is not equivalent to a constant.
95    find_reloads looks at this in order to replace pseudo reg N
96    with the constant it stands for.  */
97 rtx *reg_equiv_constant;
98
99 /* Element N is a memory location to which pseudo reg N is equivalent,
100    prior to any register elimination (such as frame pointer to stack
101    pointer).  Depending on whether or not it is a valid address, this value
102    is transferred to either reg_equiv_address or reg_equiv_mem.  */
103 rtx *reg_equiv_memory_loc;
104
105 /* Element N is the address of stack slot to which pseudo reg N is equivalent.
106    This is used when the address is not valid as a memory address
107    (because its displacement is too big for the machine.)  */
108 rtx *reg_equiv_address;
109
110 /* Element N is the memory slot to which pseudo reg N is equivalent,
111    or zero if pseudo reg N is not equivalent to a memory slot.  */
112 rtx *reg_equiv_mem;
113
114 /* Widest width in which each pseudo reg is referred to (via subreg).  */
115 static int *reg_max_ref_width;
116
117 /* Element N is the insn that initialized reg N from its equivalent
118    constant or memory slot.  */
119 static rtx *reg_equiv_init;
120
121 /* During reload_as_needed, element N contains the last pseudo regno
122    reloaded into the Nth reload register.  This vector is in parallel
123    with spill_regs.  If that pseudo reg occupied more than one register,
124    reg_reloaded_contents points to that pseudo for each spill register in
125    use; all of these must remain set for an inheritance to occur.  */
126 static int reg_reloaded_contents[FIRST_PSEUDO_REGISTER];
127
128 /* During reload_as_needed, element N contains the insn for which
129    the Nth reload register was last used.  This vector is in parallel
130    with spill_regs, and its contents are significant only when
131    reg_reloaded_contents is significant.  */
132 static rtx reg_reloaded_insn[FIRST_PSEUDO_REGISTER];
133
134 /* Number of spill-regs so far; number of valid elements of spill_regs.  */
135 static int n_spills;
136
137 /* In parallel with spill_regs, contains REG rtx's for those regs.
138    Holds the last rtx used for any given reg, or 0 if it has never
139    been used for spilling yet.  This rtx is reused, provided it has
140    the proper mode.  */
141 static rtx spill_reg_rtx[FIRST_PSEUDO_REGISTER];
142
143 /* In parallel with spill_regs, contains nonzero for a spill reg
144    that was stored after the last time it was used.
145    The precise value is the insn generated to do the store.  */
146 static rtx spill_reg_store[FIRST_PSEUDO_REGISTER];
147
148 /* This table is the inverse mapping of spill_regs:
149    indexed by hard reg number,
150    it contains the position of that reg in spill_regs,
151    or -1 for something that is not in spill_regs.  */
152 static short spill_reg_order[FIRST_PSEUDO_REGISTER];
153
154 /* This reg set indicates registers that may not be used for retrying global
155    allocation.  The registers that may not be used include all spill registers
156    and the frame pointer (if we are using one).  */
157 HARD_REG_SET forbidden_regs;
158
159 /* This reg set indicates registers that are not good for spill registers.
160    They will not be used to complete groups of spill registers.  This includes
161    all fixed registers, registers that may be eliminated, and, if
162    SMALL_REGISTER_CLASSES is not defined, registers explicitly used in the rtl.
163
164    (spill_reg_order prevents these registers from being used to start a
165    group.)  */
166 static HARD_REG_SET bad_spill_regs;
167
168 /* Describes order of use of registers for reloading
169    of spilled pseudo-registers.  `spills' is the number of
170    elements that are actually valid; new ones are added at the end.  */
171 static short spill_regs[FIRST_PSEUDO_REGISTER];
172
173 /* This reg set indicates those registers that have been used a spill
174    registers.  This information is used in reorg.c, to help figure out
175    what registers are live at any point.  It is assumed that all spill_regs
176    are dead at every CODE_LABEL.  */
177
178 HARD_REG_SET used_spill_regs;
179
180 /* Index of last register assigned as a spill register.  We allocate in
181    a round-robin fashion.  */
182
183 static int last_spill_reg;
184
185 /* Describes order of preference for putting regs into spill_regs.
186    Contains the numbers of all the hard regs, in order most preferred first.
187    This order is different for each function.
188    It is set up by order_regs_for_reload.
189    Empty elements at the end contain -1.  */
190 static short potential_reload_regs[FIRST_PSEUDO_REGISTER];
191
192 /* 1 for a hard register that appears explicitly in the rtl
193    (for example, function value registers, special registers
194    used by insns, structure value pointer registers).  */
195 static char regs_explicitly_used[FIRST_PSEUDO_REGISTER];
196
197 /* Indicates if a register was counted against the need for
198    groups.  0 means it can count against max_nongroup instead.  */
199 static HARD_REG_SET counted_for_groups;
200
201 /* Indicates if a register was counted against the need for
202    non-groups.  0 means it can become part of a new group.
203    During choose_reload_regs, 1 here means don't use this reg
204    as part of a group, even if it seems to be otherwise ok.  */
205 static HARD_REG_SET counted_for_nongroups;
206
207 /* Indexed by pseudo reg number N,
208    says may not delete stores into the real (memory) home of pseudo N.
209    This is set if we already substituted a memory equivalent in some uses,
210    which happens when we have to eliminate the fp from it.  */
211 static char *cannot_omit_stores;
212
213 /* Nonzero if indirect addressing is supported on the machine; this means
214    that spilling (REG n) does not require reloading it into a register in
215    order to do (MEM (REG n)) or (MEM (PLUS (REG n) (CONST_INT c))).  The
216    value indicates the level of indirect addressing supported, e.g., two
217    means that (MEM (MEM (REG n))) is also valid if (REG n) does not get
218    a hard register.  */
219
220 static char spill_indirect_levels;
221
222 /* Nonzero if indirect addressing is supported when the innermost MEM is
223    of the form (MEM (SYMBOL_REF sym)).  It is assumed that the level to
224    which these are valid is the same as spill_indirect_levels, above.   */
225
226 char indirect_symref_ok;
227
228 /* Nonzero if an address (plus (reg frame_pointer) (reg ...)) is valid.  */
229
230 char double_reg_address_ok;
231
232 /* Record the stack slot for each spilled hard register.  */
233
234 static rtx spill_stack_slot[FIRST_PSEUDO_REGISTER];
235
236 /* Width allocated so far for that stack slot.  */
237
238 static int spill_stack_slot_width[FIRST_PSEUDO_REGISTER];
239
240 /* Indexed by register class and basic block number, nonzero if there is
241    any need for a spill register of that class in that basic block.
242    The pointer is 0 if we did stupid allocation and don't know
243    the structure of basic blocks.  */
244
245 char *basic_block_needs[N_REG_CLASSES];
246
247 /* First uid used by insns created by reload in this function.
248    Used in find_equiv_reg.  */
249 int reload_first_uid;
250
251 /* Flag set by local-alloc or global-alloc if anything is live in
252    a call-clobbered reg across calls.  */
253
254 int caller_save_needed;
255
256 /* The register class to use for a base register when reloading an
257    address.  This is normally BASE_REG_CLASS, but it may be different
258    when using SMALL_REGISTER_CLASSES and passing parameters in
259    registers.  */
260 enum reg_class reload_address_base_reg_class;
261
262 /* The register class to use for an index register when reloading an
263    address.  This is normally INDEX_REG_CLASS, but it may be different
264    when using SMALL_REGISTER_CLASSES and passing parameters in
265    registers.  */
266 enum reg_class reload_address_index_reg_class;
267
268 /* Set to 1 while reload_as_needed is operating.
269    Required by some machines to handle any generated moves differently.  */
270
271 int reload_in_progress = 0;
272
273 /* These arrays record the insn_code of insns that may be needed to
274    perform input and output reloads of special objects.  They provide a
275    place to pass a scratch register.  */
276
277 enum insn_code reload_in_optab[NUM_MACHINE_MODES];
278 enum insn_code reload_out_optab[NUM_MACHINE_MODES];
279
280 /* This obstack is used for allocation of rtl during register elimination.
281    The allocated storage can be freed once find_reloads has processed the
282    insn.  */
283
284 struct obstack reload_obstack;
285 char *reload_firstobj;
286
287 #define obstack_chunk_alloc xmalloc
288 #define obstack_chunk_free free
289
290 /* List of labels that must never be deleted.  */
291 extern rtx forced_labels;
292
293 /* Allocation number table from global register allocation.  */
294 extern int *reg_allocno;
295 \f
296 /* This structure is used to record information about register eliminations.
297    Each array entry describes one possible way of eliminating a register
298    in favor of another.   If there is more than one way of eliminating a
299    particular register, the most preferred should be specified first.  */
300
301 static struct elim_table
302 {
303   int from;                     /* Register number to be eliminated.  */
304   int to;                       /* Register number used as replacement.  */
305   int initial_offset;           /* Initial difference between values.  */
306   int can_eliminate;            /* Non-zero if this elimination can be done.  */
307   int can_eliminate_previous;   /* Value of CAN_ELIMINATE in previous scan over
308                                    insns made by reload.  */
309   int offset;                   /* Current offset between the two regs.  */
310   int max_offset;               /* Maximum offset between the two regs.  */
311   int previous_offset;          /* Offset at end of previous insn.  */
312   int ref_outside_mem;          /* "to" has been referenced outside a MEM.  */
313   rtx from_rtx;                 /* REG rtx for the register to be eliminated.
314                                    We cannot simply compare the number since
315                                    we might then spuriously replace a hard
316                                    register corresponding to a pseudo
317                                    assigned to the reg to be eliminated.  */
318   rtx to_rtx;                   /* REG rtx for the replacement.  */
319 } reg_eliminate[] =
320
321 /* If a set of eliminable registers was specified, define the table from it.
322    Otherwise, default to the normal case of the frame pointer being
323    replaced by the stack pointer.  */
324
325 #ifdef ELIMINABLE_REGS
326   ELIMINABLE_REGS;
327 #else
328   {{ FRAME_POINTER_REGNUM, STACK_POINTER_REGNUM}};
329 #endif
330
331 #define NUM_ELIMINABLE_REGS (sizeof reg_eliminate / sizeof reg_eliminate[0])
332
333 /* Record the number of pending eliminations that have an offset not equal
334    to their initial offset.  If non-zero, we use a new copy of each
335    replacement result in any insns encountered.  */
336 static int num_not_at_initial_offset;
337
338 /* Count the number of registers that we may be able to eliminate.  */
339 static int num_eliminable;
340
341 /* For each label, we record the offset of each elimination.  If we reach
342    a label by more than one path and an offset differs, we cannot do the
343    elimination.  This information is indexed by the number of the label.
344    The first table is an array of flags that records whether we have yet
345    encountered a label and the second table is an array of arrays, one
346    entry in the latter array for each elimination.  */
347
348 static char *offsets_known_at;
349 static int (*offsets_at)[NUM_ELIMINABLE_REGS];
350
351 /* Number of labels in the current function.  */
352
353 static int num_labels;
354
355 struct hard_reg_n_uses { int regno; int uses; };
356 \f
357 static int possible_group_p             PROTO((int, int *));
358 static void count_possible_groups       PROTO((int *, enum machine_mode *,
359                                                int *, int));
360 static int modes_equiv_for_class_p      PROTO((enum machine_mode,
361                                                enum machine_mode,
362                                                enum reg_class));
363 static void spill_failure               PROTO((rtx));
364 static int new_spill_reg                PROTO((int, int, int *, int *, int,
365                                                FILE *));
366 static void delete_dead_insn            PROTO((rtx));
367 static void alter_reg                   PROTO((int, int));
368 static void mark_scratch_live           PROTO((rtx));
369 static void set_label_offsets           PROTO((rtx, rtx, int));
370 static int eliminate_regs_in_insn       PROTO((rtx, int));
371 static void mark_not_eliminable         PROTO((rtx, rtx));
372 static int spill_hard_reg               PROTO((int, int, FILE *, int));
373 static void scan_paradoxical_subregs    PROTO((rtx));
374 static int hard_reg_use_compare         PROTO((const GENERIC_PTR, const GENERIC_PTR));
375 static void order_regs_for_reload       PROTO((int));
376 static int compare_spill_regs           PROTO((const GENERIC_PTR, const GENERIC_PTR));
377 static void reload_as_needed            PROTO((rtx, int));
378 static void forget_old_reloads_1        PROTO((rtx, rtx));
379 static int reload_reg_class_lower       PROTO((const GENERIC_PTR, const GENERIC_PTR));
380 static void mark_reload_reg_in_use      PROTO((int, int, enum reload_type,
381                                                enum machine_mode));
382 static void clear_reload_reg_in_use     PROTO((int, int, enum reload_type,
383                                                enum machine_mode));
384 static int reload_reg_free_p            PROTO((int, int, enum reload_type));
385 static int reload_reg_free_before_p     PROTO((int, int, enum reload_type));
386 static int reload_reg_reaches_end_p     PROTO((int, int, enum reload_type));
387 static int reloads_conflict             PROTO((int, int));
388 static int allocate_reload_reg          PROTO((int, rtx, int, int));
389 static void choose_reload_regs          PROTO((rtx, rtx));
390 static void merge_assigned_reloads      PROTO((rtx));
391 static void emit_reload_insns           PROTO((rtx));
392 static void delete_output_reload        PROTO((rtx, int, rtx));
393 static void inc_for_reload              PROTO((rtx, rtx, int));
394 static int constraint_accepts_reg_p     PROTO((char *, rtx));
395 static int count_occurrences            PROTO((rtx, rtx));
396 static void reload_cse_invalidate_regno PROTO((int, enum machine_mode, int));
397 static int reload_cse_mem_conflict_p    PROTO((rtx, rtx, enum machine_mode,
398                                                rtx));
399 static void reload_cse_invalidate_mem   PROTO((rtx));
400 static void reload_cse_invalidate_rtx   PROTO((rtx, rtx));
401 static void reload_cse_regs             PROTO((rtx));
402 static int reload_cse_regno_equal_p     PROTO((int, rtx, enum machine_mode));
403 static int reload_cse_noop_set_p        PROTO((rtx, rtx));
404 static void reload_cse_simplify_set     PROTO((rtx, rtx));
405 static void reload_cse_check_clobber    PROTO((rtx, rtx));
406 static void reload_cse_record_set       PROTO((rtx, rtx));
407 \f
408 /* Initialize the reload pass once per compilation.  */
409
410 void
411 init_reload ()
412 {
413   register int i;
414
415   /* Often (MEM (REG n)) is still valid even if (REG n) is put on the stack.
416      Set spill_indirect_levels to the number of levels such addressing is
417      permitted, zero if it is not permitted at all.  */
418
419   register rtx tem
420     = gen_rtx (MEM, Pmode,
421                gen_rtx (PLUS, Pmode,
422                         gen_rtx (REG, Pmode, LAST_VIRTUAL_REGISTER + 1),
423                         GEN_INT (4)));
424   spill_indirect_levels = 0;
425
426   while (memory_address_p (QImode, tem))
427     {
428       spill_indirect_levels++;
429       tem = gen_rtx (MEM, Pmode, tem);
430     }
431
432   /* See if indirect addressing is valid for (MEM (SYMBOL_REF ...)).  */
433
434   tem = gen_rtx (MEM, Pmode, gen_rtx (SYMBOL_REF, Pmode, "foo"));
435   indirect_symref_ok = memory_address_p (QImode, tem);
436
437   /* See if reg+reg is a valid (and offsettable) address.  */
438
439   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
440     {
441       tem = gen_rtx (PLUS, Pmode,
442                      gen_rtx (REG, Pmode, HARD_FRAME_POINTER_REGNUM),
443                      gen_rtx (REG, Pmode, i));
444       /* This way, we make sure that reg+reg is an offsettable address.  */
445       tem = plus_constant (tem, 4);
446
447       if (memory_address_p (QImode, tem))
448         {
449           double_reg_address_ok = 1;
450           break;
451         }
452     }
453
454   /* Initialize obstack for our rtl allocation.  */
455   gcc_obstack_init (&reload_obstack);
456   reload_firstobj = (char *) obstack_alloc (&reload_obstack, 0);
457
458   /* Decide which register class should be used when reloading
459      addresses.  If we are using SMALL_REGISTER_CLASSES, and any
460      parameters are passed in registers, then we do not want to use
461      those registers when reloading an address.  Otherwise, if a
462      function argument needs a reload, we may wind up clobbering
463      another argument to the function which was already computed.  If
464      we find a subset class which simply avoids those registers, we
465      use it instead.  ??? It would be better to only use the
466      restricted class when we actually are loading function arguments,
467      but that is hard to determine.  */
468   reload_address_base_reg_class = BASE_REG_CLASS;
469   reload_address_index_reg_class = INDEX_REG_CLASS;
470 #ifdef SMALL_REGISTER_CLASSES
471   if (SMALL_REGISTER_CLASSES)
472     {
473       int regno;
474       HARD_REG_SET base, index;
475       enum reg_class *p;
476
477       COPY_HARD_REG_SET (base, reg_class_contents[BASE_REG_CLASS]);
478       COPY_HARD_REG_SET (index, reg_class_contents[INDEX_REG_CLASS]);
479       for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
480         {
481           if (FUNCTION_ARG_REGNO_P (regno))
482             {
483               CLEAR_HARD_REG_BIT (base, regno);
484               CLEAR_HARD_REG_BIT (index, regno);
485             }
486         }
487       
488       GO_IF_HARD_REG_EQUAL (base, reg_class_contents[BASE_REG_CLASS],
489                             baseok);
490       for (p = reg_class_subclasses[BASE_REG_CLASS];
491            *p != LIM_REG_CLASSES;
492            p++)
493         {
494           GO_IF_HARD_REG_EQUAL (base, reg_class_contents[*p], usebase);
495           continue;
496         usebase:
497           reload_address_base_reg_class = *p;
498           break;
499         }
500     baseok:;
501
502       GO_IF_HARD_REG_EQUAL (index, reg_class_contents[INDEX_REG_CLASS],
503                             indexok);
504       for (p = reg_class_subclasses[INDEX_REG_CLASS];
505            *p != LIM_REG_CLASSES;
506            p++)
507         {
508           GO_IF_HARD_REG_EQUAL (index, reg_class_contents[*p], useindex);
509           continue;
510         useindex:
511           reload_address_index_reg_class = *p;
512           break;
513         }
514     indexok:;
515     }
516 #endif /* SMALL_REGISTER_CLASSES */
517 }
518
519 /* Main entry point for the reload pass.
520
521    FIRST is the first insn of the function being compiled.
522
523    GLOBAL nonzero means we were called from global_alloc
524    and should attempt to reallocate any pseudoregs that we
525    displace from hard regs we will use for reloads.
526    If GLOBAL is zero, we do not have enough information to do that,
527    so any pseudo reg that is spilled must go to the stack.
528
529    DUMPFILE is the global-reg debugging dump file stream, or 0.
530    If it is nonzero, messages are written to it to describe
531    which registers are seized as reload regs, which pseudo regs
532    are spilled from them, and where the pseudo regs are reallocated to.
533
534    Return value is nonzero if reload failed
535    and we must not do any more for this function.  */
536
537 int
538 reload (first, global, dumpfile)
539      rtx first;
540      int global;
541      FILE *dumpfile;
542 {
543   register int class;
544   register int i, j, k;
545   register rtx insn;
546   register struct elim_table *ep;
547
548   int something_changed;
549   int something_needs_reloads;
550   int something_needs_elimination;
551   int new_basic_block_needs;
552   enum reg_class caller_save_spill_class = NO_REGS;
553   int caller_save_group_size = 1;
554
555   /* Nonzero means we couldn't get enough spill regs.  */
556   int failure = 0;
557
558   /* The basic block number currently being processed for INSN.  */
559   int this_block;
560
561   /* Make sure even insns with volatile mem refs are recognizable.  */
562   init_recog ();
563
564   /* Enable find_equiv_reg to distinguish insns made by reload.  */
565   reload_first_uid = get_max_uid ();
566
567   for (i = 0; i < N_REG_CLASSES; i++)
568     basic_block_needs[i] = 0;
569
570 #ifdef SECONDARY_MEMORY_NEEDED
571   /* Initialize the secondary memory table.  */
572   clear_secondary_mem ();
573 #endif
574
575   /* Remember which hard regs appear explicitly
576      before we merge into `regs_ever_live' the ones in which
577      pseudo regs have been allocated.  */
578   bcopy (regs_ever_live, regs_explicitly_used, sizeof regs_ever_live);
579
580   /* We don't have a stack slot for any spill reg yet.  */
581   bzero ((char *) spill_stack_slot, sizeof spill_stack_slot);
582   bzero ((char *) spill_stack_slot_width, sizeof spill_stack_slot_width);
583
584   /* Initialize the save area information for caller-save, in case some
585      are needed.  */
586   init_save_areas ();
587
588   /* Compute which hard registers are now in use
589      as homes for pseudo registers.
590      This is done here rather than (eg) in global_alloc
591      because this point is reached even if not optimizing.  */
592   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
593     mark_home_live (i);
594
595   /* A function that receives a nonlocal goto must save all call-saved
596      registers.  */
597   if (current_function_has_nonlocal_label)
598     for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
599       {
600         if (! call_used_regs[i] && ! fixed_regs[i])
601           regs_ever_live[i] = 1;
602       }
603
604   for (i = 0; i < scratch_list_length; i++)
605     if (scratch_list[i])
606       mark_scratch_live (scratch_list[i]);
607
608   /* Make sure that the last insn in the chain
609      is not something that needs reloading.  */
610   emit_note (NULL_PTR, NOTE_INSN_DELETED);
611
612   /* Find all the pseudo registers that didn't get hard regs
613      but do have known equivalent constants or memory slots.
614      These include parameters (known equivalent to parameter slots)
615      and cse'd or loop-moved constant memory addresses.
616
617      Record constant equivalents in reg_equiv_constant
618      so they will be substituted by find_reloads.
619      Record memory equivalents in reg_mem_equiv so they can
620      be substituted eventually by altering the REG-rtx's.  */
621
622   reg_equiv_constant = (rtx *) alloca (max_regno * sizeof (rtx));
623   bzero ((char *) reg_equiv_constant, max_regno * sizeof (rtx));
624   reg_equiv_memory_loc = (rtx *) alloca (max_regno * sizeof (rtx));
625   bzero ((char *) reg_equiv_memory_loc, max_regno * sizeof (rtx));
626   reg_equiv_mem = (rtx *) alloca (max_regno * sizeof (rtx));
627   bzero ((char *) reg_equiv_mem, max_regno * sizeof (rtx));
628   reg_equiv_init = (rtx *) alloca (max_regno * sizeof (rtx));
629   bzero ((char *) reg_equiv_init, max_regno * sizeof (rtx));
630   reg_equiv_address = (rtx *) alloca (max_regno * sizeof (rtx));
631   bzero ((char *) reg_equiv_address, max_regno * sizeof (rtx));
632   reg_max_ref_width = (int *) alloca (max_regno * sizeof (int));
633   bzero ((char *) reg_max_ref_width, max_regno * sizeof (int));
634   cannot_omit_stores = (char *) alloca (max_regno);
635   bzero (cannot_omit_stores, max_regno);
636
637 #ifdef SMALL_REGISTER_CLASSES
638   if (SMALL_REGISTER_CLASSES)
639     CLEAR_HARD_REG_SET (forbidden_regs);
640 #endif
641
642   /* Look for REG_EQUIV notes; record what each pseudo is equivalent to.
643      Also find all paradoxical subregs and find largest such for each pseudo.
644      On machines with small register classes, record hard registers that
645      are used for user variables.  These can never be used for spills. 
646      Also look for a "constant" NOTE_INSN_SETJMP.  This means that all
647      caller-saved registers must be marked live.  */
648
649   for (insn = first; insn; insn = NEXT_INSN (insn))
650     {
651       rtx set = single_set (insn);
652
653       if (GET_CODE (insn) == NOTE && CONST_CALL_P (insn)
654           && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
655         for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
656           if (! call_used_regs[i])
657             regs_ever_live[i] = 1;
658
659       if (set != 0 && GET_CODE (SET_DEST (set)) == REG)
660         {
661           rtx note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
662           if (note
663 #ifdef LEGITIMATE_PIC_OPERAND_P
664               && (! CONSTANT_P (XEXP (note, 0)) || ! flag_pic
665                   || LEGITIMATE_PIC_OPERAND_P (XEXP (note, 0)))
666 #endif
667               )
668             {
669               rtx x = XEXP (note, 0);
670               i = REGNO (SET_DEST (set));
671               if (i > LAST_VIRTUAL_REGISTER)
672                 {
673                   if (GET_CODE (x) == MEM)
674                     reg_equiv_memory_loc[i] = x;
675                   else if (CONSTANT_P (x))
676                     {
677                       if (LEGITIMATE_CONSTANT_P (x))
678                         reg_equiv_constant[i] = x;
679                       else
680                         reg_equiv_memory_loc[i]
681                           = force_const_mem (GET_MODE (SET_DEST (set)), x);
682                     }
683                   else
684                     continue;
685
686                   /* If this register is being made equivalent to a MEM
687                      and the MEM is not SET_SRC, the equivalencing insn
688                      is one with the MEM as a SET_DEST and it occurs later.
689                      So don't mark this insn now.  */
690                   if (GET_CODE (x) != MEM
691                       || rtx_equal_p (SET_SRC (set), x))
692                     reg_equiv_init[i] = insn;
693                 }
694             }
695         }
696
697       /* If this insn is setting a MEM from a register equivalent to it,
698          this is the equivalencing insn.  */
699       else if (set && GET_CODE (SET_DEST (set)) == MEM
700                && GET_CODE (SET_SRC (set)) == REG
701                && reg_equiv_memory_loc[REGNO (SET_SRC (set))]
702                && rtx_equal_p (SET_DEST (set),
703                                reg_equiv_memory_loc[REGNO (SET_SRC (set))]))
704         reg_equiv_init[REGNO (SET_SRC (set))] = insn;
705
706       if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
707         scan_paradoxical_subregs (PATTERN (insn));
708     }
709
710   /* Does this function require a frame pointer?  */
711
712   frame_pointer_needed = (! flag_omit_frame_pointer
713 #ifdef EXIT_IGNORE_STACK
714                           /* ?? If EXIT_IGNORE_STACK is set, we will not save
715                              and restore sp for alloca.  So we can't eliminate
716                              the frame pointer in that case.  At some point,
717                              we should improve this by emitting the
718                              sp-adjusting insns for this case.  */
719                           || (current_function_calls_alloca
720                               && EXIT_IGNORE_STACK)
721 #endif
722                           || FRAME_POINTER_REQUIRED);
723
724   num_eliminable = 0;
725
726   /* Initialize the table of registers to eliminate.  The way we do this
727      depends on how the eliminable registers were defined.  */
728 #ifdef ELIMINABLE_REGS
729   for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
730     {
731       ep->can_eliminate = ep->can_eliminate_previous
732         = (CAN_ELIMINATE (ep->from, ep->to)
733            && ! (ep->to == STACK_POINTER_REGNUM && frame_pointer_needed));
734     }
735 #else
736   reg_eliminate[0].can_eliminate = reg_eliminate[0].can_eliminate_previous
737     = ! frame_pointer_needed;
738 #endif
739
740   /* Count the number of eliminable registers and build the FROM and TO
741      REG rtx's.  Note that code in gen_rtx will cause, e.g.,
742      gen_rtx (REG, Pmode, STACK_POINTER_REGNUM) to equal stack_pointer_rtx.
743      We depend on this.  */
744   for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
745     {
746       num_eliminable += ep->can_eliminate;
747       ep->from_rtx = gen_rtx (REG, Pmode, ep->from);
748       ep->to_rtx = gen_rtx (REG, Pmode, ep->to);
749     }
750
751   num_labels = max_label_num () - get_first_label_num ();
752
753   /* Allocate the tables used to store offset information at labels.  */
754   offsets_known_at = (char *) alloca (num_labels);
755   offsets_at
756     = (int (*)[NUM_ELIMINABLE_REGS])
757       alloca (num_labels * NUM_ELIMINABLE_REGS * sizeof (int));
758
759   offsets_known_at -= get_first_label_num ();
760   offsets_at -= get_first_label_num ();
761
762   /* Alter each pseudo-reg rtx to contain its hard reg number.
763      Assign stack slots to the pseudos that lack hard regs or equivalents.
764      Do not touch virtual registers.  */
765
766   for (i = LAST_VIRTUAL_REGISTER + 1; i < max_regno; i++)
767     alter_reg (i, -1);
768
769   /* If we have some registers we think can be eliminated, scan all insns to
770      see if there is an insn that sets one of these registers to something
771      other than itself plus a constant.  If so, the register cannot be
772      eliminated.  Doing this scan here eliminates an extra pass through the
773      main reload loop in the most common case where register elimination
774      cannot be done.  */
775   for (insn = first; insn && num_eliminable; insn = NEXT_INSN (insn))
776     if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN
777         || GET_CODE (insn) == CALL_INSN)
778       note_stores (PATTERN (insn), mark_not_eliminable);
779
780 #ifndef REGISTER_CONSTRAINTS
781   /* If all the pseudo regs have hard regs,
782      except for those that are never referenced,
783      we know that no reloads are needed.  */
784   /* But that is not true if there are register constraints, since
785      in that case some pseudos might be in the wrong kind of hard reg.  */
786
787   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
788     if (reg_renumber[i] == -1 && reg_n_refs[i] != 0)
789       break;
790
791   if (i == max_regno && num_eliminable == 0 && ! caller_save_needed)
792     return;
793 #endif
794
795   /* Compute the order of preference for hard registers to spill.
796      Store them by decreasing preference in potential_reload_regs.  */
797
798   order_regs_for_reload (global);
799
800   /* So far, no hard regs have been spilled.  */
801   n_spills = 0;
802   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
803     spill_reg_order[i] = -1;
804
805   /* Initialize to -1, which means take the first spill register.  */
806   last_spill_reg = -1;
807
808   /* On most machines, we can't use any register explicitly used in the
809      rtl as a spill register.  But on some, we have to.  Those will have
810      taken care to keep the life of hard regs as short as possible.  */
811
812 #ifdef SMALL_REGISTER_CLASSES
813   if (! SMALL_REGISTER_CLASSES)
814 #endif
815     COPY_HARD_REG_SET (forbidden_regs, bad_spill_regs);
816
817   /* Spill any hard regs that we know we can't eliminate.  */
818   for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
819     if (! ep->can_eliminate)
820       spill_hard_reg (ep->from, global, dumpfile, 1);
821
822 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
823   if (frame_pointer_needed)
824     spill_hard_reg (HARD_FRAME_POINTER_REGNUM, global, dumpfile, 1);
825 #endif
826
827   if (global)
828     for (i = 0; i < N_REG_CLASSES; i++)
829       {
830         basic_block_needs[i] = (char *) alloca (n_basic_blocks);
831         bzero (basic_block_needs[i], n_basic_blocks);
832       }
833
834   /* From now on, we need to emit any moves without making new pseudos.  */
835   reload_in_progress = 1;
836
837   /* This loop scans the entire function each go-round
838      and repeats until one repetition spills no additional hard regs.  */
839
840   /* This flag is set when a pseudo reg is spilled,
841      to require another pass.  Note that getting an additional reload
842      reg does not necessarily imply any pseudo reg was spilled;
843      sometimes we find a reload reg that no pseudo reg was allocated in.  */
844   something_changed = 1;
845   /* This flag is set if there are any insns that require reloading.  */
846   something_needs_reloads = 0;
847   /* This flag is set if there are any insns that require register
848      eliminations.  */
849   something_needs_elimination = 0;
850   while (something_changed)
851     {
852       rtx after_call = 0;
853
854       /* For each class, number of reload regs needed in that class.
855          This is the maximum over all insns of the needs in that class
856          of the individual insn.  */
857       int max_needs[N_REG_CLASSES];
858       /* For each class, size of group of consecutive regs
859          that is needed for the reloads of this class.  */
860       int group_size[N_REG_CLASSES];
861       /* For each class, max number of consecutive groups needed.
862          (Each group contains group_size[CLASS] consecutive registers.)  */
863       int max_groups[N_REG_CLASSES];
864       /* For each class, max number needed of regs that don't belong
865          to any of the groups.  */
866       int max_nongroups[N_REG_CLASSES];
867       /* For each class, the machine mode which requires consecutive
868          groups of regs of that class.
869          If two different modes ever require groups of one class,
870          they must be the same size and equally restrictive for that class,
871          otherwise we can't handle the complexity.  */
872       enum machine_mode group_mode[N_REG_CLASSES];
873       /* Record the insn where each maximum need is first found.  */
874       rtx max_needs_insn[N_REG_CLASSES];
875       rtx max_groups_insn[N_REG_CLASSES];
876       rtx max_nongroups_insn[N_REG_CLASSES];
877       rtx x;
878       HOST_WIDE_INT starting_frame_size;
879       int previous_frame_pointer_needed = frame_pointer_needed;
880       static char *reg_class_names[] = REG_CLASS_NAMES;
881
882       something_changed = 0;
883       bzero ((char *) max_needs, sizeof max_needs);
884       bzero ((char *) max_groups, sizeof max_groups);
885       bzero ((char *) max_nongroups, sizeof max_nongroups);
886       bzero ((char *) max_needs_insn, sizeof max_needs_insn);
887       bzero ((char *) max_groups_insn, sizeof max_groups_insn);
888       bzero ((char *) max_nongroups_insn, sizeof max_nongroups_insn);
889       bzero ((char *) group_size, sizeof group_size);
890       for (i = 0; i < N_REG_CLASSES; i++)
891         group_mode[i] = VOIDmode;
892
893       /* Keep track of which basic blocks are needing the reloads.  */
894       this_block = 0;
895
896       /* Remember whether any element of basic_block_needs
897          changes from 0 to 1 in this pass.  */
898       new_basic_block_needs = 0;
899
900       /* Round size of stack frame to BIGGEST_ALIGNMENT.  This must be done
901          here because the stack size may be a part of the offset computation
902          for register elimination, and there might have been new stack slots
903          created in the last iteration of this loop.   */
904       assign_stack_local (BLKmode, 0, 0);
905
906       starting_frame_size = get_frame_size ();
907
908       /* Reset all offsets on eliminable registers to their initial values.  */
909 #ifdef ELIMINABLE_REGS
910       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
911         {
912           INITIAL_ELIMINATION_OFFSET (ep->from, ep->to, ep->initial_offset);
913           ep->previous_offset = ep->offset
914             = ep->max_offset = ep->initial_offset;
915         }
916 #else
917 #ifdef INITIAL_FRAME_POINTER_OFFSET
918       INITIAL_FRAME_POINTER_OFFSET (reg_eliminate[0].initial_offset);
919 #else
920       if (!FRAME_POINTER_REQUIRED)
921         abort ();
922       reg_eliminate[0].initial_offset = 0;
923 #endif
924       reg_eliminate[0].previous_offset = reg_eliminate[0].max_offset
925         = reg_eliminate[0].offset = reg_eliminate[0].initial_offset;
926 #endif
927
928       num_not_at_initial_offset = 0;
929
930       bzero ((char *) &offsets_known_at[get_first_label_num ()], num_labels);
931
932       /* Set a known offset for each forced label to be at the initial offset
933          of each elimination.  We do this because we assume that all
934          computed jumps occur from a location where each elimination is
935          at its initial offset.  */
936
937       for (x = forced_labels; x; x = XEXP (x, 1))
938         if (XEXP (x, 0))
939           set_label_offsets (XEXP (x, 0), NULL_RTX, 1);
940
941       /* For each pseudo register that has an equivalent location defined,
942          try to eliminate any eliminable registers (such as the frame pointer)
943          assuming initial offsets for the replacement register, which
944          is the normal case.
945
946          If the resulting location is directly addressable, substitute
947          the MEM we just got directly for the old REG.
948
949          If it is not addressable but is a constant or the sum of a hard reg
950          and constant, it is probably not addressable because the constant is
951          out of range, in that case record the address; we will generate
952          hairy code to compute the address in a register each time it is
953          needed.  Similarly if it is a hard register, but one that is not
954          valid as an address register.
955
956          If the location is not addressable, but does not have one of the
957          above forms, assign a stack slot.  We have to do this to avoid the
958          potential of producing lots of reloads if, e.g., a location involves
959          a pseudo that didn't get a hard register and has an equivalent memory
960          location that also involves a pseudo that didn't get a hard register.
961
962          Perhaps at some point we will improve reload_when_needed handling
963          so this problem goes away.  But that's very hairy.  */
964
965       for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
966         if (reg_renumber[i] < 0 && reg_equiv_memory_loc[i])
967           {
968             rtx x = eliminate_regs (reg_equiv_memory_loc[i], 0, NULL_RTX, 0);
969
970             if (strict_memory_address_p (GET_MODE (regno_reg_rtx[i]),
971                                          XEXP (x, 0)))
972               reg_equiv_mem[i] = x, reg_equiv_address[i] = 0;
973             else if (CONSTANT_P (XEXP (x, 0))
974                      || (GET_CODE (XEXP (x, 0)) == REG
975                          && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER)
976                      || (GET_CODE (XEXP (x, 0)) == PLUS
977                          && GET_CODE (XEXP (XEXP (x, 0), 0)) == REG
978                          && (REGNO (XEXP (XEXP (x, 0), 0))
979                              < FIRST_PSEUDO_REGISTER)
980                          && CONSTANT_P (XEXP (XEXP (x, 0), 1))))
981               reg_equiv_address[i] = XEXP (x, 0), reg_equiv_mem[i] = 0;
982             else
983               {
984                 /* Make a new stack slot.  Then indicate that something
985                    changed so we go back and recompute offsets for
986                    eliminable registers because the allocation of memory
987                    below might change some offset.  reg_equiv_{mem,address}
988                    will be set up for this pseudo on the next pass around
989                    the loop.  */
990                 reg_equiv_memory_loc[i] = 0;
991                 reg_equiv_init[i] = 0;
992                 alter_reg (i, -1);
993                 something_changed = 1;
994               }
995           }
996
997       /* If we allocated another pseudo to the stack, redo elimination
998          bookkeeping.  */
999       if (something_changed)
1000         continue;
1001
1002       /* If caller-saves needs a group, initialize the group to include
1003          the size and mode required for caller-saves.  */
1004
1005       if (caller_save_group_size > 1)
1006         {
1007           group_mode[(int) caller_save_spill_class] = Pmode;
1008           group_size[(int) caller_save_spill_class] = caller_save_group_size;
1009         }
1010
1011       /* Compute the most additional registers needed by any instruction.
1012          Collect information separately for each class of regs.  */
1013
1014       for (insn = first; insn; insn = NEXT_INSN (insn))
1015         {
1016           if (global && this_block + 1 < n_basic_blocks
1017               && insn == basic_block_head[this_block+1])
1018             ++this_block;
1019
1020           /* If this is a label, a JUMP_INSN, or has REG_NOTES (which
1021              might include REG_LABEL), we need to see what effects this
1022              has on the known offsets at labels.  */
1023
1024           if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN
1025               || (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
1026                   && REG_NOTES (insn) != 0))
1027             set_label_offsets (insn, insn, 0);
1028
1029           if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
1030             {
1031               /* Nonzero means don't use a reload reg that overlaps
1032                  the place where a function value can be returned.  */
1033               rtx avoid_return_reg = 0;
1034
1035               rtx old_body = PATTERN (insn);
1036               int old_code = INSN_CODE (insn);
1037               rtx old_notes = REG_NOTES (insn);
1038               int did_elimination = 0;
1039
1040               /* To compute the number of reload registers of each class 
1041                  needed for an insn, we must simulate what choose_reload_regs
1042                  can do.  We do this by splitting an insn into an "input" and
1043                  an "output" part.  RELOAD_OTHER reloads are used in both. 
1044                  The input part uses those reloads, RELOAD_FOR_INPUT reloads,
1045                  which must be live over the entire input section of reloads,
1046                  and the maximum of all the RELOAD_FOR_INPUT_ADDRESS and
1047                  RELOAD_FOR_OPERAND_ADDRESS reloads, which conflict with the
1048                  inputs.
1049
1050                  The registers needed for output are RELOAD_OTHER and
1051                  RELOAD_FOR_OUTPUT, which are live for the entire output
1052                  portion, and the maximum of all the RELOAD_FOR_OUTPUT_ADDRESS
1053                  reloads for each operand.
1054
1055                  The total number of registers needed is the maximum of the
1056                  inputs and outputs.  */
1057
1058               struct needs
1059                 {
1060                   /* [0] is normal, [1] is nongroup.  */
1061                   int regs[2][N_REG_CLASSES];
1062                   int groups[N_REG_CLASSES];
1063                 };
1064
1065               /* Each `struct needs' corresponds to one RELOAD_... type.  */
1066               struct {
1067                 struct needs other;
1068                 struct needs input;
1069                 struct needs output;
1070                 struct needs insn;
1071                 struct needs other_addr;
1072                 struct needs op_addr;
1073                 struct needs op_addr_reload;
1074                 struct needs in_addr[MAX_RECOG_OPERANDS];
1075                 struct needs in_addr_addr[MAX_RECOG_OPERANDS];
1076                 struct needs out_addr[MAX_RECOG_OPERANDS];
1077                 struct needs out_addr_addr[MAX_RECOG_OPERANDS];
1078               } insn_needs;
1079
1080               /* If needed, eliminate any eliminable registers.  */
1081               if (num_eliminable)
1082                 did_elimination = eliminate_regs_in_insn (insn, 0);
1083
1084 #ifdef SMALL_REGISTER_CLASSES
1085               /* Set avoid_return_reg if this is an insn
1086                  that might use the value of a function call.  */
1087               if (SMALL_REGISTER_CLASSES && GET_CODE (insn) == CALL_INSN)
1088                 {
1089                   if (GET_CODE (PATTERN (insn)) == SET)
1090                     after_call = SET_DEST (PATTERN (insn));
1091                   else if (GET_CODE (PATTERN (insn)) == PARALLEL
1092                            && GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) == SET)
1093                     after_call = SET_DEST (XVECEXP (PATTERN (insn), 0, 0));
1094                   else
1095                     after_call = 0;
1096                 }
1097               else if (SMALL_REGISTER_CLASSES
1098                        && after_call != 0
1099                        && !(GET_CODE (PATTERN (insn)) == SET
1100                             && SET_DEST (PATTERN (insn)) == stack_pointer_rtx))
1101                 {
1102                   if (reg_referenced_p (after_call, PATTERN (insn)))
1103                     avoid_return_reg = after_call;
1104                   after_call = 0;
1105                 }
1106 #endif /* SMALL_REGISTER_CLASSES */
1107
1108               /* Analyze the instruction.  */
1109               find_reloads (insn, 0, spill_indirect_levels, global,
1110                             spill_reg_order);
1111
1112               /* Remember for later shortcuts which insns had any reloads or
1113                  register eliminations.
1114
1115                  One might think that it would be worthwhile to mark insns
1116                  that need register replacements but not reloads, but this is
1117                  not safe because find_reloads may do some manipulation of
1118                  the insn (such as swapping commutative operands), which would
1119                  be lost when we restore the old pattern after register
1120                  replacement.  So the actions of find_reloads must be redone in
1121                  subsequent passes or in reload_as_needed.
1122
1123                  However, it is safe to mark insns that need reloads
1124                  but not register replacement.  */
1125
1126               PUT_MODE (insn, (did_elimination ? QImode
1127                                : n_reloads ? HImode
1128                                : GET_MODE (insn) == DImode ? DImode
1129                                : VOIDmode));
1130
1131               /* Discard any register replacements done.  */
1132               if (did_elimination)
1133                 {
1134                   obstack_free (&reload_obstack, reload_firstobj);
1135                   PATTERN (insn) = old_body;
1136                   INSN_CODE (insn) = old_code;
1137                   REG_NOTES (insn) = old_notes;
1138                   something_needs_elimination = 1;
1139                 }
1140
1141               /* If this insn has no reloads, we need not do anything except
1142                  in the case of a CALL_INSN when we have caller-saves and
1143                  caller-save needs reloads.  */
1144
1145               if (n_reloads == 0
1146                   && ! (GET_CODE (insn) == CALL_INSN
1147                         && caller_save_spill_class != NO_REGS))
1148                 continue;
1149
1150               something_needs_reloads = 1;
1151               bzero ((char *) &insn_needs, sizeof insn_needs);
1152
1153               /* Count each reload once in every class
1154                  containing the reload's own class.  */
1155
1156               for (i = 0; i < n_reloads; i++)
1157                 {
1158                   register enum reg_class *p;
1159                   enum reg_class class = reload_reg_class[i];
1160                   int size;
1161                   enum machine_mode mode;
1162                   int nongroup_need;
1163                   struct needs *this_needs;
1164
1165                   /* Don't count the dummy reloads, for which one of the
1166                      regs mentioned in the insn can be used for reloading.
1167                      Don't count optional reloads.
1168                      Don't count reloads that got combined with others.  */
1169                   if (reload_reg_rtx[i] != 0
1170                       || reload_optional[i] != 0
1171                       || (reload_out[i] == 0 && reload_in[i] == 0
1172                           && ! reload_secondary_p[i]))
1173                     continue;
1174
1175                   /* Show that a reload register of this class is needed
1176                      in this basic block.  We do not use insn_needs and
1177                      insn_groups because they are overly conservative for
1178                      this purpose.  */
1179                   if (global && ! basic_block_needs[(int) class][this_block])
1180                     {
1181                       basic_block_needs[(int) class][this_block] = 1;
1182                       new_basic_block_needs = 1;
1183                     }
1184
1185
1186                   mode = reload_inmode[i];
1187                   if (GET_MODE_SIZE (reload_outmode[i]) > GET_MODE_SIZE (mode))
1188                     mode = reload_outmode[i];
1189                   size = CLASS_MAX_NREGS (class, mode);
1190
1191                   /* If this class doesn't want a group, determine if we have
1192                      a nongroup need or a regular need.  We have a nongroup
1193                      need if this reload conflicts with a group reload whose
1194                      class intersects with this reload's class.  */
1195
1196                   nongroup_need = 0;
1197                   if (size == 1)
1198                     for (j = 0; j < n_reloads; j++)
1199                       if ((CLASS_MAX_NREGS (reload_reg_class[j],
1200                                             (GET_MODE_SIZE (reload_outmode[j])
1201                                              > GET_MODE_SIZE (reload_inmode[j]))
1202                                             ? reload_outmode[j]
1203                                             : reload_inmode[j])
1204                            > 1)
1205                           && (!reload_optional[j])
1206                           && (reload_in[j] != 0 || reload_out[j] != 0
1207                               || reload_secondary_p[j])
1208                           && reloads_conflict (i, j)
1209                           && reg_classes_intersect_p (class,
1210                                                       reload_reg_class[j]))
1211                         {
1212                           nongroup_need = 1;
1213                           break;
1214                         }
1215
1216                   /* Decide which time-of-use to count this reload for.  */
1217                   switch (reload_when_needed[i])
1218                     {
1219                     case RELOAD_OTHER:
1220                       this_needs = &insn_needs.other;
1221                       break;
1222                     case RELOAD_FOR_INPUT:
1223                       this_needs = &insn_needs.input;
1224                       break;
1225                     case RELOAD_FOR_OUTPUT:
1226                       this_needs = &insn_needs.output;
1227                       break;
1228                     case RELOAD_FOR_INSN:
1229                       this_needs = &insn_needs.insn;
1230                       break;
1231                     case RELOAD_FOR_OTHER_ADDRESS:
1232                       this_needs = &insn_needs.other_addr;
1233                       break;
1234                     case RELOAD_FOR_INPUT_ADDRESS:
1235                       this_needs = &insn_needs.in_addr[reload_opnum[i]];
1236                       break;
1237                     case RELOAD_FOR_INPADDR_ADDRESS:
1238                       this_needs = &insn_needs.in_addr_addr[reload_opnum[i]];
1239                       break;
1240                     case RELOAD_FOR_OUTPUT_ADDRESS:
1241                       this_needs = &insn_needs.out_addr[reload_opnum[i]];
1242                       break;
1243                     case RELOAD_FOR_OUTADDR_ADDRESS:
1244                       this_needs = &insn_needs.out_addr_addr[reload_opnum[i]];
1245                       break;
1246                     case RELOAD_FOR_OPERAND_ADDRESS:
1247                       this_needs = &insn_needs.op_addr;
1248                       break;
1249                     case RELOAD_FOR_OPADDR_ADDR:
1250                       this_needs = &insn_needs.op_addr_reload;
1251                       break;
1252                     }
1253
1254                   if (size > 1)
1255                     {
1256                       enum machine_mode other_mode, allocate_mode;
1257
1258                       /* Count number of groups needed separately from
1259                          number of individual regs needed.  */
1260                       this_needs->groups[(int) class]++;
1261                       p = reg_class_superclasses[(int) class];
1262                       while (*p != LIM_REG_CLASSES)
1263                         this_needs->groups[(int) *p++]++;
1264
1265                       /* Record size and mode of a group of this class.  */
1266                       /* If more than one size group is needed,
1267                          make all groups the largest needed size.  */
1268                       if (group_size[(int) class] < size)
1269                         {
1270                           other_mode = group_mode[(int) class];
1271                           allocate_mode = mode;
1272
1273                           group_size[(int) class] = size;
1274                           group_mode[(int) class] = mode;
1275                         }
1276                       else
1277                         {
1278                           other_mode = mode;
1279                           allocate_mode = group_mode[(int) class];
1280                         }
1281
1282                       /* Crash if two dissimilar machine modes both need
1283                          groups of consecutive regs of the same class.  */
1284
1285                       if (other_mode != VOIDmode && other_mode != allocate_mode
1286                           && ! modes_equiv_for_class_p (allocate_mode,
1287                                                         other_mode, class))
1288                         fatal_insn ("Two dissimilar machine modes both need groups of consecutive regs of the same class",
1289                                     insn);
1290                     }
1291                   else if (size == 1)
1292                     {
1293                       this_needs->regs[nongroup_need][(int) class] += 1;
1294                       p = reg_class_superclasses[(int) class];
1295                       while (*p != LIM_REG_CLASSES)
1296                         this_needs->regs[nongroup_need][(int) *p++] += 1;
1297                     }
1298                   else
1299                     abort ();
1300                 }
1301
1302               /* All reloads have been counted for this insn;
1303                  now merge the various times of use.
1304                  This sets insn_needs, etc., to the maximum total number
1305                  of registers needed at any point in this insn.  */
1306
1307               for (i = 0; i < N_REG_CLASSES; i++)
1308                 {
1309                   int in_max, out_max;
1310
1311                   /* Compute normal and nongroup needs.  */
1312                   for (j = 0; j <= 1; j++)
1313                     {
1314                       for (in_max = 0, out_max = 0, k = 0;
1315                            k < reload_n_operands; k++)
1316                         {
1317                           in_max
1318                             = MAX (in_max, insn_needs.in_addr[k].regs[j][i]);
1319                           in_max
1320                             = MAX (in_max,
1321                                    insn_needs.in_addr_addr[k].regs[j][i]);
1322                           out_max
1323                             = MAX (out_max, insn_needs.out_addr[k].regs[j][i]);
1324                           out_max
1325                             = MAX (out_max,
1326                                    insn_needs.out_addr_addr[k].regs[j][i]);
1327                         }
1328
1329                       /* RELOAD_FOR_INSN reloads conflict with inputs, outputs,
1330                          and operand addresses but not things used to reload
1331                          them.  Similarly, RELOAD_FOR_OPERAND_ADDRESS reloads
1332                          don't conflict with things needed to reload inputs or
1333                          outputs.  */
1334
1335                       in_max = MAX (MAX (insn_needs.op_addr.regs[j][i],
1336                                          insn_needs.op_addr_reload.regs[j][i]),
1337                                     in_max);
1338
1339                       out_max = MAX (out_max, insn_needs.insn.regs[j][i]);
1340
1341                       insn_needs.input.regs[j][i]
1342                         = MAX (insn_needs.input.regs[j][i]
1343                                + insn_needs.op_addr.regs[j][i]
1344                                + insn_needs.insn.regs[j][i],
1345                                in_max + insn_needs.input.regs[j][i]);
1346
1347                       insn_needs.output.regs[j][i] += out_max;
1348                       insn_needs.other.regs[j][i]
1349                         += MAX (MAX (insn_needs.input.regs[j][i],
1350                                      insn_needs.output.regs[j][i]),
1351                                 insn_needs.other_addr.regs[j][i]);
1352
1353                     }
1354
1355                   /* Now compute group needs.  */
1356                   for (in_max = 0, out_max = 0, j = 0;
1357                        j < reload_n_operands; j++)
1358                     {
1359                       in_max = MAX (in_max, insn_needs.in_addr[j].groups[i]);
1360                       in_max = MAX (in_max,
1361                                      insn_needs.in_addr_addr[j].groups[i]);
1362                       out_max
1363                         = MAX (out_max, insn_needs.out_addr[j].groups[i]);
1364                       out_max
1365                         = MAX (out_max, insn_needs.out_addr_addr[j].groups[i]);
1366                     }
1367
1368                   in_max = MAX (MAX (insn_needs.op_addr.groups[i],
1369                                      insn_needs.op_addr_reload.groups[i]),
1370                                 in_max);
1371                   out_max = MAX (out_max, insn_needs.insn.groups[i]);
1372
1373                   insn_needs.input.groups[i]
1374                     = MAX (insn_needs.input.groups[i]
1375                            + insn_needs.op_addr.groups[i]
1376                            + insn_needs.insn.groups[i],
1377                            in_max + insn_needs.input.groups[i]);
1378
1379                   insn_needs.output.groups[i] += out_max;
1380                   insn_needs.other.groups[i]
1381                     += MAX (MAX (insn_needs.input.groups[i],
1382                                  insn_needs.output.groups[i]),
1383                             insn_needs.other_addr.groups[i]);
1384                 }
1385
1386               /* If this is a CALL_INSN and caller-saves will need
1387                  a spill register, act as if the spill register is
1388                  needed for this insn.   However, the spill register
1389                  can be used by any reload of this insn, so we only
1390                  need do something if no need for that class has
1391                  been recorded.
1392
1393                  The assumption that every CALL_INSN will trigger a
1394                  caller-save is highly conservative, however, the number
1395                  of cases where caller-saves will need a spill register but
1396                  a block containing a CALL_INSN won't need a spill register
1397                  of that class should be quite rare.
1398
1399                  If a group is needed, the size and mode of the group will
1400                  have been set up at the beginning of this loop.  */
1401
1402               if (GET_CODE (insn) == CALL_INSN
1403                   && caller_save_spill_class != NO_REGS)
1404                 {
1405                   /* See if this register would conflict with any reload
1406                      that needs a group.  */
1407                   int nongroup_need = 0;
1408                   int *caller_save_needs;
1409
1410                   for (j = 0; j < n_reloads; j++)
1411                     if ((CLASS_MAX_NREGS (reload_reg_class[j],
1412                                           (GET_MODE_SIZE (reload_outmode[j])
1413                                            > GET_MODE_SIZE (reload_inmode[j]))
1414                                           ? reload_outmode[j]
1415                                           : reload_inmode[j])
1416                          > 1)
1417                         && reg_classes_intersect_p (caller_save_spill_class,
1418                                                     reload_reg_class[j]))
1419                       {
1420                         nongroup_need = 1;
1421                         break;
1422                       }
1423
1424                   caller_save_needs 
1425                     = (caller_save_group_size > 1
1426                        ? insn_needs.other.groups
1427                        : insn_needs.other.regs[nongroup_need]); 
1428
1429                   if (caller_save_needs[(int) caller_save_spill_class] == 0)
1430                     {
1431                       register enum reg_class *p
1432                         = reg_class_superclasses[(int) caller_save_spill_class];
1433
1434                       caller_save_needs[(int) caller_save_spill_class]++;
1435
1436                       while (*p != LIM_REG_CLASSES)
1437                         caller_save_needs[(int) *p++] += 1;
1438                     }
1439
1440                   /* Show that this basic block will need a register of
1441                    this class.  */
1442
1443                   if (global
1444                       && ! (basic_block_needs[(int) caller_save_spill_class]
1445                             [this_block]))
1446                     {
1447                       basic_block_needs[(int) caller_save_spill_class]
1448                         [this_block] = 1;
1449                       new_basic_block_needs = 1;
1450                     }
1451                 }
1452
1453 #ifdef SMALL_REGISTER_CLASSES
1454               /* If this insn stores the value of a function call,
1455                  and that value is in a register that has been spilled,
1456                  and if the insn needs a reload in a class
1457                  that might use that register as the reload register,
1458                  then add add an extra need in that class.
1459                  This makes sure we have a register available that does
1460                  not overlap the return value.  */
1461
1462               if (SMALL_REGISTER_CLASSES && avoid_return_reg)
1463                 {
1464                   int regno = REGNO (avoid_return_reg);
1465                   int nregs
1466                     = HARD_REGNO_NREGS (regno, GET_MODE (avoid_return_reg));
1467                   int r;
1468                   int basic_needs[N_REG_CLASSES], basic_groups[N_REG_CLASSES];
1469
1470                   /* First compute the "basic needs", which counts a
1471                      need only in the smallest class in which it
1472                      is required.  */
1473
1474                   bcopy ((char *) insn_needs.other.regs[0],
1475                          (char *) basic_needs, sizeof basic_needs);
1476                   bcopy ((char *) insn_needs.other.groups,
1477                          (char *) basic_groups, sizeof basic_groups);
1478
1479                   for (i = 0; i < N_REG_CLASSES; i++)
1480                     {
1481                       enum reg_class *p;
1482
1483                       if (basic_needs[i] >= 0)
1484                         for (p = reg_class_superclasses[i];
1485                              *p != LIM_REG_CLASSES; p++)
1486                           basic_needs[(int) *p] -= basic_needs[i];
1487
1488                       if (basic_groups[i] >= 0)
1489                         for (p = reg_class_superclasses[i];
1490                              *p != LIM_REG_CLASSES; p++)
1491                           basic_groups[(int) *p] -= basic_groups[i];
1492                     }
1493
1494                   /* Now count extra regs if there might be a conflict with
1495                      the return value register.  */
1496
1497                   for (r = regno; r < regno + nregs; r++)
1498                     if (spill_reg_order[r] >= 0)
1499                       for (i = 0; i < N_REG_CLASSES; i++)
1500                         if (TEST_HARD_REG_BIT (reg_class_contents[i], r))
1501                           {
1502                             if (basic_needs[i] > 0)
1503                               {
1504                                 enum reg_class *p;
1505
1506                                 insn_needs.other.regs[0][i]++;
1507                                 p = reg_class_superclasses[i];
1508                                 while (*p != LIM_REG_CLASSES)
1509                                   insn_needs.other.regs[0][(int) *p++]++;
1510                               }
1511                             if (basic_groups[i] > 0)
1512                               {
1513                                 enum reg_class *p;
1514
1515                                 insn_needs.other.groups[i]++;
1516                                 p = reg_class_superclasses[i];
1517                                 while (*p != LIM_REG_CLASSES)
1518                                   insn_needs.other.groups[(int) *p++]++;
1519                               }
1520                           }
1521                 }
1522 #endif /* SMALL_REGISTER_CLASSES */
1523
1524               /* For each class, collect maximum need of any insn.  */
1525
1526               for (i = 0; i < N_REG_CLASSES; i++)
1527                 {
1528                   if (max_needs[i] < insn_needs.other.regs[0][i])
1529                     {
1530                       max_needs[i] = insn_needs.other.regs[0][i];
1531                       max_needs_insn[i] = insn;
1532                     }
1533                   if (max_groups[i] < insn_needs.other.groups[i])
1534                     {
1535                       max_groups[i] = insn_needs.other.groups[i];
1536                       max_groups_insn[i] = insn;
1537                     }
1538                   if (max_nongroups[i] < insn_needs.other.regs[1][i])
1539                     {
1540                       max_nongroups[i] = insn_needs.other.regs[1][i];
1541                       max_nongroups_insn[i] = insn;
1542                     }
1543                 }
1544             }
1545           /* Note that there is a continue statement above.  */
1546         }
1547
1548       /* If we allocated any new memory locations, make another pass
1549          since it might have changed elimination offsets.  */
1550       if (starting_frame_size != get_frame_size ())
1551         something_changed = 1;
1552
1553       if (dumpfile)
1554         for (i = 0; i < N_REG_CLASSES; i++)
1555           {
1556             if (max_needs[i] > 0)
1557               fprintf (dumpfile,
1558                          ";; Need %d reg%s of class %s (for insn %d).\n",
1559                        max_needs[i], max_needs[i] == 1 ? "" : "s",
1560                        reg_class_names[i], INSN_UID (max_needs_insn[i]));
1561             if (max_nongroups[i] > 0)
1562               fprintf (dumpfile,
1563                        ";; Need %d nongroup reg%s of class %s (for insn %d).\n",
1564                        max_nongroups[i], max_nongroups[i] == 1 ? "" : "s",
1565                        reg_class_names[i], INSN_UID (max_nongroups_insn[i]));
1566             if (max_groups[i] > 0)
1567               fprintf (dumpfile,
1568                        ";; Need %d group%s (%smode) of class %s (for insn %d).\n",
1569                        max_groups[i], max_groups[i] == 1 ? "" : "s",
1570                        mode_name[(int) group_mode[i]],
1571                        reg_class_names[i], INSN_UID (max_groups_insn[i]));
1572           }
1573                          
1574       /* If we have caller-saves, set up the save areas and see if caller-save
1575          will need a spill register.  */
1576
1577       if (caller_save_needed)
1578         {
1579           /* Set the offsets for setup_save_areas.  */
1580           for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
1581                ep++)
1582             ep->previous_offset = ep->max_offset;
1583
1584           if ( ! setup_save_areas (&something_changed)
1585               && caller_save_spill_class  == NO_REGS)
1586             {
1587               /* The class we will need depends on whether the machine
1588                  supports the sum of two registers for an address; see
1589               find_address_reloads for details.  */
1590
1591               caller_save_spill_class
1592                 = double_reg_address_ok ? INDEX_REG_CLASS : BASE_REG_CLASS;
1593               caller_save_group_size
1594                 = CLASS_MAX_NREGS (caller_save_spill_class, Pmode);
1595               something_changed = 1;
1596             }
1597         }
1598
1599       /* See if anything that happened changes which eliminations are valid.
1600          For example, on the Sparc, whether or not the frame pointer can
1601          be eliminated can depend on what registers have been used.  We need
1602          not check some conditions again (such as flag_omit_frame_pointer)
1603          since they can't have changed.  */
1604
1605       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
1606         if ((ep->from == HARD_FRAME_POINTER_REGNUM && FRAME_POINTER_REQUIRED)
1607 #ifdef ELIMINABLE_REGS
1608             || ! CAN_ELIMINATE (ep->from, ep->to)
1609 #endif
1610             )
1611           ep->can_eliminate = 0;
1612
1613       /* Look for the case where we have discovered that we can't replace
1614          register A with register B and that means that we will now be
1615          trying to replace register A with register C.  This means we can
1616          no longer replace register C with register B and we need to disable
1617          such an elimination, if it exists.  This occurs often with A == ap,
1618          B == sp, and C == fp.  */
1619
1620       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
1621         {
1622           struct elim_table *op;
1623           register int new_to = -1;
1624
1625           if (! ep->can_eliminate && ep->can_eliminate_previous)
1626             {
1627               /* Find the current elimination for ep->from, if there is a
1628                  new one.  */
1629               for (op = reg_eliminate;
1630                    op < &reg_eliminate[NUM_ELIMINABLE_REGS]; op++)
1631                 if (op->from == ep->from && op->can_eliminate)
1632                   {
1633                     new_to = op->to;
1634                     break;
1635                   }
1636
1637               /* See if there is an elimination of NEW_TO -> EP->TO.  If so,
1638                  disable it.  */
1639               for (op = reg_eliminate;
1640                    op < &reg_eliminate[NUM_ELIMINABLE_REGS]; op++)
1641                 if (op->from == new_to && op->to == ep->to)
1642                   op->can_eliminate = 0;
1643             }
1644         }
1645
1646       /* See if any registers that we thought we could eliminate the previous
1647          time are no longer eliminable.  If so, something has changed and we
1648          must spill the register.  Also, recompute the number of eliminable
1649          registers and see if the frame pointer is needed; it is if there is
1650          no elimination of the frame pointer that we can perform.  */
1651
1652       frame_pointer_needed = 1;
1653       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
1654         {
1655           if (ep->can_eliminate && ep->from == FRAME_POINTER_REGNUM
1656               && ep->to != HARD_FRAME_POINTER_REGNUM)
1657             frame_pointer_needed = 0;
1658
1659           if (! ep->can_eliminate && ep->can_eliminate_previous)
1660             {
1661               ep->can_eliminate_previous = 0;
1662               spill_hard_reg (ep->from, global, dumpfile, 1);
1663               something_changed = 1;
1664               num_eliminable--;
1665             }
1666         }
1667
1668 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
1669       /* If we didn't need a frame pointer last time, but we do now, spill
1670          the hard frame pointer.  */
1671       if (frame_pointer_needed && ! previous_frame_pointer_needed)
1672         {
1673           spill_hard_reg (HARD_FRAME_POINTER_REGNUM, global, dumpfile, 1);
1674           something_changed = 1;
1675         }
1676 #endif
1677
1678       /* If all needs are met, we win.  */
1679
1680       for (i = 0; i < N_REG_CLASSES; i++)
1681         if (max_needs[i] > 0 || max_groups[i] > 0 || max_nongroups[i] > 0)
1682           break;
1683       if (i == N_REG_CLASSES && !new_basic_block_needs && ! something_changed)
1684         break;
1685
1686       /* Not all needs are met; must spill some hard regs.  */
1687
1688       /* Put all registers spilled so far back in potential_reload_regs, but
1689          put them at the front, since we've already spilled most of the
1690          pseudos in them (we might have left some pseudos unspilled if they
1691          were in a block that didn't need any spill registers of a conflicting
1692          class.  We used to try to mark off the need for those registers,
1693          but doing so properly is very complex and reallocating them is the
1694          simpler approach.  First, "pack" potential_reload_regs by pushing 
1695          any nonnegative entries towards the end.  That will leave room 
1696          for the registers we already spilled.
1697
1698          Also, undo the marking of the spill registers from the last time
1699          around in FORBIDDEN_REGS since we will be probably be allocating
1700          them again below.
1701
1702          ??? It is theoretically possible that we might end up not using one
1703          of our previously-spilled registers in this allocation, even though
1704          they are at the head of the list.  It's not clear what to do about
1705          this, but it was no better before, when we marked off the needs met
1706          by the previously-spilled registers.  With the current code, globals
1707          can be allocated into these registers, but locals cannot.  */
1708
1709       if (n_spills)
1710         {
1711           for (i = j = FIRST_PSEUDO_REGISTER - 1; i >= 0; i--)
1712             if (potential_reload_regs[i] != -1)
1713               potential_reload_regs[j--] = potential_reload_regs[i];
1714
1715           for (i = 0; i < n_spills; i++)
1716             {
1717               potential_reload_regs[i] = spill_regs[i];
1718               spill_reg_order[spill_regs[i]] = -1;
1719               CLEAR_HARD_REG_BIT (forbidden_regs, spill_regs[i]);
1720             }
1721
1722           n_spills = 0;
1723         }
1724
1725       /* Now find more reload regs to satisfy the remaining need
1726          Do it by ascending class number, since otherwise a reg
1727          might be spilled for a big class and might fail to count
1728          for a smaller class even though it belongs to that class.
1729
1730          Count spilled regs in `spills', and add entries to
1731          `spill_regs' and `spill_reg_order'.
1732
1733          ??? Note there is a problem here.
1734          When there is a need for a group in a high-numbered class,
1735          and also need for non-group regs that come from a lower class,
1736          the non-group regs are chosen first.  If there aren't many regs,
1737          they might leave no room for a group.
1738
1739          This was happening on the 386.  To fix it, we added the code
1740          that calls possible_group_p, so that the lower class won't
1741          break up the last possible group.
1742
1743          Really fixing the problem would require changes above
1744          in counting the regs already spilled, and in choose_reload_regs.
1745          It might be hard to avoid introducing bugs there.  */
1746
1747       CLEAR_HARD_REG_SET (counted_for_groups);
1748       CLEAR_HARD_REG_SET (counted_for_nongroups);
1749
1750       for (class = 0; class < N_REG_CLASSES; class++)
1751         {
1752           /* First get the groups of registers.
1753              If we got single registers first, we might fragment
1754              possible groups.  */
1755           while (max_groups[class] > 0)
1756             {
1757               /* If any single spilled regs happen to form groups,
1758                  count them now.  Maybe we don't really need
1759                  to spill another group.  */
1760               count_possible_groups (group_size, group_mode, max_groups,
1761                                      class);
1762
1763               if (max_groups[class] <= 0)
1764                 break;
1765
1766               /* Groups of size 2 (the only groups used on most machines)
1767                  are treated specially.  */
1768               if (group_size[class] == 2)
1769                 {
1770                   /* First, look for a register that will complete a group.  */
1771                   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1772                     {
1773                       int other;
1774
1775                       j = potential_reload_regs[i];
1776                       if (j >= 0 && ! TEST_HARD_REG_BIT (bad_spill_regs, j)
1777                           &&
1778                           ((j > 0 && (other = j - 1, spill_reg_order[other] >= 0)
1779                             && TEST_HARD_REG_BIT (reg_class_contents[class], j)
1780                             && TEST_HARD_REG_BIT (reg_class_contents[class], other)
1781                             && HARD_REGNO_MODE_OK (other, group_mode[class])
1782                             && ! TEST_HARD_REG_BIT (counted_for_nongroups,
1783                                                     other)
1784                             /* We don't want one part of another group.
1785                                We could get "two groups" that overlap!  */
1786                             && ! TEST_HARD_REG_BIT (counted_for_groups, other))
1787                            ||
1788                            (j < FIRST_PSEUDO_REGISTER - 1
1789                             && (other = j + 1, spill_reg_order[other] >= 0)
1790                             && TEST_HARD_REG_BIT (reg_class_contents[class], j)
1791                             && TEST_HARD_REG_BIT (reg_class_contents[class], other)
1792                             && HARD_REGNO_MODE_OK (j, group_mode[class])
1793                             && ! TEST_HARD_REG_BIT (counted_for_nongroups,
1794                                                     other)
1795                             && ! TEST_HARD_REG_BIT (counted_for_groups,
1796                                                     other))))
1797                         {
1798                           register enum reg_class *p;
1799
1800                           /* We have found one that will complete a group,
1801                              so count off one group as provided.  */
1802                           max_groups[class]--;
1803                           p = reg_class_superclasses[class];
1804                           while (*p != LIM_REG_CLASSES)
1805                             {
1806                               if (group_size [(int) *p] <= group_size [class])
1807                                 max_groups[(int) *p]--;
1808                               p++;
1809                             }
1810
1811                           /* Indicate both these regs are part of a group.  */
1812                           SET_HARD_REG_BIT (counted_for_groups, j);
1813                           SET_HARD_REG_BIT (counted_for_groups, other);
1814                           break;
1815                         }
1816                     }
1817                   /* We can't complete a group, so start one.  */
1818 #ifdef SMALL_REGISTER_CLASSES
1819                   /* Look for a pair neither of which is explicitly used.  */
1820                   if (SMALL_REGISTER_CLASSES && i == FIRST_PSEUDO_REGISTER)
1821                     for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1822                       {
1823                         int k;
1824                         j = potential_reload_regs[i];
1825                         /* Verify that J+1 is a potential reload reg.  */
1826                         for (k = 0; k < FIRST_PSEUDO_REGISTER; k++)
1827                           if (potential_reload_regs[k] == j + 1)
1828                             break;
1829                         if (j >= 0 && j + 1 < FIRST_PSEUDO_REGISTER
1830                             && k < FIRST_PSEUDO_REGISTER
1831                             && spill_reg_order[j] < 0 && spill_reg_order[j + 1] < 0
1832                             && TEST_HARD_REG_BIT (reg_class_contents[class], j)
1833                             && TEST_HARD_REG_BIT (reg_class_contents[class], j + 1)
1834                             && HARD_REGNO_MODE_OK (j, group_mode[class])
1835                             && ! TEST_HARD_REG_BIT (counted_for_nongroups,
1836                                                     j + 1)
1837                             && ! TEST_HARD_REG_BIT (bad_spill_regs, j + 1)
1838                             /* Reject J at this stage
1839                                if J+1 was explicitly used.  */
1840                             && ! regs_explicitly_used[j + 1])
1841                           break;
1842                       }
1843 #endif
1844                   /* Now try any group at all
1845                      whose registers are not in bad_spill_regs.  */
1846                   if (i == FIRST_PSEUDO_REGISTER)
1847                     for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1848                       {
1849                         int k;
1850                         j = potential_reload_regs[i];
1851                         /* Verify that J+1 is a potential reload reg.  */
1852                         for (k = 0; k < FIRST_PSEUDO_REGISTER; k++)
1853                           if (potential_reload_regs[k] == j + 1)
1854                             break;
1855                         if (j >= 0 && j + 1 < FIRST_PSEUDO_REGISTER
1856                             && k < FIRST_PSEUDO_REGISTER
1857                             && spill_reg_order[j] < 0 && spill_reg_order[j + 1] < 0
1858                             && TEST_HARD_REG_BIT (reg_class_contents[class], j)
1859                             && TEST_HARD_REG_BIT (reg_class_contents[class], j + 1)
1860                             && HARD_REGNO_MODE_OK (j, group_mode[class])
1861                             && ! TEST_HARD_REG_BIT (counted_for_nongroups,
1862                                                     j + 1)
1863                             && ! TEST_HARD_REG_BIT (bad_spill_regs, j + 1))
1864                           break;
1865                       }
1866
1867                   /* I should be the index in potential_reload_regs
1868                      of the new reload reg we have found.  */
1869
1870                   if (i >= FIRST_PSEUDO_REGISTER)
1871                     {
1872                       /* There are no groups left to spill.  */
1873                       spill_failure (max_groups_insn[class]);
1874                       failure = 1;
1875                       goto failed;
1876                     }
1877                   else
1878                     something_changed
1879                       |= new_spill_reg (i, class, max_needs, NULL_PTR,
1880                                         global, dumpfile);
1881                 }
1882               else
1883                 {
1884                   /* For groups of more than 2 registers,
1885                      look for a sufficient sequence of unspilled registers,
1886                      and spill them all at once.  */
1887                   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1888                     {
1889                       int k;
1890
1891                       j = potential_reload_regs[i];
1892                       if (j >= 0
1893                           && j + group_size[class] <= FIRST_PSEUDO_REGISTER
1894                           && HARD_REGNO_MODE_OK (j, group_mode[class]))
1895                         {
1896                           /* Check each reg in the sequence.  */
1897                           for (k = 0; k < group_size[class]; k++)
1898                             if (! (spill_reg_order[j + k] < 0
1899                                    && ! TEST_HARD_REG_BIT (bad_spill_regs, j + k)
1900                                    && TEST_HARD_REG_BIT (reg_class_contents[class], j + k)))
1901                               break;
1902                           /* We got a full sequence, so spill them all.  */
1903                           if (k == group_size[class])
1904                             {
1905                               register enum reg_class *p;
1906                               for (k = 0; k < group_size[class]; k++)
1907                                 {
1908                                   int idx;
1909                                   SET_HARD_REG_BIT (counted_for_groups, j + k);
1910                                   for (idx = 0; idx < FIRST_PSEUDO_REGISTER; idx++)
1911                                     if (potential_reload_regs[idx] == j + k)
1912                                       break;
1913                                   something_changed
1914                                     |= new_spill_reg (idx, class,
1915                                                       max_needs, NULL_PTR,
1916                                                       global, dumpfile);
1917                                 }
1918
1919                               /* We have found one that will complete a group,
1920                                  so count off one group as provided.  */
1921                               max_groups[class]--;
1922                               p = reg_class_superclasses[class];
1923                               while (*p != LIM_REG_CLASSES)
1924                                 {
1925                                   if (group_size [(int) *p]
1926                                       <= group_size [class])
1927                                     max_groups[(int) *p]--;
1928                                   p++;
1929                                 }
1930                               break;
1931                             }
1932                         }
1933                     }
1934                   /* We couldn't find any registers for this reload.
1935                      Avoid going into an infinite loop.  */
1936                   if (i >= FIRST_PSEUDO_REGISTER)
1937                     {
1938                       /* There are no groups left.  */
1939                       spill_failure (max_groups_insn[class]);
1940                       failure = 1;
1941                       goto failed;
1942                     }
1943                 }
1944             }
1945
1946           /* Now similarly satisfy all need for single registers.  */
1947
1948           while (max_needs[class] > 0 || max_nongroups[class] > 0)
1949             {
1950               /* If we spilled enough regs, but they weren't counted
1951                  against the non-group need, see if we can count them now.
1952                  If so, we can avoid some actual spilling.  */
1953               if (max_needs[class] <= 0 && max_nongroups[class] > 0)
1954                 for (i = 0; i < n_spills; i++)
1955                   if (TEST_HARD_REG_BIT (reg_class_contents[class],
1956                                          spill_regs[i])
1957                       && !TEST_HARD_REG_BIT (counted_for_groups,
1958                                              spill_regs[i])
1959                       && !TEST_HARD_REG_BIT (counted_for_nongroups,
1960                                              spill_regs[i])
1961                       && max_nongroups[class] > 0)
1962                     {
1963                       register enum reg_class *p;
1964
1965                       SET_HARD_REG_BIT (counted_for_nongroups, spill_regs[i]);
1966                       max_nongroups[class]--;
1967                       p = reg_class_superclasses[class];
1968                       while (*p != LIM_REG_CLASSES)
1969                         max_nongroups[(int) *p++]--;
1970                     }
1971               if (max_needs[class] <= 0 && max_nongroups[class] <= 0)
1972                 break;
1973
1974               /* Consider the potential reload regs that aren't
1975                  yet in use as reload regs, in order of preference.
1976                  Find the most preferred one that's in this class.  */
1977
1978               for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1979                 if (potential_reload_regs[i] >= 0
1980                     && TEST_HARD_REG_BIT (reg_class_contents[class],
1981                                           potential_reload_regs[i])
1982                     /* If this reg will not be available for groups,
1983                        pick one that does not foreclose possible groups.
1984                        This is a kludge, and not very general,
1985                        but it should be sufficient to make the 386 work,
1986                        and the problem should not occur on machines with
1987                        more registers.  */
1988                     && (max_nongroups[class] == 0
1989                         || possible_group_p (potential_reload_regs[i], max_groups)))
1990                   break;
1991
1992               /* If we couldn't get a register, try to get one even if we
1993                  might foreclose possible groups.  This may cause problems
1994                  later, but that's better than aborting now, since it is
1995                  possible that we will, in fact, be able to form the needed
1996                  group even with this allocation.  */
1997
1998               if (i >= FIRST_PSEUDO_REGISTER
1999                   && (asm_noperands (max_needs[class] > 0
2000                                      ? max_needs_insn[class]
2001                                      : max_nongroups_insn[class])
2002                       < 0))
2003                 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2004                   if (potential_reload_regs[i] >= 0
2005                       && TEST_HARD_REG_BIT (reg_class_contents[class],
2006                                             potential_reload_regs[i]))
2007                     break;
2008
2009               /* I should be the index in potential_reload_regs
2010                  of the new reload reg we have found.  */
2011
2012               if (i >= FIRST_PSEUDO_REGISTER)
2013                 {
2014                   /* There are no possible registers left to spill.  */
2015                   spill_failure (max_needs[class] > 0 ? max_needs_insn[class]
2016                                  : max_nongroups_insn[class]);
2017                   failure = 1;
2018                   goto failed;
2019                 }
2020               else
2021                 something_changed
2022                   |= new_spill_reg (i, class, max_needs, max_nongroups,
2023                                     global, dumpfile);
2024             }
2025         }
2026     }
2027
2028   /* If global-alloc was run, notify it of any register eliminations we have
2029      done.  */
2030   if (global)
2031     for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
2032       if (ep->can_eliminate)
2033         mark_elimination (ep->from, ep->to);
2034
2035   /* Insert code to save and restore call-clobbered hard regs
2036      around calls.  Tell if what mode to use so that we will process
2037      those insns in reload_as_needed if we have to.  */
2038
2039   if (caller_save_needed)
2040     save_call_clobbered_regs (num_eliminable ? QImode
2041                               : caller_save_spill_class != NO_REGS ? HImode
2042                               : VOIDmode);
2043
2044   /* If a pseudo has no hard reg, delete the insns that made the equivalence.
2045      If that insn didn't set the register (i.e., it copied the register to
2046      memory), just delete that insn instead of the equivalencing insn plus
2047      anything now dead.  If we call delete_dead_insn on that insn, we may
2048      delete the insn that actually sets the register if the register die
2049      there and that is incorrect.  */
2050
2051   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
2052     if (reg_renumber[i] < 0 && reg_equiv_init[i] != 0
2053         && GET_CODE (reg_equiv_init[i]) != NOTE)
2054       {
2055         if (reg_set_p (regno_reg_rtx[i], PATTERN (reg_equiv_init[i])))
2056           delete_dead_insn (reg_equiv_init[i]);
2057         else
2058           {
2059             PUT_CODE (reg_equiv_init[i], NOTE);
2060             NOTE_SOURCE_FILE (reg_equiv_init[i]) = 0;
2061             NOTE_LINE_NUMBER (reg_equiv_init[i]) = NOTE_INSN_DELETED;
2062           }
2063       }
2064
2065   /* Use the reload registers where necessary
2066      by generating move instructions to move the must-be-register
2067      values into or out of the reload registers.  */
2068
2069   if (something_needs_reloads || something_needs_elimination
2070       || (caller_save_needed && num_eliminable)
2071       || caller_save_spill_class != NO_REGS)
2072     reload_as_needed (first, global);
2073
2074   /* If we were able to eliminate the frame pointer, show that it is no
2075      longer live at the start of any basic block.  If it ls live by
2076      virtue of being in a pseudo, that pseudo will be marked live
2077      and hence the frame pointer will be known to be live via that
2078      pseudo.  */
2079
2080   if (! frame_pointer_needed)
2081     for (i = 0; i < n_basic_blocks; i++)
2082       basic_block_live_at_start[i][HARD_FRAME_POINTER_REGNUM / REGSET_ELT_BITS]
2083         &= ~ ((REGSET_ELT_TYPE) 1 << (HARD_FRAME_POINTER_REGNUM
2084                                       % REGSET_ELT_BITS));
2085
2086   /* Come here (with failure set nonzero) if we can't get enough spill regs
2087      and we decide not to abort about it.  */
2088  failed:
2089
2090   reload_in_progress = 0;
2091
2092   /* Now eliminate all pseudo regs by modifying them into
2093      their equivalent memory references.
2094      The REG-rtx's for the pseudos are modified in place,
2095      so all insns that used to refer to them now refer to memory.
2096
2097      For a reg that has a reg_equiv_address, all those insns
2098      were changed by reloading so that no insns refer to it any longer;
2099      but the DECL_RTL of a variable decl may refer to it,
2100      and if so this causes the debugging info to mention the variable.  */
2101
2102   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
2103     {
2104       rtx addr = 0;
2105       int in_struct = 0;
2106       if (reg_equiv_mem[i])
2107         {
2108           addr = XEXP (reg_equiv_mem[i], 0);
2109           in_struct = MEM_IN_STRUCT_P (reg_equiv_mem[i]);
2110         }
2111       if (reg_equiv_address[i])
2112         addr = reg_equiv_address[i];
2113       if (addr)
2114         {
2115           if (reg_renumber[i] < 0)
2116             {
2117               rtx reg = regno_reg_rtx[i];
2118               XEXP (reg, 0) = addr;
2119               REG_USERVAR_P (reg) = 0;
2120               MEM_IN_STRUCT_P (reg) = in_struct;
2121               PUT_CODE (reg, MEM);
2122             }
2123           else if (reg_equiv_mem[i])
2124             XEXP (reg_equiv_mem[i], 0) = addr;
2125         }
2126     }
2127
2128   /* Do a very simple CSE pass over just the hard registers.  */
2129   if (optimize > 0)
2130     reload_cse_regs (first);
2131
2132 #ifdef PRESERVE_DEATH_INFO_REGNO_P
2133   /* Make a pass over all the insns and remove death notes for things that
2134      are no longer registers or no longer die in the insn (e.g., an input
2135      and output pseudo being tied).  */
2136
2137   for (insn = first; insn; insn = NEXT_INSN (insn))
2138     if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
2139       {
2140         rtx note, next;
2141
2142         for (note = REG_NOTES (insn); note; note = next)
2143           {
2144             next = XEXP (note, 1);
2145             if (REG_NOTE_KIND (note) == REG_DEAD
2146                 && (GET_CODE (XEXP (note, 0)) != REG
2147                     || reg_set_p (XEXP (note, 0), PATTERN (insn))))
2148               remove_note (insn, note);
2149           }
2150       }
2151 #endif
2152
2153   /* Indicate that we no longer have known memory locations or constants.  */
2154   reg_equiv_constant = 0;
2155   reg_equiv_memory_loc = 0;
2156
2157   if (scratch_list)
2158     free (scratch_list);
2159   scratch_list = 0;
2160   if (scratch_block)
2161     free (scratch_block);
2162   scratch_block = 0;
2163
2164   CLEAR_HARD_REG_SET (used_spill_regs);
2165   for (i = 0; i < n_spills; i++)
2166     SET_HARD_REG_BIT (used_spill_regs, spill_regs[i]);
2167
2168   return failure;
2169 }
2170 \f
2171 /* Nonzero if, after spilling reg REGNO for non-groups,
2172    it will still be possible to find a group if we still need one.  */
2173
2174 static int
2175 possible_group_p (regno, max_groups)
2176      int regno;
2177      int *max_groups;
2178 {
2179   int i;
2180   int class = (int) NO_REGS;
2181
2182   for (i = 0; i < (int) N_REG_CLASSES; i++)
2183     if (max_groups[i] > 0)
2184       {
2185         class = i;
2186         break;
2187       }
2188
2189   if (class == (int) NO_REGS)
2190     return 1;
2191
2192   /* Consider each pair of consecutive registers.  */
2193   for (i = 0; i < FIRST_PSEUDO_REGISTER - 1; i++)
2194     {
2195       /* Ignore pairs that include reg REGNO.  */
2196       if (i == regno || i + 1 == regno)
2197         continue;
2198
2199       /* Ignore pairs that are outside the class that needs the group.
2200          ??? Here we fail to handle the case where two different classes
2201          independently need groups.  But this never happens with our
2202          current machine descriptions.  */
2203       if (! (TEST_HARD_REG_BIT (reg_class_contents[class], i)
2204              && TEST_HARD_REG_BIT (reg_class_contents[class], i + 1)))
2205         continue;
2206
2207       /* A pair of consecutive regs we can still spill does the trick.  */
2208       if (spill_reg_order[i] < 0 && spill_reg_order[i + 1] < 0
2209           && ! TEST_HARD_REG_BIT (bad_spill_regs, i)
2210           && ! TEST_HARD_REG_BIT (bad_spill_regs, i + 1))
2211         return 1;
2212
2213       /* A pair of one already spilled and one we can spill does it
2214          provided the one already spilled is not otherwise reserved.  */
2215       if (spill_reg_order[i] < 0
2216           && ! TEST_HARD_REG_BIT (bad_spill_regs, i)
2217           && spill_reg_order[i + 1] >= 0
2218           && ! TEST_HARD_REG_BIT (counted_for_groups, i + 1)
2219           && ! TEST_HARD_REG_BIT (counted_for_nongroups, i + 1))
2220         return 1;
2221       if (spill_reg_order[i + 1] < 0
2222           && ! TEST_HARD_REG_BIT (bad_spill_regs, i + 1)
2223           && spill_reg_order[i] >= 0
2224           && ! TEST_HARD_REG_BIT (counted_for_groups, i)
2225           && ! TEST_HARD_REG_BIT (counted_for_nongroups, i))
2226         return 1;
2227     }
2228
2229   return 0;
2230 }
2231 \f
2232 /* Count any groups of CLASS that can be formed from the registers recently
2233    spilled.  */
2234
2235 static void
2236 count_possible_groups (group_size, group_mode, max_groups, class)
2237      int *group_size;
2238      enum machine_mode *group_mode;
2239      int *max_groups;
2240      int class;
2241 {
2242   HARD_REG_SET new;
2243   int i, j;
2244
2245   /* Now find all consecutive groups of spilled registers
2246      and mark each group off against the need for such groups.
2247      But don't count them against ordinary need, yet.  */
2248
2249   if (group_size[class] == 0)
2250     return;
2251
2252   CLEAR_HARD_REG_SET (new);
2253
2254   /* Make a mask of all the regs that are spill regs in class I.  */
2255   for (i = 0; i < n_spills; i++)
2256     if (TEST_HARD_REG_BIT (reg_class_contents[class], spill_regs[i])
2257         && ! TEST_HARD_REG_BIT (counted_for_groups, spill_regs[i])
2258         && ! TEST_HARD_REG_BIT (counted_for_nongroups, spill_regs[i]))
2259       SET_HARD_REG_BIT (new, spill_regs[i]);
2260
2261   /* Find each consecutive group of them.  */
2262   for (i = 0; i < FIRST_PSEUDO_REGISTER && max_groups[class] > 0; i++)
2263     if (TEST_HARD_REG_BIT (new, i)
2264         && i + group_size[class] <= FIRST_PSEUDO_REGISTER
2265         && HARD_REGNO_MODE_OK (i, group_mode[class]))
2266       {
2267         for (j = 1; j < group_size[class]; j++)
2268           if (! TEST_HARD_REG_BIT (new, i + j))
2269             break;
2270
2271         if (j == group_size[class])
2272           {
2273             /* We found a group.  Mark it off against this class's need for
2274                groups, and against each superclass too.  */
2275             register enum reg_class *p;
2276
2277             max_groups[class]--;
2278             p = reg_class_superclasses[class];
2279             while (*p != LIM_REG_CLASSES)
2280               {
2281                 if (group_size [(int) *p] <= group_size [class])
2282                   max_groups[(int) *p]--;
2283                 p++;
2284               }
2285
2286             /* Don't count these registers again.  */
2287             for (j = 0; j < group_size[class]; j++)
2288               SET_HARD_REG_BIT (counted_for_groups, i + j);
2289           }
2290
2291         /* Skip to the last reg in this group.  When i is incremented above,
2292            it will then point to the first reg of the next possible group.  */
2293         i += j - 1;
2294       }
2295 }
2296 \f
2297 /* ALLOCATE_MODE is a register mode that needs to be reloaded.  OTHER_MODE is
2298    another mode that needs to be reloaded for the same register class CLASS.
2299    If any reg in CLASS allows ALLOCATE_MODE but not OTHER_MODE, fail.
2300    ALLOCATE_MODE will never be smaller than OTHER_MODE.
2301
2302    This code used to also fail if any reg in CLASS allows OTHER_MODE but not
2303    ALLOCATE_MODE.  This test is unnecessary, because we will never try to put
2304    something of mode ALLOCATE_MODE into an OTHER_MODE register.  Testing this
2305    causes unnecessary failures on machines requiring alignment of register
2306    groups when the two modes are different sizes, because the larger mode has
2307    more strict alignment rules than the smaller mode.  */
2308
2309 static int
2310 modes_equiv_for_class_p (allocate_mode, other_mode, class)
2311      enum machine_mode allocate_mode, other_mode;
2312      enum reg_class class;
2313 {
2314   register int regno;
2315   for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
2316     {
2317       if (TEST_HARD_REG_BIT (reg_class_contents[(int) class], regno)
2318           && HARD_REGNO_MODE_OK (regno, allocate_mode)
2319           && ! HARD_REGNO_MODE_OK (regno, other_mode))
2320         return 0;
2321     }
2322   return 1;
2323 }
2324
2325 /* Handle the failure to find a register to spill.
2326    INSN should be one of the insns which needed this particular spill reg.  */
2327
2328 static void
2329 spill_failure (insn)
2330      rtx insn;
2331 {
2332   if (asm_noperands (PATTERN (insn)) >= 0)
2333     error_for_asm (insn, "`asm' needs too many reloads");
2334   else
2335     fatal_insn ("Unable to find a register to spill.", insn);
2336 }
2337
2338 /* Add a new register to the tables of available spill-registers
2339     (as well as spilling all pseudos allocated to the register).
2340    I is the index of this register in potential_reload_regs.
2341    CLASS is the regclass whose need is being satisfied.
2342    MAX_NEEDS and MAX_NONGROUPS are the vectors of needs,
2343     so that this register can count off against them.
2344     MAX_NONGROUPS is 0 if this register is part of a group.
2345    GLOBAL and DUMPFILE are the same as the args that `reload' got.  */
2346
2347 static int
2348 new_spill_reg (i, class, max_needs, max_nongroups, global, dumpfile)
2349      int i;
2350      int class;
2351      int *max_needs;
2352      int *max_nongroups;
2353      int global;
2354      FILE *dumpfile;
2355 {
2356   register enum reg_class *p;
2357   int val;
2358   int regno = potential_reload_regs[i];
2359
2360   if (i >= FIRST_PSEUDO_REGISTER)
2361     abort ();   /* Caller failed to find any register.  */
2362
2363   if (fixed_regs[regno] || TEST_HARD_REG_BIT (forbidden_regs, regno))
2364     fatal ("fixed or forbidden register was spilled.\n\
2365 This may be due to a compiler bug or to impossible asm\n\
2366 statements or clauses.");
2367
2368   /* Make reg REGNO an additional reload reg.  */
2369
2370   potential_reload_regs[i] = -1;
2371   spill_regs[n_spills] = regno;
2372   spill_reg_order[regno] = n_spills;
2373   if (dumpfile)
2374     fprintf (dumpfile, "Spilling reg %d.\n", spill_regs[n_spills]);
2375
2376   /* Clear off the needs we just satisfied.  */
2377
2378   max_needs[class]--;
2379   p = reg_class_superclasses[class];
2380   while (*p != LIM_REG_CLASSES)
2381     max_needs[(int) *p++]--;
2382
2383   if (max_nongroups && max_nongroups[class] > 0)
2384     {
2385       SET_HARD_REG_BIT (counted_for_nongroups, regno);
2386       max_nongroups[class]--;
2387       p = reg_class_superclasses[class];
2388       while (*p != LIM_REG_CLASSES)
2389         max_nongroups[(int) *p++]--;
2390     }
2391
2392   /* Spill every pseudo reg that was allocated to this reg
2393      or to something that overlaps this reg.  */
2394
2395   val = spill_hard_reg (spill_regs[n_spills], global, dumpfile, 0);
2396
2397   /* If there are some registers still to eliminate and this register
2398      wasn't ever used before, additional stack space may have to be
2399      allocated to store this register.  Thus, we may have changed the offset
2400      between the stack and frame pointers, so mark that something has changed.
2401      (If new pseudos were spilled, thus requiring more space, VAL would have
2402      been set non-zero by the call to spill_hard_reg above since additional
2403      reloads may be needed in that case.
2404
2405      One might think that we need only set VAL to 1 if this is a call-used
2406      register.  However, the set of registers that must be saved by the
2407      prologue is not identical to the call-used set.  For example, the
2408      register used by the call insn for the return PC is a call-used register,
2409      but must be saved by the prologue.  */
2410   if (num_eliminable && ! regs_ever_live[spill_regs[n_spills]])
2411     val = 1;
2412
2413   regs_ever_live[spill_regs[n_spills]] = 1;
2414   n_spills++;
2415
2416   return val;
2417 }
2418 \f
2419 /* Delete an unneeded INSN and any previous insns who sole purpose is loading
2420    data that is dead in INSN.  */
2421
2422 static void
2423 delete_dead_insn (insn)
2424      rtx insn;
2425 {
2426   rtx prev = prev_real_insn (insn);
2427   rtx prev_dest;
2428
2429   /* If the previous insn sets a register that dies in our insn, delete it
2430      too.  */
2431   if (prev && GET_CODE (PATTERN (prev)) == SET
2432       && (prev_dest = SET_DEST (PATTERN (prev)), GET_CODE (prev_dest) == REG)
2433       && reg_mentioned_p (prev_dest, PATTERN (insn))
2434       && find_regno_note (insn, REG_DEAD, REGNO (prev_dest)))
2435     delete_dead_insn (prev);
2436
2437   PUT_CODE (insn, NOTE);
2438   NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
2439   NOTE_SOURCE_FILE (insn) = 0;
2440 }
2441
2442 /* Modify the home of pseudo-reg I.
2443    The new home is present in reg_renumber[I].
2444
2445    FROM_REG may be the hard reg that the pseudo-reg is being spilled from;
2446    or it may be -1, meaning there is none or it is not relevant.
2447    This is used so that all pseudos spilled from a given hard reg
2448    can share one stack slot.  */
2449
2450 static void
2451 alter_reg (i, from_reg)
2452      register int i;
2453      int from_reg;
2454 {
2455   /* When outputting an inline function, this can happen
2456      for a reg that isn't actually used.  */
2457   if (regno_reg_rtx[i] == 0)
2458     return;
2459
2460   /* If the reg got changed to a MEM at rtl-generation time,
2461      ignore it.  */
2462   if (GET_CODE (regno_reg_rtx[i]) != REG)
2463     return;
2464
2465   /* Modify the reg-rtx to contain the new hard reg
2466      number or else to contain its pseudo reg number.  */
2467   REGNO (regno_reg_rtx[i])
2468     = reg_renumber[i] >= 0 ? reg_renumber[i] : i;
2469
2470   /* If we have a pseudo that is needed but has no hard reg or equivalent,
2471      allocate a stack slot for it.  */
2472
2473   if (reg_renumber[i] < 0
2474       && reg_n_refs[i] > 0
2475       && reg_equiv_constant[i] == 0
2476       && reg_equiv_memory_loc[i] == 0)
2477     {
2478       register rtx x;
2479       int inherent_size = PSEUDO_REGNO_BYTES (i);
2480       int total_size = MAX (inherent_size, reg_max_ref_width[i]);
2481       int adjust = 0;
2482
2483       /* Each pseudo reg has an inherent size which comes from its own mode,
2484          and a total size which provides room for paradoxical subregs
2485          which refer to the pseudo reg in wider modes.
2486
2487          We can use a slot already allocated if it provides both
2488          enough inherent space and enough total space.
2489          Otherwise, we allocate a new slot, making sure that it has no less
2490          inherent space, and no less total space, then the previous slot.  */
2491       if (from_reg == -1)
2492         {
2493           /* No known place to spill from => no slot to reuse.  */
2494           x = assign_stack_local (GET_MODE (regno_reg_rtx[i]), total_size,
2495                                   inherent_size == total_size ? 0 : -1);
2496           if (BYTES_BIG_ENDIAN)
2497             /* Cancel the  big-endian correction done in assign_stack_local.
2498                Get the address of the beginning of the slot.
2499                This is so we can do a big-endian correction unconditionally
2500                below.  */
2501             adjust = inherent_size - total_size;
2502
2503           RTX_UNCHANGING_P (x) = RTX_UNCHANGING_P (regno_reg_rtx[i]);
2504         }
2505       /* Reuse a stack slot if possible.  */
2506       else if (spill_stack_slot[from_reg] != 0
2507                && spill_stack_slot_width[from_reg] >= total_size
2508                && (GET_MODE_SIZE (GET_MODE (spill_stack_slot[from_reg]))
2509                    >= inherent_size))
2510         x = spill_stack_slot[from_reg];
2511       /* Allocate a bigger slot.  */
2512       else
2513         {
2514           /* Compute maximum size needed, both for inherent size
2515              and for total size.  */
2516           enum machine_mode mode = GET_MODE (regno_reg_rtx[i]);
2517           rtx stack_slot;
2518           if (spill_stack_slot[from_reg])
2519             {
2520               if (GET_MODE_SIZE (GET_MODE (spill_stack_slot[from_reg]))
2521                   > inherent_size)
2522                 mode = GET_MODE (spill_stack_slot[from_reg]);
2523               if (spill_stack_slot_width[from_reg] > total_size)
2524                 total_size = spill_stack_slot_width[from_reg];
2525             }
2526           /* Make a slot with that size.  */
2527           x = assign_stack_local (mode, total_size,
2528                                   inherent_size == total_size ? 0 : -1);
2529           stack_slot = x;
2530           if (BYTES_BIG_ENDIAN)
2531             {
2532               /* Cancel the  big-endian correction done in assign_stack_local.
2533                  Get the address of the beginning of the slot.
2534                  This is so we can do a big-endian correction unconditionally
2535                  below.  */
2536               adjust = GET_MODE_SIZE (mode) - total_size;
2537               if (adjust)
2538                 stack_slot = gen_rtx (MEM, mode_for_size (total_size
2539                                                           * BITS_PER_UNIT,
2540                                                           MODE_INT, 1),
2541                                       plus_constant (XEXP (x, 0), adjust));
2542             }
2543           spill_stack_slot[from_reg] = stack_slot;
2544           spill_stack_slot_width[from_reg] = total_size;
2545         }
2546
2547       /* On a big endian machine, the "address" of the slot
2548          is the address of the low part that fits its inherent mode.  */
2549       if (BYTES_BIG_ENDIAN && inherent_size < total_size)
2550         adjust += (total_size - inherent_size);
2551
2552       /* If we have any adjustment to make, or if the stack slot is the
2553          wrong mode, make a new stack slot.  */
2554       if (adjust != 0 || GET_MODE (x) != GET_MODE (regno_reg_rtx[i]))
2555         {
2556           x = gen_rtx (MEM, GET_MODE (regno_reg_rtx[i]),
2557                        plus_constant (XEXP (x, 0), adjust));
2558           RTX_UNCHANGING_P (x) = RTX_UNCHANGING_P (regno_reg_rtx[i]);
2559         }
2560
2561       /* Save the stack slot for later.   */
2562       reg_equiv_memory_loc[i] = x;
2563     }
2564 }
2565
2566 /* Mark the slots in regs_ever_live for the hard regs
2567    used by pseudo-reg number REGNO.  */
2568
2569 void
2570 mark_home_live (regno)
2571      int regno;
2572 {
2573   register int i, lim;
2574   i = reg_renumber[regno];
2575   if (i < 0)
2576     return;
2577   lim = i + HARD_REGNO_NREGS (i, PSEUDO_REGNO_MODE (regno));
2578   while (i < lim)
2579     regs_ever_live[i++] = 1;
2580 }
2581
2582 /* Mark the registers used in SCRATCH as being live.  */
2583
2584 static void
2585 mark_scratch_live (scratch)
2586      rtx scratch;
2587 {
2588   register int i;
2589   int regno = REGNO (scratch);
2590   int lim = regno + HARD_REGNO_NREGS (regno, GET_MODE (scratch));
2591
2592   for (i = regno; i < lim; i++)
2593     regs_ever_live[i] = 1;
2594 }
2595 \f
2596 /* This function handles the tracking of elimination offsets around branches.
2597
2598    X is a piece of RTL being scanned.
2599
2600    INSN is the insn that it came from, if any.
2601
2602    INITIAL_P is non-zero if we are to set the offset to be the initial
2603    offset and zero if we are setting the offset of the label to be the
2604    current offset.  */
2605
2606 static void
2607 set_label_offsets (x, insn, initial_p)
2608      rtx x;
2609      rtx insn;
2610      int initial_p;
2611 {
2612   enum rtx_code code = GET_CODE (x);
2613   rtx tem;
2614   int i;
2615   struct elim_table *p;
2616
2617   switch (code)
2618     {
2619     case LABEL_REF:
2620       if (LABEL_REF_NONLOCAL_P (x))
2621         return;
2622
2623       x = XEXP (x, 0);
2624
2625       /* ... fall through ...  */
2626
2627     case CODE_LABEL:
2628       /* If we know nothing about this label, set the desired offsets.  Note
2629          that this sets the offset at a label to be the offset before a label
2630          if we don't know anything about the label.  This is not correct for
2631          the label after a BARRIER, but is the best guess we can make.  If
2632          we guessed wrong, we will suppress an elimination that might have
2633          been possible had we been able to guess correctly.  */
2634
2635       if (! offsets_known_at[CODE_LABEL_NUMBER (x)])
2636         {
2637           for (i = 0; i < NUM_ELIMINABLE_REGS; i++)
2638             offsets_at[CODE_LABEL_NUMBER (x)][i]
2639               = (initial_p ? reg_eliminate[i].initial_offset
2640                  : reg_eliminate[i].offset);
2641           offsets_known_at[CODE_LABEL_NUMBER (x)] = 1;
2642         }
2643
2644       /* Otherwise, if this is the definition of a label and it is
2645          preceded by a BARRIER, set our offsets to the known offset of
2646          that label.  */
2647
2648       else if (x == insn
2649                && (tem = prev_nonnote_insn (insn)) != 0
2650                && GET_CODE (tem) == BARRIER)
2651         {
2652           num_not_at_initial_offset = 0;
2653           for (i = 0; i < NUM_ELIMINABLE_REGS; i++)
2654             {
2655               reg_eliminate[i].offset = reg_eliminate[i].previous_offset
2656                 = offsets_at[CODE_LABEL_NUMBER (x)][i];
2657               if (reg_eliminate[i].can_eliminate
2658                   && (reg_eliminate[i].offset
2659                       != reg_eliminate[i].initial_offset))
2660                 num_not_at_initial_offset++;
2661             }
2662         }
2663
2664       else
2665         /* If neither of the above cases is true, compare each offset
2666            with those previously recorded and suppress any eliminations
2667            where the offsets disagree.  */
2668
2669         for (i = 0; i < NUM_ELIMINABLE_REGS; i++)
2670           if (offsets_at[CODE_LABEL_NUMBER (x)][i]
2671               != (initial_p ? reg_eliminate[i].initial_offset
2672                   : reg_eliminate[i].offset))
2673             reg_eliminate[i].can_eliminate = 0;
2674
2675       return;
2676
2677     case JUMP_INSN:
2678       set_label_offsets (PATTERN (insn), insn, initial_p);
2679
2680       /* ... fall through ...  */
2681
2682     case INSN:
2683     case CALL_INSN:
2684       /* Any labels mentioned in REG_LABEL notes can be branched to indirectly
2685          and hence must have all eliminations at their initial offsets.  */
2686       for (tem = REG_NOTES (x); tem; tem = XEXP (tem, 1))
2687         if (REG_NOTE_KIND (tem) == REG_LABEL)
2688           set_label_offsets (XEXP (tem, 0), insn, 1);
2689       return;
2690
2691     case ADDR_VEC:
2692     case ADDR_DIFF_VEC:
2693       /* Each of the labels in the address vector must be at their initial
2694          offsets.  We want the first first for ADDR_VEC and the second
2695          field for ADDR_DIFF_VEC.  */
2696
2697       for (i = 0; i < XVECLEN (x, code == ADDR_DIFF_VEC); i++)
2698         set_label_offsets (XVECEXP (x, code == ADDR_DIFF_VEC, i),
2699                            insn, initial_p);
2700       return;
2701
2702     case SET:
2703       /* We only care about setting PC.  If the source is not RETURN,
2704          IF_THEN_ELSE, or a label, disable any eliminations not at
2705          their initial offsets.  Similarly if any arm of the IF_THEN_ELSE
2706          isn't one of those possibilities.  For branches to a label,
2707          call ourselves recursively.
2708
2709          Note that this can disable elimination unnecessarily when we have
2710          a non-local goto since it will look like a non-constant jump to
2711          someplace in the current function.  This isn't a significant
2712          problem since such jumps will normally be when all elimination
2713          pairs are back to their initial offsets.  */
2714
2715       if (SET_DEST (x) != pc_rtx)
2716         return;
2717
2718       switch (GET_CODE (SET_SRC (x)))
2719         {
2720         case PC:
2721         case RETURN:
2722           return;
2723
2724         case LABEL_REF:
2725           set_label_offsets (XEXP (SET_SRC (x), 0), insn, initial_p);
2726           return;
2727
2728         case IF_THEN_ELSE:
2729           tem = XEXP (SET_SRC (x), 1);
2730           if (GET_CODE (tem) == LABEL_REF)
2731             set_label_offsets (XEXP (tem, 0), insn, initial_p);
2732           else if (GET_CODE (tem) != PC && GET_CODE (tem) != RETURN)
2733             break;
2734
2735           tem = XEXP (SET_SRC (x), 2);
2736           if (GET_CODE (tem) == LABEL_REF)
2737             set_label_offsets (XEXP (tem, 0), insn, initial_p);
2738           else if (GET_CODE (tem) != PC && GET_CODE (tem) != RETURN)
2739             break;
2740           return;
2741         }
2742
2743       /* If we reach here, all eliminations must be at their initial
2744          offset because we are doing a jump to a variable address.  */
2745       for (p = reg_eliminate; p < &reg_eliminate[NUM_ELIMINABLE_REGS]; p++)
2746         if (p->offset != p->initial_offset)
2747           p->can_eliminate = 0;
2748     }
2749 }
2750 \f
2751 /* Used for communication between the next two function to properly share
2752    the vector for an ASM_OPERANDS.  */
2753
2754 static struct rtvec_def *old_asm_operands_vec, *new_asm_operands_vec;
2755
2756 /* Scan X and replace any eliminable registers (such as fp) with a
2757    replacement (such as sp), plus an offset.
2758
2759    MEM_MODE is the mode of an enclosing MEM.  We need this to know how
2760    much to adjust a register for, e.g., PRE_DEC.  Also, if we are inside a
2761    MEM, we are allowed to replace a sum of a register and the constant zero
2762    with the register, which we cannot do outside a MEM.  In addition, we need
2763    to record the fact that a register is referenced outside a MEM.
2764
2765    If INSN is an insn, it is the insn containing X.  If we replace a REG
2766    in a SET_DEST with an equivalent MEM and INSN is non-zero, write a
2767    CLOBBER of the pseudo after INSN so find_equiv_regs will know that
2768    that the REG is being modified.
2769
2770    Alternatively, INSN may be a note (an EXPR_LIST or INSN_LIST).
2771    That's used when we eliminate in expressions stored in notes.
2772    This means, do not set ref_outside_mem even if the reference
2773    is outside of MEMs.
2774
2775    If we see a modification to a register we know about, take the
2776    appropriate action (see case SET, below).
2777
2778    REG_EQUIV_MEM and REG_EQUIV_ADDRESS contain address that have had
2779    replacements done assuming all offsets are at their initial values.  If
2780    they are not, or if REG_EQUIV_ADDRESS is nonzero for a pseudo we
2781    encounter, return the actual location so that find_reloads will do
2782    the proper thing.  */
2783
2784 rtx
2785 eliminate_regs (x, mem_mode, insn, storing)
2786      rtx x;
2787      enum machine_mode mem_mode;
2788      rtx insn;
2789      int storing;
2790 {
2791   enum rtx_code code = GET_CODE (x);
2792   struct elim_table *ep;
2793   int regno;
2794   rtx new;
2795   int i, j;
2796   char *fmt;
2797   int copied = 0;
2798
2799   switch (code)
2800     {
2801     case CONST_INT:
2802     case CONST_DOUBLE:
2803     case CONST:
2804     case SYMBOL_REF:
2805     case CODE_LABEL:
2806     case PC:
2807     case CC0:
2808     case ASM_INPUT:
2809     case ADDR_VEC:
2810     case ADDR_DIFF_VEC:
2811     case RETURN:
2812       return x;
2813
2814     case REG:
2815       regno = REGNO (x);
2816
2817       /* First handle the case where we encounter a bare register that
2818          is eliminable.  Replace it with a PLUS.  */
2819       if (regno < FIRST_PSEUDO_REGISTER)
2820         {
2821           for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
2822                ep++)
2823             if (ep->from_rtx == x && ep->can_eliminate)
2824               {
2825                 if (! mem_mode
2826                     /* Refs inside notes don't count for this purpose.  */
2827                     && ! (insn != 0 && (GET_CODE (insn) == EXPR_LIST
2828                                         || GET_CODE (insn) == INSN_LIST)))
2829                   ep->ref_outside_mem = 1;
2830                 return plus_constant (ep->to_rtx, ep->previous_offset);
2831               }
2832
2833         }
2834       else if (reg_equiv_memory_loc && reg_equiv_memory_loc[regno]
2835                && (reg_equiv_address[regno] || num_not_at_initial_offset))
2836         {
2837           /* In this case, find_reloads would attempt to either use an
2838              incorrect address (if something is not at its initial offset)
2839              or substitute an replaced address into an insn (which loses
2840              if the offset is changed by some later action).  So we simply
2841              return the replaced stack slot (assuming it is changed by
2842              elimination) and ignore the fact that this is actually a
2843              reference to the pseudo.  Ensure we make a copy of the
2844              address in case it is shared.  */
2845           new = eliminate_regs (reg_equiv_memory_loc[regno],
2846                                 mem_mode, insn, 0);
2847           if (new != reg_equiv_memory_loc[regno])
2848             {
2849               cannot_omit_stores[regno] = 1;
2850               return copy_rtx (new);
2851             }
2852         }
2853       return x;
2854
2855     case PLUS:
2856       /* If this is the sum of an eliminable register and a constant, rework
2857          the sum.   */
2858       if (GET_CODE (XEXP (x, 0)) == REG
2859           && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER
2860           && CONSTANT_P (XEXP (x, 1)))
2861         {
2862           for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
2863                ep++)
2864             if (ep->from_rtx == XEXP (x, 0) && ep->can_eliminate)
2865               {
2866                 if (! mem_mode
2867                     /* Refs inside notes don't count for this purpose.  */
2868                     && ! (insn != 0 && (GET_CODE (insn) == EXPR_LIST
2869                                         || GET_CODE (insn) == INSN_LIST)))
2870                   ep->ref_outside_mem = 1;
2871
2872                 /* The only time we want to replace a PLUS with a REG (this
2873                    occurs when the constant operand of the PLUS is the negative
2874                    of the offset) is when we are inside a MEM.  We won't want
2875                    to do so at other times because that would change the
2876                    structure of the insn in a way that reload can't handle.
2877                    We special-case the commonest situation in
2878                    eliminate_regs_in_insn, so just replace a PLUS with a
2879                    PLUS here, unless inside a MEM.  */
2880                 if (mem_mode != 0 && GET_CODE (XEXP (x, 1)) == CONST_INT
2881                     && INTVAL (XEXP (x, 1)) == - ep->previous_offset)
2882                   return ep->to_rtx;
2883                 else
2884                   return gen_rtx (PLUS, Pmode, ep->to_rtx,
2885                                   plus_constant (XEXP (x, 1),
2886                                                  ep->previous_offset));
2887               }
2888
2889           /* If the register is not eliminable, we are done since the other
2890              operand is a constant.  */
2891           return x;
2892         }
2893
2894       /* If this is part of an address, we want to bring any constant to the
2895          outermost PLUS.  We will do this by doing register replacement in
2896          our operands and seeing if a constant shows up in one of them.
2897
2898          We assume here this is part of an address (or a "load address" insn)
2899          since an eliminable register is not likely to appear in any other
2900          context.
2901
2902          If we have (plus (eliminable) (reg)), we want to produce
2903          (plus (plus (replacement) (reg) (const))).  If this was part of a
2904          normal add insn, (plus (replacement) (reg)) will be pushed as a
2905          reload.  This is the desired action.  */
2906
2907       {
2908         rtx new0 = eliminate_regs (XEXP (x, 0), mem_mode, insn, 0);
2909         rtx new1 = eliminate_regs (XEXP (x, 1), mem_mode, insn, 0);
2910
2911         if (new0 != XEXP (x, 0) || new1 != XEXP (x, 1))
2912           {
2913             /* If one side is a PLUS and the other side is a pseudo that
2914                didn't get a hard register but has a reg_equiv_constant,
2915                we must replace the constant here since it may no longer
2916                be in the position of any operand.  */
2917             if (GET_CODE (new0) == PLUS && GET_CODE (new1) == REG
2918                 && REGNO (new1) >= FIRST_PSEUDO_REGISTER
2919                 && reg_renumber[REGNO (new1)] < 0
2920                 && reg_equiv_constant != 0
2921                 && reg_equiv_constant[REGNO (new1)] != 0)
2922               new1 = reg_equiv_constant[REGNO (new1)];
2923             else if (GET_CODE (new1) == PLUS && GET_CODE (new0) == REG
2924                      && REGNO (new0) >= FIRST_PSEUDO_REGISTER
2925                      && reg_renumber[REGNO (new0)] < 0
2926                      && reg_equiv_constant[REGNO (new0)] != 0)
2927               new0 = reg_equiv_constant[REGNO (new0)];
2928
2929             new = form_sum (new0, new1);
2930
2931             /* As above, if we are not inside a MEM we do not want to
2932                turn a PLUS into something else.  We might try to do so here
2933                for an addition of 0 if we aren't optimizing.  */
2934             if (! mem_mode && GET_CODE (new) != PLUS)
2935               return gen_rtx (PLUS, GET_MODE (x), new, const0_rtx);
2936             else
2937               return new;
2938           }
2939       }
2940       return x;
2941
2942     case MULT:
2943       /* If this is the product of an eliminable register and a 
2944          constant, apply the distribute law and move the constant out
2945          so that we have (plus (mult ..) ..).  This is needed in order
2946          to keep load-address insns valid.   This case is pathological.
2947          We ignore the possibility of overflow here.  */
2948       if (GET_CODE (XEXP (x, 0)) == REG
2949           && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER
2950           && GET_CODE (XEXP (x, 1)) == CONST_INT)
2951         for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
2952              ep++)
2953           if (ep->from_rtx == XEXP (x, 0) && ep->can_eliminate)
2954             {
2955               if (! mem_mode
2956                   /* Refs inside notes don't count for this purpose.  */
2957                   && ! (insn != 0 && (GET_CODE (insn) == EXPR_LIST
2958                                       || GET_CODE (insn) == INSN_LIST)))
2959                 ep->ref_outside_mem = 1;
2960
2961               return
2962                 plus_constant (gen_rtx (MULT, Pmode, ep->to_rtx, XEXP (x, 1)),
2963                                ep->previous_offset * INTVAL (XEXP (x, 1)));
2964             }
2965
2966       /* ... fall through ...  */
2967
2968     case CALL:
2969     case COMPARE:
2970     case MINUS:
2971     case DIV:      case UDIV:
2972     case MOD:      case UMOD:
2973     case AND:      case IOR:      case XOR:
2974     case ROTATERT: case ROTATE:
2975     case ASHIFTRT: case LSHIFTRT: case ASHIFT:
2976     case NE:       case EQ:
2977     case GE:       case GT:       case GEU:    case GTU:
2978     case LE:       case LT:       case LEU:    case LTU:
2979       {
2980         rtx new0 = eliminate_regs (XEXP (x, 0), mem_mode, insn, 0);
2981         rtx new1
2982           = XEXP (x, 1) ? eliminate_regs (XEXP (x, 1), mem_mode, insn, 0) : 0;
2983
2984         if (new0 != XEXP (x, 0) || new1 != XEXP (x, 1))
2985           return gen_rtx (code, GET_MODE (x), new0, new1);
2986       }
2987       return x;
2988
2989     case EXPR_LIST:
2990       /* If we have something in XEXP (x, 0), the usual case, eliminate it.  */
2991       if (XEXP (x, 0))
2992         {
2993           new = eliminate_regs (XEXP (x, 0), mem_mode, insn, 0);
2994           if (new != XEXP (x, 0))
2995             x = gen_rtx (EXPR_LIST, REG_NOTE_KIND (x), new, XEXP (x, 1));
2996         }
2997
2998       /* ... fall through ...  */
2999
3000     case INSN_LIST:
3001       /* Now do eliminations in the rest of the chain.  If this was
3002          an EXPR_LIST, this might result in allocating more memory than is
3003          strictly needed, but it simplifies the code.  */
3004       if (XEXP (x, 1))
3005         {
3006           new = eliminate_regs (XEXP (x, 1), mem_mode, insn, 0);
3007           if (new != XEXP (x, 1))
3008             return gen_rtx (GET_CODE (x), GET_MODE (x), XEXP (x, 0), new);
3009         }
3010       return x;
3011
3012     case PRE_INC:
3013     case POST_INC:
3014     case PRE_DEC:
3015     case POST_DEC:
3016       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
3017         if (ep->to_rtx == XEXP (x, 0))
3018           {
3019             int size = GET_MODE_SIZE (mem_mode);
3020
3021             /* If more bytes than MEM_MODE are pushed, account for them.  */
3022 #ifdef PUSH_ROUNDING
3023             if (ep->to_rtx == stack_pointer_rtx)
3024               size = PUSH_ROUNDING (size);
3025 #endif
3026             if (code == PRE_DEC || code == POST_DEC)
3027               ep->offset += size;
3028             else
3029               ep->offset -= size;
3030           }
3031
3032       /* Fall through to generic unary operation case.  */
3033     case STRICT_LOW_PART:
3034     case NEG:          case NOT:
3035     case SIGN_EXTEND:  case ZERO_EXTEND:
3036     case TRUNCATE:     case FLOAT_EXTEND: case FLOAT_TRUNCATE:
3037     case FLOAT:        case FIX:
3038     case UNSIGNED_FIX: case UNSIGNED_FLOAT:
3039     case ABS:
3040     case SQRT:
3041     case FFS:
3042       new = eliminate_regs (XEXP (x, 0), mem_mode, insn, 0);
3043       if (new != XEXP (x, 0))
3044         return gen_rtx (code, GET_MODE (x), new);
3045       return x;
3046
3047     case SUBREG:
3048       /* Similar to above processing, but preserve SUBREG_WORD.
3049          Convert (subreg (mem)) to (mem) if not paradoxical.
3050          Also, if we have a non-paradoxical (subreg (pseudo)) and the
3051          pseudo didn't get a hard reg, we must replace this with the
3052          eliminated version of the memory location because push_reloads
3053          may do the replacement in certain circumstances.  */
3054       if (GET_CODE (SUBREG_REG (x)) == REG
3055           && (GET_MODE_SIZE (GET_MODE (x))
3056               <= GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
3057           && reg_equiv_memory_loc != 0
3058           && reg_equiv_memory_loc[REGNO (SUBREG_REG (x))] != 0)
3059         {
3060           new = eliminate_regs (reg_equiv_memory_loc[REGNO (SUBREG_REG (x))],
3061                                 mem_mode, insn, 0);
3062
3063           /* If we didn't change anything, we must retain the pseudo.  */
3064           if (new == reg_equiv_memory_loc[REGNO (SUBREG_REG (x))])
3065             new = SUBREG_REG (x);
3066           else
3067             {
3068               /* Otherwise, ensure NEW isn't shared in case we have to reload
3069                  it.  */
3070               new = copy_rtx (new);
3071
3072               /* In this case, we must show that the pseudo is used in this
3073                  insn so that delete_output_reload will do the right thing.  */
3074               if (insn != 0 && GET_CODE (insn) != EXPR_LIST
3075                   && GET_CODE (insn) != INSN_LIST)
3076                 emit_insn_before (gen_rtx (USE, VOIDmode, SUBREG_REG (x)),
3077                                   insn);
3078             }
3079         }
3080       else
3081         new = eliminate_regs (SUBREG_REG (x), mem_mode, insn, 0);
3082
3083       if (new != XEXP (x, 0))
3084         {
3085           int x_size = GET_MODE_SIZE (GET_MODE (x));
3086           int new_size = GET_MODE_SIZE (GET_MODE (new));
3087
3088           /* When asked to spill a partial word subreg, we need to go
3089              ahead and spill the whole thing against the possibility
3090              that we reload the whole reg and find garbage at the top.  */
3091           if (storing
3092               && GET_CODE (new) == MEM
3093               && x_size < new_size
3094               && ((x_size + UNITS_PER_WORD-1) / UNITS_PER_WORD
3095                   == (new_size + UNITS_PER_WORD-1) / UNITS_PER_WORD))
3096             return new;
3097           else if (GET_CODE (new) == MEM
3098                    && x_size <= new_size
3099 #ifdef LOAD_EXTEND_OP
3100                    /* On these machines we will be reloading what is
3101                       inside the SUBREG if it originally was a pseudo and
3102                       the inner and outer modes are both a word or
3103                       smaller.  So leave the SUBREG then.  */
3104                    && ! (GET_CODE (SUBREG_REG (x)) == REG
3105                          && x_size <= UNITS_PER_WORD
3106                          && new_size <= UNITS_PER_WORD
3107                          && x_size > new_size
3108                          && INTEGRAL_MODE_P (GET_MODE (new))
3109                          && LOAD_EXTEND_OP (GET_MODE (new)) != NIL)
3110 #endif
3111                    )
3112             {
3113               int offset = SUBREG_WORD (x) * UNITS_PER_WORD;
3114               enum machine_mode mode = GET_MODE (x);
3115
3116               if (BYTES_BIG_ENDIAN)
3117                 offset += (MIN (UNITS_PER_WORD,
3118                                 GET_MODE_SIZE (GET_MODE (new)))
3119                            - MIN (UNITS_PER_WORD, GET_MODE_SIZE (mode)));
3120
3121               PUT_MODE (new, mode);
3122               XEXP (new, 0) = plus_constant (XEXP (new, 0), offset);
3123               return new;
3124             }
3125           else
3126             return gen_rtx (SUBREG, GET_MODE (x), new, SUBREG_WORD (x));
3127         }
3128
3129       return x;
3130
3131     case USE:
3132       /* If using a register that is the source of an eliminate we still
3133          think can be performed, note it cannot be performed since we don't
3134          know how this register is used.  */
3135       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
3136         if (ep->from_rtx == XEXP (x, 0))
3137           ep->can_eliminate = 0;
3138
3139       new = eliminate_regs (XEXP (x, 0), mem_mode, insn, 0);
3140       if (new != XEXP (x, 0))
3141         return gen_rtx (code, GET_MODE (x), new);
3142       return x;
3143
3144     case CLOBBER:
3145       /* If clobbering a register that is the replacement register for an
3146          elimination we still think can be performed, note that it cannot
3147          be performed.  Otherwise, we need not be concerned about it.  */
3148       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
3149         if (ep->to_rtx == XEXP (x, 0))
3150           ep->can_eliminate = 0;
3151
3152       new = eliminate_regs (XEXP (x, 0), mem_mode, insn, 0);
3153       if (new != XEXP (x, 0))
3154         return gen_rtx (code, GET_MODE (x), new);
3155       return x;
3156
3157     case ASM_OPERANDS:
3158       {
3159         rtx *temp_vec;
3160         /* Properly handle sharing input and constraint vectors.  */
3161         if (ASM_OPERANDS_INPUT_VEC (x) != old_asm_operands_vec)
3162           {
3163             /* When we come to a new vector not seen before,
3164                scan all its elements; keep the old vector if none
3165                of them changes; otherwise, make a copy.  */
3166             old_asm_operands_vec = ASM_OPERANDS_INPUT_VEC (x);
3167             temp_vec = (rtx *) alloca (XVECLEN (x, 3) * sizeof (rtx));
3168             for (i = 0; i < ASM_OPERANDS_INPUT_LENGTH (x); i++)
3169               temp_vec[i] = eliminate_regs (ASM_OPERANDS_INPUT (x, i),
3170                                             mem_mode, insn, 0);
3171
3172             for (i = 0; i < ASM_OPERANDS_INPUT_LENGTH (x); i++)
3173               if (temp_vec[i] != ASM_OPERANDS_INPUT (x, i))
3174                 break;
3175
3176             if (i == ASM_OPERANDS_INPUT_LENGTH (x))
3177               new_asm_operands_vec = old_asm_operands_vec;
3178             else