OSDN Git Service

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