5 ms·

> return sparse[i] < n && dense[sparse[i]] == i This line lives in fear of the optimizer. sparse[i] references uninitialized memory and is thus UB and coul

> return sparse[i] < n && dense[sparse[i]] == i This line lives in fear of the optimizer. sparse[i] references uninitialized memory and is thus UB and could be optimized out at a certain level. Also I think I read once that even if we’ll allow that sparse[i] stays in the program, there’s still no guarantee that each access of sparse[i] will read the same value since it’s still UB.

alexvitkov 3y ago
If you're running in some theoretical fairy dust C++ spec environment sure, but in reality sparse is just a pointer and the compiler can't know its value, or whether or not it's "initialized". Even if you construct a degenerate case: int* sparse = (int*)malloc(100 * sizeof(int)); int x = sparse[40]; // provably unitialized it still won't "optimize out" the access, since 1. it's insane. nobody would write such an optimization because there's no possible performance gain, and it changes program behavior 2. malloc is just a function, it's not treated in any special way 3. there's no guarentee this malloc is a per-spec malloc, it can be a user-defined function for which this is perfectly valid
- dwattttt 3y ago
  to address the points in order: 1. a specific optimisation pass won't do this, but the combination of several passes written with other intentions can 2 & 3. the C runtime a compiler links with is known to the compiler/linker, and it _does_ usually treat intrinsics like malloc specially A quick google reveals https://github.com/llvm/llvm-project/issues/52930 https://github.com/llvm/llvm-project/issues/52930, LLVM recognising uninitialised memory as 'undef', and needing to treat it as poisoned (IIRC propogation of undef can cause things like separate uses of the variable to not even unify to a single value) EDIT: duplicated link
