OSDN Git Service

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