[X86] Add isel patterns to match BMI/TBMI instructions when lowering has turned the root nodes into one of the flag producing binops.

[craig.topper]

Summary

This fixes the patterns that have or/and as a root. 'and' is still broken because lowering keeps a CMP and we match it and the and to TEST. To fix this we'll probably need some custom code in X86ISelDAGToDAG or something. I had to look for uses of the CF flag because all these nodes have non-standard CF flag behavior. A real or/xor would always clear CF. In practice we shouldn't be using the CF flag from these nodes as far as I know.

[craig.topper]

Ping

[RKSimon]

LGTM - Are those FIXMEs for and roots listed in a bugzilla anywhere?

[craig.topper]

I can drop the AND FIXME. We got that fixed in D55870.

llvm/trunk/lib/Target/X86/X86ISelDAGToDAG.cpp

private:
 
     MachineSDNode *emitPCMPISTR(unsigned ROpc, unsigned MOpc, bool MayFoldLoad,
                                 const SDLoc &dl, MVT VT, SDNode *Node);
     MachineSDNode *emitPCMPESTR(unsigned ROpc, unsigned MOpc, bool MayFoldLoad,
                                 const SDLoc &dl, MVT VT, SDNode *Node,
                                 SDValue &InFlag);
 
     bool tryOptimizeRem8Extend(SDNode *N);
