[X86] Add more addcarry tests

[chfast]

Summary

More addcarry tests for incoming https://reviews.llvm.org/D70079.

[davezarzycki]

A few comments / questions:

1. I'm not a regular contributor to LLVM, so please wait for somebody else (like @craig.topper, @RKSimon, or @spatel) to sign off on this.
2. Once one has "add carry", one immediately wants "sub carry/borrow". Please consider adding tests to subcarry.ll.
3. What is add256_1 trying to do and how is it different than add256_2?
4. Finally, can you rename your examples to be more descriptive? In particular, if you look at early parts of the file, you'll see that there are a bunch of definitions with simple names like "add256" where 256 (etc) refers to native LLVM types, not aggregates. Perhaps names like the tests I added "sub_U320_without_i128_or" which strongly implies at the implementation strategy.

[chfast]

Add comments more descriptive test names

[chfast]

In D70237#1745687, @davezarzycki wrote:

A few comments / questions:

1. I'm not a regular contributor to LLVM, so please wait for somebody else (like @craig.topper, @RKSimon, or @spatel) to sign off on this.
2. Once one has "add carry", one immediately wants "sub carry/borrow". Please consider adding tests to subcarry.ll.

Yes, I can prepare similar tests for subtraction. Let me know if they should be include in this changeset.

3. What is add256_1 trying to do and how is it different than add256_2?

They are now described in comments (also the order has been swapped). Let me know if the descriptions are good enough.

4. Finally, can you rename your examples to be more descriptive? In particular, if you look at early parts of the file, you'll see that there are a bunch of definitions with simple names like "add256" where 256 (etc) refers to native LLVM types, not aggregates. Perhaps names like the tests I added "sub_U320_without_i128_or" which strongly implies at the implementation strategy.

Done.

[davezarzycki]

Yes, please update subcarry.ll too.

And thanks, I was trying to see why the AND instruction was used by "add_U256_without_i128_or_recursive". It's not wrong but it is more complicated than it needs to be. If you are somebody else wants to add more pattern matching as a refinement, let's handle that in a subsequent patch.

