Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

[インデックス 18538] ファイルの概要

このコミットは、Goコンパイラ（cmd/gc）における「fat variables」（複数ワードで構成される変数、例えば構造体や配列、スライスなど）のライブネス解析の正確性を向上させることを目的としています。具体的には、VARDEF（Variable Definition）命令の配置を修正し、変数の初期化と使用の順序に関するライブネス解析の誤解を解消します。また、ライブネス解析の新たなチェックを有効にし、既存のバグ（特にレース検出器が生成するコードにおける問題）を特定・修正します。

コミット

commit 7a7c0ffb478847a0711f6b829a615ef4eea5dc67
Author: Russ Cox <rsc@golang.org>
Date:   Sat Feb 15 10:58:55 2014 -0500

    cmd/gc: correct liveness for fat variables
    
    The VARDEF placement must be before the initialization
    but after any final use. If you have something like s = ... using s ...
    the rhs must be evaluated, then the VARDEF, then the lhs
    assigned.
    
    There is a large comment in pgen.c on gvardef explaining
    this in more detail.
    
    This CL also includes Ian's suggestions from earlier CLs,
    namely commenting the use of mode in link.h and fixing
    the precedence of the ~r check in dcl.c.
    
    This CL enables the check that if liveness analysis decides
    a variable is live on entry to the function, that variable must
    be a function parameter (not a result, and not a local variable).
    If this check fails, it indicates a bug in the liveness analysis or
    in the generated code being analyzed.
    
    The race detector generates invalid code for append(x, y...).
    The code declares a temporary t and then uses cap(t) before
    initializing t. The new liveness check catches this bug and
    stops the compiler from writing out the buggy code.
    Consequently, this CL disables the race detector tests in
    run.bash until the race detector bug can be fixed
    (golang.org/issue/7334).
    
    Except for the race detector bug, the liveness analysis check
    does not detect any problems (this CL and the previous CLs
    fixed all the detected problems).
    
    The net test still fails with GOGC=0 but the rest of the tests
    now pass or time out (because GOGC=0 is so slow).
    
    TBR=iant
    CC=golang-codereviews
    https://golang.org/cl/64170043

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/7a7c0ffb478847a0711f6b829a615ef4eea5dc67

元コミット内容

cmd/gc: fat variables のライブネスを修正

VARDEF の配置は、初期化の前で、かつ最終使用の後でなければならない。もし s = ... using s ... のようなものがある場合、右辺は評価され、次に VARDEF、そして左辺が割り当てられる必要がある。

pgen.c の gvardef に、これについてより詳細な大きなコメントがある。

このCL（Change List）には、以前のCLからのIanの提案も含まれている。具体的には、link.h の mode の使用にコメントを追加することと、dcl.c の ~r チェックの優先順位を修正することである。

このCLは、ライブネス解析が関数エントリ時に変数がライブであると判断した場合、その変数は関数パラメータでなければならない（結果変数でもローカル変数でもない）というチェックを有効にする。このチェックが失敗した場合、それはライブネス解析または解析されている生成コードのバグを示している。

レース検出器は append(x, y...) に対して不正なコードを生成する。このコードは一時変数 t を宣言し、t を初期化する前に cap(t) を使用する。新しいライブネスチェックはこのバグを検出し、コンパイラがバグのあるコードを書き出すのを停止させる。結果として、このCLはレース検出器のバグが修正されるまで（golang.org/issue/7334）、run.bash のレース検出器テストを無効にする。

レース検出器のバグを除いて、ライブネス解析チェックは問題を発見しない（このCLと以前のCLは、検出されたすべての問題を修正した）。

net テストは GOGC=0 でまだ失敗するが、残りのテストは合格するかタイムアウトする（GOGC=0 が非常に遅いため）。

変更の背景

このコミットの主な背景には、Goコンパイラのライブネス解析の正確性に関する問題がありました。ライブネス解析は、ガベージコレクション（GC）の効率性や、不要なコードの削除（デッドコードエリミネーション）に不可欠な要素です。変数がいつ「ライブ」（将来的に使用される可能性がある）であるかを正確に判断することは、メモリ管理の最適化において極めて重要です。

