Le compilateur gc utilise un langage orienté objet ( DSL ) de type Lisp spécial pour décrire les règles d'optimisation SSA ( Static Single Assignment ).

Je propose d'analyser les principaux éléments de ce langage, ses caractéristiques et ses limites.
Comme exercice, ajoutons au compilateur Go la génération d'une instruction qu'il n'avait pas générée précédemment, optimisant l'expression a*b+c .

Ceci est le premier article d'une série sur les composants internes du backend du compilateur Go SSA.Par conséquent, en plus d'examiner la description des règles DSL elle-même, nous examinerons les composants connexes pour créer la base nécessaire pour notre prochaine session.

Présentation

Le compilateur frontend go se termine au moment de la génération de la vue SSA à partir de l'AST annoté. Les fonctions responsables de la conversion se trouvent dans cmd / compile / internal / gc / ssa.go. Le point d'entrée du backend SSA est la fonction ssa.Compile , définie dans cmd / compile / internal / ssa / compile.go .

L'optimiseur SSA Go se compose de plusieurs phases, chacune passant par la fonction compilée. Certaines phases utilisent les soi-disant "règles de réécriture", les règles pour convertir une séquence SSA en une autre, potentiellement plus optimale.

Les règles de transformation sont décrites à l'aide d' expressions S. Les éléments de ces expressions sont ssa.Value . Dans le cas le plus simple, ces règles vous permettent de remplacer un ssa.Value par un autre.

Par exemple, le code ci-dessous réduit la multiplication des constantes 8 bits:

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

Il existe deux catégories principales de valeurs SSA: de haut niveau, presque indépendantes de la machine cible, et celles qui sont spécifiques à l'architecture (généralement associées à des instructions machine 1 en 1).

Les optimisations sont décrites en fonction de ces deux catégories. D'abord, de haut niveau et commun à toutes les architectures, puis orienté plateforme.

Tout le code associé aux règles se trouve dans cmd / compile / internal / ssa / gen . Nous considérerons deux ensembles:

1. genericOps.go - opérations indépendantes de la machine.
2. AMD64Ops.go - opérations spécifiques à GOARCH=AMD64 (64 bits x86).

Après les premières phases qui fonctionnent sur la machine abstraite, la soi-disant réduction est effectuée, ce qui entraîne une transition de genericOps à un ensemble d'architectures spécifiques. Dans notre exemple, ce sera AMD64Ops . Après ce point, toutes les phases suivantes opèrent sur la présentation de la deuxième catégorie.

Après l'optimiseur, un générateur de code entre en jeu. Pour AMD64, l'implémentation de génération de code se trouve dans le package cmd / compile / internal / amd64 . La tâche du générateur de code est de remplacer ssa.Block et ssa.Value par la séquence obj.Prog passée à l' assembleur . L'assembleur collectera le code machine, qui sera prêt à être exécuté après la liaison .

Règles d'optimisation

Si les fichiers avec des définitions d'opérations sont nommés comme " ${ARCH}Ops.go ", les règles d'optimisation sont placées dans " ${ARCH}.Rules ".

Les règles de haut niveau effectuent des transformations simples, la plupart du pliage d'expressions constantes , ainsi que certaines transformations qui simplifient le traitement ultérieur.

Chaque fichier avec des règles de bas niveau se compose de deux parties:

1. Abaissement - remplacement des opérations abstraites par des équivalents machine.
2. Les optimisations elles-mêmes.

Un exemple de réduction d'une opération à une machine:

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

C'est dans les optimisations de bas niveau que le nombre principal d'optimisations importantes est effectué, comme la réduction du coût des opérations , l'incorporation partielle et l'utilisation des capacités des modes d'adressage mémoire disponibles dans le processeur.

Les opérations ont un nom mnémonique, qui est généralement appelé opcode. Les opcodes des opérations dépendantes de l'architecture reflètent généralement les noms des instructions réelles.

Règle Description Syntaxe du langage

La grammaire de base est décrite dans 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  

Il convient également de mentionner que les commentaires " // " sont autorisés dans les fichiers .Rules .

Regardons un exemple simple qui contient tous ces éléments:

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

Toutes ces signatures explicatives ne font pas partie d'un enregistrement de règle valide.

Cette règle convertit x+0 en x . Tout ce qui se trouve dans la section conditions est un code Go normal,
sauf si limité à des expressions, dont le résultat devrait être un bool .
Vous pouvez appeler des prédicats définis dans rewrite.go .

En plus des opcodes habituels, des combinaisons peuvent être utilisées qui donnent lieu à plusieurs règles:

 (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) est l'une des opérations de genericOps.go et exprime le chargement d'un pointeur sur la pile matérielle. Pour les architectures où il n'y a pas de SP matériel, il est émulé.

