Dlaczego kompilator Rust nie optymalizuje kodu, zakładając, że dwa zmienne odwołania nie mogą aliasu?

301

O ile mi wiadomo, aliasing odniesień / wskaźników może utrudniać kompilatorowi generowanie zoptymalizowanego kodu, ponieważ muszą one zapewnić, że wygenerowany plik binarny zachowuje się poprawnie w przypadku, gdy dwa odniesienia / wskaźniki faktycznie są aliasami. Na przykład w poniższym kodzie C

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

po skompilowaniu clang version 6.0.0-1ubuntu2 (tags/RELEASE_600/final)z -O3flagą, emituje

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

Tutaj kod przechowuje z powrotem do (%rdi)dwukrotności w przypadku int *ai int *baliasu.

Gdy wyraźnie informujemy kompilator, że te dwa wskaźniki nie mogą aliasu ze restrictsłowem kluczowym:

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

Następnie Clang wyemituje bardziej zoptymalizowaną wersję kodu binarnego:

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

Ponieważ Rust upewnia się (z wyjątkiem niebezpiecznego kodu), że dwa zmienne odwołania nie mogą być aliasami, pomyślałem, że kompilator powinien być w stanie wyemitować bardziej zoptymalizowaną wersję kodu.

Kiedy testuję poniższy kod i kompiluję go za rustc 1.35.0pomocą -C opt-level=3 --emit obj,

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

generuje:

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

Nie korzysta to z gwarancji ai bnie może być alias.

Czy to dlatego, że obecny kompilator Rust jest wciąż w fazie rozwoju i nie wprowadził jeszcze analizy aliasów w celu optymalizacji?

Czy to dlatego, że jest jeszcze szansa, że ai bmoże alias, nawet w bezpiecznym Rust?

Zhiyao
źródło
3
godbolt.org/z/aEDINX , dziwne
Stargateur
76
Uwaga boczna: „ Ponieważ Rust upewnia się (z wyjątkiem niebezpiecznego kodu), że dwa zmienne odwołania nie mogą uzyskać aliasu ” - warto wspomnieć, że nawet w unsafekodzie aliasing zmiennych zmiennych nie jest dozwolony i powoduje niezdefiniowane zachowanie. Możesz mieć aliasing surowych wskaźników, ale unsafekod w rzeczywistości nie pozwala zignorować standardowych reguł Rust. To tylko powszechne nieporozumienie i dlatego warto na nie zwrócić uwagę.
Lukas Kalbertodt
6
Zajęło mi trochę czasu, aby zrozumieć, do czego zmierza przykład, ponieważ nie mam umiejętności czytania asm, więc na wypadek, gdyby pomógł komukolwiek innemu: sprowadza się do tego, czy dwie +=operacje w ciele addsmożna interpretować jako *a = *a + *b + *b. Jeśli wskaźniki nie alias, mogą one, można nawet zobaczyć, co wynosi b* + *bw drugim asm ogłoszenia: 2: 01 c0 add %eax,%eax. Ale jeśli robią alias, nie mogą, ponieważ do czasu dodania *bpo raz drugi, będzie on zawierał inną wartość niż za pierwszym razem (ten, który przechowujesz w wierszu 4:pierwszego wykazu asm).
dlukes

Odpowiedzi:

364

Rdza pierwotnie nie pozwalają LLVM za noaliasatrybut, ale ten kod spowodowanych miscompiled . Gdy wszystkie obsługiwane wersje LLVM nie będą już błędnie kompilować kodu, zostanie on ponownie włączony .

Jeśli dodasz -Zmutable-noalias=yesdo opcji kompilatora, otrzymasz oczekiwany zestaw:

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

Mówiąc najprościej, Rust umieścił wszędzie odpowiednikrestrict słowa kluczowego C , o wiele bardziej rozpowszechniony niż jakikolwiek zwykły program C. To ćwiczyło narożne przypadki LLVM więcej niż było w stanie poprawnie obsłużyć. Okazuje się, że programiści C i C ++ po prostu nie używają tak często, jak w Rust.restrict&mut

Stało się to wiele razy .

  • Rdza od 1.0 do 1.7 - noaliaswłączona
  • Rdza od 1.8 do 1.27 - noaliaswyłączone
  • Rdza od 1.28 do 1.29 - noaliaswłączony
  • Rdza od 1.30 do ??? - noaliaswyłączone

Powiązane problemy z rdzą

Shepmaster
źródło
12
To nie jest zaskakujące. Pomimo szeroko zakrojonych twierdzeń o przyjazności dla wielu języków, LLVM został specjalnie zaprojektowany jako backend C ++ i zawsze miał silną tendencję do zadławienia się rzeczami, które nie wyglądają wystarczająco jak C ++.
Mason Wheeler
47
@MasonWheeler, jeśli przejdziesz do niektórych problemów, możesz znaleźć przykłady kodu C, które używają restricti błędnie kompilują zarówno w Clang, jak i GCC. Nie ogranicza się to do języków, które nie wystarczają na „C ++”, chyba że sam policzysz C ++ w tej grupie .
Shepmaster
6
@MasonWheeler: Nie sądzę, aby LLVM był naprawdę zaprojektowany zgodnie z zasadami C lub C ++, ale raczej zgodnie z zasadami LLVM. Przyjmuje założenia, które zwykle są prawdziwe dla kodu C lub C ++, ale z tego, co mogę powiedzieć, projekt opiera się na modelu zależności statycznych od danych, który nie jest w stanie poradzić sobie z trudnymi przypadkami narożnymi. Byłoby to w porządku, gdyby pesymistycznie zakładał zależności danych, których nie można obalić, ale zamiast tego traktuje to jako działania typu no-ops, które zapisywałyby pamięć masową z tym samym wzorcem bitów, co utrzymywały, i które mają potencjalne, ale nie do udowodnienia zależności danych od czytać i pisać.
supercat
8
@ supercat Przeczytałem Wasze komentarze kilka razy, ale przyznaję, że jestem zakłopotany - nie mam pojęcia, co mają wspólnego z tym pytaniem lub odpowiedzią. Nieokreślone zachowanie tutaj nie wchodzi w grę, jest to „tylko” przypadek wielu przejść optymalizacji słabo ze sobą współdziałających.
Shepmaster
2
@avl_sweden, aby powtórzyć, to tylko błąd . Etap optymalizacji rozwijania pętli nie (nie?) Nie uwzględnia w pełni noaliaswskaźników podczas wykonywania. Utworzono nowe wskaźniki na podstawie wskaźników wejściowych, niepoprawnie kopiując noaliasatrybut, mimo że nowe wskaźniki miały alias.
Shepmaster,