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