Clang adds "noundef" annotation to char arguments

[RalfJung]

I think the way clang translates the following C code to LLVM IR is incorrect:

char id(char c) {
    return c;
}

void my_memcpy(char *src, char *dst, int n) {
    for (int i = 0; i < n; i++) {
        dst[i] = id(src[i]);
    }
}

The resulting IR defines id as @id(i8 noundef signext %0). The noundef is what I am concerned by. This translation means calling my_memcpy as follows leads to UB, since some of the bytes being copied here are undef or poison (namely, they are padding):

struct S {
    uint8_t f1;
    uint16_t f2;
};

void testcase() {
    struct S s, s_copy;
    s.f1 = 0;
    s.f2 = 0;
    my_memcpy((char*)&s, (char*)&s_copy, sizeof(struct S));
}

If I understand the C standard correctly, this program (running testcase) is entirely well-defined. In particular, C17 6.2.6.1 §5 says (emphasis mine)

Certain object representations need not represent a value of the object type. If the stored value of an object has such a representation and is read by an lvalue expression that does not have character type, the behavior is undefined.

But we are using a character type here. The standard also explicitly says in 6.2.6.2 that char types have no padding bits. So I don't think there is any room here for UB to arise when copying arbitrary data (including uninitialized memory) at char type. Therefore clang should not add noundef to character type variables.

Furthermore, I am not entirely sure what the status of this proposal is, but if it has been accepted, then I am not sure that adding noundef to any other integer type is correct, either. That proposal states explicitly

None of the integral types have extraordinary values.

And at least for C++, https://eel.is/c++draft/basic.fundamental#4 has a note on padding in integer types stating

Padding bits have unspecified value, but cannot cause traps.

So, at least for C++, I cannot see a justification for why clang adds noundef to all integer types. For non-character integer types in C, the standard is not clear enough for me to be sure either way.

Cc @aqjune @nunoplopes

[llvmbot]

@llvm/issue-subscribers-clang-codegen

[nikic]

For C++ the justification is given by https://eel.is/c++draft/basic.indet. It's very clear about anything but unsigned char/std::byte being UB, and indeterminate unsigned char is only not UB for the specific set of operations listed, which notably does not include argument passing / returning.

At least as far as C++ is concerned, the indeterminate value UB doesn't have anything to do with trap representations.

[RalfJung]

Oh I see, thanks for pointing that out. I have no idea how that can be true at the same time as the statements in basic.fundamental. The wonders of axiomatic specifications...

That would mean unsigned char / byte loads in C++ cannot be made noundef (once such a marker on load exists in the future), but noundef on arguments and return types indeed seems justified.

C doesn't have a clear enumeration like that to my knowledge, so it is less clear there. Documents like this make me think loading uninit data into a char is allowed (i.e., at least as much as C++ allows), and then I would usually think of course I can also pass them to another function, but clearly C++ doesn't satisfy that expectation...

[alercah]

My LLC/C++ is rusty, but I think that you're confusing indeterminate values and trap representations: a trap representation in C is an invalid but defined bit-pattern. C explicitly permits implementations to choose an integer representation such that you can have a trap representation that differs from a calid representation only by padding. C++ explicitly prohibits this, so you can safely write arbitrary bits to integer padding.

[RalfJung]

Those two notions are related though -- given the fuzziness of the standard, "type has no trap representation" is a hint indicating that it has no "strange" (indeterminate) values.

I didn't make this up, there are C committee discussions about indeterminate values that end up also discussing trap representations: https://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_260.htm, https://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_451.htm.

[alercah]

If I understand correctly, it's because the questions being asked about indeterminate values are ill-formed with respect to types with trap representations, because any read of an indeterminate value is UB for them (the compiler can just pick the result of the read to be the trap representation, and reading a trap representation is UB).

[RalfJung]

The question remains whether there's any way for the program above to have UB in C -- either in its form as given, or in the variant where id is inlined. (It seems like in C++, the inlined variant would be UB-free.) clang seems to say that the non-inlined version is UB, but I don't see what that is based on. The standard says (emphasis mine)

Certain object representations need not represent a value of the object type. If such a representation
is read by an lvalue expression that does not have character type, the behavior is undefined.

IOW, reading a non-value representation with an lvalue expression that has character type, like my example does, is well-defined. Therefore I think clang's noundef here is wrong.

[chorman0773]

FTR, in C also,

character types have ... no trap representations.

So an indeterminate value is just straight up an unspecified value for char. All character types lack any trap representation.

[aqjune]

Hi,

I wonder whether this story also implies that padding bits should not be undef.
Padding bits in C++ have unspecified value, and if I understand unspecified value correctly, doing any operation should not raise undefined behavior unless the operation was supposed to do so on a 'plain' (non-unspecified, non-trap) value.
However, using undef in LLVM violates this condition because conditional branching on undef is UB whereas any plain i1 value cannot cause br to raise UB.

If this reasoning is right, we can think about an alternate solution as well: initializing padding bits with zero, and keeping the noundef at i8 args. Actually this will not only fix the reported issue but also fix this incorrect lowering of padding bits to undef.

[RalfJung]

If this reasoning is right, we can think about an alternate solution as well: initializing padding bits with zero, and keeping the noundef at i8 args. Actually this will not only fix the reported issue but also fix this incorrect lowering of padding bits to undef.

I think that would still be wrong, since one should be able to copy uninitialized memory with char.

[aqjune]

In the general case, I think the arguments slightly diverge in C and C++, which is what this thread has been discussing as well.

For C:

• If there is no trap representation for non-char int types at all, it would mean that all uninitialized int variables will have unspecified values since indeterminate value is either unspecified value or trap repr. Since unspecified values are well-defined values, conceptually like freeze poison, having the noundef attributes at non-char int arguments will still hold because such value cannot appear from beginning. However, SROA should be fixed to lower load on an uninitialized int variable to some random, well-defined number rather than undef.
• If non-char int types do have trap representations, having noundef for non-char types can be justified by C17 6.2.6.1 §5. But, for the char type, I think this is still slightly complicated due to the following problem.

char c = *(char*)p; // p is, say, int32_t* storing an indeterminate value
// If the above statement succeeded, c must be unspecified value, because char type doesn't have trap representation.

Note that if c was passed to a function f(char):

f(c);

Having noundef at the argument of f will still work because c has a well-defined value.

However, another problem with this C standard semantics understanding is that supporting elimination of a redundant store-load operation using char buffer becomes hard:

char c = *(char*)p; // p is, say, int32_t* storing an indeterminate value
// If the above statement succeeded, c must be unspecified value, because char type doesn't have trap representation.
*(char*)p = c; // storing this back

This round-trip pair cannot be removed because after the removal the byte at p will be more undefined. Again, we need to disable this optimization I think (which is bad).

For C++:

• Having noundef for non-char int types are justified, as discussed above.
• Having noundef for char type <- I could not find a reasonable argument to keep this. :) Should we remove this..?