Why does the Rust compiler not optimize code assuming that two mutable references cannot alias?

As far as I know, reference/pointer aliasing can hinder the compiler's ability to generate optimized code, since they must ensure the generated binary behaves correctly in the case where the two references/pointers indeed alias. For instance, in the following C code,

void adds(int  *a, int *b) {
    *a += *b;
    *a += *b;
}

when compiled by clang version 6.0.0-1ubuntu2 (tags/RELEASE_600/final) with the -O3 flag, it emits

0000000000000000 <adds>:
   0:    8b 07                    mov    (%rdi),%eax
   2:    03 06                    add    (%rsi),%eax
   4:    89 07                    mov    %eax,(%rdi)  # The first time
   6:    03 06                    add    (%rsi),%eax
   8:    89 07                    mov    %eax,(%rdi)  # The second time
   a:    c3                       retq

Here the code stores back to (%rdi) twice in case int *a and int *b alias.

When we explicitly tell the compiler that these two pointers cannot alias with the restrict keyword:

void adds(int * restrict a, int * restrict b) {
    *a += *b;
    *a += *b;
}

Then Clang will emit a more optimized version of the binary code:

0000000000000000 <adds>:
   0:    8b 06                    mov    (%rsi),%eax
   2:    01 c0                    add    %eax,%eax
   4:    01 07                    add    %eax,(%rdi)
   6:    c3                       retq

Since Rust makes sure (except in unsafe code) that two mutable references cannot alias, I would think that the compiler should be able to emit the more optimized version of the code.

When I test with the code below and compile it with rustc 1.35.0 with -C opt-level=3 --emit obj,

#![crate_type = "staticlib"]
#[no_mangle]
fn adds(a: &mut i32, b: &mut i32) {
    *a += *b;
    *a += *b;
}

it generates:

0000000000000000 <adds>:
   0:    8b 07                    mov    (%rdi),%eax
   2:    03 06                    add    (%rsi),%eax
   4:    89 07                    mov    %eax,(%rdi)
   6:    03 06                    add    (%rsi),%eax
   8:    89 07                    mov    %eax,(%rdi)
   a:    c3                       retq

This does not take advantage of the guarantee that a and b cannot alias.

Is this because the current Rust compiler is still in development and has not yet incorporated alias analysis to do the optimization?

Is this because there is still a chance that a and b could alias, even in safe Rust?

Solution 1:

Rust originally did enable LLVM's noalias attribute, but this caused miscompiled code. When all supported LLVM versions no longer miscompile the code, it will be re-enabled.

If you add -Zmutable-noalias=yes to the compiler options, you get the expected assembly:

adds:
        mov     eax, dword ptr [rsi]
        add     eax, eax
        add     dword ptr [rdi], eax
        ret

Simply put, Rust put the equivalent of C's restrict keyword everywhere, far more prevalent than any usual C program. This exercised corner cases of LLVM more than it was able to handle correctly. It turns out that C and C++ programmers simply don't use restrict as frequently as &mut is used in Rust.

This has happened multiple times.

• Rust 1.0 through 1.7 — noalias enabled
• Rust 1.8 through 1.27 — noalias disabled
• Rust 1.28 through 1.29 — noalias enabled
• Rust 1.30 through 1.54 — noalias disabled
• Rust 1.54 through ??? — noalias conditionally enabled depending on the version of LLVM the compiler uses

Related Rust issues

• Current case

  • Incorrect code generation for nalgebra's Matrix::swap_rows() #54462
  • Re-enable noalias annotations by default once LLVM no longer miscompiles them #54878
  • Enable mutable noalias for LLVM >= 12 #82834
  • Regression: Miscompilation due to bug in "mutable noalias" logic #84958

• Previous case

  • Workaround LLVM optimizer bug by not marking &mut pointers as noalias #31545
  • Mark &mut pointers as noalias once LLVM no longer miscompiles them #31681

• Other

  • make use of LLVM's scoped noalias metadata #16515
  • Missed optimization: references from pointers aren't treated as noalias #38941
  • noalias is not enough #53105
  • mutable noalias: re-enable permanently, only for panic=abort, or stabilize flag? #45029