golangコンパイラ(cgo)のスケジューリングパスについて
こんにちは かずみんです。
今回は、golangコンパイラ(cgo)の最適化パスの一つ、スケジューリングを軽く説明します。
go/schedule.go at dev.boringcrypto.go1.8 · golang/go · GitHub
筆者の言っていることは間違っているかもしれませんので、悪しからず。
スケジューリングの最適化パスは、cpuがパイプラインしやすいように、コンパイラ側で実行順序を変更してあげる最適化です。
パイプラインのデータハザードや構造ハザードに対処する感じだと思います。
どういった順序に直してあげればいいのかは、以下のconstに書かれています。 phi関数はブロックの一番上で実行しないといけないから、一番上、という感じです。 どこに分岐したらいいのかを最後に決めたいので、ScoreControlは最後になっています。
以下のコードのはじめのrangeで、このOpのValueのidは、この順位と振り分けていっています。
その次のブロックでSelectXで、tupleになんやかんややっていますが、これはmipsだけなので、あまり気にしなくてよくて、その下のdefaultだけを着目すればよく、シンプルにconstの順に並べていっている感じだと思います。
スケジューリングパスは、こんな感じで終わり。
ハザードの対応は、この後に機械語の命令に変換するときに、データハザードなどに対応しているんじゃないかな?と思います。
そこでスーパースカラやVLIWのための処理をしているのではないか?と予測します。
また、今後読んでいきたいです。
const ( ScorePhi = iota // towards top of block ScoreArg ScoreNilCheck ScoreReadTuple ScoreVarDef ScoreMemory ScoreReadFlags ScoreDefault ScoreFlags ScoreControl // towards bottom of block ) func schedule(f *Func) { . . . for _, b := range f.Blocks { // Compute score. Larger numbers are scheduled closer to the end of the block. for _, v := range b.Values { switch { case v.Op.isLoweredGetClosurePtr(): // We also score GetLoweredClosurePtr as early as possible to ensure that the // context register is not stomped. GetLoweredClosurePtr should only appear // in the entry block where there are no phi functions, so there is no // conflict or ambiguity here. if b != f.Entry { f.Fatalf("LoweredGetClosurePtr appeared outside of entry block, b=%s", b.String()) } score[v.ID] = ScorePhi case v.Op == OpAMD64LoweredNilCheck || v.Op == OpPPC64LoweredNilCheck || v.Op == OpARMLoweredNilCheck || v.Op == OpARM64LoweredNilCheck || v.Op == Op386LoweredNilCheck || v.Op == OpMIPS64LoweredNilCheck || v.Op == OpS390XLoweredNilCheck || v.Op == OpMIPSLoweredNilCheck || v.Op == OpRISCV64LoweredNilCheck || v.Op == OpWasmLoweredNilCheck: // Nil checks must come before loads from the same address. score[v.ID] = ScoreNilCheck case v.Op == OpPhi: // We want all the phis first. score[v.ID] = ScorePhi case v.Op == OpVarDef: // We want all the vardefs next. score[v.ID] = ScoreVarDef case v.Op == OpArgIntReg || v.Op == OpArgFloatReg: // In-register args must be scheduled as early as possible to ensure that the // context register is not stomped. They should only appear in the entry block. if b != f.Entry { f.Fatalf("%s appeared outside of entry block, b=%s", v.Op, b.String()) } score[v.ID] = ScorePhi case v.Op == OpArg: // We want all the args as early as possible, for better debugging. score[v.ID] = ScoreArg case v.Type.IsMemory(): // Schedule stores as early as possible. This tends to // reduce register pressure. It also helps make sure // VARDEF ops are scheduled before the corresponding LEA. score[v.ID] = ScoreMemory case v.Op == OpSelect0 || v.Op == OpSelect1 || v.Op == OpSelectN: // Schedule the pseudo-op of reading part of a tuple // immediately after the tuple-generating op, since // this value is already live. This also removes its // false dependency on the other part of the tuple. // Also ensures tuple is never spilled. score[v.ID] = ScoreReadTuple case v.Type.IsFlags() || v.Type.IsTuple() && v.Type.FieldType(1).IsFlags(): // Schedule flag register generation as late as possible. // This makes sure that we only have one live flags // value at a time. score[v.ID] = ScoreFlags default: score[v.ID] = ScoreDefault // If we're reading flags, schedule earlier to keep flag lifetime short. for _, a := range v.Args { if a.Type.IsFlags() { score[v.ID] = ScoreReadFlags } } } } } . . . for priq.Len() > 0 { // Find highest priority schedulable value. // Note that schedule is assembled backwards. v := heap.Pop(priq).(*Value) // Add it to the schedule. // Do not emit tuple-reading ops until we're ready to emit the tuple-generating op. //TODO: maybe remove ReadTuple score above, if it does not help on performance switch { case v.Op == OpSelect0: if tuples[v.Args[0].ID] == nil { tuples[v.Args[0].ID] = make([]*Value, 2) } tuples[v.Args[0].ID][0] = v case v.Op == OpSelect1: if tuples[v.Args[0].ID] == nil { tuples[v.Args[0].ID] = make([]*Value, 2) } tuples[v.Args[0].ID][1] = v case v.Op == OpSelectN: if tuples[v.Args[0].ID] == nil { tuples[v.Args[0].ID] = make([]*Value, v.Args[0].Type.NumFields()) } tuples[v.Args[0].ID][v.AuxInt] = v case v.Type.IsResults() && tuples[v.ID] != nil: tup := tuples[v.ID] for i := len(tup) - 1; i >= 0; i-- { if tup[i] != nil { order = append(order, tup[i]) } } delete(tuples, v.ID) order = append(order, v) case v.Type.IsTuple() && tuples[v.ID] != nil: if tuples[v.ID][1] != nil { order = append(order, tuples[v.ID][1]) } if tuples[v.ID][0] != nil { order = append(order, tuples[v.ID][0]) } delete(tuples, v.ID) fallthrough default: order = append(order, v) } // Update use counts of arguments. for _, w := range v.Args { if w.Block != b { continue } uses[w.ID]-- if uses[w.ID] == 0 { // All uses scheduled, w is now schedulable. heap.Push(priq, w) } } for _, w := range additionalArgs[v.ID] { uses[w.ID]-- if uses[w.ID] == 0 { // All uses scheduled, w is now schedulable. heap.Push(priq, w) } } }