OSDN Git Service

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