OSDN Git Service

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