This is an archive of the discontinued LLVM Phabricator instance.

Add support for !noundef metatdata on loads
ClosedPublic

Authored by aqjune on Oct 8 2020, 8:40 AM.

Details

Summary

This patch adds metadata !noundef and makes load instructions can optionally have it.
A load with !noundef always return a well-defined value (has no undef bit or isn't poison).
If the loaded value isn't well defined, the behavior is undefined.

This metadata can be used to encode the assumption from C/C++ that certain reads of variables should have well-defined values.
It is helpful for optimizing freeze instructions away, because freeze can be removed when its operand has well-defined value, and showing that a load from arbitrary location is well-defined is usually hard otherwise.

The same information can be encoded with llvm.assume with operand bundle; using metadata is chosen because I wasn't sure whether code motion can be freely done when llvm.assume is inserted from clang instead.
The existing codebase already is stripping unknown metadata when doing code motion, so using metadata is UB-safe as well.

Diff Detail

Event Timeline

aqjune created this revision.Oct 8 2020, 8:40 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 8 2020, 8:40 AM
aqjune requested review of this revision.Oct 8 2020, 8:40 AM

While this is certainly in line with the prior art, I would like to revisit the trade-offs of metadata on loads vs assume. While we need to make assume side-effect free (but potentially UB so we keep control dependences), it would allow us to reduce the number of encodings. Let's say you promote a load with noundef, you might introduce an "assume nodundef" for the promoted value anyway. That begs the question why not use assume anyway. (FWIW, when metadata was introduced for these things assume did not allow non-boolean properties.)

I'd be interested what others think :)

aqjune added a comment.Oct 8 2020, 9:16 AM

Oops, just saw the reply after sending the mail to llvm-dev.
Yes, I agree that llvm.assume can encode the noundef information more precisely and it's a benefit. I'm also happy to hear other's opinions.

I created D89054 for discussion purposes.

nikic added a comment.Oct 8 2020, 10:01 AM

While this is certainly in line with the prior art, I would like to revisit the trade-offs of metadata on loads vs assume. While we need to make assume side-effect free (but potentially UB so we keep control dependences), it would allow us to reduce the number of encodings. Let's say you promote a load with noundef, you might introduce an "assume nodundef" for the promoted value anyway. That begs the question why not use assume anyway. (FWIW, when metadata was introduced for these things assume did not allow non-boolean properties.)

For some frontends (that model safe languages) it might be that *all* loads are noundef. While the work on assume bundles has improved the interaction of assumes with other optimizations, I think there are sufficient remaining issues that this kind of mass usage would probably result in regressions, especially as the optimization benefit of this metadata is currently rather minor. Additionally the sheer quantity of necessary assumes would likely have a non-trivial adverse effect on compile-time. If your original IR had 15% loads, and now you add one extra assume for every load, that will be a significant increase in instructions (not that metadata is completely free either).

15% loads, and now you add one extra assume for every load, that will be a significant increase in instructions (not that metadata is completely free either).

llvm.assume(i1 true) ["noundef"(%a), "noundef"(%b)] works right now just fine, we even merge assumes already with a pass in-tree (IIRC, @Tyker). The operand bundles could/should also take more operands to make it even simpler.

That said, I think @nikic is right that there is a trade off we have to consider and actually measure. I don't know what is best. What I know is that I would like us to employ assume aggressively to "retain knowledge". That will mean we have to deal with many llvm.assumes either way and I'd much rather have one encoding and smarts to deal with it than multiple ones.

For some frontends (that model safe languages) it might be that *all* loads are noundef.

I would consider a function/module attribute for this.

nikic added a comment.Oct 8 2020, 1:06 PM

For some frontends (that model safe languages) it might be that *all* loads are noundef.

I would consider a function/module attribute for this.

Only loads emitted by the frontend would be noundef, optimization may introduce or move loads in a way that they are no longer noundef. I think such an attribute would violate LLVMs usual attribute design, as optimizations would now have to worry about dropping function attributes when performing speculation etc (is there any precedent for something like this?) We'd also lose the noundef property for all loads in a function at once, if a single one of them is speculated.

For some frontends (that model safe languages) it might be that *all* loads are noundef.

I would consider a function/module attribute for this.

Only loads emitted by the frontend would be noundef, optimization may introduce or move loads in a way that they are no longer noundef. I think such an attribute would violate LLVMs usual attribute design, as optimizations would now have to worry about dropping function attributes when performing speculation etc (is there any precedent for something like this?) We'd also lose the noundef property for all loads in a function at once, if a single one of them is speculated.

Yeah, good point ;). Bundling noundef in a single assume still works though ;)

