OSDN Git Service

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