65

Consider the following code:

bool AllZeroes(const char buf[4])
{
    return buf[0] == 0 &&
           buf[1] == 0 &&
           buf[2] == 0 &&
           buf[3] == 0;
}

Output assembly from Clang 13 with -O3:

AllZeroes(char const*):                        # @AllZeroes(char const*)
        cmp     byte ptr [rdi], 0
        je      .LBB0_2
        xor     eax, eax
        ret
.LBB0_2:
        cmp     byte ptr [rdi + 1], 0
        je      .LBB0_4
        xor     eax, eax
        ret
.LBB0_4:
        cmp     byte ptr [rdi + 2], 0
        je      .LBB0_6
        xor     eax, eax
        ret
.LBB0_6:
        cmp     byte ptr [rdi + 3], 0
        sete    al
        ret

Each byte is compared individually, but it could've been optimized into a single 32-bit int comparison:

bool AllZeroes(const char buf[4])
{
    return *(int*)buf == 0;
}

Resulting in:

AllZeroes2(char const*):                      # @AllZeroes2(char const*)
        cmp     dword ptr [rdi], 0
        sete    al
        ret

I've also checked GCC and MSVC, and neither of them does this optimization. Is this disallowed by the C++ specification?

Edit: Changing the short-circuited AND (&&) to bitwise AND (&) will generate the optimized code. Also, changing the order the bytes are compared doesn't affect the code gen: https://godbolt.org/z/Y7TcG93sP

24
  • 3
    Could this have to do with alignment?
    – Quentin
    Nov 25, 2021 at 11:49
  • 59
    Because the compiler does not know the size of the array and && is short-circuit evaluation. The array indexes greater than 0 may only be valid if buf[0] == 0 is true. Evaluating buf[1] == 0 && may be UB if the first test is false Nov 25, 2021 at 11:51
  • 5
    @dave no, the array size in a function parameter is only a comment for the developer. const char buf[4] is exactly the same as const char *buf as function parameter.
    – mch
    Nov 25, 2021 at 11:55
  • 4
    @RichardCritten That makes sense, changing && to bitwise AND will generate the optimized code. I've also tried comparing the 3rd byte first but again, no luck: godbolt.org/z/Y7TcG93sP
    – user17507206
    Nov 25, 2021 at 11:59
  • 5
    return *(int*)buf == 0; is technically UB unless the passed in buf really does point at a int. Casting any pointer to char * and dereferencing is OK but casting char * to int * and dereferencing is only ok if the char * was originally pointing to an int. [note: all the consts removed for clarity] Nov 25, 2021 at 17:26

3 Answers 3

73

If buf[0] is nonzero, the code will not access buf[1]. So the function should return false without checking the other buf elements. If buf is close to the end of the last memory page, buf[1] may trigger an access fault. The compiler should be very careful to not read stuff which may be forbidden to read.

18
  • 4
    That's a good reason for the example in question. Furthermore, even if there is no access fault, there could be arbitrary memory in the accessible memory as well. However, the compiler appears to not optimise even when the size of the array is known: godbolt.org/z/ch41zd5Wc (edit: also added alignment to see if that helps; it does not)
    – eerorika
    Nov 25, 2021 at 12:06
  • 4
    A very clever compiler might (in principle) clone the function when buf is word aligned, e.g. with whole program optimization Nov 25, 2021 at 12:06
  • 2
    @eerorika godbolt.org/z/dfnhhx7oG Nov 25, 2021 at 13:50
  • 2
    @eerorika since the array in your compiler-explorer example isn't initialized and the called function may not initialize all elements, accessing may result in UB so the && short circuit can't be short circuited by a single read without possible UB
    – doug
    Nov 25, 2021 at 18:19
  • 8
    @doug: x86 has no trap representations for integers, so no, compilers don't need to avoid doing things in asm for the specific target just because they would be UB in portable C++, as long as the as-if rule is satisfied for all cases where the C++ abstract machine doesn't encounter UB. Speculative reads are allowed if they're from locations that definitely can't fault (on targets without hardware race detection, i.e. normal CPUs). pretend_modify could have passed the address to another thread which is currently writing the last byte, no UB unless the first 3 are zero. Nov 26, 2021 at 2:50
25

