[x86][armv8] Failure to use flag in unsigned underflow compare idiom

[WalterKruger]

It is a common idiom to check for unsigned underflow by doing a greater than compare between the difference and minuend:

#include <stdint.h>

uint64_t subIfNoUnderflow_clang(uint64_t a, uint64_t b) {
    uint64_t diff = a - b;
    return (diff > a)? a : diff;
}

Instead of using the carry flag, which is set by the subtraction, clang emits a compare instruction:

https://godbolt.org/z/ex5554M6P

subIfNoUnderflow_clang:
        mov     rax, rdi
        sub     rax, rsi
        cmp     rax, rdi
        cmovae  rax, rdi
        ret

Ideally it should produce:

subIfNoUnderflow_ideal:
        mov     rax, rdi
        sub     rax, rsi
        cmovb   rax, rdi
        ret

Related issues

#53432
#62696
#73847

[llvmbot]

@llvm/issue-subscribers-backend-x86

Author: Walter (WalterKruger)

It is a common idiom to check for unsigned underflow by doing a greater than compare between the difference and minuend:

#include <stdint.h>

uint64_t subIfNoUnderflow_clang(uint64_t a, uint64_t b) {
    uint64_t diff = a - b;
    return (diff > a)? a : diff;
}

Instead of using the carry flag, which is set by the subtraction, clang emits a compare instruction:

https://godbolt.org/z/ex5554M6P

subIfNoUnderflow_clang:
        mov     rax, rdi
        sub     rax, rsi
        cmp     rax, rdi
        cmovae  rax, rdi
        ret

Ideally it should produce:

subIfNoUnderflow_ideal:
        mov     rax, rdi
        sub     rax, rsi
        cmovb   rax, rdi
        ret

Related issues

#53432
#62696
#73847

[RKSimon]

define i64 @subIfNoUnderflow_clang(i64 %a, i64 %b) {
entry:
  %sub = sub i64 %a, %b
  %cond = tail call i64 @llvm.umin.i64(i64 %sub, i64 %a)
  ret i64 %cond
}

define i64 @subIfNoUnderflow_ideal(i64 %a, i64 %b) {
entry:
  %0 = tail call { i64, i1 } @llvm.usub.with.overflow.i64(i64 %a, i64 %b)
  %1 = extractvalue { i64, i1 } %0, 1
  %2 = extractvalue { i64, i1 } %0, 0
  %cond = select i1 %1, i64 %a, i64 %2
  ret i64 %cond
}

[RKSimon]

define i4 @src(i4 %a, i4 %b) {
  %sub = sub i4 %a, %b
  %cond = umin i4 %sub, %a
  ret i4 %cond
}
define i4 @tgt(i4 %a, i4 %b) {
  %fb = freeze i4 %b
  %usubo = usub_overflow i4 %a, %fb
  %overflow = extractvalue {i4, i1} %usubo, 1
  %sub = extractvalue {i4, i1} %usubo, 0
  %cond = select i1 %overflow, i4 %a, i4 %sub
  ret i4 %cond
}
Transformation seems to be correct!

[RKSimon]

We probably do this as a generic dag combine with suitable legality checks

[llvmbot]

Hi!

This issue may be a good introductory issue for people new to working on LLVM. If you would like to work on this issue, your first steps are:

1. Check that no other contributor is working on this issue. If someone is assigned to the issue or claimed to be working on it, ping the person. After one week without a response, the assignee may be changed.
2. Leave a comment indicating that you are working on the issue, or just create a pull request after following the steps below. Mention this issue in the description of the pull request.
3. Fix the issue locally.
4. Run the test suite locally. Remember that the subdirectories under test/ create fine-grained testing targets, so you can e.g. use make check-clang-ast to only run Clang's AST tests.
5. Create a Git commit.
6. Run git clang-format HEAD~1 to format your changes.
7. Open a pull request to the upstream repository on GitHub. Detailed instructions can be found in GitHub's documentation. Mention this issue in the description of the pull request.

If you have any further questions about this issue, don't hesitate to ask via a comment in the thread below.

[llvmbot]

@llvm/issue-subscribers-good-first-issue

Author: Walter (WalterKruger)

It is a common idiom to check for unsigned underflow by doing a greater than compare between the difference and minuend:

#include <stdint.h>

uint64_t subIfNoUnderflow_clang(uint64_t a, uint64_t b) {
    uint64_t diff = a - b;
    return (diff > a)? a : diff;
}

Instead of using the carry flag, which is set by the subtraction, clang emits a compare instruction:

https://godbolt.org/z/ex5554M6P

subIfNoUnderflow_clang:
        mov     rax, rdi
        sub     rax, rsi
        cmp     rax, rdi
        cmovae  rax, rdi
        ret

Ideally it should produce:

subIfNoUnderflow_ideal:
        mov     rax, rdi
        sub     rax, rsi
        cmovb   rax, rdi
        ret

Related issues

#53432
#62696
#73847

[ckoparkar]

I'd like to give it a go.