OSDN Git Service

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