>The standard doesn’t describe transformations; it describes behaviors

That is not remotely true - as you can see by looking up the example I reference.

>For C, that’s not something we can realistically do in every case. There’s no way to reasonably constrain the set of allowed behaviors after a program does some crazy pointer operation like * (int *) rand() = rand(), because any implementation of those constraints would more or less require an expensive run-time check at every pointer access.

That's such a weird response. There is nothing in the proposal that requires run-time checks. The proposal simply limits the ability of the compiler/translator to make counter-factual assumptions or otherwise violate the C semantics.

>What you could meaningfully ask is for particular situations (like negative shifts) to be considered unspecified or implementation-defined rather than undefined.

I don't want to do that: I want to clarify the meaning of "undefined behavior" to curtail its use as a license to do arbitrary code transformations. One implementation may trap on a negative shift, one may generate negative shift instructions that the architecture treats as no-ops or whatever they do, one might do sufficient static analysis to detect negative shifts and generate an error message - but the compiler is not free to assume that the shift operator has a negative value.

I'm not trying to remove undefined behavior from C. I am trying to correct a mistaken analysis of what undefined behavior should mean. C is intended to allow for non-portable operations, for example. These are "undefined" in the standard because they depend on the implementation, not because the C language should be specified so as to allow compilers to introduce hidden booby traps or counter-factual assumptions into the implementation

You should read the post you are replying to again, as it is well written and precise.

Basically, the intent of the proposal is understandable but it does not make sense as written.

The spec does not explain how to compile C code, it gives you a set of rules so that you could in theory take some piece of C source and a full execution trace and verify whether that trace was a conforming execution for that C code.

You take the example of the negative shift again, and it is addressed in the post you respond to : it's a perfectly fine proposal to demote negative shifts from UB to something less permissive to the compiler.

However, if you do so, of course, you have to frame what behaviors are accepted for a program doing such a negative shifts, just as you did in your post !

So let's say : arbitrary (but consistent) values are fine, termination is fine. That's great because it means we can still compile a shift to a CPU shift and there's no UB anymore. Ok.

Same goes for signed overflow.

However this is a case by case process, and you will absolutely not be able to ascribe meaning this way to many forms of UB. For example, as the GP said, storing through an invalid pointer.

If you want to compile a pointer store to a store instruction without runtime checks, then possible observable behavior include : other variable changing values, function call not returning to their calling context, and even of course running a full ROP chain exploit !

It's no surprise that in that case the specs says that the set of allowed observable behaviors is anything.

Argument like yours seem to rely on an incorrect understanding of the design of C. Languages like Java encapsulate program execution in a runtime that, in theory, can catch and manage all sorts of programmer errors that C does not catch. That's ok. If the programmer references past the end of an array, the compiler may catch and object, it may simply compile the instructions and let the program step on its own data structures or encounter a memory fault or even a protection violation if the architecture provides some type protection. And it's bizarre to see this warning about ROP exploit, when current "optimization" based on UB is a source of ROP exploit vulnerability. One cannot reliably put protections in code against bad pointers if upstream errors are grounds for deleting the guards.

> It's no surprise that in that case the specs says that the set of allowed observable behaviors is anything.

And yet UB is frequently described as this scary monster that will eat your hard drive.

Sure there are more UBs in C than there would need to be if the standard restricted more on contemporary hardware. I think it still allows ones' complement representation for example? But I guess it shouldn't be so bad as long as compilers do not exploit the freedom to do anything that comes from UB, more than they need to on a particular architecture?

Compilers do not "exploit the freedom to do anything that comes from UB", they just assume that the program does not have UB. This might or might not lead the compiler to behave as if it was doing anything it wants, but it's not screwing the programmer on purpose.

As for "UB is frequently described as this scary monster that will eat your hard drive", setting aside that UB could be exploited by an attacker, it's not hard to imagine, for instance, a recursive file deletion routine that is affected by UB misbehaving and erasing more than it should.

