OSDN Git Service

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