Caractéristiques des variables dans les modèles (expressions S à gauche de -> ):

• Variables, telles que x , sans expression via:, capturer n'importe quoi
• comme une variable régulière, _ capture n'importe quelle valeur, mais le résultat peut être ignoré

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

Si AuxInt pas spécifié (expression entre crochets), la règle se déclenchera sur toute valeur AuxInt . De même avec les paramètres {} (à leur sujet ci-dessous).

Le nom v signifie la forme capturée la plus à l'extérieur.
Par exemple, pour l'expression (ADDQconst (SUBQconst x)) forme externe est ADDQconst .

Les variables peuvent être utilisées plusieurs fois, cela vous permet d'exiger que plusieurs parties de l'expression S se correspondent:

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

Types dans les règles

Dans certains cas, il est nécessaire d'indiquer explicitement le type de formulaire généré et / ou correspondant.
Le type est indiqué entre "crochets triangulaires", comme argument de type dans les modèles C ++:

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

En plus des types, il y a des "caractères" (ou, plus universellement - des propriétés Aux ).

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

• [argsWidth] - Value.AuxInt . Pour StaticCall - la taille totale des arguments passés
• {target} - Value.Aux . Pour StaticCall - fonction appelée
• <typ.UInt32> - Value.Type . Type de valeur

La sémantique d' Aux et AuxInt varie considérablement d'une opération à l'autre. La meilleure source de documentation dans ce cas est les fichiers *Ops.go Chaque opData opcode opData a un champ aux qui décrit comment interpréter ces champs.

Pour la description des types, le package cmd / compile / internal / types est utilisé . Certains types sont spécifiques au backend SSA, par exemple types.TypeFlags , les autres sont communs entre cmd/compile/internal/gc et cmd/compile/internal/ssa .

Types spéciaux

Il existe un type spécial de types.TypeMem , qui remplit plusieurs fonctions à la fois:

1. Vous permet de trier et de regrouper ssa.Value par modèles d'accès à la mémoire. En particulier, cela garantit le bon ordre d'exécution dans le cadre des blocs de base (à leur sujet ci-dessous).
2. Détermine l'état du flux mémoire dans le programme. Si l'instruction modifie la mémoire, une nouvelle valeur SSA de type types.TypeMem sera générée à la suite de cette opération.

Comme la signification spéciale d' OpPhi , la mémoire est interprétée exceptionnellement dans de nombreuses phases de l'optimiseur.

Un autre type spécial est les types.TypeFlags mentionnés ci-dessus. Ce type décrit l'instruction générant des drapeaux CPU .

Dans ce cas, les instructions comme ADDQ , bien qu'elles génèrent des indicateurs, ne sont pas de type types.Flags , mais sont marquées avec l'attribut clobberFlags .

types.Flags utilisé pour mettre en évidence le résultat d'instructions telles que CMPQ , qui n'écrivent le résultat dans aucun de leurs opérandes explicites, mais mettent uniquement à jour l'état interne du processeur, qui peut être utilisé par l'instruction suivante.

Des instructions comme SETL vous permettent de «lire» les drapeaux et de les renvoyer en tant que ssa.Value , qui peut être placé dans un registre.

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

Programme d'inspection SSA

Disons que nous avons un programme comme celui-ci ( example.go ):

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

Nous pouvons regarder le code SSA qui est généré pour la fonction fusedMulAdd :

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

Maintenant, vérifiez le répertoire de travail (actuel):

• ssa.txt contient un vidage tekt.
• ssa.html , qui est généré automatiquement, contient les mêmes informations, mais dans un format plus interactif et plus lisible. Essayez d'ouvrir dans un navigateur.

 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 

Voici à quoi ressemble le programme SSA pour fusedMulAdd après la phase 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) 

Traduire cela en expressions 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) 

Ajout de nouvelles règles d'optimisation

Sur les processeurs avec FMA, nous pouvons calculer a*c + b dans une instruction au lieu de deux.

Prenez CL117295 comme base de la paternité d' Ilya Tokar .

Pour votre commodité, j'ai préparé un patch diff .

1. Ajout d'une nouvelle opération - FMASD

