OSDN Git Service

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