[LangRef] Clarify the behavior of memory access instructions when pointers/sizes aren't well-defined

[aqjune]

Summary

This is a patch to LangRef that clarifies the behavior of load/store/memset/memcpy/memmove when the pointers or sizes are not well-defined
as well.

MSan detects a case when e.g., only lower bits of address are garbage when -msan-check-access-address is enabled, and it does not directly conflict with this patch because a C program should not use a pointer with undef bits and reasonable optimizations do not convert a well-defined pointer into a pointer with undef bits.

This patch contains a definition of a well-defined value as well.

[aqjune]

Fix typo

[eugenis]

llvm/docs/LangRef.rst

3728

This is a definition of "well-defined" - make it bold and perhaps make sure it appears in the ToC. Searching through the document, this terms appears with different meaning in several places.

Otherwise LGTM

[jdoerfert]

I block this until the llvm-dev discussion concludes. From what I can tell, people there seam to suggest this is not the right approach.

[aqjune]

Update the contents to follow the conclusion of the discussion at llvm-dev.

I think the behavior of the sanitizer is still valid.
The logic couldn't be applied to IR because existing dereferenceability checking analyses accept pointers with undef bits.

Made the definition of a well-defined value clearer.
A definition of 'frozen value' is omitted because contexts of their current uses say the meaning straightforwardly.

Memset/memcpy/memmove's len are allowed to have undef bits as well.

[jdoerfert]

llvm/docs/LangRef.rst

3743

I'm not too happy with the word "never". It implies there can be change and I much rather talk about values with the implicit assumption that it is the dynamic value.

[aqjune]

Update the definition of a well-defined value to show that it is defined per a program execution

[jdoerfert]

llvm/docs/LangRef.rst

3743

A constant of a single value, non-vector type is well defined if it is a non-undef constant.

Do we need "single value" at all? When are aggregates different? If so, we need a different name.

The sentence about integer constants should then be removed from the first paragraph.

[aqjune]

llvm/docs/LangRef.rst

3743

It is a single value type that is not a vector type - I followed the categorization of a single value type described at LangRef. When it is an aggregate type, it follows the description in the first paragraph.

I think the sentence about integer constants in the first paragraph helps emphasize that a well-defined value is a dynamic concept, but not a strong opinion.

[jdoerfert]

llvm/docs/LangRef.rst

3743

Fair. can we link https://llvm.org/docs/LangRef.html#single-value-types ?

I don't see how separating integer constants makes it less confusing, or I don't understand the problem.
When I read it I asked myself why integer constants are different, or if they were not.

[aqjune]

Add a link, remove a sentence

[aqjune]

llvm/docs/LangRef.rst

3743

Since it can be interpreted as that an integer constant is special, simply removed it

[jdoerfert]

LGTM, I'm no MSAN expert and can't speak to the interaction, this makes sense to me and matches our llvm-dev discussion. Feel free to add the discussion link in the commit message too.

[eugenis]

MSan will complain about any undefined bits in a pointer.
We have not seen a false positive caused by this so far, but it sounds like we should relax the requirement. Does it make sense for MSan to allow undef in the lower bits up to the known dereferenceable range of the pointer?

[aqjune]

In D87994#2295457, @eugenis wrote:

MSan will complain about any undefined bits in a pointer.
We have not seen a false positive caused by this so far, but it sounds like we should relax the requirement. Does it make sense for MSan to allow undef in the lower bits up to the known dereferenceable range of the pointer?

I think it depends on whether the frontend languages support nondeterministic accesses.
Optimizations cannot introduce undef bits to the pointers in general, because it can change a program that deterministically accesses memory locations to a program that nondeterministically does it.
if it is illegal for the frontend languages (that MSan is targetting) to generate such pointers, I think the check is still valid.
Also, even if it is not UB, it might be still useful - D86000 detects behavior that isn't undefined but is practically problematic as well, so it might be okay.

[aqjune]

A link to the llvm-dev discussion: https://groups.google.com/g/llvm-dev/c/2Qk4fOHUoAE/m/KcvYMEgOAgAJ

llvm/docs/LangRef.rst

 doesn't actually *have a live range*. Instead, the value is logically
 read from arbitrary registers that happen to be around when needed, so
 the value is not necessarily consistent over time. In fact, ``%A`` and
 ``%C`` need to have the same semantics or the core LLVM "replace all
 uses with" concept would not hold.
 
 To ensure all uses of a given register observe the same value (even if
 '``undef``'), the :ref:`freeze instruction <i_freeze>` can be used.
-A value is frozen if its uses see the same value.
-An aggregate value or vector is frozen if its elements are frozen.
-The padding of an aggregate isn't considered, since it isn't visible
-without storing it into memory and loading it with a different type.
 
 .. code-block:: llvm
 
       %A = sdiv undef, %X
       %B = sdiv %X, undef
     Safe:
       %A = 0
     b: unreachable
