This is an archive of the discontinued LLVM Phabricator instance.

[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

All alive proofs:
https://alive2.llvm.org/ce/z/KmgDpF
https://alive2.llvm.org/ce/z/fLwWa9
https://alive2.llvm.org/ce/z/ZKQn2P

Fix: https://github.com/llvm/llvm-project/issues/59666

Diff Detail

Event Timeline

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

rebase with precommit tests.

spatel added inline comments.Feb 6 2023, 12:53 PM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
5836

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

5849

Include "ULT" here?

llvm/test/Transforms/InstCombine/icmp-range.ll
631–632

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

Can you add alive2 links?

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

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

5849

Include "ULT" here?

All corresponding unsigned predicts no?

spatel added inline comments.Feb 6 2023, 1:45 PM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
5849

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.

bcl5980 added inline comments.Feb 6 2023, 7:08 PM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
5849

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
631–632

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)

Address comments.

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.

spatel added inline comments.Feb 10 2023, 11:48 AM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
5842–5843

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)
add cases return constant

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
  %add = add i128 %zext.a, %sext.b
  %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
  %add = add i128 %zext.a, %sext.b
  %r = icmp sgt i128 %add, 9223372036854775808
  ret i1 %r
}

Thanks for the catch!

spatel accepted this revision.Feb 14 2023, 8:26 AM

LGTM - please pre-commit the extra baseline tests that were added in the last few rounds of review.

This revision is now accepted and ready to land.Feb 14 2023, 8:26 AM