Proposal: represent bit pointers at runtime

[mlugg]

I've been working a lot with pointers in Sema recently, and have become fairly confident that our abstraction of "bit pointers" as it stands today is highly flawed. This is a proposal to fundamentally change them.

Background

Currently, bit-pointers work by being a component of the pointer type. The type *align(1:6:8) T contains a pointer to an 8-byte "host" value, which itself has 1-byte alignment, and which contains a value of type T at an offset of 6 bits.

This setup somewhat simplifies code generation, since we don't need to worry about accessing at arbitrary bit offsets, and bit-pointers are given the same in-memory representation as any other pointer type. However, this comes at the cost of confusion. The whole point of a runtime pointer is that we don't need to know anything about the location of its target at compile-time; that information is not encoded in the type. (Well, okay, there's alignment, but you can always use align(1) if you'd like to be able to refer to any address). Bit pointers in their current form violate this rule by effectively encoding part of the address in the type.

Proposal

I propose that we eliminate the *align(a:o:b) T form from the language, and instead introduce a new "bit pointer" type which contains a bit offset in the pointer value. I'll briefly discuss syntax later, but for now, let's just say $T is a bit-pointer to T. const, volatile, and addrspace are all valid on bit-pointers, but align is not, with bit-pointers all being considered to have no alignment requirement (align(1)).

[$]T (a bit many-pointer) can also be introduced; technically a slice-like type also could, but it's less clear how to write that with a new sigil, and besides, it seems to me unnecessary complexity for something that will essentially never be useful (if you do need it, just use a struct of [$]T and usize). Note that [$c]T wouldn't make any sense, since bit-pointers can't interop with C in the first place.

@intFromPtr and @ptrFromInt are not valid operations to convert to and from bit pointers (supercedes #2677). @alignCast is also invalid on bit pointers, but @ptrCast, @constCast, @volatileCast, and @addrSpaceCast are allowed. You cannot in any defined way cast from a bit-pointer to a standard (byte-aligned) pointer(*), but you can coerce in the other direction (this coercion is always safe; it's akin to lowering pointer alignment). Note also that this solves an existing footgun where @ptrCast on a bit-pointer can easily result in pointing to bogus memory; another example of how storing the bit offset as a part of the type leads to trouble.

(*): if desired, we could allow @ptrCast to do this, asserting that the bit offset is 0, but I doubt there's really any situation where it's practically useful.

Justification

While this change may complicate compiler implementation, I believe it significantly simplies the language, and makes it more useful. In my opinion, bit pointers as they stand today are one of the most confusing parts of Zig; they're poorly documented, buggy, rare to come by, have a confusing syntax (it's not immediately clear how they relate to pointer alignment!), and make pointers unexpectedly non-interchangable. The more "opaque" bit-pointer system proposed here is a big simplification: the language-level construct can be simply defined as that "$T is a pointer to a T which may not be byte-aligned", and any details of the representation become implementation details (assuming bit-pointers have undefined layout, which seems to me a reasonable choice).

There are no complexities from ABI interop, since this is not an ABI type. That means we also don't really lose anything from bit-pointers having undefined layout.

Also note that pointers currently have a fourth align field: the "vector index". This is intended to deal with vectors having undefined layout (which they currently don't but hey, y'know!). This proposal would definitively eliminate the need for the vector index. Here's something interesting: the vector index is permitted to be a generic value called "runtime" (this is the type resulting from e.g. &vec[runtime_index]), but there is no memory to actually store the runtime-known index, so these types generally give garbage results when used right now. If we want &vec[runtime_index] to be permitted, these pointers must store this extra information, at which point we essentially have this proposal implemented, just limited to a small subset of types!

Syntax

The $T syntax here isn't a concrete proposal (in fact I don't think I really like it much), it was purely written here so I had something to work with. I did consider the syntax *bit T, but this reserves bit as a keyword, so IMHO is a non-starter. One option would be *align(0) T, although this may be a bit confusing since we've effectively rejected the notion of align(0) in other contexts in the past (#3802), and it makes 0 a special case since it is the only align which changes pointer representation. I'm not 100% sure where to go with this; bikeshedding is encouraged.

