[RFC] Allocator Provenance Model

IR & Optimizations
1

Motivation

We model memory allocation as “creating” provenance and memory deallocation as “destroying” provenance. This is reasonably well-defined in cases where the implementation of the allocator lives in a different module. However, it becomes unclear what exactly these terms mean when the allocator is visible in the same module. This RFC is an attempt to specify the provenance semantics of allocators in LLVM, and provide the means to correctly handle them even if asymmetrically inlined.

Additionally, the proposal also provides a mechanism to represent one large allocation that contains multiple smaller ones in a way that can be understood by the optimizer. This desire has previously come up in N-ary separate_objects / non-argument `noalias` groups, esp. in the context of GPU targets.

There are a number of challenges related to allocator provenance, but I think the most important ones are:

  • Nesting. For example, a bump pointer allocator might use a custom allocator, which might in turn use malloc. Our specified semantics for return-position noalias (which is used primarily to denote allocators) is “a pointer to allocated storage disjoint from the storage for any other object accessible to the caller”. However, if there are (visible) nested allocators, both the allocator return value and the underlying allocation it is serviced from may both be “accessible”.
  • Free-lists. The provenance of the pointer passed to the deallocator function is destroyed – however, the deallocator may stash the pointer inside a free list and then return it from the allocator again. The pointer returned from the allocator of course can’t have destroyed provenance.
  • Leaked allocations. It’s possible for allocations to never be explicitly deallocated (i.e. leak), but the parent allocation to be freed. A typical example is a bump pointer allocator going out of scope. How to handle this is an open question of the proposal.

Proposal

Intrinsics

We model allocator provenance using two new intrinsics llvm.provenance.alloc and llvm.provenance.dealloc. Allocators should call llvm.provenance.alloc when returning the pointer from the allocator and llvm.provenance.dealloc when accepting the pointer argument to the deallocator:

define ptr noalias @"operator new"(i64 %size) {
   %p = ... ; Somehow obtain the memory
   %p.alloc = call ptr @llvm.provenance.alloc(ptr %p, i64 %size)
   ret ptr %p.alloc
}

define void @"operator delete"(ptr %p.alloc) {
   %p = call ptr @llvm.provenance.dealloc(ptr %p.alloc)
   ... ; Do something with the freed memory, e.g. put it in a free list.
   ret void
}

For allocators that are visible and may be inlined, these intrinsics should be explicitly materialized. For inaccessible allocators, we can just pretend these operations are there to understand their semantics. The intrinsics can also be used entirely standalone to manage sub-allocations of a larger allocation.

Allocator provenance

Allocator provenance forms a tree, where each allocation adds a new leaf provenance, which remembers which parent allocator provenance it was derived from. A deallocation removes a leaf (or subtree). Only the leaves have (full) access to the memory range they cover.

More explicitly, the semantics of the two intrinsics are:

%ptr = @llvm.provenance.alloc(%ptr_orig, %size):

  • If %ptr_orig is a null pointer, return a null pointer.
  • We call the provenance of %ptr_orig the parent allocator provenance. It must have access permissions for %size bytes starting at %ptr_orig, otherwise the behavior is undefined.
  • Access permissions for %size bytes starting at %ptr_orig are masked in the parent allocator provenance (including any provenance derived from it). “Masked” means that loads (using the parent allocator provenance) return poison, while stored caused undefined behavior.
  • Returns a pointer to a new allocated object of size %size at address %ptr_orig (which has access permissions for %size bytes starting at %ptr_orig).

%ptr_orig = @llvm.provenance.dealloc(%ptr):

  • If %ptr is a null pointer, return a null pointer.
  • %ptr must have allocator provenance, otherwise the behavior is undefined.
  • Destroy the allocated object %ptr (which includes “destroying” the provenance and disabling all access permissions). What happens if there is any live child allocator provenance is discussed later.
  • Restore masked access permissions for %size bytes starting at %ptr in the parent allocator provenance.
  • Return a pointer with the parent allocator provenance.

Permission masking

When a sub-allocation is created, we want the memory covered by that sub-allocation to no longer be accessible by the parent allocation, otherwise we could not treat the sub-allocation as an identified object for alias analysis purposes.

At the same time, making all memory accesses to the memory region through the parent allocation UB would imply that the parent allocation is no longer fully dereferenceable, in the sense that speculating loads into it may cause UB. This is a problem, because we assume that allocas and globals are always dereferenceable, and we’d like it to be possible to produce sub-allocations of allocas/globals.

