[InstCombine] reduce test-for-overflow of shifted value

[rotateright]

Forking this off from #57330:

define i1 @src(i8 %x) {
  %add = shl i8 %x, 1
  %cmp = icmp ult i8 %add, %x
  ret i1 %cmp
}

define i1 @tgt(i8 %x) {
  %r = icmp slt i8 %x, 0
  ret i1 %r
}

https://alive2.llvm.org/ce/z/sTrumT

[llvmbot]

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

[tianz]

I would like to take a look at this as my first issue!

[rotateright]

Sounds good. Your solution should be flexible enough to handle patterns where the icmp operands are swapped and also when the icmp predicate is inverted.

If you have questions, post here or post a patch to Phabricator and ask there. I am "spatel" on Phabricator if you want to add me as a reviewer.

[RKSimon]

See also #51889

[tianz]

I spent some time getting a better understanding of this issue. Basically, we want to reduce
ult (x << 1), x into slt x, 0, because unsigned x << 1 only overflows when signed x < 0

Similarly,
ugt x, (x << 1) is equivalent to slt x, 0
ugt (x << 1), x is equivalent to sgt x, 0
ult x, (x << 1) is equivalent to sgt x, 0

Are there any other patterns I'm missing?

My next step is to find the best place in InstCombineCompares.cpp to implement this change.

Any feedbacks, comments and suggestions are much appreciated!

[rotateright]

Test all of the unsigned predicates and see if there is a pattern.

For example uge (x << 1), x is equivalent to sgt x, -1:
https://alive2.llvm.org/ce/z/MB7wv3

We can also reduce equality predicates:
https://alive2.llvm.org/ce/z/7mRDRz

[rotateright]

Also, you can look at the related bug (#51889) and the patch that was proposed to solve it to get ideas about where in InstCombineCompares to add code.

[tianz]

Proposed fix: https://reviews.llvm.org/D132888
@rotateright @RKSimon I've added both of you as the potential reviewers. Thank you both for the help!