[X86] Emit BZHI when mask is ~(-1 << nbits))

[lebedev.ri]

Summary

In D47428, i propose to choose the ~(-(1 << nbits)) as the canonical form of low-bit-mask formation.
As it is seen from these tests, there is a reason for that.

AArch64 currently better handles ~(-(1 << nbits)), but not the more traditional (1 << nbits) - 1 (sic!).
The other way around for X86.
It would be much better to canonicalize.

This patch is completely monkey-typing.
I don't really understand how this works :)
I have based it on // x & (-1 >> (32 - y)) pattern.

Also, when we only have BMI, i wonder if we could use BEXTR with start=0 ?

Related links:
https://bugs.llvm.org/show_bug.cgi?id=36419
https://bugs.llvm.org/show_bug.cgi?id=37603
https://bugs.llvm.org/show_bug.cgi?id=37610
https://rise4fun.com/Alive/idM

[lebedev.ri]

Rebased ontop of reworked tests,
Redo patternmatch ontop of the first matcher there, x & ((1 << y) - 1).

[lebedev.ri]

• Rebased ontop of revisited tests.
• Monkey-fix the rest of the patterns when the index is i8.

[lebedev.ri]

Rebased ontop of updated tests.

[lebedev.ri]

I will follow-up with a similar patches for bextr, but after this lands.

[lebedev.ri]

Rebased.

[RKSimon]

lib/Target/X86/X86InstrInfo.td

2503

We're duplicating all these patterns for 32/64 cases - worth wrapping these in a bzhi_patterns multiclass?

[lebedev.ri]

Apply multiclass to the cases where $lz is always GR8.
This is kinda messy, not too good with tablegen yet..

I'm not quite sure how to handle those last few special cases where $lz is always GR32.

[craig.topper]

lib/Target/X86/X86InstrInfo.td

2439

I'm thorougly confused as to how this many arguments are "Intrinsic". I wouldn't have expected that to work unless Intrinsic is very loosely defined. DstMemInt and DstInt should be of type "Instruction". And they should probably be DstMemInst and DstInst. I think "Int" should be of type ValueType and renamed to VT.

[craig.topper]

lib/Target/X86/X86InstrInfo.td

2436

bitwidth isn't used in this class.

[lebedev.ri]

Cleanup multiclass a bit more.

lib/Target/X86/X86InstrInfo.td

2439

I'm thorougly confused as to how this many arguments are "Intrinsic".

I'm super confused by this too.
I'm not quite familiar with this, and there does not seem to be any documentation,
so i'm writing this via the copy-paste method :/
Naturally, the results are rather suboptimal.

But even then, this is still backwards. We want to define input patterns,
and then define the output pattern, as sub-class. But i guess that can be done later.

[lebedev.ri]

lib/Target/X86/X86InstrInfo.td

2454–2458

I understand that this still has some duplication.
I have tried reworking it further, but i do not yet understand how
to pass either RC:$src or (x86memop addr:$src) as multiclass param.

[lebedev.ri]

Any directional hints on this?
Is this sufficiently tablegen-y, or any suggestions on how to condense it further?

[craig.topper]

LGTM

[lebedev.ri]

In D47453#1123754, @craig.topper wrote:

LGTM

Thank you for the review!

lib/Target/X86/X86InstrInfo.td

