406

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  # load a into EAX
   2:    03 06                    add    (%rsi),%eax  # load-and-add b
   4:    89 07                    mov    %eax,(%rdi)  # store into a
   6:    03 06                    add    (%rsi),%eax  # load-and-add b again
   8:    89 07                    mov    %eax,(%rdi)  # store into a again
   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 that effectively does *a += 2 * (*b), which is equivalent if (as promised by restrict) *b isn't modified by assigning to *a:

0000000000000000 <adds>:
   0:    8b 06                    mov    (%rsi),%eax   # load b once
   2:    01 c0                    add    %eax,%eax     # double it
   4:    01 07                    add    %eax,(%rdi)   # *a += 2 * (*b)
   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?

4
  • 7
    godbolt.org/z/aEDINX, strange
    – Stargateur
    Jul 29, 2019 at 18:06
  • 130
    Side remark: "Since Rust makes sure (except in unsafe code) that two mutable references cannot alias" -- it is worth mentioning that even in unsafe code, aliasing mutable references are not allowed and result in undefined behavior. You can have aliasing raw pointers, but unsafe code does not actually allow you to ignore Rust standard rules. It's just a common misconception and thus worth pointing out. Jul 29, 2019 at 19:20
  • 12
    It took me a while to figure out what the example is getting at, because I'm not skilled at reading asm, so in case it helps anyone else: it boils down to whether the two += operations in the body of adds can be reinterpreted as *a = *a + *b + *b. If the pointers don't alias, they can, you can even see what amounts to b* + *b in the second asm listing: 2: 01 c0 add %eax,%eax. But if they do alias, they can't, because by the time you add *b for the second time, it will contain a different value than the first time around (the one you store on line 4: of the first asm listing).
    – dlukes
    Aug 2, 2019 at 12:44
  • 2
    @dlukes: Yup. I commented the asm and added that *a += 2 * (*b) equivalence for future readers. Mar 19, 2022 at 18:07

1 Answer 1

476

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

21
  • 27
    This is not surprising. Its broadly-scoped claims of multi-language-friendliness notwithstanding, LLVM was specifically designed as a C++ backend and it has always had a strong tendency to choke on things that don't look enough like C++. Jul 30, 2019 at 21:38
  • 66
    @MasonWheeler if you click through to some of the issues, you can find C code examples that use restrict and miscompile on both Clang and GCC. It’s not limited to languages that aren’t “C++ enough”, unless you count C++ itself in that group.
    – Shepmaster
    Jul 30, 2019 at 21:44
  • 6
    @MasonWheeler: I don't think LLVM was really designed around the rules of C or C++, but rather around the rules of LLVM. It makes assumptions that usually hold true for C or C++ code, but from what I can tell the design is predicated upon a static-data-dependencies model which can't handle tricky corner cases. That would be okay if it pessimistically assumed data dependencies that can't be disproven, but instead it treats as no-ops actions which would write storage with the same bit pattern as it held, and which have potential but not provable data dependencies on the read and the write.
    – supercat
    Jul 30, 2019 at 22:20
  • 11
    @supercat I've read your comments a few times, but I admit I'm stumped — I have no idea what they have to do with this question or answer. Undefined behavior doesn't come into play here, this is "just" a case of multiple optimization passes interacting poorly with each other.
    – Shepmaster
    Jul 31, 2019 at 13:41
  • 11
    @avl_sweden to reiterate, it's just a bug. The loop unrolling optimization step did (does?) not fully take noalias pointers into account when executing. It created new pointers based on input pointers, improperly copying the noalias attribute even though the new pointers did alias.
    – Shepmaster
    Aug 7, 2019 at 12:53

Not the answer you're looking for? Browse other questions tagged or ask your own question.