This is an archive of the discontinued LLVM Phabricator instance.

[GVN,NewGVN] Keep nonnull if K does not move.
ClosedPublic

Authored by fhahn on May 24 2018, 10:52 AM.

Details

Summary

In combineMetadata, we should be able to preserve K's nonnull metadata,
if K does not move. This condition should hold for all replacements by
NewGVN/GVN, but I added a bunch of assertions to verify that.

Fixes PR35038.

There probably are additional kinds of metadata that could be preserved
using similar reasoning. This is follow-up work.

Diff Detail

Repository
rL LLVM

Event Timeline

fhahn created this revision.May 24 2018, 10:52 AM

This assertion must hold for all replacements independent of this patch, because it would be invalid SSA otherwise.
I don't think the assertion is worth it given that.
The only case that is not true is when you are replacing into a phi node in a successor block (and there it is legal because it dominates that edge, even if it does not dominate the phi node).
Your assertion also would not catch this case.

Past that, I assume this works in the memory models being laid out by Nuno, Sanjoy, et al, but adding Nuno to verify.

fhahn updated this revision to Diff 148584.May 25 2018, 4:37 AM

Thanks @dberlin . Remove the assertions, they were mostly there to convince myself that nothing strange is going on.

nikic added a subscriber: nikic.May 25 2018, 10:54 AM

The optimization looks good to me.

So, just curious if we can get rid of the extra parameters you've added.
If you bootstrap with combineMetadata and patchReplacement asserting that the replacement dominates, does the assertion trigger?
If not, we can get rid of the parameters
If so, i'd love to see an example where so it can be analyzed.

fhahn updated this revision to Diff 148897.May 29 2018, 6:49 AM

The parameter for patchReplacement is certainly not needed, I removed it. For most other uses, there is no dominance for combineMetadata, as it is used for code sinking and hoisting with instructions form different code paths. I've created D47475 to handle all calls to combineMetadata explicitly.

nlopes added inline comments.Jun 4 2018, 3:02 PM
test/Transforms/NewGVN/metadata-nonnull.ll
45 ↗(On Diff #148897)

This doesn't seem correct to be in the model where load !nonnull is not UB. Passing poison as a function argument is not UB. The function might not even use the argument, for example.
Anyway, we need to define the semantics !nonnull before moving on, otherwise we can't tell if this is correct or not.

nikic added inline comments.Jun 5 2018, 3:39 AM
test/Transforms/NewGVN/metadata-nonnull.ll
45 ↗(On Diff #148897)

This is replacing a !nonnull load with an ordinary load, so this shouldn't be exploiting UB. As far as I can see this test corresponds to the existing behavior, it only ensures that the !nonnull in bb1 is not incorrectly propagated to the load in top.

fhahn updated this revision to Diff 149939.Jun 5 2018, 4:42 AM

Rebased after Local.h got moved. I've also added some CHECK-NOT lines to ensure nonnull is not propagated in the negative test cases.

fhahn added inline comments.Jun 5 2018, 4:44 AM
test/Transforms/NewGVN/metadata-nonnull.ll
45 ↗(On Diff #148897)

This doesn't seem correct to be in the model where load !nonnull is not UB. Passing poison as a function argument is not UB. The function might not even use the argument, for example.

I think I am missing something there. @use1 is readonly, so the loaded value should not change? @test7 is a similar test case where @use2 might change the loaded value.

nlopes added inline comments.Jun 5 2018, 8:12 AM
test/Transforms/NewGVN/metadata-nonnull.ll
98 ↗(On Diff #149939)

Somehow the line numbers changed. Getting back to my point: here "ret %v2" is replaced with "ret %v1". So it replaces a normal load with a nonnull load.
This is correct only if the nonnull load is UB. The use by "@use1" call does turn into UB if %v1 is poison. So we need to define if the load is UB or if it returns poison. I don't have any insight to have a preferred option, tough.

fhahn added inline comments.Jun 7 2018, 2:03 AM
test/Transforms/NewGVN/metadata-nonnull.ll
98 ↗(On Diff #149939)

Ah right, thanks! So if the nonnull load would be poison, then it would not work, as the rational behind preserving the !nonnull metadata here would be that %v1 is guaranteed to be nonnull, so the later loads of the same location must also be nonnull.

Eli's clarification of the LangRef in D47747 make loading null from a nonnull load UB, which would make this behaviour OK IIUC, assuming it goes in :)

fhahn updated this revision to Diff 156286.Jul 19 2018, 9:07 AM
fhahn retitled this revision from [GVN,NewGVN] Propagate nonnull if K dominates J. to [GVN,NewGVN] Keep nonnull if K does not move..
fhahn edited the summary of this revision. (Show Details)

Renamed KDominatesJ to DoesKMove as suggested by Eli in D47475.

efriedma added inline comments.Jul 19 2018, 4:03 PM
include/llvm/Transforms/Utils/Local.h
391 ↗(On Diff #156286)

I think the name DoesKMove is backwards, if you're defaulting it to "false".

fhahn updated this revision to Diff 156512.Jul 20 2018, 9:14 AM

Flip default for DoesKMove.

This revision is now accepted and ready to land.Jul 30 2018, 3:18 PM
fhahn added a comment.Aug 1 2018, 6:33 AM

Thank you very much Eli! This patch depends on D47337, which actually moves combineMetadata to Utils/Local. It would be great if someone could have a quick look there too, if it's the right place to move it to.

This revision was automatically updated to reflect the committed changes.