O compilador gc usa uma DSL (linguagem orientada a objetos) semelhante ao Lisp para descrever as regras de otimização de atribuição única estática (SSA).

Proponho analisar os principais elementos dessa linguagem, suas características e limitações.
Como exercício, vamos adicionar ao compilador Go a geração de uma instrução que não havia gerado anteriormente, otimizando a expressão a*b+c .

Este é o primeiro artigo de uma série sobre os componentes internos do back-end do compilador Go SSA ; portanto, além de revisar a descrição das regras DSL, veremos os componentes relacionados para criar a base necessária para a próxima sessão.

1. Introdução

O compilador frontend go termina no momento da geração da exibição SSA do AST anotado. As funções responsáveis ​​pela conversão podem ser encontradas em cmd / compile / internal / gc / ssa.go. O ponto de entrada no back-end SSA é a função ssa.Compile , definida em cmd / compile / internal / ssa / compile.go .

O otimizador SSA Go consiste em várias fases, cada uma das quais passa pela função compilada. Algumas fases usam as chamadas "regras de reescrita", as regras para converter uma sequência SSA em outra, potencialmente mais ideais.

As regras de transformação são descritas usando expressões S. Os elementos dessas expressões são ssa.Value . No caso mais simples, essas regras permitem substituir um ssa.Value por outro.

Por exemplo, o código abaixo reduz a multiplicação de constantes de 8 bits:

 (Mul8 (Const8 [c]) (Const8 [d])) -> (Const8 [int64(int8(c*d))]) 

Existem duas categorias principais de valores de SSA: alto nível, quase independente da máquina de destino e aquelas específicas da arquitetura (geralmente mapeadas para instruções de máquina 1 em 1).

As otimizações são descritas em termos dessas duas categorias. Primeiro, de alto nível e comum a todas as arquiteturas, depois orientado à plataforma.

Todo o código associado às regras está em cmd / compile / internal / ssa / gen . Vamos considerar dois conjuntos:

1. genericOps.go - operações independentes da máquina.
2. AMD64Ops.go - operações específicas para GOARCH=AMD64 (x86 de 64 bits).

Após as primeiras fases que funcionam na máquina abstrata, é executada a chamada redução, que resulta em uma transição de genericOps para um conjunto de arquiteturas específicas. No nosso exemplo, este será AMD64Ops . Após esse ponto, todas as fases subsequentes operam na apresentação da segunda categoria.

Após o otimizador, um gerador de código entra em ação. Para o AMD64, a implementação da geração de código pode ser encontrada no pacote cmd / compile / internal / amd64 . A tarefa do gerador de código é substituir ssa.Block e ssa.Value pela sequência obj.Prog passada para o assembler . O montador coletará o código da máquina, que estará pronto para execução após a vinculação .

Regras de otimização

Se os arquivos com definições de operação forem nomeados como " ${ARCH}Ops.go ", as regras de otimização serão colocadas em " ${ARCH}.Rules ".

As regras de alto nível executam transformações simples, a maioria das dobras de expressões constantes , bem como algumas transformações que simplificam o processamento subsequente.

Cada arquivo com regras de baixo nível consiste em duas partes:

1. Abaixando - substituindo operações abstratas por equivalentes de máquina.
2. As próprias otimizações.

Um exemplo de redução de uma operação para uma máquina:

 (Const32 [val]) -> (MOVLconst [val]) // L - long, 32- (Const64 [val]) -> (MOVQconst [val]) // Q - quad, 64- | | generic op | AMD64 op 

É nas otimizações de baixo nível que o principal número de otimizações importantes é realizado, como a redução do custo das operações , incorporação parcial e utilização dos recursos dos modos de endereçamento de memória disponíveis no processador.

As operações têm um nome mnemônico, que geralmente é chamado de código de operação. Os códigos de operação das operações dependentes da arquitetura geralmente refletem os nomes das instruções reais.