As such, “masked permissions” have the same semantics as allocas after lifetime.end: Loads with masked permissions result in a poison value, while stores cause undefined behavior. This also means that llvm.provenance.alloc is nofree, as it does not render any bytes non-dereferenceable.

Conversely, llvm.provenance.dealloc fully disables permissions (“destroys” the provenance), so both loads and stores become UB.

Open question: Leaked allocations

An open question of this proposal is how to handle leaked allocations. Consider the following setup: We allocate a chunk of memory using malloc() and use it as the backing memory for a bump pointer allocator. The allocations returned by the bump pointer allocator are (typically) never freed. However, the backing storage will get freed().

This poses a problem for using return-position noalias on the result of the bump pointer allocator.

%ptr = call noalias ptr @bump_ptr_alloc(ptr %underlying_allocation, i64 %size)
%v = load i32, ptr %ptr
call void @free(ptr %underlying_allocation)

Under current semantics, the return-position noalias here implies that the @free() call cannot affect %ptr, so it would be fine to sink the load below the @free() call. Of course, this does not hold in this setup.

I think there are basically two ways to solve this:

  • Do not allow deallocating a parent allocation while there are still live child allocations. In practice, this means that the allocator modelling framework can mostly only be used for global allocators which don’t have a freeable parent allocation (or at least we can pretend that they don’t, because it’s only freed on program shutdown). This means bump pointer allocators cannot be annotated noalias (or __attribute__((malloc)) in C).
  • Weaken return-position noalias to not be noalias with regard to unknown non-nofree calls.

A possible middle-ground here would be to change the llvm.provenance.alloc signature to be something like this:

declare ptr @llvm.provenance.alloc(ptr %p, i64 %size, i1 immarg %can_free_via_parent)

Where the %can_free_via_parent argument determines whether it’s legal to free an ancestor allocation while this allocation is still live. If %can_free_via_parent is false, then the return value is noalias (with its current meaning). If %can_free_via_parent is true, then it’s not noalias (though if we wanted, we could add an attribute to encode the weaker semantics, like a freeable_noalias).

Reallocation

Reallocation can be represented by a combination of @llvm.provenance.dealloc (on entry to the reallocator) and @llvm.provenance.alloc (on return from the reallocator).

Notably, this combination of dealloc+alloc implies the usual reallocation semantics, where accesses through the original pointer are UB after reallocation, even if the address of the allocation stays the same. LLVM also has a notion of in-place growable allocations, where the original pointer can be used after the grow operation. We could introduce an additional @llvm.provenance.grow intrinsic to represent such an in-place grow operation, but this proposal doesn’t do so.

A consequence of representing realloc using dealloc+alloc is that dealloc cannot poison the memory (contrary to a previous version of this proposal). However, LLVM currently implicitly assumes that allockind("free") poisons the memory (or more specifically, that removing stores prior to free is legal). An additional allockind flag to indicate whether free poisons the memory will be needed (like allockind("free,poisons_memory")).

Address identity

LLVM currently makes a number of assumptions about address identity of functions with noalias returns. It was always dubious to bind these to noalias (which is a statement about provenance only), but this RFC makes the problem more obvious.

The first assumption is that the address of the allocation is unpredictable. That is, we can always fold comparisons of the address with another address (not derived from the allocation) to false, as long as this happens consistently for all observations of the allocation address. This clearly does not hold up under this proposal, because the address of the @llvm.provenance.alloc return value is the same as its argument.

The second assumption is that noalias return allocations can not overlap with allocas or globals. This is also not true under this proposal, as it’s possible to perform an @llvm.provenance.alloc on a global or alloc (and in fact, doing this on globals is a primary use case, see “standalone usage” below).

To address this, assumptions about allocation addresses should be decoupled from noalias and moved to allockind properties instead. There should be an address_unpredictable property for the first assumption, and an alloc_disjoint property for the second. alloc_disjoint can only be used for top-level allocators which are not nested within another allocator.

Standalone usage

The allocator provenance intrinsics can also be used standalone, for use cases like the ones discussed in N-ary separate_objects / non-argument `noalias` groups.

For example, a global of multiple merged allocations could looks something like this:

@merged_global = [TOTAL_SIZE x i8]

; ...
%global1 = call noalias ptr @llvm.provenance.alloc(ptr @merged_global, i64 SIZE_1)
%global2 = call noalias ptr @llvm.provenance.alloc(
    ptr getelementptr (i8, ptr @merged_global, i64 SIZE_1), i64 SIZE_2)
