[x86] fold the mask op on 8- and 16-bit rotates

[spatel]

Summary

Ref the post-commit thread for r310770:
http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20170807/478507.html

The motivating cases as 'C' source examples can look like this:

unsigned char rotate_right_8(unsigned char v, int shift) {
  //shift &= 7;
  v = ( v >> shift ) | ( v << ( 8 - shift ) );
  return v;
}

https://godbolt.org/g/K6rc1A

Notice that the source doesn't contain UB-safe masked shift amounts, but instcombine created those in order to produce narrow rotate patterns.
This should be the last step needed to resolve PR34046:
https://bugs.llvm.org/show_bug.cgi?id=34046

[craig.topper]

LGTM

lib/Target/X86/X86InstrCompiler.td

 // where the least significant bit is not 0. However, the probability of this
 // happening is considered low enough that this is officially not a
 // "real problem".
 def : Pat<(shl GR8 :$src1, (i8 1)), (ADD8rr  GR8 :$src1, GR8 :$src1)>;
 def : Pat<(shl GR16:$src1, (i8 1)), (ADD16rr GR16:$src1, GR16:$src1)>;
 def : Pat<(shl GR32:$src1, (i8 1)), (ADD32rr GR32:$src1, GR32:$src1)>;
 def : Pat<(shl GR64:$src1, (i8 1)), (ADD64rr GR64:$src1, GR64:$src1)>;
 
-// Helper imms that check if a mask doesn't change significant shift bits.
+// Helper imms to check if a mask doesn't change significant shift/rotate bits.
+def immShift8 : ImmLeaf<i8, [{
+  return countTrailingOnes<uint64_t>(Imm) >= 3;
+}]>;
+def immShift16 : ImmLeaf<i8, [{
+  return countTrailingOnes<uint64_t>(Imm) >= 4;
+}]>;
 def immShift32 : ImmLeaf<i8, [{
   return countTrailingOnes<uint64_t>(Imm) >= 5;
 }]>;
 def immShift64 : ImmLeaf<i8, [{
   return countTrailingOnes<uint64_t>(Imm) >= 6;
 }]>;
 
 // Shift amount is implicitly masked.
