[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

3732

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

3747

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

3747

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

3747

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

3747

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

3747

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:
 
+.. _welldefinedvalues:
+
+Well-Defined Values
+-------------------
+
+Given a program execution, a value is *well defined* if the value does not
+have an undef bit and is not poison in the execution.
+An aggregate value or vector is well defined if its elements are well defined.
+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.
+
+A constant of a :ref:`single value <t_single_value>`, non-vector type is well
+defined if it is a non-undef constant. Note that there is no poison constant
+in LLVM.
+The result of :ref:`freeze instruction <i_freeze>` is well defined regardless
+of its operand.
+
 .. _blockaddress:
 
 Addresses of Basic Blocks
 -------------------------
 
 ``blockaddress(@function, %block)``
 
 The '``blockaddress``' constant computes the address of the specified

 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
 padding from the loaded aggregate value.
 
+If the pointer is not a well-defined value, all of its possible representations
+should be dereferenceable. For example, loading a byte from a pointer to an
+array of type ``[16 x i8]`` with offset ``undef & 31`` is undefined behavior.
+Loading a byte at offset ``undef & 15`` nondeterministically reads one of the
+bytes.
+
 Examples:
 """""""""
 
 .. code-block:: llvm
 
       %ptr = alloca i32                               ; yields i32*:ptr
       store i32 3, i32* %ptr                          ; yields void
       %val = load i32, i32* %ptr                      ; yields i32:val = i32 3

 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>`.
 
+If ``<pointer>`` is not a well-defined value, all of its possible
+representations should be dereferenceable. For example, storing a byte to a
+pointer to an array of type ``[16 x i8]`` with offset ``undef & 31`` is
+undefined behavior. Storing a byte to an offset ``undef & 15``
+nondeterministically stores to one of offsets from 0 to 15.
+
 Example:
 """"""""
 
 .. code-block:: llvm
 
       %ptr = alloca i32                               ; yields i32*:ptr
       store i32 3, i32* %ptr                          ; yields void
       %val = load i32, i32* %ptr                      ; yields i32:val = i32 3

 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.
 
 If "len" is 0, the pointers may be NULL, dangling, ``undef``, or ``poison``
 pointers. However, they must still be appropriately aligned.
+If "len" isn't a well-defined value, all of its possible representations should
+make the behavior of this ``llvm.memcpy`` defined, otherwise the behavior is
+undefined.
 
 .. _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.
 
 If "len" is 0, the pointers may be NULL, dangling, ``undef``, or ``poison``
 pointers. However, they must still be appropriately aligned.
+If "len" isn't a well-defined value, all of its possible representations should
+make the behavior of this ``llvm.memmove`` defined, otherwise the behavior is
+undefined.
 
 .. _int_memset:
 
 '``llvm.memset.*``' Intrinsics
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""

 
 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.
 
 If "len" is 0, the pointer may be NULL, dangling, ``undef``, or ``poison``
 pointer. However, it must still be appropriately aligned.
+If "len" isn't a well-defined value, all of its possible representations should
+make the behavior of this ``llvm.memset`` defined, otherwise the behavior is
+undefined.
 
 '``llvm.sqrt.*``' Intrinsic
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 
 This is an overloaded intrinsic. You can use ``llvm.sqrt`` on any