/* Analyze RTL for C-Compiler
- Copyright (C) 1987, 88, 92-97, 1998 Free Software Foundation, Inc.
+ Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
+ 1999, 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
-This file is part of GNU CC.
+This file is part of GCC.
-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 2, or (at your option)
-any later version.
+GCC 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 2, 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.
+GCC 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, 59 Temple Place - Suite 330,
-Boston, MA 02111-1307, USA. */
+along with GCC; see the file COPYING. If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA. */
#include "config.h"
#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "toplev.h"
#include "rtl.h"
-
-static int rtx_addr_can_trap_p PROTO((rtx));
-static void reg_set_p_1 PROTO((rtx, rtx));
-static void reg_set_last_1 PROTO((rtx, rtx));
-
+#include "hard-reg-set.h"
+#include "insn-config.h"
+#include "recog.h"
+#include "target.h"
+#include "output.h"
+#include "tm_p.h"
+#include "flags.h"
+#include "basic-block.h"
+#include "real.h"
+#include "regs.h"
+#include "function.h"
/* Forward declarations */
-static int jmp_uses_reg_or_mem PROTO((rtx));
+static int global_reg_mentioned_p_1 (rtx *, void *);
+static void set_of_1 (rtx, rtx, void *);
+static void insn_dependent_p_1 (rtx, rtx, void *);
+static int rtx_referenced_p_1 (rtx *, void *);
+static int computed_jump_p_1 (rtx);
+static void parms_set (rtx, rtx, void *);
+static bool hoist_test_store (rtx, rtx, regset);
+static void hoist_update_store (rtx, rtx *, rtx, rtx);
+
+static unsigned HOST_WIDE_INT cached_nonzero_bits (rtx, enum machine_mode,
+ rtx, enum machine_mode,
+ unsigned HOST_WIDE_INT);
+static unsigned HOST_WIDE_INT nonzero_bits1 (rtx, enum machine_mode, rtx,
+ enum machine_mode,
+ unsigned HOST_WIDE_INT);
+static unsigned int cached_num_sign_bit_copies (rtx, enum machine_mode, rtx,
+ enum machine_mode,
+ unsigned int);
+static unsigned int num_sign_bit_copies1 (rtx, enum machine_mode, rtx,
+ enum machine_mode, unsigned int);
/* Bit flags that specify the machine subtype we are compiling for.
Bits are tested using macros TARGET_... defined in the tm.h file
(within one function) and so is anything marked `unchanging'. */
int
-rtx_unstable_p (x)
- rtx x;
+rtx_unstable_p (rtx x)
{
- register RTX_CODE code = GET_CODE (x);
- register int i;
- register char *fmt;
+ RTX_CODE code = GET_CODE (x);
+ int i;
+ const char *fmt;
- if (code == MEM)
- return ! RTX_UNCHANGING_P (x);
+ switch (code)
+ {
+ case MEM:
+ return !MEM_READONLY_P (x) || rtx_unstable_p (XEXP (x, 0));
- if (code == QUEUED)
- return 1;
+ case CONST:
+ case CONST_INT:
+ case CONST_DOUBLE:
+ case CONST_VECTOR:
+ case SYMBOL_REF:
+ case LABEL_REF:
+ return 0;
- if (code == CONST || code == CONST_INT)
- return 0;
+ case REG:
+ /* As in rtx_varies_p, we have to use the actual rtx, not reg number. */
+ if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
+ /* The arg pointer varies if it is not a fixed register. */
+ || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM]))
+ return 0;
+#ifndef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
+ /* ??? When call-clobbered, the value is stable modulo the restore
+ that must happen after a call. This currently screws up local-alloc
+ into believing that the restore is not needed. */
+ if (x == pic_offset_table_rtx)
+ return 0;
+#endif
+ return 1;
+
+ case ASM_OPERANDS:
+ if (MEM_VOLATILE_P (x))
+ return 1;
+
+ /* Fall through. */
- if (code == REG)
- return ! (REGNO (x) == FRAME_POINTER_REGNUM
- || REGNO (x) == HARD_FRAME_POINTER_REGNUM
- || REGNO (x) == ARG_POINTER_REGNUM
- || RTX_UNCHANGING_P (x));
+ default:
+ break;
+ }
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
if (fmt[i] == 'e')
- if (rtx_unstable_p (XEXP (x, i)))
- return 1;
+ {
+ if (rtx_unstable_p (XEXP (x, i)))
+ return 1;
+ }
+ else if (fmt[i] == 'E')
+ {
+ int j;
+ for (j = 0; j < XVECLEN (x, i); j++)
+ if (rtx_unstable_p (XVECEXP (x, i, j)))
+ return 1;
+ }
+
return 0;
}
/* Return 1 if X has a value that can vary even between two
executions of the program. 0 means X can be compared reliably
against certain constants or near-constants.
+ FOR_ALIAS is nonzero if we are called from alias analysis; if it is
+ zero, we are slightly more conservative.
The frame pointer and the arg pointer are considered constant. */
int
-rtx_varies_p (x)
- rtx x;
+rtx_varies_p (rtx x, int for_alias)
{
- register RTX_CODE code = GET_CODE (x);
- register int i;
- register char *fmt;
+ RTX_CODE code;
+ int i;
+ const char *fmt;
+
+ if (!x)
+ return 0;
+ code = GET_CODE (x);
switch (code)
{
case MEM:
- case QUEUED:
- return 1;
+ return !MEM_READONLY_P (x) || rtx_varies_p (XEXP (x, 0), for_alias);
case CONST:
case CONST_INT:
case CONST_DOUBLE:
+ case CONST_VECTOR:
case SYMBOL_REF:
case LABEL_REF:
return 0;
and arg pointers and not just the register number in case we have
eliminated the frame and/or arg pointer and are using it
for pseudos. */
- return ! (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
- || x == arg_pointer_rtx || x == pic_offset_table_rtx);
+ if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
+ /* The arg pointer varies if it is not a fixed register. */
+ || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM]))
+ return 0;
+ if (x == pic_offset_table_rtx
+#ifdef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
+ /* ??? When call-clobbered, the value is stable modulo the restore
+ that must happen after a call. This currently screws up
+ local-alloc into believing that the restore is not needed, so we
+ must return 0 only if we are called from alias analysis. */
+ && for_alias
+#endif
+ )
+ return 0;
+ return 1;
case LO_SUM:
/* The operand 0 of a LO_SUM is considered constant
- (in fact is it related specifically to operand 1). */
- return rtx_varies_p (XEXP (x, 1));
-
+ (in fact it is related specifically to operand 1)
+ during alias analysis. */
+ return (! for_alias && rtx_varies_p (XEXP (x, 0), for_alias))
+ || rtx_varies_p (XEXP (x, 1), for_alias);
+
+ case ASM_OPERANDS:
+ if (MEM_VOLATILE_P (x))
+ return 1;
+
+ /* Fall through. */
+
default:
break;
}
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
if (fmt[i] == 'e')
- if (rtx_varies_p (XEXP (x, i)))
- return 1;
+ {
+ if (rtx_varies_p (XEXP (x, i), for_alias))
+ return 1;
+ }
+ else if (fmt[i] == 'E')
+ {
+ int j;
+ for (j = 0; j < XVECLEN (x, i); j++)
+ if (rtx_varies_p (XVECEXP (x, i, j), for_alias))
+ return 1;
+ }
+
return 0;
}
/* Return 0 if the use of X as an address in a MEM can cause a trap. */
-static int
-rtx_addr_can_trap_p (x)
- register rtx x;
+int
+rtx_addr_can_trap_p (rtx x)
{
- register enum rtx_code code = GET_CODE (x);
+ enum rtx_code code = GET_CODE (x);
switch (code)
{
case SYMBOL_REF:
+ return SYMBOL_REF_WEAK (x);
+
case LABEL_REF:
- /* SYMBOL_REF is problematic due to the possible presence of
- a #pragma weak, but to say that loads from symbols can trap is
- *very* costly. It's not at all clear what's best here. For
- now, we ignore the impact of #pragma weak. */
return 0;
case REG:
/* As in rtx_varies_p, we have to use the actual rtx, not reg number. */
- return ! (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
- || x == stack_pointer_rtx || x == arg_pointer_rtx);
+ if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
+ || x == stack_pointer_rtx
+ /* The arg pointer varies if it is not a fixed register. */
+ || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM]))
+ return 0;
+ /* All of the virtual frame registers are stack references. */
+ if (REGNO (x) >= FIRST_VIRTUAL_REGISTER
+ && REGNO (x) <= LAST_VIRTUAL_REGISTER)
+ return 0;
+ return 1;
case CONST:
return rtx_addr_can_trap_p (XEXP (x, 0));
case PLUS:
/* An address is assumed not to trap if it is an address that can't
- trap plus a constant integer. */
- return (rtx_addr_can_trap_p (XEXP (x, 0))
- || GET_CODE (XEXP (x, 1)) != CONST_INT);
+ trap plus a constant integer or it is the pic register plus a
+ constant. */
+ return ! ((! rtx_addr_can_trap_p (XEXP (x, 0))
+ && GET_CODE (XEXP (x, 1)) == CONST_INT)
+ || (XEXP (x, 0) == pic_offset_table_rtx
+ && CONSTANT_P (XEXP (x, 1))));
case LO_SUM:
+ case PRE_MODIFY:
return rtx_addr_can_trap_p (XEXP (x, 1));
-
+
+ case PRE_DEC:
+ case PRE_INC:
+ case POST_DEC:
+ case POST_INC:
+ case POST_MODIFY:
+ return rtx_addr_can_trap_p (XEXP (x, 0));
+
default:
break;
}
return 1;
}
-/* Return 1 if X refers to a memory location whose address
+/* Return true if X is an address that is known to not be zero. */
+
+bool
+nonzero_address_p (rtx x)
+{
+ enum rtx_code code = GET_CODE (x);
+
+ switch (code)
+ {
+ case SYMBOL_REF:
+ return !SYMBOL_REF_WEAK (x);
+
+ case LABEL_REF:
+ return true;
+
+ case REG:
+ /* As in rtx_varies_p, we have to use the actual rtx, not reg number. */
+ if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
+ || x == stack_pointer_rtx
+ || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM]))
+ return true;
+ /* All of the virtual frame registers are stack references. */
+ if (REGNO (x) >= FIRST_VIRTUAL_REGISTER
+ && REGNO (x) <= LAST_VIRTUAL_REGISTER)
+ return true;
+ return false;
+
+ case CONST:
+ return nonzero_address_p (XEXP (x, 0));
+
+ case PLUS:
+ if (GET_CODE (XEXP (x, 1)) == CONST_INT)
+ {
+ /* Pointers aren't allowed to wrap. If we've got a register
+ that is known to be a pointer, and a positive offset, then
+ the composite can't be zero. */
+ if (INTVAL (XEXP (x, 1)) > 0
+ && REG_P (XEXP (x, 0))
+ && REG_POINTER (XEXP (x, 0)))
+ return true;
+
+ return nonzero_address_p (XEXP (x, 0));
+ }
+ /* Handle PIC references. */
+ else if (XEXP (x, 0) == pic_offset_table_rtx
+ && CONSTANT_P (XEXP (x, 1)))
+ return true;
+ return false;
+
+ case PRE_MODIFY:
+ /* Similar to the above; allow positive offsets. Further, since
+ auto-inc is only allowed in memories, the register must be a
+ pointer. */
+ if (GET_CODE (XEXP (x, 1)) == CONST_INT
+ && INTVAL (XEXP (x, 1)) > 0)
+ return true;
+ return nonzero_address_p (XEXP (x, 0));
+
+ case PRE_INC:
+ /* Similarly. Further, the offset is always positive. */
+ return true;
+
+ case PRE_DEC:
+ case POST_DEC:
+ case POST_INC:
+ case POST_MODIFY:
+ return nonzero_address_p (XEXP (x, 0));
+
+ case LO_SUM:
+ return nonzero_address_p (XEXP (x, 1));
+
+ default:
+ break;
+ }
+
+ /* If it isn't one of the case above, might be zero. */
+ return false;
+}
+
+/* Return 1 if X refers to a memory location whose address
cannot be compared reliably with constant addresses,
- or if X refers to a BLKmode memory object. */
+ or if X refers to a BLKmode memory object.
+ FOR_ALIAS is nonzero if we are called from alias analysis; if it is
+ zero, we are slightly more conservative. */
int
-rtx_addr_varies_p (x)
- rtx x;
+rtx_addr_varies_p (rtx x, int for_alias)
{
- register enum rtx_code code;
- register int i;
- register char *fmt;
+ enum rtx_code code;
+ int i;
+ const char *fmt;
if (x == 0)
return 0;
code = GET_CODE (x);
if (code == MEM)
- return GET_MODE (x) == BLKmode || rtx_varies_p (XEXP (x, 0));
+ return GET_MODE (x) == BLKmode || rtx_varies_p (XEXP (x, 0), for_alias);
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
if (fmt[i] == 'e')
{
- if (rtx_addr_varies_p (XEXP (x, i)))
+ if (rtx_addr_varies_p (XEXP (x, i), for_alias))
return 1;
}
else if (fmt[i] == 'E')
{
int j;
for (j = 0; j < XVECLEN (x, i); j++)
- if (rtx_addr_varies_p (XVECEXP (x, i, j)))
+ if (rtx_addr_varies_p (XVECEXP (x, i, j), for_alias))
return 1;
}
return 0;
/* Return the value of the integer term in X, if one is apparent;
otherwise return 0.
Only obvious integer terms are detected.
- This is used in cse.c with the `related_value' field.*/
+ This is used in cse.c with the `related_value' field. */
HOST_WIDE_INT
-get_integer_term (x)
- rtx x;
+get_integer_term (rtx x)
{
if (GET_CODE (x) == CONST)
x = XEXP (x, 0);
Only obvious integer terms are detected. */
rtx
-get_related_value (x)
- rtx x;
+get_related_value (rtx x)
{
if (GET_CODE (x) != CONST)
return 0;
return 0;
}
\f
-/* Nonzero if register REG appears somewhere within IN.
- Also works if REG is not a register; in this case it checks
- for a subexpression of IN that is Lisp "equal" to REG. */
+/* Given a tablejump insn INSN, return the RTL expression for the offset
+ into the jump table. If the offset cannot be determined, then return
+ NULL_RTX.
-int
-reg_mentioned_p (reg, in)
- register rtx reg, in;
+ If EARLIEST is nonzero, it is a pointer to a place where the earliest
+ insn used in locating the offset was found. */
+
+rtx
+get_jump_table_offset (rtx insn, rtx *earliest)
{
- register char *fmt;
- register int i;
- register enum rtx_code code;
+ rtx label = NULL;
+ rtx table = NULL;
+ rtx set;
+ rtx old_insn;
+ rtx x;
+ rtx old_x;
+ rtx y;
+ rtx old_y;
+ int i;
- if (in == 0)
- return 0;
+ if (!tablejump_p (insn, &label, &table) || !(set = single_set (insn)))
+ return NULL_RTX;
- if (reg == in)
- return 1;
+ x = SET_SRC (set);
- if (GET_CODE (in) == LABEL_REF)
- return reg == XEXP (in, 0);
+ /* Some targets (eg, ARM) emit a tablejump that also
+ contains the out-of-range target. */
+ if (GET_CODE (x) == IF_THEN_ELSE
+ && GET_CODE (XEXP (x, 2)) == LABEL_REF)
+ x = XEXP (x, 1);
- code = GET_CODE (in);
+ /* Search backwards and locate the expression stored in X. */
+ for (old_x = NULL_RTX; REG_P (x) && x != old_x;
+ old_x = x, x = find_last_value (x, &insn, NULL_RTX, 0))
+ ;
- switch (code)
+ /* If X is an expression using a relative address then strip
+ off the addition / subtraction of PC, PIC_OFFSET_TABLE_REGNUM,
+ or the jump table label. */
+ if (GET_CODE (PATTERN (table)) == ADDR_DIFF_VEC
+ && (GET_CODE (x) == PLUS || GET_CODE (x) == MINUS))
{
- /* Compare registers by number. */
- case REG:
- return GET_CODE (reg) == REG && REGNO (in) == REGNO (reg);
+ for (i = 0; i < 2; i++)
+ {
+ old_insn = insn;
+ y = XEXP (x, i);
- /* These codes have no constituent expressions
- and are unique. */
- case SCRATCH:
- case CC0:
- case PC:
- return 0;
+ if (y == pc_rtx || y == pic_offset_table_rtx)
+ break;
- case CONST_INT:
- return GET_CODE (reg) == CONST_INT && INTVAL (in) == INTVAL (reg);
-
- case CONST_DOUBLE:
- /* These are kept unique for a given value. */
- return 0;
-
- default:
- break;
+ for (old_y = NULL_RTX; REG_P (y) && y != old_y;
+ old_y = y, y = find_last_value (y, &old_insn, NULL_RTX, 0))
+ ;
+
+ if ((GET_CODE (y) == LABEL_REF && XEXP (y, 0) == label))
+ break;
+ }
+
+ if (i >= 2)
+ return NULL_RTX;
+
+ x = XEXP (x, 1 - i);
+
+ for (old_x = NULL_RTX; REG_P (x) && x != old_x;
+ old_x = x, x = find_last_value (x, &insn, NULL_RTX, 0))
+ ;
}
- if (GET_CODE (reg) == code && rtx_equal_p (reg, in))
- return 1;
+ /* Strip off any sign or zero extension. */
+ if (GET_CODE (x) == SIGN_EXTEND || GET_CODE (x) == ZERO_EXTEND)
+ {
+ x = XEXP (x, 0);
- fmt = GET_RTX_FORMAT (code);
+ for (old_x = NULL_RTX; REG_P (x) && x != old_x;
+ old_x = x, x = find_last_value (x, &insn, NULL_RTX, 0))
+ ;
+ }
- for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+ /* If X isn't a MEM then this isn't a tablejump we understand. */
+ if (!MEM_P (x))
+ return NULL_RTX;
+
+ /* Strip off the MEM. */
+ x = XEXP (x, 0);
+
+ for (old_x = NULL_RTX; REG_P (x) && x != old_x;
+ old_x = x, x = find_last_value (x, &insn, NULL_RTX, 0))
+ ;
+
+ /* If X isn't a PLUS than this isn't a tablejump we understand. */
+ if (GET_CODE (x) != PLUS)
+ return NULL_RTX;
+
+ /* At this point we should have an expression representing the jump table
+ plus an offset. Examine each operand in order to determine which one
+ represents the jump table. Knowing that tells us that the other operand
+ must represent the offset. */
+ for (i = 0; i < 2; i++)
{
- if (fmt[i] == 'E')
- {
- register int j;
- for (j = XVECLEN (in, i) - 1; j >= 0; j--)
- if (reg_mentioned_p (reg, XVECEXP (in, i, j)))
- return 1;
- }
- else if (fmt[i] == 'e'
- && reg_mentioned_p (reg, XEXP (in, i)))
- return 1;
+ old_insn = insn;
+ y = XEXP (x, i);
+
+ for (old_y = NULL_RTX; REG_P (y) && y != old_y;
+ old_y = y, y = find_last_value (y, &old_insn, NULL_RTX, 0))
+ ;
+
+ if ((GET_CODE (y) == CONST || GET_CODE (y) == LABEL_REF)
+ && reg_mentioned_p (label, y))
+ break;
}
- return 0;
-}
-\f
-/* Return 1 if in between BEG and END, exclusive of BEG and END, there is
- no CODE_LABEL insn. */
-int
-no_labels_between_p (beg, end)
- rtx beg, end;
-{
- register rtx p;
- for (p = NEXT_INSN (beg); p != end; p = NEXT_INSN (p))
- if (GET_CODE (p) == CODE_LABEL)
- return 0;
- return 1;
-}
+ if (i >= 2)
+ return NULL_RTX;
-/* Nonzero if register REG is used in an insn between
- FROM_INSN and TO_INSN (exclusive of those two). */
+ x = XEXP (x, 1 - i);
-int
-reg_used_between_p (reg, from_insn, to_insn)
- rtx reg, from_insn, to_insn;
-{
- register rtx insn;
+ /* Strip off the addition / subtraction of PIC_OFFSET_TABLE_REGNUM. */
+ if (GET_CODE (x) == PLUS || GET_CODE (x) == MINUS)
+ for (i = 0; i < 2; i++)
+ if (XEXP (x, i) == pic_offset_table_rtx)
+ {
+ x = XEXP (x, 1 - i);
+ break;
+ }
- if (from_insn == to_insn)
- return 0;
+ if (earliest)
+ *earliest = insn;
- for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
- if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
- && (reg_overlap_mentioned_p (reg, PATTERN (insn))
- || (GET_CODE (insn) == CALL_INSN
- && (find_reg_fusage (insn, USE, reg)
- || find_reg_fusage (insn, CLOBBER, reg)))))
- return 1;
- return 0;
+ /* Return the RTL expression representing the offset. */
+ return x;
}
\f
-/* Nonzero if the old value of X, a register, is referenced in BODY. If X
- is entirely replaced by a new value and the only use is as a SET_DEST,
- we do not consider it a reference. */
+/* A subroutine of global_reg_mentioned_p, returns 1 if *LOC mentions
+ a global register. */
-int
-reg_referenced_p (x, body)
- rtx x;
- rtx body;
+static int
+global_reg_mentioned_p_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
{
- int i;
+ int regno;
+ rtx x = *loc;
- switch (GET_CODE (body))
+ if (! x)
+ return 0;
+
+ switch (GET_CODE (x))
{
- case SET:
- if (reg_overlap_mentioned_p (x, SET_SRC (body)))
- return 1;
+ case SUBREG:
+ if (REG_P (SUBREG_REG (x)))
+ {
+ if (REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER
+ && global_regs[subreg_regno (x)])
+ return 1;
+ return 0;
+ }
+ break;
- /* If the destination is anything other than CC0, PC, a REG or a SUBREG
- of a REG that occupies all of the REG, the insn references X if
- it is mentioned in the destination. */
- if (GET_CODE (SET_DEST (body)) != CC0
- && GET_CODE (SET_DEST (body)) != PC
- && GET_CODE (SET_DEST (body)) != REG
- && ! (GET_CODE (SET_DEST (body)) == SUBREG
- && GET_CODE (SUBREG_REG (SET_DEST (body))) == REG
- && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (SET_DEST (body))))
- + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD)
- == ((GET_MODE_SIZE (GET_MODE (SET_DEST (body)))
- + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD)))
- && reg_overlap_mentioned_p (x, SET_DEST (body)))
+ case REG:
+ regno = REGNO (x);
+ if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
return 1;
return 0;
- case ASM_OPERANDS:
- for (i = ASM_OPERANDS_INPUT_LENGTH (body) - 1; i >= 0; i--)
- if (reg_overlap_mentioned_p (x, ASM_OPERANDS_INPUT (body, i)))
- return 1;
+ case SCRATCH:
+ case PC:
+ case CC0:
+ case CONST_INT:
+ case CONST_DOUBLE:
+ case CONST:
+ case LABEL_REF:
return 0;
case CALL:
- case USE:
- return reg_overlap_mentioned_p (x, body);
-
- case TRAP_IF:
- return reg_overlap_mentioned_p (x, TRAP_CONDITION (body));
+ /* A non-constant call might use a global register. */
+ return 1;
- case UNSPEC:
- case UNSPEC_VOLATILE:
- case PARALLEL:
- for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
- if (reg_referenced_p (x, XVECEXP (body, 0, i)))
- return 1;
- return 0;
-
default:
- return 0;
+ break;
}
-}
-
-/* Nonzero if register REG is referenced in an insn between
- FROM_INSN and TO_INSN (exclusive of those two). Sets of REG do
- not count. */
-
-int
-reg_referenced_between_p (reg, from_insn, to_insn)
- rtx reg, from_insn, to_insn;
-{
- register rtx insn;
-
- if (from_insn == to_insn)
- return 0;
-
- for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
- if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
- && (reg_referenced_p (reg, PATTERN (insn))
- || (GET_CODE (insn) == CALL_INSN
- && find_reg_fusage (insn, USE, reg))))
- return 1;
- return 0;
-}
-\f
-/* Nonzero if register REG is set or clobbered in an insn between
- FROM_INSN and TO_INSN (exclusive of those two). */
-
-int
-reg_set_between_p (reg, from_insn, to_insn)
- rtx reg, from_insn, to_insn;
-{
- register rtx insn;
-
- if (from_insn == to_insn)
- return 0;
- for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
- if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
- && reg_set_p (reg, insn))
- return 1;
return 0;
}
-/* Internals of reg_set_between_p. */
-
-static rtx reg_set_reg;
-static int reg_set_flag;
-
-static void
-reg_set_p_1 (x, pat)
- rtx x;
- rtx pat ATTRIBUTE_UNUSED;
-{
- /* We don't want to return 1 if X is a MEM that contains a register
- within REG_SET_REG. */
-
- if ((GET_CODE (x) != MEM)
- && reg_overlap_mentioned_p (reg_set_reg, x))
- reg_set_flag = 1;
-}
+/* Returns nonzero if X mentions a global register. */
int
-reg_set_p (reg, insn)
- rtx reg, insn;
+global_reg_mentioned_p (rtx x)
{
- rtx body = insn;
-
- /* We can be passed an insn or part of one. If we are passed an insn,
- check if a side-effect of the insn clobbers REG. */
- if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
- {
- if (FIND_REG_INC_NOTE (insn, reg)
- || (GET_CODE (insn) == CALL_INSN
- /* We'd like to test call_used_regs here, but rtlanal.c can't
- reference that variable due to its use in genattrtab. So
- we'll just be more conservative.
-
- ??? Unless we could ensure that the CALL_INSN_FUNCTION_USAGE
- information holds all clobbered registers. */
- && ((GET_CODE (reg) == REG
- && REGNO (reg) < FIRST_PSEUDO_REGISTER)
- || GET_CODE (reg) == MEM
- || find_reg_fusage (insn, CLOBBER, reg))))
- return 1;
-
- body = PATTERN (insn);
+ if (INSN_P (x))
+ {
+ if (CALL_P (x))
+ {
+ if (! CONST_OR_PURE_CALL_P (x))
+ return 1;
+ x = CALL_INSN_FUNCTION_USAGE (x);
+ if (x == 0)
+ return 0;
+ }
+ else
+ x = PATTERN (x);
}
- reg_set_reg = reg;
- reg_set_flag = 0;
- note_stores (body, reg_set_p_1);
- return reg_set_flag;
+ return for_each_rtx (&x, global_reg_mentioned_p_1, NULL);
}
-
-/* Similar to reg_set_between_p, but check all registers in X. Return 0
- only if none of them are modified between START and END. Return 1 if
- X contains a MEM; this routine does not perform any memory aliasing. */
+\f
+/* Return the number of places FIND appears within X. If COUNT_DEST is
+ zero, we do not count occurrences inside the destination of a SET. */
int
-modified_between_p (x, start, end)
- rtx x;
- rtx start, end;
+count_occurrences (rtx x, rtx find, int count_dest)
{
- enum rtx_code code = GET_CODE (x);
- char *fmt;
int i, j;
+ enum rtx_code code;
+ const char *format_ptr;
+ int count;
+
+ if (x == find)
+ return 1;
+
+ code = GET_CODE (x);
switch (code)
{
+ case REG:
case CONST_INT:
case CONST_DOUBLE:
- case CONST:
+ case CONST_VECTOR:
case SYMBOL_REF:
- case LABEL_REF:
- return 0;
-
+ case CODE_LABEL:
case PC:
case CC0:
- return 1;
+ return 0;
case MEM:
- /* If the memory is not constant, assume it is modified. If it is
- constant, we still have to check the address. */
- if (! RTX_UNCHANGING_P (x))
+ if (MEM_P (find) && rtx_equal_p (x, find))
return 1;
break;
- case REG:
- return reg_set_between_p (x, start, end);
-
+ case SET:
+ if (SET_DEST (x) == find && ! count_dest)
+ return count_occurrences (SET_SRC (x), find, count_dest);
+ break;
+
default:
break;
}
- fmt = GET_RTX_FORMAT (code);
- for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+ format_ptr = GET_RTX_FORMAT (code);
+ count = 0;
+
+ for (i = 0; i < GET_RTX_LENGTH (code); i++)
{
- if (fmt[i] == 'e' && modified_between_p (XEXP (x, i), start, end))
- return 1;
+ switch (*format_ptr++)
+ {
+ case 'e':
+ count += count_occurrences (XEXP (x, i), find, count_dest);
+ break;
- if (fmt[i] == 'E')
- for (j = XVECLEN (x, i) - 1; j >= 0; j--)
- if (modified_between_p (XVECEXP (x, i, j), start, end))
- return 1;
+ case 'E':
+ for (j = 0; j < XVECLEN (x, i); j++)
+ count += count_occurrences (XVECEXP (x, i, j), find, count_dest);
+ break;
+ }
}
-
- return 0;
+ return count;
}
-
-/* Similar to reg_set_p, but check all registers in X. Return 0 only if none
- of them are modified in INSN. Return 1 if X contains a MEM; this routine
- does not perform any memory aliasing. */
+\f
+/* Nonzero if register REG appears somewhere within IN.
+ Also works if REG is not a register; in this case it checks
+ for a subexpression of IN that is Lisp "equal" to REG. */
int
-modified_in_p (x, insn)
- rtx x;
- rtx insn;
+reg_mentioned_p (rtx reg, rtx in)
{
- enum rtx_code code = GET_CODE (x);
- char *fmt;
- int i, j;
+ const char *fmt;
+ int i;
+ enum rtx_code code;
+
+ if (in == 0)
+ return 0;
+
+ if (reg == in)
+ return 1;
+
+ if (GET_CODE (in) == LABEL_REF)
+ return reg == XEXP (in, 0);
+
+ code = GET_CODE (in);
switch (code)
{
- case CONST_INT:
- case CONST_DOUBLE:
- case CONST:
- case SYMBOL_REF:
- case LABEL_REF:
- return 0;
+ /* Compare registers by number. */
+ case REG:
+ return REG_P (reg) && REGNO (in) == REGNO (reg);
- case PC:
+ /* These codes have no constituent expressions
+ and are unique. */
+ case SCRATCH:
case CC0:
- return 1;
-
- case MEM:
- /* If the memory is not constant, assume it is modified. If it is
- constant, we still have to check the address. */
- if (! RTX_UNCHANGING_P (x))
- return 1;
- break;
+ case PC:
+ return 0;
- case REG:
- return reg_set_p (x, insn);
+ case CONST_INT:
+ case CONST_VECTOR:
+ case CONST_DOUBLE:
+ /* These are kept unique for a given value. */
+ return 0;
default:
break;
}
+ if (GET_CODE (reg) == code && rtx_equal_p (reg, in))
+ return 1;
+
fmt = GET_RTX_FORMAT (code);
+
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
- if (fmt[i] == 'e' && modified_in_p (XEXP (x, i), insn))
- return 1;
-
if (fmt[i] == 'E')
- for (j = XVECLEN (x, i) - 1; j >= 0; j--)
- if (modified_in_p (XVECEXP (x, i, j), insn))
- return 1;
+ {
+ int j;
+ for (j = XVECLEN (in, i) - 1; j >= 0; j--)
+ if (reg_mentioned_p (reg, XVECEXP (in, i, j)))
+ return 1;
+ }
+ else if (fmt[i] == 'e'
+ && reg_mentioned_p (reg, XEXP (in, i)))
+ return 1;
}
-
return 0;
}
\f
-/* Given an INSN, return a SET expression if this insn has only a single SET.
- It may also have CLOBBERs, USEs, or SET whose output
- will not be used, which we ignore. */
+/* Return 1 if in between BEG and END, exclusive of BEG and END, there is
+ no CODE_LABEL insn. */
-rtx
-single_set (insn)
- rtx insn;
+int
+no_labels_between_p (rtx beg, rtx end)
{
- rtx set;
- int i;
-
- if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
+ rtx p;
+ if (beg == end)
return 0;
-
- if (GET_CODE (PATTERN (insn)) == SET)
- return PATTERN (insn);
-
- else if (GET_CODE (PATTERN (insn)) == PARALLEL)
- {
- for (i = 0, set = 0; i < XVECLEN (PATTERN (insn), 0); i++)
- if (GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == SET
- && (! find_reg_note (insn, REG_UNUSED,
- SET_DEST (XVECEXP (PATTERN (insn), 0, i)))
- || side_effects_p (XVECEXP (PATTERN (insn), 0, i))))
- {
- if (set)
- return 0;
- else
- set = XVECEXP (PATTERN (insn), 0, i);
- }
- return set;
- }
-
- return 0;
+ for (p = NEXT_INSN (beg); p != end; p = NEXT_INSN (p))
+ if (LABEL_P (p))
+ return 0;
+ return 1;
}
-\f
-/* Return the last thing that X was assigned from before *PINSN. Verify that
- the object is not modified up to VALID_TO. If it was, if we hit
- a partial assignment to X, or hit a CODE_LABEL first, return X. If we
- found an assignment, update *PINSN to point to it. */
-rtx
-find_last_value (x, pinsn, valid_to)
- rtx x;
- rtx *pinsn;
- rtx valid_to;
+/* Return 1 if in between BEG and END, exclusive of BEG and END, there is
+ no JUMP_INSN insn. */
+
+int
+no_jumps_between_p (rtx beg, rtx end)
{
rtx p;
+ for (p = NEXT_INSN (beg); p != end; p = NEXT_INSN (p))
+ if (JUMP_P (p))
+ return 0;
+ return 1;
+}
- for (p = PREV_INSN (*pinsn); p && GET_CODE (p) != CODE_LABEL;
- p = PREV_INSN (p))
- if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
- {
- rtx set = single_set (p);
- rtx note = find_reg_note (p, REG_EQUAL, NULL_RTX);
-
- if (set && rtx_equal_p (x, SET_DEST (set)))
- {
- rtx src = SET_SRC (set);
+/* Nonzero if register REG is used in an insn between
+ FROM_INSN and TO_INSN (exclusive of those two). */
- if (note && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
- src = XEXP (note, 0);
+int
+reg_used_between_p (rtx reg, rtx from_insn, rtx to_insn)
+{
+ rtx insn;
- if (! modified_between_p (src, PREV_INSN (p), valid_to)
- /* Reject hard registers because we don't usually want
- to use them; we'd rather use a pseudo. */
- && ! (GET_CODE (src) == REG
- && REGNO (src) < FIRST_PSEUDO_REGISTER))
- {
- *pinsn = p;
- return src;
- }
- }
-
- /* If set in non-simple way, we don't have a value. */
- if (reg_set_p (x, p))
- break;
- }
+ if (from_insn == to_insn)
+ return 0;
- return x;
-}
+ for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
+ if (INSN_P (insn)
+ && (reg_overlap_mentioned_p (reg, PATTERN (insn))
+ || (CALL_P (insn)
+ && (find_reg_fusage (insn, USE, reg)
+ || find_reg_fusage (insn, CLOBBER, reg)))))
+ return 1;
+ return 0;
+}
\f
-/* Return nonzero if register in range [REGNO, ENDREGNO)
- appears either explicitly or implicitly in X
- other than being stored into.
-
- References contained within the substructure at LOC do not count.
- LOC may be zero, meaning don't ignore anything. */
+/* Nonzero if the old value of X, a register, is referenced in BODY. If X
+ is entirely replaced by a new value and the only use is as a SET_DEST,
+ we do not consider it a reference. */
int
-refers_to_regno_p (regno, endregno, x, loc)
- int regno, endregno;
- rtx x;
- rtx *loc;
+reg_referenced_p (rtx x, rtx body)
{
- register int i;
- register RTX_CODE code;
- register char *fmt;
-
- repeat:
- /* The contents of a REG_NONNEG note is always zero, so we must come here
- upon repeat in case the last REG_NOTE is a REG_NONNEG note. */
- if (x == 0)
- return 0;
-
- code = GET_CODE (x);
+ int i;
- switch (code)
+ switch (GET_CODE (body))
{
- case REG:
- i = REGNO (x);
-
- /* If we modifying the stack, frame, or argument pointer, it will
- clobber a virtual register. In fact, we could be more precise,
- but it isn't worth it. */
- if ((i == STACK_POINTER_REGNUM
-#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
- || i == ARG_POINTER_REGNUM
-#endif
- || i == FRAME_POINTER_REGNUM)
- && regno >= FIRST_VIRTUAL_REGISTER && regno <= LAST_VIRTUAL_REGISTER)
+ case SET:
+ if (reg_overlap_mentioned_p (x, SET_SRC (body)))
return 1;
- return (endregno > i
- && regno < i + (i < FIRST_PSEUDO_REGISTER
- ? HARD_REGNO_NREGS (i, GET_MODE (x))
- : 1));
-
- case SUBREG:
- /* If this is a SUBREG of a hard reg, we can see exactly which
- registers are being modified. Otherwise, handle normally. */
- if (GET_CODE (SUBREG_REG (x)) == REG
- && REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER)
- {
- int inner_regno = REGNO (SUBREG_REG (x)) + SUBREG_WORD (x);
- int inner_endregno
- = inner_regno + (inner_regno < FIRST_PSEUDO_REGISTER
- ? HARD_REGNO_NREGS (regno, GET_MODE (x)) : 1);
-
- return endregno > inner_regno && regno < inner_endregno;
- }
- break;
-
- case CLOBBER:
- case SET:
- if (&SET_DEST (x) != loc
- /* Note setting a SUBREG counts as referring to the REG it is in for
- a pseudo but not for hard registers since we can
- treat each word individually. */
- && ((GET_CODE (SET_DEST (x)) == SUBREG
- && loc != &SUBREG_REG (SET_DEST (x))
- && GET_CODE (SUBREG_REG (SET_DEST (x))) == REG
- && REGNO (SUBREG_REG (SET_DEST (x))) >= FIRST_PSEUDO_REGISTER
- && refers_to_regno_p (regno, endregno,
- SUBREG_REG (SET_DEST (x)), loc))
- || (GET_CODE (SET_DEST (x)) != REG
- && refers_to_regno_p (regno, endregno, SET_DEST (x), loc))))
+ /* If the destination is anything other than CC0, PC, a REG or a SUBREG
+ of a REG that occupies all of the REG, the insn references X if
+ it is mentioned in the destination. */
+ if (GET_CODE (SET_DEST (body)) != CC0
+ && GET_CODE (SET_DEST (body)) != PC
+ && !REG_P (SET_DEST (body))
+ && ! (GET_CODE (SET_DEST (body)) == SUBREG
+ && REG_P (SUBREG_REG (SET_DEST (body)))
+ && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (SET_DEST (body))))
+ + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD)
+ == ((GET_MODE_SIZE (GET_MODE (SET_DEST (body)))
+ + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD)))
+ && reg_overlap_mentioned_p (x, SET_DEST (body)))
return 1;
+ return 0;
- if (code == CLOBBER || loc == &SET_SRC (x))
- return 0;
- x = SET_SRC (x);
- goto repeat;
-
- default:
- break;
- }
+ case ASM_OPERANDS:
+ for (i = ASM_OPERANDS_INPUT_LENGTH (body) - 1; i >= 0; i--)
+ if (reg_overlap_mentioned_p (x, ASM_OPERANDS_INPUT (body, i)))
+ return 1;
+ return 0;
- /* X does not match, so try its subexpressions. */
+ case CALL:
+ case USE:
+ case IF_THEN_ELSE:
+ return reg_overlap_mentioned_p (x, body);
- fmt = GET_RTX_FORMAT (code);
- for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
- {
- if (fmt[i] == 'e' && loc != &XEXP (x, i))
- {
- if (i == 0)
- {
- x = XEXP (x, 0);
- goto repeat;
- }
- else
- if (refers_to_regno_p (regno, endregno, XEXP (x, i), loc))
- return 1;
- }
- else if (fmt[i] == 'E')
- {
- register int j;
- for (j = XVECLEN (x, i) - 1; j >=0; j--)
- if (loc != &XVECEXP (x, i, j)
- && refers_to_regno_p (regno, endregno, XVECEXP (x, i, j), loc))
- return 1;
- }
- }
- return 0;
-}
+ case TRAP_IF:
+ return reg_overlap_mentioned_p (x, TRAP_CONDITION (body));
-/* Nonzero if modifying X will affect IN. If X is a register or a SUBREG,
- we check if any register number in X conflicts with the relevant register
- numbers. If X is a constant, return 0. If X is a MEM, return 1 iff IN
- contains a MEM (we don't bother checking for memory addresses that can't
- conflict because we expect this to be a rare case. */
+ case PREFETCH:
+ return reg_overlap_mentioned_p (x, XEXP (body, 0));
-int
-reg_overlap_mentioned_p (x, in)
- rtx x, in;
-{
- int regno, endregno;
+ case UNSPEC:
+ case UNSPEC_VOLATILE:
+ for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
+ if (reg_overlap_mentioned_p (x, XVECEXP (body, 0, i)))
+ return 1;
+ return 0;
- /* Overly conservative. */
- if (GET_CODE (x) == STRICT_LOW_PART)
- x = XEXP (x, 0);
+ case PARALLEL:
+ for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
+ if (reg_referenced_p (x, XVECEXP (body, 0, i)))
+ return 1;
+ return 0;
- /* If either argument is a constant, then modifying X can not affect IN. */
- if (CONSTANT_P (x) || CONSTANT_P (in))
- return 0;
- else if (GET_CODE (x) == SUBREG)
- {
- regno = REGNO (SUBREG_REG (x));
- if (regno < FIRST_PSEUDO_REGISTER)
- regno += SUBREG_WORD (x);
- }
- else if (GET_CODE (x) == REG)
- regno = REGNO (x);
- else if (GET_CODE (x) == MEM)
- {
- char *fmt;
- int i;
+ case CLOBBER:
+ if (MEM_P (XEXP (body, 0)))
+ if (reg_overlap_mentioned_p (x, XEXP (XEXP (body, 0), 0)))
+ return 1;
+ return 0;
- if (GET_CODE (in) == MEM)
+ case COND_EXEC:
+ if (reg_overlap_mentioned_p (x, COND_EXEC_TEST (body)))
return 1;
+ return reg_referenced_p (x, COND_EXEC_CODE (body));
- fmt = GET_RTX_FORMAT (GET_CODE (in));
-
- for (i = GET_RTX_LENGTH (GET_CODE (in)) - 1; i >= 0; i--)
- if (fmt[i] == 'e' && reg_overlap_mentioned_p (x, XEXP (in, i)))
- return 1;
-
+ default:
return 0;
}
- else if (GET_CODE (x) == SCRATCH || GET_CODE (x) == PC
- || GET_CODE (x) == CC0)
- return reg_mentioned_p (x, in);
- else if (GET_CODE (x) == PARALLEL
- && GET_MODE (x) == BLKmode)
- {
- register int i;
+}
- /* If any register in here refers to it
- we return true. */
- for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
- if (reg_overlap_mentioned_p (SET_DEST (XVECEXP (x, 0, i)), in))
- return 1;
- return 0;
- }
- else
- abort ();
+/* Nonzero if register REG is referenced in an insn between
+ FROM_INSN and TO_INSN (exclusive of those two). Sets of REG do
+ not count. */
- endregno = regno + (regno < FIRST_PSEUDO_REGISTER
- ? HARD_REGNO_NREGS (regno, GET_MODE (x)) : 1);
+int
+reg_referenced_between_p (rtx reg, rtx from_insn, rtx to_insn)
+{
+ rtx insn;
+
+ if (from_insn == to_insn)
+ return 0;
- return refers_to_regno_p (regno, endregno, in, NULL_PTR);
+ for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
+ if (INSN_P (insn)
+ && (reg_referenced_p (reg, PATTERN (insn))
+ || (CALL_P (insn)
+ && find_reg_fusage (insn, USE, reg))))
+ return 1;
+ return 0;
}
\f
-/* Used for communications between the next few functions. */
-
-static int reg_set_last_unknown;
-static rtx reg_set_last_value;
-static int reg_set_last_first_regno, reg_set_last_last_regno;
-
-/* Called via note_stores from reg_set_last. */
+/* Nonzero if register REG is set or clobbered in an insn between
+ FROM_INSN and TO_INSN (exclusive of those two). */
-static void
-reg_set_last_1 (x, pat)
- rtx x;
- rtx pat;
+int
+reg_set_between_p (rtx reg, rtx from_insn, rtx to_insn)
{
- int first, last;
+ rtx insn;
- /* If X is not a register, or is not one in the range we care
- about, ignore. */
- if (GET_CODE (x) != REG)
- return;
+ if (from_insn == to_insn)
+ return 0;
- first = REGNO (x);
- last = first + (first < FIRST_PSEUDO_REGISTER
- ? HARD_REGNO_NREGS (first, GET_MODE (x)) : 1);
+ for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
+ if (INSN_P (insn) && reg_set_p (reg, insn))
+ return 1;
+ return 0;
+}
- if (first >= reg_set_last_last_regno
- || last <= reg_set_last_first_regno)
- return;
+/* Internals of reg_set_between_p. */
+int
+reg_set_p (rtx reg, rtx insn)
+{
+ /* We can be passed an insn or part of one. If we are passed an insn,
+ check if a side-effect of the insn clobbers REG. */
+ if (INSN_P (insn)
+ && (FIND_REG_INC_NOTE (insn, reg)
+ || (CALL_P (insn)
+ && ((REG_P (reg)
+ && REGNO (reg) < FIRST_PSEUDO_REGISTER
+ && TEST_HARD_REG_BIT (regs_invalidated_by_call,
+ REGNO (reg)))
+ || MEM_P (reg)
+ || find_reg_fusage (insn, CLOBBER, reg)))))
+ return 1;
- /* If this is a CLOBBER or is some complex LHS, or doesn't modify
- exactly the registers we care about, show we don't know the value. */
- if (GET_CODE (pat) == CLOBBER || SET_DEST (pat) != x
- || first != reg_set_last_first_regno
- || last != reg_set_last_last_regno)
- reg_set_last_unknown = 1;
- else
- reg_set_last_value = SET_SRC (pat);
+ return set_of (reg, insn) != NULL_RTX;
}
-/* Return the last value to which REG was set prior to INSN. If we can't
- find it easily, return 0.
-
- We only return a REG, SUBREG, or constant because it is too hard to
- check if a MEM remains unchanged. */
+/* Similar to reg_set_between_p, but check all registers in X. Return 0
+ only if none of them are modified between START and END. Do not
+ consider non-registers one way or the other. */
-rtx
-reg_set_last (x, insn)
- rtx x;
- rtx insn;
+int
+regs_set_between_p (rtx x, rtx start, rtx end)
{
- rtx orig_insn = insn;
-
- reg_set_last_first_regno = REGNO (x);
+ enum rtx_code code = GET_CODE (x);
+ const char *fmt;
+ int i, j;
- reg_set_last_last_regno
- = reg_set_last_first_regno
- + (reg_set_last_first_regno < FIRST_PSEUDO_REGISTER
- ? HARD_REGNO_NREGS (reg_set_last_first_regno, GET_MODE (x)) : 1);
+ switch (code)
+ {
+ case CONST_INT:
+ case CONST_DOUBLE:
+ case CONST_VECTOR:
+ case CONST:
+ case SYMBOL_REF:
+ case LABEL_REF:
+ case PC:
+ case CC0:
+ return 0;
- reg_set_last_unknown = 0;
- reg_set_last_value = 0;
+ case REG:
+ return reg_set_between_p (x, start, end);
- /* Scan backwards until reg_set_last_1 changed one of the above flags.
- Stop when we reach a label or X is a hard reg and we reach a
- CALL_INSN (if reg_set_last_last_regno is a hard reg).
+ default:
+ break;
+ }
- If we find a set of X, ensure that its SET_SRC remains unchanged. */
+ fmt = GET_RTX_FORMAT (code);
+ for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+ {
+ if (fmt[i] == 'e' && regs_set_between_p (XEXP (x, i), start, end))
+ return 1;
- /* We compare with <= here, because reg_set_last_last_regno
- is actually the number of the first reg *not* in X. */
- for (;
- insn && GET_CODE (insn) != CODE_LABEL
- && ! (GET_CODE (insn) == CALL_INSN
- && reg_set_last_last_regno <= FIRST_PSEUDO_REGISTER);
- insn = PREV_INSN (insn))
- if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
- {
- note_stores (PATTERN (insn), reg_set_last_1);
- if (reg_set_last_unknown)
- return 0;
- else if (reg_set_last_value)
- {
- if (CONSTANT_P (reg_set_last_value)
- || ((GET_CODE (reg_set_last_value) == REG
- || GET_CODE (reg_set_last_value) == SUBREG)
- && ! reg_set_between_p (reg_set_last_value,
- insn, orig_insn)))
- return reg_set_last_value;
- else
- return 0;
- }
- }
+ else if (fmt[i] == 'E')
+ for (j = XVECLEN (x, i) - 1; j >= 0; j--)
+ if (regs_set_between_p (XVECEXP (x, i, j), start, end))
+ return 1;
+ }
return 0;
}
-\f
-/* This is 1 until after the rtl generation pass. */
-int rtx_equal_function_value_matters;
-/* Return 1 if X and Y are identical-looking rtx's.
- This is the Lisp function EQUAL for rtx arguments. */
+/* Similar to reg_set_between_p, but check all registers in X. Return 0
+ only if none of them are modified between START and END. Return 1 if
+ X contains a MEM; this routine does usememory aliasing. */
int
-rtx_equal_p (x, y)
- rtx x, y;
+modified_between_p (rtx x, rtx start, rtx end)
{
- register int i;
- register int j;
- register enum rtx_code code;
- register char *fmt;
+ enum rtx_code code = GET_CODE (x);
+ const char *fmt;
+ int i, j;
+ rtx insn;
- if (x == y)
- return 1;
- if (x == 0 || y == 0)
+ if (start == end)
return 0;
- code = GET_CODE (x);
- /* Rtx's of different codes cannot be equal. */
- if (code != GET_CODE (y))
- return 0;
+ switch (code)
+ {
+ case CONST_INT:
+ case CONST_DOUBLE:
+ case CONST_VECTOR:
+ case CONST:
+ case SYMBOL_REF:
+ case LABEL_REF:
+ return 0;
- /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
- (REG:SI x) and (REG:HI x) are NOT equivalent. */
+ case PC:
+ case CC0:
+ return 1;
- if (GET_MODE (x) != GET_MODE (y))
- return 0;
+ case MEM:
+ if (MEM_READONLY_P (x))
+ return 0;
+ if (modified_between_p (XEXP (x, 0), start, end))
+ return 1;
+ for (insn = NEXT_INSN (start); insn != end; insn = NEXT_INSN (insn))
+ if (memory_modified_in_insn_p (x, insn))
+ return 1;
+ return 0;
+ break;
- /* REG, LABEL_REF, and SYMBOL_REF can be compared nonrecursively. */
-
- if (code == REG)
- /* Until rtl generation is complete, don't consider a reference to the
- return register of the current function the same as the return from a
- called function. This eases the job of function integration. Once the
- distinction is no longer needed, they can be considered equivalent. */
- return (REGNO (x) == REGNO (y)
- && (! rtx_equal_function_value_matters
- || REG_FUNCTION_VALUE_P (x) == REG_FUNCTION_VALUE_P (y)));
- else if (code == LABEL_REF)
- return XEXP (x, 0) == XEXP (y, 0);
- else if (code == SYMBOL_REF)
- return XSTR (x, 0) == XSTR (y, 0);
- else if (code == SCRATCH || code == CONST_DOUBLE)
- return 0;
+ case REG:
+ return reg_set_between_p (x, start, end);
- /* Compare the elements. If any pair of corresponding elements
- fail to match, return 0 for the whole things. */
+ default:
+ break;
+ }
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
- switch (fmt[i])
- {
- case 'w':
- if (XWINT (x, i) != XWINT (y, i))
- return 0;
- break;
-
- case 'n':
- case 'i':
- if (XINT (x, i) != XINT (y, i))
- return 0;
- break;
+ if (fmt[i] == 'e' && modified_between_p (XEXP (x, i), start, end))
+ return 1;
- case 'V':
- case 'E':
- /* Two vectors must have the same length. */
- if (XVECLEN (x, i) != XVECLEN (y, i))
- return 0;
+ else if (fmt[i] == 'E')
+ for (j = XVECLEN (x, i) - 1; j >= 0; j--)
+ if (modified_between_p (XVECEXP (x, i, j), start, end))
+ return 1;
+ }
- /* And the corresponding elements must match. */
- for (j = 0; j < XVECLEN (x, i); j++)
- if (rtx_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
- return 0;
- break;
+ return 0;
+}
- case 'e':
- if (rtx_equal_p (XEXP (x, i), XEXP (y, i)) == 0)
- return 0;
- break;
+/* Similar to reg_set_p, but check all registers in X. Return 0 only if none
+ of them are modified in INSN. Return 1 if X contains a MEM; this routine
+ does use memory aliasing. */
- case 'S':
- case 's':
- if (strcmp (XSTR (x, i), XSTR (y, i)))
- return 0;
- break;
+int
+modified_in_p (rtx x, rtx insn)
+{
+ enum rtx_code code = GET_CODE (x);
+ const char *fmt;
+ int i, j;
- case 'u':
- /* These are just backpointers, so they don't matter. */
- break;
+ switch (code)
+ {
+ case CONST_INT:
+ case CONST_DOUBLE:
+ case CONST_VECTOR:
+ case CONST:
+ case SYMBOL_REF:
+ case LABEL_REF:
+ return 0;
- case '0':
- break;
+ case PC:
+ case CC0:
+ return 1;
- /* It is believed that rtx's at this level will never
- contain anything but integers and other rtx's,
- except for within LABEL_REFs and SYMBOL_REFs. */
- default:
- abort ();
- }
+ case MEM:
+ if (MEM_READONLY_P (x))
+ return 0;
+ if (modified_in_p (XEXP (x, 0), insn))
+ return 1;
+ if (memory_modified_in_insn_p (x, insn))
+ return 1;
+ return 0;
+ break;
+
+ case REG:
+ return reg_set_p (x, insn);
+
+ default:
+ break;
}
- return 1;
+
+ fmt = GET_RTX_FORMAT (code);
+ for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+ {
+ if (fmt[i] == 'e' && modified_in_p (XEXP (x, i), insn))
+ return 1;
+
+ else if (fmt[i] == 'E')
+ for (j = XVECLEN (x, i) - 1; j >= 0; j--)
+ if (modified_in_p (XVECEXP (x, i, j), insn))
+ return 1;
+ }
+
+ return 0;
+}
+
+/* Return true if anything in insn X is (anti,output,true) dependent on
+ anything in insn Y. */
+
+int
+insn_dependent_p (rtx x, rtx y)
+{
+ rtx tmp;
+
+ gcc_assert (INSN_P (x));
+ gcc_assert (INSN_P (y));
+
+ tmp = PATTERN (y);
+ note_stores (PATTERN (x), insn_dependent_p_1, &tmp);
+ if (tmp == NULL_RTX)
+ return 1;
+
+ tmp = PATTERN (x);
+ note_stores (PATTERN (y), insn_dependent_p_1, &tmp);
+ if (tmp == NULL_RTX)
+ return 1;
+
+ return 0;
+}
+
+/* A helper routine for insn_dependent_p called through note_stores. */
+
+static void
+insn_dependent_p_1 (rtx x, rtx pat ATTRIBUTE_UNUSED, void *data)
+{
+ rtx * pinsn = (rtx *) data;
+
+ if (*pinsn && reg_mentioned_p (x, *pinsn))
+ *pinsn = NULL_RTX;
}
\f
-/* Call FUN on each register or MEM that is stored into or clobbered by X.
- (X would be the pattern of an insn).
- FUN receives two arguments:
- the REG, MEM, CC0 or PC being stored in or clobbered,
- the SET or CLOBBER rtx that does the store.
+/* Helper function for set_of. */
+struct set_of_data
+ {
+ rtx found;
+ rtx pat;
+ };
- If the item being stored in or clobbered is a SUBREG of a hard register,
- the SUBREG will be passed. */
-
-void
-note_stores (x, fun)
- register rtx x;
- void (*fun) ();
+static void
+set_of_1 (rtx x, rtx pat, void *data1)
{
- if ((GET_CODE (x) == SET || GET_CODE (x) == CLOBBER))
- {
- register rtx dest = SET_DEST (x);
- while ((GET_CODE (dest) == SUBREG
- && (GET_CODE (SUBREG_REG (dest)) != REG
- || REGNO (SUBREG_REG (dest)) >= FIRST_PSEUDO_REGISTER))
- || GET_CODE (dest) == ZERO_EXTRACT
- || GET_CODE (dest) == SIGN_EXTRACT
- || GET_CODE (dest) == STRICT_LOW_PART)
- dest = XEXP (dest, 0);
+ struct set_of_data *data = (struct set_of_data *) (data1);
+ if (rtx_equal_p (x, data->pat)
+ || (!MEM_P (x) && reg_overlap_mentioned_p (data->pat, x)))
+ data->found = pat;
+}
- if (GET_CODE (dest) == PARALLEL
- && GET_MODE (dest) == BLKmode)
- {
- register int i;
- for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
- (*fun) (SET_DEST (XVECEXP (dest, 0, i)), x);
- }
- else
- (*fun) (dest, x);
- }
- else if (GET_CODE (x) == PARALLEL)
+/* Give an INSN, return a SET or CLOBBER expression that does modify PAT
+ (either directly or via STRICT_LOW_PART and similar modifiers). */
+rtx
+set_of (rtx pat, rtx insn)
+{
+ struct set_of_data data;
+ data.found = NULL_RTX;
+ data.pat = pat;
+ note_stores (INSN_P (insn) ? PATTERN (insn) : insn, set_of_1, &data);
+ return data.found;
+}
+\f
+/* Given an INSN, return a SET expression if this insn has only a single SET.
+ It may also have CLOBBERs, USEs, or SET whose output
+ will not be used, which we ignore. */
+
+rtx
+single_set_2 (rtx insn, rtx pat)
+{
+ rtx set = NULL;
+ int set_verified = 1;
+ int i;
+
+ if (GET_CODE (pat) == PARALLEL)
{
- register int i;
- for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
+ for (i = 0; i < XVECLEN (pat, 0); i++)
{
- register rtx y = XVECEXP (x, 0, i);
- if (GET_CODE (y) == SET || GET_CODE (y) == CLOBBER)
+ rtx sub = XVECEXP (pat, 0, i);
+ switch (GET_CODE (sub))
{
- register rtx dest = SET_DEST (y);
- while ((GET_CODE (dest) == SUBREG
- && (GET_CODE (SUBREG_REG (dest)) != REG
- || (REGNO (SUBREG_REG (dest))
- >= FIRST_PSEUDO_REGISTER)))
- || GET_CODE (dest) == ZERO_EXTRACT
- || GET_CODE (dest) == SIGN_EXTRACT
- || GET_CODE (dest) == STRICT_LOW_PART)
- dest = XEXP (dest, 0);
- if (GET_CODE (dest) == PARALLEL
- && GET_MODE (dest) == BLKmode)
+ case USE:
+ case CLOBBER:
+ break;
+
+ case SET:
+ /* We can consider insns having multiple sets, where all
+ but one are dead as single set insns. In common case
+ only single set is present in the pattern so we want
+ to avoid checking for REG_UNUSED notes unless necessary.
+
+ When we reach set first time, we just expect this is
+ the single set we are looking for and only when more
+ sets are found in the insn, we check them. */
+ if (!set_verified)
{
- register int i;
- for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
- (*fun) (SET_DEST (XVECEXP (dest, 0, i)), y);
+ if (find_reg_note (insn, REG_UNUSED, SET_DEST (set))
+ && !side_effects_p (set))
+ set = NULL;
+ else
+ set_verified = 1;
}
- else
- (*fun) (dest, y);
+ if (!set)
+ set = sub, set_verified = 0;
+ else if (!find_reg_note (insn, REG_UNUSED, SET_DEST (sub))
+ || side_effects_p (sub))
+ return NULL_RTX;
+ break;
+
+ default:
+ return NULL_RTX;
}
}
}
+ return set;
}
-\f
-/* Return nonzero if X's old contents don't survive after INSN.
- This will be true if X is (cc0) or if X is a register and
- X dies in INSN or because INSN entirely sets X.
-
- "Entirely set" means set directly and not through a SUBREG,
- ZERO_EXTRACT or SIGN_EXTRACT, so no trace of the old contents remains.
- Likewise, REG_INC does not count.
-
- REG may be a hard or pseudo reg. Renumbering is not taken into account,
- but for this use that makes no difference, since regs don't overlap
- during their lifetimes. Therefore, this function may be used
- at any time after deaths have been computed (in flow.c).
- If REG is a hard reg that occupies multiple machine registers, this
- function will only return 1 if each of those registers will be replaced
- by INSN. */
+/* Given an INSN, return nonzero if it has more than one SET, else return
+ zero. */
int
-dead_or_set_p (insn, x)
- rtx insn;
- rtx x;
+multiple_sets (rtx insn)
{
- register int regno, last_regno;
- register int i;
-
- /* Can't use cc0_rtx below since this file is used by genattrtab.c. */
- if (GET_CODE (x) == CC0)
- return 1;
-
- if (GET_CODE (x) != REG)
- abort ();
+ int found;
+ int i;
- regno = REGNO (x);
- last_regno = (regno >= FIRST_PSEUDO_REGISTER ? regno
- : regno + HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1);
+ /* INSN must be an insn. */
+ if (! INSN_P (insn))
+ return 0;
- for (i = regno; i <= last_regno; i++)
- if (! dead_or_set_regno_p (insn, i))
- return 0;
+ /* Only a PARALLEL can have multiple SETs. */
+ if (GET_CODE (PATTERN (insn)) == PARALLEL)
+ {
+ for (i = 0, found = 0; i < XVECLEN (PATTERN (insn), 0); i++)
+ if (GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == SET)
+ {
+ /* If we have already found a SET, then return now. */
+ if (found)
+ return 1;
+ else
+ found = 1;
+ }
+ }
- return 1;
+ /* Either zero or one SET. */
+ return 0;
}
-
-/* Utility function for dead_or_set_p to check an individual register. Also
- called from flow.c. */
+\f
+/* Return nonzero if the destination of SET equals the source
+ and there are no side effects. */
int
-dead_or_set_regno_p (insn, test_regno)
- rtx insn;
- int test_regno;
+set_noop_p (rtx set)
{
- int regno, endregno;
- rtx link;
+ rtx src = SET_SRC (set);
+ rtx dst = SET_DEST (set);
- /* REG_READ notes are not normally maintained after reload, so we
- ignore them if the are invalid. */
- if (! reload_completed
-#ifdef PRESERVE_DEATH_INFO_REGNO_P
- || PRESERVE_DEATH_INFO_REGNO_P (test_regno)
-#endif
- )
- {
- /* See if there is a death note for something that includes
- TEST_REGNO. */
- for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
- {
- if (REG_NOTE_KIND (link) != REG_DEAD
- || GET_CODE (XEXP (link, 0)) != REG)
- continue;
+ if (dst == pc_rtx && src == pc_rtx)
+ return 1;
- regno = REGNO (XEXP (link, 0));
- endregno = (regno >= FIRST_PSEUDO_REGISTER ? regno + 1
- : regno + HARD_REGNO_NREGS (regno,
- GET_MODE (XEXP (link, 0))));
+ if (MEM_P (dst) && MEM_P (src))
+ return rtx_equal_p (dst, src) && !side_effects_p (dst);
- if (test_regno >= regno && test_regno < endregno)
- return 1;
- }
- }
+ if (GET_CODE (dst) == SIGN_EXTRACT
+ || GET_CODE (dst) == ZERO_EXTRACT)
+ return rtx_equal_p (XEXP (dst, 0), src)
+ && ! BYTES_BIG_ENDIAN && XEXP (dst, 2) == const0_rtx
+ && !side_effects_p (src);
- if (GET_CODE (insn) == CALL_INSN
- && find_regno_fusage (insn, CLOBBER, test_regno))
- return 1;
+ if (GET_CODE (dst) == STRICT_LOW_PART)
+ dst = XEXP (dst, 0);
- if (GET_CODE (PATTERN (insn)) == SET)
+ if (GET_CODE (src) == SUBREG && GET_CODE (dst) == SUBREG)
{
- rtx dest = SET_DEST (PATTERN (insn));
-
- /* A value is totally replaced if it is the destination or the
- destination is a SUBREG of REGNO that does not change the number of
- words in it. */
- if (GET_CODE (dest) == SUBREG
- && (((GET_MODE_SIZE (GET_MODE (dest))
- + UNITS_PER_WORD - 1) / UNITS_PER_WORD)
- == ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest)))
- + UNITS_PER_WORD - 1) / UNITS_PER_WORD)))
- dest = SUBREG_REG (dest);
-
- if (GET_CODE (dest) != REG)
+ if (SUBREG_BYTE (src) != SUBREG_BYTE (dst))
return 0;
+ src = SUBREG_REG (src);
+ dst = SUBREG_REG (dst);
+ }
- regno = REGNO (dest);
- endregno = (regno >= FIRST_PSEUDO_REGISTER ? regno + 1
- : regno + HARD_REGNO_NREGS (regno, GET_MODE (dest)));
+ return (REG_P (src) && REG_P (dst)
+ && REGNO (src) == REGNO (dst));
+}
+\f
+/* Return nonzero if an insn consists only of SETs, each of which only sets a
+ value to itself. */
- return (test_regno >= regno && test_regno < endregno);
- }
- else if (GET_CODE (PATTERN (insn)) == PARALLEL)
- {
- register int i;
+int
+noop_move_p (rtx insn)
+{
+ rtx pat = PATTERN (insn);
- for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
- {
- rtx body = XVECEXP (PATTERN (insn), 0, i);
+ if (INSN_CODE (insn) == NOOP_MOVE_INSN_CODE)
+ return 1;
- if (GET_CODE (body) == SET || GET_CODE (body) == CLOBBER)
- {
- rtx dest = SET_DEST (body);
+ /* Insns carrying these notes are useful later on. */
+ if (find_reg_note (insn, REG_EQUAL, NULL_RTX))
+ return 0;
- if (GET_CODE (dest) == SUBREG
- && (((GET_MODE_SIZE (GET_MODE (dest))
- + UNITS_PER_WORD - 1) / UNITS_PER_WORD)
- == ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest)))
- + UNITS_PER_WORD - 1) / UNITS_PER_WORD)))
- dest = SUBREG_REG (dest);
+ /* For now treat an insn with a REG_RETVAL note as a
+ a special insn which should not be considered a no-op. */
+ if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
+ return 0;
- if (GET_CODE (dest) != REG)
- continue;
+ if (GET_CODE (pat) == SET && set_noop_p (pat))
+ return 1;
- regno = REGNO (dest);
- endregno = (regno >= FIRST_PSEUDO_REGISTER ? regno + 1
- : regno + HARD_REGNO_NREGS (regno, GET_MODE (dest)));
+ if (GET_CODE (pat) == PARALLEL)
+ {
+ int i;
+ /* If nothing but SETs of registers to themselves,
+ this insn can also be deleted. */
+ for (i = 0; i < XVECLEN (pat, 0); i++)
+ {
+ rtx tem = XVECEXP (pat, 0, i);
- if (test_regno >= regno && test_regno < endregno)
- return 1;
- }
+ if (GET_CODE (tem) == USE
+ || GET_CODE (tem) == CLOBBER)
+ continue;
+
+ if (GET_CODE (tem) != SET || ! set_noop_p (tem))
+ return 0;
}
- }
+ return 1;
+ }
return 0;
}
+\f
-/* Return the reg-note of kind KIND in insn INSN, if there is one.
- If DATUM is nonzero, look for one whose datum is DATUM. */
+/* Return the last thing that X was assigned from before *PINSN. If VALID_TO
+ is not NULL_RTX then verify that the object is not modified up to VALID_TO.
+ If the object was modified, if we hit a partial assignment to X, or hit a
+ CODE_LABEL first, return X. If we found an assignment, update *PINSN to
+ point to it. ALLOW_HWREG is set to 1 if hardware registers are allowed to
+ be the src. */
rtx
-find_reg_note (insn, kind, datum)
- rtx insn;
- enum reg_note kind;
- rtx datum;
+find_last_value (rtx x, rtx *pinsn, rtx valid_to, int allow_hwreg)
{
- register rtx link;
+ rtx p;
- /* Ignore anything that is not an INSN, JUMP_INSN or CALL_INSN. */
- if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
- return 0;
+ for (p = PREV_INSN (*pinsn); p && !LABEL_P (p);
+ p = PREV_INSN (p))
+ if (INSN_P (p))
+ {
+ rtx set = single_set (p);
+ rtx note = find_reg_note (p, REG_EQUAL, NULL_RTX);
- for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
- if (REG_NOTE_KIND (link) == kind
- && (datum == 0 || datum == XEXP (link, 0)))
- return link;
- return 0;
-}
+ if (set && rtx_equal_p (x, SET_DEST (set)))
+ {
+ rtx src = SET_SRC (set);
-/* Return the reg-note of kind KIND in insn INSN which applies to register
- number REGNO, if any. Return 0 if there is no such reg-note. Note that
- the REGNO of this NOTE need not be REGNO if REGNO is a hard register;
- it might be the case that the note overlaps REGNO. */
+ if (note && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
+ src = XEXP (note, 0);
-rtx
-find_regno_note (insn, kind, regno)
- rtx insn;
- enum reg_note kind;
- int regno;
-{
- register rtx link;
+ if ((valid_to == NULL_RTX
+ || ! modified_between_p (src, PREV_INSN (p), valid_to))
+ /* Reject hard registers because we don't usually want
+ to use them; we'd rather use a pseudo. */
+ && (! (REG_P (src)
+ && REGNO (src) < FIRST_PSEUDO_REGISTER) || allow_hwreg))
+ {
+ *pinsn = p;
+ return src;
+ }
+ }
- /* Ignore anything that is not an INSN, JUMP_INSN or CALL_INSN. */
- if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
- return 0;
+ /* If set in non-simple way, we don't have a value. */
+ if (reg_set_p (x, p))
+ break;
+ }
- for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
- if (REG_NOTE_KIND (link) == kind
- /* Verify that it is a register, so that scratch and MEM won't cause a
- problem here. */
- && GET_CODE (XEXP (link, 0)) == REG
- && REGNO (XEXP (link, 0)) <= regno
- && ((REGNO (XEXP (link, 0))
- + (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
- : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)),
- GET_MODE (XEXP (link, 0)))))
- > regno))
- return link;
- return 0;
+ return x;
}
+\f
+/* Return nonzero if register in range [REGNO, ENDREGNO)
+ appears either explicitly or implicitly in X
+ other than being stored into.
-/* Return true if DATUM, or any overlap of DATUM, of kind CODE is found
- in the CALL_INSN_FUNCTION_USAGE information of INSN. */
+ References contained within the substructure at LOC do not count.
+ LOC may be zero, meaning don't ignore anything. */
int
-find_reg_fusage (insn, code, datum)
- rtx insn;
- enum rtx_code code;
- rtx datum;
+refers_to_regno_p (unsigned int regno, unsigned int endregno, rtx x,
+ rtx *loc)
{
- /* If it's not a CALL_INSN, it can't possibly have a
- CALL_INSN_FUNCTION_USAGE field, so don't bother checking. */
- if (GET_CODE (insn) != CALL_INSN)
+ int i;
+ unsigned int x_regno;
+ RTX_CODE code;
+ const char *fmt;
+
+ repeat:
+ /* The contents of a REG_NONNEG note is always zero, so we must come here
+ upon repeat in case the last REG_NOTE is a REG_NONNEG note. */
+ if (x == 0)
return 0;
- if (! datum)
- abort();
+ code = GET_CODE (x);
- if (GET_CODE (datum) != REG)
+ switch (code)
{
- register rtx link;
+ case REG:
+ x_regno = REGNO (x);
+
+ /* If we modifying the stack, frame, or argument pointer, it will
+ clobber a virtual register. In fact, we could be more precise,
+ but it isn't worth it. */
+ if ((x_regno == STACK_POINTER_REGNUM
+#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
+ || x_regno == ARG_POINTER_REGNUM
+#endif
+ || x_regno == FRAME_POINTER_REGNUM)
+ && regno >= FIRST_VIRTUAL_REGISTER && regno <= LAST_VIRTUAL_REGISTER)
+ return 1;
+
+ return (endregno > x_regno
+ && regno < x_regno + (x_regno < FIRST_PSEUDO_REGISTER
+ ? hard_regno_nregs[x_regno][GET_MODE (x)]
+ : 1));
+
+ case SUBREG:
+ /* If this is a SUBREG of a hard reg, we can see exactly which
+ registers are being modified. Otherwise, handle normally. */
+ if (REG_P (SUBREG_REG (x))
+ && REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER)
+ {
+ unsigned int inner_regno = subreg_regno (x);
+ unsigned int inner_endregno
+ = inner_regno + (inner_regno < FIRST_PSEUDO_REGISTER
+ ? hard_regno_nregs[inner_regno][GET_MODE (x)] : 1);
+
+ return endregno > inner_regno && regno < inner_endregno;
+ }
+ break;
+
+ case CLOBBER:
+ case SET:
+ if (&SET_DEST (x) != loc
+ /* Note setting a SUBREG counts as referring to the REG it is in for
+ a pseudo but not for hard registers since we can
+ treat each word individually. */
+ && ((GET_CODE (SET_DEST (x)) == SUBREG
+ && loc != &SUBREG_REG (SET_DEST (x))
+ && REG_P (SUBREG_REG (SET_DEST (x)))
+ && REGNO (SUBREG_REG (SET_DEST (x))) >= FIRST_PSEUDO_REGISTER
+ && refers_to_regno_p (regno, endregno,
+ SUBREG_REG (SET_DEST (x)), loc))
+ || (!REG_P (SET_DEST (x))
+ && refers_to_regno_p (regno, endregno, SET_DEST (x), loc))))
+ return 1;
+
+ if (code == CLOBBER || loc == &SET_SRC (x))
+ return 0;
+ x = SET_SRC (x);
+ goto repeat;
+
+ default:
+ break;
+ }
+
+ /* X does not match, so try its subexpressions. */
+
+ fmt = GET_RTX_FORMAT (code);
+ for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+ {
+ if (fmt[i] == 'e' && loc != &XEXP (x, i))
+ {
+ if (i == 0)
+ {
+ x = XEXP (x, 0);
+ goto repeat;
+ }
+ else
+ if (refers_to_regno_p (regno, endregno, XEXP (x, i), loc))
+ return 1;
+ }
+ else if (fmt[i] == 'E')
+ {
+ int j;
+ for (j = XVECLEN (x, i) - 1; j >= 0; j--)
+ if (loc != &XVECEXP (x, i, j)
+ && refers_to_regno_p (regno, endregno, XVECEXP (x, i, j), loc))
+ return 1;
+ }
+ }
+ return 0;
+}
+
+/* Nonzero if modifying X will affect IN. If X is a register or a SUBREG,
+ we check if any register number in X conflicts with the relevant register
+ numbers. If X is a constant, return 0. If X is a MEM, return 1 iff IN
+ contains a MEM (we don't bother checking for memory addresses that can't
+ conflict because we expect this to be a rare case. */
+
+int
+reg_overlap_mentioned_p (rtx x, rtx in)
+{
+ unsigned int regno, endregno;
+
+ /* If either argument is a constant, then modifying X can not
+ affect IN. Here we look at IN, we can profitably combine
+ CONSTANT_P (x) with the switch statement below. */
+ if (CONSTANT_P (in))
+ return 0;
+
+ recurse:
+ switch (GET_CODE (x))
+ {
+ case STRICT_LOW_PART:
+ case ZERO_EXTRACT:
+ case SIGN_EXTRACT:
+ /* Overly conservative. */
+ x = XEXP (x, 0);
+ goto recurse;
+
+ case SUBREG:
+ regno = REGNO (SUBREG_REG (x));
+ if (regno < FIRST_PSEUDO_REGISTER)
+ regno = subreg_regno (x);
+ goto do_reg;
+
+ case REG:
+ regno = REGNO (x);
+ do_reg:
+ endregno = regno + (regno < FIRST_PSEUDO_REGISTER
+ ? hard_regno_nregs[regno][GET_MODE (x)] : 1);
+ return refers_to_regno_p (regno, endregno, in, (rtx*) 0);
+
+ case MEM:
+ {
+ const char *fmt;
+ int i;
+
+ if (MEM_P (in))
+ return 1;
+
+ fmt = GET_RTX_FORMAT (GET_CODE (in));
+ for (i = GET_RTX_LENGTH (GET_CODE (in)) - 1; i >= 0; i--)
+ if (fmt[i] == 'e' && reg_overlap_mentioned_p (x, XEXP (in, i)))
+ return 1;
+
+ return 0;
+ }
+
+ case SCRATCH:
+ case PC:
+ case CC0:
+ return reg_mentioned_p (x, in);
+
+ case PARALLEL:
+ {
+ int i;
+
+ /* If any register in here refers to it we return true. */
+ for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
+ if (XEXP (XVECEXP (x, 0, i), 0) != 0
+ && reg_overlap_mentioned_p (XEXP (XVECEXP (x, 0, i), 0), in))
+ return 1;
+ return 0;
+ }
+
+ default:
+ gcc_assert (CONSTANT_P (x));
+ return 0;
+ }
+}
+\f
+/* Call FUN on each register or MEM that is stored into or clobbered by X.
+ (X would be the pattern of an insn).
+ FUN receives two arguments:
+ the REG, MEM, CC0 or PC being stored in or clobbered,
+ the SET or CLOBBER rtx that does the store.
+
+ If the item being stored in or clobbered is a SUBREG of a hard register,
+ the SUBREG will be passed. */
+
+void
+note_stores (rtx x, void (*fun) (rtx, rtx, void *), void *data)
+{
+ int i;
+
+ if (GET_CODE (x) == COND_EXEC)
+ x = COND_EXEC_CODE (x);
+
+ if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
+ {
+ rtx dest = SET_DEST (x);
+
+ while ((GET_CODE (dest) == SUBREG
+ && (!REG_P (SUBREG_REG (dest))
+ || REGNO (SUBREG_REG (dest)) >= FIRST_PSEUDO_REGISTER))
+ || GET_CODE (dest) == ZERO_EXTRACT
+ || GET_CODE (dest) == SIGN_EXTRACT
+ || GET_CODE (dest) == STRICT_LOW_PART)
+ dest = XEXP (dest, 0);
+
+ /* If we have a PARALLEL, SET_DEST is a list of EXPR_LIST expressions,
+ each of whose first operand is a register. */
+ if (GET_CODE (dest) == PARALLEL)
+ {
+ for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
+ if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
+ (*fun) (XEXP (XVECEXP (dest, 0, i), 0), x, data);
+ }
+ else
+ (*fun) (dest, x, data);
+ }
+
+ else if (GET_CODE (x) == PARALLEL)
+ for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
+ note_stores (XVECEXP (x, 0, i), fun, data);
+}
+\f
+/* Like notes_stores, but call FUN for each expression that is being
+ referenced in PBODY, a pointer to the PATTERN of an insn. We only call
+ FUN for each expression, not any interior subexpressions. FUN receives a
+ pointer to the expression and the DATA passed to this function.
+
+ Note that this is not quite the same test as that done in reg_referenced_p
+ since that considers something as being referenced if it is being
+ partially set, while we do not. */
+
+void
+note_uses (rtx *pbody, void (*fun) (rtx *, void *), void *data)
+{
+ rtx body = *pbody;
+ int i;
+
+ switch (GET_CODE (body))
+ {
+ case COND_EXEC:
+ (*fun) (&COND_EXEC_TEST (body), data);
+ note_uses (&COND_EXEC_CODE (body), fun, data);
+ return;
+
+ case PARALLEL:
+ for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
+ note_uses (&XVECEXP (body, 0, i), fun, data);
+ return;
+
+ case USE:
+ (*fun) (&XEXP (body, 0), data);
+ return;
+
+ case ASM_OPERANDS:
+ for (i = ASM_OPERANDS_INPUT_LENGTH (body) - 1; i >= 0; i--)
+ (*fun) (&ASM_OPERANDS_INPUT (body, i), data);
+ return;
+
+ case TRAP_IF:
+ (*fun) (&TRAP_CONDITION (body), data);
+ return;
+
+ case PREFETCH:
+ (*fun) (&XEXP (body, 0), data);
+ return;
+
+ case UNSPEC:
+ case UNSPEC_VOLATILE:
+ for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
+ (*fun) (&XVECEXP (body, 0, i), data);
+ return;
+
+ case CLOBBER:
+ if (MEM_P (XEXP (body, 0)))
+ (*fun) (&XEXP (XEXP (body, 0), 0), data);
+ return;
+
+ case SET:
+ {
+ rtx dest = SET_DEST (body);
+
+ /* For sets we replace everything in source plus registers in memory
+ expression in store and operands of a ZERO_EXTRACT. */
+ (*fun) (&SET_SRC (body), data);
+
+ if (GET_CODE (dest) == ZERO_EXTRACT)
+ {
+ (*fun) (&XEXP (dest, 1), data);
+ (*fun) (&XEXP (dest, 2), data);
+ }
+
+ while (GET_CODE (dest) == SUBREG || GET_CODE (dest) == STRICT_LOW_PART)
+ dest = XEXP (dest, 0);
+
+ if (MEM_P (dest))
+ (*fun) (&XEXP (dest, 0), data);
+ }
+ return;
+
+ default:
+ /* All the other possibilities never store. */
+ (*fun) (pbody, data);
+ return;
+ }
+}
+\f
+/* Return nonzero if X's old contents don't survive after INSN.
+ This will be true if X is (cc0) or if X is a register and
+ X dies in INSN or because INSN entirely sets X.
+
+ "Entirely set" means set directly and not through a SUBREG,
+ ZERO_EXTRACT or SIGN_EXTRACT, so no trace of the old contents remains.
+ Likewise, REG_INC does not count.
+
+ REG may be a hard or pseudo reg. Renumbering is not taken into account,
+ but for this use that makes no difference, since regs don't overlap
+ during their lifetimes. Therefore, this function may be used
+ at any time after deaths have been computed (in flow.c).
+
+ If REG is a hard reg that occupies multiple machine registers, this
+ function will only return 1 if each of those registers will be replaced
+ by INSN. */
+
+int
+dead_or_set_p (rtx insn, rtx x)
+{
+ unsigned int regno, last_regno;
+ unsigned int i;
+
+ /* Can't use cc0_rtx below since this file is used by genattrtab.c. */
+ if (GET_CODE (x) == CC0)
+ return 1;
+
+ gcc_assert (REG_P (x));
+
+ regno = REGNO (x);
+ last_regno = (regno >= FIRST_PSEUDO_REGISTER ? regno
+ : regno + hard_regno_nregs[regno][GET_MODE (x)] - 1);
+
+ for (i = regno; i <= last_regno; i++)
+ if (! dead_or_set_regno_p (insn, i))
+ return 0;
+
+ return 1;
+}
+
+/* Utility function for dead_or_set_p to check an individual register. Also
+ called from flow.c. */
+
+int
+dead_or_set_regno_p (rtx insn, unsigned int test_regno)
+{
+ unsigned int regno, endregno;
+ rtx pattern;
+
+ /* See if there is a death note for something that includes TEST_REGNO. */
+ if (find_regno_note (insn, REG_DEAD, test_regno))
+ return 1;
+
+ if (CALL_P (insn)
+ && find_regno_fusage (insn, CLOBBER, test_regno))
+ return 1;
+
+ pattern = PATTERN (insn);
+
+ if (GET_CODE (pattern) == COND_EXEC)
+ pattern = COND_EXEC_CODE (pattern);
+
+ if (GET_CODE (pattern) == SET)
+ {
+ rtx dest = SET_DEST (pattern);
+
+ /* A value is totally replaced if it is the destination or the
+ destination is a SUBREG of REGNO that does not change the number of
+ words in it. */
+ if (GET_CODE (dest) == SUBREG
+ && (((GET_MODE_SIZE (GET_MODE (dest))
+ + UNITS_PER_WORD - 1) / UNITS_PER_WORD)
+ == ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest)))
+ + UNITS_PER_WORD - 1) / UNITS_PER_WORD)))
+ dest = SUBREG_REG (dest);
+
+ if (!REG_P (dest))
+ return 0;
+
+ regno = REGNO (dest);
+ endregno = (regno >= FIRST_PSEUDO_REGISTER ? regno + 1
+ : regno + hard_regno_nregs[regno][GET_MODE (dest)]);
+
+ return (test_regno >= regno && test_regno < endregno);
+ }
+ else if (GET_CODE (pattern) == PARALLEL)
+ {
+ int i;
+
+ for (i = XVECLEN (pattern, 0) - 1; i >= 0; i--)
+ {
+ rtx body = XVECEXP (pattern, 0, i);
+
+ if (GET_CODE (body) == COND_EXEC)
+ body = COND_EXEC_CODE (body);
+
+ if (GET_CODE (body) == SET || GET_CODE (body) == CLOBBER)
+ {
+ rtx dest = SET_DEST (body);
+
+ if (GET_CODE (dest) == SUBREG
+ && (((GET_MODE_SIZE (GET_MODE (dest))
+ + UNITS_PER_WORD - 1) / UNITS_PER_WORD)
+ == ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest)))
+ + UNITS_PER_WORD - 1) / UNITS_PER_WORD)))
+ dest = SUBREG_REG (dest);
+
+ if (!REG_P (dest))
+ continue;
+
+ regno = REGNO (dest);
+ endregno = (regno >= FIRST_PSEUDO_REGISTER ? regno + 1
+ : regno + hard_regno_nregs[regno][GET_MODE (dest)]);
+
+ if (test_regno >= regno && test_regno < endregno)
+ return 1;
+ }
+ }
+ }
+
+ return 0;
+}
+
+/* Return the reg-note of kind KIND in insn INSN, if there is one.
+ If DATUM is nonzero, look for one whose datum is DATUM. */
+
+rtx
+find_reg_note (rtx insn, enum reg_note kind, rtx datum)
+{
+ rtx link;
+
+ /* Ignore anything that is not an INSN, JUMP_INSN or CALL_INSN. */
+ if (! INSN_P (insn))
+ return 0;
+ if (datum == 0)
+ {
+ for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
+ if (REG_NOTE_KIND (link) == kind)
+ return link;
+ return 0;
+ }
+
+ for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
+ if (REG_NOTE_KIND (link) == kind && datum == XEXP (link, 0))
+ return link;
+ return 0;
+}
+
+/* Return the reg-note of kind KIND in insn INSN which applies to register
+ number REGNO, if any. Return 0 if there is no such reg-note. Note that
+ the REGNO of this NOTE need not be REGNO if REGNO is a hard register;
+ it might be the case that the note overlaps REGNO. */
+
+rtx
+find_regno_note (rtx insn, enum reg_note kind, unsigned int regno)
+{
+ rtx link;
+
+ /* Ignore anything that is not an INSN, JUMP_INSN or CALL_INSN. */
+ if (! INSN_P (insn))
+ return 0;
+
+ for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
+ if (REG_NOTE_KIND (link) == kind
+ /* Verify that it is a register, so that scratch and MEM won't cause a
+ problem here. */
+ && REG_P (XEXP (link, 0))
+ && REGNO (XEXP (link, 0)) <= regno
+ && ((REGNO (XEXP (link, 0))
+ + (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
+ : hard_regno_nregs[REGNO (XEXP (link, 0))]
+ [GET_MODE (XEXP (link, 0))]))
+ > regno))
+ return link;
+ return 0;
+}
+
+/* Return a REG_EQUIV or REG_EQUAL note if insn has only a single set and
+ has such a note. */
+
+rtx
+find_reg_equal_equiv_note (rtx insn)
+{
+ rtx link;
+
+ if (!INSN_P (insn))
+ return 0;
+ for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
+ if (REG_NOTE_KIND (link) == REG_EQUAL
+ || REG_NOTE_KIND (link) == REG_EQUIV)
+ {
+ if (single_set (insn) == 0)
+ return 0;
+ return link;
+ }
+ return NULL;
+}
+
+/* Return true if DATUM, or any overlap of DATUM, of kind CODE is found
+ in the CALL_INSN_FUNCTION_USAGE information of INSN. */
+
+int
+find_reg_fusage (rtx insn, enum rtx_code code, rtx datum)
+{
+ /* If it's not a CALL_INSN, it can't possibly have a
+ CALL_INSN_FUNCTION_USAGE field, so don't bother checking. */
+ if (!CALL_P (insn))
+ return 0;
+
+ gcc_assert (datum);
+
+ if (!REG_P (datum))
+ {
+ rtx link;
for (link = CALL_INSN_FUNCTION_USAGE (insn);
- link;
+ link;
link = XEXP (link, 1))
- if (GET_CODE (XEXP (link, 0)) == code
- && rtx_equal_p (datum, SET_DEST (XEXP (link, 0))))
- return 1;
+ if (GET_CODE (XEXP (link, 0)) == code
+ && rtx_equal_p (datum, XEXP (XEXP (link, 0), 0)))
+ return 1;
+ }
+ else
+ {
+ unsigned int regno = REGNO (datum);
+
+ /* CALL_INSN_FUNCTION_USAGE information cannot contain references
+ to pseudo registers, so don't bother checking. */
+
+ if (regno < FIRST_PSEUDO_REGISTER)
+ {
+ unsigned int end_regno
+ = regno + hard_regno_nregs[regno][GET_MODE (datum)];
+ unsigned int i;
+
+ for (i = regno; i < end_regno; i++)
+ if (find_regno_fusage (insn, code, i))
+ return 1;
+ }
+ }
+
+ return 0;
+}
+
+/* Return true if REGNO, or any overlap of REGNO, of kind CODE is found
+ in the CALL_INSN_FUNCTION_USAGE information of INSN. */
+
+int
+find_regno_fusage (rtx insn, enum rtx_code code, unsigned int regno)
+{
+ rtx link;
+
+ /* CALL_INSN_FUNCTION_USAGE information cannot contain references
+ to pseudo registers, so don't bother checking. */
+
+ if (regno >= FIRST_PSEUDO_REGISTER
+ || !CALL_P (insn) )
+ return 0;
+
+ for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
+ {
+ unsigned int regnote;
+ rtx op, reg;
+
+ if (GET_CODE (op = XEXP (link, 0)) == code
+ && REG_P (reg = XEXP (op, 0))
+ && (regnote = REGNO (reg)) <= regno
+ && regnote + hard_regno_nregs[regnote][GET_MODE (reg)] > regno)
+ return 1;
+ }
+
+ return 0;
+}
+
+/* Return true if INSN is a call to a pure function. */
+
+int
+pure_call_p (rtx insn)
+{
+ rtx link;
+
+ if (!CALL_P (insn) || ! CONST_OR_PURE_CALL_P (insn))
+ return 0;
+
+ /* Look for the note that differentiates const and pure functions. */
+ for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
+ {
+ rtx u, m;
+
+ if (GET_CODE (u = XEXP (link, 0)) == USE
+ && MEM_P (m = XEXP (u, 0)) && GET_MODE (m) == BLKmode
+ && GET_CODE (XEXP (m, 0)) == SCRATCH)
+ return 1;
+ }
+
+ return 0;
+}
+\f
+/* Remove register note NOTE from the REG_NOTES of INSN. */
+
+void
+remove_note (rtx insn, rtx note)
+{
+ rtx link;
+
+ if (note == NULL_RTX)
+ return;
+
+ if (REG_NOTES (insn) == note)
+ {
+ REG_NOTES (insn) = XEXP (note, 1);
+ return;
+ }
+
+ for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
+ if (XEXP (link, 1) == note)
+ {
+ XEXP (link, 1) = XEXP (note, 1);
+ return;
+ }
+
+ gcc_unreachable ();
+}
+
+/* Search LISTP (an EXPR_LIST) for an entry whose first operand is NODE and
+ return 1 if it is found. A simple equality test is used to determine if
+ NODE matches. */
+
+int
+in_expr_list_p (rtx listp, rtx node)
+{
+ rtx x;
+
+ for (x = listp; x; x = XEXP (x, 1))
+ if (node == XEXP (x, 0))
+ return 1;
+
+ return 0;
+}
+
+/* Search LISTP (an EXPR_LIST) for an entry whose first operand is NODE and
+ remove that entry from the list if it is found.
+
+ A simple equality test is used to determine if NODE matches. */
+
+void
+remove_node_from_expr_list (rtx node, rtx *listp)
+{
+ rtx temp = *listp;
+ rtx prev = NULL_RTX;
+
+ while (temp)
+ {
+ if (node == XEXP (temp, 0))
+ {
+ /* Splice the node out of the list. */
+ if (prev)
+ XEXP (prev, 1) = XEXP (temp, 1);
+ else
+ *listp = XEXP (temp, 1);
+
+ return;
+ }
+
+ prev = temp;
+ temp = XEXP (temp, 1);
+ }
+}
+\f
+/* Nonzero if X contains any volatile instructions. These are instructions
+ which may cause unpredictable machine state instructions, and thus no
+ instructions should be moved or combined across them. This includes
+ only volatile asms and UNSPEC_VOLATILE instructions. */
+
+int
+volatile_insn_p (rtx x)
+{
+ RTX_CODE code;
+
+ code = GET_CODE (x);
+ switch (code)
+ {
+ case LABEL_REF:
+ case SYMBOL_REF:
+ case CONST_INT:
+ case CONST:
+ case CONST_DOUBLE:
+ case CONST_VECTOR:
+ case CC0:
+ case PC:
+ case REG:
+ case SCRATCH:
+ case CLOBBER:
+ case ADDR_VEC:
+ case ADDR_DIFF_VEC:
+ case CALL:
+ case MEM:
+ return 0;
+
+ case UNSPEC_VOLATILE:
+ /* case TRAP_IF: This isn't clear yet. */
+ return 1;
+
+ case ASM_INPUT:
+ case ASM_OPERANDS:
+ if (MEM_VOLATILE_P (x))
+ return 1;
+
+ default:
+ break;
+ }
+
+ /* Recursively scan the operands of this expression. */
+
+ {
+ const char *fmt = GET_RTX_FORMAT (code);
+ int i;
+
+ for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+ {
+ if (fmt[i] == 'e')
+ {
+ if (volatile_insn_p (XEXP (x, i)))
+ return 1;
+ }
+ else if (fmt[i] == 'E')
+ {
+ int j;
+ for (j = 0; j < XVECLEN (x, i); j++)
+ if (volatile_insn_p (XVECEXP (x, i, j)))
+ return 1;
+ }
+ }
+ }
+ return 0;
+}
+
+/* Nonzero if X contains any volatile memory references
+ UNSPEC_VOLATILE operations or volatile ASM_OPERANDS expressions. */
+
+int
+volatile_refs_p (rtx x)
+{
+ RTX_CODE code;
+
+ code = GET_CODE (x);
+ switch (code)
+ {
+ case LABEL_REF:
+ case SYMBOL_REF:
+ case CONST_INT:
+ case CONST:
+ case CONST_DOUBLE:
+ case CONST_VECTOR:
+ case CC0:
+ case PC:
+ case REG:
+ case SCRATCH:
+ case CLOBBER:
+ case ADDR_VEC:
+ case ADDR_DIFF_VEC:
+ return 0;
+
+ case UNSPEC_VOLATILE:
+ return 1;
+
+ case MEM:
+ case ASM_INPUT:
+ case ASM_OPERANDS:
+ if (MEM_VOLATILE_P (x))
+ return 1;
+
+ default:
+ break;
+ }
+
+ /* Recursively scan the operands of this expression. */
+
+ {
+ const char *fmt = GET_RTX_FORMAT (code);
+ int i;
+
+ for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+ {
+ if (fmt[i] == 'e')
+ {
+ if (volatile_refs_p (XEXP (x, i)))
+ return 1;
+ }
+ else if (fmt[i] == 'E')
+ {
+ int j;
+ for (j = 0; j < XVECLEN (x, i); j++)
+ if (volatile_refs_p (XVECEXP (x, i, j)))
+ return 1;
+ }
+ }
+ }
+ return 0;
+}
+
+/* Similar to above, except that it also rejects register pre- and post-
+ incrementing. */
+
+int
+side_effects_p (rtx x)
+{
+ RTX_CODE code;
+
+ code = GET_CODE (x);
+ switch (code)
+ {
+ case LABEL_REF:
+ case SYMBOL_REF:
+ case CONST_INT:
+ case CONST:
+ case CONST_DOUBLE:
+ case CONST_VECTOR:
+ case CC0:
+ case PC:
+ case REG:
+ case SCRATCH:
+ case ADDR_VEC:
+ case ADDR_DIFF_VEC:
+ return 0;
+
+ case CLOBBER:
+ /* Reject CLOBBER with a non-VOID mode. These are made by combine.c
+ when some combination can't be done. If we see one, don't think
+ that we can simplify the expression. */
+ return (GET_MODE (x) != VOIDmode);
+
+ case PRE_INC:
+ case PRE_DEC:
+ case POST_INC:
+ case POST_DEC:
+ case PRE_MODIFY:
+ case POST_MODIFY:
+ case CALL:
+ case UNSPEC_VOLATILE:
+ /* case TRAP_IF: This isn't clear yet. */
+ return 1;
+
+ case MEM:
+ case ASM_INPUT:
+ case ASM_OPERANDS:
+ if (MEM_VOLATILE_P (x))
+ return 1;
+
+ default:
+ break;
+ }
+
+ /* Recursively scan the operands of this expression. */
+
+ {
+ const char *fmt = GET_RTX_FORMAT (code);
+ int i;
+
+ for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+ {
+ if (fmt[i] == 'e')
+ {
+ if (side_effects_p (XEXP (x, i)))
+ return 1;
+ }
+ else if (fmt[i] == 'E')
+ {
+ int j;
+ for (j = 0; j < XVECLEN (x, i); j++)
+ if (side_effects_p (XVECEXP (x, i, j)))
+ return 1;
+ }
+ }
+ }
+ return 0;
+}
+\f
+/* Return nonzero if evaluating rtx X might cause a trap. */
+
+int
+may_trap_p (rtx x)
+{
+ int i;
+ enum rtx_code code;
+ const char *fmt;
+
+ if (x == 0)
+ return 0;
+ code = GET_CODE (x);
+ switch (code)
+ {
+ /* Handle these cases quickly. */
+ case CONST_INT:
+ case CONST_DOUBLE:
+ case CONST_VECTOR:
+ case SYMBOL_REF:
+ case LABEL_REF:
+ case CONST:
+ case PC:
+ case CC0:
+ case REG:
+ case SCRATCH:
+ return 0;
+
+ case ASM_INPUT:
+ case UNSPEC_VOLATILE:
+ case TRAP_IF:
+ return 1;
+
+ case ASM_OPERANDS:
+ return MEM_VOLATILE_P (x);
+
+ /* Memory ref can trap unless it's a static var or a stack slot. */
+ case MEM:
+ if (MEM_NOTRAP_P (x))
+ return 0;
+ return rtx_addr_can_trap_p (XEXP (x, 0));
+
+ /* Division by a non-constant might trap. */
+ case DIV:
+ case MOD:
+ case UDIV:
+ case UMOD:
+ if (HONOR_SNANS (GET_MODE (x)))
+ return 1;
+ if (! CONSTANT_P (XEXP (x, 1))
+ || (GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT
+ && flag_trapping_math))
+ return 1;
+ if (XEXP (x, 1) == const0_rtx)
+ return 1;
+ break;
+
+ case EXPR_LIST:
+ /* An EXPR_LIST is used to represent a function call. This
+ certainly may trap. */
+ return 1;
+
+ case GE:
+ case GT:
+ case LE:
+ case LT:
+ case LTGT:
+ case COMPARE:
+ /* Some floating point comparisons may trap. */
+ if (!flag_trapping_math)
+ break;
+ /* ??? There is no machine independent way to check for tests that trap
+ when COMPARE is used, though many targets do make this distinction.
+ For instance, sparc uses CCFPE for compares which generate exceptions
+ and CCFP for compares which do not generate exceptions. */
+ if (HONOR_NANS (GET_MODE (x)))
+ return 1;
+ /* But often the compare has some CC mode, so check operand
+ modes as well. */
+ if (HONOR_NANS (GET_MODE (XEXP (x, 0)))
+ || HONOR_NANS (GET_MODE (XEXP (x, 1))))
+ return 1;
+ break;
+
+ case EQ:
+ case NE:
+ if (HONOR_SNANS (GET_MODE (x)))
+ return 1;
+ /* Often comparison is CC mode, so check operand modes. */
+ if (HONOR_SNANS (GET_MODE (XEXP (x, 0)))
+ || HONOR_SNANS (GET_MODE (XEXP (x, 1))))
+ return 1;
+ break;
+
+ case FIX:
+ /* Conversion of floating point might trap. */
+ if (flag_trapping_math && HONOR_NANS (GET_MODE (XEXP (x, 0))))
+ return 1;
+ break;
+
+ case NEG:
+ case ABS:
+ /* These operations don't trap even with floating point. */
+ break;
+
+ default:
+ /* Any floating arithmetic may trap. */
+ if (GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT
+ && flag_trapping_math)
+ return 1;
+ }
+
+ fmt = GET_RTX_FORMAT (code);
+ for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+ {
+ if (fmt[i] == 'e')
+ {
+ if (may_trap_p (XEXP (x, i)))
+ return 1;
+ }
+ else if (fmt[i] == 'E')
+ {
+ int j;
+ for (j = 0; j < XVECLEN (x, i); j++)
+ if (may_trap_p (XVECEXP (x, i, j)))
+ return 1;
+ }
+ }
+ return 0;
+}
+\f
+/* Return nonzero if X contains a comparison that is not either EQ or NE,
+ i.e., an inequality. */
+
+int
+inequality_comparisons_p (rtx x)
+{
+ const char *fmt;
+ int len, i;
+ enum rtx_code code = GET_CODE (x);
+
+ switch (code)
+ {
+ case REG:
+ case SCRATCH:
+ case PC:
+ case CC0:
+ case CONST_INT:
+ case CONST_DOUBLE:
+ case CONST_VECTOR:
+ case CONST:
+ case LABEL_REF:
+ case SYMBOL_REF:
+ return 0;
+
+ case LT:
+ case LTU:
+ case GT:
+ case GTU:
+ case LE:
+ case LEU:
+ case GE:
+ case GEU:
+ return 1;
+
+ default:
+ break;
+ }
+
+ len = GET_RTX_LENGTH (code);
+ fmt = GET_RTX_FORMAT (code);
+
+ for (i = 0; i < len; i++)
+ {
+ if (fmt[i] == 'e')
+ {
+ if (inequality_comparisons_p (XEXP (x, i)))
+ return 1;
+ }
+ else if (fmt[i] == 'E')
+ {
+ int j;
+ for (j = XVECLEN (x, i) - 1; j >= 0; j--)
+ if (inequality_comparisons_p (XVECEXP (x, i, j)))
+ return 1;
+ }
+ }
+
+ return 0;
+}
+\f
+/* Replace any occurrence of FROM in X with TO. The function does
+ not enter into CONST_DOUBLE for the replace.
+
+ Note that copying is not done so X must not be shared unless all copies
+ are to be modified. */
+
+rtx
+replace_rtx (rtx x, rtx from, rtx to)
+{
+ int i, j;
+ const char *fmt;
+
+ /* The following prevents loops occurrence when we change MEM in
+ CONST_DOUBLE onto the same CONST_DOUBLE. */
+ if (x != 0 && GET_CODE (x) == CONST_DOUBLE)
+ return x;
+
+ if (x == from)
+ return to;
+
+ /* Allow this function to make replacements in EXPR_LISTs. */
+ if (x == 0)
+ return 0;
+
+ if (GET_CODE (x) == SUBREG)
+ {
+ rtx new = replace_rtx (SUBREG_REG (x), from, to);
+
+ if (GET_CODE (new) == CONST_INT)
+ {
+ x = simplify_subreg (GET_MODE (x), new,
+ GET_MODE (SUBREG_REG (x)),
+ SUBREG_BYTE (x));
+ gcc_assert (x);
+ }
+ else
+ SUBREG_REG (x) = new;
+
+ return x;
+ }
+ else if (GET_CODE (x) == ZERO_EXTEND)
+ {
+ rtx new = replace_rtx (XEXP (x, 0), from, to);
+
+ if (GET_CODE (new) == CONST_INT)
+ {
+ x = simplify_unary_operation (ZERO_EXTEND, GET_MODE (x),
+ new, GET_MODE (XEXP (x, 0)));
+ gcc_assert (x);
+ }
+ else
+ XEXP (x, 0) = new;
+
+ return x;
+ }
+
+ fmt = GET_RTX_FORMAT (GET_CODE (x));
+ for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
+ {
+ if (fmt[i] == 'e')
+ XEXP (x, i) = replace_rtx (XEXP (x, i), from, to);
+ else if (fmt[i] == 'E')
+ for (j = XVECLEN (x, i) - 1; j >= 0; j--)
+ XVECEXP (x, i, j) = replace_rtx (XVECEXP (x, i, j), from, to);
+ }
+
+ return x;
+}
+\f
+/* Throughout the rtx X, replace many registers according to REG_MAP.
+ Return the replacement for X (which may be X with altered contents).
+ REG_MAP[R] is the replacement for register R, or 0 for don't replace.
+ NREGS is the length of REG_MAP; regs >= NREGS are not mapped.
+
+ We only support REG_MAP entries of REG or SUBREG. Also, hard registers
+ should not be mapped to pseudos or vice versa since validate_change
+ is not called.
+
+ If REPLACE_DEST is 1, replacements are also done in destinations;
+ otherwise, only sources are replaced. */
+
+rtx
+replace_regs (rtx x, rtx *reg_map, unsigned int nregs, int replace_dest)
+{
+ enum rtx_code code;
+ int i;
+ const char *fmt;
+
+ if (x == 0)
+ return x;
+
+ code = GET_CODE (x);
+ switch (code)
+ {
+ case SCRATCH:
+ case PC:
+ case CC0:
+ case CONST_INT:
+ case CONST_DOUBLE:
+ case CONST_VECTOR:
+ case CONST:
+ case SYMBOL_REF:
+ case LABEL_REF:
+ return x;
+
+ case REG:
+ /* Verify that the register has an entry before trying to access it. */
+ if (REGNO (x) < nregs && reg_map[REGNO (x)] != 0)
+ {
+ /* SUBREGs can't be shared. Always return a copy to ensure that if
+ this replacement occurs more than once then each instance will
+ get distinct rtx. */
+ if (GET_CODE (reg_map[REGNO (x)]) == SUBREG)
+ return copy_rtx (reg_map[REGNO (x)]);
+ return reg_map[REGNO (x)];
+ }
+ return x;
+
+ case SUBREG:
+ /* Prevent making nested SUBREGs. */
+ if (REG_P (SUBREG_REG (x)) && REGNO (SUBREG_REG (x)) < nregs
+ && reg_map[REGNO (SUBREG_REG (x))] != 0
+ && GET_CODE (reg_map[REGNO (SUBREG_REG (x))]) == SUBREG)
+ {
+ rtx map_val = reg_map[REGNO (SUBREG_REG (x))];
+ return simplify_gen_subreg (GET_MODE (x), map_val,
+ GET_MODE (SUBREG_REG (x)),
+ SUBREG_BYTE (x));
+ }
+ break;
+
+ case SET:
+ if (replace_dest)
+ SET_DEST (x) = replace_regs (SET_DEST (x), reg_map, nregs, 0);
+
+ else if (MEM_P (SET_DEST (x))
+ || GET_CODE (SET_DEST (x)) == STRICT_LOW_PART)
+ /* Even if we are not to replace destinations, replace register if it
+ is CONTAINED in destination (destination is memory or
+ STRICT_LOW_PART). */
+ XEXP (SET_DEST (x), 0) = replace_regs (XEXP (SET_DEST (x), 0),
+ reg_map, nregs, 0);
+ else if (GET_CODE (SET_DEST (x)) == ZERO_EXTRACT)
+ /* Similarly, for ZERO_EXTRACT we replace all operands. */
+ break;
+
+ SET_SRC (x) = replace_regs (SET_SRC (x), reg_map, nregs, 0);
+ return x;
+
+ default:
+ break;
+ }
+
+ fmt = GET_RTX_FORMAT (code);
+ for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+ {
+ if (fmt[i] == 'e')
+ XEXP (x, i) = replace_regs (XEXP (x, i), reg_map, nregs, replace_dest);
+ else if (fmt[i] == 'E')
+ {
+ int j;
+ for (j = 0; j < XVECLEN (x, i); j++)
+ XVECEXP (x, i, j) = replace_regs (XVECEXP (x, i, j), reg_map,
+ nregs, replace_dest);
+ }
+ }
+ return x;
+}
+
+/* Replace occurrences of the old label in *X with the new one.
+ DATA is a REPLACE_LABEL_DATA containing the old and new labels. */
+
+int
+replace_label (rtx *x, void *data)
+{
+ rtx l = *x;
+ rtx old_label = ((replace_label_data *) data)->r1;
+ rtx new_label = ((replace_label_data *) data)->r2;
+ bool update_label_nuses = ((replace_label_data *) data)->update_label_nuses;
+
+ if (l == NULL_RTX)
+ return 0;
+
+ if (GET_CODE (l) == SYMBOL_REF
+ && CONSTANT_POOL_ADDRESS_P (l))
+ {
+ rtx c = get_pool_constant (l);
+ if (rtx_referenced_p (old_label, c))
+ {
+ rtx new_c, new_l;
+ replace_label_data *d = (replace_label_data *) data;
+
+ /* Create a copy of constant C; replace the label inside
+ but do not update LABEL_NUSES because uses in constant pool
+ are not counted. */
+ new_c = copy_rtx (c);
+ d->update_label_nuses = false;
+ for_each_rtx (&new_c, replace_label, data);
+ d->update_label_nuses = update_label_nuses;
+
+ /* Add the new constant NEW_C to constant pool and replace
+ the old reference to constant by new reference. */
+ new_l = XEXP (force_const_mem (get_pool_mode (l), new_c), 0);
+ *x = replace_rtx (l, l, new_l);
+ }
+ return 0;
}
- else
+
+ /* If this is a JUMP_INSN, then we also need to fix the JUMP_LABEL
+ field. This is not handled by for_each_rtx because it doesn't
+ handle unprinted ('0') fields. */
+ if (JUMP_P (l) && JUMP_LABEL (l) == old_label)
+ JUMP_LABEL (l) = new_label;
+
+ if ((GET_CODE (l) == LABEL_REF
+ || GET_CODE (l) == INSN_LIST)
+ && XEXP (l, 0) == old_label)
+ {
+ XEXP (l, 0) = new_label;
+ if (update_label_nuses)
+ {
+ ++LABEL_NUSES (new_label);
+ --LABEL_NUSES (old_label);
+ }
+ return 0;
+ }
+
+ return 0;
+}
+
+/* When *BODY is equal to X or X is directly referenced by *BODY
+ return nonzero, thus FOR_EACH_RTX stops traversing and returns nonzero
+ too, otherwise FOR_EACH_RTX continues traversing *BODY. */
+
+static int
+rtx_referenced_p_1 (rtx *body, void *x)
+{
+ rtx y = (rtx) x;
+
+ if (*body == NULL_RTX)
+ return y == NULL_RTX;
+
+ /* Return true if a label_ref *BODY refers to label Y. */
+ if (GET_CODE (*body) == LABEL_REF && LABEL_P (y))
+ return XEXP (*body, 0) == y;
+
+ /* If *BODY is a reference to pool constant traverse the constant. */
+ if (GET_CODE (*body) == SYMBOL_REF
+ && CONSTANT_POOL_ADDRESS_P (*body))
+ return rtx_referenced_p (y, get_pool_constant (*body));
+
+ /* By default, compare the RTL expressions. */
+ return rtx_equal_p (*body, y);
+}
+
+/* Return true if X is referenced in BODY. */
+
+int
+rtx_referenced_p (rtx x, rtx body)
+{
+ return for_each_rtx (&body, rtx_referenced_p_1, x);
+}
+
+/* If INSN is a tablejump return true and store the label (before jump table) to
+ *LABELP and the jump table to *TABLEP. LABELP and TABLEP may be NULL. */
+
+bool
+tablejump_p (rtx insn, rtx *labelp, rtx *tablep)
+{
+ rtx label, table;
+
+ if (JUMP_P (insn)
+ && (label = JUMP_LABEL (insn)) != NULL_RTX
+ && (table = next_active_insn (label)) != NULL_RTX
+ && JUMP_P (table)
+ && (GET_CODE (PATTERN (table)) == ADDR_VEC
+ || GET_CODE (PATTERN (table)) == ADDR_DIFF_VEC))
+ {
+ if (labelp)
+ *labelp = label;
+ if (tablep)
+ *tablep = table;
+ return true;
+ }
+ return false;
+}
+
+/* A subroutine of computed_jump_p, return 1 if X contains a REG or MEM or
+ constant that is not in the constant pool and not in the condition
+ of an IF_THEN_ELSE. */
+
+static int
+computed_jump_p_1 (rtx x)
+{
+ enum rtx_code code = GET_CODE (x);
+ int i, j;
+ const char *fmt;
+
+ switch (code)
+ {
+ case LABEL_REF:
+ case PC:
+ return 0;
+
+ case CONST:
+ case CONST_INT:
+ case CONST_DOUBLE:
+ case CONST_VECTOR:
+ case SYMBOL_REF:
+ case REG:
+ return 1;
+
+ case MEM:
+ return ! (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
+ && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)));
+
+ case IF_THEN_ELSE:
+ return (computed_jump_p_1 (XEXP (x, 1))
+ || computed_jump_p_1 (XEXP (x, 2)));
+
+ default:
+ break;
+ }
+
+ fmt = GET_RTX_FORMAT (code);
+ for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+ {
+ if (fmt[i] == 'e'
+ && computed_jump_p_1 (XEXP (x, i)))
+ return 1;
+
+ else if (fmt[i] == 'E')
+ for (j = 0; j < XVECLEN (x, i); j++)
+ if (computed_jump_p_1 (XVECEXP (x, i, j)))
+ return 1;
+ }
+
+ return 0;
+}
+
+/* Return nonzero if INSN is an indirect jump (aka computed jump).
+
+ Tablejumps and casesi insns are not considered indirect jumps;
+ we can recognize them by a (use (label_ref)). */
+
+int
+computed_jump_p (rtx insn)
+{
+ int i;
+ if (JUMP_P (insn))
+ {
+ rtx pat = PATTERN (insn);
+
+ if (find_reg_note (insn, REG_LABEL, NULL_RTX))
+ return 0;
+ else if (GET_CODE (pat) == PARALLEL)
+ {
+ int len = XVECLEN (pat, 0);
+ int has_use_labelref = 0;
+
+ for (i = len - 1; i >= 0; i--)
+ if (GET_CODE (XVECEXP (pat, 0, i)) == USE
+ && (GET_CODE (XEXP (XVECEXP (pat, 0, i), 0))
+ == LABEL_REF))
+ has_use_labelref = 1;
+
+ if (! has_use_labelref)
+ for (i = len - 1; i >= 0; i--)
+ if (GET_CODE (XVECEXP (pat, 0, i)) == SET
+ && SET_DEST (XVECEXP (pat, 0, i)) == pc_rtx
+ && computed_jump_p_1 (SET_SRC (XVECEXP (pat, 0, i))))
+ return 1;
+ }
+ else if (GET_CODE (pat) == SET
+ && SET_DEST (pat) == pc_rtx
+ && computed_jump_p_1 (SET_SRC (pat)))
+ return 1;
+ }
+ return 0;
+}
+
+/* Traverse X via depth-first search, calling F for each
+ sub-expression (including X itself). F is also passed the DATA.
+ If F returns -1, do not traverse sub-expressions, but continue
+ traversing the rest of the tree. If F ever returns any other
+ nonzero value, stop the traversal, and return the value returned
+ by F. Otherwise, return 0. This function does not traverse inside
+ tree structure that contains RTX_EXPRs, or into sub-expressions
+ whose format code is `0' since it is not known whether or not those
+ codes are actually RTL.
+
+ This routine is very general, and could (should?) be used to
+ implement many of the other routines in this file. */
+
+int
+for_each_rtx (rtx *x, rtx_function f, void *data)
+{
+ int result;
+ int length;
+ const char *format;
+ int i;
+
+ /* Call F on X. */
+ result = (*f) (x, data);
+ if (result == -1)
+ /* Do not traverse sub-expressions. */
+ return 0;
+ else if (result != 0)
+ /* Stop the traversal. */
+ return result;
+
+ if (*x == NULL_RTX)
+ /* There are no sub-expressions. */
+ return 0;
+
+ length = GET_RTX_LENGTH (GET_CODE (*x));
+ format = GET_RTX_FORMAT (GET_CODE (*x));
+
+ for (i = 0; i < length; ++i)
+ {
+ switch (format[i])
+ {
+ case 'e':
+ result = for_each_rtx (&XEXP (*x, i), f, data);
+ if (result != 0)
+ return result;
+ break;
+
+ case 'V':
+ case 'E':
+ if (XVEC (*x, i) != 0)
+ {
+ int j;
+ for (j = 0; j < XVECLEN (*x, i); ++j)
+ {
+ result = for_each_rtx (&XVECEXP (*x, i, j), f, data);
+ if (result != 0)
+ return result;
+ }
+ }
+ break;
+
+ default:
+ /* Nothing to do. */
+ break;
+ }
+
+ }
+
+ return 0;
+}
+
+/* Searches X for any reference to REGNO, returning the rtx of the
+ reference found if any. Otherwise, returns NULL_RTX. */
+
+rtx
+regno_use_in (unsigned int regno, rtx x)
+{
+ const char *fmt;
+ int i, j;
+ rtx tem;
+
+ if (REG_P (x) && REGNO (x) == regno)
+ return x;
+
+ fmt = GET_RTX_FORMAT (GET_CODE (x));
+ for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
+ {
+ if (fmt[i] == 'e')
+ {
+ if ((tem = regno_use_in (regno, XEXP (x, i))))
+ return tem;
+ }
+ else if (fmt[i] == 'E')
+ for (j = XVECLEN (x, i) - 1; j >= 0; j--)
+ if ((tem = regno_use_in (regno , XVECEXP (x, i, j))))
+ return tem;
+ }
+
+ return NULL_RTX;
+}
+
+/* Return a value indicating whether OP, an operand of a commutative
+ operation, is preferred as the first or second operand. The higher
+ the value, the stronger the preference for being the first operand.
+ We use negative values to indicate a preference for the first operand
+ and positive values for the second operand. */
+
+int
+commutative_operand_precedence (rtx op)
+{
+ enum rtx_code code = GET_CODE (op);
+
+ /* Constants always come the second operand. Prefer "nice" constants. */
+ if (code == CONST_INT)
+ return -7;
+ if (code == CONST_DOUBLE)
+ return -6;
+ op = avoid_constant_pool_reference (op);
+ code = GET_CODE (op);
+
+ switch (GET_RTX_CLASS (code))
+ {
+ case RTX_CONST_OBJ:
+ if (code == CONST_INT)
+ return -5;
+ if (code == CONST_DOUBLE)
+ return -4;
+ return -3;
+
+ case RTX_EXTRA:
+ /* SUBREGs of objects should come second. */
+ if (code == SUBREG && OBJECT_P (SUBREG_REG (op)))
+ return -2;
+
+ if (!CONSTANT_P (op))
+ return 0;
+ else
+ /* As for RTX_CONST_OBJ. */
+ return -3;
+
+ case RTX_OBJ:
+ /* Complex expressions should be the first, so decrease priority
+ of objects. */
+ return -1;
+
+ case RTX_COMM_ARITH:
+ /* Prefer operands that are themselves commutative to be first.
+ This helps to make things linear. In particular,
+ (and (and (reg) (reg)) (not (reg))) is canonical. */
+ return 4;
+
+ case RTX_BIN_ARITH:
+ /* If only one operand is a binary expression, it will be the first
+ operand. In particular, (plus (minus (reg) (reg)) (neg (reg)))
+ is canonical, although it will usually be further simplified. */
+ return 2;
+
+ case RTX_UNARY:
+ /* Then prefer NEG and NOT. */
+ if (code == NEG || code == NOT)
+ return 1;
+
+ default:
+ return 0;
+ }
+}
+
+/* Return 1 iff it is necessary to swap operands of commutative operation
+ in order to canonicalize expression. */
+
+int
+swap_commutative_operands_p (rtx x, rtx y)
+{
+ return (commutative_operand_precedence (x)
+ < commutative_operand_precedence (y));
+}
+
+/* Return 1 if X is an autoincrement side effect and the register is
+ not the stack pointer. */
+int
+auto_inc_p (rtx x)
+{
+ switch (GET_CODE (x))
{
- register int regno = REGNO (datum);
+ case PRE_INC:
+ case POST_INC:
+ case PRE_DEC:
+ case POST_DEC:
+ case PRE_MODIFY:
+ case POST_MODIFY:
+ /* There are no REG_INC notes for SP. */
+ if (XEXP (x, 0) != stack_pointer_rtx)
+ return 1;
+ default:
+ break;
+ }
+ return 0;
+}
+
+/* Return 1 if the sequence of instructions beginning with FROM and up
+ to and including TO is safe to move. If NEW_TO is non-NULL, and
+ the sequence is not already safe to move, but can be easily
+ extended to a sequence which is safe, then NEW_TO will point to the
+ end of the extended sequence.
+
+ For now, this function only checks that the region contains whole
+ exception regions, but it could be extended to check additional
+ conditions as well. */
+
+int
+insns_safe_to_move_p (rtx from, rtx to, rtx *new_to)
+{
+ int eh_region_count = 0;
+ int past_to_p = 0;
+ rtx r = from;
+
+ /* By default, assume the end of the region will be what was
+ suggested. */
+ if (new_to)
+ *new_to = to;
+
+ while (r)
+ {
+ if (NOTE_P (r))
+ {
+ switch (NOTE_LINE_NUMBER (r))
+ {
+ case NOTE_INSN_EH_REGION_BEG:
+ ++eh_region_count;
+ break;
+
+ case NOTE_INSN_EH_REGION_END:
+ if (eh_region_count == 0)
+ /* This sequence of instructions contains the end of
+ an exception region, but not he beginning. Moving
+ it will cause chaos. */
+ return 0;
+
+ --eh_region_count;
+ break;
+
+ default:
+ break;
+ }
+ }
+ else if (past_to_p)
+ /* If we've passed TO, and we see a non-note instruction, we
+ can't extend the sequence to a movable sequence. */
+ return 0;
+
+ if (r == to)
+ {
+ if (!new_to)
+ /* It's OK to move the sequence if there were matched sets of
+ exception region notes. */
+ return eh_region_count == 0;
+
+ past_to_p = 1;
+ }
+
+ /* It's OK to move the sequence if there were matched sets of
+ exception region notes. */
+ if (past_to_p && eh_region_count == 0)
+ {
+ *new_to = r;
+ return 1;
+ }
+
+ /* Go to the next instruction. */
+ r = NEXT_INSN (r);
+ }
- /* CALL_INSN_FUNCTION_USAGE information cannot contain references
- to pseudo registers, so don't bother checking. */
+ return 0;
+}
- if (regno < FIRST_PSEUDO_REGISTER)
- {
- int end_regno = regno + HARD_REGNO_NREGS (regno, GET_MODE (datum));
- int i;
+/* Return nonzero if IN contains a piece of rtl that has the address LOC. */
+int
+loc_mentioned_in_p (rtx *loc, rtx in)
+{
+ enum rtx_code code = GET_CODE (in);
+ const char *fmt = GET_RTX_FORMAT (code);
+ int i, j;
- for (i = regno; i < end_regno; i++)
- if (find_regno_fusage (insn, code, i))
- return 1;
- }
+ for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+ {
+ if (loc == &in->u.fld[i].rt_rtx)
+ return 1;
+ if (fmt[i] == 'e')
+ {
+ if (loc_mentioned_in_p (loc, XEXP (in, i)))
+ return 1;
+ }
+ else if (fmt[i] == 'E')
+ for (j = XVECLEN (in, i) - 1; j >= 0; j--)
+ if (loc_mentioned_in_p (loc, XVECEXP (in, i, j)))
+ return 1;
}
-
return 0;
}
-/* Return true if REGNO, or any overlap of REGNO, of kind CODE is found
- in the CALL_INSN_FUNCTION_USAGE information of INSN. */
+/* Helper function for subreg_lsb. Given a subreg's OUTER_MODE, INNER_MODE,
+ and SUBREG_BYTE, return the bit offset where the subreg begins
+ (counting from the least significant bit of the operand). */
-int
-find_regno_fusage (insn, code, regno)
- rtx insn;
- enum rtx_code code;
- int regno;
+unsigned int
+subreg_lsb_1 (enum machine_mode outer_mode,
+ enum machine_mode inner_mode,
+ unsigned int subreg_byte)
{
- register rtx link;
+ unsigned int bitpos;
+ unsigned int byte;
+ unsigned int word;
- /* CALL_INSN_FUNCTION_USAGE information cannot contain references
- to pseudo registers, so don't bother checking. */
+ /* A paradoxical subreg begins at bit position 0. */
+ if (GET_MODE_BITSIZE (outer_mode) > GET_MODE_BITSIZE (inner_mode))
+ return 0;
- if (regno >= FIRST_PSEUDO_REGISTER
- || GET_CODE (insn) != CALL_INSN )
+ if (WORDS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
+ /* If the subreg crosses a word boundary ensure that
+ it also begins and ends on a word boundary. */
+ gcc_assert (!((subreg_byte % UNITS_PER_WORD
+ + GET_MODE_SIZE (outer_mode)) > UNITS_PER_WORD
+ && (subreg_byte % UNITS_PER_WORD
+ || GET_MODE_SIZE (outer_mode) % UNITS_PER_WORD)));
+
+ if (WORDS_BIG_ENDIAN)
+ word = (GET_MODE_SIZE (inner_mode)
+ - (subreg_byte + GET_MODE_SIZE (outer_mode))) / UNITS_PER_WORD;
+ else
+ word = subreg_byte / UNITS_PER_WORD;
+ bitpos = word * BITS_PER_WORD;
+
+ if (BYTES_BIG_ENDIAN)
+ byte = (GET_MODE_SIZE (inner_mode)
+ - (subreg_byte + GET_MODE_SIZE (outer_mode))) % UNITS_PER_WORD;
+ else
+ byte = subreg_byte % UNITS_PER_WORD;
+ bitpos += byte * BITS_PER_UNIT;
+
+ return bitpos;
+}
+
+/* Given a subreg X, return the bit offset where the subreg begins
+ (counting from the least significant bit of the reg). */
+
+unsigned int
+subreg_lsb (rtx x)
+{
+ return subreg_lsb_1 (GET_MODE (x), GET_MODE (SUBREG_REG (x)),
+ SUBREG_BYTE (x));
+}
+
+/* This function returns the regno offset of a subreg expression.
+ xregno - A regno of an inner hard subreg_reg (or what will become one).
+ xmode - The mode of xregno.
+ offset - The byte offset.
+ ymode - The mode of a top level SUBREG (or what may become one).
+ RETURN - The regno offset which would be used. */
+unsigned int
+subreg_regno_offset (unsigned int xregno, enum machine_mode xmode,
+ unsigned int offset, enum machine_mode ymode)
+{
+ int nregs_xmode, nregs_ymode;
+ int mode_multiple, nregs_multiple;
+ int y_offset;
+
+ gcc_assert (xregno < FIRST_PSEUDO_REGISTER);
+
+ nregs_xmode = hard_regno_nregs[xregno][xmode];
+ nregs_ymode = hard_regno_nregs[xregno][ymode];
+
+ /* If this is a big endian paradoxical subreg, which uses more actual
+ hard registers than the original register, we must return a negative
+ offset so that we find the proper highpart of the register. */
+ if (offset == 0
+ && nregs_ymode > nregs_xmode
+ && (GET_MODE_SIZE (ymode) > UNITS_PER_WORD
+ ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN))
+ return nregs_xmode - nregs_ymode;
+
+ if (offset == 0 || nregs_xmode == nregs_ymode)
return 0;
- for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
- {
- register int regnote;
- register rtx op;
-
- if (GET_CODE (op = XEXP (link, 0)) == code
- && GET_CODE (SET_DEST (op)) == REG
- && (regnote = REGNO (SET_DEST (op))) <= regno
- && regnote
- + HARD_REGNO_NREGS (regnote, GET_MODE (SET_DEST (op)))
- > regno)
- return 1;
- }
+ /* size of ymode must not be greater than the size of xmode. */
+ mode_multiple = GET_MODE_SIZE (xmode) / GET_MODE_SIZE (ymode);
+ gcc_assert (mode_multiple != 0);
- return 0;
+ y_offset = offset / GET_MODE_SIZE (ymode);
+ nregs_multiple = nregs_xmode / nregs_ymode;
+ return (y_offset / (mode_multiple / nregs_multiple)) * nregs_ymode;
}
-\f
-/* Remove register note NOTE from the REG_NOTES of INSN. */
-void
-remove_note (insn, note)
- register rtx note;
- register rtx insn;
+/* This function returns true when the offset is representable via
+ subreg_offset in the given regno.
+ xregno - A regno of an inner hard subreg_reg (or what will become one).
+ xmode - The mode of xregno.
+ offset - The byte offset.
+ ymode - The mode of a top level SUBREG (or what may become one).
+ RETURN - The regno offset which would be used. */
+bool
+subreg_offset_representable_p (unsigned int xregno, enum machine_mode xmode,
+ unsigned int offset, enum machine_mode ymode)
{
- register rtx link;
+ int nregs_xmode, nregs_ymode;
+ int mode_multiple, nregs_multiple;
+ int y_offset;
+
+ gcc_assert (xregno < FIRST_PSEUDO_REGISTER);
+
+ nregs_xmode = hard_regno_nregs[xregno][xmode];
+ nregs_ymode = hard_regno_nregs[xregno][ymode];
+
+ /* Paradoxical subregs are always valid. */
+ if (offset == 0
+ && nregs_ymode > nregs_xmode
+ && (GET_MODE_SIZE (ymode) > UNITS_PER_WORD
+ ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN))
+ return true;
+
+ /* Lowpart subregs are always valid. */
+ if (offset == subreg_lowpart_offset (ymode, xmode))
+ return true;
+
+ /* This should always pass, otherwise we don't know how to verify the
+ constraint. These conditions may be relaxed but subreg_offset would
+ need to be redesigned. */
+ gcc_assert ((GET_MODE_SIZE (xmode) % GET_MODE_SIZE (ymode)) == 0);
+ gcc_assert ((GET_MODE_SIZE (ymode) % nregs_ymode) == 0);
+ gcc_assert ((nregs_xmode % nregs_ymode) == 0);
+
+ /* The XMODE value can be seen as a vector of NREGS_XMODE
+ values. The subreg must represent a lowpart of given field.
+ Compute what field it is. */
+ offset -= subreg_lowpart_offset (ymode,
+ mode_for_size (GET_MODE_BITSIZE (xmode)
+ / nregs_xmode,
+ MODE_INT, 0));
+
+ /* size of ymode must not be greater than the size of xmode. */
+ mode_multiple = GET_MODE_SIZE (xmode) / GET_MODE_SIZE (ymode);
+ gcc_assert (mode_multiple != 0);
+
+ y_offset = offset / GET_MODE_SIZE (ymode);
+ nregs_multiple = nregs_xmode / nregs_ymode;
+
+ gcc_assert ((offset % GET_MODE_SIZE (ymode)) == 0);
+ gcc_assert ((mode_multiple % nregs_multiple) == 0);
+
+ return (!(y_offset % (mode_multiple / nregs_multiple)));
+}
- if (REG_NOTES (insn) == note)
+/* Return the final regno that a subreg expression refers to. */
+unsigned int
+subreg_regno (rtx x)
+{
+ unsigned int ret;
+ rtx subreg = SUBREG_REG (x);
+ int regno = REGNO (subreg);
+
+ ret = regno + subreg_regno_offset (regno,
+ GET_MODE (subreg),
+ SUBREG_BYTE (x),
+ GET_MODE (x));
+ return ret;
+
+}
+struct parms_set_data
+{
+ int nregs;
+ HARD_REG_SET regs;
+};
+
+/* Helper function for noticing stores to parameter registers. */
+static void
+parms_set (rtx x, rtx pat ATTRIBUTE_UNUSED, void *data)
+{
+ struct parms_set_data *d = data;
+ if (REG_P (x) && REGNO (x) < FIRST_PSEUDO_REGISTER
+ && TEST_HARD_REG_BIT (d->regs, REGNO (x)))
{
- REG_NOTES (insn) = XEXP (note, 1);
- return;
+ CLEAR_HARD_REG_BIT (d->regs, REGNO (x));
+ d->nregs--;
}
+}
- for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
- if (XEXP (link, 1) == note)
+/* Look backward for first parameter to be loaded.
+ Do not skip BOUNDARY. */
+rtx
+find_first_parameter_load (rtx call_insn, rtx boundary)
+{
+ struct parms_set_data parm;
+ rtx p, before;
+
+ /* Since different machines initialize their parameter registers
+ in different orders, assume nothing. Collect the set of all
+ parameter registers. */
+ CLEAR_HARD_REG_SET (parm.regs);
+ parm.nregs = 0;
+ for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
+ if (GET_CODE (XEXP (p, 0)) == USE
+ && REG_P (XEXP (XEXP (p, 0), 0)))
{
- XEXP (link, 1) = XEXP (note, 1);
- return;
+ gcc_assert (REGNO (XEXP (XEXP (p, 0), 0)) < FIRST_PSEUDO_REGISTER);
+
+ /* We only care about registers which can hold function
+ arguments. */
+ if (!FUNCTION_ARG_REGNO_P (REGNO (XEXP (XEXP (p, 0), 0))))
+ continue;
+
+ SET_HARD_REG_BIT (parm.regs, REGNO (XEXP (XEXP (p, 0), 0)));
+ parm.nregs++;
}
+ before = call_insn;
+
+ /* Search backward for the first set of a register in this set. */
+ while (parm.nregs && before != boundary)
+ {
+ before = PREV_INSN (before);
+
+ /* It is possible that some loads got CSEed from one call to
+ another. Stop in that case. */
+ if (CALL_P (before))
+ break;
+
+ /* Our caller needs either ensure that we will find all sets
+ (in case code has not been optimized yet), or take care
+ for possible labels in a way by setting boundary to preceding
+ CODE_LABEL. */
+ if (LABEL_P (before))
+ {
+ gcc_assert (before == boundary);
+ break;
+ }
- abort ();
+ if (INSN_P (before))
+ note_stores (PATTERN (before), parms_set, &parm);
+ }
+ return before;
}
-\f
-/* Nonzero if X contains any volatile instructions. These are instructions
- which may cause unpredictable machine state instructions, and thus no
- instructions should be moved or combined across them. This includes
- only volatile asms and UNSPEC_VOLATILE instructions. */
-int
-volatile_insn_p (x)
- rtx x;
+/* Return true if we should avoid inserting code between INSN and preceding
+ call instruction. */
+
+bool
+keep_with_call_p (rtx insn)
{
- register RTX_CODE code;
+ rtx set;
- code = GET_CODE (x);
- switch (code)
+ if (INSN_P (insn) && (set = single_set (insn)) != NULL)
{
- case LABEL_REF:
- case SYMBOL_REF:
- case CONST_INT:
- case CONST:
- case CONST_DOUBLE:
- case CC0:
- case PC:
- case REG:
- case SCRATCH:
- case CLOBBER:
- case ASM_INPUT:
- case ADDR_VEC:
- case ADDR_DIFF_VEC:
- case CALL:
- case MEM:
- return 0;
+ if (REG_P (SET_DEST (set))
+ && REGNO (SET_DEST (set)) < FIRST_PSEUDO_REGISTER
+ && fixed_regs[REGNO (SET_DEST (set))]
+ && general_operand (SET_SRC (set), VOIDmode))
+ return true;
+ if (REG_P (SET_SRC (set))
+ && FUNCTION_VALUE_REGNO_P (REGNO (SET_SRC (set)))
+ && REG_P (SET_DEST (set))
+ && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
+ return true;
+ /* There may be a stack pop just after the call and before the store
+ of the return register. Search for the actual store when deciding
+ if we can break or not. */
+ if (SET_DEST (set) == stack_pointer_rtx)
+ {
+ rtx i2 = next_nonnote_insn (insn);
+ if (i2 && keep_with_call_p (i2))
+ return true;
+ }
+ }
+ return false;
+}
- case UNSPEC_VOLATILE:
- /* case TRAP_IF: This isn't clear yet. */
- return 1;
+/* Return true when store to register X can be hoisted to the place
+ with LIVE registers (can be NULL). Value VAL contains destination
+ whose value will be used. */
- case ASM_OPERANDS:
- if (MEM_VOLATILE_P (x))
- return 1;
+static bool
+hoist_test_store (rtx x, rtx val, regset live)
+{
+ if (GET_CODE (x) == SCRATCH)
+ return true;
- default:
- break;
+ if (rtx_equal_p (x, val))
+ return true;
+
+ /* Allow subreg of X in case it is not writing just part of multireg pseudo.
+ Then we would need to update all users to care hoisting the store too.
+ Caller may represent that by specifying whole subreg as val. */
+
+ if (GET_CODE (x) == SUBREG && rtx_equal_p (SUBREG_REG (x), val))
+ {
+ if (GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))) > UNITS_PER_WORD
+ && GET_MODE_BITSIZE (GET_MODE (x)) <
+ GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))))
+ return false;
+ return true;
}
+ if (GET_CODE (x) == SUBREG)
+ x = SUBREG_REG (x);
- /* Recursively scan the operands of this expression. */
+ /* Anything except register store is not hoistable. This includes the
+ partial stores to registers. */
- {
- register char *fmt = GET_RTX_FORMAT (code);
- register int i;
-
- for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
- {
- if (fmt[i] == 'e')
- {
- if (volatile_insn_p (XEXP (x, i)))
- return 1;
- }
- if (fmt[i] == 'E')
- {
- register int j;
- for (j = 0; j < XVECLEN (x, i); j++)
- if (volatile_insn_p (XVECEXP (x, i, j)))
- return 1;
- }
- }
- }
- return 0;
+ if (!REG_P (x))
+ return false;
+
+ /* Pseudo registers can be always replaced by another pseudo to avoid
+ the side effect, for hard register we must ensure that they are dead.
+ Eventually we may want to add code to try turn pseudos to hards, but it
+ is unlikely useful. */
+
+ if (REGNO (x) < FIRST_PSEUDO_REGISTER)
+ {
+ int regno = REGNO (x);
+ int n = hard_regno_nregs[regno][GET_MODE (x)];
+
+ if (!live)
+ return false;
+ if (REGNO_REG_SET_P (live, regno))
+ return false;
+ while (--n > 0)
+ if (REGNO_REG_SET_P (live, regno + n))
+ return false;
+ }
+ return true;
}
-/* Nonzero if X contains any volatile memory references
- UNSPEC_VOLATILE operations or volatile ASM_OPERANDS expressions. */
-int
-volatile_refs_p (x)
- rtx x;
+/* Return true if INSN can be hoisted to place with LIVE hard registers
+ (LIVE can be NULL when unknown). VAL is expected to be stored by the insn
+ and used by the hoisting pass. */
+
+bool
+can_hoist_insn_p (rtx insn, rtx val, regset live)
{
- register RTX_CODE code;
+ rtx pat = PATTERN (insn);
+ int i;
- code = GET_CODE (x);
- switch (code)
+ /* It probably does not worth the complexity to handle multiple
+ set stores. */
+ if (!single_set (insn))
+ return false;
+ /* We can move CALL_INSN, but we need to check that all caller clobbered
+ regs are dead. */
+ if (CALL_P (insn))
+ return false;
+ /* In future we will handle hoisting of libcall sequences, but
+ give up for now. */
+ if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
+ return false;
+ switch (GET_CODE (pat))
{
- case LABEL_REF:
- case SYMBOL_REF:
- case CONST_INT:
- case CONST:
- case CONST_DOUBLE:
- case CC0:
- case PC:
- case REG:
- case SCRATCH:
+ case SET:
+ if (!hoist_test_store (SET_DEST (pat), val, live))
+ return false;
+ break;
+ case USE:
+ /* USES do have sick semantics, so do not move them. */
+ return false;
+ break;
case CLOBBER:
- case ASM_INPUT:
- case ADDR_VEC:
- case ADDR_DIFF_VEC:
- return 0;
+ if (!hoist_test_store (XEXP (pat, 0), val, live))
+ return false;
+ break;
+ case PARALLEL:
+ for (i = 0; i < XVECLEN (pat, 0); i++)
+ {
+ rtx x = XVECEXP (pat, 0, i);
+ switch (GET_CODE (x))
+ {
+ case SET:
+ if (!hoist_test_store (SET_DEST (x), val, live))
+ return false;
+ break;
+ case USE:
+ /* We need to fix callers to really ensure availability
+ of all values insn uses, but for now it is safe to prohibit
+ hoisting of any insn having such a hidden uses. */
+ return false;
+ break;
+ case CLOBBER:
+ if (!hoist_test_store (SET_DEST (x), val, live))
+ return false;
+ break;
+ default:
+ break;
+ }
+ }
+ break;
+ default:
+ gcc_unreachable ();
+ }
+ return true;
+}
- case CALL:
- case UNSPEC_VOLATILE:
- /* case TRAP_IF: This isn't clear yet. */
- return 1;
+/* Update store after hoisting - replace all stores to pseudo registers
+ by new ones to avoid clobbering of values except for store to VAL that will
+ be updated to NEW. */
- case MEM:
- case ASM_OPERANDS:
- if (MEM_VOLATILE_P (x))
- return 1;
+static void
+hoist_update_store (rtx insn, rtx *xp, rtx val, rtx new)
+{
+ rtx x = *xp;
- default:
- break;
+ if (GET_CODE (x) == SCRATCH)
+ return;
+
+ if (GET_CODE (x) == SUBREG && SUBREG_REG (x) == val)
+ validate_change (insn, xp,
+ simplify_gen_subreg (GET_MODE (x), new, GET_MODE (new),
+ SUBREG_BYTE (x)), 1);
+ if (rtx_equal_p (x, val))
+ {
+ validate_change (insn, xp, new, 1);
+ return;
+ }
+ if (GET_CODE (x) == SUBREG)
+ {
+ xp = &SUBREG_REG (x);
+ x = *xp;
}
- /* Recursively scan the operands of this expression. */
+ gcc_assert (REG_P (x));
- {
- register char *fmt = GET_RTX_FORMAT (code);
- register int i;
-
- for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
- {
- if (fmt[i] == 'e')
- {
- if (volatile_refs_p (XEXP (x, i)))
- return 1;
- }
- if (fmt[i] == 'E')
- {
- register int j;
- for (j = 0; j < XVECLEN (x, i); j++)
- if (volatile_refs_p (XVECEXP (x, i, j)))
- return 1;
- }
- }
- }
- return 0;
+ /* We've verified that hard registers are dead, so we may keep the side
+ effect. Otherwise replace it by new pseudo. */
+ if (REGNO (x) >= FIRST_PSEUDO_REGISTER)
+ validate_change (insn, xp, gen_reg_rtx (GET_MODE (x)), 1);
+ REG_NOTES (insn)
+ = alloc_EXPR_LIST (REG_UNUSED, *xp, REG_NOTES (insn));
}
-/* Similar to above, except that it also rejects register pre- and post-
- incrementing. */
+/* Create a copy of INSN after AFTER replacing store of VAL to NEW
+ and each other side effect to pseudo register by new pseudo register. */
-int
-side_effects_p (x)
- rtx x;
+rtx
+hoist_insn_after (rtx insn, rtx after, rtx val, rtx new)
+{
+ rtx pat;
+ int i;
+ rtx note;
+ int applied;
+
+ insn = emit_copy_of_insn_after (insn, after);
+ pat = PATTERN (insn);
+
+ /* Remove REG_UNUSED notes as we will re-emit them. */
+ while ((note = find_reg_note (insn, REG_UNUSED, NULL_RTX)))
+ remove_note (insn, note);
+
+ /* To get this working callers must ensure to move everything referenced
+ by REG_EQUAL/REG_EQUIV notes too. Lets remove them, it is probably
+ easier. */
+ while ((note = find_reg_note (insn, REG_EQUAL, NULL_RTX)))
+ remove_note (insn, note);
+ while ((note = find_reg_note (insn, REG_EQUIV, NULL_RTX)))
+ remove_note (insn, note);
+
+ /* Remove REG_DEAD notes as they might not be valid anymore in case
+ we create redundancy. */
+ while ((note = find_reg_note (insn, REG_DEAD, NULL_RTX)))
+ remove_note (insn, note);
+ switch (GET_CODE (pat))
+ {
+ case SET:
+ hoist_update_store (insn, &SET_DEST (pat), val, new);
+ break;
+ case USE:
+ break;
+ case CLOBBER:
+ hoist_update_store (insn, &XEXP (pat, 0), val, new);
+ break;
+ case PARALLEL:
+ for (i = 0; i < XVECLEN (pat, 0); i++)
+ {
+ rtx x = XVECEXP (pat, 0, i);
+ switch (GET_CODE (x))
+ {
+ case SET:
+ hoist_update_store (insn, &SET_DEST (x), val, new);
+ break;
+ case USE:
+ break;
+ case CLOBBER:
+ hoist_update_store (insn, &SET_DEST (x), val, new);
+ break;
+ default:
+ break;
+ }
+ }
+ break;
+ default:
+ gcc_unreachable ();
+ }
+ applied = apply_change_group ();
+ gcc_assert (applied);
+
+ return insn;
+}
+
+rtx
+hoist_insn_to_edge (rtx insn, edge e, rtx val, rtx new)
{
- register RTX_CODE code;
+ rtx new_insn;
- code = GET_CODE (x);
- switch (code)
+ /* We cannot insert instructions on an abnormal critical edge.
+ It will be easier to find the culprit if we die now. */
+ gcc_assert (!(e->flags & EDGE_ABNORMAL) || !EDGE_CRITICAL_P (e));
+
+ /* Do not use emit_insn_on_edge as we want to preserve notes and similar
+ stuff. We also emit CALL_INSNS and firends. */
+ if (e->insns.r == NULL_RTX)
{
- case LABEL_REF:
- case SYMBOL_REF:
- case CONST_INT:
- case CONST:
- case CONST_DOUBLE:
- case CC0:
- case PC:
- case REG:
- case SCRATCH:
- case ASM_INPUT:
- case ADDR_VEC:
- case ADDR_DIFF_VEC:
- return 0;
+ start_sequence ();
+ emit_note (NOTE_INSN_DELETED);
+ }
+ else
+ push_to_sequence (e->insns.r);
+
+ new_insn = hoist_insn_after (insn, get_last_insn (), val, new);
- case CLOBBER:
- /* Reject CLOBBER with a non-VOID mode. These are made by combine.c
- when some combination can't be done. If we see one, don't think
- that we can simplify the expression. */
- return (GET_MODE (x) != VOIDmode);
+ e->insns.r = get_insns ();
+ end_sequence ();
+ return new_insn;
+}
- case PRE_INC:
- case PRE_DEC:
- case POST_INC:
- case POST_DEC:
- case CALL:
- case UNSPEC_VOLATILE:
- /* case TRAP_IF: This isn't clear yet. */
- return 1;
+/* Return true if LABEL is a target of JUMP_INSN. This applies only
+ to non-complex jumps. That is, direct unconditional, conditional,
+ and tablejumps, but not computed jumps or returns. It also does
+ not apply to the fallthru case of a conditional jump. */
- case MEM:
- case ASM_OPERANDS:
- if (MEM_VOLATILE_P (x))
- return 1;
+bool
+label_is_jump_target_p (rtx label, rtx jump_insn)
+{
+ rtx tmp = JUMP_LABEL (jump_insn);
- default:
- break;
- }
+ if (label == tmp)
+ return true;
- /* Recursively scan the operands of this expression. */
+ if (tablejump_p (jump_insn, NULL, &tmp))
+ {
+ rtvec vec = XVEC (PATTERN (tmp),
+ GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC);
+ int i, veclen = GET_NUM_ELEM (vec);
- {
- register char *fmt = GET_RTX_FORMAT (code);
- register int i;
-
- for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
- {
- if (fmt[i] == 'e')
- {
- if (side_effects_p (XEXP (x, i)))
- return 1;
- }
- if (fmt[i] == 'E')
- {
- register int j;
- for (j = 0; j < XVECLEN (x, i); j++)
- if (side_effects_p (XVECEXP (x, i, j)))
- return 1;
- }
- }
- }
- return 0;
+ for (i = 0; i < veclen; ++i)
+ if (XEXP (RTVEC_ELT (vec, i), 0) == label)
+ return true;
+ }
+
+ return false;
}
+
\f
-/* Return nonzero if evaluating rtx X might cause a trap. */
+/* Return an estimate of the cost of computing rtx X.
+ One use is in cse, to decide which expression to keep in the hash table.
+ Another is in rtl generation, to pick the cheapest way to multiply.
+ Other uses like the latter are expected in the future. */
int
-may_trap_p (x)
- rtx x;
+rtx_cost (rtx x, enum rtx_code outer_code ATTRIBUTE_UNUSED)
{
- int i;
+ int i, j;
enum rtx_code code;
- char *fmt;
+ const char *fmt;
+ int total;
if (x == 0)
return 0;
+
+ /* Compute the default costs of certain things.
+ Note that targetm.rtx_costs can override the defaults. */
+
code = GET_CODE (x);
switch (code)
{
- /* Handle these cases quickly. */
- case CONST_INT:
- case CONST_DOUBLE:
- case SYMBOL_REF:
- case LABEL_REF:
- case CONST:
- case PC:
- case CC0:
- case REG:
- case SCRATCH:
- return 0;
-
- /* Conditional trap can trap! */
- case UNSPEC_VOLATILE:
- case TRAP_IF:
- return 1;
-
- /* Memory ref can trap unless it's a static var or a stack slot. */
- case MEM:
- return rtx_addr_can_trap_p (XEXP (x, 0));
-
- /* Division by a non-constant might trap. */
+ case MULT:
+ total = COSTS_N_INSNS (5);
+ break;
case DIV:
- case MOD:
case UDIV:
+ case MOD:
case UMOD:
- if (! CONSTANT_P (XEXP (x, 1))
- || GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT)
- return 1;
- /* This was const0_rtx, but by not using that,
- we can link this file into other programs. */
- if (GET_CODE (XEXP (x, 1)) == CONST_INT && INTVAL (XEXP (x, 1)) == 0)
- return 1;
+ total = COSTS_N_INSNS (7);
+ break;
+ case USE:
+ /* Used in loop.c and combine.c as a marker. */
+ total = 0;
break;
+ default:
+ total = COSTS_N_INSNS (1);
+ }
- case EXPR_LIST:
- /* An EXPR_LIST is used to represent a function call. This
- certainly may trap. */
- return 1;
+ switch (code)
+ {
+ case REG:
+ return 0;
+
+ case SUBREG:
+ /* If we can't tie these modes, make this expensive. The larger
+ the mode, the more expensive it is. */
+ if (! MODES_TIEABLE_P (GET_MODE (x), GET_MODE (SUBREG_REG (x))))
+ return COSTS_N_INSNS (2
+ + GET_MODE_SIZE (GET_MODE (x)) / UNITS_PER_WORD);
+ break;
default:
- /* Any floating arithmetic may trap. */
- if (GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT)
- return 1;
+ if (targetm.rtx_costs (x, code, outer_code, &total))
+ return total;
+ break;
}
+ /* Sum the costs of the sub-rtx's, plus cost of this operation,
+ which is already in total. */
+
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
- {
- if (fmt[i] == 'e')
- {
- if (may_trap_p (XEXP (x, i)))
- return 1;
- }
- else if (fmt[i] == 'E')
- {
- register int j;
- for (j = 0; j < XVECLEN (x, i); j++)
- if (may_trap_p (XVECEXP (x, i, j)))
- return 1;
- }
- }
- return 0;
+ if (fmt[i] == 'e')
+ total += rtx_cost (XEXP (x, i), code);
+ else if (fmt[i] == 'E')
+ for (j = 0; j < XVECLEN (x, i); j++)
+ total += rtx_cost (XVECEXP (x, i, j), code);
+
+ return total;
}
\f
-/* Return nonzero if X contains a comparison that is not either EQ or NE,
- i.e., an inequality. */
+/* Return cost of address expression X.
+ Expect that X is properly formed address reference. */
int
-inequality_comparisons_p (x)
- rtx x;
+address_cost (rtx x, enum machine_mode mode)
{
- register char *fmt;
- register int len, i;
- register enum rtx_code code = GET_CODE (x);
+ /* We may be asked for cost of various unusual addresses, such as operands
+ of push instruction. It is not worthwhile to complicate writing
+ of the target hook by such cases. */
- switch (code)
- {
- case REG:
- case SCRATCH:
- case PC:
- case CC0:
- case CONST_INT:
- case CONST_DOUBLE:
- case CONST:
- case LABEL_REF:
- case SYMBOL_REF:
- return 0;
+ if (!memory_address_p (mode, x))
+ return 1000;
- case LT:
- case LTU:
- case GT:
- case GTU:
- case LE:
- case LEU:
- case GE:
- case GEU:
- return 1;
-
- default:
- break;
- }
+ return targetm.address_cost (x);
+}
- len = GET_RTX_LENGTH (code);
- fmt = GET_RTX_FORMAT (code);
+/* If the target doesn't override, compute the cost as with arithmetic. */
- for (i = 0; i < len; i++)
- {
- if (fmt[i] == 'e')
- {
- if (inequality_comparisons_p (XEXP (x, i)))
- return 1;
- }
- else if (fmt[i] == 'E')
- {
- register int j;
- for (j = XVECLEN (x, i) - 1; j >= 0; j--)
- if (inequality_comparisons_p (XVECEXP (x, i, j)))
- return 1;
- }
- }
-
- return 0;
+int
+default_address_cost (rtx x)
+{
+ return rtx_cost (x, MEM);
}
\f
-/* Replace any occurrence of FROM in X with TO. The function does
- not enter into CONST_DOUBLE for the replace.
- Note that copying is not done so X must not be shared unless all copies
- are to be modified. */
+unsigned HOST_WIDE_INT
+nonzero_bits (rtx x, enum machine_mode mode)
+{
+ return cached_nonzero_bits (x, mode, NULL_RTX, VOIDmode, 0);
+}
-rtx
-replace_rtx (x, from, to)
- rtx x, from, to;
+unsigned int
+num_sign_bit_copies (rtx x, enum machine_mode mode)
{
- register int i, j;
- register char *fmt;
+ return cached_num_sign_bit_copies (x, mode, NULL_RTX, VOIDmode, 0);
+}
- /* The following prevents loops occurrence when we change MEM in
- CONST_DOUBLE onto the same CONST_DOUBLE. */
- if (x != 0 && GET_CODE (x) == CONST_DOUBLE)
- return x;
+/* The function cached_nonzero_bits is a wrapper around nonzero_bits1.
+ It avoids exponential behavior in nonzero_bits1 when X has
+ identical subexpressions on the first or the second level. */
- if (x == from)
- return to;
+static unsigned HOST_WIDE_INT
+cached_nonzero_bits (rtx x, enum machine_mode mode, rtx known_x,
+ enum machine_mode known_mode,
+ unsigned HOST_WIDE_INT known_ret)
+{
+ if (x == known_x && mode == known_mode)
+ return known_ret;
- /* Allow this function to make replacements in EXPR_LISTs. */
- if (x == 0)
- return 0;
+ /* Try to find identical subexpressions. If found call
+ nonzero_bits1 on X with the subexpressions as KNOWN_X and the
+ precomputed value for the subexpression as KNOWN_RET. */
- fmt = GET_RTX_FORMAT (GET_CODE (x));
- for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
+ if (ARITHMETIC_P (x))
{
- if (fmt[i] == 'e')
- XEXP (x, i) = replace_rtx (XEXP (x, i), from, to);
- else if (fmt[i] == 'E')
- for (j = XVECLEN (x, i) - 1; j >= 0; j--)
- XVECEXP (x, i, j) = replace_rtx (XVECEXP (x, i, j), from, to);
+ rtx x0 = XEXP (x, 0);
+ rtx x1 = XEXP (x, 1);
+
+ /* Check the first level. */
+ if (x0 == x1)
+ return nonzero_bits1 (x, mode, x0, mode,
+ cached_nonzero_bits (x0, mode, known_x,
+ known_mode, known_ret));
+
+ /* Check the second level. */
+ if (ARITHMETIC_P (x0)
+ && (x1 == XEXP (x0, 0) || x1 == XEXP (x0, 1)))
+ return nonzero_bits1 (x, mode, x1, mode,
+ cached_nonzero_bits (x1, mode, known_x,
+ known_mode, known_ret));
+
+ if (ARITHMETIC_P (x1)
+ && (x0 == XEXP (x1, 0) || x0 == XEXP (x1, 1)))
+ return nonzero_bits1 (x, mode, x0, mode,
+ cached_nonzero_bits (x0, mode, known_x,
+ known_mode, known_ret));
}
- return x;
-}
-\f
-/* Throughout the rtx X, replace many registers according to REG_MAP.
- Return the replacement for X (which may be X with altered contents).
- REG_MAP[R] is the replacement for register R, or 0 for don't replace.
- NREGS is the length of REG_MAP; regs >= NREGS are not mapped.
+ return nonzero_bits1 (x, mode, known_x, known_mode, known_ret);
+}
- We only support REG_MAP entries of REG or SUBREG. Also, hard registers
- should not be mapped to pseudos or vice versa since validate_change
- is not called.
+/* We let num_sign_bit_copies recur into nonzero_bits as that is useful.
+ We don't let nonzero_bits recur into num_sign_bit_copies, because that
+ is less useful. We can't allow both, because that results in exponential
+ run time recursion. There is a nullstone testcase that triggered
+ this. This macro avoids accidental uses of num_sign_bit_copies. */
+#define cached_num_sign_bit_copies sorry_i_am_preventing_exponential_behavior
+
+/* Given an expression, X, compute which bits in X can be nonzero.
+ We don't care about bits outside of those defined in MODE.
+
+ For most X this is simply GET_MODE_MASK (GET_MODE (MODE)), but if X is
+ an arithmetic operation, we can do better. */
+
+static unsigned HOST_WIDE_INT
+nonzero_bits1 (rtx x, enum machine_mode mode, rtx known_x,
+ enum machine_mode known_mode,
+ unsigned HOST_WIDE_INT known_ret)
+{
+ unsigned HOST_WIDE_INT nonzero = GET_MODE_MASK (mode);
+ unsigned HOST_WIDE_INT inner_nz;
+ enum rtx_code code;
+ unsigned int mode_width = GET_MODE_BITSIZE (mode);
+
+ /* For floating-point values, assume all bits are needed. */
+ if (FLOAT_MODE_P (GET_MODE (x)) || FLOAT_MODE_P (mode))
+ return nonzero;
+
+ /* If X is wider than MODE, use its mode instead. */
+ if (GET_MODE_BITSIZE (GET_MODE (x)) > mode_width)
+ {
+ mode = GET_MODE (x);
+ nonzero = GET_MODE_MASK (mode);
+ mode_width = GET_MODE_BITSIZE (mode);
+ }
+
+ if (mode_width > HOST_BITS_PER_WIDE_INT)
+ /* Our only callers in this case look for single bit values. So
+ just return the mode mask. Those tests will then be false. */
+ return nonzero;
+
+#ifndef WORD_REGISTER_OPERATIONS
+ /* If MODE is wider than X, but both are a single word for both the host
+ and target machines, we can compute this from which bits of the
+ object might be nonzero in its own mode, taking into account the fact
+ that on many CISC machines, accessing an object in a wider mode
+ causes the high-order bits to become undefined. So they are
+ not known to be zero. */
+
+ if (GET_MODE (x) != VOIDmode && GET_MODE (x) != mode
+ && GET_MODE_BITSIZE (GET_MODE (x)) <= BITS_PER_WORD
+ && GET_MODE_BITSIZE (GET_MODE (x)) <= HOST_BITS_PER_WIDE_INT
+ && GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (GET_MODE (x)))
+ {
+ nonzero &= cached_nonzero_bits (x, GET_MODE (x),
+ known_x, known_mode, known_ret);
+ nonzero |= GET_MODE_MASK (mode) & ~GET_MODE_MASK (GET_MODE (x));
+ return nonzero;
+ }
+#endif
+
+ code = GET_CODE (x);
+ switch (code)
+ {
+ case REG:
+#if defined(POINTERS_EXTEND_UNSIGNED) && !defined(HAVE_ptr_extend)
+ /* If pointers extend unsigned and this is a pointer in Pmode, say that
+ all the bits above ptr_mode are known to be zero. */
+ if (POINTERS_EXTEND_UNSIGNED && GET_MODE (x) == Pmode
+ && REG_POINTER (x))
+ nonzero &= GET_MODE_MASK (ptr_mode);
+#endif
+
+ /* Include declared information about alignment of pointers. */
+ /* ??? We don't properly preserve REG_POINTER changes across
+ pointer-to-integer casts, so we can't trust it except for
+ things that we know must be pointers. See execute/960116-1.c. */
+ if ((x == stack_pointer_rtx
+ || x == frame_pointer_rtx
+ || x == arg_pointer_rtx)
+ && REGNO_POINTER_ALIGN (REGNO (x)))
+ {
+ unsigned HOST_WIDE_INT alignment
+ = REGNO_POINTER_ALIGN (REGNO (x)) / BITS_PER_UNIT;
+
+#ifdef PUSH_ROUNDING
+ /* If PUSH_ROUNDING is defined, it is possible for the
+ stack to be momentarily aligned only to that amount,
+ so we pick the least alignment. */
+ if (x == stack_pointer_rtx && PUSH_ARGS)
+ alignment = MIN ((unsigned HOST_WIDE_INT) PUSH_ROUNDING (1),
+ alignment);
+#endif
+
+ nonzero &= ~(alignment - 1);
+ }
+
+ {
+ unsigned HOST_WIDE_INT nonzero_for_hook = nonzero;
+ rtx new = rtl_hooks.reg_nonzero_bits (x, mode, known_x,
+ known_mode, known_ret,
+ &nonzero_for_hook);
+
+ if (new)
+ nonzero_for_hook &= cached_nonzero_bits (new, mode, known_x,
+ known_mode, known_ret);
+
+ return nonzero_for_hook;
+ }
+
+ case CONST_INT:
+#ifdef SHORT_IMMEDIATES_SIGN_EXTEND
+ /* If X is negative in MODE, sign-extend the value. */
+ if (INTVAL (x) > 0 && mode_width < BITS_PER_WORD
+ && 0 != (INTVAL (x) & ((HOST_WIDE_INT) 1 << (mode_width - 1))))
+ return (INTVAL (x) | ((HOST_WIDE_INT) (-1) << mode_width));
+#endif
+
+ return INTVAL (x);
+
+ case MEM:
+#ifdef LOAD_EXTEND_OP
+ /* In many, if not most, RISC machines, reading a byte from memory
+ zeros the rest of the register. Noticing that fact saves a lot
+ of extra zero-extends. */
+ if (LOAD_EXTEND_OP (GET_MODE (x)) == ZERO_EXTEND)
+ nonzero &= GET_MODE_MASK (GET_MODE (x));
+#endif
+ break;
+
+ case EQ: case NE:
+ case UNEQ: case LTGT:
+ case GT: case GTU: case UNGT:
+ case LT: case LTU: case UNLT:
+ case GE: case GEU: case UNGE:
+ case LE: case LEU: case UNLE:
+ case UNORDERED: case ORDERED:
+
+ /* If this produces an integer result, we know which bits are set.
+ Code here used to clear bits outside the mode of X, but that is
+ now done above. */
+
+ if (GET_MODE_CLASS (mode) == MODE_INT
+ && mode_width <= HOST_BITS_PER_WIDE_INT)
+ nonzero = STORE_FLAG_VALUE;
+ break;
+
+ case NEG:
+#if 0
+ /* Disabled to avoid exponential mutual recursion between nonzero_bits
+ and num_sign_bit_copies. */
+ if (num_sign_bit_copies (XEXP (x, 0), GET_MODE (x))
+ == GET_MODE_BITSIZE (GET_MODE (x)))
+ nonzero = 1;
+#endif
+
+ if (GET_MODE_SIZE (GET_MODE (x)) < mode_width)
+ nonzero |= (GET_MODE_MASK (mode) & ~GET_MODE_MASK (GET_MODE (x)));
+ break;
+
+ case ABS:
+#if 0
+ /* Disabled to avoid exponential mutual recursion between nonzero_bits
+ and num_sign_bit_copies. */
+ if (num_sign_bit_copies (XEXP (x, 0), GET_MODE (x))
+ == GET_MODE_BITSIZE (GET_MODE (x)))
+ nonzero = 1;
+#endif
+ break;
+
+ case TRUNCATE:
+ nonzero &= (cached_nonzero_bits (XEXP (x, 0), mode,
+ known_x, known_mode, known_ret)
+ & GET_MODE_MASK (mode));
+ break;
+
+ case ZERO_EXTEND:
+ nonzero &= cached_nonzero_bits (XEXP (x, 0), mode,
+ known_x, known_mode, known_ret);
+ if (GET_MODE (XEXP (x, 0)) != VOIDmode)
+ nonzero &= GET_MODE_MASK (GET_MODE (XEXP (x, 0)));
+ break;
+
+ case SIGN_EXTEND:
+ /* If the sign bit is known clear, this is the same as ZERO_EXTEND.
+ Otherwise, show all the bits in the outer mode but not the inner
+ may be nonzero. */
+ inner_nz = cached_nonzero_bits (XEXP (x, 0), mode,
+ known_x, known_mode, known_ret);
+ if (GET_MODE (XEXP (x, 0)) != VOIDmode)
+ {
+ inner_nz &= GET_MODE_MASK (GET_MODE (XEXP (x, 0)));
+ if (inner_nz
+ & (((HOST_WIDE_INT) 1
+ << (GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0))) - 1))))
+ inner_nz |= (GET_MODE_MASK (mode)
+ & ~GET_MODE_MASK (GET_MODE (XEXP (x, 0))));
+ }
+
+ nonzero &= inner_nz;
+ break;
+
+ case AND:
+ nonzero &= cached_nonzero_bits (XEXP (x, 0), mode,
+ known_x, known_mode, known_ret)
+ & cached_nonzero_bits (XEXP (x, 1), mode,
+ known_x, known_mode, known_ret);
+ break;
+
+ case XOR: case IOR:
+ case UMIN: case UMAX: case SMIN: case SMAX:
+ {
+ unsigned HOST_WIDE_INT nonzero0 =
+ cached_nonzero_bits (XEXP (x, 0), mode,
+ known_x, known_mode, known_ret);
+
+ /* Don't call nonzero_bits for the second time if it cannot change
+ anything. */
+ if ((nonzero & nonzero0) != nonzero)
+ nonzero &= nonzero0
+ | cached_nonzero_bits (XEXP (x, 1), mode,
+ known_x, known_mode, known_ret);
+ }
+ break;
+
+ case PLUS: case MINUS:
+ case MULT:
+ case DIV: case UDIV:
+ case MOD: case UMOD:
+ /* We can apply the rules of arithmetic to compute the number of
+ high- and low-order zero bits of these operations. We start by
+ computing the width (position of the highest-order nonzero bit)
+ and the number of low-order zero bits for each value. */
+ {
+ unsigned HOST_WIDE_INT nz0 =
+ cached_nonzero_bits (XEXP (x, 0), mode,
+ known_x, known_mode, known_ret);
+ unsigned HOST_WIDE_INT nz1 =
+ cached_nonzero_bits (XEXP (x, 1), mode,
+ known_x, known_mode, known_ret);
+ int sign_index = GET_MODE_BITSIZE (GET_MODE (x)) - 1;
+ int width0 = floor_log2 (nz0) + 1;
+ int width1 = floor_log2 (nz1) + 1;
+ int low0 = floor_log2 (nz0 & -nz0);
+ int low1 = floor_log2 (nz1 & -nz1);
+ HOST_WIDE_INT op0_maybe_minusp
+ = (nz0 & ((HOST_WIDE_INT) 1 << sign_index));
+ HOST_WIDE_INT op1_maybe_minusp
+ = (nz1 & ((HOST_WIDE_INT) 1 << sign_index));
+ unsigned int result_width = mode_width;
+ int result_low = 0;
+
+ switch (code)
+ {
+ case PLUS:
+ result_width = MAX (width0, width1) + 1;
+ result_low = MIN (low0, low1);
+ break;
+ case MINUS:
+ result_low = MIN (low0, low1);
+ break;
+ case MULT:
+ result_width = width0 + width1;
+ result_low = low0 + low1;
+ break;
+ case DIV:
+ if (width1 == 0)
+ break;
+ if (! op0_maybe_minusp && ! op1_maybe_minusp)
+ result_width = width0;
+ break;
+ case UDIV:
+ if (width1 == 0)
+ break;
+ result_width = width0;
+ break;
+ case MOD:
+ if (width1 == 0)
+ break;
+ if (! op0_maybe_minusp && ! op1_maybe_minusp)
+ result_width = MIN (width0, width1);
+ result_low = MIN (low0, low1);
+ break;
+ case UMOD:
+ if (width1 == 0)
+ break;
+ result_width = MIN (width0, width1);
+ result_low = MIN (low0, low1);
+ break;
+ default:
+ gcc_unreachable ();
+ }
- If REPLACE_DEST is 1, replacements are also done in destinations;
- otherwise, only sources are replaced. */
+ if (result_width < mode_width)
+ nonzero &= ((HOST_WIDE_INT) 1 << result_width) - 1;
-rtx
-replace_regs (x, reg_map, nregs, replace_dest)
- rtx x;
- rtx *reg_map;
- int nregs;
- int replace_dest;
-{
- register enum rtx_code code;
- register int i;
- register char *fmt;
+ if (result_low > 0)
+ nonzero &= ~(((HOST_WIDE_INT) 1 << result_low) - 1);
- if (x == 0)
- return x;
+#ifdef POINTERS_EXTEND_UNSIGNED
+ /* If pointers extend unsigned and this is an addition or subtraction
+ to a pointer in Pmode, all the bits above ptr_mode are known to be
+ zero. */
+ if (POINTERS_EXTEND_UNSIGNED > 0 && GET_MODE (x) == Pmode
+ && (code == PLUS || code == MINUS)
+ && REG_P (XEXP (x, 0)) && REG_POINTER (XEXP (x, 0)))
+ nonzero &= GET_MODE_MASK (ptr_mode);
+#endif
+ }
+ break;
- code = GET_CODE (x);
- switch (code)
- {
- case SCRATCH:
- case PC:
- case CC0:
- case CONST_INT:
- case CONST_DOUBLE:
- case CONST:
- case SYMBOL_REF:
- case LABEL_REF:
- return x;
+ case ZERO_EXTRACT:
+ if (GET_CODE (XEXP (x, 1)) == CONST_INT
+ && INTVAL (XEXP (x, 1)) < HOST_BITS_PER_WIDE_INT)
+ nonzero &= ((HOST_WIDE_INT) 1 << INTVAL (XEXP (x, 1))) - 1;
+ break;
- case REG:
- /* Verify that the register has an entry before trying to access it. */
- if (REGNO (x) < nregs && reg_map[REGNO (x)] != 0)
+ case SUBREG:
+ /* If this is a SUBREG formed for a promoted variable that has
+ been zero-extended, we know that at least the high-order bits
+ are zero, though others might be too. */
+
+ if (SUBREG_PROMOTED_VAR_P (x) && SUBREG_PROMOTED_UNSIGNED_P (x) > 0)
+ nonzero = GET_MODE_MASK (GET_MODE (x))
+ & cached_nonzero_bits (SUBREG_REG (x), GET_MODE (x),
+ known_x, known_mode, known_ret);
+
+ /* If the inner mode is a single word for both the host and target
+ machines, we can compute this from which bits of the inner
+ object might be nonzero. */
+ if (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) <= BITS_PER_WORD
+ && (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x)))
+ <= HOST_BITS_PER_WIDE_INT))
{
- /* SUBREGs can't be shared. Always return a copy to ensure that if
- this replacement occurs more than once then each instance will
- get distinct rtx. */
- if (GET_CODE (reg_map[REGNO (x)]) == SUBREG)
- return copy_rtx (reg_map[REGNO (x)]);
- return reg_map[REGNO (x)];
+ nonzero &= cached_nonzero_bits (SUBREG_REG (x), mode,
+ known_x, known_mode, known_ret);
+
+#if defined (WORD_REGISTER_OPERATIONS) && defined (LOAD_EXTEND_OP)
+ /* If this is a typical RISC machine, we only have to worry
+ about the way loads are extended. */
+ if ((LOAD_EXTEND_OP (GET_MODE (SUBREG_REG (x))) == SIGN_EXTEND
+ ? (((nonzero
+ & (((unsigned HOST_WIDE_INT) 1
+ << (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) - 1))))
+ != 0))
+ : LOAD_EXTEND_OP (GET_MODE (SUBREG_REG (x))) != ZERO_EXTEND)
+ || !MEM_P (SUBREG_REG (x)))
+#endif
+ {
+ /* On many CISC machines, accessing an object in a wider mode
+ causes the high-order bits to become undefined. So they are
+ not known to be zero. */
+ if (GET_MODE_SIZE (GET_MODE (x))
+ > GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
+ nonzero |= (GET_MODE_MASK (GET_MODE (x))
+ & ~GET_MODE_MASK (GET_MODE (SUBREG_REG (x))));
+ }
}
- return x;
+ break;
- case SUBREG:
- /* Prevent making nested SUBREGs. */
- if (GET_CODE (SUBREG_REG (x)) == REG && REGNO (SUBREG_REG (x)) < nregs
- && reg_map[REGNO (SUBREG_REG (x))] != 0
- && GET_CODE (reg_map[REGNO (SUBREG_REG (x))]) == SUBREG)
+ case ASHIFTRT:
+ case LSHIFTRT:
+ case ASHIFT:
+ case ROTATE:
+ /* The nonzero bits are in two classes: any bits within MODE
+ that aren't in GET_MODE (x) are always significant. The rest of the
+ nonzero bits are those that are significant in the operand of
+ the shift when shifted the appropriate number of bits. This
+ shows that high-order bits are cleared by the right shift and
+ low-order bits by left shifts. */
+ if (GET_CODE (XEXP (x, 1)) == CONST_INT
+ && INTVAL (XEXP (x, 1)) >= 0
+ && INTVAL (XEXP (x, 1)) < HOST_BITS_PER_WIDE_INT)
{
- rtx map_val = reg_map[REGNO (SUBREG_REG (x))];
- rtx map_inner = SUBREG_REG (map_val);
-
- if (GET_MODE (x) == GET_MODE (map_inner))
- return map_inner;
- else
+ enum machine_mode inner_mode = GET_MODE (x);
+ unsigned int width = GET_MODE_BITSIZE (inner_mode);
+ int count = INTVAL (XEXP (x, 1));
+ unsigned HOST_WIDE_INT mode_mask = GET_MODE_MASK (inner_mode);
+ unsigned HOST_WIDE_INT op_nonzero =
+ cached_nonzero_bits (XEXP (x, 0), mode,
+ known_x, known_mode, known_ret);
+ unsigned HOST_WIDE_INT inner = op_nonzero & mode_mask;
+ unsigned HOST_WIDE_INT outer = 0;
+
+ if (mode_width > width)
+ outer = (op_nonzero & nonzero & ~mode_mask);
+
+ if (code == LSHIFTRT)
+ inner >>= count;
+ else if (code == ASHIFTRT)
{
- /* We cannot call gen_rtx here since we may be linked with
- genattrtab.c. */
- /* Let's try clobbering the incoming SUBREG and see
- if this is really safe. */
- SUBREG_REG (x) = map_inner;
- SUBREG_WORD (x) += SUBREG_WORD (map_val);
- return x;
-#if 0
- rtx new = rtx_alloc (SUBREG);
- PUT_MODE (new, GET_MODE (x));
- SUBREG_REG (new) = map_inner;
- SUBREG_WORD (new) = SUBREG_WORD (x) + SUBREG_WORD (map_val);
-#endif
+ inner >>= count;
+
+ /* If the sign bit may have been nonzero before the shift, we
+ need to mark all the places it could have been copied to
+ by the shift as possibly nonzero. */
+ if (inner & ((HOST_WIDE_INT) 1 << (width - 1 - count)))
+ inner |= (((HOST_WIDE_INT) 1 << count) - 1) << (width - count);
}
+ else if (code == ASHIFT)
+ inner <<= count;
+ else
+ inner = ((inner << (count % width)
+ | (inner >> (width - (count % width)))) & mode_mask);
+
+ nonzero &= (outer | inner);
}
break;
- case SET:
- if (replace_dest)
- SET_DEST (x) = replace_regs (SET_DEST (x), reg_map, nregs, 0);
+ case FFS:
+ case POPCOUNT:
+ /* This is at most the number of bits in the mode. */
+ nonzero = ((HOST_WIDE_INT) 2 << (floor_log2 (mode_width))) - 1;
+ break;
- else if (GET_CODE (SET_DEST (x)) == MEM
- || GET_CODE (SET_DEST (x)) == STRICT_LOW_PART)
- /* Even if we are not to replace destinations, replace register if it
- is CONTAINED in destination (destination is memory or
- STRICT_LOW_PART). */
- XEXP (SET_DEST (x), 0) = replace_regs (XEXP (SET_DEST (x), 0),
- reg_map, nregs, 0);
- else if (GET_CODE (SET_DEST (x)) == ZERO_EXTRACT)
- /* Similarly, for ZERO_EXTRACT we replace all operands. */
- break;
+ case CLZ:
+ /* If CLZ has a known value at zero, then the nonzero bits are
+ that value, plus the number of bits in the mode minus one. */
+ if (CLZ_DEFINED_VALUE_AT_ZERO (mode, nonzero))
+ nonzero |= ((HOST_WIDE_INT) 1 << (floor_log2 (mode_width))) - 1;
+ else
+ nonzero = -1;
+ break;
+
+ case CTZ:
+ /* If CTZ has a known value at zero, then the nonzero bits are
+ that value, plus the number of bits in the mode minus one. */
+ if (CTZ_DEFINED_VALUE_AT_ZERO (mode, nonzero))
+ nonzero |= ((HOST_WIDE_INT) 1 << (floor_log2 (mode_width))) - 1;
+ else
+ nonzero = -1;
+ break;
+
+ case PARITY:
+ nonzero = 1;
+ break;
+
+ case IF_THEN_ELSE:
+ {
+ unsigned HOST_WIDE_INT nonzero_true =
+ cached_nonzero_bits (XEXP (x, 1), mode,
+ known_x, known_mode, known_ret);
+
+ /* Don't call nonzero_bits for the second time if it cannot change
+ anything. */
+ if ((nonzero & nonzero_true) != nonzero)
+ nonzero &= nonzero_true
+ | cached_nonzero_bits (XEXP (x, 2), mode,
+ known_x, known_mode, known_ret);
+ }
+ break;
- SET_SRC (x) = replace_regs (SET_SRC (x), reg_map, nregs, 0);
- return x;
-
default:
break;
}
- fmt = GET_RTX_FORMAT (code);
- for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+ return nonzero;
+}
+
+/* See the macro definition above. */
+#undef cached_num_sign_bit_copies
+
+\f
+/* The function cached_num_sign_bit_copies is a wrapper around
+ num_sign_bit_copies1. It avoids exponential behavior in
+ num_sign_bit_copies1 when X has identical subexpressions on the
+ first or the second level. */
+
+static unsigned int
+cached_num_sign_bit_copies (rtx x, enum machine_mode mode, rtx known_x,
+ enum machine_mode known_mode,
+ unsigned int known_ret)
+{
+ if (x == known_x && mode == known_mode)
+ return known_ret;
+
+ /* Try to find identical subexpressions. If found call
+ num_sign_bit_copies1 on X with the subexpressions as KNOWN_X and
+ the precomputed value for the subexpression as KNOWN_RET. */
+
+ if (ARITHMETIC_P (x))
{
- if (fmt[i] == 'e')
- XEXP (x, i) = replace_regs (XEXP (x, i), reg_map, nregs, replace_dest);
- if (fmt[i] == 'E')
- {
- register int j;
- for (j = 0; j < XVECLEN (x, i); j++)
- XVECEXP (x, i, j) = replace_regs (XVECEXP (x, i, j), reg_map,
- nregs, replace_dest);
- }
+ rtx x0 = XEXP (x, 0);
+ rtx x1 = XEXP (x, 1);
+
+ /* Check the first level. */
+ if (x0 == x1)
+ return
+ num_sign_bit_copies1 (x, mode, x0, mode,
+ cached_num_sign_bit_copies (x0, mode, known_x,
+ known_mode,
+ known_ret));
+
+ /* Check the second level. */
+ if (ARITHMETIC_P (x0)
+ && (x1 == XEXP (x0, 0) || x1 == XEXP (x0, 1)))
+ return
+ num_sign_bit_copies1 (x, mode, x1, mode,
+ cached_num_sign_bit_copies (x1, mode, known_x,
+ known_mode,
+ known_ret));
+
+ if (ARITHMETIC_P (x1)
+ && (x0 == XEXP (x1, 0) || x0 == XEXP (x1, 1)))
+ return
+ num_sign_bit_copies1 (x, mode, x0, mode,
+ cached_num_sign_bit_copies (x0, mode, known_x,
+ known_mode,
+ known_ret));
}
- return x;
+
+ return num_sign_bit_copies1 (x, mode, known_x, known_mode, known_ret);
}
-/* Return 1 if X, the SRC_SRC of SET of (pc) contain a REG or MEM that is
- not in the constant pool and not in the condition of an IF_THEN_ELSE. */
+/* Return the number of bits at the high-order end of X that are known to
+ be equal to the sign bit. X will be used in mode MODE; if MODE is
+ VOIDmode, X will be used in its own mode. The returned value will always
+ be between 1 and the number of bits in MODE. */
-static int
-jmp_uses_reg_or_mem (x)
- rtx x;
+static unsigned int
+num_sign_bit_copies1 (rtx x, enum machine_mode mode, rtx known_x,
+ enum machine_mode known_mode,
+ unsigned int known_ret)
{
enum rtx_code code = GET_CODE (x);
- int i, j;
- char *fmt;
+ unsigned int bitwidth = GET_MODE_BITSIZE (mode);
+ int num0, num1, result;
+ unsigned HOST_WIDE_INT nonzero;
- switch (code)
+ /* If we weren't given a mode, use the mode of X. If the mode is still
+ VOIDmode, we don't know anything. Likewise if one of the modes is
+ floating-point. */
+
+ if (mode == VOIDmode)
+ mode = GET_MODE (x);
+
+ if (mode == VOIDmode || FLOAT_MODE_P (mode) || FLOAT_MODE_P (GET_MODE (x)))
+ return 1;
+
+ /* For a smaller object, just ignore the high bits. */
+ if (bitwidth < GET_MODE_BITSIZE (GET_MODE (x)))
{
- case CONST:
- case LABEL_REF:
- case PC:
- return 0;
+ num0 = cached_num_sign_bit_copies (x, GET_MODE (x),
+ known_x, known_mode, known_ret);
+ return MAX (1,
+ num0 - (int) (GET_MODE_BITSIZE (GET_MODE (x)) - bitwidth));
+ }
- case REG:
+ if (GET_MODE (x) != VOIDmode && bitwidth > GET_MODE_BITSIZE (GET_MODE (x)))
+ {
+#ifndef WORD_REGISTER_OPERATIONS
+ /* If this machine does not do all register operations on the entire
+ register and MODE is wider than the mode of X, we can say nothing
+ at all about the high-order bits. */
return 1;
+#else
+ /* Likewise on machines that do, if the mode of the object is smaller
+ than a word and loads of that size don't sign extend, we can say
+ nothing about the high order bits. */
+ if (GET_MODE_BITSIZE (GET_MODE (x)) < BITS_PER_WORD
+#ifdef LOAD_EXTEND_OP
+ && LOAD_EXTEND_OP (GET_MODE (x)) != SIGN_EXTEND
+#endif
+ )
+ return 1;
+#endif
+ }
- case MEM:
- return ! (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
- && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)));
+ switch (code)
+ {
+ case REG:
- case IF_THEN_ELSE:
- return (jmp_uses_reg_or_mem (XEXP (x, 1))
- || jmp_uses_reg_or_mem (XEXP (x, 2)));
+#if defined(POINTERS_EXTEND_UNSIGNED) && !defined(HAVE_ptr_extend)
+ /* If pointers extend signed and this is a pointer in Pmode, say that
+ all the bits above ptr_mode are known to be sign bit copies. */
+ if (! POINTERS_EXTEND_UNSIGNED && GET_MODE (x) == Pmode && mode == Pmode
+ && REG_POINTER (x))
+ return GET_MODE_BITSIZE (Pmode) - GET_MODE_BITSIZE (ptr_mode) + 1;
+#endif
- case PLUS: case MINUS: case MULT:
- return (jmp_uses_reg_or_mem (XEXP (x, 0))
- || jmp_uses_reg_or_mem (XEXP (x, 1)));
+ {
+ unsigned int copies_for_hook = 1, copies = 1;
+ rtx new = rtl_hooks.reg_num_sign_bit_copies (x, mode, known_x,
+ known_mode, known_ret,
+ &copies_for_hook);
- default:
- break;
- }
+ if (new)
+ copies = cached_num_sign_bit_copies (new, mode, known_x,
+ known_mode, known_ret);
- fmt = GET_RTX_FORMAT (code);
- for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
- {
- if (fmt[i] == 'e'
- && jmp_uses_reg_or_mem (XEXP (x, i)))
- return 1;
+ if (copies > 1 || copies_for_hook > 1)
+ return MAX (copies, copies_for_hook);
- if (fmt[i] == 'E')
- for (j = 0; j < XVECLEN (x, i); j++)
- if (jmp_uses_reg_or_mem (XVECEXP (x, i, j)))
- return 1;
- }
+ /* Else, use nonzero_bits to guess num_sign_bit_copies (see below). */
+ }
+ break;
- return 0;
-}
+ case MEM:
+#ifdef LOAD_EXTEND_OP
+ /* Some RISC machines sign-extend all loads of smaller than a word. */
+ if (LOAD_EXTEND_OP (GET_MODE (x)) == SIGN_EXTEND)
+ return MAX (1, ((int) bitwidth
+ - (int) GET_MODE_BITSIZE (GET_MODE (x)) + 1));
+#endif
+ break;
-/* Return nonzero if INSN is an indirect jump (aka computed jump).
+ case CONST_INT:
+ /* If the constant is negative, take its 1's complement and remask.
+ Then see how many zero bits we have. */
+ nonzero = INTVAL (x) & GET_MODE_MASK (mode);
+ if (bitwidth <= HOST_BITS_PER_WIDE_INT
+ && (nonzero & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)
+ nonzero = (~nonzero) & GET_MODE_MASK (mode);
- Tablejumps and casesi insns are not considered indirect jumps;
- we can recognize them by a (use (lael_ref)). */
+ return (nonzero == 0 ? bitwidth : bitwidth - floor_log2 (nonzero) - 1);
-int
-computed_jump_p (insn)
- rtx insn;
-{
- int i;
- if (GET_CODE (insn) == JUMP_INSN)
- {
- rtx pat = PATTERN (insn);
+ case SUBREG:
+ /* If this is a SUBREG for a promoted object that is sign-extended
+ and we are looking at it in a wider mode, we know that at least the
+ high-order bits are known to be sign bit copies. */
- if (GET_CODE (pat) == PARALLEL)
+ if (SUBREG_PROMOTED_VAR_P (x) && ! SUBREG_PROMOTED_UNSIGNED_P (x))
{
- int len = XVECLEN (pat, 0);
- int has_use_labelref = 0;
+ num0 = cached_num_sign_bit_copies (SUBREG_REG (x), mode,
+ known_x, known_mode, known_ret);
+ return MAX ((int) bitwidth
+ - (int) GET_MODE_BITSIZE (GET_MODE (x)) + 1,
+ num0);
+ }
- for (i = len - 1; i >= 0; i--)
- if (GET_CODE (XVECEXP (pat, 0, i)) == USE
- && (GET_CODE (XEXP (XVECEXP (pat, 0, i), 0))
- == LABEL_REF))
- has_use_labelref = 1;
+ /* For a smaller object, just ignore the high bits. */
+ if (bitwidth <= GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))))
+ {
+ num0 = cached_num_sign_bit_copies (SUBREG_REG (x), VOIDmode,
+ known_x, known_mode, known_ret);
+ return MAX (1, (num0
+ - (int) (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x)))
+ - bitwidth)));
+ }
- if (! has_use_labelref)
- for (i = len - 1; i >= 0; i--)
- if (GET_CODE (XVECEXP (pat, 0, i)) == SET
- && SET_DEST (XVECEXP (pat, 0, i)) == pc_rtx
- && jmp_uses_reg_or_mem (SET_SRC (XVECEXP (pat, 0, i))))
- return 1;
+#ifdef WORD_REGISTER_OPERATIONS
+#ifdef LOAD_EXTEND_OP
+ /* For paradoxical SUBREGs on machines where all register operations
+ affect the entire register, just look inside. Note that we are
+ passing MODE to the recursive call, so the number of sign bit copies
+ will remain relative to that mode, not the inner mode. */
+
+ /* This works only if loads sign extend. Otherwise, if we get a
+ reload for the inner part, it may be loaded from the stack, and
+ then we lose all sign bit copies that existed before the store
+ to the stack. */
+
+ if ((GET_MODE_SIZE (GET_MODE (x))
+ > GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
+ && LOAD_EXTEND_OP (GET_MODE (SUBREG_REG (x))) == SIGN_EXTEND
+ && MEM_P (SUBREG_REG (x)))
+ return cached_num_sign_bit_copies (SUBREG_REG (x), mode,
+ known_x, known_mode, known_ret);
+#endif
+#endif
+ break;
+
+ case SIGN_EXTRACT:
+ if (GET_CODE (XEXP (x, 1)) == CONST_INT)
+ return MAX (1, (int) bitwidth - INTVAL (XEXP (x, 1)));
+ break;
+
+ case SIGN_EXTEND:
+ return (bitwidth - GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0)))
+ + cached_num_sign_bit_copies (XEXP (x, 0), VOIDmode,
+ known_x, known_mode, known_ret));
+
+ case TRUNCATE:
+ /* For a smaller object, just ignore the high bits. */
+ num0 = cached_num_sign_bit_copies (XEXP (x, 0), VOIDmode,
+ known_x, known_mode, known_ret);
+ return MAX (1, (num0 - (int) (GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0)))
+ - bitwidth)));
+
+ case NOT:
+ return cached_num_sign_bit_copies (XEXP (x, 0), mode,
+ known_x, known_mode, known_ret);
+
+ case ROTATE: case ROTATERT:
+ /* If we are rotating left by a number of bits less than the number
+ of sign bit copies, we can just subtract that amount from the
+ number. */
+ if (GET_CODE (XEXP (x, 1)) == CONST_INT
+ && INTVAL (XEXP (x, 1)) >= 0
+ && INTVAL (XEXP (x, 1)) < (int) bitwidth)
+ {
+ num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
+ known_x, known_mode, known_ret);
+ return MAX (1, num0 - (code == ROTATE ? INTVAL (XEXP (x, 1))
+ : (int) bitwidth - INTVAL (XEXP (x, 1))));
}
- else if (GET_CODE (pat) == SET
- && SET_DEST (pat) == pc_rtx
- && jmp_uses_reg_or_mem (SET_SRC (pat)))
+ break;
+
+ case NEG:
+ /* In general, this subtracts one sign bit copy. But if the value
+ is known to be positive, the number of sign bit copies is the
+ same as that of the input. Finally, if the input has just one bit
+ that might be nonzero, all the bits are copies of the sign bit. */
+ num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
+ known_x, known_mode, known_ret);
+ if (bitwidth > HOST_BITS_PER_WIDE_INT)
+ return num0 > 1 ? num0 - 1 : 1;
+
+ nonzero = nonzero_bits (XEXP (x, 0), mode);
+ if (nonzero == 1)
+ return bitwidth;
+
+ if (num0 > 1
+ && (((HOST_WIDE_INT) 1 << (bitwidth - 1)) & nonzero))
+ num0--;
+
+ return num0;
+
+ case IOR: case AND: case XOR:
+ case SMIN: case SMAX: case UMIN: case UMAX:
+ /* Logical operations will preserve the number of sign-bit copies.
+ MIN and MAX operations always return one of the operands. */
+ num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
+ known_x, known_mode, known_ret);
+ num1 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
+ known_x, known_mode, known_ret);
+ return MIN (num0, num1);
+
+ case PLUS: case MINUS:
+ /* For addition and subtraction, we can have a 1-bit carry. However,
+ if we are subtracting 1 from a positive number, there will not
+ be such a carry. Furthermore, if the positive number is known to
+ be 0 or 1, we know the result is either -1 or 0. */
+
+ if (code == PLUS && XEXP (x, 1) == constm1_rtx
+ && bitwidth <= HOST_BITS_PER_WIDE_INT)
+ {
+ nonzero = nonzero_bits (XEXP (x, 0), mode);
+ if ((((HOST_WIDE_INT) 1 << (bitwidth - 1)) & nonzero) == 0)
+ return (nonzero == 1 || nonzero == 0 ? bitwidth
+ : bitwidth - floor_log2 (nonzero) - 1);
+ }
+
+ num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
+ known_x, known_mode, known_ret);
+ num1 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
+ known_x, known_mode, known_ret);
+ result = MAX (1, MIN (num0, num1) - 1);
+
+#ifdef POINTERS_EXTEND_UNSIGNED
+ /* If pointers extend signed and this is an addition or subtraction
+ to a pointer in Pmode, all the bits above ptr_mode are known to be
+ sign bit copies. */
+ if (! POINTERS_EXTEND_UNSIGNED && GET_MODE (x) == Pmode
+ && (code == PLUS || code == MINUS)
+ && REG_P (XEXP (x, 0)) && REG_POINTER (XEXP (x, 0)))
+ result = MAX ((int) (GET_MODE_BITSIZE (Pmode)
+ - GET_MODE_BITSIZE (ptr_mode) + 1),
+ result);
+#endif
+ return result;
+
+ case MULT:
+ /* The number of bits of the product is the sum of the number of
+ bits of both terms. However, unless one of the terms if known
+ to be positive, we must allow for an additional bit since negating
+ a negative number can remove one sign bit copy. */
+
+ num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
+ known_x, known_mode, known_ret);
+ num1 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
+ known_x, known_mode, known_ret);
+
+ result = bitwidth - (bitwidth - num0) - (bitwidth - num1);
+ if (result > 0
+ && (bitwidth > HOST_BITS_PER_WIDE_INT
+ || (((nonzero_bits (XEXP (x, 0), mode)
+ & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)
+ && ((nonzero_bits (XEXP (x, 1), mode)
+ & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0))))
+ result--;
+
+ return MAX (1, result);
+
+ case UDIV:
+ /* The result must be <= the first operand. If the first operand
+ has the high bit set, we know nothing about the number of sign
+ bit copies. */
+ if (bitwidth > HOST_BITS_PER_WIDE_INT)
return 1;
- }
- return 0;
-}
+ else if ((nonzero_bits (XEXP (x, 0), mode)
+ & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)
+ return 1;
+ else
+ return cached_num_sign_bit_copies (XEXP (x, 0), mode,
+ known_x, known_mode, known_ret);
-/* Traverse X via depth-first search, calling F for each
- sub-expression (including X itself). F is also passed the DATA.
- If F returns -1, do not traverse sub-expressions, but continue
- traversing the rest of the tree. If F ever returns any other
- non-zero value, stop the traversal, and return the value returned
- by F. Otherwise, return 0. This function does not traverse inside
- tree structure that contains RTX_EXPRs, or into sub-expressions
- whose format code is `0' since it is not known whether or not those
- codes are actually RTL.
+ case UMOD:
+ /* The result must be <= the second operand. */
+ return cached_num_sign_bit_copies (XEXP (x, 1), mode,
+ known_x, known_mode, known_ret);
- This routine is very general, and could (should?) be used to
- implement many of the other routines in this file. */
+ case DIV:
+ /* Similar to unsigned division, except that we have to worry about
+ the case where the divisor is negative, in which case we have
+ to add 1. */
+ result = cached_num_sign_bit_copies (XEXP (x, 0), mode,
+ known_x, known_mode, known_ret);
+ if (result > 1
+ && (bitwidth > HOST_BITS_PER_WIDE_INT
+ || (nonzero_bits (XEXP (x, 1), mode)
+ & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0))
+ result--;
+
+ return result;
-int for_each_rtx (x, f, data)
- rtx* x;
- rtx_function f;
- void* data;
-{
- int result;
- int length;
- char* format;
- int i;
+ case MOD:
+ result = cached_num_sign_bit_copies (XEXP (x, 1), mode,
+ known_x, known_mode, known_ret);
+ if (result > 1
+ && (bitwidth > HOST_BITS_PER_WIDE_INT
+ || (nonzero_bits (XEXP (x, 1), mode)
+ & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0))
+ result--;
+
+ return result;
+
+ case ASHIFTRT:
+ /* Shifts by a constant add to the number of bits equal to the
+ sign bit. */
+ num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
+ known_x, known_mode, known_ret);
+ if (GET_CODE (XEXP (x, 1)) == CONST_INT
+ && INTVAL (XEXP (x, 1)) > 0)
+ num0 = MIN ((int) bitwidth, num0 + INTVAL (XEXP (x, 1)));
+
+ return num0;
+
+ case ASHIFT:
+ /* Left shifts destroy copies. */
+ if (GET_CODE (XEXP (x, 1)) != CONST_INT
+ || INTVAL (XEXP (x, 1)) < 0
+ || INTVAL (XEXP (x, 1)) >= (int) bitwidth)
+ return 1;
- /* Call F on X. */
- result = (*f)(x, data);
- if (result == -1)
- /* Do not traverse sub-expressions. */
- return 0;
- else if (result != 0)
- /* Stop the traversal. */
- return result;
+ num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
+ known_x, known_mode, known_ret);
+ return MAX (1, num0 - INTVAL (XEXP (x, 1)));
- if (*x == NULL_RTX)
- /* There are no sub-expressions. */
- return 0;
+ case IF_THEN_ELSE:
+ num0 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
+ known_x, known_mode, known_ret);
+ num1 = cached_num_sign_bit_copies (XEXP (x, 2), mode,
+ known_x, known_mode, known_ret);
+ return MIN (num0, num1);
+
+ case EQ: case NE: case GE: case GT: case LE: case LT:
+ case UNEQ: case LTGT: case UNGE: case UNGT: case UNLE: case UNLT:
+ case GEU: case GTU: case LEU: case LTU:
+ case UNORDERED: case ORDERED:
+ /* If the constant is negative, take its 1's complement and remask.
+ Then see how many zero bits we have. */
+ nonzero = STORE_FLAG_VALUE;
+ if (bitwidth <= HOST_BITS_PER_WIDE_INT
+ && (nonzero & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)
+ nonzero = (~nonzero) & GET_MODE_MASK (mode);
+
+ return (nonzero == 0 ? bitwidth : bitwidth - floor_log2 (nonzero) - 1);
- length = GET_RTX_LENGTH (GET_CODE (*x));
- format = GET_RTX_FORMAT (GET_CODE (*x));
+ default:
+ break;
+ }
+
+ /* If we haven't been able to figure it out by one of the above rules,
+ see if some of the high-order bits are known to be zero. If so,
+ count those bits and return one less than that amount. If we can't
+ safely compute the mask for this mode, always return BITWIDTH. */
+
+ bitwidth = GET_MODE_BITSIZE (mode);
+ if (bitwidth > HOST_BITS_PER_WIDE_INT)
+ return 1;
+
+ nonzero = nonzero_bits (x, mode);
+ return nonzero & ((HOST_WIDE_INT) 1 << (bitwidth - 1))
+ ? 1 : bitwidth - floor_log2 (nonzero) - 1;
+}
+
+/* Calculate the rtx_cost of a single instruction. A return value of
+ zero indicates an instruction pattern without a known cost. */
+
+int
+insn_rtx_cost (rtx pat)
+{
+ int i, cost;
+ rtx set;
- for (i = 0; i < length; ++i)
+ /* Extract the single set rtx from the instruction pattern.
+ We can't use single_set since we only have the pattern. */
+ if (GET_CODE (pat) == SET)
+ set = pat;
+ else if (GET_CODE (pat) == PARALLEL)
{
- switch (format[i])
+ set = NULL_RTX;
+ for (i = 0; i < XVECLEN (pat, 0); i++)
{
- case 'e':
- result = for_each_rtx (&XEXP (*x, i), f, data);
- if (result != 0)
- return result;
- break;
-
- case 'V':
- case 'E':
- if (XVEC (*x, i) != 0)
+ rtx x = XVECEXP (pat, 0, i);
+ if (GET_CODE (x) == SET)
{
- int j;
- for (j = 0; j < XVECLEN (*x, i); ++j)
- {
- result = for_each_rtx (&XVECEXP (*x, i, j), f, data);
- if (result != 0)
- return result;
- }
+ if (set)
+ return 0;
+ set = x;
}
- break;
-
- default:
- /* Nothing to do. */
- break;
}
-
+ if (!set)
+ return 0;
}
+ else
+ return 0;
- return 0;
+ cost = rtx_cost (SET_SRC (set), SET);
+ return cost > 0 ? cost : COSTS_N_INSNS (1);
}