My patch is designed to recognize the following pattern (which clang happens to generate but I didn't know that going in):

temp[n] = x[n] + y[n];
result[n] = temp[n] + ((temp[n-1] < x[n-1]) | (result[n-1] < temp[n-1]));

In English: "either the previous addition overflowed or the previous carry propagation overflowed (but they cannot both overflow)."

Because the two carries cannot both overflow at the same time, you can also use XOR or ADD to merge the carry flags, but ADD is more difficult to pattern match because the compiler can commute the additions.

[chfast]

In D70237#1747220, @davezarzycki wrote:

Yes, please update subcarry.ll too.

I will.

And thanks, I was trying to see why the AND instruction was used by "add_U256_without_i128_or_recursive". It's not wrong but it is more complicated than it needs to be. If you are somebody else wants to add more pattern matching as a refinement, let's handle that in a subsequent patch.

Yes, that's reasonable. This implementation comes from my small library for 256-bit arithmetic. The 255-bit addition is defined in terms of uint128 type (custom, not __int128). I just inlined all the functions manually. Maybe there is a way to change my implementation in a way it will benefit from this PR.
Anyway, the only question for is if I should keep this test.

[davezarzycki]

When you update the tests, please remove the URLs. Also, what do you see the tests adding above and beyond what already exist in the file? For example, the nested structures design only changes the operands to getelementptr, but it doesn't change how the add/sub carry optimization works. And the by-reference versus by-value tests are also independent of the add/sub carry optimization.

[chfast]

Update addcarry tests and add a subcarry test

[chfast]

I ended up with optimizing my bigint library. The end result is - add_U256_without_i128_or_recursive which works better in current LLVM release and is also nicely reduced by D70079.
The analogous implementations of subtraction is added as sub_U256_without_i128_or_recursive test. This one should be interested to you @davezarzycki, your changes make it better, but it looks it is not perfect yet.

[davezarzycki]

In D70237#1749635, @chfast wrote:

I ended up with optimizing my bigint library. The end result is - add_U256_without_i128_or_recursive which works better in current LLVM release and is also nicely reduced by D70079.
The analogous implementations of subtraction is added as sub_U256_without_i128_or_recursive test. This one should be interested to you @davezarzycki, your changes make it better, but it looks it is not perfect yet.

Thanks for the update. Where is the original source for sub_U256_without_i128_or_recursive? The IR is strange. It seems to use two different strategies for merging carry flags.

And as a reminder, please remove the URLs from the test files.

[chfast]

Remove URLs

[chfast]

Thanks for the update. Where is the original source for sub_U256_without_i128_or_recursive? The IR is strange. It seems to use two different strategies for merging carry flags.

I don't really have a standalone implementation for it at the moment. It is code for this procedure for uint256 type: https://github.com/chfast/intx/blob/master/include/intx/intx.hpp#L528-L532. It is the same as the one for add, just + replaced with - and < with > for checking the carry flag. But probably LLVM has disturbed it a bit because add is proffered over sub in some places.

[davezarzycki]

In D70237#1749841, @chfast wrote:

Thanks for the update. Where is the original source for sub_U256_without_i128_or_recursive? The IR is strange. It seems to use two different strategies for merging carry flags.

I don't really have a standalone implementation for it at the moment. It is code for this procedure for uint256 type: https://github.com/chfast/intx/blob/master/include/intx/intx.hpp#L528-L532. It is the same as the one for add, just + replaced with - and < with > for checking the carry flag. But probably LLVM has disturbed it a bit because add is proffered over sub in some places.

Okay. I'm okay with these tests now. Please wait for somebody more experienced / authoritative too sign off though. Thanks!

Also, the tree-like recursion that generated sub_U256_without_i128_or_recursive will be extremely difficult to optimize. Please consider linear recursion instead.

[spatel]

LGTM. We can always adjust/add tests in the follow-ups to the code for overflow/carry.

llvm/test/CodeGen/X86/addcarry.ll

967

curry -> carry

[chfast]

Fix typo

llvm/test/CodeGen/X86/addcarry.ll

; CHECK-NEXT:    retq
   %28 = getelementptr inbounds %struct.U192, %struct.U192* %2, i64 0, i32 0, i64 2
   %29 = load i64, i64* %28, align 8
   %30 = add i64 %27, %29
   %31 = add i64 %30, %24
   %32 = getelementptr inbounds %struct.U192, %struct.U192* %0, i64 0, i32 0, i64 2
   store i64 %31, i64* %32, align 8
   ret void
 }
