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

このコミットは、Go言語のコンパイラおよびランタイムの一部に影響を与える変更を含んでいます。主な変更は、switch文のコンパイル方法の最適化に焦点を当てています。

• src/cmd/6g/gen.c: Go言語の64ビットアーキテクチャ向けコンパイラ（6g）のコード生成部分です。このファイルにswitch文の定数ケースを効率的に処理するための新しいロジックが大幅に追加されました。
• src/cmd/gc/walk.c: Go言語のコンパイラにおける抽象構文木（AST）の走査（ウォーク）処理を行う部分です。このコミットでは、エラーメッセージの出力方法に関する軽微な変更が含まれています。
• src/runtime/hashmap.c: Go言語のランタイムにおけるハッシュマップの実装です。データのアライメントに関する変更が含まれています。

コミット

• コミットハッシュ: e875055461d9b99fb4dfe2d8022098578a27a17e
• 作者: Ken Thompson ken@golang.org
• 日付: Fri Nov 14 16:24:27 2008 -0800

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

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

元コミット内容

    switch
    
    R=r
    OCL=19288
    CL=19288

このコミットメッセージは簡潔に「switch」とだけ記されており、Go言語のswitch文に関する変更であることを示唆しています。

変更の背景

このコミットの主要な目的は、Go言語のswitch文、特に多数の定数ケースを持つswitch文のコンパイル効率を向上させることにあります。初期のコンパイラでは、switch文の各caseをシーケンシャルに比較するコードが生成されることがあり、ケース数が増えるにつれてコンパイルされたコードの実行速度が低下する可能性がありました。

この変更により、コンパイラは定数ケースのswitch文に対して、より最適化されたコード（具体的には二分探索のような構造）を生成できるようになり、実行時のパフォーマンスが改善されます。これは、コンパイラが生成するアセンブリコードの品質を高め、Goプログラム全体の実行効率を向上させるための重要なステップです。

前提知識の解説

Go言語のswitch文

Go言語のswitch文は、他の多くの言語と同様に、与えられた式の値に基づいて異なるコードブロックを実行するための制御構造です。Goのswitch文は、caseに複数の値を指定したり、caseに式を指定したり、fallthroughキーワードを使って次のcaseに処理を継続させたりする柔軟性を持っています。

コンパイラのコード生成

コンパイラは、プログラミング言語で書かれたソースコードを、コンピュータが直接実行できる機械語（アセンブリコード）に変換するソフトウェアです。この変換プロセスには、字句解析、構文解析、意味解析、中間コード生成、最適化、そして最終的なコード生成といった段階があります。このコミットは、特に「最適化」と「最終的なコード生成」の段階に関わっています。

switch文のコンパイル戦略

switch文を機械語にコンパイルする際には、いくつかの戦略があります。

1. シーケンシャルな比較 (Sequential Comparison): 最も単純な方法で、各caseを上から順にif-else if-elseのように比較していく方法です。ケース数が少ない場合には効率的ですが、ケース数が増えると線形的に比較回数が増え、パフォーマンスが低下します。
2. ジャンプテーブル (Jump Table): switch式の値が連続した整数である場合によく用いられます。switch式の値を配列のインデックスとして使用し、対応するcaseブロックへのジャンプ先アドレスを格納したテーブル（ジャンプテーブル）から直接アドレスを取得してジャンプします。これは非常に高速ですが、ケース値が密接している場合にのみ適用可能です。
3. 二分探索 (Binary Search): ケース値が連続していない（疎な）場合や、文字列、浮動小数点数など、直接インデックスとして使えない値の場合に有効です。case値をソートし、二分探索アルゴリズムを用いて目的のcaseブロックを特定します。これにより、比較回数を対数的に（O(log N)）削減できます。

このコミットは、主に3番目の二分探索戦略を定数ケースのswitch文に適用することで、コンパイルされたコードの効率を向上させています。

Goコンパイラ (6g)

