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   if (GET_CODE (body) == ASM_OPERANDS)
1405     /* No output operands: return number of input operands.  */
1406     return ASM_OPERANDS_INPUT_LENGTH (body);
1407   if (GET_CODE (body) == SET && GET_CODE (SET_SRC (body)) == ASM_OPERANDS)
1408     /* Single output operand: BODY is (set OUTPUT (asm_operands ...)).  */
1409     return ASM_OPERANDS_INPUT_LENGTH (SET_SRC (body)) + 1;
1410   else if (GET_CODE (body) == PARALLEL
1411            && GET_CODE (XVECEXP (body, 0, 0)) == SET
1412            && GET_CODE (SET_SRC (XVECEXP (body, 0, 0))) == ASM_OPERANDS)
1413     {
1414       /* Multiple output operands, or 1 output plus some clobbers:
1415          body is [(set OUTPUT (asm_operands ...))... (clobber (reg ...))...].  */
1416       int i;
1417       int n_sets;
1418
1419       /* Count backwards through CLOBBERs to determine number of SETs.  */
1420       for (i = XVECLEN (body, 0); i > 0; i--)
1421         {
1422           if (GET_CODE (XVECEXP (body, 0, i - 1)) == SET)
1423             break;
1424           if (GET_CODE (XVECEXP (body, 0, i - 1)) != CLOBBER)
1425             return -1;
1426         }
1427
1428       /* N_SETS is now number of output operands.  */
1429       n_sets = i;
1430
1431       /* Verify that all the SETs we have
1432          came from a single original asm_operands insn
1433          (so that invalid combinations are blocked).  */
1434       for (i = 0; i < n_sets; i++)
1435         {
1436           rtx elt = XVECEXP (body, 0, i);
1437           if (GET_CODE (elt) != SET)
1438             return -1;
1439           if (GET_CODE (SET_SRC (elt)) != ASM_OPERANDS)
1440             return -1;
1441           /* If these ASM_OPERANDS rtx's came from different original insns
1442              then they aren't allowed together.  */
1443           if (ASM_OPERANDS_INPUT_VEC (SET_SRC (elt))
1444               != ASM_OPERANDS_INPUT_VEC (SET_SRC (XVECEXP (body, 0, 0))))
1445             return -1;
1446         }
1447       return (ASM_OPERANDS_INPUT_LENGTH (SET_SRC (XVECEXP (body, 0, 0)))
1448               + n_sets);
1449     }
1450   else if (GET_CODE (body) == PARALLEL
1451            && GET_CODE (XVECEXP (body, 0, 0)) == ASM_OPERANDS)
1452     {
1453       /* 0 outputs, but some clobbers:
1454          body is [(asm_operands ...) (clobber (reg ...))...].  */
1455       int i;
1456
1457       /* Make sure all the other parallel things really are clobbers.  */
1458       for (i = XVECLEN (body, 0) - 1; i > 0; i--)
1459         if (GET_CODE (XVECEXP (body, 0, i)) != CLOBBER)
1460           return -1;
1461
1462       return ASM_OPERANDS_INPUT_LENGTH (XVECEXP (body, 0, 0));
1463     }
1464   else
1465     return -1;
1466 }
1467
1468 /* Assuming BODY is an insn body that uses ASM_OPERANDS,
1469    copy its operands (both input and output) into the vector OPERANDS,
1470    the locations of the operands within the insn into the vector OPERAND_LOCS,
1471    and the constraints for the operands into CONSTRAINTS.
1472    Write the modes of the operands into MODES.
1473    Return the assembler-template.
1474
1475    If MODES, OPERAND_LOCS, CONSTRAINTS or OPERANDS is 0,
1476    we don't store that info.  */
1477
1478 const char *
1479 decode_asm_operands (body, operands, operand_locs, constraints, modes)
1480      rtx body;
1481      rtx *operands;
1482      rtx **operand_locs;
1483      const char **constraints;
1484      enum machine_mode *modes;
1485 {
1486   register int i;
1487   int noperands;
1488   const char *template = 0;
1489
1490   if (GET_CODE (body) == SET && GET_CODE (SET_SRC (body)) == ASM_OPERANDS)
1491     {
1492       rtx asmop = SET_SRC (body);
1493       /* Single output operand: BODY is (set OUTPUT (asm_operands ....)).  */
1494
1495       noperands = ASM_OPERANDS_INPUT_LENGTH (asmop) + 1;
1496
1497       for (i = 1; i < noperands; i++)
1498         {
1499           if (operand_locs)
1500             operand_locs[i] = &ASM_OPERANDS_INPUT (asmop, i - 1);
1501           if (operands)
1502             operands[i] = ASM_OPERANDS_INPUT (asmop, i - 1);
1503           if (constraints)
1504             constraints[i] = ASM_OPERANDS_INPUT_CONSTRAINT (asmop, i - 1);
1505           if (modes)
1506             modes[i] = ASM_OPERANDS_INPUT_MODE (asmop, i - 1);
1507         }
1508
1509       /* The output is in the SET.
1510          Its constraint is in the ASM_OPERANDS itself.  */
1511       if (operands)
1512         operands[0] = SET_DEST (body);
1513       if (operand_locs)
1514         operand_locs[0] = &SET_DEST (body);
1515       if (constraints)
1516         constraints[0] = ASM_OPERANDS_OUTPUT_CONSTRAINT (asmop);
1517       if (modes)
1518         modes[0] = GET_MODE (SET_DEST (body));
1519       template = ASM_OPERANDS_TEMPLATE (asmop);
1520     }
1521   else if (GET_CODE (body) == ASM_OPERANDS)
1522     {
1523       rtx asmop = body;
1524       /* No output operands: BODY is (asm_operands ....).  */
1525
1526       noperands = ASM_OPERANDS_INPUT_LENGTH (asmop);
1527
1528       /* The input operands are found in the 1st element vector.  */
1529       /* Constraints for inputs are in the 2nd element vector.  */
1530       for (i = 0; i < noperands; i++)
1531         {
1532           if (operand_locs)
1533             operand_locs[i] = &ASM_OPERANDS_INPUT (asmop, i);
1534           if (operands)
1535             operands[i] = ASM_OPERANDS_INPUT (asmop, i);
1536           if (constraints)
1537             constraints[i] = ASM_OPERANDS_INPUT_CONSTRAINT (asmop, i);
1538           if (modes)
1539             modes[i] = ASM_OPERANDS_INPUT_MODE (asmop, i);
1540         }
1541       template = ASM_OPERANDS_TEMPLATE (asmop);
1542     }
1543   else if (GET_CODE (body) == PARALLEL
1544            && GET_CODE (XVECEXP (body, 0, 0)) == SET)
1545     {
1546       rtx asmop = SET_SRC (XVECEXP (body, 0, 0));
1547       int nparallel = XVECLEN (body, 0); /* Includes CLOBBERs.  */
1548       int nin = ASM_OPERANDS_INPUT_LENGTH (asmop);
1549       int nout = 0;             /* Does not include CLOBBERs.  */
1550
1551       /* At least one output, plus some CLOBBERs.  */
1552
1553       /* The outputs are in the SETs.
1554          Their constraints are in the ASM_OPERANDS itself.  */
1555       for (i = 0; i < nparallel; i++)
1556         {
1557           if (GET_CODE (XVECEXP (body, 0, i)) == CLOBBER)
1558             break;              /* Past last SET */
1559
1560           if (operands)
1561             operands[i] = SET_DEST (XVECEXP (body, 0, i));
1562           if (operand_locs)
1563             operand_locs[i] = &SET_DEST (XVECEXP (body, 0, i));
1564           if (constraints)
1565             constraints[i] = XSTR (SET_SRC (XVECEXP (body, 0, i)), 1);
1566           if (modes)
1567             modes[i] = GET_MODE (SET_DEST (XVECEXP (body, 0, i)));
1568           nout++;
1569         }
1570
1571       for (i = 0; i < nin; i++)
1572         {
1573           if (operand_locs)
1574             operand_locs[i + nout] = &ASM_OPERANDS_INPUT (asmop, i);
1575           if (operands)
1576             operands[i + nout] = ASM_OPERANDS_INPUT (asmop, i);
1577           if (constraints)
1578             constraints[i + nout] = ASM_OPERANDS_INPUT_CONSTRAINT (asmop, i);
1579           if (modes)
1580             modes[i + nout] = ASM_OPERANDS_INPUT_MODE (asmop, i);
1581         }
1582
1583       template = ASM_OPERANDS_TEMPLATE (asmop);
1584     }
1585   else if (GET_CODE (body) == PARALLEL
1586            && GET_CODE (XVECEXP (body, 0, 0)) == ASM_OPERANDS)
1587     {
1588       /* No outputs, but some CLOBBERs.  */
1589
1590       rtx asmop = XVECEXP (body, 0, 0);
1591       int nin = ASM_OPERANDS_INPUT_LENGTH (asmop);
1592
1593       for (i = 0; i < nin; i++)
1594         {
1595           if (operand_locs)
1596             operand_locs[i] = &ASM_OPERANDS_INPUT (asmop, i);
1597           if (operands)
1598             operands[i] = ASM_OPERANDS_INPUT (asmop, i);
1599           if (constraints)
1600             constraints[i] = ASM_OPERANDS_INPUT_CONSTRAINT (asmop, i);
1601           if (modes)
1602             modes[i] = ASM_OPERANDS_INPUT_MODE (asmop, i);
1603         }
1604
1605       template = ASM_OPERANDS_TEMPLATE (asmop);
1606     }
1607
1608   return template;
1609 }
1610
1611 /* Check if an asm_operand matches it's constraints.
1612    Return > 0 if ok, = 0 if bad, < 0 if inconclusive.  */
1613
1614 int
1615 asm_operand_ok (op, constraint)
1616      rtx op;
1617      const char *constraint;
1618 {
1619   int result = 0;
1620
1621   /* Use constrain_operands after reload.  */
1622   if (reload_completed)
1623     abort ();
1624
1625   while (*constraint)
1626     {
1627       char c = *constraint++;
1628       switch (c)
1629         {
1630         case '=':
1631         case '+':
1632         case '*':
1633         case '%':
1634         case '?':
1635         case '!':
1636         case '#':
1637         case '&':
1638         case ',':
1639           break;
1640
1641         case '0': case '1': case '2': case '3': case '4':
1642         case '5': case '6': case '7': case '8': case '9':
1643           /* For best results, our caller should have given us the
1644              proper matching constraint, but we can't actually fail
1645              the check if they didn't.  Indicate that results are
1646              inconclusive.  */
1647           result = -1;
1648           break;
1649
1650         case 'p':
1651           if (address_operand (op, VOIDmode))
1652             return 1;
1653           break;
1654
1655         case 'm':
1656         case 'V': /* non-offsettable */
1657           if (memory_operand (op, VOIDmode))
1658             return 1;
1659           break;
1660
1661         case 'o': /* offsettable */
1662           if (offsettable_nonstrict_memref_p (op))
1663             return 1;
1664           break;
1665
1666         case '<':
1667           /* ??? Before flow, auto inc/dec insns are not supposed to exist,
1668              excepting those that expand_call created.  Further, on some
1669              machines which do not have generalized auto inc/dec, an inc/dec
1670              is not a memory_operand.
1671
1672              Match any memory and hope things are resolved after reload.  */
1673
1674           if (GET_CODE (op) == MEM
1675               && (1
1676                   || GET_CODE (XEXP (op, 0)) == PRE_DEC
1677                   || GET_CODE (XEXP (op, 0)) == POST_DEC))
1678             return 1;
1679           break;
1680
1681         case '>':
1682           if (GET_CODE (op) == MEM
1683               && (1
1684                   || GET_CODE (XEXP (op, 0)) == PRE_INC
1685                   || GET_CODE (XEXP (op, 0)) == POST_INC))
1686             return 1;
1687           break;
1688
1689         case 'E':
1690 #ifndef REAL_ARITHMETIC
1691           /* Match any floating double constant, but only if
1692              we can examine the bits of it reliably.  */
1693           if ((HOST_FLOAT_FORMAT != TARGET_FLOAT_FORMAT
1694                || HOST_BITS_PER_WIDE_INT != BITS_PER_WORD)
1695               && GET_MODE (op) != VOIDmode && ! flag_pretend_float)
1696             break;
1697 #endif
1698           /* FALLTHRU */
1699
1700         case 'F':
1701           if (GET_CODE (op) == CONST_DOUBLE)
1702             return 1;
1703           break;
1704
1705         case 'G':
1706           if (GET_CODE (op) == CONST_DOUBLE
1707               && CONST_DOUBLE_OK_FOR_LETTER_P (op, 'G'))
1708             return 1;
1709           break;
1710         case 'H':
1711           if (GET_CODE (op) == CONST_DOUBLE
1712               && CONST_DOUBLE_OK_FOR_LETTER_P (op, 'H'))
1713             return 1;
1714           break;
1715
1716         case 's':
1717           if (GET_CODE (op) == CONST_INT
1718               || (GET_CODE (op) == CONST_DOUBLE
1719                   && GET_MODE (op) == VOIDmode))
1720             break;
1721           /* FALLTHRU */
1722
1723         case 'i':
1724           if (CONSTANT_P (op)
1725 #ifdef LEGITIMATE_PIC_OPERAND_P
1726               && (! flag_pic || LEGITIMATE_PIC_OPERAND_P (op))
1727 #endif
1728               )
1729             return 1;
1730           break;
1731
1732         case 'n':
1733           if (GET_CODE (op) == CONST_INT
1734               || (GET_CODE (op) == CONST_DOUBLE
1735                   && GET_MODE (op) == VOIDmode))
1736             return 1;
1737           break;
1738
1739         case 'I':
1740           if (GET_CODE (op) == CONST_INT
1741               && CONST_OK_FOR_LETTER_P (INTVAL (op), 'I'))
1742             return 1;
1743           break;
1744         case 'J':
1745           if (GET_CODE (op) == CONST_INT
1746               && CONST_OK_FOR_LETTER_P (INTVAL (op), 'J'))
1747             return 1;
1748           break;
1749         case 'K':
1750           if (GET_CODE (op) == CONST_INT
1751               && CONST_OK_FOR_LETTER_P (INTVAL (op), 'K'))
1752             return 1;
1753           break;
1754         case 'L':
1755           if (GET_CODE (op) == CONST_INT
1756               && CONST_OK_FOR_LETTER_P (INTVAL (op), 'L'))
1757             return 1;
1758           break;
1759         case 'M':
1760           if (GET_CODE (op) == CONST_INT
1761               && CONST_OK_FOR_LETTER_P (INTVAL (op), 'M'))
1762             return 1;
1763           break;
1764         case 'N':
1765           if (GET_CODE (op) == CONST_INT
1766               && CONST_OK_FOR_LETTER_P (INTVAL (op), 'N'))
1767             return 1;
1768           break;
1769         case 'O':
1770           if (GET_CODE (op) == CONST_INT
1771               && CONST_OK_FOR_LETTER_P (INTVAL (op), 'O'))
1772             return 1;
1773           break;
1774         case 'P':
1775           if (GET_CODE (op) == CONST_INT
1776               && CONST_OK_FOR_LETTER_P (INTVAL (op), 'P'))
1777             return 1;
1778           break;
1779
1780         case 'X':
1781           return 1;
1782
1783         case 'g':
1784           if (general_operand (op, VOIDmode))
1785             return 1;
1786           break;
1787
1788         default:
1789           /* For all other letters, we first check for a register class,
1790              otherwise it is an EXTRA_CONSTRAINT.  */
1791           if (REG_CLASS_FROM_LETTER (c) != NO_REGS)
1792             {
1793             case 'r':
1794               if (GET_MODE (op) == BLKmode)
1795                 break;
1796               if (register_operand (op, VOIDmode))
1797                 return 1;
1798             }
1799 #ifdef EXTRA_CONSTRAINT
1800           if (EXTRA_CONSTRAINT (op, c))
1801             return 1;
1802 #endif
1803           break;
1804         }
1805     }
1806
1807   return result;
1808 }
1809 \f
1810 /* Given an rtx *P, if it is a sum containing an integer constant term,
1811    return the location (type rtx *) of the pointer to that constant term.
1812    Otherwise, return a null pointer.  */
1813
1814 static rtx *
1815 find_constant_term_loc (p)
1816      rtx *p;
1817 {
1818   register rtx *tem;
1819   register enum rtx_code code = GET_CODE (*p);
1820
1821   /* If *P IS such a constant term, P is its location.  */
1822
1823   if (code == CONST_INT || code == SYMBOL_REF || code == LABEL_REF
1824       || code == CONST)
1825     return p;
1826
1827   /* Otherwise, if not a sum, it has no constant term.  */
1828
1829   if (GET_CODE (*p) != PLUS)
1830     return 0;
1831
1832   /* If one of the summands is constant, return its location.  */
1833
1834   if (XEXP (*p, 0) && CONSTANT_P (XEXP (*p, 0))
1835       && XEXP (*p, 1) && CONSTANT_P (XEXP (*p, 1)))
1836     return p;
1837
1838   /* Otherwise, check each summand for containing a constant term.  */
1839
1840   if (XEXP (*p, 0) != 0)
1841     {
1842       tem = find_constant_term_loc (&XEXP (*p, 0));
1843       if (tem != 0)
1844         return tem;
1845     }
1846
1847   if (XEXP (*p, 1) != 0)
1848     {
1849       tem = find_constant_term_loc (&XEXP (*p, 1));
1850       if (tem != 0)
1851         return tem;
1852     }
1853
1854   return 0;
1855 }
1856 \f
1857 /* Return 1 if OP is a memory reference
1858    whose address contains no side effects
1859    and remains valid after the addition
1860    of a positive integer less than the
1861    size of the object being referenced.
1862
1863    We assume that the original address is valid and do not check it.
1864
1865    This uses strict_memory_address_p as a subroutine, so
1866    don't use it before reload.  */
1867
1868 int
1869 offsettable_memref_p (op)
1870      rtx op;
1871 {
1872   return ((GET_CODE (op) == MEM)
1873           && offsettable_address_p (1, GET_MODE (op), XEXP (op, 0)));
1874 }
1875
1876 /* Similar, but don't require a strictly valid mem ref:
1877    consider pseudo-regs valid as index or base regs.  */
1878
1879 int
1880 offsettable_nonstrict_memref_p (op)
1881      rtx op;
1882 {
1883   return ((GET_CODE (op) == MEM)
1884           && offsettable_address_p (0, GET_MODE (op), XEXP (op, 0)));
1885 }
1886
1887 /* Return 1 if Y is a memory address which contains no side effects
1888    and would remain valid after the addition of a positive integer
1889    less than the size of that mode.
1890
1891    We assume that the original address is valid and do not check it.
1892    We do check that it is valid for narrower modes.
1893
1894    If STRICTP is nonzero, we require a strictly valid address,
1895    for the sake of use in reload.c.  */
1896
1897 int
1898 offsettable_address_p (strictp, mode, y)
1899      int strictp;
1900      enum machine_mode mode;
1901      register rtx y;
1902 {
1903   register enum rtx_code ycode = GET_CODE (y);
1904   register rtx z;
1905   rtx y1 = y;
1906   rtx *y2;
1907   int (*addressp) PARAMS ((enum machine_mode, rtx)) =
1908     (strictp ? strict_memory_address_p : memory_address_p);
1909   unsigned int mode_sz = GET_MODE_SIZE (mode);
1910
1911   if (CONSTANT_ADDRESS_P (y))
1912     return 1;
1913
1914   /* Adjusting an offsettable address involves changing to a narrower mode.
1915      Make sure that's OK.  */
1916
1917   if (mode_dependent_address_p (y))
1918     return 0;
1919
1920   /* ??? How much offset does an offsettable BLKmode reference need?
1921      Clearly that depends on the situation in which it's being used.
1922      However, the current situation in which we test 0xffffffff is
1923      less than ideal.  Caveat user.  */
1924   if (mode_sz == 0)
1925     mode_sz = BIGGEST_ALIGNMENT / BITS_PER_UNIT;
1926
1927   /* If the expression contains a constant term,
1928      see if it remains valid when max possible offset is added.  */
1929
1930   if ((ycode == PLUS) && (y2 = find_constant_term_loc (&y1)))
1931     {
1932       int good;
1933
1934       y1 = *y2;
1935       *y2 = plus_constant (*y2, mode_sz - 1);
1936       /* Use QImode because an odd displacement may be automatically invalid
1937          for any wider mode.  But it should be valid for a single byte.  */
1938       good = (*addressp) (QImode, y);
1939
1940       /* In any case, restore old contents of memory.  */
1941       *y2 = y1;
1942       return good;
1943     }
1944
1945   if (GET_RTX_CLASS (ycode) == 'a')
1946     return 0;
1947
1948   /* The offset added here is chosen as the maximum offset that
1949      any instruction could need to add when operating on something
1950      of the specified mode.  We assume that if Y and Y+c are
1951      valid addresses then so is Y+d for all 0<d<c.  */
1952
1953   z = plus_constant_for_output (y, mode_sz - 1);
1954
1955   /* Use QImode because an odd displacement may be automatically invalid
1956      for any wider mode.  But it should be valid for a single byte.  */
1957   return (*addressp) (QImode, z);
1958 }
1959
1960 /* Return 1 if ADDR is an address-expression whose effect depends
1961    on the mode of the memory reference it is used in.
1962
1963    Autoincrement addressing is a typical example of mode-dependence
1964    because the amount of the increment depends on the mode.  */
1965
1966 int
1967 mode_dependent_address_p (addr)
1968   rtx addr ATTRIBUTE_UNUSED; /* Maybe used in GO_IF_MODE_DEPENDENT_ADDRESS. */
1969 {
1970   GO_IF_MODE_DEPENDENT_ADDRESS (addr, win);
1971   return 0;
1972   /* Label `win' might (not) be used via GO_IF_MODE_DEPENDENT_ADDRESS. */
1973  win: ATTRIBUTE_UNUSED_LABEL
1974   return 1;
1975 }
1976
1977 /* Return 1 if OP is a general operand
1978    other than a memory ref with a mode dependent address.  */
1979
1980 int
1981 mode_independent_operand (op, mode)
1982      enum machine_mode mode;
1983      rtx op;
1984 {
1985   rtx addr;
1986
1987   if (! general_operand (op, mode))
1988     return 0;
1989
1990   if (GET_CODE (op) != MEM)
1991     return 1;
1992
1993   addr = XEXP (op, 0);
1994   GO_IF_MODE_DEPENDENT_ADDRESS (addr, lose);
1995   return 1;
1996   /* Label `lose' might (not) be used via GO_IF_MODE_DEPENDENT_ADDRESS. */
1997  lose: ATTRIBUTE_UNUSED_LABEL
1998   return 0;
1999 }
2000
2001 /* Given an operand OP that is a valid memory reference which
2002    satisfies offsettable_memref_p, return a new memory reference whose
2003    address has been adjusted by OFFSET.  OFFSET should be positive and
2004    less than the size of the object referenced.  */
2005
2006 rtx
2007 adj_offsettable_operand (op, offset)
2008      rtx op;
2009      int offset;
2010 {
2011   register enum rtx_code code = GET_CODE (op);
2012
2013   if (code == MEM)
2014     {
2015       register rtx y = XEXP (op, 0);
2016       register rtx new;
2017
2018       if (CONSTANT_ADDRESS_P (y))
2019         {
2020           new = gen_rtx_MEM (GET_MODE (op),
2021                              plus_constant_for_output (y, offset));
2022           MEM_COPY_ATTRIBUTES (new, op);
2023           return new;
2024         }
2025
2026       if (GET_CODE (y) == PLUS)
2027         {
2028           rtx z = y;
2029           register rtx *const_loc;
2030
2031           op = copy_rtx (op);
2032           z = XEXP (op, 0);
2033           const_loc = find_constant_term_loc (&z);
2034           if (const_loc)
2035             {
2036               *const_loc = plus_constant_for_output (*const_loc, offset);
2037               return op;
2038             }
2039         }
2040
2041       new = gen_rtx_MEM (GET_MODE (op), plus_constant_for_output (y, offset));
2042       MEM_COPY_ATTRIBUTES (new, op);
2043       return new;
2044     }
2045   abort ();
2046 }
2047 \f
2048 /* Like extract_insn, but save insn extracted and don't extract again, when
2049    called again for the same insn expecting that recog_data still contain the
2050    valid information.  This is used primary by gen_attr infrastructure that
2051    often does extract insn again and again.  */
2052 void
2053 extract_insn_cached (insn)
2054      rtx insn;
2055 {
2056   if (recog_data.insn == insn && INSN_CODE (insn) >= 0)
2057     return;
2058   extract_insn (insn);
2059   recog_data.insn = insn;
2060 }
2061 /* Do cached extract_insn, constrain_operand and complain about failures.
2062    Used by insn_attrtab.  */
2063 void
2064 extract_constrain_insn_cached (insn)
2065      rtx insn;
2066 {
2067   extract_insn_cached (insn);
2068   if (which_alternative == -1
2069       && !constrain_operands (reload_completed))
2070     fatal_insn_not_found (insn);
2071 }
2072 \f
2073 /* Analyze INSN and fill in recog_data.  */
2074
2075 void
2076 extract_insn (insn)
2077      rtx insn;
2078 {
2079   int i;
2080   int icode;
2081   int noperands;
2082   rtx body = PATTERN (insn);
2083
2084   recog_data.insn = NULL;
2085   recog_data.n_operands = 0;
2086   recog_data.n_alternatives = 0;
2087   recog_data.n_dups = 0;
2088   which_alternative = -1;
2089
2090   switch (GET_CODE (body))
2091     {
2092     case USE:
2093     case CLOBBER:
2094     case ASM_INPUT:
2095     case ADDR_VEC:
2096     case ADDR_DIFF_VEC:
2097       return;
2098
2099     case SET:
2100     case PARALLEL:
2101     case ASM_OPERANDS:
2102       recog_data.n_operands = noperands = asm_noperands (body);
2103       if (noperands >= 0)
2104         {
2105           /* This insn is an `asm' with operands.  */
2106
2107           /* expand_asm_operands makes sure there aren't too many operands.  */
2108           if (noperands > MAX_RECOG_OPERANDS)
2109             abort ();
2110
2111           /* Now get the operand values and constraints out of the insn.  */
2112           decode_asm_operands (body, recog_data.operand,
2113                                recog_data.operand_loc,
2114                                recog_data.constraints,
2115                                recog_data.operand_mode);
2116           if (noperands > 0)
2117             {
2118               const char *p =  recog_data.constraints[0];
2119               recog_data.n_alternatives = 1;
2120               while (*p)
2121                 recog_data.n_alternatives += (*p++ == ',');
2122             }
2123           break;
2124         }
2125
2126       /* FALLTHROUGH */
2127
2128     default:
2129       /* Ordinary insn: recognize it, get the operands via insn_extract
2130          and get the constraints.  */
2131
2132       icode = recog_memoized (insn);
2133       if (icode < 0)
2134         fatal_insn_not_found (insn);
2135
2136       recog_data.n_operands = noperands = insn_data[icode].n_operands;
2137       recog_data.n_alternatives = insn_data[icode].n_alternatives;
2138       recog_data.n_dups = insn_data[icode].n_dups;
2139
2140       insn_extract (insn);
2141
2142       for (i = 0; i < noperands; i++)
2143         {
2144           recog_data.constraints[i] = insn_data[icode].operand[i].constraint;
2145           recog_data.operand_mode[i] = insn_data[icode].operand[i].mode;
2146           /* VOIDmode match_operands gets mode from their real operand.  */
2147           if (recog_data.operand_mode[i] == VOIDmode)
2148             recog_data.operand_mode[i] = GET_MODE (recog_data.operand[i]);
2149         }
2150     }
2151   for (i = 0; i < noperands; i++)
2152     recog_data.operand_type[i]
2153       = (recog_data.constraints[i][0] == '=' ? OP_OUT
2154          : recog_data.constraints[i][0] == '+' ? OP_INOUT
2155          : OP_IN);
2156
2157   if (recog_data.n_alternatives > MAX_RECOG_ALTERNATIVES)
2158     abort ();
2159 }
2160
2161 /* After calling extract_insn, you can use this function to extract some
2162    information from the constraint strings into a more usable form.
2163    The collected data is stored in recog_op_alt.  */
2164 void
2165 preprocess_constraints ()
2166 {
2167   int i;
2168
2169   memset (recog_op_alt, 0, sizeof recog_op_alt);
2170   for (i = 0; i < recog_data.n_operands; i++)
2171     {
2172       int j;
2173       struct operand_alternative *op_alt;
2174       const char *p = recog_data.constraints[i];
2175
2176       op_alt = recog_op_alt[i];
2177
2178       for (j = 0; j < recog_data.n_alternatives; j++)
2179         {
2180           op_alt[j].class = NO_REGS;
2181           op_alt[j].constraint = p;
2182           op_alt[j].matches = -1;
2183           op_alt[j].matched = -1;
2184
2185           if (*p == '\0' || *p == ',')
2186             {
2187               op_alt[j].anything_ok = 1;
2188               continue;
2189             }
2190
2191           for (;;)
2192             {
2193               char c = *p++;
2194               if (c == '#')
2195                 do
2196                   c = *p++;
2197                 while (c != ',' && c != '\0');
2198               if (c == ',' || c == '\0')
2199                 break;
2200
2201               switch (c)
2202                 {
2203                 case '=': case '+': case '*': case '%':
2204                 case 'E': case 'F': case 'G': case 'H':
2205                 case 's': case 'i': case 'n':
2206                 case 'I': case 'J': case 'K': case 'L':
2207                 case 'M': case 'N': case 'O': case 'P':
2208                   /* These don't say anything we care about.  */
2209                   break;
2210
2211                 case '?':
2212                   op_alt[j].reject += 6;
2213                   break;
2214                 case '!':
2215                   op_alt[j].reject += 600;
2216                   break;
2217                 case '&':
2218                   op_alt[j].earlyclobber = 1;
2219                   break;
2220
2221                 case '0': case '1': case '2': case '3': case '4':
2222                 case '5': case '6': case '7': case '8': case '9':
2223                   op_alt[j].matches = c - '0';
2224                   recog_op_alt[op_alt[j].matches][j].matched = i;
2225                   break;
2226
2227                 case 'm':
2228                   op_alt[j].memory_ok = 1;
2229                   break;
2230                 case '<':
2231                   op_alt[j].decmem_ok = 1;
2232                   break;
2233                 case '>':
2234                   op_alt[j].incmem_ok = 1;
2235                   break;
2236                 case 'V':
2237                   op_alt[j].nonoffmem_ok = 1;
2238                   break;
2239                 case 'o':
2240                   op_alt[j].offmem_ok = 1;
2241                   break;
2242                 case 'X':
2243                   op_alt[j].anything_ok = 1;
2244                   break;
2245
2246                 case 'p':
2247                   op_alt[j].class = reg_class_subunion[(int) op_alt[j].class][(int) BASE_REG_CLASS];
2248                   break;
2249
2250                 case 'g': case 'r':
2251                   op_alt[j].class = reg_class_subunion[(int) op_alt[j].class][(int) GENERAL_REGS];
2252                   break;
2253
2254                 default:
2255                   op_alt[j].class = reg_class_subunion[(int) op_alt[j].class][(int) REG_CLASS_FROM_LETTER ((unsigned char)c)];
2256                   break;
2257                 }
2258             }
2259         }
2260     }
2261 }
2262
2263 /* Check the operands of an insn against the insn's operand constraints
2264    and return 1 if they are valid.
2265    The information about the insn's operands, constraints, operand modes
2266    etc. is obtained from the global variables set up by extract_insn.
2267
2268    WHICH_ALTERNATIVE is set to a number which indicates which
2269    alternative of constraints was matched: 0 for the first alternative,
2270    1 for the next, etc.
2271
2272    In addition, when two operands are match
2273    and it happens that the output operand is (reg) while the
2274    input operand is --(reg) or ++(reg) (a pre-inc or pre-dec),
2275    make the output operand look like the input.
2276    This is because the output operand is the one the template will print.
2277
2278    This is used in final, just before printing the assembler code and by
2279    the routines that determine an insn's attribute.
2280
2281    If STRICT is a positive non-zero value, it means that we have been
2282    called after reload has been completed.  In that case, we must
2283    do all checks strictly.  If it is zero, it means that we have been called
2284    before reload has completed.  In that case, we first try to see if we can
2285    find an alternative that matches strictly.  If not, we try again, this
2286    time assuming that reload will fix up the insn.  This provides a "best
2287    guess" for the alternative and is used to compute attributes of insns prior
2288    to reload.  A negative value of STRICT is used for this internal call.  */
2289
2290 struct funny_match
2291 {
2292   int this, other;
2293 };
2294
2295 int
2296 constrain_operands (strict)
2297      int strict;
2298 {
2299   const char *constraints[MAX_RECOG_OPERANDS];
2300   int matching_operands[MAX_RECOG_OPERANDS];
2301   int earlyclobber[MAX_RECOG_OPERANDS];
2302   register int c;
2303
2304   struct funny_match funny_match[MAX_RECOG_OPERANDS];
2305   int funny_match_index;
2306
2307   if (recog_data.n_operands == 0 || recog_data.n_alternatives == 0)
2308     return 1;
2309
2310   for (c = 0; c < recog_data.n_operands; c++)
2311     {
2312       constraints[c] = recog_data.constraints[c];
2313       matching_operands[c] = -1;
2314     }
2315
2316   which_alternative = 0;
2317
2318   while (which_alternative < recog_data.n_alternatives)
2319     {
2320       register int opno;
2321       int lose = 0;
2322       funny_match_index = 0;
2323
2324       for (opno = 0; opno < recog_data.n_operands; opno++)
2325         {
2326           register rtx op = recog_data.operand[opno];
2327           enum machine_mode mode = GET_MODE (op);
2328           register const char *p = constraints[opno];
2329           int offset = 0;
2330           int win = 0;
2331           int val;
2332
2333           earlyclobber[opno] = 0;
2334
2335           /* A unary operator may be accepted by the predicate, but it
2336              is irrelevant for matching constraints.  */
2337           if (GET_RTX_CLASS (GET_CODE (op)) == '1')
2338             op = XEXP (op, 0);
2339
2340           if (GET_CODE (op) == SUBREG)
2341             {
2342               if (GET_CODE (SUBREG_REG (op)) == REG
2343                   && REGNO (SUBREG_REG (op)) < FIRST_PSEUDO_REGISTER)
2344                 offset = SUBREG_WORD (op);
2345               op = SUBREG_REG (op);
2346             }
2347
2348           /* An empty constraint or empty alternative
2349              allows anything which matched the pattern.  */
2350           if (*p == 0 || *p == ',')
2351             win = 1;
2352
2353           while (*p && (c = *p++) != ',')
2354             switch (c)
2355               {
2356               case '?':  case '!': case '*':  case '%':
2357               case '=':  case '+':
2358                 break;
2359
2360               case '#':
2361                 /* Ignore rest of this alternative as far as
2362                    constraint checking is concerned.  */
2363                 while (*p && *p != ',')
2364                   p++;
2365                 break;
2366
2367               case '&':
2368                 earlyclobber[opno] = 1;
2369                 break;
2370
2371               case '0':  case '1':  case '2':  case '3':  case '4':
2372               case '5':  case '6':  case '7':  case '8':  case '9':
2373
2374                 /* This operand must be the same as a previous one.
2375                    This kind of constraint is used for instructions such
2376                    as add when they take only two operands.
2377
2378                    Note that the lower-numbered operand is passed first.
2379
2380                    If we are not testing strictly, assume that this constraint
2381                    will be satisfied.  */
2382                 if (strict < 0)
2383                   val = 1;
2384                 else
2385                   {
2386                     rtx op1 = recog_data.operand[c - '0'];
2387                     rtx op2 = recog_data.operand[opno];
2388
2389                     /* A unary operator may be accepted by the predicate,
2390                        but it is irrelevant for matching constraints.  */
2391                     if (GET_RTX_CLASS (GET_CODE (op1)) == '1')
2392                       op1 = XEXP (op1, 0);
2393                     if (GET_RTX_CLASS (GET_CODE (op2)) == '1')
2394                       op2 = XEXP (op2, 0);
2395
2396                     val = operands_match_p (op1, op2);
2397                   }
2398
2399                 matching_operands[opno] = c - '0';
2400                 matching_operands[c - '0'] = opno;
2401
2402                 if (val != 0)
2403                   win = 1;
2404                 /* If output is *x and input is *--x,
2405                    arrange later to change the output to *--x as well,
2406                    since the output op is the one that will be printed.  */
2407                 if (val == 2 && strict > 0)
2408                   {
2409                     funny_match[funny_match_index].this = opno;
2410                     funny_match[funny_match_index++].other = c - '0';
2411                   }
2412                 break;
2413
2414               case 'p':
2415                 /* p is used for address_operands.  When we are called by
2416                    gen_reload, no one will have checked that the address is
2417                    strictly valid, i.e., that all pseudos requiring hard regs
2418                    have gotten them.  */
2419                 if (strict <= 0
2420                     || (strict_memory_address_p (recog_data.operand_mode[opno],
2421                                                  op)))
2422                   win = 1;
2423                 break;
2424
2425                 /* No need to check general_operand again;
2426                    it was done in insn-recog.c.  */
2427               case 'g':
2428                 /* Anything goes unless it is a REG and really has a hard reg
2429                    but the hard reg is not in the class GENERAL_REGS.  */
2430                 if (strict < 0
2431                     || GENERAL_REGS == ALL_REGS
2432                     || GET_CODE (op) != REG
2433                     || (reload_in_progress
2434                         && REGNO (op) >= FIRST_PSEUDO_REGISTER)
2435                     || reg_fits_class_p (op, GENERAL_REGS, offset, mode))
2436                   win = 1;
2437                 break;
2438
2439               case 'X':
2440                 /* This is used for a MATCH_SCRATCH in the cases when
2441                    we don't actually need anything.  So anything goes
2442                    any time.  */
2443                 win = 1;
2444                 break;
2445
2446               case 'm':
2447                 if (GET_CODE (op) == MEM
2448                     /* Before reload, accept what reload can turn into mem.  */
2449                     || (strict < 0 && CONSTANT_P (op))
2450                     /* During reload, accept a pseudo  */
2451                     || (reload_in_progress && GET_CODE (op) == REG
2452                         && REGNO (op) >= FIRST_PSEUDO_REGISTER))
2453                   win = 1;
2454                 break;
2455
2456               case '<':
2457                 if (GET_CODE (op) == MEM
2458                     && (GET_CODE (XEXP (op, 0)) == PRE_DEC
2459                         || GET_CODE (XEXP (op, 0)) == POST_DEC))
2460                   win = 1;
2461                 break;
2462
2463               case '>':
2464                 if (GET_CODE (op) == MEM
2465                     && (GET_CODE (XEXP (op, 0)) == PRE_INC
2466                         || GET_CODE (XEXP (op, 0)) == POST_INC))
2467                   win = 1;
2468                 break;
2469
2470               case 'E':
2471 #ifndef REAL_ARITHMETIC
2472                 /* Match any CONST_DOUBLE, but only if
2473                    we can examine the bits of it reliably.  */
2474                 if ((HOST_FLOAT_FORMAT != TARGET_FLOAT_FORMAT
2475                      || HOST_BITS_PER_WIDE_INT != BITS_PER_WORD)
2476                     && GET_MODE (op) != VOIDmode && ! flag_pretend_float)
2477                   break;
2478 #endif
2479                 if (GET_CODE (op) == CONST_DOUBLE)
2480                   win = 1;
2481                 break;
2482
2483               case 'F':
2484                 if (GET_CODE (op) == CONST_DOUBLE)
2485                   win = 1;
2486                 break;
2487
2488               case 'G':
2489               case 'H':
2490                 if (GET_CODE (op) == CONST_DOUBLE
2491                     && CONST_DOUBLE_OK_FOR_LETTER_P (op, c))
2492                   win = 1;
2493                 break;
2494
2495               case 's':
2496                 if (GET_CODE (op) == CONST_INT
2497                     || (GET_CODE (op) == CONST_DOUBLE
2498                         && GET_MODE (op) == VOIDmode))
2499                   break;
2500               case 'i':
2501                 if (CONSTANT_P (op))
2502                   win = 1;
2503                 break;
2504
2505               case 'n':
2506                 if (GET_CODE (op) == CONST_INT
2507                     || (GET_CODE (op) == CONST_DOUBLE
2508                         && GET_MODE (op) == VOIDmode))
2509                   win = 1;
2510                 break;
2511
2512               case 'I':
2513               case 'J':
2514               case 'K':
2515               case 'L':
2516               case 'M':
2517               case 'N':
2518               case 'O':
2519               case 'P':
2520                 if (GET_CODE (op) == CONST_INT
2521                     && CONST_OK_FOR_LETTER_P (INTVAL (op), c))
2522                   win = 1;
2523                 break;
2524
2525               case 'V':
2526                 if (GET_CODE (op) == MEM
2527                     && ((strict > 0 && ! offsettable_memref_p (op))
2528                         || (strict < 0
2529                             && !(CONSTANT_P (op) || GET_CODE (op) == MEM))
2530                         || (reload_in_progress
2531                             && !(GET_CODE (op) == REG
2532                                  && REGNO (op) >= FIRST_PSEUDO_REGISTER))))
2533                   win = 1;
2534                 break;
2535
2536               case 'o':
2537                 if ((strict > 0 && offsettable_memref_p (op))
2538                     || (strict == 0 && offsettable_nonstrict_memref_p (op))
2539                     /* Before reload, accept what reload can handle.  */
2540                     || (strict < 0
2541                         && (CONSTANT_P (op) || GET_CODE (op) == MEM))
2542                     /* During reload, accept a pseudo  */
2543                     || (reload_in_progress && GET_CODE (op) == REG
2544                         && REGNO (op) >= FIRST_PSEUDO_REGISTER))
2545                   win = 1;
2546                 break;
2547
2548               default:
2549                 {
2550                   enum reg_class class;
2551
2552                   class = (c == 'r' ? GENERAL_REGS : REG_CLASS_FROM_LETTER (c));
2553                   if (class != NO_REGS)
2554                     {
2555                       if (strict < 0
2556                           || (strict == 0
2557                               && GET_CODE (op) == REG
2558                               && REGNO (op) >= FIRST_PSEUDO_REGISTER)
2559                           || (strict == 0 && GET_CODE (op) == SCRATCH)
2560                           || (GET_CODE (op) == REG
2561                               && reg_fits_class_p (op, class, offset, mode)))
2562                         win = 1;
2563                     }
2564 #ifdef EXTRA_CONSTRAINT
2565                   else if (EXTRA_CONSTRAINT (op, c))
2566                     win = 1;
2567 #endif
2568                   break;
2569                 }
2570               }
2571
2572           constraints[opno] = p;
2573           /* If this operand did not win somehow,
2574              this alternative loses.  */
2575           if (! win)
2576             lose = 1;
2577         }
2578       /* This alternative won; the operands are ok.
2579          Change whichever operands this alternative says to change.  */
2580       if (! lose)
2581         {
2582           int opno, eopno;
2583
2584           /* See if any earlyclobber operand conflicts with some other
2585              operand.  */
2586
2587           if (strict > 0)
2588             for (eopno = 0; eopno < recog_data.n_operands; eopno++)
2589               /* Ignore earlyclobber operands now in memory,
2590                  because we would often report failure when we have
2591                  two memory operands, one of which was formerly a REG.  */
2592               if (earlyclobber[eopno]
2593                   && GET_CODE (recog_data.operand[eopno]) == REG)
2594                 for (opno = 0; opno < recog_data.n_operands; opno++)
2595                   if ((GET_CODE (recog_data.operand[opno]) == MEM
2596                        || recog_data.operand_type[opno] != OP_OUT)
2597                       && opno != eopno
2598                       /* Ignore things like match_operator operands.  */
2599                       && *recog_data.constraints[opno] != 0
2600                       && ! (matching_operands[opno] == eopno
2601                             && operands_match_p (recog_data.operand[opno],
2602                                                  recog_data.operand[eopno]))
2603                       && ! safe_from_earlyclobber (recog_data.operand[opno],
2604                                                    recog_data.operand[eopno]))
2605                     lose = 1;
2606
2607           if (! lose)
2608             {
2609               while (--funny_match_index >= 0)
2610                 {
2611                   recog_data.operand[funny_match[funny_match_index].other]
2612                     = recog_data.operand[funny_match[funny_match_index].this];
2613                 }
2614
2615               return 1;
2616             }
2617         }
2618
2619       which_alternative++;
2620     }
2621
2622   which_alternative = -1;
2623   /* If we are about to reject this, but we are not to test strictly,
2624      try a very loose test.  Only return failure if it fails also.  */
2625   if (strict == 0)
2626     return constrain_operands (-1);
2627   else
2628     return 0;
2629 }
2630
2631 /* Return 1 iff OPERAND (assumed to be a REG rtx)
2632    is a hard reg in class CLASS when its regno is offset by OFFSET
2633    and changed to mode MODE.
2634    If REG occupies multiple hard regs, all of them must be in CLASS.  */
2635
2636 int
2637 reg_fits_class_p (operand, class, offset, mode)
2638      rtx operand;
2639      register enum reg_class class;
2640      int offset;
2641      enum machine_mode mode;
2642 {
2643   register int regno = REGNO (operand);
2644   if (regno < FIRST_PSEUDO_REGISTER
2645       && TEST_HARD_REG_BIT (reg_class_contents[(int) class],
2646                             regno + offset))
2647     {
2648       register int sr;
2649       regno += offset;
2650       for (sr = HARD_REGNO_NREGS (regno, mode) - 1;
2651            sr > 0; sr--)
2652         if (! TEST_HARD_REG_BIT (reg_class_contents[(int) class],
2653                                  regno + sr))
2654           break;
2655       return sr == 0;
2656     }
2657
2658   return 0;
2659 }
2660 \f
2661 /* Split all insns in the function.  If UPD_LIFE, update life info after.  */
2662
2663 void
2664 split_all_insns (upd_life)
2665      int upd_life;
2666 {
2667   sbitmap blocks;
2668   int changed;
2669   int i;
2670
2671   blocks = sbitmap_alloc (n_basic_blocks);
2672   sbitmap_zero (blocks);
2673   changed = 0;
2674
2675   for (i = n_basic_blocks - 1; i >= 0; --i)
2676     {
2677       basic_block bb = BASIC_BLOCK (i);
2678       rtx insn, next;
2679
2680       for (insn = bb->head; insn ; insn = next)
2681         {
2682           rtx set;
2683
2684           /* Can't use `next_real_insn' because that might go across
2685              CODE_LABELS and short-out basic blocks.  */
2686           next = NEXT_INSN (insn);
2687           if (! INSN_P (insn))
2688             ;
2689
2690           /* Don't split no-op move insns.  These should silently
2691              disappear later in final.  Splitting such insns would
2692              break the code that handles REG_NO_CONFLICT blocks.  */
2693
2694           else if ((set = single_set (insn)) != NULL
2695                    && rtx_equal_p (SET_SRC (set), SET_DEST (set)))
2696             {
2697               /* Nops get in the way while scheduling, so delete them
2698                  now if register allocation has already been done.  It
2699                  is too risky to try to do this before register
2700                  allocation, and there are unlikely to be very many
2701                  nops then anyways.  */
2702               if (reload_completed)
2703                 {
2704                   PUT_CODE (insn, NOTE);
2705                   NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
2706                   NOTE_SOURCE_FILE (insn) = 0;
2707                 }
2708             }
2709           else
2710             {
2711               /* Split insns here to get max fine-grain parallelism.  */
2712               rtx first = PREV_INSN (insn);
2713               rtx last = try_split (PATTERN (insn), insn, 1);
2714
2715               if (last != insn)
2716                 {
2717                   SET_BIT (blocks, i);
2718                   changed = 1;
2719
2720                   /* try_split returns the NOTE that INSN became.  */
2721                   first = NEXT_INSN (first);
2722                   PUT_CODE (insn, NOTE);
2723                   NOTE_SOURCE_FILE (insn) = 0;
2724                   NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
2725
2726                   if (insn == bb->end)
2727                     {
2728                       bb->end = last;
2729                       break;
2730                     }
2731                 }
2732             }
2733
2734           if (insn == bb->end)
2735             break;
2736         }
2737
2738       /* ??? When we're called from just after reload, the CFG is in bad
2739          shape, and we may have fallen off the end.  This could be fixed
2740          by having reload not try to delete unreachable code.  Otherwise
2741          assert we found the end insn.  */
2742       if (insn == NULL && upd_life)
2743         abort ();
2744     }
2745
2746   if (changed && upd_life)
2747     {
2748       compute_bb_for_insn (get_max_uid ());
2749       count_or_remove_death_notes (blocks, 1);
2750       update_life_info (blocks, UPDATE_LIFE_LOCAL, PROP_DEATH_NOTES);
2751     }
2752
2753   sbitmap_free (blocks);
2754 }
2755 \f
2756 #ifdef HAVE_peephole2
2757 struct peep2_insn_data
2758 {
2759   rtx insn;
2760   regset live_before;
2761 };
2762
2763 static struct peep2_insn_data peep2_insn_data[MAX_INSNS_PER_PEEP2 + 1];
2764 static int peep2_current;
2765
2766 /* A non-insn marker indicating the last insn of the block.
2767    The live_before regset for this element is correct, indicating
2768    global_live_at_end for the block.  */
2769 #define PEEP2_EOB       pc_rtx
2770
2771 /* Return the Nth non-note insn after `current', or return NULL_RTX if it
2772    does not exist.  Used by the recognizer to find the next insn to match
2773    in a multi-insn pattern.  */
2774
2775 rtx
2776 peep2_next_insn (n)
2777      int n;
2778 {
2779   if (n >= MAX_INSNS_PER_PEEP2 + 1)
2780     abort ();
2781
2782   n += peep2_current;
2783   if (n >= MAX_INSNS_PER_PEEP2 + 1)
2784     n -= MAX_INSNS_PER_PEEP2 + 1;
2785
2786   if (peep2_insn_data[n].insn == PEEP2_EOB)
2787     return NULL_RTX;
2788   return peep2_insn_data[n].insn;
2789 }
2790
2791 /* Return true if REGNO is dead before the Nth non-note insn
2792    after `current'.  */
2793
2794 int
2795 peep2_regno_dead_p (ofs, regno)
2796      int ofs;
2797      int regno;
2798 {
2799   if (ofs >= MAX_INSNS_PER_PEEP2 + 1)
2800     abort ();
2801
2802   ofs += peep2_current;
2803   if (ofs >= MAX_INSNS_PER_PEEP2 + 1)
2804     ofs -= MAX_INSNS_PER_PEEP2 + 1;
2805
2806   if (peep2_insn_data[ofs].insn == NULL_RTX)
2807     abort ();
2808
2809   return ! REGNO_REG_SET_P (peep2_insn_data[ofs].live_before, regno);
2810 }
2811
2812 /* Similarly for a REG.  */
2813
2814 int
2815 peep2_reg_dead_p (ofs, reg)
2816      int ofs;
2817      rtx reg;
2818 {
2819   int regno, n;
2820
2821   if (ofs >= MAX_INSNS_PER_PEEP2 + 1)
2822     abort ();
2823
2824   ofs += peep2_current;
2825   if (ofs >= MAX_INSNS_PER_PEEP2 + 1)
2826     ofs -= MAX_INSNS_PER_PEEP2 + 1;
2827
2828   if (peep2_insn_data[ofs].insn == NULL_RTX)
2829     abort ();
2830
2831   regno = REGNO (reg);
2832   n = HARD_REGNO_NREGS (regno, GET_MODE (reg));
2833   while (--n >= 0)
2834     if (REGNO_REG_SET_P (peep2_insn_data[ofs].live_before, regno + n))
2835       return 0;
2836   return 1;
2837 }
2838
2839 /* Try to find a hard register of mode MODE, matching the register class in
2840    CLASS_STR, which is available at the beginning of insn CURRENT_INSN and
2841    remains available until the end of LAST_INSN.  LAST_INSN may be NULL_RTX,
2842    in which case the only condition is that the register must be available
2843    before CURRENT_INSN.
2844    Registers that already have bits set in REG_SET will not be considered.
2845
2846    If an appropriate register is available, it will be returned and the
2847    corresponding bit(s) in REG_SET will be set; otherwise, NULL_RTX is
2848    returned.  */
2849
2850 rtx
2851 peep2_find_free_register (from, to, class_str, mode, reg_set)
2852      int from, to;
2853      const char *class_str;
2854      enum machine_mode mode;
2855      HARD_REG_SET *reg_set;
2856 {
2857   static int search_ofs;
2858   enum reg_class class;
2859   HARD_REG_SET live;
2860   int i;
2861
2862   if (from >= MAX_INSNS_PER_PEEP2 + 1 || to >= MAX_INSNS_PER_PEEP2 + 1)
2863     abort ();
2864
2865   from += peep2_current;
2866   if (from >= MAX_INSNS_PER_PEEP2 + 1)
2867     from -= MAX_INSNS_PER_PEEP2 + 1;
2868   to += peep2_current;
2869   if (to >= MAX_INSNS_PER_PEEP2 + 1)
2870     to -= MAX_INSNS_PER_PEEP2 + 1;
2871
2872   if (peep2_insn_data[from].insn == NULL_RTX)
2873     abort ();
2874   REG_SET_TO_HARD_REG_SET (live, peep2_insn_data[from].live_before);
2875
2876   while (from != to)
2877     {
2878       HARD_REG_SET this_live;
2879
2880       if (++from >= MAX_INSNS_PER_PEEP2 + 1)
2881         from = 0;
2882       if (peep2_insn_data[from].insn == NULL_RTX)
2883         abort ();
2884       REG_SET_TO_HARD_REG_SET (this_live, peep2_insn_data[from].live_before);
2885       IOR_HARD_REG_SET (live, this_live);
2886     }
2887
2888   class = (class_str[0] == 'r' ? GENERAL_REGS
2889            : REG_CLASS_FROM_LETTER (class_str[0]));
2890
2891   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2892     {
2893       int raw_regno, regno, success, j;
2894
2895       /* Distribute the free registers as much as possible.  */
2896       raw_regno = search_ofs + i;
2897       if (raw_regno >= FIRST_PSEUDO_REGISTER)
2898         raw_regno -= FIRST_PSEUDO_REGISTER;
2899 #ifdef REG_ALLOC_ORDER
2900       regno = reg_alloc_order[raw_regno];
2901 #else
2902       regno = raw_regno;
2903 #endif
2904
2905       /* Don't allocate fixed registers.  */
2906       if (fixed_regs[regno])
2907         continue;
2908       /* Make sure the register is of the right class.  */
2909       if (! TEST_HARD_REG_BIT (reg_class_contents[class], regno))
2910         continue;
2911       /* And can support the mode we need.  */
2912       if (! HARD_REGNO_MODE_OK (regno, mode))
2913         continue;
2914       /* And that we don't create an extra save/restore.  */
2915       if (! call_used_regs[regno] && ! regs_ever_live[regno])
2916         continue;
2917       /* And we don't clobber traceback for noreturn functions.  */
2918       if ((regno == FRAME_POINTER_REGNUM || regno == HARD_FRAME_POINTER_REGNUM)
2919           && (! reload_completed || frame_pointer_needed))
2920         continue;
2921
2922       success = 1;
2923       for (j = HARD_REGNO_NREGS (regno, mode) - 1; j >= 0; j--)
2924         {
2925           if (TEST_HARD_REG_BIT (*reg_set, regno + j)
2926               || TEST_HARD_REG_BIT (live, regno + j))
2927             {
2928               success = 0;
2929               break;
2930             }
2931         }
2932       if (success)
2933         {
2934           for (j = HARD_REGNO_NREGS (regno, mode) - 1; j >= 0; j--)
2935             SET_HARD_REG_BIT (*reg_set, regno + j);
2936
2937           /* Start the next search with the next register.  */
2938           if (++raw_regno >= FIRST_PSEUDO_REGISTER)
2939             raw_regno = 0;
2940           search_ofs = raw_regno;
2941
2942           return gen_rtx_REG (mode, regno);
2943         }
2944     }
2945
2946   search_ofs = 0;
2947   return NULL_RTX;
2948 }
2949
2950 /* Perform the peephole2 optimization pass. */
2951
2952 void
2953 peephole2_optimize (dump_file)
2954      FILE *dump_file ATTRIBUTE_UNUSED;
2955 {
2956   regset_head rs_heads[MAX_INSNS_PER_PEEP2 + 2];
2957   rtx insn, prev;
2958   regset live;
2959   int i, b;
2960 #ifdef HAVE_conditional_execution
2961   sbitmap blocks;
2962   int changed;
2963 #endif
2964
2965   /* Initialize the regsets we're going to use.  */
2966   for (i = 0; i < MAX_INSNS_PER_PEEP2 + 1; ++i)
2967     peep2_insn_data[i].live_before = INITIALIZE_REG_SET (rs_heads[i]);
2968   live = INITIALIZE_REG_SET (rs_heads[i]);
2969
2970 #ifdef HAVE_conditional_execution
2971   blocks = sbitmap_alloc (n_basic_blocks);
2972   sbitmap_zero (blocks);
2973   changed = 0;
2974 #else
2975   count_or_remove_death_notes (NULL, 1);
2976 #endif
2977
2978   for (b = n_basic_blocks - 1; b >= 0; --b)
2979     {
2980       basic_block bb = BASIC_BLOCK (b);
2981       struct propagate_block_info *pbi;
2982
2983       /* Indicate that all slots except the last holds invalid data.  */
2984       for (i = 0; i < MAX_INSNS_PER_PEEP2; ++i)
2985         peep2_insn_data[i].insn = NULL_RTX;
2986
2987       /* Indicate that the last slot contains live_after data.  */
2988       peep2_insn_data[MAX_INSNS_PER_PEEP2].insn = PEEP2_EOB;
2989       peep2_current = MAX_INSNS_PER_PEEP2;
2990
2991       /* Start up propagation.  */
2992       COPY_REG_SET (live, bb->global_live_at_end);
2993       COPY_REG_SET (peep2_insn_data[MAX_INSNS_PER_PEEP2].live_before, live);
2994
2995 #ifdef HAVE_conditional_execution
2996       pbi = init_propagate_block_info (bb, live, NULL, 0);
2997 #else
2998       pbi = init_propagate_block_info (bb, live, NULL, PROP_DEATH_NOTES);
2999 #endif
3000
3001       for (insn = bb->end; ; insn = prev)
3002         {
3003           prev = PREV_INSN (insn);
3004           if (INSN_P (insn))
3005             {
3006               rtx try;
3007               int match_len;
3008
3009               /* Record this insn.  */
3010               if (--peep2_current < 0)
3011                 peep2_current = MAX_INSNS_PER_PEEP2;
3012               peep2_insn_data[peep2_current].insn = insn;
3013               propagate_one_insn (pbi, insn);
3014               COPY_REG_SET (peep2_insn_data[peep2_current].live_before, live);
3015
3016               /* Match the peephole.  */
3017               try = peephole2_insns (PATTERN (insn), insn, &match_len);
3018               if (try != NULL)
3019                 {
3020                   i = match_len + peep2_current;
3021                   if (i >= MAX_INSNS_PER_PEEP2 + 1)
3022                     i -= MAX_INSNS_PER_PEEP2 + 1;
3023
3024                   /* Replace the old sequence with the new.  */
3025                   flow_delete_insn_chain (insn, peep2_insn_data[i].insn);
3026                   try = emit_insn_after (try, prev);
3027
3028                   /* Adjust the basic block boundaries.  */
3029                   if (peep2_insn_data[i].insn == bb->end)
3030                     bb->end = try;
3031                   if (insn == bb->head)
3032                     bb->head = NEXT_INSN (prev);
3033
3034 #ifdef HAVE_conditional_execution
3035                   /* With conditional execution, we cannot back up the
3036                      live information so easily, since the conditional
3037                      death data structures are not so self-contained.
3038                      So record that we've made a modification to this
3039                      block and update life information at the end.  */
3040                   SET_BIT (blocks, b);
3041                   changed = 1;
3042
3043                   for (i = 0; i < MAX_INSNS_PER_PEEP2 + 1; ++i)
3044                     peep2_insn_data[i].insn = NULL_RTX;
3045                   peep2_insn_data[peep2_current].insn = PEEP2_EOB;
3046 #else
3047                   /* Back up lifetime information past the end of the
3048                      newly created sequence.  */
3049                   if (++i >= MAX_INSNS_PER_PEEP2 + 1)
3050                     i = 0;
3051                   COPY_REG_SET (live, peep2_insn_data[i].live_before);
3052
3053                   /* Update life information for the new sequence.  */
3054                   do
3055                     {
3056                       if (INSN_P (try))
3057                         {
3058                           if (--i < 0)
3059                             i = MAX_INSNS_PER_PEEP2;
3060                           peep2_insn_data[i].insn = try;
3061                           propagate_one_insn (pbi, try);
3062                           COPY_REG_SET (peep2_insn_data[i].live_before, live);
3063                         }
3064                       try = PREV_INSN (try);
3065                     }
3066                   while (try != prev);
3067
3068                   /* ??? Should verify that LIVE now matches what we
3069                      had before the new sequence.  */
3070
3071                   peep2_current = i;
3072 #endif
3073                 }
3074             }
3075
3076           if (insn == bb->head)
3077             break;
3078         }
3079
3080       free_propagate_block_info (pbi);
3081     }
3082
3083   for (i = 0; i < MAX_INSNS_PER_PEEP2 + 1; ++i)
3084     FREE_REG_SET (peep2_insn_data[i].live_before);
3085   FREE_REG_SET (live);
3086
3087 #ifdef HAVE_conditional_execution
3088   count_or_remove_death_notes (blocks, 1);
3089   update_life_info (blocks, UPDATE_LIFE_LOCAL, PROP_DEATH_NOTES);
3090   sbitmap_free (blocks);
3091 #endif
3092 }
3093 #endif /* HAVE_peephole2 */