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)
}
}
}
}
今後
今後は、パスの一つ一つがどんなのか、軽く説明していきたい気持ちがある。専門的に知らなくても、日常的な言葉でわかるものが結構ある。
全然説明になってないじゃないか。と思う人もいるかもしれませんが、最適化に興味を持つ人がでてくると、幸いです。
