GCC undefined behaviors are getting wild
blog.pkh.me
blog.pkh.me
This has caused a Linux kernel exploit in the past [1], with GCC removing a null pointer check after a pointer had been dereferenced. Null pointer dereferences are UB, thus GCC was allowed to remove the following check against null. In the kernel, accessing a null ptr is technically fine, so the Linux kernel is now compiled with -fno-delete-null-pointer-checks, extending the list of differences between standard C and Linux kernel C.
The C standard also allows doing it even when there is no UB. C gives implementations a ton of freedom.
Like many other large C codebases, it also uses -fno-strict-aliasing and -fno-strict-overflow (which is a synonym for "-fwrapv -fwrapv-pointer").
I'd be curious to know how much production code today that's written in C is that performance critical, i.e. depends on all those bonkers exploits of UB for optimizations. The Linux kernel seems to do fine without this.
Most programs rarely issue all the instructions that a CPU can handle simultaneously, they are stuck waiting on memory or linear dependencies. An extra compile-out-able conditional typically doesn't touch memory and is off the linear dependency path, which makes it virtually free.
So the actual real-world overhead ends up at less than 1%, but in most cases something that is indistinguishable from 0.
If you care that much about 1% you are probably already writing the most performance critical parts in Assembly anyway.
I call this hotspot fallacy and it is a common one. This assumes there is relatively small performance critical parts that can be rewritten in assembly. Yes, sometimes there is a hotspot, but by no means always. A lot of people caring about 1% is running gigabytes binary on datacenter scale computer without hotspots.
It is sad that we don't get hardware assistance for that trap on any widespread cpu, at least that I know of.
Without you have to do convoluted things like rearranging the expression to unnatural forms (move the addition to the right but invert to subtraction, etc), special case INT_MAX/INT_MIN, and so on - which you then have to hope the compiler is smart enough to optimize, which it often isn't (oh how ironic).
The problem is the program isn't invalidated, it's compiled and run.
The malicious compiler introducing security bugs from Ken Thompson's "Reflections on Trusting Trust" is real, and it's the C standard.
I will grant that trying to detect UB at runtime may impose serious performance penalties, since it's very hard to do arithmetic without risking it. But at compile time? If a situation has been statically determined to invoke UB that should be a compile time error.
Also, if an optimizer determines that an entire statement has no effect, that should be at least a warning. (C lack C#'s concept of a "code analysis hint" which have individually configurable severity levels).
That's simply not how the compiler works.
There is (presumably, I haven't actually looked) no boolean function in GCC called is_undefined_behavior(). It's just that each optimization part of the compiler can (and does) assume that UB doesn't happen, and results like the article's are then essentially emergent behavior.
See also: https://blog.regehr.org/archives/213
Does that mean it's acceptable for GCC to reformat my hard drive?
Just because something is UD doesn't give anyone a license to do crazy things.
If I misspell --help I expect the program to do something reasonable. If I invoke UD I still expect the program to do something reasonable.
Removing checks for an overflow because overflows 'can't happen' is just crazy.
UD is supposed to allow C to be implemented on different architectures if you don't know whether it will overflow to INT_MIN it makes sense to leave the implementation open. If I, the user knows what happens when an int overflows then I should be able to make use of that and guard against it myself. A compiler undermining that is a bug and user hostile.
No, it's not, and I don't know why you'd think so. UB is a concept applying to C programs, not GCC invocations.
> UD is supposed to allow C to be implemented on different architectures if you don't know whether it will overflow to INT_MIN it makes sense to leave the implementation open. If I, the user knows what happens when an int overflows then I should be able to make use of that and guard against it myself.
I think you're confusing UB with unspecified and implementation defined behavior. It's fine if you think something shouldn't be UB, but you have to go lobbying the C standard for that. Compiler writers aren't to blame here.
A slightly less textualist approach to language recognizes that when we talk about C and UB, we mean behavior, which is undefined, of operations otherwise defined by the C standard.
No GCC --hlep isn't in the c standard.
But it is a simple example to illustrate how programs react when it receives something that isn't in the spec. GCC could do anything with Gcc --hlep just like it could do anything with INT_MAX + 1. That doesnt mean that all options open to it are reasonable.
If I typed in GCC --hlep I would be reasonably pissed that it deleted my hard drive. You pointing out that GCC never made any claims about what would happen if I did that doesn't make it ok.
If you come across UD, there's reasonable and unreasonable ways to deal with that. Reformatting your hard drive which is presumably allowed by the C standard isn't reasonable. I would contend that removing checks is also unreasonable.
Yeah, but removing a null check after a dereference has a solid rationale, so it’s very different from GCC taking it upon itself to format your drive.
That would logically include reformatting your hard drive.
I definitely disagree with that pov, if you don't accept that UB can result in anything then the line needs to be drawn somewhere.
I would contend that UB stems from the hardware. C won't take responsibility for what the hardware does. Neither will it step in to change what the hardware does. That in turn means that UB means the compiler shouldn't optimise because the behaviour is undefined.
What should happen when I invoke --hlep then? The program could give an error, could warn that it's an unrecognised flag. Could ask you if you meant --help. Infer you mean help and give you that, or it could give you a choo Choo train running across the screen. Or it could reformat your hard drive. Just because it isn't specifically listed as UD doesn't mean it's not. If it isn't defined then it's undefined. The question is what is the reasonable thing to do when someone types --hlep. I hope we can agree reformating your hard drive isn't the most reasonable thing to do.
>I think you're confusing UB with unspecified and implementation defined behavior
Am I? What's the reason for not defining integer overflow? Yes unspecified behaviour could be used to allow portability, but so can undefined.
>It's fine if you think something shouldn't be UB, but you have to go lobbying the C standard for that. Compiler writers aren't to blame here.
I'm not saying it shouldn't be UB. I'm saying there's reasonable and unreasonable things to do when you encounter UB. In the article the author took reasonable steps to protect themselves and the compiler undermined that. That isn't reasonable. In exactly the same way that --hlep shouldn't lead to my hard drive getting reformatted.
C gives you enough rope to hang yourself. It isn't required for GCC to tie the noose and stick your head in it though.
I think you're confusing UB with unspecified and implementation defined behavior
I honestly don't understand the point of this paragraph.
> Am I? What's the reason for not defining integer overflow? Yes unspecified behaviour could be used to allow portability, but so can undefined.
Yes, you are confused about that. UB is precisely the kind of behavior where the C standard deemed it unsuitable to define as implementation defined or whatever, and it usually has really good reasons to do so. You could look them up instead of asking rhetorically.
> I'm not saying it shouldn't be UB. I'm saying there's reasonable and unreasonable things to do when you encounter UB. In the article the author took reasonable steps to protect themselves and the compiler undermined that. That isn't reasonable. In exactly the same way that --hlep shouldn't lead to my hard drive getting reformatted.
Again, you seem to fundamentally misunderstand how compilers work in this case. They largely don't "encounter" UB; It's optimization passes are coded with the assumption that UB can't happen. The ability to do that is fundamentally the point of UB. Situations like in the article are not a specific act of the compiler to screw you in particular, but an emergent result.
Additionally, I think you you're also confusing Undefined Behavior with 'behavior of something that is undefined'. These are not the same things.
Which is as wrong as coding GCC to assume --hlep can't happen.
It will happen and you need to deal with it when it does, and there are reasonable and unreasonable ways of dealing with that.
If you don't understand my --hlep example how about: Int mian () {
What should the compiler do there? Same rules apply should it reformat your hard drive or warn you that it can't find such a function? There are reasonable and unreasonable ways to deal with behaviour that hasn't been defined.
If I put in INT_MAX + 1 it isn't reasonable to reformat my hard drive. The compiler doesn't have carte blanche to do what it likes just because it's UD. It should be doing something reasonable. To me removing an overflow check isn't reasonable.
If you want to have a debate about what is reasonable we can have that debate but if you're going to say UB means anything tlcan happen then I'm just going to ask why it shouldn't reformat your hard drive.
> It will happen and you need to deal with it when it does, and there are reasonable and unreasonable ways of dealing with that.
A compiler's handling of UB simply can't work the same way handling flag passing works in GCC. Fundamentally.
With GCC, the example is something like:
if (strcmp(argv[1], "--help") == 0) { /* do help */ } else { /* handle it not being help, for example 'hlep' or whatever */ }
Compilers don't and can't work this way. There is no 'if (is_undefined_behavior(ast)) { /screw the user / }'. UB is a property of an execution, i.e. what happens at runtime, and can't _generally_ be detected at compile time. And you very probably do not want checks for every operation that can result in UB at runtime! (But if you do, that's what UBSan is!).
So, the only way to handle UB is either
1) Leaving the semantics of those situation undefined (== not occuring), and coding the transformation passes (so also opt passes) that way.
or
2) Defining some semantics for those cases.
But 2) is just implementation defined behavior! And that is what you're arguing for here. You want signed integer overflow to be unspecified or implementation defined behavior. That's fine, but a job for the committee.
It's basically dead code removal. X supposedly can't happen so you never need to check for X.
The instance in the article is about checking for an overflow. The author was handling the situation. C handed him the rope, he used the rope sensibly checking for overflow. GCC took the rope and wrapped it around his neck. Fine GCC (and C) can't detect overflow at compile time and doesn't want to get involved in runtime checks. Leave it to the user then. But GCC isn't leaving it to the user it's undermining the user.
Re 2) (are you referring to gccs committee or the c committee?)
I don't mind what it's deemed to be, I expect GCC to do something reasonable with it. Whatever happens a behavior needs to be decided by someone. Some of those behaviours are reasonable some aren't. If you're doing a check for UB, the reasonable thing, to me is to maintain that check.
I could make a choice when I write an app to assume that user input never exceeds 100 bytes. I could document it saying anything could happen, then reasonably (well many people would disagree) leave it there, that is my choice.
If you come along and put 101bytes of input in you would complain if my app then reformatted your hard drive. Wouldn't you also complain if GCC did the same?
There's atleast a post a week complaining about user hostile practices with regard to apps. Why do compiler writers get a free pass? If I put up code assuming user input would be less than 100 bytes documented or not, someone would raise that as an issue so why the double standard.
I'm not even advocating the equavalent of safe user input. I'm advocating that just because you go outside the bounds of what is defined, you do something reasonable.
The problem is that you need to do the check before you cause UB, not after, and here the check appears after. If you do the check before, the compiler will not touch it.
The compiler can't know that this code is part of a UB check (so it should leave it alone), whereas this other code here isn't a UB check but is just computation (so it should assume no UB and optimise it). It just optimises everything, and assumes you don't cause UB anywhere.
Now, I'm not defending this approach, but C works like this for performance and portability reasons. There are modern alternatives that give you most or all of the performance without all these traps.
Is it more performant?
How would you do the check in the article in a more performant way?
Philosophically I'm not sure it's even possible. Sure you could do the check before the overflow but any way you slice it that calculation ultimately applies to something that is going to be UB so the compiler is free to optimise it out? Yes you can make it unrelated enough that the compiler doesn't realise. But really if the compiler can always assume you aren't going to overflow integers, then it should be able to optimise away 'stupid' questions like 'if I add X and y, would that be an overflow?'.
>The compiler can't know that this code is part of a UB check
If it doesn't know what the code is then it shouldn't be deleting it. It has just rearranged code that it knows is UB, it is now faced with a check on that UB. It could (and does) decide that can't possibly happen, because 'UB'. It could instead decide that it is UB and so doesn't know if this check is meaningful or not, and not delete the check, this to me is the original point of UB, C doesn't know whether your machine is 1s complement, 2s complement or 3s complement, it leaves it to the programmer to deal with the situation, if the programmer knows he's working on 2s complement machines that overflow predictably he can work on that assumption, the compiler isn't expected to know, but it should stay out of the way because the programmer does. The performance of c as I understood it is that overflow check is optional, you aren't forced to check. But you are required to ensure that the check is done if needed, or deal with the consequences.
Would you get rid of something you don't understand because you can't see it doing something useful. Or would you keep it because you don't know what you might break when you delete it? GCC in this case is deleting something it doesn't understand. Why is that not a bug?
No, if you never do the calculation it's not going to be UB.
int8_t x = some_input();
if (x > 10) return bad_value;
else x *= 10;
> It has just rearranged code that it knows is UB
No - that's the problem. The compiler doesn't know that the code is UB, because this depends on the exact values at runtime, which the compiler doesn't know.
In some limited cases it could perform data flow analysis and know for sure that it will be UB, but those cases are very limited. In general there is no way for to know. So there are three things it could do:
A) Warn/error if there could possibly be UB. This would result in warnings in hundreds of thousands of pieces of legitimate code, where there are in fact guarantees about the value but the compiler can't prove or see it. It would require much more verbose code to work around these, or changing the language significantly. For example, you could represent this in the type system, or have annotations.
B) Insert runtime checks for the UB. This would have a significant performance overhead, as there are lots of "innocent" operations in the language that, in the right circumstances, lead to UB. So we would bloat the code with a lot of branches, 99.999% of which will never ever be taken, filling up the instruction cache and branch predictor. You get something more like (the runtime behaviour of) Python or JavaScript. Or even C if you enable UBSan.
C) Assume that the programmer has inserted these checks where they are needed, and omitted them where they are not. You get performance, but in exchange for that you are responsible for avoiding UB. This is what C chooses.
> C doesn't know whether your machine is 1s complement, 2s complement or 3s complement, it leaves it to the programmer to deal with the situation, if the programmer knows he's working on 2s complement machines that overflow predictably he can work on that assumption, the compiler isn't expected to know, but it should stay out of the way because the programmer does
This is mostly right, but with the caveat that you can't invoke UB. If you want to deal with whatever the underlying representation is, cast it to an unsigned type and then do whatever you want with it. The compiler will not mess with your unsigned arithmetic, because it's allowed to wrap around. But for signed types, you are promising to the compiler that you won't cause overflow. In exchange the compiler promises you fast signed arithmetic.
This promise is part of the language, not part of GCC. If you removed that promise, you would have to pay the price in reduced performance.
Could you have a C compiler that inserts these checks? Yes (see UBSan). But you would be throwing away performance - it would be slower than GCC/Clang/MSVC/etc. If you're writing performance-sensitive software, you are better off either ensuring you never trigger UB, or use another language like Rust. If performance is not so important, you are probably better off writing the thing in Go/JavaScript/whatever.
int8_t x = some_input();
if (x > 10) return bad_value;
else x *= 10
If you have: Long long x = ?; Long long y = ?;
If (????); x *= y;
>No - that's the problem. The compiler doesn't know that the code is UB
Ok I should properly have said, code it can't prove isn't UB.
If it can't say X + y isn't an overflow it shouldn't just assume it can't.
If y is 1 and X is probably 9 it wouldn't be reasonable to assume the sum is 10.
>C) Assume that the programmer has inserted these checks where they are needed, and omitted them where they are not. You get performance, but in exchange for that you are responsible for avoiding UB
You get the performance by avoiding option B. I'm not even sure the programmer is responsible for avoiding UB? UB just doesn't give guarantees about what will happen. You should still be able to invoke it, and I would contend, expect the compiler to do something reasonable.
long long x = (...);
long long y = (...);
long long z;
// Portable
bool ok = x == 0 || y == 0;
if (!ok) {
long long a = x > 0 ? x : -x;
long long b = y < 0 ? y : -y;
if ((x > 0) == (y > 0))
ok = -LONG_LONG_MAX / a <= b;
else
ok = LONG_LONG_MIN / a <= b;
}
if (ok)
z = x * y;
// Compiler-specific
bool ok = !__builtin_smulll_overflow(x, y, &z);
Slightly worrying that I didn't come across this or a variation in my searches
I'm glad I don't live in your country, where the C standard has been incorporated into law, making it illegal for compiler writers to do things that are helpful to programmers and end users, but aren't required by the standard.
No, that's wrong. Implementation-Defined Behavior is supposed to allow C to be implemented on different architectures. In those cases, the implementation must define the behavior itself, and stick with it. UB, on the other hand, exists for compiler authors to optimize.
If you want to be mad at someone, be mad at the C standard for defining so much stuff as UB instead of implementation-defined behavior. Integer overflow should really be implementation-defined instead.
And since you want some cross-compiler compatibility, you also import's third parties implementation defined UB.
This is not some conceptual reasonable decision, the proper way would be to throw out compilation on each UB behavior. The reality is that the proper way would be too harsh on existing codebase, making people use a less strict compiler or not updating version, which are non-desirable effects for compilers writers.
Is it? We're talking about integer overflow here.
I wasn't in the meetings when writing all the c standards. I'm not convinced this is purely an optimisation thing though.
I would guess the story is more.
Interested party X: "can integer overflow do X?"
Party Y: "no because our processor doesn't work like that.
Party Z: "and it breaks K and R"
Party X: "how about implementation defined?"
Party A: "but our compiler targets 5 different processors"
Party B: "plus that precludes certain optimisations"
Was this really the original reason why there's UB in the C standard, or has this been retconned by 'malicious compiler authors'? ;)
But where IB can have useful definitions to document, UB was defined so because the behaviours were considered sufficiently divergent that allowing them was useless, and so it was much easier to just forbid them all.
s/exists for/has been exploited by/g
The worst part is the optimizations aren't even that significant. (I recall a blog post of somebody testing this but I can't find it rn)
Well no, it's a compilation error, you need at the very least a semicolon after hlep and from there on it depends on what GCC is. If it's a function you need parentheses around --hlep, if it's a type you need to remove the --, if it's a variable you need to put a semicolon after it,...
Because GCC is all-caps I'm guessing it's a macro, so here's an example of how you could write it (though it won't be UB): https://godbolt.org/z/dYMddrTjj
Yeah sure, if my phone auto incorrects gcc to GCC then that is technically meaningless so you're completely free to interpret my comment how you want.
..... Although..... GCC stands for GNU Compiler Collection so it can be reasonably capitalised, so maybe then, rather than saying anything goes we should do something reasonable because then you aren't left saying something really stupid if you're wrong???
https://shafik.github.io/c++/undefined%20behavior/2019/05/11...
Anything can happen with undefined behaviour, including exactly what you would expect to happen for five years, and then everything breaks.
Compiling and running as if nothing is amiss is exactly how UB is allowed to look like.
Yes, and this is a "billion-dollar mistake" that's responsible for an ongoing flow of CVEs.
(the proposal to replace "undefined" with "implementation-defined" may be the only way of fixing this, and that gets slightly easier to do as the number of actively maintained C implementations shrinks)
But you typically can’t prove that. There’s lots of code where you could prove it might happen at runtime for some inputs, but proving that such inputs occur would, at least, require whole-program analysis. The moment a program reads outside data at runtime, chances are it becomes impossible.
If you want to ban all code that might invoke it it boils down to requiring programmers to think about adding checks around every addition, multiplication, subtraction, etc. in their code, and add them to most of them. Programmers then would want the compiler to include such checks for them, and C would no longer be C.
If, as you seem to say, you want to ban a subset that’s easily provable, I think enabling all warnings already does that. See for example https://clang.llvm.org/docs/DiagnosticsReference.html#wargum..., https://clang.llvm.org/docs/DiagnosticsReference.html#warray..., https://clang.llvm.org/docs/DiagnosticsReference.html#winteg... , https://clang.llvm.org/docs/DiagnosticsReference.html#wcompa...
No, I specifically ruled out doing that in my comment.
I was referring to the situation where a null check was deleted because the compiler found UB through static analysis.
(Or specifically, placing a null check after a possibly-null usage. It is wrong to assume that after possibly-null usage the possibly-null variable is definitely-null.)
If the pointer can't be null, then code that only executes when it is null is dead code that can be pruned.
Voila, null check removed. And most relevantly, it didn't at any point know "this is undefined behaviour". At worst it assumed that dereferencing a null would mean it wouldn't keep executing.
Various optimisation phases in compilers try to establish the possible values (or ranges) of variables, and later phases can then use this to improve calculations and comparisons. It's very generic, and useful in many circumstances. For example, if the compiler can see that an integer variable 'i' can only take the values 0-5, it could optimise away a later check of 'i<10'.
In this specific case, the compiler reasoned that the pointer variable could not be zero, and so checks for it being zero were pointless.
In essence, the compiler is allowed to assume that your code is valid and will only do valid things.
if (x < 0)
return 0;
int32_t i = x * 0x1ff / 0xffff;
if (i >= 0 && i < sizeof(tab)) {
For example you would you not expect a compiler to remove a redundant bound check if it can infer that an index can't be out of range?
Then it encountered evidence explicitly contradicting that assumption (a meaningless null check), and it handled it not by changing its assumption, but by quietly removing the evidence.
> For example you would you not expect a compiler to remove a redundant bound check if it can infer that an index can't be out of range?
If it can infer it from actually good evidence, sure. But using "a pointer was dereferenced" as evidence "this pointer is safe to dereference" is comically bad evidence that only the C standard could come up with.
Do you think the compiler would be right to remove the second check here?
if (!x) std::abort();
if (!x) return;
... = *x;
[[noreturn]] void my_abort();
What if my_abort returns instead? Or another thread changes x after the fact?
It's been long enough since I wrote C that I'm not familiar with that noreturn syntax or the contract I guess it implies, but control flow analysis which can prove the code will never be run, should all ideally warn me about it so that I can remove it in the source code, not quietly remove it from the object code.
I'm not demanding that it should happen in every case, but the cases where it's undecidable whether a statement is reachable or not, obviously it's undecidable for purposes of optimizing away the statement too.
if (!x) std::abort();
if (!x) return;
int *x = libX_foo();
if (!x) {
return;
}
...
Should the compiler complain? Should you remove the check?
Consider that libX_foo returning not-null might not be part of the contract and just an implementation detail of this version.
Yes and yes.
> Consider that libX_foo returning not-null might not be part of the contract and just an implementation detail of this version.
How is it an “implementation detail” whether a procedure can return null? That's always an important part of its interface.
Also consider code that call libX_foo via a pointer. After specialization the compiler might see that the check is redundant, but you can't remove the check because the function might still be called with other function pointers making full use of the contract.
I'd expect any reasonable library to say “libX_foo returns null if [something happens]”. What use is there in a procedure that can just return null whenever it feels like it?
In gpderetta's example, the interface contract for that function says "it can return null" (which is why the calling code has to check for null). The implementation for this particular version of the libX code, however, never returns null. That is, when the calling code is linked together with that particular version of the libX interface, and the compiler can see both the caller and the implementation (due to link-time optimization or similar), it can remove the null check in the caller. But it shouldn't complain, because the null check is correct, and will be used when the program is linked with a different version of the libX code which happens to be able to return null.
For a more concrete example: libX_foo is a function which does some calculations, and allocates temporary memory for these calculations, and this temporary allocation can fail. A later version of libX_foo changes the code so it no longer needs a temporary memory allocation, so it no longer can fail.
And LTO is not even necessary. It could be an inline function defined in a header coming from libX (this kind of thing is very common in C++ with template-heavy code). The program still cannot assume a particular version of libX, so it still needs the null check, even though in some versions of libX the compiler will remove it.
I mentioned LTO because compilation units were seen in the past as safe optimization barriers.
You can say that but in practice -Onone is fairly close to what you're asking for already. Most people are 100% unwilling to live with that performance tradeoff. We know that because almost no one builds production software without optimizations enabled.
The compiler is not intelligent. It just tries to make deductions that let it optimize programs to run faster. 99.999% of the time when it removes a "useless" null check (aka branch that has to be predicted and eat up branch prediction buffer space and bloats up the number of instructions) it really is useless. The compiler can't tell the difference between the useless ones and security critical ones because all of them look the same and are illegal by the rules of the language.
Even if you mandate that null checks can't be removed that doesn't fix all the other situations where inserting the relevant safety checks have huge perf costs or where making something safe reduces to the halting problem.
FWIW I agree that the committee should undertake an effort to convert UB to implementation-defined where possible... for example just mandate twos complement integer representations and make signed integer overflow ID.
To illustrate the complexity: most loops end up using an int which is 32-bit on most 64-bit platforms so if you require signed integer wrapping that slows down all loops because the compiler must insert artificial checks to make the 64-bit register perform 32-bit wrapping and we can't change the size of int at this point.
To accomodate trapping implementations you'd have to make it "implementation-defined or an implementation-defined signal is raised" which it happens is exactly the wording for when an out-of-range value is assigned to a signed type. In practice it means you have to avoid it in your code anyway because "an implementation-defined signal is raised" means "your program may abort and you can't stop it".
The compiler hasn't found UB through static analysis, it has found a redundant null check.
Things like that meaningless null check mentioned, can definitively be found statically (the meaningless arithmetic sanity check in OP's example, I'm not so sure, at least not with C's types).
There are languages that specify what a compiler has to do (e.g. Java w.r.t. “definite assignment” (https://docs.oracle.com/javase/specs/jls/se9/html/jls-16.htm...)), and thus require compilers to reject some programs that otherwise would be valid and run without any issues, but C chose to not do that, so compilers are free to not do anything there.
It's just that it used this proof to remove the conditional evaluation (and the branch) instead of warning the user that he was making a nonsensical if statement.
So to the question of "when can we hope to do it" the answer is, "not in all cases, sure, but certainly in this case".
("unsafe" (aka "trust me" mode) means that's not quite true, and so do some of the warnings and errors that you can enable on a C compiler, but it's close enough)
The problem with making the compiler give warnings on dead code elimination (which is what deleting things after UB really boils down to) is that it just happens so much, due to macros, inlining, or anything where you may check the same condition once it has already been asserted (by a previous check, or by construction). So you'd need some way to trace back whether the dead-ness comes directly from user-written UB (as opposed to compiler-introduced UB, which a compiler can do if it doesn't change the resulting behavior; or user-intended dead code, which is gonna be extremely subjective) which is a lot more complicated. And dead code elimination isn't even the only way UB is used by a compiler.
That's the most important point! You simply cannot detect overflow when multiplying integers in C after the fact. This is not GCC's fault.
I agree that some of the optimizations exploiting UB are too aggressive, but the article presents a really bad example.
No, it's puerile interpretations of the C standard learned from the comp.lang.c newsgroup and such places rather than from engineering work.
I had read it a long time ago, and had since forgotten the source. I've spent a few hours trying to find it in bug-trackers. really glad to have the link now, thanks!
"Possible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message)."
Ignoring the situation completely means exactly that: completely. The situation is not being ignored completely if the compilation of something which follows is predicated upon the earlier situation being free of undefined behavior.
OK, so since the situation is not being ignored completely, and translation or execution is not terminated with a diagnostic message, it must be that this is an example of "behaving in a documented manner characteristic of the implementation". Well, what is the characteristic; where is it documented? That part of the UB definition refers to documented extensions; this doesn't look like one.
What is "characteristic of the implementation" is in fact that when you multiply two signed integers together with overflow, that you get a particular result. A predictable result characteristic of how that machine performs the multiplication. If the intent is to provide a documented, characteristics behavior, that would be the thing to document: you get the machine multiplication, like in assembly language.
You may dislike it, but that is not how UB in C and C++ works. See [1] for a guide to UB in C/C++ that may already have been posted elsewhere here.
It is a common misconception that UB on a particular operation means "undefined result", but that is not the case. UB means there are no constraints whatsoever on the behavior of the program after UB, often referred to as "may delete all your files". See [2] for a real-world demo doing that.
[1] https://blog.regehr.org/archives/213
[2] https://kristerw.blogspot.com/2017/09/why-undefined-behavior...
The C standard imposes no such constraint on undefined behaviour, neither is it the case that real compilers always behave as if it did.
hxhxhrra has already shown this, but here's another good blog post on this kind of thing: https://markshroyer.com/2012/06/c-both-true-and-false/
This -fno-delete-null-pointer-checks flag is just yet another fix for insane compiler behavior and it's not the first time I've seen them do it. I've read about the Linux kernel's troube with strict aliasing and honestly I don't blame them for turning it off so they could do their type punning in peace. Wouldn't be surprised if they also had lots more flags like -fwrapv and whatnot.
Having said that I’m of split feelings here. I work in a very performance sensitive industry and on one hand welcomes the ability of compilers to use the knowledge that certain things “can’t happen” to optimize, without me having to always do these optimizations be hand.
On the other hand, there seem to be so many cases like this one where the “undefined behavior code deleter goes brrrrrr” really overextends its usefulness. The “lalalalala standard say I can do this can’t hear you” finger in your ears attitude from compiler maintainers doesn’t help at all either.
I understand that the way much of this works, propagating “poison/impossible values”, can hide the root cause, so you can’t just say “please do the good undefined behavior optimizations but not the bad, so there’s no easy answer. The outcome in the blog post doesn’t feel like a local optimum though, and it’s not the only place I’ve felt that your options are “potentially slow code” or “pray you were perfect enough to not have your program deleted”
This is not new, -fwrapv was introduced in 2003, but it can quite severely impact code quality, if you don’t care, just set that. Then complain that C is slow, because C is a shit language.
How so? How does breaking an if statement the programmer added make the code faster? If they intended the check not to happen/be required, they wouldn't have written it. Let signed int overflow and leave any code that depends on its value alone. So yes maybe make fwrapv the default.
> because C is a shit language.
Well, it's as low level as it can get before reaching assembly, but why not try reducing the number of foot guns? Sometimes you still need C, and that's not going to go away for the foreseeable future.
See your problem is that you’re
1. not thinking like a compiler
2. and reasoning on an isolated example
The compiler does not “break an if statement”, the compiler uses the UB to limit the range of the input and output, it can then propagate this range analysis to see that the check is dead code, and so removes the dead code.
It’s common for users to write unnecessary or redundant checks, even more so because of inlining, and especially macros.
If you’re carefully checking for null in every function prologue, and the compiler in-line everything and knows the pointer is non-null, all checks are dead and can be removed. Which is what the compiler does. This reduces the amount of branches (and thus the space needed by the branch predictor), and reduces the amount of code meaning the new inlined function could fall below threshold and itself become a candidate for inlining.
Also I agree you should not write code like that example and rather move the check up.
But reality is we (at least I) still depend on code written in C, like openssh, and want it to be as safe as possible. Now I can blindly trust the devs know every UB in the C spec in and out, run all the static and dynamic analysis tools in existence, but it would just make me feel even more safe if the compiler would also work with them, not against. Somewhere here in the comments it was claimed that the linux kernel for example already uses -fwrapv and its performance seems absolutely fine to me. And I'd suspect that an OS kernel is already on the more performance critical end of the spectrum regarding stuff written in C that's still in use.
I just find it worrysome that such evidently unsafe optimizations are the default, and not hidden behind some sufficiently scary-sounding flag.
A somewhat common example I've seen is sign extension in loops, where the width of the loop variable is not the same as that of the CPU register [0]. If the compiler can assume that signed integer overflow is UB, then it has a lot more freedom to unroll/vectorize the loop [1] (remove -fwrapv and watch Clang go to town).
Of course, that specific optimization is rendered somewhat moot if the programmer chooses to use a 64-bit loop variable, but that is a slightly different rabbit hole.
> If they intended the check not to happen/be required, they wouldn't have written it.
I feel that's somewhat iffy reasoning - if we trust the programmer so much, why allow the implementation to optimize in the first place? And if not to that extreme, where should the line be drawn?
[0]: https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759...
Yes, the optimization is "easily" solved, but a) it'll probably be some time until people stop teaching/using int as a loop variable, and b) there's lots of existing software out there, and perhaps optimizer improvements are an easier performance win than looking for the right loops to change.
And yes, profiling is ideal, but I can't say whether I agree off the top of my head whether this loop would be immediately obvious, or whether the fix would be obvious. It may be to us and/or the average HN reader, but I don't know how universal that knowledge base is.
One thought that just occurred to me is that while signed overflow may be useful for loop optimizations now, I suspect that it wouldn't have been useful in the same way back when C was first standardized. Wonder what the committee's reasoning for that was, if there was any...
Right. If you want each line of code to be loaded and executed precisely in sequence, exactly as written, then you know where to find Python.
The reason why C++ is always relevant here (though C macros and inlining cause similar issues) is that generic programming being close to optimal is a language feature - and one of the ways that's possible is by letting you right reusable code that might be "called" from a context in which some of the checks or conditions just aren't necessary. It's by design that the optimizer gets to... well, optimize that kind of code.
There's a solid case to be made that the details of C's UB weren't well chosen and we should try to update them; but which decades old choices are perfect? Which are easy to change once there's this much legacy software in operation?
Don't forget that some of those UB's were chosen to deal with hardware realities of the day; i.e. that the "same" operation on different hardware would do different things. For example, eliminating signed integer overflow might allow a C compiler to use a signed register that's wider than necessary, which may help on hardware that doesn't have every possible register width, or where there are complex register usage limitations. I'm no hardware geek; I'm sure somebody here knows or real examples where UB allows portability, because that's the point: UB allows people to write portable, performant code - just don't do certain things, and you're fine... which leads us to today's situation, in which UB can feel like a minefield.
That's an argument for implementation defined behaviour. Not for undefined behaviour, at least not UB in the modern sense.
If that is what you want, compilers have various flags that let you in essence do that. But the next problem with that is (1) that it's possible existing code may be suddenly and unpredictably lose performance, and (2) now you need to provide some other well-defined behavior for those UB cases, and (3) the selling point of generics/macros/inlining may be reduced.
How many relevant UB's are there? I don't know. How much perf would code common lose? I don't know. To be sure, I fully acknowledge that removing UB from the spec may be the right thing to do, but it's also easy enough to find possible problems with that strategy; I'm just pointing out the complexities, which is a lot easier than solving them or knowing which are irrelevant.
Not any more than UB does. Ie if you avoid the implementation defined behaviour, your code is perfectly portable.
(And otherwise your code could probe for what the implementation defined behaviour is, and adjust accordingly. No such luck with UB.)
However I do agree with you that it's hard to remove UB from the spec. The spec's failing is in having so much UB in the first place.
Removing a comparison because of UB is fucking stupid. The compiler on the one hand assumes that the programmer is diligent enough to consider of every invocation of UB, but on the other hand too stupid to see the check they wrote will always be true.
It's not a good idea.
For example, imagine you have some SIM wide value, and you want to do something to each word or byte that the SIMD value contains. In today's C, you can just write a bunch of ifs: is width < 2? then... is width < 4? then... etc. The compiler with completely elide those ifs and leave behind only the reachable code - if it can specialize that re-used code for the given context.
Furthermore, today those checks might be implicit via the use of UB. That's perhaps not a great solution looking at the entire ecosystem, but it is the situation we're in. Changing that might be quite a lot of work.
I just don't like that it derives preconditions from UB.
It's a lot easier to reason about code for instance when the domain of signed integer addition is all pairs of integers, not just a subset thereof.
Ideally, buffer overflows would also be defined - but without lifetime analysis ala rust or runtime costs, that's going be hard. But given how many stack guarding techniques there already are, perhaps we're closer to this than I think?
It means I can write clear code, guard things rather than explain in a comment why the guard isn't needed, and know that the compiler will remove the inefficient code. In general, optimizing compilers mean that taking the clearer option is much less of a performance loss. I like that.
In many of these UB cases, the annoying things is that the compiler removes the safety feature you explicitly added, but there are plenty of alternatives.
Your application, and the application programmer, instead fail to fulfill those compiler assumptions.
These days undefined overflow for signed integers is mostly used by compilers to be able to assume that eg 'a + 1 > a' is always true, and thus eliminate redundant checks.
(And you wouldn't typically write code like 'a + 1 > a', but you can get either from code generation via macros etc or as a intermediate result from previous optimization passes.)
These days the whole point of C is this Faustian pact with the devil of speed for sanity.
Yet, they still compare favourably with C in this regard. Almost anything does.
If an optimising C compiler can’t rely on UBs not happening, its potential is severely cut down due to the dearth of useful information provided by C’s type system.
To be honest, that's just how compiler writers interpret UB these days.
It's perfectly possible (in principle) to use lots of more sophisticated static and dynamic analysis to recover much of what C compiler just assume. You don't have to restrict yourself to what C's type system provides.
(For an example of what's possible, have a look at all the great techniques employed to make JavaScript as fast as possible. They have basically no static types to work with at all.)
I’m sure people will be very happy with a C JIT. That’s definitely what they use C for.
JIT-ed code is full of runtime type and range assertions which bail if the compiler’s assumptions are incorrect.
Instead of just assuming that 'x > x + 1' is always true (for signed integers), the compiler could also do the heavy lifting of static analysis (for cases where that's possible).
For something better matching: have a look at things like Coverity for what you can recover with static analysis of existing C code.
Make overflow on a signed int defined. Create a new type called unsafe_int where it is not.
So then the compiler writers get to implement their pointless optimization pit traps. And everyone else can avoid those by banning unsafe_int.
I meant to talk more abstractly about UB in general.
The way to start getting rid of it would be to add for...in... loops or something where the loop index can be a custom no-overflow type.
And "defining" it is a lame approach to safety. If you make it wraparound, you now have silent wraparounds that can't be found by static analysis. You want unintended overflows to trap, not just be defined.
Yes. But even the lame approach is better than UB, because it doesn't bring the whole program down.
My take is all of the low hanging fruit optimizations that the standard enables has been picked a long time ago. Everything left is problematic.
In many other domains, other languages have taken their place, and this will keep on going, even if it takes a couple of generations, or goverment cybersecurity mandatates to make it happen.
For a real prominent counterexample: the Linux kernel is intentionally programmed in a C dialect (defined by a myriad of GCC compiler flags) that removes a lot of UB.
If they craved the Faustian bargain of UB for speed, they could immediately move in that direction by dropping some GCC options.
There's nothing "easy" at all about UB-exploiting performance optimizations in modern C compilers, and "ease of implementation" is absolutely not why those optimization passes have been included. In fact, the easiest thing for the compiler to do, when it sees an int * int operation, is to emit an IMUL assembly instruction (or the equivalent for your CPU architecture) and not worry about deleting overflow checking code. Which is what C compilers did before the extent of UB exploitation became excessive.
This is -- or at least was -- a feature, not a bug. You can implement any valid program, but you can also implement some invalid programs.
I know the OP mentioned Rust, but it's a valid comparison: if you don't invoke "unsafe" then all your behaviour is well-defined. But the trade-off is that Rust will only let you implement a subset of valid programs unless you invoke "unsafe", which might be better termed "assumed correct".
If the programmer had specifically invoked the "__assert_valid_pointer(p)" standard function (which does not exists) to promise the compile that the pointer was valid then it would be fine.
The problem is that there are a lot of places where the compiler makes these assumptions.
Which is why everyone should adopt static analysis tooling and enable all the warnings that are related to UB, pointer and casts misuses.
Many think they know better, it is like those that think builders don't need protection gear at a construction site, it is stuff only for the weak.
It will have a non-trivial cost, but hopefully aggressive optimizations can remove many of these checks (which ironically it is exactly the kind of optimizations people are complaining about) and compilers provide pragmas to disable them when critical.
In a way sanitizers are getting there, but they are explicitly marked as for non-production use which is a problem.
https://isocpp.org/files/papers/P2723R0.html
Lots of people telling him it will never fly in production, while their Windows and Android phones are using the code that they say isn't good enough.
I'm still moderately optimistic. I suspect that many of these checks will end up being enabled by default on compilers shipped by distros, like stack guards and other forms of hardening.
1) The compiler sees an expression like "a += b;" where a and b are signed integers.
2) It emits "add rA rB" in x86 assembly (rA/B being the register a/b is currently in).
3) Technically the machine code emitted does not match the semantics of the source code, since it uses wraparound addition, whereas the C standard says that for the operation to be valid, the values of a and b must be such that no overflow would occur. This is fine however, because the implementation has the freedom to do anything on integer overflow, including just punting the problem to hardware as it did in this case.
4) The compiler proceeds with the rest of the code as if the line above would never overflow. My brother in the machine spirit, you chose to translate my program to a form where integer overflow is defined.
The compiler should either a) trap on integer overflow; or b) accept integer overflow. It will be fine if it chooses either a) or b) situationally, i.e. if we have a loop where assuming no overflow is faster, then by all means - add a precondition check and crash the program if it's false, but don't just assume overflow doesn't happen when you explicitly emit code with well-defined overflow semantics.
The bigger problem is there is pretty much no way to guard against this. The moment your program is longer than one page you're screwed. You may think all your functions are fine, but then you call something from some library, the compiler does some inlining and suddenly there's an integer overflow where you didn't expect, leading to your bounds check being deleted.
I would simply not depend on invoking UB as part of my program's behavior (?).
Alas, it's nearly impossible for a mere mortal to write any non-trivial C code that doesn't have UB.
Then they can add a #pragma optimize(assumes=no-int-overflow, whatever, etc) to precisely add optimizations when needed and you 'know' its safe.
Next generation of AI powered compilers will try to interpret code at a more abstract level and infer what the programmer was thinking even if they wrote the wrong thing.
Everything will work perfectly 100% of the time.
> runtime error: signed integer overflow: 50000000 * 511 cannot be represented in type 'int'
https://godbolt.org/z/oz9vvj5YM
Another heads up of the dangers of UB optimizations, and why using static analysis is a requirement for C derived languages.
If you aren't using all warnings turned on as errors, disabled implicit conversions and at very least have static analysis on the CI/CD pipeline, you're up for a couple of surprises.
From CppCon 2022, "Purging Undefined Behavior & Intel Assumptions in a Legacy C++ Codebase"
(The answer is: yes.)
The sanitizers (UB, address, memory, threads) are supported by both Clang and GCC [1]. Yes that's up to 4 different builds and tests runs but with an automated C/I this is not a big deal.
The Clang static analyzer, with Z3 enabled as a checker, used through CodeChecker [2] is now very good, so much so that I prefer it to a different commercial product showing too many false alarms. Using it on an embedded GCC cross-compiled code base may still require some workarounds, but nothing too bad and this is improving regularly too.
I wouldn't want to do without this. Switching to Rust may not always be possible, and there are big C and C++ code base that will live a long while. Tools like this help and they should be used.
So reboting into any safe alternative, is going to take decades, hence why the first step is still trying to advocate for best practices, even if it feels like a Quixotic endevour.
I'm sure you will be willing to write the GCC PR that implements the required, surely trivial, analysis.
You cannot “turn off UB”. The behaviour is undefined in the standard, and nothing the compiler can do will make it defined. There is a profound misunderstanding of what undefined behaviour is in a lot of the comments. It is not a compiler setting. The way to make it defined is to change the standard.
Going a step further, this places the article author outside GCC's main intended user group. It raises the question: Who are GCC's main intended users? And is there a way to more clearly advertise that the article author isn't part of them? This would probably help other potential GCC users to decide whether GCC is the right tool for them at all.
I don't really get the discussion about the C standard and UB in the other threads here. The standard and UB are only a tiny pixel in the big picture.
GCC implements a language. The intended users are people programming in that language, which implies some sort of proficiency. The author isn't aware of the pitfalls of said language.
This is not about GCC.
It really shouldn't be that difficult to wrap all these assumptions into a ‘if (can_exploit_ub)’. Then you can just pass something like -fno-exploit-ub and everybody's happy.
The argument about proficiency has been bruoght up multiple times already -- but only by one of the parties involved in the discussion, which shows that there is disagreement -- and besides that, makes a visit in literally every single discussion about usability.
Should all languages start warning about this or would it introduce too much clutter (much much code in real life doesn't touch upon external input or would otherwise be ok with errornous computations)? In many languages the second order-effects aren't usually dangerous (bounds checks) but for C/C++ the second order effects ARE dangerous.
In the end, GCC's users must use it, and they are the ones to give hints (ideally, answers) towards how GCC should behave in such a situation, e.g. whether GCC should prioritize optimization or (programmer's) fault tolerance.
I believe all languages that don't support bignums should do the same.
Thank you, for not using the word "begs".
The compiler, to avoid the division, compares x * 0x1ff with 512 * 0xffff instead of x * 0x1ff / 0xffff with 512. This comparison is obviously bunk, since it doesn't take the uppermost bits of the multiplication into account. But so is the original comparison!
You see the same thing happen in Rust -- https://rust.godbolt.org/z/xf67rM77T -- the difference being that there's a second language-level bounds-check inserted at the lookup site.
Edit: Though, incidentally, the comparison does not work the way it was probably intended to work. In `i < sizeof(tab)`, `i` is converted to `size_t`, so an unsigned comparison is performed, making the `i >= 0` part redundant. But the result is the same as what was intended.
Effects of UB are not temporal or spacial limited to the place where undefined behavior happens.
The moment you enter a compilation unit (assuming no link optimizations) with a state which at some point will run into undefined behavior all bets are of.
EDIT: Yes, UB can "time travel". Compared to that ignoring an if condition iff the UB code was triggered is harmless. Similar it can also "split realities". E.g. a value produced by UB might at one place have the value 1 and at another place a completely different value. E.g. unsigned int overflow values might for an if condition have one value and for the print statment in the condition another and for the index operation again a different value.
EDIT2: Which is why a lot of people which have proper understanding of C++ and don't have a sunken (learn C++) cost fallacy came to the conclusion that using C++ is a bad choice for most use-case.
Close, but not quite. This is a common misconception in the reverse direction.
Abstractly, what UB can do is performing the inverse of the preceding instructions, effectively making the abstract machine run in reverse. However, this is only equivalent to "time-traveling" until you get to the point of the last side effect (where "side effect" here refers to predefined operations in the standard that interact with the external world, such as I/O and volatile accesses), because only everything since that point can be optimized away under the as-if rule without altering the externally visible effects of the program.
As a concrete, practical example, this means the following: if you do fflush(stdout); return INT_MAX + 1; the compiler cannot omit the fflush() call merely because the subsequent statement had undefined behavior. That is, the UB cannot time-travel to before the flush. What the program can do is to write garbage to the file afterward, or attempt to overwrite what you wrote in the file to revert it to its previous state, but the fflush() must still occur before anything wild happens. If nobody observes the in-between state, then the end result can look like time-travel, but if the system blocks on fflush() and the user terminates the program while it's blocked, there is no opportunity for UB.
P.S. Have you ever seen a single example of a compiler time-traveling UB through observable behavior like this? I sure haven't. If you have, I'd love to see it, because despite all the crazy ways compilers take advantage of UB, I've never seen C/C++ compilers actually agree with the stance that this way would be somehow legal (if it's even logically possible).
if (x > 4) {
fflush();
int y = INT_MAX + 1;
}
The only real counter-argument I could see is "fflush might terminate the program, hence we need to run the function before we know if UB will be triggered". I suppose once you call a function that the compiler cannot analyze (e.g. system-calls, FFIs) the compiler may not be certain the function doesn't contain an 'exit()' call.
It seems this is correct, but there are very quick cases where the compiler does not consider a program 'pure'. Even a simple call to 'puts' already is enough to be compiled. Probably because it has side-effects in setting a value for ferror(file) to return.
I wonder if we can find an example of a function that is externally observable to a user, but that is guaranteed to finish. Then specifically i wonder if the compiler can proof that the undefined behavior is guaranteed to happen so it elides the branch, proving 'real' timetravel. That is observable.
I don't think the standard has such a thing, but if it did, the closest thing would probably be a write to a volatile variable. You'd have to make sure the compiler sees the variable as having a side-effect in the first place (so it would probably need external linkage).
Hence it won't trigger any undefined behavior.
But it is certainly 'legal' for the compiler to consider that statement to invoke undefined behavior, and prune any branch that is guaranteed to reach that statement.
The thing to realize is there is no such thing as "UB will be triggered". The only thing that exists is "UB is triggered", combined with the as-if rule, which allows modifications that don't affect what the standard considers observable behavior. Or in other words, the standard defines a program according to its observable behavior. People think it's time-travel because they think of the program in terms of expressions and statements rather than side effects, but if you think of the programs in terms of observable behaviors rather than the lines of code executing, you see that there's no time travel.
"However, if any such execution contains an undefined operation, this International Standard places no requirement on the implementation executing that program with that input (not even with regard to operations preceding the first undefined operation)."
Quote found here: https://devblogs.microsoft.com/oldnewthing/20140627-00/?p=63...
It seems that the standard explicitly disagrees with you.
(I have never actually seen a compiler act on this, but I maintain that this is just because they're either not willing to optimize on this or unable to do so. But there's a lot of UB that compilers do not exploit, so this isn't particularly concerning to me.)
False! The expression (INT_MAX + 1) has no side effect (assuming no UB), so according to the rules of the C abstract machine, the compiler is allowed to hoist this calculation above the fflush(). If you run this on a machine that traps on integer overflow (which is allowed behavior), the process could crash before the fflush() is executed. Remember, everyone: With UB, anything can happen.
Ultimately, my point here wasn't about fflush() or even about the specifics of what exactly constitutes observable behavior in the abstract machine. (I do recall writes to volatile variables was among them, but you'd have to check all of them to be sure.) Rather, my basic point was the fact (tautology?) that any interactions with the external world that affect the program's observable behavior necessarily must be allowed to happen before the program can "know" for certain that the execution path will trigger UB—which by definition isn't possible when one of the intervening operations is an opaque call.
I think the output of the Rust compiler is fine because it uses an unsigned comparison ("ja" as opposed to "jl") to implement the "if".
What actually happens is that 50000000*511 is 0x5F2E60F80, which is -219803776 when truncated to 32-bits and treated as signed. At the C abstract machine level this was UB, but at assembly level this is the value that is stored in the register and used for subsequent computations.
The compiler then says "this must be positive because I had already checked 50000000 and it was". So it only performs a signed check -219803776 < 512*511, which passes.
It's only inside the "if" that the code divides -219803776 by 65535. One could plausibly expect the result to be -3353, but the compiler decides to use an unsigned divide (again, it can do so because the input "must" be less than 2^31) and therefore it returns 61283.
But the test that's being removed is i>=0, not i<512.
I do not understand why the compiler would divide inside the 'if'...
At some point the conclusion may be that compilers are trying to be too smart for everyone's good.
I see, indeed the author did not explain entirely what was going on in the optimizer. Though he's correct that overflow is what causes the UB.
> I do not understand why the compiler would divide inside the 'if'...
Why not? A division is expensive, it makes sense to do it only if the result is used. Anyway the problem is not (just) the division, because you would still have problems if the compiler removes the comparison with 0 and also decides to use a signed division -219803776/65535.
Interestingly, there is also a chance that the compiler uses a double-precision intermediate result for the multiplication, using the x86 instructions IMUL and IDIV, because 65535>511 i.e. the final result is always smaller than the input (assuming infinite precision for intermediate results). In that case the compiler "fixes" the overflow entirely for you, but it can only do so exactly because the overflow is undefined behavior.
That does sometimes happen, and with macro expansion the similar "x = a * 10 / 100 -> x = a / 10" optimization also happens, but nobody complains because it fixes bugs in their code... ;)
Hell, rust has had codegen issues because it extensively leveraged features which are almost non-existent in C, and thus were little exercised and poorly tested.
Another thing to watch out for here (especially if anyone's trying to transpile Rust to C) might be C's strict aliasing rules accidentally getting applied to Rust raw pointers.
You're certainly not going to run into LLVM optimizing your bound-check out of existence because it occurs after an overflowing operation.
However in this case, the culprit wasn't comparison `a > b`, but assignment `a = b`.
In general, addition like 'a + b' also isn't safe in C.
The problem is the compiler going implementation defined on the multiplication/assignment then going all language lawyer on the following line and blaming the user
> In general, addition like 'a + b' also isn't safe in C.
Cool, another reason to retire it
The number being multiplied isn't known until runtime, so there's not a good way of doing this.
Just blindly accepting user input is universally bad methinks.
A C program is basically a bunch of bytes, and the C standard tells you what those bytes are supposed to mean. A compiler's job is to translate the bytes into whatever target language you fancy, and making sure to preserve the proscribed behaviour. And that's exactly what the compiler did.
The compiler has done range analysis and knows that at this point, x is non-negative. The programmer has dilgently ensured that values are such that the multiplication can't overflow, therefore the result of it is also non-negative. That means the later check for i being non-negative is trivially true.
If x == 0x804021 then x * 0x1FF yields 0x1DF, and then proceeed to access tab[0]. This is very probably NOT what the author wanted.
- Defined overflow doesn't help at all, in fact the compiler would preserve what is wrong in the first place
- overflow trap is a little bit better, at least you would get the occasion to think about it
Even if the compiler doesn't act on the UB the code is still wrong.
I get that the C standard cannot guarantee two's complement when C code can be compiled for other architectures. But looking at the list of supported architectures ( https://gcc.gnu.org/backends.html ), even exotic architectures like vax and microblaze seem to be two's complement.
Does gcc even support one's complement machines or those with CHAR_BIT != 8 ? If not, all those optimizations are utterly ridiculous. Basically an adversarial competition between compiler writers and users.
Non-8-bit char is a bit more common, probably the most common is TMS320 C5000, see https://lists.llvm.org/pipermail/llvm-dev/2009-September/026... for an example. As far as I know there is no GCC port, but it could very well have one, after all TMS320 C6000 port is upstream in GCC. (It is c6x in your table.)
Do you happen to know what compiler/language the UNIVAC folks use?
See Raymond Chen’s well known “undefined behaviour can result in time travel”.
Fun fact: not closing a string literal is UB. Ending a non-empty source file in anything other than a newline is also UB.
And 4.9 absolutely will do similar in other cases: fwrapv has existed since GCC 3.3 and fno-strict-overflow was introduced in GCC 4.2, which are flags to defeat these optimizations (and either of which avoids the crash on GCC 9.3)-- both introduced in response to increasingly effective optimization in prior GCC versions exposing errors like this. 4.9.2 just misses the optimization in this specific case.
This is about the least surprising UB. It didn't even travel backwards in time.
But is there are a reason for `i >= 0` not raising a warning if it can't happen? Or is there a warning that was not enabled? I think `i >= 0 cant be false` would save a lot of headache
edit: one post mentions macros. Which makes sense in that case I think. You can easily write such impossible conditions with macros, so making it a warning would add a lot of warnings I guess
Although there are warnings for `if (true)/if (false)` "this condition is always true/false"
Also, this UB optimization train has gone way too far and needs to back up a few stations.
I'm gonna say there needs to be a switch to make signed overflow not be UB. Maybe that already exists? starts checking docs
But I would not ever write something like this:
int32_t i = x * 0x1ff / 0xffff;
overflow is an error. I would prefer the code not to create errors unless absolutely needed.
So after checking that x > o there is no way for i (a product and ratio of positive numbers) to become negative.
The only reason this is surprising is that there is an expectation of wrapping on overflow. But this is simply not the behavior of the C virtual machine.
(Maybe today it makes sense to have even C wrap in a two’s-complement way? C is used in many places though, maybe there are still platforms in use that aren’t two’s-complement?)
For example, you don't want to have an overflow when calculating a total cost of ordered goods or size of an allocated memory block.
One could argue that it is a developer's responsibility to make sure overflow doesn't happen, but the history shows that developers usually fail to protect the program from such kind of errors. We have memory protection, why cannot we have overflow protection?
In my opinion, an overflow should cause an exception unless the program explicitly asks to ignore it. Of course this means that every addition now becomes a (very unlikely) conditional branch, but I guess this can be optimized by static prediction. Every memory access is already a conditional branch, and it doesn't cause problems.
But CPUs and programming languages seems to make writing overflow-safe code more difficult than unsafe. In assembly, you have to insert additional branch instructions, and in business-oriented languages like Java you have to write long sentences like Math.addExact(). If you write a complicated formula this way, it becomes unreadable.
Sadly, modern languages like Rust haven't fixed the mistake and also penalize writing safe code.
The only language I know with overflow protection is Swift: an overflow causes an exception there. Well done, Apple, you are lightyears ahead of open source software.
It is easy to write unsafe code and difficult to write safe code. As a result, while most mathematical operations must be safe, developers use unsafe operations because they are easier to type and more readable.
Operators like `+` should be equivalent to checked_add().unwrap(), not to unchecked_add(). Why choose unsafe and rarely used operation as a default? It is a mistake. Swift uses sane defaults.
UPD: for example, let's say we need to allocate memory for N elements of size S and a header of size H. Here is the unsafe code:
u32 s = N * S + H
u32 s = checked_add(checked_mul(N, S).unwrap(), H).unwrap()
let s: Uint32 = N * S + H
let s = N &* S &+ HIn your "unsafe" example in Rust, you still don't get undefined behavior.
https://huonw.github.io/blog/2016/04/myths-and-legends-about...
You get an unexpected behaviour instead. For example, imagine if you had a device for counting amount of bytes transferred over the network. If the counter overflows, you will get the wrong number, and issue an invalid bill to the customer. While that is a "defined" behaviour that is not what one expects.
I expect the counter either to work correctly according to normal math rules or indicate that it cannot perform the task due to hardware limitations.
One might blame the developer but history shows that developers fail to take account of overflow. For example, experienced developers writing Linux kernel made several mistakes, which lead to security vulnerabilities.
In most cases developers need standard math, not operations modulo 2^32 or 2^64. When you count bytes, you need an exact amount, not an amount modulo 2^32. Why do language designers provide modulo operations instead of normal math I don't understand.
Rust has chosen a weird path when the program works differently in debug and release mode. This is clearly wrong. I expect the same program to work the same way no matter whether optimizations are enabled or not.
Which CPU? There are a lot of CPU architectures and their variants, some older than 40 years, and C is supported on most of them. Each CPU has its use case. Also, safety is not always a top requirement.
But I also think that true safety will come at silicon level, and not from a programming language.
Safety is the requirement for desktop, mobile and server processors but x86 and ARM penalize using safe math operations (you have to insert branch instructions).
> There are a lot of CPU architectures and their variants, some older than 40 years, and C is supported on most of them.
Between safety on modern CPUs and supporting 40-years CPU I would choose the first.
I don't know what you mean with "modern", but x86 was first introduced in 1978, 1985 for 32-bit, and 2003 for 64-bit, for example.
There may be a water purifier somewhere running in a 1995 x86 box that still needs to be maintained.
> Safety is the requirement for desktop, mobile and server
There are several degrees of "safe", and I don't mean just "a hacker stole my data".
I am sure you hear about internet services crashing all the time. A failing service could be a safety issue too. And no, they are not written in C. There are entire companies living on providing redundancy and watchdog services. Often companies just go with "I don't care if the program crashes, we put another server up, just keep developing new features in whatever safe language we are using".
Then they can use 1995 year compiler with unsafe arithmetic.
Is that how it actually works or is it the kernel/hardware not letting you dereference 0?
> Every memory access is already a conditional branch, and it doesn't cause problems.
What are you referring to here? The MMU/TLB?
> Sadly, modern languages like Rust haven't fixed the mistake and also penalize writing safe code
Writing safe code is smooth as butter. You just follow borrowing and lifetime rules and you get memory safety basically for free. Same with safe concurrent data structures.
Unsafe code is the one penalized. The amount of boilerplate and unstable features I need to use in Rust for ergonomic unsafe code is pretty staggering.
Just use them
https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins...
I take issue with this sentence, since it makes it sound like there's something wrong with the C standard for it, which isn't the case.
Eg ending a non-empty source file with anything but a newline is undefined behaviour. So is not closing a string literal.
Something like #pragma come_on_be_reasonable ?
(This is rhetorical. They point is it shouldn't be every coders personal responsibility to make the tool not be openly hostile. You may take pride in personal mastery of an unreasonable thing but that doesn't make it more acceptable)
People already weren't fond of that kind of logic a hundred years ago.
I think HTML5 sets a good example of how to do it instead: A large part of the standard is about defining behaviour for functionality the standard explicitly deprecates and disallows in compliant documents - all just so "legacy" HTML documents don't end up with "undefined behaviour".
This lets you use UBSan most effectively and it's what the Google style guide says to do.
(Exception if you care about micro-performance: * / >> operations can be a little faster on unsigned types IIRC)
It always feels dirty deliberately using a signed type for something you know can never be neagtive just because that signed type has other properties you want.
I think he makes a good point. By having overflow be undefined you leave yourself open to all sorts of issues.
By the way, throwing an error on overflow is also a perfectly valid way to get defined behaviour and not end up with a nonsense value.
As chance would have it, I am actually arguing with another team today about introducing undefined behavior into our code-base. They're arguing "well it works so its fine." I used this article to argue that it doesn't matter and we're inviting really insidious errors to come in later down the road.
I expect my compiler vendor to be on my side, ie produce a compiler that helps me write good software and not get in my way. GCC is doing the opposite, it's deliberately looking to use the standard to fuck me over in the most subtle and unexpected ways. Signed integer overflow is undefined; that gives compiler authors the liberty to make it do anything they want, including well defined things that anyone would expect and find useful. But GCC decides to fuck you over so their devs can give you an arrogant reply and impose their superiority if you show up on their bug tracker.
I agree with this. Making integer overflow UB is ridiculous.
> and don't fuck up any bounds checks
But I disagree with this. That's just normal UB-based optimization, one of the point of having UB at all is to do such optimization.
With UB compilers can assume that eg 'x + 1 > x' is always true for signed integers. That allows quite a few optimizations.
Nothing in there lets the compiler get to say "this will never happen". but they do exactly this.
But "gcc -fsanitize=undefined" is just as easy to run as "gcc -O3" is.
Similarly it's invalid to check if an access to an array is out of bounds after you have accessed it.
I think as it is, it indexes a table where the first positions return tab[0], the next ffff/1ff will return tab[1] and so on.
If I see such a code at work I would reject it in less than 1ms
his code would have gotten an overflow at
int32_t i = x * 0x1ff / 0xffff;
where it not optimized away
so it seems gcc is maintaining the code behaviour, only reporting a wrong debug line for it due code being shifted around.
With -O2: https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename...
Without -O2: https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename...
[Edited. I originally wrote "It should be noted that this only happens when..." but inserted "in this particular case" after @eru pointed it out.]
UBs in C language are the asleep plague just asking to get triggered into a głos bal disaster. Oops, too late.
There is another class of those there, described in some papers for CSmith. Milder but still quite bad.
Both got quietly not acted upon, when C++ got made.
Lets go back to Pascal/Modula/Oberon.