gcc/combine.c

   1 /* Optimize by combining instructions for GNU compiler.
   2    Copyright (C) 1987, 88, 92-96, 1997 Free Software Foundation, Inc.
   3
   4 This file is part of GNU CC.
   5
   6 GNU CC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU CC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU CC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, USA.  */
  20
  21
  22 /* This module is essentially the "combiner" phase of the U. of Arizona
  23    Portable Optimizer, but redone to work on our list-structured
  24    representation for RTL instead of their string representation.
  25
  26    The LOG_LINKS of each insn identify the most recent assignment
  27    to each REG used in the insn.  It is a list of previous insns,
  28    each of which contains a SET for a REG that is used in this insn
  29    and not used or set in between.  LOG_LINKs never cross basic blocks.
  30    They were set up by the preceding pass (lifetime analysis).
  31
  32    We try to combine each pair of insns joined by a logical link.
  33    We also try to combine triples of insns A, B and C when
  34    C has a link back to B and B has a link back to A.
  35
  36    LOG_LINKS does not have links for use of the CC0.  They don't
  37    need to, because the insn that sets the CC0 is always immediately
  38    before the insn that tests it.  So we always regard a branch
  39    insn as having a logical link to the preceding insn.  The same is true
  40    for an insn explicitly using CC0.
  41
  42    We check (with use_crosses_set_p) to avoid combining in such a way
  43    as to move a computation to a place where its value would be different.
  44
  45    Combination is done by mathematically substituting the previous
  46    insn(s) values for the regs they set into the expressions in
  47    the later insns that refer to these regs.  If the result is a valid insn
  48    for our target machine, according to the machine description,
  49    we install it, delete the earlier insns, and update the data flow
  50    information (LOG_LINKS and REG_NOTES) for what we did.
  51
  52    There are a few exceptions where the dataflow information created by
  53    flow.c aren't completely updated:
  54
  55    - reg_live_length is not updated
  56    - reg_n_refs is not adjusted in the rare case when a register is
  57      no longer required in a computation
  58    - there are extremely rare cases (see distribute_regnotes) when a
  59      REG_DEAD note is lost
  60    - a LOG_LINKS entry that refers to an insn with multiple SETs may be
  61      removed because there is no way to know which register it was
  62      linking
  63
  64    To simplify substitution, we combine only when the earlier insn(s)
  65    consist of only a single assignment.  To simplify updating afterward,
  66    we never combine when a subroutine call appears in the middle.
  67
  68    Since we do not represent assignments to CC0 explicitly except when that
  69    is all an insn does, there is no LOG_LINKS entry in an insn that uses
  70    the condition code for the insn that set the condition code.
  71    Fortunately, these two insns must be consecutive.
  72    Therefore, every JUMP_INSN is taken to have an implicit logical link
  73    to the preceding insn.  This is not quite right, since non-jumps can
  74    also use the condition code; but in practice such insns would not
  75    combine anyway.  */
  76
  77 #include "config.h"
  78 #ifdef __STDC__
  79 #include <stdarg.h>
  80 #else
  81 #include <varargs.h>
  82 #endif
  83
  84 /* Must precede rtl.h for FFS.  */
  85 #include <stdio.h>
  86
  87 #include "rtl.h"
  88 #include "flags.h"
  89 #include "regs.h"
  90 #include "hard-reg-set.h"
  91 #include "expr.h"
  92 #include "basic-block.h"
  93 #include "insn-config.h"
  94 #include "insn-flags.h"
  95 #include "insn-codes.h"
  96 #include "insn-attr.h"
  97 #include "recog.h"
  98 #include "real.h"
  99
 100 /* It is not safe to use ordinary gen_lowpart in combine.
 101    Use gen_lowpart_for_combine instead.  See comments there.  */
 102 #define gen_lowpart dont_use_gen_lowpart_you_dummy
 103
 104 /* Number of attempts to combine instructions in this function.  */
 105
 106 static int combine_attempts;
 107
 108 /* Number of attempts that got as far as substitution in this function.  */
 109
 110 static int combine_merges;
 111
 112 /* Number of instructions combined with added SETs in this function.  */
 113
 114 static int combine_extras;
 115
 116 /* Number of instructions combined in this function.  */
 117
 118 static int combine_successes;
 119
 120 /* Totals over entire compilation.  */
 121
 122 static int total_attempts, total_merges, total_extras, total_successes;
 123
 124 /* Define a default value for REVERSIBLE_CC_MODE.
 125    We can never assume that a condition code mode is safe to reverse unless
 126    the md tells us so.  */
 127 #ifndef REVERSIBLE_CC_MODE
 128 #define REVERSIBLE_CC_MODE(MODE) 0
 129 #endif
 130 \f
 131 /* Vector mapping INSN_UIDs to cuids.
 132    The cuids are like uids but increase monotonically always.
 133    Combine always uses cuids so that it can compare them.
 134    But actually renumbering the uids, which we used to do,
 135    proves to be a bad idea because it makes it hard to compare
 136    the dumps produced by earlier passes with those from later passes.  */
 137
 138 static int *uid_cuid;
 139 static int max_uid_cuid;
 140
 141 /* Get the cuid of an insn.  */
 142
 143 #define INSN_CUID(INSN) \
 144 (INSN_UID (INSN) > max_uid_cuid ? insn_cuid (INSN) : uid_cuid[INSN_UID (INSN)])
 145
 146 /* Maximum register number, which is the size of the tables below.  */
 147
 148 static int combine_max_regno;
 149
 150 /* Record last point of death of (hard or pseudo) register n.  */
 151
 152 static rtx *reg_last_death;
 153
 154 /* Record last point of modification of (hard or pseudo) register n.  */
 155
 156 static rtx *reg_last_set;
 157
 158 /* Record the cuid of the last insn that invalidated memory
 159    (anything that writes memory, and subroutine calls, but not pushes).  */
 160
 161 static int mem_last_set;
 162
 163 /* Record the cuid of the last CALL_INSN
 164    so we can tell whether a potential combination crosses any calls.  */
 165
 166 static int last_call_cuid;
 167
 168 /* When `subst' is called, this is the insn that is being modified
 169    (by combining in a previous insn).  The PATTERN of this insn
 170    is still the old pattern partially modified and it should not be
 171    looked at, but this may be used to examine the successors of the insn
 172    to judge whether a simplification is valid.  */
 173
 174 static rtx subst_insn;
 175
 176 /* This is an insn that belongs before subst_insn, but is not currently
 177    on the insn chain.  */
 178
 179 static rtx subst_prev_insn;
 180
 181 /* This is the lowest CUID that `subst' is currently dealing with.
 182    get_last_value will not return a value if the register was set at or
 183    after this CUID.  If not for this mechanism, we could get confused if
 184    I2 or I1 in try_combine were an insn that used the old value of a register
 185    to obtain a new value.  In that case, we might erroneously get the
 186    new value of the register when we wanted the old one.  */
 187
 188 static int subst_low_cuid;
 189
 190 /* This contains any hard registers that are used in newpat; reg_dead_at_p
 191    must consider all these registers to be always live.  */
 192
 193 static HARD_REG_SET newpat_used_regs;
 194
 195 /* This is an insn to which a LOG_LINKS entry has been added.  If this
 196    insn is the earlier than I2 or I3, combine should rescan starting at
 197    that location.  */
 198
 199 static rtx added_links_insn;
 200
 201 /* Basic block number of the block in which we are performing combines.  */
 202 static int this_basic_block;
 203 \f
 204 /* The next group of arrays allows the recording of the last value assigned
 205    to (hard or pseudo) register n.  We use this information to see if a
 206    operation being processed is redundant given a prior operation performed
 207    on the register.  For example, an `and' with a constant is redundant if
 208    all the zero bits are already known to be turned off.
 209
 210    We use an approach similar to that used by cse, but change it in the
 211    following ways:
 212
 213    (1) We do not want to reinitialize at each label.
 214    (2) It is useful, but not critical, to know the actual value assigned
 215        to a register.  Often just its form is helpful.
 216
 217    Therefore, we maintain the following arrays:
 218
 219    reg_last_set_value           the last value assigned
 220    reg_last_set_label           records the value of label_tick when the
 221                                 register was assigned
 222    reg_last_set_table_tick      records the value of label_tick when a
 223                                 value using the register is assigned
 224    reg_last_set_invalid         set to non-zero when it is not valid
 225                                 to use the value of this register in some
 226                                 register's value
 227
 228    To understand the usage of these tables, it is important to understand
 229    the distinction between the value in reg_last_set_value being valid
 230    and the register being validly contained in some other expression in the
 231    table.
 232
 233    Entry I in reg_last_set_value is valid if it is non-zero, and either
 234    reg_n_sets[i] is 1 or reg_last_set_label[i] == label_tick.
 235
 236    Register I may validly appear in any expression returned for the value
 237    of another register if reg_n_sets[i] is 1.  It may also appear in the
 238    value for register J if reg_last_set_label[i] < reg_last_set_label[j] or
 239    reg_last_set_invalid[j] is zero.
 240
 241    If an expression is found in the table containing a register which may
 242    not validly appear in an expression, the register is replaced by
 243    something that won't match, (clobber (const_int 0)).
 244
 245    reg_last_set_invalid[i] is set non-zero when register I is being assigned
 246    to and reg_last_set_table_tick[i] == label_tick.  */
 247
 248 /* Record last value assigned to (hard or pseudo) register n.  */
 249
 250 static rtx *reg_last_set_value;
 251
 252 /* Record the value of label_tick when the value for register n is placed in
 253    reg_last_set_value[n].  */
 254
 255 static int *reg_last_set_label;
 256
 257 /* Record the value of label_tick when an expression involving register n
 258    is placed in reg_last_set_value.  */
 259
 260 static int *reg_last_set_table_tick;
 261
 262 /* Set non-zero if references to register n in expressions should not be
 263    used.  */
 264
 265 static char *reg_last_set_invalid;
 266
 267 /* Incremented for each label.  */
 268
 269 static int label_tick;
 270
 271 /* Some registers that are set more than once and used in more than one
 272    basic block are nevertheless always set in similar ways.  For example,
 273    a QImode register may be loaded from memory in two places on a machine
 274    where byte loads zero extend.
 275
 276    We record in the following array what we know about the nonzero
 277    bits of a register, specifically which bits are known to be zero.
 278
 279    If an entry is zero, it means that we don't know anything special.  */
 280
 281 static unsigned HOST_WIDE_INT *reg_nonzero_bits;
 282
 283 /* Mode used to compute significance in reg_nonzero_bits.  It is the largest
 284    integer mode that can fit in HOST_BITS_PER_WIDE_INT.  */
 285
 286 static enum machine_mode nonzero_bits_mode;
 287
 288 /* Nonzero if we know that a register has some leading bits that are always
 289    equal to the sign bit.  */
 290
 291 static char *reg_sign_bit_copies;
 292
 293 /* Nonzero when reg_nonzero_bits and reg_sign_bit_copies can be safely used.
 294    It is zero while computing them and after combine has completed.  This
 295    former test prevents propagating values based on previously set values,
 296    which can be incorrect if a variable is modified in a loop.  */
 297
 298 static int nonzero_sign_valid;
 299
 300 /* These arrays are maintained in parallel with reg_last_set_value
 301    and are used to store the mode in which the register was last set,
 302    the bits that were known to be zero when it was last set, and the
 303    number of sign bits copies it was known to have when it was last set.  */
 304
 305 static enum machine_mode *reg_last_set_mode;
 306 static unsigned HOST_WIDE_INT *reg_last_set_nonzero_bits;
 307 static char *reg_last_set_sign_bit_copies;
 308 \f
 309 /* Record one modification to rtl structure
 310    to be undone by storing old_contents into *where.
 311    is_int is 1 if the contents are an int.  */
 312
 313 struct undo
 314 {
 315   struct undo *next;
 316   int is_int;
 317   union {rtx r; int i;} old_contents;
 318   union {rtx *r; int *i;} where;
 319 };
 320
 321 /* Record a bunch of changes to be undone, up to MAX_UNDO of them.
 322    num_undo says how many are currently recorded.
 323
 324    storage is nonzero if we must undo the allocation of new storage.
 325    The value of storage is what to pass to obfree.
 326
 327    other_insn is nonzero if we have modified some other insn in the process
 328    of working on subst_insn.  It must be verified too.
 329
 330    previous_undos is the value of undobuf.undos when we started processing
 331    this substitution.  This will prevent gen_rtx_combine from re-used a piece
 332    from the previous expression.  Doing so can produce circular rtl
 333    structures.  */
 334
 335 struct undobuf
 336 {
 337   char *storage;
 338   struct undo *undos;
 339   struct undo *frees;
 340   struct undo *previous_undos;
 341   rtx other_insn;
 342 };
 343
 344 static struct undobuf undobuf;
 345
 346 /* Substitute NEWVAL, an rtx expression, into INTO, a place in some
 347    insn.  The substitution can be undone by undo_all.  If INTO is already
 348    set to NEWVAL, do not record this change.  Because computing NEWVAL might
 349    also call SUBST, we have to compute it before we put anything into
 350    the undo table.  */
 351
 352 #define SUBST(INTO, NEWVAL)  \
 353  do { rtx _new = (NEWVAL);                                      \
 354       struct undo *_buf;                                        \
 355                                                                 \
 356       if (undobuf.frees)                                        \
 357         _buf = undobuf.frees, undobuf.frees = _buf->next;       \
 358       else                                                      \
 359         _buf = (struct undo *) xmalloc (sizeof (struct undo));  \
 360                                                                 \
 361       _buf->is_int = 0;                                         \
 362       _buf->where.r = &INTO;                                    \
 363       _buf->old_contents.r = INTO;                              \
 364       INTO = _new;                                              \
 365       if (_buf->old_contents.r == INTO)                         \
 366         _buf->next = undobuf.frees, undobuf.frees = _buf;       \
 367       else                                                      \
 368         _buf->next = undobuf.undos, undobuf.undos = _buf;       \
 369     } while (0)
 370
 371 /* Similar to SUBST, but NEWVAL is an int expression.  Note that substitution
 372    for the value of a HOST_WIDE_INT value (including CONST_INT) is
 373    not safe.  */
 374
 375 #define SUBST_INT(INTO, NEWVAL)  \
 376  do { struct undo *_buf;                                        \
 377                                                                 \
 378       if (undobuf.frees)                                        \
 379         _buf = undobuf.frees, undobuf.frees = _buf->next;       \
 380       else                                                      \
 381         _buf = (struct undo *) xmalloc (sizeof (struct undo));  \
 382                                                                 \
 383       _buf->is_int = 1;                                         \
 384       _buf->where.i = (int *) &INTO;                            \
 385       _buf->old_contents.i = INTO;                              \
 386       INTO = NEWVAL;                                            \
 387       if (_buf->old_contents.i == INTO)                         \
 388         _buf->next = undobuf.frees, undobuf.frees = _buf;       \
 389       else                                                      \
 390         _buf->next = undobuf.undos, undobuf.undos = _buf;       \
 391      } while (0)
 392
 393 /* Number of times the pseudo being substituted for
 394    was found and replaced.  */
 395
 396 static int n_occurrences;
 397
 398 static void init_reg_last_arrays        PROTO((void));
 399 static void setup_incoming_promotions   PROTO((void));
 400 static void set_nonzero_bits_and_sign_copies  PROTO((rtx, rtx));
 401 static int can_combine_p        PROTO((rtx, rtx, rtx, rtx, rtx *, rtx *));
 402 static int combinable_i3pat     PROTO((rtx, rtx *, rtx, rtx, int, rtx *));
 403 static rtx try_combine          PROTO((rtx, rtx, rtx));
 404 static void undo_all            PROTO((void));
 405 static rtx *find_split_point    PROTO((rtx *, rtx));
 406 static rtx subst                PROTO((rtx, rtx, rtx, int, int));
 407 static rtx simplify_rtx         PROTO((rtx, enum machine_mode, int, int));
 408 static rtx simplify_if_then_else  PROTO((rtx));
 409 static rtx simplify_set         PROTO((rtx));
 410 static rtx simplify_logical     PROTO((rtx, int));
 411 static rtx expand_compound_operation  PROTO((rtx));
 412 static rtx expand_field_assignment  PROTO((rtx));
 413 static rtx make_extraction      PROTO((enum machine_mode, rtx, int, rtx, int,
 414                                        int, int, int));
 415 static rtx extract_left_shift   PROTO((rtx, int));
 416 static rtx make_compound_operation  PROTO((rtx, enum rtx_code));
 417 static int get_pos_from_mask    PROTO((unsigned HOST_WIDE_INT, int *));
 418 static rtx force_to_mode        PROTO((rtx, enum machine_mode,
 419                                        unsigned HOST_WIDE_INT, rtx, int));
 420 static rtx if_then_else_cond    PROTO((rtx, rtx *, rtx *));
 421 static rtx known_cond           PROTO((rtx, enum rtx_code, rtx, rtx));
 422 static int rtx_equal_for_field_assignment_p PROTO((rtx, rtx));
 423 static rtx make_field_assignment  PROTO((rtx));
 424 static rtx apply_distributive_law  PROTO((rtx));
 425 static rtx simplify_and_const_int  PROTO((rtx, enum machine_mode, rtx,
 426                                           unsigned HOST_WIDE_INT));
 427 static unsigned HOST_WIDE_INT nonzero_bits  PROTO((rtx, enum machine_mode));
 428 static int num_sign_bit_copies  PROTO((rtx, enum machine_mode));
 429 static int merge_outer_ops      PROTO((enum rtx_code *, HOST_WIDE_INT *,
 430                                        enum rtx_code, HOST_WIDE_INT,
 431                                        enum machine_mode, int *));
 432 static rtx simplify_shift_const PROTO((rtx, enum rtx_code, enum machine_mode,
 433                                        rtx, int));
 434 static int recog_for_combine    PROTO((rtx *, rtx, rtx *, int *));
 435 static rtx gen_lowpart_for_combine  PROTO((enum machine_mode, rtx));
 436 static rtx gen_rtx_combine PVPROTO((enum rtx_code code, enum machine_mode mode,
 437                                   ...));
 438 static rtx gen_binary           PROTO((enum rtx_code, enum machine_mode,
 439                                        rtx, rtx));
 440 static rtx gen_unary            PROTO((enum rtx_code, enum machine_mode,
 441                                        enum machine_mode, rtx));
 442 static enum rtx_code simplify_comparison  PROTO((enum rtx_code, rtx *, rtx *));
 443 static int reversible_comparison_p  PROTO((rtx));
 444 static void update_table_tick   PROTO((rtx));
 445 static void record_value_for_reg  PROTO((rtx, rtx, rtx));
 446 static void record_dead_and_set_regs_1  PROTO((rtx, rtx));
 447 static void record_dead_and_set_regs  PROTO((rtx));
 448 static int get_last_value_validate  PROTO((rtx *, rtx, int, int));
 449 static rtx get_last_value       PROTO((rtx));
 450 static int use_crosses_set_p    PROTO((rtx, int));
 451 static void reg_dead_at_p_1     PROTO((rtx, rtx));
 452 static int reg_dead_at_p        PROTO((rtx, rtx));
 453 static void move_deaths         PROTO((rtx, rtx, int, rtx, rtx *));
 454 static int reg_bitfield_target_p  PROTO((rtx, rtx));
 455 static void distribute_notes    PROTO((rtx, rtx, rtx, rtx, rtx, rtx));
 456 static void distribute_links    PROTO((rtx));
 457 static void mark_used_regs_combine PROTO((rtx));
 458 static int insn_cuid            PROTO((rtx));
 459 \f
 460 /* Main entry point for combiner.  F is the first insn of the function.
 461    NREGS is the first unused pseudo-reg number.  */
 462
 463 void
 464 combine_instructions (f, nregs)
 465      rtx f;
 466      int nregs;
 467 {
 468   register rtx insn, next, prev;
 469   register int i;
 470   register rtx links, nextlinks;
 471
 472   combine_attempts = 0;
 473   combine_merges = 0;
 474   combine_extras = 0;
 475   combine_successes = 0;
 476   undobuf.undos = undobuf.previous_undos = 0;
 477
 478   combine_max_regno = nregs;
 479
 480   reg_nonzero_bits
 481     = (unsigned HOST_WIDE_INT *) alloca (nregs * sizeof (HOST_WIDE_INT));
 482   reg_sign_bit_copies = (char *) alloca (nregs * sizeof (char));
 483
 484   bzero ((char *) reg_nonzero_bits, nregs * sizeof (HOST_WIDE_INT));
 485   bzero (reg_sign_bit_copies, nregs * sizeof (char));
 486
 487   reg_last_death = (rtx *) alloca (nregs * sizeof (rtx));
 488   reg_last_set = (rtx *) alloca (nregs * sizeof (rtx));
 489   reg_last_set_value = (rtx *) alloca (nregs * sizeof (rtx));
 490   reg_last_set_table_tick = (int *) alloca (nregs * sizeof (int));
 491   reg_last_set_label = (int *) alloca (nregs * sizeof (int));
 492   reg_last_set_invalid = (char *) alloca (nregs * sizeof (char));
 493   reg_last_set_mode
 494     = (enum machine_mode *) alloca (nregs * sizeof (enum machine_mode));
 495   reg_last_set_nonzero_bits
 496     = (unsigned HOST_WIDE_INT *) alloca (nregs * sizeof (HOST_WIDE_INT));
 497   reg_last_set_sign_bit_copies
 498     = (char *) alloca (nregs * sizeof (char));
 499
 500   init_reg_last_arrays ();
 501
 502   init_recog_no_volatile ();
 503
 504   /* Compute maximum uid value so uid_cuid can be allocated.  */
 505
 506   for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
 507     if (INSN_UID (insn) > i)
 508       i = INSN_UID (insn);
 509
 510   uid_cuid = (int *) alloca ((i + 1) * sizeof (int));
 511   max_uid_cuid = i;
 512
 513   nonzero_bits_mode = mode_for_size (HOST_BITS_PER_WIDE_INT, MODE_INT, 0);
 514
 515   /* Don't use reg_nonzero_bits when computing it.  This can cause problems
 516      when, for example, we have j <<= 1 in a loop.  */
 517
 518   nonzero_sign_valid = 0;
 519
 520   /* Compute the mapping from uids to cuids.
 521      Cuids are numbers assigned to insns, like uids,
 522      except that cuids increase monotonically through the code.
 523
 524      Scan all SETs and see if we can deduce anything about what
 525      bits are known to be zero for some registers and how many copies
 526      of the sign bit are known to exist for those registers.
 527
 528      Also set any known values so that we can use it while searching
 529      for what bits are known to be set.  */
 530
 531   label_tick = 1;
 532
 533   /* We need to initialize it here, because record_dead_and_set_regs may call
 534      get_last_value.  */
 535   subst_prev_insn = NULL_RTX;
 536
 537   setup_incoming_promotions ();
 538
 539   for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
 540     {
 541       uid_cuid[INSN_UID (insn)] = ++i;
 542       subst_low_cuid = i;
 543       subst_insn = insn;
 544
 545       if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
 546         {
 547           note_stores (PATTERN (insn), set_nonzero_bits_and_sign_copies);
 548           record_dead_and_set_regs (insn);
 549
 550 #ifdef AUTO_INC_DEC
 551           for (links = REG_NOTES (insn); links; links = XEXP (links, 1))
 552             if (REG_NOTE_KIND (links) == REG_INC)
 553               set_nonzero_bits_and_sign_copies (XEXP (links, 0), NULL_RTX);
 554 #endif
 555         }
 556
 557       if (GET_CODE (insn) == CODE_LABEL)
 558         label_tick++;
 559     }
 560
 561   nonzero_sign_valid = 1;
 562
 563   /* Now scan all the insns in forward order.  */
 564
 565   this_basic_block = -1;
 566   label_tick = 1;
 567   last_call_cuid = 0;
 568   mem_last_set = 0;
 569   init_reg_last_arrays ();
 570   setup_incoming_promotions ();
 571
 572   for (insn = f; insn; insn = next ? next : NEXT_INSN (insn))
 573     {
 574       next = 0;
 575
 576       /* If INSN starts a new basic block, update our basic block number.  */
 577       if (this_basic_block + 1 < n_basic_blocks
 578           && basic_block_head[this_basic_block + 1] == insn)
 579         this_basic_block++;
 580
 581       if (GET_CODE (insn) == CODE_LABEL)
 582         label_tick++;
 583
 584       else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
 585         {
 586           /* Try this insn with each insn it links back to.  */
 587
 588           for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
 589             if ((next = try_combine (insn, XEXP (links, 0), NULL_RTX)) != 0)
 590               goto retry;
 591
 592           /* Try each sequence of three linked insns ending with this one.  */
 593
 594           for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
 595             for (nextlinks = LOG_LINKS (XEXP (links, 0)); nextlinks;
 596                  nextlinks = XEXP (nextlinks, 1))
 597               if ((next = try_combine (insn, XEXP (links, 0),
 598                                        XEXP (nextlinks, 0))) != 0)
 599                 goto retry;
 600
 601 #ifdef HAVE_cc0
 602           /* Try to combine a jump insn that uses CC0
 603              with a preceding insn that sets CC0, and maybe with its
 604              logical predecessor as well.
 605              This is how we make decrement-and-branch insns.
 606              We need this special code because data flow connections
 607              via CC0 do not get entered in LOG_LINKS.  */
 608
 609           if (GET_CODE (insn) == JUMP_INSN
 610               && (prev = prev_nonnote_insn (insn)) != 0
 611               && GET_CODE (prev) == INSN
 612               && sets_cc0_p (PATTERN (prev)))
 613             {
 614               if ((next = try_combine (insn, prev, NULL_RTX)) != 0)
 615                 goto retry;
 616
 617               for (nextlinks = LOG_LINKS (prev); nextlinks;
 618                    nextlinks = XEXP (nextlinks, 1))
 619                 if ((next = try_combine (insn, prev,
 620                                          XEXP (nextlinks, 0))) != 0)
 621                   goto retry;
 622             }
 623
 624           /* Do the same for an insn that explicitly references CC0.  */
 625           if (GET_CODE (insn) == INSN
 626               && (prev = prev_nonnote_insn (insn)) != 0
 627               && GET_CODE (prev) == INSN
 628               && sets_cc0_p (PATTERN (prev))
 629               && GET_CODE (PATTERN (insn)) == SET
 630               && reg_mentioned_p (cc0_rtx, SET_SRC (PATTERN (insn))))
 631             {
 632               if ((next = try_combine (insn, prev, NULL_RTX)) != 0)
 633                 goto retry;
 634
 635               for (nextlinks = LOG_LINKS (prev); nextlinks;
 636                    nextlinks = XEXP (nextlinks, 1))
 637                 if ((next = try_combine (insn, prev,
 638                                          XEXP (nextlinks, 0))) != 0)
 639                   goto retry;
 640             }
 641
 642           /* Finally, see if any of the insns that this insn links to
 643              explicitly references CC0.  If so, try this insn, that insn,
 644              and its predecessor if it sets CC0.  */
 645           for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
 646             if (GET_CODE (XEXP (links, 0)) == INSN
 647                 && GET_CODE (PATTERN (XEXP (links, 0))) == SET
 648                 && reg_mentioned_p (cc0_rtx, SET_SRC (PATTERN (XEXP (links, 0))))
 649                 && (prev = prev_nonnote_insn (XEXP (links, 0))) != 0
 650                 && GET_CODE (prev) == INSN
 651                 && sets_cc0_p (PATTERN (prev))
 652                 && (next = try_combine (insn, XEXP (links, 0), prev)) != 0)
 653               goto retry;
 654 #endif
 655
 656           /* Try combining an insn with two different insns whose results it
 657              uses.  */
 658           for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
 659             for (nextlinks = XEXP (links, 1); nextlinks;
 660                  nextlinks = XEXP (nextlinks, 1))
 661               if ((next = try_combine (insn, XEXP (links, 0),
 662                                        XEXP (nextlinks, 0))) != 0)
 663                 goto retry;
 664
 665           if (GET_CODE (insn) != NOTE)
 666             record_dead_and_set_regs (insn);
 667
 668         retry:
 669           ;
 670         }
 671     }
 672
 673   total_attempts += combine_attempts;
 674   total_merges += combine_merges;
 675   total_extras += combine_extras;
 676   total_successes += combine_successes;
 677
 678   nonzero_sign_valid = 0;
 679 }
 680
 681 /* Wipe the reg_last_xxx arrays in preparation for another pass.  */
 682
 683 static void
 684 init_reg_last_arrays ()
 685 {
 686   int nregs = combine_max_regno;
 687
 688   bzero ((char *) reg_last_death, nregs * sizeof (rtx));
 689   bzero ((char *) reg_last_set, nregs * sizeof (rtx));
 690   bzero ((char *) reg_last_set_value, nregs * sizeof (rtx));
 691   bzero ((char *) reg_last_set_table_tick, nregs * sizeof (int));
 692   bzero ((char *) reg_last_set_label, nregs * sizeof (int));
 693   bzero (reg_last_set_invalid, nregs * sizeof (char));
 694   bzero ((char *) reg_last_set_mode, nregs * sizeof (enum machine_mode));
 695   bzero ((char *) reg_last_set_nonzero_bits, nregs * sizeof (HOST_WIDE_INT));
 696   bzero (reg_last_set_sign_bit_copies, nregs * sizeof (char));
 697 }
 698 \f
 699 /* Set up any promoted values for incoming argument registers.  */
 700
 701 static void
 702 setup_incoming_promotions ()
 703 {
 704 #ifdef PROMOTE_FUNCTION_ARGS
 705   int regno;
 706   rtx reg;
 707   enum machine_mode mode;
 708   int unsignedp;
 709   rtx first = get_insns ();
 710
 711   for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
 712     if (FUNCTION_ARG_REGNO_P (regno)
 713         && (reg = promoted_input_arg (regno, &mode, &unsignedp)) != 0)
 714       record_value_for_reg (reg, first,
 715                             gen_rtx (unsignedp ? ZERO_EXTEND : SIGN_EXTEND,
 716                                      GET_MODE (reg),
 717                                      gen_rtx (CLOBBER, mode, const0_rtx)));
 718 #endif
 719 }
 720 \f
 721 /* Called via note_stores.  If X is a pseudo that is narrower than
 722    HOST_BITS_PER_WIDE_INT and is being set, record what bits are known zero.
 723
 724    If we are setting only a portion of X and we can't figure out what
 725    portion, assume all bits will be used since we don't know what will
 726    be happening.
 727
 728    Similarly, set how many bits of X are known to be copies of the sign bit
 729    at all locations in the function.  This is the smallest number implied
 730    by any set of X.  */
 731
 732 static void
 733 set_nonzero_bits_and_sign_copies (x, set)
 734      rtx x;
 735      rtx set;
 736 {
 737   int num;
 738
 739   if (GET_CODE (x) == REG
 740       && REGNO (x) >= FIRST_PSEUDO_REGISTER
 741       /* If this register is undefined at the start of the file, we can't
 742          say what its contents were.  */
 743       && ! REGNO_REG_SET_P (basic_block_live_at_start[0], REGNO (x))
 744       && GET_MODE_BITSIZE (GET_MODE (x)) <= HOST_BITS_PER_WIDE_INT)
 745     {
 746       if (set == 0 || GET_CODE (set) == CLOBBER)
 747         {
 748           reg_nonzero_bits[REGNO (x)] = GET_MODE_MASK (GET_MODE (x));
 749           reg_sign_bit_copies[REGNO (x)] = 1;
 750           return;
 751         }
 752
 753       /* If this is a complex assignment, see if we can convert it into a
 754          simple assignment.  */
 755       set = expand_field_assignment (set);
 756
 757       /* If this is a simple assignment, or we have a paradoxical SUBREG,
 758          set what we know about X.  */
 759
 760       if (SET_DEST (set) == x
 761           || (GET_CODE (SET_DEST (set)) == SUBREG
 762               && (GET_MODE_SIZE (GET_MODE (SET_DEST (set)))
 763                   > GET_MODE_SIZE (GET_MODE (SUBREG_REG (SET_DEST (set)))))
 764               && SUBREG_REG (SET_DEST (set)) == x))
 765         {
 766           rtx src = SET_SRC (set);
 767
 768 #ifdef SHORT_IMMEDIATES_SIGN_EXTEND
 769           /* If X is narrower than a word and SRC is a non-negative
 770              constant that would appear negative in the mode of X,
 771              sign-extend it for use in reg_nonzero_bits because some
 772              machines (maybe most) will actually do the sign-extension
 773              and this is the conservative approach.
 774
 775              ??? For 2.5, try to tighten up the MD files in this regard
 776              instead of this kludge.  */
 777
 778           if (GET_MODE_BITSIZE (GET_MODE (x)) < BITS_PER_WORD
 779               && GET_CODE (src) == CONST_INT
 780               && INTVAL (src) > 0
 781               && 0 != (INTVAL (src)
 782                        & ((HOST_WIDE_INT) 1
 783                           << (GET_MODE_BITSIZE (GET_MODE (x)) - 1))))
 784             src = GEN_INT (INTVAL (src)
 785                            | ((HOST_WIDE_INT) (-1)
 786                               << GET_MODE_BITSIZE (GET_MODE (x))));
 787 #endif
 788
 789           reg_nonzero_bits[REGNO (x)]
 790             |= nonzero_bits (src, nonzero_bits_mode);
 791           num = num_sign_bit_copies (SET_SRC (set), GET_MODE (x));
 792           if (reg_sign_bit_copies[REGNO (x)] == 0
 793               || reg_sign_bit_copies[REGNO (x)] > num)
 794             reg_sign_bit_copies[REGNO (x)] = num;
 795         }
 796       else
 797         {
 798           reg_nonzero_bits[REGNO (x)] = GET_MODE_MASK (GET_MODE (x));
 799           reg_sign_bit_copies[REGNO (x)] = 1;
 800         }
 801     }
 802 }
 803 \f
 804 /* See if INSN can be combined into I3.  PRED and SUCC are optionally
 805    insns that were previously combined into I3 or that will be combined
 806    into the merger of INSN and I3.
 807
 808    Return 0 if the combination is not allowed for any reason.
 809
 810    If the combination is allowed, *PDEST will be set to the single
 811    destination of INSN and *PSRC to the single source, and this function
 812    will return 1.  */
 813
 814 static int
 815 can_combine_p (insn, i3, pred, succ, pdest, psrc)
 816      rtx insn;
 817      rtx i3;
 818      rtx pred, succ;
 819      rtx *pdest, *psrc;
 820 {
 821   int i;
 822   rtx set = 0, src, dest;
 823   rtx p, link;
 824   int all_adjacent = (succ ? (next_active_insn (insn) == succ
 825                               && next_active_insn (succ) == i3)
 826                       : next_active_insn (insn) == i3);
 827
 828   /* Can combine only if previous insn is a SET of a REG, a SUBREG or CC0.
 829      or a PARALLEL consisting of such a SET and CLOBBERs.
 830
 831      If INSN has CLOBBER parallel parts, ignore them for our processing.
 832      By definition, these happen during the execution of the insn.  When it
 833      is merged with another insn, all bets are off.  If they are, in fact,
 834      needed and aren't also supplied in I3, they may be added by
 835      recog_for_combine.  Otherwise, it won't match.
 836
 837      We can also ignore a SET whose SET_DEST is mentioned in a REG_UNUSED
 838      note.
 839
 840      Get the source and destination of INSN.  If more than one, can't
 841      combine.  */
 842
 843   if (GET_CODE (PATTERN (insn)) == SET)
 844     set = PATTERN (insn);
 845   else if (GET_CODE (PATTERN (insn)) == PARALLEL
 846            && GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) == SET)
 847     {
 848       for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++)
 849         {
 850           rtx elt = XVECEXP (PATTERN (insn), 0, i);
 851
 852           switch (GET_CODE (elt))
 853             {
 854               /* We can ignore CLOBBERs.  */
 855             case CLOBBER:
 856               break;
 857
 858             case SET:
 859               /* Ignore SETs whose result isn't used but not those that
 860                  have side-effects.  */
 861               if (find_reg_note (insn, REG_UNUSED, SET_DEST (elt))
 862                   && ! side_effects_p (elt))
 863                 break;
 864
 865               /* If we have already found a SET, this is a second one and
 866                  so we cannot combine with this insn.  */
 867               if (set)
 868                 return 0;
 869
 870               set = elt;
 871               break;
 872
 873             default:
 874               /* Anything else means we can't combine.  */
 875               return 0;
 876             }
 877         }
 878
 879       if (set == 0
 880           /* If SET_SRC is an ASM_OPERANDS we can't throw away these CLOBBERs,
 881              so don't do anything with it.  */
 882           || GET_CODE (SET_SRC (set)) == ASM_OPERANDS)
 883         return 0;
 884     }
 885   else
 886     return 0;
 887
 888   if (set == 0)
 889     return 0;
 890
 891   set = expand_field_assignment (set);
 892   src = SET_SRC (set), dest = SET_DEST (set);
 893
 894   /* Don't eliminate a store in the stack pointer.  */
 895   if (dest == stack_pointer_rtx
 896       /* If we couldn't eliminate a field assignment, we can't combine.  */
 897       || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == STRICT_LOW_PART
 898       /* Don't combine with an insn that sets a register to itself if it has
 899          a REG_EQUAL note.  This may be part of a REG_NO_CONFLICT sequence.  */
 900       || (rtx_equal_p (src, dest) && find_reg_note (insn, REG_EQUAL, NULL_RTX))
 901       /* Can't merge a function call.  */
 902       || GET_CODE (src) == CALL
 903       /* Don't eliminate a function call argument.  */
 904       || (GET_CODE (i3) == CALL_INSN
 905           && (find_reg_fusage (i3, USE, dest)
 906               || (GET_CODE (dest) == REG
 907                   && REGNO (dest) < FIRST_PSEUDO_REGISTER
 908                   && global_regs[REGNO (dest)])))
 909       /* Don't substitute into an incremented register.  */
 910       || FIND_REG_INC_NOTE (i3, dest)
 911       || (succ && FIND_REG_INC_NOTE (succ, dest))
 912       /* Don't combine the end of a libcall into anything.  */
 913       || find_reg_note (insn, REG_RETVAL, NULL_RTX)
 914       /* Make sure that DEST is not used after SUCC but before I3.  */
 915       || (succ && ! all_adjacent
 916           && reg_used_between_p (dest, succ, i3))
 917       /* Make sure that the value that is to be substituted for the register
 918          does not use any registers whose values alter in between.  However,
 919          If the insns are adjacent, a use can't cross a set even though we
 920          think it might (this can happen for a sequence of insns each setting
 921          the same destination; reg_last_set of that register might point to
 922          a NOTE).  If INSN has a REG_EQUIV note, the register is always
 923          equivalent to the memory so the substitution is valid even if there
 924          are intervening stores.  Also, don't move a volatile asm or
 925          UNSPEC_VOLATILE across any other insns.  */
 926       || (! all_adjacent
 927           && (((GET_CODE (src) != MEM
 928                 || ! find_reg_note (insn, REG_EQUIV, src))
 929                && use_crosses_set_p (src, INSN_CUID (insn)))
 930               || (GET_CODE (src) == ASM_OPERANDS && MEM_VOLATILE_P (src))
 931               || GET_CODE (src) == UNSPEC_VOLATILE))
 932       /* If there is a REG_NO_CONFLICT note for DEST in I3 or SUCC, we get
 933          better register allocation by not doing the combine.  */
 934       || find_reg_note (i3, REG_NO_CONFLICT, dest)
 935       || (succ && find_reg_note (succ, REG_NO_CONFLICT, dest))
 936       /* Don't combine across a CALL_INSN, because that would possibly
 937          change whether the life span of some REGs crosses calls or not,
 938          and it is a pain to update that information.
 939          Exception: if source is a constant, moving it later can't hurt.
 940          Accept that special case, because it helps -fforce-addr a lot.  */
 941       || (INSN_CUID (insn) < last_call_cuid && ! CONSTANT_P (src)))
 942     return 0;
 943
 944   /* DEST must either be a REG or CC0.  */
 945   if (GET_CODE (dest) == REG)
 946     {
 947       /* If register alignment is being enforced for multi-word items in all
 948          cases except for parameters, it is possible to have a register copy
 949          insn referencing a hard register that is not allowed to contain the
 950          mode being copied and which would not be valid as an operand of most
 951          insns.  Eliminate this problem by not combining with such an insn.
 952
 953          Also, on some machines we don't want to extend the life of a hard
 954          register.
 955
 956          This is the same test done in can_combine except that we don't test
 957          if SRC is a CALL operation to permit a hard register with
 958          SMALL_REGISTER_CLASSES, and that we have to take all_adjacent
 959          into account.  */
 960
 961       if (GET_CODE (src) == REG
 962           && ((REGNO (dest) < FIRST_PSEUDO_REGISTER
 963                && ! HARD_REGNO_MODE_OK (REGNO (dest), GET_MODE (dest)))
 964               /* Don't extend the life of a hard register unless it is
 965                  user variable (if we have few registers) or it can't
 966                  fit into the desired register (meaning something special
 967                  is going on).
 968                  Also avoid substituting a return register into I3, because
 969                  reload can't handle a conflict with constraints of other
 970                  inputs.  */
 971               || (REGNO (src) < FIRST_PSEUDO_REGISTER
 972                   && (! HARD_REGNO_MODE_OK (REGNO (src), GET_MODE (src))
 973 #ifdef SMALL_REGISTER_CLASSES
 974                       || (SMALL_REGISTER_CLASSES
 975                           && ((! all_adjacent && ! REG_USERVAR_P (src))
 976                               || (FUNCTION_VALUE_REGNO_P (REGNO (src))
 977                                   && ! REG_USERVAR_P (src))))
 978 #endif
 979                       ))))
 980         return 0;
 981     }
 982   else if (GET_CODE (dest) != CC0)
 983     return 0;
 984
 985   /* Don't substitute for a register intended as a clobberable operand.
 986      Similarly, don't substitute an expression containing a register that
 987      will be clobbered in I3.  */
 988   if (GET_CODE (PATTERN (i3)) == PARALLEL)
 989     for (i = XVECLEN (PATTERN (i3), 0) - 1; i >= 0; i--)
 990       if (GET_CODE (XVECEXP (PATTERN (i3), 0, i)) == CLOBBER
 991           && (reg_overlap_mentioned_p (XEXP (XVECEXP (PATTERN (i3), 0, i), 0),
 992                                        src)
 993               || rtx_equal_p (XEXP (XVECEXP (PATTERN (i3), 0, i), 0), dest)))
 994         return 0;
 995
 996   /* If INSN contains anything volatile, or is an `asm' (whether volatile
 997      or not), reject, unless nothing volatile comes between it and I3,
 998      with the exception of SUCC.  */
 999
