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