This is an archive of the discontinued LLVM Phabricator instance.

[Local] Make DoesKMove required for combineMetadata.
ClosedPublic

Authored by fhahn on May 29 2018, 6:46 AM.

Details

Summary

This patch makes the DoesKMove argument non-optional, to force people
to think about it. Most cases where it is false are either code hoisting
or code sinking, where we pick one instruction from a set of
equal instructions among different code paths.

Diff Detail

Event Timeline

fhahn created this revision.May 29 2018, 6:46 AM

Yes, this makes sense. But definitely needs tests.

fhahn updated this revision to Diff 149470.Jun 1 2018, 7:54 AM

Added tests for most cases. Missing are tests for MemCpyOptimizer and SimplifyCFG, but for those nothing changed, so would that be enough?

efriedma added inline comments.Jun 1 2018, 12:49 PM
lib/Transforms/Utils/Local.cpp
2330

Is it actually correct to use the same metadata list if KDominatesJ is false?

It's undefined behavior if a nonnull load actually produces null. So preserving nonnull metadata on a hoisted load requires proving that the hoisted load never produces null (separately from proving the load is safe to hoist).

dberlin added inline comments.Jun 1 2018, 12:57 PM
lib/Transforms/Utils/Local.cpp
2330

Yeah, i'm pretty sure there are some pre-existing bugs here, and this looks like it may be one of them.

I admit to wondering what we actually expect here.
The langref just says "The existence of the !nonnull metadata on the instruction tells the optimizer that the value loaded is known to never be null. "

Does that mean "never to be null when performed in this place in the instruction stream" or just "never be null. "

If the former, then yeah, when hoisting, we need to prove nonnullness or drop it.
If the latter, then hoisting would be fine.

I wonder how this is getting used in practice (IE are people treating it like the former/latter, and if the latter, do they expect hoisting to drop non-nullness).

efriedma added inline comments.Jun 1 2018, 1:02 PM
lib/Transforms/Utils/Local.cpp
2330

Actually, I guess none of the existing callers actually do that sort of hoisting.

But combineMetadataForCSE needs better documentation for when, exactly, it's correct to use.

efriedma added inline comments.Jun 1 2018, 1:15 PM
lib/Transforms/Utils/Local.cpp
2330

I'm not sure how you could usefully interpret the definition of !nonnull as anything other than "if the loaded value is null, the behavior is undefined", given that the optimizer can introduce impossible codepaths.

fhahn added inline comments.Jun 4 2018, 8:51 AM
lib/Transforms/Utils/Local.cpp
2330

Is it actually correct to use the same metadata list if KDominatesJ is false?

The default behavior for nonnull metadata did not change if KDominatesJ is false, it only combines nonnull md if both K and J have it.

IIUC if combineMetadata is used correctly, propagating nonnull from K to a dominated instr J is OK.

It would not be OK, (1) if K is later hoisted to a place where nonnull is not guaranteed to hold, but moving K is causing the undefined behavior, not combining of the metadata. And (2) if the loaded value might become null between K and J. For that to happen, the value needs to be modified and K would not be a valid replacement for J.

Am I missing something? The docs for combineMetadataForCSE state that K must be able to replace J, but is it worth to spelling it out more explicitly what that means?

efriedma added inline comments.Jun 4 2018, 10:36 AM
lib/Transforms/Utils/Local.cpp
2330

Yes, it would be better to spell it out.

nlopes added inline comments.Jun 4 2018, 3:00 PM
lib/Transforms/Utils/Local.cpp
2330

Just seconding what Daniel wrote: if a "load !nonnull" is UB if it loads null, then it cannot be hoisted (without dropping the flag). Instead it could rather yield poison.
Either is fine; I haven't done any study on what are common uses of !nonnull to be able vote either way.
While at it, updating LangRef to be more explicit about this case would be very much appreciated :)

fhahn updated this revision to Diff 149944.Jun 5 2018, 4:49 AM

Rebased after Local.h got moved. I've also added additional details to the comment for combineMetadataForCSE and added a few more CHECK-NOT lines to the negative tests.

fhahn added inline comments.Jun 5 2018, 4:50 AM
lib/Transforms/Utils/Local.cpp
2330

I've tweaked the comment, does it make sense now? Thanks Eli for updating the LangRef in D47747

fhahn added a comment.Jul 18 2018, 9:06 AM

ping. The langref now says the following about !nonnull loads: The existence of the !nonnull metadata on the instruction tells the optimizer that the value loaded is known to never be null. If the value is null at runtime, the behavior is undefined.. With the value being null at runetime being UB, keeping nonnull on dominating loads should be ok IIUC.

Given that it's UB to violate nonnull metadata, the metadata on J doesn't actually matter; the important question is whether K moves. If it does, we have to strip the nonnull metadata; it it doesn't, we don't. So "KDominatesJ" shouldn't exist, as far as I can tell; the boolean should just be "DoesKMove".

fhahn updated this revision to Diff 156287.Jul 19 2018, 9:30 AM
fhahn retitled this revision from [Local] Make KDominatesJ required for combineMetadata. to [Local] Make DoesKMove required for combineMetadata..
fhahn edited the summary of this revision. (Show Details)

Given that it's UB to violate nonnull metadata, the metadata on J doesn't actually matter; the important question is whether K moves. If it does, we have to strip the nonnull metadata; it it doesn't, we don't. So "KDominatesJ" shouldn't exist, as far as I can tell; the boolean should just be "DoesKMove".

Hm I realize "KDominatesJ" is not too clear, as we could hoist an instruction before running combineMetadata. It was meant to mean "in the original IR, K dominated J", so before any moving/hoisting. "DoesKMove" sounds slightly clearer. D47339 only uses the fact to not drop K's metadata if K does not move, as this enables keeping nonnull in more valid cases.

If combineMetadata is used to combine the metadata from l1 and l2 (which would preserve !nonnull, as both loads have it) and l1 gets hoisted, that would be illegal IIUC. However it looks like when we do hoisting, we create a new load without metadata, so this should not be a problem in existing code. Also it allows sinking a load and preserving the nonnull metadata, if there are loads in all predecessors and they all have nonnull.

  br i1 %x, label %bb2, label %bb2

bb1:
  ....
  %l1 = load .... !nonnull !0
  ....

bb2:
  ...
  %l2 = load .... !nonnull !0

What do you think?

Also it allows sinking a load and preserving the nonnull metadata, if there are loads in all predecessors and they all have nonnull.

I would prefer to handle that specific case in some different way; it's not the same sort of reasoning. In the CSE case, it doesn't matter whether J has nonnull metadata.

fhahn added a comment.Jul 19 2018, 3:52 PM

Also it allows sinking a load and preserving the nonnull metadata, if there are loads in all predecessors and they all have nonnull.

I would prefer to handle that specific case in some different way; it's not the same sort of reasoning. In the CSE case, it doesn't matter whether J has nonnull metadata.

Sounds good. Would it be OK to make combineMetadata stricter in that respect for the relevant metadata kinds in a follow up commit? Doing it step-by-step seems slightly easier to me, but I could also fold it into this or the previous patch if you think that's better.

Doing it in steps is fine, sure.

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

Update to account for DoesKMove.

fhahn added a comment.Aug 13 2018, 9:43 AM

Ping. Once that's in, I'll prepare a patch to handle the the CSE case outside of combineMetadata

I think this is fine, but I would be happier if Eli can take a look, as I'm not particularly familiar with this.

This revision is now accepted and ready to land.Aug 23 2018, 2:54 PM
This revision was automatically updated to reflect the committed changes.