[x86] improve CMOV codegen by pushing add into operands, part 3

[spatel]

Summary

In this episode, we are trying to avoid an x86 micro-arch quirk where complex (3 operand) LEA potentially costs significantly more than simple LEA. So we simultaneously push and pull the math around the CMOV to balance the operations.

I looked at the debug spew during instruction selection and decided against trying a later DAGToDAG transform -- it seems very difficult to match if the trailing memops are already selected and managing the creation of extra instructions at that level is always tricky.

[lebedev.ri]

I think this makes sense.

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

277

This does seem like an improvement https://godbolt.org/z/obf4sGcKW

[pengfei]

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

284–285

lea won't affect eflags, so it may still be better than add in some complex scenarios I guess?

[spatel]

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

284–285

That's true in general, but I don't think it can be a factor in this transform because we know that the cmov is a user of eflags, so it is already being set by some other op.

[RKSimon]

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

284–285

We already have passes that convert add -> lea to break intefering eflags dependencies - I think this is fine.

[RKSimon]

llvm/lib/Target/X86/X86ISelLowering.cpp

49975

We usually canonicalize add constants to RHS - does this actually cause problems?

[spatel]

llvm/lib/Target/X86/X86ISelLowering.cpp

49975

I haven't been able to come up with a test to show this pattern, but I was worried that we could get in here in some intermediate non-canonical state.

If that happens, we'd likely hit an infinite loop with the previous transform, so I figured it was better to play it safe and check for constant.

[RKSimon]

LGTM - cheers

llvm/lib/Target/X86/X86ISelLowering.cpp

