How I think about C99 strict aliasing rules | Hacker News Reader

How I think about C99 strict aliasing rules

alanwu.space

65 pointsbwidlar49 comments

It really seems like the compiler writers have gone insane in the last decade or so. Any reasonable person would look at the standard and conclude the intent is to describe what is required to write super-portable programs. Yes, you could have 1s-complement or sign-magnitude integers, so you can't rely on signed overflow for portable code. Yes, you could have separate address spaces for floating point and integers, so you can't rely on cross-type pointer casts or address arithmetic for portable code.

But the compiler writers are using "undefined behavior" as justification to break code on machines that don't have weird address spaces and don't use 1-s complement integers.

So the result... anyone who wants C/C++ to just be a high level assembler is going to need to do all their arithmetic with unsigned and all their pointers as char. Say goodbye to readability or type safety.

There are lots of real-world cases where type-based alias analysis produces not just better, but even just "decent" code. Example:

    void add_all(float **x, float **y, int m, int n) {
        for (int i = 0; i < m; i++)
            for (int j = 0; i < n; i++)
                x[i][j] += y[i][j];
    }

without TBAA cannot be optimized to

    void add_all(float **x, float **y, int m, int n) {
        for (int i = 0; i < m; i++) {
            float *xi = x[i], *yi = y[i];
            for (int j = 0; i < n; i++)
                xi[j] += yi[j];
    }

Or for overflow, "x[i] = 0;" cannot be compiled to "movl [x+RAX*4], 0" if i is an "unsigned int".

> Or for overflow, "x[i] = 0;" cannot be compiled to "movl [x+RAX*4], 0" if i is an "unsigned int".

This is another pet peeve of mine. Why does almost every justification about UB and signed overflow involve using a 32 bit integer on a 64 bit platform? Change those int variables to ssize_t (or size_t if you must), and it's good.

Instead of creating and jumping through insane hoops to improve bad code, they should warn you that there are performance costs for using the wrong sized integer as an array subscript.

Edit: Oops, I missed the point on the first one. So I removed a bad example.

> using a 32 bit integer on a 64 bit platform?

Not about integers, but in general: maybe 64-bit is overkill. The trend in ML has been to reduce size:

"We have demonstrated DNN training [using nVidia GPUs] with 8-bit floating point numbers (FP8) that achieves 2−4× speedup [compared to FP32 computation] without compromise in accuracy [on most CNN/DNN test accuracy degradation is ~0% stochastically, but max 2% on specific ImageNet runs]."

https://arxiv.org/abs/1812.08011

It's not obvious unless you read and think about the assembly, but bonzini's point was that using a 32 bit signed int (which is not allowed to overflow) means the compiler can cleverly promote it to use register RAX as an index without any other shenanigans to deal with 32 bit overflow. RAX is a 64 bit register for integers or pointers. There are reasons why this might be advantageous over using EAX, which is the name for the low 32 bits of RAX. It's very possible that bonzini is referring to the example in the following link:

https://www.youtube.com/watch?v=yG1OZ69H_-o&t=2357s

Back to your overall point though, you're right that there's frequently an advantage to having your bulk data use smaller data types. It's better for caching and memory bandwidth, and it opens up more possibilities for parallelization with SIMD or GPU magic. However, it's really a false economy for things like loop indices. It doesn't matter if you declare your variable to be int8_t using just 1 byte, because it's probably going to tie up an entire 64 bit register anyways. There are ways to use only parts of registers, so you can pretend you have more registers, but these cause dependency stalls and are generally not good for modern processors, or at least not a win for speed.

To a lesser extent, it's a false economy with floating point on the CPU too. Your 32 bit float is likely taking up an entire 128 bit (or larger) SIMD register, and the operations generally have the same latency and throughput as their 64 bit (double) equivalent.

The rules can be very different on a GPU of course.

> There are reasons why this might be advantageous over using EAX, which is the name for the low 32 bits of RAX.

EAX is not available in addresses.

> It's very possible that bonzini is referring to the example in the following link

Not intentionally but yes.

> EAX is not available in addresses.

Is this a relevant correction? If there is a point, ignore the following.

You seem to like the ATT syntax, which I avoid whenever I can. However, if there isn't a specific point, and we're just being pedantic or having a pissing match, copy the following:

    mov rbx, [rax + 4*rax]
    mov rbx, [eax + 4*eax]

    movss xmm0, [rax + 4*rax]
    movss xmm0, [eax + 4*eax]

into https://defuse.ca/online-x86-assembler.htm with the x64 option enabled. Your original example had float, so I included that as well. They all assemble, and the difference is in the REX prefix.

I haven't looked at it in a few years, and I've forgotten a lot of details, but I wrote my own x86-64 assembler for fun. And of course, like most assemblers, I improvised my own syntax and naming convention. In particular, I didn't make a distinction between EAX and RAX (or AX or ALO). To me, it's just register A, and I gave the opcodes more descriptive names to indicate the bit width.

I figure if gas can do something like ATT syntax, I can do my own my way.

Bah, for the best optimisation, you need restrict (https://en.wikipedia.org/wiki/Restrict) anyway..

> Any reasonable person would look at the standard and conclude the intent is ...

Any reasonable person would look at the standard and conclude there is no other implicit intent than to describe a standard.

> anyone who wants C/C++ to just be a high level assembler

They never got the right to pretend it, as C/C++ was never meant to be that. Sure, the first (several) versions of the compiler were not as smart as modern ones, but any reasonable person who would have looked at the standard should have understood since day 1 what all this was about.

> the compiler writers are using "undefined behavior" as justification to break code on machines that ...

If you are reasoning on any other machine that the C virtual machine, _you_ are wrong. If you want to reason about X86, use assembly. Higher level languages are not coupled to any particular hardware.

> Any reasonable person would look at the standard and conclude there is no other implicit intent than to describe a standard.

That's complete nonsense. If there wasn't intent, it would just be random words making random rules. There was a reason and motivation behind the creation of those rules, and reasonable people can at least speculate about the motivation.

> If you are reasoning on any other machine that the C virtual machine, _you_ are wrong.

The underscore is very dramatic. :-)

> If you want to reason about X86, use assembly. Higher level languages are not coupled to any particular hardware.

I never said anything about X86. I think maybe you're reliving an argument with someone else.

However, all of i686, AMD64, ARM, AArch64, PowerPC, RISC-V, Alpha, PA-RISC, or any mass market server, desktop, laptop, or smartphone in the last 30 years have one address space and use 2's complement for signed integers. It's a choice for a high level language to pretend that's not true.

It's a choice to pretend that other architectures cannot exist, or if they do, you can't port C to them.

> all of ... in the last 30 years have one address space and use 2's complement for signed integers

Yes, they do.

The C virtual machine never did and never will.

Incorrect, C2x will and that matters for casts from unsigned to signed. But signed overflow will remain undefined

> It's a choice for a high level language to pretend that's not true.

It's a choice C did since its inception: stop whining and accept the fact, please!

Again, so dramatic with the explanation point. :-)

