As others are pointing out, the C standard does allow this.
There is no safe way to check for undefined behavior (UB) after it has happened, because the whole program is immediately invalidated.
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.
> because the whole program is immediately invalidated.
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).
> If a situation has been statically determined to invoke UB that should be a compile time error.
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.
C++ bans undefined behavior in constexpr, so you can force GCC to prove that code has no undefined behavior by sprinkling it in declarations where applicable:
Constant-evaluated expressions with undefined behavior are ill-formed but constexpr annotated functions which may in some invocations result in undefined behavior are not.
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.
This has come up before, because, in some technical sense, the C standard does indeed not define what a "gcc" is, so "gcc --help" is undefined behavior according to the C standard, because the C standard does not define the behavior. By the same token, instrument flight rules are undefined behavior.
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.
I think this is confusing undefined behavior with behavior of something that is undefined. And either way, the C standard explicitly applies to C programs, so even this cute "textualist" interpretation would be wrong, IMO.
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.
The general thinking seems to be that UB can do anything so you can't complain, whatever that anything is.
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.
>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
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
> 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 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.
>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
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 */ }
Here, GCC can precisely control what happens when you pass 'hlep'.
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.
> If you're doing a check for UB, the reasonable thing, to me is to maintain that check.
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.
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?
> 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?
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;
There is no UB here, because we never execute the multiplication in cases where it would have otherwise been UB. The compiler is not free to remove the check, because it can't prove that the value is not > 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.
>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
In this simple case yes. But what if you don't know what you're going to multiply by? What if you can't say that X is a bad value?
If you have:
Long long x = ?;
Long long y = ?;
If (????); x *= y;
I don't know the answer to this. I've looked online and the answers invoke UB. The best I can think of is a LUT of safe / unsafe combinations, but that isn't faster, and when you're at that point you may as well give up on the MUL hardware in your cpu, I'm not even sure how to safely calculate the LUT, I suppose you could iterate with additions subbing the current total from int_max and checking if that's bigger than the number you're about to add.
But that's frankly stupid. And again you are basically checking if something is going to be UB which can't happen the compiler is therefore free to remove the check.
Or do you roll your own data type with unsigned ints and a sign bit? But but then what's the point of having signed ints, and what happens to Cs speed. Or is there some bit twiddling you can do?
>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.
It is tedious but possible to check for overflow before multiplying signed integers.
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);
> 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 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.
> UD is supposed to allow C to be implemented on different architectures
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.
Not only to optimize but to write safety tools. If you defined all the behavior, and then someone used some rare behavior like integer overflow by accident, it'd be harder to detect that since you have to assume it was intentional.
UB is also very much based around software incompatibilities though, not just the ability to optimise stuff.
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.
You're getting it backward. UB doesn't immediately stop compilation only due to implementation defined backward compatibility, just because you don't want to break compilation of existing programs each time the compiler converges to the C spec and identified an implementation of undefined behavior.
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.
I can't really follow. What would be wrong with making -fwrapv the default? i.e. let the compiler assume signed integers are two's complement on according platforms (i.e. virtually everything in use today). Then stop assuming "a + 1 < a" cannot be true for signed ints. How would that make existing code worse, or break it? It's basically what you already get with -O0 afaict, so any such program would be broken with optimizations turned off.
I think I misunderstood your comment, sorry, but I have difficulties in understanding how it's different that how things works already, then. You either have to rely that the compiler author did chose what you expect (not the case here), or check by yourself and hope it won't change.
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
I'm not sure if you're supporting my pov by showing the absurdity of the other position???
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???
Parent point is when the standard talks about UB it refers about translating C code. So parent cheekly interpreted your comment about command line flags (which are outside the remit of the standard) as code instead. I thought it was fitting.
The example here doesn't have compile-time known undefined behavior though; as-is, the program is well-formed assuming you give it safe arguments (which is a valid assumption in plenty of scenarios), and the check in question is even kept to an extent. Actual compile-time UB is usually reported. (also, even if the compiler didn't utilize UB and kept wrapping integer semantics, the code would still be partly broken were it instead, say, "x * 0x1f0 / 0xffff", as the multiplication could overflow to 0)
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.
> also, even if the compiler didn't utilize UB and kept wrapping integer semantics, the code would still be partly broken were it instead, say, "x * 0x1f0 / 0xffff", as the multiplication could overflow to 0
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.
> If a situation has been statically determined to invoke UB that should be a compile time error.
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.
C will accept every valid program, at the cost of also accepting some invalid programs. Rust will reject every invalid program, at the cost of also rejecting some valid ones.
("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)
> 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.
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.)
As I recall, the compiler didn't know it had found undefined behaviour. An optimisation pass saw "this pointer is deferenced", and from that inferred that if execution continued, the pointer can't be 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.
The compiler didn't find UB. What it saw was a pointer dereference, followed by some code later on that checked if the pointer was null.
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.
The compiler now knows x's possible range is non-negative.
int32_t i = x * 0x1ff / 0xffff;
A non-negative multiplied and divided by positive numbers means that i's possible range is also non-negative (this is where the undefinedness of integer overflow comes in - x * 0x1ff can't have a negative result without overflow occurring).
if (i >= 0 && i < sizeof(tab)) {
The first conditional is trivially true now, because of our established bounds on i, so it can just be replaced with "true". This is what causes the code to behave contrary to the OP's expectations: with his execution environment in the overflow case we can end up with a negative value in i.
It is probably more precise to say “if the pointer is null, then it doesn’t matter what I do here, so I am permitted to eliminate this” than to say that it can’t be null here. (It can’t be both null and defined behavior.)
I'm not sure that's right. The compiler isn't tracking undefined behaviour, it is tracking possible values. It just happens that one specific input into determining these values is the fact "a valid program can't dereference a null pointer", so if the source code ever dereferences a pointer, the compiler is free to reason that the pointer cannot therefore be null.
In essence, the compiler is allowed to assume that your code is valid and will only do valid things.
Consider function inlining, or use of a macro to for some generic code. For safety, we include a null check in the inlined code. But then we call it from a site where the variable is known to not be null.
The compiler hasn't found UB through static analysis, it has found a redundant null check.
> I was referring to the situation where a null check was deleted because the compiler found UB through static analysis.
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.
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 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".
But again, the compiler did not find UB through static analysis. The compiler inferred that the pointer could not be null and removed a redundant check.
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?
The compiler made a dangerous assumption that the standard permits ("the author surely has guaranteed, through means I can't analyze, that this pointer will never be null").
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.
If I had written the above code, I had clearly done something wrong. I would not want the compiler to remove the second check. I'd want it to (at the very least) warn me about an unreachable return statement, so that I could remove the actual meaningless code.
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.
The first check might be in a completely different function in another module (for example a postcondition check before a return). Removing dead code is completely normal and desirable, warning every time it happens would be completely pointless and wrong.
libX_foo from libX gets at some point updated to abort if the return value would be null. After interprocedural analysis (possibly during LTO) the compiler infers that the if statement is redundant.
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.
> How is it an “implementation detail” whether a procedure can return null? That's always an important part of its interface.
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.
The contract is that libX_foo can return null. But a specific implementation might not. Now you need to remove the caller side check to shut up the compiler which will leave you exposed to a future update making full use of the contract.
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?
It returns null when it fails to do its task for some reason. It is not unreasonable for the condition for that failure to be complex enough or change over time so it doesn't make sense to spell it out in the interface contract.
You typically can't prove it, but if and when you can prove it, you should definitively warn about it or even refuse to compile.
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).
So, how much effort should the standard require a compiler to make for “if and when you can prove it”? You can’t, for example, reasonably require a compiler to know whether Fermat’s theorem is true if that’s needed to prove it.
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.
Everyone wants to drag nontermination into this, but in the OP's example, the compiler already had proof that a the conditional would never evaluate to true. What you can or can't prove in the bigger picture isn't so interesting when we already have the proof we need right now.
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".
> 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)
You can already do that to some extent. There's tons of compiler flags that make C more defined. Eg both clang and gcc support `-fno-strict-overflow` to define signed integer overflow as wraparound according to two's complement.
-fwrapv introduces runtime bugs on purpose! The last thing you want is an unexpected situation where n is an integer and n+1 is somehow less than n. And of course that bug has good chances of leading to UB elsewhere, such as a bad subscript. If you want to protect from UB on int overflow, -ftrapv (not -fwrapv) is the only sane approach. Then at least you'll throw an exception, similar to range checking subscripts.
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).
We've got a few components written in C that I'm (partially) responsible for. It's mostly maintenance, but for reasons like this I run that code with -O0 in production, and add all those kinds of flags.
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.
I'm fairly confident in declaring the answer to your question: None.
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.
> 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.
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!
The C standard doesn't really matter. Standards don't compile or run code. Only thing that matters is what the compilers do. "Linux kernel C" is a vastly superior language simply because it attempts to force the compiler to define what used to be undefined.
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.
I don't believe that it does. If the invalid arithmetic proceeds without crashing, and produces a value in the int32_t i variable, then that issue is settled. The subsequent statement should behave according to accessing that value.
"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.
> I don't believe that it does. If the invalid arithmetic proceeds without crashing, and produces a value in the int32_t i variable, then that issue is settled. The subsequent statement should behave according to accessing that value.
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.
> If the invalid arithmetic proceeds without crashing, and produces a value in the int32_t i variable, then that issue is settled. The subsequent statement should behave according to accessing that value.
The C standard imposes no such constraint on undefined behaviour, neither is it the case that real compilers always behave as if it did.
Even if this solution cannot be used for the Linux kernel, for user programs written in C the undefined behavior should always be converted into defined behavior by using compilation options like "-fsanitize=undefined -fsanitize-undefined-trap-on-error".
Somewhat unfortunately this is valid behavior according to the standard. Having to go through walls of text in a standard to prevent the compiler from deleting your security checks because of how you multiplied two integers seems a bit silly.
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”
The problem here is that the thing that "can't happen" isn't actually something that can't happen, it's something that isn't allowed to happen according to a many-hundred-page document that approximately nobody reads. It's not something that can be optimised because the compiler can prove it cannot happen, it is allowed to be optimised because the standard says "dear programmer, if you ever make this happen, god help you".
I think this view is slightly unfair. I think of UB as the compiler saying "when you promised this thing wouldn't happen, I took you at your word. If bad things happen because you lied, they're your fault, not mine."
Lying requires intent. This was a mistake, something that humans are well-known for making, and if the compiler is designed to assume otherwise, it borders on useless in the real world.
A compiler can’t know why you fucked up, it can’t even know that you fucked up, because UBs are just ways for it to infer and propagate constraints.
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.
> A compiler can’t know why you fucked up, it can’t even know that you fucked up, because UBs are just ways for it to infer and propagate constraints.
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.)
> 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.
Oh, I didn't mean to imply that it would be practical. Only that it's possible and that the type system isn't the only thing you can rely on.
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).
But you talked about JavaScript, where the “heavy lifting” is in fact “assume that it's always true, and switch back a less optimized version if the assumption turns out to be false”. That's exactly the kind of things you cannot do in C, because people use C in contexts were JIT isn't an option.
The signed integer overflow rule is extremely important for common optimizations, mostly related to loops like knowing if they're finite or rewriting their index directions.
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.
> 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.
I've been wondering if I should mention that using int for an index is a bad idea because the standard only guarantees it's 16 bits. You should use size_t instead. And in C size_t is unsigned.
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.
C has always considered that the programmer knows what they are doing. Programs are assumed correct unless proven invalid.
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".
Writing Rust and Haskell for sanity is not something I would agree with. Maybe for language characteristics but reading those make me jump out of the window.
I think Rust doesn't allow integer overflow either, unless you specifically use the wrapping_* operations. Probably the same kind of thing will also happen to Rust.
And yet C is still the dominant language. Undefined behavior is actually the reason why: any defined behavior is expensive to implement in the compiler and possibly incurs a cost at runtime. The language design intentionally trades programmer’s sanity for ease of implementation.
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.
Legacy reasons, most embedded devs and UNIX clones won't use anything else.
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.
> The language design intentionally trades programmer’s sanity for ease of implementation.
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.
I agree on the top compilers but there are dozens if not hundreds architectures with their own proprietary C compilers maintained by a dinosaur and a couple intern dino chicks if they’re lucky. I postulate any other language wouldn’t be implemented or would be defanged to C-level of (non)safety anyway in a way similar to mrustc.
I don't think this is a fair comparison as this is all based on implicit inferences by the compiler.
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.
Even if someone would read all those pages, constraining ourselves to ISO C only, no way that after an year they would still remeber the about 200 UB cases that are documented there.
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.
I think implicitly compiler-added runtime check are a more robust and reliable solution than static analysis. For example for pointer dereferences the compiler should could 0-offset dummy load if the load is not guaranteed to be within a page of the pointer. Or adding abort-on-overflow for math. Or bound checking where possible.
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.
I agree, but unfortunely that will never happen in most C and C++ circles, just see the heat JF Bastien has been facing for a feature that has been shipping in Windows and Android for the last two years, proven in the battlefield to hardly hinder performance in real use cases.
Zero initialization is also one of those features that seems such a low hanging fruit to implement...
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.
It's still braindead and idiotic. Every relevant platform nowadays has well defined overflow for signed ints. A sane C compiler should go with that and base its optimizations on it. GCC has been a pile of garbage in this regard for many years now. Its devs get further removed from reality with every year. Treating signed int overflow as undefined should be hidden behind a flag.
The C/C++ language doesn't provide for a way for the compiler to see that you really meant this one check to take precedence over the implicit promise in another.
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.
> 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.
That's an argument for implementation defined behaviour. Not for undefined behaviour, at least not UB in the modern sense.
Having implementation defined behavior would imply non-portability. C compilers have all kinds of ways of exposing platform-specific features, but sneaking those into what looks like standard behavior has its own issues. And even if you accept that, that doesn't deal with the issue of inlining, generics, and macros - you can get different implementation defined behavior even in a single hardware implementation like that.
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.
The problem is not UB per se -- the problem is that the compiler uses UB to make assumptions that are incorrect.
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.
Checks that are always true _in some context_ are entirely normal and by design if the code can be used in a different context. If your code is reused in a way that let's the optimizer re-optimize the code per-context, then you'll benefit from the compiler's ability to remove dead code or even merely to choose less expensive special case ops. Macros, templates and inlining are some common ways that happens, but platform-specific builds and perhaps others exist too.
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.
Pretty much no property, not even the most trivial ones, of a C program can be relied upon without assuming no-UB. A compiler can't even assume that a variable won't change value between a statement to the next as it could be changed asynchronously by signal handler or thread.
Exactly - so the problem is perhaps best thought of from a different perspective - i.e. not that the compiler only considered defined behavior when rewriting code (because what else would it do?), but rather that certain behavior could have a definition, but doesn't.
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?
I like that the compiler removes comparisons that always have the same result.
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.
Signed int overflow being UB is one of the most basic UBs of the language, and what allows generating tight code in loops.
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.
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?
That's one contrived example solved by changing the type of the loop variable. You have to profile your code for hot spots anyway, this loop would be immediately obvious. And if it's not a hot spot, the difference in emitted code is completely pointless.
I'm not sure using int as a loop variable on 64-bit platforms is that contrived. It's not like it's that hard to find examples using int these days, and I'd suspect that it is more common in older software as well.
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...
> 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.
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.
Ok sure, I'm using this particular example here, but I've yet to see a good counter example to convince me it's the lesser evil to let that happen.
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.
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.)
Basically, the compiler implements integer addition using an operation that doesn't match the semantics of integer addition in the standard, then hallucinates that it did. That is:
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.
Everyone wants that, but when asked for a concrete specification they seem to realize that it is harder than it sounds. Look for John Regehr's blog entries about "Friendly C" for an example. The basic problem here is that C is a terrible language. We should just give up on it by now.
This already exists. Don't write standard C, avoid it like the plague. Compile with -fno-strict-overflow -fno-strict-aliasing -fno-delete-null-pointer-checks, like I do, like Linux kernel does, and like everyone sane does.
No, not everyone sane. Rather everyone sane who has been bitten enough by these issues to use such rules. Everyone starts out at -O2, because understanding all the other flags and their implications is super difficult. As long as the insane setting is default, a large percentage of programmers will be using the insane setting. Arguing that they should have flagged their compilations otherwise is about as useful as pointing out that people shouldn't write UB in the first place.
You can get 99% of the way there with -fno-delete-null-pointer-checks -fno-strict-aliasing -fwrapv . Pretty much every program I've worked on uses those flags, as that's the only way to keep your sanity.
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.
The hard things about C are knowing all these footguns you are getting yourself into. If our electrical grid was built like this we had no isolation, no fuses, no RCDs and a constant torrent of electrocutions and fires. It is bad engineering.
> 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.
I would simply not depend on invoking UB as part of my program's behavior (?).
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"
Yes absolutely, and this is possible today with only open source software. So money is not a barrier.
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.
Definitly, Java, V8, .NET, Android runtimes still have lots of C++ into them, LLVM and GCC depend on C++ and are comparable to Linux kernel in complexity, GPGPU toolchains, .....
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.
Indeed. But still a good idea to run at least your test-suite with it. And also with address sanitizer and clang's memory sanitizer, etc. Whatever you can find.
I keep asking this: in my experience sanitizers and other dynamic checkers have always overperformed, while I'm underwhelmed by static analysis. Do people have different experiences?
Or you know, just turn off UB. I don't know why C still has this, it was useful when we had truly exotic architectures with sign bits &c, but these days it is doing way more harm than good.
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.
Right, UB is essential part of C and can't be turned off. But it's entirely possible to turn off integer overflow UB by compiling with -fno-strict-overflow, and you should use it.
Since the author and GCC disagree about whether this behaviour is useful, it is likely that insufficient requirements analysis has taken place. Is GCC supposed to behave this way? This depends on what goals it is supposed to reach. The GCC authors would say that the C standard allows such compiler behavior, and what is allowed by the C standard doesn't need to be justified by other means. The article author would argue that usability towards the programmer leads to less bugs and is needed, at least partially, as a justification.
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.
That's just saying, "there is no disagreement because one side is clearly right, and the other is clearly wrong". Even if that were true, which is far from certain in this case, it doesn't preclude a disagreement.
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.
C is in many ways a low-level assembler (as by extension C++), in this case though iirc both Java and C# has copied the behavior of fixed-size integer overflows because it's pretty much the efficient usage of the cpu multiplication instruction(and addition,subtraction) w/o introducing extra branches.
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.
Know your users. Who are the target users of GCC, and to what extent are they aware that UB can cause the then-branch of an if-statement to be executed even though the condition is actually false? Does GCC, in an "intentional no true scotsman" way, define its target users to be those that are aware of such pitfalls?
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.
GCC users quite often probably uses other compilers (not that it usually stops GNU developers from embrace-extending stuff). Don't know what the primary PS4/PS5 devkit compiler is but at least gamedevs (not an insignificant portion of developers still mainly using C++) often has MSVC(Win/Xbox) or CLang(osX/iOS/Sony?) as their daily driver due to platform choices.
Oh it is. The fact that you have to remember a (very lengthy) document and every single mention of undefined behavior in it just to be sure that the code that goes out of the compiler will somewhat resemble your mental model of it is, in my opinion, not a reasonable requirement.
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.
This has nothing to do with undefined behavior. Switch the code to unsigned integers, where overflow is perfectly defined as wrapping, and the result is exactly the same.
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.
The author took issue with the compiler removing the i >= 0 part. The compiler did so because it could infer it's true given x >= 0, the only way i < 0 could be true is via integer overflow.
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".
Despite the appearance (the printf says i=62183), the compiler is not removing the check i < 512. That's clear from the decompiled code.
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 based my comment on the description in the article.
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... ;)
It doesn’t matter what x is. Without prior undefined behavior, there is no way to justify “if (i >= 0 && i < sizeof(tab))” passing when (as demonstrated by the printf) i is not actually in that range.
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.
That is not how undefined behavior works in C (or C++).
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.
> 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. [...] Yes, UB can "time travel"
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.
The program can logically undo the call to fflush, too. Mainly by not dispatching it at all–UB is a global program attribute, at least currently. (People have made proposals to change this, but I don't think they have gone anywhere.)
No, it cannot, and UB is not a global program property. The C standard defines valid program executions according to the behaviors of the abstract machine. UB is a property of an execution of the program given some inputs.
Yes, sorry for not being precise: UB applies to executions. When I said "global" I meant global over that entire execution, so if your path ends up hitting undefined behavior it can go back and logically undo its entire execution, including parts which it shared with a well-defined execution or where you'd generally expect side effects to be placed.
No, that logically doesn't make sense. The program cannot know whether it is going through a particular execution ahead of time without actually executing all the side effects along that path first (which in this case would include the fflush()). The very difference between a "program" and a "program execution" is the fact that an execution includes the interactions of the program with the external world (as defined by the standard, all of which I loosely called "inputs" in my previous comment). The interactions basically extend prefixes of the execution through performing the semantics of the program according to the abstract machine and observing the responses from the external world. You don't have an "execution" of the program until the point of UB, until the interactions (aka side effects) up to that point have first occurred (and the responses of the system observed for continuing the execution).
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).
Can the compiler not use that to assume that (x > 4) is false because otherwise it triggers undefined behavior? Hence it is allowed to drop the entire branch?
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.
That's right, I think. If you replace the "fflush()" (which should have an argument by the way) with "f()" and declare "void f(void);" then the test and the call appear in the binary. But if you declare "__attribute__((pure)) void f(void);" then the test and the call disappear.
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 wonder if we can find an example of a function that is externally observable to a user, but that is guaranteed to finish.
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).
> 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".
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.
The program still contains undefined behavior. It is probably a matter of order of optimization whether the compiler catches the undefined behavior before it elides the useless statement.
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.
"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)."
The "[...] executing that program with that input [...]" part maybe could be read as making it specific to a given UB triggering execution; but I'm no language lawyer :).
True, only executions of a program that exhibit undefined behavior are affected.
But the moment it is clear a program will exhibit undefined behavior, the compiler is already allowed to do whatever it wants. So if 20 lines below an important function call you will certainly call a function that will certainly cause undefined behavior, the important function call can be already be left out.
I agree with your sentiment, but the way I square that with what I mentioned is that the compiler can undo side effects. As far as I am aware there is nothing special about fflush in the standard where you can't go back to where the program was before it happened.
(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.)
Something I should add here in hindsight is that I've been rather sloppy in this discussion with a few details, and perhaps they're worth clarifying. For example, despite me using them interchangeably, "observable behavior" is not the same thing as "side effects", and you really have to refer to the standard and your implementation to see what constitutes observable behavior. For example, fflush() may in fact be elidable if the compiler can prove the file is unbuffered (and it wouldn't even need UB for that). Similarly, if the compiler can prove fflush() has no observable behavior (i.e. it is guaranteed to return without raising signals, terminating the program, etc.) then it may be able to elide the call in the UB case as well. In practice this isn't usually possible to guarantee given fflush() performs an opaque system call, but it may be more possible in a freestanding implementation than in a hosted one.
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.
> if you do fflush(stdout); return INT_MAX + 1; the compiler cannot omit the fflush() call merely because the subsequent statement had undefined behavior
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.
To hammer it home: UB isn't restricted to a variable having a funny value. Your C program is allowed to play Nethack on startup, if the compiler can prove that a few hours into your program, there would be UB.
It's not the assignment. It's the multiplication x * 0x1ff.
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 it's wrong break on compiler time, not on run time
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.
I'm not sure what you mean by 'keping the sanitizing check'?
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.
All optimizing compilers do stuff like this. You yourself ask the compiler to do it when you pass it '-O2'. Its default behavior is, in fact, to not optimize based on the assumption that UB won't happen.
Fun thing there is rust feeds into the same optimisation pipeline as C or C++, so there's a definite risk of it inheriting some of their semantics via errors in the compiler implementation.
There have been several cases where Rust's use of "restrict" pointers exposed bugs in LLVM, and the Rust compiler had to disable some optimizations as a workaround. But I haven't heard of anything like that happening with signed overflow. (Probably any bugs with basic integer behavior would get noticed quickly?)
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.
The promise of Rust is that you never run into undefined behavior if you only use safe code. There are some caveats (using dependencies with badly written unsafe code, the noalias bugs others mentioned) but in the general case, if you're writing code without 'unsafe' blocks, you're not going to trigger UB.
You're certainly not going to run into LLVM optimizing your bound-check out of existence because it occurs after an overflowing operation.
Compiler bugs are always a potential issue for fuckup.
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.
Rust is a good replacement for most use cases, but I think specifically in case where you're looking for a more predictable and less risky implicit behavior, the replacement should be more stable and predictable than Rust is at the moment.
Question, but where do you get the idea that Rust is not stable or predictable? I understand you were asking for something _more_ stable/predictable than Rust, but Rust is already very stable and very predictable (in fact I can't think of any ways that Rust is "unpredictable").
C has a specification and weird stuff doesn't happen as long as you follow it. Doing so is very hard at times, but if a project cares about unpredictable optimizations, then it probably also cares about other kinds of unpredictable behavior. Which unfortunately eliminates a lot of languages that make no guarantees about their semantics.
The root of all these problems is that C doesn't guarantee two's complement behavior when compiled for two's complement machines, as far as I understand.
But why is that? Why are integer operations not defined as implementation-defined?
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.
As I understand, the only ones' complement architecture in active use is UNIVAC (yes, believe or not UNIVAC is in active use and Unisys provides commercial support).
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.)
Nitpick: it's not the behavior of the program that becomes undefined, but of the execution that it occurs in. For example, consider a program that reads argv[3] without making sure there's at least 4 arguments. If you call it with too few arguments, that entire execution is undefined (even stuff that happens before the out-of-bounds access), but if you call it with enough arguments, it is well-defined and the compiler has to emit code that will work.
Ah but the trap is that if the compiler can reason that UB always occurs (in reality it will reason that code is dead because the constraints it computes don’t allow for its execution) then it can remove the entire thing.
See Raymond Chen’s well known “undefined behaviour can result in time travel”.
Sure, but if UB always occurs, then every execution is undefined, so doesn't what I said still hold? (And the time travel is what I meant by "even stuff that happens before the out-of-bounds access".)
Yes. To spell it out: undefined behaviour doesn't just affect specific values nor just the behaviour of your program after triggering UB. It's the entire behaviour of your programme. So UB can 'travel backwards in time'.
Fun fact: not closing a string literal is UB. Ending a non-empty source file in anything other than a newline is also UB.
In addition to the points that other posts have made: it's also not especially new behavior. E.g. I see it at O2 gcc version 9.3.0 on i386. The optimization isn't performed by gcc 4.9.2 at O2 on i386. If I had to guess it probably shows up around GCC 5, but I don't seem to have any i386 vm's with gcc between 4.9.2 and 9.3 handy at the moment.
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.
The lesson is to only use C when absolutely necessary, and regularly use all the sanitizers and other safety tools you can find. Not just when you suspect something fishy.
I am on split here. Signed overflow is UB and it is pretty well known, yet author is writing code that depends on such overflow.
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"
While I have been a member of the "unsigned counting variable" minority for a long time, this kinda drives the nails into the coffin for a lot of signed array index / offset use. It's just too big a risk to accidentally have the compiler go YOLO on you for some minor detail you missed.
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
I compile all my C code with -fno-strict-overflow and -fno-strict-aliasing, and I recommend you to do so as well. C standard committee and GCC and Clang are being stupid, but that does not mean you should suffer their stupidity.
I am sort of uneasy with what the optimizing doing in here.
But I would not ever write something like this:
int32_t i = x * 0x1ff / 0xffff;
Not because I am supersmart and will / can predict how optimizer will fuck it up. It is just that I am paranoid when coding and this type of code just simply hurts my perception for some reason.
The trap in C is that you can't have overflow checks after the calculations testing if overflow happened by making assumptions about what the UB does. Once the UB has happened it's already too late. What you actually need is input range checks to ensure that following code can perform it's calculations correctly without hitting UB or you need to use helper intrinsics which perform checked math operations.
As already said it just ruffles my feathers the wrong way. I would not analyze why as I usually have better things to do with my programming time. The best answer I can come up with without thinking is something like this:
overflow is an error. I would prefer the code not to create errors unless absolutely needed.
There’s no reason to expect the result of integer overflow to be negative, or any particular value at all. It is undefined.
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?)
Be careful: it's not just that the result of the multiplication won't be what you expect. The entire execution of the program becomes undefined. For example, if you had an unconditional `puts("hello");` between the multiplication and comparison lines, if the overflow happens, it would be allowed to print "goodbye" instead.
Yes, and in particular the compiler can assume that you stay within the defined behavior. That's what's enabling the optimization in removing the i < 0 check.
I think it was a mistake when CPU and language designers decided to make overflow in arithmetic operations not an error. This is wrong. Overflow can produce invalid data, which can break something elsewhere. Overflow has been a reason for security vulnerabilities.
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.
If your unsafe code is sound, you can't cause memory corruptions with wrapping integer overflows, no matter what you do with them. If your Rust code is engineered correctly, overflows are primarily logic bugs, not memory safety issues.
> 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.
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
And here is safe code:
u32 s = checked_add(checked_mul(N, S).unwrap(), H).unwrap()
> In your "unsafe" example in Rust, you still don't get undefined behavior.
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.
> 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".
Those look rather inconvenient. Is there a sane way to keep things infix at least without having to crack open a spew of operator overloading?
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)
Huh? There's all kinds of things wrong with the C standard. For example, they really went overboard with the UB even for cases that should have arguably been implementation defined or just throw an error.
Eg ending a non-empty source file with anything but a newline is undefined behaviour. So is not closing a string literal.
They seem reasonable to me? They're similar to the compiler builtins people already know and pretty short (7 characters…). What don't you like about them?
There is an old german proverb that fits here, "Es kann nicht sein, was nicht sein darf", mocking lords and judges who purposefully mixed up things that are physically impossible to happen and things that ought not to happen by policy and made their life awfully easy that way.
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".
They're correct to do this. Signed integers have more UB, therefore you /should/ use them in all situations when overflow isn't going to happen, because you're not going to need that extra defined behavior.
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)
I would also prefer unsigned indexes but exactly because the compiler may assume that there will be no overflow, signed index access may be a bit faster and therefore preferable.
On most machines this days there is not really a performance difference between the math done on signed or unsigned integers. The only case would be if your wanting to the compiler to optimize on the fact that UB does exist. So like this in example "impossible things" get optimized out. The author here clearly does not want that.
Is there a reason why the language doesn't provide UB-on-overflow (and wrappring overflow) for both unsigned and signed types?
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.
Of course with well defined overflow you can still end up with a nonsense result that just happens to be in your valid range of values. If you don't plan to harden your code against integer overflow manually you need a language that actively checks it for you or uses a variable sized integer to be safe.
I've spent a fair bit of time running a fuzzer on Rust code that parses untrustworthy data. And the thing that saved my code time and time again was that Rust has runtime bounds checks. Even if I messed up index calculations, I'd get a controlled panic, not a vulnerability.
He is checking if the output is in a sane range. Not if the input values where. This may be correct for a trivial toy example but bite you in actual production code. Fun things like malloc(ab) vs calloc(a,b) where ab overflows in a well defined way and gives you valid pointer to an unexpectedly tiny buffer.
I think this article makes a far better case than the college hyperbole of "once you invoke undefined behavior it is allowed to format your drive and kill your cat."
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 knew rust had to be mentioned. But this is a optimization bug. I break my code several times while optimizing thinking a minor change wont matter then end up undoing it all.
I blame GCC. The C standards committee is some out of touch with reality conglomerate working in a vacuum, taking 50 years of language history into account.
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.
Why can they assume that? how on earth did "undefined" ever get read as "can not happen"? if the standard meant "can not happen", they would have said "can not happen". but they did not, they said we are not going to define what is going to happen. or in other words, the cpu is going to do something when this happens but we don't know what.
Nothing in there lets the compiler get to say "this will never happen". but they do exactly this.
Ok well yes, technically as soon as the compiler doesn't treat the overflow as UB anymore the second part is not applicable anymore. Badly worded on my side.
I'm not so sure it's that wild. Signed overflow is UB so it makes perfect sense it's not possible to check overflow happened. You need to make sure overflow doesn't happen.
Similarly it's invalid to check if an access to an array is out of bounds after you have accessed it.
It's just an artifact of decompilation. It's the same operation in machine code (checking the MSB), there's no way to tell which one was used in the original source code.
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.
[1]: https://lwn.net/Articles/342330/