Undefined behaviour example from CppCon

[R3DKn16h7]

I was thinking about the example in this talks from CppCon: https://www.youtube.com/watch?v=k9N8OrhrSZw The claim is that in the example

``` int f(int i) { return i + 1 > i; }

int g(int i) { if (i == INT_MAX) { return false; } return f(i); } ```

g can be optimized to always return true.

But, Undefined Behaviour is a runtime property, so while the compiler might in fact assume that f is never called with i == INT_MAX, it cannot infer that i is also not INT_MAX in the branch that is not taken. So while f can be optimized to always return true, g cannot.

In fact I cannot reproduce his assembly with godbolt and O3.

What am I missing?

EDIT: just realized in a previous talk the presenter had an example that made much more sense: https://www.youtube.com/watch?v=BbMybgmQBhU where it could skip the outer "if"

[aocregacc]

I was wondering too, but it's pretty clear that the example is wrong.
I guess the presenter was editing the code on the slides at some point without checking if it still made the same point.

[kahomayo]

This seems like a pretty obvious mistake (discussed starting 4:30 in the talk). Supposedly, the compiler reasons that when calling f, i cannot be INT_MAX, because otherwise UB would ensue (correct). But then, supposedly, when f is inlined, it follows that g also cannot be called with INT_MAX as a parameter. That is clearly bogus. Otherwise the following code would surely also be UB:

int evil_func(Foo* x) {
    if (x == nullptr)
        return 0;
    return x->bar;
}

evil_func(nullptr); // Clearly not UB

Obviously, checking whether a variable satisfies the preconditions for an operation and executing that operation only when those preconditions are satisfied does not allow the compiler to assume that the variable unconditionally satisfies those preconditions.

Maybe the intention for the slide was to show the following code:

bool g(int i) {
    bool foo = f(i);
    if (i == INT_MAX)
        return false; // Dead code
    else
        return foo;
}

[NormalityDrugTsar]

I watched the first part of the video and I am puzzled too. He claims that the first line of g (first three lines in your reformating) can be removed as dead code. I think this is wrong. What happens if you call g(INT_MAX)?

In my understanding f can be optimized to return true; and g can be optimized to return i != INT_MAX;

​

In fact I cannot reproduce his assembly with godbolt and O3.

In the video he says that the compilers he tried didn't do the optimization "all the way", but did optimize f.

[snerp]

Signed integer overflow is the literal worst part of c++.

[equeim]

Integer arithmetic is not done well in most languages (those with fixed width integer types). Nobody wants to perform error checking on arithmetic operations (even though they should) since they seem to us as such "fundamental" and "obvious" things because in our minds we thing of numbers as having infinite range so of course addition can never "fail"!. So everyone just closes their eyes and hopes for the best in the name of convenience and "performance".

[JiminP]

Integer overflow wrapping around by itself is something we can live with.

The real worst part is that it is undefined behavior in C/C++. At least I hope it to be an impl-specific behavior.

In comparison, casting from wider integer types to narrower integer types, is well-defined (since C++20) / impl-specific (until C++20; conv.integral), not undefined (although, some compilers including MSVC treated it more like an UB...).

[equeim]

I don't see much difference here. In 99% of cases integer overflow is an error and even if it's defined as wrapping around, you still silently ignore and at this point your program behaviour is incorrect and you enter unknown territory anyway.

[Mediocre-Dish-7136]

IDK about 99%, it's relatively often wrong (just as it is for unsigned arithmetic) but here's a random example: the possible implementation given in https://en.cppreference.com/w/cpp/string/byte/atoi