6gは、Go言語の初期のコンパイラツールチェーンの一部であり、64ビットアーキテクチャ（特にx86-64）向けのGoプログラムをコンパイルするために使用されました。Go言語のコンパイラはC言語で書かれており、このコミットで変更されているsrc/cmd/6g/gen.cもC言語で記述されています。

C言語のポインタと構造体

GoコンパイラのコードはC言語で書かれているため、Case*, Node*, Prog*といったポインタや構造体が頻繁に登場します。

• Node: 抽象構文木（AST）のノードを表す構造体です。ソースコードの各要素（変数、式、文など）がNodeとして表現されます。
• Case: switch文のcase節を表す構造体で、caseの値と、そのcaseに対応するコードブロックへのポインタ（Prog*）を含みます。
• Prog: アセンブリ命令を表す構造体です。コンパイラはProg構造体のリストを生成し、それが最終的に機械語に変換されます。

技術的詳細

このコミットの核心は、src/cmd/6g/gen.cに追加されたcsort、casecmp、swconstの3つの新しい関数と、既存のswgen関数の変更にあります。

csort 関数

Case* csort(Case *l, int(*f)(Case*, Case*))

この関数は、Case構造体のリンクリストをソートするためのマージソートアルゴリズムの実装です。switch文の定数ケースを効率的に二分探索するためには、まずこれらのケースをソートしておく必要があります。fは比較関数へのポインタで、casecmp関数がこれに渡されます。

casecmp 関数

int casecmp(Case *c1, Case *c2)

この関数は、2つのCase構造体に含まれる定数値を比較するためのものです。switch文のcaseには、整数、浮動小数点数、文字列などのリテラル値が指定されることがあります。casecmpは、これらの異なる型の値を適切に比較し、ソート順を決定します。

• Wlitfloat: 浮動小数点数リテラルの比較 (mpcmpfltflt)
• Wlitint: 整数リテラルの比較 (mpcmpfixfix)
• Wlitstr: 文字列リテラルの比較 (cmpslit)

whatis関数は、Nodeの型を判別するために使用されます。

swconst 関数

void swconst(Case *sa, int nc, Node *n1, Node *tmp)

この関数は、定数ケースを持つswitch文のコード生成の核心を担います。saはソートされたCaseリストの先頭、ncはケースの数、n1は比較に使用する一時的なNode、tmpはswitchの対象となる式の一時的な値を保持するNodeです。

• 少数のケースの処理 (nc < 4): ケースの数が少ない場合（このコードでは4未満）、コンパイラは各caseをシーケンシャルに比較するコードを生成します。これは、OEQ（等価比較）命令を使用して、switchの対象値（tmp）と各case値（s->scase）を比較し、一致すれば対応するcaseブロック（s->sprog）へジャンプする命令を生成します。シーケンシャルな比較は、オーバーヘッドが少ないため、少数のケースでは効率的です。

• 多数のケースの処理 (nc >= 4): ケースの数が多い場合、swconstは二分探索のアプローチを採用します。

  1. 中央のケースを見つける: nc/2番目のケースを見つけ、そのケースを基準にリストを2つに分割します。
  2. ジャンプ命令の生成:
     • p1 = gbranch(AJMP, T): まず、中央のケースの比較を行うコードへの無条件ジャンプ命令を生成します。
     • p2 = pc: 現在のプログラムカウンタ（pc）を保存し、これがswitchの対象値が中央のケースより小さい場合に実行される「低い半分」のコードブロックの開始点となります。
  3. 再帰呼び出し（低い半分）: swconst(sa, n, n1, tmp) を呼び出し、分割されたリストの低い半分（中央のケースより小さい値のケース）に対して再帰的にコードを生成します。
  4. 中央のケースの比較:
     • setlineno(s->scase): ソースコードの行番号を設定します。
     • n1->op = OLE; n1->left = tmp; n1->right = s->scase;: switchの対象値（tmp）が中央のケース値（s->scase）以下であるかを比較するOLE（Less than or Equal）命令を生成します。
     • bgen(n1, 1, p2): この比較結果に基づいて分岐命令を生成します。もしtmp <= s->scaseであれば、p2（低い半分のコードブロック）へジャンプします。
  5. 再帰呼び出し（高い半分）: swconst(sb, nc-n, n1, tmp) を呼び出し、分割されたリストの高い半分（中央のケースより大きい値のケース）に対して再帰的にコードを生成します。
  6. パッチ処理: patch(p1, pc) と patch(p3, pc) は、先に生成しておいたジャンプ命令のターゲットアドレスを、適切なコードブロックの開始アドレスに修正します。これにより、コンパイル時にジャンプ先が確定します。

