OSDN Git Service

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