Sintaxe do idioma da descrição da regra

A gramática básica é descrita em rulegen.go :

 // rule syntax: // sexpr [&& extra conditions] -> [@block] sexpr // // sexpr are s-expressions (lisp-like parenthesized groupings) // sexpr ::= [variable:](opcode sexpr*) // | variable // | <type> // | [auxint] // | {aux} // // aux ::= variable | {code} // type ::= variable | {code} // variable ::= some token // opcode ::= one of the opcodes from the *Ops.go files 

 //  : // sexpr [&&  ] -> [@block] sexpr // // sexpr -  S- (   ) // sexpr ::= [variable:](opcode sexpr*) // | variable // | <type> // | [auxint] // | {aux} // // aux ::= variable | {code} // type ::= variable | {code} // variable ::= Go  ( ) // opcode ::=   *Ops.go  

Também vale a pena mencionar que " // " comentários são permitidos nos arquivos .Rules .

Vejamos um exemplo simples que contém todos esses elementos:

  Opcode=ADDLconst -    32-  : AuxInt=c - ,    `x` : : (ADDLconst [c] x) && int32(c)==0 -> x | / | / | | / | / | | / | /    | /   ( `&&`    ) ,     

Todas essas assinaturas explicativas não fazem parte de um registro de regra válido.

Esta regra converte x+0 em x . Tudo dentro da seção de condições é um código Go normal,
a menos que limitado a expressões, cujo resultado deve ser um bool .
Você pode chamar predicados definidos em rewrite.go .

Além dos opcodes usuais, podem ser usadas combinações que dão origem a várias regras:

 (ADD(Q|L)const [off] x:(SP)) -> (LEA(Q|L) [off] x) //  Q|L alternation: (ADDQconst [off] x:(SP)) -> (LEAQ [off] x) (ADDLconst [off] x:(SP)) -> (LEAL [off] x) //    `x`: (ADDQconst [off] (SP)) -> (LEAQ [off] (SP)) (ADDLconst [off] (SP)) -> (LEAL [off] (SP)) 

(SP) é uma das operações no genericOps.go e expressa o carregamento de um ponteiro na pilha de hardware. Para arquiteturas em que não há hardware SP , ele é emulado.

Recursos de variáveis ​​em modelos (expressões S à esquerda de -> ):

• Variáveis, como x , sem expressão através de : capturam qualquer coisa
• como uma variável regular, _ captura qualquer valor, mas o resultado pode ser ignorado

 //       :    ADDQconst, //          : (ADDQconst _) -> v (ADDQconst x) -> (ADDQconst x) 

Se AuxInt não AuxInt especificado (expressão entre colchetes), a regra será acionada em qualquer valor de AuxInt . Da mesma forma com os parâmetros {} (sobre eles abaixo).

O nome v significa a forma capturada mais externa.
Por exemplo, para a expressão (ADDQconst (SUBQconst x)) formulário externo é ADDQconst .

As variáveis ​​podem ser usadas várias vezes, isso permite exigir que várias partes da expressão S correspondam:

 (ADDQconst [v] (ADDQconst [v] x)) // , ,  "x+2+2" (x+v+v). 

Tipos de regras

Em alguns casos, é necessário indicar explicitamente o tipo de formulário gerado e / ou correspondente.
O tipo é indicado em "colchetes triangulares", como um argumento de tipo nos modelos C ++:

 // typ.UInt32 -   BTSLconst. // BSFL    typ.UInt32,    //    . (Ctz16 x) -> (BSFL (BTSLconst <typ.UInt32> [16] x)) 

Além dos tipos, existem "caracteres" (ou, mais universalmente - propriedades Aux ).

 (StaticCall [argsWidth] {target} mem) -> (CALLstatic [argsWidth] {target} mem) 

• [argsWidth] - Value.AuxInt . Para StaticCall - o tamanho total dos argumentos transmitidos
• {target} - Value.Aux . Para StaticCall - chamada de função
• <typ.UInt32> - Value.Type . Tipo de valor