Dans le fichier compile/internal/ssa/gen/AMD64Ops.go trouvez la AMD64ops tranche AMD64ops et ajoutez un nouvel élément (n'importe où):

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

Puisqu'il n'y avait pas d'opérations (fp,fp,fp -> fp) auparavant, vous devez définir un nouveau qualificatif:

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

2. Ajout d'une règle d'optimisation

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

Une mise en œuvre plus correcte ne serait pas inconditionnelle et vérifierait la disponibilité de FMA. Nous supposerons qu'il y a définitivement un FMA sur notre machine cible.

Le compilateur utilise config pour ces vérifications:

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

 $ lscpu | grep fma 

3. Mise en œuvre de la génération de code

Maintenant, dans la fonction ssaGenValue , définie dans le compile/internal/amd64/ssa.go , vous devez ajouter la génération de code pour 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. } } 

Maintenant, tout est prêt pour tester le travail de notre nouvelle optimisation. Il est très rare d'ajouter de nouvelles instructions, généralement de nouvelles optimisations sont effectuées sur la base d'opérations SSA déjà définies.

Vérification des résultats

La première étape consiste à générer du code Go à partir des gen/AMD64Ops.go et gen/AMD64.Rules .

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

Ensuite, nous devons construire notre nouveau compilateur:

 go install cmd/compile 

Maintenant, lors de la compilation du même exemple, nous obtenons un code machine différent:

 - 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 

Blocs de base

Maintenant que le travail le plus difficile a été fait, parlons des blocs de base .

Les valeurs que nous avons optimisées ci-dessus sont en blocs et les blocs sont en fonction.

Les blocs, comme ssa.Value , sont abstraits et dépendent de la machine. Tous les blocs ont exactement un point d'entrée et de 0 à 2 blocs de destination (selon le type de bloc).

Les blocs les plus simples sont If , Exit et Plain :

• Exit bloc de Exit a 0 bloc d'affectation. Ce sont des blocs feuilles qui effectuent un saut non local, par exemple en utilisant la panic .
• Plain bloc Plain a 1 blocs d'affectation. Il peut être considéré comme un saut inconditionnel après avoir terminé toutes les instructions du bloc vers un autre bloc.
• If bloc a 2 blocs de destination. La transition s'effectue en fonction de la condition ( Block.Control ).

Voici des exemples simples de réécriture de blocs abstraits en blocs AMD64 :

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

Le sujet des blocs sera examiné plus en détail dans le contexte d'autres phases d'optimisation dans la partie SSA du compilateur.

Limites des règles d'optimisation

Le backend SSA a ses avantages. Certaines optimisations sont réalisables dans O(1) . Cependant, il existe également des inconvénients en raison desquels le SSA de l'optimiseur seul ne sera pas suffisant, au moins jusqu'à ce que certains aspects de sa mise en œuvre changent.

Supposons que vous souhaitiez append :

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

Au moment où le SSA est généré, la structure de haut niveau du code est perdue et l' append , n'étant pas une fonction ordinaire, est déjà intégré dans le corps du bloc conteneur. Vous devrez écrire une règle lourde qui capture la séquence complète des opérations générées pour l' append .

En parlant spécifiquement de .Rules , ce DSL a un travail plutôt faible avec les blocs ( ssa.Block ). Toute optimisation non triviale associée aux blocs est impossible à exprimer dans ce langage. La mise à jour partielle des blocs n'est pas possible. Il est également impossible de jeter des blocs (mais il existe un hack sous la forme du First bloc, qui est utilisé pour supprimer le code mort).

Même si certaines des lacunes peuvent être corrigées, la plupart des compilateurs conviennent qu'il n'y a pas de forme intermédiaire unique et meilleure pour représenter le code.

Allez ça va plus vite

Si vous trouvez des règles d'optimisation intéressantes, n'hésitez pas à les envoyer à go-review.googlesource.com . Je serais heureux de revoir (ajouter à iskander.sharipov@intel.com dans CC).

Compilateur de piratage heureux!

Matériel bonus

Exemples de bons correctifs dans Go qui ont ajouté ou modifié des règles SSA:

• CL99656: cmd / compile / internal / ssa: émet IMUL3 {L / Q} pour MUL {L / Q} const sur x86
• CL102277: cmd / compile / internal / ssa: optimisez l'écart NEG double sur amd64
• CL54410: cmd / compile / internal / ssa: utilisez sse pour mettre à zéro sur amd64
• CL58090: cmd / compile / internal / ssa: suppression des extensions zéro redondantes sur amd64
• CL95475: cmd / compile / internal / ssa: combinez les magasins d'octets sur amd64
• CL97175: cmd / compile / internal / ssa: combinez les magasins LittleEndian consécutifs sur arm64
• CL115617: cmd / compile / internal / ssa: supprime l'extension zéro inutile
• CL101275: cmd / compile: ajoutez amd64 LEAL {1,2,4,8} ops

Il n'y a pas si longtemps, un document README semblait décrire la partie SSA du compilateur.
Lecture recommandée.