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

このコミットは、Goコンパイラのcmd/gc（現在のsrc/cmd/compileに相当）における最適化に関する修正です。具体的には、append()組み込み関数のインライン化処理において発生していた不要な境界チェックを排除することを目的としています。これにより、生成されるコードの効率が向上します。

コミット

commit 4b0eb19a05133d4cc117fefe1e37ea1e35a64c73
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Mon May 20 23:19:41 2013 +0200

    cmd/gc: eliminate a useless bounds check in inlined append().
    
    R=golang-dev, daniel.morsing, r
    CC=golang-dev
    https://golang.org/cl/9358043

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

https://github.com/golang/go/commit/4b0eb19a05133d4cc117fefe1e37ea1e35a64c73

元コミット内容

cmd/gc: eliminate a useless bounds check in inlined append().

変更の背景

Go言語のコンパイラは、プログラムの実行効率を向上させるために様々な最適化を行います。その一つが「境界チェックの最適化 (Bounds Check Elimination, BCE)」です。スライスや配列にアクセスする際、インデックスが有効な範囲内にあるかを検証する「境界チェック」が挿入されますが、コンパイラは静的解析によって、そのチェックが不要であると判断できる場合にこれを省略します。

このコミット以前のGoコンパイラでは、append()組み込み関数がインライン化される際に、特定の状況下で不要な境界チェックが挿入されていました。append()はスライスに要素を追加する関数であり、内部的にはスライスの容量を拡張するために新しいスライスを作成する操作（s[:n+argc]のようなスライス式）を伴うことがあります。このスライス式に対して、コンパイラが誤って「境界が確定している」ことを示すフラグ（nx->bounded = 1）を設定してしまい、結果として冗長な境界チェックが残存していました。

この不要な境界チェックは、プログラムの実行時にわずかながらオーバーヘッドとなり、パフォーマンスに影響を与えていました。本コミットは、この特定のケースにおける無駄な境界チェックを排除し、コンパイラが生成するコードの効率を改善することを目的としています。

前提知識の解説

• Goコンパイラのwalkフェーズ: Goコンパイラは、ソースコードを機械語に変換する過程で複数のフェーズを経ます。walkフェーズ（src/cmd/gc/walk.cに実装されていた）は、抽象構文木（AST）をより低レベルな中間表現（IR）に変換し、最適化やコード生成に適した形に書き換える役割を担っていました。このフェーズでは、組み込み関数のインライン化や、スライス操作などの特定の言語機能のセマンティクスをIRに変換する処理が行われます。

• append()組み込み関数: append()はGo言語の組み込み関数で、スライスに1つ以上の要素を追加するために使用されます。スライスの容量が不足している場合、append()はより大きな容量を持つ新しい基底配列を割り当て、既存の要素をコピーし、新しい要素を追加します。この内部的な処理には、既存のスライスを拡張するようなスライス操作が含まれます。

• 境界チェック (Bounds Check): Go言語はメモリ安全性を重視しており、スライスや配列へのアクセス時には、インデックスが有効な範囲内にあるかを確認する境界チェックが自動的に挿入されます。例えば、s[i]のようなアクセスでは、0 <= i < len(s)が満たされているかを確認します。

• 境界チェックの最適化 (Bounds Check Elimination, BCE): コンパイラは、静的解析によってインデックスが必ず有効な範囲内にあることを証明できる場合、対応する境界チェックを省略します。これにより、実行時のオーバーヘッドが削減され、パフォーマンスが向上します。例えば、ループ内でインデックスが確実に範囲内にとどまることが保証される場合などです。

• Node構造体: Goコンパイラの内部では、プログラムの各要素（変数、式、関数呼び出しなど）がNodeという構造体で表現されます。これらのNodeはASTや中間表現の構築に使用されます。Node構造体には、そのノードの種類（Op）、型情報、関連する値、そして様々なフラグが含まれます。

• OSLICE: OSLICEは、Goコンパイラの内部中間表現におけるオペレーションコード（Op）の一つで、スライス操作（例: s[low:high]、s[:]など）を表します。

• nx->bounded: Node構造体（ここではnxという変数名で参照されている）のboundedフィールドは、そのノードが表す式（特にスライス式）が「境界が確定している」状態にあることを示すフラグです。このフラグが設定されている場合、コンパイラは対応する境界チェックを省略できる可能性があります。しかし、誤って設定されると、本来不要な境界チェックが残存する原因となります。

• nx->etype: Node構造体のetypeフィールドは、通常、そのノードが表す型の「要素型 (element type)」を示します。例えば、スライス型[]intのetypeはintになります。しかし、このコミットの文脈では、nx->boundedの代わりにnx->etype = 1が設定されており、1が具体的な型を表すとは考えにくいです。これは、当時のC言語で書かれたコンパイラ内部の特定のフラグや状態を示すために、etypeフィールドが一時的に流用されたか、あるいは1が特定の内部的な型IDを表す可能性が考えられます。この変更の主目的はboundedフラグの削除による境界チェックの排除であり、etype = 1はそれに伴うコンパイラ内部の状態調整であると推測されます。

技術的詳細

このコミットは、Goコンパイラのsrc/cmd/gc/walk.cファイル内のappend関数（Goのappend()組み込み関数のコンパイラ内部処理）に焦点を当てています。このファイルは、Goコンパイラの初期のC言語実装の一部であり、ASTのウォークと中間表現への変換を担当していました。

問題は、append()がインライン化される際に、スライスの容量を拡張するために生成されるスライス式（例: s[:n+argc]）に関連していました。このスライス式は、コンパイラ内部ではOSLICEオペレーションコードを持つNode（コードではnxとして参照）として表現されます。