具体的には、以下の問題が指摘されていました。

  1. VARDEF 命令の不適切な配置: Goコンパイラは、変数の定義を示す VARDEF という擬似命令を生成します。これはライブネス解析器に対するヒントとして機能します。しかし、特に「fat variables」（構造体、配列、スライスなど、複数のメモリワードを占める変数）の再割り当てや部分的な更新において、VARDEF の配置が不適切だと、ライブネス解析が変数のライフタイムを誤って判断する可能性がありました。例えば、x = x[1:] のような操作では、右辺の評価で x の古い値が使用され、その後に x の新しい値が割り当てられます。もし VARDEF が右辺の評価前に配置されると、解析器は古い x が不要だと誤解し、最適化によって問題を引き起こす可能性がありました。逆に、新しい値の割り当て後に配置されると、新しい x の値がライブネス解析によって適切に追跡されない可能性がありました。

  2. ライブネス解析の不変条件の違反: コンパイラのライブネス解析には、「関数エントリ時にライブである変数は、必ず関数パラメータでなければならない」という重要な不変条件があります。もしローカル変数や戻り値が関数エントリ時にライブであると判断された場合、それはコンパイラ内部のバグを示唆します。このコミット以前は、この不変条件を厳密にチェックするメカニズムが不十分でした。

  3. レース検出器のバグ: Goのレース検出器は、並行処理におけるデータ競合を検出するための強力なツールですが、特定のケース（append 関数の使用など）で不正なコードを生成するというバグを抱えていました。このバグは、一時変数が初期化される前に使用されるという形で現れ、ライブネス解析の誤りとして顕在化しました。

これらの問題は、コンパイラが生成するコードの正確性や、ガベージコレクションの効率に直接影響を与えるため、修正が急務でした。

前提知識の解説

このコミットを理解するためには、Goコンパイラの内部構造、特にコード生成と最適化のフェーズ、およびライブネス解析の概念について基本的な知識が必要です。

  1. Goコンパイラ（cmd/gc）: Goコンパイラは、Go言語のソースコードを機械語に変換するツールチェーンの一部です。複数のフェーズに分かれており、このコミットで言及されているファイル群（cgen.c, ggen.c, peep.c, reg.c, dcl.c, gen.c, pgen.c, plive.c）は、主にコード生成（gen）、バックエンド（cgen, ggen）、最適化（peep, reg）、宣言処理（dcl）、擬似命令生成（pgen）、ライブネス解析（plive）といったコンパイラの後半部分に関わっています。

  2. ライブネス解析（Liveness Analysis）: ライブネス解析は、プログラムの特定のポイントにおいて、どの変数が「ライブ」（その値が将来的に読み取られる可能性がある）であるかを決定するデータフロー解析の一種です。

    • 目的:
      • ガベージコレクション（GC）: GCは、ライブでない（もう使用されない）メモリを解放します。ライブネス解析は、GCがどのオブジェクトを安全に解放できるかを判断するのに役立ちます。
      • レジスタ割り当て: ライブな変数をレジスタに割り当てることで、メモリへのアクセスを減らし、プログラムの実行速度を向上させます。
      • デッドコードエリミネーション: ライブでない変数の計算や、その変数への代入はデッドコードと見なされ、削除される可能性があります。
    • 基本概念:
      • Live-in: あるプログラムポイントに入る時点で変数がライブであること。
      • Live-out: あるプログラムポイントから出る時点で変数がライブであること。
      • Use: 変数の値が読み取られること。
      • Definition (Def): 変数に新しい値が書き込まれること。
    • 解析の仕組み: 通常、ライブネス解析はプログラムの制御フローグラフ（CFG）上で逆方向に（プログラムの終わりから始まりへ）行われます。ある変数がライブであるのは、その変数の値が、現在のポイントから到達可能なパス上で、その変数の次の定義の前に使用される場合です。

  3. VARDEF 命令: Goコンパイラ内部で使用される擬似命令（pseudo-instruction）の一つです。これは、実際の機械語命令ではなく、コンパイラのライブネス解析器に対して「ここで変数が完全に定義（初期化）された」というヒントを与えるために挿入されます。特に、複数ワードの変数（構造体、配列、スライスなど）の初期化において重要です。単一ワードの変数の場合は、通常の代入命令からライブネス解析器が定義を推測できますが、複数ワードの場合は、複数の命令にまたがる初期化のどの時点で変数が「完全に定義された」と見なすべきかを明示するために VARDEF が使われます。

  4. Fat Variables（ファット変数）: Go言語における「fat variables」とは、単一のCPUレジスタやメモリワードに収まらない、複数のメモリワードを占める変数のことを指します。典型的な例は以下の通りです。

    • スライス（[]T）: ポインタ、長さ、容量の3つのフィールドから構成されます。
    • 文字列（string）: ポインタと長さの2つのフィールドから構成されます。
    • インターフェース（interface{}）: 型情報と値の2つのフィールドから構成されます。
    • 構造体（struct）: 複数のフィールドを持つ場合。
    • 配列（[N]T）: 要素数が多い場合。 これらの変数は、代入や引数渡し、戻り値として扱われる際に、複数のメモリ操作を伴うため、ライブネス解析が複雑になります。

  5. Goのレース検出器（Race Detector）: Goランタイムに組み込まれているツールで、並行実行されるGoルーチン間でのデータ競合（data race）を検出します。データ競合は、複数のGoルーチンが同時に同じメモリ位置にアクセスし、少なくとも1つのアクセスが書き込みであり、かつアクセスが同期されていない場合に発生します。レース検出器は、プログラムの実行時にこれらの競合を特定し、デバッグを支援します。