1000   if (GET_CODE (src) == ASM_OPERANDS || volatile_refs_p (src))
1001     for (p = NEXT_INSN (insn); p != i3; p = NEXT_INSN (p))
1002       if (GET_RTX_CLASS (GET_CODE (p)) == 'i'
1003           && p != succ && volatile_refs_p (PATTERN (p)))
1004         return 0;
1005
1006   /* If INSN is an asm, and DEST is a hard register, reject, since it has
1007      to be an explicit register variable, and was chosen for a reason.  */
1008
1009   if (GET_CODE (src) == ASM_OPERANDS
1010       && GET_CODE (dest) == REG && REGNO (dest) < FIRST_PSEUDO_REGISTER)
1011     return 0;
1012
1013   /* If there are any volatile insns between INSN and I3, reject, because
1014      they might affect machine state.  */
1015
1016   for (p = NEXT_INSN (insn); p != i3; p = NEXT_INSN (p))
1017     if (GET_RTX_CLASS (GET_CODE (p)) == 'i'
1018         && p != succ && volatile_insn_p (PATTERN (p)))
1019       return 0;
1020
1021   /* If INSN or I2 contains an autoincrement or autodecrement,
1022      make sure that register is not used between there and I3,
1023      and not already used in I3 either.
1024      Also insist that I3 not be a jump; if it were one
1025      and the incremented register were spilled, we would lose.  */
1026
1027 #ifdef AUTO_INC_DEC
1028   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1029     if (REG_NOTE_KIND (link) == REG_INC
1030         && (GET_CODE (i3) == JUMP_INSN
1031             || reg_used_between_p (XEXP (link, 0), insn, i3)
1032             || reg_overlap_mentioned_p (XEXP (link, 0), PATTERN (i3))))
1033       return 0;
1034 #endif
1035
1036 #ifdef HAVE_cc0
1037   /* Don't combine an insn that follows a CC0-setting insn.
1038      An insn that uses CC0 must not be separated from the one that sets it.
1039      We do, however, allow I2 to follow a CC0-setting insn if that insn
1040      is passed as I1; in that case it will be deleted also.
1041      We also allow combining in this case if all the insns are adjacent
1042      because that would leave the two CC0 insns adjacent as well.
1043      It would be more logical to test whether CC0 occurs inside I1 or I2,
1044      but that would be much slower, and this ought to be equivalent.  */
1045
1046   p = prev_nonnote_insn (insn);
1047   if (p && p != pred && GET_CODE (p) == INSN && sets_cc0_p (PATTERN (p))
1048       && ! all_adjacent)
1049     return 0;
1050 #endif
1051
1052   /* If we get here, we have passed all the tests and the combination is
1053      to be allowed.  */
1054
1055   *pdest = dest;
1056   *psrc = src;
1057
1058   return 1;
1059 }
1060 \f
1061 /* LOC is the location within I3 that contains its pattern or the component
1062    of a PARALLEL of the pattern.  We validate that it is valid for combining.
1063
1064    One problem is if I3 modifies its output, as opposed to replacing it
1065    entirely, we can't allow the output to contain I2DEST or I1DEST as doing
1066    so would produce an insn that is not equivalent to the original insns.
1067
1068    Consider:
1069
1070          (set (reg:DI 101) (reg:DI 100))
1071          (set (subreg:SI (reg:DI 101) 0) <foo>)
1072
1073    This is NOT equivalent to:
1074
1075          (parallel [(set (subreg:SI (reg:DI 100) 0) <foo>)
1076                     (set (reg:DI 101) (reg:DI 100))])
1077
1078    Not only does this modify 100 (in which case it might still be valid
1079    if 100 were dead in I2), it sets 101 to the ORIGINAL value of 100.
1080
1081    We can also run into a problem if I2 sets a register that I1
1082    uses and I1 gets directly substituted into I3 (not via I2).  In that
1083    case, we would be getting the wrong value of I2DEST into I3, so we
1084    must reject the combination.  This case occurs when I2 and I1 both
1085    feed into I3, rather than when I1 feeds into I2, which feeds into I3.
1086    If I1_NOT_IN_SRC is non-zero, it means that finding I1 in the source
1087    of a SET must prevent combination from occurring.
1088
1089    On machines where SMALL_REGISTER_CLASSES is defined, we don't combine
1090    if the destination of a SET is a hard register that isn't a user
1091    variable.
1092
1093    Before doing the above check, we first try to expand a field assignment
1094    into a set of logical operations.
1095
1096    If PI3_DEST_KILLED is non-zero, it is a pointer to a location in which
1097    we place a register that is both set and used within I3.  If more than one
1098    such register is detected, we fail.
1099
1100    Return 1 if the combination is valid, zero otherwise.  */
1101
1102 static int
1103 combinable_i3pat (i3, loc, i2dest, i1dest, i1_not_in_src, pi3dest_killed)
1104      rtx i3;
1105      rtx *loc;
1106      rtx i2dest;
1107      rtx i1dest;
1108      int i1_not_in_src;
1109      rtx *pi3dest_killed;
1110 {
1111   rtx x = *loc;
1112
1113   if (GET_CODE (x) == SET)
1114     {
1115       rtx set = expand_field_assignment (x);
1116       rtx dest = SET_DEST (set);
1117       rtx src = SET_SRC (set);
1118       rtx inner_dest = dest, inner_src = src;
1119
1120       SUBST (*loc, set);
1121
1122       while (GET_CODE (inner_dest) == STRICT_LOW_PART
1123              || GET_CODE (inner_dest) == SUBREG
1124              || GET_CODE (inner_dest) == ZERO_EXTRACT)
1125         inner_dest = XEXP (inner_dest, 0);
1126
1127   /* We probably don't need this any more now that LIMIT_RELOAD_CLASS
1128      was added.  */
1129 #if 0
1130       while (GET_CODE (inner_src) == STRICT_LOW_PART
1131              || GET_CODE (inner_src) == SUBREG
1132              || GET_CODE (inner_src) == ZERO_EXTRACT)
1133         inner_src = XEXP (inner_src, 0);
1134
1135       /* If it is better that two different modes keep two different pseudos,
1136          avoid combining them.  This avoids producing the following pattern
1137          on a 386:
1138           (set (subreg:SI (reg/v:QI 21) 0)
1139                (lshiftrt:SI (reg/v:SI 20)
1140                    (const_int 24)))
1141          If that were made, reload could not handle the pair of
1142          reg 20/21, since it would try to get any GENERAL_REGS
1143          but some of them don't handle QImode.  */
1144
1145       if (rtx_equal_p (inner_src, i2dest)
1146           && GET_CODE (inner_dest) == REG
1147           && ! MODES_TIEABLE_P (GET_MODE (i2dest), GET_MODE (inner_dest)))
1148         return 0;
1149 #endif
1150
1151       /* Check for the case where I3 modifies its output, as
1152          discussed above.  */
1153       if ((inner_dest != dest
1154            && (reg_overlap_mentioned_p (i2dest, inner_dest)
1155                || (i1dest && reg_overlap_mentioned_p (i1dest, inner_dest))))
1156           /* This is the same test done in can_combine_p except that we
1157              allow a hard register with SMALL_REGISTER_CLASSES if SRC is a
1158              CALL operation.
1159              Moreover, we can't test all_adjacent; we don't have to, since
1160              this instruction will stay in place, thus we are not considering
1161              to increase the lifetime of INNER_DEST.  */
1162           || (GET_CODE (inner_dest) == REG
1163               && REGNO (inner_dest) < FIRST_PSEUDO_REGISTER
1164               && (! HARD_REGNO_MODE_OK (REGNO (inner_dest),
1165                                         GET_MODE (inner_dest))
1166 #ifdef SMALL_REGISTER_CLASSES
1167                  || (SMALL_REGISTER_CLASSES
1168                      && GET_CODE (src) != CALL && ! REG_USERVAR_P (inner_dest)
1169                      && FUNCTION_VALUE_REGNO_P (REGNO (inner_dest)))
1170 #endif
1171                   ))
1172           || (i1_not_in_src && reg_overlap_mentioned_p (i1dest, src)))
1173         return 0;
1174
1175       /* If DEST is used in I3, it is being killed in this insn,
1176          so record that for later.
1177          Never add REG_DEAD notes for the FRAME_POINTER_REGNUM or the
1178          STACK_POINTER_REGNUM, since these are always considered to be
1179          live.  Similarly for ARG_POINTER_REGNUM if it is fixed.  */
1180       if (pi3dest_killed && GET_CODE (dest) == REG
1181           && reg_referenced_p (dest, PATTERN (i3))
1182           && REGNO (dest) != FRAME_POINTER_REGNUM
1183 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
1184           && REGNO (dest) != HARD_FRAME_POINTER_REGNUM
1185 #endif
1186 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
1187           && (REGNO (dest) != ARG_POINTER_REGNUM
1188               || ! fixed_regs [REGNO (dest)])
1189 #endif
1190           && REGNO (dest) != STACK_POINTER_REGNUM)
1191         {
1192           if (*pi3dest_killed)
1193             return 0;
1194
1195           *pi3dest_killed = dest;
1196         }
1197     }
1198
1199   else if (GET_CODE (x) == PARALLEL)
1200     {
1201       int i;
1202
1203       for (i = 0; i < XVECLEN (x, 0); i++)
1204         if (! combinable_i3pat (i3, &XVECEXP (x, 0, i), i2dest, i1dest,
1205                                 i1_not_in_src, pi3dest_killed))
1206           return 0;
1207     }
1208
1209   return 1;
1210 }
1211 \f
1212 /* Try to combine the insns I1 and I2 into I3.
1213    Here I1 and I2 appear earlier than I3.
1214    I1 can be zero; then we combine just I2 into I3.
1215
1216    It we are combining three insns and the resulting insn is not recognized,
1217    try splitting it into two insns.  If that happens, I2 and I3 are retained
1218    and I1 is pseudo-deleted by turning it into a NOTE.  Otherwise, I1 and I2
1219    are pseudo-deleted.
1220
1221    Return 0 if the combination does not work.  Then nothing is changed.
1222    If we did the combination, return the insn at which combine should
1223    resume scanning.  */
1224
1225 static rtx
1226 try_combine (i3, i2, i1)
1227      register rtx i3, i2, i1;
1228 {
1229   /* New patterns for I3 and I3, respectively.  */
1230   rtx newpat, newi2pat = 0;
1231   /* Indicates need to preserve SET in I1 or I2 in I3 if it is not dead.  */
1232   int added_sets_1, added_sets_2;
1233   /* Total number of SETs to put into I3.  */
1234   int total_sets;
1235   /* Nonzero is I2's body now appears in I3.  */
1236   int i2_is_used;
1237   /* INSN_CODEs for new I3, new I2, and user of condition code.  */
1238   int insn_code_number, i2_code_number, other_code_number;
1239   /* Contains I3 if the destination of I3 is used in its source, which means
1240      that the old life of I3 is being killed.  If that usage is placed into
1241      I2 and not in I3, a REG_DEAD note must be made.  */
1242   rtx i3dest_killed = 0;
1243   /* SET_DEST and SET_SRC of I2 and I1.  */
1244   rtx i2dest, i2src, i1dest = 0, i1src = 0;
1245   /* PATTERN (I2), or a copy of it in certain cases.  */
1246   rtx i2pat;
1247   /* Indicates if I2DEST or I1DEST is in I2SRC or I1_SRC.  */
1248   int i2dest_in_i2src = 0, i1dest_in_i1src = 0, i2dest_in_i1src = 0;
1249   int i1_feeds_i3 = 0;
1250   /* Notes that must be added to REG_NOTES in I3 and I2.  */
1251   rtx new_i3_notes, new_i2_notes;
1252   /* Notes that we substituted I3 into I2 instead of the normal case.  */
1253   int i3_subst_into_i2 = 0;
1254   /* Notes that I1, I2 or I3 is a MULT operation.  */
1255   int have_mult = 0;
1256   /* Number of clobbers of SCRATCH we had to add.  */
1257   int i3_scratches = 0, i2_scratches = 0, other_scratches = 0;
1258
1259   int maxreg;
1260   rtx temp;
1261   register rtx link;
1262   int i;
1263
1264   /* If any of I1, I2, and I3 isn't really an insn, we can't do anything.
1265      This can occur when flow deletes an insn that it has merged into an
1266      auto-increment address.  We also can't do anything if I3 has a
1267      REG_LIBCALL note since we don't want to disrupt the contiguity of a
1268      libcall.  */
1269
1270   if (GET_RTX_CLASS (GET_CODE (i3)) != 'i'
1271       || GET_RTX_CLASS (GET_CODE (i2)) != 'i'
1272       || (i1 && GET_RTX_CLASS (GET_CODE (i1)) != 'i')
1273       || find_reg_note (i3, REG_LIBCALL, NULL_RTX))
1274     return 0;
1275
1276   combine_attempts++;
1277
1278   undobuf.undos = undobuf.previous_undos = 0;
1279   undobuf.other_insn = 0;
1280
1281   /* Save the current high-water-mark so we can free storage if we didn't
1282      accept this combination.  */
1283   undobuf.storage = (char *) oballoc (0);
1284
1285   /* Reset the hard register usage information.  */
1286   CLEAR_HARD_REG_SET (newpat_used_regs);
1287
1288   /* If I1 and I2 both feed I3, they can be in any order.  To simplify the
1289      code below, set I1 to be the earlier of the two insns.  */
1290   if (i1 && INSN_CUID (i1) > INSN_CUID (i2))
1291     temp = i1, i1 = i2, i2 = temp;
1292
1293   added_links_insn = 0;
1294
1295   /* First check for one important special-case that the code below will
1296      not handle.  Namely, the case where I1 is zero, I2 has multiple sets,
1297      and I3 is a SET whose SET_SRC is a SET_DEST in I2.  In that case,
1298      we may be able to replace that destination with the destination of I3.
1299      This occurs in the common code where we compute both a quotient and
1300      remainder into a structure, in which case we want to do the computation
1301      directly into the structure to avoid register-register copies.
1302
1303      We make very conservative checks below and only try to handle the
1304      most common cases of this.  For example, we only handle the case
1305      where I2 and I3 are adjacent to avoid making difficult register
1306      usage tests.  */
1307
1308   if (i1 == 0 && GET_CODE (i3) == INSN && GET_CODE (PATTERN (i3)) == SET
1309       && GET_CODE (SET_SRC (PATTERN (i3))) == REG
1310       && REGNO (SET_SRC (PATTERN (i3))) >= FIRST_PSEUDO_REGISTER
1311 #ifdef SMALL_REGISTER_CLASSES
1312       && (! SMALL_REGISTER_CLASSES
1313           || GET_CODE (SET_DEST (PATTERN (i3))) != REG
1314           || REGNO (SET_DEST (PATTERN (i3))) >= FIRST_PSEUDO_REGISTER
1315           || REG_USERVAR_P (SET_DEST (PATTERN (i3))))
1316 #endif
1317       && find_reg_note (i3, REG_DEAD, SET_SRC (PATTERN (i3)))
1318       && GET_CODE (PATTERN (i2)) == PARALLEL
1319       && ! side_effects_p (SET_DEST (PATTERN (i3)))
1320       /* If the dest of I3 is a ZERO_EXTRACT or STRICT_LOW_PART, the code
1321          below would need to check what is inside (and reg_overlap_mentioned_p
1322          doesn't support those codes anyway).  Don't allow those destinations;
1323          the resulting insn isn't likely to be recognized anyway.  */
1324       && GET_CODE (SET_DEST (PATTERN (i3))) != ZERO_EXTRACT
1325       && GET_CODE (SET_DEST (PATTERN (i3))) != STRICT_LOW_PART
1326       && ! reg_overlap_mentioned_p (SET_SRC (PATTERN (i3)),
1327                                     SET_DEST (PATTERN (i3)))
1328       && next_real_insn (i2) == i3)
1329     {
1330       rtx p2 = PATTERN (i2);
1331
1332       /* Make sure that the destination of I3,
1333          which we are going to substitute into one output of I2,
1334          is not used within another output of I2.  We must avoid making this:
1335          (parallel [(set (mem (reg 69)) ...)
1336                     (set (reg 69) ...)])
1337          which is not well-defined as to order of actions.
1338          (Besides, reload can't handle output reloads for this.)
1339
1340          The problem can also happen if the dest of I3 is a memory ref,
1341          if another dest in I2 is an indirect memory ref.  */
1342       for (i = 0; i < XVECLEN (p2, 0); i++)
1343         if ((GET_CODE (XVECEXP (p2, 0, i)) == SET
1344              || GET_CODE (XVECEXP (p2, 0, i)) == CLOBBER)
1345             && reg_overlap_mentioned_p (SET_DEST (PATTERN (i3)),
1346                                         SET_DEST (XVECEXP (p2, 0, i))))
1347           break;
1348
1349       if (i == XVECLEN (p2, 0))
1350         for (i = 0; i < XVECLEN (p2, 0); i++)
1351           if (SET_DEST (XVECEXP (p2, 0, i)) == SET_SRC (PATTERN (i3)))
1352             {
1353               combine_merges++;
1354
1355               subst_insn = i3;
1356               subst_low_cuid = INSN_CUID (i2);
1357
1358               added_sets_2 = added_sets_1 = 0;
1359               i2dest = SET_SRC (PATTERN (i3));
1360
1361               /* Replace the dest in I2 with our dest and make the resulting
1362                  insn the new pattern for I3.  Then skip to where we
1363                  validate the pattern.  Everything was set up above.  */
1364               SUBST (SET_DEST (XVECEXP (p2, 0, i)),
1365                      SET_DEST (PATTERN (i3)));
1366
1367               newpat = p2;
1368               i3_subst_into_i2 = 1;
1369               goto validate_replacement;
1370             }
1371     }
1372
1373 #ifndef HAVE_cc0
1374   /* If we have no I1 and I2 looks like:
1375         (parallel [(set (reg:CC X) (compare:CC OP (const_int 0)))
1376                    (set Y OP)])
1377      make up a dummy I1 that is
1378         (set Y OP)
1379      and change I2 to be
1380         (set (reg:CC X) (compare:CC Y (const_int 0)))
1381
1382      (We can ignore any trailing CLOBBERs.)
1383
1384      This undoes a previous combination and allows us to match a branch-and-
1385      decrement insn.  */
1386
1387   if (i1 == 0 && GET_CODE (PATTERN (i2)) == PARALLEL
1388       && XVECLEN (PATTERN (i2), 0) >= 2
1389       && GET_CODE (XVECEXP (PATTERN (i2), 0, 0)) == SET
1390       && (GET_MODE_CLASS (GET_MODE (SET_DEST (XVECEXP (PATTERN (i2), 0, 0))))
1391           == MODE_CC)
1392       && GET_CODE (SET_SRC (XVECEXP (PATTERN (i2), 0, 0))) == COMPARE
1393       && XEXP (SET_SRC (XVECEXP (PATTERN (i2), 0, 0)), 1) == const0_rtx
1394       && GET_CODE (XVECEXP (PATTERN (i2), 0, 1)) == SET
1395       && GET_CODE (SET_DEST (XVECEXP (PATTERN (i2), 0, 1))) == REG
1396       && rtx_equal_p (XEXP (SET_SRC (XVECEXP (PATTERN (i2), 0, 0)), 0),
1397                       SET_SRC (XVECEXP (PATTERN (i2), 0, 1))))
1398     {
1399       for (i =  XVECLEN (PATTERN (i2), 0) - 1; i >= 2; i--)
1400         if (GET_CODE (XVECEXP (PATTERN (i2), 0, i)) != CLOBBER)
1401           break;
1402
1403       if (i == 1)
1404         {
1405           /* We make I1 with the same INSN_UID as I2.  This gives it
1406              the same INSN_CUID for value tracking.  Our fake I1 will
1407              never appear in the insn stream so giving it the same INSN_UID
1408              as I2 will not cause a problem.  */
1409
1410           subst_prev_insn = i1
1411             = gen_rtx (INSN, VOIDmode, INSN_UID (i2), NULL_RTX, i2,
1412                        XVECEXP (PATTERN (i2), 0, 1), -1, NULL_RTX, NULL_RTX);
1413
1414           SUBST (PATTERN (i2), XVECEXP (PATTERN (i2), 0, 0));
1415           SUBST (XEXP (SET_SRC (PATTERN (i2)), 0),
1416                  SET_DEST (PATTERN (i1)));
1417         }
1418     }
1419 #endif
1420
1421   /* Verify that I2 and I1 are valid for combining.  */
1422   if (! can_combine_p (i2, i3, i1, NULL_RTX, &i2dest, &i2src)
1423       || (i1 && ! can_combine_p (i1, i3, NULL_RTX, i2, &i1dest, &i1src)))
1424     {
1425       undo_all ();
1426       return 0;
1427     }
1428
1429   /* Record whether I2DEST is used in I2SRC and similarly for the other
1430      cases.  Knowing this will help in register status updating below.  */
1431   i2dest_in_i2src = reg_overlap_mentioned_p (i2dest, i2src);
1432   i1dest_in_i1src = i1 && reg_overlap_mentioned_p (i1dest, i1src);
1433   i2dest_in_i1src = i1 && reg_overlap_mentioned_p (i2dest, i1src);
1434
1435   /* See if I1 directly feeds into I3.  It does if I1DEST is not used
1436      in I2SRC.  */
1437   i1_feeds_i3 = i1 && ! reg_overlap_mentioned_p (i1dest, i2src);
1438
1439   /* Ensure that I3's pattern can be the destination of combines.  */
1440   if (! combinable_i3pat (i3, &PATTERN (i3), i2dest, i1dest,
1441                           i1 && i2dest_in_i1src && i1_feeds_i3,
1442                           &i3dest_killed))
1443     {
1444       undo_all ();
1445       return 0;
1446     }
1447
1448   /* See if any of the insns is a MULT operation.  Unless one is, we will
1449      reject a combination that is, since it must be slower.  Be conservative
1450      here.  */
1451   if (GET_CODE (i2src) == MULT
1452       || (i1 != 0 && GET_CODE (i1src) == MULT)
1453       || (GET_CODE (PATTERN (i3)) == SET
1454           && GET_CODE (SET_SRC (PATTERN (i3))) == MULT))
1455     have_mult = 1;
1456
1457   /* If I3 has an inc, then give up if I1 or I2 uses the reg that is inc'd.
1458      We used to do this EXCEPT in one case: I3 has a post-inc in an
1459      output operand.  However, that exception can give rise to insns like
1460         mov r3,(r3)+
1461      which is a famous insn on the PDP-11 where the value of r3 used as the
1462      source was model-dependent.  Avoid this sort of thing.  */
1463
1464 #if 0
1465   if (!(GET_CODE (PATTERN (i3)) == SET
1466         && GET_CODE (SET_SRC (PATTERN (i3))) == REG
1467         && GET_CODE (SET_DEST (PATTERN (i3))) == MEM
1468         && (GET_CODE (XEXP (SET_DEST (PATTERN (i3)), 0)) == POST_INC
1469             || GET_CODE (XEXP (SET_DEST (PATTERN (i3)), 0)) == POST_DEC)))
1470     /* It's not the exception.  */
1471 #endif
1472 #ifdef AUTO_INC_DEC
1473     for (link = REG_NOTES (i3); link; link = XEXP (link, 1))
1474       if (REG_NOTE_KIND (link) == REG_INC
1475           && (reg_overlap_mentioned_p (XEXP (link, 0), PATTERN (i2))
1476               || (i1 != 0
1477                   && reg_overlap_mentioned_p (XEXP (link, 0), PATTERN (i1)))))
1478         {
1479           undo_all ();
1480           return 0;
1481         }
1482 #endif
1483
1484   /* See if the SETs in I1 or I2 need to be kept around in the merged
1485      instruction: whenever the value set there is still needed past I3.
1486      For the SETs in I2, this is easy: we see if I2DEST dies or is set in I3.
1487
1488      For the SET in I1, we have two cases:  If I1 and I2 independently
1489      feed into I3, the set in I1 needs to be kept around if I1DEST dies
1490      or is set in I3.  Otherwise (if I1 feeds I2 which feeds I3), the set
1491      in I1 needs to be kept around unless I1DEST dies or is set in either
1492      I2 or I3.  We can distinguish these cases by seeing if I2SRC mentions
1493      I1DEST.  If so, we know I1 feeds into I2.  */
1494
1495   added_sets_2 = ! dead_or_set_p (i3, i2dest);
1496
1497   added_sets_1
1498     = i1 && ! (i1_feeds_i3 ? dead_or_set_p (i3, i1dest)
1499                : (dead_or_set_p (i3, i1dest) || dead_or_set_p (i2, i1dest)));
1500
1501   /* If the set in I2 needs to be kept around, we must make a copy of
1502      PATTERN (I2), so that when we substitute I1SRC for I1DEST in
1503      PATTERN (I2), we are only substituting for the original I1DEST, not into
1504      an already-substituted copy.  This also prevents making self-referential
1505      rtx.  If I2 is a PARALLEL, we just need the piece that assigns I2SRC to
1506      I2DEST.  */
1507
1508   i2pat = (GET_CODE (PATTERN (i2)) == PARALLEL
1509            ? gen_rtx (SET, VOIDmode, i2dest, i2src)
1510            : PATTERN (i2));
1511
1512   if (added_sets_2)
1513     i2pat = copy_rtx (i2pat);
1514
1515   combine_merges++;
1516
1517   /* Substitute in the latest insn for the regs set by the earlier ones.  */
1518
1519   maxreg = max_reg_num ();
1520
1521   subst_insn = i3;
1522
1523   /* It is possible that the source of I2 or I1 may be performing an
1524      unneeded operation, such as a ZERO_EXTEND of something that is known
1525      to have the high part zero.  Handle that case by letting subst look at
1526      the innermost one of them.
1527
1528      Another way to do this would be to have a function that tries to
1529      simplify a single insn instead of merging two or more insns.  We don't
1530      do this because of the potential of infinite loops and because
1531      of the potential extra memory required.  However, doing it the way
1532      we are is a bit of a kludge and doesn't catch all cases.
1533
1534      But only do this if -fexpensive-optimizations since it slows things down
1535      and doesn't usually win.  */
1536
1537   if (flag_expensive_optimizations)
1538     {
1539       /* Pass pc_rtx so no substitutions are done, just simplifications.
1540          The cases that we are interested in here do not involve the few
1541          cases were is_replaced is checked.  */
1542       if (i1)
1543         {
1544           subst_low_cuid = INSN_CUID (i1);
1545           i1src = subst (i1src, pc_rtx, pc_rtx, 0, 0);
1546         }
1547       else
1548         {
1549           subst_low_cuid = INSN_CUID (i2);
1550           i2src = subst (i2src, pc_rtx, pc_rtx, 0, 0);
1551         }
1552
1553       undobuf.previous_undos = undobuf.undos;
1554     }
1555
1556 #ifndef HAVE_cc0
1557   /* Many machines that don't use CC0 have insns that can both perform an
1558      arithmetic operation and set the condition code.  These operations will
1559      be represented as a PARALLEL with the first element of the vector
1560      being a COMPARE of an arithmetic operation with the constant zero.
1561      The second element of the vector will set some pseudo to the result
1562      of the same arithmetic operation.  If we simplify the COMPARE, we won't
1563      match such a pattern and so will generate an extra insn.   Here we test
1564      for this case, where both the comparison and the operation result are
1565      needed, and make the PARALLEL by just replacing I2DEST in I3SRC with
1566      I2SRC.  Later we will make the PARALLEL that contains I2.  */
1567
1568   if (i1 == 0 && added_sets_2 && GET_CODE (PATTERN (i3)) == SET
1569       && GET_CODE (SET_SRC (PATTERN (i3))) == COMPARE
1570       && XEXP (SET_SRC (PATTERN (i3)), 1) == const0_rtx
1571       && rtx_equal_p (XEXP (SET_SRC (PATTERN (i3)), 0), i2dest))
1572     {
1573       rtx *cc_use;
1574       enum machine_mode compare_mode;
1575
1576       newpat = PATTERN (i3);
1577       SUBST (XEXP (SET_SRC (newpat), 0), i2src);
1578
1579       i2_is_used = 1;
1580
1581 #ifdef EXTRA_CC_MODES
1582       /* See if a COMPARE with the operand we substituted in should be done
1583          with the mode that is currently being used.  If not, do the same
1584          processing we do in `subst' for a SET; namely, if the destination
1585          is used only once, try to replace it with a register of the proper
1586          mode and also replace the COMPARE.  */
1587       if (undobuf.other_insn == 0
1588           && (cc_use = find_single_use (SET_DEST (newpat), i3,
1589                                         &undobuf.other_insn))
1590           && ((compare_mode = SELECT_CC_MODE (GET_CODE (*cc_use),
1591                                               i2src, const0_rtx))
1592               != GET_MODE (SET_DEST (newpat))))
1593         {
1594           int regno = REGNO (SET_DEST (newpat));
1595           rtx new_dest = gen_rtx (REG, compare_mode, regno);
1596
1597           if (regno < FIRST_PSEUDO_REGISTER
1598               || (REG_N_SETS (regno) == 1 && ! added_sets_2
1599                   && ! REG_USERVAR_P (SET_DEST (newpat))))
1600             {
1601               if (regno >= FIRST_PSEUDO_REGISTER)
1602                 SUBST (regno_reg_rtx[regno], new_dest);
1603
1604               SUBST (SET_DEST (newpat), new_dest);
1605               SUBST (XEXP (*cc_use, 0), new_dest);
1606               SUBST (SET_SRC (newpat),
1607                      gen_rtx_combine (COMPARE, compare_mode,
1608                                       i2src, const0_rtx));
1609             }
1610           else
1611             undobuf.other_insn = 0;
1612         }
1613 #endif
1614     }
1615   else
1616 #endif
1617     {
1618       n_occurrences = 0;                /* `subst' counts here */
1619
1620       /* If I1 feeds into I2 (not into I3) and I1DEST is in I1SRC, we
1621          need to make a unique copy of I2SRC each time we substitute it
1622          to avoid self-referential rtl.  */
1623
1624       subst_low_cuid = INSN_CUID (i2);
1625       newpat = subst (PATTERN (i3), i2dest, i2src, 0,
1626                       ! i1_feeds_i3 && i1dest_in_i1src);
1627       undobuf.previous_undos = undobuf.undos;
1628
1629       /* Record whether i2's body now appears within i3's body.  */
1630       i2_is_used = n_occurrences;
1631     }
1632
1633   /* If we already got a failure, don't try to do more.  Otherwise,
1634      try to substitute in I1 if we have it.  */
1635
1636   if (i1 && GET_CODE (newpat) != CLOBBER)
1637     {
1638       /* Before we can do this substitution, we must redo the test done
1639          above (see detailed comments there) that ensures  that I1DEST
1640          isn't mentioned in any SETs in NEWPAT that are field assignments.  */
1641
1642       if (! combinable_i3pat (NULL_RTX, &newpat, i1dest, NULL_RTX,
1643                               0, NULL_PTR))
1644         {
1645           undo_all ();
1646           return 0;
1647         }
1648
1649       n_occurrences = 0;
1650       subst_low_cuid = INSN_CUID (i1);
1651       newpat = subst (newpat, i1dest, i1src, 0, 0);
1652       undobuf.previous_undos = undobuf.undos;
1653     }
1654
1655   /* Fail if an autoincrement side-effect has been duplicated.  Be careful
1656      to count all the ways that I2SRC and I1SRC can be used.  */
1657   if ((FIND_REG_INC_NOTE (i2, NULL_RTX) != 0
1658        && i2_is_used + added_sets_2 > 1)
1659       || (i1 != 0 && FIND_REG_INC_NOTE (i1, NULL_RTX) != 0
1660           && (n_occurrences + added_sets_1 + (added_sets_2 && ! i1_feeds_i3)
1661               > 1))
1662       /* Fail if we tried to make a new register (we used to abort, but there's
1663          really no reason to).  */
1664       || max_reg_num () != maxreg
1665       /* Fail if we couldn't do something and have a CLOBBER.  */
1666       || GET_CODE (newpat) == CLOBBER
1667       /* Fail if this new pattern is a MULT and we didn't have one before
1668          at the outer level.  */
1669       || (GET_CODE (newpat) == SET && GET_CODE (SET_SRC (newpat)) == MULT
1670           && ! have_mult))
1671     {
1672       undo_all ();
1673       return 0;
1674     }
1675
1676   /* If the actions of the earlier insns must be kept
1677      in addition to substituting them into the latest one,
1678      we must make a new PARALLEL for the latest insn
1679      to hold additional the SETs.  */
1680
1681   if (added_sets_1 || added_sets_2)
1682     {
1683       combine_extras++;
1684
1685       if (GET_CODE (newpat) == PARALLEL)
1686         {
1687           rtvec old = XVEC (newpat, 0);
1688           total_sets = XVECLEN (newpat, 0) + added_sets_1 + added_sets_2;
1689           newpat = gen_rtx (PARALLEL, VOIDmode, rtvec_alloc (total_sets));
1690           bcopy ((char *) &old->elem[0], (char *) XVEC (newpat, 0)->elem,
1691                  sizeof (old->elem[0]) * old->num_elem);
1692         }
1693       else
1694         {
1695           rtx old = newpat;
1696           total_sets = 1 + added_sets_1 + added_sets_2;
1697           newpat = gen_rtx (PARALLEL, VOIDmode, rtvec_alloc (total_sets));
1698           XVECEXP (newpat, 0, 0) = old;
1699         }
1700
1701      if (added_sets_1)
1702        XVECEXP (newpat, 0, --total_sets)
1703          = (GET_CODE (PATTERN (i1)) == PARALLEL
1704             ? gen_rtx (SET, VOIDmode, i1dest, i1src) : PATTERN (i1));
1705
1706      if (added_sets_2)
1707         {
1708           /* If there is no I1, use I2's body as is.  We used to also not do
1709              the subst call below if I2 was substituted into I3,
1710              but that could lose a simplification.  */
1711           if (i1 == 0)
1712             XVECEXP (newpat, 0, --total_sets) = i2pat;
1713           else
1714             /* See comment where i2pat is assigned.  */
1715             XVECEXP (newpat, 0, --total_sets)
1716               = subst (i2pat, i1dest, i1src, 0, 0);
1717         }
1718     }
1719
1720   /* We come here when we are replacing a destination in I2 with the
1721      destination of I3.  */
1722  validate_replacement:
1723
1724   /* Note which hard regs this insn has as inputs.  */
1725   mark_used_regs_combine (newpat);
1726
1727   /* Is the result of combination a valid instruction?  */
1728   insn_code_number
1729     = recog_for_combine (&newpat, i3, &new_i3_notes, &i3_scratches);
1730
1731   /* If the result isn't valid, see if it is a PARALLEL of two SETs where
1732      the second SET's destination is a register that is unused.  In that case,
1733      we just need the first SET.   This can occur when simplifying a divmod
1734      insn.  We *must* test for this case here because the code below that
1735      splits two independent SETs doesn't handle this case correctly when it
1736      updates the register status.  Also check the case where the first
1737      SET's destination is unused.  That would not cause incorrect code, but
1738      does cause an unneeded insn to remain.  */
1739
1740   if (insn_code_number < 0 && GET_CODE (newpat) == PARALLEL
1741       && XVECLEN (newpat, 0) == 2
1742       && GET_CODE (XVECEXP (newpat, 0, 0)) == SET
1743       && GET_CODE (XVECEXP (newpat, 0, 1)) == SET
1744       && GET_CODE (SET_DEST (XVECEXP (newpat, 0, 1))) == REG
1745       && find_reg_note (i3, REG_UNUSED, SET_DEST (XVECEXP (newpat, 0, 1)))
1746       && ! side_effects_p (SET_SRC (XVECEXP (newpat, 0, 1)))
1747       && asm_noperands (newpat) < 0)
1748     {
1749       newpat = XVECEXP (newpat, 0, 0);
1750       insn_code_number
1751         = recog_for_combine (&newpat, i3, &new_i3_notes, &i3_scratches);
1752     }
1753
1754   else if (insn_code_number < 0 && GET_CODE (newpat) == PARALLEL
1755            && XVECLEN (newpat, 0) == 2
1756            && GET_CODE (XVECEXP (newpat, 0, 0)) == SET
1757            && GET_CODE (XVECEXP (newpat, 0, 1)) == SET
1758            && GET_CODE (SET_DEST (XVECEXP (newpat, 0, 0))) == REG
1759            && find_reg_note (i3, REG_UNUSED, SET_DEST (XVECEXP (newpat, 0, 0)))
1760            && ! side_effects_p (SET_SRC (XVECEXP (newpat, 0, 0)))
1761            && asm_noperands (newpat) < 0)
1762     {
1763       newpat = XVECEXP (newpat, 0, 1);
1764       insn_code_number
1765         = recog_for_combine (&newpat, i3, &new_i3_notes, &i3_scratches);
1766     }
1767
1768   /* If we were combining three insns and the result is a simple SET
1769      with no ASM_OPERANDS that wasn't recognized, try to split it into two
1770      insns.  There are two ways to do this.  It can be split using a
1771      machine-specific method (like when you have an addition of a large
1772      constant) or by combine in the function find_split_point.  */
1773
1774   if (i1 && insn_code_number < 0 && GET_CODE (newpat) == SET
1775       && asm_noperands (newpat) < 0)
1776     {
1777       rtx m_split, *split;
1778       rtx ni2dest = i2dest;
1779
1780       /* See if the MD file can split NEWPAT.  If it can't, see if letting it
1781          use I2DEST as a scratch register will help.  In the latter case,
1782          convert I2DEST to the mode of the source of NEWPAT if we can.  */
1783
1784       m_split = split_insns (newpat, i3);
1785
1786       /* We can only use I2DEST as a scratch reg if it doesn't overlap any
1787          inputs of NEWPAT.  */
1788
1789       /* ??? If I2DEST is not safe, and I1DEST exists, then it would be
1790          possible to try that as a scratch reg.  This would require adding
1791          more code to make it work though.  */
1792
1793       if (m_split == 0 && ! reg_overlap_mentioned_p (ni2dest, newpat))
1794         {
1795           /* If I2DEST is a hard register or the only use of a pseudo,
1796              we can change its mode.  */
1797           if (GET_MODE (SET_DEST (newpat)) != GET_MODE (i2dest)
1798               && GET_MODE (SET_DEST (newpat)) != VOIDmode
1799               && GET_CODE (i2dest) == REG
1800               && (REGNO (i2dest) < FIRST_PSEUDO_REGISTER
1801                   || (REG_N_SETS (REGNO (i2dest)) == 1 && ! added_sets_2
1802                       && ! REG_USERVAR_P (i2dest))))
1803             ni2dest = gen_rtx (REG, GET_MODE (SET_DEST (newpat)),
1804                                REGNO (i2dest));
1805
1806           m_split = split_insns (gen_rtx (PARALLEL, VOIDmode,
1807                                           gen_rtvec (2, newpat,
1808                                                      gen_rtx (CLOBBER,
1809                                                               VOIDmode,
1810                                                               ni2dest))),
1811                                  i3);
1812         }
1813
1814       if (m_split && GET_CODE (m_split) == SEQUENCE
1815           && XVECLEN (m_split, 0) == 2
1816           && (next_real_insn (i2) == i3
1817               || ! use_crosses_set_p (PATTERN (XVECEXP (m_split, 0, 0)),
1818                                       INSN_CUID (i2))))
1819         {
1820           rtx i2set, i3set;
1821           rtx newi3pat = PATTERN (XVECEXP (m_split, 0, 1));
1822           newi2pat = PATTERN (XVECEXP (m_split, 0, 0));
1823
1824           i3set = single_set (XVECEXP (m_split, 0, 1));
1825           i2set = single_set (XVECEXP (m_split, 0, 0));
1826
1827           /* In case we changed the mode of I2DEST, replace it in the
1828              pseudo-register table here.  We can't do it above in case this
1829              code doesn't get executed and we do a split the other way.  */
1830
1831           if (REGNO (i2dest) >= FIRST_PSEUDO_REGISTER)
1832             SUBST (regno_reg_rtx[REGNO (i2dest)], ni2dest);
1833
1834           i2_code_number = recog_for_combine (&newi2pat, i2, &new_i2_notes,
1835                                               &i2_scratches);
1836
1837           /* If I2 or I3 has multiple SETs, we won't know how to track
1838              register status, so don't use these insns.  If I2's destination
1839              is used between I2 and I3, we also can't use these insns.  */
1840
1841           if (i2_code_number >= 0 && i2set && i3set
1842               && (next_real_insn (i2) == i3
1843                   || ! reg_used_between_p (SET_DEST (i2set), i2, i3)))
1844             insn_code_number = recog_for_combine (&newi3pat, i3, &new_i3_notes,
1845                                                   &i3_scratches);
1846           if (insn_code_number >= 0)
1847             newpat = newi3pat;
1848
1849           /* It is possible that both insns now set the destination of I3.
1850              If so, we must show an extra use of it.  */
1851
1852           if (insn_code_number >= 0)
1853             {
1854               rtx new_i3_dest = SET_DEST (i3set);
1855               rtx new_i2_dest = SET_DEST (i2set);
1856
1857               while (GET_CODE (new_i3_dest) == ZERO_EXTRACT
1858                      || GET_CODE (new_i3_dest) == STRICT_LOW_PART
1859                      || GET_CODE (new_i3_dest) == SUBREG)
1860                 new_i3_dest = XEXP (new_i3_dest, 0);
1861
1862               while (GET_CODE (new_i2_dest) == ZERO_EXTRACT
1863                      || GET_CODE (new_i2_dest) == STRICT_LOW_PART
1864                      || GET_CODE (new_i2_dest) == SUBREG)
1865                 new_i2_dest = XEXP (new_i2_dest, 0);
1866
1867               if (GET_CODE (new_i3_dest) == REG
1868                   && GET_CODE (new_i2_dest) == REG
1869                   && REGNO (new_i3_dest) == REGNO (new_i2_dest))
1870                 REG_N_SETS (REGNO (new_i2_dest))++;
1871             }
1872         }
1873
1874       /* If we can split it and use I2DEST, go ahead and see if that
1875          helps things be recognized.  Verify that none of the registers
1876          are set between I2 and I3.  */
1877       if (insn_code_number < 0 && (split = find_split_point (&newpat, i3)) != 0
1878 #ifdef HAVE_cc0
1879           && GET_CODE (i2dest) == REG
1880 #endif
1881           /* We need I2DEST in the proper mode.  If it is a hard register
1882              or the only use of a pseudo, we can change its mode.  */
1883           && (GET_MODE (*split) == GET_MODE (i2dest)
1884               || GET_MODE (*split) == VOIDmode
1885               || REGNO (i2dest) < FIRST_PSEUDO_REGISTER
1886               || (REG_N_SETS (REGNO (i2dest)) == 1 && ! added_sets_2
1887                   && ! REG_USERVAR_P (i2dest)))
1888           && (next_real_insn (i2) == i3
1889               || ! use_crosses_set_p (*split, INSN_CUID (i2)))
1890           /* We can't overwrite I2DEST if its value is still used by
1891              NEWPAT.  */
1892           && ! reg_referenced_p (i2dest, newpat))
1893         {
1894           rtx newdest = i2dest;
1895           enum rtx_code split_code = GET_CODE (*split);
1896           enum machine_mode split_mode = GET_MODE (*split);
1897
1898           /* Get NEWDEST as a register in the proper mode.  We have already
1899              validated that we can do this.  */
1900           if (GET_MODE (i2dest) != split_mode && split_mode != VOIDmode)
1901             {
1902               newdest = gen_rtx (REG, split_mode, REGNO (i2dest));
1903
1904               if (REGNO (i2dest) >= FIRST_PSEUDO_REGISTER)
1905                 SUBST (regno_reg_rtx[REGNO (i2dest)], newdest);
1906             }
1907
1908           /* If *SPLIT is a (mult FOO (const_int pow2)), convert it to
1909              an ASHIFT.  This can occur if it was inside a PLUS and hence
1910              appeared to be a memory address.  This is a kludge.  */
1911           if (split_code == MULT
1912               && GET_CODE (XEXP (*split, 1)) == CONST_INT
1913               && (i = exact_log2 (INTVAL (XEXP (*split, 1)))) >= 0)
1914             {
1915               SUBST (*split, gen_rtx_combine (ASHIFT, split_mode,
1916                                               XEXP (*split, 0), GEN_INT (i)));
1917               /* Update split_code because we may not have a multiply
1918                  anymore.  */
1919               split_code = GET_CODE (*split);
1920             }
1921
1922 #ifdef INSN_SCHEDULING
1923           /* If *SPLIT is a paradoxical SUBREG, when we split it, it should
1924              be written as a ZERO_EXTEND.  */
1925           if (split_code == SUBREG && GET_CODE (SUBREG_REG (*split)) == MEM)
1926             SUBST (*split, gen_rtx_combine (ZERO_EXTEND, split_mode,
1927                                             XEXP (*split, 0)));
1928 #endif
1929
1930           newi2pat = gen_rtx_combine (SET, VOIDmode, newdest, *split);
1931           SUBST (*split, newdest);
1932           i2_code_number
1933             = recog_for_combine (&newi2pat, i2, &new_i2_notes, &i2_scratches);
1934
1935           /* If the split point was a MULT and we didn't have one before,
1936              don't use one now.  */
1937           if (i2_code_number >= 0 && ! (split_code == MULT && ! have_mult))
1938             insn_code_number
1939               = recog_for_combine (&newpat, i3, &new_i3_notes, &i3_scratches);
1940         }
1941     }
1942
1943   /* Check for a case where we loaded from memory in a narrow mode and
1944      then sign extended it, but we need both registers.  In that case,
1945      we have a PARALLEL with both loads from the same memory location.
1946      We can split this into a load from memory followed by a register-register
1947      copy.  This saves at least one insn, more if register allocation can
1948      eliminate the copy.
1949
1950      We cannot do this if the destination of the second assignment is
1951      a register that we have already assumed is zero-extended.  Similarly
1952      for a SUBREG of such a register.  */
1953
1954   else if (i1 && insn_code_number < 0 && asm_noperands (newpat) < 0
1955            && GET_CODE (newpat) == PARALLEL
1956            && XVECLEN (newpat, 0) == 2
1957            && GET_CODE (XVECEXP (newpat, 0, 0)) == SET
1958            && GET_CODE (SET_SRC (XVECEXP (newpat, 0, 0))) == SIGN_EXTEND
1959            && GET_CODE (XVECEXP (newpat, 0, 1)) == SET
1960            && rtx_equal_p (SET_SRC (XVECEXP (newpat, 0, 1)),
1961                            XEXP (SET_SRC (XVECEXP (newpat, 0, 0)), 0))
1962            && ! use_crosses_set_p (SET_SRC (XVECEXP (newpat, 0, 1)),
1963                                    INSN_CUID (i2))
1964            && GET_CODE (SET_DEST (XVECEXP (newpat, 0, 1))) != ZERO_EXTRACT
1965            && GET_CODE (SET_DEST (XVECEXP (newpat, 0, 1))) != STRICT_LOW_PART
1966            && ! (temp = SET_DEST (XVECEXP (newpat, 0, 1)),
1967                  (GET_CODE (temp) == REG
1968                   && reg_nonzero_bits[REGNO (temp)] != 0
1969                   && GET_MODE_BITSIZE (GET_MODE (temp)) < BITS_PER_WORD
1970                   && GET_MODE_BITSIZE (GET_MODE (temp)) < HOST_BITS_PER_INT
1971                   && (reg_nonzero_bits[REGNO (temp)]
1972                       != GET_MODE_MASK (word_mode))))
1973            && ! (GET_CODE (SET_DEST (XVECEXP (newpat, 0, 1))) == SUBREG
1974                  && (temp = SUBREG_REG (SET_DEST (XVECEXP (newpat, 0, 1))),
1975                      (GET_CODE (temp) == REG
1976                       && reg_nonzero_bits[REGNO (temp)] != 0
1977                       && GET_MODE_BITSIZE (GET_MODE (temp)) < BITS_PER_WORD
1978                       && GET_MODE_BITSIZE (GET_MODE (temp)) < HOST_BITS_PER_INT
1979                       && (reg_nonzero_bits[REGNO (temp)]
1980                           != GET_MODE_MASK (word_mode)))))
1981            && ! reg_overlap_mentioned_p (SET_DEST (XVECEXP (newpat, 0, 1)),
1982                                          SET_SRC (XVECEXP (newpat, 0, 1)))
1983            && ! find_reg_note (i3, REG_UNUSED,
1984                                SET_DEST (XVECEXP (newpat, 0, 0))))
1985     {
1986       rtx ni2dest;
1987
1988       newi2pat = XVECEXP (newpat, 0, 0);
1989       ni2dest = SET_DEST (XVECEXP (newpat, 0, 0));
1990       newpat = XVECEXP (newpat, 0, 1);
1991       SUBST (SET_SRC (newpat),
1992              gen_lowpart_for_combine (GET_MODE (SET_SRC (newpat)), ni2dest));
1993       i2_code_number
1994         = recog_for_combine (&newi2pat, i2, &new_i2_notes, &i2_scratches);
1995
1996       if (i2_code_number >= 0)
1997         insn_code_number
1998           = recog_for_combine (&newpat, i3, &new_i3_notes, &i3_scratches);
1999
2000       if (insn_code_number >= 0)
2001         {
2002           rtx insn;
2003           rtx link;
2004
2005           /* If we will be able to accept this, we have made a change to the
2006              destination of I3.  This can invalidate a LOG_LINKS pointing
2007              to I3.  No other part of combine.c makes such a transformation.
2008
2009              The new I3 will have a destination that was previously the
2010              destination of I1 or I2 and which was used in i2 or I3.  Call
2011              distribute_links to make a LOG_LINK from the next use of
2012              that destination.  */
2013
2014           PATTERN (i3) = newpat;
2015           distribute_links (gen_rtx (INSN_LIST, VOIDmode, i3, NULL_RTX));
2016
2017           /* I3 now uses what used to be its destination and which is
2018              now I2's destination.  That means we need a LOG_LINK from
2019              I3 to I2.  But we used to have one, so we still will.
2020
2021              However, some later insn might be using I2's dest and have
2022              a LOG_LINK pointing at I3.  We must remove this link.
2023              The simplest way to remove the link is to point it at I1,
2024              which we know will be a NOTE.  */
2025
2026           for (insn = NEXT_INSN (i3);
2027                insn && (this_basic_block == n_basic_blocks - 1
2028                         || insn != basic_block_head[this_basic_block + 1]);
2029                insn = NEXT_INSN (insn))
2030             {
2031               if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
2032                   && reg_referenced_p (ni2dest, PATTERN (insn)))
2033                 {
2034                   for (link = LOG_LINKS (insn); link;
2035                        link = XEXP (link, 1))
2036                     if (XEXP (link, 0) == i3)
2037                       XEXP (link, 0) = i1;
2038
2039                   break;
2040                 }
2041             }
2042         }
2043     }
2044
2045   /* Similarly, check for a case where we have a PARALLEL of two independent
2046      SETs but we started with three insns.  In this case, we can do the sets
2047      as two separate insns.  This case occurs when some SET allows two
2048      other insns to combine, but the destination of that SET is still live.  */
2049
2050   else if (i1 && insn_code_number < 0 && asm_noperands (newpat) < 0
2051            && GET_CODE (newpat) == PARALLEL
2052            && XVECLEN (newpat, 0) == 2
2053            && GET_CODE (XVECEXP (newpat, 0, 0)) == SET
2054            && GET_CODE (SET_DEST (XVECEXP (newpat, 0, 0))) != ZERO_EXTRACT
2055            && GET_CODE (SET_DEST (XVECEXP (newpat, 0, 0))) != STRICT_LOW_PART
2056            && GET_CODE (XVECEXP (newpat, 0, 1)) == SET
2057            && GET_CODE (SET_DEST (XVECEXP (newpat, 0, 1))) != ZERO_EXTRACT
2058            && GET_CODE (SET_DEST (XVECEXP (newpat, 0, 1))) != STRICT_LOW_PART
2059            && ! use_crosses_set_p (SET_SRC (XVECEXP (newpat, 0, 1)),
2060                                    INSN_CUID (i2))
2061            /* Don't pass sets with (USE (MEM ...)) dests to the following.  */
2062            && GET_CODE (SET_DEST (XVECEXP (newpat, 0, 1))) != USE
2063            && GET_CODE (SET_DEST (XVECEXP (newpat, 0, 0))) != USE
2064            && ! reg_referenced_p (SET_DEST (XVECEXP (newpat, 0, 1)),
2065                                   XVECEXP (newpat, 0, 0))
2066            && ! reg_referenced_p (SET_DEST (XVECEXP (newpat, 0, 0)),
2067                                   XVECEXP (newpat, 0, 1)))
2068     {
2069       newi2pat = XVECEXP (newpat, 0, 1);
2070       newpat = XVECEXP (newpat, 0, 0);
2071
2072       i2_code_number
2073         = recog_for_combine (&newi2pat, i2, &new_i2_notes, &i2_scratches);
2074
2075       if (i2_code_number >= 0)
2076         insn_code_number
2077           = recog_for_combine (&newpat, i3, &new_i3_notes, &i3_scratches);
2078     }
2079
2080   /* If it still isn't recognized, fail and change things back the way they
2081      were.  */
2082   if ((insn_code_number < 0
2083        /* Is the result a reasonable ASM_OPERANDS?  */
2084        && (! check_asm_operands (newpat) || added_sets_1 || added_sets_2)))
2085     {
2086       undo_all ();
2087       return 0;
2088     }
2089
2090   /* If we had to change another insn, make sure it is valid also.  */
2091   if (undobuf.other_insn)
2092     {
2093       rtx other_pat = PATTERN (undobuf.other_insn);
2094       rtx new_other_notes;
2095       rtx note, next;
2096
2097       CLEAR_HARD_REG_SET (newpat_used_regs);
2098
2099       other_code_number
2100         = recog_for_combine (&other_pat, undobuf.other_insn,
2101                              &new_other_notes, &other_scratches);
2102
2103       if (other_code_number < 0 && ! check_asm_operands (other_pat))
2104         {
2105           undo_all ();
2106           return 0;
2107         }
2108
2109       PATTERN (undobuf.other_insn) = other_pat;
2110
2111       /* If any of the notes in OTHER_INSN were REG_UNUSED, ensure that they
2112          are still valid.  Then add any non-duplicate notes added by
2113          recog_for_combine.  */
2114       for (note = REG_NOTES (undobuf.other_insn); note; note = next)
2115         {
2116           next = XEXP (note, 1);
2117
2118           if (REG_NOTE_KIND (note) == REG_UNUSED
2119               && ! reg_set_p (XEXP (note, 0), PATTERN (undobuf.other_insn)))
2120             {
2121               if (GET_CODE (XEXP (note, 0)) == REG)
2122                 REG_N_DEATHS (REGNO (XEXP (note, 0)))--;
2123
2124               remove_note (undobuf.other_insn, note);
2125             }
2126         }
2127
2128       for (note = new_other_notes; note; note = XEXP (note, 1))
2129         if (GET_CODE (XEXP (note, 0)) == REG)
2130           REG_N_DEATHS (REGNO (XEXP (note, 0)))++;
2131
2132       distribute_notes (new_other_notes, undobuf.other_insn,
2133                         undobuf.other_insn, NULL_RTX, NULL_RTX, NULL_RTX);
2134     }
2135
2136   /* We now know that we can do this combination.  Merge the insns and
2137      update the status of registers and LOG_LINKS.  */
2138
2139   {
2140     rtx i3notes, i2notes, i1notes = 0;
2141     rtx i3links, i2links, i1links = 0;
2142     rtx midnotes = 0;
2143     register int regno;
2144     /* Compute which registers we expect to eliminate.  */
2145     rtx elim_i2 = (newi2pat || i2dest_in_i2src || i2dest_in_i1src
2146                    ? 0 : i2dest);
2147     rtx elim_i1 = i1 == 0 || i1dest_in_i1src ? 0 : i1dest;
2148
2149     /* Get the old REG_NOTES and LOG_LINKS from all our insns and
2150        clear them.  */
2151     i3notes = REG_NOTES (i3), i3links = LOG_LINKS (i3);
2152     i2notes = REG_NOTES (i2), i2links = LOG_LINKS (i2);
2153     if (i1)
2154       i1notes = REG_NOTES (i1), i1links = LOG_LINKS (i1);
2155
2156     /* Ensure that we do not have something that should not be shared but
2157        occurs multiple times in the new insns.  Check this by first
2158        resetting all the `used' flags and then copying anything is shared.  */
2159
2160     reset_used_flags (i3notes);
2161     reset_used_flags (i2notes);
2162     reset_used_flags (i1notes);
2163     reset_used_flags (newpat);
2164     reset_used_flags (newi2pat);
2165     if (undobuf.other_insn)
2166       reset_used_flags (PATTERN (undobuf.other_insn));
2167
2168     i3notes = copy_rtx_if_shared (i3notes);
2169     i2notes = copy_rtx_if_shared (i2notes);
2170     i1notes = copy_rtx_if_shared (i1notes);
2171     newpat = copy_rtx_if_shared (newpat);
2172     newi2pat = copy_rtx_if_shared (newi2pat);
2173     if (undobuf.other_insn)
2174       reset_used_flags (PATTERN (undobuf.other_insn));
2175
2176     INSN_CODE (i3) = insn_code_number;
2177     PATTERN (i3) = newpat;
2178     if (undobuf.other_insn)
2179       INSN_CODE (undobuf.other_insn) = other_code_number;
2180
2181     /* We had one special case above where I2 had more than one set and
2182        we replaced a destination of one of those sets with the destination
2183        of I3.  In that case, we have to update LOG_LINKS of insns later
2184        in this basic block.  Note that this (expensive) case is rare.
2185
2186        Also, in this case, we must pretend that all REG_NOTEs for I2
2187        actually came from I3, so that REG_UNUSED notes from I2 will be
2188        properly handled.  */
2189
2190     if (i3_subst_into_i2)
2191       {
2192         for (i = 0; i < XVECLEN (PATTERN (i2), 0); i++)
2193           if (GET_CODE (SET_DEST (XVECEXP (PATTERN (i2), 0, i))) == REG
2194               && SET_DEST (XVECEXP (PATTERN (i2), 0, i)) != i2dest
2195               && ! find_reg_note (i2, REG_UNUSED,
2196                                   SET_DEST (XVECEXP (PATTERN (i2), 0, i))))
2197             for (temp = NEXT_INSN (i2);
2198                  temp && (this_basic_block == n_basic_blocks - 1
2199                           || basic_block_head[this_basic_block] != temp);
2200                  temp = NEXT_INSN (temp))
2201               if (temp != i3 && GET_RTX_CLASS (GET_CODE (temp)) == 'i')
2202                 for (link = LOG_LINKS (temp); link; link = XEXP (link, 1))
2203                   if (XEXP (link, 0) == i2)
2204                     XEXP (link, 0) = i3;
2205
2206         if (i3notes)
2207           {
2208             rtx link = i3notes;
2209             while (XEXP (link, 1))
2210               link = XEXP (link, 1);
2211             XEXP (link, 1) = i2notes;
2212           }
2213         else
2214           i3notes = i2notes;
2215         i2notes = 0;
2216       }
2217
2218     LOG_LINKS (i3) = 0;
2219     REG_NOTES (i3) = 0;
2220     LOG_LINKS (i2) = 0;
2221     REG_NOTES (i2) = 0;
2222
2223     if (newi2pat)
2224       {
2225         INSN_CODE (i2) = i2_code_number;
2226         PATTERN (i2) = newi2pat;
2227       }
2228     else
2229       {
2230         PUT_CODE (i2, NOTE);
2231         NOTE_LINE_NUMBER (i2) = NOTE_INSN_DELETED;
2232         NOTE_SOURCE_FILE (i2) = 0;
2233       }
2234
2235     if (i1)
2236       {
2237         LOG_LINKS (i1) = 0;
2238         REG_NOTES (i1) = 0;
2239         PUT_CODE (i1, NOTE);
2240         NOTE_LINE_NUMBER (i1) = NOTE_INSN_DELETED;
2241         NOTE_SOURCE_FILE (i1) = 0;
2242       }
2243
2244     /* Get death notes for everything that is now used in either I3 or
2245        I2 and used to die in a previous insn.  If we built two new
2246        patterns, move from I1 to I2 then I2 to I3 so that we get the
2247        proper movement on registers that I2 modifies.  */
2248
2249     if (newi2pat)
2250       {
2251         move_deaths (newi2pat, NULL_RTX, INSN_CUID (i1), i2, &midnotes);
2252         move_deaths (newpat, newi2pat, INSN_CUID (i1), i3, &midnotes);
2253       }
2254     else
2255       move_deaths (newpat, NULL_RTX, i1 ? INSN_CUID (i1) : INSN_CUID (i2),
2256                    i3, &midnotes);
2257
2258     /* Distribute all the LOG_LINKS and REG_NOTES from I1, I2, and I3.  */
2259     if (i3notes)
2260       distribute_notes (i3notes, i3, i3, newi2pat ? i2 : NULL_RTX,
2261                         elim_i2, elim_i1);
2262     if (i2notes)
2263       distribute_notes (i2notes, i2, i3, newi2pat ? i2 : NULL_RTX,
2264                         elim_i2, elim_i1);
2265     if (i1notes)
2266       distribute_notes (i1notes, i1, i3, newi2pat ? i2 : NULL_RTX,
2267                         elim_i2, elim_i1);
2268     if (midnotes)
2269       distribute_notes (midnotes, NULL_RTX, i3, newi2pat ? i2 : NULL_RTX,
2270                         elim_i2, elim_i1);
2271
2272     /* Distribute any notes added to I2 or I3 by recog_for_combine.  We
2273        know these are REG_UNUSED and want them to go to the desired insn,
2274        so we always pass it as i3.  We have not counted the notes in
2275        reg_n_deaths yet, so we need to do so now.  */
2276
2277     if (newi2pat && new_i2_notes)
2278       {
2279         for (temp = new_i2_notes; temp; temp = XEXP (temp, 1))
2280           if (GET_CODE (XEXP (temp, 0)) == REG)
2281             REG_N_DEATHS (REGNO (XEXP (temp, 0)))++;
2282
2283         distribute_notes (new_i2_notes, i2, i2, NULL_RTX, NULL_RTX, NULL_RTX);
2284       }
2285
2286     if (new_i3_notes)
2287       {
2288         for (temp = new_i3_notes; temp; temp = XEXP (temp, 1))
2289           if (GET_CODE (XEXP (temp, 0)) == REG)
2290             REG_N_DEATHS (REGNO (XEXP (temp, 0)))++;
2291
2292         distribute_notes (new_i3_notes, i3, i3, NULL_RTX, NULL_RTX, NULL_RTX);
2293       }
2294
2295     /* If I3DEST was used in I3SRC, it really died in I3.  We may need to
2296        put a REG_DEAD note for it somewhere.  Similarly for I2 and I1.
2297        Show an additional death due to the REG_DEAD note we make here.  If
2298        we discard it in distribute_notes, we will decrement it again.  */
2299
2300     if (i3dest_killed)
2301       {
2302         if (GET_CODE (i3dest_killed) == REG)
2303           REG_N_DEATHS (REGNO (i3dest_killed))++;
2304
2305         distribute_notes (gen_rtx (EXPR_LIST, REG_DEAD, i3dest_killed,
2306                                    NULL_RTX),
2307                           NULL_RTX, i3, newi2pat ? i2 : NULL_RTX,
2308                           NULL_RTX, NULL_RTX);
2309       }
2310
2311     /* For I2 and I1, we have to be careful.  If NEWI2PAT exists and sets
2312        I2DEST or I1DEST, the death must be somewhere before I2, not I3.  If
2313        we passed I3 in that case, it might delete I2.  */
2314
2315     if (i2dest_in_i2src)
2316       {
2317         if (GET_CODE (i2dest) == REG)
2318           REG_N_DEATHS (REGNO (i2dest))++;
2319
2320         if (newi2pat && reg_set_p (i2dest, newi2pat))
2321           distribute_notes (gen_rtx (EXPR_LIST, REG_DEAD, i2dest, NULL_RTX),
2322                             NULL_RTX, i2, NULL_RTX, NULL_RTX, NULL_RTX);
2323         else
2324           distribute_notes (gen_rtx (EXPR_LIST, REG_DEAD, i2dest, NULL_RTX),
2325                             NULL_RTX, i3, newi2pat ? i2 : NULL_RTX,
2326                             NULL_RTX, NULL_RTX);
2327       }
2328
2329     if (i1dest_in_i1src)
2330       {
2331         if (GET_CODE (i1dest) == REG)
2332           REG_N_DEATHS (REGNO (i1dest))++;
2333
2334         if (newi2pat && reg_set_p (i1dest, newi2pat))
2335           distribute_notes (gen_rtx (EXPR_LIST, REG_DEAD, i1dest, NULL_RTX),
2336                             NULL_RTX, i2, NULL_RTX, NULL_RTX, NULL_RTX);
2337         else
2338           distribute_notes (gen_rtx (EXPR_LIST, REG_DEAD, i1dest, NULL_RTX),
2339                             NULL_RTX, i3, newi2pat ? i2 : NULL_RTX,
2340                             NULL_RTX, NULL_RTX);
2341       }
2342
2343     distribute_links (i3links);
2344     distribute_links (i2links);
2345     distribute_links (i1links);
2346
2347     if (GET_CODE (i2dest) == REG)
2348       {
2349         rtx link;
2350         rtx i2_insn = 0, i2_val = 0, set;
2351
2352         /* The insn that used to set this register doesn't exist, and
2353            this life of the register may not exist either.  See if one of
2354            I3's links points to an insn that sets I2DEST.  If it does,
2355            that is now the last known value for I2DEST. If we don't update
2356            this and I2 set the register to a value that depended on its old
2357            contents, we will get confused.  If this insn is used, thing
2358            will be set correctly in combine_instructions.  */
2359
2360         for (link = LOG_LINKS (i3); link; link = XEXP (link, 1))
2361           if ((set = single_set (XEXP (link, 0))) != 0
2362               && rtx_equal_p (i2dest, SET_DEST (set)))
2363             i2_insn = XEXP (link, 0), i2_val = SET_SRC (set);
2364
2365         record_value_for_reg (i2dest, i2_insn, i2_val);
2366
2367         /* If the reg formerly set in I2 died only once and that was in I3,
2368            zero its use count so it won't make `reload' do any work.  */
2369         if (! added_sets_2
2370             && (newi2pat == 0 || ! reg_mentioned_p (i2dest, newi2pat))
2371             && ! i2dest_in_i2src)
2372           {
2373             regno = REGNO (i2dest);
2374             REG_N_SETS (regno)--;
2375             if (REG_N_SETS (regno) == 0
2376                 && ! REGNO_REG_SET_P (basic_block_live_at_start[0], regno))
2377               REG_N_REFS (regno) = 0;
2378           }
2379       }
2380
2381     if (i1 && GET_CODE (i1dest) == REG)
2382       {
2383         rtx link;
2384         rtx i1_insn = 0, i1_val = 0, set;
2385
2386         for (link = LOG_LINKS (i3); link; link = XEXP (link, 1))
2387           if ((set = single_set (XEXP (link, 0))) != 0
2388               && rtx_equal_p (i1dest, SET_DEST (set)))
2389             i1_insn = XEXP (link, 0), i1_val = SET_SRC (set);
2390
2391         record_value_for_reg (i1dest, i1_insn, i1_val);
2392
2393         regno = REGNO (i1dest);
2394         if (! added_sets_1 && ! i1dest_in_i1src)
2395           {
2396             REG_N_SETS (regno)--;
2397             if (REG_N_SETS (regno) == 0
2398                 && ! REGNO_REG_SET_P (basic_block_live_at_start[0], regno))
2399               REG_N_REFS (regno) = 0;
2400           }
2401       }
2402
2403     /* Update reg_nonzero_bits et al for any changes that may have been made
2404        to this insn.  */
2405
2406     note_stores (newpat, set_nonzero_bits_and_sign_copies);
2407     if (newi2pat)
2408       note_stores (newi2pat, set_nonzero_bits_and_sign_copies);
2409
2410     /* If we added any (clobber (scratch)), add them to the max for a
2411        block.  This is a very pessimistic calculation, since we might
2412        have had them already and this might not be the worst block, but
2413        it's not worth doing any better.  */
2414     max_scratch += i3_scratches + i2_scratches + other_scratches;
2415
2416     /* If I3 is now an unconditional jump, ensure that it has a
2417        BARRIER following it since it may have initially been a
2418        conditional jump.  It may also be the last nonnote insn.  */
2419
2420     if ((GET_CODE (newpat) == RETURN || simplejump_p (i3))
2421         && ((temp = next_nonnote_insn (i3)) == NULL_RTX
2422             || GET_CODE (temp) != BARRIER))
2423       emit_barrier_after (i3);
2424   }
2425
2426   combine_successes++;
2427
2428   /* Clear this here, so that subsequent get_last_value calls are not
2429      affected.  */
2430   subst_prev_insn = NULL_RTX;
2431
2432   if (added_links_insn
2433       && (newi2pat == 0 || INSN_CUID (added_links_insn) < INSN_CUID (i2))
2434       && INSN_CUID (added_links_insn) < INSN_CUID (i3))
2435     return added_links_insn;
2436   else
2437     return newi2pat ? i2 : i3;
2438 }
2439 \f
2440 /* Undo all the modifications recorded in undobuf.  */
2441
2442 static void
2443 undo_all ()
2444 {
2445   struct undo *undo, *next;
2446
2447   for (undo = undobuf.undos; undo; undo = next)
2448     {
2449       next = undo->next;
2450       if (undo->is_int)
2451         *undo->where.i = undo->old_contents.i;
2452       else
2453         *undo->where.r = undo->old_contents.r;
2454
2455       undo->next = undobuf.frees;
2456       undobuf.frees = undo;
2457     }
2458
2459   obfree (undobuf.storage);
2460   undobuf.undos = undobuf.previous_undos = 0;
2461
2462   /* Clear this here, so that subsequent get_last_value calls are not
2463      affected.  */
2464   subst_prev_insn = NULL_RTX;
2465 }
2466 \f
2467 /* Find the innermost point within the rtx at LOC, possibly LOC itself,
2468    where we have an arithmetic expression and return that point.  LOC will
2469    be inside INSN.
2470
2471    try_combine will call this function to see if an insn can be split into
2472    two insns.  */
2473
2474 static rtx *
2475 find_split_point (loc, insn)
2476      rtx *loc;
2477      rtx insn;
2478 {
2479   rtx x = *loc;
2480   enum rtx_code code = GET_CODE (x);
2481   rtx *split;
2482   int len = 0, pos, unsignedp;
2483   rtx inner;
2484
2485   /* First special-case some codes.  */
2486   switch (code)
2487     {
2488     case SUBREG:
2489 #ifdef INSN_SCHEDULING
2490       /* If we are making a paradoxical SUBREG invalid, it becomes a split
2491          point.  */
2492       if (GET_CODE (SUBREG_REG (x)) == MEM)
2493         return loc;
2494 #endif
2495       return find_split_point (&SUBREG_REG (x), insn);
2496
2497     case MEM:
2498 #ifdef HAVE_lo_sum
2499       /* If we have (mem (const ..)) or (mem (symbol_ref ...)), split it
2500          using LO_SUM and HIGH.  */
2501       if (GET_CODE (XEXP (x, 0)) == CONST
2502           || GET_CODE (XEXP (x, 0)) == SYMBOL_REF)
2503         {
2504           SUBST (XEXP (x, 0),
2505                  gen_rtx_combine (LO_SUM, Pmode,
2506                                   gen_rtx_combine (HIGH, Pmode, XEXP (x, 0)),
2507                                   XEXP (x, 0)));
2508           return &XEXP (XEXP (x, 0), 0);
2509         }
2510 #endif
2511
2512       /* If we have a PLUS whose second operand is a constant and the
2513          address is not valid, perhaps will can split it up using
2514          the machine-specific way to split large constants.  We use
2515          the first pseudo-reg (one of the virtual regs) as a placeholder;
2516          it will not remain in the result.  */
2517       if (GET_CODE (XEXP (x, 0)) == PLUS
2518           && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
2519           && ! memory_address_p (GET_MODE (x), XEXP (x, 0)))
2520         {
2521           rtx reg = regno_reg_rtx[FIRST_PSEUDO_REGISTER];
2522           rtx seq = split_insns (gen_rtx (SET, VOIDmode, reg, XEXP (x, 0)),
2523                                  subst_insn);
2524
2525           /* This should have produced two insns, each of which sets our
2526              placeholder.  If the source of the second is a valid address,
2527              we can make put both sources together and make a split point
2528              in the middle.  */
2529
2530           if (seq && XVECLEN (seq, 0) == 2
2531               && GET_CODE (XVECEXP (seq, 0, 0)) == INSN
2532               && GET_CODE (PATTERN (XVECEXP (seq, 0, 0))) == SET
2533               && SET_DEST (PATTERN (XVECEXP (seq, 0, 0))) == reg
2534               && ! reg_mentioned_p (reg,
2535                                     SET_SRC (PATTERN (XVECEXP (seq, 0, 0))))
2536               && GET_CODE (XVECEXP (seq, 0, 1)) == INSN
2537               && GET_CODE (PATTERN (XVECEXP (seq, 0, 1))) == SET
2538               && SET_DEST (PATTERN (XVECEXP (seq, 0, 1))) == reg
2539               && memory_address_p (GET_MODE (x),
2540                                    SET_SRC (PATTERN (XVECEXP (seq, 0, 1)))))
2541             {
2542               rtx src1 = SET_SRC (PATTERN (XVECEXP (seq, 0, 0)));
2543               rtx src2 = SET_SRC (PATTERN (XVECEXP (seq, 0, 1)));
2544
2545               /* Replace the placeholder in SRC2 with SRC1.  If we can
2546                  find where in SRC2 it was placed, that can become our
2547                  split point and we can replace this address with SRC2.
2548                  Just try two obvious places.  */
2549
2550               src2 = replace_rtx (src2, reg, src1);
2551               split = 0;
2552               if (XEXP (src2, 0) == src1)
2553                 split = &XEXP (src2, 0);
2554               else if (GET_RTX_FORMAT (GET_CODE (XEXP (src2, 0)))[0] == 'e'
2555                        && XEXP (XEXP (src2, 0), 0) == src1)
2556                 split = &XEXP (XEXP (src2, 0), 0);
2557
2558               if (split)
2559                 {
2560                   SUBST (XEXP (x, 0), src2);
2561                   return split;
2562                 }
2563             }
2564
2565           /* If that didn't work, perhaps the first operand is complex and
2566              needs to be computed separately, so make a split point there.
2567              This will occur on machines that just support REG + CONST
2568              and have a constant moved through some previous computation.  */
2569
2570           else if (GET_RTX_CLASS (GET_CODE (XEXP (XEXP (x, 0), 0))) != 'o'
2571                    && ! (GET_CODE (XEXP (XEXP (x, 0), 0)) == SUBREG
2572                          && (GET_RTX_CLASS (GET_CODE (SUBREG_REG (XEXP (XEXP (x, 0), 0))))
2573                              == 'o')))
2574             return &XEXP (XEXP (x, 0), 0);
2575         }
2576       break;
2577
2578     case SET:
2579 #ifdef HAVE_cc0
2580       /* If SET_DEST is CC0 and SET_SRC is not an operand, a COMPARE, or a
2581          ZERO_EXTRACT, the most likely reason why this doesn't match is that
2582          we need to put the operand into a register.  So split at that
2583          point.  */
2584
2585       if (SET_DEST (x) == cc0_rtx
2586           && GET_CODE (SET_SRC (x)) != COMPARE
2587           && GET_CODE (SET_SRC (x)) != ZERO_EXTRACT
2588           && GET_RTX_CLASS (GET_CODE (SET_SRC (x))) != 'o'
2589           && ! (GET_CODE (SET_SRC (x)) == SUBREG
2590                 && GET_RTX_CLASS (GET_CODE (SUBREG_REG (SET_SRC (x)))) == 'o'))
2591         return &SET_SRC (x);
2592 #endif
2593
2594       /* See if we can split SET_SRC as it stands.  */
2595       split = find_split_point (&SET_SRC (x), insn);
2596       if (split && split != &SET_SRC (x))
2597         return split;
2598
2599       /* See if we can split SET_DEST as it stands.  */
2600       split = find_split_point (&SET_DEST (x), insn);
2601       if (split && split != &SET_DEST (x))
2602         return split;
2603
2604       /* See if this is a bitfield assignment with everything constant.  If
2605          so, this is an IOR of an AND, so split it into that.  */
2606       if (GET_CODE (SET_DEST (x)) == ZERO_EXTRACT
2607           && (GET_MODE_BITSIZE (GET_MODE (XEXP (SET_DEST (x), 0)))
2608               <= HOST_BITS_PER_WIDE_INT)
2609           && GET_CODE (XEXP (SET_DEST (x), 1)) == CONST_INT
2610           && GET_CODE (XEXP (SET_DEST (x), 2)) == CONST_INT
2611           && GET_CODE (SET_SRC (x)) == CONST_INT
2612           && ((INTVAL (XEXP (SET_DEST (x), 1))
2613               + INTVAL (XEXP (SET_DEST (x), 2)))
2614               <= GET_MODE_BITSIZE (GET_MODE (XEXP (SET_DEST (x), 0))))
2615           && ! side_effects_p (XEXP (SET_DEST (x), 0)))
2616         {
2617           int pos = INTVAL (XEXP (SET_DEST (x), 2));
2618           int len = INTVAL (XEXP (SET_DEST (x), 1));
2619           int src = INTVAL (SET_SRC (x));
2620           rtx dest = XEXP (SET_DEST (x), 0);
2621           enum machine_mode mode = GET_MODE (dest);
2622           unsigned HOST_WIDE_INT mask = ((HOST_WIDE_INT) 1 << len) - 1;
2623
2624           if (BITS_BIG_ENDIAN)
2625             pos = GET_MODE_BITSIZE (mode) - len - pos;
2626
2627           if (src == mask)
2628             SUBST (SET_SRC (x),
2629                    gen_binary (IOR, mode, dest, GEN_INT (src << pos)));
2630           else
2631             SUBST (SET_SRC (x),
2632                    gen_binary (IOR, mode,
2633                                gen_binary (AND, mode, dest,
2634                                            GEN_INT (~ (mask << pos)
2635                                                     & GET_MODE_MASK (mode))),
2636                                GEN_INT (src << pos)));
2637
2638           SUBST (SET_DEST (x), dest);
2639
2640           split = find_split_point (&SET_SRC (x), insn);
2641           if (split && split != &SET_SRC (x))
2642             return split;
2643         }
2644
2645       /* Otherwise, see if this is an operation that we can split into two.
2646          If so, try to split that.  */
2647       code = GET_CODE (SET_SRC (x));
2648
2649       switch (code)
2650         {
2651         case AND:
2652           /* If we are AND'ing with a large constant that is only a single
2653              bit and the result is only being used in a context where we
2654              need to know if it is zero or non-zero, replace it with a bit
2655              extraction.  This will avoid the large constant, which might
2656              have taken more than one insn to make.  If the constant were
2657              not a valid argument to the AND but took only one insn to make,
2658              this is no worse, but if it took more than one insn, it will
2659              be better.  */
2660
2661           if (GET_CODE (XEXP (SET_SRC (x), 1)) == CONST_INT
2662               && GET_CODE (XEXP (SET_SRC (x), 0)) == REG
2663               && (pos = exact_log2 (INTVAL (XEXP (SET_SRC (x), 1)))) >= 7
2664               && GET_CODE (SET_DEST (x)) == REG
2665               && (split = find_single_use (SET_DEST (x), insn, NULL_PTR)) != 0
2666               && (GET_CODE (*split) == EQ || GET_CODE (*split) == NE)
2667               && XEXP (*split, 0) == SET_DEST (x)
2668               && XEXP (*split, 1) == const0_rtx)
2669             {
2670               rtx extraction = make_extraction (GET_MODE (SET_DEST (x)),
2671                                                 XEXP (SET_SRC (x), 0),
2672                                                 pos, NULL_RTX, 1, 1, 0, 0);
2673               if (extraction != 0)
2674                 {
2675                   SUBST (SET_SRC (x), extraction);
2676                   return find_split_point (loc, insn);
2677                 }
2678             }
2679           break;
2680
2681         case NE:
2682           /* if STORE_FLAG_VALUE is -1, this is (NE X 0) and only one bit of X
2683              is known to be on, this can be converted into a NEG of a shift. */
2684           if (STORE_FLAG_VALUE == -1 && XEXP (SET_SRC (x), 1) == const0_rtx
2685               && GET_MODE (SET_SRC (x)) == GET_MODE (XEXP (SET_SRC (x), 0))
2686               && 1 <= (pos = exact_log2
2687                        (nonzero_bits (XEXP (SET_SRC (x), 0),
2688                                       GET_MODE (XEXP (SET_SRC (x), 0))))))
2689             {
2690               enum machine_mode mode = GET_MODE (XEXP (SET_SRC (x), 0));
2691
2692               SUBST (SET_SRC (x),
2693                      gen_rtx_combine (NEG, mode,
2694                                       gen_rtx_combine (LSHIFTRT, mode,
2695                                                        XEXP (SET_SRC (x), 0),
2696                                                        GEN_INT (pos))));
2697
2698               split = find_split_point (&SET_SRC (x), insn);
2699               if (split && split != &SET_SRC (x))
2700                 return split;
2701             }
2702           break;
2703
2704         case SIGN_EXTEND:
2705           inner = XEXP (SET_SRC (x), 0);
2706
2707           /* We can't optimize if either mode is a partial integer
2708              mode as we don't know how many bits are significant
2709              in those modes.  */
2710           if (GET_MODE_CLASS (GET_MODE (inner)) == MODE_PARTIAL_INT
2711               || GET_MODE_CLASS (GET_MODE (SET_SRC (x))) == MODE_PARTIAL_INT)
2712             break;
2713
2714           pos = 0;
2715           len = GET_MODE_BITSIZE (GET_MODE (inner));
2716           unsignedp = 0;
2717           break;
2718
2719         case SIGN_EXTRACT:
2720         case ZERO_EXTRACT:
2721           if (GET_CODE (XEXP (SET_SRC (x), 1)) == CONST_INT
2722               && GET_CODE (XEXP (SET_SRC (x), 2)) == CONST_INT)
2723             {
2724               inner = XEXP (SET_SRC (x), 0);
2725               len = INTVAL (XEXP (SET_SRC (x), 1));
2726               pos = INTVAL (XEXP (SET_SRC (x), 2));
2727
2728               if (BITS_BIG_ENDIAN)
2729                 pos = GET_MODE_BITSIZE (GET_MODE (inner)) - len - pos;
2730               unsignedp = (code == ZERO_EXTRACT);
2731             }
2732           break;
2733         }
2734
2735       if (len && pos >= 0 && pos + len <= GET_MODE_BITSIZE (GET_MODE (inner)))
2736         {
2737           enum machine_mode mode = GET_MODE (SET_SRC (x));
2738
2739           /* For unsigned, we have a choice of a shift followed by an
2740              AND or two shifts.  Use two shifts for field sizes where the
2741              constant might be too large.  We assume here that we can
2742              always at least get 8-bit constants in an AND insn, which is
2743              true for every current RISC.  */
2744
2745           if (unsignedp && len <= 8)
2746             {
2747               SUBST (SET_SRC (x),
2748                      gen_rtx_combine
2749                      (AND, mode,
2750                       gen_rtx_combine (LSHIFTRT, mode,
2751                                        gen_lowpart_for_combine (mode, inner),
2752                                        GEN_INT (pos)),
2753                       GEN_INT (((HOST_WIDE_INT) 1 << len) - 1)));
2754
2755               split = find_split_point (&SET_SRC (x), insn);
2756               if (split && split != &SET_SRC (x))
2757                 return split;
2758             }
2759           else
2760             {
2761               SUBST (SET_SRC (x),
2762                      gen_rtx_combine
2763                      (unsignedp ? LSHIFTRT : ASHIFTRT, mode,
2764                       gen_rtx_combine (ASHIFT, mode,
2765                                        gen_lowpart_for_combine (mode, inner),
2766                                        GEN_INT (GET_MODE_BITSIZE (mode)
2767                                                 - len - pos)),
2768                       GEN_INT (GET_MODE_BITSIZE (mode) - len)));
2769
2770               split = find_split_point (&SET_SRC (x), insn);
2771               if (split && split != &SET_SRC (x))
2772                 return split;
2773             }
2774         }
2775
2776       /* See if this is a simple operation with a constant as the second
2777          operand.  It might be that this constant is out of range and hence
2778          could be used as a split point.  */
2779       if ((GET_RTX_CLASS (GET_CODE (SET_SRC (x))) == '2'
2780            || GET_RTX_CLASS (GET_CODE (SET_SRC (x))) == 'c'
2781            || GET_RTX_CLASS (GET_CODE (SET_SRC (x))) == '<')
2782           && CONSTANT_P (XEXP (SET_SRC (x), 1))
2783           && (GET_RTX_CLASS (GET_CODE (XEXP (SET_SRC (x), 0))) == 'o'
2784               || (GET_CODE (XEXP (SET_SRC (x), 0)) == SUBREG
2785                   && (GET_RTX_CLASS (GET_CODE (SUBREG_REG (XEXP (SET_SRC (x), 0))))
2786                       == 'o'))))
2787         return &XEXP (SET_SRC (x), 1);
2788
2789       /* Finally, see if this is a simple operation with its first operand
2790          not in a register.  The operation might require this operand in a
2791          register, so return it as a split point.  We can always do this
2792          because if the first operand were another operation, we would have
2793          already found it as a split point.  */
2794       if ((GET_RTX_CLASS (GET_CODE (SET_SRC (x))) == '2'
2795            || GET_RTX_CLASS (GET_CODE (SET_SRC (x))) == 'c'
2796            || GET_RTX_CLASS (GET_CODE (SET_SRC (x))) == '<'
2797            || GET_RTX_CLASS (GET_CODE (SET_SRC (x))) == '1')
2798           && ! register_operand (XEXP (SET_SRC (x), 0), VOIDmode))
2799         return &XEXP (SET_SRC (x), 0);
2800
2801       return 0;
2802
2803     case AND:
2804     case IOR:
2805       /* We write NOR as (and (not A) (not B)), but if we don't have a NOR,
2806          it is better to write this as (not (ior A B)) so we can split it.
2807          Similarly for IOR.  */
2808       if (GET_CODE (XEXP (x, 0)) == NOT && GET_CODE (XEXP (x, 1)) == NOT)
2809         {
2810           SUBST (*loc,
2811                  gen_rtx_combine (NOT, GET_MODE (x),
2812                                   gen_rtx_combine (code == IOR ? AND : IOR,
2813                                                    GET_MODE (x),
2814                                                    XEXP (XEXP (x, 0), 0),
2815                                                    XEXP (XEXP (x, 1), 0))));
2816           return find_split_point (loc, insn);
2817         }
2818
2819       /* Many RISC machines have a large set of logical insns.  If the
2820          second operand is a NOT, put it first so we will try to split the
2821          other operand first.  */
2822       if (GET_CODE (XEXP (x, 1)) == NOT)
2823         {
2824           rtx tem = XEXP (x, 0);
2825           SUBST (XEXP (x, 0), XEXP (x, 1));
2826           SUBST (XEXP (x, 1), tem);
2827         }
2828       break;
2829     }
2830
2831   /* Otherwise, select our actions depending on our rtx class.  */
2832   switch (GET_RTX_CLASS (code))
2833     {
2834     case 'b':                   /* This is ZERO_EXTRACT and SIGN_EXTRACT.  */
2835     case '3':
2836       split = find_split_point (&XEXP (x, 2), insn);
2837       if (split)
2838         return split;
2839       /* ... fall through ...  */
2840     case '2':
2841     case 'c':
2842     case '<':
2843       split = find_split_point (&XEXP (x, 1), insn);
2844       if (split)
2845         return split;
2846       /* ... fall through ...  */
2847     case '1':
2848       /* Some machines have (and (shift ...) ...) insns.  If X is not
2849          an AND, but XEXP (X, 0) is, use it as our split point.  */
2850       if (GET_CODE (x) != AND && GET_CODE (XEXP (x, 0)) == AND)
2851         return &XEXP (x, 0);
2852
2853       split = find_split_point (&XEXP (x, 0), insn);
2854       if (split)
2855         return split;
2856       return loc;
2857     }
2858
2859   /* Otherwise, we don't have a split point.  */
2860   return 0;
2861 }
2862 \f
2863 /* Throughout X, replace FROM with TO, and return the result.
2864    The result is TO if X is FROM;
2865    otherwise the result is X, but its contents may have been modified.
2866    If they were modified, a record was made in undobuf so that
2867    undo_all will (among other things) return X to its original state.
2868
2869    If the number of changes necessary is too much to record to undo,
2870    the excess changes are not made, so the result is invalid.
2871    The changes already made can still be undone.
2872    undobuf.num_undo is incremented for such changes, so by testing that
2873    the caller can tell whether the result is valid.
2874
2875    `n_occurrences' is incremented each time FROM is replaced.
2876
2877    IN_DEST is non-zero if we are processing the SET_DEST of a SET.
2878
2879    UNIQUE_COPY is non-zero if each substitution must be unique.  We do this
2880    by copying if `n_occurrences' is non-zero.  */
2881
2882 static rtx
2883 subst (x, from, to, in_dest, unique_copy)
2884      register rtx x, from, to;
2885      int in_dest;
2886      int unique_copy;
2887 {
2888   register enum rtx_code code = GET_CODE (x);
2889   enum machine_mode op0_mode = VOIDmode;
2890   register char *fmt;
2891   register int len, i;
2892   rtx new;
2893
2894 /* Two expressions are equal if they are identical copies of a shared
2895    RTX or if they are both registers with the same register number
2896    and mode.  */
2897
2898 #define COMBINE_RTX_EQUAL_P(X,Y)                        \
2899   ((X) == (Y)                                           \
2900    || (GET_CODE (X) == REG && GET_CODE (Y) == REG       \
2901        && REGNO (X) == REGNO (Y) && GET_MODE (X) == GET_MODE (Y)))
2902
2903   if (! in_dest && COMBINE_RTX_EQUAL_P (x, from))
2904     {
2905       n_occurrences++;
2906       return (unique_copy && n_occurrences > 1 ? copy_rtx (to) : to);
2907     }
2908
2909   /* If X and FROM are the same register but different modes, they will
2910      not have been seen as equal above.  However, flow.c will make a
2911      LOG_LINKS entry for that case.  If we do nothing, we will try to
2912      rerecognize our original insn and, when it succeeds, we will
2913      delete the feeding insn, which is incorrect.
2914
2915      So force this insn not to match in this (rare) case.  */
2916   if (! in_dest && code == REG && GET_CODE (from) == REG
2917       && REGNO (x) == REGNO (from))
2918     return gen_rtx (CLOBBER, GET_MODE (x), const0_rtx);
2919
2920   /* If this is an object, we are done unless it is a MEM or LO_SUM, both
2921      of which may contain things that can be combined.  */
2922   if (code != MEM && code != LO_SUM && GET_RTX_CLASS (code) == 'o')
2923     return x;
2924
2925   /* It is possible to have a subexpression appear twice in the insn.
2926      Suppose that FROM is a register that appears within TO.
2927      Then, after that subexpression has been scanned once by `subst',
2928      the second time it is scanned, TO may be found.  If we were
2929      to scan TO here, we would find FROM within it and create a
2930      self-referent rtl structure which is completely wrong.  */
2931   if (COMBINE_RTX_EQUAL_P (x, to))
2932     return to;
2933
2934   len = GET_RTX_LENGTH (code);
2935   fmt = GET_RTX_FORMAT (code);
2936
2937   /* We don't need to process a SET_DEST that is a register, CC0, or PC, so
2938      set up to skip this common case.  All other cases where we want to
2939      suppress replacing something inside a SET_SRC are handled via the
2940      IN_DEST operand.  */
2941   if (code == SET
2942       && (GET_CODE (SET_DEST (x)) == REG
2943         || GET_CODE (SET_DEST (x)) == CC0
2944         || GET_CODE (SET_DEST (x)) == PC))
2945     fmt = "ie";
2946
2947   /* Get the mode of operand 0 in case X is now a SIGN_EXTEND of a
2948      constant.  */
2949   if (fmt[0] == 'e')
2950     op0_mode = GET_MODE (XEXP (x, 0));
2951
2952   for (i = 0; i < len; i++)
2953     {
2954       if (fmt[i] == 'E')
2955         {
2956           register int j;
2957           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2958             {
2959               if (COMBINE_RTX_EQUAL_P (XVECEXP (x, i, j), from))
2960                 {
2961                   new = (unique_copy && n_occurrences ? copy_rtx (to) : to);
2962                   n_occurrences++;
2963                 }
2964               else
2965                 {
2966                   new = subst (XVECEXP (x, i, j), from, to, 0, unique_copy);
2967
2968                   /* If this substitution failed, this whole thing fails.  */
2969                   if (GET_CODE (new) == CLOBBER && XEXP (new, 0) == const0_rtx)
2970                     return new;
2971                 }
2972
2973               SUBST (XVECEXP (x, i, j), new);
2974             }
2975         }
2976       else if (fmt[i] == 'e')
2977         {
2978           if (COMBINE_RTX_EQUAL_P (XEXP (x, i), from))
2979             {
2980               /* In general, don't install a subreg involving two modes not
2981                  tieable.  It can worsen register allocation, and can even
2982                  make invalid reload insns, since the reg inside may need to
2983                  be copied from in the outside mode, and that may be invalid
2984                  if it is an fp reg copied in integer mode.
2985
2986                  We allow two exceptions to this: It is valid if it is inside
2987                  another SUBREG and the mode of that SUBREG and the mode of
2988                  the inside of TO is tieable and it is valid if X is a SET
2989                  that copies FROM to CC0.  */
2990               if (GET_CODE (to) == SUBREG
2991                   && ! MODES_TIEABLE_P (GET_MODE (to),
2992                                         GET_MODE (SUBREG_REG (to)))
2993                   && ! (code == SUBREG
2994                         && MODES_TIEABLE_P (GET_MODE (x),
2995                                             GET_MODE (SUBREG_REG (to))))
2996 #ifdef HAVE_cc0
2997                   && ! (code == SET && i == 1 && XEXP (x, 0) == cc0_rtx)
2998 #endif
2999                   )
3000                 return gen_rtx (CLOBBER, VOIDmode, const0_rtx);
3001
3002               new = (unique_copy && n_occurrences ? copy_rtx (to) : to);
3003               n_occurrences++;
3004             }
3005           else
3006             /* If we are in a SET_DEST, suppress most cases unless we
3007                have gone inside a MEM, in which case we want to
3008                simplify the address.  We assume here that things that
3009                are actually part of the destination have their inner
3010                parts in the first expression.  This is true for SUBREG,
3011                STRICT_LOW_PART, and ZERO_EXTRACT, which are the only
3012                things aside from REG and MEM that should appear in a
3013                SET_DEST.  */
3014             new = subst (XEXP (x, i), from, to,
3015                          (((in_dest
3016                             && (code == SUBREG || code == STRICT_LOW_PART
3017                                 || code == ZERO_EXTRACT))
3018                            || code == SET)
3019                           && i == 0), unique_copy);
3020
3021           /* If we found that we will have to reject this combination,
3022              indicate that by returning the CLOBBER ourselves, rather than
3023              an expression containing it.  This will speed things up as
3024              well as prevent accidents where two CLOBBERs are considered
3025              to be equal, thus producing an incorrect simplification.  */
3026
3027           if (GET_CODE (new) == CLOBBER && XEXP (new, 0) == const0_rtx)
3028             return new;
3029
3030           SUBST (XEXP (x, i), new);
3031         }
3032     }
3033
3034   /* Try to simplify X.  If the simplification changed the code, it is likely
3035      that further simplification will help, so loop, but limit the number
3036      of repetitions that will be performed.  */
3037
3038   for (i = 0; i < 4; i++)
3039     {
3040       /* If X is sufficiently simple, don't bother trying to do anything
3041          with it.  */
3042       if (code != CONST_INT && code != REG && code != CLOBBER)
3043         x = simplify_rtx (x, op0_mode, i == 3, in_dest);
3044
3045       if (GET_CODE (x) == code)
3046         break;
3047
3048       code = GET_CODE (x);
3049
3050       /* We no longer know the original mode of operand 0 since we
3051          have changed the form of X)  */
3052       op0_mode = VOIDmode;
3053     }
3054
3055   return x;
3056 }
3057 \f
3058 /* Simplify X, a piece of RTL.  We just operate on the expression at the
3059    outer level; call `subst' to simplify recursively.  Return the new
3060    expression.
3061
3062    OP0_MODE is the original mode of XEXP (x, 0); LAST is nonzero if this
3063    will be the iteration even if an expression with a code different from
3064    X is returned; IN_DEST is nonzero if we are inside a SET_DEST.  */
3065
3066 static rtx
3067 simplify_rtx (x, op0_mode, last, in_dest)
3068      rtx x;
3069      enum machine_mode op0_mode;
3070      int last;
3071      int in_dest;
3072 {
3073   enum rtx_code code = GET_CODE (x);
3074   enum machine_mode mode = GET_MODE (x);
3075   rtx temp;
3076   int i;
3077
3078   /* If this is a commutative operation, put a constant last and a complex
3079      expression first.  We don't need to do this for comparisons here.  */
3080   if (GET_RTX_CLASS (code) == 'c'
3081       && ((CONSTANT_P (XEXP (x, 0)) && GET_CODE (XEXP (x, 1)) != CONST_INT)
3082           || (GET_RTX_CLASS (GET_CODE (XEXP (x, 0))) == 'o'
3083               && GET_RTX_CLASS (GET_CODE (XEXP (x, 1))) != 'o')
3084           || (GET_CODE (XEXP (x, 0)) == SUBREG
3085               && GET_RTX_CLASS (GET_CODE (SUBREG_REG (XEXP (x, 0)))) == 'o'
3086               && GET_RTX_CLASS (GET_CODE (XEXP (x, 1))) != 'o')))
3087     {
3088       temp = XEXP (x, 0);
3089       SUBST (XEXP (x, 0), XEXP (x, 1));
3090       SUBST (XEXP (x, 1), temp);
3091     }
3092
3093   /* If this is a PLUS, MINUS, or MULT, and the first operand is the
3094      sign extension of a PLUS with a constant, reverse the order of the sign
3095      extension and the addition. Note that this not the same as the original
3096      code, but overflow is undefined for signed values.  Also note that the
3097      PLUS will have been partially moved "inside" the sign-extension, so that
3098      the first operand of X will really look like:
3099          (ashiftrt (plus (ashift A C4) C5) C4).
3100      We convert this to
3101          (plus (ashiftrt (ashift A C4) C2) C4)
3102      and replace the first operand of X with that expression.  Later parts
3103      of this function may simplify the expression further.
3104
3105      For example, if we start with (mult (sign_extend (plus A C1)) C2),
3106      we swap the SIGN_EXTEND and PLUS.  Later code will apply the
3107      distributive law to produce (plus (mult (sign_extend X) C1) C3).
3108
3109      We do this to simplify address expressions.  */
3110
3111   if ((code == PLUS || code == MINUS || code == MULT)
3112       && GET_CODE (XEXP (x, 0)) == ASHIFTRT
3113       && GET_CODE (XEXP (XEXP (x, 0), 0)) == PLUS
3114       && GET_CODE (XEXP (XEXP (XEXP (x, 0), 0), 0)) == ASHIFT
3115       && GET_CODE (XEXP (XEXP (XEXP (XEXP (x, 0), 0), 0), 1)) == CONST_INT
3116       && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
3117       && XEXP (XEXP (XEXP (XEXP (x, 0), 0), 0), 1) == XEXP (XEXP (x, 0), 1)
3118       && GET_CODE (XEXP (XEXP (XEXP (x, 0), 0), 1)) == CONST_INT
3119       && (temp = simplify_binary_operation (ASHIFTRT, mode,
3120                                             XEXP (XEXP (XEXP (x, 0), 0), 1),
3121                                             XEXP (XEXP (x, 0), 1))) != 0)
3122     {
3123       rtx new
3124         = simplify_shift_const (NULL_RTX, ASHIFT, mode,
3125                                 XEXP (XEXP (XEXP (XEXP (x, 0), 0), 0), 0),
3126                                 INTVAL (XEXP (XEXP (x, 0), 1)));
3127
3128       new = simplify_shift_const (NULL_RTX, ASHIFTRT, mode, new,
3129                                   INTVAL (XEXP (XEXP (x, 0), 1)));
3130
3131       SUBST (XEXP (x, 0), gen_binary (PLUS, mode, new, temp));
3132     }
3133
3134   /* If this is a simple operation applied to an IF_THEN_ELSE, try
3135      applying it to the arms of the IF_THEN_ELSE.  This often simplifies
3136      things.  Check for cases where both arms are testing the same
3137      condition.
3138
3139      Don't do anything if all operands are very simple.  */
3140
3141   if (((GET_RTX_CLASS (code) == '2' || GET_RTX_CLASS (code) == 'c'
3142         || GET_RTX_CLASS (code) == '<')
3143        && ((GET_RTX_CLASS (GET_CODE (XEXP (x, 0))) != 'o'
3144             && ! (GET_CODE (XEXP (x, 0)) == SUBREG
3145                   && (GET_RTX_CLASS (GET_CODE (SUBREG_REG (XEXP (x, 0))))
3146                       == 'o')))
3147            || (GET_RTX_CLASS (GET_CODE (XEXP (x, 1))) != 'o'
3148                && ! (GET_CODE (XEXP (x, 1)) == SUBREG
3149                      && (GET_RTX_CLASS (GET_CODE (SUBREG_REG (XEXP (x, 1))))
3150                          == 'o')))))
3151       || (GET_RTX_CLASS (code) == '1'
3152           && ((GET_RTX_CLASS (GET_CODE (XEXP (x, 0))) != 'o'
3153                && ! (GET_CODE (XEXP (x, 0)) == SUBREG
3154                      && (GET_RTX_CLASS (GET_CODE (SUBREG_REG (XEXP (x, 0))))
3155                          == 'o'))))))
3156     {
3157       rtx cond, true, false;
3158
3159       cond = if_then_else_cond (x, &true, &false);
3160       if (cond != 0
3161           /* If everything is a comparison, what we have is highly unlikely
3162              to be simpler, so don't use it.  */
3163           && ! (GET_RTX_CLASS (code) == '<'
3164                 && (GET_RTX_CLASS (GET_CODE (true)) == '<'
3165                     || GET_RTX_CLASS (GET_CODE (false)) == '<')))
3166         {
3167           rtx cop1 = const0_rtx;
3168           enum rtx_code cond_code = simplify_comparison (NE, &cond, &cop1);
3169
3170           if (cond_code == NE && GET_RTX_CLASS (GET_CODE (cond)) == '<')
3171             return x;
3172
3173           /* Simplify the alternative arms; this may collapse the true and
3174              false arms to store-flag values.  */
3175           true = subst (true, pc_rtx, pc_rtx, 0, 0);
3176           false = subst (false, pc_rtx, pc_rtx, 0, 0);
3177
3178           /* Restarting if we generate a store-flag expression will cause
3179              us to loop.  Just drop through in this case.  */
3180
3181           /* If the result values are STORE_FLAG_VALUE and zero, we can
3182              just make the comparison operation.  */
3183           if (true == const_true_rtx && false == const0_rtx)
3184             x = gen_binary (cond_code, mode, cond, cop1);
3185           else if (true == const0_rtx && false == const_true_rtx)
3186             x = gen_binary (reverse_condition (cond_code), mode, cond, cop1);
3187
3188           /* Likewise, we can make the negate of a comparison operation
3189              if the result values are - STORE_FLAG_VALUE and zero.  */
3190           else if (GET_CODE (true) == CONST_INT
3191                    && INTVAL (true) == - STORE_FLAG_VALUE
3192                    && false == const0_rtx)
3193             x = gen_unary (NEG, mode, mode,
3194                            gen_binary (cond_code, mode, cond, cop1));
3195           else if (GET_CODE (false) == CONST_INT
3196                    && INTVAL (false) == - STORE_FLAG_VALUE
3197                    && true == const0_rtx)
3198             x = gen_unary (NEG, mode, mode,
3199                            gen_binary (reverse_condition (cond_code),
3200                                        mode, cond, cop1));
3201           else
3202             return gen_rtx (IF_THEN_ELSE, mode,
3203                             gen_binary (cond_code, VOIDmode, cond, cop1),
3204                             true, false);
3205
3206           code = GET_CODE (x);
3207           op0_mode = VOIDmode;
3208         }
3209     }
3210
3211   /* Try to fold this expression in case we have constants that weren't
3212      present before.  */
3213   temp = 0;
3214   switch (GET_RTX_CLASS (code))
3215     {
3216     case '1':
3217       temp = simplify_unary_operation (code, mode, XEXP (x, 0), op0_mode);
3218       break;
3219     case '<':
3220       temp = simplify_relational_operation (code, op0_mode,
3221                                             XEXP (x, 0), XEXP (x, 1));
3222 #ifdef FLOAT_STORE_FLAG_VALUE
3223       if (temp != 0 && GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT)
3224         temp = ((temp == const0_rtx) ? CONST0_RTX (GET_MODE (x))
3225                 : immed_real_const_1 (FLOAT_STORE_FLAG_VALUE, GET_MODE (x)));
3226 #endif
3227       break;
3228     case 'c':
3229     case '2':
3230       temp = simplify_binary_operation (code, mode, XEXP (x, 0), XEXP (x, 1));
3231       break;
3232     case 'b':
3233     case '3':
3234       temp = simplify_ternary_operation (code, mode, op0_mode, XEXP (x, 0),
3235                                          XEXP (x, 1), XEXP (x, 2));
3236       break;
3237     }
3238
3239   if (temp)
3240     x = temp, code = GET_CODE (temp);
3241
3242   /* First see if we can apply the inverse distributive law.  */
3243   if (code == PLUS || code == MINUS
3244       || code == AND || code == IOR || code == XOR)
3245     {
3246       x = apply_distributive_law (x);
3247       code = GET_CODE (x);
3248     }
3249
3250   /* If CODE is an associative operation not otherwise handled, see if we
3251      can associate some operands.  This can win if they are constants or
3252      if they are logically related (i.e. (a & b) & a.  */
3253   if ((code == PLUS || code == MINUS
3254        || code == MULT || code == AND || code == IOR || code == XOR
3255        || code == DIV || code == UDIV
3256        || code == SMAX || code == SMIN || code == UMAX || code == UMIN)
3257       && INTEGRAL_MODE_P (mode))
3258     {
3259       if (GET_CODE (XEXP (x, 0)) == code)
3260         {
3261           rtx other = XEXP (XEXP (x, 0), 0);
3262           rtx inner_op0 = XEXP (XEXP (x, 0), 1);
3263           rtx inner_op1 = XEXP (x, 1);
3264           rtx inner;
3265
3266           /* Make sure we pass the constant operand if any as the second
3267              one if this is a commutative operation.  */
3268           if (CONSTANT_P (inner_op0) && GET_RTX_CLASS (code) == 'c')
3269             {
3270               rtx tem = inner_op0;
3271               inner_op0 = inner_op1;
3272               inner_op1 = tem;
3273             }
3274           inner = simplify_binary_operation (code == MINUS ? PLUS
3275                                              : code == DIV ? MULT
3276                                              : code == UDIV ? MULT
3277                                              : code,
3278                                              mode, inner_op0, inner_op1);
3279
3280           /* For commutative operations, try the other pair if that one
3281              didn't simplify.  */
3282           if (inner == 0 && GET_RTX_CLASS (code) == 'c')
3283             {
3284               other = XEXP (XEXP (x, 0), 1);
3285               inner = simplify_binary_operation (code, mode,
3286                                                  XEXP (XEXP (x, 0), 0),
3287                                                  XEXP (x, 1));
3288             }
3289
3290           if (inner)
3291             return gen_binary (code, mode, other, inner);
3292         }
3293     }
3294
3295   /* A little bit of algebraic simplification here.  */
3296   switch (code)
3297     {
3298     case MEM:
3299       /* Ensure that our address has any ASHIFTs converted to MULT in case
3300          address-recognizing predicates are called later.  */
3301       temp = make_compound_operation (XEXP (x, 0), MEM);
3302       SUBST (XEXP (x, 0), temp);
3303       break;
3304
3305     case SUBREG:
3306       /* (subreg:A (mem:B X) N) becomes a modified MEM unless the SUBREG
3307          is paradoxical.  If we can't do that safely, then it becomes
3308          something nonsensical so that this combination won't take place.  */
3309
3310       if (GET_CODE (SUBREG_REG (x)) == MEM
3311           && (GET_MODE_SIZE (mode)
3312               <= GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))))
3313         {
3314           rtx inner = SUBREG_REG (x);
3315           int endian_offset = 0;
3316           /* Don't change the mode of the MEM
3317              if that would change the meaning of the address.  */
3318           if (MEM_VOLATILE_P (SUBREG_REG (x))
3319               || mode_dependent_address_p (XEXP (inner, 0)))
3320             return gen_rtx (CLOBBER, mode, const0_rtx);
3321
3322           if (BYTES_BIG_ENDIAN)
3323             {
3324               if (GET_MODE_SIZE (mode) < UNITS_PER_WORD)
3325                 endian_offset += UNITS_PER_WORD - GET_MODE_SIZE (mode);
3326               if (GET_MODE_SIZE (GET_MODE (inner)) < UNITS_PER_WORD)
3327                 endian_offset -= (UNITS_PER_WORD
3328                                   - GET_MODE_SIZE (GET_MODE (inner)));
3329             }
3330           /* Note if the plus_constant doesn't make a valid address
3331              then this combination won't be accepted.  */
3332           x = gen_rtx (MEM, mode,
3333                        plus_constant (XEXP (inner, 0),
3334                                       (SUBREG_WORD (x) * UNITS_PER_WORD
3335                                        + endian_offset)));
3336           MEM_VOLATILE_P (x) = MEM_VOLATILE_P (inner);
3337           RTX_UNCHANGING_P (x) = RTX_UNCHANGING_P (inner);
3338           MEM_IN_STRUCT_P (x) = MEM_IN_STRUCT_P (inner);
3339           return x;
3340         }
3341
3342       /* If we are in a SET_DEST, these other cases can't apply.  */
3343       if (in_dest)
3344         return x;
3345
3346       /* Changing mode twice with SUBREG => just change it once,
3347          or not at all if changing back to starting mode.  */
3348       if (GET_CODE (SUBREG_REG (x)) == SUBREG)
3349         {
3350           if (mode == GET_MODE (SUBREG_REG (SUBREG_REG (x)))
3351               && SUBREG_WORD (x) == 0 && SUBREG_WORD (SUBREG_REG (x)) == 0)
3352             return SUBREG_REG (SUBREG_REG (x));
3353
3354           SUBST_INT (SUBREG_WORD (x),
3355                      SUBREG_WORD (x) + SUBREG_WORD (SUBREG_REG (x)));
3356           SUBST (SUBREG_REG (x), SUBREG_REG (SUBREG_REG (x)));
3357         }
3358
3359       /* SUBREG of a hard register => just change the register number
3360          and/or mode.  If the hard register is not valid in that mode,
3361          suppress this combination.  If the hard register is the stack,
3362          frame, or argument pointer, leave this as a SUBREG.  */
3363
3364       if (GET_CODE (SUBREG_REG (x)) == REG
3365           && REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER
3366           && REGNO (SUBREG_REG (x)) != FRAME_POINTER_REGNUM
3367 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
3368           && REGNO (SUBREG_REG (x)) != HARD_FRAME_POINTER_REGNUM
3369 #endif
3370 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
3371           && REGNO (SUBREG_REG (x)) != ARG_POINTER_REGNUM
3372 #endif
3373           && REGNO (SUBREG_REG (x)) != STACK_POINTER_REGNUM)
3374         {
3375           if (HARD_REGNO_MODE_OK (REGNO (SUBREG_REG (x)) + SUBREG_WORD (x),
3376                                   mode))
3377             return gen_rtx (REG, mode,
3378                             REGNO (SUBREG_REG (x)) + SUBREG_WORD (x));
3379           else
3380             return gen_rtx (CLOBBER, mode, const0_rtx);
3381         }
3382
3383       /* For a constant, try to pick up the part we want.  Handle a full
3384          word and low-order part.  Only do this if we are narrowing
3385          the constant; if it is being widened, we have no idea what
3386          the extra bits will have been set to.  */
3387
3388       if (CONSTANT_P (SUBREG_REG (x)) && op0_mode != VOIDmode
3389           && GET_MODE_SIZE (mode) == UNITS_PER_WORD
3390           && GET_MODE_SIZE (op0_mode) > UNITS_PER_WORD
3391           && GET_MODE_CLASS (mode) == MODE_INT)
3392         {
3393           temp = operand_subword (SUBREG_REG (x), SUBREG_WORD (x),
3394                                   0, op0_mode);
3395           if (temp)
3396             return temp;
3397         }
3398
3399       /* If we want a subreg of a constant, at offset 0,
3400          take the low bits.  On a little-endian machine, that's
3401          always valid.  On a big-endian machine, it's valid
3402          only if the constant's mode fits in one word.   Note that we
3403          cannot use subreg_lowpart_p since SUBREG_REG may be VOIDmode.  */
3404       if (CONSTANT_P (SUBREG_REG (x))
3405           && ((GET_MODE_SIZE (op0_mode) <= UNITS_PER_WORD
3406               || ! WORDS_BIG_ENDIAN)
3407               ? SUBREG_WORD (x) == 0
3408               : (SUBREG_WORD (x)
3409                  == ((GET_MODE_SIZE (op0_mode)
3410                       - MAX (GET_MODE_SIZE (mode), UNITS_PER_WORD))
3411                      / UNITS_PER_WORD)))
3412           && GET_MODE_SIZE (mode) <= GET_MODE_SIZE (op0_mode)
3413           && (! WORDS_BIG_ENDIAN
3414               || GET_MODE_BITSIZE (op0_mode) <= BITS_PER_WORD))
3415         return gen_lowpart_for_combine (mode, SUBREG_REG (x));
3416
3417       /* A paradoxical SUBREG of a VOIDmode constant is the same constant,
3418          since we are saying that the high bits don't matter.  */
3419       if (CONSTANT_P (SUBREG_REG (x)) && GET_MODE (SUBREG_REG (x)) == VOIDmode
3420           && GET_MODE_SIZE (mode) > GET_MODE_SIZE (op0_mode))
3421         return SUBREG_REG (x);
3422
3423       /* Note that we cannot do any narrowing for non-constants since
3424          we might have been counting on using the fact that some bits were
3425          zero.  We now do this in the SET.  */
3426
3427       break;
3428
3429     case NOT:
3430       /* (not (plus X -1)) can become (neg X).  */
3431       if (GET_CODE (XEXP (x, 0)) == PLUS
3432           && XEXP (XEXP (x, 0), 1) == constm1_rtx)
3433         return gen_rtx_combine (NEG, mode, XEXP (XEXP (x, 0), 0));
3434
3435       /* Similarly, (not (neg X)) is (plus X -1).  */
3436       if (GET_CODE (XEXP (x, 0)) == NEG)
3437         return gen_rtx_combine (PLUS, mode, XEXP (XEXP (x, 0), 0),
3438                                 constm1_rtx);
3439
3440       /* (not (xor X C)) for C constant is (xor X D) with D = ~ C.  */
3441       if (GET_CODE (XEXP (x, 0)) == XOR
3442           && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
3443           && (temp = simplify_unary_operation (NOT, mode,
3444                                                XEXP (XEXP (x, 0), 1),
3445                                                mode)) != 0)
3446         return gen_binary (XOR, mode, XEXP (XEXP (x, 0), 0), temp);
3447
3448       /* (not (ashift 1 X)) is (rotate ~1 X).  We used to do this for operands
3449          other than 1, but that is not valid.  We could do a similar
3450          simplification for (not (lshiftrt C X)) where C is just the sign bit,
3451          but this doesn't seem common enough to bother with.  */
3452       if (GET_CODE (XEXP (x, 0)) == ASHIFT
3453           && XEXP (XEXP (x, 0), 0) == const1_rtx)
3454         return gen_rtx (ROTATE, mode, gen_unary (NOT, mode, mode, const1_rtx),
3455                         XEXP (XEXP (x, 0), 1));
3456
3457       if (GET_CODE (XEXP (x, 0)) == SUBREG
3458           && subreg_lowpart_p (XEXP (x, 0))
3459           && (GET_MODE_SIZE (GET_MODE (XEXP (x, 0)))
3460               < GET_MODE_SIZE (GET_MODE (SUBREG_REG (XEXP (x, 0)))))
3461           && GET_CODE (SUBREG_REG (XEXP (x, 0))) == ASHIFT
3462           && XEXP (SUBREG_REG (XEXP (x, 0)), 0) == const1_rtx)
3463         {
3464           enum machine_mode inner_mode = GET_MODE (SUBREG_REG (XEXP (x, 0)));
3465
3466           x = gen_rtx (ROTATE, inner_mode,
3467                        gen_unary (NOT, inner_mode, inner_mode, const1_rtx),
3468                        XEXP (SUBREG_REG (XEXP (x, 0)), 1));
3469           return gen_lowpart_for_combine (mode, x);
3470         }
3471
3472       /* If STORE_FLAG_VALUE is -1, (not (comparison foo bar)) can be done by
3473          reversing the comparison code if valid.  */
3474       if (STORE_FLAG_VALUE == -1
3475           && GET_RTX_CLASS (GET_CODE (XEXP (x, 0))) == '<'
3476           && reversible_comparison_p (XEXP (x, 0)))
3477         return gen_rtx_combine (reverse_condition (GET_CODE (XEXP (x, 0))),
3478                                 mode, XEXP (XEXP (x, 0), 0),
3479                                 XEXP (XEXP (x, 0), 1));
3480
3481       /* (ashiftrt foo C) where C is the number of bits in FOO minus 1
3482          is (lt foo (const_int 0)) if STORE_FLAG_VALUE is -1, so we can
3483          perform the above simplification.  */
3484
3485       if (STORE_FLAG_VALUE == -1
3486           && XEXP (x, 1) == const1_rtx
3487           && GET_CODE (XEXP (x, 0)) == ASHIFTRT
3488           && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
3489           && INTVAL (XEXP (XEXP (x, 0), 1)) == GET_MODE_BITSIZE (mode) - 1)
3490         return gen_rtx_combine (GE, mode, XEXP (XEXP (x, 0), 0), const0_rtx);
3491
3492       /* Apply De Morgan's laws to reduce number of patterns for machines
3493          with negating logical insns (and-not, nand, etc.).  If result has
3494          only one NOT, put it first, since that is how the patterns are
3495          coded.  */
3496
3497       if (GET_CODE (XEXP (x, 0)) == IOR || GET_CODE (XEXP (x, 0)) == AND)
3498         {
3499          rtx in1 = XEXP (XEXP (x, 0), 0), in2 = XEXP (XEXP (x, 0), 1);
3500
3501          if (GET_CODE (in1) == NOT)
3502            in1 = XEXP (in1, 0);
3503          else
3504            in1 = gen_rtx_combine (NOT, GET_MODE (in1), in1);
3505
3506          if (GET_CODE (in2) == NOT)
3507            in2 = XEXP (in2, 0);
3508          else if (GET_CODE (in2) == CONST_INT
3509                   && GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT)
3510            in2 = GEN_INT (GET_MODE_MASK (mode) & ~ INTVAL (in2));
3511          else
3512            in2 = gen_rtx_combine (NOT, GET_MODE (in2), in2);
3513
3514          if (GET_CODE (in2) == NOT)
3515            {
3516              rtx tem = in2;
3517              in2 = in1; in1 = tem;
3518            }
3519
3520          return gen_rtx_combine (GET_CODE (XEXP (x, 0)) == IOR ? AND : IOR,
3521                                  mode, in1, in2);
3522        }
3523       break;
3524
3525     case NEG:
3526       /* (neg (plus X 1)) can become (not X).  */
3527       if (GET_CODE (XEXP (x, 0)) == PLUS
3528           && XEXP (XEXP (x, 0), 1) == const1_rtx)
3529         return gen_rtx_combine (NOT, mode, XEXP (XEXP (x, 0), 0));
3530
3531       /* Similarly, (neg (not X)) is (plus X 1).  */
3532       if (GET_CODE (XEXP (x, 0)) == NOT)
3533         return plus_constant (XEXP (XEXP (x, 0), 0), 1);
3534
3535       /* (neg (minus X Y)) can become (minus Y X).  */
3536       if (GET_CODE (XEXP (x, 0)) == MINUS
3537           && (! FLOAT_MODE_P (mode)
3538               /* x-y != -(y-x) with IEEE floating point.  */
3539               || TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
3540               || flag_fast_math))
3541         return gen_binary (MINUS, mode, XEXP (XEXP (x, 0), 1),
3542                            XEXP (XEXP (x, 0), 0));
3543
3544       /* (neg (xor A 1)) is (plus A -1) if A is known to be either 0 or 1.  */
3545       if (GET_CODE (XEXP (x, 0)) == XOR && XEXP (XEXP (x, 0), 1) == const1_rtx
3546           && nonzero_bits (XEXP (XEXP (x, 0), 0), mode) == 1)
3547         return gen_binary (PLUS, mode, XEXP (XEXP (x, 0), 0), constm1_rtx);
3548
3549       /* NEG commutes with ASHIFT since it is multiplication.  Only do this
3550          if we can then eliminate the NEG (e.g.,
3551          if the operand is a constant).  */
3552
3553       if (GET_CODE (XEXP (x, 0)) == ASHIFT)
3554         {
3555           temp = simplify_unary_operation (NEG, mode,
3556                                            XEXP (XEXP (x, 0), 0), mode);
3557           if (temp)
3558             {
3559               SUBST (XEXP (XEXP (x, 0), 0), temp);
3560               return XEXP (x, 0);
3561             }
3562         }
3563
3564       temp = expand_compound_operation (XEXP (x, 0));
3565
3566       /* For C equal to the width of MODE minus 1, (neg (ashiftrt X C)) can be
3567          replaced by (lshiftrt X C).  This will convert
3568          (neg (sign_extract X 1 Y)) to (zero_extract X 1 Y).  */
3569
3570       if (GET_CODE (temp) == ASHIFTRT
3571           && GET_CODE (XEXP (temp, 1)) == CONST_INT
3572           && INTVAL (XEXP (temp, 1)) == GET_MODE_BITSIZE (mode) - 1)
3573         return simplify_shift_const (temp, LSHIFTRT, mode, XEXP (temp, 0),
3574                                      INTVAL (XEXP (temp, 1)));
3575
3576       /* If X has only a single bit that might be nonzero, say, bit I, convert
3577          (neg X) to (ashiftrt (ashift X C-I) C-I) where C is the bitsize of
3578          MODE minus 1.  This will convert (neg (zero_extract X 1 Y)) to
3579          (sign_extract X 1 Y).  But only do this if TEMP isn't a register
3580          or a SUBREG of one since we'd be making the expression more
3581          complex if it was just a register.  */
3582
3583       if (GET_CODE (temp) != REG
3584           && ! (GET_CODE (temp) == SUBREG
3585                 && GET_CODE (SUBREG_REG (temp)) == REG)
3586           && (i = exact_log2 (nonzero_bits (temp, mode))) >= 0)
3587         {
3588           rtx temp1 = simplify_shift_const
3589             (NULL_RTX, ASHIFTRT, mode,
3590              simplify_shift_const (NULL_RTX, ASHIFT, mode, temp,
3591                                    GET_MODE_BITSIZE (mode) - 1 - i),
3592              GET_MODE_BITSIZE (mode) - 1 - i);
3593
3594           /* If all we did was surround TEMP with the two shifts, we
3595              haven't improved anything, so don't use it.  Otherwise,
3596              we are better off with TEMP1.  */
3597           if (GET_CODE (temp1) != ASHIFTRT
3598               || GET_CODE (XEXP (temp1, 0)) != ASHIFT
3599               || XEXP (XEXP (temp1, 0), 0) != temp)
3600             return temp1;
3601         }
3602       break;
3603
3604     case TRUNCATE:
3605       /* We can't handle truncation to a partial integer mode here
3606          because we don't know the real bitsize of the partial
3607          integer mode.  */
3608       if (GET_MODE_CLASS (mode) == MODE_PARTIAL_INT)
3609         break;
3610
3611       if (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT)
3612         SUBST (XEXP (x, 0),
3613                force_to_mode (XEXP (x, 0), GET_MODE (XEXP (x, 0)),
3614                               GET_MODE_MASK (mode), NULL_RTX, 0));
3615
3616       /* (truncate:SI ({sign,zero}_extend:DI foo:SI)) == foo:SI.  */
3617       if ((GET_CODE (XEXP (x, 0)) == SIGN_EXTEND
3618            || GET_CODE (XEXP (x, 0)) == ZERO_EXTEND)
3619           && GET_MODE (XEXP (XEXP (x, 0), 0)) == mode)
3620         return XEXP (XEXP (x, 0), 0);
3621
3622       /* (truncate:SI (OP:DI ({sign,zero}_extend:DI foo:SI))) is
3623          (OP:SI foo:SI) if OP is NEG or ABS.  */
3624       if ((GET_CODE (XEXP (x, 0)) == ABS
3625            || GET_CODE (XEXP (x, 0)) == NEG)
3626           && (GET_CODE (XEXP (XEXP (x, 0), 0)) == SIGN_EXTEND
3627               || GET_CODE (XEXP (XEXP (x, 0), 0)) == ZERO_EXTEND)
3628           && GET_MODE (XEXP (XEXP (XEXP (x, 0), 0), 0)) == mode)
3629         return gen_unary (GET_CODE (XEXP (x, 0)), mode, mode,
3630                           XEXP (XEXP (XEXP (x, 0), 0), 0));
3631
3632       /* (truncate:SI (subreg:DI (truncate:SI X) 0)) is
3633          (truncate:SI x).  */
3634       if (GET_CODE (XEXP (x, 0)) == SUBREG
3635           && GET_CODE (SUBREG_REG (XEXP (x, 0))) == TRUNCATE
3636           && subreg_lowpart_p (XEXP (x, 0)))
3637         return SUBREG_REG (XEXP (x, 0));
3638
3639       /* If we know that the value is already truncated, we can
3640          replace the TRUNCATE with a SUBREG.  */
3641       if (GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0))) <= HOST_BITS_PER_WIDE_INT
3642           && (nonzero_bits (XEXP (x, 0), GET_MODE (XEXP (x, 0)))
3643               &~ GET_MODE_MASK (mode)) == 0)
3644         return gen_lowpart_for_combine (mode, XEXP (x, 0));
3645
3646       /* A truncate of a comparison can be replaced with a subreg if
3647          STORE_FLAG_VALUE permits.  This is like the previous test,
3648          but it works even if the comparison is done in a mode larger
3649          than HOST_BITS_PER_WIDE_INT.  */
3650       if (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT
3651           && GET_RTX_CLASS (GET_CODE (XEXP (x, 0))) == '<'
3652           && ((HOST_WIDE_INT) STORE_FLAG_VALUE &~ GET_MODE_MASK (mode)) == 0)
3653         return gen_lowpart_for_combine (mode, XEXP (x, 0));
3654
3655       /* Similarly, a truncate of a register whose value is a
3656          comparison can be replaced with a subreg if STORE_FLAG_VALUE
3657          permits.  */
3658       if (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT
3659           && ((HOST_WIDE_INT) STORE_FLAG_VALUE &~ GET_MODE_MASK (mode)) == 0
3660           && (temp = get_last_value (XEXP (x, 0)))
3661           && GET_RTX_CLASS (GET_CODE (temp)) == '<')
3662         return gen_lowpart_for_combine (mode, XEXP (x, 0));
3663
3664       break;
3665
3666     case FLOAT_TRUNCATE:
3667       /* (float_truncate:SF (float_extend:DF foo:SF)) = foo:SF.  */
3668       if (GET_CODE (XEXP (x, 0)) == FLOAT_EXTEND
3669           && GET_MODE (XEXP (XEXP (x, 0), 0)) == mode)
3670         return XEXP (XEXP (x, 0), 0);
3671
3672       /* (float_truncate:SF (OP:DF (float_extend:DF foo:sf))) is
3673          (OP:SF foo:SF) if OP is NEG or ABS.  */
3674       if ((GET_CODE (XEXP (x, 0)) == ABS
3675            || GET_CODE (XEXP (x, 0)) == NEG)
3676           && GET_CODE (XEXP (XEXP (x, 0), 0)) == FLOAT_EXTEND
3677           && GET_MODE (XEXP (XEXP (XEXP (x, 0), 0), 0)) == mode)
3678         return gen_unary (GET_CODE (XEXP (x, 0)), mode, mode,
3679                           XEXP (XEXP (XEXP (x, 0), 0), 0));
3680
3681       /* (float_truncate:SF (subreg:DF (float_truncate:SF X) 0))
3682          is (float_truncate:SF x).  */
3683       if (GET_CODE (XEXP (x, 0)) == SUBREG
3684           && subreg_lowpart_p (XEXP (x, 0))
3685           && GET_CODE (SUBREG_REG (XEXP (x, 0))) == FLOAT_TRUNCATE)
3686         return SUBREG_REG (XEXP (x, 0));
3687       break;
3688
3689 #ifdef HAVE_cc0
3690     case COMPARE:
3691       /* Convert (compare FOO (const_int 0)) to FOO unless we aren't
3692          using cc0, in which case we want to leave it as a COMPARE
3693          so we can distinguish it from a register-register-copy.  */
3694       if (XEXP (x, 1) == const0_rtx)
3695         return XEXP (x, 0);
3696
3697       /* In IEEE floating point, x-0 is not the same as x.  */
3698       if ((TARGET_FLOAT_FORMAT != IEEE_FLOAT_FORMAT
3699            || ! FLOAT_MODE_P (GET_MODE (XEXP (x, 0)))
3700            || flag_fast_math)
3701           && XEXP (x, 1) == CONST0_RTX (GET_MODE (XEXP (x, 0))))
3702         return XEXP (x, 0);
3703       break;
3704 #endif
3705
3706     case CONST:
3707       /* (const (const X)) can become (const X).  Do it this way rather than
3708          returning the inner CONST since CONST can be shared with a
3709          REG_EQUAL note.  */
3710       if (GET_CODE (XEXP (x, 0)) == CONST)
3711         SUBST (XEXP (x, 0), XEXP (XEXP (x, 0), 0));
3712       break;
3713
3714 #ifdef HAVE_lo_sum
3715     case LO_SUM:
3716       /* Convert (lo_sum (high FOO) FOO) to FOO.  This is necessary so we
3717          can add in an offset.  find_split_point will split this address up
3718          again if it doesn't match.  */
3719       if (GET_CODE (XEXP (x, 0)) == HIGH
3720           && rtx_equal_p (XEXP (XEXP (x, 0), 0), XEXP (x, 1)))
3721         return XEXP (x, 1);
3722       break;
3723 #endif
3724
3725     case PLUS:
3726       /* If we have (plus (plus (A const) B)), associate it so that CONST is
3727          outermost.  That's because that's the way indexed addresses are
3728          supposed to appear.  This code used to check many more cases, but
3729          they are now checked elsewhere.  */
3730       if (GET_CODE (XEXP (x, 0)) == PLUS
3731           && CONSTANT_ADDRESS_P (XEXP (XEXP (x, 0), 1)))
3732         return gen_binary (PLUS, mode,
3733                            gen_binary (PLUS, mode, XEXP (XEXP (x, 0), 0),
3734                                        XEXP (x, 1)),
3735                            XEXP (XEXP (x, 0), 1));
3736
3737       /* (plus (xor (and <foo> (const_int pow2 - 1)) <c>) <-c>)
3738          when c is (const_int (pow2 + 1) / 2) is a sign extension of a
3739          bit-field and can be replaced by either a sign_extend or a
3740          sign_extract.  The `and' may be a zero_extend.  */
3741       if (GET_CODE (XEXP (x, 0)) == XOR
3742           && GET_CODE (XEXP (x, 1)) == CONST_INT
3743           && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
3744           && INTVAL (XEXP (x, 1)) == - INTVAL (XEXP (XEXP (x, 0), 1))
3745           && (i = exact_log2 (INTVAL (XEXP (XEXP (x, 0), 1)))) >= 0
3746           && GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT
3747           && ((GET_CODE (XEXP (XEXP (x, 0), 0)) == AND
3748                && GET_CODE (XEXP (XEXP (XEXP (x, 0), 0), 1)) == CONST_INT
3749                && (INTVAL (XEXP (XEXP (XEXP (x, 0), 0), 1))
3750                    == ((HOST_WIDE_INT) 1 << (i + 1)) - 1))
3751               || (GET_CODE (XEXP (XEXP (x, 0), 0)) == ZERO_EXTEND
3752                   && (GET_MODE_BITSIZE (GET_MODE (XEXP (XEXP (XEXP (x, 0), 0), 0)))
3753                       == i + 1))))
3754         return simplify_shift_const
3755           (NULL_RTX, ASHIFTRT, mode,
3756            simplify_shift_const (NULL_RTX, ASHIFT, mode,
3757                                  XEXP (XEXP (XEXP (x, 0), 0), 0),
3758                                  GET_MODE_BITSIZE (mode) - (i + 1)),
3759            GET_MODE_BITSIZE (mode) - (i + 1));
3760
3761       /* (plus (comparison A B) C) can become (neg (rev-comp A B)) if
3762          C is 1 and STORE_FLAG_VALUE is -1 or if C is -1