Page MenuHomePhabricator

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

Authored by HLJ2009 on Jun 7 2018, 6:59 PM.

Details

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.

Diff Detail

Repository
rL LLVM

Event Timeline

HLJ2009 created this revision.Jun 7 2018, 6:59 PM
HLJ2009 retitled this revision from x > y && x != 0 -> x > y to x > y && x != 0 should fold to x > y.Jun 7 2018, 7:17 PM
HLJ2009 edited the summary of this revision. (Show Details)
HLJ2009 added reviewers: spatel, craig.topper.
HLJ2009 retitled this revision from x > y && x != 0 should fold to x > y to unsigned foo(unsigned x, unsigned y) { return x > y && x != 0; } should fold to x > y.Jun 7 2018, 7:22 PM
lebedev.ri added inline comments.
lib/Analysis/InstructionSimplify.cpp
1312 ↗(On Diff #150440)

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 marked an inline comment as done.Jun 7 2018, 11:51 PM
HLJ2009 added inline comments.
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 added inline comments.Jun 7 2018, 11:56 PM
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 added inline comments.Jun 7 2018, 11:58 PM
test/Transforms/InstCombine/and3.ll
4 ↗(On Diff #150440)

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

HLJ2009 updated this revision to Diff 150464.Jun 8 2018, 1:26 AM

modify the test file.

lebedev.ri added inline comments.Jun 8 2018, 1:36 AM
lib/Analysis/InstructionSimplify.cpp
1312 ↗(On Diff #150464)

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 added inline comments.Jun 8 2018, 1:44 AM
lib/Analysis/InstructionSimplify.cpp
1312 ↗(On Diff #150464)

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 added inline comments.Jun 8 2018, 1:47 AM
lib/Analysis/InstructionSimplify.cpp
1312 ↗(On Diff #150464)

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 added inline comments.Jun 8 2018, 2:16 AM
lib/Analysis/InstructionSimplify.cpp
1312 ↗(On Diff #150464)

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 added inline comments.Jun 8 2018, 2:27 AM
lib/Analysis/InstructionSimplify.cpp
1312 ↗(On Diff #150464)

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 added inline comments.Jun 8 2018, 2:36 AM
lib/Analysis/InstructionSimplify.cpp
1312 ↗(On Diff #150464)

We are talking past each other.

HLJ2009 added inline comments.Jun 8 2018, 2:54 AM
lib/Analysis/InstructionSimplify.cpp
1312 ↗(On Diff #150464)

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 added a comment.Jun 8 2018, 6:50 AM

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.

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 added a comment.Jun 8 2018, 7:33 AM

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 updated this revision to Diff 150518.Jun 8 2018, 8:03 AM

update simplifyUnsignedRangeCheck function's test cases

HLJ2009 updated this revision to Diff 150607.Jun 8 2018, 10:12 PM

Move the test file to D47972 for submission

lebedev.ri added inline comments.Jun 11 2018, 12:00 AM
lib/Analysis/InstructionSimplify.cpp
1312–1316 ↗(On Diff #150607)

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 added inline comments.Jun 11 2018, 12:05 AM
lib/Analysis/InstructionSimplify.cpp
1312–1316 ↗(On Diff #150607)

Yes, your analysis is the same as mine.

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 ↗(On Diff #150607)

OK

HLJ2009 updated this revision to Diff 150898.Jun 12 2018, 1:22 AM

submit code based on trunk branch

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.

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?

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..

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 updated this revision to Diff 151454.Jun 14 2018, 8:30 PM

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 accepted this revision.Jun 14 2018, 11:34 PM

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.

This revision is now accepted and ready to land.Jun 14 2018, 11:34 PM

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.

lebedev.ri retitled this revision from unsigned foo(unsigned x, unsigned y) { return x > y && x != 0; } should fold to x > y to [InstSimplify] Fix some missed optimization opportunities in simplifyUnsignedRangeCheck().Jun 15 2018, 3:21 AM
lebedev.ri edited the summary of this revision. (Show Details)
spatel accepted this revision.Jun 15 2018, 9:50 AM

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

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.

This revision was automatically updated to reflect the committed changes.