How is this UB? foo() won't have any access to y so won't be able to modify it, so we can be more or less certain that y is still 42 when bar() is called? What is it that i'm missing?

That's it -- the optimization is legal because there's no way foo() could modify y, because any (&x)[1] = 20 shenanigans would be UB.

This is how UB is used in optimizations; it's (usually) not that the compiler is finding positions where UB occurs and explicitly choosing to perform mischief, it's performing a bunch of simple and obviously-what-you-want rewrites that are only correct because of UB; otherwise, arbitrary pointer writes are too powerful.

UB is what allows `(&x)[1]` to happen at all. If you didn't have UB, there would be no reasonable way to allow code that messes up arbitrary pointers.

A typical non-UB language wouldn't allow `(&x)[1]` and it would be easy to allow the optimization.

It would be difficult or obtuse to design a non-UB language that doesn't allow optimizing y away.

Standard Forth, to my knowledge, doesn't have UB and consequently doesn't allow the optimization. That'd just be

    : foo CELL + 20 SWAP ! ;

there. Machine languages also generally don't have this kind of UB, and don't allow the optimization.

It's not impossible to imagine a C without UB, it's just not a particularly desirable language.

Parameters don't really work the same way in Forth. A similar C program would explicitly pass in an entire stack every time it runs a function, or have a global stack variable. And such a C program would disallow the optimization whether or not you consider UB.

Machine language means you have basically no rules imposed on your code at all. So it's true that you can't optimize anything, but I think that's outside the scope of normal language talk.

In my example, the variables are assumed to be addressable, only the address of x was passed via the stack.

Dunno what you mean about having no rules imposed on your code -- you can define the semantics of the language formally and execute them on a machine, same as you can for C, JavaScript, or Prolog.

> In my example, the variables are assumed to be addressable, only the address of x was passed via the stack.

Yeah but I could add 3 billion to the pointer instead. Now what happens, if we're trying to define behavior?

> you can define the semantics of the language formally

If the semantics aren't a direct translation into CPU opcodes, then it's not machine code. And CPU opcodes can access all memory at all times including self-inspection so you can't change anything for optimization purposes without an additional framework on top.

> Now what happens, if we're trying to define behavior?

The cell whose address is three billion greater, mod the size of the address space, now has a value of 20?

> If the semantics aren't a direct translation into CPU opcodes, then it's not machine code.

Just because the semantics are defined that way doesn't necessarily mean you couldn't make another implementation that obeys those semantics. For instance, QEMU can perform optimizations on the code it runs, and invalidate them if the program changes those instructions. The semantics of reading from and writing to memory are unchanged by these optimizations, and the implementation doesn't need to do anything special on read.

> The cell whose address is three billion greater, mod the size of the address space, now has a value of 20?

Cool. It sounds like you figured out a restricted form of pointers for stack variables, since there's no danger of corrupting the code or breaking important invariants elsewhere.

Now imaging tightening those restrictions a bit. Instead of wrapping pointers inside the entire stack, wrap pointers inside their original variable.

Now you have a language with no UB that allows the optimizer to replace y with 42!

> For instance, QEMU can perform optimizations on the code it runs, and invalidate them if the program changes those instructions.

The machine can take shortcuts, and when QEMU is acting as a virtual machine it can do that. But the compiler can't take any shortcuts, because it never knows when external code is going to examine random bytes and need them to be unchanged.

> Now imagine tightening those restrictions a bit.

Yep, that's one approach, though that's just as hard to compile as one that is defined to trap and end execution on an out-of-bounds write.

As I said up-thread, it's possible to define a C dialect without UB, it's just not what most of its users actually want out of the language, since on current hardware it adds significant runtime overhead.

> The machine [...] the compiler

Isn't QEMU both the machine and the compiler (EDIT: perhaps better-put, what's the distinction? They're both just the implementation.) The bytes only need to be unchanged on read from inside the program; if you compile them to something else, that's fine. Prolog programs can introspect with clause/2 and it doesn't cause trouble there.

> Yep, that's one approach, though that's just as hard to compile as one that is defined to trap and end execution on an out-of-bounds write.

> As I said up-thread, it's possible to define a C dialect without UB, it's just not what most of its users actually want out of the language, since on current hardware it adds significant runtime overhead.

So my core point is this: It's not UB that enables this optimization. When you ask "how can that optimization be legal without UB?", the hard part is "without UB" all by itself. If you have a language with UB, the optimization is easy to enable. If you have a language without UB, the optimization is easy to enable. That optimization is not an example of why we need UB.

> Isn't QEMU both the machine and the compiler (EDIT: perhaps better-put, what's the distinction? They're both just the implementation.) The bytes only need to be unchanged on read from inside the program; if you compile them to something else, that's fine. Prolog programs can introspect with clause/2 and it doesn't cause trouble there.

Basically, I don't think "The bytes only need to be unchanged on read from inside the program" is true. If you're compiling machine code you're not in charge of the entire computer. The code might ask other code to look at the bytes, and you won't be able to intercept that unless you do some kind of ridiculous rootkit takeover when the compiled program launches, creating a virtual machine and moving everything that was already running into it.

> that's just as hard to compile as one that is defined to trap and end execution on an out-of-bounds write

I believe simply disallowing "+" and "-" from accepting pointer types is slighlty less work than writing logic for "integral + pointer", "pointer + integral", "pointer - integral", and "pointer - pointer". Although on the other hand it means that instead of literally rewriting "a[i]" to "*(a+i)" in the AST, one has to write a separate logic for array accesses so... okay, so it's exactly as easy to compile ("as hard" technically works as well, but since it's actually rather easy, not hard, I've chosen "as easy", hope you don't mind).

The UB permits the optimization, but is not necessary for it. If a language had a stricter definition of pointer and memory access behavior then the optimization would still be applicable if it conformed to the assumption that people are making around the UB in C.

UB is not necessary for optimization, it just permits some optimizations which may or may not be valid and may or may not be consistent across compilers and platforms because people get to fill in the gaps with whatever they want.

The biggest misunderstanding people have around UB is—in my experience—the (often) subconscious assumption that UB optimization is around optimizing the performance of code that exhibits UB. It is not.

You're partially correct. foo() won't have any access to y so won't be able to modify it… unless foo() is written in way that exploits undefined behavior. Compilers can (and should) assume that foo() is not written pathologically in a way that writes into the frames of functions higher in the call stack, and so can make the above optimization.

Y is never visible from foo()s scope. You'd have to employ ABI specific stack manipulation to get to it. Optimization in the outside frame doesn't depend on foo().

And that ABI specific stack manipulation would be UB, so the optimizer can assume it doesn't happen. With no UB, that's not true.

You assume a langue without UB would allow stack manipulation. But then it would have to be defined. How would you possibly define it fully?

There's an area of memory into which variables with automatic storage duration are allocated at implementation-defined addrs, at any point exactly those variables have addresses.

> at any point exactly those variables have addresses

That doesn't sound like it lets me increment any stack address I want and store into the resulting pointer.

And are return values still on the same stack? I probably should have said I meant the traditional kind of C stack.

> That doesn't sound like it lets me increment any stack address I want and store into the resulting pointer.

Why not?

> And are return values still on the same stack?

Other implementation-defined things might have addresses too, those things just aren't variables. I think you might be able to still allow inlining without UB if you make it implementation-defined per call-site what other things might get addresses.

> Why not?

At this point the conversation has completely converged so I'm only going to reply over here: https://news.ycombinator.com/item?id=36169808