Page MenuHomePhabricator

[InstCombine] reduce icmp(ashr X, C1), C2 to sign-bit test
ClosedPublic

Authored by spatel on Jan 4 2021, 9:13 AM.

Details

Summary

This is a more basic pattern that we should handle before trying to solve:
https://llvm.org/PR48640

There might be a better way to think about this because the pre-condition that I came up with (number of sign bits in the compare constant) misses a potential transform for each of ugt and ult as commented on in the test file.

Tried to model this is in Alive:
https://rise4fun.com/Alive/juX1
...but I couldn't get the ComputeNumSignBits() pre-condition to work as expected, so replaced with leading 0/1 preconditions instead.

Name: ugt
Pre: countLeadingZeros(C2) <= C1 && countLeadingOnes(C2) <= C1
%a = ashr %x, C1
%r = icmp ugt i8 %a, C2
  =>
%r = icmp slt i8 %x, 0

Name: ult
Pre: countLeadingZeros(C2) <= C1 && countLeadingOnes(C2) <= C1
%a = ashr %x, C1
%r = icmp ult i4 %a, C2
  => 
%r = icmp sgt i4 %x, -1

Diff Detail

Event Timeline

spatel created this revision.Jan 4 2021, 9:13 AM
spatel requested review of this revision.Jan 4 2021, 9:13 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 4 2021, 9:13 AM
lebedev.ri added inline comments.Jan 4 2021, 10:02 AM
llvm/test/Transforms/InstCombine/icmp-shr.ll
512

It's a : (colon), not a ; (semicolon), does this test parse?

spatel marked an inline comment as done.Jan 4 2021, 10:14 AM
spatel added inline comments.
llvm/test/Transforms/InstCombine/icmp-shr.ll
512

Oops - I pasted in the test comments after running ninja check, so missed the typo.

spatel updated this revision to Diff 314403.Jan 4 2021, 10:14 AM
spatel marked an inline comment as done.

Patch updated:
Fixed semi-colon typos in test comments.

spatel updated this revision to Diff 315782.Jan 11 2021, 6:14 AM

Ping.
Note: I added a bitwidth > 2 constraint to be safe and avoid degenerate narrow bit patterns, but I'm not sure how to write negative tests for that would actually survive to this point in instcombine (instsimplify appears to reduce those first).

lebedev.ri requested changes to this revision.Jan 11 2021, 6:29 AM

Sorry for the delay.

alive1 does not actually have a countLeadingOnes() precondition
(at least as per https://github.com/nunoplopes/alive/blob/master/constants.py),
so the proof is faulty. ComputeNumSignBits(), OTOH, works for me:

$ cat /tmp/test.ll
Name: lshr ugt
Pre: ComputeNumSignBits(C2) <= C1
%a = lshr i8 %x, C1
%r = icmp ugt i8 %a, C2
  =>
%r = icmp slt i8 %x, 0

Name: lshr ult
Pre: ComputeNumSignBits(C2) <= C1
%a = lshr i8 %x, C1
%r = icmp ult i8 %a, C2
  =>
%r = icmp sgt i8 %x, -1

Name: ashr ugt
Pre: ComputeNumSignBits(C2) <= C1
%a = ashr i8 %x, C1
%r = icmp ugt i8 %a, C2
  =>
%r = icmp slt i8 %x, 0

Name: ashr ult
Pre: ComputeNumSignBits(C2) <= C1
%a = ashr i8 %x, C1
%r = icmp ult i8 %a, C2
  =>
%r = icmp sgt i8 %x, -1

$ /repositories/alive/alive.py /tmp/test.ll 
----------------------------------------
Optimization: lshr ugt
Precondition: (ComputeNumSignBits(C2) <= C1)
  %a = lshr i8 %x, C1
  %r = icmp ugt i8 %a, C2
=>
  %r = icmp slt i8 %x, 0


ERROR: Mismatch in values of i1 %r

Example:
%x i8 = 0x80 (128, -128)
C1 i8 = 0x07 (7)
C2 i8 = 0xD0 (208, -48)
%a i8 = 0x01 (1)
Source value: 0x0 (0)
Target value: 0x1 (1, -1)

Am i holding it wrong, or is this missing some preconditions?

This revision now requires changes to proceed.Jan 11 2021, 6:29 AM
spatel added a subscriber: nlopes.Jan 11 2021, 7:18 AM

alive1 does not actually have a countLeadingOnes() precondition

Weird - maybe @nlopes can tell us how this example parses at all then: https://rise4fun.com/Alive/juX1

(at least as per https://github.com/nunoplopes/alive/blob/master/constants.py),
so the proof is faulty. ComputeNumSignBits(), OTOH, works for me:

...

Am i holding it wrong, or is this missing some preconditions?

Your example has lshr, but we only want to check ashr here, right?

Take a look at this one:
https://rise4fun.com/Alive/o8vS

ERROR: Mismatch in values of i1 %r

Example:
%x i8 = 0x80 (128, -128)
C1 i8 = 0x04 (4)
C2 i8 = 0xFA (250, -6)
%a i8 = 0xF8 (248, -8)
Source value: 0x0 (0)
Target value: 0x1 (1, -1)

This failure does not correspond to the pre-condition, does it? The number of signbits in C2 == 0xFA is 5, and 5 <= 4 is not true.

alive1 does not actually have a countLeadingOnes() precondition

Weird - maybe @nlopes can tell us how this example parses at all then: https://rise4fun.com/Alive/juX1

(at least as per https://github.com/nunoplopes/alive/blob/master/constants.py),

Ah, the rise4fun.com version uses the newsema branch. countLeadingOnes seems to be implemented in newsema but not in master.
(the newsema has better support for undef & poison, which wasn't complete in the original/master version. I don't remember why this branch wasn't merged, but I think it broke some functionality)

Anyone see problems with this Alive2 implementation using count-leading-*?
https://alive2.llvm.org/ce/z/SWxadd

I also manually entered all of the i4 regression tests with fixed constants in Alive1 (rise4fun), and they appear to be correct as shown in the test diffs.

lebedev.ri accepted this revision.Jan 11 2021, 8:52 AM

LGTM

Anyone see problems with this Alive2 implementation using count-leading-*?
https://alive2.llvm.org/ce/z/SWxadd

I also manually entered all of the i4 regression tests with fixed constants in Alive1 (rise4fun), and they appear to be correct as shown in the test diffs.

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

This revision is now accepted and ready to land.Jan 11 2021, 8:52 AM

Anyone see problems with this Alive2 implementation using count-leading-*?
https://alive2.llvm.org/ce/z/SWxadd

I also manually entered all of the i4 regression tests with fixed constants in Alive1 (rise4fun), and they appear to be correct as shown in the test diffs.

That's a clever way!
Another way is to use assume to encode the precondition if you prefer: https://alive2.llvm.org/ce/z/__szVL

Another way is to use assume to encode the precondition if you prefer: https://alive2.llvm.org/ce/z/__szVL

Thanks for the improved examples! It would be great if we collected things like that to use as reference/documentation (maybe there's already a folder, but I just don't know about it?).

Another way is to use assume to encode the precondition if you prefer: https://alive2.llvm.org/ce/z/__szVL

Thanks for the improved examples!

It would be great if we collected things like that to use as reference/documentation

Yes

(maybe there's already a folder, but I just don't know about it?).

Not that i know of, which means it [effectively] doesn't exist.

This revision was automatically updated to reflect the committed changes.