This is an archive of the discontinued LLVM Phabricator instance.

Fix a bug w/inbounds invalidation in LFTR (was: Strengthen LFTR's ability to replace IVs)
ClosedPublic

Authored by reames on Jun 5 2019, 7:38 PM.

Details

Summary

This contains fixes for two cases where we might invalidate inbounds and leave it stale in the IR (a miscompile). Case 1 is when switching to an IV with no dynamically live uses, and case 2 is when doing pre-to-post conversion on the same pointer type IV.

As was pointed out in the review thread by Nikita, this is defending against a separate issue from the hasConcreteDef case. This is about poison, that's about undef. Unfortunately, the two are different, see Nikita's comment for a fuller explanation, he explains it well.

Diff Detail

Event Timeline

reames created this revision.Jun 5 2019, 7:38 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 5 2019, 7:38 PM
nikic added inline comments.Jun 6 2019, 9:37 AM
lib/Transforms/Scalar/IndVarSimplify.cpp
2079

nit: Return true if ... provably

2082

nit: s/LoopExisting BB/ExitingBB

2101

I feel like there's some confusion here between instructions that have a poison operand and instructions that produce poison. As you're inserting into Visited before doing the propagation test, Visited holds instructions that have a poison operand. However, in the Visited.count(NotPoison) check below you are assuming that Visited instructions return poison.

2116

Why is this condition separate? This seems wrong for a) non-dominating store and b) poison being on the value operand, not the pointer operand.

2118

I think this isn't right as documented (branching on poison is not UB and there may be abnormal exits), though it seems okay for the purpose we need this.

nikic added a comment.Jun 6 2019, 9:44 AM

I think overall doing something like this makes sense: For pointer IVs, we'll pretty much always have either a load or store on it.

reames updated this revision to Diff 203397.Jun 6 2019, 10:08 AM

Cleanup code and fix a couple of bugs in the process.

reames marked 3 inline comments as done.Jun 6 2019, 10:12 AM

Address a few of Nikita's comment. I ended up heavily revising the structure, so the line locations got a bit confusing.

lib/Transforms/Scalar/IndVarSimplify.cpp
2101

See the revised code. It should be a lot more clear on this.

2116

That's specifically why it's separate. The LangRef specifically gives an example of a poison value operand to a store being UB.

2118

wait, wait. No. Branching on posion is *definitely* UB. Or at least I believe it is! What makes you think otherwise?

reames updated this revision to Diff 203400.Jun 6 2019, 10:21 AM

Revise comments per Nikita's suggestions and some further word smithing of my own.

nikic added inline comments.Jun 6 2019, 11:02 AM
lib/Transforms/Scalar/IndVarSimplify.cpp
2116

Storing poison is not UB for a normal store. Langref seems to say that it is UB for a volatile store, because volatile is externally observable. It only says that in an example though, and it's not clear how that follows from the preceding definitions.

The langref description of poison semantics is really quite bad. It describes the dependence behavior, but does not explain when exactly a dependence on poison triggers immediate UB.

2118

I used to think that as well, but unfortunately it's not the case. Branching on poison is not UB itself, you need a side-effect that is control dependent on the poisoned branch. There is a proposal to make branching on poison immediate UB (http://www.cs.utah.edu/~regehr/papers/undef-pldi17.pdf and https://lists.llvm.org/pipermail/llvm-dev/2016-October/106182.html), but I don't think this went anywhere.

reames planned changes to this revision.Jun 6 2019, 12:09 PM
reames marked 2 inline comments as done.
reames added inline comments.
lib/Transforms/Scalar/IndVarSimplify.cpp
2116

I want to debate this point further, but for the moment, I'll simply remove the special store case. As you point out, even without this it's really useful for pointer IVs, and we can separate that discussion into a separate patch/step.

2118

Gah, you're correct. I'd forgotten the unswitching case.

For the moment, I'll remove the branch handling from the current patch, and then come back to figure out how to handle it separately.

