Could we have Rust without provenance?

[RalfJung]

Every time I make provenance-based arguments, some people dispute that the need for provenance exists in the first place. I disagree with them, and I am not alone in this, but it is a very reasonable objection nevertheless.

I will not be able to fairly represent the arguments of the no-provenance fraction, so I hope @digama0 will reply here summarizing the key arguments and explaining how alias analysis can reasonably be done in a compiler without provenance -- or, alternatively, how a "Rust without provenance" could be compiled to a backend like LLVM that demonstrably does have provenance as support for its alias analysis.

[digama0]

To begin with, the model I proposed in the linked thread is not about eliminating all provenance. It is about treating the *mut T type as equivalent to usize, as a provenance free integer, while treating &mut T and &T and &Cell<T> and Box<T> as references with stacked borrows style provenance.

The lowering of all the operations into LLVM is fairly easy to guess from this description:

• (x: &mut T) as *mut T is ptrtoint(x)
• *(x: *mut T) is *inttoptr(x)
• (x: *mut T) as usize is x
• (x: usize) as *mut T is x

An alternative lowering maps *mut T to LLVM pointers, but in this case one has to be careful to erase provenance of all pointers on entry to a function and when reading new values (roughly in the same places as the SB retag operation). The calling convention for rust functions would ensure that one only passes LLVM-provenance-free pointers to a function, so adding an additional erase_provenance(x) on all pointers x: *T coming into an LLVM function is valid.

The main issue with this proposal is that it prevents most alias analysis on such pointers. Here is an example:

fn foo() {
  let mut x = 0;
  let mut y = 0;
  let x_ptr = &mut x as *mut u8;
  let y_ptr = &mut y as *mut u8;
  *y_ptr = 1;
  *x_ptr = 2;
  println!("{}", *y); // rewrite `*y` to 1? Yes!
}

It isn't possible to perform alias analysis directly here based on the separateness of the allocations to deduce that the write to x doesn't invalidate y, but the information is local enough that we can still figure out what the write will hit. If we offset the pointer by a compiler-unknown amount, alias analysis is defeated:

fn foo(n: usize) {
  let mut x = 0;
  let mut y = 0;
  let x_ptr = (&mut x as *mut u8).wrapping_add(n);
  let y_ptr = &mut y as *mut u8;
  *y_ptr = 1;
  *x_ptr = 2;
  println!("{}", *y); // rewrite `*y` to 1? No!
}

Here, LLVM style provenance would permit the rewrite, but when pointers are just integers, it is possible for n to translate x_ptr to equal y_ptr in which case the two pointers are aliasing.

I contend that this problem is far less disruptive for Rust than it would be in C/C++. Rust already has a much better alias analysis, in the form of references and stacked borrows semantics, so pointers are usually used in low level code in small functions that don't directly benefit much from such optimizations. However, issues start to crop up when these functions are inlined, and I think the main question will hinge on the performance of commonly used functions like IndexMut for Vec that could add raw pointer operations into idiomatic Rust code.

[digama0]

I think the main question will hinge on the performance of commonly used functions like IndexMut for Vec that could add raw pointer operations into idiomatic Rust code.

Actually IndexMut for Vec isn't a problem, because it can be done entirely with references: &mut Vec<T> -> &mut [T] -> &mut T -> write, so we actually know that the write is inbounds of the relevant allocation. That means that in let mut x = vec![0]; let y = vec![0]; x[i] = 1; use(y[0]) we can still optimize y[0] to 0 even though we have an indirect write, because that write first had to get mutable access to the value, which is prevented by y's ownership of its data.

[thomcc]

I think this would cause performance problems for iterators, like slice::Iter, and various data structures.

But I also think we could provide an opt-in type could be provided for such cases — something like Unique (probably something distinct from Unique though) that behaves like a pointer type with the "current" provenance semantics in order to get more optimizations.

In general, I am heavily in favor of this investigation. The current semantics lead to a sort of "spooky action at a distance" that I thought I had left behind when switching to a computer science major years ago at university (😉). It's very hard to reason about in practice, and a staggering amount of unsafe code in the wild gets it wrong. (That code is likely only saved by the fact that we don't do anything too aggressively inter-procedural)

[Diggsey]

It would definitely be interesting to experiment with a model where alias and/or provenance information can be explicitly provided by the programmer for raw pointers via some kind of attribute.

Given that raw pointers are very rarely used in Rust, it could make more sense to go this route rather than having complicated and confusing provenance rules.