技術的詳細

このコミットの技術的詳細は、主にVARDEF命令の配置ロジックの修正と、ライブネス解析の新たな不変条件チェックの導入に集約されます。

1. VARDEF 命令の配置ロジックの修正

コミットメッセージで最も強調されているのは、VARDEF命令の配置に関する修正です。以前のコンパイラでは、VARDEFが不適切なタイミングで挿入されることがあり、これがライブネス解析の誤りにつながっていました。

問題の具体例 (x = x[1:]): x = x[1:] のようなスライス操作を考えます。

  1. まず、右辺 x[1:] が評価されます。この評価には、元の x の値（特にその基底ポインタ、長さ、容量）が必要です。
  2. 次に、評価された新しいスライスの値が左辺の x に割り当てられます。

もし VARDEF x が右辺の評価前に挿入されると、ライブネス解析器は「x がここで新しく定義された」と解釈し、古い x の値はもう不要だと判断してしまいます。しかし、実際には右辺の評価で古い x が必要なので、これは誤りです。 逆に、もし VARDEF x が新しい x の値が割り当てられた後に挿入されると、ライブネス解析器は新しい x の値を適切に追跡できず、その値がデッドであると誤解する可能性があります。

正しい VARDEF の配置: コミットメッセージが示すように、VARDEFは以下の条件を満たす必要があります。

  • 初期化の前: 変数の新しい値が実際にメモリに書き込まれる命令群の直前。
  • 最終使用の後: 変数の古い値が最後に使用される命令の直後。

これにより、ライブネス解析器は、変数の古い値が使用され終わった直後に新しい値が定義されたことを正確に認識し、その後のライブネスを正しく追跡できるようになります。

この修正は、src/cmd/{5g,6g,8g}/cgen.c および src/cmd/gc/gen.c、src/cmd/gc/pgen.c の gvardef 関数の呼び出し箇所に影響を与えています。特に、sgen（ステートメント生成）や componentgen（複合型の要素生成）などの関数で、ONAME（名前付き変数）に対する gvardef の呼び出しが、より適切なタイミングに移動されています。また、clearfat 関数からの gvardef の呼び出しが削除されています。これは、clearfat が変数のアドレスをクリアする操作であり、変数の「定義」とは異なるためです。

src/cmd/gc/pgen.c の gvardef 関数には、このロジックの重要性を説明する詳細なコメントが追加されています。このコメントは、VARDEF が単一ワードの値ではなく、複数ワードの「fat variables」の定義をライブネス解析に伝えるための「kludge」（一時しのぎの解決策）であると述べています。

2. ライブネス解析の新たな不変条件チェック

このコミットでは、ライブネス解析の健全性を保証するための重要なチェックが src/cmd/gc/plive.c に導入されています。

