Kompilator gc menggunakan bahasa berorientasi objek khusus ( DSL ) mirip Lisp untuk menggambarkan aturan optimasi Tugas Tunggal Statis (SSA).

Saya mengusulkan untuk menganalisis elemen-elemen utama dari bahasa ini, fitur-fiturnya dan keterbatasannya.
Sebagai latihan, mari kita tambahkan ke kompiler Go generasi instruksi yang sebelumnya tidak dihasilkan, mengoptimalkan ekspresi a*b+c .

Ini adalah artikel pertama dalam seri tentang internal backend kompiler Go SSA , oleh karena itu, selain meninjau deskripsi DSL dari aturan itu sendiri, kami akan mempertimbangkan komponen terkait untuk membuat basis yang diperlukan untuk sesi berikutnya.

Pendahuluan

Compiler frontend go berakhir pada saat menghasilkan tampilan SSA dari AST beranotasi. Fungsi yang bertanggung jawab untuk konversi dapat ditemukan di cmd / compile / internal / gc / ssa.go. Titik masuk ke backend SSA adalah fungsi ssa.Compile , didefinisikan dalam cmd / compile / internal / ssa / compile.go .

Pengoptimal SSA Go terdiri dari beberapa fase, yang masing-masing melewati fungsi yang dikompilasi. Beberapa fase menggunakan apa yang disebut "aturan penulisan ulang", aturan untuk mengubah satu urutan SSA ke yang lain, berpotensi lebih optimal.

Aturan transformasi dijelaskan menggunakan S-expressions . Elemen dari ekspresi ini adalah ssa.Value . Dalam kasus paling sederhana, aturan-aturan ini memungkinkan Anda untuk mengganti satu ssa.Value dengan yang lain.

Sebagai contoh, kode di bawah ini mengalikan perkalian konstanta 8-bit:

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

Ada dua kategori utama nilai SSA: tingkat tinggi, hampir tidak tergantung pada mesin target, dan yang spesifik arsitektur (biasanya dipetakan ke instruksi mesin 1-in-1).

Optimalisasi dijelaskan dalam dua kategori ini. Pertama, tingkat tinggi dan umum untuk semua arsitektur, kemudian berorientasi platform.

Semua kode yang terkait dengan aturan terletak pada cmd / compile / internal / ssa / gen . Kami akan mempertimbangkan dua set:

1. genericOps.go - operasi independen-mesin.
2. AMD64Ops.go - operasi khusus untuk GOARCH=AMD64 (64-bit x86).

Setelah beberapa fase pertama yang bekerja pada mesin abstrak, yang disebut penurunan dilakukan, yang menghasilkan transisi dari genericOps ke seperangkat arsitektur tertentu. Dalam contoh kita, ini akan menjadi AMD64Ops . Setelah titik ini, semua fase berikutnya beroperasi pada presentasi dari kategori kedua.

Setelah optimizer, generator kode mulai berlaku. Untuk AMD64, implementasi pembuatan kode dapat ditemukan dalam paket cmd / compile / internal / amd64 . Tugas pembuat kode adalah mengganti ssa.Block dan ssa.Value dengan urutan obj.Prog diteruskan ke assembler . Assembler akan mengumpulkan kode mesin, yang akan siap untuk dieksekusi setelah menautkan .

Aturan Optimasi

Jika file dengan definisi operasi diberi nama seperti " ${ARCH}Ops.go ", maka aturan optimasi ditempatkan di " ${ARCH}.Rules ".

Aturan tingkat tinggi melakukan transformasi sederhana, sebagian besar lipatan ekspresi konstan , serta beberapa transformasi yang menyederhanakan proses selanjutnya.

Setiap file dengan aturan level rendah terdiri dari dua bagian:

1. Menurunkan - mengganti operasi abstrak dengan setara mesin.
2. Optimalisasi sendiri.

Contoh mengurangi operasi ke mesin:

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

Dalam optimalisasi tingkat rendah, sejumlah utama optimasi penting dilakukan, seperti mengurangi biaya operasi , menanamkan sebagian dan memanfaatkan kemampuan mode pengalamatan memori yang tersedia di prosesor.

Operasi memiliki nama mnemonik, yang biasanya disebut opcode. Opcode dari operasi yang bergantung pada arsitektur biasanya mencerminkan nama instruksi yang sebenarnya.

Aturan Deskripsi Sintaks Bahasa

Tata bahasa dasar dijelaskan dalam 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  

Perlu disebutkan juga bahwa komentar " // " diperbolehkan di dalam file .Rules .

Mari kita lihat contoh sederhana yang berisi semua elemen ini:

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

Semua tanda tangan penjelasan ini bukan bagian dari catatan aturan yang valid.

Aturan ini mengonversi x+0 ke x . Segala sesuatu di dalam bagian ketentuan adalah kode Go normal,
kecuali terbatas pada ekspresi, yang hasilnya harus bool .
Anda dapat memanggil predikat yang ditentukan dalam rewrite.go .

