OSDN Git Service

394a43014b62a7765bed08b58a4b55d0fdb0febb
[pf3gnuchains/gcc-fork.git] / gcc / reload.c
1 /* Search an insn for pseudo regs that must be in hard regs and are not.
2    Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3    1999, 2000, 2001, 2002, 2003, 2004, 2005  Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING.  If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, USA.  */
21
22 /* This file contains subroutines used only from the file reload1.c.
23    It knows how to scan one insn for operands and values
24    that need to be copied into registers to make valid code.
25    It also finds other operands and values which are valid
26    but for which equivalent values in registers exist and
27    ought to be used instead.
28
29    Before processing the first insn of the function, call `init_reload'.
30    init_reload actually has to be called earlier anyway.
31
32    To scan an insn, call `find_reloads'.  This does two things:
33    1. sets up tables describing which values must be reloaded
34    for this insn, and what kind of hard regs they must be reloaded into;
35    2. optionally record the locations where those values appear in
36    the data, so they can be replaced properly later.
37    This is done only if the second arg to `find_reloads' is nonzero.
38
39    The third arg to `find_reloads' specifies the number of levels
40    of indirect addressing supported by the machine.  If it is zero,
41    indirect addressing is not valid.  If it is one, (MEM (REG n))
42    is valid even if (REG n) did not get a hard register; if it is two,
43    (MEM (MEM (REG n))) is also valid even if (REG n) did not get a
44    hard register, and similarly for higher values.
45
46    Then you must choose the hard regs to reload those pseudo regs into,
47    and generate appropriate load insns before this insn and perhaps
48    also store insns after this insn.  Set up the array `reload_reg_rtx'
49    to contain the REG rtx's for the registers you used.  In some
50    cases `find_reloads' will return a nonzero value in `reload_reg_rtx'
51    for certain reloads.  Then that tells you which register to use,
52    so you do not need to allocate one.  But you still do need to add extra
53    instructions to copy the value into and out of that register.
54
55    Finally you must call `subst_reloads' to substitute the reload reg rtx's
56    into the locations already recorded.
57
58 NOTE SIDE EFFECTS:
59
60    find_reloads can alter the operands of the instruction it is called on.
61
62    1. Two operands of any sort may be interchanged, if they are in a
63    commutative instruction.
64    This happens only if find_reloads thinks the instruction will compile
65    better that way.
66
67    2. Pseudo-registers that are equivalent to constants are replaced
68    with those constants if they are not in hard registers.
69
70 1 happens every time find_reloads is called.
71 2 happens only when REPLACE is 1, which is only when
72 actually doing the reloads, not when just counting them.
73
74 Using a reload register for several reloads in one insn:
75
76 When an insn has reloads, it is considered as having three parts:
77 the input reloads, the insn itself after reloading, and the output reloads.
78 Reloads of values used in memory addresses are often needed for only one part.
79
80 When this is so, reload_when_needed records which part needs the reload.
81 Two reloads for different parts of the insn can share the same reload
82 register.
83
84 When a reload is used for addresses in multiple parts, or when it is
85 an ordinary operand, it is classified as RELOAD_OTHER, and cannot share
86 a register with any other reload.  */
87
88 #define REG_OK_STRICT
89
90 #include "config.h"
91 #include "system.h"
92 #include "coretypes.h"
93 #include "tm.h"
94 #include "rtl.h"
95 #include "tm_p.h"
96 #include "insn-config.h"
97 #include "expr.h"
98 #include "optabs.h"
99 #include "recog.h"
100 #include "reload.h"
101 #include "regs.h"
102 #include "hard-reg-set.h"
103 #include "flags.h"
104 #include "real.h"
105 #include "output.h"
106 #include "function.h"
107 #include "toplev.h"
108 #include "params.h"
109 #include "target.h"
110
111 /* True if X is a constant that can be forced into the constant pool.  */
112 #define CONST_POOL_OK_P(X)                      \
113   (CONSTANT_P (X)                               \
114    && GET_CODE (X) != HIGH                      \
115    && !targetm.cannot_force_const_mem (X))
116
117 /* True if C is a non-empty register class that has too few registers
118    to be safely used as a reload target class.  */
119 #define SMALL_REGISTER_CLASS_P(C) \
120   (reg_class_size [(C)] == 1 \
121    || (reg_class_size [(C)] >= 1 && CLASS_LIKELY_SPILLED_P (C)))
122
123 \f
124 /* All reloads of the current insn are recorded here.  See reload.h for
125    comments.  */
126 int n_reloads;
127 struct reload rld[MAX_RELOADS];
128
129 /* All the "earlyclobber" operands of the current insn
130    are recorded here.  */
131 int n_earlyclobbers;
132 rtx reload_earlyclobbers[MAX_RECOG_OPERANDS];
133
134 int reload_n_operands;
135
136 /* Replacing reloads.
137
138    If `replace_reloads' is nonzero, then as each reload is recorded
139    an entry is made for it in the table `replacements'.
140    Then later `subst_reloads' can look through that table and
141    perform all the replacements needed.  */
142
143 /* Nonzero means record the places to replace.  */
144 static int replace_reloads;
145
146 /* Each replacement is recorded with a structure like this.  */
147 struct replacement
148 {
149   rtx *where;                   /* Location to store in */
150   rtx *subreg_loc;              /* Location of SUBREG if WHERE is inside
151                                    a SUBREG; 0 otherwise.  */
152   int what;                     /* which reload this is for */
153   enum machine_mode mode;       /* mode it must have */
154 };
155
156 static struct replacement replacements[MAX_RECOG_OPERANDS * ((MAX_REGS_PER_ADDRESS * 2) + 1)];
157
158 /* Number of replacements currently recorded.  */
159 static int n_replacements;
160
161 /* Used to track what is modified by an operand.  */
162 struct decomposition
163 {
164   int reg_flag;         /* Nonzero if referencing a register.  */
165   int safe;             /* Nonzero if this can't conflict with anything.  */
166   rtx base;             /* Base address for MEM.  */
167   HOST_WIDE_INT start;  /* Starting offset or register number.  */
168   HOST_WIDE_INT end;    /* Ending offset or register number.  */
169 };
170
171 #ifdef SECONDARY_MEMORY_NEEDED
172
173 /* Save MEMs needed to copy from one class of registers to another.  One MEM
174    is used per mode, but normally only one or two modes are ever used.
175
176    We keep two versions, before and after register elimination.  The one
177    after register elimination is record separately for each operand.  This
178    is done in case the address is not valid to be sure that we separately
179    reload each.  */
180
181 static rtx secondary_memlocs[NUM_MACHINE_MODES];
182 static rtx secondary_memlocs_elim[NUM_MACHINE_MODES][MAX_RECOG_OPERANDS];
183 static int secondary_memlocs_elim_used = 0;
184 #endif
185
186 /* The instruction we are doing reloads for;
187    so we can test whether a register dies in it.  */
188 static rtx this_insn;
189
190 /* Nonzero if this instruction is a user-specified asm with operands.  */
191 static int this_insn_is_asm;
192
193 /* If hard_regs_live_known is nonzero,
194    we can tell which hard regs are currently live,
195    at least enough to succeed in choosing dummy reloads.  */
196 static int hard_regs_live_known;
197
198 /* Indexed by hard reg number,
199    element is nonnegative if hard reg has been spilled.
200    This vector is passed to `find_reloads' as an argument
201    and is not changed here.  */
202 static short *static_reload_reg_p;
203
204 /* Set to 1 in subst_reg_equivs if it changes anything.  */
205 static int subst_reg_equivs_changed;
206
207 /* On return from push_reload, holds the reload-number for the OUT
208    operand, which can be different for that from the input operand.  */
209 static int output_reloadnum;
210
211   /* Compare two RTX's.  */
212 #define MATCHES(x, y) \
213  (x == y || (x != 0 && (REG_P (x)                               \
214                         ? REG_P (y) && REGNO (x) == REGNO (y)   \
215                         : rtx_equal_p (x, y) && ! side_effects_p (x))))
216
217   /* Indicates if two reloads purposes are for similar enough things that we
218      can merge their reloads.  */
219 #define MERGABLE_RELOADS(when1, when2, op1, op2) \
220   ((when1) == RELOAD_OTHER || (when2) == RELOAD_OTHER   \
221    || ((when1) == (when2) && (op1) == (op2))            \
222    || ((when1) == RELOAD_FOR_INPUT && (when2) == RELOAD_FOR_INPUT) \
223    || ((when1) == RELOAD_FOR_OPERAND_ADDRESS            \
224        && (when2) == RELOAD_FOR_OPERAND_ADDRESS)        \
225    || ((when1) == RELOAD_FOR_OTHER_ADDRESS              \
226        && (when2) == RELOAD_FOR_OTHER_ADDRESS))
227
228   /* Nonzero if these two reload purposes produce RELOAD_OTHER when merged.  */
229 #define MERGE_TO_OTHER(when1, when2, op1, op2) \
230   ((when1) != (when2)                                   \
231    || ! ((op1) == (op2)                                 \
232          || (when1) == RELOAD_FOR_INPUT                 \
233          || (when1) == RELOAD_FOR_OPERAND_ADDRESS       \
234          || (when1) == RELOAD_FOR_OTHER_ADDRESS))
235
236   /* If we are going to reload an address, compute the reload type to
237      use.  */
238 #define ADDR_TYPE(type)                                 \
239   ((type) == RELOAD_FOR_INPUT_ADDRESS                   \
240    ? RELOAD_FOR_INPADDR_ADDRESS                         \
241    : ((type) == RELOAD_FOR_OUTPUT_ADDRESS               \
242       ? RELOAD_FOR_OUTADDR_ADDRESS                      \
243       : (type)))
244
245 #ifdef HAVE_SECONDARY_RELOADS
246 static int push_secondary_reload (int, rtx, int, int, enum reg_class,
247                                   enum machine_mode, enum reload_type,
248                                   enum insn_code *);
249 #endif
250 static enum reg_class find_valid_class (enum machine_mode, enum machine_mode,
251                                         int, unsigned int);
252 static int reload_inner_reg_of_subreg (rtx, enum machine_mode, int);
253 static void push_replacement (rtx *, int, enum machine_mode);
254 static void dup_replacements (rtx *, rtx *);
255 static void combine_reloads (void);
256 static int find_reusable_reload (rtx *, rtx, enum reg_class,
257                                  enum reload_type, int, int);
258 static rtx find_dummy_reload (rtx, rtx, rtx *, rtx *, enum machine_mode,
259                               enum machine_mode, enum reg_class, int, int);
260 static int hard_reg_set_here_p (unsigned int, unsigned int, rtx);
261 static struct decomposition decompose (rtx);
262 static int immune_p (rtx, rtx, struct decomposition);
263 static int alternative_allows_memconst (const char *, int);
264 static rtx find_reloads_toplev (rtx, int, enum reload_type, int, int, rtx,
265                                 int *);
266 static rtx make_memloc (rtx, int);
267 static int maybe_memory_address_p (enum machine_mode, rtx, rtx *);
268 static int find_reloads_address (enum machine_mode, rtx *, rtx, rtx *,
269                                  int, enum reload_type, int, rtx);
270 static rtx subst_reg_equivs (rtx, rtx);
271 static rtx subst_indexed_address (rtx);
272 static void update_auto_inc_notes (rtx, int, int);
273 static int find_reloads_address_1 (enum machine_mode, rtx, int, rtx *,
274                                    int, enum reload_type,int, rtx);
275 static void find_reloads_address_part (rtx, rtx *, enum reg_class,
276                                        enum machine_mode, int,
277                                        enum reload_type, int);
278 static rtx find_reloads_subreg_address (rtx, int, int, enum reload_type,
279                                         int, rtx);
280 static void copy_replacements_1 (rtx *, rtx *, int);
281 static int find_inc_amount (rtx, rtx);
282 static int refers_to_mem_for_reload_p (rtx);
283 static int refers_to_regno_for_reload_p (unsigned int, unsigned int,
284                                          rtx, rtx *);
285 \f
286 #ifdef HAVE_SECONDARY_RELOADS
287
288 /* Determine if any secondary reloads are needed for loading (if IN_P is
289    nonzero) or storing (if IN_P is zero) X to or from a reload register of
290    register class RELOAD_CLASS in mode RELOAD_MODE.  If secondary reloads
291    are needed, push them.
292
293    Return the reload number of the secondary reload we made, or -1 if
294    we didn't need one.  *PICODE is set to the insn_code to use if we do
295    need a secondary reload.  */
296
297 static int
298 push_secondary_reload (int in_p, rtx x, int opnum, int optional,
299                        enum reg_class reload_class,
300                        enum machine_mode reload_mode, enum reload_type type,
301                        enum insn_code *picode)
302 {
303   enum reg_class class = NO_REGS;
304   enum machine_mode mode = reload_mode;
305   enum insn_code icode = CODE_FOR_nothing;
306   enum reg_class t_class = NO_REGS;
307   enum machine_mode t_mode = VOIDmode;
308   enum insn_code t_icode = CODE_FOR_nothing;
309   enum reload_type secondary_type;
310   int s_reload, t_reload = -1;
311
312   if (type == RELOAD_FOR_INPUT_ADDRESS
313       || type == RELOAD_FOR_OUTPUT_ADDRESS
314       || type == RELOAD_FOR_INPADDR_ADDRESS
315       || type == RELOAD_FOR_OUTADDR_ADDRESS)
316     secondary_type = type;
317   else
318     secondary_type = in_p ? RELOAD_FOR_INPUT_ADDRESS : RELOAD_FOR_OUTPUT_ADDRESS;
319
320   *picode = CODE_FOR_nothing;
321
322   /* If X is a paradoxical SUBREG, use the inner value to determine both the
323      mode and object being reloaded.  */
324   if (GET_CODE (x) == SUBREG
325       && (GET_MODE_SIZE (GET_MODE (x))
326           > GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))))
327     {
328       x = SUBREG_REG (x);
329       reload_mode = GET_MODE (x);
330     }
331
332   /* If X is a pseudo-register that has an equivalent MEM (actually, if it
333      is still a pseudo-register by now, it *must* have an equivalent MEM
334      but we don't want to assume that), use that equivalent when seeing if
335      a secondary reload is needed since whether or not a reload is needed
336      might be sensitive to the form of the MEM.  */
337
338   if (REG_P (x) && REGNO (x) >= FIRST_PSEUDO_REGISTER
339       && reg_equiv_mem[REGNO (x)] != 0)
340     x = reg_equiv_mem[REGNO (x)];
341
342 #ifdef SECONDARY_INPUT_RELOAD_CLASS
343   if (in_p)
344     class = SECONDARY_INPUT_RELOAD_CLASS (reload_class, reload_mode, x);
345 #endif
346
347 #ifdef SECONDARY_OUTPUT_RELOAD_CLASS
348   if (! in_p)
349     class = SECONDARY_OUTPUT_RELOAD_CLASS (reload_class, reload_mode, x);
350 #endif
351
352   /* If we don't need any secondary registers, done.  */
353   if (class == NO_REGS)
354     return -1;
355
356   /* Get a possible insn to use.  If the predicate doesn't accept X, don't
357      use the insn.  */
358
359   icode = (in_p ? reload_in_optab[(int) reload_mode]
360            : reload_out_optab[(int) reload_mode]);
361
362   if (icode != CODE_FOR_nothing
363       && insn_data[(int) icode].operand[in_p].predicate
364       && (! (insn_data[(int) icode].operand[in_p].predicate) (x, reload_mode)))
365     icode = CODE_FOR_nothing;
366
367   /* If we will be using an insn, see if it can directly handle the reload
368      register we will be using.  If it can, the secondary reload is for a
369      scratch register.  If it can't, we will use the secondary reload for
370      an intermediate register and require a tertiary reload for the scratch
371      register.  */
372
373   if (icode != CODE_FOR_nothing)
374     {
375       /* If IN_P is nonzero, the reload register will be the output in
376          operand 0.  If IN_P is zero, the reload register will be the input
377          in operand 1.  Outputs should have an initial "=", which we must
378          skip.  */
379
380       enum reg_class insn_class;
381
382       if (insn_data[(int) icode].operand[!in_p].constraint[0] == 0)
383         insn_class = ALL_REGS;
384       else
385         {
386           const char *insn_constraint
387             = &insn_data[(int) icode].operand[!in_p].constraint[in_p];
388           char insn_letter = *insn_constraint;
389           insn_class
390             = (insn_letter == 'r' ? GENERAL_REGS
391                : REG_CLASS_FROM_CONSTRAINT ((unsigned char) insn_letter,
392                                             insn_constraint));
393
394           gcc_assert (insn_class != NO_REGS);
395           gcc_assert (!in_p
396                       || insn_data[(int) icode].operand[!in_p].constraint[0]
397                          == '=');
398         }
399
400       /* The scratch register's constraint must start with "=&".  */
401       gcc_assert (insn_data[(int) icode].operand[2].constraint[0] == '='
402                   && insn_data[(int) icode].operand[2].constraint[1] == '&');
403
404       if (reg_class_subset_p (reload_class, insn_class))
405         mode = insn_data[(int) icode].operand[2].mode;
406       else
407         {
408           const char *t_constraint
409             = &insn_data[(int) icode].operand[2].constraint[2];
410           char t_letter = *t_constraint;
411           class = insn_class;
412           t_mode = insn_data[(int) icode].operand[2].mode;
413           t_class = (t_letter == 'r' ? GENERAL_REGS
414                      : REG_CLASS_FROM_CONSTRAINT ((unsigned char) t_letter,
415                                                   t_constraint));
416           t_icode = icode;
417           icode = CODE_FOR_nothing;
418         }
419     }
420
421   /* This case isn't valid, so fail.  Reload is allowed to use the same
422      register for RELOAD_FOR_INPUT_ADDRESS and RELOAD_FOR_INPUT reloads, but
423      in the case of a secondary register, we actually need two different
424      registers for correct code.  We fail here to prevent the possibility of
425      silently generating incorrect code later.
426
427      The convention is that secondary input reloads are valid only if the
428      secondary_class is different from class.  If you have such a case, you
429      can not use secondary reloads, you must work around the problem some
430      other way.
431
432      Allow this when a reload_in/out pattern is being used.  I.e. assume
433      that the generated code handles this case.  */
434
435   gcc_assert (!in_p || class != reload_class || icode != CODE_FOR_nothing
436               || t_icode != CODE_FOR_nothing);
437
438   /* If we need a tertiary reload, see if we have one we can reuse or else
439      make a new one.  */
440
441   if (t_class != NO_REGS)
442     {
443       for (t_reload = 0; t_reload < n_reloads; t_reload++)
444         if (rld[t_reload].secondary_p
445             && (reg_class_subset_p (t_class, rld[t_reload].class)
446                 || reg_class_subset_p (rld[t_reload].class, t_class))
447             && ((in_p && rld[t_reload].inmode == t_mode)
448                 || (! in_p && rld[t_reload].outmode == t_mode))
449             && ((in_p && (rld[t_reload].secondary_in_icode
450                           == CODE_FOR_nothing))
451                 || (! in_p &&(rld[t_reload].secondary_out_icode
452                               == CODE_FOR_nothing)))
453             && (SMALL_REGISTER_CLASS_P (t_class) || SMALL_REGISTER_CLASSES)
454             && MERGABLE_RELOADS (secondary_type,
455                                  rld[t_reload].when_needed,
456                                  opnum, rld[t_reload].opnum))
457           {
458             if (in_p)
459               rld[t_reload].inmode = t_mode;
460             if (! in_p)
461               rld[t_reload].outmode = t_mode;
462
463             if (reg_class_subset_p (t_class, rld[t_reload].class))
464               rld[t_reload].class = t_class;
465
466             rld[t_reload].opnum = MIN (rld[t_reload].opnum, opnum);
467             rld[t_reload].optional &= optional;
468             rld[t_reload].secondary_p = 1;
469             if (MERGE_TO_OTHER (secondary_type, rld[t_reload].when_needed,
470                                 opnum, rld[t_reload].opnum))
471               rld[t_reload].when_needed = RELOAD_OTHER;
472           }
473
474       if (t_reload == n_reloads)
475         {
476           /* We need to make a new tertiary reload for this register class.  */
477           rld[t_reload].in = rld[t_reload].out = 0;
478           rld[t_reload].class = t_class;
479           rld[t_reload].inmode = in_p ? t_mode : VOIDmode;
480           rld[t_reload].outmode = ! in_p ? t_mode : VOIDmode;
481           rld[t_reload].reg_rtx = 0;
482           rld[t_reload].optional = optional;
483           rld[t_reload].inc = 0;
484           /* Maybe we could combine these, but it seems too tricky.  */
485           rld[t_reload].nocombine = 1;
486           rld[t_reload].in_reg = 0;
487           rld[t_reload].out_reg = 0;
488           rld[t_reload].opnum = opnum;
489           rld[t_reload].when_needed = secondary_type;
490           rld[t_reload].secondary_in_reload = -1;
491           rld[t_reload].secondary_out_reload = -1;
492           rld[t_reload].secondary_in_icode = CODE_FOR_nothing;
493           rld[t_reload].secondary_out_icode = CODE_FOR_nothing;
494           rld[t_reload].secondary_p = 1;
495
496           n_reloads++;
497         }
498     }
499
500   /* See if we can reuse an existing secondary reload.  */
501   for (s_reload = 0; s_reload < n_reloads; s_reload++)
502     if (rld[s_reload].secondary_p
503         && (reg_class_subset_p (class, rld[s_reload].class)
504             || reg_class_subset_p (rld[s_reload].class, class))
505         && ((in_p && rld[s_reload].inmode == mode)
506             || (! in_p && rld[s_reload].outmode == mode))
507         && ((in_p && rld[s_reload].secondary_in_reload == t_reload)
508             || (! in_p && rld[s_reload].secondary_out_reload == t_reload))
509         && ((in_p && rld[s_reload].secondary_in_icode == t_icode)
510             || (! in_p && rld[s_reload].secondary_out_icode == t_icode))
511         && (SMALL_REGISTER_CLASS_P (class) || SMALL_REGISTER_CLASSES)
512         && MERGABLE_RELOADS (secondary_type, rld[s_reload].when_needed,
513                              opnum, rld[s_reload].opnum))
514       {
515         if (in_p)
516           rld[s_reload].inmode = mode;
517         if (! in_p)
518           rld[s_reload].outmode = mode;
519
520         if (reg_class_subset_p (class, rld[s_reload].class))
521           rld[s_reload].class = class;
522
523         rld[s_reload].opnum = MIN (rld[s_reload].opnum, opnum);
524         rld[s_reload].optional &= optional;
525         rld[s_reload].secondary_p = 1;
526         if (MERGE_TO_OTHER (secondary_type, rld[s_reload].when_needed,
527                             opnum, rld[s_reload].opnum))
528           rld[s_reload].when_needed = RELOAD_OTHER;
529       }
530
531   if (s_reload == n_reloads)
532     {
533 #ifdef SECONDARY_MEMORY_NEEDED
534       /* If we need a memory location to copy between the two reload regs,
535          set it up now.  Note that we do the input case before making
536          the reload and the output case after.  This is due to the
537          way reloads are output.  */
538
539       if (in_p && icode == CODE_FOR_nothing
540           && SECONDARY_MEMORY_NEEDED (class, reload_class, mode))
541         {
542           get_secondary_mem (x, reload_mode, opnum, type);
543
544           /* We may have just added new reloads.  Make sure we add
545              the new reload at the end.  */
546           s_reload = n_reloads;
547         }
548 #endif
549
550       /* We need to make a new secondary reload for this register class.  */
551       rld[s_reload].in = rld[s_reload].out = 0;
552       rld[s_reload].class = class;
553
554       rld[s_reload].inmode = in_p ? mode : VOIDmode;
555       rld[s_reload].outmode = ! in_p ? mode : VOIDmode;
556       rld[s_reload].reg_rtx = 0;
557       rld[s_reload].optional = optional;
558       rld[s_reload].inc = 0;
559       /* Maybe we could combine these, but it seems too tricky.  */
560       rld[s_reload].nocombine = 1;
561       rld[s_reload].in_reg = 0;
562       rld[s_reload].out_reg = 0;
563       rld[s_reload].opnum = opnum;
564       rld[s_reload].when_needed = secondary_type;
565       rld[s_reload].secondary_in_reload = in_p ? t_reload : -1;
566       rld[s_reload].secondary_out_reload = ! in_p ? t_reload : -1;
567       rld[s_reload].secondary_in_icode = in_p ? t_icode : CODE_FOR_nothing;
568       rld[s_reload].secondary_out_icode
569         = ! in_p ? t_icode : CODE_FOR_nothing;
570       rld[s_reload].secondary_p = 1;
571
572       n_reloads++;
573
574 #ifdef SECONDARY_MEMORY_NEEDED
575       if (! in_p && icode == CODE_FOR_nothing
576           && SECONDARY_MEMORY_NEEDED (reload_class, class, mode))
577         get_secondary_mem (x, mode, opnum, type);
578 #endif
579     }
580
581   *picode = icode;
582   return s_reload;
583 }
584 #endif /* HAVE_SECONDARY_RELOADS */
585 \f
586 #ifdef SECONDARY_MEMORY_NEEDED
587
588 /* Return a memory location that will be used to copy X in mode MODE.
589    If we haven't already made a location for this mode in this insn,
590    call find_reloads_address on the location being returned.  */
591
592 rtx
593 get_secondary_mem (rtx x ATTRIBUTE_UNUSED, enum machine_mode mode,
594                    int opnum, enum reload_type type)
595 {
596   rtx loc;
597   int mem_valid;
598
599   /* By default, if MODE is narrower than a word, widen it to a word.
600      This is required because most machines that require these memory
601      locations do not support short load and stores from all registers
602      (e.g., FP registers).  */
603
604 #ifdef SECONDARY_MEMORY_NEEDED_MODE
605   mode = SECONDARY_MEMORY_NEEDED_MODE (mode);
606 #else
607   if (GET_MODE_BITSIZE (mode) < BITS_PER_WORD && INTEGRAL_MODE_P (mode))
608     mode = mode_for_size (BITS_PER_WORD, GET_MODE_CLASS (mode), 0);
609 #endif
610
611   /* If we already have made a MEM for this operand in MODE, return it.  */
612   if (secondary_memlocs_elim[(int) mode][opnum] != 0)
613     return secondary_memlocs_elim[(int) mode][opnum];
614
615   /* If this is the first time we've tried to get a MEM for this mode,
616      allocate a new one.  `something_changed' in reload will get set
617      by noticing that the frame size has changed.  */
618
619   if (secondary_memlocs[(int) mode] == 0)
620     {
621 #ifdef SECONDARY_MEMORY_NEEDED_RTX
622       secondary_memlocs[(int) mode] = SECONDARY_MEMORY_NEEDED_RTX (mode);
623 #else
624       secondary_memlocs[(int) mode]
625         = assign_stack_local (mode, GET_MODE_SIZE (mode), 0);
626 #endif
627     }
628
629   /* Get a version of the address doing any eliminations needed.  If that
630      didn't give us a new MEM, make a new one if it isn't valid.  */
631
632   loc = eliminate_regs (secondary_memlocs[(int) mode], VOIDmode, NULL_RTX);
633   mem_valid = strict_memory_address_p (mode, XEXP (loc, 0));
634
635   if (! mem_valid && loc == secondary_memlocs[(int) mode])
636     loc = copy_rtx (loc);
637
638   /* The only time the call below will do anything is if the stack
639      offset is too large.  In that case IND_LEVELS doesn't matter, so we
640      can just pass a zero.  Adjust the type to be the address of the
641      corresponding object.  If the address was valid, save the eliminated
642      address.  If it wasn't valid, we need to make a reload each time, so
643      don't save it.  */
644
645   if (! mem_valid)
646     {
647       type =  (type == RELOAD_FOR_INPUT ? RELOAD_FOR_INPUT_ADDRESS
648                : type == RELOAD_FOR_OUTPUT ? RELOAD_FOR_OUTPUT_ADDRESS
649                : RELOAD_OTHER);
650
651       find_reloads_address (mode, &loc, XEXP (loc, 0), &XEXP (loc, 0),
652                             opnum, type, 0, 0);
653     }
654
655   secondary_memlocs_elim[(int) mode][opnum] = loc;
656   if (secondary_memlocs_elim_used <= (int)mode)
657     secondary_memlocs_elim_used = (int)mode + 1;
658   return loc;
659 }
660
661 /* Clear any secondary memory locations we've made.  */
662
663 void
664 clear_secondary_mem (void)
665 {
666   memset (secondary_memlocs, 0, sizeof secondary_memlocs);
667 }
668 #endif /* SECONDARY_MEMORY_NEEDED */
669 \f
670
671 /* Find the largest class which has at least one register valid in
672    mode INNER, and which for every such register, that register number
673    plus N is also valid in OUTER (if in range) and is cheap to move
674    into REGNO.  Such a class must exist.  */
675
676 static enum reg_class
677 find_valid_class (enum machine_mode outer ATTRIBUTE_UNUSED,
678                   enum machine_mode inner ATTRIBUTE_UNUSED, int n,
679                   unsigned int dest_regno ATTRIBUTE_UNUSED)
680 {
681   int best_cost = -1;
682   int class;
683   int regno;
684   enum reg_class best_class = NO_REGS;
685   enum reg_class dest_class ATTRIBUTE_UNUSED = REGNO_REG_CLASS (dest_regno);
686   unsigned int best_size = 0;
687   int cost;
688
689   for (class = 1; class < N_REG_CLASSES; class++)
690     {
691       int bad = 0;
692       int good = 0;
693       for (regno = 0; regno < FIRST_PSEUDO_REGISTER - n && ! bad; regno++)
694         if (TEST_HARD_REG_BIT (reg_class_contents[class], regno))
695           {
696             if (HARD_REGNO_MODE_OK (regno, inner))
697               {
698                 good = 1;
699                 if (! TEST_HARD_REG_BIT (reg_class_contents[class], regno + n)
700                     || ! HARD_REGNO_MODE_OK (regno + n, outer))
701                   bad = 1;
702               }
703           }
704
705       if (bad || !good)
706         continue;
707       cost = REGISTER_MOVE_COST (outer, class, dest_class);
708
709       if ((reg_class_size[class] > best_size
710            && (best_cost < 0 || best_cost >= cost))
711           || best_cost > cost)
712         {
713           best_class = class;
714           best_size = reg_class_size[class];
715           best_cost = REGISTER_MOVE_COST (outer, class, dest_class);
716         }
717     }
718
719   gcc_assert (best_size != 0);
720
721   return best_class;
722 }
723 \f
724 /* Return the number of a previously made reload that can be combined with
725    a new one, or n_reloads if none of the existing reloads can be used.
726    OUT, CLASS, TYPE and OPNUM are the same arguments as passed to
727    push_reload, they determine the kind of the new reload that we try to
728    combine.  P_IN points to the corresponding value of IN, which can be
729    modified by this function.
730    DONT_SHARE is nonzero if we can't share any input-only reload for IN.  */
731
732 static int
733 find_reusable_reload (rtx *p_in, rtx out, enum reg_class class,
734                       enum reload_type type, int opnum, int dont_share)
735 {
736   rtx in = *p_in;
737   int i;
738   /* We can't merge two reloads if the output of either one is
739      earlyclobbered.  */
740
741   if (earlyclobber_operand_p (out))
742     return n_reloads;
743
744   /* We can use an existing reload if the class is right
745      and at least one of IN and OUT is a match
746      and the other is at worst neutral.
747      (A zero compared against anything is neutral.)
748
749      If SMALL_REGISTER_CLASSES, don't use existing reloads unless they are
750      for the same thing since that can cause us to need more reload registers
751      than we otherwise would.  */
752
753   for (i = 0; i < n_reloads; i++)
754     if ((reg_class_subset_p (class, rld[i].class)
755          || reg_class_subset_p (rld[i].class, class))
756         /* If the existing reload has a register, it must fit our class.  */
757         && (rld[i].reg_rtx == 0
758             || TEST_HARD_REG_BIT (reg_class_contents[(int) class],
759                                   true_regnum (rld[i].reg_rtx)))
760         && ((in != 0 && MATCHES (rld[i].in, in) && ! dont_share
761              && (out == 0 || rld[i].out == 0 || MATCHES (rld[i].out, out)))
762             || (out != 0 && MATCHES (rld[i].out, out)
763                 && (in == 0 || rld[i].in == 0 || MATCHES (rld[i].in, in))))
764         && (rld[i].out == 0 || ! earlyclobber_operand_p (rld[i].out))
765         && (SMALL_REGISTER_CLASS_P (class) || SMALL_REGISTER_CLASSES)
766         && MERGABLE_RELOADS (type, rld[i].when_needed, opnum, rld[i].opnum))
767       return i;
768
769   /* Reloading a plain reg for input can match a reload to postincrement
770      that reg, since the postincrement's value is the right value.
771      Likewise, it can match a preincrement reload, since we regard
772      the preincrementation as happening before any ref in this insn
773      to that register.  */
774   for (i = 0; i < n_reloads; i++)
775     if ((reg_class_subset_p (class, rld[i].class)
776          || reg_class_subset_p (rld[i].class, class))
777         /* If the existing reload has a register, it must fit our
778            class.  */
779         && (rld[i].reg_rtx == 0
780             || TEST_HARD_REG_BIT (reg_class_contents[(int) class],
781                                   true_regnum (rld[i].reg_rtx)))
782         && out == 0 && rld[i].out == 0 && rld[i].in != 0
783         && ((REG_P (in)
784              && GET_RTX_CLASS (GET_CODE (rld[i].in)) == RTX_AUTOINC
785              && MATCHES (XEXP (rld[i].in, 0), in))
786             || (REG_P (rld[i].in)
787                 && GET_RTX_CLASS (GET_CODE (in)) == RTX_AUTOINC
788                 && MATCHES (XEXP (in, 0), rld[i].in)))
789         && (rld[i].out == 0 || ! earlyclobber_operand_p (rld[i].out))
790         && (SMALL_REGISTER_CLASS_P (class) || SMALL_REGISTER_CLASSES)
791         && MERGABLE_RELOADS (type, rld[i].when_needed,
792                              opnum, rld[i].opnum))
793       {
794         /* Make sure reload_in ultimately has the increment,
795            not the plain register.  */
796         if (REG_P (in))
797           *p_in = rld[i].in;
798         return i;
799       }
800   return n_reloads;
801 }
802
803 /* Return nonzero if X is a SUBREG which will require reloading of its
804    SUBREG_REG expression.  */
805
806 static int
807 reload_inner_reg_of_subreg (rtx x, enum machine_mode mode, int output)
808 {
809   rtx inner;
810
811   /* Only SUBREGs are problematical.  */
812   if (GET_CODE (x) != SUBREG)
813     return 0;
814
815   inner = SUBREG_REG (x);
816
817   /* If INNER is a constant or PLUS, then INNER must be reloaded.  */
818   if (CONSTANT_P (inner) || GET_CODE (inner) == PLUS)
819     return 1;
820
821   /* If INNER is not a hard register, then INNER will not need to
822      be reloaded.  */
823   if (!REG_P (inner)
824       || REGNO (inner) >= FIRST_PSEUDO_REGISTER)
825     return 0;
826
827   /* If INNER is not ok for MODE, then INNER will need reloading.  */
828   if (! HARD_REGNO_MODE_OK (subreg_regno (x), mode))
829     return 1;
830
831   /* If the outer part is a word or smaller, INNER larger than a
832      word and the number of regs for INNER is not the same as the
833      number of words in INNER, then INNER will need reloading.  */
834   return (GET_MODE_SIZE (mode) <= UNITS_PER_WORD
835           && output
836           && GET_MODE_SIZE (GET_MODE (inner)) > UNITS_PER_WORD
837           && ((GET_MODE_SIZE (GET_MODE (inner)) / UNITS_PER_WORD)
838               != (int) hard_regno_nregs[REGNO (inner)][GET_MODE (inner)]));
839 }
840
841 /* Return nonzero if IN can be reloaded into REGNO with mode MODE without
842    requiring an extra reload register.  The caller has already found that
843    IN contains some reference to REGNO, so check that we can produce the
844    new value in a single step.  E.g. if we have
845    (set (reg r13) (plus (reg r13) (const int 1))), and there is an
846    instruction that adds one to a register, this should succeed.
847    However, if we have something like
848    (set (reg r13) (plus (reg r13) (const int 999))), and the constant 999
849    needs to be loaded into a register first, we need a separate reload
850    register.
851    Such PLUS reloads are generated by find_reload_address_part.
852    The out-of-range PLUS expressions are usually introduced in the instruction
853    patterns by register elimination and substituting pseudos without a home
854    by their function-invariant equivalences.  */
855 static int
856 can_reload_into (rtx in, int regno, enum machine_mode mode)
857 {
858   rtx dst, test_insn;
859   int r = 0;
860   struct recog_data save_recog_data;
861
862   /* For matching constraints, we often get notional input reloads where
863      we want to use the original register as the reload register.  I.e.
864      technically this is a non-optional input-output reload, but IN is
865      already a valid register, and has been chosen as the reload register.
866      Speed this up, since it trivially works.  */
867   if (REG_P (in))
868     return 1;
869
870   /* To test MEMs properly, we'd have to take into account all the reloads
871      that are already scheduled, which can become quite complicated.
872      And since we've already handled address reloads for this MEM, it
873      should always succeed anyway.  */
874   if (MEM_P (in))
875     return 1;
876
877   /* If we can make a simple SET insn that does the job, everything should
878      be fine.  */
879   dst =  gen_rtx_REG (mode, regno);
880   test_insn = make_insn_raw (gen_rtx_SET (VOIDmode, dst, in));
881   save_recog_data = recog_data;
882   if (recog_memoized (test_insn) >= 0)
883     {
884       extract_insn (test_insn);
885       r = constrain_operands (1);
886     }
887   recog_data = save_recog_data;
888   return r;
889 }
890
891 /* Record one reload that needs to be performed.
892    IN is an rtx saying where the data are to be found before this instruction.
893    OUT says where they must be stored after the instruction.
894    (IN is zero for data not read, and OUT is zero for data not written.)
895    INLOC and OUTLOC point to the places in the instructions where
896    IN and OUT were found.
897    If IN and OUT are both nonzero, it means the same register must be used
898    to reload both IN and OUT.
899
900    CLASS is a register class required for the reloaded data.
901    INMODE is the machine mode that the instruction requires
902    for the reg that replaces IN and OUTMODE is likewise for OUT.
903
904    If IN is zero, then OUT's location and mode should be passed as
905    INLOC and INMODE.
906
907    STRICT_LOW is the 1 if there is a containing STRICT_LOW_PART rtx.
908
909    OPTIONAL nonzero means this reload does not need to be performed:
910    it can be discarded if that is more convenient.
911
912    OPNUM and TYPE say what the purpose of this reload is.
913
914    The return value is the reload-number for this reload.
915
916    If both IN and OUT are nonzero, in some rare cases we might
917    want to make two separate reloads.  (Actually we never do this now.)
918    Therefore, the reload-number for OUT is stored in
919    output_reloadnum when we return; the return value applies to IN.
920    Usually (presently always), when IN and OUT are nonzero,
921    the two reload-numbers are equal, but the caller should be careful to
922    distinguish them.  */
923
924 int
925 push_reload (rtx in, rtx out, rtx *inloc, rtx *outloc,
926              enum reg_class class, enum machine_mode inmode,
927              enum machine_mode outmode, int strict_low, int optional,
928              int opnum, enum reload_type type)
929 {
930   int i;
931   int dont_share = 0;
932   int dont_remove_subreg = 0;
933   rtx *in_subreg_loc = 0, *out_subreg_loc = 0;
934   int secondary_in_reload = -1, secondary_out_reload = -1;
935   enum insn_code secondary_in_icode = CODE_FOR_nothing;
936   enum insn_code secondary_out_icode = CODE_FOR_nothing;
937
938   /* INMODE and/or OUTMODE could be VOIDmode if no mode
939      has been specified for the operand.  In that case,
940      use the operand's mode as the mode to reload.  */
941   if (inmode == VOIDmode && in != 0)
942     inmode = GET_MODE (in);
943   if (outmode == VOIDmode && out != 0)
944     outmode = GET_MODE (out);
945
946   /* If IN is a pseudo register everywhere-equivalent to a constant, and
947      it is not in a hard register, reload straight from the constant,
948      since we want to get rid of such pseudo registers.
949      Often this is done earlier, but not always in find_reloads_address.  */
950   if (in != 0 && REG_P (in))
951     {
952       int regno = REGNO (in);
953
954       if (regno >= FIRST_PSEUDO_REGISTER && reg_renumber[regno] < 0
955           && reg_equiv_constant[regno] != 0)
956         in = reg_equiv_constant[regno];
957     }
958
959   /* Likewise for OUT.  Of course, OUT will never be equivalent to
960      an actual constant, but it might be equivalent to a memory location
961      (in the case of a parameter).  */
962   if (out != 0 && REG_P (out))
963     {
964       int regno = REGNO (out);
965
966       if (regno >= FIRST_PSEUDO_REGISTER && reg_renumber[regno] < 0
967           && reg_equiv_constant[regno] != 0)
968         out = reg_equiv_constant[regno];
969     }
970
971   /* If we have a read-write operand with an address side-effect,
972      change either IN or OUT so the side-effect happens only once.  */
973   if (in != 0 && out != 0 && MEM_P (in) && rtx_equal_p (in, out))
974     switch (GET_CODE (XEXP (in, 0)))
975       {
976       case POST_INC: case POST_DEC:   case POST_MODIFY:
977         in = replace_equiv_address_nv (in, XEXP (XEXP (in, 0), 0));
978         break;
979
980       case PRE_INC: case PRE_DEC: case PRE_MODIFY:
981         out = replace_equiv_address_nv (out, XEXP (XEXP (out, 0), 0));
982         break;
983
984       default:
985         break;
986       }
987
988   /* If we are reloading a (SUBREG constant ...), really reload just the
989      inside expression in its own mode.  Similarly for (SUBREG (PLUS ...)).
990      If we have (SUBREG:M1 (MEM:M2 ...) ...) (or an inner REG that is still
991      a pseudo and hence will become a MEM) with M1 wider than M2 and the
992      register is a pseudo, also reload the inside expression.
993      For machines that extend byte loads, do this for any SUBREG of a pseudo
994      where both M1 and M2 are a word or smaller, M1 is wider than M2, and
995      M2 is an integral mode that gets extended when loaded.
996      Similar issue for (SUBREG:M1 (REG:M2 ...) ...) for a hard register R where
997      either M1 is not valid for R or M2 is wider than a word but we only
998      need one word to store an M2-sized quantity in R.
999      (However, if OUT is nonzero, we need to reload the reg *and*
1000      the subreg, so do nothing here, and let following statement handle it.)
1001
1002      Note that the case of (SUBREG (CONST_INT...)...) is handled elsewhere;
1003      we can't handle it here because CONST_INT does not indicate a mode.
1004
1005      Similarly, we must reload the inside expression if we have a
1006      STRICT_LOW_PART (presumably, in == out in the cas).
1007
1008      Also reload the inner expression if it does not require a secondary
1009      reload but the SUBREG does.
1010
1011      Finally, reload the inner expression if it is a register that is in
1012      the class whose registers cannot be referenced in a different size
1013      and M1 is not the same size as M2.  If subreg_lowpart_p is false, we
1014      cannot reload just the inside since we might end up with the wrong
1015      register class.  But if it is inside a STRICT_LOW_PART, we have
1016      no choice, so we hope we do get the right register class there.  */
1017
1018   if (in != 0 && GET_CODE (in) == SUBREG
1019       && (subreg_lowpart_p (in) || strict_low)
1020 #ifdef CANNOT_CHANGE_MODE_CLASS
1021       && !CANNOT_CHANGE_MODE_CLASS (GET_MODE (SUBREG_REG (in)), inmode, class)
1022 #endif
1023       && (CONSTANT_P (SUBREG_REG (in))
1024           || GET_CODE (SUBREG_REG (in)) == PLUS
1025           || strict_low
1026           || (((REG_P (SUBREG_REG (in))
1027                 && REGNO (SUBREG_REG (in)) >= FIRST_PSEUDO_REGISTER)
1028                || MEM_P (SUBREG_REG (in)))
1029               && ((GET_MODE_SIZE (inmode)
1030                    > GET_MODE_SIZE (GET_MODE (SUBREG_REG (in))))
1031 #ifdef LOAD_EXTEND_OP
1032                   || (GET_MODE_SIZE (inmode) <= UNITS_PER_WORD
1033                       && (GET_MODE_SIZE (GET_MODE (SUBREG_REG (in)))
1034                           <= UNITS_PER_WORD)
1035                       && (GET_MODE_SIZE (inmode)
1036                           > GET_MODE_SIZE (GET_MODE (SUBREG_REG (in))))
1037                       && INTEGRAL_MODE_P (GET_MODE (SUBREG_REG (in)))
1038                       && LOAD_EXTEND_OP (GET_MODE (SUBREG_REG (in))) != UNKNOWN)
1039 #endif
1040 #ifdef WORD_REGISTER_OPERATIONS
1041                   || ((GET_MODE_SIZE (inmode)
1042                        < GET_MODE_SIZE (GET_MODE (SUBREG_REG (in))))
1043                       && ((GET_MODE_SIZE (inmode) - 1) / UNITS_PER_WORD ==
1044                           ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (in))) - 1)
1045                            / UNITS_PER_WORD)))
1046 #endif
1047                   ))
1048           || (REG_P (SUBREG_REG (in))
1049               && REGNO (SUBREG_REG (in)) < FIRST_PSEUDO_REGISTER
1050               /* The case where out is nonzero
1051                  is handled differently in the following statement.  */
1052               && (out == 0 || subreg_lowpart_p (in))
1053               && ((GET_MODE_SIZE (inmode) <= UNITS_PER_WORD
1054                    && (GET_MODE_SIZE (GET_MODE (SUBREG_REG (in)))
1055                        > UNITS_PER_WORD)
1056                    && ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (in)))
1057                         / UNITS_PER_WORD)
1058                        != (int) hard_regno_nregs[REGNO (SUBREG_REG (in))]
1059                                                 [GET_MODE (SUBREG_REG (in))]))
1060                   || ! HARD_REGNO_MODE_OK (subreg_regno (in), inmode)))
1061 #ifdef SECONDARY_INPUT_RELOAD_CLASS
1062           || (SECONDARY_INPUT_RELOAD_CLASS (class, inmode, in) != NO_REGS
1063               && (SECONDARY_INPUT_RELOAD_CLASS (class,
1064                                                 GET_MODE (SUBREG_REG (in)),
1065                                                 SUBREG_REG (in))
1066                   == NO_REGS))
1067 #endif
1068 #ifdef CANNOT_CHANGE_MODE_CLASS
1069           || (REG_P (SUBREG_REG (in))
1070               && REGNO (SUBREG_REG (in)) < FIRST_PSEUDO_REGISTER
1071               && REG_CANNOT_CHANGE_MODE_P
1072               (REGNO (SUBREG_REG (in)), GET_MODE (SUBREG_REG (in)), inmode))
1073 #endif
1074           ))
1075     {
1076       in_subreg_loc = inloc;
1077       inloc = &SUBREG_REG (in);
1078       in = *inloc;
1079 #if ! defined (LOAD_EXTEND_OP) && ! defined (WORD_REGISTER_OPERATIONS)
1080       if (MEM_P (in))
1081         /* This is supposed to happen only for paradoxical subregs made by
1082            combine.c.  (SUBREG (MEM)) isn't supposed to occur other ways.  */
1083         gcc_assert (GET_MODE_SIZE (GET_MODE (in)) <= GET_MODE_SIZE (inmode));
1084 #endif
1085       inmode = GET_MODE (in);
1086     }
1087
1088   /* Similar issue for (SUBREG:M1 (REG:M2 ...) ...) for a hard register R where
1089      either M1 is not valid for R or M2 is wider than a word but we only
1090      need one word to store an M2-sized quantity in R.
1091
1092      However, we must reload the inner reg *as well as* the subreg in
1093      that case.  */
1094
1095   /* Similar issue for (SUBREG constant ...) if it was not handled by the
1096      code above.  This can happen if SUBREG_BYTE != 0.  */
1097
1098   if (in != 0 && reload_inner_reg_of_subreg (in, inmode, 0))
1099     {
1100       enum reg_class in_class = class;
1101
1102       if (REG_P (SUBREG_REG (in)))
1103         in_class
1104           = find_valid_class (inmode, GET_MODE (SUBREG_REG (in)),
1105                               subreg_regno_offset (REGNO (SUBREG_REG (in)),
1106                                                    GET_MODE (SUBREG_REG (in)),
1107                                                    SUBREG_BYTE (in),
1108                                                    GET_MODE (in)),
1109                               REGNO (SUBREG_REG (in)));
1110
1111       /* This relies on the fact that emit_reload_insns outputs the
1112          instructions for input reloads of type RELOAD_OTHER in the same
1113          order as the reloads.  Thus if the outer reload is also of type
1114          RELOAD_OTHER, we are guaranteed that this inner reload will be
1115          output before the outer reload.  */
1116       push_reload (SUBREG_REG (in), NULL_RTX, &SUBREG_REG (in), (rtx *) 0,
1117                    in_class, VOIDmode, VOIDmode, 0, 0, opnum, type);
1118       dont_remove_subreg = 1;
1119     }
1120
1121   /* Similarly for paradoxical and problematical SUBREGs on the output.
1122      Note that there is no reason we need worry about the previous value
1123      of SUBREG_REG (out); even if wider than out,
1124      storing in a subreg is entitled to clobber it all
1125      (except in the case of STRICT_LOW_PART,
1126      and in that case the constraint should label it input-output.)  */
1127   if (out != 0 && GET_CODE (out) == SUBREG
1128       && (subreg_lowpart_p (out) || strict_low)
1129 #ifdef CANNOT_CHANGE_MODE_CLASS
1130       && !CANNOT_CHANGE_MODE_CLASS (GET_MODE (SUBREG_REG (out)), outmode, class)
1131 #endif
1132       && (CONSTANT_P (SUBREG_REG (out))
1133           || strict_low
1134           || (((REG_P (SUBREG_REG (out))
1135                 && REGNO (SUBREG_REG (out)) >= FIRST_PSEUDO_REGISTER)
1136                || MEM_P (SUBREG_REG (out)))
1137               && ((GET_MODE_SIZE (outmode)
1138                    > GET_MODE_SIZE (GET_MODE (SUBREG_REG (out))))
1139 #ifdef WORD_REGISTER_OPERATIONS
1140                   || ((GET_MODE_SIZE (outmode)
1141                        < GET_MODE_SIZE (GET_MODE (SUBREG_REG (out))))
1142                       && ((GET_MODE_SIZE (outmode) - 1) / UNITS_PER_WORD ==
1143                           ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (out))) - 1)
1144                            / UNITS_PER_WORD)))
1145 #endif
1146                   ))
1147           || (REG_P (SUBREG_REG (out))
1148               && REGNO (SUBREG_REG (out)) < FIRST_PSEUDO_REGISTER
1149               && ((GET_MODE_SIZE (outmode) <= UNITS_PER_WORD
1150                    && (GET_MODE_SIZE (GET_MODE (SUBREG_REG (out)))
1151                        > UNITS_PER_WORD)
1152                    && ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (out)))
1153                         / UNITS_PER_WORD)
1154                        != (int) hard_regno_nregs[REGNO (SUBREG_REG (out))]
1155                                                 [GET_MODE (SUBREG_REG (out))]))
1156                   || ! HARD_REGNO_MODE_OK (subreg_regno (out), outmode)))
1157 #ifdef SECONDARY_OUTPUT_RELOAD_CLASS
1158           || (SECONDARY_OUTPUT_RELOAD_CLASS (class, outmode, out) != NO_REGS
1159               && (SECONDARY_OUTPUT_RELOAD_CLASS (class,
1160                                                  GET_MODE (SUBREG_REG (out)),
1161                                                  SUBREG_REG (out))
1162                   == NO_REGS))
1163 #endif
1164 #ifdef CANNOT_CHANGE_MODE_CLASS
1165           || (REG_P (SUBREG_REG (out))
1166               && REGNO (SUBREG_REG (out)) < FIRST_PSEUDO_REGISTER
1167               && REG_CANNOT_CHANGE_MODE_P (REGNO (SUBREG_REG (out)),
1168                                            GET_MODE (SUBREG_REG (out)),
1169                                            outmode))
1170 #endif
1171           ))
1172     {
1173       out_subreg_loc = outloc;
1174       outloc = &SUBREG_REG (out);
1175       out = *outloc;
1176 #if ! defined (LOAD_EXTEND_OP) && ! defined (WORD_REGISTER_OPERATIONS)
1177       gcc_assert (!MEM_P (out)
1178                   || GET_MODE_SIZE (GET_MODE (out))
1179                      <= GET_MODE_SIZE (outmode));
1180 #endif
1181       outmode = GET_MODE (out);
1182     }
1183
1184   /* Similar issue for (SUBREG:M1 (REG:M2 ...) ...) for a hard register R where
1185      either M1 is not valid for R or M2 is wider than a word but we only
1186      need one word to store an M2-sized quantity in R.
1187
1188      However, we must reload the inner reg *as well as* the subreg in
1189      that case.  In this case, the inner reg is an in-out reload.  */
1190
1191   if (out != 0 && reload_inner_reg_of_subreg (out, outmode, 1))
1192     {
1193       /* This relies on the fact that emit_reload_insns outputs the
1194          instructions for output reloads of type RELOAD_OTHER in reverse
1195          order of the reloads.  Thus if the outer reload is also of type
1196          RELOAD_OTHER, we are guaranteed that this inner reload will be
1197          output after the outer reload.  */
1198       dont_remove_subreg = 1;
1199       push_reload (SUBREG_REG (out), SUBREG_REG (out), &SUBREG_REG (out),
1200                    &SUBREG_REG (out),
1201                    find_valid_class (outmode, GET_MODE (SUBREG_REG (out)),
1202                                      subreg_regno_offset (REGNO (SUBREG_REG (out)),
1203                                                           GET_MODE (SUBREG_REG (out)),
1204                                                           SUBREG_BYTE (out),
1205                                                           GET_MODE (out)),
1206                                      REGNO (SUBREG_REG (out))),
1207                    VOIDmode, VOIDmode, 0, 0,
1208                    opnum, RELOAD_OTHER);
1209     }
1210
1211   /* If IN appears in OUT, we can't share any input-only reload for IN.  */
1212   if (in != 0 && out != 0 && MEM_P (out)
1213       && (REG_P (in) || MEM_P (in))
1214       && reg_overlap_mentioned_for_reload_p (in, XEXP (out, 0)))
1215     dont_share = 1;
1216
1217   /* If IN is a SUBREG of a hard register, make a new REG.  This
1218      simplifies some of the cases below.  */
1219
1220   if (in != 0 && GET_CODE (in) == SUBREG && REG_P (SUBREG_REG (in))
1221       && REGNO (SUBREG_REG (in)) < FIRST_PSEUDO_REGISTER
1222       && ! dont_remove_subreg)
1223     in = gen_rtx_REG (GET_MODE (in), subreg_regno (in));
1224
1225   /* Similarly for OUT.  */
1226   if (out != 0 && GET_CODE (out) == SUBREG
1227       && REG_P (SUBREG_REG (out))
1228       && REGNO (SUBREG_REG (out)) < FIRST_PSEUDO_REGISTER
1229       && ! dont_remove_subreg)
1230     out = gen_rtx_REG (GET_MODE (out), subreg_regno (out));
1231
1232   /* Narrow down the class of register wanted if that is
1233      desirable on this machine for efficiency.  */
1234   if (in != 0)
1235     class = PREFERRED_RELOAD_CLASS (in, class);
1236
1237   /* Output reloads may need analogous treatment, different in detail.  */
1238 #ifdef PREFERRED_OUTPUT_RELOAD_CLASS
1239   if (out != 0)
1240     class = PREFERRED_OUTPUT_RELOAD_CLASS (out, class);
1241 #endif
1242
1243   /* Make sure we use a class that can handle the actual pseudo
1244      inside any subreg.  For example, on the 386, QImode regs
1245      can appear within SImode subregs.  Although GENERAL_REGS
1246      can handle SImode, QImode needs a smaller class.  */
1247 #ifdef LIMIT_RELOAD_CLASS
1248   if (in_subreg_loc)
1249     class = LIMIT_RELOAD_CLASS (inmode, class);
1250   else if (in != 0 && GET_CODE (in) == SUBREG)
1251     class = LIMIT_RELOAD_CLASS (GET_MODE (SUBREG_REG (in)), class);
1252
1253   if (out_subreg_loc)
1254     class = LIMIT_RELOAD_CLASS (outmode, class);
1255   if (out != 0 && GET_CODE (out) == SUBREG)
1256     class = LIMIT_RELOAD_CLASS (GET_MODE (SUBREG_REG (out)), class);
1257 #endif
1258
1259   /* Verify that this class is at least possible for the mode that
1260      is specified.  */
1261   if (this_insn_is_asm)
1262     {
1263       enum machine_mode mode;
1264       if (GET_MODE_SIZE (inmode) > GET_MODE_SIZE (outmode))
1265         mode = inmode;
1266       else
1267         mode = outmode;
1268       if (mode == VOIDmode)
1269         {
1270           error_for_asm (this_insn, "cannot reload integer constant "
1271                          "operand in %<asm%>");
1272           mode = word_mode;
1273           if (in != 0)
1274             inmode = word_mode;
1275           if (out != 0)
1276             outmode = word_mode;
1277         }
1278       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1279         if (HARD_REGNO_MODE_OK (i, mode)
1280             && TEST_HARD_REG_BIT (reg_class_contents[(int) class], i))
1281           {
1282             int nregs = hard_regno_nregs[i][mode];
1283
1284             int j;
1285             for (j = 1; j < nregs; j++)
1286               if (! TEST_HARD_REG_BIT (reg_class_contents[(int) class], i + j))
1287                 break;
1288             if (j == nregs)
1289               break;
1290           }
1291       if (i == FIRST_PSEUDO_REGISTER)
1292         {
1293           error_for_asm (this_insn, "impossible register constraint "
1294                          "in %<asm%>");
1295           class = ALL_REGS;
1296         }
1297     }
1298
1299   /* Optional output reloads are always OK even if we have no register class,
1300      since the function of these reloads is only to have spill_reg_store etc.
1301      set, so that the storing insn can be deleted later.  */
1302   gcc_assert (class != NO_REGS
1303               || (optional != 0 && type == RELOAD_FOR_OUTPUT));
1304
1305   i = find_reusable_reload (&in, out, class, type, opnum, dont_share);
1306
1307   if (i == n_reloads)
1308     {
1309       /* See if we need a secondary reload register to move between CLASS
1310          and IN or CLASS and OUT.  Get the icode and push any required reloads
1311          needed for each of them if so.  */
1312
1313 #ifdef SECONDARY_INPUT_RELOAD_CLASS
1314       if (in != 0)
1315         secondary_in_reload
1316           = push_secondary_reload (1, in, opnum, optional, class, inmode, type,
1317                                    &secondary_in_icode);
1318 #endif
1319
1320 #ifdef SECONDARY_OUTPUT_RELOAD_CLASS
1321       if (out != 0 && GET_CODE (out) != SCRATCH)
1322         secondary_out_reload
1323           = push_secondary_reload (0, out, opnum, optional, class, outmode,
1324                                    type, &secondary_out_icode);
1325 #endif
1326
1327       /* We found no existing reload suitable for re-use.
1328          So add an additional reload.  */
1329
1330 #ifdef SECONDARY_MEMORY_NEEDED
1331       /* If a memory location is needed for the copy, make one.  */
1332       if (in != 0 && (REG_P (in) || GET_CODE (in) == SUBREG)
1333           && reg_or_subregno (in) < FIRST_PSEUDO_REGISTER
1334           && SECONDARY_MEMORY_NEEDED (REGNO_REG_CLASS (reg_or_subregno (in)),
1335                                       class, inmode))
1336         get_secondary_mem (in, inmode, opnum, type);
1337 #endif
1338
1339       i = n_reloads;
1340       rld[i].in = in;
1341       rld[i].out = out;
1342       rld[i].class = class;
1343       rld[i].inmode = inmode;
1344       rld[i].outmode = outmode;
1345       rld[i].reg_rtx = 0;
1346       rld[i].optional = optional;
1347       rld[i].inc = 0;
1348       rld[i].nocombine = 0;
1349       rld[i].in_reg = inloc ? *inloc : 0;
1350       rld[i].out_reg = outloc ? *outloc : 0;
1351       rld[i].opnum = opnum;
1352       rld[i].when_needed = type;
1353       rld[i].secondary_in_reload = secondary_in_reload;
1354       rld[i].secondary_out_reload = secondary_out_reload;
1355       rld[i].secondary_in_icode = secondary_in_icode;
1356       rld[i].secondary_out_icode = secondary_out_icode;
1357       rld[i].secondary_p = 0;
1358
1359       n_reloads++;
1360
1361 #ifdef SECONDARY_MEMORY_NEEDED
1362       if (out != 0 && (REG_P (out) || GET_CODE (out) == SUBREG)
1363           && reg_or_subregno (out) < FIRST_PSEUDO_REGISTER
1364           && SECONDARY_MEMORY_NEEDED (class,
1365                                       REGNO_REG_CLASS (reg_or_subregno (out)),
1366                                       outmode))
1367         get_secondary_mem (out, outmode, opnum, type);
1368 #endif
1369     }
1370   else
1371     {
1372       /* We are reusing an existing reload,
1373          but we may have additional information for it.
1374          For example, we may now have both IN and OUT
1375          while the old one may have just one of them.  */
1376
1377       /* The modes can be different.  If they are, we want to reload in
1378          the larger mode, so that the value is valid for both modes.  */
1379       if (inmode != VOIDmode
1380           && GET_MODE_SIZE (inmode) > GET_MODE_SIZE (rld[i].inmode))
1381         rld[i].inmode = inmode;
1382       if (outmode != VOIDmode
1383           && GET_MODE_SIZE (outmode) > GET_MODE_SIZE (rld[i].outmode))
1384         rld[i].outmode = outmode;
1385       if (in != 0)
1386         {
1387           rtx in_reg = inloc ? *inloc : 0;
1388           /* If we merge reloads for two distinct rtl expressions that
1389              are identical in content, there might be duplicate address
1390              reloads.  Remove the extra set now, so that if we later find
1391              that we can inherit this reload, we can get rid of the
1392              address reloads altogether.
1393
1394              Do not do this if both reloads are optional since the result
1395              would be an optional reload which could potentially leave
1396              unresolved address replacements.
1397
1398              It is not sufficient to call transfer_replacements since
1399              choose_reload_regs will remove the replacements for address
1400              reloads of inherited reloads which results in the same
1401              problem.  */
1402           if (rld[i].in != in && rtx_equal_p (in, rld[i].in)
1403               && ! (rld[i].optional && optional))
1404             {
1405               /* We must keep the address reload with the lower operand
1406                  number alive.  */
1407               if (opnum > rld[i].opnum)
1408                 {
1409                   remove_address_replacements (in);
1410                   in = rld[i].in;
1411                   in_reg = rld[i].in_reg;
1412                 }
1413               else
1414                 remove_address_replacements (rld[i].in);
1415             }
1416           rld[i].in = in;
1417           rld[i].in_reg = in_reg;
1418         }
1419       if (out != 0)
1420         {
1421           rld[i].out = out;
1422           rld[i].out_reg = outloc ? *outloc : 0;
1423         }
1424       if (reg_class_subset_p (class, rld[i].class))
1425         rld[i].class = class;
1426       rld[i].optional &= optional;
1427       if (MERGE_TO_OTHER (type, rld[i].when_needed,
1428                           opnum, rld[i].opnum))
1429         rld[i].when_needed = RELOAD_OTHER;
1430       rld[i].opnum = MIN (rld[i].opnum, opnum);
1431     }
1432
1433   /* If the ostensible rtx being reloaded differs from the rtx found
1434      in the location to substitute, this reload is not safe to combine
1435      because we cannot reliably tell whether it appears in the insn.  */
1436
1437   if (in != 0 && in != *inloc)
1438     rld[i].nocombine = 1;
1439
1440 #if 0
1441   /* This was replaced by changes in find_reloads_address_1 and the new
1442      function inc_for_reload, which go with a new meaning of reload_inc.  */
1443
1444   /* If this is an IN/OUT reload in an insn that sets the CC,
1445      it must be for an autoincrement.  It doesn't work to store
1446      the incremented value after the insn because that would clobber the CC.
1447      So we must do the increment of the value reloaded from,
1448      increment it, store it back, then decrement again.  */
1449   if (out != 0 && sets_cc0_p (PATTERN (this_insn)))
1450     {
1451       out = 0;
1452       rld[i].out = 0;
1453       rld[i].inc = find_inc_amount (PATTERN (this_insn), in);
1454       /* If we did not find a nonzero amount-to-increment-by,
1455          that contradicts the belief that IN is being incremented
1456          in an address in this insn.  */
1457       gcc_assert (rld[i].inc != 0);
1458     }
1459 #endif
1460
1461   /* If we will replace IN and OUT with the reload-reg,
1462      record where they are located so that substitution need
1463      not do a tree walk.  */
1464
1465   if (replace_reloads)
1466     {
1467       if (inloc != 0)
1468         {
1469           struct replacement *r = &replacements[n_replacements++];
1470           r->what = i;
1471           r->subreg_loc = in_subreg_loc;
1472           r->where = inloc;
1473           r->mode = inmode;
1474         }
1475       if (outloc != 0 && outloc != inloc)
1476         {
1477           struct replacement *r = &replacements[n_replacements++];
1478           r->what = i;
1479           r->where = outloc;
1480           r->subreg_loc = out_subreg_loc;
1481           r->mode = outmode;
1482         }
1483     }
1484
1485   /* If this reload is just being introduced and it has both
1486      an incoming quantity and an outgoing quantity that are
1487      supposed to be made to match, see if either one of the two
1488      can serve as the place to reload into.
1489
1490      If one of them is acceptable, set rld[i].reg_rtx
1491      to that one.  */
1492
1493   if (in != 0 && out != 0 && in != out && rld[i].reg_rtx == 0)
1494     {
1495       rld[i].reg_rtx = find_dummy_reload (in, out, inloc, outloc,
1496                                           inmode, outmode,
1497                                           rld[i].class, i,
1498                                           earlyclobber_operand_p (out));
1499
1500       /* If the outgoing register already contains the same value
1501          as the incoming one, we can dispense with loading it.
1502          The easiest way to tell the caller that is to give a phony
1503          value for the incoming operand (same as outgoing one).  */
1504       if (rld[i].reg_rtx == out
1505           && (REG_P (in) || CONSTANT_P (in))
1506           && 0 != find_equiv_reg (in, this_insn, 0, REGNO (out),
1507                                   static_reload_reg_p, i, inmode))
1508         rld[i].in = out;
1509     }
1510
1511   /* If this is an input reload and the operand contains a register that
1512      dies in this insn and is used nowhere else, see if it is the right class
1513      to be used for this reload.  Use it if so.  (This occurs most commonly
1514      in the case of paradoxical SUBREGs and in-out reloads).  We cannot do
1515      this if it is also an output reload that mentions the register unless
1516      the output is a SUBREG that clobbers an entire register.
1517
1518      Note that the operand might be one of the spill regs, if it is a
1519      pseudo reg and we are in a block where spilling has not taken place.
1520      But if there is no spilling in this block, that is OK.
1521      An explicitly used hard reg cannot be a spill reg.  */
1522
1523   if (rld[i].reg_rtx == 0 && in != 0 && hard_regs_live_known)
1524     {
1525       rtx note;
1526       int regno;
1527       enum machine_mode rel_mode = inmode;
1528
1529       if (out && GET_MODE_SIZE (outmode) > GET_MODE_SIZE (inmode))
1530         rel_mode = outmode;
1531
1532       for (note = REG_NOTES (this_insn); note; note = XEXP (note, 1))
1533         if (REG_NOTE_KIND (note) == REG_DEAD
1534             && REG_P (XEXP (note, 0))
1535             && (regno = REGNO (XEXP (note, 0))) < FIRST_PSEUDO_REGISTER
1536             && reg_mentioned_p (XEXP (note, 0), in)
1537             /* Check that we don't use a hardreg for an uninitialized
1538                pseudo.  See also find_dummy_reload().  */
1539             && (ORIGINAL_REGNO (XEXP (note, 0)) < FIRST_PSEUDO_REGISTER
1540                 || ! bitmap_bit_p (ENTRY_BLOCK_PTR->global_live_at_end,
1541                                    ORIGINAL_REGNO (XEXP (note, 0))))
1542             && ! refers_to_regno_for_reload_p (regno,
1543                                                (regno
1544                                                 + hard_regno_nregs[regno]
1545                                                                   [rel_mode]),
1546                                                PATTERN (this_insn), inloc)
1547             /* If this is also an output reload, IN cannot be used as
1548                the reload register if it is set in this insn unless IN
1549                is also OUT.  */
1550             && (out == 0 || in == out
1551                 || ! hard_reg_set_here_p (regno,
1552                                           (regno
1553                                            + hard_regno_nregs[regno]
1554                                                              [rel_mode]),
1555                                           PATTERN (this_insn)))
1556             /* ??? Why is this code so different from the previous?
1557                Is there any simple coherent way to describe the two together?
1558                What's going on here.  */
1559             && (in != out
1560                 || (GET_CODE (in) == SUBREG
1561                     && (((GET_MODE_SIZE (GET_MODE (in)) + (UNITS_PER_WORD - 1))
1562                          / UNITS_PER_WORD)
1563                         == ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (in)))
1564                              + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD))))
1565             /* Make sure the operand fits in the reg that dies.  */
1566             && (GET_MODE_SIZE (rel_mode)
1567                 <= GET_MODE_SIZE (GET_MODE (XEXP (note, 0))))
1568             && HARD_REGNO_MODE_OK (regno, inmode)
1569             && HARD_REGNO_MODE_OK (regno, outmode))
1570           {
1571             unsigned int offs;
1572             unsigned int nregs = MAX (hard_regno_nregs[regno][inmode],
1573                                       hard_regno_nregs[regno][outmode]);
1574
1575             for (offs = 0; offs < nregs; offs++)
1576               if (fixed_regs[regno + offs]
1577                   || ! TEST_HARD_REG_BIT (reg_class_contents[(int) class],
1578                                           regno + offs))
1579                 break;
1580
1581             if (offs == nregs
1582                 && (! (refers_to_regno_for_reload_p
1583                        (regno, (regno + hard_regno_nregs[regno][inmode]),
1584                                 in, (rtx *)0))
1585                     || can_reload_into (in, regno, inmode)))
1586               {
1587                 rld[i].reg_rtx = gen_rtx_REG (rel_mode, regno);
1588                 break;
1589               }
1590           }
1591     }
1592
1593   if (out)
1594     output_reloadnum = i;
1595
1596   return i;
1597 }
1598
1599 /* Record an additional place we must replace a value
1600    for which we have already recorded a reload.
1601    RELOADNUM is the value returned by push_reload
1602    when the reload was recorded.
1603    This is used in insn patterns that use match_dup.  */
1604
1605 static void
1606 push_replacement (rtx *loc, int reloadnum, enum machine_mode mode)
1607 {
1608   if (replace_reloads)
1609     {
1610       struct replacement *r = &replacements[n_replacements++];
1611       r->what = reloadnum;
1612       r->where = loc;
1613       r->subreg_loc = 0;
1614       r->mode = mode;
1615     }
1616 }
1617
1618 /* Duplicate any replacement we have recorded to apply at
1619    location ORIG_LOC to also be performed at DUP_LOC.
1620    This is used in insn patterns that use match_dup.  */
1621
1622 static void
1623 dup_replacements (rtx *dup_loc, rtx *orig_loc)
1624 {
1625   int i, n = n_replacements;
1626
1627   for (i = 0; i < n; i++)
1628     {
1629       struct replacement *r = &replacements[i];
1630       if (r->where == orig_loc)
1631         push_replacement (dup_loc, r->what, r->mode);
1632     }
1633 }
1634 \f
1635 /* Transfer all replacements that used to be in reload FROM to be in
1636    reload TO.  */
1637
1638 void
1639 transfer_replacements (int to, int from)
1640 {
1641   int i;
1642
1643   for (i = 0; i < n_replacements; i++)
1644     if (replacements[i].what == from)
1645       replacements[i].what = to;
1646 }
1647 \f
1648 /* IN_RTX is the value loaded by a reload that we now decided to inherit,
1649    or a subpart of it.  If we have any replacements registered for IN_RTX,
1650    cancel the reloads that were supposed to load them.
1651    Return nonzero if we canceled any reloads.  */
1652 int
1653 remove_address_replacements (rtx in_rtx)
1654 {
1655   int i, j;
1656   char reload_flags[MAX_RELOADS];
1657   int something_changed = 0;
1658
1659   memset (reload_flags, 0, sizeof reload_flags);
1660   for (i = 0, j = 0; i < n_replacements; i++)
1661     {
1662       if (loc_mentioned_in_p (replacements[i].where, in_rtx))
1663         reload_flags[replacements[i].what] |= 1;
1664       else
1665         {
1666           replacements[j++] = replacements[i];
1667           reload_flags[replacements[i].what] |= 2;
1668         }
1669     }
1670   /* Note that the following store must be done before the recursive calls.  */
1671   n_replacements = j;
1672
1673   for (i = n_reloads - 1; i >= 0; i--)
1674     {
1675       if (reload_flags[i] == 1)
1676         {
1677           deallocate_reload_reg (i);
1678           remove_address_replacements (rld[i].in);
1679           rld[i].in = 0;
1680           something_changed = 1;
1681         }
1682     }
1683   return something_changed;
1684 }
1685 \f
1686 /* If there is only one output reload, and it is not for an earlyclobber
1687    operand, try to combine it with a (logically unrelated) input reload
1688    to reduce the number of reload registers needed.
1689
1690    This is safe if the input reload does not appear in
1691    the value being output-reloaded, because this implies
1692    it is not needed any more once the original insn completes.
1693
1694    If that doesn't work, see we can use any of the registers that
1695    die in this insn as a reload register.  We can if it is of the right
1696    class and does not appear in the value being output-reloaded.  */
1697
1698 static void
1699 combine_reloads (void)
1700 {
1701   int i;
1702   int output_reload = -1;
1703   int secondary_out = -1;
1704   rtx note;
1705
1706   /* Find the output reload; return unless there is exactly one
1707      and that one is mandatory.  */
1708
1709   for (i = 0; i < n_reloads; i++)
1710     if (rld[i].out != 0)
1711       {
1712         if (output_reload >= 0)
1713           return;
1714         output_reload = i;
1715       }
1716
1717   if (output_reload < 0 || rld[output_reload].optional)
1718     return;
1719
1720   /* An input-output reload isn't combinable.  */
1721
1722   if (rld[output_reload].in != 0)
1723     return;
1724
1725   /* If this reload is for an earlyclobber operand, we can't do anything.  */
1726   if (earlyclobber_operand_p (rld[output_reload].out))
1727     return;
1728
1729   /* If there is a reload for part of the address of this operand, we would
1730      need to chnage it to RELOAD_FOR_OTHER_ADDRESS.  But that would extend
1731      its life to the point where doing this combine would not lower the
1732      number of spill registers needed.  */
1733   for (i = 0; i < n_reloads; i++)
1734     if ((rld[i].when_needed == RELOAD_FOR_OUTPUT_ADDRESS
1735          || rld[i].when_needed == RELOAD_FOR_OUTADDR_ADDRESS)
1736         && rld[i].opnum == rld[output_reload].opnum)
1737       return;
1738
1739   /* Check each input reload; can we combine it?  */
1740
1741   for (i = 0; i < n_reloads; i++)
1742     if (rld[i].in && ! rld[i].optional && ! rld[i].nocombine
1743         /* Life span of this reload must not extend past main insn.  */
1744         && rld[i].when_needed != RELOAD_FOR_OUTPUT_ADDRESS
1745         && rld[i].when_needed != RELOAD_FOR_OUTADDR_ADDRESS
1746         && rld[i].when_needed != RELOAD_OTHER
1747         && (CLASS_MAX_NREGS (rld[i].class, rld[i].inmode)
1748             == CLASS_MAX_NREGS (rld[output_reload].class,
1749                                 rld[output_reload].outmode))
1750         && rld[i].inc == 0
1751         && rld[i].reg_rtx == 0
1752 #ifdef SECONDARY_MEMORY_NEEDED
1753         /* Don't combine two reloads with different secondary
1754            memory locations.  */
1755         && (secondary_memlocs_elim[(int) rld[output_reload].outmode][rld[i].opnum] == 0
1756             || secondary_memlocs_elim[(int) rld[output_reload].outmode][rld[output_reload].opnum] == 0
1757             || rtx_equal_p (secondary_memlocs_elim[(int) rld[output_reload].outmode][rld[i].opnum],
1758                             secondary_memlocs_elim[(int) rld[output_reload].outmode][rld[output_reload].opnum]))
1759 #endif
1760         && (SMALL_REGISTER_CLASSES
1761             ? (rld[i].class == rld[output_reload].class)
1762             : (reg_class_subset_p (rld[i].class,
1763                                    rld[output_reload].class)
1764                || reg_class_subset_p (rld[output_reload].class,
1765                                       rld[i].class)))
1766         && (MATCHES (rld[i].in, rld[output_reload].out)
1767             /* Args reversed because the first arg seems to be
1768                the one that we imagine being modified
1769                while the second is the one that might be affected.  */
1770             || (! reg_overlap_mentioned_for_reload_p (rld[output_reload].out,
1771                                                       rld[i].in)
1772                 /* However, if the input is a register that appears inside
1773                    the output, then we also can't share.
1774                    Imagine (set (mem (reg 69)) (plus (reg 69) ...)).
1775                    If the same reload reg is used for both reg 69 and the
1776                    result to be stored in memory, then that result
1777                    will clobber the address of the memory ref.  */
1778                 && ! (REG_P (rld[i].in)
1779                       && reg_overlap_mentioned_for_reload_p (rld[i].in,
1780                                                              rld[output_reload].out))))
1781         && ! reload_inner_reg_of_subreg (rld[i].in, rld[i].inmode,
1782                                          rld[i].when_needed != RELOAD_FOR_INPUT)
1783         && (reg_class_size[(int) rld[i].class]
1784             || SMALL_REGISTER_CLASSES)
1785         /* We will allow making things slightly worse by combining an
1786            input and an output, but no worse than that.  */
1787         && (rld[i].when_needed == RELOAD_FOR_INPUT
1788             || rld[i].when_needed == RELOAD_FOR_OUTPUT))
1789       {
1790         int j;
1791
1792         /* We have found a reload to combine with!  */
1793         rld[i].out = rld[output_reload].out;
1794         rld[i].out_reg = rld[output_reload].out_reg;
1795         rld[i].outmode = rld[output_reload].outmode;
1796         /* Mark the old output reload as inoperative.  */
1797         rld[output_reload].out = 0;
1798         /* The combined reload is needed for the entire insn.  */
1799         rld[i].when_needed = RELOAD_OTHER;
1800         /* If the output reload had a secondary reload, copy it.  */
1801         if (rld[output_reload].secondary_out_reload != -1)
1802           {
1803             rld[i].secondary_out_reload
1804               = rld[output_reload].secondary_out_reload;
1805             rld[i].secondary_out_icode
1806               = rld[output_reload].secondary_out_icode;
1807           }
1808
1809 #ifdef SECONDARY_MEMORY_NEEDED
1810         /* Copy any secondary MEM.  */
1811         if (secondary_memlocs_elim[(int) rld[output_reload].outmode][rld[output_reload].opnum] != 0)
1812           secondary_memlocs_elim[(int) rld[output_reload].outmode][rld[i].opnum]
1813             = secondary_memlocs_elim[(int) rld[output_reload].outmode][rld[output_reload].opnum];
1814 #endif
1815         /* If required, minimize the register class.  */
1816         if (reg_class_subset_p (rld[output_reload].class,
1817                                 rld[i].class))
1818           rld[i].class = rld[output_reload].class;
1819
1820         /* Transfer all replacements from the old reload to the combined.  */
1821         for (j = 0; j < n_replacements; j++)
1822           if (replacements[j].what == output_reload)
1823             replacements[j].what = i;
1824
1825         return;
1826       }
1827
1828   /* If this insn has only one operand that is modified or written (assumed
1829      to be the first),  it must be the one corresponding to this reload.  It
1830      is safe to use anything that dies in this insn for that output provided
1831      that it does not occur in the output (we already know it isn't an
1832      earlyclobber.  If this is an asm insn, give up.  */
1833
1834   if (INSN_CODE (this_insn) == -1)
1835     return;
1836
1837   for (i = 1; i < insn_data[INSN_CODE (this_insn)].n_operands; i++)
1838     if (insn_data[INSN_CODE (this_insn)].operand[i].constraint[0] == '='
1839         || insn_data[INSN_CODE (this_insn)].operand[i].constraint[0] == '+')
1840       return;
1841
1842   /* See if some hard register that dies in this insn and is not used in
1843      the output is the right class.  Only works if the register we pick
1844      up can fully hold our output reload.  */
1845   for (note = REG_NOTES (this_insn); note; note = XEXP (note, 1))
1846     if (REG_NOTE_KIND (note) == REG_DEAD
1847         && REG_P (XEXP (note, 0))
1848         && ! reg_overlap_mentioned_for_reload_p (XEXP (note, 0),
1849                                                  rld[output_reload].out)
1850         && REGNO (XEXP (note, 0)) < FIRST_PSEUDO_REGISTER
1851         && HARD_REGNO_MODE_OK (REGNO (XEXP (note, 0)), rld[output_reload].outmode)
1852         && TEST_HARD_REG_BIT (reg_class_contents[(int) rld[output_reload].class],
1853                               REGNO (XEXP (note, 0)))
1854         && (hard_regno_nregs[REGNO (XEXP (note, 0))][rld[output_reload].outmode]
1855             <= hard_regno_nregs[REGNO (XEXP (note, 0))][GET_MODE (XEXP (note, 0))])
1856         /* Ensure that a secondary or tertiary reload for this output
1857            won't want this register.  */
1858         && ((secondary_out = rld[output_reload].secondary_out_reload) == -1
1859             || (! (TEST_HARD_REG_BIT
1860                    (reg_class_contents[(int) rld[secondary_out].class],
1861                     REGNO (XEXP (note, 0))))
1862                 && ((secondary_out = rld[secondary_out].secondary_out_reload) == -1
1863                     ||  ! (TEST_HARD_REG_BIT
1864                            (reg_class_contents[(int) rld[secondary_out].class],
1865                             REGNO (XEXP (note, 0)))))))
1866         && ! fixed_regs[REGNO (XEXP (note, 0))])
1867       {
1868         rld[output_reload].reg_rtx
1869           = gen_rtx_REG (rld[output_reload].outmode,
1870                          REGNO (XEXP (note, 0)));
1871         return;
1872       }
1873 }
1874 \f
1875 /* Try to find a reload register for an in-out reload (expressions IN and OUT).
1876    See if one of IN and OUT is a register that may be used;
1877    this is desirable since a spill-register won't be needed.
1878    If so, return the register rtx that proves acceptable.
1879
1880    INLOC and OUTLOC are locations where IN and OUT appear in the insn.
1881    CLASS is the register class required for the reload.
1882
1883    If FOR_REAL is >= 0, it is the number of the reload,
1884    and in some cases when it can be discovered that OUT doesn't need
1885    to be computed, clear out rld[FOR_REAL].out.
1886
1887    If FOR_REAL is -1, this should not be done, because this call
1888    is just to see if a register can be found, not to find and install it.
1889
1890    EARLYCLOBBER is nonzero if OUT is an earlyclobber operand.  This
1891    puts an additional constraint on being able to use IN for OUT since
1892    IN must not appear elsewhere in the insn (it is assumed that IN itself
1893    is safe from the earlyclobber).  */
1894
1895 static rtx
1896 find_dummy_reload (rtx real_in, rtx real_out, rtx *inloc, rtx *outloc,
1897                    enum machine_mode inmode, enum machine_mode outmode,
1898                    enum reg_class class, int for_real, int earlyclobber)
1899 {
1900   rtx in = real_in;
1901   rtx out = real_out;
1902   int in_offset = 0;
1903   int out_offset = 0;
1904   rtx value = 0;
1905
1906   /* If operands exceed a word, we can't use either of them
1907      unless they have the same size.  */
1908   if (GET_MODE_SIZE (outmode) != GET_MODE_SIZE (inmode)
1909       && (GET_MODE_SIZE (outmode) > UNITS_PER_WORD
1910           || GET_MODE_SIZE (inmode) > UNITS_PER_WORD))
1911     return 0;
1912
1913   /* Note that {in,out}_offset are needed only when 'in' or 'out'
1914      respectively refers to a hard register.  */
1915
1916   /* Find the inside of any subregs.  */
1917   while (GET_CODE (out) == SUBREG)
1918     {
1919       if (REG_P (SUBREG_REG (out))
1920           && REGNO (SUBREG_REG (out)) < FIRST_PSEUDO_REGISTER)
1921         out_offset += subreg_regno_offset (REGNO (SUBREG_REG (out)),
1922                                            GET_MODE (SUBREG_REG (out)),
1923                                            SUBREG_BYTE (out),
1924                                            GET_MODE (out));
1925       out = SUBREG_REG (out);
1926     }
1927   while (GET_CODE (in) == SUBREG)
1928     {
1929       if (REG_P (SUBREG_REG (in))
1930           && REGNO (SUBREG_REG (in)) < FIRST_PSEUDO_REGISTER)
1931         in_offset += subreg_regno_offset (REGNO (SUBREG_REG (in)),
1932                                           GET_MODE (SUBREG_REG (in)),
1933                                           SUBREG_BYTE (in),
1934                                           GET_MODE (in));
1935       in = SUBREG_REG (in);
1936     }
1937
1938   /* Narrow down the reg class, the same way push_reload will;
1939      otherwise we might find a dummy now, but push_reload won't.  */
1940   class = PREFERRED_RELOAD_CLASS (in, class);
1941
1942   /* See if OUT will do.  */
1943   if (REG_P (out)
1944       && REGNO (out) < FIRST_PSEUDO_REGISTER)
1945     {
1946       unsigned int regno = REGNO (out) + out_offset;
1947       unsigned int nwords = hard_regno_nregs[regno][outmode];
1948       rtx saved_rtx;
1949
1950       /* When we consider whether the insn uses OUT,
1951          ignore references within IN.  They don't prevent us
1952          from copying IN into OUT, because those refs would
1953          move into the insn that reloads IN.
1954
1955          However, we only ignore IN in its role as this reload.
1956          If the insn uses IN elsewhere and it contains OUT,
1957          that counts.  We can't be sure it's the "same" operand
1958          so it might not go through this reload.  */
1959       saved_rtx = *inloc;
1960       *inloc = const0_rtx;
1961
1962       if (regno < FIRST_PSEUDO_REGISTER
1963           && HARD_REGNO_MODE_OK (regno, outmode)
1964           && ! refers_to_regno_for_reload_p (regno, regno + nwords,
1965                                              PATTERN (this_insn), outloc))
1966         {
1967           unsigned int i;
1968
1969           for (i = 0; i < nwords; i++)
1970             if (! TEST_HARD_REG_BIT (reg_class_contents[(int) class],
1971                                      regno + i))
1972               break;
1973
1974           if (i == nwords)
1975             {
1976               if (REG_P (real_out))
1977                 value = real_out;
1978               else
1979                 value = gen_rtx_REG (outmode, regno);
1980             }
1981         }
1982
1983       *inloc = saved_rtx;
1984     }
1985
1986   /* Consider using IN if OUT was not acceptable
1987      or if OUT dies in this insn (like the quotient in a divmod insn).
1988      We can't use IN unless it is dies in this insn,
1989      which means we must know accurately which hard regs are live.
1990      Also, the result can't go in IN if IN is used within OUT,
1991      or if OUT is an earlyclobber and IN appears elsewhere in the insn.  */
1992   if (hard_regs_live_known
1993       && REG_P (in)
1994       && REGNO (in) < FIRST_PSEUDO_REGISTER
1995       && (value == 0
1996           || find_reg_note (this_insn, REG_UNUSED, real_out))
1997       && find_reg_note (this_insn, REG_DEAD, real_in)
1998       && !fixed_regs[REGNO (in)]
1999       && HARD_REGNO_MODE_OK (REGNO (in),
2000                              /* The only case where out and real_out might
2001                                 have different modes is where real_out
2002                                 is a subreg, and in that case, out
2003                                 has a real mode.  */
2004                              (GET_MODE (out) != VOIDmode
2005                               ? GET_MODE (out) : outmode))
2006         /* But only do all this if we can be sure, that this input
2007            operand doesn't correspond with an uninitialized pseudoreg.
2008            global can assign some hardreg to it, which is the same as
2009            a different pseudo also currently live (as it can ignore the
2010            conflict).  So we never must introduce writes to such hardregs,
2011            as they would clobber the other live pseudo using the same.
2012            See also PR20973.  */
2013       && (ORIGINAL_REGNO (in) < FIRST_PSEUDO_REGISTER
2014           || ! bitmap_bit_p (ENTRY_BLOCK_PTR->global_live_at_end,
2015                              ORIGINAL_REGNO (in))))
2016     {
2017       unsigned int regno = REGNO (in) + in_offset;
2018       unsigned int nwords = hard_regno_nregs[regno][inmode];
2019
2020       if (! refers_to_regno_for_reload_p (regno, regno + nwords, out, (rtx*) 0)
2021           && ! hard_reg_set_here_p (regno, regno + nwords,
2022                                     PATTERN (this_insn))
2023           && (! earlyclobber
2024               || ! refers_to_regno_for_reload_p (regno, regno + nwords,
2025                                                  PATTERN (this_insn), inloc)))
2026         {
2027           unsigned int i;
2028
2029           for (i = 0; i < nwords; i++)
2030             if (! TEST_HARD_REG_BIT (reg_class_contents[(int) class],
2031                                      regno + i))
2032               break;
2033
2034           if (i == nwords)
2035             {
2036               /* If we were going to use OUT as the reload reg
2037                  and changed our mind, it means OUT is a dummy that
2038                  dies here.  So don't bother copying value to it.  */
2039               if (for_real >= 0 && value == real_out)
2040                 rld[for_real].out = 0;
2041               if (REG_P (real_in))
2042                 value = real_in;
2043               else
2044                 value = gen_rtx_REG (inmode, regno);
2045             }
2046         }
2047     }
2048
2049   return value;
2050 }
2051 \f
2052 /* This page contains subroutines used mainly for determining
2053    whether the IN or an OUT of a reload can serve as the
2054    reload register.  */
2055
2056 /* Return 1 if X is an operand of an insn that is being earlyclobbered.  */
2057
2058 int
2059 earlyclobber_operand_p (rtx x)
2060 {
2061   int i;
2062
2063   for (i = 0; i < n_earlyclobbers; i++)
2064     if (reload_earlyclobbers[i] == x)
2065       return 1;
2066
2067   return 0;
2068 }
2069
2070 /* Return 1 if expression X alters a hard reg in the range
2071    from BEG_REGNO (inclusive) to END_REGNO (exclusive),
2072    either explicitly or in the guise of a pseudo-reg allocated to REGNO.
2073    X should be the body of an instruction.  */
2074
2075 static int
2076 hard_reg_set_here_p (unsigned int beg_regno, unsigned int end_regno, rtx x)
2077 {
2078   if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
2079     {
2080       rtx op0 = SET_DEST (x);
2081
2082       while (GET_CODE (op0) == SUBREG)
2083         op0 = SUBREG_REG (op0);
2084       if (REG_P (op0))
2085         {
2086           unsigned int r = REGNO (op0);
2087
2088           /* See if this reg overlaps range under consideration.  */
2089           if (r < end_regno
2090               && r + hard_regno_nregs[r][GET_MODE (op0)] > beg_regno)
2091             return 1;
2092         }
2093     }
2094   else if (GET_CODE (x) == PARALLEL)
2095     {
2096       int i = XVECLEN (x, 0) - 1;
2097
2098       for (; i >= 0; i--)
2099         if (hard_reg_set_here_p (beg_regno, end_regno, XVECEXP (x, 0, i)))
2100           return 1;
2101     }
2102
2103   return 0;
2104 }
2105
2106 /* Return 1 if ADDR is a valid memory address for mode MODE,
2107    and check that each pseudo reg has the proper kind of
2108    hard reg.  */
2109
2110 int
2111 strict_memory_address_p (enum machine_mode mode ATTRIBUTE_UNUSED, rtx addr)
2112 {
2113   GO_IF_LEGITIMATE_ADDRESS (mode, addr, win);
2114   return 0;
2115
2116  win:
2117   return 1;
2118 }
2119 \f
2120 /* Like rtx_equal_p except that it allows a REG and a SUBREG to match
2121    if they are the same hard reg, and has special hacks for
2122    autoincrement and autodecrement.
2123    This is specifically intended for find_reloads to use
2124    in determining whether two operands match.
2125    X is the operand whose number is the lower of the two.
2126
2127    The value is 2 if Y contains a pre-increment that matches
2128    a non-incrementing address in X.  */
2129
2130 /* ??? To be completely correct, we should arrange to pass
2131    for X the output operand and for Y the input operand.
2132    For now, we assume that the output operand has the lower number
2133    because that is natural in (SET output (... input ...)).  */
2134
2135 int
2136 operands_match_p (rtx x, rtx y)
2137 {
2138   int i;
2139   RTX_CODE code = GET_CODE (x);
2140   const char *fmt;
2141   int success_2;
2142
2143   if (x == y)
2144     return 1;
2145   if ((code == REG || (code == SUBREG && REG_P (SUBREG_REG (x))))
2146       && (REG_P (y) || (GET_CODE (y) == SUBREG
2147                                   && REG_P (SUBREG_REG (y)))))
2148     {
2149       int j;
2150
2151       if (code == SUBREG)
2152         {
2153           i = REGNO (SUBREG_REG (x));
2154           if (i >= FIRST_PSEUDO_REGISTER)
2155             goto slow;
2156           i += subreg_regno_offset (REGNO (SUBREG_REG (x)),
2157                                     GET_MODE (SUBREG_REG (x)),
2158                                     SUBREG_BYTE (x),
2159                                     GET_MODE (x));
2160         }
2161       else
2162         i = REGNO (x);
2163
2164       if (GET_CODE (y) == SUBREG)
2165         {
2166           j = REGNO (SUBREG_REG (y));
2167           if (j >= FIRST_PSEUDO_REGISTER)
2168             goto slow;
2169           j += subreg_regno_offset (REGNO (SUBREG_REG (y)),
2170                                     GET_MODE (SUBREG_REG (y)),
2171                                     SUBREG_BYTE (y),
2172                                     GET_MODE (y));
2173         }
2174       else
2175         j = REGNO (y);
2176
2177       /* On a WORDS_BIG_ENDIAN machine, point to the last register of a
2178          multiple hard register group of scalar integer registers, so that
2179          for example (reg:DI 0) and (reg:SI 1) will be considered the same
2180          register.  */
2181       if (WORDS_BIG_ENDIAN && GET_MODE_SIZE (GET_MODE (x)) > UNITS_PER_WORD
2182           && SCALAR_INT_MODE_P (GET_MODE (x))
2183           && i < FIRST_PSEUDO_REGISTER)
2184         i += hard_regno_nregs[i][GET_MODE (x)] - 1;
2185       if (WORDS_BIG_ENDIAN && GET_MODE_SIZE (GET_MODE (y)) > UNITS_PER_WORD
2186           && SCALAR_INT_MODE_P (GET_MODE (y))
2187           && j < FIRST_PSEUDO_REGISTER)
2188         j += hard_regno_nregs[j][GET_MODE (y)] - 1;
2189
2190       return i == j;
2191     }
2192   /* If two operands must match, because they are really a single
2193      operand of an assembler insn, then two postincrements are invalid
2194      because the assembler insn would increment only once.
2195      On the other hand, a postincrement matches ordinary indexing
2196      if the postincrement is the output operand.  */
2197   if (code == POST_DEC || code == POST_INC || code == POST_MODIFY)
2198     return operands_match_p (XEXP (x, 0), y);
2199   /* Two preincrements are invalid
2200      because the assembler insn would increment only once.
2201      On the other hand, a preincrement matches ordinary indexing
2202      if the preincrement is the input operand.
2203      In this case, return 2, since some callers need to do special
2204      things when this happens.  */
2205   if (GET_CODE (y) == PRE_DEC || GET_CODE (y) == PRE_INC
2206       || GET_CODE (y) == PRE_MODIFY)
2207     return operands_match_p (x, XEXP (y, 0)) ? 2 : 0;
2208
2209  slow:
2210
2211   /* Now we have disposed of all the cases
2212      in which different rtx codes can match.  */
2213   if (code != GET_CODE (y))
2214     return 0;
2215   if (code == LABEL_REF)
2216     return XEXP (x, 0) == XEXP (y, 0);
2217   if (code == SYMBOL_REF)
2218     return XSTR (x, 0) == XSTR (y, 0);
2219
2220   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.  */
2221
2222   if (GET_MODE (x) != GET_MODE (y))
2223     return 0;
2224
2225   /* Compare the elements.  If any pair of corresponding elements
2226      fail to match, return 0 for the whole things.  */
2227
2228   success_2 = 0;
2229   fmt = GET_RTX_FORMAT (code);
2230   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2231     {
2232       int val, j;
2233       switch (fmt[i])
2234         {
2235         case 'w':
2236           if (XWINT (x, i) != XWINT (y, i))
2237             return 0;
2238           break;
2239
2240         case 'i':
2241           if (XINT (x, i) != XINT (y, i))
2242             return 0;
2243           break;
2244
2245         case 'e':
2246           val = operands_match_p (XEXP (x, i), XEXP (y, i));
2247           if (val == 0)
2248             return 0;
2249           /* If any subexpression returns 2,
2250              we should return 2 if we are successful.  */
2251           if (val == 2)
2252             success_2 = 1;
2253           break;
2254
2255         case '0':
2256           break;
2257
2258         case 'E':
2259           if (XVECLEN (x, i) != XVECLEN (y, i))
2260             return 0;
2261           for (j = XVECLEN (x, i) - 1; j >= 0; --j)
2262             {
2263               val = operands_match_p (XVECEXP (x, i, j), XVECEXP (y, i, j));
2264               if (val == 0)
2265                 return 0;
2266               if (val == 2)
2267                 success_2 = 1;
2268             }
2269           break;
2270
2271           /* It is believed that rtx's at this level will never
2272              contain anything but integers and other rtx's,
2273              except for within LABEL_REFs and SYMBOL_REFs.  */
2274         default:
2275           gcc_unreachable ();
2276         }
2277     }
2278   return 1 + success_2;
2279 }
2280 \f
2281 /* Describe the range of registers or memory referenced by X.
2282    If X is a register, set REG_FLAG and put the first register
2283    number into START and the last plus one into END.
2284    If X is a memory reference, put a base address into BASE
2285    and a range of integer offsets into START and END.
2286    If X is pushing on the stack, we can assume it causes no trouble,
2287    so we set the SAFE field.  */
2288
2289 static struct decomposition
2290 decompose (rtx x)
2291 {
2292   struct decomposition val;
2293   int all_const = 0;
2294
2295   memset (&val, 0, sizeof (val));
2296
2297   switch (GET_CODE (x))
2298     {
2299     case MEM:
2300       {
2301         rtx base = NULL_RTX, offset = 0;
2302         rtx addr = XEXP (x, 0);
2303         
2304         if (GET_CODE (addr) == PRE_DEC || GET_CODE (addr) == PRE_INC
2305             || GET_CODE (addr) == POST_DEC || GET_CODE (addr) == POST_INC)
2306           {
2307             val.base = XEXP (addr, 0);
2308             val.start = -GET_MODE_SIZE (GET_MODE (x));
2309             val.end = GET_MODE_SIZE (GET_MODE (x));
2310             val.safe = REGNO (val.base) == STACK_POINTER_REGNUM;
2311             return val;
2312           }
2313         
2314         if (GET_CODE (addr) == PRE_MODIFY || GET_CODE (addr) == POST_MODIFY)
2315           {
2316             if (GET_CODE (XEXP (addr, 1)) == PLUS
2317                 && XEXP (addr, 0) == XEXP (XEXP (addr, 1), 0)
2318                 && CONSTANT_P (XEXP (XEXP (addr, 1), 1)))
2319               {
2320                 val.base  = XEXP (addr, 0);
2321                 val.start = -INTVAL (XEXP (XEXP (addr, 1), 1));
2322                 val.end   = INTVAL (XEXP (XEXP (addr, 1), 1));
2323                 val.safe  = REGNO (val.base) == STACK_POINTER_REGNUM;
2324                 return val;
2325               }
2326           }
2327         
2328         if (GET_CODE (addr) == CONST)
2329           {
2330             addr = XEXP (addr, 0);
2331             all_const = 1;
2332           }
2333         if (GET_CODE (addr) == PLUS)
2334           {
2335             if (CONSTANT_P (XEXP (addr, 0)))
2336               {
2337                 base = XEXP (addr, 1);
2338                 offset = XEXP (addr, 0);
2339               }
2340             else if (CONSTANT_P (XEXP (addr, 1)))
2341               {
2342                 base = XEXP (addr, 0);
2343                 offset = XEXP (addr, 1);
2344               }
2345           }
2346         
2347         if (offset == 0)
2348           {
2349             base = addr;
2350             offset = const0_rtx;
2351           }
2352         if (GET_CODE (offset) == CONST)
2353           offset = XEXP (offset, 0);
2354         if (GET_CODE (offset) == PLUS)
2355           {
2356             if (GET_CODE (XEXP (offset, 0)) == CONST_INT)
2357               {
2358                 base = gen_rtx_PLUS (GET_MODE (base), base, XEXP (offset, 1));
2359                 offset = XEXP (offset, 0);
2360               }
2361             else if (GET_CODE (XEXP (offset, 1)) == CONST_INT)
2362               {
2363                 base = gen_rtx_PLUS (GET_MODE (base), base, XEXP (offset, 0));
2364                 offset = XEXP (offset, 1);
2365               }
2366             else
2367               {
2368                 base = gen_rtx_PLUS (GET_MODE (base), base, offset);
2369                 offset = const0_rtx;
2370               }
2371           }
2372         else if (GET_CODE (offset) != CONST_INT)
2373           {
2374             base = gen_rtx_PLUS (GET_MODE (base), base, offset);
2375             offset = const0_rtx;
2376           }
2377         
2378         if (all_const && GET_CODE (base) == PLUS)
2379           base = gen_rtx_CONST (GET_MODE (base), base);
2380         
2381         gcc_assert (GET_CODE (offset) == CONST_INT);
2382         
2383         val.start = INTVAL (offset);
2384         val.end = val.start + GET_MODE_SIZE (GET_MODE (x));
2385         val.base = base;
2386       }
2387       break;
2388       
2389     case REG:
2390       val.reg_flag = 1;
2391       val.start = true_regnum (x);
2392       if (val.start < 0)
2393         {
2394           /* A pseudo with no hard reg.  */
2395           val.start = REGNO (x);
2396           val.end = val.start + 1;
2397         }
2398       else
2399         /* A hard reg.  */
2400         val.end = val.start + hard_regno_nregs[val.start][GET_MODE (x)];
2401       break;
2402
2403     case SUBREG:
2404       if (!REG_P (SUBREG_REG (x)))
2405         /* This could be more precise, but it's good enough.  */
2406         return decompose (SUBREG_REG (x));
2407       val.reg_flag = 1;
2408       val.start = true_regnum (x);
2409       if (val.start < 0)
2410         return decompose (SUBREG_REG (x));
2411       else
2412         /* A hard reg.  */
2413         val.end = val.start + hard_regno_nregs[val.start][GET_MODE (x)];
2414       break;
2415
2416     case SCRATCH:
2417       /* This hasn't been assigned yet, so it can't conflict yet.  */
2418       val.safe = 1;
2419       break;
2420
2421     default:
2422       gcc_assert (CONSTANT_P (x));
2423       val.safe = 1;
2424       break;
2425     }
2426   return val;
2427 }
2428
2429 /* Return 1 if altering Y will not modify the value of X.
2430    Y is also described by YDATA, which should be decompose (Y).  */
2431
2432 static int
2433 immune_p (rtx x, rtx y, struct decomposition ydata)
2434 {
2435   struct decomposition xdata;
2436
2437   if (ydata.reg_flag)
2438     return !refers_to_regno_for_reload_p (ydata.start, ydata.end, x, (rtx*) 0);
2439   if (ydata.safe)
2440     return 1;
2441
2442   gcc_assert (MEM_P (y));
2443   /* If Y is memory and X is not, Y can't affect X.  */
2444   if (!MEM_P (x))
2445     return 1;
2446
2447   xdata = decompose (x);
2448
2449   if (! rtx_equal_p (xdata.base, ydata.base))
2450     {
2451       /* If bases are distinct symbolic constants, there is no overlap.  */
2452       if (CONSTANT_P (xdata.base) && CONSTANT_P (ydata.base))
2453         return 1;
2454       /* Constants and stack slots never overlap.  */
2455       if (CONSTANT_P (xdata.base)
2456           && (ydata.base == frame_pointer_rtx
2457               || ydata.base == hard_frame_pointer_rtx
2458               || ydata.base == stack_pointer_rtx))
2459         return 1;
2460       if (CONSTANT_P (ydata.base)
2461           && (xdata.base == frame_pointer_rtx
2462               || xdata.base == hard_frame_pointer_rtx
2463               || xdata.base == stack_pointer_rtx))
2464         return 1;
2465       /* If either base is variable, we don't know anything.  */
2466       return 0;
2467     }
2468
2469   return (xdata.start >= ydata.end || ydata.start >= xdata.end);
2470 }
2471
2472 /* Similar, but calls decompose.  */
2473
2474 int
2475 safe_from_earlyclobber (rtx op, rtx clobber)
2476 {
2477   struct decomposition early_data;
2478
2479   early_data = decompose (clobber);
2480   return immune_p (op, clobber, early_data);
2481 }
2482 \f
2483 /* Main entry point of this file: search the body of INSN
2484    for values that need reloading and record them with push_reload.
2485    REPLACE nonzero means record also where the values occur
2486    so that subst_reloads can be used.
2487
2488    IND_LEVELS says how many levels of indirection are supported by this
2489    machine; a value of zero means that a memory reference is not a valid
2490    memory address.
2491
2492    LIVE_KNOWN says we have valid information about which hard
2493    regs are live at each point in the program; this is true when
2494    we are called from global_alloc but false when stupid register
2495    allocation has been done.
2496
2497    RELOAD_REG_P if nonzero is a vector indexed by hard reg number
2498    which is nonnegative if the reg has been commandeered for reloading into.
2499    It is copied into STATIC_RELOAD_REG_P and referenced from there
2500    by various subroutines.
2501
2502    Return TRUE if some operands need to be changed, because of swapping
2503    commutative operands, reg_equiv_address substitution, or whatever.  */
2504
2505 int
2506 find_reloads (rtx insn, int replace, int ind_levels, int live_known,
2507               short *reload_reg_p)
2508 {
2509   int insn_code_number;
2510   int i, j;
2511   int noperands;
2512   /* These start out as the constraints for the insn
2513      and they are chewed up as we consider alternatives.  */
2514   char *constraints[MAX_RECOG_OPERANDS];
2515   /* These are the preferred classes for an operand, or NO_REGS if it isn't
2516      a register.  */
2517   enum reg_class preferred_class[MAX_RECOG_OPERANDS];
2518   char pref_or_nothing[MAX_RECOG_OPERANDS];
2519   /* Nonzero for a MEM operand whose entire address needs a reload. 
2520      May be -1 to indicate the entire address may or may not need a reload.  */
2521   int address_reloaded[MAX_RECOG_OPERANDS];
2522   /* Nonzero for an address operand that needs to be completely reloaded.
2523      May be -1 to indicate the entire operand may or may not need a reload.  */
2524   int address_operand_reloaded[MAX_RECOG_OPERANDS];
2525   /* Value of enum reload_type to use for operand.  */
2526   enum reload_type operand_type[MAX_RECOG_OPERANDS];
2527   /* Value of enum reload_type to use within address of operand.  */
2528   enum reload_type address_type[MAX_RECOG_OPERANDS];
2529   /* Save the usage of each operand.  */
2530   enum reload_usage { RELOAD_READ, RELOAD_READ_WRITE, RELOAD_WRITE } modified[MAX_RECOG_OPERANDS];
2531   int no_input_reloads = 0, no_output_reloads = 0;
2532   int n_alternatives;
2533   int this_alternative[MAX_RECOG_OPERANDS];
2534   char this_alternative_match_win[MAX_RECOG_OPERANDS];
2535   char this_alternative_win[MAX_RECOG_OPERANDS];
2536   char this_alternative_offmemok[MAX_RECOG_OPERANDS];
2537   char this_alternative_earlyclobber[MAX_RECOG_OPERANDS];
2538   int this_alternative_matches[MAX_RECOG_OPERANDS];
2539   int swapped;
2540   int goal_alternative[MAX_RECOG_OPERANDS];
2541   int this_alternative_number;
2542   int goal_alternative_number = 0;
2543   int operand_reloadnum[MAX_RECOG_OPERANDS];
2544   int goal_alternative_matches[MAX_RECOG_OPERANDS];
2545   int goal_alternative_matched[MAX_RECOG_OPERANDS];
2546   char goal_alternative_match_win[MAX_RECOG_OPERANDS];
2547   char goal_alternative_win[MAX_RECOG_OPERANDS];
2548   char goal_alternative_offmemok[MAX_RECOG_OPERANDS];
2549   char goal_alternative_earlyclobber[MAX_RECOG_OPERANDS];
2550   int goal_alternative_swapped;
2551   int best;
2552   int commutative;
2553   char operands_match[MAX_RECOG_OPERANDS][MAX_RECOG_OPERANDS];
2554   rtx substed_operand[MAX_RECOG_OPERANDS];
2555   rtx body = PATTERN (insn);
2556   rtx set = single_set (insn);
2557   int goal_earlyclobber = 0, this_earlyclobber;
2558   enum machine_mode operand_mode[MAX_RECOG_OPERANDS];
2559   int retval = 0;
2560
2561   this_insn = insn;
2562   n_reloads = 0;
2563   n_replacements = 0;
2564   n_earlyclobbers = 0;
2565   replace_reloads = replace;
2566   hard_regs_live_known = live_known;
2567   static_reload_reg_p = reload_reg_p;
2568
2569   /* JUMP_INSNs and CALL_INSNs are not allowed to have any output reloads;
2570      neither are insns that SET cc0.  Insns that use CC0 are not allowed
2571      to have any input reloads.  */
2572   if (JUMP_P (insn) || CALL_P (insn))
2573     no_output_reloads = 1;
2574
2575 #ifdef HAVE_cc0
2576   if (reg_referenced_p (cc0_rtx, PATTERN (insn)))
2577     no_input_reloads = 1;
2578   if (reg_set_p (cc0_rtx, PATTERN (insn)))
2579     no_output_reloads = 1;
2580 #endif
2581
2582 #ifdef SECONDARY_MEMORY_NEEDED
2583   /* The eliminated forms of any secondary memory locations are per-insn, so
2584      clear them out here.  */
2585
2586   if (secondary_memlocs_elim_used)
2587     {
2588       memset (secondary_memlocs_elim, 0,
2589               sizeof (secondary_memlocs_elim[0]) * secondary_memlocs_elim_used);
2590       secondary_memlocs_elim_used = 0;
2591     }
2592 #endif
2593
2594   /* Dispose quickly of (set (reg..) (reg..)) if both have hard regs and it
2595      is cheap to move between them.  If it is not, there may not be an insn
2596      to do the copy, so we may need a reload.  */
2597   if (GET_CODE (body) == SET
2598       && REG_P (SET_DEST (body))
2599       && REGNO (SET_DEST (body)) < FIRST_PSEUDO_REGISTER
2600       && REG_P (SET_SRC (body))
2601       && REGNO (SET_SRC (body)) < FIRST_PSEUDO_REGISTER
2602       && REGISTER_MOVE_COST (GET_MODE (SET_SRC (body)),
2603                              REGNO_REG_CLASS (REGNO (SET_SRC (body))),
2604                              REGNO_REG_CLASS (REGNO (SET_DEST (body)))) == 2)
2605     return 0;
2606
2607   extract_insn (insn);
2608
2609   noperands = reload_n_operands = recog_data.n_operands;
2610   n_alternatives = recog_data.n_alternatives;
2611
2612   /* Just return "no reloads" if insn has no operands with constraints.  */
2613   if (noperands == 0 || n_alternatives == 0)
2614     return 0;
2615
2616   insn_code_number = INSN_CODE (insn);
2617   this_insn_is_asm = insn_code_number < 0;
2618
2619   memcpy (operand_mode, recog_data.operand_mode,
2620           noperands * sizeof (enum machine_mode));
2621   memcpy (constraints, recog_data.constraints, noperands * sizeof (char *));
2622
2623   commutative = -1;
2624
2625   /* If we will need to know, later, whether some pair of operands
2626      are the same, we must compare them now and save the result.
2627      Reloading the base and index registers will clobber them
2628      and afterward they will fail to match.  */
2629
2630   for (i = 0; i < noperands; i++)
2631     {
2632       char *p;
2633       int c;
2634
2635       substed_operand[i] = recog_data.operand[i];
2636       p = constraints[i];
2637
2638       modified[i] = RELOAD_READ;
2639
2640       /* Scan this operand's constraint to see if it is an output operand,
2641          an in-out operand, is commutative, or should match another.  */
2642
2643       while ((c = *p))
2644         {
2645           p += CONSTRAINT_LEN (c, p);
2646           switch (c)
2647             {
2648             case '=':
2649               modified[i] = RELOAD_WRITE;
2650               break;
2651             case '+':
2652               modified[i] = RELOAD_READ_WRITE;
2653               break;
2654             case '%':
2655               {
2656                 /* The last operand should not be marked commutative.  */
2657                 gcc_assert (i != noperands - 1);
2658
2659                 /* We currently only support one commutative pair of
2660                    operands.  Some existing asm code currently uses more
2661                    than one pair.  Previously, that would usually work,
2662                    but sometimes it would crash the compiler.  We
2663                    continue supporting that case as well as we can by
2664                    silently ignoring all but the first pair.  In the
2665                    future we may handle it correctly.  */
2666                 if (commutative < 0)
2667                   commutative = i;
2668                 else
2669                   gcc_assert (this_insn_is_asm);
2670               }
2671               break;
2672             /* Use of ISDIGIT is tempting here, but it may get expensive because
2673                of locale support we don't want.  */
2674             case '0': case '1': case '2': case '3': case '4':
2675             case '5': case '6': case '7': case '8': case '9':
2676               {
2677                 c = strtoul (p - 1, &p, 10);
2678
2679                 operands_match[c][i]
2680                   = operands_match_p (recog_data.operand[c],
2681                                       recog_data.operand[i]);
2682
2683                 /* An operand may not match itself.  */
2684                 gcc_assert (c != i);
2685
2686                 /* If C can be commuted with C+1, and C might need to match I,
2687                    then C+1 might also need to match I.  */
2688                 if (commutative >= 0)
2689                   {
2690                     if (c == commutative || c == commutative + 1)
2691                       {
2692                         int other = c + (c == commutative ? 1 : -1);
2693                         operands_match[other][i]
2694                           = operands_match_p (recog_data.operand[other],
2695                                               recog_data.operand[i]);
2696                       }
2697                     if (i == commutative || i == commutative + 1)
2698                       {
2699                         int other = i + (i == commutative ? 1 : -1);
2700                         operands_match[c][other]
2701                           = operands_match_p (recog_data.operand[c],
2702                                               recog_data.operand[other]);
2703                       }
2704                     /* Note that C is supposed to be less than I.
2705                        No need to consider altering both C and I because in
2706                        that case we would alter one into the other.  */
2707                   }
2708               }
2709             }
2710         }
2711     }
2712
2713   /* Examine each operand that is a memory reference or memory address
2714      and reload parts of the addresses into index registers.
2715      Also here any references to pseudo regs that didn't get hard regs
2716      but are equivalent to constants get replaced in the insn itself
2717      with those constants.  Nobody will ever see them again.
2718
2719      Finally, set up the preferred classes of each operand.  */
2720
2721   for (i = 0; i < noperands; i++)
2722     {
2723       RTX_CODE code = GET_CODE (recog_data.operand[i]);
2724
2725       address_reloaded[i] = 0;
2726       address_operand_reloaded[i] = 0;
2727       operand_type[i] = (modified[i] == RELOAD_READ ? RELOAD_FOR_INPUT
2728                          : modified[i] == RELOAD_WRITE ? RELOAD_FOR_OUTPUT
2729                          : RELOAD_OTHER);
2730       address_type[i]
2731         = (modified[i] == RELOAD_READ ? RELOAD_FOR_INPUT_ADDRESS
2732            : modified[i] == RELOAD_WRITE ? RELOAD_FOR_OUTPUT_ADDRESS
2733            : RELOAD_OTHER);
2734
2735       if (*constraints[i] == 0)
2736         /* Ignore things like match_operator operands.  */
2737         ;
2738       else if (constraints[i][0] == 'p'
2739                || EXTRA_ADDRESS_CONSTRAINT (constraints[i][0], constraints[i]))
2740         {
2741           address_operand_reloaded[i]
2742             = find_reloads_address (recog_data.operand_mode[i], (rtx*) 0,
2743                                     recog_data.operand[i],
2744                                     recog_data.operand_loc[i],
2745                                     i, operand_type[i], ind_levels, insn);
2746
2747           /* If we now have a simple operand where we used to have a
2748              PLUS or MULT, re-recognize and try again.  */
2749           if ((OBJECT_P (*recog_data.operand_loc[i])
2750                || GET_CODE (*recog_data.operand_loc[i]) == SUBREG)
2751               && (GET_CODE (recog_data.operand[i]) == MULT
2752                   || GET_CODE (recog_data.operand[i]) == PLUS))
2753             {
2754               INSN_CODE (insn) = -1;
2755               retval = find_reloads (insn, replace, ind_levels, live_known,
2756                                      reload_reg_p);
2757               return retval;
2758             }
2759
2760           recog_data.operand[i] = *recog_data.operand_loc[i];
2761           substed_operand[i] = recog_data.operand[i];
2762
2763           /* Address operands are reloaded in their existing mode,
2764              no matter what is specified in the machine description.  */
2765           operand_mode[i] = GET_MODE (recog_data.operand[i]);
2766         }
2767       else if (code == MEM)
2768         {
2769           address_reloaded[i]
2770             = find_reloads_address (GET_MODE (recog_data.operand[i]),
2771                                     recog_data.operand_loc[i],
2772                                     XEXP (recog_data.operand[i], 0),
2773                                     &XEXP (recog_data.operand[i], 0),
2774                                     i, address_type[i], ind_levels, insn);
2775           recog_data.operand[i] = *recog_data.operand_loc[i];
2776           substed_operand[i] = recog_data.operand[i];
2777         }
2778       else if (code == SUBREG)
2779         {
2780           rtx reg = SUBREG_REG (recog_data.operand[i]);
2781           rtx op
2782             = find_reloads_toplev (recog_data.operand[i], i, address_type[i],
2783                                    ind_levels,
2784                                    set != 0
2785                                    && &SET_DEST (set) == recog_data.operand_loc[i],
2786                                    insn,
2787                                    &address_reloaded[i]);
2788
2789           /* If we made a MEM to load (a part of) the stackslot of a pseudo
2790              that didn't get a hard register, emit a USE with a REG_EQUAL
2791              note in front so that we might inherit a previous, possibly
2792              wider reload.  */
2793
2794           if (replace
2795               && MEM_P (op)
2796               && REG_P (reg)
2797               && (GET_MODE_SIZE (GET_MODE (reg))
2798                   >= GET_MODE_SIZE (GET_MODE (op))))
2799             set_unique_reg_note (emit_insn_before (gen_rtx_USE (VOIDmode, reg),
2800                                                    insn),
2801                                  REG_EQUAL, reg_equiv_memory_loc[REGNO (reg)]);
2802
2803           substed_operand[i] = recog_data.operand[i] = op;
2804         }
2805       else if (code == PLUS || GET_RTX_CLASS (code) == RTX_UNARY)
2806         /* We can get a PLUS as an "operand" as a result of register
2807            elimination.  See eliminate_regs and gen_reload.  We handle
2808            a unary operator by reloading the operand.  */
2809         substed_operand[i] = recog_data.operand[i]
2810           = find_reloads_toplev (recog_data.operand[i], i, address_type[i],
2811                                  ind_levels, 0, insn,
2812                                  &address_reloaded[i]);
2813       else if (code == REG)
2814         {
2815           /* This is equivalent to calling find_reloads_toplev.
2816              The code is duplicated for speed.
2817              When we find a pseudo always equivalent to a constant,
2818              we replace it by the constant.  We must be sure, however,
2819              that we don't try to replace it in the insn in which it
2820              is being set.  */
2821           int regno = REGNO (recog_data.operand[i]);
2822           if (reg_equiv_constant[regno] != 0
2823               && (set == 0 || &SET_DEST (set) != recog_data.operand_loc[i]))
2824             {
2825               /* Record the existing mode so that the check if constants are
2826                  allowed will work when operand_mode isn't specified.  */
2827
2828               if (operand_mode[i] == VOIDmode)
2829                 operand_mode[i] = GET_MODE (recog_data.operand[i]);
2830
2831               substed_operand[i] = recog_data.operand[i]
2832                 = reg_equiv_constant[regno];
2833             }
2834           if (reg_equiv_memory_loc[regno] != 0
2835               && (reg_equiv_address[regno] != 0 || num_not_at_initial_offset))
2836             /* We need not give a valid is_set_dest argument since the case
2837                of a constant equivalence was checked above.  */
2838             substed_operand[i] = recog_data.operand[i]
2839               = find_reloads_toplev (recog_data.operand[i], i, address_type[i],
2840                                      ind_levels, 0, insn,
2841                                      &address_reloaded[i]);
2842         }
2843       /* If the operand is still a register (we didn't replace it with an
2844          equivalent), get the preferred class to reload it into.  */
2845       code = GET_CODE (recog_data.operand[i]);
2846       preferred_class[i]
2847         = ((code == REG && REGNO (recog_data.operand[i])
2848             >= FIRST_PSEUDO_REGISTER)
2849            ? reg_preferred_class (REGNO (recog_data.operand[i]))
2850            : NO_REGS);
2851       pref_or_nothing[i]
2852         = (code == REG
2853            && REGNO (recog_data.operand[i]) >= FIRST_PSEUDO_REGISTER
2854            && reg_alternate_class (REGNO (recog_data.operand[i])) == NO_REGS);
2855     }
2856
2857   /* If this is simply a copy from operand 1 to operand 0, merge the
2858      preferred classes for the operands.  */
2859   if (set != 0 && noperands >= 2 && recog_data.operand[0] == SET_DEST (set)
2860       && recog_data.operand[1] == SET_SRC (set))
2861     {
2862       preferred_class[0] = preferred_class[1]
2863         = reg_class_subunion[(int) preferred_class[0]][(int) preferred_class[1]];
2864       pref_or_nothing[0] |= pref_or_nothing[1];
2865       pref_or_nothing[1] |= pref_or_nothing[0];
2866     }
2867
2868   /* Now see what we need for pseudo-regs that didn't get hard regs
2869      or got the wrong kind of hard reg.  For this, we must consider
2870      all the operands together against the register constraints.  */
2871
2872   best = MAX_RECOG_OPERANDS * 2 + 600;
2873
2874   swapped = 0;
2875   goal_alternative_swapped = 0;
2876  try_swapped:
2877
2878   /* The constraints are made of several alternatives.
2879      Each operand's constraint looks like foo,bar,... with commas
2880      separating the alternatives.  The first alternatives for all
2881      operands go together, the second alternatives go together, etc.
2882
2883      First loop over alternatives.  */
2884
2885   for (this_alternative_number = 0;
2886        this_alternative_number < n_alternatives;
2887        this_alternative_number++)
2888     {
2889       /* Loop over operands for one constraint alternative.  */
2890       /* LOSERS counts those that don't fit this alternative
2891          and would require loading.  */
2892       int losers = 0;
2893       /* BAD is set to 1 if it some operand can't fit this alternative
2894          even after reloading.  */
2895       int bad = 0;
2896       /* REJECT is a count of how undesirable this alternative says it is
2897          if any reloading is required.  If the alternative matches exactly
2898          then REJECT is ignored, but otherwise it gets this much
2899          counted against it in addition to the reloading needed.  Each
2900          ? counts three times here since we want the disparaging caused by
2901          a bad register class to only count 1/3 as much.  */
2902       int reject = 0;
2903
2904       this_earlyclobber = 0;
2905
2906       for (i = 0; i < noperands; i++)
2907         {
2908           char *p = constraints[i];
2909           char *end;
2910           int len;
2911           int win = 0;
2912           int did_match = 0;
2913           /* 0 => this operand can be reloaded somehow for this alternative.  */
2914           int badop = 1;
2915           /* 0 => this operand can be reloaded if the alternative allows regs.  */
2916           int winreg = 0;
2917           int c;
2918           int m;
2919           rtx operand = recog_data.operand[i];
2920           int offset = 0;
2921           /* Nonzero means this is a MEM that must be reloaded into a reg
2922              regardless of what the constraint says.  */
2923           int force_reload = 0;
2924           int offmemok = 0;
2925           /* Nonzero if a constant forced into memory would be OK for this
2926              operand.  */
2927           int constmemok = 0;
2928           int earlyclobber = 0;
2929
2930           /* If the predicate accepts a unary operator, it means that
2931              we need to reload the operand, but do not do this for
2932              match_operator and friends.  */
2933           if (UNARY_P (operand) && *p != 0)
2934             operand = XEXP (operand, 0);
2935
2936           /* If the operand is a SUBREG, extract
2937              the REG or MEM (or maybe even a constant) within.
2938              (Constants can occur as a result of reg_equiv_constant.)  */
2939
2940           while (GET_CODE (operand) == SUBREG)
2941             {
2942               /* Offset only matters when operand is a REG and
2943                  it is a hard reg.  This is because it is passed
2944                  to reg_fits_class_p if it is a REG and all pseudos
2945                  return 0 from that function.  */
2946               if (REG_P (SUBREG_REG (operand))
2947                   && REGNO (SUBREG_REG (operand)) < FIRST_PSEUDO_REGISTER)
2948                 {
2949                   if (!subreg_offset_representable_p
2950                         (REGNO (SUBREG_REG (operand)),
2951                          GET_MODE (SUBREG_REG (operand)),
2952                          SUBREG_BYTE (operand),
2953                          GET_MODE (operand)))
2954                      force_reload = 1;
2955                   offset += subreg_regno_offset (REGNO (SUBREG_REG (operand)),
2956                                                  GET_MODE (SUBREG_REG (operand)),
2957                                                  SUBREG_BYTE (operand),
2958                                                  GET_MODE (operand));
2959                 }
2960               operand = SUBREG_REG (operand);
2961               /* Force reload if this is a constant or PLUS or if there may
2962                  be a problem accessing OPERAND in the outer mode.  */
2963               if (CONSTANT_P (operand)
2964                   || GET_CODE (operand) == PLUS
2965                   /* We must force a reload of paradoxical SUBREGs
2966                      of a MEM because the alignment of the inner value
2967                      may not be enough to do the outer reference.  On
2968                      big-endian machines, it may also reference outside
2969                      the object.
2970
2971                      On machines that extend byte operations and we have a
2972                      SUBREG where both the inner and outer modes are no wider
2973                      than a word and the inner mode is narrower, is integral,
2974                      and gets extended when loaded from memory, combine.c has
2975                      made assumptions about the behavior of the machine in such
2976                      register access.  If the data is, in fact, in memory we
2977                      must always load using the size assumed to be in the
2978                      register and let the insn do the different-sized
2979                      accesses.
2980
2981                      This is doubly true if WORD_REGISTER_OPERATIONS.  In
2982                      this case eliminate_regs has left non-paradoxical
2983                      subregs for push_reload to see.  Make sure it does
2984                      by forcing the reload.
2985
2986                      ??? When is it right at this stage to have a subreg
2987                      of a mem that is _not_ to be handled specially?  IMO
2988                      those should have been reduced to just a mem.  */
2989                   || ((MEM_P (operand)
2990                        || (REG_P (operand)
2991                            && REGNO (operand) >= FIRST_PSEUDO_REGISTER))
2992 #ifndef WORD_REGISTER_OPERATIONS
2993                       && (((GET_MODE_BITSIZE (GET_MODE (operand))
2994                             < BIGGEST_ALIGNMENT)
2995                            && (GET_MODE_SIZE (operand_mode[i])
2996                                > GET_MODE_SIZE (GET_MODE (operand))))
2997                           || BYTES_BIG_ENDIAN
2998 #ifdef LOAD_EXTEND_OP
2999                           || (GET_MODE_SIZE (operand_mode[i]) <= UNITS_PER_WORD
3000                               && (GET_MODE_SIZE (GET_MODE (operand))
3001                                   <= UNITS_PER_WORD)
3002                               && (GET_MODE_SIZE (operand_mode[i])
3003                                   > GET_MODE_SIZE (GET_MODE (operand)))
3004                               && INTEGRAL_MODE_P (GET_MODE (operand))
3005                               && LOAD_EXTEND_OP (GET_MODE (operand)) != UNKNOWN)
3006 #endif
3007                           )
3008 #endif
3009                       )
3010                   )
3011                 force_reload = 1;
3012             }
3013
3014           this_alternative[i] = (int) NO_REGS;
3015           this_alternative_win[i] = 0;
3016           this_alternative_match_win[i] = 0;
3017           this_alternative_offmemok[i] = 0;
3018           this_alternative_earlyclobber[i] = 0;
3019           this_alternative_matches[i] = -1;
3020
3021           /* An empty constraint or empty alternative
3022              allows anything which matched the pattern.  */
3023           if (*p == 0 || *p == ',')
3024             win = 1, badop = 0;
3025
3026           /* Scan this alternative's specs for this operand;
3027              set WIN if the operand fits any letter in this alternative.
3028              Otherwise, clear BADOP if this operand could
3029              fit some letter after reloads,
3030              or set WINREG if this operand could fit after reloads
3031              provided the constraint allows some registers.  */
3032
3033           do
3034             switch ((c = *p, len = CONSTRAINT_LEN (c, p)), c)
3035               {
3036               case '\0':
3037                 len = 0;
3038                 break;
3039               case ',':
3040                 c = '\0';
3041                 break;
3042
3043               case '=':  case '+':  case '*':
3044                 break;
3045
3046               case '%':
3047                 /* We only support one commutative marker, the first
3048                    one.  We already set commutative above.  */
3049                 break;
3050
3051               case '?':
3052                 reject += 6;
3053                 break;
3054
3055               case '!':
3056                 reject = 600;
3057                 break;
3058
3059               case '#':
3060                 /* Ignore rest of this alternative as far as
3061                    reloading is concerned.  */
3062                 do
3063                   p++;
3064                 while (*p && *p != ',');
3065                 len = 0;
3066                 break;
3067
3068               case '0':  case '1':  case '2':  case '3':  case '4':
3069               case '5':  case '6':  case '7':  case '8':  case '9':
3070                 m = strtoul (p, &end, 10);
3071                 p = end;
3072                 len = 0;
3073
3074                 this_alternative_matches[i] = m;
3075                 /* We are supposed to match a previous operand.
3076                    If we do, we win if that one did.
3077                    If we do not, count both of the operands as losers.
3078                    (This is too conservative, since most of the time
3079                    only a single reload insn will be needed to make
3080                    the two operands win.  As a result, this alternative
3081                    may be rejected when it is actually desirable.)  */
3082                 if ((swapped && (m != commutative || i != commutative + 1))
3083                     /* If we are matching as if two operands were swapped,
3084                        also pretend that operands_match had been computed
3085                        with swapped.
3086                        But if I is the second of those and C is the first,
3087                        don't exchange them, because operands_match is valid
3088                        only on one side of its diagonal.  */
3089                     ? (operands_match
3090                        [(m == commutative || m == commutative + 1)
3091                        ? 2 * commutative + 1 - m : m]
3092                        [(i == commutative || i == commutative + 1)
3093                        ? 2 * commutative + 1 - i : i])
3094                     : operands_match[m][i])
3095                   {
3096                     /* If we are matching a non-offsettable address where an
3097                        offsettable address was expected, then we must reject
3098                        this combination, because we can't reload it.  */
3099                     if (this_alternative_offmemok[m]
3100                         && MEM_P (recog_data.operand[m])
3101                         && this_alternative[m] == (int) NO_REGS
3102                         && ! this_alternative_win[m])
3103                       bad = 1;
3104
3105                     did_match = this_alternative_win[m];
3106                   }
3107                 else
3108                   {
3109                     /* Operands don't match.  */
3110                     rtx value;
3111                     int loc1, loc2;
3112                     /* Retroactively mark the operand we had to match
3113                        as a loser, if it wasn't already.  */
3114                     if (this_alternative_win[m])
3115                       losers++;
3116                     this_alternative_win[m] = 0;
3117                     if (this_alternative[m] == (int) NO_REGS)
3118                       bad = 1;
3119                     /* But count the pair only once in the total badness of
3120                        this alternative, if the pair can be a dummy reload.
3121                        The pointers in operand_loc are not swapped; swap
3122                        them by hand if necessary.  */
3123                     if (swapped && i == commutative)
3124                       loc1 = commutative + 1;
3125                     else if (swapped && i == commutative + 1)
3126                       loc1 = commutative;
3127                     else
3128                       loc1 = i;
3129                     if (swapped && m == commutative)
3130                       loc2 = commutative + 1;
3131                     else if (swapped && m == commutative + 1)
3132                       loc2 = commutative;
3133                     else
3134                       loc2 = m;
3135                     value
3136                       = find_dummy_reload (recog_data.operand[i],
3137                                            recog_data.operand[m],
3138                                            recog_data.operand_loc[loc1],
3139                                            recog_data.operand_loc[loc2],
3140                                            operand_mode[i], operand_mode[m],
3141                                            this_alternative[m], -1,
3142                                            this_alternative_earlyclobber[m]);
3143
3144                     if (value != 0)
3145                       losers--;
3146                   }
3147                 /* This can be fixed with reloads if the operand
3148                    we are supposed to match can be fixed with reloads.  */
3149                 badop = 0;
3150                 this_alternative[i] = this_alternative[m];
3151
3152                 /* If we have to reload this operand and some previous
3153                    operand also had to match the same thing as this
3154                    operand, we don't know how to do that.  So reject this
3155                    alternative.  */
3156                 if (! did_match || force_reload)
3157                   for (j = 0; j < i; j++)
3158                     if (this_alternative_matches[j]
3159                         == this_alternative_matches[i])
3160                       badop = 1;
3161                 break;
3162
3163               case 'p':
3164                 /* All necessary reloads for an address_operand
3165                    were handled in find_reloads_address.  */
3166                 this_alternative[i] = (int) MODE_BASE_REG_CLASS (VOIDmode);
3167                 win = 1;
3168                 badop = 0;
3169                 break;
3170
3171               case 'm':
3172                 if (force_reload)
3173                   break;
3174                 if (MEM_P (operand)
3175                     || (REG_P (operand)
3176                         && REGNO (operand) >= FIRST_PSEUDO_REGISTER
3177                         && reg_renumber[REGNO (operand)] < 0))
3178                   win = 1;
3179                 if (CONST_POOL_OK_P (operand))
3180                   badop = 0;
3181                 constmemok = 1;
3182                 break;
3183
3184               case '<':
3185                 if (MEM_P (operand)
3186                     && ! address_reloaded[i]
3187                     && (GET_CODE (XEXP (operand, 0)) == PRE_DEC
3188                         || GET_CODE (XEXP (operand, 0)) == POST_DEC))
3189                   win = 1;
3190                 break;
3191
3192               case '>':
3193                 if (MEM_P (operand)
3194                     && ! address_reloaded[i]
3195                     && (GET_CODE (XEXP (operand, 0)) == PRE_INC
3196                         || GET_CODE (XEXP (operand, 0)) == POST_INC))
3197                   win = 1;
3198                 break;
3199
3200                 /* Memory operand whose address is not offsettable.  */
3201               case 'V':
3202                 if (force_reload)
3203                   break;
3204                 if (MEM_P (operand)
3205                     && ! (ind_levels ? offsettable_memref_p (operand)
3206                           : offsettable_nonstrict_memref_p (operand))
3207                     /* Certain mem addresses will become offsettable
3208                        after they themselves are reloaded.  This is important;
3209                        we don't want our own handling of unoffsettables
3210                        to override the handling of reg_equiv_address.  */
3211                     && !(REG_P (XEXP (operand, 0))
3212                          && (ind_levels == 0
3213                              || reg_equiv_address[REGNO (XEXP (operand, 0))] != 0)))
3214                   win = 1;
3215                 break;
3216
3217                 /* Memory operand whose address is offsettable.  */
3218               case 'o':
3219                 if (force_reload)
3220                   break;
3221                 if ((MEM_P (operand)
3222                      /* If IND_LEVELS, find_reloads_address won't reload a
3223                         pseudo that didn't get a hard reg, so we have to
3224                         reject that case.  */
3225                      && ((ind_levels ? offsettable_memref_p (operand)
3226                           : offsettable_nonstrict_memref_p (operand))
3227                          /* A reloaded address is offsettable because it is now
3228                             just a simple register indirect.  */
3229                          || address_reloaded[i] == 1))
3230                     || (REG_P (operand)
3231                         && REGNO (operand) >= FIRST_PSEUDO_REGISTER
3232                         && reg_renumber[REGNO (operand)] < 0
3233                         /* If reg_equiv_address is nonzero, we will be
3234                            loading it into a register; hence it will be
3235                            offsettable, but we cannot say that reg_equiv_mem
3236                            is offsettable without checking.  */
3237                         && ((reg_equiv_mem[REGNO (operand)] != 0
3238                              && offsettable_memref_p (reg_equiv_mem[REGNO (operand)]))
3239                             || (reg_equiv_address[REGNO (operand)] != 0))))
3240                   win = 1;
3241                 if (CONST_POOL_OK_P (operand)
3242                     || MEM_P (operand))
3243                   badop = 0;
3244                 constmemok = 1;
3245                 offmemok = 1;
3246                 break;
3247
3248               case '&':
3249                 /* Output operand that is stored before the need for the
3250                    input operands (and their index registers) is over.  */
3251                 earlyclobber = 1, this_earlyclobber = 1;
3252                 break;
3253
3254               case 'E':
3255               case 'F':
3256                 if (GET_CODE (operand) == CONST_DOUBLE
3257                     || (GET_CODE (operand) == CONST_VECTOR
3258                         && (GET_MODE_CLASS (GET_MODE (operand))
3259                             == MODE_VECTOR_FLOAT)))
3260                   win = 1;
3261                 break;
3262
3263               case 'G':
3264               case 'H':
3265                 if (GET_CODE (operand) == CONST_DOUBLE
3266                     && CONST_DOUBLE_OK_FOR_CONSTRAINT_P (operand, c, p))
3267                   win = 1;
3268                 break;
3269
3270               case 's':
3271                 if (GET_CODE (operand) == CONST_INT
3272                     || (GET_CODE (operand) == CONST_DOUBLE
3273                         && GET_MODE (operand) == VOIDmode))
3274                   break;
3275               case 'i':
3276                 if (CONSTANT_P (operand)
3277                     && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (operand)))
3278                   win = 1;
3279                 break;
3280
3281               case 'n':
3282                 if (GET_CODE (operand) == CONST_INT
3283                     || (GET_CODE (operand) == CONST_DOUBLE
3284                         && GET_MODE (operand) == VOIDmode))
3285                   win = 1;
3286                 break;
3287
3288               case 'I':
3289               case 'J':
3290               case 'K':
3291               case 'L':
3292               case 'M':
3293               case 'N':
3294               case 'O':
3295               case 'P':
3296                 if (GET_CODE (operand) == CONST_INT
3297                     && CONST_OK_FOR_CONSTRAINT_P (INTVAL (operand), c, p))
3298                   win = 1;
3299                 break;
3300
3301               case 'X':
3302                 win = 1;
3303                 break;
3304
3305               case 'g':
3306                 if (! force_reload
3307                     /* A PLUS is never a valid operand, but reload can make
3308                        it from a register when eliminating registers.  */
3309                     && GET_CODE (operand) != PLUS
3310                     /* A SCRATCH is not a valid operand.  */
3311                     && GET_CODE (operand) != SCRATCH
3312                     && (! CONSTANT_P (operand)
3313                         || ! flag_pic
3314                         || LEGITIMATE_PIC_OPERAND_P (operand))
3315                     && (GENERAL_REGS == ALL_REGS
3316                         || !REG_P (operand)
3317                         || (REGNO (operand) >= FIRST_PSEUDO_REGISTER
3318                             && reg_renumber[REGNO (operand)] < 0)))
3319                   win = 1;
3320                 /* Drop through into 'r' case.  */
3321
3322               case 'r':
3323                 this_alternative[i]
3324                   = (int) reg_class_subunion[this_alternative[i]][(int) GENERAL_REGS];
3325                 goto reg;
3326
3327               default:
3328                 if (REG_CLASS_FROM_CONSTRAINT (c, p) == NO_REGS)
3329                   {
3330 #ifdef EXTRA_CONSTRAINT_STR
3331                     if (EXTRA_MEMORY_CONSTRAINT (c, p))
3332                       {
3333                         if (force_reload)
3334                           break;
3335                         if (EXTRA_CONSTRAINT_STR (operand, c, p))
3336                           win = 1;
3337                         /* If the address was already reloaded,
3338                            we win as well.  */
3339                         else if (MEM_P (operand)
3340                                  && address_reloaded[i] == 1)
3341                           win = 1;
3342                         /* Likewise if the address will be reloaded because
3343                            reg_equiv_address is nonzero.  For reg_equiv_mem
3344                            we have to check.  */
3345                         else if (REG_P (operand)
3346                                  && REGNO (operand) >= FIRST_PSEUDO_REGISTER
3347                                  && reg_renumber[REGNO (operand)] < 0
3348                                  && ((reg_equiv_mem[REGNO (operand)] != 0
3349                                       && EXTRA_CONSTRAINT_STR (reg_equiv_mem[REGNO (operand)], c, p))
3350                                      || (reg_equiv_address[REGNO (operand)] != 0)))
3351                           win = 1;
3352
3353                         /* If we didn't already win, we can reload
3354                            constants via force_const_mem, and other
3355                            MEMs by reloading the address like for 'o'.  */
3356                         if (CONST_POOL_OK_P (operand)
3357                             || MEM_P (operand))
3358                           badop = 0;
3359                         constmemok = 1;
3360                         offmemok = 1;
3361                         break;
3362                       }
3363                     if (EXTRA_ADDRESS_CONSTRAINT (c, p))
3364                       {
3365                         if (EXTRA_CONSTRAINT_STR (operand, c, p))
3366                           win = 1;
3367
3368                         /* If we didn't already win, we can reload
3369                            the address into a base register.  */
3370                         this_alternative[i] = (int) MODE_BASE_REG_CLASS (VOIDmode);
3371                         badop = 0;
3372                         break;
3373                       }
3374
3375                     if (EXTRA_CONSTRAINT_STR (operand, c, p))
3376                       win = 1;
3377 #endif
3378                     break;
3379                   }
3380
3381                 this_alternative[i]
3382                   = (int) (reg_class_subunion
3383                            [this_alternative[i]]
3384                            [(int) REG_CLASS_FROM_CONSTRAINT (c, p)]);
3385               reg:
3386                 if (GET_MODE (operand) == BLKmode)
3387                   break;
3388                 winreg = 1;
3389                 if (REG_P (operand)
3390                     && reg_fits_class_p (operand, this_alternative[i],
3391                                          offset, GET_MODE (recog_data.operand[i])))
3392                   win = 1;
3393                 break;
3394               }
3395           while ((p += len), c);
3396
3397           constraints[i] = p;
3398
3399           /* If this operand could be handled with a reg,
3400              and some reg is allowed, then this operand can be handled.  */
3401           if (winreg && this_alternative[i] != (int) NO_REGS)
3402             badop = 0;
3403
3404           /* Record which operands fit this alternative.  */
3405           this_alternative_earlyclobber[i] = earlyclobber;
3406           if (win && ! force_reload)
3407             this_alternative_win[i] = 1;
3408           else if (did_match && ! force_reload)
3409             this_alternative_match_win[i] = 1;
3410           else
3411             {
3412               int const_to_mem = 0;
3413
3414               this_alternative_offmemok[i] = offmemok;
3415               losers++;
3416               if (badop)
3417                 bad = 1;
3418               /* Alternative loses if it has no regs for a reg operand.  */
3419               if (REG_P (operand)
3420                   && this_alternative[i] == (int) NO_REGS
3421                   && this_alternative_matches[i] < 0)
3422                 bad = 1;
3423
3424               /* If this is a constant that is reloaded into the desired
3425                  class by copying it to memory first, count that as another
3426                  reload.  This is consistent with other code and is
3427                  required to avoid choosing another alternative when
3428                  the constant is moved into memory by this function on
3429                  an early reload pass.  Note that the test here is
3430                  precisely the same as in the code below that calls
3431                  force_const_mem.  */
3432               if (CONST_POOL_OK_P (operand)
3433                   && ((PREFERRED_RELOAD_CLASS (operand,
3434                                                (enum reg_class) this_alternative[i])
3435                        == NO_REGS)
3436                       || no_input_reloads)
3437                   && operand_mode[i] != VOIDmode)
3438                 {
3439                   const_to_mem = 1;
3440                   if (this_alternative[i] != (int) NO_REGS)
3441                     losers++;
3442                 }
3443
3444               /* If we can't reload this value at all, reject this
3445                  alternative.  Note that we could also lose due to
3446                  LIMIT_RELOAD_RELOAD_CLASS, but we don't check that
3447                  here.  */
3448
3449               if (! CONSTANT_P (operand)
3450                   && (enum reg_class) this_alternative[i] != NO_REGS
3451                   && (PREFERRED_RELOAD_CLASS (operand,
3452                                               (enum reg_class) this_alternative[i])
3453                       == NO_REGS))
3454                 bad = 1;
3455
3456               /* Alternative loses if it requires a type of reload not
3457                  permitted for this insn.  We can always reload SCRATCH
3458                  and objects with a REG_UNUSED note.  */
3459               else if (GET_CODE (operand) != SCRATCH
3460                        && modified[i] != RELOAD_READ && no_output_reloads
3461                        && ! find_reg_note (insn, REG_UNUSED, operand))
3462                 bad = 1;
3463               else if (modified[i] != RELOAD_WRITE && no_input_reloads
3464                        && ! const_to_mem)
3465                 bad = 1;
3466
3467               /* We prefer to reload pseudos over reloading other things,
3468                  since such reloads may be able to be eliminated later.
3469                  If we are reloading a SCRATCH, we won't be generating any
3470                  insns, just using a register, so it is also preferred.
3471                  So bump REJECT in other cases.  Don't do this in the
3472                  case where we are forcing a constant into memory and
3473                  it will then win since we don't want to have a different
3474                  alternative match then.  */
3475               if (! (REG_P (operand)
3476                      && REGNO (operand) >= FIRST_PSEUDO_REGISTER)
3477                   && GET_CODE (operand) != SCRATCH
3478                   && ! (const_to_mem && constmemok))
3479                 reject += 2;
3480
3481               /* Input reloads can be inherited more often than output
3482                  reloads can be removed, so penalize output reloads.  */
3483               if (operand_type[i] != RELOAD_FOR_INPUT
3484                   && GET_CODE (operand) != SCRATCH)
3485                 reject++;
3486             }
3487
3488           /* If this operand is a pseudo register that didn't get a hard
3489              reg and this alternative accepts some register, see if the
3490              class that we want is a subset of the preferred class for this
3491              register.  If not, but it intersects that class, use the
3492              preferred class instead.  If it does not intersect the preferred
3493              class, show that usage of this alternative should be discouraged;
3494              it will be discouraged more still if the register is `preferred
3495              or nothing'.  We do this because it increases the chance of
3496              reusing our spill register in a later insn and avoiding a pair
3497              of memory stores and loads.
3498
3499              Don't bother with this if this alternative will accept this
3500              operand.
3501
3502              Don't do this for a multiword operand, since it is only a
3503              small win and has the risk of requiring more spill registers,
3504              which could cause a large loss.
3505
3506              Don't do this if the preferred class has only one register
3507              because we might otherwise exhaust the class.  */
3508
3509           if (! win && ! did_match
3510               && this_alternative[i] != (int) NO_REGS
3511               && GET_MODE_SIZE (operand_mode[i]) <= UNITS_PER_WORD
3512               && reg_class_size [(int) preferred_class[i]] > 0
3513               && ! SMALL_REGISTER_CLASS_P (preferred_class[i]))
3514             {
3515               if (! reg_class_subset_p (this_alternative[i],
3516                                         preferred_class[i]))
3517                 {
3518                   /* Since we don't have a way of forming the intersection,
3519                      we just do something special if the preferred class
3520                      is a subset of the class we have; that's the most
3521                      common case anyway.  */
3522                   if (reg_class_subset_p (preferred_class[i],
3523                                           this_alternative[i]))
3524                     this_alternative[i] = (int) preferred_class[i];
3525                   else
3526                     reject += (2 + 2 * pref_or_nothing[i]);
3527                 }
3528             }
3529         }
3530
3531       /* Now see if any output operands that are marked "earlyclobber"
3532          in this alternative conflict with any input operands
3533          or any memory addresses.  */
3534
3535       for (i = 0; i < noperands; i++)
3536         if (this_alternative_earlyclobber[i]
3537             && (this_alternative_win[i] || this_alternative_match_win[i]))
3538           {
3539             struct decomposition early_data;
3540
3541             early_data = decompose (recog_data.operand[i]);
3542
3543             gcc_assert (modified[i] != RELOAD_READ);
3544
3545             if (this_alternative[i] == NO_REGS)
3546               {
3547                 this_alternative_earlyclobber[i] = 0;
3548                 gcc_assert (this_insn_is_asm);
3549                 error_for_asm (this_insn,
3550                                "%<&%> constraint used with no register class");
3551               }
3552
3553             for (j = 0; j < noperands; j++)
3554               /* Is this an input operand or a memory ref?  */
3555               if ((MEM_P (recog_data.operand[j])
3556                    || modified[j] != RELOAD_WRITE)
3557                   && j != i
3558                   /* Ignore things like match_operator operands.  */
3559                   && *recog_data.constraints[j] != 0
3560                   /* Don't count an input operand that is constrained to match
3561                      the early clobber operand.  */
3562                   && ! (this_alternative_matches[j] == i
3563                         && rtx_equal_p (recog_data.operand[i],
3564                                         recog_data.operand[j]))
3565                   /* Is it altered by storing the earlyclobber operand?  */
3566                   && !immune_p (recog_data.operand[j], recog_data.operand[i],
3567                                 early_data))
3568                 {
3569                   /* If the output is in a non-empty few-regs class,
3570                      it's costly to reload it, so reload the input instead.  */
3571                   if (SMALL_REGISTER_CLASS_P (this_alternative[i])
3572                       && (REG_P (recog_data.operand[j])
3573                           || GET_CODE (recog_data.operand[j]) == SUBREG))
3574                     {
3575                       losers++;
3576                       this_alternative_win[j] = 0;
3577                       this_alternative_match_win[j] = 0;
3578                     }
3579                   else
3580                     break;
3581                 }
3582             /* If an earlyclobber operand conflicts with something,
3583                it must be reloaded, so request this and count the cost.  */
3584             if (j != noperands)
3585               {
3586                 losers++;
3587                 this_alternative_win[i] = 0;
3588                 this_alternative_match_win[j] = 0;
3589                 for (j = 0; j < noperands; j++)
3590                   if (this_alternative_matches[j] == i
3591                       && this_alternative_match_win[j])
3592                     {
3593                       this_alternative_win[j] = 0;
3594                       this_alternative_match_win[j] = 0;
3595                       losers++;
3596                     }
3597               }
3598           }
3599
3600       /* If one alternative accepts all the operands, no reload required,
3601          choose that alternative; don't consider the remaining ones.  */
3602       if (losers == 0)
3603         {
3604           /* Unswap these so that they are never swapped at `finish'.  */
3605           if (commutative >= 0)
3606             {
3607               recog_data.operand[commutative] = substed_operand[commutative];
3608               recog_data.operand[commutative + 1]
3609                 = substed_operand[commutative + 1];
3610             }
3611           for (i = 0; i < noperands; i++)
3612             {
3613               goal_alternative_win[i] = this_alternative_win[i];
3614               goal_alternative_match_win[i] = this_alternative_match_win[i];
3615               goal_alternative[i] = this_alternative[i];
3616               goal_alternative_offmemok[i] = this_alternative_offmemok[i];
3617               goal_alternative_matches[i] = this_alternative_matches[i];
3618               goal_alternative_earlyclobber[i]
3619                 = this_alternative_earlyclobber[i];
3620             }
3621           goal_alternative_number = this_alternative_number;
3622           goal_alternative_swapped = swapped;
3623           goal_earlyclobber = this_earlyclobber;
3624           goto finish;
3625         }
3626
3627       /* REJECT, set by the ! and ? constraint characters and when a register
3628          would be reloaded into a non-preferred class, discourages the use of
3629          this alternative for a reload goal.  REJECT is incremented by six
3630          for each ? and two for each non-preferred class.  */
3631       losers = losers * 6 + reject;
3632
3633       /* If this alternative can be made to work by reloading,
3634          and it needs less reloading than the others checked so far,
3635          record it as the chosen goal for reloading.  */
3636       if (! bad && best > losers)
3637         {
3638           for (i = 0; i < noperands; i++)
3639             {
3640               goal_alternative[i] = this_alternative[i];
3641               goal_alternative_win[i] = this_alternative_win[i];
3642               goal_alternative_match_win[i] = this_alternative_match_win[i];
3643               goal_alternative_offmemok[i] = this_alternative_offmemok[i];
3644               goal_alternative_matches[i] = this_alternative_matches[i];
3645               goal_alternative_earlyclobber[i]
3646                 = this_alternative_earlyclobber[i];
3647             }
3648           goal_alternative_swapped = swapped;
3649           best = losers;
3650           goal_alternative_number = this_alternative_number;
3651           goal_earlyclobber = this_earlyclobber;
3652         }
3653     }
3654
3655   /* If insn is commutative (it's safe to exchange a certain pair of operands)
3656      then we need to try each alternative twice,
3657      the second time matching those two operands
3658      as if we had exchanged them.
3659      To do this, really exchange them in operands.
3660
3661      If we have just tried the alternatives the second time,
3662      return operands to normal and drop through.  */
3663
3664   if (commutative >= 0)
3665     {
3666       swapped = !swapped;
3667       if (swapped)
3668         {
3669           enum reg_class tclass;
3670           int t;
3671
3672           recog_data.operand[commutative] = substed_operand[commutative + 1];
3673           recog_data.operand[commutative + 1] = substed_operand[commutative];
3674           /* Swap the duplicates too.  */
3675           for (i = 0; i < recog_data.n_dups; i++)
3676             if (recog_data.dup_num[i] == commutative
3677                 || recog_data.dup_num[i] == commutative + 1)
3678               *recog_data.dup_loc[i]
3679                  = recog_data.operand[(int) recog_data.dup_num[i]];
3680
3681           tclass = preferred_class[commutative];
3682           preferred_class[commutative] = preferred_class[commutative + 1];
3683           preferred_class[commutative + 1] = tclass;
3684
3685           t = pref_or_nothing[commutative];
3686           pref_or_nothing[commutative] = pref_or_nothing[commutative + 1];
3687           pref_or_nothing[commutative + 1] = t;
3688
3689           t = address_reloaded[commutative];
3690           address_reloaded[commutative] = address_reloaded[commutative + 1];
3691           address_reloaded[commutative + 1] = t;
3692
3693           memcpy (constraints, recog_data.constraints,
3694                   noperands * sizeof (char *));
3695           goto try_swapped;
3696         }
3697       else
3698         {
3699           recog_data.operand[commutative] = substed_operand[commutative];
3700           recog_data.operand[commutative + 1]
3701             = substed_operand[commutative + 1];
3702           /* Unswap the duplicates too.  */
3703           for (i = 0; i < recog_data.n_dups; i++)
3704             if (recog_data.dup_num[i] == commutative
3705                 || recog_data.dup_num[i] == commutative + 1)
3706               *recog_data.dup_loc[i]
3707                  = recog_data.operand[(int) recog_data.dup_num[i]];
3708         }
3709     }
3710
3711   /* The operands don't meet the constraints.
3712      goal_alternative describes the alternative
3713      that we could reach by reloading the fewest operands.
3714      Reload so as to fit it.  */
3715
3716   if (best == MAX_RECOG_OPERANDS * 2 + 600)
3717     {
3718       /* No alternative works with reloads??  */
3719       if (insn_code_number >= 0)
3720         fatal_insn ("unable to generate reloads for:", insn);
3721       error_for_asm (insn, "inconsistent operand constraints in an %<asm%>");
3722       /* Avoid further trouble with this insn.  */
3723       PATTERN (insn) = gen_rtx_USE (VOIDmode, const0_rtx);
3724       n_reloads = 0;
3725       return 0;
3726     }
3727
3728   /* Jump to `finish' from above if all operands are valid already.
3729      In that case, goal_alternative_win is all 1.  */
3730  finish:
3731
3732   /* Right now, for any pair of operands I and J that are required to match,
3733      with I < J,
3734      goal_alternative_matches[J] is I.
3735      Set up goal_alternative_matched as the inverse function:
3736      goal_alternative_matched[I] = J.  */
3737
3738   for (i = 0; i < noperands; i++)
3739     goal_alternative_matched[i] = -1;
3740
3741   for (i = 0; i < noperands; i++)
3742     if (! goal_alternative_win[i]
3743         && goal_alternative_matches[i] >= 0)
3744       goal_alternative_matched[goal_alternative_matches[i]] = i;
3745