; ...

This is of course under the assumption that there is a single place where these sub-allocations can be created (e.g. at the start of a kernel). This model does not work if you need multiple places to independently derive pointers to sub-allocations.

This also covers the case where allocations can be freed again (via @llvm.provenance.dealloc) and the memory reused.

Attributes

The attributes that are applicable to the two intrinsics are as follows:

declare noalias ptr @llvm.provenance.alloc(ptr %ptr_orig, i64 %size)
    nofree nosync nocallback
    memory(argmem: readwrite, inaccessiblemem: readwrite)
    allockind("alloc") allocsize(1) "alloc-family"="provenance-alloc"

declare ptr @llvm.provenance.dealloc(ptr allocptr captures(address) %ptr)
    nosync nocallback
    memory(argmem: readwrite, inaccessiblemem: readwrite) 
    allockind("free") "alloc-family"="provenance-alloc"

Some notes on the attributes:

  • The argument to dealloc is captures(address), i.e. the provenance is not captured. This is valid, because provenance non-capture means that the provenance of the pointer passed to the intrinsic is disabled when the intrinsic returns. This is fine, because the return value of @llvm.provenance.dealloc recovers the parent allocator provenance, so free-list style usages are still valid.
  • Pairs of provenance.alloc/provenance.dealloc on the same pointer can be elided, under the usual allockind constraints.
  • We do not assume that the pointers are nonnull, to make integration with fallible allocators easier.
  • We do not assume that @llvm.provenance.alloc initializes the memory to any particular value.
  • Both intrinsics read and write argument memory, to indicate that accesses (to the parent or child allocation) cannot be reordered around these intrinsics. Both intrinsics also have inaccessiblemem: readwrite, because they cannot be freely moved. (Is the inaccessiblemem actually needed if we already have argmem: readwrite?)
  • The presence of the noalias return attribute is contingent on which semantics we pick for “leaked allocations”. E.g. if we have a %can_free_via_parent flag, noalias would only apply if it is false.
  • We don’t specify allockinds address_unpredictable, alloc_disjoint on alloc or poisons_memory on dealloc for reasons explained above.

Changelog

  • 2026-06-22: Changed dealloc to not poison memory, and added section on “reallocation”.
  • 2026-06-22: Added section on address identity, with proposed additional allockind values to control address identitiy optimizations.
4 Likes
LLVM Weekly - #651, June 22nd 2026
2

Looks interesting!

One thing that comes to mind is restrict. In a way, it’s also a way to restrict permissions on a pointer. It is different from what you are proposing because with restrict we may know the byte size statically and we cannot invalidate the parent.
I’m just wondering if it’s worth solving both problems at the same time, since they share the same common interest of restricting access to only parts of an object.

3

Do we need something like llvm.provenance.realloc for the case where realloc doesn’t allocate new memory? This cannot be represented by dealloc+alloc pairs since contents are poisoned after deallocation.

4

I think llvm.provenance.realloc would be somewhat problematic in terms of practical usage: If we have a user-provided reallocator (this doesn’t exist in C++, but e.g. there is GlobalAlloc::realloc in Rust), we don’t really know whether the return value is an in-place reallocation or not. So I’m not sure how we would insert the intrinsic in that case.

It’s probably better to just drop the “llvm.provenance.dealloc poisons the memory” bit, in which case realloc can be implemented as a simple combination of dealloc (on entry) and alloc (on return).

However, this will also need a minor change to allockind("free") to be able to explicitly specify whether free can read the memory or not. Currently, DSE assumes that it can’t (as modeled here by the memory poisoning).

Restrict does have some overlap, but I think the semantics are sufficiently different that they should be modeled by different mechanisms.

One big difference is that for allocations, the scope (both spatial and temporal) of applicability is delineated explicitly by the alloc and dealloc operations (modulo the leaked allocation caveat). For restrict, this is instead determined dynamically based on which locations get written. Additionally, restrict applicability is also bound to lexical scopes, while allocations are not.

Another significant difference is that allocators integrate with the concept of “allocated objects” – though I guess one could essentially get that part with a combination of restrict semantics and subobject provenance.

1 Like
5

May have more detailed thoughts during the week, but I think this model does work for explicitly demarcating subobjects in an arena / shared memory / …

6

The user could explicitly insert the call? Probably the compiler can’t do it automatically.

I guess a non-poisoning variant of alloc/dealloc is more straightforward, since you can just dealloc on entry to realloc, then alloc on return.