A semântica de Aux e AuxInt varia muito de operação para operação. A melhor fonte de documentação nesse caso são os arquivos *Ops.go Cada opData código de operação opData possui um campo aux que descreve como interpretar esses campos.

Para a descrição dos tipos, o pacote cmd / compile / internal / types é usado . Alguns tipos são específicos para o back-end do SSA, por exemplo types.TypeFlags , o restante é comum entre cmd/compile/internal/gc e cmd/compile/internal/ssa .

Tipos especiais

Há um tipo especial de types.TypeMem , que executa várias funções ao mesmo tempo:

1. Permite classificar e agrupar ssa.Value por padrões de acesso à memória. Em particular, isso garante a ordem de execução correta na estrutura dos blocos base (sobre eles abaixo).
2. Determina o estado do fluxo de memória no programa. Se a instrução modificar a memória, um novo valor SSA do tipo types.TypeMem será gerado como resultado desta operação.

Como o significado especial do OpPhi , a memória é interpretada excepcionalmente em muitas fases do otimizador.

Outro tipo especial são os types.TypeFlags mencionados acima. Este tipo descreve a instrução que gera sinalizadores de CPU .

Nesse caso, instruções como ADDQ , embora gerem sinalizadores, não são do tipo types.Flags , mas são marcadas com o atributo clobberFlags .

types.Flags usado para destacar o resultado de instruções como CMPQ , que não gravam o resultado em nenhum de seus operandos explícitos, mas apenas atualizam o estado interno do processador, que pode ser usado pela próxima instrução.

Instruções como SETL permitem "ler" sinalizadores e retorná-los como ssa.Value , que pode ser colocado em um registro.

  L-less than G-greater than | | (SETL (InvertFlags x)) -> (SETG x) | ,   

Programa de inspeção SSA

Digamos que temos um programa como este ( example.go ):

 package example func fusedMulAdd(a, b, c float64) float64 { return a*c + b } 

Podemos observar o código SSA gerado para a função fusedMulAdd :

 $ GOSSAFUNC=fusedMulAdd go tool compile example.go > ssa.txt 

Agora verifique o diretório de trabalho (atual):

• ssa.txt contém um despejo de texto.
• ssa.html , gerado automaticamente, contém as mesmas informações, mas em um formato mais interativo e de fácil leitura. Tente abrir em um navegador.

 v7 (4) MOVSD a(SP), X0 v11 (4) MOVSD c+16(SP), X1 v12 (4) MULSD X1, X0 v6 (4) MOVSD b+8(SP), X1 v13 (4) ADDSD X1, X0 v15 (4) MOVSD X0, ret+24(SP) b1 (4) RET 

É assim que o programa SSA do fusedMulAdd parece após a fase lower (ssa.html):

 lower [77667 ns] b1: v1 (?) = InitMem <mem> v2 (?) = SP <uintptr> v7 (?) = LEAQ <*float64> {~r3} v2 v8 (3) = Arg <float64> {a} v9 (3) = Arg <float64> {b} v10 (3) = Arg <float64> {c} v12 (+4) = MULSD <float64> v8 v10 v13 (4) = ADDSD <float64> v12 v9 v14 (4) = VarDef <mem> {~r3} v1 v15 (4) = MOVSDstore <mem> {~r3} v2 v13 v14 Ret v15 (line +4) 

Traduzindo isso em expressões S:

 (MOVQstore {~r3} (SP) (ADDSD (MULSD (Arg {a}) (Arg {c})) (Arg {b}))) 

 regalloc [87237 ns] b1: v1 (?) = InitMem <mem> v14 (4) = VarDef <mem> {~r3} v1 v2 (?) = SP <uintptr> : SP v8 (3) = Arg <float64> {a} : a[float64] v9 (3) = Arg <float64> {b} : b[float64] v10 (3) = Arg <float64> {c} : c[float64] v7 (4) = LoadReg <float64> v8 : X0 v11 (4) = LoadReg <float64> v10 : X1 v12 (+4) = MULSD <float64> v7 v11 : X0 v6 (4) = LoadReg <float64> v9 : X1 v13 (4) = ADDSD <float64> v12 v6 : X0 v15 (4) = MOVSDstore <mem> {~r3} v2 v13 v14 Ret v15 (line +4) 

