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

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

このコミットは、Goコンパイラ（cmd/gc）における一時変数（temporary variables）の最適化パスを追加するものです。具体的には、生存期間が重複しない同じ型の一時変数をマージすることで、スタックフレームサイズを削減し、コンパイラのレジスタ割り当ての効率を向上させることを目的としています。

コミット

commit fa72679f0710c406c88db40f2a92d905b7a7c055
Author: Russ Cox <rsc@golang.org>
Date:   Tue Aug 13 00:09:31 2013 -0400

    cmd/gc: add temporary-merging optimization pass
    
    The compilers assume they can generate temporary variables
    as needed to preserve the right semantics or simplify code
    generation and the back end will still generate good code.
    This turns out not to be true. The back ends will only
    track the first 128 variables per function and give up
    on the remainder. That needs to be fixed too, in a later CL.
    
    This CL merges temporary variables with equal types and
    non-overlapping lifetimes using the greedy algorithm in
    Poletto and Sarkar, "Linear Scan Register Allocation",
    ACM TOPLAS 1999.
    
    The result can be striking in the right functions.
    
    Top 20 frame size changes in a 6g godoc binary by bytes saved:
    
    5464 1984 (-3480, -63.7%) go/build.(*Context).Import
    4456 1824 (-2632, -59.1%) go/printer.(*printer).expr1
    2560   80 (-2480, -96.9%) time.nextStdChunk
    3496 1608 (-1888, -54.0%) go/printer.(*printer).stmt
    1896  272 (-1624, -85.7%) net/http.init
    2688 1400 (-1288, -47.9%) fmt.(*pp).printReflectValue
    2800 1512 (-1288, -46.0%) main.main
    3296 2016 (-1280, -38.8%) crypto/tls.(*Conn).clientHandshake
    1664  488 (-1176, -70.7%) time.loadZoneZip
    1760  608 (-1152, -65.5%) time.parse
    4104 3072 (-1032, -25.1%) runtime/pprof.writeHeap
    1680  712 ( -968, -57.6%) go/ast.Walk
    2488 1560 ( -928, -37.3%) crypto/x509.parseCertificate
    1128  392 ( -736, -65.2%) math/big.nat.divLarge
    1528  864 ( -664, -43.5%) go/printer.(*printer).fieldList
    1360  712 ( -648, -47.6%) regexp/syntax.(*parser).factor
    2104 1528 ( -576, -27.4%) encoding/asn1.parseField
    1064  504 ( -560, -52.6%) encoding/xml.(*Decoder).text
     584   48 ( -536, -91.8%) html.init
    1400  864 ( -536, -38.3%) go/doc.playExample
    
    In the same godoc build, cuts the number of functions with
    too many vars from 83 to 32.
    
    R=ken2
    CC=golang-dev
    https://golang.org/cl/12829043

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

https://github.com/golang/go/commit/fa72679f0710c406c88db40f2a92d905b7a7c055

元コミット内容

Goコンパイラは、コード生成のセマンティクスを維持したり、コード生成を簡素化するために必要に応じて一時変数を生成します。しかし、バックエンドが最初の128個の変数しか追跡せず、それ以降の変数を適切に処理できないという問題がありました。このコミットは、この問題を部分的に解決するため、同じ型で生存期間が重複しない一時変数を、PolettoとSarkarの「Linear Scan Register Allocation」アルゴリズム（ACM TOPLAS 1999）の貪欲アルゴリズムを用いてマージする最適化パスを追加します。

この最適化により、特定の関数では顕著な効果が見られ、godocバイナリのビルドにおいて、スタックフレームサイズが大幅に削減されました。例えば、go/build.(*Context).Import関数では63.7%の削減、time.nextStdChunk関数では96.9%の削減が達成されています。また、多すぎる変数を抱える関数の数が83から32に減少しました。

変更の背景

Goコンパイラは、コードの正確性を保証し、コード生成を簡素化するために、多くの「一時変数」（temporary variables）を生成します。これらの一時変数は、中間表現（IR）の段階で導入され、計算結果の一時的な保持や、複雑な式の分解などに利用されます。しかし、当時のGoコンパイラのバックエンド（特にレジスタ割り当て部分）には、関数ごとに追跡できる変数の数に制限（128個）があり、これを超えると最適化が適切に行われなくなるという問題がありました。

この制限により、多くの関数で不必要に大きなスタックフレームが割り当てられたり、レジスタの利用効率が低下したりしていました。特に、多くの小さな一時変数が生成されるようなコードパターンでは、この問題が顕著になり、生成されるバイナリのサイズ増加や実行時性能の低下につながっていました。

