[RFC] Improvements to capture tracking

IR & Optimizations
1

Motivation

In this RFC, I’d like to discuss three improvements we can make to increase the precision of capture tracking. My primary motivation is the first one, but I’d like to bring up the rest as well, so we can amortize the cost of making changes to the nocapture representation in IR.

Distinguishing address capture and provenance escape

Currently, LLVM’s nocapture attribute and the CaptureTracking analysis conflate two concepts:

  • Address capture: This means that information about the identity or bitwise representation of the address may be leaked. For example, because the function converts the pointer to integer, or performs a pointer comparison.
  • Provenance escape: This means that memory accesses may be performed through the escaped pointer after the function returns.

These two concepts are relevant in different scenarios. For example, alias analysis cares exclusively about provenance escapes. Conversely, optimizations replacing one allocation with another may only care about address capture.

In practice, with LLVM IR as it currently is, we usually cannot distinguish between these two concepts. If you have a store ptr %p, ptr @global, then this is both an address capture and a provenance escape, as we can’t track how the pointer will be used after this.

One notable exception are pointer icmps, which constitute address captures, but not provenance escapes. For example, if you have icmp eq ptr %p, %q, then you may not be allowed to access the memory behind %p through %q, despite them having the same address.

Furthermore, I expect that future IR improvements will make the difference more pronounced. In particular, Rust has a ptr.addr() operation, which returns the integral address of the pointer, without exposing its provenance. Ideally, we would represent this as a ptrtoint noescape operation in LLVM IR to enable additional optimization, but this capability currently doesn’t exist, and wouldn’t be particularly useful until we separate the capture/escape concepts.

Distinguishing read-only and read-write provenance escape

The provenance escape case can be further split into two cases: In one, the escaped pointer can only be used in a read-only fashion. In the other, it can be used for reads and writes. This distinction can be quite useful to improve alias analysis results, as many cases only care about potential writes, not reads.

This is a property that we’re unlikely to derive from IR analysis, but that a frontend can provide. For example, if you pass a (non-mut, Freeze) reference to a function in Rust, then the pointer will not only be read-only inside the function, but any escape based on it will also be read-only.

Distinguishing capture via return and other pathways

Finally, it can be useful to distinguish whether a capture can occur only because the pointer is returned, or also for other reasons (like a store into memory). If the capture is only via return, then CaptureTracking can continue recursive analysis on the return value.

The Attributor framework currently represents this using a custom "no-capture-maybe-returned" attribute.

Proposal

I’m somewhat unsure what the best way to solve all of the above problems would be in terms of IR representation, so I’ll build this up in multiple steps. Feedback on what we should actually do here is greatly appreciated!

Distinguishing address capture and provenance escape

This part can be easily addressed by splitting nocapture into two attributes:

  • nocapture: Information about the identity or integral representation of the address may be captured. Makes no statement about the provenance of the pointer.
  • noescape: Provenance of the pointer may escape, and memory accesses may be performed through it after the function returns. Makes no statement about the address identity or representation.

An interesting question here is whether having only nocapture would make sense under the new semantics. This means that there is a potential provenance escape, but no address capture. I don’t think this is something we can infer (any operation that leaks provenance also leaks the address), but it’s plausible that a frontend could provide the information (e.g. if it just never allows inspecting the identity/address of a pointer). As such, I think it’s best to keep both attributes completely orthogonal and allow all combinations of them.

Distinguishing read-only and read-write provenance escape

To support this, I think it would be best to represent captures using a single attribute that specifies everything that may be captured instead:

  • No attribute: Everything may be captured.
  • captures(none) (= nocapture noescape)
  • captures(address) (= noescape)
  • captures(provenance) (= nocapture)
  • captures(address, read-provenance) (A Rust & reference)

An alternative would be to solve this completely independently of the “capturing” property, by changing the semantics of the readonly attribute instead.

It is my understanding that readonly currently only constrains accesses during the function call. That is, if a readonly pointer escapes, then it is legal to perform write accesses through it after the function returns.

We could instead define readonly as a provenance restriction, in which case any access based on the readonly pointer would have to be read-only, even after the function returns.

I think that overall, this may be the cleaner approach, but it does cause an asymmetry between readonly and writeonly. That is, readonly would be defined in terms of provenance, while writeonly would be defined in terms of effects.

Distinguishing capture via return and other pathways

This is the part I’m least certain about. One way to approach this would be to mirror the memory attribute and specify which locations capture which information. For example captures(none, return: address, provenance) would express that both address and provenance are captured, but only via the return value.

To be honest, I think this is somewhat overkill, at least if “return” is the only location we’re interested in separating. This also allows things like captures(address, return: provenance), which is more fine-grained than we can really use.

Possibly this just needs a one-bit modifier along the lines of captures(address, provenance in return).

Questions

From my side, the main two questions I’d like to have some feedback on are:

  • Should the “read-only provenance escape” case be handled as part of the capture representation, or by changing readonly semantics?
  • Do we want to distinguish return-only captures, and if so, what should the syntax be?
13 Likes
2

Thank you for the interesting writeup.

On your questions…

I’d prefer going with the capture semantics over modifying the readonly ones. I see where you’re going with that, but I think the asymmetry you highlight would be confusing, and a source of nasty bugs.

I do think that tracking capture/escape through returns is interesting. As a simple example, imagine a set of routines which construct a moderately complex object DAG. Being able to reliably detect such a subgraph without relying on inlining could be useful. For instance, it would allow a rewrite which replaced calls to malloc or new with calls to (something close to) placement-new working bottom up through the call graph. This would split escape analysis into conceptually two pieces: placement rewriting, and placement selection. The later can also include various object merging strategies.