One could even imagine re-defining references to be equivalent to pointers with a particularly restrictive combination of those attributes applied.

[RalfJung]

To begin with, the model I proposed in the linked thread is not about eliminating all provenance. It is about treating the *mut T type as equivalent to usize, as a provenance free integer, while treating &mut T and &T and &Cell and Box as references with stacked borrows style provenance.

Okay. (I thought you had proposed multiple different models, but I am okay with focusing on that one for now.)

But I don't think this solves #286; now we just have that same problem with reference-to-int (and even reference-to-ptr) transmutes. As long as there is provenance anywhere in the logic, this problem will arise.

(When I said "pointer" in #286, I meant all types carrying pointer values -- references, raw pointers, function pointers. I should have been more clear about this.)

[RalfJung]

Regarding the proposal itself, I am skeptical because one reason people reach to unsafe code is performance -- so if the pointer model we give them there is even less optimizable than what C does, that will be a problem. For example, the only reason wrapping_offset even exists is that enough people thought it is really important to preserve provenance.

If we have two kinds of raw pointers (one with and one without provenance), then we get plenty of subtle issues when converting between the two -- in fact, those will be exactly the same issues that we currently have when converting between pointers and integers. So in a sense we can already have a "raw pointer without provenance" as a user-defined type:

struct PtrWithoutProvenance<T>(usize, PhantomData<*mut T>);

I don't quite see how turning this into a primitive type would make the language easier to learn.

In general, I am heavily in favor of this investigation. The current semantics lead to a sort of "spooky action at a distance" that I thought I had left behind when switching to a computer science major years ago at university (wink).

I am not sure what you are referring to by "action at a distance" here. The underlying problem is that many people have a fundamentally wrong model of what pointers look like. Naturally, when you come in with an incorrect mental model, the behavior of the "real thing" will look spooky and non-sensical.

The "only" thing people need to accept and learn when using raw pointers is that each pointer is tied to a particular allocated object. A pointer consists of some address it points to, plus some unique ID identifying the object it is associated with. Whenever a pointer is used, if the addresses it accesses are outside of the object identified by that ID, we have UB. I don't think this is complicated, and there is nothing going on "at a distance" here. The problem is not that these rules are complicated, the problem is that people don't expect any such rules, because there is a lot of false information and bad teaching material out there that makes people believe pointers in C or Rust work the same as addresses in assembly.

[thomcc]

But I don't think this solves #286; now we just have that same problem with reference-to-int (and even reference-to-ptr) transmutes. As long as there is provenance anywhere in the logic, this problem will arise.

Yeah, I suspected this was the case in general, and was in the middle of writing this last night before I went to bed. I didn't post it because I had wanted to look at it with clear eyes, but I think it's mostly still relevant, although part is not (or at least, it's confirmed), and so you should be aware of that going in.

---

(Begin post written before most recent replies)

That said, would pointers not having provenance fix the "spooky action at a distance" issue that I'm alluding to? I think the answer is no, although perhaps it would reduce the severity of it.

Like, I could be wrong (I have a track record of being... very wrong about this stuff, let's say) but I think this does very little if anything to fix the most common issues I've seen, which is where some reference is created (either accidentally, because of ergonomics, etc) and it invalidates the provenance of a pointer.

I think the only way to fix that issue is reducing the provenance of references. I'm fairly confident we don't want that, or at least it's not being proposed here...

That said, I guess I do think it's worth seeing the performance impact of a "Rust without provenance" would be. I'm guessing all the talk of it being unoptimizable means we expect it to be worse than "C++ with -fno-strict-aliasing"? Is there alias analysis that C/C++ compilers will do that's not the TBAA sort? Sorry, every compiler I've worked on was very heavily in the "very much a DSL" camp, and even then it was quite a long time ago.

If C++-sans-TBAA is the same: in practice... honestly strict aliasing doesn't help much at all — It helps some, but they're both still pretty fast without it. When I wrote more C++, I usually would turn it off, just because I don't want to worry about UB in a library accidentally biting me, and because I won't miss the ~5% speed hit (this is about what I've seen on average, and if you google around that's in the same ballpark as others seem to have seen also, so seems plausible).

That said, even a 5% speed is a tough pill to swallow across all code... Especially since some code is will get hit much harder, and this comes with the threat of making it harder to optimize things in the future... Realistically, for Rust it's probably higher than 5% too no? — I think we generally believe that Rust's alias analysis is much more helpful than C++'s especially where being able to remove redundant loads from inner loops are concerned, which could have a big impact...

OTOH it's just 5% though, it might not be worth it when you compare to the sorts of algorithmic-ish optimizations that libraries would be able to perform without those restrictions. Increased flexibility there would be very helpful, and could easily make up a perf difference like that.

Anyway all of that is just speculating, but without more details its hard for someone like me to try this out. Is removing noalias from the llvm that Rustc genreates enough? Do we need to remove dereferencable too? Or do LLVMs pointers already imply some amount of provenance, and to avoid that, we need to move everything to integers.

(End post written before most recent replies)

---

So yeah, after some though:

1. I think we should be pretty clear about what code we want to enable when proposing something like this. (Doing so will be critical to "sell it" more broadly, especially if it comes with any kind of performance hit)

   This is especially true for the half-measures like "removing pointer prov. but keeping it for refs", which seemed more promising until I thought about it, and now seem even less useful that Ralf has chimed in.

2. Does anybody know if Rust without prov. would be equivalent in terms of optimizability to, say, C/C++ with -fno-strict-aliasing? I'm assuming there's more to it.

   If there's not, I think it's pretty misleading to say something like "it is not possible to write a reasonably optimizing compiler for a model where pointers have no provenance" — in practice that drastically overstates how much those optimizations help at all. IIRC, MSVC didn't even start doing them at all until a year or two ago.

   That's not to say we can definitely give it up, but just that it's not so far-gone that it should be thrown out from the start.

3. If we wanted to try this, what's needed?

   • Disabling noalias (for both &T and &mut T) (this is easy)
   • Do we need to remove dereferencable too? (this is also easy, I think, but it seems like it wouldnt be needed)
     • Is there anything else? Presumably align and nonnull can stay?
   • Do we need to go all the way to casting every pointer to int and back? It was kind of implied earlier but I'm not sure it was. I'm guessing if it's needed, it's to avoid some "latent" provenance already present in LLVM-IR pointers?
     • If that's the case, is this even enough? Isn't part of the problem in What about: Pointer-to-integer transmutes? #286 caused by the fact that LLVM optimizations could "see through" ptrtoint and inttoptr? Or am I misunderstanding.

---

One final note I have to say something about though:

Regarding the proposal itself, I am skeptical because one reason people reach to unsafe code is performance -- so if the pointer model we give them there is even less optimizable than what C does, that will be a problem

This is sort of not right. I do often reach for unsafe for performance, but the performance I get is usually not from compiler optimizations, it's various sorts of algorithmic ones. Let's stretch a bit and call "explicit vectorization" or other stuff of that ilk an algorithmic optimization, but it often is a real algorithmic change too — often in the form of a smarter data structure, or more clever synchronization, and that sort of thing.

In general, I reach for it when the optimizer has already failed me, and I'm taking matters into my own hands. For sure, there are cases where I do a thing with unsafe, it's to help the optimizer out, but I don't think this is really the common case at all. I can't speak for other authors of unsafe rust, but I think this is pretty typical.

This is largely because the sorts of speed-ups you can get from doing something in a smarter way... They're real, easy to measure, easy to iterate on, and almost always much larger than almost anything a smarter compiler will give you. (Well, unless you're saying something like "this will turn your code into -O0 code" which I have a... hard time believing).

[chorman0773]

I'm guessing all the talk of it being unoptimizable means we expect it to be worse than "C++ with -fno-strict-aliasing"? Is there alias analysis that C/C++ compilers will do that's not the TBAA sort?

Yes, same kinds of things rust can do on raw pointers: ie. can this x pointer access/modify y object.
A simple example is (C++ Code, though same applies for C):

void bar(int* i);
int foo(){
     int x;
     int y;
     int* px = &x;
     int* py = &y;
     *px = 5;
     bar(py);
     return x; 
}

That can be transformed to

int foo(){
     int y;
     bar(&y);
     return 5;
}

because of provenance, and local alias analysis. IMO, provenance is a source of local reasoning about foreign code. Without provenance, one could argue it's valid for the py passed to bar to access px, thus rendering the assignment ellision invalid, because bar may access x and thus, because the compiler cannot inspect bar, must assume it does so.

Likewise, any time you have a translation unit boundery in a rust program, provenance becomes necessary to ensure the scope of accesses. In rustc currently, translation unit bounderies are crates. In lccc, the intention is to convert each source file into a translation unit, to improve parallelization (though this can be disabled).

[Diggsey]

@chorman0773 in your example, it seems like you can achieve the same optimization using escape-analysis alone.

While bar could materialize any random address and write to it, the compiler can see that the address of neither x nor px escapes from the function, so bar has no way of knowing for sure that it's writing to x.

[chorman0773]

While bar could materialize any random address and write to it, the compiler can see that the address of neither x nor px escapes from the function, so bar has no way of knowing for sure that it's writing to x.

I'd argue that escape-analysis is a form of provenance. The same applies if there is a deterministic way to reach x's address from y, but not the actual object (for example, if they are adjacent fields with the same access modifier in a non-standard layout structure).

[RalfJung]

@thomcc

That said, I guess I do think it's worth seeing the performance impact of a "Rust without provenance" would be. I'm guessing all the talk of it being unoptimizable means we expect it to be worse than "C++ with -fno-strict-aliasing"?

This is an interesting question. Performance would probably be the same as "C/C++ without provenance", which very different from "C/C++ with no-strict-aliasing". I don't think the experiment of building such a compiler has been done. Such a compiler would essentially have to treat every local that ever has its address taken as escaped, even if that address is not given away, since someone else might "guess" the right address. (You can sometimes argue that guessing is impossible, but that is non-trivial. This is the argument @Diggsey also makes.)

You seem to think provenance in C/C++ is only about TBAA. That is not so, even C/C++ sans TBAA have provenance. It is reflected in the standard where it says that doing pointer arithmetic on a pointer cannot be used to create a pointer that points to a different allocated object. In C/C++/Rust without provenance, we would have to account for the fact that any kind of pointer arithmetic can compute pointers to any allocated object. So, basically, once you did ptr.offset(foo), now ptr potentially aliases anything, even local variables of the current function.

If we wanted to try this, what's needed?

We'd need a compiler that does not exploit provenance in its alias analysis. I do not know of such a compiler even for C/C++.

@Diggsey
Compilers currently assume that if ptr1 and ptr2 point to different allocated objects, then ptr1.offset will also never point to the allocated object of ptr2. That assumption is simply wrong if you remove provenance from the Abstract Machine. ptr1.offset(ptr2.offset_from(ptr1)) will alias ptr2. Put differently, the escape analysis made by typical compilers has to be made weaker (consider more things as "escaped") to be correct in a provenance-free world.

I would love to see the experiment of building such a compiler actually being made! This discussion is frustratingly void of good data. We have plenty of theorems and counterexamples showing what is correct and what is not correct, but we lack good indications for what the performance trade-offs are in this landscape of possible Abstract Machines. The only datum we can really go off of is that pretty much all compilers have an escape analysis that is correct only in the presence of explicit provenance in the Abstract Machine, so clearly these compiler authors thought they need that stronger analysis.

Of course, provenance in Rust goes way further than that -- all the Stacked Borrows optimizations would of course also be lost in a totally provenance-free world.

@chorman0773

I'd argue that escape-analysis is a form of provenance.

This mixes up operational semantics and static analysis.
The operational semantics is the "source of truth", it defines what the program might do when being executed. A static analysis is an approximation that the compiler computes of these possible program behaviors; it is justified against the operational semantics. A static analysis can, in principle, be proven correct; an operational semantics cannot be proven correct since it defines what "correct" even means when talking about program executions.

So, if the operational semantics (the Abstract Machine) does not have provenance, a static analysis cannot magically "add" it.
That said, of course the notion of a "data/control dependency" can be defined in any operational semantics, and can be useful for analysis, so maybe that's what you mean here. However, it is important to separate "explicit" provenance that exists in the Abstract Machine of the language "by fiat", from "implicit"/"analysis-only" notions that are defined by static analysis and can be proven correct against the operational semantics of the Abstract Machine.

To give a concrete example: if the abstract machine does not have provenance, then no amount of escape analysis can recover the Stacked Borrows optimizations.

[bjorn3]

I would love to see the experiment of building such a compiler actually being made!

cg_clif is currently such a compiler. Cranelift itself doesn't have any provenance. It doesn't have much optimizations either, so it is much slower than what a compiler without provenance could theoretically be though.

[RalfJung]

Cranelift will be [even more] interesting to watch for its future development then. :)
(Also I have a nagging worry here that people used to work in compilers with provenance -- so, presumably the vast majority of compiler engineers -- will introduce provenance-exploiting optimizations to cranelift without even realizing...)