Marking SSA values as pointing to immutable memory

IR & Optimizations
1

Hi everyone,

As part of my project to improve code generation in Rust, I’m interested in how best to tell LLVM that the memory a particular SSA pointer value is pointing to, along with the memory all pointers based on that pointer are pointing to, is strongly immutable. We have a few ways to do this in LLVM IR already, and none of them seem quite optimal:

  1. readonly noalias parameter attributes — This is perfect for function parameters, and I’m adding optimizations to LLVM that use this right now, but there are two major cases it misses: (a) in Rust, any references contained within an object that there is itself an immutable reference to are guaranteed to point to immutable memory; (b) functions can return immutable references. It’d be nice if we had some way to express these extra guarantees in LLVM IR so that alias analysis can use them.

  2. llvm.invariant.start and llvm.invariant.end pairs — Originally, I had a pull request to use these, but it was pointed out to me a few times that using them in alias analysis isn’t really feasible from a compile time point of view, as slow graph algorithms like Floyd-Warshall (O(n^3) [!!]) are needed to answer queries like “is this pointer pointing to immutable memory at this instruction”, like alias analysis wants. As a result they don’t seem feasible for use in this case.

  3. llvm.launder.invariant.group — This is closer to what I need, but the problem is that if I have %q = llvm.launder.invariant.group(ptr %p); %r = llvm.launder.invariant.group(ptr %q), %r and %q are treated as in different invariant groups, so loads from %q won’t be forwarded to %r. Instead of the semantics of llvm.launder.invariant.group, I’d want something like an llvm.guarantee.invariant intrinsic such that llvm.guarantee.invariant(llvm.guarantee.invariant(%p)) is equivalent to llvm.guarantee.invariant(%p).

  4. Scoped noalias metadata—This would require quite a bit of (flow-sensitive!) data tracking in the frontend to keep track of all the alias sets at every program point, and it generally seems overkill for simply guaranteeing the invariance of memory.

My current thinking is that perhaps some !invariant metadata attached to the load or call instruction that manufactures the pointer might be optimal, because that would be fairly lightweight, would follow the !tbaa pattern that we already have, and would obey the rule that metadata can be safely dropped without changing the program semantics. An alternative would be to introduce an ptr2 = llvm.guarantee.invariant(ptr, size) intrinsic. This seems a bit heavier-weight, and I’d have to make sure all optimizations can see through that intrinsic appropriately, but perhaps it’s the best option. I’m curious what others’ thoughts may be.

Thanks!

1 Like
2

Out of curiosity, who/what uses llvm.launder.invariant.group? According to LangRef, it only makes sense in the context of also using !invariant.group metadata; it’s also identical to llvm.strip.invariant.group? This seems a pretty underspecified corner of LangRef.

There’s !invariant.load which we rely on in LLPC for similar purposes, but it may actually be too strong for what Rust needs.

I would like to understand better what you mean by “strongly immutable”, and for what kind of code you’re seeking better code generation. Do you have a toy example?

3

Hint: ⚙ D47103 Implement strip.invariant.group

Devirtualization.

4

We are relying on invariant start intrinsic to mark locations that become invariant after initialization in our downstream frontend (Azul’s Falcon JIT compiler for Java).

Invariant starts are supported in EarlyCSE and LICM at the moment. Handling this intrinsic doesn’t have to be an O^3 ordeal. If you do a forward propagation like EarlyCSE, it’s just a linear scan through the IR.

5

Well, the problem is that in Rust it’s frequently the case that we know memory is temporally invariant, but it will become mutable later. For example, when you pass a value by immutable reference to a function, for the most part any heap objects that that value points to are also known to be immutable. However, after the function returns that memory might be mutable again. So we can’t just mark such pointers with llvm.invariant.start—we’d have to include the llvm.invariant.end markers and that would cause the annoying problems with control flow again when functions get inlined. AFAICT the query we need is something like “is this instruction dominated by an llvm.invariant.start and is it impossible for any BB with llvm.invariant.end in it to reach the instruction without going through the llvm.invariant.start”, which I don’t see a fast way to calculate.

Really, I think what we want is a way to say that “all memory addresses based on this particular pointer value (in the LLVM Value sense) will always load the same value”, instead of “this memory is known to be immutable”.

6

I believe in Rust it is not limited to function boundaries, but couldn’t you pass in fat pointers.

llvm.fat.pointer(ptr, size, access_mode)

enum AccessMode {
  ReadOnly,
  WriteOnly,
  ReadWrite
}

On second thought, you are more interested in ranges of the heap:

llvm.heap.range(start, end, access_mode)

I believe this is closer to you challenge:

[[readonly::propagate]] void *ref;

fn foo() {
    let list = LinkedList::from([1, 2, 3]);
    bar(&list);
}

fn bar(ll: &LinkedList<i32>) {
    // propagate readonly on ll
}
7

What kind of optimizations do you want to implement?

I believe that your example of adding readonly metadata to loads does not sound too bad.

bar(&list, &list);

fn bar(l1: &LinkedList<i32>, l2: &LinkedList<i32>) {
    // propagate readonly on all loads of l1 and l2
}
8

I found this diff: ⚙ D134410 [clang][CodeGen] Add noundef metadata to load instructions (preliminary 1 or 2).

9

Have you considered just exposing an abstracted picture of Rust’s knowledge for a “range-based alias-analysis” analogous to type-based alias analysis?

Roughly speaking, what I mean is adding !rbaa metadata to loads, stores, and function calls which contain two pieces of information:

  1. The abstracted “location” of the instruction (but think of it more as the interval during which nothing relevant happens to the set of accessible memory references)
  2. The underlying reference(s) of the load/store pointer / function call pointer arguments. A reference is characterized by some form of unique ID combined with a range (= set of locations) of validity.

The rule is: if memory access A’s location is in memory access B’s range, and they have different underlying references, then the accesses do not alias.

The main algorithmic challenge is how to represent ranges efficiently and how to efficiently do a “range contains location?” query. (It seems likely that the graph of ranges and their overlaps is chordal or near-chordal; perhaps that helps.)

10

Could the full restrict infrastructure be of help ? (⚙ D68484 [PATCH 01/27] [noalias] LangRef: noalias intrinsics and ptr_provenance documentation.)