Hacker News Reader

Comment by leni536 | Hacker News Reader

13. But if the line with UB isn't executed, then the program will work normally as if the UB wasn't there.
14. Okay, but if the line with UB is unreachable (dead) code, then it's as if the UB wasn't there.
15. If the line with UB is unreachable code, then the program won't crash because of the UB.

16. If the line with UB is unreachable code, then the program will at least stop running somehow and at some point.

This is nonsense. The line with UB has to be reached for the execution to be undefined.

View on HN

You have to understand that in the modern understanding of UB as applied by compiler writers, the compiler has every right to assume the program never triggers UB. This means that lines which would be UB if a variable had certain values can be used as proof that the variable doesn't have those values, thereby eliminating checks.

For example, if a program looks like this:

  void foo(int* const p) {
    if (p!=NULL) {
      bar(p);
    }
    *p = 1; //this line would be UB if p could be NULL
    //so we are free to assume p is not NULL in this scope
  }

It will very likely be optimized to this:

  void foo(int* const p) {
    bar(p);
    *p = 1;
  }

And even if bar() itself had a line checking if p was not NULL, that will get ellided as well if bar() gets inlined.

This is a good example of how UB on a later line can have an impact on earlier lines, or even in other places in the code.

Note that it's not executions which trigger UB, it is source code programs that do.

Edit: fixed const pointer syntax.

I don't think this proves the point, because foo() will not invoke UB unless it is called with a NULL argument.