entry:
       %poison3 = load i16, i16* %narrowaddr ; Returns a poison value.
       %poison4 = load i64, i64* %wideaddr   ; Returns a poison value.
 
       %cmp = icmp slt i32 %poison, 0       ; Returns a poison value.
       br i1 %cmp, label %end, label %end   ; undefined behavior
 
     end:
 
+A value is well-defined, or *frozen*, if the value never has undef bit
+and is never poison.
+If a variable has a frozen value, its uses should always see the same
+defined value.
+An aggregate value or vector is frozen if its elements are frozen.
+The padding of an aggregate isn't considered, since it isn't visible
+without storing it into memory and loading it with a different type.
+
 .. _blockaddress:
 
 Addresses of Basic Blocks
 -------------------------
 
 ``blockaddress(@function, %block)``
 
 The '``blockaddress``' constant computes the address of the specified
 basic block in the specified function, and always has an ``i8*`` type.
 Taking the address of the entry block is illegal.
 
 This value only has defined behavior when used as an operand to the
 ':ref:`indirectbr <i_indirectbr>`' or ':ref:`callbr <i_callbr>`'instruction, or
 for comparisons against null. Pointer equality tests between labels addresses
 results in undefined behavior --- though, again, comparison against null is ok,
 and no label is equal to the null pointer. This may be passed around as an

 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.
 
 Semantics:
 """"""""""
 
-The location of memory pointed to is loaded. If the value being loaded
+The location of memory pointed to is loaded.
+The pointer should be well-defined. For example, one cannot load a pointer
+to an array of type ``[16 x i8]`` with offset ``undef & 16``, even if
+``undef & 16`` is always less than 16. If the pointer isn't well-defined,
+the behavior is undefined.
+
+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
 of bytes, the result is undefined if the value was not originally
 written using a store of the same type.
 If the value being loaded is of aggregate type, the bytes that correspond to
 padding may be accessed but are ignored, because it is impossible to observe

 
 The optional ``!invariant.group`` metadata must reference a
 single metadata name ``<index>``. See ``invariant.group`` metadata.
 
 Semantics:
 """"""""""
 
 The contents of memory are updated to contain ``<value>`` at the
-location specified by the ``<pointer>`` operand. If ``<value>`` is
+location specified by the ``<pointer>`` operand.
+``<pointer>`` should be well-defined. For example, one cannot store a value to
+a pointer to an array of type ``[16 x i8]`` with offset ``undef & 16``, even if
+``undef & 16`` is always less than 16. If ``<pointer>`` isn't well-defined,
+the behavior is undefined.
+
+If ``<value>`` is
 of scalar type then the number of bytes written does not exceed the
 minimum number of bytes needed to hold all bits of the type. For
 example, storing an ``i24`` writes at most three bytes. When writing a
 value of a type like ``i20`` with a size that is not an integral number
 of bytes, it is unspecified what happens to the extra bits that do not
 belong to the type, but they will typically be overwritten.
 If ``<value>`` is of aggregate type, padding is filled with
 :ref:`undef <undefvalues>`.

 """"""""""
 
 The '``llvm.memcpy.*``' intrinsics copy a block of memory from the source
 location to the destination location, which must either be equal or
 non-overlapping. It copies "len" bytes of memory over. If the argument is known
 to be aligned to some boundary, this can be specified as an attribute on the
 argument.
 
+"len" should be well-defined, otherwise the behavior is undefined.
 If "len" is 0, the pointers may be NULL, dangling, ``undef``, or ``poison``
 pointers. However, they must still be appropriately aligned.
+If "len" is not 0, the pointers should be well-defined.
 
 .. _int_memcpy_inline:
 
 '``llvm.memcpy.inline``' Intrinsic
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""

 """"""""""
 
 The '``llvm.memmove.*``' intrinsics copy a block of memory from the
 source location to the destination location, which may overlap. It
 copies "len" bytes of memory over. If the argument is known to be
 aligned to some boundary, this can be specified as an attribute on
 the argument.
 
+"len" should be well-defined, otherwise the behavior is undefined.
 If "len" is 0, the pointers may be NULL, dangling, ``undef``, or ``poison``
 pointers. However, they must still be appropriately aligned.
+If "len" is not 0, the pointers should be well-defined.
 
 .. _int_memset:
 
 '``llvm.memset.*``' Intrinsics
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""

 Semantics:
 """"""""""
 
 The '``llvm.memset.*``' intrinsics fill "len" bytes of memory starting
 at the destination location. If the argument is known to be
 aligned to some boundary, this can be specified as an attribute on
 the argument.
 
+"len" should be well-defined, otherwise the behavior is undefined.
 If "len" is 0, the pointer may be NULL, dangling, ``undef``, or ``poison``
 pointer. However, it must still be appropriately aligned.
+If "len" is not 0, the pointer should be well-defined.
 
 '``llvm.sqrt.*``' Intrinsic
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 
 This is an overloaded intrinsic. You can use ``llvm.sqrt`` on any