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 Free Software Foundation, Inc.
   3
   4 This file is part of GNU CC.
   5
   6 GNU CC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU CC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU CC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  19
  20
  21 /* This file contains subroutines used only from the file reload1.c.
  22    It knows how to scan one insn for operands and values
  23    that need to be copied into registers to make valid code.
  24    It also finds other operands and values which are valid
  25    but for which equivalent values in registers exist and
  26    ought to be used instead.
  27
  28    Before processing the first insn of the function, call `init_reload'.
  29
  30    To scan an insn, call `find_reloads'.  This does two things:
  31    1. sets up tables describing which values must be reloaded
  32    for this insn, and what kind of hard regs they must be reloaded into;
  33    2. optionally record the locations where those values appear in
  34    the data, so they can be replaced properly later.
  35    This is done only if the second arg to `find_reloads' is nonzero.
  36
  37    The third arg to `find_reloads' specifies the number of levels
  38    of indirect addressing supported by the machine.  If it is zero,
  39    indirect addressing is not valid.  If it is one, (MEM (REG n))
  40    is valid even if (REG n) did not get a hard register; if it is two,
  41    (MEM (MEM (REG n))) is also valid even if (REG n) did not get a
  42    hard register, and similarly for higher values.
  43
  44    Then you must choose the hard regs to reload those pseudo regs into,
  45    and generate appropriate load insns before this insn and perhaps
  46    also store insns after this insn.  Set up the array `reload_reg_rtx'
  47    to contain the REG rtx's for the registers you used.  In some
  48    cases `find_reloads' will return a nonzero value in `reload_reg_rtx'
  49    for certain reloads.  Then that tells you which register to use,
  50    so you do not need to allocate one.  But you still do need to add extra
  51    instructions to copy the value into and out of that register.
  52
  53    Finally you must call `subst_reloads' to substitute the reload reg rtx's
  54    into the locations already recorded.
  55
  56 NOTE SIDE EFFECTS:
  57
  58    find_reloads can alter the operands of the instruction it is called on.
  59
  60    1. Two operands of any sort may be interchanged, if they are in a
  61    commutative instruction.
  62    This happens only if find_reloads thinks the instruction will compile
  63    better that way.
  64
  65    2. Pseudo-registers that are equivalent to constants are replaced
  66    with those constants if they are not in hard registers.
  67
  68 1 happens every time find_reloads is called.
  69 2 happens only when REPLACE is 1, which is only when
  70 actually doing the reloads, not when just counting them.
  71
  72
  73 Using a reload register for several reloads in one insn:
  74
  75 When an insn has reloads, it is considered as having three parts:
  76 the input reloads, the insn itself after reloading, and the output reloads.
  77 Reloads of values used in memory addresses are often needed for only one part.
  78
  79 When this is so, reload_when_needed records which part needs the reload.
  80 Two reloads for different parts of the insn can share the same reload
  81 register.
  82
  83 When a reload is used for addresses in multiple parts, or when it is
  84 an ordinary operand, it is classified as RELOAD_OTHER, and cannot share
  85 a register with any other reload.  */
  86
  87 #define REG_OK_STRICT
  88
  89 #include "config.h"
  90 #include "rtl.h"
  91 #include "insn-config.h"
  92 #include "insn-codes.h"
  93 #include "recog.h"
  94 #include "reload.h"
  95 #include "regs.h"
  96 #include "hard-reg-set.h"
  97 #include "flags.h"
  98 #include "real.h"
  99
 100 #ifndef REGISTER_MOVE_COST
 101 #define REGISTER_MOVE_COST(x, y) 2
 102 #endif
 103 \f
 104 /* The variables set up by `find_reloads' are:
 105
 106    n_reloads              number of distinct reloads needed; max reload # + 1
 107        tables indexed by reload number
 108    reload_in              rtx for value to reload from
 109    reload_out             rtx for where to store reload-reg afterward if nec
 110                            (often the same as reload_in)
 111    reload_reg_class       enum reg_class, saying what regs to reload into
 112    reload_inmode          enum machine_mode; mode this operand should have
 113                            when reloaded, on input.
 114    reload_outmode         enum machine_mode; mode this operand should have
 115                            when reloaded, on output.
 116    reload_strict_low      char; currently always zero; used to mean that this
 117                           reload is inside a STRICT_LOW_PART, but we don't
 118                           need to know this anymore.
 119    reload_optional        char, nonzero for an optional reload.
 120                            Optional reloads are ignored unless the
 121                            value is already sitting in a register.
 122    reload_inc             int, positive amount to increment or decrement by if
 123                            reload_in is a PRE_DEC, PRE_INC, POST_DEC, POST_INC.
 124                            Ignored otherwise (don't assume it is zero).
 125    reload_in_reg          rtx.  A reg for which reload_in is the equivalent.
 126                            If reload_in is a symbol_ref which came from
 127                            reg_equiv_constant, then this is the pseudo
 128                            which has that symbol_ref as equivalent.
 129    reload_reg_rtx         rtx.  This is the register to reload into.
 130                            If it is zero when `find_reloads' returns,
 131                            you must find a suitable register in the class
 132                            specified by reload_reg_class, and store here
 133                            an rtx for that register with mode from
 134                            reload_inmode or reload_outmode.
 135    reload_nocombine       char, nonzero if this reload shouldn't be
 136                            combined with another reload.
 137    reload_needed_for      rtx, operand this reload is needed for address of.
 138                            0 means it isn't needed for addressing.
 139    reload_needed_for_multiple
 140                           int, 1 if this reload needed for more than one thing.
 141    reload_when_needed     enum, classifies reload as needed either for
 142                            addressing an input reload, addressing an output,
 143                            for addressing a non-reloaded mem ref,
 144                            or for unspecified purposes (i.e., more than one
 145                            of the above).
 146    reload_secondary_reload int, gives the reload number of a secondary
 147                            reload, when needed; otherwise -1
 148    reload_secondary_p     int, 1 if this is a secondary register for one
 149                           or more reloads.
 150    reload_secondary_icode enum insn_code, if a secondary reload is required,
 151                            gives the INSN_CODE that uses the secondary
 152                            reload as a scratch register, or CODE_FOR_nothing
 153                            if the secondary reload register is to be an
 154                            intermediate register.  */
 155 int n_reloads;
 156
 157 rtx reload_in[MAX_RELOADS];
 158 rtx reload_out[MAX_RELOADS];
 159 enum reg_class reload_reg_class[MAX_RELOADS];
 160 enum machine_mode reload_inmode[MAX_RELOADS];
 161 enum machine_mode reload_outmode[MAX_RELOADS];
 162 char reload_strict_low[MAX_RELOADS];
 163 rtx reload_reg_rtx[MAX_RELOADS];
 164 char reload_optional[MAX_RELOADS];
 165 int reload_inc[MAX_RELOADS];
 166 rtx reload_in_reg[MAX_RELOADS];
 167 char reload_nocombine[MAX_RELOADS];
 168 int reload_needed_for_multiple[MAX_RELOADS];
 169 rtx reload_needed_for[MAX_RELOADS];
 170 enum reload_when_needed reload_when_needed[MAX_RELOADS];
 171 int reload_secondary_reload[MAX_RELOADS];
 172 int reload_secondary_p[MAX_RELOADS];
 173 enum insn_code reload_secondary_icode[MAX_RELOADS];
 174
 175 /* All the "earlyclobber" operands of the current insn
 176    are recorded here.  */
 177 int n_earlyclobbers;
 178 rtx reload_earlyclobbers[MAX_RECOG_OPERANDS];
 179
 180 /* Replacing reloads.
 181
 182    If `replace_reloads' is nonzero, then as each reload is recorded
 183    an entry is made for it in the table `replacements'.
 184    Then later `subst_reloads' can look through that table and
 185    perform all the replacements needed.  */
 186
 187 /* Nonzero means record the places to replace.  */
 188 static int replace_reloads;
 189
 190 /* Each replacement is recorded with a structure like this.  */
 191 struct replacement
 192 {
 193   rtx *where;                   /* Location to store in */
 194   rtx *subreg_loc;              /* Location of SUBREG if WHERE is inside
 195                                    a SUBREG; 0 otherwise.  */
 196   int what;                     /* which reload this is for */
 197   enum machine_mode mode;       /* mode it must have */
 198 };
 199
 200 static struct replacement replacements[MAX_RECOG_OPERANDS * ((MAX_REGS_PER_ADDRESS * 2) + 1)];
 201
 202 /* Number of replacements currently recorded.  */
 203 static int n_replacements;
 204
 205 /* MEM-rtx's created for pseudo-regs in stack slots not directly addressable;
 206    (see reg_equiv_address).  */
 207 static rtx memlocs[MAX_RECOG_OPERANDS * ((MAX_REGS_PER_ADDRESS * 2) + 1)];
 208 static int n_memlocs;
 209
 210 #ifdef SECONDARY_MEMORY_NEEDED
 211
 212 /* Save MEMs needed to copy from one class of registers to another.  One MEM
 213    is used per mode, but normally only one or two modes are ever used.
 214
 215    We keep two versions, before and after register elimination.  */
 216
 217 static rtx secondary_memlocs[NUM_MACHINE_MODES];
 218 static rtx secondary_memlocs_elim[NUM_MACHINE_MODES];
 219 #endif
 220
 221 /* The instruction we are doing reloads for;
 222    so we can test whether a register dies in it.  */
 223 static rtx this_insn;
 224
 225 /* Nonzero if this instruction is a user-specified asm with operands.  */
 226 static int this_insn_is_asm;
 227
 228 /* If hard_regs_live_known is nonzero,
 229    we can tell which hard regs are currently live,
 230    at least enough to succeed in choosing dummy reloads.  */
 231 static int hard_regs_live_known;
 232
 233 /* Indexed by hard reg number,
 234    element is nonegative if hard reg has been spilled.
 235    This vector is passed to `find_reloads' as an argument
 236    and is not changed here.  */
 237 static short *static_reload_reg_p;
 238
 239 /* Set to 1 in subst_reg_equivs if it changes anything.  */
 240 static int subst_reg_equivs_changed;
 241
 242 /* On return from push_reload, holds the reload-number for the OUT
 243    operand, which can be different for that from the input operand.  */
 244 static int output_reloadnum;
 245
 246 static int alternative_allows_memconst ();
 247 static rtx find_dummy_reload ();
 248 static rtx find_reloads_toplev ();
 249 static int find_reloads_address ();
 250 static int find_reloads_address_1 ();
 251 static void find_reloads_address_part ();
 252 static int hard_reg_set_here_p ();
 253 /* static rtx forget_volatility (); */
 254 static rtx subst_reg_equivs ();
 255 static rtx subst_indexed_address ();
 256 void copy_replacements ();
 257 rtx find_equiv_reg ();
 258 static int find_inc_amount ();
 259 \f
 260 #ifdef HAVE_SECONDARY_RELOADS
 261
 262 /* Determine if any secondary reloads are needed for loading (if IN_P is
 263    non-zero) or storing (if IN_P is zero) X to or from a reload register of
 264    register class RELOAD_CLASS in mode RELOAD_MODE.
 265
 266    Return the register class of a secondary reload register, or NO_REGS if
 267    none.  *PMODE is set to the mode that the register is required in.
 268    If the reload register is needed as a scratch register instead of an
 269    intermediate register, *PICODE is set to the insn_code of the insn to be
 270    used to load or store the primary reload register; otherwise *PICODE
 271    is set to CODE_FOR_nothing.
 272
 273    In some cases (such as storing MQ into an external memory location on
 274    the RT), both an intermediate register and a scratch register.  In that
 275    case, *PICODE is set to CODE_FOR_nothing, the class for the intermediate
 276    register is returned, and the *PTERTIARY_... variables are set to describe
 277    the scratch register.  */
 278
 279 static enum reg_class
 280 find_secondary_reload (x, reload_class, reload_mode, in_p, picode, pmode,
 281                       ptertiary_class, ptertiary_icode, ptertiary_mode)
 282      rtx x;
 283      enum reg_class reload_class;
 284      enum machine_mode reload_mode;
 285      int in_p;
 286      enum insn_code *picode;
 287      enum machine_mode *pmode;
 288      enum reg_class *ptertiary_class;
 289      enum insn_code *ptertiary_icode;
 290      enum machine_mode *ptertiary_mode;
 291 {
 292   enum reg_class class = NO_REGS;
 293   enum machine_mode mode = reload_mode;
 294   enum insn_code icode = CODE_FOR_nothing;
 295   enum reg_class t_class = NO_REGS;
 296   enum machine_mode t_mode = VOIDmode;
 297   enum insn_code t_icode = CODE_FOR_nothing;
 298
 299   /* If X is a pseudo-register that has an equivalent MEM (actually, if it
 300      is still a pseudo-register by now, it *must* have an equivalent MEM
 301      but we don't want to assume that), use that equivalent when seeing if
 302      a secondary reload is needed since whether or not a reload is needed
 303      might be sensitive to the form of the MEM.  */
 304
 305   if (GET_CODE (x) == REG && REGNO (x) >= FIRST_PSEUDO_REGISTER
 306       && reg_equiv_mem[REGNO (x)] != 0)
 307     x = reg_equiv_mem[REGNO (x)];
 308
 309 #ifdef SECONDARY_INPUT_RELOAD_CLASS
 310   if (in_p)
 311     class = SECONDARY_INPUT_RELOAD_CLASS (reload_class, reload_mode, x);
 312 #endif
 313
 314 #ifdef SECONDARY_OUTPUT_RELOAD_CLASS
 315   if (! in_p)
 316     class = SECONDARY_OUTPUT_RELOAD_CLASS (reload_class, reload_mode, x);
 317 #endif
 318
 319   /* If we don't need any secondary registers, go away; the rest of the
 320      values won't be used.  */
 321   if (class == NO_REGS)
 322     return NO_REGS;
 323
 324   /* Get a possible insn to use.  If the predicate doesn't accept X, don't
 325      use the insn.  */
 326
 327   icode = (in_p ? reload_in_optab[(int) reload_mode]
 328            : reload_out_optab[(int) reload_mode]);
 329
 330   if (icode != CODE_FOR_nothing
 331       && insn_operand_predicate[(int) icode][in_p]
 332       && (! (insn_operand_predicate[(int) icode][in_p]) (x, reload_mode)))
 333     icode = CODE_FOR_nothing;
 334
 335   /* If we will be using an insn, see if it can directly handle the reload
 336      register we will be using.  If it can, the secondary reload is for a
 337      scratch register.  If it can't, we will use the secondary reload for
 338      an intermediate register and require a tertiary reload for the scratch
 339      register.  */
 340
 341   if (icode != CODE_FOR_nothing)
 342     {
 343       /* If IN_P is non-zero, the reload register will be the output in
 344          operand 0.  If IN_P is zero, the reload register will be the input
 345          in operand 1.  Outputs should have an initial "=", which we must
 346          skip.  */
 347
 348       char insn_letter = insn_operand_constraint[(int) icode][!in_p][in_p];
 349       enum reg_class insn_class
 350         = (insn_letter == 'r' ? GENERAL_REGS
 351            : REG_CLASS_FROM_LETTER (insn_letter));
 352
 353       if (insn_class == NO_REGS
 354           || (in_p && insn_operand_constraint[(int) icode][!in_p][0] != '=')
 355           /* The scratch register's constraint must start with "=&".  */
 356           || insn_operand_constraint[(int) icode][2][0] != '='
 357           || insn_operand_constraint[(int) icode][2][1] != '&')
 358         abort ();
 359
 360       if (reg_class_subset_p (reload_class, insn_class))
 361         mode = insn_operand_mode[(int) icode][2];
 362       else
 363         {
 364           char t_letter = insn_operand_constraint[(int) icode][2][2];
 365           class = insn_class;
 366           t_mode = insn_operand_mode[(int) icode][2];
 367           t_class = (t_letter == 'r' ? GENERAL_REGS
 368                      : REG_CLASS_FROM_LETTER (t_letter));
 369           t_icode = icode;
 370           icode = CODE_FOR_nothing;
 371         }
 372     }
 373
 374   *pmode = mode;
 375   *picode = icode;
 376   *ptertiary_class = t_class;
 377   *ptertiary_mode = t_mode;
 378   *ptertiary_icode = t_icode;
 379
 380   return class;
 381 }
 382 #endif /* HAVE_SECONDARY_RELOADS */
 383 \f
 384 #ifdef SECONDARY_MEMORY_NEEDED
 385
 386 /* Return a memory location that will be used to copy X in mode MODE.
 387    If we haven't already made a location for this mode in this insn,
 388    call find_reloads_address on the location being returned.  */
 389
 390 rtx
 391 get_secondary_mem (x, mode)
 392      rtx x;
 393      enum machine_mode mode;
 394 {
 395   rtx loc;
 396   int mem_valid;
 397
 398   /* If MODE is narrower than a word, widen it.  This is required because
 399      most machines that require these memory locations do not support
 400      short load and stores from all registers (e.g., FP registers).  We could
 401      possibly conditionalize this, but we lose nothing by doing the wider
 402      mode.  */
 403
 404   if (GET_MODE_BITSIZE (mode) < BITS_PER_WORD)
 405     mode = mode_for_size (BITS_PER_WORD, GET_MODE_CLASS (mode), 0);
 406
 407   /* If we already have made a MEM for this insn, return it.  */
 408   if (secondary_memlocs_elim[(int) mode] != 0)
 409     return secondary_memlocs_elim[(int) mode];
 410
 411   /* If this is the first time we've tried to get a MEM for this mode,
 412      allocate a new one.  `something_changed' in reload will get set
 413      by noticing that the frame size has changed.  */
 414
 415   if (secondary_memlocs[(int) mode] == 0)
 416     secondary_memlocs[(int) mode]
 417       = assign_stack_local (mode, GET_MODE_SIZE (mode), 0);
 418
 419   /* Get a version of the address doing any eliminations needed.  If that
 420      didn't give us a new MEM, make a new one if it isn't valid.  */
 421
 422   loc = eliminate_regs (secondary_memlocs[(int) mode], 0, NULL_RTX);
 423   mem_valid = strict_memory_address_p (mode, XEXP (loc, 0));
 424
 425   if (! mem_valid && loc == secondary_memlocs[(int) mode])
 426     loc = copy_rtx (loc);
 427
 428   /* The only time the call below will do anything is if the stack
 429      offset is too large.  In that case IND_LEVELS doesn't matter, so we
 430      can just pass a zero.  */
 431   if (! mem_valid)
 432     find_reloads_address (mode, NULL_PTR, XEXP (loc, 0), &XEXP (loc, 0), x, 0);
 433
 434   secondary_memlocs_elim[(int) mode] = loc;
 435
 436   return loc;
 437 }
 438
 439 /* Clear any secondary memory locations we've made.  */
 440
 441 void
 442 clear_secondary_mem ()
 443 {
 444   int i;
 445
 446   for (i = 0; i < NUM_MACHINE_MODES; i++)
 447     secondary_memlocs[i] = 0;
 448 }
 449 #endif /* SECONDARY_MEMORY_NEEDED */
 450 \f
 451 /* Record one (sometimes two) reload that needs to be performed.
 452    IN is an rtx saying where the data are to be found before this instruction.
 453    OUT says where they must be stored after the instruction.
 454    (IN is zero for data not read, and OUT is zero for data not written.)
 455    INLOC and OUTLOC point to the places in the instructions where
 456    IN and OUT were found.
 457    CLASS is a register class required for the reloaded data.
 458    INMODE is the machine mode that the instruction requires
 459    for the reg that replaces IN and OUTMODE is likewise for OUT.
 460
 461    If IN is zero, then OUT's location and mode should be passed as
 462    INLOC and INMODE.
 463
 464    STRICT_LOW is the 1 if there is a containing STRICT_LOW_PART rtx.
 465
 466    OPTIONAL nonzero means this reload does not need to be performed:
 467    it can be discarded if that is more convenient.
 468
 469    The return value is the reload-number for this reload.
 470
 471    If both IN and OUT are nonzero, in some rare cases we might
 472    want to make two separate reloads.  (Actually we never do this now.)
 473    Therefore, the reload-number for OUT is stored in
 474    output_reloadnum when we return; the return value applies to IN.
 475    Usually (presently always), when IN and OUT are nonzero,
 476    the two reload-numbers are equal, but the caller should be careful to
 477    distinguish them.  */
 478
 479 static int
 480 push_reload (in, out, inloc, outloc, class,
 481              inmode, outmode, strict_low, optional, needed_for)
 482      register rtx in, out;
 483      rtx *inloc, *outloc;
 484      enum reg_class class;
 485      enum machine_mode inmode, outmode;
 486      int strict_low;
 487      int optional;
 488      rtx needed_for;
 489 {
 490   register int i;
 491   int dont_share = 0;
 492   rtx *in_subreg_loc = 0, *out_subreg_loc = 0;
 493   int secondary_reload = -1;
 494   enum insn_code secondary_icode = CODE_FOR_nothing;
 495
 496   /* Compare two RTX's.  */
 497 #define MATCHES(x, y) \
 498  (x == y || (x != 0 && (GET_CODE (x) == REG                             \
 499                         ? GET_CODE (y) == REG && REGNO (x) == REGNO (y) \
 500                         : rtx_equal_p (x, y) && ! side_effects_p (x))))
 501
 502   /* INMODE and/or OUTMODE could be VOIDmode if no mode
 503      has been specified for the operand.  In that case,
 504      use the operand's mode as the mode to reload.  */
 505   if (inmode == VOIDmode && in != 0)
 506     inmode = GET_MODE (in);
 507   if (outmode == VOIDmode && out != 0)
 508     outmode = GET_MODE (out);
 509
 510   /* If IN is a pseudo register everywhere-equivalent to a constant, and
 511      it is not in a hard register, reload straight from the constant,
 512      since we want to get rid of such pseudo registers.
 513      Often this is done earlier, but not always in find_reloads_address.  */
 514   if (in != 0 && GET_CODE (in) == REG)
 515     {
 516       register int regno = REGNO (in);
 517
 518       if (regno >= FIRST_PSEUDO_REGISTER && reg_renumber[regno] < 0
 519           && reg_equiv_constant[regno] != 0)
 520         in = reg_equiv_constant[regno];
 521     }
 522
 523   /* Likewise for OUT.  Of course, OUT will never be equivalent to
 524      an actual constant, but it might be equivalent to a memory location
 525      (in the case of a parameter).  */
 526   if (out != 0 && GET_CODE (out) == REG)
 527     {
 528       register int regno = REGNO (out);
 529
 530       if (regno >= FIRST_PSEUDO_REGISTER && reg_renumber[regno] < 0
 531           && reg_equiv_constant[regno] != 0)
 532         out = reg_equiv_constant[regno];
 533     }
 534
 535   /* If we have a read-write operand with an address side-effect,
 536      change either IN or OUT so the side-effect happens only once.  */
 537   if (in != 0 && out != 0 && GET_CODE (in) == MEM && rtx_equal_p (in, out))
 538     {
 539       if (GET_CODE (XEXP (in, 0)) == POST_INC
 540           || GET_CODE (XEXP (in, 0)) == POST_DEC)
 541         in = gen_rtx (MEM, GET_MODE (in), XEXP (XEXP (in, 0), 0));
 542       if (GET_CODE (XEXP (in, 0)) == PRE_INC
 543           || GET_CODE (XEXP (in, 0)) == PRE_DEC)
 544         out = gen_rtx (MEM, GET_MODE (out), XEXP (XEXP (out, 0), 0));
 545     }
 546
 547   /* If we are reloading a (SUBREG (MEM ...) ...) or (SUBREG constant ...),
 548      really reload just the inside expression in its own mode.
 549      If we have (SUBREG:M1 (REG:M2 ...) ...) with M1 wider than M2 and the
 550      register is a pseudo, this will become the same as the above case.
 551      Do the same for (SUBREG:M1 (REG:M2 ...) ...) for a hard register R where
 552      either M1 is not valid for R or M2 is wider than a word but we only
 553      need one word to store an M2-sized quantity in R.
 554      Note that the case of (SUBREG (CONST_INT...)...) is handled elsewhere;
 555      we can't handle it here because CONST_INT does not indicate a mode.
 556
 557      Similarly, we must reload the inside expression if we have a
 558      STRICT_LOW_PART (presumably, in == out in the cas).
 559
 560      Also reload the inner expression if it does not require a secondary
 561      reload but the SUBREG does.  */
 562
 563   if (in != 0 && GET_CODE (in) == SUBREG
 564       && (GET_CODE (SUBREG_REG (in)) != REG
 565           || strict_low
 566           || (GET_CODE (SUBREG_REG (in)) == REG
 567               && REGNO (SUBREG_REG (in)) >= FIRST_PSEUDO_REGISTER
 568               && (GET_MODE_SIZE (inmode)
 569                   > GET_MODE_SIZE (GET_MODE (SUBREG_REG (in)))))
 570           || (GET_CODE (SUBREG_REG (in)) == REG
 571               && REGNO (SUBREG_REG (in)) < FIRST_PSEUDO_REGISTER
 572               && (! HARD_REGNO_MODE_OK (REGNO (SUBREG_REG (in)), inmode)
 573                   || (GET_MODE_SIZE (inmode) <= UNITS_PER_WORD
 574                       && (GET_MODE_SIZE (GET_MODE (SUBREG_REG (in)))
 575                           > UNITS_PER_WORD)
 576                       && ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (in)))
 577                            / UNITS_PER_WORD)
 578                           != HARD_REGNO_NREGS (REGNO (SUBREG_REG (in)),
 579                                                GET_MODE (SUBREG_REG (in)))))))
 580 #ifdef SECONDARY_INPUT_RELOAD_CLASS
 581           || (SECONDARY_INPUT_RELOAD_CLASS (class, inmode, in) != NO_REGS
 582               && (SECONDARY_INPUT_RELOAD_CLASS (class,
 583                                                 GET_MODE (SUBREG_REG (in)),
 584                                                 SUBREG_REG (in))
 585                   == NO_REGS))
 586 #endif
 587           ))
 588     {
 589       in_subreg_loc = inloc;
 590       inloc = &SUBREG_REG (in);
 591       in = *inloc;
 592       if (GET_CODE (in) == MEM)
 593         /* This is supposed to happen only for paradoxical subregs made by
 594            combine.c.  (SUBREG (MEM)) isn't supposed to occur other ways.  */
 595         if (GET_MODE_SIZE (GET_MODE (in)) > GET_MODE_SIZE (inmode))
 596           abort ();
 597       inmode = GET_MODE (in);
 598     }
 599
 600   /* Similarly for paradoxical and problematical SUBREGs on the output.
 601      Note that there is no reason we need worry about the previous value
 602      of SUBREG_REG (out); even if wider than out,
 603      storing in a subreg is entitled to clobber it all
 604      (except in the case of STRICT_LOW_PART,
 605      and in that case the constraint should label it input-output.)  */
 606   if (out != 0 && GET_CODE (out) == SUBREG
 607       && (GET_CODE (SUBREG_REG (out)) != REG
 608           || strict_low
 609           || (GET_CODE (SUBREG_REG (out)) == REG
 610               && REGNO (SUBREG_REG (out)) >= FIRST_PSEUDO_REGISTER
 611               && (GET_MODE_SIZE (outmode)
 612                   > GET_MODE_SIZE (GET_MODE (SUBREG_REG (out)))))
 613           || (GET_CODE (SUBREG_REG (out)) == REG
 614               && REGNO (SUBREG_REG (out)) < FIRST_PSEUDO_REGISTER
 615               && (! HARD_REGNO_MODE_OK (REGNO (SUBREG_REG (out)), outmode)
 616                   || (GET_MODE_SIZE (outmode) <= UNITS_PER_WORD
 617                       && (GET_MODE_SIZE (GET_MODE (SUBREG_REG (out)))
 618                           > UNITS_PER_WORD)
 619                       && ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (out)))
 620                            / UNITS_PER_WORD)
 621                           != HARD_REGNO_NREGS (REGNO (SUBREG_REG (out)),
 622                                                GET_MODE (SUBREG_REG (out)))))))
 623 #ifdef SECONDARY_OUTPUT_RELOAD_CLASS
 624           || (SECONDARY_OUTPUT_RELOAD_CLASS (class, outmode, out) != NO_REGS
 625               && (SECONDARY_OUTPUT_RELOAD_CLASS (class,
 626                                                  GET_MODE (SUBREG_REG (out)),
 627                                                  SUBREG_REG (out))
 628                   == NO_REGS))
 629 #endif
 630           ))
 631     {
 632       out_subreg_loc = outloc;
 633       outloc = &SUBREG_REG (out);
 634       out = *outloc;
 635       if (GET_CODE (out) == MEM
 636           && GET_MODE_SIZE (GET_MODE (out)) > GET_MODE_SIZE (outmode))
 637         abort ();
 638       outmode = GET_MODE (out);
 639     }
 640
 641   /* That's all we use STRICT_LOW for, so clear it.  At some point,
 642      we may want to get rid of reload_strict_low.  */
 643   strict_low = 0;
 644
 645   /* If IN appears in OUT, we can't share any input-only reload for IN.  */
 646   if (in != 0 && out != 0 && GET_CODE (out) == MEM
 647       && (GET_CODE (in) == REG || GET_CODE (in) == MEM)
 648       && reg_overlap_mentioned_for_reload_p (in, XEXP (out, 0)))
 649     dont_share = 1;
 650
 651   /* If IN is a SUBREG of a hard register, make a new REG.  This
 652      simplifies some of the cases below.  */
 653
 654   if (in != 0 && GET_CODE (in) == SUBREG && GET_CODE (SUBREG_REG (in)) == REG
 655       && REGNO (SUBREG_REG (in)) < FIRST_PSEUDO_REGISTER)
 656     in = gen_rtx (REG, GET_MODE (in),
 657                   REGNO (SUBREG_REG (in)) + SUBREG_WORD (in));
 658
 659   /* Similarly for OUT.  */
 660   if (out != 0 && GET_CODE (out) == SUBREG
 661       && GET_CODE (SUBREG_REG (out)) == REG
 662       && REGNO (SUBREG_REG (out)) < FIRST_PSEUDO_REGISTER)
 663     out = gen_rtx (REG, GET_MODE (out),
 664                   REGNO (SUBREG_REG (out)) + SUBREG_WORD (out));
 665
 666   /* Narrow down the class of register wanted if that is
 667      desirable on this machine for efficiency.  */
 668   if (in != 0)
 669     class = PREFERRED_RELOAD_CLASS (in, class);
 670
 671   /* Output reloads may need analagous treatment, different in detail.  */
 672 #ifdef PREFERRED_OUTPUT_RELOAD_CLASS
 673   if (out != 0)
 674     class = PREFERRED_OUTPUT_RELOAD_CLASS (out, class);
 675 #endif
 676
 677   /* Make sure we use a class that can handle the actual pseudo
 678      inside any subreg.  For example, on the 386, QImode regs
 679      can appear within SImode subregs.  Although GENERAL_REGS
 680      can handle SImode, QImode needs a smaller class.  */
 681 #ifdef LIMIT_RELOAD_CLASS
 682   if (in_subreg_loc)
 683     class = LIMIT_RELOAD_CLASS (inmode, class);
 684   else if (in != 0 && GET_CODE (in) == SUBREG)
 685     class = LIMIT_RELOAD_CLASS (GET_MODE (SUBREG_REG (in)), class);
 686
 687   if (out_subreg_loc)
 688     class = LIMIT_RELOAD_CLASS (outmode, class);
 689   if (out != 0 && GET_CODE (out) == SUBREG)
 690     class = LIMIT_RELOAD_CLASS (GET_MODE (SUBREG_REG (out)), class);
 691 #endif
 692
 693   if (class == NO_REGS)
 694     abort ();
 695
 696   /* Verify that this class is at least possible for the mode that
 697      is specified.  */
 698   if (this_insn_is_asm)
 699     {
 700       enum machine_mode mode;
 701       if (GET_MODE_SIZE (inmode) > GET_MODE_SIZE (outmode))
 702         mode = inmode;
 703       else
 704         mode = outmode;
 705       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 706         if (HARD_REGNO_MODE_OK (i, mode)
 707             && TEST_HARD_REG_BIT (reg_class_contents[(int) class], i))
 708           {
 709             int nregs = HARD_REGNO_NREGS (i, mode);
 710
 711             int j;
 712             for (j = 1; j < nregs; j++)
 713               if (! TEST_HARD_REG_BIT (reg_class_contents[(int) class], i + j))
 714                 break;
 715             if (j == nregs)
 716               break;
 717           }
 718       if (i == FIRST_PSEUDO_REGISTER)
 719         {
 720           error_for_asm (this_insn, "impossible register constraint in `asm'");
 721           class = ALL_REGS;
 722         }
 723     }
 724
 725   /* We can use an existing reload if the class is right
 726      and at least one of IN and OUT is a match
 727      and the other is at worst neutral.
 728      (A zero compared against anything is neutral.)  */
 729   for (i = 0; i < n_reloads; i++)
 730     if ((reg_class_subset_p (class, reload_reg_class[i])
 731          || reg_class_subset_p (reload_reg_class[i], class))
 732         && reload_strict_low[i] == strict_low
 733         /* If the existing reload has a register, it must fit our class.  */
 734         && (reload_reg_rtx[i] == 0
 735             || TEST_HARD_REG_BIT (reg_class_contents[(int) class],
 736                                   true_regnum (reload_reg_rtx[i])))
 737         && ((in != 0 && MATCHES (reload_in[i], in) && ! dont_share
 738              && (out == 0 || reload_out[i] == 0 || MATCHES (reload_out[i], out)))
 739             ||
 740             (out != 0 && MATCHES (reload_out[i], out)
 741              && (in == 0 || reload_in[i] == 0 || MATCHES (reload_in[i], in)))))
 742       break;
 743
 744   /* Reloading a plain reg for input can match a reload to postincrement
 745      that reg, since the postincrement's value is the right value.
 746      Likewise, it can match a preincrement reload, since we regard
 747      the preincrementation as happening before any ref in this insn
 748      to that register.  */
 749   if (i == n_reloads)
 750     for (i = 0; i < n_reloads; i++)
 751       if ((reg_class_subset_p (class, reload_reg_class[i])
 752            || reg_class_subset_p (reload_reg_class[i], class))
 753           /* If the existing reload has a register, it must fit our class.  */
 754           && (reload_reg_rtx[i] == 0
 755               || TEST_HARD_REG_BIT (reg_class_contents[(int) class],
 756                                     true_regnum (reload_reg_rtx[i])))
 757           && reload_strict_low[i] == strict_low
 758           && out == 0 && reload_out[i] == 0 && reload_in[i] != 0
 759           && ((GET_CODE (in) == REG
 760                && (GET_CODE (reload_in[i]) == POST_INC
 761                    || GET_CODE (reload_in[i]) == POST_DEC
 762                    || GET_CODE (reload_in[i]) == PRE_INC
 763                    || GET_CODE (reload_in[i]) == PRE_DEC)
 764                && MATCHES (XEXP (reload_in[i], 0), in))
 765               ||
 766               (GET_CODE (reload_in[i]) == REG
 767                && (GET_CODE (in) == POST_INC
 768                    || GET_CODE (in) == POST_DEC
 769                    || GET_CODE (in) == PRE_INC
 770                    || GET_CODE (in) == PRE_DEC)
 771                && MATCHES (XEXP (in, 0), reload_in[i]))))
 772         {
 773           /* Make sure reload_in ultimately has the increment,
 774              not the plain register.  */
 775           if (GET_CODE (in) == REG)
 776             in = reload_in[i];
 777           break;
 778         }
 779
 780   if (i == n_reloads)
 781     {
 782 #ifdef HAVE_SECONDARY_RELOADS
 783       enum reg_class secondary_class = NO_REGS;
 784       enum reg_class secondary_out_class = NO_REGS;
 785       enum machine_mode secondary_mode = inmode;
 786       enum machine_mode secondary_out_mode = outmode;
 787       enum insn_code secondary_icode;
 788       enum insn_code secondary_out_icode = CODE_FOR_nothing;
 789       enum reg_class tertiary_class = NO_REGS;
 790       enum reg_class tertiary_out_class = NO_REGS;
 791       enum machine_mode tertiary_mode;
 792       enum machine_mode tertiary_out_mode;
 793       enum insn_code tertiary_icode;
 794       enum insn_code tertiary_out_icode = CODE_FOR_nothing;
 795       int tertiary_reload = -1;
 796
 797       /* See if we need a secondary reload register to move between
 798          CLASS and IN or CLASS and OUT.  Get the modes and icodes to
 799          use for each of them if so.  */
 800
 801 #ifdef SECONDARY_INPUT_RELOAD_CLASS
 802       if (in != 0)
 803         secondary_class
 804           = find_secondary_reload (in, class, inmode, 1, &secondary_icode,
 805                                    &secondary_mode, &tertiary_class,
 806                                    &tertiary_icode, &tertiary_mode);
 807 #endif
 808
 809 #ifdef SECONDARY_OUTPUT_RELOAD_CLASS
 810       if (out != 0 && GET_CODE (out) != SCRATCH)
 811         secondary_out_class
 812           = find_secondary_reload (out, class, outmode, 0,
 813                                    &secondary_out_icode, &secondary_out_mode,
 814                                    &tertiary_out_class, &tertiary_out_icode,
 815                                    &tertiary_out_mode);
 816 #endif
 817
 818       /* We can only record one secondary and one tertiary reload.  If both
 819          IN and OUT need secondary reloads, we can only make an in-out
 820          reload if neither need an insn and if the classes are compatible.  */
 821
 822       if (secondary_class != NO_REGS && secondary_out_class != NO_REGS
 823           && reg_class_subset_p (secondary_out_class, secondary_class))
 824         secondary_class = secondary_out_class;
 825
 826       if (secondary_class != NO_REGS && secondary_out_class != NO_REGS
 827           && (! reg_class_subset_p (secondary_class, secondary_out_class)
 828               || secondary_icode != CODE_FOR_nothing
 829               || secondary_out_icode != CODE_FOR_nothing))
 830         {
 831           push_reload (NULL_RTX, out, NULL_PTR, outloc, class,
 832                        VOIDmode, outmode, strict_low, optional, needed_for);
 833           out = 0;
 834           outloc = 0;
 835           outmode = VOIDmode;
 836         }
 837
 838       /* If we need a secondary reload for OUT but not IN, copy the
 839          information.  */
 840       if (secondary_class == NO_REGS && secondary_out_class != NO_REGS)
 841         {
 842           secondary_class = secondary_out_class;
 843           secondary_icode = secondary_out_icode;
 844           tertiary_class = tertiary_out_class;
 845           tertiary_icode = tertiary_out_icode;
 846           tertiary_mode = tertiary_out_mode;
 847         }
 848
 849       if (secondary_class != NO_REGS)
 850         {
 851           /* If we need a tertiary reload, see if we have one we can reuse
 852              or else make one.  */
 853
 854           if (tertiary_class != NO_REGS)
 855             {
 856               for (tertiary_reload = 0; tertiary_reload < n_reloads;
 857                    tertiary_reload++)
 858                 if (reload_secondary_p[tertiary_reload]
 859                     && (reg_class_subset_p (tertiary_class,
 860                                             reload_reg_class[tertiary_reload])
 861                         || reg_class_subset_p (reload_reg_class[tertiary_reload],
 862                                                tertiary_class))
 863                     && ((reload_inmode[tertiary_reload] == tertiary_mode)
 864                         || reload_inmode[tertiary_reload] == VOIDmode)
 865                     && ((reload_outmode[tertiary_reload] == tertiary_mode)
 866                         || reload_outmode[tertiary_reload] == VOIDmode)
 867                     && (reload_secondary_icode[tertiary_reload]
 868                         == CODE_FOR_nothing))
 869
 870                   {
 871                     if (tertiary_mode != VOIDmode)
 872                       reload_inmode[tertiary_reload] = tertiary_mode;
 873                     if (tertiary_out_mode != VOIDmode)
 874                       reload_outmode[tertiary_reload] = tertiary_mode;
 875                     if (reg_class_subset_p (tertiary_class,
 876                                             reload_reg_class[tertiary_reload]))
 877                       reload_reg_class[tertiary_reload] = tertiary_class;
 878                     if (reload_needed_for[tertiary_reload] != needed_for)
 879                       reload_needed_for_multiple[tertiary_reload] = 1;
 880                     reload_optional[tertiary_reload] &= optional;
 881                     reload_secondary_p[tertiary_reload] = 1;
 882                   }
 883
 884               if (tertiary_reload == n_reloads)
 885                 {
 886                   /* We need to make a new tertiary reload for this register
 887                      class.  */
 888                   reload_in[tertiary_reload] = reload_out[tertiary_reload] = 0;
 889                   reload_reg_class[tertiary_reload] = tertiary_class;
 890                   reload_inmode[tertiary_reload] = tertiary_mode;
 891                   reload_outmode[tertiary_reload] = tertiary_mode;
 892                   reload_reg_rtx[tertiary_reload] = 0;
 893                   reload_optional[tertiary_reload] = optional;
 894                   reload_inc[tertiary_reload] = 0;
 895                   reload_strict_low[tertiary_reload] = 0;
 896                   /* Maybe we could combine these, but it seems too tricky.  */
 897                   reload_nocombine[tertiary_reload] = 1;
 898                   reload_in_reg[tertiary_reload] = 0;
 899                   reload_needed_for[tertiary_reload] = needed_for;
 900                   reload_needed_for_multiple[tertiary_reload] = 0;
 901                   reload_secondary_reload[tertiary_reload] = -1;
 902                   reload_secondary_icode[tertiary_reload] = CODE_FOR_nothing;
 903                   reload_secondary_p[tertiary_reload] = 1;
 904
 905                   n_reloads++;
 906                   i = n_reloads;
 907                 }
 908             }
 909
 910           /* See if we can reuse an existing secondary reload.  */
 911           for (secondary_reload = 0; secondary_reload < n_reloads;
 912                secondary_reload++)
 913             if (reload_secondary_p[secondary_reload]
 914                 && (reg_class_subset_p (secondary_class,
 915                                         reload_reg_class[secondary_reload])
 916                     || reg_class_subset_p (reload_reg_class[secondary_reload],
 917                                            secondary_class))
 918                 && ((reload_inmode[secondary_reload] == secondary_mode)
 919                     || reload_inmode[secondary_reload] == VOIDmode)
 920                 && ((reload_outmode[secondary_reload] == secondary_out_mode)
 921                     || reload_outmode[secondary_reload] == VOIDmode)
 922                 && reload_secondary_reload[secondary_reload] == tertiary_reload
 923                 && reload_secondary_icode[secondary_reload] == tertiary_icode)
 924               {
 925                 if (secondary_mode != VOIDmode)
 926                   reload_inmode[secondary_reload] = secondary_mode;
 927                 if (secondary_out_mode != VOIDmode)
 928                   reload_outmode[secondary_reload] = secondary_out_mode;
 929                 if (reg_class_subset_p (secondary_class,
 930                                         reload_reg_class[secondary_reload]))
 931                   reload_reg_class[secondary_reload] = secondary_class;
 932                 if (reload_needed_for[secondary_reload] != needed_for)
 933                   reload_needed_for_multiple[secondary_reload] = 1;
 934                 reload_optional[secondary_reload] &= optional;
 935                 reload_secondary_p[secondary_reload] = 1;
 936               }
 937
 938           if (secondary_reload == n_reloads)
 939             {
 940               /* We need to make a new secondary reload for this register
 941                  class.  */
 942               reload_in[secondary_reload] = reload_out[secondary_reload] = 0;
 943               reload_reg_class[secondary_reload] = secondary_class;
 944               reload_inmode[secondary_reload] = secondary_mode;
 945               reload_outmode[secondary_reload] = secondary_out_mode;
 946               reload_reg_rtx[secondary_reload] = 0;
 947               reload_optional[secondary_reload] = optional;
 948               reload_inc[secondary_reload] = 0;
 949               reload_strict_low[secondary_reload] = 0;
 950               /* Maybe we could combine these, but it seems too tricky.  */
 951               reload_nocombine[secondary_reload] = 1;
 952               reload_in_reg[secondary_reload] = 0;
 953               reload_needed_for[secondary_reload] = needed_for;
 954               reload_needed_for_multiple[secondary_reload] = 0;
 955               reload_secondary_reload[secondary_reload] = tertiary_reload;
 956               reload_secondary_icode[secondary_reload] = tertiary_icode;
 957               reload_secondary_p[secondary_reload] = 1;
 958
 959               n_reloads++;
 960               i = n_reloads;
 961
 962 #ifdef SECONDARY_MEMORY_NEEDED
 963               /* If we need a memory location to copy between the two
 964                  reload regs, set it up now.  */
 965
 966               if (in != 0 && secondary_icode == CODE_FOR_nothing
 967                   && SECONDARY_MEMORY_NEEDED (secondary_class, class, inmode))
 968                 get_secondary_mem (in, inmode);
 969
 970               if (out != 0 && secondary_icode == CODE_FOR_nothing
 971                   && SECONDARY_MEMORY_NEEDED (class, secondary_class, outmode))
 972                 get_secondary_mem (out, outmode);
 973 #endif
 974             }
 975         }
 976 #endif
 977
 978       /* We found no existing reload suitable for re-use.
 979          So add an additional reload.  */
 980
 981       reload_in[i] = in;
 982       reload_out[i] = out;
 983       reload_reg_class[i] = class;
 984       reload_inmode[i] = inmode;
 985       reload_outmode[i] = outmode;
 986       reload_reg_rtx[i] = 0;
 987       reload_optional[i] = optional;
 988       reload_inc[i] = 0;
 989       reload_strict_low[i] = strict_low;
 990       reload_nocombine[i] = 0;
 991       reload_in_reg[i] = inloc ? *inloc : 0;
 992       reload_needed_for[i] = needed_for;
 993       reload_needed_for_multiple[i] = 0;
 994       reload_secondary_reload[i] = secondary_reload;
 995       reload_secondary_icode[i] = secondary_icode;
 996       reload_secondary_p[i] = 0;
 997
 998       n_reloads++;
 999
1000 #ifdef SECONDARY_MEMORY_NEEDED
1001       /* If a memory location is needed for the copy, make one.  */
1002       if (in != 0 && GET_CODE (in) == REG
1003           && REGNO (in) < FIRST_PSEUDO_REGISTER
1004           && SECONDARY_MEMORY_NEEDED (REGNO_REG_CLASS (REGNO (in)),
1005                                      class, inmode))
1006         get_secondary_mem (in, inmode);
1007
1008       if (out != 0 && GET_CODE (out) == REG
1009           && REGNO (out) < FIRST_PSEUDO_REGISTER
1010           && SECONDARY_MEMORY_NEEDED (class, REGNO_REG_CLASS (REGNO (out)),
1011                                       outmode))
1012         get_secondary_mem (out, outmode);
1013 #endif
1014     }
1015   else
1016     {
1017       /* We are reusing an existing reload,
1018          but we may have additional information for it.
1019          For example, we may now have both IN and OUT
1020          while the old one may have just one of them.  */
1021
1022       if (inmode != VOIDmode)
1023         reload_inmode[i] = inmode;
1024       if (outmode != VOIDmode)
1025         reload_outmode[i] = outmode;
1026       if (in != 0)
1027         reload_in[i] = in;
1028       if (out != 0)
1029         reload_out[i] = out;
1030       if (reg_class_subset_p (class, reload_reg_class[i]))
1031         reload_reg_class[i] = class;
1032       reload_optional[i] &= optional;
1033       if (reload_needed_for[i] != needed_for)
1034         reload_needed_for_multiple[i] = 1;
1035     }
1036
1037   /* If the ostensible rtx being reload differs from the rtx found
1038      in the location to substitute, this reload is not safe to combine
1039      because we cannot reliably tell whether it appears in the insn.  */
1040
1041   if (in != 0 && in != *inloc)
1042     reload_nocombine[i] = 1;
1043
1044 #if 0
1045   /* This was replaced by changes in find_reloads_address_1 and the new
1046      function inc_for_reload, which go with a new meaning of reload_inc.  */
1047
1048   /* If this is an IN/OUT reload in an insn that sets the CC,
1049      it must be for an autoincrement.  It doesn't work to store
1050      the incremented value after the insn because that would clobber the CC.
1051      So we must do the increment of the value reloaded from,
1052      increment it, store it back, then decrement again.  */
1053   if (out != 0 && sets_cc0_p (PATTERN (this_insn)))
1054     {
1055       out = 0;
1056       reload_out[i] = 0;
1057       reload_inc[i] = find_inc_amount (PATTERN (this_insn), in);
1058       /* If we did not find a nonzero amount-to-increment-by,
1059          that contradicts the belief that IN is being incremented
1060          in an address in this insn.  */
1061       if (reload_inc[i] == 0)
1062         abort ();
1063     }
1064 #endif
1065
1066   /* If we will replace IN and OUT with the reload-reg,
1067      record where they are located so that substitution need
1068      not do a tree walk.  */
1069
1070   if (replace_reloads)
1071     {
1072       if (inloc != 0)
1073         {
1074           register struct replacement *r = &replacements[n_replacements++];
1075           r->what = i;
1076           r->subreg_loc = in_subreg_loc;
1077           r->where = inloc;
1078           r->mode = inmode;
1079         }
1080       if (outloc != 0 && outloc != inloc)
1081         {
1082           register struct replacement *r = &replacements[n_replacements++];
1083           r->what = i;
1084           r->where = outloc;
1085           r->subreg_loc = out_subreg_loc;
1086           r->mode = outmode;
1087         }
1088     }
1089
1090   /* If this reload is just being introduced and it has both
1091      an incoming quantity and an outgoing quantity that are
1092      supposed to be made to match, see if either one of the two
1093      can serve as the place to reload into.
1094
1095      If one of them is acceptable, set reload_reg_rtx[i]
1096      to that one.  */
1097
1098   if (in != 0 && out != 0 && in != out && reload_reg_rtx[i] == 0)
1099     {
1100       reload_reg_rtx[i] = find_dummy_reload (in, out, inloc, outloc,
1101                                              reload_reg_class[i], i);
1102
1103       /* If the outgoing register already contains the same value
1104          as the incoming one, we can dispense with loading it.
1105          The easiest way to tell the caller that is to give a phony
1106          value for the incoming operand (same as outgoing one).  */
1107       if (reload_reg_rtx[i] == out
1108           && (GET_CODE (in) == REG || CONSTANT_P (in))
1109           && 0 != find_equiv_reg (in, this_insn, 0, REGNO (out),
1110                                   static_reload_reg_p, i, inmode))
1111         reload_in[i] = out;
1112     }
1113
1114   /* If this is an input reload and the operand contains a register that
1115      dies in this insn and is used nowhere else, see if it is the right class
1116      to be used for this reload.  Use it if so.  (This occurs most commonly
1117      in the case of paradoxical SUBREGs and in-out reloads).  We cannot do
1118      this if it is also an output reload that mentions the register unless
1119      the output is a SUBREG that clobbers an entire register.
1120
1121      Note that the operand might be one of the spill regs, if it is a
1122      pseudo reg and we are in a block where spilling has not taken place.
1123      But if there is no spilling in this block, that is OK.
1124      An explicitly used hard reg cannot be a spill reg.  */
1125
1126   if (reload_reg_rtx[i] == 0 && in != 0)
1127     {
1128       rtx note;
1129       int regno;
1130
1131       for (note = REG_NOTES (this_insn); note; note = XEXP (note, 1))
1132         if (REG_NOTE_KIND (note) == REG_DEAD
1133             && GET_CODE (XEXP (note, 0)) == REG
1134             && (regno = REGNO (XEXP (note, 0))) < FIRST_PSEUDO_REGISTER
1135             && reg_mentioned_p (XEXP (note, 0), in)
1136             && ! refers_to_regno_for_reload_p (regno,
1137                                                (regno
1138                                                 + HARD_REGNO_NREGS (regno,
1139                                                                     inmode)),
1140                                                PATTERN (this_insn), inloc)
1141             && (in != out
1142                 || (GET_CODE (in) == SUBREG
1143                     && (((GET_MODE_SIZE (GET_MODE (in)) + (UNITS_PER_WORD - 1))
1144                          / UNITS_PER_WORD)
1145                         == ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (in)))
1146                              + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD))))
1147             /* Make sure the operand fits in the reg that dies.  */
1148             && GET_MODE_SIZE (inmode) <= GET_MODE_SIZE (GET_MODE (XEXP (note, 0)))
1149             && HARD_REGNO_MODE_OK (regno, inmode)
1150             && GET_MODE_SIZE (outmode) <= GET_MODE_SIZE (GET_MODE (XEXP (note, 0)))
1151             && HARD_REGNO_MODE_OK (regno, outmode)
1152             && TEST_HARD_REG_BIT (reg_class_contents[(int) class], regno)
1153             && !fixed_regs[regno])
1154           {
1155             reload_reg_rtx[i] = gen_rtx (REG, inmode, regno);
1156             break;
1157           }
1158     }
1159
1160   if (out)
1161     output_reloadnum = i;
1162
1163   return i;
1164 }
1165
1166 /* Record an additional place we must replace a value
1167    for which we have already recorded a reload.
1168    RELOADNUM is the value returned by push_reload
1169    when the reload was recorded.
1170    This is used in insn patterns that use match_dup.  */
1171
1172 static void
1173 push_replacement (loc, reloadnum, mode)
1174      rtx *loc;
1175      int reloadnum;
1176      enum machine_mode mode;
1177 {
1178   if (replace_reloads)
1179     {
1180       register struct replacement *r = &replacements[n_replacements++];
1181       r->what = reloadnum;
1182       r->where = loc;
1183       r->subreg_loc = 0;
1184       r->mode = mode;
1185     }
1186 }
1187 \f
1188 /* If there is only one output reload, and it is not for an earlyclobber
1189    operand, try to combine it with a (logically unrelated) input reload
1190    to reduce the number of reload registers needed.
1191
1192    This is safe if the input reload does not appear in
1193    the value being output-reloaded, because this implies
1194    it is not needed any more once the original insn completes.
1195
1196    If that doesn't work, see we can use any of the registers that
1197    die in this insn as a reload register.  We can if it is of the right
1198    class and does not appear in the value being output-reloaded.  */
1199
1200 static void
1201 combine_reloads ()
1202 {
1203   int i;
1204   int output_reload = -1;
1205   rtx note;
1206
1207   /* Find the output reload; return unless there is exactly one
1208      and that one is mandatory.  */
1209
1210   for (i = 0; i < n_reloads; i++)
1211     if (reload_out[i] != 0)
1212       {
1213         if (output_reload >= 0)
1214           return;
1215         output_reload = i;
1216       }
1217
1218   if (output_reload < 0 || reload_optional[output_reload])
1219     return;
1220
1221   /* An input-output reload isn't combinable.  */
1222
1223   if (reload_in[output_reload] != 0)
1224     return;
1225
1226   /* If this reload is for an earlyclobber operand, we can't do anything.  */
1227
1228   for (i = 0; i < n_earlyclobbers; i++)
1229     if (reload_out[output_reload] == reload_earlyclobbers[i])
1230       return;
1231
1232   /* Check each input reload; can we combine it?  */
1233
1234   for (i = 0; i < n_reloads; i++)
1235     if (reload_in[i] && ! reload_optional[i] && ! reload_nocombine[i]
1236         /* Life span of this reload must not extend past main insn.  */
1237         && reload_when_needed[i] != RELOAD_FOR_OUTPUT_RELOAD_ADDRESS
1238         && reload_inmode[i] == reload_outmode[output_reload]
1239         && reload_inc[i] == 0
1240         && reload_reg_rtx[i] == 0
1241         && reload_strict_low[i] == 0
1242         /* Don't combine two reloads with different secondary reloads. */
1243         && (reload_secondary_reload[i] == reload_secondary_reload[output_reload]
1244             || reload_secondary_reload[i] == -1
1245             || reload_secondary_reload[output_reload] == -1)
1246         && (reg_class_subset_p (reload_reg_class[i],
1247                                 reload_reg_class[output_reload])
1248             || reg_class_subset_p (reload_reg_class[output_reload],
1249                                    reload_reg_class[i]))
1250         && (MATCHES (reload_in[i], reload_out[output_reload])
1251             /* Args reversed because the first arg seems to be
1252                the one that we imagine being modified
1253                while the second is the one that might be affected.  */
1254             || (! reg_overlap_mentioned_for_reload_p (reload_out[output_reload],
1255                                                       reload_in[i])
1256                 /* However, if the input is a register that appears inside
1257                    the output, then we also can't share.
1258                    Imagine (set (mem (reg 69)) (plus (reg 69) ...)).
1259                    If the same reload reg is used for both reg 69 and the
1260                    result to be stored in memory, then that result
1261                    will clobber the address of the memory ref.  */
1262                 && ! (GET_CODE (reload_in[i]) == REG
1263                       && reg_overlap_mentioned_for_reload_p (reload_in[i],
1264                                                              reload_out[output_reload])))))
1265       {
1266         int j;
1267
1268         /* We have found a reload to combine with!  */
1269         reload_out[i] = reload_out[output_reload];
1270         reload_outmode[i] = reload_outmode[output_reload];
1271         /* Mark the old output reload as inoperative.  */
1272         reload_out[output_reload] = 0;
1273         /* The combined reload is needed for the entire insn.  */
1274         reload_needed_for_multiple[i] = 1;
1275         reload_when_needed[i] = RELOAD_OTHER;
1276         /* If the output reload had a secondary reload, copy it. */
1277         if (reload_secondary_reload[output_reload] != -1)
1278           reload_secondary_reload[i] = reload_secondary_reload[output_reload];
1279         /* If required, minimize the register class. */
1280         if (reg_class_subset_p (reload_reg_class[output_reload],
1281                                 reload_reg_class[i]))
1282           reload_reg_class[i] = reload_reg_class[output_reload];
1283
1284         /* Transfer all replacements from the old reload to the combined.  */
1285         for (j = 0; j < n_replacements; j++)
1286           if (replacements[j].what == output_reload)
1287             replacements[j].what = i;
1288
1289         return;
1290       }
1291
1292   /* If this insn has only one operand that is modified or written (assumed
1293      to be the first),  it must be the one corresponding to this reload.  It
1294      is safe to use anything that dies in this insn for that output provided
1295      that it does not occur in the output (we already know it isn't an
1296      earlyclobber.  If this is an asm insn, give up.  */
1297
1298   if (INSN_CODE (this_insn) == -1)
1299     return;
1300
1301   for (i = 1; i < insn_n_operands[INSN_CODE (this_insn)]; i++)
1302     if (insn_operand_constraint[INSN_CODE (this_insn)][i][0] == '='
1303         || insn_operand_constraint[INSN_CODE (this_insn)][i][0] == '+')
1304       return;
1305
1306   /* See if some hard register that dies in this insn and is not used in
1307      the output is the right class.  Only works if the register we pick
1308      up can fully hold our output reload.  */
1309   for (note = REG_NOTES (this_insn); note; note = XEXP (note, 1))
1310     if (REG_NOTE_KIND (note) == REG_DEAD
1311         && GET_CODE (XEXP (note, 0)) == REG
1312         && ! reg_overlap_mentioned_for_reload_p (XEXP (note, 0),
1313                                                  reload_out[output_reload])
1314         && REGNO (XEXP (note, 0)) < FIRST_PSEUDO_REGISTER
1315         && HARD_REGNO_MODE_OK (REGNO (XEXP (note, 0)), reload_outmode[output_reload])
1316         && TEST_HARD_REG_BIT (reg_class_contents[(int) reload_reg_class[output_reload]],
1317                               REGNO (XEXP (note, 0)))
1318         && (HARD_REGNO_NREGS (REGNO (XEXP (note, 0)), reload_outmode[output_reload])
1319             <= HARD_REGNO_NREGS (REGNO (XEXP (note, 0)), GET_MODE (XEXP (note, 0))))
1320         && ! fixed_regs[REGNO (XEXP (note, 0))])
1321       {
1322         reload_reg_rtx[output_reload] = gen_rtx (REG,
1323                                                  reload_outmode[output_reload],
1324                                                  REGNO (XEXP (note, 0)));
1325         return;
1326       }
1327 }
1328 \f
1329 /* Try to find a reload register for an in-out reload (expressions IN and OUT).
1330    See if one of IN and OUT is a register that may be used;
1331    this is desirable since a spill-register won't be needed.
1332    If so, return the register rtx that proves acceptable.
1333
1334    INLOC and OUTLOC are locations where IN and OUT appear in the insn.
1335    CLASS is the register class required for the reload.
1336
1337    If FOR_REAL is >= 0, it is the number of the reload,
1338    and in some cases when it can be discovered that OUT doesn't need
1339    to be computed, clear out reload_out[FOR_REAL].
1340
1341    If FOR_REAL is -1, this should not be done, because this call
1342    is just to see if a register can be found, not to find and install it.  */
1343
1344 static rtx
1345 find_dummy_reload (real_in, real_out, inloc, outloc, class, for_real)
1346      rtx real_in, real_out;
1347      rtx *inloc, *outloc;
1348      enum reg_class class;
1349      int for_real;
1350 {
1351   rtx in = real_in;
1352   rtx out = real_out;
1353   int in_offset = 0;
1354   int out_offset = 0;
1355   rtx value = 0;
1356
1357   /* If operands exceed a word, we can't use either of them
1358      unless they have the same size.  */
1359   if (GET_MODE_SIZE (GET_MODE (real_out)) != GET_MODE_SIZE (GET_MODE (real_in))
1360       && (GET_MODE_SIZE (GET_MODE (real_out)) > UNITS_PER_WORD
1361           || GET_MODE_SIZE (GET_MODE (real_in)) > UNITS_PER_WORD))
1362     return 0;
1363
1364   /* Find the inside of any subregs.  */
1365   while (GET_CODE (out) == SUBREG)
1366     {
1367       out_offset = SUBREG_WORD (out);
1368       out = SUBREG_REG (out);
1369     }
1370   while (GET_CODE (in) == SUBREG)
1371     {
1372       in_offset = SUBREG_WORD (in);
1373       in = SUBREG_REG (in);
1374     }
1375
1376   /* Narrow down the reg class, the same way push_reload will;
1377      otherwise we might find a dummy now, but push_reload won't.  */
1378   class = PREFERRED_RELOAD_CLASS (in, class);
1379
1380   /* See if OUT will do.  */
1381   if (GET_CODE (out) == REG
1382       && REGNO (out) < FIRST_PSEUDO_REGISTER)
1383     {
1384       register int regno = REGNO (out) + out_offset;
1385       int nwords = HARD_REGNO_NREGS (regno, GET_MODE (real_out));
1386       rtx saved_rtx;
1387
1388       /* When we consider whether the insn uses OUT,
1389          ignore references within IN.  They don't prevent us
1390          from copying IN into OUT, because those refs would
1391          move into the insn that reloads IN.
1392
1393          However, we only ignore IN in its role as this reload.
1394          If the insn uses IN elsewhere and it contains OUT,
1395          that counts.  We can't be sure it's the "same" operand
1396          so it might not go through this reload.  */
1397       saved_rtx = *inloc;
1398       *inloc = const0_rtx;
1399
1400       if (regno < FIRST_PSEUDO_REGISTER
1401           /* A fixed reg that can overlap other regs better not be used
1402              for reloading in any way.  */
1403 #ifdef OVERLAPPING_REGNO_P
1404           && ! (fixed_regs[regno] && OVERLAPPING_REGNO_P (regno))
1405 #endif
1406           && ! refers_to_regno_for_reload_p (regno, regno + nwords,
1407                                              PATTERN (this_insn), outloc))
1408         {
1409           int i;
1410           for (i = 0; i < nwords; i++)
1411             if (! TEST_HARD_REG_BIT (reg_class_contents[(int) class],
1412                                      regno + i))
1413               break;
1414
1415           if (i == nwords)
1416             {
1417               if (GET_CODE (real_out) == REG)
1418                 value = real_out;
1419               else
1420                 value = gen_rtx (REG, GET_MODE (real_out), regno);
1421             }
1422         }
1423
1424       *inloc = saved_rtx;
1425     }
1426
1427   /* Consider using IN if OUT was not acceptable
1428      or if OUT dies in this insn (like the quotient in a divmod insn).
1429      We can't use IN unless it is dies in this insn,
1430      which means we must know accurately which hard regs are live.
1431      Also, the result can't go in IN if IN is used within OUT.  */
1432   if (hard_regs_live_known
1433       && GET_CODE (in) == REG
1434       && REGNO (in) < FIRST_PSEUDO_REGISTER
1435       && (value == 0
1436           || find_reg_note (this_insn, REG_UNUSED, real_out))
1437       && find_reg_note (this_insn, REG_DEAD, real_in)
1438       && !fixed_regs[REGNO (in)]
1439       && HARD_REGNO_MODE_OK (REGNO (in), GET_MODE (out)))
1440     {
1441       register int regno = REGNO (in) + in_offset;
1442       int nwords = HARD_REGNO_NREGS (regno, GET_MODE (real_in));
1443
1444       if (! refers_to_regno_for_reload_p (regno, regno + nwords, out, NULL_PTR)
1445           && ! hard_reg_set_here_p (regno, regno + nwords,
1446                                     PATTERN (this_insn)))
1447         {
1448           int i;
1449           for (i = 0; i < nwords; i++)
1450             if (! TEST_HARD_REG_BIT (reg_class_contents[(int) class],
1451                                      regno + i))
1452               break;
1453
1454           if (i == nwords)
1455             {
1456               /* If we were going to use OUT as the reload reg
1457                  and changed our mind, it means OUT is a dummy that
1458                  dies here.  So don't bother copying value to it.  */
1459               if (for_real >= 0 && value == real_out)
1460                 reload_out[for_real] = 0;
1461               if (GET_CODE (real_in) == REG)
1462                 value = real_in;
1463               else
1464                 value = gen_rtx (REG, GET_MODE (real_in), regno);
1465             }
1466         }
1467     }
1468
1469   return value;
1470 }
1471 \f
1472 /* This page contains subroutines used mainly for determining
1473    whether the IN or an OUT of a reload can serve as the
1474    reload register.  */
1475
1476 /* Return 1 if expression X alters a hard reg in the range
1477    from BEG_REGNO (inclusive) to END_REGNO (exclusive),
1478    either explicitly or in the guise of a pseudo-reg allocated to REGNO.
1479    X should be the body of an instruction.  */
1480
1481 static int
1482 hard_reg_set_here_p (beg_regno, end_regno, x)
1483      register int beg_regno, end_regno;
1484      rtx x;
1485 {
1486   if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
1487     {
1488       register rtx op0 = SET_DEST (x);
1489       while (GET_CODE (op0) == SUBREG)
1490         op0 = SUBREG_REG (op0);
1491       if (GET_CODE (op0) == REG)
1492         {
1493           register int r = REGNO (op0);
1494           /* See if this reg overlaps range under consideration.  */
1495           if (r < end_regno
1496               && r + HARD_REGNO_NREGS (r, GET_MODE (op0)) > beg_regno)
1497             return 1;
1498         }
1499     }
1500   else if (GET_CODE (x) == PARALLEL)
1501     {
1502       register int i = XVECLEN (x, 0) - 1;
1503       for (; i >= 0; i--)
1504         if (hard_reg_set_here_p (beg_regno, end_regno, XVECEXP (x, 0, i)))
1505           return 1;
1506     }
1507
1508   return 0;
1509 }
1510
1511 /* Return 1 if ADDR is a valid memory address for mode MODE,
1512    and check that each pseudo reg has the proper kind of
1513    hard reg.  */
1514
1515 int
1516 strict_memory_address_p (mode, addr)
1517      enum machine_mode mode;
1518      register rtx addr;
1519 {
1520   GO_IF_LEGITIMATE_ADDRESS (mode, addr, win);
1521   return 0;
1522
1523  win:
1524   return 1;
1525 }
1526
1527 \f
1528 /* Like rtx_equal_p except that it allows a REG and a SUBREG to match
1529    if they are the same hard reg, and has special hacks for
1530    autoincrement and autodecrement.
1531    This is specifically intended for find_reloads to use
1532    in determining whether two operands match.
1533    X is the operand whose number is the lower of the two.
1534
1535    The value is 2 if Y contains a pre-increment that matches
1536    a non-incrementing address in X.  */
1537
1538 /* ??? To be completely correct, we should arrange to pass
1539    for X the output operand and for Y the input operand.
1540    For now, we assume that the output operand has the lower number
1541    because that is natural in (SET output (... input ...)).  */
1542
1543 int
1544 operands_match_p (x, y)
1545      register rtx x, y;
1546 {
1547   register int i;
1548   register RTX_CODE code = GET_CODE (x);
1549   register char *fmt;
1550   int success_2;
1551
1552   if (x == y)
1553     return 1;
1554   if ((code == REG || (code == SUBREG && GET_CODE (SUBREG_REG (x)) == REG))
1555       && (GET_CODE (y) == REG || (GET_CODE (y) == SUBREG
1556                                   && GET_CODE (SUBREG_REG (y)) == REG)))
1557     {
1558       register int j;
1559
1560       if (code == SUBREG)
1561         {
1562           i = REGNO (SUBREG_REG (x));
1563           if (i >= FIRST_PSEUDO_REGISTER)
1564             goto slow;
1565           i += SUBREG_WORD (x);
1566         }
1567       else
1568         i = REGNO (x);
1569
1570       if (GET_CODE (y) == SUBREG)
1571         {
1572           j = REGNO (SUBREG_REG (y));
1573           if (j >= FIRST_PSEUDO_REGISTER)
1574             goto slow;
1575           j += SUBREG_WORD (y);
1576         }
1577       else
1578         j = REGNO (y);
1579
1580       return i == j;
1581     }
1582   /* If two operands must match, because they are really a single
1583      operand of an assembler insn, then two postincrements are invalid
1584      because the assembler insn would increment only once.
1585      On the other hand, an postincrement matches ordinary indexing
1586      if the postincrement is the output operand.  */
1587   if (code == POST_DEC || code == POST_INC)
1588     return operands_match_p (XEXP (x, 0), y);
1589   /* Two preincrements are invalid
1590      because the assembler insn would increment only once.
1591      On the other hand, an preincrement matches ordinary indexing
1592      if the preincrement is the input operand.
1593      In this case, return 2, since some callers need to do special
1594      things when this happens.  */
1595   if (GET_CODE (y) == PRE_DEC || GET_CODE (y) == PRE_INC)
1596     return operands_match_p (x, XEXP (y, 0)) ? 2 : 0;
1597
1598  slow:
1599
1600   /* Now we have disposed of all the cases
1601      in which different rtx codes can match.  */
1602   if (code != GET_CODE (y))
1603     return 0;
1604   if (code == LABEL_REF)
1605     return XEXP (x, 0) == XEXP (y, 0);
1606   if (code == SYMBOL_REF)
1607     return XSTR (x, 0) == XSTR (y, 0);
1608
1609   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.  */
1610
1611   if (GET_MODE (x) != GET_MODE (y))
1612     return 0;
1613
1614   /* Compare the elements.  If any pair of corresponding elements
1615      fail to match, return 0 for the whole things.  */
1616
1617   success_2 = 0;
1618   fmt = GET_RTX_FORMAT (code);
1619   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1620     {
1621       int val;
1622       switch (fmt[i])
1623         {
1624         case 'w':
1625           if (XWINT (x, i) != XWINT (y, i))
1626             return 0;
1627           break;
1628
1629         case 'i':
1630           if (XINT (x, i) != XINT (y, i))
1631             return 0;
1632           break;
1633
1634         case 'e':
1635           val = operands_match_p (XEXP (x, i), XEXP (y, i));
1636           if (val == 0)
1637             return 0;
1638           /* If any subexpression returns 2,
1639              we should return 2 if we are successful.  */
1640           if (val == 2)
1641             success_2 = 1;
1642           break;
1643
1644         case '0':
1645           break;
1646
1647           /* It is believed that rtx's at this level will never
1648              contain anything but integers and other rtx's,
1649              except for within LABEL_REFs and SYMBOL_REFs.  */
1650         default:
1651           abort ();
1652         }
1653     }
1654   return 1 + success_2;
1655 }
1656 \f
1657 /* Return the number of times character C occurs in string S.  */
1658
1659 int
1660 n_occurrences (c, s)
1661      char c;
1662      char *s;
1663 {
1664   int n = 0;
1665   while (*s)
1666     n += (*s++ == c);
1667   return n;
1668 }
1669 \f
1670 struct decomposition
1671 {
1672   int reg_flag;
1673   int safe;
1674   rtx base;
1675   HOST_WIDE_INT start;
1676   HOST_WIDE_INT end;
1677 };
1678
1679 /* Describe the range of registers or memory referenced by X.
1680    If X is a register, set REG_FLAG and put the first register
1681    number into START and the last plus one into END.
1682    If X is a memory reference, put a base address into BASE
1683    and a range of integer offsets into START and END.
1684    If X is pushing on the stack, we can assume it causes no trouble,
1685    so we set the SAFE field.  */
1686
1687 static struct decomposition
1688 decompose (x)
1689      rtx x;
1690 {
1691   struct decomposition val;
1692   int all_const = 0;
1693
1694   val.reg_flag = 0;
1695   val.safe = 0;
1696   if (GET_CODE (x) == MEM)
1697     {
1698       rtx base, offset = 0;
1699       rtx addr = XEXP (x, 0);
1700
1701       if (GET_CODE (addr) == PRE_DEC || GET_CODE (addr) == PRE_INC
1702           || GET_CODE (addr) == POST_DEC || GET_CODE (addr) == POST_INC)
1703         {
1704           val.base = XEXP (addr, 0);
1705           val.start = - GET_MODE_SIZE (GET_MODE (x));
1706           val.end = GET_MODE_SIZE (GET_MODE (x));
1707           val.safe = REGNO (val.base) == STACK_POINTER_REGNUM;
1708           return val;
1709         }
1710
1711       if (GET_CODE (addr) == CONST)
1712         {
1713           addr = XEXP (addr, 0);
1714           all_const = 1;
1715         }
1716       if (GET_CODE (addr) == PLUS)
1717         {
1718           if (CONSTANT_P (XEXP (addr, 0)))
1719             {
1720               base = XEXP (addr, 1);
1721               offset = XEXP (addr, 0);
1722             }
1723           else if (CONSTANT_P (XEXP (addr, 1)))
1724             {
1725               base = XEXP (addr, 0);
1726               offset = XEXP (addr, 1);
1727             }
1728         }
1729
1730       if (offset == 0)
1731         {
1732           base = addr;
1733           offset = const0_rtx;
1734         }
1735       if (GET_CODE (offset) == CONST)
1736         offset = XEXP (offset, 0);
1737       if (GET_CODE (offset) == PLUS)
1738         {
1739           if (GET_CODE (XEXP (offset, 0)) == CONST_INT)
1740             {
1741               base = gen_rtx (PLUS, GET_MODE (base), base, XEXP (offset, 1));
1742               offset = XEXP (offset, 0);
1743             }
1744           else if (GET_CODE (XEXP (offset, 1)) == CONST_INT)
1745             {
1746               base = gen_rtx (PLUS, GET_MODE (base), base, XEXP (offset, 0));
1747               offset = XEXP (offset, 1);
1748             }
1749           else
1750             {
1751               base = gen_rtx (PLUS, GET_MODE (base), base, offset);
1752               offset = const0_rtx;
1753             }
1754         }
1755       else if (GET_CODE (offset) != CONST_INT)
1756         {
1757           base = gen_rtx (PLUS, GET_MODE (base), base, offset);
1758           offset = const0_rtx;
1759         }
1760
1761       if (all_const && GET_CODE (base) == PLUS)
1762         base = gen_rtx (CONST, GET_MODE (base), base);
1763
1764       if (GET_CODE (offset) != CONST_INT)
1765         abort ();
1766
1767       val.start = INTVAL (offset);
1768       val.end = val.start + GET_MODE_SIZE (GET_MODE (x));
1769       val.base = base;
1770       return val;
1771     }
1772   else if (GET_CODE (x) == REG)
1773     {
1774       val.reg_flag = 1;
1775       val.start = true_regnum (x);
1776       if (val.start < 0)
1777         {
1778           /* A pseudo with no hard reg.  */
1779           val.start = REGNO (x);
1780           val.end = val.start + 1;
1781         }
1782       else
1783         /* A hard reg.  */
1784         val.end = val.start + HARD_REGNO_NREGS (val.start, GET_MODE (x));
1785     }
1786   else if (GET_CODE (x) == SUBREG)
1787     {
1788       if (GET_CODE (SUBREG_REG (x)) != REG)
1789         /* This could be more precise, but it's good enough.  */
1790         return decompose (SUBREG_REG (x));
1791       val.reg_flag = 1;
1792       val.start = true_regnum (x);
1793       if (val.start < 0)
1794         return decompose (SUBREG_REG (x));
1795       else
1796         /* A hard reg.  */
1797         val.end = val.start + HARD_REGNO_NREGS (val.start, GET_MODE (x));
1798     }
1799   else if (CONSTANT_P (x)
1800            /* This hasn't been assigned yet, so it can't conflict yet.  */
1801            || GET_CODE (x) == SCRATCH)
1802     val.safe = 1;
1803   else
1804     abort ();
1805   return val;
1806 }
1807
1808 /* Return 1 if altering Y will not modify the value of X.
1809    Y is also described by YDATA, which should be decompose (Y).  */
1810
1811 static int
1812 immune_p (x, y, ydata)
1813      rtx x, y;
1814      struct decomposition ydata;
1815 {
1816   struct decomposition xdata;
1817
1818   if (ydata.reg_flag)
1819     return !refers_to_regno_for_reload_p (ydata.start, ydata.end, x, NULL_PTR);
1820   if (ydata.safe)
1821     return 1;
1822
1823   if (GET_CODE (y) != MEM)
1824     abort ();
1825   /* If Y is memory and X is not, Y can't affect X.  */
1826   if (GET_CODE (x) != MEM)
1827     return 1;
1828
1829   xdata =  decompose (x);
1830
1831   if (! rtx_equal_p (xdata.base, ydata.base))
1832     {
1833       /* If bases are distinct symbolic constants, there is no overlap.  */
1834       if (CONSTANT_P (xdata.base) && CONSTANT_P (ydata.base))
1835         return 1;
1836       /* Constants and stack slots never overlap.  */
1837       if (CONSTANT_P (xdata.base)
1838           && (ydata.base == frame_pointer_rtx
1839               || ydata.base == stack_pointer_rtx))
1840         return 1;
1841       if (CONSTANT_P (ydata.base)
1842           && (xdata.base == frame_pointer_rtx
1843               || xdata.base == stack_pointer_rtx))
1844         return 1;
1845       /* If either base is variable, we don't know anything.  */
1846       return 0;
1847     }
1848
1849
1850   return (xdata.start >= ydata.end || ydata.start >= xdata.end);
1851 }
1852
1853 /* Similar, but calls decompose.  */
1854
1855 int
1856 safe_from_earlyclobber (op, clobber)
1857      rtx op, clobber;
1858 {
1859   struct decomposition early_data;
1860
1861   early_data = decompose (clobber);
1862   return immune_p (op, clobber, early_data);
1863 }
1864 \f
1865 /* Main entry point of this file: search the body of INSN
1866    for values that need reloading and record them with push_reload.
1867    REPLACE nonzero means record also where the values occur
1868    so that subst_reloads can be used.
1869
1870    IND_LEVELS says how many levels of indirection are supported by this
1871    machine; a value of zero means that a memory reference is not a valid
1872    memory address.
1873
1874    LIVE_KNOWN says we have valid information about which hard
1875    regs are live at each point in the program; this is true when
1876    we are called from global_alloc but false when stupid register
1877    allocation has been done.
1878
1879    RELOAD_REG_P if nonzero is a vector indexed by hard reg number
1880    which is nonnegative if the reg has been commandeered for reloading into.
1881    It is copied into STATIC_RELOAD_REG_P and referenced from there
1882    by various subroutines.  */
1883
1884 void
1885 find_reloads (insn, replace, ind_levels, live_known, reload_reg_p)
1886      rtx insn;
1887      int replace, ind_levels;
1888      int live_known;
1889      short *reload_reg_p;
1890 {
1891   rtx non_reloaded_operands[MAX_RECOG_OPERANDS];
1892   int n_non_reloaded_operands = 0;
1893 #ifdef REGISTER_CONSTRAINTS
1894
1895   enum reload_modified { RELOAD_NOTHING, RELOAD_READ, RELOAD_READ_WRITE, RELOAD_WRITE };
1896
1897   register int insn_code_number;
1898   register int i;
1899   int noperands;
1900   /* These are the constraints for the insn.  We don't change them.  */
1901   char *constraints1[MAX_RECOG_OPERANDS];
1902   /* These start out as the constraints for the insn
1903      and they are chewed up as we consider alternatives.  */
1904   char *constraints[MAX_RECOG_OPERANDS];
1905   /* These are the preferred classes for an operand, or NO_REGS if it isn't
1906      a register.  */
1907   enum reg_class preferred_class[MAX_RECOG_OPERANDS];
1908   char pref_or_nothing[MAX_RECOG_OPERANDS];
1909   /* Nonzero for a MEM operand whose entire address needs a reload.  */
1910   int address_reloaded[MAX_RECOG_OPERANDS];
1911   int no_input_reloads = 0, no_output_reloads = 0;
1912   int n_alternatives;
1913   int this_alternative[MAX_RECOG_OPERANDS];
1914   char this_alternative_win[MAX_RECOG_OPERANDS];
1915   char this_alternative_offmemok[MAX_RECOG_OPERANDS];
1916   char this_alternative_earlyclobber[MAX_RECOG_OPERANDS];
1917   int this_alternative_matches[MAX_RECOG_OPERANDS];
1918   int swapped;
1919   int goal_alternative[MAX_RECOG_OPERANDS];
1920   int this_alternative_number;
1921   int goal_alternative_number;
1922   int operand_reloadnum[MAX_RECOG_OPERANDS];
1923   int goal_alternative_matches[MAX_RECOG_OPERANDS];
1924   int goal_alternative_matched[MAX_RECOG_OPERANDS];
1925   char goal_alternative_win[MAX_RECOG_OPERANDS];
1926   char goal_alternative_offmemok[MAX_RECOG_OPERANDS];
1927   char goal_alternative_earlyclobber[MAX_RECOG_OPERANDS];
1928   int goal_alternative_swapped;
1929   enum reload_modified modified[MAX_RECOG_OPERANDS];
1930   int best;
1931   int commutative;
1932   char operands_match[MAX_RECOG_OPERANDS][MAX_RECOG_OPERANDS];
1933   rtx substed_operand[MAX_RECOG_OPERANDS];
1934   rtx body = PATTERN (insn);
1935   rtx set = single_set (insn);
1936   int goal_earlyclobber, this_earlyclobber;
1937   enum machine_mode operand_mode[MAX_RECOG_OPERANDS];
1938
1939   this_insn = insn;
1940   this_insn_is_asm = 0;         /* Tentative.  */
1941   n_reloads = 0;
1942   n_replacements = 0;
1943   n_memlocs = 0;
1944   n_earlyclobbers = 0;
1945   replace_reloads = replace;
1946   hard_regs_live_known = live_known;
1947   static_reload_reg_p = reload_reg_p;
1948
1949   /* JUMP_INSNs and CALL_INSNs are not allowed to have any output reloads;
1950      neither are insns that SET cc0.  Insns that use CC0 are not allowed
1951      to have any input reloads.  */
1952   if (GET_CODE (insn) == JUMP_INSN || GET_CODE (insn) == CALL_INSN)
1953     no_output_reloads = 1;
1954
1955 #ifdef HAVE_cc0
1956   if (reg_referenced_p (cc0_rtx, PATTERN (insn)))
1957     no_input_reloads = 1;
1958   if (reg_set_p (cc0_rtx, PATTERN (insn)))
1959     no_output_reloads = 1;
1960 #endif
1961
1962 #ifdef SECONDARY_MEMORY_NEEDED
1963   /* The eliminated forms of any secondary memory locations are per-insn, so
1964      clear them out here.  */
1965
1966   bzero (secondary_memlocs_elim, sizeof secondary_memlocs_elim);
1967 #endif
1968
1969   /* Find what kind of insn this is.  NOPERANDS gets number of operands.
1970      Make OPERANDS point to a vector of operand values.
1971      Make OPERAND_LOCS point to a vector of pointers to
1972      where the operands were found.
1973      Fill CONSTRAINTS and CONSTRAINTS1 with pointers to the
1974      constraint-strings for this insn.
1975      Return if the insn needs no reload processing.  */
1976
1977   switch (GET_CODE (body))
1978     {
1979     case USE:
1980     case CLOBBER:
1981     case ASM_INPUT:
1982     case ADDR_VEC:
1983     case ADDR_DIFF_VEC:
1984       return;
1985
1986     case SET:
1987       /* Dispose quickly of (set (reg..) (reg..)) if both have hard regs and it
1988          is cheap to move between them.  If it is not, there may not be an insn
1989          to do the copy, so we may need a reload.  */
1990       if (GET_CODE (SET_DEST (body)) == REG
1991           && REGNO (SET_DEST (body)) < FIRST_PSEUDO_REGISTER
1992           && GET_CODE (SET_SRC (body)) == REG
1993           && REGNO (SET_SRC (body)) < FIRST_PSEUDO_REGISTER
1994           && REGISTER_MOVE_COST (REGNO_REG_CLASS (REGNO (SET_SRC (body))),
1995                                  REGNO_REG_CLASS (REGNO (SET_DEST (body)))) == 2)
1996         return;
1997     case PARALLEL:
1998     case ASM_OPERANDS:
1999       noperands = asm_noperands (body);
2000       if (noperands >= 0)
2001         {
2002           /* This insn is an `asm' with operands.  */
2003
2004           insn_code_number = -1;
2005           this_insn_is_asm = 1;
2006
2007           /* expand_asm_operands makes sure there aren't too many operands.  */
2008           if (noperands > MAX_RECOG_OPERANDS)
2009             abort ();
2010
2011           /* Now get the operand values and constraints out of the insn.  */
2012
2013           decode_asm_operands (body, recog_operand, recog_operand_loc,
2014                                constraints, operand_mode);
2015           if (noperands > 0)
2016             {
2017               bcopy (constraints, constraints1, noperands * sizeof (char *));
2018               n_alternatives = n_occurrences (',', constraints[0]) + 1;
2019               for (i = 1; i < noperands; i++)
2020                 if (n_alternatives != n_occurrences (',', constraints[i]) + 1)
2021                   {
2022                     error_for_asm (insn, "operand constraints differ in number of alternatives");
2023                     /* Avoid further trouble with this insn.  */
2024                     PATTERN (insn) = gen_rtx (USE, VOIDmode, const0_rtx);
2025                     n_reloads = 0;
2026                     return;
2027                   }
2028             }
2029           break;
2030         }
2031
2032     default:
2033       /* Ordinary insn: recognize it, get the operands via insn_extract
2034          and get the constraints.  */
2035
2036       insn_code_number = recog_memoized (insn);
2037       if (insn_code_number < 0)
2038         fatal_insn_not_found (insn);
2039
2040       noperands = insn_n_operands[insn_code_number];
2041       n_alternatives = insn_n_alternatives[insn_code_number];
2042       /* Just return "no reloads" if insn has no operands with constraints.  */
2043       if (n_alternatives == 0)
2044         return;
2045       insn_extract (insn);
2046       for (i = 0; i < noperands; i++)
2047         {
2048           constraints[i] = constraints1[i]
2049             = insn_operand_constraint[insn_code_number][i];
2050           operand_mode[i] = insn_operand_mode[insn_code_number][i];
2051         }
2052     }
2053
2054   if (noperands == 0)
2055     return;
2056
2057   commutative = -1;
2058
2059   /* If we will need to know, later, whether some pair of operands
2060      are the same, we must compare them now and save the result.
2061      Reloading the base and index registers will clobber them
2062      and afterward they will fail to match.  */
2063
2064   for (i = 0; i < noperands; i++)
2065     {
2066       register char *p;
2067       register int c;
2068
2069       substed_operand[i] = recog_operand[i];
2070       p = constraints[i];
2071
2072       /* Scan this operand's constraint to see if it should match another.  */
2073
2074       while (c = *p++)
2075         if (c == '%')
2076           {
2077             /* The last operand should not be marked commutative.  */
2078             if (i == noperands - 1)
2079               {
2080                 if (this_insn_is_asm)
2081                   warning_for_asm (this_insn,
2082                                    "`%%' constraint used with last operand");
2083                 else
2084                   abort ();
2085               }
2086             else
2087               commutative = i;
2088           }
2089         else if (c >= '0' && c <= '9')
2090           {
2091             c -= '0';
2092             operands_match[c][i]
2093               = operands_match_p (recog_operand[c], recog_operand[i]);
2094
2095             /* An operand may not match itself.  */
2096             if (c == i)
2097               {
2098                 if (this_insn_is_asm)
2099                   warning_for_asm (this_insn,
2100                                    "operand %d has constraint %d", i, c);
2101                 else
2102                   abort ();
2103               }
2104
2105             /* If C can be commuted with C+1, and C might need to match I,
2106                then C+1 might also need to match I.  */
2107             if (commutative >= 0)
2108               {
2109                 if (c == commutative || c == commutative + 1)
2110                   {
2111                     int other = c + (c == commutative ? 1 : -1);
2112                     operands_match[other][i]
2113                       = operands_match_p (recog_operand[other], recog_operand[i]);
2114                   }
2115                 if (i == commutative || i == commutative + 1)
2116                   {
2117                     int other = i + (i == commutative ? 1 : -1);
2118                     operands_match[c][other]
2119                       = operands_match_p (recog_operand[c], recog_operand[other]);
2120                   }
2121                 /* Note that C is supposed to be less than I.
2122                    No need to consider altering both C and I
2123                    because in that case we would alter one into the other.  */
2124               }
2125           }
2126     }
2127
2128   /* Examine each operand that is a memory reference or memory address
2129      and reload parts of the addresses into index registers.
2130      While we are at it, initialize the array `modified'.
2131      Also here any references to pseudo regs that didn't get hard regs
2132      but are equivalent to constants get replaced in the insn itself
2133      with those constants.  Nobody will ever see them again.
2134
2135      Finally, set up the preferred classes of each operand.  */
2136
2137   for (i = 0; i < noperands; i++)
2138     {
2139       register RTX_CODE code = GET_CODE (recog_operand[i]);
2140       modified[i] = RELOAD_READ;
2141       address_reloaded[i] = 0;
2142
2143       if (constraints[i][0] == 'p')
2144         {
2145           find_reloads_address (VOIDmode, NULL_PTR,
2146                                 recog_operand[i], recog_operand_loc[i],
2147                                 recog_operand[i], ind_levels);
2148           substed_operand[i] = recog_operand[i] = *recog_operand_loc[i];
2149         }
2150       else if (code == MEM)
2151         {
2152           if (find_reloads_address (GET_MODE (recog_operand[i]),
2153                                     recog_operand_loc[i],
2154                                     XEXP (recog_operand[i], 0),
2155                                     &XEXP (recog_operand[i], 0),
2156                                     recog_operand[i], ind_levels))
2157             address_reloaded[i] = 1;
2158           substed_operand[i] = recog_operand[i] = *recog_operand_loc[i];
2159         }
2160       else if (code == SUBREG)
2161         substed_operand[i] = recog_operand[i] = *recog_operand_loc[i]
2162           = find_reloads_toplev (recog_operand[i], ind_levels,
2163                                  set != 0
2164                                  && &SET_DEST (set) == recog_operand_loc[i]);
2165       else if (code == REG)
2166         {
2167           /* This is equivalent to calling find_reloads_toplev.
2168              The code is duplicated for speed.
2169              When we find a pseudo always equivalent to a constant,
2170              we replace it by the constant.  We must be sure, however,
2171              that we don't try to replace it in the insn in which it
2172              is being set.   */
2173           register int regno = REGNO (recog_operand[i]);
2174           if (reg_equiv_constant[regno] != 0
2175               && (set == 0 || &SET_DEST (set) != recog_operand_loc[i]))
2176             substed_operand[i] = recog_operand[i]
2177               = reg_equiv_constant[regno];
2178 #if 0 /* This might screw code in reload1.c to delete prior output-reload
2179          that feeds this insn.  */
2180           if (reg_equiv_mem[regno] != 0)
2181             substed_operand[i] = recog_operand[i]
2182               = reg_equiv_mem[regno];
2183 #endif
2184           if (reg_equiv_address[regno] != 0)
2185             {
2186               /* If reg_equiv_address is not a constant address, copy it,
2187                  since it may be shared.  */
2188               rtx address = reg_equiv_address[regno];
2189
2190               if (rtx_varies_p (address))
2191                 address = copy_rtx (address);
2192
2193               /* If this is an output operand, we must output a CLOBBER
2194                  after INSN so find_equiv_reg knows REGNO is being written. */
2195               if (constraints[i][0] == '='
2196                   || constraints[i][0] == '+')
2197                 emit_insn_after (gen_rtx (CLOBBER, VOIDmode, recog_operand[i]),
2198                                  insn);
2199
2200               *recog_operand_loc[i] = recog_operand[i]
2201                 = gen_rtx (MEM, GET_MODE (recog_operand[i]), address);
2202               RTX_UNCHANGING_P (recog_operand[i])
2203                 = RTX_UNCHANGING_P (regno_reg_rtx[regno]);
2204               find_reloads_address (GET_MODE (recog_operand[i]),
2205                                     recog_operand_loc[i],
2206                                     XEXP (recog_operand[i], 0),
2207                                     &XEXP (recog_operand[i], 0),
2208                                     recog_operand[i], ind_levels);
2209               substed_operand[i] = recog_operand[i] = *recog_operand_loc[i];
2210             }
2211         }
2212       /* If the operand is still a register (we didn't replace it with an
2213          equivalent), get the preferred class to reload it into.  */
2214       code = GET_CODE (recog_operand[i]);
2215       preferred_class[i]
2216         = ((code == REG && REGNO (recog_operand[i]) >= FIRST_PSEUDO_REGISTER)
2217            ? reg_preferred_class (REGNO (recog_operand[i])) : NO_REGS);
2218       pref_or_nothing[i]
2219         = (code == REG && REGNO (recog_operand[i]) >= FIRST_PSEUDO_REGISTER
2220            && reg_alternate_class (REGNO (recog_operand[i])) == NO_REGS);
2221     }
2222
2223   /* If this is simply a copy from operand 1 to operand 0, merge the
2224      preferred classes for the operands.  */
2225   if (set != 0 && noperands >= 2 && recog_operand[0] == SET_DEST (set)
2226       && recog_operand[1] == SET_SRC (set))
2227     {
2228       preferred_class[0] = preferred_class[1]
2229         = reg_class_subunion[(int) preferred_class[0]][(int) preferred_class[1]];
2230       pref_or_nothing[0] |= pref_or_nothing[1];
2231       pref_or_nothing[1] |= pref_or_nothing[0];
2232     }
2233
2234   /* Now see what we need for pseudo-regs that didn't get hard regs
2235      or got the wrong kind of hard reg.  For this, we must consider
2236      all the operands together against the register constraints.  */
2237
2238   best = MAX_RECOG_OPERANDS + 300;
2239
2240   swapped = 0;
2241   goal_alternative_swapped = 0;
2242  try_swapped:
2243
2244   /* The constraints are made of several alternatives.
2245      Each operand's constraint looks like foo,bar,... with commas
2246      separating the alternatives.  The first alternatives for all
2247      operands go together, the second alternatives go together, etc.
2248
2249      First loop over alternatives.  */
2250
2251   for (this_alternative_number = 0;
2252        this_alternative_number < n_alternatives;
2253        this_alternative_number++)
2254     {
2255       /* Loop over operands for one constraint alternative.  */
2256       /* LOSERS counts those that don't fit this alternative
2257          and would require loading.  */
2258       int losers = 0;
2259       /* BAD is set to 1 if it some operand can't fit this alternative
2260          even after reloading.  */
2261       int bad = 0;
2262       /* REJECT is a count of how undesirable this alternative says it is
2263          if any reloading is required.  If the alternative matches exactly
2264          then REJECT is ignored, but otherwise it gets this much
2265          counted against it in addition to the reloading needed.  Each
2266          ? counts three times here since we want the disparaging caused by
2267          a bad register class to only count 1/3 as much.  */
2268       int reject = 0;
2269
2270       this_earlyclobber = 0;
2271
2272       for (i = 0; i < noperands; i++)
2273         {
2274           register char *p = constraints[i];
2275           register int win = 0;
2276           /* 0 => this operand can be reloaded somehow for this alternative */
2277           int badop = 1;
2278           /* 0 => this operand can be reloaded if the alternative allows regs.  */
2279           int winreg = 0;
2280           int c;
2281           register rtx operand = recog_operand[i];
2282           int offset = 0;
2283           /* Nonzero means this is a MEM that must be reloaded into a reg
2284              regardless of what the constraint says.  */
2285           int force_reload = 0;
2286           int offmemok = 0;
2287           int earlyclobber = 0;
2288
2289           /* If the operand is a SUBREG, extract
2290              the REG or MEM (or maybe even a constant) within.
2291              (Constants can occur as a result of reg_equiv_constant.)  */
2292
2293           while (GET_CODE (operand) == SUBREG)
2294             {
2295               offset += SUBREG_WORD (operand);
2296               operand = SUBREG_REG (operand);
2297               /* Force reload if this is not a register or if there may may
2298                  be a problem accessing the register in the outer mode.  */
2299               if (GET_CODE (operand) != REG
2300 #if defined(BYTE_LOADS_ZERO_EXTEND) || defined(BYTE_LOADS_SIGN_EXTEND)
2301                   /* ??? The comment below clearly does not match the code.
2302                      What the code below actually does is set force_reload
2303                      for a paradoxical subreg of a pseudo.  rms and kenner
2304                      can't see the point of doing this.  */
2305                   /* Nonparadoxical subreg of a pseudoreg.
2306                      Don't to load the full width if on this machine
2307                      we expected the fetch to extend.  */
2308                   || ((GET_MODE_SIZE (operand_mode[i])
2309                        > GET_MODE_SIZE (GET_MODE (operand)))
2310                       && REGNO (operand) >= FIRST_PSEUDO_REGISTER)
2311 #endif
2312                   /* Subreg of a hard reg which can't handle the subreg's mode
2313                      or which would handle that mode in the wrong number of
2314                      registers for subregging to work.  */
2315                   || (REGNO (operand) < FIRST_PSEUDO_REGISTER
2316                       && (! HARD_REGNO_MODE_OK (REGNO (operand),
2317                                                 operand_mode[i])
2318                           || (GET_MODE_SIZE (operand_mode[i]) <= UNITS_PER_WORD
2319                               && (GET_MODE_SIZE (GET_MODE (operand))
2320                                   > UNITS_PER_WORD)
2321                               && ((GET_MODE_SIZE (GET_MODE (operand))
2322                                    / UNITS_PER_WORD)
2323                                   != HARD_REGNO_NREGS (REGNO (operand),
2324                                                        GET_MODE (operand)))))))
2325                 force_reload = 1;
2326             }
2327
2328           this_alternative[i] = (int) NO_REGS;
2329           this_alternative_win[i] = 0;
2330           this_alternative_offmemok[i] = 0;
2331           this_alternative_earlyclobber[i] = 0;
2332           this_alternative_matches[i] = -1;
2333
2334           /* An empty constraint or empty alternative
2335              allows anything which matched the pattern.  */
2336           if (*p == 0 || *p == ',')
2337             win = 1, badop = 0;
2338
2339           /* Scan this alternative's specs for this operand;
2340              set WIN if the operand fits any letter in this alternative.
2341              Otherwise, clear BADOP if this operand could
2342              fit some letter after reloads,
2343              or set WINREG if this operand could fit after reloads
2344              provided the constraint allows some registers.  */
2345
2346           while (*p && (c = *p++) != ',')
2347             switch (c)
2348               {
2349               case '=':
2350                 modified[i] = RELOAD_WRITE;
2351                 break;
2352
2353               case '+':
2354                 modified[i] = RELOAD_READ_WRITE;
2355                 break;
2356
2357               case '*':
2358                 break;
2359
2360               case '%':
2361                 /* The last operand should not be marked commutative.  */
2362                 if (i != noperands - 1)
2363                   commutative = i;
2364                 break;
2365
2366               case '?':
2367                 reject += 3;
2368                 break;
2369
2370               case '!':
2371                 reject = 300;
2372                 break;
2373
2374               case '#':
2375                 /* Ignore rest of this alternative as far as
2376                    reloading is concerned.  */
2377                 while (*p && *p != ',') p++;
2378                 break;
2379
2380               case '0':
2381               case '1':
2382               case '2':
2383               case '3':
2384               case '4':
2385                 c -= '0';
2386                 this_alternative_matches[i] = c;
2387                 /* We are supposed to match a previous operand.
2388                    If we do, we win if that one did.
2389                    If we do not, count both of the operands as losers.
2390                    (This is too conservative, since most of the time
2391                    only a single reload insn will be needed to make
2392                    the two operands win.  As a result, this alternative
2393                    may be rejected when it is actually desirable.)  */
2394                 if ((swapped && (c != commutative || i != commutative + 1))
2395                     /* If we are matching as if two operands were swapped,
2396                        also pretend that operands_match had been computed
2397                        with swapped.
2398                        But if I is the second of those and C is the first,
2399                        don't exchange them, because operands_match is valid
2400                        only on one side of its diagonal.  */
2401                     ? (operands_match
2402                         [(c == commutative || c == commutative + 1)
2403                          ? 2*commutative + 1 - c : c]
2404                         [(i == commutative || i == commutative + 1)
2405                          ? 2*commutative + 1 - i : i])
2406                     : operands_match[c][i])
2407                   win = this_alternative_win[c];
2408                 else
2409                   {
2410                     /* Operands don't match.  */
2411                     rtx value;
2412                     /* Retroactively mark the operand we had to match
2413                        as a loser, if it wasn't already.  */
2414                     if (this_alternative_win[c])
2415                       losers++;
2416                     this_alternative_win[c] = 0;
2417                     if (this_alternative[c] == (int) NO_REGS)
2418                       bad = 1;
2419                     /* But count the pair only once in the total badness of
2420                        this alternative, if the pair can be a dummy reload.  */
2421                     value
2422                       = find_dummy_reload (recog_operand[i], recog_operand[c],
2423                                            recog_operand_loc[i], recog_operand_loc[c],
2424                                            this_alternative[c], -1);
2425
2426                     if (value != 0)
2427                       losers--;
2428                   }
2429                 /* This can be fixed with reloads if the operand
2430                    we are supposed to match can be fixed with reloads.  */
2431                 badop = 0;
2432                 this_alternative[i] = this_alternative[c];
2433                 break;
2434
2435               case 'p':
2436                 /* All necessary reloads for an address_operand
2437                    were handled in find_reloads_address.  */
2438                 this_alternative[i] = (int) ALL_REGS;
2439                 win = 1;
2440                 break;
2441
2442               case 'm':
2443                 if (force_reload)
2444                   break;
2445                 if (GET_CODE (operand) == MEM
2446                     || (GET_CODE (operand) == REG
2447                         && REGNO (operand) >= FIRST_PSEUDO_REGISTER
2448                         && reg_renumber[REGNO (operand)] < 0))
2449                   win = 1;
2450                 if (CONSTANT_P (operand))
2451                   badop = 0;
2452                 break;
2453
2454               case '<':
2455                 if (GET_CODE (operand) == MEM
2456                     && ! address_reloaded[i]
2457                     && (GET_CODE (XEXP (operand, 0)) == PRE_DEC
2458                         || GET_CODE (XEXP (operand, 0)) == POST_DEC))
2459                   win = 1;
2460                 break;
2461
2462               case '>':
2463                 if (GET_CODE (operand) == MEM
2464                     && ! address_reloaded[i]
2465                     && (GET_CODE (XEXP (operand, 0)) == PRE_INC
2466                         || GET_CODE (XEXP (operand, 0)) == POST_INC))
2467                   win = 1;
2468                 break;
2469
2470                 /* Memory operand whose address is not offsettable.  */
2471               case 'V':
2472                 if (force_reload)
2473                   break;
2474                 if (GET_CODE (operand) == MEM
2475                     && ! (ind_levels ? offsettable_memref_p (operand)
2476                           : offsettable_nonstrict_memref_p (operand))
2477                     /* Certain mem addresses will become offsettable
2478                        after they themselves are reloaded.  This is important;
2479                        we don't want our own handling of unoffsettables
2480                        to override the handling of reg_equiv_address.  */
2481                     && !(GET_CODE (XEXP (operand, 0)) == REG
2482                          && (ind_levels == 0
2483                              || reg_equiv_address[REGNO (XEXP (operand, 0))] != 0)))
2484                   win = 1;
2485                 break;
2486
2487                 /* Memory operand whose address is offsettable.  */
2488               case 'o':
2489                 if (force_reload)
2490                   break;
2491                 if ((GET_CODE (operand) == MEM
2492                      /* If IND_LEVELS, find_reloads_address won't reload a
2493                         pseudo that didn't get a hard reg, so we have to
2494                         reject that case.  */
2495                      && (ind_levels ? offsettable_memref_p (operand)
2496                          : offsettable_nonstrict_memref_p (operand)))
2497                     /* Certain mem addresses will become offsettable
2498                        after they themselves are reloaded.  This is important;
2499                        we don't want our own handling of unoffsettables
2500                        to override the handling of reg_equiv_address.  */
2501                     || (GET_CODE (operand) == MEM
2502                         && GET_CODE (XEXP (operand, 0)) == REG
2503                         && (ind_levels == 0
2504                             || reg_equiv_address[REGNO (XEXP (operand, 0))] != 0))
2505                     || (GET_CODE (operand) == REG
2506                         && REGNO (operand) >= FIRST_PSEUDO_REGISTER
2507                         && reg_renumber[REGNO (operand)] < 0))
2508                   win = 1;
2509                 if (CONSTANT_P (operand) || GET_CODE (operand) == MEM)
2510                   badop = 0;
2511                 offmemok = 1;
2512                 break;
2513
2514               case '&':
2515                 /* Output operand that is stored before the need for the
2516                    input operands (and their index registers) is over.  */
2517                 earlyclobber = 1, this_earlyclobber = 1;
2518                 break;
2519
2520               case 'E':
2521                 /* Match any floating double constant, but only if
2522                    we can examine the bits of it reliably.  */
2523                 if ((HOST_FLOAT_FORMAT != TARGET_FLOAT_FORMAT
2524                      || HOST_BITS_PER_WIDE_INT != BITS_PER_WORD)
2525                     && GET_MODE (operand) != VOIDmode && ! flag_pretend_float)
2526                   break;
2527                 if (GET_CODE (operand) == CONST_DOUBLE)
2528                   win = 1;
2529                 break;
2530
2531               case 'F':
2532                 if (GET_CODE (operand) == CONST_DOUBLE)
2533                   win = 1;
2534                 break;
2535
2536               case 'G':
2537               case 'H':
2538                 if (GET_CODE (operand) == CONST_DOUBLE
2539                     && CONST_DOUBLE_OK_FOR_LETTER_P (operand, c))
2540                   win = 1;
2541                 break;
2542
2543               case 's':
2544                 if (GET_CODE (operand) == CONST_INT
2545                     || (GET_CODE (operand) == CONST_DOUBLE
2546                         && GET_MODE (operand) == VOIDmode))
2547                   break;
2548               case 'i':
2549                 if (CONSTANT_P (operand)
2550 #ifdef LEGITIMATE_PIC_OPERAND_P
2551                     && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (operand))
2552 #endif
2553                     )
2554                   win = 1;
2555                 break;
2556
2557               case 'n':
2558                 if (GET_CODE (operand) == CONST_INT
2559                     || (GET_CODE (operand) == CONST_DOUBLE
2560                         && GET_MODE (operand) == VOIDmode))
2561                   win = 1;
2562                 break;
2563
2564               case 'I':
2565               case 'J':
2566               case 'K':
2567               case 'L':
2568               case 'M':
2569               case 'N':
2570               case 'O':
2571               case 'P':
2572                 if (GET_CODE (operand) == CONST_INT
2573                     && CONST_OK_FOR_LETTER_P (INTVAL (operand), c))
2574                   win = 1;
2575                 break;
2576
2577               case 'X':
2578                 win = 1;
2579                 break;
2580
2581               case 'g':
2582                 if (! force_reload
2583                     /* A PLUS is never a valid operand, but reload can make
2584                        it from a register when eliminating registers.  */
2585                     && GET_CODE (operand) != PLUS
2586                     /* A SCRATCH is not a valid operand.  */
2587                     && GET_CODE (operand) != SCRATCH
2588 #ifdef LEGITIMATE_PIC_OPERAND_P
2589                     && (! CONSTANT_P (operand)
2590                         || ! flag_pic
2591                         || LEGITIMATE_PIC_OPERAND_P (operand))
2592 #endif
2593                     && (GENERAL_REGS == ALL_REGS
2594                         || GET_CODE (operand) != REG
2595                         || (REGNO (operand) >= FIRST_PSEUDO_REGISTER
2596                             && reg_renumber[REGNO (operand)] < 0)))
2597                   win = 1;
2598                 /* Drop through into 'r' case */
2599
2600               case 'r':
2601                 this_alternative[i]
2602                   = (int) reg_class_subunion[this_alternative[i]][(int) GENERAL_REGS];
2603                 goto reg;
2604
2605 #ifdef EXTRA_CONSTRAINT
2606               case 'Q':
2607               case 'R':
2608               case 'S':
2609               case 'T':
2610               case 'U':
2611                 if (EXTRA_CONSTRAINT (operand, c))
2612                   win = 1;
2613                 break;
2614 #endif
2615
2616               default:
2617                 this_alternative[i]
2618                   = (int) reg_class_subunion[this_alternative[i]][(int) REG_CLASS_FROM_LETTER (c)];
2619
2620               reg:
2621                 if (GET_MODE (operand) == BLKmode)
2622                   break;
2623                 winreg = 1;
2624                 if (GET_CODE (operand) == REG
2625                     && reg_fits_class_p (operand, this_alternative[i],
2626                                          offset, GET_MODE (recog_operand[i])))
2627                   win = 1;
2628                 break;
2629               }
2630
2631           constraints[i] = p;
2632
2633           /* If this operand could be handled with a reg,
2634              and some reg is allowed, then this operand can be handled.  */
2635           if (winreg && this_alternative[i] != (int) NO_REGS)
2636             badop = 0;
2637
2638           /* Record which operands fit this alternative.  */
2639           this_alternative_earlyclobber[i] = earlyclobber;
2640           if (win && ! force_reload)
2641             this_alternative_win[i] = 1;
2642           else
2643             {
2644               this_alternative_offmemok[i] = offmemok;
2645               losers++;
2646               if (badop)
2647                 bad = 1;
2648               /* Alternative loses if it has no regs for a reg operand.  */
2649               if (GET_CODE (operand) == REG
2650                   && this_alternative[i] == (int) NO_REGS
2651                   && this_alternative_matches[i] < 0)
2652                 bad = 1;
2653
2654               /* Alternative loses if it requires a type of reload not
2655                  permitted for this insn.  We can always reload SCRATCH
2656                  and objects with a REG_UNUSED note.  */
2657               if (GET_CODE (operand) != SCRATCH && modified[i] != RELOAD_READ
2658                   && no_output_reloads
2659                   && ! find_reg_note (insn, REG_UNUSED, operand))
2660                 bad = 1;
2661               else if (modified[i] != RELOAD_WRITE && no_input_reloads)
2662                 bad = 1;
2663
2664               /* We prefer to reload pseudos over reloading other things,
2665                  since such reloads may be able to be eliminated later.
2666                  If we are reloading a SCRATCH, we won't be generating any
2667                  insns, just using a register, so it is also preferred.
2668                  So bump REJECT in other cases.  */
2669               if (GET_CODE (operand) != REG && GET_CODE (operand) != SCRATCH)
2670                 reject++;
2671             }
2672
2673           /* If this operand is a pseudo register that didn't get a hard
2674              reg and this alternative accepts some register, see if the
2675              class that we want is a subset of the preferred class for this
2676              register.  If not, but it intersects that class, use the
2677              preferred class instead.  If it does not intersect the preferred
2678              class, show that usage of this alternative should be discouraged;
2679              it will be discouraged more still if the register is `preferred
2680              or nothing'.  We do this because it increases the chance of
2681              reusing our spill register in a later insn and avoiding a pair
2682              of memory stores and loads.
2683
2684              Don't bother with this if this alternative will accept this
2685              operand.
2686
2687              Don't do this if the preferred class has only one register
2688              because we might otherwise exhaust the class.  */
2689
2690
2691           if (! win && this_alternative[i] != (int) NO_REGS
2692               && reg_class_size[(int) preferred_class[i]] > 1)
2693             {
2694               if (! reg_class_subset_p (this_alternative[i],
2695                                         preferred_class[i]))
2696                 {
2697                   /* Since we don't have a way of forming the intersection,
2698                      we just do something special if the preferred class
2699                      is a subset of the class we have; that's the most
2700                      common case anyway.  */
2701                   if (reg_class_subset_p (preferred_class[i],
2702                                           this_alternative[i]))
2703                     this_alternative[i] = (int) preferred_class[i];
2704                   else
2705                     reject += (1 + pref_or_nothing[i]);
2706                 }
2707             }
2708         }
2709
2710       /* Now see if any output operands that are marked "earlyclobber"
2711          in this alternative conflict with any input operands
2712          or any memory addresses.  */
2713
2714       for (i = 0; i < noperands; i++)
2715         if (this_alternative_earlyclobber[i]
2716             && this_alternative_win[i])
2717           {
2718             struct decomposition early_data;
2719             int j;
2720
2721             early_data = decompose (recog_operand[i]);
2722
2723             if (modified[i] == RELOAD_READ)
2724               {
2725                 if (this_insn_is_asm)
2726                   warning_for_asm (this_insn,
2727                                    "`&' constraint used with input operand");
2728                 else
2729                   abort ();
2730                 continue;
2731               }
2732
2733             if (this_alternative[i] == NO_REGS)
2734               {
2735                 this_alternative_earlyclobber[i] = 0;
2736                 if (this_insn_is_asm)
2737                   error_for_asm (this_insn,
2738                                  "`&' constraint used with no register class");
2739                 else
2740                   abort ();
2741               }
2742
2743             for (j = 0; j < noperands; j++)
2744               /* Is this an input operand or a memory ref?  */
2745               if ((GET_CODE (recog_operand[j]) == MEM
2746                    || modified[j] != RELOAD_WRITE)
2747                   && j != i
2748                   /* Ignore things like match_operator operands.  */
2749                   && *constraints1[j] != 0
2750                   /* Don't count an input operand that is constrained to match
2751                      the early clobber operand.  */
2752                   && ! (this_alternative_matches[j] == i
2753                         && rtx_equal_p (recog_operand[i], recog_operand[j]))
2754                   /* Is it altered by storing the earlyclobber operand?  */
2755                   && !immune_p (recog_operand[j], recog_operand[i], early_data))
2756                 {
2757                   /* If the output is in a single-reg class,
2758                      it's costly to reload it, so reload the input instead.  */
2759                   if (reg_class_size[this_alternative[i]] == 1
2760                       && (GET_CODE (recog_operand[j]) == REG
2761                           || GET_CODE (recog_operand[j]) == SUBREG))
2762                     {
2763                       losers++;
2764                       this_alternative_win[j] = 0;
2765                     }
2766                   else
2767                     break;
2768                 }
2769             /* If an earlyclobber operand conflicts with something,
2770                it must be reloaded, so request this and count the cost.  */
2771             if (j != noperands)
2772               {
2773                 losers++;
2774                 this_alternative_win[i] = 0;
2775                 for (j = 0; j < noperands; j++)
2776                   if (this_alternative_matches[j] == i
2777                       && this_alternative_win[j])
2778                     {
2779                       this_alternative_win[j] = 0;
2780                       losers++;
2781                     }
2782               }
2783           }
2784
2785       /* If one alternative accepts all the operands, no reload required,
2786          choose that alternative; don't consider the remaining ones.  */
2787       if (losers == 0)
2788         {
2789           /* Unswap these so that they are never swapped at `finish'.  */
2790           if (commutative >= 0)
2791             {
2792               recog_operand[commutative] = substed_operand[commutative];
2793               recog_operand[commutative + 1]
2794                 = substed_operand[commutative + 1];
2795             }
2796           for (i = 0; i < noperands; i++)
2797             {
2798               goal_alternative_win[i] = 1;
2799               goal_alternative[i] = this_alternative[i];
2800               goal_alternative_offmemok[i] = this_alternative_offmemok[i];
2801               goal_alternative_matches[i] = this_alternative_matches[i];
2802               goal_alternative_earlyclobber[i]
2803                 = this_alternative_earlyclobber[i];
2804             }
2805           goal_alternative_number = this_alternative_number;
2806           goal_alternative_swapped = swapped;
2807           goal_earlyclobber = this_earlyclobber;
2808           goto finish;
2809         }
2810
2811       /* REJECT, set by the ! and ? constraint characters and when a register
2812          would be reloaded into a non-preferred class, discourages the use of
2813          this alternative for a reload goal.  REJECT is incremented by three
2814          for each ? and one for each non-preferred class.  */
2815       losers = losers * 3 + reject;
2816
2817       /* If this alternative can be made to work by reloading,
2818          and it needs less reloading than the others checked so far,
2819          record it as the chosen goal for reloading.  */
2820       if (! bad && best > losers)
2821         {
2822           for (i = 0; i < noperands; i++)
2823             {
2824               goal_alternative[i] = this_alternative[i];
2825               goal_alternative_win[i] = this_alternative_win[i];
2826               goal_alternative_offmemok[i] = this_alternative_offmemok[i];
2827               goal_alternative_matches[i] = this_alternative_matches[i];
2828               goal_alternative_earlyclobber[i]
2829                 = this_alternative_earlyclobber[i];
2830             }
2831           goal_alternative_swapped = swapped;
2832           best = losers;
2833           goal_alternative_number = this_alternative_number;
2834           goal_earlyclobber = this_earlyclobber;
2835         }
2836     }
2837
2838   /* If insn is commutative (it's safe to exchange a certain pair of operands)
2839      then we need to try each alternative twice,
2840      the second time matching those two operands
2841      as if we had exchanged them.
2842      To do this, really exchange them in operands.
2843
2844      If we have just tried the alternatives the second time,
2845      return operands to normal and drop through.  */
2846
2847   if (commutative >= 0)
2848     {
2849       swapped = !swapped;
2850       if (swapped)
2851         {
2852           register enum reg_class tclass;
2853           register int t;
2854
2855           recog_operand[commutative] = substed_operand[commutative + 1];
2856           recog_operand[commutative + 1] = substed_operand[commutative];
2857
2858           tclass = preferred_class[commutative];
2859           preferred_class[commutative] = preferred_class[commutative + 1];
2860           preferred_class[commutative + 1] = tclass;
2861
2862           t = pref_or_nothing[commutative];
2863           pref_or_nothing[commutative] = pref_or_nothing[commutative + 1];
2864           pref_or_nothing[commutative + 1] = t;
2865
2866           bcopy (constraints1, constraints, noperands * sizeof (char *));
2867           goto try_swapped;
2868         }
2869       else
2870         {
2871           recog_operand[commutative] = substed_operand[commutative];
2872           recog_operand[commutative + 1] = substed_operand[commutative + 1];
2873         }
2874     }
2875
2876   /* The operands don't meet the constraints.
2877      goal_alternative describes the alternative
2878      that we could reach by reloading the fewest operands.
2879      Reload so as to fit it.  */
2880
2881   if (best == MAX_RECOG_OPERANDS + 300)
2882     {
2883       /* No alternative works with reloads??  */
2884       if (insn_code_number >= 0)
2885         abort ();
2886       error_for_asm (insn, "inconsistent operand constraints in an `asm'");
2887       /* Avoid further trouble with this insn.  */
2888       PATTERN (insn) = gen_rtx (USE, VOIDmode, const0_rtx);
2889       n_reloads = 0;
2890       return;
2891     }
2892
2893   /* Jump to `finish' from above if all operands are valid already.
2894      In that case, goal_alternative_win is all 1.  */
2895  finish:
2896
2897   /* Right now, for any pair of operands I and J that are required to match,
2898      with I < J,
2899      goal_alternative_matches[J] is I.
2900      Set up goal_alternative_matched as the inverse function:
2901      goal_alternative_matched[I] = J.  */
2902
2903   for (i = 0; i < noperands; i++)
2904     goal_alternative_matched[i] = -1;
2905
2906   for (i = 0; i < noperands; i++)
2907     if (! goal_alternative_win[i]
2908         && goal_alternative_matches[i] >= 0)
2909       goal_alternative_matched[goal_alternative_matches[i]] = i;
2910
2911   /* If the best alternative is with operands 1 and 2 swapped,
2912      consider them swapped before reporting the reloads.  */
2913
2914   if (goal_alternative_swapped)
2915     {
2916       register rtx tem;
2917
2918       tem = substed_operand[commutative];
2919       substed_operand[commutative] = substed_operand[commutative + 1];
2920       substed_operand[commutative + 1] = tem;
2921       tem = recog_operand[commutative];
2922       recog_operand[commutative] = recog_operand[commutative + 1];
2923       recog_operand[commutative + 1] = tem;
2924     }
2925
2926   /* Perform whatever substitutions on the operands we are supposed
2927      to make due to commutativity or replacement of registers
2928      with equivalent constants or memory slots.  */
2929
2930   for (i = 0; i < noperands; i++)
2931     {
2932       *recog_operand_loc[i] = substed_operand[i];
2933       /* While we are looping on operands, initialize this.  */
2934       operand_reloadnum[i] = -1;
2935     }
2936
2937   /* Any constants that aren't allowed and can't be reloaded
2938      into registers are here changed into memory references.  */
2939   for (i = 0; i < noperands; i++)
2940     if (! goal_alternative_win[i]
2941         && CONSTANT_P (recog_operand[i])
2942         && (PREFERRED_RELOAD_CLASS (recog_operand[i],
2943                                     (enum reg_class) goal_alternative[i])
2944             == NO_REGS)
2945         && operand_mode[i] != VOIDmode)
2946       {
2947         *recog_operand_loc[i] = recog_operand[i]
2948           = find_reloads_toplev (force_const_mem (operand_mode[i],
2949                                                   recog_operand[i]),
2950                                  ind_levels, 0);
2951         if (alternative_allows_memconst (constraints1[i],
2952                                          goal_alternative_number))
2953           goal_alternative_win[i] = 1;
2954       }
2955
2956   /* Now record reloads for all the operands that need them.  */
2957   for (i = 0; i < noperands; i++)
2958     if (! goal_alternative_win[i])
2959       {
2960         /* Operands that match previous ones have already been handled.  */
2961         if (goal_alternative_matches[i] >= 0)
2962           ;
2963         /* Handle an operand with a nonoffsettable address
2964            appearing where an offsettable address will do
2965            by reloading the address into a base register.  */
2966         else if (goal_alternative_matched[i] == -1
2967                  && goal_alternative_offmemok[i]
2968                  && GET_CODE (recog_operand[i]) == MEM)
2969           {
2970             operand_reloadnum[i]
2971               = push_reload (XEXP (recog_operand[i], 0), NULL_RTX,
2972                              &XEXP (recog_operand[i], 0), NULL_PTR,
2973                              BASE_REG_CLASS, GET_MODE (XEXP (recog_operand[i], 0)),
2974                              VOIDmode, 0, 0, NULL_RTX);
2975             reload_inc[operand_reloadnum[i]]
2976               = GET_MODE_SIZE (GET_MODE (recog_operand[i]));
2977           }
2978         else if (goal_alternative_matched[i] == -1)
2979           operand_reloadnum[i] =
2980             push_reload (modified[i] != RELOAD_WRITE ? recog_operand[i] : 0,
2981                          modified[i] != RELOAD_READ ? recog_operand[i] : 0,
2982                          modified[i] != RELOAD_WRITE ? recog_operand_loc[i] : 0,
2983                          modified[i] != RELOAD_READ ? recog_operand_loc[i] : 0,
2984                          (enum reg_class) goal_alternative[i],
2985                          (modified[i] == RELOAD_WRITE ? VOIDmode : operand_mode[i]),
2986                          (modified[i] == RELOAD_READ ? VOIDmode : operand_mode[i]),
2987                          (insn_code_number < 0 ? 0
2988                           : insn_operand_strict_low[insn_code_number][i]),
2989                          0, NULL_RTX);
2990         /* In a matching pair of operands, one must be input only
2991            and the other must be output only.
2992            Pass the input operand as IN and the other as OUT.  */
2993         else if (modified[i] == RELOAD_READ
2994                  && modified[goal_alternative_matched[i]] == RELOAD_WRITE)
2995           {
2996             operand_reloadnum[i]
2997               = push_reload (recog_operand[i],
2998                              recog_operand[goal_alternative_matched[i]],
2999                              recog_operand_loc[i],
3000                              recog_operand_loc[goal_alternative_matched[i]],
3001                              (enum reg_class) goal_alternative[i],
3002                              operand_mode[i],
3003                              operand_mode[goal_alternative_matched[i]],
3004                              0, 0, NULL_RTX);
3005             operand_reloadnum[goal_alternative_matched[i]] = output_reloadnum;
3006           }
3007         else if (modified[i] == RELOAD_WRITE
3008                  && modified[goal_alternative_matched[i]] == RELOAD_READ)
3009           {
3010             operand_reloadnum[goal_alternative_matched[i]]
3011               = push_reload (recog_operand[goal_alternative_matched[i]],
3012                              recog_operand[i],
3013                              recog_operand_loc[goal_alternative_matched[i]],
3014                              recog_operand_loc[i],
3015                              (enum reg_class) goal_alternative[i],
3016                              operand_mode[goal_alternative_matched[i]],
3017                              operand_mode[i],
3018                              0, 0, NULL_RTX);
3019             operand_reloadnum[i] = output_reloadnum;
3020           }
3021         else if (insn_code_number >= 0)
3022           abort ();
3023         else
3024           {
3025             error_for_asm (insn, "inconsistent operand constraints in an `asm'");
3026             /* Avoid further trouble with this insn.  */
3027             PATTERN (insn) = gen_rtx (USE, VOIDmode, const0_rtx);
3028             n_reloads = 0;
3029             return;
3030           }
3031       }
3032     else if (goal_alternative_matched[i] < 0
3033              && goal_alternative_matches[i] < 0
3034              && optimize)
3035       {
3036         rtx operand = recog_operand[i];
3037         /* For each non-matching operand that's a pseudo-register
3038            that didn't get a hard register, make an optional reload.
3039            This may get done even if the insn needs no reloads otherwise.  */
3040         /* (It would be safe to make an optional reload for a matching pair
3041            of operands, but we don't bother yet.)  */
3042         while (GET_CODE (operand) == SUBREG)
3043           operand = XEXP (operand, 0);
3044         if (GET_CODE (operand) == REG
3045             && REGNO (operand) >= FIRST_PSEUDO_REGISTER
3046             && reg_renumber[REGNO (operand)] < 0
3047             && (enum reg_class) goal_alternative[i] != NO_REGS
3048             /* Don't make optional output reloads for jump insns
3049                (such as aobjeq on the vax).  */
3050             && (modified[i] == RELOAD_READ
3051                 || GET_CODE (insn) != JUMP_INSN))
3052           operand_reloadnum[i]
3053             = push_reload (modified[i] != RELOAD_WRITE ? recog_operand[i] : 0,
3054                            modified[i] != RELOAD_READ ? recog_operand[i] : 0,
3055                            modified[i] != RELOAD_WRITE ? recog_operand_loc[i] : 0,
3056                            modified[i] != RELOAD_READ ? recog_operand_loc[i] : 0,
3057                            (enum reg_class) goal_alternative[i],
3058                            (modified[i] == RELOAD_WRITE ? VOIDmode : operand_mode[i]),
3059                            (modified[i] == RELOAD_READ ? VOIDmode : operand_mode[i]),
3060                            (insn_code_number < 0 ? 0
3061                             : insn_operand_strict_low[insn_code_number][i]),
3062                            1, NULL_RTX);
3063         /* Make an optional reload for an explicit mem ref.  */
3064         else if (GET_CODE (operand) == MEM
3065                  && (enum reg_class) goal_alternative[i] != NO_REGS
3066                  /* Don't make optional output reloads for jump insns
3067                     (such as aobjeq on the vax).  */
3068                  && (modified[i] == RELOAD_READ
3069                      || GET_CODE (insn) != JUMP_INSN))
3070           operand_reloadnum[i]
3071             = push_reload (modified[i] != RELOAD_WRITE ? recog_operand[i] : 0,
3072                            modified[i] != RELOAD_READ ? recog_operand[i] : 0,
3073                            modified[i] != RELOAD_WRITE ? recog_operand_loc[i] : 0,
3074                            modified[i] != RELOAD_READ ? recog_operand_loc[i] : 0,
3075                            (enum reg_class) goal_alternative[i],
3076                            (modified[i] == RELOAD_WRITE ? VOIDmode : operand_mode[i]),
3077                            (modified[i] == RELOAD_READ ? VOIDmode : operand_mode[i]),
3078                            (insn_code_number < 0 ? 0
3079                             : insn_operand_strict_low[insn_code_number][i]),
3080                            1, NULL_RTX);
3081         else
3082           non_reloaded_operands[n_non_reloaded_operands++] = recog_operand[i];
3083       }
3084     else if (goal_alternative_matched[i] < 0
3085              && goal_alternative_matches[i] < 0)
3086       non_reloaded_operands[n_non_reloaded_operands++] = recog_operand[i];
3087
3088   /* Record the values of the earlyclobber operands for the caller.  */
3089   if (goal_earlyclobber)
3090     for (i = 0; i < noperands; i++)
3091       if (goal_alternative_earlyclobber[i])
3092         reload_earlyclobbers[n_earlyclobbers++] = recog_operand[i];
3093
3094   /* If this insn pattern contains any MATCH_DUP's, make sure that
3095      they will be substituted if the operands they match are substituted.
3096      Also do now any substitutions we already did on the operands.
3097
3098      Don't do this if we aren't making replacements because we might be
3099      propagating things allocated by frame pointer elimination into places
3100      it doesn't expect.  */
3101
3102   if (insn_code_number >= 0 && replace)
3103     for (i = insn_n_dups[insn_code_number] - 1; i >= 0; i--)
3104       {
3105         int opno = recog_dup_num[i];
3106         *recog_dup_loc[i] = *recog_operand_loc[opno];
3107         if (operand_reloadnum[opno] >= 0)
3108           push_replacement (recog_dup_loc[i], operand_reloadnum[opno],
3109                             insn_operand_mode[insn_code_number][opno]);
3110       }
3111
3112 #if 0
3113   /* This loses because reloading of prior insns can invalidate the equivalence
3114      (or at least find_equiv_reg isn't smart enough to find it any more),
3115      causing this insn to need more reload regs than it needed before.
3116      It may be too late to make the reload regs available.
3117      Now this optimization is done safely in choose_reload_regs.  */
3118
3119   /* For each reload of a reg into some other class of reg,
3120      search for an existing equivalent reg (same value now) in the right class.
3121      We can use it as long as we don't need to change its contents.  */
3122   for (i = 0; i < n_reloads; i++)
3123     if (reload_reg_rtx[i] == 0
3124         && reload_in[i] != 0
3125         && GET_CODE (reload_in[i]) == REG
3126         && reload_out[i] == 0)
3127       {
3128         reload_reg_rtx[i]
3129           = find_equiv_reg (reload_in[i], insn, reload_reg_class[i], -1,
3130                             static_reload_reg_p, 0, reload_inmode[i]);
3131         /* Prevent generation of insn to load the value
3132            because the one we found already has the value.  */
3133         if (reload_reg_rtx[i])
3134           reload_in[i] = reload_reg_rtx[i];
3135       }
3136 #endif
3137
3138 #else /* no REGISTER_CONSTRAINTS */
3139   int noperands;
3140   int insn_code_number;
3141   int goal_earlyclobber = 0; /* Always 0, to make combine_reloads happen.  */
3142   register int i;
3143   rtx body = PATTERN (insn);
3144
3145   n_reloads = 0;
3146   n_replacements = 0;
3147   n_earlyclobbers = 0;
3148   replace_reloads = replace;
3149   this_insn = insn;
3150
3151   /* Find what kind of insn this is.  NOPERANDS gets number of operands.
3152      Store the operand values in RECOG_OPERAND and the locations
3153      of the words in the insn that point to them in RECOG_OPERAND_LOC.
3154      Return if the insn needs no reload processing.  */
3155
3156   switch (GET_CODE (body))
3157     {
3158     case USE:
3159     case CLOBBER:
3160     case ASM_INPUT:
3161     case ADDR_VEC:
3162     case ADDR_DIFF_VEC:
3163       return;
3164
3165     case PARALLEL:
3166     case SET:
3167       noperands = asm_noperands (body);
3168       if (noperands >= 0)
3169         {
3170           /* This insn is an `asm' with operands.
3171              First, find out how many operands, and allocate space.  */
3172
3173           insn_code_number = -1;
3174           /* ??? This is a bug! ???
3175              Give up and delete this insn if it has too many operands.  */
3176           if (noperands > MAX_RECOG_OPERANDS)
3177             abort ();
3178
3179           /* Now get the operand values out of the insn.  */
3180
3181           decode_asm_operands (body, recog_operand, recog_operand_loc,
3182                                NULL_PTR, NULL_PTR);
3183           break;
3184         }
3185
3186     default:
3187       /* Ordinary insn: recognize it, allocate space for operands and
3188          constraints, and get them out via insn_extract.  */
3189
3190       insn_code_number = recog_memoized (insn);
3191       noperands = insn_n_operands[insn_code_number];
3192       insn_extract (insn);
3193     }
3194
3195   if (noperands == 0)
3196     return;
3197
3198   for (i = 0; i < noperands; i++)
3199     {
3200       register RTX_CODE code = GET_CODE (recog_operand[i]);
3201       int is_set_dest = GET_CODE (body) == SET && (i == 0);
3202
3203       if (insn_code_number >= 0)
3204         if (insn_operand_address_p[insn_code_number][i])
3205           find_reloads_address (VOIDmode, NULL_PTR,
3206                                 recog_operand[i], recog_operand_loc[i],
3207                                 recog_operand[i], ind_levels);
3208       if (code == MEM)
3209         find_reloads_address (GET_MODE (recog_operand[i]),
3210                               recog_operand_loc[i],
3211                               XEXP (recog_operand[i], 0),
3212                               &XEXP (recog_operand[i], 0),
3213                               recog_operand[i], ind_levels);
3214       if (code == SUBREG)
3215         recog_operand[i] = *recog_operand_loc[i]
3216           = find_reloads_toplev (recog_operand[i], ind_levels, is_set_dest);
3217       if (code == REG)
3218         {
3219           register int regno = REGNO (recog_operand[i]);
3220           if (reg_equiv_constant[regno] != 0 && !is_set_dest)
3221             recog_operand[i] = *recog_operand_loc[i]
3222               = reg_equiv_constant[regno];
3223 #if 0 /* This might screw code in reload1.c to delete prior output-reload
3224          that feeds this insn.  */
3225           if (reg_equiv_mem[regno] != 0)
3226             recog_operand[i] = *recog_operand_loc[i]
3227               = reg_equiv_mem[regno];
3228 #endif
3229         }
3230       /* All operands are non-reloaded.  */
3231       non_reloaded_operands[n_non_reloaded_operands++] = recog_operand[i];
3232     }
3233 #endif /* no REGISTER_CONSTRAINTS */
3234
3235   /* Determine which part of the insn each reload is needed for,
3236      based on which operand the reload is needed for.
3237      Reloads of entire operands are classified as RELOAD_OTHER.
3238      So are reloads for which a unique purpose is not known.  */
3239
3240   for (i = 0; i < n_reloads; i++)
3241     {
3242       reload_when_needed[i] = RELOAD_OTHER;
3243
3244       if (reload_needed_for[i] != 0 && ! reload_needed_for_multiple[i])
3245         {
3246           int j;
3247           int output_address = 0;
3248           int input_address = 0;
3249           int operand_address = 0;
3250
3251           /* This reload is needed only for the address of something.
3252              Determine whether it is needed for addressing an operand
3253              being reloaded for input, whether it is needed for an
3254              operand being reloaded for output, and whether it is needed
3255              for addressing an operand that won't really be reloaded.
3256
3257              Note that we know that this reload is needed in only one address,
3258              but we have not yet checked for the case where that same address
3259              is used in both input and output reloads.
3260              The following code detects this case.  */
3261
3262           for (j = 0; j < n_reloads; j++)
3263             if (reload_needed_for[i] == reload_in[j]
3264                 || reload_needed_for[i] == reload_out[j])
3265               {
3266                 if (reload_optional[j])
3267                   operand_address = 1;
3268                 else
3269                   {
3270                     if (reload_needed_for[i] == reload_in[j])
3271                       input_address = 1;
3272                     if (reload_needed_for[i] == reload_out[j])
3273                       output_address = 1;
3274                   }
3275               }
3276           /* Don't ignore memrefs without optional reloads.  */
3277           for (j = 0; j < n_non_reloaded_operands; j++)
3278             if (reload_needed_for[i] == non_reloaded_operands[j])
3279               operand_address = 1;
3280
3281           /* If it is needed for only one of those, record which one.  */
3282
3283           if (input_address && ! output_address && ! operand_address)
3284             reload_when_needed[i] = RELOAD_FOR_INPUT_RELOAD_ADDRESS;
3285           if (output_address && ! input_address && ! operand_address)
3286             reload_when_needed[i] = RELOAD_FOR_OUTPUT_RELOAD_ADDRESS;
3287           if (operand_address && ! input_address && ! output_address)
3288             reload_when_needed[i] = RELOAD_FOR_OPERAND_ADDRESS;
3289
3290           /* Indicate those RELOAD_OTHER reloads which, though they have
3291              0 for reload_output, still cannot overlap an output reload.  */
3292
3293           if (output_address && reload_when_needed[i] == RELOAD_OTHER)
3294             reload_needed_for_multiple[i] = 1;
3295
3296           /* If we have earlyclobbers, make sure nothing overlaps them.  */
3297           if (n_earlyclobbers > 0)
3298             {
3299               reload_when_needed[i] = RELOAD_OTHER;
3300               reload_needed_for_multiple[i] = 1;
3301             }
3302         }
3303     }
3304
3305   /* Perhaps an output reload can be combined with another
3306      to reduce needs by one.  */
3307   if (!goal_earlyclobber)
3308     combine_reloads ();
3309 }
3310
3311 /* Return 1 if alternative number ALTNUM in constraint-string CONSTRAINT
3312    accepts a memory operand with constant address.  */
3313
3314 static int
3315 alternative_allows_memconst (constraint, altnum)
3316      char *constraint;
3317      int altnum;
3318 {
3319   register int c;
3320   /* Skip alternatives before the one requested.  */
3321   while (altnum > 0)
3322     {
3323       while (*constraint++ != ',');
3324       altnum--;
3325     }
3326   /* Scan the requested alternative for 'm' or 'o'.
3327      If one of them is present, this alternative accepts memory constants.  */
3328   while ((c = *constraint++) && c != ',' && c != '#')
3329     if (c == 'm' || c == 'o')
3330       return 1;
3331   return 0;
3332 }
3333 \f
3334 /* Scan X for memory references and scan the addresses for reloading.
3335    Also checks for references to "constant" regs that we want to eliminate
3336    and replaces them with the values they stand for.
3337    We may alter X destructively if it contains a reference to such.
3338    If X is just a constant reg, we return the equivalent value
3339    instead of X.
3340
3341    IND_LEVELS says how many levels of indirect addressing this machine
3342    supports.
3343
3344    IS_SET_DEST is true if X is the destination of a SET, which is not
3345    appropriate to be replaced by a constant.  */
3346
3347 static rtx
3348 find_reloads_toplev (x, ind_levels, is_set_dest)
3349      rtx x;
3350      int ind_levels;
3351      int is_set_dest;
3352 {
3353   register RTX_CODE code = GET_CODE (x);
3354
3355   register char *fmt = GET_RTX_FORMAT (code);
3356   register int i;
3357
3358   if (code == REG)
3359     {
3360       /* This code is duplicated for speed in find_reloads.  */
3361       register int regno = REGNO (x);
3362       if (reg_equiv_constant[regno] != 0 && !is_set_dest)
3363         x = reg_equiv_constant[regno];
3364 #if 0
3365 /*  This creates (subreg (mem...)) which would cause an unnecessary
3366     reload of the mem.  */
3367       else if (reg_equiv_mem[regno] != 0)
3368         x = reg_equiv_mem[regno];
3369 #endif
3370       else if (reg_equiv_address[regno] != 0)
3371         {
3372           /* If reg_equiv_address varies, it may be shared, so copy it.  */
3373           rtx addr = reg_equiv_address[regno];
3374
3375           if (rtx_varies_p (addr))
3376             addr = copy_rtx (addr);
3377
3378           x = gen_rtx (MEM, GET_MODE (x), addr);
3379           RTX_UNCHANGING_P (x) = RTX_UNCHANGING_P (regno_reg_rtx[regno]);
3380           find_reloads_address (GET_MODE (x), NULL_PTR,
3381                                 XEXP (x, 0),
3382                                 &XEXP (x, 0), x, ind_levels);
3383         }
3384       return x;
3385     }
3386   if (code == MEM)
3387     {
3388       rtx tem = x;
3389       find_reloads_address (GET_MODE (x), &tem, XEXP (x, 0), &XEXP (x, 0),
3390                             x, ind_levels);
3391       return tem;
3392     }
3393
3394   if (code == SUBREG && GET_CODE (SUBREG_REG (x)) == REG)
3395     {
3396       /* Check for SUBREG containing a REG that's equivalent to a constant.
3397          If the constant has a known value, truncate it right now.
3398          Similarly if we are extracting a single-word of a multi-word
3399          constant.  If the constant is symbolic, allow it to be substituted
3400          normally.  push_reload will strip the subreg later.  If the
3401          constant is VOIDmode, abort because we will lose the mode of
3402          the register (this should never happen because one of the cases
3403          above should handle it).  */
3404
3405       register int regno = REGNO (SUBREG_REG (x));
3406       rtx tem;
3407
3408       if (subreg_lowpart_p (x)
3409           && regno >= FIRST_PSEUDO_REGISTER && reg_renumber[regno] < 0
3410           && reg_equiv_constant[regno] != 0
3411           && (tem = gen_lowpart_common (GET_MODE (x),
3412                                         reg_equiv_constant[regno])) != 0)
3413         return tem;
3414
3415       if (GET_MODE_BITSIZE (GET_MODE (x)) == BITS_PER_WORD
3416           && regno >= FIRST_PSEUDO_REGISTER && reg_renumber[regno] < 0
3417           && reg_equiv_constant[regno] != 0
3418           && (tem = operand_subword (reg_equiv_constant[regno],
3419                                      SUBREG_WORD (x), 0,
3420                                      GET_MODE (SUBREG_REG (x)))) != 0)
3421         return tem;
3422
3423       if (regno >= FIRST_PSEUDO_REGISTER && reg_renumber[regno] < 0
3424           && reg_equiv_constant[regno] != 0
3425           && GET_MODE (reg_equiv_constant[regno]) == VOIDmode)
3426         abort ();
3427
3428       /* If the subreg contains a reg that will be converted to a mem,
3429          convert the subreg to a narrower memref now.
3430          Otherwise, we would get (subreg (mem ...) ...),
3431          which would force reload of the mem.
3432
3433          We also need to do this if there is an equivalent MEM that is
3434          not offsettable.  In that case, alter_subreg would produce an
3435          invalid address on big-endian machines.
3436
3437          For machines that extend byte loads, we must not reload using
3438          a wider mode if we have a paradoxical SUBREG.  find_reloads will
3439          force a reload in that case.  So we should not do anything here.  */
3440
3441       else if (regno >= FIRST_PSEUDO_REGISTER
3442 #if defined(BYTE_LOADS_ZERO_EXTEND) || defined(BYTE_LOADS_SIGN_EXTEND)
3443                && (GET_MODE_SIZE (GET_MODE (x))
3444                    <= GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
3445 #endif
3446                && (reg_equiv_address[regno] != 0
3447                    || (reg_equiv_mem[regno] != 0
3448                        && ! offsettable_memref_p (reg_equiv_mem[regno]))))
3449         {
3450           int offset = SUBREG_WORD (x) * UNITS_PER_WORD;
3451           rtx addr = (reg_equiv_address[regno] ? reg_equiv_address[regno]
3452                       : XEXP (reg_equiv_mem[regno], 0));
3453 #if BYTES_BIG_ENDIAN
3454           int size;
3455           size = GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)));
3456           offset += MIN (size, UNITS_PER_WORD);
3457           size = GET_MODE_SIZE (GET_MODE (x));
3458           offset -= MIN (size, UNITS_PER_WORD);
3459 #endif
3460           addr = plus_constant (addr, offset);
3461           x = gen_rtx (MEM, GET_MODE (x), addr);
3462           RTX_UNCHANGING_P (x) = RTX_UNCHANGING_P (regno_reg_rtx[regno]);
3463           find_reloads_address (GET_MODE (x), NULL_PTR,
3464                                 XEXP (x, 0),
3465                                 &XEXP (x, 0), x, ind_levels);
3466         }
3467
3468     }
3469
3470   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3471     {
3472       if (fmt[i] == 'e')
3473         XEXP (x, i) = find_reloads_toplev (XEXP (x, i),
3474                                            ind_levels, is_set_dest);
3475     }
3476   return x;
3477 }
3478
3479 static rtx
3480 make_memloc (ad, regno)
3481      rtx ad;
3482      int regno;
3483 {
3484   register int i;
3485   rtx tem = reg_equiv_address[regno];
3486   for (i = 0; i < n_memlocs; i++)
3487     if (rtx_equal_p (tem, XEXP (memlocs[i], 0)))
3488       return memlocs[i];
3489
3490   /* If TEM might contain a pseudo, we must copy it to avoid
3491      modifying it when we do the substitution for the reload.  */
3492   if (rtx_varies_p (tem))
3493     tem = copy_rtx (tem);
3494
3495   tem = gen_rtx (MEM, GET_MODE (ad), tem);
3496   RTX_UNCHANGING_P (tem) = RTX_UNCHANGING_P (regno_reg_rtx[regno]);
3497   memlocs[n_memlocs++] = tem;
3498   return tem;
3499 }
3500
3501 /* Record all reloads needed for handling memory address AD
3502    which appears in *LOC in a memory reference to mode MODE
3503    which itself is found in location  *MEMREFLOC.
3504    Note that we take shortcuts assuming that no multi-reg machine mode
3505    occurs as part of an address.
3506
3507    OPERAND is the operand of the insn within which this address appears.
3508
3509    IND_LEVELS says how many levels of indirect addressing this machine
3510    supports.
3511
3512    Value is nonzero if this address is reloaded or replaced as a whole.
3513    This is interesting to the caller if the address is an autoincrement.
3514
3515    Note that there is no verification that the address will be valid after
3516    this routine does its work.  Instead, we rely on the fact that the address
3517    was valid when reload started.  So we need only undo things that reload
3518    could have broken.  These are wrong register types, pseudos not allocated
3519    to a hard register, and frame pointer elimination.  */
3520
3521 static int
3522 find_reloads_address (mode, memrefloc, ad, loc, operand, ind_levels)
3523      enum machine_mode mode;
3524      rtx *memrefloc;
3525      rtx ad;
3526      rtx *loc;
3527      rtx operand;
3528      int ind_levels;
3529 {
3530   register int regno;
3531   rtx tem;
3532
3533   /* If the address is a register, see if it is a legitimate address and
3534      reload if not.  We first handle the cases where we need not reload
3535      or where we must reload in a non-standard way.  */
3536
3537   if (GET_CODE (ad) == REG)
3538     {
3539       regno = REGNO (ad);
3540
3541       if (reg_equiv_constant[regno] != 0
3542           && strict_memory_address_p (mode, reg_equiv_constant[regno]))
3543         {
3544           *loc = ad = reg_equiv_constant[regno];
3545           return 1;
3546         }
3547
3548       else if (reg_equiv_address[regno] != 0)
3549         {
3550           tem = make_memloc (ad, regno);
3551           find_reloads_address (GET_MODE (tem), NULL_PTR, XEXP (tem, 0),
3552                                 &XEXP (tem, 0), operand, ind_levels);
3553           push_reload (tem, NULL_RTX, loc, NULL_PTR, BASE_REG_CLASS,
3554                        GET_MODE (ad), VOIDmode, 0, 0,
3555                        operand);
3556           return 1;
3557         }
3558
3559       else if (reg_equiv_mem[regno] != 0)
3560         {
3561           tem = XEXP (reg_equiv_mem[regno], 0);
3562
3563           /* If we can't indirect any more, a pseudo must be reloaded.
3564              If the pseudo's address in its MEM is a SYMBOL_REF, it
3565              must be reloaded unless indirect_symref_ok.  Otherwise, it
3566              can be reloaded if the address is REG or REG + CONST_INT.  */
3567
3568           if (ind_levels > 0
3569               && ! (GET_CODE (tem) == SYMBOL_REF && ! indirect_symref_ok)
3570               && ((GET_CODE (tem) == REG
3571                    && REGNO (tem) < FIRST_PSEUDO_REGISTER)
3572                   || (GET_CODE (tem) == PLUS
3573                       && GET_CODE (XEXP (tem, 0)) == REG
3574                       && REGNO (XEXP (tem, 0)) < FIRST_PSEUDO_REGISTER
3575                       && GET_CODE (XEXP (tem, 1)) == CONST_INT)))
3576             return 0;
3577         }
3578
3579       /* The only remaining case where we can avoid a reload is if this is a
3580          hard register that is valid as a base register and which is not the
3581          subject of a CLOBBER in this insn.  */
3582
3583       else if (regno < FIRST_PSEUDO_REGISTER && REGNO_OK_FOR_BASE_P (regno)
3584                && ! regno_clobbered_p (regno, this_insn))
3585         return 0;
3586
3587       /* If we do not have one of the cases above, we must do the reload.  */
3588       push_reload (ad, NULL_RTX, loc, NULL_PTR, BASE_REG_CLASS,
3589                    GET_MODE (ad), VOIDmode, 0, 0, operand);
3590       return 1;
3591     }
3592
3593   if (strict_memory_address_p (mode, ad))
3594     {
3595       /* The address appears valid, so reloads are not needed.
3596          But the address may contain an eliminable register.
3597          This can happen because a machine with indirect addressing
3598          may consider a pseudo register by itself a valid address even when
3599          it has failed to get a hard reg.
3600          So do a tree-walk to find and eliminate all such regs.  */
3601
3602       /* But first quickly dispose of a common case.  */
3603       if (GET_CODE (ad) == PLUS
3604           && GET_CODE (XEXP (ad, 1)) == CONST_INT
3605           && GET_CODE (XEXP (ad, 0)) == REG
3606           && reg_equiv_constant[REGNO (XEXP (ad, 0))] == 0)
3607         return 0;
3608
3609       subst_reg_equivs_changed = 0;
3610       *loc = subst_reg_equivs (ad);
3611
3612       if (! subst_reg_equivs_changed)
3613         return 0;
3614
3615       /* Check result for validity after substitution.  */
3616       if (strict_memory_address_p (mode, ad))
3617         return 0;
3618     }
3619
3620   /* The address is not valid.  We have to figure out why.  One possibility
3621      is that it is itself a MEM.  This can happen when the frame pointer is
3622      being eliminated, a pseudo is not allocated to a hard register, and the
3623      offset between the frame and stack pointers is not its initial value.
3624      In that case the pseudo will have been replaced by a MEM referring to
3625      the stack pointer.  */
3626   if (GET_CODE (ad) == MEM)
3627     {
3628       /* First ensure that the address in this MEM is valid.  Then, unless
3629          indirect addresses are valid, reload the MEM into a register.  */
3630       tem = ad;
3631       find_reloads_address (GET_MODE (ad), &tem, XEXP (ad, 0), &XEXP (ad, 0),
3632                             operand, ind_levels == 0 ? 0 : ind_levels - 1);
3633
3634       /* If tem was changed, then we must create a new memory reference to
3635          hold it and store it back into memrefloc.  */
3636       if (tem != ad && memrefloc)
3637         {
3638           rtx oldref = *memrefloc;
3639           *memrefloc = copy_rtx (*memrefloc);
3640           copy_replacements (tem, XEXP (*memrefloc, 0));
3641           loc = &XEXP (*memrefloc, 0);
3642           if (operand == oldref)
3643             operand = *memrefloc;
3644         }
3645
3646       /* Check similar cases as for indirect addresses as above except
3647          that we can allow pseudos and a MEM since they should have been
3648          taken care of above.  */
3649
3650       if (ind_levels == 0
3651           || (GET_CODE (XEXP (tem, 0)) == SYMBOL_REF && ! indirect_symref_ok)
3652           || GET_CODE (XEXP (tem, 0)) == MEM
3653           || ! (GET_CODE (XEXP (tem, 0)) == REG
3654                 || (GET_CODE (XEXP (tem, 0)) == PLUS
3655                     && GET_CODE (XEXP (XEXP (tem, 0), 0)) == REG
3656                     && GET_CODE (XEXP (XEXP (tem, 0), 1)) == CONST_INT)))
3657         {
3658           /* Must use TEM here, not AD, since it is the one that will
3659              have any subexpressions reloaded, if needed.  */
3660           push_reload (tem, NULL_RTX, loc, NULL_PTR,
3661                        BASE_REG_CLASS, GET_MODE (tem), VOIDmode, 0,
3662                        0, operand);
3663           return 1;
3664         }
3665       else
3666         return 0;
3667     }
3668
3669   /* If we have address of a stack slot but it's not valid
3670      (displacement is too large), compute the sum in a register.  */
3671   else if (GET_CODE (ad) == PLUS
3672            && (XEXP (ad, 0) == frame_pointer_rtx
3673 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3674                || XEXP (ad, 0) == arg_pointer_rtx
3675 #endif
3676                || XEXP (ad, 0) == stack_pointer_rtx)
3677            && GET_CODE (XEXP (ad, 1)) == CONST_INT)
3678     {
3679       /* Unshare the MEM rtx so we can safely alter it.  */
3680       if (memrefloc)
3681         {
3682           rtx oldref = *memrefloc;
3683           *memrefloc = copy_rtx (*memrefloc);
3684           loc = &XEXP (*memrefloc, 0);
3685           if (operand == oldref)
3686             operand = *memrefloc;
3687         }
3688       if (double_reg_address_ok)
3689         {
3690           /* Unshare the sum as well.  */
3691           *loc = ad = copy_rtx (ad);
3692           /* Reload the displacement into an index reg.
3693              We assume the frame pointer or arg pointer is a base reg.  */
3694           find_reloads_address_part (XEXP (ad, 1), &XEXP (ad, 1),
3695                                      INDEX_REG_CLASS, GET_MODE (ad), operand,
3696                                      ind_levels);
3697         }
3698       else
3699         {
3700           /* If the sum of two regs is not necessarily valid,
3701              reload the sum into a base reg.
3702              That will at least work.  */
3703           find_reloads_address_part (ad, loc, BASE_REG_CLASS, Pmode,
3704                                      operand, ind_levels);
3705         }
3706       return 1;
3707     }
3708
3709   /* If we have an indexed stack slot, there are three possible reasons why
3710      it might be invalid: The index might need to be reloaded, the address
3711      might have been made by frame pointer elimination and hence have a
3712      constant out of range, or both reasons might apply.
3713
3714      We can easily check for an index needing reload, but even if that is the
3715      case, we might also have an invalid constant.  To avoid making the
3716      conservative assumption and requiring two reloads, we see if this address
3717      is valid when not interpreted strictly.  If it is, the only problem is
3718      that the index needs a reload and find_reloads_address_1 will take care
3719      of it.
3720
3721      There is still a case when we might generate an extra reload,
3722      however.  In certain cases eliminate_regs will return a MEM for a REG
3723      (see the code there for details).  In those cases, memory_address_p
3724      applied to our address will return 0 so we will think that our offset
3725      must be too large.  But it might indeed be valid and the only problem
3726      is that a MEM is present where a REG should be.  This case should be
3727      very rare and there doesn't seem to be any way to avoid it.
3728
3729      If we decide to do something here, it must be that
3730      `double_reg_address_ok' is true and that this address rtl was made by
3731      eliminate_regs.  We generate a reload of the fp/sp/ap + constant and
3732      rework the sum so that the reload register will be added to the index.
3733      This is safe because we know the address isn't shared.
3734
3735      We check for fp/ap/sp as both the first and second operand of the
3736      innermost PLUS.  */
3737
3738   else if (GET_CODE (ad) == PLUS && GET_CODE (XEXP (ad, 1)) == CONST_INT
3739            && GET_CODE (XEXP (ad, 0)) == PLUS
3740            && (XEXP (XEXP (ad, 0), 0) == frame_pointer_rtx
3741 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3742                || XEXP (XEXP (ad, 0), 0) == arg_pointer_rtx
3743 #endif
3744                || XEXP (XEXP (ad, 0), 0) == stack_pointer_rtx)
3745            && ! memory_address_p (mode, ad))
3746     {
3747       *loc = ad = gen_rtx (PLUS, GET_MODE (ad),
3748                            plus_constant (XEXP (XEXP (ad, 0), 0),
3749                                           INTVAL (XEXP (ad, 1))),
3750                            XEXP (XEXP (ad, 0), 1));
3751       find_reloads_address_part (XEXP (ad, 0), &XEXP (ad, 0), BASE_REG_CLASS,
3752                                  GET_MODE (ad), operand, ind_levels);
3753       find_reloads_address_1 (XEXP (ad, 1), 1, &XEXP (ad, 1), operand, 0);
3754
3755       return 1;
3756     }
3757
3758   else if (GET_CODE (ad) == PLUS && GET_CODE (XEXP (ad, 1)) == CONST_INT
3759            && GET_CODE (XEXP (ad, 0)) == PLUS
3760            && (XEXP (XEXP (ad, 0), 1) == frame_pointer_rtx
3761 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3762                || XEXP (XEXP (ad, 0), 1) == arg_pointer_rtx
3763 #endif
3764                || XEXP (XEXP (ad, 0), 1) == stack_pointer_rtx)
3765            && ! memory_address_p (mode, ad))
3766     {
3767       *loc = ad = gen_rtx (PLUS, GET_MODE (ad),
3768                            plus_constant (XEXP (XEXP (ad, 0), 1),
3769                                           INTVAL (XEXP (ad, 1))),
3770                            XEXP (XEXP (ad, 0), 0));
3771       find_reloads_address_part (XEXP (ad, 0), &XEXP (ad, 0), BASE_REG_CLASS,
3772                                  GET_MODE (ad), operand, ind_levels);
3773       find_reloads_address_1 (XEXP (ad, 1), 1, &XEXP (ad, 1), operand, 0);
3774
3775       return 1;
3776     }
3777
3778   /* See if address becomes valid when an eliminable register
3779      in a sum is replaced.  */
3780
3781   tem = ad;
3782   if (GET_CODE (ad) == PLUS)
3783     tem = subst_indexed_address (ad);
3784   if (tem != ad && strict_memory_address_p (mode, tem))
3785     {
3786       /* Ok, we win that way.  Replace any additional eliminable
3787          registers.  */
3788
3789       subst_reg_equivs_changed = 0;
3790       tem = subst_reg_equivs (tem);
3791
3792       /* Make sure that didn't make the address invalid again.  */
3793
3794       if (! subst_reg_equivs_changed || strict_memory_address_p (mode, tem))
3795         {
3796           *loc = tem;
3797           return 0;
3798         }
3799     }
3800
3801   /* If constants aren't valid addresses, reload the constant address
3802      into a register.  */
3803   if (CONSTANT_P (ad) && ! strict_memory_address_p (mode, ad))
3804     {
3805       /* If AD is in address in the constant pool, the MEM rtx may be shared.
3806          Unshare it so we can safely alter it.  */
3807       if (memrefloc && GET_CODE (ad) == SYMBOL_REF
3808           && CONSTANT_POOL_ADDRESS_P (ad))
3809         {
3810           rtx oldref = *memrefloc;
3811           *memrefloc = copy_rtx (*memrefloc);
3812           loc = &XEXP (*memrefloc, 0);
3813           if (operand == oldref)
3814             operand = *memrefloc;
3815         }
3816
3817       find_reloads_address_part (ad, loc, BASE_REG_CLASS, Pmode, operand,
3818                                  ind_levels);
3819       return 1;
3820     }
3821
3822   return find_reloads_address_1 (ad, 0, loc, operand, ind_levels);
3823 }
3824 \f
3825 /* Find all pseudo regs appearing in AD
3826    that are eliminable in favor of equivalent values
3827    and do not have hard regs; replace them by their equivalents.  */
3828
3829 static rtx
3830 subst_reg_equivs (ad)
3831      rtx ad;
3832 {
3833   register RTX_CODE code = GET_CODE (ad);
3834   register int i;
3835   register char *fmt;
3836
3837   switch (code)
3838     {
3839     case HIGH:
3840     case CONST_INT:
3841     case CONST:
3842     case CONST_DOUBLE:
3843     case SYMBOL_REF:
3844     case LABEL_REF:
3845     case PC:
3846     case CC0:
3847       return ad;
3848
3849     case REG:
3850       {
3851         register int regno = REGNO (ad);
3852
3853         if (reg_equiv_constant[regno] != 0)
3854           {
3855             subst_reg_equivs_changed = 1;
3856             return reg_equiv_constant[regno];
3857           }
3858       }
3859       return ad;
3860
3861     case PLUS:
3862       /* Quickly dispose of a common case.  */
3863       if (XEXP (ad, 0) == frame_pointer_rtx
3864           && GET_CODE (XEXP (ad, 1)) == CONST_INT)
3865         return ad;
3866     }
3867
3868   fmt = GET_RTX_FORMAT (code);
3869   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3870     if (fmt[i] == 'e')
3871       XEXP (ad, i) = subst_reg_equivs (XEXP (ad, i));
3872   return ad;
3873 }
3874 \f
3875 /* Compute the sum of X and Y, making canonicalizations assumed in an
3876    address, namely: sum constant integers, surround the sum of two
3877    constants with a CONST, put the constant as the second operand, and
3878    group the constant on the outermost sum.
3879
3880    This routine assumes both inputs are already in canonical form.  */
3881
3882 rtx
3883 form_sum (x, y)
3884      rtx x, y;
3885 {
3886   rtx tem;
3887
3888   if (GET_CODE (x) == CONST_INT)
3889     return plus_constant (y, INTVAL (x));
3890   else if (GET_CODE (y) == CONST_INT)
3891     return plus_constant (x, INTVAL (y));
3892   else if (CONSTANT_P (x))
3893     tem = x, x = y, y = tem;
3894
3895   if (GET_CODE (x) == PLUS && CONSTANT_P (XEXP (x, 1)))
3896     return form_sum (XEXP (x, 0), form_sum (XEXP (x, 1), y));
3897
3898   /* Note that if the operands of Y are specified in the opposite
3899      order in the recursive calls below, infinite recursion will occur.  */
3900   if (GET_CODE (y) == PLUS && CONSTANT_P (XEXP (y, 1)))
3901     return form_sum (form_sum (x, XEXP (y, 0)), XEXP (y, 1));
3902
3903   /* If both constant, encapsulate sum.  Otherwise, just form sum.  A
3904      constant will have been placed second.  */
3905   if (CONSTANT_P (x) && CONSTANT_P (y))
3906     {
3907       if (GET_CODE (x) == CONST)
3908         x = XEXP (x, 0);
3909       if (GET_CODE (y) == CONST)
3910         y = XEXP (y, 0);
3911
3912       return gen_rtx (CONST, VOIDmode, gen_rtx (PLUS, Pmode, x, y));
3913     }
3914
3915   return gen_rtx (PLUS, Pmode, x, y);
3916 }
3917 \f
3918 /* If ADDR is a sum containing a pseudo register that should be
3919    replaced with a constant (from reg_equiv_constant),
3920    return the result of doing so, and also apply the associative
3921    law so that the result is more likely to be a valid address.
3922    (But it is not guaranteed to be one.)
3923
3924    Note that at most one register is replaced, even if more are
3925    replaceable.  Also, we try to put the result into a canonical form
3926    so it is more likely to be a valid address.
3927
3928    In all other cases, return ADDR.  */
3929
3930 static rtx
3931 subst_indexed_address (addr)
3932      rtx addr;
3933 {
3934   rtx op0 = 0, op1 = 0, op2 = 0;
3935   rtx tem;
3936   int regno;
3937
3938   if (GET_CODE (addr) == PLUS)
3939     {
3940       /* Try to find a register to replace.  */
3941       op0 = XEXP (addr, 0), op1 = XEXP (addr, 1), op2 = 0;
3942       if (GET_CODE (op0) == REG
3943           && (regno = REGNO (op0)) >= FIRST_PSEUDO_REGISTER
3944           && reg_renumber[regno] < 0
3945           && reg_equiv_constant[regno] != 0)
3946         op0 = reg_equiv_constant[regno];
3947       else if (GET_CODE (op1) == REG
3948           && (regno = REGNO (op1)) >= FIRST_PSEUDO_REGISTER
3949           && reg_renumber[regno] < 0
3950           && reg_equiv_constant[regno] != 0)
3951         op1 = reg_equiv_constant[regno];
3952       else if (GET_CODE (op0) == PLUS
3953                && (tem = subst_indexed_address (op0)) != op0)
3954         op0 = tem;
3955       else if (GET_CODE (op1) == PLUS
3956                && (tem = subst_indexed_address (op1)) != op1)
3957         op1 = tem;
3958       else
3959         return addr;
3960
3961       /* Pick out up to three things to add.  */
3962       if (GET_CODE (op1) == PLUS)
3963         op2 = XEXP (op1, 1), op1 = XEXP (op1, 0);
3964       else if (GET_CODE (op0) == PLUS)
3965         op2 = op1, op1 = XEXP (op0, 1), op0 = XEXP (op0, 0);
3966
3967       /* Compute the sum.  */
3968       if (op2 != 0)
3969         op1 = form_sum (op1, op2);
3970       if (op1 != 0)
3971         op0 = form_sum (op0, op1);
3972
3973       return op0;
3974     }
3975   return addr;
3976 }
3977 \f
3978 /* Record the pseudo registers we must reload into hard registers
3979    in a subexpression of a would-be memory address, X.
3980    (This function is not called if the address we find is strictly valid.)
3981    CONTEXT = 1 means we are considering regs as index regs,
3982    = 0 means we are considering them as base regs.
3983
3984    OPERAND is the operand of the insn within which this address appears.
3985
3986    IND_LEVELS says how many levels of indirect addressing are
3987    supported at this point in the address.
3988
3989    We return nonzero if X, as a whole, is reloaded or replaced.  */
3990
3991 /* Note that we take shortcuts assuming that no multi-reg machine mode
3992    occurs as part of an address.
3993    Also, this is not fully machine-customizable; it works for machines
3994    such as vaxes and 68000's and 32000's, but other possible machines
3995    could have addressing modes that this does not handle right.  */
3996
3997 static int
3998 find_reloads_address_1 (x, context, loc, operand, ind_levels)
3999      rtx x;
4000      int context;
4001      rtx *loc;
4002      rtx operand;
4003      int ind_levels;
4004 {
4005   register RTX_CODE code = GET_CODE (x);
4006
4007   if (code == PLUS)
4008     {
4009       register rtx op0 = XEXP (x, 0);
4010       register rtx op1 = XEXP (x, 1);
4011       register RTX_CODE code0 = GET_CODE (op0);
4012       register RTX_CODE code1 = GET_CODE (op1);
4013       if (code0 == MULT || code0 == SIGN_EXTEND || code1 == MEM)
4014         {
4015           find_reloads_address_1 (op0, 1, &XEXP (x, 0), operand, ind_levels);
4016           find_reloads_address_1 (op1, 0, &XEXP (x, 1), operand, ind_levels);
4017         }
4018       else if (code1 == MULT || code1 == SIGN_EXTEND || code0 == MEM)
4019         {
4020           find_reloads_address_1 (op0, 0, &XEXP (x, 0), operand, ind_levels);
4021           find_reloads_address_1 (op1, 1, &XEXP (x, 1), operand, ind_levels);
4022         }
4023       else if (code0 == CONST_INT || code0 == CONST
4024                || code0 == SYMBOL_REF || code0 == LABEL_REF)
4025         {
4026           find_reloads_address_1 (op1, 0, &XEXP (x, 1), operand, ind_levels);
4027         }
4028       else if (code1 == CONST_INT || code1 == CONST
4029                || code1 == SYMBOL_REF || code1 == LABEL_REF)
4030         {
4031           find_reloads_address_1 (op0, 0, &XEXP (x, 0), operand, ind_levels);
4032         }
4033       else if (code0 == REG && code1 == REG)
4034         {
4035           if (REG_OK_FOR_INDEX_P (op0)
4036               && REG_OK_FOR_BASE_P (op1))
4037             return 0;
4038           else if (REG_OK_FOR_INDEX_P (op1)
4039               && REG_OK_FOR_BASE_P (op0))
4040             return 0;
4041           else if (REG_OK_FOR_BASE_P (op1))
4042             find_reloads_address_1 (op0, 1, &XEXP (x, 0), operand, ind_levels);
4043           else if (REG_OK_FOR_BASE_P (op0))
4044             find_reloads_address_1 (op1, 1, &XEXP (x, 1), operand, ind_levels);
4045           else if (REG_OK_FOR_INDEX_P (op1))
4046             find_reloads_address_1 (op0, 0, &XEXP (x, 0), operand, ind_levels);
4047           else if (REG_OK_FOR_INDEX_P (op0))
4048             find_reloads_address_1 (op1, 0, &XEXP (x, 1), operand, ind_levels);
4049           else
4050             {
4051               find_reloads_address_1 (op0, 1, &XEXP (x, 0), operand,
4052                                       ind_levels);
4053               find_reloads_address_1 (op1, 0, &XEXP (x, 1), operand,
4054                                       ind_levels);
4055             }
4056         }
4057       else if (code0 == REG)
4058         {
4059           find_reloads_address_1 (op0, 1, &XEXP (x, 0), operand, ind_levels);
4060           find_reloads_address_1 (op1, 0, &XEXP (x, 1), operand, ind_levels);
4061         }
4062       else if (code1 == REG)
4063         {
4064           find_reloads_address_1 (op1, 1, &XEXP (x, 1), operand, ind_levels);
4065           find_reloads_address_1 (op0, 0, &XEXP (x, 0), operand, ind_levels);
4066         }
4067     }
4068   else if (code == POST_INC || code == POST_DEC
4069            || code == PRE_INC || code == PRE_DEC)
4070     {
4071       if (GET_CODE (XEXP (x, 0)) == REG)
4072         {
4073           register int regno = REGNO (XEXP (x, 0));
4074           int value = 0;
4075           rtx x_orig = x;
4076
4077           /* A register that is incremented cannot be constant!  */
4078           if (regno >= FIRST_PSEUDO_REGISTER
4079               && reg_equiv_constant[regno] != 0)
4080             abort ();
4081
4082           /* Handle a register that is equivalent to a memory location
4083              which cannot be addressed directly.  */
4084           if (reg_equiv_address[regno] != 0)
4085             {
4086               rtx tem = make_memloc (XEXP (x, 0), regno);
4087               /* First reload the memory location's address.  */
4088               find_reloads_address (GET_MODE (tem), 0, XEXP (tem, 0),
4089                                     &XEXP (tem, 0), operand, ind_levels);
4090               /* Put this inside a new increment-expression.  */
4091               x = gen_rtx (GET_CODE (x), GET_MODE (x), tem);
4092               /* Proceed to reload that, as if it contained a register.  */
4093             }
4094
4095           /* If we have a hard register that is ok as an index,
4096              don't make a reload.  If an autoincrement of a nice register
4097              isn't "valid", it must be that no autoincrement is "valid".
4098              If that is true and something made an autoincrement anyway,
4099              this must be a special context where one is allowed.
4100              (For example, a "push" instruction.)
4101              We can't improve this address, so leave it alone.  */
4102
4103           /* Otherwise, reload the autoincrement into a suitable hard reg
4104              and record how much to increment by.  */
4105
4106           if (reg_renumber[regno] >= 0)
4107             regno = reg_renumber[regno];
4108           if ((regno >= FIRST_PSEUDO_REGISTER
4109                || !(context ? REGNO_OK_FOR_INDEX_P (regno)
4110                     : REGNO_OK_FOR_BASE_P (regno))))
4111             {
4112               register rtx link;
4113
4114               int reloadnum
4115                 = push_reload (x, NULL_RTX, loc, NULL_PTR,
4116                                context ? INDEX_REG_CLASS : BASE_REG_CLASS,
4117                                GET_MODE (x), GET_MODE (x), VOIDmode, 0, operand);
4118               reload_inc[reloadnum]
4119                 = find_inc_amount (PATTERN (this_insn), XEXP (x_orig, 0));
4120
4121               value = 1;
4122
4123 #ifdef AUTO_INC_DEC
4124               /* Update the REG_INC notes.  */
4125
4126               for (link = REG_NOTES (this_insn);
4127                    link; link = XEXP (link, 1))
4128                 if (REG_NOTE_KIND (link) == REG_INC
4129                     && REGNO (XEXP (link, 0)) == REGNO (XEXP (x_orig, 0)))
4130                   push_replacement (&XEXP (link, 0), reloadnum, VOIDmode);
4131 #endif
4132             }
4133           return value;
4134         }
4135       else if (GET_CODE (XEXP (x, 0)) == MEM)
4136         {
4137           /* This is probably the result of a substitution, by eliminate_regs,
4138              of an equivalent address for a pseudo that was not allocated to a
4139              hard register.  Verify that the specified address is valid and
4140              reload it into a register.  */
4141           rtx tem = XEXP (x, 0);
4142           register rtx link;
4143           int reloadnum;
4144
4145           /* Since we know we are going to reload this item, don't decrement
4146              for the indirection level.
4147
4148              Note that this is actually conservative:  it would be slightly
4149              more efficient to use the value of SPILL_INDIRECT_LEVELS from
4150              reload1.c here.  */
4151           find_reloads_address (GET_MODE (x), &XEXP (x, 0),
4152                                 XEXP (XEXP (x, 0), 0), &XEXP (XEXP (x, 0), 0),
4153                                 operand, ind_levels);
4154
4155           reloadnum = push_reload (x, NULL_RTX, loc, NULL_PTR,
4156                                    context ? INDEX_REG_CLASS : BASE_REG_CLASS,
4157                                    GET_MODE (x), VOIDmode, 0, 0, operand);
4158           reload_inc[reloadnum]
4159             = find_inc_amount (PATTERN (this_insn), XEXP (x, 0));
4160
4161           link = FIND_REG_INC_NOTE (this_insn, tem);
4162           if (link != 0)
4163             push_replacement (&XEXP (link, 0), reloadnum, VOIDmode);
4164
4165           return 1;
4166         }
4167     }
4168   else if (code == MEM)
4169     {
4170       /* This is probably the result of a substitution, by eliminate_regs,
4171          of an equivalent address for a pseudo that was not allocated to a
4172          hard register.  Verify that the specified address is valid and reload
4173          it into a register.
4174
4175          Since we know we are going to reload this item, don't decrement
4176          for the indirection level.
4177
4178          Note that this is actually conservative:  it would be slightly more
4179          efficient to use the value of SPILL_INDIRECT_LEVELS from
4180          reload1.c here.  */
4181
4182       find_reloads_address (GET_MODE (x), loc, XEXP (x, 0), &XEXP (x, 0),
4183                             operand, ind_levels);
4184
4185       push_reload (*loc, NULL_RTX, loc, NULL_PTR,
4186                    context ? INDEX_REG_CLASS : BASE_REG_CLASS,
4187                    GET_MODE (x), VOIDmode, 0, 0, operand);
4188       return 1;
4189     }
4190   else if (code == REG)
4191     {
4192       register int regno = REGNO (x);
4193
4194       if (reg_equiv_constant[regno] != 0)
4195         {
4196           find_reloads_address_part (reg_equiv_constant[regno], loc,
4197                                      (context ? INDEX_REG_CLASS
4198                                       : BASE_REG_CLASS),
4199                                      GET_MODE (x), operand, ind_levels);
4200           return 1;
4201         }
4202
4203 #if 0 /* This might screw code in reload1.c to delete prior output-reload
4204          that feeds this insn.  */
4205       if (reg_equiv_mem[regno] != 0)
4206         {
4207           push_reload (reg_equiv_mem[regno], NULL_RTX, loc, NULL_PTR,
4208                        context ? INDEX_REG_CLASS : BASE_REG_CLASS,
4209                        GET_MODE (x), VOIDmode, 0, 0, operand);
4210           return 1;
4211         }
4212 #endif
4213       if (reg_equiv_address[regno] != 0)
4214         {
4215           x = make_memloc (x, regno);
4216           find_reloads_address (GET_MODE (x), 0, XEXP (x, 0), &XEXP (x, 0),
4217                                 operand, ind_levels);
4218         }
4219
4220       if (reg_renumber[regno] >= 0)
4221         regno = reg_renumber[regno];
4222       if ((regno >= FIRST_PSEUDO_REGISTER
4223            || !(context ? REGNO_OK_FOR_INDEX_P (regno)
4224                 : REGNO_OK_FOR_BASE_P (regno))))
4225         {
4226           push_reload (x, NULL_RTX, loc, NULL_PTR,
4227                        context ? INDEX_REG_CLASS : BASE_REG_CLASS,
4228                        GET_MODE (x), VOIDmode, 0, 0, operand);
4229           return 1;
4230         }
4231
4232       /* If a register appearing in an address is the subject of a CLOBBER
4233          in this insn, reload it into some other register to be safe.
4234          The CLOBBER is supposed to make the register unavailable
4235          from before this insn to after it.  */
4236       if (regno_clobbered_p (regno, this_insn))
4237         {
4238           push_reload (x, NULL_RTX, loc, NULL_PTR,
4239                        context ? INDEX_REG_CLASS : BASE_REG_CLASS,
4240                        GET_MODE (x), VOIDmode, 0, 0, operand);
4241           return 1;
4242         }
4243     }
4244   else
4245     {
4246       register char *fmt = GET_RTX_FORMAT (code);
4247       register int i;
4248       for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4249         {
4250           if (fmt[i] == 'e')
4251             find_reloads_address_1 (XEXP (x, i), context, &XEXP (x, i),
4252                                     operand, ind_levels);
4253         }
4254     }
4255
4256   return 0;
4257 }
4258 \f
4259 /* X, which is found at *LOC, is a part of an address that needs to be
4260    reloaded into a register of class CLASS.  If X is a constant, or if
4261    X is a PLUS that contains a constant, check that the constant is a
4262    legitimate operand and that we are supposed to be able to load
4263    it into the register.
4264
4265    If not, force the constant into memory and reload the MEM instead.
4266
4267    MODE is the mode to use, in case X is an integer constant.
4268
4269    NEEDED_FOR says which operand this reload is needed for.
4270
4271    IND_LEVELS says how many levels of indirect addressing this machine
4272    supports.  */
4273
4274 static void
4275 find_reloads_address_part (x, loc, class, mode, needed_for, ind_levels)
4276      rtx x;
4277      rtx *loc;
4278      enum reg_class class;
4279      enum machine_mode mode;
4280      rtx needed_for;
4281      int ind_levels;
4282 {
4283   if (CONSTANT_P (x)
4284       && (! LEGITIMATE_CONSTANT_P (x)
4285           || PREFERRED_RELOAD_CLASS (x, class) == NO_REGS))
4286     {
4287       rtx tem = x = force_const_mem (mode, x);
4288       find_reloads_address (mode, &tem, XEXP (tem, 0), &XEXP (tem, 0),
4289                             needed_for, ind_levels);
4290     }
4291
4292   else if (GET_CODE (x) == PLUS
4293            && CONSTANT_P (XEXP (x, 1))
4294            && (! LEGITIMATE_CONSTANT_P (XEXP (x, 1))
4295                || PREFERRED_RELOAD_CLASS (XEXP (x, 1), class) == NO_REGS))
4296     {
4297       rtx tem = force_const_mem (GET_MODE (x), XEXP (x, 1));
4298
4299       x = gen_rtx (PLUS, GET_MODE (x), XEXP (x, 0), tem);
4300       find_reloads_address (mode, &tem, XEXP (tem, 0), &XEXP (tem, 0),
4301                             needed_for, ind_levels);
4302     }
4303
4304   push_reload (x, NULL_RTX, loc, NULL_PTR, class,
4305                mode, VOIDmode, 0, 0, needed_for);
4306 }
4307 \f
4308 /* Substitute into X the registers into which we have reloaded
4309    the things that need reloading.  The array `replacements'
4310    says contains the locations of all pointers that must be changed
4311    and says what to replace them with.
4312
4313    Return the rtx that X translates into; usually X, but modified.  */
4314
4315 void
4316 subst_reloads ()
4317 {
4318   register int i;
4319
4320   for (i = 0; i < n_replacements; i++)
4321     {
4322       register struct replacement *r = &replacements[i];
4323       register rtx reloadreg = reload_reg_rtx[r->what];
4324       if (reloadreg)
4325         {
4326           /* Encapsulate RELOADREG so its machine mode matches what
4327              used to be there.  */
4328           if (GET_MODE (reloadreg) != r->mode && r->mode != VOIDmode)
4329             reloadreg = gen_rtx (REG, r->mode, REGNO (reloadreg));
4330
4331           /* If we are putting this into a SUBREG and RELOADREG is a
4332              SUBREG, we would be making nested SUBREGs, so we have to fix
4333              this up.  Note that r->where == &SUBREG_REG (*r->subreg_loc).  */
4334
4335           if (r->subreg_loc != 0 && GET_CODE (reloadreg) == SUBREG)
4336             {
4337               if (GET_MODE (*r->subreg_loc)
4338                   == GET_MODE (SUBREG_REG (reloadreg)))
4339                 *r->subreg_loc = SUBREG_REG (reloadreg);
4340               else
4341                 {
4342                   *r->where = SUBREG_REG (reloadreg);
4343                   SUBREG_WORD (*r->subreg_loc) += SUBREG_WORD (reloadreg);
4344                 }
4345             }
4346           else
4347             *r->where = reloadreg;
4348         }
4349       /* If reload got no reg and isn't optional, something's wrong.  */
4350       else if (! reload_optional[r->what])
4351         abort ();
4352     }
4353 }
4354 \f
4355 /* Make a copy of any replacements being done into X and move those copies
4356    to locations in Y, a copy of X.  We only look at the highest level of
4357    the RTL.  */
4358
4359 void
4360 copy_replacements (x, y)
4361      rtx x;
4362      rtx y;
4363 {
4364   int i, j;
4365   enum rtx_code code = GET_CODE (x);
4366   char *fmt = GET_RTX_FORMAT (code);
4367   struct replacement *r;
4368
4369   /* We can't support X being a SUBREG because we might then need to know its
4370      location if something inside it was replaced.  */
4371   if (code == SUBREG)
4372     abort ();
4373
4374   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4375     if (fmt[i] == 'e')
4376       for (j = 0; j < n_replacements; j++)
4377         {
4378           if (replacements[j].subreg_loc == &XEXP (x, i))
4379             {
4380               r = &replacements[n_replacements++];
4381               r->where = replacements[j].where;
4382               r->subreg_loc = &XEXP (y, i);
4383               r->what = replacements[j].what;
4384               r->mode = replacements[j].mode;
4385             }
4386           else if (replacements[j].where == &XEXP (x, i))
4387             {
4388               r = &replacements[n_replacements++];
4389               r->where = &XEXP (y, i);
4390               r->subreg_loc = 0;
4391               r->what = replacements[j].what;
4392               r->mode = replacements[j].mode;
4393             }
4394         }
4395 }
4396 \f
4397 /* If LOC was scheduled to be replaced by something, return the replacement.
4398    Otherwise, return *LOC.  */
4399
4400 rtx
4401 find_replacement (loc)
4402      rtx *loc;
4403 {
4404   struct replacement *r;
4405
4406   for (r = &replacements[0]; r < &replacements[n_replacements]; r++)
4407     {
4408       rtx reloadreg = reload_reg_rtx[r->what];
4409
4410       if (reloadreg && r->where == loc)
4411         {
4412           if (r->mode != VOIDmode && GET_MODE (reloadreg) != r->mode)
4413             reloadreg = gen_rtx (REG, r->mode, REGNO (reloadreg));
4414
4415           return reloadreg;
4416         }
4417       else if (reloadreg && r->subreg_loc == loc)
4418         {
4419           /* RELOADREG must be either a REG or a SUBREG.
4420
4421              ??? Is it actually still ever a SUBREG?  If so, why?  */
4422
4423           if (GET_CODE (reloadreg) == REG)
4424             return gen_rtx (REG, GET_MODE (*loc),
4425                             REGNO (reloadreg) + SUBREG_WORD (*loc));
4426           else if (GET_MODE (reloadreg) == GET_MODE (*loc))
4427             return reloadreg;
4428           else
4429             return gen_rtx (SUBREG, GET_MODE (*loc), SUBREG_REG (reloadreg),
4430                             SUBREG_WORD (reloadreg) + SUBREG_WORD (*loc));
4431         }
4432     }
4433
4434   return *loc;
4435 }
4436 \f
4437 /* Return nonzero if register in range [REGNO, ENDREGNO)
4438    appears either explicitly or implicitly in X
4439    other than being stored into.
4440
4441    References contained within the substructure at LOC do not count.
4442    LOC may be zero, meaning don't ignore anything.
4443
4444    This is similar to refers_to_regno_p in rtlanal.c except that we
4445    look at equivalences for pseudos that didn't get hard registers.  */
4446
4447 int
4448 refers_to_regno_for_reload_p (regno, endregno, x, loc)
4449      int regno, endregno;
4450      rtx x;
4451      rtx *loc;
4452 {
4453   register int i;
4454   register RTX_CODE code;
4455   register char *fmt;
4456
4457   if (x == 0)
4458     return 0;
4459
4460  repeat:
4461   code = GET_CODE (x);
4462
4463   switch (code)
4464     {
4465     case REG:
4466       i = REGNO (x);
4467
4468       /* If this is a pseudo, a hard register must not have been allocated.
4469          X must therefore either be a constant or be in memory.  */
4470       if (i >= FIRST_PSEUDO_REGISTER)
4471         {
4472           if (reg_equiv_memory_loc[i])
4473             return refers_to_regno_for_reload_p (regno, endregno,
4474                                                  reg_equiv_memory_loc[i],
4475                                                  NULL_PTR);
4476
4477           if (reg_equiv_constant[i])
4478             return 0;
4479
4480           abort ();
4481         }
4482
4483       return (endregno > i
4484               && regno < i + (i < FIRST_PSEUDO_REGISTER
4485                               ? HARD_REGNO_NREGS (i, GET_MODE (x))
4486                               : 1));
4487
4488     case SUBREG:
4489       /* If this is a SUBREG of a hard reg, we can see exactly which
4490          registers are being modified.  Otherwise, handle normally.  */
4491       if (GET_CODE (SUBREG_REG (x)) == REG
4492           && REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER)
4493         {
4494           int inner_regno = REGNO (SUBREG_REG (x)) + SUBREG_WORD (x);
4495           int inner_endregno
4496             = inner_regno + (inner_regno < FIRST_PSEUDO_REGISTER
4497                              ? HARD_REGNO_NREGS (regno, GET_MODE (x)) : 1);
4498
4499           return endregno > inner_regno && regno < inner_endregno;
4500         }
4501       break;
4502
4503     case CLOBBER:
4504     case SET:
4505       if (&SET_DEST (x) != loc
4506           /* Note setting a SUBREG counts as referring to the REG it is in for
4507              a pseudo but not for hard registers since we can
4508              treat each word individually.  */
4509           && ((GET_CODE (SET_DEST (x)) == SUBREG
4510                && loc != &SUBREG_REG (SET_DEST (x))
4511                && GET_CODE (SUBREG_REG (SET_DEST (x))) == REG
4512                && REGNO (SUBREG_REG (SET_DEST (x))) >= FIRST_PSEUDO_REGISTER
4513                && refers_to_regno_for_reload_p (regno, endregno,
4514                                                 SUBREG_REG (SET_DEST (x)),
4515                                                 loc))
4516               || (GET_CODE (SET_DEST (x)) != REG
4517                   && refers_to_regno_for_reload_p (regno, endregno,
4518                                                    SET_DEST (x), loc))))
4519         return 1;
4520
4521       if (code == CLOBBER || loc == &SET_SRC (x))
4522         return 0;
4523       x = SET_SRC (x);
4524       goto repeat;
4525     }
4526
4527   /* X does not match, so try its subexpressions.  */
4528
4529   fmt = GET_RTX_FORMAT (code);
4530   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4531     {
4532       if (fmt[i] == 'e' && loc != &XEXP (x, i))
4533         {
4534           if (i == 0)
4535             {
4536               x = XEXP (x, 0);
4537               goto repeat;
4538             }
4539           else
4540             if (refers_to_regno_for_reload_p (regno, endregno,
4541                                               XEXP (x, i), loc))
4542               return 1;
4543         }
4544       else if (fmt[i] == 'E')
4545         {
4546           register int j;
4547           for (j = XVECLEN (x, i) - 1; j >=0; j--)
4548             if (loc != &XVECEXP (x, i, j)
4549                 && refers_to_regno_for_reload_p (regno, endregno,
4550                                                  XVECEXP (x, i, j), loc))
4551               return 1;
4552         }
4553     }
4554   return 0;
4555 }
4556
4557 /* Nonzero if modifying X will affect IN.  If X is a register or a SUBREG,
4558    we check if any register number in X conflicts with the relevant register
4559    numbers.  If X is a constant, return 0.  If X is a MEM, return 1 iff IN
4560    contains a MEM (we don't bother checking for memory addresses that can't
4561    conflict because we expect this to be a rare case.
4562
4563    This function is similar to reg_overlap_mention_p in rtlanal.c except
4564    that we look at equivalences for pseudos that didn't get hard registers.  */
4565
4566 int
4567 reg_overlap_mentioned_for_reload_p (x, in)
4568      rtx x, in;
4569 {
4570   int regno, endregno;
4571
4572   if (GET_CODE (x) == SUBREG)
4573     {
4574       regno = REGNO (SUBREG_REG (x));
4575       if (regno < FIRST_PSEUDO_REGISTER)
4576         regno += SUBREG_WORD (x);
4577     }
4578   else if (GET_CODE (x) == REG)
4579     {
4580       regno = REGNO (x);
4581
4582       /* If this is a pseudo, it must not have been assigned a hard register.
4583          Therefore, it must either be in memory or be a constant.  */
4584
4585       if (regno >= FIRST_PSEUDO_REGISTER)
4586         {
4587           if (reg_equiv_memory_loc[regno])
4588             return refers_to_mem_for_reload_p (in);
4589           else if (reg_equiv_constant[regno])
4590             return 0;
4591           abort ();
4592         }
4593     }
4594   else if (CONSTANT_P (x))
4595     return 0;
4596   else if (GET_CODE (x) == MEM)
4597     return refers_to_mem_for_reload_p (in);
4598   else if (GET_CODE (x) == SCRATCH || GET_CODE (x) == PC
4599            || GET_CODE (x) == CC0)
4600     return reg_mentioned_p (x, in);
4601   else
4602     abort ();
4603
4604   endregno = regno + (regno < FIRST_PSEUDO_REGISTER
4605                       ? HARD_REGNO_NREGS (regno, GET_MODE (x)) : 1);
4606
4607   return refers_to_regno_for_reload_p (regno, endregno, in, NULL_PTR);
4608 }
4609
4610 /* Return nonzero if anything in X contains a MEM.  Look also for pseudo
4611    registers.  */
4612
4613 int
4614 refers_to_mem_for_reload_p (x)
4615      rtx x;
4616 {
4617   char *fmt;
4618   int i;
4619
4620   if (GET_CODE (x) == MEM)
4621     return 1;
4622
4623   if (GET_CODE (x) == REG)
4624     return (REGNO (x) >= FIRST_PSEUDO_REGISTER
4625             && reg_equiv_memory_loc[REGNO (x)]);
4626
4627   fmt = GET_RTX_FORMAT (GET_CODE (x));
4628   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
4629     if (fmt[i] == 'e'
4630         && (GET_CODE (XEXP (x, i)) == MEM
4631             || refers_to_mem_for_reload_p (XEXP (x, i))))
4632       return 1;
4633
4634   return 0;
4635 }
4636 \f
4637 #if 0
4638
4639 /* [[This function is currently obsolete, now that volatility
4640    is represented by a special bit `volatil' so VOLATILE is never used;
4641    and UNCHANGING has never been brought into use.]]
4642
4643    Alter X by eliminating all VOLATILE and UNCHANGING expressions.
4644    Each of them is replaced by its operand.
4645    Thus, (PLUS (VOLATILE (MEM (REG 5))) (CONST_INT 4))
4646    becomes (PLUS (MEM (REG 5)) (CONST_INT 4)).
4647
4648    If X is itself a VOLATILE expression,
4649    we return the expression that should replace it
4650    but we do not modify X.  */
4651
4652 static rtx
4653 forget_volatility (x)
4654      register rtx x;
4655 {
4656   enum rtx_code code = GET_CODE (x);
4657   register char *fmt;
4658   register int i;
4659   register rtx value = 0;
4660
4661   switch (code)
4662     {
4663     case LABEL_REF:
4664     case SYMBOL_REF:
4665     case CONST_INT:
4666     case CONST_DOUBLE:
4667     case CONST:
4668     case REG:
4669     case CC0:
4670     case PC:
4671       return x;
4672
4673     case VOLATILE:
4674     case UNCHANGING:
4675       return XEXP (x, 0);
4676     }
4677
4678   fmt = GET_RTX_FORMAT (code);
4679   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4680     {
4681       if (fmt[i] == 'e')
4682         XEXP (x, i) = forget_volatility (XEXP (x, i));
4683       if (fmt[i] == 'E')
4684         {
4685           register int j;
4686           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
4687             XVECEXP (x, i, j) = forget_volatility (XVECEXP (x, i, j));
4688         }
4689     }
4690
4691   return x;
4692 }
4693
4694 #endif
4695 \f
4696 /* Check the insns before INSN to see if there is a suitable register
4697    containing the same value as GOAL.
4698    If OTHER is -1, look for a register in class CLASS.
4699    Otherwise, just see if register number OTHER shares GOAL's value.
4700
4701    Return an rtx for the register found, or zero if none is found.
4702
4703    If RELOAD_REG_P is (short *)1,
4704    we reject any hard reg that appears in reload_reg_rtx
4705    because such a hard reg is also needed coming into this insn.
4706
4707    If RELOAD_REG_P is any other nonzero value,
4708    it is a vector indexed by hard reg number
4709    and we reject any hard reg whose element in the vector is nonnegative
4710    as well as any that appears in reload_reg_rtx.
4711
4712    If GOAL is zero, then GOALREG is a register number; we look
4713    for an equivalent for that register.
4714
4715    MODE is the machine mode of the value we want an equivalence for.
4716    If GOAL is nonzero and not VOIDmode, then it must have mode MODE.
4717
4718    This function is used by jump.c as well as in the reload pass.
4719
4720    If GOAL is the sum of the stack pointer and a constant, we treat it
4721    as if it were a constant except that sp is required to be unchanging.  */
4722
4723 rtx
4724 find_equiv_reg (goal, insn, class, other, reload_reg_p, goalreg, mode)
4725      register rtx goal;
4726      rtx insn;
4727      enum reg_class class;
4728      register int other;
4729      short *reload_reg_p;
4730      int goalreg;
4731      enum machine_mode mode;
4732 {
4733   register rtx p = insn;
4734   rtx valtry, value, where;
4735   register rtx pat;
4736   register int regno = -1;
4737   int valueno;
4738   int goal_mem = 0;
4739   int goal_const = 0;
4740   int goal_mem_addr_varies = 0;
4741   int need_stable_sp = 0;
4742   int nregs;
4743   int valuenregs;
4744
4745   if (goal == 0)
4746     regno = goalreg;
4747   else if (GET_CODE (goal) == REG)
4748     regno = REGNO (goal);
4749   else if (GET_CODE (goal) == MEM)
4750     {
4751       enum rtx_code code = GET_CODE (XEXP (goal, 0));
4752       if (MEM_VOLATILE_P (goal))
4753         return 0;
4754       if (flag_float_store && GET_MODE_CLASS (GET_MODE (goal)) == MODE_FLOAT)
4755         return 0;
4756       /* An address with side effects must be reexecuted.  */
4757       switch (code)
4758         {
4759         case POST_INC:
4760         case PRE_INC:
4761         case POST_DEC:
4762         case PRE_DEC:
4763           return 0;
4764         }
4765       goal_mem = 1;
4766     }
4767   else if (CONSTANT_P (goal))
4768     goal_const = 1;
4769   else if (GET_CODE (goal) == PLUS
4770            && XEXP (goal, 0) == stack_pointer_rtx
4771            && CONSTANT_P (XEXP (goal, 1)))
4772     goal_const = need_stable_sp = 1;
4773   else
4774     return 0;
4775
4776   /* On some machines, certain regs must always be rejected
4777      because they don't behave the way ordinary registers do.  */
4778
4779 #ifdef OVERLAPPING_REGNO_P
4780    if (regno >= 0 && regno < FIRST_PSEUDO_REGISTER
4781        && OVERLAPPING_REGNO_P (regno))
4782      return 0;
4783 #endif
4784
4785   /* Scan insns back from INSN, looking for one that copies
4786      a value into or out of GOAL.
4787      Stop and give up if we reach a label.  */
4788
4789   while (1)
4790     {
4791       p = PREV_INSN (p);
4792       if (p == 0 || GET_CODE (p) == CODE_LABEL)
4793         return 0;
4794       if (GET_CODE (p) == INSN
4795           /* If we don't want spill regs ... */
4796           && (! (reload_reg_p != 0 && reload_reg_p != (short *)1)
4797           /* ... then ignore insns introduced by reload; they aren't useful
4798              and can cause results in reload_as_needed to be different
4799              from what they were when calculating the need for spills.
4800              If we notice an input-reload insn here, we will reject it below,
4801              but it might hide a usable equivalent.  That makes bad code.
4802              It may even abort: perhaps no reg was spilled for this insn
4803              because it was assumed we would find that equivalent.  */
4804               || INSN_UID (p) < reload_first_uid))
4805         {
4806           rtx tem;
4807           pat = single_set (p);
4808           /* First check for something that sets some reg equal to GOAL.  */
4809           if (pat != 0
4810               && ((regno >= 0
4811                    && true_regnum (SET_SRC (pat)) == regno
4812                    && (valueno = true_regnum (valtry = SET_DEST (pat))) >= 0)
4813                   ||
4814                   (regno >= 0
4815                    && true_regnum (SET_DEST (pat)) == regno
4816                    && (valueno = true_regnum (valtry = SET_SRC (pat))) >= 0)
4817                   ||
4818                   (goal_const && rtx_equal_p (SET_SRC (pat), goal)
4819                    && (valueno = true_regnum (valtry = SET_DEST (pat))) >= 0)
4820                   || (goal_mem
4821                       && (valueno = true_regnum (valtry = SET_DEST (pat))) >= 0
4822                       && rtx_renumbered_equal_p (goal, SET_SRC (pat)))
4823                   || (goal_mem
4824                       && (valueno = true_regnum (valtry = SET_SRC (pat))) >= 0
4825                       && rtx_renumbered_equal_p (goal, SET_DEST (pat)))
4826                   /* If we are looking for a constant,
4827                      and something equivalent to that constant was copied
4828                      into a reg, we can use that reg.  */
4829                   || (goal_const && (tem = find_reg_note (p, REG_EQUIV,
4830                                                           NULL_RTX))
4831                       && rtx_equal_p (XEXP (tem, 0), goal)
4832                       && (valueno = true_regnum (valtry = SET_DEST (pat))) >= 0)
4833                   || (goal_const && (tem = find_reg_note (p, REG_EQUIV,
4834                                                           NULL_RTX))
4835                       && GET_CODE (SET_DEST (pat)) == REG
4836                       && GET_CODE (XEXP (tem, 0)) == CONST_DOUBLE
4837                       && GET_MODE_CLASS (GET_MODE (XEXP (tem, 0))) == MODE_FLOAT
4838                       && GET_CODE (goal) == CONST_INT
4839                       && INTVAL (goal) == CONST_DOUBLE_LOW (XEXP (tem, 0))
4840                       && (valtry = operand_subword (SET_DEST (pat), 0, 0,
4841                                                     VOIDmode))
4842                       && (valueno = true_regnum (valtry)) >= 0)
4843                   || (goal_const && (tem = find_reg_note (p, REG_EQUIV,
4844                                                           NULL_RTX))
4845                       && GET_CODE (SET_DEST (pat)) == REG
4846                       && GET_CODE (XEXP (tem, 0)) == CONST_DOUBLE
4847                       && GET_MODE_CLASS (GET_MODE (XEXP (tem, 0))) == MODE_FLOAT
4848                       && GET_CODE (goal) == CONST_INT
4849                       && INTVAL (goal) == CONST_DOUBLE_HIGH (XEXP (tem, 0))
4850                       && (valtry
4851                           = operand_subword (SET_DEST (pat), 1, 0, VOIDmode))
4852                       && (valueno = true_regnum (valtry)) >= 0)))
4853             if (other >= 0
4854                 ? valueno == other
4855                 : ((unsigned) valueno < FIRST_PSEUDO_REGISTER
4856                    && TEST_HARD_REG_BIT (reg_class_contents[(int) class],
4857                                          valueno)))
4858               {
4859                 value = valtry;
4860                 where = p;
4861                 break;
4862               }
4863         }
4864     }
4865
4866   /* We found a previous insn copying GOAL into a suitable other reg VALUE
4867      (or copying VALUE into GOAL, if GOAL is also a register).
4868      Now verify that VALUE is really valid.  */
4869
4870   /* VALUENO is the register number of VALUE; a hard register.  */
4871
4872   /* Don't try to re-use something that is killed in this insn.  We want
4873      to be able to trust REG_UNUSED notes.  */
4874   if (find_reg_note (where, REG_UNUSED, value))
4875     return 0;
4876
4877   /* If we propose to get the value from the stack pointer or if GOAL is
4878      a MEM based on the stack pointer, we need a stable SP.  */
4879   if (valueno == STACK_POINTER_REGNUM
4880       || (goal_mem && reg_overlap_mentioned_for_reload_p (stack_pointer_rtx,
4881                                                           goal)))
4882     need_stable_sp = 1;
4883
4884   /* Reject VALUE if the copy-insn moved the wrong sort of datum.  */
4885   if (GET_MODE (value) != mode)
4886     return 0;
4887
4888   /* Reject VALUE if it was loaded from GOAL
4889      and is also a register that appears in the address of GOAL.  */
4890
4891   if (goal_mem && value == SET_DEST (PATTERN (where))
4892       && refers_to_regno_for_reload_p (valueno,
4893                                        (valueno
4894                                         + HARD_REGNO_NREGS (valueno, mode)),
4895                                        goal, NULL_PTR))
4896     return 0;
4897
4898   /* Reject registers that overlap GOAL.  */
4899
4900   if (!goal_mem && !goal_const
4901       && regno + HARD_REGNO_NREGS (regno, mode) > valueno
4902       && regno < valueno + HARD_REGNO_NREGS (valueno, mode))
4903     return 0;
4904
4905   /* Reject VALUE if it is one of the regs reserved for reloads.
4906      Reload1 knows how to reuse them anyway, and it would get
4907      confused if we allocated one without its knowledge.
4908      (Now that insns introduced by reload are ignored above,
4909      this case shouldn't happen, but I'm not positive.)  */
4910
4911   if (reload_reg_p != 0 && reload_reg_p != (short *)1
4912       && reload_reg_p[valueno] >= 0)
4913     return 0;
4914
4915   /* On some machines, certain regs must always be rejected
4916      because they don't behave the way ordinary registers do.  */
4917
4918 #ifdef OVERLAPPING_REGNO_P
4919   if (OVERLAPPING_REGNO_P (valueno))
4920     return 0;
4921 #endif
4922
4923   nregs = HARD_REGNO_NREGS (regno, mode);
4924   valuenregs = HARD_REGNO_NREGS (valueno, mode);
4925
4926   /* Reject VALUE if it is a register being used for an input reload
4927      even if it is not one of those reserved.  */
4928
4929   if (reload_reg_p != 0)
4930     {
4931       int i;
4932       for (i = 0; i < n_reloads; i++)
4933         if (reload_reg_rtx[i] != 0 && reload_in[i])
4934           {
4935             int regno1 = REGNO (reload_reg_rtx[i]);
4936             int nregs1 = HARD_REGNO_NREGS (regno1,
4937                                            GET_MODE (reload_reg_rtx[i]));
4938             if (regno1 < valueno + valuenregs
4939                 && regno1 + nregs1 > valueno)
4940               return 0;
4941           }
4942     }
4943
4944   if (goal_mem)
4945     goal_mem_addr_varies = rtx_addr_varies_p (goal);
4946
4947   /* Now verify that the values of GOAL and VALUE remain unaltered
4948      until INSN is reached.  */
4949
4950   p = insn;
4951   while (1)
4952     {
4953       p = PREV_INSN (p);
4954       if (p == where)
4955         return value;
4956
4957       /* Don't trust the conversion past a function call
4958          if either of the two is in a call-clobbered register, or memory.  */
4959       if (GET_CODE (p) == CALL_INSN
4960           && ((regno >= 0 && regno < FIRST_PSEUDO_REGISTER
4961                && call_used_regs[regno])
4962               ||
4963               (valueno >= 0 && valueno < FIRST_PSEUDO_REGISTER
4964                && call_used_regs[valueno])
4965               ||
4966               goal_mem
4967               || need_stable_sp))
4968         return 0;
4969
4970 #ifdef INSN_CLOBBERS_REGNO_P
4971       if ((valueno >= 0 && valueno < FIRST_PSEUDO_REGISTER
4972           && INSN_CLOBBERS_REGNO_P (p, valueno))
4973           || (regno >= 0 && regno < FIRST_PSEUDO_REGISTER
4974           && INSN_CLOBBERS_REGNO_P (p, regno)))
4975         return 0;
4976 #endif
4977
4978       if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
4979         {
4980           /* If this insn P stores in either GOAL or VALUE, return 0.
4981              If GOAL is a memory ref and this insn writes memory, return 0.
4982              If GOAL is a memory ref and its address is not constant,
4983              and this insn P changes a register used in GOAL, return 0.  */
4984
4985           pat = PATTERN (p);
4986           if (GET_CODE (pat) == SET || GET_CODE (pat) == CLOBBER)
4987             {
4988               register rtx dest = SET_DEST (pat);
4989               while (GET_CODE (dest) == SUBREG
4990                      || GET_CODE (dest) == ZERO_EXTRACT
4991                      || GET_CODE (dest) == SIGN_EXTRACT
4992                      || GET_CODE (dest) == STRICT_LOW_PART)
4993                 dest = XEXP (dest, 0);
4994               if (GET_CODE (dest) == REG)
4995                 {
4996                   register int xregno = REGNO (dest);
4997                   int xnregs;
4998                   if (REGNO (dest) < FIRST_PSEUDO_REGISTER)
4999                     xnregs = HARD_REGNO_NREGS (xregno, GET_MODE (dest));
5000                   else
5001                     xnregs = 1;
5002                   if (xregno < regno + nregs && xregno + xnregs > regno)
5003                     return 0;
5004                   if (xregno < valueno + valuenregs
5005                       && xregno + xnregs > valueno)
5006                     return 0;
5007                   if (goal_mem_addr_varies
5008                       && reg_overlap_mentioned_for_reload_p (dest, goal))
5009                     return 0;
5010                 }
5011               else if (goal_mem && GET_CODE (dest) == MEM
5012                        && ! push_operand (dest, GET_MODE (dest)))
5013                 return 0;
5014               else if (need_stable_sp && push_operand (dest, GET_MODE (dest)))
5015                 return 0;
5016             }
5017           else if (GET_CODE (pat) == PARALLEL)
5018             {
5019               register int i;
5020               for (i = XVECLEN (pat, 0) - 1; i >= 0; i--)
5021                 {
5022                   register rtx v1 = XVECEXP (pat, 0, i);
5023                   if (GET_CODE (v1) == SET || GET_CODE (v1) == CLOBBER)
5024                     {
5025                       register rtx dest = SET_DEST (v1);
5026                       while (GET_CODE (dest) == SUBREG
5027                              || GET_CODE (dest) == ZERO_EXTRACT
5028                              || GET_CODE (dest) == SIGN_EXTRACT
5029                              || GET_CODE (dest) == STRICT_LOW_PART)
5030                         dest = XEXP (dest, 0);
5031                       if (GET_CODE (dest) == REG)
5032                         {
5033                           register int xregno = REGNO (dest);
5034                           int xnregs;
5035                           if (REGNO (dest) < FIRST_PSEUDO_REGISTER)
5036                             xnregs = HARD_REGNO_NREGS (xregno, GET_MODE (dest));
5037                           else
5038                             xnregs = 1;
5039                           if (xregno < regno + nregs
5040                               && xregno + xnregs > regno)
5041                             return 0;
5042                           if (xregno < valueno + valuenregs
5043                               && xregno + xnregs > valueno)
5044                             return 0;
5045                           if (goal_mem_addr_varies
5046                               && reg_overlap_mentioned_for_reload_p (dest,
5047                                                                      goal))
5048                             return 0;
5049                         }
5050                       else if (goal_mem && GET_CODE (dest) == MEM
5051                                && ! push_operand (dest, GET_MODE (dest)))
5052                         return 0;
5053                       else if (need_stable_sp
5054                                && push_operand (dest, GET_MODE (dest)))
5055                         return 0;
5056                     }
5057                 }
5058             }
5059
5060 #ifdef AUTO_INC_DEC
5061           /* If this insn auto-increments or auto-decrements
5062              either regno or valueno, return 0 now.
5063              If GOAL is a memory ref and its address is not constant,
5064              and this insn P increments a register used in GOAL, return 0.  */
5065           {
5066             register rtx link;
5067
5068             for (link = REG_NOTES (p); link; link = XEXP (link, 1))
5069               if (REG_NOTE_KIND (link) == REG_INC
5070                   && GET_CODE (XEXP (link, 0)) == REG)
5071                 {
5072                   register int incno = REGNO (XEXP (link, 0));
5073                   if (incno < regno + nregs && incno >= regno)
5074                     return 0;
5075                   if (incno < valueno + valuenregs && incno >= valueno)
5076                     return 0;
5077                   if (goal_mem_addr_varies
5078                       && reg_overlap_mentioned_for_reload_p (XEXP (link, 0),
5079                                                              goal))
5080                     return 0;
5081                 }
5082           }
5083 #endif
5084         }
5085     }
5086 }
5087 \f
5088 /* Find a place where INCED appears in an increment or decrement operator
5089    within X, and return the amount INCED is incremented or decremented by.
5090    The value is always positive.  */
5091
5092 static int
5093 find_inc_amount (x, inced)
5094      rtx x, inced;
5095 {
5096   register enum rtx_code code = GET_CODE (x);
5097   register char *fmt;
5098   register int i;
5099
5100   if (code == MEM)
5101     {
5102       register rtx addr = XEXP (x, 0);
5103       if ((GET_CODE (addr) == PRE_DEC
5104            || GET_CODE (addr) == POST_DEC
5105            || GET_CODE (addr) == PRE_INC
5106            || GET_CODE (addr) == POST_INC)
5107           && XEXP (addr, 0) == inced)
5108         return GET_MODE_SIZE (GET_MODE (x));
5109     }
5110
5111   fmt = GET_RTX_FORMAT (code);
5112   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
5113     {
5114       if (fmt[i] == 'e')
5115         {
5116           register int tem = find_inc_amount (XEXP (x, i), inced);
5117           if (tem != 0)
5118             return tem;
5119         }
5120       if (fmt[i] == 'E')
5121         {
5122           register int j;
5123           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
5124             {
5125               register int tem = find_inc_amount (XVECEXP (x, i, j), inced);
5126               if (tem != 0)
5127                 return tem;
5128             }
5129         }
5130     }
5131
5132   return 0;
5133 }
5134 \f
5135 /* Return 1 if register REGNO is the subject of a clobber in insn INSN.  */
5136
5137 int
5138 regno_clobbered_p (regno, insn)
5139      int regno;
5140      rtx insn;
5141 {
5142   if (GET_CODE (PATTERN (insn)) == CLOBBER
5143       && GET_CODE (XEXP (PATTERN (insn), 0)) == REG)
5144     return REGNO (XEXP (PATTERN (insn), 0)) == regno;
5145
5146   if (GET_CODE (PATTERN (insn)) == PARALLEL)
5147     {
5148       int i = XVECLEN (PATTERN (insn), 0) - 1;
5149
5150       for (; i >= 0; i--)
5151         {
5152           rtx elt = XVECEXP (PATTERN (insn), 0, i);
5153           if (GET_CODE (elt) == CLOBBER && GET_CODE (XEXP (elt, 0)) == REG
5154               && REGNO (XEXP (elt, 0)) == regno)
5155             return 1;
5156         }
5157     }
5158
5159   return 0;
5160 }