OSDN Git Service

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