この再帰的な構造により、生成されるアセンブリコードは二分探索木のような形になり、switch文の実行時に必要な比較回数が大幅に削減されます。

swgen 関数の変更

swgen関数は、Go言語のswitch文全体のコード生成を統括する関数です。このコミットでは、swgenが定数ケースを識別し、それらをcsortでソートし、swconstに渡して最適化されたコードを生成するロジックが追加されました。

• sa = C; nc = 0;: 定数ケースのリストの開始点と数を初期化します。
• for(s=s0; s!=C; s=s->slink) ループ内で、各caseの型をwhatis(s->scase)で判別します。
• Wlitfloat, Wlitint, Wlitstr のいずれかであれば、定数ケースとしてカウントし、saとse（リストの開始と終了）を更新します。
• 定数ケースのグループが途切れた場合、またはループの最後に、se->slink = C; でリストを終端し、sa = csort(sa, casecmp); でソートし、swconst(sa, nc, &n1, &tmp); で最適化されたコードを生成します。

src/cmd/gc/walk.c の変更

このファイルでは、エラーメッセージの出力方法がfatalからyyerrorに変更されています。

• fatal("walktype: top=%d %O", top, n->op); → yyerror("didn't expect %O here", n->op);
• fatal("mapop: top=%d %O", top, n->op); → yyerror("didn't expect %O here", n->op);

fatalはコンパイラを即座に終了させる関数ですが、yyerrorはエラーを報告しつつコンパイル処理を継続させることが可能です（ただし、最終的にエラーがあればコンパイルは失敗します）。これは、よりユーザーフレンドリーなエラー報告メカニズムへの改善を示唆しています。

src/runtime/hashmap.c の変更

このファイルでは、ハッシュマップのデータアライメントに関する変更が行われています。

• datasize = rnd(datasize, 8); → datasize = rnd(datasize, sizeof (void *));

rnd関数は、指定されたサイズを特定のアライメントに丸めるために使用されます。以前は8バイトアライメントに固定されていましたが、sizeof (void *)を使用することで、ポインタのサイズ（システムによって4バイトまたは8バイト）に合わせたアライメントを保証するようになりました。これは、コードのポータビリティを向上させ、異なるアーキテクチャ上での正しいメモリレイアウトを保証するための変更です。

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

このコミットのコアとなる変更は、src/cmd/6g/gen.cファイルに集約されています。特に、以下の新しい関数と、それらを呼び出すswgen関数の変更が重要です。

• csort 関数（約30行の追加）
• casecmp 関数（約20行の追加）
• swconst 関数（約60行の追加）
• 既存の swgen 関数内での、定数ケースの識別、ソート、そして swconst の呼び出しロジックの追加（約30行の変更）

これらの変更により、switch文のコンパイル戦略が根本的に改善されました。

コアとなるコードの解説

swconst関数は、Goコンパイラが定数ケースを持つswitch文をどのように最適化されたアセンブリコードに変換するかを示す最も重要な部分です。

この関数は、ソートされたCase構造体のリストを受け取り、そのリストのサイズ（nc）に基づいて異なるコード生成戦略を採用します。