Let me take a shift operation as an example. On architectures where it's no problem to "overshift" (e.g. the operation always results in 0), the compiler could be just fine and leave shifts alone. Maybe a 0 is exactly what the user wanted!

Or, the compiler could assume that the programmer made sure that overshifting never happens, since it's UB. Based on that assumption, it could make more aggressive (and possibly totally insignificant) optimizations by inferring other assumptions that don't align with the programmer's idea anymore.

I never encountered such a sitation myself, but there are stories like that on the internet, where for example the Linux kernel was broken.

Another scenario, the user might always do an operation that sometimes results in a random value (which is UB), but in the end only use the resulting value if it was not UB. The compiler instead could assume the operation can never happen in the first place. Again, there is a misalignment here in how the compiler reasoned and how the programmer reasoned (closer to the actual hardware).

So, the difficult problem is probably defining the UB configurations as narrowly as possible. It might be a good idea to specify UB per architecture in some cases, but then it would lead to a lot of complexity. In any case a guideline for compilers should be to minimize surprises, which means not applying many optimizations around UB. That's easier said than done I guess.

> As for "UB is frequently described as this scary monster that will eat your hard drive", setting aside that UB could be exploited by an attacker, it's not hard to imagine, for instance, a recursive file deletion routine that is affected by UB misbehaving and erasing more than it should.

I'd figure it's much more likely to happen as a result of a logic error introduced by the programmer, without any UB involved.

There's also this infamous example of UB: https://kristerw.blogspot.com/2017/09/why-undefined-behavior... (explanation: https://blog.tchatzigiannakis.com/undefined-behavior-can-lit...)

Thanks, that's interesting. And still, it's artificially constructed, so concerning the point I made (actual logic bugs are more likely) I think it stands.

IMHO this is clearly a compiler bug. Yes, it's technically allowed to do this because calling a NULL function pointer is UB, but nobody wants such an optimization (which is my first point from earlier). If the compiler makes such a decision based on UB, shouldn't it be able to at least issue a warning?

Furthermore, why should this be optimized in the first place? If the user decides to make a function pointer instead of a hard-wired inlineable call, he is aware of the performance implications (which are negligible in 99.9% of the cases). Where function call efficiency matters, nobody ever used a function pointer.

Shouldn't the compiler architecture be able to avoid making this optimization, simply by avoiding propagating the UB? It should simply not say "Calling NULL can never happen". This way it would never make optimizations that make the situation even worse. I think this would even be less optimization code!

Instead, when the UB happens, the programmer should get what he deserves (which is, well, calling NULL, and most likely resulting in a segfault, which is the right thing).

On the other hand, if the compiler can infer the value of a function pointer based on propagation of values alone, I'm fine with hard-coding the address, even though it's probably not worth the effort anyway.

That's a "devirtualization" optimization. Suppose you have a C++ class with a virtual method (or something similar coded in C), which only has a single concrete implementation. Clearly, every place which calls that virtual method through any pointer to that class can only be calling that single concrete implementation, so the compiler can call the function directly instead of through the function pointer, perhaps even inlining the called function.

Yes, that EraseAll example is silly, but how can the optimizer distinguish it from non-silly examples? Perhaps there are other alternative functions which also set that same function pointer, but they were all hidden by some #ifdef; in that case, devirtualizing when there's only one option left will be a performance win, and can expose other optimization opportunities.

> devirtualization

Hmm, shouldn't it be possible to do that in some other way? After all, a virtual function is something different than a function pointer (the vtable holding a function pointer is only an implementation detail, isn't it?).

Anyway, I'd rather not have that optimization. When we don't want to pay a small performance hit, we shouldn't make a virtual function in the first place. It's good to see how advanced optimization tricks can combine in dangerous ways with complicated language features!

> distinguish it from non-silly examples?

Yes, probably not possible. There is a real risk, but non-silly examples are less likely than constructed ones.

> all hidden by some #ifdef

If you do it with the preprocessor, there is no need for function pointers in the first place. Just make a #define instead of a variable.

