OSDN Git Service

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