Missed optimization (unnecessary sext): y >= x should imply y - x >= 0

[Explorer09]

Test code

#include <stdint.h>
extern void subroutine(uint64_t x);

void func1(int32_t a, int32_t b) {
   if (a > b)
      return;
   subroutine(b - a);
}

void func2(int32_t a, int32_t b) {
   if (a > b)
      return;
   subroutine((uint64_t)(int32_t)(b - a));
}

void func3(int32_t a, int32_t b) {
   if (a > b)
      return;
   subroutine((uint64_t)(uint32_t)(b - a));
}

uint64_t func4(int32_t a, int32_t b) {
   if (a > b)
      return 0;
   return (b - a);
}

uint64_t func5(int32_t a, int32_t b) {
   if (a > b)
      return 0;
   return (uint64_t)(int32_t)(b - a);
}

uint64_t func6(int32_t a, int32_t b) {
   if (a > b)
      return 0;
   return (uint64_t)(uint32_t)(b - a);
}

Actual result (x86-64 clang 20.1.0 with -Os option): func1, func2, func4 and func5 made unnecessary sign extensions (movsxd instruction). (https://godbolt.org/z/s3zvnET5e)

Expected result: func1, func2 and func3 compile to same code. func4, func5 and func6 compile to same code.

After the (a > b) conditional, Clang should be able to know that (a <= b), which in turn implies (0 <= b - a). In other words, (b - a) would be always nonnegative.

[dtcxzyw]

https://alive2.llvm.org/ce/z/4RNUig

[dtcxzyw]

We may extend isKnownNonNegative to call isImpliedByDomCondition first:

llvm-project/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

Lines 1120 to 1122 in dfaa662

	Value *X, *Y;
	if (match(Op, m_NSWSub(m_Value(X), m_Value(Y))))
	return isImpliedByDomCondition(ICmpInst::ICMP_SLE, X, Y, SQ.CxtI, SQ.DL);

[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: Kang-Che Sung (宋岡哲) (Explorer09)

Test code

#include <stdint.h>
extern void subroutine(uint64_t x);

void func1(int32_t a, int32_t b) {
   if (a > b)
      return;
   subroutine(b - a);
}

void func2(int32_t a, int32_t b) {
   if (a > b)
      return;
   subroutine((uint64_t)(int32_t)(b - a));
}

void func3(int32_t a, int32_t b) {
   if (a > b)
      return;
   subroutine((uint64_t)(uint32_t)(b - a));
}

uint64_t func4(int32_t a, int32_t b) {
   if (a > b)
      return 0;
   return (b - a);
}

uint64_t func5(int32_t a, int32_t b) {
   if (a > b)
      return 0;
   return (uint64_t)(int32_t)(b - a);
}

uint64_t func6(int32_t a, int32_t b) {
   if (a > b)
      return 0;
   return (uint64_t)(uint32_t)(b - a);
}

Actual result (x86-64 clang 20.1.0 with -Os option): func1, func2, func4 and func5 made unnecessary sign extensions (movsxd instruction). (https://godbolt.org/z/s3zvnET5e)

Expected result: func1, func2 and func3 compile to same code. func4, func5 and func6 compile to same code.

After the (a > b) conditional, Clang should be able to know that (a <= b), which in turn implies (0 <= b - a). In other words, (b - a) would be always nonnegative.

[hulxv]

@dtcxzyw I would like to work on it.

[dtcxzyw]

@hulxv Please read https://llvm.org/docs/InstCombineContributorGuide.html before submitting a patch. Good luck :)