Por que o compilador Rust não otimiza o código assumindo que duas referências mutáveis ​​não podem usar o alias?

301

Até onde eu sei, o aliasing de referência / ponteiro pode prejudicar a capacidade do compilador de gerar código otimizado, pois eles devem garantir que o binário gerado se comporte corretamente no caso em que as duas referências / ponteiros realmente sejam alias. Por exemplo, no código C a seguir,

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

quando compilado clang version 6.0.0-1ubuntu2 (tags/RELEASE_600/final)com a -O3bandeira, emite

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

Aqui, o código é armazenado novamente (%rdi)duas vezes em case int *ae int *balias.

Quando dizemos explicitamente ao compilador que esses dois ponteiros não podem usar o alias da restrictpalavra-chave:

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

Então o Clang emitirá uma versão mais otimizada do código binário:

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

Como o Rust garante (exceto no código não seguro) que duas referências mutáveis ​​não possam usar o alias, eu pensaria que o compilador deveria poder emitir a versão mais otimizada do código.

Quando eu testo com o código abaixo e o compilo rustc 1.35.0com -C opt-level=3 --emit obj,

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

gera:

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

Isso não tira proveito da garantia que ae bnão pode ser um alias.

Isso ocorre porque o atual compilador Rust ainda está em desenvolvimento e ainda não incorporou a análise de alias para fazer a otimização?

Isso ocorre porque ainda existe uma chance ae bpoderia, mesmo em Rust seguro?

rust compiler-optimization llvm-codegen Zhiyao
fonte
3
godbolt.org/z/aEDINX , estranho
Stargateur
76
Observação lateral: " Como o Rust garante (exceto no código não seguro) que duas referências mutáveis ​​não possam usar o alias " - vale ressaltar que mesmo no unsafecódigo, referências mutáveis ​​no alias não são permitidas e resultam em comportamento indefinido. Você pode ter ponteiros brutos com alias, mas o unsafecódigo na verdade não permite que você ignore as regras padrão do Rust. É apenas um equívoco comum e, portanto, vale a pena apontar.
Lukas Kalbertodt 29/07/19
6
Demorei um pouco para descobrir como o exemplo está chegando, porque eu não sou habilidoso em ler asm, por isso, caso ajude mais alguém: tudo se resume a se as duas +=operações no corpo de addspodem ser reinterpretadas como *a = *a + *b + *b. Se os ponteiros não aliás, eles podem, você pode até ver o que equivale a b* + *bno segundo asm lista: 2: 01 c0 add %eax,%eax. Mas se eles criarem um alias, não poderão, porque na hora em que você adicionar *bpela segunda vez, ele conterá um valor diferente do que na primeira vez (o que você armazena na linha 4:da primeira listagem de asm).
dlukes

Respostas:

364

Rust originalmente fez habilitar do LLVM noaliasatributo, mas este código miscompiled causado . Quando todas as versões suportadas do LLVM não compactarem mais o código, ele será reativado .

Se você adicionar -Zmutable-noalias=yesàs opções do compilador, obterá o assembly esperado:

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

Simplificando, Rust colocou o equivalente à restrictpalavra-chave de C em todos os lugares , muito mais prevalente do que qualquer programa C usual. Isso exercitou casos de canto do LLVM mais do que era capaz de lidar corretamente. Acontece que os programadores de C e C ++ simplesmente não usam restrictcom tanta frequência quanto &muté usado no Rust.

Isso aconteceu várias vezes .

  • Rust 1.0 a 1.7 - noaliasativado
  • Rust 1.8 a 1.27 - noaliasdesativado
  • Ferrugem 1,28 a 1,29 - noaliasativado
  • Ferrugem 1,30 a ??? - noaliasdesativado

Problemas de ferrugem relacionados

Shepmaster
fonte
12
Isto não é surpreendente. Apesar de suas reivindicações de amplo escopo de compatibilidade com vários idiomas, o LLVM foi projetado especificamente como um back-end em C ++ e sempre teve uma forte tendência a engasgar com coisas que não se parecem com o C ++.
Mason Wheeler
47
@MasonWheeler Se você clicar em alguns dos problemas, poderá encontrar exemplos de código C que usam restricte compilam incorretamente no Clang e no GCC. Não se limita a idiomas que não são "C ++ suficientes", a menos que você conte o C ++ nesse grupo .
Shepmaster 30/07/19
6
@MasonWheeler: Eu não acho que o LLVM foi realmente projetado em torno das regras do C ou C ++, mas sim em torno das regras do LLVM. Ele faz suposições que geralmente são verdadeiras para código C ou C ++, mas, pelo que posso dizer, o design se baseia em um modelo de dependências de dados estáticos que não pode lidar com casos de canto complicados. Tudo bem se ele assumisse pessimisticamente dependências de dados que não podem ser refutadas, mas, em vez disso, trata-se de ações não operacionais que gravariam armazenamento com o mesmo padrão de bits que mantinham e que tinham dependências de dados potenciais, mas não prováveis, no leia e escreva.
Supercat
8
@ supercat Eu li seus comentários algumas vezes, mas admito que estou perplexo - não tenho idéia do que eles têm a ver com esta pergunta ou resposta. O comportamento indefinido não entra em jogo aqui, este é "apenas" um caso de várias passagens de otimização interagindo mal entre si.
Shepmaster 31/07/19
2
@avl_sweden para reiterar, é apenas um bug . A etapa de otimização de desenrolamento do loop (não leva) leva totalmente noaliasem conta os ponteiros durante a execução. Ele criou novos ponteiros com base nos ponteiros de entrada, copiando incorretamente o noaliasatributo, mesmo que os novos ponteiros fizessem um alias.
Shepmaster 7/08/19