OSDN Git Service

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