チェックの内容: 「関数エントリ時にライブである変数は、関数パラメータでなければならない」という不変条件を強制します。

  • plive.c の livenessepilogue 関数内で、ATEXT 命令（関数の開始を示す）のライブネス解析結果をチェックします。
  • もし関数エントリ時にライブであると判断された変数が PPARAM（関数パラメータ）でない場合（例えば、ローカル変数や戻り値である場合）、yyerrorl を呼び出してコンパイルエラーを発生させます。これは、ライブネス解析またはコード生成にバグがあることを示します。

このチェックは、以前はコメントアウトされていたか、無効化されていたものが有効化されました（if(0 && p->as == ATEXT) が if(p->as == ATEXT) に変更）。このチェックを有効にすることで、コンパイラはライブネス解析の誤りを早期に発見し、不正なコードの生成を防ぐことができます。

3. レース検出器のバグと一時的な無効化

新しいライブネスチェックを有効にした結果、Goのレース検出器が append(x, y...) のような操作に対して生成するコードにバグがあることが判明しました。具体的には、レース検出器が生成する一時変数が、初期化される前に使用されるという問題です（例: cap(t) が t の初期化前に呼ばれる）。

このバグは、新しいライブネスチェックによって「関数エントリ時にローカル変数がライブである」というエラーとして検出されました。この問題を回避するため、コミットは一時的に run.bash スクリプト内のレース検出器テストを無効にしています（XXX プレフィックスを追加）。これは、golang.org/issue/7334 で追跡されている既知のバグであり、このコミットはコンパイラがバグのあるコードを生成するのを防ぐ一方で、根本的なレース検出器のバグ修正は別のコミットに委ねられています。

4. その他の修正

  • link.h の mode フィールドのコメント: include/link.h で Prog 構造体の mode フィールドに関するコメントが更新され、その用途がより明確になりました。
  • dcl.c の ~r チェックの優先順位: src/cmd/gc/dcl.c で、匿名戻り値に割り当てられる ~r%d 形式の名前をチェックする際の論理演算子の優先順位が修正されました。これにより、戻り値が名前付きであるかどうかの判断がより正確になります。

これらの変更は、Goコンパイラの堅牢性と正確性を高め、特に複雑なデータ構造のライブネス解析における信頼性を向上させるものです。

コアとなるコードの変更箇所

このコミットにおけるコアとなるコードの変更箇所は多岐にわたりますが、特に重要なのは以下のファイルとコードブロックです。

  1. src/cmd/gc/pgen.c: gvardef 関数の新しいコメントと、gvardef の呼び出しに関するロジックの変更。これは VARDEF 命令のセマンティクスと配置の核心を説明しています。

    // gvardef inserts a VARDEF for n into the instruction stream.
// VARDEF is an annotation for the liveness analysis, marking a place
// where a complete initialization (definition) of a variable begins.
// ... (中略) ...
// VARDEF is a bit of a kludge to work around the fact that the instruction
// stream is working on single-word values but the liveness analysis
// wants to work on individual variables, which might be multi-word
// aggregates.

    また、gvardef 関数自体に、n->op != ONAME の場合のチェックとエラー処理が追加されています。

  2. src/cmd/gc/gen.c: gvardef の呼び出し箇所の変更。特に OAS (代入) や OSLICE (スライス操作) の処理において、VARDEF の挿入タイミングが調整されています。

    • cgen_as 関数内での gvardef(nl) の追加（isfat(tl) かつ nl->op == ONAME の場合）。
    • cgen_slice 関数内で、スライスの基底ポインタの評価後に gvardef(res) が移動・追加されています。これは、スライスの各要素（ポインタ、長さ、容量）が完全に設定された後に VARDEF を挿入することで、ライブネス解析がスライス全体を正しく追跡できるようにするためです。

  3. src/cmd/{5g,6g,8g}/cgen.c: 各アーキテクチャ固有のコード生成バックエンドにおける gvardef の呼び出し箇所の調整。

    • agen 関数で一時変数 n1 の宣言後に gvardef(&n1) が追加。
    • sgen 関数から gvardef(res) の古い呼び出しが削除され、より適切なタイミング（agenr の後など）に移動または追加されています。
    • componentgen 関数で、ONAME の nl に対して gvardef(nl) が追加されています。

  4. src/cmd/{5g,6g,8g}/ggen.c: markautoused および fixautoused 関数における AVARDEF 命令の扱い。

    • markautoused で p->as == AVARDEF もスキップ対象に追加。
    • fixautoused で、使用されていない AVARDEF 命令を ANOP (no-op) に置き換えるロジックが追加されています。これは、VARDEF が他の命令と混在しているため、単純に削除するとジャンプターゲットがずれる可能性があるためです。

  5. src/cmd/gc/plive.c: ライブネス解析の不変条件チェックの有効化と、エラーメッセージの改善。

    • livenessepilogue 関数内で、ATEXT 命令（関数エントリ）におけるライブネスチェックが有効化されています。
    // 変更前: if(0 && p->as == ATEXT) {
