Add support for !noundef metatdata on loads

[aqjune]

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.

[jdoerfert]

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]

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.

[jdoerfert]

I created D89054 for discussion purposes.

[nikic]

In D89050#2319554, @jdoerfert wrote:

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).

[jdoerfert]

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.

[jdoerfert]

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]

In D89050#2320036, @jdoerfert wrote:

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.

[jdoerfert]

In D89050#2320052, @nikic wrote:

In D89050#2320036, @jdoerfert wrote:

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 ;)

[aqjune]

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.

[jdoerfert]

In D89050#2324427, @aqjune wrote:

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]

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.

[aqjune]

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.

[jdoerfert]

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]

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]

Update wording of LangRef

[aqjune]

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

[aqjune]

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

[jdoerfert]

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?)

[aqjune]

Rebase

[aqjune]

Remove .rej

[aqjune]

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 .

[malharJ]

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]

In D89050#3272418, @malharJ wrote:

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]

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]

In D89050#3272626, @malharJ wrote:

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.

[malharJ]

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.

[aqjune]

In D89050#3272837, @malharJ wrote:

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.

llvm/docs/LangRef.rst

 '``load``' Instruction
 ^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 
 ::
 
       <result> = load [volatile] <ty>, <ty>* <pointer>[, align <alignment>][, !nontemporal !<nontemp_node>][, !invariant.load !<empty_node>][, !invariant.group !<empty_node>][, !nonnull !<empty_node>][, !dereferenceable !<deref_bytes_node>][, !dereferenceable_or_null !<deref_bytes_node>][, !align !<align_node>][, !noundef !<empty_node>]
       <result> = load atomic [volatile] <ty>, <ty>* <pointer> [syncscope("<target-scope>")] <ordering>, align <alignment> [, !invariant.group !<empty_node>]
       !<nontemp_node> = !{ i32 1 }
       !<empty_node> = !{}
       !<deref_bytes_node> = !{ i64 <dereferenceable_bytes> }
       !<align_node> = !{ i64 <value_alignment> }
 
 Overview:
 """""""""
 
 The '``load``' instruction is used to read from memory.
 
 Arguments:
 """"""""""

 ``<align_node>`` corresponding to a metadata node with one ``i64`` entry.
 The existence of the ``!align`` metadata on the instruction tells the
 optimizer that the value loaded is known to be aligned to a boundary specified
 by the integer value in the metadata node. The alignment must be a power of 2.
 This is analogous to the ''align'' attribute on parameters and return values.
 This metadata can only be applied to loads of a pointer type. If the returned
 value is not appropriately aligned at runtime, the behavior is undefined.
 
+The optional ``!noundef`` metadata must reference a single metadata name
+``<empty_node>`` corresponding to a node with no entries. The existence of
+``!noundef`` metadata on the instruction tells the optimizer that the value
+loaded is known to be :ref:`well defined <welldefinedvalues>`.
+If the value isn't well defined, the behavior is undefined.
+
 Semantics:
 """"""""""
 
 The location of memory pointed to is loaded. If the value being loaded
 is of scalar type then the number of bytes read does not exceed the
 minimum number of bytes needed to hold all bits of the type. For
 example, loading an ``i24`` reads at most three bytes. When loading a
 value of a type like ``i20`` with a size that is not an integral number

llvm/include/llvm/IR/FixedMetadataKinds.def

 LLVM_FIXED_MD_KIND(MD_associated, "associated", 22)
 LLVM_FIXED_MD_KIND(MD_callees, "callees", 23)
 LLVM_FIXED_MD_KIND(MD_irr_loop, "irr_loop", 24)
 LLVM_FIXED_MD_KIND(MD_access_group, "llvm.access.group", 25)
 LLVM_FIXED_MD_KIND(MD_callback, "callback", 26)
 LLVM_FIXED_MD_KIND(MD_preserve_access_index, "llvm.preserve.access.index", 27)
 LLVM_FIXED_MD_KIND(MD_misexpect, "misexpect", 28)
 LLVM_FIXED_MD_KIND(MD_vcall_visibility, "vcall_visibility", 29)
+LLVM_FIXED_MD_KIND(MD_noundef, "noundef", 30)
 No newline at end of file

llvm/lib/Analysis/ValueTracking.cpp

if (const auto *PN = dyn_cast<PHINode>(V)) {
         }
       }
       if (IsWellDefined)
         return true;
     } else if (!canCreateUndefOrPoison(Opr) && all_of(Opr->operands(), OpCheck))
       return true;
   }
 
+  if (auto *I = dyn_cast<LoadInst>(V))
+    if (I->getMetadata(LLVMContext::MD_noundef))
+      return true;
+
   if (programUndefinedIfUndefOrPoison(V, PoisonOnly))
     return true;
 
   // CxtI may be null or a cloned instruction.
   if (!CtxI || !CtxI->getParent() || !DT)
     return false;
 
   auto *DNode = DT->getNode(CtxI->getParent());

llvm/lib/Transforms/InstCombine/InstCombineLoadStoreAlloca.cpp

for (const auto &MDPair : MD) {
     case LLVMContext::MD_nontemporal:
     case LLVMContext::MD_mem_parallel_loop_access:
     case LLVMContext::MD_access_group:
       // All of these directly apply.
       NewStore->setMetadata(ID, N);
       break;
     case LLVMContext::MD_invariant_load:
     case LLVMContext::MD_nonnull:
+    case LLVMContext::MD_noundef:
     case LLVMContext::MD_range:
     case LLVMContext::MD_align:
     case LLVMContext::MD_dereferenceable:
     case LLVMContext::MD_dereferenceable_or_null:
       // These don't apply for stores.
       break;
     }
   }

llvm/test/Transforms/InstSimplify/freeze-noundef.ll

 ; CHECK-NEXT:    call void @use_i1(i1 [[Y]])
 ; CHECK-NEXT:    ret i1 [[Y]]
 ;
   %y = add nsw i1 %x, 1
   call void @use_i1(i1 %y)
   %f = freeze i1 %y
   ret i1 %f
 }
+
+define i32 @noundef_metadata(i32* %p) {
+; CHECK-LABEL: @noundef_metadata(
+; CHECK-NEXT:    [[V:%.*]] = load i32, i32* [[P:%.*]], align 4, !noundef !0
+; CHECK-NEXT:    ret i32 [[V]]
+;
+  %v = load i32, i32* %p, !noundef !{}
+  %v.fr = freeze i32 %v
+  ret i32 %v.fr
+}
+
+define {i8, i32} @noundef_metadata2({i8, i32}* %p) {
+; CHECK-LABEL: @noundef_metadata2(
+; CHECK-NEXT:    [[V:%.*]] = load { i8, i32 }, { i8, i32 }* [[P:%.*]], align 4, !noundef !0
+; CHECK-NEXT:    ret { i8, i32 } [[V]]
+;
+  %v = load {i8, i32}, {i8, i32}* %p, !noundef !{}
+  %v.fr = freeze {i8, i32} %v
+  ret {i8, i32} %v.fr
+}