OSDN Git Service

717489f3216c216612261e94abf991282f0123df
[pf3gnuchains/gcc-fork.git] / gcc / reload1.c
1 /* Reload pseudo regs into hard regs for insns that require hard regs.
2    Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3    1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING.  If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, USA.  */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26
27 #include "machmode.h"
28 #include "hard-reg-set.h"
29 #include "rtl.h"
30 #include "tm_p.h"
31 #include "obstack.h"
32 #include "insn-config.h"
33 #include "flags.h"
34 #include "function.h"
35 #include "expr.h"
36 #include "optabs.h"
37 #include "regs.h"
38 #include "basic-block.h"
39 #include "reload.h"
40 #include "recog.h"
41 #include "output.h"
42 #include "real.h"
43 #include "toplev.h"
44 #include "except.h"
45 #include "tree.h"
46
47 /* This file contains the reload pass of the compiler, which is
48    run after register allocation has been done.  It checks that
49    each insn is valid (operands required to be in registers really
50    are in registers of the proper class) and fixes up invalid ones
51    by copying values temporarily into registers for the insns
52    that need them.
53
54    The results of register allocation are described by the vector
55    reg_renumber; the insns still contain pseudo regs, but reg_renumber
56    can be used to find which hard reg, if any, a pseudo reg is in.
57
58    The technique we always use is to free up a few hard regs that are
59    called ``reload regs'', and for each place where a pseudo reg
60    must be in a hard reg, copy it temporarily into one of the reload regs.
61
62    Reload regs are allocated locally for every instruction that needs
63    reloads.  When there are pseudos which are allocated to a register that
64    has been chosen as a reload reg, such pseudos must be ``spilled''.
65    This means that they go to other hard regs, or to stack slots if no other
66    available hard regs can be found.  Spilling can invalidate more
67    insns, requiring additional need for reloads, so we must keep checking
68    until the process stabilizes.
69
70    For machines with different classes of registers, we must keep track
71    of the register class needed for each reload, and make sure that
72    we allocate enough reload registers of each class.
73
74    The file reload.c contains the code that checks one insn for
75    validity and reports the reloads that it needs.  This file
76    is in charge of scanning the entire rtl code, accumulating the
77    reload needs, spilling, assigning reload registers to use for
78    fixing up each insn, and generating the new insns to copy values
79    into the reload registers.  */
80
81 #ifndef LOCAL_REGNO
82 #define LOCAL_REGNO(REGNO)  0
83 #endif
84 \f
85 /* During reload_as_needed, element N contains a REG rtx for the hard reg
86    into which reg N has been reloaded (perhaps for a previous insn).  */
87 static rtx *reg_last_reload_reg;
88
89 /* Elt N nonzero if reg_last_reload_reg[N] has been set in this insn
90    for an output reload that stores into reg N.  */
91 static char *reg_has_output_reload;
92
93 /* Indicates which hard regs are reload-registers for an output reload
94    in the current insn.  */
95 static HARD_REG_SET reg_is_output_reload;
96
97 /* Element N is the constant value to which pseudo reg N is equivalent,
98    or zero if pseudo reg N is not equivalent to a constant.
99    find_reloads looks at this in order to replace pseudo reg N
100    with the constant it stands for.  */
101 rtx *reg_equiv_constant;
102
103 /* Element N is a memory location to which pseudo reg N is equivalent,
104    prior to any register elimination (such as frame pointer to stack
105    pointer).  Depending on whether or not it is a valid address, this value
106    is transferred to either reg_equiv_address or reg_equiv_mem.  */
107 rtx *reg_equiv_memory_loc;
108
109 /* Element N is the address of stack slot to which pseudo reg N is equivalent.
110    This is used when the address is not valid as a memory address
111    (because its displacement is too big for the machine.)  */
112 rtx *reg_equiv_address;
113
114 /* Element N is the memory slot to which pseudo reg N is equivalent,
115    or zero if pseudo reg N is not equivalent to a memory slot.  */
116 rtx *reg_equiv_mem;
117
118 /* Widest width in which each pseudo reg is referred to (via subreg).  */
119 static unsigned int *reg_max_ref_width;
120
121 /* Element N is the list of insns that initialized reg N from its equivalent
122    constant or memory slot.  */
123 static rtx *reg_equiv_init;
124
125 /* Vector to remember old contents of reg_renumber before spilling.  */
126 static short *reg_old_renumber;
127
128 /* During reload_as_needed, element N contains the last pseudo regno reloaded
129    into hard register N.  If that pseudo reg occupied more than one register,
130    reg_reloaded_contents points to that pseudo for each spill register in
131    use; all of these must remain set for an inheritance to occur.  */
132 static int reg_reloaded_contents[FIRST_PSEUDO_REGISTER];
133
134 /* During reload_as_needed, element N contains the insn for which
135    hard register N was last used.   Its contents are significant only
136    when reg_reloaded_valid is set for this register.  */
137 static rtx reg_reloaded_insn[FIRST_PSEUDO_REGISTER];
138
139 /* Indicate if reg_reloaded_insn / reg_reloaded_contents is valid.  */
140 static HARD_REG_SET reg_reloaded_valid;
141 /* Indicate if the register was dead at the end of the reload.
142    This is only valid if reg_reloaded_contents is set and valid.  */
143 static HARD_REG_SET reg_reloaded_dead;
144
145 /* Number of spill-regs so far; number of valid elements of spill_regs.  */
146 static int n_spills;
147
148 /* In parallel with spill_regs, contains REG rtx's for those regs.
149    Holds the last rtx used for any given reg, or 0 if it has never
150    been used for spilling yet.  This rtx is reused, provided it has
151    the proper mode.  */
152 static rtx spill_reg_rtx[FIRST_PSEUDO_REGISTER];
153
154 /* In parallel with spill_regs, contains nonzero for a spill reg
155    that was stored after the last time it was used.
156    The precise value is the insn generated to do the store.  */
157 static rtx spill_reg_store[FIRST_PSEUDO_REGISTER];
158
159 /* This is the register that was stored with spill_reg_store.  This is a
160    copy of reload_out / reload_out_reg when the value was stored; if
161    reload_out is a MEM, spill_reg_stored_to will be set to reload_out_reg.  */
162 static rtx spill_reg_stored_to[FIRST_PSEUDO_REGISTER];
163
164 /* This table is the inverse mapping of spill_regs:
165    indexed by hard reg number,
166    it contains the position of that reg in spill_regs,
167    or -1 for something that is not in spill_regs.
168
169    ?!?  This is no longer accurate.  */
170 static short spill_reg_order[FIRST_PSEUDO_REGISTER];
171
172 /* This reg set indicates registers that can't be used as spill registers for
173    the currently processed insn.  These are the hard registers which are live
174    during the insn, but not allocated to pseudos, as well as fixed
175    registers.  */
176 static HARD_REG_SET bad_spill_regs;
177
178 /* These are the hard registers that can't be used as spill register for any
179    insn.  This includes registers used for user variables and registers that
180    we can't eliminate.  A register that appears in this set also can't be used
181    to retry register allocation.  */
182 static HARD_REG_SET bad_spill_regs_global;
183
184 /* Describes order of use of registers for reloading
185    of spilled pseudo-registers.  `n_spills' is the number of
186    elements that are actually valid; new ones are added at the end.
187
188    Both spill_regs and spill_reg_order are used on two occasions:
189    once during find_reload_regs, where they keep track of the spill registers
190    for a single insn, but also during reload_as_needed where they show all
191    the registers ever used by reload.  For the latter case, the information
192    is calculated during finish_spills.  */
193 static short spill_regs[FIRST_PSEUDO_REGISTER];
194
195 /* This vector of reg sets indicates, for each pseudo, which hard registers
196    may not be used for retrying global allocation because the register was
197    formerly spilled from one of them.  If we allowed reallocating a pseudo to
198    a register that it was already allocated to, reload might not
199    terminate.  */
200 static HARD_REG_SET *pseudo_previous_regs;
201
202 /* This vector of reg sets indicates, for each pseudo, which hard
203    registers may not be used for retrying global allocation because they
204    are used as spill registers during one of the insns in which the
205    pseudo is live.  */
206 static HARD_REG_SET *pseudo_forbidden_regs;
207
208 /* All hard regs that have been used as spill registers for any insn are
209    marked in this set.  */
210 static HARD_REG_SET used_spill_regs;
211
212 /* Index of last register assigned as a spill register.  We allocate in
213    a round-robin fashion.  */
214 static int last_spill_reg;
215
216 /* Nonzero if indirect addressing is supported on the machine; this means
217    that spilling (REG n) does not require reloading it into a register in
218    order to do (MEM (REG n)) or (MEM (PLUS (REG n) (CONST_INT c))).  The
219    value indicates the level of indirect addressing supported, e.g., two
220    means that (MEM (MEM (REG n))) is also valid if (REG n) does not get
221    a hard register.  */
222 static char spill_indirect_levels;
223
224 /* Nonzero if indirect addressing is supported when the innermost MEM is
225    of the form (MEM (SYMBOL_REF sym)).  It is assumed that the level to
226    which these are valid is the same as spill_indirect_levels, above.  */
227 char indirect_symref_ok;
228
229 /* Nonzero if an address (plus (reg frame_pointer) (reg ...)) is valid.  */
230 char double_reg_address_ok;
231
232 /* Record the stack slot for each spilled hard register.  */
233 static rtx spill_stack_slot[FIRST_PSEUDO_REGISTER];
234
235 /* Width allocated so far for that stack slot.  */
236 static unsigned int spill_stack_slot_width[FIRST_PSEUDO_REGISTER];
237
238 /* Record which pseudos needed to be spilled.  */
239 static regset_head spilled_pseudos;
240
241 /* Used for communication between order_regs_for_reload and count_pseudo.
242    Used to avoid counting one pseudo twice.  */
243 static regset_head pseudos_counted;
244
245 /* First uid used by insns created by reload in this function.
246    Used in find_equiv_reg.  */
247 int reload_first_uid;
248
249 /* Flag set by local-alloc or global-alloc if anything is live in
250    a call-clobbered reg across calls.  */
251 int caller_save_needed;
252
253 /* Set to 1 while reload_as_needed is operating.
254    Required by some machines to handle any generated moves differently.  */
255 int reload_in_progress = 0;
256
257 /* These arrays record the insn_code of insns that may be needed to
258    perform input and output reloads of special objects.  They provide a
259    place to pass a scratch register.  */
260 enum insn_code reload_in_optab[NUM_MACHINE_MODES];
261 enum insn_code reload_out_optab[NUM_MACHINE_MODES];
262
263 /* This obstack is used for allocation of rtl during register elimination.
264    The allocated storage can be freed once find_reloads has processed the
265    insn.  */
266 struct obstack reload_obstack;
267
268 /* Points to the beginning of the reload_obstack.  All insn_chain structures
269    are allocated first.  */
270 char *reload_startobj;
271
272 /* The point after all insn_chain structures.  Used to quickly deallocate
273    memory allocated in copy_reloads during calculate_needs_all_insns.  */
274 char *reload_firstobj;
275
276 /* This points before all local rtl generated by register elimination.
277    Used to quickly free all memory after processing one insn.  */
278 static char *reload_insn_firstobj;
279
280 /* List of insn_chain instructions, one for every insn that reload needs to
281    examine.  */
282 struct insn_chain *reload_insn_chain;
283
284 /* List of all insns needing reloads.  */
285 static struct insn_chain *insns_need_reload;
286 \f
287 /* This structure is used to record information about register eliminations.
288    Each array entry describes one possible way of eliminating a register
289    in favor of another.   If there is more than one way of eliminating a
290    particular register, the most preferred should be specified first.  */
291
292 struct elim_table
293 {
294   int from;                     /* Register number to be eliminated.  */
295   int to;                       /* Register number used as replacement.  */
296   HOST_WIDE_INT initial_offset; /* Initial difference between values.  */
297   int can_eliminate;            /* Nonzero if this elimination can be done.  */
298   int can_eliminate_previous;   /* Value of CAN_ELIMINATE in previous scan over
299                                    insns made by reload.  */
300   HOST_WIDE_INT offset;         /* Current offset between the two regs.  */
301   HOST_WIDE_INT previous_offset;/* Offset at end of previous insn.  */
302   int ref_outside_mem;          /* "to" has been referenced outside a MEM.  */
303   rtx from_rtx;                 /* REG rtx for the register to be eliminated.
304                                    We cannot simply compare the number since
305                                    we might then spuriously replace a hard
306                                    register corresponding to a pseudo
307                                    assigned to the reg to be eliminated.  */
308   rtx to_rtx;                   /* REG rtx for the replacement.  */
309 };
310
311 static struct elim_table *reg_eliminate = 0;
312
313 /* This is an intermediate structure to initialize the table.  It has
314    exactly the members provided by ELIMINABLE_REGS.  */
315 static const struct elim_table_1
316 {
317   const int from;
318   const int to;
319 } reg_eliminate_1[] =
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 ARRAY_SIZE (reg_eliminate_1)
332
333 /* Record the number of pending eliminations that have an offset not equal
334    to their initial offset.  If nonzero, we use a new copy of each
335    replacement result in any insns encountered.  */
336 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 /* And the number of registers that are equivalent to a constant that
341    can be eliminated to frame_pointer / arg_pointer + constant.  */
342 static int num_eliminable_invariants;
343
344 /* For each label, we record the offset of each elimination.  If we reach
345    a label by more than one path and an offset differs, we cannot do the
346    elimination.  This information is indexed by the difference of the
347    number of the label and the first label number.  We can't offset the
348    pointer itself as this can cause problems on machines with segmented
349    memory.  The first table is an array of flags that records whether we
350    have yet encountered a label and the second table is an array of arrays,
351    one entry in the latter array for each elimination.  */
352
353 static int first_label_num;
354 static char *offsets_known_at;
355 static HOST_WIDE_INT (*offsets_at)[NUM_ELIMINABLE_REGS];
356
357 /* Number of labels in the current function.  */
358
359 static int num_labels;
360 \f
361 static void replace_pseudos_in (rtx *, enum machine_mode, rtx);
362 static void maybe_fix_stack_asms (void);
363 static void copy_reloads (struct insn_chain *);
364 static void calculate_needs_all_insns (int);
365 static int find_reg (struct insn_chain *, int);
366 static void find_reload_regs (struct insn_chain *);
367 static void select_reload_regs (void);
368 static void delete_caller_save_insns (void);
369
370 static void spill_failure (rtx, enum reg_class);
371 static void count_spilled_pseudo (int, int, int);
372 static void delete_dead_insn (rtx);
373 static void alter_reg (int, int);
374 static void set_label_offsets (rtx, rtx, int);
375 static void check_eliminable_occurrences (rtx);
376 static void elimination_effects (rtx, enum machine_mode);
377 static int eliminate_regs_in_insn (rtx, int);
378 static void update_eliminable_offsets (void);
379 static void mark_not_eliminable (rtx, rtx, void *);
380 static void set_initial_elim_offsets (void);
381 static void verify_initial_elim_offsets (void);
382 static void set_initial_label_offsets (void);
383 static void set_offsets_for_label (rtx);
384 static void init_elim_table (void);
385 static void update_eliminables (HARD_REG_SET *);
386 static void spill_hard_reg (unsigned int, int);
387 static int finish_spills (int);
388 static void ior_hard_reg_set (HARD_REG_SET *, HARD_REG_SET *);
389 static void scan_paradoxical_subregs (rtx);
390 static void count_pseudo (int);
391 static void order_regs_for_reload (struct insn_chain *);
392 static void reload_as_needed (int);
393 static void forget_old_reloads_1 (rtx, rtx, void *);
394 static int reload_reg_class_lower (const void *, const void *);
395 static void mark_reload_reg_in_use (unsigned int, int, enum reload_type,
396                                     enum machine_mode);
397 static void clear_reload_reg_in_use (unsigned int, int, enum reload_type,
398                                      enum machine_mode);
399 static int reload_reg_free_p (unsigned int, int, enum reload_type);
400 static int reload_reg_free_for_value_p (int, int, int, enum reload_type,
401                                         rtx, rtx, int, int);
402 static int free_for_value_p (int, enum machine_mode, int, enum reload_type,
403                              rtx, rtx, int, int);
404 static int reload_reg_reaches_end_p (unsigned int, int, enum reload_type);
405 static int allocate_reload_reg (struct insn_chain *, int, int);
406 static int conflicts_with_override (rtx);
407 static void failed_reload (rtx, int);
408 static int set_reload_reg (int, int);
409 static void choose_reload_regs_init (struct insn_chain *, rtx *);
410 static void choose_reload_regs (struct insn_chain *);
411 static void merge_assigned_reloads (rtx);
412 static void emit_input_reload_insns (struct insn_chain *, struct reload *,
413                                      rtx, int);
414 static void emit_output_reload_insns (struct insn_chain *, struct reload *,
415                                       int);
416 static void do_input_reload (struct insn_chain *, struct reload *, int);
417 static void do_output_reload (struct insn_chain *, struct reload *, int);
418 static void emit_reload_insns (struct insn_chain *);
419 static void delete_output_reload (rtx, int, int);
420 static void delete_address_reloads (rtx, rtx);
421 static void delete_address_reloads_1 (rtx, rtx, rtx);
422 static rtx inc_for_reload (rtx, rtx, rtx, int);
423 #ifdef AUTO_INC_DEC
424 static void add_auto_inc_notes (rtx, rtx);
425 #endif
426 static void copy_eh_notes (rtx, rtx);
427 \f
428 /* Initialize the reload pass once per compilation.  */
429
430 void
431 init_reload (void)
432 {
433   int i;
434
435   /* Often (MEM (REG n)) is still valid even if (REG n) is put on the stack.
436      Set spill_indirect_levels to the number of levels such addressing is
437      permitted, zero if it is not permitted at all.  */
438
439   rtx tem
440     = gen_rtx_MEM (Pmode,
441                    gen_rtx_PLUS (Pmode,
442                                  gen_rtx_REG (Pmode,
443                                               LAST_VIRTUAL_REGISTER + 1),
444                                  GEN_INT (4)));
445   spill_indirect_levels = 0;
446
447   while (memory_address_p (QImode, tem))
448     {
449       spill_indirect_levels++;
450       tem = gen_rtx_MEM (Pmode, tem);
451     }
452
453   /* See if indirect addressing is valid for (MEM (SYMBOL_REF ...)).  */
454
455   tem = gen_rtx_MEM (Pmode, gen_rtx_SYMBOL_REF (Pmode, "foo"));
456   indirect_symref_ok = memory_address_p (QImode, tem);
457
458   /* See if reg+reg is a valid (and offsettable) address.  */
459
460   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
461     {
462       tem = gen_rtx_PLUS (Pmode,
463                           gen_rtx_REG (Pmode, HARD_FRAME_POINTER_REGNUM),
464                           gen_rtx_REG (Pmode, i));
465
466       /* This way, we make sure that reg+reg is an offsettable address.  */
467       tem = plus_constant (tem, 4);
468
469       if (memory_address_p (QImode, tem))
470         {
471           double_reg_address_ok = 1;
472           break;
473         }
474     }
475
476   /* Initialize obstack for our rtl allocation.  */
477   gcc_obstack_init (&reload_obstack);
478   reload_startobj = obstack_alloc (&reload_obstack, 0);
479
480   INIT_REG_SET (&spilled_pseudos);
481   INIT_REG_SET (&pseudos_counted);
482 }
483
484 /* List of insn chains that are currently unused.  */
485 static struct insn_chain *unused_insn_chains = 0;
486
487 /* Allocate an empty insn_chain structure.  */
488 struct insn_chain *
489 new_insn_chain (void)
490 {
491   struct insn_chain *c;
492
493   if (unused_insn_chains == 0)
494     {
495       c = obstack_alloc (&reload_obstack, sizeof (struct insn_chain));
496       INIT_REG_SET (&c->live_throughout);
497       INIT_REG_SET (&c->dead_or_set);
498     }
499   else
500     {
501       c = unused_insn_chains;
502       unused_insn_chains = c->next;
503     }
504   c->is_caller_save_insn = 0;
505   c->need_operand_change = 0;
506   c->need_reload = 0;
507   c->need_elim = 0;
508   return c;
509 }
510
511 /* Small utility function to set all regs in hard reg set TO which are
512    allocated to pseudos in regset FROM.  */
513
514 void
515 compute_use_by_pseudos (HARD_REG_SET *to, regset from)
516 {
517   unsigned int regno;
518
519   EXECUTE_IF_SET_IN_REG_SET
520     (from, FIRST_PSEUDO_REGISTER, regno,
521      {
522        int r = reg_renumber[regno];
523        int nregs;
524
525        if (r < 0)
526          {
527            /* reload_combine uses the information from
528               BASIC_BLOCK->global_live_at_start, which might still
529               contain registers that have not actually been allocated
530               since they have an equivalence.  */
531            if (! reload_completed)
532              abort ();
533          }
534        else
535          {
536            nregs = HARD_REGNO_NREGS (r, PSEUDO_REGNO_MODE (regno));
537            while (nregs-- > 0)
538              SET_HARD_REG_BIT (*to, r + nregs);
539          }
540      });
541 }
542
543 /* Replace all pseudos found in LOC with their corresponding
544    equivalences.  */
545
546 static void
547 replace_pseudos_in (rtx *loc, enum machine_mode mem_mode, rtx usage)
548 {
549   rtx x = *loc;
550   enum rtx_code code;
551   const char *fmt;
552   int i, j;
553
554   if (! x)
555     return;
556
557   code = GET_CODE (x);
558   if (code == REG)
559     {
560       unsigned int regno = REGNO (x);
561
562       if (regno < FIRST_PSEUDO_REGISTER)
563         return;
564
565       x = eliminate_regs (x, mem_mode, usage);
566       if (x != *loc)
567         {
568           *loc = x;
569           replace_pseudos_in (loc, mem_mode, usage);
570           return;
571         }
572
573       if (reg_equiv_constant[regno])
574         *loc = reg_equiv_constant[regno];
575       else if (reg_equiv_mem[regno])
576         *loc = reg_equiv_mem[regno];
577       else if (reg_equiv_address[regno])
578         *loc = gen_rtx_MEM (GET_MODE (x), reg_equiv_address[regno]);
579       else if (GET_CODE (regno_reg_rtx[regno]) != REG
580                || REGNO (regno_reg_rtx[regno]) != regno)
581         *loc = regno_reg_rtx[regno];
582       else
583         abort ();
584
585       return;
586     }
587   else if (code == MEM)
588     {
589       replace_pseudos_in (& XEXP (x, 0), GET_MODE (x), usage);
590       return;
591     }
592
593   /* Process each of our operands recursively.  */
594   fmt = GET_RTX_FORMAT (code);
595   for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
596     if (*fmt == 'e')
597       replace_pseudos_in (&XEXP (x, i), mem_mode, usage);
598     else if (*fmt == 'E')
599       for (j = 0; j < XVECLEN (x, i); j++)
600         replace_pseudos_in (& XVECEXP (x, i, j), mem_mode, usage);
601 }
602
603 \f
604 /* Global variables used by reload and its subroutines.  */
605
606 /* Set during calculate_needs if an insn needs register elimination.  */
607 static int something_needs_elimination;
608 /* Set during calculate_needs if an insn needs an operand changed.  */
609 int something_needs_operands_changed;
610
611 /* Nonzero means we couldn't get enough spill regs.  */
612 static int failure;
613
614 /* Main entry point for the reload pass.
615
616    FIRST is the first insn of the function being compiled.
617
618    GLOBAL nonzero means we were called from global_alloc
619    and should attempt to reallocate any pseudoregs that we
620    displace from hard regs we will use for reloads.
621    If GLOBAL is zero, we do not have enough information to do that,
622    so any pseudo reg that is spilled must go to the stack.
623
624    Return value is nonzero if reload failed
625    and we must not do any more for this function.  */
626
627 int
628 reload (rtx first, int global)
629 {
630   int i;
631   rtx insn;
632   struct elim_table *ep;
633   basic_block bb;
634
635   /* Make sure even insns with volatile mem refs are recognizable.  */
636   init_recog ();
637
638   failure = 0;
639
640   reload_firstobj = obstack_alloc (&reload_obstack, 0);
641
642   /* Make sure that the last insn in the chain
643      is not something that needs reloading.  */
644   emit_note (NOTE_INSN_DELETED);
645
646   /* Enable find_equiv_reg to distinguish insns made by reload.  */
647   reload_first_uid = get_max_uid ();
648
649 #ifdef SECONDARY_MEMORY_NEEDED
650   /* Initialize the secondary memory table.  */
651   clear_secondary_mem ();
652 #endif
653
654   /* We don't have a stack slot for any spill reg yet.  */
655   memset (spill_stack_slot, 0, sizeof spill_stack_slot);
656   memset (spill_stack_slot_width, 0, sizeof spill_stack_slot_width);
657
658   /* Initialize the save area information for caller-save, in case some
659      are needed.  */
660   init_save_areas ();
661
662   /* Compute which hard registers are now in use
663      as homes for pseudo registers.
664      This is done here rather than (eg) in global_alloc
665      because this point is reached even if not optimizing.  */
666   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
667     mark_home_live (i);
668
669   /* A function that receives a nonlocal goto must save all call-saved
670      registers.  */
671   if (current_function_has_nonlocal_label)
672     for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
673       if (! call_used_regs[i] && ! fixed_regs[i] && ! LOCAL_REGNO (i))
674         regs_ever_live[i] = 1;
675
676   /* Find all the pseudo registers that didn't get hard regs
677      but do have known equivalent constants or memory slots.
678      These include parameters (known equivalent to parameter slots)
679      and cse'd or loop-moved constant memory addresses.
680
681      Record constant equivalents in reg_equiv_constant
682      so they will be substituted by find_reloads.
683      Record memory equivalents in reg_mem_equiv so they can
684      be substituted eventually by altering the REG-rtx's.  */
685
686   reg_equiv_constant = xcalloc (max_regno, sizeof (rtx));
687   reg_equiv_mem = xcalloc (max_regno, sizeof (rtx));
688   reg_equiv_init = xcalloc (max_regno, sizeof (rtx));
689   reg_equiv_address = xcalloc (max_regno, sizeof (rtx));
690   reg_max_ref_width = xcalloc (max_regno, sizeof (int));
691   reg_old_renumber = xcalloc (max_regno, sizeof (short));
692   memcpy (reg_old_renumber, reg_renumber, max_regno * sizeof (short));
693   pseudo_forbidden_regs = xmalloc (max_regno * sizeof (HARD_REG_SET));
694   pseudo_previous_regs = xcalloc (max_regno, sizeof (HARD_REG_SET));
695
696   CLEAR_HARD_REG_SET (bad_spill_regs_global);
697
698   /* Look for REG_EQUIV notes; record what each pseudo is equivalent to.
699      Also find all paradoxical subregs and find largest such for each pseudo.
700      On machines with small register classes, record hard registers that
701      are used for user variables.  These can never be used for spills.
702      Also look for a "constant" REG_SETJMP.  This means that all
703      caller-saved registers must be marked live.  */
704
705   num_eliminable_invariants = 0;
706   for (insn = first; insn; insn = NEXT_INSN (insn))
707     {
708       rtx set = single_set (insn);
709
710       /* We may introduce USEs that we want to remove at the end, so
711          we'll mark them with QImode.  Make sure there are no
712          previously-marked insns left by say regmove.  */
713       if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == USE
714           && GET_MODE (insn) != VOIDmode)
715         PUT_MODE (insn, VOIDmode);
716
717       if (GET_CODE (insn) == CALL_INSN
718           && find_reg_note (insn, REG_SETJMP, NULL))
719         for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
720           if (! call_used_regs[i])
721             regs_ever_live[i] = 1;
722
723       if (set != 0 && GET_CODE (SET_DEST (set)) == REG)
724         {
725           rtx note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
726           if (note
727 #ifdef LEGITIMATE_PIC_OPERAND_P
728               && (! function_invariant_p (XEXP (note, 0))
729                   || ! flag_pic
730                   /* A function invariant is often CONSTANT_P but may
731                      include a register.  We promise to only pass
732                      CONSTANT_P objects to LEGITIMATE_PIC_OPERAND_P.  */
733                   || (CONSTANT_P (XEXP (note, 0))
734                       && LEGITIMATE_PIC_OPERAND_P (XEXP (note, 0))))
735 #endif
736               )
737             {
738               rtx x = XEXP (note, 0);
739               i = REGNO (SET_DEST (set));
740               if (i > LAST_VIRTUAL_REGISTER)
741                 {
742                   /* It can happen that a REG_EQUIV note contains a MEM
743                      that is not a legitimate memory operand.  As later
744                      stages of reload assume that all addresses found
745                      in the reg_equiv_* arrays were originally legitimate,
746                      we ignore such REG_EQUIV notes.  */
747                   if (memory_operand (x, VOIDmode))
748                     {
749                       /* Always unshare the equivalence, so we can
750                          substitute into this insn without touching the
751                          equivalence.  */
752                       reg_equiv_memory_loc[i] = copy_rtx (x);
753                     }
754                   else if (function_invariant_p (x))
755                     {
756                       if (GET_CODE (x) == PLUS)
757                         {
758                           /* This is PLUS of frame pointer and a constant,
759                              and might be shared.  Unshare it.  */
760                           reg_equiv_constant[i] = copy_rtx (x);
761                           num_eliminable_invariants++;
762                         }
763                       else if (x == frame_pointer_rtx
764                                || x == arg_pointer_rtx)
765                         {
766                           reg_equiv_constant[i] = x;
767                           num_eliminable_invariants++;
768                         }
769                       else if (LEGITIMATE_CONSTANT_P (x))
770                         reg_equiv_constant[i] = x;
771                       else
772                         {
773                           reg_equiv_memory_loc[i]
774                             = force_const_mem (GET_MODE (SET_DEST (set)), x);
775                           if (!reg_equiv_memory_loc[i])
776                             continue;
777                         }
778                     }
779                   else
780                     continue;
781
782                   /* If this register is being made equivalent to a MEM
783                      and the MEM is not SET_SRC, the equivalencing insn
784                      is one with the MEM as a SET_DEST and it occurs later.
785                      So don't mark this insn now.  */
786                   if (GET_CODE (x) != MEM
787                       || rtx_equal_p (SET_SRC (set), x))
788                     reg_equiv_init[i]
789                       = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init[i]);
790                 }
791             }
792         }
793
794       /* If this insn is setting a MEM from a register equivalent to it,
795          this is the equivalencing insn.  */
796       else if (set && GET_CODE (SET_DEST (set)) == MEM
797                && GET_CODE (SET_SRC (set)) == REG
798                && reg_equiv_memory_loc[REGNO (SET_SRC (set))]
799                && rtx_equal_p (SET_DEST (set),
800                                reg_equiv_memory_loc[REGNO (SET_SRC (set))]))
801         reg_equiv_init[REGNO (SET_SRC (set))]
802           = gen_rtx_INSN_LIST (VOIDmode, insn,
803                                reg_equiv_init[REGNO (SET_SRC (set))]);
804
805       if (INSN_P (insn))
806         scan_paradoxical_subregs (PATTERN (insn));
807     }
808
809   init_elim_table ();
810
811   first_label_num = get_first_label_num ();
812   num_labels = max_label_num () - first_label_num;
813
814   /* Allocate the tables used to store offset information at labels.  */
815   /* We used to use alloca here, but the size of what it would try to
816      allocate would occasionally cause it to exceed the stack limit and
817      cause a core dump.  */
818   offsets_known_at = xmalloc (num_labels);
819   offsets_at = xmalloc (num_labels * NUM_ELIMINABLE_REGS * sizeof (HOST_WIDE_INT));
820
821   /* Alter each pseudo-reg rtx to contain its hard reg number.
822      Assign stack slots to the pseudos that lack hard regs or equivalents.
823      Do not touch virtual registers.  */
824
825   for (i = LAST_VIRTUAL_REGISTER + 1; i < max_regno; i++)
826     alter_reg (i, -1);
827
828   /* If we have some registers we think can be eliminated, scan all insns to
829      see if there is an insn that sets one of these registers to something
830      other than itself plus a constant.  If so, the register cannot be
831      eliminated.  Doing this scan here eliminates an extra pass through the
832      main reload loop in the most common case where register elimination
833      cannot be done.  */
834   for (insn = first; insn && num_eliminable; insn = NEXT_INSN (insn))
835     if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN
836         || GET_CODE (insn) == CALL_INSN)
837       note_stores (PATTERN (insn), mark_not_eliminable, NULL);
838
839   maybe_fix_stack_asms ();
840
841   insns_need_reload = 0;
842   something_needs_elimination = 0;
843
844   /* Initialize to -1, which means take the first spill register.  */
845   last_spill_reg = -1;
846
847   /* Spill any hard regs that we know we can't eliminate.  */
848   CLEAR_HARD_REG_SET (used_spill_regs);
849   for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
850     if (! ep->can_eliminate)
851       spill_hard_reg (ep->from, 1);
852
853 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
854   if (frame_pointer_needed)
855     spill_hard_reg (HARD_FRAME_POINTER_REGNUM, 1);
856 #endif
857   finish_spills (global);
858
859   /* From now on, we may need to generate moves differently.  We may also
860      allow modifications of insns which cause them to not be recognized.
861      Any such modifications will be cleaned up during reload itself.  */
862   reload_in_progress = 1;
863
864   /* This loop scans the entire function each go-round
865      and repeats until one repetition spills no additional hard regs.  */
866   for (;;)
867     {
868       int something_changed;
869       int did_spill;
870
871       HOST_WIDE_INT starting_frame_size;
872
873       /* Round size of stack frame to stack_alignment_needed.  This must be done
874          here because the stack size may be a part of the offset computation
875          for register elimination, and there might have been new stack slots
876          created in the last iteration of this loop.  */
877       if (cfun->stack_alignment_needed)
878         assign_stack_local (BLKmode, 0, cfun->stack_alignment_needed);
879
880       starting_frame_size = get_frame_size ();
881
882       set_initial_elim_offsets ();
883       set_initial_label_offsets ();
884
885       /* For each pseudo register that has an equivalent location defined,
886          try to eliminate any eliminable registers (such as the frame pointer)
887          assuming initial offsets for the replacement register, which
888          is the normal case.
889
890          If the resulting location is directly addressable, substitute
891          the MEM we just got directly for the old REG.
892
893          If it is not addressable but is a constant or the sum of a hard reg
894          and constant, it is probably not addressable because the constant is
895          out of range, in that case record the address; we will generate
896          hairy code to compute the address in a register each time it is
897          needed.  Similarly if it is a hard register, but one that is not
898          valid as an address register.
899
900          If the location is not addressable, but does not have one of the
901          above forms, assign a stack slot.  We have to do this to avoid the
902          potential of producing lots of reloads if, e.g., a location involves
903          a pseudo that didn't get a hard register and has an equivalent memory
904          location that also involves a pseudo that didn't get a hard register.
905
906          Perhaps at some point we will improve reload_when_needed handling
907          so this problem goes away.  But that's very hairy.  */
908
909       for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
910         if (reg_renumber[i] < 0 && reg_equiv_memory_loc[i])
911           {
912             rtx x = eliminate_regs (reg_equiv_memory_loc[i], 0, NULL_RTX);
913
914             if (strict_memory_address_p (GET_MODE (regno_reg_rtx[i]),
915                                          XEXP (x, 0)))
916               reg_equiv_mem[i] = x, reg_equiv_address[i] = 0;
917             else if (CONSTANT_P (XEXP (x, 0))
918                      || (GET_CODE (XEXP (x, 0)) == REG
919                          && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER)
920                      || (GET_CODE (XEXP (x, 0)) == PLUS
921                          && GET_CODE (XEXP (XEXP (x, 0), 0)) == REG
922                          && (REGNO (XEXP (XEXP (x, 0), 0))
923                              < FIRST_PSEUDO_REGISTER)
924                          && CONSTANT_P (XEXP (XEXP (x, 0), 1))))
925               reg_equiv_address[i] = XEXP (x, 0), reg_equiv_mem[i] = 0;
926             else
927               {
928                 /* Make a new stack slot.  Then indicate that something
929                    changed so we go back and recompute offsets for
930                    eliminable registers because the allocation of memory
931                    below might change some offset.  reg_equiv_{mem,address}
932                    will be set up for this pseudo on the next pass around
933                    the loop.  */
934                 reg_equiv_memory_loc[i] = 0;
935                 reg_equiv_init[i] = 0;
936                 alter_reg (i, -1);
937               }
938           }
939
940       if (caller_save_needed)
941         setup_save_areas ();
942
943       /* If we allocated another stack slot, redo elimination bookkeeping.  */
944       if (starting_frame_size != get_frame_size ())
945         continue;
946
947       if (caller_save_needed)
948         {
949           save_call_clobbered_regs ();
950           /* That might have allocated new insn_chain structures.  */
951           reload_firstobj = obstack_alloc (&reload_obstack, 0);
952         }
953
954       calculate_needs_all_insns (global);
955
956       CLEAR_REG_SET (&spilled_pseudos);
957       did_spill = 0;
958
959       something_changed = 0;
960
961       /* If we allocated any new memory locations, make another pass
962          since it might have changed elimination offsets.  */
963       if (starting_frame_size != get_frame_size ())
964         something_changed = 1;
965
966       {
967         HARD_REG_SET to_spill;
968         CLEAR_HARD_REG_SET (to_spill);
969         update_eliminables (&to_spill);
970         for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
971           if (TEST_HARD_REG_BIT (to_spill, i))
972             {
973               spill_hard_reg (i, 1);
974               did_spill = 1;
975
976               /* Regardless of the state of spills, if we previously had
977                  a register that we thought we could eliminate, but now can
978                  not eliminate, we must run another pass.
979
980                  Consider pseudos which have an entry in reg_equiv_* which
981                  reference an eliminable register.  We must make another pass
982                  to update reg_equiv_* so that we do not substitute in the
983                  old value from when we thought the elimination could be
984                  performed.  */
985               something_changed = 1;
986             }
987       }
988
989       select_reload_regs ();
990       if (failure)
991         goto failed;
992
993       if (insns_need_reload != 0 || did_spill)
994         something_changed |= finish_spills (global);
995
996       if (! something_changed)
997         break;
998
999       if (caller_save_needed)
1000         delete_caller_save_insns ();
1001
1002       obstack_free (&reload_obstack, reload_firstobj);
1003     }
1004
1005   /* If global-alloc was run, notify it of any register eliminations we have
1006      done.  */
1007   if (global)
1008     for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
1009       if (ep->can_eliminate)
1010         mark_elimination (ep->from, ep->to);
1011
1012   /* If a pseudo has no hard reg, delete the insns that made the equivalence.
1013      If that insn didn't set the register (i.e., it copied the register to
1014      memory), just delete that insn instead of the equivalencing insn plus
1015      anything now dead.  If we call delete_dead_insn on that insn, we may
1016      delete the insn that actually sets the register if the register dies
1017      there and that is incorrect.  */
1018
1019   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1020     {
1021       if (reg_renumber[i] < 0 && reg_equiv_init[i] != 0)
1022         {
1023           rtx list;
1024           for (list = reg_equiv_init[i]; list; list = XEXP (list, 1))
1025             {
1026               rtx equiv_insn = XEXP (list, 0);
1027
1028               /* If we already deleted the insn or if it may trap, we can't
1029                  delete it.  The latter case shouldn't happen, but can
1030                  if an insn has a variable address, gets a REG_EH_REGION
1031                  note added to it, and then gets converted into an load
1032                  from a constant address.  */
1033               if (GET_CODE (equiv_insn) == NOTE
1034                   || can_throw_internal (equiv_insn))
1035                 ;
1036               else if (reg_set_p (regno_reg_rtx[i], PATTERN (equiv_insn)))
1037                 delete_dead_insn (equiv_insn);
1038               else
1039                 {
1040                   PUT_CODE (equiv_insn, NOTE);
1041                   NOTE_SOURCE_FILE (equiv_insn) = 0;
1042                   NOTE_LINE_NUMBER (equiv_insn) = NOTE_INSN_DELETED;
1043                 }
1044             }
1045         }
1046     }
1047
1048   /* Use the reload registers where necessary
1049      by generating move instructions to move the must-be-register
1050      values into or out of the reload registers.  */
1051
1052   if (insns_need_reload != 0 || something_needs_elimination
1053       || something_needs_operands_changed)
1054     {
1055       HOST_WIDE_INT old_frame_size = get_frame_size ();
1056
1057       reload_as_needed (global);
1058
1059       if (old_frame_size != get_frame_size ())
1060         abort ();
1061
1062       if (num_eliminable)
1063         verify_initial_elim_offsets ();
1064     }
1065
1066   /* If we were able to eliminate the frame pointer, show that it is no
1067      longer live at the start of any basic block.  If it ls live by
1068      virtue of being in a pseudo, that pseudo will be marked live
1069      and hence the frame pointer will be known to be live via that
1070      pseudo.  */
1071
1072   if (! frame_pointer_needed)
1073     FOR_EACH_BB (bb)
1074       CLEAR_REGNO_REG_SET (bb->global_live_at_start,
1075                            HARD_FRAME_POINTER_REGNUM);
1076
1077   /* Come here (with failure set nonzero) if we can't get enough spill regs
1078      and we decide not to abort about it.  */
1079  failed:
1080
1081   CLEAR_REG_SET (&spilled_pseudos);
1082   reload_in_progress = 0;
1083
1084   /* Now eliminate all pseudo regs by modifying them into
1085      their equivalent memory references.
1086      The REG-rtx's for the pseudos are modified in place,
1087      so all insns that used to refer to them now refer to memory.
1088
1089      For a reg that has a reg_equiv_address, all those insns
1090      were changed by reloading so that no insns refer to it any longer;
1091      but the DECL_RTL of a variable decl may refer to it,
1092      and if so this causes the debugging info to mention the variable.  */
1093
1094   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1095     {
1096       rtx addr = 0;
1097
1098       if (reg_equiv_mem[i])
1099         addr = XEXP (reg_equiv_mem[i], 0);
1100
1101       if (reg_equiv_address[i])
1102         addr = reg_equiv_address[i];
1103
1104       if (addr)
1105         {
1106           if (reg_renumber[i] < 0)
1107             {
1108               rtx reg = regno_reg_rtx[i];
1109
1110               REG_USERVAR_P (reg) = 0;
1111               PUT_CODE (reg, MEM);
1112               XEXP (reg, 0) = addr;
1113               if (reg_equiv_memory_loc[i])
1114                 MEM_COPY_ATTRIBUTES (reg, reg_equiv_memory_loc[i]);
1115               else
1116                 {
1117                   RTX_UNCHANGING_P (reg) = MEM_IN_STRUCT_P (reg)
1118                     = MEM_SCALAR_P (reg) = 0;
1119                   MEM_ATTRS (reg) = 0;
1120                 }
1121             }
1122           else if (reg_equiv_mem[i])
1123             XEXP (reg_equiv_mem[i], 0) = addr;
1124         }
1125     }
1126
1127   /* We must set reload_completed now since the cleanup_subreg_operands call
1128      below will re-recognize each insn and reload may have generated insns
1129      which are only valid during and after reload.  */
1130   reload_completed = 1;
1131
1132   /* Make a pass over all the insns and delete all USEs which we inserted
1133      only to tag a REG_EQUAL note on them.  Remove all REG_DEAD and REG_UNUSED
1134      notes.  Delete all CLOBBER insns, except those that refer to the return
1135      value and the special mem:BLK CLOBBERs added to prevent the scheduler
1136      from misarranging variable-array code, and simplify (subreg (reg))
1137      operands.  Also remove all REG_RETVAL and REG_LIBCALL notes since they
1138      are no longer useful or accurate.  Strip and regenerate REG_INC notes
1139      that may have been moved around.  */
1140
1141   for (insn = first; insn; insn = NEXT_INSN (insn))
1142     if (INSN_P (insn))
1143       {
1144         rtx *pnote;
1145
1146         if (GET_CODE (insn) == CALL_INSN)
1147           replace_pseudos_in (& CALL_INSN_FUNCTION_USAGE (insn),
1148                               VOIDmode, CALL_INSN_FUNCTION_USAGE (insn));
1149
1150         if ((GET_CODE (PATTERN (insn)) == USE
1151              /* We mark with QImode USEs introduced by reload itself.  */
1152              && (GET_MODE (insn) == QImode
1153                  || find_reg_note (insn, REG_EQUAL, NULL_RTX)))
1154             || (GET_CODE (PATTERN (insn)) == CLOBBER
1155                 && (GET_CODE (XEXP (PATTERN (insn), 0)) != MEM
1156                     || GET_MODE (XEXP (PATTERN (insn), 0)) != BLKmode
1157                     || (GET_CODE (XEXP (XEXP (PATTERN (insn), 0), 0)) != SCRATCH
1158                         && XEXP (XEXP (PATTERN (insn), 0), 0)
1159                                 != stack_pointer_rtx))
1160                 && (GET_CODE (XEXP (PATTERN (insn), 0)) != REG
1161                     || ! REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0)))))
1162           {
1163             delete_insn (insn);
1164             continue;
1165           }
1166
1167         /* Some CLOBBERs may survive until here and still reference unassigned
1168            pseudos with const equivalent, which may in turn cause ICE in later
1169            passes if the reference remains in place.  */
1170         if (GET_CODE (PATTERN (insn)) == CLOBBER)
1171           replace_pseudos_in (& XEXP (PATTERN (insn), 0),
1172                               VOIDmode, PATTERN (insn));
1173
1174         pnote = &REG_NOTES (insn);
1175         while (*pnote != 0)
1176           {
1177             if (REG_NOTE_KIND (*pnote) == REG_DEAD
1178                 || REG_NOTE_KIND (*pnote) == REG_UNUSED
1179                 || REG_NOTE_KIND (*pnote) == REG_INC
1180                 || REG_NOTE_KIND (*pnote) == REG_RETVAL
1181                 || REG_NOTE_KIND (*pnote) == REG_LIBCALL)
1182               *pnote = XEXP (*pnote, 1);
1183             else
1184               pnote = &XEXP (*pnote, 1);
1185           }
1186
1187 #ifdef AUTO_INC_DEC
1188         add_auto_inc_notes (insn, PATTERN (insn));
1189 #endif
1190
1191         /* And simplify (subreg (reg)) if it appears as an operand.  */
1192         cleanup_subreg_operands (insn);
1193       }
1194
1195   /* If we are doing stack checking, give a warning if this function's
1196      frame size is larger than we expect.  */
1197   if (flag_stack_check && ! STACK_CHECK_BUILTIN)
1198     {
1199       HOST_WIDE_INT size = get_frame_size () + STACK_CHECK_FIXED_FRAME_SIZE;
1200       static int verbose_warned = 0;
1201
1202       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1203         if (regs_ever_live[i] && ! fixed_regs[i] && call_used_regs[i])
1204           size += UNITS_PER_WORD;
1205
1206       if (size > STACK_CHECK_MAX_FRAME_SIZE)
1207         {
1208           warning ("frame size too large for reliable stack checking");
1209           if (! verbose_warned)
1210             {
1211               warning ("try reducing the number of local variables");
1212               verbose_warned = 1;
1213             }
1214         }
1215     }
1216
1217   /* Indicate that we no longer have known memory locations or constants.  */
1218   if (reg_equiv_constant)
1219     free (reg_equiv_constant);
1220   reg_equiv_constant = 0;
1221   if (reg_equiv_memory_loc)
1222     free (reg_equiv_memory_loc);
1223   reg_equiv_memory_loc = 0;
1224
1225   if (offsets_known_at)
1226     free (offsets_known_at);
1227   if (offsets_at)
1228     free (offsets_at);
1229
1230   free (reg_equiv_mem);
1231   free (reg_equiv_init);
1232   free (reg_equiv_address);
1233   free (reg_max_ref_width);
1234   free (reg_old_renumber);
1235   free (pseudo_previous_regs);
1236   free (pseudo_forbidden_regs);
1237
1238   CLEAR_HARD_REG_SET (used_spill_regs);
1239   for (i = 0; i < n_spills; i++)
1240     SET_HARD_REG_BIT (used_spill_regs, spill_regs[i]);
1241
1242   /* Free all the insn_chain structures at once.  */
1243   obstack_free (&reload_obstack, reload_startobj);
1244   unused_insn_chains = 0;
1245   fixup_abnormal_edges ();
1246
1247   /* Replacing pseudos with their memory equivalents might have
1248      created shared rtx.  Subsequent passes would get confused
1249      by this, so unshare everything here.  */
1250   unshare_all_rtl_again (first);
1251
1252   return failure;
1253 }
1254
1255 /* Yet another special case.  Unfortunately, reg-stack forces people to
1256    write incorrect clobbers in asm statements.  These clobbers must not
1257    cause the register to appear in bad_spill_regs, otherwise we'll call
1258    fatal_insn later.  We clear the corresponding regnos in the live
1259    register sets to avoid this.
1260    The whole thing is rather sick, I'm afraid.  */
1261
1262 static void
1263 maybe_fix_stack_asms (void)
1264 {
1265 #ifdef STACK_REGS
1266   const char *constraints[MAX_RECOG_OPERANDS];
1267   enum machine_mode operand_mode[MAX_RECOG_OPERANDS];
1268   struct insn_chain *chain;
1269
1270   for (chain = reload_insn_chain; chain != 0; chain = chain->next)
1271     {
1272       int i, noperands;
1273       HARD_REG_SET clobbered, allowed;
1274       rtx pat;
1275
1276       if (! INSN_P (chain->insn)
1277           || (noperands = asm_noperands (PATTERN (chain->insn))) < 0)
1278         continue;
1279       pat = PATTERN (chain->insn);
1280       if (GET_CODE (pat) != PARALLEL)
1281         continue;
1282
1283       CLEAR_HARD_REG_SET (clobbered);
1284       CLEAR_HARD_REG_SET (allowed);
1285
1286       /* First, make a mask of all stack regs that are clobbered.  */
1287       for (i = 0; i < XVECLEN (pat, 0); i++)
1288         {
1289           rtx t = XVECEXP (pat, 0, i);
1290           if (GET_CODE (t) == CLOBBER && STACK_REG_P (XEXP (t, 0)))
1291             SET_HARD_REG_BIT (clobbered, REGNO (XEXP (t, 0)));
1292         }
1293
1294       /* Get the operand values and constraints out of the insn.  */
1295       decode_asm_operands (pat, recog_data.operand, recog_data.operand_loc,
1296                            constraints, operand_mode);
1297
1298       /* For every operand, see what registers are allowed.  */
1299       for (i = 0; i < noperands; i++)
1300         {
1301           const char *p = constraints[i];
1302           /* For every alternative, we compute the class of registers allowed
1303              for reloading in CLS, and merge its contents into the reg set
1304              ALLOWED.  */
1305           int cls = (int) NO_REGS;
1306
1307           for (;;)
1308             {
1309               char c = *p;
1310
1311               if (c == '\0' || c == ',' || c == '#')
1312                 {
1313                   /* End of one alternative - mark the regs in the current
1314                      class, and reset the class.  */
1315                   IOR_HARD_REG_SET (allowed, reg_class_contents[cls]);
1316                   cls = NO_REGS;
1317                   p++;
1318                   if (c == '#')
1319                     do {
1320                       c = *p++;
1321                     } while (c != '\0' && c != ',');
1322                   if (c == '\0')
1323                     break;
1324                   continue;
1325                 }
1326
1327               switch (c)
1328                 {
1329                 case '=': case '+': case '*': case '%': case '?': case '!':
1330                 case '0': case '1': case '2': case '3': case '4': case 'm':
1331                 case '<': case '>': case 'V': case 'o': case '&': case 'E':
1332                 case 'F': case 's': case 'i': case 'n': case 'X': case 'I':
1333                 case 'J': case 'K': case 'L': case 'M': case 'N': case 'O':
1334                 case 'P':
1335                   break;
1336
1337                 case 'p':
1338                   cls = (int) reg_class_subunion[cls]
1339                     [(int) MODE_BASE_REG_CLASS (VOIDmode)];
1340                   break;
1341
1342                 case 'g':
1343                 case 'r':
1344                   cls = (int) reg_class_subunion[cls][(int) GENERAL_REGS];
1345                   break;
1346
1347                 default:
1348                   if (EXTRA_ADDRESS_CONSTRAINT (c, p))
1349                     cls = (int) reg_class_subunion[cls]
1350                       [(int) MODE_BASE_REG_CLASS (VOIDmode)];
1351                   else
1352                     cls = (int) reg_class_subunion[cls]
1353                       [(int) REG_CLASS_FROM_CONSTRAINT (c, p)];
1354                 }
1355               p += CONSTRAINT_LEN (c, p);
1356             }
1357         }
1358       /* Those of the registers which are clobbered, but allowed by the
1359          constraints, must be usable as reload registers.  So clear them
1360          out of the life information.  */
1361       AND_HARD_REG_SET (allowed, clobbered);
1362       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1363         if (TEST_HARD_REG_BIT (allowed, i))
1364           {
1365             CLEAR_REGNO_REG_SET (&chain->live_throughout, i);
1366             CLEAR_REGNO_REG_SET (&chain->dead_or_set, i);
1367           }
1368     }
1369
1370 #endif
1371 }
1372 \f
1373 /* Copy the global variables n_reloads and rld into the corresponding elts
1374    of CHAIN.  */
1375 static void
1376 copy_reloads (struct insn_chain *chain)
1377 {
1378   chain->n_reloads = n_reloads;
1379   chain->rld = obstack_alloc (&reload_obstack,
1380                               n_reloads * sizeof (struct reload));
1381   memcpy (chain->rld, rld, n_reloads * sizeof (struct reload));
1382   reload_insn_firstobj = obstack_alloc (&reload_obstack, 0);
1383 }
1384
1385 /* Walk the chain of insns, and determine for each whether it needs reloads
1386    and/or eliminations.  Build the corresponding insns_need_reload list, and
1387    set something_needs_elimination as appropriate.  */
1388 static void
1389 calculate_needs_all_insns (int global)
1390 {
1391   struct insn_chain **pprev_reload = &insns_need_reload;
1392   struct insn_chain *chain, *next = 0;
1393
1394   something_needs_elimination = 0;
1395
1396   reload_insn_firstobj = obstack_alloc (&reload_obstack, 0);
1397   for (chain = reload_insn_chain; chain != 0; chain = next)
1398     {
1399       rtx insn = chain->insn;
1400
1401       next = chain->next;
1402
1403       /* Clear out the shortcuts.  */
1404       chain->n_reloads = 0;
1405       chain->need_elim = 0;
1406       chain->need_reload = 0;
1407       chain->need_operand_change = 0;
1408
1409       /* If this is a label, a JUMP_INSN, or has REG_NOTES (which might
1410          include REG_LABEL), we need to see what effects this has on the
1411          known offsets at labels.  */
1412
1413       if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN
1414           || (INSN_P (insn) && REG_NOTES (insn) != 0))
1415         set_label_offsets (insn, insn, 0);
1416
1417       if (INSN_P (insn))
1418         {
1419           rtx old_body = PATTERN (insn);
1420           int old_code = INSN_CODE (insn);
1421           rtx old_notes = REG_NOTES (insn);
1422           int did_elimination = 0;
1423           int operands_changed = 0;
1424           rtx set = single_set (insn);
1425
1426           /* Skip insns that only set an equivalence.  */
1427           if (set && GET_CODE (SET_DEST (set)) == REG
1428               && reg_renumber[REGNO (SET_DEST (set))] < 0
1429               && reg_equiv_constant[REGNO (SET_DEST (set))])
1430             continue;
1431
1432           /* If needed, eliminate any eliminable registers.  */
1433           if (num_eliminable || num_eliminable_invariants)
1434             did_elimination = eliminate_regs_in_insn (insn, 0);
1435
1436           /* Analyze the instruction.  */
1437           operands_changed = find_reloads (insn, 0, spill_indirect_levels,
1438                                            global, spill_reg_order);
1439
1440           /* If a no-op set needs more than one reload, this is likely
1441              to be something that needs input address reloads.  We
1442              can't get rid of this cleanly later, and it is of no use
1443              anyway, so discard it now.
1444              We only do this when expensive_optimizations is enabled,
1445              since this complements reload inheritance / output
1446              reload deletion, and it can make debugging harder.  */
1447           if (flag_expensive_optimizations && n_reloads > 1)
1448             {
1449               rtx set = single_set (insn);
1450               if (set
1451                   && SET_SRC (set) == SET_DEST (set)
1452                   && GET_CODE (SET_SRC (set)) == REG
1453                   && REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER)
1454                 {
1455                   delete_insn (insn);
1456                   /* Delete it from the reload chain.  */
1457                   if (chain->prev)
1458                     chain->prev->next = next;
1459                   else
1460                     reload_insn_chain = next;
1461                   if (next)
1462                     next->prev = chain->prev;
1463                   chain->next = unused_insn_chains;
1464                   unused_insn_chains = chain;
1465                   continue;
1466                 }
1467             }
1468           if (num_eliminable)
1469             update_eliminable_offsets ();
1470
1471           /* Remember for later shortcuts which insns had any reloads or
1472              register eliminations.  */
1473           chain->need_elim = did_elimination;
1474           chain->need_reload = n_reloads > 0;
1475           chain->need_operand_change = operands_changed;
1476
1477           /* Discard any register replacements done.  */
1478           if (did_elimination)
1479             {
1480               obstack_free (&reload_obstack, reload_insn_firstobj);
1481               PATTERN (insn) = old_body;
1482               INSN_CODE (insn) = old_code;
1483               REG_NOTES (insn) = old_notes;
1484               something_needs_elimination = 1;
1485             }
1486
1487           something_needs_operands_changed |= operands_changed;
1488
1489           if (n_reloads != 0)
1490             {
1491               copy_reloads (chain);
1492               *pprev_reload = chain;
1493               pprev_reload = &chain->next_need_reload;
1494             }
1495         }
1496     }
1497   *pprev_reload = 0;
1498 }
1499 \f
1500 /* Comparison function for qsort to decide which of two reloads
1501    should be handled first.  *P1 and *P2 are the reload numbers.  */
1502
1503 static int
1504 reload_reg_class_lower (const void *r1p, const void *r2p)
1505 {
1506   int r1 = *(const short *) r1p, r2 = *(const short *) r2p;
1507   int t;
1508
1509   /* Consider required reloads before optional ones.  */
1510   t = rld[r1].optional - rld[r2].optional;
1511   if (t != 0)
1512     return t;
1513
1514   /* Count all solitary classes before non-solitary ones.  */
1515   t = ((reg_class_size[(int) rld[r2].class] == 1)
1516        - (reg_class_size[(int) rld[r1].class] == 1));
1517   if (t != 0)
1518     return t;
1519
1520   /* Aside from solitaires, consider all multi-reg groups first.  */
1521   t = rld[r2].nregs - rld[r1].nregs;
1522   if (t != 0)
1523     return t;
1524
1525   /* Consider reloads in order of increasing reg-class number.  */
1526   t = (int) rld[r1].class - (int) rld[r2].class;
1527   if (t != 0)
1528     return t;
1529
1530   /* If reloads are equally urgent, sort by reload number,
1531      so that the results of qsort leave nothing to chance.  */
1532   return r1 - r2;
1533 }
1534 \f
1535 /* The cost of spilling each hard reg.  */
1536 static int spill_cost[FIRST_PSEUDO_REGISTER];
1537
1538 /* When spilling multiple hard registers, we use SPILL_COST for the first
1539    spilled hard reg and SPILL_ADD_COST for subsequent regs.  SPILL_ADD_COST
1540    only the first hard reg for a multi-reg pseudo.  */
1541 static int spill_add_cost[FIRST_PSEUDO_REGISTER];
1542
1543 /* Update the spill cost arrays, considering that pseudo REG is live.  */
1544
1545 static void
1546 count_pseudo (int reg)
1547 {
1548   int freq = REG_FREQ (reg);
1549   int r = reg_renumber[reg];
1550   int nregs;
1551
1552   if (REGNO_REG_SET_P (&pseudos_counted, reg)
1553       || REGNO_REG_SET_P (&spilled_pseudos, reg))
1554     return;
1555
1556   SET_REGNO_REG_SET (&pseudos_counted, reg);
1557
1558   if (r < 0)
1559     abort ();
1560
1561   spill_add_cost[r] += freq;
1562
1563   nregs = HARD_REGNO_NREGS (r, PSEUDO_REGNO_MODE (reg));
1564   while (nregs-- > 0)
1565     spill_cost[r + nregs] += freq;
1566 }
1567
1568 /* Calculate the SPILL_COST and SPILL_ADD_COST arrays and determine the
1569    contents of BAD_SPILL_REGS for the insn described by CHAIN.  */
1570
1571 static void
1572 order_regs_for_reload (struct insn_chain *chain)
1573 {
1574   int i;
1575   HARD_REG_SET used_by_pseudos;
1576   HARD_REG_SET used_by_pseudos2;
1577
1578   COPY_HARD_REG_SET (bad_spill_regs, fixed_reg_set);
1579
1580   memset (spill_cost, 0, sizeof spill_cost);
1581   memset (spill_add_cost, 0, sizeof spill_add_cost);
1582
1583   /* Count number of uses of each hard reg by pseudo regs allocated to it
1584      and then order them by decreasing use.  First exclude hard registers
1585      that are live in or across this insn.  */
1586
1587   REG_SET_TO_HARD_REG_SET (used_by_pseudos, &chain->live_throughout);
1588   REG_SET_TO_HARD_REG_SET (used_by_pseudos2, &chain->dead_or_set);
1589   IOR_HARD_REG_SET (bad_spill_regs, used_by_pseudos);
1590   IOR_HARD_REG_SET (bad_spill_regs, used_by_pseudos2);
1591
1592   /* Now find out which pseudos are allocated to it, and update
1593      hard_reg_n_uses.  */
1594   CLEAR_REG_SET (&pseudos_counted);
1595
1596   EXECUTE_IF_SET_IN_REG_SET
1597     (&chain->live_throughout, FIRST_PSEUDO_REGISTER, i,
1598      {
1599        count_pseudo (i);
1600      });
1601   EXECUTE_IF_SET_IN_REG_SET
1602     (&chain->dead_or_set, FIRST_PSEUDO_REGISTER, i,
1603      {
1604        count_pseudo (i);
1605      });
1606   CLEAR_REG_SET (&pseudos_counted);
1607 }
1608 \f
1609 /* Vector of reload-numbers showing the order in which the reloads should
1610    be processed.  */
1611 static short reload_order[MAX_RELOADS];
1612
1613 /* This is used to keep track of the spill regs used in one insn.  */
1614 static HARD_REG_SET used_spill_regs_local;
1615
1616 /* We decided to spill hard register SPILLED, which has a size of
1617    SPILLED_NREGS.  Determine how pseudo REG, which is live during the insn,
1618    is affected.  We will add it to SPILLED_PSEUDOS if necessary, and we will
1619    update SPILL_COST/SPILL_ADD_COST.  */
1620
1621 static void
1622 count_spilled_pseudo (int spilled, int spilled_nregs, int reg)
1623 {
1624   int r = reg_renumber[reg];
1625   int nregs = HARD_REGNO_NREGS (r, PSEUDO_REGNO_MODE (reg));
1626
1627   if (REGNO_REG_SET_P (&spilled_pseudos, reg)
1628       || spilled + spilled_nregs <= r || r + nregs <= spilled)
1629     return;
1630
1631   SET_REGNO_REG_SET (&spilled_pseudos, reg);
1632
1633   spill_add_cost[r] -= REG_FREQ (reg);
1634   while (nregs-- > 0)
1635     spill_cost[r + nregs] -= REG_FREQ (reg);
1636 }
1637
1638 /* Find reload register to use for reload number ORDER.  */
1639
1640 static int
1641 find_reg (struct insn_chain *chain, int order)
1642 {
1643   int rnum = reload_order[order];
1644   struct reload *rl = rld + rnum;
1645   int best_cost = INT_MAX;
1646   int best_reg = -1;
1647   unsigned int i, j;
1648   int k;
1649   HARD_REG_SET not_usable;
1650   HARD_REG_SET used_by_other_reload;
1651
1652   COPY_HARD_REG_SET (not_usable, bad_spill_regs);
1653   IOR_HARD_REG_SET (not_usable, bad_spill_regs_global);
1654   IOR_COMPL_HARD_REG_SET (not_usable, reg_class_contents[rl->class]);
1655
1656   CLEAR_HARD_REG_SET (used_by_other_reload);
1657   for (k = 0; k < order; k++)
1658     {
1659       int other = reload_order[k];
1660
1661       if (rld[other].regno >= 0 && reloads_conflict (other, rnum))
1662         for (j = 0; j < rld[other].nregs; j++)
1663           SET_HARD_REG_BIT (used_by_other_reload, rld[other].regno + j);
1664     }
1665
1666   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1667     {
1668       unsigned int regno = i;
1669
1670       if (! TEST_HARD_REG_BIT (not_usable, regno)
1671           && ! TEST_HARD_REG_BIT (used_by_other_reload, regno)
1672           && HARD_REGNO_MODE_OK (regno, rl->mode))
1673         {
1674           int this_cost = spill_cost[regno];
1675           int ok = 1;
1676           unsigned int this_nregs = HARD_REGNO_NREGS (regno, rl->mode);
1677
1678           for (j = 1; j < this_nregs; j++)
1679             {
1680               this_cost += spill_add_cost[regno + j];
1681               if ((TEST_HARD_REG_BIT (not_usable, regno + j))
1682                   || TEST_HARD_REG_BIT (used_by_other_reload, regno + j))
1683                 ok = 0;
1684             }
1685           if (! ok)
1686             continue;
1687           if (rl->in && GET_CODE (rl->in) == REG && REGNO (rl->in) == regno)
1688             this_cost--;
1689           if (rl->out && GET_CODE (rl->out) == REG && REGNO (rl->out) == regno)
1690             this_cost--;
1691           if (this_cost < best_cost
1692               /* Among registers with equal cost, prefer caller-saved ones, or
1693                  use REG_ALLOC_ORDER if it is defined.  */
1694               || (this_cost == best_cost
1695 #ifdef REG_ALLOC_ORDER
1696                   && (inv_reg_alloc_order[regno]
1697                       < inv_reg_alloc_order[best_reg])
1698 #else
1699                   && call_used_regs[regno]
1700                   && ! call_used_regs[best_reg]
1701 #endif
1702                   ))
1703             {
1704               best_reg = regno;
1705               best_cost = this_cost;
1706             }
1707         }
1708     }
1709   if (best_reg == -1)
1710     return 0;
1711
1712   if (rtl_dump_file)
1713     fprintf (rtl_dump_file, "Using reg %d for reload %d\n", best_reg, rnum);
1714
1715   rl->nregs = HARD_REGNO_NREGS (best_reg, rl->mode);
1716   rl->regno = best_reg;
1717
1718   EXECUTE_IF_SET_IN_REG_SET
1719     (&chain->live_throughout, FIRST_PSEUDO_REGISTER, j,
1720      {
1721        count_spilled_pseudo (best_reg, rl->nregs, j);
1722      });
1723
1724   EXECUTE_IF_SET_IN_REG_SET
1725     (&chain->dead_or_set, FIRST_PSEUDO_REGISTER, j,
1726      {
1727        count_spilled_pseudo (best_reg, rl->nregs, j);
1728      });
1729
1730   for (i = 0; i < rl->nregs; i++)
1731     {
1732       if (spill_cost[best_reg + i] != 0
1733           || spill_add_cost[best_reg + i] != 0)
1734         abort ();
1735       SET_HARD_REG_BIT (used_spill_regs_local, best_reg + i);
1736     }
1737   return 1;
1738 }
1739
1740 /* Find more reload regs to satisfy the remaining need of an insn, which
1741    is given by CHAIN.
1742    Do it by ascending class number, since otherwise a reg
1743    might be spilled for a big class and might fail to count
1744    for a smaller class even though it belongs to that class.  */
1745
1746 static void
1747 find_reload_regs (struct insn_chain *chain)
1748 {
1749   int i;
1750
1751   /* In order to be certain of getting the registers we need,
1752      we must sort the reloads into order of increasing register class.
1753      Then our grabbing of reload registers will parallel the process
1754      that provided the reload registers.  */
1755   for (i = 0; i < chain->n_reloads; i++)
1756     {
1757       /* Show whether this reload already has a hard reg.  */
1758       if (chain->rld[i].reg_rtx)
1759         {
1760           int regno = REGNO (chain->rld[i].reg_rtx);
1761           chain->rld[i].regno = regno;
1762           chain->rld[i].nregs
1763             = HARD_REGNO_NREGS (regno, GET_MODE (chain->rld[i].reg_rtx));
1764         }
1765       else
1766         chain->rld[i].regno = -1;
1767       reload_order[i] = i;
1768     }
1769
1770   n_reloads = chain->n_reloads;
1771   memcpy (rld, chain->rld, n_reloads * sizeof (struct reload));
1772
1773   CLEAR_HARD_REG_SET (used_spill_regs_local);
1774
1775   if (rtl_dump_file)
1776     fprintf (rtl_dump_file, "Spilling for insn %d.\n", INSN_UID (chain->insn));
1777
1778   qsort (reload_order, n_reloads, sizeof (short), reload_reg_class_lower);
1779
1780   /* Compute the order of preference for hard registers to spill.  */
1781
1782   order_regs_for_reload (chain);
1783
1784   for (i = 0; i < n_reloads; i++)
1785     {
1786       int r = reload_order[i];
1787
1788       /* Ignore reloads that got marked inoperative.  */
1789       if ((rld[r].out != 0 || rld[r].in != 0 || rld[r].secondary_p)
1790           && ! rld[r].optional
1791           && rld[r].regno == -1)
1792         if (! find_reg (chain, i))
1793           {
1794             spill_failure (chain->insn, rld[r].class);
1795             failure = 1;
1796             return;
1797           }
1798     }
1799
1800   COPY_HARD_REG_SET (chain->used_spill_regs, used_spill_regs_local);
1801   IOR_HARD_REG_SET (used_spill_regs, used_spill_regs_local);
1802
1803   memcpy (chain->rld, rld, n_reloads * sizeof (struct reload));
1804 }
1805
1806 static void
1807 select_reload_regs (void)
1808 {
1809   struct insn_chain *chain;
1810
1811   /* Try to satisfy the needs for each insn.  */
1812   for (chain = insns_need_reload; chain != 0;
1813        chain = chain->next_need_reload)
1814     find_reload_regs (chain);
1815 }
1816 \f
1817 /* Delete all insns that were inserted by emit_caller_save_insns during
1818    this iteration.  */
1819 static void
1820 delete_caller_save_insns (void)
1821 {
1822   struct insn_chain *c = reload_insn_chain;
1823
1824   while (c != 0)
1825     {
1826       while (c != 0 && c->is_caller_save_insn)
1827         {
1828           struct insn_chain *next = c->next;
1829           rtx insn = c->insn;
1830
1831           if (c == reload_insn_chain)
1832             reload_insn_chain = next;
1833           delete_insn (insn);
1834
1835           if (next)
1836             next->prev = c->prev;
1837           if (c->prev)
1838             c->prev->next = next;
1839           c->next = unused_insn_chains;
1840           unused_insn_chains = c;
1841           c = next;
1842         }
1843       if (c != 0)
1844         c = c->next;
1845     }
1846 }
1847 \f
1848 /* Handle the failure to find a register to spill.
1849    INSN should be one of the insns which needed this particular spill reg.  */
1850
1851 static void
1852 spill_failure (rtx insn, enum reg_class class)
1853 {
1854   static const char *const reg_class_names[] = REG_CLASS_NAMES;
1855   if (asm_noperands (PATTERN (insn)) >= 0)
1856     error_for_asm (insn, "can't find a register in class `%s' while reloading `asm'",
1857                    reg_class_names[class]);
1858   else
1859     {
1860       error ("unable to find a register to spill in class `%s'",
1861              reg_class_names[class]);
1862       fatal_insn ("this is the insn:", insn);
1863     }
1864 }
1865 \f
1866 /* Delete an unneeded INSN and any previous insns who sole purpose is loading
1867    data that is dead in INSN.  */
1868
1869 static void
1870 delete_dead_insn (rtx insn)
1871 {
1872   rtx prev = prev_real_insn (insn);
1873   rtx prev_dest;
1874
1875   /* If the previous insn sets a register that dies in our insn, delete it
1876      too.  */
1877   if (prev && GET_CODE (PATTERN (prev)) == SET
1878       && (prev_dest = SET_DEST (PATTERN (prev)), GET_CODE (prev_dest) == REG)
1879       && reg_mentioned_p (prev_dest, PATTERN (insn))
1880       && find_regno_note (insn, REG_DEAD, REGNO (prev_dest))
1881       && ! side_effects_p (SET_SRC (PATTERN (prev))))
1882     delete_dead_insn (prev);
1883
1884   PUT_CODE (insn, NOTE);
1885   NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
1886   NOTE_SOURCE_FILE (insn) = 0;
1887 }
1888
1889 /* Modify the home of pseudo-reg I.
1890    The new home is present in reg_renumber[I].
1891
1892    FROM_REG may be the hard reg that the pseudo-reg is being spilled from;
1893    or it may be -1, meaning there is none or it is not relevant.
1894    This is used so that all pseudos spilled from a given hard reg
1895    can share one stack slot.  */
1896
1897 static void
1898 alter_reg (int i, int from_reg)
1899 {
1900   /* When outputting an inline function, this can happen
1901      for a reg that isn't actually used.  */
1902   if (regno_reg_rtx[i] == 0)
1903     return;
1904
1905   /* If the reg got changed to a MEM at rtl-generation time,
1906      ignore it.  */
1907   if (GET_CODE (regno_reg_rtx[i]) != REG)
1908     return;
1909
1910   /* Modify the reg-rtx to contain the new hard reg
1911      number or else to contain its pseudo reg number.  */
1912   REGNO (regno_reg_rtx[i])
1913     = reg_renumber[i] >= 0 ? reg_renumber[i] : i;
1914
1915   /* If we have a pseudo that is needed but has no hard reg or equivalent,
1916      allocate a stack slot for it.  */
1917
1918   if (reg_renumber[i] < 0
1919       && REG_N_REFS (i) > 0
1920       && reg_equiv_constant[i] == 0
1921       && reg_equiv_memory_loc[i] == 0)
1922     {
1923       rtx x;
1924       unsigned int inherent_size = PSEUDO_REGNO_BYTES (i);
1925       unsigned int total_size = MAX (inherent_size, reg_max_ref_width[i]);
1926       int adjust = 0;
1927
1928       /* Each pseudo reg has an inherent size which comes from its own mode,
1929          and a total size which provides room for paradoxical subregs
1930          which refer to the pseudo reg in wider modes.
1931
1932          We can use a slot already allocated if it provides both
1933          enough inherent space and enough total space.
1934          Otherwise, we allocate a new slot, making sure that it has no less
1935          inherent space, and no less total space, then the previous slot.  */
1936       if (from_reg == -1)
1937         {
1938           /* No known place to spill from => no slot to reuse.  */
1939           x = assign_stack_local (GET_MODE (regno_reg_rtx[i]), total_size,
1940                                   inherent_size == total_size ? 0 : -1);
1941           if (BYTES_BIG_ENDIAN)
1942             /* Cancel the  big-endian correction done in assign_stack_local.
1943                Get the address of the beginning of the slot.
1944                This is so we can do a big-endian correction unconditionally
1945                below.  */
1946             adjust = inherent_size - total_size;
1947
1948           RTX_UNCHANGING_P (x) = RTX_UNCHANGING_P (regno_reg_rtx[i]);
1949
1950           /* Nothing can alias this slot except this pseudo.  */
1951           set_mem_alias_set (x, new_alias_set ());
1952         }
1953
1954       /* Reuse a stack slot if possible.  */
1955       else if (spill_stack_slot[from_reg] != 0
1956                && spill_stack_slot_width[from_reg] >= total_size
1957                && (GET_MODE_SIZE (GET_MODE (spill_stack_slot[from_reg]))
1958                    >= inherent_size))
1959         x = spill_stack_slot[from_reg];
1960
1961       /* Allocate a bigger slot.  */
1962       else
1963         {
1964           /* Compute maximum size needed, both for inherent size
1965              and for total size.  */
1966           enum machine_mode mode = GET_MODE (regno_reg_rtx[i]);
1967           rtx stack_slot;
1968
1969           if (spill_stack_slot[from_reg])
1970             {
1971               if (GET_MODE_SIZE (GET_MODE (spill_stack_slot[from_reg]))
1972                   > inherent_size)
1973                 mode = GET_MODE (spill_stack_slot[from_reg]);
1974               if (spill_stack_slot_width[from_reg] > total_size)
1975                 total_size = spill_stack_slot_width[from_reg];
1976             }
1977
1978           /* Make a slot with that size.  */
1979           x = assign_stack_local (mode, total_size,
1980                                   inherent_size == total_size ? 0 : -1);
1981           stack_slot = x;
1982
1983           /* All pseudos mapped to this slot can alias each other.  */
1984           if (spill_stack_slot[from_reg])
1985             set_mem_alias_set (x, MEM_ALIAS_SET (spill_stack_slot[from_reg]));
1986           else
1987             set_mem_alias_set (x, new_alias_set ());
1988
1989           if (BYTES_BIG_ENDIAN)
1990             {
1991               /* Cancel the  big-endian correction done in assign_stack_local.
1992                  Get the address of the beginning of the slot.
1993                  This is so we can do a big-endian correction unconditionally
1994                  below.  */
1995               adjust = GET_MODE_SIZE (mode) - total_size;
1996               if (adjust)
1997                 stack_slot
1998                   = adjust_address_nv (x, mode_for_size (total_size
1999                                                          * BITS_PER_UNIT,
2000                                                          MODE_INT, 1),
2001                                        adjust);
2002             }
2003
2004           spill_stack_slot[from_reg] = stack_slot;
2005           spill_stack_slot_width[from_reg] = total_size;
2006         }
2007
2008       /* On a big endian machine, the "address" of the slot
2009          is the address of the low part that fits its inherent mode.  */
2010       if (BYTES_BIG_ENDIAN && inherent_size < total_size)
2011         adjust += (total_size - inherent_size);
2012
2013       /* If we have any adjustment to make, or if the stack slot is the
2014          wrong mode, make a new stack slot.  */
2015       x = adjust_address_nv (x, GET_MODE (regno_reg_rtx[i]), adjust);
2016
2017       /* If we have a decl for the original register, set it for the
2018          memory.  If this is a shared MEM, make a copy.  */
2019       if (REG_EXPR (regno_reg_rtx[i])
2020           && TREE_CODE_CLASS (TREE_CODE (REG_EXPR (regno_reg_rtx[i]))) == 'd')
2021         {
2022           rtx decl = DECL_RTL_IF_SET (REG_EXPR (regno_reg_rtx[i]));
2023
2024           /* We can do this only for the DECLs home pseudo, not for
2025              any copies of it, since otherwise when the stack slot
2026              is reused, nonoverlapping_memrefs_p might think they
2027              cannot overlap.  */
2028           if (decl && GET_CODE (decl) == REG && REGNO (decl) == (unsigned) i)
2029             {
2030               if (from_reg != -1 && spill_stack_slot[from_reg] == x)
2031                 x = copy_rtx (x);
2032
2033               set_mem_attrs_from_reg (x, regno_reg_rtx[i]);
2034             }
2035         }
2036
2037       /* Save the stack slot for later.  */
2038       reg_equiv_memory_loc[i] = x;
2039     }
2040 }
2041
2042 /* Mark the slots in regs_ever_live for the hard regs
2043    used by pseudo-reg number REGNO.  */
2044
2045 void
2046 mark_home_live (int regno)
2047 {
2048   int i, lim;
2049
2050   i = reg_renumber[regno];
2051   if (i < 0)
2052     return;
2053   lim = i + HARD_REGNO_NREGS (i, PSEUDO_REGNO_MODE (regno));
2054   while (i < lim)
2055     regs_ever_live[i++] = 1;
2056 }
2057 \f
2058 /* This function handles the tracking of elimination offsets around branches.
2059
2060    X is a piece of RTL being scanned.
2061
2062    INSN is the insn that it came from, if any.
2063
2064    INITIAL_P is nonzero if we are to set the offset to be the initial
2065    offset and zero if we are setting the offset of the label to be the
2066    current offset.  */
2067
2068 static void
2069 set_label_offsets (rtx x, rtx insn, int initial_p)
2070 {
2071   enum rtx_code code = GET_CODE (x);
2072   rtx tem;
2073   unsigned int i;
2074   struct elim_table *p;
2075
2076   switch (code)
2077     {
2078     case LABEL_REF:
2079       if (LABEL_REF_NONLOCAL_P (x))
2080         return;
2081
2082       x = XEXP (x, 0);
2083
2084       /* ... fall through ...  */
2085
2086     case CODE_LABEL:
2087       /* If we know nothing about this label, set the desired offsets.  Note
2088          that this sets the offset at a label to be the offset before a label
2089          if we don't know anything about the label.  This is not correct for
2090          the label after a BARRIER, but is the best guess we can make.  If
2091          we guessed wrong, we will suppress an elimination that might have
2092          been possible had we been able to guess correctly.  */
2093
2094       if (! offsets_known_at[CODE_LABEL_NUMBER (x) - first_label_num])
2095         {
2096           for (i = 0; i < NUM_ELIMINABLE_REGS; i++)
2097             offsets_at[CODE_LABEL_NUMBER (x) - first_label_num][i]
2098               = (initial_p ? reg_eliminate[i].initial_offset
2099                  : reg_eliminate[i].offset);
2100           offsets_known_at[CODE_LABEL_NUMBER (x) - first_label_num] = 1;
2101         }
2102
2103       /* Otherwise, if this is the definition of a label and it is
2104          preceded by a BARRIER, set our offsets to the known offset of
2105          that label.  */
2106
2107       else if (x == insn
2108                && (tem = prev_nonnote_insn (insn)) != 0
2109                && GET_CODE (tem) == BARRIER)
2110         set_offsets_for_label (insn);
2111       else
2112         /* If neither of the above cases is true, compare each offset
2113            with those previously recorded and suppress any eliminations
2114            where the offsets disagree.  */
2115
2116         for (i = 0; i < NUM_ELIMINABLE_REGS; i++)
2117           if (offsets_at[CODE_LABEL_NUMBER (x) - first_label_num][i]
2118               != (initial_p ? reg_eliminate[i].initial_offset
2119                   : reg_eliminate[i].offset))
2120             reg_eliminate[i].can_eliminate = 0;
2121
2122       return;
2123
2124     case JUMP_INSN:
2125       set_label_offsets (PATTERN (insn), insn, initial_p);
2126
2127       /* ... fall through ...  */
2128
2129     case INSN:
2130     case CALL_INSN:
2131       /* Any labels mentioned in REG_LABEL notes can be branched to indirectly
2132          and hence must have all eliminations at their initial offsets.  */
2133       for (tem = REG_NOTES (x); tem; tem = XEXP (tem, 1))
2134         if (REG_NOTE_KIND (tem) == REG_LABEL)
2135           set_label_offsets (XEXP (tem, 0), insn, 1);
2136       return;
2137
2138     case PARALLEL:
2139     case ADDR_VEC:
2140     case ADDR_DIFF_VEC:
2141       /* Each of the labels in the parallel or address vector must be
2142          at their initial offsets.  We want the first field for PARALLEL
2143          and ADDR_VEC and the second field for ADDR_DIFF_VEC.  */
2144
2145       for (i = 0; i < (unsigned) XVECLEN (x, code == ADDR_DIFF_VEC); i++)
2146         set_label_offsets (XVECEXP (x, code == ADDR_DIFF_VEC, i),
2147                            insn, initial_p);
2148       return;
2149
2150     case SET:
2151       /* We only care about setting PC.  If the source is not RETURN,
2152          IF_THEN_ELSE, or a label, disable any eliminations not at
2153          their initial offsets.  Similarly if any arm of the IF_THEN_ELSE
2154          isn't one of those possibilities.  For branches to a label,
2155          call ourselves recursively.
2156
2157          Note that this can disable elimination unnecessarily when we have
2158          a non-local goto since it will look like a non-constant jump to
2159          someplace in the current function.  This isn't a significant
2160          problem since such jumps will normally be when all elimination
2161          pairs are back to their initial offsets.  */
2162
2163       if (SET_DEST (x) != pc_rtx)
2164         return;
2165
2166       switch (GET_CODE (SET_SRC (x)))
2167         {
2168         case PC:
2169         case RETURN:
2170           return;
2171
2172         case LABEL_REF:
2173           set_label_offsets (XEXP (SET_SRC (x), 0), insn, initial_p);
2174           return;
2175
2176         case IF_THEN_ELSE:
2177           tem = XEXP (SET_SRC (x), 1);
2178           if (GET_CODE (tem) == LABEL_REF)
2179             set_label_offsets (XEXP (tem, 0), insn, initial_p);
2180           else if (GET_CODE (tem) != PC && GET_CODE (tem) != RETURN)
2181             break;
2182
2183           tem = XEXP (SET_SRC (x), 2);
2184           if (GET_CODE (tem) == LABEL_REF)
2185             set_label_offsets (XEXP (tem, 0), insn, initial_p);
2186           else if (GET_CODE (tem) != PC && GET_CODE (tem) != RETURN)
2187             break;
2188           return;
2189
2190         default:
2191           break;
2192         }
2193
2194       /* If we reach here, all eliminations must be at their initial
2195          offset because we are doing a jump to a variable address.  */
2196       for (p = reg_eliminate; p < &reg_eliminate[NUM_ELIMINABLE_REGS]; p++)
2197         if (p->offset != p->initial_offset)
2198           p->can_eliminate = 0;
2199       break;
2200
2201     default:
2202       break;
2203     }
2204 }
2205 \f
2206 /* Scan X and replace any eliminable registers (such as fp) with a
2207    replacement (such as sp), plus an offset.
2208
2209    MEM_MODE is the mode of an enclosing MEM.  We need this to know how
2210    much to adjust a register for, e.g., PRE_DEC.  Also, if we are inside a
2211    MEM, we are allowed to replace a sum of a register and the constant zero
2212    with the register, which we cannot do outside a MEM.  In addition, we need
2213    to record the fact that a register is referenced outside a MEM.
2214
2215    If INSN is an insn, it is the insn containing X.  If we replace a REG
2216    in a SET_DEST with an equivalent MEM and INSN is nonzero, write a
2217    CLOBBER of the pseudo after INSN so find_equiv_regs will know that
2218    the REG is being modified.
2219
2220    Alternatively, INSN may be a note (an EXPR_LIST or INSN_LIST).
2221    That's used when we eliminate in expressions stored in notes.
2222    This means, do not set ref_outside_mem even if the reference
2223    is outside of MEMs.
2224
2225    REG_EQUIV_MEM and REG_EQUIV_ADDRESS contain address that have had
2226    replacements done assuming all offsets are at their initial values.  If
2227    they are not, or if REG_EQUIV_ADDRESS is nonzero for a pseudo we
2228    encounter, return the actual location so that find_reloads will do
2229    the proper thing.  */
2230
2231 rtx
2232 eliminate_regs (rtx x, enum machine_mode mem_mode, rtx insn)
2233 {
2234   enum rtx_code code = GET_CODE (x);
2235   struct elim_table *ep;
2236   int regno;
2237   rtx new;
2238   int i, j;
2239   const char *fmt;
2240   int copied = 0;
2241
2242   if (! current_function_decl)
2243     return x;
2244
2245   switch (code)
2246     {
2247     case CONST_INT:
2248     case CONST_DOUBLE:
2249     case CONST_VECTOR:
2250     case CONST:
2251     case SYMBOL_REF:
2252     case CODE_LABEL:
2253     case PC:
2254     case CC0:
2255     case ASM_INPUT:
2256     case ADDR_VEC:
2257     case ADDR_DIFF_VEC:
2258     case RETURN:
2259       return x;
2260
2261     case ADDRESSOF:
2262       /* This is only for the benefit of the debugging backends, which call
2263          eliminate_regs on DECL_RTL; any ADDRESSOFs in the actual insns are
2264          removed after CSE.  */
2265       new = eliminate_regs (XEXP (x, 0), 0, insn);
2266       if (GET_CODE (new) == MEM)
2267         return XEXP (new, 0);
2268       return x;
2269
2270     case REG:
2271       regno = REGNO (x);
2272
2273       /* First handle the case where we encounter a bare register that
2274          is eliminable.  Replace it with a PLUS.  */
2275       if (regno < FIRST_PSEUDO_REGISTER)
2276         {
2277           for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
2278                ep++)
2279             if (ep->from_rtx == x && ep->can_eliminate)
2280               return plus_constant (ep->to_rtx, ep->previous_offset);
2281
2282         }
2283       else if (reg_renumber && reg_renumber[regno] < 0
2284                && reg_equiv_constant && reg_equiv_constant[regno]
2285                && ! CONSTANT_P (reg_equiv_constant[regno]))
2286         return eliminate_regs (copy_rtx (reg_equiv_constant[regno]),
2287                                mem_mode, insn);
2288       return x;
2289
2290     /* You might think handling MINUS in a manner similar to PLUS is a
2291        good idea.  It is not.  It has been tried multiple times and every
2292        time the change has had to have been reverted.
2293
2294        Other parts of reload know a PLUS is special (gen_reload for example)
2295        and require special code to handle code a reloaded PLUS operand.
2296
2297        Also consider backends where the flags register is clobbered by a
2298        MINUS, but we can emit a PLUS that does not clobber flags (ia32,
2299        lea instruction comes to mind).  If we try to reload a MINUS, we
2300        may kill the flags register that was holding a useful value.
2301
2302        So, please before trying to handle MINUS, consider reload as a
2303        whole instead of this little section as well as the backend issues.  */
2304     case PLUS:
2305       /* If this is the sum of an eliminable register and a constant, rework
2306          the sum.  */
2307       if (GET_CODE (XEXP (x, 0)) == REG
2308           && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER
2309           && CONSTANT_P (XEXP (x, 1)))
2310         {
2311           for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
2312                ep++)
2313             if (ep->from_rtx == XEXP (x, 0) && ep->can_eliminate)
2314               {
2315                 /* The only time we want to replace a PLUS with a REG (this
2316                    occurs when the constant operand of the PLUS is the negative
2317                    of the offset) is when we are inside a MEM.  We won't want
2318                    to do so at other times because that would change the
2319                    structure of the insn in a way that reload can't handle.
2320                    We special-case the commonest situation in
2321                    eliminate_regs_in_insn, so just replace a PLUS with a
2322                    PLUS here, unless inside a MEM.  */
2323                 if (mem_mode != 0 && GET_CODE (XEXP (x, 1)) == CONST_INT
2324                     && INTVAL (XEXP (x, 1)) == - ep->previous_offset)
2325                   return ep->to_rtx;
2326                 else
2327                   return gen_rtx_PLUS (Pmode, ep->to_rtx,
2328                                        plus_constant (XEXP (x, 1),
2329                                                       ep->previous_offset));
2330               }
2331
2332           /* If the register is not eliminable, we are done since the other
2333              operand is a constant.  */
2334           return x;
2335         }
2336
2337       /* If this is part of an address, we want to bring any constant to the
2338          outermost PLUS.  We will do this by doing register replacement in
2339          our operands and seeing if a constant shows up in one of them.
2340
2341          Note that there is no risk of modifying the structure of the insn,
2342          since we only get called for its operands, thus we are either
2343          modifying the address inside a MEM, or something like an address
2344          operand of a load-address insn.  */
2345
2346       {
2347         rtx new0 = eliminate_regs (XEXP (x, 0), mem_mode, insn);
2348         rtx new1 = eliminate_regs (XEXP (x, 1), mem_mode, insn);
2349
2350         if (reg_renumber && (new0 != XEXP (x, 0) || new1 != XEXP (x, 1)))
2351           {
2352             /* If one side is a PLUS and the other side is a pseudo that
2353                didn't get a hard register but has a reg_equiv_constant,
2354                we must replace the constant here since it may no longer
2355                be in the position of any operand.  */
2356             if (GET_CODE (new0) == PLUS && GET_CODE (new1) == REG
2357                 && REGNO (new1) >= FIRST_PSEUDO_REGISTER
2358                 && reg_renumber[REGNO (new1)] < 0
2359                 && reg_equiv_constant != 0
2360                 && reg_equiv_constant[REGNO (new1)] != 0)
2361               new1 = reg_equiv_constant[REGNO (new1)];
2362             else if (GET_CODE (new1) == PLUS && GET_CODE (new0) == REG
2363                      && REGNO (new0) >= FIRST_PSEUDO_REGISTER
2364                      && reg_renumber[REGNO (new0)] < 0
2365                      && reg_equiv_constant[REGNO (new0)] != 0)
2366               new0 = reg_equiv_constant[REGNO (new0)];
2367
2368             new = form_sum (new0, new1);
2369
2370             /* As above, if we are not inside a MEM we do not want to
2371                turn a PLUS into something else.  We might try to do so here
2372                for an addition of 0 if we aren't optimizing.  */
2373             if (! mem_mode && GET_CODE (new) != PLUS)
2374               return gen_rtx_PLUS (GET_MODE (x), new, const0_rtx);
2375             else
2376               return new;
2377           }
2378       }
2379       return x;
2380
2381     case MULT:
2382       /* If this is the product of an eliminable register and a
2383          constant, apply the distribute law and move the constant out
2384          so that we have (plus (mult ..) ..).  This is needed in order
2385          to keep load-address insns valid.   This case is pathological.
2386          We ignore the possibility of overflow here.  */
2387       if (GET_CODE (XEXP (x, 0)) == REG
2388           && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER
2389           && GET_CODE (XEXP (x, 1)) == CONST_INT)
2390         for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
2391              ep++)
2392           if (ep->from_rtx == XEXP (x, 0) && ep->can_eliminate)
2393             {
2394               if (! mem_mode
2395                   /* Refs inside notes don't count for this purpose.  */
2396                   && ! (insn != 0 && (GET_CODE (insn) == EXPR_LIST
2397                                       || GET_CODE (insn) == INSN_LIST)))
2398                 ep->ref_outside_mem = 1;
2399
2400               return
2401                 plus_constant (gen_rtx_MULT (Pmode, ep->to_rtx, XEXP (x, 1)),
2402                                ep->previous_offset * INTVAL (XEXP (x, 1)));
2403             }
2404
2405       /* ... fall through ...  */
2406
2407     case CALL:
2408     case COMPARE:
2409     /* See comments before PLUS about handling MINUS.  */
2410     case MINUS:
2411     case DIV:      case UDIV:
2412     case MOD:      case UMOD:
2413     case AND:      case IOR:      case XOR:
2414     case ROTATERT: case ROTATE:
2415     case ASHIFTRT: case LSHIFTRT: case ASHIFT:
2416     case NE:       case EQ:
2417     case GE:       case GT:       case GEU:    case GTU:
2418     case LE:       case LT:       case LEU:    case LTU:
2419       {
2420         rtx new0 = eliminate_regs (XEXP (x, 0), mem_mode, insn);
2421         rtx new1
2422           = XEXP (x, 1) ? eliminate_regs (XEXP (x, 1), mem_mode, insn) : 0;
2423
2424         if (new0 != XEXP (x, 0) || new1 != XEXP (x, 1))
2425           return gen_rtx_fmt_ee (code, GET_MODE (x), new0, new1);
2426       }
2427       return x;
2428
2429     case EXPR_LIST:
2430       /* If we have something in XEXP (x, 0), the usual case, eliminate it.  */
2431       if (XEXP (x, 0))
2432         {
2433           new = eliminate_regs (XEXP (x, 0), mem_mode, insn);
2434           if (new != XEXP (x, 0))
2435             {
2436               /* If this is a REG_DEAD note, it is not valid anymore.
2437                  Using the eliminated version could result in creating a
2438                  REG_DEAD note for the stack or frame pointer.  */
2439               if (GET_MODE (x) == REG_DEAD)
2440                 return (XEXP (x, 1)
2441                         ? eliminate_regs (XEXP (x, 1), mem_mode, insn)
2442                         : NULL_RTX);
2443
2444               x = gen_rtx_EXPR_LIST (REG_NOTE_KIND (x), new, XEXP (x, 1));
2445             }
2446         }
2447
2448       /* ... fall through ...  */
2449
2450     case INSN_LIST:
2451       /* Now do eliminations in the rest of the chain.  If this was
2452          an EXPR_LIST, this might result in allocating more memory than is
2453          strictly needed, but it simplifies the code.  */
2454       if (XEXP (x, 1))
2455         {
2456           new = eliminate_regs (XEXP (x, 1), mem_mode, insn);
2457           if (new != XEXP (x, 1))
2458             return
2459               gen_rtx_fmt_ee (GET_CODE (x), GET_MODE (x), XEXP (x, 0), new);
2460         }
2461       return x;
2462
2463     case PRE_INC:
2464     case POST_INC:
2465     case PRE_DEC:
2466     case POST_DEC:
2467     case STRICT_LOW_PART:
2468     case NEG:          case NOT:
2469     case SIGN_EXTEND:  case ZERO_EXTEND:
2470     case TRUNCATE:     case FLOAT_EXTEND: case FLOAT_TRUNCATE:
2471     case FLOAT:        case FIX:
2472     case UNSIGNED_FIX: case UNSIGNED_FLOAT:
2473     case ABS:
2474     case SQRT:
2475     case FFS:
2476     case CLZ:
2477     case CTZ:
2478     case POPCOUNT:
2479     case PARITY:
2480       new = eliminate_regs (XEXP (x, 0), mem_mode, insn);
2481       if (new != XEXP (x, 0))
2482         return gen_rtx_fmt_e (code, GET_MODE (x), new);
2483       return x;
2484
2485     case SUBREG:
2486       /* Similar to above processing, but preserve SUBREG_BYTE.
2487          Convert (subreg (mem)) to (mem) if not paradoxical.
2488          Also, if we have a non-paradoxical (subreg (pseudo)) and the
2489          pseudo didn't get a hard reg, we must replace this with the
2490          eliminated version of the memory location because push_reload
2491          may do the replacement in certain circumstances.  */
2492       if (GET_CODE (SUBREG_REG (x)) == REG
2493           && (GET_MODE_SIZE (GET_MODE (x))
2494               <= GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
2495           && reg_equiv_memory_loc != 0
2496           && reg_equiv_memory_loc[REGNO (SUBREG_REG (x))] != 0)
2497         {
2498           new = SUBREG_REG (x);
2499         }
2500       else
2501         new = eliminate_regs (SUBREG_REG (x), mem_mode, insn);
2502
2503       if (new != SUBREG_REG (x))
2504         {
2505           int x_size = GET_MODE_SIZE (GET_MODE (x));
2506           int new_size = GET_MODE_SIZE (GET_MODE (new));
2507
2508           if (GET_CODE (new) == MEM
2509               && ((x_size < new_size
2510 #ifdef WORD_REGISTER_OPERATIONS
2511                    /* On these machines, combine can create rtl of the form
2512                       (set (subreg:m1 (reg:m2 R) 0) ...)
2513                       where m1 < m2, and expects something interesting to
2514                       happen to the entire word.  Moreover, it will use the
2515                       (reg:m2 R) later, expecting all bits to be preserved.
2516                       So if the number of words is the same, preserve the
2517                       subreg so that push_reload can see it.  */
2518                    && ! ((x_size - 1) / UNITS_PER_WORD
2519                          == (new_size -1 ) / UNITS_PER_WORD)
2520 #endif
2521                    )
2522                   || x_size == new_size)
2523               )
2524             return adjust_address_nv (new, GET_MODE (x), SUBREG_BYTE (x));
2525           else
2526             return gen_rtx_SUBREG (GET_MODE (x), new, SUBREG_BYTE (x));
2527         }
2528
2529       return x;
2530
2531     case MEM:
2532       /* This is only for the benefit of the debugging backends, which call
2533          eliminate_regs on DECL_RTL; any ADDRESSOFs in the actual insns are
2534          removed after CSE.  */
2535       if (GET_CODE (XEXP (x, 0)) == ADDRESSOF)
2536         return eliminate_regs (XEXP (XEXP (x, 0), 0), 0, insn);
2537
2538       /* Our only special processing is to pass the mode of the MEM to our
2539          recursive call and copy the flags.  While we are here, handle this
2540          case more efficiently.  */
2541       return
2542         replace_equiv_address_nv (x,
2543                                   eliminate_regs (XEXP (x, 0),
2544                                                   GET_MODE (x), insn));
2545
2546     case USE:
2547       /* Handle insn_list USE that a call to a pure function may generate.  */
2548       new = eliminate_regs (XEXP (x, 0), 0, insn);
2549       if (new != XEXP (x, 0))
2550         return gen_rtx_USE (GET_MODE (x), new);
2551       return x;
2552
2553     case CLOBBER:
2554     case ASM_OPERANDS:
2555     case SET:
2556       abort ();
2557
2558     default:
2559       break;
2560     }
2561
2562   /* Process each of our operands recursively.  If any have changed, make a
2563      copy of the rtx.  */
2564   fmt = GET_RTX_FORMAT (code);
2565   for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
2566     {
2567       if (*fmt == 'e')
2568         {
2569           new = eliminate_regs (XEXP (x, i), mem_mode, insn);
2570           if (new != XEXP (x, i) && ! copied)
2571             {
2572               rtx new_x = rtx_alloc (code);
2573               memcpy (new_x, x, RTX_SIZE (code));
2574               x = new_x;
2575               copied = 1;
2576             }
2577           XEXP (x, i) = new;
2578         }
2579       else if (*fmt == 'E')
2580         {
2581           int copied_vec = 0;
2582           for (j = 0; j < XVECLEN (x, i); j++)
2583             {
2584               new = eliminate_regs (XVECEXP (x, i, j), mem_mode, insn);
2585               if (new != XVECEXP (x, i, j) && ! copied_vec)
2586                 {
2587                   rtvec new_v = gen_rtvec_v (XVECLEN (x, i),
2588                                              XVEC (x, i)->elem);
2589                   if (! copied)
2590                     {
2591                       rtx new_x = rtx_alloc (code);
2592                       memcpy (new_x, x, RTX_SIZE (code));
2593                       x = new_x;
2594                       copied = 1;
2595                     }
2596                   XVEC (x, i) = new_v;
2597                   copied_vec = 1;
2598                 }
2599               XVECEXP (x, i, j) = new;
2600             }
2601         }
2602     }
2603
2604   return x;
2605 }
2606
2607 /* Scan rtx X for modifications of elimination target registers.  Update
2608    the table of eliminables to reflect the changed state.  MEM_MODE is
2609    the mode of an enclosing MEM rtx, or VOIDmode if not within a MEM.  */
2610
2611 static void
2612 elimination_effects (rtx x, enum machine_mode mem_mode)
2613 {
2614   enum rtx_code code = GET_CODE (x);
2615   struct elim_table *ep;
2616   int regno;
2617   int i, j;
2618   const char *fmt;
2619
2620   switch (code)
2621     {
2622     case CONST_INT:
2623     case CONST_DOUBLE:
2624     case CONST_VECTOR:
2625     case CONST:
2626     case SYMBOL_REF:
2627     case CODE_LABEL:
2628     case PC:
2629     case CC0:
2630     case ASM_INPUT:
2631     case ADDR_VEC:
2632     case ADDR_DIFF_VEC:
2633     case RETURN:
2634       return;
2635
2636     case ADDRESSOF:
2637       abort ();
2638
2639     case REG:
2640       regno = REGNO (x);
2641
2642       /* First handle the case where we encounter a bare register that
2643          is eliminable.  Replace it with a PLUS.  */
2644       if (regno < FIRST_PSEUDO_REGISTER)
2645         {
2646           for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
2647                ep++)
2648             if (ep->from_rtx == x && ep->can_eliminate)
2649               {
2650                 if (! mem_mode)
2651                   ep->ref_outside_mem = 1;
2652                 return;
2653               }
2654
2655         }
2656       else if (reg_renumber[regno] < 0 && reg_equiv_constant
2657                && reg_equiv_constant[regno]
2658                && ! function_invariant_p (reg_equiv_constant[regno]))
2659         elimination_effects (reg_equiv_constant[regno], mem_mode);
2660       return;
2661
2662     case PRE_INC:
2663     case POST_INC:
2664     case PRE_DEC:
2665     case POST_DEC:
2666     case POST_MODIFY:
2667     case PRE_MODIFY:
2668       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
2669         if (ep->to_rtx == XEXP (x, 0))
2670           {
2671             int size = GET_MODE_SIZE (mem_mode);
2672
2673             /* If more bytes than MEM_MODE are pushed, account for them.  */
2674 #ifdef PUSH_ROUNDING
2675             if (ep->to_rtx == stack_pointer_rtx)
2676               size = PUSH_ROUNDING (size);
2677 #endif
2678             if (code == PRE_DEC || code == POST_DEC)
2679               ep->offset += size;
2680             else if (code == PRE_INC || code == POST_INC)
2681               ep->offset -= size;
2682             else if ((code == PRE_MODIFY || code == POST_MODIFY)
2683                      && GET_CODE (XEXP (x, 1)) == PLUS
2684                      && XEXP (x, 0) == XEXP (XEXP (x, 1), 0)
2685                      && CONSTANT_P (XEXP (XEXP (x, 1), 1)))
2686               ep->offset -= INTVAL (XEXP (XEXP (x, 1), 1));
2687           }
2688
2689       /* These two aren't unary operators.  */
2690       if (code == POST_MODIFY || code == PRE_MODIFY)
2691         break;
2692
2693       /* Fall through to generic unary operation case.  */
2694     case STRICT_LOW_PART:
2695     case NEG:          case NOT:
2696     case SIGN_EXTEND:  case ZERO_EXTEND:
2697     case TRUNCATE:     case FLOAT_EXTEND: case FLOAT_TRUNCATE:
2698     case FLOAT:        case FIX:
2699     case UNSIGNED_FIX: case UNSIGNED_FLOAT:
2700     case ABS:
2701     case SQRT:
2702     case FFS:
2703     case CLZ:
2704     case CTZ:
2705     case POPCOUNT:
2706     case PARITY:
2707       elimination_effects (XEXP (x, 0), mem_mode);
2708       return;
2709
2710     case SUBREG:
2711       if (GET_CODE (SUBREG_REG (x)) == REG
2712           && (GET_MODE_SIZE (GET_MODE (x))
2713               <= GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
2714           && reg_equiv_memory_loc != 0
2715           && reg_equiv_memory_loc[REGNO (SUBREG_REG (x))] != 0)
2716         return;
2717
2718       elimination_effects (SUBREG_REG (x), mem_mode);
2719       return;
2720
2721     case USE:
2722       /* If using a register that is the source of an eliminate we still
2723          think can be performed, note it cannot be performed since we don't
2724          know how this register is used.  */
2725       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
2726         if (ep->from_rtx == XEXP (x, 0))
2727           ep->can_eliminate = 0;
2728
2729       elimination_effects (XEXP (x, 0), mem_mode);
2730       return;
2731
2732     case CLOBBER:
2733       /* If clobbering a register that is the replacement register for an
2734          elimination we still think can be performed, note that it cannot
2735          be performed.  Otherwise, we need not be concerned about it.  */
2736       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
2737         if (ep->to_rtx == XEXP (x, 0))
2738           ep->can_eliminate = 0;
2739
2740       elimination_effects (XEXP (x, 0), mem_mode);
2741       return;
2742
2743     case SET:
2744       /* Check for setting a register that we know about.  */
2745       if (GET_CODE (SET_DEST (x)) == REG)
2746         {
2747           /* See if this is setting the replacement register for an
2748              elimination.
2749
2750              If DEST is the hard frame pointer, we do nothing because we
2751              assume that all assignments to the frame pointer are for
2752              non-local gotos and are being done at a time when they are valid
2753              and do not disturb anything else.  Some machines want to
2754              eliminate a fake argument pointer (or even a fake frame pointer)
2755              with either the real frame or the stack pointer.  Assignments to
2756              the hard frame pointer must not prevent this elimination.  */
2757
2758           for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
2759                ep++)
2760             if (ep->to_rtx == SET_DEST (x)
2761                 && SET_DEST (x) != hard_frame_pointer_rtx)
2762               {
2763                 /* If it is being incremented, adjust the offset.  Otherwise,
2764                    this elimination can't be done.  */
2765                 rtx src = SET_SRC (x);
2766
2767                 if (GET_CODE (src) == PLUS
2768                     && XEXP (src, 0) == SET_DEST (x)
2769                     && GET_CODE (XEXP (src, 1)) == CONST_INT)
2770                   ep->offset -= INTVAL (XEXP (src, 1));
2771                 else
2772                   ep->can_eliminate = 0;
2773               }
2774         }
2775
2776       elimination_effects (SET_DEST (x), 0);
2777       elimination_effects (SET_SRC (x), 0);
2778       return;
2779
2780     case MEM:
2781       if (GET_CODE (XEXP (x, 0)) == ADDRESSOF)
2782         abort ();
2783
2784       /* Our only special processing is to pass the mode of the MEM to our
2785          recursive call.  */
2786       elimination_effects (XEXP (x, 0), GET_MODE (x));
2787       return;
2788
2789     default:
2790       break;
2791     }
2792
2793   fmt = GET_RTX_FORMAT (code);
2794   for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
2795     {
2796       if (*fmt == 'e')
2797         elimination_effects (XEXP (x, i), mem_mode);
2798       else if (*fmt == 'E')
2799         for (j = 0; j < XVECLEN (x, i); j++)
2800           elimination_effects (XVECEXP (x, i, j), mem_mode);
2801     }
2802 }
2803
2804 /* Descend through rtx X and verify that no references to eliminable registers
2805    remain.  If any do remain, mark the involved register as not
2806    eliminable.  */
2807
2808 static void
2809 check_eliminable_occurrences (rtx x)
2810 {
2811   const char *fmt;
2812   int i;
2813   enum rtx_code code;
2814
2815   if (x == 0)
2816     return;
2817
2818   code = GET_CODE (x);
2819
2820   if (code == REG && REGNO (x) < FIRST_PSEUDO_REGISTER)
2821     {
2822       struct elim_table *ep;
2823
2824       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
2825         if (ep->from_rtx == x && ep->can_eliminate)
2826           ep->can_eliminate = 0;
2827       return;
2828     }
2829
2830   fmt = GET_RTX_FORMAT (code);
2831   for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
2832     {
2833       if (*fmt == 'e')
2834         check_eliminable_occurrences (XEXP (x, i));
2835       else if (*fmt == 'E')
2836         {
2837           int j;
2838           for (j = 0; j < XVECLEN (x, i); j++)
2839             check_eliminable_occurrences (XVECEXP (x, i, j));
2840         }
2841     }
2842 }
2843 \f
2844 /* Scan INSN and eliminate all eliminable registers in it.
2845
2846    If REPLACE is nonzero, do the replacement destructively.  Also
2847    delete the insn as dead it if it is setting an eliminable register.
2848
2849    If REPLACE is zero, do all our allocations in reload_obstack.
2850
2851    If no eliminations were done and this insn doesn't require any elimination
2852    processing (these are not identical conditions: it might be updating sp,
2853    but not referencing fp; this needs to be seen during reload_as_needed so
2854    that the offset between fp and sp can be taken into consideration), zero
2855    is returned.  Otherwise, 1 is returned.  */
2856
2857 static int
2858 eliminate_regs_in_insn (rtx insn, int replace)
2859 {
2860   int icode = recog_memoized (insn);
2861   rtx old_body = PATTERN (insn);
2862   int insn_is_asm = asm_noperands (old_body) >= 0;
2863   rtx old_set = single_set (insn);
2864   rtx new_body;
2865   int val = 0;
2866   int i;
2867   rtx substed_operand[MAX_RECOG_OPERANDS];
2868   rtx orig_operand[MAX_RECOG_OPERANDS];
2869   struct elim_table *ep;
2870
2871   if (! insn_is_asm && icode < 0)
2872     {
2873       if (GET_CODE (PATTERN (insn)) == USE
2874           || GET_CODE (PATTERN (insn)) == CLOBBER
2875           || GET_CODE (PATTERN (insn)) == ADDR_VEC
2876           || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC
2877           || GET_CODE (PATTERN (insn)) == ASM_INPUT)
2878         return 0;
2879       abort ();
2880     }
2881
2882   if (old_set != 0 && GET_CODE (SET_DEST (old_set)) == REG
2883       && REGNO (SET_DEST (old_set)) < FIRST_PSEUDO_REGISTER)
2884     {
2885       /* Check for setting an eliminable register.  */
2886       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
2887         if (ep->from_rtx == SET_DEST (old_set) && ep->can_eliminate)
2888           {
2889 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2890             /* If this is setting the frame pointer register to the
2891                hardware frame pointer register and this is an elimination
2892                that will be done (tested above), this insn is really
2893                adjusting the frame pointer downward to compensate for
2894                the adjustment done before a nonlocal goto.  */
2895             if (ep->from == FRAME_POINTER_REGNUM
2896                 && ep->to == HARD_FRAME_POINTER_REGNUM)
2897               {
2898                 rtx base = SET_SRC (old_set);
2899                 rtx base_insn = insn;
2900                 HOST_WIDE_INT offset = 0;
2901
2902                 while (base != ep->to_rtx)
2903                   {
2904                     rtx prev_insn, prev_set;
2905
2906                     if (GET_CODE (base) == PLUS
2907                         && GET_CODE (XEXP (base, 1)) == CONST_INT)
2908                       {
2909                         offset += INTVAL (XEXP (base, 1));
2910                         base = XEXP (base, 0);
2911                       }
2912                     else if ((prev_insn = prev_nonnote_insn (base_insn)) != 0
2913                              && (prev_set = single_set (prev_insn)) != 0
2914                              && rtx_equal_p (SET_DEST (prev_set), base))
2915                       {
2916                         base = SET_SRC (prev_set);
2917                         base_insn = prev_insn;
2918                       }
2919                     else
2920                       break;
2921                   }
2922
2923                 if (base == ep->to_rtx)
2924                   {
2925                     rtx src
2926                       = plus_constant (ep->to_rtx, offset - ep->offset);
2927
2928                     new_body = old_body;
2929                     if (! replace)
2930                       {
2931                         new_body = copy_insn (old_body);
2932                         if (REG_NOTES (insn))
2933                           REG_NOTES (insn) = copy_insn_1 (REG_NOTES (insn));
2934                       }
2935                     PATTERN (insn) = new_body;
2936                     old_set = single_set (insn);
2937
2938                     /* First see if this insn remains valid when we
2939                        make the change.  If not, keep the INSN_CODE
2940                        the same and let reload fit it up.  */
2941                     validate_change (insn, &SET_SRC (old_set), src, 1);
2942                     validate_change (insn, &SET_DEST (old_set),
2943                                      ep->to_rtx, 1);
2944                     if (! apply_change_group ())
2945                       {
2946                         SET_SRC (old_set) = src;
2947                         SET_DEST (old_set) = ep->to_rtx;
2948                       }
2949
2950                     val = 1;
2951                     goto done;
2952                   }
2953               }
2954 #endif
2955
2956             /* In this case this insn isn't serving a useful purpose.  We
2957                will delete it in reload_as_needed once we know that this
2958                elimination is, in fact, being done.
2959
2960                If REPLACE isn't set, we can't delete this insn, but needn't
2961                process it since it won't be used unless something changes.  */
2962             if (replace)
2963               {
2964                 delete_dead_insn (insn);
2965                 return 1;
2966               }
2967             val = 1;
2968             goto done;
2969           }
2970     }
2971
2972   /* We allow one special case which happens to work on all machines we
2973      currently support: a single set with the source being a PLUS of an
2974      eliminable register and a constant.  */
2975   if (old_set
2976       && GET_CODE (SET_DEST (old_set)) == REG
2977       && GET_CODE (SET_SRC (old_set)) == PLUS
2978       && GET_CODE (XEXP (SET_SRC (old_set), 0)) == REG
2979       && GET_CODE (XEXP (SET_SRC (old_set), 1)) == CONST_INT
2980       && REGNO (XEXP (SET_SRC (old_set), 0)) < FIRST_PSEUDO_REGISTER)
2981     {
2982       rtx reg = XEXP (SET_SRC (old_set), 0);
2983       HOST_WIDE_INT offset = INTVAL (XEXP (SET_SRC (old_set), 1));
2984
2985       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
2986         if (ep->from_rtx == reg && ep->can_eliminate)
2987           {
2988             offset += ep->offset;
2989
2990             if (offset == 0)
2991               {
2992                 int num_clobbers;
2993                 /* We assume here that if we need a PARALLEL with
2994                    CLOBBERs for this assignment, we can do with the
2995                    MATCH_SCRATCHes that add_clobbers allocates.
2996                    There's not much we can do if that doesn't work.  */
2997                 PATTERN (insn) = gen_rtx_SET (VOIDmode,
2998                                               SET_DEST (old_set),
2999                                               ep->to_rtx);
3000                 num_clobbers = 0;
3001                 INSN_CODE (insn) = recog (PATTERN (insn), insn, &num_clobbers);
3002                 if (num_clobbers)
3003                   {
3004                     rtvec vec = rtvec_alloc (num_clobbers + 1);
3005
3006                     vec->elem[0] = PATTERN (insn);
3007                     PATTERN (insn) = gen_rtx_PARALLEL (VOIDmode, vec);
3008                     add_clobbers (PATTERN (insn), INSN_CODE (insn));
3009                   }
3010                 if (INSN_CODE (insn) < 0)
3011                   abort ();
3012               }
3013             else
3014               {
3015                 new_body = old_body;
3016                 if (! replace)
3017                   {
3018                     new_body = copy_insn (old_body);
3019                     if (REG_NOTES (insn))
3020                       REG_NOTES (insn) = copy_insn_1 (REG_NOTES (insn));
3021                   }
3022                 PATTERN (insn) = new_body;
3023                 old_set = single_set (insn);
3024
3025                 XEXP (SET_SRC (old_set), 0) = ep->to_rtx;
3026                 XEXP (SET_SRC (old_set), 1) = GEN_INT (offset);
3027               }
3028             val = 1;
3029             /* This can't have an effect on elimination offsets, so skip right
3030                to the end.  */
3031             goto done;
3032           }
3033     }
3034
3035   /* Determine the effects of this insn on elimination offsets.  */
3036   elimination_effects (old_body, 0);
3037
3038   /* Eliminate all eliminable registers occurring in operands that
3039      can be handled by reload.  */
3040   extract_insn (insn);
3041   for (i = 0; i < recog_data.n_operands; i++)
3042     {
3043       orig_operand[i] = recog_data.operand[i];
3044       substed_operand[i] = recog_data.operand[i];
3045
3046       /* For an asm statement, every operand is eliminable.  */
3047       if (insn_is_asm || insn_data[icode].operand[i].eliminable)
3048         {
3049           /* Check for setting a register that we know about.  */
3050           if (recog_data.operand_type[i] != OP_IN
3051               && GET_CODE (orig_operand[i]) == REG)
3052             {
3053               /* If we are assigning to a register that can be eliminated, it
3054                  must be as part of a PARALLEL, since the code above handles
3055                  single SETs.  We must indicate that we can no longer
3056                  eliminate this reg.  */
3057               for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
3058                    ep++)
3059                 if (ep->from_rtx == orig_operand[i] && ep->can_eliminate)
3060                   ep->can_eliminate = 0;
3061             }
3062
3063           substed_operand[i] = eliminate_regs (recog_data.operand[i], 0,
3064                                                replace ? insn : NULL_RTX);
3065           if (substed_operand[i] != orig_operand[i])
3066             val = 1;
3067           /* Terminate the search in check_eliminable_occurrences at
3068              this point.  */
3069           *recog_data.operand_loc[i] = 0;
3070
3071         /* If an output operand changed from a REG to a MEM and INSN is an
3072            insn, write a CLOBBER insn.  */
3073           if (recog_data.operand_type[i] != OP_IN
3074               && GET_CODE (orig_operand[i]) == REG
3075               && GET_CODE (substed_operand[i]) == MEM
3076               && replace)
3077             emit_insn_after (gen_rtx_CLOBBER (VOIDmode, orig_operand[i]),
3078                              insn);
3079         }
3080     }
3081
3082   for (i = 0; i < recog_data.n_dups; i++)
3083     *recog_data.dup_loc[i]
3084       = *recog_data.operand_loc[(int) recog_data.dup_num[i]];
3085
3086   /* If any eliminable remain, they aren't eliminable anymore.  */
3087   check_eliminable_occurrences (old_body);
3088
3089   /* Substitute the operands; the new values are in the substed_operand
3090      array.  */
3091   for (i = 0; i < recog_data.n_operands; i++)
3092     *recog_data.operand_loc[i] = substed_operand[i];
3093   for (i = 0; i < recog_data.n_dups; i++)
3094     *recog_data.dup_loc[i] = substed_operand[(int) recog_data.dup_num[i]];
3095
3096   /* If we are replacing a body that was a (set X (plus Y Z)), try to
3097      re-recognize the insn.  We do this in case we had a simple addition
3098      but now can do this as a load-address.  This saves an insn in this
3099      common case.
3100      If re-recognition fails, the old insn code number will still be used,
3101      and some register operands may have changed into PLUS expressions.
3102      These will be handled by find_reloads by loading them into a register
3103      again.  */
3104
3105   if (val)
3106     {
3107       /* If we aren't replacing things permanently and we changed something,
3108          make another copy to ensure that all the RTL is new.  Otherwise
3109          things can go wrong if find_reload swaps commutative operands
3110          and one is inside RTL that has been copied while the other is not.  */
3111       new_body = old_body;
3112       if (! replace)
3113         {
3114           new_body = copy_insn (old_body);
3115           if (REG_NOTES (insn))
3116             REG_NOTES (insn) = copy_insn_1 (REG_NOTES (insn));
3117         }
3118       PATTERN (insn) = new_body;
3119
3120       /* If we had a move insn but now we don't, rerecognize it.  This will
3121          cause spurious re-recognition if the old move had a PARALLEL since
3122          the new one still will, but we can't call single_set without
3123          having put NEW_BODY into the insn and the re-recognition won't
3124          hurt in this rare case.  */
3125       /* ??? Why this huge if statement - why don't we just rerecognize the
3126          thing always?  */
3127       if (! insn_is_asm
3128           && old_set != 0
3129           && ((GET_CODE (SET_SRC (old_set)) == REG
3130                && (GET_CODE (new_body) != SET
3131                    || GET_CODE (SET_SRC (new_body)) != REG))
3132               /* If this was a load from or store to memory, compare
3133                  the MEM in recog_data.operand to the one in the insn.
3134                  If they are not equal, then rerecognize the insn.  */
3135               || (old_set != 0
3136                   && ((GET_CODE (SET_SRC (old_set)) == MEM
3137                        && SET_SRC (old_set) != recog_data.operand[1])
3138                       || (GET_CODE (SET_DEST (old_set)) == MEM
3139                           && SET_DEST (old_set) != recog_data.operand[0])))
3140               /* If this was an add insn before, rerecognize.  */
3141               || GET_CODE (SET_SRC (old_set)) == PLUS))
3142         {
3143           int new_icode = recog (PATTERN (insn), insn, 0);
3144           if (new_icode < 0)
3145             INSN_CODE (insn) = icode;
3146         }
3147     }
3148
3149   /* Restore the old body.  If there were any changes to it, we made a copy
3150      of it while the changes were still in place, so we'll correctly return
3151      a modified insn below.  */
3152   if (! replace)
3153     {
3154       /* Restore the old body.  */
3155       for (i = 0; i < recog_data.n_operands; i++)
3156         *recog_data.operand_loc[i] = orig_operand[i];
3157       for (i = 0; i < recog_data.n_dups; i++)
3158         *recog_data.dup_loc[i] = orig_operand[(int) recog_data.dup_num[i]];
3159     }
3160
3161   /* Update all elimination pairs to reflect the status after the current
3162      insn.  The changes we make were determined by the earlier call to
3163      elimination_effects.
3164
3165      We also detect cases where register elimination cannot be done,
3166      namely, if a register would be both changed and referenced outside a MEM
3167      in the resulting insn since such an insn is often undefined and, even if
3168      not, we cannot know what meaning will be given to it.  Note that it is
3169      valid to have a register used in an address in an insn that changes it
3170      (presumably with a pre- or post-increment or decrement).
3171
3172      If anything changes, return nonzero.  */
3173
3174   for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
3175     {
3176       if (ep->previous_offset != ep->offset && ep->ref_outside_mem)
3177         ep->can_eliminate = 0;
3178
3179       ep->ref_outside_mem = 0;
3180
3181       if (ep->previous_offset != ep->offset)
3182         val = 1;
3183     }
3184
3185  done:
3186   /* If we changed something, perform elimination in REG_NOTES.  This is
3187      needed even when REPLACE is zero because a REG_DEAD note might refer
3188      to a register that we eliminate and could cause a different number
3189      of spill registers to be needed in the final reload pass than in
3190      the pre-passes.  */
3191   if (val && REG_NOTES (insn) != 0)
3192     REG_NOTES (insn) = eliminate_regs (REG_NOTES (insn), 0, REG_NOTES (insn));
3193
3194   return val;
3195 }
3196
3197 /* Loop through all elimination pairs.
3198    Recalculate the number not at initial offset.
3199
3200    Compute the maximum offset (minimum offset if the stack does not
3201    grow downward) for each elimination pair.  */
3202
3203 static void
3204 update_eliminable_offsets (void)
3205 {
3206   struct elim_table *ep;
3207
3208   num_not_at_initial_offset = 0;
3209   for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
3210     {
3211       ep->previous_offset = ep->offset;
3212       if (ep->can_eliminate && ep->offset != ep->initial_offset)
3213         num_not_at_initial_offset++;
3214     }
3215 }
3216
3217 /* Given X, a SET or CLOBBER of DEST, if DEST is the target of a register
3218    replacement we currently believe is valid, mark it as not eliminable if X
3219    modifies DEST in any way other than by adding a constant integer to it.
3220
3221    If DEST is the frame pointer, we do nothing because we assume that
3222    all assignments to the hard frame pointer are nonlocal gotos and are being
3223    done at a time when they are valid and do not disturb anything else.
3224    Some machines want to eliminate a fake argument pointer with either the
3225    frame or stack pointer.  Assignments to the hard frame pointer must not
3226    prevent this elimination.
3227
3228    Called via note_stores from reload before starting its passes to scan
3229    the insns of the function.  */
3230
3231 static void
3232 mark_not_eliminable (rtx dest, rtx x, void *data ATTRIBUTE_UNUSED)
3233 {
3234   unsigned int i;
3235
3236   /* A SUBREG of a hard register here is just changing its mode.  We should
3237      not see a SUBREG of an eliminable hard register, but check just in
3238      case.  */
3239   if (GET_CODE (dest) == SUBREG)
3240     dest = SUBREG_REG (dest);
3241
3242   if (dest == hard_frame_pointer_rtx)
3243     return;
3244
3245   for (i = 0; i < NUM_ELIMINABLE_REGS; i++)
3246     if (reg_eliminate[i].can_eliminate && dest == reg_eliminate[i].to_rtx
3247         && (GET_CODE (x) != SET
3248             || GET_CODE (SET_SRC (x)) != PLUS
3249             || XEXP (SET_SRC (x), 0) != dest
3250             || GET_CODE (XEXP (SET_SRC (x), 1)) != CONST_INT))
3251       {
3252         reg_eliminate[i].can_eliminate_previous
3253           = reg_eliminate[i].can_eliminate = 0;
3254         num_eliminable--;
3255       }
3256 }
3257
3258 /* Verify that the initial elimination offsets did not change since the
3259    last call to set_initial_elim_offsets.  This is used to catch cases
3260    where something illegal happened during reload_as_needed that could
3261    cause incorrect code to be generated if we did not check for it.  */
3262
3263 static void
3264 verify_initial_elim_offsets (void)
3265 {
3266   HOST_WIDE_INT t;
3267
3268 #ifdef ELIMINABLE_REGS
3269   struct elim_table *ep;
3270
3271   for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
3272     {
3273       INITIAL_ELIMINATION_OFFSET (ep->from, ep->to, t);
3274       if (t != ep->initial_offset)
3275         abort ();
3276     }
3277 #else
3278   INITIAL_FRAME_POINTER_OFFSET (t);
3279   if (t != reg_eliminate[0].initial_offset)
3280     abort ();
3281 #endif
3282 }
3283
3284 /* Reset all offsets on eliminable registers to their initial values.  */
3285
3286 static void
3287 set_initial_elim_offsets (void)
3288 {
3289   struct elim_table *ep = reg_eliminate;
3290
3291 #ifdef ELIMINABLE_REGS
3292   for (; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
3293     {
3294       INITIAL_ELIMINATION_OFFSET (ep->from, ep->to, ep->initial_offset);
3295       ep->previous_offset = ep->offset = ep->initial_offset;
3296     }
3297 #else
3298   INITIAL_FRAME_POINTER_OFFSET (ep->initial_offset);
3299   ep->previous_offset = ep->offset = ep->initial_offset;
3300 #endif
3301
3302   num_not_at_initial_offset = 0;
3303 }
3304
3305 /* Initialize the known label offsets.
3306    Set a known offset for each forced label to be at the initial offset
3307    of each elimination.  We do this because we assume that all
3308    computed jumps occur from a location where each elimination is
3309    at its initial offset.
3310    For all other labels, show that we don't know the offsets.  */
3311
3312 static void
3313 set_initial_label_offsets (void)
3314 {
3315   rtx x;
3316   memset (offsets_known_at, 0, num_labels);
3317
3318   for (x = forced_labels; x; x = XEXP (x, 1))
3319     if (XEXP (x, 0))
3320       set_label_offsets (XEXP (x, 0), NULL_RTX, 1);
3321 }
3322
3323 /* Set all elimination offsets to the known values for the code label given
3324    by INSN.  */
3325
3326 static void
3327 set_offsets_for_label (rtx insn)
3328 {
3329   unsigned int i;
3330   int label_nr = CODE_LABEL_NUMBER (insn);
3331   struct elim_table *ep;
3332
3333   num_not_at_initial_offset = 0;
3334   for (i = 0, ep = reg_eliminate; i < NUM_ELIMINABLE_REGS; ep++, i++)
3335     {
3336       ep->offset = ep->previous_offset
3337                  = offsets_at[label_nr - first_label_num][i];
3338       if (ep->can_eliminate && ep->offset != ep->initial_offset)
3339         num_not_at_initial_offset++;
3340     }
3341 }
3342
3343 /* See if anything that happened changes which eliminations are valid.
3344    For example, on the SPARC, whether or not the frame pointer can
3345    be eliminated can depend on what registers have been used.  We need
3346    not check some conditions again (such as flag_omit_frame_pointer)
3347    since they can't have changed.  */
3348
3349 static void
3350 update_eliminables (HARD_REG_SET *pset)
3351 {
3352   int previous_frame_pointer_needed = frame_pointer_needed;
3353   struct elim_table *ep;
3354
3355   for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
3356     if ((ep->from == HARD_FRAME_POINTER_REGNUM && FRAME_POINTER_REQUIRED)
3357 #ifdef ELIMINABLE_REGS
3358         || ! CAN_ELIMINATE (ep->from, ep->to)
3359 #endif
3360         )
3361       ep->can_eliminate = 0;
3362
3363   /* Look for the case where we have discovered that we can't replace
3364      register A with register B and that means that we will now be
3365      trying to replace register A with register C.  This means we can
3366      no longer replace register C with register B and we need to disable
3367      such an elimination, if it exists.  This occurs often with A == ap,
3368      B == sp, and C == fp.  */
3369
3370   for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
3371     {
3372       struct elim_table *op;
3373       int new_to = -1;
3374
3375       if (! ep->can_eliminate && ep->can_eliminate_previous)
3376         {
3377           /* Find the current elimination for ep->from, if there is a
3378              new one.  */
3379           for (op = reg_eliminate;
3380                op < &reg_eliminate[NUM_ELIMINABLE_REGS]; op++)
3381             if (op->from == ep->from && op->can_eliminate)
3382               {
3383                 new_to = op->to;
3384                 break;
3385               }
3386
3387           /* See if there is an elimination of NEW_TO -> EP->TO.  If so,
3388              disable it.  */
3389           for (op = reg_eliminate;
3390                op < &reg_eliminate[NUM_ELIMINABLE_REGS]; op++)
3391             if (op->from == new_to && op->to == ep->to)
3392               op->can_eliminate = 0;
3393         }
3394     }
3395
3396   /* See if any registers that we thought we could eliminate the previous
3397      time are no longer eliminable.  If so, something has changed and we
3398      must spill the register.  Also, recompute the number of eliminable
3399      registers and see if the frame pointer is needed; it is if there is
3400      no elimination of the frame pointer that we can perform.  */
3401
3402   frame_pointer_needed = 1;
3403   for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
3404     {
3405       if (ep->can_eliminate && ep->from == FRAME_POINTER_REGNUM
3406           && ep->to != HARD_FRAME_POINTER_REGNUM)
3407         frame_pointer_needed = 0;
3408
3409       if (! ep->can_eliminate && ep->can_eliminate_previous)
3410         {
3411           ep->can_eliminate_previous = 0;
3412           SET_HARD_REG_BIT (*pset, ep->from);
3413           num_eliminable--;
3414         }
3415     }
3416
3417   /* If we didn't need a frame pointer last time, but we do now, spill
3418      the hard frame pointer.  */
3419   if (frame_pointer_needed && ! previous_frame_pointer_needed)
3420     SET_HARD_REG_BIT (*pset, HARD_FRAME_POINTER_REGNUM);
3421 }
3422
3423 /* Initialize the table of registers to eliminate.  */
3424
3425 static void
3426 init_elim_table (void)
3427 {
3428   struct elim_table *ep;
3429 #ifdef ELIMINABLE_REGS
3430   const struct elim_table_1 *ep1;
3431 #endif
3432
3433   if (!reg_eliminate)
3434     reg_eliminate = xcalloc (sizeof (struct elim_table), NUM_ELIMINABLE_REGS);
3435
3436   /* Does this function require a frame pointer?  */
3437
3438   frame_pointer_needed = (! flag_omit_frame_pointer
3439 #ifdef EXIT_IGNORE_STACK
3440                           /* ?? If EXIT_IGNORE_STACK is set, we will not save
3441                              and restore sp for alloca.  So we can't eliminate
3442                              the frame pointer in that case.  At some point,
3443                              we should improve this by emitting the
3444                              sp-adjusting insns for this case.  */
3445                           || (current_function_calls_alloca
3446                               && EXIT_IGNORE_STACK)
3447 #endif
3448                           || FRAME_POINTER_REQUIRED);
3449
3450   num_eliminable = 0;
3451
3452 #ifdef ELIMINABLE_REGS
3453   for (ep = reg_eliminate, ep1 = reg_eliminate_1;
3454        ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++, ep1++)
3455     {
3456       ep->from = ep1->from;
3457       ep->to = ep1->to;
3458       ep->can_eliminate = ep->can_eliminate_previous
3459         = (CAN_ELIMINATE (ep->from, ep->to)
3460            && ! (ep->to == STACK_POINTER_REGNUM && frame_pointer_needed));
3461     }
3462 #else
3463   reg_eliminate[0].from = reg_eliminate_1[0].from;
3464   reg_eliminate[0].to = reg_eliminate_1[0].to;
3465   reg_eliminate[0].can_eliminate = reg_eliminate[0].can_eliminate_previous
3466     = ! frame_pointer_needed;
3467 #endif
3468
3469   /* Count the number of eliminable registers and build the FROM and TO
3470      REG rtx's.  Note that code in gen_rtx will cause, e.g.,
3471      gen_rtx (REG, Pmode, STACK_POINTER_REGNUM) to equal stack_pointer_rtx.
3472      We depend on this.  */
3473   for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
3474     {
3475       num_eliminable += ep->can_eliminate;
3476       ep->from_rtx = gen_rtx_REG (Pmode, ep->from);
3477       ep->to_rtx = gen_rtx_REG (Pmode, ep->to);
3478     }
3479 }
3480 \f
3481 /* Kick all pseudos out of hard register REGNO.
3482
3483    If CANT_ELIMINATE is nonzero, it means that we are doing this spill
3484    because we found we can't eliminate some register.  In the case, no pseudos
3485    are allowed to be in the register, even if they are only in a block that
3486    doesn't require spill registers, unlike the case when we are spilling this
3487    hard reg to produce another spill register.
3488
3489    Return nonzero if any pseudos needed to be kicked out.  */
3490
3491 static void
3492 spill_hard_reg (unsigned int regno, int cant_eliminate)
3493 {
3494   int i;
3495
3496   if (cant_eliminate)
3497     {
3498       SET_HARD_REG_BIT (bad_spill_regs_global, regno);
3499       regs_ever_live[regno] = 1;
3500     }
3501
3502   /* Spill every pseudo reg that was allocated to this reg
3503      or to something that overlaps this reg.  */
3504
3505   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
3506     if (reg_renumber[i] >= 0
3507         && (unsigned int) reg_renumber[i] <= regno
3508         && ((unsigned int) reg_renumber[i]
3509             + HARD_REGNO_NREGS ((unsigned int) reg_renumber[i],
3510                                 PSEUDO_REGNO_MODE (i))
3511             > regno))
3512       SET_REGNO_REG_SET (&spilled_pseudos, i);
3513 }
3514
3515 /* I'm getting weird preprocessor errors if I use IOR_HARD_REG_SET
3516    from within EXECUTE_IF_SET_IN_REG_SET.  Hence this awkwardness.  */
3517
3518 static void
3519 ior_hard_reg_set (HARD_REG_SET *set1, HARD_REG_SET *set2)
3520 {
3521   IOR_HARD_REG_SET (*set1, *set2);
3522 }
3523
3524 /* After find_reload_regs has been run for all insn that need reloads,
3525    and/or spill_hard_regs was called, this function is used to actually
3526    spill pseudo registers and try to reallocate them.  It also sets up the
3527    spill_regs array for use by choose_reload_regs.  */
3528
3529 static int
3530 finish_spills (int global)
3531 {
3532   struct insn_chain *chain;
3533   int something_changed = 0;
3534   int i;
3535
3536   /* Build the spill_regs array for the function.  */
3537   /* If there are some registers still to eliminate and one of the spill regs
3538      wasn't ever used before, additional stack space may have to be
3539      allocated to store this register.  Thus, we may have changed the offset
3540      between the stack and frame pointers, so mark that something has changed.
3541
3542      One might think that we need only set VAL to 1 if this is a call-used
3543      register.  However, the set of registers that must be saved by the
3544      prologue is not identical to the call-used set.  For example, the
3545      register used by the call insn for the return PC is a call-used register,
3546      but must be saved by the prologue.  */
3547
3548   n_spills = 0;
3549   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3550     if (TEST_HARD_REG_BIT (used_spill_regs, i))
3551       {
3552         spill_reg_order[i] = n_spills;
3553         spill_regs[n_spills++] = i;
3554         if (num_eliminable && ! regs_ever_live[i])
3555           something_changed = 1;
3556         regs_ever_live[i] = 1;
3557       }
3558     else
3559       spill_reg_order[i] = -1;
3560
3561   EXECUTE_IF_SET_IN_REG_SET
3562     (&spilled_pseudos, FIRST_PSEUDO_REGISTER, i,
3563      {
3564        /* Record the current hard register the pseudo is allocated to in
3565           pseudo_previous_regs so we avoid reallocating it to the same
3566           hard reg in a later pass.  */
3567        if (reg_renumber[i] < 0)
3568          abort ();
3569
3570        SET_HARD_REG_BIT (pseudo_previous_regs[i], reg_renumber[i]);
3571        /* Mark it as no longer having a hard register home.  */
3572        reg_renumber[i] = -1;
3573        /* We will need to scan everything again.  */
3574        something_changed = 1;
3575      });
3576
3577   /* Retry global register allocation if possible.  */
3578   if (global)
3579     {
3580       memset (pseudo_forbidden_regs, 0, max_regno * sizeof (HARD_REG_SET));
3581       /* For every insn that needs reloads, set the registers used as spill
3582          regs in pseudo_forbidden_regs for every pseudo live across the
3583          insn.  */
3584       for (chain = insns_need_reload; chain; chain = chain->next_need_reload)
3585         {
3586           EXECUTE_IF_SET_IN_REG_SET
3587             (&chain->live_throughout, FIRST_PSEUDO_REGISTER, i,
3588              {
3589                ior_hard_reg_set (pseudo_forbidden_regs + i,
3590                                  &chain->used_spill_regs);
3591              });
3592           EXECUTE_IF_SET_IN_REG_SET
3593             (&chain->dead_or_set, FIRST_PSEUDO_REGISTER, i,
3594              {
3595                ior_hard_reg_set (pseudo_forbidden_regs + i,
3596                                  &chain->used_spill_regs);
3597              });
3598         }
3599
3600       /* Retry allocating the spilled pseudos.  For each reg, merge the
3601          various reg sets that indicate which hard regs can't be used,
3602          and call retry_global_alloc.
3603          We change spill_pseudos here to only contain pseudos that did not
3604          get a new hard register.  */
3605       for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
3606         if (reg_old_renumber[i] != reg_renumber[i])
3607           {
3608             HARD_REG_SET forbidden;
3609             COPY_HARD_REG_SET (forbidden, bad_spill_regs_global);
3610             IOR_HARD_REG_SET (forbidden, pseudo_forbidden_regs[i]);
3611             IOR_HARD_REG_SET (forbidden, pseudo_previous_regs[i]);
3612             retry_global_alloc (i, forbidden);
3613             if (reg_renumber[i] >= 0)
3614               CLEAR_REGNO_REG_SET (&spilled_pseudos, i);
3615           }
3616     }
3617
3618   /* Fix up the register information in the insn chain.
3619      This involves deleting those of the spilled pseudos which did not get
3620      a new hard register home from the live_{before,after} sets.  */
3621   for (chain = reload_insn_chain; chain; chain = chain->next)
3622     {
3623       HARD_REG_SET used_by_pseudos;
3624       HARD_REG_SET used_by_pseudos2;
3625
3626       AND_COMPL_REG_SET (&chain->live_throughout, &spilled_pseudos);
3627       AND_COMPL_REG_SET (&chain->dead_or_set, &spilled_pseudos);
3628
3629       /* Mark any unallocated hard regs as available for spills.  That
3630          makes inheritance work somewhat better.  */
3631       if (chain->need_reload)
3632         {
3633           REG_SET_TO_HARD_REG_SET (used_by_pseudos, &chain->live_throughout);
3634           REG_SET_TO_HARD_REG_SET (used_by_pseudos2, &chain->dead_or_set);
3635           IOR_HARD_REG_SET (used_by_pseudos, used_by_pseudos2);
3636
3637           /* Save the old value for the sanity test below.  */
3638           COPY_HARD_REG_SET (used_by_pseudos2, chain->used_spill_regs);
3639
3640           compute_use_by_pseudos (&used_by_pseudos, &chain->live_throughout);
3641           compute_use_by_pseudos (&used_by_pseudos, &chain->dead_or_set);
3642           COMPL_HARD_REG_SET (chain->used_spill_regs, used_by_pseudos);
3643           AND_HARD_REG_SET (chain->used_spill_regs, used_spill_regs);
3644
3645           /* Make sure we only enlarge the set.  */
3646           GO_IF_HARD_REG_SUBSET (used_by_pseudos2, chain->used_spill_regs, ok);
3647           abort ();
3648         ok:;
3649         }
3650     }
3651
3652   /* Let alter_reg modify the reg rtx's for the modified pseudos.  */
3653   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
3654     {
3655       int regno = reg_renumber[i];
3656       if (reg_old_renumber[i] == regno)
3657         continue;
3658
3659       alter_reg (i, reg_old_renumber[i]);
3660       reg_old_renumber[i] = regno;
3661       if (rtl_dump_file)
3662         {
3663           if (regno == -1)
3664             fprintf (rtl_dump_file, " Register %d now on stack.\n\n", i);
3665           else
3666             fprintf (rtl_dump_file, " Register %d now in %d.\n\n",
3667                      i, reg_renumber[i]);
3668         }
3669     }
3670
3671   return something_changed;
3672 }
3673 \f
3674 /* Find all paradoxical subregs within X and update reg_max_ref_width.
3675    Also mark any hard registers used to store user variables as
3676    forbidden from being used for spill registers.  */
3677
3678 static void
3679 scan_paradoxical_subregs (rtx x)
3680 {
3681   int i;
3682   const char *fmt;
3683   enum rtx_code code = GET_CODE (x);
3684
3685   switch (code)
3686     {
3687     case REG:
3688 #if 0
3689       if (SMALL_REGISTER_CLASSES && REGNO (x) < FIRST_PSEUDO_REGISTER
3690           && REG_USERVAR_P (x))
3691         SET_HARD_REG_BIT (bad_spill_regs_global, REGNO (x));
3692 #endif
3693       return;
3694
3695     case CONST_INT:
3696     case CONST:
3697     case SYMBOL_REF:
3698     case LABEL_REF:
3699     case CONST_DOUBLE:
3700     case CONST_VECTOR: /* shouldn't happen, but just in case.  */
3701     case CC0:
3702     case PC:
3703     case USE:
3704     case CLOBBER:
3705       return;
3706
3707     case SUBREG:
3708       if (GET_CODE (SUBREG_REG (x)) == REG
3709           && GET_MODE_SIZE (GET_MODE (x)) > GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
3710         reg_max_ref_width[REGNO (SUBREG_REG (x))]
3711           = GET_MODE_SIZE (GET_MODE (x));
3712       return;
3713
3714     default:
3715       break;
3716     }
3717
3718   fmt = GET_RTX_FORMAT (code);
3719   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3720     {
3721       if (fmt[i] == 'e')
3722         scan_paradoxical_subregs (XEXP (x, i));
3723       else if (fmt[i] == 'E')
3724         {
3725           int j;
3726           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3727             scan_paradoxical_subregs (XVECEXP (x, i, j));
3728         }
3729     }
3730 }
3731 \f
3732 /* Reload pseudo-registers into hard regs around each insn as needed.
3733    Additional register load insns are output before the insn that needs it
3734    and perhaps store insns after insns that modify the reloaded pseudo reg.
3735
3736    reg_last_reload_reg and reg_reloaded_contents keep track of
3737    which registers are already available in reload registers.
3738    We update these for the reloads that we perform,
3739    as the insns are scanned.  */
3740
3741 static void
3742 reload_as_needed (int live_known)
3743 {
3744   struct insn_chain *chain;
3745 #if defined (AUTO_INC_DEC)
3746   int i;
3747 #endif
3748   rtx x;
3749
3750   memset (spill_reg_rtx, 0, sizeof spill_reg_rtx);
3751   memset (spill_reg_store, 0, sizeof spill_reg_store);
3752   reg_last_reload_reg = xcalloc (max_regno, sizeof (rtx));
3753   reg_has_output_reload = xmalloc (max_regno);
3754   CLEAR_HARD_REG_SET (reg_reloaded_valid);
3755
3756   set_initial_elim_offsets ();
3757
3758   for (chain = reload_insn_chain; chain; chain = chain->next)
3759     {
3760       rtx prev = 0;
3761       rtx insn = chain->insn;
3762       rtx old_next = NEXT_INSN (insn);
3763
3764       /* If we pass a label, copy the offsets from the label information
3765          into the current offsets of each elimination.  */
3766       if (GET_CODE (insn) == CODE_LABEL)
3767         set_offsets_for_label (insn);
3768
3769       else if (INSN_P (insn))
3770         {
3771           rtx oldpat = copy_rtx (PATTERN (insn));
3772
3773           /* If this is a USE and CLOBBER of a MEM, ensure that any
3774              references to eliminable registers have been removed.  */
3775
3776           if ((GET_CODE (PATTERN (insn)) == USE
3777                || GET_CODE (PATTERN (insn)) == CLOBBER)
3778               && GET_CODE (XEXP (PATTERN (insn), 0)) == MEM)
3779             XEXP (XEXP (PATTERN (insn), 0), 0)
3780               = eliminate_regs (XEXP (XEXP (PATTERN (insn), 0), 0),
3781                                 GET_MODE (XEXP (PATTERN (insn), 0)),
3782                                 NULL_RTX);
3783
3784           /* If we need to do register elimination processing, do so.
3785              This might delete the insn, in which case we are done.  */
3786           if ((num_eliminable || num_eliminable_invariants) && chain->need_elim)
3787             {
3788               eliminate_regs_in_insn (insn, 1);
3789               if (GET_CODE (insn) == NOTE)
3790                 {
3791                   update_eliminable_offsets ();
3792                   continue;
3793                 }
3794             }
3795
3796           /* If need_elim is nonzero but need_reload is zero, one might think
3797              that we could simply set n_reloads to 0.  However, find_reloads
3798              could have done some manipulation of the insn (such as swapping
3799              commutative operands), and these manipulations are lost during
3800              the first pass for every insn that needs register elimination.
3801              So the actions of find_reloads must be redone here.  */
3802
3803           if (! chain->need_elim && ! chain->need_reload
3804               && ! chain->need_operand_change)
3805             n_reloads = 0;
3806           /* First find the pseudo regs that must be reloaded for this insn.
3807              This info is returned in the tables reload_... (see reload.h).
3808              Also modify the body of INSN by substituting RELOAD
3809              rtx's for those pseudo regs.  */
3810           else
3811             {
3812               memset (reg_has_output_reload, 0, max_regno);
3813               CLEAR_HARD_REG_SET (reg_is_output_reload);
3814
3815               find_reloads (insn, 1, spill_indirect_levels, live_known,
3816                             spill_reg_order);
3817             }
3818
3819           if (n_reloads > 0)
3820             {
3821               rtx next = NEXT_INSN (insn);
3822               rtx p;
3823
3824               prev = PREV_INSN (insn);
3825
3826               /* Now compute which reload regs to reload them into.  Perhaps
3827                  reusing reload regs from previous insns, or else output
3828                  load insns to reload them.  Maybe output store insns too.
3829                  Record the choices of reload reg in reload_reg_rtx.  */
3830               choose_reload_regs (chain);
3831
3832               /* Merge any reloads that we didn't combine for fear of
3833                  increasing the number of spill registers needed but now
3834                  discover can be safely merged.  */
3835               if (SMALL_REGISTER_CLASSES)
3836                 merge_assigned_reloads (insn);
3837
3838               /* Generate the insns to reload operands into or out of
3839                  their reload regs.  */
3840               emit_reload_insns (chain);
3841
3842               /* Substitute the chosen reload regs from reload_reg_rtx
3843                  into the insn's body (or perhaps into the bodies of other
3844                  load and store insn that we just made for reloading
3845                  and that we moved the structure into).  */
3846               subst_reloads (insn);
3847
3848               /* If this was an ASM, make sure that all the reload insns
3849                  we have generated are valid.  If not, give an error
3850                  and delete them.  */
3851
3852               if (asm_noperands (PATTERN (insn)) >= 0)
3853                 for (p = NEXT_INSN (prev); p != next; p = NEXT_INSN (p))
3854                   if (p != insn && INSN_P (p)
3855                       && GET_CODE (PATTERN (p)) != USE
3856                       && (recog_memoized (p) < 0
3857                           || (extract_insn (p), ! constrain_operands (1))))
3858                     {
3859                       error_for_asm (insn,
3860                                      "`asm' operand requires impossible reload");
3861                       delete_insn (p);
3862                     }
3863             }
3864
3865           if (num_eliminable && chain->need_elim)
3866             update_eliminable_offsets ();
3867
3868           /* Any previously reloaded spilled pseudo reg, stored in this insn,
3869              is no longer validly lying around to save a future reload.
3870              Note that this does not detect pseudos that were reloaded
3871              for this insn in order to be stored in
3872              (obeying register constraints).  That is correct; such reload
3873              registers ARE still valid.  */
3874           note_stores (oldpat, forget_old_reloads_1, NULL);
3875
3876           /* There may have been CLOBBER insns placed after INSN.  So scan
3877              between INSN and NEXT and use them to forget old reloads.  */
3878           for (x = NEXT_INSN (insn); x != old_next; x = NEXT_INSN (x))
3879             if (GET_CODE (x) == INSN && GET_CODE (PATTERN (x)) == CLOBBER)
3880               note_stores (PATTERN (x), forget_old_reloads_1, NULL);
3881
3882 #ifdef AUTO_INC_DEC
3883           /* Likewise for regs altered by auto-increment in this insn.
3884              REG_INC notes have been changed by reloading:
3885              find_reloads_address_1 records substitutions for them,
3886              which have been performed by subst_reloads above.  */
3887           for (i = n_reloads - 1; i >= 0; i--)
3888             {
3889               rtx in_reg = rld[i].in_reg;
3890               if (in_reg)
3891                 {
3892                   enum rtx_code code = GET_CODE (in_reg);
3893                   /* PRE_INC / PRE_DEC will have the reload register ending up
3894                      with the same value as the stack slot, but that doesn't
3895                      hold true for POST_INC / POST_DEC.  Either we have to
3896                      convert the memory access to a true POST_INC / POST_DEC,
3897                      or we can't use the reload register for inheritance.  */
3898                   if ((code == POST_INC || code == POST_DEC)
3899                       && TEST_HARD_REG_BIT (reg_reloaded_valid,
3900                                             REGNO (rld[i].reg_rtx))
3901                       /* Make sure it is the inc/dec pseudo, and not
3902                          some other (e.g. output operand) pseudo.  */
3903                       && ((unsigned) reg_reloaded_contents[REGNO (rld[i].reg_rtx)]
3904                           == REGNO (XEXP (in_reg, 0))))
3905
3906                     {
3907                       rtx reload_reg = rld[i].reg_rtx;
3908                       enum machine_mode mode = GET_MODE (reload_reg);
3909                       int n = 0;
3910                       rtx p;
3911
3912                       for (p = PREV_INSN (old_next); p != prev; p = PREV_INSN (p))
3913                         {
3914                           /* We really want to ignore REG_INC notes here, so
3915                              use PATTERN (p) as argument to reg_set_p .  */
3916                           if (reg_set_p (reload_reg, PATTERN (p)))
3917                             break;
3918                           n = count_occurrences (PATTERN (p), reload_reg, 0);
3919                           if (! n)
3920                             continue;
3921                           if (n == 1)
3922                             {
3923                               n = validate_replace_rtx (reload_reg,
3924                                                         gen_rtx (code, mode,
3925                                                                  reload_reg),
3926                                                         p);
3927
3928                               /* We must also verify that the constraints
3929                                  are met after the replacement.  */
3930                               extract_insn (p);
3931                               if (n)
3932                                 n = constrain_operands (1);
3933                               else
3934                                 break;
3935
3936                               /* If the constraints were not met, then
3937                                  undo the replacement.  */
3938                               if (!n)
3939                                 {
3940                                   validate_replace_rtx (gen_rtx (code, mode,
3941                                                                  reload_reg),
3942                                                         reload_reg, p);
3943                                   break;
3944                                 }
3945
3946                             }
3947                           break;
3948                         }
3949                       if (n == 1)
3950                         {
3951                           REG_NOTES (p)
3952                             = gen_rtx_EXPR_LIST (REG_INC, reload_reg,