OSDN Git Service

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