Thanks again for the example, very interesting!

Undefined behavior doesn’t exist to ease portability per se, it exists to handle meaningless yet syntactically valid constructs.

Shifting by a negative number is meaningless and is indicative of programming error. Instead of specifying that an implementation should check and handle these programming errors, which implies runtime costs, we use undefined behavior and leave the responsibility to the programmer.

The reason many compilers assume a positive shift after a shift operation executes is because otherwise the entire program would be undefined. You’re effectively asking for undefined programs to have defined behavior. The equivalent would be asking the compiler to correct your typos and it can’t do that. As they say: garbage in, garbage out. The compiler isn’t the one booby trapping you, you’re booby trapping yourself.

I think GP is right that what you want is more definition but it has to be in specific cases because otherwise the runtime costs would be too high. In your negative shift example, the definition would be “shifting by a negative number results in garbage output,” but note that that would burden implementations where negative shifts trap.

> it exists to handle meaningless yet syntactically valid constructs.

Maybe more like "handle bad situations that cannot be precluded at compile time". And since C has "no runtime", so can't do much "handling" at run time, it gets UB instead.

It doesn’t need to be unable to be precluded at compile-time to be UB. The expression “1 << -3” can be precluded at compile-time, yet it compiles just fine: instead it invokes UB.

Doing something at runtime is a different concept from having a runtime.

In any case, C, in fact, often does have a runtime. What do you think executes main()?

Yes, 1<<-3 can be detected as UB at compile time when doing constant propagation. But that wasn't my point (you could declare this expression invalid, no need for UB). I was pointing out that UB is not about "meaningless yet syntactically valid constructs" (if there is such a thing at all; I won't argue). UB in general manifests at run time. So I was only proposing a reformulation.

> In any case, C, in fact, often does have a runtime. What do you think executes main()?

Sure, that's why I said it has "no runtime" (in quotes). I'm not trying to split hairs here.

But your formulation isn’t right because it’s not about the UB code being detectable at compile-time or run-time, it’s about describing how the UB code should behave regardless of when it can be analyzed.

In the context of real numbers sqrt(-1) is syntactically valid yet meaningless code. In other contexts, 1 << -3 is too. Also log(-1). Perfectly valid syntax but has no meaning.

The intent of scare-quotes tends to be ambiguous so I avoid them in discussion. http://frivolousquotationmarks.tumblr.com

You're right, they're often ambiguous, but often I don't know how to say it tersely in a different way. My assumption was that in that context the statement [C has "no runtime"] had clear meaning, but maybe I was wrong. The point was to make it obvious that I don't want that be taken too literally, and that I don't want to start a hair splitting discussion whether C has a runtime or not. Apparently it didn't accomplish that goal.

As to the formulation of UB, it's not about code ("syntactically valid constructs") but about manifestation. And manifestation is a run time thing. 1<<-3 "is" UB, yes. And that can be detected at compile time through constant propagation. But that's not why we need UB. We could just forbid 1<<-3, so there was no need for UB in the first place.

UB is really about values not known at compile time. The expression 1<<x might manifest in UB at run time, depending on the value of x. Since x in general is not known well enough to decide whether it will ever be negative, the question "will this expression ever manifest in UB at run time?" is in general undecidable, so the best answer is "possibly". That does not imply that it's always a bad idea to use the expression 1<<x, and it does not make the construct meaningless. (Really I don't think the construct itself has a meaning, but as I said I won't argue here).

And that's why I think the formulation "handle meaningless yet syntactically valid constructs" is misleading. It's not about the construct (i.e., syntactic construction). It's about run time values that lead to UB, and that are totally independent from the construct itself. They might come from a wrong function invocation, or from malicious user input. It is the programmer's duty to make sure, by whatever means, that UB never manifests.

Maybe that's just what you were trying to say, but I think it's important to be clear that it's not about the syntactic constructs.