The first thing to understand is that f(const char buf[4]) does not guarantee that the pointer points to 4 elements, it means exactly the same as const char *buf, the 4 is completely ignored by the language. (C99 has a solution to this, but it's not supported in C++, more on that below)

Given AllZeroes(memset(malloc(1),~0,1)), the implementation

bool AllZeroes(const char buf[4])
{
    return buf[0] == 0 &&
           buf[1] == 0 &&
           buf[2] == 0 &&
           buf[3] == 0;
}

should work, because it never tries to read byte #2 (which doesn't exist) when it notices that byte #1 is non-zero, while the implementation

bool AllZeroes(const int32_t *buf)
{
    return (*buf == 0);
}

should segfault as it tries to read the first 4 bytes while only 1 byte exists (malloced 1 byte only)

FWIW Clang gets it right (and GCC doesn't) in C99 with the implementation

_Bool AllZeroes(const char buf[static 4])
{
    return buf[0] == 0 &
           buf[1] == 0 &
           buf[2] == 0 &
           buf[3] == 0;
}

which compiles to the same as

_Bool AllZeroes(const int32_t *buf)
{
    return (*buf == 0);
}

see https://godbolt.org/z/Grqs3En3K (thanks to Caze @libera #C for finding that)

  • unfortunately buf[static 4], which in C99 is a guarantee-from-the-programmer-to-the-compiler that the pointer points to minimum 4 elements, is not supported in C++
8
  • 6
    Generally agree with this answer, but "should segfault" really isn't a thing. Malloc doesn't make any gaurantees about the addresses outside of the allocation it doesn't gaurantee they are accessible but it doesn't gaurantee they are inaccessible either.
    – plugwash
    Nov 26, 2021 at 21:44
  • 4
    const std::array<char, 4> *buf - pretty sure that accessing any member of a class object implies that an entire object of that class type is present and fully accessible, even if the only member is an array. e.g. that it would be UB to pass a pointer to the last byte of a page as such an arg. (Another thread might be writing one of the members, but that's fine in asm). Allocating memory for a part of structure is about C, not C++. I think there was a C++ Q&A about this at some point in the past year or two, but I didn't find it with some searching. Nov 27, 2021 at 3:16
  • @PeterCordes yeah i'm pretty sure you're right, i removed the std::array section, thanks
    – hanshenrik
    Nov 27, 2021 at 7:00
  • 2
    I thought that section was actually pretty relevant. It's strict-aliasing UB to point a std::array<char,4> pointer at an object that isn't a std::array (although it probably works in practice), but re-designing the function to take a const std::array by pointer or reference instead of a raw const char* is something one might want to do, showing one indirect advantage of using container classes instead of C-style arrays. It's C++'s answer to [static 4]. (In this case it's small enough that even taking it by value might be even better; having the 4 bytes in one register arg is perfect) Nov 27, 2021 at 7:17
  • 3
    What if instead of the aliasing cast to std::array<char, 4>* you used an input of type std::span<char, 4>? According to cppreference.com it's UB to try to construct a span of static positive extent pointing to an invalid range; so technically, I guess a compiler could coalesce accesses to such a span. (Though as far as I know, there would have to be compiler-specific annotations of some kind in the standard library headers to be able to implement such an optimization -- or make std::span alias or wrap a built-in type, etc.) Nov 27, 2021 at 18:00
14

There's the short-circuit evaluation thing. So it can't be optimized as you think. If buf[0] == 0 is false buf[1] == 0 must not be checked. It can be UB or something forbidden to use or whatever - this all must still work.

https://en.wikipedia.org/wiki/Short-circuit_evaluation

3
  • 5
    Re: "it can be ub": Undefined behavior is a property of C++ code, not a property of compiler-generated assembly code. It's 100% fine for a C++ compiler to perform an optimization that would be "undefined behavior" if you wrote it in C++, as long as the compiler knows that the generated assembly will be safe on the systems that the generated code supports.
    – ruakh
    Nov 26, 2021 at 6:43
  • 2
    @ruakh: Right, it's not ISO C abstract-machine UB that's the problem, it's stuff that might fault on actual x86. In this case, it's unmapped pages. Without an alignment guarantee on the pointer, arr[3] could be in the next page, which might be unmapped. It's legal (no C UB) to pass this function a pointer to the last byte of a a page, if the byte is non-zero. (It's the strlen problem in reverse: vectorized strlen getting away with reading unallocated memory and this) Nov 26, 2021 at 11:12
  • 2
    (In another comment thread, I pointed out that C data-race UB is specifically not a problem on x86, or other normal ISAs, because speculative reads are well defined as long as you don't care about the value.) Nov 26, 2021 at 11:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.