[DAGCombine] Consider SETULT as carry flag

[chfast]

Summary

The SETcc/SETULT sets carry flag in the same way as usub, so it can
be considered as a carry flag and pulled into addcarry, subcarry nodes.

[RKSimon]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2772

Do we need any getBooleanContents checks here?

[chfast]

What do you think about this idea in general? Can we assume or check if SETULT actually affects CL flag on given target?

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2772

I'm not sure. But I can pass it though the getBooleanContents check below.

[craig.topper]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

2773

Use return SDValue() to match the rest of the code.

[chfast]

Address review comments.

[chfast]

Use switch. Rebased.

[lebedev.ri]

Is ISD::SETULT documented as affecting carry flag?

[chfast]

In D118037#3272185, @lebedev.ri wrote:

Is ISD::SETULT documented as affecting carry flag?

I have not found anything about it in code comments.

I'm now investigating what is SETCCCARRY node kind about...

[RKSimon]

BTW - how come we still have the ISD::ADDE/SUBE nodes? I thought we were intending to get rid of them as the glue nodes made them difficult to work with.

[chfast]

In D118037#3272270, @RKSimon wrote:

BTW - how come we still have the ISD::ADDE/SUBE nodes? I thought we were intending to get rid of them as the glue nodes made them difficult to work with.

I'm happy to remove these later if you give me hints where to start.

[chfast]

What I try to do in the end is to fix https://github.com/llvm/llvm-project/issues/53432. Maybe this particular change is not good direction, but on the other hand it also helps with the test add_U320_without_i128_add already in repo.

[RKSimon]

Maybe perform this inside X86ISelLowering?

[chfast]

In D118037#3294363, @RKSimon wrote:

Maybe perform this inside X86ISelLowering?

I'm totally inexperienced with X86ISelLowering but I'm guessing I'd need to duplicate some/all DAGCombine match patters which take carry flag into account. These tend to be quite complex.

[craig.topper]

llvm/test/CodeGen/X86/addcarry.ll

1335

This case looks like an easy X86 backend peephole.

X86ISD::ADC with an unused flag result, 0 for RHS, LHS is a single use ADD. If so fold the ADD operands into a new X86ISD::ADC.

I'm not sure about the @add_U320_without_i128_add case without staring at it for a lot longer.

[RKSimon]

llvm/test/CodeGen/X86/addcarry.ll

1335

combineSBB already does something similar, we're just missing this from combineADC

[chfast]

This was intermediate change to solve https://github.com/llvm/llvm-project/issues/53432. There I want to merge sub + cmp into single sbb. Any suggestions how to solve it differently?

[chfast]

llvm/test/CodeGen/X86/addcarry.ll

1335

See https://reviews.llvm.org/D120435.

[RKSimon]

@chfast reverse-ping - any luck with working out how best to deal with add_U320_without_i128_add?

[chfast]

In D118037#3377941, @RKSimon wrote:

@chfast reverse-ping - any luck with working out how best to deal with add_U320_without_i128_add?

No. I tried to untangle the graph here for long time but without any meaningful results. But I believe the test can be reduced. This is not my priority any more but I may contribute a reduced tests some day.

[chfast]

On the high level note, using builtin_subc() or builtin_sub_with_overflow() is good enough workaround.

I also think it would be very nice to have generic addc/subc intrinsic on LLVM IR level. Then many of these carry matching could be done in LLVM IR.

[chfast]

Should I try to push this by adding a TTI flag like "CmpULTsetsCarryFlag"?

[RKSimon]

Please can you rebase to see where we currently are? Also D127115 affects these tests - so maybe see whether this SETULT change is still needed after that patch or whether something else can further improve the codegen?

[chfast]

Rebased.

[deadalnix]

In D118037#3731784, @RKSimon wrote:

Please can you rebase to see where we currently are? Also D127115 affects these tests - so maybe see whether this SETULT change is still needed after that patch or whether something else can further improve the codegen?

For what it is worth, when the dag is processed in fully topological order, and you add in D57317 , then you get optimal codegen for these tests.

[chfast]

In D118037#3740763, @deadalnix wrote:

In D118037#3731784, @RKSimon wrote:

Please can you rebase to see where we currently are? Also D127115 affects these tests - so maybe see whether this SETULT change is still needed after that patch or whether something else can further improve the codegen?

For what it is worth, when the dag is processed in fully topological order, and you add in D57317 , then you get optimal codegen for these tests.

Yes, this is great. Thanks for reaching out. I will try to be little involved in both then.

I'm not actively working on this one so I will probably focus on regression tests for combining cmp into sbb (as the result of recent changes to InstCombine).

