Der gc Compiler verwendet eine spezielle Lisp-ähnliche objektorientierte Sprache ( DSL ), um die SSA-Optimierungsregeln ( Static Single Assignment ) zu beschreiben.

Ich schlage vor, die Hauptelemente dieser Sprache, ihre Merkmale und Einschränkungen zu analysieren.
Als Übung fügen wir dem Go-Compiler die Generierung einer Anweisung hinzu, die zuvor nicht generiert wurde, und optimieren den Ausdruck a*b+c .

Dies ist der erste Artikel in einer Reihe über die Interna des Go SSA-Compiler-Backends. Daher werden wir nicht nur die Beschreibung der DSL-Regeln selbst überprüfen, sondern auch verwandte Komponenten untersuchen, um die erforderliche Basis für unsere nächste Sitzung zu schaffen.

Einführung

Der Frontend-Go-Compiler endet zum Zeitpunkt der Generierung der SSA-Ansicht aus dem mit Anmerkungen versehenen AST. Die für die Konvertierung verantwortlichen Funktionen finden Sie in cmd / compile / internal / gc / ssa.go. Der Einstiegspunkt in das SSA-Backend ist die Funktion ssa.Compile , die in cmd / compile / internal / ssa / compile.go definiert ist .

Der SSA Go-Optimierer besteht aus mehreren Phasen, von denen jede die kompilierte Funktion durchläuft. Einige Phasen verwenden die sogenannten "Umschreiberegeln", die Regeln zum Konvertieren einer SSA-Sequenz in eine andere, möglicherweise optimaler.

Transformationsregeln werden mit S-Ausdrücken beschrieben . Die Elemente dieser Ausdrücke sind ssa.Value . Im einfachsten Fall können Sie mit diesen Regeln einen ssa.Value durch einen anderen ersetzen.

Der folgende Code reduziert beispielsweise die Multiplikation von 8-Bit-Konstanten:

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

Es gibt zwei Hauptkategorien von SSA-Werten: High-Level, fast unabhängig vom Zielcomputer, und solche, die architekturspezifisch sind (normalerweise 1-in-1-Maschinenanweisungen zugeordnet).

Optimierungen werden anhand dieser beiden Kategorien beschrieben. Zuerst auf hoher Ebene und allen Architekturen gemeinsam, dann plattformorientiert.

Der gesamte mit den Regeln verknüpfte Code befindet sich in cmd / compile / internal / ssa / gen . Wir werden zwei Sätze betrachten:

1. genericOps.go - maschinenunabhängige Operationen.
2. AMD64Ops.go - Vorgänge, die für GOARCH=AMD64 (64-Bit x86) spezifisch sind.

Nach den ersten Phasen, die auf der abstrakten Maschine arbeiten, wird das sogenannte Absenken durchgeführt, was zu einem Übergang von genericOps zu einer Reihe spezifischer Architekturen führt. In unserem Beispiel ist dies AMD64Ops . Nach diesem Punkt bearbeiten alle nachfolgenden Phasen die Präsentation aus der zweiten Kategorie.

Nach dem Optimierer kommt ein Codegenerator ins Spiel. Für AMD64 befindet sich die Implementierung der Codegenerierung im Paket cmd / compile / internal / amd64 . Die Aufgabe des Codegenerators besteht darin, ssa.Block und ssa.Value durch die an den Assembler übergebene Sequenz obj.Prog zu ersetzen. Der Assembler sammelt den Maschinencode, der nach dem Verknüpfen zur Ausführung bereit ist.

Optimierungsregeln

Wenn Dateien mit Operationsdefinitionen den Namen " ${ARCH}Ops.go " haben, werden Optimierungsregeln in " ${ARCH}.Rules " platziert.

Übergeordnete Regeln führen einfache Transformationen durch, wobei die meisten konstanten Ausdrücke gefaltet werden , sowie einige Transformationen, die die nachfolgende Verarbeitung vereinfachen.

Jede Datei mit Regeln auf niedriger Ebene besteht aus zwei Teilen:

1. Absenken - Ersetzen abstrakter Operationen durch Maschinenäquivalente.
2. Die Optimierungen selbst.

Ein Beispiel für die Reduzierung eines Vorgangs auf eine Maschine:

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

Bei Optimierungen auf niedriger Ebene wird die Hauptanzahl wichtiger Optimierungen durchgeführt, z. B. die Reduzierung der Betriebskosten , die teilweise Einbettung und Nutzung der Funktionen der im Prozessor verfügbaren Speicheradressierungsmodi .

Operationen haben einen mnemonischen Namen, der normalerweise als Opcode bezeichnet wird. Die Opcodes von architekturabhängigen Operationen spiegeln normalerweise die Namen der tatsächlichen Anweisungen wider.

Regel Beschreibung Sprachsyntax

Die grundlegende Grammatik ist in rulegen.go beschrieben :

 // 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  

Erwähnenswert ist auch, dass " // " -Kommentare in .Rules Dateien zulässig sind.

Schauen wir uns ein einfaches Beispiel an, das all diese Elemente enthält:

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

Alle diese erklärenden Signaturen sind nicht Teil eines gültigen Regeldatensatzes.

Diese Regel konvertiert x+0 in x . Alles im Bedingungsabschnitt ist ein normaler Go-Code.
sofern nicht auf Ausdrücke beschränkt, deren Ergebnis ein bool .
Sie können in rewrite.go definierte Prädikate aufrufen .

Zusätzlich zu den üblichen Opcodes können Kombinationen verwendet werden, die zu mehreren Regeln führen:

 (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) ist eine der Operationen in genericOps.go und drückt das Laden eines Zeigers auf den Hardware-Stack aus. Für Architekturen ohne Hardware- SP wird es emuliert.

Funktionen von Variablen in Vorlagen (S-Ausdrücke links von -> ):

• Variablen wie x ohne Ausdruck durch : erfassen alles
• Wie eine reguläre Variable erfasst _ beliebigen Wert, das Ergebnis kann jedoch ignoriert werden

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

Wenn AuxInt nicht angegeben ist (Ausdruck in eckigen Klammern), wird die Regel für jeden AuxInt Wert AuxInt . Ähnliches gilt für {} -Parameter (dazu unten).

Der Name v bedeutet die äußerste erfasste Form.
Für den Ausdruck (ADDQconst (SUBQconst x)) lautet (ADDQconst (SUBQconst x)) externe Form beispielsweise ADDQconst .

Variablen können mehrmals verwendet werden. Auf diese Weise können Sie festlegen, dass mehrere Teile des S-Ausdrucks miteinander übereinstimmen:

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

Typen in Regeln

In einigen Fällen muss der Typ des generierten und / oder übereinstimmenden Formulars explizit angegeben werden.
Der Typ wird in "dreieckigen Klammern" als Typargument in C ++ - Vorlagen angegeben:

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

Zusätzlich zu den Typen gibt es "Zeichen" (oder allgemeiner - Aux Eigenschaften).

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

• [argsWidth] - Value.AuxInt . Für StaticCall - die Gesamtgröße der übergebenen Argumente
• {target} - Value.Aux . Für StaticCall - aufgerufene Funktion
• <typ.UInt32> - Value.Type . Werttyp

Die Semantik von Aux und AuxInt von Operation zu Operation sehr unterschiedlich. Die beste Dokumentationsquelle in diesem Fall sind *Ops.go Dateien. Jede opData-Opcode- opData verfügt über ein Hilfsfeld, in dem die Interpretation dieser Felder beschrieben wird.

Für die Beschreibung der Typen wird das Paket cmd / compile / internal / types verwendet . Einige Typen sind spezifisch für das SSA-Backend, z. B. types.TypeFlags , der Rest ist zwischen cmd/compile/internal/gc und cmd/compile/internal/ssa .

Spezielle Typen

Es gibt einen speziellen Typ von types.TypeMem , der mehrere Funktionen gleichzeitig ausführt:

1. Ermöglicht das Sortieren und Gruppieren von ssa.Value nach Speicherzugriffsmustern. Dies garantiert insbesondere die korrekte Ausführungsreihenfolge im Rahmen der Basisblöcke (dazu unten).
2. Bestimmt den Status des Speicherstroms im Programm. Wenn der Befehl den Speicher types.TypeMem wird als Ergebnis dieser Operation ein neuer SSA-Wert vom Typ types.TypeMem generiert.

Wie die spezielle Bedeutung von OpPhi wird der Speicher in vielen Phasen des Optimierers außergewöhnlich interpretiert.

Ein weiterer spezieller Typ sind die types.TypeFlags genannten types.TypeFlags . Dieser Typ beschreibt den Befehl, der CPU-Flags generiert.

In diesem Fall sind Anweisungen wie ADDQ , obwohl sie Flags generieren, nicht vom Typ types.Flags , sondern mit dem Attribut clobberFlags .

types.Flags verwendet, um das Ergebnis von Anweisungen wie CMPQ , die das Ergebnis nicht in einen ihrer expliziten Operanden schreiben, sondern nur den internen Status des Prozessors aktualisieren, der von der nächsten Anweisung verwendet werden kann.

Mit Anweisungen wie SETL können Sie Flags „lesen“ und als ssa.Value , der in ein Register gestellt werden kann.

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

SSA-Inspektionsprogramm

Nehmen wir an, wir haben ein Programm wie dieses ( example.go ):

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

Wir können uns den SSA-Code ansehen, der für die Funktion fusedMulAdd generiert wird:

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

Überprüfen Sie nun das Arbeitsverzeichnis (aktuell):

• ssa.txt enthält einen Tekt-Dump.
• ssa.html , das automatisch generiert wird, enthält dieselben Informationen, jedoch in einem interaktiveren und bequem lesbaren Format. Versuchen Sie, in einem Browser zu öffnen.

 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 

So sieht das SSA-Programm für fusedMulAdd nach der lower Phase aus (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) 

Dies in S-Ausdrücke übersetzen:

 (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) 

Hinzufügen neuer Optimierungsregeln

Auf Prozessoren mit FMA können wir a*c + b in einem Befehl anstelle von zwei berechnen.

Nehmen Sie CL117295 als Grundlage für die Urheberschaft von Ilya Tokar .

Für Ihre Bequemlichkeit habe ich einen diff Patch vorbereitet.

1. Hinzufügen einer neuen Operation - FMASD

compile/internal/ssa/gen/AMD64Ops.go Sie in der Datei compile/internal/ssa/gen/AMD64Ops.go die Slice- AMD64ops und fügen Sie ein neues Element hinzu (irgendwo):

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

Da zuvor keine Operationen (fp,fp,fp -> fp) waren, müssen Sie ein neues Qualifikationsmerkmal definieren:

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

2. Hinzufügen einer Optimierungsregel

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

Eine korrektere Implementierung wäre nicht unbedingt erforderlich und würde die Verfügbarkeit von FMA prüfen. Wir gehen davon aus, dass auf unserer Zielmaschine definitiv eine FMA vorhanden ist.

Der Compiler verwendet config für solche Überprüfungen:

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

 $ lscpu | grep fma 

3. Implementierung der Codegenerierung

In der Funktion ssaGenValue , die in der compile/internal/amd64/ssa.go , müssen Sie nun die Codegenerierung für 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. } } 

Jetzt ist alles bereit, um die Arbeit unserer neuen Optimierung zu testen. Es ist sehr selten, dass neue Anweisungen hinzugefügt werden. In der Regel werden neue Optimierungen basierend auf bereits definierten SSA-Vorgängen durchgeführt.

Ergebnisse überprüfen

Der erste Schritt besteht darin, Go-Code aus den aktualisierten gen/AMD64Ops.go und gen/AMD64.Rules .

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

Als nächstes müssen wir unseren neuen Compiler erstellen:

 go install cmd/compile 

Wenn wir nun dasselbe Beispiel kompilieren, erhalten wir einen anderen Maschinencode:

 - 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 

Grundblöcke

