gcc/recog.c

   1 /* Subroutines used by or related to instruction recognition.
   2    Copyright (C) 1987, 1988, 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998
   3    1999, 2000 Free Software Foundation, Inc.
   4
   5 This file is part of GNU CC.
   6
   7 GNU CC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GNU CC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GNU CC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, USA.  */
  21
  22
  23 #include "config.h"
  24 #include "system.h"
  25 #include "rtl.h"
  26 #include "tm_p.h"
  27 #include "insn-config.h"
  28 #include "insn-attr.h"
  29 #include "insn-flags.h"
  30 #include "insn-codes.h"
  31 #include "hard-reg-set.h"
  32 #include "recog.h"
  33 #include "regs.h"
  34 #include "function.h"
  35 #include "flags.h"
  36 #include "real.h"
  37 #include "toplev.h"
  38 #include "basic-block.h"
  39 #include "output.h"
  40
  41 #ifndef STACK_PUSH_CODE
  42 #ifdef STACK_GROWS_DOWNWARD
  43 #define STACK_PUSH_CODE PRE_DEC
  44 #else
  45 #define STACK_PUSH_CODE PRE_INC
  46 #endif
  47 #endif
  48
  49 #ifndef STACK_POP_CODE
  50 #ifdef STACK_GROWS_DOWNWARD
  51 #define STACK_POP_CODE POST_INC
  52 #else
  53 #define STACK_POP_CODE POST_DEC
  54 #endif
  55 #endif
  56
  57 static void validate_replace_rtx_1      PARAMS ((rtx *, rtx, rtx, rtx));
  58 static rtx *find_single_use_1           PARAMS ((rtx, rtx *));
  59 static rtx *find_constant_term_loc      PARAMS ((rtx *));
  60 static int insn_invalid_p               PARAMS ((rtx));
  61
  62 /* Nonzero means allow operands to be volatile.
  63    This should be 0 if you are generating rtl, such as if you are calling
  64    the functions in optabs.c and expmed.c (most of the time).
  65    This should be 1 if all valid insns need to be recognized,
  66    such as in regclass.c and final.c and reload.c.
  67
  68    init_recog and init_recog_no_volatile are responsible for setting this.  */
  69
  70 int volatile_ok;
  71
  72 struct recog_data recog_data;
  73
  74 /* Contains a vector of operand_alternative structures for every operand.
  75    Set up by preprocess_constraints.  */
  76 struct operand_alternative recog_op_alt[MAX_RECOG_OPERANDS][MAX_RECOG_ALTERNATIVES];
  77
  78 /* On return from `constrain_operands', indicate which alternative
  79    was satisfied.  */
  80
  81 int which_alternative;
  82
  83 /* Nonzero after end of reload pass.
  84    Set to 1 or 0 by toplev.c.
  85    Controls the significance of (SUBREG (MEM)).  */
  86
  87 int reload_completed;
  88
  89 /* Initialize data used by the function `recog'.
  90    This must be called once in the compilation of a function
  91    before any insn recognition may be done in the function.  */
  92
  93 void
  94 init_recog_no_volatile ()
  95 {
  96   volatile_ok = 0;
  97 }
  98
  99 void
 100 init_recog ()
 101 {
 102   volatile_ok = 1;
 103 }
 104
 105 /* Try recognizing the instruction INSN,
 106    and return the code number that results.
 107    Remember the code so that repeated calls do not
 108    need to spend the time for actual rerecognition.
 109
 110    This function is the normal interface to instruction recognition.
 111    The automatically-generated function `recog' is normally called
 112    through this one.  (The only exception is in combine.c.)  */
 113
 114 int
 115 recog_memoized_1 (insn)
 116      rtx insn;
 117 {
 118   if (INSN_CODE (insn) < 0)
 119     INSN_CODE (insn) = recog (PATTERN (insn), insn, NULL_PTR);
 120   return INSN_CODE (insn);
 121 }
 122 \f
 123 /* Check that X is an insn-body for an `asm' with operands
 124    and that the operands mentioned in it are legitimate.  */
 125
 126 int
 127 check_asm_operands (x)
 128      rtx x;
 129 {
 130   int noperands;
 131   rtx *operands;
 132   const char **constraints;
 133   int i;
 134
 135   /* Post-reload, be more strict with things.  */
 136   if (reload_completed)
 137     {
 138       /* ??? Doh!  We've not got the wrapping insn.  Cook one up.  */
 139       extract_insn (make_insn_raw (x));
 140       constrain_operands (1);
 141       return which_alternative >= 0;
 142     }
 143
 144   noperands = asm_noperands (x);
 145   if (noperands < 0)
 146     return 0;
 147   if (noperands == 0)
 148     return 1;
 149
 150   operands = (rtx *) alloca (noperands * sizeof (rtx));
 151   constraints = (const char **) alloca (noperands * sizeof (char *));
 152
 153   decode_asm_operands (x, operands, NULL_PTR, constraints, NULL_PTR);
 154
 155   for (i = 0; i < noperands; i++)
 156     {
 157       const char *c = constraints[i];
 158       if (c[0] == '%')
 159         c++;
 160       if (ISDIGIT ((unsigned char)c[0]) && c[1] == '\0')
 161         c = constraints[c[0] - '0'];
 162
 163       if (! asm_operand_ok (operands[i], c))
 164         return 0;
 165     }
 166
 167   return 1;
 168 }
 169 \f
 170 /* Static data for the next two routines.  */
 171
 172 typedef struct change_t
 173 {
 174   rtx object;
 175   int old_code;
 176   rtx *loc;
 177   rtx old;
 178 } change_t;
 179
 180 static change_t *changes;
 181 static int changes_allocated;
 182
 183 static int num_changes = 0;
 184
 185 /* Validate a proposed change to OBJECT.  LOC is the location in the rtl for
 186    at which NEW will be placed.  If OBJECT is zero, no validation is done,
 187    the change is simply made.
 188
 189    Two types of objects are supported:  If OBJECT is a MEM, memory_address_p
 190    will be called with the address and mode as parameters.  If OBJECT is
 191    an INSN, CALL_INSN, or JUMP_INSN, the insn will be re-recognized with
 192    the change in place.
 193
 194    IN_GROUP is non-zero if this is part of a group of changes that must be
 195    performed as a group.  In that case, the changes will be stored.  The
 196    function `apply_change_group' will validate and apply the changes.
 197
 198    If IN_GROUP is zero, this is a single change.  Try to recognize the insn
 199    or validate the memory reference with the change applied.  If the result
 200    is not valid for the machine, suppress the change and return zero.
 201    Otherwise, perform the change and return 1.  */
 202
 203 int
 204 validate_change (object, loc, new, in_group)
 205     rtx object;
 206     rtx *loc;
 207     rtx new;
 208     int in_group;
 209 {
 210   rtx old = *loc;
 211
 212   if (old == new || rtx_equal_p (old, new))
 213     return 1;
 214
 215   if (in_group == 0 && num_changes != 0)
 216     abort ();
 217
 218   *loc = new;
 219
 220   /* Save the information describing this change.  */
 221   if (num_changes >= changes_allocated)
 222     {
 223       if (changes_allocated == 0)
 224         /* This value allows for repeated substitutions inside complex
 225            indexed addresses, or changes in up to 5 insns.  */
 226         changes_allocated = MAX_RECOG_OPERANDS * 5;
 227       else
 228         changes_allocated *= 2;
 229
 230       changes =
 231         (change_t*) xrealloc (changes,
 232                               sizeof (change_t) * changes_allocated);
 233     }
 234
 235   changes[num_changes].object = object;
 236   changes[num_changes].loc = loc;
 237   changes[num_changes].old = old;
 238
 239   if (object && GET_CODE (object) != MEM)
 240     {
 241       /* Set INSN_CODE to force rerecognition of insn.  Save old code in
 242          case invalid.  */
 243       changes[num_changes].old_code = INSN_CODE (object);
 244       INSN_CODE (object) = -1;
 245     }
 246
 247   num_changes++;
 248
 249   /* If we are making a group of changes, return 1.  Otherwise, validate the
 250      change group we made.  */
 251
 252   if (in_group)
 253     return 1;
 254   else
 255     return apply_change_group ();
 256 }
 257
 258 /* This subroutine of apply_change_group verifies whether the changes to INSN
 259    were valid; i.e. whether INSN can still be recognized.  */
 260
 261 static int
 262 insn_invalid_p (insn)
 263      rtx insn;
 264 {
 265   int icode = recog_memoized (insn);
 266   int is_asm = icode < 0 && asm_noperands (PATTERN (insn)) >= 0;
 267
 268   if (is_asm && ! check_asm_operands (PATTERN (insn)))
 269     return 1;
 270   if (! is_asm && icode < 0)
 271     return 1;
 272
 273   /* After reload, verify that all constraints are satisfied.  */
 274   if (reload_completed)
 275     {
 276       extract_insn (insn);
 277
 278       if (! constrain_operands (1))
 279         return 1;
 280     }
 281
 282   return 0;
 283 }
 284
 285 /* Apply a group of changes previously issued with `validate_change'.
 286    Return 1 if all changes are valid, zero otherwise.  */
 287
 288 int
 289 apply_change_group ()
 290 {
 291   int i;
 292
 293   /* The changes have been applied and all INSN_CODEs have been reset to force
 294      rerecognition.
 295
 296      The changes are valid if we aren't given an object, or if we are
 297      given a MEM and it still is a valid address, or if this is in insn
 298      and it is recognized.  In the latter case, if reload has completed,
 299      we also require that the operands meet the constraints for
 300      the insn.  */
 301
 302   for (i = 0; i < num_changes; i++)
 303     {
 304       rtx object = changes[i].object;
 305
 306       if (object == 0)
 307         continue;
 308
 309       if (GET_CODE (object) == MEM)
 310         {
 311           if (! memory_address_p (GET_MODE (object), XEXP (object, 0)))
 312             break;
 313         }
 314       else if (insn_invalid_p (object))
 315         {
 316           rtx pat = PATTERN (object);
 317
 318           /* Perhaps we couldn't recognize the insn because there were
 319              extra CLOBBERs at the end.  If so, try to re-recognize
 320              without the last CLOBBER (later iterations will cause each of
 321              them to be eliminated, in turn).  But don't do this if we
 322              have an ASM_OPERAND.  */
 323           if (GET_CODE (pat) == PARALLEL
 324               && GET_CODE (XVECEXP (pat, 0, XVECLEN (pat, 0) - 1)) == CLOBBER
 325               && asm_noperands (PATTERN (object)) < 0)
 326             {
 327                rtx newpat;
 328
 329                if (XVECLEN (pat, 0) == 2)
 330                  newpat = XVECEXP (pat, 0, 0);
 331                else
 332                  {
 333                    int j;
 334
 335                    newpat
 336                      = gen_rtx_PARALLEL (VOIDmode,
 337                                          gen_rtvec (XVECLEN (pat, 0) - 1));
 338                    for (j = 0; j < XVECLEN (newpat, 0); j++)
 339                      XVECEXP (newpat, 0, j) = XVECEXP (pat, 0, j);
 340                  }
 341
 342                /* Add a new change to this group to replace the pattern
 343                   with this new pattern.  Then consider this change
 344                   as having succeeded.  The change we added will
 345                   cause the entire call to fail if things remain invalid.
 346
 347                   Note that this can lose if a later change than the one
 348                   we are processing specified &XVECEXP (PATTERN (object), 0, X)
 349                   but this shouldn't occur.  */
 350
 351                validate_change (object, &PATTERN (object), newpat, 1);
 352              }
 353           else if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
 354             /* If this insn is a CLOBBER or USE, it is always valid, but is
 355                never recognized.  */
 356             continue;
 357           else
 358             break;
 359         }
 360     }
 361
 362   if (i == num_changes)
 363     {
 364       num_changes = 0;
 365       return 1;
 366     }
 367   else
 368     {
 369       cancel_changes (0);
 370       return 0;
 371     }
 372 }
 373
 374 /* Return the number of changes so far in the current group.   */
 375
 376 int
 377 num_validated_changes ()
 378 {
 379   return num_changes;
 380 }
 381
 382 /* Retract the changes numbered NUM and up.  */
 383
 384 void
 385 cancel_changes (num)
 386      int num;
 387 {
 388   int i;
 389
 390   /* Back out all the changes.  Do this in the opposite order in which
 391      they were made.  */
 392   for (i = num_changes - 1; i >= num; i--)
 393     {
 394       *changes[i].loc = changes[i].old;
 395       if (changes[i].object && GET_CODE (changes[i].object) != MEM)
 396         INSN_CODE (changes[i].object) = changes[i].old_code;
 397     }
 398   num_changes = num;
 399 }
 400
 401 /* Replace every occurrence of FROM in X with TO.  Mark each change with
 402    validate_change passing OBJECT.  */
 403
 404 static void
 405 validate_replace_rtx_1 (loc, from, to, object)
 406      rtx *loc;
 407      rtx from, to, object;
 408 {
 409   register int i, j;
 410   register const char *fmt;
 411   register rtx x = *loc;
 412   enum rtx_code code;
 413
 414   if (!x)
 415     return;
 416   code = GET_CODE (x);
 417   /* X matches FROM if it is the same rtx or they are both referring to the
 418      same register in the same mode.  Avoid calling rtx_equal_p unless the
 419      operands look similar.  */
 420
 421   if (x == from
 422       || (GET_CODE (x) == REG && GET_CODE (from) == REG
 423           && GET_MODE (x) == GET_MODE (from)
 424           && REGNO (x) == REGNO (from))
 425       || (GET_CODE (x) == GET_CODE (from) && GET_MODE (x) == GET_MODE (from)
 426           && rtx_equal_p (x, from)))
 427     {
 428       validate_change (object, loc, to, 1);
 429       return;
 430     }
 431
 432   /* For commutative or comparison operations, try replacing each argument
 433      separately and seeing if we made any changes.  If so, put a constant
 434      argument last.*/
 435   if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == 'c')
 436     {
 437       int prev_changes = num_changes;
 438
 439       validate_replace_rtx_1 (&XEXP (x, 0), from, to, object);
 440       validate_replace_rtx_1 (&XEXP (x, 1), from, to, object);
 441       if (prev_changes != num_changes && CONSTANT_P (XEXP (x, 0)))
 442         {
 443           validate_change (object, loc,
 444                            gen_rtx_fmt_ee (GET_RTX_CLASS (code) == 'c' ? code
 445                                            : swap_condition (code),
 446                                            GET_MODE (x), XEXP (x, 1),
 447                                            XEXP (x, 0)),
 448                            1);
 449           x = *loc;
 450           code = GET_CODE (x);
 451         }
 452     }
 453
 454   /* Note that if CODE's RTX_CLASS is "c" or "<" we will have already
 455      done the substitution, otherwise we won't.  */
 456
 457   switch (code)
 458     {
 459     case PLUS:
 460       /* If we have a PLUS whose second operand is now a CONST_INT, use
 461          plus_constant to try to simplify it.  */
 462       if (GET_CODE (XEXP (x, 1)) == CONST_INT && XEXP (x, 1) == to)
 463         validate_change (object, loc, plus_constant (XEXP (x, 0), INTVAL (to)),
 464                          1);
 465       return;
 466
 467     case MINUS:
 468       if (GET_CODE (to) == CONST_INT && XEXP (x, 1) == from)
 469         {
 470           validate_change (object, loc,
 471                            plus_constant (XEXP (x, 0), - INTVAL (to)),
 472                            1);
 473           return;
 474         }
 475       break;
 476
 477     case ZERO_EXTEND:
 478     case SIGN_EXTEND:
 479       /* In these cases, the operation to be performed depends on the mode
 480          of the operand.  If we are replacing the operand with a VOIDmode
 481          constant, we lose the information.  So try to simplify the operation
 482          in that case.  If it fails, substitute in something that we know
 483          won't be recognized.  */
 484       if (GET_MODE (to) == VOIDmode
 485           && rtx_equal_p (XEXP (x, 0), from))
 486         {
 487           rtx new = simplify_unary_operation (code, GET_MODE (x), to,
 488                                               GET_MODE (from));
 489           if (new == 0)
 490             new = gen_rtx_CLOBBER (GET_MODE (x), const0_rtx);
 491
 492           validate_change (object, loc, new, 1);
 493           return;
 494         }
 495       break;
 496
 497     case SUBREG:
 498       /* In case we are replacing by constant, attempt to simplify it to non-SUBREG
 499          expression.  We can't do this later, since the information about inner mode
 500          may be lost.  */
 501       if (CONSTANT_P (to) && rtx_equal_p (SUBREG_REG (x), from))
 502         {
 503           if (GET_MODE_SIZE (GET_MODE (x)) == UNITS_PER_WORD
 504               && GET_MODE_SIZE (GET_MODE (from)) > UNITS_PER_WORD
 505               && GET_MODE_CLASS (GET_MODE (x)) == MODE_INT)
 506             {
 507               rtx temp = operand_subword (to, SUBREG_WORD (x),
 508                                           0, GET_MODE (from));
 509               if (temp)
 510                 {
 511                   validate_change (object, loc, temp, 1);
 512                   return;
 513                 }
 514             }
 515           if (subreg_lowpart_p (x))
 516             {
 517               rtx new =  gen_lowpart_if_possible (GET_MODE (x), to);
 518               if (new)
 519                 {
 520                   validate_change (object, loc, new, 1);
 521                   return;
 522                 }
 523             }
 524
 525           /* A paradoxical SUBREG of a VOIDmode constant is the same constant,
 526              since we are saying that the high bits don't matter.  */
 527           if (GET_MODE (to) == VOIDmode
 528               && GET_MODE_SIZE (GET_MODE (x)) > GET_MODE_SIZE (GET_MODE (from)))
 529             {
 530               validate_change (object, loc, to, 1);
 531               return;
 532             }
 533         }
 534
 535       /* Changing mode twice with SUBREG => just change it once,
 536          or not at all if changing back to starting mode.  */
 537       if (GET_CODE (to) == SUBREG
 538           && rtx_equal_p (SUBREG_REG (x), from))
 539         {
 540           if (GET_MODE (x) == GET_MODE (SUBREG_REG (to))
 541               && SUBREG_WORD (x) == 0 && SUBREG_WORD (to) == 0)
 542             {
 543               validate_change (object, loc, SUBREG_REG (to), 1);
 544               return;
 545             }
 546
 547           validate_change (object, loc,
 548                            gen_rtx_SUBREG (GET_MODE (x), SUBREG_REG (to),
 549                                            SUBREG_WORD (x) + SUBREG_WORD (to)), 1);
 550           return;
 551         }
 552
 553       /* If we have a SUBREG of a register that we are replacing and we are
 554          replacing it with a MEM, make a new MEM and try replacing the
 555          SUBREG with it.  Don't do this if the MEM has a mode-dependent address
 556          or if we would be widening it.  */
 557
 558       if (GET_CODE (from) == REG
 559           && GET_CODE (to) == MEM
 560           && rtx_equal_p (SUBREG_REG (x), from)
 561           && ! mode_dependent_address_p (XEXP (to, 0))
 562           && ! MEM_VOLATILE_P (to)
 563           && GET_MODE_SIZE (GET_MODE (x)) <= GET_MODE_SIZE (GET_MODE (to)))
 564         {
 565           int offset = SUBREG_WORD (x) * UNITS_PER_WORD;
 566           enum machine_mode mode = GET_MODE (x);
 567           rtx new;
 568
 569           if (BYTES_BIG_ENDIAN)
 570             offset += (MIN (UNITS_PER_WORD,
 571                             GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
 572                        - MIN (UNITS_PER_WORD, GET_MODE_SIZE (mode)));
 573
 574           new = gen_rtx_MEM (mode, plus_constant (XEXP (to, 0), offset));
 575           MEM_COPY_ATTRIBUTES (new, to);
 576           validate_change (object, loc, new, 1);
 577           return;
 578         }
 579       break;
 580
 581     case ZERO_EXTRACT:
 582     case SIGN_EXTRACT:
 583       /* If we are replacing a register with memory, try to change the memory
 584          to be the mode required for memory in extract operations (this isn't
 585          likely to be an insertion operation; if it was, nothing bad will
 586          happen, we might just fail in some cases).  */
 587
 588       if (GET_CODE (from) == REG && GET_CODE (to) == MEM
 589           && rtx_equal_p (XEXP (x, 0), from)
 590           && GET_CODE (XEXP (x, 1)) == CONST_INT
 591           && GET_CODE (XEXP (x, 2)) == CONST_INT
 592           && ! mode_dependent_address_p (XEXP (to, 0))
 593           && ! MEM_VOLATILE_P (to))
 594         {
 595           enum machine_mode wanted_mode = VOIDmode;
 596           enum machine_mode is_mode = GET_MODE (to);
 597           int pos = INTVAL (XEXP (x, 2));
 598
 599 #ifdef HAVE_extzv
 600           if (code == ZERO_EXTRACT)
 601             {
 602               wanted_mode = insn_data[(int) CODE_FOR_extzv].operand[1].mode;
 603               if (wanted_mode == VOIDmode)
 604                 wanted_mode = word_mode;
 605             }
 606 #endif
 607 #ifdef HAVE_extv
 608           if (code == SIGN_EXTRACT)
 609             {
 610               wanted_mode = insn_data[(int) CODE_FOR_extv].operand[1].mode;
 611               if (wanted_mode == VOIDmode)
 612                 wanted_mode = word_mode;
 613             }
 614 #endif
 615
 616           /* If we have a narrower mode, we can do something.  */
 617           if (wanted_mode != VOIDmode
 618               && GET_MODE_SIZE (wanted_mode) < GET_MODE_SIZE (is_mode))
 619             {
 620               int offset = pos / BITS_PER_UNIT;
 621               rtx newmem;
 622
 623                   /* If the bytes and bits are counted differently, we
 624                      must adjust the offset.  */
 625               if (BYTES_BIG_ENDIAN != BITS_BIG_ENDIAN)
 626                 offset = (GET_MODE_SIZE (is_mode) - GET_MODE_SIZE (wanted_mode)
 627                           - offset);
 628
 629               pos %= GET_MODE_BITSIZE (wanted_mode);
 630
 631               newmem = gen_rtx_MEM (wanted_mode,
 632                                     plus_constant (XEXP (to, 0), offset));
 633               MEM_COPY_ATTRIBUTES (newmem, to);
 634
 635               validate_change (object, &XEXP (x, 2), GEN_INT (pos), 1);
 636               validate_change (object, &XEXP (x, 0), newmem, 1);
 637             }
 638         }
 639
 640       break;
 641
 642     default:
 643       break;
 644     }
 645
 646   /* For commutative or comparison operations we've already performed
 647      replacements.  Don't try to perform them again.  */
 648   if (GET_RTX_CLASS (code) != '<' && GET_RTX_CLASS (code) != 'c')
 649     {
 650       fmt = GET_RTX_FORMAT (code);
 651       for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 652         {
 653           if (fmt[i] == 'e')
 654             validate_replace_rtx_1 (&XEXP (x, i), from, to, object);
 655           else if (fmt[i] == 'E')
 656             for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 657               validate_replace_rtx_1 (&XVECEXP (x, i, j), from, to, object);
 658         }
 659     }
 660 }
 661
 662 /* Try replacing every occurrence of FROM in subexpression LOC of INSN
 663    with TO.  After all changes have been made, validate by seeing
 664    if INSN is still valid.  */
 665
 666 int
 667 validate_replace_rtx_subexp (from, to, insn, loc)
 668      rtx from, to, insn, *loc;
 669 {
 670   validate_replace_rtx_1 (loc, from, to, insn);
 671   return apply_change_group ();
 672 }
 673
 674 /* Try replacing every occurrence of FROM in INSN with TO.  After all
 675    changes have been made, validate by seeing if INSN is still valid.  */
 676
 677 int
 678 validate_replace_rtx (from, to, insn)
 679      rtx from, to, insn;
 680 {
 681   validate_replace_rtx_1 (&PATTERN (insn), from, to, insn);
 682   return apply_change_group ();
 683 }
 684
 685 /* Try replacing every occurrence of FROM in INSN with TO.  After all
 686    changes have been made, validate by seeing if INSN is still valid.  */
 687
 688 void
 689 validate_replace_rtx_group (from, to, insn)
 690      rtx from, to, insn;
 691 {
 692   validate_replace_rtx_1 (&PATTERN (insn), from, to, insn);
 693 }
 694
 695 /* Try replacing every occurrence of FROM in INSN with TO, avoiding
 696    SET_DESTs.  After all changes have been made, validate by seeing if
 697    INSN is still valid.  */
 698
 699 int
 700 validate_replace_src (from, to, insn)
 701      rtx from, to, insn;
 702 {
 703   if ((GET_CODE (insn) != INSN && GET_CODE (insn) != JUMP_INSN)
 704       || GET_CODE (PATTERN (insn)) != SET)
 705     abort ();
 706
 707   validate_replace_rtx_1 (&SET_SRC (PATTERN (insn)), from, to, insn);
 708   if (GET_CODE (SET_DEST (PATTERN (insn))) == MEM)
 709     validate_replace_rtx_1 (&XEXP (SET_DEST (PATTERN (insn)), 0),
 710                             from, to, insn);
 711   return apply_change_group ();
 712 }
 713 \f
 714 #ifdef HAVE_cc0
 715 /* Return 1 if the insn using CC0 set by INSN does not contain
 716    any ordered tests applied to the condition codes.
 717    EQ and NE tests do not count.  */
 718
 719 int
 720 next_insn_tests_no_inequality (insn)
 721      rtx insn;
 722 {
 723   register rtx next = next_cc0_user (insn);
 724
 725   /* If there is no next insn, we have to take the conservative choice.  */
 726   if (next == 0)
 727     return 0;
 728
 729   return ((GET_CODE (next) == JUMP_INSN
 730            || GET_CODE (next) == INSN
 731            || GET_CODE (next) == CALL_INSN)
 732           && ! inequality_comparisons_p (PATTERN (next)));
 733 }
 734
 735 #if 0  /* This is useless since the insn that sets the cc's
 736           must be followed immediately by the use of them.  */
 737 /* Return 1 if the CC value set up by INSN is not used.  */
 738
 739 int
 740 next_insns_test_no_inequality (insn)
 741      rtx insn;
 742 {
 743   register rtx next = NEXT_INSN (insn);
 744
 745   for (; next != 0; next = NEXT_INSN (next))
 746     {
 747       if (GET_CODE (next) == CODE_LABEL
 748           || GET_CODE (next) == BARRIER)
 749         return 1;
 750       if (GET_CODE (next) == NOTE)
 751         continue;
 752       if (inequality_comparisons_p (PATTERN (next)))
 753         return 0;
 754       if (sets_cc0_p (PATTERN (next)) == 1)
 755         return 1;
 756       if (! reg_mentioned_p (cc0_rtx, PATTERN (next)))
 757         return 1;
 758     }
 759   return 1;
 760 }
 761 #endif
 762 #endif
 763 \f
 764 /* This is used by find_single_use to locate an rtx that contains exactly one
 765    use of DEST, which is typically either a REG or CC0.  It returns a
 766    pointer to the innermost rtx expression containing DEST.  Appearances of
 767    DEST that are being used to totally replace it are not counted.  */
 768
 769 static rtx *
 770 find_single_use_1 (dest, loc)
 771      rtx dest;
 772      rtx *loc;
 773 {
 774   rtx x = *loc;
 775   enum rtx_code code = GET_CODE (x);
 776   rtx *result = 0;
 777   rtx *this_result;
 778   int i;
 779   const char *fmt;
 780
 781   switch (code)
 782     {
 783     case CONST_INT:
 784     case CONST:
 785     case LABEL_REF:
 786     case SYMBOL_REF:
 787     case CONST_DOUBLE:
 788     case CLOBBER:
 789       return 0;
 790
 791     case SET:
 792       /* If the destination is anything other than CC0, PC, a REG or a SUBREG
 793          of a REG that occupies all of the REG, the insn uses DEST if
 794          it is mentioned in the destination or the source.  Otherwise, we
 795          need just check the source.  */
 796       if (GET_CODE (SET_DEST (x)) != CC0
 797           && GET_CODE (SET_DEST (x)) != PC
 798           && GET_CODE (SET_DEST (x)) != REG
 799           && ! (GET_CODE (SET_DEST (x)) == SUBREG
 800                 && GET_CODE (SUBREG_REG (SET_DEST (x))) == REG
 801                 && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (SET_DEST (x))))
 802                       + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD)
 803                     == ((GET_MODE_SIZE (GET_MODE (SET_DEST (x)))
 804                          + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD))))
 805         break;
 806
 807       return find_single_use_1 (dest, &SET_SRC (x));
 808
 809     case MEM:
 810     case SUBREG:
 811       return find_single_use_1 (dest, &XEXP (x, 0));
 812
 813     default:
 814       break;
 815     }
 816
 817   /* If it wasn't one of the common cases above, check each expression and
 818      vector of this code.  Look for a unique usage of DEST.  */
 819
 820   fmt = GET_RTX_FORMAT (code);
 821   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 822     {
 823       if (fmt[i] == 'e')
 824         {
 825           if (dest == XEXP (x, i)
 826               || (GET_CODE (dest) == REG && GET_CODE (XEXP (x, i)) == REG
 827                   && REGNO (dest) == REGNO (XEXP (x, i))))
 828             this_result = loc;
 829           else
 830             this_result = find_single_use_1 (dest, &XEXP (x, i));
 831
 832           if (result == 0)
 833             result = this_result;
 834           else if (this_result)
 835             /* Duplicate usage.  */
 836             return 0;
 837         }
 838       else if (fmt[i] == 'E')
 839         {
 840           int j;
 841
 842           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
 843             {
 844               if (XVECEXP (x, i, j) == dest
 845                   || (GET_CODE (dest) == REG
 846                       && GET_CODE (XVECEXP (x, i, j)) == REG
 847                       && REGNO (XVECEXP (x, i, j)) == REGNO (dest)))
 848                 this_result = loc;
 849               else
 850                 this_result = find_single_use_1 (dest, &XVECEXP (x, i, j));
 851
 852               if (result == 0)
 853                 result = this_result;
 854               else if (this_result)
 855                 return 0;
 856             }
 857         }
 858     }
 859
 860   return result;
 861 }
 862 \f
 863 /* See if DEST, produced in INSN, is used only a single time in the
 864    sequel.  If so, return a pointer to the innermost rtx expression in which
 865    it is used.
 866
 867    If PLOC is non-zero, *PLOC is set to the insn containing the single use.
 868
 869    This routine will return usually zero either before flow is called (because
 870    there will be no LOG_LINKS notes) or after reload (because the REG_DEAD
 871    note can't be trusted).
 872
 873    If DEST is cc0_rtx, we look only at the next insn.  In that case, we don't
 874    care about REG_DEAD notes or LOG_LINKS.
 875
 876    Otherwise, we find the single use by finding an insn that has a
 877    LOG_LINKS pointing at INSN and has a REG_DEAD note for DEST.  If DEST is
 878    only referenced once in that insn, we know that it must be the first
 879    and last insn referencing DEST.  */
 880
 881 rtx *
 882 find_single_use (dest, insn, ploc)
 883      rtx dest;
 884      rtx insn;
 885      rtx *ploc;
 886 {
 887   rtx next;
 888   rtx *result;
 889   rtx link;
 890
 891 #ifdef HAVE_cc0
 892   if (dest == cc0_rtx)
 893     {
 894       next = NEXT_INSN (insn);
 895       if (next == 0
 896           || (GET_CODE (next) != INSN && GET_CODE (next) != JUMP_INSN))
 897         return 0;
 898
 899       result = find_single_use_1 (dest, &PATTERN (next));
 900       if (result && ploc)
 901         *ploc = next;
 902       return result;
 903     }
 904 #endif
 905
 906   if (reload_completed || reload_in_progress || GET_CODE (dest) != REG)
 907     return 0;
 908
 909   for (next = next_nonnote_insn (insn);
 910        next != 0 && GET_CODE (next) != CODE_LABEL;
 911        next = next_nonnote_insn (next))
 912     if (INSN_P (next) && dead_or_set_p (next, dest))
 913       {
 914         for (link = LOG_LINKS (next); link; link = XEXP (link, 1))
 915           if (XEXP (link, 0) == insn)
 916             break;
 917
 918         if (link)
 919           {
 920             result = find_single_use_1 (dest, &PATTERN (next));
 921             if (ploc)
 922               *ploc = next;
 923             return result;
 924           }
 925       }
 926
 927   return 0;
 928 }
 929 \f
 930 /* Return 1 if OP is a valid general operand for machine mode MODE.
 931    This is either a register reference, a memory reference,
 932    or a constant.  In the case of a memory reference, the address
 933    is checked for general validity for the target machine.
 934
 935    Register and memory references must have mode MODE in order to be valid,
 936    but some constants have no machine mode and are valid for any mode.
 937
 938    If MODE is VOIDmode, OP is checked for validity for whatever mode
 939    it has.
 940
 941    The main use of this function is as a predicate in match_operand
 942    expressions in the machine description.
 943
 944    For an explanation of this function's behavior for registers of
 945    class NO_REGS, see the comment for `register_operand'.  */
 946
 947 int
 948 general_operand (op, mode)
 949      register rtx op;
 950      enum machine_mode mode;
 951 {
 952   register enum rtx_code code = GET_CODE (op);
 953   int mode_altering_drug = 0;
 954
 955   if (mode == VOIDmode)
 956     mode = GET_MODE (op);
 957
 958   /* Don't accept CONST_INT or anything similar
 959      if the caller wants something floating.  */
 960   if (GET_MODE (op) == VOIDmode && mode != VOIDmode
 961       && GET_MODE_CLASS (mode) != MODE_INT
 962       && GET_MODE_CLASS (mode) != MODE_PARTIAL_INT)
 963     return 0;
 964
 965   if (CONSTANT_P (op))
 966     return ((GET_MODE (op) == VOIDmode || GET_MODE (op) == mode
 967              || mode == VOIDmode)
 968 #ifdef LEGITIMATE_PIC_OPERAND_P
 969             && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op))
 970 #endif
 971             && LEGITIMATE_CONSTANT_P (op));
 972
 973   /* Except for certain constants with VOIDmode, already checked for,
 974      OP's mode must match MODE if MODE specifies a mode.  */
 975
 976   if (GET_MODE (op) != mode)
 977     return 0;
 978
 979   if (code == SUBREG)
 980     {
 981 #ifdef INSN_SCHEDULING
 982       /* On machines that have insn scheduling, we want all memory
 983          reference to be explicit, so outlaw paradoxical SUBREGs.  */
 984       if (GET_CODE (SUBREG_REG (op)) == MEM
 985           && GET_MODE_SIZE (mode) > GET_MODE_SIZE (GET_MODE (SUBREG_REG (op))))
 986         return 0;
 987 #endif
 988
 989       op = SUBREG_REG (op);
 990       code = GET_CODE (op);
 991 #if 0
 992       /* No longer needed, since (SUBREG (MEM...))
 993          will load the MEM into a reload reg in the MEM's own mode.  */
 994       mode_altering_drug = 1;
 995 #endif
 996     }
 997
 998   if (code == REG)
 999     /* A register whose class is NO_REGS is not a general operand.  */