Implementation

On the level of semantic analysis, this change, while broad, is fairly simple: allow operations working with pointers to take $T where it makes sense, and to return $T where it makes sense. In terms of runtime representation, I propose that these pointers simply store an additional "bit offset" in the range 0 to 7 alongside the normal byte address. This does have the unfortunate effect of doubling the pointer size (so on 64-bit platforms we pay the cost of 64 bits for just 3 bits of information!), but the rarity of these pointers, and particularly of storing them, makes this (in my eyes) a non-issue.

Note that this representation removes the concept of a "host size" from bit pointers. I don't believe this raises any problems; this is used today essentially tell backends how to load these pointers, but backends can freely make whatever choice they want. In fact, using the host size naively can lead to inefficient code; if loading a 4-byte value from a 64-byte packed struct, we know for a fact that we need to load at most 5 bytes of memory, which will probably fit in a register for easy shifting!

[rohlem]

Simplification suggestion:

• Introduce bitalign keyword where status-quo align(N) is exactly equivalent to bitalign(N*8).
• Use bitalign to designate bit-aligned pointer types without any further syntax changes. (+ allow const/var/member declarations in one fell swoop)
• For builtins with align in the name, similarly introduce bitAlign variants.
• (Optionally rename align to bytealign for disambiguation.)

[mlugg]

Hm, interesting idea. I kinda like it, but my main issue with it is that the switch from "normal, well-defined layout, pointer" to "bit pointer, undefined layout" is non-obvious - it's just when bitalign falls below 8, there's no specific syntactic indicator or anything. I'm not dismissing the idea, and I appreciate the extension of the general concept of alignment to make it work, but I do think that's a little implicit for such a fundamental difference.

[rohlem]

