OSDN Git Service

* rtl.h (remove_reg_equal_equiv_notes): New prototype.
[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   /* For notes, be conservative and simply remove them.  */
1730   remove_reg_equal_equiv_notes (insn);
1731
1732   /* The new insn will have a destination that was previously the destination
1733      of an insn just above it.  Call distribute_links to make a LOG_LINK from
1734      the next use of that destination.  */
1735   distribute_links (gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX));
1736 }
1737
1738 /* Return TRUE if combine can reuse reg X in mode MODE.
1739    ADDED_SETS is nonzero if the original set is still required.  */
1740 static bool
1741 can_change_dest_mode (rtx x, int added_sets, enum machine_mode mode)
1742 {
1743   unsigned int regno;
1744
1745   if (!REG_P(x))
1746     return false;
1747
1748   regno = REGNO (x);
1749   /* Allow hard registers if the new mode is legal, and occupies no more
1750      registers than the old mode.  */
1751   if (regno < FIRST_PSEUDO_REGISTER)
1752     return (HARD_REGNO_MODE_OK (regno, mode)
1753             && (hard_regno_nregs[regno][GET_MODE (x)]
1754                 >= hard_regno_nregs[regno][mode]));
1755
1756   /* Or a pseudo that is only used once.  */
1757   return (REG_N_SETS (regno) == 1 && !added_sets
1758           && !REG_USERVAR_P (x));
1759 }
1760
1761
1762 /* Check whether X, the destination of a set, refers to part of
1763    the register specified by REG.  */
1764
1765 static bool
1766 reg_subword_p (rtx x, rtx reg)
1767 {
1768   /* Check that reg is an integer mode register.  */
1769   if (!REG_P (reg) || GET_MODE_CLASS (GET_MODE (reg)) != MODE_INT)
1770     return false;
1771
1772   if (GET_CODE (x) == STRICT_LOW_PART
1773       || GET_CODE (x) == ZERO_EXTRACT)
1774     x = XEXP (x, 0);
1775
1776   return GET_CODE (x) == SUBREG
1777          && SUBREG_REG (x) == reg
1778          && GET_MODE_CLASS (GET_MODE (x)) == MODE_INT;
1779 }
1780
1781
1782 /* Try to combine the insns I1 and I2 into I3.
1783    Here I1 and I2 appear earlier than I3.
1784    I1 can be zero; then we combine just I2 into I3.
1785
1786    If we are combining three insns and the resulting insn is not recognized,
1787    try splitting it into two insns.  If that happens, I2 and I3 are retained
1788    and I1 is pseudo-deleted by turning it into a NOTE.  Otherwise, I1 and I2
1789    are pseudo-deleted.
1790
1791    Return 0 if the combination does not work.  Then nothing is changed.
1792    If we did the combination, return the insn at which combine should
1793    resume scanning.
1794
1795    Set NEW_DIRECT_JUMP_P to a nonzero value if try_combine creates a
1796    new direct jump instruction.  */
1797
1798 static rtx
1799 try_combine (rtx i3, rtx i2, rtx i1, int *new_direct_jump_p)
1800 {
1801   /* New patterns for I3 and I2, respectively.  */
1802   rtx newpat, newi2pat = 0;
1803   rtvec newpat_vec_with_clobbers = 0;
1804   int substed_i2 = 0, substed_i1 = 0;
1805   /* Indicates need to preserve SET in I1 or I2 in I3 if it is not dead.  */
1806   int added_sets_1, added_sets_2;
1807   /* Total number of SETs to put into I3.  */
1808   int total_sets;
1809   /* Nonzero if I2's body now appears in I3.  */
1810   int i2_is_used;
1811   /* INSN_CODEs for new I3, new I2, and user of condition code.  */
1812   int insn_code_number, i2_code_number = 0, other_code_number = 0;
1813   /* Contains I3 if the destination of I3 is used in its source, which means
1814      that the old life of I3 is being killed.  If that usage is placed into
1815      I2 and not in I3, a REG_DEAD note must be made.  */
1816   rtx i3dest_killed = 0;
1817   /* SET_DEST and SET_SRC of I2 and I1.  */
1818   rtx i2dest, i2src, i1dest = 0, i1src = 0;
1819   /* PATTERN (I1) and PATTERN (I2), or a copy of it in certain cases.  */
1820   rtx i1pat = 0, i2pat = 0;
1821   /* Indicates if I2DEST or I1DEST is in I2SRC or I1_SRC.  */
1822   int i2dest_in_i2src = 0, i1dest_in_i1src = 0, i2dest_in_i1src = 0;
1823   int i2dest_killed = 0, i1dest_killed = 0;
1824   int i1_feeds_i3 = 0;
1825   /* Notes that must be added to REG_NOTES in I3 and I2.  */
1826   rtx new_i3_notes, new_i2_notes;
1827   /* Notes that we substituted I3 into I2 instead of the normal case.  */
1828   int i3_subst_into_i2 = 0;
1829   /* Notes that I1, I2 or I3 is a MULT operation.  */
1830   int have_mult = 0;
1831   int swap_i2i3 = 0;
1832
1833   int maxreg;
1834   rtx temp;
1835   rtx link;
1836   int i;
1837
1838   /* Exit early if one of the insns involved can't be used for
1839      combinations.  */
1840   if (cant_combine_insn_p (i3)
1841       || cant_combine_insn_p (i2)
1842       || (i1 && cant_combine_insn_p (i1))
1843       || likely_spilled_retval_p (i3)
1844       /* We also can't do anything if I3 has a
1845          REG_LIBCALL note since we don't want to disrupt the contiguity of a
1846          libcall.  */
1847 #if 0
1848       /* ??? This gives worse code, and appears to be unnecessary, since no
1849          pass after flow uses REG_LIBCALL/REG_RETVAL notes.  */
1850       || find_reg_note (i3, REG_LIBCALL, NULL_RTX)
1851 #endif
1852       )
1853     return 0;
1854
1855   combine_attempts++;
1856   undobuf.other_insn = 0;
1857
1858   /* Reset the hard register usage information.  */
1859   CLEAR_HARD_REG_SET (newpat_used_regs);
1860
1861   /* If I1 and I2 both feed I3, they can be in any order.  To simplify the
1862      code below, set I1 to be the earlier of the two insns.  */
1863   if (i1 && INSN_CUID (i1) > INSN_CUID (i2))
1864     temp = i1, i1 = i2, i2 = temp;
1865
1866   added_links_insn = 0;
1867
1868   /* First check for one important special-case that the code below will
1869      not handle.  Namely, the case where I1 is zero, I2 is a PARALLEL
1870      and I3 is a SET whose SET_SRC is a SET_DEST in I2.  In that case,
1871      we may be able to replace that destination with the destination of I3.
1872      This occurs in the common code where we compute both a quotient and
1873      remainder into a structure, in which case we want to do the computation
1874      directly into the structure to avoid register-register copies.
1875
1876      Note that this case handles both multiple sets in I2 and also
1877      cases where I2 has a number of CLOBBER or PARALLELs.
1878
1879      We make very conservative checks below and only try to handle the
1880      most common cases of this.  For example, we only handle the case
1881      where I2 and I3 are adjacent to avoid making difficult register
1882      usage tests.  */
1883
1884   if (i1 == 0 && NONJUMP_INSN_P (i3) && GET_CODE (PATTERN (i3)) == SET
1885       && REG_P (SET_SRC (PATTERN (i3)))
1886       && REGNO (SET_SRC (PATTERN (i3))) >= FIRST_PSEUDO_REGISTER
1887       && find_reg_note (i3, REG_DEAD, SET_SRC (PATTERN (i3)))
1888       && GET_CODE (PATTERN (i2)) == PARALLEL
1889       && ! side_effects_p (SET_DEST (PATTERN (i3)))
1890       /* If the dest of I3 is a ZERO_EXTRACT or STRICT_LOW_PART, the code
1891          below would need to check what is inside (and reg_overlap_mentioned_p
1892          doesn't support those codes anyway).  Don't allow those destinations;
1893          the resulting insn isn't likely to be recognized anyway.  */
1894       && GET_CODE (SET_DEST (PATTERN (i3))) != ZERO_EXTRACT
1895       && GET_CODE (SET_DEST (PATTERN (i3))) != STRICT_LOW_PART
1896       && ! reg_overlap_mentioned_p (SET_SRC (PATTERN (i3)),
1897                                     SET_DEST (PATTERN (i3)))
1898       && next_real_insn (i2) == i3)
1899     {
1900       rtx p2 = PATTERN (i2);
1901
1902       /* Make sure that the destination of I3,
1903          which we are going to substitute into one output of I2,
1904          is not used within another output of I2.  We must avoid making this:
1905          (parallel [(set (mem (reg 69)) ...)
1906                     (set (reg 69) ...)])
1907          which is not well-defined as to order of actions.
1908          (Besides, reload can't handle output reloads for this.)
1909
1910          The problem can also happen if the dest of I3 is a memory ref,
1911          if another dest in I2 is an indirect memory ref.  */
1912       for (i = 0; i < XVECLEN (p2, 0); i++)
1913         if ((GET_CODE (XVECEXP (p2, 0, i)) == SET
1914              || GET_CODE (XVECEXP (p2, 0, i)) == CLOBBER)
1915             && reg_overlap_mentioned_p (SET_DEST (PATTERN (i3)),
1916                                         SET_DEST (XVECEXP (p2, 0, i))))
1917           break;
1918
1919       if (i == XVECLEN (p2, 0))
1920         for (i = 0; i < XVECLEN (p2, 0); i++)
1921           if ((GET_CODE (XVECEXP (p2, 0, i)) == SET
1922                || GET_CODE (XVECEXP (p2, 0, i)) == CLOBBER)
1923               && SET_DEST (XVECEXP (p2, 0, i)) == SET_SRC (PATTERN (i3)))
1924             {
1925               combine_merges++;
1926
1927               subst_insn = i3;
1928               subst_low_cuid = INSN_CUID (i2);
1929
1930               added_sets_2 = added_sets_1 = 0;
1931               i2dest = SET_SRC (PATTERN (i3));
1932               i2dest_killed = dead_or_set_p (i2, i2dest);
1933
1934               /* Replace the dest in I2 with our dest and make the resulting
1935                  insn the new pattern for I3.  Then skip to where we
1936                  validate the pattern.  Everything was set up above.  */
1937               SUBST (SET_DEST (XVECEXP (p2, 0, i)),
1938                      SET_DEST (PATTERN (i3)));
1939
1940               newpat = p2;
1941               i3_subst_into_i2 = 1;
1942               goto validate_replacement;
1943             }
1944     }
1945
1946   /* If I2 is setting a pseudo to a constant and I3 is setting some
1947      sub-part of it to another constant, merge them by making a new
1948      constant.  */
1949   if (i1 == 0
1950       && (temp = single_set (i2)) != 0
1951       && (GET_CODE (SET_SRC (temp)) == CONST_INT
1952           || GET_CODE (SET_SRC (temp)) == CONST_DOUBLE)
1953       && GET_CODE (PATTERN (i3)) == SET
1954       && (GET_CODE (SET_SRC (PATTERN (i3))) == CONST_INT
1955           || GET_CODE (SET_SRC (PATTERN (i3))) == CONST_DOUBLE)
1956       && reg_subword_p (SET_DEST (PATTERN (i3)), SET_DEST (temp)))
1957     {
1958       rtx dest = SET_DEST (PATTERN (i3));
1959       int offset = -1;
1960       int width = 0;
1961
1962       if (GET_CODE (dest) == ZERO_EXTRACT)
1963         {
1964           if (GET_CODE (XEXP (dest, 1)) == CONST_INT
1965               && GET_CODE (XEXP (dest, 2)) == CONST_INT)
1966             {
1967               width = INTVAL (XEXP (dest, 1));
1968               offset = INTVAL (XEXP (dest, 2));
1969               dest = XEXP (dest, 0);
1970               if (BITS_BIG_ENDIAN)
1971                 offset = GET_MODE_BITSIZE (GET_MODE (dest)) - width - offset;
1972             }
1973         }
1974       else
1975         {
1976           if (GET_CODE (dest) == STRICT_LOW_PART)
1977             dest = XEXP (dest, 0);
1978           width = GET_MODE_BITSIZE (GET_MODE (dest));
1979           offset = 0;
1980         }
1981
1982       if (offset >= 0)
1983         {
1984           /* If this is the low part, we're done.  */
1985           if (subreg_lowpart_p (dest))
1986             ;
1987           /* Handle the case where inner is twice the size of outer.  */
1988           else if (GET_MODE_BITSIZE (GET_MODE (SET_DEST (temp)))
1989                    == 2 * GET_MODE_BITSIZE (GET_MODE (dest)))
1990             offset += GET_MODE_BITSIZE (GET_MODE (dest));
1991           /* Otherwise give up for now.  */
1992           else
1993             offset = -1;
1994         }
1995
1996       if (offset >= 0
1997           && (GET_MODE_BITSIZE (GET_MODE (SET_DEST (temp)))
1998               <= HOST_BITS_PER_WIDE_INT * 2))
1999         {
2000           HOST_WIDE_INT mhi, ohi, ihi;
2001           HOST_WIDE_INT mlo, olo, ilo;
2002           rtx inner = SET_SRC (PATTERN (i3));
2003           rtx outer = SET_SRC (temp);
2004
2005           if (GET_CODE (outer) == CONST_INT)
2006             {
2007               olo = INTVAL (outer);
2008               ohi = olo < 0 ? -1 : 0;
2009             }
2010           else
2011             {
2012               olo = CONST_DOUBLE_LOW (outer);
2013               ohi = CONST_DOUBLE_HIGH (outer);
2014             }
2015
2016           if (GET_CODE (inner) == CONST_INT)
2017             {
2018               ilo = INTVAL (inner);
2019               ihi = ilo < 0 ? -1 : 0;
2020             }
2021           else
2022             {
2023               ilo = CONST_DOUBLE_LOW (inner);
2024               ihi = CONST_DOUBLE_HIGH (inner);
2025             }
2026
2027           if (width < HOST_BITS_PER_WIDE_INT)
2028             {
2029               mlo = ((unsigned HOST_WIDE_INT) 1 << width) - 1;
2030               mhi = 0;
2031             }
2032           else if (width < HOST_BITS_PER_WIDE_INT * 2)
2033             {
2034               mhi = ((unsigned HOST_WIDE_INT) 1
2035                      << (width - HOST_BITS_PER_WIDE_INT)) - 1;
2036               mlo = -1;
2037             }
2038           else
2039             {
2040               mlo = -1;
2041               mhi = -1;
2042             }
2043
2044           ilo &= mlo;
2045           ihi &= mhi;
2046
2047           if (offset >= HOST_BITS_PER_WIDE_INT)
2048             {
2049               mhi = mlo << (offset - HOST_BITS_PER_WIDE_INT);
2050               mlo = 0;
2051               ihi = ilo << (offset - HOST_BITS_PER_WIDE_INT);
2052               ilo = 0;
2053             }
2054           else if (offset > 0)
2055             {
2056               mhi = (mhi << offset) | ((unsigned HOST_WIDE_INT) mlo
2057                                        >> (HOST_BITS_PER_WIDE_INT - offset));
2058               mlo = mlo << offset;
2059               ihi = (ihi << offset) | ((unsigned HOST_WIDE_INT) ilo
2060                                        >> (HOST_BITS_PER_WIDE_INT - offset));
2061               ilo = ilo << offset;
2062             }
2063
2064           olo = (olo & ~mlo) | ilo;
2065           ohi = (ohi & ~mhi) | ihi;
2066
2067           combine_merges++;
2068           subst_insn = i3;
2069           subst_low_cuid = INSN_CUID (i2);
2070           added_sets_2 = added_sets_1 = 0;
2071           i2dest = SET_DEST (temp);
2072           i2dest_killed = dead_or_set_p (i2, i2dest);
2073
2074           SUBST (SET_SRC (temp),
2075                  immed_double_const (olo, ohi, GET_MODE (SET_DEST (temp))));
2076
2077           newpat = PATTERN (i2);
2078           goto validate_replacement;
2079         }
2080     }
2081
2082 #ifndef HAVE_cc0
2083   /* If we have no I1 and I2 looks like:
2084         (parallel [(set (reg:CC X) (compare:CC OP (const_int 0)))
2085                    (set Y OP)])
2086      make up a dummy I1 that is
2087         (set Y OP)
2088      and change I2 to be
2089         (set (reg:CC X) (compare:CC Y (const_int 0)))
2090
2091      (We can ignore any trailing CLOBBERs.)
2092
2093      This undoes a previous combination and allows us to match a branch-and-
2094      decrement insn.  */
2095
2096   if (i1 == 0 && GET_CODE (PATTERN (i2)) == PARALLEL
2097       && XVECLEN (PATTERN (i2), 0) >= 2
2098       && GET_CODE (XVECEXP (PATTERN (i2), 0, 0)) == SET
2099       && (GET_MODE_CLASS (GET_MODE (SET_DEST (XVECEXP (PATTERN (i2), 0, 0))))
2100           == MODE_CC)
2101       && GET_CODE (SET_SRC (XVECEXP (PATTERN (i2), 0, 0))) == COMPARE
2102       && XEXP (SET_SRC (XVECEXP (PATTERN (i2), 0, 0)), 1) == const0_rtx
2103       && GET_CODE (XVECEXP (PATTERN (i2), 0, 1)) == SET
2104       && REG_P (SET_DEST (XVECEXP (PATTERN (i2), 0, 1)))
2105       && rtx_equal_p (XEXP (SET_SRC (XVECEXP (PATTERN (i2), 0, 0)), 0),
2106                       SET_SRC (XVECEXP (PATTERN (i2), 0, 1))))
2107     {
2108       for (i = XVECLEN (PATTERN (i2), 0) - 1; i >= 2; i--)
2109         if (GET_CODE (XVECEXP (PATTERN (i2), 0, i)) != CLOBBER)
2110           break;
2111
2112       if (i == 1)
2113         {
2114           /* We make I1 with the same INSN_UID as I2.  This gives it
2115              the same INSN_CUID for value tracking.  Our fake I1 will
2116              never appear in the insn stream so giving it the same INSN_UID
2117              as I2 will not cause a problem.  */
2118
2119           i1 = gen_rtx_INSN (VOIDmode, INSN_UID (i2), NULL_RTX, i2,
2120                              BLOCK_FOR_INSN (i2), INSN_LOCATOR (i2),
2121                              XVECEXP (PATTERN (i2), 0, 1), -1, NULL_RTX,
2122                              NULL_RTX);
2123
2124           SUBST (PATTERN (i2), XVECEXP (PATTERN (i2), 0, 0));
2125           SUBST (XEXP (SET_SRC (PATTERN (i2)), 0),
2126                  SET_DEST (PATTERN (i1)));
2127         }
2128     }
2129 #endif
2130
2131   /* Verify that I2 and I1 are valid for combining.  */
2132   if (! can_combine_p (i2, i3, i1, NULL_RTX, &i2dest, &i2src)
2133       || (i1 && ! can_combine_p (i1, i3, NULL_RTX, i2, &i1dest, &i1src)))
2134     {
2135       undo_all ();
2136       return 0;
2137     }
2138
2139   /* Record whether I2DEST is used in I2SRC and similarly for the other
2140      cases.  Knowing this will help in register status updating below.  */
2141   i2dest_in_i2src = reg_overlap_mentioned_p (i2dest, i2src);
2142   i1dest_in_i1src = i1 && reg_overlap_mentioned_p (i1dest, i1src);
2143   i2dest_in_i1src = i1 && reg_overlap_mentioned_p (i2dest, i1src);
2144   i2dest_killed = dead_or_set_p (i2, i2dest);
2145   i1dest_killed = i1 && dead_or_set_p (i1, i1dest);
2146
2147   /* See if I1 directly feeds into I3.  It does if I1DEST is not used
2148      in I2SRC.  */
2149   i1_feeds_i3 = i1 && ! reg_overlap_mentioned_p (i1dest, i2src);
2150
2151   /* Ensure that I3's pattern can be the destination of combines.  */
2152   if (! combinable_i3pat (i3, &PATTERN (i3), i2dest, i1dest,
2153                           i1 && i2dest_in_i1src && i1_feeds_i3,
2154                           &i3dest_killed))
2155     {
2156       undo_all ();
2157       return 0;
2158     }
2159
2160   /* See if any of the insns is a MULT operation.  Unless one is, we will
2161      reject a combination that is, since it must be slower.  Be conservative
2162      here.  */
2163   if (GET_CODE (i2src) == MULT
2164       || (i1 != 0 && GET_CODE (i1src) == MULT)
2165       || (GET_CODE (PATTERN (i3)) == SET
2166           && GET_CODE (SET_SRC (PATTERN (i3))) == MULT))
2167     have_mult = 1;
2168
2169   /* If I3 has an inc, then give up if I1 or I2 uses the reg that is inc'd.
2170      We used to do this EXCEPT in one case: I3 has a post-inc in an
2171      output operand.  However, that exception can give rise to insns like
2172         mov r3,(r3)+
2173      which is a famous insn on the PDP-11 where the value of r3 used as the
2174      source was model-dependent.  Avoid this sort of thing.  */
2175
2176 #if 0
2177   if (!(GET_CODE (PATTERN (i3)) == SET
2178         && REG_P (SET_SRC (PATTERN (i3)))
2179         && MEM_P (SET_DEST (PATTERN (i3)))
2180         && (GET_CODE (XEXP (SET_DEST (PATTERN (i3)), 0)) == POST_INC
2181             || GET_CODE (XEXP (SET_DEST (PATTERN (i3)), 0)) == POST_DEC)))
2182     /* It's not the exception.  */
2183 #endif
2184 #ifdef AUTO_INC_DEC
2185     for (link = REG_NOTES (i3); link; link = XEXP (link, 1))
2186       if (REG_NOTE_KIND (link) == REG_INC
2187           && (reg_overlap_mentioned_p (XEXP (link, 0), PATTERN (i2))
2188               || (i1 != 0
2189                   && reg_overlap_mentioned_p (XEXP (link, 0), PATTERN (i1)))))
2190         {
2191           undo_all ();
2192           return 0;
2193         }
2194 #endif
2195
2196   /* See if the SETs in I1 or I2 need to be kept around in the merged
2197      instruction: whenever the value set there is still needed past I3.
2198      For the SETs in I2, this is easy: we see if I2DEST dies or is set in I3.
2199
2200      For the SET in I1, we have two cases:  If I1 and I2 independently
2201      feed into I3, the set in I1 needs to be kept around if I1DEST dies
2202      or is set in I3.  Otherwise (if I1 feeds I2 which feeds I3), the set
2203      in I1 needs to be kept around unless I1DEST dies or is set in either
2204      I2 or I3.  We can distinguish these cases by seeing if I2SRC mentions
2205      I1DEST.  If so, we know I1 feeds into I2.  */
2206
2207   added_sets_2 = ! dead_or_set_p (i3, i2dest);
2208
2209   added_sets_1
2210     = i1 && ! (i1_feeds_i3 ? dead_or_set_p (i3, i1dest)
2211                : (dead_or_set_p (i3, i1dest) || dead_or_set_p (i2, i1dest)));
2212
2213   /* If the set in I2 needs to be kept around, we must make a copy of
2214      PATTERN (I2), so that when we substitute I1SRC for I1DEST in
2215      PATTERN (I2), we are only substituting for the original I1DEST, not into
2216      an already-substituted copy.  This also prevents making self-referential
2217      rtx.  If I2 is a PARALLEL, we just need the piece that assigns I2SRC to
2218      I2DEST.  */
2219
2220   if (added_sets_2)
2221     {
2222       if (GET_CODE (PATTERN (i2)) == PARALLEL)
2223         i2pat = gen_rtx_SET (VOIDmode, i2dest, copy_rtx (i2src));
2224       else
2225         i2pat = copy_rtx (PATTERN (i2));
2226     }
2227
2228   if (added_sets_1)
2229     {
2230       if (GET_CODE (PATTERN (i1)) == PARALLEL)
2231         i1pat = gen_rtx_SET (VOIDmode, i1dest, copy_rtx (i1src));
2232       else
2233         i1pat = copy_rtx (PATTERN (i1));
2234     }
2235
2236   combine_merges++;
2237
2238   /* Substitute in the latest insn for the regs set by the earlier ones.  */
2239
2240   maxreg = max_reg_num ();
2241
2242   subst_insn = i3;
2243
2244 #ifndef HAVE_cc0
2245   /* Many machines that don't use CC0 have insns that can both perform an
2246      arithmetic operation and set the condition code.  These operations will
2247      be represented as a PARALLEL with the first element of the vector
2248      being a COMPARE of an arithmetic operation with the constant zero.
2249      The second element of the vector will set some pseudo to the result
2250      of the same arithmetic operation.  If we simplify the COMPARE, we won't
2251      match such a pattern and so will generate an extra insn.   Here we test
2252      for this case, where both the comparison and the operation result are
2253      needed, and make the PARALLEL by just replacing I2DEST in I3SRC with
2254      I2SRC.  Later we will make the PARALLEL that contains I2.  */
2255
2256   if (i1 == 0 && added_sets_2 && GET_CODE (PATTERN (i3)) == SET
2257       && GET_CODE (SET_SRC (PATTERN (i3))) == COMPARE
2258       && XEXP (SET_SRC (PATTERN (i3)), 1) == const0_rtx
2259       && rtx_equal_p (XEXP (SET_SRC (PATTERN (i3)), 0), i2dest))
2260     {
2261 #ifdef SELECT_CC_MODE
2262       rtx *cc_use;
2263       enum machine_mode compare_mode;
2264 #endif
2265
2266       newpat = PATTERN (i3);
2267       SUBST (XEXP (SET_SRC (newpat), 0), i2src);
2268
2269       i2_is_used = 1;
2270
2271 #ifdef SELECT_CC_MODE
2272       /* See if a COMPARE with the operand we substituted in should be done
2273          with the mode that is currently being used.  If not, do the same
2274          processing we do in `subst' for a SET; namely, if the destination
2275          is used only once, try to replace it with a register of the proper
2276          mode and also replace the COMPARE.  */
2277       if (undobuf.other_insn == 0
2278           && (cc_use = find_single_use (SET_DEST (newpat), i3,
2279                                         &undobuf.other_insn))
2280           && ((compare_mode = SELECT_CC_MODE (GET_CODE (*cc_use),
2281                                               i2src, const0_rtx))
2282               != GET_MODE (SET_DEST (newpat))))
2283         {
2284           if (can_change_dest_mode(SET_DEST (newpat), added_sets_2,
2285                                    compare_mode))
2286             {
2287               unsigned int regno = REGNO (SET_DEST (newpat));
2288               rtx new_dest;
2289
2290               if (regno < FIRST_PSEUDO_REGISTER)
2291                 new_dest = gen_rtx_REG (compare_mode, regno);
2292               else
2293                 {
2294                   SUBST_MODE (regno_reg_rtx[regno], compare_mode);
2295                   new_dest = regno_reg_rtx[regno];
2296                 }
2297
2298               SUBST (SET_DEST (newpat), new_dest);
2299               SUBST (XEXP (*cc_use, 0), new_dest);
2300               SUBST (SET_SRC (newpat),
2301                      gen_rtx_COMPARE (compare_mode, i2src, const0_rtx));
2302             }
2303           else
2304             undobuf.other_insn = 0;
2305         }
2306 #endif
2307     }
2308   else
2309 #endif
2310     {
2311       /* It is possible that the source of I2 or I1 may be performing
2312          an unneeded operation, such as a ZERO_EXTEND of something
2313          that is known to have the high part zero.  Handle that case
2314          by letting subst look at the innermost one of them.
2315
2316          Another way to do this would be to have a function that tries
2317          to simplify a single insn instead of merging two or more
2318          insns.  We don't do this because of the potential of infinite
2319          loops and because of the potential extra memory required.
2320          However, doing it the way we are is a bit of a kludge and
2321          doesn't catch all cases.
2322
2323          But only do this if -fexpensive-optimizations since it slows
2324          things down and doesn't usually win.
2325
2326          This is not done in the COMPARE case above because the
2327          unmodified I2PAT is used in the PARALLEL and so a pattern
2328          with a modified I2SRC would not match.  */
2329
2330       if (flag_expensive_optimizations)
2331         {
2332           /* Pass pc_rtx so no substitutions are done, just
2333              simplifications.  */
2334           if (i1)
2335             {
2336               subst_low_cuid = INSN_CUID (i1);
2337               i1src = subst (i1src, pc_rtx, pc_rtx, 0, 0);
2338             }
2339           else
2340             {
2341               subst_low_cuid = INSN_CUID (i2);
2342               i2src = subst (i2src, pc_rtx, pc_rtx, 0, 0);
2343             }
2344         }
2345
2346       n_occurrences = 0;                /* `subst' counts here */
2347
2348       /* If I1 feeds into I2 (not into I3) and I1DEST is in I1SRC, we
2349          need to make a unique copy of I2SRC each time we substitute it
2350          to avoid self-referential rtl.  */
2351
2352       subst_low_cuid = INSN_CUID (i2);
2353       newpat = subst (PATTERN (i3), i2dest, i2src, 0,
2354                       ! i1_feeds_i3 && i1dest_in_i1src);
2355       substed_i2 = 1;
2356
2357       /* Record whether i2's body now appears within i3's body.  */
2358       i2_is_used = n_occurrences;
2359     }
2360
2361   /* If we already got a failure, don't try to do more.  Otherwise,
2362      try to substitute in I1 if we have it.  */
2363
2364   if (i1 && GET_CODE (newpat) != CLOBBER)
2365     {
2366       /* Before we can do this substitution, we must redo the test done
2367          above (see detailed comments there) that ensures  that I1DEST
2368          isn't mentioned in any SETs in NEWPAT that are field assignments.  */
2369
2370       if (! combinable_i3pat (NULL_RTX, &newpat, i1dest, NULL_RTX,
2371                               0, (rtx*) 0))
2372         {
2373           undo_all ();
2374           return 0;
2375         }
2376
2377       n_occurrences = 0;
2378       subst_low_cuid = INSN_CUID (i1);
2379       newpat = subst (newpat, i1dest, i1src, 0, 0);
2380       substed_i1 = 1;
2381     }
2382
2383   /* Fail if an autoincrement side-effect has been duplicated.  Be careful
2384      to count all the ways that I2SRC and I1SRC can be used.  */
2385   if ((FIND_REG_INC_NOTE (i2, NULL_RTX) != 0
2386        && i2_is_used + added_sets_2 > 1)
2387       || (i1 != 0 && FIND_REG_INC_NOTE (i1, NULL_RTX) != 0
2388           && (n_occurrences + added_sets_1 + (added_sets_2 && ! i1_feeds_i3)
2389               > 1))
2390       /* Fail if we tried to make a new register.  */
2391       || max_reg_num () != maxreg
2392       /* Fail if we couldn't do something and have a CLOBBER.  */
2393       || GET_CODE (newpat) == CLOBBER
2394       /* Fail if this new pattern is a MULT and we didn't have one before
2395          at the outer level.  */
2396       || (GET_CODE (newpat) == SET && GET_CODE (SET_SRC (newpat)) == MULT
2397           && ! have_mult))
2398     {
2399       undo_all ();
2400       return 0;
2401     }
2402
2403   /* If the actions of the earlier insns must be kept
2404      in addition to substituting them into the latest one,
2405      we must make a new PARALLEL for the latest insn
2406      to hold additional the SETs.  */
2407
2408   if (added_sets_1 || added_sets_2)
2409     {
2410       combine_extras++;
2411
2412       if (GET_CODE (newpat) == PARALLEL)
2413         {
2414           rtvec old = XVEC (newpat, 0);
2415           total_sets = XVECLEN (newpat, 0) + added_sets_1 + added_sets_2;
2416           newpat = gen_rtx_PARALLEL (VOIDmode, rtvec_alloc (total_sets));
2417           memcpy (XVEC (newpat, 0)->elem, &old->elem[0],
2418                   sizeof (old->elem[0]) * old->num_elem);
2419         }
2420       else
2421         {
2422           rtx old = newpat;
2423           total_sets = 1 + added_sets_1 + added_sets_2;
2424           newpat = gen_rtx_PARALLEL (VOIDmode, rtvec_alloc (total_sets));
2425           XVECEXP (newpat, 0, 0) = old;
2426         }
2427
2428       if (added_sets_1)
2429         XVECEXP (newpat, 0, --total_sets) = i1pat;
2430
2431       if (added_sets_2)
2432         {
2433           /* If there is no I1, use I2's body as is.  We used to also not do
2434              the subst call below if I2 was substituted into I3,
2435              but that could lose a simplification.  */
2436           if (i1 == 0)
2437             XVECEXP (newpat, 0, --total_sets) = i2pat;
2438           else
2439             /* See comment where i2pat is assigned.  */
2440             XVECEXP (newpat, 0, --total_sets)
2441               = subst (i2pat, i1dest, i1src, 0, 0);
2442         }
2443     }
2444
2445   /* We come here when we are replacing a destination in I2 with the
2446      destination of I3.  */
2447  validate_replacement:
2448
2449   /* Note which hard regs this insn has as inputs.  */
2450   mark_used_regs_combine (newpat);
2451
2452   /* If recog_for_combine fails, it strips existing clobbers.  If we'll
2453      consider splitting this pattern, we might need these clobbers.  */
2454   if (i1 && GET_CODE (newpat) == PARALLEL
2455       && GET_CODE (XVECEXP (newpat, 0, XVECLEN (newpat, 0) - 1)) == CLOBBER)
2456     {
2457       int len = XVECLEN (newpat, 0);
2458
2459       newpat_vec_with_clobbers = rtvec_alloc (len);
2460       for (i = 0; i < len; i++)
2461         RTVEC_ELT (newpat_vec_with_clobbers, i) = XVECEXP (newpat, 0, i);
2462     }
2463
2464   /* Is the result of combination a valid instruction?  */
2465   insn_code_number = recog_for_combine (&newpat, i3, &new_i3_notes);
2466
2467   /* If the result isn't valid, see if it is a PARALLEL of two SETs where
2468      the second SET's destination is a register that is unused and isn't
2469      marked as an instruction that might trap in an EH region.  In that case,
2470      we just need the first SET.   This can occur when simplifying a divmod
2471      insn.  We *must* test for this case here because the code below that
2472      splits two independent SETs doesn't handle this case correctly when it
2473      updates the register status.
2474
2475      It's pointless doing this if we originally had two sets, one from
2476      i3, and one from i2.  Combining then splitting the parallel results
2477      in the original i2 again plus an invalid insn (which we delete).
2478      The net effect is only to move instructions around, which makes
2479      debug info less accurate.
2480
2481      Also check the case where the first SET's destination is unused.
2482      That would not cause incorrect code, but does cause an unneeded
2483      insn to remain.  */
2484
2485   if (insn_code_number < 0
2486       && !(added_sets_2 && i1 == 0)
2487       && GET_CODE (newpat) == PARALLEL
2488       && XVECLEN (newpat, 0) == 2
2489       && GET_CODE (XVECEXP (newpat, 0, 0)) == SET
2490       && GET_CODE (XVECEXP (newpat, 0, 1)) == SET
2491       && asm_noperands (newpat) < 0)
2492     {
2493       rtx set0 = XVECEXP (newpat, 0, 0);
2494       rtx set1 = XVECEXP (newpat, 0, 1);
2495       rtx note;
2496
2497       if (((REG_P (SET_DEST (set1))
2498             && find_reg_note (i3, REG_UNUSED, SET_DEST (set1)))
2499            || (GET_CODE (SET_DEST (set1)) == SUBREG
2500                && find_reg_note (i3, REG_UNUSED, SUBREG_REG (SET_DEST (set1)))))
2501           && (!(note = find_reg_note (i3, REG_EH_REGION, NULL_RTX))
2502               || INTVAL (XEXP (note, 0)) <= 0)
2503           && ! side_effects_p (SET_SRC (set1)))
2504         {
2505           newpat = set0;
2506           insn_code_number = recog_for_combine (&newpat, i3, &new_i3_notes);
2507         }
2508
2509       else if (((REG_P (SET_DEST (set0))
2510                  && find_reg_note (i3, REG_UNUSED, SET_DEST (set0)))
2511                 || (GET_CODE (SET_DEST (set0)) == SUBREG
2512                     && find_reg_note (i3, REG_UNUSED,
2513                                       SUBREG_REG (SET_DEST (set0)))))
2514                && (!(note = find_reg_note (i3, REG_EH_REGION, NULL_RTX))
2515                    || INTVAL (XEXP (note, 0)) <= 0)
2516                && ! side_effects_p (SET_SRC (set0)))
2517         {
2518           newpat = set1;
2519           insn_code_number = recog_for_combine (&newpat, i3, &new_i3_notes);
2520
2521           if (insn_code_number >= 0)
2522             {
2523               /* If we will be able to accept this, we have made a
2524                  change to the destination of I3.  This requires us to
2525                  do a few adjustments.  */
2526
2527               PATTERN (i3) = newpat;
2528               adjust_for_new_dest (i3);
2529             }
2530         }
2531     }
2532
2533   /* If we were combining three insns and the result is a simple SET
2534      with no ASM_OPERANDS that wasn't recognized, try to split it into two
2535      insns.  There are two ways to do this.  It can be split using a
2536      machine-specific method (like when you have an addition of a large
2537      constant) or by combine in the function find_split_point.  */
2538
2539   if (i1 && insn_code_number < 0 && GET_CODE (newpat) == SET
2540       && asm_noperands (newpat) < 0)
2541     {
2542       rtx m_split, *split;
2543
2544       /* See if the MD file can split NEWPAT.  If it can't, see if letting it
2545          use I2DEST as a scratch register will help.  In the latter case,
2546          convert I2DEST to the mode of the source of NEWPAT if we can.  */
2547
2548       m_split = split_insns (newpat, i3);
2549
2550       /* We can only use I2DEST as a scratch reg if it doesn't overlap any
2551          inputs of NEWPAT.  */
2552
2553       /* ??? If I2DEST is not safe, and I1DEST exists, then it would be
2554          possible to try that as a scratch reg.  This would require adding
2555          more code to make it work though.  */
2556
2557       if (m_split == 0 && ! reg_overlap_mentioned_p (i2dest, newpat))
2558         {
2559           enum machine_mode new_mode = GET_MODE (SET_DEST (newpat));
2560
2561           /* First try to split using the original register as a
2562              scratch register.  */
2563           m_split = split_insns (gen_rtx_PARALLEL
2564                                  (VOIDmode,
2565                                   gen_rtvec (2, newpat,
2566                                              gen_rtx_CLOBBER (VOIDmode,
2567                                                               i2dest))),
2568                                  i3);
2569
2570           /* If that didn't work, try changing the mode of I2DEST if
2571              we can.  */
2572           if (m_split == 0
2573               && new_mode != GET_MODE (i2dest)
2574               && new_mode != VOIDmode
2575               && can_change_dest_mode (i2dest, added_sets_2, new_mode))
2576             {
2577               enum machine_mode old_mode = GET_MODE (i2dest);
2578               rtx ni2dest;
2579
2580               if (REGNO (i2dest) < FIRST_PSEUDO_REGISTER)
2581                 ni2dest = gen_rtx_REG (new_mode, REGNO (i2dest));
2582               else
2583                 {
2584                   SUBST_MODE (regno_reg_rtx[REGNO (i2dest)], new_mode);
2585                   ni2dest = regno_reg_rtx[REGNO (i2dest)];
2586                 }
2587
2588               m_split = split_insns (gen_rtx_PARALLEL
2589                                      (VOIDmode,
2590                                       gen_rtvec (2, newpat,
2591                                                  gen_rtx_CLOBBER (VOIDmode,
2592                                                                   ni2dest))),
2593                                      i3);
2594
2595               if (m_split == 0
2596                   && REGNO (i2dest) >= FIRST_PSEUDO_REGISTER)
2597                 {
2598                   struct undo *buf;
2599
2600                   PUT_MODE (regno_reg_rtx[REGNO (i2dest)], old_mode);
2601                   buf = undobuf.undos;
2602                   undobuf.undos = buf->next;
2603                   buf->next = undobuf.frees;
2604                   undobuf.frees = buf;
2605                 }
2606             }
2607         }
2608
2609       /* If recog_for_combine has discarded clobbers, try to use them
2610          again for the split.  */
2611       if (m_split == 0 && newpat_vec_with_clobbers)
2612         m_split
2613           = split_insns (gen_rtx_PARALLEL (VOIDmode,
2614                                            newpat_vec_with_clobbers), i3);
2615
2616       if (m_split && NEXT_INSN (m_split) == NULL_RTX)
2617         {
2618           m_split = PATTERN (m_split);
2619           insn_code_number = recog_for_combine (&m_split, i3, &new_i3_notes);
2620           if (insn_code_number >= 0)
2621             newpat = m_split;
2622         }
2623       else if (m_split && NEXT_INSN (NEXT_INSN (m_split)) == NULL_RTX
2624                && (next_real_insn (i2) == i3
2625                    || ! use_crosses_set_p (PATTERN (m_split), INSN_CUID (i2))))
2626         {
2627           rtx i2set, i3set;
2628           rtx newi3pat = PATTERN (NEXT_INSN (m_split));
2629           newi2pat = PATTERN (m_split);
2630
2631           i3set = single_set (NEXT_INSN (m_split));
2632           i2set = single_set (m_split);
2633
2634           i2_code_number = recog_for_combine (&newi2pat, i2, &new_i2_notes);
2635
2636           /* If I2 or I3 has multiple SETs, we won't know how to track
2637              register status, so don't use these insns.  If I2's destination
2638              is used between I2 and I3, we also can't use these insns.  */
2639
2640           if (i2_code_number >= 0 && i2set && i3set
2641               && (next_real_insn (i2) == i3
2642                   || ! reg_used_between_p (SET_DEST (i2set), i2, i3)))
2643             insn_code_number = recog_for_combine (&newi3pat, i3,
2644                                                   &new_i3_notes);
2645           if (insn_code_number >= 0)
2646             newpat = newi3pat;
2647
2648           /* It is possible that both insns now set the destination of I3.
2649              If so, we must show an extra use of it.  */
2650
2651           if (insn_code_number >= 0)
2652             {
2653               rtx new_i3_dest = SET_DEST (i3set);
2654               rtx new_i2_dest = SET_DEST (i2set);
2655
2656               while (GET_CODE (new_i3_dest) == ZERO_EXTRACT
2657                      || GET_CODE (new_i3_dest) == STRICT_LOW_PART
2658                      || GET_CODE (new_i3_dest) == SUBREG)
2659                 new_i3_dest = XEXP (new_i3_dest, 0);
2660
2661               while (GET_CODE (new_i2_dest) == ZERO_EXTRACT
2662                      || GET_CODE (new_i2_dest) == STRICT_LOW_PART
2663                      || GET_CODE (new_i2_dest) == SUBREG)
2664                 new_i2_dest = XEXP (new_i2_dest, 0);
2665
2666               if (REG_P (new_i3_dest)
2667                   && REG_P (new_i2_dest)
2668                   && REGNO (new_i3_dest) == REGNO (new_i2_dest))
2669                 REG_N_SETS (REGNO (new_i2_dest))++;
2670             }
2671         }
2672
2673       /* If we can split it and use I2DEST, go ahead and see if that
2674          helps things be recognized.  Verify that none of the registers
2675          are set between I2 and I3.  */
2676       if (insn_code_number < 0 && (split = find_split_point (&newpat, i3)) != 0
2677 #ifdef HAVE_cc0
2678           && REG_P (i2dest)
2679 #endif
2680           /* We need I2DEST in the proper mode.  If it is a hard register
2681              or the only use of a pseudo, we can change its mode.
2682              Make sure we don't change a hard register to have a mode that
2683              isn't valid for it, or change the number of registers.  */
2684           && (GET_MODE (*split) == GET_MODE (i2dest)
2685               || GET_MODE (*split) == VOIDmode
2686               || can_change_dest_mode (i2dest, added_sets_2,
2687                                        GET_MODE (*split)))
2688           && (next_real_insn (i2) == i3
2689               || ! use_crosses_set_p (*split, INSN_CUID (i2)))
2690           /* We can't overwrite I2DEST if its value is still used by
2691              NEWPAT.  */
2692           && ! reg_referenced_p (i2dest, newpat))
2693         {
2694           rtx newdest = i2dest;
2695           enum rtx_code split_code = GET_CODE (*split);
2696           enum machine_mode split_mode = GET_MODE (*split);
2697           bool subst_done = false;
2698           newi2pat = NULL_RTX;
2699
2700           /* Get NEWDEST as a register in the proper mode.  We have already
2701              validated that we can do this.  */
2702           if (GET_MODE (i2dest) != split_mode && split_mode != VOIDmode)
2703             {
2704               if (REGNO (i2dest) < FIRST_PSEUDO_REGISTER)
2705                 newdest = gen_rtx_REG (split_mode, REGNO (i2dest));
2706               else
2707                 {
2708                   SUBST_MODE (regno_reg_rtx[REGNO (i2dest)], split_mode);
2709                   newdest = regno_reg_rtx[REGNO (i2dest)];
2710                 }
2711             }
2712
2713           /* If *SPLIT is a (mult FOO (const_int pow2)), convert it to
2714              an ASHIFT.  This can occur if it was inside a PLUS and hence
2715              appeared to be a memory address.  This is a kludge.  */
2716           if (split_code == MULT
2717               && GET_CODE (XEXP (*split, 1)) == CONST_INT
2718               && INTVAL (XEXP (*split, 1)) > 0
2719               && (i = exact_log2 (INTVAL (XEXP (*split, 1)))) >= 0)
2720             {
2721               SUBST (*split, gen_rtx_ASHIFT (split_mode,
2722                                              XEXP (*split, 0), GEN_INT (i)));
2723               /* Update split_code because we may not have a multiply
2724                  anymore.  */
2725               split_code = GET_CODE (*split);
2726             }
2727
2728 #ifdef INSN_SCHEDULING
2729           /* If *SPLIT is a paradoxical SUBREG, when we split it, it should
2730              be written as a ZERO_EXTEND.  */
2731           if (split_code == SUBREG && MEM_P (SUBREG_REG (*split)))
2732             {
2733 #ifdef LOAD_EXTEND_OP
2734               /* Or as a SIGN_EXTEND if LOAD_EXTEND_OP says that that's
2735                  what it really is.  */
2736               if (LOAD_EXTEND_OP (GET_MODE (SUBREG_REG (*split)))
2737                   == SIGN_EXTEND)
2738                 SUBST (*split, gen_rtx_SIGN_EXTEND (split_mode,
2739                                                     SUBREG_REG (*split)));
2740               else
2741 #endif
2742                 SUBST (*split, gen_rtx_ZERO_EXTEND (split_mode,
2743                                                     SUBREG_REG (*split)));
2744             }
2745 #endif
2746
2747           /* Attempt to split binary operators using arithmetic identities.  */
2748           if (BINARY_P (SET_SRC (newpat))
2749               && split_mode == GET_MODE (SET_SRC (newpat))
2750               && ! side_effects_p (SET_SRC (newpat)))
2751             {
2752               rtx setsrc = SET_SRC (newpat);
2753               enum machine_mode mode = GET_MODE (setsrc);
2754               enum rtx_code code = GET_CODE (setsrc);
2755               rtx src_op0 = XEXP (setsrc, 0);
2756               rtx src_op1 = XEXP (setsrc, 1);
2757
2758               /* Split "X = Y op Y" as "Z = Y; X = Z op Z".  */
2759               if (rtx_equal_p (src_op0, src_op1))
2760                 {
2761                   newi2pat = gen_rtx_SET (VOIDmode, newdest, src_op0);
2762                   SUBST (XEXP (setsrc, 0), newdest);
2763                   SUBST (XEXP (setsrc, 1), newdest);
2764                   subst_done = true;
2765                 }
2766               /* Split "((P op Q) op R) op S" where op is PLUS or MULT.  */
2767               else if ((code == PLUS || code == MULT)
2768                        && GET_CODE (src_op0) == code
2769                        && GET_CODE (XEXP (src_op0, 0)) == code
2770                        && (INTEGRAL_MODE_P (mode)
2771                            || (FLOAT_MODE_P (mode)
2772                                && flag_unsafe_math_optimizations)))
2773                 {
2774                   rtx p = XEXP (XEXP (src_op0, 0), 0);
2775                   rtx q = XEXP (XEXP (src_op0, 0), 1);
2776                   rtx r = XEXP (src_op0, 1);
2777                   rtx s = src_op1;
2778
2779                   /* Split both "((X op Y) op X) op Y" and
2780                      "((X op Y) op Y) op X" as "T op T" where T is
2781                      "X op Y".  */
2782                   if ((rtx_equal_p (p,r) && rtx_equal_p (q,s))
2783                        || (rtx_equal_p (p,s) && rtx_equal_p (q,r)))
2784                     {
2785                       newi2pat = gen_rtx_SET (VOIDmode, newdest,
2786                                               XEXP (src_op0, 0));
2787                       SUBST (XEXP (setsrc, 0), newdest);
2788                       SUBST (XEXP (setsrc, 1), newdest);
2789                       subst_done = true;
2790                     }
2791                   /* Split "((X op X) op Y) op Y)" as "T op T" where
2792                      T is "X op Y".  */
2793                   else if (rtx_equal_p (p,q) && rtx_equal_p (r,s))
2794                     {
2795                       rtx tmp = simplify_gen_binary (code, mode, p, r);
2796                       newi2pat = gen_rtx_SET (VOIDmode, newdest, tmp);
2797                       SUBST (XEXP (setsrc, 0), newdest);
2798                       SUBST (XEXP (setsrc, 1), newdest);
2799                       subst_done = true;
2800                     }
2801                 }
2802             }
2803
2804           if (!subst_done)
2805             {
2806               newi2pat = gen_rtx_SET (VOIDmode, newdest, *split);
2807               SUBST (*split, newdest);
2808             }
2809
2810           i2_code_number = recog_for_combine (&newi2pat, i2, &new_i2_notes);
2811
2812           /* recog_for_combine might have added CLOBBERs to newi2pat.
2813              Make sure NEWPAT does not depend on the clobbered regs.  */
2814           if (GET_CODE (newi2pat) == PARALLEL)
2815             for (i = XVECLEN (newi2pat, 0) - 1; i >= 0; i--)
2816               if (GET_CODE (XVECEXP (newi2pat, 0, i)) == CLOBBER)
2817                 {
2818                   rtx reg = XEXP (XVECEXP (newi2pat, 0, i), 0);
2819                   if (reg_overlap_mentioned_p (reg, newpat))
2820                     {
2821                       undo_all ();
2822                       return 0;
2823                     }
2824                 }
2825
2826           /* If the split point was a MULT and we didn't have one before,
2827              don't use one now.  */
2828           if (i2_code_number >= 0 && ! (split_code == MULT && ! have_mult))
2829             insn_code_number = recog_for_combine (&newpat, i3, &new_i3_notes);
2830         }
2831     }
2832
2833   /* Check for a case where we loaded from memory in a narrow mode and
2834      then sign extended it, but we need both registers.  In that case,
2835      we have a PARALLEL with both loads from the same memory location.
2836      We can split this into a load from memory followed by a register-register
2837      copy.  This saves at least one insn, more if register allocation can
2838      eliminate the copy.
2839
2840      We cannot do this if the destination of the first assignment is a
2841      condition code register or cc0.  We eliminate this case by making sure
2842      the SET_DEST and SET_SRC have the same mode.
2843
2844      We cannot do this if the destination of the second assignment is
2845      a register that we have already assumed is zero-extended.  Similarly
2846      for a SUBREG of such a register.  */
2847
2848   else if (i1 && insn_code_number < 0 && asm_noperands (newpat) < 0
2849            && GET_CODE (newpat) == PARALLEL
2850            && XVECLEN (newpat, 0) == 2
2851            && GET_CODE (XVECEXP (newpat, 0, 0)) == SET
2852            && GET_CODE (SET_SRC (XVECEXP (newpat, 0, 0))) == SIGN_EXTEND
2853            && (GET_MODE (SET_DEST (XVECEXP (newpat, 0, 0)))
2854                == GET_MODE (SET_SRC (XVECEXP (newpat, 0, 0))))
2855            && GET_CODE (XVECEXP (newpat, 0, 1)) == SET
2856            && rtx_equal_p (SET_SRC (XVECEXP (newpat, 0, 1)),
2857                            XEXP (SET_SRC (XVECEXP (newpat, 0, 0)), 0))
2858            && ! use_crosses_set_p (SET_SRC (XVECEXP (newpat, 0, 1)),
2859                                    INSN_CUID (i2))
2860            && GET_CODE (SET_DEST (XVECEXP (newpat, 0, 1))) != ZERO_EXTRACT
2861            && GET_CODE (SET_DEST (XVECEXP (newpat, 0, 1))) != STRICT_LOW_PART
2862            && ! (temp = SET_DEST (XVECEXP (newpat, 0, 1)),
2863                  (REG_P (temp)
2864                   && reg_stat[REGNO (temp)].nonzero_bits != 0
2865                   && GET_MODE_BITSIZE (GET_MODE (temp)) < BITS_PER_WORD
2866                   && GET_MODE_BITSIZE (GET_MODE (temp)) < HOST_BITS_PER_INT
2867                   && (reg_stat[REGNO (temp)].nonzero_bits
2868                       != GET_MODE_MASK (word_mode))))
2869            && ! (GET_CODE (SET_DEST (XVECEXP (newpat, 0, 1))) == SUBREG
2870                  && (temp = SUBREG_REG (SET_DEST (XVECEXP (newpat, 0, 1))),
2871                      (REG_P (temp)
2872                       && reg_stat[REGNO (temp)].nonzero_bits != 0
2873                       && GET_MODE_BITSIZE (GET_MODE (temp)) < BITS_PER_WORD
2874                       && GET_MODE_BITSIZE (GET_MODE (temp)) < HOST_BITS_PER_INT
2875                       && (reg_stat[REGNO (temp)].nonzero_bits
2876                           != GET_MODE_MASK (word_mode)))))
2877            && ! reg_overlap_mentioned_p (SET_DEST (XVECEXP (newpat, 0, 1)),
2878                                          SET_SRC (XVECEXP (newpat, 0, 1)))
2879            && ! find_reg_note (i3, REG_UNUSED,
2880                                SET_DEST (XVECEXP (newpat, 0, 0))))
2881     {
2882       rtx ni2dest;
2883
2884       newi2pat = XVECEXP (newpat, 0, 0);
2885       ni2dest = SET_DEST (XVECEXP (newpat, 0, 0));
2886       newpat = XVECEXP (newpat, 0, 1);
2887       SUBST (SET_SRC (newpat),
2888              gen_lowpart (GET_MODE (SET_SRC (newpat)), ni2dest));
2889       i2_code_number = recog_for_combine (&newi2pat, i2, &new_i2_notes);
2890
2891       if (i2_code_number >= 0)
2892         insn_code_number = recog_for_combine (&newpat, i3, &new_i3_notes);
2893
2894       if (insn_code_number >= 0)
2895         swap_i2i3 = 1;
2896     }
2897
2898   /* Similarly, check for a case where we have a PARALLEL of two independent
2899      SETs but we started with three insns.  In this case, we can do the sets
2900      as two separate insns.  This case occurs when some SET allows two
2901      other insns to combine, but the destination of that SET is still live.  */
2902
2903   else if (i1 && insn_code_number < 0 && asm_noperands (newpat) < 0
2904            && GET_CODE (newpat) == PARALLEL
2905            && XVECLEN (newpat, 0) == 2
2906            && GET_CODE (XVECEXP (newpat, 0, 0)) == SET
2907            && GET_CODE (SET_DEST (XVECEXP (newpat, 0, 0))) != ZERO_EXTRACT
2908            && GET_CODE (SET_DEST (XVECEXP (newpat, 0, 0))) != STRICT_LOW_PART
2909            && GET_CODE (XVECEXP (newpat, 0, 1)) == SET
2910            && GET_CODE (SET_DEST (XVECEXP (newpat, 0, 1))) != ZERO_EXTRACT
2911            && GET_CODE (SET_DEST (XVECEXP (newpat, 0, 1))) != STRICT_LOW_PART
2912            && ! use_crosses_set_p (SET_SRC (XVECEXP (newpat, 0, 1)),
2913                                    INSN_CUID (i2))
2914            && ! reg_referenced_p (SET_DEST (XVECEXP (newpat, 0, 1)),
2915                                   XVECEXP (newpat, 0, 0))
2916            && ! reg_referenced_p (SET_DEST (XVECEXP (newpat, 0, 0)),
2917                                   XVECEXP (newpat, 0, 1))
2918            && ! (contains_muldiv (SET_SRC (XVECEXP (newpat, 0, 0)))
2919                  && contains_muldiv (SET_SRC (XVECEXP (newpat, 0, 1))))
2920 #ifdef HAVE_cc0
2921            /* We cannot split the parallel into two sets if both sets
2922               reference cc0.  */
2923            && ! (reg_referenced_p (cc0_rtx, XVECEXP (newpat, 0, 0))
2924                  && reg_referenced_p (cc0_rtx, XVECEXP (newpat, 0, 1)))
2925 #endif
2926            )
2927     {
2928       /* Normally, it doesn't matter which of the two is done first,
2929          but it does if one references cc0.  In that case, it has to
2930          be first.  */
2931 #ifdef HAVE_cc0
2932       if (reg_referenced_p (cc0_rtx, XVECEXP (newpat, 0, 0)))
2933         {
2934           newi2pat = XVECEXP (newpat, 0, 0);
2935           newpat = XVECEXP (newpat, 0, 1);
2936         }
2937       else
2938 #endif
2939         {
2940           newi2pat = XVECEXP (newpat, 0, 1);
2941           newpat = XVECEXP (newpat, 0, 0);
2942         }
2943
2944       i2_code_number = recog_for_combine (&newi2pat, i2, &new_i2_notes);
2945
2946       if (i2_code_number >= 0)
2947         insn_code_number = recog_for_combine (&newpat, i3, &new_i3_notes);
2948     }
2949
2950   /* If it still isn't recognized, fail and change things back the way they
2951      were.  */
2952   if ((insn_code_number < 0
2953        /* Is the result a reasonable ASM_OPERANDS?  */
2954        && (! check_asm_operands (newpat) || added_sets_1 || added_sets_2)))
2955     {
2956       undo_all ();
2957       return 0;
2958     }
2959
2960   /* If we had to change another insn, make sure it is valid also.  */
2961   if (undobuf.other_insn)
2962     {
2963       rtx other_pat = PATTERN (undobuf.other_insn);
2964       rtx new_other_notes;
2965       rtx note, next;
2966
2967       CLEAR_HARD_REG_SET (newpat_used_regs);
2968
2969       other_code_number = recog_for_combine (&other_pat, undobuf.other_insn,
2970                                              &new_other_notes);
2971
2972       if (other_code_number < 0 && ! check_asm_operands (other_pat))
2973         {
2974           undo_all ();
2975           return 0;
2976         }
2977
2978       PATTERN (undobuf.other_insn) = other_pat;
2979
2980       /* If any of the notes in OTHER_INSN were REG_UNUSED, ensure that they
2981          are still valid.  Then add any non-duplicate notes added by
2982          recog_for_combine.  */
2983       for (note = REG_NOTES (undobuf.other_insn); note; note = next)
2984         {
2985           next = XEXP (note, 1);
2986
2987           if (REG_NOTE_KIND (note) == REG_UNUSED
2988               && ! reg_set_p (XEXP (note, 0), PATTERN (undobuf.other_insn)))
2989             {
2990               if (REG_P (XEXP (note, 0)))
2991                 REG_N_DEATHS (REGNO (XEXP (note, 0)))--;
2992
2993               remove_note (undobuf.other_insn, note);
2994             }
2995         }
2996
2997       for (note = new_other_notes; note; note = XEXP (note, 1))
2998         if (REG_P (XEXP (note, 0)))
2999           REG_N_DEATHS (REGNO (XEXP (note, 0)))++;
3000
3001       distribute_notes (new_other_notes, undobuf.other_insn,
3002                         undobuf.other_insn, NULL_RTX, NULL_RTX, NULL_RTX);
3003     }
3004 #ifdef HAVE_cc0
3005   /* If I2 is the CC0 setter and I3 is the CC0 user then check whether
3006      they are adjacent to each other or not.  */
3007   {
3008     rtx p = prev_nonnote_insn (i3);
3009     if (p && p != i2 && NONJUMP_INSN_P (p) && newi2pat
3010         && sets_cc0_p (newi2pat))
3011       {
3012         undo_all ();
3013         return 0;
3014       }
3015   }
3016 #endif
3017
3018   /* Only allow this combination if insn_rtx_costs reports that the
3019      replacement instructions are cheaper than the originals.  */
3020   if (!combine_validate_cost (i1, i2, i3, newpat, newi2pat))
3021     {
3022       undo_all ();
3023       return 0;
3024     }
3025
3026   /* We now know that we can do this combination.  Merge the insns and
3027      update the status of registers and LOG_LINKS.  */
3028
3029   if (swap_i2i3)
3030     {
3031       rtx insn;
3032       rtx link;
3033       rtx ni2dest;
3034
3035       /* I3 now uses what used to be its destination and which is now
3036          I2's destination.  This requires us to do a few adjustments.  */
3037       PATTERN (i3) = newpat;
3038       adjust_for_new_dest (i3);
3039
3040       /* We need a LOG_LINK from I3 to I2.  But we used to have one,
3041          so we still will.
3042
3043          However, some later insn might be using I2's dest and have
3044          a LOG_LINK pointing at I3.  We must remove this link.
3045          The simplest way to remove the link is to point it at I1,
3046          which we know will be a NOTE.  */
3047
3048       /* newi2pat is usually a SET here; however, recog_for_combine might
3049          have added some clobbers.  */
3050       if (GET_CODE (newi2pat) == PARALLEL)
3051         ni2dest = SET_DEST (XVECEXP (newi2pat, 0, 0));
3052       else
3053         ni2dest = SET_DEST (newi2pat);
3054
3055       for (insn = NEXT_INSN (i3);
3056            insn && (this_basic_block->next_bb == EXIT_BLOCK_PTR
3057                     || insn != BB_HEAD (this_basic_block->next_bb));
3058            insn = NEXT_INSN (insn))
3059         {
3060           if (INSN_P (insn) && reg_referenced_p (ni2dest, PATTERN (insn)))
3061             {
3062               for (link = LOG_LINKS (insn); link;
3063                    link = XEXP (link, 1))
3064                 if (XEXP (link, 0) == i3)
3065                   XEXP (link, 0) = i1;
3066
3067               break;
3068             }
3069         }
3070     }
3071
3072   {
3073     rtx i3notes, i2notes, i1notes = 0;
3074     rtx i3links, i2links, i1links = 0;
3075     rtx midnotes = 0;
3076     unsigned int regno;
3077     /* Compute which registers we expect to eliminate.  newi2pat may be setting
3078        either i3dest or i2dest, so we must check it.  Also, i1dest may be the
3079        same as i3dest, in which case newi2pat may be setting i1dest.  */
3080     rtx elim_i2 = ((newi2pat && reg_set_p (i2dest, newi2pat))
3081                    || i2dest_in_i2src || i2dest_in_i1src
3082                    || !i2dest_killed
3083                    ? 0 : i2dest);
3084     rtx elim_i1 = (i1 == 0 || i1dest_in_i1src
3085                    || (newi2pat && reg_set_p (i1dest, newi2pat))
3086                    || !i1dest_killed
3087                    ? 0 : i1dest);
3088
3089     /* Get the old REG_NOTES and LOG_LINKS from all our insns and
3090        clear them.  */
3091     i3notes = REG_NOTES (i3), i3links = LOG_LINKS (i3);
3092     i2notes = REG_NOTES (i2), i2links = LOG_LINKS (i2);
3093     if (i1)
3094       i1notes = REG_NOTES (i1), i1links = LOG_LINKS (i1);
3095
3096     /* Ensure that we do not have something that should not be shared but
3097        occurs multiple times in the new insns.  Check this by first
3098        resetting all the `used' flags and then copying anything is shared.  */
3099
3100     reset_used_flags (i3notes);
3101     reset_used_flags (i2notes);
3102     reset_used_flags (i1notes);
3103     reset_used_flags (newpat);
3104     reset_used_flags (newi2pat);
3105     if (undobuf.other_insn)
3106       reset_used_flags (PATTERN (undobuf.other_insn));
3107
3108     i3notes = copy_rtx_if_shared (i3notes);
3109     i2notes = copy_rtx_if_shared (i2notes);
3110     i1notes = copy_rtx_if_shared (i1notes);
3111     newpat = copy_rtx_if_shared (newpat);
3112     newi2pat = copy_rtx_if_shared (newi2pat);
3113     if (undobuf.other_insn)
3114       reset_used_flags (PATTERN (undobuf.other_insn));
3115
3116     INSN_CODE (i3) = insn_code_number;
3117     PATTERN (i3) = newpat;
3118
3119     if (CALL_P (i3) && CALL_INSN_FUNCTION_USAGE (i3))
3120       {
3121         rtx call_usage = CALL_INSN_FUNCTION_USAGE (i3);
3122
3123         reset_used_flags (call_usage);
3124         call_usage = copy_rtx (call_usage);
3125
3126         if (substed_i2)
3127           replace_rtx (call_usage, i2dest, i2src);
3128
3129         if (substed_i1)
3130           replace_rtx (call_usage, i1dest, i1src);
3131
3132         CALL_INSN_FUNCTION_USAGE (i3) = call_usage;
3133       }
3134
3135     if (undobuf.other_insn)
3136       INSN_CODE (undobuf.other_insn) = other_code_number;
3137
3138     /* We had one special case above where I2 had more than one set and
3139        we replaced a destination of one of those sets with the destination
3140        of I3.  In that case, we have to update LOG_LINKS of insns later
3141        in this basic block.  Note that this (expensive) case is rare.
3142
3143        Also, in this case, we must pretend that all REG_NOTEs for I2
3144        actually came from I3, so that REG_UNUSED notes from I2 will be
3145        properly handled.  */
3146
3147     if (i3_subst_into_i2)
3148       {
3149         for (i = 0; i < XVECLEN (PATTERN (i2), 0); i++)
3150           if ((GET_CODE (XVECEXP (PATTERN (i2), 0, i)) == SET
3151                || GET_CODE (XVECEXP (PATTERN (i2), 0, i)) == CLOBBER)
3152               && REG_P (SET_DEST (XVECEXP (PATTERN (i2), 0, i)))
3153               && SET_DEST (XVECEXP (PATTERN (i2), 0, i)) != i2dest
3154               && ! find_reg_note (i2, REG_UNUSED,
3155                                   SET_DEST (XVECEXP (PATTERN (i2), 0, i))))
3156             for (temp = NEXT_INSN (i2);
3157                  temp && (this_basic_block->next_bb == EXIT_BLOCK_PTR
3158                           || BB_HEAD (this_basic_block) != temp);
3159                  temp = NEXT_INSN (temp))
3160               if (temp != i3 && INSN_P (temp))
3161                 for (link = LOG_LINKS (temp); link; link = XEXP (link, 1))
3162                   if (XEXP (link, 0) == i2)
3163                     XEXP (link, 0) = i3;
3164
3165         if (i3notes)
3166           {
3167             rtx link = i3notes;
3168             while (XEXP (link, 1))
3169               link = XEXP (link, 1);
3170             XEXP (link, 1) = i2notes;
3171           }
3172         else
3173           i3notes = i2notes;
3174         i2notes = 0;
3175       }
3176
3177     LOG_LINKS (i3) = 0;
3178     REG_NOTES (i3) = 0;
3179     LOG_LINKS (i2) = 0;
3180     REG_NOTES (i2) = 0;
3181
3182     if (newi2pat)
3183       {
3184         INSN_CODE (i2) = i2_code_number;
3185         PATTERN (i2) = newi2pat;
3186       }
3187     else
3188       SET_INSN_DELETED (i2);
3189
3190     if (i1)
3191       {
3192         LOG_LINKS (i1) = 0;
3193         REG_NOTES (i1) = 0;
3194         SET_INSN_DELETED (i1);
3195       }
3196
3197     /* Get death notes for everything that is now used in either I3 or
3198        I2 and used to die in a previous insn.  If we built two new
3199        patterns, move from I1 to I2 then I2 to I3 so that we get the
3200        proper movement on registers that I2 modifies.  */
3201
3202     if (newi2pat)
3203       {
3204         move_deaths (newi2pat, NULL_RTX, INSN_CUID (i1), i2, &midnotes);
3205         move_deaths (newpat, newi2pat, INSN_CUID (i1), i3, &midnotes);
3206       }
3207     else
3208       move_deaths (newpat, NULL_RTX, i1 ? INSN_CUID (i1) : INSN_CUID (i2),
3209                    i3, &midnotes);
3210
3211     /* Distribute all the LOG_LINKS and REG_NOTES from I1, I2, and I3.  */
3212     if (i3notes)
3213       distribute_notes (i3notes, i3, i3, newi2pat ? i2 : NULL_RTX,
3214                         elim_i2, elim_i1);
3215     if (i2notes)
3216       distribute_notes (i2notes, i2, i3, newi2pat ? i2 : NULL_RTX,
3217                         elim_i2, elim_i1);
3218     if (i1notes)
3219       distribute_notes (i1notes, i1, i3, newi2pat ? i2 : NULL_RTX,
3220                         elim_i2, elim_i1);
3221     if (midnotes)
3222       distribute_notes (midnotes, NULL_RTX, i3, newi2pat ? i2 : NULL_RTX,
3223                         elim_i2, elim_i1);
3224
3225     /* Distribute any notes added to I2 or I3 by recog_for_combine.  We
3226        know these are REG_UNUSED and want them to go to the desired insn,
3227        so we always pass it as i3.  We have not counted the notes in
3228        reg_n_deaths yet, so we need to do so now.  */
3229
3230     if (newi2pat && new_i2_notes)
3231       {
3232         for (temp = new_i2_notes; temp; temp = XEXP (temp, 1))
3233           if (REG_P (XEXP (temp, 0)))
3234             REG_N_DEATHS (REGNO (XEXP (temp, 0)))++;
3235
3236         distribute_notes (new_i2_notes, i2, i2, NULL_RTX, NULL_RTX, NULL_RTX);
3237       }
3238
3239     if (new_i3_notes)
3240       {
3241         for (temp = new_i3_notes; temp; temp = XEXP (temp, 1))
3242           if (REG_P (XEXP (temp, 0)))
3243             REG_N_DEATHS (REGNO (XEXP (temp, 0)))++;
3244
3245         distribute_notes (new_i3_notes, i3, i3, NULL_RTX, NULL_RTX, NULL_RTX);
3246       }
3247
3248     /* If I3DEST was used in I3SRC, it really died in I3.  We may need to
3249        put a REG_DEAD note for it somewhere.  If NEWI2PAT exists and sets
3250        I3DEST, the death must be somewhere before I2, not I3.  If we passed I3
3251        in that case, it might delete I2.  Similarly for I2 and I1.
3252        Show an additional death due to the REG_DEAD note we make here.  If
3253        we discard it in distribute_notes, we will decrement it again.  */
3254
3255     if (i3dest_killed)
3256       {
3257         if (REG_P (i3dest_killed))
3258           REG_N_DEATHS (REGNO (i3dest_killed))++;
3259
3260         if (newi2pat && reg_set_p (i3dest_killed, newi2pat))
3261           distribute_notes (gen_rtx_EXPR_LIST (REG_DEAD, i3dest_killed,
3262                                                NULL_RTX),
3263                             NULL_RTX, i2, NULL_RTX, elim_i2, elim_i1);
3264         else
3265           distribute_notes (gen_rtx_EXPR_LIST (REG_DEAD, i3dest_killed,
3266                                                NULL_RTX),
3267                             NULL_RTX, i3, newi2pat ? i2 : NULL_RTX,
3268                             elim_i2, elim_i1);
3269       }
3270
3271     if (i2dest_in_i2src)
3272       {
3273         if (REG_P (i2dest))
3274           REG_N_DEATHS (REGNO (i2dest))++;
3275
3276         if (newi2pat && reg_set_p (i2dest, newi2pat))
3277           distribute_notes (gen_rtx_EXPR_LIST (REG_DEAD, i2dest, NULL_RTX),
3278                             NULL_RTX, i2, NULL_RTX, NULL_RTX, NULL_RTX);
3279         else
3280           distribute_notes (gen_rtx_EXPR_LIST (REG_DEAD, i2dest, NULL_RTX),
3281                             NULL_RTX, i3, newi2pat ? i2 : NULL_RTX,
3282                             NULL_RTX, NULL_RTX);
3283       }
3284
3285     if (i1dest_in_i1src)
3286       {
3287         if (REG_P (i1dest))
3288           REG_N_DEATHS (REGNO (i1dest))++;
3289
3290         if (newi2pat && reg_set_p (i1dest, newi2pat))
3291           distribute_notes (gen_rtx_EXPR_LIST (REG_DEAD, i1dest, NULL_RTX),
3292                             NULL_RTX, i2, NULL_RTX, NULL_RTX, NULL_RTX);
3293         else
3294           distribute_notes (gen_rtx_EXPR_LIST (REG_DEAD, i1dest, NULL_RTX),
3295                             NULL_RTX, i3, newi2pat ? i2 : NULL_RTX,
3296                             NULL_RTX, NULL_RTX);
3297       }
3298
3299     distribute_links (i3links);
3300     distribute_links (i2links);
3301     distribute_links (i1links);
3302
3303     if (REG_P (i2dest))
3304       {
3305         rtx link;
3306         rtx i2_insn = 0, i2_val = 0, set;
3307
3308         /* The insn that used to set this register doesn't exist, and
3309            this life of the register may not exist either.  See if one of
3310            I3's links points to an insn that sets I2DEST.  If it does,
3311            that is now the last known value for I2DEST. If we don't update
3312            this and I2 set the register to a value that depended on its old
3313            contents, we will get confused.  If this insn is used, thing
3314            will be set correctly in combine_instructions.  */
3315
3316         for (link = LOG_LINKS (i3); link; link = XEXP (link, 1))
3317           if ((set = single_set (XEXP (link, 0))) != 0
3318               && rtx_equal_p (i2dest, SET_DEST (set)))
3319             i2_insn = XEXP (link, 0), i2_val = SET_SRC (set);
3320
3321         record_value_for_reg (i2dest, i2_insn, i2_val);
3322
3323         /* If the reg formerly set in I2 died only once and that was in I3,
3324            zero its use count so it won't make `reload' do any work.  */
3325         if (! added_sets_2