How I think about C99 strict aliasing rules

https://alanwu.space/post/strict-aliasing/

by bwidlar • 4 years ago

65 49 4 years ago

sylware• 4 years ago

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).

spacechild1• 4 years ago

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

mort96• 4 years ago

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

dang2• 4 years ago

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

Tomte• 4 years ago

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.

JonChesterfield2• 4 years ago

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.

andi9992• 4 years ago

Can you give an example?

formerly_proven• 4 years ago

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?

JonChesterfield2• 4 years ago

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.

xscott13• 4 years ago

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.

bonzini6• 4 years ago

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".

xscott13• 4 years ago

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.

renox• 4 years ago

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

pif3• 4 years ago

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.

xscott13• 4 years ago

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.

jcranmer3• 4 years ago

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."

electroly• 4 years ago

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?

xscott13• 4 years ago

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.

manwe150• 4 years ago

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

xscott13• 4 years ago

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.

lloda• 4 years ago

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.

AshamedCaptain• 4 years ago

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.

planede• 4 years ago

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.

gpderetta• 4 years ago

but LTO enables interproc optimizations between separate compilation units.

Annatar• 4 years ago

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.

synergy20• 4 years ago

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.

How I think about C99 strict aliasing rules

Related Stories