This is an archive of the discontinued LLVM Phabricator instance.

[InstSimplify] don't let poison inhibit an easy fold
ClosedPublic

Authored by spatel on Oct 6 2017, 10:34 AM.

Details

Summary

D38591 offers one way to avoid the assert in PR34838, but we could just explicitly handle this pattern in InstSimplify to make life easier for InstCombine. This also avoids using computeKnownBits() if we don't have to and gets known bad code reduced faster, so we're not wasting time on it.

Diff Detail

Event Timeline

spatel created this revision.Oct 6 2017, 10:34 AM
efriedma edited edge metadata.Oct 6 2017, 12:20 PM

If I understand correctly, the reason computeKnownBits can't handle this is that it doesn't know what to do with a known poison value? We could just solve the issue in computeKnownBits: currently, it says there are no known bits when it detects a shift overflow, but it could just say, for example, that all the bits are known zero (since the result of computeKnownBits is only meaningful if the value isn't poison).

If I understand correctly, the reason computeKnownBits can't handle this is that it doesn't know what to do with a known poison value? We could just solve the issue in computeKnownBits: currently, it says there are no known bits when it detects a shift overflow, but it could just say, for example, that all the bits are known zero (since the result of computeKnownBits is only meaningful if the value isn't poison).

Ah, I thought that wasn't an option. I remember some bug report related to undef handling in computeKnownBits that made we think we have to be conservative, but I'm not locating it. We have these comments in computeKnownBitsFromShiftOperator():

// If there is conflict between Known.Zero and Known.One, this must be an
// overflowing left shift, so the shift result is undefined. Clear Known
// bits so that other code could propagate this undef.

...

// If the shift amount could be greater than or equal to the bit-width of the LHS, the
// value could be undef, so we don't know anything about it.

...

// If there are no compatible shift amounts, then we've proven that the shift
// amount must be >= the BitWidth, and the result is undefined. We could
// return anything we'd like, but we need to make sure the sets of known bits
// stay disjoint (it should be better for some other code to actually
// propagate the undef than to pick a value here using known bits).
spatel added a comment.Oct 6 2017, 1:09 PM

Also, this is in the header comment for computeKnownBits():
/ NOTE: we cannot consider 'undef' to be "IsZero" here. The problem is that
/ we cannot optimize based on the assumption that it is zero without changing
/ it to be an explicit zero. If we don't change it to zero, other code could
/ optimized based on the contradictory assumption that it is non-zero.

So since we don't know what the caller will do with the result, we're conservative. Is it different if something is known to produce poison rather than undef?

The exact definition of poison is still getting refined, but it's different from undef. undef is a bit-wise property, which is why ComputeKnownBits has to be careful around it. poison works differently; essentially, any arithmetic or logical operation which has poison as an input produces poison, no matter what the other input is. So it doesn't matter what ComputeKnownBits returns for a known poison value.

spatel added a comment.Oct 6 2017, 4:08 PM

The exact definition of poison is still getting refined, but it's different from undef. undef is a bit-wise property, which is why ComputeKnownBits has to be careful around it. poison works differently; essentially, any arithmetic or logical operation which has poison as an input produces poison, no matter what the other input is. So it doesn't matter what ComputeKnownBits returns for a known poison value.

Thanks! Then, it seems clear I can abandon the InstCombine fix, and I'll redo this one to work in value tracking directly.

spatel updated this revision to Diff 118138.Oct 7 2017, 8:48 AM

Patch updated:
Have computeKnownBitsFromShiftOperator() return a zero constant when we discover a conflict in known bits. This allows InstSimplify to fold compares.

spatel added inline comments.Oct 7 2017, 8:55 AM
lib/Analysis/ValueTracking.cpp
822–825

Oops - this comment doesn't make sense. An overshift produces poison too. Removing this check would mean we're going to fall through to the expensive check below more often though. Do we want to do that or should I just fix the comment?

spatel updated this revision to Diff 118139.Oct 7 2017, 9:00 AM

Patch updated:
Fix bogus comment about undef and add a TODO for a potential follow-up patch.

efriedma accepted this revision.Oct 11 2017, 7:11 PM

My only potential concern here is that we could end up blocking optimizations because we're folding to undef rather than zero... but that's probably rare enough that it doesn't matter. LGTM.

lib/Analysis/ValueTracking.cpp
822–825

IIRC the old version of this comment is just outdated; we recently adjusted LangRef to be a bit more aggressive with shifts because we have some transforms which depend on it being poison rather than undef.

Probably worth investigating getting rid of this at some point; I expect there are some interesting shifts we could analyze.

This revision is now accepted and ready to land.Oct 11 2017, 7:11 PM
spatel closed this revision.Oct 12 2017, 10:36 AM

Closed with rL315595