Well, likewise I don't see the reason of why they would have to be so fundamentally different. Pointers are just numbers, depending on alignment they need more or fewer backing bits of information.
Is there a benefit to making bitalign(1) pointer layout be different from std.meta.Int(.unsigned, @bitSizeOf(usize)+3)?
(Also, I've never had a use case where the memory layout of pointer types (aka accessing them by @ptrCast/@bitCast reinterpretation instead of via @xFromY) mattered in the first place. Am I missing out on some fun?)

[mlugg]

Well, likewise I don't see the reason of why they would have to be so fundamentally different. Pointers are just numbers, depending on alignment they need more or fewer backing bits of information. Is there a benefit to making bitalign(1) pointer layout be different from std.meta.Int(.unsigned, @bitSizeOf(usize)+3)?

It could be that, and that's essentially the representation I proposed, but the point is that's still very different to a normal pointer. Pointers have a fixed size, determined by the architecture; the CPU directly dereferences them; and, arguably most importantly, they can be passed over ABI. Bit pointers violate all of these properties: they're necessarily larger than normal pointers, require nontrivial logic to dereference, and cannot be passed over ABI.

[mlugg]

(Also, I've never had a use case where the memory layout of pointer types (aka accessing them by @ptrCast/@bitCast reinterpretation instead of via @xFromY) mattered in the first place. Am I missing out on some fun?)

Probably not, I don't really think there's a use case for reinterpreting pointer values in memory in Zig. The reason pointers having a well-defined layout is important is simply that they can be passed over ABI. Bit pointers can't be passed over ABI, so there's no need for them to have a well-defined layout; and having undefined layout allows an implementation to change its representation down the line if something else turns out more efficient, plus allows for some size optimizations (related: #104).

[rohlem]

Well, okay, I don't want to keep unnecessarily dragging out this 1-on-1 thread without new suggestions.
To me align is already a quite-special-purpose tool that I don't see people (or at least myself) using "on accident" - and even moreso bitalign.
OTOH when you're writing comptime type construction code, you're likely to be aware of the 8-bit size of bytes and can account for it. (Plus compile errors keep you in check.)
I currently can't really come up with a scenario where a layout mismatch would go unnoticed by the type system and manifest as a runtime bug, but maybe I'm not thinking creatively enough.

[jacobly0]

Note that the important part about the host size for backends is not what that size actually is, but rather where does there exist a known-size, known-alignment block of dereferenceable memory that necessarily contains the bit field. Given an arbitrarily large but suitably aligned block, the backend can calculate the optimal offset and load/store size with a still-known alignment to use to actually perform the operation. It may not be obvious with the current set of functional backends, but losing this alignment information will have performance implications on other targets.

---

if loading a 4-byte value from a 64-byte packed struct, we know for a fact that we need to load at most 5 bytes of memory, which will probably fit in a register for easy shifting!

This optimization is not valid without knowing the size and alignment of the packed struct, since it could just as easily be the last field of a packed struct at the end of a page of memory, which could fault if you try to access all 5 bytes starting at a runtime bit offset of 0.

---

While I do not disagree with any of the following points:

• Bit pointers are confusing.
• Bit pointers could use a better, more intuitive syntax.
• Bit pointers are complicated.
• Runtime bit pointers are useful.
• Runtime bit many-pointers are even more useful.

I do not personally draw the conclusion that the current feature needs to be removed, just that the feature could use some work and runtime bit pointers sound cool.

[rohlem]

my main issue with it is that the switch from "normal, well-defined layout, pointer" to "bit pointer, undefined layout" is non-obvious - it's just when bitalign falls below 8, there's no specific syntactic indicator or anything.

Just wanted to add - probably obvious, but since it hasn't been explicitly spelled out yet:
We could make bitalign(N) with N >= 8 a compile error that tells you to use align(N/8) instead.
That way we reinforce one-way-to-do-things, and in the resulting code it's very explicit whether a pointer type anything is bit-aligned or not (by which keyword is being used).

[mlugg]

I just clocked that I forgot to reply to @jacobly0's comment here - that's my bad.

Thanks for explaining why host size matters - I hadn't considered this case. So, without a host size, every bit operation would require a conditional branch to determine how many bytes to load - that's definitely not great.

One option here would be to add runtime bit-pointers on top of the current system; for instance, with bitalign syntax, you can either specify a standard align(a:o:h), to get a comptime-offset bit-pointer like today, or you can specify bitalign(n) for an actual runtime bit-pointer. The former could coerce to the latter, and combining bit-pointers could even be resolved with PTR - neat! I do think that if we expose the concept of bit-pointers in Zig then it really makes sense to support runtime bit-pointers, since the concept isn't very generally useful otherwise.

It's worth noting, however, that direct usage of bit-pointers in user code pretty much never happens - as I mentioned, without runtime bit-pointers, they're actually not a particularly useful concept, since the pointer type kinda locks you into an exact field. The reason they're absolutely necessary is basically for assignments to work - foo.bar = 123 needs to construct the pointer &foo.bar and store into it. Given this, it's worth considering that if we did away with comptime-offset bit-pointers, we wouldn't lose any efficiency in this case if the optimizer could notice that the branch is trivial. For language simplicity, if we can implement this optimization reliably, I would still be in favor of removing comptime-offset bit-pointers, instead having the optimizer identify this trivial property of the runtime bit-pointer. This optimization sounds fairly simple to implement even today - we could annotate trivially known bit-offsets onto AIR instructions, either during semantic analysis or in a later optimization pass.

[alexrp]

FWIW, it's not clear to me how volatile on bit pointers could be implemented correctly, given that we mustn't generate more volatile loads or stores than was written by the programmer.

[rohlem]

it's not clear to me how volatile on bit pointers could be implemented correctly

If we can't, there's also the option to make volatile (accesses via) bit pointers a compile error. (Though maybe that was the obvious intent / implied already.)