golang(cgo)コンパイラの共通部分式除去について
こんにちは、かずみんです。
golangの最適化パスを読んでいて、なんとなく、理解できたものを軽く紹介していくスタイル。連載するかどうかは、分からない。間違ってる部分とかあると、思います。
cgoってのは、golangコンパイラの一種です。何も考えずにインストールすると、大体これ使ってます。
共通部分式除去( Common subexpression elimination, CSE )は、コンパイラの最適化の一つで、同じ計算式が現れるところを 一つの変数に置き換えられるかを計算して、できるなら置き換えるもの。簡単に説明すると、同じ式を何回もやっちゃうと、時間がかかるので、計算しなくても、一度計算したものに置き換えようね。って感じ。
コードは、シンプルに理解するために、適宜削除しているコードなどがあります。完全版が見たければ、githubに行きましょう。
go/cse.go at master · golang/go · GitHub
zero CSEというパスもありますが、それは別になっています。
子の最適化パスが大まかにやっている処理としては、こんな感じ。
三つめが肝心なのだが、コードを見てくれ
以下のコードには、適宜コメントで説明している。
func cse(f *Func) { Valueポインタ型の配列をf.NumValues()個用意する。 a := make([]*Value, 0, f.NumValues()) //f.auxmapがnilだったら、f.auxmapを初期化してあげる。 if f.auxmap == nil { f.auxmap = auxmap{} } //TypeがMemoryではないすべてのValueを最初に用意したa変数に追加していく。 //その際に、一つ条件がある。 //auxmap[v.Aux]が0だったら、f.auxmap配列の長さに1を足したものをそれに入れる。 for _, b := range f.Blocks { for _, v := range b.Values { if v.Type.IsMemory() { continue // memory values can never cse } if f.auxmap[v.Aux] == 0 { f.auxmap[v.Aux] = int32(len(f.auxmap)) + 1 } a = append(a, v) } } //パーティションを計算する partition := partitionValues(a, f.auxmap) //パーティションからクラスに変換する。 //すべてのvalueをv.IDが添え字なvalueEqClassにidをマイナスにして、ストアする。 valueEqClass := make([]ID, f.NumValues()) for _, b := range f.Blocks { for _, v := range b.Values { // Use negative equivalence class #s for unique values. valueEqClass[v.ID] = -v.ID } } var pNum ID = 1 //パーティションのすべてのvalueにpNumを与える。 //大事なのは、みんなバラバラってところ。あとで、やるけど、肝心なのは、同じなら、という処理。 for _, e := range partition { for _, v := range e { valueEqClass[v.ID] = pNum } pNum++ } // // 等価クラスを、等価でない引数があるポイントで分割します。 分割が見つからないまで繰り返します。 var splitPoints []int byArgClass := new(partitionByArgClass) // reuseable partitionByArgClass to reduce allocations for { changed := false //パーティっしょん配列を先頭から走査。 for i := 0; i < len(partition); i++ { e := partition[i] if opcodeTable[e[0].Op].commutative { //比較の前に、二つの引数(Args)を並び替えます。 for _, v := range e { if valueEqClass[v.Args[0].ID] > valueEqClass[v.Args[1].ID] { v.Args[0], v.Args[1] = v.Args[1], v.Args[0] } } } // 頑張って、ソート。引数の eq クラスでソート byArgClass.a = e byArgClass.eqClass = valueEqClass sort.Sort(byArgClass) // 分割ポイントを見つける splitPoints = append(splitPoints[:0], 0) for j := 1; j < len(e); j++ { v, w := e[j-1], e[j] // Note: commutative args already correctly ordered by byArgClass. eqArgs := true for k, a := range v.Args { b := w.Args[k] if valueEqClass[a.ID] != valueEqClass[b.ID] { eqArgs = false break } } if !eqArgs { splitPoints = append(splitPoints, j) } } if len(splitPoints) == 1 { continue // no splits, leave equivalence class alone. } // e の代わりに別の等価クラスを下に移動します。 partition[i] = partition[len(partition)-1] partition = partition[:len(partition)-1] i-- // 見つけた e の部分に対して新しい等価クラスを追加します。 splitPoints = append(splitPoints, len(e)) for j := 0; j < len(splitPoints)-1; j++ { f := e[splitPoints[j]:splitPoints[j+1]] if len(f) == 1 { // Don't add singletons. valueEqClass[f[0].ID] = -f[0].ID continue } for _, v := range f { valueEqClass[v.ID] = pNum } pNum++ partition = append(partition, f) } changed = true } if !changed { break } } 厳密支配を手に入れる(strictly dominate) sdom := f.Sdom() // v と w が同じクラスにあり、v が w を支配する場合は、v を w に置き換えます。 rewrite := make([]*Value, f.NumValues()) byDom := new(partitionByDom) // reusable partitionByDom to reduce allocs for _, e := range partition { byDom.a = e byDom.sdom = sdom sort.Sort(byDom) for i := 0; i < len(e)-1; i++ { // eはドミネーターによりソートされているので、一番大きいドミネータ要素は、スライスの先頭にある。 v := e[i] e[i] = nil // メインの入れ替え作業 for j := i + 1; j < len(e); j++ { w := e[j] //vがwのアンセスターだったら、入れ替えをrewriteに記録。そうじゃなきゃforを抜け出す。 if sdom.IsAncestorEq(v.Block, w.Block) { rewrite[w.ID] = v e[j] = nil } else { // e is sorted by domorder, so v.Block doesn't dominate any subsequent blocks in e break } } } } rewrites := int64(0) // rewriteに記録していたものを実際に適用する。 for _, b := range f.Blocks { for _, v := range b.Values { for i, w := range v.Args { //変更したいのは、w.IDを添え字にしたrewrite配列に入ってるから、それを取り出して、 vのi番目にストア。 if x := rewrite[w.ID]; x != nil { v.SetArg(i, x) rewrites++ } } } //コントロールバリューってのも変えとかなくちゃいけない。 for i, v := range b.ControlValues() { if x := rewrite[v.ID]; x != nil { b.ReplaceControl(i, x) } } } }
今後
今後は、パスの一つ一つがどんなのか、軽く説明していきたい気持ちがある。専門的に知らなくても、日常的な言葉でわかるものが結構ある。
全然説明になってないじゃないか。と思う人もいるかもしれませんが、最適化に興味を持つ人がでてくると、幸いです。