Selain opcode biasa, kombinasi dapat digunakan yang menimbulkan beberapa aturan:

 (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) adalah salah satu operasi di genericOps.go dan menyatakan memuat pointer ke tumpukan perangkat keras. Untuk arsitektur di mana tidak ada perangkat keras SP , itu ditiru.

Fitur variabel dalam templat (ekspresi S di sebelah kiri -> ):

• Variabel, seperti x , tanpa ekspresi melalui:, menangkap apa pun
• seperti variabel biasa, _ menangkap nilai apa pun, tetapi hasilnya dapat diabaikan

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

Jika AuxInt tidak ditentukan (ekspresi dalam kurung siku), maka aturan akan AuxInt nilai AuxInt apa pun. Demikian pula dengan {} -parameters (tentangnya di bawah).

Nama v berarti bentuk tangkapan terluar.
Misalnya, untuk ekspresi (ADDQconst (SUBQconst x)) bentuk eksternal adalah ADDQconst .

Variabel dapat digunakan beberapa kali, ini memungkinkan Anda untuk mengharuskan beberapa bagian ekspresi-S cocok satu sama lain:

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

Jenis dalam Aturan

Dalam beberapa kasus, diperlukan untuk secara eksplisit menunjukkan jenis yang dihasilkan dan / atau formulir yang cocok.
Tipe ditunjukkan dalam "kurung segitiga", sebagai argumen tipe dalam templat C ++:

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

Selain tipe, ada "karakter" (atau, lebih universal - properti Aux ).

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

• [argsWidth] - Value.AuxInt . Untuk StaticCall - ukuran total argumen yang diteruskan
• {target} - Value.Aux . Untuk fungsi StaticCall - disebut
• <typ.UInt32> - Value.Type . Jenis nilai

Semantik Aux dan AuxInt sangat bervariasi dari operasi ke operasi. Sumber dokumentasi terbaik dalam hal ini adalah file *Ops.go Setiap opData opcode opData memiliki bidang isian yang menjelaskan bagaimana menafsirkan bidang ini.

Untuk deskripsi tipe paket cmd / compile / internal / types digunakan . Beberapa tipe khusus untuk backend SSA, misalnya types.TypeFlags , sisanya umum antara cmd/compile/internal/gc dan cmd/compile/internal/ssa .

Jenis khusus

Ada jenis tipe khusus. types.TypeMem yang melakukan beberapa fungsi sekaligus:

1. Memungkinkan Anda mengurutkan dan mengelompokkan ssa.Value berdasarkan pola akses memori. Secara khusus, ini menjamin urutan eksekusi yang benar dalam kerangka blok dasar (tentangnya di bawah).
2. Menentukan status aliran memori dalam program. Jika instruksi mengubah memori, nilai SSA baru dari jenis tipe. types.TypeMem akan dihasilkan sebagai hasil dari operasi ini.

Seperti makna khusus OpPhi , memori ditafsirkan secara luar biasa dalam banyak fase pengoptimal.

Tipe khusus lainnya adalah types.TypeFlags disebutkan di atas. Tipe ini menjelaskan instruksi yang menghasilkan flag CPU .

Dalam kasus ini, instruksi seperti ADDQ , meskipun mereka menghasilkan flag, bukan tipe types.Flags . types.Flags , tetapi ditandai dengan atribut clobberFlags .

types.Flags digunakan untuk menyorot hasil instruksi seperti CMPQ , yang tidak menulis hasilnya ke salah satu operand eksplisit mereka, tetapi hanya memperbarui keadaan internal prosesor, yang dapat digunakan oleh instruksi berikutnya.

Instruksi seperti SETL memungkinkan Anda untuk "membaca" flag dan mengembalikannya sebagai ssa.Value , yang dapat ditempatkan dalam register.

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

Program inspeksi SSA

Katakanlah kita memiliki program seperti ini ( example.go ):

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

Kita dapat melihat kode SSA yang dihasilkan untuk fungsi fusedMulAdd :

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

Sekarang periksa direktori kerja (saat ini):

• ssa.txt berisi dump tekt.
• ssa.html , yang dihasilkan secara otomatis, berisi informasi yang sama, tetapi dalam format yang lebih interaktif dan mudah dibaca. Coba buka di browser.

 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 

Seperti inilah tampilan program SSA untuk fusedMulAdd setelah 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) 

Menerjemahkan ini ke dalam ekspresi-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) 

Menambahkan Aturan Optimasi Baru

Pada prosesor dengan FMA, kita dapat menghitung a*c + b dalam satu instruksi, bukan dua.

Ambil CL117295 sebagai dasar kepengarangan Ilya Tokar .

Untuk kenyamanan Anda, saya telah menyiapkan patch diff .

1. Menambahkan operasi baru - FMASD

Dalam compile/internal/ssa/gen/AMD64Ops.go file compile/internal/ssa/gen/AMD64Ops.go temukan AMD64ops slice AMD64ops dan tambahkan elemen baru (di mana saja):

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

Karena tidak ada operasi (fp,fp,fp -> fp) sebelumnya, Anda perlu mendefinisikan kualifikasi baru:

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

