This is an archive of the discontinued LLVM Phabricator instance.

[ValueTracking] ComputeKnownBits - minimum leading/trailing zero bits in LSHR/SHL (PR44526)
ClosedPublic

Authored by RKSimon on Oct 30 2020, 10:33 AM.

Details

Summary

Followup to D72573 - as detailed in https://blog.regehr.org/archives/1709 we don't make use of the known leading/trailing zeros for shifted values in cases where we don't know the shift amount value.

Stop ValueTracking returning zero for poison shift patterns and use the KnownBits shift helpers directly.

Extend KnownBits::shl to combine all possible shifted combinations if both min/max shift amount values are in range.

Diff Detail

Event Timeline

RKSimon created this revision.Oct 30 2020, 10:33 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 30 2020, 10:33 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
RKSimon requested review of this revision.Oct 30 2020, 10:33 AM
RKSimon added inline comments.Oct 30 2020, 10:39 AM
llvm/test/Transforms/InstCombine/and2.ll
155 ↗(On Diff #301948)

These tests look like they might even need to be scrapped? And we just limit the transform to Shl instead of logical shifts in general.

llvm/test/Transforms/InstCombine/lshr-and-negC-icmpeq-zero.ll
191 ↗(On Diff #301948)

Replace with -12345 so we don't have leading zeroes?

llvm/test/Transforms/InstCombine/signbit-shl-and-icmpeq-zero.ll
190 ↗(On Diff #301948)

Replace with -2147483649 so we don't have trailing zeroes?

efriedma added inline comments.Oct 30 2020, 11:13 AM
llvm/lib/Analysis/ValueTracking.cpp
1245

We could also do AShr... not really useful for known zeros, but maybe for known ones.

llvm/test/Transforms/InstCombine/and2.ll
155 ↗(On Diff #301948)

I suspect we might want to continue to favor icmp+zext over lshr.

RKSimon planned changes to this revision.Nov 7 2020, 7:06 AM
RKSimon updated this revision to Diff 305760.Nov 17 2020, 5:53 AM
RKSimon edited the summary of this revision. (Show Details)

Rebase now that computeKnownBitsFromShiftOperator's callbacks uses KnownBits shift handling.

RKSimon planned changes to this revision.Nov 17 2020, 6:22 AM
RKSimon updated this revision to Diff 308079.Nov 27 2020, 9:46 AM
RKSimon retitled this revision from [WIP][ValueTracking] ComputeKnownBits - minimum leading/trailing zero bits in LSHR/SHL (PR44526) to [ValueTracking] ComputeKnownBits - minimum leading/trailing zero bits in LSHR/SHL (PR44526).
RKSimon edited the summary of this revision. (Show Details)

Move the and(logical_shift(1, X), 1) --> zext(X == 0) earlier so SimplifyDemandedInstructionBits doesn't remove the pattern.

spatel added inline comments.Nov 30 2020, 4:58 AM
llvm/lib/Analysis/ValueTracking.cpp
996–1003

I'm not sure if it changes anything directly here, but we should revisit this conflict logic (similarly at the final block in the function) because we have a poison value in IR with D71126 (see also D92270).

RKSimon marked an inline comment as done.Nov 30 2020, 7:14 AM
RKSimon added inline comments.
llvm/lib/Analysis/ValueTracking.cpp
996–1003

TBH - I don't think we should be setting 'known bits' to arbitrary/poison numbers like this inside ValueTracking - poison handling should be inside the shift combines and we should just return 'unknown' here.

Is this something that needs to be addressed before this patch do you think? I've just kept to the current behaviour here so far.

spatel added inline comments.Nov 30 2020, 8:53 AM
llvm/lib/Analysis/ValueTracking.cpp
996–1003

I'm not sure if this patch exposes a new way for that clamp to zero to cause trouble, but I agree that we can return unknown state here and try to deal with the poison cases more directly in instsimplify or other passes.

RKSimon updated this revision to Diff 325446.Feb 22 2021, 7:46 AM

Rebase + simplify after D95959

Poison nsw shl patterns no longer return zero and instead bails out - InstSimplify should handle this and return poison.

RKSimon updated this revision to Diff 325451.Feb 22 2021, 8:05 AM

Add shl nsw poison handling to SimplifyShlInst

spatel added inline comments.Feb 22 2021, 8:50 AM
llvm/lib/Analysis/ValueTracking.cpp
1057–1058

Do you plan to change this independently (or is there some reason not to change it)?

RKSimon added inline comments.Feb 22 2021, 8:56 AM
llvm/lib/Analysis/ValueTracking.cpp
1057–1058

thanks - my rebase screwed up

RKSimon marked an inline comment as not done.Feb 22 2021, 9:36 AM
RKSimon added inline comments.
llvm/lib/Analysis/ValueTracking.cpp
1057–1058

and fixing this unearthes another poison case - looking at this now

RKSimon updated this revision to Diff 325558.Feb 22 2021, 1:54 PM
RKSimon marked an inline comment as not done.
RKSimon edited the summary of this revision. (Show Details)

KnownBits::shl - combine all possible shifted combinations if both min/max shift amount values are in range - helps find some additional poision cases and prevents another regression due to ValueTracking clearing all KnownBits for poison shifts.

nikic added a reviewer: nikic.Feb 22 2021, 2:02 PM
RKSimon updated this revision to Diff 325725.Feb 23 2021, 3:04 AM

Add early-out from KnownBits::shl loop if we know no bits

RKSimon updated this revision to Diff 325835.Feb 23 2021, 10:32 AM
RKSimon edited the summary of this revision. (Show Details)

rebase

spatel accepted this revision.Feb 23 2021, 1:15 PM
spatel added a subscriber: aqjune.

cc @aqjune - another step away from undef. :)

LGTM - hoping that the 'nsw' check before the computeKnownBits means the compile-time impact is minimal, but that's something to watch out for.

This revision is now accepted and ready to land.Feb 23 2021, 1:15 PM
nikic added inline comments.Feb 23 2021, 1:27 PM
llvm/lib/Support/KnownBits.cpp
207

Hm, this code basically repeats what ValueTracking does in a slightly weaker form (using all shifts between min and max, rather than only the possible ones). If we're going to do this inside the KnownBits function itself, then I think we should be doing it only here, not in both places.

RKSimon added inline comments.Feb 24 2021, 3:52 AM
llvm/lib/Support/KnownBits.cpp
207

I'm intending to clean this up as a followup - cheers

This revision was landed with ongoing or failed builds.Feb 24 2021, 4:16 AM
This revision was automatically updated to reflect the committed changes.

It seems that this commit has caused several test failures.

You can see here: http://lab.llvm.org:8011/#/builders/52/builds/4550

Could you please fix them?
Thanks,

It seems that this commit has caused several test failures.

You can see here: http://lab.llvm.org:8011/#/builders/52/builds/4550

Could you please fix them?
Thanks,

I've reverted for now - I took a quick look at the sanitizer test and couldn't grok whats going wrong, will try again when I'm awake :)

I've reverted for now - I took a quick look at the sanitizer test and couldn't grok whats going wrong, will try again when I'm awake :)

Thanks for your quick response :).