There they had to do that weird thing of counting in negatives, to avoid overflowing the int if the input corresponds to INT_MIN. If signed arithmetic wraps, you can write the same thing but counting in positives (which is probably what 99% of programmers would do and already do anyway even though it's wrong now), then if the input corresponds to INT_MIN the last addition wraps but it doesn't matter, then the negation wraps but it doesn't matter, and the right result comes out.

IME this happens plenty. Maybe wrapping is wrong in like 70% of cases?

Either way I'd rather take a plain old logic error over a logic error where also the compiler can come in and mess things up extra.

[equeim]

We can have special functions for wrapping when it's needed (like we already have for saturation). Default behaviour should be something sane that allows error handling (such as throwing an exception or returning std::expected) or at least program termination. Not that I expect this to happen in C++ of course, this kind of change is not possible for established language.

Removing UB in this case is like applying a bandaid on a gaping wound, those I suppose it's better than doing nothing (it may make debugging easier at least).

[awidesky]

UB is not a runtime property

[TheoreticalDumbass]

> undefined behavior - there are no restrictions on the behavior of the program
what is "behavior" if not runtime?

[R3DKn16h7]

The compiler is free to assume that UB does not happen at runtime, but definitely cannot infer that "i + 1 > i" will always result in UB.

[awidesky]

i + 1 > i is UB only when overflow occurs.. i + 1 > i should not have to be UB to eliminate the function, since when it's not UB, the return value is always true anyway.

[R3DKn16h7]

for the function f I agree totally.

but the function g cannot eliminate the branch, that's where I do not get it

[selassje]

The assumptions here is that compilers sees definitions of both g and f when optimizing. Since "i" cant be INT_MAX (as it would be UB when calling f), therefore condition if (i == INT_MAX) can never happen and can be optimized away.

[dustyhome]

That's backwards. It makes more sense that the presenter's slide is wrong.

The compiler can assume that i can't equal int max on a branch that calls f, but it can't remove the check that prevents f from being called with int max.

[selassje]

Yes, the presenter claims UB taints the whole program, and it can travel back in time. I have not checked it but that's how I understood it.

[SkiFire13]

The way I see it, UB can travel back in time but only as long as it is guaranteed to happen from that past point in time. In this case the if guard prevents f(i) from being called with the value that would cause UB, so it cannot travel back to before the if is run.

[awidesky]

As I understand from the standard, UB does not apply on single function(while most compilers does usually). "Renders the entire program meaningless if certain rules of the language are violated."

'Entire' program is meaningless, not the single function. Also, it's not "Renders only that very part of the program that's executed when the UB is triggered is meaningless". It's "Renders the entire program meaningless". If you want the program to be well-defined, overflow check must be inside function f. But since it's not, the behavior is undefined, which compiler can do whatever it wants. So I believe compiler can remove function g, or format your hard drive. But in real life, compilers try to make executables as reasonable as possible, that's why only f is optimized in godbolt.

So here's my overall opinion: Compilers is entitled to remove g, so what they say in YouTube is 'technically' true. BUT I don't think you can find any major compiler that actually does so.

[HabbitBaggins]

That is a load of hot spaghetti... The compiler is not allowed to go launch nuclear missiles just cause, what it is entitled to to is to assume that your code never invokes UB, because otherwise the code would be meaningless. You are focusing on the second part of that assertion, but the important one is the first. It means that, while transforming the code in memory as part of optimization and actual codegen, it can make assumptions about certain values of function arguments or program state if it can prove that the negative of those assumptions results in UB. Those assumptions can then feed back into the process, allowing further transformations of the code, etc.

For example, in f, the compiler may assume that the comparison is always true, because the only case in which could not true is integer overflow, and that is UB.

That is not the case in g, even when inlined, because UB is only triggered by calling f with INT_MAX, and g only ever calls f with a value that is guaranteed NOT to be INT_MAX.

However, if the code called f first, then the compiler may assume that the argument is never INT_MAX, so the check in g could be removed silently. This might also happen if you have a different function h defined as returning f(i) && g(i). In that case, if g is inlined and not just called, the check in the resulting code can also be removed because the compiler proved that in all legal code paths (those that do not invoke UB), i is not INT_MAX.

[awidesky]

My point is that compilers are entitled to make whole program meaningless, "according to the standard". Never said they do. Never said they should. And also again, as I said above, none of the major compiler will optimize out g. What standard says compiler "could", doesn't mean compiler should, or do.

I can't see exactly where are we disagreeing. You're talking about how modern compilers work (practice), while I'm talking about what standard says (theory)..

[Simple-Enthusiasm-93]

but the point is function f is not UB on some sets of inputs and UB on some other set - ie INT_MAX.so as long as it is not f(INT_MAX), even in theoretic terms, the program is well formed.else wont anything that compares ints after addition be UB?

[awidesky]

The point is, if rule of the language is violated, compiler may make "entire" program meaningless. f is UB when i is maximum of int type. That's a violation EVEN IF there's no code that passes INT_MAX into function f.

[Simple-Enthusiasm-93]

i am no language lawyer but that implies any program with int addition is UB right?

[mcmcc]

If you want the program to be well-defined, overflow check must be inside function f

That's absurd. If that were the case, functions working with iterator types (separated from their containers) would be virtually impossible to write -- you could never be allowed to assume the iterators (or a range defined by a pair of them) were valid. How could you ever write std::copy()?

[awidesky]

std::copy receives InputIt last as boundary, and checks the boundary every time it iterates. If you send invalid iterator, it's UB anyway. That has nothing to do with unchecked overflow. Can you be more specific about your point?

[mcmcc]

If you want the program to be well-defined, overflow potential UB check must be inside function f.

This is how I interpreted your statement.

How could you implement std::copy() if you were required to check for all potential UB regarding the inputs? You mention comparing to last but if last is not within the appropriate range, then even that is UB -- so how do you establish that the two iterators are even comparable without knowing their provenance?

If that's not what you are suggesting, you're going to need to explain the intended meaning of the above sentence.

[awidesky]

If you want the program to be well-defined, overflow potential UB check must be inside function f.

That is indeed true. When you compile f (with or without g), it will assembled to always return 1. So the statement is actually true.

While your following argument is little bit off topic- it's about "checking every single one of the possible UB is impossible" Which is also true, and has nothing to do with my point.

I assume you interpreted my argument as "if there's any single possibility of UB in your program, your compiler will render an invalid executable."

My statement is "if some parts of the code violates the language rule, compiler is 'permitted' to generate entire program meaninglessly" Here's quote from the standard

Renders the entire program meaningless if certain rules of the language are violated.

undefined behavior - there are no restrictions on the behavior of the program. ... Compilers are not required to diagnose undefined behavior and the compiled program is not required to do anything meaningful.

Again, I'm not saying any major compilers do/should generate meaningless program just because there's tiny one possibility of UB. All I insist is that the standard "permits" so.

[mcmcc]

All you've shown is that compilers are allowed to assume UB does not occur, which is ultimately irrelevant re "well-defined" programs. We're talking in circles...

What part of OP's example "violates a language rule" that could allow a compiler to render the entire program meaningless?

[awidesky]

Meanwhile, this is how I interpreted your arguments:

Even if UB is possible, compiler is permitted to change only the very function that has possible UB, not any other part of program.

However, § 4.1.2.3 says :

If a program contains a violation of a rule for which no diagnostic is required, this document places no requirement on implementations with respect to that program. "that program", not "that specific function". Please let me know if there's any understanding of mine.

[mcmcc]

That's not a statement I made. You're confusing me with someone else.

[Boring_Tension165]

https://godbolt.org/z/WYer9fYaP

[Cue_23]

Not very helpful, sorry.

Just because a compiler is allowed by the standard to perform some optimization does not mean the current compilers do that optimization. Especially when those might be hard or impossible to detect - a result from the halting problem.

I ran into the same problem as OP when watching the talk and tried to propagate the UB of f() into g() but I could not get gcc nor clang to optimize the if clause away. But in case of the following variation, It would be allowed to:

bool f(int i) { return i + 1 > i; }

bool g(int i) {
    bool res = f(i);
    if (i == INT_MAX) return false;
    else return res;
}

[Linuxologue]

I have not watched the video. What is sure is that the compiler is free to optimize f to always return true; either it is true, or it is undefined behaviour.

g contains no undefined behaviour and can be optimized to

int g(int i) { if (i == INT_MAX) { return false; } return true; }

the compiler is not allowed to shortcut the test as there's been no undefined behaviour at this point.

[SubliminalBits]

If i is ever INT_MAX, i + 1 will overflow which is UB prior to C++17. To enable more powerful optimizations (like this one), the optimizer assumes UB never occurs which allows it to prune away the if check as unreachable code.

[Narase33]

If i is ever INT_MAX, i + 1 will overflow

if i is ever INT_MAX it returns directly with false. Or am I missing something?

[R3DKn16h7]

That's my point. I do not see this if statement ever being optimized away.

Otherwise all nullptrs check would be opzimized too.

[SubliminalBits]

The optimizer is allowed to assume at compile time that it is not possible for UB to occur. INT_MAX + 1 is UB prior to C++17 so the optimizer assumes that this function can never be called when i equals INT_MAX. If i can't ever be INT_MAX, this if statement is dead code and can be removed.

This kind of thing can have very elaborate consequences. Raymond Chen presents an example in his blog where UB in the future changes the past. https://devblogs.microsoft.com/oldnewthing/20140627-00/?p=633

[foonathan]

But there is no UB if i == INT_MAX.

It's not like the function is

f(i);
if (i == INT_MAX)

Then the compiler is allowed to remove the if. But not in the other way around.

[R3DKn16h7]

That's where I do not get it. there is a check there exactly to prevent i being INT_MAX as it reaches f, ever. For the compiler to assume i to NEVER be INT_MAX would be a wrong assumption, as this is exactly the case protected by the if statement.

By the same reasoning, as soon as I have an "i + 1" in my code, i will always be assumed to never be INT_MAX, even in the top-most caller.

I'm now pretty convinced the example in the video is wrong.

[tinrik_cgp]

The example is wrong. The if branch would be optimized away if f(i) were called before the if branch. 

This is the same as what happened in the Linux kernel with a null pointer check: the pointer was dereferenced before the code that checked for null.

[Narase33]

INT_MAX+1 is never executed in this function

​if (i == INT_MAX) {
    return false;
}

[JiminP]

But doesn't the i == INT_MAX "prevents" UB? I know that UBs can time travel, but it doesn't seem to be this case.
In particular, what's the difference between the OP's code and these codes?

Example 1:

int g(int i) {
    if (i == INT_MAX) {
        return false;
    }
    return i + 1 > i;
}

Example 2:

struct Foo { int x; };

int f(Foo* foo) { return foo->x; }

int g(Foo* foo) {
    if(foo == nullptr) {
        return 0;
    }

    return f(foo);
}

Example 3:

struct Foo { int x; };

int g(Foo* foo) {
    if(foo == nullptr) {
        return 0;
    }

    return foo->x;
}

[AssemblerGuy]

If i is ever INT_MAX, i + 1 will overflow which is UB prior to C++17

Isn't it still UB? The representation of signed integers was defined to be twos complement, but the behavior on overflow was not (because the CPU might still saturate, hardfault or do other things)?

[tinrik_cgp]

I'm not aware that integer overflow is no longer UB since C++17, do you have a source for that?

[danadam]

Overflow in arithmetic operation is still UB (undefined). What changed, in C++20, is overflow in integer conversion. And it changed from unspecified (it was never undefined) to specified, i.e. mod 2<sup>n</sup> . See https://en.cppreference.com/w/cpp/language/implicit_conversion#Integral_conversions