gcc/combine.c

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