Tree Borrows

> On the one hand, compilers would like to exploit the strong guarantees of the type system—particularly those pertaining to aliasing of pointers—in order to unlock powerful intraprocedural optimizations.

How true is this really?

Torvalds has argued for a long time that strict aliasing rules in C are more trouble than they're worth, I find his arguments compelling. Here's one of many examples: https://lore.kernel.org/all/CAHk-=wgq1DvgNVoodk7JKc6BuU1m9Un... (the entire thread worth reading if you find this sort of thing interesting)

Is Rust somehow fundamentally different? Based on limited experience, it seems not (at least, when unsafe is involved...).

While I can't name the product I work on, we also use -fno-strict-aliasing. The problem with these optimisations is that they can only be done safely if you can prove aliasing never happens, which is equivalent to solving the halting problem in C++. In Rust I suspect the stronger type system can actually prove that aliasing doesn't happen in select cases. In any case, I can always manually do the optimisations enabled by strict aliasing in hot code, but I can never undo a customer losing data due to miscompilation.

> actually prove that aliasing doesn't happen in select cases

In the safe subset of Rust it's guaranteed in all cases. Even across libraries. Even in multi-threaded code.

To elaborate on that some more, safe Rust can guarantee that mutable aliasing never happens, without solving the halting program, because it forbids some programs that could've been considered legal. Here's an example of a function that's allowed:

    fn foo() {
        let mut x = 42;
        let mut mutable_references = Vec::new();
        let test: bool = rand::random();
        if test {
            mutable_references.push(&mut x);
        } else {
            mutable_references.push(&mut x);
        }
    }

Because only one if/else branch is ever allowed to execute, the compiler can see "lexically" that only one mutable reference to `x` is created, and `foo` compiles. But this other function that's "obviously" equivalent doesn't compile:

    fn bar() {
        let mut x = 42;
        let mut mutable_references = Vec::new();
        let test: bool = rand::random();
        if test {
            mutable_references.push(&mut x);
        }
        if !test {
            mutable_references.push(&mut x); // error: cannot borrow `x` as mutable more than once at a time
        }
    }

The Rust compiler doesn't do the analysis necessary to see that only one of those branches can execute, so it conservatively assumes that both of them can, and it refuses to compile `bar`. To do things like `bar`, you have to either refactor them to look more like `foo`, or else you have to use `unsafe` code.