static SDValue pushAddIntoCmovOfConsts(SDNode *N, SelectionDAG &DAG) {
   // 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 C1, C2), OtherOp --> cmov (add OtherOp, C1), (add OtherOp, C2)
   EVT VT = N->getValueType(0);
   SDLoc DL(N);
   SDValue FalseOp = Cmov.getOperand(0);
   SDValue TrueOp = Cmov.getOperand(1);
+
+  // We will push the add through the select, but we can potentially do better
+  // if we know there is another add in the sequence and this is pointer math.
+  // In that case, we can absorb an add into the trailing memory op and avoid
+  // a 3-operand LEA which is likely slower than a 2-operand LEA.
+  // TODO: If target has "slow3OpsLEA", do this even without the trailing memop?
+  if (OtherOp.getOpcode() == ISD::ADD && OtherOp.hasOneUse() &&
+      !isa<ConstantSDNode>(OtherOp.getOperand(0)) &&
+      all_of(N->uses(), [&](SDNode *Use) {
+        auto *MemNode = dyn_cast<MemSDNode>(Use);
+        return MemNode && MemNode->getBasePtr().getNode() == N;
+      })) {
+    // add (cmov C1, C2), add (X, Y) --> add (cmov (add X, C1), (add X, C2)), Y
+    // TODO: We are arbitrarily choosing op0 as the 1st piece of the sum, but
+    //       it is possible that choosing op1 might be better.
+    SDValue X = OtherOp.getOperand(0), Y = OtherOp.getOperand(1);
+    FalseOp = DAG.getNode(ISD::ADD, DL, VT, X, FalseOp);
+    TrueOp = DAG.getNode(ISD::ADD, DL, VT, X, TrueOp);
+    Cmov = DAG.getNode(X86ISD::CMOV, DL, VT, FalseOp, TrueOp,
+                       Cmov.getOperand(2), Cmov.getOperand(3));
+    return DAG.getNode(ISD::ADD, DL, VT, Cmov, Y);
+  }
+
+  // add (cmov C1, C2), OtherOp --> cmov (add OtherOp, C1), (add OtherOp, C2)
   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,

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

; CHECK-NEXT:    retq
   %idx40 = mul i64 %idx, 40
   %gep2 = getelementptr inbounds i16, i16* %ptr, i64 33
   %gep1 = getelementptr inbounds i16, i16* %ptr, i64 30
   %sel = select i1 %b, i16* %gep1, i16* %gep2
   %gep3 = getelementptr inbounds i16, i16* %sel, i64 %idx40
   ret i16* %gep3
 }
 
 define void @bullet_load_store(i32 %x, i64 %y, %class.btAxis* %p) {
 ; CHECK-LABEL: bullet_load_store:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    leaq (%rsi,%rsi,4), %rax
 ; CHECK-NEXT:    shlq $4, %rax
+; CHECK-NEXT:    leaq 66(%rdx), %rcx
+; CHECK-NEXT:    addq $60, %rdx
 ; CHECK-NEXT:    testb $1, %dil
-; CHECK-NEXT:    leaq 60(%rdx,%rax), %rcx
-; CHECK-NEXT:    leaq 66(%rdx,%rax), %rax
-; CHECK-NEXT:    cmoveq %rcx, %rax
-; CHECK-NEXT:    decw (%rax)
+; CHECK-NEXT:    cmovneq %rcx, %rdx
+; CHECK-NEXT:    decw (%rdx,%rax)
 ; CHECK-NEXT:    retq
   %and = and i32 %x, 1
   %b = icmp eq i32 %and, 0
   %gep2 = getelementptr inbounds %class.btAxis, %class.btAxis* %p, i64 %y, i32 2, i64 0
   %gep1 = getelementptr inbounds %class.btAxis, %class.btAxis* %p, i64 %y, i32 1, i64 0
   %sel = select i1 %b, i16* %gep1, i16* %gep2
   %ld = load i16, i16* %sel, align 4
   %dec = add i16 %ld, -1
   store i16 %dec, i16* %sel, align 4
   ret void
 }
 
 define void @complex_lea_alt1(i1 %b, i16* readnone %ptr, i64 %idx) {
 ; CHECK-LABEL: complex_lea_alt1:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    leaq 60(%rdx,%rsi), %rax
-; CHECK-NEXT:    leaq 66(%rdx,%rsi), %rcx
+; CHECK-NEXT:    leaq 60(%rdx), %rax
+; CHECK-NEXT:    addq $66, %rdx
 ; CHECK-NEXT:    testb $1, %dil
-; CHECK-NEXT:    cmovneq %rax, %rcx
-; CHECK-NEXT:    decw (%rcx)
+; CHECK-NEXT:    cmovneq %rax, %rdx
+; CHECK-NEXT:    decw (%rdx,%rsi)
 ; CHECK-NEXT:    retq
   %i = ptrtoint i16* %ptr to i64
   %sum = add i64 %idx, %i
   %base = inttoptr i64 %sum to i16*
   %gep2 = getelementptr inbounds i16, i16* %base, i64 33
   %gep1 = getelementptr inbounds i16, i16* %base, i64 30
   %sel = select i1 %b, i16* %gep1, i16* %gep2
   %ld = load i16, i16* %sel, align 4
   %dec = add i16 %ld, -1
   store i16 %dec, i16* %sel, align 4
   ret void
 }
 
 define void @complex_lea_alt2(i1 %b, i16* readnone %ptr, i64 %idx) {
 ; CHECK-LABEL: complex_lea_alt2:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    leaq 60(%rsi,%rdx), %rax
-; CHECK-NEXT:    leaq 66(%rsi,%rdx), %rcx
+; CHECK-NEXT:    leaq 60(%rsi), %rax
+; CHECK-NEXT:    addq $66, %rsi
 ; CHECK-NEXT:    testb $1, %dil
-; CHECK-NEXT:    cmovneq %rax, %rcx
-; CHECK-NEXT:    decw (%rcx)
+; CHECK-NEXT:    cmovneq %rax, %rsi
+; CHECK-NEXT:    decw (%rsi,%rdx)
 ; CHECK-NEXT:    retq
   %i = ptrtoint i16* %ptr to i64
   %sum = add i64 %i, %idx
   %base = inttoptr i64 %sum to i16*
   %gep2 = getelementptr inbounds i16, i16* %base, i64 33
   %gep1 = getelementptr inbounds i16, i16* %base, i64 30
   %sel = select i1 %b, i16* %gep1, i16* %gep2
   %ld = load i16, i16* %sel, align 4
; CHECK-NEXT:    retq
   %dec = add i16 %ld, -1
   store i16 %dec, i16* %sel, align 4
   ret void
 }
 
 define void @complex_lea_alt7(i1 %b, i16* readnone %ptr, i64 %idx) {
 ; CHECK-LABEL: complex_lea_alt7:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    leaq 60(%rdx,%rsi), %rax
-; CHECK-NEXT:    leaq 66(%rdx,%rsi), %rcx
+; CHECK-NEXT:    leaq 60(%rdx), %rax
+; CHECK-NEXT:    addq $66, %rdx
 ; CHECK-NEXT:    testb $1, %dil
-; CHECK-NEXT:    cmovneq %rax, %rcx
-; CHECK-NEXT:    decw (%rcx)
+; CHECK-NEXT:    cmovneq %rax, %rdx
+; CHECK-NEXT:    decw (%rdx,%rsi)
 ; CHECK-NEXT:    retq
   %i = ptrtoint i16* %ptr to i64
   %o = add i64 %idx, %i
   %o66 = add i64 %o, 66
   %o60 = add i64 %o, 60
   %p66 = inttoptr i64 %o66 to i16*
   %p60 = inttoptr i64 %o60 to i16*
   %sel = select i1 %b, i16* %p60, i16* %p66
   %ld = load i16, i16* %sel, align 4
   %dec = add i16 %ld, -1
   store i16 %dec, i16* %sel, align 4
   ret void
 }
 
 define void @complex_lea_alt8(i1 %b, i16* readnone %ptr, i64 %idx) {
 ; CHECK-LABEL: complex_lea_alt8:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    leaq 60(%rsi,%rdx), %rax
-; CHECK-NEXT:    leaq 66(%rsi,%rdx), %rcx
+; CHECK-NEXT:    leaq 60(%rsi), %rax
+; CHECK-NEXT:    addq $66, %rsi
 ; CHECK-NEXT:    testb $1, %dil
-; CHECK-NEXT:    cmovneq %rax, %rcx
-; CHECK-NEXT:    decw (%rcx)
+; CHECK-NEXT:    cmovneq %rax, %rsi
+; CHECK-NEXT:    decw (%rsi,%rdx)
 ; CHECK-NEXT:    retq
   %i = ptrtoint i16* %ptr to i64
   %o = add i64 %i, %idx
   %o66 = add i64 %o, 66
   %o60 = add i64 %o, 60
   %p66 = inttoptr i64 %o66 to i16*
   %p60 = inttoptr i64 %o60 to i16*
   %sel = select i1 %b, i16* %p60, i16* %p66
   %ld = load i16, i16* %sel, align 4
   %dec = add i16 %ld, -1
   store i16 %dec, i16* %sel, align 4
   ret void
 }