OSDN Git Service

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