FWIW, here's a work-in-progress patch. It takes the current
optabs handling of doubleword shifts by constants and generalises
it to handle variable shifts as well. I've tried to take advantage
of SHIFT_COUNT_TRUNCATED where possible.
Unfortunately, I'm not sure whether the code is good enough in the
!SHIFT_COUNT_TRUNCATED case. E.g. ARM has special asm versions of
64-bit shifts, and it takes advantage of the fact that word shifts by
32 bits or more will set the result to 0 (ashl or lshr) or -1 (ashr).
We can't do that in optabs.c since !SHIFT_COUNT_TRUNCATED dosn't mean
that shifts _aren't_ truncated, it simply means that the behaviour of
out-of-range shifts is undefined.
I've checked that the new open-coded variable shifts do work on ARM,
but perhaps they should be disabled on !SHIFT_COUNT_TRUNCATED targets,
at least for now.
Anyway, the SHIFT_COUNT_TRUNCATED version produces MIPS sequences
that are the same length as Maciej's asm versions (assuming conditional
moves are available). They should take 5 cycles on a typical 2-way
superscalar target.
I've bootstrapped & regression tested the patch on mips-sgi-irix6.5 but
it's not really ready for approval yet. Just posting for info & comments.
Of course, this doesn't let linux off the hook. It still needs to define
the libgcc shift functions if it wants to support -Os compilation.
Richard
* optabs.c (simplify_expand_binop, expand_superword_shift)
(expand_subword_shift, expand_doubleword_shift): New functions.
Generalize expand_binop's handling of doubleword shifts so that
it can cope with non-constant shift amounts.
(expand_binop): Replace said handling with expand_doubleword_shift.
Index: optabs.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/optabs.c,v
retrieving revision 1.231
diff -c -p -F^\([(a-zA-Z0-9_]\|#define\) -r1.231 optabs.c
*** optabs.c 22 Jul 2004 08:20:35 -0000 1.231
--- optabs.c 7 Aug 2004 07:14:19 -0000
*************** optab_for_tree_code (enum tree_code code
*** 709,715 ****
--- 709,981 ----
return NULL;
}
}
+
+ /* Like expand_binop, but return a constant rtx if the result can be
+ calculated at compile time. The arguments and return value are
+ otherwise the same as for expand_binop. */
+
+ static rtx
+ simplify_expand_binop (enum machine_mode mode, optab binoptab,
+ rtx op0, rtx op1, rtx target, int unsignedp,
+ enum optab_methods methods)
+ {
+ if (CONSTANT_P (op0) && CONSTANT_P (op1))
+ return simplify_gen_binary (binoptab->code, mode, op0, op1);
+ else
+ return expand_binop (mode, binoptab, op0, op1, target, unsignedp, methods);
+ }
+ /* This subroutine of expand_doubleword_shift handles the cases in which
+ the effective shift value is >= BITS_PER_WORD. The arguments and return
+ value are the same as for the parent routine. */
+
+ static bool
+ expand_superword_shift (enum machine_mode op1_mode, optab binoptab,
+ rtx outof_input, rtx op1,
+ rtx outof_target, rtx into_target,
+ int unsignedp, enum optab_methods methods)
+ {
+ rtx tmp;
+
+ /* If shifts aren't truncated, we should shift OUTOF_INPUT by
+ (OP1 - BITS_PER_WORD) bits and store the result in INTO_TARGET.
+ If shifts are truncated, we can just shift by OP1 itself . */
+ if (SHIFT_COUNT_TRUNCATED && !CONSTANT_P (op1))
+ tmp = op1;
+ else
+ {
+ tmp = immed_double_const (BITS_PER_WORD, 0, op1_mode);
+ tmp = simplify_expand_binop (op1_mode, sub_optab, op1, tmp,
+ 0, true, methods);
+ if (tmp == 0)
+ return false;
+ }
+ tmp = expand_binop (word_mode, binoptab, outof_input, tmp,
+ into_target, unsignedp, methods);
+ if (tmp == 0)
+ return false;
+ if (tmp != into_target)
+ emit_move_insn (into_target, tmp);
+
+ /* For a signed right shift, we must fill OUTOF_TARGET with copies
+ of the sign bit, otherwise we must fill it with zeros. */
+ if (binoptab != ashr_optab)
+ tmp = CONST0_RTX (word_mode);
+ else
+ {
+ tmp = expand_binop (word_mode, binoptab,
+ outof_input, GEN_INT (BITS_PER_WORD - 1),
+ outof_target, unsignedp, methods);
+ if (tmp == 0)
+ return false;
+ }
+ if (tmp != outof_target)
+ emit_move_insn (outof_target, tmp);
+
+ return true;
+ }
+
+ /* This subroutine of expand_doubleword_shift handles the cases in which
+ the effective shift value is < BITS_PER_WORD. The arguments and return
+ value are the same as for the parent routine. */
+
+ static bool
+ expand_subword_shift (enum machine_mode op1_mode, optab binoptab,
+ rtx outof_input, rtx into_input, rtx op1,
+ rtx outof_target, rtx into_target,
+ int unsignedp, enum optab_methods methods)
+ {
+ optab reverse_unsigned_shift, unsigned_shift;
+ rtx tmp, carries;
+
+ reverse_unsigned_shift = (binoptab == ashl_optab ? lshr_optab : ashl_optab);
+ unsigned_shift = (binoptab == ashl_optab ? ashl_optab : lshr_optab);
+
+ /* The low OP1 bits of INTO_TARGET come from the high bits of OUTOF_INPUT.
+ We therefore need to shift OUTOF_INPUT by (BITS_PER_WORD - OP1) bits in
+ the opposite direction to BINOPTAB. */
+ if (GET_CODE (op1) != CONST_INT || INTVAL (op1) == 0)
+ {
+ /* We must avoid shifting by BITS_PER_WORD bits since that is
+ either the same as a zero shift (if SHIFT_COUNT_TRUNCATED)
+ or has undefined RTL semantics. Do a single shift first,
+ then shift by the remainder. It's OK to use ~OP1 as the
+ remainder if shift counts are truncated. */
+ carries = expand_binop (word_mode, reverse_unsigned_shift,
+ outof_input, const1_rtx, 0, unsignedp, methods);
+ if (SHIFT_COUNT_TRUNCATED && !CONSTANT_P (op1))
+ {
+ tmp = immed_double_const (-1, -1, op1_mode);
+ tmp = simplify_expand_binop (op1_mode, xor_optab, op1, tmp,
+ 0, true, methods);
+ }
+ else
+ {
+ tmp = immed_double_const (BITS_PER_WORD - 1, 0, op1_mode);
+ tmp = simplify_expand_binop (op1_mode, sub_optab, tmp, op1,
+ 0, true, methods);
+ }
+ }
+ else
+ {
+ carries = outof_input;
+ tmp = immed_double_const (BITS_PER_WORD, 0, op1_mode);
+ tmp = simplify_expand_binop (op1_mode, sub_optab, tmp, op1,
+ 0, true, methods);
+ }
+ if (tmp == 0 || carries == 0)
+ return false;
+ carries = expand_binop (word_mode, reverse_unsigned_shift,
+ carries, tmp, 0, unsignedp, methods);
+ if (carries == 0)
+ return false;
+
+ /* Shift INTO_INPUT logically by OP1 bits... */
+ tmp = expand_binop (word_mode, unsigned_shift, into_input, op1,
+ 0, unsignedp, methods);
+ if (tmp == 0)
+ return false;
+
+ /* ...and OR in the bits carried over from OUTOF_INPUT. */
+ tmp = expand_binop (word_mode, ior_optab, carries, tmp,
+ into_target, unsignedp, methods);
+ if (tmp == 0)
+ return false;
+ if (tmp != into_target)
+ emit_move_insn (into_target, tmp);
+
+ /* Use a standard word_mode shift for the out-of half. */
+ tmp = expand_binop (word_mode, binoptab, outof_input, op1,
+ outof_target, unsignedp, methods);
+ if (tmp == 0)
+ return false;
+ if (tmp != outof_target)
+ emit_move_insn (outof_target, tmp);
+
+ return true;
+ }
+
+ /* Expand a doubleword shift (ashl, ashr or lshr) using word-mode shifts.
+ OUTOF_INPUT is the input word that we are shifting away from and
+ INTO_INPUT is the word that we are shifting towards. OUTOF_TARGET
+ and INTO_TARGET specify the equivalent words of the output. OP1 is
+ the shift amount, which has mode OP1_MODE. BINOPTAB, UNSIGNEDP and
+ METHODS are as for expand_binop.
+
+ This function must not assign to OUTOF_TARGET or INTO_TARGET
+ until it has completely finished with the input operands.
+
+ Return true if the shift could be successfully synthesized. */
+
+ static bool
+ expand_doubleword_shift (enum machine_mode op1_mode, optab binoptab,
+ rtx outof_input, rtx into_input, rtx op1,
+ rtx outof_target, rtx into_target,
+ int unsignedp, enum optab_methods methods)
+ {
+ rtx tmp, cmp1, cmp2;
+ rtx subword_label, done_label;
+ #ifdef HAVE_conditional_move
+ rtx start, outof_superword, into_superword;
+ #endif
+ enum rtx_code cmp_code;
+
+ /* Set CMP_CODE, CMP1 and CMP2 so that the rtx (CMP_CODE CMP1 CMP2)
+ is true when the effective shift value is less than BITS_PER_WORD. */
+ tmp = immed_double_const (BITS_PER_WORD, 0, op1_mode);
+ if (SHIFT_COUNT_TRUNCATED)
+ {
+ cmp1 = simplify_expand_binop (op1_mode, and_optab,
+ op1, tmp, 0, true, methods);
+ cmp2 = const0_rtx;
+ cmp_code = EQ;
+ if (cmp1 == 0)
+ return false;
+ }
+ else
+ {
+ cmp1 = op1;
+ cmp2 = tmp;
+ cmp_code = LT;
+ }
+
+ /* If we can compute the condition at compile time, pick the
+ appropriate subroutine. */
+ tmp = simplify_relational_operation (cmp_code, SImode, op1_mode, cmp1, cmp2);
+ if (tmp != 0 && GET_CODE (tmp) == CONST_INT)
+ {
+ if (tmp == const0_rtx)
+ return expand_superword_shift (op1_mode, binoptab,
+ outof_input, op1,
+ outof_target, into_target,
+ unsignedp, methods);
+ else
+ return expand_subword_shift (op1_mode, binoptab,
+ outof_input, into_input, op1,
+ outof_target, into_target,
+ unsignedp, methods);
+ }
+
+ #ifdef HAVE_conditional_move
+ /* Try using conditional moves to select between the subword and
+ superword forms. Do the superword version first, putting the
+ result into a temporary comprised of OUTOF_SUPERWORD and
+ INTO_SUPERWORD. Then do the subword version and store it
+ directly into the final output.
+
+ Note that OUTOF_TARGET and INTO_SUPERWORD are both equal to
+ (shift OUTOF_INPUT OP1) when shift counts are truncated. */
+ outof_superword = gen_reg_rtx (word_mode);
+ into_superword = gen_reg_rtx (word_mode);
+
+ start = get_last_insn ();
+ if (expand_superword_shift (op1_mode, binoptab,
+ outof_input, op1,
+ outof_superword, into_superword,
+ unsignedp, methods)
+ && expand_subword_shift (op1_mode, binoptab,
+ outof_input, into_input, op1,
+ outof_target, into_target,
+ unsignedp, methods)
+ && emit_conditional_move (into_target, cmp_code, cmp1, cmp2, op1_mode,
+ into_target, (SHIFT_COUNT_TRUNCATED
+ ? outof_target
+ : into_superword),
+ word_mode, unsignedp)
+ && emit_conditional_move (outof_target, cmp_code, cmp1, cmp2, op1_mode,
+ outof_target, outof_superword, word_mode,
+ unsignedp))
+ return true;
+
+ delete_insns_since (start);
+ #endif
+
+ /* As a last resort, use branches to select the correct alternative. */
+ subword_label = gen_label_rtx ();
+ done_label = gen_label_rtx ();
+
+ do_compare_rtx_and_jump (cmp1, cmp2, cmp_code, true, op1_mode,
+ 0, 0, subword_label);
+
+ if (!expand_superword_shift (op1_mode, binoptab,
+ outof_input, op1,
+ outof_target, into_target,
+ unsignedp, methods))
+ return false;
+
+ emit_jump_insn (gen_jump (done_label));
+ emit_barrier ();
+ emit_label (subword_label);
+
+ if (!expand_subword_shift (op1_mode, binoptab,
+ outof_input, into_input, op1,
+ outof_target, into_target,
+ unsignedp, methods))
+ return false;
+
+ emit_label (done_label);
+ return true;
+ }
/* Wrapper around expand_binop which takes an rtx code to specify
the operation to perform, not an optab pointer. All other
*************** expand_binop (enum machine_mode mode, op
*** 1035,1050 ****
if ((binoptab == lshr_optab || binoptab == ashl_optab
|| binoptab == ashr_optab)
&& class == MODE_INT
! && GET_CODE (op1) == CONST_INT
&& GET_MODE_SIZE (mode) == 2 * UNITS_PER_WORD
&& binoptab->handlers[(int) word_mode].insn_code != CODE_FOR_nothing
&& ashl_optab->handlers[(int) word_mode].insn_code != CODE_FOR_nothing
&& lshr_optab->handlers[(int) word_mode].insn_code != CODE_FOR_nothing)
{
! rtx insns, inter, equiv_value;
rtx into_target, outof_target;
rtx into_input, outof_input;
! int shift_count, left_shift, outof_word;
/* If TARGET is the same as one of the operands, the REG_EQUAL note
won't be accurate, so use a new target. */
--- 1301,1317 ----
if ((binoptab == lshr_optab || binoptab == ashl_optab
|| binoptab == ashr_optab)
&& class == MODE_INT
! && (GET_CODE (op1) == CONST_INT || !optimize_size)
&& GET_MODE_SIZE (mode) == 2 * UNITS_PER_WORD
&& binoptab->handlers[(int) word_mode].insn_code != CODE_FOR_nothing
&& ashl_optab->handlers[(int) word_mode].insn_code != CODE_FOR_nothing
&& lshr_optab->handlers[(int) word_mode].insn_code != CODE_FOR_nothing)
{
! rtx insns, equiv_value;
rtx into_target, outof_target;
rtx into_input, outof_input;
! enum machine_mode op1_mode;
! int left_shift, outof_word;
/* If TARGET is the same as one of the operands, the REG_EQUAL note
won't be accurate, so use a new target. */
*************** expand_binop (enum machine_mode mode, op
*** 1053,1059 ****
start_sequence ();
! shift_count = INTVAL (op1);
/* OUTOF_* is the word we are shifting bits away from, and
INTO_* is the word that we are shifting bits towards, thus
--- 1320,1326 ----
start_sequence ();
! op1_mode = GET_MODE (op1) != VOIDmode ? GET_MODE (op1) : word_mode;
/* OUTOF_* is the word we are shifting bits away from, and
INTO_* is the word that we are shifting bits towards, thus
*************** expand_binop (enum machine_mode mode, op
*** 1069,1145 ****
outof_input = operand_subword_force (op0, outof_word, mode);
into_input = operand_subword_force (op0, 1 - outof_word, mode);
! if (shift_count >= BITS_PER_WORD)
! {
! inter = expand_binop (word_mode, binoptab,
! outof_input,
! GEN_INT (shift_count - BITS_PER_WORD),
! into_target, unsignedp, next_methods);
!
! if (inter != 0 && inter != into_target)
! emit_move_insn (into_target, inter);
!
! /* For a signed right shift, we must fill the word we are shifting
! out of with copies of the sign bit. Otherwise it is zeroed. */
! if (inter != 0 && binoptab != ashr_optab)
! inter = CONST0_RTX (word_mode);
! else if (inter != 0)
! inter = expand_binop (word_mode, binoptab,
! outof_input,
! GEN_INT (BITS_PER_WORD - 1),
! outof_target, unsignedp, next_methods);
!
! if (inter != 0 && inter != outof_target)
! emit_move_insn (outof_target, inter);
! }
! else
{
! rtx carries;
! optab reverse_unsigned_shift, unsigned_shift;
!
! /* For a shift of less then BITS_PER_WORD, to compute the carry,
! we must do a logical shift in the opposite direction of the
! desired shift. */
!
! reverse_unsigned_shift = (left_shift ? lshr_optab : ashl_optab);
!
! /* For a shift of less than BITS_PER_WORD, to compute the word
! shifted towards, we need to unsigned shift the orig value of
! that word. */
!
! unsigned_shift = (left_shift ? ashl_optab : lshr_optab);
!
! carries = expand_binop (word_mode, reverse_unsigned_shift,
! outof_input,
! GEN_INT (BITS_PER_WORD - shift_count),
! 0, unsignedp, next_methods);
- if (carries == 0)
- inter = 0;
- else
- inter = expand_binop (word_mode, unsigned_shift, into_input,
- op1, 0, unsignedp, next_methods);
-
- if (inter != 0)
- inter = expand_binop (word_mode, ior_optab, carries, inter,
- into_target, unsignedp, next_methods);
-
- if (inter != 0 && inter != into_target)
- emit_move_insn (into_target, inter);
-
- if (inter != 0)
- inter = expand_binop (word_mode, binoptab, outof_input,
- op1, outof_target, unsignedp, next_methods);
-
- if (inter != 0 && inter != outof_target)
- emit_move_insn (outof_target, inter);
- }
-
- insns = get_insns ();
- end_sequence ();
-
- if (inter != 0)
- {
if (binoptab->code != UNKNOWN)
equiv_value = gen_rtx_fmt_ee (binoptab->code, mode, op0, op1);
else
--- 1336,1349 ----
outof_input = operand_subword_force (op0, outof_word, mode);
into_input = operand_subword_force (op0, 1 - outof_word, mode);
! if (expand_doubleword_shift (op1_mode, binoptab,
! outof_input, into_input, op1,
! outof_target, into_target,
! unsignedp, methods))
{
! insns = get_insns ();
! end_sequence ();
if (binoptab->code != UNKNOWN)
equiv_value = gen_rtx_fmt_ee (binoptab->code, mode, op0, op1);
else
*************** expand_binop (enum machine_mode mode, op
*** 1148,1153 ****
--- 1352,1358 ----
emit_no_conflict_block (insns, target, op0, op1, equiv_value);
return target;
}
+ end_sequence ();
}
/* Synthesize double word rotates from single word shifts. */
