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