Three proposals for the C standard WG14
yodaiken.com
yodaiken.com
The standard doesn’t describe transformations; it describes behaviors. You can’t just say that undefined behaviors can’t be “transformed”, because there was nothing to transform them _from_. If you want some behaviors to be possible and some behaviors to be impossible, then you need to define those behaviors.
For C, that’s not something we can realistically do in every case. There’s no way to reasonably constrain the set of allowed behaviors after a program does some crazy pointer operation like * (int *) rand() = rand(), because any implementation of those constraints would more or less require an expensive run-time check at every pointer access.
What you could meaningfully ask is for particular situations (like negative shifts) to be considered unspecified or implementation-defined rather than undefined. That way you don’t give up the ability to constrain the behavior of programs after those situations arise. There are already many unspecified behaviors in the standard, such as reading the value of padding bytes in structs.
Such proposals could be considered on their merits, but they’d have to be discussed individually. There’s no way to remove all undefined behavior from C and still have something that would be recognizable as C.
That doesn't seem to be an argument against, or even related to, what the proposal entails. All of these proposals are reductive attempts to curb the instability that UB introduces, for little value (see the linux kernel).
> because there was nothing to transform them _from_
Yes there was. Anything that can result in UB.
> For C, that’s not something we can realistically do in every case.
That's why the proposal is not exhaustive, as described.
For instance, the following code is not valid C code:
int a[2], b;
a[2] = 5;
If you want the compiler to do something specific, you need to define it. In some cases the standard has language for otherwise-defined behavior that is carved out as undefined (e.g., strict aliasing), and it's easy to go "Never mind"; in some cases it does not (e.g., writing to a string literal). For these ones, the behavior needs to be defined.
Simply saying "Don't optimize this" is just saying "I'm not going to define the behavior, but don't implement it this way," which isn't a particularly useful way to define a standard (e.g., for the null checks example, is the compiler permitted to leave the null check in, but insert a segfault right before it?).
No the compiler is not entitled to insert a segfault. Segaults come from architectures and operating systems, not from compilers. The compiler is free to leave in the dereference of the null pointer and then, who knows what happens. But the compiler can't break the code by deleting a perfectly conforming null check on the theory that a previous dereference means that the pointer is not null.
The original Bourne shell used signal to catch memory faults so it could operate dynamic paging! If your OS/implementation permits, C is supposed to allow you do do things like that. The compiler is NOT supposed to insulate the programmer from bumps. (Disclaimer: I am not endorsing the horrible design of the Bourne shell which was also written in a macro style that made C into pseudo Algol).
As for deleting null checks, time-travelling UB etc. the compiler always assumes the code is valid, bug-free for the compiler-specific definition of valid. This is at least the standard definition but it can be expanded by flags and extensions. Then they optimize that code without regard to what happens if the code actually had programming bugs.
If you want to add a definition for signed integer overflow (as C++ is considering, see http://wg21.link/P0907r0 ) then it would be defined and the compiler would no longer get to consider "if signed overflow" and "if false" the same.
But when you are programming in C, you are programming against the C abstract machine, not against an architecture or operating system. It's this machine that you are breaking when you invoke ub.
Passive voice! You expect C code to go beyond the territory of the abstract machine. The authors of the standard, quite clearly, do not.
I can see both of these arguments. I think there is a place in the world for a C that is machine-specific. But it's clearly not what the standard authors have in mind, there are clearly people who find the genericness of C useful (cf. "portable assembler"), and piecemeal solutions like skipping individual bad optimizations won't solve the underlying problem that there's no way in C to say "Dude, I'm writing for a reasonable UNIX on a reasonable modern machine with a single flat address space for code and data and non-exception-raising two's-complement arithmetic and the ability to do nonaligned reads/writes and other normal things, please stop thinking I might also be writing for a PDP-11 bootloader."
I think you should go to the standards committee with a single proposal, which is that C should stop trying to be portable to weird / old architectures (and people who need them can use weird / old compilers, anyway). Among other things, you can now enable certain types of optimizations if the compiler is permitted to assume that arithmetic is two's-complement and nonaligned reads/writes work and so forth.
One of the most popular architectures for "a reasonable UNIX on a reasonable modern machine with a single flat address space for code and data" is the x86, and on it, some nonaligned reads/writes do trap. Certain optimizations can be done only if the compiler is permitted to assume that the data is aligned.
That is 100% wrong.
>Strictly conforming programs are intended to be maximally portable among conforming implementations. Conforming programs may depend upon nonportable features of a conforming implementation.
The whole concept of "undefined behavior" is to cope with the reality that C programs routinely go beyond the bounds of the abstract machine.
Why is this different from letting the compiler optimize out the second check here?
int foo(unsigned int i) {
if (i < 5)
return this();
if (i < 4)
return that();
return those();
}
What about the following—are you okay with compilers optimizing it?
struct pointer {
int *value;
char valid;
}
void *deref(struct pointer p) {
if (!p.valid)
abort();
return *p.value;
}
void stuff(struct pointer p) {
int n = deref(p);
if (!p.valid) {
fprintf(stderr, "Hey, that pointer wasn't valid!\n");
return;
...
}
> The original Bourne shell used signal to catch memory faults so it could operate dynamic paging! If your OS/implementation permits, C is supposed to allow you do do things like that.
I'd believe that (especially given the state of optimizers in Bourne's era) C does allow you to do things like this. I'd also believe that with sufficient -fno-unwanted-cleverness flags. C is the best way to do things like this.
But asking C to be designed to support things like this is quite a change. I get that this is exactly the change you're pushing for, but, the only way it can work is if the C abstract machine becomes hardware-dependent enough that you can embed platform assumptions in your C—and so C is no longer a "portable assembler."
There's precedent for this. One that comes to mind is the ability to cast a data pointer to a function pointer (which doesn't have to be valid; the abstract machine doesn't know if your physical machine uses different address spaces and different representations for the two, and even the brand new architecture WebAssembly uses different address spaces, but compatible representations). dlsym() implicitly requires this, and POSIX.1-2013 finally made an explicit requirement that a C implementation conforming to POSIX must define it in a meaningful way. http://pubs.opengroup.org/onlinepubs/9699919799/functions/dl...
I would certainly support a variant of C that did things like assume a flat address space, validity of all pointer values besides NULL (and an expectation that signals can catch and fix invalid pointer dereferences), char = unsigned char, 8-bit bytes, two's complement arithmetic, etc. It would not support every architecture C supports. It wouldn't be a good fit as a C standard, but as a variant for people who are happy to never target segmented real-mode x86 or the PDP-11, it seems pretty great.
That is not remotely true - as you can see by looking up the example I reference.
>For C, that’s not something we can realistically do in every case. There’s no way to reasonably constrain the set of allowed behaviors after a program does some crazy pointer operation like * (int *) rand() = rand(), because any implementation of those constraints would more or less require an expensive run-time check at every pointer access.
That's such a weird response. There is nothing in the proposal that requires run-time checks. The proposal simply limits the ability of the compiler/translator to make counter-factual assumptions or otherwise violate the C semantics.
>What you could meaningfully ask is for particular situations (like negative shifts) to be considered unspecified or implementation-defined rather than undefined.
I don't want to do that: I want to clarify the meaning of "undefined behavior" to curtail its use as a license to do arbitrary code transformations. One implementation may trap on a negative shift, one may generate negative shift instructions that the architecture treats as no-ops or whatever they do, one might do sufficient static analysis to detect negative shifts and generate an error message - but the compiler is not free to assume that the shift operator has a negative value.
I'm not trying to remove undefined behavior from C. I am trying to correct a mistaken analysis of what undefined behavior should mean. C is intended to allow for non-portable operations, for example. These are "undefined" in the standard because they depend on the implementation, not because the C language should be specified so as to allow compilers to introduce hidden booby traps or counter-factual assumptions into the implementation
Shifting by a negative number is meaningless and is indicative of programming error. Instead of specifying that an implementation should check and handle these programming errors, which implies runtime costs, we use undefined behavior and leave the responsibility to the programmer.
The reason many compilers assume a positive shift after a shift operation executes is because otherwise the entire program would be undefined. You’re effectively asking for undefined programs to have defined behavior. The equivalent would be asking the compiler to correct your typos and it can’t do that. As they say: garbage in, garbage out. The compiler isn’t the one booby trapping you, you’re booby trapping yourself.
I think GP is right that what you want is more definition but it has to be in specific cases because otherwise the runtime costs would be too high. In your negative shift example, the definition would be “shifting by a negative number results in garbage output,” but note that that would burden implementations where negative shifts trap.
Maybe more like "handle bad situations that cannot be precluded at compile time". And since C has "no runtime", so can't do much "handling" at run time, it gets UB instead.
Doing something at runtime is a different concept from having a runtime.
In any case, C, in fact, often does have a runtime. What do you think executes main()?
> In any case, C, in fact, often does have a runtime. What do you think executes main()?
Sure, that's why I said it has "no runtime" (in quotes). I'm not trying to split hairs here.
In the context of real numbers sqrt(-1) is syntactically valid yet meaningless code. In other contexts, 1 << -3 is too. Also log(-1). Perfectly valid syntax but has no meaning.
The intent of scare-quotes tends to be ambiguous so I avoid them in discussion. http://frivolousquotationmarks.tumblr.com
As to the formulation of UB, it's not about code ("syntactically valid constructs") but about manifestation. And manifestation is a run time thing. 1<<-3 "is" UB, yes. And that can be detected at compile time through constant propagation. But that's not why we need UB. We could just forbid 1<<-3, so there was no need for UB in the first place.
UB is really about values not known at compile time. The expression 1<<x might manifest in UB at run time, depending on the value of x. Since x in general is not known well enough to decide whether it will ever be negative, the question "will this expression ever manifest in UB at run time?" is in general undecidable, so the best answer is "possibly". That does not imply that it's always a bad idea to use the expression 1<<x, and it does not make the construct meaningless. (Really I don't think the construct itself has a meaning, but as I said I won't argue here).
And that's why I think the formulation "handle meaningless yet syntactically valid constructs" is misleading. It's not about the construct (i.e., syntactic construction). It's about run time values that lead to UB, and that are totally independent from the construct itself. They might come from a wrong function invocation, or from malicious user input. It is the programmer's duty to make sure, by whatever means, that UB never manifests.
Maybe that's just what you were trying to say, but I think it's important to be clear that it's not about the syntactic constructs.
Syntactic constructs in general should and do have meaning. The meaning isn’t inherent, but nothing has inherent meaning. log(x) has no inherent meaning, but when x is positive we have decided that it means that it evaluates to the value to which you would raise 10 to get x.
Bad run-time values only cause UB in the context of improper usage in syntactic constructs. They aren’t independent of syntactic constructs: both syntactic constructs and values dictate behavior.
You’re right that UB only manifests itself at run-time. And you’re right that we wouldn’t need to use UB for constructs that only manifest their behavior at compile-time. Indeed, there exists syntactically valid yet meaningless C++ template substitutions that don’t result in UB, they result in compilation errors.
Basically, the intent of the proposal is understandable but it does not make sense as written.
The spec does not explain how to compile C code, it gives you a set of rules so that you could in theory take some piece of C source and a full execution trace and verify whether that trace was a conforming execution for that C code.
You take the example of the negative shift again, and it is addressed in the post you respond to : it's a perfectly fine proposal to demote negative shifts from UB to something less permissive to the compiler.
However, if you do so, of course, you have to frame what behaviors are accepted for a program doing such a negative shifts, just as you did in your post !
So let's say : arbitrary (but consistent) values are fine, termination is fine. That's great because it means we can still compile a shift to a CPU shift and there's no UB anymore. Ok.
Same goes for signed overflow.
However this is a case by case process, and you will absolutely not be able to ascribe meaning this way to many forms of UB. For example, as the GP said, storing through an invalid pointer.
If you want to compile a pointer store to a store instruction without runtime checks, then possible observable behavior include : other variable changing values, function call not returning to their calling context, and even of course running a full ROP chain exploit !
It's no surprise that in that case the specs says that the set of allowed observable behaviors is anything.
And yet UB is frequently described as this scary monster that will eat your hard drive.
Sure there are more UBs in C than there would need to be if the standard restricted more on contemporary hardware. I think it still allows ones' complement representation for example? But I guess it shouldn't be so bad as long as compilers do not exploit the freedom to do anything that comes from UB, more than they need to on a particular architecture?
As for "UB is frequently described as this scary monster that will eat your hard drive", setting aside that UB could be exploited by an attacker, it's not hard to imagine, for instance, a recursive file deletion routine that is affected by UB misbehaving and erasing more than it should.
Or, the compiler could assume that the programmer made sure that overshifting never happens, since it's UB. Based on that assumption, it could make more aggressive (and possibly totally insignificant) optimizations by inferring other assumptions that don't align with the programmer's idea anymore.
I never encountered such a sitation myself, but there are stories like that on the internet, where for example the Linux kernel was broken.
Another scenario, the user might always do an operation that sometimes results in a random value (which is UB), but in the end only use the resulting value if it was not UB. The compiler instead could assume the operation can never happen in the first place. Again, there is a misalignment here in how the compiler reasoned and how the programmer reasoned (closer to the actual hardware).
So, the difficult problem is probably defining the UB configurations as narrowly as possible. It might be a good idea to specify UB per architecture in some cases, but then it would lead to a lot of complexity. In any case a guideline for compilers should be to minimize surprises, which means not applying many optimizations around UB. That's easier said than done I guess.
I'd figure it's much more likely to happen as a result of a logic error introduced by the programmer, without any UB involved.
IMHO this is clearly a compiler bug. Yes, it's technically allowed to do this because calling a NULL function pointer is UB, but nobody wants such an optimization (which is my first point from earlier). If the compiler makes such a decision based on UB, shouldn't it be able to at least issue a warning?
Furthermore, why should this be optimized in the first place? If the user decides to make a function pointer instead of a hard-wired inlineable call, he is aware of the performance implications (which are negligible in 99.9% of the cases). Where function call efficiency matters, nobody ever used a function pointer.
Shouldn't the compiler architecture be able to avoid making this optimization, simply by avoiding propagating the UB? It should simply not say "Calling NULL can never happen". This way it would never make optimizations that make the situation even worse. I think this would even be less optimization code!
Instead, when the UB happens, the programmer should get what he deserves (which is, well, calling NULL, and most likely resulting in a segfault, which is the right thing).
On the other hand, if the compiler can infer the value of a function pointer based on propagation of values alone, I'm fine with hard-coding the address, even though it's probably not worth the effort anyway.
Yes, that EraseAll example is silly, but how can the optimizer distinguish it from non-silly examples? Perhaps there are other alternative functions which also set that same function pointer, but they were all hidden by some #ifdef; in that case, devirtualizing when there's only one option left will be a performance win, and can expose other optimization opportunities.
Hmm, shouldn't it be possible to do that in some other way? After all, a virtual function is something different than a function pointer (the vtable holding a function pointer is only an implementation detail, isn't it?).
Anyway, I'd rather not have that optimization. When we don't want to pay a small performance hit, we shouldn't make a virtual function in the first place. It's good to see how advanced optimization tricks can combine in dangerous ways with complicated language features!
> distinguish it from non-silly examples?
Yes, probably not possible. There is a real risk, but non-silly examples are less likely than constructed ones.
> all hidden by some #ifdef
If you do it with the preprocessor, there is no need for function pointers in the first place. Just make a #define instead of a variable.
Thanks again for the example, very interesting!
First, the compiler is allowed to compile your program as-if all values of all variables are such that undefined behaviour doesn't happen, but isn't allowed to extract value bounds based on that for the purposes of optimising across more than one expression. So the compiler is allowed to assume pointers aren't NULL where they are dereferenced, because that is undefined behaviour and the compiler either has to assume the pointer isn't NULL, or require proof from the programmer, or refuse to compile any C program with pointer dereferencing because it is potentially invalid C. However, it is not allowed to assume that because a pointer was dereferenced, that it is not NULL. This restriction should be tight enough that
int a, b;
... set a and b ...
if (a > 0 && b > 0 && (a+b)&(int)(-1) > a) {
...
} else {
...
}
mov eax a
add eax b
cmp eax a
jle .else
float max (float f[], int length, int* max_index) {
float max_value = -FLT_MAX;
*max_index = -1;
for (int i = 0; i < length; i++) {
if (max_value < f[i]) {
*max_index= i;
max_value = f[i];
}
}
return max_value;
}
Such an approach would preclude putting any variable in a register if there is any not-provably-valid pointer store anywhere in the program.
Feel free to try, but I guarantee you that for most non trivial optimization it's going to be easy to find a piece of code that is UB today and where the optimization is observably different from the reference compilation.
[1] https://blog.regehr.org/archives/1180 [2] https://blog.regehr.org/archives/1287
Even if you don’t agree with this proposal, or with Regehr’s, surely a reasonable response would be “okay, yeah, it would be good to do something along those lines, but not that; how about this?”
If I were more cynical, I'd say that the C-standards community has simply ceded the ecosystem niche of a low-level language which has common-sense behavior, creating an opportunity for other languages such as Rust, D, Zig, etc. But I don't really believe that. Almost everything we do relies on C at the bottom, and it's pretty much the only viable way to publish an API that can be consumed by multiple languages.
I think it's true that almost everything we do relies on the C ABI at the bottom. That's different from relying on C, and I think these are actually the same problem: the C ABI is straightforward and has been implicitly stable (whereas e.g. the Rust ABI is explicitly not stable) because the C ABI has very few types and very little information in types (aliasing, ownership, alignment, thread-safety, parameter types of functions, etc.) and the more common-sense lower-level languages are obligated to have meaningful types.
You can certainly publish a C API / ABI from a Rust library and consume it from a D program without either side knowing that the other side isn't actually written in C.
I am curious what is the next meaningful step beyond the C ABI and the C type system: even stabilizing the Rust ABI (which I would love to see) isn't going to help a lot for writing D libraries that implement them or Python programs that consume them, partly because Rust has unique ideas of things like lifetimes that don't immediately translate to other languages. What's the subset of stuff that's in all these languages' type systems that isn't in the C ABI?
I'm reminded of Vala (which I kind of miss), which was GNOME's attempt a couple years ago at a better-than-C language that was very explicitly C-ABI-compatible. It used the GObject protocols for types - is GObject the shape of thing to standardize?
The C ABI and type system omits a lot of stuff that could be useful. Some points off the top of my head:
* Vector types
* Multiple return values
* Functions with bound environments
* Coroutines
* Dynamically-sized callee-allocated structures (most notably lists)
* Distinguishing between "byte array" and "string" types
* Vtables
* Something that lets GC'd languages cooperate more nicely. I'm not sure how exactly to specify this, but this is the sort of thing we could have if we stopped insisting that everything must be in terms of C ABI.
The only one that comes to mind is https://research.mozilla.org/2014/08/26/javascript-servos-on... , which is Rust (pre-1.0) and JavaScript, but that somewhat doesn't count because Rust isn't really a GC'd language. (This article was written about a year after the special syntax for garbage-collected references was removed and Gc<T> became just a thing in the standard library, and about a month before that type was also removed because it wasn't a very good GC.)
It seems to me that if you make your GC a purely refcounting system this is easier: you just need to specify how to incref and decref objects, and put a well-known function in the vtable for destroying and deallocating the object. I'd guess that's how things like GObject or Qt bindings in Python or similar languages work.
I personally think ownership is a biggie. If I pass in a pointer, is it expected to outlive the call?
And buffer sizes, of course.
Not quite true, on Windows it is called COM, WinRT or UWP as of Windows 10. Or MSIL in alternative.
On IBM i, IBM z, Unisys ClearPath, takes a variation of what is known as language environment.
On Android you will have more luck targeting DEX than C.
On browsers better compile to JavaScript in some way.
The trouble is that "carry information with variables" means one of two things, runtime checks (which often - but not always! - rule out "high performance") or types.
Rust is my personal preference here, but it's hardly the only option - Go and idiomatic C++14 are also good direct competitors, Java and PyPy can be faster than AOT-compiled code if you don't mind startup time, many applications actually aren't in need of a language that aggressively optimizes (e.g., it's relatively short logic on top of a database that someone else is writing in C), etc.
So the only alternative is to improve the band-aids and keep sponsoring PhDs on security research related to C.
C is already mush. Maybe it wasn't in the 1980s, but it certainly has been since I first started learning C (around 2000).
I'm simply responding out of rational self-interest to recognizing that C cannot be what I want it to be, and what I want it to be looks an awful lot like Rust (or Go, or Swift, or...).
C doesn't even have sum types with a language construct for exhaustive matching. That, by itself, makes C programming dangerous. For every NULL check unexpectedly deleted by a compiler, there are a thousand NULL checks that weren't written in the first place, because C has no mechanism to require a NULL check before using a pointer.
Frankly, I don't understand the UB hate at all. There is a rapidly growing space of programming languages specifically designed to give you safety guarantees and well defined behavior. If that's what you want, by all means use them. There are still those of us out there for whom even `-fwrapv` represents an unacceptable loss in performance for certain programs. There is an important and valuable niche for a language that enables compilers to optimize code without regard for saving programmers from mistakes in their code, and that's always going to be the case. Most people probably shouldn't be using it very much, but that's an entirely different issue from trying to "fix" what's not broken in C.
I haven't stumbled across anything new or unique here, it's just that most people don't write compute-constrained kernels that often these days. The optimization benefits of UB for signed integers are well known, and that's just one useful example of UB in C compilers.
And again, I'm fully on board with the notion that many people would be better off with a more error tolerant subset of what C does - and there's a lot of languages that provide just that. I'm just saying there are real costs to the change and they matter.
Regardless, apart from pathological integer math cases, these things have little to do with the cost of overflow checks. Rather, it's about the followup optimizations the compiler can do after the UB frees it from a restrictive assumption. The trivial common examples (optimizing x*2/2 to x for integers, etc.) don't really capture the impact of these things very well, because you can't demonstrate it in a oneliner, but you can derive representative examples pretty easily if you take tight-ish loops (>16 independent loads, some SIMD-able compute, a few dependent stores at the end) and switch the index types. The vectorizer is often easy to defeat if it can't assume no overflows, the cost of the check itself is irrelevant.
On your last point, I don't think compute intensive kernels are "self-evidently more important" than anything else. I think there are usecases - like scientific computing, device drivers and embedded software, to name a few - that often benefit from prioritizing programmer control over any safety net, and FORTRAN doesn't cut it for many of those uses. There are plenty of languages that give you all the safety you could possibly want. C/C++ have never been about that and I don't see why that should change. Use the right tool for the job, by all means advocate for people who don't need this level of control to use something "safer", but the notion that every tool should be blunted to some common denominator just makes no sense to me.
If you're not a compiler writer, you probably have a mental model of undefined behavior that works like this:
if (expr->invokes_undefined_behavior()) {
// Yay! Silly user!
shit_on_users_code();
}
But that's not how compilers work, not in the slightest. Instead, the undefined behavior effects tend to work like a chain: you dereferenced a pointer, therefore it's now safe to assume on any subsequent path that it will always be safe to dereference that pointer, therefore we can move that later load out of that loop even though we don't know if the loop will be executed in the first place. And the reason that logic works is because we're allowed to optimize under the assumption of undefined behavior in one of those steps.
Now in some cases--signed integer overflow and strict aliasing come most readily to mind--there is a single knob you can twist to disable the undefined behavior (and most compilers let you twist that knob with command-line flags). Arguing whether or not the standard itself should dictate a different position on that knob is one thing, and it's by no means a bad discussion to have. But instead arguing "let's let you keep undefined behavior, but let's try to specify what you can do with undefined behavior" runs into the problem that it's very difficult to actually specify what somewhat-constrained undefined behavior really means. Look up the massive email threads on LLVM that try to tease what poison and undef actually mean.
I find that very patronizing.
Yes, we mere compiler users complain about specific examples; that’s because we keep finding specific examples that break in weird ways!
But at the same time, we realize that it’s a general approach that causes trouble. As I understand it: assuming that undefined behavior cannot happen and optimizing on that basis.
I’m not arguing for specific small tweaks to fix a few known weirdnesses, or even a more general adjustment to the notions of poison and undef (as your mention of “massive email threads” suggests).
I’m arguing, first, that the entire approach seems to be misguided and not working well; as evidence, many real-world examples of code doing extremely unexpected things, and the position of the Linux kernel maintainers (surely an important group of users by any standard).
Second, that the problem seems to be largely ignored by compiler writers; as evidence, no changes or improvements, despite several proposals from outsiders. You can point to massive internal debate on email threads but it amounts to nothing if nothing comes out of it.
Undefined behavior is one of the tricks that enabled C compilers to catch up with what everyone else was doing in big iron outside AT&T walls.
Fran Allen the Turing awardee on high-performance computing and compiler research, stated this on C:
"Oh, it was quite a while ago. I kind of stopped when C came out. That was a big blow. We were making so much good progress on optimizations and transformations. We were getting rid of just one nice problem after another. When C came out, at one of the SIGPLAN compiler conferences, there was a debate between Steve Johnson from Bell Labs, who was supporting C, and one of our people, Bill Harrison, who was working on a project that I had at that time supporting automatic optimization...The nubbin of the debate was Steve's defense of not having to build optimizers anymore because the programmer would take care of it. That it was really a programmer's issue....
Seibel: Do you think C is a reasonable language if they had restricted its use to operating-system kernels?
Allen: Oh, yeah. That would have been fine. And, in fact, you need to have something like that, something where experts can really fine-tune without big bottlenecks because those are key problems to solve. By 1960, we had a long list of amazing languages: Lisp, APL, Fortran, COBOL, Algol 60. These are higher-level than C. We have seriously regressed, since C developed. C has destroyed our ability to advance the state of the art in automatic optimization, automatic parallelization, automatic mapping of a high-level language to the machine. This is one of the reasons compilers are ... basically not taught much anymore in the colleges and universities."
-- Fran Allen interview, Excerpted from: Peter Seibel. Coders at Work: Reflections on the Craft of Programming
As for the modesty, it's presumably a reference to this: https://en.wikipedia.org/wiki/A_Modest_Proposal
- allowed to assume that the negative shift does not happen (what it says now)
- the value of each dynamic negative shift is unspecified but it must have a well defined value, however the same shift operation in the source code could return a different output given the same inputs dynamically (eg in a different loop iteration or function call)
- each source code shift is a well defined (unspecified on negative inputs) function
- all shifts in the program are a well defined (unspecified) function
So, for example, the last (least surprising) version means that you have to compile every shift to the target CPU's shift and that you also have to use the target's behavior when you constant fold a shift at compile time.
(2) seems like it is already specified; the trouble is in determining what "the semantics of the program" are. This relates to (1) although it doesn't seem like the author has a completely solid grasp of the legalities of the language.
(1) essentially disables inlining as a side effect, at least if undefined behavior is involved. (2) either is 100% redundant or means that every implementation must strictly execute the C abstract machine with absolutely no optimization permitted. (3) means you can no longer access any type with a char. You also couldn't access the bits of a float by casting to an int.
The second although I think I get the reasoning, seems not well-defined to me. I am not talking about expanding into it with concrete steps. You need to define what kind of semantic invariance to require. You might just not want the compiler deleting sections it thinks do not affect the output; you might not want the compiler to alter nop segments for timing reasons (e.g. when writing a cryptographic primitive). There is a wide variety of different aspects of semantics and it is not clear what you propose. This have been a discussion topic among cryptographers. Or you are a kernel programmer and actually do not want checks removed or aliasing messed with etc. (One reason people compile their kernels with specific options -- see Linus' rants about UB if you want to pull some extra hair of your head.)
Anyways -- I am afraid at times GCC might be too far gone to tone down undefined behavior. Anyone working on a compiler has any input if there are plans, in the (unlikely) case the next WG decides to go sane on undefined behavior, how their compiler is going to address that new standard?
Disclaimer: I have contributed on my own time to one of the GCC frontends, so I guess I know a little bit more about compilers and the compiler development than the average Joe, but I wouldn't call myself an expert nor am I in a position to do any decisions wrt this for GCC. With that out of the way:
- You can see compiler development, particularly the optimizer stuff, as a game, where the standard limits what you can do, and the goal is to make SPEC CPU [1] run as fast as possible (your employer says which target CPU(s) you should focus on).
- The standard is the "contract" between the user and the compiler writers. Compiler writers do take standards conformance pretty seriously.
- If the standard changes, say to limit undefined behavior, compiler developers adapt to the new rules, and the game continues. No big drama here.
- AFAICT GCC developers wouldn't complain that loudly about "losing" previously allowed optimizations. There is (again, AFAICT) sympathy towards the viewpoint of changing the standard towards improving robustness.
- What you won't see is GCC, or any other compiler, doing it on their own without the standard backing them. That would just lose performance compared to the competition, and wouldn't help users write portable code anyway.
[1] Yes, there are other benchmarks too, but SPEC CPU is the most influential one.
Here's the thing I don't quite understand: I gather that this is advocating for something like GCC's -fno-delete-null-pointer-checks to be part of the spec, but, how is -fno-delete-null-pointer-checks actually helpful?
I think it's because if you write code like this:
void foo(struct foo *param) {
int n = param->length, i;
if (param == NULL) {
return;
}
for (i = 0; i < n; i++) {
do_something(param->data[i]);
}
}
But for -fno-delete-null-pointer-checks, you're relying on the second optimization, moving the dereference later. Otherwise you'd just have segfaulted already (or, in a kernel context, the read might have succeeded from a userspace page mapped at the null page). Right?
It seems reasonable for the compiler (or some other tool) to produce a hard error here and prevent this code from compiling, saying, hey, this is clearly doing something unwanted. It doesn't seem reasonable to expect the compiler to do certain optimizations to make your code safe, without which your code would have a security vulnerability, and also get mad at the compiler for doing more optimizations that return it to the original state of things.
> The limitation of lvalue access by types has never made much sense and required a undefensible exception for character pointers.
My understanding of type-based alias analysis is that it's required for code like this to optimize the way you'd want:
struct string {
size_t len;
char *data;
}
void copy_string(struct string *dest, struct string *src) {
size_t i;
if (dest->len < src->len) return;
for (i = 0; i < src->len; i++) {
dest->data[i] = src->data[i];
}
}
You can do this without type-based alias analysis in a language that gave you different tools for managing variables, but doing so backwards-compatibly in C seems difficult, and this proposed rule does not seem to help.
I agree, it would be best if the compiler rejected this as clearly incorrect code. I think that needs a change in the spec relating to undefined behavior, though (and more importantly a change in direction from compiler vendors).
Edit to add: your second example, type aliasing, is a good one too. I think that one could also be usefully addressed by a compiler that flags it as a likely error. Although you’d need some way to annotate the code in the event that the weird aliasing behavior is actually correct and expected (I dunno, make “len” volatile or something?)
My concern is largely about how to phrase "The compiler may not delete this dead code" in a way that's meaningful. For instance, I assume the intent of the proposal is not to forbid optimizing this code in the obvious way, right?
int n = param->length, i;
if (param == NULL) {
return;
}
if (param == NULL) {
return;
}
for (i = 0; i < n; i++) {
do_something(param->data[i]);
}
int n = param->length, i;
for (i = 0; i < n; i++) {
if (param == NULL) {
return;
}
do_something(param->data[i]);
}
> I think that one could also be usefully addressed by a compiler that flags it as a likely error.
The compiler can't know when compiling that one function whether src->len and dest->data alias. It might be compiling that file as a standalone object file, with no other context about who's calling it. Should it emit a warning when compiling that code? (What's the warning, "I'd like to optimize this but I can't?")
Alternatively, should it flag the function ... somehow ... so that when someone else calls it with aliasing arguments, that's an error? That isn't even a capability available to the C language as written: it's valid to call that function knowing nothing other than the struct definition and the function's prototype.
You can imagine a language where variables carried information about whether they alias. (Actually you don't really have to imagine; the `restrict` keyword does a subset of this in C itself, and other languages have much more explicit ways of tracking this, such as Rust's shared vs. mutable references.) But it would be hard to retrofit such a thing onto existing C code.
The fundamental problem with the C language working group is that they're obligated to keep working on C as it already exists.
Yes, that's exactly what I had in mind! :)
More generally, it might be the case that enough of the last several years of unpopular optimizations are controlled by flags that you can compile the code twice, once with the optimization enabled and once without, and warn whenever the optimization changes something. It might even be possible to do this with a shell script that treats the compiler as a black box with -ffunction-sections and uses objdump or something.
I do wonder how hard it is to write code that produces the same object code regardless of something more major like -ftrapv, though.
The optimization isn't written in the form of "If you see this ridiculous code, make it less ridiculous." It's written in the form of "You can refactor repeated checks of presumed-non-aliased variables into a single check." Otherwise code like
for (i = 0; i < *plen; i++)
> some buggy code dereferences a null pointer - which actually works in this implementation.
What implementation is this? (Are you mmapping at NULL, or writing for an architecture without an MMU, or something?)
NULL doesn't have to be address zero. It's denoted by literal zero, in the C source, but it can be something totally different when translated to the machine. Can you arrange for some other address to generate a segfault, and tell your C compiler to use that as NULL? (I don't know how to do this with gcc, and I'd like to know how, honestly - it seems like a significant win for kernel security if NULL pointers in kernel code were an invalid kernelspace address and not an invalid userspace address.)
If so, then again, this has the fundamental problem that you're expecting the compiler to implement some optimizations - like pushing the dereference out of the buggy driver via LTO - and not others. If the compiler had all optimizations off, it would just generate code to read from x->buffer in the obvious place, which would page-fault at runtime before the check from core code even happened.
If the core code implements the check first, then this optimization won't cause you problems, because this optimization is strictly about checking for a NULL pointer after using it.
For the specific case of computing the address of x->buffer without actually dereferencing it, I do agree that the compiler should not consider that to be an implicit non-null promise. That seems much more likely to be a change you can make without breaking the language spec. See the subthread with 'dbaupp.
(Alternatively, you could work on building tools for driver writers to write in a less error-prone language than C, because drivers being of poor quality is a much broader problem with much broader impacts than just triggering ill-advised optimizations under LTO, and simply optimizing drivers less efficiently isn't going to solve the problem that the driver shouldn't be dereferencing x->buffer without its own NULL check in the first place. If you check my recent GitHub activity you might notice a project to do exactly this in Linux....)
I am expecting the compiler to only make optimizations based on things it knows are true - that are true. So if the source code is "check for null;check for null; do something;" the compiler should be able to delete the second check (hopefully with a warning). In fact, the Standard is very explicit about permitting optimizing compilers to delete repeated operations. However, in the case I described, the compiler does not know that the pointer is non-null, it's just easier to assume it is not null. That leads to an "optimization" that is not an optimization. I agree that requiring compilers to only use true optimizations is more of a challenge than allowing them to use false ones, but nobody said it was going to be easy. In particular, it looks like Clang loses way too much information going from source to llvm language which makes it difficult to carry information about whether, for example, a pointer dereference is safe or not - but that's a defect in the compiler, not in the source language.
Something that's actually a pointer offset, not a dereference, like `int *n = ¶m->length`, is also an assertion of being non-null.
It seems reasonable to amend the C standard to say "That's not an assertion of being non-null" (and more generally to make &invalid_pointer->item and &invalid_pointer[n] valid; IIRC implementing offsetof as (size_t)(((type *)NULL)->member) is UB). Would that prevent any significant optimizations?
Also does the rule that pointers can only point to elements of allocated objects or one-past-the-end enable any significant optimizations?
Yes, for segmented architectures like the 8086, it means that pointers don't have to be normalized after every operation. That is, when you increment or decrement a pointer, you only need to do the operation on the offset, you don't have to touch the segment. When all you have is less than 10 MHz, every operation counts.
(For those who don't remember the 8086, it's not as simple as concatenating the segment and the offset to obtain the physical address: to get the 20-bit physical address from the 16-bit segment and the 16-bit offset, the formula is segment*16+offset. As a consequence, the same memory location could be accessed through several distinct segment:offset pairs. If the memory allocator chose the segment value right, objects of 64 KiB or less could be indexed by doing all operations on the offset value, without having to touch the segment value.)
If you really think C is enough of a disaster that this is justified, why even care about fixing C?
The thing is, the redundant null check usually doesn’t appear literally in the source, but comes from an inlined function call (or even a macro). In that case, the null check is probably not a mistake; it’s just that this particular caller of the function that got inlined never passes null, and so will never trigger that code path.
I do think there’s unexplored potential for compilers to identify when they’ve eliminated code that didn’t come from inlining, and warn the user about the potential bug. However, this is much easier said than done, since the IR has gone through a lot of transformations by that point and there are a lot of edge cases to worry about. For example, even if all the IR instructions corresponding to a given piece of source code are dead, that code might still have affected the function compilation in some manner and thus isn’t useless – such as by being merged with a different (or perhaps redundant) computation, or by affecting control flow.
Also, even if some code path really is useless as compiled, it might be for innocuous reasons. For example, perhaps a given null check was not itself inlined, but the value being checked comes from an inlined function:
void *get_a_pointer(void) {
static int x;
return &x; // not null!
}
int main(void) {
void *p = get_a_pointer();
if (p == NULL) …
}
One could argue with the your analogy that UB in C is silly because it assumes programmers who make no mistakes. In reality, writing C code can be economical (adequate safety, low cost, high performance) -- pricing in all the human errors -- and making the proposed would also cost performance and possibly money for some, that's why there is pushback on such proposals.
But you must also know that you must trust at least part of the environment your operating in. There will never be a language or a tool that can make a program useful and correct when nothing can be trusted. C/C++ regarding UB is just explicit about trusting the code that is currently being compiled for the sake of optimizing code that actually is. I get where you're coming from, but this is one of the possible solutions, and a very widely accepted one given that the whole world runs on C.
Managed languages might avoid some class of bugs, but they will always retain some, and I'm not sure it is possible to guard against all without solving the halting problem. Some C/C++ people might on the contrary find it bizarre that your languages do absolutely unnecessary bounds checks. None of them are better than the other on an absolute scale, it all depends on what you want to use the tool for.
That is the typical C hand waving that every language has errors, so no big issue.
Of course there are no perfect programming languages, however it is quite different having to handle "Logic Errors" or "Logic Errors + Memory Corruption Errors + UB Errors + Implicit Conversion Errors".
Even 10% reduction is a major improvement.
You may have misunderstood how rogue optimizers obtain their license to miscompile.
It is not by assuming that the "behavior left undefined is impossible".
As boring and tautological as it sounds, it is by assuming that the operation with "behavior left undefined", when it actually happens, has undefined (and therefore arbitrary) behavior.