// 変更後: if(p->as == ATEXT) {
    • checkauto および checkparam 関数の引数から char *where が削除され、エラーメッセージのフォーマットが改善されています。
    • newcfg 関数で、到達不能な基本ブロックが検出された場合のエラーメッセージがより詳細になり、printcfg の呼び出しが追加されています。

  6. src/run.bash: レース検出器テストの一時的な無効化。

    # Disabled due to golang.org/issue/7334; remove XXX below to reenable.
case "$GOHOSTOS-$GOOS-$GOARCH-$CGO_ENABLED" in
XXXlinux-linux-amd64-1 | XXXdarwin-darwin-amd64-1)

    XXX プレフィックスを追加することで、該当するテストが実行されないようにしています。

  7. test/live.go および test/live1.go: ライブネス解析の修正を検証するためのテストケースの追加と調整。

    • test/live.go に f13 関数が追加され、s = h13(s, g13(s)) のようなケースで VARDEF の配置が正しくないとライブネス解析が失敗することを示すテストが追加されています。
    • test/live1.go のコメントが更新され、このテストが VARDEF の配置ミスによる一時変数のライブネス問題（特にラッパー関数で発生する）を検出するために使用されていることが明記されています。

コアとなるコードの解説

src/cmd/gc/pgen.c の gvardef コメント

このコミットの最も重要な変更の一つは、src/cmd/gc/pgen.c に追加された gvardef 関数の詳細なコメントです。これは、VARDEF 命令の目的と、その配置がライブネス解析に与える影響を明確に説明しています。

// gvardef inserts a VARDEF for n into the instruction stream.
// VARDEF is an annotation for the liveness analysis, marking a place
// where a complete initialization (definition) of a variable begins.
// Since the liveness analysis can see initialization of single-word
// variables quite easy, gvardef is usually only called for multi-word
// or 'fat' variables, those satisfying isfat(n->type).
// However, gvardef is also called when a non-fat variable is initialized
// via a block move; the only time this happens is when you have
//      return f()
// for a function with multiple return values exactly matching the return
// types of the current function.
//
// A 'VARDEF x' annotation in the instruction stream tells the liveness
// analysis to behave as though the variable x is being initialized at that
// point in the instruction stream. The VARDEF must appear before the
// actual (multi-instruction) initialization, and it must also appear after
// any uses of the previous value, if any. For example, if compiling:
//
//      x = x[1:]
//
// it is important to generate code like:
//
//      base, len, cap = pieces of x[1:]
//      VARDEF x
//      x = {base, len, cap}
//
// If instead the generated code looked like:
//
//      VARDEF x
//      base, len, cap = pieces of x[1:]
//      x = {base, len, cap}
//
// then the liveness analysis would decide the previous value of x was
// unnecessary even though it is about to be used by the x[1:] computation.
// Similarly, if the generated code looked like:
//
//      base, len, cap = pieces of x[1:]
//      x = {base, len, cap}
//      VARDEF x
//
// then the liveness analysis will not preserve the new value of x, because
// the VARDEF appears to have "overwritten" it.
//
// VARDEF is a bit of a kludge to work around the fact that the instruction
// stream is working on single-word values but the liveness analysis
// wants to work on individual variables, which might be multi-word
// aggregates. It might make sense at some point to look into letting
// the liveness analysis work on single-word values as well, although
// there are complications around interface values, which cannot be
// treated as individual words.

