[X86] Move X86DAGToDAGISel::matchBEXTRFromAnd() into X86ISelLowering

[lebedev.ri]

Summary

As discussed in PR38938,
we fail to emit BEXTR if the mask is shifted.
We can't deal with that in X86DAGToDAGISel before the address mode for the inc is selected,
and we can't really do it in the normal DAGCombine, because we don't have generic ISD::BitFieldExtract node,
and if we simply turn the shifted mask into a normal mask + shift-left, it will be folded back.
So it would seem X86ISelLowering is the place to handle this.

[lebedev.ri]

test/CodeGen/X86/tbm_patterns.ll

52–64 ↗

(On Diff #166697)

This seems to be a miscompile, BEXTR does not touch EFLAGS?

[lebedev.ri]

test/CodeGen/X86/tbm_patterns.ll

52–64 ↗

(On Diff #166697)

Aha, it is not, i just can't read.
http://www.felixcloutier.com/x86/BEXTR.html#flags-affected

[craig.topper]

lib/Target/X86/X86ISelLowering.cpp

35252 ↗

(On Diff #166697)

Remove the call to dump.

35308 ↗

(On Diff #166697)

Remove call to dump.

test/CodeGen/X86/extract-bits.ll

5797 ↗

(On Diff #166697)

This is not an improvement. We traded a shift right plus an and for a move immediate, a 2 uop bextr, and a shift left. So we went from 2 uops to 4. At least on Haswell.

[lebedev.ri]

Thank you for taking a look!

test/CodeGen/X86/extract-bits.ll

5797 ↗

(On Diff #166697)

Aha. So the D52293 has the same problem, obviously.
Is adding FeatureSlowBEXTR the way forward?

[craig.topper]

test/CodeGen/X86/extract-bits.ll

5797 ↗

(On Diff #166697)

It's still an increase in instruction even on AMD in the BMI1 case. We still went from 2 uops to 3 uops. We'd only be ok with BEXTRI TBM instruction.

In the case from PR38938 we were able to fold the shl into an addressing calculation which made it beneficial.

[craig.topper]

I'm not sure matchBEXTRFromAnd() for BMI was ever a good idea for Intel CPUs. I took it out and got performance improvements on several benchmarks in our internal list. Only a couple regressions and one of those was on a test that's really sensitive to code layout.

[lebedev.ri]

In D52426#1246032, @craig.topper wrote:

We'd only be ok with BEXTRI TBM instruction.
I'm not sure matchBEXTRFromAnd() for BMI was ever a good idea for Intel CPUs. I took it out and got performance improvements on several benchmarks in our internal list. Only a couple regressions and one of those was on a test that's really sensitive to code layout.
In the case from PR38938 we were able to fold the shl into an addressing calculation which made it beneficial.

Okay, so these simple cases are ok if there is TBM.
But the PR38938 - AMD Jaguar - does not have TBM.
There really isn't any fundamental difference in the IR between this, and the D52293,
so i would have guessed they should be using the *same* profitability check, correct?
So what would it be? "have TBM, or shifting a newly-loaded value?"
@RKSimon

[RKSimon]

@lebedev.ri Are you able to refactor this now that D52570 has landed?

[lebedev.ri]

In D52426#1250354, @RKSimon wrote:

@lebedev.ri Are you able to refactor this now that D52570 has landed?

Rebased now that D52570 has landed.

[RKSimon]

Can you remove the D52293 dependency and just move the current code to DAG so we can fix PR38938?

[lebedev.ri]

Drop parent review.

[RKSimon]

lib/Target/X86/X86ISelLowering.cpp

35245 ↗

(On Diff #167721)

Most of this could be replaced with:

return (VT == MVT::i32 || (VT == MVT::i64 && Subtarget.is64Bit()));

35261 ↗

(On Diff #167721)

You could just use the EVT value all the way through if you changed hasBEXTR to take an EVT instead of MVT

[lebedev.ri]

Consistently use EVT.

[craig.topper]

lib/Target/X86/X86ISelLowering.cpp

35407 ↗

(On Diff #167788)

This should probably be below the LegalizeOps check. We should give ample opportunity for AND based DAG combines to optimize this.

[lebedev.ri]

Move to after isBeforeLegalizeOps().

lib/Target/X86/X86ISelLowering.cpp

35407 ↗

(On Diff #167788)

I'm not sure about the test for this.
Also, should it be *right* after the isBeforeLegalizeOps(), or somewhere at the end of the block?

[lebedev.ri]

Ping.

[RKSimon]

lib/Target/X86/X86ISelLowering.cpp

35249 ↗

(On Diff #167790)

asserts should have a message

test/CodeGen/X86/bmi-x86_64.ll

105 ↗

(On Diff #167790)

Why is this call non_bextr64?

[lebedev.ri]

test/CodeGen/X86/bmi-x86_64.ll

105 ↗

(On Diff #167790)

That is how you named it when adding in rL232580 / https://github.com/llvm-mirror/llvm/commit/cbaefea0c0c1792390375b20c31b7c1fe8d0d2c7
Should i rename it?

105 ↗

(On Diff #167790)

Whoops, typo, s/you//.
Still, should i rename it?

[RKSimon]

I'm a bit worried about these test changes - I thought this patch was about moving the existing code, not altering the pattern matching features.

[lebedev.ri]

In D52426#1260326, @RKSimon wrote:

I'm a bit worried about these test changes - I thought this patch was about moving the existing code, not altering the pattern matching features.

I guess i mislabelled it then. Please see the description of this differential for the context.
Would it be better to split this into a NFC code move + non-NFC "support shifted mask"?

[lebedev.ri]

Split into two reviews.
This only moves the code, but one test still changes..

[RKSimon]

LGTM - thanks

[lebedev.ri]

In D52426#1260519, @RKSimon wrote:

LGTM - thanks

Thank you for the review!

[craig.topper]

For the PR we're trying to fix, perhaps we should be looking at these 3 similar functions in X86ISelDAGToDAG.cpp that are called when an address computation comes from a SHL+AND

if (!foldMaskAndShiftToExtract(*CurDAG, N, Mask, Shift, X, AM))
  return false;

// Try to fold the mask and shift directly into the scale.
if (!foldMaskAndShiftToScale(*CurDAG, N, Mask, Shift, X, AM))
  return false;

// Try to swap the mask and shift to place shifts which can be done as
// a scale on the outside of the mask.
if (!foldMaskedShiftToScaledMask(*CurDAG, N, Mask, Shift, X, AM))
  return false;

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

bool useNonTemporalLoad(LoadSDNode *N) const {
       case 32:
         return Subtarget->hasAVX2();
       case 64:
         return Subtarget->hasAVX512();
       }
     }
 
     bool foldLoadStoreIntoMemOperand(SDNode *Node);
-    bool matchBEXTRFromAnd(SDNode *Node);
     bool shrinkAndImmediate(SDNode *N);
     bool isMaskZeroExtended(SDNode *N) const;
     bool tryShiftAmountMod(SDNode *N);
 
     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,
bool X86DAGToDAGISel::foldLoadStoreIntoMemOperand(SDNode *Node) {
   // Update Load Chain uses as well.
   ReplaceUses(SDValue(LoadNode, 1), SDValue(Result, 1));
   ReplaceUses(SDValue(StoreNode, 0), SDValue(Result, 1));
   ReplaceUses(SDValue(StoredVal.getNode(), 1), SDValue(Result, 0));
   CurDAG->RemoveDeadNode(Node);
   return true;
 }
 
-// See if this is an (X >> C1) & C2 that we can match to BEXTR/BEXTRI.
-bool X86DAGToDAGISel::matchBEXTRFromAnd(SDNode *Node) {
-  MVT NVT = Node->getSimpleValueType(0);
-  SDLoc dl(Node);
-
-  SDValue N0 = Node->getOperand(0);
-  SDValue N1 = Node->getOperand(1);
-
-  // If we have TBM we can use an immediate for the control. If we have BMI
-  // we should only do this if the BEXTR instruction is implemented well.
-  // Otherwise moving the control into a register makes this more costly.
-  // TODO: Maybe load folding, greater than 32-bit masks, or a guarantee of LICM
-  // hoisting the move immediate would make it worthwhile with a less optimal
-  // BEXTR?
-  if (!Subtarget->hasTBM() &&
-      !(Subtarget->hasBMI() && Subtarget->hasFastBEXTR()))
-    return false;
-
-  // Must have a shift right.
-  if (N0->getOpcode() != ISD::SRL && N0->getOpcode() != ISD::SRA)
-    return false;
-
-  // Shift can't have additional users.
-  if (!N0->hasOneUse())
-    return false;
-
-  // Only supported for 32 and 64 bits.
-  if (NVT != MVT::i32 && NVT != MVT::i64)
-    return false;
-
-  // Shift amount and RHS of and must be constant.
-  ConstantSDNode *MaskCst = dyn_cast<ConstantSDNode>(N1);
-  ConstantSDNode *ShiftCst = dyn_cast<ConstantSDNode>(N0->getOperand(1));
-  if (!MaskCst || !ShiftCst)
-    return false;
-
-  // And RHS must be a mask.
-  uint64_t Mask = MaskCst->getZExtValue();
-  if (!isMask_64(Mask))
-    return false;
-
-  uint64_t Shift = ShiftCst->getZExtValue();
-  uint64_t MaskSize = countPopulation(Mask);
-
-  // Don't interfere with something that can be handled by extracting AH.
-  // TODO: If we are able to fold a load, BEXTR might still be better than AH.
-  if (Shift == 8 && MaskSize == 8)
-    return false;
-
-  // Make sure we are only using bits that were in the original value, not
-  // shifted in.
-  if (Shift + MaskSize > NVT.getSizeInBits())
-    return false;
-
-  // Create a BEXTR node and run it through selection.
-  SDValue C = CurDAG->getConstant(Shift | (MaskSize << 8), dl, NVT);
-  SDValue New = CurDAG->getNode(X86ISD::BEXTR, dl, NVT,
-                                N0->getOperand(0), C);
-  ReplaceNode(Node, New.getNode());
-  SelectCode(New.getNode());
-  return true;
-}
-
 // Emit a PCMISTR(I/M) instruction.
 MachineSDNode *X86DAGToDAGISel::emitPCMPISTR(unsigned ROpc, unsigned MOpc,
                                              bool MayFoldLoad, const SDLoc &dl,
                                              MVT VT, SDNode *Node) {
   SDValue N0 = Node->getOperand(0);
   SDValue N1 = Node->getOperand(1);
   SDValue Imm = Node->getOperand(2);
   const ConstantInt *Val = cast<ConstantSDNode>(Imm)->getConstantIntValue();
void X86DAGToDAGISel::Select(SDNode *Node) {
   case ISD::SRL:
   case ISD::SRA:
   case ISD::SHL:
     if (tryShiftAmountMod(Node))
       return;
     break;
 
   case ISD::AND:
-    if (matchBEXTRFromAnd(Node))
-      return;
     if (AndImmShrink && shrinkAndImmediate(Node))
       return;
 
     LLVM_FALLTHROUGH;
   case ISD::OR:
   case ISD::XOR: {
 
     // For operations of the form (x << C1) op C2, check if we can use a smaller

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

if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(MemOp)) {
           return DAG.getNode(ISD::AND, dl, VT, Inp, LShr);
         }
       }
     }
   }
   return SDValue();
 }
 
+static bool hasBEXTR(const X86Subtarget &Subtarget, EVT VT) {
+  // If we have TBM we can use an immediate for the control. If we have BMI
+  // we should only do this if the BEXTR instruction is implemented well.
+  // Otherwise moving the control into a register makes this more costly.
+  // TODO: Maybe load folding, greater than 32-bit masks, or a guarantee of LICM
+  // hoisting the move immediate would make it worthwhile with a less optimal
+  // BEXTR?
+  if (!Subtarget.hasTBM() && !(Subtarget.hasBMI() && Subtarget.hasFastBEXTR()))
+    return false;
+  return (VT == MVT::i32 || (VT == MVT::i64 && Subtarget.is64Bit()));
+}
+
+// See if this is an (X >> C1) & C2 that we can match to BEXTR/BEXTRI.
+static SDValue combineAndIntoBEXTR(SDNode *Node, SelectionDAG &DAG,
+                                   const X86Subtarget &Subtarget) {
+  EVT NVT = Node->getValueType(0);
+  SDLoc dl(Node);
+
+  SDValue N0 = Node->getOperand(0);
+  SDValue N1 = Node->getOperand(1);
+
+  // Check if subtarget has BEXTR instruction for the node's type
+  if (!hasBEXTR(Subtarget, NVT))
+    return SDValue();
+
+  // Must have a shift right.
+  if (N0->getOpcode() != ISD::SRL && N0->getOpcode() != ISD::SRA)
+    return SDValue();
+
+  // Shift can't have additional users.
+  if (!N0->hasOneUse())
+    return SDValue();
+
+  // Shift amount and RHS of and must be constant.
+  ConstantSDNode *MaskCst = dyn_cast<ConstantSDNode>(N1);
+  ConstantSDNode *ShiftCst = dyn_cast<ConstantSDNode>(N0->getOperand(1));
+  if (!MaskCst || !ShiftCst)
+    return SDValue();
+
+  // And RHS must be a mask.
+  uint64_t Mask = MaskCst->getZExtValue();
+  if (!isMask_64(Mask))
+    return SDValue();
+
+  uint64_t Shift = ShiftCst->getZExtValue();
+  uint64_t MaskSize = countPopulation(Mask);
+
+  // Don't interfere with something that can be handled by extracting AH.
+  // TODO: If we are able to fold a load, BEXTR might still be better than AH.
+  if (Shift == 8 && MaskSize == 8)
+    return SDValue();
+
+  // Make sure we are only using bits that were in the original value, not
+  // shifted in.
+  if (Shift + MaskSize > NVT.getSizeInBits())
+    return SDValue();
+
+  // Create a BEXTR node.
+  SDValue C = DAG.getConstant(Shift | (MaskSize << 8), dl, NVT);
+  SDValue New = DAG.getNode(X86ISD::BEXTR, dl, NVT, N0->getOperand(0), C);
+  return New;
+}
+
 // Look for (and (ctpop X), 1) which is the IR form of __builtin_parity.
 // Turn it into series of XORs and a setnp.
 static SDValue combineParity(SDNode *N, SelectionDAG &DAG,
                              const X86Subtarget &Subtarget) {
   EVT VT = N->getValueType(0);
 
   // We only support 64-bit and 32-bit. 64-bit requires special handling
   // unless the 64-bit popcnt instruction is legal.
static SDValue combineAnd(SDNode *N, SelectionDAG &DAG,
 
   // This must be done before legalization has expanded the ctpop.
   if (SDValue V = combineParity(N, DAG, Subtarget))
     return V;
 
   if (DCI.isBeforeLegalizeOps())
     return SDValue();
 
+  if (SDValue R = combineAndIntoBEXTR(N, DAG, Subtarget))
+    return R;
+
   if (SDValue R = combineCompareEqual(N, DAG, DCI, Subtarget))
     return R;
 
   if (SDValue FPLogic = convertIntLogicToFPLogic(N, DAG, Subtarget))
     return FPLogic;
 
   if (SDValue R = combineANDXORWithAllOnesIntoANDNP(N, DAG))
     return R;

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

; CHECK-NEXT:    retq
   %t3 = select i1 %t2, i32 %b, i32 %t1
   ret i32 %t3
 }
 
 define i32 @test_x86_tbm_bextri_u32_z2(i32 %a, i32 %b, i32 %c) nounwind {
 ; CHECK-LABEL: test_x86_tbm_bextri_u32_z2:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movl %esi, %eax
-; CHECK-NEXT:    shrl $4, %edi
-; CHECK-NEXT:    testl $4095, %edi # imm = 0xFFF
+; CHECK-NEXT:    bextrl $3076, %edi, %ecx # imm = 0xC04
 ; CHECK-NEXT:    cmovnel %edx, %eax
 ; CHECK-NEXT:    retq
   %t0 = lshr i32 %a, 4
   %t1 = and i32 %t0, 4095
   %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_bextri_u64_z2(i64 %a, i64 %b, i64 %c) nounwind {
 ; CHECK-LABEL: test_x86_tbm_bextri_u64_z2:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movq %rsi, %rax
-; CHECK-NEXT:    shrl $4, %edi
-; CHECK-NEXT:    testl $4095, %edi # imm = 0xFFF
+; CHECK-NEXT:    bextrl $3076, %edi, %ecx # imm = 0xC04
 ; CHECK-NEXT:    cmovneq %rdx, %rax
 ; CHECK-NEXT:    retq
   %t0 = lshr i64 %a, 4
   %t1 = and i64 %t0, 4095
   %t2 = icmp eq i64 %t1, 0
   %t3 = select i1 %t2, i64 %b, i64 %c
   ret i64 %t3
 }