[X86] Prefer rotate by 1 over rotate by imm

[zvi]

Summary

Rotate by 1 is translated to 1 micro-op, while rotate with imm8 is translated to 2 micro-ops.

Fixes pr30644.

[craig.topper]

lib/Target/X86/X86InstrShiftRotate.td

612

Does rotr by 1 never get emitted or should we really have two patterns here?

[zvi]

lib/Target/X86/X86InstrShiftRotate.td

612

Note that for 8-bit operands:
rotate right by 1 is same as rotate left by 7.

It seems that the canonical form prefers the latter while the target prefers the former.

Does this answer your question, Craig?

[RKSimon]

test/CodeGen/X86/rotate.ll

2–217

We have a 64-bit triple and a 32-bit arch - this needs fixing and if possible test on both 32 and 64 bit targets.

If possible add i64 tests as well?

[zvi]

test/CodeGen/X86/rotate.ll

2–217

Good catch!
Will add the i64 tests.

[zvi]

Rebased on top of trunk after r283695 was comitted.

[zvi]

test/CodeGen/X86/rotate.ll

2–217

Fixed in r283695

[RKSimon]

Please can you confirm that the _lrotl/_lrotr intrinsics (I think they are only on clang-cl) can't create the removed rotr #1 pattern

[zvi]

In D25399#565597, @RKSimon wrote:

Please can you confirm that the _lrotl/_lrotr intrinsics (I think they are only on clang-cl) can't create the removed rotr #1 pattern

Seems like for 64-bit operand intrinsics we are not matching any rotate instructions:

unsigned long ltestl(unsigned long _Value) {
   return _lrotl(_Value, 1);
}
      leaq    (%rdi,%rdi), %rax
      shrq    $31, %rdi
      orq     %rdi, %rax
      retq


unsigned long ltestr(unsigned long _Value) {
  return _lrotr(_Value, 1);
}
      movq    %rdi, %rax
      shrq    %rax
      shlq    $31, %rdi
      orq     %rax, %rdi
      movq    %rdi, %rax
      retq

But the 32-bit operand flavors are matching rotate instructions (these are withour this patch):

unsigned long testl(unsigned long _Value) {
  return _rotl(_Value, 1);
}
      roll    %edi
      movq    %rdi, %rax
      retq


unsigned long testr(unsigned long _Value) {
  return _rotr(_Value, 1);
}
      roll    $31, %edi
      movq    %rdi, %rax
      retq

The 64-bit operand issue seems like out of scope of this patch, since the matching to ISD::ROTR/ROTL nodes happens in the target-independent phase of DagCombine. I will open a Bugzilla for this and will investigate it further.

[zvi]

Actually, the relevant 64-bit operand intrinsics are _rotl64 and _rotr64 for which the generated code without this patch is:

test_rotl64(unsigned long):                       # @test_rotl64(unsigned long)
      rolq    %rdi
      movq    %rdi, %rax
      retq

test_rotr64(unsigned long):                       # @test_rotr64(unsigned long)
      rolq    $63, %rdi
      movq    %rdi, %rax
      retq

[RKSimon]

Thanks for checking, LGTM

[Eugene.Zelenko]

Committed in rL283758.

lib/Target/X86/X86InstrShiftRotate.td

def ROR64ri  : RIi8<0xC1, MRM1r, (outs GR64:$dst),
                     (ins GR64:$src1, u8imm:$src2),
                     "ror{q}\t{$src2, $dst|$dst, $src2}",
                     [(set GR64:$dst, (rotr GR64:$src1, (i8 imm:$src2)))],
                     IIC_SR>;
 
 // Rotate by 1
 def ROR8r1   : I<0xD0, MRM1r, (outs GR8 :$dst), (ins GR8 :$src1),
                  "ror{b}\t$dst",
-                 [(set GR8:$dst, (rotr GR8:$src1, (i8 1)))],
+                 [(set GR8:$dst, (rotl GR8:$src1, (i8 7)))],
                  IIC_SR>;
 def ROR16r1  : I<0xD1, MRM1r, (outs GR16:$dst), (ins GR16:$src1),
                  "ror{w}\t$dst",
-                 [(set GR16:$dst, (rotr GR16:$src1, (i8 1)))],
+                 [(set GR16:$dst, (rotl GR16:$src1, (i8 15)))],
                  IIC_SR>, OpSize16;
 def ROR32r1  : I<0xD1, MRM1r, (outs GR32:$dst), (ins GR32:$src1),
                  "ror{l}\t$dst",
-                 [(set GR32:$dst, (rotr GR32:$src1, (i8 1)))],
+                 [(set GR32:$dst, (rotl GR32:$src1, (i8 31)))],
                  IIC_SR>, OpSize32;
 def ROR64r1  : RI<0xD1, MRM1r, (outs GR64:$dst), (ins GR64:$src1),
                   "ror{q}\t$dst",