このコメントは、VARDEF がライブネス解析のための「アノテーション」（注釈）であり、変数の完全な初期化が始まる場所を示すことを明確にしています。特に、x = x[1:] の例を用いて、VARDEF の配置がライブネス解析にどのように影響するかを詳細に説明しています。

  • 右辺の評価（pieces of x[1:]）が完了し、古い x の値がもう必要ないことを確認した後。
  • 左辺への新しい値の割り当て（x = {base, len, cap}）が始まる直前。 このタイミングで VARDEF x を挿入することが、ライブネス解析が x のライフタイムを正確に追跡するために不可欠であることを強調しています。また、VARDEF が複数ワードの変数を扱うライブネス解析と、単一ワードの命令ストリームとの間の「一時しのぎの解決策」（kludge）であるという洞察も提供しています。

src/cmd/gc/gen.c の cgen_slice 関数における gvardef の移動

スライス操作のコード生成を担当する cgen_slice 関数における gvardef の呼び出し位置の変更は、このコミットの重要な修正点です。

変更前:

// ...
gvardef(res); // ここでVARDEFが挿入されていた
// ...
// dst.len = hi [ - lo ]
// ...
// dst.cap = cap [ - lo ]
// ...
// dst.array = src.array  [ + lo *width ]
// ...

変更前は、スライスの基底ポインタ、長さ、容量のいずれも計算される前に gvardef(res) が呼び出されていました。これは、スライス res がまだ完全に初期化されていないにもかかわらず、ライブネス解析器に「res が定義された」と誤って伝えてしまう可能性がありました。

変更後:

// ...
// evaluate base pointer first, because it is the only
// possibly complex expression. once that is evaluated
// and stored, updating the len and cap can be done
// without making any calls, so without doing anything that
// might cause preemption or garbage collection.
// this makes the whole slice update atomic as far as the
// garbage collector can see.
//
base = temp(types[TUINTPTR]);
// ... base の計算と格納 ...
//
// committed to the update
gvardef(res); // ここに移動
//
// dst.array = src.array  [ + lo *width ]
// ...
// dst.len = hi [ - lo ]
// ...
// dst.cap = cap [ - lo ]
// ...

変更後では、スライスの基底ポインタ（base）が計算され、一時変数に格納された後に gvardef(res) が呼び出されています。これは、スライスの最も重要な部分である基底ポインタが確定した時点で、スライス全体が「定義され始めた」とライブネス解析器に伝えるためです。このタイミングは、スライスの長さや容量の計算（これらは通常、より単純な操作であり、GCやプリエンプションを引き起こさない）の前に来ます。これにより、スライス全体の更新がGCから見てアトミックになり、ライブネス解析がより正確に行われるようになります。

src/cmd/gc/plive.c のライブネスチェック有効化

src/cmd/gc/plive.c の livenessepilogue 関数における以下の変更は、ライブネス解析の健全性を強制するものです。

// 変更前:
// if(0 && p->as == ATEXT) { // チェックが無効化されていた
//     // ...
// }

// 変更後:
if(p->as == ATEXT) { // チェックが有効化された
    for(j = 0; j < liveout->n; j++) {
        if(!bvget(liveout, j))
            continue;
        n = *(Node**)arrayget(lv->vars, j);
        if(n->class != PPARAM)
            yyerrorl(p->lineno, "internal error: %N %lN recorded as live on entry", curfn->nname, n);
    }
}

このコードは、関数のエントリポイント（ATEXT 命令）において、ライブネス解析が「ライブである」と判断した変数が、実際に「関数パラメータ」（PPARAM）であるかどうかをチェックします。もし、ローカル変数や戻り値が関数エントリ時にライブであると判断された場合、それはコンパイラのライブネス解析またはコード生成に深刻なバグがあることを意味します。このチェックを有効にすることで、そのようなバグが早期に検出され、コンパイル時にエラーとして報告されるようになります。これにより、不正なコードが生成されるのを防ぎ、コンパイラの信頼性が向上します。

これらの変更は、Goコンパイラのライブネス解析の正確性を大幅に向上させ、特に複雑なデータ構造や最適化されたコードパスにおける潜在的なバグを防ぐ上で重要な役割を果たしています。

関連リンク

参考にした情報源リンク

  • Go Compiler Internals (Liveness Analysis, GC): 一般的なコンパイラのライブネス解析に関する情報源。
  • Go Language Specification (Slices, Strings, Interfaces): Go言語のデータ構造に関する公式ドキュメント。
  • Go Race Detector Documentation: Goのレース検出器に関する公式ドキュメント。