Nachdem die schwierigste Arbeit erledigt wurde, sprechen wir über die Basisblöcke .

Die oben optimierten Werte sind in Blöcken angegeben, und die Blöcke sind in Funktion.

Blöcke sind wie ssa.Value abstrakt und maschinenabhängig. Alle Blöcke haben genau einen Einstiegspunkt und 0 bis 2 Zielblöcke (je nach Blocktyp).

Die einfachsten Blöcke sind If , Exit und Plain :

• Exit hat 0 Zuweisungsblöcke. Dies sind Blattblöcke, die beispielsweise mit panic einen nicht lokalen Sprung panic .
• Plain Block hat 1 Zuweisungsblöcke. Es kann als bedingungsloser Sprung betrachtet werden, nachdem alle Anweisungen des Blocks zu einem anderen Block ausgeführt wurden.
• If Block 2 Zielblöcke hat. Der Übergang erfolgt je nach Bedingung ( Block.Control ).

Hier sind einfache Beispiele für das Umschreiben abstrakter Blöcke in AMD64 Blöcke:

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

Das Thema Blöcke wird im Zusammenhang mit anderen Optimierungsphasen im SSA-Teil des Compilers näher betrachtet.

Einschränkungen der Optimierungsregeln

Das SSA-Backend hat seine Vorteile. Einige Optimierungen sind in O(1) . Es gibt jedoch auch Nachteile, aufgrund derer die SSA des Optimierers allein nicht ausreicht, zumindest bis sich einige Aspekte seiner Implementierung ändern.

Angenommen, Sie möchten append :

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

Zum Zeitpunkt der Generierung des SSA geht die übergeordnete Struktur des Codes verloren und das append , da es keine gewöhnliche Funktion ist, bereits in den Hauptteil des enthaltenen Blocks integriert. Sie müssen eine umständliche Regel schreiben, die die gesamte Abfolge der zum append generierten Vorgänge erfasst.

Apropos .Rules , dann hat dieses DSL eher schwache Arbeit mit Blöcken ( ssa.Block ). Eine nicht triviale Optimierung, die mit Blöcken verbunden ist, kann in dieser Sprache nicht ausgedrückt werden. Eine teilweise Blockaktualisierung ist nicht möglich. Es ist auch unmöglich, Blöcke wegzuwerfen (aber es gibt einen Hack in Form des First Blocks, mit dem toter Code gelöscht wird).

Selbst wenn einige der Mängel behoben werden können, stimmen die meisten Compiler darin überein, dass es keine einzige und bessere Zwischenform für die Darstellung des Codes gibt.

Geh das geht schneller

Wenn Sie coole Optimierungsregeln haben, senden Sie diese bitte an go-review.googlesource.com . Ich würde gerne eine Bewertung iskander.sharipov@intel.com (zu iskander.sharipov@intel.com in CC hinzufügen).

Viel Spaß beim Hacking Compiler!

Bonusmaterial

Beispiele für gute Patches in Go, die SSA-Regeln hinzugefügt oder geändert haben:

• CL99656: cmd / compile / internal / ssa: IMUL3 {L / Q} für MUL {L / Q} const auf x86 ausgeben
• CL102277: cmd / compile / internal / ssa: Optimiere das doppelte NEG auf amd64
• CL54410: cmd / compile / internal / ssa: Verwenden Sie sse auf amd64 auf Null
• CL58090: cmd / compile / internal / ssa: Entfernen Sie redundante Null-Erweiterungen auf amd64
• CL95475: cmd / compile / internal / ssa: Bytespeicher auf amd64 kombinieren
• CL97175: cmd / compile / internal / ssa: Kombinieren Sie aufeinanderfolgende LittleEndian-Speicher auf arm64
• CL115617: cmd / compile / internal / ssa: Entfernen Sie die nutzlose Null-Erweiterung
• CL101275: cmd / compile: füge amd64 LEAL {1,2,4,8} ops hinzu

Vor nicht allzu langer Zeit erschien ein README- Dokument, das den SSA-Teil des Compilers beschreibt.
Empfohlene Lektüre.