[X86] Only match BMI (BLSR, BLSI, BLSMSK) if the add/sub op is single use

[goldstein.w.n]

Summary

If the add/sub is not single use, it will need to be materialized
later, in which case using the BMI instruction is a de-optimization in
terms of code-size and throughput.

i.e:

// Good
leal -1(%rdi), %eax
andl %eax, %eax
xorl %eax, %esi
...

// Unecessary BMI (lower throughput, larger code size)
leal -1(%rdi), %eax
blsr %edi, %eax
xorl %eax, %esi
...

Note, this may cause more mov instructions to be emitted sometimes
because BMI instructions only have 1 src and write-only to dst. A
better approach may be to only avoid BMI for (and/xor X, (add/sub
0/-1, X)) if this is the last use of X but NOT the last use of
(add/sub 0/-1, X).

[goldstein.w.n]

NOTE/Request for advise: This regresses the tests in GlobalISel. I think its because of the single-use defs in the td, as even if I made them just return true the tests the BMI ops still werent getting matched. BMI is still does work (see the bmi-out-of-order.ll tests and bmi.ll is still fine).

Can anyone give me some guidance about how to get the patterns to use custom defs and work for GlobalISel?

[craig.topper]

In D141180#4032986, @goldstein.w.n wrote:

NOTE/Request for advise: This regresses the tests in GlobalISel. I think its because of the single-use defs in the td, as even if I made them just return true the tests the BMI ops still werent getting matched. BMI is still does work (see the bmi-out-of-order.ll tests and bmi.ll is still fine).

Can anyone give me some guidance about how to get the patterns to use custom defs and work for GlobalISel?

I wouldn't worry about GlobalISel. It's not actively being used or developed as far as I know.

[craig.topper]

llvm/lib/Target/X86/X86InstrInfo.td

1271

Maybe we should have

`class binop_oneuse<SDPatternOperator operator>
    : PatFrag<(ops node:$A, node:$B),
              (operator node:$A, node:$B), [{
  return N->hasOneUse();
}]>;`

def add_su : binop_oneuse<add>;
def and_su : binop_oneuse<and>;
def srl_su : binop_oneuse<srl>;

class unop_oneuse<SDPatternOperator operator>
    : PatFrag<(ops node:$A),
              (operator node:$A), [{
  return N->hasOneUse();
}]>;

def ineg_su : unop_oneuse<ineg>;
def trunc_su : unop_oneuse<trunc>;

[goldstein.w.n]

llvm/lib/Target/X86/X86InstrInfo.td

1271

Maybe we should have

`class binop_oneuse<SDPatternOperator operator>
    : PatFrag<(ops node:$A, node:$B),
              (operator node:$A, node:$B), [{
  return N->hasOneUse();
}]>;`

def add_su : binop_oneuse<add>;
def and_su : binop_oneuse<and>;
def srl_su : binop_oneuse<srl>;

class unop_oneuse<SDPatternOperator operator>
    : PatFrag<(ops node:$A),
              (operator node:$A), [{
  return N->hasOneUse();
}]>;

def ineg_su : unop_oneuse<ineg>;
def trunc_su : unop_oneuse<trunc>;

Makes sense, will do for V2.

Any thoughts on:
"""
Note, this may cause more mov instructions to be emitted sometimes
because BMI instructions only have 1 src and write-only to dst. A
better approach may be to only avoid BMI for (and/xor X, (add/sub
0/-1, X)) if this is the last use of X but NOT the last use of
(add/sub 0/-1, X).
"""
?

[pengfei]

llvm/lib/Target/X86/X86InstrInfo.td

1271

Microarchitecture usually can eliminate mov instructions by register renaming, so we can consider no performance lost except for code size.

[goldstein.w.n]

llvm/lib/Target/X86/X86InstrInfo.td

1271

Microarchitecture usually can eliminate mov instructions by register renaming, so we can consider no performance lost except for code size.

IIRC like 80% success rate and some targets like ICX have to disabled. Also still decode and presumably RR overhead. So unless its backend bound work think it will show up.

Note its 1 extra byte for 64-bit, 1 less byte for 32-bit.

I'll leave it as a todo for now I guess.

[goldstein.w.n]

Factor out binop/unop patterns

[goldstein.w.n]

ping.

