[x86] improve CMOV codegen by pushing add into operands

[spatel]

Summary

This is not the transform direction we want in general, but by the time we have a CMOV, we've already tried everything else that could be better.
The transform increases the uses of the other add operand, but that is safe according to Alive2:
https://alive2.llvm.org/ce/z/Yn6p-A

We could probably extend this to other binops (not just add), but this is the motivating pattern discussed in:
https://llvm.org/PR51069

The test with i8 shows a missed fold because there's a trunc sitting in front of the add. I haven't checked to see what it would take to get that case.

[pengfei]

llvm/lib/Target/X86/X86ISelLowering.cpp

49872

Surprising to see the first operand is false operand. I saw we are taking it as true in same cases

def : Pat<(f128 (X86cmov VR128:$t, VR128:$f, timm:$cond, EFLAGS)),
          (CMOV_VR128 VR128:$t, VR128:$f, timm:$cond)>;

Which one is right?

[craig.topper]

llvm/lib/Target/X86/X86ISelLowering.cpp

49872

It should be false first. For non-pseudos false should be same as the dest operand making it a tied register which should be the first source operand. The comments in emitLoweredSelect which handle the pseudo also have false first.

[lebedev.ri]

Aha, yes, this late this is fine.
Looks good to me.
I guess you want to deal with i8 as a follow-up step?

llvm/lib/Target/X86/X86ISelLowering.cpp

49850

It's not really hoisting, pushAddThroughCmovOfConsts/pushAddIntoCmovOfConsts maybe or something?

49872

Unless i'm really misreading it, i believe the assembly is correct, so false first.

llvm/test/CodeGen/X86/add-cmov.ll

51–52

I guess you need to look past a truncation when looking for the cmov,
and then widen everything to the cmov type.

[RKSimon]

Nice!

FTR - I'd started trying to get cmov-of-constants support into X86DAGToDAGISel::matchAddress (but maybe it should be in a LEA pass?) as I think we could then handle "add(x,add(y,cmov(20, 50))) -> add(add(x, 20), cmov(y,add(y,30)))" to help pull more of the math inside LEA?

[spatel]

llvm/lib/Target/X86/X86ISelLowering.cpp

49850

Sure - will update.

49872

I copied that code from combineCMov(), so we should be consistent in this file at least.

llvm/test/CodeGen/X86/add-cmov.ll

51–52

Yes - or we try to carve out another case where we prefer i32 instead of trying to narrow the add. Changing the preferred type would probably be the better choice, but there will likely be a lot of test diffs...

[spatel]

Patch updated - changed "hoist" to "push".

[lebedev.ri]

I think byte-sized add should be dealt with separately.
LG unless there are other comments.

llvm/test/CodeGen/X86/add-cmov.ll

51–52

I think we should in general widen everything less than i32 to i32,
but here i'd guess it would be better to just look past trunc.

[RKSimon]

LGTM - cheers

llvm/lib/Target/X86/X86ISelLowering.cpp

static SDValue matchPMADDWD_2(SelectionDAG &DAG, SDValue N0, SDValue N1,
 
   auto PMADDBuilder = [](SelectionDAG &DAG, const SDLoc &DL,
                          ArrayRef<SDValue> Ops) {
     EVT OpVT = Ops[0].getValueType();
     assert(OpVT.getScalarType() == MVT::i16 &&
            "Unexpected scalar element type");
     assert(OpVT == Ops[1].getValueType() && "Operands' types mismatch");
     EVT ResVT = EVT::getVectorVT(*DAG.getContext(), MVT::i32,
                                  OpVT.getVectorNumElements() / 2);
     return DAG.getNode(X86ISD::VPMADDWD, DL, ResVT, Ops[0], Ops[1]);
   };
 
   // If the output is narrower than an input, extract the low part of the input
   // vector.
   EVT OutVT16 = EVT::getVectorVT(*DAG.getContext(), MVT::i16,
                                VT.getVectorNumElements() * 2);
   if (OutVT16.bitsLT(In0.getValueType())) {
     In0 = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, OutVT16, In0,
                       DAG.getIntPtrConstant(0, DL));
   }
   if (OutVT16.bitsLT(In1.getValueType())) {
     In1 = DAG.getNode(ISD::EXTRACT_SUBVECTOR, DL, OutVT16, In1,
                       DAG.getIntPtrConstant(0, DL));
   }
   return SplitOpsAndApply(DAG, Subtarget, DL, VT, { In0, In1 },
                           PMADDBuilder);
 }
 
+/// CMOV of constants requires materializing constant operands in registers.
+/// Try to fold those constants into an 'add' instruction to reduce instruction
+/// count. We do this with CMOV rather the generic 'select' because there are
+/// earlier folds that may be used to turn select-of-constants into logic hacks.
+static SDValue pushAddIntoCmovOfConsts(SDNode *N, SelectionDAG &DAG) {
+  // This checks for a zero operand because add-of-0 gets simplified away.
+  // TODO: Allow generating an extra add?
+  auto isSuitableCmov = [](SDValue V) {
+    if (V.getOpcode() != X86ISD::CMOV || !V.hasOneUse())
+      return false;
+    return isa<ConstantSDNode>(V.getOperand(0)) &&
+           isa<ConstantSDNode>(V.getOperand(1)) &&
+           (isNullConstant(V.getOperand(0)) || isNullConstant(V.getOperand(1)));
+  };
+
+  // Match an appropriate CMOV as the first operand of the add.
+  SDValue Cmov = N->getOperand(0);
+  SDValue OtherOp = N->getOperand(1);
+  if (!isSuitableCmov(Cmov))
+    std::swap(Cmov, OtherOp);
+  if (!isSuitableCmov(Cmov))
+    return SDValue();
+
+  // add (cmov C, 0), OtherOp --> cmov (add OtherOp, C), OtherOp
+  // add (cmov 0, C), OtherOp --> cmov OtherOp, (add OtherOp, C)
+  SDLoc DL(N);
+  SDValue FalseOp = Cmov.getOperand(0);
+  SDValue TrueOp = Cmov.getOperand(1);
+  EVT VT = N->getValueType(0);
+  FalseOp = DAG.getNode(ISD::ADD, DL, VT, OtherOp, FalseOp);
+  TrueOp = DAG.getNode(ISD::ADD, DL, VT, OtherOp, TrueOp);
+  return DAG.getNode(X86ISD::CMOV, DL, VT, FalseOp, TrueOp, Cmov.getOperand(2),
+                     Cmov.getOperand(3));
+}
+
 static SDValue combineAdd(SDNode *N, SelectionDAG &DAG,
                           TargetLowering::DAGCombinerInfo &DCI,
                           const X86Subtarget &Subtarget) {
   EVT VT = N->getValueType(0);
   SDValue Op0 = N->getOperand(0);
   SDValue Op1 = N->getOperand(1);
 
+  if (SDValue Select = pushAddIntoCmovOfConsts(N, DAG))
+    return Select;
+
   if (SDValue MAdd = matchPMADDWD(DAG, Op0, Op1, SDLoc(N), VT, Subtarget))
     return MAdd;
   if (SDValue MAdd = matchPMADDWD_2(DAG, Op0, Op1, SDLoc(N), VT, Subtarget))
     return MAdd;
 
   // Try to synthesize horizontal adds from adds of shuffles.
   if (SDValue V = combineToHorizontalAddSub(N, DAG, Subtarget))
     return V;

llvm/test/CodeGen/X86/add-cmov.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -verify-machineinstrs -mtriple=x86_64-- | FileCheck %s
 
 define i64 @select_consts_i64(i64 %offset, i32 %x) {
 ; CHECK-LABEL: select_consts_i64:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    xorl %ecx, %ecx
+; CHECK-NEXT:    leaq 42(%rdi), %rax
 ; CHECK-NEXT:    testl %esi, %esi
-; CHECK-NEXT:    movl $42, %eax
-; CHECK-NEXT:    cmovneq %rcx, %rax
-; CHECK-NEXT:    addq %rdi, %rax
+; CHECK-NEXT:    cmovneq %rdi, %rax
 ; CHECK-NEXT:    retq
   %b = icmp eq i32 %x, 0
   %s = select i1 %b, i64 42, i64 0
   %r = add i64 %s, %offset
   ret i64 %r
 }
 
 define i32 @select_consts_i32(i32 %offset, i64 %x) {
 ; CHECK-LABEL: select_consts_i32:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    xorl %ecx, %ecx
+; CHECK-NEXT:    # kill: def $edi killed $edi def $rdi
+; CHECK-NEXT:    leal 43(%rdi), %eax
 ; CHECK-NEXT:    cmpq $42, %rsi
-; CHECK-NEXT:    movl $43, %eax
-; CHECK-NEXT:    cmovgel %ecx, %eax
-; CHECK-NEXT:    addl %edi, %eax
+; CHECK-NEXT:    cmovgel %edi, %eax
 ; CHECK-NEXT:    retq
   %b = icmp sgt i64 %x, 41
   %s = select i1 %b, i32 0, i32 43
   %r = add i32 %offset, %s
   ret i32 %r
 }
 
 define i16 @select_consts_i16(i16 %offset, i1 %b) {
 ; CHECK-LABEL: select_consts_i16:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    xorl %ecx, %ecx
+; CHECK-NEXT:    # kill: def $edi killed $edi def $rdi
+; CHECK-NEXT:    leal 44(%rdi), %eax
 ; CHECK-NEXT:    testb $1, %sil
-; CHECK-NEXT:    movl $44, %eax
-; CHECK-NEXT:    cmovel %ecx, %eax
-; CHECK-NEXT:    addl %edi, %eax
+; CHECK-NEXT:    cmovel %edi, %eax
 ; CHECK-NEXT:    # kill: def $ax killed $ax killed $eax
 ; CHECK-NEXT:    retq
   %s = select i1 %b, i16 44, i16 0
   %r = add i16 %s, %offset
   ret i16 %r
 }
 
 define i8 @select_consts_i8(i8 %offset, i1 %b) {
 ; CHECK-LABEL: select_consts_i8:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    xorl %ecx, %ecx
 ; CHECK-NEXT:    testb $1, %sil
 ; CHECK-NEXT:    movl $45, %eax
 ; CHECK-NEXT:    cmovnel %ecx, %eax
 ; CHECK-NEXT:    addb %dil, %al
 ; CHECK-NEXT:    # kill: def $al killed $al killed $eax
 ; CHECK-NEXT:    retq
   %s = select i1 %b, i8 0, i8 45
   %r = add i8 %offset, %s
   ret i8 %r
 }
 
 define i32 @select_consts_use_i32(i32 %offset, i64 %x, i32* %p) {