I’m not saying that 1<<x is generally meaningless. I’m saying that whenever the shift operand is negative, it’s meaningless. Just like log(x) isn’t generally meaningless, it’s only meaningless when the argument is not positive.

Syntactic constructs in general should and do have meaning. The meaning isn’t inherent, but nothing has inherent meaning. log(x) has no inherent meaning, but when x is positive we have decided that it means that it evaluates to the value to which you would raise 10 to get x.

Bad run-time values only cause UB in the context of improper usage in syntactic constructs. They aren’t independent of syntactic constructs: both syntactic constructs and values dictate behavior.

You’re right that UB only manifests itself at run-time. And you’re right that we wouldn’t need to use UB for constructs that only manifest their behavior at compile-time. Indeed, there exists syntactically valid yet meaningless C++ template substitutions that don’t result in UB, they result in compilation errors.

> The standard doesn’t describe transformations; it describes behaviors.

That doesn't seem to be an argument against, or even related to, what the proposal entails. All of these proposals are reductive attempts to curb the instability that UB introduces, for little value (see the linux kernel).

> because there was nothing to transform them _from_

Yes there was. Anything that can result in UB.

> For C, that’s not something we can realistically do in every case.

That's why the proposal is not exhaustive, as described.

There aren't things that "can result in" UB, though. The C code itself, before any compilation, is already undefined by the C spec.

For instance, the following code is not valid C code:

    int a[2], b;
    a[2] = 5;

The compiler is free to do anything it wants, because the standard has not defined what it does. It could stop. Most likely it will just overwrite whatever memory is after a[1] with 5, because that's easiest.

If you want the compiler to do something specific, you need to define it. In some cases the standard has language for otherwise-defined behavior that is carved out as undefined (e.g., strict aliasing), and it's easy to go "Never mind"; in some cases it does not (e.g., writing to a string literal). For these ones, the behavior needs to be defined.

Simply saying "Don't optimize this" is just saying "I'm not going to define the behavior, but don't implement it this way," which isn't a particularly useful way to define a standard (e.g., for the null checks example, is the compiler permitted to leave the null check in, but insert a segfault right before it?).

It's completely valid. It's just not conforming.

No the compiler is not entitled to insert a segfault. Segaults come from architectures and operating systems, not from compilers. The compiler is free to leave in the dereference of the null pointer and then, who knows what happens. But the compiler can't break the code by deleting a perfectly conforming null check on the theory that a previous dereference means that the pointer is not null.

The original Bourne shell used signal to catch memory faults so it could operate dynamic paging! If your OS/implementation permits, C is supposed to allow you do do things like that. The compiler is NOT supposed to insulate the programmer from bumps. (Disclaimer: I am not endorsing the horrible design of the Bourne shell which was also written in a macro style that made C into pseudo Algol).

> Segaults come from architectures and operating systems, not from compilers.

But when you are programming in C, you are programming against the C abstract machine, not against an architecture or operating system. It's this machine that you are breaking when you invoke ub.

C is not Java.

... and ? it still targets an abstract machine, defined in the C standard in section 5.1.2.3 (Program execution) : http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf

It targets the abstract machine, but the dispute here is about what should happen when the program operation goes into territory that the abstract machine does not specify. And C code is EXPECTED to go beyond the territory of the abstract machine.

> And C code is EXPECTED to go beyond the territory of the abstract machine.

Passive voice! You expect C code to go beyond the territory of the abstract machine. The authors of the standard, quite clearly, do not.

I can see both of these arguments. I think there is a place in the world for a C that is machine-specific. But it's clearly not what the standard authors have in mind, there are clearly people who find the genericness of C useful (cf. "portable assembler"), and piecemeal solutions like skipping individual bad optimizations won't solve the underlying problem that there's no way in C to say "Dude, I'm writing for a reasonable UNIX on a reasonable modern machine with a single flat address space for code and data and non-exception-raising two's-complement arithmetic and the ability to do nonaligned reads/writes and other normal things, please stop thinking I might also be writing for a PDP-11 bootloader."