+
+    bool hasNoSignFlagUses(SDValue Flags) const;
+    bool hasNoCarryFlagUses(SDValue Flags) const;
   };
 }
 
 
 // Returns true if this masked compare can be implemented legally with this
 // type.
 static bool isLegalMaskCompare(SDNode *N, const X86Subtarget *Subtarget) {
   unsigned Opcode = N->getOpcode();
static X86::CondCode getCondFromOpc(unsigned Opc) {
   if (CC == X86::COND_INVALID)
     CC = X86::getCondFromCMovOpc(Opc);
 
   return CC;
 }
 
 /// Test whether the given X86ISD::CMP node has any uses which require the SF
 /// flag to be accurate.
-static bool hasNoSignFlagUses(SDValue Flags) {
+bool X86DAGToDAGISel::hasNoSignFlagUses(SDValue Flags) const {
   // Examine each user of the node.
   for (SDNode::use_iterator UI = Flags->use_begin(), UE = Flags->use_end();
          UI != UE; ++UI) {
     // Only check things that use the flags.
     if (UI.getUse().getResNo() != Flags.getResNo())
       continue;
     // Only examine CopyToReg uses that copy to EFLAGS.
     if (UI->getOpcode() != ISD::CopyToReg ||
for (SDNode::use_iterator FlagUI = UI->use_begin(),
       }
     }
   }
   return true;
 }
 
 /// Test whether the given node which sets flags has any uses which require the
 /// CF flag to be accurate.
-static bool hasNoCarryFlagUses(SDValue Flags) {
+ bool X86DAGToDAGISel::hasNoCarryFlagUses(SDValue Flags) const {
   // Examine each user of the node.
   for (SDNode::use_iterator UI = Flags->use_begin(), UE = Flags->use_end();
          UI != UE; ++UI) {
     // Only check things that use the flags.
     if (UI.getUse().getResNo() != Flags.getResNo())
       continue;
     // Only examine CopyToReg uses that copy to EFLAGS.
     if (UI->getOpcode() != ISD::CopyToReg ||

llvm/trunk/lib/Target/X86/X86InstrInfo.td

let Predicates = [HasBMI], Defs = [EFLAGS] in {
   defm BLSI32 : bmi_bls<"blsi{l}", MRM3r, MRM3m, GR32, i32mem>;
   defm BLSI64 : bmi_bls<"blsi{q}", MRM3r, MRM3m, GR64, i64mem>, VEX_W;
 }
 
 //===----------------------------------------------------------------------===//
 // Pattern fragments to auto generate BMI instructions.
 //===----------------------------------------------------------------------===//
 
+def or_flag_nocf : PatFrag<(ops node:$lhs, node:$rhs),
+                           (X86or_flag node:$lhs, node:$rhs), [{
+  return hasNoCarryFlagUses(SDValue(N, 1));
+}]>;
+
+def xor_flag_nocf : PatFrag<(ops node:$lhs, node:$rhs),
+                            (X86xor_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)),
             (BLSR32rr GR32:$src)>;
   def : Pat<(and GR64:$src, (add GR64:$src, -1)),
             (BLSR64rr GR64:$src)>;
 
   def : Pat<(xor GR32:$src, (add GR32:$src, -1)),
             (BLSMSK32rr GR32:$src)>;
   def : Pat<(xor GR64:$src, (add GR64:$src, -1)),
             (BLSMSK64rr GR64:$src)>;
 
   def : Pat<(and GR32:$src, (ineg GR32:$src)),
             (BLSI32rr GR32:$src)>;
   def : Pat<(and GR64:$src, (ineg GR64:$src)),
             (BLSI64rr GR64:$src)>;
+
+  // Versions to match flag producing ops.
+  // X86and_flag nodes are rarely created. Those should use CMP+AND. We do
+  // TESTrr matching in PostProcessISelDAG to allow BLSR/BLSI to be formed.
+  def : Pat<(xor_flag_nocf GR32:$src, (add GR32:$src, -1)),
+            (BLSMSK32rr GR32:$src)>;
+  def : Pat<(xor_flag_nocf GR64:$src, (add GR64:$src, -1)),
+            (BLSMSK64rr 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}"),
              [(set RC:$dst, (OpNode RC:$src1, RC:$src2)), (implicit EFLAGS)]>,
def : Pat<(or (not GR32:$src), (add GR32:$src, 1)),
             (T1MSKC32rr GR32:$src)>;
   def : Pat<(or (not GR64:$src), (add GR64:$src, 1)),
             (T1MSKC64rr GR64:$src)>;
 
   def : Pat<(and (not GR32:$src), (add GR32:$src, -1)),
             (TZMSK32rr GR32:$src)>;
   def : Pat<(and (not GR64:$src), (add GR64:$src, -1)),
             (TZMSK64rr GR64:$src)>;
+
+  // Patterns to match flag producing ops.
+  // X86and_flag nodes are rarely created. Those should use CMP+AND. We do
+  // TESTrr matching in PostProcessISelDAG to allow BLSR/BLSI to be formed.
+  def : Pat<(or_flag_nocf GR32:$src, (not (add GR32:$src, 1))),
+            (BLCI32rr GR32:$src)>;
+  def : Pat<(or_flag_nocf GR64:$src, (not (add GR64:$src, 1))),
+            (BLCI64rr GR64:$src)>;
+
+  // Extra patterns because opt can optimize the above patterns to this.
+  def : Pat<(or_flag_nocf GR32:$src, (sub -2, GR32:$src)),
+            (BLCI32rr GR32:$src)>;
+  def : Pat<(or_flag_nocf GR64:$src, (sub -2, GR64:$src)),
+            (BLCI64rr GR64:$src)>;
+
+  def : Pat<(xor_flag_nocf GR32:$src, (add GR32:$src, 1)),
+            (BLCMSK32rr GR32:$src)>;
+  def : Pat<(xor_flag_nocf GR64:$src, (add GR64:$src, 1)),
+            (BLCMSK64rr GR64:$src)>;
+
+  def : Pat<(or_flag_nocf GR32:$src, (add GR32:$src, 1)),
+            (BLCS32rr GR32:$src)>;
+  def : Pat<(or_flag_nocf GR64:$src, (add GR64:$src, 1)),
+            (BLCS64rr GR64:$src)>;
+
+  def : Pat<(or_flag_nocf GR32:$src, (add GR32:$src, -1)),
+            (BLSFILL32rr GR32:$src)>;
+  def : Pat<(or_flag_nocf GR64:$src, (add GR64:$src, -1)),
+            (BLSFILL64rr GR64:$src)>;
+
+  def : Pat<(or_flag_nocf (not GR32:$src), (add GR32:$src, -1)),
+            (BLSIC32rr GR32:$src)>;
+  def : Pat<(or_flag_nocf (not GR64:$src), (add GR64:$src, -1)),
+            (BLSIC64rr GR64:$src)>;
+
+  def : Pat<(or_flag_nocf (not GR32:$src), (add GR32:$src, 1)),
+            (T1MSKC32rr GR32:$src)>;
+  def : Pat<(or_flag_nocf (not GR64:$src), (add GR64:$src, 1)),
+            (T1MSKC64rr GR64:$src)>;
 } // HasTBM
 
 //===----------------------------------------------------------------------===//
 // Memory Instructions
 //
 
 let Predicates = [HasCLFLUSHOPT], SchedRW = [WriteLoad] in
 def CLFLUSHOPT : I<0xAE, MRM7m, (outs), (ins i8mem:$src),

llvm/trunk/test/CodeGen/X86/bmi.ll

; X64-NEXT:    retq
   %t2 = icmp eq i32 %t1, 0
   %t3 = select i1 %t2, i32 %b, i32 %t1
   ret i32 %t3
 }
 
 define i32 @blsmsk32_z2(i32 %a, i32 %b, i32 %c) nounwind {
 ; X86-LABEL: blsmsk32_z2:
 ; X86:       # %bb.0:
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    leal -1(%eax), %ecx
-; X86-NEXT:    xorl %eax, %ecx
+; X86-NEXT:    blsmskl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    leal {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    leal {{[0-9]+}}(%esp), %ecx
 ; X86-NEXT:    cmovel %eax, %ecx
 ; X86-NEXT:    movl (%ecx), %eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: blsmsk32_z2:
 ; X64:       # %bb.0:
 ; X64-NEXT:    movl %esi, %eax
-; X64-NEXT:    # kill: def $edi killed $edi def $rdi
-; X64-NEXT:    leal -1(%rdi), %ecx
-; X64-NEXT:    xorl %edi, %ecx
+; X64-NEXT:    blsmskl %edi, %ecx
 ; X64-NEXT:    cmovnel %edx, %eax
 ; X64-NEXT:    retq
   %t0 = sub i32 %a, 1
   %t1 = xor i32 %t0, %a
   %t2 = icmp eq i32 %t1, 0
   %t3 = select i1 %t2, i32 %b, i32 %c
   ret i32 %t3
 }

 ; X86-NEXT:    movl (%ecx), %eax
 ; X86-NEXT:    movl 4(%ecx), %edx
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: blsmsk64_z2:
 ; X64:       # %bb.0:
 ; X64-NEXT:    movq %rsi, %rax
-; X64-NEXT:    leaq -1(%rdi), %rcx
-; X64-NEXT:    xorq %rdi, %rcx
+; X64-NEXT:    blsmskq %rdi, %rcx
 ; X64-NEXT:    cmovneq %rdx, %rax
 ; X64-NEXT:    retq
   %t0 = sub i64 %a, 1
   %t1 = xor i64 %t0, %a
   %t2 = icmp eq i64 %t1, 0
   %t3 = select i1 %t2, i64 %b, i64 %c
   ret i64 %t3
 }

llvm/trunk/test/CodeGen/X86/tbm_patterns.ll

; CHECK-NEXT:    retq
   %t4 = select i1 %t3, i32 %b, i32 %t2
   ret i32 %t4
 }
 
 define i32 @test_x86_tbm_blci_u32_z2(i32 %a, i32 %b, i32 %c) nounwind {
 ; CHECK-LABEL: test_x86_tbm_blci_u32_z2:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movl %esi, %eax
-; CHECK-NEXT:    # kill: def $edi killed $edi def $rdi
-; CHECK-NEXT:    leal 1(%rdi), %ecx
-; CHECK-NEXT:    notl %ecx
-; CHECK-NEXT:    orl %edi, %ecx
+; CHECK-NEXT:    blcil %edi, %ecx
 ; CHECK-NEXT:    cmovnel %edx, %eax
 ; CHECK-NEXT:    retq
   %t0 = add i32 1, %a
   %t1 = xor i32 %t0, -1
   %t2 = or i32 %t1, %a
   %t3 = icmp eq i32 %t2, 0
   %t4 = select i1 %t3, i32 %b, i32 %c
   ret i32 %t4
; CHECK-NEXT:    retq
   %t4 = select i1 %t3, i64 %b, i64 %t2
   ret i64 %t4
 }
 
 define i64 @test_x86_tbm_blci_u64_z2(i64 %a, i64 %b, i64 %c) nounwind {
 ; CHECK-LABEL: test_x86_tbm_blci_u64_z2:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movq %rsi, %rax
-; CHECK-NEXT:    leaq 1(%rdi), %rcx
-; CHECK-NEXT:    notq %rcx
-; CHECK-NEXT:    orq %rdi, %rcx
+; CHECK-NEXT:    blciq %rdi, %rcx
 ; CHECK-NEXT:    cmovneq %rdx, %rax
 ; CHECK-NEXT:    retq
   %t0 = add i64 1, %a
   %t1 = xor i64 %t0, -1
   %t2 = or i64 %t1, %a
   %t3 = icmp eq i64 %t2, 0
   %t4 = select i1 %t3, i64 %b, i64 %c
   ret i64 %t4
; CHECK-NEXT:    retq
   %t3 = select i1 %t2, i32 %b, i32 %t1
   ret i32 %t3
 }
 
 define i32 @test_x86_tbm_blcmsk_u32_z2(i32 %a, i32 %b, i32 %c) nounwind {
 ; CHECK-LABEL: test_x86_tbm_blcmsk_u32_z2:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movl %esi, %eax
-; CHECK-NEXT:    # kill: def $edi killed $edi def $rdi
-; CHECK-NEXT:    leal 1(%rdi), %ecx
-; CHECK-NEXT:    xorl %edi, %ecx
+; CHECK-NEXT:    blcmskl %edi, %ecx
 ; CHECK-NEXT:    cmovnel %edx, %eax
 ; CHECK-NEXT:    retq
   %t0 = add i32 %a, 1
   %t1 = xor i32 %t0, %a
   %t2 = icmp eq i32 %t1, 0
   %t3 = select i1 %t2, i32 %b, i32 %c
   ret i32 %t3
 }
; CHECK-NEXT:    retq
   %t3 = select i1 %t2, i64 %b, i64 %t1
   ret i64 %t3
 }
 
 define i64 @test_x86_tbm_blcmsk_u64_z2(i64 %a, i64 %b, i64 %c) nounwind {
 ; CHECK-LABEL: test_x86_tbm_blcmsk_u64_z2:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movq %rsi, %rax
-; CHECK-NEXT:    leaq 1(%rdi), %rcx
-; CHECK-NEXT:    xorq %rdi, %rcx
+; CHECK-NEXT:    blcmskq %rdi, %rcx
 ; CHECK-NEXT:    cmovneq %rdx, %rax
 ; CHECK-NEXT:    retq
   %t0 = add i64 %a, 1
   %t1 = xor i64 %t0, %a
   %t2 = icmp eq i64 %t1, 0
   %t3 = select i1 %t2, i64 %b, i64 %c
   ret i64 %t3
 }
; CHECK-NEXT:    retq
   %t3 = select i1 %t2, i32 %b, i32 %t1
   ret i32 %t3
 }
 
 define i32 @test_x86_tbm_blcs_u32_z2(i32 %a, i32 %b, i32 %c) nounwind {
 ; CHECK-LABEL: test_x86_tbm_blcs_u32_z2:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movl %esi, %eax
-; CHECK-NEXT:    # kill: def $edi killed $edi def $rdi
-; CHECK-NEXT:    leal 1(%rdi), %ecx
-; CHECK-NEXT:    orl %edi, %ecx
+; CHECK-NEXT:    blcsl %edi, %ecx
 ; CHECK-NEXT:    cmovnel %edx, %eax
 ; CHECK-NEXT:    retq
   %t0 = add i32 %a, 1
   %t1 = or i32 %t0, %a
   %t2 = icmp eq i32 %t1, 0
   %t3 = select i1 %t2, i32 %b, i32 %c
   ret i32 %t3
 }
