+/* Optimize by combining instructions for GNU compiler.
+ Copyright (C) 1987, 1988 Free Software Foundation, Inc.
+
+This file is part of GNU CC.
+
+GNU CC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 1, or (at your option)
+any later version.
+
+GNU CC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU CC; see the file COPYING. If not, write to
+the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
+
+
+/* This module is essentially the "combiner" phase of the U. of Arizona
+ Portable Optimizer, but redone to work on our list-structured
+ representation for RTL instead of their string representation.
+
+ The LOG_LINKS of each insn identify the most recent assignment
+ to each REG used in the insn. It is a list of previous insns,
+ each of which contains a SET for a REG that is used in this insn
+ and not used or set in between. LOG_LINKs never cross basic blocks.
+ They were set up by the preceding pass (lifetime analysis).
+
+ We try to combine each pair of insns joined by a logical link.
+ We also try to combine triples of insns A, B and C when
+ C has a link back to B and B has a link back to A.
+
+ LOG_LINKS does not have links for use of the CC0. They don't
+ need to, because the insn that sets the CC0 is always immediately
+ before the insn that tests it. So we always regard a branch
+ insn as having a logical link to the preceding insn.
+
+ We check (with use_crosses_set_p) to avoid combining in such a way
+ as to move a computation to a place where its value would be different.
+
+ Combination is done by mathematically substituting the previous
+ insn(s) values for the regs they set into the expressions in
+ the later insns that refer to these regs. If the result is a valid insn
+ for our target machine, according to the machine description,
+ we install it, delete the earlier insns, and update the data flow
+ information (LOG_LINKS and REG_NOTES) for what we did.
+
+ To simplify substitution, we combine only when the earlier insn(s)
+ consist of only a single assignment. To simplify updating afterward,
+ we never combine when a subroutine call appears in the middle.
+
+ Since we do not represent assignments to CC0 explicitly except when that
+ is all an insn does, there is no LOG_LINKS entry in an insn that uses
+ the condition code for the insn that set the condition code.
+ Fortunately, these two insns must be consecutive.
+ Therefore, every JUMP_INSN is taken to have an implicit logical link
+ to the preceding insn. This is not quite right, since non-jumps can
+ also use the condition code; but in practice such insns would not
+ combine anyway. */
+
+#include <stdio.h>
+
+#include "config.h"
+#include "rtl.h"
+#include "flags.h"
+#include "regs.h"
+#include "basic-block.h"
+#include "insn-config.h"
+#include "recog.h"
+
+#define max(A,B) ((A) > (B) ? (A) : (B))
+#define min(A,B) ((A) < (B) ? (A) : (B))
+
+/* It is not safe to use ordinary gen_lowpart in combine.
+ Use gen_lowpart_for_combine instead. See comments there. */
+#define gen_lowpart dont_use_gen_lowpart_you_dummy
+
+/* Number of attempts to combine instructions in this function. */
+
+static int combine_attempts;
+static int distrib_attempts;
+
+/* Number of attempts that got as far as substitution in this function. */
+
+static int combine_merges;
+static int distrib_merges_1, distrib_merges_2;
+
+/* Number of instructions combined with added SETs in this function. */
+
+static int combine_extras;
+
+/* Number of instructions combined in this function. */
+
+static int combine_successes;
+static int distrib_successes;
+
+/* Totals over entire compilation. */
+
+static int total_attempts, total_merges, total_extras, total_successes;
+static int total_distrib_attempts, total_distrib_merges_1, total_distrib_merges_2, total_distrib_successes;
+
+
+/* Vector mapping INSN_UIDs to cuids.
+ The cuids are like uids but increase monononically always.
+ Combine always uses cuids so that it can compare them.
+ But actually renumbering the uids, which we used to do,
+ proves to be a bad idea because it makes it hard to compare
+ the dumps produced by earlier passes with those from later passes. */
+
+static int *uid_cuid;
+
+/* Get the cuid of an insn. */
+
+#define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
+
+
+/* Record last point of death of (hard or pseudo) register n. */
+
+static rtx *reg_last_death;
+
+/* Record last point of modification of (hard or pseudo) register n. */
+
+static rtx *reg_last_set;
+
+/* Record the cuid of the last insn that invalidated memory
+ (anything that writes memory, and subroutine calls). */
+
+static int mem_last_set;
+
+/* Record the cuid of the last CALL_INSN
+ so we can tell whether a potential combination crosses any calls. */
+
+static int last_call_cuid;
+
+/* When `subst' is called, this is the insn that is being modified
+ (by combining in a previous insn). The PATTERN of this insn
+ is still the old pattern partially modified and it should not be
+ looked at, but this may be used to examine the successors of the insn
+ to judge whether a simplification is valid. */
+
+static rtx subst_insn;
+
+/* Record one modification to rtl structure
+ to be undone by storing old_contents into *where.
+ is_int is 1 if the contents are an int. */
+
+struct undo
+{
+ rtx *where;
+ rtx old_contents;
+ int is_int;
+};
+
+struct undo_int
+{
+ int *where;
+ int old_contents;
+ int is_int;
+};
+
+/* Record a bunch of changes to be undone, up to MAX_UNDO of them.
+ num_undo says how many are currently recorded.
+ storage is nonzero if we must undo the allocation of new storage.
+ The value of storage is what to pass to obfree. */
+
+#define MAX_UNDO 10
+
+struct undobuf
+{
+ int num_undo;
+ char *storage;
+ struct undo undo[MAX_UNDO];
+};
+
+static struct undobuf undobuf;
+
+/* Number of times the pseudo being substituted for
+ was found and replaced. */
+
+static int n_occurrences;
+
+static void move_deaths ();
+static void move_deaths_2 ();
+void remove_death ();
+static void record_dead_and_set_regs ();
+int regno_dead_p ();
+static int use_crosses_set_p ();
+static int try_combine ();
+static rtx try_distrib ();
+static rtx subst ();
+static void undo_all ();
+static void copy_substitutions ();
+static void add_links ();
+static void remove_links ();
+static void add_incs ();
+static int adjacent_insns_p ();
+static int check_asm_operands ();
+static rtx simplify_and_const_int ();
+static rtx gen_lowpart_for_combine ();
+static void simplify_set_cc0_and ();
+\f
+/* Main entry point for combiner. F is the first insn of the function.
+ NREGS is the first unused pseudo-reg number. */
+
+void
+combine_instructions (f, nregs)
+ rtx f;
+ int nregs;
+{
+ register rtx insn;
+ register int i;
+ register rtx links, nextlinks;
+ rtx prev;
+
+ combine_attempts = 0;
+ combine_merges = 0;
+ combine_extras = 0;
+ combine_successes = 0;
+ distrib_attempts = 0;
+ distrib_merges_1 = 0;
+ distrib_merges_2 = 0;
+ distrib_successes = 0;
+
+ reg_last_death = (rtx *) alloca (nregs * sizeof (rtx));
+ reg_last_set = (rtx *) alloca (nregs * sizeof (rtx));
+ bzero (reg_last_death, nregs * sizeof (rtx));
+ bzero (reg_last_set, nregs * sizeof (rtx));
+
+ init_recog ();
+
+ /* Compute maximum uid value so uid_cuid can be allocated. */
+
+ for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
+ if (INSN_UID (insn) > i)
+ i = INSN_UID (insn);
+
+ uid_cuid = (int *) alloca ((i + 1) * sizeof (int));
+
+ /* Compute the mapping from uids to cuids.
+ Cuids are numbers assigned to insns, like uids,
+ except that cuids increase monotonically through the code. */
+
+ for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
+ INSN_CUID (insn) = ++i;
+
+ /* Now scan all the insns in forward order. */
+
+ last_call_cuid = 0;
+ mem_last_set = 0;
+ prev = 0;
+
+ for (insn = f; insn; insn = NEXT_INSN (insn))
+ {
+ if (GET_CODE (insn) == INSN
+ || GET_CODE (insn) == CALL_INSN
+ || GET_CODE (insn) == JUMP_INSN)
+ {
+ retry:
+ /* Try this insn with each insn it links back to. */
+
+ for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
+ if (try_combine (insn, XEXP (links, 0), 0))
+ goto retry;
+
+ /* Try each sequence of three linked insns ending with this one. */
+
+ for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
+ if (GET_CODE (XEXP (links, 0)) != NOTE)
+ for (nextlinks = LOG_LINKS (XEXP (links, 0)); nextlinks;
+ nextlinks = XEXP (nextlinks, 1))
+ if (try_combine (insn, XEXP (links, 0), XEXP (nextlinks, 0)))
+ goto retry;
+
+ /* Try to combine a jump insn that uses CC0
+ with a preceding insn that sets CC0, and maybe with its
+ logical predecessor as well.
+ This is how we make decrement-and-branch insns.
+ We need this special code because data flow connections
+ via CC0 do not get entered in LOG_LINKS. */
+
+ if (GET_CODE (insn) == JUMP_INSN
+ && prev != 0
+ && GET_CODE (prev) == INSN
+ && GET_CODE (PATTERN (prev)) == SET
+ && GET_CODE (SET_DEST (PATTERN (prev))) == CC0)
+ {
+ if (try_combine (insn, prev, 0))
+ goto retry;
+
+ if (GET_CODE (prev) != NOTE)
+ for (nextlinks = LOG_LINKS (prev); nextlinks;
+ nextlinks = XEXP (nextlinks, 1))
+ if (try_combine (insn, prev, XEXP (nextlinks, 0)))
+ goto retry;
+ }
+
+ /* Try to apply the distributive law to this insn
+ and two insns that compute the operands of this one. */
+ for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
+ if (GET_CODE (XEXP (links, 0)) != NOTE)
+ for (nextlinks = XEXP (links, 1); nextlinks; nextlinks = XEXP (nextlinks, 1))
+ if (GET_CODE (XEXP (nextlinks, 0)) != NOTE)
+ {
+ rtx try_from = 0;
+
+ if (GET_CODE (PATTERN (XEXP (links, 0))) == SET
+ && find_reg_note (insn, REG_DEAD, SET_DEST (PATTERN (XEXP (links, 0))))
+ && GET_CODE (PATTERN (XEXP (nextlinks, 0))) == SET
+ && find_reg_note (insn, REG_DEAD, SET_DEST (PATTERN (XEXP (nextlinks, 0)))))
+ try_from = try_distrib (insn, XEXP (links, 0), XEXP (nextlinks, 0));
+ if (try_from != 0)
+ {
+ insn = try_from;
+ goto retry;
+ }
+ }
+#if 0
+/* Turned off because on 68020 it takes four insns to make
+ something like (a[b / 32] & (1 << (31 - (b % 32)))) != 0
+ that could actually be optimized, and that's an unlikely piece of code. */
+ /* If an insn gets or sets a bit field, try combining it
+ with two different insns whose results it uses. */
+ if (GET_CODE (insn) == INSN
+ && GET_CODE (PATTERN (insn)) == SET
+ && (GET_CODE (SET_DEST (PATTERN (insn))) == ZERO_EXTRACT
+ || GET_CODE (SET_DEST (PATTERN (insn))) == SIGN_EXTRACT
+ || GET_CODE (SET_SRC (PATTERN (insn))) == ZERO_EXTRACT
+ || GET_CODE (SET_SRC (PATTERN (insn))) == SIGN_EXTRACT))
+ {
+ for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
+ if (GET_CODE (XEXP (links, 0)) != NOTE)
+ for (nextlinks = XEXP (links, 1); nextlinks;
+ nextlinks = XEXP (nextlinks, 1))
+ if (try_combine (insn, XEXP (links, 0), XEXP (nextlinks, 0)))
+ goto retry;
+ }
+#endif
+ if (GET_CODE (insn) != NOTE)
+ record_dead_and_set_regs (insn);
+ prev = insn;
+ }
+ else if (GET_CODE (insn) != NOTE)
+ prev = 0;
+ }
+ total_attempts += combine_attempts;
+ total_merges += combine_merges;
+ total_extras += combine_extras;
+ total_successes += combine_successes;
+}
+\f
+/* Try to combine the insns I1 and I2 into I3.
+ Here I1 appears earlier than I2, which is earlier than I3.
+ I1 can be zero; then we combine just I2 into I3.
+
+ Return 1 if successful; if that happens, I1 and I2 are pseudo-deleted
+ by turning them into NOTEs, and I3 is modified.
+ Return 0 if the combination does not work. Then nothing is changed. */
+
+static int
+try_combine (i3, i2, i1)
+ register rtx i3, i2, i1;
+{
+ register rtx newpat;
+ int added_sets_1 = 0;
+ int added_sets_2 = 0;
+ int total_sets;
+ int i2_is_used;
+ register rtx link;
+ int insn_code_number;
+ rtx i2dest, i2src;
+ rtx i1dest, i1src;
+ int maxreg;
+ rtx temp;
+ int i;
+
+ combine_attempts++;
+
+ /* Don't combine with something already used up by combination. */
+
+ if (GET_CODE (i2) == NOTE
+ || (i1 && GET_CODE (i1) == NOTE))
+ return 0;
+
+ /* Don't combine across a CALL_INSN, because that would possibly
+ change whether the life span of some REGs crosses calls or not,
+ and it is a pain to update that information. */
+
+ if (INSN_CUID (i2) < last_call_cuid
+ || (i1 && INSN_CUID (i1) < last_call_cuid))
+ return 0;
+
+ /* Can combine only if previous insn is a SET of a REG, a SUBREG or CC0.
+ That REG must be either set or dead by the final instruction
+ (so that we can safely forget about setting it).
+ Also test use_crosses_set_p to make sure that the value
+ that is to be substituted for the register
+ does not use any registers whose values alter in between.
+ Do not try combining with moves from one register to another
+ since it is better to let them be tied by register allocation.
+ (There is a switch to permit such combination; except the insns
+ that copy a function value into another register are never combined
+ because moving that too far away from the function call could cause
+ something else to be stored in that register in the interim.)
+
+ A set of a SUBREG is considered as if it were a set from
+ SUBREG. Thus, (SET (SUBREG:X (REG:Y...)) (something:X...))
+ is handled by substituting (SUBREG:Y (something:X...)) for (REG:Y...). */
+
+ if (GET_CODE (PATTERN (i2)) != SET)
+ return 0;
+ i2dest = SET_DEST (PATTERN (i2));
+ i2src = SET_SRC (PATTERN (i2));
+ if (GET_CODE (i2dest) == SUBREG)
+ {
+ i2dest = SUBREG_REG (i2dest);
+ i2src = gen_rtx (SUBREG, GET_MODE (i2dest), i2src, 0);
+ }
+ /* Don't eliminate a store in the stack pointer. */
+ if (i2dest == stack_pointer_rtx)
+ return 0;
+ /* Don't install a subreg involving two modes not tieable.
+ It can worsen register allocation, and can even make invalid reload insns,
+ since the reg inside may need to be copied from in the outside mode,
+ and that may be invalid if it is an fp reg copied in integer mode. */
+ if (GET_CODE (i2src) == SUBREG
+ && ! MODES_TIEABLE_P (GET_MODE (i2src), GET_MODE (SUBREG_REG (i2src))))
+ return 0;
+ if (GET_CODE (i2dest) != CC0
+ && (GET_CODE (i2dest) != REG
+ || (GET_CODE (i2src) == REG
+ /* Do allow the combination of y = x; x = y; (with x dead)
+ because the result will turn into nothing. */
+ && !(GET_CODE (PATTERN (i3)) == SET
+ && i2src == SET_DEST (PATTERN (i3)))
+ && (!flag_combine_regs
+ /* Don't substitute a function value reg for any other. */
+ || FUNCTION_VALUE_REGNO_P (REGNO (i2src))))
+ || GET_CODE (i2src) == CALL
+ /* Don't substitute into an incremented register. */
+ || find_reg_note (i3, REG_INC, i2dest)
+ || use_crosses_set_p (i2src, INSN_CUID (i2))))
+ return 0;
+ if (GET_CODE (i2src) == ASM_OPERANDS && MEM_VOLATILE_P (i2src))
+ return 0;
+ /* Don't substitute for a register intended as a clobberable operand. */
+ if (GET_CODE (PATTERN (i3)) == PARALLEL)
+ for (i = 0; i < XVECLEN (PATTERN (i3), 0); i++)
+ if (GET_CODE (XVECEXP (PATTERN (i3), 0, i)) == CLOBBER
+ && XEXP (XVECEXP (PATTERN (i3), 0, i), 0) == i2dest)
+ return 0;
+
+ if (i1 != 0)
+ {
+ if (GET_CODE (PATTERN (i1)) != SET)
+ return 0;
+ i1dest = SET_DEST (PATTERN (i1));
+ i1src = SET_SRC (PATTERN (i1));
+ if (GET_CODE (i1dest) == SUBREG)
+ {
+ i1dest = SUBREG_REG (i1dest);
+ i1src = gen_rtx (SUBREG, GET_MODE (i1dest), i1src, 0);
+ }
+ if (i1dest == stack_pointer_rtx)
+ return 0;
+ if (GET_CODE (i1src) == SUBREG
+ && ! MODES_TIEABLE_P (GET_MODE (i1src),
+ GET_MODE (SUBREG_REG (i1src))))
+ return 0;
+ if (GET_CODE (i1dest) != CC0
+ && (GET_CODE (i1dest) != REG
+ || (GET_CODE (i1src) == REG
+ && (!flag_combine_regs
+ || FUNCTION_VALUE_REGNO_P (REGNO (i1src))))
+ || GET_CODE (i1src) == CALL
+ || find_reg_note (i3, REG_INC, i1dest)
+ || find_reg_note (i2, REG_INC, i1dest)
+ || use_crosses_set_p (i1src, INSN_CUID (i1))))
+ return 0;
+ if (GET_CODE (i1src) == ASM_OPERANDS && MEM_VOLATILE_P (i1src))
+ return 0;
+ /* Don't substitute for a register intended as a clobberable operand. */
+ if (GET_CODE (PATTERN (i3)) == PARALLEL)
+ for (i = 0; i < XVECLEN (PATTERN (i3), 0); i++)
+ if (GET_CODE (XVECEXP (PATTERN (i3), 0, i)) == CLOBBER
+ && XEXP (XVECEXP (PATTERN (i3), 0, i), 0) == i1dest)
+ return 0;
+ }
+
+ /* If it is better that two different modes keep two different pseudos,
+ avoid combining them. */
+ if (GET_CODE (PATTERN (i3)) == SET)
+ {
+ rtx i3dest = SET_DEST (PATTERN (i3));
+ while (GET_CODE (i3dest) == SUBREG
+ || GET_CODE (i3dest) == STRICT_LOW_PART
+ || GET_CODE (i3dest) == SIGN_EXTRACT
+ || GET_CODE (i3dest) == ZERO_EXTRACT)
+ i3dest = SUBREG_REG (i3dest);
+
+ if (SET_SRC (PATTERN (i3)) == i2dest
+ && GET_CODE (i3dest) == REG
+ && ! MODES_TIEABLE_P (GET_MODE (i2dest), GET_MODE (i3dest)))
+ return 0;
+ }
+
+ /* If I2 contains anything volatile, reject, unless nothing
+ volatile comes between it and I3. */
+ if (volatile_refs_p (PATTERN (i2)))
+ {
+ rtx insn;
+ for (insn = NEXT_INSN (i2); insn != i3; insn = NEXT_INSN (insn))
+ if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN
+ || GET_CODE (insn) == JUMP_INSN)
+ if (volatile_refs_p (PATTERN (insn)))
+ return 0;
+ }
+ /* Likewise for I1; nothing volatile can come between it and I3,
+ except optionally I2. */
+ if (i1 && volatile_refs_p (PATTERN (i1)))
+ {
+ rtx insn;
+ rtx end = (volatile_refs_p (PATTERN (i2)) ? i2 : i3);
+ for (insn = NEXT_INSN (i1); insn != end; insn = NEXT_INSN (insn))
+ if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN
+ || GET_CODE (insn) == JUMP_INSN)
+ if (volatile_refs_p (PATTERN (insn)))
+ return 0;
+ }
+
+ /* If I1 or I2 contains an autoincrement or autodecrement,
+ make sure that register is not used between there and I3,
+ and not already used in I3 either.
+ Also insist that I3 not be a jump; if it were one
+ and the incremented register were spilled, we would lose. */
+ for (link = REG_NOTES (i2); link; link = XEXP (link, 1))
+ if (REG_NOTE_KIND (link) == REG_INC
+ && (GET_CODE (i3) == JUMP_INSN
+ || reg_used_between_p (XEXP (link, 0), i2, i3)
+ || reg_mentioned_p (XEXP (link, 0), PATTERN (i3))))
+ return 0;
+
+ if (i1)
+ for (link = REG_NOTES (i1); link; link = XEXP (link, 1))
+ if (REG_NOTE_KIND (link) == REG_INC
+ && (GET_CODE (i3) == JUMP_INSN
+ || reg_used_between_p (XEXP (link, 0), i1, i3)
+ || reg_mentioned_p (XEXP (link, 0), PATTERN (i3))))
+ return 0;
+
+ /* If I3 has an inc, then give up if I1 or I2 uses the reg that is inc'd,
+ EXCEPT in one case: I3 has a post-inc in an output operand. */
+ if (!(GET_CODE (PATTERN (i3)) == SET
+ && GET_CODE (SET_SRC (PATTERN (i3))) == REG
+ && GET_CODE (SET_DEST (PATTERN (i3))) == MEM
+ && (GET_CODE (XEXP (SET_DEST (PATTERN (i3)), 0)) == POST_INC
+ || GET_CODE (XEXP (SET_DEST (PATTERN (i3)), 0)) == POST_DEC)))
+ /* It's not the exception. */
+ for (link = REG_NOTES (i3); link; link = XEXP (link, 1))
+ if (REG_NOTE_KIND (link) == REG_INC
+ && (reg_mentioned_p (XEXP (link, 0), PATTERN (i2))
+ || (i1 != 0
+ && reg_mentioned_p (XEXP (link, 0), PATTERN (i1)))))
+ return 0;
+
+ /* Don't combine an insn I1 or I2 that follows a CC0-setting insn.
+ An insn that uses CC0 must not be separated from the one that sets it.
+ It would be more logical to test whether CC0 occurs inside I1 or I2,
+ but that would be much slower, and this ought to be equivalent. */
+ temp = PREV_INSN (i2);
+ while (temp && GET_CODE (temp) == NOTE)
+ temp = PREV_INSN (temp);
+ if (temp && GET_CODE (temp) == INSN && sets_cc0_p (PATTERN (temp)))
+ return 0;
+ if (i1)
+ {
+ temp = PREV_INSN (i2);
+ while (temp && GET_CODE (temp) == NOTE)
+ temp = PREV_INSN (temp);
+ if (temp && GET_CODE (temp) == INSN && sets_cc0_p (PATTERN (temp)))
+ return 0;
+ }
+
+ /* See if the SETs in i1 or i2 need to be kept around in the merged
+ instruction: whenever the value set there is still needed past i3. */
+ added_sets_2 = (GET_CODE (i2dest) != CC0
+ && ! dead_or_set_p (i3, i2dest));
+ if (i1)
+ added_sets_1 = ! (dead_or_set_p (i3, i1dest)
+ || dead_or_set_p (i2, i1dest));
+
+ combine_merges++;
+
+ undobuf.num_undo = 0;
+ undobuf.storage = 0;
+
+ /* Substitute in the latest insn for the regs set by the earlier ones. */
+
+ maxreg = max_reg_num ();
+
+ subst_insn = i3;
+ n_occurrences = 0; /* `subst' counts here */
+
+ newpat = subst (PATTERN (i3), i2dest, i2src);
+ /* Record whether i2's body now appears within i3's body. */
+ i2_is_used = n_occurrences;
+
+ if (i1)
+ {
+ n_occurrences = 0;
+ newpat = subst (newpat, i1dest, i1src);
+ }
+
+ if (GET_CODE (PATTERN (i3)) == SET
+ && SET_DEST (PATTERN (i3)) == cc0_rtx
+ && (GET_CODE (SET_SRC (PATTERN (i3))) == AND
+ || GET_CODE (SET_SRC (PATTERN (i3))) == LSHIFTRT)
+ && next_insn_tests_no_inequality (i3))
+ simplify_set_cc0_and (i3);
+
+ if (max_reg_num () != maxreg)
+ abort ();
+
+ /* If the actions of the earler insns must be kept
+ in addition to substituting them into the latest one,
+ we must make a new PARALLEL for the latest insn
+ to hold additional the SETs. */
+
+ if (added_sets_1 || added_sets_2)
+ {
+ combine_extras++;
+
+ /* Arrange to free later what we allocate now
+ if we don't accept this combination. */
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+
+ if (GET_CODE (newpat) == PARALLEL)
+ {
+ rtvec old = XVEC (newpat, 0);
+ total_sets = XVECLEN (newpat, 0) + added_sets_1 + added_sets_2;
+ newpat = gen_rtx (PARALLEL, VOIDmode, rtvec_alloc (total_sets));
+ bcopy (&old->elem[0], &XVECEXP (newpat, 0, 0),
+ sizeof (old->elem[0]) * old->num_elem);
+ }
+ else
+ {
+ rtx old = newpat;
+ total_sets = 1 + added_sets_1 + added_sets_2;
+ newpat = gen_rtx (PARALLEL, VOIDmode, rtvec_alloc (total_sets));
+ XVECEXP (newpat, 0, 0) = old;
+ }
+ if (added_sets_1)
+ {
+ XVECEXP (newpat, 0, --total_sets) = PATTERN (i1);
+ }
+ if (added_sets_2)
+ {
+ /* If there is no I1, use I2's body as is. */
+ if (i1 == 0
+ /* If I2 was stuck into I3, then anything within it has
+ already had I1 substituted into it when that was done to I3. */
+ || i2_is_used)
+ {
+ XVECEXP (newpat, 0, --total_sets) = PATTERN (i2);
+ }
+ else
+ XVECEXP (newpat, 0, --total_sets)
+ = subst (PATTERN (i2), i1dest, i1src);
+ }
+ }
+
+ /* Fail if an autoincrement side-effect has been duplicated. */
+ if ((i2_is_used > 1 && find_reg_note (i2, REG_INC, 0) != 0)
+ || (i1 != 0 && n_occurrences > 1 && find_reg_note (i1, REG_INC, 0) != 0))
+ {
+ undo_all ();
+ return 0;
+ }
+
+ /* Is the result of combination a valid instruction? */
+ insn_code_number = recog (newpat, i3);
+
+ if (insn_code_number >= 0
+ /* Is the result a reasonable ASM_OPERANDS? */
+ || (check_asm_operands (newpat) && ! added_sets_1 && ! added_sets_2))
+ {
+ /* Yes. Install it. */
+ register int regno;
+ INSN_CODE (i3) = insn_code_number;
+ PATTERN (i3) = newpat;
+ /* If anything was substituted more than once,
+ copy it to avoid invalid shared rtl structure. */
+ copy_substitutions ();
+ /* The data flowing into I2 now flows into I3.
+ But we cannot always move all of I2's LOG_LINKS into I3,
+ since they must go to a setting of a REG from the
+ first use following. If I2 was the first use following a set,
+ I3 is now a use, but it is not the first use
+ if some instruction between I2 and I3 is also a use.
+ Here, for simplicity, we move all the links only if
+ there are no real insns between I2 and I3.
+ Otherwise, we move only links that correspond to regs
+ that used to die in I2. They are always safe to move. */
+ add_links (i3, i2, adjacent_insns_p (i2, i3));
+ /* Most REGs that previously died in I2 now die in I3. */
+ move_deaths (i2src, INSN_CUID (i2), i3);
+ if (GET_CODE (i2dest) == REG)
+ {
+ /* If the reg formerly set in I2 died only once and that was in I3,
+ zero its use count so it won't make `reload' do any work. */
+ regno = REGNO (i2dest);
+ if (! added_sets_2)
+ {
+ reg_n_sets[regno]--;
+ /* Used to check && regno_dead_p (regno, i3) also here. */
+ if (reg_n_sets[regno] == 0
+ && ! (basic_block_live_at_start[0][regno / HOST_BITS_PER_INT]
+ & (1 << (regno % HOST_BITS_PER_INT))))
+ reg_n_refs[regno] = 0;
+ }
+ /* If a ref to REGNO was substituted into I3 from I2,
+ then it still dies there if it previously did.
+ Otherwise either REGNO never did die in I3 so remove_death is safe
+ or this entire life of REGNO is gone so remove its death. */
+ if (!added_sets_2
+ && ! reg_mentioned_p (i2dest, PATTERN (i3)))
+ remove_death (regno, i3);
+ }
+ /* Any registers previously autoincremented in I2
+ are now incremented in I3. */
+ add_incs (i3, REG_NOTES (i2));
+ if (i1)
+ {
+ /* Likewise, merge the info from I1 and get rid of it. */
+ add_links (i3, i1,
+ adjacent_insns_p (i1, i2) && adjacent_insns_p (i2, i3));
+ move_deaths (i1src, INSN_CUID (i1), i3);
+ if (GET_CODE (i1dest) == REG)
+ {
+ regno = REGNO (i1dest);
+ if (! added_sets_1)
+ {
+ reg_n_sets[regno]--;
+ /* Used to also check && regno_dead_p (regno, i3) here. */
+
+ if (reg_n_sets[regno] == 0
+ && ! (basic_block_live_at_start[0][regno / HOST_BITS_PER_INT]
+ & (1 << (regno % HOST_BITS_PER_INT))))
+
+ reg_n_refs[regno] = 0;
+ }
+ /* If a ref to REGNO was substituted into I3 from I1,
+ then it still dies there if it previously did.
+ Else either REGNO never did die in I3 so remove_death is safe
+ or this entire life of REGNO is gone so remove its death. */
+ if (! added_sets_1
+ && ! reg_mentioned_p (i1dest, PATTERN (i3)))
+ remove_death (regno, i3);
+ }
+ add_incs (i3, REG_NOTES (i1));
+ LOG_LINKS (i1) = 0;
+ PUT_CODE (i1, NOTE);
+ NOTE_LINE_NUMBER (i1) = NOTE_INSN_DELETED;
+ NOTE_SOURCE_FILE (i1) = 0;
+ }
+ /* Get rid of I2. */
+ LOG_LINKS (i2) = 0;
+ PUT_CODE (i2, NOTE);
+ NOTE_LINE_NUMBER (i2) = NOTE_INSN_DELETED;
+ NOTE_SOURCE_FILE (i2) = 0;
+
+ combine_successes++;
+ return 1;
+ }
+
+ /* Failure: change I3 back the way it was. */
+ undo_all ();
+
+ return 0;
+}
+\f
+/* Undo all the modifications recorded in undobuf. */
+
+static void
+undo_all ()
+{
+ register int i;
+ if (undobuf.num_undo > MAX_UNDO)
+ undobuf.num_undo = MAX_UNDO;
+ for (i = undobuf.num_undo - 1; i >= 0; i--)
+ *undobuf.undo[i].where = undobuf.undo[i].old_contents;
+ if (undobuf.storage)
+ obfree (undobuf.storage);
+ undobuf.num_undo = 0;
+ undobuf.storage = 0;
+}
+
+/* If this insn had more than one substitution,
+ copy all but one, so that no invalid shared substructure is introduced. */
+
+static void
+copy_substitutions ()
+{
+ register int i;
+ if (undobuf.num_undo > 1)
+ {
+ for (i = undobuf.num_undo - 1; i >= 1; i--)
+ if (! undobuf.undo[i].is_int)
+ *undobuf.undo[i].where = copy_rtx (*undobuf.undo[i].where);
+ }
+}
+
+/* Throughout X, replace FROM with TO, and return the result.
+ The result is TO if X is FROM;
+ otherwise the result is X, but its contents may have been modified.
+ If they were modified, a record was made in undobuf so that
+ undo_all will (among other things) return X to its original state.
+
+ If the number of changes necessary is too much to record to undo,
+ the excess changes are not made, so the result is invalid.
+ The changes already made can still be undone.
+ undobuf.num_undo is incremented for such changes, so by testing that
+ the caller can tell whether the result is valid.
+
+ `n_occurrences' is incremented each time FROM is replaced. */
+
+static rtx
+subst (x, from, to)
+ register rtx x, from, to;
+{
+ register char *fmt;
+ register int len, i;
+ register enum rtx_code code;
+ char was_replaced[2];
+
+#define SUBST(INTO, NEWVAL) \
+ do { if (undobuf.num_undo < MAX_UNDO) \
+ { \
+ undobuf.undo[undobuf.num_undo].where = &INTO; \
+ undobuf.undo[undobuf.num_undo].old_contents = INTO; \
+ undobuf.undo[undobuf.num_undo].is_int = 0; \
+ INTO = NEWVAL; \
+ } \
+ undobuf.num_undo++; } while (0)
+
+#define SUBST_INT(INTO, NEWVAL) \
+ do { if (undobuf.num_undo < MAX_UNDO) \
+ { \
+ struct undo_int *u = (struct undo_int *)&undobuf.undo[undobuf.num_undo];\
+ u->where = &INTO; \
+ u->old_contents = INTO; \
+ u->is_int = 1; \
+ INTO = NEWVAL; \
+ } \
+ undobuf.num_undo++; } while (0)
+
+/* FAKE_EXTEND_SAFE_P (MODE, FROM) is 1 if (subreg:MODE FROM 0) is a safe
+ replacement for (zero_extend:MODE FROM) or (sign_extend:MODE FROM).
+ If it is 0, that cannot be done. We can now do this for any MEM
+ because (SUBREG (MEM...)) is guaranteed to cause the MEM to be reloaded.
+ If not for that, MEM's would very rarely be safe. */
+
+/* Reject MODEs bigger than a word, because we might not be able
+ to reference a two-register group starting with an arbitrary register
+ (and currently gen_lowpart might crash for a SUBREG). */
+
+#define FAKE_EXTEND_SAFE_P(MODE, FROM) \
+ (GET_MODE_SIZE (MODE) <= UNITS_PER_WORD \
+ && (GET_CODE (FROM) == REG || GET_CODE (FROM) == SUBREG \
+ || GET_CODE (FROM) == MEM))
+
+ if (x == from)
+ return to;
+
+ /* It is possible to have a subexpression appear twice in the insn.
+ Suppose that FROM is a register that appears within TO.
+ Then, after that subexpression has been scanned once by `subst',
+ the second time it is scanned, TO may be found. If we were
+ to scan TO here, we would find FROM within it and create a
+ self-referent rtl structure which is completely wrong. */
+ if (x == to)
+ return to;
+
+ code = GET_CODE (x);
+
+ /* A little bit of algebraic simplification here. */
+ switch (code)
+ {
+ /* This case has no effect except to speed things up. */
+ case REG:
+ case CONST_INT:
+ case CONST:
+ case SYMBOL_REF:
+ case LABEL_REF:
+ case PC:
+ case CC0:
+ return x;
+ }
+
+ was_replaced[0] = 0;
+ was_replaced[1] = 0;
+
+ len = GET_RTX_LENGTH (code);
+ fmt = GET_RTX_FORMAT (code);
+
+ /* Don't replace FROM where it is being stored in rather than used. */
+ if (code == SET && SET_DEST (x) == from)
+ fmt = "ie";
+ if (code == SET && GET_CODE (SET_DEST (x)) == SUBREG
+ && SUBREG_REG (SET_DEST (x)) == from)
+ fmt = "ie";
+
+ for (i = 0; i < len; i++)
+ {
+ if (fmt[i] == 'E')
+ {
+ register int j;
+ for (j = XVECLEN (x, i) - 1; j >= 0; j--)
+ {
+ register rtx new;
+ if (XVECEXP (x, i, j) == from)
+ new = to, n_occurrences++;
+ else
+ new = subst (XVECEXP (x, i, j), from, to);
+ if (new != XVECEXP (x, i, j))
+ SUBST (XVECEXP (x, i, j), new);
+ }
+ }
+ else if (fmt[i] == 'e')
+ {
+ register rtx new;
+
+ if (XEXP (x, i) == from)
+ {
+ new = to;
+ n_occurrences++;
+ if (i < 2)
+ was_replaced[i] = 1;
+ }
+ else
+ new = subst (XEXP (x, i), from, to);
+
+ if (new != XEXP (x, i))
+ SUBST (XEXP (x, i), new);
+ }
+ }
+
+ /* A little bit of algebraic simplification here. */
+ switch (code)
+ {
+ case SUBREG:
+ /* Changing mode twice with SUBREG => just change it once,
+ or not at all if changing back to starting mode. */
+ if (SUBREG_REG (x) == to
+ && GET_CODE (to) == SUBREG)
+ {
+ if (GET_MODE (x) == GET_MODE (SUBREG_REG (to)))
+ if (SUBREG_WORD (x) == 0 && SUBREG_WORD (to) == 0)
+ return SUBREG_REG (to);
+ SUBST (SUBREG_REG (x), SUBREG_REG (to));
+ if (SUBREG_WORD (to) != 0)
+ SUBST_INT (SUBREG_WORD (x), SUBREG_WORD (x) + SUBREG_WORD (to));
+ }
+ if (SUBREG_REG (x) == to
+ && (GET_CODE (to) == SIGN_EXTEND || GET_CODE (to) == ZERO_EXTEND)
+ && subreg_lowpart_p (x))
+ {
+ /* (subreg (sign_extend X)) is X, if it has same mode as X. */
+ if (GET_MODE (x) == GET_MODE (XEXP (to, 0)))
+ return XEXP (to, 0);
+ /* (subreg (sign_extend X)), if it has a mode wider than X,
+ can be done with (sign_extend X). */
+ if (GET_MODE_SIZE (GET_MODE (x)) > GET_MODE_SIZE (GET_MODE (XEXP (to, 0))))
+ {
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ return gen_rtx (GET_CODE (to), GET_MODE (x), XEXP (to, 0));
+ }
+ /* Extend and then truncate smaller than it was to start with:
+ no need to extend. */
+ if (GET_MODE_SIZE (GET_MODE (x)) < GET_MODE_SIZE (GET_MODE (XEXP (to, 0))))
+ {
+ SUBST (XEXP (x, 0), XEXP (to, 0));
+ }
+ }
+ /* (subreg:A (mem:B X) N) becomes a modified MEM.
+ If we can't do that safely, then it becomes something nonsensical
+ so that this combination won't take place.
+ This avoids producing any (subreg (mem))s except in the special
+ paradoxical case where gen_lowpart_for_combine makes them. */
+ if (SUBREG_REG (x) == to
+ && GET_CODE (to) == MEM)
+ {
+ int endian_offset = 0;
+ /* Don't combine this if mode A is wider than B. */
+ if (GET_MODE_SIZE (GET_MODE (x)) > GET_MODE_SIZE (GET_MODE (to)))
+ return gen_rtx (CLOBBER, VOIDmode, const0_rtx);
+ /* Don't change the mode of the MEM
+ if that would change the meaning of the address. */
+ if (mode_dependent_address_p (XEXP (to, 0)))
+ return gen_rtx (CLOBBER, VOIDmode, const0_rtx);
+#ifdef BYTES_BIG_ENDIAN
+ if (GET_MODE_SIZE (GET_MODE (x)) < UNITS_PER_WORD)
+ endian_offset += UNITS_PER_WORD - GET_MODE_SIZE (GET_MODE (x));
+ if (GET_MODE_SIZE (GET_MODE (to)) < UNITS_PER_WORD)
+ endian_offset -= UNITS_PER_WORD - GET_MODE_SIZE (GET_MODE (to));
+#endif
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ /* Note if the plus_constant doesn't make a valid address
+ then this combination won't be accepted. */
+ return gen_rtx (MEM, GET_MODE (x),
+ plus_constant (XEXP (to, 0),
+ (SUBREG_WORD (x) * UNITS_PER_WORD
+ + endian_offset)));
+ }
+ break;
+
+ case NOT:
+ /* (not (minus X 1)) can become (neg X). */
+ if (was_replaced[0]
+ && ((GET_CODE (to) == PLUS && INTVAL (XEXP (to, 1)) == -1)
+ || (GET_CODE (to) == MINUS && XEXP (to, 1) == const1_rtx)))
+ {
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ return gen_rtx (NEG, GET_MODE (to), XEXP (to, 0));
+ }
+ /* Don't let substitution introduce double-negatives. */
+ if (was_replaced[0]
+ && GET_CODE (to) == code)
+ return XEXP (to, 0);
+ break;
+
+ case NEG:
+ /* (neg (minus X Y)) can become (minus Y X). */
+ if (was_replaced[0] && GET_CODE (to) == MINUS)
+ {
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ return gen_rtx (MINUS, GET_MODE (to),
+ XEXP (to, 1), XEXP (to, 0));
+ }
+ /* Don't let substitution introduce double-negatives. */
+ if (was_replaced[0]
+ && GET_CODE (to) == code)
+ return XEXP (to, 0);
+ break;
+
+ case FLOAT_TRUNCATE:
+ /* (float_truncate:SF (float_extend:DF foo:SF)) = foo:SF. */
+ if (was_replaced[0]
+ && GET_CODE (to) == FLOAT_EXTEND
+ && GET_MODE (XEXP (to, 0)) == GET_MODE (x))
+ return XEXP (to, 0);
+ break;
+
+#if 0
+ case COMPARE:
+ /* -x>0 if 0>x. */
+ if (GET_CODE (XEXP (x, 0)) == NEG && XEXP (x, 1) == const0_rtx)
+ {
+ SUBST (XEXP (x, 1), XEXP (XEXP (x, 0), 0));
+ SUBST (XEXP (x, 0), const0_rtx);
+ }
+ if (GET_CODE (XEXP (x, 1)) == NEG && XEXP (x, 0) == const0_rtx)
+ {
+ SUBST (XEXP (x, 0), XEXP (XEXP (x, 1), 0));
+ SUBST (XEXP (x, 1), const0_rtx);
+ }
+ break;
+#endif
+
+ case PLUS:
+#if 0 /* Turned off for caution: turn it on after 1.36. */
+ /* Identify constant sums as such. */
+ if ((was_replaced[0] || was_replaced[1])
+ && CONSTANT_P (XEXP (x, 0))
+ && CONSTANT_P (XEXP (x, 1)))
+ {
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ return gen_rtx (CONST, GET_MODE (x), x);
+ }
+#endif
+ /* In (plus <foo> (ashift <bar> <n>))
+ change the shift to a multiply so we can recognize
+ scaled indexed addresses. */
+ if ((was_replaced[0]
+ || was_replaced[1])
+ && GET_CODE (to) == ASHIFT
+ && GET_CODE (XEXP (to, 1)) == CONST_INT
+ && INTVAL (XEXP (to, 1)) < HOST_BITS_PER_INT)
+ {
+ rtx temp;
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ temp = gen_rtx (MULT, GET_MODE (to),
+ XEXP (to, 0),
+ gen_rtx (CONST_INT, VOIDmode,
+ 1 << INTVAL (XEXP (to, 1))));
+ if (was_replaced[0])
+ SUBST (XEXP (x, 0), temp);
+ else
+ SUBST (XEXP (x, 1), temp);
+ }
+ /* (plus X (neg Y)) becomes (minus X Y). */
+ if (GET_CODE (XEXP (x, 1)) == NEG)
+ {
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ return gen_rtx (MINUS, GET_MODE (x),
+ XEXP (x, 0), XEXP (XEXP (x, 1), 0));
+ }
+ /* (plus (neg X) Y) becomes (minus Y X). */
+ if (GET_CODE (XEXP (x, 0)) == NEG)
+ {
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ return gen_rtx (MINUS, GET_MODE (x),
+ XEXP (x, 1), XEXP (XEXP (x, 0), 0));
+ }
+ /* (plus (plus x c1) c2) => (plus x c1+c2) */
+ if (GET_CODE (XEXP (x, 1)) == CONST_INT
+ && GET_CODE (XEXP (x, 0)) == PLUS
+ && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT)
+ {
+ int sum = (INTVAL (XEXP (x, 1))
+ + INTVAL (XEXP (XEXP (x, 0), 1)));
+ if (sum == 0)
+ return XEXP (XEXP (x, 0), 0);
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ SUBST (XEXP (x, 1), gen_rtx (CONST_INT, VOIDmode, sum));
+ SUBST (XEXP (x, 0), XEXP (XEXP (x, 0), 0));
+ break;
+ }
+ /* If we have something (putative index) being added to a sum,
+ associate it so that any constant term is outermost.
+ That's because that's the way indexed addresses are
+ now supposed to appear. */
+ if (((was_replaced[0] && GET_CODE (XEXP (x, 1)) == PLUS)
+ || (was_replaced[1] && GET_CODE (XEXP (x, 0)) == PLUS))
+ ||
+ ((was_replaced[0] || was_replaced[1])
+ && GET_CODE (to) == PLUS))
+ {
+ rtx offset = 0, base, index;
+ if (GET_CODE (to) != PLUS)
+ {
+ index = to;
+ base = was_replaced[0] ? XEXP (x, 1) : XEXP (x, 0);
+ }
+ else
+ {
+ index = was_replaced[0] ? XEXP (x, 1) : XEXP (x, 0);
+ base = to;
+ }
+ if (CONSTANT_ADDRESS_P (XEXP (base, 0)))
+ {
+ offset = XEXP (base, 0);
+ base = XEXP (base, 1);
+ }
+ else if (CONSTANT_ADDRESS_P (XEXP (base, 1)))
+ {
+ offset = XEXP (base, 1);
+ base = XEXP (base, 0);
+ }
+ if (offset != 0)
+ {
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ if (GET_CODE (offset) == CONST_INT)
+ return plus_constant (gen_rtx (PLUS, GET_MODE (index),
+ base, index),
+ INTVAL (offset));
+ if (GET_CODE (index) == CONST_INT)
+ return plus_constant (gen_rtx (PLUS, GET_MODE (offset),
+ base, offset),
+ INTVAL (index));
+ return gen_rtx (PLUS, GET_MODE (index),
+ gen_rtx (PLUS, GET_MODE (index),
+ base, index),
+ offset);
+ }
+ }
+ break;
+
+ case EQ:
+ case NE:
+ /* If comparing a subreg against zero, discard the subreg. */
+ if (was_replaced[0]
+ && GET_CODE (to) == SUBREG
+ && SUBREG_WORD (to) == 0
+ && XEXP (x, 1) == const0_rtx)
+ SUBST (XEXP (x, 0), SUBREG_REG (to));
+
+ /* If comparing a ZERO_EXTRACT against zero,
+ canonicalize to a SIGN_EXTRACT,
+ since the two are equivalent here. */
+ if (was_replaced[0]
+ && GET_CODE (to) == ZERO_EXTRACT
+ && XEXP (x, 1) == const0_rtx)
+ {
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ SUBST (XEXP (x, 0),
+ gen_rtx (SIGN_EXTRACT, GET_MODE (to),
+ XEXP (to, 0), XEXP (to, 1),
+ XEXP (to, 2)));
+ }
+#ifndef BITS_BIG_ENDIAN
+ /* If we are putting (ASHIFT 1 x) into (EQ (AND ... y) 0),
+ arrange to return (EQ (SIGN_EXTRACT y 1 x) 0),
+ which is what jump-on-bit instructions are written with. */
+ else if (XEXP (x, 1) == const0_rtx
+ && GET_CODE (XEXP (x, 0)) == AND
+ && (XEXP (XEXP (x, 0), 0) == to
+ || XEXP (XEXP (x, 0), 1) == to)
+ && GET_CODE (to) == ASHIFT
+ && XEXP (to, 0) == const1_rtx)
+ {
+ register rtx y = XEXP (XEXP (x, 0),
+ XEXP (XEXP (x, 0), 0) == to);
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ SUBST (XEXP (x, 0),
+ gen_rtx (SIGN_EXTRACT, GET_MODE (to),
+ y,
+ const1_rtx, XEXP (to, 1)));
+ }
+#endif /* not BITS_BIG_ENDIAN */
+ /* Negation is a no-op before equality test against zero. */
+ if (GET_CODE (XEXP (x, 0)) == NEG && XEXP (x, 1) == const0_rtx)
+ {
+ SUBST (XEXP (x, 0), XEXP (XEXP (x, 0), 0));
+ }
+ if (GET_CODE (XEXP (x, 1)) == NEG && XEXP (x, 0) == const0_rtx)
+ {
+ SUBST (XEXP (x, 1), XEXP (XEXP (x, 1), 0));
+ }
+ break;
+
+ case ZERO_EXTEND:
+ /* Nested zero-extends are equivalent to just one. */
+ if (was_replaced[0]
+ && GET_CODE (to) == ZERO_EXTEND)
+ SUBST (XEXP (x, 0), XEXP (to, 0));
+ /* Zero extending a constant int can be replaced
+ by a zero-extended constant. */
+ if (was_replaced[0]
+ && HOST_BITS_PER_INT >= GET_MODE_BITSIZE (GET_MODE (from))
+ && GET_CODE (to) == CONST_INT)
+ {
+ int intval = INTVAL (to) & GET_MODE_MASK (GET_MODE (from));
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ return gen_rtx (CONST_INT, VOIDmode, intval);
+ }
+ /* Zero-extending the result of an and with a constant can be done
+ with a wider and. */
+ if (was_replaced[0]
+ && GET_CODE (to) == AND
+ && GET_CODE (XEXP (to, 1)) == CONST_INT
+ && FAKE_EXTEND_SAFE_P (GET_MODE (x), XEXP (to, 0))
+ /* Avoid getting wrong result if the constant has high bits set
+ that are irrelevant in the narrow mode where it is being used. */
+ && 0 == (INTVAL (XEXP (to, 1))
+ & ~ GET_MODE_MASK (GET_MODE (to))))
+ {
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ return gen_rtx (AND, GET_MODE (x),
+ gen_lowpart_for_combine (GET_MODE (x), XEXP (to, 0)),
+ XEXP (to, 1));
+ }
+ /* Change (zero_extend:M (subreg:N (zero_extract:M ...) 0))
+ to (zero_extract:M ...) if the field extracted fits in mode N. */
+ if (GET_CODE (XEXP (x, 0)) == SUBREG
+ && GET_CODE (XEXP (XEXP (x, 0), 0)) == ZERO_EXTRACT
+ && GET_CODE (XEXP (XEXP (XEXP (x, 0), 0), 1)) == CONST_INT
+ && (INTVAL (XEXP (XEXP (XEXP (x, 0), 0), 1))
+ <= GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0)))))
+ {
+ return XEXP (XEXP (x, 0), 0);
+ }
+ /* Change (zero_extend:M (subreg:N (and:M ... <const>) 0))
+ to (and:M ...) if the significant bits fit in mode N. */
+ if (GET_CODE (XEXP (x, 0)) == SUBREG
+ && SUBREG_REG (XEXP (x, 0)) == to
+ && SUBREG_WORD (XEXP (x, 0)) == 0
+ && GET_CODE (to) == AND
+ && GET_CODE (XEXP (to, 1)) == CONST_INT
+ && FAKE_EXTEND_SAFE_P (GET_MODE (x), XEXP (to, 0))
+ /* Avoid getting wrong result if the constant has high bits set
+ that are irrelevant in the narrow mode where it is being used. */
+ && 0 == (INTVAL (XEXP (to, 1))
+ & ~ GET_MODE_MASK (GET_MODE (to))))
+ {
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ return gen_rtx (AND, GET_MODE (x),
+ gen_lowpart_for_combine (GET_MODE (x), XEXP (to, 0)),
+ XEXP (to, 1));
+ }
+ /* In (zero_extend:M (subreg:N (lshiftrt:M REG))),
+ where REG was assigned from (zero_extend:M (any:N ...)),
+ remove the outer zero extension. */
+ if (GET_CODE (XEXP (x, 0)) == SUBREG
+ && SUBREG_REG (XEXP (x, 0)) == to
+ && SUBREG_WORD (XEXP (x, 0)) == 0
+ && GET_CODE (to) == LSHIFTRT)
+ {
+ rtx tmp = XEXP (to, 0);
+
+ /* See if arg of LSHIFTRT is a register whose value we can find. */
+ if (GET_CODE (tmp) == REG)
+ if (reg_n_sets[REGNO (tmp)] == 1
+ && reg_last_set[REGNO (tmp)] != 0
+ && SET_DEST (PATTERN (reg_last_set[REGNO (tmp)])) == tmp)
+ tmp = SET_SRC (PATTERN (reg_last_set[REGNO (tmp)]));
+ else
+ break;
+
+ if (GET_CODE (tmp) == ZERO_EXTEND
+ && GET_MODE (tmp) == GET_MODE (x)
+ && GET_MODE (XEXP (tmp, 0)) == GET_MODE (XEXP (x, 0)))
+ return SUBREG_REG (XEXP (x, 0));
+ }
+ break;
+
+ case SIGN_EXTEND:
+ /* Nested sign-extends are equivalent to just one. */
+ if (was_replaced[0]
+ && GET_CODE (to) == SIGN_EXTEND)
+ SUBST (XEXP (x, 0), XEXP (to, 0));
+ /* Sign extending a constant int can be replaced
+ by a sign-extended constant. */
+ if (was_replaced[0]
+ && HOST_BITS_PER_INT >= GET_MODE_BITSIZE (GET_MODE (from))
+ && GET_CODE (to) == CONST_INT)
+ {
+ int intval = INTVAL (to);
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ if (intval > 0
+ && (intval & (1 << (GET_MODE_BITSIZE (GET_MODE (from)) - 1))))
+ intval |= ~ GET_MODE_MASK (GET_MODE (from));
+ return gen_rtx (CONST_INT, VOIDmode, intval);
+ }
+ /* Sign-extending the result of an and with a constant can be done
+ with a wider and, provided the high bit of the constant is 0. */
+ if (was_replaced[0]
+ && GET_CODE (to) == AND
+ && GET_CODE (XEXP (to, 1)) == CONST_INT
+ && FAKE_EXTEND_SAFE_P (GET_MODE (x), XEXP (to, 0))
+ && ((INTVAL (XEXP (to, 1))
+ & (-1 << (GET_MODE_BITSIZE (GET_MODE (to)) - 1)))
+ == 0))
+ {
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ return gen_rtx (AND, GET_MODE (x),
+ gen_lowpart_for_combine (GET_MODE (x), XEXP (to, 0)),
+ XEXP (to, 1));
+ }
+ /* hacks added by tiemann. */
+ /* Change (sign_extend:M (subreg:N (and:M ... <const>) 0))
+ to (and:M ...), provided the result fits in mode N,
+ and the high bit of the constant is 0 in mode N. */
+ if (GET_CODE (XEXP (x, 0)) == SUBREG
+ && SUBREG_REG (XEXP (x, 0)) == to
+ && SUBREG_WORD (XEXP (x, 0)) == 0
+ && GET_CODE (to) == AND
+ && GET_CODE (XEXP (to, 1)) == CONST_INT
+ && FAKE_EXTEND_SAFE_P (GET_MODE (x), XEXP (to, 0))
+ && ((INTVAL (XEXP (to, 1))
+ & (-1 << (GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0))) - 1)))
+ == 0))
+ {
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ return gen_rtx (AND, GET_MODE (x),
+ gen_lowpart_for_combine (GET_MODE (x), XEXP (to, 0)),
+ XEXP (to, 1));
+ }
+ /* In (sign_extend:M (subreg:N (ashiftrt:M REG))),
+ where REG was assigned from (sign_extend:M (any:N ...)),
+ remove the outer sign extension. */
+ if (GET_CODE (XEXP (x, 0)) == SUBREG
+ && SUBREG_REG (XEXP (x, 0)) == to
+ && SUBREG_WORD (XEXP (x, 0)) == 0
+ && GET_CODE (to) == ASHIFTRT)
+ {
+ rtx tmp = XEXP (to, 0);
+
+ /* See if arg of LSHIFTRT is a register whose value we can find. */
+ if (GET_CODE (tmp) == REG)
+ if (reg_n_sets[REGNO (tmp)] == 1
+ && reg_last_set[REGNO (tmp)] != 0
+ && SET_DEST (PATTERN (reg_last_set[REGNO (tmp)])) == tmp)
+ tmp = SET_SRC (PATTERN (reg_last_set[REGNO (tmp)]));
+ else
+ break;
+
+ if (GET_CODE (tmp) == SIGN_EXTEND
+ && GET_MODE (tmp) == GET_MODE (x)
+ && GET_MODE (XEXP (tmp, 0)) == GET_MODE (XEXP (x, 0)))
+ return SUBREG_REG (XEXP (x, 0));
+ }
+ break;
+
+ case SET:
+ /* In (set (zero-extract <x> <n> <y>) (and <foo> <(2**n-1) | anything>))
+ the `and' can be deleted. This can happen when storing a bit
+ that came from a set-flag insn followed by masking to one bit. */
+ if (GET_CODE (XEXP (x, 0)) == ZERO_EXTRACT
+ && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
+ && was_replaced[1]
+ && GET_CODE (to) == AND
+ && GET_CODE (XEXP (to, 1)) == CONST_INT
+ && 0 == (((1 << INTVAL (XEXP (XEXP (x, 0), 1))) - 1)
+ & ~ INTVAL (XEXP (to, 1))))
+ {
+ SUBST (XEXP (x, 1), XEXP (to, 0));
+ }
+ /* In (set (zero-extract <x> <n> <y>)
+ (subreg (and <foo> <(2**n-1) | anything>)))
+ the `and' can be deleted. */
+ if (GET_CODE (XEXP (x, 0)) == ZERO_EXTRACT
+ && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
+ && GET_CODE (XEXP (x, 1)) == SUBREG
+ && SUBREG_WORD (XEXP (x, 1)) == 0
+ && GET_CODE (SUBREG_REG (XEXP (x, 1))) == AND
+ && GET_CODE (XEXP (SUBREG_REG (XEXP (x, 1)), 1)) == CONST_INT
+ && 0 == (((1 << INTVAL (XEXP (XEXP (x, 0), 1))) - 1)
+ & ~ INTVAL (XEXP (SUBREG_REG (XEXP (x, 1)), 1))))
+ {
+ SUBST (SUBREG_REG (XEXP (x, 1)), XEXP (SUBREG_REG (XEXP (x, 1)), 0));
+ }
+ /* (set (zero_extract ...) (and/or/xor (zero_extract ...) const)),
+ if both zero_extracts have the same location, size and position,
+ can be changed to avoid the byte extracts. */
+ if ((GET_CODE (XEXP (x, 0)) == ZERO_EXTRACT
+ || GET_CODE (XEXP (x, 0)) == SIGN_EXTRACT)
+ && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
+ && (GET_CODE (XEXP (x, 1)) == AND
+ || GET_CODE (XEXP (x, 1)) == IOR
+ || GET_CODE (XEXP (x, 1)) == XOR)
+ && rtx_equal_p (XEXP (x, 0), XEXP (XEXP (x, 1), 0))
+ && GET_CODE (XEXP (XEXP (x, 1), 0)) == GET_CODE (XEXP (x, 0))
+ && GET_CODE (XEXP (XEXP (x, 1), 1)) == CONST_INT
+ /* zero_extract can apply to a QImode even if the bits extracted
+ don't fit inside that byte. In such a case, we may not do this
+ optimization, since the OR or AND insn really would need
+ to fit in a byte. */
+ && (INTVAL (XEXP (XEXP (x, 0), 1)) + INTVAL (XEXP (XEXP (x, 0), 2))
+ < GET_MODE_BITSIZE (GET_MODE (XEXP (XEXP (x, 0), 0)))))
+ {
+ int shiftcount;
+ int newmask;
+#ifdef BITS_BIG_ENDIAN
+ shiftcount
+ = GET_MODE_BITSIZE (GET_MODE (XEXP (XEXP (x, 0), 0)))
+ - INTVAL (XEXP (XEXP (x, 0), 1)) - INTVAL (XEXP (XEXP (x, 0), 2));
+#else
+ shiftcount
+ = INTVAL (XEXP (XEXP (x, 0), 2));
+#endif
+ newmask = ((INTVAL (XEXP (XEXP (x, 1), 1)) << shiftcount)
+ + (GET_CODE (XEXP (x, 1)) == AND
+ ? (1 << shiftcount) - 1
+ : 0));
+ if (GET_MODE_BITSIZE (GET_MODE (XEXP (XEXP (x, 0), 0)))
+ < HOST_BITS_PER_INT)
+ newmask &= (1 << GET_MODE_BITSIZE (GET_MODE (XEXP (XEXP (x, 0), 0)))) - 1;
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ return
+ gen_rtx (SET, VOIDmode,
+ XEXP (XEXP (x, 0), 0),
+ gen_rtx (GET_CODE (XEXP (x, 1)),
+ GET_MODE (XEXP (XEXP (x, 0), 0)),
+ XEXP (XEXP (XEXP (x, 1), 0), 0),
+ gen_rtx (CONST_INT, VOIDmode, newmask)));
+ }
+ /* Can simplify (set (cc0) (compare (zero/sign_extend FOO) CONST))
+ to (set (cc0) (compare FOO CONST)) if CONST fits in FOO's mode
+ and we are only testing equality.
+ In fact, this is valid for zero_extend if what follows is an
+ unsigned comparison, and for sign_extend with a signed comparison. */
+ if (SET_DEST (x) == cc0_rtx
+ && GET_CODE (SET_SRC (x)) == COMPARE
+ && (GET_CODE (XEXP (SET_SRC (x), 0)) == ZERO_EXTEND
+ || GET_CODE (XEXP (SET_SRC (x), 0)) == SIGN_EXTEND)
+ && next_insn_tests_no_inequality (subst_insn)
+ && GET_CODE (XEXP (SET_SRC (x), 1)) == CONST_INT
+ /* This is overly cautious by one bit, but saves worrying about
+ whether it is zero-extension or sign extension. */
+ && ((unsigned) INTVAL (XEXP (SET_SRC (x), 1))
+ < (1 << (GET_MODE_BITSIZE (GET_MODE (XEXP (XEXP (SET_SRC (x), 0), 0))) - 1))))
+ SUBST (XEXP (SET_SRC (x), 0), XEXP (XEXP (SET_SRC (x), 0), 0));
+ break;
+
+ case AND:
+ if (GET_CODE (XEXP (x, 1)) == CONST_INT)
+ {
+ rtx tem = simplify_and_const_int (x, to);
+ if (tem)
+ return tem;
+ }
+ break;
+
+ case IOR:
+ case XOR:
+ /* (ior (ior x c1) c2) => (ior x c1|c2); likewise for xor. */
+ if (GET_CODE (XEXP (x, 1)) == CONST_INT
+ && GET_CODE (XEXP (x, 0)) == code
+ && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT)
+ {
+ int c0 = INTVAL (XEXP (x, 1));
+ int c1 = INTVAL (XEXP (XEXP (x, 0), 1));
+ int combined = (code == IOR ? c0 | c1 : c0 ^ c1);
+
+ if (combined == 0)
+ return XEXP (XEXP (x, 0), 0);
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ SUBST (XEXP (x, 1), gen_rtx (CONST_INT, VOIDmode, combined));
+ SUBST (XEXP (x, 0), XEXP (XEXP (x, 0), 0));
+ break;
+ }
+
+ case FLOAT:
+ /* (float (sign_extend <X>)) = (float <X>). */
+ if (was_replaced[0]
+ && GET_CODE (to) == SIGN_EXTEND)
+ SUBST (XEXP (x, 0), XEXP (to, 0));
+ break;
+
+ case ZERO_EXTRACT:
+ /* (ZERO_EXTRACT (TRUNCATE x)...)
+ can become (ZERO_EXTRACT x ...). */
+ if (was_replaced[0]
+ && GET_CODE (to) == TRUNCATE)
+ {
+#ifdef BITS_BIG_ENDIAN
+ if (GET_CODE (XEXP (x, 2)) == CONST_INT)
+ {
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ /* On a big-endian machine, must increment the bit-number
+ since sign bit is farther away in the pre-truncated value. */
+ return gen_rtx (ZERO_EXTRACT, GET_MODE (x),
+ XEXP (to, 0),
+ XEXP (x, 1),
+ gen_rtx (CONST_INT, VOIDmode,
+ (INTVAL (XEXP (x, 2))
+ + GET_MODE_BITSIZE (GET_MODE (XEXP (to, 0)))
+ - GET_MODE_BITSIZE (GET_MODE (to)))));
+ }
+#else
+ SUBST (XEXP (x, 0), XEXP (to, 0));
+#endif
+ }
+ /* Extracting a single bit from the result of a shift:
+ see which bit it was before the shift and extract that directly. */
+ if (was_replaced[0]
+ && (GET_CODE (to) == ASHIFTRT || GET_CODE (to) == LSHIFTRT
+ || GET_CODE (to) == ASHIFT || GET_CODE (to) == LSHIFT)
+ && GET_CODE (XEXP (to, 1)) == CONST_INT
+ && XEXP (x, 1) == const1_rtx
+ && GET_CODE (XEXP (x, 2)) == CONST_INT)
+ {
+ int shift = INTVAL (XEXP (to, 1));
+ int newpos;
+ if (GET_CODE (to) == ASHIFT || GET_CODE (to) == LSHIFT)
+ shift = - shift;
+#ifdef BITS_BIG_ENDIAN
+ shift = - shift;
+#endif
+ newpos = INTVAL (XEXP (x, 2)) + shift;
+ if (newpos >= 0 &&
+ newpos < GET_MODE_BITSIZE (GET_MODE (to)))
+ {
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ return gen_rtx (ZERO_EXTRACT, GET_MODE (x),
+ XEXP (to, 0), const1_rtx,
+ gen_rtx (CONST_INT, VOIDmode, newpos));
+ }
+ }
+ break;
+
+ case LSHIFTRT:
+ case ASHIFTRT:
+ case ROTATE:
+ case ROTATERT:
+#ifdef SHIFT_COUNT_TRUNCATED
+ /* (lshift <X> (sign_extend <Y>)) = (lshift <X> <Y>) (most machines).
+ True for all kinds of shifts and also for zero_extend. */
+ if (was_replaced[1]
+ && (GET_CODE (to) == SIGN_EXTEND
+ || GET_CODE (to) == ZERO_EXTEND)
+ && FAKE_EXTEND_SAFE_P (GET_MODE (to), XEXP (to, 0)))
+ {
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ SUBST (XEXP (x, 1),
+ /* This is a perverse SUBREG, wider than its base. */
+ gen_lowpart_for_combine (GET_MODE (to), XEXP (to, 0)));
+ }
+#endif
+ /* Two shifts in a row of same kind
+ in same direction with constant counts
+ may be combined. */
+ if (was_replaced[0]
+ && GET_CODE (to) == GET_CODE (x)
+ && GET_CODE (XEXP (x, 1)) == CONST_INT
+ && GET_CODE (XEXP (to, 1)) == CONST_INT
+ && INTVAL (XEXP (to, 1)) > 0
+ && INTVAL (XEXP (x, 1)) > 0
+ && (INTVAL (XEXP (x, 1)) + INTVAL (XEXP (to, 1))
+ < GET_MODE_BITSIZE (GET_MODE (x))))
+ {
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ return gen_rtx (GET_CODE (x), GET_MODE (x),
+ XEXP (to, 0),
+ gen_rtx (CONST_INT, VOIDmode,
+ INTVAL (XEXP (x, 1))
+ + INTVAL (XEXP (to, 1))));
+ }
+ break;
+
+ case LSHIFT:
+ case ASHIFT:
+#ifdef SHIFT_COUNT_TRUNCATED
+ /* (lshift <X> (sign_extend <Y>)) = (lshift <X> <Y>) (most machines).
+ True for all kinds of shifts and also for zero_extend. */
+ if (was_replaced[1]
+ && (GET_CODE (to) == SIGN_EXTEND
+ || GET_CODE (to) == ZERO_EXTEND)
+ && FAKE_EXTEND_SAFE_P (GET_MODE (to), XEXP (to, 0)))
+ {
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ SUBST (XEXP (x, 1),
+ /* This is a perverse SUBREG, wider than its base. */
+ gen_lowpart_for_combine (GET_MODE (to), XEXP (to, 0)));
+ }
+#endif
+ /* (lshift (and (lshiftrt <foo> <X>) <Y>) <X>)
+ happens copying between bit fields in similar structures.
+ It can be replaced by one and instruction.
+ It does not matter whether the shifts are logical or arithmetic. */
+ if (GET_CODE (XEXP (x, 0)) == AND
+ && GET_CODE (XEXP (x, 1)) == CONST_INT
+ && INTVAL (XEXP (x, 1)) > 0
+ && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
+ && XEXP (XEXP (x, 0), 0) == to
+ && (GET_CODE (to) == LSHIFTRT
+ || GET_CODE (to) == ASHIFTRT)
+#if 0
+/* I now believe this restriction is unnecessary.
+ The outer shift will discard those bits in any case, right? */
+
+ /* If inner shift is arithmetic, either it shifts left or
+ the bits it shifts the sign into are zeroed by the and. */
+ && (INTVAL (XEXP (x, 1)) < 0
+ || ((unsigned) INTVAL (XEXP (XEXP (x, 0), 1))
+ < 1 << (GET_MODE_BITSIZE (GET_MODE (x))
+ - INTVAL (XEXP (x, 0)))))
+#endif
+ && GET_CODE (XEXP (to, 1)) == CONST_INT
+ && INTVAL (XEXP (x, 1)) == INTVAL (XEXP (to, 1)))
+ {
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ /* The constant in the new `and' is <Y> << <X>
+ but clear out all bits that don't belong in our mode. */
+ return gen_rtx (AND, GET_MODE (x), XEXP (to, 0),
+ gen_rtx (CONST_INT, VOIDmode,
+ (GET_MODE_MASK (GET_MODE (x))
+ & ((GET_MODE_MASK (GET_MODE (x))
+ & INTVAL (XEXP (XEXP (x, 0), 1)))
+ << INTVAL (XEXP (x, 1))))));
+ }
+ /* Two shifts in a row in same direction with constant counts
+ may be combined. */
+ if (was_replaced[0]
+ && (GET_CODE (to) == ASHIFT || GET_CODE (to) == LSHIFT)
+ && GET_CODE (XEXP (x, 1)) == CONST_INT
+ && GET_CODE (XEXP (to, 1)) == CONST_INT
+ && INTVAL (XEXP (to, 1)) > 0
+ && INTVAL (XEXP (x, 1)) > 0
+ && (INTVAL (XEXP (x, 1)) + INTVAL (XEXP (to, 1))
+ < GET_MODE_BITSIZE (GET_MODE (x))))
+ {
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ return gen_rtx (GET_CODE (x), GET_MODE (x),
+ XEXP (to, 0),
+ gen_rtx (CONST_INT, VOIDmode,
+ INTVAL (XEXP (x, 1))
+ + INTVAL (XEXP (to, 1))));
+ }
+ /* (ashift (ashiftrt <foo> <X>) <X>)
+ (or, on some machines, (ashift (ashift <foo> <-X>) <X>) instead)
+ happens if you divide by 2**N and then multiply by 2**N.
+ It can be replaced by one `and' instruction.
+ It does not matter whether the shifts are logical or arithmetic. */
+ if (GET_CODE (XEXP (x, 1)) == CONST_INT
+ && INTVAL (XEXP (x, 1)) > 0
+ && was_replaced[0]
+ && (((GET_CODE (to) == LSHIFTRT || GET_CODE (to) == ASHIFTRT)
+ && GET_CODE (XEXP (to, 1)) == CONST_INT
+ && INTVAL (XEXP (x, 1)) == INTVAL (XEXP (to, 1)))
+ ||
+ ((GET_CODE (to) == LSHIFT || GET_CODE (to) == ASHIFT)
+ && GET_CODE (XEXP (to, 1)) == CONST_INT
+ && INTVAL (XEXP (x, 1)) == - INTVAL (XEXP (to, 1)))))
+ {
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ /* The constant in the new `and' is -1 << <X>
+ but clear out all bits that don't belong in our mode. */
+ return gen_rtx (AND, GET_MODE (x), XEXP (to, 0),
+ gen_rtx (CONST_INT, VOIDmode,
+ (GET_MODE_MASK (GET_MODE (x))
+ & (GET_MODE_MASK (GET_MODE (x))
+ << INTVAL (XEXP (x, 1))))));
+ }
+
+ }
+
+ return x;
+}
+
+/* This is the AND case of the function subst. */
+
+static rtx
+simplify_and_const_int (x, to)
+ rtx x, to;
+{
+ register rtx varop = XEXP (x, 0);
+ register int constop = INTVAL (XEXP (x, 1));
+
+ /* (and (subreg (and <foo> <constant>) 0) <constant>)
+ results from an andsi followed by an andqi,
+ which happens frequently when storing bit-fields
+ on something whose result comes from an andsi. */
+ if (GET_CODE (varop) == SUBREG
+ && XEXP (varop, 0) == to
+ && subreg_lowpart_p (varop)
+ && GET_CODE (to) == AND
+ && GET_CODE (XEXP (to, 1)) == CONST_INT
+ /* Verify that the result of the outer `and'
+ is not affected by any bits not defined in the inner `and'.
+ True if the outer mode is narrower, or if the outer constant
+ masks to zero all the bits that the inner mode doesn't have. */
+ && (GET_MODE_SIZE (GET_MODE (x)) < GET_MODE_SIZE (GET_MODE (to))
+ || (constop & ~ GET_MODE_MASK (GET_MODE (to))) == 0))
+ {
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ return gen_rtx (AND, GET_MODE (x),
+ gen_lowpart_for_combine (GET_MODE (x), XEXP (to, 0)),
+ gen_rtx (CONST_INT, VOIDmode,
+ constop
+ /* Remember that the bits outside that mode
+ are not being changed, so the effect
+ is as if they were all 1. */
+ & INTVAL (XEXP (to, 1))));
+ }
+ /* (and:SI (zero_extract:SI ...) <constant>)
+ results from an andsi following a byte-fetch on risc machines.
+ When the constant includes all bits extracted, eliminate the `and'. */
+ if (GET_CODE (varop) == ZERO_EXTRACT
+ && GET_CODE (XEXP (varop, 1)) == CONST_INT
+ /* The `and' must not clear any bits that the extract can give. */
+ && (~ constop & ((1 << INTVAL (XEXP (varop, 1))) - 1)) == 0)
+ return varop;
+ /* (and (zero_extend <foo>) <constant>)
+ often results from storing in a bit-field something
+ that was calculated as a short. Replace with a single `and'
+ in whose constant all bits not in <foo>'s mode are zero. */
+ if (varop == to
+ && GET_CODE (to) == ZERO_EXTEND
+ && FAKE_EXTEND_SAFE_P (GET_MODE (x), XEXP (to, 0)))
+ {
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ return gen_rtx (AND, GET_MODE (x),
+ /* This is a perverse SUBREG, wider than its base. */
+ gen_lowpart_for_combine (GET_MODE (x), XEXP (to, 0)),
+ gen_rtx (CONST_INT, VOIDmode,
+ constop & GET_MODE_MASK (GET_MODE (XEXP (to, 0)))));
+ }
+ /* (and (sign_extend <foo>) <constant>)
+ can be replaced with (and (subreg <foo>) <constant>)
+ if <constant> is narrower than <foo>'s mode,
+ or with (zero_extend <foo>) if <constant> is a mask for that mode. */
+ if (varop == to
+ && GET_CODE (to) == SIGN_EXTEND
+ && ((unsigned) constop <= GET_MODE_MASK (GET_MODE (XEXP (to, 0))))
+ && FAKE_EXTEND_SAFE_P (GET_MODE (x), XEXP (to, 0)))
+ {
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ if (constop == GET_MODE_MASK (GET_MODE (XEXP (to, 0))))
+ return gen_rtx (ZERO_EXTEND, GET_MODE (x), XEXP (to, 0));
+ return gen_rtx (AND, GET_MODE (x),
+ /* This is a perverse SUBREG, wider than its base. */
+ gen_lowpart_for_combine (GET_MODE (x), XEXP (to, 0)),
+ XEXP (x, 1));
+ }
+ /* (and (and <foo> <constant>) <constant>)
+ comes from two and instructions in a row. */
+ if (varop == to
+ && GET_CODE (to) == AND
+ && GET_CODE (XEXP (to, 1)) == CONST_INT)
+ {
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ return gen_rtx (AND, GET_MODE (x),
+ XEXP (to, 0),
+ gen_rtx (CONST_INT, VOIDmode,
+ constop
+ & INTVAL (XEXP (to, 1))));
+ }
+ /* (and (ashiftrt (ashift FOO N) N) CONST)
+ may be simplified to (and FOO CONST) if CONST masks off the bits
+ changed by the two shifts. */
+ if (GET_CODE (varop) == ASHIFTRT
+ && GET_CODE (XEXP (varop, 1)) == CONST_INT
+ && XEXP (varop, 0) == to
+ && GET_CODE (to) == ASHIFT
+ && GET_CODE (XEXP (to, 1)) == CONST_INT
+ && INTVAL (XEXP (varop, 1)) == INTVAL (XEXP (to, 1))
+ && ((unsigned) constop >> INTVAL (XEXP (varop, 1))) == 0)
+ {
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ /* If CONST is a mask for the low byte,
+ change this into a zero-extend instruction
+ from just the low byte of FOO. */
+ if (constop == GET_MODE_MASK (QImode))
+ {
+ rtx temp = gen_lowpart_for_combine (QImode, XEXP (to, 0));
+ if (GET_CODE (temp) != CLOBBER)
+ return gen_rtx (ZERO_EXTEND, GET_MODE (x), temp);
+ }
+ return gen_rtx (AND, GET_MODE (x),
+ XEXP (to, 0), XEXP (x, 1));
+ }
+ /* (and (ashiftrt (zero_extend FOO) N) CONST)
+ may be simplified to (and (ashiftrt (subreg FOO) N) CONST)
+ if CONST masks off the bits changed by extension. */
+ if ((GET_CODE (varop) == ASHIFTRT || GET_CODE (varop) == LSHIFTRT)
+ && GET_CODE (XEXP (varop, 1)) == CONST_INT
+ && XEXP (varop, 0) == to
+ && (GET_CODE (to) == ZERO_EXTEND || GET_CODE (to) == SIGN_EXTEND)
+ /* Verify the and discards all the extended bits. */
+ && (((unsigned) constop << INTVAL (XEXP (varop, 1)))
+ >> GET_MODE_BITSIZE (GET_MODE (XEXP (to, 0)))) == 0
+ && FAKE_EXTEND_SAFE_P (GET_MODE (x), XEXP (to, 0)))
+ {
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ SUBST (XEXP (varop, 0),
+ gen_lowpart_for_combine (GET_MODE (x), XEXP (to, 0)));
+ return x;
+ }
+ /* (and x const) may be converted to (zero_extend (subreg x 0)). */
+ if (constop == GET_MODE_MASK (QImode)
+ && GET_CODE (varop) == REG)
+ {
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ return gen_rtx (ZERO_EXTEND, GET_MODE (x),
+ gen_rtx (SUBREG, QImode, varop, 0));
+ }
+ if (constop == GET_MODE_MASK (HImode)
+ && GET_CODE (varop) == REG)
+ {
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+ return gen_rtx (ZERO_EXTEND, GET_MODE (x),
+ gen_rtx (SUBREG, HImode, varop, 0));
+ }
+ /* No simplification applies. */
+ return 0;
+}
+
+/* Like gen_lowpart but for use by combine. In combine it is not possible
+ to create any new pseudoregs. However, it is safe to create
+ invalid memory addresses, because combine will try to recognize
+ them and all they will do is make the combine attempt fail.
+
+ If for some reason this cannot do its job, an rtx
+ (clobber (const_int 0)) is returned.
+ An insn containing that will not be recognized. */
+
+#undef gen_lowpart
+
+static rtx
+gen_lowpart_for_combine (mode, x)
+ enum machine_mode mode;
+ register rtx x;
+{
+ if (GET_CODE (x) == SUBREG || GET_CODE (x) == REG)
+ return gen_lowpart (mode, x);
+ if (GET_MODE (x) == mode)
+ return gen_rtx (CLOBBER, VOIDmode, const0_rtx);
+ if (GET_CODE (x) == MEM)
+ {
+ register int offset = 0;
+
+ /* Refuse to work on a volatile memory ref. */
+ if (MEM_VOLATILE_P (x))
+ return gen_rtx (CLOBBER, VOIDmode, const0_rtx);
+
+ /* If we want to refer to something bigger than the original memref,
+ generate a perverse subreg instead. That will force a reload
+ of the original memref X. */
+ if (GET_MODE_SIZE (GET_MODE (x)) < GET_MODE_SIZE (mode))
+ return gen_rtx (SUBREG, mode, x, 0);
+
+#ifdef WORDS_BIG_ENDIAN
+ offset = (max (GET_MODE_SIZE (GET_MODE (x)), UNITS_PER_WORD)
+ - max (GET_MODE_SIZE (mode), UNITS_PER_WORD));
+#endif
+#ifdef BYTES_BIG_ENDIAN
+ /* Adjust the address so that the address-after-the-data
+ is unchanged. */
+ offset -= (min (UNITS_PER_WORD, GET_MODE_SIZE (mode))
+ - min (UNITS_PER_WORD, GET_MODE_SIZE (GET_MODE (x))));
+#endif
+ return gen_rtx (MEM, mode, plus_constant (XEXP (x, 0),
+ offset));
+ }
+ else
+ return gen_rtx (CLOBBER, VOIDmode, const0_rtx);
+}
+\f
+/* After substitution, if the resulting pattern looks like
+ (set (cc0) (and ...)) or (set (cc0) (lshiftrt ...)),
+ this function is called to simplify the
+ pattern into a bit-field operation if possible. */
+
+static void
+simplify_set_cc0_and (insn)
+ rtx insn;
+{
+ register rtx value = XEXP (PATTERN (insn), 1);
+ register rtx op0 = XEXP (value, 0);
+ register rtx op1 = XEXP (value, 1);
+ int offset = 0;
+ rtx var = 0;
+ rtx bitnum = 0;
+ int temp;
+ int unit;
+ rtx newpat;
+
+ if (GET_CODE (value) == AND)
+ {
+ op0 = XEXP (value, 0);
+ op1 = XEXP (value, 1);
+ }
+ else if (GET_CODE (value) == LSHIFTRT)
+ {
+ /* If there is no AND, but there is a shift that discards
+ all but the sign bit, we can pretend that the shift result
+ is ANDed with 1. Otherwise we cannot handle just a shift. */
+ if (GET_CODE (XEXP (value, 1)) == CONST_INT
+ && (INTVAL (XEXP (value, 1))
+ == GET_MODE_BITSIZE (GET_MODE (value)) - 1))
+ {
+ op0 = value;
+ op1 = const1_rtx;
+ }
+ else
+ return;
+ }
+ else
+ abort ();
+
+ /* Look for a constant power of 2 or a shifted 1
+ on either side of the AND. Set VAR to the other side.
+ Set BITNUM to the shift count of the 1 (as an rtx).
+ Or, if bit number is constant, set OFFSET to the bit number. */
+
+ switch (GET_CODE (op0))
+ {
+ case CONST_INT:
+ temp = exact_log2 (INTVAL (op0));
+ if (temp < 0)
+ return;
+ offset = temp;
+ var = op1;
+ break;
+
+ case ASHIFT:
+ case LSHIFT:
+ if (XEXP (op0, 0) == const1_rtx)
+ {
+ bitnum = XEXP (op0, 1);
+ var = op1;
+ }
+ }
+ if (var == 0)
+ switch (GET_CODE (op1))
+ {
+ case CONST_INT:
+ temp = exact_log2 (INTVAL (op1));
+ if (temp < 0)
+ return;
+ offset = temp;
+ var = op0;
+ break;
+
+ case ASHIFT:
+ case LSHIFT:
+ if (XEXP (op1, 0) == const1_rtx)
+ {
+ bitnum = XEXP (op1, 1);
+ var = op0;
+ }
+ }
+
+ /* If VAR is 0, we didn't find something recognizable. */
+ if (var == 0)
+ return;
+
+ if (!undobuf.storage)
+ undobuf.storage = (char *) oballoc (0);
+
+ /* If the bit position is currently exactly 0,
+ extract a right-shift from the variable portion. */
+ if (offset == 0
+ && (GET_CODE (var) == ASHIFTRT || GET_CODE (var) == LSHIFTRT))
+ {
+ bitnum = XEXP (var, 1);
+ var = XEXP (var, 0);
+ }
+
+ if (GET_CODE (var) == SUBREG && SUBREG_WORD (var) == 0)
+ var = SUBREG_REG (var);
+
+ /* Note that BITNUM and OFFSET are always little-endian thru here
+ even on a big-endian machine. */
+
+#ifdef BITS_BIG_ENDIAN
+ unit = GET_MODE_BITSIZE (GET_MODE (var)) - 1;
+
+ if (bitnum != 0)
+ bitnum = gen_rtx (MINUS, SImode,
+ gen_rtx (CONST_INT, VOIDmode, unit), bitnum);
+ else
+ offset = unit - offset;
+#endif
+
+ if (bitnum == 0)
+ bitnum = gen_rtx (CONST_INT, VOIDmode, offset);
+
+ newpat = gen_rtx (SET, VOIDmode, cc0_rtx,
+ gen_rtx (ZERO_EXTRACT, VOIDmode, var, const1_rtx, bitnum));
+ if (recog (newpat, insn) >= 0)
+ {
+ if (undobuf.num_undo < MAX_UNDO)
+ {
+ undobuf.undo[undobuf.num_undo].where = &XEXP (PATTERN (insn), 1);
+ undobuf.undo[undobuf.num_undo].old_contents = value;
+ XEXP (PATTERN (insn), 1) = XEXP (newpat, 1);
+ }
+ undobuf.num_undo++;
+ }
+}
+\f
+/* Update the records of when each REG was most recently set or killed
+ for the things done by INSN. This is the last thing done in processing
+ INSN in the combiner loop.
+
+ We update reg_last_set, reg_last_death, and also the similar information
+ mem_last_set (which insn most recently modified memory)
+ and last_call_cuid (which insn was the most recent subroutine call). */
+
+static void
+record_dead_and_set_regs (insn)
+ rtx insn;
+{
+ register rtx link;
+ for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
+ {
+ if (REG_NOTE_KIND (link) == REG_DEAD)
+ reg_last_death[REGNO (XEXP (link, 0))] = insn;
+ else if (REG_NOTE_KIND (link) == REG_INC)
+ reg_last_set[REGNO (XEXP (link, 0))] = insn;
+ }
+
+ if (GET_CODE (insn) == CALL_INSN)
+ last_call_cuid = mem_last_set = INSN_CUID (insn);
+
+ if (GET_CODE (PATTERN (insn)) == PARALLEL)
+ {
+ register int i;
+ for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
+ {
+ register rtx elt = XVECEXP (PATTERN (insn), 0, i);
+ register enum rtx_code code = GET_CODE (elt);
+ if (code == SET || code == CLOBBER)
+ {
+ rtx dest = XEXP (elt, 0);
+ while (GET_CODE (dest) == SUBREG
+ || GET_CODE (dest) == STRICT_LOW_PART
+ || GET_CODE (dest) == SIGN_EXTRACT
+ || GET_CODE (dest) == ZERO_EXTRACT)
+ dest = XEXP (dest, 0);
+
+ if (GET_CODE (dest) == REG)
+ reg_last_set[REGNO (dest)] = insn;
+ else if (GET_CODE (dest) == MEM)
+ mem_last_set = INSN_CUID (insn);
+ }
+ }
+ }
+ else if (GET_CODE (PATTERN (insn)) == SET
+ || GET_CODE (PATTERN (insn)) == CLOBBER)
+ {
+ register rtx dest = XEXP (PATTERN (insn), 0);
+
+ while (GET_CODE (dest) == SUBREG
+ || GET_CODE (dest) == STRICT_LOW_PART
+ || GET_CODE (dest) == SIGN_EXTRACT
+ || GET_CODE (dest) == ZERO_EXTRACT)
+ dest = XEXP (dest, 0);
+
+ if (GET_CODE (dest) == REG)
+ reg_last_set[REGNO (dest)] = insn;
+ else if (GET_CODE (dest) == MEM)
+ mem_last_set = INSN_CUID (insn);
+ }
+}
+
+/* Return nonzero if expression X refers to a REG or to memory
+ that is set in an instruction more recent than FROM_CUID. */
+
+static int
+use_crosses_set_p (x, from_cuid)
+ register rtx x;
+ int from_cuid;
+{
+ register char *fmt;
+ register int i;
+ register enum rtx_code code = GET_CODE (x);
+
+ if (code == REG)
+ {
+ register int regno = REGNO (x);
+#ifdef PUSH_ROUNDING
+ /* Don't allow uses of the stack pointer to be moved,
+ because we don't know whether the move crosses a push insn. */
+ if (regno == STACK_POINTER_REGNUM)
+ return 1;
+#endif
+ return (reg_last_set[regno]
+ && INSN_CUID (reg_last_set[regno]) > from_cuid);
+ }
+
+ if (code == MEM && mem_last_set > from_cuid)
+ return 1;
+
+ fmt = GET_RTX_FORMAT (code);
+
+ for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+ {
+ if (fmt[i] == 'E')
+ {
+ register int j;
+ for (j = XVECLEN (x, i) - 1; j >= 0; j--)
+ if (use_crosses_set_p (XVECEXP (x, i, j), from_cuid))
+ return 1;
+ }
+ else if (fmt[i] == 'e'
+ && use_crosses_set_p (XEXP (x, i), from_cuid))
+ return 1;
+ }
+ return 0;
+}
+\f
+/* Return nonzero if reg REGNO is marked as dying in INSN. */
+
+int
+regno_dead_p (regno, insn)
+ int regno;
+ rtx insn;
+{
+ register rtx link;
+
+ for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
+ if ((REG_NOTE_KIND (link) == REG_DEAD
+ || REG_NOTE_KIND (link) == REG_INC)
+ && REGNO (XEXP (link, 0)) == regno)
+ return 1;
+
+ return 0;
+}
+
+/* Return nonzero if J is the first insn following I,
+ not counting labels, line numbers, etc.
+ We assume that J follows I. */
+
+static int
+adjacent_insns_p (i, j)
+ rtx i, j;
+{
+ register rtx insn;
+ for (insn = NEXT_INSN (i); insn != j; insn = NEXT_INSN (insn))
+ if (GET_CODE (insn) == INSN
+ || GET_CODE (insn) == CALL_INSN
+ || GET_CODE (insn) == JUMP_INSN)
+ return 0;
+ return 1;
+}
+
+/* Check that X is an insn-body for an `asm' with operands
+ and that the operands mentioned in it are legitimate. */
+
+static int
+check_asm_operands (x)
+ rtx x;
+{
+ int noperands = asm_noperands (x);
+ rtx *operands;
+ int i;
+
+ if (noperands < 0)
+ return 0;
+ if (noperands == 0)
+ return 1;
+
+ operands = (rtx *) alloca (noperands * sizeof (rtx));
+ decode_asm_operands (x, operands, 0, 0, 0);
+
+ for (i = 0; i < noperands; i++)
+ if (!general_operand (operands[i], VOIDmode))
+ return 0;
+
+ return 1;
+}
+\f
+/* Concatenate the list of logical links of OINSN
+ into INSN's list of logical links.
+ Modifies OINSN destructively.
+
+ If ALL_LINKS is nonzero, move all the links that OINSN has.
+ Otherwise, move only those that point to insns that set regs
+ that die in the insn OINSN.
+ Other links are clobbered so that they are no longer effective. */
+
+static void
+add_links (insn, oinsn, all_links)
+ rtx insn, oinsn;
+ int all_links;
+{
+ register rtx links = LOG_LINKS (oinsn);
+ if (! all_links)
+ {
+ rtx tail;
+ for (tail = links; tail; tail = XEXP (tail, 1))
+ {
+ rtx target = XEXP (tail, 0);
+ if (GET_CODE (target) != INSN
+ || GET_CODE (PATTERN (target)) != SET
+ || GET_CODE (SET_DEST (PATTERN (target))) != REG
+ || ! dead_or_set_p (oinsn, SET_DEST (PATTERN (target))))
+ /* OINSN is going to become a NOTE
+ so a link pointing there will have no effect. */
+ XEXP (tail, 0) = oinsn;
+ }
+ }
+ if (LOG_LINKS (insn) == 0)
+ LOG_LINKS (insn) = links;
+ else
+ {
+ register rtx next, prev = LOG_LINKS (insn);
+ while (next = XEXP (prev, 1))
+ prev = next;
+ XEXP (prev, 1) = links;
+ }
+}
+
+/* Delete any LOG_LINKS of INSN which point at OINSN. */
+
+static void
+remove_links (insn, oinsn)
+ rtx insn, oinsn;
+{
+ register rtx next = LOG_LINKS (insn), prev = 0;
+ while (next)
+ {
+ if (XEXP (next, 0) == oinsn)
+ {
+ if (prev)
+ XEXP (prev, 1) = XEXP (next, 1);
+ else
+ LOG_LINKS (insn) = XEXP (next, 1);
+ }
+ else
+ prev = next;
+ next = XEXP (next, 1);
+ }
+}
+
+/* Concatenate the any elements of the list of reg-notes INCS
+ which are of type REG_INC
+ into INSN's list of reg-notes. */
+
+static void
+add_incs (insn, incs)
+ rtx insn, incs;
+{
+ register rtx tail;
+
+ for (tail = incs; tail; tail = XEXP (tail, 1))
+ if (REG_NOTE_KIND (tail) == REG_INC)
+ REG_NOTES (insn)
+ = gen_rtx (EXPR_LIST, REG_INC, XEXP (tail, 0), REG_NOTES (insn));
+}
+\f
+/* Remove register number REGNO from the dead registers list of INSN. */
+
+void
+remove_death (regno, insn)
+ int regno;
+ rtx insn;
+{
+ register rtx link, next;
+ while ((link = REG_NOTES (insn))
+ && REG_NOTE_KIND (link) == REG_DEAD
+ && REGNO (XEXP (link, 0)) == regno)
+ REG_NOTES (insn) = XEXP (link, 1);
+
+ if (link)
+ while (next = XEXP (link, 1))
+ {
+ if (REG_NOTE_KIND (next) == REG_DEAD
+ && REGNO (XEXP (next, 0)) == regno)
+ XEXP (link, 1) = XEXP (next, 1);
+ else
+ link = next;
+ }
+}
+
+/* For each register (hardware or pseudo) used within expression X,
+ if its death is in an instruction with cuid
+ between FROM_CUID (inclusive) and TO_INSN (exclusive),
+ mark it as dead in TO_INSN instead.
+
+ This is done when X is being merged by combination into TO_INSN. */
+
+static void
+move_deaths (x, from_cuid, to_insn)
+ rtx x;
+ int from_cuid;
+ rtx to_insn;
+{
+ register char *fmt;
+ register int len, i;
+ register enum rtx_code code = GET_CODE (x);
+
+ if (code == REG)
+ {
+ register rtx where_dead = reg_last_death[REGNO (x)];
+
+ if (where_dead && INSN_CUID (where_dead) >= from_cuid
+ && INSN_CUID (where_dead) < INSN_CUID (to_insn))
+ {
+ remove_death (REGNO (x), reg_last_death[REGNO (x)]);
+ if (! dead_or_set_p (to_insn, x))
+ REG_NOTES (to_insn)
+ = gen_rtx (EXPR_LIST, REG_DEAD, x, REG_NOTES (to_insn));
+ }
+ return;
+ }
+
+ len = GET_RTX_LENGTH (code);
+ fmt = GET_RTX_FORMAT (code);
+
+ for (i = 0; i < len; i++)
+ {
+ if (fmt[i] == 'E')
+ {
+ register int j;
+ for (j = XVECLEN (x, i) - 1; j >= 0; j--)
+ move_deaths (XVECEXP (x, i, j), from_cuid, to_insn);
+ }
+ else if (fmt[i] == 'e')
+ move_deaths (XEXP (x, i), from_cuid, to_insn);
+ }
+}
+\f
+/* Like move_deaths, but deaths are moving both forward
+ (from FROM_CUID to TO_INSN), and backwards
+ (from FROM_INSN to TO_INSN). This is what happens
+ when an insn is removed after applying the distributive law. */
+
+static void
+move_deaths_2 (x, from_cuid, from_insn, to_insn)
+ rtx x;
+ int from_cuid;
+ rtx from_insn, to_insn;
+{
+ register char *fmt;
+ register int len, i;
+ register enum rtx_code code = GET_CODE (x);
+
+ if (code == REG)
+ {
+ register rtx where_dead = reg_last_death[REGNO (x)];
+
+ if (where_dead && INSN_CUID (where_dead) >= from_cuid
+ && INSN_CUID (where_dead) < INSN_CUID (to_insn))
+ {
+ remove_death (REGNO (x), reg_last_death[REGNO (x)]);
+ if (! dead_or_set_p (to_insn, x))
+ REG_NOTES (to_insn)
+ = gen_rtx (EXPR_LIST, REG_DEAD, x, REG_NOTES (to_insn));
+ }
+ /* Can't use where_dead for from_insn because it has
+ not been computed yet. */
+ else if (dead_or_set_p (from_insn, x))
+ {
+ remove_death (REGNO (x), from_insn);
+ if (! dead_or_set_p (to_insn, x))
+ REG_NOTES (to_insn)
+ = gen_rtx (EXPR_LIST, REG_DEAD, x, REG_NOTES (to_insn));
+ }
+ return;
+ }
+
+ len = GET_RTX_LENGTH (code);
+ fmt = GET_RTX_FORMAT (code);
+
+ for (i = 0; i < len; i++)
+ {
+ if (fmt[i] == 'E')
+ {
+ register int j;
+ for (j = XVECLEN (x, i) - 1; j >= 0; j--)
+ move_deaths_2 (XVECEXP (x, i, j), from_cuid, from_insn, to_insn);
+ }
+ else if (fmt[i] == 'e')
+ move_deaths_2 (XEXP (x, i), from_cuid, from_insn, to_insn);
+ }
+}
+\f
+/* The distrib combiner rewrites groups of insns so that optimizations
+ can be more easily recognized. The front-end does not know how to
+ group certain kinds of operations for efficient execution, and the
+ resulting code can be quite poor. For example, on a machine without
+ bitfield instructions, bitfield references look like
+
+ (and (lshiftrt ... n) m)
+
+ When combining two bitfield operations, such as with ||, this can
+ yield code like
+
+ (set z
+ (or (and (lshiftrt x n) 1)
+ (and (lshiftrt y n) 1)))
+
+ which can be more efficiently executed as
+
+ (set z
+ (lshiftrt (and (or x y)
+ (1 << m)) n))
+
+ From there, the combiner attempts to rewrite the insns,
+ keeping flow information accurate for later passes,
+ and reducing the total number of insns executed.
+
+ This function returns the point at which we should try
+ looking for more simplifications. This will be before
+ INSN if the call succeeds. We do not need to fear
+ infinite loops, since this function is guaranteed to
+ eliminate at least one (non-note) instruction if it returns
+ successfully. */
+
+static rtx
+try_distrib (insn, xprev1, xprev2)
+ rtx insn, xprev1, xprev2;
+{
+ rtx pat = PATTERN (insn);
+ rtx prev1, prev2, pat1, pat2, src1, src2;
+ rtx to_prev, to_insn;
+ enum rtx_code code;
+ int insn_code_number, prev_code_number, regno;
+ rtx new_insn_pat, new_prev_pat;
+
+ distrib_attempts++;
+
+ /* ??? Need to implement a test that PREV2 and PREV1
+ are completely independent. Right now their
+ recognition ability is sufficiently limited that
+ it should not be necessary, but better safe than sorry. */
+
+ /* Let PREV1 be the later of the two insns, and PREV2 the earlier. */
+ if (INSN_CUID (xprev1) > INSN_CUID (xprev2))
+ {
+ prev1 = xprev1;
+ prev2 = xprev2;
+ }
+ else
+ {
+ prev1 = xprev2;
+ prev2 = xprev1;
+ }
+
+ pat1 = PATTERN (prev1);
+ pat2 = PATTERN (prev2);
+
+ /* First, see if INSN, PREV1, and PREV2 have patterns we can expect
+ to simplify. */
+
+ if (GET_CODE (pat) != SET
+ || GET_CODE (pat1) != SET
+ || GET_CODE (pat2) != SET)
+ return 0;
+
+ code = GET_CODE (SET_SRC (pat));
+ src1 = SET_SRC (pat1);
+ src2 = SET_SRC (pat2);
+
+ if (GET_CODE (SET_DEST (pat1)) != REG
+ || GET_CODE (SET_DEST (pat2)) != REG)
+ return 0;
+
+ switch (code)
+ {
+ default:
+ return 0;
+
+ case IOR:
+ case AND:
+ case XOR:
+ case PLUS:
+ ;
+ }
+
+ /* Insns PREV1 and PREV2 must provide the two operands of the arithmetic
+ that is done in INSN. */
+ if (! ((XEXP (SET_SRC (pat), 0) == SET_DEST (pat1)
+ && XEXP (SET_SRC (pat), 1) == SET_DEST (pat2))
+ ||
+ (XEXP (SET_SRC (pat), 0) == SET_DEST (pat2)
+ && XEXP (SET_SRC (pat), 1) == SET_DEST (pat1))))
+ return 0;
+
+ /* They must not be used in any other way in INSN.
+ In particular, they must not be used in a result memory address. */
+ if (reg_mentioned_p (SET_DEST (pat1), SET_DEST (pat))
+ || reg_mentioned_p (SET_DEST (pat2), SET_DEST (pat)))
+ return 0;
+
+ /* Give up if the two operands' modes don't match. */
+ if (GET_MODE (src1) != GET_MODE (src2))
+ return 0;
+
+ /* PREV1 and PREV2 must compute the same operation.
+ Actually, there are other cases that could be handled,
+ but are not implemented. For example:
+
+ (set (reg:SI 94)
+ (and:SI (reg:SI 73)
+ (const_int 223)))
+
+ (set (reg:SI 95)
+ (zero_extend:SI (subreg:QI (reg:SI 91) 0)))
+
+ (set (reg:SI 96)
+ (ior:SI (reg:SI 94)
+ (reg:SI 95)))
+
+ In this case, we know that because (reg:SI 94) has
+ been anded with 223, there is no need to zero_extend
+ (reg:SI 91), and we could eliminate (reg:SI 95). */
+
+ if (GET_CODE (src1) != GET_CODE (src2))
+ return 0;
+
+ /* The SETs in PREV1 and PREV2 do not need to be kept around. */
+
+ undobuf.num_undo = 0;
+ undobuf.storage = 0;
+
+ /* Substitute in the latest insn for the regs set by the earlier ones. */
+ subst_insn = insn;
+ n_occurrences = 0; /* `subst' counts here */
+
+ switch (GET_CODE (src1))
+ {
+ /* case XOR: Does not distribute through anything! */
+ case LSHIFTRT:
+ case ASHIFTRT:
+ /* Right-shift can't distribute through addition
+ since the round-off would happen differently. */
+ case AND:
+ case IOR:
+ /* Boolean ops don't distribute through addition. */
+ if (code == PLUS)
+ return 0;
+ goto do_distrib;
+
+ case LSHIFT:
+ case ASHIFT:
+ /* Left shifts are multiplication; they distribute through
+ addition. Also, since they work bitwise, they
+ distribute through boolean operations. */
+#ifdef NEGATIVE_SHIFT_COUNTS
+ /* Negative count is really a right-shift. */
+ if (NEGATIVE_SHIFT_COUNTS
+ && code == PLUS
+ && !(GET_CODE (XEXP (src1, 1))
+ == CONST_INT && INTVAL (XEXP (src1, 1)) >= 0))
+ return 0;
+#endif
+ goto do_distrib;
+
+ case MULT:
+ /* Multiplication distributes through addition only. */
+ if (code != PLUS)
+ return 0;
+
+ do_distrib:
+ if (GET_CODE (XEXP (src1, 1)) != CONST_INT
+ || GET_CODE (XEXP (src2, 1)) != CONST_INT
+ || INTVAL (XEXP (src1, 1)) != INTVAL (XEXP (src2, 1)))
+ return 0;
+
+ /* Give up if we would move a use of a reg across an alteration.
+ Note this is unnecessarily conservative, since a problem really
+ happens only if this reg is set *between* PREV2 and PREV1
+ But this test is easier. */
+ if (use_crosses_set_p (XEXP (src2, 0), INSN_CUID (prev2)))
+ return 0;
+
+ /* Try changing (+ (* x c) (* y c)) to (* (+ x y) c). */
+ to_prev = gen_rtx (code, GET_MODE (src1),
+ XEXP (src1, 0), XEXP (src2, 0));
+ to_insn = gen_rtx (GET_CODE (src1), GET_MODE (src1), SET_DEST (pat1), XEXP (src1, 1));
+ break;
+
+ case ZERO_EXTEND:
+ case SIGN_EXTEND:
+ /* Extension can't distribute through addition;
+ the carries could be changed. */
+ if (code == PLUS)
+ return 0;
+ {
+ rtx inner1 = XEXP (src1, 0), inner2 = XEXP (src2, 0);
+ int subreg_needed = 0;
+
+ /* Try changing (& (extend x) (extend y)) to (extend (& x y)). */
+ /* But keep extend insns together with their subregs. */
+ if (GET_CODE (inner1) == SUBREG)
+ {
+ if (SUBREG_WORD (inner1) != 0)
+ return 0;
+ else
+ {
+ subreg_needed = 1;
+ inner1 = SUBREG_REG (inner1);
+ }
+ }
+
+ if (GET_CODE (inner2) == SUBREG)
+ {
+ if (SUBREG_WORD (inner2) != 0)
+ return 0;
+ else
+ {
+ subreg_needed = 1;
+ inner2 = SUBREG_REG (inner2);
+ }
+ }
+
+ /* Give up if we would move a use of a reg across an alteration.
+ Note this is unnecessarily conservative, since a problem really
+ happens only if this reg is set *between* PREV2 and PREV1
+ But this test is easier. */
+ if (use_crosses_set_p (inner2, INSN_CUID (prev2)))
+ return 0;
+
+ to_prev = gen_rtx (code, GET_MODE (src1), inner1, inner2);
+ to_insn = gen_rtx (GET_CODE (src1), GET_MODE (src1),
+ subreg_needed
+ ? gen_rtx (SUBREG, GET_MODE (XEXP (src1, 0)),
+ SET_DEST (pat1), 0)
+ : SET_DEST (pat1));
+ }
+ break;
+
+ default:
+ return 0;
+ }
+
+ /* Are the results of this "substitution" a valid instruction? */
+
+ new_insn_pat = subst (PATTERN (insn), SET_SRC (PATTERN (insn)), to_insn);
+ distrib_merges_1++;
+
+ insn_code_number = recog (new_insn_pat, insn);
+ if (insn_code_number < 0)
+ {
+ undo_all ();
+ return 0;
+ }
+
+ subst_insn = prev1;
+ new_prev_pat = subst (pat1, src1, to_prev);
+ distrib_merges_2++;
+
+ prev_code_number = recog (new_prev_pat, prev1);
+ if (prev_code_number < 0)
+ {
+ undo_all ();
+ return 0;
+ }
+
+ /* Everything worked; install the new patterns. */
+ INSN_CODE (insn) = insn_code_number;
+ PATTERN (insn) = new_insn_pat;
+
+ INSN_CODE (prev1) = prev_code_number;
+ PATTERN (prev1) = new_prev_pat;
+
+ /* Need to change LOG_LINKS around...PREV1 now gets
+ whatever flowed into PREV2. PREV2 is going to
+ become a NOTE, so we clear out its LOG_LINKS. */
+ remove_links (insn, prev2);
+ add_links (prev1, prev2, adjacent_insns_p (prev2, prev1));
+
+ /* Registers which died in PREV2 now die in PREV1.
+ Also, registers born in PREV2 dying in INSN now die in PREV1. */
+ move_deaths_2 (src2, INSN_CUID (prev2), insn, prev1);
+
+ regno = REGNO (SET_DEST (pat2));
+
+ reg_n_sets[regno]--;
+ if (reg_n_sets[regno] == 0
+ && ! (basic_block_live_at_start[0][regno / HOST_BITS_PER_INT]
+ & (1 << (regno % HOST_BITS_PER_INT))))
+ reg_n_refs[regno] = 0;
+ remove_death (regno, insn);
+
+ PUT_CODE (prev2, NOTE);
+ NOTE_LINE_NUMBER (prev2) = NOTE_INSN_DELETED;
+ NOTE_SOURCE_FILE (prev2) = 0;
+
+ distrib_successes++;
+ return prev1;
+}
+\f
+void
+dump_combine_stats (file)
+ FILE *file;
+{
+ fprintf
+ (file,
+ ";; Combiner statistics: %d attempts, %d substitutions (%d requiring new space),\n;; %d successes.\n\n",
+ combine_attempts, combine_merges, combine_extras, combine_successes);
+ fprintf
+ (file,
+ ";; Distributer statistics: %d attempts, %d:%d substitutions,\n;; %d successes.\n\n",
+ distrib_attempts, distrib_merges_1,
+ distrib_merges_2, distrib_successes);
+}
+
+void
+dump_combine_total_stats (file)
+ FILE *file;
+{
+ fprintf
+ (file,
+ "\n;; Combiner totals: %d attempts, %d substitutions (%d requiring new space),\n;; %d successes.\n",
+ total_attempts, total_merges, total_extras, total_successes);
+ fprintf
+ (file,
+ "\n;; Distributer totals: %d attempts, %d:%d substitutions,\n;; %d successes.\n",
+ total_distrib_attempts, total_distrib_merges_1,
+ total_distrib_merges_2, total_distrib_successes);
+}
projects / unix-history / commitdiff