1. 少数のケース (nc < 4):

   if(nc < 4) {
       for(s=sa; s!=C; s=s->slink) {
           setlineno(s->scase);
           memset(n1, 0, sizeof(*n1));
           n1->op = OEQ; // 等価比較
           n1->left = tmp; // switch対象の値
           n1->right = s->scase; // caseの値
           walktype(n1, Erv);
           bgen(n1, 1, s->sprog); // 一致したらcaseブロックへジャンプ
       }
       return;
   }
   

   ここでは、各case値に対してOEQ（等価比較）命令を生成し、switchの対象値と比較します。一致すれば、そのcaseに対応するコードブロック（s->sprog）へジャンプする命令（bgen）が生成されます。これは、if (tmp == case1) { ... } else if (tmp == case2) { ... } のようなシーケンシャルな比較に相当します。

2. 多数のケース (nc >= 4):

   n = nc/2; // 中央のケースを見つける
   for(s=sa; s!=C; s=s->slink) {
       n--;
       if(n == 0)
           break;
   }
   n = nc/2;
   sb = s->slink;
   s->slink = C; // リストを2つに分割
   
   p1 = gbranch(AJMP, T); // 無条件ジャンプ命令を生成 (後でパッチ)
   p2 = pc; // 低い半分のコードブロックの開始点
   swconst(sa, n, n1, tmp); // 低い半分を再帰的に処理
   
   p3 = gbranch(AJMP, T); // 無条件ジャンプ命令を生成 (後でパッチ)
   patch(p1, pc); // p1のジャンプ先を現在のpcに設定 (中央のケースの比較へ)
   
   setlineno(s->scase);
   memset(n1, 0, sizeof(*n1));
   n1->op = OLE; // 以下であるか比較
   n1->left = tmp;
   n1->right = s->scase; // 中央のcaseの値
   walktype(n1, Erv);
   bgen(n1, 1, p2); // tmp <= s->scase なら低い半分へジャンプ
   
   swconst(sb, nc-n, n1, tmp); // 高い半分を再帰的に処理
   patch(p3, pc); // p3のジャンプ先を現在のpcに設定 (switch文の終わりへ)
   

   この部分では、二分探索のロジックがアセンブリレベルで構築されます。

   • まず、ケースリストを中央で2つに分割します。
   • gbranch(AJMP, T) は、無条件ジャンプ命令を生成します。この時点ではジャンプ先は未定（T）ですが、後でpatch関数によって適切なアドレスに修正されます。
   • p2 = pc は、現在のプログラムカウンタ（pc）を保存し、これが「低い半分」のcaseを処理するコードブロックの開始アドレスとなります。
   • swconst(sa, n, n1, tmp) の再帰呼び出しにより、低い半分のcaseに対するコードが生成されます。
   • patch(p1, pc) は、最初に生成したジャンプ命令p1のターゲットを、現在のpc（つまり、中央のcaseの比較コードの開始点）に設定します。
   • n1->op = OLE; は、「以下であるか」を比較する命令を生成します。switchの対象値が中央のcase値以下であれば、bgen(n1, 1, p2) によって低い半分のコードブロック（p2）へジャンプします。
   • そうでなければ、高い半分のcaseを処理するためにswconst(sb, nc-n, n1, tmp) が再帰的に呼び出されます。
   • patch(p3, pc) は、高い半分の処理が終わった後にswitch文の終わりへジャンプするための命令p3のターゲットを修正します。

この一連の処理により、コンパイラはswitch文の定数ケースに対して、効率的な二分探索の分岐構造を持つアセンブリコードを生成します。これにより、実行時の比較回数が大幅に削減され、特に多数のcaseを持つswitch文のパフォーマンスが向上します。

関連リンク

• Go言語のswitch文に関する公式ドキュメント: https://go.dev/tour/flowcontrol/8
• Go言語のコンパイラに関する一般的な情報（Goのソースコード構造など）: https://go.dev/doc/contribute#source

参考にした情報源リンク

• Go言語の公式ドキュメント
• Go言語のソースコード（特にsrc/cmd/6gディレクトリ内のファイル）
• コンパイラ設計に関する一般的な知識（特にコード生成と最適化の戦略）
• マージソートおよび二分探索アルゴリズムに関する知識