I think you should go to the standards committee with a single proposal, which is that C should stop trying to be portable to weird / old architectures (and people who need them can use weird / old compilers, anyway). Among other things, you can now enable certain types of optimizations if the compiler is permitted to assume that arithmetic is two's-complement and nonaligned reads/writes work and so forth.

>You expect C code to go beyond the territory of the abstract machine. The authors of the standard, quite clearly, do not.

That is 100% wrong.

>Strictly conforming programs are intended to be maximally portable among conforming implementations. Conforming programs may depend upon nonportable features of a conforming implementation.

The whole concept of "undefined behavior" is to cope with the reality that C programs routinely go beyond the bounds of the abstract machine.

> if the compiler is permitted to assume that [...] nonaligned reads/writes work

One of the most popular architectures for "a reasonable UNIX on a reasonable modern machine with a single flat address space for code and data" is the x86, and on it, some nonaligned reads/writes do trap. Certain optimizations can be done only if the compiler is permitted to assume that the data is aligned.

As usual, this is pure handwaving: " certain optimizations ... "

What is your definition of valid? It's not valid by any C standard or common compiler implementation. For the sake of any argument, we should at least agree on a common definition for valid.

As for deleting null checks, time-travelling UB etc. the compiler always assumes the code is valid, bug-free for the compiler-specific definition of valid. This is at least the standard definition but it can be expanded by flags and extensions. Then they optimize that code without regard to what happens if the code actually had programming bugs.

is k = i+j valid C? Can it be translated sensibly to add i,j; jump on overflow to random; store k; ? How about sometimes omitting the jump to random and sometimes not?

Signed integer overflow is undefined, so the only obligation is that the code operates correctly when signed integer overflow doesn't happen. So, yes all those options are permissible, because as far as the C standard specifies, it's "add i,j; if false jump to random; store k".