このコミットは、この問題に対処するための初期ステップとして、一時変数の数を減らすことを目的としています。具体的には、生存期間が重複しない一時変数を再利用することで、変数の総数を減らし、バックエンドのレジスタ割り当て器がより効率的に動作できるようにします。これにより、スタックフレームサイズの削減と、全体的なコード品質の向上が期待されます。

前提知識の解説

コンパイラの最適化と一時変数

コンパイラは、ソースコードを機械語に変換する過程で、プログラムの実行効率を向上させるための様々な最適化を行います。その中で、「一時変数」は、コンパイラが内部的に生成する変数であり、中間計算結果を保持するために使用されます。例えば、a = (b + c) * dのような式では、b + cの結果を一時変数に格納し、その一時変数とdを乗算するといった形で利用されます。

一時変数は、コードの正確性を保ちつつ、コンパイラの処理を簡素化する上で非常に有用ですが、その数が多すぎると、メモリ使用量の増加やレジスタ割り当ての非効率性といった問題を引き起こす可能性があります。

レジスタ割り当て（Register Allocation）

レジスタ割り当ては、コンパイラのバックエンドにおける最も重要な最適化の一つです。CPUのレジスタは、メインメモリよりもはるかに高速にアクセスできるため、頻繁にアクセスされる変数をレジスタに割り当てることで、プログラムの実行速度を大幅に向上させることができます。

しかし、CPUのレジスタ数は限られているため、どの変数をどのレジスタに割り当てるか、あるいはレジスタに割り当てられない変数をどのようにメモリ（スタック）に退避（spill）させるか、という問題は非常に複雑です。

線形スキャンレジスタ割り当て（Linear Scan Register Allocation）

線形スキャンレジスタ割り当ては、PolettoとSarkarによって1999年に提案されたレジスタ割り当てアルゴリズムです。従来のグラフ彩色に基づくレジスタ割り当てアルゴリズムが、変数の干渉グラフを構築するために高い計算コストを要するのに対し、線形スキャンはより高速でシンプルなアプローチを取ります。

このアルゴリズムの基本的な考え方は以下の通りです。

  1. 生存期間の計算: 各変数について、プログラムのどの範囲（命令の開始から終了まで）でその変数が「生存している」（値が有効である）かを計算します。これを「生存期間」（live range）と呼びます。
  2. 生存期間のソート: 変数をその生存期間の開始点に基づいてソートします。
  3. 貪欲な割り当て: ソートされた順に変数を見ていき、利用可能なレジスタがあればその変数に割り当てます。
  4. レジスタの解放: 変数の生存期間が終了したら、その変数が使用していたレジスタを解放し、他の変数に再利用できるようにします。
  5. スピル（Spilling）: もし利用可能なレジスタがない場合、現在レジスタに割り当てられている変数の中から、最も長く生存する変数をメモリに退避させ（スピル）、そのレジスタを新しい変数に割り当てます。

線形スキャンは、グラフ彩色に比べて最適性は劣るものの、コンパイル時間が短く、JITコンパイラなど、高速なコンパイルが求められる環境で広く採用されています。このコミットでは、このアルゴリズムの考え方を一時変数のマージに応用しています。

Goコンパイラ (cmd/gc) のアーキテクチャ

Goコンパイラ (cmd/gc) は、Go言語の公式コンパイラであり、そのアーキテクチャは伝統的なコンパイラの三段階（フロントエンド、ミドルエンド、バックエンド）に分けられます。

  • フロントエンド: 字句解析、構文解析、型チェックなどを行い、ソースコードを抽象構文木（AST）に変換します。
  • ミドルエンド: ASTに対して様々な最適化（エスケープ解析、インライン化、デッドコード削除など）を適用し、中間表現（IR）を生成します。Go 1.7以降はSSA（Static Single Assignment）形式が導入され、より高度な最適化が可能になりました。
  • バックエンド: 最適化されたIRをターゲットアーキテクチャの機械語に変換し、レジスタ割り当てや命令スケジューリングなどを行います。

このコミットは、主にミドルエンドとバックエンドの間の最適化フェーズに位置し、レジスタ割り当ての効率を向上させるための前処理として機能します。

技術的詳細

このコミットで導入された一時変数マージの最適化は、Goコンパイラのcmd/gc（および各アーキテクチャ固有のコンパイラである5g, 6g, 8g）のバックエンドに近い部分で行われます。

主要なアイデアは、PolettoとSarkarの線形スキャンレジスタ割り当てアルゴリズムを応用し、生存期間が重複しない同じ型の一時変数を一つの変数として再利用することです。これにより、コンパイラが扱う一時変数の総数を減らし、レジスタ割り当て器の負担を軽減します。