You do know your posting history is readable to all of us, right? It's very clear that your game is to post a 1 or 2 line snipe to try and antagonize people. You do you, but I'm not whining, and you're just trolling.

Best wishes.

The next version of C will have twos-complement only. But that has nothing to do with overflow being undefined; you could make it implementation-defined if all you cared about was -magnitude and ones-complement representation, or saturating arithmetic.

> But that has nothing to do with overflow being undefined;

That's not the whole story [0]. It looks like JF Bastien managed to convince everyone that 2's complement is the only signed representation that exists and is worth considering, and so pretending to be portable to anything else is pointless. But then he met "strong resistance" trying to finish the job:

The author had hoped to make this well-defined as wrapping (the operations produce the same value bits as for the corresponding unsigned type), but WG21 had strong resistance against this.

So at least one standards person tried to achieve sanity, but he was overwhelmed or outnumbered by the rest of the asylum.

For a stand alone application, -fwrapv makes this silliness go away. However, if I want to write a library where I don't get to control the options my end users select, we're going to end up with silliness like this:

    struct integer { intptr_t val; };
    integer operator +(integer lhs, integer rhs) {
        return (integer) { intptr_t(uintptr_t(lhs.val) + uintptr_t(rhs.val)) };
    }

There. Now I've got sane integers. Compliant, and I'll bet it optimizes just as well.