7

Not sure whether it is helpful from the backend design perspective, but GitHub - microsoft/snmalloc: Message passing based allocator · GitHub does have a built-in provenance model (that works with cheri).

Update: I had a quick scan through the RFC (sorry for the brevity). I think snmalloc’s model is very close to the one in the RFC in most parts, especially in reallocation (deallocate+allocate) and the dealloction (promote ptr to allocator capability).

I think cheri’s leak model is more like transitive revocation (I may understand it wrongly since I don’t work on the cheri part of snmalloc): https://ieeexplore.ieee.org/document/9152640

1 Like
8

The non-allocating forms of operator new and operator new[] plus their corresponding deallocation functions are exempt (or perhaps even prohibited) from this?

I guess they must be given the proposed exclusive ownership nature of leaf allocations.

9

IIUC, this targets “well-behaved” allocators for some definition of “well-behaved”, which I suspect is a higher bar than C++ requires for “allocation functions” outside of the “replaceable global allocation functions”. For other allocation functions in C++, I believe things like “monitoring” of the memory contents (using C++ code within the program) via pointers not derived from the return value of the allocation function is permitted.

The document might be improved if it clarified its expectations of front-end behaviour, perhaps by discussing what Clang might do for C++ using terminology aligned with the C++ standard.

10

Yes, in C++ the allocator model described here only applies to “replaceable global allocation functions” under -fassume-sane-operator-new (which is the default), not other forms of operator new/delete.

It also applies to C allocation functions known to LLVM, such as malloc. Though those are not particularly semantically interesting outside of “LTO including libc” contexts.

The proposal does not directly apply to functions annotated with __attribute__((malloc)), though the parts discussing return-position noalias semantics do. In particular, the discussion on leaked allocations concludes that annotating a bump pointer allocator with __attribute__((malloc)) is not legal. I think this is already implied by our documentation for the attribute. (Interestingly, LLVM itself used to mark its BumpPtrAllocator as such, but then dropped the annotation due to miscompiles. I believe the reason was a different one though, related to SpecificBumpPtrAllocator reading memory on destruction.)

3 Likes
11

One thing I realized while reading the proposal is how naturally the distinction emerges between noalias as a provenance statement and the address identity assumptions (unpredictability, disjointness from allocas/globals), which happens to be true for heap allocators like malloc, but would not hold for the GPU shared memory use case (or suballocations). This is a nice clarification.

Given the BumpPtrAllocator experience, it seems that not annotating bump pointer allocators with noalias may be a reasonable starting point (which, IIUC, is what the proposal hints at). I assume this may be revisited should it cause optimization regressions, though I feel like that avoiding the can_free_via_parent flag would keep the intrinsic design a bit cleaner.

I have been sort of wondering whether noalias could be treated as implicitly scoped, relying on the provenance tree to encode lifetime dependencies (child allocations can be reordered freely among themselves, but not past the parent’s deallocation). I guess this, though, would probably put additional burden on AA, and would possibly require provenance ancestry to be explicitly encoded for opaque allocator functions.

12

We discussed the “leaked allocations” issue at the last formal spec WG meeting, and the consensus was that we should start by not supporting that case (i.e. freeing a parent allocation with live children should be UB), as that is consistent with current LLVM assumptions. We always have the option of extending this in the future, for example using the proposed immarg argument.

13

The semantics make a lot of sense to me, they are pretty much what I expected (except for what happens with memory contents, see below). But I am surprised how they are added to the IR. I did not expect new intrinsics. I expected we’d say that a function with allockind("alloc") is specified to implicitly perform what this RFC calls llvm.provenance.alloc on its return value. That side-effect then gives LLVM license to perform the optimizations that it performs.

To my knowledge, LLVM will assume that the pointer returned from a 4-byte allocation (for any allockind("alloc") function) cannot alias an 8-byte access. How is that assumption justified? I thought the justification would be that we know that the return value has a provenance returned by what you call llvm.provenance.alloc.

So, this is another provenance in the same allocated object? Or is it a new allocated object?

I expected this to say that it’s a new allocated object whose bytes are all uninitialized. That explains why LLVM can assume that the contents of a allockind("alloc") memory is uninitialized. Those bytes are thrown away on free, which explains why stores just before allockind("free") can be removed. And the bytes in the parent allocation all get reset to poison, to make sure that the allocator itself has no way of observing what the user wrote into that memory.

