KazuminEngine

プログラマーの日記

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