[X86] Search through associative operators for BMI patterns (BLSI, BLSR, BLSMSK)

[goldstein.w.n]

Summary

(a & (-b)) & b is often lowered as:

%sub  = sub i32     0, %b
%and0 = and i32  %sub, %a
%and1 = and i32 %and0, %b

Which won't get detected by the BLSI pattern as b & -b are never in
the same SDNode.

This patch will do a small search through associative operators and try
and place BMI patterns in the same node so they will hit the pattern.

[craig.topper]

Isn’t the property “associative” rather than “commutative”?

[craig.topper]

llvm/lib/Target/X86/X86ISelLowering.cpp

48801

Do not use all caps for OPC

48808

If you only look through binops without going through bitcasts, extends, or truncates, you can assume the types will always match.

48828

You can use isNullConstant(Op.getOperand(0) here.

48837

isOneConstant(Op.getOperand(1))

48846

isAllOnesConstant(Op.getOperand(OpIdx)

48854

Lower case start of function name

48858

Just check VT != MVT::i32 && VT != MVT::i64 unless you're trying to support i33-i63?

48865

You can drop all the curly braces here.

49096

Space after if

49097

Over indented

52013

Space after if

52014

Over indented

[goldstein.w.n]

Fix format issues.
Remove unneeded code.
Cleanup code.

[goldstein.w.n]

Change commutable -> assosative in commit / code.

[goldstein.w.n]

Remove unneeded braces in a few more places

[goldstein.w.n]

ping.

[goldstein.w.n]

ping.

[goldstein.w.n]

ping2.

[pengfei]

llvm/lib/Target/X86/X86ISelLowering.cpp

48807

Add period in the end. The same for others below.

48811

SDLoc DL(Op);

48841

Can we assume it is canonical and just check operand 1?

[goldstein.w.n]

Fix nits + rebase

[pengfei]

LGTM.

[goldstein.w.n]

@pengfei I was thinking patch, is it liable to cause an infinite loop? Its just reordering and another place might undo its changes. Maybe it makes more sense in X86::ISelDAGToDag?

llvm/lib/Target/X86/X86ISelLowering.cpp

static unsigned convertIntLogicToFPLogicOpcode(unsigned Opcode) {
   case ISD::OR:  FPOpcode = X86ISD::FOR;  break;
   case ISD::XOR: FPOpcode = X86ISD::FXOR; break;
   }
   return FPOpcode;
 }
 
 /// If both input operands of a logic op are being cast from floating-point
 /// types or FP compares, try to convert this into a floating-point logic node
 /// to avoid unnecessary moves from SSE to integer registers.
 static SDValue convertIntLogicToFPLogic(SDNode *N, SelectionDAG &DAG,
                                         TargetLowering::DAGCombinerInfo &DCI,
                                         const X86Subtarget &Subtarget) {
   EVT VT = N->getValueType(0);
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   SDLoc DL(N);
 
   if (!((N0.getOpcode() == ISD::BITCAST && N1.getOpcode() == ISD::BITCAST) ||
         (N0.getOpcode() == ISD::SETCC && N1.getOpcode() == ISD::SETCC)))
     return SDValue();
 
   SDValue N00 = N0.getOperand(0);
   SDValue N10 = N1.getOperand(0);
   EVT N00Type = N00.getValueType();
   EVT N10Type = N10.getValueType();
 
   // Ensure that both types are the same and are legal scalar fp types.
   if (N00Type != N10Type || !((Subtarget.hasSSE1() && N00Type == MVT::f32) ||
                               (Subtarget.hasSSE2() && N00Type == MVT::f64) ||
                               (Subtarget.hasFP16() && N00Type == MVT::f16)))
     return SDValue();
 
   if (N0.getOpcode() == ISD::BITCAST && !DCI.isBeforeLegalizeOps()) {
     unsigned FPOpcode = convertIntLogicToFPLogicOpcode(N->getOpcode());
     SDValue FPLogic = DAG.getNode(FPOpcode, DL, N00Type, N00, N10);
     return DAG.getBitcast(VT, FPLogic);
   }
 
   if (VT != MVT::i1 || N0.getOpcode() != ISD::SETCC || !N0.hasOneUse() ||
       !N1.hasOneUse())
     return SDValue();
 
   ISD::CondCode CC0 = cast<CondCodeSDNode>(N0.getOperand(2))->get();
   ISD::CondCode CC1 = cast<CondCodeSDNode>(N1.getOperand(2))->get();
 
   // The vector ISA for FP predicates is incomplete before AVX, so converting
   // COMIS* to CMPS* may not be a win before AVX.
   if (!Subtarget.hasAVX() &&
       !(cheapX86FSETCC_SSE(CC0) && cheapX86FSETCC_SSE(CC1)))
     return SDValue();
 
   // Convert scalar FP compares and logic to vector compares (COMIS* to CMPS*)
   // and vector logic:
   // logic (setcc N00, N01), (setcc N10, N11) -->
   // extelt (logic (setcc (s2v N00), (s2v N01)), setcc (s2v N10), (s2v N11))), 0
   unsigned NumElts = 128 / N00Type.getSizeInBits();
   EVT VecVT = EVT::getVectorVT(*DAG.getContext(), N00Type, NumElts);
   EVT BoolVecVT = EVT::getVectorVT(*DAG.getContext(), MVT::i1, NumElts);
   SDValue ZeroIndex = DAG.getVectorIdxConstant(0, DL);
   SDValue N01 = N0.getOperand(1);
   SDValue N11 = N1.getOperand(1);
   SDValue Vec00 = DAG.getNode(ISD::SCALAR_TO_VECTOR, DL, VecVT, N00);
   SDValue Vec01 = DAG.getNode(ISD::SCALAR_TO_VECTOR, DL, VecVT, N01);
   SDValue Vec10 = DAG.getNode(ISD::SCALAR_TO_VECTOR, DL, VecVT, N10);
   SDValue Vec11 = DAG.getNode(ISD::SCALAR_TO_VECTOR, DL, VecVT, N11);
   SDValue Setcc0 = DAG.getSetCC(DL, BoolVecVT, Vec00, Vec01, CC0);
   SDValue Setcc1 = DAG.getSetCC(DL, BoolVecVT, Vec10, Vec11, CC1);
   SDValue Logic = DAG.getNode(N->getOpcode(), DL, BoolVecVT, Setcc0, Setcc1);
   return DAG.getNode(ISD::EXTRACT_VECTOR_ELT, DL, VT, Logic, ZeroIndex);
 }
 
 // Attempt to fold BITOP(MOVMSK(X),MOVMSK(Y)) -> MOVMSK(BITOP(X,Y))
 // to reduce XMM->GPR traffic.
 static SDValue combineBitOpWithMOVMSK(SDNode *N, SelectionDAG &DAG) {
   unsigned Opc = N->getOpcode();
   assert((Opc == ISD::OR || Opc == ISD::AND || Opc == ISD::XOR) &&
          "Unexpected bit opcode");
 
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
 
if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(MemOp)) {
             if (Elem->getZExtValue() != (((uint64_t)1 << j) - 1)) {
               ConstantsMatch = false;
               break;
             }
           }
           if (!ConstantsMatch)
             continue;
 
           // Do the transformation (For 32-bit type):
           // -> (and (load arr[idx]), inp)
           // <- (and (srl 0xFFFFFFFF, (sub 32, idx)))
           //    that will be replaced with one bzhi instruction.
           SDValue Inp = (i == 0) ? Node->getOperand(1) : Node->getOperand(0);
           SDValue SizeC = DAG.getConstant(VT.getSizeInBits(), dl, MVT::i32);
 
           // Get the Node which indexes into the array.
           SDValue Index = getIndexFromUnindexedLoad(Ld);
           if (!Index)
SmallVector<SDValue, 4> Ops(Src.getNumOperands(),
                               DAG.getConstant(0, dl, SubVecVT));
   Ops[0] = SubVec;
   SDValue Concat = DAG.getNode(ISD::CONCAT_VECTORS, dl, SrcVT,
                                Ops);
   EVT IntVT = EVT::getIntegerVT(*DAG.getContext(), SrcVT.getSizeInBits());
   return DAG.getZExtOrTrunc(DAG.getBitcast(IntVT, Concat), dl, VT);
 }
 
+static SDValue getBMIMatchingOp(unsigned Opc, SelectionDAG &DAG,
+                                SDValue OpMustEq, SDValue Op, unsigned Depth) {
+  // We don't want to go crazy with the recursion here. This isn't a super
+  // important optimization.
+  static constexpr unsigned kMaxDepth = 2;
+
+  // Only do this re-ordering if op has one use.
+  if (!Op.hasOneUse())
+    return SDValue();
+
+  SDLoc DL(Op);
+  // If we hit another assosiative op, recurse further.
+  if (Op.getOpcode() == Opc) {
+    // Done recursing.
+    if (Depth++ >= kMaxDepth)
+      return SDValue();
+
+    for (unsigned OpIdx = 0; OpIdx < 2; ++OpIdx)
+      if (SDValue R =
+              getBMIMatchingOp(Opc, DAG, OpMustEq, Op.getOperand(OpIdx), Depth))
+        return DAG.getNode(Op.getOpcode(), DL, Op.getValueType(), R,
+                           Op.getOperand(1 - OpIdx));
+
+  } else if (Op.getOpcode() == ISD::SUB) {
+    if (Opc == ISD::AND) {
+      // BLSI: (and x, (sub 0, x))
+      if (isNullConstant(Op.getOperand(0)) && Op.getOperand(1) == OpMustEq)
+        return DAG.getNode(Opc, DL, Op.getValueType(), OpMustEq, Op);
+    }
+    // Opc must be ISD::AND or ISD::XOR
+    // BLSR: (and x, (sub x, 1))
+    // BLSMSK: (xor x, (sub x, 1))
+    if (isOneConstant(Op.getOperand(1)) && Op.getOperand(0) == OpMustEq)
+      return DAG.getNode(Opc, DL, Op.getValueType(), OpMustEq, Op);
+
+  } else if (Op.getOpcode() == ISD::ADD) {
+    // Opc must be ISD::AND or ISD::XOR
+    // BLSR: (and x, (add x, -1))
+    // BLSMSK: (xor x, (add x, -1))
+    if (isAllOnesConstant(Op.getOperand(1)) && Op.getOperand(0) == OpMustEq)
+      return DAG.getNode(Opc, DL, Op.getValueType(), OpMustEq, Op);
+  }
+  return SDValue();
+}
+
+static SDValue combineBMILogicOp(SDNode *N, SelectionDAG &DAG,
+                                 const X86Subtarget &Subtarget) {
+  EVT VT = N->getValueType(0);
+  // Make sure this node is a candidate for BMI instructions.
+  if (!Subtarget.hasBMI() || !VT.isScalarInteger() ||
+      (VT != MVT::i32 && VT != MVT::i64))
+    return SDValue();
+
+  assert(N->getOpcode() == ISD::AND || N->getOpcode() == ISD::XOR);
+
+  // Try and match LHS and RHS.
+  for (unsigned OpIdx = 0; OpIdx < 2; ++OpIdx)
+    if (SDValue OpMatch =
+            getBMIMatchingOp(N->getOpcode(), DAG, N->getOperand(OpIdx),
+                             N->getOperand(1 - OpIdx), 0))
+      return OpMatch;
+  return SDValue();
+}
+
 static SDValue combineAnd(SDNode *N, SelectionDAG &DAG,
                           TargetLowering::DAGCombinerInfo &DCI,
                           const X86Subtarget &Subtarget) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   EVT VT = N->getValueType(0);
   SDLoc dl(N);
   const TargetLowering &TLI = DAG.getTargetLoweringInfo();
if (VT == SrcVecVT.getScalarType() && N0->isOnlyUserOf(SrcVec.getNode()) &&
               X86::MaxShuffleCombineDepth,
               /*HasVarMask*/ false, /*AllowVarCrossLaneMask*/ true,
               /*AllowVarPerLaneMask*/ true, DAG, Subtarget))
         return DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, VT, Shuffle,
                            N0.getOperand(1));
     }
   }
 
+  if (SDValue R = combineBMILogicOp(N, DAG, Subtarget))
+    return R;
+
   return SDValue();
 }
 
 // Canonicalize OR(AND(X,C),AND(Y,~C)) -> OR(AND(X,C),ANDNP(C,Y))
 static SDValue canonicalizeBitSelect(SDNode *N, SelectionDAG &DAG,
                                      const X86Subtarget &Subtarget) {
   assert(N->getOpcode() == ISD::OR && "Unexpected Opcode");
 
static SDValue combineTruncate(SDNode *N, SelectionDAG &DAG,
   // The bitcast source is a direct mmx result.
   // Detect bitcasts between i32 to x86mmx
   if (Src.getOpcode() == ISD::BITCAST && VT == MVT::i32) {
     SDValue BCSrc = Src.getOperand(0);
     if (BCSrc.getValueType() == MVT::x86mmx)
       return DAG.getNode(X86ISD::MMX_MOVD2W, DL, MVT::i32, BCSrc);
   }
 
   // Try to truncate extended sign/zero bits with PACKSS/PACKUS.
   if (SDValue V = combineVectorSignBitsTruncation(N, DL, DAG, Subtarget))
     return V;
 
   return combineVectorTruncation(N, DAG, Subtarget);
 }
 
 static SDValue combineVTRUNC(SDNode *N, SelectionDAG &DAG,
                              TargetLowering::DAGCombinerInfo &DCI) {
   EVT VT = N->getValueType(0);
if (N1C && !N1C->isOpaque() && N001C && !N001C->isOpaque()) {
       SDLoc DL(N);
       SDValue LHS = DAG.getZExtOrTrunc(TruncExtSrc.getOperand(0), DL, VT);
       SDValue RHS = DAG.getZExtOrTrunc(TruncExtSrc.getOperand(1), DL, VT);
       return DAG.getNode(ISD::XOR, DL, VT, LHS,
                          DAG.getNode(ISD::XOR, DL, VT, RHS, N1));
     }
   }
 
+  if (SDValue R = combineBMILogicOp(N, DAG, Subtarget))
+    return R;
+
   return combineFneg(N, DAG, DCI, Subtarget);
 }
 
 static SDValue combineBEXTR(SDNode *N, SelectionDAG &DAG,
                             TargetLowering::DAGCombinerInfo &DCI,
                             const X86Subtarget &Subtarget) {
   EVT VT = N->getValueType(0);
   unsigned NumBits = VT.getSizeInBits();

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

 ; X86-NEXT:    xorl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    xorl %ecx, %eax
 ; X86-NEXT:    xorl %esi, %edx
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: blsmask_through1:
 ; X64:       # %bb.0: # %entry
-; X64-NEXT:    xorq %rsi, %rdi
-; X64-NEXT:    leaq -1(%rsi), %rax
+; X64-NEXT:    blsmskq %rsi, %rax
 ; X64-NEXT:    xorq %rdi, %rax
 ; X64-NEXT:    retq
 entry:
   %sub = add i64 %b, -1
   %0 = xor i64 %sub, %a
   %xor1 = xor i64 %0, %b
   ret i64 %xor1
 }
 
 define i32 @blsmask_through2(i32 %a, i32 %b, i32 %c) nounwind {
 ; X86-LABEL: blsmask_through2:
 ; X86:       # %bb.0: # %entry
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    leal -1(%ecx), %eax
+; X86-NEXT:    blsmskl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    xorl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    xorl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    xorl %ecx, %eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: blsmask_through2:
 ; X64:       # %bb.0: # %entry
-; X64-NEXT:    # kill: def $esi killed $esi def $rsi
-; X64-NEXT:    leal -1(%rsi), %eax
+; X64-NEXT:    blsmskl %esi, %eax
 ; X64-NEXT:    xorl %edx, %edi
 ; X64-NEXT:    xorl %edi, %eax
-; X64-NEXT:    xorl %esi, %eax
 ; X64-NEXT:    retq
 entry:
   %sub = add nsw i32 %b, -1
   %0 = xor i32 %sub, %a
   %1 = xor i32 %0, %c
   %xor2 = xor i32 %1, %b
   ret i32 %xor2
 }

 ; X86-NEXT:    andl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    andl %esi, %edx
 ; X86-NEXT:    andl %ecx, %eax
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: blsi_through1:
 ; X64:       # %bb.0: # %entry
-; X64-NEXT:    movq %rsi, %rax
-; X64-NEXT:    andq %rsi, %rdi
-; X64-NEXT:    negq %rax
+; X64-NEXT:    blsiq %rsi, %rax
 ; X64-NEXT:    andq %rdi, %rax
 ; X64-NEXT:    retq
 entry:
   %sub = sub nsw i64 0, %b
   %and = and i64 %sub, %a
   %and1 = and i64 %and, %b
   ret i64 %and1
 }
 
 define i32 @blsi_through2(i32 %a, i32 %b, i32 %c) nounwind {
 ; X86-LABEL: blsi_through2:
 ; X86:       # %bb.0: # %entry
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    movl %ecx, %eax
-; X86-NEXT:    negl %eax
+; X86-NEXT:    blsil {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    andl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    andl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    andl %ecx, %eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: blsi_through2:
 ; X64:       # %bb.0: # %entry
-; X64-NEXT:    movl %esi, %eax
-; X64-NEXT:    negl %eax
+; X64-NEXT:    blsil %esi, %eax
 ; X64-NEXT:    andl %edx, %edi
 ; X64-NEXT:    andl %edi, %eax
-; X64-NEXT:    andl %esi, %eax
 ; X64-NEXT:    retq
 entry:
   %sub = sub i32 0, %b
   %and = and i32 %sub, %a
   %0 = and i32 %and, %c
   %and2 = and i32 %0, %b
   ret i32 %and2
 }

 ; X86-NEXT:    andl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    andl %esi, %edx
 ; X86-NEXT:    andl %ecx, %eax
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: blsi_through3:
 ; X64:       # %bb.0: # %entry
-; X64-NEXT:    movq %rsi, %rax
-; X64-NEXT:    negq %rax
+; X64-NEXT:    blsiq %rsi, %rax
 ; X64-NEXT:    andq %rdx, %rdi
 ; X64-NEXT:    andq %rdi, %rax
-; X64-NEXT:    andq %rsi, %rax
 ; X64-NEXT:    retq
 entry:
   %sub = sub i64 0, %b
   %and = and i64 %sub, %a
   %0 = and i64 %and, %c
   %and3 = and i64 %0, %b
   ret i64 %and3
 }

 ; X86-NEXT:    andl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    andl %ecx, %eax
 ; X86-NEXT:    andl %esi, %edx
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: blsr_through1:
 ; X64:       # %bb.0: # %entry
