[X86] X86DAGToDAGISel::matchBitExtract(): pattern b: truncation awareness

[lebedev.ri]

Summary

(Not so) boringly identical to pattern a (D62786)
Not yet sure how do deal with the last pattern c.

[lebedev.ri]

Rebased

[lebedev.ri]

Rebased, extra test exposed an alternative way to still end up
with unrecognized pattern with truncation, so handle it too.

This resulted in inlining isBitwiseNot(), not sure if it would be better to extend it with all that instead?

[RKSimon]

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

8630

Could you not create an AllOnes equivalent MaskedValueIsZero instead? MaskedValueIsAllOnes?

[lebedev.ri]

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

8630

Err, s/not//?
"Could you create an AllOnes equivalent of MaskedValueIsZero instead? MaskedValueIsAllOnes?"

[lebedev.ri]

Introduce SelectionDAG::MaskedValueIsAllOnes().
Is this better?

[RKSimon]

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

8630

I don't think we need a DemandedElts variant so this should work.

/// MaskedValueIsAllOnes - Return true if 'V & Mask' is known to be all ones.
bool MaskedValueIsAllOnes(SDValue Op, const APInt &Mask, unsigned Depth = 0) const;

bool SelectionDAG::MaskedValueIsAllOnes(SDValue V, const APInt &Mask, unsigned Depth) const {
  return Mask.isSubsetOf(computeKnownBits(V, Depth).One);
}

[lebedev.ri]

Drop demandedelements variant

[RKSimon]

LGTM with one minor

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

2248

Remove this line - its MaskedValueIsZero specific

[lebedev.ri]

Rebased.

include/llvm/CodeGen/SelectionDAG.h

bool MaskedValueIsZero(SDValue Op, const APInt &Mask,
                          unsigned Depth = 0) const;
 
   /// Return true if 'Op & Mask' is known to be zero in DemandedElts.  We
   /// use this predicate to simplify operations downstream.  Op and Mask are
   /// known to be the same type.
   bool MaskedValueIsZero(SDValue Op, const APInt &Mask,
                          const APInt &DemandedElts, unsigned Depth = 0) const;
 
+  /// Return true if '(Op & Mask) == Mask'.
+  /// Op and Mask are known to be the same type.
+  bool MaskedValueIsAllOnes(SDValue Op, const APInt &Mask,
+                            unsigned Depth = 0) const;
+
   /// Determine which bits of Op are known to be either zero or one and return
   /// them in Known. For vectors, the known bits are those that are shared by
   /// every vector element.
   /// Targets can implement the computeKnownBitsForTargetNode method in the
   /// TargetLowering class to allow target nodes to be understood.
   KnownBits computeKnownBits(SDValue Op, unsigned Depth = 0) const;
 
   /// Determine which bits of Op are known to be either zero or one and return

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

 /// DemandedElts.  We use this predicate to simplify operations downstream.
 /// Mask is known to be zero for bits that V cannot have.
 bool SelectionDAG::MaskedValueIsZero(SDValue V, const APInt &Mask,
                                      const APInt &DemandedElts,
                                      unsigned Depth) const {
   return Mask.isSubsetOf(computeKnownBits(V, DemandedElts, Depth).Zero);
 }
 
