OSDN Git Service

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