El compilador gc usa un lenguaje especial orientado a objetos ( DSL ) similar a Lisp para describir las reglas de optimización de asignación individual estática (SSA).

Propongo analizar los elementos principales de este lenguaje, sus características y limitaciones.
Como ejercicio, agreguemos al compilador Go la generación de una instrucción que no había generado previamente, optimizando la expresión a*b+c .

Este es el primer artículo de una serie sobre las partes internas del backend del compilador Go SSA , por lo que, además de revisar la descripción de las reglas DSL en sí, analizaremos los componentes relacionados para crear la base necesaria para nuestra próxima sesión.

Introduccion

El compilador de frontend go finaliza en el momento de generar la vista SSA desde el AST anotado. Las funciones responsables de la conversión se pueden encontrar en cmd / compile / internal / gc / ssa.go. El punto de entrada al backend SSA es la función ssa.Compile , definida en cmd / compile / internal / ssa / compile.go .

El optimizador SSA Go consta de varias fases, cada una de las cuales pasa a través de la función compilada. Algunas fases usan las llamadas "reglas de reescritura", las reglas para convertir una secuencia SSA en otra, potencialmente más óptima.

Las reglas de transformación se describen usando expresiones S. Los elementos de estas expresiones son ssa.Value . En el caso más simple, estas reglas le permiten reemplazar un valor ssa.Value con otro.

Por ejemplo, el siguiente código contrae la multiplicación de constantes de 8 bits:

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

Hay dos categorías principales de valores SSA: de alto nivel, casi independientes de la máquina de destino, y aquellas que son específicas de la arquitectura (generalmente asignadas a instrucciones de máquina 1 en 1).

Las optimizaciones se describen en términos de estas dos categorías. Primero, de alto nivel y común a todas las arquitecturas, luego orientado a la plataforma.

Todo el código asociado con las reglas se encuentra en cmd / compile / internal / ssa / gen . Consideraremos dos conjuntos:

1. genericOps.go : operaciones independientes de la máquina.
2. AMD64Ops.go : operaciones específicas de GOARCH=AMD64 (64 bits x86).

Después de las primeras fases que funcionan en la máquina abstracta, se realiza la llamada reducción, que da como resultado una transición de genericOps a un conjunto de arquitecturas específicas. En nuestro ejemplo, este será AMD64Ops . Después de este punto, todas las fases posteriores operan en la presentación de la segunda categoría.

Después del optimizador, entra en juego un generador de código. Para AMD64, la implementación de generación de código se puede encontrar en el paquete cmd / compile / internal / amd64 . La tarea del generador de código es reemplazar ssa.Block y ssa.Value con la secuencia obj.Prog pasada al ensamblador . El ensamblador recopilará el código de la máquina, que estará listo para su ejecución después del enlace .

Reglas de optimización

Si los archivos con definiciones de operación se nombran como " ${ARCH}Ops.go ", las reglas de optimización se colocan en " ${ARCH}.Rules ".

Las reglas de alto nivel realizan transformaciones simples, la mayoría del plegado de expresiones constantes , así como algunas transformaciones que simplifican el procesamiento posterior.

Cada archivo con reglas de bajo nivel consta de dos partes:

1. Bajar - reemplazar operaciones abstractas con equivalentes de máquina.
2. Las optimizaciones en sí mismas.

Un ejemplo de reducción de una operación a una máquina:

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

Es en las optimizaciones de bajo nivel que se realiza el número principal de optimizaciones importantes, como reducir el costo de las operaciones , incorporar parcialmente y utilizar las capacidades de los modos de direccionamiento de memoria disponibles en el procesador.

Las operaciones tienen un nombre mnemotécnico, que generalmente se denomina código de operación. Los códigos de operación de operaciones dependientes de la arquitectura generalmente reflejan los nombres de las instrucciones reales.

Regla Descripción Lengua Sintaxis

La gramática básica se describe en 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  

También vale la pena mencionar que los comentarios " // " están permitidos dentro de los archivos .Rules .

Veamos un ejemplo simple que contiene todos estos elementos:

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

Todas estas firmas explicativas no son parte de un registro de regla válido.

Esta regla convierte x+0 a x . Todo dentro de la sección de condiciones es un código Go normal,
a menos que se limite a expresiones, cuyo resultado debería ser un bool .
Puede llamar a predicados definidos en rewrite.go .