[0[] https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p09...

> So at least one standards person tried to achieve sanity

At the cost of real-world pessimization of generated code.

It's basically impossible to optimize induction variables without undefined signed overflow, and it's possibly the most important optimization for C code, maybe after inlining and simple manipulations such as dead code elimination.

On the other hand, defining right shift of negative numbers is now a no brainer. No compiler even thought of exploiting UB there, and C2X will codify that.

> Compliant, and I'll bet it optimizes just as well.

Try, you will be surprised.

> It's basically impossible to optimize induction variables without undefined signed overflow

Here's a piece of code you can compile with:

    gcc -O3 -Wall -Wextra mandel.c -DINTEGER=size_t -o mansize
    gcc -O3 -Wall -Wextra mandel.c -DINTEGER=int -o manint

https://godbolt.org/z/Wx4aavvjj

Both versions, the one with the signed integer UB you claim is so important, and the one using size_t with no UB worries at all run in about .28 seconds on my desktop.

I can imagine you'll have some objection: This isn't a true Scotsman, or this isn't representative of real world code, or this example makes it too easy for the compiler to optimize, or that's not about induction variables, or something creative...

That's fine, but the next example is on you. I look forward to seeing what you come up with.

> it's possibly the most important optimization for C code, maybe after inlining and simple manipulations such as dead code elimination.

Dead code elimination is one of the most important optimizations?!? Are you worried about binary size or CPU time?

> This isn't a true Scotsman, or this isn't representative of real world code

It is, but induction variables optimization generally requires lots of memory accesses. I will try to come up with something.

> Dead code elimination is one of the most important optimizations

Yes, inlined code has a lot of constant conditions and code that similarly only follows one path only. Dead code elimination, constant propagation, eliminating stuff like &*x so that x can stay in a register, are all very important to achieve zero-cost abstraction. Mostly in C++, Rust and the like, but also in C.

> I will try to come up with something.

Looking forward to it.

As I expected, you haven't backed up your claims. Maybe you should admit they aren't true, at least to yourself.

The semantics of "restrict", which made it into C99, inherently require the anything-goes interpretation of UB to have the keyword make any sense. These means your "faulty" definition of undefined behavior is at least 23 years old. If you dig a little deeper, it has to be even older. The semantics of unions were changed in C99 so as to make type punning via unions no longer UB--which at least implies that people were thinking about the optimization effects of UB even earlier.

The other thing to note was that if UB were "just" about portability to "weird" machines... why did the C committee choose to make it undefined instead of implementation-defined? The specification already has a tool that gives compilers flexibility for weird architectures; not using that tool suggests that the committee didn't want to require the compiler to do something "reasonable."

Your question seems to be rhetorical and assumes that I know the answer, but I don't. Why did they choose to make all this stuff UB instead of implementation-defined? I don't really understand why we have UB at all instead of all of that stuff being implementation-defined. Other languages have far fewer things that they consider UB, and that seems better to me. Why was having a large swath of UB considered better?

I think historically the idea behind UB was to allow to write a compliant compiler (for different platforms) as easily as possible. (so to decrease the burden on the compiler writer). This has worked. Why they kept this approach? I dont know.

There are a few reasons to make things UB. One of the big reasons is--drumroll--to enable compiler optimizations. The other big reason is some variation on the problem that actually coming up with reasonable semantics is difficult to impossible, and often one of the factors that makes such semantics difficult is again because of compiler optimizations.

I think there's a big misconception here that the use of UB to drive optimizations is somehow a perversion of the original design for C, but the evidence strongly points away from that. In particular, strict aliasing rules don't really make sense unless you're going to use them to afford optimization opportunities, and those were present as far back as C89.

I will additionally point out that any C-like language is going to have a large kernel of necessarily UB to permit any optimization whatsoever (namely, UB in relation to memory unsafety) [1]. The things in C where people most complain about UB--namely signed integer overflow and strict aliasing--also happen to be the ones where there's no good reason to interpret C89's decision to make them UB instead of something lesser as anything other than letting compilers optimize them because they're UB. Even if it seems to be gratuitous (and I would personally argue that it is), it is very much intentional.

[1] Yes, even Rust makes this UB.

I've thought a lot about the restrict keyword since a month ago when you and I argued about this in the context of intentionally adding UB to Rust.

I think you're wrong to conclude that UB was some kind of goal for "restrict" in C. As I remember it, there was a bit of envy in how Fortran compilers could make a few optimizations that C compilers could not. (Even now, some of the old-time Fortran advocates still trot this out as a reason Fortran is better) So C needed a way to say, "this function is more like Fortran now, go ahead and re-order the reads and writes if it helps". Thus "restrict" was born as a promise from the programmer to the compiler. The keyword mostly makes sense from that point of view, but of course there are devils in the details as shown in Ralf's article.

I haven't seen the mission statement, but there seems to be some agreement that the intent of the standards committee was to "codify existing practice" rather than define things on first principles or something. I'm sympathetic to the standard saying, "it's undefined to break your promise on this new feature we gave you".

As for why to make things like signed overflow undefined vs implementation defined, we could argue about it. If you've got a link to something more than speculation about that choice, I'd like to read it. My opinion shouldn't be terribly valuable to anyone.

> not using that tool suggests that the committee didn't want to require the compiler to do something "reasonable."

I believe it's a completely valid interpretation to treat undefined behavior as implementation defined. Maybe the whole point was, "Let them do what they want. The users can pick a different compiler if they want."

At this point, assuming the future standards mission is still to "codify existing practice", they'll probably keep listening to the compiler writers and programmers who prefer niche optimizations over sanity.

Btw, you should think about whether these optimizations are really that valuable. You're paying a cost, are you getting a benefit? Take a computationally intensive program you care about and recompile it with -frwapv. Don't just look at the assembly, measure the run time. Outside of some contrived example you don't really care about, I doubt you'll see much difference. And even if you do have an example you care about, I'm guessing it could be fixed by changing a 32 bit signed int to use a 64 bit array index.

> As for why to make things like signed overflow undefined vs implementation defined, we could argue about it. If you've got a link to something more than speculation about that choice, I'd like to read it. My opinion shouldn't be terribly valuable to anyone.

I'm (slowly) working on a "In Defense of UB" blog post, and I'm going to see if I can track down some old C committee members who might be able to offer more than speculation here. But I can't guarantee it, this is about discussions that happened well over 3 decades ago, and there's a good chance that recollections of details from that time are imperfect or just plain missing.

I'll be eager to read that when you're done. I doubt I'll agree with your thesis, but still :-)

I just went and skimmed the forward from an early version of "The C Programming Language" book [0]. There's certainly mention of writing portable programs, but UB as a device doesn't seem to be in there. And who knows what passed for "portability" in the early 70s - with enough preprocessor conditionals, you could have completely separate programs in the same file.

> I'm going to see if I can track down some old C committee members

I'll be interested in what they say, but any committee of more than one person is going to have varying beliefs and motivations. I'm sure you wouldn't do this, but it'd be possible to emphasize the examples that support your position while neglecting other view points.

I also hope you'll at least consider Dennis Ritchie's perspective on the topic. Since he created the language, I think his opinion should carry more weight than most others. I haven't tracked the whole history of how "noalias" became "restrict", but he pretty clearly thought "noalias" was an "abomination" that created "hash of apparently safe programs". [1] At the very least, I think it shows he was opposed to making "hash" in the name of optimizations.

I had no idea this debate has been going on since 1988. I guess compiler writers have been insane for much longer than I knew.

[0] https://archive.org/details/TheCProgrammingLanguageFirstEdit...

[1] https://groups.google.com/g/comp.lang.c/c/K0Cz2s9il3E/m/YDyo...

You cannot anymore. "There is One True Representation for signed integers, and that representation is two’s complement" (P0907R4)

This part is telling:

> If a signed operation would naturally produce a value that is not within the range of the result type, the behavior is undefined. The author had hoped to make this well-defined as wrapping (the operations produce the same value bits as for the corresponding unsigned type), but WG21 had strong resistance against this.

So, even within the standards group there are disagreements on the topic.

It's a good point that aliasing issues may show up as different warnings, like maybe-uninitialized in the example. Those warnings are often not obvious at all.

Beyond this, one thing I have been putting thoughts into is removing integer promotion and the implicit casts (except for void*) and use explicit static/dynamic casts (not with the horrible c++ syntax). I also thought about static and dynamic consts, but if I understood well, constant folding would be one of the easiest optimizations to do, then that would not be worth it. I still wonder what typedef/typeof/_Generic are doing into C. They may be "cheap" to implement, but could lead to excessive generalizations with a strong smell of Rube Goldberg Machine (happening in the linux kernel).

typedef has been there since at least C89... the only alternative is #define - how is that better?

I have always imagine LTO to be such a huge pandora's box regarding this type of issues (e.g. the removal of the impicit memory barrier between function calls) that the fact that it isn't (e.g. many distributions enable lto by default) means that either these problems are way overblown or compilers are still keeping barriers between function calls internally.

Compilers definitely don't keep barriers between function calls internally. AFAIK LTO enables inlining as well, but inlining is not the only inter-procedural optimization that can happen.

but LTO enables interproc optimizations between separate compilation units.

Yes. OP should mention that they talk about "function calls (to functions defined in other translation units)", even though it's semi-implicit in mentioning LTO.

For code that has to do clever things with types, I've now given up on the C type system and just copy bytes through arrays of uint64_t instead. I miss structs but overall the loss is workable. Atomics through the non-standardised intrinsics that work on normal types instead of the _Atomic qualified ones.

Can you give an example?

> I've now given up on the C type system and just copy bytes through arrays of uint64_t instead. I miss structs but overall the loss is workable.

Can you elaborate? This sounds like you're using uint64_t as an universal-aliasing-mcguffin, which doesn't work, so I'm guessing that's not what you mean?

I've been putting off replying until at a desk but that's not worked out.

What used to be struct { atomic_uint64_t count; uint32_t X; uint32_t Y; void * Z; }; is now a uint64_t[4] with bytewise copies to get the void* back and intrinsics for the atomic operations.

Functions all take a uint64_t* so the array length is discarded. Means some functions can take a pointer to the refcount field and others to the first data field for when there is no refcount involved.

uint64_t has no magic aliasing properties, but pointers and doubles can be memcpy'd into it, and things like uint64_t data[2048] in .rodata can have whatever set of objects one likes embedded in it. Slightly sketchy is casting addresses directly to uint64_t instead of memcpy but clang does not yet mangle code doing that. Will change static data to asm when it does.

This makes writing correct C moderately harder but has the redeeming feature that type based alias analysis is no longer a hazard.

This was a good article, and more such articles with examples are needed because understanding how pointer aliasing works can yield significant performance gains, since the compiler can be directed to make optimizations it would otherwise not make.

linux kernel defaults to 'no-strict-aliasing'.

I wonder if this statement is correct: "always do -fno-strict-aliasing by default, only do -fstrict-aliasing where the performance bottleneck is"? It seems like a compromise between safety(less UB) and performance to me.

Why was the "How" removed from the title? "How I think about C99 strict aliasing rules" is surely much more appropriate?

Yes, HN's title truncator is overzealous sometimes. We've recapitated the title above.

I think I've asked this before, but can you please make the title change not silent, but something like "we've improved the title" with an accept or restore click?

The current flow is really unfortunate.

It’s ironic that this website is built on the one language known more than anything else for making fast, sweeping changes on the fly and yet has changed arguably the least of any message board of the last 20 years.

There have been many changes—just not many visible changes. Users hate change.

Reply on news.ycombinator.com