It puts the article in a different light. Makes you wonder what else he is incompetent or negligent about. In this sense it does hurt: it hurts him, it makes him less credible.
What are you trying to say? That because he is an authority figure to you and perhaps to other people, it is somehow OK to be ignorant about certain things? Last time I did something similar it was due to sheer ignorance and placebo. It might be a bad mistake, or a terrible habit, but it is what it is. It is silly regardless of who it comes from. :)
He is competent, and he wrote a blogpost to share something he knows on the web. It's a bit goofy to start claiming things about a character you don't know from a free publication.
Let me repeat: it is silly regardless of who it comes from. Everything else is irrelevant. You appear to be biased to the point of completely ignoring everything I have said. I get it, you like him. It does not change anything.
I merely suggested the possibility that he might be negligent or wrong about other relevant things. Do you think that this is impossible?
The author is competent and not at all silly. And the author explicitly stated what -O9 does and why he used it.
> You appear to be biased to the point of completely ignoring everything I have said.
This is in violation of you usage agreement with ycombinator.
> I merely suggested the possibility that he might be negligent or wrong about other relevant things.
No, that's not true.
> Do you think that this is impossible?
Strawman.
I see that you created your account just a few days ago ... you might want to be careful with it. In any case, I won't be engaging with you further, and I doubt that I'm the only one.
In older times (around the GCC 2.7 series, I think), "-O9" was documented to be the "future-proof" setting that selects the maximum optimization level, whatever it is. In practice, GCC never defined anything beyond -O3, but I still use -O9 when I want to make GCC do its best (or worst). Call it force of habit from a lengthening experience. (With Clang I use -O3 because if I write -O9 it screams at me.)
(Note that -O3 is usually not that good an idea: aggressive loop unrolling can sometimes decrease performance because of cache issues, for instance. To optimize code properly, you have to make benchmarks and adjust both the code and compiler flags accordingly, in a well-thought feedback cycle. The use of aggressive optimizations in the blog post is to make the examples trip UB more clearly.)
Upvoted for the signed integer overflow example. I'll admit that I actually don't know the most idiomatic, bulletproof way of testing for signed overflow in C; if you google "how to test signed integer overflow in C", the very first result is essentially equivalent to the buggy example in the blog post ( https://www.geeksforgeeks.org/check-for-integer-overflow/ ), and I'm not keen to repeat the legendary case of signed overflow within the PHP interpreter: https://web.archive.org/web/20120412194929/http://use.perl.o...
I'm not sure there is a reliable, generic approach for detecting overflow in conformant C; you probably have to come up with the appropriate proof for the specific operation that you're about to do. OpenBSD does it for multiplication in reallocarray() [1], which was introduced because it was easy to code an integer overflow when doing something like malloc(sizeof(member) * nmembers).
It depends on what operation could potentially overflow.
Mozilla has a CheckedInt (C++) type that checks all operations for overflow. You can see examples of how this is actually implemented here: <https://searchfox.org/mozilla-central/source/mfbt/CheckedInt.... You can derive similar C implementations if you work through all of the template magic.
Be warned that the definition of what is undefined, implementation-specific, and well-defined varies depending on the exact version of the C or C++ standard you use.
Well, the way you test are usually: 1) you know the ranges your params belong to and 2) you avoid situations where you might overflow. Usually if you catch the overflow you already lost.
I'm surprised to see that for unsigned ints modular semantics are guaranteed by the spec
"Please tell me again how unsigned ints are broken" It seems this meme seems to be the C version of anti-vaxxers.
"don't know the most idiomatic, bulletproof way of testing for signed overflow in C"
Basically, a great tool for static analysis and/or Frama-C for just the range analysis. Then, a coding style that facilitates such analysis. That should cover analysis. Idiomatic might be a problem because I see so many overflows in C code that it seems idiomatic for it to have them. ;)
In C you avoid signed integer overflow either by knowing that the result will be in range before applying an operation, or, as a last resort, by testing that the operation is defined before carrying it out. For example, if a and b are ints, then a + b is defined if (a >= 0 && b <= INT_MAX - a) || (a < 0 && b >= INT_MIN - a).
Additionally, some compilers can insert code to detect signed integer overflow at runtime. Clang has the -fsanitize=undefined flag [1].
Nope, that's the old way. Nowadays you do have access to the (un)signed add with carry (adc) builtins, which are the best way to provide an alternate method on overflow.
Nope. Practically gcc and clang are available for all platforms, and for the rare cases someone uses another compiler or an old version you ifdef it out with the slow path. even ICC has the add/mult with carry overflow builtins.
The ISO C standard is hopelessly behind for decades. They don't even define a proper (unicode) string API (search, norm, utf8, fc) , constexpr, a memory model, ... and leave everything to the implementors.
I very much doubt that, specially since clang doesn't even cover all gcc supported architectures.
Additionally, being available doesn't mean it is the compiler one is allowed to use.
Apparently you haven't kept up with ISO C, C11 defined the memory model and portable threads. It is unfortunate that compiler vendors, specially your beloved gcc and clang disregard the security Annex K.
Why do you aspire to write "portable" code which you are referring to as code that conforms to the ISO C standard when most widely used compilers do not? What you are suggesting is extremely impractical, it is a matter between theory and practice. Conforming to the standard when the compiler itself does not is impractical. On top of that, these compilers are available on most platforms, and yours seem to be such an edge case that it is negligible, and you can make the necessary adjustments when and if it ever comes to that. It is likely that it will not. If it does, it is just a matter of one or two ifdefs. Personally I write code that conforms to the compiler, because in reality, from a practical point of view, that is all that really matters.
It is not impractical, past experience on doing library projects for mutiple POSIX platforms, where the number one requirement was that they had to be compilable by the system compilers, teached me the right way of writing portable C code.
Such as? Do not get me wrong, I am against using GNU extensions, for example, and I do tend to make my code as portable as possible, but my main issue was with people glorifying the standard to what compilers themselves do not even strictly conform, and sometimes for good reasons. When you write code, you cannot ignore the compiler for obvious practical reasons. It does not matter what the paper says when the compiler does something completely different, or differently. If something goes terrible, you cannot say, "Oops, I was silly. I did not bother checking the documentation of the compiler.".
I'll just say it: that's a clang bug. The assumption being made by the optimizer is wrong, for exactly the reason that overflow exists.
I get very tired of people trying to make this "really" about "undefined behavior" sanity when real compilers are real software with real behavior. And here there is a clearly desired behavior (whether or not it got written into a standard somehwere), and clang implemented something else. That's wrong.
This particular undefined case is a really interesting one; it seems utterly non-obvious why it exists, until you remember one thing...
The most popular architecture today is 64-bit, with ABI specifying that the integer type is 32-bits wide.
So when faced with performing an operation on two 32-bit signed integers, on a 64-bit platform, you have to either:
1) perform the operation in 32-bit registers - if available - and even if available, usually far far far fewer in number thus massive performance & resource penalties to code
2) perform the operation in 64-bit registers, then add code to check the result, and if it would overflow in 32-bit, compute what the overflowed result would have looked like in a 32-bit register, and return that instead - again quite a performance hit
3) perform the operation in 64-bit registers, and just return the lower 32-bits, whatever that might be
The standard declined to pick a choice, which is why we have UB here.
(For unsigned integers, you can just truncate the result and it works every time, which is why the standard defines the result)
On the contrary: if clang assumed that signed integers could overflow by default, then that would be a bug. Why? Because it would result in missed optimizations, and optimizations are the reason why we use an optimizing compiler.
The loop codegen when the optimization is not performed is pretty atrocious. That is the bug, and solving that bug is the reason why compilers assume signed overflow cannot happen.
If you want to blame something, blame the C language. Compiler developers are just doing their jobs.
Here's an example of what can happen if the compiler doesn't perform these optimizations:
That's a great article, although I don't think it shows the advantage of assuming that undefined behavior will never occur. Rather than assuming "no undefined behavior", wouldn't it be legal (and preferable) for a compiler to just let the overflow (or lack of overflow) occur, and make the same optimization? For me the entire point of contention is the difference between "undefined" and "implementation defined". Maybe I'm wrong about the details here, but I think this is a case where a compiler could be just as fast without the nasal daemons.
It is doing exactly what you say - the code as generated simply lets the "overflow" occur, which is what makes it fast. In particular, if the index variable overflows the size of `int` it will just keep increasing. Effectively, the compiler has replaced int with long under the covers, since the cases where the behavior between int and long differ are exactly the cases where the int has overflowed.
So it's not always the case that the compiler assumes "overflow won't happen" and then _removes code_ - it just compiles code in a way that is ideal for the non overflow case and then what happens in the overflow case just falls out of the generated assembly (usually it does something bad like OOB access, but the same would generally be true of a wrapping overflow also).
You can't make this "implementation defined though", because the behavior is from a C-source point of view, it is effectively: "In the case an int overflows, we silently add 32 more bits and keep incrementing". Obviously you can't support that behavior in general, and even in specific cases it leads to nonsense like ints have non-representable values, etc.
GCC gets those loops optimized correctly without hitting the broken code in the linked article. I don't see that that's particularly responsive. Software is a concrete thing, it has concrete behavior, and problems can be solved there instead of pontificating about what paper standards say.
> If you want to blame something, blame the C language. Compiler developers are just doing their jobs.
Compiler developers are doing a fantastic job, and I absolutely do blame the C language and standard.
For the cases referenced in the article, it seems to me that the preferred solutions would be making int 64-bits and leaning on the restrict keyword rather than the semi-disaster that is strict aliasing (https://blog.regehr.org/archives/1307).
Instead of obfuscating with ifdef's, what's the downside of just using a non-standard but well-supported intrinsic that works for major compilers on common systems? For closed source, you are distributing a binary anyway, and have control of the compiler you choose. For open source, it may fail to compile, but the error message should make it clear what needs to be done (probably linking in a function written in assembly for the unsupported platform).
Undefined behavior gets a bad rap, but it's not always evil. Compilers and executables would be a lot slower if they had to account for these cases.
If you're writing serious C, you should be using tools like valgrind on debug-mode executables to make sure you aren't relying on undefined behavior. The tools are there. It's just not something a lot of people do.
My instinct is to downvote this to keep it at the bottom of the page, but since you are a new user with seemingly good intentions, that seems too rude.
Undefined behavior gets a bad rap, but it's not always evil.
Probably true, but make sure that you are distinguishing between undefined and implementation defined.
Compilers and executables would be a lot slower if they had to account for these cases.
Maybe, but I'd like to see better quantification for "a lot". My instinct (unsourced) is that it's usually minimal for most C, and quite significant for templated C++. But I'd interested in seeing firm numbers on this.
If you're writing serious C, you should be using tools like valgrind on debug-mode executables to make sure you aren't relying on undefined behavior.
This is where I think you veer off into being mostly wrong. I grew up with Valgrind, but I don't think it really has much use any more. You are almost always better off with one of the now built-in "sanitizers": https://github.com/google/sanitizers/wiki/AddressSanitizerCo....
But while you should be using these to catch bugs, neither the sanitizers nor Valgrind are able to catch the dangerous forms of undefined behavior shown in the examples in the article. UBSan is great and should be more used than it is (https://medium.com/@lucianoalmeida1/the-undefined-behavior-s...) but it is not going to catch anything near all the problems with undefined behavior!
Here's a summary of the unfortunate state of the art: https://blog.regehr.org/archives/1520. While there are underutilized tools that can help, "using tools like valgrind on debug-mode executables to make sure you aren't relying on undefined behavior" is likely to give you misplaced confidence that you are free from the dangers.
I think this is the overhead for mitigating by adding additional code (a branch on overflow that can be predicted as not taken), rather than the cost of lost optimizations that could have been used by assuming that UB does not occur. So a useful number, but measuring something else.
Although perhaps it can be used an an upper bound on the boost provided UB-free optimizations? That is, the overflow checking has both a direct cost, and prevents certain beneficial optimizations. Thus we can assume that the optimization benefit (on SPEC CPU 2006) is something less than 30%. That is to say, real, but not enormous compared to an algorithmic difference.
I don’t have numbers but I if imagine you forced the compiler to assume that any two pointers, regardless of type, could alias unless it could be proven otherwise, many of the optimizations that reduce or eliminate the cost of repeated indirection through a pointer could no longer be applied.
I agree with everything in the article - the example of non-intuitive effects of the strict aliasing rule, a tricky integer overflow example, and the unpopular plea to switch away from C/C++.
When I write C and C++ code, I try to make my logic portable and standards-compliant so that it will work on all platforms. So instead of assuming int is 32 bits, I am only allowed to assume that int is at least 16 bits wide. I assume that sizeof(char) could equal sizeof(int) and both could be 64 bits. I avoid bitwise manipulation on negative numbers, because they're not guaranteed to be two's complement. Keeping all of these pessimistic assumptions in mind while I code is a mental burden that I don't experience in other languages.
uint32_t a = UINT32_C(0xFFFFFFFF);
uint32_t b = a << 31;
b should be 0x80000000
Looks innocent, eh? Left-shifting an unsigned integer will discard the top bits and never cause undefined behavior. Except, this reasoning can be wrong on some platforms. Suppose:
typedef unsigned short uint32_t;
typedef int int48_t;
Now (uint32_t)a → (unsigned short)a → (int)a → (int48_t)a, due to typedefs and integer promotion. But because a is a signed integer, it is undefined behavior to shift 1's into the sign bit. Kaboom.
>I avoid bitwise manipulation on negative numbers, because they're not guaranteed to be two's complement.
This seems purely theoretical, as there is no reasonable architectures that are not using two's complement. It will be defined as two's complement in C++20. (but still with signed overflow UB, to keep some optimizations possible)
> The C standard specifies that values “cannot” be accessed through pointers that do not match the effective type of the value
Yet they can be and often are by using the union trick.
To decide whether to use the union trick requires a discussion of a program's desired portability which-- while usually desirable-- is a separate issue from undefined behavior.
The union thing is still 100% undefined behavior though, right? Some specific compilers guarantee a particular behavior, but by relying on it, you're not _really_ writing standard C anymore.
The rule allows both the union trick and a totally hacky char type exception (this was added because the standards authors found out that their rule was inconsistent and instead of backing it out, tried to hack it up).
7 An object shall have its stored value accessed only by an lvalue expression that has one of the following types:88)
— a type compatible with the effective type of the object,
— a qualified version of a type compatible with the effective type of the object,
— a type that is the signed or unsigned type corresponding to the effective type of the object, — a type that is the signed or unsigned type corresponding to a qualified version of the effective type of the object,
— an aggregate or union type that includes one of the aforementioned types among its members (including, recursively, a member of a subaggregate or contained union), or
One argument (that is unrelated to optimization) for keeping signed wrap undefined is that most instances of it is a real bug. By keep signed wrap undefined, you now have the option of using -ftrapv to weed out such bugs.
That might be a valid argument for making -ftrapv the standard. It's certainly not an argument for keeping it undefined. Most -f options tweak the standard in some way and defining overflow would not make -ftrapv suddenly go away.
Is there a compiler flag that can be set to print a warning about all undefined behaviour? I'm no a C dev but this UB business seems like a little cat and mouse game between the developer and the compiler which tries to find "tricks" to avoid doing stuff, which seems backwards.
Chris Lattner addresses this in part 3 of his “What Every C Programmer Should Know About Undefined Behavior” [0]:
“People often ask why the compiler doesn't produce warnings when it is taking advantage of undefined behavior to do an optimization, since any such case might actually be a bug in the user code. The challenges with this approach are that it is 1) likely to generate far too many warnings to be useful - because these optimizations kick in all the time when there is no bug, 2) it is really tricky to generate these warnings only when people want them, and 3) we have no good way to express (to the user) how a series of optimizations combined to expose the opportunity being optimized.”
Granted, this was written in 2011, so there’s a chance that something has changed, but the points brought up there seem like it isn’t that easy to fix.
I suspect such an option would be so verbose as to be useless; I believe it is virtually impossible to write any substantial amount of C without encountering undefined-behavior. It still might have some value for writing programs if you're willing to put in the absurd amount of effort required to actually be safe, but now we're getting into the territory of OpenBSD or qmail; possible, but vanishingly rare.
Just a reminder that there are ZERO published studies showing that these UB "optimizations" have significant value for any real programs. They impose a bizarre notion of C semantics that is not compatible with the language design. A good critique, for example, of the UB alias behavior can be found in Brian Kernhighans article on Pascal ( http://www.cs.virginia.edu/~evans/cs655-S00/readings/bwk-on-... ). The Standards authors have made the exact same error but in an ad hoc hacked up manner.
Again: not a single study with a benchmark, just an anecdote that actually means the opposite of what is intended. The authors of Bzip had to write non-idiomatic code to prevent UB "optimization" from breaking their code, and this results in compiled code that may or may not be slower. Tip: fewer assembly instructions does not always mean faster execution in a pipelined processor. In fact, compiling with -fwrap probably would generate better code.
Do you have a single published study showing that the UB "optimizations" benefit real programs?
I typed in the example code and current Clang generates exactly the same assembly for both u and not u integers - which is correct. So the problem he is describing is an error in Clang code generation that has since been fixed. Again: I have yet to see a serious attempt to validate the utility of UB "optimizations" - this video certainly does not contain any.
But the purported massive difference of the video disappears on those versions too. So that's the big proof of the efficacy of UB driven "optimization" - one additional assembler instruction in the clang code, some movslq vs movl. Dramatic. A micro-benchmark that indicates zero.
Anyway, only accepting "published studies" is pretty silly. UB is an engineering concern, not an academic one. Optimizations based on it arose because customers demanded them. Sometimes they can be quite significant: see https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759... for a good explanation of why signed overflow UB matters a lot for optimization of loops, for instance.
There's this weird myth that compiler developers like implementing clever complicated optimizations just because they hate programmers or are trying to make busy work for themselves or something. Compiler developers, like other developers, don't like to do work for no reason. They implemented these optimizations because customers filed bug reports indicating "missed optimizations", and they needed to exploit undefined behavior to satisfy those customers.
You are joking, right? Regehr's paper covers a proposed CHANGE to Clang/LVM UB behavior, while I was asking for studies that show advantages of UB "optimization" itself. The numbers show minor changes of performance on an artificial benchmark - some better some worse. Try better.
The absence of any actual studies showing benefits of UB "optimizations" is glaring. I don't care about motivations, which could simply be incompetance.
The point of giving that example is to show that there are studies that examine the benefit of undefined behavior, and in this case measure the performance of dialing back some degree of that UB exploitation.
It's trivial to show that if you try to completely eliminate undefined behavior from the C language then performance will collapse. Even register allocation depends on exploiting undefined behavior—who's to say that some wild pointer you created didn't accidentally point to some local variable? The reason why you don't see any studies on it is that it's obvious.
When it comes to signed overflow, the status quo comes from two inconvenient facts: (1) lots of C code out there loops over arrays using int for indices; (2) lots of C code out there assumes int is 32 bits. The latter means that, during the 64-bit transition, no compiler could switch to ILP64 and was forced to settle on LP64 (or LLP64 in the case of Windows). Confronted with these facts, compiler developers did the best they could, exploiting signed overflow in order to provide sensible codegen for idiomatic loops in C on 64-bit. The real world is complicated, and sometimes the right solution to an engineering problem is messy.
Regarding the charge of incompetence, with all due respect, my friends who work on Clang and GCC are better programmers than 99% of commenters on this site.
>The point of giving that example is to show that there are studies that examine the benefit of undefined behavior,
Of course, that is exactly what Regehr's paper does not show. It shows that a modification of Clang/LVM UB operations has some good properties. I am asking for studies showing significant benefits for UB "optimizations" that are not available otherwise.
I never advocated eliminating undefined behavior from C, I advocate eliminating UB based "optimizations" from C compilers, particularly "optimizations" which rely on assuming code will never do what emitted code does!
>The reason why you don't see any studies on it is that it's obvious.
And that is the classic tell for a serious mistake in engineering. We don't need to study it, its obvious.
Your response is flat out wrong. C is not defined as a memory safe language. You are inventing a false dichotomy: if the compiler cannot assume UB never happens, it must ensure UB never happens. Nope.
> I never advocated eliminating undefined behavior from C, I advocate eliminating UB based "optimizations" from C compilers, particularly "optimizations" which rely on assuming code will never do what emitted code does!
OK, then that definition excludes register allocation as a permitted optimization.
If you want to compile C code without any exploitation of undefined behavior, that's readily available! Just pass -O0 to your compiler.
with all due respect, my friends who work on Clang and GCC are better programmers than 99% of commenters on this site
I presume that both you and the majority of the people who work on compilers are great programmers. Which makes difficulty in communication even stranger.
Summarizing the anti-UB side, we really don't like it when the compiler drops explicit error checking code on the basis that error check would only be used if undefined behavior occurred. That is, I'd like a naive check for overflow to either emit an error message, or to compile as written with the behavior dependent on the underlying architecture.
Even register allocation depends on exploiting undefined behavior—who's to say that some wild pointer you created didn't accidentally point to some local variable?
The confusing part is that you (and many other smart people) seem to feel that "don't drop explicit error checks" is completely equivalent to "don't store local variables in registers". To me (to us) these are completely independent, with the dropped errors checking being a "real problem" and the possibly clobbered variables being a "not a problem", and in fact, everything working the way it should.
Could you explain more why you feel these two are equivalent?
My guess is that the difference is philosophical, between those who feel that the source code is a recipe, versus those who feel the source code is a mathematical proof. In my view, the goal of the compiler isn't to create a perfect program suitable for an perfect abstract machine, rather it's to translate the intent of the programmer into assembly language suitable for a particular deterministic processor.
I have no problem with a compiler that produces code that crashes on malformed input (division by zero, reading a NULL pointer) but I want it to leave the actual crash up to the processor. With overflow as with the case of clobbered aliased variables, I'm fine if the compiler generates code that only works correctly if the runtime error does not occur, but I'm not OK with reasoning non-locally that the error checks can be omitted because the error is logically impossible. Do you really not distinguish these two cases?
Dropping "explicit error checks" is no doubt bad from the user's point of view, but the primary difficulty is that to the compiler, working at the abstract level of multi-pass optimization of the IR, the good and bad cases all look the same. Pruning paths that lead to UB leads to some significant actual real-world optimizations (and these extend beyond these various signed-wrapping examples), and people want those whether they know it or not. Unfortunately, to the compilers, your overflow check just looks like another one of these cases.
That is, it is very hard for the compiler to guess the programmer's intent, and say "oh, this is actually a check which is trying to avoid overflow, and despite that it uses UB, we should compile this part with wrapping semantics instead", and yet apply the optimization in all the other places you would want it. You could probably come up with some type of pattern recognition, or some heuristics like "if the optimization makes some of the original source code dead unconditionally, don't make it", but I think this is both very difficult and in many cases worse than the current disease.
I think you can make a strong argument that the optimizations enabled by some types of UB exploitation are not worth the bugs and vulnerabilities they cause, and so the UB should be removed entirely, making it defined or implementation defined. Trying to have your cake (yes, it should still make these optimizations x and y) but eating it too (oh, but case z is different, see?) is a tougher proposition.
Dropping "explicit error checks" is no doubt bad from the user's point of view
Only from the user's point of view? No, I'd say it's bad in some absolute sense as well.
Can we at least agree that it would be better for the compiler to do what the programmer clearly intended? Yes, given current limitations, it can be difficult to see how a compiler has enough information to always recognize this intent. But I hope we at least both agree that if all else doing equal, doing what the programmer meant is the preferred choice?
As a parallel, I think the approach of having -Wall flag "if (a = b)" as a likely error but be overrideable with "if ((a = b))" is a great solution. Maybe this one can be solved with an extra block, or with a better #pragma, or just really good heuristics. But the current approach of silent deletion of explicit code for undefined behavior is a terrible pattern!
> Only from the user's point of view? No, I'd say it's bad in some absolute sense as well.
I didn't say _only_, but I'm not sure about "bad" an an "absolute" sense. I think it would take a lot of defining the exact question to debate that. For me if it is a bad outcome from the user's point of view, it is already worth discussing.
> Can we at least agree that it would be better for the compiler to do what the programmer clearly intended?
I guess? It would be pretty neat to work in a language that did what I intended rather than what I wrote, but it will quickly become unsustainable when two people write the same code but intended different things.
That problem doesn't apply exactly here since the code is just UB, so the intent doesn't exactly conflict with the actual semantics since there are no semantics. However, the compiler writers have decided to chose the behavior which produces the fastest code.
> Maybe this one can be solved with an extra block, or with a better #pragma, or just really good heuristics.
IMO, it is largely already solved.
If you want signed overflow to behave as, well, signed overflow, use -fwrapv. You pay the small price in reduced optimization opportunities, but you get well-defined behavior on wrapping always (note: wrapping is still almost always a bug!).
I think you can make a good argument that this flag should be the default behavior. Certainly, if you were designing a new language you might want to make it the default and maybe C and/or C++ will get there some day.
> But the current approach of silent deletion of explicit code for undefined behavior is a terrible pattern!
This sentence embodies my main complaint with the endless discussions on this topic. There is no optimization that just removes signed overflows checks, inserted there by a malicious compiler writer. There is a big family of interlocking optimizations, which as a whole are responsible for some spectacular gains in compiled code efficiency. For example there is dead code elimination, which is really important. There is treating code that does something impossible or UB as dead, which is also important (it extends way beyond this signedness stuff).
All this conspires to eliminate the _explicit_ overflow check which is the poster-child for compiler misbehavior - but the same optimizations do all sorts of other stuff that you wouldn't have a problem with. Everyone points there finger at this case that looks bad and says "obviously don't do that", but very few explain how. Deep within the guts of the optimizer, you just have IR which probably looks nothing like the code you wrote, there is no distinction between explicit and other code, and no "annotation of intent" to tell anyone what the programmer _really meant_.
You have most or all of the major compilers implementing this optimization, yet none of them have apparently solved this simple case of not messing up what the programmer wrote? Probably because it is not at all simple.
The solution I'm aware of is to just always treat overflow as defined. I.e., the -fwrapv solution. I'd be fine if compiler makes made it the default - but I guess the competitive pressures mean that compilers generally leave all legal optimizations on at the highest levels, to not be slower than the other guy. I'm OK with that also - at least it's a consistent rule.
The compiler-writers position is if you write broken code that invokes UB, you don't get the complain. I think that's often a reasonable approach. In other languages it's just the obvious default: it's just a bit annoying in C/C++ because there are so many things that people think should work, and did work, but are actually UB.
There is a big family of interlocking optimizations, which as a whole are responsible for some spectacular gains in compiled code efficiency.
I agree with you on the "interlocking" part, and the lack of conspiracy, but is there a canonical example of these "spectacular gains"? Particularly, from an optimization that depends on the assumption that the program exhibits no undefined behavior, where the opportunity for optimization disappears if the undefined behavior were instead to be implementation defined.
You have most or all of the major compilers implementing this optimization, yet none of them have apparently solved this simple case of not messing up what the programmer wrote?
I do not assume that it is simple, only that it is important and desirable. I'm not sure if compiler writers believe it to be impossible to do things better than they do, or just not sufficiently desirable to make it worth the effort. My guess would be that it's impossible to obey programmer intent perfectly in these cases, but possible to do much better than is done currently.
The solution I'm aware of is to just always treat overflow as defined.
First, I'm using signed integer overflow as the example not because it's a particular focus for me, but because it was central to the examples of linked article. Rather than -fwrapv, my personal preferred practice is to avoid unnecessary use of signed integers. My actual focus is the larger group of optimizations thought to be possible only because one can assume that a program does not invoke undefined behavior.
I'd like to see C (and probably C++, although I've thought about it less) reduce the scope of undefined behavior, either at the level of the standard or of individual compilers. I think there is room to allow more cases to be architecturally defined without significant adverse effect. I think the counter-argument is that if this were done, performance would necessarily drop. I haven't yet seen proof of this.
It appears that many people seem to assume (as you seem to) that there is no room between "implementation defined" (-fwrapv) and "undefined behavior" (nasal daemons). What I (and I think vyodaiken) are arguing is that there is a level of compiler agnosticism and architecturally defined that can be a useful middle ground. I think this approach (at least for C) offers 95% of the optimization potential while going 95% of the way of honoring the "obvious" intent of the programmer.
> I agree with you on the "interlocking" part, and the lack of conspiracy, but is there a canonical example of these "spectacular gains"?
To be clear, when I spoke of spectacular gains, I meant the overall result of all optimizations that modern compilers make, not just the "controversial subset". To see that with pretty much any program, just compare compiling with and without optimizations, or perhaps compare against a 20 or 30 year old C compiler if you can find one.
The actual impact of this specific controversial signedness optimization is likely to be small overall, at best low single digit %s but likely even less over a complex piece of software. That's true of many of individual optimizations today. In this case, you can easily A/B test this by compiling with and without -fwrapv. I have seen plenty of cases where the difference is zero within measurement accuracy!
In unusual cases, the optimization might speed up some loops by 2x or 3x (an example at [1]), but unless that loop makes up the majority of your application, those speedups will be averaged out by a lot of code that doesn't change.
So this signedness thing is not at all an example of spectacular gains, and I didn't mean to imply that it was.
Outside of signedness, if you want examples of some significant gains by "exploiting" UB rather than making all behavior [implementation] defined, don't worry: there is no shortage. Just go through a list like [2] and then follow the discussions in many places (including proposals in the standards committees) about what optimizations each UB allows. Certainly not all of the reasons for UB lead to interesting optimizations, but many do.
Consider a simple example: deallocating (e.g., free() in C, delete in C++) the same memory twice is UB, as is deallocating memory that was never allocated. You could certainly make this well-defined or implementation-defined instead: just define it to return some kind of error indication or do be a no-op.
If you've ever tried to write a high performance memory allocator, you already know that this requirement will kill you. You'll have to be able to distinguish a valid pointer from an invalid one, and you'll probably have to implement your whole allocation scheme in a different way.
Despite invalid deallocation and the consequent heap corruption being a major issue pretty much across the spectrum of C/C++ software (way more than a few signedness quirks), you don't hear almost any wailing or gnashing of teeth about how crazy it is when these programs malfunction - it's never going to make the front page of HN.
Now, you are probably thinking that obviously they malfunction because they have a bug! They are violating the specification! Well, the same is true of the signedness stuff - it's just a lot more surprising and less expected because (a) it's a relatively new phenomenon (b) like many more people people are aware of the UBness of invalid frees than are aware of the UB of signed overflow (c) if the compiler compiled it in the "obvious" way on "my hardware" it would have worked!
To be clear, I think this allocation thing is a completely defensible example of UB. OTOH, I think given modern hardware, and the limited gains, the signedness thing specifically is less defensible: but the solution is there no matter which side you fall on given -fwrapv.
> Rather than -fwrapv, my personal preferred practice is to avoid unnecessary use of signed integers.
Interesting. I use the opposite approach: I try to use signed for all _numeric_ values (leaving unsigned for "bit strings"), because I'm quite sure that the number of bugs caused by the discontinuity at zero (for unsigned values) is much larger than the number caused by the discontinuity or UB at INT_MIN/INT_MAX. Avoiding bugs is my goal and when you "wrap" a value it's almost always a bug whether the compiler exploited it to do something weird ...
A fine link, but oddly one that the two of us have already referenced in a different subthread. As stated there, I think there is room for a non-fwrapv approach that works just as well.
I try to use signed for all _numeric_ values (leaving unsigned for "bit strings"), because I'm quite sure that the number of bugs caused by the discontinuity at zero (for unsigned values) is much larger than the number caused by the discontinuity or UB at INT_MIN/INT_MAX.
I was probably unclear. I don't prefer unsigned to avoid the UB, but to get better generated assembly. While the unnecessary sign extension moves frequently come for free, occasionally they don't. I think the bugs are as likely to bite (or not bite) in either case, and need to be avoided by other means.
To see that with pretty much any program, just compare compiling with and without optimizations, or perhaps compare against a 20 or 30 year old C compiler if you can find one.
I'm less sure of that. You saw, for example, the current thread on RWT: https://www.realworldtech.com/forum/?threadid=182093&curpost...? I think the situation is rather that recent compilers do a better job with naive code, but are more likely to pessimize consciously constructed code. One major example of this is the most important micro-performance issue I've seen, which is the failure of GCC and Clang to reliably get µop macro-fusion bottom of loop branches. ICC does a much better job of keeping a decrement to zero tight to a fused jz, making the loop body one µop smaller.
These people are smart enough to get us into this
situation, so one would imagine they'd be smart enough
to least discuss this better way if it exists.
I lack that belief, but I'm not sure if that makes me more or less cynical than you. I think the issue is that almost everyone involved in standards process is likely to share a set of core philosophical beliefs about programming that may be self-consistent but not cover the full range of possibility. Consider as not quite parallels who becomes a US Supreme Court Justice or military commander, and how the selection process of being appointable affects the range of ideas espoused.
So what is this better way?
It might not be the solution, but I think that what you are not seeing is that there are other interpretations of "implementation defined" besides "always wrap" or saturate. You (and I think the standards committees) seem to want all non-UB programs to be fully deterministic, such that an emulator can always be written that will produce the same results as a real processor. I think there's room for an approach that says "if you stray beyond these rules, the real processor will decide your fate" without the "electric fence of death" approach currently taken by UB. I might be wrong to call this "implementation defined", but I think that's where it best fits in.
Consider a simple example: deallocating (e.g., free() in C, delete in C++) the same memory twice is UB, as is deallocating memory that was never allocated.
Let's use that an as example. What I want is for a standards compliant compiler to adopt this attitude: "It is unpredictable what happens if you call free twice in succession on the same pointer. Our compiler will try to issue a warning if it sees this happening, but the generated assembly is guaranteed to call free() twice. What happens after that is between you and your god."
I don't want is for it to be a guaranteed no-op. Nor do I want it the compiler t...
> As stated there, I think there is room for a non-fwrapv approach that works just as well.
Maybe I am missing something, but I feel the compiler is doing exactly what you are suggesting in that subthread, and I replied in that vein. Perhaps I am misunderstanding what you are suggesting.
> I was probably unclear. I don't prefer unsigned to avoid the UB, but to get better generated assembly. While the unnecessary sign extension moves frequently come for free, occasionally they don't.
That seems backwards. Due to this "issue" the suggestion is that signed often generates better assembly, because the compiler can reason that overflow doesn't occur. With unsigned, the compiler must generate code that accommodates wraparound, since it is allowed to occur.
For example, I would have expected the example code in the link to compile to worse code if an unsigned loop counter is used, since wraparound is legal and so the compiler will have to zero-extend each value. As it turns out it doesn't, since of course the compiler can additionally prove that if wraparound occurs this particular loop won't even be entered (since the condition is `i < count`). This proof is quite fragile however, if the loop condition were different or if any other math occurs on index it would break as in [1].
So it is not the case that compiler exploitation of UB simply brings signed level with the performance of unsigned, but that it can make signed faster, and that's how it is usually presented/argued.
Now I'm certainly not saying it is always true that is signed is no slower than unsigned: signed has the advantage of no-wrapping semantics, while unsigned has the advantage of zero extension being free in some scenarios (on some platforms) since it can be rolled into some other operation which implicitly zero extends, which is what I think you were referring to [2]. Which one has an effect (or greater) effect depends on the code.
> I think the bugs are as likely to bite (or not bite) in either case, and need to be avoided by other means.
Definitely not. Code with unsigned is always just one subtraction away from a huge (nonsense) value. That issue is a real one that occurs all the time, and why even the C++ folks (who ISTM rarely admit errors) generally acknowledge that using unsigned for things like container sizes was an error (albeit an uncorrectable one).
Signed values on the other hand, only overflow if you actually have a gigantic value that exceeds 2^31 or 2^63 or whatever. In many cases such large values cannot occur due to range of possible values (i.e., the meaning of the values), and especially with 64-bit values are unlikely to occur outside of malice. Furthermore, unsigned values are still subject to this type of overflow - but at 2^32 (2^64) rather than 2^31 (2^63).
I agree though that you should still use other mechanisms to avoid overflow even with signed values, but there is benefit to defense in depth.
> I'm less sure of [compiler optimization having improved spectacularly]. You saw, for example, the current thread on RWT: https://www.realworldtech.com/forum/?threadid=182093&curpost...? I think the situation is rather that recent compilers do a better job with naive code, but are more likely to pessimize consciously constructed code.
I'm not saying compilers are infallible. I am definitely in the camp that compilers have a long way to go. I believe optimization has improved dramatically in the last few decades. Perhaps "spectacularly" was too strong. This RWT example doesn't seem to contradict this: this is code that should have been well-optimized even 20 years ago. It is not in the set of things that needed to get better, so it should stay about the same. Due to some flaws in gcc, it actually has gotten worse. It is is large, complex code with lots of abstractions where...
> I think there's room for an approach that says "if you stray beyond these rules, the real processor will decide your fate" without the "electric fence of death" approach currently taken by UB. I might be wrong to call this "implementation defined", but I think that's where it best fits in.
How is this different from -fwrapv? The real processor implements the -fwrapv behavior, so it seems like the same thing.
If it's something different, how is it different than the current behavior of "compiler does whatever it wants and then the CPU executes the instructions"?
Maybe a specific example would help?
I think a key problem is that you are jumping ahead to "the real processor will decide your fate" - but that's not the interesting part. We all understand how real processors work (they wrap) - the whole question is what the language semantics of signed values are, because before you get to the processor, you have to compile the code. Even before that you have to write the code, and you want to know what happens when you do basic math on integers. If you want to invoke the specific processor behavior as part of the definition of how integers work, you also need to provide some kind of mapping from the source to machine operations (hint: I think -fwrapv behavior is the best or only way to do this practically).
> I don't want is for it to be a guaranteed no-op. Nor do I want it the compiler to eliminate code based on the assumption that the second call never happens. I want it to warn if it can (which can be a fatal warning if desired) but to always generate assembly that makes the potentially crashing call. My contract with the compiler is limited to determinism of the assembly it generates on my behalf, and does not include any guarantees or restrictions on the runtime behavior.
I see. What you basically want is a non-optimizing compiler, or a compiler that does only a limited amount of optimization following very strict rules (perhaps akin to something along the lines of how volatile is treated) about what can be optimized.
I think it is actually much more complicated than you would think (because the existing model of "as-if execution preserving required side-effects" is really very simple and clean).
More to the point, I don't think you'll ever get it [3] and you might not like what you get. 90% of optimization is eliminating code. The compiler eliminates function calls, assignments, math, allocations, jumps, branches, copies, constructors, and the list goes on forever. Elimination is the name of the game. Almost all of the time the result produced is indistinguishable from what you imagine the abstract machine doing, even though the combination of the compiler and real machine it is doing nothing like that at all.
These cases that get the press are notable for their exceptionality - at the intersection of a mismatch between what the standard says and how people imagine the language to work, and a similar mismatch between how people believe a compile (should?) work and how it does, and probably also a mismatch between the priorities of the compiler writers (performance on benchmarks) and users (correct code).
> My worry is that you (and others) don't consider this to be a standards compliant interpretation of "implementation defined", nor can it be "undefined behavior" if the compiler also reasons that UB can be assumed to never occur.
As above I'm not 100% clear on what you are suggesting, but I think it could be implementation defined as long as you can explain it (-fwrapv qualifies easily). After all, implementation defined has to be _defined_ in some way, right?
It could _definitely_ be UB, since UB can be whatever you want. A compiler could implement your suggestion right now and it would be within the rules. That just leaves us back where we are today though, right? Unknown or unexpected behavior in the presence of UB behavior.
Why do you assume we want either Pascal ("wrapping semantics") or random-"optimizations". Those are not the choices. It's actually very easy for the compiler to detect that it is a check to avoid overflow, it's the text of the program. You don't need to compile with wrapping semantics: the compiler generates code that actually does overflow the counter. All you need to do is to stop using invalid reasoning of the type: We assume that overflow cannot happen, yet generate code in which it does happen.
> Why do you assume we want either Pascal ("wrapping semantics") or random-"optimizations".
I don't think I assumed that.
I think there are a variety of ways of dealing with the overflow issue, which fall at a variety of points within the multi-dimensional design space that includes considerations like (a) comprehensibility by the average programmer and principle of least surprise (b) performance (c) fast failure (d) portability across hardware.
I don't know if C and C++ made the right decision with leaving this UB, nor am I convinced of the compiler writers method of handling the UB, but they are at least consistent in usually favoring performance and portability above other concerns. That it, is it is not obviously wrong to me or, nor dominated with another obviously better behavior.
> It's actually very easy for the compiler to detect that it is a check to avoid overflow, it's the text of the program.
I guess you are suggesting some type of idiom recognition, which will preserve these checks, but still allow full optimization in other cases where overflow is not expected or the intent of the programmer was different? I don't think that will ever happen. The best you can hope for is that the involved compilers simply decide to define signed overflow as wrapping, i.e., make the -fwrapv behavior the default. Personally I think that's a reasonable choice.
I can't imagine it is ever the intent of the programmer that if(i+1 < i)x be there simply as decoration to be removed by the compiler. If the compiler can deduce that the test will evaluate as false (or true), it is perfectly reasonable to optimize by deleting the line (or the check, in case of true). But this should be sound deduction. For example, if the target processor traps on overflow, the compiler can deduct that the conditional is always false. But what GCC/Clang do now is (a) generate machine code on x86 and ARM that does wrap, and (b) transform code on the axiom that ints will not wrap!That is, they take "false" for a theorem.
> I can't imagine it is ever the intent of the programmer that if(i+1 < i)x be there simply as decoration to be removed by the compiler.
I agree.
> But this should be sound deduction. For example, if the target processor traps on overflow, the compiler can deduct that the conditional is always false. But what GCC/Clang do now is (a) generate machine code on x86 and ARM that does wrap, and (b) transform code on the axiom that ints will not wrap!That is, they take "false" for a theorem.
I understand the desire, but you are talking about a different language, maybe assembly. C and C++ compilers just aren't in the habit of purposely compiling ill-formed code differently depending on the target processor. First and foremost they apply the rules of the language, and the rules are oriented towards portable-yet-fast code, and then as a last step they generate assembly or machine code.
I _really_ don't think you want the compiler changing the rules of the game depending on the target architecture. In fact, the trend is almost entirely away from this in all modern languages: towards a single consistent execution regardless of the architecture.
So the "deductions" you talk about are necessarily going to be against the abstract machine defined in the language, not against the final target.
It worth noting too that there is even an increasing trend towards separating the higher-level compilation and optimization and the final generation of a binary from the IR, for example in the Apple App Store I think you now submit IR which can be specialized by the store itself for each target device, including some not created yet. So at least in the initial stages of compilation, you may not even know the target, or it may not even exist at the current time!
Even the C standard still pays lip service to the notion of C as high level assembler. The notion that C should be an abstract high level language insulated from the machine is foreign both to the language design and usage. C is not designed to be memory safe, for example. The intent of implementation dependent and undefined in the C specification was to make explicit that the compiler was not entrusted with safeguarding the programmer against non-portable use. The bizarre theory that this can be interpreted as a license to sabotage the programmer in the case of non-portable use makes C unusable for its intended purposes - even if it make it possible to wring performance from terribly written benchmarks.
They impose a bizarre notion of C semantics that is not compatible with the language design.
Let's not forget that the standards committee even suggests "behaving during translation or program execution in a documented manner characteristic of the environment" (that's the exact wording from the standard) as one of the possible outcomes of UB, and it's the one that C programmers are most familiar with and also the one most aligned with the spirit of the language.
Thus IMHO the blame falls entirely on the compiler authors for not making reasonable choices. The whole argument that UB makes for great optimisations is not supported by compilers like Intel's ICC, which has historically been much less likely to exploit UB, yet can generate far better code than GCC --- because it is much better at instruction selection/scheduling.
That's correct, but I fault the Standard committee for not rejecting the peculiar interpretation that allows Compiler developers to assume e.g. overflow does not happen while emitting code that does overflow.
In Zig we embrace undefined behavior. It's what allows tools to catch mistakes, and it's what arms the optimizer with the assumptions it needs to be effective.
For example, not only is it undefined behavior to overflow on signed integer addition, in Zig it's also undefined behavior to overflow on unsigned integer addition. If you want wrapping integer addition, you have to use the wrapping integer addition operator, which is defined to wraparound on overflow.
Here's the trick though - Zig catches most kinds of undefined behavior before they have a chance to cause problems in release builds. Some undefined behavior is caught at compile time, and otherwise most undefined behavior is caught at runtime, in debug builds. And finally, if you are not confident in the level of testing your software has undergone, you can make a "release-safe" build, which has optimizations on, but includes undefined behavior checks and will crash (or invoke user-defined panic function) rather than invoke undefined behavior.
If the programmer can rely on your behavior, i.e. its being caught, then... that's not really undefined behavior, then.
The entire point of undefined behavior is that anything can happen. Wrap-around, segmentation faults, elided security checks or even ravenous polar bears, anything goes, and you can't know in advance what will.
The penultimate example tripped me up. I was under the impression that arithmetic conversions for binary operators only happened if the types of the operands were different. But reading the standard, and then actually experimenting with clang and __auto_type, does confirm that if the operands can be converted to int or unsigned int, then they will be (and that it will convert to int if int can represent all the values). That's really kind of nasty given the lack of wrapping overflow on signed integers.
This actually makes me wonder, if I do want wrapping overflow on signed integers in C, how do I request it? Is there some compiler builtin or stdlib function to say "please add/multiply/whatever these signed integers with overflow"?
You have several options, at least if you are willing to stick with GCC/Clang. Passing -fwrapv will give you well-defined (wrapping) signed overflow, which is often the native machine behaviour anyway. If you are interested in catching overflow when it happens, you can use intrinsics like __builtin_add_overflow. These look at the overflow flags present on many machines to let you know if the operation overflowed so you can handle it any way you like. If you are of the opinion that overflow should never happen in your program, you can pass -ftrapv which asks the compiler to crash your program if overflow ever occurs.
108 comments
[ 4.0 ms ] story [ 194 ms ] threadEDIT: Per https://wiki.gentoo.org/wiki/GCC_optimization#What_about_-O_... it's `enabled = (level >= 3);`
I merely suggested the possibility that he might be negligent or wrong about other relevant things. Do you think that this is impossible?
> You appear to be biased to the point of completely ignoring everything I have said.
This is in violation of you usage agreement with ycombinator.
> I merely suggested the possibility that he might be negligent or wrong about other relevant things.
No, that's not true.
> Do you think that this is impossible?
Strawman.
I see that you created your account just a few days ago ... you might want to be careful with it. In any case, I won't be engaging with you further, and I doubt that I'm the only one.
I do not see how it would be the case.
> No, that's not true.
Care to elaborate as to why you think that it is impossible for him to be negligent or wrong?
> I see that you created your account just a few days ago
What does it have to do with anything?
> you might want to be careful with it
Are you threatening me?
> I won't be engaging with you
Okay.
> I doubt that I'm the only one
Perhaps.
(Note that -O3 is usually not that good an idea: aggressive loop unrolling can sometimes decrease performance because of cache issues, for instance. To optimize code properly, you have to make benchmarks and adjust both the code and compiler flags accordingly, in a well-thought feedback cycle. The use of aggressive optimizations in the blog post is to make the examples trip UB more clearly.)
[1] https://github.com/openbsd/src/blob/master/lib/libc/stdlib/r...
Mozilla has a CheckedInt (C++) type that checks all operations for overflow. You can see examples of how this is actually implemented here: <https://searchfox.org/mozilla-central/source/mfbt/CheckedInt.... You can derive similar C implementations if you work through all of the template magic.
Be warned that the definition of what is undefined, implementation-specific, and well-defined varies depending on the exact version of the C or C++ standard you use.
I'm surprised to see that for unsigned ints modular semantics are guaranteed by the spec
"Please tell me again how unsigned ints are broken" It seems this meme seems to be the C version of anti-vaxxers.
Basically, a great tool for static analysis and/or Frama-C for just the range analysis. Then, a coding style that facilitates such analysis. That should cover analysis. Idiomatic might be a problem because I see so many overflows in C code that it seems idiomatic for it to have them. ;)
Additionally, some compilers can insert code to detect signed integer overflow at runtime. Clang has the -fsanitize=undefined flag [1].
[1] https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html
Portable means being defined in the ISO C standard.
The ISO C standard is hopelessly behind for decades. They don't even define a proper (unicode) string API (search, norm, utf8, fc) , constexpr, a memory model, ... and leave everything to the implementors.
Additionally, being available doesn't mean it is the compiler one is allowed to use.
Apparently you haven't kept up with ISO C, C11 defined the memory model and portable threads. It is unfortunate that compiler vendors, specially your beloved gcc and clang disregard the security Annex K.
Such as? Do not get me wrong, I am against using GNU extensions, for example, and I do tend to make my code as portable as possible, but my main issue was with people glorifying the standard to what compilers themselves do not even strictly conform, and sometimes for good reasons. When you write code, you cannot ignore the compiler for obvious practical reasons. It does not matter what the paper says when the compiler does something completely different, or differently. If something goes terrible, you cannot say, "Oops, I was silly. I did not bother checking the documentation of the compiler.".
This reminds me of something like: https://lkml.org/lkml/2018/6/5/769
I get very tired of people trying to make this "really" about "undefined behavior" sanity when real compilers are real software with real behavior. And here there is a clearly desired behavior (whether or not it got written into a standard somehwere), and clang implemented something else. That's wrong.
The most popular architecture today is 64-bit, with ABI specifying that the integer type is 32-bits wide.
So when faced with performing an operation on two 32-bit signed integers, on a 64-bit platform, you have to either:
1) perform the operation in 32-bit registers - if available - and even if available, usually far far far fewer in number thus massive performance & resource penalties to code
2) perform the operation in 64-bit registers, then add code to check the result, and if it would overflow in 32-bit, compute what the overflowed result would have looked like in a 32-bit register, and return that instead - again quite a performance hit
3) perform the operation in 64-bit registers, and just return the lower 32-bits, whatever that might be
The standard declined to pick a choice, which is why we have UB here.
(For unsigned integers, you can just truncate the result and it works every time, which is why the standard defines the result)
False for x86-64. There are sixteen 32-bit general-purpose registers: eax, ebx, ..., r8d, ..., r16d. There are sixteen 64-bit registers too: rax, rbx, ..., r8, ..., r16.
Here's an example of what can happen if the compiler doesn't perform these optimizations: https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759...
The loop codegen when the optimization is not performed is pretty atrocious. That is the bug, and solving that bug is the reason why compilers assume signed overflow cannot happen.
If you want to blame something, blame the C language. Compiler developers are just doing their jobs.
That's a great article, although I don't think it shows the advantage of assuming that undefined behavior will never occur. Rather than assuming "no undefined behavior", wouldn't it be legal (and preferable) for a compiler to just let the overflow (or lack of overflow) occur, and make the same optimization? For me the entire point of contention is the difference between "undefined" and "implementation defined". Maybe I'm wrong about the details here, but I think this is a case where a compiler could be just as fast without the nasal daemons.
So it's not always the case that the compiler assumes "overflow won't happen" and then _removes code_ - it just compiles code in a way that is ideal for the non overflow case and then what happens in the overflow case just falls out of the generated assembly (usually it does something bad like OOB access, but the same would generally be true of a wrapping overflow also).
You can't make this "implementation defined though", because the behavior is from a C-source point of view, it is effectively: "In the case an int overflows, we silently add 32 more bits and keep incrementing". Obviously you can't support that behavior in general, and even in specific cases it leads to nonsense like ints have non-representable values, etc.
Compiler developers are doing a fantastic job, and I absolutely do blame the C language and standard.
For the cases referenced in the article, it seems to me that the preferred solutions would be making int 64-bits and leaning on the restrict keyword rather than the semi-disaster that is strict aliasing (https://blog.regehr.org/archives/1307).
If you're writing serious C, you should be using tools like valgrind on debug-mode executables to make sure you aren't relying on undefined behavior. The tools are there. It's just not something a lot of people do.
Undefined behavior gets a bad rap, but it's not always evil.
Probably true, but make sure that you are distinguishing between undefined and implementation defined.
Compilers and executables would be a lot slower if they had to account for these cases.
Maybe, but I'd like to see better quantification for "a lot". My instinct (unsourced) is that it's usually minimal for most C, and quite significant for templated C++. But I'd interested in seeing firm numbers on this.
If you're writing serious C, you should be using tools like valgrind on debug-mode executables to make sure you aren't relying on undefined behavior.
This is where I think you veer off into being mostly wrong. I grew up with Valgrind, but I don't think it really has much use any more. You are almost always better off with one of the now built-in "sanitizers": https://github.com/google/sanitizers/wiki/AddressSanitizerCo....
But while you should be using these to catch bugs, neither the sanitizers nor Valgrind are able to catch the dangerous forms of undefined behavior shown in the examples in the article. UBSan is great and should be more used than it is (https://medium.com/@lucianoalmeida1/the-undefined-behavior-s...) but it is not going to catch anything near all the problems with undefined behavior!
Here's a summary of the unfortunate state of the art: https://blog.regehr.org/archives/1520. While there are underutilized tools that can help, "using tools like valgrind on debug-mode executables to make sure you aren't relying on undefined behavior" is likely to give you misplaced confidence that you are free from the dangers.
From Regehr's blog post that you linked:
> An issue with mitigating integer UBs is the overhead. For example, they cause SPEC CPU 2006 to run about 30% slower.
Although perhaps it can be used an an upper bound on the boost provided UB-free optimizations? That is, the overflow checking has both a direct cost, and prevents certain beneficial optimizations. Thus we can assume that the optimization benefit (on SPEC CPU 2006) is something less than 30%. That is to say, real, but not enormous compared to an algorithmic difference.
I think so too - as OP just said "dealing with," it wasn't clear to me that you were talking about just ignoring rather than handling.
When I write C and C++ code, I try to make my logic portable and standards-compliant so that it will work on all platforms. So instead of assuming int is 32 bits, I am only allowed to assume that int is at least 16 bits wide. I assume that sizeof(char) could equal sizeof(int) and both could be 64 bits. I avoid bitwise manipulation on negative numbers, because they're not guaranteed to be two's complement. Keeping all of these pessimistic assumptions in mind while I code is a mental burden that I don't experience in other languages.
Regarding integer promotions, here is one tricky situation I reasoned about and asked in https://stackoverflow.com/questions/39964651/is-masking-befo... . Suppose you want to compute:
Looks innocent, eh? Left-shifting an unsigned integer will discard the top bits and never cause undefined behavior. Except, this reasoning can be wrong on some platforms. Suppose: Now (uint32_t)a → (unsigned short)a → (int)a → (int48_t)a, due to typedefs and integer promotion. But because a is a signed integer, it is undefined behavior to shift 1's into the sign bit. Kaboom.This seems purely theoretical, as there is no reasonable architectures that are not using two's complement. It will be defined as two's complement in C++20. (but still with signed overflow UB, to keep some optimizations possible)
Yet they can be and often are by using the union trick.
To decide whether to use the union trick requires a discussion of a program's desired portability which-- while usually desirable-- is a separate issue from undefined behavior.
7 An object shall have its stored value accessed only by an lvalue expression that has one of the following types:88)
— a type compatible with the effective type of the object,
— a qualified version of a type compatible with the effective type of the object,
— a type that is the signed or unsigned type corresponding to the effective type of the object, — a type that is the signed or unsigned type corresponding to a qualified version of the effective type of the object,
— an aggregate or union type that includes one of the aforementioned types among its members (including, recursively, a member of a subaggregate or contained union), or
— a character type
I think this is used in "type punning" in union structures. This is a related comment by Linus Torvalds on the kernel list:
https://lkml.org/lkml/2018/6/5/769
“People often ask why the compiler doesn't produce warnings when it is taking advantage of undefined behavior to do an optimization, since any such case might actually be a bug in the user code. The challenges with this approach are that it is 1) likely to generate far too many warnings to be useful - because these optimizations kick in all the time when there is no bug, 2) it is really tricky to generate these warnings only when people want them, and 3) we have no good way to express (to the user) how a series of optimizations combined to expose the opportunity being optimized.”
Granted, this was written in 2011, so there’s a chance that something has changed, but the points brought up there seem like it isn’t that easy to fix.
[0]: http://blog.llvm.org/2011/05/what-every-c-programmer-should-...
Just use the flags that Linux has forced on the compiler developers in order to be able to make use of C or else give up on writing correct code. http://www.yodaiken.com/2018/11/17/standard-c-is-more-fun-th...
I typed in the example code and current Clang generates exactly the same assembly for both u and not u integers - which is correct. So the problem he is describing is an error in Clang code generation that has since been fixed. Again: I have yet to see a serious attempt to validate the utility of UB "optimizations" - this video certainly does not contain any.
What? Sure there are. John Regehr publishes work in this area. https://www.cs.utah.edu/~regehr/papers/undef-pldi17.pdf has performance numbers on taming some undefined behavior, for example (note the regressions).
Anyway, only accepting "published studies" is pretty silly. UB is an engineering concern, not an academic one. Optimizations based on it arose because customers demanded them. Sometimes they can be quite significant: see https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759... for a good explanation of why signed overflow UB matters a lot for optimization of loops, for instance.
There's this weird myth that compiler developers like implementing clever complicated optimizations just because they hate programmers or are trying to make busy work for themselves or something. Compiler developers, like other developers, don't like to do work for no reason. They implemented these optimizations because customers filed bug reports indicating "missed optimizations", and they needed to exploit undefined behavior to satisfy those customers.
The absence of any actual studies showing benefits of UB "optimizations" is glaring. I don't care about motivations, which could simply be incompetance.
It's trivial to show that if you try to completely eliminate undefined behavior from the C language then performance will collapse. Even register allocation depends on exploiting undefined behavior—who's to say that some wild pointer you created didn't accidentally point to some local variable? The reason why you don't see any studies on it is that it's obvious.
When it comes to signed overflow, the status quo comes from two inconvenient facts: (1) lots of C code out there loops over arrays using int for indices; (2) lots of C code out there assumes int is 32 bits. The latter means that, during the 64-bit transition, no compiler could switch to ILP64 and was forced to settle on LP64 (or LLP64 in the case of Windows). Confronted with these facts, compiler developers did the best they could, exploiting signed overflow in order to provide sensible codegen for idiomatic loops in C on 64-bit. The real world is complicated, and sometimes the right solution to an engineering problem is messy.
Regarding the charge of incompetence, with all due respect, my friends who work on Clang and GCC are better programmers than 99% of commenters on this site.
Of course, that is exactly what Regehr's paper does not show. It shows that a modification of Clang/LVM UB operations has some good properties. I am asking for studies showing significant benefits for UB "optimizations" that are not available otherwise.
I never advocated eliminating undefined behavior from C, I advocate eliminating UB based "optimizations" from C compilers, particularly "optimizations" which rely on assuming code will never do what emitted code does!
>The reason why you don't see any studies on it is that it's obvious.
And that is the classic tell for a serious mistake in engineering. We don't need to study it, its obvious.
Your response is flat out wrong. C is not defined as a memory safe language. You are inventing a false dichotomy: if the compiler cannot assume UB never happens, it must ensure UB never happens. Nope.
OK, then that definition excludes register allocation as a permitted optimization.
If you want to compile C code without any exploitation of undefined behavior, that's readily available! Just pass -O0 to your compiler.
Oh come on.
I presume that both you and the majority of the people who work on compilers are great programmers. Which makes difficulty in communication even stranger.
Summarizing the anti-UB side, we really don't like it when the compiler drops explicit error checking code on the basis that error check would only be used if undefined behavior occurred. That is, I'd like a naive check for overflow to either emit an error message, or to compile as written with the behavior dependent on the underlying architecture.
Even register allocation depends on exploiting undefined behavior—who's to say that some wild pointer you created didn't accidentally point to some local variable?
The confusing part is that you (and many other smart people) seem to feel that "don't drop explicit error checks" is completely equivalent to "don't store local variables in registers". To me (to us) these are completely independent, with the dropped errors checking being a "real problem" and the possibly clobbered variables being a "not a problem", and in fact, everything working the way it should.
Could you explain more why you feel these two are equivalent?
My guess is that the difference is philosophical, between those who feel that the source code is a recipe, versus those who feel the source code is a mathematical proof. In my view, the goal of the compiler isn't to create a perfect program suitable for an perfect abstract machine, rather it's to translate the intent of the programmer into assembly language suitable for a particular deterministic processor.
I have no problem with a compiler that produces code that crashes on malformed input (division by zero, reading a NULL pointer) but I want it to leave the actual crash up to the processor. With overflow as with the case of clobbered aliased variables, I'm fine if the compiler generates code that only works correctly if the runtime error does not occur, but I'm not OK with reasoning non-locally that the error checks can be omitted because the error is logically impossible. Do you really not distinguish these two cases?
That is, it is very hard for the compiler to guess the programmer's intent, and say "oh, this is actually a check which is trying to avoid overflow, and despite that it uses UB, we should compile this part with wrapping semantics instead", and yet apply the optimization in all the other places you would want it. You could probably come up with some type of pattern recognition, or some heuristics like "if the optimization makes some of the original source code dead unconditionally, don't make it", but I think this is both very difficult and in many cases worse than the current disease.
I think you can make a strong argument that the optimizations enabled by some types of UB exploitation are not worth the bugs and vulnerabilities they cause, and so the UB should be removed entirely, making it defined or implementation defined. Trying to have your cake (yes, it should still make these optimizations x and y) but eating it too (oh, but case z is different, see?) is a tougher proposition.
Only from the user's point of view? No, I'd say it's bad in some absolute sense as well.
Can we at least agree that it would be better for the compiler to do what the programmer clearly intended? Yes, given current limitations, it can be difficult to see how a compiler has enough information to always recognize this intent. But I hope we at least both agree that if all else doing equal, doing what the programmer meant is the preferred choice?
As a parallel, I think the approach of having -Wall flag "if (a = b)" as a likely error but be overrideable with "if ((a = b))" is a great solution. Maybe this one can be solved with an extra block, or with a better #pragma, or just really good heuristics. But the current approach of silent deletion of explicit code for undefined behavior is a terrible pattern!
I didn't say _only_, but I'm not sure about "bad" an an "absolute" sense. I think it would take a lot of defining the exact question to debate that. For me if it is a bad outcome from the user's point of view, it is already worth discussing.
> Can we at least agree that it would be better for the compiler to do what the programmer clearly intended?
I guess? It would be pretty neat to work in a language that did what I intended rather than what I wrote, but it will quickly become unsustainable when two people write the same code but intended different things.
That problem doesn't apply exactly here since the code is just UB, so the intent doesn't exactly conflict with the actual semantics since there are no semantics. However, the compiler writers have decided to chose the behavior which produces the fastest code.
> Maybe this one can be solved with an extra block, or with a better #pragma, or just really good heuristics.
IMO, it is largely already solved.
If you want signed overflow to behave as, well, signed overflow, use -fwrapv. You pay the small price in reduced optimization opportunities, but you get well-defined behavior on wrapping always (note: wrapping is still almost always a bug!).
I think you can make a good argument that this flag should be the default behavior. Certainly, if you were designing a new language you might want to make it the default and maybe C and/or C++ will get there some day.
> But the current approach of silent deletion of explicit code for undefined behavior is a terrible pattern!
This sentence embodies my main complaint with the endless discussions on this topic. There is no optimization that just removes signed overflows checks, inserted there by a malicious compiler writer. There is a big family of interlocking optimizations, which as a whole are responsible for some spectacular gains in compiled code efficiency. For example there is dead code elimination, which is really important. There is treating code that does something impossible or UB as dead, which is also important (it extends way beyond this signedness stuff).
All this conspires to eliminate the _explicit_ overflow check which is the poster-child for compiler misbehavior - but the same optimizations do all sorts of other stuff that you wouldn't have a problem with. Everyone points there finger at this case that looks bad and says "obviously don't do that", but very few explain how. Deep within the guts of the optimizer, you just have IR which probably looks nothing like the code you wrote, there is no distinction between explicit and other code, and no "annotation of intent" to tell anyone what the programmer _really meant_.
You have most or all of the major compilers implementing this optimization, yet none of them have apparently solved this simple case of not messing up what the programmer wrote? Probably because it is not at all simple.
The solution I'm aware of is to just always treat overflow as defined. I.e., the -fwrapv solution. I'd be fine if compiler makes made it the default - but I guess the competitive pressures mean that compilers generally leave all legal optimizations on at the highest levels, to not be slower than the other guy. I'm OK with that also - at least it's a consistent rule.
The compiler-writers position is if you write broken code that invokes UB, you don't get the complain. I think that's often a reasonable approach. In other languages it's just the obvious default: it's just a bit annoying in C/C++ because there are so many things that people think should work, and did work, but are actually UB.
I agree with you on the "interlocking" part, and the lack of conspiracy, but is there a canonical example of these "spectacular gains"? Particularly, from an optimization that depends on the assumption that the program exhibits no undefined behavior, where the opportunity for optimization disappears if the undefined behavior were instead to be implementation defined.
You have most or all of the major compilers implementing this optimization, yet none of them have apparently solved this simple case of not messing up what the programmer wrote?
I do not assume that it is simple, only that it is important and desirable. I'm not sure if compiler writers believe it to be impossible to do things better than they do, or just not sufficiently desirable to make it worth the effort. My guess would be that it's impossible to obey programmer intent perfectly in these cases, but possible to do much better than is done currently.
The solution I'm aware of is to just always treat overflow as defined.
First, I'm using signed integer overflow as the example not because it's a particular focus for me, but because it was central to the examples of linked article. Rather than -fwrapv, my personal preferred practice is to avoid unnecessary use of signed integers. My actual focus is the larger group of optimizations thought to be possible only because one can assume that a program does not invoke undefined behavior.
I'd like to see C (and probably C++, although I've thought about it less) reduce the scope of undefined behavior, either at the level of the standard or of individual compilers. I think there is room to allow more cases to be architecturally defined without significant adverse effect. I think the counter-argument is that if this were done, performance would necessarily drop. I haven't yet seen proof of this.
It appears that many people seem to assume (as you seem to) that there is no room between "implementation defined" (-fwrapv) and "undefined behavior" (nasal daemons). What I (and I think vyodaiken) are arguing is that there is a level of compiler agnosticism and architecturally defined that can be a useful middle ground. I think this approach (at least for C) offers 95% of the optimization potential while going 95% of the way of honoring the "obvious" intent of the programmer.
To be clear, when I spoke of spectacular gains, I meant the overall result of all optimizations that modern compilers make, not just the "controversial subset". To see that with pretty much any program, just compare compiling with and without optimizations, or perhaps compare against a 20 or 30 year old C compiler if you can find one.
The actual impact of this specific controversial signedness optimization is likely to be small overall, at best low single digit %s but likely even less over a complex piece of software. That's true of many of individual optimizations today. In this case, you can easily A/B test this by compiling with and without -fwrapv. I have seen plenty of cases where the difference is zero within measurement accuracy!
In unusual cases, the optimization might speed up some loops by 2x or 3x (an example at [1]), but unless that loop makes up the majority of your application, those speedups will be averaged out by a lot of code that doesn't change.
So this signedness thing is not at all an example of spectacular gains, and I didn't mean to imply that it was.
Outside of signedness, if you want examples of some significant gains by "exploiting" UB rather than making all behavior [implementation] defined, don't worry: there is no shortage. Just go through a list like [2] and then follow the discussions in many places (including proposals in the standards committees) about what optimizations each UB allows. Certainly not all of the reasons for UB lead to interesting optimizations, but many do.
Consider a simple example: deallocating (e.g., free() in C, delete in C++) the same memory twice is UB, as is deallocating memory that was never allocated. You could certainly make this well-defined or implementation-defined instead: just define it to return some kind of error indication or do be a no-op.
If you've ever tried to write a high performance memory allocator, you already know that this requirement will kill you. You'll have to be able to distinguish a valid pointer from an invalid one, and you'll probably have to implement your whole allocation scheme in a different way.
Despite invalid deallocation and the consequent heap corruption being a major issue pretty much across the spectrum of C/C++ software (way more than a few signedness quirks), you don't hear almost any wailing or gnashing of teeth about how crazy it is when these programs malfunction - it's never going to make the front page of HN.
Now, you are probably thinking that obviously they malfunction because they have a bug! They are violating the specification! Well, the same is true of the signedness stuff - it's just a lot more surprising and less expected because (a) it's a relatively new phenomenon (b) like many more people people are aware of the UBness of invalid frees than are aware of the UB of signed overflow (c) if the compiler compiled it in the "obvious" way on "my hardware" it would have worked!
To be clear, I think this allocation thing is a completely defensible example of UB. OTOH, I think given modern hardware, and the limited gains, the signedness thing specifically is less defensible: but the solution is there no matter which side you fall on given -fwrapv.
> Rather than -fwrapv, my personal preferred practice is to avoid unnecessary use of signed integers.
Interesting. I use the opposite approach: I try to use signed for all _numeric_ values (leaving unsigned for "bit strings"), because I'm quite sure that the number of bugs caused by the discontinuity at zero (for unsigned values) is much larger than the number caused by the discontinuity or UB at INT_MIN/INT_MAX. Avoiding bugs is my goal and when you "wrap" a value it's almost always a bug whether the compiler exploited it to do something weird ...
https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759...
A fine link, but oddly one that the two of us have already referenced in a different subthread. As stated there, I think there is room for a non-fwrapv approach that works just as well.
I try to use signed for all _numeric_ values (leaving unsigned for "bit strings"), because I'm quite sure that the number of bugs caused by the discontinuity at zero (for unsigned values) is much larger than the number caused by the discontinuity or UB at INT_MIN/INT_MAX.
I was probably unclear. I don't prefer unsigned to avoid the UB, but to get better generated assembly. While the unnecessary sign extension moves frequently come for free, occasionally they don't. I think the bugs are as likely to bite (or not bite) in either case, and need to be avoided by other means.
To see that with pretty much any program, just compare compiling with and without optimizations, or perhaps compare against a 20 or 30 year old C compiler if you can find one.
I'm less sure of that. You saw, for example, the current thread on RWT: https://www.realworldtech.com/forum/?threadid=182093&curpost...? I think the situation is rather that recent compilers do a better job with naive code, but are more likely to pessimize consciously constructed code. One major example of this is the most important micro-performance issue I've seen, which is the failure of GCC and Clang to reliably get µop macro-fusion bottom of loop branches. ICC does a much better job of keeping a decrement to zero tight to a fused jz, making the loop body one µop smaller.
These people are smart enough to get us into this situation, so one would imagine they'd be smart enough to least discuss this better way if it exists.
I lack that belief, but I'm not sure if that makes me more or less cynical than you. I think the issue is that almost everyone involved in standards process is likely to share a set of core philosophical beliefs about programming that may be self-consistent but not cover the full range of possibility. Consider as not quite parallels who becomes a US Supreme Court Justice or military commander, and how the selection process of being appointable affects the range of ideas espoused.
So what is this better way?
It might not be the solution, but I think that what you are not seeing is that there are other interpretations of "implementation defined" besides "always wrap" or saturate. You (and I think the standards committees) seem to want all non-UB programs to be fully deterministic, such that an emulator can always be written that will produce the same results as a real processor. I think there's room for an approach that says "if you stray beyond these rules, the real processor will decide your fate" without the "electric fence of death" approach currently taken by UB. I might be wrong to call this "implementation defined", but I think that's where it best fits in.
Consider a simple example: deallocating (e.g., free() in C, delete in C++) the same memory twice is UB, as is deallocating memory that was never allocated.
Let's use that an as example. What I want is for a standards compliant compiler to adopt this attitude: "It is unpredictable what happens if you call free twice in succession on the same pointer. Our compiler will try to issue a warning if it sees this happening, but the generated assembly is guaranteed to call free() twice. What happens after that is between you and your god."
I don't want is for it to be a guaranteed no-op. Nor do I want it the compiler t...
Maybe I am missing something, but I feel the compiler is doing exactly what you are suggesting in that subthread, and I replied in that vein. Perhaps I am misunderstanding what you are suggesting.
> I was probably unclear. I don't prefer unsigned to avoid the UB, but to get better generated assembly. While the unnecessary sign extension moves frequently come for free, occasionally they don't.
That seems backwards. Due to this "issue" the suggestion is that signed often generates better assembly, because the compiler can reason that overflow doesn't occur. With unsigned, the compiler must generate code that accommodates wraparound, since it is allowed to occur.
For example, I would have expected the example code in the link to compile to worse code if an unsigned loop counter is used, since wraparound is legal and so the compiler will have to zero-extend each value. As it turns out it doesn't, since of course the compiler can additionally prove that if wraparound occurs this particular loop won't even be entered (since the condition is `i < count`). This proof is quite fragile however, if the loop condition were different or if any other math occurs on index it would break as in [1].
So it is not the case that compiler exploitation of UB simply brings signed level with the performance of unsigned, but that it can make signed faster, and that's how it is usually presented/argued.
Now I'm certainly not saying it is always true that is signed is no slower than unsigned: signed has the advantage of no-wrapping semantics, while unsigned has the advantage of zero extension being free in some scenarios (on some platforms) since it can be rolled into some other operation which implicitly zero extends, which is what I think you were referring to [2]. Which one has an effect (or greater) effect depends on the code.
> I think the bugs are as likely to bite (or not bite) in either case, and need to be avoided by other means.
Definitely not. Code with unsigned is always just one subtraction away from a huge (nonsense) value. That issue is a real one that occurs all the time, and why even the C++ folks (who ISTM rarely admit errors) generally acknowledge that using unsigned for things like container sizes was an error (albeit an uncorrectable one).
Signed values on the other hand, only overflow if you actually have a gigantic value that exceeds 2^31 or 2^63 or whatever. In many cases such large values cannot occur due to range of possible values (i.e., the meaning of the values), and especially with 64-bit values are unlikely to occur outside of malice. Furthermore, unsigned values are still subject to this type of overflow - but at 2^32 (2^64) rather than 2^31 (2^63).
I agree though that you should still use other mechanisms to avoid overflow even with signed values, but there is benefit to defense in depth.
> I'm less sure of [compiler optimization having improved spectacularly]. You saw, for example, the current thread on RWT: https://www.realworldtech.com/forum/?threadid=182093&curpost...? I think the situation is rather that recent compilers do a better job with naive code, but are more likely to pessimize consciously constructed code.
I'm not saying compilers are infallible. I am definitely in the camp that compilers have a long way to go. I believe optimization has improved dramatically in the last few decades. Perhaps "spectacularly" was too strong. This RWT example doesn't seem to contradict this: this is code that should have been well-optimized even 20 years ago. It is not in the set of things that needed to get better, so it should stay about the same. Due to some flaws in gcc, it actually has gotten worse. It is is large, complex code with lots of abstractions where...
How is this different from -fwrapv? The real processor implements the -fwrapv behavior, so it seems like the same thing.
If it's something different, how is it different than the current behavior of "compiler does whatever it wants and then the CPU executes the instructions"?
Maybe a specific example would help?
I think a key problem is that you are jumping ahead to "the real processor will decide your fate" - but that's not the interesting part. We all understand how real processors work (they wrap) - the whole question is what the language semantics of signed values are, because before you get to the processor, you have to compile the code. Even before that you have to write the code, and you want to know what happens when you do basic math on integers. If you want to invoke the specific processor behavior as part of the definition of how integers work, you also need to provide some kind of mapping from the source to machine operations (hint: I think -fwrapv behavior is the best or only way to do this practically).
> I don't want is for it to be a guaranteed no-op. Nor do I want it the compiler to eliminate code based on the assumption that the second call never happens. I want it to warn if it can (which can be a fatal warning if desired) but to always generate assembly that makes the potentially crashing call. My contract with the compiler is limited to determinism of the assembly it generates on my behalf, and does not include any guarantees or restrictions on the runtime behavior.
I see. What you basically want is a non-optimizing compiler, or a compiler that does only a limited amount of optimization following very strict rules (perhaps akin to something along the lines of how volatile is treated) about what can be optimized.
I think it is actually much more complicated than you would think (because the existing model of "as-if execution preserving required side-effects" is really very simple and clean).
More to the point, I don't think you'll ever get it [3] and you might not like what you get. 90% of optimization is eliminating code. The compiler eliminates function calls, assignments, math, allocations, jumps, branches, copies, constructors, and the list goes on forever. Elimination is the name of the game. Almost all of the time the result produced is indistinguishable from what you imagine the abstract machine doing, even though the combination of the compiler and real machine it is doing nothing like that at all.
These cases that get the press are notable for their exceptionality - at the intersection of a mismatch between what the standard says and how people imagine the language to work, and a similar mismatch between how people believe a compile (should?) work and how it does, and probably also a mismatch between the priorities of the compiler writers (performance on benchmarks) and users (correct code).
> My worry is that you (and others) don't consider this to be a standards compliant interpretation of "implementation defined", nor can it be "undefined behavior" if the compiler also reasons that UB can be assumed to never occur.
As above I'm not 100% clear on what you are suggesting, but I think it could be implementation defined as long as you can explain it (-fwrapv qualifies easily). After all, implementation defined has to be _defined_ in some way, right?
It could _definitely_ be UB, since UB can be whatever you want. A compiler could implement your suggestion right now and it would be within the rules. That just leaves us back where we are today though, right? Unknown or unexpected behavior in the presence of UB behavior.
I think there is a misconcept...
I don't think I assumed that.
I think there are a variety of ways of dealing with the overflow issue, which fall at a variety of points within the multi-dimensional design space that includes considerations like (a) comprehensibility by the average programmer and principle of least surprise (b) performance (c) fast failure (d) portability across hardware.
I don't know if C and C++ made the right decision with leaving this UB, nor am I convinced of the compiler writers method of handling the UB, but they are at least consistent in usually favoring performance and portability above other concerns. That it, is it is not obviously wrong to me or, nor dominated with another obviously better behavior.
> It's actually very easy for the compiler to detect that it is a check to avoid overflow, it's the text of the program.
I guess you are suggesting some type of idiom recognition, which will preserve these checks, but still allow full optimization in other cases where overflow is not expected or the intent of the programmer was different? I don't think that will ever happen. The best you can hope for is that the involved compilers simply decide to define signed overflow as wrapping, i.e., make the -fwrapv behavior the default. Personally I think that's a reasonable choice.
I agree.
> But this should be sound deduction. For example, if the target processor traps on overflow, the compiler can deduct that the conditional is always false. But what GCC/Clang do now is (a) generate machine code on x86 and ARM that does wrap, and (b) transform code on the axiom that ints will not wrap!That is, they take "false" for a theorem.
I understand the desire, but you are talking about a different language, maybe assembly. C and C++ compilers just aren't in the habit of purposely compiling ill-formed code differently depending on the target processor. First and foremost they apply the rules of the language, and the rules are oriented towards portable-yet-fast code, and then as a last step they generate assembly or machine code.
I _really_ don't think you want the compiler changing the rules of the game depending on the target architecture. In fact, the trend is almost entirely away from this in all modern languages: towards a single consistent execution regardless of the architecture.
So the "deductions" you talk about are necessarily going to be against the abstract machine defined in the language, not against the final target.
It worth noting too that there is even an increasing trend towards separating the higher-level compilation and optimization and the final generation of a binary from the IR, for example in the Apple App Store I think you now submit IR which can be specialized by the store itself for each target device, including some not created yet. So at least in the initial stages of compilation, you may not even know the target, or it may not even exist at the current time!
Let's not forget that the standards committee even suggests "behaving during translation or program execution in a documented manner characteristic of the environment" (that's the exact wording from the standard) as one of the possible outcomes of UB, and it's the one that C programmers are most familiar with and also the one most aligned with the spirit of the language.
Thus IMHO the blame falls entirely on the compiler authors for not making reasonable choices. The whole argument that UB makes for great optimisations is not supported by compilers like Intel's ICC, which has historically been much less likely to exploit UB, yet can generate far better code than GCC --- because it is much better at instruction selection/scheduling.
For example, not only is it undefined behavior to overflow on signed integer addition, in Zig it's also undefined behavior to overflow on unsigned integer addition. If you want wrapping integer addition, you have to use the wrapping integer addition operator, which is defined to wraparound on overflow.
Here's the trick though - Zig catches most kinds of undefined behavior before they have a chance to cause problems in release builds. Some undefined behavior is caught at compile time, and otherwise most undefined behavior is caught at runtime, in debug builds. And finally, if you are not confident in the level of testing your software has undergone, you can make a "release-safe" build, which has optimizations on, but includes undefined behavior checks and will crash (or invoke user-defined panic function) rather than invoke undefined behavior.
You can see some examples of this here: https://ziglang.org/documentation/master/#Undefined-Behavior
The entire point of undefined behavior is that anything can happen. Wrap-around, segmentation faults, elided security checks or even ravenous polar bears, anything goes, and you can't know in advance what will.
This actually makes me wonder, if I do want wrapping overflow on signed integers in C, how do I request it? Is there some compiler builtin or stdlib function to say "please add/multiply/whatever these signed integers with overflow"?