[X86] CombineBT - more aggressively determine demanded bits

[RKSimon]

Summary

This patch is in 2 parts that can be committed separately if desired:

1 - replace combineBT's use of SimplifyDemandedBits (hasOneUse only) with SelectionDAG::GetDemandedBits to more aggressively determine the lower bits used by BT.

2 - update SelectionDAG::GetDemandedBits to support ANY_EXTEND - if the demanded bits are only in the non-extended portion, then peek through and demand from the source value and then ANY_EXTEND that if we found a match.

[craig.topper]

lib/CodeGen/SelectionDAG/SelectionDAG.cpp

2007 ↗

(On Diff #108296)

This doesn't seem right to me. Doesn't that get the upper SrcBitWidth bits of Mask? But the extended bits should be (BitWidth - SrcBitWidth) right?

But in any case can't this be 'if (Mask.getActiveBits() > SrcBitWidth)' which would avoid a temporary APInt.

[RKSimon]

Use APInt::getActiveBits to avoid temp APInt creation

[craig.topper]

LGTM

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

case ISD::SRL:
     break;
   case ISD::AND: {
     // X & -1 -> X (ignoring bits which aren't demanded).
     ConstantSDNode *AndVal = isConstOrConstSplat(V.getOperand(1));
     if (AndVal && Mask.isSubsetOf(AndVal->getAPIntValue()))
       return V.getOperand(0);
     break;
   }
+  case ISD::ANY_EXTEND: {
+    SDValue Src = V.getOperand(0);
+    unsigned SrcBitWidth = Src.getScalarValueSizeInBits();
+    // Being conservative here - only peek through if we only demand bits in the
+    // non-extended source (even though the extended bits are technically undef).
+    if (Mask.getActiveBits() > SrcBitWidth)
+      break;
+    APInt SrcMask = Mask.trunc(SrcBitWidth);
+    if (SDValue DemandedSrc = GetDemandedBits(Src, SrcMask))
+      return getNode(ISD::ANY_EXTEND, SDLoc(V), V.getValueType(), DemandedSrc);
+    break;
+  }
   }
   return SDValue();
 }
 
 /// SignBitIsZero - Return true if the sign bit of Op is known to be zero.  We
 /// use this predicate to simplify operations downstream.
 bool SelectionDAG::SignBitIsZero(SDValue Op, unsigned Depth) const {
   unsigned BitWidth = Op.getScalarValueSizeInBits();

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

if (combineX86ShufflesRecursively({Op}, 0, Op, NonceMask, {},
       return SDValue(); // This routine will use CombineTo to replace N.
   }
 
   return SDValue();
 }
 
 static SDValue combineBT(SDNode *N, SelectionDAG &DAG,
                          TargetLowering::DAGCombinerInfo &DCI) {
+  SDValue N0 = N->getOperand(0);
+  SDValue N1 = N->getOperand(1);
+
   // BT ignores high bits in the bit index operand.
-  SDValue Op1 = N->getOperand(1);
-  if (Op1.hasOneUse()) {
-    unsigned BitWidth = Op1.getValueSizeInBits();
-    APInt DemandedMask = APInt::getLowBitsSet(BitWidth, Log2_32(BitWidth));
-    KnownBits Known;
-    TargetLowering::TargetLoweringOpt TLO(DAG, !DCI.isBeforeLegalize(),
-                                          !DCI.isBeforeLegalizeOps());
-    const TargetLowering &TLI = DAG.getTargetLoweringInfo();
-    if (TLI.ShrinkDemandedConstant(Op1, DemandedMask, TLO) ||
-        TLI.SimplifyDemandedBits(Op1, DemandedMask, Known, TLO))
-      DCI.CommitTargetLoweringOpt(TLO);
-  }
+  unsigned BitWidth = N1.getValueSizeInBits();
+  if (SDValue DemandedN1 = DAG.GetDemandedBits(N1, DemandedMask))
+    return DAG.getNode(X86ISD::BT, SDLoc(N), MVT::i32, N0, DemandedN1);
+
   return SDValue();
 }
 
 static SDValue combineSignExtendInReg(SDNode *N, SelectionDAG &DAG,
                                       const X86Subtarget &Subtarget) {
   EVT VT = N->getValueType(0);
   if (!VT.isVector())
     return SDValue();

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

 ; X86-NEXT:    pushl %esi
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 ; X86-NEXT:    movl %ecx, %eax
 ; X86-NEXT:    shrl $5, %eax
 ; X86-NEXT:    movl (%edx,%eax,4), %esi
 ; X86-NEXT:    movl $1, %edx
 ; X86-NEXT:    shll %cl, %edx
-; X86-NEXT:    andb $31, %cl
-; X86-NEXT:    movzbl %cl, %ecx
 ; X86-NEXT:    btl %ecx, %esi
 ; X86-NEXT:    jae .LBB30_2
 ; X86-NEXT:  # BB#1:
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 ; X86-NEXT:    orl %edx, (%ecx,%eax,4)
 ; X86-NEXT:  .LBB30_2:
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: demanded_i32:
 ; X64:       # BB#0:
 ; X64-NEXT:    movl %edx, %eax
 ; X64-NEXT:    shrl $5, %eax
 ; X64-NEXT:    movl (%rdi,%rax,4), %r8d
 ; X64-NEXT:    movl $1, %edi
 ; X64-NEXT:    movl %edx, %ecx
 ; X64-NEXT:    shll %cl, %edi
-; X64-NEXT:    andb $31, %dl
-; X64-NEXT:    movzbl %dl, %ecx
-; X64-NEXT:    btl %ecx, %r8d
+; X64-NEXT:    btl %edx, %r8d
 ; X64-NEXT:    jae .LBB30_2
 ; X64-NEXT:  # BB#1:
 ; X64-NEXT:    orl %edi, (%rsi,%rax,4)
 ; X64-NEXT:  .LBB30_2:
 ; X64-NEXT:    retq
   %4 = lshr i32 %2, 5
   %5 = zext i32 %4 to i64
   %6 = getelementptr inbounds i32, i32* %0, i64 %5