[RKSimon]

LGTM - for ryzen at least the moves tend to always be free.

[goldstein.w.n]

In D141180#4061582, @RKSimon wrote:

LGTM - for ryzen at least the moves tend to always be free.

can you also checkout D141179 or should I split this?

[goldstein.w.n]

Rebase

llvm/lib/Target/X86/X86InstrInfo.td

def extloadi64i32  : PatFrag<(ops node:$ptr), (i64 (unindexedload node:$ptr)), [{
   if (ExtType != ISD::EXTLOAD)
     return false;
   if (LD->getMemoryVT() == MVT::i32)
     return true;
 
   return LD->getAlign() >= 4 && LD->isSimple();
 }]>;
 
-
-// An 'and' node with a single use.
-def and_su : PatFrag<(ops node:$lhs, node:$rhs), (and node:$lhs, node:$rhs), [{
-  return N->hasOneUse();
-}]>;
-// An 'srl' node with a single use.
-def srl_su : PatFrag<(ops node:$lhs, node:$rhs), (srl node:$lhs, node:$rhs), [{
+// binary op with only one user
+class binop_oneuse<SDPatternOperator operator>
+    : PatFrag<(ops node:$A, node:$B),
+              (operator node:$A, node:$B), [{
   return N->hasOneUse();
 }]>;
-// An 'trunc' node with a single use.
-def trunc_su : PatFrag<(ops node:$src), (trunc node:$src), [{
+
+def add_su : binop_oneuse<add>;
+def and_su : binop_oneuse<and>;
+def srl_su : binop_oneuse<srl>;
+
+// unary op with only one user
+class unop_oneuse<SDPatternOperator operator>
+    : PatFrag<(ops node:$A),
+              (operator node:$A), [{
   return N->hasOneUse();
 }]>;
 
+
+def ineg_su : unop_oneuse<ineg>;
+def trunc_su : unop_oneuse<trunc>;
+
 //===----------------------------------------------------------------------===//
 // Instruction list.
 //
 
 // Nop
 let hasSideEffects = 0, SchedRW = [WriteNop] in {
   def NOOP : I<0x90, RawFrm, (outs), (ins), "nop", []>;
   def NOOPW : I<0x1f, MRMXm, (outs), (ins i16mem:$zero),
def xor_flag_nocf : PatFrag<(ops node:$lhs, node:$rhs),
   return hasNoCarryFlagUses(SDValue(N, 1));
 }]>;
 
 def and_flag_nocf : PatFrag<(ops node:$lhs, node:$rhs),
                             (X86and_flag node:$lhs, node:$rhs), [{
   return hasNoCarryFlagUses(SDValue(N, 1));
 }]>;
 
+
 let Predicates = [HasBMI] in {
-  // FIXME: patterns for the load versions are not implemented
-  def : Pat<(and GR32:$src, (add GR32:$src, -1)),
+  // FIXME(1): patterns for the load versions are not implemented
+  // FIXME(2): By only matching `add_su` and `ineg_su` we may emit
+  // extra `mov` instructions if `src` has future uses. It may be better
+  // to always match if `src` has more users.
+  def : Pat<(and GR32:$src, (add_su GR32:$src, -1)),
             (BLSR32rr GR32:$src)>;
-  def : Pat<(and GR64:$src, (add GR64:$src, -1)),
+  def : Pat<(and GR64:$src, (add_su GR64:$src, -1)),
             (BLSR64rr GR64:$src)>;
 
-  def : Pat<(xor GR32:$src, (add GR32:$src, -1)),
+  def : Pat<(xor GR32:$src, (add_su GR32:$src, -1)),
             (BLSMSK32rr GR32:$src)>;
-  def : Pat<(xor GR64:$src, (add GR64:$src, -1)),
+  def : Pat<(xor GR64:$src, (add_su GR64:$src, -1)),
             (BLSMSK64rr GR64:$src)>;
 
-  def : Pat<(and GR32:$src, (ineg GR32:$src)),
+  def : Pat<(and GR32:$src, (ineg_su GR32:$src)),
             (BLSI32rr GR32:$src)>;
-  def : Pat<(and GR64:$src, (ineg GR64:$src)),
+  def : Pat<(and GR64:$src, (ineg_su GR64:$src)),
             (BLSI64rr GR64:$src)>;
 
   // Versions to match flag producing ops.
-  def : Pat<(and_flag_nocf GR32:$src, (add GR32:$src, -1)),
+  def : Pat<(and_flag_nocf GR32:$src, (add_su GR32:$src, -1)),
             (BLSR32rr GR32:$src)>;
-  def : Pat<(and_flag_nocf GR64:$src, (add GR64:$src, -1)),
+  def : Pat<(and_flag_nocf GR64:$src, (add_su GR64:$src, -1)),
             (BLSR64rr GR64:$src)>;
 
-  def : Pat<(xor_flag_nocf GR32:$src, (add GR32:$src, -1)),
+  def : Pat<(xor_flag_nocf GR32:$src, (add_su GR32:$src, -1)),
             (BLSMSK32rr GR32:$src)>;
-  def : Pat<(xor_flag_nocf GR64:$src, (add GR64:$src, -1)),
+  def : Pat<(xor_flag_nocf GR64:$src, (add_su GR64:$src, -1)),
             (BLSMSK64rr GR64:$src)>;
 
-  def : Pat<(and_flag_nocf GR32:$src, (ineg GR32:$src)),
+  def : Pat<(and_flag_nocf GR32:$src, (ineg_su GR32:$src)),
             (BLSI32rr GR32:$src)>;
-  def : Pat<(and_flag_nocf GR64:$src, (ineg GR64:$src)),
+  def : Pat<(and_flag_nocf GR64:$src, (ineg_su GR64:$src)),
             (BLSI64rr GR64:$src)>;
 }
 
 multiclass bmi_bextr<bits<8> opc, string mnemonic, RegisterClass RC,
                      X86MemOperand x86memop, SDNode OpNode,
                      PatFrag ld_frag, X86FoldableSchedWrite Sched> {
   def rr : I<opc, MRMSrcReg4VOp3, (outs RC:$dst), (ins RC:$src1, RC:$src2),
              !strconcat(mnemonic, "\t{$src2, $src1, $dst|$dst, $src1, $src2}"),

llvm/test/CodeGen/X86/GlobalISel/select-blsi.mir

registers:
   - { id: 2, class: gpr }
   - { id: 3, class: gpr }
 # G_SUB and G_AND both use %0 so we should match this.
 body:             |
   bb.1:
     liveins: $edi
 
     ; CHECK-LABEL: name: test_blsi32rr
-    ; CHECK: [[COPY:%[0-9]+]]:gr32 = COPY $edi
-    ; CHECK: [[BLSI32rr:%[0-9]+]]:gr32 = BLSI32rr [[COPY]], implicit-def $eflags
-    ; CHECK: $edi = COPY [[BLSI32rr]]
+    ; CHECK: liveins: $edi
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: [[COPY:%[0-9]+]]:gr32 = COPY $edi
+    ; CHECK-NEXT: [[MOV32r0_:%[0-9]+]]:gr32 = MOV32r0 implicit-def $eflags
+    ; CHECK-NEXT: [[SUB32rr:%[0-9]+]]:gr32 = SUB32rr [[MOV32r0_]], [[COPY]], implicit-def $eflags
+    ; CHECK-NEXT: [[AND32rr:%[0-9]+]]:gr32 = AND32rr [[SUB32rr]], [[COPY]], implicit-def $eflags
+    ; CHECK-NEXT: $edi = COPY [[AND32rr]]
     %0(s32) = COPY $edi
     %1(s32) = G_CONSTANT i32 0
     %2(s32) = G_SUB %1, %0
     %3(s32) = G_AND %2, %0
     $edi = COPY %3
 
 ...
 ---
 name:            test_blsi32rr_nomatch
 alignment:       16
 legalized:       true
 regBankSelected: true
 registers:
   - { id: 0, class: gpr }
   - { id: 1, class: gpr }
   - { id: 2, class: gpr }
   - { id: 3, class: gpr }
 # G_SUB and G_AND use different operands so we shouldn't match this.
 body:             |
   bb.1:
     liveins: $edi
 
     ; CHECK-LABEL: name: test_blsi32rr_nomatch
-    ; CHECK: [[COPY:%[0-9]+]]:gr32 = COPY $edi
-    ; CHECK: [[MOV32r0_:%[0-9]+]]:gr32 = MOV32r0 implicit-def $eflags
-    ; CHECK: [[SUB32ri:%[0-9]+]]:gr32 = SUB32ri8 [[MOV32r0_]], 0, implicit-def $eflags
-    ; CHECK: [[AND32rr:%[0-9]+]]:gr32 = AND32rr [[SUB32ri]], [[COPY]], implicit-def $eflags
-    ; CHECK: $edi = COPY [[AND32rr]]
+    ; CHECK: liveins: $edi
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: [[COPY:%[0-9]+]]:gr32 = COPY $edi
+    ; CHECK-NEXT: [[MOV32r0_:%[0-9]+]]:gr32 = MOV32r0 implicit-def $eflags
+    ; CHECK-NEXT: [[SUB32ri8_:%[0-9]+]]:gr32 = SUB32ri8 [[MOV32r0_]], 0, implicit-def $eflags
+    ; CHECK-NEXT: [[AND32rr:%[0-9]+]]:gr32 = AND32rr [[SUB32ri8_]], [[COPY]], implicit-def $eflags
+    ; CHECK-NEXT: $edi = COPY [[AND32rr]]
     %0(s32) = COPY $edi
     %1(s32) = G_CONSTANT i32 0
     %2(s32) = G_SUB %1, %1
     %3(s32) = G_AND %2, %0
     $edi = COPY %3
 ...

llvm/test/CodeGen/X86/GlobalISel/select-blsr.mir

registers:
   - { id: 2, class: gpr }
   - { id: 3, class: gpr }
 # G_ADD and G_AND both use %0 so we should match this.
 body:             |
   bb.1:
     liveins: $edi
 
     ; CHECK-LABEL: name: test_blsr32rr
-    ; CHECK: [[COPY:%[0-9]+]]:gr32 = COPY $edi
-    ; CHECK: [[BLSR32rr:%[0-9]+]]:gr32 = BLSR32rr [[COPY]], implicit-def $eflags
-    ; CHECK: $edi = COPY [[BLSR32rr]]
+    ; CHECK: liveins: $edi
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: [[COPY:%[0-9]+]]:gr32 = COPY $edi
+    ; CHECK-NEXT: [[DEC32r:%[0-9]+]]:gr32 = DEC32r [[COPY]], implicit-def $eflags
+    ; CHECK-NEXT: [[AND32rr:%[0-9]+]]:gr32 = AND32rr [[DEC32r]], [[COPY]], implicit-def $eflags
+    ; CHECK-NEXT: $edi = COPY [[AND32rr]]
     %0(s32) = COPY $edi
     %1(s32) = G_CONSTANT i32 -1
     %2(s32) = G_ADD %0, %1
     %3(s32) = G_AND %2, %0
     $edi = COPY %3
 
 ...
 ---
 name:            test_blsr32rr_nomatch
 alignment:       16
 legalized:       true
 regBankSelected: true
 registers:
   - { id: 0, class: gpr }
   - { id: 1, class: gpr }
   - { id: 2, class: gpr }
   - { id: 3, class: gpr }
 # G_ADD and G_AND use different operands so we shouldn't match this.
 body:             |
   bb.1:
     liveins: $edi
 
     ; CHECK-LABEL: name: test_blsr32rr_nomatch
-    ; CHECK: [[COPY:%[0-9]+]]:gr32 = COPY $edi
-    ; CHECK: [[MOV32ri:%[0-9]+]]:gr32 = MOV32ri -1
-    ; CHECK: [[DEC32r:%[0-9]+]]:gr32 = DEC32r [[MOV32ri]], implicit-def $eflags
-    ; CHECK: [[AND32rr:%[0-9]+]]:gr32 = AND32rr [[DEC32r]], [[COPY]], implicit-def $eflags
-    ; CHECK: $edi = COPY [[AND32rr]]
+    ; CHECK: liveins: $edi
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: [[COPY:%[0-9]+]]:gr32 = COPY $edi
+    ; CHECK-NEXT: [[MOV32ri:%[0-9]+]]:gr32 = MOV32ri -1
+    ; CHECK-NEXT: [[DEC32r:%[0-9]+]]:gr32 = DEC32r [[MOV32ri]], implicit-def $eflags
+    ; CHECK-NEXT: [[AND32rr:%[0-9]+]]:gr32 = AND32rr [[DEC32r]], [[COPY]], implicit-def $eflags
+    ; CHECK-NEXT: $edi = COPY [[AND32rr]]
     %0(s32) = COPY $edi
     %1(s32) = G_CONSTANT i32 -1
     %2(s32) = G_ADD %1, %1
     %3(s32) = G_AND %2, %0
     $edi = COPY %3
 ...

llvm/test/CodeGen/X86/bmi-out-of-order.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=i686-unknown-unknown -mattr=+cmov,+bmi | FileCheck %s --check-prefix=X86
 ; RUN: llc < %s -mtriple=x86_64-unknown-unknown -mattr=+cmov,+bmi | FileCheck %s --check-prefix=X64
 
 source_filename = "/home/noah/.tmp/objdumps/test.c-2023-01-06-T18-38-57.o.c"
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define i32 @blsmsk_used2(i32 %a) nounwind {
 ; X86-LABEL: blsmsk_used2:
 ; X86:       # %bb.0: # %entry
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    blsmskl %eax, %ecx
-; X86-NEXT:    decl %eax
+; X86-NEXT:    leal -1(%eax), %ecx
+; X86-NEXT:    xorl %ecx, %eax
 ; X86-NEXT:    imull %ecx, %eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: blsmsk_used2:
 ; X64:       # %bb.0: # %entry
 ; X64-NEXT:    # kill: def $edi killed $edi def $rdi
-; X64-NEXT:    blsmskl %edi, %ecx
 ; X64-NEXT:    leal -1(%rdi), %eax
-; X64-NEXT:    imull %ecx, %eax
+; X64-NEXT:    xorl %eax, %edi
+; X64-NEXT:    imull %edi, %eax
 ; X64-NEXT:    retq
 entry:
   %sub = add i32 %a, -1
   %xor = xor i32 %sub, %a
   %mul = mul i32 %xor, %sub
   ret i32 %mul
 }
 
entry:
   %or = or i64 %mul, %xor1
   ret i64 %or
 }
 
 define i32 @blsi_used2(i32 %a) nounwind {
 ; X86-LABEL: blsi_used2:
 ; X86:       # %bb.0: # %entry
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    blsil %eax, %ecx
-; X86-NEXT:    negl %eax
+; X86-NEXT:    movl %eax, %ecx
+; X86-NEXT:    negl %ecx
+; X86-NEXT:    andl %ecx, %eax
 ; X86-NEXT:    imull %ecx, %eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: blsi_used2:
 ; X64:       # %bb.0: # %entry
-; X64-NEXT:    blsil %edi, %eax
-; X64-NEXT:    negl %edi
+; X64-NEXT:    movl %edi, %eax
+; X64-NEXT:    negl %eax
+; X64-NEXT:    andl %eax, %edi
 ; X64-NEXT:    imull %edi, %eax
 ; X64-NEXT:    retq
 entry:
   %sub = sub nsw i32 0, %a
   %and = and i32 %sub, %a
   %mul = mul nsw i32 %and, %sub
   ret i32 %mul
 }
entry:
   %or = or i64 %mul, %and1
   ret i64 %or
 }
 
 define i32 @blsr_used2(i32 %a) nounwind {
 ; X86-LABEL: blsr_used2:
 ; X86:       # %bb.0: # %entry
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    blsrl %eax, %ecx
-; X86-NEXT:    decl %eax
+; X86-NEXT:    leal -1(%eax), %ecx
+; X86-NEXT:    andl %ecx, %eax
 ; X86-NEXT:    imull %ecx, %eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: blsr_used2:
 ; X64:       # %bb.0: # %entry
 ; X64-NEXT:    # kill: def $edi killed $edi def $rdi
-; X64-NEXT:    blsrl %edi, %ecx
 ; X64-NEXT:    leal -1(%rdi), %eax
-; X64-NEXT:    imull %ecx, %eax
+; X64-NEXT:    andl %eax, %edi
+; X64-NEXT:    imull %edi, %eax
 ; X64-NEXT:    retq
 entry:
   %sub = add i32 %a, -1
   %and = and i32 %sub, %a
   %mul = mul i32 %and, %sub
   ret i32 %mul
 }