+/// MaskedValueIsAllOnes - Return true if '(Op & Mask) == Mask'.
+/// Mask is known to be zero for bits that V cannot have.
+bool SelectionDAG::MaskedValueIsAllOnes(SDValue V, const APInt &Mask,
+                                        unsigned Depth) const {
+  return Mask.isSubsetOf(computeKnownBits(V, Depth).One);
+}
+
 /// isSplatValue - Return true if the vector V has the same value
 /// across all DemandedElts.
 bool SelectionDAG::isSplatValue(SDValue V, const APInt &DemandedElts,
                                 APInt &UndefElts) {
   if (!DemandedElts)
     return false; // No demanded elts, better to assume we don't know anything.
 
   EVT VT = V.getValueType();

 bool llvm::isAllOnesConstant(SDValue V) {
   ConstantSDNode *Const = dyn_cast<ConstantSDNode>(V);
   return Const != nullptr && Const->isAllOnesValue();
 }
 
 bool llvm::isOneConstant(SDValue V) {
   ConstantSDNode *Const = dyn_cast<ConstantSDNode>(V);
   return Const != nullptr && Const->isOne();
 }
 
 SDValue llvm::peekThroughBitcasts(SDValue V) {
   while (V.getOpcode() == ISD::BITCAST)
     V = V.getOperand(0);
   return V;
 }
 
 SDValue llvm::peekThroughOneUseBitcasts(SDValue V) {

lib/Target/X86/X86ISelDAGToDAG.cpp

auto matchPatternA = [&checkOneUse, peekThroughOneUseTruncation,
     if (M0->getOpcode() != ISD::SHL || !checkOneUse(M0))
       return false;
     if (!isOneConstant(M0->getOperand(0)))
       return false;
     NBits = M0->getOperand(1);
     return true;
   };
 
+  auto isAllOnes = [this, peekThroughOneUseTruncation, NVT](SDValue V) {
+    V = peekThroughOneUseTruncation(V);
+    return CurDAG->MaskedValueIsAllOnes(
+        V, APInt::getLowBitsSet(V.getSimpleValueType().getSizeInBits(),
+                                NVT.getSizeInBits()));
+  };
+
   // b) x & ~(-1 << nbits)
-  auto matchPatternB = [&checkOneUse, &NBits](SDValue Mask) -> bool {
+  auto matchPatternB = [&checkOneUse, isAllOnes, &peekThroughOneUseTruncation,
+                        &NBits](SDValue Mask) -> bool {
     // Match `~()`. Must only have one use!
-    if (!isBitwiseNot(Mask) || !checkOneUse(Mask))
+    if (Mask.getOpcode() != ISD::XOR || !checkOneUse(Mask))
       return false;
-    // Match `-1 << nbits`. Must only have one use!
-    SDValue M0 = Mask->getOperand(0);
+    // The -1 only has to be all-ones for the final Node's NVT.
+    if (!isAllOnes(Mask->getOperand(1)))
+      return false;
+    // Match `-1 << nbits`. Might be truncated. Must only have one use!
+    SDValue M0 = peekThroughOneUseTruncation(Mask->getOperand(0));
     if (M0->getOpcode() != ISD::SHL || !checkOneUse(M0))
       return false;
-    if (!isAllOnesConstant(M0->getOperand(0)))
+    // The -1 only has to be all-ones for the final Node's NVT.
+    if (!isAllOnes(M0->getOperand(0)))
       return false;
     NBits = M0->getOperand(1);
     return true;
   };
 
   // Match potentially-truncated (bitwidth - y)
   auto matchShiftAmt = [checkOneUse, Size, &NBits](SDValue ShiftAmt) {
     // Skip over a truncate of the shift amount.

test/CodeGen/X86/extract-bits.ll

 ; X64-NOBMI-NEXT:    shlq %cl, %rax
 ; X64-NOBMI-NEXT:    notl %eax
 ; X64-NOBMI-NEXT:    andl %edi, %eax
 ; X64-NOBMI-NEXT:    # kill: def $eax killed $eax killed $rax
 ; X64-NOBMI-NEXT:    retq
 ;
 ; X64-BMI1NOTBM-LABEL: bextr64_32_b0:
 ; X64-BMI1NOTBM:       # %bb.0:
-; X64-BMI1NOTBM-NEXT:    movq %rsi, %rcx
-; X64-BMI1NOTBM-NEXT:    # kill: def $cl killed $cl killed $rcx
-; X64-BMI1NOTBM-NEXT:    shrq %cl, %rdi
-; X64-BMI1NOTBM-NEXT:    movq $-1, %rax
-; X64-BMI1NOTBM-NEXT:    movl %edx, %ecx
-; X64-BMI1NOTBM-NEXT:    shlq %cl, %rax
-; X64-BMI1NOTBM-NEXT:    andnl %edi, %eax, %eax
+; X64-BMI1NOTBM-NEXT:    shll $8, %edx
+; X64-BMI1NOTBM-NEXT:    movzbl %sil, %eax
+; X64-BMI1NOTBM-NEXT:    orl %edx, %eax
+; X64-BMI1NOTBM-NEXT:    bextrq %rax, %rdi, %rax
+; X64-BMI1NOTBM-NEXT:    # kill: def $eax killed $eax killed $rax
 ; X64-BMI1NOTBM-NEXT:    retq
 ;
 ; X64-BMI1BMI2-LABEL: bextr64_32_b0:
 ; X64-BMI1BMI2:       # %bb.0:
-; X64-BMI1BMI2-NEXT:    # kill: def $edx killed $edx def $rdx
 ; X64-BMI1BMI2-NEXT:    shrxq %rsi, %rdi, %rax
-; X64-BMI1BMI2-NEXT:    movq $-1, %rcx
-; X64-BMI1BMI2-NEXT:    shlxq %rdx, %rcx, %rcx
-; X64-BMI1BMI2-NEXT:    andnl %eax, %ecx, %eax
+; X64-BMI1BMI2-NEXT:    bzhil %edx, %eax, %eax
 ; X64-BMI1BMI2-NEXT:    retq
   %shiftedval = lshr i64 %val, %numskipbits
   %widenumlowbits = zext i8 %numlowbits to i64
   %notmask = shl nsw i64 -1, %widenumlowbits
   %mask = xor i64 %notmask, -1
   %wideres = and i64 %shiftedval, %mask
   %res = trunc i64 %wideres to i32
   ret i32 %res

 ; X64-NOBMI-NEXT:    shlq %cl, %rsi
 ; X64-NOBMI-NEXT:    xorl %esi, %eax
 ; X64-NOBMI-NEXT:    andl %edi, %eax
 ; X64-NOBMI-NEXT:    # kill: def $eax killed $eax killed $rax
 ; X64-NOBMI-NEXT:    retq
 ;
 ; X64-BMI1NOTBM-LABEL: bextr64_32_b3:
 ; X64-BMI1NOTBM:       # %bb.0:
-; X64-BMI1NOTBM-NEXT:    movq %rsi, %rcx
-; X64-BMI1NOTBM-NEXT:    # kill: def $cl killed $cl killed $rcx
-; X64-BMI1NOTBM-NEXT:    shrq %cl, %rdi
-; X64-BMI1NOTBM-NEXT:    movl $4294967295, %eax # imm = 0xFFFFFFFF
-; X64-BMI1NOTBM-NEXT:    movl $4294967295, %esi # imm = 0xFFFFFFFF
-; X64-BMI1NOTBM-NEXT:    movl %edx, %ecx
-; X64-BMI1NOTBM-NEXT:    shlq %cl, %rsi
-; X64-BMI1NOTBM-NEXT:    xorl %esi, %eax
-; X64-BMI1NOTBM-NEXT:    andl %edi, %eax
+; X64-BMI1NOTBM-NEXT:    shll $8, %edx
+; X64-BMI1NOTBM-NEXT:    movzbl %sil, %eax
+; X64-BMI1NOTBM-NEXT:    orl %edx, %eax
+; X64-BMI1NOTBM-NEXT:    bextrq %rax, %rdi, %rax
 ; X64-BMI1NOTBM-NEXT:    # kill: def $eax killed $eax killed $rax
 ; X64-BMI1NOTBM-NEXT:    retq
 ;
 ; X64-BMI1BMI2-LABEL: bextr64_32_b3:
 ; X64-BMI1BMI2:       # %bb.0:
-; X64-BMI1BMI2-NEXT:    # kill: def $edx killed $edx def $rdx
 ; X64-BMI1BMI2-NEXT:    shrxq %rsi, %rdi, %rax
-; X64-BMI1BMI2-NEXT:    movl $4294967295, %ecx # imm = 0xFFFFFFFF
-; X64-BMI1BMI2-NEXT:    shlxq %rdx, %rcx, %rdx
-; X64-BMI1BMI2-NEXT:    xorl %edx, %ecx
-; X64-BMI1BMI2-NEXT:    andl %ecx, %eax
-; X64-BMI1BMI2-NEXT:    # kill: def $eax killed $eax killed $rax
+; X64-BMI1BMI2-NEXT:    bzhil %edx, %eax, %eax
 ; X64-BMI1BMI2-NEXT:    retq
   %shiftedval = lshr i64 %val, %numskipbits
   %widenumlowbits = zext i8 %numlowbits to i64
   %notmask = shl nsw i64 4294967295, %widenumlowbits
   %mask = xor i64 %notmask, 4294967295
   %wideres = and i64 %shiftedval, %mask
   %res = trunc i64 %wideres to i32
   ret i32 %res

test/CodeGen/X86/extract-lowbits.ll

 ; X64-NOBMI-NEXT:    shlq %cl, %rax
 ; X64-NOBMI-NEXT:    notl %eax
 ; X64-NOBMI-NEXT:    andl %edi, %eax
 ; X64-NOBMI-NEXT:    # kill: def $eax killed $eax killed $rax
 ; X64-NOBMI-NEXT:    retq
 ;
 ; X64-BMI1NOTBM-LABEL: bzhi64_32_b0:
 ; X64-BMI1NOTBM:       # %bb.0:
-; X64-BMI1NOTBM-NEXT:    movl %esi, %ecx
-; X64-BMI1NOTBM-NEXT:    movq $-1, %rax
-; X64-BMI1NOTBM-NEXT:    # kill: def $cl killed $cl killed $ecx
-; X64-BMI1NOTBM-NEXT:    shlq %cl, %rax
-; X64-BMI1NOTBM-NEXT:    andnl %edi, %eax, %eax
+; X64-BMI1NOTBM-NEXT:    shll $8, %esi
+; X64-BMI1NOTBM-NEXT:    bextrl %esi, %edi, %eax
 ; X64-BMI1NOTBM-NEXT:    retq
 ;
 ; X64-BMI1BMI2-LABEL: bzhi64_32_b0:
 ; X64-BMI1BMI2:       # %bb.0:
-; X64-BMI1BMI2-NEXT:    # kill: def $esi killed $esi def $rsi
-; X64-BMI1BMI2-NEXT:    movq $-1, %rax
-; X64-BMI1BMI2-NEXT:    shlxq %rsi, %rax, %rax
-; X64-BMI1BMI2-NEXT:    andnl %edi, %eax, %eax
+; X64-BMI1BMI2-NEXT:    bzhil %esi, %edi, %eax
 ; X64-BMI1BMI2-NEXT:    retq
   %widenumlowbits = zext i8 %numlowbits to i64
   %notmask = shl nsw i64 -1, %widenumlowbits
   %mask = xor i64 %notmask, -1
   %wideres = and i64 %val, %mask
   %res = trunc i64 %wideres to i32
   ret i32 %res
 }

 ; X64-NOBMI-NEXT:    shlq %cl, %rdx
 ; X64-NOBMI-NEXT:    xorl %edx, %eax
 ; X64-NOBMI-NEXT:    andl %edi, %eax
 ; X64-NOBMI-NEXT:    # kill: def $eax killed $eax killed $rax
 ; X64-NOBMI-NEXT:    retq
 ;
 ; X64-BMI1NOTBM-LABEL: bzhi64_32_b3:
 ; X64-BMI1NOTBM:       # %bb.0:
-; X64-BMI1NOTBM-NEXT:    movl %esi, %ecx
-; X64-BMI1NOTBM-NEXT:    movl $4294967295, %eax # imm = 0xFFFFFFFF
-; X64-BMI1NOTBM-NEXT:    movl $4294967295, %edx # imm = 0xFFFFFFFF
-; X64-BMI1NOTBM-NEXT:    # kill: def $cl killed $cl killed $ecx
-; X64-BMI1NOTBM-NEXT:    shlq %cl, %rdx
-; X64-BMI1NOTBM-NEXT:    xorl %edx, %eax
-; X64-BMI1NOTBM-NEXT:    andl %edi, %eax
-; X64-BMI1NOTBM-NEXT:    # kill: def $eax killed $eax killed $rax
+; X64-BMI1NOTBM-NEXT:    shll $8, %esi
+; X64-BMI1NOTBM-NEXT:    bextrl %esi, %edi, %eax
 ; X64-BMI1NOTBM-NEXT:    retq
 ;
 ; X64-BMI1BMI2-LABEL: bzhi64_32_b3:
 ; X64-BMI1BMI2:       # %bb.0:
-; X64-BMI1BMI2-NEXT:    # kill: def $esi killed $esi def $rsi
-; X64-BMI1BMI2-NEXT:    movl $4294967295, %eax # imm = 0xFFFFFFFF
-; X64-BMI1BMI2-NEXT:    shlxq %rsi, %rax, %rcx
-; X64-BMI1BMI2-NEXT:    xorl %ecx, %eax
-; X64-BMI1BMI2-NEXT:    andl %edi, %eax
-; X64-BMI1BMI2-NEXT:    # kill: def $eax killed $eax killed $rax
+; X64-BMI1BMI2-NEXT:    bzhil %esi, %edi, %eax
 ; X64-BMI1BMI2-NEXT:    retq
   %widenumlowbits = zext i8 %numlowbits to i64
   %notmask = shl nsw i64 4294967295, %widenumlowbits
   %mask = xor i64 %notmask, 4294967295
   %wideres = and i64 %val, %mask
   %res = trunc i64 %wideres to i32
   ret i32 %res
 }