OSDN Git Service

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