def : Pat<(and GR64:$src, AndMask64:$mask),
                              (MOV8ri (CountTrailingOnes imm:$mask)), sub_8bit))>;
   def : Pat<(and (loadi64 addr:$src), AndMask64:$mask),
             (BZHI64rm addr:$src,
               (INSERT_SUBREG (i64 (IMPLICIT_DEF)),
                              (MOV8ri (CountTrailingOnes imm:$mask)), sub_8bit))>;
 }
 
 let Predicates = [HasBMI2] in {
+  // x & ((1 << y) - 1)
   def : Pat<(and GR32:$src, (add (shl 1, GR8:$lz), -1)),
             (BZHI32rr GR32:$src,
               (INSERT_SUBREG (i32 (IMPLICIT_DEF)), GR8:$lz, sub_8bit))>;
 
   def : Pat<(and (loadi32 addr:$src), (add (shl 1, GR8:$lz), -1)),
             (BZHI32rm addr:$src,
               (INSERT_SUBREG (i32 (IMPLICIT_DEF)), GR8:$lz, sub_8bit))>;
 
   def : Pat<(and GR64:$src, (add (shl 1, GR8:$lz), -1)),
             (BZHI64rr GR64:$src,
               (INSERT_SUBREG (i64 (IMPLICIT_DEF)), GR8:$lz, sub_8bit))>;
 
   def : Pat<(and (loadi64 addr:$src), (add (shl 1, GR8:$lz), -1)),
             (BZHI64rm addr:$src,
               (INSERT_SUBREG (i64 (IMPLICIT_DEF)), GR8:$lz, sub_8bit))>;
 
+  // x & ~(-1 << y)
+  def : Pat<(and GR32:$src, (xor (shl -1, GR8:$lz), -1)),
+            (BZHI32rr GR32:$src,
+              (INSERT_SUBREG (i32 (IMPLICIT_DEF)), GR8:$lz, sub_8bit))>;
+
+  def : Pat<(and (loadi32 addr:$src), (xor (shl -1, GR8:$lz), -1)),
+            (BZHI32rm addr:$src,
+              (INSERT_SUBREG (i32 (IMPLICIT_DEF)), GR8:$lz, sub_8bit))>;
+
+  def : Pat<(and GR64:$src, (xor (shl -1, GR8:$lz), -1)),
+            (BZHI64rr GR64:$src,
+              (INSERT_SUBREG (i64 (IMPLICIT_DEF)), GR8:$lz, sub_8bit))>;
+
+  def : Pat<(and (loadi64 addr:$src), (xor (shl -1, GR8:$lz), -1)),
+            (BZHI64rm addr:$src,
+              (INSERT_SUBREG (i64 (IMPLICIT_DEF)), GR8:$lz, sub_8bit))>;
+
   // x & (-1 >> (32 - y))
   def : Pat<(and GR32:$src, (srl -1, (i8 (trunc (sub 32, GR32:$lz))))),
             (BZHI32rr GR32:$src, GR32:$lz)>;
   def : Pat<(and (loadi32 addr:$src), (srl -1, (i8 (trunc (sub 32, GR32:$lz))))),
             (BZHI32rm addr:$src, GR32:$lz)>;
 
   // x & (-1 >> (64 - y))
   def : Pat<(and GR64:$src, (srl -1, (i8 (trunc (sub 64, GR32:$lz))))),
def : Pat<(srl (shl (loadi64 addr:$src), (i8 (trunc (sub 64, GR32:$lz)))),
             (BZHI64rm addr:$src,
               (INSERT_SUBREG (i64 (IMPLICIT_DEF)), GR32:$lz, sub_32bit))>;
 } // HasBMI2
 
 multiclass bmi_pdep_pext<string mnemonic, RegisterClass RC,
                          X86MemOperand x86memop, Intrinsic Int,
                          PatFrag ld_frag> {
   def rr : I<0xF5, MRMSrcReg, (outs RC:$dst), (ins RC:$src1, RC:$src2),
              !strconcat(mnemonic, "\t{$src2, $src1, $dst|$dst, $src1, $src2}"),
              [(set RC:$dst, (Int RC:$src1, RC:$src2))]>,
              VEX_4V, Sched<[WriteALU]>;
   def rm : I<0xF5, MRMSrcMem, (outs RC:$dst), (ins RC:$src1, x86memop:$src2),
              !strconcat(mnemonic, "\t{$src2, $src1, $dst|$dst, $src1, $src2}"),
              [(set RC:$dst, (Int RC:$src1, (ld_frag addr:$src2)))]>,
              VEX_4V, Sched<[WriteALULd, ReadAfterLd]>;
 }
 

test/CodeGen/X86/bmi-bzhi.ll

 ; CHECK-BMI1-NEXT:    movl $-1, %eax
 ; CHECK-BMI1-NEXT:    movl %esi, %ecx
 ; CHECK-BMI1-NEXT:    shll %cl, %eax
 ; CHECK-BMI1-NEXT:    andnl %edi, %eax, %eax
 ; CHECK-BMI1-NEXT:    retq
 ;
 ; CHECK-BMI2-LABEL: bzhi32_b0:
 ; CHECK-BMI2:       # %bb.0:
-; CHECK-BMI2-NEXT:    movl $-1, %eax
-; CHECK-BMI2-NEXT:    shlxl %esi, %eax, %eax
-; CHECK-BMI2-NEXT:    andnl %edi, %eax, %eax
+; CHECK-BMI2-NEXT:    bzhil %esi, %edi, %eax
 ; CHECK-BMI2-NEXT:    retq
   %notmask = shl i32 -1, %numlowbits
   %mask = xor i32 %notmask, -1
   %masked = and i32 %mask, %val
   ret i32 %masked
 }
 
 define i32 @bzhi32_b1_indexzext(i32 %val, i8 zeroext %numlowbits) {

 ; CHECK-BMI1-NEXT:    movl $-1, %eax
 ; CHECK-BMI1-NEXT:    movl %esi, %ecx
 ; CHECK-BMI1-NEXT:    shll %cl, %eax
 ; CHECK-BMI1-NEXT:    andnl %edi, %eax, %eax
 ; CHECK-BMI1-NEXT:    retq
 ;
 ; CHECK-BMI2-LABEL: bzhi32_b1_indexzext:
 ; CHECK-BMI2:       # %bb.0:
-; CHECK-BMI2-NEXT:    movl $-1, %eax
-; CHECK-BMI2-NEXT:    shlxl %esi, %eax, %eax
-; CHECK-BMI2-NEXT:    andnl %edi, %eax, %eax
+; CHECK-BMI2-NEXT:    bzhil %esi, %edi, %eax
 ; CHECK-BMI2-NEXT:    retq
   %conv = zext i8 %numlowbits to i32
   %notmask = shl i32 -1, %conv
   %mask = xor i32 %notmask, -1
   %masked = and i32 %mask, %val
   ret i32 %masked
 }
 

 ; CHECK-BMI1-NEXT:    movl $-1, %eax
 ; CHECK-BMI1-NEXT:    movl %esi, %ecx
 ; CHECK-BMI1-NEXT:    shll %cl, %eax
 ; CHECK-BMI1-NEXT:    andnl (%rdi), %eax, %eax
 ; CHECK-BMI1-NEXT:    retq
 ;
 ; CHECK-BMI2-LABEL: bzhi32_b2_load:
 ; CHECK-BMI2:       # %bb.0:
-; CHECK-BMI2-NEXT:    movl $-1, %eax
-; CHECK-BMI2-NEXT:    shlxl %esi, %eax, %eax
-; CHECK-BMI2-NEXT:    andnl (%rdi), %eax, %eax
+; CHECK-BMI2-NEXT:    bzhil %esi, (%rdi), %eax
 ; CHECK-BMI2-NEXT:    retq
   %val = load i32, i32* %w
   %notmask = shl i32 -1, %numlowbits
   %mask = xor i32 %notmask, -1
   %masked = and i32 %mask, %val
   ret i32 %masked
 }
 

 ; CHECK-BMI1-NEXT:    movl $-1, %eax
 ; CHECK-BMI1-NEXT:    movl %esi, %ecx
 ; CHECK-BMI1-NEXT:    shll %cl, %eax
 ; CHECK-BMI1-NEXT:    andnl (%rdi), %eax, %eax
 ; CHECK-BMI1-NEXT:    retq
 ;
 ; CHECK-BMI2-LABEL: bzhi32_b3_load_indexzext:
 ; CHECK-BMI2:       # %bb.0:
-; CHECK-BMI2-NEXT:    movl $-1, %eax
-; CHECK-BMI2-NEXT:    shlxl %esi, %eax, %eax
-; CHECK-BMI2-NEXT:    andnl (%rdi), %eax, %eax
+; CHECK-BMI2-NEXT:    bzhil %esi, (%rdi), %eax
 ; CHECK-BMI2-NEXT:    retq
   %val = load i32, i32* %w
   %conv = zext i8 %numlowbits to i32
   %notmask = shl i32 -1, %conv
   %mask = xor i32 %notmask, -1
   %masked = and i32 %mask, %val
   ret i32 %masked
 }

 ; CHECK-BMI1-NEXT:    movl $-1, %eax
 ; CHECK-BMI1-NEXT:    movl %esi, %ecx
 ; CHECK-BMI1-NEXT:    shll %cl, %eax
 ; CHECK-BMI1-NEXT:    andnl %edi, %eax, %eax
 ; CHECK-BMI1-NEXT:    retq
 ;
 ; CHECK-BMI2-LABEL: bzhi32_b4_commutative:
 ; CHECK-BMI2:       # %bb.0:
-; CHECK-BMI2-NEXT:    movl $-1, %eax
-; CHECK-BMI2-NEXT:    shlxl %esi, %eax, %eax
-; CHECK-BMI2-NEXT:    andnl %edi, %eax, %eax
+; CHECK-BMI2-NEXT:    bzhil %esi, %edi, %eax
 ; CHECK-BMI2-NEXT:    retq
   %notmask = shl i32 -1, %numlowbits
   %mask = xor i32 %notmask, -1
   %masked = and i32 %val, %mask ; swapped order
   ret i32 %masked
 }
 
 define i16 @bzhi32_b5_trunc16(i32 %val, i32 %numlowbits) {

 ; CHECK-BMI1-NEXT:    movl %esi, %ecx
 ; CHECK-BMI1-NEXT:    shll %cl, %eax
 ; CHECK-BMI1-NEXT:    andnl %edi, %eax, %eax
 ; CHECK-BMI1-NEXT:    # kill: def $ax killed $ax killed $eax
 ; CHECK-BMI1-NEXT:    retq
 ;
 ; CHECK-BMI2-LABEL: bzhi32_b5_trunc16:
 ; CHECK-BMI2:       # %bb.0:
-; CHECK-BMI2-NEXT:    movl $-1, %eax
-; CHECK-BMI2-NEXT:    shlxl %esi, %eax, %eax
-; CHECK-BMI2-NEXT:    andnl %edi, %eax, %eax
+; CHECK-BMI2-NEXT:    bzhil %esi, %edi, %eax
 ; CHECK-BMI2-NEXT:    # kill: def $ax killed $ax killed $eax
 ; CHECK-BMI2-NEXT:    retq
   %notmask = shl i32 -1, %numlowbits
   %mask = xor i32 %notmask, -1
   %masked = and i32 %val, %mask ; swapped order
   %ret = trunc i32 %masked to i16
   ret i16 %ret
 }

 ; CHECK-BMI1-NEXT:    movq $-1, %rax
 ; CHECK-BMI1-NEXT:    movl %esi, %ecx
 ; CHECK-BMI1-NEXT:    shlq %cl, %rax
 ; CHECK-BMI1-NEXT:    andnq %rdi, %rax, %rax
 ; CHECK-BMI1-NEXT:    retq
 ;
 ; CHECK-BMI2-LABEL: bzhi64_b0:
 ; CHECK-BMI2:       # %bb.0:
-; CHECK-BMI2-NEXT:    movq $-1, %rax
-; CHECK-BMI2-NEXT:    shlxq %rsi, %rax, %rax
-; CHECK-BMI2-NEXT:    andnq %rdi, %rax, %rax
+; CHECK-BMI2-NEXT:    bzhiq %rsi, %rdi, %rax
 ; CHECK-BMI2-NEXT:    retq
   %notmask = shl i64 -1, %numlowbits
   %mask = xor i64 %notmask, -1
   %masked = and i64 %mask, %val
   ret i64 %masked
 }
 
 define i64 @bzhi64_b1_indexzext(i64 %val, i8 zeroext %numlowbits) {

 ; CHECK-BMI1-NEXT:    movl %esi, %ecx
 ; CHECK-BMI1-NEXT:    shlq %cl, %rax
 ; CHECK-BMI1-NEXT:    andnq %rdi, %rax, %rax
 ; CHECK-BMI1-NEXT:    retq
 ;
 ; CHECK-BMI2-LABEL: bzhi64_b1_indexzext:
 ; CHECK-BMI2:       # %bb.0:
 ; CHECK-BMI2-NEXT:    # kill: def $esi killed $esi def $rsi
-; CHECK-BMI2-NEXT:    movq $-1, %rax
-; CHECK-BMI2-NEXT:    shlxq %rsi, %rax, %rax
-; CHECK-BMI2-NEXT:    andnq %rdi, %rax, %rax
+; CHECK-BMI2-NEXT:    bzhiq %rsi, %rdi, %rax
 ; CHECK-BMI2-NEXT:    retq
   %conv = zext i8 %numlowbits to i64
   %notmask = shl i64 -1, %conv
   %mask = xor i64 %notmask, -1
   %masked = and i64 %mask, %val
   ret i64 %masked
 }
 

 ; CHECK-BMI1-NEXT:    movq $-1, %rax
 ; CHECK-BMI1-NEXT:    movl %esi, %ecx
 ; CHECK-BMI1-NEXT:    shlq %cl, %rax
 ; CHECK-BMI1-NEXT:    andnq (%rdi), %rax, %rax
 ; CHECK-BMI1-NEXT:    retq
 ;
 ; CHECK-BMI2-LABEL: bzhi64_b2_load:
 ; CHECK-BMI2:       # %bb.0:
