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