+
+
+%uint128 = type { i64, i64 }
+
+define zeroext i1 @uaddo_U128_without_i128_or(i64 %0, i64 %1, i64 %2, i64 %3, %uint128* nocapture %4) nounwind {
+; CHECK-LABEL: uaddo_U128_without_i128_or:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    addq %rcx, %rsi
+; CHECK-NEXT:    setb %cl
+; CHECK-NEXT:    addq %rdx, %rdi
+; CHECK-NEXT:    adcq $0, %rsi
+; CHECK-NEXT:    setb %al
+; CHECK-NEXT:    orb %cl, %al
+; CHECK-NEXT:    movq %rsi, (%r8)
+; CHECK-NEXT:    movq %rdi, 8(%r8)
+; CHECK-NEXT:    retq
+  %6 = add i64 %2, %0
+  %7 = icmp ult i64 %6, %0
+  %8 = add i64 %3, %1
+  %9 = icmp ult i64 %8, %1
+  %10 = zext i1 %7 to i64
+  %11 = add i64 %8, %10
+  %12 = icmp ult i64 %11, %8
+  %13 = or i1 %9, %12
+  %14 = getelementptr inbounds %uint128, %uint128* %4, i64 0, i32 0
+  store i64 %11, i64* %14, align 8
+  %15 = getelementptr inbounds %uint128, %uint128* %4, i64 0, i32 1
+  store i64 %6, i64* %15, align 8
+  ret i1 %13
+}
+
+
+%uint192 = type { i64, i64, i64 }
+
+define void @add_U192_without_i128_or(%uint192* sret %0, i64 %1, i64 %2, i64 %3, i64 %4, i64 %5, i64 %6) nounwind {
+; CHECK-LABEL: add_U192_without_i128_or:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movq %rdi, %rax
+; CHECK-NEXT:    addq %r9, %rdx
+; CHECK-NEXT:    setb %dil
+; CHECK-NEXT:    addq %r8, %rsi
+; CHECK-NEXT:    adcq $0, %rdx
+; CHECK-NEXT:    setb %r8b
+; CHECK-NEXT:    orb %dil, %r8b
+; CHECK-NEXT:    addq {{[0-9]+}}(%rsp), %rcx
+; CHECK-NEXT:    movzbl %r8b, %edi
+; CHECK-NEXT:    addq %rcx, %rdi
+; CHECK-NEXT:    movq %rdi, (%rax)
+; CHECK-NEXT:    movq %rdx, 8(%rax)
+; CHECK-NEXT:    movq %rsi, 16(%rax)
+; CHECK-NEXT:    retq
+  %8 = add i64 %4, %1
+  %9 = icmp ult i64 %8, %1
+  %10 = add i64 %5, %2
+  %11 = icmp ult i64 %10, %2
+  %12 = zext i1 %9 to i64
+  %13 = add i64 %10, %12
+  %14 = icmp ult i64 %13, %10
+  %15 = or i1 %11, %14
+  %16 = add i64 %6, %3
+  %17 = zext i1 %15 to i64
+  %18 = add i64 %16, %17
+  %19 = getelementptr inbounds %uint192, %uint192* %0, i64 0, i32 0
+  store i64 %18, i64* %19, align 8
+  %20 = getelementptr inbounds %uint192, %uint192* %0, i64 0, i32 1
+  store i64 %13, i64* %20, align 8
+  %21 = getelementptr inbounds %uint192, %uint192* %0, i64 0, i32 2
+  store i64 %8, i64* %21, align 8
+  ret void
+}
+
+
+%uint256 = type { %uint128, %uint128 }
+
+; Classic unrolled 256-bit addition implementation using i64 as the word type.
+; It starts by adding least significant words and propagates carry to additions of the higher words.
+define void @add_U256_without_i128_or_by_i64_words(%uint256* sret %0, %uint256* %1, %uint256* %2) nounwind {
+; CHECK-LABEL: add_U256_without_i128_or_by_i64_words:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movq %rdi, %rax
+; CHECK-NEXT:    movq (%rdx), %r9
+; CHECK-NEXT:    movq 8(%rdx), %r10
+; CHECK-NEXT:    addq 8(%rsi), %r10
+; CHECK-NEXT:    setb %r8b
+; CHECK-NEXT:    addq (%rsi), %r9
+; CHECK-NEXT:    adcq $0, %r10
+; CHECK-NEXT:    setb %cl
+; CHECK-NEXT:    orb %r8b, %cl
+; CHECK-NEXT:    movq 16(%rdx), %rdi
+; CHECK-NEXT:    addq 16(%rsi), %rdi
+; CHECK-NEXT:    setb %r8b
+; CHECK-NEXT:    movzbl %cl, %r11d
+; CHECK-NEXT:    addq %rdi, %r11
+; CHECK-NEXT:    setb %cl
+; CHECK-NEXT:    orb %r8b, %cl
+; CHECK-NEXT:    movq 24(%rdx), %rdx
+; CHECK-NEXT:    addq 24(%rsi), %rdx
+; CHECK-NEXT:    movzbl %cl, %ecx
+; CHECK-NEXT:    addq %rdx, %rcx
+; CHECK-NEXT:    movq %rcx, (%rax)
+; CHECK-NEXT:    movq %r11, 8(%rax)
+; CHECK-NEXT:    movq %r10, 16(%rax)
+; CHECK-NEXT:    movq %r9, 24(%rax)
+; CHECK-NEXT:    retq
+  %4 = getelementptr inbounds %uint256, %uint256* %1, i64 0, i32 0, i32 0
+  %5 = load i64, i64* %4, align 8
+  %6 = getelementptr inbounds %uint256, %uint256* %2, i64 0, i32 0, i32 0
+  %7 = load i64, i64* %6, align 8
+  %8 = add i64 %7, %5
+  %9 = icmp ult i64 %8, %5
+  %10 = getelementptr inbounds %uint256, %uint256* %1, i64 0, i32 0, i32 1
+  %11 = load i64, i64* %10, align 8
+  %12 = getelementptr inbounds %uint256, %uint256* %2, i64 0, i32 0, i32 1
+  %13 = load i64, i64* %12, align 8
+  %14 = add i64 %13, %11
+  %15 = icmp ult i64 %14, %11
+  %16 = zext i1 %9 to i64
+  %17 = add i64 %14, %16
+  %18 = icmp ult i64 %17, %16
+  %19 = or i1 %15, %18
+  %20 = getelementptr inbounds %uint256, %uint256* %1, i64 0, i32 1, i32 0
+  %21 = load i64, i64* %20, align 8
+  %22 = getelementptr inbounds %uint256, %uint256* %2, i64 0, i32 1, i32 0
+  %23 = load i64, i64* %22, align 8
+  %24 = add i64 %23, %21
+  %25 = icmp ult i64 %24, %21
+  %26 = zext i1 %19 to i64
+  %27 = add i64 %24, %26
+  %28 = icmp ult i64 %27, %26
+  %29 = or i1 %25, %28
+  %30 = getelementptr inbounds %uint256, %uint256* %1, i64 0, i32 1, i32 1
+  %31 = load i64, i64* %30, align 8
+  %32 = getelementptr inbounds %uint256, %uint256* %2, i64 0, i32 1, i32 1
+  %33 = load i64, i64* %32, align 8
+  %34 = add i64 %33, %31
+  %35 = zext i1 %29 to i64
+  %36 = add i64 %34, %35
+  %37 = getelementptr inbounds %uint256, %uint256* %0, i64 0, i32 0, i32 0
+  store i64 %36, i64* %37, align 8
+  %38 = getelementptr inbounds %uint256, %uint256* %0, i64 0, i32 0, i32 1
+  store i64 %27, i64* %38, align 8
+  %39 = getelementptr inbounds %uint256, %uint256* %0, i64 0, i32 1, i32 0
+  store i64 %17, i64* %39, align 8
+  %40 = getelementptr inbounds %uint256, %uint256* %0, i64 0, i32 1, i32 1
+  store i64 %8, i64* %40, align 8
+  ret void
+}
+
+; The 256-bit addition implementation using two inlined uaddo procedures for U128 type { i64, i64 }.
+; This is similar to how LLVM legalize types in CodeGen.
+define void @add_U256_without_i128_or_recursive(%uint256* sret %0, %uint256* %1, %uint256* %2) nounwind {
+; CHECK-LABEL: add_U256_without_i128_or_recursive:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movq %rdi, %rax
+; CHECK-NEXT:    movq (%rdx), %r9
+; CHECK-NEXT:    movq 8(%rdx), %rdi
+; CHECK-NEXT:    addq 8(%rsi), %rdi
+; CHECK-NEXT:    setb %r8b
+; CHECK-NEXT:    addq (%rsi), %r9
+; CHECK-NEXT:    adcq $0, %rdi
+; CHECK-NEXT:    setb %cl
+; CHECK-NEXT:    orb %r8b, %cl
+; CHECK-NEXT:    movq 16(%rdx), %r8
+; CHECK-NEXT:    movq 24(%rdx), %r10
+; CHECK-NEXT:    xorl %edx, %edx
+; CHECK-NEXT:    addq 16(%rsi), %r8
+; CHECK-NEXT:    setb %dl
+; CHECK-NEXT:    addq 24(%rsi), %r10
+; CHECK-NEXT:    movzbl %cl, %ecx
+; CHECK-NEXT:    addq %r8, %rcx
+; CHECK-NEXT:    adcq %r10, %rdx
+; CHECK-NEXT:    movq %r9, (%rax)
+; CHECK-NEXT:    movq %rdi, 8(%rax)
+; CHECK-NEXT:    movq %rcx, 16(%rax)
+; CHECK-NEXT:    movq %rdx, 24(%rax)
+; CHECK-NEXT:    retq
+  %4 = getelementptr inbounds %uint256, %uint256* %1, i64 0, i32 0, i32 0
+  %5 = load i64, i64* %4, align 8
+  %6 = getelementptr inbounds %uint256, %uint256* %1, i64 0, i32 0, i32 1
+  %7 = load i64, i64* %6, align 8
+  %8 = getelementptr inbounds %uint256, %uint256* %2, i64 0, i32 0, i32 0
+  %9 = load i64, i64* %8, align 8
+  %10 = getelementptr inbounds %uint256, %uint256* %2, i64 0, i32 0, i32 1
+  %11 = load i64, i64* %10, align 8
+  %12 = add i64 %9, %5
+  %13 = icmp ult i64 %12, %5
+  %14 = add i64 %11, %7
+  %15 = icmp ult i64 %14, %7
+  %16 = zext i1 %13 to i64
+  %17 = add i64 %14, %16
+  %18 = icmp ult i64 %17, %14
+  %19 = or i1 %15, %18
+  %20 = getelementptr inbounds %uint256, %uint256* %1, i64 0, i32 1, i32 0
+  %21 = load i64, i64* %20, align 8
+  %22 = getelementptr inbounds %uint256, %uint256* %1, i64 0, i32 1, i32 1
+  %23 = load i64, i64* %22, align 8
+  %24 = getelementptr inbounds %uint256, %uint256* %2, i64 0, i32 1, i32 0
+  %25 = load i64, i64* %24, align 8
+  %26 = getelementptr inbounds %uint256, %uint256* %2, i64 0, i32 1, i32 1
+  %27 = load i64, i64* %26, align 8
+  %28 = add i64 %25, %21
+  %29 = icmp ult i64 %28, %21
+  %30 = add i64 %27, %23
+  %31 = zext i1 %29 to i64
+  %32 = add i64 %30, %31
+  %33 = zext i1 %19 to i64
+  %34 = add i64 %28, %33
+  %35 = icmp ult i64 %34, %28
+  %36 = zext i1 %35 to i64
+  %37 = add i64 %32, %36
+  %38 = getelementptr inbounds %uint256, %uint256* %0, i64 0, i32 0, i32 0
+  store i64 %12, i64* %38, align 8
+  %39 = getelementptr inbounds %uint256, %uint256* %0, i64 0, i32 0, i32 1
+  store i64 %17, i64* %39, align 8
+  %40 = getelementptr inbounds %uint256, %uint256* %0, i64 0, i32 1, i32 0
+  store i64 %34, i64* %40, align 8
+  %41 = getelementptr inbounds %uint256, %uint256* %0, i64 0, i32 1, i32 1
+  store i64 %37, i64* %41, align 8
+  ret void
+}