以前のコードでは、このOSLICEノードに対してnx->bounded = 1;という行が実行されていました。これは、コンパイラに対して、このスライス式の境界が確定している（つまり、インデックスが常に有効範囲内にある）ことを示唆するものでした。しかし、append()のインライン化の特定の文脈では、このboundedフラグの設定が誤っており、結果としてコンパイラが不要な境界チェックを挿入してしまう原因となっていました。

本コミットでは、このnx->bounded = 1;の行を削除することで、コンパイラがこの特定のOSLICEノードに対して無駄な境界チェックを適用するのを防ぎます。これにより、コンパイラはより効率的なコードを生成できるようになります。

代わりにnx->etype = 1;が追加されていますが、これはetypeが通常「要素型」を意味することを考えると、直感的には理解しにくい変更です。しかし、当時のC言語で書かれたコンパイラのコードベースでは、特定の内部的な状態やフラグを示すために既存のフィールドが流用されることがありました。このetype = 1は、無駄な境界チェックの排除と同時に、OSLICEノードの内部状態を正しく設定するための、コンパイラ内部の調整である可能性が高いです。例えば、特定の最適化パスで必要とされる情報や、後続のコンパイラフェーズでの処理を適切に行うためのマーカーとして機能していたのかもしれません。

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

--- a/src/cmd/gc/walk.c
+++ b/src/cmd/gc/walk.c
@@ -2537,7 +2537,7 @@ append(Node *n, NodeList **init)
 	l = list(l, nod(OAS, nn, nod(OLEN, ns, N)));	 // n = len(s)
 
 	nx = nod(OSLICE, ns, nod(OKEY, N, nod(OADD, nn, na)));	 // ...s[:n+argc]
-	nx->bounded = 1;
+	nx->etype = 1;
 	l = list(l, nod(OAS, ns, nx));			// s = s[:n+argc]
 
 	for (a = n->list->next;	 a != nil; a = a->next) {

コアとなるコードの解説

変更はsrc/cmd/gc/walk.cファイルのappend関数内にあります。この関数は、Goのappend()組み込み関数のコンパイラ内部での処理を担当しています。

1. nx = nod(OSLICE, ns, nod(OKEY, N, nod(OADD, nn, na))); この行は、スライスsをn+argcの長さまで拡張するスライス式（s[:n+argc]に相当）を表すOSLICEノードnxを生成しています。nsは元のスライス、nは元のスライスの長さ、argcは追加される引数の数、naは新しい容量に関連する値です。

2. - nx->bounded = 1; この行が削除されました。以前のコードでは、生成されたOSLICEノードnxに対してboundedフラグを1（真）に設定していました。これは、このスライス式の境界が確定していることをコンパイラに示唆するものでしたが、append()のインライン化の特定の文脈では、この設定が誤っており、結果として不要な境界チェックが挿入されていました。この行を削除することで、その無駄な境界チェックが回避されます。

3. + nx->etype = 1; 削除された行の代わりに、この行が追加されました。etypeフィールドは通常、ノードが表す型の要素型を示しますが、ここでは1という値が設定されています。この変更の正確な意図は、当時のコンパイラ内部の文脈に深く依存しますが、無駄な境界チェックの排除と同時に、このOSLICEノードの内部状態を正しく設定するための、コンパイラ内部の調整であると推測されます。例えば、後続のコンパイラフェーズでこのノードを適切に処理するための特定のマーカーとして機能していた可能性があります。

この変更により、append()のインライン化によって生成されるコードから不要な境界チェックが取り除かれ、全体的な実行効率が向上しました。

関連リンク

• Go CL 9358043: https://golang.org/cl/9358043

参考にした情報源リンク

• Go compiler walk.c and OSLICE context:
  • https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQGAh_3xXRY4byAzlOkQRwyd_Rv5yWGSSjwpAsG94T3zC7Z38n9Mp_vGad9Y4Ubw9vM6k0OKZYVB-hhH1PXavakzo8v1YZr5lf7OdcMTQiFxlIsOzOGoQqSF4-aRiIi0Y0l_pf0jQuHhHhFIlYtIswlyO2jP3HsNAE9R
  • https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQGXyimEz_cSBWAJQdAfjGclGa5ebLlRQrR2JmLaIrkO_40xcmgBrI9C7xoZ9RiGf2zs1BK3U7zhqU1ucrF4U85NDZVH6zO247O4sO3b0sxB6S1lfAE1XYN7sqrVX30odqoMAv-sQY1HFP7iupa6ODXCOiGQkj_I0LEMOyZa8r1ImrGQZS4MHPrL4TE=
  • https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQEHQUYj4vQEMXf13ZmPQAORP3CFEoOYlQ0NPOOdj7nbRjjHK76DC1jTNcCuEorzlwQvGOSPOrgX_znG1BY3Jlr-TDINCcpY-BROloi3WxsBNJJJZM2r9NcXGitVdtW6VuWiWkXWE1Fjpa9nGfVQcTF7huzonev_i365_Bh57mTy2pxMJNlWKC21S8-CZWYxAqH6oKONUhgV125e
• Go Bounds Check Elimination:
  • https://vertexaisearch.cloud.google.com/grounding-api-redirect/AUZIYQH0FLBdCBmbsFoquOuDnPHkCgt3JB2dm1cpPdUnmqgfLGKR-FI7yj5k4XoX6ZHdyPkrjP1mCSEKxvHa6J-iNDPN80uGXCnXhJUNbn-XYbCzzVrDkvMeWqlebWOkVOtIJY_YBOqrCrcj_I94gqUOkW82VPM=