Borrowing Rules, Aliasing Invariants & LLVM Optimization

Passing data by ownership is safe, but transferring ownership repeatedly through functions is inefficient and unwieldy. Rust solves this through borrowing: creating references that grant temporary read or write access to data without transferring ownership.

To maintain memory safety and eliminate data races, borrowing is governed by the XOR Aliasing Invariant.

1. The Fundamental XOR Aliasing Invariant#

The borrowing model can be stated as an exclusive mathematical rule:

> At any given point in program execution, you may have either any number of immutable references (&T), or exactly one mutable reference (&mut T), but never both.

Let $R(x)$ be the set of active immutable references pointing to resource $x$, and let $W(x)$ be the set of active mutable references pointing to $x$. The Aliasing Safety Invariant mandates:

Expressed as a constraint equation, the product of active reader count and writer count must always equal zero:

2. Preventing Iterator Invalidation#

In languages like C++ or Python, modifying a collection while iterating over it causes undefined behavior or runtime exceptions (iterator invalidation). In Rust, iterator invalidation is impossible because it violates the XOR aliasing invariant at compile time:

1
2
3
4
5
6
7
8
9
10
11
12
13
fn main() {
    let mut numbers = vec![1, 2, 3, 4, 5];

    for item in &numbers {
        // 'item' is an active immutable borrow (&i32) into 'numbers'!
        if *item == 3 {
            // Attempting to mutate 'numbers' requires &mut numbers:
            // numbers.push(100); 
            // COMPILE ERROR: cannot borrow `numbers` as mutable 
            // because it is also borrowed as immutable
        }
    }
}

3. Reference Reborrowing#

When you pass a mutable reference to another function or assign it to a new binding, Rust does not move the reference; it creates a reborrow:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
fn modify(val: &mut i32) {
    *val += 10;
}

fn main() {
    let mut data = 50;
    let r = &mut data;

    // REBORROW: A temporary &mut borrow is created from 'r'.
    // While 'modify' runs, the original binding 'r' is suspended.
    modify(r);

    // Once the reborrow ends, 'r' becomes active again!
    *r += 5;
    println!("Final value: {}", data); // 65
}

4. Hardware Optimization: The LLVM noalias Advantage#

Beyond memory safety, exclusive borrowing unlocks tremendous hardware-level performance.

In C and C++, two raw pointers int* a and int* b passed to a function might point to overlapping memory regions (pointer aliasing). Because of this possibility, the compiler must emit instructions that reload values from RAM repeatedly after every write.

In Rust, a mutable reference &mut T is guaranteed to have exclusive access. rustc emits the LLVM noalias parameter attribute:

5. Concept Verification#

Test your understanding of borrowing rules and alias optimization: