[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.

49091

Space after if

49092

Over indented

52008

Space after if

52009

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

                               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.getNode());
+  // 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))
+    for (unsigned OpIdx = 0; OpIdx < 2; ++OpIdx) {
+      if (isAllOnesConstant(Op.getOperand(OpIdx)) &&
+          Op.getOperand(1 - OpIdx) == 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();

               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");
 

       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:    blsmskl %esi, %eax
 ; X64-NEXT:    xorl %edx, %edi
-; X64-NEXT:    xorl %esi, %edi
-; X64-NEXT:    leal -1(%rsi), %eax
 ; X64-NEXT:    xorl %edi, %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:    blsil %esi, %eax
 ; X64-NEXT:    andl %edx, %edi
-; X64-NEXT:    andl %esi, %edi
-; X64-NEXT:    negl %eax
 ; X64-NEXT:    andl %edi, %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:    blsiq %rsi, %rax
 ; X64-NEXT:    andq %rdx, %rdi
-; X64-NEXT:    andq %rsi, %rdi
-; X64-NEXT:    negq %rax
 ; X64-NEXT:    andq %rdi, %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:    blsrl %esi, %eax
 ; X64-NEXT:    andl %edx, %edi
-; X64-NEXT:    andl %esi, %edi
-; X64-NEXT:    leal -1(%rsi), %eax
 ; X64-NEXT:    andl %edi, %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