具体的な処理の流れは以下のようになります。

  1. 一時変数の特定: 関数内で生成されたすべての一時変数（autotmpというシンボル名を持つ変数）を特定します。これらの変数は、通常、コンパイラが内部的に生成するもので、ユーザーコードで直接参照されることはありません。
  2. 生存期間の計算: 各一時変数について、その変数が「定義」され、最後に「使用」されるまでのプログラム上の範囲（生存期間）を特定します。これは、命令の順序（Prog.loc）に基づいて行われます。
  3. 生存期間のソート: 特定された一時変数を、その生存期間の開始点（start）に基づいて昇順にソートします。
  4. 貪欲なマージ: ソートされた一時変数を順に処理します。
    • 現在処理している一時変数と生存期間が重複しない、かつ同じ型を持つ、以前に処理された一時変数（既にマージ済みまたは解放済み）を探します。
    • もしそのような変数が見つかれば、現在の一時変数をその変数にマージします。つまり、現在の一時変数の参照を、マージ先の変数に置き換えます。
    • 適切なマージ先が見つからない場合、現在の一時変数は新しい変数として扱われます。
  5. プログラムの更新: マージが完了した後、プログラム内のすべての一時変数への参照を、マージ後の変数に更新します。これにより、複数の論理的な一時変数が、物理的には一つの変数として扱われるようになります。
  6. 宣言リストのクリーンアップ: マージされた一時変数は、もはや個別の宣言として不要になるため、関数の宣言リストから削除されます。

この最適化は、特に多くの小さな一時変数が生成されるような複雑な式や、ループ内で一時変数が繰り返し使用されるような場合に効果を発揮します。変数の数を減らすことで、コンパイラのレジスタ割り当て器がより多くの変数をレジスタに割り当てられるようになり、スタックへのスピル（退避）が減少します。結果として、スタックフレームサイズの削減と、実行時性能の向上が期待できます。

コミットメッセージに記載されているように、この最適化はgodocバイナリのビルドにおいて、特定の関数のスタックフレームサイズを劇的に削減する効果をもたらしました。これは、Goコンパイラが生成する一時変数の数が、当時のバックエンドのレジスタ割り当て器の能力を超えていたことを示唆しています。

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

このコミットにおける主要なコード変更は、Goコンパイラの共通部分 (src/cmd/gc) と、各アーキテクチャ固有のコンパイラ (src/cmd/5g, src/cmd/6g, src/cmd/8g) に分散しています。

  • src/cmd/gc/go.h:
    • Node構造体にvoid *opt;フィールドが追加されました。これは、最適化パスで一時的なデータをノードに関連付けるために使用されます。
  • src/cmd/gc/popt.h:
    • mergetemp(Prog*);関数のプロトタイプが追加されました。
  • src/cmd/gc/popt.c:
    • mergetemp関数が新規に追加されました。これが一時変数マージ最適化の主要なロジックを実装しています。
    • TempVarとTempFlowという新しい構造体が定義されました。これらは一時変数の情報と制御フローグラフのノードを関連付けるために使用されます。
    • mergewalk関数が追加されました。これは一時変数の生存期間を計算するためのヘルパー関数です。
  • src/cmd/{5,6,8}g/opt.h:
    • EXTERN Reg* firstr;の宣言が削除されました。これは、reg.c内でstatic宣言に移動されたためです。
  • src/cmd/{5,6,8}g/reg.c:
    • static Reg* firstr;が追加され、firstrがファイルスコープの静的変数になりました。
    • regopt関数内で、mergetemp(firstp);が呼び出されるようになりました。これにより、レジスタ割り当ての前に一時変数マージ最適化が実行されます。
    • fixtemp関数が削除されました。この関数は、一時変数を削減するための以前の試みでしたが、mergetempによって置き換えられました。
    • regopt関数内の不要なループ（for(r = firstr; r != R; r = (Reg*)r->f.link) r->f.active = 0;）が削除されました。これはflowrpo関数内で処理されるようになりました。
  • src/cmd/{5,6,8}g/peep.c:
    • flowend(g);の呼び出しが追加されました。
  • src/cmd/6l/list.c:
    • アセンブリコードの出力フォーマットが一部変更されました（%D,%d,%Dから%D,%d,%lD）。これは直接的な最適化とは関係なく、デバッグ出力の改善と思われます。

最も重要な変更は、src/cmd/gc/popt.cにmergetemp関数が追加され、それが各アーキテクチャのreg.cから呼び出されるようになった点です。これにより、コンパイラのレジスタ割り当てフェーズの前に、一時変数のマージが行われるようになりました。

コアとなるコードの解説