[lebedev.ri]

This review may be stuck/dead, consider abandoning if no longer relevant.
Removing myself as reviewer in attempt to clean dashboard.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (V.getOpcode() == ISD::AND && isOneConstant(V.getOperand(1))) {
       Masked = true;
       V = V.getOperand(0);
       continue;
     }
 
     break;
   }
 
+  switch (V.getOpcode()) {
+  case ISD::ADDCARRY:
+  case ISD::SUBCARRY:
+  case ISD::UADDO:
+  case ISD::USUBO: {
     // If this is not a carry, return.
     if (V.getResNo() != 1)
       return SDValue();
 
-  if (V.getOpcode() != ISD::ADDCARRY && V.getOpcode() != ISD::SUBCARRY &&
-      V.getOpcode() != ISD::UADDO && V.getOpcode() != ISD::USUBO)
-    return SDValue();
-
-  EVT VT = V->getValueType(0);
+    EVT VT = V.getNode()->getValueType(0);
     if (!TLI.isOperationLegalOrCustom(V.getOpcode(), VT))
       return SDValue();
+    break;
+  }
+  case ISD::SETCC: {
+    // Consider SETULT which affects carry flag only.
+    ISD::CondCode CC = cast<CondCodeSDNode>(V.getOperand(2))->get();
+    if (CC != ISD::SETULT)
+      return SDValue();
+    break;
+  }
+  default:
+    return SDValue();
+  }
 
   // If the result is masked, then no matter what kind of bool it is we can
   // return. If it isn't, then we need to make sure the bool type is either 0 or
   // 1 and not other values.
   if (Masked ||
       TLI.getBooleanContents(V.getValueType()) ==
           TargetLoweringBase::ZeroOrOneBooleanContent)
     return V;

llvm/test/CodeGen/AArch64/arm64-csel.ll

entry:
   %. = select i1 %cmp, i64 0, i64 9223372036854775807
   ret i64 %.
 }
 
 ; Regression test for FalseVal - TrueVal overflow
 define i64 @foo18_overflow3(i1 %cmp) nounwind readnone optsize ssp {
 ; CHECK-LABEL: foo18_overflow3:
 ; CHECK:       // %bb.0: // %entry
-; CHECK-NEXT:    mov x8, #-9223372036854775808 
-; CHECK-NEXT:    tst w0, #0x1 
-; CHECK-NEXT:    csel x0, x8, xzr, ne 
+; CHECK-NEXT:    mov x8, #-9223372036854775808
+; CHECK-NEXT:    tst w0, #0x1
+; CHECK-NEXT:    csel x0, x8, xzr, ne
 ; CHECK-NEXT:    ret
 entry:
   %. = select i1 %cmp, i64 -9223372036854775808, i64 0
   ret i64 %.
 }
 
 ; Regression test for TrueVal - FalseVal overflow
 define i64 @foo18_overflow4(i1 %cmp) nounwind readnone optsize ssp {
 ; CHECK-LABEL: foo18_overflow4:
 ; CHECK:       // %bb.0: // %entry
-; CHECK-NEXT:    mov x8, #-9223372036854775808 
-; CHECK-NEXT:    tst w0, #0x1 
-; CHECK-NEXT:    csel x0, xzr, x8, ne 
+; CHECK-NEXT:    mov x8, #-9223372036854775808
+; CHECK-NEXT:    tst w0, #0x1
+; CHECK-NEXT:    csel x0, xzr, x8, ne
 ; CHECK-NEXT:    ret
 entry:
   %. = select i1 %cmp, i64 0, i64 -9223372036854775808
   ret i64 %.
 }
 
 define i64 @foo19(i64 %a, i64 %b, i64 %c) {
 ; CHECK-LABEL: foo19:
 ; CHECK:       // %bb.0: // %entry
 ; CHECK-NEXT:    cmp x0, x1
-; CHECK-NEXT:    cinc x0, x2, lo
+; CHECK-NEXT:    cset w8, lo
+; CHECK-NEXT:    cmp w8, #1
+; CHECK-NEXT:    cinc x0, x2, hs
 ; CHECK-NEXT:    ret
 entry:
   %cmp = icmp ult i64 %a, %b
   %inc = zext i1 %cmp to i64
   %inc.c = add i64 %inc, %c
   ret i64 %inc.c
 }
 

llvm/test/CodeGen/X86/addcarry.ll