Adicionando novas regras de otimização

Nos processadores com FMA, podemos calcular a*c + b em uma instrução em vez de duas.

Tome CL117295 como base da autoria de Ilya Tokar .

Para sua conveniência, preparei um patch diff .

1. Adicionando uma nova operação - FMASD

No arquivo compile/internal/ssa/gen/AMD64Ops.go localize a AMD64ops fatia AMD64ops e adicione um novo elemento (em qualquer lugar):

 { // fp64 fma name: "FMASD", //   SSA argLength: 3, reg: fp31, //   regalloc,   resultInArg0: true, //     source,  destination asm: "VFMADD231SD", //   }, 

Como não havia operações (fp,fp,fp -> fp) antes, você precisa definir um novo qualificador:

  fp01 = regInfo{inputs: nil, outputs: fponly} fp21 = regInfo{inputs: []regMask{fp, fp}, outputs: fponly} + fp31 = regInfo{inputs: []regMask{fp, fp, fp}, outputs: fponly} 

2. Adicionando uma regra de otimização

 (ADDSD (MULSD xy) z) -> (FMASD zxy) 

Uma implementação mais correta não seria incondicional e verificaria a disponibilidade das FMA. Assumiremos que há definitivamente uma FMA em nossa máquina de destino.

O compilador usa a config para essas verificações:

 //  config.useFMA=false,    . (ADDSD (MULSD xy) z) && config.useFMA-> (FMASD zxy) 

 $ lscpu | grep fma 

3. Implementação da geração de código

Agora, na função ssaGenValue , definida no compile/internal/amd64/ssa.go , você precisa adicionar a geração de código para o FMASD :

 func ssaGenValue(s *gc.SSAGenState, v *ssa.Value) { switch v.Op { case ssa.OpAMD64FMASD: p := s.Prog(v.Op.Asm()) //   obj.Prog    // From:  source . p.From = obj.Addr{Type: obj.TYPE_REG, Reg: v.Args[2].Reg()} // To: destination . // v.Reg()  ,      FMASD. p.To = obj.Addr{Type: obj.TYPE_REG, Reg: v.Reg()} // From3:  source . //  From3 .     //  RestArgs,    source ,  . p.SetFrom3(obj.Addr{ Type: obj.TYPE_REG, Reg: v.Args[1].Reg(), }) if v.Reg() != v.Args[0].Reg() { //   resultInArg0 s := v.LongString() v.Fatalf("input[0] and output not in same register %s", s) } //    ,     case. } } 

Agora tudo está pronto para testar o trabalho de nossa nova otimização. É muito raro adicionar novas instruções, geralmente novas otimizações são feitas com base em operações SSA já definidas.

Verificando resultados

A primeira etapa é gerar o código Go a partir das gen/AMD64Ops.go e gen/AMD64.Rules .

 #  GOROOT  ,   ,   `go env GOROOT`. cd $GOROOT/src/cmd/compile/internal/ssa/gen && go run *.go 

Em seguida, precisamos construir nosso novo compilador:

 go install cmd/compile 

Agora, ao compilar o mesmo exemplo, obtemos um código de máquina diferente:

 - v7 (4) MOVSD a(SP), X0 - v11 (4) MOVSD c+16(SP), X1 - v12 (4) MULSD X1, X0 - v6 (4) MOVSD b+8(SP), X1 - v13 (4) ADDSD X1, X0 - v15 (4) MOVSD X0, ret+24(SP) - b1 (4) RET + v12 (4) MOVSD b+8(SP), X0 + v7 (4) MOVSD a(SP), X1 + v11 (4) MOVSD c+16(SP), X2 + v13 (4) VFMADD231SD X2, X1, X0 + v15 (4) MOVSD X0, ret+24(SP) + b1 (4) RET 

Blocos básicos

Agora que o trabalho mais difícil foi realizado, vamos falar sobre os blocos de base .

Os valores que otimizamos acima estão em blocos e os blocos estão em função.

Blocos, como ssa.Value , são abstratos e dependem da máquina. Todos os blocos têm exatamente um ponto de entrada e de 0 a 2 blocos de destino (dependendo do tipo de bloco).

Os blocos mais simples são If , Exit e Plain :

• Exit bloco de Exit possui 0 blocos de atribuição. Estes são blocos de folhas que dão um salto não local, por exemplo, usando panic .
• Plain bloco Plain possui 1 bloco de atribuição. Pode ser considerado como um salto incondicional após a conclusão de todas as instruções do bloco para outro bloco.
• If bloco tiver 2 blocos de destino. A transição é realizada dependendo da condição ( Block.Control ).

Aqui estão exemplos simples de reescrever blocos abstratos em blocos AMD64 :

   "then" ( ) |  "else" ( ) | | (If (SETL cmp) yes no) -> (LT cmp yes no) (If (SETLE cmp) yes no) -> (LE cmp yes no) 

O tópico dos blocos será considerado em mais detalhes no contexto de outras fases de otimização na parte SSA do compilador.

Limitações das regras de otimização

O back-end da SSA tem suas vantagens. Algumas otimizações são viáveis ​​em O(1) . No entanto, também existem desvantagens devido às quais o SSA do otimizador sozinho não será suficiente, pelo menos até que alguns aspectos de sua implementação sejam alterados.

Suponha que você queira append :

 xs = append(xs, 'a') xs = append(xs, 'b') // => xs = append(xs, 'a', 'b') 

No momento em que o SSA é gerado, a estrutura de alto nível do código é perdida e append , não sendo uma função comum, já está embutida no corpo do bloco que o contém. Você precisará escrever uma regra complicada que capture toda a sequência de operações geradas para append .

Falando especificamente sobre .Rules , esse DSL tem um trabalho bastante fraco com blocos ( ssa.Block ). Qualquer otimização não trivial associada a blocos é impossível para expressão nessa linguagem. Atualização parcial do bloco não é possível. Também é impossível jogar fora blocos (mas há um hack na forma do First bloco, que é usado para excluir o código morto).

Mesmo que algumas das deficiências sejam corrigíveis, a maioria dos compiladores concorda que não existe uma forma intermediária única e melhor para representar o código.

Vá mais rápido

Se você criar algumas regras interessantes de otimização, envie-as para go-review.googlesource.com . Ficaria feliz em revisar (adicione iskander.sharipov@intel.com no CC).

Feliz hacker compilador!

Material bônus

Exemplos de boas correções no Go que adicionaram ou alteraram regras de SSA:

• CL99656: cmd / compile / internal / ssa: emite IMUL3 {L / Q} para MUL {L / Q} const no x86
• CL102277: cmd / compile / internal / ssa: otimizar afastado o dobro do NEG no amd64
• CL54410: cmd / compile / internal / ssa: use sse para zero no amd64
• CL58090: cmd / compile / internal / ssa: remove zeroextensions redundantes no amd64
• CL95475: cmd / compile / internal / ssa: combina armazenamentos de bytes no amd64
• CL97175: cmd / compile / internal / ssa: combina lojas LittleEndian consecutivas no arm64
• CL115617: cmd / compile / internal / ssa: remova a extensão zero inútil
• CL101275: cmd / compile: inclua operações amd64 LEAL {1,2,4,8}

Há pouco tempo, apareceu um documento README para descrever a parte SSA do compilador.
Leitura recomendada.