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