If you want to add a definition for signed integer overflow (as C++ is considering, see http://wg21.link/P0907r0 ) then it would be defined and the compiler would no longer get to consider "if signed overflow" and "if false" the same.

I 100% doubt that that Ritchie would have agreed. This is the existing interpretation of the standard, which is exactly what I propose to change. I believe the standard interpretation has strayed from both the language design and the objectives of the language.

> But the compiler can't break the code by deleting a perfectly conforming null check on the theory that a previous dereference means that the pointer is not null.

Why is this different from letting the compiler optimize out the second check here?

    int foo(unsigned int i) {
        if (i < 5)
            return this();
        if (i < 4)
            return that();
        return those();
    }

The C standard knows that NULL is special, a marker value for an invalid pointer. (The implementation does not have to translate it as the pointer with numeric value zero; the abstract machine just needs some value.) Absent an Optional/Maybe/etc. type, C needs some invalid pointer.

What about the following—are you okay with compilers optimizing it?

    struct pointer {
        int *value;
        char valid;
    }

    void *deref(struct pointer p) {
        if (!p.valid)
            abort();
        return *p.value;
    }

    void stuff(struct pointer p) {
        int n = deref(p);
        if (!p.valid) {
            fprintf(stderr, "Hey, that pointer wasn't valid!\n");
            return;
        ...
    }

No NULLs involved.

> The original Bourne shell used signal to catch memory faults so it could operate dynamic paging! If your OS/implementation permits, C is supposed to allow you do do things like that.

I'd believe that (especially given the state of optimizers in Bourne's era) C does allow you to do things like this. I'd also believe that with sufficient -fno-unwanted-cleverness flags. C is the best way to do things like this.

But asking C to be designed to support things like this is quite a change. I get that this is exactly the change you're pushing for, but, the only way it can work is if the C abstract machine becomes hardware-dependent enough that you can embed platform assumptions in your C—and so C is no longer a "portable assembler."

There's precedent for this. One that comes to mind is the ability to cast a data pointer to a function pointer (which doesn't have to be valid; the abstract machine doesn't know if your physical machine uses different address spaces and different representations for the two, and even the brand new architecture WebAssembly uses different address spaces, but compatible representations). dlsym() implicitly requires this, and POSIX.1-2013 finally made an explicit requirement that a C implementation conforming to POSIX must define it in a meaningful way. http://pubs.opengroup.org/onlinepubs/9699919799/functions/dl...

I would certainly support a variant of C that did things like assume a flat address space, validity of all pointer values besides NULL (and an expectation that signals can catch and fix invalid pointer dereferences), char = unsigned char, 8-bit bytes, two's complement arithmetic, etc. It would not support every architecture C supports. It wouldn't be a good fit as a C standard, but as a variant for people who are happy to never target segmented real-mode x86 or the PDP-11, it seems pretty great.

There is nothing in what I have proposed that requires assuming a flat address space or that pointers can catch and fix invalid pointer dereferences etc.

You can fulfill (1) not too hard.

First, the compiler is allowed to compile your program as-if all values of all variables are such that undefined behaviour doesn't happen, but isn't allowed to extract value bounds based on that for the purposes of optimising across more than one expression. So the compiler is allowed to assume pointers aren't NULL where they are dereferenced, because that is undefined behaviour and the compiler either has to assume the pointer isn't NULL, or require proof from the programmer, or refuse to compile any C program with pointer dereferencing because it is potentially invalid C. However, it is not allowed to assume that because a pointer was dereferenced, that it is not NULL. This restriction should be tight enough that

    int a, b;
    ... set a and b ...
    if (a > 0 && b > 0 && (a+b)&(int)(-1) > a) {
        ...
    } else {
        ...
    }

is compiled to something like

    mov eax a
    add eax b
    cmp eax a
    jle .else

Second, you can define "trivially compiled C" for every platform as a set of substitution rules that transform every C operation into machine instructions without any optimization. Such a trivial compilation would have every variable write correspond to a memory write, keep no variables in registers, always compile the same expression to the exact same machine code (except for memory addresses of variables involved), never inline functions etc. But it would still be allowed to e.g. put 32-bit integers in 64-bit registers on the basis that int operations are assumed not to overflow. The committee should define that for every supported platform as a reference C compiler, then require that C compilation produce machine code with observable side-effects for single-threaded execution equivalent to the reference trivially compiled C.

Isn't the reference compiler with trivial compilation equivalent to trying to make all UB implementation-defined where the implementation is the "trivial compilation"? For example this would preclude optimization based on aliasing rules which a lot of tight loops rely on.

  float max (float f[], int length, int* max_index) {
    float max_value = -FLT_MAX;
    *max_index = -1;
    for (int i = 0; i < length; i++) {
      if (max_value < f[i]) {
         *max_index= i;
         max_value = f[i];
      }
    }
    return max_value;
  }

Take the code above. It obviously has a well-defined trivial compilation implementation even for cases where max_index aliases an element of the f[] array. There is a good reason that implementations are allowed to assume that doesn't happen: it produces better code in the case where the program has no bugs. Otherwise even at -O3, the implementation would have to read f[i] twice from memory as the value might have changed when *max_index was written if it wants the same behavior as the "trivial compilation" implementation.

> Second, you can define "trivially compiled C" for every platform as a set of substitution rules that transform every C operation into machine instructions without any optimization. Such a trivial compilation would have every variable write correspond to a memory write, keep no variables in registers, always compile the same expression to the exact same machine code (except for memory addresses of variables involved), never inline functions etc. But it would still be allowed to e.g. put 32-bit integers in 64-bit registers on the basis that int operations are assumed not to overflow. The committee should define that for every supported platform as a reference C compiler, then require that C compilation produce machine code with observable side-effects for single-threaded execution equivalent to the reference trivially compiled C.

Such an approach would preclude putting any variable in a register if there is any not-provably-valid pointer store anywhere in the program.

Feel free to try, but I guarantee you that for most non trivial optimization it's going to be easy to find a piece of code that is UB today and where the optimization is observably different from the reference compilation.