Además de los códigos de operación habituales, se pueden usar combinaciones que dan lugar a varias reglas:

 (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) es una de las operaciones en genericOps.go y expresa la carga de un puntero a la pila de hardware. Para arquitecturas donde no hay SP hardware, se emula.

Características de las variables en plantillas (expresiones S a la izquierda de -> ):

• Las variables, como x , sin expresión a través de : capturan cualquier cosa
• como una variable regular, _ captura cualquier valor, pero el resultado puede ignorarse

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

Si no se especifica AuxInt (expresión entre corchetes), la regla se activará en cualquier valor AuxInt . De manera similar con los parámetros {} (sobre ellos a continuación).

El nombre v significa la forma capturada más externa.
Por ejemplo, para la expresión (ADDQconst (SUBQconst x)) forma externa es ADDQconst .

Las variables se pueden usar varias veces, esto le permite requerir que varias partes de la expresión S coincidan entre sí:

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

Tipos en reglas

En algunos casos, se requiere indicar explícitamente el tipo de formulario generado y / o coincidente.
El tipo se indica en "corchetes triangulares", como argumento de tipo en plantillas C ++:

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

Además de los tipos, hay "caracteres" (o, más universalmente, propiedades Aux ).

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

• [argsWidth] - Value.AuxInt . Para StaticCall : el tamaño total de los argumentos pasados
• {target} - Value.Aux . Para StaticCall - llamada función
• <typ.UInt32> - Value.Type . Tipo de valor

La semántica de Aux y AuxInt varía mucho de una operación a otra. La mejor fuente de documentación en este caso son los archivos *Ops.go Cada opData opData opcode tiene un campo aux que describe cómo interpretar estos campos.

Para la descripción de los tipos se utiliza el paquete cmd / compile / internal / types . Algunos tipos son específicos del backend SSA, por ejemplo types.TypeFlags . types.TypeFlags , el resto son comunes entre cmd/compile/internal/gc y cmd/compile/internal/ssa .

Tipos especiales

Hay un tipo especial de tipos: types.TypeMem , que realiza varias funciones a la vez:

1. Le permite ordenar y agrupar ssa.Value por patrones de acceso a la memoria. En particular, esto garantiza el orden correcto de ejecución dentro del marco de los bloques base (sobre ellos a continuación).
2. Determina el estado del flujo de memoria en el programa. Si la instrucción modifica la memoria, se generará un nuevo valor SSA de tipos types.TypeMem como resultado de esta operación.

Al igual que el significado especial de OpPhi , la memoria se interpreta excepcionalmente en muchas fases del optimizador.

Otro tipo especial es el types.TypeFlags mencionado anteriormente. Este tipo describe la instrucción que genera banderas de CPU .

En este caso, las instrucciones como ADDQ , aunque generan banderas, no son de tipo types.Flags , pero están marcadas con el atributo clobberFlags .

types.Flags usa para resaltar el resultado de instrucciones como CMPQ , que no escriben el resultado en ninguno de sus operandos explícitos, sino que solo actualizan el estado interno del procesador, que puede usarse en la siguiente instrucción.

Las instrucciones como SETL permiten "leer" las banderas y devolverlas como ssa.Value , que puede colocarse en un registro.

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

Programa de inspección de la SSA

Digamos que tenemos un programa como este ( example.go ):

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

Podemos ver el código SSA que se genera para la función fusedMulAdd :

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

Ahora verifique el directorio de trabajo (actual):

• ssa.txt contiene un volcado de tekt.
• ssa.html , que se genera automáticamente, contiene la misma información, pero en un formato más interactivo y fácil de leer. Intenta abrir en un 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 

Así es como se ve el programa SSA para fusedMulAdd después de la 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) 

Traduciendo esto a expresiones 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) 

Agregar nuevas reglas de optimización

En los procesadores con FMA, podemos calcular a*c + b en una instrucción en lugar de dos.

Tome CL117295 como base de la autoría de Ilya Tokar .

Para su comodidad, he preparado un parche de diff .

1. Agregar una nueva operación - FMASD

En el archivo compile/internal/ssa/gen/AMD64Ops.go encuentre la AMD64ops y agregue un nuevo elemento (en cualquier lugar):

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

Como antes no había operaciones (fp,fp,fp -> fp) , debe definir un nuevo calificador:

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

2. Agregar una regla de optimización

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