That does mean we probably have another bug in LFTR though. We treat a comparison used in the exit test as being concrete which per this discussion seems not guaranteed if the loop contains no side effects.

reames updated this revision to Diff 203416.Jun 6 2019, 12:17 PM

Remove the two cases Nikita noted.

Nikita, do you see any other problems with this? If it looks okay conceptually, my next step will be to write a bunch of tests. I'd like to check this in to IndVarSimplify, and then in a separate reviewed NFC change move it into ValueTracking and common with the existing version as much as possible. Does that seem like a reasonable plan?

I'm not entirely comfortable trying to test this exclusively through LFTR. Any ideas on how to better expose it? (I'm not saying I think testing through LFTR isn't a reasonable starting point to get it committed, just that long term, I think the final code in ValueTracking will be too important to only test through one transform.)

nikic added inline comments.Jun 6 2019, 1:19 PM
lib/Transforms/Scalar/IndVarSimplify.cpp
2084

Rename PoisonI to I and Visited to KnownPoison? PoisonI is a bit odd in that it needn't be itself poison. Can also drop DT argument.

2104

I don't understand the phi logic here. If you have

x1 = poison
if (...)
  x2 = not poison
x3 = phi(x1, x2)

then x3 is not guaranteed poison, even though x1 dominates the phi.

2135

Should probably swap these conditions.

nikic added a comment.Jun 6 2019, 1:22 PM

Regarding testing, if this code is in ValueTracking it would be possible to unit test it: https://github.com/llvm-mirror/llvm/blob/master/unittests/Analysis/ValueTrackingTest.cpp That is provide a bit of IR and then check an instruction with some defined name.

reames updated this revision to Diff 203449.Jun 6 2019, 2:35 PM

Remove the buggy phi code Nikita pointed out and otherwise address last round of comments from Nikita.

reames marked an inline comment as done.Jun 6 2019, 2:36 PM
reames added inline comments.
lib/Transforms/Scalar/IndVarSimplify.cpp
2135

Out of curiosity, why? This seems natural to me and seems to fit the existing idiom in ValueTracking.

nikic added inline comments.Jun 7 2019, 12:07 PM
lib/Transforms/Scalar/IndVarSimplify.cpp
2135

That was just a perf consideration. Instruction dominance without OBB is a linear scan.

reames marked an inline comment as done.Jun 10 2019, 10:21 AM
reames added inline comments.
lib/Transforms/Scalar/IndVarSimplify.cpp
2135

Oh! The comment ended up shifting lines on the new patch. Yeah, that makes perfect sense!

reames updated this revision to Diff 203879.Jun 10 2019, 12:54 PM

Rebase on top of newly added tests.

After staring at the test diffs, I think we may have to recombine this back into D62936. The problem is that by being willing to switch IVs for pointers (correctly now), we *also* expose more pre-to-post conversion opportunities on the new IVs. So, despite getting the logic about dead IVs right, we're still miscompiling these in the end.

nikic added inline comments.Jun 10 2019, 2:30 PM
lib/Transforms/Scalar/IndVarSimplify.cpp
2098

wit -> with

2106

out -> our, though given the generalized formulation used here now, we shouldn't mention "exit block" anymore.

2265

Unfortunately, I don't think this is right :( The problem is that hasConcreteDef() deals with a similar but distinct issue: an undef IV, not a poison one.

Consider an IV of the form {undef,+,1} (without nuw/nsw, so never poison). In theory there is nothing wrong with using such an IV. However, due to LLVMs broken implementation of undef, it is generally illegal to add a new use to a value that is potentially undef, because the fact that two uses of undef must be the same will not be preserved. This is why the hasConcreteDef() check is necessary.

Now, the mustExecuteUBIfPoisonOnPathTo() check is correct if we assume that Phi is poison, but not if it is undef, because they have different propagation semantics. For example:

%iv = {undef,+,1}
%or = or %iv, 1
%div = udiv -1, %or
br -> exit