It is true that when foo() is called with a NULL argument, the UB will be realized before bar() has had a chance to run (EDIT: this doesn't actually appear to be true for the given code sample, neither Clang nor GCC elide this NULL check: https://godbolt.org/z/v9v74c3jd, which makes sense as bar() could call exit()).

> Note that it's not executions which trigger UB, it is source code programs that do.

For C, I think this interpretation is directly contradicted by DR #109: https://www.open-std.org/jtc1/sc22/wg14/docs/rr/dr_109.html

> Furthermore, if every possible execution of a given program would result in undefined behavior, the given program is not strictly conforming. A conforming implementation must not fail to translate a strictly conforming program simply because some possible execution of that program would result in undefined behavior. Because foo might never be called, the example given must be successfully translated by a conforming implementation.

> It is true that when foo() is called with a NULL argument, the UB will be realized before bar() has had a chance to run. But the line with UB has already been proven reachable prior to the actual dereference, so the UB has in a sense already been invoked.

The point of those numbered lines was to refer to how people normally think about UB. Someone seeing that function may be tempted to say that it's not UB to call with a NULL value as long as the dereference doesn't happen (say, bar() could call exit() or it could run an infinite loop). What you're saying is exactly what the article is saying: the fact that a line with UB is unreachable in practice doesn't mean that it can't affect your program.

> For C, I think this interpretation is directly contradicted by DR #109: https://www.open-std.org/jtc1/sc22/wg14/docs/rr/dr_109.html

The standard talks about executions in the sense of theoretical executions by the C abstract machine, not actual executions of the compiled binary. I thought the other comment was rendering to the latter notion of execution, but perhaps I was wrong and it was also talking about the former.

> Someone seeing that function may be tempted to say that it's not UB to call with a NULL value as long as the dereference doesn't happen (say, bar() could call exit() or it could run an infinite loop).

An infinite loop is UB for precisely this reason: https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1528.htm So an infinite loop cannot prevent the invocation of UB, because an infinite loop is itself UB.

I would expect that a call to exit() inside bar() would prevent eliding of the NULL check. If the program calls exit() before the dereference, it does not invoke UB and therefore should run correctly. I tried your example and Clang and GCC do not actually elide the NULL check in this case, probably for this reason: https://godbolt.org/z/cnWPz3o59

> The standard talks about executions in the sense of theoretical executions by the C abstract machine, not actual executions of the compiled binary. I thought the other comment was rendering to the latter notion of execution, but perhaps I was wrong and it was also talking about the former.

I don't see how this would change the analysis. Running the binary triggers actual executions of both the abstract machine and the physical binary.

The fact that bar could exit or not return doesn't matter (although it was indeed my initial line of reasoning) as if the value is null bar won't be called and UB happens; hence the value can't be null and bar can be called unconditionally. The value is still dereferenced only after calling bar.

Still gcc doesn't optimize the check away so it is possible there is some other line of reasoning that prevents the transformation.

Btw this is a nice example how this stuff is subtle.

My first answer was going to be that the transformation is not allowed, but then I thought about it more.

I couldn't get gcc to break it either though. Either it misses the optimization or tries to be conservative with reordering UB with side effects.

Can you just check, I don't think the line *p=1 will even compile given the definition of p

Oops, I got the const pointer syntax wrong, fixed now.

Yes, thank you. It's clear these points are incorrect if you consider the purpose of undefined behavior. Compilers are allowed to assume undefined behavior is never invoked (which may be useful for optimization and other reasons); it is a promise from the programmer that they will not invoke undefined behavior specifically so that the compiler may assume they don't. Things are often made undefined behavior because the assumption is useful, but hard or impossible to prove in general with static analysis, so it requires a programmer who can consider the context of the code to assure the assumption always holds. If undefined behavior is invoked, some of the compiler's assumptions are wrong, so anything could happen (see the "principle of explosion"[1]). If no undefined behavior is invoked, all of the compiler's assumptions are correct, so the program must behave correctly.

For example, imagine a C programmer writes a function that adds two `int` values. Hypothetically, with some inputs, the addition may overflow. That would be undefined behavior, so the compiler assumes the function is never called with such inputs, and optimizes accordingly. The programmer knows this, and assures the function is never called with those inputs. Since the only assumption the compiler made was that the function wasn't called with input which would cause the addition to overflow, and the programmer assured that assumption is correct, the function always behaves correctly.

Consider if the same function's inputs were provided at runtime from stdin. The behavior of the whole program is undefined if invalid inputs are given, but if only valid inputs are given, the program must behave correctly.

[1]: https://en.wikipedia.org/wiki/Principle_of_explosion

Now look at a large code base, with lots of checks for inputs. With O0 it's usually straight-forward to read, but with heavy optimizations applied it can become a real nightmare. And in that scenario all it takes is some reordering of the UB before the DCE pass can prove the code to be unreachable (which might not happen on the first DCE pass, because the value analysis/constant propagation didn't work its magic, yet). Also static program analyses can be both forward and backward.

I'm afraid it's not nonsense, that's why it's a common misunderstanding ;)

> This is nonsense. The line with UB has to be reached for the execution to be undefined.