llvm/test/CodeGen/X86/subcarry.ll

; CHECK-NEXT:    retq
   %28 = getelementptr inbounds %struct.U192, %struct.U192* %2, i64 0, i32 0, i64 2
   %29 = load i64, i64* %28, align 8
   %30 = sub i64 %27, %29
   %31 = sub i64 %30, %24
   %32 = getelementptr inbounds %struct.U192, %struct.U192* %0, i64 0, i32 0, i64 2
   store i64 %31, i64* %32, align 8
   ret void
 }
+
+%uint128 = type { i64, i64 }
+%uint256 = type { %uint128, %uint128 }
+
+; The 256-bit subtraction implementation using two inlined usubo procedures for U128 type { i64, i64 }.
+; This is similar to how LLVM legalize types in CodeGen.
+define void @sub_U256_without_i128_or_recursive(%uint256* sret %0, %uint256* %1, %uint256* %2) nounwind {
+; CHECK-LABEL: sub_U256_without_i128_or_recursive:
+; CHECK:       # %bb.0:
+; CHECK-NEXT:    movq %rdi, %rax
+; CHECK-NEXT:    movq (%rsi), %r8
+; CHECK-NEXT:    movq 8(%rsi), %r10
+; CHECK-NEXT:    xorl %ecx, %ecx
+; CHECK-NEXT:    subq (%rdx), %r8
+; CHECK-NEXT:    setb %cl
+; CHECK-NEXT:    subq 8(%rdx), %r10
+; CHECK-NEXT:    setb %r9b
+; CHECK-NEXT:    subq %rcx, %r10
+; CHECK-NEXT:    setb %cl
+; CHECK-NEXT:    orb %r9b, %cl
+; CHECK-NEXT:    movq 16(%rsi), %rdi
+; CHECK-NEXT:    movq 24(%rsi), %rsi
+; CHECK-NEXT:    xorl %r9d, %r9d
+; CHECK-NEXT:    subq 16(%rdx), %rdi
+; CHECK-NEXT:    setb %r9b
+; CHECK-NEXT:    subq 24(%rdx), %rsi
+; CHECK-NEXT:    movzbl %cl, %ecx
+; CHECK-NEXT:    subq %rcx, %rdi
+; CHECK-NEXT:    sbbq %r9, %rsi
+; CHECK-NEXT:    movq %r8, (%rax)
+; CHECK-NEXT:    movq %r10, 8(%rax)
+; CHECK-NEXT:    movq %rdi, 16(%rax)
+; CHECK-NEXT:    movq %rsi, 24(%rax)
+; CHECK-NEXT:    retq
+  %4 = getelementptr inbounds %uint256, %uint256* %1, i64 0, i32 0, i32 0
+  %5 = load i64, i64* %4, align 8
+  %6 = getelementptr inbounds %uint256, %uint256* %1, i64 0, i32 0, i32 1
+  %7 = load i64, i64* %6, align 8
+  %8 = getelementptr inbounds %uint256, %uint256* %2, i64 0, i32 0, i32 0
+  %9 = load i64, i64* %8, align 8
+  %10 = getelementptr inbounds %uint256, %uint256* %2, i64 0, i32 0, i32 1
+  %11 = load i64, i64* %10, align 8
+  %12 = sub i64 %5, %9
+  %13 = icmp ult i64 %5, %9
+  %14 = sub i64 %7, %11
+  %15 = icmp ult i64 %7, %11
+  %16 = zext i1 %13 to i64
+  %17 = sub i64 %14, %16
+  %18 = icmp ult i64 %14, %16
+  %19 = or i1 %15, %18
+  %20 = getelementptr inbounds %uint256, %uint256* %1, i64 0, i32 1, i32 0
+  %21 = load i64, i64* %20, align 8
+  %22 = getelementptr inbounds %uint256, %uint256* %1, i64 0, i32 1, i32 1
+  %23 = load i64, i64* %22, align 8
+  %24 = getelementptr inbounds %uint256, %uint256* %2, i64 0, i32 1, i32 0
+  %25 = load i64, i64* %24, align 8
+  %26 = getelementptr inbounds %uint256, %uint256* %2, i64 0, i32 1, i32 1
+  %27 = load i64, i64* %26, align 8
+  %28 = sub i64 %21, %25
+  %29 = icmp ult i64 %21, %25
+  %30 = sub i64 %23, %27
+  %31 = zext i1 %29 to i64
+  %32 = sub i64 %30, %31
+  %33 = zext i1 %19 to i64
+  %34 = sub i64 %28, %33
+  %35 = icmp ult i64 %28, %33
+  %36 = zext i1 %35 to i64
+  %37 = sub i64 %32, %36
+  %38 = getelementptr inbounds %uint256, %uint256* %0, i64 0, i32 0, i32 0
+  store i64 %12, i64* %38, align 8
+  %39 = getelementptr inbounds %uint256, %uint256* %0, i64 0, i32 0, i32 1
+  store i64 %17, i64* %39, align 8
+  %40 = getelementptr inbounds %uint256, %uint256* %0, i64 0, i32 1, i32 0
+  store i64 %34, i64* %40, align 8
+  %41 = getelementptr inbounds %uint256, %uint256* %0, i64 0, i32 1, i32 1
+  store i64 %37, i64* %41, align 8
+  ret void
+}