Here, if %iv were poison, then the udiv would trigger UB and it would be safe to add a new use. However, it is only undef here, in which case the udiv will *not* trigger UB. But because the check is performed under the assumption of poison, we'll incorrectly switch to this IV.

reames updated this revision to Diff 203918.Jun 10 2019, 3:43 PM
reames retitled this revision from Strengthen LFTR's ability to replace IVs to Fix a bug w/inbounds invalidation in LFTR (was: Strengthen LFTR's ability to replace IVs).
reames edited the summary of this revision. (Show Details)

Minor rebase. As pointed out by previous comments both from myself and Nikita, the entire approach here is broken. This doesn't actually appear to be separable from D62936. Given all the meaningful review has happened here, I'm going to repurpose this review for the bug fix and close that one.

For the moment though, this patch is known stale and needs reworked.

reames updated this revision to Diff 203926.Jun 10 2019, 4:05 PM

First iteration on a combined patch. The tests need updated to reflect the poison/undef split. I'll do that, then rebase on top.

reames updated this revision to Diff 203929.Jun 10 2019, 4:25 PM

Rebase over tweaked tests and address comments from Nikita.

nikic added a comment.Jun 11 2019, 1:21 PM

I was going to suggest that we only perform the poison/UB check if the GEP actually is inbounds... but I guess that wouldn't be quite right, as the poison can also come from the start value rather than the increment.

Let me try to summarize all the problems we can run into and how they will be handled as of this patch. Thankfully, our IV always has the simple form IV = {S,+,1}. Then, there are the following cases:

  1. S may be undef. Handled by hasConcreteDef().
  2. S may be poison. For pointers: Poison/UB check or prevent LFTR. For integers: Not handled.
  3. IV may become poison due to nowrap/inbounds on last iteration. For pointers: Poison/UB check or use pre-inc. For integers: Recompute nowrap flags.
  4. IV may become poison due to nowrap/inbounds on arbitrary iteration. For pointers: Poison/UB check or prevent LFTR. For integers: Recompute nowrap flags, but recomputation is not fully correct right now.

Notably, we don't handle case 2 for integers. We could drop the pointer type check. Probably better would be to instead handle cases 1&2 together by turning hasConcreteDef() into isNeverUndefOrPoison(). This would be similar to hasConcreteDef(), but also returning false for instructions with poison flags (I think that hasConcreteDef() should be doing that even when checking for undef, because ultimately we'll end up relaxing poison to undef anyway, due to lack of poison representation in IR.) An important case where isNeverUndefOrPoison() returns true is a constant start value, which many of the test cases have, I believe.

Then, we could split handling as follows. First, determine whether an IV can be used at all:

  • If pre-inc IV (or a poison-propagating dependent value, including the post-inc IV) is used in current loop condition: Can use IV.
  • Otherwise, if S is may be undef or poison: Don't use IV.
  • Otherwise, if integer IV or pointer IV without inbounds: Can use IV.
  • Otherwise, if UB check on pre-inc IV succeeds: Can use IV.
  • Otherwise, don't use IV.

Second, determine what to do about post-inc IV. For integers are recompute flags. For pointers:

  • If post-inc IV (or a poison-propagating dependent value) is used in current loop condition: Can use post-inc.
  • Otherwise, if UB check on post-inc IV succeeds: Can use post-inc.
  • Otherwise, use pre-inc.

I think that this should be close to the best we can do, though things are getting quite complicated here.

(Not saying we should do this in this revision, I'm just trying to sort out my thoughts.)

Let me try to summarize all the problems we can run into and how they will be handled as of this patch. Thankfully, our IV always has the simple form IV = {S,+,1}. Then, there are the following cases:
....

  1. S may be poison. For pointers: Poison/UB check or prevent LFTR. For integers: Not handled.

...

Actually, think 'S' being poisoned is almost fully handled or maybe even fully handled. If 'S' is poison, then IV must be poison on at least the first iteration. Given that, if we find a side effect which must execute on the path to our exit block, then we've proven we must have executed UB. As such, the program is undefined and we have no further obligations.

The only case where this line of reasoning doesn't work is a) our exit itself isn't evaluated on the first iteration and b) there's some operation within the IV computation which 1) strips poison from a poison input and 2) contributes to the next iteration of the IV.

