OSDN Git Service

* rtlanal.c (add_reg_note): New function.
[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 = XOBNEWVAR (&reload_obstack, char, 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 = XOBNEW (&reload_obstack, 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 = XNEWVEC (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 = XOBNEWVAR (&reload_obstack, char, 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 = XOBNEWVAR (&reload_obstack, char, 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 = XOBNEWVEC (&reload_obstack, struct reload, n_reloads);
1504   memcpy (chain->rld, rld, n_reloads * sizeof (struct reload));
1505   reload_insn_firstobj = XOBNEWVAR (&reload_obstack, char, 0);
1506 }
1507
1508 /* Walk the chain of insns, and determine for each whether it needs reloads
1509    and/or eliminations.  Build the corresponding insns_need_reload list, and
1510    set something_needs_elimination as appropriate.  */
1511 static void
1512 calculate_needs_all_insns (int global)
1513 {
1514   struct insn_chain **pprev_reload = &insns_need_reload;
1515   struct insn_chain *chain, *next = 0;
1516
1517   something_needs_elimination = 0;
1518
1519   reload_insn_firstobj = XOBNEWVAR (&reload_obstack, char, 0);
1520   for (chain = reload_insn_chain; chain != 0; chain = next)
1521     {
1522       rtx insn = chain->insn;
1523
1524       next = chain->next;
1525
1526       /* Clear out the shortcuts.  */
1527       chain->n_reloads = 0;
1528       chain->need_elim = 0;
1529       chain->need_reload = 0;
1530       chain->need_operand_change = 0;
1531
1532       /* If this is a label, a JUMP_INSN, or has REG_NOTES (which might
1533          include REG_LABEL_OPERAND and REG_LABEL_TARGET), we need to see
1534          what effects this has on the known offsets at labels.  */
1535
1536       if (LABEL_P (insn) || JUMP_P (insn)
1537           || (INSN_P (insn) && REG_NOTES (insn) != 0))
1538         set_label_offsets (insn, insn, 0);
1539
1540       if (INSN_P (insn))
1541         {
1542           rtx old_body = PATTERN (insn);
1543           int old_code = INSN_CODE (insn);
1544           rtx old_notes = REG_NOTES (insn);
1545           int did_elimination = 0;
1546           int operands_changed = 0;
1547           rtx set = single_set (insn);
1548
1549           /* Skip insns that only set an equivalence.  */
1550           if (set && REG_P (SET_DEST (set))
1551               && reg_renumber[REGNO (SET_DEST (set))] < 0
1552               && (reg_equiv_constant[REGNO (SET_DEST (set))]
1553                   || (reg_equiv_invariant[REGNO (SET_DEST (set))]))
1554                       && reg_equiv_init[REGNO (SET_DEST (set))])
1555             continue;
1556
1557           /* If needed, eliminate any eliminable registers.  */
1558           if (num_eliminable || num_eliminable_invariants)
1559             did_elimination = eliminate_regs_in_insn (insn, 0);
1560
1561           /* Analyze the instruction.  */
1562           operands_changed = find_reloads (insn, 0, spill_indirect_levels,
1563                                            global, spill_reg_order);
1564
1565           /* If a no-op set needs more than one reload, this is likely
1566              to be something that needs input address reloads.  We
1567              can't get rid of this cleanly later, and it is of no use
1568              anyway, so discard it now.
1569              We only do this when expensive_optimizations is enabled,
1570              since this complements reload inheritance / output
1571              reload deletion, and it can make debugging harder.  */
1572           if (flag_expensive_optimizations && n_reloads > 1)
1573             {
1574               rtx set = single_set (insn);
1575               if (set
1576                   && SET_SRC (set) == SET_DEST (set)
1577                   && REG_P (SET_SRC (set))
1578                   && REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER)
1579                 {
1580                   delete_insn (insn);
1581                   /* Delete it from the reload chain.  */
1582                   if (chain->prev)
1583                     chain->prev->next = next;
1584                   else
1585                     reload_insn_chain = next;
1586                   if (next)
1587                     next->prev = chain->prev;
1588                   chain->next = unused_insn_chains;
1589                   unused_insn_chains = chain;
1590                   continue;
1591                 }
1592             }
1593           if (num_eliminable)
1594             update_eliminable_offsets ();
1595
1596           /* Remember for later shortcuts which insns had any reloads or
1597              register eliminations.  */
1598           chain->need_elim = did_elimination;
1599           chain->need_reload = n_reloads > 0;
1600           chain->need_operand_change = operands_changed;
1601
1602           /* Discard any register replacements done.  */
1603           if (did_elimination)
1604             {
1605               obstack_free (&reload_obstack, reload_insn_firstobj);
1606               PATTERN (insn) = old_body;
1607               INSN_CODE (insn) = old_code;
1608               REG_NOTES (insn) = old_notes;
1609               something_needs_elimination = 1;
1610             }
1611
1612           something_needs_operands_changed |= operands_changed;
1613
1614           if (n_reloads != 0)
1615             {
1616               copy_reloads (chain);
1617               *pprev_reload = chain;
1618               pprev_reload = &chain->next_need_reload;
1619             }
1620         }
1621     }
1622   *pprev_reload = 0;
1623 }
1624 \f
1625 /* Comparison function for qsort to decide which of two reloads
1626    should be handled first.  *P1 and *P2 are the reload numbers.  */
1627
1628 static int
1629 reload_reg_class_lower (const void *r1p, const void *r2p)
1630 {
1631   int r1 = *(const short *) r1p, r2 = *(const short *) r2p;
1632   int t;
1633
1634   /* Consider required reloads before optional ones.  */
1635   t = rld[r1].optional - rld[r2].optional;
1636   if (t != 0)
1637     return t;
1638
1639   /* Count all solitary classes before non-solitary ones.  */
1640   t = ((reg_class_size[(int) rld[r2].class] == 1)
1641        - (reg_class_size[(int) rld[r1].class] == 1));
1642   if (t != 0)
1643     return t;
1644
1645   /* Aside from solitaires, consider all multi-reg groups first.  */
1646   t = rld[r2].nregs - rld[r1].nregs;
1647   if (t != 0)
1648     return t;
1649
1650   /* Consider reloads in order of increasing reg-class number.  */
1651   t = (int) rld[r1].class - (int) rld[r2].class;
1652   if (t != 0)
1653     return t;
1654
1655   /* If reloads are equally urgent, sort by reload number,
1656      so that the results of qsort leave nothing to chance.  */
1657   return r1 - r2;
1658 }
1659 \f
1660 /* The cost of spilling each hard reg.  */
1661 static int spill_cost[FIRST_PSEUDO_REGISTER];
1662
1663 /* When spilling multiple hard registers, we use SPILL_COST for the first
1664    spilled hard reg and SPILL_ADD_COST for subsequent regs.  SPILL_ADD_COST
1665    only the first hard reg for a multi-reg pseudo.  */
1666 static int spill_add_cost[FIRST_PSEUDO_REGISTER];
1667
1668 /* Update the spill cost arrays, considering that pseudo REG is live.  */
1669
1670 static void
1671 count_pseudo (int reg)
1672 {
1673   int freq = REG_FREQ (reg);
1674   int r = reg_renumber[reg];
1675   int nregs;
1676
1677   if (REGNO_REG_SET_P (&pseudos_counted, reg)
1678       || REGNO_REG_SET_P (&spilled_pseudos, reg))
1679     return;
1680
1681   SET_REGNO_REG_SET (&pseudos_counted, reg);
1682
1683   gcc_assert (r >= 0);
1684
1685   spill_add_cost[r] += freq;
1686
1687   nregs = hard_regno_nregs[r][PSEUDO_REGNO_MODE (reg)];
1688   while (nregs-- > 0)
1689     spill_cost[r + nregs] += freq;
1690 }
1691
1692 /* Calculate the SPILL_COST and SPILL_ADD_COST arrays and determine the
1693    contents of BAD_SPILL_REGS for the insn described by CHAIN.  */
1694
1695 static void
1696 order_regs_for_reload (struct insn_chain *chain)
1697 {
1698   unsigned i;
1699   HARD_REG_SET used_by_pseudos;
1700   HARD_REG_SET used_by_pseudos2;
1701   reg_set_iterator rsi;
1702
1703   COPY_HARD_REG_SET (bad_spill_regs, fixed_reg_set);
1704
1705   memset (spill_cost, 0, sizeof spill_cost);
1706   memset (spill_add_cost, 0, sizeof spill_add_cost);
1707
1708   /* Count number of uses of each hard reg by pseudo regs allocated to it
1709      and then order them by decreasing use.  First exclude hard registers
1710      that are live in or across this insn.  */
1711
1712   REG_SET_TO_HARD_REG_SET (used_by_pseudos, &chain->live_throughout);
1713   REG_SET_TO_HARD_REG_SET (used_by_pseudos2, &chain->dead_or_set);
1714   IOR_HARD_REG_SET (bad_spill_regs, used_by_pseudos);
1715   IOR_HARD_REG_SET (bad_spill_regs, used_by_pseudos2);
1716
1717   /* Now find out which pseudos are allocated to it, and update
1718      hard_reg_n_uses.  */
1719   CLEAR_REG_SET (&pseudos_counted);
1720
1721   EXECUTE_IF_SET_IN_REG_SET
1722     (&chain->live_throughout, FIRST_PSEUDO_REGISTER, i, rsi)
1723     {
1724       count_pseudo (i);
1725     }
1726   EXECUTE_IF_SET_IN_REG_SET
1727     (&chain->dead_or_set, FIRST_PSEUDO_REGISTER, i, rsi)
1728     {
1729       count_pseudo (i);
1730     }
1731   CLEAR_REG_SET (&pseudos_counted);
1732 }
1733 \f
1734 /* Vector of reload-numbers showing the order in which the reloads should
1735    be processed.  */
1736 static short reload_order[MAX_RELOADS];
1737
1738 /* This is used to keep track of the spill regs used in one insn.  */
1739 static HARD_REG_SET used_spill_regs_local;
1740
1741 /* We decided to spill hard register SPILLED, which has a size of
1742    SPILLED_NREGS.  Determine how pseudo REG, which is live during the insn,
1743    is affected.  We will add it to SPILLED_PSEUDOS if necessary, and we will
1744    update SPILL_COST/SPILL_ADD_COST.  */
1745
1746 static void
1747 count_spilled_pseudo (int spilled, int spilled_nregs, int reg)
1748 {
1749   int r = reg_renumber[reg];
1750   int nregs = hard_regno_nregs[r][PSEUDO_REGNO_MODE (reg)];
1751
1752   if (REGNO_REG_SET_P (&spilled_pseudos, reg)
1753       || spilled + spilled_nregs <= r || r + nregs <= spilled)
1754     return;
1755
1756   SET_REGNO_REG_SET (&spilled_pseudos, reg);
1757
1758   spill_add_cost[r] -= REG_FREQ (reg);
1759   while (nregs-- > 0)
1760     spill_cost[r + nregs] -= REG_FREQ (reg);
1761 }
1762
1763 /* Find reload register to use for reload number ORDER.  */
1764
1765 static int
1766 find_reg (struct insn_chain *chain, int order)
1767 {
1768   int rnum = reload_order[order];
1769   struct reload *rl = rld + rnum;
1770   int best_cost = INT_MAX;
1771   int best_reg = -1;
1772   unsigned int i, j;
1773   int k;
1774   HARD_REG_SET not_usable;
1775   HARD_REG_SET used_by_other_reload;
1776   reg_set_iterator rsi;
1777
1778   COPY_HARD_REG_SET (not_usable, bad_spill_regs);
1779   IOR_HARD_REG_SET (not_usable, bad_spill_regs_global);
1780   IOR_COMPL_HARD_REG_SET (not_usable, reg_class_contents[rl->class]);
1781
1782   CLEAR_HARD_REG_SET (used_by_other_reload);
1783   for (k = 0; k < order; k++)
1784     {
1785       int other = reload_order[k];
1786
1787       if (rld[other].regno >= 0 && reloads_conflict (other, rnum))
1788         for (j = 0; j < rld[other].nregs; j++)
1789           SET_HARD_REG_BIT (used_by_other_reload, rld[other].regno + j);
1790     }
1791
1792   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1793     {
1794       unsigned int regno = i;
1795
1796       if (! TEST_HARD_REG_BIT (not_usable, regno)
1797           && ! TEST_HARD_REG_BIT (used_by_other_reload, regno)
1798           && HARD_REGNO_MODE_OK (regno, rl->mode))
1799         {
1800           int this_cost = spill_cost[regno];
1801           int ok = 1;
1802           unsigned int this_nregs = hard_regno_nregs[regno][rl->mode];
1803
1804           for (j = 1; j < this_nregs; j++)
1805             {
1806               this_cost += spill_add_cost[regno + j];
1807               if ((TEST_HARD_REG_BIT (not_usable, regno + j))
1808                   || TEST_HARD_REG_BIT (used_by_other_reload, regno + j))
1809                 ok = 0;
1810             }
1811           if (! ok)
1812             continue;
1813           if (rl->in && REG_P (rl->in) && REGNO (rl->in) == regno)
1814             this_cost--;
1815           if (rl->out && REG_P (rl->out) && REGNO (rl->out) == regno)
1816             this_cost--;
1817           if (this_cost < best_cost
1818               /* Among registers with equal cost, prefer caller-saved ones, or
1819                  use REG_ALLOC_ORDER if it is defined.  */
1820               || (this_cost == best_cost
1821 #ifdef REG_ALLOC_ORDER
1822                   && (inv_reg_alloc_order[regno]
1823                       < inv_reg_alloc_order[best_reg])
1824 #else
1825                   && call_used_regs[regno]
1826                   && ! call_used_regs[best_reg]
1827 #endif
1828                   ))
1829             {
1830               best_reg = regno;
1831               best_cost = this_cost;
1832             }
1833         }
1834     }
1835   if (best_reg == -1)
1836     return 0;
1837
1838   if (dump_file)
1839     fprintf (dump_file, "Using reg %d for reload %d\n", best_reg, rnum);
1840
1841   rl->nregs = hard_regno_nregs[best_reg][rl->mode];
1842   rl->regno = best_reg;
1843
1844   EXECUTE_IF_SET_IN_REG_SET
1845     (&chain->live_throughout, FIRST_PSEUDO_REGISTER, j, rsi)
1846     {
1847       count_spilled_pseudo (best_reg, rl->nregs, j);
1848     }
1849
1850   EXECUTE_IF_SET_IN_REG_SET
1851     (&chain->dead_or_set, FIRST_PSEUDO_REGISTER, j, rsi)
1852     {
1853       count_spilled_pseudo (best_reg, rl->nregs, j);
1854     }
1855
1856   for (i = 0; i < rl->nregs; i++)
1857     {
1858       gcc_assert (spill_cost[best_reg + i] == 0);
1859       gcc_assert (spill_add_cost[best_reg + i] == 0);
1860       SET_HARD_REG_BIT (used_spill_regs_local, best_reg + i);
1861     }
1862   return 1;
1863 }
1864
1865 /* Find more reload regs to satisfy the remaining need of an insn, which
1866    is given by CHAIN.
1867    Do it by ascending class number, since otherwise a reg
1868    might be spilled for a big class and might fail to count
1869    for a smaller class even though it belongs to that class.  */
1870
1871 static void
1872 find_reload_regs (struct insn_chain *chain)
1873 {
1874   int i;
1875
1876   /* In order to be certain of getting the registers we need,
1877      we must sort the reloads into order of increasing register class.
1878      Then our grabbing of reload registers will parallel the process
1879      that provided the reload registers.  */
1880   for (i = 0; i < chain->n_reloads; i++)
1881     {
1882       /* Show whether this reload already has a hard reg.  */
1883       if (chain->rld[i].reg_rtx)
1884         {
1885           int regno = REGNO (chain->rld[i].reg_rtx);
1886           chain->rld[i].regno = regno;
1887           chain->rld[i].nregs
1888             = hard_regno_nregs[regno][GET_MODE (chain->rld[i].reg_rtx)];
1889         }
1890       else
1891         chain->rld[i].regno = -1;
1892       reload_order[i] = i;
1893     }
1894
1895   n_reloads = chain->n_reloads;
1896   memcpy (rld, chain->rld, n_reloads * sizeof (struct reload));
1897
1898   CLEAR_HARD_REG_SET (used_spill_regs_local);
1899
1900   if (dump_file)
1901     fprintf (dump_file, "Spilling for insn %d.\n", INSN_UID (chain->insn));
1902
1903   qsort (reload_order, n_reloads, sizeof (short), reload_reg_class_lower);
1904
1905   /* Compute the order of preference for hard registers to spill.  */
1906
1907   order_regs_for_reload (chain);
1908
1909   for (i = 0; i < n_reloads; i++)
1910     {
1911       int r = reload_order[i];
1912
1913       /* Ignore reloads that got marked inoperative.  */
1914       if ((rld[r].out != 0 || rld[r].in != 0 || rld[r].secondary_p)
1915           && ! rld[r].optional
1916           && rld[r].regno == -1)
1917         if (! find_reg (chain, i))
1918           {
1919             if (dump_file)
1920               fprintf (dump_file, "reload failure for reload %d\n", r);
1921             spill_failure (chain->insn, rld[r].class);
1922             failure = 1;
1923             return;
1924           }
1925     }
1926
1927   COPY_HARD_REG_SET (chain->used_spill_regs, used_spill_regs_local);
1928   IOR_HARD_REG_SET (used_spill_regs, used_spill_regs_local);
1929
1930   memcpy (chain->rld, rld, n_reloads * sizeof (struct reload));
1931 }
1932
1933 static void
1934 select_reload_regs (void)
1935 {
1936   struct insn_chain *chain;
1937
1938   /* Try to satisfy the needs for each insn.  */
1939   for (chain = insns_need_reload; chain != 0;
1940        chain = chain->next_need_reload)
1941     find_reload_regs (chain);
1942 }
1943 \f
1944 /* Delete all insns that were inserted by emit_caller_save_insns during
1945    this iteration.  */
1946 static void
1947 delete_caller_save_insns (void)
1948 {
1949   struct insn_chain *c = reload_insn_chain;
1950
1951   while (c != 0)
1952     {
1953       while (c != 0 && c->is_caller_save_insn)
1954         {
1955           struct insn_chain *next = c->next;
1956           rtx insn = c->insn;
1957
1958           if (c == reload_insn_chain)
1959             reload_insn_chain = next;
1960           delete_insn (insn);
1961
1962           if (next)
1963             next->prev = c->prev;
1964           if (c->prev)
1965             c->prev->next = next;
1966           c->next = unused_insn_chains;
1967           unused_insn_chains = c;
1968           c = next;
1969         }
1970       if (c != 0)
1971         c = c->next;
1972     }
1973 }
1974 \f
1975 /* Handle the failure to find a register to spill.
1976    INSN should be one of the insns which needed this particular spill reg.  */
1977
1978 static void
1979 spill_failure (rtx insn, enum reg_class class)
1980 {
1981   if (asm_noperands (PATTERN (insn)) >= 0)
1982     error_for_asm (insn, "can't find a register in class %qs while "
1983                    "reloading %<asm%>",
1984                    reg_class_names[class]);
1985   else
1986     {
1987       error ("unable to find a register to spill in class %qs",
1988              reg_class_names[class]);
1989
1990       if (dump_file)
1991         {
1992           fprintf (dump_file, "\nReloads for insn # %d\n", INSN_UID (insn));
1993           debug_reload_to_stream (dump_file);
1994         }
1995       fatal_insn ("this is the insn:", insn);
1996     }
1997 }
1998 \f
1999 /* Delete an unneeded INSN and any previous insns who sole purpose is loading
2000    data that is dead in INSN.  */
2001
2002 static void
2003 delete_dead_insn (rtx insn)
2004 {
2005   rtx prev = prev_real_insn (insn);
2006   rtx prev_dest;
2007
2008   /* If the previous insn sets a register that dies in our insn, delete it
2009      too.  */
2010   if (prev && GET_CODE (PATTERN (prev)) == SET
2011       && (prev_dest = SET_DEST (PATTERN (prev)), REG_P (prev_dest))
2012       && reg_mentioned_p (prev_dest, PATTERN (insn))
2013       && find_regno_note (insn, REG_DEAD, REGNO (prev_dest))
2014       && ! side_effects_p (SET_SRC (PATTERN (prev))))
2015     delete_dead_insn (prev);
2016
2017   SET_INSN_DELETED (insn);
2018 }
2019
2020 /* Modify the home of pseudo-reg I.
2021    The new home is present in reg_renumber[I].
2022
2023    FROM_REG may be the hard reg that the pseudo-reg is being spilled from;
2024    or it may be -1, meaning there is none or it is not relevant.
2025    This is used so that all pseudos spilled from a given hard reg
2026    can share one stack slot.  */
2027
2028 static void
2029 alter_reg (int i, int from_reg)
2030 {
2031   /* When outputting an inline function, this can happen
2032      for a reg that isn't actually used.  */
2033   if (regno_reg_rtx[i] == 0)
2034     return;
2035
2036   /* If the reg got changed to a MEM at rtl-generation time,
2037      ignore it.  */
2038   if (!REG_P (regno_reg_rtx[i]))
2039     return;
2040
2041   /* Modify the reg-rtx to contain the new hard reg
2042      number or else to contain its pseudo reg number.  */
2043   SET_REGNO (regno_reg_rtx[i],
2044              reg_renumber[i] >= 0 ? reg_renumber[i] : i);
2045
2046   /* If we have a pseudo that is needed but has no hard reg or equivalent,
2047      allocate a stack slot for it.  */
2048
2049   if (reg_renumber[i] < 0
2050       && REG_N_REFS (i) > 0
2051       && reg_equiv_constant[i] == 0
2052       && (reg_equiv_invariant[i] == 0 || reg_equiv_init[i] == 0)
2053       && reg_equiv_memory_loc[i] == 0)
2054     {
2055       rtx x;
2056       enum machine_mode mode = GET_MODE (regno_reg_rtx[i]);
2057       unsigned int inherent_size = PSEUDO_REGNO_BYTES (i);
2058       unsigned int inherent_align = GET_MODE_ALIGNMENT (mode);
2059       unsigned int total_size = MAX (inherent_size, reg_max_ref_width[i]);
2060       unsigned int min_align = reg_max_ref_width[i] * BITS_PER_UNIT;
2061       int adjust = 0;
2062
2063       /* Each pseudo reg has an inherent size which comes from its own mode,
2064          and a total size which provides room for paradoxical subregs
2065          which refer to the pseudo reg in wider modes.
2066
2067          We can use a slot already allocated if it provides both
2068          enough inherent space and enough total space.
2069          Otherwise, we allocate a new slot, making sure that it has no less
2070          inherent space, and no less total space, then the previous slot.  */
2071       if (from_reg == -1)
2072         {
2073           alias_set_type alias_set = new_alias_set ();
2074
2075           /* No known place to spill from => no slot to reuse.  */
2076           x = assign_stack_local (mode, total_size,
2077                                   min_align > inherent_align
2078                                   || total_size > inherent_size ? -1 : 0);
2079           if (BYTES_BIG_ENDIAN)
2080             /* Cancel the  big-endian correction done in assign_stack_local.
2081                Get the address of the beginning of the slot.
2082                This is so we can do a big-endian correction unconditionally
2083                below.  */
2084             adjust = inherent_size - total_size;
2085
2086           /* Nothing can alias this slot except this pseudo.  */
2087           set_mem_alias_set (x, alias_set);
2088           dse_record_singleton_alias_set (alias_set, mode);
2089         }
2090
2091       /* Reuse a stack slot if possible.  */
2092       else if (spill_stack_slot[from_reg] != 0
2093                && spill_stack_slot_width[from_reg] >= total_size
2094                && (GET_MODE_SIZE (GET_MODE (spill_stack_slot[from_reg]))
2095                    >= inherent_size)
2096                && MEM_ALIGN (spill_stack_slot[from_reg]) >= min_align)
2097         x = spill_stack_slot[from_reg];
2098       /* Allocate a bigger slot.  */
2099       else
2100         {
2101           /* Compute maximum size needed, both for inherent size
2102              and for total size.  */
2103           rtx stack_slot;
2104
2105           if (spill_stack_slot[from_reg])
2106             {
2107               if (GET_MODE_SIZE (GET_MODE (spill_stack_slot[from_reg]))
2108                   > inherent_size)
2109                 mode = GET_MODE (spill_stack_slot[from_reg]);
2110               if (spill_stack_slot_width[from_reg] > total_size)
2111                 total_size = spill_stack_slot_width[from_reg];
2112               if (MEM_ALIGN (spill_stack_slot[from_reg]) > min_align)
2113                 min_align = MEM_ALIGN (spill_stack_slot[from_reg]);
2114             }
2115
2116           /* Make a slot with that size.  */
2117           x = assign_stack_local (mode, total_size,
2118                                   min_align > inherent_align
2119                                   || total_size > inherent_size ? -1 : 0);
2120           stack_slot = x;
2121
2122           /* All pseudos mapped to this slot can alias each other.  */
2123           if (spill_stack_slot[from_reg])
2124             {
2125               alias_set_type alias_set 
2126                 = MEM_ALIAS_SET (spill_stack_slot[from_reg]);
2127               set_mem_alias_set (x, alias_set);
2128               dse_invalidate_singleton_alias_set (alias_set);
2129             }
2130           else
2131             {
2132               alias_set_type alias_set = new_alias_set ();
2133               set_mem_alias_set (x, alias_set);
2134               dse_record_singleton_alias_set (alias_set, mode);
2135             }
2136
2137           if (BYTES_BIG_ENDIAN)
2138             {
2139               /* Cancel the  big-endian correction done in assign_stack_local.
2140                  Get the address of the beginning of the slot.
2141                  This is so we can do a big-endian correction unconditionally
2142                  below.  */
2143               adjust = GET_MODE_SIZE (mode) - total_size;
2144               if (adjust)
2145                 stack_slot
2146                   = adjust_address_nv (x, mode_for_size (total_size
2147                                                          * BITS_PER_UNIT,
2148                                                          MODE_INT, 1),
2149                                        adjust);
2150             }
2151
2152           spill_stack_slot[from_reg] = stack_slot;
2153           spill_stack_slot_width[from_reg] = total_size;
2154         }
2155
2156       /* On a big endian machine, the "address" of the slot
2157          is the address of the low part that fits its inherent mode.  */
2158       if (BYTES_BIG_ENDIAN && inherent_size < total_size)
2159         adjust += (total_size - inherent_size);
2160
2161       /* If we have any adjustment to make, or if the stack slot is the
2162          wrong mode, make a new stack slot.  */
2163       x = adjust_address_nv (x, GET_MODE (regno_reg_rtx[i]), adjust);
2164
2165       /* If we have a decl for the original register, set it for the
2166          memory.  If this is a shared MEM, make a copy.  */
2167       if (REG_EXPR (regno_reg_rtx[i])
2168           && DECL_P (REG_EXPR (regno_reg_rtx[i])))
2169         {
2170           rtx decl = DECL_RTL_IF_SET (REG_EXPR (regno_reg_rtx[i]));
2171
2172           /* We can do this only for the DECLs home pseudo, not for
2173              any copies of it, since otherwise when the stack slot
2174              is reused, nonoverlapping_memrefs_p might think they
2175              cannot overlap.  */
2176           if (decl && REG_P (decl) && REGNO (decl) == (unsigned) i)
2177             {
2178               if (from_reg != -1 && spill_stack_slot[from_reg] == x)
2179                 x = copy_rtx (x);
2180
2181               set_mem_attrs_from_reg (x, regno_reg_rtx[i]);
2182             }
2183         }
2184
2185       /* Save the stack slot for later.  */
2186       reg_equiv_memory_loc[i] = x;
2187     }
2188 }
2189
2190 /* Mark the slots in regs_ever_live for the hard regs used by
2191    pseudo-reg number REGNO, accessed in MODE.  */
2192
2193 static void
2194 mark_home_live_1 (int regno, enum machine_mode mode)
2195 {
2196   int i, lim;
2197
2198   i = reg_renumber[regno];
2199   if (i < 0)
2200     return;
2201   lim = end_hard_regno (mode, i);
2202   while (i < lim)
2203     df_set_regs_ever_live(i++, true);
2204 }
2205
2206 /* Mark the slots in regs_ever_live for the hard regs
2207    used by pseudo-reg number REGNO.  */
2208
2209 void
2210 mark_home_live (int regno)
2211 {
2212   if (reg_renumber[regno] >= 0)
2213     mark_home_live_1 (regno, PSEUDO_REGNO_MODE (regno));
2214 }
2215 \f
2216 /* This function handles the tracking of elimination offsets around branches.
2217
2218    X is a piece of RTL being scanned.
2219
2220    INSN is the insn that it came from, if any.
2221
2222    INITIAL_P is nonzero if we are to set the offset to be the initial
2223    offset and zero if we are setting the offset of the label to be the
2224    current offset.  */
2225
2226 static void
2227 set_label_offsets (rtx x, rtx insn, int initial_p)
2228 {
2229   enum rtx_code code = GET_CODE (x);
2230   rtx tem;
2231   unsigned int i;
2232   struct elim_table *p;
2233
2234   switch (code)
2235     {
2236     case LABEL_REF:
2237       if (LABEL_REF_NONLOCAL_P (x))
2238         return;
2239
2240       x = XEXP (x, 0);
2241
2242       /* ... fall through ...  */
2243
2244     case CODE_LABEL:
2245       /* If we know nothing about this label, set the desired offsets.  Note
2246          that this sets the offset at a label to be the offset before a label
2247          if we don't know anything about the label.  This is not correct for
2248          the label after a BARRIER, but is the best guess we can make.  If
2249          we guessed wrong, we will suppress an elimination that might have
2250          been possible had we been able to guess correctly.  */
2251
2252       if (! offsets_known_at[CODE_LABEL_NUMBER (x) - first_label_num])
2253         {
2254           for (i = 0; i < NUM_ELIMINABLE_REGS; i++)
2255             offsets_at[CODE_LABEL_NUMBER (x) - first_label_num][i]
2256               = (initial_p ? reg_eliminate[i].initial_offset
2257                  : reg_eliminate[i].offset);
2258           offsets_known_at[CODE_LABEL_NUMBER (x) - first_label_num] = 1;
2259         }
2260
2261       /* Otherwise, if this is the definition of a label and it is
2262          preceded by a BARRIER, set our offsets to the known offset of
2263          that label.  */
2264
2265       else if (x == insn
2266                && (tem = prev_nonnote_insn (insn)) != 0
2267                && BARRIER_P (tem))
2268         set_offsets_for_label (insn);
2269       else
2270         /* If neither of the above cases is true, compare each offset
2271            with those previously recorded and suppress any eliminations
2272            where the offsets disagree.  */
2273
2274         for (i = 0; i < NUM_ELIMINABLE_REGS; i++)
2275           if (offsets_at[CODE_LABEL_NUMBER (x) - first_label_num][i]
2276               != (initial_p ? reg_eliminate[i].initial_offset
2277                   : reg_eliminate[i].offset))
2278             reg_eliminate[i].can_eliminate = 0;
2279
2280       return;
2281
2282     case JUMP_INSN:
2283       set_label_offsets (PATTERN (insn), insn, initial_p);
2284
2285       /* ... fall through ...  */
2286
2287     case INSN:
2288     case CALL_INSN:
2289       /* Any labels mentioned in REG_LABEL_OPERAND notes can be branched
2290          to indirectly and hence must have all eliminations at their
2291          initial offsets.  */
2292       for (tem = REG_NOTES (x); tem; tem = XEXP (tem, 1))
2293         if (REG_NOTE_KIND (tem) == REG_LABEL_OPERAND)
2294           set_label_offsets (XEXP (tem, 0), insn, 1);
2295       return;
2296
2297     case PARALLEL:
2298     case ADDR_VEC:
2299     case ADDR_DIFF_VEC:
2300       /* Each of the labels in the parallel or address vector must be
2301          at their initial offsets.  We want the first field for PARALLEL
2302          and ADDR_VEC and the second field for ADDR_DIFF_VEC.  */
2303
2304       for (i = 0; i < (unsigned) XVECLEN (x, code == ADDR_DIFF_VEC); i++)
2305         set_label_offsets (XVECEXP (x, code == ADDR_DIFF_VEC, i),
2306                            insn, initial_p);
2307       return;
2308
2309     case SET:
2310       /* We only care about setting PC.  If the source is not RETURN,
2311          IF_THEN_ELSE, or a label, disable any eliminations not at
2312          their initial offsets.  Similarly if any arm of the IF_THEN_ELSE
2313          isn't one of those possibilities.  For branches to a label,
2314          call ourselves recursively.
2315
2316          Note that this can disable elimination unnecessarily when we have
2317          a non-local goto since it will look like a non-constant jump to
2318          someplace in the current function.  This isn't a significant
2319          problem since such jumps will normally be when all elimination
2320          pairs are back to their initial offsets.  */
2321
2322       if (SET_DEST (x) != pc_rtx)
2323         return;
2324
2325       switch (GET_CODE (SET_SRC (x)))
2326         {
2327         case PC:
2328         case RETURN:
2329           return;
2330
2331         case LABEL_REF:
2332           set_label_offsets (SET_SRC (x), insn, initial_p);
2333           return;
2334
2335         case IF_THEN_ELSE:
2336           tem = XEXP (SET_SRC (x), 1);
2337           if (GET_CODE (tem) == LABEL_REF)
2338             set_label_offsets (XEXP (tem, 0), insn, initial_p);
2339           else if (GET_CODE (tem) != PC && GET_CODE (tem) != RETURN)
2340             break;
2341
2342           tem = XEXP (SET_SRC (x), 2);
2343           if (GET_CODE (tem) == LABEL_REF)
2344             set_label_offsets (XEXP (tem, 0), insn, initial_p);
2345           else if (GET_CODE (tem) != PC && GET_CODE (tem) != RETURN)
2346             break;
2347           return;
2348
2349         default:
2350           break;
2351         }
2352
2353       /* If we reach here, all eliminations must be at their initial
2354          offset because we are doing a jump to a variable address.  */
2355       for (p = reg_eliminate; p < &reg_eliminate[NUM_ELIMINABLE_REGS]; p++)
2356         if (p->offset != p->initial_offset)
2357           p->can_eliminate = 0;
2358       break;
2359
2360     default:
2361       break;
2362     }
2363 }
2364 \f
2365 /* Scan X and replace any eliminable registers (such as fp) with a
2366    replacement (such as sp), plus an offset.
2367
2368    MEM_MODE is the mode of an enclosing MEM.  We need this to know how
2369    much to adjust a register for, e.g., PRE_DEC.  Also, if we are inside a
2370    MEM, we are allowed to replace a sum of a register and the constant zero
2371    with the register, which we cannot do outside a MEM.  In addition, we need
2372    to record the fact that a register is referenced outside a MEM.
2373
2374    If INSN is an insn, it is the insn containing X.  If we replace a REG
2375    in a SET_DEST with an equivalent MEM and INSN is nonzero, write a
2376    CLOBBER of the pseudo after INSN so find_equiv_regs will know that
2377    the REG is being modified.
2378
2379    Alternatively, INSN may be a note (an EXPR_LIST or INSN_LIST).
2380    That's used when we eliminate in expressions stored in notes.
2381    This means, do not set ref_outside_mem even if the reference
2382    is outside of MEMs.
2383
2384    REG_EQUIV_MEM and REG_EQUIV_ADDRESS contain address that have had
2385    replacements done assuming all offsets are at their initial values.  If
2386    they are not, or if REG_EQUIV_ADDRESS is nonzero for a pseudo we
2387    encounter, return the actual location so that find_reloads will do
2388    the proper thing.  */
2389
2390 static rtx
2391 eliminate_regs_1 (rtx x, enum machine_mode mem_mode, rtx insn,
2392                   bool may_use_invariant)
2393 {
2394   enum rtx_code code = GET_CODE (x);
2395   struct elim_table *ep;
2396   int regno;
2397   rtx new;
2398   int i, j;
2399   const char *fmt;
2400   int copied = 0;
2401
2402   if (! current_function_decl)
2403     return x;
2404
2405   switch (code)
2406     {
2407     case CONST_INT:
2408     case CONST_DOUBLE:
2409     case CONST_FIXED:
2410     case CONST_VECTOR:
2411     case CONST:
2412     case SYMBOL_REF:
2413     case CODE_LABEL:
2414     case PC:
2415     case CC0:
2416     case ASM_INPUT:
2417     case ADDR_VEC:
2418     case ADDR_DIFF_VEC:
2419     case RETURN:
2420       return x;
2421
2422     case REG:
2423       regno = REGNO (x);
2424
2425       /* First handle the case where we encounter a bare register that
2426          is eliminable.  Replace it with a PLUS.  */
2427       if (regno < FIRST_PSEUDO_REGISTER)
2428         {
2429           for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
2430                ep++)
2431             if (ep->from_rtx == x && ep->can_eliminate)
2432               return plus_constant (ep->to_rtx, ep->previous_offset);
2433
2434         }
2435       else if (reg_renumber && reg_renumber[regno] < 0
2436                && reg_equiv_invariant && reg_equiv_invariant[regno])
2437         {
2438           if (may_use_invariant)
2439             return eliminate_regs_1 (copy_rtx (reg_equiv_invariant[regno]),
2440                                      mem_mode, insn, true);
2441           /* There exists at least one use of REGNO that cannot be
2442              eliminated.  Prevent the defining insn from being deleted.  */
2443           reg_equiv_init[regno] = NULL_RTX;
2444           alter_reg (regno, -1);
2445         }
2446       return x;
2447
2448     /* You might think handling MINUS in a manner similar to PLUS is a
2449        good idea.  It is not.  It has been tried multiple times and every
2450        time the change has had to have been reverted.
2451
2452        Other parts of reload know a PLUS is special (gen_reload for example)
2453        and require special code to handle code a reloaded PLUS operand.
2454
2455        Also consider backends where the flags register is clobbered by a
2456        MINUS, but we can emit a PLUS that does not clobber flags (IA-32,
2457        lea instruction comes to mind).  If we try to reload a MINUS, we
2458        may kill the flags register that was holding a useful value.
2459
2460        So, please before trying to handle MINUS, consider reload as a
2461        whole instead of this little section as well as the backend issues.  */
2462     case PLUS:
2463       /* If this is the sum of an eliminable register and a constant, rework
2464          the sum.  */
2465       if (REG_P (XEXP (x, 0))
2466           && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER
2467           && CONSTANT_P (XEXP (x, 1)))
2468         {
2469           for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
2470                ep++)
2471             if (ep->from_rtx == XEXP (x, 0) && ep->can_eliminate)
2472               {
2473                 /* The only time we want to replace a PLUS with a REG (this
2474                    occurs when the constant operand of the PLUS is the negative
2475                    of the offset) is when we are inside a MEM.  We won't want
2476                    to do so at other times because that would change the
2477                    structure of the insn in a way that reload can't handle.
2478                    We special-case the commonest situation in
2479                    eliminate_regs_in_insn, so just replace a PLUS with a
2480                    PLUS here, unless inside a MEM.  */
2481                 if (mem_mode != 0 && GET_CODE (XEXP (x, 1)) == CONST_INT
2482                     && INTVAL (XEXP (x, 1)) == - ep->previous_offset)
2483                   return ep->to_rtx;
2484                 else
2485                   return gen_rtx_PLUS (Pmode, ep->to_rtx,
2486                                        plus_constant (XEXP (x, 1),
2487                                                       ep->previous_offset));
2488               }
2489
2490           /* If the register is not eliminable, we are done since the other
2491              operand is a constant.  */
2492           return x;
2493         }
2494
2495       /* If this is part of an address, we want to bring any constant to the
2496          outermost PLUS.  We will do this by doing register replacement in
2497          our operands and seeing if a constant shows up in one of them.
2498
2499          Note that there is no risk of modifying the structure of the insn,
2500          since we only get called for its operands, thus we are either
2501          modifying the address inside a MEM, or something like an address
2502          operand of a load-address insn.  */
2503
2504       {
2505         rtx new0 = eliminate_regs_1 (XEXP (x, 0), mem_mode, insn, true);
2506         rtx new1 = eliminate_regs_1 (XEXP (x, 1), mem_mode, insn, true);
2507
2508         if (reg_renumber && (new0 != XEXP (x, 0) || new1 != XEXP (x, 1)))
2509           {
2510             /* If one side is a PLUS and the other side is a pseudo that
2511                didn't get a hard register but has a reg_equiv_constant,
2512                we must replace the constant here since it may no longer
2513                be in the position of any operand.  */
2514             if (GET_CODE (new0) == PLUS && REG_P (new1)
2515                 && REGNO (new1) >= FIRST_PSEUDO_REGISTER
2516                 && reg_renumber[REGNO (new1)] < 0
2517                 && reg_equiv_constant != 0
2518                 && reg_equiv_constant[REGNO (new1)] != 0)
2519               new1 = reg_equiv_constant[REGNO (new1)];
2520             else if (GET_CODE (new1) == PLUS && REG_P (new0)
2521                      && REGNO (new0) >= FIRST_PSEUDO_REGISTER
2522                      && reg_renumber[REGNO (new0)] < 0
2523                      && reg_equiv_constant[REGNO (new0)] != 0)
2524               new0 = reg_equiv_constant[REGNO (new0)];
2525
2526             new = form_sum (new0, new1);
2527
2528             /* As above, if we are not inside a MEM we do not want to
2529                turn a PLUS into something else.  We might try to do so here
2530                for an addition of 0 if we aren't optimizing.  */
2531             if (! mem_mode && GET_CODE (new) != PLUS)
2532               return gen_rtx_PLUS (GET_MODE (x), new, const0_rtx);
2533             else
2534               return new;
2535           }
2536       }
2537       return x;
2538
2539     case MULT:
2540       /* If this is the product of an eliminable register and a
2541          constant, apply the distribute law and move the constant out
2542          so that we have (plus (mult ..) ..).  This is needed in order
2543          to keep load-address insns valid.   This case is pathological.
2544          We ignore the possibility of overflow here.  */
2545       if (REG_P (XEXP (x, 0))
2546           && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER
2547           && GET_CODE (XEXP (x, 1)) == CONST_INT)
2548         for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
2549              ep++)
2550           if (ep->from_rtx == XEXP (x, 0) && ep->can_eliminate)
2551             {
2552               if (! mem_mode
2553                   /* Refs inside notes don't count for this purpose.  */
2554                   && ! (insn != 0 && (GET_CODE (insn) == EXPR_LIST
2555                                       || GET_CODE (insn) == INSN_LIST)))
2556                 ep->ref_outside_mem = 1;
2557
2558               return
2559                 plus_constant (gen_rtx_MULT (Pmode, ep->to_rtx, XEXP (x, 1)),
2560                                ep->previous_offset * INTVAL (XEXP (x, 1)));
2561             }
2562
2563       /* ... fall through ...  */
2564
2565     case CALL:
2566     case COMPARE:
2567     /* See comments before PLUS about handling MINUS.  */
2568     case MINUS:
2569     case DIV:      case UDIV:
2570     case MOD:      case UMOD:
2571     case AND:      case IOR:      case XOR:
2572     case ROTATERT: case ROTATE:
2573     case ASHIFTRT: case LSHIFTRT: case ASHIFT:
2574     case NE:       case EQ:
2575     case GE:       case GT:       case GEU:    case GTU:
2576     case LE:       case LT:       case LEU:    case LTU:
2577       {
2578         rtx new0 = eliminate_regs_1 (XEXP (x, 0), mem_mode, insn, false);
2579         rtx new1 = XEXP (x, 1)
2580                    ? eliminate_regs_1 (XEXP (x, 1), mem_mode, insn, false) : 0;
2581
2582         if (new0 != XEXP (x, 0) || new1 != XEXP (x, 1))
2583           return gen_rtx_fmt_ee (code, GET_MODE (x), new0, new1);
2584       }
2585       return x;
2586
2587     case EXPR_LIST:
2588       /* If we have something in XEXP (x, 0), the usual case, eliminate it.  */
2589       if (XEXP (x, 0))
2590         {
2591           new = eliminate_regs_1 (XEXP (x, 0), mem_mode, insn, true);
2592           if (new != XEXP (x, 0))
2593             {
2594               /* If this is a REG_DEAD note, it is not valid anymore.
2595                  Using the eliminated version could result in creating a
2596                  REG_DEAD note for the stack or frame pointer.  */
2597               if (GET_MODE (x) == REG_DEAD)
2598                 return (XEXP (x, 1)
2599                         ? eliminate_regs_1 (XEXP (x, 1), mem_mode, insn, true)
2600                         : NULL_RTX);
2601
2602               x = gen_rtx_EXPR_LIST (REG_NOTE_KIND (x), new, XEXP (x, 1));
2603             }
2604         }
2605
2606       /* ... fall through ...  */
2607
2608     case INSN_LIST:
2609       /* Now do eliminations in the rest of the chain.  If this was
2610          an EXPR_LIST, this might result in allocating more memory than is
2611          strictly needed, but it simplifies the code.  */
2612       if (XEXP (x, 1))
2613         {
2614           new = eliminate_regs_1 (XEXP (x, 1), mem_mode, insn, true);
2615           if (new != XEXP (x, 1))
2616             return
2617               gen_rtx_fmt_ee (GET_CODE (x), GET_MODE (x), XEXP (x, 0), new);
2618         }
2619       return x;
2620
2621     case PRE_INC:
2622     case POST_INC:
2623     case PRE_DEC:
2624     case POST_DEC:
2625       /* We do not support elimination of a register that is modified.
2626          elimination_effects has already make sure that this does not
2627          happen.  */
2628       return x;
2629
2630     case PRE_MODIFY:
2631     case POST_MODIFY:
2632       /* We do not support elimination of a register that is modified.
2633          elimination_effects has already make sure that this does not
2634          happen.  The only remaining case we need to consider here is
2635          that the increment value may be an eliminable register.  */
2636       if (GET_CODE (XEXP (x, 1)) == PLUS
2637           && XEXP (XEXP (x, 1), 0) == XEXP (x, 0))
2638         {
2639           rtx new = eliminate_regs_1 (XEXP (XEXP (x, 1), 1), mem_mode,
2640                                       insn, true);
2641
2642           if (new != XEXP (XEXP (x, 1), 1))
2643             return gen_rtx_fmt_ee (code, GET_MODE (x), XEXP (x, 0),
2644                                    gen_rtx_PLUS (GET_MODE (x),
2645                                                  XEXP (x, 0), new));
2646         }
2647       return x;
2648
2649     case STRICT_LOW_PART:
2650     case NEG:          case NOT:
2651     case SIGN_EXTEND:  case ZERO_EXTEND:
2652     case TRUNCATE:     case FLOAT_EXTEND: case FLOAT_TRUNCATE:
2653     case FLOAT:        case FIX:
2654     case UNSIGNED_FIX: case UNSIGNED_FLOAT:
2655     case ABS:
2656     case SQRT:
2657     case FFS:
2658     case CLZ:
2659     case CTZ:
2660     case POPCOUNT:
2661     case PARITY:
2662     case BSWAP:
2663       new = eliminate_regs_1 (XEXP (x, 0), mem_mode, insn, false);
2664       if (new != XEXP (x, 0))
2665         return gen_rtx_fmt_e (code, GET_MODE (x), new);
2666       return x;
2667
2668     case SUBREG:
2669       /* Similar to above processing, but preserve SUBREG_BYTE.
2670          Convert (subreg (mem)) to (mem) if not paradoxical.
2671          Also, if we have a non-paradoxical (subreg (pseudo)) and the
2672          pseudo didn't get a hard reg, we must replace this with the
2673          eliminated version of the memory location because push_reload
2674          may do the replacement in certain circumstances.  */
2675       if (REG_P (SUBREG_REG (x))
2676           && (GET_MODE_SIZE (GET_MODE (x))
2677               <= GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
2678           && reg_equiv_memory_loc != 0
2679           && reg_equiv_memory_loc[REGNO (SUBREG_REG (x))] != 0)
2680         {
2681           new = SUBREG_REG (x);
2682         }
2683       else
2684         new = eliminate_regs_1 (SUBREG_REG (x), mem_mode, insn, false);
2685
2686       if (new != SUBREG_REG (x))
2687         {
2688           int x_size = GET_MODE_SIZE (GET_MODE (x));
2689           int new_size = GET_MODE_SIZE (GET_MODE (new));
2690
2691           if (MEM_P (new)
2692               && ((x_size < new_size
2693 #ifdef WORD_REGISTER_OPERATIONS
2694                    /* On these machines, combine can create rtl of the form
2695                       (set (subreg:m1 (reg:m2 R) 0) ...)
2696                       where m1 < m2, and expects something interesting to
2697                       happen to the entire word.  Moreover, it will use the
2698                       (reg:m2 R) later, expecting all bits to be preserved.
2699                       So if the number of words is the same, preserve the
2700                       subreg so that push_reload can see it.  */
2701                    && ! ((x_size - 1) / UNITS_PER_WORD
2702                          == (new_size -1 ) / UNITS_PER_WORD)
2703 #endif
2704                    )
2705                   || x_size == new_size)
2706               )
2707             return adjust_address_nv (new, GET_MODE (x), SUBREG_BYTE (x));
2708           else
2709             return gen_rtx_SUBREG (GET_MODE (x), new, SUBREG_BYTE (x));
2710         }
2711
2712       return x;
2713
2714     case MEM:
2715       /* Our only special processing is to pass the mode of the MEM to our
2716          recursive call and copy the flags.  While we are here, handle this
2717          case more efficiently.  */
2718       return
2719         replace_equiv_address_nv (x,
2720                                   eliminate_regs_1 (XEXP (x, 0), GET_MODE (x),
2721                                                     insn, true));
2722
2723     case USE:
2724       /* Handle insn_list USE that a call to a pure function may generate.  */
2725       new = eliminate_regs_1 (XEXP (x, 0), 0, insn, false);
2726       if (new != XEXP (x, 0))
2727         return gen_rtx_USE (GET_MODE (x), new);
2728       return x;
2729
2730     case CLOBBER:
2731     case ASM_OPERANDS:
2732     case SET:
2733       gcc_unreachable ();
2734
2735     default:
2736       break;
2737     }
2738
2739   /* Process each of our operands recursively.  If any have changed, make a
2740      copy of the rtx.  */
2741   fmt = GET_RTX_FORMAT (code);
2742   for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
2743     {
2744       if (*fmt == 'e')
2745         {
2746           new = eliminate_regs_1 (XEXP (x, i), mem_mode, insn, false);
2747           if (new != XEXP (x, i) && ! copied)
2748             {
2749               x = shallow_copy_rtx (x);
2750               copied = 1;
2751             }
2752           XEXP (x, i) = new;
2753         }
2754       else if (*fmt == 'E')
2755         {
2756           int copied_vec = 0;
2757           for (j = 0; j < XVECLEN (x, i); j++)
2758             {
2759               new = eliminate_regs_1 (XVECEXP (x, i, j), mem_mode, insn, false);
2760               if (new != XVECEXP (x, i, j) && ! copied_vec)
2761                 {
2762                   rtvec new_v = gen_rtvec_v (XVECLEN (x, i),
2763                                              XVEC (x, i)->elem);
2764                   if (! copied)
2765                     {
2766                       x = shallow_copy_rtx (x);
2767                       copied = 1;
2768                     }
2769                   XVEC (x, i) = new_v;
2770                   copied_vec = 1;
2771                 }
2772               XVECEXP (x, i, j) = new;
2773             }
2774         }
2775     }
2776
2777   return x;
2778 }
2779
2780 rtx
2781 eliminate_regs (rtx x, enum machine_mode mem_mode, rtx insn)
2782 {
2783   return eliminate_regs_1 (x, mem_mode, insn, false);
2784 }
2785
2786 /* Scan rtx X for modifications of elimination target registers.  Update
2787    the table of eliminables to reflect the changed state.  MEM_MODE is
2788    the mode of an enclosing MEM rtx, or VOIDmode if not within a MEM.  */
2789
2790 static void
2791 elimination_effects (rtx x, enum machine_mode mem_mode)
2792 {
2793   enum rtx_code code = GET_CODE (x);
2794   struct elim_table *ep;
2795   int regno;
2796   int i, j;
2797   const char *fmt;
2798
2799   switch (code)
2800     {
2801     case CONST_INT:
2802     case CONST_DOUBLE:
2803     case CONST_FIXED:
2804     case CONST_VECTOR:
2805     case CONST:
2806     case SYMBOL_REF:
2807     case CODE_LABEL:
2808     case PC:
2809     case CC0:
2810     case ASM_INPUT:
2811     case ADDR_VEC:
2812     case ADDR_DIFF_VEC:
2813     case RETURN:
2814       return;
2815
2816     case REG:
2817       regno = REGNO (x);
2818
2819       /* First handle the case where we encounter a bare register that
2820          is eliminable.  Replace it with a PLUS.  */
2821       if (regno < FIRST_PSEUDO_REGISTER)
2822         {
2823           for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
2824                ep++)
2825             if (ep->from_rtx == x && ep->can_eliminate)
2826               {
2827                 if (! mem_mode)
2828                   ep->ref_outside_mem = 1;
2829                 return;
2830               }
2831
2832         }
2833       else if (reg_renumber[regno] < 0 && reg_equiv_constant
2834                && reg_equiv_constant[regno]
2835                && ! function_invariant_p (reg_equiv_constant[regno]))
2836         elimination_effects (reg_equiv_constant[regno], mem_mode);
2837       return;
2838
2839     case PRE_INC:
2840     case POST_INC:
2841     case PRE_DEC:
2842     case POST_DEC:
2843     case POST_MODIFY:
2844     case PRE_MODIFY:
2845       /* If we modify the source of an elimination rule, disable it.  */
2846       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
2847         if (ep->from_rtx == XEXP (x, 0))
2848           ep->can_eliminate = 0;
2849
2850       /* If we modify the target of an elimination rule by adding a constant,
2851          update its offset.  If we modify the target in any other way, we'll
2852          have to disable the rule as well.  */
2853       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
2854         if (ep->to_rtx == XEXP (x, 0))
2855           {
2856             int size = GET_MODE_SIZE (mem_mode);
2857
2858             /* If more bytes than MEM_MODE are pushed, account for them.  */
2859 #ifdef PUSH_ROUNDING
2860             if (ep->to_rtx == stack_pointer_rtx)
2861               size = PUSH_ROUNDING (size);
2862 #endif
2863             if (code == PRE_DEC || code == POST_DEC)
2864               ep->offset += size;
2865             else if (code == PRE_INC || code == POST_INC)
2866               ep->offset -= size;
2867             else if (code == PRE_MODIFY || code == POST_MODIFY)
2868               {
2869                 if (GET_CODE (XEXP (x, 1)) == PLUS
2870                     && XEXP (x, 0) == XEXP (XEXP (x, 1), 0)
2871                     && CONST_INT_P (XEXP (XEXP (x, 1), 1)))
2872                   ep->offset -= INTVAL (XEXP (XEXP (x, 1), 1));
2873                 else
2874                   ep->can_eliminate = 0;
2875               }
2876           }
2877
2878       /* These two aren't unary operators.  */
2879       if (code == POST_MODIFY || code == PRE_MODIFY)
2880         break;
2881
2882       /* Fall through to generic unary operation case.  */
2883     case STRICT_LOW_PART:
2884     case NEG:          case NOT:
2885     case SIGN_EXTEND:  case ZERO_EXTEND:
2886     case TRUNCATE:     case FLOAT_EXTEND: case FLOAT_TRUNCATE:
2887     case FLOAT:        case FIX:
2888     case UNSIGNED_FIX: case UNSIGNED_FLOAT:
2889     case ABS:
2890     case SQRT:
2891     case FFS:
2892     case CLZ:
2893     case CTZ:
2894     case POPCOUNT:
2895     case PARITY:
2896     case BSWAP:
2897       elimination_effects (XEXP (x, 0), mem_mode);
2898       return;
2899
2900     case SUBREG:
2901       if (REG_P (SUBREG_REG (x))
2902           && (GET_MODE_SIZE (GET_MODE (x))
2903               <= GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
2904           && reg_equiv_memory_loc != 0
2905           && reg_equiv_memory_loc[REGNO (SUBREG_REG (x))] != 0)
2906         return;
2907
2908       elimination_effects (SUBREG_REG (x), mem_mode);
2909       return;
2910
2911     case USE:
2912       /* If using a register that is the source of an eliminate we still
2913          think can be performed, note it cannot be performed since we don't
2914          know how this register is used.  */
2915       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
2916         if (ep->from_rtx == XEXP (x, 0))
2917           ep->can_eliminate = 0;
2918
2919       elimination_effects (XEXP (x, 0), mem_mode);
2920       return;
2921
2922     case CLOBBER:
2923       /* If clobbering a register that is the replacement register for an
2924          elimination we still think can be performed, note that it cannot
2925          be performed.  Otherwise, we need not be concerned about it.  */
2926       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
2927         if (ep->to_rtx == XEXP (x, 0))
2928           ep->can_eliminate = 0;
2929
2930       elimination_effects (XEXP (x, 0), mem_mode);
2931       return;
2932
2933     case SET:
2934       /* Check for setting a register that we know about.  */
2935       if (REG_P (SET_DEST (x)))
2936         {
2937           /* See if this is setting the replacement register for an
2938              elimination.
2939
2940              If DEST is the hard frame pointer, we do nothing because we
2941              assume that all assignments to the frame pointer are for
2942              non-local gotos and are being done at a time when they are valid
2943              and do not disturb anything else.  Some machines want to
2944              eliminate a fake argument pointer (or even a fake frame pointer)
2945              with either the real frame or the stack pointer.  Assignments to
2946              the hard frame pointer must not prevent this elimination.  */
2947
2948           for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
2949                ep++)
2950             if (ep->to_rtx == SET_DEST (x)
2951                 && SET_DEST (x) != hard_frame_pointer_rtx)
2952               {
2953                 /* If it is being incremented, adjust the offset.  Otherwise,
2954                    this elimination can't be done.  */
2955                 rtx src = SET_SRC (x);
2956
2957                 if (GET_CODE (src) == PLUS
2958                     && XEXP (src, 0) == SET_DEST (x)
2959                     && GET_CODE (XEXP (src, 1)) == CONST_INT)
2960                   ep->offset -= INTVAL (XEXP (src, 1));
2961                 else
2962                   ep->can_eliminate = 0;
2963               }
2964         }
2965
2966       elimination_effects (SET_DEST (x), 0);
2967       elimination_effects (SET_SRC (x), 0);
2968       return;
2969
2970     case MEM:
2971       /* Our only special processing is to pass the mode of the MEM to our
2972          recursive call.  */
2973       elimination_effects (XEXP (x, 0), GET_MODE (x));
2974       return;
2975
2976     default:
2977       break;
2978     }
2979
2980   fmt = GET_RTX_FORMAT (code);
2981   for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
2982     {
2983       if (*fmt == 'e')
2984         elimination_effects (XEXP (x, i), mem_mode);
2985       else if (*fmt == 'E')
2986         for (j = 0; j < XVECLEN (x, i); j++)
2987           elimination_effects (XVECEXP (x, i, j), mem_mode);
2988     }
2989 }
2990
2991 /* Descend through rtx X and verify that no references to eliminable registers
2992    remain.  If any do remain, mark the involved register as not
2993    eliminable.  */
2994
2995 static void
2996 check_eliminable_occurrences (rtx x)
2997 {
2998   const char *fmt;
2999   int i;
3000   enum rtx_code code;
3001
3002   if (x == 0)
3003     return;
3004
3005   code = GET_CODE (x);
3006
3007   if (code == REG && REGNO (x) < FIRST_PSEUDO_REGISTER)
3008     {
3009       struct elim_table *ep;
3010
3011       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
3012         if (ep->from_rtx == x)
3013           ep->can_eliminate = 0;
3014       return;
3015     }
3016
3017   fmt = GET_RTX_FORMAT (code);
3018   for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
3019     {
3020       if (*fmt == 'e')
3021         check_eliminable_occurrences (XEXP (x, i));
3022       else if (*fmt == 'E')
3023         {
3024           int j;
3025           for (j = 0; j < XVECLEN (x, i); j++)
3026             check_eliminable_occurrences (XVECEXP (x, i, j));
3027         }
3028     }
3029 }
3030 \f
3031 /* Scan INSN and eliminate all eliminable registers in it.
3032
3033    If REPLACE is nonzero, do the replacement destructively.  Also
3034    delete the insn as dead it if it is setting an eliminable register.
3035
3036    If REPLACE is zero, do all our allocations in reload_obstack.
3037
3038    If no eliminations were done and this insn doesn't require any elimination
3039    processing (these are not identical conditions: it might be updating sp,
3040    but not referencing fp; this needs to be seen during reload_as_needed so
3041    that the offset between fp and sp can be taken into consideration), zero
3042    is returned.  Otherwise, 1 is returned.  */
3043
3044 static int
3045 eliminate_regs_in_insn (rtx insn, int replace)
3046 {
3047   int icode = recog_memoized (insn);
3048   rtx old_body = PATTERN (insn);
3049   int insn_is_asm = asm_noperands (old_body) >= 0;
3050   rtx old_set = single_set (insn);
3051   rtx new_body;
3052   int val = 0;
3053   int i;
3054   rtx substed_operand[MAX_RECOG_OPERANDS];
3055   rtx orig_operand[MAX_RECOG_OPERANDS];
3056   struct elim_table *ep;
3057   rtx plus_src, plus_cst_src;
3058
3059   if (! insn_is_asm && icode < 0)
3060     {
3061       gcc_assert (GET_CODE (PATTERN (insn)) == USE
3062                   || GET_CODE (PATTERN (insn)) == CLOBBER
3063                   || GET_CODE (PATTERN (insn)) == ADDR_VEC
3064                   || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC
3065                   || GET_CODE (PATTERN (insn)) == ASM_INPUT);
3066       return 0;
3067     }
3068
3069   if (old_set != 0 && REG_P (SET_DEST (old_set))
3070       && REGNO (SET_DEST (old_set)) < FIRST_PSEUDO_REGISTER)
3071     {
3072       /* Check for setting an eliminable register.  */
3073       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
3074         if (ep->from_rtx == SET_DEST (old_set) && ep->can_eliminate)
3075           {
3076 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
3077             /* If this is setting the frame pointer register to the
3078                hardware frame pointer register and this is an elimination
3079                that will be done (tested above), this insn is really
3080                adjusting the frame pointer downward to compensate for
3081                the adjustment done before a nonlocal goto.  */
3082             if (ep->from == FRAME_POINTER_REGNUM
3083                 && ep->to == HARD_FRAME_POINTER_REGNUM)
3084               {
3085                 rtx base = SET_SRC (old_set);
3086                 rtx base_insn = insn;
3087                 HOST_WIDE_INT offset = 0;
3088
3089                 while (base != ep->to_rtx)
3090                   {
3091                     rtx prev_insn, prev_set;
3092
3093                     if (GET_CODE (base) == PLUS
3094                         && GET_CODE (XEXP (base, 1)) == CONST_INT)
3095                       {
3096                         offset += INTVAL (XEXP (base, 1));
3097                         base = XEXP (base, 0);
3098                       }
3099                     else if ((prev_insn = prev_nonnote_insn (base_insn)) != 0
3100                              && (prev_set = single_set (prev_insn)) != 0
3101                              && rtx_equal_p (SET_DEST (prev_set), base))
3102                       {
3103                         base = SET_SRC (prev_set);
3104                         base_insn = prev_insn;
3105                       }
3106                     else
3107                       break;
3108                   }
3109
3110                 if (base == ep->to_rtx)
3111                   {
3112                     rtx src
3113                       = plus_constant (ep->to_rtx, offset - ep->offset);
3114
3115                     new_body = old_body;
3116                     if (! replace)
3117                       {
3118                         new_body = copy_insn (old_body);
3119                         if (REG_NOTES (insn))
3120                           REG_NOTES (insn) = copy_insn_1 (REG_NOTES (insn));
3121                       }
3122                     PATTERN (insn) = new_body;
3123                     old_set = single_set (insn);
3124
3125                     /* First see if this insn remains valid when we
3126                        make the change.  If not, keep the INSN_CODE
3127                        the same and let reload fit it up.  */
3128                     validate_change (insn, &SET_SRC (old_set), src, 1);
3129                     validate_change (insn, &SET_DEST (old_set),
3130                                      ep->to_rtx, 1);
3131                     if (! apply_change_group ())
3132                       {
3133                         SET_SRC (old_set) = src;
3134                         SET_DEST (old_set) = ep->to_rtx;
3135                       }
3136
3137                     val = 1;
3138                     goto done;
3139                   }
3140               }
3141 #endif
3142
3143             /* In this case this insn isn't serving a useful purpose.  We
3144                will delete it in reload_as_needed once we know that this
3145                elimination is, in fact, being done.
3146
3147                If REPLACE isn't set, we can't delete this insn, but needn't
3148                process it since it won't be used unless something changes.  */
3149             if (replace)
3150               {
3151                 delete_dead_insn (insn);
3152                 return 1;
3153               }
3154             val = 1;
3155             goto done;
3156           }
3157     }
3158
3159   /* We allow one special case which happens to work on all machines we
3160      currently support: a single set with the source or a REG_EQUAL
3161      note being a PLUS of an eliminable register and a constant.  */
3162   plus_src = plus_cst_src = 0;
3163   if (old_set && REG_P (SET_DEST (old_set)))
3164     {
3165       if (GET_CODE (SET_SRC (old_set)) == PLUS)
3166         plus_src = SET_SRC (old_set);
3167       /* First see if the source is of the form (plus (...) CST).  */
3168       if (plus_src
3169           && GET_CODE (XEXP (plus_src, 1)) == CONST_INT)
3170         plus_cst_src = plus_src;
3171       else if (REG_P (SET_SRC (old_set))
3172                || plus_src)
3173         {
3174           /* Otherwise, see if we have a REG_EQUAL note of the form
3175              (plus (...) CST).  */
3176           rtx links;
3177           for (links = REG_NOTES (insn); links; links = XEXP (links, 1))
3178             {
3179               if ((REG_NOTE_KIND (links) == REG_EQUAL
3180                    || REG_NOTE_KIND (links) == REG_EQUIV)
3181                   && GET_CODE (XEXP (links, 0)) == PLUS
3182                   && GET_CODE (XEXP (XEXP (links, 0), 1)) == CONST_INT)
3183                 {
3184                   plus_cst_src = XEXP (links, 0);
3185                   break;
3186                 }
3187             }
3188         }
3189
3190       /* Check that the first operand of the PLUS is a hard reg or
3191          the lowpart subreg of one.  */
3192       if (plus_cst_src)
3193         {
3194           rtx reg = XEXP (plus_cst_src, 0);
3195           if (GET_CODE (reg) == SUBREG && subreg_lowpart_p (reg))
3196             reg = SUBREG_REG (reg);
3197
3198           if (!REG_P (reg) || REGNO (reg) >= FIRST_PSEUDO_REGISTER)
3199             plus_cst_src = 0;
3200         }
3201     }
3202   if (plus_cst_src)
3203     {
3204       rtx reg = XEXP (plus_cst_src, 0);
3205       HOST_WIDE_INT offset = INTVAL (XEXP (plus_cst_src, 1));
3206
3207       if (GET_CODE (reg) == SUBREG)
3208         reg = SUBREG_REG (reg);
3209
3210       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
3211         if (ep->from_rtx == reg && ep->can_eliminate)
3212           {
3213             rtx to_rtx = ep->to_rtx;
3214             offset += ep->offset;
3215             offset = trunc_int_for_mode (offset, GET_MODE (reg));
3216
3217             if (GET_CODE (XEXP (plus_cst_src, 0)) == SUBREG)
3218               to_rtx = gen_lowpart (GET_MODE (XEXP (plus_cst_src, 0)),
3219                                     to_rtx);
3220             /* If we have a nonzero offset, and the source is already
3221                a simple REG, the following transformation would
3222                increase the cost of the insn by replacing a simple REG
3223                with (plus (reg sp) CST).  So try only when we already
3224                had a PLUS before.  */
3225             if (offset == 0 || plus_src)
3226               {
3227                 rtx new_src = plus_constant (to_rtx, offset);
3228
3229                 new_body = old_body;
3230                 if (! replace)
3231                   {
3232                     new_body = copy_insn (old_body);
3233                     if (REG_NOTES (insn))
3234                       REG_NOTES (insn) = copy_insn_1 (REG_NOTES (insn));
3235                   }
3236                 PATTERN (insn) = new_body;
3237                 old_set = single_set (insn);
3238
3239                 /* First see if this insn remains valid when we make the
3240                    change.  If not, try to replace the whole pattern with
3241                    a simple set (this may help if the original insn was a
3242                    PARALLEL that was only recognized as single_set due to 
3243                    REG_UNUSED notes).  If this isn't valid either, keep
3244                    the INSN_CODE the same and let reload fix it up.  */
3245                 if (!validate_change (insn, &SET_SRC (old_set), new_src, 0))
3246                   {
3247                     rtx new_pat = gen_rtx_SET (VOIDmode,
3248                                                SET_DEST (old_set), new_src);
3249
3250                     if (!validate_change (insn, &PATTERN (insn), new_pat, 0))
3251                       SET_SRC (old_set) = new_src;
3252                   }
3253               }
3254             else
3255               break;
3256
3257             val = 1;
3258             /* This can't have an effect on elimination offsets, so skip right
3259                to the end.  */
3260             goto done;
3261           }
3262     }
3263
3264   /* Determine the effects of this insn on elimination offsets.  */
3265   elimination_effects (old_body, 0);
3266
3267   /* Eliminate all eliminable registers occurring in operands that
3268      can be handled by reload.  */
3269   extract_insn (insn);
3270   for (i = 0; i < recog_data.n_operands; i++)
3271     {
3272       orig_operand[i] = recog_data.operand[i];
3273       substed_operand[i] = recog_data.operand[i];
3274
3275       /* For an asm statement, every operand is eliminable.  */
3276       if (insn_is_asm || insn_data[icode].operand[i].eliminable)
3277         {
3278           bool is_set_src, in_plus;
3279
3280           /* Check for setting a register that we know about.  */
3281           if (recog_data.operand_type[i] != OP_IN
3282               && REG_P (orig_operand[i]))
3283             {
3284               /* If we are assigning to a register that can be eliminated, it
3285                  must be as part of a PARALLEL, since the code above handles
3286                  single SETs.  We must indicate that we can no longer
3287                  eliminate this reg.  */
3288               for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
3289                    ep++)
3290                 if (ep->from_rtx == orig_operand[i])
3291                   ep->can_eliminate = 0;
3292             }
3293
3294           /* Companion to the above plus substitution, we can allow
3295              invariants as the source of a plain move.  */
3296           is_set_src = false;
3297           if (old_set && recog_data.operand_loc[i] == &SET_SRC (old_set))
3298             is_set_src = true;
3299           in_plus = false;
3300           if (plus_src
3301               && (recog_data.operand_loc[i] == &XEXP (plus_src, 0)
3302                   || recog_data.operand_loc[i] == &XEXP (plus_src, 1)))
3303             in_plus = true;
3304
3305           substed_operand[i]
3306             = eliminate_regs_1 (recog_data.operand[i], 0,
3307                                 replace ? insn : NULL_RTX,
3308                                 is_set_src || in_plus);
3309           if (substed_operand[i] != orig_operand[i])
3310             val = 1;
3311           /* Terminate the search in check_eliminable_occurrences at
3312              this point.  */
3313           *recog_data.operand_loc[i] = 0;
3314
3315           /* If an output operand changed from a REG to a MEM and INSN is an
3316              insn, write a CLOBBER insn.  */
3317           if (recog_data.operand_type[i] != OP_IN
3318               && REG_P (orig_operand[i])
3319               && MEM_P (substed_operand[i])
3320               && replace)
3321             emit_insn_after (gen_clobber (orig_operand[i]), insn);
3322         }
3323     }
3324
3325   for (i = 0; i < recog_data.n_dups; i++)
3326     *recog_data.dup_loc[i]
3327       = *recog_data.operand_loc[(int) recog_data.dup_num[i]];
3328
3329   /* If any eliminable remain, they aren't eliminable anymore.  */
3330   check_eliminable_occurrences (old_body);
3331
3332   /* Substitute the operands; the new values are in the substed_operand
3333      array.  */
3334   for (i = 0; i < recog_data.n_operands; i++)
3335     *recog_data.operand_loc[i] = substed_operand[i];
3336   for (i = 0; i < recog_data.n_dups; i++)
3337     *recog_data.dup_loc[i] = substed_operand[(int) recog_data.dup_num[i]];
3338
3339   /* If we are replacing a body that was a (set X (plus Y Z)), try to
3340      re-recognize the insn.  We do this in case we had a simple addition
3341      but now can do this as a load-address.  This saves an insn in this
3342      common case.
3343      If re-recognition fails, the old insn code number will still be used,
3344      and some register operands may have changed into PLUS expressions.
3345      These will be handled by find_reloads by loading them into a register
3346      again.  */
3347
3348   if (val)
3349     {
3350       /* If we aren't replacing things permanently and we changed something,
3351          make another copy to ensure that all the RTL is new.  Otherwise
3352          things can go wrong if find_reload swaps commutative operands
3353          and one is inside RTL that has been copied while the other is not.  */
3354       new_body = old_body;
3355       if (! replace)
3356         {
3357           new_body = copy_insn (old_body);
3358           if (REG_NOTES (insn))
3359             REG_NOTES (insn) = copy_insn_1 (REG_NOTES (insn));
3360         }
3361       PATTERN (insn) = new_body;
3362
3363       /* If we had a move insn but now we don't, rerecognize it.  This will
3364          cause spurious re-recognition if the old move had a PARALLEL since
3365          the new one still will, but we can't call single_set without
3366          having put NEW_BODY into the insn and the re-recognition won't
3367          hurt in this rare case.  */
3368       /* ??? Why this huge if statement - why don't we just rerecognize the
3369          thing always?  */
3370       if (! insn_is_asm
3371           && old_set != 0
3372           && ((REG_P (SET_SRC (old_set))
3373                && (GET_CODE (new_body) != SET
3374                    || !REG_P (SET_SRC (new_body))))
3375               /* If this was a load from or store to memory, compare
3376                  the MEM in recog_data.operand to the one in the insn.
3377                  If they are not equal, then rerecognize the insn.  */
3378               || (old_set != 0
3379                   && ((MEM_P (SET_SRC (old_set))
3380                        && SET_SRC (old_set) != recog_data.operand[1])
3381                       || (MEM_P (SET_DEST (old_set))
3382                           && SET_DEST (old_set) != recog_data.operand[0])))
3383               /* If this was an add insn before, rerecognize.  */
3384               || GET_CODE (SET_SRC (old_set)) == PLUS))
3385         {
3386           int new_icode = recog (PATTERN (insn), insn, 0);
3387           if (new_icode >= 0)
3388             INSN_CODE (insn) = new_icode;
3389         }
3390     }
3391
3392   /* Restore the old body.  If there were any changes to it, we made a copy
3393      of it while the changes were still in place, so we'll correctly return
3394      a modified insn below.  */
3395   if (! replace)
3396     {
3397       /* Restore the old body.  */
3398       for (i = 0; i < recog_data.n_operands; i++)
3399         *recog_data.operand_loc[i] = orig_operand[i];
3400       for (i = 0; i < recog_data.n_dups; i++)
3401         *recog_data.dup_loc[i] = orig_operand[(int) recog_data.dup_num[i]];
3402     }
3403
3404   /* Update&