+
+/* Return true if we should avoid inserting code between INSN and preceding
+ call instruction. */
+
+bool
+keep_with_call_p (rtx insn)
+{
+ rtx set;
+
+ if (INSN_P (insn) && (set = single_set (insn)) != NULL)
+ {
+ 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;
+}
+
+/* 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. */
+
+static bool
+hoist_test_store (rtx x, rtx val, regset live)
+{
+ if (GET_CODE (x) == SCRATCH)
+ return true;
+
+ 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);
+
+ /* Anything except register store is not hoistable. This includes the
+ partial stores to registers. */
+
+ 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;
+}
+
+
+/* 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)
+{
+ rtx pat = PATTERN (insn);
+ int i;
+
+ /* 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 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:
+ 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;
+}
+
+/* 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. */
+
+static void
+hoist_update_store (rtx insn, rtx *xp, rtx val, rtx new)
+{
+ rtx x = *xp;
+
+ 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;
+ }
+
+ gcc_assert (REG_P (x));
+
+ /* 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));
+}
+
+/* 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. */
+
+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)
+{
+ rtx new_insn;
+
+ /* 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)
+ {
+ 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);
+
+ e->insns.r = get_insns ();
+ end_sequence ();
+ return new_insn;
+}
+
+/* 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. */
+
+bool
+label_is_jump_target_p (rtx label, rtx jump_insn)
+{
+ rtx tmp = JUMP_LABEL (jump_insn);
+
+ if (label == tmp)
+ return true;
+
+ 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);
+
+ for (i = 0; i < veclen; ++i)
+ if (XEXP (RTVEC_ELT (vec, i), 0) == label)
+ return true;
+ }
+
+ return false;
+}
+
+\f
+/* 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
+rtx_cost (rtx x, enum rtx_code outer_code ATTRIBUTE_UNUSED)
+{
+ int i, j;
+ enum rtx_code code;
+ 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)
+ {
+ case MULT:
+ total = COSTS_N_INSNS (5);
+ break;
+ case DIV:
+ case UDIV:
+ case MOD:
+ case UMOD:
+ 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);
+ }
+
+ 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:
+ 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')
+ 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 cost of address expression X.
+ Expect that X is properly formed address reference. */
+
+int
+address_cost (rtx x, enum machine_mode mode)
+{
+ /* 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. */
+
+ if (!memory_address_p (mode, x))
+ return 1000;
+
+ return targetm.address_cost (x);
+}
+
+/* If the target doesn't override, compute the cost as with arithmetic. */
+
+int
+default_address_cost (rtx x)
+{
+ return rtx_cost (x, MEM);
+}
+\f
+
+unsigned HOST_WIDE_INT
+nonzero_bits (rtx x, enum machine_mode mode)
+{
+ return cached_nonzero_bits (x, mode, NULL_RTX, VOIDmode, 0);
+}
+
+unsigned int
+num_sign_bit_copies (rtx x, enum machine_mode mode)
+{
+ return cached_num_sign_bit_copies (x, mode, NULL_RTX, VOIDmode, 0);
+}
+
+/* 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. */
+
+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;
+
+ /* 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. */
+
+ if (ARITHMETIC_P (x))
+ {
+ 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 nonzero_bits1 (x, mode, known_x, known_mode, known_ret);
+}
+
+/* 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 (result_width < mode_width)
+ nonzero &= ((HOST_WIDE_INT) 1 << result_width) - 1;
+
+ if (result_low > 0)
+ nonzero &= ~(((HOST_WIDE_INT) 1 << result_low) - 1);
+
+#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;
+
+ 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 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))
+ {
+ 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))));
+ }
+ }
+ break;
+
+ 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)
+ {
+ 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)
+ {
+ 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 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;
+
+ 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;
+
+ default:
+ break;
+ }
+
+ 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))
+ {
+ 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 num_sign_bit_copies1 (x, mode, known_x, known_mode, known_ret);
+}
+
+/* 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 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);
+ unsigned int bitwidth = GET_MODE_BITSIZE (mode);
+ int num0, num1, result;
+ unsigned HOST_WIDE_INT nonzero;
+
+ /* 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)))
+ {
+ 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));
+ }
+
+ 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
+ }
+
+ switch (code)
+ {
+ case REG:
+
+#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
+
+ {
+ 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);
+
+ if (new)
+ copies = cached_num_sign_bit_copies (new, mode, known_x,
+ known_mode, known_ret);
+
+ if (copies > 1 || copies_for_hook > 1)
+ return MAX (copies, copies_for_hook);
+
+ /* Else, use nonzero_bits to guess num_sign_bit_copies (see below). */
+ }
+ break;
+
+ 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;
+
+ 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);
+
+ return (nonzero == 0 ? bitwidth : bitwidth - floor_log2 (nonzero) - 1);
+
+ 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 (SUBREG_PROMOTED_VAR_P (x) && ! SUBREG_PROMOTED_UNSIGNED_P (x))
+ {
+ 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 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)));
+ }
+
+#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))));
+ }
+ 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;
+ 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);
+
+ 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);
+
+ 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;
+
+ 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;
+
+ num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
+ known_x, known_mode, known_ret);
+ return MAX (1, num0 - INTVAL (XEXP (x, 1)));
+
+ 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);
+
+ 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;
+
+ /* 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)
+ {
+ set = NULL_RTX;
+ for (i = 0; i < XVECLEN (pat, 0); i++)
+ {
+ rtx x = XVECEXP (pat, 0, i);
+ if (GET_CODE (x) == SET)
+ {
+ if (set)
+ return 0;
+ set = x;
+ }
+ }
+ if (!set)
+ return 0;
+ }
+ else
+ return 0;
+
+ cost = rtx_cost (SET_SRC (set), SET);
+ return cost > 0 ? cost : COSTS_N_INSNS (1);
+}