Apparently you have a different idea for where all those assumptions come from, but it’s not clear to me what that idea looks like.

(FWIW, this is what I have in mind for Rust: the return value of the registered global allocator implicitly passes through something like llvm.provenance.alloc, except it produces a genuine new allocation that’s fully uninitialized/zeroed. And the argument to the registered global deallocator implicitly passes through something like llvm.provenance.dealloc, throwing away the allocation that was previously implicitly created together with all its contents.)

1 Like
14

There’s two reasons for the new intrinsics: One is that they can be used by themselves to preserve aliasing properties when merging allocations (see the “standalone usage” section). The other is that allocators can be inlined.

If you half-inline an allocator (e.g. alloc is not inlined, but free is), it would be incorrect to just inline the allocator implementation, without representing the provenance changes.

Consider this dummy allocator, which only supports a single allocation being live at a time (always returns the same pointer).

define noalias ptr @alloc(i64 %size) allocsize(1) allockind("alloc") "alloc-family"="foo" {
  ret ptr @g
}
define void @dealloc(ptr allocptr %p) allockind("dealloc") "alloc-family"="foo" {
  ret void
}

; Usage
%p1 = call noalias ptr @alloc(i64 %size)
call ptr @dealloc(ptr %p1)
%p2 = call noalias ptr @alloc(i64 %size)
call ptr @dealloc(ptr %p2)

Now, if we only inline @dealloc we get:

%p1 = call noalias ptr @alloc(i64 %size)
%p2 = call noalias ptr @alloc(i64 %size)

And now we’re left with two allocations returning the same noalias pointer, without any deallocations in between.

With the intrinsics, we’re still left with a provenance.dealloc after inlining, which pairs with provenance.alloc in @alloc:

%p1 = call noalias ptr @alloc(i64 %size)
call ptr @llvm.provenance.dealloc(ptr %p1)
%p2 = call noalias ptr @alloc(i64 %size)
call ptr @llvm.provenance.dealloc(ptr %p2)

Now, an alternative way to solve this would be to automatically insert these intrinsics only when we actually do the inlining. But I think this would be fragile, because e.g. in the above example the call to @dealloc could be removed not via inlining, but via attribute inference, which sees that the body of the function does nothing. So we’d end up collecting special cases in various IPO transforms that need to know that that functions with allockind have additional implicit operations on entry and exit.

This is why I think it’s better to have frontends explicitly materialize these intrinsics for functions that are annotated with allockind, to automatically give us the right behavior for any inter-procedural optimizations.

Good question. I guess it should say it’s a new allocated object (which overlaps with the masked region of the parent allocated object). Though I’m actually not sure what the practical difference would be. Does an allocated object differ materially from subobject provenance here in how it would affect semantics of following code?

allockind("alloc") does not assume the memory is uninitialized. There is a separate allockind("uninit") property that determines whether this is the case. For example calloc uses allockind("zeroed") instead. For the free case, see the discussion in the “Reallocation” section. We indeed currently assume that, but I think we need to relax it to model reallocation, and make this a separate allockind property as well.

2 Likes
15

“Subobject provenance” should imply that the object can be accessed via pointers not derived from the return value of the (leaf) allocator. I don’t know if you think that makes a “practical difference” in the implementation that you have in mind, but it sounds like a real semantic difference to me.

16

Which is something that, in some cases, we explicitly don’t want to have. Allocators (say, an arena allocator or the like) should be able to return pointers to something that confer “ownership” of the allocated region - nothing will accesses those values except through the pointer returned until deallocation happens.

17

Which is fine. I just don’t think that is “subobject provenance”. It could be named something else.

18

Sorry, using the term subobject provenance was probably confusing in this context. As the proposal is currently written, it’s essentially subobject provenance on the child pointer plus permission masking on the parent pointer. I did not mean to imply that the second part should go away. The question was about what the actual effect of saying that the returned pointer is a new allocated object would be. The main thing that comes to mind is inbounds semantics, though that’s just a question of definition.

(I do think it makes sense to say it’s a new allocated object – after all, it stands to reason that an allocated returns an allocated object. I’m just trying to understand the implications of two possible models here. One just has one top-level allocated object, and “sub-allocations” are handled via provenance. The other has nested, overlapping allocated objects.)

19

Are there differences between pointer comparison semantics (equality or relational) between the two models?

20

I don’t think anything we’re discussing affects address bits. And as LangRef says, “icmp on pointers is equivalent to icmp on the ptrtoaddr of the pointers.”

1 Like