In general, I support the split you’re proposing. I explored this a few years back, but never quite got it working cleanly enough in my head to propose the IR changes. If it’s helpful, you can find my notes from that exercise here: public-notes/defining-capture.rst at master · preames/public-notes · GitHub and public-notes/defining-escape.rst at master · preames/public-notes · GitHub

One thing I note from my past notes is that I was thinking along the lines of the visibility of object contents instead of providence. I think those two are conceptually interchangeable, but not entirely sure.

3

This is technically not true; for example, you can ptrmask away all the bits of an address. But realistically, it’s not going to come up.

I’m a little concerned about making provenance reasoning more complicated when we still haven’t implemented a self-consistent definition for how the provenance is computed for inttoptr/load/store/etc. instructions. But maybe doing this would help us clarify the model without losing optimizations. Not sure.

I don’t think we want to redefine the existing readonly. We might eventually decide we don’t need readonly on arguments, but trying to get rid of readonly at the same time as implementing this proposal seems like a lot of complexity for little benefit.

What exactly are the relevant Rust semantics here?

Say you have some raw memory allocated by malloc, and you pass a reference to it into a function. The function stashes away the pointer bits in an integer somewhere. Then, after the lifetime of the reference ends, some later function casts those bits to a pointer, and writes to the memory. All of these steps are fine, as far as I can tell? Or is the last step illegal unless the pointer’s provenance is explicitly escaped somewhere? Does it matter if you get the memory by some way other than malloc?

1 Like
4

I don’t think that this proposal materially intersects with the open questions around our provenance model. As long as we treat ptrtoint (without the hypothetical noescape flag) and store into memory as both capture and escape, that’s conservatively correct independently of what the precise rules are.

I don’t think we want to remove readonly from arguments – the property it encodes is certainly useful by itself. It just doesn’t encode everything we’d like, for some use cases.

I assume that by “Rust semantics” you are referring to the bit about ptr.addr(), not the bit about read-only references.

The way this works is that Rust has two provenance models (in the process of being stabilized). One is strict provenance, where p.addr() gives you the address without exposing the pointer provenance, and you have use something like p.with_addr(addr) to recombine the address addr with the provenance of p before you can access through it.

The other is exposed provenance, where p.expose_provenance() gives you the address and exposes the pointer provenance, and then ptr::with_exposed_provenance(addr) can create a pointer from the address with the provenance determined in some magic, as-yet unspecified way.

Using the terminology from this RFC, ptr.addr() only captures the address, while ptr.expose_provenance() both captures the address and escapes the provenance.

So for your example with malloc, the answer depends on whether the “stashes away the pointers bits in an integer somewhere” happened via addr() or expose_provenance(). In the former case, the later access would indeed be UB.

Part of the long-term goal here is to get better optimization support for the “strict provenance” model, which completely sidesteps all the open questions of LLVM’s own provenance model, and does not require LLVM to make very conservative assumptions for pointer to int casts.

5

Why are nocapture and noescape bundled together in captures()? Can we keep them separate with nocapture and escapes(no|returnonly|yes)?

6

If I’m reading this correctly, for GC escape analysis only provenance escape would be relevant. Is that correct?
So for example, a ptrtoint would not let the pointer escape. Nor would icmp with another pointer.

If so, this would be very useful. Right now I’m relying on nocapture for a heap-to-stack transformation pass but in many cases it’s more conservative than I would like it to be (for example, ptrtoint and icmp typically do not let a pointer escape while right now they do capture the pointer with current nocapture semantics).

Also, if I’m understanding this correctly, captures(read-provenance) would allow the object to be converted to a global constant object: it is only read from and no code inspects the address itself (which also becomes constant when converting to a global object).

7

More fine-grained capture semantics in the IR are long overdue. Thanks for driving this!

Wrt. the questions:

  • I would not touch readonly, as said before, asymmetrical semantics will cause more issues in the future. If anything, add readonly, or some spelling thereof, to the captures attribute. It’s even more fine-grained since it means only the captured pointer is read only, not the entire pointer. I’ll get back to this scenario in a sec.
  • I very much think return-only captures are worth handling. I like the memory like representation, especially because I don’t think return has to be the only thing we are tracking in the future. Even if we assume it is, the encoding is consistent with memory and to me it makes sense to use the same scheme again.

One thing that came up above a few times are annotations on instructions.
I believe this will make those really important, especially to encode frontend/language knowledge:

int a = 2, b = 3;
struct S s = {&a, 42, &b};
s->a = 42;
library_that_only_reads_a_and_b(s); // the "capture" of a here is readonly even if a is written in the function scope.
builtin_that_does_not_remember_addr_of_a_and_b(s);
1 Like
8

Thanks for this writeup - I agree that separating address and provenance capture would be very nice.

In the CHERI LLVM downstream, we have the property that a ptrtoint from CHERI capabilities (represented as ptr addrspace(200)) always strips the “provenance” capability metadata and only returns the address part, so any such cast would be a ptrtoint noescape. Performing an inttoptr to addrspace 200 gives a pointer with invalid provenance, so the only way to get back to a valid pointer is by using the ptrtoint result with a gep or the downstream @llvm.cheri.address.set(ptr, addr) intrinsic.

I like the proposed captures(...) syntax and I believe having the provenance vs address capture be distinct in LLVM IR would be very nice for the Rust strict provenance model and could most likely also benefit code generation for CHERI-enabled architectures.