This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
PR 17886
- From: Mark Mitchell <mark at codesourcery dot com>
- To: gcc-patches at gcc dot gnu dot org
- Cc: rth at redhat dot com
- Date: Wed, 28 Sep 2005 15:07:58 -0700
- Subject: PR 17886
- Reply-to: mark at codesourcery dot com
This patch improves handling of rotations of 64-bit values by
constants on IA32. For example, consider:
unsigned long long f(unsigned long long x)
{
enum { y = 55 };
return (x << y) | (x >> (64 - y));
}
Without the patch, we get the following code with -O2 -fomit-frame-pointer:
subl $12, %esp
movl 20(%esp), %edx
movl 16(%esp), %eax
movl %edi, 8(%esp)
movl %ebx, (%esp)
movl %esi, 4(%esp)
movl %edx, %edi
movl %eax, %ebx
movl %eax, %esi
sall $23, %edi
shrl $9, %ebx
sall $23, %esi
movl %edi, %eax
movl %edx, %ecx
movl 8(%esp), %edi
orl %ebx, %eax
movl %esi, %edx
movl (%esp), %ebx
movl 4(%esp), %esi
shrl $9, %ecx
addl $12, %esp
orl %ecx, %edx
ret
With the patch, we get:
movl 4(%esp), %eax
movl 8(%esp), %edx
movl %eax, %ecx
shrdl $9, %edx, %eax
shrdl $9, %ecx, %edx
ret
The point of the change to expmed.c/optabs.c is that, without the
patch, we notice in expand_shift that rotation in one direction has
failed and try rotation in the other direction. However, expand_binop
outwits us -- it synthesizes rotation in the first direction with
shifts and ors. So, we really need expand_binop to try the
counter-rotation itself.
Thanks to Richard Sandiford and Kazu Hirata who helped me develop the
patch.
OK?
--
Mark Mitchell
CodeSourcery, LLC
mark@codesourcery.com
2005-09-28 Mark Mitchell <mark@codesourcery.com>
PR 17886
* expmed.c (expand_shift): Move logic to reverse rotation
direction when rotating by constants ...
* optabs.c (expand_binop): ... here.
* config/i386/i386.md (rotrdi3): Handle 32-bit mode.
(ix86_rotrdi3): New pattern.
(rotldi3): Handle 32-bit mode.
(ix86_rotldi3): New pattern.
Index: gcc/config/i386/i386.md
===================================================================
RCS file: /cvs/gcc/gcc/gcc/config/i386/i386.md,v
retrieving revision 1.656
diff -c -5 -p -r1.656 i386.md
*** gcc/config/i386/i386.md 26 Sep 2005 17:21:00 -0000 1.656
--- gcc/config/i386/i386.md 28 Sep 2005 21:57:03 -0000
***************
*** 12002,12018 ****
(set_attr "mode" "QI")])
;; Rotate instructions
(define_expand "rotldi3"
! [(set (match_operand:DI 0 "nonimmediate_operand" "")
! (rotate:DI (match_operand:DI 1 "nonimmediate_operand" "")
(match_operand:QI 2 "nonmemory_operand" "")))
(clobber (reg:CC FLAGS_REG))]
! "TARGET_64BIT"
! "ix86_expand_binary_operator (ROTATE, DImode, operands); DONE;")
(define_insn "*rotlsi3_1_one_bit_rex64"
[(set (match_operand:DI 0 "nonimmediate_operand" "=rm")
(rotate:DI (match_operand:DI 1 "nonimmediate_operand" "0")
(match_operand:QI 2 "const1_operand" "")))
(clobber (reg:CC FLAGS_REG))]
--- 12002,12054 ----
(set_attr "mode" "QI")])
;; Rotate instructions
(define_expand "rotldi3"
! [(set (match_operand:DI 0 "shiftdi_operand" "")
! (rotate:DI (match_operand:DI 1 "shiftdi_operand" "")
(match_operand:QI 2 "nonmemory_operand" "")))
(clobber (reg:CC FLAGS_REG))]
! ""
! {
! if (TARGET_64BIT)
! {
! ix86_expand_binary_operator (ROTATE, DImode, operands);
! DONE;
! }
! if (!const_1_to_31_operand (operands[2], VOIDmode))
! FAIL;
! emit_insn (gen_ix86_rotldi3 (operands[0], operands[1], operands[2]));
! DONE;
! })
+ ;; Implement rotation using two double-precision shift instructions
+ ;; and a scratch register.
+ (define_insn_and_split "ix86_rotldi3"
+ [(set (match_operand:DI 0 "register_operand" "=r")
+ (rotate:DI (match_operand:DI 1 "register_operand" "0")
+ (match_operand:QI 2 "const_1_to_31_operand" "I")))
+ (clobber (reg:CC FLAGS_REG))
+ (clobber (match_scratch:SI 3 "=&r"))]
+ "!TARGET_64BIT"
+ ""
+ "&& reload_completed"
+ [(set (match_dup 3) (match_dup 4))
+ (parallel
+ [(set (match_dup 4)
+ (ior:SI (ashift:SI (match_dup 4) (match_dup 2))
+ (lshiftrt:SI (match_dup 5)
+ (minus:QI (const_int 32) (match_dup 2)))))
+ (clobber (reg:CC FLAGS_REG))])
+ (parallel
+ [(set (match_dup 5)
+ (ior:SI (ashift:SI (match_dup 5) (match_dup 2))
+ (lshiftrt:SI (match_dup 3)
+ (minus:QI (const_int 32) (match_dup 2)))))
+ (clobber (reg:CC FLAGS_REG))])]
+ "split_di (operands, 1, operands + 4, operands + 5);")
+
(define_insn "*rotlsi3_1_one_bit_rex64"
[(set (match_operand:DI 0 "nonimmediate_operand" "=rm")
(rotate:DI (match_operand:DI 1 "nonimmediate_operand" "0")
(match_operand:QI 2 "const1_operand" "")))
(clobber (reg:CC FLAGS_REG))]
***************
*** 12190,12205 ****
rol{b}\t{%b2, %0|%0, %b2}"
[(set_attr "type" "rotate")
(set_attr "mode" "QI")])
(define_expand "rotrdi3"
! [(set (match_operand:DI 0 "nonimmediate_operand" "")
! (rotatert:DI (match_operand:DI 1 "nonimmediate_operand" "")
! (match_operand:QI 2 "nonmemory_operand" "")))
(clobber (reg:CC FLAGS_REG))]
! "TARGET_64BIT"
! "ix86_expand_binary_operator (ROTATERT, DImode, operands); DONE;")
(define_insn "*rotrdi3_1_one_bit_rex64"
[(set (match_operand:DI 0 "nonimmediate_operand" "=rm")
(rotatert:DI (match_operand:DI 1 "nonimmediate_operand" "0")
(match_operand:QI 2 "const1_operand" "")))
--- 12226,12277 ----
rol{b}\t{%b2, %0|%0, %b2}"
[(set_attr "type" "rotate")
(set_attr "mode" "QI")])
(define_expand "rotrdi3"
! [(set (match_operand:DI 0 "shiftdi_operand" "")
! (rotate:DI (match_operand:DI 1 "shiftdi_operand" "")
! (match_operand:QI 2 "nonmemory_operand" "")))
(clobber (reg:CC FLAGS_REG))]
! ""
! {
! if (TARGET_64BIT)
! {
! ix86_expand_binary_operator (ROTATERT, DImode, operands);
! DONE;
! }
! if (!const_1_to_31_operand (operands[2], VOIDmode))
! FAIL;
! emit_insn (gen_ix86_rotrdi3 (operands[0], operands[1], operands[2]));
! DONE;
! })
!
! ;; Implement rotation using two double-precision shift instructions
! ;; and a scratch register.
! (define_insn_and_split "ix86_rotrdi3"
! [(set (match_operand:DI 0 "register_operand" "=r")
! (rotatert:DI (match_operand:DI 1 "register_operand" "0")
! (match_operand:QI 2 "const_1_to_31_operand" "I")))
! (clobber (reg:CC FLAGS_REG))
! (clobber (match_scratch:SI 3 "=&r"))]
! "!TARGET_64BIT"
! ""
! "&& reload_completed"
! [(set (match_dup 3) (match_dup 4))
! (parallel
! [(set (match_dup 4)
! (ior:SI (ashiftrt:SI (match_dup 4) (match_dup 2))
! (ashift:SI (match_dup 5)
! (minus:QI (const_int 32) (match_dup 2)))))
! (clobber (reg:CC FLAGS_REG))])
! (parallel
! [(set (match_dup 5)
! (ior:SI (ashiftrt:SI (match_dup 5) (match_dup 2))
! (ashift:SI (match_dup 3)
! (minus:QI (const_int 32) (match_dup 2)))))
! (clobber (reg:CC FLAGS_REG))])]
! "split_di (operands, 1, operands + 4, operands + 5);")
(define_insn "*rotrdi3_1_one_bit_rex64"
[(set (match_operand:DI 0 "nonimmediate_operand" "=rm")
(rotatert:DI (match_operand:DI 1 "nonimmediate_operand" "0")
(match_operand:QI 2 "const1_operand" "")))
Index: gcc/expmed.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/expmed.c,v
retrieving revision 1.236
diff -c -5 -p -r1.236 expmed.c
*** gcc/expmed.c 22 Sep 2005 14:45:25 -0000 1.236
--- gcc/expmed.c 28 Sep 2005 21:57:03 -0000
*************** expand_shift (enum tree_code code, enum
*** 2235,2257 ****
}
temp = expand_binop (mode,
left ? rotl_optab : rotr_optab,
shifted, op1, target, unsignedp, methods);
-
- /* If we don't have the rotate, but we are rotating by a constant
- that is in range, try a rotate in the opposite direction. */
-
- if (temp == 0 && GET_CODE (op1) == CONST_INT
- && INTVAL (op1) > 0
- && (unsigned int) INTVAL (op1) < GET_MODE_BITSIZE (mode))
- temp = expand_binop (mode,
- left ? rotr_optab : rotl_optab,
- shifted,
- GEN_INT (GET_MODE_BITSIZE (mode)
- - INTVAL (op1)),
- target, unsignedp, methods);
}
else if (unsignedp)
temp = expand_binop (mode,
left ? ashl_optab : lshr_optab,
shifted, op1, target, unsignedp, methods);
--- 2235,2244 ----
Index: gcc/optabs.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/optabs.c,v
retrieving revision 1.294
diff -c -5 -p -r1.294 optabs.c
*** gcc/optabs.c 27 Sep 2005 21:09:28 -0000 1.294
--- gcc/optabs.c 28 Sep 2005 21:57:03 -0000
*************** expand_binop (enum machine_mode mode, op
*** 1047,1056 ****
--- 1047,1057 ----
|| binoptab->code == LSHIFTRT
|| binoptab->code == ROTATE
|| binoptab->code == ROTATERT);
rtx entry_last = get_last_insn ();
rtx last;
+ bool first_pass_p;
class = GET_MODE_CLASS (mode);
/* If subtracting an integer constant, convert this into an addition of
the negated constant. */
*************** expand_binop (enum machine_mode mode, op
*** 1096,1105 ****
--- 1097,1108 ----
op1 = op0;
op0 = temp;
}
}
+ retry:
+
/* If we can do it with a three-operand insn, do so. */
if (methods != OPTAB_MUST_WIDEN
&& binoptab->handlers[(int) mode].insn_code != CODE_FOR_nothing)
{
*************** expand_binop (enum machine_mode mode, op
*** 1181,1190 ****
--- 1184,1209 ----
}
else
delete_insns_since (last);
}
+ /* If we were trying to rotate by a constant value, and that didn't
+ work, try rotating the other direction before falling back to
+ shifts and bitwise-or. */
+ if (first_pass_p
+ && (binoptab == rotl_optab || binoptab == rotr_optab)
+ && class == MODE_INT
+ && GET_CODE (op1) == CONST_INT
+ && INTVAL (op1) > 0
+ && (unsigned int) INTVAL (op1) < GET_MODE_BITSIZE (mode))
+ {
+ first_pass_p = false;
+ op1 = GEN_INT (GET_MODE_BITSIZE (mode) - INTVAL (op1));
+ binoptab = binoptab == rotl_optab ? rotr_optab : rotl_optab;
+ goto retry;
+ }
+
/* If this is a multiply, see if we can do a widening operation that
takes operands of this mode and makes a wider mode. */
if (binoptab == smul_optab && GET_MODE_WIDER_MODE (mode) != VOIDmode
&& (((unsignedp ? umul_widen_optab : smul_widen_optab)