Una implementación más correcta no sería incondicional y verificaría la disponibilidad de FMA. Asumiremos que definitivamente hay un FMA en nuestra máquina de destino.

El compilador usa config para tales comprobaciones:

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

 $ lscpu | grep fma 

3. Implementación de la generación de código.

Ahora, en la función ssaGenValue , definida en el compile/internal/amd64/ssa.go , debe agregar la generación de código para 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. } } 

Ahora todo está listo para probar el trabajo de nuestra nueva optimización. Es muy raro agregar nuevas instrucciones, generalmente se realizan nuevas optimizaciones basadas en operaciones SSA ya definidas.

Comprobación de resultados

El primer paso es generar el código Go a partir de las gen/AMD64Ops.go y gen/AMD64.Rules .

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

A continuación, necesitamos construir nuestro nuevo compilador:

 go install cmd/compile 

Ahora, al compilar el mismo ejemplo, obtenemos un 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 

Bloques básicos

Ahora que se ha realizado el trabajo más difícil, hablemos de los bloques base .

Los valores que optimizamos anteriormente están en bloques, y los bloques están en función.

Los bloques, como ssa.Value , son abstractos y dependen de la máquina. Todos los bloques tienen exactamente un punto de entrada y de 0 a 2 bloques de destino (según el tipo de bloque).

Los bloques más simples son If , Exit y Plain :

• Exit bloque de Exit tiene 0 bloques de asignación. Estos son bloques de hojas que hacen un salto no local, por ejemplo, usando panic .
• Plain bloque Plain tiene 1 bloques de asignación. Se puede considerar como un salto incondicional después de completar todas las instrucciones del bloque a otro bloque.
• If bloque tiene 2 bloques de destino. La transición se lleva a cabo según la condición ( Block.Control ).

Aquí hay ejemplos simples de reescribir bloques abstractos en bloques AMD64 :

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

El tema de los bloques se considerará con más detalle en el contexto de otras fases de optimización en la parte SSA del compilador.

Limitaciones de las reglas de optimización

El backend de SSA tiene sus ventajas. Algunas optimizaciones son factibles en O(1) . Sin embargo, también hay inconvenientes debido a que el SSA del optimizador solo no será suficiente, al menos hasta que cambien algunos aspectos de su implementación.

Suponga que desea append :

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

En el momento en que se genera el SSA, la estructura de alto nivel del código se pierde y append , al no ser una función ordinaria, ya está integrada en el cuerpo del bloque contenedor. Tendrá que escribir una regla engorrosa que capture la secuencia completa de operaciones generadas para append .

Hablando específicamente sobre .Rules , entonces este DSL tiene un trabajo bastante débil con bloques ( ssa.Block ). Cualquier optimización no trivial asociada con bloques es imposible de expresar en este lenguaje. La actualización parcial del bloque no es posible. También es imposible tirar bloques (pero hay un truco en forma del First bloque, que se usa para eliminar el código muerto).

Incluso si algunas de las deficiencias son reparables, la mayoría de los compiladores están de acuerdo en que no existe una única forma intermedia y mejor para representar el código.

Ve que va más rápido

Si se te ocurren algunas reglas geniales de optimización, no dudes en enviarlo a go-review.googlesource.com . Estaría encantado de revisar (agregar a iskander.sharipov@intel.com en CC).

¡Feliz compilador de pirateo!

Material de bonificación

Ejemplos de buenos parches en Go que agregaron o cambiaron las reglas de SSA:

• CL99656: cmd / compile / internal / ssa: emite IMUL3 {L / Q} para MUL {L / Q} const en x86
• CL102277: cmd / compile / internal / ssa: optimiza el doble NEG en amd64
• CL54410: cmd / compile / internal / ssa: use sse to zero en amd64
• CL58090: cmd / compile / internal / ssa: elimine las extensiones cero redundantes en amd64
• CL95475: cmd / compile / internal / ssa: combinar tiendas de bytes en amd64
• CL97175: cmd / compile / internal / ssa: combine tiendas LittleEndian consecutivas en arm64
• CL115617: cmd / compile / internal / ssa: eliminar extensión cero inútil
• CL101275: cmd / compilar: agregar operaciones amd64 LEAL {1,2,4,8}

No hace mucho tiempo, un documento README parecía describir la parte SSA del compilador.
Lectura recomendada.