; CHECK-NEXT:    retq
   %t3 = select i1 %t2, i64 %b, i64 %t1
   ret i64 %t3
 }
 
 define i64 @test_x86_tbm_blcs_u64_z2(i64 %a, i64 %b, i64 %c) nounwind {
 ; CHECK-LABEL: test_x86_tbm_blcs_u64_z2:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movq %rsi, %rax
-; CHECK-NEXT:    leaq 1(%rdi), %rcx
-; CHECK-NEXT:    orq %rdi, %rcx
+; CHECK-NEXT:    blcsq %rdi, %rcx
 ; CHECK-NEXT:    cmovneq %rdx, %rax
 ; CHECK-NEXT:    retq
   %t0 = add i64 %a, 1
   %t1 = or i64 %t0, %a
   %t2 = icmp eq i64 %t1, 0
   %t3 = select i1 %t2, i64 %b, i64 %c
   ret i64 %t3
 }
; CHECK-NEXT:    retq
   %t3 = select i1 %t2, i32 %b, i32 %t1
   ret i32 %t3
 }
 
 define i32 @test_x86_tbm_blsfill_u32_z2(i32 %a, i32 %b, i32 %c) nounwind {
 ; CHECK-LABEL: test_x86_tbm_blsfill_u32_z2:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movl %esi, %eax
-; CHECK-NEXT:    # kill: def $edi killed $edi def $rdi
-; CHECK-NEXT:    leal -1(%rdi), %ecx
-; CHECK-NEXT:    orl %edi, %ecx
+; CHECK-NEXT:    blsfilll %edi, %ecx
 ; CHECK-NEXT:    cmovnel %edx, %eax
 ; CHECK-NEXT:    retq
   %t0 = add i32 %a, -1
   %t1 = or i32 %t0, %a
   %t2 = icmp eq i32 %t1, 0
   %t3 = select i1 %t2, i32 %b, i32 %c
   ret i32 %t3
 }
