OSDN Git Service

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