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_needed_for_multiple[i]
1239         && reload_inmode[i] == reload_outmode[output_reload]
1240         && reload_inc[i] == 0
1241         && reload_reg_rtx[i] == 0
1242         && reload_strict_low[i] == 0
1243         /* Don't combine two reloads with different secondary reloads. */
1244         && (reload_secondary_reload[i] == reload_secondary_reload[output_reload]
1245             || reload_secondary_reload[i] == -1
1246             || reload_secondary_reload[output_reload] == -1)
1247         && (reg_class_subset_p (reload_reg_class[i],
1248                                 reload_reg_class[output_reload])
1249             || reg_class_subset_p (reload_reg_class[output_reload],
1250                                    reload_reg_class[i]))
1251         && (MATCHES (reload_in[i], reload_out[output_reload])
1252             /* Args reversed because the first arg seems to be
1253                the one that we imagine being modified
1254                while the second is the one that might be affected.  */
1255             || (! reg_overlap_mentioned_for_reload_p (reload_out[output_reload],
1256                                                       reload_in[i])
1257                 /* However, if the input is a register that appears inside
1258                    the output, then we also can't share.
1259                    Imagine (set (mem (reg 69)) (plus (reg 69) ...)).
1260                    If the same reload reg is used for both reg 69 and the
1261                    result to be stored in memory, then that result
1262                    will clobber the address of the memory ref.  */
1263                 && ! (GET_CODE (reload_in[i]) == REG
1264                       && reg_overlap_mentioned_for_reload_p (reload_in[i],
1265                                                              reload_out[output_reload])))))
1266       {
1267         int j;
1268
1269         /* We have found a reload to combine with!  */
1270         reload_out[i] = reload_out[output_reload];
1271         reload_outmode[i] = reload_outmode[output_reload];
1272         /* Mark the old output reload as inoperative.  */
1273         reload_out[output_reload] = 0;
1274         /* The combined reload is needed for the entire insn.  */
1275         reload_needed_for_multiple[i] = 1;
1276         reload_when_needed[i] = RELOAD_OTHER;
1277         /* If the output reload had a secondary reload, copy it. */
1278         if (reload_secondary_reload[output_reload] != -1)
1279           reload_secondary_reload[i] = reload_secondary_reload[output_reload];
1280         /* If required, minimize the register class. */
1281         if (reg_class_subset_p (reload_reg_class[output_reload],
1282                                 reload_reg_class[i]))
1283           reload_reg_class[i] = reload_reg_class[output_reload];
1284
1285         /* Transfer all replacements from the old reload to the combined.  */
1286         for (j = 0; j < n_replacements; j++)
1287           if (replacements[j].what == output_reload)
1288             replacements[j].what = i;
1289
1290         return;
1291       }
1292
1293   /* If this insn has only one operand that is modified or written (assumed
1294      to be the first),  it must be the one corresponding to this reload.  It
1295      is safe to use anything that dies in this insn for that output provided
1296      that it does not occur in the output (we already know it isn't an
1297      earlyclobber.  If this is an asm insn, give up.  */
1298
1299   if (INSN_CODE (this_insn) == -1)
1300     return;
1301
1302   for (i = 1; i < insn_n_operands[INSN_CODE (this_insn)]; i++)
1303     if (insn_operand_constraint[INSN_CODE (this_insn)][i][0] == '='
1304         || insn_operand_constraint[INSN_CODE (this_insn)][i][0] == '+')
1305       return;
1306
1307   /* See if some hard register that dies in this insn and is not used in
1308      the output is the right class.  Only works if the register we pick
1309      up can fully hold our output reload.  */
1310   for (note = REG_NOTES (this_insn); note; note = XEXP (note, 1))
1311     if (REG_NOTE_KIND (note) == REG_DEAD
1312         && GET_CODE (XEXP (note, 0)) == REG
1313         && ! reg_overlap_mentioned_for_reload_p (XEXP (note, 0),
1314                                                  reload_out[output_reload])
1315         && REGNO (XEXP (note, 0)) < FIRST_PSEUDO_REGISTER
1316         && HARD_REGNO_MODE_OK (REGNO (XEXP (note, 0)), reload_outmode[output_reload])
1317         && TEST_HARD_REG_BIT (reg_class_contents[(int) reload_reg_class[output_reload]],
1318                               REGNO (XEXP (note, 0)))
1319         && (HARD_REGNO_NREGS (REGNO (XEXP (note, 0)), reload_outmode[output_reload])
1320             <= HARD_REGNO_NREGS (REGNO (XEXP (note, 0)), GET_MODE (XEXP (note, 0))))
1321         && ! fixed_regs[REGNO (XEXP (note, 0))])
1322       {
1323         reload_reg_rtx[output_reload] = gen_rtx (REG,
1324                                                  reload_outmode[output_reload],
1325                                                  REGNO (XEXP (note, 0)));
1326         return;
1327       }
1328 }
1329 \f
1330 /* Try to find a reload register for an in-out reload (expressions IN and OUT).
1331    See if one of IN and OUT is a register that may be used;
1332    this is desirable since a spill-register won't be needed.
1333    If so, return the register rtx that proves acceptable.
1334
1335    INLOC and OUTLOC are locations where IN and OUT appear in the insn.
1336    CLASS is the register class required for the reload.
1337
1338    If FOR_REAL is >= 0, it is the number of the reload,
1339    and in some cases when it can be discovered that OUT doesn't need
1340    to be computed, clear out reload_out[FOR_REAL].
1341
1342    If FOR_REAL is -1, this should not be done, because this call
1343    is just to see if a register can be found, not to find and install it.  */
1344
1345 static rtx
1346 find_dummy_reload (real_in, real_out, inloc, outloc, class, for_real)
1347      rtx real_in, real_out;
1348      rtx *inloc, *outloc;
1349      enum reg_class class;
1350      int for_real;
1351 {
1352   rtx in = real_in;
1353   rtx out = real_out;
1354   int in_offset = 0;
1355   int out_offset = 0;
1356   rtx value = 0;
1357
1358   /* If operands exceed a word, we can't use either of them
1359      unless they have the same size.  */
1360   if (GET_MODE_SIZE (GET_MODE (real_out)) != GET_MODE_SIZE (GET_MODE (real_in))
1361       && (GET_MODE_SIZE (GET_MODE (real_out)) > UNITS_PER_WORD
1362           || GET_MODE_SIZE (GET_MODE (real_in)) > UNITS_PER_WORD))
1363     return 0;
1364
1365   /* Find the inside of any subregs.  */
1366   while (GET_CODE (out) == SUBREG)
1367     {
1368       out_offset = SUBREG_WORD (out);
1369       out = SUBREG_REG (out);
1370     }
1371   while (GET_CODE (in) == SUBREG)
1372     {
1373       in_offset = SUBREG_WORD (in);
1374       in = SUBREG_REG (in);
1375     }
1376
1377   /* Narrow down the reg class, the same way push_reload will;
1378      otherwise we might find a dummy now, but push_reload won't.  */
1379   class = PREFERRED_RELOAD_CLASS (in, class);
1380
1381   /* See if OUT will do.  */
1382   if (GET_CODE (out) == REG
1383       && REGNO (out) < FIRST_PSEUDO_REGISTER)
1384     {
1385       register int regno = REGNO (out) + out_offset;
1386       int nwords = HARD_REGNO_NREGS (regno, GET_MODE (real_out));
1387       rtx saved_rtx;
1388
1389       /* When we consider whether the insn uses OUT,
1390          ignore references within IN.  They don't prevent us
1391          from copying IN into OUT, because those refs would
1392          move into the insn that reloads IN.
1393
1394          However, we only ignore IN in its role as this reload.
1395          If the insn uses IN elsewhere and it contains OUT,
1396          that counts.  We can't be sure it's the "same" operand
1397          so it might not go through this reload.  */
1398       saved_rtx = *inloc;
1399       *inloc = const0_rtx;
1400
1401       if (regno < FIRST_PSEUDO_REGISTER
1402           /* A fixed reg that can overlap other regs better not be used
1403              for reloading in any way.  */
1404 #ifdef OVERLAPPING_REGNO_P
1405           && ! (fixed_regs[regno] && OVERLAPPING_REGNO_P (regno))
1406 #endif
1407           && ! refers_to_regno_for_reload_p (regno, regno + nwords,
1408                                              PATTERN (this_insn), outloc))
1409         {
1410           int i;
1411           for (i = 0; i < nwords; i++)
1412             if (! TEST_HARD_REG_BIT (reg_class_contents[(int) class],
1413                                      regno + i))
1414               break;
1415
1416           if (i == nwords)
1417             {
1418               if (GET_CODE (real_out) == REG)
1419                 value = real_out;
1420               else
1421                 value = gen_rtx (REG, GET_MODE (real_out), regno);
1422             }
1423         }
1424
1425       *inloc = saved_rtx;
1426     }
1427
1428   /* Consider using IN if OUT was not acceptable
1429      or if OUT dies in this insn (like the quotient in a divmod insn).
1430      We can't use IN unless it is dies in this insn,
1431      which means we must know accurately which hard regs are live.
1432      Also, the result can't go in IN if IN is used within OUT.  */
1433   if (hard_regs_live_known
1434       && GET_CODE (in) == REG
1435       && REGNO (in) < FIRST_PSEUDO_REGISTER
1436       && (value == 0
1437           || find_reg_note (this_insn, REG_UNUSED, real_out))
1438       && find_reg_note (this_insn, REG_DEAD, real_in)
1439       && !fixed_regs[REGNO (in)]
1440       && HARD_REGNO_MODE_OK (REGNO (in), GET_MODE (out)))
1441     {
1442       register int regno = REGNO (in) + in_offset;
1443       int nwords = HARD_REGNO_NREGS (regno, GET_MODE (real_in));
1444
1445       if (! refers_to_regno_for_reload_p (regno, regno + nwords, out, NULL_PTR)
1446           && ! hard_reg_set_here_p (regno, regno + nwords,
1447                                     PATTERN (this_insn)))
1448         {
1449           int i;
1450           for (i = 0; i < nwords; i++)
1451             if (! TEST_HARD_REG_BIT (reg_class_contents[(int) class],
1452                                      regno + i))
1453               break;
1454
1455           if (i == nwords)
1456             {
1457               /* If we were going to use OUT as the reload reg
1458                  and changed our mind, it means OUT is a dummy that
1459                  dies here.  So don't bother copying value to it.  */
1460               if (for_real >= 0 && value == real_out)
1461                 reload_out[for_real] = 0;
1462               if (GET_CODE (real_in) == REG)
1463                 value = real_in;
1464               else
1465                 value = gen_rtx (REG, GET_MODE (real_in), regno);
1466             }
1467         }
1468     }
1469
1470   return value;
1471 }
1472 \f
1473 /* This page contains subroutines used mainly for determining
1474    whether the IN or an OUT of a reload can serve as the
1475    reload register.  */
1476
1477 /* Return 1 if expression X alters a hard reg in the range
1478    from BEG_REGNO (inclusive) to END_REGNO (exclusive),
1479    either explicitly or in the guise of a pseudo-reg allocated to REGNO.
1480    X should be the body of an instruction.  */
1481
1482 static int
1483 hard_reg_set_here_p (beg_regno, end_regno, x)
1484      register int beg_regno, end_regno;
1485      rtx x;
1486 {
1487   if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
1488     {
1489       register rtx op0 = SET_DEST (x);
1490       while (GET_CODE (op0) == SUBREG)
1491         op0 = SUBREG_REG (op0);
1492       if (GET_CODE (op0) == REG)
1493         {
1494           register int r = REGNO (op0);
1495           /* See if this reg overlaps range under consideration.  */
1496           if (r < end_regno
1497               && r + HARD_REGNO_NREGS (r, GET_MODE (op0)) > beg_regno)
1498             return 1;
1499         }
1500     }
1501   else if (GET_CODE (x) == PARALLEL)
1502     {
1503       register int i = XVECLEN (x, 0) - 1;
1504       for (; i >= 0; i--)
1505         if (hard_reg_set_here_p (beg_regno, end_regno, XVECEXP (x, 0, i)))
1506           return 1;
1507     }
1508
1509   return 0;
1510 }
1511
1512 /* Return 1 if ADDR is a valid memory address for mode MODE,
1513    and check that each pseudo reg has the proper kind of
1514    hard reg.  */
1515
1516 int
1517 strict_memory_address_p (mode, addr)
1518      enum machine_mode mode;
1519      register rtx addr;
1520 {
1521   GO_IF_LEGITIMATE_ADDRESS (mode, addr, win);
1522   return 0;
1523
1524  win:
1525   return 1;
1526 }
1527
1528 \f
1529 /* Like rtx_equal_p except that it allows a REG and a SUBREG to match
1530    if they are the same hard reg, and has special hacks for
1531    autoincrement and autodecrement.
1532    This is specifically intended for find_reloads to use
1533    in determining whether two operands match.
1534    X is the operand whose number is the lower of the two.
1535
1536    The value is 2 if Y contains a pre-increment that matches
1537    a non-incrementing address in X.  */
1538
1539 /* ??? To be completely correct, we should arrange to pass
1540    for X the output operand and for Y the input operand.
1541    For now, we assume that the output operand has the lower number
1542    because that is natural in (SET output (... input ...)).  */
1543
1544 int
1545 operands_match_p (x, y)
1546      register rtx x, y;
1547 {
1548   register int i;
1549   register RTX_CODE code = GET_CODE (x);
1550   register char *fmt;
1551   int success_2;
1552
1553   if (x == y)
1554     return 1;
1555   if ((code == REG || (code == SUBREG && GET_CODE (SUBREG_REG (x)) == REG))
1556       && (GET_CODE (y) == REG || (GET_CODE (y) == SUBREG
1557                                   && GET_CODE (SUBREG_REG (y)) == REG)))
1558     {
1559       register int j;
1560
1561       if (code == SUBREG)
1562         {
1563           i = REGNO (SUBREG_REG (x));
1564           if (i >= FIRST_PSEUDO_REGISTER)
1565             goto slow;
1566           i += SUBREG_WORD (x);
1567         }
1568       else
1569         i = REGNO (x);
1570
1571       if (GET_CODE (y) == SUBREG)
1572         {
1573           j = REGNO (SUBREG_REG (y));
1574           if (j >= FIRST_PSEUDO_REGISTER)
1575             goto slow;
1576           j += SUBREG_WORD (y);
1577         }
1578       else
1579         j = REGNO (y);
1580
1581       return i == j;
1582     }
1583   /* If two operands must match, because they are really a single
1584      operand of an assembler insn, then two postincrements are invalid
1585      because the assembler insn would increment only once.
1586      On the other hand, an postincrement matches ordinary indexing
1587      if the postincrement is the output operand.  */
1588   if (code == POST_DEC || code == POST_INC)
1589     return operands_match_p (XEXP (x, 0), y);
1590   /* Two preincrements are invalid
1591      because the assembler insn would increment only once.
1592      On the other hand, an preincrement matches ordinary indexing
1593      if the preincrement is the input operand.
1594      In this case, return 2, since some callers need to do special
1595      things when this happens.  */
1596   if (GET_CODE (y) == PRE_DEC || GET_CODE (y) == PRE_INC)
1597     return operands_match_p (x, XEXP (y, 0)) ? 2 : 0;
1598
1599  slow:
1600
1601   /* Now we have disposed of all the cases
1602      in which different rtx codes can match.  */
1603   if (code != GET_CODE (y))
1604     return 0;
1605   if (code == LABEL_REF)
1606     return XEXP (x, 0) == XEXP (y, 0);
1607   if (code == SYMBOL_REF)
1608     return XSTR (x, 0) == XSTR (y, 0);
1609
1610   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.  */
1611
1612   if (GET_MODE (x) != GET_MODE (y))
1613     return 0;
1614
1615   /* Compare the elements.  If any pair of corresponding elements
1616      fail to match, return 0 for the whole things.  */
1617
1618   success_2 = 0;
1619   fmt = GET_RTX_FORMAT (code);
1620   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1621     {
1622       int val;
1623       switch (fmt[i])
1624         {
1625         case 'w':
1626           if (XWINT (x, i) != XWINT (y, i))
1627             return 0;
1628           break;
1629
1630         case 'i':
1631           if (XINT (x, i) != XINT (y, i))
1632             return 0;
1633           break;
1634
1635         case 'e':
1636           val = operands_match_p (XEXP (x, i), XEXP (y, i));
1637           if (val == 0)
1638             return 0;
1639           /* If any subexpression returns 2,
1640              we should return 2 if we are successful.  */
1641           if (val == 2)
1642             success_2 = 1;
1643           break;
1644
1645         case '0':
1646           break;
1647
1648           /* It is believed that rtx's at this level will never
1649              contain anything but integers and other rtx's,
1650              except for within LABEL_REFs and SYMBOL_REFs.  */
1651         default:
1652           abort ();
1653         }
1654     }
1655   return 1 + success_2;
1656 }
1657 \f
1658 /* Return the number of times character C occurs in string S.  */
1659
1660 int
1661 n_occurrences (c, s)
1662      char c;
1663      char *s;
1664 {
1665   int n = 0;
1666   while (*s)
1667     n += (*s++ == c);
1668   return n;
1669 }
1670 \f
1671 struct decomposition
1672 {
1673   int reg_flag;
1674   int safe;
1675   rtx base;
1676   HOST_WIDE_INT start;
1677   HOST_WIDE_INT end;
1678 };
1679
1680 /* Describe the range of registers or memory referenced by X.
1681    If X is a register, set REG_FLAG and put the first register
1682    number into START and the last plus one into END.
1683    If X is a memory reference, put a base address into BASE
1684    and a range of integer offsets into START and END.
1685    If X is pushing on the stack, we can assume it causes no trouble,
1686    so we set the SAFE field.  */
1687
1688 static struct decomposition
1689 decompose (x)
1690      rtx x;
1691 {
1692   struct decomposition val;
1693   int all_const = 0;
1694
1695   val.reg_flag = 0;
1696   val.safe = 0;
1697   if (GET_CODE (x) == MEM)
1698     {
1699       rtx base, offset = 0;
1700       rtx addr = XEXP (x, 0);
1701
1702       if (GET_CODE (addr) == PRE_DEC || GET_CODE (addr) == PRE_INC
1703           || GET_CODE (addr) == POST_DEC || GET_CODE (addr) == POST_INC)
1704         {
1705           val.base = XEXP (addr, 0);
1706           val.start = - GET_MODE_SIZE (GET_MODE (x));
1707           val.end = GET_MODE_SIZE (GET_MODE (x));
1708           val.safe = REGNO (val.base) == STACK_POINTER_REGNUM;
1709           return val;
1710         }
1711
1712       if (GET_CODE (addr) == CONST)
1713         {
1714           addr = XEXP (addr, 0);
1715           all_const = 1;
1716         }
1717       if (GET_CODE (addr) == PLUS)
1718         {
1719           if (CONSTANT_P (XEXP (addr, 0)))
1720             {
1721               base = XEXP (addr, 1);
1722               offset = XEXP (addr, 0);
1723             }
1724           else if (CONSTANT_P (XEXP (addr, 1)))
1725             {
1726               base = XEXP (addr, 0);
1727               offset = XEXP (addr, 1);
1728             }
1729         }
1730
1731       if (offset == 0)
1732         {
1733           base = addr;
1734           offset = const0_rtx;
1735         }
1736       if (GET_CODE (offset) == CONST)
1737         offset = XEXP (offset, 0);
1738       if (GET_CODE (offset) == PLUS)
1739         {
1740           if (GET_CODE (XEXP (offset, 0)) == CONST_INT)
1741             {
1742               base = gen_rtx (PLUS, GET_MODE (base), base, XEXP (offset, 1));
1743               offset = XEXP (offset, 0);
1744             }
1745           else if (GET_CODE (XEXP (offset, 1)) == CONST_INT)
1746             {
1747               base = gen_rtx (PLUS, GET_MODE (base), base, XEXP (offset, 0));
1748               offset = XEXP (offset, 1);
1749             }
1750           else
1751             {
1752               base = gen_rtx (PLUS, GET_MODE (base), base, offset);
1753               offset = const0_rtx;
1754             }
1755         }
1756       else if (GET_CODE (offset) != CONST_INT)
1757         {
1758           base = gen_rtx (PLUS, GET_MODE (base), base, offset);
1759           offset = const0_rtx;
1760         }
1761
1762       if (all_const && GET_CODE (base) == PLUS)
1763         base = gen_rtx (CONST, GET_MODE (base), base);
1764
1765       if (GET_CODE (offset) != CONST_INT)
1766         abort ();
1767
1768       val.start = INTVAL (offset);
1769       val.end = val.start + GET_MODE_SIZE (GET_MODE (x));
1770       val.base = base;
1771       return val;
1772     }
1773   else if (GET_CODE (x) == REG)
1774     {
1775       val.reg_flag = 1;
1776       val.start = true_regnum (x);
1777       if (val.start < 0)
1778         {
1779           /* A pseudo with no hard reg.  */
1780           val.start = REGNO (x);
1781           val.end = val.start + 1;
1782         }
1783       else
1784         /* A hard reg.  */
1785         val.end = val.start + HARD_REGNO_NREGS (val.start, GET_MODE (x));
1786     }
1787   else if (GET_CODE (x) == SUBREG)
1788     {
1789       if (GET_CODE (SUBREG_REG (x)) != REG)
1790         /* This could be more precise, but it's good enough.  */
1791         return decompose (SUBREG_REG (x));
1792       val.reg_flag = 1;
1793       val.start = true_regnum (x);
1794       if (val.start < 0)
1795         return decompose (SUBREG_REG (x));
1796       else
1797         /* A hard reg.  */
1798         val.end = val.start + HARD_REGNO_NREGS (val.start, GET_MODE (x));
1799     }
1800   else if (CONSTANT_P (x)
1801            /* This hasn't been assigned yet, so it can't conflict yet.  */
1802            || GET_CODE (x) == SCRATCH)
1803     val.safe = 1;
1804   else
1805     abort ();
1806   return val;
1807 }
1808
1809 /* Return 1 if altering Y will not modify the value of X.
1810    Y is also described by YDATA, which should be decompose (Y).  */
1811
1812 static int
1813 immune_p (x, y, ydata)
1814      rtx x, y;
1815      struct decomposition ydata;
1816 {
1817   struct decomposition xdata;
1818
1819   if (ydata.reg_flag)
1820     return !refers_to_regno_for_reload_p (ydata.start, ydata.end, x, NULL_PTR);
1821   if (ydata.safe)
1822     return 1;
1823
1824   if (GET_CODE (y) != MEM)
1825     abort ();
1826   /* If Y is memory and X is not, Y can't affect X.  */
1827   if (GET_CODE (x) != MEM)
1828     return 1;
1829
1830   xdata =  decompose (x);
1831
1832   if (! rtx_equal_p (xdata.base, ydata.base))
1833     {
1834       /* If bases are distinct symbolic constants, there is no overlap.  */
1835       if (CONSTANT_P (xdata.base) && CONSTANT_P (ydata.base))
1836         return 1;
1837       /* Constants and stack slots never overlap.  */
1838       if (CONSTANT_P (xdata.base)
1839           && (ydata.base == frame_pointer_rtx
1840               || ydata.base == stack_pointer_rtx))
1841         return 1;
1842       if (CONSTANT_P (ydata.base)
1843           && (xdata.base == frame_pointer_rtx
1844               || xdata.base == stack_pointer_rtx))
1845         return 1;
1846       /* If either base is variable, we don't know anything.  */
1847       return 0;
1848     }
1849
1850
1851   return (xdata.start >= ydata.end || ydata.start >= xdata.end);
1852 }
1853
1854 /* Similar, but calls decompose.  */
1855
1856 int
1857 safe_from_earlyclobber (op, clobber)
1858      rtx op, clobber;
1859 {
1860   struct decomposition early_data;
1861
1862   early_data = decompose (clobber);
1863   return immune_p (op, clobber, early_data);
1864 }
1865 \f
1866 /* Main entry point of this file: search the body of INSN
1867    for values that need reloading and record them with push_reload.
1868    REPLACE nonzero means record also where the values occur
1869    so that subst_reloads can be used.
1870
1871    IND_LEVELS says how many levels of indirection are supported by this
1872    machine; a value of zero means that a memory reference is not a valid
1873    memory address.
1874
1875    LIVE_KNOWN says we have valid information about which hard
1876    regs are live at each point in the program; this is true when
1877    we are called from global_alloc but false when stupid register
1878    allocation has been done.
1879
1880    RELOAD_REG_P if nonzero is a vector indexed by hard reg number
1881    which is nonnegative if the reg has been commandeered for reloading into.
1882    It is copied into STATIC_RELOAD_REG_P and referenced from there
1883    by various subroutines.  */
1884
1885 void
1886 find_reloads (insn, replace, ind_levels, live_known, reload_reg_p)
1887      rtx insn;
1888      int replace, ind_levels;
1889      int live_known;
1890      short *reload_reg_p;
1891 {
1892   rtx non_reloaded_operands[MAX_RECOG_OPERANDS];
1893   int n_non_reloaded_operands = 0;
1894 #ifdef REGISTER_CONSTRAINTS
1895
1896   enum reload_modified { RELOAD_NOTHING, RELOAD_READ, RELOAD_READ_WRITE, RELOAD_WRITE };
1897
1898   register int insn_code_number;
1899   register int i;
1900   int noperands;
1901   /* These are the constraints for the insn.  We don't change them.  */
1902   char *constraints1[MAX_RECOG_OPERANDS];
1903   /* These start out as the constraints for the insn
1904      and they are chewed up as we consider alternatives.  */
1905   char *constraints[MAX_RECOG_OPERANDS];
1906   /* These are the preferred classes for an operand, or NO_REGS if it isn't
1907      a register.  */
1908   enum reg_class preferred_class[MAX_RECOG_OPERANDS];
1909   char pref_or_nothing[MAX_RECOG_OPERANDS];
1910   /* Nonzero for a MEM operand whose entire address needs a reload.  */
1911   int address_reloaded[MAX_RECOG_OPERANDS];
1912   int no_input_reloads = 0, no_output_reloads = 0;
1913   int n_alternatives;
1914   int this_alternative[MAX_RECOG_OPERANDS];
1915   char this_alternative_win[MAX_RECOG_OPERANDS];
1916   char this_alternative_offmemok[MAX_RECOG_OPERANDS];
1917   char this_alternative_earlyclobber[MAX_RECOG_OPERANDS];
1918   int this_alternative_matches[MAX_RECOG_OPERANDS];
1919   int swapped;
1920   int goal_alternative[MAX_RECOG_OPERANDS];
1921   int this_alternative_number;
1922   int goal_alternative_number;
1923   int operand_reloadnum[MAX_RECOG_OPERANDS];
1924   int goal_alternative_matches[MAX_RECOG_OPERANDS];
1925   int goal_alternative_matched[MAX_RECOG_OPERANDS];
1926   char goal_alternative_win[MAX_RECOG_OPERANDS];
1927   char goal_alternative_offmemok[MAX_RECOG_OPERANDS];
1928   char goal_alternative_earlyclobber[MAX_RECOG_OPERANDS];
1929   int goal_alternative_swapped;
1930   enum reload_modified modified[MAX_RECOG_OPERANDS];
1931   int best;
1932   int commutative;
1933   char operands_match[MAX_RECOG_OPERANDS][MAX_RECOG_OPERANDS];
1934   rtx substed_operand[MAX_RECOG_OPERANDS];
1935   rtx body = PATTERN (insn);
1936   rtx set = single_set (insn);
1937   int goal_earlyclobber, this_earlyclobber;
1938   enum machine_mode operand_mode[MAX_RECOG_OPERANDS];
1939
1940   this_insn = insn;
1941   this_insn_is_asm = 0;         /* Tentative.  */
1942   n_reloads = 0;
1943   n_replacements = 0;
1944   n_memlocs = 0;
1945   n_earlyclobbers = 0;
1946   replace_reloads = replace;
1947   hard_regs_live_known = live_known;
1948   static_reload_reg_p = reload_reg_p;
1949
1950   /* JUMP_INSNs and CALL_INSNs are not allowed to have any output reloads;
1951      neither are insns that SET cc0.  Insns that use CC0 are not allowed
1952      to have any input reloads.  */
1953   if (GET_CODE (insn) == JUMP_INSN || GET_CODE (insn) == CALL_INSN)
1954     no_output_reloads = 1;
1955
1956 #ifdef HAVE_cc0
1957   if (reg_referenced_p (cc0_rtx, PATTERN (insn)))
1958     no_input_reloads = 1;
1959   if (reg_set_p (cc0_rtx, PATTERN (insn)))
1960     no_output_reloads = 1;
1961 #endif
1962
1963 #ifdef SECONDARY_MEMORY_NEEDED
1964   /* The eliminated forms of any secondary memory locations are per-insn, so
1965      clear them out here.  */
1966
1967   bzero (secondary_memlocs_elim, sizeof secondary_memlocs_elim);
1968 #endif
1969
1970   /* Find what kind of insn this is.  NOPERANDS gets number of operands.
1971      Make OPERANDS point to a vector of operand values.
1972      Make OPERAND_LOCS point to a vector of pointers to
1973      where the operands were found.
1974      Fill CONSTRAINTS and CONSTRAINTS1 with pointers to the
1975      constraint-strings for this insn.
1976      Return if the insn needs no reload processing.  */
1977
1978   switch (GET_CODE (body))
1979     {
1980     case USE:
1981     case CLOBBER:
1982     case ASM_INPUT:
1983     case ADDR_VEC:
1984     case ADDR_DIFF_VEC:
1985       return;
1986
1987     case SET:
1988       /* Dispose quickly of (set (reg..) (reg..)) if both have hard regs and it
1989          is cheap to move between them.  If it is not, there may not be an insn
1990          to do the copy, so we may need a reload.  */
1991       if (GET_CODE (SET_DEST (body)) == REG
1992           && REGNO (SET_DEST (body)) < FIRST_PSEUDO_REGISTER
1993           && GET_CODE (SET_SRC (body)) == REG
1994           && REGNO (SET_SRC (body)) < FIRST_PSEUDO_REGISTER
1995           && REGISTER_MOVE_COST (REGNO_REG_CLASS (REGNO (SET_SRC (body))),
1996                                  REGNO_REG_CLASS (REGNO (SET_DEST (body)))) == 2)
1997         return;
1998     case PARALLEL:
1999     case ASM_OPERANDS:
2000       noperands = asm_noperands (body);
2001       if (noperands >= 0)
2002         {
2003           /* This insn is an `asm' with operands.  */
2004
2005           insn_code_number = -1;
2006           this_insn_is_asm = 1;
2007
2008           /* expand_asm_operands makes sure there aren't too many operands.  */
2009           if (noperands > MAX_RECOG_OPERANDS)
2010             abort ();
2011
2012           /* Now get the operand values and constraints out of the insn.  */
2013
2014           decode_asm_operands (body, recog_operand, recog_operand_loc,
2015                                constraints, operand_mode);
2016           if (noperands > 0)
2017             {
2018               bcopy (constraints, constraints1, noperands * sizeof (char *));
2019               n_alternatives = n_occurrences (',', constraints[0]) + 1;
2020               for (i = 1; i < noperands; i++)
2021                 if (n_alternatives != n_occurrences (',', constraints[i]) + 1)
2022                   {
2023                     error_for_asm (insn, "operand constraints differ in number of alternatives");
2024                     /* Avoid further trouble with this insn.  */
2025                     PATTERN (insn) = gen_rtx (USE, VOIDmode, const0_rtx);
2026                     n_reloads = 0;
2027                     return;
2028                   }
2029             }
2030           break;
2031         }
2032
2033     default:
2034       /* Ordinary insn: recognize it, get the operands via insn_extract
2035          and get the constraints.  */
2036
2037       insn_code_number = recog_memoized (insn);
2038       if (insn_code_number < 0)
2039         fatal_insn_not_found (insn);
2040
2041       noperands = insn_n_operands[insn_code_number];
2042       n_alternatives = insn_n_alternatives[insn_code_number];
2043       /* Just return "no reloads" if insn has no operands with constraints.  */
2044       if (n_alternatives == 0)
2045         return;
2046       insn_extract (insn);
2047       for (i = 0; i < noperands; i++)
2048         {
2049           constraints[i] = constraints1[i]
2050             = insn_operand_constraint[insn_code_number][i];
2051           operand_mode[i] = insn_operand_mode[insn_code_number][i];
2052         }
2053     }
2054
2055   if (noperands == 0)
2056     return;
2057
2058   commutative = -1;
2059
2060   /* If we will need to know, later, whether some pair of operands
2061      are the same, we must compare them now and save the result.
2062      Reloading the base and index registers will clobber them
2063      and afterward they will fail to match.  */
2064
2065   for (i = 0; i < noperands; i++)
2066     {
2067       register char *p;
2068       register int c;
2069
2070       substed_operand[i] = recog_operand[i];
2071       p = constraints[i];
2072
2073       /* Scan this operand's constraint to see if it should match another.  */
2074
2075       while (c = *p++)
2076         if (c == '%')
2077           {
2078             /* The last operand should not be marked commutative.  */
2079             if (i == noperands - 1)
2080               {
2081                 if (this_insn_is_asm)
2082                   warning_for_asm (this_insn,
2083                                    "`%%' constraint used with last operand");
2084                 else
2085                   abort ();
2086               }
2087             else
2088               commutative = i;
2089           }
2090         else if (c >= '0' && c <= '9')
2091           {
2092             c -= '0';
2093             operands_match[c][i]
2094               = operands_match_p (recog_operand[c], recog_operand[i]);
2095
2096             /* An operand may not match itself.  */
2097             if (c == i)
2098               {
2099                 if (this_insn_is_asm)
2100                   warning_for_asm (this_insn,
2101                                    "operand %d has constraint %d", i, c);
2102                 else
2103                   abort ();
2104               }
2105
2106             /* If C can be commuted with C+1, and C might need to match I,
2107                then C+1 might also need to match I.  */
2108             if (commutative >= 0)
2109               {
2110                 if (c == commutative || c == commutative + 1)
2111                   {
2112                     int other = c + (c == commutative ? 1 : -1);
2113                     operands_match[other][i]
2114                       = operands_match_p (recog_operand[other], recog_operand[i]);
2115                   }
2116                 if (i == commutative || i == commutative + 1)
2117                   {
2118                     int other = i + (i == commutative ? 1 : -1);
2119                     operands_match[c][other]
2120                       = operands_match_p (recog_operand[c], recog_operand[other]);
2121                   }
2122                 /* Note that C is supposed to be less than I.
2123                    No need to consider altering both C and I
2124                    because in that case we would alter one into the other.  */
2125               }
2126           }
2127     }
2128
2129   /* Examine each operand that is a memory reference or memory address
2130      and reload parts of the addresses into index registers.
2131      While we are at it, initialize the array `modified'.
2132      Also here any references to pseudo regs that didn't get hard regs
2133      but are equivalent to constants get replaced in the insn itself
2134      with those constants.  Nobody will ever see them again.
2135
2136      Finally, set up the preferred classes of each operand.  */
2137
2138   for (i = 0; i < noperands; i++)
2139     {
2140       register RTX_CODE code = GET_CODE (recog_operand[i]);
2141       modified[i] = RELOAD_READ;
2142       address_reloaded[i] = 0;
2143
2144       if (constraints[i][0] == 'p')
2145         {
2146           find_reloads_address (VOIDmode, NULL_PTR,
2147                                 recog_operand[i], recog_operand_loc[i],
2148                                 recog_operand[i], ind_levels);
2149           substed_operand[i] = recog_operand[i] = *recog_operand_loc[i];
2150         }
2151       else if (code == MEM)
2152         {
2153           if (find_reloads_address (GET_MODE (recog_operand[i]),
2154                                     recog_operand_loc[i],
2155                                     XEXP (recog_operand[i], 0),
2156                                     &XEXP (recog_operand[i], 0),
2157                                     recog_operand[i], ind_levels))
2158             address_reloaded[i] = 1;
2159           substed_operand[i] = recog_operand[i] = *recog_operand_loc[i];
2160         }
2161       else if (code == SUBREG)
2162         substed_operand[i] = recog_operand[i] = *recog_operand_loc[i]
2163           = find_reloads_toplev (recog_operand[i], ind_levels,
2164                                  set != 0
2165                                  && &SET_DEST (set) == recog_operand_loc[i]);
2166       else if (code == REG)
2167         {
2168           /* This is equivalent to calling find_reloads_toplev.
2169              The code is duplicated for speed.
2170              When we find a pseudo always equivalent to a constant,
2171              we replace it by the constant.  We must be sure, however,
2172              that we don't try to replace it in the insn in which it
2173              is being set.   */
2174           register int regno = REGNO (recog_operand[i]);
2175           if (reg_equiv_constant[regno] != 0
2176               && (set == 0 || &SET_DEST (set) != recog_operand_loc[i]))
2177             substed_operand[i] = recog_operand[i]
2178               = reg_equiv_constant[regno];
2179 #if 0 /* This might screw code in reload1.c to delete prior output-reload
2180          that feeds this insn.  */
2181           if (reg_equiv_mem[regno] != 0)
2182             substed_operand[i] = recog_operand[i]
2183               = reg_equiv_mem[regno];
2184 #endif
2185           if (reg_equiv_address[regno] != 0)
2186             {
2187               /* If reg_equiv_address is not a constant address, copy it,
2188                  since it may be shared.  */
2189               rtx address = reg_equiv_address[regno];
2190
2191               if (rtx_varies_p (address))
2192                 address = copy_rtx (address);
2193
2194               /* If this is an output operand, we must output a CLOBBER
2195                  after INSN so find_equiv_reg knows REGNO is being written. */
2196               if (constraints[i][0] == '='
2197                   || constraints[i][0] == '+')
2198                 emit_insn_after (gen_rtx (CLOBBER, VOIDmode, recog_operand[i]),
2199                                  insn);
2200
2201               *recog_operand_loc[i] = recog_operand[i]
2202                 = gen_rtx (MEM, GET_MODE (recog_operand[i]), address);
2203               RTX_UNCHANGING_P (recog_operand[i])
2204                 = RTX_UNCHANGING_P (regno_reg_rtx[regno]);
2205               find_reloads_address (GET_MODE (recog_operand[i]),
2206                                     recog_operand_loc[i],
2207                                     XEXP (recog_operand[i], 0),
2208                                     &XEXP (recog_operand[i], 0),
2209                                     recog_operand[i], ind_levels);
2210               substed_operand[i] = recog_operand[i] = *recog_operand_loc[i];
2211             }
2212         }
2213       /* If the operand is still a register (we didn't replace it with an
2214          equivalent), get the preferred class to reload it into.  */
2215       code = GET_CODE (recog_operand[i]);
2216       preferred_class[i]
2217         = ((code == REG && REGNO (recog_operand[i]) >= FIRST_PSEUDO_REGISTER)
2218            ? reg_preferred_class (REGNO (recog_operand[i])) : NO_REGS);
2219       pref_or_nothing[i]
2220         = (code == REG && REGNO (recog_operand[i]) >= FIRST_PSEUDO_REGISTER
2221            && reg_alternate_class (REGNO (recog_operand[i])) == NO_REGS);
2222     }
2223
2224   /* If this is simply a copy from operand 1 to operand 0, merge the
2225      preferred classes for the operands.  */
2226   if (set != 0 && noperands >= 2 && recog_operand[0] == SET_DEST (set)
2227       && recog_operand[1] == SET_SRC (set))
2228     {
2229       preferred_class[0] = preferred_class[1]
2230         = reg_class_subunion[(int) preferred_class[0]][(int) preferred_class[1]];
2231       pref_or_nothing[0] |= pref_or_nothing[1];
2232       pref_or_nothing[1] |= pref_or_nothing[0];
2233     }
2234
2235   /* Now see what we need for pseudo-regs that didn't get hard regs
2236      or got the wrong kind of hard reg.  For this, we must consider
2237      all the operands together against the register constraints.  */
2238
2239   best = MAX_RECOG_OPERANDS + 300;
2240
2241   swapped = 0;
2242   goal_alternative_swapped = 0;
2243  try_swapped:
2244
2245   /* The constraints are made of several alternatives.
2246      Each operand's constraint looks like foo,bar,... with commas
2247      separating the alternatives.  The first alternatives for all
2248      operands go together, the second alternatives go together, etc.
2249
2250      First loop over alternatives.  */
2251
2252   for (this_alternative_number = 0;
2253        this_alternative_number < n_alternatives;
2254        this_alternative_number++)
2255     {
2256       /* Loop over operands for one constraint alternative.  */
2257       /* LOSERS counts those that don't fit this alternative
2258          and would require loading.  */
2259       int losers = 0;
2260       /* BAD is set to 1 if it some operand can't fit this alternative
2261          even after reloading.  */
2262       int bad = 0;
2263       /* REJECT is a count of how undesirable this alternative says it is
2264          if any reloading is required.  If the alternative matches exactly
2265          then REJECT is ignored, but otherwise it gets this much
2266          counted against it in addition to the reloading needed.  Each
2267          ? counts three times here since we want the disparaging caused by
2268          a bad register class to only count 1/3 as much.  */
2269       int reject = 0;
2270
2271       this_earlyclobber = 0;
2272
2273       for (i = 0; i < noperands; i++)
2274         {
2275           register char *p = constraints[i];
2276           register int win = 0;
2277           /* 0 => this operand can be reloaded somehow for this alternative */
2278           int badop = 1;
2279           /* 0 => this operand can be reloaded if the alternative allows regs.  */
2280           int winreg = 0;
2281           int c;
2282           register rtx operand = recog_operand[i];
2283           int offset = 0;
2284           /* Nonzero means this is a MEM that must be reloaded into a reg
2285              regardless of what the constraint says.  */
2286           int force_reload = 0;
2287           int offmemok = 0;
2288           int earlyclobber = 0;
2289
2290           /* If the operand is a SUBREG, extract
2291              the REG or MEM (or maybe even a constant) within.
2292              (Constants can occur as a result of reg_equiv_constant.)  */
2293
2294           while (GET_CODE (operand) == SUBREG)
2295             {
2296               offset += SUBREG_WORD (operand);
2297               operand = SUBREG_REG (operand);
2298               /* Force reload if this is not a register or if there may may
2299                  be a problem accessing the register in the outer mode.  */
2300               if (GET_CODE (operand) != REG
2301 #if defined(BYTE_LOADS_ZERO_EXTEND) || defined(BYTE_LOADS_SIGN_EXTEND)
2302                   /* ??? The comment below clearly does not match the code.
2303                      What the code below actually does is set force_reload
2304                      for a paradoxical subreg of a pseudo.  rms and kenner
2305                      can't see the point of doing this.  */
2306                   /* Nonparadoxical subreg of a pseudoreg.
2307                      Don't to load the full width if on this machine
2308                      we expected the fetch to extend.  */
2309                   || ((GET_MODE_SIZE (operand_mode[i])
2310                        > GET_MODE_SIZE (GET_MODE (operand)))
2311                       && REGNO (operand) >= FIRST_PSEUDO_REGISTER)
2312 #endif
2313                   /* Subreg of a hard reg which can't handle the subreg's mode
2314                      or which would handle that mode in the wrong number of
2315                      registers for subregging to work.  */
2316                   || (REGNO (operand) < FIRST_PSEUDO_REGISTER
2317                       && (! HARD_REGNO_MODE_OK (REGNO (operand),
2318                                                 operand_mode[i])
2319                           || (GET_MODE_SIZE (operand_mode[i]) <= UNITS_PER_WORD
2320                               && (GET_MODE_SIZE (GET_MODE (operand))
2321                                   > UNITS_PER_WORD)
2322                               && ((GET_MODE_SIZE (GET_MODE (operand))
2323                                    / UNITS_PER_WORD)
2324                                   != HARD_REGNO_NREGS (REGNO (operand),
2325                                                        GET_MODE (operand)))))))
2326                 force_reload = 1;
2327             }
2328
2329           this_alternative[i] = (int) NO_REGS;
2330           this_alternative_win[i] = 0;
2331           this_alternative_offmemok[i] = 0;
2332           this_alternative_earlyclobber[i] = 0;
2333           this_alternative_matches[i] = -1;
2334
2335           /* An empty constraint or empty alternative
2336              allows anything which matched the pattern.  */
2337           if (*p == 0 || *p == ',')
2338             win = 1, badop = 0;
2339
2340           /* Scan this alternative's specs for this operand;
2341              set WIN if the operand fits any letter in this alternative.
2342              Otherwise, clear BADOP if this operand could
2343              fit some letter after reloads,
2344              or set WINREG if this operand could fit after reloads
2345              provided the constraint allows some registers.  */
2346
2347           while (*p && (c = *p++) != ',')
2348             switch (c)
2349               {
2350               case '=':
2351                 modified[i] = RELOAD_WRITE;
2352                 break;
2353
2354               case '+':
2355                 modified[i] = RELOAD_READ_WRITE;
2356                 break;
2357
2358               case '*':
2359                 break;
2360
2361               case '%':
2362                 /* The last operand should not be marked commutative.  */
2363                 if (i != noperands - 1)
2364                   commutative = i;
2365                 break;
2366
2367               case '?':
2368                 reject += 3;
2369                 break;
2370
2371               case '!':
2372                 reject = 300;
2373                 break;
2374
2375               case '#':
2376                 /* Ignore rest of this alternative as far as
2377                    reloading is concerned.  */
2378                 while (*p && *p != ',') p++;
2379                 break;
2380
2381               case '0':
2382               case '1':
2383               case '2':
2384               case '3':
2385               case '4':
2386                 c -= '0';
2387                 this_alternative_matches[i] = c;
2388                 /* We are supposed to match a previous operand.
2389                    If we do, we win if that one did.
2390                    If we do not, count both of the operands as losers.
2391                    (This is too conservative, since most of the time
2392                    only a single reload insn will be needed to make
2393                    the two operands win.  As a result, this alternative
2394                    may be rejected when it is actually desirable.)  */
2395                 if ((swapped && (c != commutative || i != commutative + 1))
2396                     /* If we are matching as if two operands were swapped,
2397                        also pretend that operands_match had been computed
2398                        with swapped.
2399                        But if I is the second of those and C is the first,
2400                        don't exchange them, because operands_match is valid
2401                        only on one side of its diagonal.  */
2402                     ? (operands_match
2403                         [(c == commutative || c == commutative + 1)
2404                          ? 2*commutative + 1 - c : c]
2405                         [(i == commutative || i == commutative + 1)
2406                          ? 2*commutative + 1 - i : i])
2407                     : operands_match[c][i])
2408                   win = this_alternative_win[c];
2409                 else
2410                   {
2411                     /* Operands don't match.  */
2412                     rtx value;
2413                     /* Retroactively mark the operand we had to match
2414                        as a loser, if it wasn't already.  */
2415                     if (this_alternative_win[c])
2416                       losers++;
2417                     this_alternative_win[c] = 0;
2418                     if (this_alternative[c] == (int) NO_REGS)
2419                       bad = 1;
2420                     /* But count the pair only once in the total badness of
2421                        this alternative, if the pair can be a dummy reload.  */
2422                     value
2423                       = find_dummy_reload (recog_operand[i], recog_operand[c],
2424                                            recog_operand_loc[i], recog_operand_loc[c],
2425                                            this_alternative[c], -1);
2426
2427                     if (value != 0)
2428                       losers--;
2429                   }
2430                 /* This can be fixed with reloads if the operand
2431                    we are supposed to match can be fixed with reloads.  */
2432                 badop = 0;
2433                 this_alternative[i] = this_alternative[c];
2434                 break;
2435
2436               case 'p':
2437                 /* All necessary reloads for an address_operand
2438                    were handled in find_reloads_address.  */
2439                 this_alternative[i] = (int) ALL_REGS;
2440                 win = 1;
2441                 break;
2442
2443               case 'm':
2444                 if (force_reload)
2445                   break;
2446                 if (GET_CODE (operand) == MEM
2447                     || (GET_CODE (operand) == REG
2448                         && REGNO (operand) >= FIRST_PSEUDO_REGISTER
2449                         && reg_renumber[REGNO (operand)] < 0))
2450                   win = 1;
2451                 if (CONSTANT_P (operand))
2452                   badop = 0;
2453                 break;
2454
2455               case '<':
2456                 if (GET_CODE (operand) == MEM
2457                     && ! address_reloaded[i]
2458                     && (GET_CODE (XEXP (operand, 0)) == PRE_DEC
2459                         || GET_CODE (XEXP (operand, 0)) == POST_DEC))
2460                   win = 1;
2461                 break;
2462
2463               case '>':
2464                 if (GET_CODE (operand) == MEM
2465                     && ! address_reloaded[i]
2466                     && (GET_CODE (XEXP (operand, 0)) == PRE_INC
2467                         || GET_CODE (XEXP (operand, 0)) == POST_INC))
2468                   win = 1;
2469                 break;
2470
2471                 /* Memory operand whose address is not offsettable.  */
2472               case 'V':
2473                 if (force_reload)
2474                   break;
2475                 if (GET_CODE (operand) == MEM
2476                     && ! (ind_levels ? offsettable_memref_p (operand)
2477                           : offsettable_nonstrict_memref_p (operand))
2478                     /* Certain mem addresses will become offsettable
2479                        after they themselves are reloaded.  This is important;
2480                        we don't want our own handling of unoffsettables
2481                        to override the handling of reg_equiv_address.  */
2482                     && !(GET_CODE (XEXP (operand, 0)) == REG
2483                          && (ind_levels == 0
2484                              || reg_equiv_address[REGNO (XEXP (operand, 0))] != 0)))
2485                   win = 1;
2486                 break;
2487
2488                 /* Memory operand whose address is offsettable.  */
2489               case 'o':
2490                 if (force_reload)
2491                   break;
2492                 if ((GET_CODE (operand) == MEM
2493                      /* If IND_LEVELS, find_reloads_address won't reload a
2494                         pseudo that didn't get a hard reg, so we have to
2495                         reject that case.  */
2496                      && (ind_levels ? offsettable_memref_p (operand)
2497                          : offsettable_nonstrict_memref_p (operand)))
2498                     /* Certain mem addresses will become offsettable
2499                        after they themselves are reloaded.  This is important;
2500                        we don't want our own handling of unoffsettables
2501                        to override the handling of reg_equiv_address.  */
2502                     || (GET_CODE (operand) == MEM
2503                         && GET_CODE (XEXP (operand, 0)) == REG
2504                         && (ind_levels == 0
2505                             || reg_equiv_address[REGNO (XEXP (operand, 0))] != 0))
2506                     || (GET_CODE (operand) == REG
2507                         && REGNO (operand) >= FIRST_PSEUDO_REGISTER
2508                         && reg_renumber[REGNO (operand)] < 0))
2509                   win = 1;
2510                 if (CONSTANT_P (operand) || GET_CODE (operand) == MEM)
2511                   badop = 0;
2512                 offmemok = 1;
2513                 break;
2514
2515               case '&':
2516                 /* Output operand that is stored before the need for the
2517                    input operands (and their index registers) is over.  */
2518                 earlyclobber = 1, this_earlyclobber = 1;
2519                 break;
2520
2521               case 'E':
2522                 /* Match any floating double constant, but only if
2523                    we can examine the bits of it reliably.  */
2524                 if ((HOST_FLOAT_FORMAT != TARGET_FLOAT_FORMAT
2525                      || HOST_BITS_PER_WIDE_INT != BITS_PER_WORD)
2526                     && GET_MODE (operand) != VOIDmode && ! flag_pretend_float)
2527                   break;
2528                 if (GET_CODE (operand) == CONST_DOUBLE)
2529                   win = 1;
2530                 break;
2531
2532               case 'F':
2533                 if (GET_CODE (operand) == CONST_DOUBLE)
2534                   win = 1;
2535                 break;
2536
2537               case 'G':
2538               case 'H':
2539                 if (GET_CODE (operand) == CONST_DOUBLE
2540                     && CONST_DOUBLE_OK_FOR_LETTER_P (operand, c))
2541                   win = 1;
2542                 break;
2543
2544               case 's':
2545                 if (GET_CODE (operand) == CONST_INT
2546                     || (GET_CODE (operand) == CONST_DOUBLE
2547                         && GET_MODE (operand) == VOIDmode))
2548                   break;
2549               case 'i':
2550                 if (CONSTANT_P (operand)
2551 #ifdef LEGITIMATE_PIC_OPERAND_P
2552                     && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (operand))
2553 #endif
2554                     )
2555                   win = 1;
2556                 break;
2557
2558               case 'n':
2559                 if (GET_CODE (operand) == CONST_INT
2560                     || (GET_CODE (operand) == CONST_DOUBLE
2561                         && GET_MODE (operand) == VOIDmode))
2562                   win = 1;
2563                 break;
2564
2565               case 'I':
2566               case 'J':
2567               case 'K':
2568               case 'L':
2569               case 'M':
2570               case 'N':
2571               case 'O':
2572               case 'P':
2573                 if (GET_CODE (operand) == CONST_INT
2574                     && CONST_OK_FOR_LETTER_P (INTVAL (operand), c))
2575                   win = 1;
2576                 break;
2577
2578               case 'X':
2579                 win = 1;
2580                 break;
2581
2582               case 'g':
2583                 if (! force_reload
2584                     /* A PLUS is never a valid operand, but reload can make
2585                        it from a register when eliminating registers.  */
2586                     && GET_CODE (operand) != PLUS
2587                     /* A SCRATCH is not a valid operand.  */
2588                     && GET_CODE (operand) != SCRATCH
2589 #ifdef LEGITIMATE_PIC_OPERAND_P
2590                     && (! CONSTANT_P (operand)
2591                         || ! flag_pic
2592                         || LEGITIMATE_PIC_OPERAND_P (operand))
2593 #endif
2594                     && (GENERAL_REGS == ALL_REGS
2595                         || GET_CODE (operand) != REG
2596                         || (REGNO (operand) >= FIRST_PSEUDO_REGISTER
2597                             && reg_renumber[REGNO (operand)] < 0)))
2598                   win = 1;
2599                 /* Drop through into 'r' case */
2600
2601               case 'r':
2602                 this_alternative[i]
2603                   = (int) reg_class_subunion[this_alternative[i]][(int) GENERAL_REGS];
2604                 goto reg;
2605
2606 #ifdef EXTRA_CONSTRAINT
2607               case 'Q':
2608               case 'R':
2609               case 'S':
2610               case 'T':
2611               case 'U':
2612                 if (EXTRA_CONSTRAINT (operand, c))
2613                   win = 1;
2614                 break;
2615 #endif
2616
2617               default:
2618                 this_alternative[i]
2619                   = (int) reg_class_subunion[this_alternative[i]][(int) REG_CLASS_FROM_LETTER (c)];
2620
2621               reg:
2622                 if (GET_MODE (operand) == BLKmode)
2623                   break;
2624                 winreg = 1;
2625                 if (GET_CODE (operand) == REG
2626                     && reg_fits_class_p (operand, this_alternative[i],
2627                                          offset, GET_MODE (recog_operand[i])))
2628                   win = 1;
2629                 break;
2630               }
2631
2632           constraints[i] = p;
2633
2634           /* If this operand could be handled with a reg,
2635              and some reg is allowed, then this operand can be handled.  */
2636           if (winreg && this_alternative[i] != (int) NO_REGS)
2637             badop = 0;
2638
2639           /* Record which operands fit this alternative.  */
2640           this_alternative_earlyclobber[i] = earlyclobber;
2641           if (win && ! force_reload)
2642             this_alternative_win[i] = 1;
2643           else
2644             {
2645               this_alternative_offmemok[i] = offmemok;
2646               losers++;
2647               if (badop)
2648                 bad = 1;
2649               /* Alternative loses if it has no regs for a reg operand.  */
2650               if (GET_CODE (operand) == REG
2651                   && this_alternative[i] == (int) NO_REGS
2652                   && this_alternative_matches[i] < 0)
2653                 bad = 1;
2654
2655               /* Alternative loses if it requires a type of reload not
2656                  permitted for this insn.  We can always reload SCRATCH
2657                  and objects with a REG_UNUSED note.  */
2658               if (GET_CODE (operand) != SCRATCH && modified[i] != RELOAD_READ
2659                   && no_output_reloads
2660                   && ! find_reg_note (insn, REG_UNUSED, operand))
2661                 bad = 1;
2662               else if (modified[i] != RELOAD_WRITE && no_input_reloads)
2663                 bad = 1;
2664
2665               /* We prefer to reload pseudos over reloading other things,
2666                  since such reloads may be able to be eliminated later.
2667                  If we are reloading a SCRATCH, we won't be generating any
2668                  insns, just using a register, so it is also preferred.
2669                  So bump REJECT in other cases.  */
2670               if (GET_CODE (operand) != REG && GET_CODE (operand) != SCRATCH)
2671                 reject++;
2672             }
2673
2674           /* If this operand is a pseudo register that didn't get a hard
2675              reg and this alternative accepts some register, see if the
2676              class that we want is a subset of the preferred class for this
2677              register.  If not, but it intersects that class, use the
2678              preferred class instead.  If it does not intersect the preferred
2679              class, show that usage of this alternative should be discouraged;
2680              it will be discouraged more still if the register is `preferred
2681              or nothing'.  We do this because it increases the chance of
2682              reusing our spill register in a later insn and avoiding a pair
2683              of memory stores and loads.
2684
2685              Don't bother with this if this alternative will accept this
2686              operand.
2687
2688              Don't do this if the preferred class has only one register
2689              because we might otherwise exhaust the class.  */
2690
2691
2692           if (! win && this_alternative[i] != (int) NO_REGS
2693               && reg_class_size[(int) preferred_class[i]] > 1)
2694             {
2695               if (! reg_class_subset_p (this_alternative[i],
2696                                         preferred_class[i]))
2697                 {
2698                   /* Since we don't have a way of forming the intersection,
2699                      we just do something special if the preferred class
2700                      is a subset of the class we have; that's the most
2701                      common case anyway.  */
2702                   if (reg_class_subset_p (preferred_class[i],
2703                                           this_alternative[i]))
2704                     this_alternative[i] = (int) preferred_class[i];
2705                   else
2706                     reject += (1 + pref_or_nothing[i]);
2707                 }
2708             }
2709         }
2710
2711       /* Now see if any output operands that are marked "earlyclobber"
2712          in this alternative conflict with any input operands
2713          or any memory addresses.  */
2714
2715       for (i = 0; i < noperands; i++)
2716         if (this_alternative_earlyclobber[i]
2717             && this_alternative_win[i])
2718           {
2719             struct decomposition early_data;
2720             int j;
2721
2722             early_data = decompose (recog_operand[i]);
2723
2724             if (modified[i] == RELOAD_READ)
2725               {
2726                 if (this_insn_is_asm)
2727                   warning_for_asm (this_insn,
2728                                    "`&' constraint used with input operand");
2729                 else
2730                   abort ();
2731                 continue;
2732               }
2733
2734             if (this_alternative[i] == NO_REGS)
2735               {
2736                 this_alternative_earlyclobber[i] = 0;
2737                 if (this_insn_is_asm)
2738                   error_for_asm (this_insn,
2739                                  "`&' constraint used with no register class");
2740                 else
2741                   abort ();
2742               }
2743
2744             for (j = 0; j < noperands; j++)
2745               /* Is this an input operand or a memory ref?  */
2746               if ((GET_CODE (recog_operand[j]) == MEM
2747                    || modified[j] != RELOAD_WRITE)
2748                   && j != i
2749                   /* Ignore things like match_operator operands.  */
2750                   && *constraints1[j] != 0
2751                   /* Don't count an input operand that is constrained to match
2752                      the early clobber operand.  */
2753                   && ! (this_alternative_matches[j] == i
2754                         && rtx_equal_p (recog_operand[i], recog_operand[j]))
2755                   /* Is it altered by storing the earlyclobber operand?  */
2756                   && !immune_p (recog_operand[j], recog_operand[i], early_data))
2757                 {
2758                   /* If the output is in a single-reg class,
2759                      it's costly to reload it, so reload the input instead.  */
2760                   if (reg_class_size[this_alternative[i]] == 1
2761                       && (GET_CODE (recog_operand[j]) == REG
2762                           || GET_CODE (recog_operand[j]) == SUBREG))
2763                     {
2764                       losers++;
2765                       this_alternative_win[j] = 0;
2766                     }
2767                   else
2768                     break;
2769                 }
2770             /* If an earlyclobber operand conflicts with something,
2771                it must be reloaded, so request this and count the cost.  */
2772             if (j != noperands)
2773               {
2774                 losers++;
2775                 this_alternative_win[i] = 0;
2776                 for (j = 0; j < noperands; j++)
2777                   if (this_alternative_matches[j] == i
2778                       && this_alternative_win[j])
2779                     {
2780                       this_alternative_win[j] = 0;
2781                       losers++;
2782                     }
2783               }
2784           }
2785
2786       /* If one alternative accepts all the operands, no reload required,
2787          choose that alternative; don't consider the remaining ones.  */
2788       if (losers == 0)
2789         {
2790           /* Unswap these so that they are never swapped at `finish'.  */
2791           if (commutative >= 0)
2792             {
2793               recog_operand[commutative] = substed_operand[commutative];
2794               recog_operand[commutative + 1]
2795                 = substed_operand[commutative + 1];
2796             }
2797           for (i = 0; i < noperands; i++)
2798             {
2799               goal_alternative_win[i] = 1;
2800               goal_alternative[i] = this_alternative[i];
2801               goal_alternative_offmemok[i] = this_alternative_offmemok[i];
2802               goal_alternative_matches[i] = this_alternative_matches[i];
2803               goal_alternative_earlyclobber[i]
2804                 = this_alternative_earlyclobber[i];
2805             }
2806           goal_alternative_number = this_alternative_number;
2807           goal_alternative_swapped = swapped;
2808           goal_earlyclobber = this_earlyclobber;
2809           goto finish;
2810         }
2811
2812       /* REJECT, set by the ! and ? constraint characters and when a register
2813          would be reloaded into a non-preferred class, discourages the use of
2814          this alternative for a reload goal.  REJECT is incremented by three
2815          for each ? and one for each non-preferred class.  */
2816       losers = losers * 3 + reject;
2817
2818       /* If this alternative can be made to work by reloading,
2819          and it needs less reloading than the others checked so far,
2820          record it as the chosen goal for reloading.  */
2821       if (! bad && best > losers)
2822         {
2823           for (i = 0; i < noperands; i++)
2824             {
2825               goal_alternative[i] = this_alternative[i];
2826               goal_alternative_win[i] = this_alternative_win[i];
2827               goal_alternative_offmemok[i] = this_alternative_offmemok[i];
2828               goal_alternative_matches[i] = this_alternative_matches[i];
2829               goal_alternative_earlyclobber[i]
2830                 = this_alternative_earlyclobber[i];
2831             }
2832           goal_alternative_swapped = swapped;
2833           best = losers;
2834           goal_alternative_number = this_alternative_number;
2835           goal_earlyclobber = this_earlyclobber;
2836         }
2837     }
2838
2839   /* If insn is commutative (it's safe to exchange a certain pair of operands)
2840      then we need to try each alternative twice,
2841      the second time matching those two operands
2842      as if we had exchanged them.
2843      To do this, really exchange them in operands.
2844
2845      If we have just tried the alternatives the second time,
2846      return operands to normal and drop through.  */
2847
2848   if (commutative >= 0)
2849     {
2850       swapped = !swapped;
2851       if (swapped)
2852         {
2853           register enum reg_class tclass;
2854           register int t;
2855
2856           recog_operand[commutative] = substed_operand[commutative + 1];
2857           recog_operand[commutative + 1] = substed_operand[commutative];
2858
2859           tclass = preferred_class[commutative];
2860           preferred_class[commutative] = preferred_class[commutative + 1];
2861           preferred_class[commutative + 1] = tclass;
2862
2863           t = pref_or_nothing[commutative];
2864           pref_or_nothing[commutative] = pref_or_nothing[commutative + 1];
2865           pref_or_nothing[commutative + 1] = t;
2866
2867           bcopy (constraints1, constraints, noperands * sizeof (char *));
2868           goto try_swapped;
2869         }
2870       else
2871         {
2872           recog_operand[commutative] = substed_operand[commutative];
2873           recog_operand[commutative + 1] = substed_operand[commutative + 1];
2874         }
2875     }
2876
2877   /* The operands don't meet the constraints.
2878      goal_alternative describes the alternative
2879      that we could reach by reloading the fewest operands.
2880      Reload so as to fit it.  */
2881
2882   if (best == MAX_RECOG_OPERANDS + 300)
2883     {
2884       /* No alternative works with reloads??  */
2885       if (insn_code_number >= 0)
2886         abort ();
2887       error_for_asm (insn, "inconsistent operand constraints in an `asm'");
2888       /* Avoid further trouble with this insn.  */
2889       PATTERN (insn) = gen_rtx (USE, VOIDmode, const0_rtx);
2890       n_reloads = 0;
2891       return;
2892     }
2893
2894   /* Jump to `finish' from above if all operands are valid already.
2895      In that case, goal_alternative_win is all 1.  */
2896  finish:
2897
2898   /* Right now, for any pair of operands I and J that are required to match,
2899      with I < J,
2900      goal_alternative_matches[J] is I.
2901      Set up goal_alternative_matched as the inverse function:
2902      goal_alternative_matched[I] = J.  */
2903
2904   for (i = 0; i < noperands; i++)
2905     goal_alternative_matched[i] = -1;
2906
2907   for (i = 0; i < noperands; i++)
2908     if (! goal_alternative_win[i]
2909         && goal_alternative_matches[i] >= 0)
2910       goal_alternative_matched[goal_alternative_matches[i]] = i;
2911
2912   /* If the best alternative is with operands 1 and 2 swapped,
2913      consider them swapped before reporting the reloads.  */
2914
2915   if (goal_alternative_swapped)
2916     {
2917       register rtx tem;
2918
2919       tem = substed_operand[commutative];
2920       substed_operand[commutative] = substed_operand[commutative + 1];
2921       substed_operand[commutative + 1] = tem;
2922       tem = recog_operand[commutative];
2923       recog_operand[commutative] = recog_operand[commutative + 1];
2924       recog_operand[commutative + 1] = tem;
2925     }
2926
2927   /* Perform whatever substitutions on the operands we are supposed
2928      to make due to commutativity or replacement of registers
2929      with equivalent constants or memory slots.  */
2930
2931   for (i = 0; i < noperands; i++)
2932     {
2933       *recog_operand_loc[i] = substed_operand[i];
2934       /* While we are looping on operands, initialize this.  */
2935       operand_reloadnum[i] = -1;
2936     }
2937
2938   /* Any constants that aren't allowed and can't be reloaded
2939      into registers are here changed into memory references.  */
2940   for (i = 0; i < noperands; i++)
2941     if (! goal_alternative_win[i]
2942         && CONSTANT_P (recog_operand[i])
2943         && (PREFERRED_RELOAD_CLASS (recog_operand[i],
2944                                     (enum reg_class) goal_alternative[i])
2945             == NO_REGS)
2946         && operand_mode[i] != VOIDmode)
2947       {
2948         *recog_operand_loc[i] = recog_operand[i]
2949           = find_reloads_toplev (force_const_mem (operand_mode[i],
2950                                                   recog_operand[i]),
2951                                  ind_levels, 0);
2952         if (alternative_allows_memconst (constraints1[i],
2953                                          goal_alternative_number))
2954           goal_alternative_win[i] = 1;
2955       }
2956
2957   /* Now record reloads for all the operands that need them.  */
2958   for (i = 0; i < noperands; i++)
2959     if (! goal_alternative_win[i])
2960       {
2961         /* Operands that match previous ones have already been handled.  */
2962         if (goal_alternative_matches[i] >= 0)
2963           ;
2964         /* Handle an operand with a nonoffsettable address
2965            appearing where an offsettable address will do
2966            by reloading the address into a base register.  */
2967         else if (goal_alternative_matched[i] == -1
2968                  && goal_alternative_offmemok[i]
2969                  && GET_CODE (recog_operand[i]) == MEM)
2970           {
2971             operand_reloadnum[i]
2972               = push_reload (XEXP (recog_operand[i], 0), NULL_RTX,
2973                              &XEXP (recog_operand[i], 0), NULL_PTR,
2974                              BASE_REG_CLASS, GET_MODE (XEXP (recog_operand[i], 0)),
2975                              VOIDmode, 0, 0, NULL_RTX);
2976             reload_inc[operand_reloadnum[i]]
2977               = GET_MODE_SIZE (GET_MODE (recog_operand[i]));
2978           }
2979         else if (goal_alternative_matched[i] == -1)
2980           operand_reloadnum[i] =
2981             push_reload (modified[i] != RELOAD_WRITE ? recog_operand[i] : 0,
2982                          modified[i] != RELOAD_READ ? recog_operand[i] : 0,
2983                          modified[i] != RELOAD_WRITE ? recog_operand_loc[i] : 0,
2984                          modified[i] != RELOAD_READ ? recog_operand_loc[i] : 0,
2985                          (enum reg_class) goal_alternative[i],
2986                          (modified[i] == RELOAD_WRITE ? VOIDmode : operand_mode[i]),
2987                          (modified[i] == RELOAD_READ ? VOIDmode : operand_mode[i]),
2988                          (insn_code_number < 0 ? 0
2989                           : insn_operand_strict_low[insn_code_number][i]),
2990                          0, NULL_RTX);
2991         /* In a matching pair of operands, one must be input only
2992            and the other must be output only.
2993            Pass the input operand as IN and the other as OUT.  */
2994         else if (modified[i] == RELOAD_READ
2995                  && modified[goal_alternative_matched[i]] == RELOAD_WRITE)
2996           {
2997             operand_reloadnum[i]
2998               = push_reload (recog_operand[i],
2999                              recog_operand[goal_alternative_matched[i]],
3000                              recog_operand_loc[i],
3001                              recog_operand_loc[goal_alternative_matched[i]],
3002                              (enum reg_class) goal_alternative[i],
3003                              operand_mode[i],
3004                              operand_mode[goal_alternative_matched[i]],
3005                              0, 0, NULL_RTX);
3006             operand_reloadnum[goal_alternative_matched[i]] = output_reloadnum;
3007           }
3008         else if (modified[i] == RELOAD_WRITE
3009                  && modified[goal_alternative_matched[i]] == RELOAD_READ)
3010           {
3011             operand_reloadnum[goal_alternative_matched[i]]
3012               = push_reload (recog_operand[goal_alternative_matched[i]],
3013                              recog_operand[i],
3014                              recog_operand_loc[goal_alternative_matched[i]],
3015                              recog_operand_loc[i],
3016                              (enum reg_class) goal_alternative[i],
3017                              operand_mode[goal_alternative_matched[i]],
3018                              operand_mode[i],
3019                              0, 0, NULL_RTX);
3020             operand_reloadnum[i] = output_reloadnum;
3021           }
3022         else if (insn_code_number >= 0)
3023           abort ();
3024         else
3025           {
3026             error_for_asm (insn, "inconsistent operand constraints in an `asm'");
3027             /* Avoid further trouble with this insn.  */
3028             PATTERN (insn) = gen_rtx (USE, VOIDmode, const0_rtx);
3029             n_reloads = 0;
3030             return;
3031           }
3032       }
3033     else if (goal_alternative_matched[i] < 0
3034              && goal_alternative_matches[i] < 0
3035              && optimize)
3036       {
3037         rtx operand = recog_operand[i];
3038         /* For each non-matching operand that's a pseudo-register
3039            that didn't get a hard register, make an optional reload.
3040            This may get done even if the insn needs no reloads otherwise.  */
3041         /* (It would be safe to make an optional reload for a matching pair
3042            of operands, but we don't bother yet.)  */
3043         while (GET_CODE (operand) == SUBREG)
3044           operand = XEXP (operand, 0);
3045         if (GET_CODE (operand) == REG
3046             && REGNO (operand) >= FIRST_PSEUDO_REGISTER
3047             && reg_renumber[REGNO (operand)] < 0
3048             && (enum reg_class) goal_alternative[i] != NO_REGS
3049             /* Don't make optional output reloads for jump insns
3050                (such as aobjeq on the vax).  */
3051             && (modified[i] == RELOAD_READ
3052                 || GET_CODE (insn) != JUMP_INSN))
3053           operand_reloadnum[i]
3054             = push_reload (modified[i] != RELOAD_WRITE ? recog_operand[i] : 0,
3055                            modified[i] != RELOAD_READ ? recog_operand[i] : 0,
3056                            modified[i] != RELOAD_WRITE ? recog_operand_loc[i] : 0,
3057                            modified[i] != RELOAD_READ ? recog_operand_loc[i] : 0,
3058                            (enum reg_class) goal_alternative[i],
3059                            (modified[i] == RELOAD_WRITE ? VOIDmode : operand_mode[i]),
3060                            (modified[i] == RELOAD_READ ? VOIDmode : operand_mode[i]),
3061                            (insn_code_number < 0 ? 0
3062                             : insn_operand_strict_low[insn_code_number][i]),
3063                            1, NULL_RTX);
3064         /* Make an optional reload for an explicit mem ref.  */
3065         else if (GET_CODE (operand) == MEM
3066                  && (enum reg_class) goal_alternative[i] != NO_REGS
3067                  /* Don't make optional output reloads for jump insns
3068                     (such as aobjeq on the vax).  */
3069                  && (modified[i] == RELOAD_READ
3070                      || GET_CODE (insn) != JUMP_INSN))
3071           operand_reloadnum[i]
3072             = push_reload (modified[i] != RELOAD_WRITE ? recog_operand[i] : 0,
3073                            modified[i] != RELOAD_READ ? recog_operand[i] : 0,
3074                            modified[i] != RELOAD_WRITE ? recog_operand_loc[i] : 0,
3075                            modified[i] != RELOAD_READ ? recog_operand_loc[i] : 0,
3076                            (enum reg_class) goal_alternative[i],
3077                            (modified[i] == RELOAD_WRITE ? VOIDmode : operand_mode[i]),
3078                            (modified[i] == RELOAD_READ ? VOIDmode : operand_mode[i]),
3079                            (insn_code_number < 0 ? 0
3080                             : insn_operand_strict_low[insn_code_number][i]),
3081                            1, NULL_RTX);
3082         else
3083           non_reloaded_operands[n_non_reloaded_operands++] = recog_operand[i];
3084       }
3085     else if (goal_alternative_matched[i] < 0
3086              && goal_alternative_matches[i] < 0)
3087       non_reloaded_operands[n_non_reloaded_operands++] = recog_operand[i];
3088
3089   /* Record the values of the earlyclobber operands for the caller.  */
3090   if (goal_earlyclobber)
3091     for (i = 0; i < noperands; i++)
3092       if (goal_alternative_earlyclobber[i])
3093         reload_earlyclobbers[n_earlyclobbers++] = recog_operand[i];
3094
3095   /* If this insn pattern contains any MATCH_DUP's, make sure that
3096      they will be substituted if the operands they match are substituted.
3097      Also do now any substitutions we already did on the operands.
3098
3099      Don't do this if we aren't making replacements because we might be
3100      propagating things allocated by frame pointer elimination into places
3101      it doesn't expect.  */
3102
3103   if (insn_code_number >= 0 && replace)
3104     for (i = insn_n_dups[insn_code_number] - 1; i >= 0; i--)
3105       {
3106         int opno = recog_dup_num[i];
3107         *recog_dup_loc[i] = *recog_operand_loc[opno];
3108         if (operand_reloadnum[opno] >= 0)
3109           push_replacement (recog_dup_loc[i], operand_reloadnum[opno],
3110                             insn_operand_mode[insn_code_number][opno]);
3111       }
3112
3113 #if 0
3114   /* This loses because reloading of prior insns can invalidate the equivalence
3115      (or at least find_equiv_reg isn't smart enough to find it any more),
3116      causing this insn to need more reload regs than it needed before.
3117      It may be too late to make the reload regs available.
3118      Now this optimization is done safely in choose_reload_regs.  */
3119
3120   /* For each reload of a reg into some other class of reg,
3121      search for an existing equivalent reg (same value now) in the right class.
3122      We can use it as long as we don't need to change its contents.  */
3123   for (i = 0; i < n_reloads; i++)
3124     if (reload_reg_rtx[i] == 0
3125         && reload_in[i] != 0
3126         && GET_CODE (reload_in[i]) == REG
3127         && reload_out[i] == 0)
3128       {
3129         reload_reg_rtx[i]
3130           = find_equiv_reg (reload_in[i], insn, reload_reg_class[i], -1,
3131                             static_reload_reg_p, 0, reload_inmode[i]);
3132         /* Prevent generation of insn to load the value
3133            because the one we found already has the value.  */
3134         if (reload_reg_rtx[i])
3135           reload_in[i] = reload_reg_rtx[i];
3136       }
3137 #endif
3138
3139 #else /* no REGISTER_CONSTRAINTS */
3140   int noperands;
3141   int insn_code_number;
3142   int goal_earlyclobber = 0; /* Always 0, to make combine_reloads happen.  */
3143   register int i;
3144   rtx body = PATTERN (insn);
3145
3146   n_reloads = 0;
3147   n_replacements = 0;
3148   n_earlyclobbers = 0;
3149   replace_reloads = replace;
3150   this_insn = insn;
3151
3152   /* Find what kind of insn this is.  NOPERANDS gets number of operands.
3153      Store the operand values in RECOG_OPERAND and the locations
3154      of the words in the insn that point to them in RECOG_OPERAND_LOC.
3155      Return if the insn needs no reload processing.  */
3156
3157   switch (GET_CODE (body))
3158     {
3159     case USE:
3160     case CLOBBER:
3161     case ASM_INPUT:
3162     case ADDR_VEC:
3163     case ADDR_DIFF_VEC:
3164       return;
3165
3166     case PARALLEL:
3167     case SET:
3168       noperands = asm_noperands (body);
3169       if (noperands >= 0)
3170         {
3171           /* This insn is an `asm' with operands.
3172              First, find out how many operands, and allocate space.  */
3173
3174           insn_code_number = -1;
3175           /* ??? This is a bug! ???
3176              Give up and delete this insn if it has too many operands.  */
3177           if (noperands > MAX_RECOG_OPERANDS)
3178             abort ();
3179
3180           /* Now get the operand values out of the insn.  */
3181
3182           decode_asm_operands (body, recog_operand, recog_operand_loc,
3183                                NULL_PTR, NULL_PTR);
3184           break;
3185         }
3186
3187     default:
3188       /* Ordinary insn: recognize it, allocate space for operands and
3189          constraints, and get them out via insn_extract.  */
3190
3191       insn_code_number = recog_memoized (insn);
3192       noperands = insn_n_operands[insn_code_number];
3193       insn_extract (insn);
3194     }
3195
3196   if (noperands == 0)
3197     return;
3198
3199   for (i = 0; i < noperands; i++)
3200     {
3201       register RTX_CODE code = GET_CODE (recog_operand[i]);
3202       int is_set_dest = GET_CODE (body) == SET && (i == 0);
3203
3204       if (insn_code_number >= 0)
3205         if (insn_operand_address_p[insn_code_number][i])
3206           find_reloads_address (VOIDmode, NULL_PTR,
3207                                 recog_operand[i], recog_operand_loc[i],
3208                                 recog_operand[i], ind_levels);
3209       if (code == MEM)
3210         find_reloads_address (GET_MODE (recog_operand[i]),
3211                               recog_operand_loc[i],
3212                               XEXP (recog_operand[i], 0),
3213                               &XEXP (recog_operand[i], 0),
3214                               recog_operand[i], ind_levels);
3215       if (code == SUBREG)
3216         recog_operand[i] = *recog_operand_loc[i]
3217           = find_reloads_toplev (recog_operand[i], ind_levels, is_set_dest);
3218       if (code == REG)
3219         {
3220           register int regno = REGNO (recog_operand[i]);
3221           if (reg_equiv_constant[regno] != 0 && !is_set_dest)
3222             recog_operand[i] = *recog_operand_loc[i]
3223               = reg_equiv_constant[regno];
3224 #if 0 /* This might screw code in reload1.c to delete prior output-reload
3225          that feeds this insn.  */
3226           if (reg_equiv_mem[regno] != 0)
3227             recog_operand[i] = *recog_operand_loc[i]
3228               = reg_equiv_mem[regno];
3229 #endif
3230         }
3231       /* All operands are non-reloaded.  */
3232       non_reloaded_operands[n_non_reloaded_operands++] = recog_operand[i];
3233     }
3234 #endif /* no REGISTER_CONSTRAINTS */
3235
3236   /* Determine which part of the insn each reload is needed for,
3237      based on which operand the reload is needed for.
3238      Reloads of entire operands are classified as RELOAD_OTHER.
3239      So are reloads for which a unique purpose is not known.  */
3240
3241   for (i = 0; i < n_reloads; i++)
3242     {
3243       reload_when_needed[i] = RELOAD_OTHER;
3244
3245       if (reload_needed_for[i] != 0 && ! reload_needed_for_multiple[i])
3246         {
3247           int j;
3248           int output_address = 0;
3249           int input_address = 0;
3250           int operand_address = 0;
3251
3252           /* This reload is needed only for the address of something.
3253              Determine whether it is needed for addressing an operand
3254              being reloaded for input, whether it is needed for an
3255              operand being reloaded for output, and whether it is needed
3256              for addressing an operand that won't really be reloaded.
3257
3258              Note that we know that this reload is needed in only one address,
3259              but we have not yet checked for the case where that same address
3260              is used in both input and output reloads.
3261              The following code detects this case.  */
3262
3263           for (j = 0; j < n_reloads; j++)
3264             if (reload_needed_for[i] == reload_in[j]
3265                 || reload_needed_for[i] == reload_out[j])
3266               {
3267                 if (reload_optional[j])
3268                   operand_address = 1;
3269                 else
3270                   {
3271                     if (reload_needed_for[i] == reload_in[j])
3272                       input_address = 1;
3273                     if (reload_needed_for[i] == reload_out[j])
3274                       output_address = 1;
3275                   }
3276               }
3277           /* Don't ignore memrefs without optional reloads.  */
3278           for (j = 0; j < n_non_reloaded_operands; j++)
3279             if (reload_needed_for[i] == non_reloaded_operands[j])
3280               operand_address = 1;
3281
3282           /* If it is needed for only one of those, record which one.  */
3283
3284           if (input_address && ! output_address && ! operand_address)
3285             reload_when_needed[i] = RELOAD_FOR_INPUT_RELOAD_ADDRESS;
3286           if (output_address && ! input_address && ! operand_address)
3287             reload_when_needed[i] = RELOAD_FOR_OUTPUT_RELOAD_ADDRESS;
3288           if (operand_address && ! input_address && ! output_address)
3289             reload_when_needed[i] = RELOAD_FOR_OPERAND_ADDRESS;
3290
3291           /* Indicate those RELOAD_OTHER reloads which, though they have
3292              0 for reload_output, still cannot overlap an output reload.  */
3293
3294           if (output_address && reload_when_needed[i] == RELOAD_OTHER)
3295             reload_needed_for_multiple[i] = 1;
3296
3297           /* If we have earlyclobbers, make sure nothing overlaps them.  */
3298           if (n_earlyclobbers > 0)
3299             {
3300               reload_when_needed[i] = RELOAD_OTHER;
3301               reload_needed_for_multiple[i] = 1;
3302             }
3303         }
3304     }
3305
3306   /* Perhaps an output reload can be combined with another
3307      to reduce needs by one.  */
3308   if (!goal_earlyclobber)
3309     combine_reloads ();
3310 }
3311
3312 /* Return 1 if alternative number ALTNUM in constraint-string CONSTRAINT
3313    accepts a memory operand with constant address.  */
3314
3315 static int
3316 alternative_allows_memconst (constraint, altnum)
3317      char *constraint;
3318      int altnum;
3319 {
3320   register int c;
3321   /* Skip alternatives before the one requested.  */
3322   while (altnum > 0)
3323     {
3324       while (*constraint++ != ',');
3325       altnum--;
3326     }
3327   /* Scan the requested alternative for 'm' or 'o'.
3328      If one of them is present, this alternative accepts memory constants.  */
3329   while ((c = *constraint++) && c != ',' && c != '#')
3330     if (c == 'm' || c == 'o')
3331       return 1;
3332   return 0;
3333 }
3334 \f
3335 /* Scan X for memory references and scan the addresses for reloading.
3336    Also checks for references to "constant" regs that we want to eliminate
3337    and replaces them with the values they stand for.
3338    We may alter X destructively if it contains a reference to such.
3339    If X is just a constant reg, we return the equivalent value
3340    instead of X.
3341
3342    IND_LEVELS says how many levels of indirect addressing this machine
3343    supports.
3344
3345    IS_SET_DEST is true if X is the destination of a SET, which is not
3346    appropriate to be replaced by a constant.  */
3347
3348 static rtx
3349 find_reloads_toplev (x, ind_levels, is_set_dest)
3350      rtx x;
3351      int ind_levels;
3352      int is_set_dest;
3353 {
3354   register RTX_CODE code = GET_CODE (x);
3355
3356   register char *fmt = GET_RTX_FORMAT (code);
3357   register int i;
3358
3359   if (code == REG)
3360     {
3361       /* This code is duplicated for speed in find_reloads.  */
3362       register int regno = REGNO (x);
3363       if (reg_equiv_constant[regno] != 0 && !is_set_dest)
3364         x = reg_equiv_constant[regno];
3365 #if 0
3366 /*  This creates (subreg (mem...)) which would cause an unnecessary
3367     reload of the mem.  */
3368       else if (reg_equiv_mem[regno] != 0)
3369         x = reg_equiv_mem[regno];
3370 #endif
3371       else if (reg_equiv_address[regno] != 0)
3372         {
3373           /* If reg_equiv_address varies, it may be shared, so copy it.  */
3374           rtx addr = reg_equiv_address[regno];
3375
3376           if (rtx_varies_p (addr))
3377             addr = copy_rtx (addr);
3378
3379           x = gen_rtx (MEM, GET_MODE (x), addr);
3380           RTX_UNCHANGING_P (x) = RTX_UNCHANGING_P (regno_reg_rtx[regno]);
3381           find_reloads_address (GET_MODE (x), NULL_PTR,
3382                                 XEXP (x, 0),
3383                                 &XEXP (x, 0), x, ind_levels);
3384         }
3385       return x;
3386     }
3387   if (code == MEM)
3388     {
3389       rtx tem = x;
3390       find_reloads_address (GET_MODE (x), &tem, XEXP (x, 0), &XEXP (x, 0),
3391                             x, ind_levels);
3392       return tem;
3393     }
3394
3395   if (code == SUBREG && GET_CODE (SUBREG_REG (x)) == REG)
3396     {
3397       /* Check for SUBREG containing a REG that's equivalent to a constant.
3398          If the constant has a known value, truncate it right now.
3399          Similarly if we are extracting a single-word of a multi-word
3400          constant.  If the constant is symbolic, allow it to be substituted
3401          normally.  push_reload will strip the subreg later.  If the
3402          constant is VOIDmode, abort because we will lose the mode of
3403          the register (this should never happen because one of the cases
3404          above should handle it).  */
3405
3406       register int regno = REGNO (SUBREG_REG (x));
3407       rtx tem;
3408
3409       if (subreg_lowpart_p (x)
3410           && regno >= FIRST_PSEUDO_REGISTER && reg_renumber[regno] < 0
3411           && reg_equiv_constant[regno] != 0
3412           && (tem = gen_lowpart_common (GET_MODE (x),
3413                                         reg_equiv_constant[regno])) != 0)
3414         return tem;
3415
3416       if (GET_MODE_BITSIZE (GET_MODE (x)) == BITS_PER_WORD
3417           && regno >= FIRST_PSEUDO_REGISTER && reg_renumber[regno] < 0
3418           && reg_equiv_constant[regno] != 0
3419           && (tem = operand_subword (reg_equiv_constant[regno],
3420                                      SUBREG_WORD (x), 0,
3421                                      GET_MODE (SUBREG_REG (x)))) != 0)
3422         return tem;
3423
3424       if (regno >= FIRST_PSEUDO_REGISTER && reg_renumber[regno] < 0
3425           && reg_equiv_constant[regno] != 0
3426           && GET_MODE (reg_equiv_constant[regno]) == VOIDmode)
3427         abort ();
3428
3429       /* If the subreg contains a reg that will be converted to a mem,
3430          convert the subreg to a narrower memref now.
3431          Otherwise, we would get (subreg (mem ...) ...),
3432          which would force reload of the mem.
3433
3434          We also need to do this if there is an equivalent MEM that is
3435          not offsettable.  In that case, alter_subreg would produce an
3436          invalid address on big-endian machines.
3437
3438          For machines that extend byte loads, we must not reload using
3439          a wider mode if we have a paradoxical SUBREG.  find_reloads will
3440          force a reload in that case.  So we should not do anything here.  */
3441
3442       else if (regno >= FIRST_PSEUDO_REGISTER
3443 #if defined(BYTE_LOADS_ZERO_EXTEND) || defined(BYTE_LOADS_SIGN_EXTEND)
3444                && (GET_MODE_SIZE (GET_MODE (x))
3445                    <= GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
3446 #endif
3447                && (reg_equiv_address[regno] != 0
3448                    || (reg_equiv_mem[regno] != 0
3449                        && ! offsettable_memref_p (reg_equiv_mem[regno]))))
3450         {
3451           int offset = SUBREG_WORD (x) * UNITS_PER_WORD;
3452           rtx addr = (reg_equiv_address[regno] ? reg_equiv_address[regno]
3453                       : XEXP (reg_equiv_mem[regno], 0));
3454 #if BYTES_BIG_ENDIAN
3455           int size;
3456           size = GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)));
3457           offset += MIN (size, UNITS_PER_WORD);
3458           size = GET_MODE_SIZE (GET_MODE (x));
3459           offset -= MIN (size, UNITS_PER_WORD);
3460 #endif
3461           addr = plus_constant (addr, offset);
3462           x = gen_rtx (MEM, GET_MODE (x), addr);
3463           RTX_UNCHANGING_P (x) = RTX_UNCHANGING_P (regno_reg_rtx[regno]);
3464           find_reloads_address (GET_MODE (x), NULL_PTR,
3465                                 XEXP (x, 0),
3466                                 &XEXP (x, 0), x, ind_levels);
3467         }
3468
3469     }
3470
3471   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3472     {
3473       if (fmt[i] == 'e')
3474         XEXP (x, i) = find_reloads_toplev (XEXP (x, i),
3475                                            ind_levels, is_set_dest);
3476     }
3477   return x;
3478 }
3479
3480 static rtx
3481 make_memloc (ad, regno)
3482      rtx ad;
3483      int regno;
3484 {
3485   register int i;
3486   rtx tem = reg_equiv_address[regno];
3487   for (i = 0; i < n_memlocs; i++)
3488     if (rtx_equal_p (tem, XEXP (memlocs[i], 0)))
3489       return memlocs[i];
3490
3491   /* If TEM might contain a pseudo, we must copy it to avoid
3492      modifying it when we do the substitution for the reload.  */
3493   if (rtx_varies_p (tem))
3494     tem = copy_rtx (tem);
3495
3496   tem = gen_rtx (MEM, GET_MODE (ad), tem);
3497   RTX_UNCHANGING_P (tem) = RTX_UNCHANGING_P (regno_reg_rtx[regno]);
3498   memlocs[n_memlocs++] = tem;
3499   return tem;
3500 }
3501
3502 /* Record all reloads needed for handling memory address AD
3503    which appears in *LOC in a memory reference to mode MODE
3504    which itself is found in location  *MEMREFLOC.
3505    Note that we take shortcuts assuming that no multi-reg machine mode
3506    occurs as part of an address.
3507
3508    OPERAND is the operand of the insn within which this address appears.
3509
3510    IND_LEVELS says how many levels of indirect addressing this machine
3511    supports.
3512
3513    Value is nonzero if this address is reloaded or replaced as a whole.
3514    This is interesting to the caller if the address is an autoincrement.
3515
3516    Note that there is no verification that the address will be valid after
3517    this routine does its work.  Instead, we rely on the fact that the address
3518    was valid when reload started.  So we need only undo things that reload
3519    could have broken.  These are wrong register types, pseudos not allocated
3520    to a hard register, and frame pointer elimination.  */
3521
3522 static int
3523 find_reloads_address (mode, memrefloc, ad, loc, operand, ind_levels)
3524      enum machine_mode mode;
3525      rtx *memrefloc;
3526      rtx ad;
3527      rtx *loc;
3528      rtx operand;
3529      int ind_levels;
3530 {
3531   register int regno;
3532   rtx tem;
3533
3534   /* If the address is a register, see if it is a legitimate address and
3535      reload if not.  We first handle the cases where we need not reload
3536      or where we must reload in a non-standard way.  */
3537
3538   if (GET_CODE (ad) == REG)
3539     {
3540       regno = REGNO (ad);
3541
3542       if (reg_equiv_constant[regno] != 0
3543           && strict_memory_address_p (mode, reg_equiv_constant[regno]))
3544         {
3545           *loc = ad = reg_equiv_constant[regno];
3546           return 1;
3547         }
3548
3549       else if (reg_equiv_address[regno] != 0)
3550         {
3551           tem = make_memloc (ad, regno);
3552           find_reloads_address (GET_MODE (tem), NULL_PTR, XEXP (tem, 0),
3553                                 &XEXP (tem, 0), operand, ind_levels);
3554           push_reload (tem, NULL_RTX, loc, NULL_PTR, BASE_REG_CLASS,
3555                        GET_MODE (ad), VOIDmode, 0, 0,
3556                        operand);
3557           return 1;
3558         }
3559
3560       else if (reg_equiv_mem[regno] != 0)
3561         {
3562           tem = XEXP (reg_equiv_mem[regno], 0);
3563
3564           /* If we can't indirect any more, a pseudo must be reloaded.
3565              If the pseudo's address in its MEM is a SYMBOL_REF, it
3566              must be reloaded unless indirect_symref_ok.  Otherwise, it
3567              can be reloaded if the address is REG or REG + CONST_INT.  */
3568
3569           if (ind_levels > 0
3570               && ! (GET_CODE (tem) == SYMBOL_REF && ! indirect_symref_ok)
3571               && ((GET_CODE (tem) == REG
3572                    && REGNO (tem) < FIRST_PSEUDO_REGISTER)
3573                   || (GET_CODE (tem) == PLUS
3574                       && GET_CODE (XEXP (tem, 0)) == REG
3575                       && REGNO (XEXP (tem, 0)) < FIRST_PSEUDO_REGISTER
3576                       && GET_CODE (XEXP (tem, 1)) == CONST_INT)))
3577             return 0;
3578         }
3579
3580       /* The only remaining case where we can avoid a reload is if this is a
3581          hard register that is valid as a base register and which is not the
3582          subject of a CLOBBER in this insn.  */
3583
3584       else if (regno < FIRST_PSEUDO_REGISTER && REGNO_OK_FOR_BASE_P (regno)
3585                && ! regno_clobbered_p (regno, this_insn))
3586         return 0;
3587
3588       /* If we do not have one of the cases above, we must do the reload.  */
3589       push_reload (ad, NULL_RTX, loc, NULL_PTR, BASE_REG_CLASS,
3590                    GET_MODE (ad), VOIDmode, 0, 0, operand);
3591       return 1;
3592     }
3593
3594   if (strict_memory_address_p (mode, ad))
3595     {
3596       /* The address appears valid, so reloads are not needed.
3597          But the address may contain an eliminable register.
3598          This can happen because a machine with indirect addressing
3599          may consider a pseudo register by itself a valid address even when
3600          it has failed to get a hard reg.
3601          So do a tree-walk to find and eliminate all such regs.  */
3602
3603       /* But first quickly dispose of a common case.  */
3604       if (GET_CODE (ad) == PLUS
3605           && GET_CODE (XEXP (ad, 1)) == CONST_INT
3606           && GET_CODE (XEXP (ad, 0)) == REG
3607           && reg_equiv_constant[REGNO (XEXP (ad, 0))] == 0)
3608         return 0;
3609
3610       subst_reg_equivs_changed = 0;
3611       *loc = subst_reg_equivs (ad);
3612
3613       if (! subst_reg_equivs_changed)
3614         return 0;
3615
3616       /* Check result for validity after substitution.  */
3617       if (strict_memory_address_p (mode, ad))
3618         return 0;
3619     }
3620
3621   /* The address is not valid.  We have to figure out why.  One possibility
3622      is that it is itself a MEM.  This can happen when the frame pointer is
3623      being eliminated, a pseudo is not allocated to a hard register, and the
3624      offset between the frame and stack pointers is not its initial value.
3625      In that case the pseudo will have been replaced by a MEM referring to
3626      the stack pointer.  */
3627   if (GET_CODE (ad) == MEM)
3628     {
3629       /* First ensure that the address in this MEM is valid.  Then, unless
3630          indirect addresses are valid, reload the MEM into a register.  */
3631       tem = ad;
3632       find_reloads_address (GET_MODE (ad), &tem, XEXP (ad, 0), &XEXP (ad, 0),
3633                             operand, ind_levels == 0 ? 0 : ind_levels - 1);
3634
3635       /* If tem was changed, then we must create a new memory reference to
3636          hold it and store it back into memrefloc.  */
3637       if (tem != ad && memrefloc)
3638         {
3639           rtx oldref = *memrefloc;
3640           *memrefloc = copy_rtx (*memrefloc);
3641           copy_replacements (tem, XEXP (*memrefloc, 0));
3642           loc = &XEXP (*memrefloc, 0);
3643           if (operand == oldref)
3644             operand = *memrefloc;
3645         }
3646
3647       /* Check similar cases as for indirect addresses as above except
3648          that we can allow pseudos and a MEM since they should have been
3649          taken care of above.  */
3650
3651       if (ind_levels == 0
3652           || (GET_CODE (XEXP (tem, 0)) == SYMBOL_REF && ! indirect_symref_ok)
3653           || GET_CODE (XEXP (tem, 0)) == MEM
3654           || ! (GET_CODE (XEXP (tem, 0)) == REG
3655                 || (GET_CODE (XEXP (tem, 0)) == PLUS
3656                     && GET_CODE (XEXP (XEXP (tem, 0), 0)) == REG
3657                     && GET_CODE (XEXP (XEXP (tem, 0), 1)) == CONST_INT)))
3658         {
3659           /* Must use TEM here, not AD, since it is the one that will
3660              have any subexpressions reloaded, if needed.  */
3661           push_reload (tem, NULL_RTX, loc, NULL_PTR,
3662                        BASE_REG_CLASS, GET_MODE (tem), VOIDmode, 0,
3663                        0, operand);
3664           return 1;
3665         }
3666       else
3667         return 0;
3668     }
3669
3670   /* If we have address of a stack slot but it's not valid
3671      (displacement is too large), compute the sum in a register.  */
3672   else if (GET_CODE (ad) == PLUS
3673            && (XEXP (ad, 0) == frame_pointer_rtx
3674 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3675                || XEXP (ad, 0) == arg_pointer_rtx
3676 #endif
3677                || XEXP (ad, 0) == stack_pointer_rtx)
3678            && GET_CODE (XEXP (ad, 1)) == CONST_INT)
3679     {
3680       /* Unshare the MEM rtx so we can safely alter it.  */
3681       if (memrefloc)
3682         {
3683           rtx oldref = *memrefloc;
3684           *memrefloc = copy_rtx (*memrefloc);
3685           loc = &XEXP (*memrefloc, 0);
3686           if (operand == oldref)
3687             operand = *memrefloc;
3688         }
3689       if (double_reg_address_ok)
3690         {
3691           /* Unshare the sum as well.  */
3692           *loc = ad = copy_rtx (ad);
3693           /* Reload the displacement into an index reg.
3694              We assume the frame pointer or arg pointer is a base reg.  */
3695           find_reloads_address_part (XEXP (ad, 1), &XEXP (ad, 1),
3696                                      INDEX_REG_CLASS, GET_MODE (ad), operand,
3697                                      ind_levels);
3698         }
3699       else
3700         {
3701           /* If the sum of two regs is not necessarily valid,
3702              reload the sum into a base reg.
3703              That will at least work.  */
3704           find_reloads_address_part (ad, loc, BASE_REG_CLASS, Pmode,
3705                                      operand, ind_levels);
3706         }
3707       return 1;
3708     }
3709
3710   /* If we have an indexed stack slot, there are three possible reasons why
3711      it might be invalid: The index might need to be reloaded, the address
3712      might have been made by frame pointer elimination and hence have a
3713      constant out of range, or both reasons might apply.
3714
3715      We can easily check for an index needing reload, but even if that is the
3716      case, we might also have an invalid constant.  To avoid making the
3717      conservative assumption and requiring two reloads, we see if this address
3718      is valid when not interpreted strictly.  If it is, the only problem is
3719      that the index needs a reload and find_reloads_address_1 will take care
3720      of it.
3721
3722      There is still a case when we might generate an extra reload,
3723      however.  In certain cases eliminate_regs will return a MEM for a REG
3724      (see the code there for details).  In those cases, memory_address_p
3725      applied to our address will return 0 so we will think that our offset
3726      must be too large.  But it might indeed be valid and the only problem
3727      is that a MEM is present where a REG should be.  This case should be
3728      very rare and there doesn't seem to be any way to avoid it.
3729
3730      If we decide to do something here, it must be that
3731      `double_reg_address_ok' is true and that this address rtl was made by
3732      eliminate_regs.  We generate a reload of the fp/sp/ap + constant and
3733      rework the sum so that the reload register will be added to the index.
3734      This is safe because we know the address isn't shared.
3735
3736      We check for fp/ap/sp as both the first and second operand of the
3737      innermost PLUS.  */
3738
3739   else if (GET_CODE (ad) == PLUS && GET_CODE (XEXP (ad, 1)) == CONST_INT
3740            && GET_CODE (XEXP (ad, 0)) == PLUS
3741            && (XEXP (XEXP (ad, 0), 0) == frame_pointer_rtx
3742 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3743                || XEXP (XEXP (ad, 0), 0) == arg_pointer_rtx
3744 #endif
3745                || XEXP (XEXP (ad, 0), 0) == stack_pointer_rtx)
3746            && ! memory_address_p (mode, ad))
3747     {
3748       *loc = ad = gen_rtx (PLUS, GET_MODE (ad),
3749                            plus_constant (XEXP (XEXP (ad, 0), 0),
3750                                           INTVAL (XEXP (ad, 1))),
3751                            XEXP (XEXP (ad, 0), 1));
3752       find_reloads_address_part (XEXP (ad, 0), &XEXP (ad, 0), BASE_REG_CLASS,
3753                                  GET_MODE (ad), operand, ind_levels);
3754       find_reloads_address_1 (XEXP (ad, 1), 1, &XEXP (ad, 1), operand, 0);
3755
3756       return 1;
3757     }
3758
3759   else if (GET_CODE (ad) == PLUS && GET_CODE (XEXP (ad, 1)) == CONST_INT
3760            && GET_CODE (XEXP (ad, 0)) == PLUS
3761            && (XEXP (XEXP (ad, 0), 1) == frame_pointer_rtx
3762 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3763                || XEXP (XEXP (ad, 0), 1) == arg_pointer_rtx
3764 #endif
3765                || XEXP (XEXP (ad, 0), 1) == stack_pointer_rtx)
3766            && ! memory_address_p (mode, ad))
3767     {
3768       *loc = ad = gen_rtx (PLUS, GET_MODE (ad),
3769                            plus_constant (XEXP (XEXP (ad, 0), 1),
3770                                           INTVAL (XEXP (ad, 1))),
3771                            XEXP (XEXP (ad, 0), 0));
3772       find_reloads_address_part (XEXP (ad, 0), &XEXP (ad, 0), BASE_REG_CLASS,
3773                                  GET_MODE (ad), operand, ind_levels);
3774       find_reloads_address_1 (XEXP (ad, 1), 1, &XEXP (ad, 1), operand, 0);
3775
3776       return 1;
3777     }
3778
3779   /* See if address becomes valid when an eliminable register
3780      in a sum is replaced.  */
3781
3782   tem = ad;
3783   if (GET_CODE (ad) == PLUS)
3784     tem = subst_indexed_address (ad);
3785   if (tem != ad && strict_memory_address_p (mode, tem))
3786     {
3787       /* Ok, we win that way.  Replace any additional eliminable
3788          registers.  */
3789
3790       subst_reg_equivs_changed = 0;
3791       tem = subst_reg_equivs (tem);
3792
3793       /* Make sure that didn't make the address invalid again.  */
3794
3795       if (! subst_reg_equivs_changed || strict_memory_address_p (mode, tem))
3796         {
3797           *loc = tem;
3798           return 0;
3799         }
3800     }
3801
3802   /* If constants aren't valid addresses, reload the constant address
3803      into a register.  */
3804   if (CONSTANT_P (ad) && ! strict_memory_address_p (mode, ad))
3805     {
3806       /* If AD is in address in the constant pool, the MEM rtx may be shared.
3807          Unshare it so we can safely alter it.  */
3808       if (memrefloc && GET_CODE (ad) == SYMBOL_REF
3809           && CONSTANT_POOL_ADDRESS_P (ad))
3810         {
3811           rtx oldref = *memrefloc;
3812           *memrefloc = copy_rtx (*memrefloc);
3813           loc = &XEXP (*memrefloc, 0);
3814           if (operand == oldref)
3815             operand = *memrefloc;
3816         }
3817
3818       find_reloads_address_part (ad, loc, BASE_REG_CLASS, Pmode, operand,
3819                                  ind_levels);
3820       return 1;
3821     }
3822
3823   return find_reloads_address_1 (ad, 0, loc, operand, ind_levels);
3824 }
3825 \f
3826 /* Find all pseudo regs appearing in AD
3827    that are eliminable in favor of equivalent values
3828    and do not have hard regs; replace them by their equivalents.  */
3829
3830 static rtx
3831 subst_reg_equivs (ad)
3832      rtx ad;
3833 {
3834   register RTX_CODE code = GET_CODE (ad);
3835   register int i;
3836   register char *fmt;
3837
3838   switch (code)
3839     {
3840     case HIGH:
3841     case CONST_INT:
3842     case CONST:
3843     case CONST_DOUBLE:
3844     case SYMBOL_REF:
3845     case LABEL_REF:
3846     case PC:
3847     case CC0:
3848       return ad;
3849
3850     case REG:
3851       {
3852         register int regno = REGNO (ad);
3853
3854         if (reg_equiv_constant[regno] != 0)
3855           {
3856             subst_reg_equivs_changed = 1;
3857             return reg_equiv_constant[regno];
3858           }
3859       }
3860       return ad;
3861
3862     case PLUS:
3863       /* Quickly dispose of a common case.  */
3864       if (XEXP (ad, 0) == frame_pointer_rtx
3865           && GET_CODE (XEXP (ad, 1)) == CONST_INT)
3866         return ad;
3867     }
3868
3869   fmt = GET_RTX_FORMAT (code);
3870   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3871     if (fmt[i] == 'e')
3872       XEXP (ad, i) = subst_reg_equivs (XEXP (ad, i));
3873   return ad;
3874 }
3875 \f
3876 /* Compute the sum of X and Y, making canonicalizations assumed in an
3877    address, namely: sum constant integers, surround the sum of two
3878    constants with a CONST, put the constant as the second operand, and
3879    group the constant on the outermost sum.
3880
3881    This routine assumes both inputs are already in canonical form.  */
3882
3883 rtx
3884 form_sum (x, y)
3885      rtx x, y;
3886 {
3887   rtx tem;
3888
3889   if (GET_CODE (x) == CONST_INT)
3890     return plus_constant (y, INTVAL (x));
3891   else if (GET_CODE (y) == CONST_INT)
3892     return plus_constant (x, INTVAL (y));
3893   else if (CONSTANT_P (x))
3894     tem = x, x = y, y = tem;
3895
3896   if (GET_CODE (x) == PLUS && CONSTANT_P (XEXP (x, 1)))
3897     return form_sum (XEXP (x, 0), form_sum (XEXP (x, 1), y));
3898
3899   /* Note that if the operands of Y are specified in the opposite
3900      order in the recursive calls below, infinite recursion will occur.  */
3901   if (GET_CODE (y) == PLUS && CONSTANT_P (XEXP (y, 1)))
3902     return form_sum (form_sum (x, XEXP (y, 0)), XEXP (y, 1));
3903
3904   /* If both constant, encapsulate sum.  Otherwise, just form sum.  A
3905      constant will have been placed second.  */
3906   if (CONSTANT_P (x) && CONSTANT_P (y))
3907     {
3908       if (GET_CODE (x) == CONST)
3909         x = XEXP (x, 0);
3910       if (GET_CODE (y) == CONST)
3911         y = XEXP (y, 0);
3912
3913       return gen_rtx (CONST, VOIDmode, gen_rtx (PLUS, Pmode, x, y));
3914     }
3915
3916   return gen_rtx (PLUS, Pmode, x, y);
3917 }
3918 \f
3919 /* If ADDR is a sum containing a pseudo register that should be
3920    replaced with a constant (from reg_equiv_constant),
3921    return the result of doing so, and also apply the associative
3922    law so that the result is more likely to be a valid address.
3923    (But it is not guaranteed to be one.)
3924
3925    Note that at most one register is replaced, even if more are
3926    replaceable.  Also, we try to put the result into a canonical form
3927    so it is more likely to be a valid address.
3928
3929    In all other cases, return ADDR.  */
3930
3931 static rtx
3932 subst_indexed_address (addr)
3933      rtx addr;
3934 {
3935   rtx op0 = 0, op1 = 0, op2 = 0;
3936   rtx tem;
3937   int regno;
3938
3939   if (GET_CODE (addr) == PLUS)
3940     {
3941       /* Try to find a register to replace.  */
3942       op0 = XEXP (addr, 0), op1 = XEXP (addr, 1), op2 = 0;
3943       if (GET_CODE (op0) == REG
3944           && (regno = REGNO (op0)) >= FIRST_PSEUDO_REGISTER
3945           && reg_renumber[regno] < 0
3946           && reg_equiv_constant[regno] != 0)
3947         op0 = reg_equiv_constant[regno];
3948       else if (GET_CODE (op1) == REG
3949           && (regno = REGNO (op1)) >= FIRST_PSEUDO_REGISTER
3950           && reg_renumber[regno] < 0
3951           && reg_equiv_constant[regno] != 0)
3952         op1 = reg_equiv_constant[regno];
3953       else if (GET_CODE (op0) == PLUS
3954                && (tem = subst_indexed_address (op0)) != op0)
3955         op0 = tem;
3956       else if (GET_CODE (op1) == PLUS
3957                && (tem = subst_indexed_address (op1)) != op1)
3958         op1 = tem;
3959       else
3960         return addr;
3961
3962       /* Pick out up to three things to add.  */
3963       if (GET_CODE (op1) == PLUS)
3964         op2 = XEXP (op1, 1), op1 = XEXP (op1, 0);
3965       else if (GET_CODE (op0) == PLUS)
3966         op2 = op1, op1 = XEXP (op0, 1), op0 = XEXP (op0, 0);
3967
3968       /* Compute the sum.  */
3969       if (op2 != 0)
3970         op1 = form_sum (op1, op2);
3971       if (op1 != 0)
3972         op0 = form_sum (op0, op1);
3973
3974       return op0;
3975     }
3976   return addr;
3977 }
3978 \f
3979 /* Record the pseudo registers we must reload into hard registers
3980    in a subexpression of a would-be memory address, X.
3981    (This function is not called if the address we find is strictly valid.)
3982    CONTEXT = 1 means we are considering regs as index regs,
3983    = 0 means we are considering them as base regs.
3984
3985    OPERAND is the operand of the insn within which this address appears.
3986
3987    IND_LEVELS says how many levels of indirect addressing are
3988    supported at this point in the address.
3989
3990    We return nonzero if X, as a whole, is reloaded or replaced.  */
3991
3992 /* Note that we take shortcuts assuming that no multi-reg machine mode
3993    occurs as part of an address.
3994    Also, this is not fully machine-customizable; it works for machines
3995    such as vaxes and 68000's and 32000's, but other possible machines
3996    could have addressing modes that this does not handle right.  */
3997
3998 static int
3999 find_reloads_address_1 (x, context, loc, operand, ind_levels)
4000      rtx x;
4001      int context;
4002      rtx *loc;
4003      rtx operand;
4004      int ind_levels;
4005 {
4006   register RTX_CODE code = GET_CODE (x);
4007
4008   if (code == PLUS)
4009     {
4010       register rtx op0 = XEXP (x, 0);
4011       register rtx op1 = XEXP (x, 1);
4012       register RTX_CODE code0 = GET_CODE (op0);
4013       register RTX_CODE code1 = GET_CODE (op1);
4014       if (code0 == MULT || code0 == SIGN_EXTEND || code1 == MEM)
4015         {
4016           find_reloads_address_1 (op0, 1, &XEXP (x, 0), operand, ind_levels);
4017           find_reloads_address_1 (op1, 0, &XEXP (x, 1), operand, ind_levels);
4018         }
4019       else if (code1 == MULT || code1 == SIGN_EXTEND || code0 == MEM)
4020         {
4021           find_reloads_address_1 (op0, 0, &XEXP (x, 0), operand, ind_levels);
4022           find_reloads_address_1 (op1, 1, &XEXP (x, 1), operand, ind_levels);
4023         }
4024       else if (code0 == CONST_INT || code0 == CONST
4025                || code0 == SYMBOL_REF || code0 == LABEL_REF)
4026         {
4027           find_reloads_address_1 (op1, 0, &XEXP (x, 1), operand, ind_levels);
4028         }
4029       else if (code1 == CONST_INT || code1 == CONST
4030                || code1 == SYMBOL_REF || code1 == LABEL_REF)
4031         {
4032           find_reloads_address_1 (op0, 0, &XEXP (x, 0), operand, ind_levels);
4033         }
4034       else if (code0 == REG && code1 == REG)
4035         {
4036           if (REG_OK_FOR_INDEX_P (op0)
4037               && REG_OK_FOR_BASE_P (op1))
4038             return 0;
4039           else if (REG_OK_FOR_INDEX_P (op1)
4040               && REG_OK_FOR_BASE_P (op0))
4041             return 0;
4042           else if (REG_OK_FOR_BASE_P (op1))
4043             find_reloads_address_1 (op0, 1, &XEXP (x, 0), operand, ind_levels);
4044           else if (REG_OK_FOR_BASE_P (op0))
4045             find_reloads_address_1 (op1, 1, &XEXP (x, 1), operand, ind_levels);
4046           else if (REG_OK_FOR_INDEX_P (op1))
4047             find_reloads_address_1 (op0, 0, &XEXP (x, 0), operand, ind_levels);
4048           else if (REG_OK_FOR_INDEX_P (op0))
4049             find_reloads_address_1 (op1, 0, &XEXP (x, 1), operand, ind_levels);
4050           else
4051             {
4052               find_reloads_address_1 (op0, 1, &XEXP (x, 0), operand,
4053                                       ind_levels);
4054               find_reloads_address_1 (op1, 0, &XEXP (x, 1), operand,
4055                                       ind_levels);
4056             }
4057         }
4058       else if (code0 == REG)
4059         {
4060           find_reloads_address_1 (op0, 1, &XEXP (x, 0), operand, ind_levels);
4061           find_reloads_address_1 (op1, 0, &XEXP (x, 1), operand, ind_levels);
4062         }
4063       else if (code1 == REG)
4064         {
4065           find_reloads_address_1 (op1, 1, &XEXP (x, 1), operand, ind_levels);
4066           find_reloads_address_1 (op0, 0, &XEXP (x, 0), operand, ind_levels);
4067         }
4068     }
4069   else if (code == POST_INC || code == POST_DEC
4070            || code == PRE_INC || code == PRE_DEC)
4071     {
4072       if (GET_CODE (XEXP (x, 0)) == REG)
4073         {
4074           register int regno = REGNO (XEXP (x, 0));
4075           int value = 0;
4076           rtx x_orig = x;
4077
4078           /* A register that is incremented cannot be constant!  */
4079           if (regno >= FIRST_PSEUDO_REGISTER
4080               && reg_equiv_constant[regno] != 0)
4081             abort ();
4082
4083           /* Handle a register that is equivalent to a memory location
4084              which cannot be addressed directly.  */
4085           if (reg_equiv_address[regno] != 0)
4086             {
4087               rtx tem = make_memloc (XEXP (x, 0), regno);
4088               /* First reload the memory location's address.  */
4089               find_reloads_address (GET_MODE (tem), 0, XEXP (tem, 0),
4090                                     &XEXP (tem, 0), operand, ind_levels);
4091               /* Put this inside a new increment-expression.  */
4092               x = gen_rtx (GET_CODE (x), GET_MODE (x), tem);
4093               /* Proceed to reload that, as if it contained a register.  */
4094             }
4095
4096           /* If we have a hard register that is ok as an index,
4097              don't make a reload.  If an autoincrement of a nice register
4098              isn't "valid", it must be that no autoincrement is "valid".
4099              If that is true and something made an autoincrement anyway,
4100              this must be a special context where one is allowed.
4101              (For example, a "push" instruction.)
4102              We can't improve this address, so leave it alone.  */
4103
4104           /* Otherwise, reload the autoincrement into a suitable hard reg
4105              and record how much to increment by.  */
4106
4107           if (reg_renumber[regno] >= 0)
4108             regno = reg_renumber[regno];
4109           if ((regno >= FIRST_PSEUDO_REGISTER
4110                || !(context ? REGNO_OK_FOR_INDEX_P (regno)
4111                     : REGNO_OK_FOR_BASE_P (regno))))
4112             {
4113               register rtx link;
4114
4115               int reloadnum
4116                 = push_reload (x, NULL_RTX, loc, NULL_PTR,
4117                                context ? INDEX_REG_CLASS : BASE_REG_CLASS,
4118                                GET_MODE (x), GET_MODE (x), VOIDmode, 0, operand);
4119               reload_inc[reloadnum]
4120                 = find_inc_amount (PATTERN (this_insn), XEXP (x_orig, 0));
4121
4122               value = 1;
4123
4124 #ifdef AUTO_INC_DEC
4125               /* Update the REG_INC notes.  */
4126
4127               for (link = REG_NOTES (this_insn);
4128                    link; link = XEXP (link, 1))
4129                 if (REG_NOTE_KIND (link) == REG_INC
4130                     && REGNO (XEXP (link, 0)) == REGNO (XEXP (x_orig, 0)))
4131                   push_replacement (&XEXP (link, 0), reloadnum, VOIDmode);
4132 #endif
4133             }
4134           return value;
4135         }
4136       else if (GET_CODE (XEXP (x, 0)) == MEM)
4137         {
4138           /* This is probably the result of a substitution, by eliminate_regs,
4139              of an equivalent address for a pseudo that was not allocated to a
4140              hard register.  Verify that the specified address is valid and
4141              reload it into a register.  */
4142           rtx tem = XEXP (x, 0);
4143           register rtx link;
4144           int reloadnum;
4145
4146           /* Since we know we are going to reload this item, don't decrement
4147              for the indirection level.
4148
4149              Note that this is actually conservative:  it would be slightly
4150              more efficient to use the value of SPILL_INDIRECT_LEVELS from
4151              reload1.c here.  */
4152           find_reloads_address (GET_MODE (x), &XEXP (x, 0),
4153                                 XEXP (XEXP (x, 0), 0), &XEXP (XEXP (x, 0), 0),
4154                                 operand, ind_levels);
4155
4156           reloadnum = push_reload (x, NULL_RTX, loc, NULL_PTR,
4157                                    context ? INDEX_REG_CLASS : BASE_REG_CLASS,
4158                                    GET_MODE (x), VOIDmode, 0, 0, operand);
4159           reload_inc[reloadnum]
4160             = find_inc_amount (PATTERN (this_insn), XEXP (x, 0));
4161
4162           link = FIND_REG_INC_NOTE (this_insn, tem);
4163           if (link != 0)
4164             push_replacement (&XEXP (link, 0), reloadnum, VOIDmode);
4165
4166           return 1;
4167         }
4168     }
4169   else if (code == MEM)
4170     {
4171       /* This is probably the result of a substitution, by eliminate_regs,
4172          of an equivalent address for a pseudo that was not allocated to a
4173          hard register.  Verify that the specified address is valid and reload
4174          it into a register.
4175
4176          Since we know we are going to reload this item, don't decrement
4177          for the indirection level.
4178
4179          Note that this is actually conservative:  it would be slightly more
4180          efficient to use the value of SPILL_INDIRECT_LEVELS from
4181          reload1.c here.  */
4182
4183       find_reloads_address (GET_MODE (x), loc, XEXP (x, 0), &XEXP (x, 0),
4184                             operand, ind_levels);
4185
4186       push_reload (*loc, NULL_RTX, loc, NULL_PTR,
4187                    context ? INDEX_REG_CLASS : BASE_REG_CLASS,
4188                    GET_MODE (x), VOIDmode, 0, 0, operand);
4189       return 1;
4190     }
4191   else if (code == REG)
4192     {
4193       register int regno = REGNO (x);
4194
4195       if (reg_equiv_constant[regno] != 0)
4196         {
4197           find_reloads_address_part (reg_equiv_constant[regno], loc,
4198                                      (context ? INDEX_REG_CLASS
4199                                       : BASE_REG_CLASS),
4200                                      GET_MODE (x), operand, ind_levels);
4201           return 1;
4202         }
4203
4204 #if 0 /* This might screw code in reload1.c to delete prior output-reload
4205          that feeds this insn.  */
4206       if (reg_equiv_mem[regno] != 0)
4207         {
4208           push_reload (reg_equiv_mem[regno], NULL_RTX, loc, NULL_PTR,
4209                        context ? INDEX_REG_CLASS : BASE_REG_CLASS,
4210                        GET_MODE (x), VOIDmode, 0, 0, operand);
4211           return 1;
4212         }
4213 #endif
4214       if (reg_equiv_address[regno] != 0)
4215         {
4216           x = make_memloc (x, regno);
4217           find_reloads_address (GET_MODE (x), 0, XEXP (x, 0), &XEXP (x, 0),
4218                                 operand, ind_levels);
4219         }
4220
4221       if (reg_renumber[regno] >= 0)
4222         regno = reg_renumber[regno];
4223       if ((regno >= FIRST_PSEUDO_REGISTER
4224            || !(context ? REGNO_OK_FOR_INDEX_P (regno)
4225                 : REGNO_OK_FOR_BASE_P (regno))))
4226         {
4227           push_reload (x, NULL_RTX, loc, NULL_PTR,
4228                        context ? INDEX_REG_CLASS : BASE_REG_CLASS,
4229                        GET_MODE (x), VOIDmode, 0, 0, operand);
4230           return 1;
4231         }
4232
4233       /* If a register appearing in an address is the subject of a CLOBBER
4234          in this insn, reload it into some other register to be safe.
4235          The CLOBBER is supposed to make the register unavailable
4236          from before this insn to after it.  */
4237       if (regno_clobbered_p (regno, this_insn))
4238         {
4239           push_reload (x, NULL_RTX, loc, NULL_PTR,
4240                        context ? INDEX_REG_CLASS : BASE_REG_CLASS,
4241                        GET_MODE (x), VOIDmode, 0, 0, operand);
4242           return 1;
4243         }
4244     }
4245   else
4246     {
4247       register char *fmt = GET_RTX_FORMAT (code);
4248       register int i;
4249       for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4250         {
4251           if (fmt[i] == 'e')
4252             find_reloads_address_1 (XEXP (x, i), context, &XEXP (x, i),
4253                                     operand, ind_levels);
4254         }
4255     }
4256
4257   return 0;
4258 }
4259 \f
4260 /* X, which is found at *LOC, is a part of an address that needs to be
4261    reloaded into a register of class CLASS.  If X is a constant, or if
4262    X is a PLUS that contains a constant, check that the constant is a
4263    legitimate operand and that we are supposed to be able to load
4264    it into the register.
4265
4266    If not, force the constant into memory and reload the MEM instead.
4267
4268    MODE is the mode to use, in case X is an integer constant.
4269
4270    NEEDED_FOR says which operand this reload is needed for.
4271
4272    IND_LEVELS says how many levels of indirect addressing this machine
4273    supports.  */
4274
4275 static void
4276 find_reloads_address_part (x, loc, class, mode, needed_for, ind_levels)
4277      rtx x;
4278      rtx *loc;
4279      enum reg_class class;
4280      enum machine_mode mode;
4281      rtx needed_for;
4282      int ind_levels;
4283 {
4284   if (CONSTANT_P (x)
4285       && (! LEGITIMATE_CONSTANT_P (x)
4286           || PREFERRED_RELOAD_CLASS (x, class) == NO_REGS))
4287     {
4288       rtx tem = x = force_const_mem (mode, x);
4289       find_reloads_address (mode, &tem, XEXP (tem, 0), &XEXP (tem, 0),
4290                             needed_for, ind_levels);
4291     }
4292
4293   else if (GET_CODE (x) == PLUS
4294            && CONSTANT_P (XEXP (x, 1))
4295            && (! LEGITIMATE_CONSTANT_P (XEXP (x, 1))
4296                || PREFERRED_RELOAD_CLASS (XEXP (x, 1), class) == NO_REGS))
4297     {
4298       rtx tem = force_const_mem (GET_MODE (x), XEXP (x, 1));
4299
4300       x = gen_rtx (PLUS, GET_MODE (x), XEXP (x, 0), tem);
4301       find_reloads_address (mode, &tem, XEXP (tem, 0), &XEXP (tem, 0),
4302                             needed_for, ind_levels);
4303     }
4304
4305   push_reload (x, NULL_RTX, loc, NULL_PTR, class,
4306                mode, VOIDmode, 0, 0, needed_for);
4307 }
4308 \f
4309 /* Substitute into X the registers into which we have reloaded
4310    the things that need reloading.  The array `replacements'
4311    says contains the locations of all pointers that must be changed
4312    and says what to replace them with.
4313
4314    Return the rtx that X translates into; usually X, but modified.  */
4315
4316 void
4317 subst_reloads ()
4318 {
4319   register int i;
4320
4321   for (i = 0; i < n_replacements; i++)
4322     {
4323       register struct replacement *r = &replacements[i];
4324       register rtx reloadreg = reload_reg_rtx[r->what];
4325       if (reloadreg)
4326         {
4327           /* Encapsulate RELOADREG so its machine mode matches what
4328              used to be there.  */
4329           if (GET_MODE (reloadreg) != r->mode && r->mode != VOIDmode)
4330             reloadreg = gen_rtx (REG, r->mode, REGNO (reloadreg));
4331
4332           /* If we are putting this into a SUBREG and RELOADREG is a
4333              SUBREG, we would be making nested SUBREGs, so we have to fix
4334              this up.  Note that r->where == &SUBREG_REG (*r->subreg_loc).  */
4335
4336           if (r->subreg_loc != 0 && GET_CODE (reloadreg) == SUBREG)
4337             {
4338               if (GET_MODE (*r->subreg_loc)
4339                   == GET_MODE (SUBREG_REG (reloadreg)))
4340                 *r->subreg_loc = SUBREG_REG (reloadreg);
4341               else
4342                 {
4343                   *r->where = SUBREG_REG (reloadreg);
4344                   SUBREG_WORD (*r->subreg_loc) += SUBREG_WORD (reloadreg);
4345                 }
4346             }
4347           else
4348             *r->where = reloadreg;
4349         }
4350       /* If reload got no reg and isn't optional, something's wrong.  */
4351       else if (! reload_optional[r->what])
4352         abort ();
4353     }
4354 }
4355 \f
4356 /* Make a copy of any replacements being done into X and move those copies
4357    to locations in Y, a copy of X.  We only look at the highest level of
4358    the RTL.  */
4359
4360 void
4361 copy_replacements (x, y)
4362      rtx x;
4363      rtx y;
4364 {
4365   int i, j;
4366   enum rtx_code code = GET_CODE (x);
4367   char *fmt = GET_RTX_FORMAT (code);
4368   struct replacement *r;
4369
4370   /* We can't support X being a SUBREG because we might then need to know its
4371      location if something inside it was replaced.  */
4372   if (code == SUBREG)
4373     abort ();
4374
4375   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4376     if (fmt[i] == 'e')
4377       for (j = 0; j < n_replacements; j++)
4378         {
4379           if (replacements[j].subreg_loc == &XEXP (x, i))
4380             {
4381               r = &replacements[n_replacements++];
4382               r->where = replacements[j].where;
4383               r->subreg_loc = &XEXP (y, i);
4384               r->what = replacements[j].what;
4385               r->mode = replacements[j].mode;
4386             }
4387           else if (replacements[j].where == &XEXP (x, i))
4388             {
4389               r = &replacements[n_replacements++];
4390               r->where = &XEXP (y, i);
4391               r->subreg_loc = 0;
4392               r->what = replacements[j].what;
4393               r->mode = replacements[j].mode;
4394             }
4395         }
4396 }
4397 \f
4398 /* If LOC was scheduled to be replaced by something, return the replacement.
4399    Otherwise, return *LOC.  */
4400
4401 rtx
4402 find_replacement (loc)
4403      rtx *loc;
4404 {
4405   struct replacement *r;
4406
4407   for (r = &replacements[0]; r < &replacements[n_replacements]; r++)
4408     {
4409       rtx reloadreg = reload_reg_rtx[r->what];
4410
4411       if (reloadreg && r->where == loc)
4412         {
4413           if (r->mode != VOIDmode && GET_MODE (reloadreg) != r->mode)
4414             reloadreg = gen_rtx (REG, r->mode, REGNO (reloadreg));
4415
4416           return reloadreg;
4417         }
4418       else if (reloadreg && r->subreg_loc == loc)
4419         {
4420           /* RELOADREG must be either a REG or a SUBREG.
4421
4422              ??? Is it actually still ever a SUBREG?  If so, why?  */
4423
4424           if (GET_CODE (reloadreg) == REG)
4425             return gen_rtx (REG, GET_MODE (*loc),
4426                             REGNO (reloadreg) + SUBREG_WORD (*loc));
4427           else if (GET_MODE (reloadreg) == GET_MODE (*loc))
4428             return reloadreg;
4429           else
4430             return gen_rtx (SUBREG, GET_MODE (*loc), SUBREG_REG (reloadreg),
4431                             SUBREG_WORD (reloadreg) + SUBREG_WORD (*loc));
4432         }
4433     }
4434
4435   return *loc;
4436 }
4437 \f
4438 /* Return nonzero if register in range [REGNO, ENDREGNO)
4439    appears either explicitly or implicitly in X
4440    other than being stored into.
4441
4442    References contained within the substructure at LOC do not count.
4443    LOC may be zero, meaning don't ignore anything.
4444
4445    This is similar to refers_to_regno_p in rtlanal.c except that we
4446    look at equivalences for pseudos that didn't get hard registers.  */
4447
4448 int
4449 refers_to_regno_for_reload_p (regno, endregno, x, loc)
4450      int regno, endregno;
4451      rtx x;
4452      rtx *loc;
4453 {
4454   register int i;
4455   register RTX_CODE code;
4456   register char *fmt;
4457
4458   if (x == 0)
4459     return 0;
4460
4461  repeat:
4462   code = GET_CODE (x);
4463
4464   switch (code)
4465     {
4466     case REG:
4467       i = REGNO (x);
4468
4469       /* If this is a pseudo, a hard register must not have been allocated.
4470          X must therefore either be a constant or be in memory.  */
4471       if (i >= FIRST_PSEUDO_REGISTER)
4472         {
4473           if (reg_equiv_memory_loc[i])
4474             return refers_to_regno_for_reload_p (regno, endregno,
4475                                                  reg_equiv_memory_loc[i],
4476                                                  NULL_PTR);
4477
4478           if (reg_equiv_constant[i])
4479             return 0;
4480
4481           abort ();
4482         }
4483
4484       return (endregno > i
4485               && regno < i + (i < FIRST_PSEUDO_REGISTER
4486                               ? HARD_REGNO_NREGS (i, GET_MODE (x))
4487                               : 1));
4488
4489     case SUBREG:
4490       /* If this is a SUBREG of a hard reg, we can see exactly which
4491          registers are being modified.  Otherwise, handle normally.  */
4492       if (GET_CODE (SUBREG_REG (x)) == REG
4493           && REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER)
4494         {
4495           int inner_regno = REGNO (SUBREG_REG (x)) + SUBREG_WORD (x);
4496           int inner_endregno
4497             = inner_regno + (inner_regno < FIRST_PSEUDO_REGISTER
4498                              ? HARD_REGNO_NREGS (regno, GET_MODE (x)) : 1);
4499
4500           return endregno > inner_regno && regno < inner_endregno;
4501         }
4502       break;
4503
4504     case CLOBBER:
4505     case SET:
4506       if (&SET_DEST (x) != loc
4507           /* Note setting a SUBREG counts as referring to the REG it is in for
4508              a pseudo but not for hard registers since we can
4509              treat each word individually.  */
4510           && ((GET_CODE (SET_DEST (x)) == SUBREG
4511                && loc != &SUBREG_REG (SET_DEST (x))
4512                && GET_CODE (SUBREG_REG (SET_DEST (x))) == REG
4513                && REGNO (SUBREG_REG (SET_DEST (x))) >= FIRST_PSEUDO_REGISTER
4514                && refers_to_regno_for_reload_p (regno, endregno,
4515                                                 SUBREG_REG (SET_DEST (x)),
4516                                                 loc))
4517               || (GET_CODE (SET_DEST (x)) != REG
4518                   && refers_to_regno_for_reload_p (regno, endregno,
4519                                                    SET_DEST (x), loc))))
4520         return 1;
4521
4522       if (code == CLOBBER || loc == &SET_SRC (x))
4523         return 0;
4524       x = SET_SRC (x);
4525       goto repeat;
4526     }
4527
4528   /* X does not match, so try its subexpressions.  */
4529
4530   fmt = GET_RTX_FORMAT (code);
4531   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4532     {
4533       if (fmt[i] == 'e' && loc != &XEXP (x, i))
4534         {
4535           if (i == 0)
4536             {
4537               x = XEXP (x, 0);
4538               goto repeat;
4539             }
4540           else
4541             if (refers_to_regno_for_reload_p (regno, endregno,
4542                                               XEXP (x, i), loc))
4543               return 1;
4544         }
4545       else if (fmt[i] == 'E')
4546         {
4547           register int j;
4548           for (j = XVECLEN (x, i) - 1; j >=0; j--)
4549             if (loc != &XVECEXP (x, i, j)
4550                 && refers_to_regno_for_reload_p (regno, endregno,
4551                                                  XVECEXP (x, i, j), loc))
4552               return 1;
4553         }
4554     }
4555   return 0;
4556 }
4557
4558 /* Nonzero if modifying X will affect IN.  If X is a register or a SUBREG,
4559    we check if any register number in X conflicts with the relevant register
4560    numbers.  If X is a constant, return 0.  If X is a MEM, return 1 iff IN
4561    contains a MEM (we don't bother checking for memory addresses that can't
4562    conflict because we expect this to be a rare case.
4563
4564    This function is similar to reg_overlap_mention_p in rtlanal.c except
4565    that we look at equivalences for pseudos that didn't get hard registers.  */
4566
4567 int
4568 reg_overlap_mentioned_for_reload_p (x, in)
4569      rtx x, in;
4570 {
4571   int regno, endregno;
4572
4573   if (GET_CODE (x) == SUBREG)
4574     {
4575       regno = REGNO (SUBREG_REG (x));
4576       if (regno < FIRST_PSEUDO_REGISTER)
4577         regno += SUBREG_WORD (x);
4578     }
4579   else if (GET_CODE (x) == REG)
4580     {
4581       regno = REGNO (x);
4582
4583       /* If this is a pseudo, it must not have been assigned a hard register.
4584          Therefore, it must either be in memory or be a constant.  */
4585
4586       if (regno >= FIRST_PSEUDO_REGISTER)
4587         {
4588           if (reg_equiv_memory_loc[regno])
4589             return refers_to_mem_for_reload_p (in);
4590           else if (reg_equiv_constant[regno])
4591             return 0;
4592           abort ();
4593         }
4594     }
4595   else if (CONSTANT_P (x))
4596     return 0;
4597   else if (GET_CODE (x) == MEM)
4598     return refers_to_mem_for_reload_p (in);
4599   else if (GET_CODE (x) == SCRATCH || GET_CODE (x) == PC
4600            || GET_CODE (x) == CC0)
4601     return reg_mentioned_p (x, in);
4602   else
4603     abort ();
4604
4605   endregno = regno + (regno < FIRST_PSEUDO_REGISTER
4606                       ? HARD_REGNO_NREGS (regno, GET_MODE (x)) : 1);
4607
4608   return refers_to_regno_for_reload_p (regno, endregno, in, NULL_PTR);
4609 }
4610
4611 /* Return nonzero if anything in X contains a MEM.  Look also for pseudo
4612    registers.  */
4613
4614 int
4615 refers_to_mem_for_reload_p (x)
4616      rtx x;
4617 {
4618   char *fmt;
4619   int i;
4620
4621   if (GET_CODE (x) == MEM)
4622     return 1;
4623
4624   if (GET_CODE (x) == REG)
4625     return (REGNO (x) >= FIRST_PSEUDO_REGISTER
4626             && reg_equiv_memory_loc[REGNO (x)]);
4627
4628   fmt = GET_RTX_FORMAT (GET_CODE (x));
4629   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
4630     if (fmt[i] == 'e'
4631         && (GET_CODE (XEXP (x, i)) == MEM
4632             || refers_to_mem_for_reload_p (XEXP (x, i))))
4633       return 1;
4634
4635   return 0;
4636 }
4637 \f
4638 #if 0
4639
4640 /* [[This function is currently obsolete, now that volatility
4641    is represented by a special bit `volatil' so VOLATILE is never used;
4642    and UNCHANGING has never been brought into use.]]
4643
4644    Alter X by eliminating all VOLATILE and UNCHANGING expressions.
4645    Each of them is replaced by its operand.
4646    Thus, (PLUS (VOLATILE (MEM (REG 5))) (CONST_INT 4))
4647    becomes (PLUS (MEM (REG 5)) (CONST_INT 4)).
4648
4649    If X is itself a VOLATILE expression,
4650    we return the expression that should replace it
4651    but we do not modify X.  */
4652
4653 static rtx
4654 forget_volatility (x)
4655      register rtx x;
4656 {
4657   enum rtx_code code = GET_CODE (x);
4658   register char *fmt;
4659   register int i;
4660   register rtx value = 0;
4661
4662   switch (code)
4663     {
4664     case LABEL_REF:
4665     case SYMBOL_REF:
4666     case CONST_INT:
4667     case CONST_DOUBLE:
4668     case CONST:
4669     case REG:
4670     case CC0:
4671     case PC:
4672       return x;
4673
4674     case VOLATILE:
4675     case UNCHANGING:
4676       return XEXP (x, 0);
4677     }
4678
4679   fmt = GET_RTX_FORMAT (code);
4680   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4681     {
4682       if (fmt[i] == 'e')
4683         XEXP (x, i) = forget_volatility (XEXP (x, i));
4684       if (fmt[i] == 'E')
4685         {
4686           register int j;
4687           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
4688             XVECEXP (x, i, j) = forget_volatility (XVECEXP (x, i, j));
4689         }
4690     }
4691
4692   return x;
4693 }
4694
4695 #endif
4696 \f
4697 /* Check the insns before INSN to see if there is a suitable register
4698    containing the same value as GOAL.
4699    If OTHER is -1, look for a register in class CLASS.
4700    Otherwise, just see if register number OTHER shares GOAL's value.
4701
4702    Return an rtx for the register found, or zero if none is found.
4703
4704    If RELOAD_REG_P is (short *)1,
4705    we reject any hard reg that appears in reload_reg_rtx
4706    because such a hard reg is also needed coming into this insn.
4707
4708    If RELOAD_REG_P is any other nonzero value,
4709    it is a vector indexed by hard reg number
4710    and we reject any hard reg whose element in the vector is nonnegative
4711    as well as any that appears in reload_reg_rtx.
4712
4713    If GOAL is zero, then GOALREG is a register number; we look
4714    for an equivalent for that register.
4715
4716    MODE is the machine mode of the value we want an equivalence for.
4717    If GOAL is nonzero and not VOIDmode, then it must have mode MODE.
4718
4719    This function is used by jump.c as well as in the reload pass.
4720
4721    If GOAL is the sum of the stack pointer and a constant, we treat it
4722    as if it were a constant except that sp is required to be unchanging.  */
4723
4724 rtx
4725 find_equiv_reg (goal, insn, class, other, reload_reg_p, goalreg, mode)
4726      register rtx goal;
4727      rtx insn;
4728      enum reg_class class;
4729      register int other;
4730      short *reload_reg_p;
4731      int goalreg;
4732      enum machine_mode mode;
4733 {
4734   register rtx p = insn;
4735   rtx valtry, value, where;
4736   register rtx pat;
4737   register int regno = -1;
4738   int valueno;
4739   int goal_mem = 0;
4740   int goal_const = 0;
4741   int goal_mem_addr_varies = 0;
4742   int need_stable_sp = 0;
4743   int nregs;
4744   int valuenregs;
4745
4746   if (goal == 0)
4747     regno = goalreg;
4748   else if (GET_CODE (goal) == REG)
4749     regno = REGNO (goal);
4750   else if (GET_CODE (goal) == MEM)
4751     {
4752       enum rtx_code code = GET_CODE (XEXP (goal, 0));
4753       if (MEM_VOLATILE_P (goal))
4754         return 0;
4755       if (flag_float_store && GET_MODE_CLASS (GET_MODE (goal)) == MODE_FLOAT)
4756         return 0;
4757       /* An address with side effects must be reexecuted.  */
4758       switch (code)
4759         {
4760         case POST_INC:
4761         case PRE_INC:
4762         case POST_DEC:
4763         case PRE_DEC:
4764           return 0;
4765         }
4766       goal_mem = 1;
4767     }
4768   else if (CONSTANT_P (goal))
4769     goal_const = 1;
4770   else if (GET_CODE (goal) == PLUS
4771            && XEXP (goal, 0) == stack_pointer_rtx
4772            && CONSTANT_P (XEXP (goal, 1)))
4773     goal_const = need_stable_sp = 1;
4774   else
4775     return 0;
4776
4777   /* On some machines, certain regs must always be rejected
4778      because they don't behave the way ordinary registers do.  */
4779
4780 #ifdef OVERLAPPING_REGNO_P
4781    if (regno >= 0 && regno < FIRST_PSEUDO_REGISTER
4782        && OVERLAPPING_REGNO_P (regno))
4783      return 0;
4784 #endif
4785
4786   /* Scan insns back from INSN, looking for one that copies
4787      a value into or out of GOAL.
4788      Stop and give up if we reach a label.  */
4789
4790   while (1)
4791     {
4792       p = PREV_INSN (p);
4793       if (p == 0 || GET_CODE (p) == CODE_LABEL)
4794         return 0;
4795       if (GET_CODE (p) == INSN
4796           /* If we don't want spill regs ... */
4797           && (! (reload_reg_p != 0 && reload_reg_p != (short *)1)
4798           /* ... then ignore insns introduced by reload; they aren't useful
4799              and can cause results in reload_as_needed to be different
4800              from what they were when calculating the need for spills.
4801              If we notice an input-reload insn here, we will reject it below,
4802              but it might hide a usable equivalent.  That makes bad code.
4803              It may even abort: perhaps no reg was spilled for this insn
4804              because it was assumed we would find that equivalent.  */
4805               || INSN_UID (p) < reload_first_uid))
4806         {
4807           rtx tem;
4808           pat = single_set (p);
4809           /* First check for something that sets some reg equal to GOAL.  */
4810           if (pat != 0
4811               && ((regno >= 0
4812                    && true_regnum (SET_SRC (pat)) == regno
4813                    && (valueno = true_regnum (valtry = SET_DEST (pat))) >= 0)
4814                   ||
4815                   (regno >= 0
4816                    && true_regnum (SET_DEST (pat)) == regno
4817                    && (valueno = true_regnum (valtry = SET_SRC (pat))) >= 0)
4818                   ||
4819                   (goal_const && rtx_equal_p (SET_SRC (pat), goal)
4820                    && (valueno = true_regnum (valtry = SET_DEST (pat))) >= 0)
4821                   || (goal_mem
4822                       && (valueno = true_regnum (valtry = SET_DEST (pat))) >= 0
4823                       && rtx_renumbered_equal_p (goal, SET_SRC (pat)))
4824                   || (goal_mem
4825                       && (valueno = true_regnum (valtry = SET_SRC (pat))) >= 0
4826                       && rtx_renumbered_equal_p (goal, SET_DEST (pat)))
4827                   /* If we are looking for a constant,
4828                      and something equivalent to that constant was copied
4829                      into a reg, we can use that reg.  */
4830                   || (goal_const && (tem = find_reg_note (p, REG_EQUIV,
4831                                                           NULL_RTX))
4832                       && rtx_equal_p (XEXP (tem, 0), goal)
4833                       && (valueno = true_regnum (valtry = SET_DEST (pat))) >= 0)
4834                   || (goal_const && (tem = find_reg_note (p, REG_EQUIV,
4835                                                           NULL_RTX))
4836                       && GET_CODE (SET_DEST (pat)) == REG
4837                       && GET_CODE (XEXP (tem, 0)) == CONST_DOUBLE
4838                       && GET_MODE_CLASS (GET_MODE (XEXP (tem, 0))) == MODE_FLOAT
4839                       && GET_CODE (goal) == CONST_INT
4840                       && INTVAL (goal) == CONST_DOUBLE_LOW (XEXP (tem, 0))
4841                       && (valtry = operand_subword (SET_DEST (pat), 0, 0,
4842                                                     VOIDmode))
4843                       && (valueno = true_regnum (valtry)) >= 0)
4844                   || (goal_const && (tem = find_reg_note (p, REG_EQUIV,
4845                                                           NULL_RTX))
4846                       && GET_CODE (SET_DEST (pat)) == REG
4847                       && GET_CODE (XEXP (tem, 0)) == CONST_DOUBLE
4848                       && GET_MODE_CLASS (GET_MODE (XEXP (tem, 0))) == MODE_FLOAT
4849                       && GET_CODE (goal) == CONST_INT
4850                       && INTVAL (goal) == CONST_DOUBLE_HIGH (XEXP (tem, 0))
4851                       && (valtry
4852                           = operand_subword (SET_DEST (pat), 1, 0, VOIDmode))
4853                       && (valueno = true_regnum (valtry)) >= 0)))
4854             if (other >= 0
4855                 ? valueno == other
4856                 : ((unsigned) valueno < FIRST_PSEUDO_REGISTER
4857                    && TEST_HARD_REG_BIT (reg_class_contents[(int) class],
4858                                          valueno)))
4859               {
4860                 value = valtry;
4861                 where = p;
4862                 break;
4863               }
4864         }
4865     }
4866
4867   /* We found a previous insn copying GOAL into a suitable other reg VALUE
4868      (or copying VALUE into GOAL, if GOAL is also a register).
4869      Now verify that VALUE is really valid.  */
4870
4871   /* VALUENO is the register number of VALUE; a hard register.  */
4872
4873   /* Don't try to re-use something that is killed in this insn.  We want
4874      to be able to trust REG_UNUSED notes.  */
4875   if (find_reg_note (where, REG_UNUSED, value))
4876     return 0;
4877
4878   /* If we propose to get the value from the stack pointer or if GOAL is
4879      a MEM based on the stack pointer, we need a stable SP.  */
4880   if (valueno == STACK_POINTER_REGNUM
4881       || (goal_mem && reg_overlap_mentioned_for_reload_p (stack_pointer_rtx,
4882                                                           goal)))
4883     need_stable_sp = 1;
4884
4885   /* Reject VALUE if the copy-insn moved the wrong sort of datum.  */
4886   if (GET_MODE (value) != mode)
4887     return 0;
4888
4889   /* Reject VALUE if it was loaded from GOAL
4890      and is also a register that appears in the address of GOAL.  */
4891
4892   if (goal_mem && value == SET_DEST (PATTERN (where))
4893       && refers_to_regno_for_reload_p (valueno,
4894                                        (valueno
4895                                         + HARD_REGNO_NREGS (valueno, mode)),
4896                                        goal, NULL_PTR))
4897     return 0;
4898
4899   /* Reject registers that overlap GOAL.  */
4900
4901   if (!goal_mem && !goal_const
4902       && regno + HARD_REGNO_NREGS (regno, mode) > valueno
4903       && regno < valueno + HARD_REGNO_NREGS (valueno, mode))
4904     return 0;
4905
4906   /* Reject VALUE if it is one of the regs reserved for reloads.
4907      Reload1 knows how to reuse them anyway, and it would get
4908      confused if we allocated one without its knowledge.
4909      (Now that insns introduced by reload are ignored above,
4910      this case shouldn't happen, but I'm not positive.)  */
4911
4912   if (reload_reg_p != 0 && reload_reg_p != (short *)1
4913       && reload_reg_p[valueno] >= 0)
4914     return 0;
4915
4916   /* On some machines, certain regs must always be rejected
4917      because they don't behave the way ordinary registers do.  */
4918
4919 #ifdef OVERLAPPING_REGNO_P
4920   if (OVERLAPPING_REGNO_P (valueno))
4921     return 0;
4922 #endif
4923
4924   nregs = HARD_REGNO_NREGS (regno, mode);
4925   valuenregs = HARD_REGNO_NREGS (valueno, mode);
4926
4927   /* Reject VALUE if it is a register being used for an input reload
4928      even if it is not one of those reserved.  */
4929
4930   if (reload_reg_p != 0)
4931     {
4932       int i;
4933       for (i = 0; i < n_reloads; i++)
4934         if (reload_reg_rtx[i] != 0 && reload_in[i])
4935           {
4936             int regno1 = REGNO (reload_reg_rtx[i]);
4937             int nregs1 = HARD_REGNO_NREGS (regno1,
4938                                            GET_MODE (reload_reg_rtx[i]));
4939             if (regno1 < valueno + valuenregs
4940                 && regno1 + nregs1 > valueno)
4941               return 0;
4942           }
4943     }
4944
4945   if (goal_mem)
4946     goal_mem_addr_varies = rtx_addr_varies_p (goal);
4947
4948   /* Now verify that the values of GOAL and VALUE remain unaltered
4949      until INSN is reached.  */
4950
4951   p = insn;
4952   while (1)
4953     {
4954       p = PREV_INSN (p);
4955       if (p == where)
4956         return value;
4957
4958       /* Don't trust the conversion past a function call
4959          if either of the two is in a call-clobbered register, or memory.  */
4960       if (GET_CODE (p) == CALL_INSN
4961           && ((regno >= 0 && regno < FIRST_PSEUDO_REGISTER
4962                && call_used_regs[regno])
4963               ||
4964               (valueno >= 0 && valueno < FIRST_PSEUDO_REGISTER
4965                && call_used_regs[valueno])
4966               ||
4967               goal_mem
4968               || need_stable_sp))
4969         return 0;
4970
4971 #ifdef INSN_CLOBBERS_REGNO_P
4972       if ((valueno >= 0 && valueno < FIRST_PSEUDO_REGISTER
4973           && INSN_CLOBBERS_REGNO_P (p, valueno))
4974           || (regno >= 0 && regno < FIRST_PSEUDO_REGISTER
4975           && INSN_CLOBBERS_REGNO_P (p, regno)))
4976         return 0;
4977 #endif
4978
4979       if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
4980         {
4981           /* If this insn P stores in either GOAL or VALUE, return 0.
4982              If GOAL is a memory ref and this insn writes memory, return 0.
4983              If GOAL is a memory ref and its address is not constant,
4984              and this insn P changes a register used in GOAL, return 0.  */
4985
4986           pat = PATTERN (p);
4987           if (GET_CODE (pat) == SET || GET_CODE (pat) == CLOBBER)
4988             {
4989               register rtx dest = SET_DEST (pat);
4990               while (GET_CODE (dest) == SUBREG
4991                      || GET_CODE (dest) == ZERO_EXTRACT
4992                      || GET_CODE (dest) == SIGN_EXTRACT
4993                      || GET_CODE (dest) == STRICT_LOW_PART)
4994                 dest = XEXP (dest, 0);
4995               if (GET_CODE (dest) == REG)
4996                 {
4997                   register int xregno = REGNO (dest);
4998                   int xnregs;
4999                   if (REGNO (dest) < FIRST_PSEUDO_REGISTER)
5000                     xnregs = HARD_REGNO_NREGS (xregno, GET_MODE (dest));
5001                   else
5002                     xnregs = 1;
5003                   if (xregno < regno + nregs && xregno + xnregs > regno)
5004                     return 0;
5005                   if (xregno < valueno + valuenregs
5006                       && xregno + xnregs > valueno)
5007                     return 0;
5008                   if (goal_mem_addr_varies
5009                       && reg_overlap_mentioned_for_reload_p (dest, goal))
5010                     return 0;
5011                 }
5012               else if (goal_mem && GET_CODE (dest) == MEM
5013                        && ! push_operand (dest, GET_MODE (dest)))
5014                 return 0;
5015               else if (need_stable_sp && push_operand (dest, GET_MODE (dest)))
5016                 return 0;
5017             }
5018           else if (GET_CODE (pat) == PARALLEL)
5019             {
5020               register int i;
5021               for (i = XVECLEN (pat, 0) - 1; i >= 0; i--)
5022                 {
5023                   register rtx v1 = XVECEXP (pat, 0, i);
5024                   if (GET_CODE (v1) == SET || GET_CODE (v1) == CLOBBER)
5025                     {
5026                       register rtx dest = SET_DEST (v1);
5027                       while (GET_CODE (dest) == SUBREG
5028                              || GET_CODE (dest) == ZERO_EXTRACT
5029                              || GET_CODE (dest) == SIGN_EXTRACT
5030                              || GET_CODE (dest) == STRICT_LOW_PART)
5031                         dest = XEXP (dest, 0);
5032                       if (GET_CODE (dest) == REG)
5033                         {
5034                           register int xregno = REGNO (dest);
5035                           int xnregs;
5036                           if (REGNO (dest) < FIRST_PSEUDO_REGISTER)
5037                             xnregs = HARD_REGNO_NREGS (xregno, GET_MODE (dest));
5038                           else
5039                             xnregs = 1;
5040                           if (xregno < regno + nregs
5041                               && xregno + xnregs > regno)
5042                             return 0;
5043                           if (xregno < valueno + valuenregs
5044                               && xregno + xnregs > valueno)
5045                             return 0;
5046                           if (goal_mem_addr_varies
5047                               && reg_overlap_mentioned_for_reload_p (dest,
5048                                                                      goal))
5049                             return 0;
5050                         }
5051                       else if (goal_mem && GET_CODE (dest) == MEM
5052                                && ! push_operand (dest, GET_MODE (dest)))
5053                         return 0;
5054                       else if (need_stable_sp
5055                                && push_operand (dest, GET_MODE (dest)))
5056                         return 0;
5057                     }
5058                 }
5059             }
5060
5061 #ifdef AUTO_INC_DEC
5062           /* If this insn auto-increments or auto-decrements
5063              either regno or valueno, return 0 now.
5064              If GOAL is a memory ref and its address is not constant,
5065              and this insn P increments a register used in GOAL, return 0.  */
5066           {
5067             register rtx link;
5068
5069             for (link = REG_NOTES (p); link; link = XEXP (link, 1))
5070               if (REG_NOTE_KIND (link) == REG_INC
5071                   && GET_CODE (XEXP (link, 0)) == REG)
5072                 {
5073                   register int incno = REGNO (XEXP (link, 0));
5074                   if (incno < regno + nregs && incno >= regno)
5075                     return 0;
5076                   if (incno < valueno + valuenregs && incno >= valueno)
5077                     return 0;
5078                   if (goal_mem_addr_varies
5079                       && reg_overlap_mentioned_for_reload_p (XEXP (link, 0),
5080                                                              goal))
5081                     return 0;
5082                 }
5083           }
5084 #endif
5085         }
5086     }
5087 }
5088 \f
5089 /* Find a place where INCED appears in an increment or decrement operator
5090    within X, and return the amount INCED is incremented or decremented by.
5091    The value is always positive.  */
5092
5093 static int
5094 find_inc_amount (x, inced)
5095      rtx x, inced;
5096 {
5097   register enum rtx_code code = GET_CODE (x);
5098   register char *fmt;
5099   register int i;
5100
5101   if (code == MEM)
5102     {
5103       register rtx addr = XEXP (x, 0);
5104       if ((GET_CODE (addr) == PRE_DEC
5105            || GET_CODE (addr) == POST_DEC
5106            || GET_CODE (addr) == PRE_INC
5107            || GET_CODE (addr) == POST_INC)
5108           && XEXP (addr, 0) == inced)
5109         return GET_MODE_SIZE (GET_MODE (x));
5110     }
5111
5112   fmt = GET_RTX_FORMAT (code);
5113   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
5114     {
5115       if (fmt[i] == 'e')
5116         {
5117           register int tem = find_inc_amount (XEXP (x, i), inced);
5118           if (tem != 0)
5119             return tem;
5120         }
5121       if (fmt[i] == 'E')
5122         {
5123           register int j;
5124           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
5125             {
5126               register int tem = find_inc_amount (XVECEXP (x, i, j), inced);
5127               if (tem != 0)
5128                 return tem;
5129             }
5130         }
5131     }
5132
5133   return 0;
5134 }
5135 \f
5136 /* Return 1 if register REGNO is the subject of a clobber in insn INSN.  */
5137
5138 int
5139 regno_clobbered_p (regno, insn)
5140      int regno;
5141      rtx insn;
5142 {
5143   if (GET_CODE (PATTERN (insn)) == CLOBBER
5144       && GET_CODE (XEXP (PATTERN (insn), 0)) == REG)
5145     return REGNO (XEXP (PATTERN (insn), 0)) == regno;
5146
5147   if (GET_CODE (PATTERN (insn)) == PARALLEL)
5148     {
5149       int i = XVECLEN (PATTERN (insn), 0) - 1;
5150
5151       for (; i >= 0; i--)
5152         {
5153           rtx elt = XVECEXP (PATTERN (insn), 0, i);
5154           if (GET_CODE (elt) == CLOBBER && GET_CODE (XEXP (elt, 0)) == REG
5155               && REGNO (XEXP (elt, 0)) == regno)
5156             return 1;
5157         }
5158     }
5159
5160   return 0;
5161 }