Hacker News Reader

Comment by alexvitkov | Hacker News Reader

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

View on HN

> 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

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/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.

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

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.

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.

MSVC and especially ICC got higher performance than GCC without exploiting UB, so how do you explain that?

> 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.

Here's some examples where ICC comes out ahead, often far ahead:

https://keyj.emphy.de/compiler-benchmark/

https://iitd-plos.github.io/col729/labs/lab0/lab0_submission...

As for MSVC, my experience has been that it often generates smaller and slightly faster code than the others (except for ICC), but there's definitely some styles of code which it won't want to optimise.

They definitely “exploit” UBs, any proof on the contrary?

Somebody removed all the insane UB-"optimizations" and the result wasn't even any slower. Can't find the blog now.

I'd be quite interested to read that post, given that one of the big UB hammers is strict aliasing which gets used a _lot_

How do you decide whether an UB-optimization is insane or not? "I know it when I see it" may work for lawmakers, but it's not good enough for compiler developers.

Because if you want to disable all UB-based optimizations, there's already a compiler flag that does that: -O0.

Seriously, in a language as low level as C++, every optimization needs some form of assumptions, and UB is how we currently allow compilers to make those assumptions.

Example: because it's undefined behavior to read pointers out-of-bounds, it is not possible for a valid program to scan a whole stack frame, so it is okay for the compiler to remove variables from the stack frame and instead store them in registers.

Without UB-optimizations, you would need some others justification of why it is okay for the compiler to change the result of a stack scan. Or use -O0 which keeps all variables on the stack. (but that certainly will be slower!)

Look at Intel's compiler or MSVC, vs. GCC and LLVM. The former two are known to rarely exploit UB, yet are competitive and even faster with certain code (especially ICC) compared to the latter two.

and UB is how we currently allow compilers to make those assumptions.

No, the behaviour of the target hardware is what should guide that.

UB has no bearing on that. If a variable has never had its address taken, then there's no expectation that it ever be in memory.

> UB has no bearing on that. If a variable has never had its address taken, then there's no expectation that it ever be in memory.

there were plenty of programs that expected specific stack layouts and were broken when compilers started optimizing stack spilling/register allocation more aggressively. Remember that register existed as a keyword.

The address taken might have been a useful practical rule for some compiler, but I don't think it was ever endorsed by the standards (except for prohibiting taking the address of a register variable in C).

As mentioned in another comment in this thread, UB optimizations (whatever that means) are not about “hah, let’s make this edge case a trap for the programmers”, it is about general assumptions the compiler writer gets to make if they leave the door open for that through UB.

Say, you could remove this memory read and reuse the variable’s value from the top of the function, but to be able to make this optimization you need it explicitly stated that no other thread can modify the memory in the meanwhile. UB makes the assumption valid, without it you could barely apply any optimizations.

This seems like the sort of a comment that can only be written by completely refusing to understand why compiler writers take advantage of UB. Compiler writers are not engaging in "adversarial" behavior with their users -- they are their own users!

The simple truth is a lot of UB exists to allow for optimizations that programmers entirely take for granted. In order to optimize something, you have to make assumptions, particularly when dealing with languages as permissive as C and C++. By programming to an abstract machine and explicitly specifying which behavior is defined and which is not, we allow a compiler to make these assumptions. Despite what you may wish, a compiler is not able to read your mind to know when a given piece of UB is actually code that you intended to execute with particular semantics, or whether it's the result of some other optimizations on a code path that will never execute.

> Compiler writers are not engaging in "adversarial" behavior with their users -- they are their own users!

Only if your language is self-hosting, isn't it?

That's usually a major checkpoint for a programming language maturing no?

Go became self-hosting in 2015 (1.5) [1]

Rust was originally written in OCaml and became self-hosted in 2011 - excluding LLVM of course, but I guess, that's kind of up to you where you draw that specific line.

[1] https://go.dev/blog/go1.5

It might make sense for a General Purpose language, but really only if the language's goals make it suitable.

For example suppose you decided goal #1 is ease of use for beginners so you consciously choose verbose syntax. It's unlikely that your compiler is written by beginners and they may get sick of needing all this verbosity.

For Special Purpose languages it only makes sense if their purpose is centrally writing compilers. It doesn't make sense to write your Verilog "compiler" in Verilog.

> That's usually a major checkpoint for a programming language maturing no?

It depends on the goals of the language. Of course, compiler writers tend to be (relative) fans of their language, so they might want to use it more than might be wise.

But eg I wouldn't want to write _any_ compiler in C or Fortran or Cobol. That includes not wanting to write C, Fortran or Cobol compilers in these languages.

(But I think any language that you might want to write a compiler in should have algebraic data types and pattern matching at the very least, especially these days.)

Somewhat ironically, writing a Python compiler in Python would be an ok idea, but writing a Python interpreter in Python is probably not a good one.

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

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

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.

Why not? I have used volatile countless times to work around optimisations

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.

In the general case you're right, in this case where the optimization is related to the usage of uninitialized memory I don't think that you're correct. Of course this means that the programmer must 'think like an optimizer' and rewrite is-member(i): return sparse[i] < n && dense[sparse[i]] == i as uint sparse = sparse[i] return sparse < n && dense[sparse] == i otherwise the compiler would generate two load instead of 1.

Well, you're 100% wrong: 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.

> 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 where the path causing UB is optimized away and it just returns 42 (and a call to rand).

I wonder why the original example emits `ret` instead of `ud2`. Clang is known to emit it for paths with the provable UB.

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.

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.

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.

is there an option to emit a warning on encountering ub?

That's impossible in the general case, but there are compiler warnings that try to help you catch as much as they can, use `-Wall` when building code, and there is runtime instrumentation `-fsanitize=undefined` to catch as much UB as possible without breaking the ABI. Also consider using `-fsanitize=address,undefined` while developing and `-fsanitize=thread` for threaded code. `-fsanitize=memory` is a bit difficult to deploy because you need all your libraries (except libc) to be built with it too, including your C++ standard library if you're building C++.

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/807690610916df8aef17cd1...

[2] https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attribute...

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, 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

Reply on news.ycombinator.com