Do there even exist operations which perform (b)? That would seem to be a contradiction.

If there aren't, then we're fully covered. If there are, then we'd need to find a UB operation on the path to the backedge to ensure poison on a prefix of the iteration space (only) is covered. This would be easy to implement, though I'd prefer to do so in a separate change for sanity at this point. :)

nikic added a comment.Jun 12 2019, 1:24 PM

Actually, think 'S' being poisoned is almost fully handled or maybe even fully handled. If 'S' is poison, then IV must be poison on at least the first iteration. Given that, if we find a side effect which must execute on the path to our exit block, then we've proven we must have executed UB. As such, the program is undefined and we have no further obligations.

The only case where this line of reasoning doesn't work is a) our exit itself isn't evaluated on the first iteration and b) there's some operation within the IV computation which 1) strips poison from a poison input and 2) contributes to the next iteration of the IV.

Do there even exist operations which perform (b)? That would seem to be a contradiction.

If there aren't, then we're fully covered. If there are, then we'd need to find a UB operation on the path to the backedge to ensure poison on a prefix of the iteration space (only) is covered. This would be easy to implement, though I'd prefer to do so in a separate change for sanity at this point. :)

If the mustExecuteUBIfPoisonOnPathTo() check is performed, then, as you argue, we do handle S being poison properly. It's just that the check is only performed on pointers, but not integers (in this patch).

In any case, let's defer that one, this patch is about pointers. There's one last tweak I'd like to see here: If the condition already depends on the post-inc IV, then we can safely use it. Going through the test cases this is actually the case for most of the regressions in existing tests (I've left comments), so I think it would be very worthwhile to check this case.

lib/Transforms/Scalar/IndVarSimplify.cpp
2080

posion -> poison

2092

Given the now more general formulation of the function, the mention of "exiting block" should probably be dropped.

test/Transforms/IndVarSimplify/2011-11-01-lftrptr.ll
350

Condition already depends on post-inc IV.

test/Transforms/IndVarSimplify/lftr-address-space-pointers.ll
47 ↗(On Diff #203929)

Condition already depends on post-inc IV.

97 ↗(On Diff #203929)

Condition already depends on post-inc IV.

test/Transforms/IndVarSimplify/lftr-reuse.ll
55

Condition already depends on post-inc IV.

326

Condition already depends on post-inc IV.

If the mustExecuteUBIfPoisonOnPathTo() check is performed, then, as you argue, we do handle S being poison properly. It's just that the check is only performed on pointers, but not integers (in this patch).

Ah, agreed.

In any case, let's defer that one, this patch is about pointers. There's one last tweak I'd like to see here: If the condition already depends on the post-inc IV, then we can safely use it. Going through the test cases this is actually the case for most of the regressions in existing tests (I've left comments), so I think it would be very worthwhile to check this case.

Very nice observation! Will incorporate and update shortly.

reames updated this revision to Diff 204364.Jun 12 2019, 3:02 PM

Incorporate Nikita's suggestion about IVs which are already post-increment, and just need their formed changed.

nikic accepted this revision.Jun 13 2019, 10:03 AM

LGTM

lib/Transforms/Scalar/IndVarSimplify.cpp
2411

We could move IncVar declared below to the top of the function, use it here and also change the CmpIndVar assignment below to CmpIndVar = IncVar. As is, we're accessing this value three times in this function...

This revision is now accepted and ready to land.Jun 13 2019, 10:03 AM
This revision was automatically updated to reflect the committed changes.

This caused a regression, where compilation now crashes. See https://bugs.llvm.org/show_bug.cgi?id=42279 for details.