def : Pat<(frag GR64:$src1, (and CL, immShift64)),
             (!cast<Instruction>(name # "64rCL") GR64:$src1)>;
   def : Pat<(store (frag (loadi64 addr:$dst), (and CL, immShift64)), addr:$dst),
             (!cast<Instruction>(name # "64mCL") addr:$dst)>;
 }
 
 defm : MaskedShiftAmountPats<shl, "SHL">;
 defm : MaskedShiftAmountPats<srl, "SHR">;
 defm : MaskedShiftAmountPats<sra, "SAR">;
-defm : MaskedShiftAmountPats<rotl, "ROL">;
-defm : MaskedShiftAmountPats<rotr, "ROR">;
+
+// ROL/ROR instructions allow a stronger mask optimization than shift for 8- and
+// 16-bit. We can remove a mask of any (bitwidth - 1) on the rotation amount
+// because over-rotating produces the same result. This is noted in the Intel
+// docs with: "tempCOUNT <- (COUNT & COUNTMASK) MOD SIZE". Masking the rotation
+// amount could affect EFLAGS results, but that does not matter because we are
+// not tracking flags for these nodes.
+multiclass MaskedRotateAmountPats<SDNode frag, string name> {
+  // (rot x (and y, BitWidth - 1)) ==> (rot x, y)
+  def : Pat<(frag GR8:$src1, (and CL, immShift8)),
+  (!cast<Instruction>(name # "8rCL") GR8:$src1)>;
+  def : Pat<(frag GR16:$src1, (and CL, immShift16)),
+  (!cast<Instruction>(name # "16rCL") GR16:$src1)>;
+  def : Pat<(frag GR32:$src1, (and CL, immShift32)),
+  (!cast<Instruction>(name # "32rCL") GR32:$src1)>;
+  def : Pat<(store (frag (loadi8 addr:$dst), (and CL, immShift8)), addr:$dst),
+  (!cast<Instruction>(name # "8mCL") addr:$dst)>;
+  def : Pat<(store (frag (loadi16 addr:$dst), (and CL, immShift16)), addr:$dst),
+  (!cast<Instruction>(name # "16mCL") addr:$dst)>;
+  def : Pat<(store (frag (loadi32 addr:$dst), (and CL, immShift32)), addr:$dst),
+  (!cast<Instruction>(name # "32mCL") addr:$dst)>;
+
+  // (rot x (and y, 63)) ==> (rot x, y)
+  def : Pat<(frag GR64:$src1, (and CL, immShift64)),
+  (!cast<Instruction>(name # "64rCL") GR64:$src1)>;
+  def : Pat<(store (frag (loadi64 addr:$dst), (and CL, immShift64)), addr:$dst),
+  (!cast<Instruction>(name # "64mCL") addr:$dst)>;
+}
+
+
+defm : MaskedRotateAmountPats<rotl, "ROL">;
+defm : MaskedRotateAmountPats<rotr, "ROR">;
 
 // Double shift amount is implicitly masked.
 multiclass MaskedDoubleShiftAmountPats<SDNode frag, string name> {
   // (shift x (and y, 31)) ==> (shift x, y)
   def : Pat<(frag GR16:$src1, GR16:$src2, (and CL, immShift32)),
             (!cast<Instruction>(name # "16rrCL") GR16:$src1, GR16:$src2)>;
   def : Pat<(frag GR32:$src1, GR32:$src2, (and CL, immShift32)),
             (!cast<Instruction>(name # "32rrCL") GR32:$src1, GR32:$src2)>;

test/CodeGen/X86/rotate4.ll

 }
 
 ; The next 8 tests include masks of the narrow width shift amounts that should be eliminated.
 ; These patterns are produced by instcombine after r310509.
 
 define i8 @rotate_left_8(i8 %x, i32 %amount) {
 ; CHECK-LABEL: rotate_left_8:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    andb $7, %sil
 ; CHECK-NEXT:    movl %esi, %ecx
 ; CHECK-NEXT:    rolb %cl, %dil
 ; CHECK-NEXT:    movl %edi, %eax
 ; CHECK-NEXT:    retq
   %amt = trunc i32 %amount to i8
   %sub = sub i8 0, %amt
   %maskamt = and i8 %amt, 7
   %masksub = and i8 %sub, 7
   %shl = shl i8 %x, %maskamt
   %shr = lshr i8 %x, %masksub
   %or = or i8 %shl, %shr
   ret i8 %or
 }
 
 define i8 @rotate_right_8(i8 %x, i32 %amount) {
 ; CHECK-LABEL: rotate_right_8:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    andb $7, %sil
 ; CHECK-NEXT:    movl %esi, %ecx
 ; CHECK-NEXT:    rorb %cl, %dil
 ; CHECK-NEXT:    movl %edi, %eax
 ; CHECK-NEXT:    retq
   %amt = trunc i32 %amount to i8
   %sub = sub i8 0, %amt
   %maskamt = and i8 %amt, 7
   %masksub = and i8 %sub, 7
   %shr = lshr i8 %x, %maskamt
   %shl = shl i8 %x, %masksub
   %or = or i8 %shr, %shl
   ret i8 %or
 }
 
 define i16 @rotate_left_16(i16 %x, i32 %amount) {
 ; CHECK-LABEL: rotate_left_16:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    andb $15, %sil
 ; CHECK-NEXT:    movl %esi, %ecx
 ; CHECK-NEXT:    rolw %cl, %di
 ; CHECK-NEXT:    movl %edi, %eax
 ; CHECK-NEXT:    retq
   %amt = trunc i32 %amount to i16
   %sub = sub i16 0, %amt
   %maskamt = and i16 %amt, 15
   %masksub = and i16 %sub, 15
   %shl = shl i16 %x, %maskamt
   %shr = lshr i16 %x, %masksub
   %or = or i16 %shl, %shr
   ret i16 %or
 }
 
 define i16 @rotate_right_16(i16 %x, i32 %amount) {
 ; CHECK-LABEL: rotate_right_16:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    andb $15, %sil
 ; CHECK-NEXT:    movl %esi, %ecx
 ; CHECK-NEXT:    rorw %cl, %di
 ; CHECK-NEXT:    movl %edi, %eax
 ; CHECK-NEXT:    retq
   %amt = trunc i32 %amount to i16
   %sub = sub i16 0, %amt
   %maskamt = and i16 %amt, 15
   %masksub = and i16 %sub, 15
   %shr = lshr i16 %x, %maskamt
   %shl = shl i16 %x, %masksub
   %or = or i16 %shr, %shl
   ret i16 %or
 }
 
 define void @rotate_left_m8(i8* %p, i32 %amount) {
 ; CHECK-LABEL: rotate_left_m8:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    andb $7, %sil
 ; CHECK-NEXT:    movl %esi, %ecx
 ; CHECK-NEXT:    rolb %cl, (%rdi)
 ; CHECK-NEXT:    retq
   %x = load i8, i8* %p, align 1
   %amt = trunc i32 %amount to i8
   %sub = sub i8 0, %amt
   %maskamt = and i8 %amt, 7
   %masksub = and i8 %sub, 7
   %shl = shl i8 %x, %maskamt
   %shr = lshr i8 %x, %masksub
   %or = or i8 %shl, %shr
   store i8 %or, i8* %p, align 1
   ret void
 }
 
 define void @rotate_right_m8(i8* %p, i32 %amount) {
 ; CHECK-LABEL: rotate_right_m8:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    andb $7, %sil
 ; CHECK-NEXT:    movl %esi, %ecx
 ; CHECK-NEXT:    rorb %cl, (%rdi)
 ; CHECK-NEXT:    retq
   %x = load i8, i8* %p, align 1
   %amt = trunc i32 %amount to i8
   %sub = sub i8 0, %amt
   %maskamt = and i8 %amt, 7
   %masksub = and i8 %sub, 7
   %shl = shl i8 %x, %masksub
   %shr = lshr i8 %x, %maskamt
   %or = or i8 %shl, %shr
   store i8 %or, i8* %p, align 1
   ret void
 }
 
 define void @rotate_left_m16(i16* %p, i32 %amount) {
 ; CHECK-LABEL: rotate_left_m16:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    andb $15, %sil
 ; CHECK-NEXT:    movl %esi, %ecx
 ; CHECK-NEXT:    rolw %cl, (%rdi)
 ; CHECK-NEXT:    retq
   %x = load i16, i16* %p, align 1
   %amt = trunc i32 %amount to i16
   %sub = sub i16 0, %amt
   %maskamt = and i16 %amt, 15
   %masksub = and i16 %sub, 15
   %shl = shl i16 %x, %maskamt
   %shr = lshr i16 %x, %masksub
   %or = or i16 %shl, %shr
   store i16 %or, i16* %p, align 1
   ret void
 }
 
 define void @rotate_right_m16(i16* %p, i32 %amount) {
 ; CHECK-LABEL: rotate_right_m16:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    andb $15, %sil
 ; CHECK-NEXT:    movl %esi, %ecx
 ; CHECK-NEXT:    rorw %cl, (%rdi)
 ; CHECK-NEXT:    retq
   %x = load i16, i16* %p, align 1
   %amt = trunc i32 %amount to i16
   %sub = sub i16 0, %amt
   %maskamt = and i16 %amt, 15
   %masksub = and i16 %sub, 15
   %shl = shl i16 %x, %masksub
   %shr = lshr i16 %x, %maskamt
   %or = or i16 %shl, %shr
   store i16 %or, i16* %p, align 1
   ret void
 }