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