2. Menambahkan aturan optimasi

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

Implementasi yang lebih benar tidak akan tanpa syarat dan akan memeriksa ketersediaan FMA. Kami akan berasumsi bahwa pasti ada FMA di mesin target kami.

Kompiler menggunakan config untuk pemeriksaan tersebut:

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

 $ lscpu | grep fma 

3. Implementasi pembuatan kode

Sekarang, dalam fungsi ssaGenValue , didefinisikan dalam file compile/internal/amd64/ssa.go , Anda perlu menambahkan pembuatan kode untuk 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. } } 

Sekarang semuanya siap untuk menguji karya optimasi baru kami. Sangat jarang menambahkan instruksi baru, biasanya optimasi baru dilakukan berdasarkan operasi SSA yang sudah ditentukan.

Memeriksa Hasil

Langkah pertama adalah membuat kode Go dari gen/AMD64Ops.go diperbarui gen/AMD64Ops.go dan gen/AMD64.Rules .

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

Selanjutnya, kita perlu membangun kompiler baru kita:

 go install cmd/compile 

Sekarang, ketika mengkompilasi contoh yang sama, kami mendapatkan kode mesin yang berbeda:

 - 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 

Blok dasar

Sekarang setelah pekerjaan yang paling sulit telah dilakukan, mari kita bicara tentang blok dasar .

Nilai yang kami optimalkan di atas adalah dalam blok, dan blok dalam fungsi.

Blok, seperti ssa.Value , abstrak dan bergantung pada mesin. Semua blok memiliki tepat satu titik masuk dan dari 0 hingga 2 blok tujuan (tergantung pada jenis blok).

Blok paling sederhana adalah If , Exit dan Plain :

• Blok Exit memiliki 0 blok tugas. Ini adalah blok daun yang membuat lompatan non-lokal, misalnya, menggunakan panic .
• Blok Plain memiliki 1 blok tugas. Ini dapat dianggap sebagai lompatan tanpa syarat setelah menyelesaikan semua instruksi blok ke blok lain.
• If blok memiliki 2 blok tujuan. Transisi dilakukan tergantung pada kondisinya ( Block.Control ).

Berikut adalah contoh sederhana penulisan ulang blok abstrak menjadi blok AMD64 :

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

Topik blok akan dipertimbangkan secara lebih rinci dalam konteks fase optimisasi lainnya di bagian SSA dari kompiler.

Keterbatasan Aturan Optimasi

Backend SSA memiliki kelebihan. Beberapa optimasi layak dilakukan di O(1) . Namun, ada juga kelemahan karena SSA dari optimizer saja tidak akan cukup, setidaknya sampai beberapa aspek perubahan implementasinya.

Misalkan Anda ingin append :

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

Pada saat SSA dihasilkan, struktur kode tingkat tinggi hilang dan append , karena bukan fungsi biasa, sudah dibangun ke dalam tubuh blok yang berisi. Anda harus menulis aturan rumit yang menangkap seluruh urutan operasi yang dihasilkan untuk append .

Berbicara secara khusus tentang. .Rules , maka DSL ini memiliki kerja yang agak lemah dengan blok ( ssa.Block ). Optimalisasi nontrivial apa pun yang terkait dengan blok tidak mungkin diungkapkan dalam bahasa ini. Pembaruan blok sebagian tidak dimungkinkan. Juga tidak mungkin untuk membuang blok (tetapi ada hack dalam bentuk blok First , yang digunakan untuk menghapus kode mati).

Bahkan jika beberapa kekurangan dapat diperbaiki, sebagian besar penyusun setuju bahwa tidak ada bentuk peralihan yang lebih baik untuk mewakili kode.

Lakukan lebih cepat

Jika Anda membuat beberapa aturan optimasi yang keren, silakan kirim ke go-review.googlesource.com . Saya akan senang untuk meninjau (tambahkan ke iskander.sharipov@intel.com di CC).

Selamat kompiler peretasan!

Bahan Bonus

Contoh tambalan yang baik di Go yang menambah atau mengubah aturan SSA:

• CL99656: cmd / compile / internal / ssa: emit IMUL3 {L / Q} untuk MUL {L / Q} const pada x86
• CL102277: cmd / compile / internal / ssa: optimalkan NEG ganda pada amd64
• CL54410: cmd / compile / internal / ssa: gunakan sse to zero pada amd64
• CL58090: cmd / compile / internal / ssa: hapus redextant zeroextensions pada amd64
• CL95475: cmd / compile / internal / ssa: gabungkan toko byte di amd64
• CL97175: cmd / compile / internal / ssa: gabungkan toko LittleEndian berturut-turut di arm64
• CL115617: cmd / compile / internal / ssa: hapus ekstensi nol yang tidak berguna
• CL101275: cmd / compile: tambahkan amd64 LEAL {1,2,4,8} ops

Belum lama ini, dokumen README muncul untuk menggambarkan bagian SSA dari kompiler.
Bacaan yang disarankan.