# [InstCombine] fold icmp of the sum of ext bool based on limited range ClosedPublic

Authored by bcl5980 on Feb 6 2023, 12:54 AM.

# Details

Summary

For the pattern (zext i1 X) + (sext i1 Y), the constant range is [-1, 1].
We can simplify the pattern by logical operations. Like:

```(zext i1 X) + (sext i1 Y) == -1 -->  ~X & Y
(zext i1 X) + (sext i1 Y) == 0  --> ~(X ^ Y)
(zext i1 X) + (sext i1 Y) == 1 --> X & ~Y```

And other predicates can the combination of these results:

```(zext i1 X) + (sext i1 Y)) != -1 --> X | ~Y
(zext i1 X) + (sext i1 Y)) s> -1 --> X | ~Y
(zext i1 X) + (sext i1 Y)) u< -1 --> X | ~Y
(zext i1 X) + (sext i1 Y)) s> 0 --> X & ~Y
(zext i1 X) + (sext i1 Y)) s< 0 --> ~X & Y
(zext i1 X) + (sext i1 Y)) != 1 --> ~X | Y
(zext i1 X) + (sext i1 Y)) s< 1 --> ~X | Y
(zext i1 X) + (sext i1 Y)) u> 1 --> ~X & Y```

# Diff Detail

### Event Timeline

bcl5980 created this revision.Feb 6 2023, 12:54 AM
Herald added a project: Restricted Project. Feb 6 2023, 12:54 AM
bcl5980 requested review of this revision.Feb 6 2023, 12:54 AM
Herald added a project: Restricted Project. Feb 6 2023, 12:54 AM
bcl5980 updated this revision to Diff 495025.Feb 6 2023, 1:19 AM

rebase with precommit tests.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
5868

This description does not make sense to me. We need to specify the predicate along with the constant value to know the correct transform?

5881

Include "ULT" here?

llvm/test/Transforms/InstCombine/icmp-range.ll
662

Where do we transform this pattern? Is it possible that the existing code can be extended to handle more predicates?

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
5878

Think it would be clearer to have the comments for each transform at their respective case statement.

5881

Include "ULT" here?

All corresponding unsigned predicts no?

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
5881

We could, but it would probably just be dead code.

UGT: "x u> -1" is really "x u> 0xffff..." (is always simplified to false).
SLT: handled by SCCP, but nothing in instcombine gets it, so we should add that to the list too.

All of ULE/UGE/SLE/SGE will be canonicalized to their LT/GT counterparts, so we don't need to handle those.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
5881

Thanks for the mention for the unsigned compare.
ult -1 is the same to ne -1 here.
ugt 1 is the same to eq -1 here.
ugt 0 is the same to ne 0 here.
ult 1 is the same to eq 0 here.

llvm/test/Transforms/InstCombine/icmp-range.ll
662

It comes from computeKnownBits, sgt -1 can ignore the sign bit to do this. It only works for sgt -1 I think.

bcl5980 updated this revision to Diff 495356.Feb 6 2023, 8:02 PM
bcl5980 edited the summary of this revision. (Show Details)

bcl5980 updated this revision to Diff 495361.Feb 6 2023, 8:05 PM
bcl5980 updated this revision to Diff 495365.Feb 6 2023, 8:11 PM

rebase tests.

bcl5980 updated this revision to Diff 496322.Feb 9 2023, 8:31 PM

Make the code easier to read.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
5874–5875

Since we are going through these combinations, we should handle these cases that are missed by InstCombine:
https://alive2.llvm.org/ce/z/3m9D9D

If there are other combinations that are not already handled, then let's reduce those too?

bcl5980 updated this revision to Diff 496832.Feb 12 2023, 8:21 PM

remove the condition CmpC->abs().ule(1)

remove the condition CmpC->abs().ule(1)

Without that condition, we can't use getSextValue() safely on the compare constant. This test needs to be added (please pre-commit the new tests too) because it will now crash:

```define i1 @zext_sext_add_icmp_sgt_minus2(i1 %a, i1 %b) {
%zext.a = zext i1 %a to i128
%sext.b = sext i1 %b to i128
%r = icmp sgt i128 %add, 9223372036854775808
ret i1 %r
}```
bcl5980 updated this revision to Diff 497170.Feb 13 2023, 6:22 PM

use APint to compare to make it work for integer types with larger than 64bits.

remove the condition CmpC->abs().ule(1)

Without that condition, we can't use getSextValue() safely on the compare constant. This test needs to be added (please pre-commit the new tests too) because it will now crash:

```define i1 @zext_sext_add_icmp_sgt_minus2(i1 %a, i1 %b) {
%zext.a = zext i1 %a to i128
%sext.b = sext i1 %b to i128