- adwn 3y ago
  Well, you're 100% wrong: https://godbolt.org/z/en31xx9Yx https://godbolt.org/z/en31xx9Yx clang optimizes this function to a single ret, optimizing away not just the memory access, but the call to malloc() as well. I does this (and is allowed to do this) because it recognizes that sparse[40] accesses uninitialized memory, which is UB, and therefore anything goes – including replacing the entire function with a no-op.
  - pca006132 3y ago
    > and therefore anything goes – including replacing the entire function with a no-op. Well, I think the compiler is just thinking that the control flow of a correct program cannot cause UB, so the path causing UB is infeasible path and is optimized away. E.g. https://godbolt.org/z/h69GnfYbd https://godbolt.org/z/h69GnfYbd where the path causing UB is optimized away and it just returns 42 (and a call to rand).
    - lifthrasiir 3y ago
      I wonder why the original example emits `ret` instead of `ud2`. Clang is known to emit it for paths with the provable UB.
      - nwallin 3y ago
        Theirs not to reason why. Theirs but to do and die. Likely there's some SSA going on that recons the value from the pointer is undefined. So any value will do. And whatever value happens to be in eax is a perfectly cromulent value; might as well just return that.
        lifthrasiir 3y ago
        I mean, there is even no reason to emit a single instruction. However it would be helpful for the unconditional UB to turn to a trap (in fact, UB is particularly bad because some of them won't have a visible effect for a long time). Given clang and LLVM does emit ud2 for traps from UB, I think this could also have become ud2 but it somehow didn't.
      - ynik 3y ago
        It's because accessing uninitialized memory is not UB in clang. From clang's point of view, a read from uninitialized memory returns the special value `undef`. Many operations applied to `undef` also return `undef`, but some (e.g. branching `if (undef)`) are outright UB. But the original example doesn't do anything with `undef`, so it's not clang-UB. The compiler generated valid code for the function, it just happens to pick "whatever was previously in RAX" as the value read from the uninitialized memory. The malloc call is optimized out because it's no longer necessary after the uninitialized read was replaced (the same will happen to any other malloc call where the return value is unused). Note that the reason for this weird `undef` semantics ("almost but not quite UB yet") is that padding bytes are also uninitialized, but copying a whole struct incl. padding (even a memcpy-style byte-wise copy) must be defined behavior.
- nwallin 3y ago
  c code: #include <stdlib.h> int foo(int x) { int* p = malloc(1024); x = p[x]; free (p); return x; } assembly: foo: # @foo ret https://godbolt.org/z/jfvKon5v7 https://godbolt.org/z/jfvKon5v7
  - 4gotunameagain 3y ago
    change `int* p = malloc(1024);` to `volatile int* p = malloc(1024);` asm: foo: # @foo push rbx mov ebx, edi mov edi, 1024 call malloc@PLT movsxd rcx, ebx mov ebx, dword ptr [rax + 4\*rcx] mov rdi, rax call free@PLT mov eax, ebx pop rbx ret https://godbolt.org/z/E6Teqns8b https://godbolt.org/z/E6Teqns8b
    - tleb_ 3y ago
      That is because there is a read to p[x]. If it gets removed, the malloc and free disappear. volatile shouldn't appear in such code that does not handle MMIO memory.
      - 4gotunameagain 3y ago
        Why not? I have used volatile countless times to work around optimisations
        dwattttt 3y ago
        The optimisation is (absent a bug in the compiler) valid, unless you've written UB in there somewhere. The _reason_ to try not to volatile something is that optimisation is quite a powerful one; if the compiler can prove something written to memory can't have changed since it was written, then it doesn't need to load it from memory if it's later used. Hits to memory can be quite slow, so this optimisation entirely removing the hit can make a big difference if the code is performance sensitive.
- nlewycky 3y ago
  > 1. it's insane. nobody would write such an optimization because there's no possible performance gain, and it changes program behavior LLVM explicitly has an 'undef' constant value which facilitates this optimization. https://llvm.org/docs/LangRef.html#undefined-values https://llvm.org/docs/LangRef.html#undefined-values FWIW, the most important reason compilers do this is to decrease compile time. The compiler notices that some code has undefined behaviour and deletes the code now instead of waiting to prove that the path to this code is unreachable. The later optimizations tend to be slower and scale badly with more code in the function, so deleting it earlier will speed up the compilation. > 2. malloc is just a function, it's not treated in any special way The compiler is full of optimizations that treat malloc and other functions specially. This file implements an analysis, but the results of the analysis is used by transformations. https://github.com/llvm/llvm-project/blob/main/llvm/lib/Analysis/MemoryBuiltins.cpp#L55 https://github.com/llvm/llvm-project/blob/main/llvm/lib/Anal... > 3. there's no guarentee this malloc is a per-spec malloc, it can be a user-defined function for which this is perfectly valid Yep, there's a flag for that mode, `-ffreestanding` which corresponds to freestanding mode in the C89 standard, section 2.1.2.1. Without that flag, we assume malloc, strlen, etc., are the standard library functions that do as described in the standard.
- lifthrasiir 3y ago
  Others have explained pretty well about UBs, but I would give an explicit evidence against 2 by quoting the actual glibc code [1]: /* Allocate SIZE bytes of memory. */ extern void *malloc (size_t __size) __THROW __attribute_malloc__ __attribute_alloc_size__ ((1)) __wur; Expanding macro gives three GCC function attributes [2]: `__attribute__ ((malloc))`, `__attribute__ ((alloc_size(1)))` and `__attribute__ ((warn_unused_result))`. They are used for GCC (and others recognizing them) to actually ensure that they behave as the standard dictates and give better error messages. Your own malloc-like functions won't be treated same unless you give similar attributes. [1] https://github.com/bminor/glibc/blob/807690610916df8aef17cd14bfadd5d4b6e699a9/stdlib/stdlib.h#L671-L676 https://github.com/bminor/glibc/blob/807690610916df8aef17cd1... [2] https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attribute...
- turndown 3y ago
  Others have shown that your degenerate example really does optimize it all away, but I'll just say that we really do exist in a theoretical fairy dust C++ spec environment, because when we compile a piece of code we compile it against the abstract machine. This is one of those insane gotchas of programming languages - unless you're writing assembly yourself you must pass the bar set by the abstract machine and nothing else. I recommend [0], along with every link in the article, and every article on the blog. 0: https://research.swtch.com/ub https://research.swtch.com/ub
  - userbinator 3y ago
    This is one of those insane gotchas of programming languages ...created only by adversarial compiler writers who seem to be as user-hostile as a lot of other "developers" these days. They can get away with being pedantic assholes, because they know that realistically no one is going to switch compilers that easily. That said, C and even C++ used to not be like this.
    - sweetjuly 3y ago
      Compiler authors aren't doing this because they hate you, they're doing this because we want ever high performance. C and C++ didn't use to be like this because compilers were not capable of making the optimizations they can today.
      - userbinator 3y ago
        MSVC and especially ICC got higher performance than GCC without exploiting UB, so how do you explain that?
        spacechild1 3y ago
        > MSVC Citation needed. This does not match my experience. > ICC If I'm not mistaken, this is largely because ICC uses unsafe math optimizations by default.
lifthrasiir 3y ago
See also https://stackoverflow.com/a/43825157 https://stackoverflow.com/a/43825157 for possible workarounds. If you care about the standard comformance `calloc` seems the best approach.
tedunangst 3y ago
It's not required that the memory be uninitialized. The trick also permits reusing the same memory without clearing every time.
laanaah 3y ago
The way I usually deal with this nonsense is to write a function in assembly that returns its pointer argument: stop_messing_with_my_code: mov rax, rdi ret extern "C" void *stop_messing_with_my_code(void *); void *p = stop_messing_with_my_code(malloc(100)); // compiler cant know what my function does, it might have initialized it, // aligned it properly, returned the correct, type, etc. Also useful for getting around the idiotic type-based aliasing so you can write custom allocators (i.e a byte pool allocated statically/globally, then allocate data from that which is common in embedded, which is technically not possible in standard C or C++...)
- gpderetta 3y ago
  Laundering your pointers through no-op inline asm also helps.
  - thrtythreeforty 3y ago
    This is an extremely useful trick for foiling the optimizer. To make it explicit, it goes like this: asm volatile("" : "+r"(my_val) ::); This means "an empty assembly statement that you must assume contains side effects, and takes my_val as an input register and modifies it somehow." Note that because there is no assembly, this is perfectly portable (across architectures, maybe not across compilers, since only GCC and Clang know this syntax). I've used it to get the compiler to forget that function pointers cannot be null, for example. Of course you are still in "implementation defined behavior" land re: the standard. But it's often pretty easy to reason like the compiler does once you know your target architecture, and once your values are all unconstrained integers.
- Joker_vD 3y ago
  > a byte pool allocated statically/globally, then allocate data from that which is common in embedded, which is technically not possible Is it? I thought that char-pointers-into-char-arrays are specifically allowed to alias with whatever type. But yeah, it's a shame we don't have an official "launder" function a-la C++: the malloc/calloc/realloc get to launder the pointers they return simply because the standard declares those functions special.
anonymoushn 3y ago
If we actually got sparse from mmap, it's all zeros, and if it has nonzero numbers in it, it's because we previously wrote them. Seems like you only catch nasal demons if you make the mistake of calling malloc.
- ahoka 3y ago
  Yes, this is actually a good solution.
- gpderetta 3y ago
  or use calloc. Or just zero the whole buffer the first time: both mmap and calloc will have to zero on first use anyway, but future resets won't need zeroing. Or use optimization barriers as described elsethread.

alexvitkov 3y ago

If you're running in some theoretical fairy dust C++ spec environment sure, but in reality sparse is just a pointer and the compiler can't know its value, or whether or not it's "initialized". Even if you construct a degenerate case: int* sparse = (int*)malloc(100 * sizeof(int)); int x = sparse[40]; // provably unitialized it still won't "optimize out" the access, since 1. it's insane. nobody would write such an optimization because there's no possible performance gain, and it changes program behavior 2. malloc is just a function, it's not treated in any special way 3. there's no guarentee this malloc is a per-spec malloc, it can be a user-defined function for which this is perfectly valid

dwattttt 3y ago
to address the points in order: 1. a specific optimisation pass won't do this, but the combination of several passes written with other intentions can 2 & 3. the C runtime a compiler links with is known to the compiler/linker, and it _does_ usually treat intrinsics like malloc specially A quick google reveals https://github.com/llvm/llvm-project/issues/52930 https://github.com/llvm/llvm-project/issues/52930, LLVM recognising uninitialised memory as 'undef', and needing to treat it as poisoned (IIRC propogation of undef can cause things like separate uses of the variable to not even unify to a single value) EDIT: duplicated link
adwn 3y ago
Well, you're 100% wrong: https://godbolt.org/z/en31xx9Yx https://godbolt.org/z/en31xx9Yx clang optimizes this function to a single ret, optimizing away not just the memory access, but the call to malloc() as well. I does this (and is allowed to do this) because it recognizes that sparse[40] accesses uninitialized memory, which is UB, and therefore anything goes – including replacing the entire function with a no-op.
- pca006132 3y ago
  > and therefore anything goes – including replacing the entire function with a no-op. Well, I think the compiler is just thinking that the control flow of a correct program cannot cause UB, so the path causing UB is infeasible path and is optimized away. E.g. https://godbolt.org/z/h69GnfYbd https://godbolt.org/z/h69GnfYbd where the path causing UB is optimized away and it just returns 42 (and a call to rand).
  - lifthrasiir 3y ago
    I wonder why the original example emits `ret` instead of `ud2`. Clang is known to emit it for paths with the provable UB.
    - nwallin 3y ago
      Theirs not to reason why. Theirs but to do and die. Likely there's some SSA going on that recons the value from the pointer is undefined. So any value will do. And whatever value happens to be in eax is a perfectly cromulent value; might as well just return that.
      - lifthrasiir 3y ago
        I mean, there is even no reason to emit a single instruction. However it would be helpful for the unconditional UB to turn to a trap (in fact, UB is particularly bad because some of them won't have a visible effect for a long time). Given clang and LLVM does emit ud2 for traps from UB, I think this could also have become ud2 but it somehow didn't.
    - ynik 3y ago
      It's because accessing uninitialized memory is not UB in clang. From clang's point of view, a read from uninitialized memory returns the special value `undef`. Many operations applied to `undef` also return `undef`, but some (e.g. branching `if (undef)`) are outright UB. But the original example doesn't do anything with `undef`, so it's not clang-UB. The compiler generated valid code for the function, it just happens to pick "whatever was previously in RAX" as the value read from the uninitialized memory. The malloc call is optimized out because it's no longer necessary after the uninitialized read was replaced (the same will happen to any other malloc call where the return value is unused). Note that the reason for this weird `undef` semantics ("almost but not quite UB yet") is that padding bytes are also uninitialized, but copying a whole struct incl. padding (even a memcpy-style byte-wise copy) must be defined behavior.
nwallin 3y ago
c code: #include <stdlib.h> int foo(int x) { int* p = malloc(1024); x = p[x]; free (p); return x; } assembly: foo: # @foo ret https://godbolt.org/z/jfvKon5v7 https://godbolt.org/z/jfvKon5v7
- 4gotunameagain 3y ago
  change `int* p = malloc(1024);` to `volatile int* p = malloc(1024);` asm: foo: # @foo push rbx mov ebx, edi mov edi, 1024 call malloc@PLT movsxd rcx, ebx mov ebx, dword ptr [rax + 4\*rcx] mov rdi, rax call free@PLT mov eax, ebx pop rbx ret https://godbolt.org/z/E6Teqns8b https://godbolt.org/z/E6Teqns8b
  - tleb_ 3y ago
    That is because there is a read to p[x]. If it gets removed, the malloc and free disappear. volatile shouldn't appear in such code that does not handle MMIO memory.
    - 4gotunameagain 3y ago
      Why not? I have used volatile countless times to work around optimisations
      - dwattttt 3y ago
        The optimisation is (absent a bug in the compiler) valid, unless you've written UB in there somewhere. The _reason_ to try not to volatile something is that optimisation is quite a powerful one; if the compiler can prove something written to memory can't have changed since it was written, then it doesn't need to load it from memory if it's later used. Hits to memory can be quite slow, so this optimisation entirely removing the hit can make a big difference if the code is performance sensitive.
nlewycky 3y ago
> 1. it's insane. nobody would write such an optimization because there's no possible performance gain, and it changes program behavior LLVM explicitly has an 'undef' constant value which facilitates this optimization. https://llvm.org/docs/LangRef.html#undefined-values https://llvm.org/docs/LangRef.html#undefined-values FWIW, the most important reason compilers do this is to decrease compile time. The compiler notices that some code has undefined behaviour and deletes the code now instead of waiting to prove that the path to this code is unreachable. The later optimizations tend to be slower and scale badly with more code in the function, so deleting it earlier will speed up the compilation. > 2. malloc is just a function, it's not treated in any special way The compiler is full of optimizations that treat malloc and other functions specially. This file implements an analysis, but the results of the analysis is used by transformations. https://github.com/llvm/llvm-project/blob/main/llvm/lib/Analysis/MemoryBuiltins.cpp#L55 https://github.com/llvm/llvm-project/blob/main/llvm/lib/Anal... > 3. there's no guarentee this malloc is a per-spec malloc, it can be a user-defined function for which this is perfectly valid Yep, there's a flag for that mode, `-ffreestanding` which corresponds to freestanding mode in the C89 standard, section 2.1.2.1. Without that flag, we assume malloc, strlen, etc., are the standard library functions that do as described in the standard.
lifthrasiir 3y ago
Others have explained pretty well about UBs, but I would give an explicit evidence against 2 by quoting the actual glibc code [1]: /* Allocate SIZE bytes of memory. */ extern void *malloc (size_t __size) __THROW __attribute_malloc__ __attribute_alloc_size__ ((1)) __wur; Expanding macro gives three GCC function attributes [2]: `__attribute__ ((malloc))`, `__attribute__ ((alloc_size(1)))` and `__attribute__ ((warn_unused_result))`. They are used for GCC (and others recognizing them) to actually ensure that they behave as the standard dictates and give better error messages. Your own malloc-like functions won't be treated same unless you give similar attributes. [1] https://github.com/bminor/glibc/blob/807690610916df8aef17cd14bfadd5d4b6e699a9/stdlib/stdlib.h#L671-L676 https://github.com/bminor/glibc/blob/807690610916df8aef17cd1... [2] https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attribute...
turndown 3y ago
Others have shown that your degenerate example really does optimize it all away, but I'll just say that we really do exist in a theoretical fairy dust C++ spec environment, because when we compile a piece of code we compile it against the abstract machine. This is one of those insane gotchas of programming languages - unless you're writing assembly yourself you must pass the bar set by the abstract machine and nothing else. I recommend [0], along with every link in the article, and every article on the blog. 0: https://research.swtch.com/ub https://research.swtch.com/ub
- userbinator 3y ago
  This is one of those insane gotchas of programming languages ...created only by adversarial compiler writers who seem to be as user-hostile as a lot of other "developers" these days. They can get away with being pedantic assholes, because they know that realistically no one is going to switch compilers that easily. That said, C and even C++ used to not be like this.
  - sweetjuly 3y ago
    Compiler authors aren't doing this because they hate you, they're doing this because we want ever high performance. C and C++ didn't use to be like this because compilers were not capable of making the optimizations they can today.
    - userbinator 3y ago
      MSVC and especially ICC got higher performance than GCC without exploiting UB, so how do you explain that?
      - spacechild1 3y ago
        > MSVC Citation needed. This does not match my experience. > ICC If I'm not mistaken, this is largely because ICC uses unsafe math optimizations by default.

lifthrasiir 3y ago

See also https://stackoverflow.com/a/43825157 https://stackoverflow.com/a/43825157 for possible workarounds. If you care about the standard comformance `calloc` seems the best approach.

tedunangst 3y ago

It's not required that the memory be uninitialized. The trick also permits reusing the same memory without clearing every time.

laanaah 3y ago

The way I usually deal with this nonsense is to write a function in assembly that returns its pointer argument: stop_messing_with_my_code: mov rax, rdi ret extern "C" void *stop_messing_with_my_code(void *); void *p = stop_messing_with_my_code(malloc(100)); // compiler cant know what my function does, it might have initialized it, // aligned it properly, returned the correct, type, etc. Also useful for getting around the idiotic type-based aliasing so you can write custom allocators (i.e a byte pool allocated statically/globally, then allocate data from that which is common in embedded, which is technically not possible in standard C or C++...)

gpderetta 3y ago
Laundering your pointers through no-op inline asm also helps.
- thrtythreeforty 3y ago
  This is an extremely useful trick for foiling the optimizer. To make it explicit, it goes like this: asm volatile("" : "+r"(my_val) ::); This means "an empty assembly statement that you must assume contains side effects, and takes my_val as an input register and modifies it somehow." Note that because there is no assembly, this is perfectly portable (across architectures, maybe not across compilers, since only GCC and Clang know this syntax). I've used it to get the compiler to forget that function pointers cannot be null, for example. Of course you are still in "implementation defined behavior" land re: the standard. But it's often pretty easy to reason like the compiler does once you know your target architecture, and once your values are all unconstrained integers.
Joker_vD 3y ago
> a byte pool allocated statically/globally, then allocate data from that which is common in embedded, which is technically not possible Is it? I thought that char-pointers-into-char-arrays are specifically allowed to alias with whatever type. But yeah, it's a shame we don't have an official "launder" function a-la C++: the malloc/calloc/realloc get to launder the pointers they return simply because the standard declares those functions special.

anonymoushn 3y ago

If we actually got sparse from mmap, it's all zeros, and if it has nonzero numbers in it, it's because we previously wrote them. Seems like you only catch nasal demons if you make the mistake of calling malloc.

ahoka 3y ago
Yes, this is actually a good solution.
gpderetta 3y ago
or use calloc. Or just zero the whole buffer the first time: both mmap and calloc will have to zero on first use anyway, but future resets won't need zeroing. Or use optimization barriers as described elsethread.