-; X64-NEXT:    andq %rsi, %rdi
-; X64-NEXT:    leaq -1(%rsi), %rax
+; X64-NEXT:    blsrq %rsi, %rax
 ; X64-NEXT:    andq %rdi, %rax
 ; X64-NEXT:    retq
 entry:
   %sub = add i64 %b, -1
   %0 = and i64 %sub, %a
   %and1 = and i64 %0, %b
   ret i64 %and1
 }
 
 define i32 @blsr_through2(i32 %a, i32 %b, i32 %c) nounwind {
 ; X86-LABEL: blsr_through2:
 ; X86:       # %bb.0: # %entry
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X86-NEXT:    leal -1(%ecx), %eax
+; X86-NEXT:    blsrl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    andl {{[0-9]+}}(%esp), %eax
 ; X86-NEXT:    andl {{[0-9]+}}(%esp), %eax
-; X86-NEXT:    andl %ecx, %eax
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: blsr_through2:
 ; X64:       # %bb.0: # %entry
-; X64-NEXT:    # kill: def $esi killed $esi def $rsi
-; X64-NEXT:    leal -1(%rsi), %eax
+; X64-NEXT:    blsrl %esi, %eax
 ; X64-NEXT:    andl %edx, %edi
 ; X64-NEXT:    andl %edi, %eax
-; X64-NEXT:    andl %esi, %eax
 ; X64-NEXT:    retq
 entry:
   %sub = add nsw i32 %b, -1
   %0 = and i32 %sub, %a
   %1 = and i32 %0, %c
   %and2 = and i32 %1, %b
   ret i32 %and2
 }