-; CHECK-BMI2-NEXT:    movq $-1, %rax
-; CHECK-BMI2-NEXT:    shlxq %rsi, %rax, %rax
-; CHECK-BMI2-NEXT:    andnq (%rdi), %rax, %rax
+; CHECK-BMI2-NEXT:    bzhiq %rsi, (%rdi), %rax
 ; CHECK-BMI2-NEXT:    retq
   %val = load i64, i64* %w
   %notmask = shl i64 -1, %numlowbits
   %mask = xor i64 %notmask, -1
   %masked = and i64 %mask, %val
   ret i64 %masked
 }
 

 ; CHECK-BMI1-NEXT:    movl %esi, %ecx
 ; CHECK-BMI1-NEXT:    shlq %cl, %rax
 ; CHECK-BMI1-NEXT:    andnq (%rdi), %rax, %rax
 ; CHECK-BMI1-NEXT:    retq
 ;
 ; CHECK-BMI2-LABEL: bzhi64_b3_load_indexzext:
 ; CHECK-BMI2:       # %bb.0:
 ; CHECK-BMI2-NEXT:    # kill: def $esi killed $esi def $rsi
-; CHECK-BMI2-NEXT:    movq $-1, %rax
-; CHECK-BMI2-NEXT:    shlxq %rsi, %rax, %rax
-; CHECK-BMI2-NEXT:    andnq (%rdi), %rax, %rax
+; CHECK-BMI2-NEXT:    bzhiq %rsi, (%rdi), %rax
 ; CHECK-BMI2-NEXT:    retq
   %val = load i64, i64* %w
   %conv = zext i8 %numlowbits to i64
   %notmask = shl i64 -1, %conv
   %mask = xor i64 %notmask, -1
   %masked = and i64 %mask, %val
   ret i64 %masked
 }

 ; CHECK-BMI1-NEXT:    movq $-1, %rax
 ; CHECK-BMI1-NEXT:    movl %esi, %ecx
 ; CHECK-BMI1-NEXT:    shlq %cl, %rax
 ; CHECK-BMI1-NEXT:    andnq %rdi, %rax, %rax
 ; CHECK-BMI1-NEXT:    retq
 ;
 ; CHECK-BMI2-LABEL: bzhi64_b4_commutative:
 ; CHECK-BMI2:       # %bb.0:
-; CHECK-BMI2-NEXT:    movq $-1, %rax
-; CHECK-BMI2-NEXT:    shlxq %rsi, %rax, %rax
-; CHECK-BMI2-NEXT:    andnq %rdi, %rax, %rax
+; CHECK-BMI2-NEXT:    bzhiq %rsi, %rdi, %rax
 ; CHECK-BMI2-NEXT:    retq
   %notmask = shl i64 -1, %numlowbits
   %mask = xor i64 %notmask, -1
   %masked = and i64 %val, %mask ; swapped order
   ret i64 %masked
 }
 
 define i32 @bzhi64_b5_trunc32(i64 %val, i64 %numlowbits) {