This is an archive of the discontinued LLVM Phabricator instance.

[BDCE] clear poison generators after turning a value into zero (PR33695, PR34037)
ClosedPublic

Authored by spatel on Aug 10 2017, 2:29 PM.

Details

Summary

Since we have a known miscompile danger here, I'll propose a patch for people to look at.
This is the most basic (yet still incomplete) solution that I could come up with for the miscompiles in:
https://bugs.llvm.org/show_bug.cgi?id=33695
https://bugs.llvm.org/show_bug.cgi?id=34037

As discussed in PR33695, we need to do more than this, and there are probably better implementations, but this is a safe first step to close the hole?

Diff Detail

Repository
rL LLVM

Event Timeline

spatel created this revision.Aug 10 2017, 2:29 PM
majnemer added inline comments.
lib/Transforms/Scalar/BDCE.cpp
56 ↗(On Diff #110633)

I recommend using a worklist so that this doesn't blow up the stack.

hfinkel added inline comments.Aug 10 2017, 7:50 PM
lib/Transforms/Scalar/BDCE.cpp
50 ↗(On Diff #110633)

Just to make this a little better: if any of the users are a store, call, invoke, atomicrmw, atomiccmpxchg, or return - anything that will make the value externally observable, we can stop recursing to clear the flags.

54 ↗(On Diff #110633)

I can't think of any current metadata that would be invalidated, but assumes might indeed be.

davide requested changes to this revision.Aug 10 2017, 11:16 PM

I concur with David that this should use a worklist.

This revision now requires changes to proceed.Aug 10 2017, 11:16 PM
spatel updated this revision to Diff 110728.Aug 11 2017, 8:05 AM
spatel edited edge metadata.
spatel marked 2 inline comments as done.

Patch updated:

  1. Use a loop (worklist) rather than recursion to avoid blowing up the stack.
  2. Add an exclusion list based on opcodes to stop the search.
  3. Add a test to show that the exclusion list works for a call inst.
  4. Add a TODO comment with Nuno's suggestion from the bug report to make this better.
hfinkel added inline comments.Aug 11 2017, 8:59 AM
lib/Transforms/Scalar/BDCE.cpp
46 ↗(On Diff #110728)

I think this is better than the opcode list I suggested. Why don't we just do this instead? Isn't it just something like this?

auto isExternallyVisible = [&](Instruction *I) {
  // Any value we're trivializing should be an integer value, and moreover, any conversion between an integer value and a non-integer value should demand all of the bits, which will cause us to stop looking down the use/def chain, so we should only see integer-typed instructions here.
  assert(I->getType()->isIntegerTy() && "Trivializing a non-integer value?");
  return DB.getDemandedBits(I).isAllOnesValue();
}
80 ↗(On Diff #110728)

Range metadata can't be invalid here because it applies only to memory accesses (which demand all bits). As a result, I'd like to not see it in a TODO, although a comment explaining why it's not an issue would be good.

80 ↗(On Diff #110728)

Please just include the assume check if it is not complicated. I think this will work:

if (auto *II = dyn_cast<IntrinsicInst>(J)) {
  if (II->getIntrinsicID() == Intrinsic::assume)
   // We can delete the assume here because it can't appear in the worklist multiple times (because it only has one operand).
   II->eraseFromParent();
 }
spatel updated this revision to Diff 110786.Aug 11 2017, 12:32 PM

Patch updated - mostly just cutting and pasting the code Hal posted:

  1. Make isExternallyVisible() check the calculated demanded bits rather than a list of opcodes.
  2. Add a check for and delete llvm.assume.

I've been trying to find a test for the llvm.assume part, but I haven't gotten anywhere, so I'm probably not understanding that case. An assume takes an i1 param, so it always demands all the bits of that param. And therefore, the assume will never be added to the worklist?

nlopes edited edge metadata.Aug 12 2017, 2:54 AM

LGTM, with minor comments: missing the CHECK comment above, and missing a test for the assume removal.

test/Transforms/BDCE/invalidate-assumptions.ll
72 ↗(On Diff #110786)

Missing CHECK comment here.

spatel updated this revision to Diff 110837.Aug 12 2017, 7:33 AM

Patch updated - sorry, the last diff was not the one I intended to upload. This is NFC from the last rev, but:

  1. Includes Hal's comment about range metadata.
  2. Has CHECK lines for the poison_on_call_user_is_ok() test.

I'm still not sure how to test the llvm.assume case - any ideas?

hfinkel edited edge metadata.Aug 12 2017, 7:37 AM

The comments about assume, otherwise, LGTM too.

lib/Transforms/Scalar/BDCE.cpp
71 ↗(On Diff #110786)

I've changed my mind about assume. I believe, now that you're checking the demanded bits, you can't hit this case. The issue is that the assume demands its operand, and it must do this. Essentially, the value of the condition is an observable of the program (i.e. trivializing values can't change it). If there's a compare feeding the assume, for example, it in turn demands whatever bits are necessary in order to ensure its result. As a result, the compare shouldn't imply anything about its operands that trivializing changes (if it did, then the truth of the condition would not have have universally implied that thing in the first place). Thus, I think you can just remove the assume handling.

72 ↗(On Diff #110786)

You need a continue after this. You can't then dereference J.

spatel updated this revision to Diff 110839.Aug 12 2017, 7:56 AM
spatel marked an inline comment as done.

Patch updated:
Replace the assume deletion with a comment about why it can't happen. :)

hfinkel accepted this revision.Aug 12 2017, 8:00 AM

LGTM

This revision was automatically updated to reflect the committed changes.