; CHECK-NEXT:    retq
   ret { i64, i64, i1 } %r
 }
 
 %struct.U320 = type { [5 x i64] }
 
 define i32 @add_U320_without_i128_add(ptr nocapture dereferenceable(40) %0, i64 %1, i64 %2, i64 %3, i64 %4, i64 %5) nounwind {
 ; CHECK-LABEL: add_U320_without_i128_add:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    pushq %r14
-; CHECK-NEXT:    pushq %rbx
-; CHECK-NEXT:    movq 16(%rdi), %rax
-; CHECK-NEXT:    leaq (%rax,%rcx), %r10
+; CHECK-NEXT:    movq 16(%rdi), %r10
+; CHECK-NEXT:    xorl %r11d, %r11d
+; CHECK-NEXT:    movq %r10, %rax
+; CHECK-NEXT:    addq %rcx, %rax
+; CHECK-NEXT:    setb %r11b
 ; CHECK-NEXT:    addq %rsi, (%rdi)
 ; CHECK-NEXT:    adcq %rdx, 8(%rdi)
-; CHECK-NEXT:    movq %rax, %rdx
-; CHECK-NEXT:    adcq %rcx, %rdx
-; CHECK-NEXT:    movq 24(%rdi), %r11
-; CHECK-NEXT:    leaq (%r8,%r11), %r14
-; CHECK-NEXT:    xorl %ebx, %ebx
-; CHECK-NEXT:    cmpq %r10, %rdx
-; CHECK-NEXT:    setb %bl
-; CHECK-NEXT:    addq %rcx, %rax
-; CHECK-NEXT:    adcq %r14, %rbx
-; CHECK-NEXT:    movq 32(%rdi), %r10
-; CHECK-NEXT:    leaq (%r9,%r10), %rcx
-; CHECK-NEXT:    xorl %esi, %esi
-; CHECK-NEXT:    cmpq %r14, %rbx
-; CHECK-NEXT:    setb %sil
-; CHECK-NEXT:    addq %r11, %r8
-; CHECK-NEXT:    adcq %rcx, %rsi
+; CHECK-NEXT:    adcq %rcx, %r10
+; CHECK-NEXT:    xorl %ecx, %ecx
+; CHECK-NEXT:    addq 24(%rdi), %r8
+; CHECK-NEXT:    setb %cl
+; CHECK-NEXT:    cmpq %rax, %r10
+; CHECK-NEXT:    adcq %r8, %r11
+; CHECK-NEXT:    movq 32(%rdi), %rdx
+; CHECK-NEXT:    leaq (%r9,%rdx), %rsi
+; CHECK-NEXT:    cmpq %r8, %r11
+; CHECK-NEXT:    adcq %rsi, %rcx
 ; CHECK-NEXT:    xorl %eax, %eax
-; CHECK-NEXT:    cmpq %rcx, %rsi
+; CHECK-NEXT:    cmpq %rsi, %rcx
 ; CHECK-NEXT:    setb %al
-; CHECK-NEXT:    addq %r10, %r9
-; CHECK-NEXT:    movq %rdx, 16(%rdi)
-; CHECK-NEXT:    movq %rbx, 24(%rdi)
-; CHECK-NEXT:    movq %rsi, 32(%rdi)
+; CHECK-NEXT:    addq %rdx, %r9
+; CHECK-NEXT:    movq %r10, 16(%rdi)
+; CHECK-NEXT:    movq %r11, 24(%rdi)
+; CHECK-NEXT:    movq %rcx, 32(%rdi)
 ; CHECK-NEXT:    adcl $0, %eax
-; CHECK-NEXT:    popq %rbx
-; CHECK-NEXT:    popq %r14
 ; CHECK-NEXT:    retq
   %7 = load i64, ptr %0, align 8
   %8 = getelementptr inbounds %struct.U320, ptr %0, i64 0, i32 0, i64 1
   %9 = load i64, ptr %8, align 8
   %10 = getelementptr inbounds %struct.U320, ptr %0, i64 0, i32 0, i64 2
   %11 = load i64, ptr %10, align 8
   %12 = getelementptr inbounds %struct.U320, ptr %0, i64 0, i32 0, i64 3
   %13 = load i64, ptr %12, align 8
; CHECK-NEXT:    retq
   ret void
 }
 
 define i32 @addcarry_ult(i32 %a, i32 %b, i32 %x, i32 %y) nounwind {
 ; CHECK-LABEL: addcarry_ult:
 ; CHECK:       # %bb.0:
 ; CHECK-NEXT:    movl %edi, %eax
 ; CHECK-NEXT:    cmpl %ecx, %edx
 ; CHECK-NEXT:    adcl %esi, %eax
 ; CHECK-NEXT:    retq
   %s = add i32 %a, %b
   %k = icmp ult i32 %x, %y
   %z = zext i1 %k to i32
   %r = add i32 %s, %z
   ret i32 %r
 }