OSDN Git Service

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