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