; CHECK-NEXT:    retq
   %t3 = select i1 %t2, i64 %b, i64 %t1
   ret i64 %t3
 }
 
 define i64 @test_x86_tbm_blsfill_u64_z2(i64 %a, i64 %b, i64 %c) nounwind {
 ; CHECK-LABEL: test_x86_tbm_blsfill_u64_z2:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movq %rsi, %rax
-; CHECK-NEXT:    leaq -1(%rdi), %rcx
-; CHECK-NEXT:    orq %rdi, %rcx
+; CHECK-NEXT:    blsfillq %rdi, %rcx
 ; CHECK-NEXT:    cmovneq %rdx, %rax
 ; CHECK-NEXT:    retq
   %t0 = add i64 %a, -1
   %t1 = or i64 %t0, %a
   %t2 = icmp eq i64 %t1, 0
   %t3 = select i1 %t2, i64 %b, i64 %c
   ret i64 %t3
 }
; CHECK-NEXT:    retq
   %t4 = select i1 %t3, i32 %b, i32 %t2
   ret i32 %t4
 }
 
 define i32 @test_x86_tbm_blsic_u32_z2(i32 %a, i32 %b, i32 %c) nounwind {
 ; CHECK-LABEL: test_x86_tbm_blsic_u32_z2:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movl %esi, %eax
-; CHECK-NEXT:    movl %edi, %ecx
-; CHECK-NEXT:    notl %ecx
-; CHECK-NEXT:    decl %edi
-; CHECK-NEXT:    orl %ecx, %edi
+; CHECK-NEXT:    blsicl %edi, %ecx
 ; CHECK-NEXT:    cmovnel %edx, %eax
 ; CHECK-NEXT:    retq
   %t0 = xor i32 %a, -1
   %t1 = add i32 %a, -1
   %t2 = or i32 %t0, %t1
   %t3 = icmp eq i32 %t2, 0
   %t4 = select i1 %t3, i32 %b, i32 %c
   ret i32 %t4
; CHECK-NEXT:    retq
   %t4 = select i1 %t3, i64 %b, i64 %t2
   ret i64 %t4
 }
 
 define i64 @test_x86_tbm_blsic_u64_z2(i64 %a, i64 %b, i64 %c) nounwind {
 ; CHECK-LABEL: test_x86_tbm_blsic_u64_z2:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movq %rsi, %rax
-; CHECK-NEXT:    movq %rdi, %rcx
-; CHECK-NEXT:    notq %rcx
-; CHECK-NEXT:    decq %rdi
-; CHECK-NEXT:    orq %rcx, %rdi
+; CHECK-NEXT:    blsicq %rdi, %rcx
 ; CHECK-NEXT:    cmovneq %rdx, %rax
 ; CHECK-NEXT:    retq
   %t0 = xor i64 %a, -1
   %t1 = add i64 %a, -1
   %t2 = or i64 %t0, %t1
   %t3 = icmp eq i64 %t2, 0
   %t4 = select i1 %t3, i64 %b, i64 %c
   ret i64 %t4
; CHECK-NEXT:    retq
   %t4 = select i1 %t3, i32 %b, i32 %t2
   ret i32 %t4
 }
 
 define i32 @test_x86_tbm_t1mskc_u32_z2(i32 %a, i32 %b, i32 %c) nounwind {
 ; CHECK-LABEL: test_x86_tbm_t1mskc_u32_z2:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movl %esi, %eax
-; CHECK-NEXT:    movl %edi, %ecx
-; CHECK-NEXT:    notl %ecx
-; CHECK-NEXT:    incl %edi
-; CHECK-NEXT:    orl %ecx, %edi
+; CHECK-NEXT:    t1mskcl %edi, %ecx
 ; CHECK-NEXT:    cmovnel %edx, %eax
 ; CHECK-NEXT:    retq
   %t0 = xor i32 %a, -1
   %t1 = add i32 %a, 1
   %t2 = or i32 %t0, %t1
   %t3 = icmp eq i32 %t2, 0
   %t4 = select i1 %t3, i32 %b, i32 %c
   ret i32 %t4
; CHECK-NEXT:    retq
   %t4 = select i1 %t3, i64 %b, i64 %t2
   ret i64 %t4
 }
 
 define i64 @test_x86_tbm_t1mskc_u64_z2(i64 %a, i64 %b, i64 %c) nounwind {
 ; CHECK-LABEL: test_x86_tbm_t1mskc_u64_z2:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movq %rsi, %rax
-; CHECK-NEXT:    movq %rdi, %rcx
-; CHECK-NEXT:    notq %rcx
-; CHECK-NEXT:    incq %rdi
-; CHECK-NEXT:    orq %rcx, %rdi
+; CHECK-NEXT:    t1mskcq %rdi, %rcx
 ; CHECK-NEXT:    cmovneq %rdx, %rax
 ; CHECK-NEXT:    retq
   %t0 = xor i64 %a, -1
   %t1 = add i64 %a, 1
   %t2 = or i64 %t0, %t1
   %t3 = icmp eq i64 %t2, 0
   %t4 = select i1 %t3, i64 %b, i64 %c
   ret i64 %t4