I made D89219 that updates relevant functions to exploit llvm.assume's noundef operand bundle.

BTW, given v = op; call llvm.assume()["noundef"(v)], if we want to move v across the assume call, the call should be appropriately moved with v. I wonder whether there is a handy way to do this, since things get complicated when the assume has several operand bundles that are not using v.

What about leaving call llvm.assume whenever the load !noundef is moved to somewhere else? I guess this is what LLVM is doing as well.

!noundef is a syntactic sugar of llvm.assume()["noundef"(..)], but seems helpful for the brevity and size of the bitcode.

uenoku added a subscriber: uenoku.Oct 12 2020, 7:25 AM

I made D89219 that updates relevant functions to exploit llvm.assume's noundef operand bundle.

Thx!

BTW, given v = op; call llvm.assume()["noundef"(v)], if we want to move v across the assume call, the call should be appropriately moved with v. I wonder whether there is a handy way to do this, since things get complicated when the assume has several operand bundles that are not using v.

Operand bundles are unknown uses. You should not be able to break things. Hoisting v does and should not impact the operand bundles. If you want to sink v you need to know about "droppable uses" and "drop them", SROA knows about them nowadays for example.

What about leaving call llvm.assume whenever the load !noundef is moved to somewhere else? I guess this is what LLVM is doing as well.

If --enable-knowledge-retention is set, we should certainly do that if we would otherwise strip the metadata (not only for noundef).

!noundef is a syntactic sugar of llvm.assume()["noundef"(..)], but seems helpful for the brevity and size of the bitcode.

I agree, especially if there is no llvm.assume available in the context to attach the information. If there is, I doubt there is overhead. My idea for the future is that we will have enough llvm.assumes such that this would not be a problem, though I won't block the metadata because of this. (Maybe it was wrong to start the discussion in this review then)

Tyker added a comment.Oct 12 2020, 1:41 PM

What about leaving call llvm.assume whenever the load !noundef is moved to somewhere else? I guess this is what LLVM is doing as well.

If --enable-knowledge-retention is set, we should certainly do that if we would otherwise strip the metadata (not only for noundef).

this is not implemented the assume building currently don't look at any metadata.

Sorry for my change in stance.
May I proceed with this patch?

If --enable-knowledge-retention is set, we should certainly do that if we would otherwise strip the metadata (not only for noundef).

Yes, I think so because metadata is still common.

OK, let's go with this for now. All looks good but I don't get one thing, see below.

llvm/docs/LangRef.rst
9279

Why do we need index? and what is index?

aqjune added inline comments.Oct 15 2020, 4:10 PM
llvm/docs/LangRef.rst
9279

An index is the name of the metadata node, and it is used as a placeholder that represents the existence of !noundef key. This is analogous to what !nonnull does.

define void @f() {
  %v = load i32, i32* [[P:%.*]], align 4, !noundef !0
}
!0 = !{}

To be precise, the first sentence should end with '... {} or a single metadata name <index> ...'. I'll update this sentence as well as !nonnull's sentence.


About the verbosity of this empty metadata node:
The empty node is necessary because metadata is stored as a key-value store (MDAttachmentMap).
This makes textual representation slightly more verbose compared to attaching !noundef without value. To remove these, two workarounds are here:

  1. When parsing metadata attached to instructions, if there is no value, automatically add empty node
  2. Add a special state 'has a key but not value' to MDAttachmentMap's each slot

The first approach causes a discrepancy between IR and bitcode. The second one might be a more viable option, but it breaks invariants that currently holds (e.g., MDAttachmentMap::getAll's returned values are all valid metadata)

aqjune updated this revision to Diff 298513.Oct 15 2020, 4:29 PM

Update wording of LangRef

aqjune updated this revision to Diff 298518.Oct 15 2020, 4:43 PM

Undo unnecessary changes

Use 'metadata node' instead of 'metadata name', because metadata node's contents can be written in place
e.g., load %ptr, !range !{i32 0, i32 3}

Use <empty_node> instead of <index> for nonnull/invariant.start/etc

Seems like the word index isn't conveying helpful information, so I renamed it into empty_node

jdoerfert accepted this revision.Oct 16 2020, 7:27 AM

LGTM. Would be best to split it now. Also one nit below.

llvm/docs/LangRef.rst
9184

The rewrite could be commited as NFC cleanup first. That part really makes things better :)

9278

reference to well defined (IIRC we have a section, right?)

