OSDN Git Service

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