[InstSimplify] Fix some missed optimization opportunities in simplifyUnsignedRangeCheck()

[HLJ2009]

Summary

For both operands are unsigned, the following optimizations are valid, and missing:

1. X > Y && X != 0 --> X > Y
2. X > Y || X != 0 --> X != 0
3. X <= Y || X != 0 --> true
4. X <= Y || X == 0 --> X <= Y
5. X > Y && X == 0 --> false

unsigned foo(unsigned x, unsigned y) { return x > y && x != 0; }
should fold to x > y, but I found we haven't done it right now.
besides, unsigned foo(unsigned x, unsigned y) { return x < y && y != 0; }
Has been folded to x < y, so there may be a bug.
I analyzed out that there may be a bit problematic logic at line 1312 in the InstructionSimplify.cpp file.

Depends on D48000.

[lebedev.ri]

lib/Analysis/InstructionSimplify.cpp

1316

Alive thinks this makes sense: https://rise4fun.com/Alive/7d9

test/Transforms/InstCombine/and3.ll

4 ↗

(On Diff #150440)

Can you place it next to the rest of the tests from simplifyUnsignedRangeCheck()?

[HLJ2009]

test/Transforms/InstCombine/and3.ll

4 ↗

(On Diff #150440)

Yes, I want to do it. However I've looked for a test file specific to simplifyUnsignedRangeCheck, but I didn't find it. If possible, I can add the remaining test cases for simplifyUnsignedRangeCheck

[lebedev.ri]

test/Transforms/InstCombine/and3.ll

4 ↗

(On Diff #150440)

Cripple that function:

static Value *simplifyUnsignedRangeCheck(ICmpInst *ZeroICmp,
                                         ICmpInst *UnsignedICmp, bool IsAnd) {
  return nullptr;
...
}

and look through the tests that are now failing.
I think it might be test/Transforms/InstCombine/range-check.ll.

[HLJ2009]

test/Transforms/InstCombine/and3.ll

4 ↗

(On Diff #150440)

Thank you very much for pointing this out. I'll update it soon.

[HLJ2009]

modify the test file.

[lebedev.ri]

lib/Analysis/InstructionSimplify.cpp

1316

So was the old one a harmless typo that rendered that if useless, was that a miscompile (needs test then),
or is the RHS of the diff is a new case (so the old one is a standalone case, too, and needs a test)?

[HLJ2009]

lib/Analysis/InstructionSimplify.cpp

1316

Yes, you are right. For the optimization of this file, I did not find the corresponding test case file.Do I need to add all the remaining test cases now? Or submit a change individually.

[HLJ2009]

lib/Analysis/InstructionSimplify.cpp

1316

If we add a test file named simplifyUnsignedRangeCheck.ll and write the optimizations in this function as test cases, would it be better ?

[lebedev.ri]

lib/Analysis/InstructionSimplify.cpp

1316

Hm?
It looks like test/Transforms/InstCombine/range-check.ll is the testfile with tests for this function, no?
But that wasn't the question.
Is this change fixing a code that was *supposed* to handle your case as-is [but did nothing, or miscompiled something],
or does it change the code that was properly handling some other case?

[HLJ2009]

lib/Analysis/InstructionSimplify.cpp

1316

I looked at the range-check.ll file, and its test point does not seem to be in the function that I modified.My changes will not affect other cases and will not cause compilation errors.

[lebedev.ri]

lib/Analysis/InstructionSimplify.cpp

1316

We are talking past each other.

[HLJ2009]

lib/Analysis/InstructionSimplify.cpp

1316

The "if" in the code should match the below ir
define i32 @test1(i32 %x, i32 %y) {

%1 = icmp ult i32 %x, %y
%2 = icmp ne i32 %y, 0
%3 = and i1 %2, %1
%4 = zext i1 %3 to i32
ret i32 %4

}
The "else if" in the code should match the below ir
define i32 @test1(i32 %x, i32 %y) {

%1 = icmp ugt i32 %x, %y
%2 = icmp ne i32 %x, 0
%3 = and i1 %2, %1
%4 = zext i1 %3 to i32
ret i32 %4

}
but "else if" branche always match less than the corresponding ir

[spatel]

Re: test location
This transform is in InstSimplify, so it should have tests under test/Transforms/InstSimplify. Ie, we shouldn't need to run -instcombine to demonstrate the fold.
Have a look in Transforms/InstSimplify/AndOrXor.ll for existing tests. You may want to do some preliminary cleanup if the tests are scattered between InstCombine and InstSimplify.

[HLJ2009]

In D47922#1126437, @spatel wrote:

Re: test location
This transform is in InstSimplify, so it should have tests under test/Transforms/InstSimplify. Ie, we shouldn't need to run -instcombine to demonstrate the fold.
Have a look in Transforms/InstSimplify/AndOrXor.ll for existing tests. You may want to do some preliminary cleanup if the tests are scattered between InstCombine and InstSimplify.

hi ,

I found that there are several test cases not written. Do I need to add them now? Or do I write it alone and submit it again?

[spatel]

In D47922#1126459, @HLJ2009 wrote:

In D47922#1126437, @spatel wrote:

Re: test location
This transform is in InstSimplify, so it should have tests under test/Transforms/InstSimplify. Ie, we shouldn't need to run -instcombine to demonstrate the fold.
Have a look in Transforms/InstSimplify/AndOrXor.ll for existing tests. You may want to do some preliminary cleanup if the tests are scattered between InstCombine and InstSimplify.

hi ,

I found that there are several test cases not written. Do I need to add them now? Or do I write it alone and submit it again?

Please add missing tests now (before proposing a code change). That way, we will have baseline tests that show the current behavior. When your code change is made, the tests will show the improvement.

When I use Roman's suggestion to stub out the function in question, I see these are the existing positive tests for simplifyUnsignedRangeCheck():

define i1 @and_icmp1(i32 %x, i32 %y) {
; CHECK-LABEL: @and_icmp1(
; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT:    ret i1 [[TMP1]]
;
  %1 = icmp ult i32 %x, %y
  %2 = icmp ne i32 %y, 0
  %3 = and i1 %1, %2
  ret i1 %3
}

define i1 @and_icmp2(i32 %x, i32 %y) {
; CHECK-LABEL: @and_icmp2(
; CHECK-NEXT:    ret i1 false
;
  %1 = icmp ult i32 %x, %y
  %2 = icmp eq i32 %y, 0
  %3 = and i1 %1, %2
  ret i1 %3
}

define i1 @or_icmp1(i32 %x, i32 %y) {
; CHECK-LABEL: @or_icmp1(
; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i32 [[Y:%.*]], 0
; CHECK-NEXT:    ret i1 [[TMP1]]
;
  %1 = icmp ult i32 %x, %y
  %2 = icmp ne i32 %y, 0
  %3 = or i1 %1, %2
  ret i1 %3
}

define i1 @or_icmp2(i32 %x, i32 %y) {
; CHECK-LABEL: @or_icmp2(
; CHECK-NEXT:    ret i1 true
;
  %1 = icmp uge i32 %x, %y
  %2 = icmp ne i32 %y, 0
  %3 = or i1 %1, %2
  ret i1 %3
}

define i1 @or_icmp3(i32 %x, i32 %y) {
; CHECK-LABEL: @or_icmp3(
; CHECK-NEXT:    [[TMP1:%.*]] = icmp uge i32 [[X:%.*]], [[Y:%.*]]
; CHECK-NEXT:    ret i1 [[TMP1]]
;
  %1 = icmp uge i32 %x, %y
  %2 = icmp eq i32 %y, 0
  %3 = or i1 %1, %2
  ret i1 %3
}

define i32 @or_of_zexted_icmps(i32 %i) {
; CHECK-LABEL: @or_of_zexted_icmps(
; CHECK-NEXT:    ret i32 1
;
  %cmp0 = icmp ne i32 %i, 0
  %conv0 = zext i1 %cmp0 to i32
  %cmp1 = icmp uge i32 4, %i
  %conv1 = zext i1 %cmp1 to i32
  %or = or i32 %conv0, %conv1
  ret i32 %or
}

[HLJ2009]

update simplifyUnsignedRangeCheck function's test cases

[HLJ2009]

Move the test file to D47972 for submission

[lebedev.ri]

lib/Analysis/InstructionSimplify.cpp

1312–1316

After staring at this a bit more, the original code looks like just a dead code.
We are first trying to match match(UnsignedICmp, m_ICmp(UnsignedPred, m_Value(X), m_Specific(Y)).
I.e. we take whatever X, and the specific value of Y. This could match.
And then we check that ICmpInst::isUnsigned(UnsignedPred) is true. This could fail.
Then we fall back to else if.
And use match(UnsignedICmp, m_ICmp(UnsignedPred, m_Value(Y), m_Specific(X)).
But this could not possibly match, because the first time we took X from the first operand,
and now we are looking for this very X in the second operand.
And the m_ICmp() is not commutable.
So i think this is simply a typo.

[HLJ2009]

lib/Analysis/InstructionSimplify.cpp

1312–1316

Yes, your analysis is the same as mine.

[lebedev.ri]

There was no need to close D47972 and open a new D48000.
But regardless, please do update this differential,
rebase it ontop of the updated tests, to show how it affects them.

lib/Analysis/InstructionSimplify.cpp

1312–1316

OK

[HLJ2009]

submit code based on trunk branch

[lebedev.ri]

And now,

$ cd llvm
$ git checkout master # the svn trunk
$ arc patch D47922 
$ # unstage the test/test/Transforms/InstSimplify/AndOrXor.ll from last commit, delete that leftover file.
$ git rebase arcpatch-D48000 arcpatch-D47922
$ cd ../llvm-build/ # or whereever
$ ninja
$ ../llvm/utils/utils/update_test_checks.py --opt-binary ./bin/opt ../llvm/test/test/Transforms/InstSimplify/AndOrXor.ll
$ git commit --amend
$ git diff -p -U99999 arcpatch-D48000..arcpatch-D48000 > /tmp/patch.patch # i.e. from D48000 (!!! *not* svn trunk/git master) to this patch
$ # Update this differential with that patch.

[HLJ2009]

In D47922#1130939, @lebedev.ri wrote:

And now,

$ cd llvm
$ git checkout master # the svn trunk
$ arc patch D47922 
$ # unstage the test/test/Transforms/InstSimplify/AndOrXor.ll from last commit, delete that leftover file.
$ git rebase arcpatch-D48000 arcpatch-D47922
$ cd ../llvm-build/ # or whereever
$ ninja
$ ../llvm/utils/utils/update_test_checks.py --opt-binary ./bin/opt ../llvm/test/test/Transforms/InstSimplify/AndOrXor.ll
$ git commit --amend
$ git diff -p -U99999 arcpatch-D48000..arcpatch-D48000 > /tmp/patch.patch # i.e. from D48000 (!!! *not* svn trunk/git master) to this patch
$ # Update this differential with that patch.

hi ,
when I use git rebase arcpatch-D48000 arcpatch-D47922 command, I found this error fatal: Needed a single revision ,invalid upstream arcpatch-D48000
Do I have such permission to do such a thing?

[lebedev.ri]

In D47922#1130979, @HLJ2009 wrote:

In D47922#1130939, @lebedev.ri wrote:

And now,

$ cd llvm
$ git checkout master # the svn trunk
$ arc patch D47922 
$ # unstage the test/test/Transforms/InstSimplify/AndOrXor.ll from last commit, delete that leftover file.
$ git rebase arcpatch-D48000 arcpatch-D47922
$ cd ../llvm-build/ # or whereever
$ ninja
$ ../llvm/utils/utils/update_test_checks.py --opt-binary ./bin/opt ../llvm/test/test/Transforms/InstSimplify/AndOrXor.ll
$ git commit --amend
$ git diff -p -U99999 arcpatch-D48000..arcpatch-D48000 > /tmp/patch.patch # i.e. from D48000 (!!! *not* svn trunk/git master) to this patch
$ # Update this differential with that patch.

hi ,
when I use git rebase arcpatch-D48000 arcpatch-D47922 command, I found this error fatal: Needed a single revision ,invalid upstream arcpatch-D48000
Do I have such permission to do such a thing?

You obviously need to do that in the very same repo clone where you did https://reviews.llvm.org/D48000#1130858
I would really suggest reading something about git, the workflow, basic commands..

[HLJ2009]

In D47922#1130988, @lebedev.ri wrote:

In D47922#1130979, @HLJ2009 wrote:

In D47922#1130939, @lebedev.ri wrote:

And now,

$ cd llvm
$ git checkout master # the svn trunk
$ arc patch D47922 
$ # unstage the test/test/Transforms/InstSimplify/AndOrXor.ll from last commit, delete that leftover file.
$ git rebase arcpatch-D48000 arcpatch-D47922
$ cd ../llvm-build/ # or whereever
$ ninja
$ ../llvm/utils/utils/update_test_checks.py --opt-binary ./bin/opt ../llvm/test/test/Transforms/InstSimplify/AndOrXor.ll
$ git commit --amend
$ git diff -p -U99999 arcpatch-D48000..arcpatch-D48000 > /tmp/patch.patch # i.e. from D48000 (!!! *not* svn trunk/git master) to this patch
$ # Update this differential with that patch.

hi ,
when I use git rebase arcpatch-D48000 arcpatch-D47922 command, I found this error fatal: Needed a single revision ,invalid upstream arcpatch-D48000
Do I have such permission to do such a thing?

You obviously need to do that in the very same repo clone where you did https://reviews.llvm.org/D48000#1130858
I would really suggest reading something about git, the workflow, basic commands..

Thank you for you comments.

[HLJ2009]

use utils/update_test_checks.py to get the difference file we want and set the test baseline. @lebedev.ri would you like to see if I was doing it right? Thanks very much.

[lebedev.ri]

Ok, thanks, that is much better.
Alive agrees that these are valid transforms.
I would personally prefer to also have some *negative* tests.
But this looks good to me. Unless others have any comments.

[HLJ2009]

In D47922#1133217, @lebedev.ri wrote:

Ok, thanks, that is much better.
Alive agrees that these are valid transforms.
I would personally prefer to also have some *negative* tests.
But this looks good to me. Unless others have any comments.

Thank you very much for the code reviewer, and also thanks for introducing the use of the update_test_checks.py tool.

[spatel]

LGTM too. Thanks for finding the bug and working through the steps to make good patches.

[HLJ2009]

In D47922#1133834, @spatel wrote:

LGTM too. Thanks for finding the bug and working through the steps to make good patches.

Thanks for code review. And also thank you for your help.

lib/Analysis/InstructionSimplify.cpp

static Value *simplifyUnsignedRangeCheck(ICmpInst *ZeroICmp,
   Value *X, *Y;
 
   ICmpInst::Predicate EqPred;
   if (!match(ZeroICmp, m_ICmp(EqPred, m_Value(Y), m_Zero())) ||
       !ICmpInst::isEquality(EqPred))
     return nullptr;
 
   ICmpInst::Predicate UnsignedPred;
   if (match(UnsignedICmp, m_ICmp(UnsignedPred, m_Value(X), m_Specific(Y))) &&
       ICmpInst::isUnsigned(UnsignedPred))
     ;
   else if (match(UnsignedICmp,
-                 m_ICmp(UnsignedPred, m_Value(Y), m_Specific(X))) &&
+                 m_ICmp(UnsignedPred, m_Specific(Y), m_Value(X))) &&
            ICmpInst::isUnsigned(UnsignedPred))
     UnsignedPred = ICmpInst::getSwappedPredicate(UnsignedPred);
   else
     return nullptr;
 
   // X < Y && Y != 0  -->  X < Y
   // X < Y || Y != 0  -->  Y != 0
   if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_NE)

test/Transforms/InstSimplify/AndOrXor.ll

;
   %2 = icmp ne i32 %y, 0
   %3 = and i1 %1, %2
   ret i1 %3
 }
 
 define i1 @and_icmp2(i32 %x, i32 %y) {
 ; CHECK-LABEL: @and_icmp2(
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i32 [[X]], 0
-; CHECK-NEXT:    [[TMP3:%.*]] = and i1 [[TMP1]], [[TMP2]]
-; CHECK-NEXT:    ret i1 [[TMP3]]
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %1 = icmp ugt i32 %x, %y
   %2 = icmp ne i32 %x, 0
   %3 = and i1 %1, %2
   ret i1 %3
 }
 
 define i1 @and_icmp3(i32 %x, i32 %y) {
 ; CHECK-LABEL: @and_icmp3(
 ; CHECK-NEXT:    ret i1 false
 ;
   %1 = icmp ult i32 %x, %y
   %2 = icmp eq i32 %y, 0
   %3 = and i1 %1, %2
   ret i1 %3
 }
 
 define i1 @and_icmp4(i32 %x, i32 %y) {
 ; CHECK-LABEL: @and_icmp4(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[X]], 0
-; CHECK-NEXT:    [[TMP3:%.*]] = and i1 [[TMP1]], [[TMP2]]
-; CHECK-NEXT:    ret i1 [[TMP3]]
+; CHECK-NEXT:    ret i1 false
 ;
   %1 = icmp ugt i32 %x, %y
   %2 = icmp eq i32 %x, 0
   %3 = and i1 %1, %2
   ret i1 %3
 }
 
 define i1 @or_icmp1(i32 %x, i32 %y) {
 ; CHECK-LABEL: @or_icmp1(
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i32 [[Y:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %1 = icmp ult i32 %x, %y
   %2 = icmp ne i32 %y, 0
   %3 = or i1 %1, %2
   ret i1 %3
 }
 
 define i1 @or_icmp2(i32 %x, i32 %y) {
 ; CHECK-LABEL: @or_icmp2(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i32 [[X]], 0
-; CHECK-NEXT:    [[TMP3:%.*]] = or i1 [[TMP1]], [[TMP2]]
-; CHECK-NEXT:    ret i1 [[TMP3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i32 [[X:%.*]], 0
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %1 = icmp ugt i32 %x, %y
   %2 = icmp ne i32 %x, 0
   %3 = or i1 %1, %2
   ret i1 %3
 }
 
 define i1 @or_icmp3(i32 %x, i32 %y) {
 ; CHECK-LABEL: @or_icmp3(
 ; CHECK-NEXT:    ret i1 true
 ;
   %1 = icmp uge i32 %x, %y
   %2 = icmp ne i32 %y, 0
   %3 = or i1 %1, %2
   ret i1 %3
 }
 
 define i1 @or_icmp4(i32 %x, i32 %y) {
 ; CHECK-LABEL: @or_icmp4(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp ule i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp ne i32 [[X]], 0
-; CHECK-NEXT:    [[TMP3:%.*]] = or i1 [[TMP1]], [[TMP2]]
-; CHECK-NEXT:    ret i1 [[TMP3]]
+; CHECK-NEXT:    ret i1 true
 ;
   %1 = icmp ule i32 %x, %y
   %2 = icmp ne i32 %x, 0
   %3 = or i1 %1, %2
   ret i1 %3
 }
 
 define i1 @or_icmp5(i32 %x, i32 %y) {
 ; CHECK-LABEL: @or_icmp5(
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp uge i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %1 = icmp uge i32 %x, %y
   %2 = icmp eq i32 %y, 0
   %3 = or i1 %1, %2
   ret i1 %3
 }
 
 define i1 @or_icmp6(i32 %x, i32 %y) {
 ; CHECK-LABEL: @or_icmp6(
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp ule i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[X]], 0
-; CHECK-NEXT:    [[TMP3:%.*]] = or i1 [[TMP1]], [[TMP2]]
-; CHECK-NEXT:    ret i1 [[TMP3]]
+; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %1 = icmp ule i32 %x, %y
   %2 = icmp eq i32 %x, 0
   %3 = or i1 %1, %2
   ret i1 %3
 }
 
 ; PR27869 - Look through casts to eliminate cmps and bitwise logic.