Check the footnote at item 14, it links to a page which shows one example of how a line with UB can be reached (basically: the optimizer can reorder the code so that parts of the line with UB will run much earlier than you'd expect).

I checked the footnote. It describes a case where invoking UB (transmuting "3" to a bool) can cause dead code to become live. But transmuting "3" to a bool is itself UB. So this fails to prove that execution becomes undefined without reaching a line containing UB.

UB "making dead code live again" is not an example of UB in dead code making the execution undefined.

Yes UB in live code can have surprising effects, including executing dead code.

Unless your code is actually commented out (actually dropped from the program), it can still (maybe) execute.

I think the main reason for this is an if(testSomeState()) { //code with UB } block being optimized to just //code with UB.

Functions which are unreachable, maybe I agree, they can't be executed (without UB somewhere in reachable code). I'm not sure that's true though - if you have UB in your hardware (not your code), you can still execute that code. This is why (at least I was taught) never to leave dead code around. There's this better thing for that called source control you may have heard of...

IF you have perfect hardware, and IF you have perfect logic/compiler and IF you have no UB in your program, then maybe you can guarantee that dead code is really dead, but I'm not really sure you want to heavily define dead code like that.

Just remove it. Especially if it has UB in it to cause more fun bugs...

If UB happens¹, anything can happen. So if the check can only happen after UB, or leads to UB, it can be removed. That isn't the case in your example – testSomeState() can return false (and if it can't, it getting optimized out is unrelated do the code it guards). Points 14-16 from the article are just nonsense, UB is a runtime concept and dead code doesn't run unless you already triggered UB¹.

¹or is guaranteed to happen in the future

That example specifically states:

> Right now, we have the fundamental principle that dead code cannot affect program behavior.

"The line with UB" becomes a very vague notion well before the program even executes. You can see this by dumping the disassembly of your program. The compiler can determine when values are defined and used and will emit code that satisfies the semantics of your program (according to the language specification). This often means that expressions within the same statement get evaluated at significantly different times, hoisted outside of loops, etc.

The assembly dump does not matter for this analysis (except for finding buggy compilers!) - the C abstract machine itself applies all side-effects before each sequence point.

Can someone with more knowledge chip in? If I define

  void bar(int* const p, int n) {
    for (int i=0; i<n; ++i) {
      int m = *p
      // other code (without UB)
    }
  }

it might get optimized via loop-invariant code motion to

  void bar(int* const p, int n) {
    int m = *p
    for (int i=0; i<n; ++i) {
      // other code (without UB)
    }
  }

so it could still be UB when called with p=NULL and n=0, right?

Edit: Oops, in the previous version I used a write instead of a read on *p, making the optimization invalid.

No, that transformation is straight-up buggy unless the compiler can also prove that n > 0 (ie by inlining the bar() function into a context where n is always positive).

If you had *p == 0 before calling bar(p, 0) then *p had better not be 1 after!

The first form has no undefined behavior. Since p may be NULL, in general the compiler is not allowed to make that transformation unless it can prove bar never gets called with p=NULL and n=0 (which it probably can't).

If the compiler has some special knowledge of the target architecture which makes the second form behave as if the first form was executed (such as if NULL is a valid address on the target architecture), it may make the transformation, but that still wouldn't cause undefined behavior, because it must behave as if it had the first form.

Thank you for clarifying! It's definitely relieving, after reading the post, to know that there is some limit for undefined behavior.

Everyone's getting confused about the word "reach". If the execution of a program triggers UB at any point then its behavior is undefined at all points, even before the UB was triggered. But the compiler does have to respect and preserve the behavior of any completely UB-free execution of your program, even if other executions (say with different input) could trigger UB.

So we could say, unreachable UB is fine, but if you do reach it, then it doesn't matter when you reached it.

Point 14 explicitly says UB in dead code.

The implicit assumption is no UB in live code, otherwise the UB in dead code is a red herring.

So the UB is never reached, by the definition of dead code.

Unreachable UB is fine.

If this wasn't the intended message of point 14, then it's phrased wrong.

Yeah the format of the article makes this mistake extra confusing. The statement in point 14 is in fact true, but the whole premise is that all these statements are supposed to be false.

Looks like you believe in some falsehoods most programmers believe about UB. Well, you are not alone.

No, the commenter is right, at least for Rust (can't say for other languages). UB is a property of a particular execution of a program, it happens when code is executed on the abstract machine. As the blog post linked from the article (point 14, footnote 6) states:

> Right now, we have the fundamental principle that dead code cannot affect program behavior.

On C UB is a property of any code, reachable or not, just like the article's references explain.

Why are people fighting this?

And yes, Rust is much more reasonable about it.

How do you decide if i+1 is UB or not, unless the abstract machine reaches that line with a given value of i?

If you write i+1 anywhere on your code, the compiler is free to assume i is different from the maxumim value and rewrite your code with that in mind.

If you are not satisfied, you can read the article's references (there are 2 for unreacheable code). Or any article about UB here for the last 20 years.

No it doesn't. Modern processors do out-of-order execution, so your program might be doing UB before you expect.

That's sounds plausible, but isn't. First of all, out-of-order execution has nothing to do with unreachable core - it just means that reachable code sometimes gets executed in a different order than the binary shows. It is speculative execution which can lead to unreachable code actually being executed.

However, even when processors execute code speculatively, they guarantee that no observable effects of executing that code will happen. So, if you have something like `if false {*NULL=7/0}`, the processor might attempt to execute that line speculatively, but it will revert any change it made, and it will not trap regardless of any other flags.

Out-of-order execution isn't the reason for this. The C standard assumes an abstract machine that allows OoOE, of course, but even with strict in-order hardware UB can hit you at any time, even before you'd think it could. That is because the C standard doesn't limit UB to any constraints like "following lines" or "subsequently executed instructions". Independent of the hardware, the compiler is allowed quite a bit of reordering of instructions. The standard just requires that (some) effects of those executions are ordered as written, but that doesn't include UB.

So if you have UB in your future path of execution, the compiler might just do whatever _right now_.

It still has to be executed by the abstract machine for the given set inputs for the whole execution to be undefined.

You are right that once the execution is undefined, you can't reason about the behavior. This includes ordering of side effects, or side effects od operations occurring before the line with UB.

But uttering UB in dead code making execution UB is utter nonsense. Otherwise any execution of any program that just utters __builtin_unreachable() would be undefined.

No, no, no. UB is a global property of your program. "All bets are off" even at compile time.

"Anything at all can happen; the Standard imposes no requirements. The program may fail to compile, or it may execute incorrectly (either crashing or silently generating incorrect results), or it may fortuitously do exactly what the programmer intended."

https://blog.regehr.org/archives/213

A program like

  int main(int argc, char **argv) {
    int a = atoi(argv[1]);
    int b = atoi(argv[2]);
    return a + b;
  }

contains signed integer overflow in some executions but not others. Can you explain what effect the counterfactual signed integer overflow is allowed to have in executions that do not contain signed integer overflow?

UB is typically a property of the execution of a program. A program may bump into UB for one set of inputs, but not for an other set.

That is a misconception.

"If any step in a program’s execution has undefined behavior, then the entire execution is without meaning. This is important: it’s not that evaluating (1<<32) has an unpredictable result, but rather that the entire execution of a program that evaluates this expression is meaningless. Also, it’s not that the execution is meaningful up to the point where undefined behavior happens: the bad effects can actually precede the undefined operation."

I agree, but this doesn't refute what I wrote.

"If any step in a program’s execution has undefined behavior, then the entire execution is without meaning..."

Yes. So UB is a property of a given execition, not a static property of the program itself.

I don't argue that you can reason about the behavior of any part of the execution, once it evaluates operations with UB.

once and before.

If a given execution would eventually lead to UB, then it retroactively it cannot be reasoned about.

This time traveling behavior is what is confusing people in thinking that if any execution is UB then all possible executions are UB.

I think this hits the nail on the head.

Many people in this thread are confused and think that unreachable UB (either statically or dynamically unreachable) compromises the entire program. This is not true, but your comment helps me better understand how people reached this conclusion.

Reachable UB (either provably reached at compile time or dynamically reached at runtime) can retroactively invalidate the correctness of previous statements. But this does not mean that unreachable UB compromises the correctness of well-defined executions.

You are indeed correct. I would add that there are some instances of UB that actually UB at translation time: for example ODR violations and some preprocessor dark corners. At least the latter is getting stamped out.

The C++ standard calls these "ill-formed, no dioagnosrics required" instead of UB, although it's not always consistent. It is indeed more or less "translation-time UB". The difference is exactly that affected lines don't need to be in the execution path to make all executions undefined, and that the compiler/linker may fail the translation.

UB is a property of the source code, or more specifically a property of how source code should be compiled into machine code. It means that there is no constraint on the machine code which will be produced if your source code has certain properties.

Reply on news.ycombinator.com