Undefined behavior in C is a reading error • Hacker News Board

Re: Undefined behavior in C is a reading error

#211

Post by bregma » Thu, May 20, 2021, 9:03 PM UTC

tsimionescu wrote: post #206

layer8 wrote: post #149

Because there seems to be some confusion in this thread: - "Implementation-defined behavior" means that the C standard specifies the allowable behaviors that a C implementation must choose from, and the implementation must document its particular choice. - "Unspecified behavior" means that the C standard places no particular restrictions on the behavior, but a C implementation must pick a behavior and document its ch…

I would note that the article is explicitly contesting the definition of UB that you are giving here (though you are absolutely right that this is the de facto definition used by all major compilers, and the commtitee). Basically the article is arguing that UB should be similar to Unspecified behavior - behavior that the implementation leaves up to the hardware and/or OS. I'm not sure where I fall to this issue, thou…

from ISO/IEC 9899:2011 "Programming Languages -- C"

    3.4.3

    1 undefined behavior behavior, upon use of a nonportable or erroneous program   construct or of erroneous data, for which this International Standard imposes no requirements

    2 NOTE Possible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message).

It doesn't look like a leap to go from this definition to that of ignoring the situation completely with unpredictable results.

Re: Undefined behavior in C is a reading error

#212

Post by Jweb_Guru » Thu, May 20, 2021, 9:08 PM UTC

btilly wrote: post #153

_kst_ wrote: post #31

The author suggests that the text following the definition of "undefined behavior", listing the permitted or possible range of undefined behavior, should be read to restrict the consequences. But the first possibility listed is "ignoring the situation completely with unpredictable results". Surely that covers any possible consequences. The author also says: > Returning a pointer to indeterminate value data, surely a…

The author suggests that the text following the definition of "undefined behavior", listing the permitted or possible range of undefined behavior, should be read to restrict the consequences. But the first possibility listed is "ignoring the situation completely with unpredictable results". Surely that covers any possible consequences. Absolutely not. In the C89 standard, undefined behavior becomes undefined *UPON US…

This is actually desired though, at least by some programs. For example, say you have a function with a very expensive loop that repeatedly performs a null check and then executes some extra code if it's null, but never sets the value. This is called from another function which uses the checked value without a null check (proving it's not null) before and after the loop ends. The first function is inlined. You want to tell the compiler not to optimize out the null check and extra code in the loop? Or that it can't optimize stuff out to reuse the value from the first use of the value? If so, what is the compiler allowed to optimize out or reorder?

