News for hackers. Stuff that matters.
Re:Undefined behavior in C is a reading error by anarazel on Thursday May 20, 2021 @12:31PM (#27223333)
> For example, if signed integer overflow yielded an unspecified result rather than causing undefined behavior, I wonder if any implementations would be adversely affected.

I suspect so - makes it harder to reason about loop counts because the compiler can't necessarily guarantee that an incremented loop counter won't become negative and thus the loop needs to iterate more.

E.g. something like for (int i=param; i < param + 16; i++) has a guaranteed loop count with the current rules, but not with yours?

That's not an excuse for but having any way to do proper overflowing operations on signed integers though.

Re:Undefined behavior in C is a reading error by not2b on Thursday May 20, 2021 @05:34PM (#27227615)
That's the exact reason why this rule was introduced into the standard: it was so C compilers could compete with Fortran compilers (Fortran has similar rules and at the time they were beating C compilers on equivalent scientific codes by 2-3x).

Fortran has even more restrictive aliasing rules than C: a function is allowed to assume that any two array arguments passed as arguments do not overlap. If they do, the behavior is undefined.

Re:Undefined behavior in C is a reading error by vyodaiken on Friday May 21, 2021 @09:27AM (#27233705)
Exactly - it was done for meaningless benchmarking reasons. C programmers would be happy to use "restrict" as an opt-in for those, but this argument about FORTRAN goes back to the initial days of the standard when Dennis Ritchie had to push "noalias" out of the proposed standard.
Re:Undefined behavior in C is a reading error by Asooka on Thursday May 20, 2021 @01:05PM (#27223859)
> I suspect so - makes it harder to reason about loop counts because the compiler can't necessarily guarantee that an incremented loop counter won't become negative and thus the loop needs to iterate more.

This is a favourite example that gets thrown around, but for all practical loops GCC and clang seem to have no problem even when you compile with -fwrapv

Re:Undefined behavior in C is a reading error by anarazel on Thursday May 20, 2021 @01:12PM (#27223954)
Postgres compiles with fwrapv for many years now, and yes, it does introduce a measurable CPU overhead. Not 10%, but also not just 0.1%.
Re:Undefined behavior in C is a reading error by vyodaiken on Friday May 21, 2021 @09:36AM (#27233793)
link?
Re:Undefined behavior in C is a reading error by anarazel on Friday May 21, 2021 @03:44PM (#27238967)
Locally run benchmarks.
Re:Undefined behavior in C is a reading error by simias on Thursday May 20, 2021 @03:01PM (#27225588)
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 being said I just tried and at least by default GCC emits the non-trapping "ADDU" even for signed adds, so maybe nobody actually uses that feature in practice.

Re:Undefined behavior in C is a reading error by anarazel on Thursday May 20, 2021 @03:44PM (#27226136)
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.
Re:Undefined behavior in C is a reading error by tsimionescu on Thursday May 20, 2021 @05:08PM (#27227287)
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 by lmm on Thursday May 20, 2021 @08:47PM (#27229293)
GCC is optimised for performing well on benchmarks at the expense of anything else. Vendor compilers for those architectures traditionally had more programmer-friendly features like trapping instead of creating an exploitable security vulnerability.
Re:Undefined behavior in C is a reading error by saagarjha on Thursday May 20, 2021 @09:55PM (#27229687)
> GCC is optimised for performing well on benchmarks at the expense of anything else.

This is very wrong, and I don't know why you would come to this conclusion.

> Vendor compilers for those architectures traditionally had more programmer-friendly features like trapping instead of creating an exploitable security vulnerability.

GCC has this feature too.

Re:Undefined behavior in C is a reading error by OskarS on Thursday May 20, 2021 @01:57PM (#27224653)
Assuming you defined signed integer overflow to follow two’s complement rules (the only reasonable interpretation other than UB), it would still be a guaranteed loop count of 16. (EDIT: i’m a dumbass, this is obvs not true. disregard this paragraph)

There’s an interesting thing to note with that example though: even if you did make signed integer overflow defined, that code is still obviously incorrect if param + 16 overflows. Like, the fact that signed integer overflow is UB is totally fine in this example: making it defined behavior doesn’t fix the code, and if making it UB allows the compiler to optimize, then why not?

Arguably, this is the case with the vast majority of signed integer overflow examples: the UB isn’t really the issue, the issue is that the programmer didn’t consider overflow, and if overflow happens the code is incorrect regardless. Why cripple the compilers ability to optimize to protect cases which are almost certainly incorrect anyway?

Re:Undefined behavior in C is a reading error by Gibbon1 on Thursday May 20, 2021 @04:05PM (#27226442)
The real problem is in a better world 'int' would be replaced by types that actually exhibit the correct behavior.

for a loop counter you want an index type that will seg fault on overflow. If you think not having that check is worth it the programmer would need to tag it with unsafe.

It's also problematic because it's size is defined as at least 16 bits. But programmers which means you should never use it to store a constant larger than 16 bits. But people do that all the time.

Re:Undefined behavior in C is a reading error by OskarS on Thursday May 20, 2021 @04:17PM (#27226611)
I’m not sure I agree. If signed overflow is UB, loops like this can be optimized the hell out of. The most obvious way would be to unroll it and eliminate the loop (and loop variable) entirely, but you can also do things like vectorize it, maybe turn it in to just a small number of SIMD instructions. The performance gains are potentially enormous if this is in a hot loop.

With your magic int that traps on overflow, you couldn’t do that if the compiler was forced to rely on that behaviour. This is exactly why signed overflow is UB in C, and I don’t think that’s an unreasonable case for a language like C.

To be clear, my point is that this program is incorrect if overflow happens regardless of whether overflow is UB or not. So you might as well make it UB and optimize the hell out of it.

Re:Undefined behavior in C is a reading error by cygx on Thursday May 20, 2021 @04:56PM (#27227128)
The broader argument is that signedness of the integer type used for indexing is a non-obvious gotcha affecting vectorizability. It makes sense once you understand C integer semantics, but putting on a language designer hat, I'd go with something more explicit.
Re:Undefined behavior in C is a reading error by thewakalix on Thursday May 20, 2021 @04:47PM (#27227007)
Many people write C programs that are not intended to be portable to 16-bit architectures.
Re:Undefined behavior in C is a reading error by _kst_ on Thursday May 20, 2021 @01:29PM (#27224203)
for (int i=param; i < param + 16; i++)

does not have a guaranteed loop count with the current rules. The loop body will execute 16 times if param <= INT_MAX-16, but if the expression "param + 16" can overflow, the behavior is undefined. (I'm assuming param is of type int.)

Re:Undefined behavior in C is a reading error by msbarnett on Thursday May 20, 2021 @01:36PM (#27224327)
> does not have a guaranteed loop count with the current rules. The loop body will execute 16 times if param <= INT_MAX-16, but if the expression "param + 16" can overflow, the behavior is undefined. (I'm assuming param is of type int.)

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.

Re:Undefined behavior in C is a reading error by _kst_ on Thursday May 20, 2021 @03:05PM (#27225631)
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 that the implementation doesn't have to be aware that the behavior is undefined. In this particular case:

for (int i=param; i < param + 16; i++)

that means the compiler can assume there's no overflow and generate code that always executes the loop body exactly 16 times, or it can generate naive code that computes param + 16 and uses whatever result the hardware gives it. And the implementation is under no obligation to tell you how it decides that.

Re:Undefined behavior in C is a reading error by msbarnett on Thursday May 20, 2021 @03:12PM (#27225700)
> that means the compiler can assume there's no overflow and generate code that always executes the loop body exactly 16 times

Right. That's what I said.

And just to be super-precise about the wording, the standard doesn't say "ignore the behavior 'with unpredictable results'" it says "Permissible undefined behavior ranges from ignoring the situation completely with unpredictable results". Nitpicky, but the former wording could be taken to imply that ignoring behavior is only permissible if the behavior is unpredictable, when what the standard actually says is that you can ignore the behavior, even if the results of ignoring it are unpredictable.

Re:Undefined behavior in C is a reading error by _kst_ on Thursday May 20, 2021 @03:28PM (#27225899)
And my point is that as far as the language is concerned, there is no guaranteed loop count under any circumstances. (An implementation is allowed, but not required, to define the behavior for that implementation.)
Re:Undefined behavior in C is a reading error by Smaug123 on Thursday May 20, 2021 @05:41PM (#27227704)
The two of you are not disagreeing except insofar as you're both using the word "guaranteed" to mean completely different things. _kst_, you're using it to mean "the programmer can rely on it". msbarnett, you're using it to mean "the compiler can rely on it".
Re:Undefined behavior in C is a reading error by tsimionescu on Thursday May 20, 2021 @05:16PM (#27227395)
> 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 by vyodaiken on Friday May 21, 2021 @09:39AM (#27233833)
in which case the overflow will cause the loop to change some random memory, but its ok since removing a single instruction test that is easy to pipeline is worth incorrect results!
Re:Undefined behavior in C is a reading error by dooglius on Thursday May 20, 2021 @02:33PM (#27225206)
Either the limit on param is guaranteed in some way by the rest of the program, or it is not. If it is, then the loop count is guaranteed in both cases. If it is not, the loop count is not guaranteed in either case.
Re:Undefined behavior in C is a reading error by msbarnett on Thursday May 20, 2021 @02:47PM (#27225392)
That you wish that the C Standard mandated this interpretation does not change the fact that this is not what the C Standard says.
Re:Undefined behavior in C is a reading error by dooglius on Thursday May 20, 2021 @02:58PM (#27225535)
You are mistaken, the C standard is quite clear that it does not make any guarantees regarding the behavior of programs that exhibit undefined behavior, and that signed integer overflow is undefined behavior.
Re:Undefined behavior in C is a reading error by msbarnett on Thursday May 20, 2021 @03:06PM (#27225645)
"for (int i=param; i < param + 16; i++) does not have a guaranteed loop count in the presence of undefined behavior" is true, but it's equally true that the C standard is quite clear that undefined behavior can be ignored, so we can validly treat "for (int i=param; i < param + 16; i++)" as if it were guaranteed to loop 16 times in all cases.
Re:Undefined behavior in C is a reading error by _kst_ on Thursday May 20, 2021 @04:01PM (#27226379)
No, the C standard doesn't say that "undefined behavior can be ignored" (which would mean what, making it defined?).

It says, "NOTE Possible undefined behavior ranges from ignoring the situation completely with unpredictable results, ...".

It doesn't say that the behavior can be ignored. It says that the undefinedness can be ignored. The implementation doesn't have to take notice of the fact that the behavior is undefined.

Let's take a simpler example:

    printf("%d\n", INT_MAX + 1);
The behavior is undefined. The standard does not guarantee anything about it. A conforming implementation can reject it at compile time, or it can generate code that crashes, or it can generate code that emits an ADD instruction and print whatever the hardware returns, or it can play roge at compile time. (The traditional joke is that can make demons fly out of your nose. Of course it can't, but an implementation that did so would be physically impossible, not non-conforming.)

An implementation might define the behavior, but it's still "undefined behavior" as that term is defined by the ISO C standard.

Re:Undefined behavior in C is a reading error by msbarnett on Thursday May 20, 2021 @04:08PM (#27226490)
"undefined behavior can be ignored" (meaning: the case where this could overflow need not be considered and can be treated as though it does not exist) vs "The implementation doesn't have to take notice of the fact that the behavior is undefined" strikes me as a distinction without a difference given that we land in exactly the same spot: the standard allows us to treat "for (int i=param; i < param + 16; i++)" as if it were guaranteed to loop 16 times in all cases.

> An implementation might define the behavior, but it's still "undefined behavior" as that term is defined by the ISO C standard.

The point where we seem to disagree (and the pedantry here is getting tiresome so I don't know that there's any value in continuing to go back and forth of on it) is that yes, it's undefined behavior by the ISO C standard. BUT, the ISO C standard also defines the allowable interpretations of and responses to undefined behaviour. Those responses don't exist "outside" the standard – they flow directly from it.

So it's simultaneously true that the standard does not define it and that the standard gives us a framework in which to give its undefinedness some treatment and response, even if that response is "launch angband" or, in this case, "act as if it loops 16 times in all cases".

Re:Undefined behavior in C is a reading error by _kst_ on Thursday May 20, 2021 @05:28PM (#27227533)
Of course an implementation can do anything it likes, including defining the behavior. That's one of the infinitely many ways of handling it -- precisely because it's undefined behavior.

I'm not using "undefined behavior" as the English two-word phrase. I'm using the technical term as it's defined by the ISO C standard. "The construct has undefined behavior" and "this implementation defines the behavior of the construct" are not contradictory statements.

And "ignoring the situation completely" does not imply any particular behavior. You seemed to be suggesting that "ignoring the situation completely" would result in the loop iterating exactly 16 tyimes.

Re:Undefined behavior in C is a reading error by msbarnett on Thursday May 20, 2021 @06:25PM (#27228200)
> Of course an implementation can do anything it likes, including defining the behavior. That's one of the infinitely many ways of handling it -- precisely because it's undefined behavior.

An implementation can do whatever it likes within the proscribed bounds the standard provides for reacting to "undefined behavior", and conversely whatever the implementation chooses to do within those bounds is consistent with the standard.

Which, again, is the entire point of this: "the loop iterates exactly 16 times" is a standards-conforming interpretation of the code in question. There's nothing outside the standard or non-standard about that. That is, in fact, exactly what the standard says that it is allowed to mean.

> I'm not using "undefined behavior" as the English two-word phrase. I'm using the technical term as it's defined by the ISO C standard.

So am I. Unlike you, I'm merely taking into account the part of the standard that says "NOTE: Possible undefined behavior ranges from ignoring the situation completely with unpredictable results..." and acknowledging that things that do so are standards-conforming.

> You seemed to be suggesting that "ignoring the situation completely" would result in the loop iterating exactly 16 tyimes.

I'm merely reiterating what the standard says: that the case in which the loop guard overflows can be ignored, allowing an implementation to conclude that the loop iterates exactly sixteen times in all scenarios it is required to consider.

All you seem to be doing here is reiterating, over and over again, "the standard says the behavior of the loop is undefined" to argue that the loop has no meaning, while ignoring that a different page of the same standard actual gives an allowable range of meanings to what it means for "behavior to be undefined", and that therefore anyone of those meanings is, in fact, precisely within the bounds of the standard.

We can validly say that the standard says "for (int i=param; i < param + 16; i++)" means "iterate 16 times always". We can validly say that the standard says "for (int i=param; i < param + 16; i++)" means "launch angband when param + 16 exceeds MAX_INT". Both are true statements.

Re:Undefined behavior in C is a reading error by maxlybbert on Thursday May 20, 2021 @09:58PM (#27229704)
> the standard allows us to treat "for (int i=param; i < param + 16; i++)" as if it were guaranteed to loop 16 times in all cases.

The standard allows this, but the standard also allows iterating less than 16 times, or turning it into an infinite loop, or doing things that a programmer can’t actually do intentionally inside the language’s rules. Undefined means “nothing is defined.” It doesn’t mean “nothing is defined, but in an intuitive way.”

Re:Undefined behavior in C is a reading error by masklinn on Thursday May 20, 2021 @03:04PM (#27225621)
They're not mistaken. What compilers will do is assume that UB don't happen. If no UB happens, that means `param + 16` never overflowed, therefore there are always exactly 16 operations.
Re:Undefined behavior in C is a reading error by _kst_ on Thursday May 20, 2021 @07:13PM (#27228631)
Or they assume "param + 16" will never overflow, so they emit an ADD instruction and use whatever result it yields.

Saying that a compiler "assumes" anything is anthropomorphic. A compiler may behave (generate code) in a manner that does not take the presence or absence of undefined behavior into account. If you just say it assumes something, that doesn't tell you what it will do based on that assumption.

Generating code that yields exactly 16 iterations is one of infinitely many possible consequences of undefined behavior.

If the mathematical value of `param + 16` exceeds `INT_MAX`, then the code has undefined behavior. The C standard says nothing at all about how the program will behave. A conforming compiler can generate code that iterates 42 times and then whistles Dixie. The non-normative note under the definition of "undefined behavior" does not constrain what a conforming implementation is allowed to do.

"imposes no requirements" means "imposes no requirements".

Re:Undefined behavior in C is a reading error by thewakalix on Thursday May 20, 2021 @04:51PM (#27227058)
Perhaps there's an implicit quantifier here: "for all valid implementations of the C standard, the loop count is guaranteed to be 16" versus "there exists a valid implementation of the C standard in which...".

(This line of thought inspired by RankNTypes, "who chooses the type", etc.)

Re:Undefined behavior in C is a reading error by thewakalix on Thursday May 20, 2021 @04:49PM (#27227040)
Perhaps there's an implicit quantifier here: "for all valid implementations of the C standard, the loop count is guaranteed to be 16" versus "there exists a valid implementation of the C standard in which...".
Re:Undefined behavior in C is a reading error by anarazel on Thursday May 20, 2021 @01:36PM (#27224335)
That's precisely my point? Because the overflow case is undefined, the compiler can assume it doesn't happen and optimize based on the fixed loop count.
Re:Undefined behavior in C is a reading error by rurban on Thursday May 20, 2021 @04:07PM (#27226465)
The overflow case is not UB. param can be unsigned, of fwrapv may be declared. Or the compiler chooses to declare fwrapv by default. In no case is the compiler allowed to declare the overflow away, unless it knows from before that param can not overflow. The optimization on loop count 16 can still happen with a runtime guard.
Re:Undefined behavior in C is a reading error by OskarS on Thursday May 20, 2021 @04:30PM (#27226793)
The loop counter is signed even if param is not, so i++ could overflow. fwrapv is a compiler flag, it is not part of the standard: it is a flag that mandates a certain behaviour in this case, but in standard C, the loop variable overflowing is definitely UB. No runtime guard needed, C compilers are just allowed to assume a fixed length. This is the whole reason signed overflow is UB in C, for exactly cases like this.
Re:Undefined behavior in C is a reading error by _kst_ on Thursday May 20, 2021 @05:30PM (#27227550)
If param is unsigned, then "param + 16" cannot overflow; rather, the value wraps around in a language-defined manner. I've been assuming that param is of type int (and I stated that assumption).
Re:Undefined behavior in C is a reading error by BruiseLee on Thursday May 20, 2021 @01:36PM (#27224326)
The compiler is allowed to act as if this loop executes exactly 16 times. That means it could unroll and vectorize it for example.
Re:Undefined behavior in C is a reading error by vyodaiken on Thursday May 20, 2021 @03:16PM (#27225737)
It is completely useless to allow compilers to assume false things about the code they generate.
Re:Undefined behavior in C is a reading error by fooker on Thursday May 20, 2021 @06:33PM (#27228266)
It’s not useless. The assumption is not false if the program doesn’t have undefined behavior. The assumption allows the code to be a few times faster. To disallow this assumption would inhibit these optimizations.
Re:Undefined behavior in C is a reading error by vyodaiken on Friday May 21, 2021 @06:38AM (#27232381)
a) the assumption is not false if it is not false! b) the speedup is not shown anywhere
Re:Undefined behavior in C is a reading error by fooker on Sunday May 23, 2021 @02:03PM (#27257099)
The speedup is more or less the difference between O1 and O3 optimization levels.