OSDN Git Service

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