OSDN Git Service

* reload.c (find_reloads_address_1): Handle PLUS expressions resulting
[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, 2007
4    Free Software Foundation, 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       HOST_WIDE_INT starting_frame_size;
892
893       starting_frame_size = get_frame_size ();
894
895       set_initial_elim_offsets ();
896       set_initial_label_offsets ();
897
898       /* For each pseudo register that has an equivalent location defined,
899          try to eliminate any eliminable registers (such as the frame pointer)
900          assuming initial offsets for the replacement register, which
901          is the normal case.
902
903          If the resulting location is directly addressable, substitute
904          the MEM we just got directly for the old REG.
905
906          If it is not addressable but is a constant or the sum of a hard reg
907          and constant, it is probably not addressable because the constant is
908          out of range, in that case record the address; we will generate
909          hairy code to compute the address in a register each time it is
910          needed.  Similarly if it is a hard register, but one that is not
911          valid as an address register.
912
913          If the location is not addressable, but does not have one of the
914          above forms, assign a stack slot.  We have to do this to avoid the
915          potential of producing lots of reloads if, e.g., a location involves
916          a pseudo that didn't get a hard register and has an equivalent memory
917          location that also involves a pseudo that didn't get a hard register.
918
919          Perhaps at some point we will improve reload_when_needed handling
920          so this problem goes away.  But that's very hairy.  */
921
922       for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
923         if (reg_renumber[i] < 0 && reg_equiv_memory_loc[i])
924           {
925             rtx x = eliminate_regs (reg_equiv_memory_loc[i], 0, NULL_RTX);
926
927             if (strict_memory_address_p (GET_MODE (regno_reg_rtx[i]),
928                                          XEXP (x, 0)))
929               reg_equiv_mem[i] = x, reg_equiv_address[i] = 0;
930             else if (CONSTANT_P (XEXP (x, 0))
931                      || (REG_P (XEXP (x, 0))
932                          && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER)
933                      || (GET_CODE (XEXP (x, 0)) == PLUS
934                          && REG_P (XEXP (XEXP (x, 0), 0))
935                          && (REGNO (XEXP (XEXP (x, 0), 0))
936                              < FIRST_PSEUDO_REGISTER)
937                          && CONSTANT_P (XEXP (XEXP (x, 0), 1))))
938               reg_equiv_address[i] = XEXP (x, 0), reg_equiv_mem[i] = 0;
939             else
940               {
941                 /* Make a new stack slot.  Then indicate that something
942                    changed so we go back and recompute offsets for
943                    eliminable registers because the allocation of memory
944                    below might change some offset.  reg_equiv_{mem,address}
945                    will be set up for this pseudo on the next pass around
946                    the loop.  */
947                 reg_equiv_memory_loc[i] = 0;
948                 reg_equiv_init[i] = 0;
949                 alter_reg (i, -1);
950               }
951           }
952
953       if (caller_save_needed)
954         setup_save_areas ();
955
956       /* If we allocated another stack slot, redo elimination bookkeeping.  */
957       if (starting_frame_size != get_frame_size ())
958         continue;
959       if (starting_frame_size && cfun->stack_alignment_needed)
960         {
961           /* If we have a stack frame, we must align it now.  The
962              stack size may be a part of the offset computation for
963              register elimination.  So if this changes the stack size,
964              then repeat the elimination bookkeeping.  We don't
965              realign when there is no stack, as that will cause a
966              stack frame when none is needed should
967              STARTING_FRAME_OFFSET not be already aligned to
968              STACK_BOUNDARY.  */
969           assign_stack_local (BLKmode, 0, cfun->stack_alignment_needed);
970           if (starting_frame_size != get_frame_size ())
971             continue;
972         }
973
974       if (caller_save_needed)
975         {
976           save_call_clobbered_regs ();
977           /* That might have allocated new insn_chain structures.  */
978           reload_firstobj = obstack_alloc (&reload_obstack, 0);
979         }
980
981       calculate_needs_all_insns (global);
982
983       CLEAR_REG_SET (&spilled_pseudos);
984       did_spill = 0;
985
986       something_changed = 0;
987
988       /* If we allocated any new memory locations, make another pass
989          since it might have changed elimination offsets.  */
990       if (starting_frame_size != get_frame_size ())
991         something_changed = 1;
992
993       /* Even if the frame size remained the same, we might still have
994          changed elimination offsets, e.g. if find_reloads called 
995          force_const_mem requiring the back end to allocate a constant
996          pool base register that needs to be saved on the stack.  */
997       else if (!verify_initial_elim_offsets ())
998         something_changed = 1;
999
1000       {
1001         HARD_REG_SET to_spill;
1002         CLEAR_HARD_REG_SET (to_spill);
1003         update_eliminables (&to_spill);
1004         AND_COMPL_HARD_REG_SET (used_spill_regs, to_spill);
1005
1006         for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1007           if (TEST_HARD_REG_BIT (to_spill, i))
1008             {
1009               spill_hard_reg (i, 1);
1010               did_spill = 1;
1011
1012               /* Regardless of the state of spills, if we previously had
1013                  a register that we thought we could eliminate, but now can
1014                  not eliminate, we must run another pass.
1015
1016                  Consider pseudos which have an entry in reg_equiv_* which
1017                  reference an eliminable register.  We must make another pass
1018                  to update reg_equiv_* so that we do not substitute in the
1019                  old value from when we thought the elimination could be
1020                  performed.  */
1021               something_changed = 1;
1022             }
1023       }
1024
1025       select_reload_regs ();
1026       if (failure)
1027         goto failed;
1028
1029       if (insns_need_reload != 0 || did_spill)
1030         something_changed |= finish_spills (global);
1031
1032       if (! something_changed)
1033         break;
1034
1035       if (caller_save_needed)
1036         delete_caller_save_insns ();
1037
1038       obstack_free (&reload_obstack, reload_firstobj);
1039     }
1040
1041   /* If global-alloc was run, notify it of any register eliminations we have
1042      done.  */
1043   if (global)
1044     for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
1045       if (ep->can_eliminate)
1046         mark_elimination (ep->from, ep->to);
1047
1048   /* If a pseudo has no hard reg, delete the insns that made the equivalence.
1049      If that insn didn't set the register (i.e., it copied the register to
1050      memory), just delete that insn instead of the equivalencing insn plus
1051      anything now dead.  If we call delete_dead_insn on that insn, we may
1052      delete the insn that actually sets the register if the register dies
1053      there and that is incorrect.  */
1054
1055   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1056     {
1057       if (reg_renumber[i] < 0 && reg_equiv_init[i] != 0)
1058         {
1059           rtx list;
1060           for (list = reg_equiv_init[i]; list; list = XEXP (list, 1))
1061             {
1062               rtx equiv_insn = XEXP (list, 0);
1063
1064               /* If we already deleted the insn or if it may trap, we can't
1065                  delete it.  The latter case shouldn't happen, but can
1066                  if an insn has a variable address, gets a REG_EH_REGION
1067                  note added to it, and then gets converted into a load
1068                  from a constant address.  */
1069               if (NOTE_P (equiv_insn)
1070                   || can_throw_internal (equiv_insn))
1071                 ;
1072               else if (reg_set_p (regno_reg_rtx[i], PATTERN (equiv_insn)))
1073                 delete_dead_insn (equiv_insn);
1074               else
1075                 SET_INSN_DELETED (equiv_insn);
1076             }
1077         }
1078     }
1079
1080   /* Use the reload registers where necessary
1081      by generating move instructions to move the must-be-register
1082      values into or out of the reload registers.  */
1083
1084   if (insns_need_reload != 0 || something_needs_elimination
1085       || something_needs_operands_changed)
1086     {
1087       HOST_WIDE_INT old_frame_size = get_frame_size ();
1088
1089       reload_as_needed (global);
1090
1091       gcc_assert (old_frame_size == get_frame_size ());
1092
1093       gcc_assert (verify_initial_elim_offsets ());
1094     }
1095
1096   /* If we were able to eliminate the frame pointer, show that it is no
1097      longer live at the start of any basic block.  If it ls live by
1098      virtue of being in a pseudo, that pseudo will be marked live
1099      and hence the frame pointer will be known to be live via that
1100      pseudo.  */
1101
1102   if (! frame_pointer_needed)
1103     FOR_EACH_BB (bb)
1104       CLEAR_REGNO_REG_SET (bb->il.rtl->global_live_at_start,
1105                            HARD_FRAME_POINTER_REGNUM);
1106
1107   /* Come here (with failure set nonzero) if we can't get enough spill
1108      regs.  */
1109  failed:
1110
1111   CLEAR_REG_SET (&spilled_pseudos);
1112   reload_in_progress = 0;
1113
1114   /* Now eliminate all pseudo regs by modifying them into
1115      their equivalent memory references.
1116      The REG-rtx's for the pseudos are modified in place,
1117      so all insns that used to refer to them now refer to memory.
1118
1119      For a reg that has a reg_equiv_address, all those insns
1120      were changed by reloading so that no insns refer to it any longer;
1121      but the DECL_RTL of a variable decl may refer to it,
1122      and if so this causes the debugging info to mention the variable.  */
1123
1124   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1125     {
1126       rtx addr = 0;
1127
1128       if (reg_equiv_mem[i])
1129         addr = XEXP (reg_equiv_mem[i], 0);
1130
1131       if (reg_equiv_address[i])
1132         addr = reg_equiv_address[i];
1133
1134       if (addr)
1135         {
1136           if (reg_renumber[i] < 0)
1137             {
1138               rtx reg = regno_reg_rtx[i];
1139
1140               REG_USERVAR_P (reg) = 0;
1141               PUT_CODE (reg, MEM);
1142               XEXP (reg, 0) = addr;
1143               if (reg_equiv_memory_loc[i])
1144                 MEM_COPY_ATTRIBUTES (reg, reg_equiv_memory_loc[i]);
1145               else
1146                 {
1147                   MEM_IN_STRUCT_P (reg) = MEM_SCALAR_P (reg) = 0;
1148                   MEM_ATTRS (reg) = 0;
1149                 }
1150               MEM_NOTRAP_P (reg) = 1;
1151             }
1152           else if (reg_equiv_mem[i])
1153             XEXP (reg_equiv_mem[i], 0) = addr;
1154         }
1155     }
1156
1157   /* We must set reload_completed now since the cleanup_subreg_operands call
1158      below will re-recognize each insn and reload may have generated insns
1159      which are only valid during and after reload.  */
1160   reload_completed = 1;
1161
1162   /* Make a pass over all the insns and delete all USEs which we inserted
1163      only to tag a REG_EQUAL note on them.  Remove all REG_DEAD and REG_UNUSED
1164      notes.  Delete all CLOBBER insns, except those that refer to the return
1165      value and the special mem:BLK CLOBBERs added to prevent the scheduler
1166      from misarranging variable-array code, and simplify (subreg (reg))
1167      operands.  Also remove all REG_RETVAL and REG_LIBCALL notes since they
1168      are no longer useful or accurate.  Strip and regenerate REG_INC notes
1169      that may have been moved around.  */
1170
1171   for (insn = first; insn; insn = NEXT_INSN (insn))
1172     if (INSN_P (insn))
1173       {
1174         rtx *pnote;
1175
1176         /* Clean up invalid ASMs so that they don't confuse later passes.
1177            See PR 21299.  */
1178         if (asm_noperands (PATTERN (insn)) >= 0)
1179           {
1180             extract_insn (insn);
1181             if (!constrain_operands (1))
1182               {
1183                 error_for_asm (insn,
1184                                "%<asm%> operand has impossible constraints");
1185                 delete_insn (insn);
1186                 continue;
1187               }
1188           }
1189
1190         if (CALL_P (insn))
1191           replace_pseudos_in (& CALL_INSN_FUNCTION_USAGE (insn),
1192                               VOIDmode, CALL_INSN_FUNCTION_USAGE (insn));
1193
1194         if ((GET_CODE (PATTERN (insn)) == USE
1195              /* We mark with QImode USEs introduced by reload itself.  */
1196              && (GET_MODE (insn) == QImode
1197                  || find_reg_note (insn, REG_EQUAL, NULL_RTX)))
1198             || (GET_CODE (PATTERN (insn)) == CLOBBER
1199                 && (!MEM_P (XEXP (PATTERN (insn), 0))
1200                     || GET_MODE (XEXP (PATTERN (insn), 0)) != BLKmode
1201                     || (GET_CODE (XEXP (XEXP (PATTERN (insn), 0), 0)) != SCRATCH
1202                         && XEXP (XEXP (PATTERN (insn), 0), 0)
1203                                 != stack_pointer_rtx))
1204                 && (!REG_P (XEXP (PATTERN (insn), 0))
1205                     || ! REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0)))))
1206           {
1207             delete_insn (insn);
1208             continue;
1209           }
1210
1211         /* Some CLOBBERs may survive until here and still reference unassigned
1212            pseudos with const equivalent, which may in turn cause ICE in later
1213            passes if the reference remains in place.  */
1214         if (GET_CODE (PATTERN (insn)) == CLOBBER)
1215           replace_pseudos_in (& XEXP (PATTERN (insn), 0),
1216                               VOIDmode, PATTERN (insn));
1217
1218         /* Discard obvious no-ops, even without -O.  This optimization
1219            is fast and doesn't interfere with debugging.  */
1220         if (NONJUMP_INSN_P (insn)
1221             && GET_CODE (PATTERN (insn)) == SET
1222             && REG_P (SET_SRC (PATTERN (insn)))
1223             && REG_P (SET_DEST (PATTERN (insn)))
1224             && (REGNO (SET_SRC (PATTERN (insn)))
1225                 == REGNO (SET_DEST (PATTERN (insn)))))
1226           {
1227             delete_insn (insn);
1228             continue;
1229           }
1230
1231         pnote = &REG_NOTES (insn);
1232         while (*pnote != 0)
1233           {
1234             if (REG_NOTE_KIND (*pnote) == REG_DEAD
1235                 || REG_NOTE_KIND (*pnote) == REG_UNUSED
1236                 || REG_NOTE_KIND (*pnote) == REG_INC
1237                 || REG_NOTE_KIND (*pnote) == REG_RETVAL
1238                 || REG_NOTE_KIND (*pnote) == REG_LIBCALL)
1239               *pnote = XEXP (*pnote, 1);
1240             else
1241               pnote = &XEXP (*pnote, 1);
1242           }
1243
1244 #ifdef AUTO_INC_DEC
1245         add_auto_inc_notes (insn, PATTERN (insn));
1246 #endif
1247
1248         /* And simplify (subreg (reg)) if it appears as an operand.  */
1249         cleanup_subreg_operands (insn);
1250       }
1251
1252   /* If we are doing stack checking, give a warning if this function's
1253      frame size is larger than we expect.  */
1254   if (flag_stack_check && ! STACK_CHECK_BUILTIN)
1255     {
1256       HOST_WIDE_INT size = get_frame_size () + STACK_CHECK_FIXED_FRAME_SIZE;
1257       static int verbose_warned = 0;
1258
1259       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1260         if (regs_ever_live[i] && ! fixed_regs[i] && call_used_regs[i])
1261           size += UNITS_PER_WORD;
1262
1263       if (size > STACK_CHECK_MAX_FRAME_SIZE)
1264         {
1265           warning (0, "frame size too large for reliable stack checking");
1266           if (! verbose_warned)
1267             {
1268               warning (0, "try reducing the number of local variables");
1269               verbose_warned = 1;
1270             }
1271         }
1272     }
1273
1274   /* Indicate that we no longer have known memory locations or constants.  */
1275   if (reg_equiv_constant)
1276     free (reg_equiv_constant);
1277   if (reg_equiv_invariant)
1278     free (reg_equiv_invariant);
1279   reg_equiv_constant = 0;
1280   reg_equiv_invariant = 0;
1281   VEC_free (rtx, gc, reg_equiv_memory_loc_vec);
1282   reg_equiv_memory_loc = 0;
1283
1284   if (offsets_known_at)
1285     free (offsets_known_at);
1286   if (offsets_at)
1287     free (offsets_at);
1288
1289   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1290     if (reg_equiv_alt_mem_list[i])
1291       free_EXPR_LIST_list (&reg_equiv_alt_mem_list[i]);
1292   free (reg_equiv_alt_mem_list);
1293
1294   free (reg_equiv_mem);
1295   reg_equiv_init = 0;
1296   free (reg_equiv_address);
1297   free (reg_max_ref_width);
1298   free (reg_old_renumber);
1299   free (pseudo_previous_regs);
1300   free (pseudo_forbidden_regs);
1301
1302   CLEAR_HARD_REG_SET (used_spill_regs);
1303   for (i = 0; i < n_spills; i++)
1304     SET_HARD_REG_BIT (used_spill_regs, spill_regs[i]);
1305
1306   /* Free all the insn_chain structures at once.  */
1307   obstack_free (&reload_obstack, reload_startobj);
1308   unused_insn_chains = 0;
1309   fixup_abnormal_edges ();
1310
1311   /* Replacing pseudos with their memory equivalents might have
1312      created shared rtx.  Subsequent passes would get confused
1313      by this, so unshare everything here.  */
1314   unshare_all_rtl_again (first);
1315
1316 #ifdef STACK_BOUNDARY
1317   /* init_emit has set the alignment of the hard frame pointer
1318      to STACK_BOUNDARY.  It is very likely no longer valid if
1319      the hard frame pointer was used for register allocation.  */
1320   if (!frame_pointer_needed)
1321     REGNO_POINTER_ALIGN (HARD_FRAME_POINTER_REGNUM) = BITS_PER_UNIT;
1322 #endif
1323
1324   return failure;
1325 }
1326
1327 /* Yet another special case.  Unfortunately, reg-stack forces people to
1328    write incorrect clobbers in asm statements.  These clobbers must not
1329    cause the register to appear in bad_spill_regs, otherwise we'll call
1330    fatal_insn later.  We clear the corresponding regnos in the live
1331    register sets to avoid this.
1332    The whole thing is rather sick, I'm afraid.  */
1333
1334 static void
1335 maybe_fix_stack_asms (void)
1336 {
1337 #ifdef STACK_REGS
1338   const char *constraints[MAX_RECOG_OPERANDS];
1339   enum machine_mode operand_mode[MAX_RECOG_OPERANDS];
1340   struct insn_chain *chain;
1341
1342   for (chain = reload_insn_chain; chain != 0; chain = chain->next)
1343     {
1344       int i, noperands;
1345       HARD_REG_SET clobbered, allowed;
1346       rtx pat;
1347
1348       if (! INSN_P (chain->insn)
1349           || (noperands = asm_noperands (PATTERN (chain->insn))) < 0)
1350         continue;
1351       pat = PATTERN (chain->insn);
1352       if (GET_CODE (pat) != PARALLEL)
1353         continue;
1354
1355       CLEAR_HARD_REG_SET (clobbered);
1356       CLEAR_HARD_REG_SET (allowed);
1357
1358       /* First, make a mask of all stack regs that are clobbered.  */
1359       for (i = 0; i < XVECLEN (pat, 0); i++)
1360         {
1361           rtx t = XVECEXP (pat, 0, i);
1362           if (GET_CODE (t) == CLOBBER && STACK_REG_P (XEXP (t, 0)))
1363             SET_HARD_REG_BIT (clobbered, REGNO (XEXP (t, 0)));
1364         }
1365
1366       /* Get the operand values and constraints out of the insn.  */
1367       decode_asm_operands (pat, recog_data.operand, recog_data.operand_loc,
1368                            constraints, operand_mode);
1369
1370       /* For every operand, see what registers are allowed.  */
1371       for (i = 0; i < noperands; i++)
1372         {
1373           const char *p = constraints[i];
1374           /* For every alternative, we compute the class of registers allowed
1375              for reloading in CLS, and merge its contents into the reg set
1376              ALLOWED.  */
1377           int cls = (int) NO_REGS;
1378
1379           for (;;)
1380             {
1381               char c = *p;
1382
1383               if (c == '\0' || c == ',' || c == '#')
1384                 {
1385                   /* End of one alternative - mark the regs in the current
1386                      class, and reset the class.  */
1387                   IOR_HARD_REG_SET (allowed, reg_class_contents[cls]);
1388                   cls = NO_REGS;
1389                   p++;
1390                   if (c == '#')
1391                     do {
1392                       c = *p++;
1393                     } while (c != '\0' && c != ',');
1394                   if (c == '\0')
1395                     break;
1396                   continue;
1397                 }
1398
1399               switch (c)
1400                 {
1401                 case '=': case '+': case '*': case '%': case '?': case '!':
1402                 case '0': case '1': case '2': case '3': case '4': case 'm':
1403                 case '<': case '>': case 'V': case 'o': case '&': case 'E':
1404                 case 'F': case 's': case 'i': case 'n': case 'X': case 'I':
1405                 case 'J': case 'K': case 'L': case 'M': case 'N': case 'O':
1406                 case 'P':
1407                   break;
1408
1409                 case 'p':
1410                   cls = (int) reg_class_subunion[cls]
1411                       [(int) base_reg_class (VOIDmode, ADDRESS, SCRATCH)];
1412                   break;
1413
1414                 case 'g':
1415                 case 'r':
1416                   cls = (int) reg_class_subunion[cls][(int) GENERAL_REGS];
1417                   break;
1418
1419                 default:
1420                   if (EXTRA_ADDRESS_CONSTRAINT (c, p))
1421                     cls = (int) reg_class_subunion[cls]
1422                       [(int) base_reg_class (VOIDmode, ADDRESS, SCRATCH)];
1423                   else
1424                     cls = (int) reg_class_subunion[cls]
1425                       [(int) REG_CLASS_FROM_CONSTRAINT (c, p)];
1426                 }
1427               p += CONSTRAINT_LEN (c, p);
1428             }
1429         }
1430       /* Those of the registers which are clobbered, but allowed by the
1431          constraints, must be usable as reload registers.  So clear them
1432          out of the life information.  */
1433       AND_HARD_REG_SET (allowed, clobbered);
1434       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1435         if (TEST_HARD_REG_BIT (allowed, i))
1436           {
1437             CLEAR_REGNO_REG_SET (&chain->live_throughout, i);
1438             CLEAR_REGNO_REG_SET (&chain->dead_or_set, i);
1439           }
1440     }
1441
1442 #endif
1443 }
1444 \f
1445 /* Copy the global variables n_reloads and rld into the corresponding elts
1446    of CHAIN.  */
1447 static void
1448 copy_reloads (struct insn_chain *chain)
1449 {
1450   chain->n_reloads = n_reloads;
1451   chain->rld = obstack_alloc (&reload_obstack,
1452                               n_reloads * sizeof (struct reload));
1453   memcpy (chain->rld, rld, n_reloads * sizeof (struct reload));
1454   reload_insn_firstobj = obstack_alloc (&reload_obstack, 0);
1455 }
1456
1457 /* Walk the chain of insns, and determine for each whether it needs reloads
1458    and/or eliminations.  Build the corresponding insns_need_reload list, and
1459    set something_needs_elimination as appropriate.  */
1460 static void
1461 calculate_needs_all_insns (int global)
1462 {
1463   struct insn_chain **pprev_reload = &insns_need_reload;
1464   struct insn_chain *chain, *next = 0;
1465
1466   something_needs_elimination = 0;
1467
1468   reload_insn_firstobj = obstack_alloc (&reload_obstack, 0);
1469   for (chain = reload_insn_chain; chain != 0; chain = next)
1470     {
1471       rtx insn = chain->insn;
1472
1473       next = chain->next;
1474
1475       /* Clear out the shortcuts.  */
1476       chain->n_reloads = 0;
1477       chain->need_elim = 0;
1478       chain->need_reload = 0;
1479       chain->need_operand_change = 0;
1480
1481       /* If this is a label, a JUMP_INSN, or has REG_NOTES (which might
1482          include REG_LABEL), we need to see what effects this has on the
1483          known offsets at labels.  */
1484
1485       if (LABEL_P (insn) || JUMP_P (insn)
1486           || (INSN_P (insn) && REG_NOTES (insn) != 0))
1487         set_label_offsets (insn, insn, 0);
1488
1489       if (INSN_P (insn))
1490         {
1491           rtx old_body = PATTERN (insn);
1492           int old_code = INSN_CODE (insn);
1493           rtx old_notes = REG_NOTES (insn);
1494           int did_elimination = 0;
1495           int operands_changed = 0;
1496           rtx set = single_set (insn);
1497
1498           /* Skip insns that only set an equivalence.  */
1499           if (set && REG_P (SET_DEST (set))
1500               && reg_renumber[REGNO (SET_DEST (set))] < 0
1501               && (reg_equiv_constant[REGNO (SET_DEST (set))]
1502                   || (reg_equiv_invariant[REGNO (SET_DEST (set))]))
1503                       && reg_equiv_init[REGNO (SET_DEST (set))])
1504             continue;
1505
1506           /* If needed, eliminate any eliminable registers.  */
1507           if (num_eliminable || num_eliminable_invariants)
1508             did_elimination = eliminate_regs_in_insn (insn, 0);
1509
1510           /* Analyze the instruction.  */
1511           operands_changed = find_reloads (insn, 0, spill_indirect_levels,
1512                                            global, spill_reg_order);
1513
1514           /* If a no-op set needs more than one reload, this is likely
1515              to be something that needs input address reloads.  We
1516              can't get rid of this cleanly later, and it is of no use
1517              anyway, so discard it now.
1518              We only do this when expensive_optimizations is enabled,
1519              since this complements reload inheritance / output
1520              reload deletion, and it can make debugging harder.  */
1521           if (flag_expensive_optimizations && n_reloads > 1)
1522             {
1523               rtx set = single_set (insn);
1524               if (set
1525                   && SET_SRC (set) == SET_DEST (set)
1526                   && REG_P (SET_SRC (set))
1527                   && REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER)
1528                 {
1529                   delete_insn (insn);
1530                   /* Delete it from the reload chain.  */
1531                   if (chain->prev)
1532                     chain->prev->next = next;
1533                   else
1534                     reload_insn_chain = next;
1535                   if (next)
1536                     next->prev = chain->prev;
1537                   chain->next = unused_insn_chains;
1538                   unused_insn_chains = chain;
1539                   continue;
1540                 }
1541             }
1542           if (num_eliminable)
1543             update_eliminable_offsets ();
1544
1545           /* Remember for later shortcuts which insns had any reloads or
1546              register eliminations.  */
1547           chain->need_elim = did_elimination;
1548           chain->need_reload = n_reloads > 0;
1549           chain->need_operand_change = operands_changed;
1550
1551           /* Discard any register replacements done.  */
1552           if (did_elimination)
1553             {
1554               obstack_free (&reload_obstack, reload_insn_firstobj);
1555               PATTERN (insn) = old_body;
1556               INSN_CODE (insn) = old_code;
1557               REG_NOTES (insn) = old_notes;
1558               something_needs_elimination = 1;
1559             }
1560
1561           something_needs_operands_changed |= operands_changed;
1562
1563           if (n_reloads != 0)
1564             {
1565               copy_reloads (chain);
1566               *pprev_reload = chain;
1567               pprev_reload = &chain->next_need_reload;
1568             }
1569         }
1570     }
1571   *pprev_reload = 0;
1572 }
1573 \f
1574 /* Comparison function for qsort to decide which of two reloads
1575    should be handled first.  *P1 and *P2 are the reload numbers.  */
1576
1577 static int
1578 reload_reg_class_lower (const void *r1p, const void *r2p)
1579 {
1580   int r1 = *(const short *) r1p, r2 = *(const short *) r2p;
1581   int t;
1582
1583   /* Consider required reloads before optional ones.  */
1584   t = rld[r1].optional - rld[r2].optional;
1585   if (t != 0)
1586     return t;
1587
1588   /* Count all solitary classes before non-solitary ones.  */
1589   t = ((reg_class_size[(int) rld[r2].class] == 1)
1590        - (reg_class_size[(int) rld[r1].class] == 1));
1591   if (t != 0)
1592     return t;
1593
1594   /* Aside from solitaires, consider all multi-reg groups first.  */
1595   t = rld[r2].nregs - rld[r1].nregs;
1596   if (t != 0)
1597     return t;
1598
1599   /* Consider reloads in order of increasing reg-class number.  */
1600   t = (int) rld[r1].class - (int) rld[r2].class;
1601   if (t != 0)
1602     return t;
1603
1604   /* If reloads are equally urgent, sort by reload number,
1605      so that the results of qsort leave nothing to chance.  */
1606   return r1 - r2;
1607 }
1608 \f
1609 /* The cost of spilling each hard reg.  */
1610 static int spill_cost[FIRST_PSEUDO_REGISTER];
1611
1612 /* When spilling multiple hard registers, we use SPILL_COST for the first
1613    spilled hard reg and SPILL_ADD_COST for subsequent regs.  SPILL_ADD_COST
1614    only the first hard reg for a multi-reg pseudo.  */
1615 static int spill_add_cost[FIRST_PSEUDO_REGISTER];
1616
1617 /* Update the spill cost arrays, considering that pseudo REG is live.  */
1618
1619 static void
1620 count_pseudo (int reg)
1621 {
1622   int freq = REG_FREQ (reg);
1623   int r = reg_renumber[reg];
1624   int nregs;
1625
1626   if (REGNO_REG_SET_P (&pseudos_counted, reg)
1627       || REGNO_REG_SET_P (&spilled_pseudos, reg))
1628     return;
1629
1630   SET_REGNO_REG_SET (&pseudos_counted, reg);
1631
1632   gcc_assert (r >= 0);
1633
1634   spill_add_cost[r] += freq;
1635
1636   nregs = hard_regno_nregs[r][PSEUDO_REGNO_MODE (reg)];
1637   while (nregs-- > 0)
1638     spill_cost[r + nregs] += freq;
1639 }
1640
1641 /* Calculate the SPILL_COST and SPILL_ADD_COST arrays and determine the
1642    contents of BAD_SPILL_REGS for the insn described by CHAIN.  */
1643
1644 static void
1645 order_regs_for_reload (struct insn_chain *chain)
1646 {
1647   unsigned i;
1648   HARD_REG_SET used_by_pseudos;
1649   HARD_REG_SET used_by_pseudos2;
1650   reg_set_iterator rsi;
1651
1652   COPY_HARD_REG_SET (bad_spill_regs, fixed_reg_set);
1653
1654   memset (spill_cost, 0, sizeof spill_cost);
1655   memset (spill_add_cost, 0, sizeof spill_add_cost);
1656
1657   /* Count number of uses of each hard reg by pseudo regs allocated to it
1658      and then order them by decreasing use.  First exclude hard registers
1659      that are live in or across this insn.  */
1660
1661   REG_SET_TO_HARD_REG_SET (used_by_pseudos, &chain->live_throughout);
1662   REG_SET_TO_HARD_REG_SET (used_by_pseudos2, &chain->dead_or_set);
1663   IOR_HARD_REG_SET (bad_spill_regs, used_by_pseudos);
1664   IOR_HARD_REG_SET (bad_spill_regs, used_by_pseudos2);
1665
1666   /* Now find out which pseudos are allocated to it, and update
1667      hard_reg_n_uses.  */
1668   CLEAR_REG_SET (&pseudos_counted);
1669
1670   EXECUTE_IF_SET_IN_REG_SET
1671     (&chain->live_throughout, FIRST_PSEUDO_REGISTER, i, rsi)
1672     {
1673       count_pseudo (i);
1674     }
1675   EXECUTE_IF_SET_IN_REG_SET
1676     (&chain->dead_or_set, FIRST_PSEUDO_REGISTER, i, rsi)
1677     {
1678       count_pseudo (i);
1679     }
1680   CLEAR_REG_SET (&pseudos_counted);
1681 }
1682 \f
1683 /* Vector of reload-numbers showing the order in which the reloads should
1684    be processed.  */
1685 static short reload_order[MAX_RELOADS];
1686
1687 /* This is used to keep track of the spill regs used in one insn.  */
1688 static HARD_REG_SET used_spill_regs_local;
1689
1690 /* We decided to spill hard register SPILLED, which has a size of
1691    SPILLED_NREGS.  Determine how pseudo REG, which is live during the insn,
1692    is affected.  We will add it to SPILLED_PSEUDOS if necessary, and we will
1693    update SPILL_COST/SPILL_ADD_COST.  */
1694
1695 static void
1696 count_spilled_pseudo (int spilled, int spilled_nregs, int reg)
1697 {
1698   int r = reg_renumber[reg];
1699   int nregs = hard_regno_nregs[r][PSEUDO_REGNO_MODE (reg)];
1700
1701   if (REGNO_REG_SET_P (&spilled_pseudos, reg)
1702       || spilled + spilled_nregs <= r || r + nregs <= spilled)
1703     return;
1704
1705   SET_REGNO_REG_SET (&spilled_pseudos, reg);
1706
1707   spill_add_cost[r] -= REG_FREQ (reg);
1708   while (nregs-- > 0)
1709     spill_cost[r + nregs] -= REG_FREQ (reg);
1710 }
1711
1712 /* Find reload register to use for reload number ORDER.  */
1713
1714 static int
1715 find_reg (struct insn_chain *chain, int order)
1716 {
1717   int rnum = reload_order[order];
1718   struct reload *rl = rld + rnum;
1719   int best_cost = INT_MAX;
1720   int best_reg = -1;
1721   unsigned int i, j;
1722   int k;
1723   HARD_REG_SET not_usable;
1724   HARD_REG_SET used_by_other_reload;
1725   reg_set_iterator rsi;
1726
1727   COPY_HARD_REG_SET (not_usable, bad_spill_regs);
1728   IOR_HARD_REG_SET (not_usable, bad_spill_regs_global);
1729   IOR_COMPL_HARD_REG_SET (not_usable, reg_class_contents[rl->class]);
1730
1731   CLEAR_HARD_REG_SET (used_by_other_reload);
1732   for (k = 0; k < order; k++)
1733     {
1734       int other = reload_order[k];
1735
1736       if (rld[other].regno >= 0 && reloads_conflict (other, rnum))
1737         for (j = 0; j < rld[other].nregs; j++)
1738           SET_HARD_REG_BIT (used_by_other_reload, rld[other].regno + j);
1739     }
1740
1741   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1742     {
1743       unsigned int regno = i;
1744
1745       if (! TEST_HARD_REG_BIT (not_usable, regno)
1746           && ! TEST_HARD_REG_BIT (used_by_other_reload, regno)
1747           && HARD_REGNO_MODE_OK (regno, rl->mode))
1748         {
1749           int this_cost = spill_cost[regno];
1750           int ok = 1;
1751           unsigned int this_nregs = hard_regno_nregs[regno][rl->mode];
1752
1753           for (j = 1; j < this_nregs; j++)
1754             {
1755               this_cost += spill_add_cost[regno + j];
1756               if ((TEST_HARD_REG_BIT (not_usable, regno + j))
1757                   || TEST_HARD_REG_BIT (used_by_other_reload, regno + j))
1758                 ok = 0;
1759             }
1760           if (! ok)
1761             continue;
1762           if (rl->in && REG_P (rl->in) && REGNO (rl->in) == regno)
1763             this_cost--;
1764           if (rl->out && REG_P (rl->out) && REGNO (rl->out) == regno)
1765             this_cost--;
1766           if (this_cost < best_cost
1767               /* Among registers with equal cost, prefer caller-saved ones, or
1768                  use REG_ALLOC_ORDER if it is defined.  */
1769               || (this_cost == best_cost
1770 #ifdef REG_ALLOC_ORDER
1771                   && (inv_reg_alloc_order[regno]
1772                       < inv_reg_alloc_order[best_reg])
1773 #else
1774                   && call_used_regs[regno]
1775                   && ! call_used_regs[best_reg]
1776 #endif
1777                   ))
1778             {
1779               best_reg = regno;
1780               best_cost = this_cost;
1781             }
1782         }
1783     }
1784   if (best_reg == -1)
1785     return 0;
1786
1787   if (dump_file)
1788     fprintf (dump_file, "Using reg %d for reload %d\n", best_reg, rnum);
1789
1790   rl->nregs = hard_regno_nregs[best_reg][rl->mode];
1791   rl->regno = best_reg;
1792
1793   EXECUTE_IF_SET_IN_REG_SET
1794     (&chain->live_throughout, FIRST_PSEUDO_REGISTER, j, rsi)
1795     {
1796       count_spilled_pseudo (best_reg, rl->nregs, j);
1797     }
1798
1799   EXECUTE_IF_SET_IN_REG_SET
1800     (&chain->dead_or_set, FIRST_PSEUDO_REGISTER, j, rsi)
1801     {
1802       count_spilled_pseudo (best_reg, rl->nregs, j);
1803     }
1804
1805   for (i = 0; i < rl->nregs; i++)
1806     {
1807       gcc_assert (spill_cost[best_reg + i] == 0);
1808       gcc_assert (spill_add_cost[best_reg + i] == 0);
1809       SET_HARD_REG_BIT (used_spill_regs_local, best_reg + i);
1810     }
1811   return 1;
1812 }
1813
1814 /* Find more reload regs to satisfy the remaining need of an insn, which
1815    is given by CHAIN.
1816    Do it by ascending class number, since otherwise a reg
1817    might be spilled for a big class and might fail to count
1818    for a smaller class even though it belongs to that class.  */
1819
1820 static void
1821 find_reload_regs (struct insn_chain *chain)
1822 {
1823   int i;
1824
1825   /* In order to be certain of getting the registers we need,
1826      we must sort the reloads into order of increasing register class.
1827      Then our grabbing of reload registers will parallel the process
1828      that provided the reload registers.  */
1829   for (i = 0; i < chain->n_reloads; i++)
1830     {
1831       /* Show whether this reload already has a hard reg.  */
1832       if (chain->rld[i].reg_rtx)
1833         {
1834           int regno = REGNO (chain->rld[i].reg_rtx);
1835           chain->rld[i].regno = regno;
1836           chain->rld[i].nregs
1837             = hard_regno_nregs[regno][GET_MODE (chain->rld[i].reg_rtx)];
1838         }
1839       else
1840         chain->rld[i].regno = -1;
1841       reload_order[i] = i;
1842     }
1843
1844   n_reloads = chain->n_reloads;
1845   memcpy (rld, chain->rld, n_reloads * sizeof (struct reload));
1846
1847   CLEAR_HARD_REG_SET (used_spill_regs_local);
1848
1849   if (dump_file)
1850     fprintf (dump_file, "Spilling for insn %d.\n", INSN_UID (chain->insn));
1851
1852   qsort (reload_order, n_reloads, sizeof (short), reload_reg_class_lower);
1853
1854   /* Compute the order of preference for hard registers to spill.  */
1855
1856   order_regs_for_reload (chain);
1857
1858   for (i = 0; i < n_reloads; i++)
1859     {
1860       int r = reload_order[i];
1861
1862       /* Ignore reloads that got marked inoperative.  */
1863       if ((rld[r].out != 0 || rld[r].in != 0 || rld[r].secondary_p)
1864           && ! rld[r].optional
1865           && rld[r].regno == -1)
1866         if (! find_reg (chain, i))
1867           {
1868             if (dump_file)
1869               fprintf (dump_file, "reload failure for reload %d\n", r);
1870             spill_failure (chain->insn, rld[r].class);
1871             failure = 1;
1872             return;
1873           }
1874     }
1875
1876   COPY_HARD_REG_SET (chain->used_spill_regs, used_spill_regs_local);
1877   IOR_HARD_REG_SET (used_spill_regs, used_spill_regs_local);
1878
1879   memcpy (chain->rld, rld, n_reloads * sizeof (struct reload));
1880 }
1881
1882 static void
1883 select_reload_regs (void)
1884 {
1885   struct insn_chain *chain;
1886
1887   /* Try to satisfy the needs for each insn.  */
1888   for (chain = insns_need_reload; chain != 0;
1889        chain = chain->next_need_reload)
1890     find_reload_regs (chain);
1891 }
1892 \f
1893 /* Delete all insns that were inserted by emit_caller_save_insns during
1894    this iteration.  */
1895 static void
1896 delete_caller_save_insns (void)
1897 {
1898   struct insn_chain *c = reload_insn_chain;
1899
1900   while (c != 0)
1901     {
1902       while (c != 0 && c->is_caller_save_insn)
1903         {
1904           struct insn_chain *next = c->next;
1905           rtx insn = c->insn;
1906
1907           if (c == reload_insn_chain)
1908             reload_insn_chain = next;
1909           delete_insn (insn);
1910
1911           if (next)
1912             next->prev = c->prev;
1913           if (c->prev)
1914             c->prev->next = next;
1915           c->next = unused_insn_chains;
1916           unused_insn_chains = c;
1917           c = next;
1918         }
1919       if (c != 0)
1920         c = c->next;
1921     }
1922 }
1923 \f
1924 /* Handle the failure to find a register to spill.
1925    INSN should be one of the insns which needed this particular spill reg.  */
1926
1927 static void
1928 spill_failure (rtx insn, enum reg_class class)
1929 {
1930   if (asm_noperands (PATTERN (insn)) >= 0)
1931     error_for_asm (insn, "can't find a register in class %qs while "
1932                    "reloading %<asm%>",
1933                    reg_class_names[class]);
1934   else
1935     {
1936       error ("unable to find a register to spill in class %qs",
1937              reg_class_names[class]);
1938
1939       if (dump_file)
1940         {
1941           fprintf (dump_file, "\nReloads for insn # %d\n", INSN_UID (insn));
1942           debug_reload_to_stream (dump_file);
1943         }
1944       fatal_insn ("this is the insn:", insn);
1945     }
1946 }
1947 \f
1948 /* Delete an unneeded INSN and any previous insns who sole purpose is loading
1949    data that is dead in INSN.  */
1950
1951 static void
1952 delete_dead_insn (rtx insn)
1953 {
1954   rtx prev = prev_real_insn (insn);
1955   rtx prev_dest;
1956
1957   /* If the previous insn sets a register that dies in our insn, delete it
1958      too.  */
1959   if (prev && GET_CODE (PATTERN (prev)) == SET
1960       && (prev_dest = SET_DEST (PATTERN (prev)), REG_P (prev_dest))
1961       && reg_mentioned_p (prev_dest, PATTERN (insn))
1962       && find_regno_note (insn, REG_DEAD, REGNO (prev_dest))
1963       && ! side_effects_p (SET_SRC (PATTERN (prev))))
1964     delete_dead_insn (prev);
1965
1966   SET_INSN_DELETED (insn);
1967 }
1968
1969 /* Modify the home of pseudo-reg I.
1970    The new home is present in reg_renumber[I].
1971
1972    FROM_REG may be the hard reg that the pseudo-reg is being spilled from;
1973    or it may be -1, meaning there is none or it is not relevant.
1974    This is used so that all pseudos spilled from a given hard reg
1975    can share one stack slot.  */
1976
1977 static void
1978 alter_reg (int i, int from_reg)
1979 {
1980   /* When outputting an inline function, this can happen
1981      for a reg that isn't actually used.  */
1982   if (regno_reg_rtx[i] == 0)
1983     return;
1984
1985   /* If the reg got changed to a MEM at rtl-generation time,
1986      ignore it.  */
1987   if (!REG_P (regno_reg_rtx[i]))
1988     return;
1989
1990   /* Modify the reg-rtx to contain the new hard reg
1991      number or else to contain its pseudo reg number.  */
1992   REGNO (regno_reg_rtx[i])
1993     = reg_renumber[i] >= 0 ? reg_renumber[i] : i;
1994
1995   /* If we have a pseudo that is needed but has no hard reg or equivalent,
1996      allocate a stack slot for it.  */
1997
1998   if (reg_renumber[i] < 0
1999       && REG_N_REFS (i) > 0
2000       && reg_equiv_constant[i] == 0
2001       && (reg_equiv_invariant[i] == 0 || reg_equiv_init[i] == 0)
2002       && reg_equiv_memory_loc[i] == 0)
2003     {
2004       rtx x;
2005       enum machine_mode mode = GET_MODE (regno_reg_rtx[i]);
2006       unsigned int inherent_size = PSEUDO_REGNO_BYTES (i);
2007       unsigned int inherent_align = GET_MODE_ALIGNMENT (mode);
2008       unsigned int total_size = MAX (inherent_size, reg_max_ref_width[i]);
2009       unsigned int min_align = reg_max_ref_width[i] * BITS_PER_UNIT;
2010       int adjust = 0;
2011
2012       /* Each pseudo reg has an inherent size which comes from its own mode,
2013          and a total size which provides room for paradoxical subregs
2014          which refer to the pseudo reg in wider modes.
2015
2016          We can use a slot already allocated if it provides both
2017          enough inherent space and enough total space.
2018          Otherwise, we allocate a new slot, making sure that it has no less
2019          inherent space, and no less total space, then the previous slot.  */
2020       if (from_reg == -1)
2021         {
2022           /* No known place to spill from => no slot to reuse.  */
2023           x = assign_stack_local (mode, total_size,
2024                                   min_align > inherent_align
2025                                   || total_size > inherent_size ? -1 : 0);
2026           if (BYTES_BIG_ENDIAN)
2027             /* Cancel the  big-endian correction done in assign_stack_local.
2028                Get the address of the beginning of the slot.
2029                This is so we can do a big-endian correction unconditionally
2030                below.  */
2031             adjust = inherent_size - total_size;
2032
2033           /* Nothing can alias this slot except this pseudo.  */
2034           set_mem_alias_set (x, new_alias_set ());
2035         }
2036
2037       /* Reuse a stack slot if possible.  */
2038       else if (spill_stack_slot[from_reg] != 0
2039                && spill_stack_slot_width[from_reg] >= total_size
2040                && (GET_MODE_SIZE (GET_MODE (spill_stack_slot[from_reg]))
2041                    >= inherent_size)
2042                && MEM_ALIGN (spill_stack_slot[from_reg]) >= min_align)
2043         x = spill_stack_slot[from_reg];
2044
2045       /* Allocate a bigger slot.  */
2046       else
2047         {
2048           /* Compute maximum size needed, both for inherent size
2049              and for total size.  */
2050           rtx stack_slot;
2051
2052           if (spill_stack_slot[from_reg])
2053             {
2054               if (GET_MODE_SIZE (GET_MODE (spill_stack_slot[from_reg]))
2055                   > inherent_size)
2056                 mode = GET_MODE (spill_stack_slot[from_reg]);
2057               if (spill_stack_slot_width[from_reg] > total_size)
2058                 total_size = spill_stack_slot_width[from_reg];
2059               if (MEM_ALIGN (spill_stack_slot[from_reg]) > min_align)
2060                 min_align = MEM_ALIGN (spill_stack_slot[from_reg]);
2061             }
2062
2063           /* Make a slot with that size.  */
2064           x = assign_stack_local (mode, total_size,
2065                                   min_align > inherent_align
2066                                   || total_size > inherent_size ? -1 : 0);
2067           stack_slot = x;
2068
2069           /* All pseudos mapped to this slot can alias each other.  */
2070           if (spill_stack_slot[from_reg])
2071             set_mem_alias_set (x, MEM_ALIAS_SET (spill_stack_slot[from_reg]));
2072           else
2073             set_mem_alias_set (x, new_alias_set ());
2074
2075           if (BYTES_BIG_ENDIAN)
2076             {
2077               /* Cancel the  big-endian correction done in assign_stack_local.
2078                  Get the address of the beginning of the slot.
2079                  This is so we can do a big-endian correction unconditionally
2080                  below.  */
2081               adjust = GET_MODE_SIZE (mode) - total_size;
2082               if (adjust)
2083                 stack_slot
2084                   = adjust_address_nv (x, mode_for_size (total_size
2085                                                          * BITS_PER_UNIT,
2086                                                          MODE_INT, 1),
2087                                        adjust);
2088             }
2089
2090           spill_stack_slot[from_reg] = stack_slot;
2091           spill_stack_slot_width[from_reg] = total_size;
2092         }
2093
2094       /* On a big endian machine, the "address" of the slot
2095          is the address of the low part that fits its inherent mode.  */
2096       if (BYTES_BIG_ENDIAN && inherent_size < total_size)
2097         adjust += (total_size - inherent_size);
2098
2099       /* If we have any adjustment to make, or if the stack slot is the
2100          wrong mode, make a new stack slot.  */
2101       x = adjust_address_nv (x, GET_MODE (regno_reg_rtx[i]), adjust);
2102
2103       /* If we have a decl for the original register, set it for the
2104          memory.  If this is a shared MEM, make a copy.  */
2105       if (REG_EXPR (regno_reg_rtx[i])
2106           && DECL_P (REG_EXPR (regno_reg_rtx[i])))
2107         {
2108           rtx decl = DECL_RTL_IF_SET (REG_EXPR (regno_reg_rtx[i]));
2109
2110           /* We can do this only for the DECLs home pseudo, not for
2111              any copies of it, since otherwise when the stack slot
2112              is reused, nonoverlapping_memrefs_p might think they
2113              cannot overlap.  */
2114           if (decl && REG_P (decl) && REGNO (decl) == (unsigned) i)
2115             {
2116               if (from_reg != -1 && spill_stack_slot[from_reg] == x)
2117                 x = copy_rtx (x);
2118
2119               set_mem_attrs_from_reg (x, regno_reg_rtx[i]);
2120             }
2121         }
2122
2123       /* Save the stack slot for later.  */
2124       reg_equiv_memory_loc[i] = x;
2125     }
2126 }
2127
2128 /* Mark the slots in regs_ever_live for the hard regs
2129    used by pseudo-reg number REGNO.  */
2130
2131 void
2132 mark_home_live (int regno)
2133 {
2134   int i, lim;
2135
2136   i = reg_renumber[regno];
2137   if (i < 0)
2138     return;
2139   lim = i + hard_regno_nregs[i][PSEUDO_REGNO_MODE (regno)];
2140   while (i < lim)
2141     regs_ever_live[i++] = 1;
2142 }
2143 \f
2144 /* This function handles the tracking of elimination offsets around branches.
2145
2146    X is a piece of RTL being scanned.
2147
2148    INSN is the insn that it came from, if any.
2149
2150    INITIAL_P is nonzero if we are to set the offset to be the initial
2151    offset and zero if we are setting the offset of the label to be the
2152    current offset.  */
2153
2154 static void
2155 set_label_offsets (rtx x, rtx insn, int initial_p)
2156 {
2157   enum rtx_code code = GET_CODE (x);
2158   rtx tem;
2159   unsigned int i;
2160   struct elim_table *p;
2161
2162   switch (code)
2163     {
2164     case LABEL_REF:
2165       if (LABEL_REF_NONLOCAL_P (x))
2166         return;
2167
2168       x = XEXP (x, 0);
2169
2170       /* ... fall through ...  */
2171
2172     case CODE_LABEL:
2173       /* If we know nothing about this label, set the desired offsets.  Note
2174          that this sets the offset at a label to be the offset before a label
2175          if we don't know anything about the label.  This is not correct for
2176          the label after a BARRIER, but is the best guess we can make.  If
2177          we guessed wrong, we will suppress an elimination that might have
2178          been possible had we been able to guess correctly.  */
2179
2180       if (! offsets_known_at[CODE_LABEL_NUMBER (x) - first_label_num])
2181         {
2182           for (i = 0; i < NUM_ELIMINABLE_REGS; i++)
2183             offsets_at[CODE_LABEL_NUMBER (x) - first_label_num][i]
2184               = (initial_p ? reg_eliminate[i].initial_offset
2185                  : reg_eliminate[i].offset);
2186           offsets_known_at[CODE_LABEL_NUMBER (x) - first_label_num] = 1;
2187         }
2188
2189       /* Otherwise, if this is the definition of a label and it is
2190          preceded by a BARRIER, set our offsets to the known offset of
2191          that label.  */
2192
2193       else if (x == insn
2194                && (tem = prev_nonnote_insn (insn)) != 0
2195                && BARRIER_P (tem))
2196         set_offsets_for_label (insn);
2197       else
2198         /* If neither of the above cases is true, compare each offset
2199            with those previously recorded and suppress any eliminations
2200            where the offsets disagree.  */
2201
2202         for (i = 0; i < NUM_ELIMINABLE_REGS; i++)
2203           if (offsets_at[CODE_LABEL_NUMBER (x) - first_label_num][i]
2204               != (initial_p ? reg_eliminate[i].initial_offset
2205                   : reg_eliminate[i].offset))
2206             reg_eliminate[i].can_eliminate = 0;
2207
2208       return;
2209
2210     case JUMP_INSN:
2211       set_label_offsets (PATTERN (insn), insn, initial_p);
2212
2213       /* ... fall through ...  */
2214
2215     case INSN:
2216     case CALL_INSN:
2217       /* Any labels mentioned in REG_LABEL notes can be branched to indirectly
2218          and hence must have all eliminations at their initial offsets.  */
2219       for (tem = REG_NOTES (x); tem; tem = XEXP (tem, 1))
2220         if (REG_NOTE_KIND (tem) == REG_LABEL)
2221           set_label_offsets (XEXP (tem, 0), insn, 1);
2222       return;
2223
2224     case PARALLEL:
2225     case ADDR_VEC:
2226     case ADDR_DIFF_VEC:
2227       /* Each of the labels in the parallel or address vector must be
2228          at their initial offsets.  We want the first field for PARALLEL
2229          and ADDR_VEC and the second field for ADDR_DIFF_VEC.  */
2230
2231       for (i = 0; i < (unsigned) XVECLEN (x, code == ADDR_DIFF_VEC); i++)
2232         set_label_offsets (XVECEXP (x, code == ADDR_DIFF_VEC, i),
2233                            insn, initial_p);
2234       return;
2235
2236     case SET:
2237       /* We only care about setting PC.  If the source is not RETURN,
2238          IF_THEN_ELSE, or a label, disable any eliminations not at
2239          their initial offsets.  Similarly if any arm of the IF_THEN_ELSE
2240          isn't one of those possibilities.  For branches to a label,
2241          call ourselves recursively.
2242
2243          Note that this can disable elimination unnecessarily when we have
2244          a non-local goto since it will look like a non-constant jump to
2245          someplace in the current function.  This isn't a significant
2246          problem since such jumps will normally be when all elimination
2247          pairs are back to their initial offsets.  */
2248
2249       if (SET_DEST (x) != pc_rtx)
2250         return;
2251
2252       switch (GET_CODE (SET_SRC (x)))
2253         {
2254         case PC:
2255         case RETURN:
2256           return;
2257
2258         case LABEL_REF:
2259           set_label_offsets (SET_SRC (x), insn, initial_p);
2260           return;
2261
2262         case IF_THEN_ELSE:
2263           tem = XEXP (SET_SRC (x), 1);
2264           if (GET_CODE (tem) == LABEL_REF)
2265             set_label_offsets (XEXP (tem, 0), insn, initial_p);
2266           else if (GET_CODE (tem) != PC && GET_CODE (tem) != RETURN)
2267             break;
2268
2269           tem = XEXP (SET_SRC (x), 2);
2270           if (GET_CODE (tem) == LABEL_REF)
2271             set_label_offsets (XEXP (tem, 0), insn, initial_p);
2272           else if (GET_CODE (tem) != PC && GET_CODE (tem) != RETURN)
2273             break;
2274           return;
2275
2276         default:
2277           break;
2278         }
2279
2280       /* If we reach here, all eliminations must be at their initial
2281          offset because we are doing a jump to a variable address.  */
2282       for (p = reg_eliminate; p < &reg_eliminate[NUM_ELIMINABLE_REGS]; p++)
2283         if (p->offset != p->initial_offset)
2284           p->can_eliminate = 0;
2285       break;
2286
2287     default:
2288       break;
2289     }
2290 }
2291 \f
2292 /* Scan X and replace any eliminable registers (such as fp) with a
2293    replacement (such as sp), plus an offset.
2294
2295    MEM_MODE is the mode of an enclosing MEM.  We need this to know how
2296    much to adjust a register for, e.g., PRE_DEC.  Also, if we are inside a
2297    MEM, we are allowed to replace a sum of a register and the constant zero
2298    with the register, which we cannot do outside a MEM.  In addition, we need
2299    to record the fact that a register is referenced outside a MEM.
2300
2301    If INSN is an insn, it is the insn containing X.  If we replace a REG
2302    in a SET_DEST with an equivalent MEM and INSN is nonzero, write a
2303    CLOBBER of the pseudo after INSN so find_equiv_regs will know that
2304    the REG is being modified.
2305
2306    Alternatively, INSN may be a note (an EXPR_LIST or INSN_LIST).
2307    That's used when we eliminate in expressions stored in notes.
2308    This means, do not set ref_outside_mem even if the reference
2309    is outside of MEMs.
2310
2311    REG_EQUIV_MEM and REG_EQUIV_ADDRESS contain address that have had
2312    replacements done assuming all offsets are at their initial values.  If
2313    they are not, or if REG_EQUIV_ADDRESS is nonzero for a pseudo we
2314    encounter, return the actual location so that find_reloads will do
2315    the proper thing.  */
2316
2317 static rtx
2318 eliminate_regs_1 (rtx x, enum machine_mode mem_mode, rtx insn,
2319                   bool may_use_invariant)
2320 {
2321   enum rtx_code code = GET_CODE (x);
2322   struct elim_table *ep;
2323   int regno;
2324   rtx new;
2325   int i, j;
2326   const char *fmt;
2327   int copied = 0;
2328
2329   if (! current_function_decl)
2330     return x;
2331
2332   switch (code)
2333     {
2334     case CONST_INT:
2335     case CONST_DOUBLE:
2336     case CONST_VECTOR:
2337     case CONST:
2338     case SYMBOL_REF:
2339     case CODE_LABEL:
2340     case PC:
2341     case CC0:
2342     case ASM_INPUT:
2343     case ADDR_VEC:
2344     case ADDR_DIFF_VEC:
2345     case RETURN:
2346       return x;
2347
2348     case REG:
2349       regno = REGNO (x);
2350
2351       /* First handle the case where we encounter a bare register that
2352          is eliminable.  Replace it with a PLUS.  */
2353       if (regno < FIRST_PSEUDO_REGISTER)
2354         {
2355           for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
2356                ep++)
2357             if (ep->from_rtx == x && ep->can_eliminate)
2358               return plus_constant (ep->to_rtx, ep->previous_offset);
2359
2360         }
2361       else if (reg_renumber && reg_renumber[regno] < 0
2362                && reg_equiv_invariant && reg_equiv_invariant[regno])
2363         {
2364           if (may_use_invariant)
2365             return eliminate_regs_1 (copy_rtx (reg_equiv_invariant[regno]),
2366                                      mem_mode, insn, true);
2367           /* There exists at least one use of REGNO that cannot be
2368              eliminated.  Prevent the defining insn from being deleted.  */
2369           reg_equiv_init[regno] = NULL_RTX;
2370           alter_reg (regno, -1);
2371         }
2372       return x;
2373
2374     /* You might think handling MINUS in a manner similar to PLUS is a
2375        good idea.  It is not.  It has been tried multiple times and every
2376        time the change has had to have been reverted.
2377
2378        Other parts of reload know a PLUS is special (gen_reload for example)
2379        and require special code to handle code a reloaded PLUS operand.
2380
2381        Also consider backends where the flags register is clobbered by a
2382        MINUS, but we can emit a PLUS that does not clobber flags (IA-32,
2383        lea instruction comes to mind).  If we try to reload a MINUS, we
2384        may kill the flags register that was holding a useful value.
2385
2386        So, please before trying to handle MINUS, consider reload as a
2387        whole instead of this little section as well as the backend issues.  */
2388     case PLUS:
2389       /* If this is the sum of an eliminable register and a constant, rework
2390          the sum.  */
2391       if (REG_P (XEXP (x, 0))
2392           && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER
2393           && CONSTANT_P (XEXP (x, 1)))
2394         {
2395           for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
2396                ep++)
2397             if (ep->from_rtx == XEXP (x, 0) && ep->can_eliminate)
2398               {
2399                 /* The only time we want to replace a PLUS with a REG (this
2400                    occurs when the constant operand of the PLUS is the negative
2401                    of the offset) is when we are inside a MEM.  We won't want
2402                    to do so at other times because that would change the
2403                    structure of the insn in a way that reload can't handle.
2404                    We special-case the commonest situation in
2405                    eliminate_regs_in_insn, so just replace a PLUS with a
2406                    PLUS here, unless inside a MEM.  */
2407                 if (mem_mode != 0 && GET_CODE (XEXP (x, 1)) == CONST_INT
2408                     && INTVAL (XEXP (x, 1)) == - ep->previous_offset)
2409                   return ep->to_rtx;
2410                 else
2411                   return gen_rtx_PLUS (Pmode, ep->to_rtx,
2412                                        plus_constant (XEXP (x, 1),
2413                                                       ep->previous_offset));
2414               }
2415
2416           /* If the register is not eliminable, we are done since the other
2417              operand is a constant.  */
2418           return x;
2419         }
2420
2421       /* If this is part of an address, we want to bring any constant to the
2422          outermost PLUS.  We will do this by doing register replacement in
2423          our operands and seeing if a constant shows up in one of them.
2424
2425          Note that there is no risk of modifying the structure of the insn,
2426          since we only get called for its operands, thus we are either
2427          modifying the address inside a MEM, or something like an address
2428          operand of a load-address insn.  */
2429
2430       {
2431         rtx new0 = eliminate_regs_1 (XEXP (x, 0), mem_mode, insn, true);
2432         rtx new1 = eliminate_regs_1 (XEXP (x, 1), mem_mode, insn, true);
2433
2434         if (reg_renumber && (new0 != XEXP (x, 0) || new1 != XEXP (x, 1)))
2435           {
2436             /* If one side is a PLUS and the other side is a pseudo that
2437                didn't get a hard register but has a reg_equiv_constant,
2438                we must replace the constant here since it may no longer
2439                be in the position of any operand.  */
2440             if (GET_CODE (new0) == PLUS && REG_P (new1)
2441                 && REGNO (new1) >= FIRST_PSEUDO_REGISTER
2442                 && reg_renumber[REGNO (new1)] < 0
2443                 && reg_equiv_constant != 0
2444                 && reg_equiv_constant[REGNO (new1)] != 0)
2445               new1 = reg_equiv_constant[REGNO (new1)];
2446             else if (GET_CODE (new1) == PLUS && REG_P (new0)
2447                      && REGNO (new0) >= FIRST_PSEUDO_REGISTER
2448                      && reg_renumber[REGNO (new0)] < 0
2449                      && reg_equiv_constant[REGNO (new0)] != 0)
2450               new0 = reg_equiv_constant[REGNO (new0)];
2451
2452             new = form_sum (new0, new1);
2453
2454             /* As above, if we are not inside a MEM we do not want to
2455                turn a PLUS into something else.  We might try to do so here
2456                for an addition of 0 if we aren't optimizing.  */
2457             if (! mem_mode && GET_CODE (new) != PLUS)
2458               return gen_rtx_PLUS (GET_MODE (x), new, const0_rtx);
2459             else
2460               return new;
2461           }
2462       }
2463       return x;
2464
2465     case MULT:
2466       /* If this is the product of an eliminable register and a
2467          constant, apply the distribute law and move the constant out
2468          so that we have (plus (mult ..) ..).  This is needed in order
2469          to keep load-address insns valid.   This case is pathological.
2470          We ignore the possibility of overflow here.  */
2471       if (REG_P (XEXP (x, 0))
2472           && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER
2473           && GET_CODE (XEXP (x, 1)) == CONST_INT)
2474         for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
2475              ep++)
2476           if (ep->from_rtx == XEXP (x, 0) && ep->can_eliminate)
2477             {
2478               if (! mem_mode
2479                   /* Refs inside notes don't count for this purpose.  */
2480                   && ! (insn != 0 && (GET_CODE (insn) == EXPR_LIST
2481                                       || GET_CODE (insn) == INSN_LIST)))
2482                 ep->ref_outside_mem = 1;
2483
2484               return
2485                 plus_constant (gen_rtx_MULT (Pmode, ep->to_rtx, XEXP (x, 1)),
2486                                ep->previous_offset * INTVAL (XEXP (x, 1)));
2487             }
2488
2489       /* ... fall through ...  */
2490
2491     case CALL:
2492     case COMPARE:
2493     /* See comments before PLUS about handling MINUS.  */
2494     case MINUS:
2495     case DIV:      case UDIV:
2496     case MOD:      case UMOD:
2497     case AND:      case IOR:      case XOR:
2498     case ROTATERT: case ROTATE:
2499     case ASHIFTRT: case LSHIFTRT: case ASHIFT:
2500     case NE:       case EQ:
2501     case GE:       case GT:       case GEU:    case GTU:
2502     case LE:       case LT:       case LEU:    case LTU:
2503       {
2504         rtx new0 = eliminate_regs_1 (XEXP (x, 0), mem_mode, insn, false);
2505         rtx new1 = XEXP (x, 1)
2506                    ? eliminate_regs_1 (XEXP (x, 1), mem_mode, insn, false) : 0;
2507
2508         if (new0 != XEXP (x, 0) || new1 != XEXP (x, 1))
2509           return gen_rtx_fmt_ee (code, GET_MODE (x), new0, new1);
2510       }
2511       return x;
2512
2513     case EXPR_LIST:
2514       /* If we have something in XEXP (x, 0), the usual case, eliminate it.  */
2515       if (XEXP (x, 0))
2516         {
2517           new = eliminate_regs_1 (XEXP (x, 0), mem_mode, insn, true);
2518           if (new != XEXP (x, 0))
2519             {
2520               /* If this is a REG_DEAD note, it is not valid anymore.
2521                  Using the eliminated version could result in creating a
2522                  REG_DEAD note for the stack or frame pointer.  */
2523               if (GET_MODE (x) == REG_DEAD)
2524                 return (XEXP (x, 1)
2525                         ? eliminate_regs_1 (XEXP (x, 1), mem_mode, insn, true)
2526                         : NULL_RTX);
2527
2528               x = gen_rtx_EXPR_LIST (REG_NOTE_KIND (x), new, XEXP (x, 1));
2529             }
2530         }
2531
2532       /* ... fall through ...  */
2533
2534     case INSN_LIST:
2535       /* Now do eliminations in the rest of the chain.  If this was
2536          an EXPR_LIST, this might result in allocating more memory than is
2537          strictly needed, but it simplifies the code.  */
2538       if (XEXP (x, 1))
2539         {
2540           new = eliminate_regs_1 (XEXP (x, 1), mem_mode, insn, true);
2541           if (new != XEXP (x, 1))
2542             return
2543               gen_rtx_fmt_ee (GET_CODE (x), GET_MODE (x), XEXP (x, 0), new);
2544         }
2545       return x;
2546
2547     case PRE_INC:
2548     case POST_INC:
2549     case PRE_DEC:
2550     case POST_DEC:
2551       /* We do not support elimination of a register that is modified.
2552          elimination_effects has already make sure that this does not
2553          happen.  */
2554       return x;
2555
2556     case PRE_MODIFY:
2557     case POST_MODIFY:
2558       /* We do not support elimination of a register that is modified.
2559          elimination_effects has already make sure that this does not
2560          happen.  The only remaining case we need to consider here is
2561          that the increment value may be an eliminable register.  */
2562       if (GET_CODE (XEXP (x, 1)) == PLUS
2563           && XEXP (XEXP (x, 1), 0) == XEXP (x, 0))
2564         {
2565           rtx new = eliminate_regs_1 (XEXP (XEXP (x, 1), 1), mem_mode,
2566                                       insn, true);
2567
2568           if (new != XEXP (XEXP (x, 1), 1))
2569             return gen_rtx_fmt_ee (code, GET_MODE (x), XEXP (x, 0),
2570                                    gen_rtx_PLUS (GET_MODE (x),
2571                                                  XEXP (x, 0), new));
2572         }
2573       return x;
2574
2575     case STRICT_LOW_PART:
2576     case NEG:          case NOT:
2577     case SIGN_EXTEND:  case ZERO_EXTEND:
2578     case TRUNCATE:     case FLOAT_EXTEND: case FLOAT_TRUNCATE:
2579     case FLOAT:        case FIX:
2580     case UNSIGNED_FIX: case UNSIGNED_FLOAT:
2581     case ABS:
2582     case SQRT:
2583     case FFS:
2584     case CLZ:
2585     case CTZ:
2586     case POPCOUNT:
2587     case PARITY:
2588     case BSWAP:
2589       new = eliminate_regs_1 (XEXP (x, 0), mem_mode, insn, false);
2590       if (new != XEXP (x, 0))
2591         return gen_rtx_fmt_e (code, GET_MODE (x), new);
2592       return x;
2593
2594     case SUBREG:
2595       /* Similar to above processing, but preserve SUBREG_BYTE.
2596          Convert (subreg (mem)) to (mem) if not paradoxical.
2597          Also, if we have a non-paradoxical (subreg (pseudo)) and the
2598          pseudo didn't get a hard reg, we must replace this with the
2599          eliminated version of the memory location because push_reload
2600          may do the replacement in certain circumstances.  */
2601       if (REG_P (SUBREG_REG (x))
2602           && (GET_MODE_SIZE (GET_MODE (x))
2603               <= GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
2604           && reg_equiv_memory_loc != 0
2605           && reg_equiv_memory_loc[REGNO (SUBREG_REG (x))] != 0)
2606         {
2607           new = SUBREG_REG (x);
2608         }
2609       else
2610         new = eliminate_regs_1 (SUBREG_REG (x), mem_mode, insn, false);
2611
2612       if (new != SUBREG_REG (x))
2613         {
2614           int x_size = GET_MODE_SIZE (GET_MODE (x));
2615           int new_size = GET_MODE_SIZE (GET_MODE (new));
2616
2617           if (MEM_P (new)
2618               && ((x_size < new_size
2619 #ifdef WORD_REGISTER_OPERATIONS
2620                    /* On these machines, combine can create rtl of the form
2621                       (set (subreg:m1 (reg:m2 R) 0) ...)
2622                       where m1 < m2, and expects something interesting to
2623                       happen to the entire word.  Moreover, it will use the
2624                       (reg:m2 R) later, expecting all bits to be preserved.
2625                       So if the number of words is the same, preserve the
2626                       subreg so that push_reload can see it.  */
2627                    && ! ((x_size - 1) / UNITS_PER_WORD
2628                          == (new_size -1 ) / UNITS_PER_WORD)
2629 #endif
2630                    )
2631                   || x_size == new_size)
2632               )
2633             return adjust_address_nv (new, GET_MODE (x), SUBREG_BYTE (x));
2634           else
2635             return gen_rtx_SUBREG (GET_MODE (x), new, SUBREG_BYTE (x));
2636         }
2637
2638       return x;
2639
2640     case MEM:
2641       /* Our only special processing is to pass the mode of the MEM to our
2642          recursive call and copy the flags.  While we are here, handle this
2643          case more efficiently.  */
2644       return
2645         replace_equiv_address_nv (x,
2646                                   eliminate_regs_1 (XEXP (x, 0), GET_MODE (x),
2647                                                     insn, true));
2648
2649     case USE:
2650       /* Handle insn_list USE that a call to a pure function may generate.  */
2651       new = eliminate_regs_1 (XEXP (x, 0), 0, insn, false);
2652       if (new != XEXP (x, 0))
2653         return gen_rtx_USE (GET_MODE (x), new);
2654       return x;
2655
2656     case CLOBBER:
2657     case ASM_OPERANDS:
2658     case SET:
2659       gcc_unreachable ();
2660
2661     default:
2662       break;
2663     }
2664
2665   /* Process each of our operands recursively.  If any have changed, make a
2666      copy of the rtx.  */
2667   fmt = GET_RTX_FORMAT (code);
2668   for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
2669     {
2670       if (*fmt == 'e')
2671         {
2672           new = eliminate_regs_1 (XEXP (x, i), mem_mode, insn, false);
2673           if (new != XEXP (x, i) && ! copied)
2674             {
2675               x = shallow_copy_rtx (x);
2676               copied = 1;
2677             }
2678           XEXP (x, i) = new;
2679         }
2680       else if (*fmt == 'E')
2681         {
2682           int copied_vec = 0;
2683           for (j = 0; j < XVECLEN (x, i); j++)
2684             {
2685               new = eliminate_regs_1 (XVECEXP (x, i, j), mem_mode, insn, false);
2686               if (new != XVECEXP (x, i, j) && ! copied_vec)
2687                 {
2688                   rtvec new_v = gen_rtvec_v (XVECLEN (x, i),
2689                                              XVEC (x, i)->elem);
2690                   if (! copied)
2691                     {
2692                       x = shallow_copy_rtx (x);
2693                       copied = 1;
2694                     }
2695                   XVEC (x, i) = new_v;
2696                   copied_vec = 1;
2697                 }
2698               XVECEXP (x, i, j) = new;
2699             }
2700         }
2701     }
2702
2703   return x;
2704 }
2705
2706 rtx
2707 eliminate_regs (rtx x, enum machine_mode mem_mode, rtx insn)
2708 {
2709   return eliminate_regs_1 (x, mem_mode, insn, false);
2710 }
2711
2712 /* Scan rtx X for modifications of elimination target registers.  Update
2713    the table of eliminables to reflect the changed state.  MEM_MODE is
2714    the mode of an enclosing MEM rtx, or VOIDmode if not within a MEM.  */
2715
2716 static void
2717 elimination_effects (rtx x, enum machine_mode mem_mode)
2718 {
2719   enum rtx_code code = GET_CODE (x);
2720   struct elim_table *ep;
2721   int regno;
2722   int i, j;
2723   const char *fmt;
2724
2725   switch (code)
2726     {
2727     case CONST_INT:
2728     case CONST_DOUBLE:
2729     case CONST_VECTOR:
2730     case CONST:
2731     case SYMBOL_REF:
2732     case CODE_LABEL:
2733     case PC:
2734     case CC0:
2735     case ASM_INPUT:
2736     case ADDR_VEC:
2737     case ADDR_DIFF_VEC:
2738     case RETURN:
2739       return;
2740
2741     case REG:
2742       regno = REGNO (x);
2743
2744       /* First handle the case where we encounter a bare register that
2745          is eliminable.  Replace it with a PLUS.  */
2746       if (regno < FIRST_PSEUDO_REGISTER)
2747         {
2748           for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
2749                ep++)
2750             if (ep->from_rtx == x && ep->can_eliminate)
2751               {
2752                 if (! mem_mode)
2753                   ep->ref_outside_mem = 1;
2754                 return;
2755               }
2756
2757         }
2758       else if (reg_renumber[regno] < 0 && reg_equiv_constant
2759                && reg_equiv_constant[regno]
2760                && ! function_invariant_p (reg_equiv_constant[regno]))
2761         elimination_effects (reg_equiv_constant[regno], mem_mode);
2762       return;
2763
2764     case PRE_INC:
2765     case POST_INC:
2766     case PRE_DEC:
2767     case POST_DEC:
2768     case POST_MODIFY:
2769     case PRE_MODIFY:
2770       /* If we modify the source of an elimination rule, disable it.  */
2771       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
2772         if (ep->from_rtx == XEXP (x, 0))
2773           ep->can_eliminate = 0;
2774
2775       /* If we modify the target of an elimination rule by adding a constant,
2776          update its offset.  If we modify the target in any other way, we'll
2777          have to disable the rule as well.  */
2778       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
2779         if (ep->to_rtx == XEXP (x, 0))
2780           {
2781             int size = GET_MODE_SIZE (mem_mode);
2782
2783             /* If more bytes than MEM_MODE are pushed, account for them.  */
2784 #ifdef PUSH_ROUNDING
2785             if (ep->to_rtx == stack_pointer_rtx)
2786               size = PUSH_ROUNDING (size);
2787 #endif
2788             if (code == PRE_DEC || code == POST_DEC)
2789               ep->offset += size;
2790             else if (code == PRE_INC || code == POST_INC)
2791               ep->offset -= size;
2792             else if (code == PRE_MODIFY || code == POST_MODIFY)
2793               {
2794                 if (GET_CODE (XEXP (x, 1)) == PLUS
2795                     && XEXP (x, 0) == XEXP (XEXP (x, 1), 0)
2796                     && CONST_INT_P (XEXP (XEXP (x, 1), 1)))
2797                   ep->offset -= INTVAL (XEXP (XEXP (x, 1), 1));
2798                 else
2799                   ep->can_eliminate = 0;
2800               }
2801           }
2802
2803       /* These two aren't unary operators.  */
2804       if (code == POST_MODIFY || code == PRE_MODIFY)
2805         break;
2806
2807       /* Fall through to generic unary operation case.  */
2808     case STRICT_LOW_PART:
2809     case NEG:          case NOT:
2810     case SIGN_EXTEND:  case ZERO_EXTEND:
2811     case TRUNCATE:     case FLOAT_EXTEND: case FLOAT_TRUNCATE:
2812     case FLOAT:        case FIX:
2813     case UNSIGNED_FIX: case UNSIGNED_FLOAT:
2814     case ABS:
2815     case SQRT:
2816     case FFS:
2817     case CLZ:
2818     case CTZ:
2819     case POPCOUNT:
2820     case PARITY:
2821     case BSWAP:
2822       elimination_effects (XEXP (x, 0), mem_mode);
2823       return;
2824
2825     case SUBREG:
2826       if (REG_P (SUBREG_REG (x))
2827           && (GET_MODE_SIZE (GET_MODE (x))
2828               <= GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
2829           && reg_equiv_memory_loc != 0
2830           && reg_equiv_memory_loc[REGNO (SUBREG_REG (x))] != 0)
2831         return;
2832
2833       elimination_effects (SUBREG_REG (x), mem_mode);
2834       return;
2835
2836     case USE:
2837       /* If using a register that is the source of an eliminate we still
2838          think can be performed, note it cannot be performed since we don't
2839          know how this register is used.  */
2840       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
2841         if (ep->from_rtx == XEXP (x, 0))
2842           ep->can_eliminate = 0;
2843
2844       elimination_effects (XEXP (x, 0), mem_mode);
2845       return;
2846
2847     case CLOBBER:
2848       /* If clobbering a register that is the replacement register for an
2849          elimination we still think can be performed, note that it cannot
2850          be performed.  Otherwise, we need not be concerned about it.  */
2851       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
2852         if (ep->to_rtx == XEXP (x, 0))
2853           ep->can_eliminate = 0;
2854
2855       elimination_effects (XEXP (x, 0), mem_mode);
2856       return;
2857
2858     case SET:
2859       /* Check for setting a register that we know about.  */
2860       if (REG_P (SET_DEST (x)))
2861         {
2862           /* See if this is setting the replacement register for an
2863              elimination.
2864
2865              If DEST is the hard frame pointer, we do nothing because we
2866              assume that all assignments to the frame pointer are for
2867              non-local gotos and are being done at a time when they are valid
2868              and do not disturb anything else.  Some machines want to
2869              eliminate a fake argument pointer (or even a fake frame pointer)
2870              with either the real frame or the stack pointer.  Assignments to
2871              the hard frame pointer must not prevent this elimination.  */
2872
2873           for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
2874                ep++)
2875             if (ep->to_rtx == SET_DEST (x)
2876                 && SET_DEST (x) != hard_frame_pointer_rtx)
2877               {
2878                 /* If it is being incremented, adjust the offset.  Otherwise,
2879                    this elimination can't be done.  */
2880                 rtx src = SET_SRC (x);
2881
2882                 if (GET_CODE (src) == PLUS
2883                     && XEXP (src, 0) == SET_DEST (x)
2884                     && GET_CODE (XEXP (src, 1)) == CONST_INT)
2885                   ep->offset -= INTVAL (XEXP (src, 1));
2886                 else
2887                   ep->can_eliminate = 0;
2888               }
2889         }
2890
2891       elimination_effects (SET_DEST (x), 0);
2892       elimination_effects (SET_SRC (x), 0);
2893       return;
2894
2895     case MEM:
2896       /* Our only special processing is to pass the mode of the MEM to our
2897          recursive call.  */
2898       elimination_effects (XEXP (x, 0), GET_MODE (x));
2899       return;
2900
2901     default:
2902       break;
2903     }
2904
2905   fmt = GET_RTX_FORMAT (code);
2906   for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
2907     {
2908       if (*fmt == 'e')
2909         elimination_effects (XEXP (x, i), mem_mode);
2910       else if (*fmt == 'E')
2911         for (j = 0; j < XVECLEN (x, i); j++)
2912           elimination_effects (XVECEXP (x, i, j), mem_mode);
2913     }
2914 }
2915
2916 /* Descend through rtx X and verify that no references to eliminable registers
2917    remain.  If any do remain, mark the involved register as not
2918    eliminable.  */
2919
2920 static void
2921 check_eliminable_occurrences (rtx x)
2922 {
2923   const char *fmt;
2924   int i;
2925   enum rtx_code code;
2926
2927   if (x == 0)
2928     return;
2929
2930   code = GET_CODE (x);
2931
2932   if (code == REG && REGNO (x) < FIRST_PSEUDO_REGISTER)
2933     {
2934       struct elim_table *ep;
2935
2936       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
2937         if (ep->from_rtx == x)
2938           ep->can_eliminate = 0;
2939       return;
2940     }
2941
2942   fmt = GET_RTX_FORMAT (code);
2943   for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
2944     {
2945       if (*fmt == 'e')
2946         check_eliminable_occurrences (XEXP (x, i));
2947       else if (*fmt == 'E')
2948         {
2949           int j;
2950           for (j = 0; j < XVECLEN (x, i); j++)
2951             check_eliminable_occurrences (XVECEXP (x, i, j));
2952         }
2953     }
2954 }
2955 \f
2956 /* Scan INSN and eliminate all eliminable registers in it.
2957
2958    If REPLACE is nonzero, do the replacement destructively.  Also
2959    delete the insn as dead it if it is setting an eliminable register.
2960
2961    If REPLACE is zero, do all our allocations in reload_obstack.
2962
2963    If no eliminations were done and this insn doesn't require any elimination
2964    processing (these are not identical conditions: it might be updating sp,
2965    but not referencing fp; this needs to be seen during reload_as_needed so
2966    that the offset between fp and sp can be taken into consideration), zero
2967    is returned.  Otherwise, 1 is returned.  */
2968
2969 static int
2970 eliminate_regs_in_insn (rtx insn, int replace)
2971 {
2972   int icode = recog_memoized (insn);
2973   rtx old_body = PATTERN (insn);
2974   int insn_is_asm = asm_noperands (old_body) >= 0;
2975   rtx old_set = single_set (insn);
2976   rtx new_body;
2977   int val = 0;
2978   int i;
2979   rtx substed_operand[MAX_RECOG_OPERANDS];
2980   rtx orig_operand[MAX_RECOG_OPERANDS];
2981   struct elim_table *ep;
2982   rtx plus_src, plus_cst_src;
2983
2984   if (! insn_is_asm && icode < 0)
2985     {
2986       gcc_assert (GET_CODE (PATTERN (insn)) == USE
2987                   || GET_CODE (PATTERN (insn)) == CLOBBER
2988                   || GET_CODE (PATTERN (insn)) == ADDR_VEC
2989                   || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC
2990                   || GET_CODE (PATTERN (insn)) == ASM_INPUT);
2991       return 0;
2992     }
2993
2994   if (old_set != 0 && REG_P (SET_DEST (old_set))
2995       && REGNO (SET_DEST (old_set)) < FIRST_PSEUDO_REGISTER)
2996     {
2997       /* Check for setting an eliminable register.  */
2998       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
2999         if (ep->from_rtx == SET_DEST (old_set) && ep->can_eliminate)
3000           {
3001 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
3002             /* If this is setting the frame pointer register to the
3003                hardware frame pointer register and this is an elimination
3004                that will be done (tested above), this insn is really
3005                adjusting the frame pointer downward to compensate for
3006                the adjustment done before a nonlocal goto.  */
3007             if (ep->from == FRAME_POINTER_REGNUM
3008                 && ep->to == HARD_FRAME_POINTER_REGNUM)
3009               {
3010                 rtx base = SET_SRC (old_set);
3011                 rtx base_insn = insn;
3012                 HOST_WIDE_INT offset = 0;
3013
3014                 while (base != ep->to_rtx)
3015                   {
3016                     rtx prev_insn, prev_set;
3017
3018                     if (GET_CODE (base) == PLUS
3019                         && GET_CODE (XEXP (base, 1)) == CONST_INT)
3020                       {
3021                         offset += INTVAL (XEXP (base, 1));
3022                         base = XEXP (base, 0);
3023                       }
3024                     else if ((prev_insn = prev_nonnote_insn (base_insn)) != 0
3025                              && (prev_set = single_set (prev_insn)) != 0
3026                              && rtx_equal_p (SET_DEST (prev_set), base))
3027                       {
3028                         base = SET_SRC (prev_set);
3029                         base_insn = prev_insn;
3030                       }
3031                     else
3032                       break;
3033                   }
3034
3035                 if (base == ep->to_rtx)
3036                   {
3037                     rtx src
3038                       = plus_constant (ep->to_rtx, offset - ep->offset);
3039
3040                     new_body = old_body;
3041                     if (! replace)
3042                       {
3043                         new_body = copy_insn (old_body);
3044                         if (REG_NOTES (insn))
3045                           REG_NOTES (insn) = copy_insn_1 (REG_NOTES (insn));
3046                       }
3047                     PATTERN (insn) = new_body;
3048                     old_set = single_set (insn);
3049
3050                     /* First see if this insn remains valid when we
3051                        make the change.  If not, keep the INSN_CODE
3052                        the same and let reload fit it up.  */
3053                     validate_change (insn, &SET_SRC (old_set), src, 1);
3054                     validate_change (insn, &SET_DEST (old_set),
3055                                      ep->to_rtx, 1);
3056                     if (! apply_change_group ())
3057                       {
3058                         SET_SRC (old_set) = src;
3059                         SET_DEST (old_set) = ep->to_rtx;
3060                       }
3061
3062                     val = 1;
3063                     goto done;
3064                   }
3065               }
3066 #endif
3067
3068             /* In this case this insn isn't serving a useful purpose.  We
3069                will delete it in reload_as_needed once we know that this
3070                elimination is, in fact, being done.
3071
3072                If REPLACE isn't set, we can't delete this insn, but needn't
3073                process it since it won't be used unless something changes.  */
3074             if (replace)
3075               {
3076                 delete_dead_insn (insn);
3077                 return 1;
3078               }
3079             val = 1;
3080             goto done;
3081           }
3082     }
3083
3084   /* We allow one special case which happens to work on all machines we
3085      currently support: a single set with the source or a REG_EQUAL
3086      note being a PLUS of an eliminable register and a constant.  */
3087   plus_src = plus_cst_src = 0;
3088   if (old_set && REG_P (SET_DEST (old_set)))
3089     {
3090       if (GET_CODE (SET_SRC (old_set)) == PLUS)
3091         plus_src = SET_SRC (old_set);
3092       /* First see if the source is of the form (plus (...) CST).  */
3093       if (plus_src
3094           && GET_CODE (XEXP (plus_src, 1)) == CONST_INT)
3095         plus_cst_src = plus_src;
3096       else if (REG_P (SET_SRC (old_set))
3097                || plus_src)
3098         {
3099           /* Otherwise, see if we have a REG_EQUAL note of the form
3100              (plus (...) CST).  */
3101           rtx links;
3102           for (links = REG_NOTES (insn); links; links = XEXP (links, 1))
3103             {
3104               if (REG_NOTE_KIND (links) == REG_EQUAL
3105                   && GET_CODE (XEXP (links, 0)) == PLUS
3106                   && GET_CODE (XEXP (XEXP (links, 0), 1)) == CONST_INT)
3107                 {
3108                   plus_cst_src = XEXP (links, 0);
3109                   break;
3110                 }
3111             }
3112         }
3113
3114       /* Check that the first operand of the PLUS is a hard reg or
3115          the lowpart subreg of one.  */
3116       if (plus_cst_src)
3117         {
3118           rtx reg = XEXP (plus_cst_src, 0);
3119           if (GET_CODE (reg) == SUBREG && subreg_lowpart_p (reg))
3120             reg = SUBREG_REG (reg);
3121
3122           if (!REG_P (reg) || REGNO (reg) >= FIRST_PSEUDO_REGISTER)
3123             plus_cst_src = 0;
3124         }
3125     }
3126   if (plus_cst_src)
3127     {
3128       rtx reg = XEXP (plus_cst_src, 0);
3129       HOST_WIDE_INT offset = INTVAL (XEXP (plus_cst_src, 1));
3130
3131       if (GET_CODE (reg) == SUBREG)
3132         reg = SUBREG_REG (reg);
3133
3134       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
3135         if (ep->from_rtx == reg && ep->can_eliminate)
3136           {
3137             rtx to_rtx = ep->to_rtx;
3138             offset += ep->offset;
3139             offset = trunc_int_for_mode (offset, GET_MODE (reg));
3140
3141             if (GET_CODE (XEXP (plus_cst_src, 0)) == SUBREG)
3142               to_rtx = gen_lowpart (GET_MODE (XEXP (plus_cst_src, 0)),
3143                                     to_rtx);
3144             /* If we have a nonzero offset, and the source is already
3145                a simple REG, the following transformation would
3146                increase the cost of the insn by replacing a simple REG
3147                with (plus (reg sp) CST).  So try only when we already
3148                had a PLUS before.  */
3149             if (offset == 0 || plus_src)
3150               {
3151                 rtx new_src = plus_constant (to_rtx, offset);
3152
3153                 new_body = old_body;
3154                 if (! replace)
3155                   {
3156                     new_body = copy_insn (old_body);
3157                     if (REG_NOTES (insn))
3158                       REG_NOTES (insn) = copy_insn_1 (REG_NOTES (insn));
3159                   }
3160                 PATTERN (insn) = new_body;
3161                 old_set = single_set (insn);
3162
3163                 /* First see if this insn remains valid when we make the
3164                    change.  If not, try to replace the whole pattern with
3165                    a simple set (this may help if the original insn was a
3166                    PARALLEL that was only recognized as single_set due to 
3167                    REG_UNUSED notes).  If this isn't valid either, keep
3168                    the INSN_CODE the same and let reload fix it up.  */
3169                 if (!validate_change (insn, &SET_SRC (old_set), new_src, 0))
3170                   {
3171                     rtx new_pat = gen_rtx_SET (VOIDmode,
3172                                                SET_DEST (old_set), new_src);
3173
3174                     if (!validate_change (insn, &PATTERN (insn), new_pat, 0))
3175                       SET_SRC (old_set) = new_src;
3176                   }
3177               }
3178             else
3179               break;
3180
3181             val = 1;
3182             /* This can't have an effect on elimination offsets, so skip right
3183                to the end.  */
3184             goto done;
3185           }
3186     }
3187
3188   /* Determine the effects of this insn on elimination offsets.  */
3189   elimination_effects (old_body, 0);
3190
3191   /* Eliminate all eliminable registers occurring in operands that
3192      can be handled by reload.  */
3193   extract_insn (insn);
3194   for (i = 0; i < recog_data.n_operands; i++)
3195     {
3196       orig_operand[i] = recog_data.operand[i];
3197       substed_operand[i] = recog_data.operand[i];
3198
3199       /* For an asm statement, every operand is eliminable.  */
3200       if (insn_is_asm || insn_data[icode].operand[i].eliminable)
3201         {
3202           bool is_set_src, in_plus;
3203
3204           /* Check for setting a register that we know about.  */
3205           if (recog_data.operand_type[i] != OP_IN
3206               && REG_P (orig_operand[i]))
3207             {
3208               /* If we are assigning to a register that can be eliminated, it
3209                  must be as part of a PARALLEL, since the code above handles
3210                  single SETs.  We must indicate that we can no longer
3211                  eliminate this reg.  */
3212               for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
3213                    ep++)
3214                 if (ep->from_rtx == orig_operand[i])
3215                   ep->can_eliminate = 0;
3216             }
3217
3218           /* Companion to the above plus substitution, we can allow
3219              invariants as the source of a plain move.  */
3220           is_set_src = false;
3221           if (old_set && recog_data.operand_loc[i] == &SET_SRC (old_set))
3222             is_set_src = true;
3223           in_plus = false;
3224           if (plus_src
3225               && (recog_data.operand_loc[i] == &XEXP (plus_src, 0)
3226                   || recog_data.operand_loc[i] == &XEXP (plus_src, 1)))
3227             in_plus = true;
3228
3229           substed_operand[i]
3230             = eliminate_regs_1 (recog_data.operand[i], 0,
3231                                 replace ? insn : NULL_RTX,
3232                                 is_set_src || in_plus);
3233           if (substed_operand[i] != orig_operand[i])
3234             val = 1;
3235           /* Terminate the search in check_eliminable_occurrences at
3236              this point.  */
3237           *recog_data.operand_loc[i] = 0;
3238
3239         /* If an output operand changed from a REG to a MEM and INSN is an
3240            insn, write a CLOBBER insn.  */
3241           if (recog_data.operand_type[i] != OP_IN
3242               && REG_P (orig_operand[i])
3243               && MEM_P (substed_operand[i])
3244               && replace)
3245             emit_insn_after (gen_rtx_CLOBBER (VOIDmode, orig_operand[i]),
3246                              insn);
3247         }
3248     }
3249
3250   for (i = 0; i < recog_data.n_dups; i++)
3251     *recog_data.dup_loc[i]
3252       = *recog_data.operand_loc[(int) recog_data.dup_num[i]];
3253
3254   /* If any eliminable remain, they aren't eliminable anymore.  */
3255   check_eliminable_occurrences (old_body);
3256
3257   /* Substitute the operands; the new values are in the substed_operand
3258      array.  */
3259   for (i = 0; i < recog_data.n_operands; i++)
3260     *recog_data.operand_loc[i] = substed_operand[i];
3261   for (i = 0; i < recog_data.n_dups; i++)
3262     *recog_data.dup_loc[i] = substed_operand[(int) recog_data.dup_num[i]];
3263
3264   /* If we are replacing a body that was a (set X (plus Y Z)), try to
3265      re-recognize the insn.  We do this in case we had a simple addition
3266      but now can do this as a load-address.  This saves an insn in this
3267      common case.
3268      If re-recognition fails, the old insn code number will still be used,
3269      and some register operands may have changed into PLUS expressions.
3270      These will be handled by find_reloads by loading them into a register
3271      again.  */
3272
3273   if (val)
3274     {
3275       /* If we aren't replacing things permanently and we changed something,
3276          make another copy to ensure that all the RTL is new.  Otherwise
3277          things can go wrong if find_reload swaps commutative operands
3278          and one is inside RTL that has been copied while the other is not.  */
3279       new_body = old_body;
3280       if (! replace)
3281         {
3282           new_body = copy_insn (old_body);
3283           if (REG_NOTES (insn))
3284             REG_NOTES (insn) = copy_insn_1 (REG_NOTES (insn));
3285         }
3286       PATTERN (insn) = new_body;
3287
3288       /* If we had a move insn but now we don't, rerecognize it.  This will
3289          cause spurious re-recognition if the old move had a PARALLEL since
3290          the new one still will, but we can't call single_set without
3291          having put NEW_BODY into the insn and the re-recognition won't
3292          hurt in this rare case.  */
3293       /* ??? Why this huge if statement - why don't we just rerecognize the
3294          thing always?  */
3295       if (! insn_is_asm
3296           && old_set != 0
3297           && ((REG_P (SET_SRC (old_set))
3298                && (GET_CODE (new_body) != SET
3299                    || !REG_P (SET_SRC (new_body))))
3300               /* If this was a load from or store to memory, compare
3301                  the MEM in recog_data.operand to the one in the insn.
3302                  If they are not equal, then rerecognize the insn.  */
3303               || (old_set != 0
3304                   && ((MEM_P (SET_SRC (old_set))
3305                        && SET_SRC (old_set) != recog_data.operand[1])
3306                       || (MEM_P (SET_DEST (old_set))
3307                           && SET_DEST (old_set) != recog_data.operand[0])))
3308               /* If this was an add insn before, rerecognize.  */
3309               || GET_CODE (SET_SRC (old_set)) == PLUS))
3310         {
3311           int new_icode = recog (PATTERN (insn), insn, 0);
3312           if (new_icode >= 0)
3313             INSN_CODE (insn) = new_icode;
3314         }
3315     }
3316
3317   /* Restore the old body.  If there were any changes to it, we made a copy
3318      of it while the changes were still in place, so we'll correctly return
3319      a modified insn below.  */
3320   if (! replace)
3321     {
3322       /* Restore the old body.  */
3323       for (i = 0; i < recog_data.n_operands; i++)
3324         *recog_data.operand_loc[i] = orig_operand[i];
3325       for (i = 0; i < recog_data.n_dups; i++)
3326         *recog_data.dup_loc[i] = orig_operand[(int) recog_data.dup_num[i]];
3327     }
3328
3329   /* Update all elimination pairs to reflect the status after the current
3330      insn.  The changes we make were determined by the earlier call to
3331      elimination_effects.
3332
3333      We also detect cases where register elimination cannot be done,
3334      namely, if a register would be both changed and referenced outside a MEM
3335      in the resulting insn since such an insn is often undefined and, even if
3336      not, we cannot know what meaning will be given to it.  Note that it is
3337      valid to have a register used in an address in an insn that changes it
3338      (presumably with a pre- or post-increment or decrement).
3339
3340      If anything changes, return nonzero.  */
3341
3342   for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
3343     {
3344       if (ep->previous_offset != ep->offset && ep->ref_outside_mem)
3345         ep->can_eliminate = 0;
3346
3347       ep->ref_outside_mem = 0;
3348
3349       if (ep->previous_offset != ep->offset)
3350         val = 1;
3351     }
3352
3353  done:
3354   /* If we changed something, perform elimination in REG_NOTES.  This is
3355      needed even when REPLACE is zero because a REG_DEAD note might refer
3356      to a register that we eliminate and could cause a different number
3357      of spill registers to be needed in the final reload pass than in
3358      the pre-passes.  */
3359   if (val && REG_NOTES (insn) != 0)
3360     REG_NOTES (insn)
3361       = eliminate_regs_1 (REG_NOTES (insn), 0, REG_NOTES (insn), true);
3362
3363   return val;
3364 }
3365
3366 /* Loop through all elimination pairs.
3367    Recalculate the number not at initial offset.
3368
3369    Compute the maximum offset (minimum offset if the stack does not
3370    grow downward) for each elimination pair.  */
3371
3372 static void
3373 update_eliminable_offsets (void)
3374 {
3375   struct elim_table *ep;
3376
3377   num_not_at_initial_offset = 0;
3378   for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
3379     {
3380       ep->previous_offset = ep->offset;
3381       if (ep->can_eliminate && ep->offset != ep->initial_offset)
3382         num_not_at_initial_offset++;
3383     }
3384 }
3385
3386 /* Given X, a SET or CLOBBER of DEST, if DEST is the target of a register
3387    replacement we currently believe is valid, mark it as not eliminable if X
3388    modifies DEST in any way other than by adding a constant integer to it.
3389
3390    If DEST is the frame pointer, we do nothing because we assume that
3391    all assignments to the hard frame pointer are nonlocal gotos and are being
3392    done at a time when they are valid and do not disturb anything else.
3393    Some machines want to eliminate a fake argument pointer with either the
3394    frame or stack pointer.  Assignments to the hard frame pointer must not
3395    prevent this elimination.
3396
3397    Called via note_stores from reload before starting its passes to scan
3398    the insns of the function.  */
3399