This revision is now accepted and ready to land.Oct 16 2020, 7:27 AM
aqjune updated this revision to Diff 298802.Oct 16 2020, 9:45 PM

Remove .rej

This revision was landed with ongoing or failed builds.Oct 16 2020, 9:50 PM
This revision was automatically updated to reflect the committed changes.
aqjune marked an inline comment as done.Oct 16 2020, 9:57 PM

Changes in LangRef other than the name rewrite didn't seem very critical, so undid them.

Thanks!

llvm/docs/LangRef.rst
9179

The last !noundef !<empty_node> was accidentally added by 701cf4b5a59c .

Hi everyone,

If you would be so kind as to help me out here,
I'm interested in knowing if it's possible to write C/C++ code in a way that can translate to a load with !noundef metadata ?

(Background:

I came across this patch while debugging an optimization (specifically the select ---> and/or folding) in InstCombine ...
I am trying to enable that transform and one of the ways I was attempting it was to ensure that the operands of the select instruction
are well-defined values.

In my case the C/C++ code has array accesses so it translates to loads in the IR, and currently these loads do not have this !noundef metadata
attached to it so the loaded values can potentially be undef/poison values.

so I am trying to find a way if something in C/C++ code can be written in a way so as to generate loads with this metadata)

nikic added a comment.Jan 26 2022, 6:58 AM

Hi everyone,

If you would be so kind as to help me out here,
I'm interested in knowing if it's possible to write C/C++ code in a way that can translate to a load with !noundef metadata ?

(Background:

I came across this patch while debugging an optimization (specifically the select ---> and/or folding) in InstCombine ...
I am trying to enable that transform and one of the ways I was attempting it was to ensure that the operands of the select instruction
are well-defined values.

In my case the C/C++ code has array accesses so it translates to loads in the IR, and currently these loads do not have this !noundef metadata
attached to it so the loaded values can potentially be undef/poison values.

so I am trying to find a way if something in C/C++ code can be written in a way so as to generate loads with this metadata)

I think most loads in C/C++ can be annotated with !noundef based on language semantics, but I don't think anyone has looked into the necessary clang frontend work yet. noundef on arguments/returns was enabled only very recently.

You might want to file an issue for the missing transform you encountered. There's a chance that we can address it in a different way that does not require noundef.

malharJ added a comment.EditedJan 26 2022, 8:07 AM

I think most loads in C/C++ can be annotated with !noundef based on language semantics, but I don't think anyone has looked into the necessary clang frontend work yet

Thanks for clarifying this.

You might want to file an issue for the missing transform you encountered

When you say missing transform, are you referring to C/C++ array access ---> IR load !noundef transform ?

(If you are referring to the select --> and/or folding, it is not exactly missing,
rather it was disabled if the transformation was poison-unsafe (which is why
I am trying to see if I can get the IR to generate well-defined loads.
Since those loaded values are inputs to the select in my particular case.)

Below were the patches.
https://reviews.llvm.org/D99674
https://reviews.llvm.org/D101191
)

nikic added a comment.Jan 26 2022, 8:27 AM

You might want to file an issue for the missing transform you encountered

When you say missing transform, are you referring to C/C++ array access to LLVM IR load transform ?

(If you are referring to the select --> and/or folding, it is not exactly missing,
rather it was disabled if the transformation was poison-unsafe (which is why
I am trying to see if I can get the IR to generate well-defined loads.
Since those loaded values are inputs to the select in my particular case.)

Below were the patches.
https://reviews.llvm.org/D99674
https://reviews.llvm.org/D101191
)

Right, but the absence of select -> and/or folding by itself shouldn't matter -- it's only relevant in that it can prevent other transforms. We tried to make sure that everything handles the select form as far as possible, but we may have missed something, which is why I'm asking.

Right, but the absence of select -> and/or folding by itself shouldn't matter -- it's only relevant in that it can prevent other transforms

I fully agree, it's just that the presence of that transformation was helping with an optimization later on in the pipeline
in my specific case.

Otherwise there is no issue with code generation of select.

Right, but the absence of select -> and/or folding by itself shouldn't matter -- it's only relevant in that it can prevent other transforms

I fully agree, it's just that the presence of that transformation was helping with an optimization later on in the pipeline
in my specific case.

Otherwise there is no issue with code generation of select.

Hi @malharJ,
The clang change (!noundef) makes sense to me, unless the load type is unsigned char. The unsigned char case is slightly complicated.

If the other optimization which was blocked by the disabled select->and/or present in the current LLVM mainstream, could you share the optimization? I am willing to look into it.