1000     return (REGNO (op) >= FIRST_PSEUDO_REGISTER
1001             || REGNO_REG_CLASS (REGNO (op)) != NO_REGS);
1002
1003   if (code == MEM)
1004     {
1005       register rtx y = XEXP (op, 0);
1006
1007       if (! volatile_ok && MEM_VOLATILE_P (op))
1008         return 0;
1009
1010       if (GET_CODE (y) == ADDRESSOF)
1011         return 1;
1012
1013       /* Use the mem's mode, since it will be reloaded thus.  */
1014       mode = GET_MODE (op);
1015       GO_IF_LEGITIMATE_ADDRESS (mode, y, win);
1016     }
1017
1018   /* Pretend this is an operand for now; we'll run force_operand
1019      on its replacement in fixup_var_refs_1.  */
1020   if (code == ADDRESSOF)
1021     return 1;
1022
1023   return 0;
1024
1025  win:
1026   if (mode_altering_drug)
1027     return ! mode_dependent_address_p (XEXP (op, 0));
1028   return 1;
1029 }
1030 \f
1031 /* Return 1 if OP is a valid memory address for a memory reference
1032    of mode MODE.
1033
1034    The main use of this function is as a predicate in match_operand
1035    expressions in the machine description.  */
1036
1037 int
1038 address_operand (op, mode)
1039      register rtx op;
1040      enum machine_mode mode;
1041 {
1042   return memory_address_p (mode, op);
1043 }
1044
1045 /* Return 1 if OP is a register reference of mode MODE.
1046    If MODE is VOIDmode, accept a register in any mode.
1047
1048    The main use of this function is as a predicate in match_operand
1049    expressions in the machine description.
1050
1051    As a special exception, registers whose class is NO_REGS are
1052    not accepted by `register_operand'.  The reason for this change
1053    is to allow the representation of special architecture artifacts
1054    (such as a condition code register) without extending the rtl
1055    definitions.  Since registers of class NO_REGS cannot be used
1056    as registers in any case where register classes are examined,
1057    it is most consistent to keep this function from accepting them.  */
1058
1059 int
1060 register_operand (op, mode)
1061      register rtx op;
1062      enum machine_mode mode;
1063 {
1064   if (GET_MODE (op) != mode && mode != VOIDmode)
1065     return 0;
1066
1067   if (GET_CODE (op) == SUBREG)
1068     {
1069       /* Before reload, we can allow (SUBREG (MEM...)) as a register operand
1070          because it is guaranteed to be reloaded into one.
1071          Just make sure the MEM is valid in itself.
1072          (Ideally, (SUBREG (MEM)...) should not exist after reload,
1073          but currently it does result from (SUBREG (REG)...) where the
1074          reg went on the stack.)  */
1075       if (! reload_completed && GET_CODE (SUBREG_REG (op)) == MEM)
1076         return general_operand (op, mode);
1077
1078 #ifdef CLASS_CANNOT_CHANGE_MODE
1079       if (GET_CODE (SUBREG_REG (op)) == REG
1080           && REGNO (SUBREG_REG (op)) < FIRST_PSEUDO_REGISTER
1081           && (TEST_HARD_REG_BIT
1082               (reg_class_contents[(int) CLASS_CANNOT_CHANGE_MODE],
1083                REGNO (SUBREG_REG (op))))
1084           && CLASS_CANNOT_CHANGE_MODE_P (mode, GET_MODE (SUBREG_REG (op)))
1085           && GET_MODE_CLASS (GET_MODE (SUBREG_REG (op))) != MODE_COMPLEX_INT
1086           && GET_MODE_CLASS (GET_MODE (SUBREG_REG (op))) != MODE_COMPLEX_FLOAT)
1087         return 0;
1088 #endif
1089
1090       op = SUBREG_REG (op);
1091     }
1092
1093   /* If we have an ADDRESSOF, consider it valid since it will be
1094      converted into something that will not be a MEM. */
1095   if (GET_CODE (op) == ADDRESSOF)
1096     return 1;
1097
1098   /* We don't consider registers whose class is NO_REGS
1099      to be a register operand.  */
1100   return (GET_CODE (op) == REG
1101           && (REGNO (op) >= FIRST_PSEUDO_REGISTER
1102               || REGNO_REG_CLASS (REGNO (op)) != NO_REGS));
1103 }
1104
1105 /* Return 1 for a register in Pmode; ignore the tested mode.  */
1106
1107 int
1108 pmode_register_operand (op, mode)
1109      rtx op;
1110      enum machine_mode mode ATTRIBUTE_UNUSED;
1111 {
1112   return register_operand (op, Pmode);
1113 }
1114
1115 /* Return 1 if OP should match a MATCH_SCRATCH, i.e., if it is a SCRATCH
1116    or a hard register.  */
1117
1118 int
1119 scratch_operand (op, mode)
1120      register rtx op;
1121      enum machine_mode mode;
1122 {
1123   if (GET_MODE (op) != mode && mode != VOIDmode)
1124     return 0;
1125
1126   return (GET_CODE (op) == SCRATCH
1127           || (GET_CODE (op) == REG
1128               && REGNO (op) < FIRST_PSEUDO_REGISTER));
1129 }
1130
1131 /* Return 1 if OP is a valid immediate operand for mode MODE.
1132
1133    The main use of this function is as a predicate in match_operand
1134    expressions in the machine description.  */
1135
1136 int
1137 immediate_operand (op, mode)
1138      register rtx op;
1139      enum machine_mode mode;
1140 {
1141   /* Don't accept CONST_INT or anything similar
1142      if the caller wants something floating.  */
1143   if (GET_MODE (op) == VOIDmode && mode != VOIDmode
1144       && GET_MODE_CLASS (mode) != MODE_INT
1145       && GET_MODE_CLASS (mode) != MODE_PARTIAL_INT)
1146     return 0;
1147
1148   /* Accept CONSTANT_P_RTX, since it will be gone by CSE1 and
1149      result in 0/1.  It seems a safe assumption that this is
1150      in range for everyone.  */
1151   if (GET_CODE (op) == CONSTANT_P_RTX)
1152     return 1;
1153
1154   return (CONSTANT_P (op)
1155           && (GET_MODE (op) == mode || mode == VOIDmode
1156               || GET_MODE (op) == VOIDmode)
1157 #ifdef LEGITIMATE_PIC_OPERAND_P
1158           && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op))
1159 #endif
1160           && LEGITIMATE_CONSTANT_P (op));
1161 }
1162
1163 /* Returns 1 if OP is an operand that is a CONST_INT.  */
1164
1165 int
1166 const_int_operand (op, mode)
1167      register rtx op;
1168      enum machine_mode mode ATTRIBUTE_UNUSED;
1169 {
1170   return GET_CODE (op) == CONST_INT;
1171 }
1172
1173 /* Returns 1 if OP is an operand that is a constant integer or constant
1174    floating-point number.  */
1175
1176 int
1177 const_double_operand (op, mode)
1178      register rtx op;
1179      enum machine_mode mode;
1180 {
1181   /* Don't accept CONST_INT or anything similar
1182      if the caller wants something floating.  */
1183   if (GET_MODE (op) == VOIDmode && mode != VOIDmode
1184       && GET_MODE_CLASS (mode) != MODE_INT
1185       && GET_MODE_CLASS (mode) != MODE_PARTIAL_INT)
1186     return 0;
1187
1188   return ((GET_CODE (op) == CONST_DOUBLE || GET_CODE (op) == CONST_INT)
1189           && (mode == VOIDmode || GET_MODE (op) == mode
1190               || GET_MODE (op) == VOIDmode));
1191 }
1192
1193 /* Return 1 if OP is a general operand that is not an immediate operand.  */
1194
1195 int
1196 nonimmediate_operand (op, mode)
1197      register rtx op;
1198      enum machine_mode mode;
1199 {
1200   return (general_operand (op, mode) && ! CONSTANT_P (op));
1201 }
1202
1203 /* Return 1 if OP is a register reference or immediate value of mode MODE.  */
1204
1205 int
1206 nonmemory_operand (op, mode)
1207      register rtx op;
1208      enum machine_mode mode;
1209 {
1210   if (CONSTANT_P (op))
1211     {
1212       /* Don't accept CONST_INT or anything similar
1213          if the caller wants something floating.  */
1214       if (GET_MODE (op) == VOIDmode && mode != VOIDmode
1215           && GET_MODE_CLASS (mode) != MODE_INT
1216           && GET_MODE_CLASS (mode) != MODE_PARTIAL_INT)
1217         return 0;
1218
1219       return ((GET_MODE (op) == VOIDmode || GET_MODE (op) == mode
1220               || mode == VOIDmode)
1221 #ifdef LEGITIMATE_PIC_OPERAND_P
1222               && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op))
1223 #endif
1224               && LEGITIMATE_CONSTANT_P (op));
1225     }
1226
1227   if (GET_MODE (op) != mode && mode != VOIDmode)
1228     return 0;
1229
1230   if (GET_CODE (op) == SUBREG)
1231     {
1232       /* Before reload, we can allow (SUBREG (MEM...)) as a register operand
1233          because it is guaranteed to be reloaded into one.
1234          Just make sure the MEM is valid in itself.
1235          (Ideally, (SUBREG (MEM)...) should not exist after reload,
1236          but currently it does result from (SUBREG (REG)...) where the
1237          reg went on the stack.)  */
1238       if (! reload_completed && GET_CODE (SUBREG_REG (op)) == MEM)
1239         return general_operand (op, mode);
1240       op = SUBREG_REG (op);
1241     }
1242
1243   /* We don't consider registers whose class is NO_REGS
1244      to be a register operand.  */
1245   return (GET_CODE (op) == REG
1246           && (REGNO (op) >= FIRST_PSEUDO_REGISTER
1247               || REGNO_REG_CLASS (REGNO (op)) != NO_REGS));
1248 }
1249
1250 /* Return 1 if OP is a valid operand that stands for pushing a
1251    value of mode MODE onto the stack.
1252
1253    The main use of this function is as a predicate in match_operand
1254    expressions in the machine description.  */
1255
1256 int
1257 push_operand (op, mode)
1258      rtx op;
1259      enum machine_mode mode;
1260 {
1261   if (GET_CODE (op) != MEM)
1262     return 0;
1263
1264   if (mode != VOIDmode && GET_MODE (op) != mode)
1265     return 0;
1266
1267   op = XEXP (op, 0);
1268
1269   if (GET_CODE (op) != STACK_PUSH_CODE)
1270     return 0;
1271
1272   return XEXP (op, 0) == stack_pointer_rtx;
1273 }
1274
1275 /* Return 1 if OP is a valid operand that stands for popping a
1276    value of mode MODE off the stack.
1277
1278    The main use of this function is as a predicate in match_operand
1279    expressions in the machine description.  */
1280
1281 int
1282 pop_operand (op, mode)
1283      rtx op;
1284      enum machine_mode mode;
1285 {
1286   if (GET_CODE (op) != MEM)
1287     return 0;
1288
1289   if (mode != VOIDmode && GET_MODE (op) != mode)
1290     return 0;
1291
1292   op = XEXP (op, 0);
1293
1294   if (GET_CODE (op) != STACK_POP_CODE)
1295     return 0;
1296
1297   return XEXP (op, 0) == stack_pointer_rtx;
1298 }
1299
1300 /* Return 1 if ADDR is a valid memory address for mode MODE.  */
1301
1302 int
1303 memory_address_p (mode, addr)
1304      enum machine_mode mode ATTRIBUTE_UNUSED;
1305      register rtx addr;
1306 {
1307   if (GET_CODE (addr) == ADDRESSOF)
1308     return 1;
1309
1310   GO_IF_LEGITIMATE_ADDRESS (mode, addr, win);
1311   return 0;
1312
1313  win:
1314   return 1;
1315 }
1316
1317 /* Return 1 if OP is a valid memory reference with mode MODE,
1318    including a valid address.
1319
1320    The main use of this function is as a predicate in match_operand
1321    expressions in the machine description.  */
1322
1323 int
1324 memory_operand (op, mode)
1325      register rtx op;
1326      enum machine_mode mode;
1327 {
1328   rtx inner;
1329
1330   if (! reload_completed)
1331     /* Note that no SUBREG is a memory operand before end of reload pass,
1332        because (SUBREG (MEM...)) forces reloading into a register.  */
1333     return GET_CODE (op) == MEM && general_operand (op, mode);
1334
1335   if (mode != VOIDmode && GET_MODE (op) != mode)
1336     return 0;
1337
1338   inner = op;
1339   if (GET_CODE (inner) == SUBREG)
1340     inner = SUBREG_REG (inner);
1341
1342   return (GET_CODE (inner) == MEM && general_operand (op, mode));
1343 }
1344
1345 /* Return 1 if OP is a valid indirect memory reference with mode MODE;
1346    that is, a memory reference whose address is a general_operand.  */
1347
1348 int
1349 indirect_operand (op, mode)
1350      register rtx op;
1351      enum machine_mode mode;
1352 {
1353   /* Before reload, a SUBREG isn't in memory (see memory_operand, above).  */
1354   if (! reload_completed
1355       && GET_CODE (op) == SUBREG && GET_CODE (SUBREG_REG (op)) == MEM)
1356     {
1357       register int offset = SUBREG_WORD (op) * UNITS_PER_WORD;
1358       rtx inner = SUBREG_REG (op);
1359
1360       if (BYTES_BIG_ENDIAN)
1361         offset -= (MIN (UNITS_PER_WORD, GET_MODE_SIZE (GET_MODE (op)))
1362                    - MIN (UNITS_PER_WORD, GET_MODE_SIZE (GET_MODE (inner))));
1363
1364       if (mode != VOIDmode && GET_MODE (op) != mode)
1365         return 0;
1366
1367       /* The only way that we can have a general_operand as the resulting
1368          address is if OFFSET is zero and the address already is an operand
1369          or if the address is (plus Y (const_int -OFFSET)) and Y is an
1370          operand.  */
1371
1372       return ((offset == 0 && general_operand (XEXP (inner, 0), Pmode))
1373               || (GET_CODE (XEXP (inner, 0)) == PLUS
1374                   && GET_CODE (XEXP (XEXP (inner, 0), 1)) == CONST_INT
1375                   && INTVAL (XEXP (XEXP (inner, 0), 1)) == -offset
1376                   && general_operand (XEXP (XEXP (inner, 0), 0), Pmode)));
1377     }
1378
1379   return (GET_CODE (op) == MEM
1380           && memory_operand (op, mode)
1381           && general_operand (XEXP (op, 0), Pmode));
1382 }
1383
1384 /* Return 1 if this is a comparison operator.  This allows the use of
1385    MATCH_OPERATOR to recognize all the branch insns.  */
1386
1387 int
1388 comparison_operator (op, mode)
1389     register rtx op;
1390     enum machine_mode mode;
1391 {
1392   return ((mode == VOIDmode || GET_MODE (op) == mode)
1393           && GET_RTX_CLASS (GET_CODE (op)) == '<');
1394 }
1395 \f
1396 /* If BODY is an insn body that uses ASM_OPERANDS,
1397    return the number of operands (both input and output) in the insn.
1398    Otherwise return -1.  */
1399
1400 int
1401 asm_noperands (body)
1402      rtx body;
1403 {
1404   switch (GET_CODE (body))
1405     {
1406     case ASM_OPERANDS:
1407       /* No output operands: return number of input operands.  */
1408       return ASM_OPERANDS_INPUT_LENGTH (body);
1409     case SET:
1410       if (GET_CODE (SET_SRC (body)) == ASM_OPERANDS)
1411         /* Single output operand: BODY is (set OUTPUT (asm_operands ...)).  */
1412         return ASM_OPERANDS_INPUT_LENGTH (SET_SRC (body)) + 1;
1413       else
1414         return -1;
1415     case PARALLEL:
1416       if (GET_CODE (XVECEXP (body, 0, 0)) == SET
1417           && GET_CODE (SET_SRC (XVECEXP (body, 0, 0))) == ASM_OPERANDS)
1418         {
1419           /* Multiple output operands, or 1 output plus some clobbers:
1420              body is [(set OUTPUT (asm_operands ...))... (clobber (reg ...))...].  */
1421           int i;
1422           int n_sets;
1423
1424           /* Count backwards through CLOBBERs to determine number of SETs.  */
1425           for (i = XVECLEN (body, 0); i > 0; i--)
1426             {
1427               if (GET_CODE (XVECEXP (body, 0, i - 1)) == SET)
1428                 break;
1429               if (GET_CODE (XVECEXP (body, 0, i - 1)) != CLOBBER)
1430                 return -1;
1431             }
1432
1433           /* N_SETS is now number of output operands.  */
1434           n_sets = i;
1435
1436           /* Verify that all the SETs we have
1437              came from a single original asm_operands insn
1438              (so that invalid combinations are blocked).  */
1439           for (i = 0; i < n_sets; i++)
1440             {
1441               rtx elt = XVECEXP (body, 0, i);
1442               if (GET_CODE (elt) != SET)
1443                 return -1;
1444               if (GET_CODE (SET_SRC (elt)) != ASM_OPERANDS)
1445                 return -1;
1446               /* If these ASM_OPERANDS rtx's came from different original insns
1447                  then they aren't allowed together.  */
1448               if (ASM_OPERANDS_INPUT_VEC (SET_SRC (elt))
1449                   != ASM_OPERANDS_INPUT_VEC (SET_SRC (XVECEXP (body, 0, 0))))
1450                 return -1;
1451             }
1452           return (ASM_OPERANDS_INPUT_LENGTH (SET_SRC (XVECEXP (body, 0, 0)))
1453                   + n_sets);
1454         }
1455       else if (GET_CODE (XVECEXP (body, 0, 0)) == ASM_OPERANDS)
1456         {
1457           /* 0 outputs, but some clobbers:
1458              body is [(asm_operands ...) (clobber (reg ...))...].  */
1459           int i;
1460
1461           /* Make sure all the other parallel things really are clobbers.  */
1462           for (i = XVECLEN (body, 0) - 1; i > 0; i--)
1463             if (GET_CODE (XVECEXP (body, 0, i)) != CLOBBER)
1464               return -1;
1465
1466           return ASM_OPERANDS_INPUT_LENGTH (XVECEXP (body, 0, 0));
1467         }
1468       else
1469         return -1;
1470     default:
1471       return -1;
1472     }
1473 }
1474
1475 /* Assuming BODY is an insn body that uses ASM_OPERANDS,
1476    copy its operands (both input and output) into the vector OPERANDS,
1477    the locations of the operands within the insn into the vector OPERAND_LOCS,
1478    and the constraints for the operands into CONSTRAINTS.
1479    Write the modes of the operands into MODES.
1480    Return the assembler-template.
1481
1482    If MODES, OPERAND_LOCS, CONSTRAINTS or OPERANDS is 0,
1483    we don't store that info.  */
1484
1485 const char *
1486 decode_asm_operands (body, operands, operand_locs, constraints, modes)
1487      rtx body;
1488      rtx *operands;
1489      rtx **operand_locs;
1490      const char **constraints;
1491      enum machine_mode *modes;
1492 {
1493   register int i;
1494   int noperands;
1495   const char *template = 0;
1496
1497   if (GET_CODE (body) == SET && GET_CODE (SET_SRC (body)) == ASM_OPERANDS)
1498     {
1499       rtx asmop = SET_SRC (body);
1500       /* Single output operand: BODY is (set OUTPUT (asm_operands ....)).  */
1501
1502       noperands = ASM_OPERANDS_INPUT_LENGTH (asmop) + 1;
1503
1504       for (i = 1; i < noperands; i++)
1505         {
1506           if (operand_locs)
1507             operand_locs[i] = &ASM_OPERANDS_INPUT (asmop, i - 1);
1508           if (operands)
1509             operands[i] = ASM_OPERANDS_INPUT (asmop, i - 1);
1510           if (constraints)
1511             constraints[i] = ASM_OPERANDS_INPUT_CONSTRAINT (asmop, i - 1);
1512           if (modes)
1513             modes[i] = ASM_OPERANDS_INPUT_MODE (asmop, i - 1);
1514         }
1515
1516       /* The output is in the SET.
1517          Its constraint is in the ASM_OPERANDS itself.  */
1518       if (operands)
1519         operands[0] = SET_DEST (body);
1520       if (operand_locs)
1521         operand_locs[0] = &SET_DEST (body);
1522       if (constraints)
1523         constraints[0] = ASM_OPERANDS_OUTPUT_CONSTRAINT (asmop);
1524       if (modes)
1525         modes[0] = GET_MODE (SET_DEST (body));
1526       template = ASM_OPERANDS_TEMPLATE (asmop);
1527     }
1528   else if (GET_CODE (body) == ASM_OPERANDS)
1529     {
1530       rtx asmop = body;
1531       /* No output operands: BODY is (asm_operands ....).  */
1532
1533       noperands = ASM_OPERANDS_INPUT_LENGTH (asmop);
1534
1535       /* The input operands are found in the 1st element vector.  */
1536       /* Constraints for inputs are in the 2nd element vector.  */
1537       for (i = 0; i < noperands; i++)
1538         {
1539           if (operand_locs)
1540             operand_locs[i] = &ASM_OPERANDS_INPUT (asmop, i);
1541           if (operands)
1542             operands[i] = ASM_OPERANDS_INPUT (asmop, i);
1543           if (constraints)
1544             constraints[i] = ASM_OPERANDS_INPUT_CONSTRAINT (asmop, i);
1545           if (modes)
1546             modes[i] = ASM_OPERANDS_INPUT_MODE (asmop, i);
1547         }
1548       template = ASM_OPERANDS_TEMPLATE (asmop);
1549     }
1550   else if (GET_CODE (body) == PARALLEL
1551            && GET_CODE (XVECEXP (body, 0, 0)) == SET)
1552     {
1553       rtx asmop = SET_SRC (XVECEXP (body, 0, 0));
1554       int nparallel = XVECLEN (body, 0); /* Includes CLOBBERs.  */
1555       int nin = ASM_OPERANDS_INPUT_LENGTH (asmop);
1556       int nout = 0;             /* Does not include CLOBBERs.  */
1557
1558       /* At least one output, plus some CLOBBERs.  */
1559
1560       /* The outputs are in the SETs.
1561          Their constraints are in the ASM_OPERANDS itself.  */
1562       for (i = 0; i < nparallel; i++)
1563         {
1564           if (GET_CODE (XVECEXP (body, 0, i)) == CLOBBER)
1565             break;              /* Past last SET */
1566
1567           if (operands)
1568             operands[i] = SET_DEST (XVECEXP (body, 0, i));
1569           if (operand_locs)
1570             operand_locs[i] = &SET_DEST (XVECEXP (body, 0, i));
1571           if (constraints)
1572             constraints[i] = XSTR (SET_SRC (XVECEXP (body, 0, i)), 1);
1573           if (modes)
1574             modes[i] = GET_MODE (SET_DEST (XVECEXP (body, 0, i)));
1575           nout++;
1576         }
1577
1578       for (i = 0; i < nin; i++)
1579         {
1580           if (operand_locs)
1581             operand_locs[i + nout] = &ASM_OPERANDS_INPUT (asmop, i);
1582           if (operands)
1583             operands[i + nout] = ASM_OPERANDS_INPUT (asmop, i);
1584           if (constraints)
1585             constraints[i + nout] = ASM_OPERANDS_INPUT_CONSTRAINT (asmop, i);
1586           if (modes)
1587             modes[i + nout] = ASM_OPERANDS_INPUT_MODE (asmop, i);
1588         }
1589
1590       template = ASM_OPERANDS_TEMPLATE (asmop);
1591     }
1592   else if (GET_CODE (body) == PARALLEL
1593            && GET_CODE (XVECEXP (body, 0, 0)) == ASM_OPERANDS)
1594     {
1595       /* No outputs, but some CLOBBERs.  */
1596
1597       rtx asmop = XVECEXP (body, 0, 0);
1598       int nin = ASM_OPERANDS_INPUT_LENGTH (asmop);
1599
1600       for (i = 0; i < nin; i++)
1601         {
1602           if (operand_locs)
1603             operand_locs[i] = &ASM_OPERANDS_INPUT (asmop, i);
1604           if (operands)
1605             operands[i] = ASM_OPERANDS_INPUT (asmop, i);
1606           if (constraints)
1607             constraints[i] = ASM_OPERANDS_INPUT_CONSTRAINT (asmop, i);
1608           if (modes)
1609             modes[i] = ASM_OPERANDS_INPUT_MODE (asmop, i);
1610         }
1611
1612       template = ASM_OPERANDS_TEMPLATE (asmop);
1613     }
1614
1615   return template;
1616 }
1617
1618 /* Check if an asm_operand matches it's constraints.
1619    Return > 0 if ok, = 0 if bad, < 0 if inconclusive.  */
1620
1621 int
1622 asm_operand_ok (op, constraint)
1623      rtx op;
1624      const char *constraint;
1625 {
1626   int result = 0;
1627
1628   /* Use constrain_operands after reload.  */
1629   if (reload_completed)
1630     abort ();
1631
1632   while (*constraint)
1633     {
1634       char c = *constraint++;
1635       switch (c)
1636         {
1637         case '=':
1638         case '+':
1639         case '*':
1640         case '%':
1641         case '?':
1642         case '!':
1643         case '#':
1644         case '&':
1645         case ',':
1646           break;
1647
1648         case '0': case '1': case '2': case '3': case '4':
1649         case '5': case '6': case '7': case '8': case '9':
1650           /* For best results, our caller should have given us the
1651              proper matching constraint, but we can't actually fail
1652              the check if they didn't.  Indicate that results are
1653              inconclusive.  */
1654           result = -1;
1655           break;
1656
1657         case 'p':
1658           if (address_operand (op, VOIDmode))
1659             return 1;
1660           break;
1661
1662         case 'm':
1663         case 'V': /* non-offsettable */
1664           if (memory_operand (op, VOIDmode))
1665             return 1;
1666           break;
1667
1668         case 'o': /* offsettable */
1669           if (offsettable_nonstrict_memref_p (op))
1670             return 1;
1671           break;
1672
1673         case '<':
1674           /* ??? Before flow, auto inc/dec insns are not supposed to exist,
1675              excepting those that expand_call created.  Further, on some
1676              machines which do not have generalized auto inc/dec, an inc/dec
1677              is not a memory_operand.
1678
1679              Match any memory and hope things are resolved after reload.  */
1680
1681           if (GET_CODE (op) == MEM
1682               && (1
1683                   || GET_CODE (XEXP (op, 0)) == PRE_DEC
1684                   || GET_CODE (XEXP (op, 0)) == POST_DEC))
1685             return 1;
1686           break;
1687
1688         case '>':
1689           if (GET_CODE (op) == MEM
1690               && (1
1691                   || GET_CODE (XEXP (op, 0)) == PRE_INC
1692                   || GET_CODE (XEXP (op, 0)) == POST_INC))
1693             return 1;
1694           break;
1695
1696         case 'E':
1697 #ifndef REAL_ARITHMETIC
1698           /* Match any floating double constant, but only if
1699              we can examine the bits of it reliably.  */
1700           if ((HOST_FLOAT_FORMAT != TARGET_FLOAT_FORMAT
1701                || HOST_BITS_PER_WIDE_INT != BITS_PER_WORD)
1702               && GET_MODE (op) != VOIDmode && ! flag_pretend_float)
1703             break;
1704 #endif
1705           /* FALLTHRU */
1706
1707         case 'F':
1708           if (GET_CODE (op) == CONST_DOUBLE)
1709             return 1;
1710           break;
1711
1712         case 'G':
1713           if (GET_CODE (op) == CONST_DOUBLE
1714               && CONST_DOUBLE_OK_FOR_LETTER_P (op, 'G'))
1715             return 1;
1716           break;
1717         case 'H':
1718           if (GET_CODE (op) == CONST_DOUBLE
1719               && CONST_DOUBLE_OK_FOR_LETTER_P (op, 'H'))
1720             return 1;
1721           break;
1722
1723         case 's':
1724           if (GET_CODE (op) == CONST_INT
1725               || (GET_CODE (op) == CONST_DOUBLE
1726                   && GET_MODE (op) == VOIDmode))
1727             break;
1728           /* FALLTHRU */
1729
1730         case 'i':
1731           if (CONSTANT_P (op)
1732 #ifdef LEGITIMATE_PIC_OPERAND_P
1733               && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op))
1734 #endif
1735               )
1736             return 1;
1737           break;
1738
1739         case 'n':
1740           if (GET_CODE (op) == CONST_INT
1741               || (GET_CODE (op) == CONST_DOUBLE
1742                   && GET_MODE (op) == VOIDmode))
1743             return 1;
1744           break;
1745
1746         case 'I':
1747           if (GET_CODE (op) == CONST_INT
1748               && CONST_OK_FOR_LETTER_P (INTVAL (op), 'I'))
1749             return 1;
1750           break;
1751         case 'J':
1752           if (GET_CODE (op) == CONST_INT
1753               && CONST_OK_FOR_LETTER_P (INTVAL (op), 'J'))
1754             return 1;
1755           break;
1756         case 'K':
1757           if (GET_CODE (op) == CONST_INT
1758               && CONST_OK_FOR_LETTER_P (INTVAL (op), 'K'))
1759             return 1;
1760           break;
1761         case 'L':
1762           if (GET_CODE (op) == CONST_INT
1763               && CONST_OK_FOR_LETTER_P (INTVAL (op), 'L'))
1764             return 1;
1765           break;
1766         case 'M':
1767           if (GET_CODE (op) == CONST_INT
1768               && CONST_OK_FOR_LETTER_P (INTVAL (op), 'M'))
1769             return 1;
1770           break;
1771         case 'N':
1772           if (GET_CODE (op) == CONST_INT
1773               && CONST_OK_FOR_LETTER_P (INTVAL (op), 'N'))
1774             return 1;
1775           break;
1776         case 'O':
1777           if (GET_CODE (op) == CONST_INT
1778               && CONST_OK_FOR_LETTER_P (INTVAL (op), 'O'))
1779             return 1;
1780           break;
1781         case 'P':
1782           if (GET_CODE (op) == CONST_INT
1783               && CONST_OK_FOR_LETTER_P (INTVAL (op), 'P'))
1784             return 1;
1785           break;
1786
1787         case 'X':
1788           return 1;
1789
1790         case 'g':
1791           if (general_operand (op, VOIDmode))
1792             return 1;
1793           break;
1794
1795         default:
1796           /* For all other letters, we first check for a register class,
1797              otherwise it is an EXTRA_CONSTRAINT.  */
1798           if (REG_CLASS_FROM_LETTER (c) != NO_REGS)
1799             {
1800             case 'r':
1801               if (GET_MODE (op) == BLKmode)
1802                 break;
1803               if (register_operand (op, VOIDmode))
1804                 return 1;
1805             }
1806 #ifdef EXTRA_CONSTRAINT
1807           if (EXTRA_CONSTRAINT (op, c))
1808             return 1;
1809 #endif
1810           break;
1811         }
1812     }
1813
1814   return result;
1815 }
1816 \f
1817 /* Given an rtx *P, if it is a sum containing an integer constant term,
1818    return the location (type rtx *) of the pointer to that constant term.
1819    Otherwise, return a null pointer.  */
1820
1821 static rtx *
1822 find_constant_term_loc (p)
1823      rtx *p;
1824 {
1825   register rtx *tem;
1826   register enum rtx_code code = GET_CODE (*p);
1827
1828   /* If *P IS such a constant term, P is its location.  */
1829
1830   if (code == CONST_INT || code == SYMBOL_REF || code == LABEL_REF
1831       || code == CONST)
1832     return p;
1833
1834   /* Otherwise, if not a sum, it has no constant term.  */
1835
1836   if (GET_CODE (*p) != PLUS)
1837     return 0;
1838
1839   /* If one of the summands is constant, return its location.  */
1840
1841   if (XEXP (*p, 0) && CONSTANT_P (XEXP (*p, 0))
1842       && XEXP (*p, 1) && CONSTANT_P (XEXP (*p, 1)))
1843     return p;
1844
1845   /* Otherwise, check each summand for containing a constant term.  */
1846
1847   if (XEXP (*p, 0) != 0)
1848     {
1849       tem = find_constant_term_loc (&XEXP (*p, 0));
1850       if (tem != 0)
1851         return tem;
1852     }
1853
1854   if (XEXP (*p, 1) != 0)
1855     {
1856       tem = find_constant_term_loc (&XEXP (*p, 1));
1857       if (tem != 0)
1858         return tem;
1859     }
1860
1861   return 0;
1862 }
1863 \f
1864 /* Return 1 if OP is a memory reference
1865    whose address contains no side effects
1866    and remains valid after the addition
1867    of a positive integer less than the
1868    size of the object being referenced.
1869
1870    We assume that the original address is valid and do not check it.
1871
1872    This uses strict_memory_address_p as a subroutine, so
1873    don't use it before reload.  */
1874
1875 int
1876 offsettable_memref_p (op)
1877      rtx op;
1878 {
1879   return ((GET_CODE (op) == MEM)
1880           && offsettable_address_p (1, GET_MODE (op), XEXP (op, 0)));
1881 }
1882
1883 /* Similar, but don't require a strictly valid mem ref:
1884    consider pseudo-regs valid as index or base regs.  */
1885
1886 int
1887 offsettable_nonstrict_memref_p (op)
1888      rtx op;
1889 {
1890   return ((GET_CODE (op) == MEM)
1891           && offsettable_address_p (0, GET_MODE (op), XEXP (op, 0)));
1892 }
1893
1894 /* Return 1 if Y is a memory address which contains no side effects
1895    and would remain valid after the addition of a positive integer
1896    less than the size of that mode.
1897
1898    We assume that the original address is valid and do not check it.
1899    We do check that it is valid for narrower modes.
1900
1901    If STRICTP is nonzero, we require a strictly valid address,
1902    for the sake of use in reload.c.  */
1903
1904 int
1905 offsettable_address_p (strictp, mode, y)
1906      int strictp;
1907      enum machine_mode mode;
1908      register rtx y;
1909 {
1910   register enum rtx_code ycode = GET_CODE (y);
1911   register rtx z;
1912   rtx y1 = y;
1913   rtx *y2;
1914   int (*addressp) PARAMS ((enum machine_mode, rtx)) =
1915     (strictp ? strict_memory_address_p : memory_address_p);
1916   unsigned int mode_sz = GET_MODE_SIZE (mode);
1917
1918   if (CONSTANT_ADDRESS_P (y))
1919     return 1;
1920
1921   /* Adjusting an offsettable address involves changing to a narrower mode.
1922      Make sure that's OK.  */
1923
1924   if (mode_dependent_address_p (y))
1925     return 0;
1926
1927   /* ??? How much offset does an offsettable BLKmode reference need?
1928      Clearly that depends on the situation in which it's being used.
1929      However, the current situation in which we test 0xffffffff is
1930      less than ideal.  Caveat user.  */
1931   if (mode_sz == 0)
1932     mode_sz = BIGGEST_ALIGNMENT / BITS_PER_UNIT;
1933
1934   /* If the expression contains a constant term,
1935      see if it remains valid when max possible offset is added.  */
1936
1937   if ((ycode == PLUS) && (y2 = find_constant_term_loc (&y1)))
1938     {
1939       int good;
1940
1941       y1 = *y2;
1942       *y2 = plus_constant (*y2, mode_sz - 1);
1943       /* Use QImode because an odd displacement may be automatically invalid
1944          for any wider mode.  But it should be valid for a single byte.  */
1945       good = (*addressp) (QImode, y);
1946
1947       /* In any case, restore old contents of memory.  */
1948       *y2 = y1;
1949       return good;
1950     }
1951
1952   if (GET_RTX_CLASS (ycode) == 'a')
1953     return 0;
1954
1955   /* The offset added here is chosen as the maximum offset that
1956      any instruction could need to add when operating on something
1957      of the specified mode.  We assume that if Y and Y+c are
1958      valid addresses then so is Y+d for all 0<d<c.  */
1959
1960   z = plus_constant_for_output (y, mode_sz - 1);
1961
1962   /* Use QImode because an odd displacement may be automatically invalid
1963      for any wider mode.  But it should be valid for a single byte.  */
1964   return (*addressp) (QImode, z);
1965 }
1966
1967 /* Return 1 if ADDR is an address-expression whose effect depends
1968    on the mode of the memory reference it is used in.
1969
1970    Autoincrement addressing is a typical example of mode-dependence
1971    because the amount of the increment depends on the mode.  */
1972
1973 int
1974 mode_dependent_address_p (addr)
1975   rtx addr ATTRIBUTE_UNUSED; /* Maybe used in GO_IF_MODE_DEPENDENT_ADDRESS. */
1976 {
1977   GO_IF_MODE_DEPENDENT_ADDRESS (addr, win);
1978   return 0;
1979   /* Label `win' might (not) be used via GO_IF_MODE_DEPENDENT_ADDRESS. */
1980  win: ATTRIBUTE_UNUSED_LABEL
1981   return 1;
1982 }
1983
1984 /* Return 1 if OP is a general operand
1985    other than a memory ref with a mode dependent address.  */
1986
1987 int
1988 mode_independent_operand (op, mode)
1989      enum machine_mode mode;
1990      rtx op;
1991 {
1992   rtx addr;
1993
1994   if (! general_operand (op, mode))
1995     return 0;
1996
1997   if (GET_CODE (op) != MEM)
1998     return 1;
1999
2000   addr = XEXP (op, 0);
2001   GO_IF_MODE_DEPENDENT_ADDRESS (addr, lose);
2002   return 1;
2003   /* Label `lose' might (not) be used via GO_IF_MODE_DEPENDENT_ADDRESS. */
2004  lose: ATTRIBUTE_UNUSED_LABEL
2005   return 0;
2006 }
2007
2008 /* Given an operand OP that is a valid memory reference which
2009    satisfies offsettable_memref_p, return a new memory reference whose
2010    address has been adjusted by OFFSET.  OFFSET should be positive and
2011    less than the size of the object referenced.  */
2012
2013 rtx
2014 adj_offsettable_operand (op, offset)
2015      rtx op;
2016      int offset;
2017 {
2018   register enum rtx_code code = GET_CODE (op);
2019
2020   if (code == MEM)
2021     {
2022       register rtx y = XEXP (op, 0);
2023       register rtx new;
2024
2025       if (CONSTANT_ADDRESS_P (y))
2026         {
2027           new = gen_rtx_MEM (GET_MODE (op),
2028                              plus_constant_for_output (y, offset));
2029           MEM_COPY_ATTRIBUTES (new, op);
2030           return new;
2031         }
2032
2033       if (GET_CODE (y) == PLUS)
2034         {
2035           rtx z = y;
2036           register rtx *const_loc;
2037
2038           op = copy_rtx (op);
2039           z = XEXP (op, 0);
2040           const_loc = find_constant_term_loc (&z);
2041           if (const_loc)
2042             {
2043               *const_loc = plus_constant_for_output (*const_loc, offset);
2044               return op;
2045             }
2046         }
2047
2048       new = gen_rtx_MEM (GET_MODE (op), plus_constant_for_output (y, offset));
2049       MEM_COPY_ATTRIBUTES (new, op);
2050       return new;
2051     }
2052   abort ();
2053 }
2054 \f
2055 /* Like extract_insn, but save insn extracted and don't extract again, when
2056    called again for the same insn expecting that recog_data still contain the
2057    valid information.  This is used primary by gen_attr infrastructure that
2058    often does extract insn again and again.  */
2059 void
2060 extract_insn_cached (insn)
2061      rtx insn;
2062 {
2063   if (recog_data.insn == insn && INSN_CODE (insn) >= 0)
2064     return;
2065   extract_insn (insn);
2066   recog_data.insn = insn;
2067 }
2068 /* Do cached extract_insn, constrain_operand and complain about failures.
2069    Used by insn_attrtab.  */
2070 void
2071 extract_constrain_insn_cached (insn)
2072      rtx insn;
2073 {
2074   extract_insn_cached (insn);
2075   if (which_alternative == -1
2076       && !constrain_operands (reload_completed))
2077     fatal_insn_not_found (insn);
2078 }
2079 /* Do cached constrain_operand and complain about failures.  */
2080 int
2081 constrain_operands_cached (strict)
2082         int strict;
2083 {
2084   if (which_alternative == -1)
2085     return constrain_operands (strict);
2086   else
2087     return 1;
2088 }
2089 \f
2090 /* Analyze INSN and fill in recog_data.  */
2091
2092 void
2093 extract_insn (insn)
2094      rtx insn;
2095 {
2096   int i;
2097   int icode;
2098   int noperands;
2099   rtx body = PATTERN (insn);
2100
2101   recog_data.insn = NULL;
2102   recog_data.n_operands = 0;
2103   recog_data.n_alternatives = 0;
2104   recog_data.n_dups = 0;
2105   which_alternative = -1;
2106
2107   switch (GET_CODE (body))
2108     {
2109     case USE:
2110     case CLOBBER:
2111     case ASM_INPUT:
2112     case ADDR_VEC:
2113     case ADDR_DIFF_VEC:
2114       return;
2115
2116     case SET:
2117       if (GET_CODE (SET_SRC (body)) == ASM_OPERANDS)
2118         goto asm_insn;
2119       else
2120         goto normal_insn;
2121     case PARALLEL:
2122       if ((GET_CODE (XVECEXP (body, 0, 0)) == SET
2123            && GET_CODE (SET_SRC (XVECEXP (body, 0, 0))) == ASM_OPERANDS)
2124           || GET_CODE (XVECEXP (body, 0, 0)) == ASM_OPERANDS)
2125         goto asm_insn;
2126       else
2127         goto normal_insn;
2128     case ASM_OPERANDS:
2129     asm_insn:
2130       recog_data.n_operands = noperands = asm_noperands (body);
2131       if (noperands >= 0)
2132         {
2133           /* This insn is an `asm' with operands.  */
2134
2135           /* expand_asm_operands makes sure there aren't too many operands.  */
2136           if (noperands > MAX_RECOG_OPERANDS)
2137             abort ();
2138
2139           /* Now get the operand values and constraints out of the insn.  */
2140           decode_asm_operands (body, recog_data.operand,
2141                                recog_data.operand_loc,
2142                                recog_data.constraints,
2143                                recog_data.operand_mode);
2144           if (noperands > 0)
2145             {
2146               const char *p =  recog_data.constraints[0];
2147               recog_data.n_alternatives = 1;
2148               while (*p)
2149                 recog_data.n_alternatives += (*p++ == ',');
2150             }
2151           break;
2152         }
2153       fatal_insn_not_found (insn);
2154
2155     default:
2156     normal_insn:
2157       /* Ordinary insn: recognize it, get the operands via insn_extract
2158          and get the constraints.  */
2159
2160       icode = recog_memoized (insn);
2161       if (icode < 0)
2162         fatal_insn_not_found (insn);
2163
2164       recog_data.n_operands = noperands = insn_data[icode].n_operands;
2165       recog_data.n_alternatives = insn_data[icode].n_alternatives;
2166       recog_data.n_dups = insn_data[icode].n_dups;
2167
2168       insn_extract (insn);
2169
2170       for (i = 0; i < noperands; i++)
2171         {
2172           recog_data.constraints[i] = insn_data[icode].operand[i].constraint;
2173           recog_data.operand_mode[i] = insn_data[icode].operand[i].mode;
2174           /* VOIDmode match_operands gets mode from their real operand.  */
2175           if (recog_data.operand_mode[i] == VOIDmode)
2176             recog_data.operand_mode[i] = GET_MODE (recog_data.operand[i]);
2177         }
2178     }
2179   for (i = 0; i < noperands; i++)
2180     recog_data.operand_type[i]
2181       = (recog_data.constraints[i][0] == '=' ? OP_OUT
2182          : recog_data.constraints[i][0] == '+' ? OP_INOUT
2183          : OP_IN);
2184
2185   if (recog_data.n_alternatives > MAX_RECOG_ALTERNATIVES)
2186     abort ();
2187 }
2188
2189 /* After calling extract_insn, you can use this function to extract some
2190    information from the constraint strings into a more usable form.
2191    The collected data is stored in recog_op_alt.  */
2192 void
2193 preprocess_constraints ()
2194 {
2195   int i;
2196
2197   memset (recog_op_alt, 0, sizeof recog_op_alt);
2198   for (i = 0; i < recog_data.n_operands; i++)
2199     {
2200       int j;
2201       struct operand_alternative *op_alt;
2202       const char *p = recog_data.constraints[i];
2203
2204       op_alt = recog_op_alt[i];
2205
2206       for (j = 0; j < recog_data.n_alternatives; j++)
2207         {
2208           op_alt[j].class = NO_REGS;
2209           op_alt[j].constraint = p;
2210           op_alt[j].matches = -1;
2211           op_alt[j].matched = -1;
2212
2213           if (*p == '\0' || *p == ',')
2214             {
2215               op_alt[j].anything_ok = 1;
2216               continue;
2217             }
2218
2219           for (;;)
2220             {
2221               char c = *p++;
2222               if (c == '#')
2223                 do
2224                   c = *p++;
2225                 while (c != ',' && c != '\0');
2226               if (c == ',' || c == '\0')
2227                 break;
2228
2229               switch (c)
2230                 {
2231                 case '=': case '+': case '*': case '%':
2232                 case 'E': case 'F': case 'G': case 'H':
2233                 case 's': case 'i': case 'n':
2234                 case 'I': case 'J': case 'K': case 'L':
2235                 case 'M': case 'N': case 'O': case 'P':
2236                   /* These don't say anything we care about.  */
2237                   break;
2238
2239                 case '?':
2240                   op_alt[j].reject += 6;
2241                   break;
2242                 case '!':
2243                   op_alt[j].reject += 600;
2244                   break;
2245                 case '&':
2246                   op_alt[j].earlyclobber = 1;
2247                   break;
2248
2249                 case '0': case '1': case '2': case '3': case '4':
2250                 case '5': case '6': case '7': case '8': case '9':
2251                   op_alt[j].matches = c - '0';
2252                   recog_op_alt[op_alt[j].matches][j].matched = i;
2253                   break;
2254
2255                 case 'm':
2256                   op_alt[j].memory_ok = 1;
2257                   break;
2258                 case '<':
2259                   op_alt[j].decmem_ok = 1;
2260                   break;
2261                 case '>':
2262                   op_alt[j].incmem_ok = 1;
2263                   break;
2264                 case 'V':
2265                   op_alt[j].nonoffmem_ok = 1;
2266                   break;
2267                 case 'o':
2268                   op_alt[j].offmem_ok = 1;
2269                   break;
2270                 case 'X':
2271                   op_alt[j].anything_ok = 1;
2272                   break;
2273
2274                 case 'p':
2275                   op_alt[j].is_address = 1;
2276                   op_alt[j].class = reg_class_subunion[(int) op_alt[j].class][(int) BASE_REG_CLASS];
2277                   break;
2278
2279                 case 'g': case 'r':
2280                   op_alt[j].class = reg_class_subunion[(int) op_alt[j].class][(int) GENERAL_REGS];
2281                   break;
2282
2283                 default:
2284                   op_alt[j].class = reg_class_subunion[(int) op_alt[j].class][(int) REG_CLASS_FROM_LETTER ((unsigned char)c)];
2285                   break;
2286                 }
2287             }
2288         }
2289     }
2290 }
2291
2292 /* Check the operands of an insn against the insn's operand constraints
2293    and return 1 if they are valid.
2294    The information about the insn's operands, constraints, operand modes
2295    etc. is obtained from the global variables set up by extract_insn.
2296
2297    WHICH_ALTERNATIVE is set to a number which indicates which
2298    alternative of constraints was matched: 0 for the first alternative,
2299    1 for the next, etc.
2300
2301    In addition, when two operands are match
2302    and it happens that the output operand is (reg) while the
2303    input operand is --(reg) or ++(reg) (a pre-inc or pre-dec),
2304    make the output operand look like the input.
2305    This is because the output operand is the one the template will print.
2306
2307    This is used in final, just before printing the assembler code and by
2308    the routines that determine an insn's attribute.
2309
2310    If STRICT is a positive non-zero value, it means that we have been
2311    called after reload has been completed.  In that case, we must
2312    do all checks strictly.  If it is zero, it means that we have been called
2313    before reload has completed.  In that case, we first try to see if we can
2314    find an alternative that matches strictly.  If not, we try again, this
2315    time assuming that reload will fix up the insn.  This provides a "best
2316    guess" for the alternative and is used to compute attributes of insns prior
2317    to reload.  A negative value of STRICT is used for this internal call.  */
2318
2319 struct funny_match
2320 {
2321   int this, other;
2322 };
2323
2324 int
2325 constrain_operands (strict)
2326      int strict;
2327 {
2328   const char *constraints[MAX_RECOG_OPERANDS];
2329   int matching_operands[MAX_RECOG_OPERANDS];
2330   int earlyclobber[MAX_RECOG_OPERANDS];
2331   register int c;
2332
2333   struct funny_match funny_match[MAX_RECOG_OPERANDS];
2334   int funny_match_index;
2335
2336   which_alternative = 0;
2337   if (recog_data.n_operands == 0 || recog_data.n_alternatives == 0)
2338     return 1;
2339
2340   for (c = 0; c < recog_data.n_operands; c++)
2341     {
2342       constraints[c] = recog_data.constraints[c];
2343       matching_operands[c] = -1;
2344     }
2345
2346   do
2347     {
2348       register int opno;
2349       int lose = 0;
2350       funny_match_index = 0;
2351
2352       for (opno = 0; opno < recog_data.n_operands; opno++)
2353         {
2354           register rtx op = recog_data.operand[opno];
2355           enum machine_mode mode = GET_MODE (op);
2356           register const char *p = constraints[opno];
2357           int offset = 0;
2358           int win = 0;
2359           int val;
2360
2361           earlyclobber[opno] = 0;
2362
2363           /* A unary operator may be accepted by the predicate, but it
2364              is irrelevant for matching constraints.  */
2365           if (GET_RTX_CLASS (GET_CODE (op)) == '1')
2366             op = XEXP (op, 0);
2367
2368           if (GET_CODE (op) == SUBREG)
2369             {
2370               if (GET_CODE (SUBREG_REG (op)) == REG
2371                   && REGNO (SUBREG_REG (op)) < FIRST_PSEUDO_REGISTER)
2372                 offset = SUBREG_WORD (op);
2373               op = SUBREG_REG (op);
2374             }
2375
2376           /* An empty constraint or empty alternative
2377              allows anything which matched the pattern.  */
2378           if (*p == 0 || *p == ',')
2379             win = 1;
2380
2381           while (*p && (c = *p++) != ',')
2382             switch (c)
2383               {
2384               case '?':  case '!': case '*':  case '%':
2385               case '=':  case '+':
2386                 break;
2387
2388               case '#':
2389                 /* Ignore rest of this alternative as far as
2390                    constraint checking is concerned.  */
2391                 while (*p && *p != ',')
2392                   p++;
2393                 break;
2394
2395               case '&':
2396                 earlyclobber[opno] = 1;
2397                 break;
2398
2399               case '0':  case '1':  case '2':  case '3':  case '4':
2400               case '5':  case '6':  case '7':  case '8':  case '9':
2401
2402                 /* This operand must be the same as a previous one.
2403                    This kind of constraint is used for instructions such
2404                    as add when they take only two operands.
2405
2406                    Note that the lower-numbered operand is passed first.
2407
2408                    If we are not testing strictly, assume that this constraint
2409                    will be satisfied.  */
2410                 if (strict < 0)
2411                   val = 1;
2412                 else
2413                   {
2414                     rtx op1 = recog_data.operand[c - '0'];
2415                     rtx op2 = recog_data.operand[opno];
2416
2417                     /* A unary operator may be accepted by the predicate,
2418                        but it is irrelevant for matching constraints.  */
2419                     if (GET_RTX_CLASS (GET_CODE (op1)) == '1')
2420                       op1 = XEXP (op1, 0);
2421                     if (GET_RTX_CLASS (GET_CODE (op2)) == '1')
2422                       op2 = XEXP (op2, 0);
2423
2424                     val = operands_match_p (op1, op2);
2425                   }
2426
2427                 matching_operands[opno] = c - '0';
2428                 matching_operands[c - '0'] = opno;
2429
2430                 if (val != 0)
2431                   win = 1;
2432                 /* If output is *x and input is *--x,
2433                    arrange later to change the output to *--x as well,
2434                    since the output op is the one that will be printed.  */
2435                 if (val == 2 && strict > 0)
2436                   {
2437                     funny_match[funny_match_index].this = opno;
2438                     funny_match[funny_match_index++].other = c - '0';
2439                   }
2440                 break;
2441
2442               case 'p':
2443                 /* p is used for address_operands.  When we are called by
2444                    gen_reload, no one will have checked that the address is
2445                    strictly valid, i.e., that all pseudos requiring hard regs
2446                    have gotten them.  */
2447                 if (strict <= 0
2448                     || (strict_memory_address_p (recog_data.operand_mode[opno],
2449                                                  op)))
2450                   win = 1;
2451                 break;
2452
2453                 /* No need to check general_operand again;
2454                    it was done in insn-recog.c.  */
2455               case 'g':
2456                 /* Anything goes unless it is a REG and really has a hard reg
2457                    but the hard reg is not in the class GENERAL_REGS.  */
2458                 if (strict < 0
2459                     || GENERAL_REGS == ALL_REGS
2460                     || GET_CODE (op) != REG
2461                     || (reload_in_progress
2462                         && REGNO (op) >= FIRST_PSEUDO_REGISTER)
2463                     || reg_fits_class_p (op, GENERAL_REGS, offset, mode))
2464                   win = 1;
2465                 break;
2466
2467               case 'X':
2468                 /* This is used for a MATCH_SCRATCH in the cases when
2469                    we don't actually need anything.  So anything goes
2470                    any time.  */
2471                 win = 1;
2472                 break;
2473
2474               case 'm':
2475                 if (GET_CODE (op) == MEM
2476                     /* Before reload, accept what reload can turn into mem.  */
2477                     || (strict < 0 && CONSTANT_P (op))
2478                     /* During reload, accept a pseudo  */
2479                     || (reload_in_progress && GET_CODE (op) == REG
2480                         && REGNO (op) >= FIRST_PSEUDO_REGISTER))
2481                   win = 1;
2482                 break;
2483
2484               case '<':
2485                 if (GET_CODE (op) == MEM
2486                     && (GET_CODE (XEXP (op, 0)) == PRE_DEC
2487                         || GET_CODE (XEXP (op, 0)) == POST_DEC))
2488                   win = 1;
2489                 break;
2490
2491               case '>':
2492                 if (GET_CODE (op) == MEM
2493                     && (GET_CODE (XEXP (op, 0)) == PRE_INC
2494                         || GET_CODE (XEXP (op, 0)) == POST_INC))
2495                   win = 1;
2496                 break;
2497
2498               case 'E':
2499 #ifndef REAL_ARITHMETIC
2500                 /* Match any CONST_DOUBLE, but only if
2501                    we can examine the bits of it reliably.  */
2502                 if ((HOST_FLOAT_FORMAT != TARGET_FLOAT_FORMAT
2503                      || HOST_BITS_PER_WIDE_INT != BITS_PER_WORD)
2504                     && GET_MODE (op) != VOIDmode && ! flag_pretend_float)
2505                   break;
2506 #endif
2507                 if (GET_CODE (op) == CONST_DOUBLE)
2508                   win = 1;
2509                 break;
2510
2511               case 'F':
2512                 if (GET_CODE (op) == CONST_DOUBLE)
2513                   win = 1;
2514                 break;
2515
2516               case 'G':
2517               case 'H':
2518                 if (GET_CODE (op) == CONST_DOUBLE
2519                     && CONST_DOUBLE_OK_FOR_LETTER_P (op, c))
2520                   win = 1;
2521                 break;
2522
2523               case 's':
2524                 if (GET_CODE (op) == CONST_INT
2525                     || (GET_CODE (op) == CONST_DOUBLE
2526                         && GET_MODE (op) == VOIDmode))
2527                   break;
2528               case 'i':
2529                 if (CONSTANT_P (op))
2530                   win = 1;
2531                 break;
2532
2533               case 'n':
2534                 if (GET_CODE (op) == CONST_INT
2535                     || (GET_CODE (op) == CONST_DOUBLE
2536                         && GET_MODE (op) == VOIDmode))
2537                   win = 1;
2538                 break;
2539
2540               case 'I':
2541               case 'J':
2542               case 'K':
2543               case 'L':
2544               case 'M':
2545               case 'N':
2546               case 'O':
2547               case 'P':
2548                 if (GET_CODE (op) == CONST_INT
2549                     && CONST_OK_FOR_LETTER_P (INTVAL (op), c))
2550                   win = 1;
2551                 break;
2552
2553               case 'V':
2554                 if (GET_CODE (op) == MEM
2555                     && ((strict > 0 && ! offsettable_memref_p (op))
2556                         || (strict < 0
2557                             && !(CONSTANT_P (op) || GET_CODE (op) == MEM))
2558                         || (reload_in_progress
2559                             && !(GET_CODE (op) == REG
2560                                  && REGNO (op) >= FIRST_PSEUDO_REGISTER))))
2561                   win = 1;
2562                 break;
2563
2564               case 'o':
2565                 if ((strict > 0 && offsettable_memref_p (op))
2566                     || (strict == 0 && offsettable_nonstrict_memref_p (op))
2567                     /* Before reload, accept what reload can handle.  */
2568                     || (strict < 0
2569                         && (CONSTANT_P (op) || GET_CODE (op) == MEM))
2570                     /* During reload, accept a pseudo  */
2571                     || (reload_in_progress && GET_CODE (op) == REG
2572                         && REGNO (op) >= FIRST_PSEUDO_REGISTER))
2573                   win = 1;
2574                 break;
2575
2576               default:
2577                 {
2578                   enum reg_class class;
2579
2580                   class = (c == 'r' ? GENERAL_REGS : REG_CLASS_FROM_LETTER (c));
2581                   if (class != NO_REGS)
2582                     {
2583                       if (strict < 0
2584                           || (strict == 0
2585                               && GET_CODE (op) == REG
2586                               && REGNO (op) >= FIRST_PSEUDO_REGISTER)
2587                           || (strict == 0 && GET_CODE (op) == SCRATCH)
2588                           || (GET_CODE (op) == REG
2589                               && reg_fits_class_p (op, class, offset, mode)))
2590                         win = 1;
2591                     }
2592 #ifdef EXTRA_CONSTRAINT
2593                   else if (EXTRA_CONSTRAINT (op, c))
2594                     win = 1;
2595 #endif
2596                   break;
2597                 }
2598               }
2599
2600           constraints[opno] = p;
2601           /* If this operand did not win somehow,
2602              this alternative loses.  */
2603           if (! win)
2604             lose = 1;
2605         }
2606       /* This alternative won; the operands are ok.
2607          Change whichever operands this alternative says to change.  */
2608       if (! lose)
2609         {
2610           int opno, eopno;
2611
2612           /* See if any earlyclobber operand conflicts with some other
2613              operand.  */
2614
2615           if (strict > 0)
2616             for (eopno = 0; eopno < recog_data.n_operands; eopno++)
2617               /* Ignore earlyclobber operands now in memory,
2618                  because we would often report failure when we have
2619                  two memory operands, one of which was formerly a REG.  */
2620               if (earlyclobber[eopno]
2621                   && GET_CODE (recog_data.operand[eopno]) == REG)
2622                 for (opno = 0; opno < recog_data.n_operands; opno++)
2623                   if ((GET_CODE (recog_data.operand[opno]) == MEM
2624                        || recog_data.operand_type[opno] != OP_OUT)
2625                       && opno != eopno
2626                       /* Ignore things like match_operator operands.  */
2627                       && *recog_data.constraints[opno] != 0
2628                       && ! (matching_operands[opno] == eopno
2629                             && operands_match_p (recog_data.operand[opno],
2630                                                  recog_data.operand[eopno]))
2631                       && ! safe_from_earlyclobber (recog_data.operand[opno],
2632                                                    recog_data.operand[eopno]))
2633                     lose = 1;
2634
2635           if (! lose)
2636             {
2637               while (--funny_match_index >= 0)
2638                 {
2639                   recog_data.operand[funny_match[funny_match_index].other]
2640                     = recog_data.operand[funny_match[funny_match_index].this];
2641                 }
2642
2643               return 1;
2644             }
2645         }
2646
2647       which_alternative++;
2648     }
2649   while (which_alternative < recog_data.n_alternatives);
2650
2651   which_alternative = -1;
2652   /* If we are about to reject this, but we are not to test strictly,
2653      try a very loose test.  Only return failure if it fails also.  */
2654   if (strict == 0)
2655     return constrain_operands (-1);
2656   else
2657     return 0;
2658 }
2659
2660 /* Return 1 iff OPERAND (assumed to be a REG rtx)
2661    is a hard reg in class CLASS when its regno is offset by OFFSET
2662    and changed to mode MODE.
2663    If REG occupies multiple hard regs, all of them must be in CLASS.  */
2664
2665 int
2666 reg_fits_class_p (operand, class, offset, mode)
2667      rtx operand;
2668      register enum reg_class class;
2669      int offset;
2670      enum machine_mode mode;
2671 {
2672   register int regno = REGNO (operand);
2673   if (regno < FIRST_PSEUDO_REGISTER
2674       && TEST_HARD_REG_BIT (reg_class_contents[(int) class],
2675                             regno + offset))
2676     {
2677       register int sr;
2678       regno += offset;
2679       for (sr = HARD_REGNO_NREGS (regno, mode) - 1;
2680            sr > 0; sr--)
2681         if (! TEST_HARD_REG_BIT (reg_class_contents[(int) class],
2682                                  regno + sr))
2683           break;
2684       return sr == 0;
2685     }
2686
2687   return 0;
2688 }
2689 \f
2690 /* Split all insns in the function.  If UPD_LIFE, update life info after.  */
2691
2692 void
2693 split_all_insns (upd_life)
2694      int upd_life;
2695 {
2696   sbitmap blocks;
2697   int changed;
2698   int i;
2699
2700   blocks = sbitmap_alloc (n_basic_blocks);
2701   sbitmap_zero (blocks);
2702   changed = 0;
2703
2704   for (i = n_basic_blocks - 1; i >= 0; --i)
2705     {
2706       basic_block bb = BASIC_BLOCK (i);
2707       rtx insn, next;
2708
2709       for (insn = bb->head; insn ; insn = next)
2710         {
2711           rtx set;
2712
2713           /* Can't use `next_real_insn' because that might go across
2714              CODE_LABELS and short-out basic blocks.  */
2715           next = NEXT_INSN (insn);
2716           if (! INSN_P (insn))
2717             ;
2718
2719           /* Don't split no-op move insns.  These should silently
2720              disappear later in final.  Splitting such insns would
2721              break the code that handles REG_NO_CONFLICT blocks.  */
2722
2723           else if ((set = single_set (insn)) != NULL
2724                    && rtx_equal_p (SET_SRC (set), SET_DEST (set)))
2725             {
2726               /* Nops get in the way while scheduling, so delete them
2727                  now if register allocation has already been done.  It
2728                  is too risky to try to do this before register
2729                  allocation, and there are unlikely to be very many
2730                  nops then anyways.  */
2731               if (reload_completed)
2732                 {
2733                   PUT_CODE (insn, NOTE);
2734                   NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
2735                   NOTE_SOURCE_FILE (insn) = 0;
2736                 }
2737             }
2738           else
2739             {
2740               /* Split insns here to get max fine-grain parallelism.  */
2741               rtx first = PREV_INSN (insn);
2742               rtx last = try_split (PATTERN (insn), insn, 1);
2743
2744               if (last != insn)
2745                 {
2746                   SET_BIT (blocks, i);
2747                   changed = 1;
2748
2749                   /* try_split returns the NOTE that INSN became.  */
2750                   first = NEXT_INSN (first);
2751                   PUT_CODE (insn, NOTE);
2752                   NOTE_SOURCE_FILE (insn) = 0;
2753                   NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
2754
2755                   if (insn == bb->end)
2756                     {
2757                       bb->end = last;
2758                       break;
2759                     }
2760
2761                   /* ??? Coddle to md files that generate subregs in post-
2762                      reload splitters instead of computing the proper
2763                      hard register.  */
2764                   if (reload_completed)
2765                     while (1)
2766                       {
2767                         if (INSN_P (first))
2768                           cleanup_subreg_operands (first);
2769                         if (first == last)
2770                           break;
2771                         first = NEXT_INSN (first);
2772                       }
2773                 }
2774             }
2775
2776           if (insn == bb->end)
2777             break;
2778         }
2779
2780       /* ??? When we're called from just after reload, the CFG is in bad
2781          shape, and we may have fallen off the end.  This could be fixed
2782          by having reload not try to delete unreachable code.  Otherwise
2783          assert we found the end insn.  */
2784       if (insn == NULL && upd_life)
2785         abort ();
2786     }
2787
2788   if (changed && upd_life)
2789     {
2790       compute_bb_for_insn (get_max_uid ());
2791       count_or_remove_death_notes (blocks, 1);
2792       update_life_info (blocks, UPDATE_LIFE_LOCAL, PROP_DEATH_NOTES);
2793     }
2794
2795   sbitmap_free (blocks);
2796 }
2797 \f
2798 #ifdef HAVE_peephole2
2799 struct peep2_insn_data
2800 {
2801   rtx insn;
2802   regset live_before;
2803 };
2804
2805 static struct peep2_insn_data peep2_insn_data[MAX_INSNS_PER_PEEP2 + 1];
2806 static int peep2_current;
2807
2808 /* A non-insn marker indicating the last insn of the block.
2809    The live_before regset for this element is correct, indicating
2810    global_live_at_end for the block.  */
2811 #define PEEP2_EOB       pc_rtx
2812
2813 /* Return the Nth non-note insn after `current', or return NULL_RTX if it
2814    does not exist.  Used by the recognizer to find the next insn to match
2815    in a multi-insn pattern.  */
2816
2817 rtx
2818 peep2_next_insn (n)
2819      int n;
2820 {
2821   if (n >= MAX_INSNS_PER_PEEP2 + 1)
2822     abort ();
2823
2824   n += peep2_current;
2825   if (n >= MAX_INSNS_PER_PEEP2 + 1)
2826     n -= MAX_INSNS_PER_PEEP2 + 1;
2827
2828   if (peep2_insn_data[n].insn == PEEP2_EOB)
2829     return NULL_RTX;
2830   return peep2_insn_data[n].insn;
2831 }
2832
2833 /* Return true if REGNO is dead before the Nth non-note insn
2834    after `current'.  */
2835
2836 int
2837 peep2_regno_dead_p (ofs, regno)
2838      int ofs;
2839      int regno;
2840 {
2841   if (ofs >= MAX_INSNS_PER_PEEP2 + 1)
2842     abort ();
2843
2844   ofs += peep2_current;
2845   if (ofs >= MAX_INSNS_PER_PEEP2 + 1)
2846     ofs -= MAX_INSNS_PER_PEEP2 + 1;
2847
2848   if (peep2_insn_data[ofs].insn == NULL_RTX)
2849     abort ();
2850
2851   return ! REGNO_REG_SET_P (peep2_insn_data[ofs].live_before, regno);
2852 }
2853
2854 /* Similarly for a REG.  */
2855
2856 int
2857 peep2_reg_dead_p (ofs, reg)
2858      int ofs;
2859      rtx reg;
2860 {
2861   int regno, n;
2862
2863   if (ofs >= MAX_INSNS_PER_PEEP2 + 1)
2864     abort ();
2865
2866   ofs += peep2_current;
2867   if (ofs >= MAX_INSNS_PER_PEEP2 + 1)
2868     ofs -= MAX_INSNS_PER_PEEP2 + 1;
2869
2870   if (peep2_insn_data[ofs].insn == NULL_RTX)
2871     abort ();
2872
2873   regno = REGNO (reg);
2874   n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2875   while (--n >= 0)
2876     if (REGNO_REG_SET_P (peep2_insn_data[ofs].live_before, regno + n))
2877       return 0;
2878   return 1;
2879 }
2880
2881 /* Try to find a hard register of mode MODE, matching the register class in
2882    CLASS_STR, which is available at the beginning of insn CURRENT_INSN and
2883    remains available until the end of LAST_INSN.  LAST_INSN may be NULL_RTX,
2884    in which case the only condition is that the register must be available
2885    before CURRENT_INSN.
2886    Registers that already have bits set in REG_SET will not be considered.
2887
2888    If an appropriate register is available, it will be returned and the
2889    corresponding bit(s) in REG_SET will be set; otherwise, NULL_RTX is
2890    returned.  */
2891
2892 rtx
2893 peep2_find_free_register (from, to, class_str, mode, reg_set)
2894      int from, to;
2895      const char *class_str;
2896      enum machine_mode mode;
2897      HARD_REG_SET *reg_set;
2898 {
2899   static int search_ofs;
2900   enum reg_class class;
2901   HARD_REG_SET live;
2902   int i;
2903
2904   if (from >= MAX_INSNS_PER_PEEP2 + 1 || to >= MAX_INSNS_PER_PEEP2 + 1)
2905     abort ();
2906
2907   from += peep2_current;
2908   if (from >= MAX_INSNS_PER_PEEP2 + 1)
2909     from -= MAX_INSNS_PER_PEEP2 + 1;
2910   to += peep2_current;
2911   if (to >= MAX_INSNS_PER_PEEP2 + 1)
2912     to -= MAX_INSNS_PER_PEEP2 + 1;
2913
2914   if (peep2_insn_data[from].insn == NULL_RTX)
2915     abort ();
2916   REG_SET_TO_HARD_REG_SET (live, peep2_insn_data[from].live_before);
2917
2918   while (from != to)
2919     {
2920       HARD_REG_SET this_live;
2921
2922       if (++from >= MAX_INSNS_PER_PEEP2 + 1)
2923         from = 0;
2924       if (peep2_insn_data[from].insn == NULL_RTX)
2925         abort ();
2926       REG_SET_TO_HARD_REG_SET (this_live, peep2_insn_data[from].live_before);
2927       IOR_HARD_REG_SET (live, this_live);
2928     }
2929
2930   class = (class_str[0] == 'r' ? GENERAL_REGS
2931            : REG_CLASS_FROM_LETTER (class_str[0]));
2932
2933   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2934     {
2935       int raw_regno, regno, success, j;
2936
2937       /* Distribute the free registers as much as possible.  */
2938       raw_regno = search_ofs + i;
2939       if (raw_regno >= FIRST_PSEUDO_REGISTER)
2940         raw_regno -= FIRST_PSEUDO_REGISTER;
2941 #ifdef REG_ALLOC_ORDER
2942       regno = reg_alloc_order[raw_regno];
2943 #else
2944       regno = raw_regno;
2945 #endif
2946
2947       /* Don't allocate fixed registers.  */
2948       if (fixed_regs[regno])
2949         continue;
2950       /* Make sure the register is of the right class.  */
2951       if (! TEST_HARD_REG_BIT (reg_class_contents[class], regno))
2952         continue;
2953       /* And can support the mode we need.  */
2954       if (! HARD_REGNO_MODE_OK (regno, mode))
2955         continue;
2956       /* And that we don't create an extra save/restore.  */
2957       if (! call_used_regs[regno] && ! regs_ever_live[regno])
2958         continue;
2959       /* And we don't clobber traceback for noreturn functions.  */
2960       if ((regno == FRAME_POINTER_REGNUM || regno == HARD_FRAME_POINTER_REGNUM)
2961           && (! reload_completed || frame_pointer_needed))
2962         continue;
2963
2964       success = 1;
2965       for (j = HARD_REGNO_NREGS (regno, mode) - 1; j >= 0; j--)
2966         {
2967           if (TEST_HARD_REG_BIT (*reg_set, regno + j)
2968               || TEST_HARD_REG_BIT (live, regno + j))
2969             {
2970               success = 0;
2971               break;
2972             }
2973         }
2974       if (success)
2975         {
2976           for (j = HARD_REGNO_NREGS (regno, mode) - 1; j >= 0; j--)
2977             SET_HARD_REG_BIT (*reg_set, regno + j);
2978
2979           /* Start the next search with the next register.  */
2980           if (++raw_regno >= FIRST_PSEUDO_REGISTER)
2981             raw_regno = 0;
2982           search_ofs = raw_regno;
2983
2984           return gen_rtx_REG (mode, regno);
2985         }
2986     }
2987
2988   search_ofs = 0;
2989   return NULL_RTX;
2990 }
2991
2992 /* Perform the peephole2 optimization pass. */
2993
2994 void
2995 peephole2_optimize (dump_file)
2996      FILE *dump_file ATTRIBUTE_UNUSED;
2997 {
2998   regset_head rs_heads[MAX_INSNS_PER_PEEP2 + 2];
2999   rtx insn, prev;
3000   regset live;
3001   int i, b;
3002 #ifdef HAVE_conditional_execution
3003   sbitmap blocks;
3004   int changed;
3005 #endif
3006
3007   /* Initialize the regsets we're going to use.  */
3008   for (i = 0; i < MAX_INSNS_PER_PEEP2 + 1; ++i)
3009     peep2_insn_data[i].live_before = INITIALIZE_REG_SET (rs_heads[i]);
3010   live = INITIALIZE_REG_SET (rs_heads[i]);
3011
3012 #ifdef HAVE_conditional_execution
3013   blocks = sbitmap_alloc (n_basic_blocks);
3014   sbitmap_zero (blocks);
3015   changed = 0;
3016 #else
3017   count_or_remove_death_notes (NULL, 1);
3018 #endif
3019
3020   for (b = n_basic_blocks - 1; b >= 0; --b)
3021     {
3022       basic_block bb = BASIC_BLOCK (b);
3023       struct propagate_block_info *pbi;
3024
3025       /* Indicate that all slots except the last holds invalid data.  */
3026       for (i = 0; i < MAX_INSNS_PER_PEEP2; ++i)
3027         peep2_insn_data[i].insn = NULL_RTX;
3028
3029       /* Indicate that the last slot contains live_after data.  */
3030       peep2_insn_data[MAX_INSNS_PER_PEEP2].insn = PEEP2_EOB;
3031       peep2_current = MAX_INSNS_PER_PEEP2;
3032
3033       /* Start up propagation.  */
3034       COPY_REG_SET (live, bb->global_live_at_end);
3035       COPY_REG_SET (peep2_insn_data[MAX_INSNS_PER_PEEP2].live_before, live);
3036
3037 #ifdef HAVE_conditional_execution
3038       pbi = init_propagate_block_info (bb, live, NULL, 0);
3039 #else
3040       pbi = init_propagate_block_info (bb, live, NULL, PROP_DEATH_NOTES);
3041 #endif
3042
3043       for (insn = bb->end; ; insn = prev)
3044         {
3045           prev = PREV_INSN (insn);
3046           if (INSN_P (insn))
3047             {
3048               rtx try;
3049               int match_len;
3050
3051               /* Record this insn.  */
3052               if (--peep2_current < 0)
3053                 peep2_current = MAX_INSNS_PER_PEEP2;
3054               peep2_insn_data[peep2_current].insn = insn;
3055               propagate_one_insn (pbi, insn);
3056               COPY_REG_SET (peep2_insn_data[peep2_current].live_before, live);
3057
3058               /* Match the peephole.  */
3059               try = peephole2_insns (PATTERN (insn), insn, &match_len);
3060               if (try != NULL)
3061                 {
3062                   i = match_len + peep2_current;
3063                   if (i >= MAX_INSNS_PER_PEEP2 + 1)
3064                     i -= MAX_INSNS_PER_PEEP2 + 1;
3065
3066                   /* Replace the old sequence with the new.  */
3067                   flow_delete_insn_chain (insn, peep2_insn_data[i].insn);
3068                   try = emit_insn_after (try, prev);
3069
3070                   /* Adjust the basic block boundaries.  */
3071                   if (peep2_insn_data[i].insn == bb->end)
3072                     bb->end = try;
3073                   if (insn == bb->head)
3074                     bb->head = NEXT_INSN (prev);
3075
3076 #ifdef HAVE_conditional_execution
3077                   /* With conditional execution, we cannot back up the
3078                      live information so easily, since the conditional
3079                      death data structures are not so self-contained.
3080                      So record that we've made a modification to this
3081                      block and update life information at the end.  */
3082                   SET_BIT (blocks, b);
3083                   changed = 1;
3084
3085                   for (i = 0; i < MAX_INSNS_PER_PEEP2 + 1; ++i)
3086                     peep2_insn_data[i].insn = NULL_RTX;
3087                   peep2_insn_data[peep2_current].insn = PEEP2_EOB;
3088 #else
3089                   /* Back up lifetime information past the end of the
3090                      newly created sequence.  */
3091                   if (++i >= MAX_INSNS_PER_PEEP2 + 1)
3092                     i = 0;
3093                   COPY_REG_SET (live, peep2_insn_data[i].live_before);
3094
3095                   /* Update life information for the new sequence.  */
3096                   do
3097                     {
3098                       if (INSN_P (try))
3099                         {
3100                           if (--i < 0)
3101                             i = MAX_INSNS_PER_PEEP2;
3102                           peep2_insn_data[i].insn = try;
3103                           propagate_one_insn (pbi, try);
3104                           COPY_REG_SET (peep2_insn_data[i].live_before, live);
3105                         }
3106                       try = PREV_INSN (try);
3107                     }
3108                   while (try != prev);
3109
3110                   /* ??? Should verify that LIVE now matches what we
3111                      had before the new sequence.  */
3112
3113                   peep2_current = i;
3114 #endif
3115                 }
3116             }
3117
3118           if (insn == bb->head)
3119             break;
3120         }
3121
3122       free_propagate_block_info (pbi);
3123     }
3124
3125   for (i = 0; i < MAX_INSNS_PER_PEEP2 + 1; ++i)
3126     FREE_REG_SET (peep2_insn_data[i].live_before);
3127   FREE_REG_SET (live);
3128
3129 #ifdef HAVE_conditional_execution
3130   count_or_remove_death_notes (blocks, 1);
3131   update_life_info (blocks, UPDATE_LIFE_LOCAL, PROP_DEATH_NOTES);
3132   sbitmap_free (blocks);
3133 #endif
3134 }
3135 #endif /* HAVE_peephole2 */