Hi @Keno, thanks for adding another set of perspectives and requirements to the discussion!
The one thing I’m going to poke at is “address-like bits”, in the sense that not all pointers are clearly seperable into fields like that. For instance, the address computation on a ptr addrspace (7) %p is %p[80:32] + zext(p[31:0]), if we’re being somewhat strict about it.
I’m going to agree with the proposal that you can have address size = 0, since, like you said, GC roots don’t meaningfully have an address part. I think that such a “no address” pointer could also model (my understanding of) SPIR-V style bindings, where you have this abstract thing called, say, “resource #0” or “buffer #5”, which you can take offsets from, but you’re never allowed to see the address it points to.
And to kick off another round of proposed text
Pointers, version N + 1, draft 1
A pointer is a thing that refers to some object in memory. Values can be loaded from and stored to the memory referred to by a pointer.
The abstract location to which a pointer refers is stable. While, in the case of GC pointers, the location of the value pointed to in system memory can change, one may always assume that, in the absence of intervening modifications through an aliasing pointer (including pointers on other threads of execution), the value stored to a pointer will be the value returned by a subsequent load operation. (Since some pointers refer to memory that is used to communicate with hardware or other progarms, the volatile modifier can be used to require stores and loads to actually be performed.)
Pointers point into objects, which I’m pretty sure are well-defined in the LangRef already so I’m not going to repeat it. You can use
Pointers have address spaces, which are used to define either distinct kinds of memory or distinct means of accessing the same underlying memory. (… pick our favorite examples: TLS on X86 is a different means of accessing the same underlying RAM because it goes to an allocated thread-local bit, while AMDGPU has addrspace(1) and addrspace(3) for global and shared memory, and those are very distinct objects). Whether or not pointers can be losslessly converted between address spaces using the addrspacecast instruction, whether pointers in two address spaces may alias, and whether a cast is even permitted are all target-dependent properties.
Attributes of address spaces
An address space N has five (note, up from four currently) widths associated with it that are stored in the data layout
- The pointer width P , which is the number of bits used to round-trip a pointer in address space P to memory or store it in registers, if applicable
- The ABI width M, which is the number of bits used to hold the pointer in memory. Unlike the pointer width, this must be a power of two. By default, this equals the pointer width
- The ABI alignment, which defaults to match the ABI width and is used for aligning structures, the stack, etc. (See DataLayout, wording to be refined)
- The index width I, which is the number of bits that can be used to take offsets from a pointer. This is, by default, equal to the pointer width. This (should,must,is?) be less than or equal to the pointer width. It may be 0, representing memory locations that cannot be meaningfully traversed. (andgpu p8, indirect bindings, GC roots that don’t carry an offset if that’s a thing). The index width must be less than or equal to the pointer width.
- (new!) The address width A, which is the number of bits used to represent the address within the pointer’s backing memory to which this pointer refers. If this address cannot or should not be computed, or is non-deterministic, the address width may be 0. Note that “backing memory” is often, but not always, a distinct hardware object - for example, a GC pointer that tracks an offset into an object may be “backed” by the memory allocated for that object, so its address component may be an offset. (Similarity, AMDGPU has address space 5 for stack allocations, which are 32-bit pointers that are really pointing into some hardware-managed chunk of stack, which means that, while, from the global view, they’re aimed at a 64-bit address, their address width is 32 bits). It [[TODO, is/isn’t ]] permitted for the address width of a pointer to be greater than its pointer width.
Pointer-handling instructions: getelementptr
(and ptradd if we go there)
getelementptr adds offsets to pointer, existing language fine, nothing’s changing here, the index width is still the index width.
Pointer-handling instructions: ptrtoint
%x = ptrtoint ptr addrspace(N) to iP transforms a pointer %p into its underlying representation as if by bitcast.
That is, it is equivalent to
%m = alloca iM, align(abi width / 8)
store ptr addrspace(N) %p, ptr %m
%x = load iP, ptr %m
ptrtoint may impact escape or alias analysis in [todo nail down what we lose by letting these bitr run raound].
(If the integer type on the ptrtoint isn’t actually the pointer width, zero-extend or truncate the iP as appropriate)
Pointer handling instructions: inttoptr
inttoptr is the inverse of ptrtoint - it takes an iP and produces a ptr addrspace(N) from it.
This is also an as-if-by-memory-round trip bitcast analogous to ptrtoint.
(Same zero-extension/truncation note)
Unseriazable / “non-integral” address spaces
Address spaces have a property separate from their associated widths - serializability. An address space is serializable if the semantics of a pointer can survive the type-punning trip through memory implied by ptrtoint and inttoptr. That is, a serializable address space is one where inttoptr(ptrtoint(%p)) == %p for all %p.
(new!) Pointer-handling instructions: ptrtoaddr
%x = ptrtoaddr ptr addrspace(N) %p to iA returns the underlying address for a pointer as an A-bit integer.
If the address width for a pointer is 0, then ptrtoaddr on that pointer is poison.
The ptrtoaddr instruction is linear with respect to pointer offseting. That is
%p.addr = pntroaddr ptr addrspace(N) %p to iA
%q = getelementptr i8, ptr addrspace(N) %p, iI %x
%q.addr = ptrtoaddr ptr addrspace(N) %q to iA
%px.addr = add_wrapping_low_bits iA %p.addr, iI %x.addr
assert(icmp eq %px.addr, %q.addr)
holds for all pointers %p and all indices %x.
If the pointer width and address width of a pointer are equal, then the behavior of ptrtoint must be the same as the behavior of ptrtoaddr. That is, if your pointer can refer to A bits of memory using A bits of internal storage, that storage must contain said bits. If the pointer width and address width are not equal, there are no guarantees about the relationship between ptrtoint and ptrtoaddr.
(The usual sext/trunc note)
Pointer equality
The equality relationship between pointers in an address space is, ultimately, a target-specific decision. However, it must obey the following invariants:
First, if there exists a pointer %p such that %q = getelementptr i8, ptr addrspace(N) %p, iI %x and %r = getelementptr i8, ptr addrspace(N) %p, iI %y then icmp eq ptr addrspace(N) %q, %r is true if and only if icmp eq iI %x, %y is true, and icmp ne ptr addrspace(N) %q, %r is true if and only if icmp ne iI %x, %y is true.
The getelementptrs in the above definition are not required to produce pointers that are in-bounds or associated with the common ancestor %p.
Note that, if the pointer width, address width, and index are equal, this reduces to comparison between addresses by setting %p = ptr addrspace(N) null. Then, since, ptrtoaddr %q = ptrtoaddr null + %x and ptrtoaddr %r = ptrtoaddr null + %y, by linearity of ptrtoaddr, icmp eq ptr addrspace(N) %q, %r <=> icmp eq iP (ptrtoaddr %q), (ptrtoaddr %r) (As a caveat, if the index width is less than the address width, not all pointers are guaranteed to be reachable from the null value by offseting.)
At a minimum, this invariant requires that pointers within an object that are derived from the same source can be compared for equality based on their offsets by letting the common ancestor %p be the beginning of the object.
The second invariant is that if two pointers can be proven to refer to distinct objects, they must compare unequal. That is, if the set of locations associated with %q and the set of locations associated with %r are disjoint, %q and %r must not compare equal.
The third invariant is that comparison of a pointer to null is always a check that that pointer is equal to the null pointer for that address space in a ptrtoint sense.
For the CHERI folks, I think the above definition lets you have C-style “pointer equality is address equality” if you want it without too much pain. As far as middle-end passes are concerned, you can reason about equality of pointers that point into the same thing and share a capability, and if you know that two pointers don’t alias (two globals, or a global and an alloca, say), you can target-independently conclude that they’re not equal. From there, you’ve got wiggle room to define that two pointers into the same object are equal even if their capabilities don’t match, but nothing above required that.
And then it’s possible to take the opposite extension of == into an annotated pointer, and I can say that two buffer fat pointers are unequal if they’ve got different base addresses, whether or not there’s aliasing between those, because those two resources don’t have a common ancestor I can construct them from with GEP.
Integral address spaces
For brevity / historical reasons, a serializable address space where the pointer width, address width, and index width are all equal is called “integral”.
Special notes about address space 0
Address space 0 is required to be integral, to have a bit-pattern-0 pointer tha’t can’t be dereferenced unless annotated with null_pointer_is_valid, and to have (ptrtoint ptr null) == 0 (I think that last one’s still true).
Tangents
Side RFC: Can we get an addrspacecast-like that takes arguments?
There’re various operations on pointers - p8 @llvm.amdgcn.make.buffer.rsrc(p{0,1} base, i16 stride, i32 numRecords, i32 flags) comes to mind that are basically addrspacecast but need extra arguments. I think the current handling for these is to list them out in a function that contains all the intrinsics that return pointers which alias their argument. Is this fine, or do we want to something a bit more systematic here?
Side RFC: Multiple indices
There exist pointers (pointers into textures in graphics are the example at the top of my head) that meangfully have more than one index field. For example, some buffer resources on (at least AMD) GPUs are indexed by both an index and an offset, which form an indexing hierarchy of sorts. That is, bringing [RFC] Replacing getelementptr with ptradd - #16 by nhaehnle back to folks’ attention since we’re having another round of this sort of thing