Now, to see why this might actually produce a bug in working code--say some other thread has access to the not-null value and sets it racily (non-atomically) to null. Or (since most compilers are super conservative about checks of values that escape a function because they can't do proper alias analysis), some code accidentally buffer overflows and updates the pointer to null while intending to do something else. Suddenly, this obvious optimization becomes invalid!

Arguments to the effect of "the compiler shouldn't optimize out that loop due to assuming absence of undefined behavior" are basically arguments for compilers to leave tons of performance on the table, due to the fact that sometimes C programs don't follow the standard (e.g. forgetting to use atomics, or indexing out of bounds). While it's a legitimate argument, I don't think people would be too happy to find their C programs losing to Java in benchmarks on -O3, either.

Re: Undefined behavior in C is a reading error

#213

Post by tsimionescu » Thu, May 20, 2021, 9:08 PM UTC

anarazel wrote: post #161

simias wrote: post #139

Earlier quoted context omitted.

I don't know if there exists a C compiler that leverages this feature but there are ISAs (for instance MIPS) that can trap on signed overflow. The fact that it's UB in C means that you can tell the compiler to generate these exception-generating instructions, which could make some overflow bugs easier to track down without any performance implications. And your compiler would still be 100% compliant with the standard…

That doesn't really help with the compiler optimization aspect : A typical use of the range information would be to unroll the loop - in which case there's no addition to trap on anymore.

To be fair, if you want to make sure that loop is unrolled even in the presence of -fwrapv, writing it as for (int i=0; i < 16; i++) {/* use i+param */} is a very simple change for you to make even today. You'll have to make much uglier changes to code if you're at the level of optimization where loop unrolling really matters for your code on a modern processor.

Re: Undefined behavior in C is a reading error

#214

Post by fiter » Thu, May 20, 2021, 9:09 PM UTC

bregma wrote: post #211

tsimionescu wrote: post #206

Earlier quoted context omitted.

I would note that the article is explicitly contesting the definition of UB that you are giving here (though you are absolutely right that this is the de facto definition used by all major compilers, and the commtitee). Basically the article is arguing that UB should be similar to Unspecified behavior - behavior that the implementation leaves up to the hardware and/or OS. I'm not sure where I fall to this issue, thou…

from ISO/IEC 9899:2011 "Programming Languages -- C" 3.4.3 1 undefined behavior behavior, upon use of a nonportable or erroneous program construct or of erroneous data, for which this International Standard imposes no requirements 2 NOTE Possible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner charac…

This quote is the topic of the original article and the article goes into detail about how it believes the quote should be interpreted.

Re: Undefined behavior in C is a reading error

#215

Post by gameswithgo » Thu, May 20, 2021, 9:09 PM UTC

Lots of us use languages that have no/almost no undefined behavior, it is really weird to see people trying to come up with reasons why this is hard. Perhaps there are still computing environments so slow that undefined behavior still makes sense in C, and C should remain that way. If so, use something with less of this for anything else.

Re: Undefined behavior in C is a reading error

#216

Post by MauranKilom » Thu, May 20, 2021, 9:12 PM UTC

btilly wrote: post #153

_kst_ wrote: post #31

The author suggests that the text following the definition of "undefined behavior", listing the permitted or possible range of undefined behavior, should be read to restrict the consequences. But the first possibility listed is "ignoring the situation completely with unpredictable results". Surely that covers any possible consequences. The author also says: > Returning a pointer to indeterminate value data, surely a…

The author suggests that the text following the definition of "undefined behavior", listing the permitted or possible range of undefined behavior, should be read to restrict the consequences. But the first possibility listed is "ignoring the situation completely with unpredictable results". Surely that covers any possible consequences. Absolutely not. In the C89 standard, undefined behavior becomes undefined *UPON US…

> So, for example, undefined behavior that can be encountered within a loop makes it allowable to simply remove the loop. Even if the undefined behavior is inside of an if that does not happen to evaluate to true with your inputs.

The last sentence is not true. If there is UB inside the if, the compiler may assume that the if condition never evaluates to true (and hence delete that branch of the if), but it may certainly not remove the surrounding loop (unless it can also prove that the condition must be true).

Re: Undefined behavior in C is a reading error

#217

Post by pornel » Thu, May 20, 2021, 9:14 PM UTC

dooglius wrote: post #122

anarazel wrote: post #76

First: I do dislike how hard it is to avoid some UB / how impractical some of the rules are. But I also think a lot of discussions of this topic caricaturize compiler writers to a ridiculous degree. Almost describing them to write optimization passes looking for UB so they can over-optimize something, while cackling loudly in glee about all the programs they can break. The set of people doing so overlaps with the set…

The caricatures are somewhat accurate though, optimizations that look at UB adversarially are never anywhere close to justified. > The set of people doing so overlaps with the set of people complaining that the compiler doesn't optimize their code sufficiently to a significant degree. There's no contradiction here, and the overlap is generally just "people who care". The optimizations that are not safe shouldn't exis…

> optimizations that look at UB adversarially

The whole point is that there isn't such adversarial thing like "we're going to find the UB right there, won't even print a warning about it, and mess up your crappy code, haha!"

Optimizers aren't reasoning about code like people do (start to finish with high-level understanding of the whole function), but rather as series of mostly dumb, mostly isolated small passes, each pass changing one little thing about the code.

It just happens that one pass marks certain instructions as "can't happen" (like the spec says), then another pass simplifies expressions, and then another pass that removes code that doesn't do anything, usually left over from the previous steps. They sometimes combine in an "adversarial" way, but individually each pass is justified and necessary.

Compilers already have lots of different passes. Splitting optimizations into passes is a way to keep complexity closer to O(n) rather than O(n^2), but this architecture makes interactions between passes very delicate and difficult to coordinate, so it's difficult to instrument the data to avoid only cases of annoying UB without pessimizing cases that users want optimized.

Re: Undefined behavior in C is a reading error

#218

Post by btilly » Thu, May 20, 2021, 9:15 PM UTC

aw1621107 wrote: post #200

btilly wrote: post #153

Earlier quoted context omitted.

The author suggests that the text following the definition of "undefined behavior", listing the permitted or possible range of undefined behavior, should be read to restrict the consequences. But the first possibility listed is "ignoring the situation completely with unpredictable results". Surely that covers any possible consequences. Absolutely not. In the C89 standard, undefined behavior becomes undefined *UPON US…

> In the C89 standard, undefined behavior becomes undefined UPON USE OF the thing that is undefined. Is that still the case for current C standards, or did something change in C99/C11?

I don't have the C11 standard. But that part of the passage remained unchanged in C99.

In C89 there was a list of PERMISSIBLE things that compilers could do upon encountering undefined behavior. In C99 that was changed to a list of POSSIBLE things. And compilers have taken full advantage of that.

Re: Undefined behavior in C is a reading error

#219

Post by tsimionescu » Thu, May 20, 2021, 9:16 PM UTC

_kst_ wrote: post #141

msbarnett wrote: post #100

Earlier quoted context omitted.

> does not have a guaranteed loop count with the current rules. The loop body will execute 16 times if param And the standard permits us (among other responses) to ignore undefined behaviour, so it does have a guaranteed loop count under a reading of the standard which the standard specifically and explicitly allows.

No, the standard permits the implementation to ignore the behavior "with unpredictable results". If the value of param is INT_MAX, the behavior of evaluating param + 16 is undefined. It doesn't become defined behavior because a particular implementation makes a particular choice. And the implementation doesn't have to tell you what choice it makes. What the standard means by "ignoring the situation completely" is tha…

> If the value of param is INT_MAX, the behavior of evaluating param + 16 is undefined. It doesn't become defined behavior because a particular implementation makes a particular choice. And the implementation doesn't have to tell you what choice it makes.

The compiler writer argument is as follows:

The program is either UB (when param is INT-MAX - 15 higher) or has exactly 16 iterations. Since we are free to give any semantics to a UB program, it is standard-compliant to always execute 16 times regardless of param's value.

Re: Undefined behavior in C is a reading error

#220

Post by vyodaiken » Thu, May 20, 2021, 9:16 PM UTC

jcranmer wrote: post #20

It's easy to pick on undefined behavior in C when you focus on the more gratuitous undefined behaviors such as signed overflow or oversized shifts. I'm not certain why these are undefined behavior instead of implementation-defined, but my suspicion is that these caused traps on some processors, and traps are inherently undefined behavior. Instead, if you dislike undefined behavior, I challenge you to come up with wor…

"static int y; /* uninitialized / _Bool cond = f(); int x = cond ? 2 : y; / Is it legal to fold this to int x = 2; ? / Hopefully, you'll agree that that is a reasonable optimization. Now consider this code:"
Do not agree. That's not an optimization it's just false reasoning. Reasonable would be to either ignore it so the code depends on the uniitialized data, whatever it is, or to flag an error. Also according to the standard, static variable of arithmetic type are initialized to zero by default so there is no UB at all.
Second example has the same problem.

Third example has, for example, assumptions that C does not let the compiler make e.g. that z is a restricted pointer. Imagine that f(int c) { z = getsamepointer(); z +=1;return *z; }

And none of those optimizations existed in the 1980s.