OSDN Git Service

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