-                  [(set GR64:$dst, (rotr GR64:$src1, (i8 1)))],
+                  [(set GR64:$dst, (rotl GR64:$src1, (i8 63)))],
                   IIC_SR>;
 } // Constraints = "$src = $dst", SchedRW
 
 let SchedRW = [WriteShiftLd, WriteRMW] in {
 let Uses = [CL] in {
 def ROR8mCL  : I<0xD2, MRM1m, (outs), (ins i8mem :$dst),
                  "ror{b}\t{%cl, $dst|$dst, cl}",
                  [(store (rotr (loadi8 addr:$dst), CL), addr:$dst)],

test/CodeGen/X86/rotate.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=i686-unknown-linux | FileCheck %s --check-prefix=32
 ; RUN: llc < %s -mtriple=x86_64-unknown-linux | FileCheck %s --check-prefix=64
 
 define i64 @rotl64(i64 %A, i8 %Amt) {
 ; 32-LABEL: rotl64:
 ; 32:       # BB#0:
 ; 32-NEXT:    pushl %ebx
 ; 32-NEXT:  .Ltmp0:
 ; 32-NEXT:    .cfi_def_cfa_offset 8
 ; 32-NEXT:    pushl %edi
 ; 32-NEXT:  .Ltmp1:
 ; 32-NEXT:    .cfi_def_cfa_offset 12
 ; 32-NEXT:    pushl %esi
 ; 32-NEXT:  .Ltmp2:
 ; 32-NEXT:    .cfi_def_cfa_offset 16
 ; 32-NEXT:  .Ltmp3:
 ; 32-NEXT:    .cfi_offset %esi, -16
 ; 32-NEXT:  .Ltmp4:
 ; 32-NEXT:    .cfi_offset %edi, -12
 ; 32-NEXT:  .Ltmp5:
 ; 32-NEXT:    .cfi_offset %ebx, -8
 ; 32-NEXT:    movb {{[0-9]+}}(%esp), %cl
 ; 32-NEXT:    movl {{[0-9]+}}(%esp), %esi
 ; 32-NEXT:    movl {{[0-9]+}}(%esp), %edi
 ; 32-NEXT:    movl %esi, %eax
 ; 32-NEXT:    shll %cl, %eax
 ; 32-NEXT:    movl %edi, %edx
 ; 32-NEXT:    shldl %cl, %esi, %edx
 ; 32-NEXT:    testb $32, %cl
 ; 32-NEXT:    je .LBB0_2
 ; 32-NEXT:  # BB#1:
 ; 32-NEXT:    movl %eax, %edx
 ; 32-NEXT:    xorl %eax, %eax
 ; 32-NEXT:  .LBB0_2:
 ; 32-NEXT:    movb $64, %ch
 ; 32-NEXT:    subb %cl, %ch
 ; 32-NEXT:    movl %edi, %ebx
 ; 32-NEXT:    movb %ch, %cl
 ; 32-NEXT:    shrl %cl, %ebx
 ; 32-NEXT:    shrdl %cl, %edi, %esi
 ; 32-NEXT:    testb $32, %ch
 ; 32-NEXT:    je .LBB0_4
 ; 32-NEXT:  # BB#3:
 ; 32-NEXT:    movl %ebx, %esi
 ; 32-NEXT:    xorl %ebx, %ebx
 ; 32-NEXT:  .LBB0_4:
 ; 32-NEXT:    orl %esi, %eax
 ; 32-NEXT:    orl %ebx, %edx
 ; 32-NEXT:    popl %esi
 ; 32-NEXT:    popl %edi
 ; 32-NEXT:    popl %ebx
 ; 32-NEXT:    retl
 ;
 ; 64-LABEL: rotl64:
 ; 64:       # BB#0:
 ; 64-NEXT:    movl %esi, %ecx
 ; 64-NEXT:    rolq %cl, %rdi
 ; 64-NEXT:    movq %rdi, %rax
 ; 64-NEXT:    retq
   %shift.upgrd.1 = zext i8 %Amt to i64
   %B = shl i64 %A, %shift.upgrd.1
   %Amt2 = sub i8 64, %Amt
   %shift.upgrd.2 = zext i8 %Amt2 to i64
   %C = lshr i64 %A, %shift.upgrd.2
   %D = or i64 %B, %C
   ret i64 %D
 }
 
 define i64 @rotr64(i64 %A, i8 %Amt) {
 ; 32-LABEL: rotr64:
 ; 32:       # BB#0:
 ; 32-NEXT:    pushl %ebx
 ; 32-NEXT:  .Ltmp6:
 ; 32-NEXT:    .cfi_def_cfa_offset 8
 ; 32-NEXT:    pushl %edi
 ; 32-NEXT:  .Ltmp7:
 ; 32-NEXT:    .cfi_def_cfa_offset 12
 ; 32-NEXT:    pushl %esi
 ; 32-NEXT:  .Ltmp8:
 ; 32-NEXT:    .cfi_def_cfa_offset 16
 ; 32-NEXT:  .Ltmp9:
 ; 32-NEXT:    .cfi_offset %esi, -16
 ; 32-NEXT:  .Ltmp10:
 ; 32-NEXT:    .cfi_offset %edi, -12
 ; 32-NEXT:  .Ltmp11:
 ; 32-NEXT:    .cfi_offset %ebx, -8
 ; 32-NEXT:    movb {{[0-9]+}}(%esp), %cl
 ; 32-NEXT:    movl {{[0-9]+}}(%esp), %edi
 ; 32-NEXT:    movl {{[0-9]+}}(%esp), %esi
 ; 32-NEXT:    movl %esi, %edx
 ; 32-NEXT:    shrl %cl, %edx
 ; 32-NEXT:    movl %edi, %eax
 ; 32-NEXT:    shrdl %cl, %esi, %eax
 ; 32-NEXT:    testb $32, %cl
 ; 32-NEXT:    je .LBB1_2
 ; 32-NEXT:  # BB#1:
 ; 32-NEXT:    movl %edx, %eax
 ; 32-NEXT:    xorl %edx, %edx
 ; 32-NEXT:  .LBB1_2:
 ; 32-NEXT:    movb $64, %ch
 ; 32-NEXT:    subb %cl, %ch
 ; 32-NEXT:    movl %edi, %ebx
 ; 32-NEXT:    movb %ch, %cl
 ; 32-NEXT:    shll %cl, %ebx
 ; 32-NEXT:    shldl %cl, %edi, %esi
 ; 32-NEXT:    testb $32, %ch
 ; 32-NEXT:    je .LBB1_4
 ; 32-NEXT:  # BB#3:
 ; 32-NEXT:    movl %ebx, %esi
 ; 32-NEXT:    xorl %ebx, %ebx
 ; 32-NEXT:  .LBB1_4:
 ; 32-NEXT:    orl %ebx, %eax
 ; 32-NEXT:    orl %esi, %edx
 ; 32-NEXT:    popl %esi
 ; 32-NEXT:    popl %edi
 ; 32-NEXT:    popl %ebx
 ; 32-NEXT:    retl
 ;
 ; 64-LABEL: rotr64:
 ; 64:       # BB#0:
 ; 64-NEXT:    movl %esi, %ecx
 ; 64-NEXT:    rorq %cl, %rdi
 ; 64-NEXT:    movq %rdi, %rax
 ; 64-NEXT:    retq
   %shift.upgrd.3 = zext i8 %Amt to i64
   %B = lshr i64 %A, %shift.upgrd.3
   %Amt2 = sub i8 64, %Amt
   %shift.upgrd.4 = zext i8 %Amt2 to i64
   %C = shl i64 %A, %shift.upgrd.4
   %D = or i64 %B, %C
   ret i64 %D
 }
 
 define i64 @rotli64(i64 %A) {
 ; 32-LABEL: rotli64:
 ; 32:       # BB#0:
 ; 32-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; 32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 ; 32-NEXT:    movl %ecx, %edx
 ; 32-NEXT:    shldl $5, %eax, %edx
 ; 32-NEXT:    shldl $5, %ecx, %eax
 ; 32-NEXT:    retl
 ;
 ; 64-LABEL: rotli64:
 ; 64:       # BB#0:
 ; 64-NEXT:    rolq $5, %rdi
 ; 64-NEXT:    movq %rdi, %rax
 ; 64-NEXT:    retq
   %B = shl i64 %A, 5
   %C = lshr i64 %A, 59
   %D = or i64 %B, %C
   ret i64 %D
 }
 
 define i64 @rotri64(i64 %A) {
 ; 32-LABEL: rotri64:
 ; 32:       # BB#0:
 ; 32-NEXT:    movl {{[0-9]+}}(%esp), %edx
 ; 32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 ; 32-NEXT:    movl %ecx, %eax
 ; 32-NEXT:    shldl $27, %edx, %eax
 ; 32-NEXT:    shldl $27, %ecx, %edx
 ; 32-NEXT:    retl
 ;
 ; 64-LABEL: rotri64:
 ; 64:       # BB#0:
 ; 64-NEXT:    rolq $59, %rdi
 ; 64-NEXT:    movq %rdi, %rax
 ; 64-NEXT:    retq
   %B = lshr i64 %A, 5
   %C = shl i64 %A, 59
   %D = or i64 %B, %C
   ret i64 %D
 }
 
 define i64 @rotl1_64(i64 %A) {
 ; 32-LABEL: rotl1_64:
 ; 32:       # BB#0:
 ; 32-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; 32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 ; 32-NEXT:    movl %ecx, %edx
 ; 32-NEXT:    shldl $1, %eax, %edx
 ; 32-NEXT:    shldl $1, %ecx, %eax
 ; 32-NEXT:    retl
 ;
 ; 64-LABEL: rotl1_64:
 ; 64:       # BB#0:
 ; 64-NEXT:    rolq %rdi
 ; 64-NEXT:    movq %rdi, %rax
 ; 64-NEXT:    retq
   %B = shl i64 %A, 1
   %C = lshr i64 %A, 63
   %D = or i64 %B, %C
   ret i64 %D
 }
 
 define i64 @rotr1_64(i64 %A) {
 ; 32-LABEL: rotr1_64:
 ; 32:       # BB#0:
 ; 32-NEXT:    movl {{[0-9]+}}(%esp), %edx
 ; 32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 ; 32-NEXT:    movl %ecx, %eax
 ; 32-NEXT:    shldl $31, %edx, %eax
 ; 32-NEXT:    shldl $31, %ecx, %edx
 ; 32-NEXT:    retl
 ;
 ; 64-LABEL: rotr1_64:
 ; 64:       # BB#0:
-; 64-NEXT:    rolq $63, %rdi
+; 64-NEXT:    rorq %rdi
 ; 64-NEXT:    movq %rdi, %rax
 ; 64-NEXT:    retq
   %B = shl i64 %A, 63
   %C = lshr i64 %A, 1
   %D = or i64 %B, %C
   ret i64 %D
 }
 
 define i32 @rotl32(i32 %A, i8 %Amt) {
 ; 32-LABEL: rotl32:
 ; 32:       # BB#0:
 ; 32-NEXT:    movb {{[0-9]+}}(%esp), %cl
 ; 32-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; 32-NEXT:    roll %cl, %eax
 ; 32-NEXT:    retl
; 64-NEXT:    retq
   %D = or i32 %B, %C
   ret i32 %D
 }
 
 define i32 @rotr1_32(i32 %A) {
 ; 32-LABEL: rotr1_32:
 ; 32:       # BB#0:
 ; 32-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; 32-NEXT:    roll $31, %eax
+; 32-NEXT:    rorl %eax
 ; 32-NEXT:    retl
 ;
 ; 64-LABEL: rotr1_32:
 ; 64:       # BB#0:
-; 64-NEXT:    roll $31, %edi
+; 64-NEXT:    rorl %edi
 ; 64-NEXT:    movl %edi, %eax
 ; 64-NEXT:    retq
   %B = shl i32 %A, 31
   %C = lshr i32 %A, 1
   %D = or i32 %B, %C
   ret i32 %D
 }
 
; 64-NEXT:    retq
   %D = or i16 %B, %C
   ret i16 %D
 }
 
 define i16 @rotr1_16(i16 %A) {
 ; 32-LABEL: rotr1_16:
 ; 32:       # BB#0:
 ; 32-NEXT:    movzwl {{[0-9]+}}(%esp), %eax
-; 32-NEXT:    rolw $15, %ax
+; 32-NEXT:    rorw %ax
 ; 32-NEXT:    retl
 ;
 ; 64-LABEL: rotr1_16:
 ; 64:       # BB#0:
-; 64-NEXT:    rolw $15, %di
+; 64-NEXT:    rorw %di
 ; 64-NEXT:    movl %edi, %eax
 ; 64-NEXT:    retq
   %B = lshr i16 %A, 1
   %C = shl i16 %A, 15
   %D = or i16 %B, %C
   ret i16 %D
 }
 
; 64-NEXT:    retq
   %D = or i8 %B, %C
   ret i8 %D
 }
 
 define i8 @rotr1_8(i8 %A) {
 ; 32-LABEL: rotr1_8:
 ; 32:       # BB#0:
 ; 32-NEXT:    movb {{[0-9]+}}(%esp), %al
-; 32-NEXT:    rolb $7, %al
+; 32-NEXT:    rorb %al
 ; 32-NEXT:    retl
 ;
 ; 64-LABEL: rotr1_8:
 ; 64:       # BB#0:
-; 64-NEXT:    rolb $7, %dil
+; 64-NEXT:    rorb %dil
 ; 64-NEXT:    movl %edi, %eax
 ; 64-NEXT:    retq
   %B = lshr i8 %A, 1
   %C = shl i8 %A, 7
   %D = or i8 %B, %C
   ret i8 %D
 }