OSDN Git Service

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