このコミットの核となるのは、src/cmd/gc/popt.cに追加されたmergetemp関数です。この関数は、Goコンパイラが生成する一時変数を最適化し、生存期間が重複しない変数をマージすることで、スタックフレームサイズを削減し、レジスタ割り当ての効率を向上させます。

mergetemp関数の主要な処理は以下のステップで構成されます。

  1. 制御フローグラフ (CFG) の構築:

    • flowstart(firstp, sizeof(TempFlow))を呼び出して、関数の命令列（Progリスト）から制御フローグラフを構築します。このグラフは、命令間の実行順序と依存関係を表現します。TempFlowは、通常のFlow構造体にuselinkフィールドを追加したもので、一時変数の使用リストをチェインするために使われます。

  2. マージ可能一時変数の収集:

    • 関数の宣言リスト（curfn->dcl）を走査し、マージ可能な一時変数（PAUTOクラスで、アドレスが取られておらず、シンボル名がautotmpで始まるもの）を特定します。
    • これらの変数ごとにTempVar構造体を作成し、Nodeへのポインタ、定義（def）と使用（use）のフローノード、生存期間の開始（start）と終了（end）などを格納します。
    • 各Nodeのoptフィールドに、対応するTempVarへのポインタを設定し、後で簡単にアクセスできるようにします。

  3. 一時変数の使用リストの構築:

    • CFGの各フローノード（TempFlow）を走査し、各命令（Prog）がどの一時変数を使用または定義しているかを調べます。
    • 一時変数が定義された最初のフローノードをv->defに設定します。
    • 一時変数が使用されるすべてのフローノードをv->useリストにチェインします。

  4. 特殊ケースの最適化:

    • 書き込み専用の一時変数の削除: もし一時変数が一度だけ書き込まれ、その後全く使用されない場合（v->useが1つだけで、それが書き込み命令である場合）、その書き込み命令をANOP（No Operation）に変換し、一時変数をプログラムから削除します。
    • 即時使用の一時変数のマージ: 一時変数が書き込まれた直後の命令で読み込まれ、それ以外では使用されない場合、書き込み命令を削除し、読み込み命令のソースを書き込み命令のソースに直接変更します。これは、特に386コンパイラで頻繁に発生するパターンです。

  5. 一時変数の生存期間の計算:

    • 各一時変数について、mergewalk関数を呼び出して、その生存期間の開始点（start）と終了点（end）を正確に計算します。mergewalkは、制御フローグラフを逆方向にたどり、変数が生存している命令の範囲を特定します。

  6. 一時変数のソート:

    • 計算された生存期間の開始点（start）に基づいて、すべての一時変数をソートします。これは、線形スキャンアルゴリズムの重要なステップです。

  7. 線形スキャンによる一時変数のマージ:

    • ソートされた一時変数を順に処理します。
    • inuseリスト（現在レジスタに割り当てられている、またはマージ候補として考慮されている変数）とfreeリスト（解放された変数）を管理します。
    • 現在処理している一時変数vの開始点よりも前に終了する変数があれば、それらをinuseリストからfreeリストに移動します。
    • freeリストの中から、現在の一時変数vと同じ型を持ち、かつ生存期間が重複しない変数v1を探します。
    • もしv1が見つかれば、vをv1にマージします（v->merge = v1）。これにより、vはv1と同じメモリ位置を共有するようになります。
    • 適切なマージ先が見つからない場合、vはinuseリストに追加されます。inuseリストは、変数の終了点に基づいてソートされ、最も長く生存する変数がリストの先頭に来るようにします。

  8. プログラム内のノード参照の更新:

    • CFGの各フローノードを再度走査し、各命令のfrom.nodeとto.nodeが一時変数を参照している場合、その一時変数がマージされている（v->merge != nil）ならば、参照をマージ先の変数に更新します。

  9. 宣言リストのクリーンアップ:

    • 関数の宣言リスト（curfn->dcl）を走査し、マージされた（v->mergeが設定されている）または削除された（v->removedが設定されている）一時変数を宣言リストから削除します。これにより、コンパイラが最終的に生成するシンボルテーブルから不要な一時変数が取り除かれます。

  10. 補助構造の解放:

    • 一時変数の情報（TempVar配列、bystart配列、inuse配列）を解放し、Nodeのoptフィールドをクリアします。
    • flowend(g)を呼び出して、CFGに関連するリソースを解放します。

このmergetemp関数は、コンパイラのレジスタ割り当てフェーズの直前に実行されることで、レジスタ割り当て器が処理しなければならない一時変数の数を大幅に削減し、結果としてより効率的なコード生成を可能にします。

関連リンク

参考にした情報源リンク